About Research Teaching			Notice that most, if not all, of the final versions of these papers are copyrighted. Use these preprints at your own risk. Poisson-based Weight Reduction of Animated Meshes Landreneau E. and Schaefer S. To appear in Computer Graphics Forum, movie Abstract: While animation using barycentric coordinates or other automatic weight assignment methods has become a popular method for shape deformation, the global nature of the weights limits their use for real-time applications. We present a method that reduces the number of control points influencing a vertex to a user-specified number such that the deformations created by the reduced weight set resemble that of the original deformation. To do so we show how to set up a Poisson minimization problem to solve for a reduced weight set and illustrate its advantages over other weight reduction methods. Not only does weight reduction lower the amount of storage space necessary to deform these models but also allows GPU acceleration of the resulting deformations. Our experiments show that we can achieve a factor of 100 increase in speed over CPU deformations using the full weight set, which makes real-time deformations of large models possible. On the Parameterization of Catmull-Rom Curves Yuksel C., Schaefer S. and Keyser J. To appear in the 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling Abstract: The behavior of Catmull-Rom curves heavily depends on the choice of parameter values at the control points. We analyze a class of parameterizations ranging from uniform to chordal parameterization and show that, within this class, curves with centripetal parameterization contain properties that no other curves in this family possess. Researchers have previously indicated that centripetal parameterization produces visually favorable curves compared to uniform and chordal parameterizations. However, the mathematical reasons behind this behavior have been ambiguous. In this paper we prove that, for cubic Catmull-Rom curves, centripetal parameterization is the only parameterization in this family that guarantees that the curves do not form cusps or self-intersections within curve segments. Furthermore, we provide a formulation that bounds the distance of the curve to the control polygon and explain how globally intersection free Catmull-Rom curves can be generated using these properties. Simplification of Articulated Meshes Landreneau E. and Schaefer S. Computer Graphics Forum (Proceedings of Eurographics), Vol. 28, No. 2 (2009), pages 347-353, slides, movie Abstract: We present a method for simplifying a polygonal character with an associated skeletal deformation such that the simplified character approximates the original shape well when deformed. As input, we require a set of example poses that are representative of the types of deformations the character undergoes and we produce a multi-resolution hierarchy for the simplified character where all simplified vertices also have associated skin weights. We create this hierarchy by minimizing an error metric for a simplified set of vertices and their skin weights, and we show that this quartic error metric can be effectively minimized using alternating quadratic minimization for the vertices and weights separately. To enable efficient GPU accelerated deformations of the simplified character, we also provide a method that guarantees the maximum number of bone weights per simplified vertex is less than a user specified threshold at all levels of the hierarchy. Exact Evaluation of Limits and Tangents for Non-Polynomial Subdivision Schemes Schaefer S. and Warren J. Computer Aided Geometric Design, Vol. 25, No. 8 (2008), pages 607-620 Abstract: In this paper, we describe a method for exact evaluation of a limit mesh defined via subdivision and its associated tangent vectors on a uniform grid of any size. Other exact evaluation techniques either restrict the grids to have subdivision sampling and are, hence, exponentially increasing in size or make assumptions about the underlying surface being piecewise polynomial (Stam’s method is a widely used technique that makes this assumption). As opposed to Stam’s technique, our method works for both polynomial and non-polynomial schemes. The values for this exact evaluation scheme can be computed via a simple system of linear equation derived from the scaling relations associated with the scheme or, equivalently, as the dominant left eigenvector of an upsampled subdivision matrix associated with the scheme. To illustrate one possible application of this method, we demonstrate how to generate adaptive polygonalizations of a non-polynomial quad-based subdivision surfaces using our exact evaluation method. Our tessellation method guarantees a water-tight tessellation no matter how the surface is sampled and is quite fast. We achieve tessellation rates of over 33.5 million triangles/second using a CPU implementation. Streaming Surface Reconstruction Using Wavelets Manson J., Petrova G. and Schaefer S. Computer Graphics Forum (Proceedings of the Symposium on Geometry Processing), Vol. 27, No. 5 (2008), pages 1411-1420, slides, project page, cover image Abstract: We present a streaming method for reconstructing surfaces from large data sets generated by a laser range scanner using wavelets. Wavelets provide a localized, multiresolution representation of functions and this makes them ideal candidates for streaming surface reconstruction algorithms. We show how wavelets can be used to reconstruct the indicator function of a shape from a cloud of points with associated normals. Our method proceeds in several steps. We first compute a low-resolution approximation of the indicator function using an octree followed by a second pass that incrementally adds fine resolution details. The indicator function is then smoothed using a modified octree convolution step and contoured to produce the final surface. Due to the local, multiresolution nature of wavelets, our approach results in an algorithm over 10 times faster than previous methods and can process extremely large data sets in the order of several hundred million points in only an hour. G^2 Tensor Product Splines over Extraordinary Vertices Loop C. and Schaefer S. Computer Graphics Forum (Proceedings of the Symposium on Geometry Processing), Vol. 27, No. 5 (2008), pages 1373-1382, slides, cover image Abstract: We present a second order smooth filling of an n-valent Catmull-Clark spline ring with n biseptic patches. While an underdetermined biseptic solution to this problem has appeared previously, we make several advances in this paper. Most notably, we cast the problem as a constrained minimization and introduce a novel quadratic energy functional whose absolute minimum of zero is achieved for bicubic polynomials. This means that for the regular 4-valent case, we reproduce the bicubic B-splines. In other cases, the resulting surfaces are aesthetically well behaved. We extend our constrained minimization framework to handle the case of input mesh with boundary. Approximating Catmull-Clark Subdivision Surfaces with Bicubic Patches Loop C. and Schaefer S. ACM Transactions on Graphics, Vol 27, No. 1 (2008), pages 8:1-8:11, slides, movie Abstract: We present a simple and computationally efficient algorithm for approximating Catmull-Clark subdivision surfaces using a minimal set of bicubic patches. For each quadrilateral face of the control mesh, we construct a geometry patch and a pair of tangent patches. The geometry patches approximate the shape and silhouette of the Catmull-Clark surface and are smooth everywhere except along patch edges containing an extraordinary vertex where the patches are C^0. To make the patch surface appear smooth, we provide a pair of tangent patches that approximate the tangent fields of the Catmull-Clark surface. These tangent patches are used to construct a continuous normal field (through their cross-product) for shading and displacement mapping. Using this bifurcated representation, we are able to define an accurate proxy for Catmull-Clark surfaces that is efficient to evaluate on next-generation GPU architectures that expose a programmable tessellation unit. On the Smoothness of Real-Valued Functions Generated by Subdivision Schemes Using Nonlinear Binary Averaging Goldman R., Vouga E. and Schaefer S. Computer Aided Geometric Design, Vol. 26, No. 2 (2009), pages 231-242 Abstract: Our main result is that two point interpolatory subdivision schemes using C^k nonlinear averaging rules on pairs of real numbers generate real-valued functions that are also C^k. The significance of this result is the following consequence: Suppose that S is a subdivision algorithm operating on sequences of real numbers using linear binary averaging that generates C^m real-valued functions and Sbar is the same subdivision procedure where linear binary averaging is replaced everywhere in the algorithm by a C^n nonlinear binary averaging rule on pairs of real numbers; then the functions generated by the nonlinear subdivision scheme Sbar are C^k , where k = min(m, n). Non-uniform Subdivision for B-splines of Arbitrary Degree Schaefer S. and Goldman R. Computer Aided Geometric Design, Vol. 26, No. 1 (2009), pages 75-81, slides, slides Abstract: We present an efficient algorithm for subdividing non-uniform B-splines of arbitrary degree in a manner similar to the Lane-Riesenfeld subdivision algorithm for uniform Bsplines of arbitrary degree. Our algorithm consists of doubling the control points followed by d rounds of non-uniform averaging similar to the d rounds of uniform averaging in the Lane-Riesenfeld algorithm for uniform B-splines of degree d. However, unlike the Lane- Riesenfeld algorithm which follows most directly from the continuous convolution formula for the uniform B-spline basis functions, our algorithm follows naturally from blossoming. We show that our knot insertion method is simpler and more efficient than previous knot insertion algorithms for non-uniform B-splines. J-splines Rossignac J. and Schaefer S. Computer Aided Design, Vol 40, No. 10-11 (2008), pages 1024-1032 Abstract: Both the 4-point and the uniform cubic B-spline subdivisions double the number of vertices of a closed-loop polygon P^k and produce sequences of vertices f_j and b_j respectively. We study the J-spline subdivision scheme J_s, introduced by Maillot and Stam, which blends these two methods to produce vertices of the form v_j=(1–s)f_j + s b_j. Iterative applications of J_s yield a family of limit curves, the shape of which is parameterized by s. They include four-point subdivision curves (J_0), uniform cubic B-spline curves (J_1), and uniform quintic B-spline curves (J_1.5). We show that the limit curve is at least C^1 when –1.7<=s<=5.8, C^2 when 0<s<4, C^3 when 1<s<=2.8, and C^4 when s=3/2, even though 4-point yields only C^1 curves and cubic B-spline yields only C^2 curves. We generalize the J_s scheme to a two-parameter family J_{a,b} and propose data-dependent and data-independent solutions for computing values of parameters a and b that minimize various objective functions (distance to the control vertices, deviation from the control polygon, change in surface area, and popping when switching levels of subdivision in multi-resolution rendering). We extend the J-spline subdivision to open curves and to a smooth surface subdivision scheme for quad-meshes with arbitrary connectivity. Nonlinear Subdivision Through Nonlinear Averaging Schaefer S., Vouga E. and Goldman R. Computer Aided Geometric Design, Vol. 25, No. 3 (2008), pages 162-180, slides Abstract: We investigate a general class of nonlinear subdivision algorithms for functions of a real or complex variable built from linear subdivision algorithms by replacing binary linear averages such as the arithmetic mean by binary nonlinear averages such as the geometric mean. Using our method, we can easily create stationary subdivision schemes for Gaussian functions, spiral curves, and circles with uniform parametrizations. More generally, we show that stationary subdivision schemes for e^p(x), cos(p(x)) and sin(p(x)) for any polynomial or piecewise polynomial p(x) can be generated using only addition, subtraction, multiplication, and square roots. The smoothness of our nonlinear subdivision schemes is inherited from the smoothness of the original linear subdivision schemes and the differentiability of the corresponding nonlinear averaging rules. While our results are quite general, our proofs are elementary, based mainly on the observation that generic nonlinear averaging rules on a pair of real or complex numbers can be constructed by conjugating linear averaging rules with locally invertible nonlinear maps. In a forthcoming paper we show that every continuous nonlinear averaging rule on a pair of real or complex numbers can be constructed by conjugating a linear averaging rule with an associated continuous locally invertible nonlinear map. Thus the averaging rules considered in this paper are actually the general case. As an application we show how to apply our nonlinear subdivision algorithms to intersect some common transcendental functions. Exact Evaluation of Non-Polynomial Subdivision Schemes at Rational Parameter Values Schaefer S. and Warren J. Pacific Graphics 2007, pages 321-330, slides, movie, cover image Abstract: In this paper, we describe a method for exact evaluation of a limit mesh defined via subdivision on a uniform grid of any size. Other exact evaluation technique either restrict the grids to have subdivision sampling and are, hence, exponentially increasing in size or make assumptions about the underlying surface being piecewise polynomial (Stam's method is a widely used technique that makes this assumption). As opposed to Stam's technique, our method works for both polynomial and non-polynomial schemes. The values for this exact evaluation scheme can be computed via a simple system of linear equation derived from the scaling relations associated with the scheme or, equivalently, as the dominant left eigenvector of an upsampled subdivision matrix associated with the scheme. To illustrate one possible application of this method, we demonstrate how to generate adaptive polygonalizations of a non-polynomial quad-based subdivision surfaces using our exact evaluation method. Our method guarantees a water-tight tessellation no matter how the surface is sampled and is quite fast. We achieve tessellation rates of over 33.5 million triangles/second using a CPU implementation. Example-Based Skeleton Extraction Schaefer S. and Yuksel C. Eurographics Symposium on Geometry Processing 2007, pages 153-162, slides, movie, cover image Abstract: We present a method for extracting a hierarchical, rigid skeleton from a set of example poses. We then use this skeleton to not only reproduce the example poses, but create new deformations in the same style as the examples. Since rigid skeletons are used by most 3D modeling software, this skeleton and the corresponding vertex weights can be inserted directly into existing production pipelines. To create the skeleton, we first estimate the rigid transformations of the bones using a fast, face clustering approach. We present an efficient method for clustering by providing a Rigid Error Function that finds the best rigid transformation from a set of points in a robust, space efficient manner and supports fast clustering operations. Next, we solve for the vertex weights and enforce locality in the resulting weight distributions. Finally, we use these weights to determine the connectivity and joint locations of the skeleton. Manifold Dual Contouring Schaefer S., Ju T. and Warren J. Transactions on Visualization and Computer Graphics, Vol 13, No. 3 (2007), pages 610-619, slides Abstract: Dual Contouring is a feature-preserving iso-surfacing method that extracts crack-free surfaces from both uniform and adaptive octree grids. We present an extension of Dual Contouring that further guarantees that the mesh generated is a manifold even under adaptive simplification. Our main contribution is an octree-based, topology-preserving vertex clustering algorithm for adaptive contouring. The contoured surface generated by our method contains only manifold vertices and edges, preserves sharp features, and possesses much better adaptivity than those generated by other iso-surfacing methods under topologically safe simplification. A Unified, Integral Construction For Coordinates Over Closed Curves Schaefer S., Ju T. and Warren J. Computer-Aided Geometric Design 2007, Vol 24, No. 8-9 (2007), pages 481-493 slides Abstract: We propose a simple generalization of Shephard's interpolation to piecewise smooth, convex closed curves that yields a family of boundary interpolants with linear precision. Two instances of this family reduce to previously known interpolants: one based on a generalization of Wachspress coordinates to smooth curves and the other an integral version of mean value coordinates for smooth curves. A third instance of this family yields a previously unknown generalization of discrete harmonic coordinates to smooth curves. For closed, piecewise linear curves, we prove that our interpolant reproduces a general family of barycentric coordinates considered by Floater, Hormann and Kos that includes Wachspress coordinates, mean value coordinates and discrete harmonic coordinates. Barycentric Coordinates for Convex Sets Warren J., Schaefer S., Hirani A. and Desbrun M. Advances in Computational Mathematics, Vol 27, No. 3 (2007), pages 319-338 Abstract: In this paper we provide an extension of barycentric coordinates from simplices to arbitrary convex sets. Barycentric coordinates over convex 2D polygons have found numerous applications in various fields as they allow smooth interpolation of data located on vertices. However, no explicit formulation valid for arbitrary convex polytopes has been proposed to extend this interpolation in higher dimensions. Moreover, there has been no attempt to extend these functions into the continuous domain, where barycentric coordinates are related to Green’s functions and construct functions that satisfy a boundary value problem. First, we review the properties and construction of barycentric coordinates in discrete domain for convex polytopes. Next, we show how these concepts extend into the continuous domain to yield barycentric coordinates for continuous functions. We then provide a proof that our functions satisfy all the desirable properties of barycentric coordinates in arbitrary dimensions. Finally, we provide an example of constructing such barycentric functions over regions bounded by parametric curves and show how they can be used to perform freeform deformations. Image Deformation Using Moving Least Squares Schaefer S., McPhail T. and Warren J. ACM SIGGRAPH 2006, pages 533-540, slides Abstract: We provide an image deformation method based on Moving Least Squares using various classes of linear functions including affine, similarity and rigid transformations. These deformations are realistic and give the user the impression of manipulating real-world objects. We also allow the user to specify the deformations using either sets of points or line segments, the later useful for controlling curves and profiles present in the image. For each of these techniques, we provide simple closed-form solutions that yield fast deformations, which can be performed in real-time. Mean Value Coordinates for Closed Triangular Meshes Ju T., Schaefer S. and Warren J. ACM SIGGRAPH 2005, pages 561-566, slides Abstract: Constructing a function that interpolates a set of values defined at vertices of a mesh is a fundamental operation in computer graphics. Such an interpolant has many uses in applications such as shading, parameterization and deformation. For closed polygons, mean value coordinates have been proven to be an excellent method for constructing such an interpolant. In this paper, we generalize mean value coordinates from closed 2D polygons to closed triangular meshes. Given such a mesh P, we show that these coordinates are continuous everywhere and smooth on the interior of P. The coordinates are linear on the triangles of P and can reproduce linear functions on the interior of P. To illustrate their usefulness, we conclude by considering several interesting applications including constructing volumetric textures and surface deformation. A Geometric Construction of Coordinates for Convex Polyhedra using Polar Duals Ju T., Schaefer S., Warren J., Desbrun M. Eurographics Symposium on Geometry Processing 2005, pages 181-186, slides Abstract: A fundamental problem in geometry processing is that of expressing a point inside a convex polyhedron as a combination of the vertices of the polyhedron. Instances of this problem arise often in mesh parameterization and 3D deformation. A related problem is to express a vector lying in a convex cone as a non-negative combination of edge rays of this cone. This problem also arises in many applications such as planar graph embedding and spherical parameterization. In this paper, we present a unified geometric construction for building these weighted combinations using the notion of polar duals. We show that our method yields a simple geometric construction for Wachspress's barycentric coordinates, as well as for constructing Colin de Verdiere matrices from convex polyhedra---a critical step in Lovasz's method with applications to parameterizations. Subdivision Schemes and Attractors Schaefer S., Levin D., Goldman R. Eurographics Symposium on Geometry Processing 2005, pages 171-180, slides Abstract: Subdivision schemes generate self-similar curves and surfaces. Therefore there is a close connection between curves and surfaces generated by subdivision algorithms and self-similar fractals generated by Iterated Function Systems (IFS). We demonstrate that this connection between subdivision schemes and fractals is even deeper by showing that curves and surfaces generated by subdivision are also attractors, fixed points of IFS's. To illustrate this fractal nature of subdivision, we derive the associated IFS for many different subdivision curves and surfaces, including B-splines, piecewise Bezier, stationary four-point subdivision, Box-splines, Loop subdivision and Kobbelt's sqrt(3)-subdivision surfaces. Conversely, we shall show how to build subdivision schemes to generate traditional fractals such as the Sierpinski gasket and the Koch curve, and we demonstrate as well how to control the shape of these fractals by adjusting their control points. On C^2 Triangle/Quad Subdivision Schaefer S. and Warren J. ACM Transactions on Graphics, Vol 24, No. 1 (2005), pages 28-36, slides Abstract: In this paper we present a subdivision scheme for mixed triangle/quad meshes that is C^2 everywhere except for isolated, extraordinary points where the surface is C^1. The rules that we describe are the same as Stam/Loop's scheme except that we perform an unzippering pass prior to subdivision. This simple modification improves the smoothness along the ordinary triangle/quad boundary from C^1 to C^2 and creates a scheme capable of subdividing arbitrary meshes. Finally, we end with a proof based on Levin/Levin's joint spectral radius calculation to show our scheme is indeed C^2 along the triangle/quad boundary. Dual Marching Cubes: Primal Contouring of Dual Grids Schaefer S. and Warren J. Proceedings of Pacific Graphics 2004, pages 70-76, slides Abstract: We present a method for contouring an implicit function using a grid topologically dual to structured grids such as octrees. By aligning the vertices of the dual grid with the features of the implicit function, we are able to reproduce thin features without excessive subdivision required by methods such as Marching Cubes or Dual Contouring. Dual Marching Cubes produces a crack-free, adaptive polygonalization of the surface that reproduces sharp features. Our approach maintains the advantage of using structured grids for operations such as CSG while being able to conform to the relevant features of the implicit function yielding much sparser polygonalizations than has been possible using structured grids. Lofting Curve Networks using Subdivision Surfaces Schaefer S., Warren J. and Zorin D. Eurographics Symposium on Geometry Processing 2004, pages 105-116, slides Abstract: Lofting is a traditional technique for creating a curved shape by first specifying a network of curves that approximates the desired shape and then interpolating these curves with a smooth surface. This paper addresses the problem of lofting from the viewpoint of subdivision. In particular, we develop two new subdivision schemes; a univariate scheme that converges to a network of cubic splines and a modified Catmull-Clark scheme that lofts these curve networks. Near the curve network, these lofted subdivision surfaces are C^2 except for those points where three or more curves meet at which the surface is C^1 with bounded curvature. As a demonstration of these two methods, we have constructed an automatic system that quadrangulates these curve networks using a novel method and fairs the surfaces produced by our subdivision scheme. Smooth Subdivision of Tetrahedral Meshes Schaefer S., Hakenberg J. and Warren J. Eurographics Symposium on Geometry Processing 2004, pages 151-158, slides, cover image Abstract: We describe a new subdivision scheme for unstructured tetrahedral meshes. Previous tetrahderal schemes based on generalizations of box splines have encoded arbitrary directional preferences in their associated subdivision rules that were not reflected in tetrahderal base mesh. Our method avoids this choice of preferred directions resulting a scheme that is simple to implement via repeated smoothing. In an extended appendix, we analyze this tetrahedral scheme and prove that the scheme generates C^2 deformations everywhere except along edges of the tetrahedral base mesh. Along edges shared by four or more tetrahedra in the base mesh, we present strong evidence that the scheme generates C^1 deformations. A Factored Approach to Subdivision Surfaces Warren J. and Schaefer S. Computer Graphics & Applications, Vol. 24, No. 3 (2004), pages 74-81 Abstract: This tutorial explains how to implement several different subdivision schemes under a single, unified framework. Our discussion will illustrate Catmull-Clark subdivision for quadrilateral meshes, Loop subdivision for triangular meshes, and a newer combined subdivision scheme called Quad/Triangle subdivision that allows the inclusion of meshes with both quadrilateral and triangular faces. The algorithms that we explain do not require complicated data-structures or mesh traversal algorithms. Instead we focus on methods that illustrate the simplicity of the implementation. Finally, we end with a discussion on generating surfaces that are not smooth everywhere, but instead contain sharp crease curves. Teaching Computer Game Design and Construction Schaefer S. and Warren J. Computer-Aided Design 2004, Vol. 36(14), pages 1501-1510 Abstract: Computer gaming is a key component of the rapidly growing entertainment industry. While building computer games has typically been a commercial endeavor, we believe that designing and constructing a computer game is also a useful activity for educating students about geometric modeling and computer graphics. In particular, students are exposed to the practical issues surrounding topics such as geometric modeling, rendering, collision detection, character animation and graphical design. Moreover, building an advanced game provides students exposure to the real-world side of software engineering that they are typically shielded from in the standard computer class. In this paper, we describe our experiences with teaching a computer science class that focuses on designing and building the best game possible in the course of a semester. The paper breaks down a typical game into various components that are suited for individual student projects and discusses the use of modern graphical design tools such as Maya in building art for the game. We conclude with a rough timeline for developing a game during the course of a semester and review some of the lessons learned during the three years we have taught the class. Turtle Geometry in Computer Graphics and Computer Aided Design Goldman R., Schaefer S. and Ju T. Computer-Aided Design 2004, Vol. 36(14), pages 1471-1482 Abstract: LOGO is a programming language incorporating turtle graphics, originally devised for teaching computing to young children in elementary and middle schools. Here we advocate the use of LOGO to help introduce some of the basic concepts of computer graphics and computer aided design to undergraduate and graduate students in colleges and universities. We shall show how to motivate affine coordinates and affine transofmrations, fractal curves and iterated function systems, relaxation methods and subdivision scheme from elementary notions in turtle geometry and turtle programming. Recursive Turtle Programs and Iterated Affine Transformations Ju T., Schaefer S. and Goldman R. Computers and Graphics 2004, Vol. 28(6), pages 991-1004 Abstract: We provide a formal proof of equivalence between the class of fractals created by Recursive Turtle Programs (FTP) and Iterated Affine Transformations (IAT). We begin by reviewing RTP (a geometric interpretation of non-bracketed L-systems with a single production rule) and IAT (Iterated Function Systems restricted to affine transformations). Next, we provide a simple extension to RTP that generatlizes RTP from conformal transformations to arbitrary affine transformations. We then present constructive proofs of equivalence between the fractal geometry generated by RTP and IAT that yield conversion algorithms between these two methods. We conclude with possible extensions and a few open questions for future research. Adaptive Vertex Clustering Using Octrees Schaefer S. and Warren J. Proceedings of SIAM Geometric Design and Computing 2003, pages 491-500, slides Abstract: We present an adaptive vertex clustering approach to out-of-core simplification of polygonal meshes using a dynamic octree. Similar to uniform clustering, our technique utilizes quadratic error functions to position the mesh vertices; however, this new method can resolve vertices to arbitrary resolutions, which allows reproduction of extremely small details and more accurate simplifications. By sorting the vertices of the input mesh, our algorithm dynamically discovers portions of the mesh that are locally complete, which are then available for collapse when the octree grows too large. This adaptive octree is then used to cluster the vertices of the input to generate a simplified mesh. Finally, we show that our method generates the same tree that would be constructed with unbounded memory if our method is given a small amount of space in addition to the size of the output tree. Smooth Geometry Images Losasso F., Hoppe H., Schaefer S. and Warren J. Eurographics Symposium on Geometry Processing 2003, pages 138-145, slides Abstract: Previous parametric representations of smooth genus-zero surfaces require a collection of abutting patches (e.g. splines, NURBS, recursively subdivided polygons). We introduce a simple construction for these surfaces using a single uniform bi-cubic B-spline. Due to its tensor-product structure, the spline control points are conveniently stored as a geometry image with simple boundary symmetries. The bicubic surface is evaluated using subdivision, and the regular structure of the geometry image makes this computation ideally suited for graphics hardware. Specifically, we let the fragment shader pipeline perform subdivision by applying a sequence of masks (splitting, averaging, limit, and tangent) uniformly to the geometry image. We then extend this scheme to provide smooth level-of-detail transitions from a subsampled base octahedron all the way to a finely subdivided, smooth model. Finally, we show how the framework easily supports scalar displacement mapping. Dual Contouring: "The Secret Sauce" Schaefer S. and Warren J. Technical Report TR 02-408 Abstract: This paper provides several contributions related to dual contouring implicit data including solving rank deficient QEF's, reducing memory requirements, and performing fast polygon updates during CSG. First, we describe our method for solving QEF's and provide a method using mass points that improves vertex placement in the rank deficient case. This improvement leads to a technique for handling vertex placement in the presence of non-manifold sign configurations. Next, we provide a method for reducing the space requirements for storing the implicit data needed to generate the contour. Finally, we describe our method for storing the geometry data in a format suitable for fast display on modern graphics hardware as well as techniques for updating the data-structure in constant time during CSG operations. Convex Contouring of Volumetric Data Ju T., Schaefer S. and Warren J. The Visual Computer, Vol. 19, No. 7-8, 2003, pages 513-525 Abstract: In this paper we present a fast, table-driven isosurface extraction technique on volumetric data. Unlike Marching Cubes or other cell-based algorithms, the proposed polygonization generates convex negative space inside individual cells, enabling fast collision detection on the triangulated isosurface. In our implementation, we are able to perform over 2 million point classifications per second. The algorithm is driven by an automatically constructed look-up table that stores compact decision trees by sign configurations. The decision trees determine triangulations dynamically by values at cell corners. Using the same technique, we can perform fast, crack-free multi-resolution contouring on nested grids of volumetric data. The method can also be extended to extract isosurfaces on arbitrary convex, space-filling polyhedra. A Factored Interpolatory Subdivision Scheme for Surfaces of Revolution Schaefer S. Master's Thesis, Rice University 2003 slides Abstract: We present a new non-stationary, interpolatory subdivision scheme capable of producing circles and surfaces of revolution and in the limit is C^1. First, we factor the classical four point interpolatory scheme of Dyn et al. into linear subdivision plus differencing. We then extend this method onto surfaces by performing bilinear subdivision and a generalized differencing pass. This extension also provides the ability to interpolate curve networks. On open nets this simple, yet efficient, scheme reproduces the curve rule, which allows C^0 creases by joining two patches together that share the same boundary. Our subdivision scheme also contains a tension parameter that changes with the level of subdivision and gives the scheme its non-stationary property. This tension is updated using a simple recurrence and, chosen correctly, can produce exact surfaces of revolution. Dual Contouring of Hermite Data Ju T., Losasso F., Schaefer S. and Warren J. ACM SIGGRAPH 2002, pages 339-346, slides, movie Abstract: This paper describes a new method for contouring a signed grid whose edges are tagged by Hermite data (i.e; exact intersection points and normals). This method avoids the need to explicitly identify and process "features" as required in previous Hermite contouring methods. We extend this contouring method to the case of multi-signed functions and demonstrate how to model textured contours using multi-signed functions. Using a new, numerically stable representation for quadratic error functions, we develop an octree-based method for simplifying these contours and their textured regions. We next extend our contouring method to these simplified octrees. This new method imposes no constraints on the octree (such as being a restricted octree) and requires no "crack patching". We conclude with a simple test for preserving the topology of both the contour and its textured regions during simplification. A Factored Interpolatory Subdivision Scheme for Quadrilateral Surfaces Schaefer S. and Warren J. Curves and Surface Fitting: Saint Malo 2002, pages 373-382 Abstract: This paper presents a new C^1 interpolatory subdivision scheme for quadrilateral meshes based on the idea of factoring a complex scheme into several simpler passes. To illustrate this point we first factor the well-known four point rule for interpolatory curve subdivision into linear subdivision followed by a simple differencing pass. This subdivision method is then extended to surfaces by generalizing each of these passes to quadrilateral meshes (including those with extraordinary vertices). Finally, we demonstrate that this extension can also be interpreted as defining a subdivision scheme for interpolating curve networks. A subdivision scheme for hexahedral meshes Bajaj C., Schaefer S., Warren J. and Xu G. The Visual Computer, Vol. 18, 2002, pages 409-420 Abstract: In a landmark paper, Catmull and Clark described a simple generalization of the subdivision rules for bi-cubic B-splines to arbitrary quadrilateral surface meshes. This subdivision scheme has become a mainstay of surface modeling systems. Joy and MacCracken described a generalization of this surface scheme to volume meshes. Unfortunately, little is known about the smoothness and regularity of this scheme due to the complexity of the subdivision rules. This paper presents an alternative subdivision scheme for hexahedral volume meshes that consists of a simple split and average algorithm. Along extraordinary edges of the volume mesh, the scheme provably converges to a smooth limit volume. At extraordinary vertices, the authors supply strong experimental evidence that the scheme also converges to a smooth limit volume. The scheme automatically produces reasonable rules for non-manifold topology and can easily be extended to incorporate boundaries and embedded creases expressed as Catmull-Clark surfaces and B-spline curves.