Detailed Publications
 |
Screened Poisson surface reconstruction. ACM Trans. Graphics, to appear. Improved geometric fidelity and faster 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. No hindsights yet. |
 |
Cliplets: Juxtaposing still and dynamic imagery. UIST 2012. (Best Paper Award) Cinemagraphs and more general spatiotemporal compositions from handheld video.
web page
paper
project page
tutorials
demo tool
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. No hindsights yet. |
 |
A subdivision-based representation for vector image editing. IEEE Trans. Vis. Comput. Graphics, 18(11), Nov. 2012. (Spotlight Paper) Piecewise-smooth subdivision for representing and manipulating images.
web page
paper
supplement
I3D 2013 talk
IEEE
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. No hindsights yet. |
 |
GPU-efficient recursive filtering and summed-area tables. ACM Trans. Graphics (SIGGRAPH Asia), 30(6), 2011. Efficient overlapped computation of successive recursive filters on 2D images.
web page
paper
video
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 should have mentioned integral images, a term sometimes used in the computer vision literature [Viola and Jones 2001] that also refers to summed-area tables [Crow 1984]. |
 |
Freeform vector graphics with controlled thin-plate splines. ACM Trans. Graphics (SIGGRAPH Asia), 30(6), 2011. Rich set of curve and point controls for intuitive and expressive color interpolation.
web page
paper
video
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] as it 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. |
 |
Image-space bidirectional scene reprojection. ACM Trans. Graphics (SIGGRAPH Asia), 30(6), 2011. Real-time temporal upsampling through image-based reprojection of adjacent frames.
web page
paper
video
talk
supplement
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. No hindsights yet. |
 |
Real-time classification of dance gestures from skeleton animation. Symposium on Computer Animation 2011. (Honorable Mention) Recognition of Kinect motions using robust, low-dimensional feature vectors.
web page
paper
video
talk
supplement
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. No hindsights yet. |
 |
Generalized sampling in computer graphics. IMPA Tech. Report E022/2011 & Microsoft Research MSR-TR-2011-16, February 2011. Extension of recent signal-processing techniques to graphics filtering.
web page
paper
videoclip
supplemental data
supplemental videos
Analysis and reconstruction filters are crucial in graphics. The signal processing community has recently developed new filtering strategies based on a generalization of the traditional sampling pipeline. The main idea is to select simple basis functions such as B-splines but to effectively reshape these kernels by adding a discrete transformation filter. This approach is not widely known to graphics practitioners. In this paper we introduce new notation to succinctly summarize important algorithms in generalized sampling. We also present and analyze novel algorithms, including supersampling for antialiased rendering, and image downscaling for mipmap creation. The advantages of generalized sampling are twofold. The non-negativity of B-spline kernels simplifies both importance-based integration and GPU evaluation. And, the broader support of the transformed kernels improves filtering quality. A key challenge is that the discrete transformation often involves inverse convolutions, but fortunately the associated linear systems are banded and can be parallelized. No hindsights yet. |
 |
Antialiasing recovery. ACM Trans. Graphics, 30(3), 2011. Fast removal of jaggies introduced by many nonlinear image processing operations.
web page
paper
talk
image data
msdn sample code (using Direct2D Imaging Effects)
DirectX10 source code
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. Many thanks to Mark Finch for writing the Direct2D Custom Image Effect to demonstrate this technique! |
 |
Optimizing continuity in multiscale imagery. ACM Trans. Graphics (SIGGRAPH Asia), 29(6), 2010. Visually continuous mipmap pyramid spanning differing coarse- and fine-scale images.
web page
paper
docx
video
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. ACM Trans. Graphics (SIGGRAPH Asia), 29(6), 2010. Adaptively discretized equirectangular map for accurate spherical processing.
web page
paper
talk
code and data
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. Computer Graphics Forum (Eurographics), 29(2), 479-486, 2010. Optimized alignment and merging of photographs for texturing approximate geometry. web page paper talk supplemental material optimizer animation 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. ACM Trans. Graphics, 29(2), 14, 2010. Spherical gradient-domain processing on a Terapixel sky. web page paper talk Terapixel project News release supp proof code and data videoclip 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. Please see the resulting seamless terapixel night sky in WorldWide Telescope. In this work, to avoid resampling we had to use the "TOAST" spherical parameterization in which the data was already provided. 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 using the (commonly used) equirectangular parameterization, one can adaptively discretize the domain to achieve an efficient, exact solution over the sphere. |
 |
