Panda3D
New Features to the Collision Detection System

Abstract

Collision detection is essential in a game engine. It is the reason you go bonkers playing Flappy Bird. However, it would be difficult and expensive to represent each object using its exact geometry, so a better idea would be to put those objects in bounding volumes or CollisionSolids. These CollisionSolids are mathematically defined, so by using some math, a collision system would be able to detect their intersections with each other. Additional information on the collision should be provided, including the point of intersection and the vector normal to the contact (to push back on).

Currently, Panda3D is missing 3 collision tests: parabola into box, parabola into inverse sphere, box into capsule. Here are some use cases that we've probably seen before:

1. An Angry Bird hitting a box (parabola into box)
2. Protecting the audience from a football in a spherical stadium (parabola into inverse sphere)
3. Some box object hitting a player (box into capsule)

My first goal would be to add these collision tests.

My second goal would be to add another CollisionSolid named CollisionHeightfield. The idea is that we can represent heightfields using a grayscale image, with lighter (taller) and darker (lower) pixels. We can use this concept to efficiently deal with collisions in uneven terrain, rather than representing the terrain as individual CollisionPolygons.

Implementation Details

Preface

Since part of the project is figuring out the algorithms to use, this section consists of investigation on existing collision tests in Panda3D, and how they can be used as bases. At the end, I give a Minimal-Viable-Product outline of CollisionHeightfield.

Details

• Parabola into InvSphere

  Currently, there exists a Parabola into Sphere test, which splits the Parabola into tiny line segments and checks if they intersect the Sphere. Implementing Parabola into InvSphere will use the previous method as a basis, but needs further investigation on how it differs from the regular Sphere. I also have to keep in the mind edge cases, which includes the Parabola being entirely inside the bubble, or entirely outside.

• Parabola into Box

  Since the Box is not quadratic, the previous method is not necessary. The Parabola into Box test might resemble the Parabola into Polygon test, which uses the Parabola into Plane test. The Parabola into Plane test uses a quadratic equation, implementation can be found here. Edge cases include the Parabola being entirely inside the Box.

• Box into Capsule

  This one I'm not too sure about. For inspiration, I've taken a look at Ericson's chapter on Sphere-Swept Volumes as well as Capsule into Box and Box into Sphere (Arvo's Algorithm), but further investigation is required.

• CollisionHeightfield
  • MVP
    1. Can be loaded from PNMImages*
    2. Can be read/written from/to BAM files**
    3. Test intersection from sphere, box, and lines (rays, segments)
  • Extra Features
    1. Test intersection from capsule
    2. Can be read/written from/to EGG files*** (will have to add new syntax)
  
  * PNMImages are 2D arrays of pi(xels). For CollisionHeightfield, we need only a grayscale image, so the xels will have gray components
  ** BAM files allow users to store Panda3D objects as a file, but is not human-readable
  *** EGG files are the same except they are human-readable, thus the need for new syntax
  

Timeline

Week	Dates (Mon - Sun)	Description
Community Bonding	05/06 - 05/27	Review related math topics Algorithm study and research
Phase 1
1	05/27 - 06/02	Implement parabola into box detection Write unit tests for parabola into box collisions.
2	06/03 - 06/09	Implement parabola into inverse sphere detection Write unit tests for parabola into inverse sphere collisions.
3	06/10 - 06/16	Implement box into capsule detection Write unit tests for box into capsule collisions.
4	06/17 - 06/23	Discuss with mentors for requirements specification on CollisionHeightfield Begin implementing CollisionHeightfield MVP Generate from PNMImage Test collision from Ray
Phase 2
5 & 6	06/24 - 06/30 07/01 - 07/07	Continue implementing CollisionHeightfield Test collision from Segment Test collision from Line Test collision from Sphere
7 & 8	07/08 - 07/14 07/15 - 07/21	Finish implementing CollisionHeightfield MVP Test collision from Box Bam serialization Possibly implement extra features
Phase 3
9 & 10	07/22 - 07/28 07/29 - 08/04	Write more unit tests for all collisions with CollisionHeightfield Write documentation for the 3 new collision tests and CollisionHeightfield
11 & 12	08/05 - 08/11 08/12 - 08/19 (Monday)	Make a sample game that implements CollisionHeightfield and add it to panda3d/samples Complete any last unit tests and documentation

Roadblocks

One the most challenging aspect of this project is that it requires an understanding of 3D space and linear algebra. I do have a introductory understanding of 3D space, but I will have to self-study some linear algebra. Thankfully, the Collision Detection Book has an overview of the math required for this project, which will be very useful. I will be utilizing the book and other online resources to prepare myself with the math required for this project.

Research Materials

• Erison, C. (2005) Real-Time Collision Detection Book
• Bullet Heightfield Shape