Compressing dynamic meshes with geometric laplacians

This paper addresses the problem of representing dynamic 3D meshes in a compact way, so that they can be stored and transmitted efficiently. We focus on sequences of triangle meshes with shared connectivity, avoiding the necessity of having a skinning structure. Our method first computes an average mesh of the whole sequence in edge shape space. A discrete geometric Laplacian of this average surface is then used to encode the coefficients that describe the trajectories of the mesh vertices. Optionally, a novel spatio‐temporal predictor may be applied to the trajectories to further improve the compression rate. We demonstrate that our approach outperforms the current state of the art in terms of low data rate at a given perceived distortion, as measured by the STED and KG error metrics.     

Rate‐distortion optimized compression of motion capture data

Lossy compression of motion capture data can alleviate the problems of efficient storage and transmission by exploiting the redundancy and the superfluous precision of the data. When considering the acceptable amount of distortion, perceptual issues have to be taken into account. Current state of the art methods reduce the data rate required for high quality storage of motion capture data using various techniques. Most of them, however, do not use the common tools of general data compression, such as the method of Lagrange multipliers, and thus they obtain sub‐optimal results, making it difficult to do a fair comparison of their performance. In this paper, we present a general preprocessing step based on Lagrange multipliers, which allows to rigorously adjust the precision in each of the degrees of freedom of the input data according to the amount of influence the given degree of freedom has on the overall distortion. We then present a simple compression method based on Principal Component Analysis, which in combination with the proposed preprocessing achieves significantly better results than current state of the art methods. It allows optimization with respect to various distortion metrics, and we discuss the choice of the metric in two common but distinct scenarios, proposing a perceptually oriented comparison metric based on the relation of the problem at hand to the problem of compression of dynamic meshes.     

Feedback control for rotational movements in feature space

Synthesizing controllers for rotational movements in feature space is an open research problem and is particularly challenging because of the need to precisely regulate the character's global orientation, angular momentum and inertia. This paper presents feature‐based controllers for a wide variety of rotational movements, including cartwheels, dives and flips. We show that the controllers can be made robust to large external disturbances by using a time‐invariant control scheme. The generality of the control laws is demonstrated by providing examples of the flip controller with different apexes, the diving controller with different heights and styles, the cartwheel controller with different speeds and straddle widths, etc. The controllers do not rely on any input motion or offline optimization.     

General and Robust Error Estimation and Reconstruction for Monte Carlo Rendering

Adaptive filtering techniques have proven successful in handling non‐uniform noise in Monte‐Carlo rendering approaches. A recent trend is to choose an optimal filter per pixel from a selection of non spatially‐varying filters. Nonetheless, the best filter choice is difficult to predict in the absence of a reference rendering. Our approach relies on the observation that the reconstruction error is locally smooth for a given filter. Hence, we propose to construct a dense error prediction from a small set of sparse but robust estimates. The filter selection is then formulated as a non‐local optimization problem, which we solve via graph cuts, to avoid visual artifacts due to inconsistent filter choices. Our approach does not impose any restrictions on the used filters, outperforms previous state‐of‐the‐art techniques and provides an extensible framework for future reconstruction techniques.     

TightCCD: Efficient and Robust Continuous Collision Detection using Tight Error Bounds

http://gamma.cs.unc.edu/BSC/ We present a realtime and reliable continuous collision detection (CCD) algorithm between triangulated models that exploits the floating point hardware capability of current CPUs and GPUs. Our formulation is based on Bernstein Sign Classification that takes advantage of the geometry properties of Bernstein basis and Bézier curves to perform Boolean collision queries. We derive tight numerical error bounds on the computations and employ those bounds to design an accurate algorithm using finite‐precision arithmetic. Compared with prior floatingpoint CCD algorithms, our approach eliminates all the false negatives and 90–95% of the false positives. We integrated our algorithm (TightCCD) with physically‐based simulation system and observe speedups in collision queries of 5–15X compared with prior reliable CCD algorithms. Furthermore, we demonstrate its benefits in terms of improving the performance or robustness of cloth simulation systems.     

Self‐similarity for accurate compression of point sampled surfaces

