Graphics (TOG)


Search Issue
enter search term and/or author name



Section: Sampling and ray tracing

Ray tracing animated scenes using coherent grid traversal
Ingo Wald, Thiago Ize, Andrew Kensler, Aaron Knoll, Steven G. Parker
Pages: 485-493
DOI: 10.1145/1141911.1141913
We present a new approach to interactive ray tracing of moderate-sized animated scenes based on traversing frustum-bounded packets of coherent rays through uniform grids. By incrementally computing the overlap of the frustum with a slice of grid...

Guided visibility sampling
Peter Wonka, Michael Wimmer, Kaichi Zhou, Stefan Maierhofer, Gerd Hesina, Alexander Reshetov
Pages: 494-502
DOI: 10.1145/1141911.1141914
This paper addresses the problem of computing the triangles visible from a region in space. The proposed aggressive visibility solution is based on stochastic ray shooting and can take any triangular model as input. We do not rely on connectivity...

A spatial data structure for fast Poisson-disk sample generation
Daniel Dunbar, Greg Humphreys
Pages: 503-508
DOI: 10.1145/1141911.1141915
Sampling distributions with blue noise characteristics are widely used in computer graphics. Although Poisson-disk distributions are known to have excellent blue noise characteristics, they are generally regarded as too computationally expensive to...

Recursive Wang tiles for real-time blue noise
Johannes Kopf, Daniel Cohen-Or, Oliver Deussen, Dani Lischinski
Pages: 509-518
DOI: 10.1145/1141911.1141916
Well distributed point sets play an important role in a variety of computer graphics contexts, such as anti-aliasing, global illumination, halftoning, non-photorealistic rendering, point-based modeling and rendering, and geometry processing. In this...

Section: Sampling and ray tracing

Fast median and bilateral filtering
Ben Weiss
Pages: 519-526
DOI: 10.1145/1141911.1141918
Median filtering is a cornerstone of modern image processing and is used extensively in smoothing and de-noising applications. The fastest commercial implementations (e.g. in Adobe® Photoshop® CS2) exhibit O(r) runtime in the radius of...

Hybrid images
Aude Oliva, Antonio Torralba, Philippe G. Schyns
Pages: 527-532
DOI: 10.1145/1141911.1141919
We present hybrid images, a technique that produces static images with two interpretations, which change as a function of viewing distance. Hybrid images are based on the multiscale processing of images by the human visual system and are...

Image deformation using moving least squares
Scott Schaefer, Travis McPhail, Joe Warren
Pages: 533-540
DOI: 10.1145/1141911.1141920
We provide an image deformation method based on Moving Least Squares using various classes of linear functions including affine, similarity and rigid transformations. These deformations are realistic and give the user the impression of manipulating...

Appearance-space texture synthesis
Sylvain Lefebvre, Hugues Hoppe
Pages: 541-548
DOI: 10.1145/1141911.1141921
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...

Section: Sampling and ray tracing

A planar-reflective symmetry transform for 3D shapes
Joshua Podolak, Philip Shilane, Aleksey Golovinskiy, Szymon Rusinkiewicz, Thomas Funkhouser
Pages: 549-559
DOI: 10.1145/1141911.1141923
Symmetry is an important cue for many applications, including object alignment, recognition, and segmentation. In this paper, we describe a planar reflective symmetry transform (PRST) that captures a continuous measure of the reflectional symmetry of...

Partial and approximate symmetry detection for 3D geometry
Niloy J. Mitra, Leonidas J. Guibas, Mark Pauly
Pages: 560-568
DOI: 10.1145/1141911.1141924
"Symmetry is a complexity-reducing concept [...]; seek it every-where." - Alan J. PerlisMany natural and man-made objects exhibit significant symmetries or contain repeated substructures. This paper presents a new algorithm that processes geometric...

Reassembling fractured objects by geometric matching
Qi-Xing Huang, Simon Flöry, Natasha Gelfand, Michael Hofer, Helmut Pottmann
Pages: 569-578
DOI: 10.1145/1141911.1141925
We present a system for automatic reassembly of broken 3D solids. Given as input 3D digital models of the broken fragments, we analyze the geometry of the fracture surfaces to find a globally consistent reconstruction of the original object. Our...

