Random-access vector graphics.

Rendering of terrains using geometry clipmaps.

Texture mapping progressive meshes.

Factoring repeated content within and among images.

H. Wang, Y. Wexler, E. Ofek, H. Hoppe.

SIGGRAPH 2008.

[info] [paper]

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.

M. Kazhdan, H. Hoppe.

SIGGRAPH 2008.

[info] [paper] [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.

No hindsights yet.

Multi-view stereo for community photo collections.

M. Goesele, N. Snavely, B. Curless, H. Hoppe, S. Seitz.

ICCV 2007.

[info] [paper] [web 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.

No hindsights yet.

Design of tangent vector fields.

M. Fisher, P. Schröder, M. Desbrun, H. Hoppe.

SIGGRAPH 2007.

[info] [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.

No hindsights yet.

Compressed random-access trees for spatially coherent data.

S. Lefebvre, H. Hoppe.

Symposium on Rendering 2007.

[info] [paper] [supplemental results] [talk]

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.

No hindsights yet.

Texel programs for random-access antialiased vector graphics.

D. Nehab, H. Hoppe.

Microsoft Research Technical Report MSR-TR-2007-95, July 2007.

[info] [paper] [video]

We encode a broad class of vector graphics in a randomly accessible format. Our approach is to create a coarse image in which each image cell contains a texel program — a locally specialized description of the graphics primitives overlapping the cell. These texel programs are interpreted at runtime within a programmable pixel shader. Advantages include coherent low-bandwidth memory access, efficient inter-primitive antialiasing, and the ability to map general vector graphics (including strokes) onto arbitrary surfaces. We present a fast construction algorithm, and demonstrate the space and time efficiency of the representation on many practical examples.

No hindsights yet.

Unconstrained isosurface extraction on arbitrary octrees.

M. Kazhdan, A. Klein, K. Dalal, H. Hoppe.

Symposium on Geometry Processing 2007.

[info] [paper] [code]

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.

M. Bolitho, M. Kazhdan, R. Burns, H. Hoppe.

Symposium on Geometry Processing 2007.

[info] [paper] [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.

No hindsights yet.

Poisson surface reconstruction.

M. Kazhdan, M. Bolitho, H. Hoppe.

Symposium on Geometry Processing 2006, 61-70.

[info] [paper] [cover image] [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.

In our subsequent SGP 2007 paper we show that the Poisson problem can be solved out-of-core for very large models by introducing a multilevel streaming representation of the sparse octree.

Perfect spatial hashing.

S. Lefebvre, H. Hoppe.

SIGGRAPH 2006, 579-588.

[info] [paper] [video] [talk] [talk movies] [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 Texel programs for random-access antialiased vector graphics.

Appearance-space texture synthesis.

S. Lefebvre, H. Hoppe.

SIGGRAPH 2006, 541-548.

[info] [paper] [video] [talk] [talk movies] [poster] [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; Linag 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 tangent vector field design for interactive painting of oriented texture over a surface.

Parallel controllable texture synthesis.

S. Lefebvre, H. Hoppe.

SIGGRAPH 2005, 777-786.

[info] [paper] [video] [talk] [talk movies] [drag-and-drop movie] [poster] [additional results]

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.

Fast exact and approximate geodesics on meshes.

V. Surazhsky, T. Surazhsky, D. Kirsanov, S. Gortler, H. Hoppe.

SIGGRAPH 2005, 553-560.

[info] [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.

A. Asirvatham, H. Hoppe.

GPU Gems 2, M. Pharr and R. Fernando, eds., Addison-Wesley, March 2005.

[info] [paper] [demo (requires NVIDIA >=6xxx)]

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.

Geometry clipmaps: Terrain rendering using nested regular grids.

F. Losasso, H. Hoppe.

SIGGRAPH 2004, 769-776.

[info] [paper] [talk] [poster] [video]

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 (see above), we store the terrain as a set of vertex textures, thereby offloading nearly all computation to the GPU.

Digital photography with flash and no-flash image pairs.

G. Petschnigg, M. Agrawala, H. Hoppe. R. Szeliski, M. Cohen, K. Toyama.

SIGGRAPH 2004, 664-672.

[info] [paper] [web 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.

I really like the image deblurring work of [Yuan et al 2007] which uses a blurred/noisy image pair.

Inter-surface mapping.

J. Schreiner, A. Asirvatham, E. Praun, H. Hoppe.

SIGGRAPH 2004, 870-877.

[info] [paper] [talk] [talk movies]

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.

Z. Wood, H. Hoppe, M. Desbrun, P. Schröder.

Transactions on Graphics, 23(2), April 2004, 190-208.

[info] [paper] [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.

G. Tewari, J. Snyder, P. Sander, S. Gortler, H. Hoppe.

Symposium on Geometry Processing 2004, 57-66.

[info] [paper]

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.

A. Asirvatham, E. Praun, H. Hoppe.

Computer Graphics and Geometric Modeling (CGGM) 2005 Workshop.

[info] [paper]

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.

H. Hoppe, E. Praun.

MINGLE 2003 Workshop. In Advances in Multiresolution for Geometric Modelling, N. Dodgson, M. Floater, M. Sabin (eds.), Springer-Verlag, 27-46.

[info] [paper] [talk]

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.

F. Losasso, H. Hoppe, S. Schaefer, J. Warren.

Symposium on Geometry Processing 2003, 138-145.

[info] [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 vertex textures in DX9 VS3.0 provide another technique for cycling rasterization output back into the vertex stream, and are implemented in the NVIDIA GeForce 6800 (NV40). Being able to process geometry as images within the highly parallel GPU rasterizer is exciting.

Spherical parametrization and remeshing.

E. Praun, H. Hoppe.

SIGGRAPH 2003, 340-349.

[info] [paper] [talk] [cow-to-square movie] [horse-to-sphere movie] [gargoyle-to-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.

P. Sander, Z. Wood, S. Gortler, J. Snyder, H. Hoppe.

Symposium on Geometry Processing 2003, 146-155.

[info] [paper] [talk]

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.

H. Briceño, P. Sander, L. McMillan, S. Gortler, H. Hoppe.

Symposium on Computer Animation 2003, 136-146.

[info] [paper]

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

No hindsights yet.

Geometry images.

X. Gu, S. Gortler, H. Hoppe.

SIGGRAPH 2002, 355-361.

[info] [paper] [talk] [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.

P. Sander, S. Gortler, J. Snyder, H. Hoppe.

Eurographics Workshop on Rendering 2002, 87-100.

[info] [paper] [talk] [video]

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.

P. Sander, J. Snyder, S. Gortler, H. Hoppe.

SIGGRAPH 2001, 409-416.

[info] [paper] [talk] [video] [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 excellent, and should have been given stronger emphasis. See the demo above. 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.

Fine tone control in hardware hatching.

M. Webb, E. Praun, A. Finkelstein, H. Hoppe.

Symposium on Non-Photorealistic Animation and Rendering (NPAR) 2002, 53-58.

[info] [paper]

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.

E. Praun, H. Hoppe, M. Webb, A. Finkelstein.

SIGGRAPH 2001, 581-586.

[info] [paper] [talk] [video] [web 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.

J. Lengyel, E. Praun, A. Finkelstein, H. Hoppe.

Symposium on Interactive 3D Graphics 2001, 227-232.

[info] [paper] [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.

E. Praun, A. Finkelstein, H. Hoppe.

SIGGRAPH 2000, 465-470.

[info] [paper] [cover image] [talk] [video] [web 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.
Through a simple interface, the user specifies a tangential vector field over the surface, providing local control over the texture scale, and for anisotropic textures, the orientation. To paste a texture patch onto the surface, a surface patch is grown and parametrized over texture space. Specifically, we optimize the parametrization of each surface patch such that the tangential vector field aligns everywhere with the standard frame of the texture patch. We show that this optimization is solved efficiently as a sparse linear system.

We originally entitled this submission "Synthesizing surface texture by example". Perhaps we should have stuck to that title, because surface texture synthesis became a hot topic the following year. For isotropic textures, the Least squares conformal map is a nice alternative for local parametrization. In our setting, it corresponds to minimizing ||φ(S) - rot90(φ(T))||² instead of our functional ||φ(S) - s^{^}||² + ||φ(T) - t^{^}||². (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.

A. Lee, H. Moreton, H. Hoppe.

SIGGRAPH 2000, 85-94.

[info] [paper] [talk] [video]

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.

P. Sander, H. Hoppe, J. Snyder, S. Gortler.

Symposium on Interactive 3D Graphics 2001, 167-174.

[info] [paper] [talk] [video]

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.

P. Sander, X. Gu, S. Gortler, H. Hoppe, J. Snyder.

SIGGRAPH 2000, 327-334.

[info] [paper] [talk] [video]

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.

X. Gu, S. Gortler, H. Hoppe, L. McMillan, B. Brown, A. Stone.

Technical Report TR-1-99, Department of Computer Science, Harvard University, March 1999.

[info] [paper] [video]

Recent image-based rendering techniques have shown success in approximating detailed models using sampled images over coarser meshes. One limitation of these techniques is that the coarseness of the geometric mesh is apparent in the rough polygonal silhouette of the rendering. In this paper, we present a scheme for accurately capturing the external silhouette of a model in order to clip the approximate geometry.
Given a detailed model, silhouettes sampled from a discrete set of viewpoints about the object are collected into a silhouette map. The silhouette from an arbitrary viewpoint is then computed as the interpolation from three nearby viewpoints in the silhouette map. Pairwise silhouette interpolation is based on a visual hull approximation in the epipolar plane. The silhouette map itself is adaptively simplified by removing views whose silhouettes are accurately predicted by interpolation of their neighbors. The model geometry is approximated by a progressive hull construction, and is rendered using projected texture maps. The 3D rendering is clipped to the interpolated silhouette using stencil planes.

Our more recent Silhouette Clipping (2000) paper extracts silhouettes from a high-resolution mesh instead of interpolating from a set of precomputed silhouettes. Still, we have hope that the silhouette map may prove useful for using scanned silhouettes directly without having to construct explicit mesh geometry. Another related work is Image-based visual hulls.

Efficient minimization of new quadric metric for simplifying meshes with appearance attributes.

H. Hoppe, S. Marschner.

Microsoft Research Technical Report MSR-TR-2000-64, June 2000.

[info] [paper]

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.

H. Hoppe.

IEEE Visualization 1999, 59-66.

[info] [paper] [talk]

Complex triangle meshes arise naturally in many areas of computer graphics and visualization. Previous work has shown that a quadric error metric allows fast and accurate geometric simplification of meshes. This quadric approach was recently generalized to handle meshes with appearance attributes. In this paper we present an improved quadric error metric for simplifying meshes with attributes. The new metric, based on geometric correspondence in 3D, requires less storage, evaluates more quickly, and results in more accurate simplified meshes.
Meshes often have attribute discontinuities, such as surface creases and material boundaries, which require multiple attribute vectors per vertex. We show that a wedge-based mesh data structure captures such discontinuities efficiently and permits simultaneous optimization of these multiple attribute vectors. In addition to the new quadric metric, we experiment with two techniques proposed in geometric simplification, memoryless simplification and volume preservation, and show that both of these are beneficial within the quadric framework. The new scheme is demonstrated on a variety of meshes with colors and normals.

The technical report above 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.

H. Hoppe.

SIGGRAPH 1999, 269-276.

[info] [paper] [talk]

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. 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.

E. Praun, H. Hoppe, A. Finkelstein.

SIGGRAPH 1999, 69-76.

[info] [paper] [talk] [web 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.
Generalizing spread spectrum techniques to surfaces presents two major challenges. First, arbitrary surfaces lack a natural parametrization for frequency-based decomposition. Our solution is to construct a set of scalar basis function over the mesh vertices using multiresolution analysis. The watermark perturbs vertices along the direction of the surface normal, weighted by the basis functions. The second challenge is that simplification and other attacks may modify the connectivity of the mesh. We use an optimization technique to resample an attacked mesh using the original mesh connectivity. Results show that our watermarks are resistant to common mesh operations such as translation, rotation, scaling, cropping, smoothing, simplification, and resampling, as well as malicious attacks such as the insertion of noise, modification of low-order bits, or even insertion of other watermarks.

It would be nice to run side-by-side comparisons with some other recent mesh watermarking schemes, such as [Benedens 1999], or the spectral approach of [Ohbuchi et al 2001]. One major difficulty is judging the relative perceptibility of different watermarks.

View-based rendering: visualizing real objects from scanned range and color data.

K. Pulli, M. Cohen, T. Duchamp, H. Hoppe, L. Shapiro, W. Stuetzle.

Workshop on Rendering 1997, 23-34.

[info] [paper] [talk]

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.

K. Pulli, T. Duchamp, H. Hoppe, J. McDonald, L. Shapiro, W. Stuetzle.

International Conference on Recent Advances in 3-D Digital Imaging and Modeling, May 1997, 205-211.

[info] [paper] [talk]

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.

H. Hoppe.

Computers & Graphics, Vol. 22, No. 1, 1998, 27-36.

[info] [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. 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.

H. Hoppe.

IEEE Visualization 1998, 35-42.

[info] [paper] [talk] [real-time flyover movie] [video] [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.
We specialize the VDPM framework to the important case of terrain rendering. To handle huge terrain grids, we introduce a block-based simplification scheme that constructs a progressive mesh as a hierarchy of block refinements. We demonstrate the need for an accurate approximation metric during simplification. Our contributions are highlighted in a real-time flyover of a large, rugged terrain. Notably, the use of geomorphs results in visually smooth rendering even at 72 frames/sec on a graphics workstation.

The runtime geomorphs make this one of my favorite demos. The irregular meshes reduce the number of triangles for a given level of approximation accuracy, and allow large regions of the terrain to be pre-simplified. See the Puget Sound Flythrough Demo above. 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.

H. Hoppe.

SIGGRAPH 1997, 189-198.

[info] [paper] [talk] [teapot movie] [video] [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.
A number of previous schemes create view-dependent LOD meshes for height fields (e.g. terrains) and parametric surfaces (e.g. NURBS). Our framework also performs well for these special cases. Notably, the absence of a rigid subdivision structure allows more accurate approximations than with existing schemes. We include results for these cases as well as for general meshes.

Further enhancements on this approach are presented in my Visualization 1998 paper.

Progressive simplicial complexes.

J. Popovic, H. Hoppe.

SIGGRAPH 1997, 217-224.

[info] [paper] [talk] [drumset movie] [schooner movie] [video] [data]

In this paper, we introduce the progressive simplicial complex (PSC) representation, a new format for storing and transmitting triangulated geometric models. Like the earlier progressive mesh (PM) representation, it captures a given model as a coarse base model together with a sequence of refinement transformations that progressively recover detail. The PSC representation makes use of a more general refinement transformation, allowing the given model to be an arbitrary triangulation (e.g. any dimension, non-orientable, non-manifold, non-regular), and the base model to always consist of a single vertex. Indeed, the sequence of refinement transformations encodes both the geometry and the topology of the model in a unified multiresolution framework. The PSC representation retains the advantages of PM's. It defines a continuous sequence of approximating models for runtime level-of-detail control, allows smooth transitions between any pair of models in the sequence, supports progressive transmission, and offers a space-efficient representation. Moreover, by allowing changes to topology, the PSC sequence of approximations achieves better fidelity than the corresponding PM sequence.
We develop an optimization algorithm for constructing PSC representations for graphics surface models, and demonstrate the framework on models that are both geometrically and topologically complex.

It is an elegant framework for progressively encoding topology, although perhaps overly general for efficient implementation. Solutions have since been developed for the case of progressive tetrahedralizations, another interesting generalization of progressive meshes.

Progressive meshes.

H. Hoppe.

SIGGRAPH 1996, 99-108.

[info] [paper] [talk] [cessna movie] [dragon movie] [sandal movie] [geomorph movie] [video] [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.
In addition, we present a new mesh simplification procedure for constructing a PM representation from an arbitrary mesh. The goal of this optimization procedure is to preserve not just the geometry of the original mesh, but more importantly its overall appearance as defined by its discrete and scalar appearance attributes such as material identifiers, color values, normals, and texture coordinates. We demonstrate construction of the PM representation and its applications using several practical models.

More recent papers describe faster simplification criteria, such as the quadric error metric scheme of Garland and Heckbert, the memoryless scheme of Lindstrom and Turk, and my improved quadric error metric in Visualization 1999. But, the first 4 pages are still excellent. The paper should have made it more obvious that a geomorph can directly transition between any two PM meshes by simultaneously moving many vertices.

Automatic reconstruction of B-spline surfaces of arbitrary topological type.

M. Eck, H. Hoppe.

SIGGRAPH 1996, 325-334.

[info] [paper] [talk] [data]

Creating freeform surfaces is a challenging task even with advanced geometric modeling systems. Laser range scanners offer a promising alternative for model acquisition — the 3D scanning of existing objects or clay maquettes. The problem of converting the dense point sets produced by laser scanners into useful geometric models is referred to as surface reconstruction.
In this paper, we present a procedure for reconstructing a tensor product B-spline surface from a set of scanned 3D points. Unlike previous work which considers primarily the problem of fitting a single B-spline patch, our goal is to directly reconstruct a surface of arbitrary topological type. We must therefore define the surface as a network of B-spline patches. A key ingredient in our solution is a scheme for automatically constructing both a network of patches and a parametrization of the data points over these patches. In addition, we define the B-spline surface using a surface spline construction, and demonstrate that such an approach leads to an efficient procedure for fitting the surface while maintaining tangent plane continuity. We explore adaptive refinement of the patch network in order to satisfy user-specified error tolerances, and demonstrate our method on both synthetic and real data.

Reconstructing arbitrary B-spline surfaces is difficult, and this paper tackles the problem in a fully automatic approach. For some applications, it may be more practical to let the user manually specify the patch boundaries (see the related paper by Krishnamurthy and Levoy in the same proceedings). Still, the surface spline construction is useful in this context for maintaining C1 continuity without resort to constrained optimization. Sorry, the code is not available. Subdivision surfaces, which have gained popularity recently, make this reconstruction problem so much easier... (see my SIGGRAPH 1994 paper).

Multiresolution analysis of arbitrary meshes.

M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, W. Stuetzle.

SIGGRAPH 1995, 173-182.

[info] [paper] [talk] [video]

In computer graphics and geometric modeling, shapes are often represented by triangular meshes. With the advent of laser scanning systems, meshes of extreme complexity are rapidly becoming commonplace. Such meshes are notoriously expensive to store, transmit, render, and are awkward to edit. Multiresolution analysis offers a simple, unified, and theoretically sound approach to dealing with these problems. Lounsbery et al. have recently developed a technique for creating multiresolution representations for a restricted class of meshes with subdivision connectivity. Unfortunately, meshes encountered in practice typically do not meet this requirement. In this paper we present a method for overcoming the subdivision connectivity restriction, meaning that completely arbitrary meshes can now be converted to multiresolution form. The method is based on the approximation of an arbitrary initial mesh M by a mesh Mj that has subdivision connectivity and is guaranteed to be within a specified tolerance.
The key ingredient of our algorithm is the construction of a parametrization of M over a simple domain. We expect this parametrization to be of use in other contexts, such as texture mapping or the approximation of complex meshes by NURBS patches.

Novel technique for parametrizing an arbitrary triangle mesh over a simpler triangular domain of the same topological type. Subsequently, two enhancements to this paper were presented: Vertex-based Delaunay triangulation (to improve the mesh partition) and Hierarchical computation of PL harmonic embeddings (to speed up harmonic maps). The approach of remeshing a model to have subdivision connectivity was made more practical by the MAPS scheme of Lee et al in SIGGRAPH 1998. The paper is often cited for introducing the harmonic map in the context of mesh parametrization. This harmonic/conformal map has been generalized to allow free boundaries, in LSCM and DCP, which are in fact equivalent, and also identical to harmonic maps for fixed boundary.

Surface reconstruction from unorganized points.

H. Hoppe.

PhD Thesis, Dept. of Computer Science and Engineering, University of Washington, June 1994.

[info] [paper] [talk] [data] [code] [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.
Previous surface reconstruction methods have typically required additional knowledge, such as structure in the data, known surface genus, or orientation information. In contrast, the method outlined in this thesis requires only the 3D coordinates of the data points. From the data, the method is able to automatically infer the topological type of the surface, its geometry, and the presence and location of features such as boundaries, creases, and corners.
The reconstruction method has three major phases: 1) initial surface estimation, 2) mesh optimization, and 3) piecewise smooth surface optimization. A key ingredient in phase 3, and another principal contribution of this thesis, is the introduction of a new class of piecewise smooth representations based on subdivision. The effectiveness of the three-phase reconstruction method is demonstrated on a number of examples using both simulated and real data.
Phases 2 and 3 of the surface reconstruction method can also be used to approximate existing surface models. By casting surface approximation as a global optimization problem with an energy function that directly measures deviation of the approximation from the original surface, models are obtained that exhibit excellent accuracy to conciseness trade-offs. Examples of piecewise linear and piecewise smooth approximations are generated for various surfaces, including meshes, NURBS surfaces, CSG models, and implicit surfaces.

Really, there was more work here than the stapling of three papers :-)    This surface reconstruction problem has continued to be an active area; see the recent papers by Nina Amenta, the commercial product by Geomagic, and Poisson surface reconstruction. This reconstructed mannequin head has been my small contribution to the pool of geometric models commonly used in graphics.

Piecewise Smooth Surface Reconstruction.

H. Hoppe, T. DeRose, T. Duchamp, M. Halstead, H. Jin, J. McDonald, J. Schweitzer, W. Stuetzle.

SIGGRAPH 1994, 295-302.

[info] [paper] [data] [code]

We present a general method for automatic reconstruction of accurate, concise, piecewise smooth surface models from scattered range data. The method can be used in a variety of applications such as reverse engineering — the automatic generation of CAD models from physical objects. Novel aspects of the method are its ability to model surfaces of arbitrary topological type and to recover sharp features such as creases and corners. The method has proven to be effective, as demonstrated by a number of examples using both simulated and real data.
A key ingredient in the method, and a principal contribution of this paper, is the introduction of a new class of piecewise smooth surface representations based on subdivision. These surfaces have a number of properties that make them ideal for use in surface reconstruction: they are simple to implement, they can model sharp features concisely, and they can be fit to scattered range data using an unconstrained optimization procedure.

Through general optimization, this method is able to infer sharp features in the underlying geometry by simply fitting the data points. With the growing interest in subdivision surfaces, this surface fitting technique may prove useful. The paper is often cited for its introduction of sharp features in subdivision surface schemes. These features were extended in the work of Biermann et al. The SIGGRAPH 1998 paper by DeRose et al. presents extensions for "fractionally smooth" surface features.

Mesh optimization.

H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, W. Stuetzle.

SIGGRAPH 1993, 19-26.

[info] [paper] [extended TR UW CSE 1993-01-01] [data] [code]

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.

H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, W. Stuetzle.

SIGGRAPH 1992, 71-78.

[info] [paper] [data_in] [data_out] [code] [errata]

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.