Shape Matching via Quotient Spaces

We introduce a novel method for non‐rigid shape matching, designed to address the symmetric ambiguity problem present when matching shapes with intrinsic symmetries. Unlike the majority of existing methods which try to overcome this ambiguity by sampling a set of landmark correspondences, we address this problem directly by performing shape matching in an appropriate quotient space, where the symmetry has been identified and factored out. This allows us to both simplify the shape matching problem by matching between subspaces, and to return multiple solutions with equally good dense correspondences. Remarkably, both symmetry detection and shape matching are done without establishing any landmark correspondences between either points or parts of the shapes. This allows us to avoid an expensive combinatorial search present in most intrinsic symmetry detection and shape matching methods. We compare our technique with state‐of‐the‐art methods and show that superior performance can be achieved both when the symmetry on each shape is known and when it needs to be estimated.     

Scale Normalization for Isometric Shape Matching

We address the scale problem inherent to isometric shape correspondence in a combinatorial matching framework. We consider a particular setting of the general correspondence problem where one of the two shapes to be matched is an isometric (or nearly isometric) part of the other up to an arbitrary scale. We resolve the scale ambiguity by finding a coarse matching between shape extremities based on a novel scale‐invariant isometric distortion measure. The proposed algorithm also supports (partial) dense matching, that alleviates the symmetric flip problem due to initial coarse sampling. We test the performance of our matching algorithm on several shape datasets in comparison to state of the art. Our method proves useful, not only for partial matching, but also for complete matching of semantically similar hybrid shape pairs whose maximum geodesic distances may not be compatible, a case that would fail most of the conventional isometric shape matchers.     

State‐of‐the‐Art in GPU‐Based Large‐Scale Volume Visualization

This survey gives an overview of the current state of the art in GPU techniques for interactive large‐scale volume visualization. Modern techniques in this field have brought about a sea change in how interactive visualization and analysis of giga‐, tera‐ and petabytes of volume data can be enabled on GPUs. In addition to combining the parallel processing power of GPUs with out‐of‐core methods and data streaming, a major enabler for interactivity is making both the computational and the visualization effort proportional to the amount and resolution of data that is actually visible on screen, i.e. ‘output‐sensitive’ algorithms and system designs. This leads to recent output‐sensitive approaches that are ‘ray‐guided’, ‘visualization‐driven’ or ‘display‐aware’. In this survey, we focus on these characteristics and propose a new categorization of GPU‐based large‐scale volume visualization techniques based on the notions of actual output‐resolution visibility and the current working set of volume bricks—the current subset of data that is minimally required to produce an output image of the desired display resolution. Furthermore, we discuss the differences and similarities of different rendering and data traversal strategies in volume rendering by putting them into a common context—the notion of address translation. For our purposes here, we view parallel (distributed) visualization using clusters as an orthogonal set of techniques that we do not discuss in detail but that can be used in conjunction with what we present in this survey.     

Mesh Decomposition with Cross‐Boundary Brushes

We present a new intuitive UI, which we call cross‐boundary brushes, for interactive mesh decomposition. The user roughly draws one or more strokes across a desired cut and our system automatically returns a best cut running through all the strokes. By the different natures of part components (i.e., semantic parts) and patch components (i.e., flatter surface patches) in general models, we design two corresponding brushes: part‐brush and patch‐brush. These two types of brushes share a common user interface, enabling easy switch between them. The part‐brush executes a cut along an isoline of a harmonic field driven by the user‐specified strokes. We show that the inherent smoothness of the harmonic field together with a carefully designed isoline selection scheme lead to segmentation results that are insensitive to noise, pose, tessellation and variation in user's strokes. Our patch‐brush uses a novel facet‐based surface metric that alleviates sensitivity to noise and fine details common in region‐growing algorithms. Extensive experimental results demonstrate that our cutting tools can produce user‐desired segmentations for a wide variety of models even with single strokes. We also show that our tools outperform the state‐of‐art interactive segmentation tools in terms of ease of use and segmentation quality.     

Data‐Driven Shape Interpolation and Morphing Editing

Shape interpolation has many applications in computer graphics such as morphing for computer animation. In this paper, we propose a novel data‐driven mesh interpolation method. We adapt patch‐based linear rotational invariant coordinates to effectively represent deformations of models in a shape collection, and utilize this information to guide the synthesis of interpolated shapes. Unlike previous data‐driven approaches, we use a rotation/translation invariant representation which defines the plausible deformations in a global continuous space. By effectively exploiting the knowledge in the shape space, our method produces realistic interpolation results at interactive rates, outperforming state‐of‐the‐art methods for challenging cases. We further propose a novel approach to interactive editing of shape morphing according to the shape distribution. The user can explore the morphing path and select example models intuitively and adjust the path with simple interactions to edit the morphing sequences. This provides a useful tool to allow users to generate desired morphing with little effort. We demonstrate the effectiveness of our approach using various examples.     