Amortized supersampling. ACM Trans. Graphics (SIGGRAPH Asia), 28(5), 2009. Adaptive reuse of pixels from previous frames for high-quality antialiasing. web page paper video talk supplemental results microdot 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. |
 |
Parallel Poisson surface reconstruction. International Symposium on Visual Computing 2009. Parallelization of Poisson reconstruction using domain decomposition. In this work we describe a parallel implementation of the Poisson Surface Reconstruction algorithm based on multigrid domain decomposition. We compare implementations using different models of 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. No hindsights yet. |
 |
Parallel view-dependent level-of-detail control. IEEE Trans. Vis. Comput. Graphics, 16(5), 2010. Extended journal version with applications. web page paper video lucy movie 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. Symposium on Interactive 3D Graphics and Games 2009, 169-176. Selective refinement of irregular mesh hierarchy using GPU streaming passes. web page paper video talk lucy movie 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. 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 that are introduced in the DirectX 11 hull shader. |
 |
Random-access rendering of general vector graphics. ACM Trans. Graphics (SIGGRAPH Asia), 27(5), 2008. GPU rendering of vector art over surfaces using cell-specialized descriptions. web page paper docx talk tiger movie desktop movie all movies demo MSR-TR-2007-95 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. |
 |
Factoring repeated content within and among images. ACM Trans. Graphics (SIGGRAPH), 27(3), 2008. Megatexture encoded by indirecting into an optimized epitome image. web page paper docx talk data compression results 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. ACM Trans. Graphics (SIGGRAPH), 27(3), 2008. Perform k multigrid V-cycles in just k-1 streaming passes over the data. web page paper talk megapixel results 3.3-gigapixel results source code and examples 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. IEEE International Conference on Computer Vision (ICCV) 2007. Detailed 3D models reconstructed from crawled Internet images. web page paper talk project page 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. ACM Trans. Graphics (SIGGRAPH), 26(3), 2007. Interactive control of direction fields for real-time surface texture synthesis. web page paper movie - interactive design movie - no extraneous singularities 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. Symposium on Rendering 2007. Efficient representation of coherent image data such as lightmaps and alpha mattes. web page paper docx talk supplemental results 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. 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. Symposium on Geometry Processing 2007. Out-of-core solution of huge Poisson system to reconstruct 3D scans. web page paper talk cover image supplemental images code 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. Symposium on Geometry Processing 2006, 61-70. Reconstruction that considers all points at once for resilience to data noise. web page paper talk cover image award-winning code 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.
|
 |
Perfect spatial hashing. ACM Trans. Graphics (SIGGRAPH), 25(3), 2006. Sparse spatial data packed into a dense table using a simple collision-free map. web page paper docx video talk poster errata 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 the technical report MSR-TR-2007-95 Texel programs for random-access antialiased vector graphics. Alcantara et al. [2009] explore parallel construction of perfect spatial hashes. |
 |
Appearance-space texture synthesis. ACM Trans. Graphics (SIGGRAPH), 25(3), 2006. Improved synthesis quality and efficiency by pre-transforming the exemplar. web page paper docx video talk poster advection-over-horse movie additional results 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. ACM Trans. Graphics (SIGGRAPH), 24(3), 2005. Parallel synthesis of infinite deterministic content, with intuitive user controls. web page paper docx video talk drag-and-drop movie poster additional results tutorial code 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. ACM Trans. Graphics (SIGGRAPH), 24(3), 2005. Efficient computation of shortest paths and distances on triangle meshes. web page paper talk Danil Kirsanov's code (different implementation than in paper) 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. GPU Gems 2, M. Pharr and R. Fernando, eds., Addison-Wesley, March 2005. Real-time terrain rendering with all data processing on the GPU. web page paper talk quick movie demo 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 representation, which is supported in the WIC interface of Windows. See also the original paper, and the recent book 3D Engine Design for Virtual Globes [Cozzi and Ring 2011]. |
 |
