ACM DL

ACM Transactions on

Graphics (TOG)

Menu
Latest Articles

Real-time High-accuracy Three-Dimensional Reconstruction with Consumer RGB-D Cameras

We present an integrated approach for reconstructing high-fidelity three-dimensional (3D) models using consumer RGB-D cameras. RGB-D registration and... (more)

Editing Fluid Animation Using Flow Interpolation

The computational cost for creating realistic fluid animations by numerical simulation is generally expensive. In digital production environments, existing precomputed fluid animations are often reused for different scenes in order to reduce the cost of creating scenes containing fluids. However, applying the same animation to different scenes... (more)

Spline Interface for Intuitive Skinning Weight Editing

Despite the recent advances in automatic methods for computing skinning weights, manual intervention is still indispensable to produce high-quality... (more)

NEWS

New Submission Requirements

As of October 2018, ACM TOG requires submissions for review to be anonymous. See the Author Guidelines for details.  

About TOG

ACM TOG is the foremost peer-reviewed journal in the area of computer graphics. 

Recent impact factor calculations from Thomson Reuters give ACM TOG an impact factor of 4.096 and an Eigenfactor Score of 0.029, giving it the top ranking among the 104 journals in the Computer Science: Software Engineering category. 

read more
Forthcoming Articles
ALIGNet: Partial-Shape Agnostic Alignment via Unsupervised Learning

The process of aligning a pair of shapes is a fundamental operation in computer graphics. Traditional alignment methods rely heavily on matching corresponding points or features, a paradigm that falters when significant shape portions are missing. In this paper, we present a novel alignment technique between two 2D shapes that is robust to shape incompleteness. We take an unsupervised learning approach, and train a neural network on the task of shape alignment using pairs of shapes for self-supervision. Our network, called FFDnet, learns the space of warping transformations between two shapes by performing a free-form deformation on a source shape such that it aligns well with a potentially geometrically distinct partial target shape. With this extensive training, we aim for the network to form a specialized expertise over the common characteristics of the shapes in each dataset, supporting a higher-level understanding of the expected shape space that a local approach is oblivious to. Specifically, the network is trained to warp complete source shapes to incomplete targets generated from full shapes, as if the target shapes were complete, thus essentially rendering the alignment partial-shape agnostic. We constrain FFDnet through an anisotropic total variation identity regularization to promote piecewise smooth deformation fields,

Physics-Inspired Garment Recovery from a Single-View Image

Most recent garment capturing techniques rely on acquiring multiple views of clothing, which may not always be readily available, especially in the case of pre-existing photographs from the web. As an alternative, we propose a method that is able to compute a rich and realistic 3D model of a human body and its outfits from a single photograph with little human interaction. Our algorithm is not only able to capture the global shape and geometry of the clothing, it can also extract small but important details of cloth, such as occluded wrinkles and folds. Unlike previous methods using full 3D information (i.e. depth, multi-view images, or sampled 3D geometry), our approach achieves detailed garment recovery from a single-view image by using statistical, geometric, and physical priors and a combination of parameter estimation, semantic parsing, shape recovery, and physics-based cloth simulation. We demonstrate the effectiveness of our algorithm by re-purposing the reconstructed garments for virtual try-on and garment transfer applications, as well as cloth animation for digital characters.

Zero Variance-based Sampling for Volume Path Guiding

Monte Carlo methods are commonly used for robust rendering of scenes with volumetric participating media. The efficiency of these approaches is directly linked to the manner in which random sampling decisions are made during light path construction. Notably, path construction is influenced by scattering direction and distance sampling, Russian roulette, and splitting strategies. We present a new volumetric path construction technique where all these sampling decisions are guided by a cached estimate of the adjoint light transport solution. Our sampling strategy is based on the theory of zero-variance transport estimators, and it accounts for the spatial and directional variation in volumetric transport. Specifically, we construct paths incrementally by sampling collision distances proportionally to the product of transmittance and the adjoint transport solution (i.e., in-scattered radiance). Scattering directions are likewise sampled according to the product of the phase function and the incident radiance estimate. Combined with an adaptive Russian roulette and splitting strategy tailored to volumes, we demonstrate about an order-of-magnitude variance reduction compared to modern uni-directional methods. Consequently, our approach can render scenes that are otherwise intractable for such methods, while still retaining their simplicity (compared to, e. g., bi-directional methods).

