Hugues Hoppe »
Detailed Publications
Semiautomated video morphing.
Eurographics Symposium on Rendering, 2014.
Transition across two videos using optimized spatiotemporal alignment.
We explore creating smooth transitions between videos of different scenes. As in traditional image
morphing, good spatial correspondence is crucial to prevent ghosting, especially at silhouettes. Video
morphing presents added challenges. Because motions are often unsynchronized, temporal alignment is also
necessary. Applying morphing to individual frames leads to discontinuities, so temporal coherence must be
considered. Our approach is to optimize a full spatiotemporal mapping between the two videos. We reduce
tedious interaction by letting the optimization derive the finescale map given only sparse userspecified
constraints. For robustness, the optimization objective examines structural similarity of the video
content. We demonstrate the approach on a variety of videos, obtaining results using few explicit
correspondences.
No hindsights yet.


Automating image morphing using structural similarity on a halfway domain.
ACM Trans. Graphics, 33(3?), 2014. (To be presented at SIGGRAPH 2014.)
Fast optimization to align intricate shapes using little interactive guidance.
The main challenge in achieving good image morphs is to create a map that aligns corresponding image
elements. Our aim is to help automate this often tedious task. We compute the map by optimizing the
compatibility of corresponding warped image neighborhoods using an adaptation of structural similarity.
The optimization is regularized by a thinplate spline, and may be guided by a few userdrawn points. We
parameterize the map over a halfway domain and show that this representation offers many benefits. The map
is able to treat the image pair symmetrically, model simple occlusions continuously, span partially
overlapping images, and define extrapolated correspondences. Moreover, it enables direct evaluation of the
morph in a pixel shader without mesh rasterization. We improve the morphs by optimizing quadratic motion
paths and by seamlessly extending content beyond the image boundaries. We parallelize the algorithm on a
GPU to achieve a responsive interface and demonstrate challenging morphs obtained with little effort.
One exciting aspect is that just as in the earlier project
Imagespace bidirectional scene reprojection,
the iterative implicit solver is able to evaluate the morph color directly in a pixel shader,
without requiring any geometric tessellation, i.e. using only “gather” operations.
Errata: Referring to Figure 16, the text in Section 9 states “Note that the top two examples require no correspondence points”  it should be just “the top example”. 

A fresh look at generalized sampling.
Foundations and Trends in Computer Graphics and Vision, 8(1), 2014.
Extension of recent signalprocessing techniques to graphics filtering.
Discretization and reconstruction are fundamental operations in computer graphics, enabling the conversion
between sampled and continuous representations. Major advances in signalprocessing research have shown
that these operations can often be performed more efficiently by decomposing a filter into two parts: a
compactly supported continuousdomain function and a digital filter. This strategy of “generalized
sampling” has appeared in a few graphics papers, but is largely unexplored in our community. This
survey broadly summarizes the key aspects of the framework, and delves into specific applications in
graphics. Using new notation, we concisely present and extend several key techniques. In addition, we
demonstrate benefits for prefiltering in image downscaling and supersamplebased rendering, and analyze the
effect that generalized sampling has on the noise due to Monte Carlo estimation. We conclude with a
qualitative and quantitative comparison of traditional and generalized filters.
An earlier version of this paper is
IMPA Tech. Report E022/2011 & Microsoft Research MSRTR201116, February 2011
.


Automated video looping with progressive dynamism.
ACM Trans. Graphics (SIGGRAPH), 32(4), 2013.
Representation for seamlessly looping video with controllable level of dynamism.
Given a short video we create a representation that captures a spectrum of looping videos with varying
levels of dynamism, ranging from a static image to a highly animated loop. In such a progressively dynamic
video, scene liveliness can be adjusted interactively using a slider control. Applications include
background images and slideshows, where the desired level of activity may depend on personal taste or mood.
The representation also provides a segmentation of the scene into independently looping regions, enabling
interactive local adjustment over dynamism. For a landscape scene, this control might correspond to
selective animation and deanimation of grass motion, water ripples, and swaying trees. Converting
arbitrary video to looping content is a challenging research problem. Unlike prior work, we explore an
optimization in which each pixel automatically determines its own looping period. The resulting nested
segmentation of static and dynamic scene regions forms an extremely compact representation.
The timemapping equation (1) has a simpler form:
ϕ(x, t) = s_{x} +
((t  s_{x})
mod p_{x}).
(One must be careful that the C/C++
remainder
operator “% ” differs from the
modulo
operator “mod ”
for negative numbers.)
Thanks to Mark Finch for preparing and optimizing the code in our demo tool release.
Errata: The formula for b_{j}
in case (4) of page 4 has a typo; it should be
b_{j} =
V_{c}(x, ϕ(z,j)). 

Screened Poisson surface reconstruction.
ACM Trans. Graphics, 32(3), 2013. (Presented at SIGGRAPH 2013.)
Improved geometric fidelity and linearcomplexity adaptive hierarchical solver.
Poisson surface reconstruction creates watertight surfaces from oriented point sets. In this work we
extend the technique to explicitly incorporate the points as interpolation constraints. The extension can
be interpreted as a generalization of the underlying mathematical framework to a screened Poisson equation.
In contrast to other image and geometry processing techniques, the screening term is defined over a sparse
set of points rather than over the full domain. We show that these sparse constraints can nonetheless be
integrated efficiently. Because the modified linear system retains the same finiteelement discretization,
the sparsity structure is unchanged, and the system can still be solved using a multigrid approach.
Moreover we present several algorithmic improvements that together reduce the time complexity of the solver
to linear in the number of points, thereby enabling faster, higherquality surface reconstructions.
See also the comments in the earlier paper
Poisson surface reconstruction.


Cliplets: Juxtaposing still and dynamic imagery.
Symposium on User Interface Software and Technology (UIST) 2012. (Best Paper Award)
Cinemagraphs and more general spatiotemporal compositions from handheld video.
We explore creating cliplets, a form of visual media that juxtaposes still image and video segments, both
spatially and temporally, to expressively abstract a moment. Much as in cinemagraphs, the tension between
static and dynamic elements in a cliplet reinforces both aspects, strongly focusing the viewer's attention.
Creating this type of imagery is challenging without professional tools and training. We develop a set of
idioms, essentially spatiotemporal mappings, that characterize cliplet elements, and use these idioms in an
interactive system to quickly compose a cliplet from ordinary handheld video. One difficulty is to avoid
artifacts in the cliplet composition without resorting to extensive manual input. We address this with
automatic alignment, looping optimization and feathering, simultaneous matting and compositing, and
Laplacian blending. A key userinterface challenge is to provide affordances to define the parameters of
the mappings from input time to output time while maintaining a focus on the cliplet being created. We
demonstrate the creation of a variety of cliplet types. We also report on informal feedback as well as a
more structured survey of users.
With cliplets, the user interactively sketches static and dynamic regions, each assigned a uniform looping period. Our subsequent work Automated video looping animates the entire scene without user assistance, and uses combinatorial optimization to infer the optimal looping interval for each pixel. See some nice professionally created cinemagraphs at http://cinemagraphs.com/. 

A subdivisionbased representation for vector image editing.
IEEE Trans. Vis. Comput. Graphics, 18(11), Nov. 2012. (Presented at I3D 2013.)
(Spotlight Paper) Piecewisesmooth subdivision for representing and manipulating images.
Vector graphics has been employed in a wide variety of applications due to its scalability and editability.
Editability is a high priority for artists and designers who wish to produce vectorbased graphical content
with user interaction. In this paper, we introduce a new vector image representation based on piecewise
smooth subdivision surfaces, which is a simple, unified and flexible framework that supports a variety of
operations, including shape editing, color editing, image stylization, and vector image processing. These
operations effectively create novel vector graphics by reusing and altering existing image vectorization
results. Because image vectorization yields an abstraction of the original raster image, controlling the
level of detail of this abstraction is highly desirable. To this end, we design a featureoriented vector
image pyramid that offers multiple levels of abstraction simultaneously. Our new vector image
representation can be rasterized efficiently using GPUaccelerated subdivision. Experiments indicate that
our vector image representation achieves high visual quality and better supports editing operations than
existing representations.
Using a common subdivision process to define both the geometric outlines and the (piecewise) smooth color
field is elegant.


Freeform vector graphics with controlled thinplate splines.
ACM Trans. Graphics (SIGGRAPH Asia), 30(6), 2011.
Rich set of curve and point controls for intuitive and expressive color interpolation.
Recent work defines vector graphics using diffusion between colored curves. We explore higherorder
fairing to enable more natural interpolation and greater expressive control. Specifically, we build on
thinplate splines which provide smoothness everywhere except at userspecified tears and creases
(discontinuities in value and derivative respectively). Our system lets a user sketch discontinuity curves
without fixing their colors, and sprinkle color constraints at sparse interior points to obtain smooth
interpolation subject to the outlines. We refine the representation with novel contour and slope curves,
which anisotropically constrain interpolation derivatives. Compound curves further increase editing power
by expanding a single curve into multiple offsets of various basic types (value, tear, crease, slope, and
contour). The vector constraints are discretized over an image grid, and satisfied using a hierarchical
solver. We demonstrate interactive authoring on a desktop CPU.
We should have mentioned the work of
[Xia et al. 2009. PatchBased Image Vectorization
with Automatic Curvilinear Feature Alignment] which also introduces higherorder color reconstruction
for vector graphics. It optimizes parametric Bezier patches with ThinPlate Spline color functions to
approximate a given image.


GPUefficient recursive filtering and summedarea tables.
ACM Trans. Graphics (SIGGRAPH Asia), 30(6), 2011.
Efficient overlapped computation of successive recursive filters on 2D images.
Image processing operations like blurring, inverse convolution, and summedarea tables are often computed
efficiently as a sequence of 1D recursive filters. While much research has explored parallel recursive
filtering, prior techniques do not optimize across the entire filter sequence. Typically, a separate
filter (or often a causalanticausal filter pair) is required in each dimension. Computing these filter
passes independently results in significant traffic to global memory, creating a bottleneck in GPU systems.
We present a new algorithmic framework for parallel evaluation. It partitions the image into 2D blocks,
with a small band of additional data buffered along each block perimeter. We show that these perimeter
bands are sufficient to accumulate the effects of the successive filters. A remarkable result is that the
image data is read only twice and written just once, independent of image size, and thus total memory
bandwidth is reduced even compared to the traditional serial algorithm. We demonstrate significant
speedups in GPU computation.
For completeness we could have mentioned
integral images,
a term used in computer vision [Viola and Jones 2001]
to also refer to
summedarea tables [Crow 1984].


