Bullet SweepAndPrune optimization (split posting)

[Dirk Gregorius]

I am looking through the Bullet code and try to understand some of the ideas:

Q1: What is actually the motivation for the quantization? What do you win by this? Why do you speak of expanding/shrinking in this context?

Q2: What is the advantage of using continuous arrays instead of a likend list. Again you have to swap (copy) quite a lot of memory when inserting/updating the edge list.

Q3: Is the quantization related to the implementation as array or are these two independent optimizations?

[Erwin Coumans]

I am looking through the Bullet code and try to understand some of the ideas:

Q1: What is actually the motivation for the quantization? What do you win by this? Why do you speak of expanding/shrinking in this context?

Reduce memory cost (and improve performance), and perform integer comparison instead of floating point.

Q2: What is the advantage of using continuous arrays instead of a likend list. Again you have to swap (copy) quite a lot of memory when inserting/updating the edge list.

Arrays are almost always better then linked list nowadays. Traversing linked-lists trashes the cache. Those 3 array are pre-allocated once, and the swapping of endpoint is hence very cache friendly (likely to be in L1 or L2 cache). In case of streaming worlds, with large amount of added new objects the strategy still works, but needs some refinement (I'll discuss this after it is implemented in Bullet).

Q3: Is the quantization related to the implementation as array or are these two independent optimizations?

Independent. However, note that the overlap check is optimized because of array properties: array indices are compared, instead of the actual min/max values.

Hope this helps,
Erwin