As each triangle is rendered, information from it is mapped from the virtual world onto the screen. This is usually accomplished using *barycentric coordinates* (see Figure 7.7), which expresses each point in the triangle interior as a weighted average of the three vertices:

(7.10) |

for which and . The closer is to a vertex , the larger the weight . If is at the centroid of the triangle, then . If lies on an edge, then the opposing vertex weight is zero. For example, if lies on the edge between and , then . If lies on a vertex, , then , and the other two barycentric coordinates are zero.

The coordinates are calculated using Cramer's rule to solve a resulting linear system of equations. In particular, let for all combinations of and . Furthermore, let

(7.11) |

The coordinates are then given by

(7.12) |

The same barycentric coordinates may be applied to the points on the model in , or on the resulting 2D projected points (with and coordinates) in the image plane. In other words, , , and refer to the same point on the model both before, during, and after the entire chain of transformations from Section 3.5.

Furthermore, given the barycentric coordinates, the test in (7.9) can be replaced by simply determining whether , , and . If any barycentric coordinate is less than zero, then must lie outside of the triangle.

Steven M LaValle 2016-12-31