Relationship of bounding box to a shape

[gerald]

Wrt to collisions, here's my understanding, albeit sketchy.

Bounding boxes are used (only?) during the broadphase collision detection to reduce the # of collision that must be checked via more expensive methods (ie. SAT applied to polygons). Bounding boxes are always rectangular shapes that are large enough to hold the shape, regardless of the # of edges a shape is composed of.

I'm not yet sure how bounding boxes are sized though.

Any / all of this remotely accurate?

Thanks,
-Gerald

[slembcke]

That's exactly it. The bounding boxes are checked for overlap before calling more expensive collision detection routines. Each frame, Chipmunk updates the collision detection data and generates a tight fitting bounding box to fit them.

They are still a little useful outside of the engine when you want to check collisions yourself or if you just want to find the maximum height of a shape, etc.

[gerald]

Question 1:

I'm interested to understand the spatial indexing that is based on axis-aligned bounding boxes a bit more. I see in the code that you check the bounding boxes for two shapes at the beginning of the narrow-phase algorithm. That part I understand, but this occurs after the spatial algorithm has already done its magic.

Is there a simple explanation of how the broad-phase bounding box algorithm works? And, how it relates to the bounding boxes associated with each shape (I'm assuming they are related here). I didn't see this in the documentation and am interested to understand it.

Comment:

I also plan to use the library to detect which sprite has been touched on touch devices. The obvious (so far) api to call for this is cpShapePointQuery. I was hoping to see that this leveraged the bounding-box prior to doing the more expensive algorithm as well and it does. Nice!

Question 2:

I don't think I will be leveraging any of the physics as my game/story is not a physics-based variety. However, the collision detection algorithm is quite compelling vs. building my own. Has anyone bothered to refactor the codebase to include only the collision detection stuff? The simplification would be nice for folks only using that function. I'm considering doing this work for my engine, but would be delighted not to repeat that work if it has been done already.

Thanks,
-Gerald

[slembcke]

Chipmunk 5 only supported spatial hashing as a broadphase. I originally read this paper, and it's still probably the best I've seen: http://www.beosil.com/download/Collisio ... _VMV03.pdf

Chipmunk 6 defaults to a new algorithm based on AABB trees. I started out with some of my own ideas about dynamically constructing the trees. Then I found a presentation written by Erwin Cournams who wrote the Bullet Physics library on the subject, so I used a bunch of his ideas too (can't find a link to it now). Basically it builds a binary tree of bounding boxes with each level getting coarser and coarser until you hit the root. It also has a collision cache where it memorizes overlapping leaves and only updates the cache when a leaf moves far enough. It's very very efficient.

It's possible to pull out the collision detection from the rest of the physics, but it's not really going to be that easy as it was never really intended to do it. You will probably be better off just moving the bodies around for your collision shapes and override the default PreSolve() collision callback to return false (meaning it will ignore it and not apply physics). Then you will still get all of the collision events and skip all the really expensive parts of the physics.

[gerald]

Cool. Let me know if you find the AABB paper you mentioned. I'd love to read it.

[slembcke]

Hmm. This was part of it: https://graphics.stanford.edu/wikis/cs2 ... =Erwin.pdf Look at the last couple of pages. I thought I remembered seeing something more in depth, but maybe that was it. I had already spent a lot of time on my own implementation before I found it.

[gerald]

Thanks. I'll check it out.

[gerald]

Quick follow-on question for this thread as I'm just getting back to it to do the implementation (dang startup!)...

Is there a bounding box for all of the shapes contained in a given body? I know there is one per shape, but wondered if a larger one is maintained that contains all of the shapes associated with a given body?

[slembcke]

No, just per shape. I have thought about grouping them together in the spatial index, but I'd need to do some performance tests to see if it even makes sense in the general case.

[gerald]

It was of interest to me because the broad phase algorithm isn't terribly applicable for my engine, but the narrow phase turns out to be quite useful, both for touch detection and collision detection. I thought that checking the bounding box for a body prior to checking the shapes would be a good way to reduce the # of checks required.

I believe I saw a routine that merged bounding boxes in to a larger one somewhere? If so, perhaps I can construct my own from the shapes on a given body and compare against that first. If not, I can always construct something of my own.