Barycentric coordinates

Rendering a triangle using barycentric coordinates as introduced in Pineda 88 has given the main theoretical ground to gpu design and shader programming since.

Observations

Since barycentric coordinates interpolation is implemented on the GPU, this chapter mainly serves a theoretical purpose. However, it is recommended to study this topic prior to shader programming.
All the points display on the sketches below are interactive. You may click and drag them to get a better insight of what’s been discussed.

Geometric motivation

Given points $p$ , $t$ and $u$ in 2D Euclidean space, we know that the determinant gives the signed area of the parallelogram spanned by the vectors $\overrightarrow{u-t}$ and $\overrightarrow{p-t}$ :

Area_{\text{\char"25B1}} = \begin{vmatrix} u_x - t_x & p_x - t_x \\ u_y - t_y & p_y - t_y \end{vmatrix} = 2\,Area_{\triangle}

Observation
The sign of the determinant tells to which side of edge tu point p lies.

Edge functions

By developing and rearranging its terms the above determinant can be expressed in terms of point $p$ as:

2Area_{\triangle} = (t_{y} - u_{y}) p_x + (u_{x} - t_{x}) p_y + (t_{x} u_{y} - t_{y} u_{x})

which is defined as the edge function of $tu$ and simply denoted as: $e_{tu}(p)$ , i.e.,

e_{tu}(p) := (t_{y} - u_{y}) p_x + (u_{x} - t_{x}) p_y + (t_{x} u_{y} - t_{y} u_{x})

If the remaining triangle vertex $v$ is considered it’s also possible to define the other two triangle edge functions as:

e_{uv}(p) := (u_{y} - v_{y}) p_x + (v_{x} - u_{x}) p_y + (u_{x} v_{y} - u_{y} v_{x})

e_{vt}(p) := (v_{y} - t_{y}) p_x + (t_{x} - v_{x}) p_y + (v_{x} t_{y} - v_{y} t_{x})

Observation
Point p lies inside △ tuv iff the sign of the three edge functions are the same. This sole fact gives means to automate triangle rasterization.

Barycentric coordinates

The triangle (unnormalized) barycentric coordinates are defined directly from the edge functions as:

w_t(p) := e_{uv}(p)

w_u(p) := e_{vt}(p)

w_v(p) := e_{tu}(p)

Normal form

The $\triangle(t,u,v)$ area is used to define the normalized barycentric coordinates as:

\lambda_t(p) := w_t(p) / 2 \triangle(t,u,v)

\lambda_u(p) := w_u(p) / 2 \triangle(t,u,v)

\lambda_v(p) := w_v(p) / 2 \triangle(t,u,v)

where, $\lambda_t(p) + \lambda_u(p) + \lambda_v(p) = 1$

Properties

It’s easy to see that (interact with the sketch above):

if $p = t$ then $\lambda_t(p) = 1$ , $\lambda_u(p) = 0$ , and $\lambda_v(p) = 0$ .
If $p = u$ , or $p = v$ , or $p$ lies along edge $uv$ then $\lambda_t(p) = 0$ .
$p = \lambda_t(p)t + \lambda_u(p)u + \lambda_v(p)v$ , i.e., the normalized barycentric values measures the relative weights of the vertices t, u, and v required to interpolate p.

Shading

Not only positions but any vertex data, e.g., color, depth, texture coordinates, may be interpolated by using property 3 above.

Color interpolation

(software raster demo)

Color is one of the most common proporties associated to a vertex.

(click on the canvas and press any key)

TODO: sketch="/sketches/rasterize_color.js" quadrille=“true”

Color interpolations greatly alleviates the appearance of mach bands.

(click on the canvas and press any key)

TODO: sketch="/sketches/rasterize_strip.js" quadrille=“true”

Depth interpolation

(hardware raster demo)

Depth interpolation produces the z-buffer which solves the visibility problem. Vertex depth values are computed using a projection matrix.

(click on the canvas and press any key)

TODO: sketch="/sketches/zbuffer.js"

Texture mapping

(software raster demo)

Vertex texture coordinates is defined in image space (left frame).

TODO: sketch="/sketches/rasterize_texture.js" quadrille=“true”

Conclusion

Barycentric coordinates are crucial for implementing rasterization through dedicated hardware, as they can easily be parallelized, effectively address the visibility problem and also provide means to programmatically implement shading.

Spaces