Collision Detection Presentation
Author
Howdy everyone, I have to do a presentation on basic collision detection methods, and I just wanted to know if I missed anything that should be noted.
I'm doing primarily 2D collision, so 3D collision methods aren't as necessary. It's a short presentation, so I don't need to get too complicated.
Anyways, I have these so far:
Broadphase:
-Quadtrees
-Binary Space Partitioning
-Grids
Narrowphase:
-Bounding Box
-Bounding Circle
-Pixel Perfect
-Separating Axis Theorem
-Sweeptests/multisampling
Anything else I should mention you guys can think of?
Also, does anybody know exactly what spatial hashing is? There are no places that say specifically what it is, but from what I gather it's pretty much any means of separating areas into parts, so it would cover most of the broadphase techniques, but I don't want to say anything about it without knowing for sure what it is.
One quick comment: you might consider including the 'sort and sweep' method in your broad-phase survey.
That's a good spectrum of techniques.
Right now, GJK / MPR is very popular, but a bit 'hard' to implement (especially for contact points calculations). If you can find some time to introduce either of the algorithm, it could be interesting to present an iterative technique for general convex object colliisons.
Right now, GJK / MPR is very popular, but a bit 'hard' to implement (especially for contact points calculations). If you can find some time to introduce either of the algorithm, it could be interesting to present an iterative technique for general convex object colliisons.
since its 2d
Narrowphase:
linesegment vs linesegment, handles every 2d shape that boxs + circles dont work for,( not moving though)
Narrowphase:
linesegment vs linesegment, handles every 2d shape that boxs + circles dont work for,( not moving though)
Quote:Narrowphase:A line-segment-only test will miss the case where one shape is fully contained inside the other. I suppose you could add a vertex containment test, but that seems like a lot of trouble - really, the SAT would be a better bet here (with non-convex shapes decomposed into multiple convex shapes if needed).
linesegment vs linesegment, handles every 2d shape that boxs + circles dont work for,( not moving though)
Author
Line segment vs line segment I think is worth mentioning. I'm not sure I have time to really understand the other two before presenting, but I'll try.
On quad trees, I noticed that the tutorial here:
http://www.gamedev.net/reference/programming/features/quadtrees/
has a fixed leaf size for it's quadtree, but i looked at another sample here:
http://lab.polygonal.de/2007/09/09/quadtree-demonstration/
that has variable leaf size. I'm wondering what the benefits of each of these approaches are? I 'm just slightly confused on the two different approaches.
edit: tried to prettyfy links.
edit2: failed.
On quad trees, I noticed that the tutorial here:
http://www.gamedev.net/reference/programming/features/quadtrees/
has a fixed leaf size for it's quadtree, but i looked at another sample here:
http://lab.polygonal.de/2007/09/09/quadtree-demonstration/
that has variable leaf size. I'm wondering what the benefits of each of these approaches are? I 'm just slightly confused on the two different approaches.
edit: tried to prettyfy links.
edit2: failed.
>>A line-segment-only test will miss the case where one shape is fully contained inside the other.
yeah thanks I forgot about that, AABB test first then linesegmenttest, then 2(one from each shape) point in polygon tests
also WRT bounding boxs u have two sorts, AABB (axis aligned) + OBB (object aligned BB)
>>that has variable leaf size. I'm wondering what the benefits of each of these approaches are? I 'm just slightly confused on the two different approaches.<<
the first one is a true quadtree, the second is a grid (I forget the term)
I use both, each have there benifits
#B is faster for small stuff + #A is faster for large stuff
yeah thanks I forgot about that, AABB test first then linesegmenttest, then 2(one from each shape) point in polygon tests
also WRT bounding boxs u have two sorts, AABB (axis aligned) + OBB (object aligned BB)
>>that has variable leaf size. I'm wondering what the benefits of each of these approaches are? I 'm just slightly confused on the two different approaches.<<
the first one is a true quadtree, the second is a grid (I forget the term)
I use both, each have there benifits
#B is faster for small stuff + #A is faster for large stuff
Author
Quote:Original post by zedz
the first one is a true quadtree, the second is a grid (I forget the term)
I use both, each have there benifits
#B is faster for small stuff + #A is faster for large stuff
sorry, just slightly confused. The gameDev.net tutorial is a real quad-tree and the polygonal labs one is the grid? or vice versa?
Nested bounding volumes are also a form of space partitioning, I don't understand why it's a separate category.
The most popular form of binary space partitioning is kd-trees (at least in research), I think it's worth mentioning.
The most popular form of binary space partitioning is kd-trees (at least in research), I think it's worth mentioning.
Quote:Original post by way2lazy2careQuote:Original post by zedz
the first one is a true quadtree, the second is a grid (I forget the term)
I use both, each have there benifits
#B is faster for small stuff + #A is faster for large stuff
sorry, just slightly confused. The gameDev.net tutorial is a real quad-tree and the polygonal labs one is the grid? or vice versa?
actually sorry I misread, I thought the second page
http://lab.polygonal.de/2007/09/09/quadtree-demonstration/
was only only concerning itself with the leaves
thats where tree part comes from in tree I think
root -> subdivide into parts (nodes/branches) -> repeat this a few times until u come to the leaves (smallest area)
from looking at it again it looks like both links u posted describe essentially the same thing
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement