CS298 Proposal

Extending Box2D's collision detection and collision response algorithms

Joshua Newth (mrfurious at gmail dot com)

Final paper here: CS298 Final Report - PDF

Advisor: Dr. Chris Pollett

Description:

The purpose of this project is to extend Box2D to use Minkowski Portal Refinement, an alternative to GJK for collision detection, and speculative contacts, a method of implementing continuous physics that offers improved stability and parallelization. Speculative contacts in their simplest implementation do not honor restitution (the characteristic of a collision that describes how much energy is lost), and an attempt will be made to address this shortcoming.

The primary academic goal is to understand some algorithmic approaches in modern constraint based physics engines.

Schedule:

Week 1: 2/25/13	Due: Update site with work so far (MPR, Box2D collision detection).
Week 2: 3/4/13	Due: MPR implementation in Distance2D. Add MPR to Box2D.
Week 3: 3/11/13	Due: Complete MPR implementation in Box2D. Due: Begin adding speculative contacts to Box2D.
Week 4: 3/18/13	Due: Speculative contacts.
Week 5: 3/25/13	Due: Speculative contacts.
Week 6: 4/1/13	Due: Speculative contacts.
Week 7: 4/8/13	Due: Speculative contacts.
Week 8: 4/15/13	Due: Restitution.
Week 8: 4/22/13	Due: Paper layout / MPR in Box2D.
Week 8: 4/29/13	Due: First draft of paper.

Deliverables:

An implementation of MPR integrated in to Box2D's collision detection pipeline.

Speculative contacts incorporated in to Box2D's collision resolution mechanism.

These two new approaches benchmarked against the existing state of the art.

References:

Eberly, David M.Game Physics, 2nd Edition. New York: Morgan Kaufman, 2010. Print.

Hecker, Chris.Physics, Part 1: The Next Frontier. Game Developer Magazine. Oct/Nov 1996. Print.

Hecker, Chris. Physics, Part 2: Angular Effects. Game Developer Magazine. Dec/Jan 1996. Print.

Hecker, Chris. Physics, Part 3: Collision Response. Game Developer Magazine. Feb/Mar 1997. Print.

Hecker, Chris. Physics, Part 4: The Third Dimension. Game Developer Magazine. June 1997. Print.

Catto, Erin. GDC_2008. www.box2d.org. Feb 2010. Web.

Wikimedia Foundation, Inc. http://en.wikipedia.org/wiki/Euler_method. April 2013. Web.

Newth, Joshua. Multicore Architectures: Parallelism Problems and Software Solutions. San Jose State University, 2010. Print.

Catto, Erin. Computing Distance with GJK. Game Developers Conference. San Francisco, California, March 2010. Presentation.

Wikimedia Foundation, Inc. http://en.wikipedia.org/wiki/Minkowski_addition. April 2013. Web.

Physics2D.com GJK Algorithm http://physics2d.com/content/gjk-algorithm, May 2013.

de Berg, Mark, et al. Computational Geometry: Algorithms and Applications, Third Edition. Berlin: Springer 2008. Print.

Catto, Erin. Iterative Dynamics with Temporal Coherence. Crystal Dynamics, Menlo Park, California, 2005. Print.

Strunk, Oliver. Stop My Constraints From Blowing Up!, Game Developers Conference. San Francisco, California, 2013.

Snethen, Gary. XenoCollide: Complex Collision Made Simple. Game Programming Gems 7. Ed. Scott Jacobs. Boston: Course Technology 2008. Print.

Snethen, Gary. XenoCollide. http://xenocollide.snethen.com, May 2013. Web.

Snethen, Gary. Re: Minkowski Portal Refinement (MPR) for 2D. http://www.bulletphysics.org/Bullet/phpBB3/viewtopic.php?f=6&t=1964&start= 15. Physics Simulation Forum. Web.

Firth, Paul. Speculative Contacts A Continuous Collision Approach . 2011. http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/. May 2013. Web.

Brian Mirtich Impulse Based Dynamic Simulation of Rigid Body Systems. Dissertation, University of California Berkeley, 1996. Print.

Catto, Erin. Continuous Collision Detection. Game Developers Conference, San Francisco, California. March 2013. Presentation.

Wikimedia Foundation, Inc. http://en.wikipedia.org/wiki/Root-finding_algorithm. April 2013. Web.

PS4 See The Future, Specifications PS4, https://us.playstation.com/ps4/, May 2013. Web.