Large‐Scale Integer Linear Programming for Orientation Preserving 3D Shape Matching

We study an algorithmic framework for computing an elastic orientation‐preserving matching of non‐rigid 3D shapes. We outline an Integer Linear Programming formulation whose relaxed version can be minimized globally in polynomial time. Because of the high number of optimization variables, the key algorithmic challenge lies in efficiently solving the linear program. We present a performance analysis of several Linear Programming algorithms on our problem. Furthermore, we introduce a multiresolution strategy which allows the matching of higher resolution models.     

In‐situ Sampling of a Large‐Scale Particle Simulation for Interactive Visualization and Analysis

We describe a simulation‐time random sampling of a large‐scale particle simulation, the RoadRunner Universe MC³ cosmological simulation, for interactive post‐analysis and visualization. Simulation data generation rates will continue to be far greater than storage bandwidth rates by many orders of magnitude. This implies that only a very small fraction of data generated by a simulation can ever be stored and subsequently post‐analyzed. The limiting factors in this situation are similar to the problem in many population surveys: there aren't enough human resources to query a large population. To cope with the lack of resources, statistical sampling techniques are used to create a representative data set of a large population. Following this analogy, we propose to store a simulation‐time random sampling of the particle data for post‐analysis, with level‐of‐detail organization, to cope with the bottlenecks. A sample is stored directly from the simulation in a level‐of‐detail format for post‐visualization and analysis, which amortizes the cost of post‐processing and reduces workflow time. Additionally by sampling during the simulation, we are able to analyze the entire particle population to record full population statistics and quantify sample error.     

Inverse Procedural Modelling of Trees

Procedural tree models have been popular in computer graphics for their ability to generate a variety of output trees from a set of input parameters and to simulate plant interaction with the environment for a realistic placement of trees in virtual scenes. However, defining such models and their parameters is a difficult task. We propose an inverse modelling approach for stochastic trees that takes polygonal tree models as input and estimates the parameters of a procedural model so that it produces trees similar to the input. Our framework is based on a novel parametric model for tree generation and uses Monte Carlo Markov Chains to find the optimal set of parameters. We demonstrate our approach on a variety of input models obtained from different sources, such as interactive modelling systems, reconstructed scans of real trees and developmental models.     

Interactive Modeling of City Layouts using Layers of Procedural Content

In this paper, we present new solutions for the interactive modeling of city layouts that combine the power of procedural modeling with the flexibility of manual modeling. Procedural modeling enables us to quickly generate large city layouts, while manual modeling allows us to hand‐craft every aspect of a city. We introduce transformation and merging operators for both topology preserving and topology changing transformations based on graph cuts. In combination with a layering system, this allows intuitive manipulation of urban layouts using operations such as drag and drop, translation, rotation etc. In contrast to previous work, these operations always generate valid, i.e., intersection‐free layouts. Furthermore, we introduce anchored assignments to make sure that modifications are persistent even if the whole urban layout is regenerated.     

Interactive Procedural Modelling of Coherent Waterfall Scenes

Combining procedural generation and user control is a fundamental challenge for the interactive design of natural scenery. This is particularly true for modelling complex waterfall scenes where, in addition to taking charge of geometric details, an ideal tool should also provide a user with the freedom to shape the running streams and falls, while automatically maintaining physical plausibility in terms of flow network, embedding into the terrain, and visual aspects of the waterfalls. We present the first solution for the interactive procedural design of coherent waterfall scenes. Our system combines vectorial editing, where the user assembles elements to create a waterfall network over an existing terrain, with a procedural model that parametrizes these elements from hydraulic exchanges; enforces consistency between the terrain and the flow; and generates detailed geometry, animated textures and shaders for the waterfalls and their surroundings. The tool is interactive, yielding visual feedback after each edit.     

Continuum Traffic Simulation