Perfect spatial hashing
Sylvain Lefebvre, Hugues Hoppe
Pages: 579-588
DOI: 10.1145/1141911.1141926
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...

Section: Sampling and ray tracing

SmoothSketch: 3D free-form shapes from complex sketches
Olga A. Karpenko, John F. Hughes
Pages: 589-598
DOI: 10.1145/1141911.1141928
We introduce SmoothSketch---a system for inferring plausible 3D free-form shapes from visible-contour sketches. In our system, a user's sketch need not be a simple closed curve as in Igarashi's Teddy [1999], but may have cusps and T-junctions, i.e.,...

Image-based plant modeling
Long Quan, Ping Tan, Gang Zeng, Lu Yuan, Jingdong Wang, Sing Bing Kang
Pages: 599-604
DOI: 10.1145/1141911.1141929
In this paper, we propose a semi-automatic technique for modeling plants directly from images. Our image-based approach has the distinct advantage that the resulting model inherits the realistic shape and complexity of a real plant. We designed our...

Interactive decal compositing with discrete exponential maps
Ryan Schmidt, Cindy Grimm, Brian Wyvill
Pages: 605-613
DOI: 10.1145/1141911.1141930
A method is described for texturing surfaces using decals, images placed on the surface using local parameterizations. Decal parameterizations are generated with a novel O(N log N) discrete approximation to the exponential...

Procedural modeling of buildings
Pascal Müller, Peter Wonka, Simon Haegler, Andreas Ulmer, Luc Van Gool
Pages: 614-623
DOI: 10.1145/1141911.1141931
CGA shape, a novel shape grammar for the procedural modeling of CG architecture, produces building shells with high visual quality and geometric detail. It produces extensive architectural models for computer games and movies, at low cost....

Section: Sampling and ray tracing

Color harmonization
Daniel Cohen-Or, Olga Sorkine, Ran Gal, Tommer Leyvand, Ying-Qing Xu
Pages: 624-630
DOI: 10.1145/1141911.1141933
Harmonic colors are sets of colors that are aesthetically pleasing in terms of human visual perception. In this paper, we present a method that enhances the harmony among the colors of a given photograph or of a general image, while remaining...

Drag-and-drop pasting
Jiaya Jia, Jian Sun, Chi-Keung Tang, Heung-Yeung Shum
Pages: 631-637
DOI: 10.1145/1141911.1141934
In this paper, we present a user-friendly system for seamless image composition, which we call drag-and-drop pasting. We observe that for Poisson image editing [Perez et al. 2003] to work well, the user must carefully draw a boundary on the source...

Two-scale tone management for photographic look
Soonmin Bae, Sylvain Paris, Frédo Durand
Pages: 637-645
DOI: 10.1145/1141911.1141935
We introduce a new approach to tone management for photographs. Whereas traditional tone-mapping operators target a neutral and faithful rendition of the input image, we explore pictorial looks by controlling visual qualities such as the tonal...

Interactive local adjustment of tonal values
Dani Lischinski, Zeev Farbman, Matt Uyttendaele, Richard Szeliski
Pages: 646-653
DOI: 10.1145/1141911.1141936
This paper presents a new interactive tool for making local adjustments of tonal values and other visual parameters in an image. Rather than carefully selecting regions or hand-painting layer masks, the user quickly indicates regions of interest by...

Image-based material editing
Erum Arif Khan, Erik Reinhard, Roland W. Fleming, Heinrich H. Bülthoff
Pages: 654-663
DOI: 10.1145/1141911.1141937
Photo editing software allows digital images to be blurred, warped or re-colored at the touch of a button. However, it is not currently possible to change the material appearance of an object except by painstakingly painting over the appropriate...

Section: Sampling and ray tracing

Real-time GPU rendering of piecewise algebraic surfaces
Charles Loop, Jim Blinn
Pages: 664-670
DOI: 10.1145/1141911.1141939
We consider the problem of real-time GPU rendering of algebraic surfaces defined by Bézier tetrahedra. These surfaces are rendered directly in terms of their polynomial representations, as opposed to a collection of approximating triangles,...

