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. Low Rank Matrix Approximation for 3D Geometry Filtering Lu X., Schaefer S., Luo J., Ma L., and Ying H. To appear in IEEE Transactions on Visualization and Computer Graphics. Abstract: We propose a robust normal estimation method for both point clouds and meshes using a low rank matrix approximation algorithm. First, we compute a local isotropic structure for each point and find its similar, non-local structures that we organize into a matrix. We then show that a low rank matrix approximation algorithm can robustly estimate normals for both point clouds and meshes. Furthermore, we provide a new filtering method for point cloud data to smooth the position data to fit the estimated normals. We show the applications of our method to point cloud filtering, point set upsampling, surface reconstruction, mesh denoising, and geometric texture removal. Our experiments show that our method generally achieves better results than existing methods. A Family of Barycentric Coordinates for Co-Dimension 1 Manifolds with Simplicial Facets First Best Paper Award Yan Z. and Schaefer S. Computer Graphics Forum (Proceedings of the Symposium on Geometry Processing), Vol. 38, No. 5, (2019), pp. 75-83. Abstract: We construct a family of barycentric coordinates for 2D shapes including non-convex shapes, shapes with boundaries, and skeletons. Furthermore, we extend these coordinates to 3D and arbitrary dimension. Our approach modifies the construction of the Floater-Hormann-Kos family of barycentric coordinates for 2D convex shapes. We show why such coordinates are restricted to convex shapes and show how to modify these coordinates to extend to discrete manifolds of co-dimension 1 whose boundaries are composed of simplicial facets. Our coordinates are well-defined everywhere (no poles) and easy to evaluate. While our construction is widely applicable to many domains, we show several examples related to image and mesh deformation. Circle Reproduction with Interpolatory Curves at Local Maximal Curvature Points Yan Z., Schiller S. and Schaefer S. Computer Aided Geometric Design, Vol. 72, (2019), pp. 98-110. Abstract: We present a piece-wise rational, quadratic, interpolatory curve that is able to reproduce circles and other elliptical or hyperbolic shapes. The curve is curvature continuous except at infection points and points of local maximum curvature appear only at control points and nowhere else. The local maximum curvature property ensures that users have direct control over salient points of the curve, and users can control if and where features such as cusps and loops are generated. To construct the desired curve, we formulated an energy that encodes the desired properties to optimize using a boxed constrained optimization. We provide an efficient algorithm for choosing an initial guess close to the solution to accelerate convergence. In addition, we show how to automatically choose the rational weights of the curve as part of the optimization to reproduce shapes such as circles. Multi-Sided Patches via Barycentric Coordinates Schaefer S. This is a pre-print version of Chapter 8 in Generalized Barycentric Coordinates in Computer Graphics and Computational Mechanics. Eds. Hormann, K. and Sukumar N. CRC Press 2017. Abstract: In this chapter, we explore the deep connection between barycentric coordinates and higher order parametric representations of curves, surfaces, volumes in arbitrary dimension. In the case of curves, these curves are known as Bezier curves, which are used in applications from font representations to controlling animations. The extension to convex surface patches, called S-Patches, is more recent. As originally proposed, S-Patches were parametric, multi-sided surface patches restricted to convex domains. However, these restrictions were more of a function of the limited set of generalized barycentric coordinates, namely Wachspress coordinates, available at that time. Today we have generalized barycentric coordinate functions that do not require convexity and extend to arbitrary dimension. Hence, we will investigate S-Patches within their full generality afforded by modern barycentric coordinates with generalized domains and in arbitrary dimension. Simplicial Complex Augmentation Framework for Bijective Maps Jiang, Z., Schaefer S., and Panozzo D. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia), Vol. 36, No. 6, (2017), pp. 186:1-186:9 Abstract: Bijective maps are commonly used in many computer graphics and scientific computing applications, including texture, displacement, and bump mapping. However, their computation is numerically challenging due to the global nature of the problem, which makes standard smooth optimization techniques prohibitively expensive. We propose to use a scaffold structure to reduce this challenging and global problem to a local injectivity condition. This construction allows us to benefit from the recent advancements in locally injective maps optimization to efficiently compute large scale bijective maps (both in 2D and 3D), sidestepping the need to explicitly detect and avoid collisions. Our algorithm is guaranteed to robustly compute a globally bijective map, both in 2D and 3D. To demonstrate the practical applicability, we use it to compute globally bijective single patch parametrizations, to pack multiple charts into a single UV domain, to remove self-intersections from existing models, and to deform 3D objects while preventing self-intersections. Our approach is simple to implement, efficient (two orders of magnitude faster than competing methods), and robust, as we demonstrate in a stress test on a parametrization dataset with over a hundred meshes. k-Curves: Interpolation at Local Maximum Curvature Yan Z., Schiller S., Wilensky G., Carr N., and Schaefer S. ACM Transactions on Graphics (Proceedings of SIGGRAPH), Vol. 36, No. 4, (2017), pp. 129:1-129:7, slides Abstract: We present a method for constructing almost-everywhere curvature-continuous, piecewise-quadratic curves that interpolate a list of control points and have local maxima of curvature only at the control points. Our premise is that salient features of the curve should occur only at control points to avoid the creation of features unintended by the artist. While many artists prefer to use interpolated control points, the creation of artifacts, such as loops and cusps, away from control points has limited the use of these types of curves. By enforcing the maximum curvature property, loops and cusps cannot be created unless the artist intends for them to be. To create such curves, we focus on piecewise quadratic curves, which can have only one maximum curvature point. We provide a simple, iterative optimization that creates quadratic curves, one per interior control point, that meet with G2 continuity everywhere except at inflection points of the curve where the curves are G1. Despite the nonlinear nature of curvature, our curves only obtain local maxima of the absolute value of curvature only at interpolated control points. Isometry-Aware Preconditioning for Mesh Parameterization Third Best Paper Award Claici S., Bessmeltsev M., Schaefer S., and Solomon J. Computer Graphics Forum (Proceedings of the Symposium on Geometry Processing), Vol. 36, (2017), pp. 37-47 Abstract: This paper presents a new preconditioning technique for large-scale geometric optimization problems, inspired by applications in mesh parameterization. Our positive (semi-)definite preconditioner acts on the gradients of optimization problems whose variables are positions of the vertices of a triangle mesh in R2 or of a tetrahedral mesh in R3, converting localized distortion gradients into the velocity of a globally near-rigid motion via a linear solve. We pose our preconditioning tool in terms of the Killing energy of a deformation field and provide new efficient formulas for constructing Killing operators on triangle and tetrahedral meshes. We demonstrate that our method is competitive with state-of-the-art algorithms for locally injective parameterization using a variety of optimization objectives and show applications to two- and three-dimensional mesh deformation. Image Structure Retrieval via L0 Minimization Sun Y., Schaefer S., and Wang W. Transactions on Visualization and Computer Graphics, Vol. 24, No. 7, (2017), pp. 2129-2139 Abstract: Retrieving salient structure from textured images is an important but difficult problem in computer vision because texture, which can be irregular, anisotropic, non-uniform and complex, shares many of the same properties as structure. Observing that salient structure in a textured image should be piece-wise smooth, we present a method to retrieve such structures using an L0 minimization of a modified form of the relative total variation metric. Thanks to the characteristics shared by texture and small structures, our method is effective at retrieving structure based on scale as well. Our method outperforms state-of-art methods in texture removal as well as scale-space filtering. We also demonstrate our method's ability in other applications such as edge detection, clip art compression artifact removal, and inverse half-toning. Robust Mesh Denoising via Vertex Pre-filtering and L1-Median Normal Filtering Lu X., Chen W., and Schaefer S. Computer Aided Geometric Design, Vol. 54, (2017), pp. 49-60 Abstract: We propose a robust and effective mesh denoising approach consisting of three steps: vertex pre-filtering, L1-median normal filtering, and vertex updating. Given an input noisy mesh model, our method generates a high quality model that preserves geometric features. Our approach is more robust than state of the art approaches when denoising models with different levels of noise and can handle models with irregular surface sampling. Pyramid Algorithms for Barycentric Rational Interpolation Hormann K. and Schaefer S. Computer Aided Geometric Design, Vol. 42, (2016), pp. 1-6 Abstract: We present a new perspective on the Floater--Hormann interpolant. This interpolant is rational of degree (n,d), reproduces polynomials of degree d, and has no real poles. By casting the evaluation of this interpolant as a pyramid algorithm, we first demonstrate a close relation to Neville's algorithm. We then derive an O(nd) algorithm for computing the barycentric weights of the Floater-Hormann interpolant, which improves upon the original O(nd^2) construction. Bijective Parameterization with Free Boundaries Smith J. and Schaefer S. ACM Transactions on Graphics (Proceedings of SIGGRAPH), Vol. 34, No. 4, (2015), pp. 70:1-70:9, slides, movie, movie,movie,movie Abstract: We present a fully automatic method for generating guaranteed bijective surface parameterizations from triangulated 3D surfaces partitioned into charts. We do so by using a distortion metric that prevents local folds of triangles in the parameterization and a barrier function that prevents intersection of the chart boundaries. In addition, we show how to modify the line search of an interior point method to directly compute the singularities of the distortion metric and barrier functions to maintain a bijective map. By using an isometric metric that is efficient to compute and a spatial hash to accelerate the evaluation and gradient of the barrier function for the boundary, we achieve fast optimization times. Unlike previous methods, we do not require the boundary be constrained by the user to a non-intersecting shape to guarantee a bijection, and the boundary of the parameterization is free to change shape during the optimization to minimize distortion. Denoising Point Sets via L0 Minimization Sun Y., Schaefer S., and Wang W. Computer Aided Geometric Design (Proceedings of GMP), Vol. 35 (2015), pp. 2-15 Abstract: We present an anisotropic point cloud denoising method using L0 minimization. The L0 norm directly measures the sparsity of a solution, and we observe that many common objects can be defined as piece-wise smooth surfaces with a small number of features. Hence, we demonstrate how to apply an L0 optimization directly to point clouds, which produces sparser solutions and sharper surfaces than either the L1 or L2 norms. Our method can faithfully recover sharp features while at the same time smoothing the remaining regions even in the presence of large amounts of noise. Selective Degree Elevation for Multi-Sided Bézier Patches Smith J. and Schaefer S. Computer Graphics Forum (Proceedings of Eurographics), Vol. 34, No. 2 (2015), pp.609-615 Abstract: This paper presents a method to selectively elevate the degree of an S-Patch of arbitrary dimension. We consider not only S-Patches with 2D domains but 3D and higher-dimensional domains as well, of which volumetric cage deformations are a subset. We show how to selectively insert control points of a higher degree patch into a lower degree patch while maintaining the polynomial reproduction order of the original patch. This process allows the user to elevate the degree of only one portion of the patch to add new degrees of freedom or maintain continuity with adjacent patches without elevating the degree of the entire patch, which could create far more degrees of freedom than necessary. Finally we show an application to cage-based deformations where we increase the number of control points by elevating the degree of a subset of cage faces. The result is a cage deformation with higher degree triangular Bézier functions on a subset of cage faces but no interior control points. Bilinear Accelerated Filter Approximation Manson J. and Schaefer S. Computer Graphics Forum (Proceedings of EGSR), Vol. 33, No. 4 (2014), pp. 33-40, supplemental material Abstract: Our method approximates exact texture filtering for arbitrary scales and translations of an image while taking into account the performance characteristics of modern GPUs. Our algorithm is fast because it accesses textures with a high degree of spatial locality. Using bilinear samples guarantees that the texels we read are in a regular pattern and that we use a hardware accelerated path. We control the texel weights by manipulating the u, v parameters of each sample and the blend factor between the samples. Our method is similar in quality to Cardinality-Constrained Texture Filtering but runs two times faster. Cardinality-Constrained Texture Filtering Manson J. and Schaefer S. ACM Transactions on Graphics (Proceedings of SIGGRAPH), Vol. 32, No. 4 (2013), pp. 140:1-140:8, slides, supplemental material, code Abstract: We present a method to create high-quality sampling filters by combining a prescribed number of texels from several resolutions in a mipmap. Our technique provides fine control over the number of texels we read per texture sample so that we can scale quality to match a memory bandwidth budget. Our method also has a fixed cost regardless of the filter we approximate, which makes it feasible to approximate higher-quality filters such as a Lanczos 2 filter in real-time rendering. To find the best set of texels to represent a given sampling filter and what weights to assign those texels, we perform a cardinality-constrained least-squares optimization of the most likely candidate solutions and encode the results of the optimization in a small table that is easily stored on the GPU. We present results that show we accurately reproduce filters using few texel reads and that both quality and speed scale smoothly with available bandwidth. When using four or more texels per sample, our image quality exceeds that of conventional trilinear interpolation. Mesh Denoising via L0 Minimization He L. and Schaefer S. ACM Transactions on Graphics (Proceedings of SIGGRAPH), Vol. 32, No. 4 (2013), pp. 64:1-64:8, slides Abstract: We present an algorithm for denoising triangulated models based on L0 minimization. Our method maximizes the flat regions of the model and gradually removes noise while preserving sharp features. As part of this process, we build a discrete differential operator for arbitrary triangle meshes that is robust with respect to degenerate triangulations. We compare our method versus other anisotropic denoising algorithms and demonstrate that our method is more robust and produces good results even in the presence of high noise. Analytic Rasterization of Curves with Polynomial Filters Manson J. and Schaefer S. Computer Graphics Forum (Proceedings of the Eurographics), Vol. 32, No. 2 (2013), pages 499-507, slides, supplemental material, code, code Abstract: We present a method of analytically rasterizing shapes that have curved boundaries and linear color gradients using piecewise polynomial prefilters. By transforming the convolution of filters with the image from an integral over area into a boundary integral, we find closed-form expressions for rasterizing shapes. We show that a polynomial expression can be used to rasterize any combination of polynomial curves and filters. Our rasterizer also handles rational quadratic boundaries, which allows us to evaluate circles and ellipses. We apply our technique to rasterizing vector graphics and show that our derivation gives an efficient implementation as a scanline rasterizer. Improving the Parameterization of Approximate Subdivision Surfaces He L., Loop C., and Schaefer S. Computer Graphics Forum (Proceedings of Pacific Graphics), Vol. 31, No. 7 (2012), pages 2127-2134, slides Abstract: We provide a method for improving the parameterization of patching schemes that approximate Catmull-Clark subdivision surfaces, such that the new parameterization conforms better to that of the original subdivision surface. We create this reparameterization in real-time using a method that only depends on the topology of the surface and is independent of the surface's geometry. Our method can handle patches with more than one extraordinary vertex and avoids the combinatorial increase in both complexity and storage associated with multiple extraordinary vertices. Moreover, the reparameterization function is easy to implement and fast. Parameterization-Aware MIP-Mapping Manson J. and Schaefer S. Computer Graphics Forum (Proceedings of the Eurographics Symposium on Rendering), Vol. 31, No. 4 (2012), pages 1455-1463, slides, errata, code Abstract: We present a method of generating mipmaps that takes into account the distortions due to the parameterization of a surface. Existing algorithms for generating mipmaps assume that the texture is isometrically mapped to the surface and ignore the actual surface parameterization. Our method correctly downsamples warped textures by assigning texels weights proportional to their area on a surface. We also provide a least-squares approach to filtering over these warped domains that takes into account the postfilter used by the GPU. Our method improves texture filtering for most models but only modifies mipmap generation, requires no modification of art assets or rasterization algorithms, and does not affect run-time performance. Encoding Normal Vectors using Optimized Spherical Coordinates Smith J., Petrova G. and Schaefer S. Computers & Graphics (Proceedings of Shape Modeling International), Vol. 36, No. 5 (2012), pages 360-365, slides Abstract: We present a method for encoding unit vectors based on spherical coordinates that out-performs existing encoding methods both in terms of accuracy and encoding/decoding time. Given a tolerance epsilon, we solve a simple, discrete optimization problem to find a set of points on the unit sphere that can trivially be indexed such that the difference in angle between the encoded vector and the original are no more than epsilon apart. To encode a unit vector, we simply compute its spherical coordinates and round the result based on the prior optimization solution. We also present a moving frame method that further reduces the amount of data to be encoded when vectors have some coherence. Our method is extremely fast in terms of encoding and decoding both of which take constant time O(1). The accuracy of our encoding is also comparable or better than previous methods for encoding unit vectors. Progressive Encoding and Compression of Surfaces Generated from Point Cloud Data Smith J., Petrova G. and Schaefer S. Computers & Graphics (Proceedings of Shape Modeling International), Vol. 36, No. 5 (2012), pages 341-348, slides Abstract: We present a new algorithm for compressing surfaces created from oriented points, sampled using a laser range scanner or created from polygonal surfaces. We first use the input data to build an octree whose nodes contain planes that are constructed as the least square fit of the data within that node. Then, given an error threshold, we prune this octree to remove redundant data while avoiding topological changes created by merging disjoint linear pieces. From this octree representation, we provide a progressive encoding technique that encodes the octree structure as well as the plane equations. We encode the planes using distances to three points and a single bit. To decode these planes, we solve a constrained optimization problem that has closed-form solution. We then reconstruct the surface from this representation by implicitizing the discontinuous linear pieces at the leaves of the octree and take a level set of this implicit representation. Our tests show that the proposed method compresses surfaces with higher accuracy and smaller file sizes than other methods. Hierarchical Deformation of Locally Rigid Meshes Manson J. and Schaefer S. Computer Graphics Forum, Vol. 30, No. 8 (2011), pages 2387-2396, slides, movie, movie Abstract: We propose a method for calculating deformations of models by deforming a low-resolution mesh and adding details while ensuring that the details we add satisfy a set of constraints. Our method builds a low-resolution representation of a mesh by using edge collapses and performs an as-rigid-as-possible deformation on the simplified mesh. We then add back details by reversing edge-collapses so that the shape of the mesh is locally preserved. While adding details, we deform the mesh to match the predicted positions of constraints so that constraints on the full-resolution mesh are met. Our method operates on meshes with arbitrary triangulations, satisfies constraints over the full-resolution mesh, and converges quickly. Positive Gordon-Wixom Coordinates Manson J., Li K. and Schaefer S. Computer Aided Design (Proceedings of Geometric and Physical Modeling), Vol. 43, No. 11 (2011), pages 1422-1426, slides Abstract: We introduce a new construction of transfinite barycentric coordinates for arbitrary closed sets in 2D. Our method extends weighted Gordon-Wixom interpolation to non-convex shapes and produces coordinates that are positive everywhere in the interior of the domain and that are smooth for shapes with smooth boundaries. We achieve these properties by using the distance to lines tangent to the boundary curve to define a weight function that is positive and smooth. We derive closed-form expressions for arbitrary polygons in 2D and compare the basis functions of our coordinates with several other types of barycentric coordinates. Wavelet Rasterization Best Paper Award Manson J. and Schaefer S. Computer Graphics Forum (Proceedings of Eurographics), Vol. 30, No. 2 (2011), pages 395-404, slides, code, code Abstract: We present a method for analytically calculating an anti-aliased rasterization of arbitrary polygons or fonts bounded by Bezier curves in 2D as well as oriented triangle meshes in 3D. Our algorithm rasterizes multiple resolutions simultaneously using a hierarchical wavelet representation and is robust to degenerate inputs. We show that using the simplest wavelet, the Haar basis, is equivalent to performing a box-filter to the rasterized image. Because we evaluate wavelet coefficients through line integrals in 2D, we are able to derive analytic solutions for polygons that have Bezier curve boundaries of any order, and we provide solutions for quadratic and cubic curves. In 3D, we compute the wavelet coefficients through analytic surface integrals over triangle meshes and show how to do so in a computationally efficient manner. Contouring Discrete Indicator Functions Manson J., Smith J. and Schaefer S. Computer Graphics Forum (Proceedings of Eurographics), Vol. 30, No. 2 (2011), pages 385-393, slides, code Abstract: We present a method for calculating the boundary of objects from Discrete Indicator Functions that store 2-material volume fractions with a high degree of accuracy. Although Marching Cubes and its derivatives are effective methods for calculating contours of functions sampled over discrete grids, these methods perform poorly when contouring non-smooth functions such as Discrete Indicator Functions. In particular, Marching Cubes will generate surfaces that exhibit aliasing and oscillations around the exact surface. We derive a simple solution to remove these problems by using a new function to calculate the positions of vertices along cell edges that is efficient, easy to implement, and does not require any optimization or iteration. Finally, we provide empirical evidence that the error introduced by our contouring method is significantly less than is introduced by Marching Cubes. Parameterization and Applications of Catmull-Rom Curves Yuksel C., Schaefer S. and Keyser J. Computer-Aided Design, Vol. 43, No. 7 (2011), pages 747-755. 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. Finally, we discuss two example applications of Catmull-Rom curves and show how the choice of parameterization makes a signicant difference in each of these applications. Triangle Surfaces with Discrete Equivalence Classes Singh M. and Schaefer S. ACM Transactions on Graphics (Proceedings of SIGGRAPH), Vol. 29, No. 4 (2010), pages 46:1 - 46:7, slides, movie, movie Abstract: We propose a technique that takes a triangulated surface as input and outputs a surface with the same topology but altered geometry such that each polygon falls into a set of discrete equivalence classes. We begin by describing an error function that measures how close the polygons are to satisfying this criteria. To optimize this error function, we first cluster triangles into discrete sets such that the assignment of sets minimizes our error. We then find canonical polygons for each set using nonlinear optimization. Next, we solve a Poisson equation to find positions of vertices such that the surface polygons match the canonical polygons as close as possible. We also describe how to incorporate a fairness criteria into the optimization to avoid oscillations of the surface. We iterate this entire process until we reach a user specified tolerance, possibly adding clusters during iteration to guarantee convergence. We have been able to successfully reduce the number of unique triangles to lie within a small percentage of the total number of triangles in the surface and demonstrate our technique on various examples. Parameterizing Subdivision Surfaces He L., Schaefer S. and Hormann K. ACM Transactions on Graphics (Proceedings of SIGGRAPH), Vol. 29, No. 4 (2010), pages 120:1 - 120:6, slides Abstract: We present a method for parameterizing subdivision surfaces in an as-rigid-as-possible fashion. While much work has concentrated on parameterizing polygon meshes, little if any work has focused on subdivision surfaces despite their popularity. We show that polygon parameterization methods produce suboptimal results when applied to subdivision surfaces and describe how these methods may be modified to operate on subdivision surfaces. We also describe a method for creating extended charts to further reduce the distortion of the parameterization. Finally we demonstrate how to take advantage of the multi-resolution structure of subdivision surfaces to accelerate convergence of our optimization. Scales and Scale-Like Structures Landreneau E. and Schaefer S. Computer Graphics Forum (Proceedings of the Symposium on Geometry Processing), Vol. 29, No. 5 (2010), pages 1653-1660, slides, movie, additional examples Abstract: We present a method for generating scales and scale-like structures on a polygonal mesh through surface replacement. As input, we require a triangular mesh that will be covered with scales and one or more proxy-models to be used as the scale’s shape. A user begins scale generation by drawing a lateral line on the model to control the distribution and orientation of scales on the surface. We then create a vector field over the surface to control an anisotropic Voronoi tessellation, which represents the region occupied by each scale. Next we replace these regions by cutting the proxy model to match the boundary of the Voronoi region and deform the cut model onto the surface. The result is a fully connected 2-manifold that is suitable for subsequent post-processing applications like surface subdivision. Moving Least Squares Coordinates Manson J. and Schaefer S. Computer Graphics Forum (Proceedings of the Symposium on Geometry Processing), Vol. 29, No. 5 (2010), pages 1517-1524, slides Abstract: We propose a new family of barycentric coordinates that have closed-forms for arbitrary 2D polygons. These coordinates are easy to compute and have linear precision even for open polygons. Not only do these coordinates have linear precision, but we can create coordinates that reproduce polynomials of a set degree m as long as degree m polynomials are specified along the boundary of the polygon. We also show how to extend these coordinates to interpolate derivatives specified on the boundary. Suggestive Hatching Singh M. and Schaefer S. Computational Aesthetics 2010, pages 25-32, slides Abstract: We present a method for drawing lines on an object that depict both the shape and shading of the object. To do so, we construct a gradient field of the diffuse intensity of the surface to guide a set of adaptively spaced lines. The shape of these lines reflect the lighting under which the object is being viewed and its shape. When the light source is placed at the viewer’s location, these lines emanate from silhouettes and naturally extend Suggestive Contours. By using a hierarchical proximity grid, we can also improve the quality of these lines as well as control their density over the image. We also provide a method for detecting and removing ridge lines in the intensity field, which lead to artifacts in the line drawings. Isosurfaces Over Simplicial Partitions of Multiresolution Grids Manson J. and Schaefer S. Computer Graphics Forum (Proceedings of Eurographics), Vol. 29, No. 2 (2010), pages 377-385, slides, code Abstract: We provide a simple method that extracts an isosurface that is manifold and intersection-free from a function over an arbitrary octree. Our method samples the function dual to minimal edges, faces, and cells, and we show how to position those samples to reconstruct sharp and thin features of the surface. Moreover, we describe an error metric designed to guide octree expansion such that flat regions of the function are tiled with fewer polygons than curved regions to create an adaptive polygonalization of the isosurface. We then show how to improve the quality of the triangulation by moving dual vertices to the isosurface and provide a topological test that guarantees we maintain the topology of the surface. While we describe our algorithm in terms of extracting surfaces from volumetric functions, we also show that our algorithm extends to generating manifold level sets of co-dimension 1 of functions of arbitrary dimension. Approximating Subdivision Surfaces with Gregory Patches for Hardware Tessellation Loop C., Schaefer S., Ni T. and Castano I. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia), Vol. 28, No. 5 (2009), pages 151:1 - 151:9, slides, movie Abstract: We present a new method for approximating subdivision surfaces with hardware accelerated parametric patches. Our method improves the memory requirements for patch control points, translating into superior performance compared to existing methods. Our input is general, allowing for meshes that contain both quadrilateral and triangular faces in the input control mesh, as well as control meshes with boundary. We present two implementations of our scheme designed to run on Direct3D 11 class hardware equipped with a tessellator unit. Hair Meshes Yuksel C., Schaefer S. and Keyser J. ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia), Vol. 28, No. 5 (2009), pages 166:1 - 166:7, slides, movie, proceedings title page image Abstract: Despite the visual importance of hair and the attention paid to hair modeling in the graphics research, modeling realistic hair still remains a very challenging task that can be performed by very few artists. In this paper we present hair meshes, a new method for modeling hair that aims to bring hair modeling as close as possible to modeling polygonal surfaces. This new approach provides an artist with direct control of the overall shape of the hair, giving them the ability to model the exact hair shape they desire. We use the hair mesh structure for modeling the hair volume with topological constraints that allow us to automatically and uniquely trace the path of individual hair strands through this volume. We also define a set of topological operations for creating hair meshes that maintain these constraints. Furthermore, we provide a method for hiding the volumetric structure of the hair mesh from the end user, thus allowing artists to concentrate on manipulating the outer surface of the hair as a polygonal surface. We explain and show examples of how hair meshes can be used to generate individual hair strands for a wide variety of realistic hair styles. Poisson-based Weight Reduction of Animated Meshes Landreneau E. and Schaefer S. Computer Graphics Forum, Vol. 29, No. 6 (2010), pages 1945-1954, 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. SIAM/ACM Joint Conference on Geometric and Physical Modeling 2009, pages 47-53, slides 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. 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. 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). 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. 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, 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. Freeform Curves on Spheres of Arbitrary Dimension Schaefer S. and Goldman R. Proceedings of Pacific Graphics 2005, pages 160-162, Longer Version Abstract: Recursive evaluation procedures based on spherical linear interpolation and stationary subdivision algorithms based on geodesic midpoint averaging are used to construct the analogues on spheres of arbitrary dimension of Lagrange and Hermite interpolation and Bezier and B-spline approximation. 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 343-356 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.