Multi-Res Modeling Group People Research


Teaching
Publications Software
Multi-Res Modeling Group Multi-Res Modeling Group


Introduction
This code illustrates a quadtree implementation of dual quadrilateral subdivision schemes. It supports primarily Doo-Sabin and a new Bi-Quartic scheme invented by Zhang, Schröder and Zorin. Other schemes for dual quadrilateral subdivision can be added simply by editing the proper filter coefficients. There are currently 3 sets of such coefficients compiled into the code: Catmull and Clark's variant of the Doo-Sabin scheme, the Midedge variant of Habib and Warren and the new Bi-Quartic scheme which is based on a repeated averaging approach.

The code consists of two tools: mfilter and dual. mfilter supports the Doo-Sabin and Bi-Quartic schemes only and performs a single, uniform subdivision step. Cascading calls to it one can repeatedly subdivide an input mesh. The dual code supports multiple levels of subdivision including adaptive subdivision. It also supports the Midedge scheme. This support comes at the cost of placing further restrictions on the input (see below).

The main focus in this code was on simplicity so that it may serve as an educational tool for those who want to learn more about subdivision. Consequently we have favored simplicity over completeness in our implementation. For example, there are no feature based subdivision rule modifications included in the code. Boundaries have no special crease rules, etc. Such treatments can all be added, and would be included in a more complete code, but they also make the code harder to read for beginners. We included one special capability: adaptive subdivision. The subdivision part of this is easy, but the code which generates triangulated output for an adaptive dual subdivision is extremely nasty. We included it anyway, since adaptivity is so important in practice.

There are a number of properties the input meshes must satisfy:
  • The input mesh must be a topological 2-manifold. This means, any edge must have either 1 or 2 faces incident on it and every vertex must have a 1-ring of neighbors which is non-empty and has a single connected component. If any of these conditions are violated the input reader will throw an assertion. Why this limitation? Subdivision is not well defined for non-manifold meshes. One can convert any non-manifold mesh into a manifold mesh through topological replication of edges and vertices. This is rarely what the user wants, so we stayed away from this. This requirement applies to both mfilter and dual.
  • For the dual code the input mesh must have vertices of valence 4 (interior, concave corner), 2 (corner), 3 (smooth boundary) only. This is so that the implementation can use quadtrees for the organization of control points from the very beginning. Additionally when using the Bi-Quartic subdivision scheme all vertices must satisfy the condition that no more than one face incident on a vertex may have valence other than 4. Neither of these limitations are necessary for subdivision to work, but they simplify the code considerably. If you violate these conditions the code will through an assertion failure. An arbitrary 2-manifold mesh can always be converted to satisfy these requirements by running it through mfilter once (all vertices valence 4) or twice (no more than one face incident on a given vertex with valence other than 4).


Package Structure
The whole package consists of a number of directories and targets. The targets are
  • dual -- implementation of dual quadrilateral subdivision on valence-4 meshes;
  • qvlib -- A library for reading IV/WRL files;
  • mfilter -- a tool to convert a mesh into a valence-4 mesh with the Doo-Sabin or Bi-Quartic scheme. Alternatively, it can also be used as a uniform subdivision program.
These tools and their respective code can be found in the directories
  • ./quad -- source code for dual quadrilateral subdivision;
  • ./qvlib -- source code of QvLib;
  • ./meshfilter -- source code for the single level subdivision code;
The code was developed on SGI machines, but we have made an effort to ensure it works equally well under Windows. In particular the code is known to compile successfully under
  • IRIX 6.5, MIPSpro 7.2.1 Compilers
  • IRIX 6.5, g++/gcc version 2.8.1
  • Windows NT, Visual Studio 6.0

UNIX:

Every sub-project has Makefiles for SGI CC and the gnu tools. They are named Makefile.CC and Makefile.gcc respectively. Since dual and mfilter depend on qvlib, when either is compiled, qvlib will be compiled as well. Because the different compilers work differently it is recommended that one always start with a make clean before making the targets themselves. For CC use:

% make -f Makefile.CC

while g++/gcc uses:

% make -f Makefile.gcc

Windows:

Both the quad and meshfilter projects have Win32 subdirectories which contain the file win32.dsw Open this file in Microsoft Visual Studio 6.0. The compiler will create executables in the Release or Debug subdirectories depending on your target. For optimal performance, it is recommended to use the release target.

The process of compilation takes two steps: First the qvlib library is built and than the compiler automatically switches to built the main project.

Please note that the project will not build under Visual Studio 5.0



Invocation
% dual <level> <DS|ME|BIQ> [epsilon]
level - specify the maximum number of levels to subdivide
DS - Catmull-Clark variant of the Doo-Sabin scheme
ME - Habib/Warren variant of the Midedge scheme
BIQ - Bi-Quartic scheme
epsilon - optional. If positive, controls an error criterion for adaptive subdivision

Input: IV format input is expected on stdin. The input mesh should be represented by SoCoordinate3 nodes and SoIndexedFaceSet nodes. Every vertex in the input mesh is expected to have valence 4, except those on the boundary. A boundary vertex could be valence 2, 3, or 4. If a mesh does not meet the valence requirement, it should be manipulated by mfilter before getting passed to dual.

