Sweep and Prune - Implementation

[CuppoJava]

Hi,
I'm writing a sweep and prune implementation in Java but it gets pretty slow at times. I use a hashtable to maintain the list of active pairs. I found the bottleneck to be the many insertions and deletions from the hashtable. Is there a better data structure that I can use?

Thanks
-Cuppo

[Erwin Coumans]

I'm not convinced about Java's performance and memory access, but apart from that:

A good description of a fast implementation of the Sweep and Prune broadphase can be found in Gino van den Bergen's book on collision detection: http://www.dtecta.com and
http://www.amazon.com/exec/obidos/tg/de ... s&n=507846

Basically using arrays is the best and fastest.
Nowadays memory access is the bottleneck, and traversing the memory linearly (array) is the most cache friendly. Linked list and hashmap trashes the cache. Obviously, on inserts you will need to copy memory, but that won't be too bad. Especially when you add a batch insert, so you can re-allocate a batch, instead of one at a time. Pre-sort the batch for the axis, and insert the whole batch in linear time.

There are lots of other optimizations to make, using integers (quantized floats) instead of floats, etc. In my experience the Sweep and Prune is still the best broadphase available. Commercial engines like Havok, Novodex, Meqon all use it. I'm planning to add an implementation in Bullet later this year.

Using arrays obviously

Erwin

[CuppoJava]

Hi,
Thanks for that reply. I'll check out van den Bergen's book. PS: Would you recommend that one or "Real-Time Collision Detection" by Christer Ericson?

Is there an online site that can explain how to use arrays in a sweep and prune algo?

eg: Given a pair of two objects, I need to search for an existing entry, if found I increase the counter by one dimension, if not then add a new entry. etc...

Before: I kept the active pairs in a sorted array. Everytime I found a pair I used a binary search to see if the pair exists. But this turned out many times slower than the hashmap approach.

Thanks a lot for your help Erwin.

[dcoming]

eg: Given a pair of two objects, I need to search for an existing entry, if found I increase the counter by one dimension, if not then add a new entry. etc...

Before: I kept the active pairs in a sorted array. Everytime I found a pair I used a binary search to see if the pair exists. But this turned out many times slower than the hashmap approach.

Different methods have tradeoffs but the extreme end in favor of performance, if you're willing to trade O(n^2) memory for constant-time operations (insertion, removal, read, write), is the following:

You need an n by n matrix M such that M[i,j] is the counter for how many dimensions objects i,j overlap on. You'll also want pointers in this or another similar matrix that indicate (e.g., by an index or pointer) the location of the pair's representation in an unsorted list if they overlap on all dimensions. The "active list" should be efficient to use since it is unsorted.

You can greatly reduce memory requirements of the above suggestion with the following enhancements:
Use a lower triangular matrix representation. This means row 1 has 1 column, row 2 has 2 columns,... row n has n columns.. etc. This cuts memory in almost half, and you just need to make sure that when you access it, you order i,j s.t. i <= j. This one does not worsen asymptotic performance.
You can also use a sparse matrix representation since the number of overlapping objects is generally less than O(n^2). There are many to choose from, but some may hurt asymptotic worst-case performance.
Something to note: choose your matrix representation wisely so that adding objects doesn't require you to reallocate a whole n+1 by n+1 matrix each time you add an object to the scene.

[CuppoJava]

Thanks for those details.
I tried a matrix representation before but I neglected to include a pointer to the location of the pair in the unsorted active pairs list, and so searched the entire matrix for dimensions==3.

I'll think about the matrix representation, but I'll dwell on that for a while. Can you give me a few keywords that I can research for that?

A 2D array is gonna run into exactly the problem that you mentioned.

Many Thanks.
-Cuppo

[CuppoJava]

Thanks for those details.
I tried a matrix representation before but I neglected to include a pointer to the location of the pair in the unsorted active pairs list, and so searched the entire matrix for dimensions==3.

I'll think about the matrix representation, but I'll dwell on that for a while. Can you give me a few keywords that I can research for that?

A 2D array is gonna run into exactly the problem that you mentioned.

Many Thanks.
-Cuppo

[dcoming]

Thanks for those details.
Can you give me a few keywords that I can research for that?

A 2D array is gonna run into exactly the problem that you mentioned.
-Cuppo

From a software engineering perspective you may want to create a wrapper class for the matrix and have all of your code use the interface provided by the wrapper. At first, just have the wrapper work around a 2D array (its easiest) to get things working. Once you're confident it is all working properly, you can just plug in some other open source sparse matrix code. I don't use java for this, but I searched "sparse matrix java" and found MJT and JMP both for Java. Whichever you select shouldn't matter since you're not actually performing matrix operations here, just storing information.

[CuppoJava]

Thanks, you've been a great help.
I'll get my code working with a triangular 2D array first, then I'll take a look at some sparse matrix implementations and port it to Java if it's not too complicated.