Detailed Publications
|
Sandwiched compression: Repurposing standard codecs with neural network wrappers.
arXiv, 2024.
Improved image and video compression using neural pre- and post-processing.
We propose sandwiching standard image and video codecs between pre- and post-processing neural networks.
The networks are jointly trained through a differentiable codec proxy to minimize a given rate-distortion
loss. This sandwich architecture not only improves the standard codec's performance on its intended
content, it can effectively adapt the codec to other types of image/video content and to other distortion
measures. Essentially, the sandwich learns to transmit “neural code images” that optimize
overall rate-distortion performance even when the overall problem is well outside the scope of the codec's
design. Through a variety of examples, we apply the sandwich architecture to sources with different
numbers of channels, higher resolution, higher dynamic range, and perceptual distortion measures. The
results demonstrate substantial improvements (up to 9 dB gains or up to 30% bitrate reductions) compared to
alternative adaptations. We derive VQ equivalents for the sandwich, establish optimality properties, and
design differentiable codec proxies approximating current standard codecs. We further analyze model
complexity, visual quality under perceptual metrics, as well as sandwich configurations that offer
interesting potentials in image/video compression and streaming.
No hindsights yet.
|
|
Distributed Poisson surface reconstruction.
Computer Graphics Forum, 42(6), 2023.
Fast slab-based parallel Poisson reconstruction on a compute cluster.
Screened Poisson surface reconstruction robustly creates meshes from oriented point sets. For large
datasets, the technique requires hours of computation and significant memory. We present a method to
parallelize and distribute this computation over multiple commodity client nodes. The method partitions
space on one axis into adaptively sized slabs containing balanced subsets of points. Because the Poisson
formulation involves a global system, the challenge is to maintain seamless consistency at the slab
boundaries and obtain a reconstruction that is indistinguishable from the serial result. To this end, we
express the reconstructed indicator function as a sum of a low-resolution term computed on a server and
high-resolution terms computed on distributed clients. Using a client–server architecture, we map the
computation onto a sequence of serial server tasks and parallel client tasks, separated by synchronization
barriers. This architecture also enables low-memory evaluation on a single computer, albeit without
speedup. We demonstrate a 700 million vertex reconstruction of the billion point David statue scan in less
than 20 min on a 65-node cluster with a maximum memory usage of 45 GB/node, or in 14 h on a single node.
No hindsights yet.
|
|
Sandwiched image compression: Increasing the resolution and dynamic range of standard codecs.
Picture Coding Symposium (PCS) 2022. (Best Paper Finalist.)
Neural pre- and post-processing for compressing higher-resolution and HDR images.
Given a standard image codec, we compress images that may have higher resolution and/or higher bit depth
than allowed in the codec's specifications, by sandwiching the standard codec between a neural
pre-processor (before the standard encoder) and a neural post-processor (after the standard decoder).
Using a differentiable proxy for the standard codec, we design the neural pre- and post-processors to
transport the high resolution (super-resolution, SR) or high bit depth (high dynamic range, HDR) images as
lower resolution and lower bit depth images. The neural processors accomplish this with spatially coded
modulation, which acts as watermarks to preserve the important image detail during compression.
Experiments show that compared to conventional methods of transmitting high resolution or high bit depth
through lower resolution or lower bit depth codecs, our sandwich architecture gains ~9 dB for SR images and
~3 dB for HDR images at the same rate over large test sets. We also observe significant gains in visual
quality.
No hindsights yet.
|
|
Sandwiched image compression: Wrapping neural networks around a standard codec.
IEEE International Conference on Image Processing (ICIP) 2021.
Improved image compression using neural pre- and post-processing.
We sandwich a standard image codec between two neural networks: a preprocessor that outputs neural codes,
and a postprocessor that reconstructs the image. The neural codes are compressed as ordinary images by the
standard codec. Using differentiable proxies for both rate and distortion, we develop a rate-distortion
optimization framework that trains the networks to generate neural codes that are efficiently compressible
as images. This architecture not only improves rate-distortion performance for ordinary RGB images, but
also enables efficient compression of alternative image types (such as normal maps of computer graphics)
using standard image codecs. Results demonstrate the effectiveness and flexibility of neural processing in
mapping a variety of input data modalities to the rigid structure of standard codecs. A surprising result
is that the rate-distortion-optimized neural processing seamlessly learns to transport color images using a
single-channel (grayscale) codec.
No hindsights yet.
|
|
Project Starline: A high-fidelity telepresence system.
ACM Trans. Graphics (SIGGRAPH Asia), 40(6), 2021.
Chat with a remote person as if they were copresent.
We present a real-time bidirectional communication system that lets two people, separated by distance,
experience a face-to-face conversation as if they were copresent. It is the first telepresence system that
is demonstrably better than 2D videoconferencing, as measured using participant ratings (e.g., presence,
attentiveness, reaction-gauging, engagement), meeting recall, and observed nonverbal behaviors (e.g., head
nods, eyebrow movements). This milestone is reached by maximizing audiovisual fidelity and the sense of
copresence in all design elements, including physical layout, lighting, face tracking, multi-view capture,
microphone array, multi-stream compression, loudspeaker output, and lenticular display. Our system achieves
key 3D audiovisual cues (stereopsis, motion parallax, and spatialized audio) and enables the full range of
communication cues (eye contact, hand gestures, and body language), yet does not require special glasses or
body-worn microphones/headphones. The system consists of a head-tracked autostereoscopic display,
high-resolution 3D capture and rendering subsystems, and network transmission using compressed color and
depth video streams. Other contributions include a novel image-based geometry fusion algorithm, free-space
dereverberation, and talker localization.
My contributions focused on the real-time compression and rendering technologies.
Related patent publications include
Spatially adaptive video compression for multiple streams of color and depth and
Image-based geometric fusion of multiple depth images using ray casting.
|
|
Poisson surface reconstruction with envelope constraints.
Symposium on Geometry Processing 2020.
Improved reconstruction using Dirichlet constraints on visual hull or depth hull.
Reconstructing surfaces from scanned 3D points has been an important research area for several decades.
One common approach that has proven efficient and robust to noise is implicit surface reconstruction,
i.e. fitting to the points a 3D scalar function (such as an indicator function or signed-distance field)
and then extracting an isosurface. Though many techniques fall within this category, existing methods
either impose no boundary constraints or impose Dirichlet/Neumann conditions on the surface of a bounding
box containing the scanned data.
In this work, we demonstrate the benefit of supporting Dirichlet constraints on a general boundary. To this end, we adapt the Screened Poisson Reconstruction algorithm to input a constraint envelope in addition to the oriented point cloud. We impose Dirichlet boundary conditions, forcing the reconstructed implicit function to be zero outside this constraint surface. Using a visual hull and/or depth hull derived from RGB-D scans to define the constraint envelope, we obtain substantially improved surface reconstructions in regions of missing data.
No hindsights yet.
|
|
An adaptive multigrid solver for applications in computer graphics.
Computer Graphics Forum, 38(1), 2019.
General-purpose adaptive finite-elements multigrid solver in arbitrary dimension.
A key processing step in numerous computer graphics applications is the solution of a linear system
discretized over a spatial domain. Often, the linear system can be represented using an adaptive domain
tessellation, either because the solution will only be sampled sparsely, or because the solution is known to be
“interesting” (e.g. high-frequency) only in localized regions. In this work, we propose an adaptive,
finite-elements, multigrid solver capable of efficiently solving such linear systems. Our solver is
designed to be general-purpose, supporting finite-elements of different degrees, across different
dimensions, and supporting both integrated and pointwise constraints. We demonstrate the efficacy of our
solver in applications including surface reconstruction, image stitching, and Euclidean Distance Transform
calculation.
No hindsights yet.
|
|
Neural rerendering in the wild.
CVPR 2019 (oral).
Learn views under varying appearance from internet photos and reconstructed points.
We explore total scene capture — recording, modeling, and rerendering a scene under varying
appearance such as season and time of day. Starting from internet photos of a tourist landmark, we apply
traditional 3D reconstruction to register the photos and approximate the scene as a point cloud. For each
photo, we render the scene points into a deep framebuffer, and train a neural network to learn the mapping
of these initial renderings to the actual photos. This rerendering network also takes as input a latent
appearance vector and a semantic mask indicating the location of transient objects like pedestrians. The
model is evaluated on several datasets of publicly available images spanning a broad range of illumination
conditions. We create short videos demonstrating realistic manipulation of the image viewpoint, appearance,
and semantic labeling. We also compare results with prior work on scene reconstruction from internet
photos.
No hindsights yet.
|
|
Montage4D: Interactive seamless fusion of multiview video textures.
Symposium on Interactive 3D Graphics and Games (I3D), 2018.
Temporally coherent seamless stitching of multi-view textures.
The commoditization of virtual and augmented reality devices and the availability of inexpensive consumer
depth cameras have catalyzed a resurgence of interest in spatiotemporal performance capture. Recent
systems like Fusion4D and Holoportation address several crucial problems in the real-time fusion of
multiview depth maps into volumetric and deformable representations. Nonetheless, stitching multiview
video textures onto dynamic meshes remains challenging due to imprecise geometries, occlusion seams, and
critical time constraints. In this paper, we present a practical solution towards real-time seamless
texture montage for dynamic multiview reconstruction. We build on the ideas of dilated depth
discontinuities and majority voting from Holoportation to reduce ghosting effects when blending textures.
In contrast to their approach, we determine the appropriate blend of textures per vertex using
view-dependent rendering techniques, so as to avert fuzziness caused by the ubiquitous normal-weighted
blending. By leveraging geodesics-guided diffusion and temporal texture fields, our algorithm mitigates
spatial occlusion seams while preserving temporal consistency. Experiments demonstrate significant
enhancement in rendering quality, especially in detailed regions such as faces. We envision a wide range
of applications for Montage4D, including immersive telepresence for business, training, and live
entertainment.
No hindsights yet.
|
|
Gradient-domain processing within a texture atlas.
ACM Trans. Graphics (SIGGRAPH) 37(4), 2018.
Fast processing of surface signals directly in texture domain, avoiding resampling.
Processing signals on surfaces often involves resampling the signal over the vertices of a dense mesh and
applying mesh-based filtering operators. We present a framework to process a signal directly in a texture
atlas domain. The benefits are twofold: avoiding resampling degradation and exploiting the regularity of
the texture image grid. The main challenges are to preserve continuity across atlas chart boundaries and
to adapt differential operators to the non-uniform parameterization. We introduce a novel function space
and multigrid solver that jointly enable robust, interactive, and geometry-aware signal processing. We
demonstrate our approach using several applications including smoothing and sharpening, multiview
stitching, geodesic distance computation, and line integral convolution.
No hindsights yet.
|
|
Gigapixel panorama video loops.
ACM Trans. Graphics, 37(1), 2018. (Presented at SIGGRAPH 2018.)
Spatiotemporally consistent looping panorama merged from 2D grid of videos.
We present the first technique to create wide-angle, high-resolution looping panoramic videos. Starting
with a 2D grid of registered videos acquired on a robotic mount, we formulate a combinatorial optimization
to determine for each output pixel the source video and looping parameters that jointly maximize
spatiotemporal consistency. This optimization is accelerated by reducing the set of source labels using a
graph-coloring scheme. We parallelize the computation and implement it out-of-core by partitioning the
domain along low-importance paths. The merged panorama is assembled using gradient-domain blending and
stored as a hierarchy of video tiles. Finally, an interactive viewer adaptively preloads these tiles for
responsive browsing and allows the user to interactively edit and improve local regions. We demonstrate
these techniques on gigapixel-sized looping panoramas.
No hindsights yet.
|
|
Spatiotemporal atlas parameterization for evolving meshes.
ACM Trans. Graphics (SIGGRAPH) 36(4), 2017.
Tracked mesh with sparse incremental changes in connectivity and texture map.
We convert a sequence of unstructured textured meshes into a mesh with incrementally changing
connectivity and atlas parameterization.
Like prior work on surface tracking, we seek temporally coherent mesh connectivity to enable efficient
representation of surface geometry and texture.
Like recent work on evolving meshes,
we pursue local remeshing to permit tracking over long
sequences containing significant deformations or topological changes.
Our main contribution is to show that both goals are realizable within a common framework
that simultaneously evolves both the set of mesh triangles and the parametric map.
Sparsifying the remeshing operations allows the formation of large spatiotemporal texture charts.
These charts are packed as prisms into a 3D atlas for a texture video.
Reducing tracking drift using mesh-based optical flow helps improve compression of the resulting video stream.
No hindsights yet.
|
|
Motion graphs for unstructured textured meshes.
ACM Trans. Graphics (SIGGRAPH), 35(4), 2016.
Automatic smooth transitions between similar meshes in a scanned sequence.
Scanned performances are commonly represented in virtual environments
as sequences of textured triangle meshes.
Detailed shapes deforming over time benefit from
meshes with dynamically evolving connectivity.
We analyze these unstructured mesh sequences to automatically synthesize
motion graphs with new smooth transitions between compatible poses and actions.
Such motion graphs enable natural periodic motions,
stochastic playback, and user-directed animations.
The main challenge of unstructured sequences
is that the meshes differ not only in connectivity
but also in alignment, shape, and texture.
We introduce new geometry processing techniques to address these problems
and demonstrate visually seamless transitions on high-quality captures.
Although most of our data is captured at 30 frames/second, we find that it is easy to interpolate the
geometry (in the GPU) to the native display rate (e.g. 90 fps) for the best experience in a virtual
environment.
|
|
New controls for combining images in correspondence.
IEEE Trans. Vis. Comput. Graphics, 22(7), 2016. (Presented at I3D 2016.)
Multiscale edge-aware melding of geometry and shape from two images.
When interpolating images, for instance in the context of morphing, there are myriad approaches for
defining correspondence maps that align structurally similar elements. However, the actual interpolation
usually involves simple functions for both geometric paths and color blending. In this paper we explore
new types of controls for combining two images related by a correspondence map. Our insight is to apply
recent edge-aware decomposition techniques, not just to the image content but to the map itself. Our
framework establishes an intuitive low-dimensional parameter space for merging the shape and color from the
two source images at both low and high frequencies. A gallery-based user interface enables interactive
traversal of this rich space, to either define a morph path or synthesize new hybrid images. Extrapolation
of the shape parameters achieves compelling effects. Finally we demonstrate an extension of the framework
to videos.
No hindsights yet.
|
|
Fast computation of seamless video loops.
ACM Trans. Graphics (SIGGRAPH Asia), 34(6), 2015.
High-quality looping video generated in nearly real-time.
Short looping videos concisely capture the dynamism of natural scenes. Creating seamless loops usually
involves maximizing spatiotemporal consistency and applying Poisson blending. We take an end-to-end view
of the problem and present new techniques that jointly improve loop quality while also significantly
reducing processing time. A key idea is to relax the consistency constraints to anticipate the subsequent
blending, thereby enabling looping of low-frequency content like moving clouds and changing illumination.
We also analyze the input video to remove an undesired bias toward short loops. The quality gains are
demonstrated visually and confirmed quantitatively using a new gradient-domain consistency metric. We
improve system performance by classifying potentially loopable pixels, masking the 2D graph cut, pruning
graph-cut labels based on dominant periods, and optimizing on a coarse grid while retaining finer detail.
Together these techniques reduce computation times from tens of minutes to nearly real-time.
We adapted this video looping into the “Live Images” feature of the
Microsoft Pix Camera
iOS app
which shipped in July 2016.
|
|
High-quality streamable free-viewpoint video.
ACM Trans. Graphics (SIGGRAPH), 34(4), 2015.
Multimodal reconstruction of tracked textured meshes.
We present the first end-to-end solution to create high-quality free-viewpoint video encoded as a compact
data stream. Our system records performances using a dense set of RGB and IR video cameras, generates
dynamic textured surfaces, and compresses these to a streamable 3D video format. Four technical advances
contribute to high fidelity and robustness: multimodal multi-view stereo fusing RGB, IR, and silhouette
information; adaptive meshing guided by automatic detection of perceptually salient areas; mesh tracking to
create temporally coherent subsequences; and encoding of tracked textured meshes as an MPEG video
stream. Quantitative experiments demonstrate geometric accuracy, texture fidelity, and encoding
efficiency. We release several datasets with calibrated inputs and processed results to foster future
research.
Letting mesh connectivity change temporally allows capture of more general scenes,
but makes it more difficult to create transitions between different motions
and to create an efficient texture atlas;
we address these problems in the subsequent papers
Motion graphs for unstructured textured meshes and
Spatiotemporal atlas parameterization for evolving meshes.
|
|
Semi-automated video morphing.
Eurographics Symposium on Rendering, 2014.
Transition across two videos using optimized spatiotemporal alignment.
We explore creating smooth transitions between videos of different scenes. As in traditional image
morphing, good spatial correspondence is crucial to prevent ghosting, especially at silhouettes. Video
morphing presents added challenges. Because motions are often unsynchronized, temporal alignment is also
necessary. Applying morphing to individual frames leads to discontinuities, so temporal coherence must be
considered. Our approach is to optimize a full spatiotemporal mapping between the two videos. We reduce
tedious interaction by letting the optimization derive the fine-scale map given only sparse user-specified
constraints. For robustness, the optimization objective examines structural similarity of the video
content. We demonstrate the approach on a variety of videos, obtaining results using few explicit
correspondences.
No hindsights yet.
|
|
Automating image morphing using structural similarity on a halfway domain.
ACM Trans. Graphics, 33(5), 2014. (Presented at SIGGRAPH 2014.)
Fast optimization to align intricate shapes using little interactive guidance.
The main challenge in achieving good image morphs is to create a map that aligns corresponding image
elements. Our aim is to help automate this often tedious task. We compute the map by optimizing the
compatibility of corresponding warped image neighborhoods using an adaptation of structural similarity.
The optimization is regularized by a thin-plate spline, and may be guided by a few user-drawn points. We
parameterize the map over a halfway domain and show that this representation offers many benefits. The map
is able to treat the image pair symmetrically, model simple occlusions continuously, span partially
overlapping images, and define extrapolated correspondences. Moreover, it enables direct evaluation of the
morph in a pixel shader without mesh rasterization. We improve the morphs by optimizing quadratic motion
paths and by seamlessly extending content beyond the image boundaries. We parallelize the algorithm on a
GPU to achieve a responsive interface and demonstrate challenging morphs obtained with little effort.
One exciting aspect is that just as in the earlier project
Image-space bidirectional scene reprojection,
the iterative implicit solver is able to evaluate the morph color directly in a pixel shader,
without requiring any geometric tessellation, i.e. using only “gather” operations.
|
|
A fresh look at generalized sampling.
Foundations and Trends in Computer Graphics and Vision, 8(1), 2014.
Extension of recent signal-processing techniques to graphics filtering.
Discretization and reconstruction are fundamental operations in computer graphics, enabling the conversion
between sampled and continuous representations. Major advances in signal-processing research have shown
that these operations can often be performed more efficiently by decomposing a filter into two parts: a
compactly supported continuous-domain function and a digital filter. This strategy of “generalized
sampling” has appeared in a few graphics papers, but is largely unexplored in our community. This
survey broadly summarizes the key aspects of the framework, and delves into specific applications in
graphics. Using new notation, we concisely present and extend several key techniques. In addition, we
demonstrate benefits for prefiltering in image downscaling and supersample-based rendering, and analyze the
effect that generalized sampling has on the noise due to Monte Carlo estimation. We conclude with a
qualitative and quantitative comparison of traditional and generalized filters.
An earlier version of this paper is
IMPA Tech. Report E022/2011 & Microsoft Research MSR-TR-2011-16, February 2011
.
|
|
Automated video looping with progressive dynamism.
ACM Trans. Graphics (SIGGRAPH), 32(4), 2013.
Representation for seamlessly looping video with controllable level of dynamism.
Given a short video we create a representation that captures a spectrum of looping videos with varying
levels of dynamism, ranging from a static image to a highly animated loop. In such a progressively dynamic
video, scene liveliness can be adjusted interactively using a slider control. Applications include
background images and slideshows, where the desired level of activity may depend on personal taste or mood.
The representation also provides a segmentation of the scene into independently looping regions, enabling
interactive local adjustment over dynamism. For a landscape scene, this control might correspond to
selective animation and deanimation of grass motion, water ripples, and swaying trees. Converting
arbitrary video to looping content is a challenging research problem. Unlike prior work, we explore an
optimization in which each pixel automatically determines its own looping period. The resulting nested
segmentation of static and dynamic scene regions forms an extremely compact representation.
The time-mapping equation (1) has a simpler form:
ϕ(x, t) = sx +
((t - sx)
mod px).
(One must be careful that the C/C++
remainder
operator “%” differs from the
modulo
operator “mod”
for negative numbers.)
Thanks to Mark Finch for preparing and optimizing the code in our demo tool release. See also our more recent work on improving loop quality and speeding up its computation. |
|
Screened Poisson surface reconstruction.
ACM Trans. Graphics, 32(3), 2013. (Presented at SIGGRAPH 2013.)
Improved geometric fidelity and linear-complexity adaptive hierarchical solver.
Poisson surface reconstruction creates watertight surfaces from oriented point sets. In this work we
extend the technique to explicitly incorporate the points as interpolation constraints. The extension can
be interpreted as a generalization of the underlying mathematical framework to a screened Poisson equation.
In contrast to other image and geometry processing techniques, the screening term is defined over a sparse
set of points rather than over the full domain. We show that these sparse constraints can nonetheless be
integrated efficiently. Because the modified linear system retains the same finite-element discretization,
the sparsity structure is unchanged, and the system can still be solved using a multigrid approach.
Moreover we present several algorithmic improvements that together reduce the time complexity of the solver
to linear in the number of points, thereby enabling faster, higher-quality surface reconstructions.
See also the comments in the earlier paper
Poisson surface reconstruction on which this builds.
|
|
Cliplets: Juxtaposing still and dynamic imagery.
Symposium on User Interface Software and Technology (UIST) 2012. (Best Paper Award.)
Cinemagraphs and more general spatiotemporal compositions from handheld video.
We explore creating cliplets, a form of visual media that juxtaposes still image and video segments, both
spatially and temporally, to expressively abstract a moment. Much as in cinemagraphs, the tension between
static and dynamic elements in a cliplet reinforces both aspects, strongly focusing the viewer's attention.
Creating this type of imagery is challenging without professional tools and training. We develop a set of
idioms, essentially spatiotemporal mappings, that characterize cliplet elements, and use these idioms in an
interactive system to quickly compose a cliplet from ordinary handheld video. One difficulty is to avoid
artifacts in the cliplet composition without resorting to extensive manual input. We address this with
automatic alignment, looping optimization and feathering, simultaneous matting and compositing, and
Laplacian blending. A key user-interface challenge is to provide affordances to define the parameters of
the mappings from input time to output time while maintaining a focus on the cliplet being created. We
demonstrate the creation of a variety of cliplet types. We also report on informal feedback as well as a
more structured survey of users.
With cliplets, the user interactively sketches static and dynamic regions, each assigned a uniform looping period. Our subsequent work Automated video looping animates the entire scene without user assistance, and uses combinatorial optimization to infer the optimal looping interval for each pixel. See some nice professionally created cinemagraphs at https://cinemagraphs.com/. |
|
A subdivision-based representation for vector image editing.
IEEE Trans. Vis. Comput. Graphics, 18(11), Nov. 2012. (Presented at I3D 2013.)
(Spotlight Paper.) Piecewise-smooth subdivision for representing and manipulating images.
Vector graphics has been employed in a wide variety of applications due to its scalability and editability.
Editability is a high priority for artists and designers who wish to produce vector-based graphical content
with user interaction. In this paper, we introduce a new vector image representation based on piecewise
smooth subdivision surfaces, which is a simple, unified and flexible framework that supports a variety of
operations, including shape editing, color editing, image stylization, and vector image processing. These
operations effectively create novel vector graphics by reusing and altering existing image vectorization
results. Because image vectorization yields an abstraction of the original raster image, controlling the
level of detail of this abstraction is highly desirable. To this end, we design a feature-oriented vector
image pyramid that offers multiple levels of abstraction simultaneously. Our new vector image
representation can be rasterized efficiently using GPU-accelerated subdivision. Experiments indicate that
our vector image representation achieves high visual quality and better supports editing operations than
existing representations.
Using a common subdivision process to define both the geometric outlines and the (piecewise) smooth color
field is elegant.
|
|
Freeform vector graphics with controlled thin-plate splines.
ACM Trans. Graphics (SIGGRAPH Asia), 30(6), 2011.
Rich set of curve and point controls for intuitive and expressive color interpolation.
Recent work defines vector graphics using diffusion between colored curves. We explore higher-order
fairing to enable more natural interpolation and greater expressive control. Specifically, we build on
thin-plate splines which provide smoothness everywhere except at user-specified tears and creases
(discontinuities in value and derivative respectively). Our system lets a user sketch discontinuity curves
without fixing their colors, and sprinkle color constraints at sparse interior points to obtain smooth
interpolation subject to the outlines. We refine the representation with novel contour and slope curves,
which anisotropically constrain interpolation derivatives. Compound curves further increase editing power
by expanding a single curve into multiple offsets of various basic types (value, tear, crease, slope, and
contour). The vector constraints are discretized over an image grid, and satisfied using a hierarchical
solver. We demonstrate interactive authoring on a desktop CPU.
We should have mentioned the work of
[Xia et al. 2009. Patch-based image vectorization
with automatic curvilinear feature alignment] which also introduces higher-order color reconstruction
for vector graphics. It optimizes parametric Bezier patches with Thin-Plate Spline color functions to
approximate a given image.
|
|
GPU-efficient recursive filtering and summed-area tables.
ACM Trans. Graphics (SIGGRAPH Asia), 30(6), 2011.
Efficient overlapped computation of successive recursive filters on 2D images.
Image processing operations like blurring, inverse convolution, and summed-area tables are often computed
efficiently as a sequence of 1D recursive filters. While much research has explored parallel recursive
filtering, prior techniques do not optimize across the entire filter sequence. Typically, a separate
filter (or often a causal-anticausal filter pair) is required in each dimension. Computing these filter
passes independently results in significant traffic to global memory, creating a bottleneck in GPU systems.
We present a new algorithmic framework for parallel evaluation. It partitions the image into 2D blocks,
with a small band of additional data buffered along each block perimeter. We show that these perimeter
bands are sufficient to accumulate the effects of the successive filters. A remarkable result is that the
image data is read only twice and written just once, independent of image size, and thus total memory
bandwidth is reduced even compared to the traditional serial algorithm. We demonstrate significant
speedups in GPU computation.
For completeness we could have mentioned
integral images,
a term used in computer vision [Viola and Jones 2001]
to also refer to
summed-area tables [Crow 1984].
|
|
Image-space bidirectional scene reprojection.
ACM Trans. Graphics (SIGGRAPH Asia), 30(6), 2011.
Real-time temporal upsampling through image-based reprojection of adjacent frames.
We introduce a method for increasing the framerate of real-time rendering applications. Whereas many
existing temporal upsampling strategies only reuse information from previous frames, our bidirectional
technique reconstructs intermediate frames from a pair of consecutive rendered frames. This significantly
improves the accuracy and efficiency of data reuse since very few pixels are simultaneously occluded in
both frames. We present two versions of this basic algorithm. The first is appropriate for fill-bound
scenes as it limits the number of expensive shading calculations, but involves rasterization of scene
geometry at each intermediate frame. The second version, our more significant contribution, reduces both
shading and geometry computations by performing reprojection using only image-based buffers. It warps and
combines the adjacent rendered frames using an efficient iterative search on their stored scene depth and
flow. Bidirectional reprojection introduces a small amount of lag. We perform a user study to investigate
this lag, and find that its effect is minor. We demonstrate substantial performance improvements (3-4X)
for a variety of applications, including vertex-bound and fill-bound scenes, multi-pass effects, and motion
blur.
One nice contribution is the idea of using an iterative implicit solver to locate the source pixel
given a velocity field.
In the more recent project
Automating image morphing
using structural similarity on a halfway domain,
we adapt this idea to evaluate an image morph directly in a pixel shader,
without requiring any geometric tessellation, i.e. using only “gather” operations.
|
|
Real-time classification of dance gestures from skeleton animation.
Symposium on Computer Animation 2011. (Honorable Mention.)
Recognition of Kinect motions using robust, low-dimensional feature vectors.
We present a real-time gesture classification system for skeletal wireframe motion. Its key components
include an angular representation of the skeleton designed for recognition robustness under noisy input, a
cascaded correlation-based classifier for multivariate time-series data, and a distance metric based on
dynamic time-warping to evaluate the difference in motion between an acquired gesture and an oracle for the
matching gesture. While the first and last tools are generic in nature and could be applied to any
gesture-matching scenario, the classifier is conceived based on the assumption that the input motion
adheres to a known, canonical time-base: a musical beat. On a benchmark comprising 28 gesture classes,
hundreds of gesture instances recorded using the XBOX Kinect platform and performed by dozens of subjects
for each gesture class, our classifier has an average accuracy of 96.9%, for approximately 4-second
skeletal motion recordings. This accuracy is remarkable given the input noise from the real-time depth
sensor.
This technology was adapted in the
Kinect Star Wars video game.
|
|
Antialiasing recovery.
ACM Trans. Graphics, 30(3), 2011. (Presented at SIGGRAPH 2011.)
Fast removal of jaggies introduced by many nonlinear image processing operations.
We present a method for restoring antialiased edges that are damaged by certain types of nonlinear image
filters. This problem arises with many common operations such as intensity thresholding, tone mapping,
gamma correction, histogram equalization, bilateral filters, unsharp masking, and certain
non-photorealistic filters. We present a simple algorithm that selectively adjusts the local gradients in
affected regions of the filtered image so that they are consistent with those in the original image. Our
algorithm is highly parallel and is therefore easily implemented on a GPU. Our prototype system can process
up to 500 megapixels per second and we present results for a number of different image filters.
Thanks to Mark Finch
for writing the Direct2D Custom Image Effect to demonstrate this technique!
|
|
Optimizing continuity in multiscale imagery.
ACM Trans. Graphics (SIGGRAPH Asia), 29(6), 2010.
Visually continuous mipmap pyramid spanning differing coarse- and fine-scale images.
Multiscale imagery often combines several sources with differing appearance. For instance, Internet-based
maps contain satellite and aerial photography. Zooming within these maps may reveal jarring transitions.
We present a scheme that creates a visually smooth mipmap pyramid from stitched imagery at several scales.
The scheme involves two new techniques. The first, structure transfer, is a nonlinear operator that
combines the detail of one image with the local appearance of another. We use this operator to inject
detail from the fine image into the coarse one while retaining color consistency. The improved structural
similarity greatly reduces inter-level ghosting artifacts. The second, clipped Laplacian blending, is an
efficient construction to minimize blur when creating intermediate levels. It considers the sum of all
inter-level image differences within the pyramid. We demonstrate continuous zooming of map imagery from
space to ground level.
No hindsights yet.
|
|
Metric-aware processing of spherical imagery.
ACM Trans. Graphics (SIGGRAPH Asia), 29(6), 2010.
Adaptively discretized equirectangular map for accurate spherical processing.
Processing spherical images is challenging. Because no spherical parameterization is globally uniform, an
accurate solver must account for the spatially varying metric. We present the first efficient metric-aware
solver for Laplacian processing of spherical data. Our approach builds on the commonly used
equirectangular parameterization, which provides differentiability, axial symmetry, and grid sampling.
Crucially, axial symmetry lets us discretize the Laplacian operator just once per grid row. One difficulty
is that anisotropy near the poles leads to a poorly conditioned system. Our solution is to construct an
adapted hierarchy of finite elements, adjusted at the poles to maintain derivative continuity, and
selectively coarsened to bound element anisotropy. The resulting elements are nested both within and
across resolution levels. A streaming multigrid solver over this hierarchy achieves excellent convergence
rate and scales to huge images. We demonstrate applications in reaction-diffusion texture synthesis and
panorama stitching and sharpening.
No hindsights yet.
|
|
Seamless montage for texturing models.
Computer Graphics Forum (Eurographics), 29(2), 479-486, 2010.
Optimized alignment and merging of photographs for texturing approximate geometry.
We present an automatic method to recover high-resolution texture over an object by mapping detailed
photographs onto its surface. Such high-resolution detail often reveals inaccuracies in geometry and
registration, as well as lighting variations and surface reflections. Simple image projection results in
visible seams on the surface. We minimize such seams using a global optimization that assigns compatible
texture to adjacent triangles. The key idea is to search not only combinatorially over the source images,
but also over a set of local image transformations that compensate for geometric misalignment. This broad
search space is traversed using a discrete labeling algorithm, aided by a coarse-to-fine strategy. Our
approach significantly improves resilience to acquisition errors, thereby allowing simple and easy creation
of textured models for use in computer graphics.
No hindsights yet.
|
|
Distributed gradient-domain processing of planar and spherical images.
ACM Trans. Graphics, 29(2), 14, 2010. (Presented at SIGGRAPH 2010.)
Spherical gradient-domain processing on a Terapixel sky.
Gradient-domain processing is widely used to edit and combine images. In this paper we extend the
framework in two directions. First, we adapt the gradient-domain approach to operate on a spherical
domain, to enable operations such as seamless stitching, dynamic-range compression, and gradient-based
sharpening over spherical imagery. An efficient streaming computation is obtained using a new spherical
parameterization with bounded distortion and localized boundary constraints. Second, we design a
distributed solver to efficiently process large planar or spherical images. The solver partitions images
into bands, streams through these bands in parallel within a networked cluster, and schedules computation
to hide the necessary synchronization latency. We demonstrate our contributions on several datasets
including the Digitized Sky Survey, a terapixel spherical scan of the night sky.
See the resulting seamless terapixel night sky in WorldWide Telescope. In this project, the image data had to be parameterized using the “TOAST” spherical map. As explained in the paper, the resulting gradient-domain solution was therefore inexact. Our subsequent paper Metric-aware processing of spherical imagery shows that when working with the (commonly used) equirectangular parameterization, one can adaptively discretize the domain to achieve an efficient, exact solution over the sphere. |
|
Amortized supersampling.
ACM Trans. Graphics (SIGGRAPH Asia), 28(5), 2009.
Adaptive reuse of pixels from previous frames for high-quality antialiasing.
We present a real-time rendering scheme that reuses shading samples from earlier time frames to achieve
practical antialiasing of procedural shaders. Using a reprojection strategy, we maintain several sets of
shading estimates at subpixel precision, and incrementally update these such that for most pixels only one
new shaded sample is evaluated per frame. The key difficulty is to prevent accumulated blurring during
successive reprojections. We present a theoretical analysis of the blur introduced by reprojection
methods. Based on this analysis, we introduce a nonuniform spatial filter, an adaptive recursive temporal
filter, and a principled scheme for locally estimating the spatial blur. Our scheme is appropriate for
antialiasing shading attributes that vary slowly over time. It works in a single rendering pass on
commodity graphics hardware, and offers results that surpass 4x4 stratified supersampling in quality, at a
fraction of the cost.
Some related work is being pursued in the CryEngine 3 game platform,
as described by Anton Kaplanyan in a
SIGGRAPH
2010 course.
It also seems related to the temporal reprojection in
NVIDIA TXAA,
although there are few details on its technology.
|
|
Parallel Poisson surface reconstruction.
International Symposium on Visual Computing 2009.
Parallelization of Poisson reconstruction using domain decomposition.
In this work we describe a parallel implementation of the Poisson Surface Reconstruction algorithm based on
multigrid domain decomposition. We compare implementations using different models of data-sharing between
processors and show that a parallel implementation with distributed memory provides the best scalability.
Using our method, we are able to parallelize the reconstruction of models from one billion data points on
twelve processors across three machines, providing a ninefold speedup in running time without sacrificing
reconstruction accuracy.
See also the original
Poisson surface reconstruction
paper.
|
|
Parallel view-dependent level-of-detail control.
IEEE Trans. Vis. Comput. Graphics, 16(5), 2010.
Extended journal version with applications.
We present a scheme for view-dependent level-of-detail control that is implemented entirely on programmable
graphics hardware. Our scheme selectively refines and coarsens an arbitrary triangle mesh at the
granularity of individual vertices to create meshes that are highly adapted to dynamic view parameters.
Such fine-grain control has previously been demonstrated using sequential CPU algorithms. However, these
algorithms involve pointer-based structures with intricate dependencies that cannot be handled efficiently
within the restricted framework of GPU parallelism.We show that by introducing new data structures and
dependency rules, one can realize fine-grain progressive mesh updates as a sequence of parallel streaming
passes over the mesh elements. A major design challenge is that the GPU processes stream elements in
isolation. The mesh update algorithm has time complexity proportional to the selectively refined mesh, and
moreover can be amortized across several frames. The result is a single standard index buffer than can be
used directly for rendering. The static data structure is remarkably compact, requiring only 57% more
memory than an indexed triangle list. We demonstrate real-time exploration of complex models with normals
and textures, as well as shadowing and semitransparent surface rendering applications that make direct use
of the resulting dynamic index buffer.
This expanded version of the
conference paper
includes new diagrams and demonstrates some more rendering applications.
|
|
Parallel view-dependent refinement of progressive meshes.
Symposium on Interactive 3D Graphics and Games (I3D) 2009, 169-176.
Selective refinement of irregular mesh hierarchy using GPU streaming passes.
We present a scheme for view-dependent level-of-detail control that is implemented entirely on programmable
graphics hardware. Our scheme selectively refines and coarsens an arbitrary triangle mesh at the
granularity of individual vertices, to create meshes that are highly adapted to dynamic view parameters.
Such fine-grain control has previously been demonstrated using sequential CPU algorithms. However, these
algorithms involve pointer-based structures with intricate dependencies that cannot be handled efficiently
within the restricted framework of GPU parallelism. We show that by introducing new data structures and
dependency rules, one can realize fine-grain progressive mesh updates as a sequence of parallel streaming
passes over the mesh elements. A major design challenge is that the GPU processes stream elements in
isolation. The mesh update algorithm has time complexity proportional to the selectively refined mesh, and
moreover can be amortized across several frames. The static data structure is remarkably compact,
requiring only 57% more memory than an indexed triangle list. We demonstrate real-time exploration of
complex models with normals and textures.
We were invited to write an expanded version
of this conference paper in the IEEE Trans. Vis. Comput. Graphics journal.
|
|
Efficient traversal of mesh edges using adjacency primitives.
ACM Trans. Graphics (SIGGRAPH Asia), 27(5), 2008.
Fast rendering of shadow volumes, silhouettes, and motion blur.
Processing of mesh edges lies at the core of many advanced real-time rendering techniques, ranging from
shadow and silhouette computations, to motion blur and fur rendering. We present a scheme for efficient
traversal of mesh edges that builds on the adjacency primitives and programmable geometry shaders
introduced in recent graphics hardware. Our scheme aims to minimize the number of primitives while
maximizing SIMD parallelism. These objectives reduce to a set of discrete optimization problems on the
dual graph of the mesh, and we develop practical solutions to these graph problems. In addition, we extend
two existing vertex cache optimization algorithms to produce cache-efficient traversal orderings for
adjacency primitives. We demonstrate significant runtime speedups for several practical real-time
rendering algorithms.
It would be nice to extend this approach to the larger patch primitives
introduced in the
DirectX 11 hull shader.
|
|
Random-access rendering of general vector graphics.
ACM Trans. Graphics (SIGGRAPH Asia), 27(5), 2008.
GPU rendering of vector art over surfaces using cell-specialized descriptions.
We introduce a novel representation for random-access rendering of antialiased vector graphics on the GPU,
along with efficient encoding and rendering algorithms. The representation supports a broad class of
vector primitives, including multiple layers of semitransparent filled and stroked shapes, with quadratic
outlines and color gradients. Our approach is to create a coarse lattice in which each cell contains a
variable-length encoding of the graphics primitives it overlaps. These cell-specialized encodings are
interpreted at runtime within a pixel shader. Advantages include localized memory access and the ability
to map vector graphics onto arbitrary surfaces, or under arbitrary deformations. Most importantly, we
perform both prefiltering and supersampling within a single pixel shader invocation, achieving
inter-primitive antialiasing at no added memory bandwidth cost. We present an efficient encoding
algorithm, and demonstrate high-quality real-time rendering of complex, real-world examples.
One natural next step is to perform real-time conversion from the vector graphics primitives to the cell-specialized representation. This might be feasible with the increasing parallelism of the CPU. Also, it would be great to revisit the antialiasing at shape corners and for thin shapes, to further improve prefiltering for small primitives like fonts. Our earlier version of this paper, Texel programs for random-access antialiased vector graphics (MSR-TR-2007-95), also describes how a perfect hash data structure can be adapted as an alternative to the 2D indirection table. |
|
Factoring repeated content within and among images.
ACM Trans. Graphics (SIGGRAPH), 27(3), 2008.
Megatexture encoded by indirecting into an optimized epitome image.
We reduce transmission bandwidth and memory space for images by factoring their repeated content. A
transform map and a condensed epitome are created such that all image blocks can be reconstructed from
transformed epitome patches. The transforms may include affine deformation and color scaling to account
for perspective and tonal variations across the image. The factored representation allows efficient
random-access through a simple indirection, and can therefore be used for real-time texture mapping without
expansion in memory. Our scheme is orthogonal to traditional image compression, in the sense that the
epitome is amenable to further compression such as DXT. Moreover it allows a new mode of progressivity,
whereby generic features appear before unique detail. Factoring is also effective across a collection of
images, particularly in the context of image-based rendering. Eliminating redundant content lets us
include textures that are several times as large in the same memory space.
No hindsights yet.
|
|
Streaming multigrid for gradient-domain operations on large images.
ACM Trans. Graphics (SIGGRAPH), 27(3), 2008.
Perform k multigrid V-cycles in just k-1 streaming passes over the
data.
We introduce a new tool to solve the large linear systems arising from gradient-domain image processing.
Specifically, we develop a streaming multigrid solver, which needs just two sequential passes over
out-of-core data. This fast solution is enabled by a combination of three techniques: (1) use of
second-order finite elements (rather than traditional finite differences) to reach sufficient accuracy in a
single V-cycle, (2) temporally blocked relaxation, and (3) multi-level streaming to pipeline the
restriction and prolongation phases into single streaming passes. A key contribution is the extension of
the B-spline finite-element method to be compatible with the forward-difference gradient representation
commonly used with images. Our streaming solver is also efficient for in-memory images, due to its fast
convergence and excellent cache behavior. Remarkably, it can outperform spatially adaptive solvers that
exploit application-specific knowledge. We demonstrate seamless stitching and tone-mapping of gigapixel
images in about an hour on a notebook PC.
In later work, we
distributed
the solver computation over a cluster to handle terapixel images,
and generalized the approach to operate over
spherical imagery.
|
|
Multi-view stereo for community photo collections.
IEEE International Conference on Computer Vision (ICCV) 2007.
Detailed 3D models reconstructed from crawled Internet images.
We present a multi-view stereo algorithm that addresses the extreme changes in lighting, scale, clutter,
and other effects in large online community photo collections. Our idea is to intelligently choose images
to match, both at a per-view and per-pixel level. We show that such adaptive view selection enables robust
performance even with dramatic appearance variability. The stereo matching technique takes as input sparse
3D points reconstructed from structure-from-motion methods and iteratively grows surfaces from these
points. Optimizing for surface normals within a photoconsistency measure significantly improves the
matching results. While the focus of our approach is to estimate high-quality depth maps, we also show
examples of merging the resulting depth maps into compelling scene reconstructions. We demonstrate our
algorithm on standard multi-view stereo datasets and on casually acquired photo collections of famous
scenes gathered from the Internet.
One application may be to provide useful 3D impostors to improve view interpolation for image-based
rendering systems like Photosynth.
|
|
Design of tangent vector fields.
ACM Trans. Graphics (SIGGRAPH), 26(3), 2007.
Interactive control of direction fields for real-time surface texture synthesis.
Tangent vector fields are an essential ingredient in controlling surface appearance for applications
ranging from anisotropic shading to texture synthesis and non-photorealistic rendering. To achieve a
desired effect one is typically interested in smoothly varying fields that satisfy a sparse set of
user-provided constraints. Using tools from Discrete Exterior Calculus, we present a simple and efficient
algorithm for designing such fields over arbitrary triangle meshes. By representing the field as scalars
over mesh edges (i.e. discrete 1-forms), we obtain an intrinsic, coordinate-free formulation in which
field smoothness is enforced through discrete Laplace operators. Unlike previous methods, such a
formulation leads to a linear system whose sparsity permits efficient pre-factorization. Constraints are
incorporated through weighted least squares and can be updated rapidly enough to enable interactive design,
as we demonstrate in the context of anisotropic texture synthesis.
One generalization is N-symmetry fields as in Palacios and Zhang 2007 and Ray et al 2008. A common drawback in most linear approaches (including ours) is that the objective functional under-penalizes smoothness of the vector field in regions where the vectors have small magnitude. The work of Crane et al. 2010 overcomes this by optimizing over direction angles instead of vectors. |
|
Compressed random-access trees for spatially coherent data.
Symposium on Rendering 2007.
Efficient representation of coherent image data such as lightmaps and alpha mattes.
Adaptive multiresolution hierarchies are highly efficient at representing spatially coherent graphics data.
We introduce a framework for compressing such adaptive hierarchies using a compact randomly-accessible tree
structure. Prior schemes have explored compressed trees, but nearly all involve entropy coding of a
sequential traversal, thus preventing fine-grain random queries required by rendering algorithms. Instead,
we use fixed-rate encoding for both the tree topology and its data. Key elements include the replacement
of pointers by local offsets, a forested mipmap structure, vector quantization of inter-level residuals,
and efficient coding of partially defined data. Both the offsets and codebook indices are stored as byte
records for easy parsing by either CPU or GPU shaders. We show that continuous mipmapping over an adaptive
tree is more efficient using primal subdivision than traditional dual subdivision. Finally, we demonstrate
efficient compression of many data types including light maps, alpha mattes, distance fields, and HDR
images.
The compressed tree structure can also be used for lossless compression,
by replacing vector quantization with simple storage of the residual vectors.
|
|
Unconstrained isosurface extraction on arbitrary octrees.
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.
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.
(SGP 2021 Test of Time Award.) Reconstruction that considers all points at once for resilience to data noise.
We show that surface reconstruction from oriented points can be cast as a spatial Poisson problem. This
Poisson formulation considers all the points at once, without resorting to heuristic spatial partitioning
or blending, and is therefore highly resilient to data noise. Unlike radial basis function schemes, our
Poisson approach allows a hierarchy of locally supported basis functions, and therefore the solution
reduces to a well conditioned sparse linear system. We describe a spatially adaptive multiscale algorithm
whose time and space complexities are proportional to the size of the reconstructed model. Experimenting
with publicly available scan data, we demonstrate reconstruction of surfaces with greater detail than
previously achievable.
One perceived weakness of this work is that it requires oriented normals at the input points. However, most scanning technologies provide this information, either from line-of-sight knowledge or from adjacent nearby points in a range image. Experiments in [Kazhdan 2005] show that the approach is quite resilient to inaccuracies in the directions of the normals. In our subsequent SGP 2007 paper, we show that the Poisson problem can be solved out-of-core for large models by introducing a multilevel streaming representation of the sparse octree. Our 2013 paper extends the approach for improved geometric fidelity and using a faster hierarchical solver. The algorithm has been incorporated into MeshLab and VTK, and adapted over tetrahedral grids in CGAL. In 2011, Michael Kazhdan and Matthew Bolitho received the inaugural SGP Software Award for releasing the library code associated with this work. And ten years later at SGP 2021, the paper received the inaugural Test of Time Award. |
|
Perfect spatial hashing.
ACM Trans. Graphics (SIGGRAPH), 25(3), 2006.
Sparse spatial data packed into a dense table using a simple collision-free map.
We explore using hashing to pack sparse data into a compact table while retaining efficient random access.
Specifically, we design a perfect multidimensional hash function — one that is precomputed on static
data to have no hash collisions. Because our hash function makes a single reference to a small offset
table, queries always involve exactly two memory accesses and are thus ideally suited for parallel SIMD
evaluation on graphics hardware. Whereas prior hashing work strives for pseudorandom mappings, we instead
design the hash function to preserve spatial coherence and thereby improve runtime locality of reference.
We demonstrate numerous graphics applications including vector images, texture sprites, alpha channel
compression, 3D-parameterized textures, 3D painting, simulation, and collision detection.
The perfect hash data structure can be generalized to represent variable-sized data records as described in
Texel programs for random-access antialiased
vector graphics (MSR-TR-2007-95).
Alcantara et al. [2009] explore
parallel construction
of perfect spatial hashes.
|
|
Appearance-space texture synthesis.
ACM Trans. Graphics (SIGGRAPH), 25(3), 2006.
Improved synthesis quality and efficiency by pre-transforming the exemplar.
The traditional approach in texture synthesis is to compare color neighborhoods with those of an exemplar.
We show that quality is greatly improved if pointwise colors are replaced by appearance vectors that
incorporate nonlocal information such as feature and radiance-transfer data. We perform dimensionality
reduction on these vectors prior to synthesis, to create a new appearance-space exemplar. Unlike a texton
space, our appearance space is low-dimensional and Euclidean. Synthesis in this information-rich space
lets us reduce runtime neighborhood vectors from 5x5 grids to just 4 locations. Building on this unifying
framework, we introduce novel techniques for coherent anisometric synthesis, surface texture synthesis
directly in an ordinary atlas, and texture advection. Remarkably, we achieve all these functionalities in
real-time, or 3 to 4 orders of magnitude faster than prior work.
The main contribution of this paper is sometimes misinterpreted:
it is not the use of PCA projection to accelerate texture neighborhood comparisons (which is
already done in [Hertzmann et al 2001; Liang et al 2001; Lefebvre and Hoppe 2005]);
rather it is the transformation of the exemplar texture itself (into a new appearance space) to let each
transformed pixel encode nonlocal information.
See Design of tangent vector fields for interactive painting of oriented texture over a surface. |
|
Parallel controllable texture synthesis.
ACM Trans. Graphics (SIGGRAPH), 24(3), 2005.
Parallel synthesis of infinite deterministic content, with intuitive user controls.
We present a texture synthesis scheme based on neighborhood matching, with contributions in two areas:
parallelism and control. Our scheme defines an infinite, deterministic, aperiodic texture, from which
windows can be computed in real-time on a GPU. We attain high-quality synthesis using a new analysis
structure called the Gaussian stack, together with a coordinate upsampling step and a subpass correction
approach. Texture variation is achieved by multiresolution jittering of exemplar coordinates. Combined
with the local support of parallel synthesis, the jitter enables intuitive user controls including
multiscale randomness, spatial modulation over both exemplar and output, feature drag-and-drop, and
periodicity constraints. We also introduce synthesis magnification, a fast method for amplifying coarse
synthesis results to higher resolution.
We enhance the quality, efficiency, and functionality of the technique in our subsequent
SIGGRAPH 2006 paper.
Correction using subpasses is reminiscent of k-color Gauss-Seidel updates.
A similar subpass strategy is also adapted in Li-Yi Wei's
Parallel Poisson disk sampling.
|
|
Fast exact and approximate geodesics on meshes.
ACM Trans. Graphics (SIGGRAPH), 24(3), 2005.
Efficient computation of shortest paths and distances on triangle meshes.
The computation of geodesic paths and distances on triangle meshes is a common operation in many computer
graphics applications. We present several practical algorithms for computing such geodesics from a source
point to one or all other points efficiently. First, we describe an implementation of the exact "single
source, all destination" algorithm presented by Mitchell, Mount, and Papadimitriou (MMP). We show that the
algorithm runs much faster in practice than suggested by worst case analysis. Next, we extend the
algorithm with a merging operation to obtain computationally efficient and accurate approximations with
bounded error. Finally, to compute the shortest path between two given points, we use a lower-bound
property of our approximate geodesic algorithm to efficiently prune the frontier of the MMP algorithm,
thereby obtaining an exact solution even more quickly.
This computation of geodesic distances is used to improve the texture atlas parameterizations produced by
the DirectX UVAtlas tool.
See Bommes and Kobbelt
2007 for an interesting extension to compute geodesics from more general (non-point) sources.
|
|
Terrain rendering using GPU-based geometry clipmaps.
GPU Gems 2, M. Pharr and R. Fernando, eds., Addison-Wesley, March 2005.
Real-time terrain rendering with all data processing on the GPU.
The geometry clipmap introduced in Losasso and Hoppe 2004 is a new level-of-detail structure for rendering
terrains. It caches terrain geometry in a set of nested regular grids, which are incrementally shifted as
the viewer moves. The grid structure provides a number of benefits over previous irregular-mesh
techniques: simplicity of data structures, smooth visual transitions, steady rendering rate, graceful
degradation, efficient compression, and runtime detail synthesis. In this chapter, we describe a GPU-based
implementation of geometry clipmaps, enabled by vertex textures. By processing terrain geometry as a set
of images, we can perform nearly all computations on the GPU itself, thereby reducing CPU load. The
technique is easy to implement, and allows interactive flight over a 20-billion-sample grid of the United
States stored in just 355 MB of memory, at around 90 frames per second.
Unified shader cores in the latest graphics cards (NVIDIA GeForce 8800 and AMD Radeon HD 2900) provide
fast texture sampling in vertex shaders, making this implementation of geometry clipmaps extremely
practical.
The PTC image compressor mentioned in the paper was the precursor to the JPEG XR standard, which is supported in the WIC interface of Windows. See also the original paper and the recent book 3D Engine Design for Virtual Globes [Cozzi and Ring 2011]. |
|
Geometry clipmaps: Terrain rendering using nested regular grids.
ACM Trans. Graphics (SIGGRAPH), 23(3), 2004.
New terrain data structure enabling real-time decompression and synthesis.
Rendering throughput has reached a level that enables a novel approach to level-of-detail (LOD) control in
terrain rendering. We introduce the geometry clipmap, which caches the terrain in a set of nested regular
grids centered about the viewer. The grids are stored as vertex buffers in fast video memory, and are
incrementally refilled as the viewpoint moves. This simple framework provides visual continuity, uniform
frame rate, complexity throttling, and graceful degradation. Moreover it allows two new exciting real-time
functionalities: decompression and synthesis. Our main dataset is a 40GB height map of the United States.
A compressed image pyramid reduces the size by a remarkable factor of 100, so that it fits entirely in
memory. This compressed data also contributes normal maps for shading. As the viewer approaches the
surface, we synthesize grid levels finer than the stored terrain using fractal noise displacement.
Decompression, synthesis, and normal-map computations are incremental, thereby allowing interactive flight
at 60 frames/sec.
In our more recent GPU Gems 2 chapter,
we store the terrain as a set of vertex textures, thereby transferring nearly all computation to the GPU.
(See the demo available there.)
The PTC image compressor mentioned in the paper was the precursor to the JPEG XR standard, which is supported in the WIC interface of Windows. |
|
Digital photography with flash and no-flash image pairs.
ACM Trans. Graphics (SIGGRAPH), 23(3), 2004.
Combining detail of a flash image with ambient lighting of a non-flash image.
Digital photography has made it possible to quickly and easily take a pair of images of low-light
environments: one with flash to capture detail and one without flash to capture ambient illumination. We
present a variety of applications that analyze and combine the strengths of such flash/no-flash image
pairs. Our applications include denoising and detail transfer (to merge the ambient qualities of the
no-flash image with the high-frequency flash detail), white-balancing (to change the color tone of the
ambient image), continuous flash (to interactively adjust flash intensity), and red-eye removal (to repair
artifacts in the flash image). We demonstrate how these applications can synthesize new images that are of
higher quality than either of the originals.
Equation (9) in the paper has a typo; it should be “Cp = Ap / Δp”. I really like the image deblurring work of Yuan et al 2007 which uses a blurred/noisy image pair. See also my earlier work on Continuous Flash (demo). |
|
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.
Many high-resolution surfaces are created through isosurface extraction from volumetric representations,
obtained by 3D photography, CT, or MRI. Noise inherent in the acquisition process can lead to geometrical
and topological errors. Reducing geometrical errors during reconstruction is well studied. However,
isosurfaces often contain many topological errors in the form of tiny handles. These nearly
invisible artifacts hinder subsequent operations like mesh simplification, remeshing, and parametrization.
In this article we present a practical method for removing handles in an isosurface. Our algorithm makes
an axis-aligned sweep through the volume to locate handles, compute their sizes, and selectively remove
them. The algorithm is designed to facilitate out-of-core execution. It finds the handles by
incrementally constructing and analyzing a Reeb graph. The size of a handle is measured by a short
nonseparating cycle. Handles are removed robustly by modifying the volume rather than attempting "mesh
surgery". Finally, the volumetric modifications are spatially localized to preserve geometrical detail.
We demonstrate topology simplification on several complex models, and show its benefits for subsequent
surface processing.
This topologically repaired Buddha model has been used in a number of subsequent papers. Topological analysis of arbitrary meshes using Morse functions is also explored in Ni et al 2004 and Pascucci et al 2007. This paper was previously available as the technical report MSR-TR-2002-28. |
|
Signal-specialized parameterization for piecewise linear reconstruction.
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 is interesting that we obtain compression rates that are more aggressive than in traditional image
compression. This reflects the fact that the geometry of individual shapes is rather smooth, and in some
sense contains less information than typical images.
|
|
Smooth geometry images.
Symposium on Geometry Processing 2003, 138-145.
Subdivision and displacement of genus-zero mesh realized as GPU image processing.
Previous parametric representations of smooth genus-zero surfaces require a collection of abutting patches
(e.g. splines, NURBS, recursively subdivided polygons). We introduce a simple construction for these
surfaces using a single uniform bi-cubic B-spline. Due to its tensor-product structure, the spline control
points are conveniently stored as a geometry image with simple boundary symmetries. The bicubic surface is
evaluated using subdivision, and the regular structure of the geometry image makes this computation ideally
suited for graphics hardware. Specifically, we let the fragment shader pipeline perform subdivision by
applying a sequence of masks (splitting, averaging, limit, and tangent) uniformly to the geometry image.
We then extend this scheme to provide smooth level-of-detail transitions from a subsampled base octahedron
all the way to a finely subdivided, smooth model. Finally, we show how the framework easily supports
scalar displacement mapping.
After publication, we were able to merge the splitting and averaging steps into a single rasterization
pass.
The new feature of vertex textures in DirectX9 provide another technique for cycling rasterization output
back into the vertex stream.
Being able to process geometry as images within the highly parallel GPU rasterizer is exciting.
|
|
Spherical parametrization and remeshing.
ACM Trans. Graphics (SIGGRAPH), 22(3), 2003.
Robust mapping of a surface onto a sphere, allowing 2D-grid resampling.
The traditional approach for parametrizing a surface involves cutting it into charts and mapping these
piecewise onto a planar domain. We introduce a robust technique for directly parametrizing a genus-zero
surface onto a spherical domain. A key ingredient for making such a parametrization practical is the
minimization of a stretch-based measure, to reduce scale-distortion and thereby prevent undersampling. Our
second contribution is a scheme for sampling the spherical domain using uniformly subdivided polyhedral
domains, namely the tetrahedron, octahedron, and cube. We show that these particular semi-regular
samplings can be conveniently represented as completely regular 2D grids, i.e. geometry images. Moreover,
these images have simple boundary extension rules that aid many processing operations. Applications
include geometry remeshing, level-of-detail, morphing, compression, and smooth surface subdivision.
The execution times listed in the paper were reduced by a factor of 5
after further code optimization (see Talk slides).
Our approach avoids a fundamental limitation of the traditional conformal parametrization, which is that the solution may simply run out of numerical precision due to the severe scale distortion. Inter-surface mapping allows direct optimization of the map over the octahedron, rather than through the sphere intermediary, resulting in improved parametrization efficiency and reconstruction accuracy. Polycube maps are an interesting generalization of our cube parametrization. Our flat-octahedron parametrization can be seen as using a Euclidean domain with 4 cone singularities, each of 180 degrees. |
|
Multi-chart geometry images.
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.
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.
ACM Trans. Graphics (SIGGRAPH), 21(3), 2002.
Connectivity-free resampling of an arbitrary shape into a regular 2D grid.
Surface geometry is often modeled with irregular triangle meshes. The process of remeshing refers to
approximating such geometry using a mesh with (semi)-regular connectivity, which has advantages for many
graphics applications. However, current techniques for remeshing arbitrary surfaces create only
semi-regular meshes. The original mesh is typically decomposed into a set of disk-like charts,
onto which the geometry is parametrized and sampled. In this paper, we propose to remesh an arbitrary
surface onto a completely regular structure we call a geometry image. It captures
geometry as a simple 2D array of quantized points. Surface signals like normals and colors are stored in
similar 2D arrays using the same implicit surface parametrization — texture coordinates are absent.
To create a geometry image, we cut an arbitrary mesh along a network of edge paths, and parametrize the
resulting single chart onto a square. Geometry images can be encoded using traditional image compression
algorithms, such as wavelet-based coders.
Geometry images have the potential to simplify the rendering pipeline,
since they eliminate the "gather" operations associated with vertex
indices and texture coordinates.
Although the paper emphasizes the exciting possibilities of resampling
mesh geometry into an image,
the same parametrization scheme can also be used to construct single-chart
parametrizations over irregular meshes, for seam-free texture mapping.
The irregular "cruft" present in several of the parametrizations is
addressed by the inverse-stretch regularization term described in the
2003 Spherical Parametrization paper.
|
|
Signal-specialized parametrization.
Eurographics Workshop on Rendering 2002, 87-100.
Optimization of texture coordinates for accurate representation of given content.
To reduce memory requirements for texture mapping a model, we build a surface parametrization specialized
to its signal (such as color or normal). Intuitively, we want to allocate more texture samples in regions
with greater signal detail. Our approach is to minimize signal approximation error — the difference
between the original surface signal and its reconstruction from the sampled texture. Specifically, our
signal-stretch parametrization metric is derived from a Taylor expansion of signal error. For fast
evaluation, this metric is pre-integrated over the surface as a metric tensor. We minimize this nonlinear
metric using a novel coarse-to-fine hierarchical solver, further accelerated with a fine-to-coarse
propagation of the integrated metric tensor. Use of metric tensors permits anisotropic squashing of the
parametrization along directions of low signal gradient. Texture area can often be reduced by a factor of
4 for a desired signal accuracy compared to non-specialized parametrizations.
See also our follow-up work at SGP 2004
where we further improve the parameterization to account for the local linear reconstruction provided by
hardware texture sampling.
|
|
Texture mapping progressive meshes.
ACM SIGGRAPH 2001 Proceedings, 409-416.
Texture atlas compatible across levels of detail, and parameterization stretch.
Given an arbitrary mesh, we present a method to construct a progressive mesh (PM) such that all meshes in
the PM sequence share a common texture parametrization. Our method considers two important goals
simultaneously. It minimizes texture stretch (small texture distances mapped onto large surface distances)
to balance sampling rates over all locations and directions on the surface. It also minimizes texture
deviation ("slippage" error based on parametric correspondence) to obtain accurate textured mesh
approximations. The method begins by partitioning the mesh into charts using planarity and compactness
heuristics. It creates a stretch-minimizing parametrization within each chart, and resizes the charts
based on the resulting stretch. Next, it simplifies the mesh while respecting the chart boundaries. The
parametrization is re-optimized to reduce both stretch and deviation over the whole PM sequence. Finally,
the charts are packed into a texture atlas. We demonstrate using such atlases to sample color and normal
maps over several models.
The geometric-stretch parametrization introduced in this paper is a nice principled contribution,
and should have been given stronger emphasis.
Signal-specialized parametrization (2002)
presents a hierarchical algorithm to efficiently compute this parametrization on large patches, and shows
that the chart boundary need not be fixed but can be optimized as well.
The irregular "cruft" present in several of the parametrizations is addressed by the inverse-stretch
regularization term described in the 2003
Spherical Parametrization paper.
Many of our ideas (signal-specialization, integrated metric tensor, atlas packing, etc.) have been adapted in the UVAtlas technology of the Microsoft Direct3D SDK. |
|
Fine tone control in hardware hatching.
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.
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 (I3D) 2001, 227-232.
Rendering of shells and fins over general meshes.
We introduce a method for real-time rendering of fur on surfaces of arbitrary topology. As a pre-process,
we simulate virtual hair with a particle system, and sample it into a volume texture. Next, we
parameterize the texture over a surface of arbitrary topology using "lapped textures" — an approach
for applying a sample texture to a surface by repeatedly pasting patches of the texture until the surface
is covered. The use of lapped textures permits specifying a global direction field for the fur over the
surface. At runtime, the patches of volume textures are rendered as a series of concentric shells of
semi-transparent medium. To improve the visual quality of the fur near silhouettes, we place "fins" normal
to the surface and render these using conventional 2D texture maps sampled from the volume texture in the
direction of hair growth. The method generates convincing imagery of fur at interactive rates for models
of moderate complexity. Furthermore, the scheme allows real-time modification of viewing and lighting
conditions, as well as local control over hair color, length, and direction.
Don't you just feel like "shaking the bunny" to see its hair move?
It can be done by locally shearing the shells according to a
simple physical simulation (see here).
The "fin" rendering introduced in this paper has become popular in games,
and has become more efficient with geometry shaders in DirectX 10.
|
|
Lapped textures.
ACM SIGGRAPH 2000 Proceedings, 465-470.
Texture synthesis over arbitrary surfaces.
We present a method for creating texture over an arbitrary surface mesh using an example 2D texture. The
approach is to identify interesting regions (texture patches) in the 2D example, and to repeatedly
paste them onto the surface until it is completely covered. We call such a collection of overlapping
patches a lapped texture. It is rendered using compositing operations, either into a traditional
global texture map during a preprocess, or directly with the surface at runtime. The runtime compositing
approach avoids resampling artifacts and drastically reduces texture memory requirements.
Through a simple interface, the user specifies a tangential vector field over the surface, providing local control over the texture scale, and for anisotropic textures, the orientation. To paste a texture patch onto the surface, a surface patch is grown and parametrized over texture space. Specifically, we optimize the parametrization of each surface patch such that the tangential vector field aligns everywhere with the standard frame of the texture patch. We show that this optimization is solved efficiently as a sparse linear system.
As seen in the accompanying video, 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.
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 (I3D) 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.
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.
Microsoft Research Technical Report MSR-TR-2000-64, June 2000.
Fast solution of quadric metric exploiting its sub-block structure.
In an earlier paper we introduced a new quadric metric for simplifying triangle meshes using the edge
collapse operation. The quadric measures both the geometric accuracy of the simplified mesh surface and
the fidelity of appearance fields defined on the surface (such as normals or colors). The minimization of
this quadric metric involves solving a linear system of size (3+m)×(3+m),
where m is the number of distinct appearance attributes. The system has
only O(m) nonzero entries, so it can be solved
in O(m2) time using traditional sparse solvers such as the method of
conjugate gradients. In this short addendum, we show that the special structure of the sparsity permits
the system to be solved in O(m) time.
Thanks also to John Platt for explaining Lagrange multipliers to me.
|
|
New quadric metric for simplifying meshes with appearance attributes.
IEEE Visualization 1999 Conference, 59-66.
Efficient simplification metric designed around correspondence in 3D space.
Complex triangle meshes arise naturally in many areas of computer graphics and visualization. Previous
work has shown that a quadric error metric allows fast and accurate geometric simplification of meshes.
This quadric approach was recently generalized to handle meshes with appearance attributes. In this paper
we present an improved quadric error metric for simplifying meshes with attributes. The new metric, based
on geometric correspondence in 3D, requires less storage, evaluates more quickly, and results in more
accurate simplified meshes.
Meshes often have attribute discontinuities, such as surface creases and material boundaries, which require multiple attribute vectors per vertex. We show that a wedge-based mesh data structure captures such discontinuities efficiently and permits simultaneous optimization of these multiple attribute vectors. In addition to the new quadric metric, we experiment with two techniques proposed in geometric simplification, memoryless simplification and volume preservation, and show that both of these are beneficial within the quadric framework. The new scheme is demonstrated on a variety of meshes with colors and normals.
A subsequent technical report shows that the
minimization of the new quadric can be done efficiently in linear time. The present trend is to replace
per-vertex attributes by texture atlases.
|
|
Optimization of mesh locality for transparent vertex caching.
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 GPUs.
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 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.
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.
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.
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.
Visually smooth adaptation of mesh refinement using cascaded temporal geomorphs.
The key to real-time rendering of large-scale surfaces is to locally adapt surface geometric complexity to
changing view parameters. Several schemes have been developed to address this problem of view-dependent
level-of-detail control. Among these, the view-dependent progressive mesh (VDPM) framework
represents an arbitrary triangle mesh as a hierarchy of geometrically optimized refinement transformations,
from which accurate approximating meshes can be efficiently retrieved. In this paper we extend the general
VDPM framework to provide temporal coherence through the runtime creation of geomorphs. These
geomorphs eliminate "popping" artifacts by smoothly interpolating geometry. Their implementation requires
new output-sensitive data structures, which have the added benefit of reducing memory use.
We specialize the VDPM framework to the important case of terrain rendering. To handle huge terrain grids, we introduce a block-based simplification scheme that constructs a progressive mesh as a hierarchy of block refinements. We demonstrate the need for an accurate approximation metric during simplification. Our contributions are highlighted in a real-time flyover of a large, rugged terrain. Notably, the use of geomorphs results in visually smooth rendering even at 72 frames/sec on a graphics workstation.
The runtime geomorphs make this one of my favorite demos.
The irregular meshes reduce the number of triangles for a given level of approximation accuracy, and allow
large regions of the terrain to be pre-simplified.
This approach has been generalized to general (non-terrain) meshes, in
Chris Prince's Masters Thesis
Progressive
Meshes for Large Models of Arbitrary Topology.
In my opinion, for terrains the future lies in regularly sampled representations such as
geometry clipmaps.
|
|
View-dependent refinement of progressive meshes.
ACM SIGGRAPH 1997 Proceedings, 189-198.
Lossless multiresolution structure for incremental local refinement/coarsening.
Level-of-detail (LOD) representations are an important tool for real-time rendering of complex geometric
environments. The previously introduced progressive mesh representation defines for an arbitrary
triangle mesh a sequence of approximating meshes optimized for view-independent LOD. In this paper, we
introduce a framework for selectively refining an arbitrary progressive mesh according to changing view
parameters. We define efficient refinement criteria based on the view frustum, surface orientation, and
screen-space geometric error, and develop a real-time algorithm for incrementally refining and coarsening
the mesh according to these criteria. The algorithm exploits view coherence, supports frame rate
regulation, and is found to require less than 15% of total frame time on a graphics workstation. Moreover,
for continuous motions this work can be amortized over consecutive frames. In addition, smooth visual
transitions (geomorphs) can be constructed between any two selectively refined meshes.
A number of previous schemes create view-dependent LOD meshes for height fields (e.g. terrains) and parametric surfaces (e.g. NURBS). Our framework also performs well for these special cases. Notably, the absence of a rigid subdivision structure allows more accurate approximations than with existing schemes. We include results for these cases as well as for general meshes.
Further enhancements on this approach are presented in my
Visualization 1998 paper.
|
|
Progressive simplicial complexes.
ACM SIGGRAPH 1997 Proceedings, 217-224.
Progressive encoding of both topology and geometry.
In this paper, we introduce the progressive simplicial complex (PSC) representation, a new format for
storing and transmitting triangulated geometric models. Like the earlier progressive mesh (PM)
representation, it captures a given model as a coarse base model together with a sequence of refinement
transformations that progressively recover detail. The PSC representation makes use of a more general
refinement transformation, allowing the given model to be an arbitrary triangulation (e.g. any dimension,
non-orientable, non-manifold, non-regular), and the base model to always consist of a single vertex.
Indeed, the sequence of refinement transformations encodes both the geometry and the topology of the model
in a unified multiresolution framework. The PSC representation retains the advantages of PMs. 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.
ACM SIGGRAPH 1996 Proceedings, 99-108.
(Seminal Graphics Papers Vol 2.) Efficient, lossless, continuous-resolution representation of surface triangulations.
Highly detailed geometric models are rapidly becoming commonplace in computer graphics. These models,
often represented as complex triangle meshes, challenge rendering performance, transmission bandwidth, and
storage capacities. This paper introduces the progressive mesh (PM) representation, a new scheme
for storing and transmitting arbitrary triangle meshes. This efficient, lossless, continuous-resolution
representation addresses several practical problems in graphics: smooth geomorphing of level-of-detail
approximations, progressive transmission, mesh compression, and selective refinement.
In addition, we present a new mesh simplification procedure for constructing a PM representation from an arbitrary mesh. The goal of this optimization procedure is to preserve not just the geometry of the original mesh, but more importantly its overall appearance as defined by its discrete and scalar appearance attributes such as material identifiers, color values, normals, and texture coordinates. We demonstrate construction of the PM representation and its applications using several practical models.
More recent papers describe faster simplification criteria, such as the
quadric error metric scheme of Garland and
Heckbert,
the memoryless scheme of Lindstrom and Turk,
and my improved quadric error metric in
Visualization 1999.
But, the first 4 pages are still excellent. The paper should have made it more obvious that a geomorph can
directly transition between any two PM meshes by simultaneously moving many vertices.
|
|
Automatic reconstruction of B-spline surfaces of arbitrary topological type.
ACM SIGGRAPH 1996 Proceedings, 325-334.
Fully automatic creation of B-spline patch network from 3D point cloud.
Creating freeform surfaces is a challenging task even with advanced geometric modeling systems. Laser
range scanners offer a promising alternative for model acquisition — the 3D scanning of existing
objects or clay maquettes. The problem of converting the dense point sets produced by laser scanners into
useful geometric models is referred to as surface reconstruction.
In this paper, we present a procedure for reconstructing a tensor product B-spline surface from a set of scanned 3D points. Unlike previous work which considers primarily the problem of fitting a single B-spline patch, our goal is to directly reconstruct a surface of arbitrary topological type. We must therefore define the surface as a network of B-spline patches. A key ingredient in our solution is a scheme for automatically constructing both a network of patches and a parametrization of the data points over these patches. In addition, we define the B-spline surface using a surface spline construction, and demonstrate that such an approach leads to an efficient procedure for fitting the surface while maintaining tangent plane continuity. We explore adaptive refinement of the patch network in order to satisfy user-specified error tolerances, and demonstrate our method on both synthetic and real data.
Reconstructing arbitrary B-spline surfaces is difficult, and this paper tackles the problem in a fully
automatic approach.
For some applications, it may be more practical to let the user manually specify the patch boundaries (see
the related paper by Krishnamurthy and
Levoy in the same proceedings).
Still, the surface spline construction is useful in this context for maintaining C1 continuity without
resort to constrained optimization.
Sorry, the code is not available.
Subdivision surfaces, which have gained popularity recently, make this reconstruction problem so much
easier... (see my SIGGRAPH 1994 paper).
|
|
Multiresolution analysis of arbitrary meshes.
ACM SIGGRAPH 1995 Proceedings, 173-182.
Semi-regular remeshing for wavelet-based representation of surfaces.
In computer graphics and geometric modeling, shapes are often represented by triangular meshes. With the
advent of laser scanning systems, meshes of extreme complexity are rapidly becoming commonplace. Such
meshes are notoriously expensive to store, transmit, render, and are awkward to edit. Multiresolution
analysis offers a simple, unified, and theoretically sound approach to dealing with these problems.
Lounsbery et al. have recently developed a technique for creating multiresolution representations for a
restricted class of meshes with subdivision connectivity. Unfortunately, meshes encountered in
practice typically do not meet this requirement. In this paper we present a method for overcoming the
subdivision connectivity restriction, meaning that completely arbitrary meshes can now be converted to
multiresolution form. The method is based on the approximation of an arbitrary initial mesh M
by a mesh Mj that has subdivision connectivity and is guaranteed to be
within a specified tolerance.
The key ingredient of our algorithm is the construction of a parametrization of M over a simple domain. We expect this parametrization to be of use in other contexts, such as texture mapping or the approximation of complex meshes by NURBS patches.
Novel technique for parametrizing an arbitrary triangle mesh over a simpler triangular domain of the same
topological type.
Subsequently, two enhancements to this paper were presented:
Vertex-based Delaunay triangulation
(to improve the mesh partition) and
Hierarchical computation of PL harmonic embeddings
(to speed up harmonic maps).
The approach of remeshing a model to have subdivision connectivity was made more practical by the MAPS scheme of Lee et al in SIGGRAPH 1998. The paper is often cited for introducing the harmonic map in the context of mesh parametrization. This harmonic/conformal map has been generalized to allow free boundaries, in LSCM and DCP, which are in fact equivalent, and also identical to harmonic maps for fixed boundary. |
|
Surface reconstruction from unorganized points (PhD Thesis).
Department of Computer Science and Engineering, University of Washington, June 1994.
Robust surface topology and optimized geometry from scanned 3D points.
This thesis describes a general method for automatic reconstruction of accurate, concise, piecewise smooth
surfaces from unorganized 3D points. Instances of surface reconstruction arise in numerous scientific and
engineering applications, including reverse-engineering — the automatic generation of CAD models from
physical objects.
Previous surface reconstruction methods have typically required additional knowledge, such as structure in the data, known surface genus, or orientation information. In contrast, the method outlined in this thesis requires only the 3D coordinates of the data points. From the data, the method is able to automatically infer the topological type of the surface, its geometry, and the presence and location of features such as boundaries, creases, and corners. The reconstruction method has three major phases: 1) initial surface estimation, 2) mesh optimization, and 3) piecewise smooth surface optimization. A key ingredient in phase 3, and another principal contribution of this thesis, is the introduction of a new class of piecewise smooth representations based on subdivision. The effectiveness of the three-phase reconstruction method is demonstrated on a number of examples using both simulated and real data. Phases 2 and 3 of the surface reconstruction method can also be used to approximate existing surface models. By casting surface approximation as a global optimization problem with an energy function that directly measures deviation of the approximation from the original surface, models are obtained that exhibit excellent accuracy to conciseness trade-offs. Examples of piecewise linear and piecewise smooth approximations are generated for various surfaces, including meshes, NURBS surfaces, CSG models, and implicit surfaces. Really, there was more work here than the stapling of three papers :-) This surface reconstruction problem has continued to be an active area; see the recent papers by Nina Amenta and the commercial product by Geomagic. This reconstructed mannequin head is my small contribution to the pool of geometric models commonly used in graphics. See also my 2006 work Poisson surface reconstruction, which assumes oriented points but achieves greater robustness using a global (yet efficient) solution. |
|
Piecewise smooth surface reconstruction.
ACM SIGGRAPH 1994 Proceedings, 295-302.
Subdivision surfaces with sharp features, and their automatic creation by data fitting.
We present a general method for automatic reconstruction of accurate, concise, piecewise smooth surface
models from scattered range data. The method can be used in a variety of applications such as reverse
engineering — the automatic generation of CAD models from physical objects. Novel aspects of the
method are its ability to model surfaces of arbitrary topological type and to recover sharp features such
as creases and corners. The method has proven to be effective, as demonstrated by a number of examples
using both simulated and real data.
A key ingredient in the method, and a principal contribution of this paper, is the introduction of a new class of piecewise smooth surface representations based on subdivision. These surfaces have a number of properties that make them ideal for use in surface reconstruction: they are simple to implement, they can model sharp features concisely, and they can be fit to scattered range data using an unconstrained optimization procedure.
Through general optimization, this method is able to infer sharp features in the underlying geometry by
simply fitting the data points.
With the growing interest in subdivision surfaces, this surface fitting technique may prove useful.
The paper is often cited for its introduction of sharp features in subdivision surface schemes.
These features were extended in the work of
Biermann et al.
The SIGGRAPH 1998 paper
by DeRose et al. presents extensions for "fractionally smooth" surface features.
|
|
Mesh optimization.
ACM SIGGRAPH 1993 Proceedings, 19-26.
Traversing the space of triangle meshes to optimize model fidelity and conciseness.
We present a method for solving the following problem: Given a set of data points scattered in three
dimensions and an initial triangular mesh M0, produce a mesh M, of the same
topological type as M0, that fits the data well and has a small number of vertices.
Our approach is to minimize an energy function that explicitly models the competing desires of conciseness
of representation and fidelity to the data. We show that mesh optimization can be effectively used in at
least two applications: surface reconstruction from unorganized points, and mesh simplification (the
reduction of the number of vertices in an initially dense mesh of triangles).
The technique demonstrates that general optimization can achieve surprisingly good results.
This particular optimization searches over a broad space of both discrete and continuous variables to find a
concise mesh accurately fitting a set of data points.
A similar approach was used by Lindstrom and Turk in their
Image-driven mesh optimization work.
Mesh optimization is quite powerful for feature-sensitive remeshing, as it automatically migrates vertices
onto sharp features
(e.g. as used in multi-chart geometry images).
For the application of mesh simplification,
progressive meshes offer a more elegant solution.
|
|
Surface reconstruction from unorganized points.
ACM SIGGRAPH 1992 Proceedings, 71-78.
(Seminal Graphics Papers Vol 2.) Signed-distance field estimated from a set of unoriented noisy points.
We describe and demonstrate an algorithm that takes as input an unorganized set of points
{x1, ... , xn} in R3 on or
near an unknown manifold M, and produces as output a simplicial surface that
approximates M. Neither the topology, the presence of boundaries, nor the geometry
of M are assumed to be known in advance — all are inferred automatically from the data.
This problem naturally arises in a variety of practical situations such as range scanning an object from
multiple view points, recovery of biological shapes from two-dimensional slices, and interactive surface
sketching.
This paper addresses the difficult case where the data points have no inherent structure. This was useful for data we had obtained from the company Technical Arts, which manufactured a laser-sheet scanner mounted on a coordinate measuring machine. For traditional range images which have more structure in the data, a more specialized technique is the volumetric approach of Curless and Levoy (SIGGRAPH 1996), which also uses a signed-distance implicit function. Our "Riemannian Graph" construction is similar to that used to estimate manifold geodesics in Isomap construction. See also my 2006 work Poisson surface reconstruction, which assumes oriented points but achieves greater robustness using a global (yet efficient) solution. |
See content copyrights.