Efficient and Accurate Collision Response for Elastically Deformable Models

Simulating (elastically) deformable models that can collide with each other and with the environment remains a challenging task. The resulting contact problems can be elegantly approached using Lagrange multipliers to represent the unknown magnitude of the response forces. Typical methods construct and solve a Linear Complementarity Problem (LCP) to obtain the response forces. This requires the inverse of the generalized mass matrix, which is in general hard to obtain for deformable-body problems. In this paper we tackle such contact problems by directly solving the Mixed Linear Complementarity Problem (MLCP) and omitting the construction of an LCP matrix. Since the MLCP is equivalent to a convex quadratic program subject to inequality constraints, we propose to use a Conjugate Residual (CR) solver as the backbone of our collision-response system. We also propose a simple yet efficient preconditioner that ensures faster convergence. Finally, our approach is faster than existing methods (at the same accuracy), and it allows accurate treatment of friction.

Blockwise Multi-Order Feature Regression for Real-Time Path Tracing Reconstruction

Path tracing produces realistic results including global illumination using a unified simple rendering pipeline. Reducing the amount of noise to imperceptible levels without post-processing requires thousands of samples per pixel (spp), while currently it is only possible to render extremely noisy 1 spp frames in real time with desktop GPUs. However, post-processing can utilize feature buffers, which contain noise-free auxiliary data available in the rendering pipeline. Previously, regression-based noise filtering methods have only been used in offline rendering due to their high computational cost. In this paper we propose a novel regression-based reconstruction pipeline, called Blockwise Multi-Order Feature Regression (BMFR), tailored for path-traced 1 spp inputs that runs in real time. The high speed is achieved with a fast implementation of augmented QR factorization and by using stochastic regularization to address rank-deficient feature data. The proposed algorithm is 1.8× faster than the previous state-of-the-art real-time path tracing reconstruction method while producing better quality frame sequences.

A Unified Framework for Compression and Compressed Sensing of Light Fields and Light Field Videos

In this paper we present a novel dictionary learning framework designed for compression and sampling of light fields and light field videos. Unlike previous methods, where a single dictionary with one dimensional atoms is learned, we propose to train a multi dimensional dictionary ensemble (MDE). We show that learning an ensemble in the native dimensionality of the data promotes sparsity, hence increasing the compression ratio and sampling efficiency. To make maximum use of correlations within the light field data sets, we also introduce a novel non-local pre-clustering approach that constructs an aggregate MDE (AMDE). The pre-clustering not only improves the image quality, but also reduces the training time by an order of magnitude in most cases. The decoding algorithm supports efficient local reconstruction of the compressed data, which enables efficient real-time playback of high resolution light field videos. Moreover, we discuss the application of AMDE for compressed sensing. A theoretical analysis is presented which indicates the required conditions for exact recovery of point-sampled light fields that are sparse under AMDE. The analysis provides guidelines for designing efficient compressive light field cameras.

Interlinked SPH Pressure Solvers for Strong Fluid-Rigid Coupling

We present a strong fluid-rigid coupling for SPH fluids and rigid bodies with particle-sampled surfaces. The approach interlinks the iterative pressure update at fluid particles with a second SPH solver that computes artificial pressure at rigid body particles. The introduced SPH rigid body solver models rigid-rigid contacts as artificial density deviations at rigid body particles. The corresponding pressure is iteratively computed by solving a global formulation which is particularly useful for large numbers of rigid-rigid contacts. Compared to previous SPH coupling methods, the proposed concept stabilizes the fluid-rigid interface handling. It significantly reduces the computation times of SPH fluid simulations by enabling larger time steps. Performance gain factors of up to 58 compared to previous methods are presented. We illustrate the flexibility of the presented fluid-rigid coupling by integrating it into DFSPH, IISPH and a recent SPH solver for highly viscous fluids. We further show its applicability to a recent SPH solver for elastic objects. Large scenarios with up to 90M particles of various interacting materials and complex contact geometries with up to 90k rigid-rigid contacts are shown. We demonstrate the competitiveness of our proposed rigid body solver by comparing it to Bullet.

