Sign in to follow this  

Devillers Guigue

This topic is 4355 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Implemented the Devillers Guigue triangle triangle intersection test today at work. All works fine, but now that im on my own time, i'd like to fully understand the algorithm. It relies on two different geometric interpretations of the determinant
             | Ax Ay Az 1 |
 [A,B,C,D] = | Bx By Bz 1 |
             | Cx Cy Cz 1 |
             | Dx Dy Dz 1 |
given 4 3-dimensional vectors A, B, C and D. 1. Let P be the plane on which A, B and C lie. Then the sign of [A,B,C,D] specifies on which side of P, D lies. If [A,B,C,D] = 0, then D lies on P. 2. [A,B,C,D] is positive if the vector CD lies in the same direction as a right handed screw around AB, and is negative if the direction is opposite. Zero indicates the vectors intersect. Given that 1 and 2 are true, the rest of their algorithm makes sense. But where do 1 and 2 come from? Devillers and Guigue state these as facts, but provide no proofs, so i'm guessing they are fairly well known. But ive never seen them before, and no obvious intuitive explanation jumps out at me. If anyone could point me in the direction of an explanation or proof, that would be excellent. Thanks.

Share this post


Link to post
Share on other sites
I haven't heard of the paper you're talking about, but I think I see where this is going...
Generally, given three of its points, a plane's equation can be expressed in form of a determinant. The original determinant is 4x4 but a 3x3 simplification is also widely used:

| x y z 1 | | x-x1 y-y1 z-z1 |
p1: | x1 y1 z1 1 | == 0 ... or p1: | x2-x1 y2-y1 z2-z1 | = 0
| x2 y2 z2 1 | | x3-x1 y3-y1 z3-z1 |
| x3 y3 z3 1 |

This usually get's down to sth like A*x+B*y+C*z+D==0 The plane divides the 3d space in two parts. One where all points yield positive result in the plane's equation and thus don't belong to the plane and one that yields all negative. The border set of those spaces is the same, and its the very plane.

In order to test any point with respect to the plane, all you need to do is replace {x,y,z} with its cartesian coordinates {x0, y0, z0} and test the result of the determinant, which is probably why the method you're talking, about starts with taking vectors among the points...

With respect to 1.
Its trivial to prove that the axis {A,B,C} represents the plane's normal vector. Therefore, the equation can also be interpreted as {A,B,C}.{x,y,z} == -D
Ignore "-D" and assume it's zero. This moves the plane at the origin, parallel to itsself. It merely has impact on the distance of the plane from the origin, it doesn't affect its orientation.

Consider a random point and its position vector {x0,y0,z0}. For this point to yield positive dot product with {A,B,C}, the two vectors must point to the same direction, and their angle should be in the range (-pi/2, pi/2) rad. If that's the case, then both the test-point and plane normal are on the same side. (positive or negative semi-space)
If the result is negative, however, the point must lie on the other side of the 3d space, therefore the point is in the part of the 3d space that doesn't 'contain' the plane's normal...
This can also be interpreted as "signed distance" from the plane to the point.
I hope you see what I mean... This way you can test whether any point lies on the plane (equation==0) and if not, which side of the 3d space -with respect to the plane- it lies in.

With respect to 2.
This is a rule of thumb when it comes to determining the relative position of a point with respect to the plane. This has to do with a 3d system's handedness. It simply gets down to agreeing to which side the cross product of 2 vectors points at.
The cross product of two vectors is a vector perpendicular to the plane of the first two.
E.g. the cross product {1,0,0}x{0,1,0} will always be {0,0,1} no matter the 3d system. It has to do with whether you interpret {0,0,1} as 'closer' or 'farther'. (Some 3d APIs use this to determine visible geometry)

Although, changing the order of the points, will always imply the same plane, it's important to understand that their order in the determinant has immediate impact on determining its 'visible' side, thus determing the positive and negative semi-space in which it divides the 3d space.

E.g. consider the plane implied by the points {0,0,1}, {1,0,1}, {0,1,1}. It's equation would be: z == 1 or z - 1 == 0. It's normal is {0,0,1}
However, swapping two points, the plane of {0,0,1}, {0,1,1}, {1,0,1} has equation: -z+1 == 0, thus its normal is {0,0,-1}

An easier way to remember this:
Pass the vertices in the determinant in the order v0 (the test point),v1,v2,v3.
Align your right thumb finger with the vector v1v2 and your right index finger with the vector v1v3. If you stretch your middle finger perpendicular to the other two, it will point to the direction of the normal of the plane they define if the system is right handed. If the system is left handed, you should do the procedure with your left hand to get the right normal vector.

Share this post


Link to post
Share on other sites
Just a small correction to someusername's answer.

{A,B,C} can't be a normal since A, B and C are vectors.

Given a triangle defined by points (A,B,C), we can compute the triangle's normal using:

N = (A-B) x (C-B)

The aforementioned plane can be defined using this normal and the point B.
A signed distance D of any point P from that plane is given by:

Dot( N, (P-B) ) = D

or if we write it as a determinant of a matrix:

| P-B |
| A-B | = D
| C-B |

The rest is the same.

PS. Another way to understand this is to treat the determinant as a volume of a 3-simplex, namely a tetrahedron.

