Barycentric Coordinates with Applications in Mesh Deformation

Tao Ju, 2007

Introduction
Constructing a function that interpolates a set of values defined at vertices of a mesh is a fundamental operation in computer graphics. For example, Gouraud shading computes intensity f[x] at an interior point x of a triangle from intensities at the triangle vertices f_i using affine combination

The affine weights b_i[x] are often called barycentric coordinates. In a triangle, such coordinates are unique, and b_i has the geometric interpretation as the ratio of the area of the triangle formed by x and the opposite edge to vertex i over the area of the original triangle. Barycentric coordinates have many uses in applications such as shading, parameterization and deformation. However, computing such coordinates is not an easy task, especially for non-convex shapes, continuous shapes, or shapes in 3D or higher dimensions.
Methods
Our research addresses both theory and application aspects of barycentric coordinates. On the theory side, we work on developing new coordinates and extending existing coordinates to arbitrary shapes, smooth shapes and higher dimensions. On the application side, we explore the use of barycentric coordinates in mesh deformation and other applications.

Mean Value Coordinates [SIGGRAPH 2005]

Originally developed by Floater [2003], mean value coordinates have been shown to yield smooth coordinate functions in 2D for arbitrarily shaped polygons. The coordinates have been applied in parameterizing 3D meshes. Floater et al. [2005] and we independently discovered the extension of mean value coordinates onto closed triangular meshes in 3D. We show that the coordinate functions is smooth throughout the space for arbitrary closed meshes, and we demonstrated how it could be used to yield smooth deformation of complex models using simple control shapes.



Wachspress Coordinates [SGP 2005]

Wachspress [1975] first proposed a barycentric coordinates for convex 2D polygons, which has been studied and refined over the years. Although its extension to 3D shapes was found by Warren [1996] and others [2004], the construction was hard to understand. Using a geometric notion known as polar duals, we are able to express the Wachspress coordinates in any dimensions in a simple geometric form as ratios of simplicial volumes. In this same geometric construction, we are also able to express a vector lying in a convex cone as a non-negative combination of edge rays of this cone. The geometric approach simplifies constructing Colin de Verdire matrices from convex polyhedra, a critical step in Lovasz's method with applications to parameterizations.



General construction [CAGD 2007]

Since barycentric coordinates in a general shape is not unique, it is of great interest to have a general method of building possible barycentric coordinates in the hope that we could find new and meaningful coordinates. Motivated by the work of Floater et al. [2004], we developed a general construction of barycentric coordinates in convex triangular polyhedra as well simplicial shapes in higher dimensions. The nice property of this construction is that it generates all possible coordinates, and we show how Wachspress, mean value and discrete harmonics coordinates are unified by the same construction with an intrinsic geometric relation.



Coordinates for smooth shapes [CAGD 2007]

One of the logical next step continuing the study of coordinates on discrete polytopes is to consider coordinates over continuous curves and surfaces. We have developed a unifying framework for generating coordinates over continuous 2D curves, and have shown that coordinates on discrete polygons are simply special cases of the continuous construction when restricted to piece-wise linear curves. In the future, we plan to extend this result into 3D and higher dimensions with the goal of establishing a general framework of coordinates construction for both continuous and discrete shapes.




Web Resource

Talks
  • A general geometric construction of coordinates in a convex simplicial polytope
    Invited talk at Eurographics IPC Minisymposium, Prague, Czech Republic, April 2007 (Download PPT 3MB)

  • Mean value coordinates for closed triangular meshes
    Paper presentation at ACM SIGGRAPH (by Scott Schaefer), Los Angeles, August 2005 (Download PPT 16MB)
Collaborators


Comments or suggestions: taoju at cs.wustl.edu