Hive Assault: Physics and Collision Detection
Hive Assault Physics & Collision Detection
Real-time Collision detection on a dynamic implicit surface
Frank Losasso, 2001. Email: losasso@rice.edu
There are two types of collision detection in the Hive Assault code. The first one implemented makes use of the polygons that the voxel engine creates, while the second one uses the half-planes from the voxel volume.
The polygon version makes use of the fact that ellipsoids can be normalized into unit spheres, against which collision with planes and line segments are very easy and accurate. The method goes as follows:
1. Take the object position and the velocity vector and normalize them by the dimensions of the bounding ellipsoid of the object.
2. Find potential set of colliding polygons by getting the polygons within |velocity| + largest radius of bounding ellipsoid + some epsilon.
3. Go through this set of potential colliders checking which one is the first one the ellipsoid would collide with first (this step is non trivial).
4. Move the ellipsoid as far as it can go before colliding.
5. Calculate the new velocity (the rest of the old velocity projected onto the colliding polygons plane).
6. If the new velocity is larger than some epsilon, go to step 2, if not, we have found where the object should end up.
This approach is nice in that it is only limited in accuracy by the data representation for numbers that the machine uses, so we are guaranteed that the ellipsoid will never be penetrated by any geometry.
The drawbacks are however that it is complicated (step 3 requires a lot of calculations) and comparatively slow compared to the half-planes method.
The half-plane method uses the fact that the voxel representation allows for extremely fast line-of-sight calculations (A side effect of the fact that all free space within voxels is guaranteed to be convex). This allows us to basically use a porcupine ball to model collisions of a sphere. By doing line intersections of all the edges of the arms with the geometry we can check whether or not a collision occurred.
The drawback of this is that it's not accurate. Basically for any reasonable number of arms, it is possible of sharp geometry to penetrate the bounding sphere of the ball hence creating unrealistic situations where a player is pierced by some part of the level. This however is not a big problem in this game, as the geometry doesn't contain many sharp edges.
The advantage of this method is that it's fast. It's in fact about 10x the speed of the polygonal method. It is also much simpler in terms of code complexity, which means that bugs are both easier to find and fix.
Currently the game uses the half-plane collision model for both players and aliens, but there are some drawbacks that are visible in the game from this. There are some rooms with slim pillars in which the player seems to be able to walk through them, which may be because the arms on the porcupine are too far apart.