Imagespace bidirectional scene reprojection.
ACM Trans. Graphics (SIGGRAPH Asia), 30(6), 2011.
Realtime temporal upsampling through imagebased reprojection of adjacent frames.
We introduce a method for increasing the framerate of realtime rendering applications. Whereas many
existing temporal upsampling strategies only reuse information from previous frames, our bidirectional
technique reconstructs intermediate frames from a pair of consecutive rendered frames. This significantly
improves the accuracy and efficiency of data reuse since very few pixels are simultaneously occluded in
both frames. We present two versions of this basic algorithm. The first is appropriate for fillbound
scenes as it limits the number of expensive shading calculations, but involves rasterization of scene
geometry at each intermediate frame. The second version, our more significant contribution, reduces both
shading and geometry computations by performing reprojection using only imagebased buffers. It warps and
combines the adjacent rendered frames using an efficient iterative search on their stored scene depth and
flow. Bidirectional reprojection introduces a small amount of lag. We perform a user study to investigate
this lag, and find that its effect is minor. We demonstrate substantial performance improvements (34X)
for a variety of applications, including vertexbound and fillbound scenes, multipass effects, and motion
blur.
One nice contribution is the idea of using an iterative implicit solver to locate the source pixel
given a velocity field.
In the more recent project
Automating image morphing
using structural similarity on a halfway domain,
we adapt this idea to evaluate an image morph directly in a pixel shader,
without requiring any geometric tessellation, i.e. using only “gather” operations.


Realtime classification of dance gestures from skeleton animation.
Symposium on Computer Animation 2011. (Honorable Mention)
Recognition of Kinect motions using robust, lowdimensional feature vectors.
We present a realtime gesture classification system for skeletal wireframe motion. Its key components
include an angular representation of the skeleton designed for recognition robustness under noisy input, a
cascaded correlationbased classifier for multivariate timeseries data, and a distance metric based on
dynamic timewarping to evaluate the difference in motion between an acquired gesture and an oracle for the
matching gesture. While the first and last tools are generic in nature and could be applied to any
gesturematching scenario, the classifier is conceived based on the assumption that the input motion
adheres to a known, canonical timebase: a musical beat. On a benchmark comprising 28 gesture classes,
hundreds of gesture instances recorded using the XBOX Kinect platform and performed by dozens of subjects
for each gesture class, our classifier has an average accuracy of 96.9%, for approximately 4second
skeletal motion recordings. This accuracy is remarkable given the input noise from the realtime depth
sensor.
This technology was adapted in the
Kinect Star Wars video game.


Antialiasing recovery.
ACM Trans. Graphics, 30(3), 2011. (Presented at SIGGRAPH 2011.)
Fast removal of jaggies introduced by many nonlinear image processing operations.
We present a method for restoring antialiased edges that are damaged by certain types of nonlinear image
filters. This problem arises with many common operations such as intensity thresholding, tone mapping,
gamma correction, histogram equalization, bilateral filters, unsharp masking, and certain
nonphotorealistic filters. We present a simple algorithm that selectively adjusts the local gradients in
affected regions of the filtered image so that they are consistent with those in the original image. Our
algorithm is highly parallel and is therefore easily implemented on a GPU. Our prototype system can process
up to 500 megapixels per second and we present results for a number of different image filters.
Thanks to Mark Finch
for writing the Direct2D Custom Image Effect to demonstrate this technique!


Optimizing continuity in multiscale imagery.
ACM Trans. Graphics (SIGGRAPH Asia), 29(6), 2010.
Visually continuous mipmap pyramid spanning differing coarse and finescale images.
Multiscale imagery often combines several sources with differing appearance. For instance, Internetbased
maps contain satellite and aerial photography. Zooming within these maps may reveal jarring transitions.
We present a scheme that creates a visually smooth mipmap pyramid from stitched imagery at several scales.
The scheme involves two new techniques. The first, structure transfer, is a nonlinear operator that
combines the detail of one image with the local appearance of another. We use this operator to inject
detail from the fine image into the coarse one while retaining color consistency. The improved structural
similarity greatly reduces interlevel ghosting artifacts. The second, clipped Laplacian blending, is an
efficient construction to minimize blur when creating intermediate levels. It considers the sum of all
interlevel image differences within the pyramid. We demonstrate continuous zooming of map imagery from
space to ground level.
No hindsights yet.


Metricaware processing of spherical imagery.
ACM Trans. Graphics (SIGGRAPH Asia), 29(6), 2010.
Adaptively discretized equirectangular map for accurate spherical processing.
Processing spherical images is challenging. Because no spherical parameterization is globally uniform, an
accurate solver must account for the spatially varying metric. We present the first efficient metricaware
solver for Laplacian processing of spherical data. Our approach builds on the commonly used
equirectangular parameterization, which provides differentiability, axial symmetry, and grid sampling.
Crucially, axial symmetry lets us discretize the Laplacian operator just once per grid row. One difficulty
is that anisotropy near the poles leads to a poorly conditioned system. Our solution is to construct an
adapted hierarchy of finite elements, adjusted at the poles to maintain derivative continuity, and
selectively coarsened to bound element anisotropy. The resulting elements are nested both within and
across resolution levels. A streaming multigrid solver over this hierarchy achieves excellent convergence
rate and scales to huge images. We demonstrate applications in reactiondiffusion texture synthesis and
panorama stitching and sharpening.
No hindsights yet.


Seamless montage for texturing models.
Computer Graphics Forum (Eurographics), 29(2), 479486, 2010.
Optimized alignment and merging of photographs for texturing approximate geometry.
We present an automatic method to recover highresolution texture over an object by mapping detailed
photographs onto its surface. Such highresolution detail often reveals inaccuracies in geometry and
registration, as well as lighting variations and surface reflections. Simple image projection results in
visible seams on the surface. We minimize such seams using a global optimization that assigns compatible
texture to adjacent triangles. The key idea is to search not only combinatorially over the source images,
but also over a set of local image transformations that compensate for geometric misalignment. This broad
search space is traversed using a discrete labeling algorithm, aided by a coarsetofine strategy. Our
approach significantly improves resilience to acquisition errors, thereby allowing simple and easy creation
of textured models for use in computer graphics.
No hindsights yet.


Distributed gradientdomain processing of planar and spherical images.
ACM Trans. Graphics, 29(2), 14, 2010. (Presented at SIGGRAPH 2010.)
Spherical gradientdomain processing on a Terapixel sky.
Gradientdomain processing is widely used to edit and combine images. In this paper we extend the
framework in two directions. First, we adapt the gradientdomain approach to operate on a spherical
domain, to enable operations such as seamless stitching, dynamicrange compression, and gradientbased
sharpening over spherical imagery. An efficient streaming computation is obtained using a new spherical
parameterization with bounded distortion and localized boundary constraints. Second, we design a
distributed solver to efficiently process large planar or spherical images. The solver partitions images
into bands, streams through these bands in parallel within a networked cluster, and schedules computation
to hide the necessary synchronization latency. We demonstrate our contributions on several datasets
including the Digitized Sky Survey, a terapixel spherical scan of the night sky.
See the resulting seamless terapixel night sky in WorldWide Telescope. In this project, the image data had to be parameterized using the “TOAST” spherical map. As explained in the paper, the resulting gradientdomain solution was therefore inexact. Our subsequent paper Metricaware processing of spherical imagery shows that when working with the (commonly used) equirectangular parameterization, one can adaptively discretize the domain to achieve an efficient, exact solution over the sphere. 

Amortized supersampling.
ACM Trans. Graphics (SIGGRAPH Asia), 28(5), 2009.
Adaptive reuse of pixels from previous frames for highquality antialiasing.
We present a realtime rendering scheme that reuses shading samples from earlier time frames to achieve
practical antialiasing of procedural shaders. Using a reprojection strategy, we maintain several sets of
shading estimates at subpixel precision, and incrementally update these such that for most pixels only one
new shaded sample is evaluated per frame. The key difficulty is to prevent accumulated blurring during
successive reprojections. We present a theoretical analysis of the blur introduced by reprojection
methods. Based on this analysis, we introduce a nonuniform spatial filter, an adaptive recursive temporal
filter, and a principled scheme for locally estimating the spatial blur. Our scheme is appropriate for
antialiasing shading attributes that vary slowly over time. It works in a single rendering pass on
commodity graphics hardware, and offers results that surpass 4x4 stratified supersampling in quality, at a
fraction of the cost.
Some related work is being pursued in the CryEngine 3 game platform,
as described by Anton Kaplanyan in a
SIGGRAPH
2010 course.
It also seems related to the temporal reprojection in
NVIDIA TXAA,
although there are few details on its
technology.


Parallel Poisson surface reconstruction.
International Symposium on Visual Computing 2009.
Parallelization of Poisson reconstruction using domain decomposition.
In this work we describe a parallel implementation of the Poisson Surface Reconstruction algorithm based on
multigrid domain decomposition. We compare implementations using different models of datasharing between
processors and show that a parallel implementation with distributed memory provides the best scalability.
Using our method, we are able to parallelize the reconstruction of models from one billion data points on
twelve processors across three machines, providing a ninefold speedup in running time without sacrificing
reconstruction accuracy.
See also the original
Poisson surface reconstruction
paper.


Parallel viewdependent levelofdetail control.
IEEE Trans. Vis. Comput. Graphics, 16(5), 2010.
Extended journal version with applications.
We present a scheme for viewdependent levelofdetail control that is implemented entirely on programmable
graphics hardware. Our scheme selectively refines and coarsens an arbitrary triangle mesh at the
granularity of individual vertices to create meshes that are highly adapted to dynamic view parameters.
Such finegrain control has previously been demonstrated using sequential CPU algorithms. However, these
algorithms involve pointerbased structures with intricate dependencies that cannot be handled efficiently
within the restricted framework of GPU parallelism.We show that by introducing new data structures and
dependency rules, one can realize finegrain progressive mesh updates as a sequence of parallel streaming
passes over the mesh elements. A major design challenge is that the GPU processes stream elements in
isolation. The mesh update algorithm has time complexity proportional to the selectively refined mesh, and
moreover can be amortized across several frames. The result is a single standard index buffer than can be
used directly for rendering. The static data structure is remarkably compact, requiring only 57% more
memory than an indexed triangle list. We demonstrate realtime exploration of complex models with normals
and textures, as well as shadowing and semitransparent surface rendering applications that make direct use
of the resulting dynamic index buffer.
This expanded version of the
conference paper
includes new diagrams and demonstrates some more rendering applications.


Parallel viewdependent refinement of progressive meshes.
Symposium on Interactive 3D Graphics and Games 2009, 169176.
Selective refinement of irregular mesh hierarchy using GPU streaming passes.
We present a scheme for viewdependent levelofdetail control that is implemented entirely on programmable
graphics hardware. Our scheme selectively refines and coarsens an arbitrary triangle mesh at the
granularity of individual vertices, to create meshes that are highly adapted to dynamic view parameters.
Such finegrain control has previously been demonstrated using sequential CPU algorithms. However, these
algorithms involve pointerbased structures with intricate dependencies that cannot be handled efficiently
within the restricted framework of GPU parallelism. We show that by introducing new data structures and
dependency rules, one can realize finegrain progressive mesh updates as a sequence of parallel streaming
passes over the mesh elements. A major design challenge is that the GPU processes stream elements in
isolation. The mesh update algorithm has time complexity proportional to the selectively refined mesh, and
moreover can be amortized across several frames. The static data structure is remarkably compact,
requiring only 57% more memory than an indexed triangle list. We demonstrate realtime exploration of
complex models with normals and textures.
We were invited to write an expanded version
of this conference paper in the IEEE Trans. Vis. Comput. Graphics journal.


