net.phys2d.raw.collide
Class IntersectionGatherer

java.lang.Object
  net.phys2d.raw.collide.IntersectionGatherer

public class IntersectionGatherer

extends java.lang.Object

This is a very important class for collision detection between polygons for several reasons:

• First of all, it checks two edges for intersections. What edges will be checked for intersections is decided elsewhere.
• All intersecting edges are stored with some additinal information.
• Finally we return a very specific (sub) set of the intersections that is used for the physics simulation.

While intersection tests are rather straight forward and well known problems, the selection of the intersections to return is quite complicated. It suprised me that I was completely unable to find applicable information on this particular problem on the net.

Suppose we have two colliding polygons A and B. Observe that if we trace around the polygons in counterclockwise order starting on an edge of the polygon that is outside the other, we will encounter first an intersection that goes into the other polygon and then one that comes out again.

       ----
   out| B  |in
   ---+----+---
  |A  |    |   |
  |    ->--    |
   ->----------
 

These in- and outgoing intersections can be used to determine two very important things:

1. A collision normal which simply is a line perpendicular to the line from the ingoing to the outgoing intersection.
2. The penetration depth, which is determined by tracing along the in-out line for the longest line parallel to the normal in the overlapping area (see PenetrationSweep).

Retrieving these pairs is relatively easy. We simply sort the gathered intersections in the order they would occur when tracing the contour of A.

Things get complicated when polygons don't just intersect but totally penetrate eachother. First of all, the collision normals would (depending on the specific polygons and their intersection) oppose eachother, this has unpredictable but possibly still acceptible results.

The biggest problem however is the penetration depth that will be completely off. Take for example the intersection pair 1 and 2 in the example. The penetration depth will be determined by the maximum vertical distance between the edges of A between in and out and the edges of B between out and in (both counterclockwise). Clearly this gives very large penetration depths which often are completely wrong.

In the example the final result will not be very problematic: the forces are most likely to cancel eachother out. But even here it's simple to see that the penetration depth for the intersection pair (3,4) will be much bigger than the other. There are many examples that occur frequently in practice which will cause bodies to be shot in orbit (if the physics would've allowed it ;) ).

       ----
    in|A   |out
   ---3----2--------
  |B  |    |        |
  |   |    |        |
   ->-4----1--------
   out|    |in 
       ->--
 

The/A solution actually is quite straightforward: if we throw out one of the two intersection pairs, the penetration depth will be correct and there won't be any normals that cancel eachother out while they shouldn't. Aditionally this technique will decrease the number of feature pairs, which is good for speed.

Throwing out the right pairs still is quite a challange, but we can apply a technique similar to the one we used to get the intersection pairs. Then we traced the contour of A, now we trace the contour of B starting with an outgoing intersection. If we encounter an ingoing intersection of the same pair we accept the pair (i.e. not throw it out) and move on to the next intersection. If we encounter an ingoing intersection belonging to a different pair or an outgoing intersection we throw it out.

We still are not done just yet. The following example shows that it matters a great deal which intersection we start with. If we start at intersection 2, all the other intersection pairs will be thrown out and B will be pushed down. If we had chosen to start with 4 or 6, the result would be more acceptable; only (1,2) would be thrown out and B would be pushed up.

       --------------
      |B             |
      |     ----     |
   out|  in|    |out |in
   ---6----5----4----3--
  |A  |    |    |    |  |
  |   |    |     ----   |
   ->-1----2------------
    in|    |out
       ->--
 

This problem is not really solved currently. There is a heuristic in place that will select the outgoing edge that has the largest number of vertices outside A. In other words, the largest number of vertices between the chosen outgoing intersection and the last ingoing intersection (last as in clockwise as opposed to counterclockwise).

The heuristic is based on the idea that we are more likely to be pushed from A into the direction where the largest part of B is. For the example this would not work, but for many examples in practice it will.

TODO: When we're stacking a lot of triangles the heuristic fails occationaly. The triangles will sometimes jump in directions they shouldn't.

Problems

If we manage to get all intersections between polygons, we should always encounter alternating ingoing and outgoing intersections when tracing either A or B. In practice this isn't really the case for two reasons:

1. We only test intersections for specific edges. These are generated in other classes which could have bugs. This would be a cause of missing intersections.
2. The intersection test in this class has given me trouble over and over again for special cases when endpoints of two edges are involved in the intersections. For example the case where an edge is only touched by a vertex, only an ingoing intersection was created. I've had some much trouble and uncertainty here that I don't know if this is still a problem.
3. Finally an issue that will be hard to solve: the orderings defined by IntersectionComparator and PointerTableComparator suffer of floating point rounding errors when in- and outgoing edges are close together.

In stead of trying to fix this issue or throw out the faulty intersections, I've made some adjustments that will simply skip these intersections. I am afraid that these issues might cause trouble somewhere sometime, so if possible this should be fixed some time.

TODO: This class could use some specialized data structures in stead of the countless arrays which clutter the code with modulo indices.

Field Summary

static int	MAX_INTERSECTIONS The size of the intersections array, thus determening the maximum number of intersections that the IntersectionGatherer can accept.
static float	MIN_PAIR_DIST The minimum distance two intersections have to be apart to be considered a pair

Constructor Summary

IntersectionGatherer(Vector2f[] vertsA, Vector2f[] vertsB)
Construct an IntersectionGatherer for a specific pair of polygons.

Method Summary

Intersection[][]	getIntersectionPairs() Get the pairs of ingoing and outgoing intersections encountered when tracing the contour of polygon A.
Intersection[]	getIntersections() Get the list of intersections, sorted by the order defined by IntersectionComparator.
void	intersect(int a, int b) Intersect two edges of the two polygons and stores the intersecting lines along with their position.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

MIN_PAIR_DIST

public static float MIN_PAIR_DIST

The minimum distance two intersections have to be apart to be considered a pair

MAX_INTERSECTIONS

public static int MAX_INTERSECTIONS

The size of the intersections array, thus determening the maximum number of intersections that the IntersectionGatherer can accept.

Constructor Detail

IntersectionGatherer

public IntersectionGatherer(Vector2f[] vertsA,
                            Vector2f[] vertsB)

Construct an IntersectionGatherer for a specific pair of polygons.

Parameters:

vertsA - The 'first' polygon involved in this collision check

vertsB - The 'second' polygon involved in this collision check

Method Detail

intersect

public void intersect(int a,
                      int b)

Intersect two edges of the two polygons and stores the intersecting lines along with their position.

Parameters:

a - The edge of polygon A to check for intersection with B

b - The edge of polygon B to check for intersection with A

getIntersections

public Intersection[] getIntersections()

Get the list of intersections, sorted by the order defined by IntersectionComparator.

Returns:

A sorted list of intersections

getIntersectionPairs

public Intersection[][] getIntersectionPairs()

Get the pairs of ingoing and outgoing intersections encountered when tracing the contour of polygon A. Some pairs will be filtered out as described in detail in this class's documentation.

Returns:

An array with the intersection pairs which has the dimensions [n][2] or [n][1], where n is the number of intersections. For a pair i getIntersectionPairs()[i][0] will contain the ingoing intersection and getIntersectionPairs()[i][1] the outgoing intersection.