Approximate on‐Surface Distance Computation using Quasi‐Developable Charts

There is a vast number of applications that require distance field computation over triangular meshes. State‐of‐the‐art algorithms have quadratic or sub‐quadratic worst‐case complexity, making them impractical for interactive applications. While most of the research on this subject has been focused on reducing the computation complexity of the algorithms, in this work we propose an approximate algorithm that achieves similar results working in lower resolutions of the input meshes. The creation of lower resolution meshes is the essence of our proposal. The idea is to identify regions on the input mesh that can be unfolded into planar regions with minimal area distortion (i.e. quasi‐developable charts). Once charts are computed, their interior is re‐triangulated to reduce the number of triangles, which results in a collection of simplified charts that we call a base mesh. Due to the properties of quasi‐developable regions, we are able to compute distance fields over the base mesh instead of over the input mesh. This reduces the memory footprint and data processed for distance computations, which is the bottleneck of these algorithms. We present results that are one order of magnitude faster than current exact solutions, with low approximation errors.     

Optimizing Structure Preserving Embedded Deformation for Resizing Images and Vector Art

Smart deformation and warping tools play an important part in modern day geometric modeling systems. They allow existing content to be stretched or scaled while preserving visually salient information. To date, these techniques have primarily focused on preserving local shape details, not taking into account important global structures such as symmetry and line features. In this work we present a novel framework that can be used to preserve the global structure in images and vector art. Such structures include symmetries and the spatial relations in shapes and line features in an image. Central to our method is a new formulation of preserving structure as an optimization problem. We use novel optimization strategies to achieve the interactive performance required by modern day modeling applications. We demonstrate the effectiveness of our framework by performing structure preservation deformation of images and complex vector art at interactive rates.     

Interactive Physics‐based Ink Splattering Art Creation

This paper presents an interactive system for ink splattering, a form of abstract art that artists splat ink onto the canvas. The default input device of our system is a pressure‐sensitive 2D stylus, the most common sketching tool for digital artists, and we propose two interaction mode: ink‐flicking mode and ink‐dripping mode , that are designed to be analogous to the artistic techniques of ink splattering in real world. The core of our ink splattering system is a novel three‐stage ink splattering framework that simulates the physics‐based interaction of ink with different mediums including brush heads, air and paper. We have implemented the physical engine in CUDA and the whole simulation process runs at interactive speed.     

Fast and Robust Normal Estimation for Point Clouds with Sharp Features

This paper presents a new method for estimating normals on unorganized point clouds that preserves sharp features. It is based on a robust version of the Randomized Hough Transform (RHT). We consider the filled Hough transform accumulator as an image of the discrete probability distribution of possible normals. The normals we estimate corresponds to the maximum of this distribution. We use a fixed‐size accumulator for speed, statistical exploration bounds for robustness, and randomized accumulators to prevent discretization effects. We also propose various sampling strategies to deal with anisotropy, as produced by laser scans due to differences of incidence. Our experiments show that our approach offers an ideal compromise between precision, speed, and robustness: it is at least as precise and noise‐resistant as state‐of‐the‐art methods that preserve sharp features, while being almost an order of magnitude faster. Besides, it can handle anisotropy with minor speed and precision losses.     

Learnt Real‐time Meshless Simulation

We present a new real‐time approach to simulate deformable objects using a learnt statistical model to achieve a high degree of realism. Our approach improves upon state‐of‐the‐art interactive shape‐matching meshless simulation methods by not only capturing important nuances of an object's kinematics but also of its dynamic texture variation. We are able to achieve this in an automated pipeline from data capture to simulation. Our system allows for the capture of idiosyncratic characteristics of an object's dynamics which for many simulations (e.g. facial animation) is essential. We allow for the plausible simulation of mechanically complex objects without knowledge of their inner workings. The main idea of our approach is to use a flexible statistical model to achieve a geometrically‐driven simulation that allows for arbitrarily complex yet easily learned deformations while at the same time preserving the desirable properties (stability, speed and memory efficiency) of current shape‐matching simulation systems. The principal advantage of our approach is the ease with which a pseudo‐mechanical model can be learned from 3D scanner data to yield realistic animation. We present examples of non‐trivial biomechanical objects simulated on a desktop machine in real‐time, demonstrating superior realism over current geometrically motivated simulation techniques.     