Geometry clipmaps: Terrain rendering using nested regular grids. ACM Trans. Graphics (SIGGRAPH), 23(3), 2004. New terrain data structure enabling real-time decompression and synthesis. web page paper docx video talk quick movie poster 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 representation, which is supported in the WIC interface of Windows. |
 |
Digital photography with flash and no-flash image pairs. ACM Trans. Graphics (SIGGRAPH), 23(3), 2004. Combining detail of a flash image with ambient lighting of a non-flash image. web page paper docx talk project page 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 "C_p = A_p / \Delta_p".
|
 |
Inter-surface mapping. 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. ACM Trans. Graphics, 23(2), April 2004, 190-208. Repair of tiny topological handles in scanned surface models. web page paper talk older MSR-TR-2002-28 Zoë Wood's thesis data 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. |
 |
Signal-specialized parameterization for piecewise linear reconstruction. 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. 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. 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's interesting that we obtain compression rates that are more aggressive than in traditional image compression. This reflects the fact that the geometry of individual shapes is rather smooth, and in some sense contains less information than typical images. |
 |
Smooth geometry images. Symposium on Geometry Processing 2003, 138-145. Subdivision and displacement of genus-zero mesh realized as GPU image processing. web page paper talk overview slide sphere-to-square movie data 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. ACM Trans. Graphics (SIGGRAPH), 22(3), 2003. Robust mapping of a surface onto a sphere, allowing 2D-grid resampling. web page paper talk docx cow-square movie horse-sphere movie gargoyle-bunny movie data 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. 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. 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. No hindsights yet. |
 |
Geometry images. ACM Trans. Graphics (SIGGRAPH), 21(3), 2002. Connectivity-free resampling of an arbitrary shape into a regular 2D grid. web page paper talk bunny-to-square movie data 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. Eurographics Workshop on Rendering 2002, 87-100. Optimization of texture coordinates for accurate representation of given content. web page paper docx video talk 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. ACM SIGGRAPH 2001 Proceedings, 409-416. Texture atlas compatible across levels of detail, and parameterization stretch. web page paper docx video talk demo errata 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. 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. ACM SIGGRAPH 2001 Proceedings, 581-586. Fast nonphotorealistic rendering using precomputed tonal art maps. web page paper video talk project page 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. Symposium on Interactive 3D Graphics 2001, 227-232. Rendering of shells and fins over general meshes. web page paper docx talk blurb 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. ACM SIGGRAPH 2000 Proceedings, 465-470. Texture synthesis over arbitrary surfaces. web page paper video talk cover image project page
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. We originally entitled this submission "Synthesizing surface texture by example". Perhaps we should have stuck to that title, because surface texture synthesis became a hot topic the following year. For isotropic textures, the Least squares conformal map is a nice alternative for local parametrization. In our setting, it corresponds to minimizing ||φ(S) - rot90(φ(T))||2 instead of our functional ||φ(S) - s^||2 + ||φ(T) - t^||2. (Both minimizations are linear problems.) Several papers have improved our technique by adjusting the locations and extents of the patches to make their boundaries less perceptible. |
 |
Displaced subdivision surfaces. ACM SIGGRAPH 2000 Proceedings, 85-94. Automatic conversion of detailed mesh to displaced surface, and its benefits. web page paper docx video talk data 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. 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. 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. 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.
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. 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)x(3+m), where m is the number of distinct appearance attributes. The system has only O(m) nonzero entries, so it can be solved in O(m^2) time using traditional sparse solvers such as the method of conjugate gradients. In this short addendum, we show that the special structure of the sparsity permits the system to be solved in O(m) time. Thanks also to John Platt for explaining Lagrange multipliers to me. |
 |
