In order to integrate a shape into the physics engine, you need to be able to detection intersections between that shape and the others supported by the collision detection engine.
Simple Primitive IntersectionUp until now, Juggernaut has only properly supported circle/circle and circle/line interactions: the main world brush is defined by a series of straight lines (organised into a hierarchical tree structure for efficient collision), and the objects themselves are defined by a series of bounding circles. These are the simplest types of collision, as there is only ever one possible contact point between the primitives (to clarify, circles can have two actual intersections with a line/other circle, but only a single contact point is required to resolve them).
|A very rough image showing example contact points/normals for circle/line and circle/circle collision detection. By convention, the normals are defined as pointing into object A.|
For the line/circle case you need to create the function closestPointOnLine( Point A, Line B ), which will determine the closest point on the line segment B to the point A, which may either be a point along B or one of the endpoints of B. Intersection/non-intersection may then be determined by comparison of the distance of the circle centre to the closest point on B with the radius of the circle.
For a more in-depth look (including the actual maths) this site is a very useful resource.
Convex Primitive IntersectionSo, for the simple primitive case, the contact point information can be calculated directly. However, what if we want to have a more complex shape, such as an arbitrary convex polygon? Convex polygons are selected as dealing directly with non-convex polygons is much more difficult, and it is always possible to decompose non-convex polygons into multiple convex polygons. In this case, working out whether the objects intersect is much more difficult, and a naive approach would probably involve comparing every edge in shape A with every edge in shape B. Luckily, this is not necessary!
The key concepts and algorithms required in order to solve this problem are:
- The Minkowski difference (see here).
- The Gilbert–Johnson–Keerthi distance algorithm (or just GJK algorithm)
- Alternatively to GJK, a Separating Axis Theorem-based approach such as the Lin-Canny algorithm.
- The Expanding Polytope Algorithm, which may be used in conjunction with GJK in order to improve performance on deep penetrations.
The Juggernaut convex shape handler is based around GJK, and I'll mention a couple of things that I've found about it.
- It works absolutely amazingly for determining whether objects intersect or not.
- If the objects *do* intersect, the raw GJK results can be unreliable, as the closest simplex edge won't necessarily correspond to an edge on the convex hull of the Minkowski difference. To ensure that this always happens, you'll need to use the Expanding Polytope Algorithm in these cases for robust behaviour.
- Both Shape A vertices are identical and the Shape B vertices define an outside edge of B.
- Both Shape B vertices are identical and the Shape A vertices define an outside edge of A.
- Both the Shape A and Shape B vertices define outside edges of A and B, respectively. This will only really occur when the edges are very close to parallel, and can also be associated with a triangular simplex of zero are. Also, this may or may not occur in exactly the same situation depending on the initially selected simplex point.
- The vertices do something else and define non-external edges of A and/or B (may happen with raw GJK, but not GJK+EPA).
So, the solution that I've come up with is as follows: for the shape where only one vertex is returned by GJK, check both edges that are connected to it for contact points. This is almost certainly not the only solution to this problem, but it's the only one I've found that produces stable results thus far. This is demonstrated in the diagram below: