Smooth Subdivision for Mixed Volumetric Meshes

four basic shapes

From September 2003 to August 2004, I was involved in research on subdivision algorithms at the computer science department of Rice University in Houston/USA. My thesis is on how to combine uniform volumetric subdivision schemes of cubes, triangular prisms, tetrahedra, and octahedra into a single volumetric scheme.

I derive an algorithm for mixed, unstructured volume meshes consisting of these four types of shapes. In the limit, the scheme yields a parametrization of space that is

During the two semesters, Scott Schaefer helped me on issues of programming and subdivision. My advisor was Joe Warren.

Smooth Subdivision for Mixed Volumetric Meshes (Thesis) smooth_subdivis... 3 MB
Subdivision and deformation tool (including C++ source) * 200 kB
* compiled for Windows. Documentation and examples are included.
Für das Können gibt es nur einen Beweis: das Tun.
Marie von Ebner-Eschenbach

Subdivision of a volume mesh is very similar to subdivision for surfaces. Iteratively, shapes are split into smaller shapes and vertices are positioned according to certain mathematical formulas to make the outcome appear as smooth as possible. Volumetric subdivision induces a C2 parametrization of space almost everywhere.

Subdivision for surface meshes inspires volumetric subdivision

Publications related to my thesis are

The thesis is referenced in

Spinnweben: das Fliegengitter des kleinen Mannes.
Thomas Tonn

Application: Smooth deformations

Besides contextualized space partitioning, the major motivation for volumetric subdivision is to perform smooth deformations of surface models.

Deformation via volumetric subdivision

The deformation procedure requires the following input:

Let be the matrix consisting of the vertices of the surface model mesh, that is

And let be the matrix consisting of the vertices of the volumetric control mesh. We are interested in a matrix that satisfies

We deform the surface model by changing the vertices of the control mesh to . Then, the vertices of the deformed surface model compute as

My thesis describes how to obtain as a matrix product, where

Given the initial meshes, the software that we provide outputs the matrix .

To demonstrate the quality of this approach, we deform the model Noma into several poses by designing and altering a volumetric control mesh:

Character animation
please click on the image for more examples


The subdivision algorithm and the deformation results were presented within the scope of the mathematical "Studentische Vortragsreihe 2005" as well as on the 2005 "Workshop" of the geometric modeling research group of the Technische Universität Darmstadt/Germany.

Per aspera ad astra