This project is based on Taubin's Fair Surface Design algorithm, which uses a non-shrinking variant of the Gaussian smoothing algorithm to move vertices in and out in order to smooth a polygon mesh. The image above is (frame A) from a CT scan of a spine, and frames B, C, and D are successively more smoothed versions thereof. The goal of the project was to build an Open Inventor based tool for smoothing meshes, allowing constraints to be set and subdivision to be done. The final product allows fairing using arbitrary sequences of Gaussian parameters, mesh subdivision, setting of hierarchical constraints and fixed points, arbitrary motion of mesh points, and motion of mesh points with smooth deformation.

- The underlying theory
- My planned implementation timeline
- Implementation journal
- Download the final code
- Papers referenced

All images on this page (besides the screen shots) are from 1 .

For each vertex on the mesh, calculate delta-x as the weighted sum of the vectors from the vertex to its neighbors. Then, for each vertex, add in lambda (where lambda is a number between 0 and 1) times delta-x. Then repeat the algorithm, but instead of lambda, use mu (where mu is a negative number, less than -lambda). Both steps are repeated in sequence several times, until the mesh is sufficiently smooth. Without the second step, this produces Gaussian smoothing, which causes shrinkage of the mesh over time. The second step counteracts the shrinkage while still smoothing the mesh.

By repeatedly subdividing the mesh (breaking each polygonal face into multiple, smaller faces) and then applying the smoothing algorithm, a rough approximation of a surface can be turned into a much prettier surface than smoothing or subdivision alone.

By manipulating the internal representation of the mesh, it is possible to have two vertices, x and y, such that x considers y to be its neighbor, but y does not consider x to be its neighbor. This is called a non-symmetric neighborhood structure. The effect of such a manipulation on the smoothing algorithm is that x will use y's position to calculate its new position, but y will be independent of x. If y has been completely isolated, i.e. some points consider y a neighbor, but y considers itself to have no neighbors, then y will remain fixed through successive iterations of the algorithm, while still affecting surrounding vertices. An example of this can be seen in frame C of the picture above: the vertices at the foot were defined as having empty neighborhoods, so they remained stationary through the smoothing algorithm.

As an extension of this idea, a weight l can be attached to each vertex. If two vertices x and y have weights lx and ly, and they would otherwise be considered neighbors of one another (for example, because they share an edge in the mesh), then x is a neighbor of y only in ly <= lx. For example, if you were to give a set of points a label which is higher than the label the other points have, those points would only take one another into consideration as the smoothing progresses, but would affect other points. You could thus build an infrastructure about which the rest of the smoothing must be done. This is useful when you want to preserve certain aspects of the original shape of the mesh which might otherwise be smoothed away by the algorithm. An example can be seen in frame D of the picture above: the vertices at the foot have been labeled in such a way that they move only under the influence of one another, but still affect outside points.

- 4/15/97: build a tool to make example meshes by sudividing simpler meshes and jittering new coordinates in the direction of the centroid
- 4/28/97: build Inventor based tool that can do fairing of triangular meshes using Taubin's algorithm
- 5/5/97: add support for more efficient filters as discussed in the second paper
- 5/12/97: add ability to execute sequences of alternating subdivision and fairing
- 5/19/97: add ability to add hierarchical (neighborhood manipulation) constraints
- 6/2/97: add smooth interpolation (ability to move points and have shape smooth about it)

- 4/27/97: got preliminary fairing to work. These pictures
represent a gaussian smoothing algorithm, with lambda=1.0, applied 0,
1, and 20 times. Because it's plain gaussian smoothing, every
smoothing step makes the overall shape smaller, a fact that's hidden
because they were automatically resized when I did the image capture.
- 5/3/97: added ability to read in a file containing a schedule of
lambda and mu pairs to use in smoothing. This allows you to try out
some of the more efficient combinations discussed in 2. With
parameters chosen according to the rules, there is no shrinkage.
The image below is the same mesh seen in the first image above, faired
with the set of parameters described in 2, figure 9 part F (24 steps
total). Note that it looks suspiciously like the image above after a
single step of gaussian smoothing.
- 5/13/97: subdivision works. Oddly enough, a 64-face mesh shrinks
rapidly when a normally stable lambda/mu schedule is applied to it,
but if the same mesh is once subdivided, it starts to grow (slightly)
when fairing. The picture shows a simple 64 face mesh, then the same
mesh subdivided to 4096 faces (after which it looks the same) and then
faired by 24 steps of the schedule from 2, figure 9-F, and then the
original mesh, with four sequences consisting of six fairing and one
subdivision applied (same schedule). Note that the last mesh shrank
because it was only 64 faces when the first six fairing steps set in.
I don't know why that has that effect, though.
- 5/18/97: hierarchical constraints work now, despite some unidentified
inventor problems. Shown here is the same old mesh you've seen so
many times before, with the corner points fixed and thousands of fairing
steps applied.
- 6/12/97: added fixed points, in addition to the hierarchical
constraints. This allows you to actually make useful skeleton loops,
since if you make a loop (set of vertices each of which is connected
to two others) with a higher label than the surrounding points, they
will shrink and take the rest of the mesh with it (higher connectivity
skeletons -- not sure where the border is -- don't have this problem).
Also added ability to move points, and (much cooler) smooth
deformation: the ability to move points and have the surrounding
points automatically smoothed in real time. I created the thing below
by smoothing, subdividing, moving points, and smoothly deforming the
original dodecahedral (or whatever it is) mesh.
- 6/12/97: (later the same day) realized that the scope of the smooth deformation can be changed by changing the number of times the delta signal is smoothed. Added ability to manipulate this from within the program.

- The completed project code tarball.
- The README from the project code tarball, half-assedly converted to HTML.
- The version of STL I used, in a tarball.