We present a novel method for the synthesis and animation of realistic traffic flows on large‐scale road networks. Our technique is based on a continuum model of traffic flow we extend to correctly handle lane changes and merges, as well as traffic behaviors due to changes in speed limit. We demonstrate how our method can be applied to the animation of many vehicles in a large‐scale traffic network at interactive rates and show that our method can simulate believable traffic flows on publicly‐available, real‐world road data. We furthermore demonstrate the scalability of this technique on many‐core systems.     

Particle Level Set Advection for the Interactive Visualization of Unsteady 3D Flow

Typically, flow volumes are visualized by defining their boundary as iso‐surface of a level set function. Grid‐based level sets offer a good global representation but suffer from numerical diffusion of surface detail, whereas particle‐based methods preserve details more accurately but introduce the problem of unequal global representation. The particle level set (PLS) method combines the advantages of both approaches by interchanging the information between the grid and the particles. Our work demonstrates that the PLS technique can be adapted to volumetric dye advection via streak volumes, and to the visualization by time surfaces and path volumes. We achieve this with a modified and extended PLS, including a model for dye injection. A new algorithmic interpretation of PLS is introduced to exploit the efficiency of the GPU, leading to interactive visualization. Finally, we demonstrate the high quality and usefulness of PLS flow visualization by providing quantitative results on volume preservation and by discussing typical applications of 3D flow visualization.     

Multi‐Scale Geometry Interpolation

Interpolating vertex positions among triangle meshes with identical vertex‐edge graphs is a fundamental part of many geometric modelling systems. Linear vertex interpolation is robust but fails to preserve local shape. Most recent approaches identify local affine transformations for parts of the mesh, model desired interpolations of the affine transformations, and then optimize vertex positions to conform with the desired transformations. However, the local interpolation of the rotational part is non‐trivial for more than two input configurations and ambiguous if the meshes are deformed significantly. We propose a solution to the vertex interpolation problem that starts from interpolating the local metric (edge lengths) and mean curvature (dihedral angles) and makes consistent choices of local affine transformations using shape matching applied to successively larger parts of the mesh. The local interpolation can be applied to any number of input vertex configurations and due to the hierarchical scheme for generating consolidated vertex positions, the approach is fast and can be applied to very large meshes.     

Over Two Decades of Integration‐Based,Geometric Flow Visualization

With ever increasing computing power, it is possible to process ever more complex fluid simulations. However, a gap between data set sizes and our ability to visualize them remains. This is especially true for the field of flow visualization, which deals with large, time‐dependent, multivariate simulation data sets. In this paper, geometry‐based flow visualization techniques form the focus of discussion. Geometric flow visualization methods place discrete objects in the velocity field whose characteristics reflect the underlying properties of the flow. A great amount of progress has been made in this field over the last two decades. However, a number of challenges remain, including placement, speed of computation and perception. In this survey, we review and classify geometric flow visualization literature according to the most important challenges when considering such a visualization, a central theme being the seeding algorithm upon which they are based. This paper details our investigation into these techniques with discussions on their applicability and their relative merits and drawbacks. The result is an up‐to‐date overview of the current state‐of‐the‐art that highlights both solved and unsolved problems in this rapidly evolving branch of research. It also serves as a concise introduction to the field of flow visualization research.     

Multi‐Resolution Cloth Simulation

We propose a novel, multi‐resolution method to efficiently perform large‐scale cloth simulation. Our cloth simulation method is based on a triangle‐based energy model constructed from a cloth mesh. We identify that solutions of the linear system of cloth simulation are smooth in certain regions of the cloth mesh and solve the linear system on those regions in a reduced solution space. Then we reconstruct the original solutions by performing a simple interpolation from solutions computed in the reduced space. In order to identify regions where solutions are smooth, we propose simplification metrics that consider stretching, shear, and bending forces, as well as geometric collisions. Our multi‐resolution method can be applied to many existing cloth simulation methods, since our method works on a general linear system. In order to demonstrate benefits of our method, we apply our method into four large‐scale cloth benchmarks that consist of tens or hundreds of thousands of triangles. Because of the reduced computations, we achieve a performance improvement by a factor of up to one order of magnitude, with a little loss of simulation quality.     

