Archived

This topic is now archived and is closed to further replies.

Damage_Incorporated

intersect 3 planes

Recommended Posts

well been working on a small program that converts a .map file from q3radiant to raw polygon data, the problem is that the map files is madke of brushes with 4 or more planes. so i have to intersect 3 planes to get one point etc. now the algorithm simply takes two planes and then the cross product of their normal then use the a formula to intersect a line with a plane, the formula is like this: c = -plane_dist_from_origin / dot(plane_normal, line_direction) where c is simply a scalar that i multiply the line_direction with to get the point, problem is that as for now all the planes are orthogonal and thus the dot product is 0, now should i make a special case for orthogonal planes or just abandon this formula and start all over? my linear math isnt what its supposed to be so this formula is probably not even correct - Damage Inc.

Share this post


Link to post
Share on other sites
You absolutely must use orthogonal planes to find where they intersect at a point, otherwise they do not necessarily intersect at a point and are useless.

I think this equation works:

(P1.Normal * P1.Dist) + (P2.Normal * P2.Dist) + (P3.Normal * P3.Dist)

I drew up a little example on my whiteboard, and I *think* it works, but I haven't tested it in a program of any kind.

[edited by - Shadow12345 on October 5, 2003 6:27:54 PM]

Share this post


Link to post
Share on other sites
well no, three planes make a point.

Two planes make a ray, add another one, and you get a point.


I'll have a go

the line between two intersecting planes is in the form P + D.t

the direction of the line D = (N1 x N0)

and P is on both planes (N1, d1) and (N0, d0)

therefore, P verifies

(eq1) P * N0 = d0
(eq2) P * N1 = d1

(eq1) - (eq2)
P * (N1 - N0) = (d1 - d0)

multiply both sides by (N1 - N0)

P * ((N1 - N0) * (N1 - N0)) = (d1 - d0) * (N1 - N0)

therefore

P = ((d1 - d0) / (N1 - N0)^2) * (N1 - N0)

so a point on the line between two plane verifies

O = ((d1 - d0) / (N1 - N0)^2) * (N1 - N0)
D = (N1 x N0)

P = O + D * t

then you find the intersection with the third plane and the line

P = O + D.t
P.N2 = d2

t = (d2 - O.N2) / (D.N2)

so there you go

O = ((d1 - d0) / (N1 - N0)^2) * (N1 - N0)
D = (N1 x N0)
t = (d2 - O.N2) / (D.N2)

P = O + D * t

[edited by - oliii on October 5, 2003 7:22:31 PM]

Share this post


Link to post
Share on other sites
hmm, one thing i dont really understand, (N1-N0)^2 that produces a scalar right? d0, d1 etc are distances from the origin i assume, . is dot and x is cross but that eludkes me, perhaps i should read it again tomorrow im supposed to go to a lecture in 2h and sleep is usually a good thing ;P

- Damage Inc.

Share this post


Link to post
Share on other sites
Not really helping on the question but I couldn´t resist the temptation to correct oliii (take it as a token of appreciation ):


>>>> You absolutely must use orthogonal planes to find where they intersect at
>>>> a point, otherwise they do not necessarily intersect at a point and are useless.

>> well no, three planes make a point.
>> Two planes make a ray, add another one, and you get a point.

neither statement is completely correct. While it is not nessecary to take orthogonal planes you cannot assume they have a common point in general. The correct statement would be "you must take three planes with non-lineary-dependent normals".

In an implicit form a plane can be written a P={x: x*n = a} where n is the normal and a the (oriented) distance from the origin. If you want the common point p of the planes P1, P2 and P3 this is P1 & P2 & P3 so it must satisfy the conditions
p*n1 = a1
p*n2 = a2
p*n3 = a3

or as a matrix equation (A = (n1,n2,n3), b=(a1,a2,a3)):
Ap = b

This equation has exaclty one solution if Det(A)<>0 which is true only if n1,n2 and n3 are lineary independent.

Share this post


Link to post
Share on other sites
Yes, I think they knew what I meant. Your planes must be orthogonal in order to be able to combine them in such a way to represent all possible points (they form a basis).

Does anyone know if my method is correct? I am almost certain it is. If that is the case, use it, it''s the easiest that''s been posted so far

Share this post


Link to post
Share on other sites
shadow12345:
Well, I still don´t understand what you mean. You know that a basis doesn´t have to be orthogonal?
Anyways: Your method seems correct if the planes are orthogonal and seems to fail if not. I think you have to use the reciproce basis (and this would be the equivalent to finding A^-1).

Damage:
What you were trying to do in the first place seems surprisingly good. Only problem you´d get (from what I can see) is that if your line doesn´t go through the origin (which it doesn´t in general) your equation fails. You could solve this by shifting your coordinte system accordingly but take into account that this also alters the equation (distance from origin) for your 3rd plane.

Share this post


Link to post
Share on other sites