Share this post


Link to post
Share on other sites
I think you're misunderstanding my post here, ury.

I, myself, define A,B,C as the respective coefficient of x,y,z in the plane's equations: A*x+B*y+C*z+D==0.
I never said they were vectors, not did I imply it. They are obviously scalar quantities...
E.g. solving the symbolic determinant, would yield
A = -y2z1 + y3z1 + y1z2 - y3z2 - y1z3 + y2z3
This is a scalar quantity, not a vector.

A, B and C were not supposed to be the vector positions of the vertices that form the plane.

You are right, however, if you define them as such in the first place

Share this post


Link to post
Share on other sites
Thanks Someusername and Ury!

Your right, the determinant [A,B,C,D] is equivalent to the signed distance from the plane defined by A, B and C (ccw winding order) to the point D.

Heres the proof for anyone else who is interested.

| Ax Ay Az 1 |
[A,B,C,D] = | Bx By Bz 1 |
| Cx Cy Cz 1 |
| Dx Dy Dz 1 |

| Dx Dy Dz 1 |
= - | Ax Ay Az 1 | ( Three row swap operations,
| Bx By Bz 1 | -1^3 = -1 )
| Cx Cy Cz 1 |

| Ay Az 1 | | Ax Az 1 | | Ax Ay 1 | | Ax Ay Az |
= -Dx | By Bz 1 | + Dy | Bx Bz 1 | - Dz | Bx By 1 | + | Bx By Bz |
| Cx Cy 1 | | Cx Cz 1 | | Cx Cy 1 | | Cx Cy Cz |

= p.Dx + q.Dy + r.Dz + s

Where,
| Ay Az 1 |
p = - | By Bz 1 | = - AyBz + AzCz + AzBy - AzCy + ByCz - BzCy
| Cy Cz 1 |

| Ax Az 1 |
q = + | Bx Bz 1 | = + AxBz - AxCz - AzBx + AzCx - BxCz + BzCx
| Cx Cz 1 |

| Ax Ay 1 |
r = - | Bx By 1 | = - AxBy + AxCy + AyBx - AyCx - BxCy + ByCx
| Cx Cy 1 |

| Ax Ay Az |
s = + | Bx By Bz | = + AxByCz - AxBzCy - AyBxCz + AyBzCx + AzBxCy - AzByCx
| Cx Cy Cz |

Now we calculate the plane defined by A,B and C:
p'x + q'y + r'z + s' = 0
and show that it is equivalent to [A,B,C,D].
That is RTP p'=p, q'=q, r'=r and s'=s.

(p',q',r') is the plane's normal, so

(p',q',r') = (B-A)x(C-A)
= ( (By-Ay)(Cz-Az) - (Bz-Az)(Cy-Ay),
(Bx-Ax)(Cz-Az) - (Bz-Az)(Cx-Ax),
(Bx-Ax)(Cy-Ay) - (By-Ay)(Cx-Ax) )
= ( ByCz - AzBy - AyCz + AyAz - BzCy + AyBz + AzCy - AyAz,
BxCZ - AzBx - AxCz + AxAz - BzCx + AxBz + AzCx - AxAz,
BxCy - AyBx - AxCy + AxAy - ByCx + AxBy + AyCx - AxAy )
= ( p, q, r )

Since A lines on the plane,

pAx + qAy + rAz + s' = 0

and,
[A,B,C,A] = 0
pAx + qAy + rAz + s = 0

So,
s' = s

qed

Never seen the plane equation expressed in matrix determinant form before, but it is equivalent.

And one slight correction to my OP, when [A,B,C,D]=0, AB and CD are coplanar, they do not necissarily intersect (they could parallel).

Share this post


Link to post
Share on other sites
Quote:
Original post by Luke Hutchinson
1. Let P be the plane on which A, B and C lie. Then the sign of [A,B,C,D] specifies on which side of P, D lies. If [A,B,C,D] = 0, then D lies on P.
An easier way of looking at this is through the scalar triple product. The scalar triple product [A B C] = Dot(A, Cross(B, C)) returns the (signed) volume of the parallelepiped determined by the three vectors A, B, and C.

The scalar triple product can the expressed as the determinant:

| Ax Ay Az |
[A B C] = | Bx By Bz |
| Cx Cy Cz |

The determinant that you have is equivalent to:

| Ax Ay Az 1 | | Ax-Dx Ay-Dy Az-Dz |
[A,B,C,D] = | Bx By Bz 1 | = | Bx-Dx By-Dy Bz-Dz | = [A-D B-D C-D]
| Cx Cy Cz 1 | | Cx-Dx Cy-Dy Cz-Dz |
| Dx Dy Dz 1 |

Thus, it is computing the signed volume determined by the three vectors A-D, B-D, and C-D. The sign of the result depends on which side of the plane spanned by B-D and C-D the vector A-D lies. If A-D lies in the plane, the scalar triple product is zero.

Side note: Determinants are neat because they can allow a reformulation from e.g. 2D to 3D to 4D, but I often find that expressing something in terms of the scalar triple product greatly helps the geometric understanding.

Share this post


Link to post
Share on other sites

This topic is 4355 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this