Sign in to follow this  

Collision Detection Presentation

This topic is 3143 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
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
Your presentation seems to focus on the actual collisions. What about satellite issues such as game object types? For instance, you don't check bullets against bullets. Perhaps you might want to include some of those issues in addition to the geometric issues. The optimizations i can think of off the top of my head include:

- Object type comparisons (don't do collision tests for types that don't need it)

- Moving VS Non-Moving objects (you don't need to check non-movers against other non-movers, even if they are both collideable objects)

- Only check A-vs-B and never B-vs-A (redundant)

Share this post


Link to post
Share on other sites
Quote:
Original post by loufoque
Nested bounding volumes are also a form of space partitioning, I don't understand why it's a separate category.


Because space partitioning is about subdividing space into disjoint sub-spaces (e.g. kd-tree, quadtree, octree), whereas object (cf. space) partitioning schemes are about subdividing object into disjoint sub-spaces (e.g. BIH, BVH, BSP).

Think of it like you would be a farmer who finally enters into his deserved pension. As a last act, you must partition your fields for your two sons.


Space Partitioning Example. In a 3d kd-tree, an axis aligned box is divided into two boxes that do not overloap (not that it's not mandatory that the union of the sub-boxes is the initial box, i.e. sub-boxes are allowed to minimize their size). Now you grab you bunch of triangles, and sort each into either the left or the right child box, or into both.

Object Partitioning Example. In a 3d Bounding Interval Hierarchy (a hybrid of Boundin Volume Hierarchy and kd-tree, search the forums at ompf.org/forum for detailed information), you grab your bunch of triangles, and put each of them into either the left child or the right child, but never into both. Obviously, the bounding volumes of the children must be allowed to overlap.

(don't get confused about that BIH is a hybrid of kd-tree and BVH: building the structure is mostly similar to BVH, traversal is inspired by kd-tree).

Quote:
The most popular form of binary space partitioning is kd-trees (at least in research), I think it's worth mentioning.

Why do you think it is most popular? In Realtime Ray Tracing research, and for general purpose ray tracing (as in unspecialized), there is currently a tendency towards Bounding Volume Hierarchies and an ongoing trend of using Bounding Interval Hierarchies. While kd-tree were popular for years, because in combination with Vlastimil Havran's Surface Area Heuristics they yield the maximum, currently available performance for static scenes, kd-trees obviously loose when it comes to rebuilding them, even modern O(N log N) kd-tree compilers are far behind object partitioning schemes. Even a lame implementation of BIH can rebuild a million triangles a few times per second.

For even more funky information, google the name of Alexander Reshetov, or just look at the ompf-forums.

Share this post


Link to post
Share on other sites
Quote:
Because space partitioning is about subdividing space into disjoint sub-spaces (e.g. kd-tree, quadtree, octree), whereas object (cf. space) partitioning schemes are about subdividing object into disjoint sub-spaces (e.g. BIH, BVH, BSP).

An object is nothing more than a subspace. The distinction is thus nonsense.
You're simply confusing uses of the data structure. The second case you showed is the normal use: an index. You build the structure so that the data is balanced in it, and thus you can obtain nice logarithmic neighbor searches and the like. The first case you showed is just static space partitioning, not dependent upon the data, making it therefore useless, since you keep linear complexity for most operations.

Nothing requires the subdivision to be into disjoint subspaces either. See r-trees, for example, where rectangles may perfectly overlap. R-trees are actually the same thing as bounding boxes hierarchies.

Quote:
urrently available performance for static scenes, kd-trees obviously loose when it comes to rebuilding them

Obviously, kd-trees are for static problems.
The canon is that for static problems, you use kd-trees and for dynamic ones, r-trees.
Now I'm not in particular into computational geometry, so I'm not reading bleeding edge papers, but that's what the literature and I assume classes on the subject say.

Share this post


Link to post
Share on other sites
Quote:
Original post by loufoque
Quote:
Because space partitioning is about subdividing space into disjoint sub-spaces (e.g. kd-tree, quadtree, octree), whereas object (cf. space) partitioning schemes are about subdividing object into disjoint sub-spaces (e.g. BIH, BVH, BSP).

An object is nothing more than a subspace. The distinction is thus nonsense.

We don't have a science of everything. Also, gamedev.net is, if any, about applied science, not about your Ivory Tower sciene. In computer graphics and game development (and surely other disciplines) there is a clear distinction between empty space and space filled with objects. Look at the thesises of Vlastimil Havran, Carsten Benthin, Carsten Wächter, Ingo Wald, Henrik W. Jensen, and many more in the field, to see how there is a distinction. See, any empty space has infinitely many, empty subspaces. Do you handle them like space that contains polygons when building your acceleration structure?

Another hint: Space partitioning and Object partitioning are also presumptions about the perspective from which you start building your acceleration structure, which implies quite a lot of things.

So if you are uncomfortable with existing science and convetions, dig in yourself, write papers, write thesises about how it all is nonsense. I would have nothing against it as long as it is serious.

Share this post


Link to post
Share on other sites

This topic is 3143 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this