Point-sampled cell complexes
Anders Adamson, Marc Alexa
Pages: 671-680
DOI: 10.1145/1141911.1141940
A piecewise smooth surface, possibly with boundaries, sharp edges, corners, or other features is defined by a set of samples. The basic idea is to model surface patches, curve segments and points explicitly, and then to glue them together based on...

Geometric modeling with conical meshes and developable surfaces
Yang Liu, Helmut Pottmann, Johannes Wallner, Yong-Liang Yang, Wenping Wang
Pages: 681-689
DOI: 10.1145/1141911.1141941
In architectural freeform design, the relation between shape and fabrication poses new challenges and requires more sophistication from the underlying geometry. The new concept of conical meshes satisfies central requirements for this application:...

Mesh quilting for geometric texture synthesis
Kun Zhou, Xin Huang, Xi Wang, Yiying Tong, Mathieu Desbrun, Baining Guo, Heung-Yeung Shum
Pages: 690-697
DOI: 10.1145/1141911.1141942
We introduce mesh quilting, a geometric texture synthesis algorithm in which a 3D texture sample given in the form of a triangle mesh is seamlessly applied inside a thin shell around an arbitrary surface through local stitching and...

Section: Sampling and ray tracing

High dynamic range texture compression for graphics hardware
Jacob Munkberg, Petrik Clarberg, Jon Hasselgren, Tomas Akenine-Möller
Pages: 698-706
DOI: 10.1145/1141911.1141944
In this paper, we break new ground by presenting algorithms for fixed-rate compression of high dynamic range textures at low bit rates. First, the S3TC low dynamic range texture compression scheme is extended in order to enable compression of HDR...

High dynamic range texture compression
Kimmo Roimela, Tomi Aarnio, Joonas Itäranta
Pages: 707-712
DOI: 10.1145/1141911.1141945
We present a novel compression scheme for high dynamic range textures, targeted for hardware implementation. Our method encodes images at a constant 8 bits per pixel, for a compression ratio of 6:1. We demonstrate that our method achieves good visual...

Backward compatible high dynamic range MPEG video compression
Rafał Mantiuk, Alexander Efremov, Karol Myszkowski, Hans-Peter Seidel
Pages: 713-723
DOI: 10.1145/1141911.1141946
To embrace the imminent transition from traditional low-contrast video (LDR) content to superior high dynamic range (HDR) content, we propose a novel backward compatible HDR video compression (HDR MPEG) method. We introduce a compact reconstruction...

The Direct3D 10 system
David Blythe
Pages: 724-734
DOI: 10.1145/1141911.1141947
We present a system architecture for the 4th generation of PC-class programmable graphics processing units (GPUs). The new pipeline features significant additions and changes to the prior generation pipeline including a new programmable...

Section: Sampling and ray tracing

Inverse shade trees for non-parametric material representation and editing
Jason Lawrence, Aner Ben-Artzi, Christopher DeCoro, Wojciech Matusik, Hanspeter Pfister, Ravi Ramamoorthi, Szymon Rusinkiewicz
Pages: 735-745
DOI: 10.1145/1141911.1141949
Recent progress in the measurement of surface reflectance has created a demand for non-parametric appearance representations that are accurate, compact, and easy to use for rendering. Another crucial goal, which has so far received little attention,...

A compact factored representation of heterogeneous subsurface scattering
Pieter Peers, Karl vom Berge, Wojciech Matusik, Ravi Ramamoorthi, Jason Lawrence, Szymon Rusinkiewicz, Philip Dutré
Pages: 746-753
DOI: 10.1145/1141911.1141950
Many translucent materials exhibit heterogeneous subsurface scattering, which arises from complex internal structures. The acquisition and representation of these scattering functions is a complex problem that has been only partially addressed in...

Appearance manifolds for modeling time-variant appearance of materials
Jiaping Wang, Xin Tong, Stephen Lin, Minghao Pan, Chao Wang, Hujun Bao, Baining Guo, Heung-Yeung Shum
Pages: 754-761
DOI: 10.1145/1141911.1141951
We present a visual simulation technique called appearance manifolds for modeling the time-variant surface appearance of a material from data captured at a single instant in time. In modeling time-variant appearance, our method takes advantage...