Most surfaces, be it from a fine‐art artifact or a mechanical object, are characterized by a strong self‐similarity. This property finds its source in the natural structures of objects but also in the fabrication processes: regularity of the sculpting technique, or machine tool. In this paper, we propose to exploit the self‐similarity of the underlying shapes for compressing point cloud surfaces which can contain millions of points at a very high precision. Our approach locally resamples the point cloud in order to highlight the self‐similarity of the shape, while remaining consistent with the original shape and the scanner precision. It then uses this self‐similarity to create an ad hoc dictionary on which the local neighborhoods will be sparsely represented, thus allowing for a light‐weight representation of the total surface. We demonstrate the validity of our approach on several point clouds from fine‐arts and mechanical objects, as well as a urban scene. In addition, we show that our approach also achieves a filtering of noise whose magnitude is smaller than the scanner precision.     

BlendForces: A Dynamic Framework for Facial Animation

In this paper we present a new paradigm for the generation and retargeting of facial animation. Like a vast majority of the approaches that have adressed these topics, our formalism is built on blendshapes. However, where prior works have generally encoded facial geometry using a low dimensional basis of these blendshapes, we propose to encode facial dynamics by looking at blendshapes as a basis of forces rather than a basis of shapes. We develop this idea into a dynamic model that naturally combines the blendshapes paradigm with physics‐based techniques for the simulation of deforming meshes. Because it escapes the linear span of the shape basis through time‐integration and physics‐inspired simulation, this approach has a wider expressive range than previous blendshape‐based methods. Its inherent physically‐based formulation also enables the simulation of more advanced physical interactions, such as collision responses on lip contacts.     

Data‐Driven Reconstruction of Human Locomotion Using a Single Smartphone

Generating a visually appealing human motion sequence using low‐dimensional control signals is a major line of study in the motion research area in computer graphics. We propose a novel approach that allows us to reconstruct full body human locomotion using a single inertial sensing device, a smartphone. Smartphones are among the most widely used devices and incorporate inertial sensors such as an accelerometer and a gyroscope. To find a mapping between a full body pose and smartphone sensor data, we perform low dimensional embedding of full body motion capture data, based on a Gaussian Process Latent Variable Model. Our system ensures temporal coherence between the reconstructed poses by using a state decomposition model for automatic phase segmentation. Finally, application of the proposed nonlinear regression algorithm finds a proper mapping between the latent space and the sensor data. Our framework effectively reconstructs plausible 3D locomotion sequences. We compare the generated animation to ground truth data obtained using a commercial motion capture system.     

On‐line real‐time physics‐based predictive motion control with balance recovery

In this paper, we present an on‐line real‐time physics‐based approach to motion control with contact repositioning based on a low‐dimensional dynamics model using example motion data. Our approach first generates a reference motion in run time according to an on‐line user request by transforming an example motion extracted from a motion library. Guided by the reference motion, it repeatedly generates an optimal control policy for a small time window one at a time for a sequence of partially overlapping windows, each covering a couple of footsteps of the reference motion, which supports an on‐line performance. On top of this, our system dynamics and problem formulation allow to derive closed‐form derivative functions by exploiting the low‐dimensional dynamics model together with example motion data. These derivative functions and their sparse structures facilitate a real‐time performance. Our approach also allows contact foot repositioning so as to robustly respond to an external perturbation or an environmental change as well as to perform locomotion tasks such as stepping on stones effectively.     

Multiple Vertex Next Event Estimation for Lighting in dense,forward‐scattering Media

We present a new technique called Multiple Vertex Next Event Estimation, which outperforms current direct lighting techniques in forward scattering, optically dense media with the Henyey‐Greenstein phase function. Instead of a one‐segment connection from a vertex within the medium to the light source, an entire sub path of arbitrary length can be created and we show experimentally that 4–10 segments work best in practice. This is done by perturbing a seed path within the Monte Carlo context. Our technique was integrated in a Monte Carlo renderer, combining random walk path tracing with multiple vertex next event estimation via multiple importance sampling for an unbiased result. We evaluate this new technique against standard next event estimation and show that it significantly reduces noise and increases performance of multiple scattering renderings in highly anisotropic, optically dense media. Additionally, we discuss multiple light sources and performance implications of memory‐heavy heterogeneous media.     

