Graphics Reference
In-Depth Information
• Express
P
as a convex combination of
four
points of
R
4
: the three already
written and a fourth, with coordinates
n
x
,
n
y
,
n
z
, and 0, where
n
is the nor-
mal vector to the triangle. The expression will have a fourth coefficient,
,
in the solution, representing the degree to which
P
is
not
in the plane of
A
,
B
, and
C
. We ignore this and scale up the computed
δ
α
,
β
, and
γ
accord-
ingly, using
)
as the barycentric coor-
dinates. This is a good solution (in the sense that if the numerical error in
P
is entirely in the
n
direction, the method produces the correct result), but
it requires solving a 4
α/
(
1
−δ
)
,
β/
(
1
−δ
)
, and
γ/
(
1
−δ
4 system of equations.
• Delete the fourth row of the system in Equation 9.10; adjust
×
α
,
β
, and
γ
to
sum to one by dividing each by
α
+
β
+
γ
. This reduces the problem to a
3 system, but it lacks the promise of correctness for normal-only errors.
• Use the pseudoinverse to solve the overconstrained system (see Sec-
tion 10.3.9). This has the advantage that it's already part of many numer-
ical linear algebra systems, and that it works even when the triangle is
degenerate (i.e., the three points are collinear), in the sense that
if
3
×
P
lies in the triangle, then the method produces numbers
α
,
β
, and
γ
with
α
C
=
P
, even though the solution in this case is not unique.
Better still, if
P
is not in the plane of
A
,
B
, and
C
, the solution returned will
have the property that
A
+
β
B
+
γ
C
is the point in the plane of
A
,
B
, and
C
that's closest to
P
. This is therefore the ideal.
So the restated problem looks like this.
Input:
α
A
+
β
B
+
γ
• A triangle mesh in the form of an
n
×
3 table,
vtable
, of vertices
•A
k
3 table,
ftable
, of triangles, where each row of
ftable
contains
three indices into
vtable
• A point
P
of the mesh, expressed by giving the index,
t
, of the triangle in
which the point lies, and its coordinates in 3-space
×
Output:
• The value of the barycentric coordinates of
P
with respect to the vertices
of the
k
th triangle
And our revised solution is this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
double[3] barycentricCoordinates(double[,] vtable,
int[,] ftable, int t, double p[3])
{
int i0 = ftable[t, 0];
int i1 = ftable[t, 1];
int i2 = ftable[t, 2];
double[,] m = new double[4, 3];
for (int j = 0; j < 3; j++) {
for (int i = 0; i < 3; i++) {
m[i,j] = vtable[ftable[t, j], i];
}
m[3,j] = 1;
}
k = pseudoInverse(m);
return matrixVectorProduct(k, p);
}
