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.

CardinalityConstrained Texture Filtering
Manson J. and Schaefer S.
ACM Transactions on Graphics (Proceedings of SIGGRAPH), Vol. 32, No. 4 (2013), pp. 140:1140:8, supplemental material
Abstract: We present a method to create highquality 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 higherquality filters such as a Lanczos 2 filter in realtime rendering. To find the best set of texels to represent a given sampling filter and what weights to assign those texels, we perform a cardinalityconstrained leastsquares 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:164:8
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 499507, 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 closedform 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 21272134, slides
Abstract: We provide a method for improving the parameterization of patching schemes that approximate CatmullClark subdivision surfaces, such that the new parameterization conforms better to that of the original subdivision surface. We create this reparameterization in realtime 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.


ParameterizationAware MIPMapping
Manson J. and Schaefer S.
Computer Graphics Forum (Proceedings of the Eurographics Symposium on Rendering), Vol. 31, No. 4 (2012), pages 14551463, 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 leastsquares 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 runtime 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 360365, slides
Abstract: We present a method for encoding unit vectors based on spherical coordinates that outperforms 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 341348, 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 closedform 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 23872396, slides, movie, movie
Abstract: We propose a method for calculating deformations of models by deforming a lowresolution mesh and adding details while ensuring that the details we add satisfy a set of constraints. Our method builds a lowresolution representation of a mesh by using edge collapses and performs an asrigidaspossible deformation on the simplified mesh. We then add back details by reversing edgecollapses 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 fullresolution mesh are met. Our method operates on meshes with arbitrary triangulations, satisfies constraints over the fullresolution mesh, and converges quickly.


Positive GordonWixom Coordinates
Manson J., Li K. and Schaefer S.
Computer Aided Design (Proceedings of Geometric and Physical Modeling), Vol. 43, No. 11 (2011), pages 14221426, slides
Abstract: We introduce a new construction of transfinite barycentric coordinates for arbitrary closed sets in 2D. Our method extends weighted GordonWixom interpolation to nonconvex 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 closedform 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 395404, slides, code, code
Abstract: We present a method for analytically calculating an antialiased 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 boxfilter 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 385393, slides, code
Abstract: We present a method for calculating the boundary of objects from Discrete Indicator Functions that store 2material 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 nonsmooth 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 CatmullRom Curves
Yuksel C., Schaefer S. and Keyser J.
ComputerAided Design, Vol. 43, No. 7 (2011), pages 747755.
Abstract: The behavior of CatmullRom 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 CatmullRom curves, centripetal parameterization is the only parameterization in this family that guarantees that the curves do not form cusps or selfintersections within curve segments. Furthermore, we provide a formulation that bounds the distance of the curve to the control polygon and explain how globally intersectionfree CatmullRom curves can be generated using these properties. Finally, we discuss two example applications of CatmullRom 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 asrigidaspossible 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 multiresolution structure of subdivision surfaces to accelerate convergence of our optimization.


Scales and ScaleLike Structures
Landreneau E. and Schaefer S.
Computer Graphics Forum (Proceedings of the Symposium on Geometry Processing), Vol. 29, No. 5 (2010), pages 16531660, slides, movie, additional examples
Abstract: We present a method for generating scales and scalelike 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 proxymodels 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 2manifold that is suitable for subsequent postprocessing 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 15171524, slides
Abstract: We propose a new family of barycentric coordinates that have closedforms 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 2532, 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 377385, slides, code
Abstract: We provide a simple method that extracts an isosurface that is manifold and intersectionfree 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 codimension
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.


Poissonbased Weight Reduction of Animated Meshes
Landreneau E. and Schaefer S.
Computer Graphics Forum, Vol. 29, No. 6 (2010), pages 19451954, 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 realtime applications.
We present a method that reduces the number of control points influencing a vertex to a userspecified 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 realtime deformations of large models possible.


On the Parameterization of CatmullRom Curves
Yuksel C., Schaefer S. and Keyser J.
SIAM/ACM Joint Conference on Geometric and Physical Modeling 2009, pages 4753, slides
Abstract: The behavior of CatmullRom 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 CatmullRom curves, centripetal
parameterization is the only parameterization in this family that guarantees that the curves do not form cusps or
selfintersections 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 CatmullRom 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 347353, 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
multiresolution 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.


Nonuniform Subdivision for Bsplines of Arbitrary Degree
Schaefer S. and Goldman R.
Computer Aided Geometric Design, Vol. 26, No. 1 (2009), pages 7581, slides, slides
Abstract: We present an efficient algorithm for subdividing nonuniform Bsplines of arbitrary
degree in a manner similar to the LaneRiesenfeld subdivision algorithm for uniform Bsplines
of arbitrary degree. Our algorithm consists of doubling the control points followed
by d rounds of nonuniform averaging similar to the d rounds of uniform averaging in the
LaneRiesenfeld algorithm for uniform Bsplines of degree d. However, unlike the Lane
Riesenfeld algorithm which follows most directly from the continuous convolution formula
for the uniform Bspline 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 nonuniform Bsplines.


