Ok, this will be easy for my favorite math guru''s. I need a C/C++ routine (or even decent pseudo code) that calculates the point where 3 planes intersect (if they do). I need to make a Quake-style brush to polygon converter, so here is the info about the 6-sided brush (from a MAP file): (0 128 64) (0 -256 64) (-384 -256 64) (-128 -128 -192) (-128 0 -192) (-256 0 -192) (-384 -256 64) (-256 -128 -192) (-256 0 -192) (-128 -128 -192) (0 -256 64) (0 128 64) (-384 128 64) (-256 0 -192) (-128 0 -192) (-256 -128 -192) (-384 -256 64) (0 -256 64) The 3 coordinates are the points that define each plane, and there are 6 planes. I need to convert this type of info into n-sided polygons. This particular brush is a 4-sided up-side-down pyramid w/ a notch taken off of the tip. Here are some guidelines: - Brushes are always convex (of course) - The points that define the plane are counter-clockwise. (This is used to determine the normal of the plane) - If a point is outside of the brush, it isn''t a vertex. (That is, it''s been clipped off by another plane) Also, if anyone could convert this formula to C++, it would help. It is supposed to generate the texture mapping U/V coords. The only texture info that''s in the map file is U/V scale, offset, and rotation. I''m not sure what represents what in that formula. Perhaps someone else does. Any help would be VERY appreciated. Thanks, -- Dan

To find the intersection of 3 planes, you may solve the equations
Ax + By + Cz + D = 0
that represent each plane. You have 3 planes and 3 unknowns, so it''s not a problem. Otherwise, you can take a look at
http://mathforum.org/dr.math/faq/formulas/faq.analygeom_3.html#threeplanes
It explains everything you need to know about planes, and how to evaluate the intersection between two planes. Once you have this line, you can easily intersect the third plane.

And "converting" a formula to C++ is API-specific.

Cédric

OK, i will tell you the way we did it in our game-in-development.

Lets say your three points of one plane are _a, _b and _c.

First you want to get the normalized representation of your plane. The normal of that plane is (best you create a structure for planes storing information and place this in the constructor):

normal = crossProduct(_a - _b , _c - _b);
normal.normalize(); // bring len of it to 1.

Now calculate the distande of the plane to the origin:
distance = dotProduct( normal , _a);

Now you have your planes defining your brush in normalized form.
To get the polygons, you need to do the following for each of those planes P:
find two other planes A and B, so there:
1) is intersection point I,
2) and that point I isn''t "outside" your box

cedricl already said how to solve problem 1)
now check for 2) by calculating the disance of your intersection point to all planes of your brush. the point I has to be always in the "inner" side or exact on your plane to be legal.

Now you have 3 planes P, A and B, with an intersecting point of your polygons.
For this iteration P will stay the same anyway.
Now keep planes P and B, and search another plane C so you have an intersecting point of P, B, C fulfilling 1) and 2).
Continue until you come back to A again, and all your intersection points belong to your polygon in the plane P.

Now pick the next plane as P, and continue until you have the points for all polygons.

Hm... I hope you can understand this...
It is pretty simple if you once got it, but I even had a hard time to descripe this algo to our other coder

Step 1: Find the plane''s normal. Each plane in a Quake III *.map file is defined by three points (which are not necessarily verteces of the polyhedron). To find the equation of the plane, find that plane''s normal. Use the cross product to do this. So if they give you points A, B, and C, then the normal is the cross product of AB and BC. I''ll call the normal N.

To find the equation of a plane with normal N going through point P, first solve for K as follows:

N * P = K

Then, the equation of the plane is

(N.x * x) + (N.y * y) + (N.z * z) = K

Do this for each of the three planes. Now you have three equations and three variables. Solve. The simplest way is to use a matrix. This is basic linear algebra; if you need help with this google should tell you everything you need to know.

Also, there''s a good website which deals with exactly the problem you''re having. Go here.

Okies I'm having problems with the exact same thing which is why I dragged this age old topic back up. The article the last poster is reffering to is the exact same article the original poster got his equation picture from!!!! So the guy was just sent in circles, I'm having the same problem. When I use this formula I either end up with a list of normals or I end up with screwy coordinates that when checked against the planes are always outside one or other of the planes even on a cube where this should not be the case for any of the intersection points!!

Please check out my post in the DirectX forum for specifics of the code I used. My last post says I thought I'd figured out the reasoning behind it, but having worked on it some more, it wasn't the cause at all. I believe the planes have been correctly converted but somehow I'm messing up the equation. My latest code is as follows and produces the normals I speak of. If anyone can be of any assistance please please please help me out cos this is driving me nuts!!

My latest version of the intersection checking function is as follows if it helps:






Please note that code commented out is indeed commented out right now as my program stands cuz this is work in progress.

If anyone can offer any advice I'd be hugely grateful if that means anything!!

Cheers,

Steve AKA Mephs

*EDIT Ooops not so age old, I was looking at the posters time of joining =p *EDIT

[edited by - mephs on June 10, 2002 8:05:24 AM]