Data structure for fast sphere-sphere collision detection
Author
Hi all,
I''m trying to find an efficient algorithm/data structure for this problem:
Given a set of spheres in 3d-space, find all the spheres intersecting a ''query''-sphere in better-than-linear time (i.e. without checking all the spheres in the set).
I was thinking about some space-partitioning techniques but each sphere can change its position and radius arbitrarily from frame to frame so I would have to rearrange (or rebuild) the structure every frame.
Have you any suggestion?
Thanks.
Well isn't the question rather detect ALL collisions in less than n squared ? Not exactly the same.
The most obvious way is use a log(n) space partition, quadtree, octree, or more accurate data structures for this issue. Then you can actually check each sphere separately. Just put the sphere where the center (C) is, don't care about radius for storage. Care about radius (R) only when you check intersections, add the max radius (Rmax) for any sphere and inspect the neighbour nodes (store connectivity info) that intersect this "new" sphere (C,R+Rmax).
To handle movement you can simply compute the bounding sphere of all S(t) between ti and ti+1 (between two frames). Simply Cbounding is the middle :
Cbounding= 0.5*( C( ti) + C(ti+1) )
And the radius is also ez to compute : R+D/2, D being the distance run by the sphere. Now use these bounding spheres and the previous static algorithm.
Else there are other data structures based on collision events and 3 ordered lists for each coordinate. Not so ez to explain and I don't remember a link or name for this algo. However an optimized octree or quadtree is more efficient and general to me.
[edited by - Charles B on October 21, 2003 7:29:37 AM]
Static collisions
The most obvious way is use a log(n) space partition, quadtree, octree, or more accurate data structures for this issue. Then you can actually check each sphere separately. Just put the sphere where the center (C) is, don't care about radius for storage. Care about radius (R) only when you check intersections, add the max radius (Rmax) for any sphere and inspect the neighbour nodes (store connectivity info) that intersect this "new" sphere (C,R+Rmax).
Dynamic collisions
To handle movement you can simply compute the bounding sphere of all S(t) between ti and ti+1 (between two frames). Simply Cbounding is the middle :
Cbounding= 0.5*( C( ti) + C(ti+1) )
And the radius is also ez to compute : R+D/2, D being the distance run by the sphere. Now use these bounding spheres and the previous static algorithm.
Else there are other data structures based on collision events and 3 ordered lists for each coordinate. Not so ez to explain and I don't remember a link or name for this algo. However an optimized octree or quadtree is more efficient and general to me.
[edited by - Charles B on October 21, 2003 7:29:37 AM]
Look into AABB trees and OBB trees. I think theres a method for doing dynamic BSP trees, though I don''t know how reasonable it is.
quote:Original post by Zeu5
Given a set of spheres in 3d-space, find all the spheres intersecting a ''query''-sphere in better-than-linear time (i.e. without checking all the spheres in the set).
I was thinking about some space-partitioning techniques but each sphere can change its position and radius arbitrarily from frame to frame so I would have to rearrange (or rebuild) the structure every frame.
Have you any suggestion?
Thanks.
Hi Zeu5, if I understand it correctly, ABT can be a solution for you, maybe a little more powerful than you need. Accordin to Yann,
"They are a hybrid approach combining the advantages of octtrees and BSPs, and adding some more options. They can also be used on fully dynamic geometry."
Here''s a link in the forum
Yes but ABT degenerates as Yann explains and keeping it efficient is complex and surely takes some undecent processing time to update continuously. Even letting the ABT degenerate requires to modify the partition geometry from leaves to root all the time. It also remains a binary space partition. So it's fundamentally not more efficient than an octree/quadtree ... if the data you store in it fits well with an OT/QT.
That's where you missed a fundamental point. For the special case of spheres there is no need for overlapping sectors since you just need to store a ref where the center is. So OT QT or RG (regular grid) are the best and most simple solutions. You can greatly accererate the tree since the relevant info is surely at a certain level of LOD (between min and max radius). Thus you can boost the tree with regular grids up to a certain level, then quad/oct-nodes then a max depth.
Any dynamic object can be simply bounded by a sphere. With spheres you don't care about rotations, only translations. Well the conclusion is simple ... Dynamic=spheres (for level1 ColDet). Static=anything efficient for your scene.
[edited by - Charles B on October 23, 2003 6:12:41 AM]
That's where you missed a fundamental point. For the special case of spheres there is no need for overlapping sectors since you just need to store a ref where the center is. So OT QT or RG (regular grid) are the best and most simple solutions. You can greatly accererate the tree since the relevant info is surely at a certain level of LOD (between min and max radius). Thus you can boost the tree with regular grids up to a certain level, then quad/oct-nodes then a max depth.
Any dynamic object can be simply bounded by a sphere. With spheres you don't care about rotations, only translations. Well the conclusion is simple ... Dynamic=spheres (for level1 ColDet). Static=anything efficient for your scene.
[edited by - Charles B on October 23, 2003 6:12:41 AM]
Hi,
Well, if all your spheres are dynamic you''ll probably be doing swept-sphere-sphere checks, yes? Regarless, I think the best way is use a sweep and prune technique where by you quickly identify pairs of overlaps and then do your more expensive intersection tests on those.
Really watered-down description:
1) Stick an AABB bounding box around each sphere (and the path it has travelled for swept-sphere queries).
2) For each axis, insert into a list all the start and end co-ordinates of each bounding box, the idea being you end up with a list of open and close tags for each box.
3) Look through the list, and where you find two open or two close tags together, you know the boxes have overlapped, and therefore have a possible collision.
Ok, thats not the best description in the world.. Have a look here at OPCODE for a description and a decent implementation (IIRC): http://www.codercorner.com/SweepAndPrune.htm and http://www.codercorner.com/Opcode.htm
Hope that helps a bit.
T
Well, if all your spheres are dynamic you''ll probably be doing swept-sphere-sphere checks, yes? Regarless, I think the best way is use a sweep and prune technique where by you quickly identify pairs of overlaps and then do your more expensive intersection tests on those.
Really watered-down description:
1) Stick an AABB bounding box around each sphere (and the path it has travelled for swept-sphere queries).
2) For each axis, insert into a list all the start and end co-ordinates of each bounding box, the idea being you end up with a list of open and close tags for each box.
3) Look through the list, and where you find two open or two close tags together, you know the boxes have overlapped, and therefore have a possible collision.
Ok, thats not the best description in the world.. Have a look here at OPCODE for a description and a decent implementation (IIRC): http://www.codercorner.com/SweepAndPrune.htm and http://www.codercorner.com/Opcode.htm
Hope that helps a bit.
T
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