Interactive Modeling and Authoring of Climbing Plants

We present a novel system for the interactive modeling of developmental climbing plants with an emphasis on efficient control and plausible physics response. A plant is represented by a set of connected anisotropic particles that respond to the surrounding environment and to their inner state. Each particle stores biological and physical attributes that drive growth and plant adaptation to the environment such as light sensitivity, wind interaction, and physical obstacles. This representation allows for the efficient modeling of external effects that can be induced at any time without prior analysis of the plant structure. In our framework we exploit this representation to provide powerful editing capabilities that allow to edit a plant with respect to its structure and its environment while maintaining a biologically plausible appearance. Moreover, we couple plants with Lagrangian fluid dynamics and model advanced effects, such as the breaking and bending of branches. The user can thus interactively drag and prune branches or seed new plants in dynamically changing environments. Our system runs in real‐time and supports up to 20 plant instances with 25k branches in parallel. The effectiveness of our approach is demonstrated through a number of interactive experiments, including modeling and animation of different species of climbing plants on complex support structures.     

Non‐Rigid Registration Under Isometric Deformations

We present a robust and efficient algorithm for the pairwise non‐rigid registration of partially overlapping 3D surfaces. Our approach treats non‐rigid registration as an optimization problem and solves it by alternating between correspondence and deformation optimization. Assuming approximately isometric deformations, robust correspondences are generated using a pruning mechanism based on geodesic consistency. We iteratively learn an appropriate deformation discretization from the current set of correspondences and use it to update the correspondences in the next iteration. Our algorithm is able to register partially similar point clouds that undergo large deformations, in just a few seconds. We demonstrate the potential of our algorithm in various applications such as example based articulated segmentation, and shape interpolation.     

Semi‐Supervised Learning in Reconstructed Manifold Space for 3D Caricature Generation

Recently, automatic 3D caricature generation has attracted much attention from both the research community and the game industry. Machine learning has been proven effective in the automatic generation of caricatures. However, the lack of 3D caricature samples makes it challenging to train a good model. This paper addresses this problem by two steps. First, the training set is enlarged by reconstructing 3D caricatures. We reconstruct 3D caricatures based on some 2D caricature samples with a Principal Component Analysis (PCA)‐based method. Secondly, between the 2D real faces and the enlarged 3D caricatures, a regressive model is learnt by the semi‐supervised manifold regularization (MR) method. We then predict 3D caricatures for 2D real faces with the learnt model. The experiments show that our novel approach synthesizes the 3D caricature more effectively than traditional methods. Moreover, our system has been applied successfully in a massive multi‐user educational game to provide human‐like avatars.     

4D MRI Flow Coupled to Physics‐Based Fluid Simulation for Blood‐Flow Visualization

Modern MRI measurements deliver volumetric and time‐varying blood‐flow data of unprecedented quality. Visual analysis of these data potentially leads to a better diagnosis and risk assessment of various cardiovascular diseases. Recent advances have improved the speed and quality of the imaging data considerably. Nevertheless, the data remains compromised by noise and a lack of spatiotemporal resolution. Besides imaging data, also numerical simulations are employed. These are based on mathematical models of specific features of physical reality. However, these models require realistic parameters and boundary conditions based on measurements. We propose to use data assimilation to bring measured data and physically‐based simulation together, and to harness the mutual benefits. The accuracy and noise robustness of the coupled approach is validated using an analytic flow field. Furthermore, we present a comparative visualization that conveys the differences between using conventional interpolation and our coupled approach.     

Exact and Robust (Self‐)Intersections for Polygonal Meshes

