ACM DL

ACM Transactions on

Graphics (TOG)

Menu
Latest Articles

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... (more)

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

We propose a novel algorithm for decomposing general three-dimensional geometries into a small set of overlap-free height-field blocks, volumes... (more)

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)

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... (more)

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 article is a... (more)

Iterative Depth Warping

This article presents an iterative backward-warping technique and its applications. It predictively synthesizes depth buffers for novel views. Our solution is based on a fixed-point iteration that converges quickly in practice. Unlike the previous techniques, our solution is a pure backward warping without using bidirectional sources. To... (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,

Steklov Spectral Geometry for Extrinsic Shape Analysis

We propose Steklov geometry processing, an extrinsic approach to spectral geometry processing and shape analysis. Intrinsic approaches, usually based on the LaplaceBeltrami operator, cannot capture the spatial embedding of a shape up to rigid motion, while many previous extrinsic methods lack theoretical justification. Instead, we propose a systematic approach by considering the Steklov eigenvalue problem, computing the spectrum of the Dirichlet-to-Neumann operator of a surface bounding a volume. A remarkable property of this operator is that it encodes the volumetric geometry. We use the boundary element method (BEM) to discretize the operator, accelerated by hierarchical numerical schemes and preconditioning; this pipeline allows us to solve eigenvalue and linear problems on large-scale meshes despite the density of the Dirichlet-to-Neumann discretization. We further demonstrate that our operators naturally fit into existing frameworks for geometry processing, making a shift from intrinsic to extrinsic geometry as simple as substituting the LaplaceBeltrami operator with the Dirichlet-to-Neumann operator.

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.

Knittable Stitch Meshes

We introduce knittable stitch meshes for modeling complex 3D knit structures that can be fabricated via knitting. We extend the concept of stitch mesh modeling, which provides a powerful 3D design interface for knit structures but lacks the ability to produce actually knittable models. Knittable stitch meshes ensure that the final model can be knitted. Moreover, they include novel representations for handling important shaping techniques that allow modeling more complex knit structures than prior methods. In particular, we introduce shift-paths that connect the yarn for neighboring rows, general solutions for properly connecting pieces of knit fabric with mismatched knitting directions without introducing seams, and a new structure for representing short rows, a shaping technique for knitting that is crucial for creating various 3D forms, within the stitch mesh modeling framework. Our new 3D modeling interface allows for designing knittable structures with complex surface shapes and topologies, and our knittable stitch mesh structure contains all information needed for fabricating these shapes via knitting. Furthermore, we present a scheduling algorithm for providing step-by-step hand knitting instructions to a knitter. We show a variety of 3D knit shapes and garment examples designed and knitted using our system.

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.

Progressive Color Transfer with Dense Semantic Correspondences

We propose a new algorithm for color transfer between images that have perceptually similar semantic structures. We aim to achieve a more accurate color transfer that leverages semantically-meaningful dense correspondence between images. To accomplish this, our algorithm uses neural representations for matching. Additionally, the color transfer should be spatially-variant and globally coherent. Therefore, our algorithm optimizes a local linear model for color transfer satisfying both local and global constraints. Our proposed approach jointly optimizes matching and color transfer, adopting a coarse-to-fine strategy. The proposed method can be successfully extended from "one-to-one" to "one-to-many" color transfers. The latter further addresses the problem of mismatching elements of the input image. We validate our proposed method by testing it on a large variety of image content.

Functional Characterization of Deformation Fields

In this paper we present a novel representation for deformation fields of 3D shapes, by considering the induced changes in the underlying metric. In particular, our approach allows to represent a deformation field in a coordinate-free way as a linear operator acting on real-valued functions defined on the shape. Such a representation both provides a way to relate deformation fields to other classical functional operators and enables analysis and processing of deformation fields using standard linear-algebraic tools. This opens the door to a wide variety of applications such as deformation design through precise control of metric distortion, joint deformation analysis and coordinate-free deformation transfer without requiring pointwise correspondences. Our method is applicable to both surface and volumetric shape representations and we guarantee the equivalence between the operator-based and standard deformation field representation under mild genericity conditions in the discrete setting. We demonstrate the utility of our approach by comparing it with existing techniques for deformation transfer, and show significant improvement in the presence of approximate, soft maps. We also show how our representation provides a toolbox for problems which are challenging using existing techniques, such as intrinsic symmetrization and injecting extrinsic information into the computation of functional maps.

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.

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.

Vectorization of Line Drawings via PolyVector Fields

Image tracing is a foundational component of the workflow in graphic design, engineering, and computer animation, linking hand-drawn concept images to collections of smooth curves needed for geometry processing and editing. Even for clean line drawings, modern algorithms often fail to faithfully vectorize junctions, or points at which curves meet; this produces vector drawings with incorrect connectivity. This subtle issue undermines the practical application of vectorization tools and accounts for hesitance among artists and engineers to use automatic vectorization software. To address this issue, we propose a novel image vectorization method based on state-of-the-art mathematical algorithms for frame field processing. Our algorithm is tailored specifically to disambiguate junctions without sacrificing quality.

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.

All ACM Journals | See Full Journal Index

Search TOG
enter search term and/or author name