Archived

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

Wyrframe

A mathematics problem...

Recommended Posts

I'm having some real trouble with this, and could use some help... In this physics demo, I have a number of cubes, and a rope. The rope is attached to the bottom of one of these cubes, and hangs due to gravity. One of the other cubes is going to move so that one corner of it will touch the rope. Here is where the trouble begins... I already have knowledge and code to test if a point is on the "bad" side of a plane, and to test if a ray (two connected points) is passing through a plane. What I need is to determine two more things... 1. If I have two planes, how do I define, and how do I find, the ray of intersection between them? 2. If I have three planes, how do I determine the point at which they all intersect? I need #2 so that I can find the point at which to "bend" the rope... the first two planes would be two edges of the cube, and the third would be coplanar to the ray between the two ends of the rope, and not coplanar to the ray I would find in #1. Remember that I only track a plane based on it's center and it's normal... to define a cube, I use six planes, and claim that a point is inside the cube if the point is inside all six planes. I would like more than equations where possible, please... I have yet to be able to turn equations into (C++) code. [edited by - Wyrframe on July 29, 2002 10:13:55 PM]

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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 = N1*N2

where ''N1'' and ''N2'' 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 ''N1'', say, and a point on it ''c1'' that isn''t necessarily on the line. We know of two vectors, ''N1'', and ''l''. ''N1'' 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 = N1*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 ''c1'':

r = c1 + 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:

(c1 + mu * m).N2 = d = c2.N

Rearranging this equation gives:

mu = [(c2 - c1).N]/[m.N2]

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

a = c1 + 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

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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 v1 = (x1, y1, z1) and v2 = (x2, y2, z2) (or the column vectors that are the transposes of those), then the cross product of v1 and v2, v1*v2 is defined to be:
(y1z2 - z1y2, z1x2 - x1z2, x1y2 - y1x2)
which is perpendicular to both v1 and v2, and the magnitude of the vector is |v1|*|v2|*sin A, where A is the angle between v1 and v2. (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

Share this post


Link to post
Share on other sites
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:

|N1x N1y N1z| |px| = |d1|
|N2x N2y N2z| |py| = |d2|
|N3x N3y N3z| |pz| = |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:

|px| = |N1x N1y N1z|-1 |d1|
|py| = |N2x N2y N2z| |d2|
|pz| = |N3x N3y N3z| |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 px, py, and pz.

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]

Share this post


Link to post
Share on other sites