State of the Art in Transfer Functions for Direct Volume Rendering

A central topic in scientific visualization is the transfer function (TF) for volume rendering. The TF serves a fundamental role in translating scalar and multivariate data into color and opacity to express and reveal the relevant features present in the data studied. Beyond this core functionality, TFs also serve as a tool for encoding and utilizing domain knowledge and as an expression for visual design of material appearances. TFs also enable interactive volumetric exploration of complex data. The purpose of this state‐of‐the‐art report (STAR) is to provide an overview of research into the various aspects of TFs, which lead to interpretation of the underlying data through the use of meaningful visual representations. The STAR classifies TF research into the following aspects: dimensionality, derived attributes, aggregated attributes, rendering aspects, automation, and user interfaces. The STAR concludes with some interesting research challenges that form the basis of an agenda for the development of next generation TF tools and methodologies.     

Topology Aware Data‐Driven Inverse Kinematics

Creating realistic human movement is a time consuming and labour intensive task. The major difficulty is that the user has to edit individual joints while maintaining an overall realistic and collision free posture. Previous research suggests the use of data‐driven inverse kinematics, such that one can focus on the control of a few joints, while the system automatically composes a natural posture. However, as a common problem of kinematics synthesis, penetration of body parts is difficult to avoid in complex movements. In this paper, we propose a new data‐driven inverse kinematics framework that conserves the topology of the synthesizing postures. Our system monitors and regulates the topology changes using the Gauss Linking Integral (GUI), such that penetration can be efficiently prevented. As a result, complex motions with tight body movements, as well as those involving interaction with external objects, can be simulated with minimal manual intervention. Experimental results show that using our system, the user can create high quality human motion in real‐time by controlling a few joints using a mouse or a multi‐touch screen. The movement generated is both realistic and penetration free. Our system is best applied for interactive motion design in computer animations and games.     

SAFE: Structure‐aware facade editing

Many man‐made objects, in particular building facades, exhibit dominant structural relations such as symmetry and regularity. When editing these shapes, a common objective is to preserve these relations. However, often there are numerous plausible editing results that all preserve the desired structural relations of the input, creating ambiguity. We propose an interactive facade editing framework that explores this structural ambiguity. We first analyze the input in a semi‐automatic manner to detect different groupings of the facade elements and the relations among them. We then provide an incremental editing process where a set of variations that preserve the detected relations in a particular grouping are generated at each step. Starting from one input example, our system can quickly generate various facade configurations.     

Data‐guided Model Predictive Control Based on Smoothed Contact Dynamics

In this paper, we propose an efficient data‐guided method based on Model Predictive Control (MPC) to synthesize a full‐body motion. Guided by a reference motion, our method repeatedly plans the full‐body motion to produce an optimal control policy for predictive control while sliding the fixed‐span window along the time axis. Based on this policy, the method computes the joint torques of a character at every time step. Together with contact forces and external perturbations if there are any, the joint torques are used to update the state of the character. Without including the contact forces in the control vector, our formulation of the trajectory optimization problem enables automatic adjustment of contact timings and positions for balancing in response to environmental changes and external perturbations. For efficiency, we adopt derivative‐based trajectory optimization on top of state‐of‐the‐art smoothed contact dynamics. Use of derivatives enables our method to run much faster than the existing sampling‐based methods. In order to further accelerate the performance of MPC, we propose efficient numerical differentiation of the system dynamics of a full‐body character based on two schemes: data reuse and data interpolation. The former scheme exploits data dependency to reuse physical quantities of the system dynamics at near‐by time points. The latter scheme allows the use of derivatives at sparse sample points to interpolate those at other time points in the window. We further accelerate evaluation of the system dynamics by exploiting the sparsity of physical quantities such as Jacobian matrix resulting from the tree‐like structure of the articulated body. Through experiments, we show that the proposed method efficiently can synthesize realistic motions such as locomotion, dancing, gymnastic motions, and martial arts at interactive rates using moderate computing resources.     

DTI in Context: Illustrating Brain Fiber Tracts In Situ

We present an interactive illustrative visualization method inspired by traditional pen‐and‐ink illustration styles. Specifically, we explore how to provide context around DTI fiber tracts in the form of surfaces of the brain, the skull, or other objects such as tumors. These contextual surfaces are derived from either segmentation data or generated using interactive iso‐surface extraction and are rendered with a flexible, slice‐based hatching technique, controlled with ambient occlusion. This technique allows us to produce a consistent and frame‐coherent appearance with precise control over the lines. In addition, we provide context through cutting planes onto which we render gray matter with stippling. Together, our methods not only facilitate the interactive exploration and illustration of brain fibers within their anatomical context but also allow us to produce high‐quality images for print reproduction. We provide evidence for the success of our approach with an informal evaluation with domain experts.     

