Graphics Reference
In-Depth Information
•An
n
1 table,
fntable
, of function values at the vertices of the mesh
• A point
P
of the mesh, expressed by giving the index,
t
, of the triangle in
which the point lies, and its barycentric coordinates
×
α
,
β
,
γ
in that triangle
Output:
• The value of the interpolated function at
P
The first thing to realize is that only the
t
th row of
ftable
is relevant to our
problem: The point
P
lies in the
t
th triangle; the other triangles might as well not
exist. If the
t
th triangle has vertex indices
i
0,
i
1, and
i
2, then only those entries in
vtable
matter. With this in mind, our code is quite simple:
1
2
3
4
5
6
7
8
9
10
11
double meshinterp(double[,] vtable, int[,] ftable,
double[] fntable, int t, double alpha, double beta, double gamma)
{
int i0 = ftable[t, 0];
int i1 = ftable[t, 1];
int i2 = ftable[t, 2];
double fn0 = fntable[i0];
double fn1 = fntable[i1];
double fn2 = fntable[i2];
return alpha
*
fn0 + beta
*
fn1 + gamma
*
fn2;
}
Now suppose that
P
is given differently: We are given the coordinates of
P
in
3-space rather than the barycentric coordinates, and we are given the index
t
of the
triangle to which
P
belongs, and we need to find the barycentric coordinates
α
,
β
,
and
γ
. If we say that the vertices of the triangle
t
are
A
,
B
, and
C
, we want to have
α
A
x
+
β
B
x
+
γ
C
x
=
P
x
(9.8)
where the subscript
x
indicates the first coordinate of a point; we must also satisfy
the same equations for
y
and
z
. But there's one more equation that has to hold:
α
+
β
+
γ
=
1. We can rewrite that in a form that's analogous to the others:
α
1
+
β
1
+
γ
1
=
1.
(9.9)
Now our system of equations becomes
⎡
⎣
⎤
⎦
⎡
⎣
⎤
⎦
⎡
⎤
A
x
B
x
C
x
A
y
B
y
C
y
A
z
B
z
C
z
111
P
x
P
y
P
z
1
α
β
γ
⎣
⎦
=
.
(9.10)
There's really no solution here except to directly solve the system of equations.
The problem is that we have four equations in three unknowns, and most solvers
want to work with
square
matrices rather than rectangular ones. (Section 7.9.2
presented an alternative approach to this problem using some precomputation, but
that precomputation amounts to doing much of the work of solving the system of
equations.)
The good news is that the four equations are in fact redundant: The fact that
P
is
given
to us as a point of the triangle ensures that if we simply solve the first three
equations, the fourth will hold. That assurance, however, is purely mathematical—
computationally, it may happen that small errors creep in. There are several viable
approaches.