Time-varying surface appearance: acquisition, modeling and rendering
Jinwei Gu, Chien-I Tu, Ravi Ramamoorthi, Peter Belhumeur, Wojciech Matusik, Shree Nayar
Pages: 762-771
DOI: 10.1145/1141911.1141952
For computer graphics rendering, we generally assume that the appearance of surfaces remains static over time. Yet, there are a number of natural processes that cause surface appearance to vary dramatically, such as burning of wood, wetting and...

Section: Sampling and ray tracing

Flash matting
Jian Sun, Yin Li, Sing Bing Kang, Heung-Yeung Shum
Pages: 772-778
DOI: 10.1145/1141911.1141954
In this paper, we propose a novel approach to extract mattes using a pair of flash/no-flash images. Our approach, which we call flash matting, was inspired by the simple observation that the most noticeable difference between the flash and...

Natural video matting using camera arrays
Neel Joshi, Wojciech Matusik, Shai Avidan
Pages: 779-786
DOI: 10.1145/1141911.1141955
We present an algorithm and a system for high-quality natural video matting using a camera array. The system uses high frequencies present in natural scenes to compute mattes by creating a synthetic aperture image that is focused on the foreground...

Removing camera shake from a single photograph
Rob Fergus, Barun Singh, Aaron Hertzmann, Sam T. Roweis, William T. Freeman
Pages: 787-794
DOI: 10.1145/1141911.1141956
Camera shake during exposure leads to objectionable image blur and ruins many photographs. Conventional blind deconvolution methods typically assume frequency-domain constraints on images, or overly simplified parametric forms for the motion path...

Coded exposure photography: motion deblurring using fluttered shutter
Ramesh Raskar, Amit Agrawal, Jack Tumblin
Pages: 795-804
DOI: 10.1145/1141911.1141957
In a conventional single-exposure photograph, moving objects or moving cameras cause motion blur. The exposure time defines a temporal box filter that smears the moving object across the image by convolution. This box filter destroys important...

Section: Sampling and ray tracing

Efficient simulation of large bodies of water by coupling two and three dimensional techniques
Geoffrey Irving, Eran Guendelman, Frank Losasso, Ronald Fedkiw
Pages: 805-811
DOI: 10.1145/1141911.1141959
We present a new method for the efficient simulation of large bodies of water, especially effective when three-dimensional surface effects are important. Similar to a traditional two-dimensional height field approach, most of the water volume is...

Multiple interacting liquids
Frank Losasso, Tamar Shinar, Andrew Selle, Ronald Fedkiw
Pages: 812-819
DOI: 10.1145/1141911.1141960
The particle level set method has proven successful for the simulation of two separate regions (such as water and air, or fuel and products). In this paper, we propose a novel approach to extend this method to the simulation of as many regions...

Fluid animation with dynamic meshes
Bryan M. Klingner, Bryan E. Feldman, Nuttapong Chentanez, James F. O'Brien
Pages: 820-825
DOI: 10.1145/1141911.1141961
This paper presents a method for animating fluid using unstructured tetrahedral meshes that change at each time step. We show that meshes that conform well to changing boundaries and that focus computation in the visually important parts of the...

Model reduction for real-time fluids
Adrien Treuille, Andrew Lewis, Zoran Popović
Pages: 826-834
DOI: 10.1145/1141911.1141962
We present a new model reduction approach to fluid simulation, enabling large, real-time, detailed flows with continuous user interaction. Our reduced model can also handle moving obstacles immersed in the flow. We create separate models for the...

Section: Sampling and ray tracing

Photo tourism: exploring photo collections in 3D
Noah Snavely, Steven M. Seitz, Richard Szeliski
Pages: 835-846
DOI: 10.1145/1141911.1141964
We present a system for interactively browsing and exploring large unstructured collections of photographs of a scene using a novel 3D interface. Our system consists of an image-based modeling front end that automatically computes the viewpoint of...

Carsten Rother, Lucas Bordeaux, Youssef Hamadi, Andrew Blake
Pages: 847-852
DOI: 10.1145/1141911.1141965
The paper defines an automatic procedure for constructing a visually appealing collage from a collection of input images. The aim is that the resulting collage should be representative of the collection, summarising its main themes. It is also...

