Last week I worked on an implementation of the GJK and EPA agorithms using purely mathematical volumes. Each shape is defined only by a
get_support) function, which returns its extent in a direction.
While this is a nice and useful way to define geometry for those particular interference algorithms, it would be really nice to be able to actually see the geometry for debugging. To do this, a mesh approximation must be generated using only a
My idea is to use an algorithm similar to an icosphere generator. Here’s an outline of the modified algorithm:
- Start with an icosahedron and push each vertex to the extents of the object.
- For each triangle, if it has an area larger than some minimum, subdivide it into four triangles.
- For each pair of vertexes which are closer than some maximum, combine them into one.
- Repeat steps 2 & 3 until step 2 produces no triangles.
The only subtlety is in step 2, where I subdivide based on the “normalized” vertexes of the shape (which are just the vertexes of triangles on a unit icosphere).
The idea is to quickly generate a mesh which fills in high-detail areas with more polygons and leaves planar areas simple. It should result in a mesh with higher poly count in areas of higher detail.
In this shot, three different geometries were meshed using this method - they are drawn using white wireframes. A cube, a sphere, and a sphere-swept cube (which is just the Minkowski sum of the two). The wireframe for the plain old sphere is mostly masked by its non-debug mesh in this picture :P
Here are a few more. Pay no heed to the intersecting cubes. Nor the tiny icosahedrons inside the capsule shapes.
find_furthest(direction)functions are fairly simple, especially with the convention that
directionis given in the space of the object. For a point primitive, for example,
find_furthestwill always return the origin. For a line segment, it will always return one of the endpoints (whichever is most aligned with
direction). For a sphere, it will return a vector of the length of its radius, aligned with
Minkowski sums are easily obtained by simply adding the results of the
find_furthestfunctions of two primitives.
I have not yet implemented the idea in full - my current implementation is naive and results in some overlapping vertexes and duplicate triangles. I might post some code once I give it another pass.
I’m not sure this is the best way to achieve debug meshes for geometry defined with a
find_furthestfunction, but it’s my best idea for now. Please comment if you’ve got an idea or know a better way :)