Detailed Publications

Semi-automated video morphing
Semi-automated video morphing.
Jing Liao, Rodolfo Lima, Diego Nehab, Hugues Hoppe, Pedro Sander.
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 fine-scale map given only sparse user-specified 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
Automating image morphing using structural similarity on a halfway domain.
Jing Liao, Rodolfo Lima, Diego Nehab, Hugues Hoppe, Pedro Sander, Jinhui Yu.
ACM Trans. Graphics, 33(5), 2014. (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 thin-plate spline, and may be guided by a few user-drawn 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 Image-space 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
A fresh look at generalized sampling.
Diego Nehab, Hugues Hoppe.
Foundations and Trends in Computer Graphics and Vision, 8(1), 2014.
Extension of recent signal-processing techniques to graphics filtering.
Discretization and reconstruction are fundamental operations in computer graphics, enabling the conversion between sampled and continuous representations. Major advances in signal-processing research have shown that these operations can often be performed more efficiently by decomposing a filter into two parts: a compactly supported continuous-domain 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 supersample-based 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.
Automated video looping with progressive dynamism
Automated video looping with progressive dynamism.
Zicheng Liao, Neel Joshi, Hugues Hoppe.
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 time-mapping equation (1) has a simpler form: ϕ(x, t) = sx + ((t - sx) mod px). (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 bj in case (4) of page 4 has a typo; it should be bj = Vc(x, ϕ(z,j)).
(Note that the expression for Ψ includes a second set of terms (a'i - b'j)2 where a'i = Vc(z, ϕ(x,i)) and b'j = Vc(z, ϕ(z,j)).)

Screened Poisson surface reconstruction
Screened Poisson surface reconstruction.
Michael Kazhdan, Hugues Hoppe.
ACM Trans. Graphics, 32(3), 2013. (Presented at SIGGRAPH 2013.)
Improved geometric fidelity and linear-complexity 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 finite-element 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, higher-quality surface reconstructions.
See also the comments in the earlier paper Poisson surface reconstruction.
Cliplets: Juxtaposing still and dynamic imagery
Cliplets: Juxtaposing still and dynamic imagery.
Neel Joshi, Sisil Mehta, Steven Drucker, Eric Stollnitz, Hugues Hoppe, Matt Uyttendaele, Michael Cohen.
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 user-interface 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 subdivision-based representation for vector image editing
A subdivision-based representation for vector image editing.
Zicheng Liao, Hugues Hoppe, David Forsyth, Yizhou Yu.
IEEE Trans. Vis. Comput. Graphics, 18(11), Nov. 2012. (Presented at I3D 2013.)
(Spotlight Paper)
Piecewise-smooth 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 vector-based 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 feature-oriented vector image pyramid that offers multiple levels of abstraction simultaneously. Our new vector image representation can be rasterized efficiently using GPU-accelerated 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 thin-plate splines
Freeform vector graphics with controlled thin-plate splines.
Mark Finch, John Snyder, Hugues Hoppe.
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 higher-order fairing to enable more natural interpolation and greater expressive control. Specifically, we build on thin-plate splines which provide smoothness everywhere except at user-specified 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. Patch-Based Image Vectorization with Automatic Curvilinear Feature Alignment] which also introduces higher-order color reconstruction for vector graphics. It optimizes parametric Bezier patches with Thin-Plate Spline color functions to approximate a given image.
GPU-efficient recursive filtering and summed-area tables
GPU-efficient recursive filtering and summed-area tables.
Diego Nehab, André Maximo, Rodolfo Lima, Hugues Hoppe.
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 summed-area 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 causal-anticausal 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 summed-area tables [Crow 1984].
Image-space bidirectional scene reprojection
Image-space bidirectional scene reprojection.
Lei Yang, Yu-Chiu Tse, Pedro Sander, Jason Lawrence, Diego Nehab, Hugues Hoppe, Clara Wilkins.
ACM Trans. Graphics (SIGGRAPH Asia), 30(6), 2011.
Real-time temporal upsampling through image-based reprojection of adjacent frames.
We introduce a method for increasing the framerate of real-time 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 fill-bound 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 image-based 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 (3-4X) for a variety of applications, including vertex-bound and fill-bound scenes, multi-pass 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.
Real-time classification of dance gestures from skeleton animation
Real-time classification of dance gestures from skeleton animation.
Michalis Raptis, Darko Kirovski, Hugues Hoppe.
Symposium on Computer Animation 2011. (Honorable Mention)
Recognition of Kinect motions using robust, low-dimensional feature vectors.
We present a real-time 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 correlation-based classifier for multivariate time-series data, and a distance metric based on dynamic time-warping 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 gesture-matching scenario, the classifier is conceived based on the assumption that the input motion adheres to a known, canonical time-base: 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 4-second skeletal motion recordings. This accuracy is remarkable given the input noise from the real-time depth sensor.
This technology was adapted in the Kinect Star Wars video game.
Antialiasing recovery
Antialiasing recovery.
Lei Yang, Pedro Sander, Jason Lawrence, Hugues Hoppe.
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 non-photorealistic 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
Optimizing continuity in multiscale imagery.
Charles Han, Hugues Hoppe.
ACM Trans. Graphics (SIGGRAPH Asia), 29(6), 2010.
Visually continuous mipmap pyramid spanning differing coarse- and fine-scale images.
Multiscale imagery often combines several sources with differing appearance. For instance, Internet-based 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 inter-level ghosting artifacts. The second, clipped Laplacian blending, is an efficient construction to minimize blur when creating intermediate levels. It considers the sum of all inter-level image differences within the pyramid. We demonstrate continuous zooming of map imagery from space to ground level.
No hindsights yet.
Metric-aware processing of spherical imagery
Metric-aware processing of spherical imagery.
Michael Kazhdan, Hugues Hoppe.
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 metric-aware 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 reaction-diffusion texture synthesis and panorama stitching and sharpening.
No hindsights yet.
Seamless montage for texturing models
Seamless montage for texturing models.
Ran Gal, Yonatan Wexler, Eyal Ofek, Hugues Hoppe, Daniel Cohen-Or.
Computer Graphics Forum (Eurographics), 29(2), 479-486, 2010.
Optimized alignment and merging of photographs for texturing approximate geometry.
We present an automatic method to recover high-resolution texture over an object by mapping detailed photographs onto its surface. Such high-resolution 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 coarse-to-fine 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 gradient-domain processing of planar and spherical images
Distributed gradient-domain processing of planar and spherical images.
Michael Kazhdan, Dinoj Surendran, Hugues Hoppe.
ACM Trans. Graphics, 29(2), 14, 2010. (Presented at SIGGRAPH 2010.)
Spherical gradient-domain processing on a Terapixel sky.
Gradient-domain processing is widely used to edit and combine images. In this paper we extend the framework in two directions. First, we adapt the gradient-domain approach to operate on a spherical domain, to enable operations such as seamless stitching, dynamic-range compression, and gradient-based 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 gradient-domain solution was therefore inexact. Our subsequent paper Metric-aware 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
Amortized supersampling.
Lei Yang, Diego Nehab, Pedro Sander, Pitchaya Sitthi-amorn, Jason Lawrence, Hugues Hoppe.
ACM Trans. Graphics (SIGGRAPH Asia), 28(5), 2009.
Adaptive reuse of pixels from previous frames for high-quality antialiasing.
We present a real-time 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
Parallel Poisson surface reconstruction.
Matthew Bolitho, Michael Kazhdan, Randal Burns, Hugues Hoppe.
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 data-sharing 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 view-dependent level-of-detail control
Parallel view-dependent level-of-detail control.
Liang Hu, Pedro Sander, Hugues Hoppe.
IEEE Trans. Vis. Comput. Graphics, 16(5), 2010.
Extended journal version with applications.
We present a scheme for view-dependent level-of-detail 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 fine-grain control has previously been demonstrated using sequential CPU algorithms. However, these algorithms involve pointer-based 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 fine-grain 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 real-time 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 view-dependent refinement of progressive meshes
Parallel view-dependent refinement of progressive meshes.
Liang Hu, Pedro Sander, Hugues Hoppe.
Symposium on Interactive 3D Graphics and Games 2009, 169-176.
Selective refinement of irregular mesh hierarchy using GPU streaming passes.
We present a scheme for view-dependent level-of-detail 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 fine-grain control has previously been demonstrated using sequential CPU algorithms. However, these algorithms involve pointer-based 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 fine-grain 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 real-time 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
Efficient traversal of mesh edges using adjacency primitives.
Pedro Sander, Diego Nehab, Eden Chlamtac, Hugues Hoppe.
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 real-time 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 cache-efficient traversal orderings for adjacency primitives. We demonstrate significant runtime speedups for several practical real-time rendering algorithms.
It would be nice to extend this approach to the larger patch primitives introduced in the DirectX 11 hull shader.
Random-access rendering of general vector graphics
Random-access rendering of general vector graphics.
Diego Nehab, Hugues Hoppe.
ACM Trans. Graphics (SIGGRAPH Asia), 27(5), 2008.
GPU rendering of vector art over surfaces using cell-specialized descriptions.
We introduce a novel representation for random-access 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 variable-length encoding of the graphics primitives it overlaps. These cell-specialized 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 inter-primitive antialiasing at no added memory bandwidth cost. We present an efficient encoding algorithm, and demonstrate high-quality real-time rendering of complex, real-world examples.

One natural next step is to perform real-time conversion from the vector graphics primitives to the cell-specialized 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 random-access antialiased vector graphics (MSR-TR-2007-95), 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
Factoring repeated content within and among images.
Huamin Wang, Yonatan Wexler, Eyal Ofek, Hugues Hoppe.
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 random-access through a simple indirection, and can therefore be used for real-time 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 image-based 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 gradient-domain operations on large images
Streaming multigrid for gradient-domain operations on large images.
Michael Kazhdan, Hugues Hoppe.
ACM Trans. Graphics (SIGGRAPH), 27(3), 2008.
Perform k multigrid V-cycles in just k-1 streaming passes over the data.
We introduce a new tool to solve the large linear systems arising from gradient-domain image processing. Specifically, we develop a streaming multigrid solver, which needs just two sequential passes over out-of-core data. This fast solution is enabled by a combination of three techniques: (1) use of second-order finite elements (rather than traditional finite differences) to reach sufficient accuracy in a single V-cycle, (2) temporally blocked relaxation, and (3) multi-level streaming to pipeline the restriction and prolongation phases into single streaming passes. A key contribution is the extension of the B-spline finite-element method to be compatible with the forward-difference gradient representation commonly used with images. Our streaming solver is also efficient for in-memory images, due to its fast convergence and excellent cache behavior. Remarkably, it can outperform spatially adaptive solvers that exploit application-specific knowledge. We demonstrate seamless stitching and tone-mapping 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.
Multi-view stereo for community photo collections
Multi-view stereo for community photo collections.
Michael Goesele, Noah Snavely, Brian Curless, Hugues Hoppe, Steven Seitz.
IEEE International Conference on Computer Vision (ICCV) 2007.
Detailed 3D models reconstructed from crawled Internet images.
We present a multi-view 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 per-view and per-pixel 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 structure-from-motion 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 high-quality depth maps, we also show examples of merging the resulting depth maps into compelling scene reconstructions. We demonstrate our algorithm on standard multi-view 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 image-based rendering systems like Photosynth.
Design of tangent vector fields
Design of tangent vector fields.
Matthew Fisher, Peter Schröder, Mathieu Desbrun, Hugues Hoppe.
ACM Trans. Graphics (SIGGRAPH), 26(3), 2007.
Interactive control of direction fields for real-time surface texture synthesis.
Tangent vector fields are an essential ingredient in controlling surface appearance for applications ranging from anisotropic shading to texture synthesis and non-photorealistic rendering. To achieve a desired effect one is typically interested in smoothly varying fields that satisfy a sparse set of user-provided 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 1-forms), we obtain an intrinsic, coordinate-free 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 pre-factorization. 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 N-symmetry 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 under-penalizes 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 random-access trees for spatially coherent data
Compressed random-access trees for spatially coherent data.
Sylvain Lefebvre, Hugues Hoppe.
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 randomly-accessible tree structure. Prior schemes have explored compressed trees, but nearly all involve entropy coding of a sequential traversal, thus preventing fine-grain random queries required by rendering algorithms. Instead, we use fixed-rate 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 inter-level 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
Unconstrained isosurface extraction on arbitrary octrees.
Michael Kazhdan, Allison Klein, Ketan Dalal, Hugues Hoppe.
Symposium on Geometry Processing 2007.
Highly adaptable watertight surface from an unconstrained octree.
This paper presents a novel algorithm for generating a watertight level-set from an octree. We show that the level-set 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 edge-trees derived from the octree's topology. We show that the edge-trees can be used define the positions of the isovalue-crossings in a consistent fashion and to resolve inconsistencies that may arise when a single edge has multiple isovalue-crossings. Using the edge-trees, 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.
Multi-level streaming for out-of-core surface reconstruction
Multi-level streaming for out-of-core surface reconstruction.
Matthew Bolitho, Michael Kazhdan, Randal Burns, Hugues Hoppe.
Symposium on Geometry Processing 2007.
Out-of-core solution of huge Poisson system to reconstruct 3D scans.
Reconstruction of surfaces from huge collections of scanned points often requires out-of-core techniques, and most such techniques involve local computations that are not resilient to data errors. We show that a Poisson-based 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 multi-stream pass. We demonstrate scalable performance on several large datasets.
The streaming algorithm in this paper implements a prolongation-only (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 V-cycle multigrid as a streaming algorithm, although over a regular grid rather than an adaptive quadtree.
Poisson surface reconstruction
Poisson surface reconstruction.
Michael Kazhdan, Matthew Bolitho, Hugues Hoppe.
Symposium on Geometry Processing 2006, 61-70.
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 line-of-sight 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 out-of-core 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
Perfect spatial hashing.
Sylvain Lefebvre, Hugues Hoppe.
ACM Trans. Graphics (SIGGRAPH), 25(3), 2006.
Sparse spatial data packed into a dense table using a simple collision-free 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, 3D-parameterized textures, 3D painting, simulation, and collision detection.
The perfect hash data structure can be generalized to represent variable-sized data records as described in Texel programs for random-access antialiased vector graphics (MSR-TR-2007-95). Alcantara et al. [2009] explore parallel construction of perfect spatial hashes.
Appearance-space texture synthesis
Appearance-space texture synthesis.
Sylvain Lefebvre, Hugues Hoppe.
ACM Trans. Graphics (SIGGRAPH), 25(3), 2006.
Improved synthesis quality and efficiency by pre-transforming 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 radiance-transfer data. We perform dimensionality reduction on these vectors prior to synthesis, to create a new appearance-space exemplar. Unlike a texton space, our appearance space is low-dimensional and Euclidean. Synthesis in this information-rich 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 real-time, 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
Parallel controllable texture synthesis.
Sylvain Lefebvre, Hugues Hoppe.
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 real-time on a GPU. We attain high-quality 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 drag-and-drop, 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 k-color Gauss-Seidel updates. A similar subpass strategy is also adapted in Li-Yi Wei's Parallel Poisson disk sampling.
Fast exact and approximate geodesics on meshes
Fast exact and approximate geodesics on meshes.
Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven Gortler, Hugues Hoppe.
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 lower-bound 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 (non-point) sources.
Terrain rendering using GPU-based geometry clipmaps
Terrain rendering using GPU-based geometry clipmaps.
Arul Asirvatham, Hugues Hoppe.
GPU Gems 2, M. Pharr and R. Fernando, eds., Addison-Wesley, March 2005.
Real-time terrain rendering with all data processing on the GPU.
The geometry clipmap introduced in Losasso and Hoppe 2004 is a new level-of-detail 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 irregular-mesh 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 GPU-based 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 20-billion-sample 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
Geometry clipmaps: Terrain rendering using nested regular grids.
Frank Losasso, Hugues Hoppe.
ACM Trans. Graphics (SIGGRAPH), 23(3), 2004.
New terrain data structure enabling real-time decompression and synthesis.
Rendering throughput has reached a level that enables a novel approach to level-of-detail (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 real-time 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 normal-map 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 no-flash image pairs
Digital photography with flash and no-flash image pairs.
Georg Petschnigg, Maneesh Agrawala, Hugues Hoppe. Richard Szeliski, Michael Cohen, Kentaro Toyama.
ACM Trans. Graphics (SIGGRAPH), 23(3), 2004.
Combining detail of a flash image with ambient lighting of a non-flash image.
Digital photography has made it possible to quickly and easily take a pair of images of low-light 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/no-flash image pairs. Our applications include denoising and detail transfer (to merge the ambient qualities of the no-flash image with the high-frequency flash detail), white-balancing (to change the color tone of the ambient image), continuous flash (to interactively adjust flash intensity), and red-eye 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 “Cp = Ap / Δ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).

Inter-surface mapping
Inter-surface mapping.
John Schreiner, Arul Asirvatham, Emil Praun, Hugues Hoppe.
ACM Trans. Graphics (SIGGRAPH), 23(3), 2004.
Automatic creation of low-distortion 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 coarse-to-fine refinement of both meshes. By explicitly favoring low inter-surface 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. Inter-surface 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 semi-regular 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 fine-grain optimization.
No hindsights yet.
Removing excess topology from isosurfaces
Removing excess topology from isosurfaces.
Zoë Wood, Hugues Hoppe, Mathieu Desbrun, Peter Schröder.
ACM Trans. Graphics, 23(2), April 2004, 190-208.
Repair of tiny topological handles in scanned surface models.
Many high-resolution 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 axis-aligned sweep through the volume to locate handles, compute their sizes, and selectively remove them. The algorithm is designed to facilitate out-of-core 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 MSR-TR-2002-28.

Signal-specialized parameterization for piecewise linear reconstruction
Signal-specialized parameterization for piecewise linear reconstruction.
Geetika Tewari, John Snyder, Pedro Sander, Steven Gortler, Hugues Hoppe.
Symposium on Geometry Processing 2004, 57-66.
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, high-quality 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 piecewise-linear 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 signal-specialized parameterization metric proposed by Sander et al. in the 2002 Eurographics Workshop on Rendering.
Many of our ideas (signal-specialization, integrated metric tensor, atlas packing, etc.) have been adapted in the UVAtlas technology of the Microsoft Direct3D SDK.
Consistent spherical parameterization
Consistent spherical parameterization.
Arul Asirvatham, Emil Praun, Hugues Hoppe.
Computer Graphics and Geometric Modeling (CGGM) 2005 Workshop.
Low-distortion mapping between genus-zero 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 genus-0 meshes possibly with boundaries onto a common spherical domain, while ensuring that corresponding user-highlighted 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
Shape compression using spherical geometry images.
Hugues Hoppe, Emil Praun.
MINGLE 2003 Workshop. In Advances in Multiresolution for Geometric Modelling, N. Dodgson, M. Floater, M. Sabin (eds.), Springer-Verlag, 27-46.
Concise shape description exploiting 2D image compression techniques.
We recently introduced an algorithm for spherical parametrization and remeshing, which allows resampling of a genus-zero 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 higher-order 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 wavelet-based 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
Smooth geometry images.
Frank Losasso, Hugues Hoppe, Scott Schaefer, Joe Warren.
Symposium on Geometry Processing 2003, 138-145.
Subdivision and displacement of genus-zero mesh realized as GPU image processing.
Previous parametric representations of smooth genus-zero surfaces require a collection of abutting patches (e.g. splines, NURBS, recursively subdivided polygons). We introduce a simple construction for these surfaces using a single uniform bi-cubic B-spline. Due to its tensor-product structure, the spline control points are conveniently stored as a geometry image with simple boundary symmetries. The bicubic surface is evaluated using subdivision, and the regular structure of the geometry image makes this computation ideally suited for graphics hardware. Specifically, we let the fragment shader pipeline perform subdivision by applying a sequence of masks (splitting, averaging, limit, and tangent) uniformly to the geometry image. We then extend this scheme to provide smooth level-of-detail transitions from a subsampled base octahedron all the way to a finely subdivided, smooth model. Finally, we show how the framework easily supports scalar displacement mapping.
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
Spherical parametrization and remeshing.
Emil Praun, Hugues Hoppe.
ACM Trans. Graphics (SIGGRAPH), 22(3), 2003.
Robust mapping of a surface onto a sphere, allowing 2D-grid 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 genus-zero surface onto a spherical domain. A key ingredient for making such a parametrization practical is the minimization of a stretch-based measure, to reduce scale-distortion 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 semi-regular 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, level-of-detail, 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.

Inter-surface 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 flat-octahedron parametrization can be seen as using a Euclidean domain with 4 cone singularities, each of 180 degrees.

Multi-chart geometry images
Multi-chart geometry images.
Pedro Sander, Zoë Wood, Steven Gortler, John Snyder, Hugues Hoppe.
Symposium on Geometry Processing 2003, 146-155.
Surface shape represented using an atlas of charts within a regular grid.
We introduce multi-chart 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
Geometry videos: A new representation for 3D animations.
Hector Briceño, Pedro Sander, Leonard McMillan, Steven Gortler, Hugues Hoppe.
Symposium on Computer Animation 2003, 136-146.
3D animated shape represented as a geometry-image volume.
We present the "Geometry Video", a new data structure to encode animated meshes. Being able to encode animated meshes in a generic source-independent 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 re-sample and re-organize the geometry information, in such a way, that it becomes very compressible. They provide a unified and intuitive method for level-of-detail 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
Geometry images.
Xianfeng Gu, Steven Gortler, Hugues Hoppe.
ACM Trans. Graphics (SIGGRAPH), 21(3), 2002.
Connectivity-free 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 semi-regular meshes. The original mesh is typically decomposed into a set of disk-like 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 wavelet-based 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 single-chart parametrizations over irregular meshes, for seam-free texture mapping. The irregular "cruft" present in several of the parametrizations is addressed by the inverse-stretch regularization term described in the 2003 Spherical Parametrization paper.
Signal-specialized parametrization
Signal-specialized parametrization.
Pedro Sander, Steven Gortler, John Snyder, Hugues Hoppe.
Eurographics Workshop on Rendering 2002, 87-100.
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 signal-stretch parametrization metric is derived from a Taylor expansion of signal error. For fast evaluation, this metric is pre-integrated over the surface as a metric tensor. We minimize this nonlinear metric using a novel coarse-to-fine hierarchical solver, further accelerated with a fine-to-coarse 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 non-specialized parametrizations.
See also our follow-up 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
Texture mapping progressive meshes.
Pedro Sander, John Snyder, Steven Gortler, Hugues Hoppe.
ACM SIGGRAPH 2001 Proceedings, 409-416.
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 stretch-minimizing 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 re-optimized 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 geometric-stretch parametrization introduced in this paper is a nice principled contribution, and should have been given stronger emphasis. Signal-specialized 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 inverse-stretch regularization term described in the 2003 Spherical Parametrization paper.

Many of our ideas (signal-specialization, integrated metric tensor, atlas packing, etc.) have been adapted in the UVAtlas technology of the Microsoft Direct3D SDK.

Fine tone control in hardware hatching
Fine tone control in hardware hatching.
Matthew Webb, Emil Praun, Adam Finkelstein, Hugues Hoppe.
Symposium on Non-Photorealistic Animation and Rendering (NPAR) 2002, 53-58.
Crisper rendering of illumination-modulated ink strokes.
Recent advances in NPR have enabled real-time rendering of 3D models shaded with hatching strokes for use in interactive applications. The key challenges in real-time hatching are to convey tone by dynamically adjusting stroke density, while controlling stroke size and maintaining frame-to-frame coherence. In this paper, we introduce two new real-time 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 per-pixel lighting operations such as texture modulation. Both schemes run at interactive rates on inexpensive PC graphics cards.
Our per-pixel 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 Real-time hatching paper.
Real-time hatching
Real-time hatching.
Emil Praun, Hugues Hoppe, Matthew Webb, Adam Finkelstein.
ACM SIGGRAPH 2001 Proceedings, 581-586.
Fast nonphotorealistic rendering using precomputed tonal art maps.
Drawing surfaces using hatching strokes simultaneously conveys material, tone, and form. We present a real-time system for non-photorealistic rendering of hatching strokes over arbitrary surfaces. During an automatic preprocess, we construct a sequence of mip-mapped 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 curvature-based direction field. We demonstrate hatching strokes over complex surfaces in a variety of styles.
Hatching and other non-photorealistic 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 per-pixel thresholding scheme for more realistic pen strokes.
Real-time fur over arbitrary surfaces
Real-time fur over arbitrary surfaces.
Jed Lengyel, Emil Praun, Adam Finkelstein, Hugues Hoppe.
Symposium on Interactive 3D Graphics 2001, 227-232.
Rendering of shells and fins over general meshes.
We introduce a method for real-time rendering of fur on surfaces of arbitrary topology. As a pre-process, 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 semi-transparent 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 real-time 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
Lapped textures.
Emil Praun, Adam Finkelstein, Hugues Hoppe.
ACM SIGGRAPH 2000 Proceedings, 465-470.
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
Displaced subdivision surfaces.
Aaron Lee, Henry Moreton, Hugues Hoppe.
ACM SIGGRAPH 2000 Proceedings, 85-94.
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 scalar-valued 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
Discontinuity edge overdraw.
Pedro Sander, Hugues Hoppe, John Snyder, Steven Gortler.
Symposium on Interactive 3D Graphics 2001, 167-174.
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 fill-rate 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
Silhouette clipping.
Pedro Sander, Xianfeng Gu, Steven Gortler, Hugues Hoppe, John Snyder.
ACM SIGGRAPH 2000 Proceedings, 327-334.
Efficient computation of mesh silhouette, used to clip coarse geometry.
Approximating detailed models with coarse, texture-mapped 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 high-resolution meshes in less rendering time.
One fact that we forgot to mention in the paper is that backface/silhouette testing using a traditional "sphere-cone test" Abi-Ezzi and Subramaniam 1994 is equivalent to testing against some (non-optimized) 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
Silhouette mapping.
Xianfeng Gu, Steven Gortler, Hugues Hoppe, Leonard McMillan, Benedict Brown, Abraham Stone.
Technical Report TR-1-99, Dept. of Computer Science, Harvard University, March 1999.
Interpolation among a sparse set of precomputed object silhouettes.
Recent image-based 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 high-resolution 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 Image-based visual hulls.
Efficient minimization of new quadric metric for simplifying meshes with appearance attributes
Efficient minimization of new quadric metric for simplifying meshes with appearance attributes.
Hugues Hoppe, Steve Marschner.
Microsoft Research Technical Report MSR-TR-2000-64, June 2000.
Fast solution of quadric metric exploiting its sub-block 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(m2) 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
New quadric metric for simplifying meshes with appearance attributes.
Hugues Hoppe.
IEEE Visualization 1999 Conference, 59-66.
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 wedge-based 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 per-vertex attributes by texture atlases.
Optimization of mesh locality for transparent vertex caching
Optimization of mesh locality for transparent vertex caching.
Hugues Hoppe.
ACM SIGGRAPH 1999 Proceedings, 269-276.
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 strip-growing algorithm and a local optimization algorithm. The strip-growing 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
Robust mesh watermarking.
Emil Praun, Hugues Hoppe, Adam Finkelstein.
ACM SIGGRAPH 1999 Proceedings, 69-76.
Imperceptible low-frequency 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 "spread-spectrum" approach — they transform the document to the frequency domain and perturb the coefficients of the perceptually most significant basis functions. We extend this spread-spectrum 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 frequency-based 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 low-order bits, or even insertion of other watermarks.
It would be nice to run side-by-side 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.
View-based rendering: Visualizing real objects from scanned range and color data
View-based rendering: Visualizing real objects from scanned range and color data.
Kari Pulli, Michael Cohen, Tom Duchamp, Hugues Hoppe, Linda Shapiro, Werner Stuetzle.
Eurographics Workshop on Rendering 1997, 23-34.
Blending of textured depth meshes using soft z-buffering.
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 view-based 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 z-buffering. We demonstrate interactive viewing of real, non-trivial 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 image-based rendering techniques.
Robust meshes from multiple range maps
Robust meshes from multiple range maps.
Kari Pulli, Tom Duchamp, Hugues Hoppe, John McDonald, Linda Shapiro, Werner Stuetzle.
Intnl. Conf. on Recent Advances in 3-D 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
Efficient implementation of progressive meshes.
Hugues Hoppe.
Computers & Graphics, 22(1), 1998, 27-36.
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 level-of-detail 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 half-edge 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 view-dependent level-of-detail control and its application to terrain rendering
Smooth view-dependent level-of-detail control and its application to terrain rendering.
Hugues Hoppe.
IEEE Visualization 1998 Conference, 35-42.
Visually smooth adaptation of mesh refinement using cascaded temporal geomorphs.
The key to real-time rendering of large-scale surfaces is to locally adapt surface geometric complexity to changing view parameters. Several schemes have been developed to address this problem of view-dependent level-of-detail control. Among these, the view-dependent 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 output-sensitive 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 block-based 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 real-time 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 pre-simplified. This approach has been generalized to general (non-terrain) 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.
View-dependent refinement of progressive meshes
View-dependent refinement of progressive meshes.
Hugues Hoppe.
ACM SIGGRAPH 1997 Proceedings, 189-198.
Lossless multiresolution structure for incremental local refinement/coarsening.
Level-of-detail (LOD) representations are an important tool for real-time rendering of complex geometric environments. The previously introduced progressive mesh representation defines for an arbitrary triangle mesh a sequence of approximating meshes optimized for view-independent 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 screen-space geometric error, and develop a real-time 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 view-dependent 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
Progressive simplicial complexes.
Jovan Popovic, Hugues Hoppe.
ACM SIGGRAPH 1997 Proceedings, 217-224.
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, non-orientable, non-manifold, non-regular), 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 level-of-detail control, allows smooth transitions between any pair of models in the sequence, supports progressive transmission, and offers a space-efficient 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
Progressive meshes.
Hugues Hoppe.
ACM SIGGRAPH 1996 Proceedings, 99-108.
Efficient, lossless, continuous-resolution 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, continuous-resolution representation addresses several practical problems in graphics: smooth geomorphing of level-of-detail 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 B-spline surfaces of arbitrary topological type
Automatic reconstruction of B-spline surfaces of arbitrary topological type.
Matthias Eck, Hugues Hoppe.
ACM SIGGRAPH 1996 Proceedings, 325-334.
Fully automatic creation of B-spline 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 B-spline surface from a set of scanned 3D points. Unlike previous work which considers primarily the problem of fitting a single B-spline patch, our goal is to directly reconstruct a surface of arbitrary topological type. We must therefore define the surface as a network of B-spline 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 B-spline 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 user-specified error tolerances, and demonstrate our method on both synthetic and real data.
Reconstructing arbitrary B-spline 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
Multiresolution analysis of arbitrary meshes.
Matthias Eck, Tony DeRose, Tom Duchamp, Hugues Hoppe, Michael Lounsbery, Werner Stuetzle.
ACM SIGGRAPH 1995 Proceedings, 173-182.
Semi-regular remeshing for wavelet-based 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 Mj 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: Vertex-based 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)
Surface reconstruction from unorganized points (PhD Thesis).
Hugues Hoppe.
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 reverse-engineering — 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 three-phase 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 trade-offs. 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
Piecewise Smooth Surface Reconstruction.
Hugues Hoppe, Tony DeRose, Tom Duchamp, Michael Halstead, Hubert Jin, John McDonald, Jean Schweitzer, Werner Stuetzle.
ACM SIGGRAPH 1994 Proceedings, 295-302.
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
Mesh optimization.
Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, Werner Stuetzle.
ACM SIGGRAPH 1993 Proceedings, 19-26.
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 M0, produce a mesh M, of the same topological type as M0, 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 Image-driven mesh optimization work. Mesh optimization is quite powerful for feature-sensitive remeshing, as it automatically migrates vertices onto sharp features (e.g. as used in multi-chart geometry images). For the application of mesh simplification, progressive meshes offer a more elegant solution.
Surface reconstruction from unorganized points
Surface reconstruction from unorganized points.
Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, Werner Stuetzle.
ACM SIGGRAPH 1992 Proceedings, 71-78.
Signed-distance field estimated from a set of unoriented noisy points.
We describe and demonstrate an algorithm that takes as input an unorganized set of points {x1, ... , xn} in R3 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 two-dimensional 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 laser-sheet 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 signed-distance 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.

Copyrights:
ACM Copyright Notice
Copyright by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org. The definitive version of this paper can be found at ACM's Digital Library http://www.acm.org/dl/.
Eurographics Association Copyright Notice
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than Eurographics must be honored.
IEEE Copyright Notice
This material is posted here with permission of the IEEE. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to pubs-permissions@ieee.org.
Springer-Verlag Copyright Notice
The Author may publish his/her contribution on his/her personal Web page provided that he/she creates a link to the above mentioned volume of LNCS at the Springer-Verlag server or to the LNCS series Homepage (URL: http://www.springer.de/comp/lncs/index.html) and that together with this electronic version it is clearly pointed out, by prominently adding “© Springer-Verlag”, that the copyright for this contribution is held by Springer.
Contact Terms Trademarks Privacy and Cookies Code of Conduct © Microsoft Corporation. All rights reserved.Microsoft