Barycentric coordinates

From DmWiki

Barycentric coordinates were named by the german mathematican Franz Ferdinand MÃ¶bius, who is otherwise famous for inventing the MÃ¶bius Strip (http://en.wikipedia.org/wiki/M%C3%B6bius_strip).

Given a system described by the set of points P = [A, B, ..., N] and a set of barycentric coordinates [a, b, c, ..., n] the center of mass (barycenter) of P lies at the point $p = a A + b B + ... + n N$ . In computer graphics, barycentric coordinates are commonly used to describe points on convex polygons, since p is defined to be insided the convex hull of P, if $a + b + ... + n = 1$ .

Barycentric coordinates are used, for example, in computing ray-triangle intersections.

Table of contents

1 Computation for n-Simplexes

1.1 n-Simplex in n dimensions
1.2 n-Simplex in more than n dimensions

2 Links

[edit]

Computation for n-Simplexes

An n-dimensional simplex is defined as the convex hull formed by n + 1 affinely independent points. For instance, a 0-simplex is a point, a 1-simplex is a line, a 2-simplex is a triangle, a 3-simplex is a tetrahedron, etc. An n-simplex can exist in any dimension of n or higher. The most common example in computer graphics is a 2-simplex (triangle), which typically exists on a plane in 3D. Whether or not an n-simplex exists in n dimensions or higher determines which approach we should use to calculate the barycentric coordinates of a point.

If we have n + 1 affinely independent points, we can generate n linearly independent basis vectors by treating a single point as the "origin". Given the points $p_0, p_1, \cdots, p_n$ defining the simplex, we generate basis vectors $\vec{b}_1 = (p_1 - p_0), \vec{b}_2 = (p_2 - p_0), \cdots, \vec{b}_n = (p_n - p_0)$ . These basis vectors define an n dimensional subspace. If we let $r$ be the point we're testing, then we also treat it as though $p 0$ is the origin by letting $v = (r - p 0)$ . Our goal is to find the coordinates of $v$ in this subspace, which are essentially the barycentric coordinates.

[edit]

n-Simplex in n dimensions

Given n linearly independent vectors in n dimensions, we construct an nxn matrix $\mathbf{A}$ which has the basis vectors as the columns:

$\begin{bmatrix} \uparrow & \uparrow & & \uparrow \\ \vec{b}_1 & \vec{b}_2 & \cdots & \vec{b}_n \\ \downarrow & \downarrow & & \downarrow \end{bmatrix}$

The point $v$ can then be expressed in terms of the transformation $\mathbf{A}\vec{x} = v$ , where $\vec{x}$ is a vector containing the barycentric coordinates $\omega_1, \omega_2, \cdots, \omega_n$ for points $p 1$ through $p n$ . We can solve for $\vec{x}$ by multiplying both sides of the equation by $\mathbf{A}^{-1}$ , such that $\vec{x} = \mathbf{A}^{-1}v$ . We are assured the matrix is invertible because it's square and the columns are linearly independent. The barycentric coordinate for $p 0$ is then just $1 - \sum_{i=1}^n{\omega_i}$ . If $\omega_0, \omega_1, \cdots, \omega_n \geq 0$ , then the point is within the simplex.

[edit]

n-Simplex in more than n dimensions

As before, we construct a matrix $\mathbf{A}$ using the n linearly independent basis vectors as the columns. However, we won't be able to simply invert this matrix and solve for $\vec{x}$ because it is tall and hence un-invertible.

Starting from the equation $\mathbf{A}\vec{x} = v$ , we can rearrange the terms to get $\mathbf{A}\vec{x} - v = \mathbf{0}$ . The dot product of any vector with the zero vector is zero, so the dot product of each basis vector with $\mathbf{A}\vec{x} - v$ should be 0. This gives us the equation $\mathbf{A}^T(\mathbf{A}\vec{x} - v) = 0$ . We can now finally solve for $\vec{x}$ , which is $\vec{x} = (\mathbf{A}^T\mathbf{A})^{-1}\mathbf{A}^Tv$ . It is also the case that the dot product of any vector with any other perpendicular vector is also zero. So the above process would work for any vector $\mathbf{A}\vec{x} - v$ that was perpendicular to all the basis vectors. This has the effect of projecting (http://en.wikipedia.org/wiki/Projection_(linear_algebra)) all vectors orthogonally onto the subspace.