How to get the vertices of a polygon described by planes

Question

This is a repost of a question that went unanswered

basically I am trying to model a map that has the following format:

Each brush defines a solid region. Brushes define this region as the intersection of four or more planes. Each plane is defined by three noncolinear points. These points must go in a clockwise orientation:

1--2----------------->
|
3
|
|
|
|
|
,

Each brush statement looks like this:

 {
  ( 128 0 0 ) ( 128 1 0 ) ( 128 0 1 ) //plane 1
  ( 256 0 0 ) ( 256 0 1 ) ( 256 1 0 ) //plane 2
  ( 0 128 0 ) ( 0 128 1 ) ( 1 128 0 ) //plane 3
  ( 0 384 0 ) ( 1 384 0 ) ( 0 384 1 ) //plane 4
  ( 0 0 64 ) ( 1 0 64 ) ( 0 1 64 ) //plane 5
  ( 0 0 128 ) ( 0 1 128 ) ( 1 0 128 )//plane 6
 }

That's probably just a bit confusing when you first see it. It defines a rectangular region that extends from (128,128,64) to (256,384,128). Here's what a single line means:

  ( 128 0 0 ) ( 128 1 0 ) ( 128 0 1 ) 
   1st Point   2nd Point   3rd Point 

I need to find the intersection points of the planes so I can draw the shape only using a method that can draw 2d panels in 3d space. The following code would draw a triangle in space for example:

beginShape();
vertex(x0,y0,z0);
vertex(x1,y1,z1);
vertex(x2,y2,z2);
vertex(x0,y0,z0);
endShape();

Is there a better way to calculate the vertices than to loop through all possibilities of plane interesctions?

Answer 1

I don't think there is any other option: the only information you have about the vertices is contained in the planes, and the only way to get the vertices from the planes is to determine their intersections, so you will have to loop through the possibilities.

To start:

If you are sure the planes do indeed bound a volume, and that none of the planes are parallel, then each combination of 3 adjascent planes should yield one vertex (just by simultaneously solving the plane equation for all 3). You can eliminate vertices outside your volume pretty easily (to be part of the shape, they must be on or 'behind' all of the planes) so you could just test every combination of 3, if you don't have this 'adjacency' information and discard the external points.

It strikes me that you will only have convex volumes using this method - so you can probably just do a 3d convex hull on all those vertices to get drawable triangles for the faces.