How can I find the intersecting point of three planes?

Question

I'm trying to build render the raw data from a Quake 3 .map file with Java. The .map format stores brush (shape) information as a series of planes, but I'd like to convert them to points of the form (x,y,z). The math involved is a bit beyond me at this point, so does anyone have any advice on how I can do this? I'm fine with using external libraries if need be, but I'd rather use my own code if possible.

Some data to play with:

Dimensions:   64*64*64
Position:     All sides are equidistant from the origin (0,0,0)
Shape:     Cube
( 64 64 64 ) ( 64 -64 64 ) ( -64 64 64 )
( 64 64 64 ) ( -64 64 64 ) ( 64 64 -64 )
( 64 64 64 ) ( 64 64 -64 ) ( 64 -64 64 )
( -64 -64 -64 ) ( 64 -64 -64 ) ( -64 64 -64 )
( -64 -64 -64 ) ( -64 -64 64 ) ( 64 -64 -64 )
( -64 -64 -64 ) ( -64 64 -64 ) ( -64 -64 64 )

Edit:

This data is showing a cube, which has 6 sides. Each of these six sides can be stored as a plane, with three coordinates to show the position and orientation. Each row of the above data shows one plane, and all 6 of the rows make the 6 planes that make up a cube.

This image helps illustrate my point: Three Points Defining a Plane

Points p1, p2, and p3 are what I'm giving per row, in the above data.

The Quake 3 engine has to sort out what parts of the planes to keep at compile time, but I'm not interested in that at the moment. If you would like more information, feel free to ask!

Bargeboard

Can you please explain how your data represents three planes, and not 18 vectors? – Underling

Answer 1

I go to Wolfram Mathworld whenever I have questions like this. For this problem, try this page: Plane-Plane Intersection

Equation 8 on that page gives the intersection of three planes. To use it you first need to find unit normals for the planes. This is easy: given three points a, b, and c on the plane (that's what you've got, right?), take the cross product of (a-b) and (a-c) to get a normal, then divide it by its own magnitude to get a unit normal.

Abradant

Answer 2

From http://gamedev.net/forums/topic/430170-intersection-point-of-three-planes/3860657/?page=1

Given three planes defined by:

• a normal vector, m_Normal, and
• distance to the origin, m_distance.

The following will determine the unique point where all planes intersect at a point (unless a unique point doesn't exist, in the case where two or more planes are parallel).

 BOOL Plane3D::Intersects(const Plane3D &other1, const Plane3D &other2, Vector4 &intersectionPoint) const {
     float denom = DotProduct(CrossProduct(m_Normal, other1.m_Normal), other2.m_Normal);
     if( 0.0 == denom ) {
         return FALSE;
     }
     intersectionPoint = ( -(m_distance * CrossProduct(other1.m_Normal, other2.m_Normal)) - 
            (other1.m_distance * CrossProduct(other2.m_Normal, m_Normal)) - 
            (other2.m_distance * CrossProduct(m_Normal, other1.m_Normal)) )/denom; 
     return TRUE;
 }

Note that this may be numerically unstable for nearly-parallel planes, the if should really include an epsilon (denom < ε).

Southerland