Automatic Animation for Time‐Varying Data Visualization

This paper presents a digital storytelling approach that generates automatic animations for time‐varying data visualization. Our approach simulates the composition and transition of storytelling techniques and synthesizes animations to describe various event features. Specifically, we analyze information related to a given event and abstract it as an event graph, which represents data features as nodes and event relationships as links. This graph embeds a tree‐like hierarchical structure which encodes data features at different scales. Next, narrative structures are built by exploring starting nodes and suitable search strategies in this graph. Different stages of narrative structures are considered in our automatic rendering parameter decision process to generate animations as digital stories. We integrate this animation generation approach into an interactive exploration process of time‐varying data, so that more comprehensive information can be provided in a timely fashion. We demonstrate with a storm surge application that our approach allows semantic visualization of time‐varying data and easy animation generation for users without special knowledge about the underlying visualization techniques.     

Geometry and Attribute Compression for Voxel Scenes

Voxel‐based approaches are today's standard to encode volume data. Recently, directed acyclic graphs (DAGs) were successfully used for compressing sparse voxel scenes as well, but they are restricted to a single bit of (geometry) information per voxel. We present a method to compress arbitrary data, such as colors, normals, or reflectance information. By decoupling geometry and voxel data via a novel mapping scheme, we are able to apply the DAG principle to encode the topology, while using a palette‐based compression for the voxel attributes, leading to a drastic memory reduction. Our method outperforms existing state‐of‐the‐art techniques and is well‐suited for GPU architectures. We achieve real‐time performance on commodity hardware for colored scenes with up to 17 hierarchical levels (a 128K³voxel resolution), which are stored fully in core.     

Evaluation of Cluster Identification Performance for Different PCP Variants

Parallel coordinate plots (PCPs) are a well‐known visualization technique for viewing multivariate data. In the past, various visual modifications to PCPs have been proposed to facilitate tasks such as correlation and cluster identification, to reduce visual clutter, and to increase their information throughput. Most modifications pertain to the use of color and opacity, smooth curves, or the use of animation. Although many of these seem valid improvements, only few user studies have been performed to investigate this, especially with respect to cluster identification. We performed a user study to evaluate cluster identification performance – with respect to response time and correctness – of nine PCP variations, including standard PCPs. To generate the variations, we focused on covering existing techniques as well as possible while keeping testing feasible. This was done by adapting and merging techniques, which led to the following novel variations. The first is an effective way of embedding scatter plots into PCPs. The second is a technique for highlighting fuzzy clusters based on neighborhood density. The third is a spline‐based drawing technique to reduce ambiguity. The last is a pair of animation schemes for PCP rotation. We present an overview of the tested PCP variations and the results of our study. The most important result is that a fair number of the seemingly valid improvements, with the exception of scatter plots embedded into PCPs, do not result in significant performance gains.     

Guided Volume Editing based on Histogram Dissimilarity

Segmentation of volumetric data is an important part of many analysis pipelines, but frequently requires manual inspection and correction. While plenty of volume editing techniques exist, it remains cumbersome and errorprone for the user to find and select appropriate regions for editing. We propose an approach to improve volume editing by detecting potential segmentation defects while considering the underlying structure of the object of interest. Our method is based on a novel histogram dissimilarity measure between individual regions, derived from structural information extracted from the initial segmentation. Based on this information, our interactive system guides the user towards potential defects, provides integrated tools for their inspection, and automatically generates suggestions for their resolution. We demonstrate that our approach can reduce interaction effort and supports the user in a comprehensive investigation for high‐quality segmentations.     

BetweenIT: An Interactive Tool for Tight Inbetweening

The generation of inbetween frames that interpolate a given set of key frames is a major component in the production of a 2D feature animation. Our objective is to considerably reduce the cost of the inbetweening phase by offering an intuitive and effective interactive environment that automates inbetweening when possible while allowing the artist to guide, complement, or override the results. Tight inbetweens, which interpolate similar key frames, are particularly time‐consuming and tedious to draw. Therefore, we focus on automating these high‐precision and expensive portions of the process. We have designed a set of user‐guided semi‐automatic techniques that fit well with current practice and minimize the number of required artist‐gestures. We present a novel technique for stroke interpolation from only two keys which combines a stroke motion constructed from logarithmic spiral vertex trajectories with a stroke deformation based on curvature averaging and twisting warps. We discuss our system in the context of a feature animation production environment and evaluate our approach with real production data.