Saturday, 21 May 2011

Moar better collision detection.

Up until now, the only collision detection between the player's ship and the environment had been with the main outline of the world generated by the initial brush carving, which is a relatively simple shape. However, for a properly completed environment there will also be a lot flair (decorative) objects adorning the environment, and it's also important to be able to collide with them.

In addition, the laser impact effects have also been updated, with the impact explosion orientation now being determined by the normal of the impacted surface. It also kicks up some debris particle effects, although these are currently the same regardless of the surface type being hit, and thus look odd for some of the alien flora.



Flair intersection

There were two parts to getting this to work, both of which drew heavily on my existing codebase for creating and merging vector brushes (which has held up surprisingly well, given that there are a few bits that could really do with improving).

The first part is, for a given 2D (or basic 3D) mesh, generating a 2D vector brush of the outline. This abridged version is as follows:
  1. Identify all edges within the mesh. This is something that needs calculating, as by default meshes are stored in terms of vertices/triangles.
  2. Identify the set of triangles that use each edge (the set must at least of size 1, else where the hell did the edge come from?) 
  3. Determine whether each edge is potentially part of the outline.  If an edge has only one triangle associated with it, then it's always an outline edge.  For multiple triangles, it is an outline edge if the third point of each triangle (i.e. that not part of the edge) all lie on the same side of the line.
  4. Throw out all the non-outline-edge edges. 
  5. Starting on any outline edge, following connected edges around until you come back to the original edge in a loop.  In normal situations (apart from some awkward 3D configurations) there will never be any branching to worry about that.  Add that as a vector path.
  6. Repeat 5. for any currently unused outline edges until all are accounted for.
  7. Merge the set of vector paths together to form the final outline (which is a whole different bunch of algorithms).
Then, once you've generated the vector brushes for all the flair objects, you can then merge them together, and then again with the main world outline brush in order to produce the final collision geometry. Finally, take that geometry and generate a binary tree from it in order to allow efficent intersections. 

No comments:

Post a Comment