Output: IV format output goes to stdout. The output mesh is represented by a SoCoordinate3 node and a SoIndexedFaceSet node.

% mfilter <DS|BIQ>

DS - Catmull-Clark variant of the Doo-Sabin scheme
BIQ - Bi-Quartic scheme

Input: IV format input is expected on stdin. The input mesh should be represented by SoCoordinate3 and SoIndexedFaceSet nodes. The requirement on the input mesh is that it be 2-manifold (see the comments in the the introduction)

Output: IV format output goes to stdout. The output mesh is a mesh represented by a SoCoordinate3 node and a SoIndexedFaceSet node.



Examples
Here are a few example invocations to get you started with the sample models that we included. Note that these examples assume that dual, mfilter, and the iv input files are in the current directory. The iv files can be found in the quad/iv directory.
  • Doo-Sabin uniformly to level 3
    dual 3 DS < k9.iv | ivview
  • Same thing but adaptively. Maximum depth 5 error criterion 0.01
    dual 5 DS 0.01 < k9.iv | ivview
  • Different subdivision methods to compare the smoothness
    dual 5 ME 0.01 < k9.iv | ivview
    dual 5 BIQ 0.01 < k9.iv | ivview
  • The cube needs to be subdivided once first for DS
    mfilter DS < cube.iv | dual 3 DS | ivview
    mfilter BIQ < cube.iv | dual 3 BIQ | ivview
  • The pipe
    mfilter DS < pipe.iv | dual 3 DS | ivview
    mfilter BIQ < pipe.iv | dual 3 BIQ |
    ivview
  • This also works adaptively
    mfilter DS < pipe.iv | dual 3 DS 0.03 | ivview
    When doing BIQ adaptively you'll notice that the boundaries are not perfect. This is fixable, but more complicated and we left it out of this implementation.

  • Finally the head example. This is best done adaptively
    mfilter DS < head.iv | dual 5 DS 0.03 | ivview
    you can run BIQ on this, but it is too smooth to look good.

  • When running BIQ mode you may have to do 2 subdivision steps with mfilter first. The condition that dual places on its input is that all vertices have valence 4 AND at most one of the incident faces has valence other than 4. For some meshes (exercise: what type?) this requires 2 subdivision steps. For example
    mfilter BIQ < dodeca.iv | mfilter BIQ | dual 3 BIQ | ivview
  • As long as you do uniform subdivision only, you can just use mfilter
    mfilter DS < head.iv | mfilter DS | mfilter DS | mfilter DS | ivview
    Once you want adaptivity you'll need dual to do the work for you.


Notes
Here are a few notes about the code that go beyond our comments in the introduction.

Adaptivity When running dual in adaptive mode the output meshes are triangulations. Thus they are not suitable for input to dual. More interestingly the triangulation code writes out a mesh which is dual to the dual mesh, i.e., what we would otherwise call a primal mesh. The vertices of the adaptive meshes are centroids of the subdivision mesh faces. For Doo-Sabin and Midedge centroids are samples of the limit surface! The adaptivity is controlled by an error criterion which is quite simple minded in the present implementation and you are encouraged to look in the code to see how it is done and maybe add a different error criterion. Basically one wants to use a measure of the local flatness (or curvature) to stop subdividing. Fancier versions do this with respect to a given view point, for example in interactive applications. When no epsilon is given the code automatically writes out a quad mesh which is suitable as input to dual.

What gets written out? The output produced by mfilter are the control points of the next finer level of subdivision. These points are never on the limit surface, they just approach it. Additionally the boundaries shrink. For Doo-Sabin and Midedge they shrink by approximately half the outermost layer of control polygons in the limit. This is so because for these schemes the limit surface interpolates the centroids of the control mesh faces. For the Bi-Quartic scheme one looses approximately one and one-half layers from the boundary in the limit. Unfortunately the Bi-Quartic scheme does not have the simple property that the limit surface interpolates centroids. The mfilter code works this way at boundaries. The dual code actually switches to the Doo-Sabin scheme near the boundary when using the Bi-Quartic scheme to avoid this excessive shrinkage. This leads to a mixture of Doo-Sabin (near the boundary) and Bi-Quartic in the interior in these cases. Whether that's preferable over just stronger shrinkage is debatable and depends on the application. Because of this switching of methods near the boundary adaptive subdivision with boundaries which uses the Bi-Quartic scheme can have slight unevenness near the boundary.



Acknowledgements
The mfilter and dual codes were written primarily by Jianhui Zhang and Peter Schröder. The code contains material contributed by Denis Zorin and Wim Sweldens. It has also benefitted greatly from discussions with Nathan Litke, Igor Guskov, and Andrei Khodakovsky. The package uses qvlib written by Paul S. Strauss of Silicon Graphics and modified by Henning Biermann to support more vrml nodes and fileio.


Files
All files come in a single compressed tar archive. Just unroll it and you should find the above described directory hierarchy. Bug reports, praises, complaints, etc. should be sent to Peter Schröder.



Copyright © 2000 Peter Schröder