Photographing long scenes with multi-viewpoint panoramas
Aseem Agarwala, Maneesh Agrawala, Michael Cohen, David Salesin, Richard Szeliski
Pages: 853-861
DOI: 10.1145/1141911.1141966
We present a system for producing multi-viewpoint panoramas of long, roughly planar scenes, such as the facades of buildings along a city street, from a relatively sparse set of photographs captured with a handheld still camera that is moved along...

Schematic storyboarding for video visualization and editing
Dan B Goldman, Brian Curless, David Salesin, Steven M. Seitz
Pages: 862-871
DOI: 10.1145/1141911.1141967
We present a method for visualizing short video clips in a single static image, using the visual language of storyboards. These schematic storyboards are composed from multiple input frames and annotated using outlines, arrows, and text...

Section: Sampling and ray tracing

Interaction capture and synthesis
Paul G. Kry, Dinesh K. Pai
Pages: 872-880
DOI: 10.1145/1141911.1141969
Modifying motion capture to satisfy the constraints of new animation is difficult when contact is involved, and a critical problem for animation of hands. The compliance with which a character makes contact also reveals important aspects of the...

Capturing and animating skin deformation in human motion
Sang Il Park, Jessica K. Hodgins
Pages: 881-889
DOI: 10.1145/1141911.1141970
During dynamic activities, the surface of the human body moves in many subtle but visually significant ways: bending, bulging, jiggling, and stretching. We present a technique for capturing and animating those motions using a commercial motion...

Compression of motion capture databases
Okan Arikan
Pages: 890-897
DOI: 10.1145/1141911.1141971
We present a lossy compression algorithm for large databases of motion capture data. We approximate short clips of motion using Bezier curves and clustered principal component analysis. This approximation has a smoothing effect on the motion....

Motion patches: building blocks for virtual environments annotated with motion data
Kang Hoon Lee, Myung Geol Choi, Jehee Lee
Pages: 898-906
DOI: 10.1145/1141911.1141972
Real time animation of human figures in virtual environments is an important problem in the context of computer games and virtual environments. Recently, the use of large collections of captured motion data has increased realism in character...

Section: Sampling and ray tracing

Projection defocus analysis for scene capture and image display
Li Zhang, Shree Nayar
Pages: 907-915
DOI: 10.1145/1141911.1141974
In order to produce bright images, projectors have large apertures and hence narrow depths of field. In this paper, we present methods for robust scene capture and enhanced image display based on projection defocus analysis. We model a projector's...

Multiview radial catadioptric imaging for scene capture
Sujit Kuthirummal, Shree K. Nayar
Pages: 916-923
DOI: 10.1145/1141911.1141975
In this paper, we present a class of imaging systems, called radial imaging systems, that capture a scene from a large number of view-points within a single image, using a camera and a curved mirror. These systems can recover scene properties...

Light field microscopy
Marc Levoy, Ren Ng, Andrew Adams, Matthew Footer, Mark Horowitz
Pages: 924-934
DOI: 10.1145/1141911.1141976
By inserting a microlens array into the optical train of a conventional microscope, one can capture light fields of biological specimens in a single photograph. Although diffraction places a limit on the product of spatial and angular resolution in...

Fast separation of direct and global components of a scene using high frequency illumination
Shree K. Nayar, Gurunandan Krishnan, Michael D. Grossberg, Ramesh Raskar
Pages: 935-944
DOI: 10.1145/1141911.1141977
We present fast methods for separating the direct and global illumination components of a scene measured by a camera and illuminated by a light source. In theory, the separation can be done with just two images taken with a high frequency binary...

Section: Sampling and ray tracing

Real-time BRDF editing in complex lighting
Aner Ben-Artzi, Ryan Overbeck, Ravi Ramamoorthi
Pages: 945-954
DOI: 10.1145/1141911.1141979
Current systems for editing BRDFs typically allow users to adjust analytic parameters while visualizing the results in a simplified setting (e.g. unshadowed point light). This paper describes a real-time rendering system that enables interactive...

Generalized wavelet product integral for rendering dynamic glossy objects
Weifeng Sun, Amar Mukherjee
Pages: 955-966
DOI: 10.1145/1141911.1141980
We consider real-time rendering of dynamic glossy objects with realistic shadows under distant all-frequency environment lighting. Previous PRT approaches pre-compute light transport for a fixed scene and cannot account for cast shadows on...

