## Subdivide 2.0

### Henning Biermann, Denis Zorin
biermann@cs.nyu.edu, dzorin@mrl.nyu.edu
Media Research Lab, NYU

### April 2000

introduction installation tests usage file format | ### INTRODUCTION This software demonstrates algorithms for piecewise smooth subdivision surfaces described in the paper "Piecewise Smooth Subdivision Surfaces with Normal Control" by H. Biermann, A. Levin and D. Zorin. Two subdivision schemes, based on Loop and Catmull-Clark subdivision, are implemented. We have extended the classical Loop and Catmull-Clark schemes by adding rules to handle correctly a number of surface features: convex and concave corners on the boundary and on creases; extraordinary vertices on the boundary and on creases; prescribed normals at vertices. We will refer to these schemes as extended Loop and Catmull-Clark schemes. The code includes a minimal user interface for viewing control meshes and subdivision surfaces and changing mesh tags. The input to the code is a mesh description in VRML format, #### License `Subdivide` is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. #### Acknowledgments Subdivide uses the following code: GLUT, the OpenGL Utility Toolkit, by Mark Kilgard, a system independent windowing toolkit. GLUT is not included in the distribution; if it is not installed on your computer, you can obtain the source or binaries from the GLUT Home Page. QvLib. A VRML parser by Paul S. Strauss of Silicon Graphics. (Extended to handle user defined nodes correctly). Our user interface uses arcball, a general purpose 3-D rotation controller described by Ken Shoemaker in the Graphics Interface '92 Proceedings. Complete source code appears in Graphics Gems IV pp. 175-192. Our arcball implementation is based on the original code . We are very grateful to Daniel Kristjiansson and Jianbo Peng for their help with preparing this code for release. ### PACKAGE STRUCTURE The package consists of two main libraries, 3 sample programs, and an auxiliary library, `qvlib`. Interface to the main libraries is defined by the header files in the directory `../subdivide/include`. `libsub` contains classes for our versions of Catmull-Clark and Loop subdivision surfaces. To use these classes, the code has to be compiled with `qvlib` `libviewer` contains subdivision surface classes extended with rendering and interaction capabilities, and a simple viewer class to support interaction. `loopsub` is an extended Loop subdivision surface filter; it reads a file with a tagged mesh and produces an output file containing the subdivided mesh. It uses only `libsub` and `qvlib`. `ccsub` is a similar filter for extended Catmull-Clark surfaces. `subviewer` is an example showing how to use the viewer class and subdivision surface classes (both extended Loop and Catmull-Clark) with rendering and manipulation support from `libviewer`. This library requires linking with `qvlib`, `OpenGL` or `Mesa` libraries, and `GLUT`. Note that the Makefiles assume that these libraries are found in the default library path. If they are in nonstandard locations, you may have to modify the Makefiles in the directory `../examples` `qvlib` is a VRML parser. The libraries and examples can be found in the following directories:
`../subdivide/src` | Source code for `libsub.` Note that most of the work is actually done by template classes in `../subdivide/template.`
`../subdivide/viewer` | Source code for `libviewer.`
`../subdivide/template` | Header files and templates shared by `libsub` and `libviewer`.
`../subdivide/include` | Header files defining the interface for the libraries.
`../subdivide/examples` | Code for `loopsub`, `ccsub`, `subviewer.`
`../subdivide/meshes` | Several sample tagged meshes in the VRML format with additional nodes described below.
Each directory contains a README file briefly describing the contents of each file. ### COMPILING The Source code has been developed and tested under IRIX 6.5, MIPSpro Compilers: Version 7.2.1 and 7.3. IRIX 6.5, gcc version 2.95.2. Red Hat Linux, gcc-egcs version 2.91.66. Windown NT, Visual Studio 6.0 To build everything on IRIX or Linux, run one of the following commands in the directory `../subdivide`
    % make -f Makefile.CC
    % make -f Makefile.gcc
    % make -f Makefile.linux
The makefiles with extension `.CC` work with SGI MIPSPro compiler, those with extension `.gcc` work with `gcc 2.8.1 on IRIX 6.5, and those with extension `linux` work with `gcc-egcs 2.91.66` on Red hat Linix.` The makefiles assume that the GLUT library is installed in a standard location. If it is not, `subviewer` will not compile, unless you modify the makefile in `examples`, to include the path to `libglut` as a linking option, and all makefiles in `src`, `viewer` and `examples` to include the path to `glut.h` as a compile option. For Microsoft Visual Studio 6.0, there are several project files in the directory `../subdivide/winnt`. To compile, open the work space called `All.dsw` and build the release or debug version of the examples `ccsub`, `loopsub` and `subviewer`, The executables are placed in the subdirectories: debug: `.\winnt\Debug` release: `.\winnt\Release` ### TESTING A number of test meshes are contained in subdirectories of `meshes`. The script `testscript` subdivides them and writes them to corresponding output directories. The script `testscript` works only under Unix. ### USAGE The filters `loopsub` and `ccsub` take three arguments: the input file name, the output file name, and the subdivision depth. For example,
    ccsub bunny.wrl cube-out.wrl 3
