Mathematical Structures for Computer Graphics

Chapter 6Polygons and Polyhedra

Since lines and planes are fundamental to geometry, shapes bounded by lines and planes at least have access to the center stage in computer graphics. Most modeling efforts, no matter how they begin, usually end up with a vast assortment of triangles because this shape is guaranteed to be planar even when the vertices are points in space. There are online repositories of models composed entirely of very large sets (thousands) of triangles. Understanding the geometry of triangles and how to efficiently use them in computation is particularly important in graphics. More general polygons arise when constructing complex objects (polyhedra) and when projecting those objects to find shadows. The geometry of both polygons and polyhedra is the key to much of graphics and gives rise to a wide range of mathematical tools.

6.1 Triangles

Triangles are well studied in elementary geometry, and with vector geometry we have the tools to calculate most of what we need in graphics: side lengths, angles, and areas. One key problem is to determine whether a point of intersection is inside a triangle in space. Although elementary tools can suffice, there is always a quest to find better ways to express the problem in the hope of improving computational efficiency. Barycentric coordinates offer a different view of triangle geometry and thereby lead to some nice algorithms.

6.1.1 Barycentric Coordinates

Recall from Chapter 2 (Section 2.1.1) that addition of points ...