1
$\begingroup$

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.

  • 0
    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.2011-08-03

1 Answers 1

4

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.

  • 0
    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.2011-08-03