Parallel BVH Construction using Progressive Hierarchical Refinement

We propose a novel algorithm for construction of bounding volume hierarchies (BVHs) for multi‐core CPU architectures. The algorithm constructs the BVH by a divisive top‐down approach using a progressively refined cut of an existing auxiliary BVH. We propose a new strategy for refining the cut that significantly reduces the workload of individual steps of BVH construction. Additionally, we propose a new method for integrating spatial splits into the BVH construction algorithm. The auxiliary BVH is constructed using a very fast method such as LBVH based on Morton codes. We show that the method provides a very good trade‐off between the build time and ray tracing performance. We evaluated the method within the Embree ray tracing framework and show that it compares favorably with the Embree BVH builders regarding build time while maintaining comparable ray tracing speed.     

Ray Classification for Accelerated BVH Traversal

For ray tracing based methods, traversing a hierarchical acceleration data structure takes up a substantial portion of the total rendering time. We propose an additional data structure which cuts off large parts of the hierarchical traversal. We use the idea of ray classification combined with the hierarchical scene representation provided by a bounding volume hierarchy. We precompute short arrays of indices to subtrees inside the hierarchy and use them to initiate the traversal for a given ray class. This arrangement is compact enough to be cache‐friendly, preventing the method from negating its traversal gains by excessive memory traffic. The method is easy to use with existing renderers which we demonstrate by integrating it to the PBRT renderer. The proposed technique reduces the number of traversal steps by 42% on average, saving around 15% of time of finding ray‐scene intersection on average.     

3D Motion Completion in Crowded Scenes

Crowded motions refer to multiple objects moving around and interacting such as crowds, pedestrians and etc. We capture crowded scenes using a depth scanner at video frame rates. Thus, our input is a set of depth frames which sample the scene over time. Processing such data is challenging as it is highly unorganized, with large spatio‐temporal holes due to many occlusions. As no correspondence is given, locally tracking 3D points across frames is hard due to noise and missing regions. Furthermore global segmentation and motion completion in presence of large occlusions is ambiguous and hard to predict. Our algorithm utilizes Gestalt principles of common fate and good continuity to compute motion tracking and completion respectively. Our technique does not assume any pre‐given markers or motion template priors. Our key‐idea is to reduce the motion completion problem to a 1D curve fitting and matching problem which can be solved efficiently using a global optimization scheme. We demonstrate our segmentation and completion method on a variety of synthetic and real world crowded scanned scenes.     

4D video textures for interactive character appearance

4D Video Textures (4DVT) introduce a novel representation for rendering video‐realistic interactive character animation from a database of 4D actor performance captured in a multiple camera studio. 4D performance capture reconstructs dynamic shape and appearance over time but is limited to free‐viewpoint video replay of the same motion. Interactive animation from 4D performance capture has so far been limited to surface shape only. 4DVT is the final piece in the puzzle enabling video‐realistic interactive animation through two contributions: a layered view‐dependent texture map representation which supports efficient storage, transmission and rendering from multiple view video capture; and a rendering approach that combines multiple 4DVT sequences in a parametric motion space, maintaining video quality rendering of dynamic surface appearance whilst allowing high‐level interactive control of character motion and viewpoint. 4DVT is demonstrated for multiple characters and evaluated both quantitatively and through a user‐study which confirms that the visual quality of captured video is maintained. The 4DVT representation achieves >90% reduction in size and halves the rendering cost.     

Merged Multiresolution Hierarchies for Shadow Map Compression

Multiresolution Hierarchies (MH) and Directed Acyclic Graphs (DAG) are two recent approaches for the compression of high‐resolution shadow information. In this paper, we introduce Merged Multiresolution Hierarchies (MMH), a novel data structure that unifies both concepts. An MMH leverages both hierarchical homogeneity exploited in MHs, as well as topological similarities exploited in DAG representations. We propose an efficient hash‐based technique to quickly identify and remove redundant subtree instances in a modified relative MH representation. Our solution remains lossless and significantly improves the compression rate compared to both preceding shadow map compression algorithms, while retaining the full run‐time performance of traditional MH representations.     

GPU Ray Tracing using Irregular Grids

