Subdivision for the Ultimate Consumer

We make available a windows binary together with the Microsoft C++ source code that performs subdivision of surface and volumetric meshes. Key features of our program are

The software handles vertices of arbitrary dimension. Next to (x,y,z)-coordinates, texture and color coordinates are subject to subdivision as well.

Subdivision of Surface and Volumetric Meshes * subdivision.zip 80 kB
* developed at the computer science department of Rice University in 2004. My supervisors were Joe Warren and Scott Schaefer. The program is compiled for Windows. The C++ source code is included here.

Members of the open source community Quest for More Glory have used the code to refine their 3d meshes. The screen shots are taken from their forum:

Es gibt einen Platz, den du füllen musst,
den niemand sonst füllen kann,
und es gibt etwas für dich zu tun,
das niemand sonst tun kann.
Plato

Other implementations:

Code for Mathematica 9: An implementations of Doo-Sabin, Catmull-Clark, and Loop surface subdivision (with capability to handle cubic B-spline creases) is available here.

Code for MATLAB: An implementations of Loop, Schaefer/Warren TriQuad, and tetrahedral subdivision is available here.

What the program does



A popular way to represent surfaces in computer graphics is to use triangular meshes. In physical simulations for instance, triangular meshes are accurate for collision detection.

Subdivision of triangular meshes is an automated procedure to approximate smooth surfaces given an initially coarse triangular mesh.

In 1987, Charles Loop developed a subdivision algorithm for triangular meshes in his thesis Smooth subdivision surfaces based on triangles. In one round of subdivision, each triangle splits into four smaller triangles. The positioning of the vertices is determined by a mathematical formula.

Our subdivision tool applies Loops algorithm in regions of the mesh that consist entirely of triangles.




Depending on the symmetry of parts of the geometric object, quadrilateral facets might be the more intuitive choice for modelling. For instance, cylindrical shaped objects are commonly formed out of quads.

In 1978, Edwin Catmull and Jim Clark presented a subdivision scheme for quadrilateral meshes in Recursively generated B-spline surfaces on arbitrary topological meshes, what is up to the present day the most popular refinement scheme for quadrilateral meshes. Our subdivision tool applies the Catmull-Clark algorithm in regions of the mesh that are patched entirely by quads.

Evidently, the maximum convenience in surface modelling is achieved when both types of facets, triangles and quads, may be combined within a mesh.

In 2003, Adi Levin and David Levin designed a subdivison scheme for these mixed surface meshes in Analysis of Quasi-Uniform Subdivision. However, the main contribution was the novel approach to analyse mixed subdivision schemes in general.

Inspired by this novel method, Scott Schaefer and Joe Warren modified the algorithm into a simpler scheme On C^2 Triangle/Quad Subdivision, which is implemented in our subdivision tool. The scheme was published in 2005.



The applications of volumetric subdivision are deformation of surfaces and contextualized space partitioning.

Schemes for meshes consisting of cubes, or triangular prisms are derived from surface subdivision. New and fundamental shapes in the 3-dimensional scenario are tetrahedra and octahedra.

In 2004, that Scott Schaefer and Joe Warren designed Smooth Subdivision of Tetrahedral Meshes that has all the desirable properties.

Evidently, the maximum convenience in volume modelling is achieved when all types of shapes, cubes, triangular prisms, tetrahedra, and octahedra may be combined within a mesh.

In 2004, I merged the existing volumetric schemes into a universal scheme in my thesis Smooth Subdivision for Mixed Volumetric Meshes. Novel in this work are the algorithms for the refinement along the interfaces between two different types of shapes.

After several rounds of subdivision, surface meshes with their tiny facets tend to look smooth. Subdivided volumetric meshes induce a smooth parametrisation of space almost everywhere. After all, that is what the subdivision algorithms have been designed for. For more details on the performance of the subdivision algorithms please consult the research papers that are linked above.

the program seems to be working great for my purposes!
The only thing that I can think of that would make this
even more useful is if it could be compiled as a library.
But even if not I will definitely be using the program
and telling others about it! Nate

Details

These files are included in the software subdivision.zip: 

subdiv.exe            executable that performs subdivision
tab/                  folder with binary files that contain lookup tables
orientation.gif       image you see at the bottom of this webpage
run_sample.bat        batch file that calls subdiv.exe to subdivide sample.txt
sample.txt            sample mesh thoroughly commented
sample_triangle.txt   example mesh from this webpage
sample_surface.txt    ...
sample_volume.txt     ...

When supplied with no parameters, the executable subdiv.exe outputs the following message to the console: 

Subdivision for Surface and Volumetric Meshes
by jph, available at www.hakenberg.de

 syntax: subdiv filename [options]
 
options: arbitrary sequence of the characters
         b - add boundary
         s - normal subdivision
         l - linear subdivision
         
Mesh operations are performed in order of appearance.
The resulting mesh is stored in filename.out

example: subdiv sample.txt b l s s
...hit ENTER to continue...

When defining a shape of a mesh, the references to the vertices are required to appear in the order depicted below.

Orientation
A witty saying proves nothing.
François-Marie Arouet