subdivides the mesh contained in the file `bunny.wrl` 3 times using extended Catmull-Clark subdivision, and places the result into `bunny-out.wrl`. The program `subviewer` is interactive. It takes a single command line argument, the name of the file containing a mesh, and displays two windows, one showing the result of applying the extended Catmull-Clark scheme to the mesh and the other the result of applying the extended Loop scheme to the same mesh. The user interface has two modes: picking and examination. Picking allows one to select edges, vertices and sectors and to apply, change and remove the tags. In the examination mode, the arcball is used to change the camera position with respect to the mesh. Spacebar is used to switch between the two modes. In the examination mode, drag with the left mouse button pressed to rotate the surface, drag with the middle button pressed to translate it in a plane parallel to the screen, and with the left to move it perpendicular to the screen. For a two-button mouse use Alt+left mouse button instead of the middle button. The user can increase the subdivision level by pressing `d`, and write out the subdivided meshes by pressing `s` in the active window. The mesh with tags can be written with key `w`. Pressing `o` cycles between three different display modes: control mesh and subdivided mesh together, only subdivided mesh, and only control mesh. In the picking mode, vertices, edges and sectors are selected with left mouse click. Selected elements are highlighted in green. The user interface supports the following operations: Tagging the toplevel mesh: Left click on an edge toggles the edge tag (smooth/crease edge); crease edges are shown in blue. Left click on a vertex toggles the vertex tag where applicable (smooth vertex/corner). Corner vertices are shown in red. Left click on a sector: select sector, click again to toggle tag (convex/concave at corner vertices). Convex corner sectors are shown in blue, concave corner sectors are shown in orange. Modifying flatness and theta parameters: when a vertex is selected, the flatness and theta parameters can be modified at this vertex using up/down and left/right arrows respectively. ### FILE FORMAT The program reads and writes files in VRML 1.0/Inventor format, and the files are compatible with any VRML viewer. However, we use several user-defined nodes, which can be interpreted only by our software. These nodes conform to the VRML standard for extension nodes, and any standard-compliant software should ignore them. The layout of a tagged mesh description is shown below. The mesh includes a conventional `IndexedFaceSet` definition and several custom nodes describing different types of tags and tag parameters: `CornerVertex`, `CreaseVertex`, `DartVertex`, and `Sector`. In addition an `IndexedLineSet` is used to enumerate crease edges. The following nodes are just lists of different types of tagged vertices: `CornerVertex,` `CreaseVertex`, and `DartVertex`. Each of these nodes has a single field `vertexIndex`, an array of indices of tagged vertices of this type. Additionally, we provide parameters for surface sectors, that is, sequences of top-level faces adjacent to a vertex, starting and ending with a crease. The node `Sector` contains several parameters for a specific sector, given by the following fields. There may be several nodes of this type. `faceIndex` and `vertexIndex`: The sector is identified by this face/vertex pair. There are in general many ways of referring to the same sector, as we can take any face contained in it. The vertex indexed used here is not the vertex index in the `Coordinate3` node: it is the vertex number inside the face. For example, the fields `faceIndex 77` and `vertexIndex 2`, refer to the second vertex of face number `77` as listed in the `indexedFaceSet`. `sectorTag`: one of `0, 1, 2` indicating whether the sector is untagged, convex or concave. Corner vertices require either convex or concave tags. `flatness`: number in the range `[0, 1]`, controlling the shape of the surface. Reasonable choices are: `0.5` at concave corners and `0` otherwise. `theta`: only used at corner vertices. A number in the range `(0, pi)` for convex corners, and `(pi, 2pi)` for concave corners. Reasonable choices are `pi/2` and `3pi/2` respectively. `normal`: the prescribed normal direction, `0 0 0` if no normal is prescribed. `normalT`: a number in the range `[0, 1]` controlling how fast the normals of faces of the mesh converge to the prescribed limit normal. The following example shows the general file structure. We omit the actual values for the fields:
    #VRML V1.0 ascii
    Separator {
    	Coordinate3 {
    		point [ ... ]
            }

    	IndexedFaceSet {
    		coordIndex [ ... ]
            }

    	DEF creaseEdge IndexedLineSet {
    		coordIndex [ ... ]
            }

    	CornerVertex {
    		fields [
    			MFLong vertexIndex,
    		]
    		vertexIndex [ ... ]
    	}

    	CreaseVertex {
    		fields [
    			MFLong vertexIndex,
    		]
    		vertexIndex [ ... ]
            }

    	DartVertex {
    		fields [
    			MFLong vertexIndex,
    		]
    		vertexIndex [ ... ]

    	}

    	Sector {
    		fields [
    			SFLong faceIndex,
    			SFLong vertexIndex,
    			SFLong sectorTag,
    			SFFloat flatness,
    			SFFloat theta,
    			SFVec3f normal,
    			SFFloat normalT,
    		]
    		faceIndex   ...
    		vertexIndex ...
    		sectorTag   ...
    		flatness    ...
    		theta       ...
    		normal      ...
    		normalT     .
    	}

    }