Plane intersection tests -Still very stuck =/
Author
Some of you may have seen a couple of my previous posts requesting assistance on aspects of a .map file parser. Well I finally have the parser all figured out and generating a working linked list structure containing all information ready to create my vertices for rendering as an ID3DXMesh object (w00t!!).
I have stumbled upon one final problem though. I need to be able to work out the coordinates of an intersection point between 3 planes. Does anyone know how this is achieved in Direct3D? I know functions exist to determine intersection of a ray with a plane, but D3D has no functions that return the coordinates of a point intersected by 3 planes. Is it simple enough to program my own function to do this, or is the maths very difficult to achieve with the functions D3D8 gives? I've looked up info on determining intersection points, but again I can only find information on finding the intersection of a ray with a plane.
If anyone could point me in the right direction I'd appreciate it, then finally I might be able to stop bugging you guys for answers on this and move onto another section of my engine!! That on its own must be worth helping me out for (hehe yeah right!! =p)
cheers,
Steve AKA Mephs
[edited by - mephs on June 10, 2002 3:10:23 AM]
Hello
Here are the maths for your intersection:
Each plane in 3d is represented by its cartesian equation: ax+by+cz+d=0, where (a,b,c) is a normal vector to the plane, and d the distance to the origin. So finding the intersection of three planes is just solving the system:
(1) a1.x + b1.y + c1.z + d1 = 0
(2) a2.x + b2.y + c2.z + d2 = 0
(3) a3.x + b3.y + c3.z + d3 = 0
So it''s very easy to compute:3 eqs, 3 unknows, enjoy !
To compute it, you define the matrix A such as A.x = b where x is the point you want to find, b = (-d1,-d2,-d3), and A is
[[a1,b1,c1]
[a2,b2,c2]
[a3,b3,c3]]
If A.x=b then x = A^(-1).b, where A^(-1) is the inverse matrix of A. To compute it, just type:
D3DXMATRIX A;
A = ...
D3DXMatrixInvert(&A, NULL, &A);
Then:
D3DXVECTOR3 x;
D3DXVECTOR3 b = ...
D3DXVec3TransformCoord(&x, &b, &A);
The normal vector is very easy to find (just take the normalized vector product of 2 non colinear vectors lying in the plane). The distance d is the shortest path from (0,0,0) to the plane; so it is the length of the vector going from (0,0,0) to the plane and being orthogonal to it. Hint: it has the same direction as the normal to the plane.
Hope this helps
Here are the maths for your intersection:
Each plane in 3d is represented by its cartesian equation: ax+by+cz+d=0, where (a,b,c) is a normal vector to the plane, and d the distance to the origin. So finding the intersection of three planes is just solving the system:
(1) a1.x + b1.y + c1.z + d1 = 0
(2) a2.x + b2.y + c2.z + d2 = 0
(3) a3.x + b3.y + c3.z + d3 = 0
So it''s very easy to compute:3 eqs, 3 unknows, enjoy !
To compute it, you define the matrix A such as A.x = b where x is the point you want to find, b = (-d1,-d2,-d3), and A is
[[a1,b1,c1]
[a2,b2,c2]
[a3,b3,c3]]
If A.x=b then x = A^(-1).b, where A^(-1) is the inverse matrix of A. To compute it, just type:
D3DXMATRIX A;
A = ...
D3DXMatrixInvert(&A, NULL, &A);
Then:
D3DXVECTOR3 x;
D3DXVECTOR3 b = ...
D3DXVec3TransformCoord(&x, &b, &A);
The normal vector is very easy to find (just take the normalized vector product of 2 non colinear vectors lying in the plane). The distance d is the shortest path from (0,0,0) to the plane; so it is the length of the vector going from (0,0,0) to the plane and being orthogonal to it. Hint: it has the same direction as the normal to the plane.
Hope this helps
Author
Wow, well thanks for the help =)!!
I admit I don''t understand some of the conclusions you''ve come to about how to calculate it, so I''ll read up a little more on matrices and what have you, I honestly had no idea a matrix would be involved in the solving of such an equation... guess my maths needs a refresher. I''m not even sure if I could turn what you''ve told me into any usable code for lack of understanding whats going on. But I''m never one to give up on anything, I don''t like the defeatist attitude so if I can''t do something I generally keep at it for as long as possible. Anyways thanks for the info, I''ll try and put it to some good use =)
Steve AKA Mephs
I admit I don''t understand some of the conclusions you''ve come to about how to calculate it, so I''ll read up a little more on matrices and what have you, I honestly had no idea a matrix would be involved in the solving of such an equation... guess my maths needs a refresher. I''m not even sure if I could turn what you''ve told me into any usable code for lack of understanding whats going on. But I''m never one to give up on anything, I don''t like the defeatist attitude so if I can''t do something I generally keep at it for as long as possible. Anyways thanks for the info, I''ll try and put it to some good use =)
Steve AKA Mephs
Author
Arf, well I've found a ton of resources on the subject, not one of them is helpful for d3dx though. I have the planes in normalised form so a plane may look like this:
a = 0.0f //
b = 1.0f // Plane Normal
c = 0.0f //
d = -128.0f // Distance from origin
So all my 3 planes involved in the intrsection test are in this format currently. I'm having great trouble working out how to apply stefanhas' formula (http://folk.uio.no/stefanha/) to find the intersection of 3 planes. The reason being, I think, is that the forumla he is using assumes the plane is in an un normalised format such as this:
a = 128.0f //
b = 196.0f // Un-normalised plane
c = -512.0f //
d = -128.0f //
What I'm having trouble with is applying the same formula to a normalised plane. His formula appears to convert it on the fly as necessary and I'm having problems altering the formula to act on a normalised plane instead. It should be possible because I don't think the un-normalised plane is ever needed in the formula except for to work out the normalised plane from.
As for the previous suggestion.... I tried that, but you cannot make a 3X3 D3DXMATRIX... D3DX matrices are designed to only be used as 4X4 matrices.
The above code shows my function. It may make no sense as it currently stands because I've been altering it left right and centre to try to produce correct results, to no avail. I do indeed get what seem to be coordinates from the function, but when I get around to checking if the point generated lies inside all the planes, it always lies outside at least one plane, which in a simple cube map that I'm loading, should never be the case.... with a simple cube every intersection should be on or inside the plane, so my coordinates are definitely being generated incorrectly.
Can anyone please help cos I'm almost out of ideas and I've been stuck on this now for the whole of this weekend =(
In addition to the above I also remembered it may help to know how the planes were created. What I did was take each coordinate from the plane in the .map file and converted it into a plane using the D3DXPlaneFromPoints command as follows
D3DXPlaneFromPoints(&Plane, &Point1, &Point2, &Point3);
[edited by - mephs on June 10, 2002 2:14:24 AM]
[edited by - mephs on June 10, 2002 2:28:23 AM]
a = 0.0f //
b = 1.0f // Plane Normal
c = 0.0f //
d = -128.0f // Distance from origin
So all my 3 planes involved in the intrsection test are in this format currently. I'm having great trouble working out how to apply stefanhas' formula (http://folk.uio.no/stefanha/) to find the intersection of 3 planes. The reason being, I think, is that the forumla he is using assumes the plane is in an un normalised format such as this:
a = 128.0f //
b = 196.0f // Un-normalised plane
c = -512.0f //
d = -128.0f //
What I'm having trouble with is applying the same formula to a normalised plane. His formula appears to convert it on the fly as necessary and I'm having problems altering the formula to act on a normalised plane instead. It should be possible because I don't think the un-normalised plane is ever needed in the formula except for to work out the normalised plane from.
As for the previous suggestion.... I tried that, but you cannot make a 3X3 D3DXMATRIX... D3DX matrices are designed to only be used as 4X4 matrices.
BOOL cMap::GetIntersection (int a, int b, int c, D3DXPLANE *Plane, D3DXPLANE *Plane2, D3DXPLANE *Plane3, float &X, float &Y, float &Z) { D3DXVECTOR3 Normal = (&Plane->a, &Plane->b, &Plane->c); D3DXVECTOR3 Normal2 = (&Plane2->a, &Plane2->b, &Plane2->c); D3DXVECTOR3 Normal3 = (&Plane3->a, &Plane3->b, &Plane3->c); D3DXVECTOR3 CrossProduct; D3DXVECTOR3 CrossProduct2; D3DXVECTOR3 CrossProduct3; D3DXVECTOR3 IntersectCoordinate; float Num1, Num2, Num3; D3DXVec3Cross( &CrossProduct , &Normal2 , &Normal3 ); D3DXVec3Cross( &CrossProduct2 , &Normal3 , &Normal ); D3DXVec3Cross( &CrossProduct3 , &Normal , &Normal2 ); float XPos; float YPos; float ZPos; float denom = D3DXVec3Dot (&Normal, &CrossProduct); if( denom == 0 ) { return FALSE; } Num1 = (Plane->d) ; Num2 = (Plane2->d) ; Num3 = (Plane3->d) ; IntersectCoordinate.x = Num1; IntersectCoordinate.y = Num2; IntersectCoordinate.z = Num3; X = IntersectCoordinate.x; Y = IntersectCoordinate.z; Z = IntersectCoordinate.y; //XPos = (D3DXPlaneDotCoord(Plane, &D3DXVECTOR3(X,Y,Z))); //YPos = (D3DXPlaneDotCoord(Plane2, &D3DXVECTOR3(X,Y,Z))); //ZPos = (D3DXPlaneDotCoord(Plane3, &D3DXVECTOR3(X,Y,Z))); //X = XPos; //Y = YPos; //Z = ZPos; //X *= -1; //Y *= -1; //Z *= -1.0f; return TRUE;} The above code shows my function. It may make no sense as it currently stands because I've been altering it left right and centre to try to produce correct results, to no avail. I do indeed get what seem to be coordinates from the function, but when I get around to checking if the point generated lies inside all the planes, it always lies outside at least one plane, which in a simple cube map that I'm loading, should never be the case.... with a simple cube every intersection should be on or inside the plane, so my coordinates are definitely being generated incorrectly.
Can anyone please help cos I'm almost out of ideas and I've been stuck on this now for the whole of this weekend =(
In addition to the above I also remembered it may help to know how the planes were created. What I did was take each coordinate from the plane in the .map file and converted it into a plane using the D3DXPlaneFromPoints command as follows
D3DXPlaneFromPoints(&Plane, &Point1, &Point2, &Point3);
[edited by - mephs on June 10, 2002 2:14:24 AM]
[edited by - mephs on June 10, 2002 2:28:23 AM]
Author
Hmm okay maybe I can put it simpler so someone might sppot what I''m doing wrong...
When I follow Stefans equation exactly, the output coordinates are normals, not coordinates
ie
(- Distance1*(CrossProduct) - Distance2 * (CrossProduct2) - Distance3 * (CrossProduct3))
------------------------------------------------------------
denom
= 0 , -1, 0
Thats the kind of output I get, but supposedly I should be getting coordinates... not normals!! If I mess about with the way I lay out the equation in my code, I can get it to generate what looks like coordinates, but as said previously they are not correct coordinates as they always fall outside at least one or two of the planes bounding the object. I realise that worldcraft switches Z and Y coordinates from the system I''m using but I have reflected that in my check on the point against the plane. Even if I don''t take that into account it still ends up that the point is outside one plane or another.
When I follow Stefans equation exactly, the output coordinates are normals, not coordinates
ie
(- Distance1*(CrossProduct) - Distance2 * (CrossProduct2) - Distance3 * (CrossProduct3))
------------------------------------------------------------
denom
= 0 , -1, 0
Thats the kind of output I get, but supposedly I should be getting coordinates... not normals!! If I mess about with the way I lay out the equation in my code, I can get it to generate what looks like coordinates, but as said previously they are not correct coordinates as they always fall outside at least one or two of the planes bounding the object. I realise that worldcraft switches Z and Y coordinates from the system I''m using but I have reflected that in my check on the point against the plane. Even if I don''t take that into account it still ends up that the point is outside one plane or another.
Author
aha!! I believe I MAY... have solved the problem. Upon checking the data stored in the planes, the distance of every plane from the origin after the first plane is incorrect. The first plane is entirely correct, all subsequent planes are fine if they are a positive distance away from the origin, but for some reason my parser is turning all planes after the first with a negative distance from the origin into planes with a positive distance from the origin. Thus my planes are probably set up in such a way that no matter where I place a vertex, it will always land on the wrong side of one of these incorrectly made planes.
I had kinda overlooked the parser as I believed it was functioning properly, but apparantly not quite yet... ahh well back to the drawing board
Damn don''t ya hate the days where you feel like you take one step forward and two steps back :/
I had kinda overlooked the parser as I believed it was functioning properly, but apparantly not quite yet... ahh well back to the drawing board
Damn don''t ya hate the days where you feel like you take one step forward and two steps back :/
Author
Arf... I just found out the parser is indeed working fine, the problem lies in the D3DXPlaneFromPoints command
a) ( -256 128 -192 ) ( -192 128 -192 ) ( -192 -128 -192 )
b) ( -256 -128 -512 ) ( -192 -128 -512 ) ( -192 128 -512 )
A is the first plane, now in the system I''m using I''d expect the plane produced to have distance -192 from the origin, which is correct.
B is the second plane, D3DXPlaneFromPoints turns this into a plane with distance +512 from the origin, now I''d expect a plane to be produced with distance -512 from the origin, because all points defining the plane contain -512 as one of the coordinate elements. Therfore I believe the command D3DXPlaneFromPoints is judging the distance from the origin not only based on its distance as specified by the coordinates, but also by the direction of its normal, thus if the normal faces in a positive direction, it flips the distance to be on the positive side of the axis rather than the negative... therefore I''m guessing I''m gonna hafta write my own routine to turn the set of points into a plane structure..... guess thats 4 steps back for my one step forward today =/
Does that reasoning sound logical or can anyone else see something I''m doing wrong?
Also sorry if this looks like I''m bumping my own topic up, I''m trying not to but I keep discovering new things that seem to be causing the problem... hopefully this discovery should sort everything out.. I hope
a) ( -256 128 -192 ) ( -192 128 -192 ) ( -192 -128 -192 )
b) ( -256 -128 -512 ) ( -192 -128 -512 ) ( -192 128 -512 )
A is the first plane, now in the system I''m using I''d expect the plane produced to have distance -192 from the origin, which is correct.
B is the second plane, D3DXPlaneFromPoints turns this into a plane with distance +512 from the origin, now I''d expect a plane to be produced with distance -512 from the origin, because all points defining the plane contain -512 as one of the coordinate elements. Therfore I believe the command D3DXPlaneFromPoints is judging the distance from the origin not only based on its distance as specified by the coordinates, but also by the direction of its normal, thus if the normal faces in a positive direction, it flips the distance to be on the positive side of the axis rather than the negative... therefore I''m guessing I''m gonna hafta write my own routine to turn the set of points into a plane structure..... guess thats 4 steps back for my one step forward today =/
Does that reasoning sound logical or can anyone else see something I''m doing wrong?
Also sorry if this looks like I''m bumping my own topic up, I''m trying not to but I keep discovering new things that seem to be causing the problem... hopefully this discovery should sort everything out.. I hope
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