Efficient traversal of mesh edges using adjacency primitives.
ACM Trans. Graphics (SIGGRAPH Asia), 27(5), 2008.
Fast rendering of shadow volumes, silhouettes, and motion blur.
Processing of mesh edges lies at the core of many advanced realtime rendering techniques, ranging from
shadow and silhouette computations, to motion blur and fur rendering. We present a scheme for efficient
traversal of mesh edges that builds on the adjacency primitives and programmable geometry shaders
introduced in recent graphics hardware. Our scheme aims to minimize the number of primitives while
maximizing SIMD parallelism. These objectives reduce to a set of discrete optimization problems on the
dual graph of the mesh, and we develop practical solutions to these graph problems. In addition, we extend
two existing vertex cache optimization algorithms to produce cacheefficient traversal orderings for
adjacency primitives. We demonstrate significant runtime speedups for several practical realtime
rendering algorithms.
It would be nice to extend this approach to the larger patch primitives
introduced in the
DirectX 11 hull shader.


Randomaccess rendering of general vector graphics.
ACM Trans. Graphics (SIGGRAPH Asia), 27(5), 2008.
GPU rendering of vector art over surfaces using cellspecialized descriptions.
We introduce a novel representation for randomaccess rendering of antialiased vector graphics on the GPU,
along with efficient encoding and rendering algorithms. The representation supports a broad class of
vector primitives, including multiple layers of semitransparent filled and stroked shapes, with quadratic
outlines and color gradients. Our approach is to create a coarse lattice in which each cell contains a
variablelength encoding of the graphics primitives it overlaps. These cellspecialized encodings are
interpreted at runtime within a pixel shader. Advantages include localized memory access and the ability
to map vector graphics onto arbitrary surfaces, or under arbitrary deformations. Most importantly, we
perform both prefiltering and supersampling within a single pixel shader invocation, achieving
interprimitive antialiasing at no added memory bandwidth cost. We present an efficient encoding
algorithm, and demonstrate highquality realtime rendering of complex, realworld examples.
One natural next step is to perform realtime conversion from the vector graphics primitives to the cellspecialized representation. This might be feasible with the increasing parallelism of the CPU. Also, it would be great to revisit the antialiasing at shape corners and for thin shapes, to further improve prefiltering for small primitives like fonts. Our earlier version of this paper, Texel programs for randomaccess antialiased vector graphics (MSRTR200795), also describes how a perfect hash data structure can be adapted as an alternative to the 2D indirection table. 

Factoring repeated content within and among images.
ACM Trans. Graphics (SIGGRAPH), 27(3), 2008.
Megatexture encoded by indirecting into an optimized epitome image.
We reduce transmission bandwidth and memory space for images by factoring their repeated content. A
transform map and a condensed epitome are created such that all image blocks can be reconstructed from
transformed epitome patches. The transforms may include affine deformation and color scaling to account
for perspective and tonal variations across the image. The factored representation allows efficient
randomaccess through a simple indirection, and can therefore be used for realtime texture mapping without
expansion in memory. Our scheme is orthogonal to traditional image compression, in the sense that the
epitome is amenable to further compression such as DXT. Moreover it allows a new mode of progressivity,
whereby generic features appear before unique detail. Factoring is also effective across a collection of
images, particularly in the context of imagebased rendering. Eliminating redundant content lets us
include textures that are several times as large in the same memory space.
No hindsights yet.


Streaming multigrid for gradientdomain operations on large images.
ACM Trans. Graphics (SIGGRAPH), 27(3), 2008.
Perform k multigrid Vcycles in just k1 streaming passes over the
data.
We introduce a new tool to solve the large linear systems arising from gradientdomain image processing.
Specifically, we develop a streaming multigrid solver, which needs just two sequential passes over
outofcore data. This fast solution is enabled by a combination of three techniques: (1) use of
secondorder finite elements (rather than traditional finite differences) to reach sufficient accuracy in a
single Vcycle, (2) temporally blocked relaxation, and (3) multilevel streaming to pipeline the
restriction and prolongation phases into single streaming passes. A key contribution is the extension of
the Bspline finiteelement method to be compatible with the forwarddifference gradient representation
commonly used with images. Our streaming solver is also efficient for inmemory images, due to its fast
convergence and excellent cache behavior. Remarkably, it can outperform spatially adaptive solvers that
exploit applicationspecific knowledge. We demonstrate seamless stitching and tonemapping of gigapixel
images in about an hour on a notebook PC.
In later work, we
distributed
the solver computation over a cluster to handle terapixel images,
and generalized the approach to operate over
spherical imagery.


Multiview stereo for community photo collections.
IEEE International Conference on Computer Vision (ICCV) 2007.
Detailed 3D models reconstructed from crawled Internet images.
We present a multiview stereo algorithm that addresses the extreme changes in lighting, scale, clutter,
and other effects in large online community photo collections. Our idea is to intelligently choose images
to match, both at a perview and perpixel level. We show that such adaptive view selection enables robust
performance even with dramatic appearance variability. The stereo matching technique takes as input sparse
3D points reconstructed from structurefrommotion methods and iteratively grows surfaces from these
points. Optimizing for surface normals within a photoconsistency measure significantly improves the
matching results. While the focus of our approach is to estimate highquality depth maps, we also show
examples of merging the resulting depth maps into compelling scene reconstructions. We demonstrate our
algorithm on standard multiview stereo datasets and on casually acquired photo collections of famous
scenes gathered from the Internet.
One application may be to provide useful 3D impostors to improve view interpolation for imagebased
rendering systems like Photosynth.


Design of tangent vector fields.
ACM Trans. Graphics (SIGGRAPH), 26(3), 2007.
Interactive control of direction fields for realtime surface texture synthesis.
Tangent vector fields are an essential ingredient in controlling surface appearance for applications
ranging from anisotropic shading to texture synthesis and nonphotorealistic rendering. To achieve a
desired effect one is typically interested in smoothly varying fields that satisfy a sparse set of
userprovided constraints. Using tools from Discrete Exterior Calculus, we present a simple and efficient
algorithm for designing such fields over arbitrary triangle meshes. By representing the field as scalars
over mesh edges (i.e. discrete 1forms), we obtain an intrinsic, coordinatefree formulation in which
field smoothness is enforced through discrete Laplace operators. Unlike previous methods, such a
formulation leads to a linear system whose sparsity permits efficient prefactorization. Constraints are
incorporated through weighted least squares and can be updated rapidly enough to enable interactive design,
as we demonstrate in the context of anisotropic texture synthesis.
One generalization is Nsymmetry fields as in Palacios and Zhang 2007 and Ray et al 2008. A common drawback in most linear approaches (including ours) is that the objective functional underpenalizes smoothness of the vector field in regions where the vectors have small magnitude. The work of Crane et al. 2010 overcomes this by optimizing over direction angles instead of vectors. 

Compressed randomaccess trees for spatially coherent data.
Symposium on Rendering 2007.
Efficient representation of coherent image data such as lightmaps and alpha mattes.
Adaptive multiresolution hierarchies are highly efficient at representing spatially coherent graphics data.
We introduce a framework for compressing such adaptive hierarchies using a compact randomlyaccessible tree
structure. Prior schemes have explored compressed trees, but nearly all involve entropy coding of a
sequential traversal, thus preventing finegrain random queries required by rendering algorithms. Instead,
we use fixedrate encoding for both the tree topology and its data. Key elements include the replacement
of pointers by local offsets, a forested mipmap structure, vector quantization of interlevel residuals,
and efficient coding of partially defined data. Both the offsets and codebook indices are stored as byte
records for easy parsing by either CPU or GPU shaders. We show that continuous mipmapping over an adaptive
tree is more efficient using primal subdivision than traditional dual subdivision. Finally, we demonstrate
efficient compression of many data types including light maps, alpha mattes, distance fields, and HDR
images.
The compressed tree structure can also be used for lossless compression,
by replacing vector quantization with simple storage of the residual vectors.


Unconstrained isosurface extraction on arbitrary octrees.
Symposium on Geometry Processing 2007.
Highly adaptable watertight surface from an unconstrained octree.
This paper presents a novel algorithm for generating a watertight levelset from an octree. We show that
the levelset can be efficiently extracted regardless of the topology of the octree or the values assigned
to the vertices. The key idea behind our approach is the definition of a set of binary edgetrees derived
from the octree's topology. We show that the edgetrees can be used define the positions of the
isovaluecrossings in a consistent fashion and to resolve inconsistencies that may arise when a single edge
has multiple isovaluecrossings. Using the edgetrees, we show that a provably watertight mesh can be
extracted from the octree without necessitating the refinement of nodes or modification of their values.
No hindsights yet.


Multilevel streaming for outofcore surface reconstruction.
Symposium on Geometry Processing 2007.
Outofcore solution of huge Poisson system to reconstruct 3D scans.
Reconstruction of surfaces from huge collections of scanned points often requires outofcore techniques,
and most such techniques involve local computations that are not resilient to data errors. We show that a
Poissonbased reconstruction scheme, which considers all points in a global analysis, can be performed
efficiently in limited memory using a streaming framework. Specifically, we introduce a multilevel
streaming representation, which enables efficient traversal of a sparse octree by concurrently advancing
through multiple streams, one per octree level. Remarkably, for our reconstruction application, a
sufficiently accurate solution to the global linear system is obtained using a single iteration of cascadic
multigrid, which can be evaluated within a single multistream pass. We demonstrate scalable performance
on several large datasets.
The streaming algorithm in this paper implements a prolongationonly (i.e. cascadic) multigrid solver over
an adaptive 3D octree.
In our ISVC 2009 paper,
we apply domain decomposition to parallelize this cascadic multigrid computation.
Our SIGGRAPH 2008 paper
achieves a full Vcycle multigrid as a streaming algorithm,
although over a regular grid rather than an adaptive quadtree.


