Subdivide 2.0

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

February 2001

introduction

download

package structure

compilation

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,

Version 2.0

Subdivide 2.0 is a complete rewrite of the original subdivision code. The previous version Subdivide 1.0 is still available, but the code is not maintained anymore. The improvements of Version 2.0 include greater modularity and higher performance of the subdivision engine. This version only provides a minimal user interface which can be extended and adopted for particular applications. We refer to Subdivide 1.0 for a subdivision demo with a more comfortable user interface.

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.

DOWNLOAD

Subdivide 2.0 is currently available as C++ source code tested on various platforms and executables for windows (win98, win nt and win2k).

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 subdivide20/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 subdivide20/examples
  • qvlib is a VRML parser.

The libraries and examples can be found in the following directories:
subdivide20/subdivide/src Source code for libsub. Note that most of the work is actually done by template classes in subdivide20/subdivide/template.
subdivide20/subdivide/viewer Source code for libviewer.
subdivide20/subdivide/template Header files and templates shared by libsub and libviewer.
subdivide20/subdivide/includeHeader files defining the interface for the libraries.
subdivide20/subdivide/examplesCode for loopsub, ccsub, subviewer.
subdivide20/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

Note that Subdivision 2.0 requires 24-bit colors to work correctly.

To build everything on IRIX or Linux, run one of the following commands in the directory subdivide20/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 subdivide20/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: subdivide20\winnt\Debug
  • release: subdivide20\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.

Under Windows, it is easy to test the viewer by simply dragging a mesh to the executable subviewer.exe, one might try the mesh pipes.wrl which is located at subdivide20/subdivide/meshes/open_meshes/pipes.wrl.

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.

Currently, Subdivide 2.0 does not support to drag control points of the mesh .

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     .
	}

}