raycast through the sweep and prune space

[Erwin Coumans]

Although Gino van den Bergen's explanation of my idea is better and much more detailed, here is the original posting on comp.graphics.algorithms:

http://www.erwincoumans.com/p/raycast_o ... _prune.pdf

It is a very efficient way to do raycasting on dynamics scenes. It works best for very long rays (bullets), that do have a hit. See the detailed description in "Collision Detection in Interactive 3D Environments".

For very short ray, it is better to add its aabb inside the Sweep and Prune space, and perform the raycast on the overlapping objects of that aabb.

[Erin Catto]

I have implemented this algorithm. I have to say that it is a nice idea. You have to be careful to implement it correctly. A tricky case is when the line segment originates on the side of a box.

Shorter segments are faster than longer ones. Long segments have O(N) complexity where N is the number of boxes in the SAP. It is still usually faster than a brute force approach. I have also found that dynamic objects are usually spread out horizontally, so you can ignore horizontal planes in the traversal.

I have seen little else published on this topic. I'm guessing that many games just do O(N) brute force.

Erwin, did you ever do timing comparisons with brute force. How about for long segments?

As I recall, for my implementation, it is about twice as fast as brute force for segments that span the scene.

[Erwin Coumans]

Although the time complexity of the Sweep and Prune (SAP) raycast is indeed O(n) for n broaphase entries, for a lot of scenes, the average time complexity for long rays that do have an early hit is much better. For both indoor scenes and city scenes, you will barely traverse the whole scene.

Also, a good implementation can cache the starting point of the ray, deriving it from an existing broadphase entry. There are more optimizations, but I would start by making the implementation cache friendly: storage of the SAP as arrays instead of linked list. This means the SAP raycast can benefit from this too.

I recall some conversation with Pierre Terdiman whose implementation of the ray box is so efficient that it was faster then his implementation of the SAP raycast. But I think he used linked list for the SAP. Perhaps Pierre can shed a light on this ?

[Pierre]

I recall some conversation with Pierre Terdiman whose implementation of the ray box is so efficient that it was faster then his implementation of the SAP raycast. But I think he used linked list for the SAP. Perhaps Pierre can shed a light on this ?

I can use arrays or linked-lists in the SAP with a compile flag. I used arrays to test the raycast.

What I found is that for long rays crossing the whole scene, brute force was indeed faster. That's completely normal since you traverse all the boxes in both cases, but you do more work in the SAP raycast.

However when you cache the start of the ray, and when you're lucky and get an early exit, then the SAP raycast is faster.

The break-even point was somewhere in-between, but not enough in favor of the SAP raycast for my taste

Overall I didn't use it because I already had extra data structures in place, giving O(log N) raycasts anyway. [So, yes, when a dynamic object moves I update both the SAP and the other structure, but since both of them have O(1) updates it's not really an issue.]

- Pierre

[Guest]

extra data structures in place, giving O(log N) raycasts anyway

Interesting. What kind of datastructure has O(1) update ? and O(log(n)) complexity for long raycast ?

If it is a tree, like a loose kdop tree, after some motion, the tree might become very unbalanced, which makes the O(log(n)) not valid anymore. Do you rebalance the tree ?

[Pierre]

Interesting. What kind of datastructure has O(1) update ? and O(log(n)) complexity for long raycast ?

If it is a tree, like a loose kdop tree, after some motion, the tree might become very unbalanced, which makes the O(log(n)) not valid anymore. Do you rebalance the tree ?

I'm using a loose octree. As far as I know it's still O(log n) after some motion. Actually I don't think there's a difference between what you get after some motion and what you would get by re-building the octree from scratch at this point.

- Pierre

[shinichikudo]

I am not so knowledgeable about this matter. So i have to learn it. Thanks for the post.
simulation credit auto