Not logged in, Join Here! or Log In Below:  
News Articles Search    

 Home / 3D Theory & Graphics / Sweep and Prune Account Manager
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.

April 27, 2005, 01:31 AM

Hi all,

I've been reading on the sweep and prune algorithm all around the net but all papers fail to explain how to efficiently compare/exploit the overlap lists, after the 'sort & count overlap' pass.

It may be the trivial part of the algorithm but I cannot spot a fast way to do it (except a nice n~n wich is just suicide since there's an awful lot of overlaps in each lists). The few papers having a start of explanation all speak of maintaining a matrix of possible collision pairs... I hope this is not the case as the memory cost would just be prohibitive.

If somebody can help :)

Arne Rosenfeldt

May 06, 2005, 02:12 AM

Sweep and Prune
is meant for small n,
oterwise it would be hirachical from the start


May 06, 2005, 05:04 AM

Hierarchal bounding volumes are certainly useful for accelerating collision detection further (especially for colliding dynamic objects against a static world and suchlike). Nonetheless, sweep and prune can be useful for large numbers of dynamic objects. The matrix of possible collision pairs you alluded to is a sparse matrix, so it doesn't take that much memory - you just store the nonzero elements together with their locations. Effectively a plain list, maybe hash-map, of possible collision pairs.


May 06, 2005, 07:49 AM

Collision Detection in Interective 3D Environments and Real-Time Collision Detection are both excellent books about collision detection and both explains a sweep-and-prune algorithm. And no, there's no need for any kind of hierarchical structure. All you need is 3 sorted arrays ( one for each axis ) to keep track of all AABB overlaps.

This thread contains 4 messages.
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.