Chris Pollett > Students >
Newth

    ( Print View )

    [Bio]

    [CS297 Blog]

    [GJK]

    [CS297 Proposal]

    [CS297 Final Report - PDF]

    [CS298 Proposal]

    [CS298 MPR Report]

    [CS298 Box2D Collision Detection Pipeline]

    [CS298 Final Report - PDF]

                          

























Box2D Collision Detection Pipeline

My original research suggested that Box2D would follow the classical model of broadphase pairs identification followed by narrowphase collision detection mediated by pair type-specific agents, similar to the Havok model. Box2D eschews the agents for a more uniform pipeline, which rather than confusing the user with Box-Box or Circle-Circle optimized agents, simply uses a unified approach where all narrowphase collision detection is boiled down to Point - Convex Hull collision. This is actually great, but it took a while to understand. Heres how it appears to work:

1. Create an agent for every pair of shapes with overlapping bounding boxes. This agent maintains the cache of current contact points (and normals, perhaps). This agent persists so long as their AABBs overlap (ie broadphase CD indicates overlap).

2. Start with single points on each feature. These are truly any points - the beauty of GJK is that it is supposed to converge to the closest feature. Bad initial choices merely lead to further iteration.

3. Follow the standard GJK mode, but take advantage of both barycentric regions and Voronoi regions to make the logic faster and more geometric rather than the more algebraic formulations sometimes used.

This points the way to replacing his GJK implementation with MPR, where the interior point will be computed prior to the simplex selection.

This CD pipeline is outlined Erin Cattos presentation at GDC and demonstrated in his cool little application Distance2D.