i
i
i
i
i
i
i
i
48 2. Miscellaneous Math
where A is the area of the triangle. Note that A = A
a
+ A
b
+ A
c
, so it can be
computed with two additions rather than a full area formula. This rule still holds
for points outside the triangle if the areas are allowed to be signed. The reason
for this is shown in Figure 2.39. Note that these are signed areas and will be
computed correctly as long as the same signed area computation is used for both
A and the subtriangles A
a
, A
b
,andA
c
.
Figure 2.39. Theareaof
the two triangles shown is
base times height and are
thus the same, as is any tri-
angle with a vertex on the
β = 0.5 line. The height
and thus the area is propor-
tional to β.
2.7.2 3D Triangles
One wonderful thing about barycentric coordinates is that they extend almost
transparently to 3D. If we assume the points a, b,andc are 3D, then we can
still use the representation
p =(1−β − γ)a + βb + γc.
Now, as we vary β and γ, we sweep out a plane.
The normal vector to a triangle can be found by taking the cross product of
any two vectors in the plane of the triangle (Figure 2.40). It is easiest to use two
of the three edges as these vectors, for example,
n =(b − a) × (c − a). (2.35)
Note that this normal vector is not necessarily of unit length, and it obeys the
right-hand rule of cross products.
Figure 2.40. The nor-
mal vector of the triangle is
perpendicular to all vectors
in the plane of the triangle,
and thus perpendicular to
the edges of the triangle.
The area of the triangle can be found by taking the length of the cross product:
area =
1
2
(b − a) ×(c − a). (2.36)
Note that this is not a signed area, so it cannot be used directly to evaluate barycen-
tric coordinates. However, we can observe that a triangle with a “clockwise” ver-
tex order will have a normal vector that points in the opposite direction to the
normal of a triangle in the same plane with a “counterclockwise” vertex order.
Recall that
a · b = ab cos φ,
where φ is the angle between the vectors. If a and b are parallel, then cos φ = ±1,
and this gives a test of whether the vectors point in the same or opposite directions.
i
i
i
i
i
i
i
i
2.7. Triangles 49
This, along with Equations (2.34), (2.35), and (2.36) suggest the formulas
α =
n · n
a
n
2
,
β =
n · n
b
n
2
,
γ =
n · n
c
n
2
,
where n is Equation (2.35) evaluated with vertices a, b,andc; n
a
is Equa-
tion (2.35) evaluated with vertices b, c,andp, and so on, i.e.,
n
a
=(c − b) × (p − b),
n
b
=(a − c) × (p −c),
n
c
=(b − a) × (p − a).
(2.37)
Frequently Asked Questions
• Why isn’t there vector division?
It turns out that there is no “nice” analogy of division for vectors. However, it
is possible to motivate the quaternions by examining this questions in detail (see
Hoffman’s book referenced in the chapter notes).
• Is there something as clean as barycentric coordinates for polygons with
more than three sides?
Unfortunately there is not. Even convex quadrilaterals are much more compli-
cated. This is one reason triangles are such a common geometric primitive in
graphics.
• Is there an implicit form for 3D lines?
No. However, the intersection of two 3D planes defines a 3D line, so a 3D line
can be described by two simultaneous implicit 3D equations.
i
i
i
i
i
i
i
i
50 2. Miscellaneous Math
Notes
The history of vector analysis is particularly interesting. It was largely invented
by Grassman in the mid-1800s but was ignored and reinvented later (Crowe,
1994). Grassman now has a following in the graphics field of researchers who
are developing Geometric Algebra based on some of his ideas (Doran & Lasenby,
2003). Readers interested in why the particular scalar and vector products are
in some sense the right ones, and why we do not have a commonly-used vector
division, will find enlightenment in the concise About Vectors (Hoffmann, 1975).
Another important geometric tool is the quaternion invented by Hamilton in the
mid-1800s. Quaternions are useful in many situations, but especially where ori-
entations are concerned (Hanson, 2005).
Exercises
1. The cardinality of a set is the number of elements it contains. Under IEEE
floating point representation (Section 1.5), what is the cardinality of the
floats?
2. Is it possible to implement a function that maps 32-bit integers to 64-bit in-
tegers that has a well-defined inverse? Do all functions from 32-bit integers
to 64-bit integers have well-defined inverses?
3. Specify the unit cube (x-, y-, and z-coordinates all between 0 and 1 inclu-
sive) in terms of the Cartesian product of three intervals.
4. If you have access to the natural log function ln(x), specify how you could
use it to implement a log(b, x) function where b is the base of the log. What
should the function do for negative b values? Assume an IEEE floating
point implementation.
5. Solve the quadratic equation 2x
2
+6x +4=0.
6. Implement a function that takes in coefficients A, B,andC for the quadratic
equation Ax
2
+ By + C =0and computes the two solutions. Have the
function return the number of valid (not NaN) solutions and fill in the return
arguments so the smaller of the two solutions is first.
7. Show that the two forms of the quadratic formula on page 17 are equivalent
(assuming exact arithmetic) and explain how to choose one for each root in
i
i
i
i
i
i
i
i
2.7. Triangles 51
order to avoid subtracting nearly equal floating point numbers, which leads
to loss of precision.
8. Show by counterexample that it is not always true that for 3D vectors a, b,
and c, a × (b ×c)=(a × b) ×c.
9. Given the non-parallel 3D vectors a and b, compute a right-handed or-
thonormal basis such that u is parallel to a and v is in the the plane defined
by a and b.
10. What is the gradient of f(x, y, z)=x
2
+ y − 3z
3
?
11. What is a parametric form for the axis-aligned 2D ellipse?
12. What is the implicit equation of the plane through 3D points (1, 0, 0),
(0, 1, 0),and(0, 0, 1)? What is the parametric equation? What is the nor-
mal vector to this plane?
13. Given four 2D points a
0
, a
1
, b
0
,andb
1
, design a robust procedure to
determine whether the line segments a
0
a
1
and b
0
b
1
intersect.
14. Design a robust procedure to compute the barycentric coordinates of a 2D
point with respect to three 2D non-collinear points.
i
i
i
i
i
i
i
i
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.