Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've hit a stumbling block in my project to draw the Utah teapot. I want to generate a binary space partition tree of a set of 3D triangles.

The decision step in the recursive tree-construction algorithm is determining whether one triangle is in front of or behind the plane defined by another triangle.

So, given two triangles, $T_0 = (P_1, P_2, P_3), T_1 = (P_4, P_5, P_6), P_1 = (x_1, y_1, z_1), P_2 = (x_2, y_2, z_2)$, ..., we take a normal vector of $T_0$, $N_0 = (P_2 - P_1) \times (P_3 - P_1)$.

And then I get confused. Help?

I think I need to describe the coordinates of $T_1$ in terms of a Plane [ a b c d ] + $N_0$. The magnitude of the resulting vector is the distance. Positive or negative determines whether it's in front of or behind the plane. But I'm fuzzy on step 2.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Using determinants

You can use the sign of the determinant

$$\begin{vmatrix} x_1 & x_2 & x_3 & x_4 \\ y_1 & y_2 & y_3 & y_4 \\ z_1 & z_2 & z_3 & z_4 \\ 1 & 1 & 1 & 1 \end{vmatrix}$$

to decide on which side of the plane spanned by $P_1, P_2, P_3$ the last point $P_4$ lies. So take the three corners of one triangle, and perhaps the center of the other triangle, and compute the sign of that determinant to make your decisions.

You could even move the division from the computation of the center into the determinant like this:

$$\begin{vmatrix} x_1 & x_2 & x_3 & x_4 + x_5 + x_6 \\ y_1 & y_2 & y_3 & y_4 + y_5 + y_6 \\ z_1 & z_2 & z_3 & z_4 + z_5 + z_6 \\ 1 & 1 & 1 & 3 \end{vmatrix}$$

The last column is the center of the triangle $P_4,P_5,P_6$, scaled by 3. This will scale the value of the determinant by 3 as well, but won't affect its sign.

Normal form

And in case you have to compare multiple points against a given plane, you can do Laplace expansion along the fourth column and end up with 4 numbers, each computed as a $3\times 3$ determinant, which represent something like the normal form of the plane and can be used to perform the subsequent checks using only 4 multiplications per point. So you'd compute

\begin{align*} a &= -\begin{vmatrix} y_1 & y_2 & y_3 \\ z_1 & z_2 & z_3 \\ 1 & 1 & 1 \end{vmatrix} & b &= \begin{vmatrix} x_1 & x_2 & x_3 \\ z_1 & z_2 & z_3 \\ 1 & 1 & 1 \end{vmatrix} \\[2ex] c &= -\begin{vmatrix} x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \\ 1 & 1 & 1 \end{vmatrix} & d &= \begin{vmatrix} x_1 & x_2 & x_3 \\ y_1 & y_2 & y_3 \\ z_1 & z_2 & z_3 \\ \end{vmatrix} \end{align*}

After this precomputation, you can use the sign of $ax+by+cz+d$ to decide on which side of the plane a point $(x,y,z)$ lies. If you want to use centroids without division, you'd multiply $d$ by $3$ and the others by the coordinate sums. The plane itself is described as

$$ \left\{(x,y,z)\in\mathbb R^3\;\middle\vert\;ax+by+cz+d=0\right\} $$

Notice that this is not quite the Hesse normal form of the plane, because the normal vector $(a,b,c)$ isn't normalized to unit length, and $d$ isn't neccessarily positive but instead indicates on which side of the plane the origin lies. So for computing distances you'd do some more computations, but to decide sidedness, these numbers $a$ through $d$ are all you need.

share|improve this answer
    
Awesome. Much obliged. –  luser droog Feb 8 '13 at 9:06
    
Yes. I will have to test multiple triangles against the same plane. –  luser droog Feb 9 '13 at 2:58
    
OMG. Amazing. I just got the expansion done in my notebook. Yes, I thought there was a close relation to the normal form. Thank you. Thank you. –  luser droog Feb 9 '13 at 3:24
    
I'm thinking I don't want to expand this any further, and it'd be better (simpler to verify) to write a function for 2x2 determinants and a 3x3 one that calls that. –  luser droog Feb 9 '13 at 3:35
    
I've posted my determinant function back on SO –  luser droog Feb 9 '13 at 4:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.