Poisson surface reconstruction.
Symposium on Geometry Processing 2006, 6170.
Reconstruction that considers all points at once for resilience to data noise.
We show that surface reconstruction from oriented points can be cast as a spatial Poisson problem. This
Poisson formulation considers all the points at once, without resorting to heuristic spatial partitioning
or blending, and is therefore highly resilient to data noise. Unlike radial basis function schemes, our
Poisson approach allows a hierarchy of locally supported basis functions, and therefore the solution
reduces to a well conditioned sparse linear system. We describe a spatially adaptive multiscale algorithm
whose time and space complexities are proportional to the size of the reconstructed model. Experimenting
with publicly available scan data, we demonstrate reconstruction of surfaces with greater detail than
previously achievable.
One perceived weakness of this work is that it requires oriented normals at the input points. However, most scanning technologies provide this information, either from lineofsight knowledge or from adjacent nearby points in a range image. Experiments in [Kazhdan 2005] show that the approach is quite resilient to inaccuracies in the directions of the normals. In our subsequent SGP 2007 paper, we show that the Poisson problem can be solved outofcore for large models by introducing a multilevel streaming representation of the sparse octree. Our 2013 paper extends the approach for improved geometric fidelity and using a faster hierarchical solver. The algorithm has been incorporated into MeshLab and VTK Journal, and adapted over tetrahedral grids in CGAL. In 2011, Michael Kazhdan and Matthew Bolitho received the inaugural SGP Software Award for releasing the library code associated with this work. 

Perfect spatial hashing.
ACM Trans. Graphics (SIGGRAPH), 25(3), 2006.
Sparse spatial data packed into a dense table using a simple collisionfree map.
We explore using hashing to pack sparse data into a compact table while retaining efficient random access.
Specifically, we design a perfect multidimensional hash function — one that is precomputed on static
data to have no hash collisions. Because our hash function makes a single reference to a small offset
table, queries always involve exactly two memory accesses and are thus ideally suited for parallel SIMD
evaluation on graphics hardware. Whereas prior hashing work strives for pseudorandom mappings, we instead
design the hash function to preserve spatial coherence and thereby improve runtime locality of reference.
We demonstrate numerous graphics applications including vector images, texture sprites, alpha channel
compression, 3Dparameterized textures, 3D painting, simulation, and collision detection.
The perfect hash data structure can be generalized to represent variablesized data records as described in
Texel programs for randomaccess antialiased
vector graphics (MSRTR200795).
Alcantara et al. [2009] explore
parallel construction
of perfect spatial hashes.


Appearancespace texture synthesis.
ACM Trans. Graphics (SIGGRAPH), 25(3), 2006.
Improved synthesis quality and efficiency by pretransforming the exemplar.
The traditional approach in texture synthesis is to compare color neighborhoods with those of an exemplar.
We show that quality is greatly improved if pointwise colors are replaced by appearance vectors that
incorporate nonlocal information such as feature and radiancetransfer data. We perform dimensionality
reduction on these vectors prior to synthesis, to create a new appearancespace exemplar. Unlike a texton
space, our appearance space is lowdimensional and Euclidean. Synthesis in this informationrich space
lets us reduce runtime neighborhood vectors from 5x5 grids to just 4 locations. Building on this unifying
framework, we introduce novel techniques for coherent anisometric synthesis, surface texture synthesis
directly in an ordinary atlas, and texture advection. Remarkably, we achieve all these functionalities in
realtime, or 3 to 4 orders of magnitude faster than prior work.
The main contribution of this paper is sometimes misinterpreted:
it is not the use of PCA projection to accelerate texture neighborhood comparisons (which is
already done in [Hertzmann et al 2001; Liang et al 2001; Lefebvre and Hoppe 2005]);
rather it is the transformation of the exemplar texture itself (into a new appearance space) to let each
transformed pixel encode nonlocal information.
See Design of tangent vector fields for interactive painting of oriented texture over a surface. 

Parallel controllable texture synthesis.
ACM Trans. Graphics (SIGGRAPH), 24(3), 2005.
Parallel synthesis of infinite deterministic content, with intuitive user controls.
We present a texture synthesis scheme based on neighborhood matching, with contributions in two areas:
parallelism and control. Our scheme defines an infinite, deterministic, aperiodic texture, from which
windows can be computed in realtime on a GPU. We attain highquality synthesis using a new analysis
structure called the Gaussian stack, together with a coordinate upsampling step and a subpass correction
approach. Texture variation is achieved by multiresolution jittering of exemplar coordinates. Combined
with the local support of parallel synthesis, the jitter enables intuitive user controls including
multiscale randomness, spatial modulation over both exemplar and output, feature draganddrop, and
periodicity constraints. We also introduce synthesis magnification, a fast method for amplifying coarse
synthesis results to higher resolution.
We enhance the quality, efficiency, and functionality of the technique in our subsequent
SIGGRAPH 2006 paper.
Correction using subpasses is reminiscent of kcolor GaussSeidel updates.
A similar subpass strategy is also adapted in LiYi Wei's
Parallel Poisson disk sampling.


Fast exact and approximate geodesics on meshes.
ACM Trans. Graphics (SIGGRAPH), 24(3), 2005.
Efficient computation of shortest paths and distances on triangle meshes.
The computation of geodesic paths and distances on triangle meshes is a common operation in many computer
graphics applications. We present several practical algorithms for computing such geodesics from a source
point to one or all other points efficiently. First, we describe an implementation of the exact "single
source, all destination" algorithm presented by Mitchell, Mount, and Papadimitriou (MMP). We show that the
algorithm runs much faster in practice than suggested by worst case analysis. Next, we extend the
algorithm with a merging operation to obtain computationally efficient and accurate approximations with
bounded error. Finally, to compute the shortest path between two given points, we use a lowerbound
property of our approximate geodesic algorithm to efficiently prune the frontier of the MMP algorithm,
thereby obtaining an exact solution even more quickly.
This computation of geodesic distances is used to improve the texture atlas parameterizations produced by
the DirectX
UVAtlas tool.
See Bommes and Kobbelt
2007 for an interesting extension to compute geodesics from more general (nonpoint) sources.


Terrain rendering using GPUbased geometry clipmaps.
GPU Gems 2, M. Pharr and R. Fernando, eds., AddisonWesley, March 2005.
Realtime terrain rendering with all data processing on the GPU.
The geometry clipmap introduced in Losasso and Hoppe 2004 is a new levelofdetail structure for rendering
terrains. It caches terrain geometry in a set of nested regular grids, which are incrementally shifted as
the viewer moves. The grid structure provides a number of benefits over previous irregularmesh
techniques: simplicity of data structures, smooth visual transitions, steady rendering rate, graceful
degradation, efficient compression, and runtime detail synthesis. In this chapter, we describe a GPUbased
implementation of geometry clipmaps, enabled by vertex textures. By processing terrain geometry as a set
of images, we can perform nearly all computations on the GPU itself, thereby reducing CPU load. The
technique is easy to implement, and allows interactive flight over a 20billionsample grid of the United
States stored in just 355 MB of memory, at around 90 frames per second.
Unified shader cores in the latest graphics cards (NVIDIA GeForce 8800 and AMD Radeon HD 2900) provide
fast texture sampling in vertex shaders, making this implementation of geometry clipmaps extremely
practical.
The PTC image compressor mentioned in the paper was the precursor to the JPEG XR standard, which is supported in the WIC interface of Windows. See also the original paper and the recent book 3D Engine Design for Virtual Globes [Cozzi and Ring 2011]. 

Geometry clipmaps: Terrain rendering using nested regular grids.
ACM Trans. Graphics (SIGGRAPH), 23(3), 2004.
New terrain data structure enabling realtime decompression and synthesis.
Rendering throughput has reached a level that enables a novel approach to levelofdetail (LOD) control in
terrain rendering. We introduce the geometry clipmap, which caches the terrain in a set of nested regular
grids centered about the viewer. The grids are stored as vertex buffers in fast video memory, and are
incrementally refilled as the viewpoint moves. This simple framework provides visual continuity, uniform
frame rate, complexity throttling, and graceful degradation. Moreover it allows two new exciting realtime
functionalities: decompression and synthesis. Our main dataset is a 40GB height map of the United States.
A compressed image pyramid reduces the size by a remarkable factor of 100, so that it fits entirely in
memory. This compressed data also contributes normal maps for shading. As the viewer approaches the
surface, we synthesize grid levels finer than the stored terrain using fractal noise displacement.
Decompression, synthesis, and normalmap computations are incremental, thereby allowing interactive flight
at 60 frames/sec.
In our more recent GPU Gems 2 chapter,
we store the terrain as a set of vertex textures, thereby transferring nearly all computation to the GPU.
(See the demo available there.)
The PTC image compressor mentioned in the paper was the precursor to the JPEG XR standard, which is supported in the WIC interface of Windows. 

Digital photography with flash and noflash image pairs.
ACM Trans. Graphics (SIGGRAPH), 23(3), 2004.
Combining detail of a flash image with ambient lighting of a nonflash image.
Digital photography has made it possible to quickly and easily take a pair of images of lowlight
environments: one with flash to capture detail and one without flash to capture ambient illumination. We
present a variety of applications that analyze and combine the strengths of such flash/noflash image
pairs. Our applications include denoising and detail transfer (to merge the ambient qualities of the
noflash image with the highfrequency flash detail), whitebalancing (to change the color tone of the
ambient image), continuous flash (to interactively adjust flash intensity), and redeye removal (to repair
artifacts in the flash image). We demonstrate how these applications can synthesize new images that are of
higher quality than either of the originals.
Equation (9) in the paper has a typo; it should be “C_{p} = A_{p} / Δ_{p}”. I really like the image deblurring work of Yuan et al 2007 which uses a blurred/noisy image pair. I had earlier worked on Continuous Flash (demo). 

Intersurface mapping.
ACM Trans. Graphics (SIGGRAPH), 23(3), 2004.
Automatic creation of lowdistortion parametrizations between meshes.
We consider the problem of creating a map between two arbitrary triangle meshes. Whereas previous
approaches compose parametrizations over a simpler intermediate domain, we directly create and optimize a
continuous map between the meshes. Map distortion is measured with a new symmetric metric, and is
minimized during interleaved coarsetofine refinement of both meshes. By explicitly favoring low
intersurface distortion, we obtain maps that naturally align corresponding shape elements. Typically, the
user need only specify a handful of feature correspondences for initial registration, and even these
constraints can be removed during optimization. Our method robustly satisfies hard constraints if desired.
Intersurface mapping is shown using geometric and attribute morphs. Our general framework can also be
applied to parametrize surfaces onto simplicial domains, such as coarse meshes (for semiregular
remeshing), and octahedron and toroidal domains (for geometry image remeshing). In these settings, we
obtain better parametrizations than with previous specialized techniques, thanks to our finegrain
optimization.
No hindsights yet.


Removing excess topology from isosurfaces.
ACM Trans. Graphics, 23(2), April 2004, 190208.
Repair of tiny topological handles in scanned surface models.
Many highresolution surfaces are created through isosurface extraction from volumetric representations,
obtained by 3D photography, CT, or MRI. Noise inherent in the acquisition process can lead to geometrical
and topological errors. Reducing geometrical errors during reconstruction is well studied. However,
isosurfaces often contain many topological errors in the form of tiny handles. These nearly
invisible artifacts hinder subsequent operations like mesh simplification, remeshing, and parametrization.
In this article we present a practical method for removing handles in an isosurface. Our algorithm makes
an axisaligned sweep through the volume to locate handles, compute their sizes, and selectively remove
them. The algorithm is designed to facilitate outofcore execution. It finds the handles by
incrementally constructing and analyzing a Reeb graph. The size of a handle is measured by a short
nonseparating cycle. Handles are removed robustly by modifying the volume rather than attempting "mesh
surgery". Finally, the volumetric modifications are spatially localized to preserve geometrical detail.
We demonstrate topology simplification on several complex models, and show its benefits for subsequent
surface processing.
This topologically repaired Buddha model has been used in a number of subsequent papers. Topological analysis of arbitrary meshes using Morse functions is also explored in Ni et al 2004 and Pascucci et al 2007. This paper was previously available as the technical report MSRTR200228. 

