Graphics Reference
In-Depth Information
// Check if P in edge region of AC, if so return projection of P onto AC
float vb = d5*d2 - d1*d6;
if (vb <= 0.0f && d2 >= 0.0f && d6 <= 0.0f) {
floatw=d2/(d2-d6);
returna+w*ac;
// barycentric coordinates (1-w,0,w)
}
// Check if P in edge region of BC, if so return projection of P onto BC
float va = d3*d6 - d5*d4;
if (va <= 0.0f && (d4 - d3) >= 0.0f && (d5 - d6) >= 0.0f) {
float w = (d4 - d3) / ((d4 - d3) + (d5 - d6));
returnb+w*(c-b);
// barycentric coordinates (0,1-w,w)
}
// P inside face region. Compute Q through its barycentric coordinates (u,v,w)
float denom = 1.0f / (va + vb + vc);
floatv=vb*denom;
floatw=vc*denom;
returna+ab*v+ac*w;
//=u*a+v*b+w*c,u=va*denom = 1.0f-v-w
}
A third way of obtaining the closest point is to use a vector calculus approach,
as suggested in [Eberly01]. Briefly, the triangle
ABC
is parameterized as
T
(
s
,
t
)
=
A
1. The closest point to
a given point
P
now corresponds to the minimum of the squared distance function
d
(
s
,
t
)
+
s
(
B
−
A
)
+
t
(
C
−
A
), where
s
≥
0,
t
≥
0, and
s
+
t
≤
=
T
(
s
,
t
)
P
2
, which is a quadratic expression in
s
and
t
. The minimum of
this function must occur in one of three cases: at a vertex, on an edge, or in the interior
of the triangle. By first differentiating
d
(
s
,
t
) with respect to these different cases (that
is, substituting
s
−
s
as necessary), setting the derivatives to zero
and solving, and then comparing the resulting
s
and
t
values to the triangle bounds,
it is possible to find out which case corresponds to the minimum.
For this particular application, the vector calculus solution becomes more com-
plicated than just described. However, the general approach of viewing the problem
as a quadratic minimization problem is valuable, and the same idea can be used to
determine the distance between, say, a line or line segment and a triangle. Addi-
tional information on the vector calculus approach, including pseudocode, is given
in [Eberly01].
=
0,
t
=
0, or
t
=
1
−
5.1.6
Closest Point on Tetrahedron to Point
Given a point
P
, the problem is determining the point
Q
on (or in) a tetrahedron
ABCD
closest to
P
(as illustrated in Figure 5.7). A straightforward solution is to compute
Q