We present a spatial index structure to accelerate ray tracing on GPUs. It is a flat, non‐hierarchical spatial subdivision of the scene into axis aligned cells of varying size. In order to construct it, we first nest an octree into each cell of a uniform grid. We then apply two optimization passes to increase ray traversal performance: First, we reduce the expected cost for ray traversal by merging cells together. This adapts the structure to complex primitive distributions, solving the “teapot in a stadium” problem. Second, we decouple the cell boundaries used during traversal for rays entering and exiting a given cell. This allows us to extend the exiting boundaries over adjacent cells that are either empty or do not contain additional primitives. Now, exiting rays can skip empty space and avoid repeating intersection tests. Finally, we demonstrate that in addition to the fast ray traversal performance, the structure can be rebuilt efficiently in parallel, allowing for ray tracing dynamic scenes.     

Compressed Multiresolution Hierarchies for High‐Quality Precomputed Shadows

The quality of shadow mapping is traditionally limited by texture resolution. We present a novel lossless compression scheme for high‐resolution shadow maps based on precomputed multiresolution hierarchies. Traditional multiresolution trees can compactly represent homogeneous regions of shadow maps at coarser levels, but require many nodes for fine details. By conservatively adapting the depth map, we can significantly reduce the tree complexity. Our proposed method offers high compression rates, avoids quantization errors, exploits coherency along all data dimensions, and is well‐suited for GPU architectures. Our approach can be applied for coherent shadow maps as well, enabling several applications, including high‐quality soft shadows and dynamic lights moving on fixed‐trajectories.     

STAR: Visual Computing in Materials Science

Visual computing has become highly attractive for boosting research endeavors in the materials science domain. Using visual computing, a multitude of different phenomena may now be studied, at various scales, dimensions, or using different modalities. This was simply impossible before. Visual computing techniques provide novel insights in order to understand complex material systems of interest, which is demonstrated by strongly rising number of new approaches, publishing new techniques for materials analysis and simulation. Outlining the proximity of materials science and visual computing, this state of the art report focuses on the intersection of both domains in order to guide research endeavors in this field. We provide a systematic survey on the close interrelations of both fields as well as how they profit from each other. Analyzing the existing body of literature, we review the domain of visual computing supported materials science, starting with the definition of materials science as well as material systems for which visual computing is frequently used. Major tasks for visual computing, visual analysis and visualization in materials sciences are identified, as well as simulation and testing techniques, which are providing the data for the respective analyses. We reviewed the input data characteristics and the direct and derived outputs, the visualization techniques and visual metaphors used, as well as the interactions and analysis workflows employed. All our findings are finally integrated in a cumulative matrix, giving insights about the different interrelations of both domains. We conclude our report with the identification of open high level and low level challenges for future research.     

Clean color: Improving multi‐filament 3D prints

Fused Filament Fabrication is an additive manufacturing process by which a 3D object is created from plastic filament. The filament is pushed through a hot nozzle where it melts. The nozzle deposits plastic layer after layer to create the final object. This process has been popularized by the RepRap community. Several printers feature multiple extruders, allowing objects to be formed from multiple materials or colors. The extruders are mounted side by side on the printer carriage. However, the print quality suffers when objects with color patterns are printed – a disappointment for designers interested in 3D printing their colored digital models. The most severe issue is the oozing of plastic from the idle extruders: Plastics of different colors bleed onto each other giving the surface a smudged aspect, excess strings oozing from the extruder deposit on the surface, and holes appear due to this missing plastic. Fixing this issue is difficult: increasing the printing speed reduces oozing but also degrades surface quality – on large prints the required speed level become impractical. Adding a physical mechanism increases cost and print time as extruders travel to a cleaning station. Instead, we rely on software and exploit degrees of freedom of the printing process. We introduce three techniques that complement each other in improving the print quality significantly. We first reduce the impact of oozing plastic by choosing a better azimuth angle for the printed part. We build a disposable rampart in close proximity of the part, giving the extruders the opportunity to wipe oozing strings and refill with hot plastic. We finally introduce a toolpath planner avoiding and hiding most of the defects due to oozing, and seamlessly integrating the rampart. We demonstrate our technique on several challenging multiple color prints, and show that our tool path planner improves the surface finish of single color prints as well.