Triangle rasterization

The area of a triangle ABC can be determined from the coordinates of the three defining points via the Shoelace formula, as follows:

A = \left| \frac{(x_b - x_a)(y_c - y_a) - (y_b - y_a)(x_c - x_a)}{2} \right|

The area before the absolute value operation is applied is called the signed area:

A_{signed} = \frac{(x_b - x_a)(y_c - y_a) - (y_b - y_a)(x_c - x_a)}{2}

The sign of the signed area indicates the winding order of the points. The signed area will be positive if the points are in clockwise order, and negative if the points are in counter-clockwise order.

We can avoid the division if we only require the sign of the area. This is shown by the following equation, called the edge function:

E = (x_b - x_a)(y_c - y_a) - (y_b - y_a)(x_c - x_a)

The edge function can determine whether a triangle faces towards or away from the camera. If the edge function is negative, the triangle is facing away from the camera, and can be culled.

The edge function can also determine on which side of a line a point falls. Given the line AB which points toward B, the point C falls to the left side of AB if the edge function is negative, or the right side if the edge function is positive.

To determine whether the point P falls within the triangle ABC, we check the edge functions for the triangles ABP, BCP, and CAP, ensuring that the winding order of ABC is clockwise. P falls within ABC if all three edge functions are positive.

This can be made computationally more efficient by ignoring the winding order of ABC and testing only whether the signs of the three edge functions are equal, or by ensuring that the winding order of ABC is positive and failing early if any one edge function is negative.

Triangles

A triangle is a polygon with vertices V_0, V_1, V_2, and edges $

A triangle is degenerate if all three points are colinear. Any triangle lies on a plane, and for a non-degenerate triangle this plane is uniquely determined.

Triangles are always convex: for any two points inside the triangle, the line connecting them is also fully inside the triangle.