All-frequency precomputed radiance transfer using spherical radial basis functions and clustered tensor approximation
Yu-Ting Tsai, Zen-Chung Shih
Pages: 967-976
DOI: 10.1145/1141911.1141981
This paper introduces a new data representation and compression technique for precomputed radiance transfer (PRT). The light transfer functions and light sources are modeled with spherical radial basis functions (SRBFs). A SRBF is a...

Real-time soft shadows in dynamic scenes using spherical harmonic exponentiation
Zhong Ren, Rui Wang, John Snyder, Kun Zhou, Xinguo Liu, Bo Sun, Peter-Pike Sloan, Hujun Bao, Qunsheng Peng, Baining Guo
Pages: 977-986
DOI: 10.1145/1141911.1141982
Previous methods for soft shadows numerically integrate over many light directions at each receiver point, testing blocker visibility in each direction. We introduce a method for real-time soft shadows in dynamic scenes illuminated by large,...

Precomputed acoustic transfer: output-sensitive, accurate sound generation for geometrically complex vibration sources
Doug L. James, Jernej Barbič, Dinesh K. Pai
Pages: 987-995
DOI: 10.1145/1141911.1141983
Simulating sounds produced by realistic vibrating objects is challenging because sound radiation involves complex diffraction and interreflection effects that are very perceptible and important. These wave phenomena are well understood, but have been...

Section: Sampling and ray tracing

Photorealistic rendering of rain streaks
Kshitiz Garg, Shree K. Nayar
Pages: 996-1002
DOI: 10.1145/1141911.1141985
Photorealistic rendering of rain streaks with lighting and viewpoint effects is a challenging problem. Raindrops undergo rapid shape distortions as they fall, a phenomenon referred to as oscillations. Due to these oscillations, the reflection of...