Signalspecialized parameterization for piecewise linear reconstruction.
Symposium on Geometry Processing 2004, 5766.
Optimizing texture coordinates based on nonlinearity of texture content.
We propose a metric for surface parameterization specialized to its signal that can be used to create more
efficient, highquality texture maps. Derived from Taylor expansion of signal error, our metric predicts
the signal approximation error  the difference between the original surface signal and its reconstruction
from the sampled texture. Unlike previous methods, our metric assumes piecewiselinear reconstruction, and
thus makes a good approximation to bilinear reconstruction employed in graphics hardware. We achieve
significant savings in texture area for a desired signal accuracy compared to the signalspecialized
parameterization metric proposed by Sander et al. in the 2002 Eurographics Workshop on Rendering.
Many of our ideas (signalspecialization, integrated metric tensor, atlas
packing, etc.) have been adapted in the
UVAtlas
technology of the Microsoft
Direct3D SDK.


Consistent spherical parameterization.
Computer Graphics and Geometric Modeling (CGGM) 2005 Workshop.
Lowdistortion mapping between genuszero shapes.
Many applications benefit from surface parameterization, including texture mapping, morphing, remeshing,
compression, object recognition, and detail transfer, because processing is easier on the domain than on
the original irregular mesh. We present a method for simultaneously parameterizing several genus0 meshes
possibly with boundaries onto a common spherical domain, while ensuring that corresponding userhighlighted
features on each of the meshes map to the same domain locations. We obtain visually smooth
parameterizations without any cuts, and the constraints enable us to directly associate semantically
important features such as animal limbs or facial detail. Our method is robust and works well with either
sparse or dense sets of constraints.
No hindsights yet.


Shape compression using spherical geometry images.
MINGLE 2003 Workshop.
In Advances in Multiresolution for Geometric Modelling,
N. Dodgson, M. Floater, M. Sabin (eds.), SpringerVerlag, 2746.
Concise shape description exploiting 2D image compression techniques.
We recently introduced an algorithm for spherical parametrization and remeshing, which allows resampling of
a genuszero surface onto a regular 2D grid, a spherical geometry image. These geometry images offer
several advantages for shape compression. First, simple extension rules extend the square image domain to
cover the infinite plane, thereby providing a globally smooth surface parametrization. The 2D grid
structure permits use of ordinary image wavelets, including higherorder wavelets with polynomial
precision. The coarsest wavelets span the entire surface and thus encode the lowest frequencies of the
shape. Finally, the compression and decompression algorithms operate on ordinary 2D arrays, and are thus
ideally suited for hardware acceleration. In this paper, we detail two waveletbased approaches for shape
compression using spherical geometry images, and provide comparisons with previous compression schemes.
It is interesting that we obtain compression rates that are more aggressive than in traditional image
compression. This reflects the fact that the geometry of individual shapes is rather smooth, and in some
sense contains less information than typical images.


Smooth geometry images.
Symposium on Geometry Processing 2003, 138145.
Subdivision and displacement of genuszero mesh realized as GPU image processing.
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.
After publication, we were able to merge the splitting and averaging steps into a single rasterization
pass.
The new feature of vertex textures in DirectX9 provide another technique for cycling rasterization output
back into the vertex stream.
Being able to process geometry as images within the highly parallel GPU rasterizer is exciting.


Spherical parametrization and remeshing.
ACM Trans. Graphics (SIGGRAPH), 22(3), 2003.
Robust mapping of a surface onto a sphere, allowing 2Dgrid resampling.
The traditional approach for parametrizing a surface involves cutting it into charts and mapping these
piecewise onto a planar domain. We introduce a robust technique for directly parametrizing a genuszero
surface onto a spherical domain. A key ingredient for making such a parametrization practical is the
minimization of a stretchbased measure, to reduce scaledistortion and thereby prevent undersampling. Our
second contribution is a scheme for sampling the spherical domain using uniformly subdivided polyhedral
domains, namely the tetrahedron, octahedron, and cube. We show that these particular semiregular
samplings can be conveniently represented as completely regular 2D grids, i.e. geometry images. Moreover,
these images have simple boundary extension rules that aid many processing operations. Applications
include geometry remeshing, levelofdetail, morphing, compression, and smooth surface subdivision.
The execution times listed in the paper were reduced by a factor of 5
after further code optimization (see Talk slides).
Our approach avoids a fundamental limitation of the traditional conformal parametrization, which is that the solution may simply run out of numerical precision due to the severe scale distortion. Intersurface mapping allows direct optimization of the map over the octahedron, rather than through the sphere intermediary, resulting in improved parametrization efficiency and reconstruction accuracy. Polycube maps are an interesting generalization of our cube parametrization. Our flatoctahedron parametrization can be seen as using a Euclidean domain with 4 cone singularities, each of 180 degrees. 

Multichart geometry images.
Symposium on Geometry Processing 2003, 146155.
Surface shape represented using an atlas of charts within a regular grid.
We introduce multichart geometry images, a new representation for arbitrary surfaces. It is created by
resampling a surface onto a regular 2D grid. Whereas the original scheme of Gu et al. maps the entire
surface onto a single square, we use an atlas construction to map the surface piecewise onto charts of
arbitrary shape. We demonstrate that this added flexibility reduces parametrization distortion and thus
provides greater geometric fidelity, particularly for shapes with long extremities, high genus, or
disconnected components. Traditional atlas constructions suffer from discontinuous reconstruction across
chart boundaries, which in our context create unacceptable surface cracks. Our solution is a novel
zippering algorithm that creates a watertight surface. In addition, we present a new atlas chartification
scheme based on clustering optimization.
There is probably room for improvement in the zippering process, which is
important for uniform texture sampling.


Geometry videos: A new representation for 3D animations.
Symposium on Computer Animation 2003, 136146.
3D animated shape represented as a geometryimage volume.
We present the "Geometry Video", a new data structure to encode animated meshes. Being able to encode
animated meshes in a generic sourceindependent format allows people to share experiences. Changing the
viewpoint allows more interaction than the fixed view supported by 2D video. Geometry videos are based on
the "Geometry Image" mesh representation introduced by Gu et al. Our novel data structure provides a way
to treat an animated mesh as a video sequence (i.e. 3D image) and is well suited for network streaming.
This representation also offers the possibility of applying and adapting existing mature video processing
and compression techniques (such as MPEG encoding) to animated meshes. This paper describes an algorithm
to generate geometry videos from animated meshes.
The main insight of this paper, is that Geometry Videos resample and reorganize the geometry information, in such a way, that it becomes very compressible. They provide a unified and intuitive method for levelofdetail control, both in terms of mesh resolution (by scaling the two spatial dimensions) and of frame rate (by scaling the temporal dimension). Geometry Videos have a very uniform and regular structure. Their resource and computational requirements can be calculated exactly, hence making them also suitable for applications requiring level of service guarantees.
No hindsights yet.


Geometry images.
ACM Trans. Graphics (SIGGRAPH), 21(3), 2002.
Connectivityfree resampling of an arbitrary shape into a regular 2D grid.
Surface geometry is often modeled with irregular triangle meshes. The process of remeshing refers to
approximating such geometry using a mesh with (semi)regular connectivity, which has advantages for many
graphics applications. However, current techniques for remeshing arbitrary surfaces create only
semiregular meshes. The original mesh is typically decomposed into a set of disklike charts,
onto which the geometry is parametrized and sampled. In this paper, we propose to remesh an arbitrary
surface onto a completely regular structure we call a geometry image. It captures
geometry as a simple 2D array of quantized points. Surface signals like normals and colors are stored in
similar 2D arrays using the same implicit surface parametrization — texture coordinates are absent.
To create a geometry image, we cut an arbitrary mesh along a network of edge paths, and parametrize the
resulting single chart onto a square. Geometry images can be encoded using traditional image compression
algorithms, such as waveletbased coders.
Geometry images have the potential to simplify the rendering pipeline,
since they eliminate the "gather" operations associated with vertex
indices and texture coordinates.
Although the paper emphasizes the exciting possibilities of resampling
mesh geometry into an image,
the same parametrization scheme can also be used to construct singlechart
parametrizations over irregular meshes, for seamfree texture mapping.
The irregular "cruft" present in several of the parametrizations is
addressed by the inversestretch regularization term described in the
2003 Spherical Parametrization paper.


Signalspecialized parametrization.
Eurographics Workshop on Rendering 2002, 87100.
Optimization of texture coordinates for accurate representation of given content.
To reduce memory requirements for texture mapping a model, we build a surface parametrization specialized
to its signal (such as color or normal). Intuitively, we want to allocate more texture samples in regions
with greater signal detail. Our approach is to minimize signal approximation error — the difference
between the original surface signal and its reconstruction from the sampled texture. Specifically, our
signalstretch parametrization metric is derived from a Taylor expansion of signal error. For fast
evaluation, this metric is preintegrated over the surface as a metric tensor. We minimize this nonlinear
metric using a novel coarsetofine hierarchical solver, further accelerated with a finetocoarse
propagation of the integrated metric tensor. Use of metric tensors permits anisotropic squashing of the
parametrization along directions of low signal gradient. Texture area can often be reduced by a factor of
4 for a desired signal accuracy compared to nonspecialized parametrizations.
See also our followup work at SGP 2004
where we further improve the parameterization to account for the local linear reconstruction provided by
hardware texture sampling.


Texture mapping progressive meshes.
ACM SIGGRAPH 2001 Proceedings, 409416.
Texture atlas compatible across levels of detail, and parameterization stretch.
Given an arbitrary mesh, we present a method to construct a progressive mesh (PM) such that all meshes in
the PM sequence share a common texture parametrization. Our method considers two important goals
simultaneously. It minimizes texture stretch (small texture distances mapped onto large surface distances)
to balance sampling rates over all locations and directions on the surface. It also minimizes texture
deviation ("slippage" error based on parametric correspondence) to obtain accurate textured mesh
approximations. The method begins by partitioning the mesh into charts using planarity and compactness
heuristics. It creates a stretchminimizing parametrization within each chart, and resizes the charts
based on the resulting stretch. Next, it simplifies the mesh while respecting the chart boundaries. The
parametrization is reoptimized to reduce both stretch and deviation over the whole PM sequence. Finally,
the charts are packed into a texture atlas. We demonstrate using such atlases to sample color and normal
maps over several models.
The geometricstretch parametrization introduced in this paper is a nice principled contribution,
and should have been given stronger emphasis.
Signalspecialized parametrization (2002)
presents a hierarchical algorithm to efficiently compute this parametrization on large patches, and shows
that the chart boundary need not be fixed but can be optimized as well.
The irregular "cruft" present in several of the parametrizations is addressed by the inversestretch
regularization term described in the 2003
Spherical Parametrization paper.
Many of our ideas (signalspecialization, integrated metric tensor, atlas packing, etc.) have been adapted in the UVAtlas technology of the Microsoft Direct3D SDK. 