Plan3D: Viewpoint and Trajectory Optimization for Aerial Multi-View Stereo Reconstruction

We introduce a new method that efficiently computes a set of viewpoints and trajectories for high-quality 3D reconstructions in outdoor environments. Our goal is to automatically explore an unknown area, and obtain a complete 3D scan of a region of interest (e.g., a large building). Images from a commodity RGB camera, mounted on an autonomously navigated quadcopter, are fed into a multi-view stereo reconstruction pipeline that produces high-quality results but is computationally expensive. In this setting, the scanning result is constraint by the restricted flight time of quadcopters. To this end, we introduce a novel optimization strategy that respects these constraints by maximizing the information gain from sparsely-sampled view points while limiting the total travel distance of the quadcopter. Our information gain formulation leverages a hierarchical representation of this space to recognize occlusions in an efficient manner. In addition to the surface geometry, we utilize the free-space information to avoid obstacles and determine collision-free flight paths. Our tool can be used to specify the region of interest and to plan trajectories. We demonstrate our method by obtaining a number of compelling 3D reconstructions, and provide a thorough quantitative evaluation showing improvement over previous state-of-the-art and regular patterns.

2PAC: Two Point Attractors for Center of Mass Trajectories in Multi Contact Scenarios

Synthesizing motions for legged characters in arbitrary environments is a long-standing problem that has recently received a lot of attention from the computer graphics community. We tackle this problem with a procedural approach that is generic, fully automatic and independent from motion capture data. The main contribution of this paper is a point-mass-model-based method to synthesize Center Of Mass trajectories. These trajectories are then used to generate the whole-body motion of the character. The use of a point mass model often results in physically inconsistent motions and joint limit violations. We mitigate these issues through the use of a novel formulation of the kinematic constraints which allows us to generate a quasi-static Center Of Mass trajectory, in a way that is both user-friendly and computationally efficient. We also show that the quasi-static constraint can be relaxed to generate motions usable for applications of computer graphics (on average 83% of a given trajectory remain physically consistent). Our method was integrated in an open-source contact planner and tested with different scenarios - some never addressed before- featuring legged characters performing motions in cluttered environments. The computational efficiency of our trajectory generation algorithm enables us to synthesize motions in a few seconds.

A Genetic Isometric Shape Correspondence Algorithm with Adaptive Sampling

We exploit the permutation creation ability of genetic optimization to find the permutation of one point set that puts it into correspondence with another one. To this effect, we provide the first, to our knowledge, genetic algorithm for 3D shape correspondence, which is the main contribution of this paper. As another significant contribution, we present an adaptive sampling approach that relocates the matched points based on the currently available correspondence via an alternating optimization. The point sets to be matched are sampled from two isometric (or nearly isometric) shapes. The sparse one-to-one correspondence, i.e., bijection, that we produce is validated both in terms of timing and accuracy in a comprehensive evaluation suite that includes three standard shape benchmarks and state-of-the-art techniques.

LineUp: Computing Chain-based Physical Transformation

In this paper, we introduce a novel method that can generate a sequence of physical transformations between 3D models with different shape and topology. Feasible transformations are realized on a chain structure with connected components that are 3D printed. Collision-free motions are computed to transform between different configurations of the 3D printed chain structure. To realize the transformation between different 3D models, we first voxelize these input models into similar number of voxels. The challenging part of our approach is to generate a simple path --- as a chain configuration to connect most voxels. A layer-based algorithm is developed with theoretical guarantee of the existence and the path length. We find that collision-free motion sequence can always be generated when using a straight line as the intermediate configuration of transformation. The effectiveness of our method is demonstrated by both the simulation and the experimental tests taken on 3D printed chains.

Analytic Eigensystems for Isotropic Distortion Energies

