Archived

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

Tjoppen

Hmm...Define a cube by planes...

Recommended Posts

I seem to have a slight problem with my 3 plane intersection formula(i suspect...i don´t really know...) But i tried to define three planes like this: --((x,y,z),d) <- plane-- ((1,0,0),1) ((0,1,0),1) ((0,0,1),1) but that did not result in an intersection...and logically it would intersect @ (1,1,1) as long as i understand, to define a box from (-1,-1,-1) - (1,1,1) o would do: ((1,0,0),1) ((0,1,0),1) ((0,0,1),1) ((-1,0,0),1) ((0,-1,0),1) ((0,0,-1),1) or? am i missing something??? bacause i seem to have understood that the the closest point on a plane to origin is: p = d * n in other words: p is the closest point to (0,0,0) from the plane (n, d) or? plz, enlighten me

Share this post


Link to post
Share on other sites
you are right about the p = d * n.

but if you only make boxes, why not find the planes from the corners of the box?

also, wouldn''t you have to do 8 intersections?

((+/- 1, +/- 1, +/- 1), 1)
...
...

Share this post


Link to post
Share on other sites
i will try to visualize this...

      
****
* **
* A* *
***p B*
* C* *
* **
****


then p should be where A, B and C intersect...

i guess intersection between three planes is like taking three pieces of paper and put them together in some matter...

intersection between two planes makes a line...which one can intersect with a third plane...

THAT is how i visualized it...sort of...

here´s me intersection code:

  
bool GetIntersection( PLANE a, PLANE b, PLANE c, VECTOR &p )
{
float denom = DotProduct( a.n, CrossProduct( b.n, c.n ) );

if( denom == 0 ) //two or more planes are parallel

return false;

p = ( CrossProduct( b.n, c.n ) * -a.d )
- ( CrossProduct( c.n, a.n ) * b.d )
- ( CrossProduct( a.n, b.n ) * -c.d );
//calc intersect...THIS is where I believe the error is...

return true; //success(?)

}


and of course, my points->plane code:

  
PLANE CalcPlane( VECTOR a, VECTOR b, VECTOR c )
{
PLANE tmp;
tmp.n = Normal( a - b, c - b );
tmp.d = -DotProduct( tmp.n, a );
return tmp;
}

any of those wrong?

EDIT: oops...

Edited by - Tjoppen on January 13, 2002 9:30:38 AM

Share this post


Link to post
Share on other sites
BTW, when I shoot these three points through the PointsToPlane:

( 128 64 128 )
( 64 64 128 )
( 128 128 128 )

i get:

( ( 0 0 1 ) -128 )

and i don´t find this logical... wouldn´t d = 128 and NOT -128, since all of the coords are positive?

p = d * n

right?

( 0 0 1 ) * -128 = ( 0 0 -128 )

which don´t seem right to me...

Share this post


Link to post
Share on other sites
That seems a well thought out way of doing it. I''m confused by the signs though. If you have the plane x=1 then the normal is (1,0,0) and D=-(1,0,0).(1,0,0)=-1. So x=1, y=1 and z=1 are a=((1,0,0),-1), b=((0,1,0),-1) and c=((0,0,1),-1). Next you take the cross products which are bc=b x c=(1,0,0), ca=c x a=(0,1,0) and ab=a x b=(0,0,1) and you multiply by the D for the other plane. (bc*1)-(ca*-1)-(ab*1) or (1,0,0)-(0,-1,0)-(0,0,1)=(1,1,-1). Really you need ((bc*--1)+(ca*--1)+(ab*--1)) or ((1,0,0)+(0,1,0)+(0,0,1)). I think it would be less confusing to just not change the sign on D in the first place, i.e. D=P.N. The dot product of the position vector for every point in a plane with the normal for the plane is a constant. When you see a*x+b*y+c*z+d=0 it is really a*x+b*y+c*z=e and d=-e. e is the directed distance of the plane from the origin in multiples of the magnitude of (a,b,c). d is the reversed directed distance of the plane from the origin. Which direction is positive and which is negative is an arbitrary choice and generally people call it d whichever choice they make. After you make that choice though you have to use it consistantly. It can''t be positive in a given direction at one point in the calculation and negative in another.

Share this post


Link to post
Share on other sites
OMFG!

p = ( CrossProduct( b.n, c.n ) * -a.d ) - ( CrossProduct( c.n, a.n ) * b.d ) - ( CrossProduct( a.n, b.n ) * -c.d );

I think that may be my problem

Can´t check right now tho...burning---

EDIT: Oh, oh....

Perhaps I should divide that whole vector with denom....Perhaps

It works now...All i have left is to sort all verts in the resulting polys...

Edited by - Tjoppen on January 13, 2002 3:16:51 PM

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Well you should consider your pb is simply a multiplication of a vector by the inverse of a 3x3 matrix. In fact you have been reinventing the wheel ! LOL

Let your 3 planes be A, B and C and I their intersection. I belongs to every plane thus :

A.n*I = -A.d
B.n*I = -B.d
C.n*I = -C.d

( means that the projected component of I following A.n is the opposite distance of the plane A to the origin )

Now if you still cant see the matrix involved here :

I.x I.y I.z
-------------------------
| A.n.x | A.n.y | A.n.z | | A.d
| B.n.x | B.n.y | B.n.z | = | B.d = D
| C.n.x | C.n.y | C.n.z | | C.d
-------------------------

M*I = D => I = (1/M)*D if Det(M)!=0 ( intersection could be a line, empty, or even a plane if A=B=C )

Thus you probably have a math lib. Use it U dont need much more code.

Then inverting a 3x3 matrix M seen as 3 row vectors { a=A.n, b=B.n, c=C.n } is simple (note the permutations in the formula ) :