Fine tone control in hardware hatching.
Symposium on NonPhotorealistic Animation and Rendering (NPAR) 2002, 5358.
Crisper rendering of illuminationmodulated ink strokes.
Recent advances in NPR have enabled realtime rendering of 3D models shaded with hatching strokes for use
in interactive applications. The key challenges in realtime hatching are to convey tone by dynamically
adjusting stroke density, while controlling stroke size and maintaining frametoframe coherence. In this
paper, we introduce two new realtime hatching schemes that leverage recent advances in texture mapping
hardware. Both schemes provide enhanced control of tone, thereby avoiding blending or aliasing artifacts
present in previous systems. The first scheme, which relies on volume rendering hardware, admits the use
of color. The second scheme, which uses pixel shaders, allows perpixel lighting operations such as
texture modulation. Both schemes run at interactive rates on inexpensive PC graphics cards.
Our perpixel thresholding scheme creates spatially antialiased black
strokes. The funny thing is that in animations, some people prefer
the blended gray strokes from our original 2001
Realtime hatching paper.


Realtime hatching.
ACM SIGGRAPH 2001 Proceedings, 581586.
Fast nonphotorealistic rendering using precomputed tonal art maps.
Drawing surfaces using hatching strokes simultaneously conveys material, tone, and form. We present a
realtime system for nonphotorealistic rendering of hatching strokes over arbitrary surfaces. During an
automatic preprocess, we construct a sequence of mipmapped hatch images corresponding to different tones,
collectively called a tonal art map. Strokes within the hatch images are scaled to attain
appropriate stroke size and density at all resolutions, and are organized to maintain coherence across
scales and tones. At runtime, hardware multitexturing blends the hatch images over the rendered faces to
locally vary tone while maintaining both spatial and temporal coherence. To render strokes over arbitrary
surfaces, we build a lapped texture parametrization where the overlapping patches align to a
curvaturebased direction field. We demonstrate hatching strokes over complex surfaces in a variety of
styles.
Hatching and other nonphotorealistic effects have become popular
in a number of computer games.
Our NPAR 2002 paper shows how blending is
made simpler using volume textures, and describes a perpixel thresholding scheme for more realistic pen
strokes.


Realtime fur over arbitrary surfaces.
Symposium on Interactive 3D Graphics 2001, 227232.
Rendering of shells and fins over general meshes.
We introduce a method for realtime rendering of fur on surfaces of arbitrary topology. As a preprocess,
we simulate virtual hair with a particle system, and sample it into a volume texture. Next, we
parameterize the texture over a surface of arbitrary topology using "lapped textures" — an approach
for applying a sample texture to a surface by repeatedly pasting patches of the texture until the surface
is covered. The use of lapped textures permits specifying a global direction field for the fur over the
surface. At runtime, the patches of volume textures are rendered as a series of concentric shells of
semitransparent medium. To improve the visual quality of the fur near silhouettes, we place "fins" normal
to the surface and render these using conventional 2D texture maps sampled from the volume texture in the
direction of hair growth. The method generates convincing imagery of fur at interactive rates for models
of moderate complexity. Furthermore, the scheme allows realtime modification of viewing and lighting
conditions, as well as local control over hair color, length, and direction.
Don't you just feel like "shaking the bunny" to see its hair move?
It can be done by locally shearing the shells according to a
simple physical simulation (see here).
The "fin" rendering introduced in this paper has become popular in games,
and has become more efficient with geometry shaders in DirectX 10.


Lapped textures.
ACM SIGGRAPH 2000 Proceedings, 465470.
Texture synthesis over arbitrary surfaces.
We present a method for creating texture over an arbitrary surface mesh using an example 2D texture. The
approach is to identify interesting regions (texture patches) in the 2D example, and to repeatedly
paste them onto the surface until it is completely covered. We call such a collection of overlapping
patches a lapped texture. It is rendered using compositing operations, either into a traditional
global texture map during a preprocess, or directly with the surface at runtime. The runtime compositing
approach avoids resampling artifacts and drastically reduces texture memory requirements.
Through a simple interface, the user specifies a tangential vector field over the surface, providing local control over the texture scale, and for anisotropic textures, the orientation. To paste a texture patch onto the surface, a surface patch is grown and parametrized over texture space. Specifically, we optimize the parametrization of each surface patch such that the tangential vector field aligns everywhere with the standard frame of the texture patch. We show that this optimization is solved efficiently as a sparse linear system.
We originally entitled this submission "Synthesizing surface texture by
example". Perhaps we should have stuck to that title, because surface
texture synthesis became a hot topic the following year.
For isotropic textures, the Least squares conformal map is a nice alternative for local parametrization. In our setting, it corresponds to minimizing ϕ(S)  rot90(ϕ(T))^{2} instead of our functional ϕ(S)  s^^{2} + ϕ(T)  t^^{2}. (Both minimizations are linear problems.) Several papers have improved our technique by adjusting the locations and extents of the patches to make their boundaries less perceptible. 

Displaced subdivision surfaces.
ACM SIGGRAPH 2000 Proceedings, 8594.
Automatic conversion of detailed mesh to displaced surface, and its benefits.
In this paper we introduce a new surface representation, the displaced subdivision surface. It
represents a detailed surface model as a scalarvalued displacement over a smooth domain surface. Our
representation defines both the domain surface and the displacement function using a unified subdivision
framework, allowing for simple and efficient evaluation of analytic surface properties. We present a
simple, automatic scheme for converting detailed geometric models into such a representation. The
challenge in this conversion process is to find a simple subdivision surface that still faithfully
expresses the detailed model as its offset. We demonstrate that displaced subdivision surfaces offer a
number of benefits, including geometry compression, editing, animation, scalability, and adaptive
rendering. In particular, the encoding of fine detail as a scalar function makes the
representation extremely compact.
The Curved PN triangle representation
involves simple accesses to the vertex buffer.
Although that surface representation is not C1, it may be "smooth enough"
to be similarly used as a domain surface for displacement mapping.


Discontinuity edge overdraw.
Symposium on Interactive 3D Graphics 2001, 167174.
Antialiased edges rendered along silhouettes to remove spatiotemporal jaggies.
Aliasing is an important problem when rendering triangle meshes. Efficient antialiasing techniques such as
mipmapping greatly improve the filtering of textures defined over a mesh. A major component of the
remaining aliasing occurs along discontinuity edges such as silhouettes, creases, and material boundaries.
Framebuffer supersampling is a simple remedy, but 2x2 supersampling leaves behind significant temporal
artifacts, while greater supersampling demands even more fillrate and memory. We present an alternative
that focuses effort on discontinuity edges by overdrawing such edges as antialiased lines. Although the
idea is simple, several subtleties arise. Visible silhouette edges must be detected efficiently.
Discontinuity edges need consistent orientations. They must be blended as they approach the silhouette to
avoid popping. Unfortunately, edge blending results in blurriness. Our technique balances these two
competing objectives of temporal smoothness and spatial sharpness. Finally, the best results are obtained
when discontinuity edges are sorted by depth. Our approach proves surprisingly effective at reducing
temporal artifacts commonly referred to as "crawling jaggies", with little added cost.
Since hardware framebuffer multisampling is becoming standard and
inexpensive, our proposed solution may have come too late.


Silhouette clipping.
ACM SIGGRAPH 2000 Proceedings, 327334.
Efficient computation of mesh silhouette, used to clip coarse geometry.
Approximating detailed models with coarse, texturemapped meshes results in polygonal silhouettes. To
eliminate this artifact, we introduce silhouette clipping, a framework for efficiently clipping the
rendering of coarse geometry to the exact silhouette of the original model. The coarse mesh is obtained
using progressive hulls, a novel representation with the nesting property required for proper clipping. We
describe an improved technique for constructing texture and normal maps over this coarse mesh. Given a
perspective view, silhouettes are efficiently extracted from the original mesh using a precomputed search
tree. Within the tree, hierarchical culling is achieved using pairs of anchored cones. The extracted
silhouette edges are used to set the hardware stencil buffer and alpha buffer, which in turn clip and
antialias the rendered coarse geometry. Results demonstrate that silhouette clipping can produce
renderings of similar quality to highresolution meshes in less rendering time.
One fact that we forgot to mention in the paper is that backface/silhouette testing using a traditional
"spherecone test"
AbiEzzi and Subramaniam 1994
is equivalent to testing against some (nonoptimized) anchored cone; by explicitly optimizing for
the position of the anchor as we do, one obtains a tighter culling test.
The progressive hull contribution hidden in this paper should find applications in collision detection. Some recent techniques for accelerating ray tracing make use of our precomputed silhouette edge hierarchy. Shadow generation may be another application area. 

Silhouette mapping.
Technical Report TR199, Dept. of Computer Science, Harvard University, March 1999.
Interpolation among a sparse set of precomputed object silhouettes.
Recent imagebased rendering techniques have shown success in approximating detailed models using sampled
images over coarser meshes. One limitation of these techniques is that the coarseness of the geometric
mesh is apparent in the rough polygonal silhouette of the rendering. In this paper, we present a scheme
for accurately capturing the external silhouette of a model in order to clip the approximate geometry.
Given a detailed model, silhouettes sampled from a discrete set of viewpoints about the object are collected into a silhouette map. The silhouette from an arbitrary viewpoint is then computed as the interpolation from three nearby viewpoints in the silhouette map. Pairwise silhouette interpolation is based on a visual hull approximation in the epipolar plane. The silhouette map itself is adaptively simplified by removing views whose silhouettes are accurately predicted by interpolation of their neighbors. The model geometry is approximated by a progressive hull construction, and is rendered using projected texture maps. The 3D rendering is clipped to the interpolated silhouette using stencil planes.
Our more recent Silhouette Clipping (2000)
paper extracts silhouettes from a highresolution mesh instead of interpolating from a set of precomputed
silhouettes.
Still, we have hope that the silhouette map may prove useful for using scanned silhouettes directly without
having to construct explicit mesh geometry.
Another related work is Imagebased visual hulls.


