How should I calculate the vertices on n intersecting planes

Question

basically I am trying to model some map brushes that have 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 ) GROUND1_6 0 0 0 1.0 1.0
  ( 256 0 0 ) ( 256 0 1 ) ( 256 1 0 ) GROUND1_6 0 0 0 1.0 1.0
  ( 0 128 0 ) ( 0 128 1 ) ( 1 128 0 ) GROUND1_6 0 0 0 1.0 1.0
  ( 0 384 0 ) ( 1 384 0 ) ( 0 384 1 ) GROUND1_6 0 0 0 1.0 1.0
  ( 0 0 64 ) ( 1 0 64 ) ( 0 1 64 ) GROUND1_6 0 0 0 1.0 1.0
  ( 0 0 128 ) ( 0 1 128 ) ( 1 0 128 ) GROUND1_6 0 0 0 1.0 1.0
 }

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 ) GROUND1_6 0 0 0 1.0 1.0
   1st Point   2nd Point   3rd Point   Texture

I need to find the intersection points 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();

you need 4 planes (or rectangles of infinite size) to create a 3d object with finite limits in the x y and z dimensions.3 rectangles may intersect at a point making a tetrahedron, but it would be of infinite height without a forth plane cutting it somewhere — matthewaveryusa, Sep 16 '10 at 16:32
I think he means where each of two intersect but not at the point where all three intersect. Sort of like a conic across a cube? ~ I would think the naive but trivial solution is to find all maximal and minimal points of intersection between any two planes, then find the maximal triangle across those points, then plot that triangle. But it's been awhile since I've had to think of 3D surfaces and intersection without spending a half hour or more thinking on it. I seem to recall this is covered in later Algebra... — jcolebrand, Sep 16 '10 at 16:36
@mna ~ Did you just contradict your own self? are you working with planes or rectangles? planes may need a fourth to make the "conic" cut, but rectangles have defined edges. They may never intersect (which is a different problem, I think we're all assuming they intersect at some point). So with three rectangles, you can assume that the bounding edge of the triangle won't exceed the maximal points of the rectangle, no? — jcolebrand, Sep 16 '10 at 16:38
Oh I see what he was saying. The answer is still no. If two planes are parallel then you need 4 planes (the 2 additional ones not being parallel) to create at least 1 surface or point., and you need 3 planes to create a surface or point if all planes aren't parallel — matthewaveryusa, Sep 16 '10 at 16:43
Ok, so you want to find the intersection point between any three nonparallel non-colinear planes? Because for all four of them there are the following combinations: ABCD -> ABC (or ACB or CAB or CBA etc), ACD, BCD, ABD. So you need to find the four intersection points as defined by those four points. Then you figure out which three lie on the plane you want (since the math for them is portable, you really just need a function `FindPoint(plane A, plane B, plane C)`) and match them against the plane you want the triangle to be along. (so if on A, ABC, ABD, ACD). — jcolebrand, Sep 16 '10 at 20:19
No. I was looking for the non-trivial pseudo-code to find all intersection points of N planes where some can be parallel and others not, but for which the planes and their intersections create a 2-sphere topology. — matthewaveryusa, Sep 21 '10 at 19:53

score 0 · Answer 1 · answered Sep 16 '10 at 20:25

0

http://mathworld.wolfram.com/Plane-PlaneIntersection.html

This is how you find where three planes intersect. Since you're not working in 4dim (it's a game, right? we see in 3D) then the 3 plane solution given here should be sufficient.

answered Sep 16 '10 at 20:25

jcolebrand

15,889
12
75
121

score 0 · Accepted Answer · edited May 23 '17 at 12:01

No. I was looking for the non-trivial pseudo-code to find all intersection points of N planes where some can be parallel and others not, but for which the planes and their intersections create a 2-sphere topology.

The non-trivial pseudo-code would be either a) someone has already solved this problem, and you're just in code-reuse mode, or b) they're solving the problem for you.

Or c) this is a math problem and not a programming problem. Have you consulted any math professors for assistance on this? There is a math stackoverflow property (two I think!)

The only way I know of to quickly find the points of intersection is to but the vectors into the formula I linked previously. That would give you the points of intersection quite quickly. You've already got all the bits you need to calculate this information.

How to know if a line intersects a plane in C#? - Basic 2D geometry

and

http://www.google.com/search?q=plane+intersection+.net

How should I calculate the vertices on n intersecting planes

2 Answers2