Many strategies exist for optimizing non-linear distortion energies in geometry and physics applications, but devising an approach that achieves the convergence promised by Newton-type methods remains challenging. In order to guarantee the positive semi-definiteness required by these methods, a numerical eigendecomposition or approximate regularization is usually needed. In this paper, we present analytic expressions for the eigensystems at each quadrature point of a wide range of isotropic distortion energies. These systems can then be used to project energy Hessians to positive semi-definiteness analytically. Unlike previous attempts, our formulation provides compact expressions that are valid both in 2D and 3D, and does not introduce spurious degeneracies. At its core, our approach utilizes the invariants of the stretch tensor that arises from the polar decomposition of the deformation gradient. We provide closed-form expressions for the eigensystems for all these invariants, and use them to systematically derive the eigensystems of any isotropic energy. Our results are suitable for geometry optimization over flat surfaces or volumes, and agnostic to both the choice of discretization and basis function. To demonstrate the efficiency of our approach, we include comparisons against existing methods on common graphics tasks such as surface parameterization and volume deformation.

Dataset and metrics for predicting local visible differences

A large number of imaging and computer graphics applications require localized information on the visibility of image distortions. Existing image quality metrics are not suitable for this task as they provide a single quality value per image. Existing visibility metrics produce visual difference maps, and are specifically designed for detecting just noticeable distortions but their predictions are often inaccurate. In this work, we argue that the key reason for this problem is the lack of large image collections with a good coverage of possible distortions that occur in different applications. To address the problem, we collect an extensive dataset of reference and distorted image pairs together with user markings indicating whether distortions are visible or not. We propose a statistical model that is designed for the meaningful interpretation of such data, which is affected by visual search and imprecision of manual marking. We use our dataset for training existing metrics and we demonstrate that their performance significantly improves. We show that our dataset with the proposed statistical model can be used to train a new CNN-based metric, which outperforms the existing solutions. We demonstrate the utility of such a metric in visually lossless JPEG compression, super-resolution and watermarking.

Automatic Facial Rigging in the Wild

We present an automatic facial rigging system for generating person specific 3D facial blendshapes from images in the wild (e.g., Internet images of Hillary Clinton), where the face shape, pose, expressions, and illumination are all unknown. Our system initializes the 3D blendshapes with sparse facial features detected from the input images using a mutli-linear model and then refines the blendshapes via per-pixel shading cues with a new blendshape retargeting algorithm. Finally, we introduce a new algorithm for recovering detailed facial features from the input images. To handle large variations of face poses and illuminations in the input images, we also develop a set of failure detection schemes that can robustly filter out inaccurate results in each step. Our method greatly simplifies the 3D facial rigging process and generates a more faithful face shape and expression of the subject than multi-linear model fitting. We validate the robustness and accuracy of our system using images of a dozen subjects that exhibit significant variations of face shapes, poses, expressions, and illuminations.

Re-Cinematography for 360° Video: Joint Stabilization and Direction

Creating high-quality 360° video content can be challenging, as viewers may miss important events by looking in the wrong direction, or they may see things that ruin the immersion, such as stitching artifacts and the film crew. We propose 360° video re-cinematography, where the video is jointly optimized to orient important events to the front of the viewer and visual clutter behind them, while producing smooth camera motion. Unlike traditional video, viewers can still explore the space as desired, but with the knowledge that the most important content is likely to be in front of them. Cinematographic constraints can be user guided, either added directly on the equirectangular projection or by recording ``guidance'' viewing directions while watching the video in a VR headset, or automatically computed, such as via visual saliency or forward motion direction. To accomplish this, we propose a new motion estimation technique specifically designed for 360° video which outperforms the commonly used 5-point algorithm on wide angle video. We compare our approach to recent methods that address stabilization-only and converting 360° video to narrow field-of-view video.

Axis-Aligned Height-Field Block Decomposition of 3D Shapes

Subtractive manufacturing technologies, such as 3-axis milling, add a useful tool to the digital manufacturing arsenal. However, each milling pass using such machines can only carve a single height-field, defined with respect to the machine tray. We enable fabrication of general shapes using 3-axis milling, providing a robust algorithm to decompose any shape into a few height-field blocks. Such blocks can be manufactured with a single milling pass and then assembled to form the target geometry. Computing such decompositions requires solving a complex discrete optimization problem, variants of which are known to be NP-hard. We propose a two-step process, based on the observation that if the height-field directions are constrained to the major axes we can guarantee a valid decomposition starting from a suitable surface segmentation. Our method first produces a compact set of large, possibly overlapping, height-field blocks that jointly cover the model surface. We then compute an overlap-free decomposition via a combination of cycle elimination and topological sorting on a graph. The algorithm produces a compact set of height-field blocks that jointly describe the input model and satisfy all manufacturing constraints. We demonstrate our method on a range of inputs, and showcase several real life models manufactured using our technique.

