Intersection points of plane set forming convex hull

Question

Mostly looking for a nudge in the right direction here. Given a set of planes (defined as a normal and distance from origin) that form a convex hull, I would like to find the intersection points that form the corners of that hull. More directly, I'm looking for a way to generate a point cloud appropriate to provide to Bullet.

Bonus points if someone knows of a way I could give bullet the plane list directly, since I somewhat suspect that's what it's building on the backend anyway.

Answer 1

Okay, so I found something that works for me. First off, I'm using this equation to find the intersection point of three planes. (If the denominator is 0 there's no intersection.) I have to loop through all the planes multiple times, but in my case I'm doing it as a pre-process so it's not a big deal.

Just because three planes of the hull intersect, however, does not mean the intersection actually reside on the hull itself. In order to weed out the outliers I test the point to see if it lies "inside" the hull, within a reasonable margin of error. The algorithm for that is pretty simple:

function pointInHull(planes, point) {
    for (i = 0; i < planes.length; i++) {
        plane = planes[i];
        dist = point.dot(plane.normal) - plane.distance;
        if (dist > 0.01) return false; // indicates the point lies in outside the hull
    }

    return true;
}

Since no planes will ever intersect inside the hull (that's what makes it convex!) this gives me all the edge points.

So the basic code is something like this:

pointCloud = [];

for (i = 0; i < planes.length; i++) {
    p1 = planes[i];

    for (j = i+1; j < planes.length; j++) {
        p2 = planes[j];

        for (k = j+1; k < planes.length; k++) {
            p3 = planes[k];

            point = getPlaneIntersectionPoint(p1, p2, p3);

            if(point && pointInHull(planes, point)) {
                pointCloud.push(point);
            }
        }
    }
}

I certainly wouldn't recommend trying this in a realtime situation, but as an offline process it's fine.

Answer 2

A brute-force approach would be:

1. For each pair of planes, find their line of intersection (skip if the planes are parallel).
2. Clip this line by all the other planes, i.e. intersect it with them and keep track of the interval on the line that's inside them. If this interval become empty, skip it and go on to the next line.
3. Add the endpoints of the clipped line segment to the point cloud.

The trouble is that if you have n planes, this takes O(n^3) time, and will generate each point several times (once for each edge that touches it).

After a bit of googling I found that this process is referred to as "vertex enumeration" and there is a paper about a smarter and faster way to do it here. It says it will generate verts for n planes in O(n*v) time, where v is the number of vertices generated. I haven't read the paper in detail, but it looks complicated and uses a bunch of linear programming theory.