Efficient minimization of new quadric metric for simplifying meshes with appearance attributes.
Microsoft Research Technical Report MSRTR200064, June 2000.
Fast solution of quadric metric exploiting its subblock structure.
In an earlier paper we introduced a new quadric metric for simplifying triangle meshes using the edge
collapse operation. The quadric measures both the geometric accuracy of the simplified mesh surface and
the fidelity of appearance fields defined on the surface (such as normals or colors). The minimization of
this quadric metric involves solving a linear system of size (3+m)×(3+m),
where m is the number of distinct appearance attributes. The system has
only O(m) nonzero entries, so it can be solved
in O(m^{2}) time using traditional sparse solvers such as the method of
conjugate gradients. In this short addendum, we show that the special structure of the sparsity permits
the system to be solved in O(m) time.
Thanks also to John Platt for explaining Lagrange multipliers to me.


New quadric metric for simplifying meshes with appearance attributes.
IEEE Visualization 1999 Conference, 5966.
Efficient simplification metric designed around correspondence in 3D space.
Complex triangle meshes arise naturally in many areas of computer graphics and visualization. Previous
work has shown that a quadric error metric allows fast and accurate geometric simplification of meshes.
This quadric approach was recently generalized to handle meshes with appearance attributes. In this paper
we present an improved quadric error metric for simplifying meshes with attributes. The new metric, based
on geometric correspondence in 3D, requires less storage, evaluates more quickly, and results in more
accurate simplified meshes.
Meshes often have attribute discontinuities, such as surface creases and material boundaries, which require multiple attribute vectors per vertex. We show that a wedgebased mesh data structure captures such discontinuities efficiently and permits simultaneous optimization of these multiple attribute vectors. In addition to the new quadric metric, we experiment with two techniques proposed in geometric simplification, memoryless simplification and volume preservation, and show that both of these are beneficial within the quadric framework. The new scheme is demonstrated on a variety of meshes with colors and normals.
A subsequent technical report shows that the
minimization of the new quadric can be done efficiently in linear time. The present trend is to replace
pervertex attributes by texture atlases.


Optimization of mesh locality for transparent vertex caching.
ACM SIGGRAPH 1999 Proceedings, 269276.
Face reordering for efficient GPU vertex cache, advocating a FIFO policy.
Bus traffic between the graphics subsystem and memory can become a bottleneck when rendering geometrically
complex meshes. In this paper, we investigate the use of vertex caching to transparently reduce geometry
bandwidth. Use of an indexed triangle strip representation permits application programs to animate the
meshes at video rates, and provides backward compatibility on legacy hardware. The efficiency of vertex
caching is maximized by reordering the faces in the mesh during a preprocess. We present two reordering
techniques, a fast greedy stripgrowing algorithm and a local optimization algorithm. The stripgrowing
algorithm performs lookahead simulations of the cache to adapt strip lengths to the cache capacity. The
local optimization algorithm improves this initial result by exploring a set of perturbations to the face
ordering. The resulting cache miss rates are comparable to the efficiency of the earlier mesh buffer
scheme described by Deering and Chow, even though the vertex cache is not actively managed.
This technology has been transferred into the D3DX library of Microsoft DirectX
(see ID3DX10Mesh::Optimize).
We observe that optimizing meshes for vertex caching results in useful speedups on modern GPU's.
Some recent schemes including Lin and Yu 2006
and Chhugani and Kumar 2007
achieve better vertex caching behavior, but replace indexed triangle strips by indexed triangle lists,
which slightly increases the size of the index buffer.
The scheme of Sander et al 2007 is very
fast and also considers occlusion culling.


Robust mesh watermarking.
ACM SIGGRAPH 1999 Proceedings, 6976.
Imperceptible lowfrequency shape perturbations resilient to remeshing.
We describe a robust method for watermarking triangle meshes. Watermarking provides a mechanism for
copyright protection of digital media by embedding information identifying the owner in the data. The bulk
of the research on digital watermarks has focused on media such as images, video, audio, and text. Robust
watermarks must be able to survive a variety of "attacks", including resizing, cropping, and filtering.
For resilience to such attacks, recent watermarking schemes employ a "spreadspectrum" approach —
they transform the document to the frequency domain and perturb the coefficients of the perceptually most
significant basis functions. We extend this spreadspectrum approach to work for the robust watermarking
of arbitrary triangle meshes.
Generalizing spread spectrum techniques to surfaces presents two major challenges. First, arbitrary surfaces lack a natural parametrization for frequencybased decomposition. Our solution is to construct a set of scalar basis function over the mesh vertices using multiresolution analysis. The watermark perturbs vertices along the direction of the surface normal, weighted by the basis functions. The second challenge is that simplification and other attacks may modify the connectivity of the mesh. We use an optimization technique to resample an attacked mesh using the original mesh connectivity. Results show that our watermarks are resistant to common mesh operations such as translation, rotation, scaling, cropping, smoothing, simplification, and resampling, as well as malicious attacks such as the insertion of noise, modification of loworder bits, or even insertion of other watermarks.
It would be nice to run sidebyside comparisons with some other recent mesh watermarking schemes
such as Benedens 1999 or the
spectral approach of Ohbuchi et al 2001.
One major difficulty is judging the relative perceptibility of different watermarks.


Viewbased rendering: Visualizing real objects from scanned range and color data.
Eurographics Workshop on Rendering 1997, 2334.
Blending of textured depth meshes using soft zbuffering.
Modeling arbitrary real objects is difficult and rendering textured models typically does not result in
realistic images. We describe a new method for displaying scanned real objects, called
viewbased rendering. The method takes as input a collection of colored range images covering the
object and creates a collection of partial object models. These partial models are rendered separately
using traditional graphics hardware and blended together using various weights and soft zbuffering. We
demonstrate interactive viewing of real, nontrivial objects that would be difficult to model using
traditional methods.
Essentially, this approach performs runtime blending of precomputed textured depth meshes (TDMs) used as
impostors. It is yet another interesting point in the broad space of imagebased rendering techniques.


Robust meshes from multiple range maps.
Intnl. Conf. on Recent Advances in 3D Digital Imaging and Modeling, May 1997.
Robust surface reconstruction using interval analysis over volumetric octree.
This paper presents a method for modeling the surface of an object from a sequence of range maps. Our
method is based on a volumetric approach that produces a compact surface without boundary. It provides
robustness through the use of interval analysis techniques and computational efficiency through
hierarchical processing using octrees.
Unlike most volumetric integration techniques, this one does not require storage of the whole volume.


Efficient implementation of progressive meshes.
Computers & Graphics, 22(1), 1998, 2736.
Progressive mesh data structures compatible with GPU vertex buffers.
In earlier work, we introduced the progressive mesh (PM) representation, a new format for storing and
transmitting arbitrary triangle meshes. For a given mesh, the PM representation defines a continuous
sequence of levelofdetail approximations, allows smooth visual transitions (geomorphs) between these
approximations, supports progressive transmission, and makes an effective compression scheme. In this
paper, we present data structures and algorithms for efficient implementation of the PM representation and
its applications. Also, we report quantitative results using a variety of computer graphics models.
The paper details the data structures of an efficient implementation of progressive meshes.
For our more recent work with Microsoft Direct3D, the data structures have changed somewhat:
(1) wedges have become D3D vertices, and
(2) coarsening/refinement is done more efficiently using halfedge collapses.
Thanks to Craig Peeper and Anuj Gosalia, this technology has been released in the D3DX library of DirectX 8.0 (see ID3DXPMesh). A nice result in this paper is that progressive meshes can be compressed more effectively by allowing permutations of the vertex splits. 

Smooth viewdependent levelofdetail control and its application to terrain rendering.
IEEE Visualization 1998 Conference, 3542.
Visually smooth adaptation of mesh refinement using cascaded temporal geomorphs.
The key to realtime rendering of largescale surfaces is to locally adapt surface geometric complexity to
changing view parameters. Several schemes have been developed to address this problem of viewdependent
levelofdetail control. Among these, the viewdependent progressive mesh (VDPM) framework
represents an arbitrary triangle mesh as a hierarchy of geometrically optimized refinement transformations,
from which accurate approximating meshes can be efficiently retrieved. In this paper we extend the general
VDPM framework to provide temporal coherence through the runtime creation of geomorphs. These
geomorphs eliminate "popping" artifacts by smoothly interpolating geometry. Their implementation requires
new outputsensitive data structures, which have the added benefit of reducing memory use.
We specialize the VDPM framework to the important case of terrain rendering. To handle huge terrain grids, we introduce a blockbased simplification scheme that constructs a progressive mesh as a hierarchy of block refinements. We demonstrate the need for an accurate approximation metric during simplification. Our contributions are highlighted in a realtime flyover of a large, rugged terrain. Notably, the use of geomorphs results in visually smooth rendering even at 72 frames/sec on a graphics workstation.
The runtime geomorphs make this one of my favorite demos.
The irregular meshes reduce the number of triangles for a given level of approximation accuracy, and allow
large regions of the terrain to be presimplified.
This approach has been generalized to general (nonterrain) meshes, in
Chris Prince's Masters Thesis
Progressive
Meshes for Large Models of Arbitrary Topology.
In my opinion, for terrains the future lies in regularly sampled representations such as
geometry clipmaps.


Viewdependent refinement of progressive meshes.
ACM SIGGRAPH 1997 Proceedings, 189198.
Lossless multiresolution structure for incremental local refinement/coarsening.
Levelofdetail (LOD) representations are an important tool for realtime rendering of complex geometric
environments. The previously introduced progressive mesh representation defines for an arbitrary
triangle mesh a sequence of approximating meshes optimized for viewindependent LOD. In this paper, we
introduce a framework for selectively refining an arbitrary progressive mesh according to changing view
parameters. We define efficient refinement criteria based on the view frustum, surface orientation, and
screenspace geometric error, and develop a realtime algorithm for incrementally refining and coarsening
the mesh according to these criteria. The algorithm exploits view coherence, supports frame rate
regulation, and is found to require less than 15% of total frame time on a graphics workstation. Moreover,
for continuous motions this work can be amortized over consecutive frames. In addition, smooth visual
transitions (geomorphs) can be constructed between any two selectively refined meshes.
A number of previous schemes create viewdependent LOD meshes for height fields (e.g. terrains) and parametric surfaces (e.g. NURBS). Our framework also performs well for these special cases. Notably, the absence of a rigid subdivision structure allows more accurate approximations than with existing schemes. We include results for these cases as well as for general meshes.
Further enhancements on this approach are presented in my
Visualization 1998 paper.


Progressive simplicial complexes.
ACM SIGGRAPH 1997 Proceedings, 217224.
Progressive encoding of both topology and geometry.
In this paper, we introduce the progressive simplicial complex (PSC) representation, a new format for
storing and transmitting triangulated geometric models. Like the earlier progressive mesh (PM)
representation, it captures a given model as a coarse base model together with a sequence of refinement
transformations that progressively recover detail. The PSC representation makes use of a more general
refinement transformation, allowing the given model to be an arbitrary triangulation (e.g. any dimension,
nonorientable, nonmanifold, nonregular), and the base model to always consist of a single vertex.
Indeed, the sequence of refinement transformations encodes both the geometry and the topology of the model
in a unified multiresolution framework. The PSC representation retains the advantages of PM's. It defines
a continuous sequence of approximating models for runtime levelofdetail control, allows smooth
transitions between any pair of models in the sequence, supports progressive transmission, and offers a
spaceefficient representation. Moreover, by allowing changes to topology, the PSC sequence of
approximations achieves better fidelity than the corresponding PM sequence.
We develop an optimization algorithm for constructing PSC representations for graphics surface models, and demonstrate the framework on models that are both geometrically and topologically complex.
It is an elegant framework for progressively encoding topology, although perhaps overly general for
efficient implementation.
Solutions have since been developed for the case of progressive tetrahedralizations, another interesting
generalization of progressive meshes.


