A mathematics problem...

Okay... this might help... I found this on another site...

INTERSECTION OF 3 PLANES

N1 . p = d1
N2 . p = d2
N3 . p = d3

"." signifies dot product and "*" is cross product. The intersection point P is given by:

d1 ( N2 * N3 ) + d2 ( N3 * N1 ) + d3 ( N1 * N2 )
P = -------------------------------------------------------------------------
N1 . ( N2 * N3 )


Can anyone tell me what small p (not capital P) represents, and what d1-3 represent? I''ve got the savvy to figure out that N1-3 are the normals...

what site?

http://astronomy.swin.edu.au/~pbourke/geometry/3planes/

small p is just a point on the plane. the first 3 equations show that you a searching for a point p that lies on all 3 planes.

mathematically you describe a plane by the equation

p . N - d = 0

where p is any point on that plane, N is the normal vector and d is the distance of the plane to the origin.


hope this helps a little

eloso

Okay... but I can''t figure out where d1..3 figure into this... D is the scalar distance between the origin and the point on the plane nearest to the origin, right?

I presume I have to calculate that distance...

I''ve found this method to do it, but the math is way over my head... any chance someone could help me decode the process used on this page?

http://astronomy.swin.edu.au/~pbourke/geometry/pointplane/

Many thanks, in advance...

I hope this makes sense to you .

Firstly, the intersection of two planes. A plane, as eloso and you have said, can be described by its normal, ''N'', and a "distance from the origin", ''d'':

r.N = d

Here, ''r'' is any point (x,y,z) on the plane, that is to say, that if any point ''r'' satisfies this equation, then it is on the plane. There are other ways of describing planes, but I''ll just use this one.

The "distance" ''d'' is sort of a distance, but I prefer to not think of it like that. It''s certainly true (I think) that if ''N'' is normalized (has length 1), then ''d'' will be the displacement (could be negative) of the plane from the origin.

Given any point on the plane (such as the centres you use), it is very easy to determine ''d''. Since the centre points lie on the plane, they must satisfy the plane equation. Thus:

c.N = d

where ''c'' is the position of the plane centre (slightly arbitrary to use the term centre for something infinite ). All I''m doing is replacing ''r'' in the first equation with ''c''. So instead of saying that a plane equation is

r.N = d

for some ''d'', you could think about it as: any point ''r'' such that ''r.N'' is equal to ''c.N'' for *any* point ''c'' on the plane implies that ''r'' is on the plane. In other words:

r.N = c.N

I''m sure I''ve laboured this point too much, but hopefully it''ll mean everything else I say makes a bit more sense.

To get back to the point... As you say, the intersection of two planes is a line. A line can be described by a point on it ''a'', and a direction ''l'':

r = a + lambda * l

As above, ''r'' is any point on the line; ''lambda'' is a scalar value that specifies how far from the point ''a'' that ''r'' is.

To find ''l'' for the intersecting planes, I use the cross product (I''ll refer to it with a *), which I assume you are familiar with. It is given by:

l = N₁*N₂

where ''N₁'' and ''N₂'' are the normals of planes 1 and 2. This gives ''l'', as the line should be perpendicular to both the normals. Assuming these normals are different, the cross product gives the required vector. If they aren''t, then the planes are parallel. This means that either they are the same plane, or they won''t intersect.

Next we need to find ''a''. This is any point on the line, and will be a point on both planes. There might be a simpler way to find this than the following one, but it should work fine anyway.

Consider one of the planes, that has normal ''N₁'', say, and a point on it ''c₁'' that isn''t necessarily on the line. We know of two vectors, ''N₁'', and ''l''. ''N₁'' is perpendicular to the plane, and ''l'' is parallel to it. By taking the cross product of these two vectors, we can obtain a third vector ''m'':

m = N₁*l

This vector is also parallel to the plane, and crucially, a line through a point on the plane in the direction of ''m'' will intersect the line we are looking for (the intersection of the two planes). So now take the line in the direction of ''m'' through ''c₁'':

r = c₁ + mu * m

where ''mu'' is equivalent to ''lambda'' in the first line I described - just a scalar, but better to make it different to ''lambda''.

For some given ''mu'', ''r'' will be a point on the line we are aiming to get: ''a''. Also, ''r'' will be on both planes, specifically plane 2. Therefore it must satisfy plane 2''s equation:

(c₁ + mu * m).N₂ = d = c₂.N

Rearranging this equation gives:

mu = [(c₂ - c₁).N]/[m.N₂]

So now we know how far along the ''r = c₁ + mu * m'' line the point ''a'' is. Then it is easy to find:

a = c₁ + mu * m

for the ''mu'' just calculated.

So that is all that is required for the two plane case - we''ve found a point on the intersection line ''a'', and the direction of the line ''l''.

