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'm trying to find a solution to this symbolic non-linear vector equation:

P = a*(V0*t+P0) + b*(V1*t+P1) + (1-a-b)*(V2*t+P2) for a, b and t
where P, V0, V1, V2, P0, P1, P2 are known 3d vectors.

The interesting bit is that this equation has a simple geometrical interpretation. If you imagine that points P0-P2 are vertices of a triangle, V0-V2 are roughly vertex normals* and point P lies above the triangle, then the equation is satisfied for a triangle containing point P with it's three vertices on the three rays (Vx*t+Px), sharing the same parameter t value. a, b and (1-a-b) become the barycentric coordinates of the point P.

In order words for a given P we want to find t such that P is a linear combination of (Vx*t+Px).

So if the case is not degenerate, there should be only one well defined solution for t.

*) For my needs we can assume these are roughly vertex normals of a convex tri mesh and of course lie in the half space above the triangle.

I posted this question to stackoverflow, but no one was able to help me there. Both MatLab and Maxima time out while trying to solve the equation.

share|improve this question
    
It looks like you should be able to convert this into an equation of the form $Ax=0$ for some unknown vector $x=(a,b,1)$ and matrix $A = A(t)$, which has a solution only when $\det A=0$. This gives you an equation to solve for $t$ (which will probably be quadratic, so zero or two solutions) and then you can find $a$ and $b$ by finding the one-dimensional kernel of $A$. I'll look at it in more detail later, but maybe this hint is enough to get you going. –  Chris Taylor Aug 3 '11 at 10:24
add comment

1 Answer

up vote 3 down vote accepted

Let's rewrite:

$$a(P_0 - P_2 + t(V_0-V_2)) + b(P_1 - P_2 + t(V_1 - V_2)) = P - P_2 - t V_2$$

which is linear in $a$ and $b$. If we let $A=P_0-P_2$ and $A'=V_0-V_2$ and $B=P_1-P_2$ and $B'=V_1-V_2$ and $C=P-P_2$ and $C'=-V_2$ then you have

$$a(A + tA') + b(B + tB') = C + tC'$$

This can be written as a matrix equation:

$$ \begin{bmatrix} A_1 + t A'_1 & B_1 + t B'_1 & C_1 + tC'_1 \\ A_2 + t A'_2 & B_2 + t B'_2 & C_2 + tC'_2 \\ A_3 + t A'_3 & B_3 + t B'_3 & C_3 + tC'_3 \end{bmatrix} \begin{bmatrix} a \\ b \\ -1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0\end{bmatrix}$$

or $Ax=0$, with suitable definitions for $A$ and $x$, and with both $A$ and $x$ unknown. Now you know that this only has a solution if $\det A = 0$, which gives you a cubic in $t$. Solving for $t$ using your favorite cubic solver when gives you $Ax=0$ with only $x$ unknown - and $x$ is precisely the zero eigenvector of the matrix $A$. The fact that the third component of $x$ is $-1$ forces the values of $a$ and $b$, and you are done.

share|improve this answer
    
Thanks a lot, Chris! Indeed it looks like this is the way to go :) And it looks like using the additional constraints I have I'll be able to choose the correct t of the three that $\det A = 0$ will give me. –  robert Aug 3 '11 at 13:59
add comment

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.