Progressive meshes.
ACM SIGGRAPH 1996 Proceedings, 99108.
Efficient, lossless, continuousresolution representation of surface triangulations.
Highly detailed geometric models are rapidly becoming commonplace in computer graphics. These models,
often represented as complex triangle meshes, challenge rendering performance, transmission bandwidth, and
storage capacities. This paper introduces the progressive mesh (PM) representation, a new scheme
for storing and transmitting arbitrary triangle meshes. This efficient, lossless, continuousresolution
representation addresses several practical problems in graphics: smooth geomorphing of levelofdetail
approximations, progressive transmission, mesh compression, and selective refinement.
In addition, we present a new mesh simplification procedure for constructing a PM representation from an arbitrary mesh. The goal of this optimization procedure is to preserve not just the geometry of the original mesh, but more importantly its overall appearance as defined by its discrete and scalar appearance attributes such as material identifiers, color values, normals, and texture coordinates. We demonstrate construction of the PM representation and its applications using several practical models.
More recent papers describe faster simplification criteria, such as the
quadric error metric scheme of Garland and
Heckbert,
the memoryless scheme of Lindstrom and Turk,
and my improved quadric error metric in
Visualization 1999.
But, the first 4 pages are still excellent. The paper should have made it more obvious that a geomorph can
directly transition between any two PM meshes by simultaneously moving many vertices.


Automatic reconstruction of Bspline surfaces of arbitrary topological type.
ACM SIGGRAPH 1996 Proceedings, 325334.
Fully automatic creation of Bspline patch network from 3D point cloud.
Creating freeform surfaces is a challenging task even with advanced geometric modeling systems. Laser
range scanners offer a promising alternative for model acquisition — the 3D scanning of existing
objects or clay maquettes. The problem of converting the dense point sets produced by laser scanners into
useful geometric models is referred to as surface reconstruction.
In this paper, we present a procedure for reconstructing a tensor product Bspline surface from a set of scanned 3D points. Unlike previous work which considers primarily the problem of fitting a single Bspline patch, our goal is to directly reconstruct a surface of arbitrary topological type. We must therefore define the surface as a network of Bspline patches. A key ingredient in our solution is a scheme for automatically constructing both a network of patches and a parametrization of the data points over these patches. In addition, we define the Bspline surface using a surface spline construction, and demonstrate that such an approach leads to an efficient procedure for fitting the surface while maintaining tangent plane continuity. We explore adaptive refinement of the patch network in order to satisfy userspecified error tolerances, and demonstrate our method on both synthetic and real data.
Reconstructing arbitrary Bspline surfaces is difficult, and this paper tackles the problem in a fully
automatic approach.
For some applications, it may be more practical to let the user manually specify the patch boundaries (see
the related paper by Krishnamurthy and
Levoy in the same proceedings).
Still, the surface spline construction is useful in this context for maintaining C1 continuity without
resort to constrained optimization.
Sorry, the code is not available.
Subdivision surfaces, which have gained popularity recently, make this reconstruction problem so much
easier... (see my SIGGRAPH 1994 paper).


Multiresolution analysis of arbitrary meshes.
ACM SIGGRAPH 1995 Proceedings, 173182.
Semiregular remeshing for waveletbased representation of surfaces.
In computer graphics and geometric modeling, shapes are often represented by triangular meshes. With the
advent of laser scanning systems, meshes of extreme complexity are rapidly becoming commonplace. Such
meshes are notoriously expensive to store, transmit, render, and are awkward to edit. Multiresolution
analysis offers a simple, unified, and theoretically sound approach to dealing with these problems.
Lounsbery et al. have recently developed a technique for creating multiresolution representations for a
restricted class of meshes with subdivision connectivity. Unfortunately, meshes encountered in
practice typically do not meet this requirement. In this paper we present a method for overcoming the
subdivision connectivity restriction, meaning that completely arbitrary meshes can now be converted to
multiresolution form. The method is based on the approximation of an arbitrary initial mesh M
by a mesh M^{j} that has subdivision connectivity and is guaranteed to be
within a specified tolerance.
The key ingredient of our algorithm is the construction of a parametrization of M over a simple domain. We expect this parametrization to be of use in other contexts, such as texture mapping or the approximation of complex meshes by NURBS patches.
Novel technique for parametrizing an arbitrary triangle mesh over a simpler triangular domain of the same
topological type.
Subsequently, two enhancements to this paper were presented:
Vertexbased Delaunay triangulation
(to improve the mesh partition) and
Hierarchical computation of PL harmonic embeddings
(to speed up harmonic maps).
The approach of remeshing a model to have subdivision connectivity was made more practical by the MAPS scheme of Lee et al in SIGGRAPH 1998. The paper is often cited for introducing the harmonic map in the context of mesh parametrization. This harmonic/conformal map has been generalized to allow free boundaries, in LSCM and DCP, which are in fact equivalent, and also identical to harmonic maps for fixed boundary. 

Surface reconstruction from unorganized points (PhD Thesis).
Department of Computer Science and Engineering, University of Washington, June 1994.
Robust surface topology and optimized geometry from scanned 3D points.
This thesis describes a general method for automatic reconstruction of accurate, concise, piecewise smooth
surfaces from unorganized 3D points. Instances of surface reconstruction arise in numerous scientific and
engineering applications, including reverseengineering — the automatic generation of CAD models from
physical objects.
Previous surface reconstruction methods have typically required additional knowledge, such as structure in the data, known surface genus, or orientation information. In contrast, the method outlined in this thesis requires only the 3D coordinates of the data points. From the data, the method is able to automatically infer the topological type of the surface, its geometry, and the presence and location of features such as boundaries, creases, and corners. The reconstruction method has three major phases: 1) initial surface estimation, 2) mesh optimization, and 3) piecewise smooth surface optimization. A key ingredient in phase 3, and another principal contribution of this thesis, is the introduction of a new class of piecewise smooth representations based on subdivision. The effectiveness of the threephase reconstruction method is demonstrated on a number of examples using both simulated and real data. Phases 2 and 3 of the surface reconstruction method can also be used to approximate existing surface models. By casting surface approximation as a global optimization problem with an energy function that directly measures deviation of the approximation from the original surface, models are obtained that exhibit excellent accuracy to conciseness tradeoffs. Examples of piecewise linear and piecewise smooth approximations are generated for various surfaces, including meshes, NURBS surfaces, CSG models, and implicit surfaces. Really, there was more work here than the stapling of three papers :) This surface reconstruction problem has continued to be an active area; see the recent papers by Nina Amenta and the commercial product by Geomagic. This reconstructed mannequin head is my small contribution to the pool of geometric models commonly used in graphics. See also my 2006 work Poisson surface reconstruction, which assumes oriented points but achieves greater robustness using a global (yet efficient) solution. 

Piecewise Smooth Surface Reconstruction.
ACM SIGGRAPH 1994 Proceedings, 295302.
Subdivision surfaces with sharp features, and their automatic creation by data fitting.
We present a general method for automatic reconstruction of accurate, concise, piecewise smooth surface
models from scattered range data. The method can be used in a variety of applications such as reverse
engineering — the automatic generation of CAD models from physical objects. Novel aspects of the
method are its ability to model surfaces of arbitrary topological type and to recover sharp features such
as creases and corners. The method has proven to be effective, as demonstrated by a number of examples
using both simulated and real data.
A key ingredient in the method, and a principal contribution of this paper, is the introduction of a new class of piecewise smooth surface representations based on subdivision. These surfaces have a number of properties that make them ideal for use in surface reconstruction: they are simple to implement, they can model sharp features concisely, and they can be fit to scattered range data using an unconstrained optimization procedure.
Through general optimization, this method is able to infer sharp features in the underlying geometry by
simply fitting the data points.
With the growing interest in subdivision surfaces, this surface fitting technique may prove useful.
The paper is often cited for its introduction of sharp features in subdivision surface schemes.
These features were extended in the work of
Biermann et al.
The SIGGRAPH 1998 paper
by DeRose et al. presents extensions for "fractionally smooth" surface features.


Mesh optimization.
ACM SIGGRAPH 1993 Proceedings, 1926.
Traversing the space of triangle meshes to optimize model fidelity and conciseness.
We present a method for solving the following problem: Given a set of data points scattered in three
dimensions and an initial triangular mesh M_{0}, produce a mesh M, of the same
topological type as M_{0}, that fits the data well and has a small number of vertices.
Our approach is to minimize an energy function that explicitly models the competing desires of conciseness
of representation and fidelity to the data. We show that mesh optimization can be effectively used in at
least two applications: surface reconstruction from unorganized points, and mesh simplification (the
reduction of the number of vertices in an initially dense mesh of triangles).
The technique demonstrates that general optimization can achieve surprisingly good results.
This particular optimization searches over a broad space of both discrete and continuous variables to find a
concise mesh accurately fitting a set of data points.
A similar approach was used by Lindstrom and Turk in their
Imagedriven mesh optimization work.
Mesh optimization is quite powerful for featuresensitive remeshing, as it automatically migrates vertices
onto sharp features
(e.g. as used in multichart geometry images).
For the application of mesh simplification,
progressive meshes offer a more elegant solution.


Surface reconstruction from unorganized points.
ACM SIGGRAPH 1992 Proceedings, 7178.
Signeddistance field estimated from a set of unoriented noisy points.
We describe and demonstrate an algorithm that takes as input an unorganized set of points
{x_{1}, ... , x_{n}} in R^{3} on or
near an unknown manifold M, and produces as output a simplicial surface that
approximates M. Neither the topology, the presence of boundaries, nor the geometry
of M are assumed to be known in advance — all are inferred automatically from the data.
This problem naturally arises in a variety of practical situations such as range scanning an object from
multiple view points, recovery of biological shapes from twodimensional slices, and interactive surface
sketching.
This paper addresses the difficult case where the data points have no inherent structure. This was useful for data we had obtained from the company Technical Arts, which manufactured a lasersheet scanner mounted on a coordinate measuring machine. For traditional range images which have more structure in the data, a more specialized technique is the volumetric approach of Curless and Levoy (SIGGRAPH 1996), which also uses a signeddistance implicit function. Our "Riemannian Graph" construction is similar to that used to estimate manifold geodesics in Isomap construction. See also my 2006 work Poisson surface reconstruction, which assumes oriented points but achieves greater robustness using a global (yet efficient) solution. 