Acquiring scattering properties of participating media by dilution
Srinivasa G. Narasimhan, Mohit Gupta, Craig Donner, Ravi Ramamoorthi, Shree K. Nayar, Henrik Wann Jensen
Pages: 1003-1012
DOI: 10.1145/1141911.1141986
The visual world around us displays a rich set of volumetric effects due to participating media. The appearance of these media is governed by several physical properties such as particle densities, shapes and sizes, which must be input (directly or...

Analysis of human faces using a measurement-based skin reflectance model
Tim Weyrich, Wojciech Matusik, Hanspeter Pfister, Bernd Bickel, Craig Donner, Chien Tu, Janet McAndless, Jinho Lee, Addy Ngan, Henrik Wann Jensen, Markus Gross
Pages: 1013-1024
DOI: 10.1145/1141911.1141987
We have measured 3D face geometry, skin reflectance, and subsurface scattering using custom-built devices for 149 subjects of varying age, gender, and race. We developed a novel skin reflectance model whose parameters can be estimated from...

A statistical model for synthesis of detailed facial geometry
Aleksey Golovinskiy, Wojciech Matusik, Hanspeter Pfister, Szymon Rusinkiewicz, Thomas Funkhouser
Pages: 1025-1034
DOI: 10.1145/1141911.1141988
Detailed surface geometry contributes greatly to the visual realism of 3D face models. However, acquiring high-resolution face geometry is often tedious and expensive. Consequently, most face models used in games, virtual reality, or computer vision...

Section: Sampling and ray tracing

Modified subdivision surfaces with continuous curvature
Adi Levin
Pages: 1035-1040
DOI: 10.1145/1141911.1141990
We present a modification to subdivision surfaces, which guarantees second-order smoothness everywhere in the surface, including extraordinary points. The idea is to blend the limit surface with a low degree polynomial defined over the characteristic...

Edge subdivision schemes and the construction of smooth vector fields
Ke Wang, Weiwei, Yiying Tong, Mathieu Desbrun, Peter Schröder
Pages: 1041-1048
DOI: 10.1145/1141911.1141991
Vertex- and face-based subdivision schemes are now routinely used in geometric modeling and computational science, and their primal/dual relationships are well studied. In this paper, we interpret these schemes as defining bases for discrete...

Streaming computation of Delaunay triangulations
Martin Isenburg, Yuanxin Liu, Jonathan Shewchuk, Jack Snoeyink
Pages: 1049-1056
DOI: 10.1145/1141911.1141992
We show how to greatly accelerate algorithms that compute Delaunay triangulations of huge, well-distributed point sets in 2D and 3D by exploiting the natural spatial coherence in a stream of points. We achieve large performance gains by introducing...

Spectral surface quadrangulation
Shen Dong, Peer-Timo Bremer, Michael Garland, Valerio Pascucci, John C. Hart
Pages: 1057-1066
DOI: 10.1145/1141911.1141993
Resampling raw surface meshes is one of the most fundamental operations used by nearly all digital geometry processing systems. The vast majority of this work has focused on triangular remeshing, yet quadrilateral meshes are preferred for many...

Section: Sampling and ray tracing

Simulating multiple scattering in hair using a photon mapping approach
Jonathan T. Moon, Stephen R. Marschner
Pages: 1067-1074
DOI: 10.1145/1141911.1141995
Simulating multiple scattering correctly is important for accurate rendering of hair. However, a volume of hair is a difficult scene to simulate because scattering from an individual fiber is very structured and forward directed, and because the...

Statistical acceleration for animated global illumination
Mark Meyer, John Anderson
Pages: 1075-1080
DOI: 10.1145/1141911.1141996
Global illumination provides important visual cues to an animation, however its computational expense limits its use in practice. In this paper, we present an easy to implement technique for accelerating the computation of indirect illumination for...

Multidimensional lightcuts
Bruce Walter, Adam Arbree, Kavita Bala, Donald P. Greenberg
Pages: 1081-1088
DOI: 10.1145/1141911.1141997
Multidimensional lightcuts is a new scalable method for efficiently rendering rich visual effects such as motion blur, participating media, depth of field, and spatial anti-aliasing in complex scenes. It introduces a flexible, general rendering...

Direct-to-indirect transfer for cinematic relighting
Miloš Hašan, Fabio Pellacini, Kavita Bala
Pages: 1089-1097
DOI: 10.1145/1141911.1141998
This paper presents an interactive GPU-based system for cinematic relighting with multiple-bounce indirect illumination from a fixed view-point. We use a deep frame-buffer containing a set of view samples, whose indirect illumination is recomputed...

Section: Sampling and ray tracing

Editing arbitrarily deforming surface animations
Scott Kircher, Michael Garland
Pages: 1098-1107
DOI: 10.1145/1141911.1142000
Deforming surfaces, such as cloth, can be generated through physical simulation, morphing, and even video capture. Such data is currently very difficult to alter after the generation process is complete, and data generated for one purpose generally...

A fast multigrid algorithm for mesh deformation
Lin Shi, Yizhou Yu, Nathan Bell, Wei-Wen Feng
Pages: 1108-1117
DOI: 10.1145/1141911.1142001
In this paper, we present a multigrid technique for efficiently deforming large surface and volume meshes. We show that a previous least-squares formulation for distortion minimization reduces to a Laplacian system on a general graph structure for...

Vector field based shape deformations
Wolfram von Funck, Holger Theisel, Hans-Peter Seidel
Pages: 1118-1125
DOI: 10.1145/1141911.1142002
We present an approach to define shape deformations by constructing and interactively modifying C1 continuous time-dependent divergence-free vector fields. The deformation is obtained by a path line integration of the mesh vertices....

Subspace gradient domain mesh deformation
Jin Huang, Xiaohan Shi, Xinguo Liu, Kun Zhou, Li-Yi Wei, Shang-Hua Teng, Hujun Bao, Baining Guo, Heung-Yeung Shum
Pages: 1126-1134
DOI: 10.1145/1141911.1142003
In this paper we present a general framework for performing constrained mesh deformation tasks with gradient domain techniques. We present a gradient domain technique that works well with a wide variety of linear and nonlinear constraints. The...

Section: Sampling and ray tracing

Locally adapted hierarchical basis preconditioning
Richard Szeliski
Pages: 1135-1143
DOI: 10.1145/1141911.1142005
This paper develops locally adapted hierarchical basis functions for effectively preconditioning large optimization problems that arise in computer graphics applications such as tone mapping, gradient-domain blending, colorization, and scattered data...

Fast proximity computation among deformable models using discrete Voronoi diagrams
Avneesh Sud, Naga Govindaraju, Russell Gayle, Ilknur Kabul, Dinesh Manocha
Pages: 1144-1153
DOI: 10.1145/1141911.1142006
We present novel algorithms to perform collision and distance queries among multiple deformable models in dynamic environments. These include inter-object queries between different objects as well as intra-object queries. We describe a unified...

Resolving surface collisions through intersection contour minimization
Pascal Volino, Nadia Magnenat-Thalmann
Pages: 1154-1159
DOI: 10.1145/1141911.1142007
Robust handling of collisions on non-oriented deformable surfaces requires advanced methods for recovering intersecting surfaces. We present a novel method that resolves intersections between two intersecting surface regions by inducing relative...

Continuum crowds
Adrien Treuille, Seth Cooper, Zoran Popović
Pages: 1160-1168
DOI: 10.1145/1141911.1142008
We present a real-time crowd model based on continuum dynamics. In our model, a dynamic potential field simultaneously integrates global navigation with moving obstacles such as other people, efficiently solving for the motion of large crowds without...

Section: Sampling and ray tracing

The cartoon animation filter
Jue Wang, Steven M. Drucker, Maneesh Agrawala, Michael F. Cohen
Pages: 1169-1173
DOI: 10.1145/1141911.1142010
We present the "Cartoon Animation Filter", a simple filter that takes an arbitrary input motion signal and modulates it in such a way that the output motion is more "alive" or "animated". The filter adds a smoothed, inverted, and (sometimes) time...

Inverse kinematics for reduced deformable models
Kevin G. Der, Robert W. Sumner, Jovan Popović
Pages: 1174-1179
DOI: 10.1145/1141911.1142011
Articulated shapes are aptly described by reduced deformable models that express required shape deformations using a compact set of control parameters. Although sufficient to describe most shape deformations, these control parameters can be...

Super-helices for predicting the dynamics of natural hair
Florence Bertails, Basile Audoly, Marie-Paule Cani, Bernard Querleux, Frédéric Leroy, Jean-Luc Lévêque
Pages: 1180-1187
DOI: 10.1145/1141911.1142012
Simulating human hair is recognized as one of the most difficult tasks in computer animation. In this paper, we show that the Kirchhoff equations for dynamic, inextensible elastic rods can be used for accurately predicting hair motion. These...

Heads up!: biomechanical modeling and neuromuscular control of the neck
Sung-Hee Lee, Demetri Terzopoulos
Pages: 1188-1198
DOI: 10.1145/1141911.1142013
Unlike the human face, the neck has been largely overlooked in the computer graphics literature, this despite its complex anatomical structure and the important role that it plays in supporting the head in balance while generating the controlled head...

Section: Sampling and ray tracing

Exaggerated shading for depicting shape and detail
Szymon Rusinkiewicz, Michael Burns, Doug DeCarlo
Pages: 1199-1205
DOI: 10.1145/1141911.1142015
In fields ranging from technical illustration to mapmaking, artists have developed distinctive visual styles designed to convey both detail and overall shape as clearly as possible. We investigate a non-photorealistic shading model, inspired by...

Image enhancement by unsharp masking the depth buffer
Thomas Luft, Carsten Colditz, Oliver Deussen
Pages: 1206-1213
DOI: 10.1145/1141911.1142016
We present a simple and efficient method to enhance the perceptual quality of images that contain depth information. Similar to an unsharp mask, the difference between the original depth buffer content and a low-pass filtered copy is utilized to...

Manga colorization
Yingge Qu, Tien-Tsin Wong, Pheng-Ann Heng
Pages: 1214-1220
DOI: 10.1145/1141911.1142017
This paper proposes a novel colorization technique that propagates color over regions exhibiting pattern-continuity as well as intensity-continuity. The proposed method works effectively on colorizing black-and-white manga which contains intensive...

Real-time video abstraction
Holger Winnemöller, Sven C. Olsen, Bruce Gooch
Pages: 1221-1226
DOI: 10.1145/1141911.1142018
We present an automatic, real-time video and image abstraction framework that abstracts imagery by modifying the contrast of visually important features, namely luminance and color opponency. We reduce contrast in low-contrast regions using an...