On the Smoothness of RealValued 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 231242
Abstract: Our main result is that two point interpolatory subdivision schemes using C^k nonlinear averaging
rules on pairs of real numbers generate realvalued 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 realvalued 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 NonPolynomial Subdivision Schemes
Schaefer S. and Warren J.
Computer Aided Geometric Design, Vol. 25, No. 8 (2008), pages 607620
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 nonpolynomial 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 nonpolynomial quadbased subdivision surfaces using
our exact evaluation method. Our tessellation method guarantees a watertight
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 14111420, 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 lowresolution 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 13731382, slides, cover image
Abstract: We present a second order smooth filling of an nvalent CatmullClark 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
4valent case, we reproduce the bicubic Bsplines. 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 CatmullClark Subdivision Surfaces with Bicubic Patches
Loop C. and Schaefer S.
ACM Transactions on Graphics, Vol 27, No. 1 (2008), pages 8:18:11, slides, movie
Abstract: We present a simple and computationally efficient algorithm for
approximating CatmullClark 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 CatmullClark 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 CatmullClark surface. These tangent patches are
used to construct a continuous normal field (through their
crossproduct) for shading and displacement mapping. Using this
bifurcated representation, we are able to define an accurate
proxy for CatmullClark surfaces that is efficient to evaluate on
nextgeneration GPU architectures that expose a programmable
tessellation unit.


Jsplines
Rossignac J. and Schaefer S.
Computer Aided Design, Vol 40, No. 1011 (2008), pages 10241032
Abstract: Both the 4point and the uniform cubic Bspline subdivisions double the number of vertices of a closedloop polygon P^k and produce sequences of vertices f_j and b_j respectively. We study the Jspline 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 fourpoint subdivision curves (J_0), uniform cubic Bspline curves (J_1), and uniform quintic Bspline 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 4point yields only C^1 curves and cubic Bspline yields only C^2 curves. We generalize the J_s scheme to a twoparameter family J_{a,b} and propose datadependent and dataindependent 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 multiresolution rendering). We extend the Jspline subdivision to open curves and to a smooth surface subdivision scheme for quadmeshes 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 162180, 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 NonPolynomial Subdivision Schemes at Rational Parameter Values
Schaefer S. and Warren J.
Pacific Graphics 2007, pages 321330, 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 nonpolynomial 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 nonpolynomial quadbased
subdivision surfaces using our exact evaluation method. Our
method guarantees a watertight 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.


ExampleBased Skeleton Extraction
Schaefer S. and Yuksel C.
Eurographics Symposium on Geometry Processing 2007, pages 153162, 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 610619, slides
Abstract: Dual Contouring is a featurepreserving isosurfacing
method that extracts crackfree 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 octreebased, topologypreserving 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 isosurfacing methods under topologically safe
simplification.


A Unified, Integral Construction For Coordinates Over Closed Curves
Schaefer S., Ju T. and Warren J.
ComputerAided Geometric Design, Vol 24, No. 89 (2007), pages 481493 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 319338
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 533540, 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
realworld 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
closedform solutions that yield fast deformations, which can be performed in
realtime.


Mean Value Coordinates for Closed Triangular Meshes
Ju T., Schaefer S. and Warren J.
ACM SIGGRAPH 2005, pages 561566, 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 181186, 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 nonnegative
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 polyhedraa 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 171180, slides
Abstract: Subdivision schemes generate selfsimilar curves and surfaces. Therefore
there is a close connection between curves and surfaces generated by
subdivision algorithms and selfsimilar 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 Bsplines,
piecewise Bezier, stationary fourpoint subdivision, Boxsplines, 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 2836, 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 7076, 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 crackfree,
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 105116, 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 CatmullClark 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 151158, 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 7481
Abstract: This tutorial explains how to implement several different
subdivision schemes under a single, unified framework. Our
discussion will illustrate CatmullClark
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 datastructures 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.
ComputerAided Design 2004, Vol. 36(14), pages 15011510
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 realworld 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.
ComputerAided Design 2004, Vol. 36(14), pages 14711482
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 9911004
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 nonbracketed Lsystems 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 491500, slides
Abstract: We present an adaptive vertex clustering approach to outofcore
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 138145, slides
Abstract: Previous parametric representations of smooth genuszero 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 bicubic Bspline. Due to its tensorproduct 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 levelofdetail 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 02408
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 nonmanifold 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 datastructure
in constant time during CSG operations.


Convex Contouring of Volumetric Data
Ju T., Schaefer S. and Warren J.
The Visual Computer, Vol. 19, No. 78, 2003, pages 513525
Abstract: In this paper we present a fast, tabledriven isosurface
extraction technique on volumetric data. Unlike Marching Cubes or
other cellbased 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 lookup 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, crackfree
multiresolution contouring on nested grids of volumetric data.
The method can also be extended to extract isosurfaces on
arbitrary convex, spacefilling polyhedra.


A Factored Interpolatory Subdivision Scheme for Surfaces of Revolution
Schaefer S.
Master's Thesis, Rice University 2003 slides
Abstract: We present a new nonstationary, 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
nonstationary 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 339346, 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 multisigned functions and demonstrate how to model
textured contours using multisigned functions.
Using a new, numerically stable representation for quadratic error functions,
we develop an octreebased 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 373382
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 wellknown 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 343356
Abstract: In a landmark paper, Catmull and Clark described a simple
generalization of the subdivision rules for bicubic Bsplines 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 nonmanifold topology and can easily be extended to
incorporate boundaries and embedded creases expressed as CatmullClark
surfaces and Bspline curves.