We present a new technique to implement operators that modify the topology of polygonal meshes at intersections and self‐intersections. Depending on the modification strategy, this effectively results in operators for Boolean combinations or for the construction of outer hulls that are suited for mesh repair tasks and accurate mesh‐based front tracking of deformable materials that split and merge. By combining an adaptive octree with nested binary space partitions (BSP), we can guarantee exactness (= correctness) and robustness (= completeness) of the algorithm while still achieving higher performance and less memory consumption than previous approaches. The efficiency and scalability in terms of runtime and memory is obtained by an operation localization scheme. We restrict the essential computations to those cells in the adaptive octree where intersections actually occur. Within those critical cells, we convert the input geometry into a plane‐based BSP‐representation which allows us to perform all computations exactly even with fixed precision arithmetics. We carefully analyze the precision requirements of the involved geometric data and predicates in order to guarantee correctness and show how minimal input mesh quantization can be used to safely rely on computations with standard floating point numbers. We properly evaluate our method with respect to precision, robustness, and efficiency.     

Example‐Driven Procedural Urban Roads

Synthesizing and exploring large‐scale realistic urban road networks is beneficial to 3D content creation, traffic animation and urban planning. In this paper, we present an interactive tool that allows untrained users to design roads with complex realistic details and styles. Roads are generated by growing a geometric graph. During a sketching phase, the user specifies the target area and the examples. During a growing phase, two types of growth are effectively applied to generate roads in the target area; example‐based growth uses patches extracted from the source example to generate roads that preserve some interesting structures in the example road networks; procedural‐based growth uses the statistical information of the source example while effectively adapting the roads to the underlying terrain and the already generated roads. User‐specified warping, blending and interpolation operations are used at will to produce new road network designs that are inspired by the examples. Finally, our method computes city blocks, individual parcels and plausible building and tree geometries. We have used our approach to create road networks covering up to 200 and containing over 3500 km of roads.     

Woodification: User‐Controlled Cambial Growth Modeling

We present a botanical simulation of secondary (cambial) tree growth coupled to a physical cracking simulation of its bark. Whereas level set growth would use a fixed resolution voxel grid, our system extends the deformable simplicial complex (DSC), supporting new biological growth functions robustly on any surface polygonal mesh with adaptive subdivision, collision detection and topological control. We extend the DSC with temporally coherent texturing, and surface cracking with a user‐controllable biological model coupled to the stresses introduced by the cambial growth model.     

Designing Quad‐dominant Meshes with Planar Faces

We study the combined problem of approximating a surface by a quad mesh (or quad‐dominant mesh) which on the one hand has planar faces, and which on the other hand is aesthetically pleasing and has evenly spaced vertices. This work is motivated by applications in freeform architecture and leads to a discussion of fields of conjugate directions in surfaces, their singularities and indices, their optimization and their interactive modeling. The actual meshing is performed by means of a level set method which is capable of handling combinatorial singularities, and which can deal with planarity, smoothness, and spacing issues.     

Reconstructing Animated Meshes from Time‐Varying Point Clouds

In this paper, we describe a novel approach for the reconstruction of animated meshes from a series of time‐deforming point clouds. Given a set of unordered point clouds that have been captured by a fast 3‐D scanner, our algorithm is able to compute coherent meshes which approximate the input data at arbitrary time instances. Our method is based on the computation of an implicit function in ?⁴ that approximates the time‐space surface of the time‐varying point cloud. We then use the four‐dimensional implicit function to reconstruct a polygonal model for the first time‐step. By sliding this template mesh along the time‐space surface in an as‐rigid‐as‐possible manner, we obtain reconstructions for further time‐steps which have the same connectivity as the previously extracted mesh while recovering rigid motion exactly. The resulting animated meshes allow accurate motion tracking of arbitrary points and are well suited for animation compression. We demonstrate the qualities of the proposed method by applying it to several data sets acquired by real‐time 3‐D scanners.