Jump to content
  • Advertisement
Sign in to follow this  
way2lazy2care

Collision Detection Presentation

This topic is 3512 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
One quick comment: you might consider including the 'sort and sweep' method in your broad-phase survey.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
since its 2d

Narrowphase:
linesegment vs linesegment, handles every 2d shape that boxs + circles dont work for,( not moving though)

Share this post


Link to post
Share on other sites
Quote:
Narrowphase:
linesegment vs linesegment, handles every 2d shape that boxs + circles dont work for,( not moving though)
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
>>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

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by way2lazy2care
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?

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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!