{ b^c, c^a, a^b }/Det(M) and Det(M)=(a^b)*c

Thus :
I.x = (b^c) * D / Det(M)
I.y = (c^a) * D / Det(M)
I.z = (a^b) * D / Det(M)

PS: The inversion formula would have worked for column vectors but it s less convenient as A.n, B.n, C.n are rows. That''s not weird at all because : transpose(1/M) = 1/transpose(M)

OK ???

Charles B

Share this post


Link to post
Share on other sites
I take the following true:

* = the dotproduct, or .
^ = the crossproduct, or x

I was a little confused that

A.n*I = -A.d

and I tought that * was multiply...

But, however...Is this true??? Have I missed something???

D = A.d + B.d + C.d

But...

quote:

{ b^c, c^a, a^b }/Det(M) and Det(M)=(a^b)*c

Thus :
I.x = (b^c) * D / Det(M)
I.y = (c^a) * D / Det(M)
I.z = (a^b) * D / Det(M)



{ b^c, c^a, a^b }/Det(M)

There is no D in this formula, so how can the other one have it??? Wouldn´t we just get:
I.x = (b^c) / Det(M)
I.y = (c^a) / Det(M)
I.z = (a^b) / Det(M)

Or

I = { b^c, c^a, a^b } / (a^b)*c

And if so, there´s just one more thing that worries me:

b^c = cross between two PLANES...? huh?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Sorry I supposed you knew standard Math notations. But if U have pbs to solve this issue it''s obvious that you dont To me beeing fluent in maths notations is really important to be quicker and see the inner logics and solve small pbs like that. U should read some books about notations in linear algebra. Hmm do you know operator overloading in C++ ? Some 3D libs use it but it can be confusing in code. I dont like it too much.

x=DotProduct(A,B); <=> x=A*B
A=CrossProduct(B,C); <=> A=B^C

D is a 3D vector (shown as a column matrix) with components :
D{ A.d, B.d, C.d }
It is not a scalar ( not real number, not a float if u prefer ) !
Else dont be confused just because I kept A.d, B.d, C.d. I could haved renamed these components D.x, D.y, D.z but they are not 3D "world" space coordinates. It would have been confusing !

a,b,c are the 3 normals. I have defined them ! They just rename A.n, B.n, C.n, the plane normals, because I am a lazzy writter.

Well the mysterious part now ! LOL

I say that I consider the matrices as 3 rows of 3D vectors. It''s a quick way to explain that M is :

a.x a.y a.z
b.x b.y b.z
c.x c.y c.z

Considering the matrix as columns (which is the common way) would have been stupid here. I would have required new vectors {a.x,b.x,c.x}, ...,{a.z,b.z,c.z}. Instead the rows are well known : a,b,c, the plane normals.

Then let''s call N the inverse of M :

N = 1/M

I give the following formula for matrix inversion :

N = { b^c, c^a, a^b }/Det(M)

OOOPS Shame on me ! ( Supposed to be a brute at maths ! ) My memory failed at this point ! I forgot to say that there is a transposition here ! It means that N is now a matrix of column vectors !!!

Det(M) is a scalar. Multiplying a matrix by a scalar is totally equivalent to uniform scaling in fact. If you prefer N is :

| (b^c).x/Det(M) (c^a).y/Det(M) (a^b).z/Det(M) |
| (b^c).x/Det(M) (c^a).y/Det(M) (a^b).z/Det(M) |
| (b^c).x/Det(M) (c^a).y/Det(M) (a^b).z/Det(M) |

Hmm I am not too lazy this time ! LOL

I said that our starting problem was :

(1) D = M*I

which is a much more compact way of saying :

A.d = A.n*I = a*I = a.x*I.x + a.y*I.y + a.z*I.z
B.d = B.n*I = b*I = b.x*I.x + ...
C.d = C.n*I = c*I = c.x*I.x + ...

( BTW I let a mistake ! Forget the minus signs of the 1st 3 lines and read what LilBudyWizer says, U have to choose which A.d you consider. Personnally I prefer A.d to be the distance origin to plane A in the direction of A.n : O----A.d----->(A)--A.n---> here A.d > 0 )

Then solving your problem, I mean finding I is simply inverting (1) That''s all :

(1) => I = (1/M)*D = N*D, if M can be inversed (Det(M)!=0)

Aren''t maths simplier with powerful notations ?
... As long as u remember the inversion formula by heart or you find the function in your maths packages.

I = (1/Det(M))*( (b^c)*A.d + (c^a)*B.d + (a^b)*C.d )

Which more detailed is :

I.x = ((b^c).x/Det(M))*A.d + ((c^a).y/Det(M))*B.d + ...
I.y = ((b^c).y/Det(M))*A.d
I.z = ((b^c).z/Det(M))*A.d

Last thing if your 3 planes are orthogonal ( your cube example ) then Det(M) = 1. This leads to your result.

But I think the more general result for any 3 planes is more interesting to create a nice function. Call it something like :

int Intersect3Planes( Plane &A, Plane &B, Plane &C, Point &I );

Just add a special test if( fabs(Det-1.0f) < SMALL ) to detect the cube case and avoid the division : 1/Det(M). Computing Det requires only one more dot product ( 3 muls 2 adds ) because (a^b) is required elsewhere.

If Det=0 then you should return that there is no defined point intersection. If you are perfectionnist you could return the degree of the intersection: 3 for a plane (A=B=C), 2 for a line, 1 for a point, 0 for nothing.

Charles B

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Another thing your plane equations dont need to be normalized if u divide by Det(M).

For instance :

{ {2,0,0}, 2 } : 2*x=2

is the same plane as

{ {1,0,0}, 1 } : x=1

but your function would fail here and mine would still work

Charles B

Share this post


Link to post
Share on other sites