It''s not as complicated as I make it out to be, and I hope you can work with this . I''ll explain the three plane case if you like, but it''s getting late, so probably tomorrow.

Miles

Miles, that is reasonably helpful...

In fact, I have no clue why I use "centers"... center of the side of a cube was my original thought, but I see now it was completely unneeded...

Okay. I now track planes by the Ax + Bx + Cx + D = 0 equation, also known as p•N = d... Oh, hell, that''s what I was using anyways, for collision detection... *smacks own forehead*

Okay, for terminology sake, I''d like to propose a thread-wide standard? Use • (copy&paste it) or . (period) for Dot Product, and * (star) for Cross Product?

Oh, on a side note, how do I calculate the cross product of two 3-dimensional vectors? Can''t find my physics book anywhere...

Miles, please do try to explain the 3-plane point of intersection, when you get the time?

quote:

---

Original post by Wyrframe
Miles, that is reasonably helpful...

---

Glad to be of help.

quote:

---

I have no clue why I use "centers"... center of the side of a cube was my original thought, but I see now it was completely unneeded...

---

Well, it isn''t all that bad really . If the centres you refer to are centres of the sides of the boxes, then that is perfectly justified. I was criticizing myself as much as anything.

quote:

---

Okay. I now track planes by the Ax + Bx + Cx + D = 0 equation, also known as p•N = d...

---

I assume you mean Ax + By + Cz + D = 0 (x, y and z, rather than x,x&x), which like you say is equivalent (by the definition of dot product) to p•N = d if p = (x,y,z), N = (A,B,C), and d = -D. That was probably clear to you (as you indicated), but I thought I''d make sure.

quote:

---

Okay, for terminology sake, I''d like to propose a thread-wide standard? Use • (copy&paste it) or . (period) for Dot Product, and * (star) for Cross Product?

---

Sounds good to me. Just to add that I suppose that * needs to be used for scalar multiplication of vectors, like 2*N, but that should be obvious from the context.

quote:

---

Oh, on a side note, how do I calculate the cross product of two 3-dimensional vectors? Can''t find my physics book anywhere...

---

If the two vectors are v₁ = (x₁, y₁, z₁) and v₂ = (x₂, y₂, z₂) (or the column vectors that are the transposes of those), then the cross product of v₁ and v₂, v₁*v₂ is defined to be:
(y₁z₂ - z₁y₂, z₁x₂ - x₁z₂, x₁y₂ - y₁x₂)
which is perpendicular to both v₁ and v₂, and the magnitude of the vector is |v₁|*|v₂|*sin A, where A is the angle between v₁ and v₂. (IIRC )

quote:

---

Miles, please do try to explain the 3-plane point of intersection, when you get the time?

---

I should be able to do it fairly soon. I''d just like to order myself an adsl connection first (whoopeee!!)

Miles

Hello,

Ok, here's my interpretation of the 3 plane intersection. I do think that the equation you came up with should work fine, and is probably the best to use. However this is how I would have done it otherwise. Take your three equations:

N1 . p = d1
N2 . p = d2
N3 . p = d3

and represent them as matrices:

|N1_x N1_y N1_z| |p_x| = |d1|
|N2_x N2_y N2_z| |p_y| = |d2|
|N3_x N3_y N3_z| |p_z| = |d3|

In case that isn't clear, it's a 3x3 matrix (of the normal components) multiplied by a 3x1 matrix/vector (of the point of intersection) to give a 3x1 matrix/vector (of the d#s)

The three plane equations ensure that the point will lie on each and every plane, and the matrix version is just a restatement of this.

Now, what we need is p. Using simple matrix algebra, p can be determined by pre-multiplying both sides by the inverted normals matrix:

|p_x| = |N1_x N1_y N1_z|^-1 |d1|
|p_y| = |N2_x N2_y N2_z| |d2|
|p_z| = |N3_x N3_y N3_z| |d3|

So, what you need to do is to set up a matrix with the normal components, invert it, and then multiply it by the d#s matrix. The result will be a vector whose components are p_x, p_y, and p_z.

Naturally, a matrix can only be inverted if its determinant is non-zero. This turns out to be the case when (iirc)

N1.(N2*N3) != 0

which is the same condition for the equation you posted holding (you can't divide by 0), and means that the planes meet at a point, rather than a line or lines, if at all.

Like I said, I think the equation you gave is probably the best to go for. I don't know it works for sure, but it looks fine. It's probably faster than the matrix method too. Just don't forget to test that N1.(N2*N3) != 0 .

Miles

[EDIT: I tried to make the matrices look a little better. I can't get things to line up properly on the inverted matrix. Just to say that it's the whole 3x3 matrix that is being inverted, not just the first row, or anything.]

[edited by - Miles Clapham on August 1, 2002 9:13:29 PM]

Thank you much, all!