New quadric metric for simplifying meshes with appearance attributes. IEEE Visualization 1999 Conference, 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. 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. 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. ACM SIGGRAPH 1999 Proceedings, 69-76. Imperceptible low-frequency shape perturbations resilient to remeshing. web page paper talk project page
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. 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. 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. 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. Computers & Graphics, 22(1), 1998, 27-36. Progressive mesh data structures compatible with GPU vertex buffers. web page paper SIGGRAPH 1998 course slides 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. IEEE Visualization 1998 Conference, 35-42. Visually smooth adaptation of mesh refinement using cascaded temporal geomorphs. web page paper video talk real-time flyover movie better movie data
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. 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. ACM SIGGRAPH 1997 Proceedings, 189-198. Lossless multiresolution structure for incremental local refinement/coarsening. web page paper video talk teapot movie data errata
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. Further enhancements on this approach are presented in my Visualization 1998 paper. |
 |
Progressive simplicial complexes. ACM SIGGRAPH 1997 Proceedings, 217-224. Progressive encoding of both topology and geometry. web page paper video talk drumset movie schooner movie
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. It is an elegant framework for progressively encoding topology, although perhaps overly general for efficient implementation. Solutions have since been developed for the case of progressive tetrahedralizations, another interesting generalization of progressive meshes. |
 |
Progressive meshes. ACM SIGGRAPH 1996 Proceedings, 99-108. Efficient, lossless, continuous-resolution representation of surface triangulations. web page paper video talk cessna movie dragon movie sandal movie geomorph movie data
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. 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. 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. 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. 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.
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). Department of Computer Science and Engineering, University of Washington, June 1994. Robust surface topology and optimized geometry from scanned 3D points. web page paper talk data errata
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.
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, the commercial product by Geomagic,
and Poisson surface reconstruction.
This reconstructed mannequin head is my small contribution to the pool of geometric models commonly
used in graphics.
|
 |
Piecewise Smooth Surface Reconstruction. ACM SIGGRAPH 1994 Proceedings, 295-302. Subdivision surfaces with sharp features, and their automatic creation by data fitting. web page paper video talk data
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. Through general optimization, this method is able to infer sharp features in the underlying geometry by simply fitting the data points. With the growing interest in subdivision surfaces, this surface fitting technique may prove useful. The paper is often cited for its introduction of sharp features in subdivision surface schemes. These features were extended in the work of Biermann et al. The SIGGRAPH 1998 paper by DeRose et al. presents extensions for "fractionally smooth" surface features. |
 |
Mesh optimization. ACM SIGGRAPH 1993 Proceedings, 19-26. Traversing the space of triangle meshes to optimize model fidelity and conciseness. web page paper extended TR UW CSE 93-01-01 data video We present a method for solving the following problem: Given a set of data points scattered in three dimensions and an initial triangular mesh M_0, produce a mesh M, of the same topological type as M_0, that fits the data well and has a small number of vertices. Our approach is to minimize an energy function that explicitly models the competing desires of conciseness of representation and fidelity to the data. We show that mesh optimization can be effectively used in at least two applications: surface reconstruction from unorganized points, and mesh simplification (the reduction of the number of vertices in an initially dense mesh of triangles). The technique demonstrates that general optimization can achieve surprisingly good results. This particular optimization searches over a broad space of both discrete and continuous variables to find a concise mesh accurately fitting a set of data points. A similar approach was used by Lindstrom and Turk in their 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. 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 R^3 on or near an unknown manifold M, and produces as output a simplicial surface that approximates M. Neither the topology, the presence of boundaries, nor the geometry of M are assumed to be known in advance — all are inferred automatically from the data. This problem naturally arises in a variety of practical situations such as range scanning an object from multiple view points, recovery of biological shapes from 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.
|
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.