The Vector Heat Method

This paper describes a method for efficiently computing parallel transport of tangent vectors on curved surfaces, or more generally, any vector-valued data on a curved manifold. More precisely, it extends a vector field defined over any region to the rest of the domain via parallel transport along shortest geodesics. This basic operation enables fast, robust algorithms for extrapolating level set velocities, inverting the exponential map, computing geometric medians and Karcher/Fréchet means of arbitrary distributions, constructing centroidal Voronoi diagrams, and finding consistently ordered landmarks. Rather than evaluate parallel transport by explicitly tracing geodesics, we show that it can be computed via a short-time heat flow involving the connection Laplacian. As a result, transport can be achieved by solving three prefactored linear systems, each akin to a standard Poisson problem. Moreover, to implement the method we need only a discrete connection Laplacian, which we describe for a variety of geometric data structures (point clouds, polygon meshes, etc.). We also study the numerical behavior of our method, showing empirically that it converges under refinement, and augment the construction of intrinsic Delaunay triangulations (iDT) so that they can be used in the context of tangent vector field processing.

Non-line-of-sight Imaging with Partial Occluders and Surface Normals

Imaging objects obscured by occluders is a significant challenge for many applications. A camera that could ``see around corners'' could help improve navigation and mapping capabilities of autonomous vehicles or make search and rescue missions more effective. Time-resolved single-photon imaging systems have recently been demonstrated to record optical information of a scene that can lead to an estimation of the shape and reflectance of objects hidden from the line of sight of a camera. However, existing non-line-of-sight (NLOS) reconstruction algorithms have been constrained in the types of light transport effects they model for the hidden scene parts. We introduce a factored NLOS light transport representation that accounts for partial occlusions and surface normals. Based on this model, we develop a factorization approach for inverse time-resolved light transport and demonstrate high-fidelity NLOS reconstructions for challenging scenes both in simulation and with an experimental NLOS imaging system.

Surface Reconstruction Based on Modified Gauss Formula

In this paper, we introduce a surface reconstruction method that can perform gracefully with non-uniformly-distributed, noisy, and even sparse data. We reconstruct the surface by estimating an implicit function and then obtain a triangle mesh by extracting an iso-surface from it. Our implicit function takes advantage of both the indicator function and the signed distance function. It is dominated by the indicator function at the regions away from the surface and approximates the signed distance function near the surface. On one hand, it is well defined over the entire space so that the extracted iso-surface must lie near the underlying true surface and is free of spurious sheets. On the other hand, thanks to the nice properties of the signed distance function, a smooth iso-surface can be extracted using the approach of marching cubes with simple linear interpolations. More importantly, our implicit function can be estimated directly from an explicit integral formula without solving any linear system. This direct approach leads to a simple, accurate and robust reconstruction method, which can be paralleled with little overhead. We apply our method to both synthetic and real-world scanned data and demonstrate the accuracy, robustness and efficiency of our method.

A Quantitative Perceptual Model for Tactile Roughness

Everyone uses the sense of touch to explore the world, and roughness is one of the most important qualities in tactile perception. Roughness is a major identifier for judgments of material composition, comfort and friction, and it is tied closely to manual dexterity. The advent of high-resolution 3D printing technology provides the ability to fabricate arbitrary 3D textures with surface geometry that confers haptic properties. In this work, we address the problem of mapping object geometry to tactile roughness. We fabricate a set of carefully designed stimuli and use them in experiments with human subjects to build a perceptual space for roughness. We then match this space to a quantitative model obtained from strain fields derived from elasticity simulations of the human skin contacting the texture geometry, drawing from past research in neuroscience and psychophysics. We demonstrate how this model can be applied to predict and alter surface roughness, and we show several applications in the context of fabrication.

All ACM Journals | See Full Journal Index

Search TOG
enter search term and/or author name