An Efficient Algorithm for Determining an Aesthetic Shape Connecting Unorganized 2D Points

We present anefficient algorithm for determining an aesthetically pleasing shape boundary connecting all the points in a given unorganized set of 2D points, with no other information than point coordinates. By posing shape construction as a minimisation problem which follows the Gestalt laws, our desired shape is non‐intersecting, interpolates all points and minimizes a criterion related to these laws. The basis for our algorithm is an initial graph, an extension of the Euclidean minimum spanning tree but with no leaf nodes, called as the minimum boundary complex . and can be expressed similarly by parametrizing a topological constraint. A close approximation of , termed can be computed fast using a greedy algorithm. is then transformed into a closed interpolating boundary in two steps to satisfy ’s topological and minimization requirements. Computing exactly is an NP (Non‐Polynomial)‐hard problem, whereas is computed in linearithmic time. We present many examples showing considerable improvement over previous techniques, especially for shapes with sharp corners. Source code is available online.     

Enhancing Bayesian Estimators for Removing Camera Shake

The aim of removing camera shake is to estimate a sharp version x from a shaken image y when the blur kernel k is unknown. Recent research on this topic evolved through two paradigms called and . only solves for k by marginalizing the image prior, while recovers both x and k by selecting the mode of the posterior distribution. This paper first systematically analyses the latent limitations of these two estimators through Bayesian analysis. We explain the reason why it is so difficult for image statistics to solve the previously reported failure. Then we show that the leading methods, which depend on efficient prediction of large step edges, are not robust to natural images due to the diversity of edges. , although much more robust to diverse edges, is constrained by two factors: the prior variation over different images, and the ratio between image size and kernel size. To overcome these limitations, we introduce an inter‐scale prior prediction scheme and a principled mechanism for integrating the sharpening filter into . Both qualitative results and extensive quantitative comparisons demonstrate that our algorithm outperforms state‐of‐the‐art methods.     

River Networks for Instant Procedural Planets

Realistic terrain models are required in many applications, especially in computer games. Commonly, procedural models are applied to generate the corresponding models and let users experience a wide variety of new environments. Existing algorithms generate landscapes immediately with view‐dependent resolution and without preprocessing. Unfortunately, landscapes generated by such algorithms lack river networks and therefore appear unnatural. Algorithms that integrate realistic river networks are computationally expensive and cannot be used to generate a locally adaptive high resolution landscape during a fly‐through. In this paper, we propose a novel algorithm to generate realistic river networks. Our procedural algorithm creates complete planets and landscapes with realistic river networks within seconds. It starts with a coarse base geometry of a planet without further preprocessing and user intervention. By exploiting current graphics hardware, the proposed algorithm is able to generate adaptively refined landscape geometry during fly‐throughs.     

Scalable Partitioning for Parallel Position Based Dynamics

We introduce a practical partitioning technique designed for parallelizing Position Based Dynamics, and exploiting the ubiquitous multi‐core processors present in current commodity GPUs. The input is a set of particles whose dynamics is influenced by spatial constraints. In the initialization phase, we build a graph in which each node corresponds to a constraint and two constraints are connected by an edge if they influence at least one common particle. We introduce a novel greedy algorithm for inserting additional constraints (phantoms) in the graph such that the resulting topology is ‐colourable, where is an arbitrary number. We color the graph, and the constraints with the same color are assigned to the same partition. Then, the set of constraints belonging to each partition is solved in parallel during the animation phase. We demonstrate this by using our partitioning technique; the performance hit caused by the GPU kernel calls is significantly decreased, leaving unaffected the visual quality, robustness and speed of serial position based dynamics.     

Turning a Digital Camera into an Absolute 2D Tele‐Colorimeter

We present a simple and effective technique for absolute colorimetric camera characterization, invariant to changes in exposure/aperture and scene irradiance, suitable in a wide range of applications including image‐based reflectance measurements, spectral pre‐filtering and spectral upsampling for rendering, to improve colour accuracy in high dynamic range imaging. Our method requires a limited number of acquisitions, an off‐the‐shelf target and a commonly available projector, used as a controllable light source, other than the reflected radiance to be known. The characterized camera can be effectively used as a 2D tele‐colorimeter, providing the user with an accurate estimate of the distribution of luminance and chromaticity in a scene, without requiring explicit knowledge of the incident lighting power spectra. We validate the approach by comparing our estimated absolute tristimulus values (XYZ data in ) with the measurements of a professional 2D tele‐colorimeter, for a set of scenes with complex geometry, spatially varying reflectance and light sources with very different spectral power distribution.     

Revectorization-Based Soft Shadow Mapping

In this paper, we present revectorization-based soft shadow mapping, an algorithm that enables the rendering of visually plausible anti-aliased soft shadows in real time. In revectorization-based shadow mapping, shadow silhouettes are anti-aliased and filtered on the basis of a discontinuity space. By replacing the filtering step of the theoretical framework of the percentage-closer soft shadow algorithm by a revectorization-based filtering algorithm, we are able to provide anti-aliasing mainly for near contact shadows or small penumbra sizes generated from low-resolution shadow maps. Moreover, we present a screen-space variant of our technique that generates visually plausible soft shadows with an overhead of only in processing time, when compared to the fastest soft shadow algorithms proposed in the literature, but that introduces shadow overestimation artefacts in the final rendering.     

Greedy Geometric Algorithms for Collection of Balls,with Applications to Geometric Approximation and Molecular Coarse‐Graining

Choosing balls that best approximate a 3D object is a non‐trivial problem. To answer it, we first address the inner approximation problem, which consists of approximating an object defined by a union of n balls with balls defining a region . This solution is further used to construct an outer approximation enclosing the initial shape, and an interpolated approximation sandwiched between the inner and outer approximations. The inner approximation problem is reduced to a geometric generalization of weighted max k‐cover, solved with the greedy strategy which achieves the classical lower bound. The outer approximation is reduced to exploiting the partition of the boundary of by the Apollonius Voronoi diagram of the balls defining the inner approximation. Implementation‐wise, we present robust software incorporating the calculation of the exact Delaunay triangulation of points with degree two algebraic coordinates, of the exact medial axis of a union of balls, and of a certified estimate of the volume of a union of balls. Application‐wise, we exhibit accurate coarse‐grain molecular models using a number of balls 20 times smaller than the number of atoms, a key requirement to simulate crowded cellular environments.     

Designing large‐scale interactive traffic animations for urban modeling

Designing and optimizing traffic behavior and animation is a challenging problem of interest to virtual environment content generation and to urban planning and design. While some traffic simulation methods have appeared in computer graphics, most related systems focus on the design of buildings, roads, or cities but without explicitly considering urban traffic. To our knowledge, our work provides the first interactive approach which enables a designer to specify a desired vehicular traffic behavior (e.g., road occupancy, travel time, emissions, etc.) and the system will automatically compute what realistic 3D urban model (e.g., an interconnected network of roads, parcels, and buildings) yields the specified behavior. Our system both altered and improved traffic behavior in novel procedurally‐generated cities and in road networks of existing cities. Our urban models contain up to 360 km of roads, 300,000 vehicles, and typically cover four hours of simulated peak traffic time. The typical editing session time to “paint” a new traffic pattern and to compute the new/changed urban model is two to five minutes.     

Stability of Dissipation Elements: A Case Study in Combustion

Recently, dissipation elements have been gaining popularity as a mechanism for measurement of fundamental properties of turbulent flow, such as turbulence length scales and zonal partitioning. Dissipation elements segment a domain according to the source and destination of streamlines in the gradient flow field of a scalar function f : → ?. They have traditionally been computed by numerically integrating streamlines from the center of each voxel in the positive and negative gradient directions, and grouping those voxels whose streamlines terminate at the same extremal pair. We show that the same structures map well to combinatorial topology concepts developed recently in the visualization community. Namely, dissipation elements correspond to sets of cells of the Morse‐Smale complex. The topology‐based formulation enables a more exploratory analysis of the nature of dissipation elements, in particular, in understanding their stability with respect to small scale variations. We present two examples from combustion science that raise significant questions about the role of small scale perturbation and indeed the definition of dissipation elements themselves.     

Synthesis of Responsive Motion Using a Dynamic Model

Synthesizing the movements of a responsive virtual character in the event of unexpected perturbations has proven a difficult challenge. To solve this problem, we devise a fully automatic method that learns a nonlinear probabilistic model of dynamic responses from very few perturbed walking sequences. This model is able to synthesize responses and recovery motions under new perturbations different from those in the training examples. When perturbations occur, we propose a physics‐based method that initiates motion transitions to the most probable response example based on the dynamic states of the character. Our algorithm can be applied to any motion sequences without the need for preprocessing such as segmentation or alignment. The results show that three perturbed motion clips can sufficiently generate a variety of realistic responses, and 14 clips can create a responsive virtual character that reacts realistically to external forces in different directions applied on different body parts at different moments in time.     

Curve Reconstruction with Many Fewer Samples

We consider the problem of sampling points from a collection of smooth curves in the plane, such that the Crust family of proximity‐based reconstruction algorithms can rebuild the curves. Reconstruction requires a dense sampling of local features, i.e., parts of the curve that are close in Euclidean distance but far apart geodesically. We show that ε < 0.47‐sampling is sufficient for our proposed HNN‐Crust variant, improving upon the state‐of‐the‐art requirement of ε < ‐sampling. Thus we may reconstruct curves with many fewer samples. We also present a new sampling scheme that reduces the required density even further than ε < 0.47‐sampling. We achieve this by better controlling the spacing between geodesically consecutive points. Our novel sampling condition is based on the reach, the minimum local feature size along intervals between samples. This is mathematically closer to the reconstruction density requirements, particularly near sharp‐angled features. We prove lower and upper bounds on reach ρ‐sampling density in terms of lfs ε‐sampling and demonstrate that we typically reduce the required number of samples for reconstruction by more than half.     

Authoring Hierarchical Road Networks

We present a procedural method for generating hierarchical road networks connecting cities, towns and villages over large terrains. Our approach relies on an original geometric graph generation algorithm based on a non‐Euclidean metric combined with a path merging algorithm that creates junctions between the different types of roads. Unlike previous work, our method allows high level user control by manipulating the density and the pattern of the network. The geometry of the highways, primary and secondary roads as well as the interchanges and intersections are automatically created from the graph structure by instantiating generic parameterized models.     

Diffusion‐Based Snow Cover Generation

We present a method to generate snow covers on complex scene geometries. Both volumetric snow shapes and photorealistic texturing are computed. We formulate snow accumulation as a diffusive distribution process on a ground scene. Our theoretical framework is motivated by models for granular material deposition. With the framework we can capture the most relevant features of natural snow cover geometries in a concise local computation scheme. Snow bridges and overhangs are also included. Snow surface texture coordinates are computed to create realistic ground–snow interfaces. Several example scenes and a supplementary snow cover growth animation demonstrate the method's efficiency.     

Procedural Modelling of Urban Road Networks

We present a model for growing procedural road networks in and close to cities. The main idea of our paper is that a city cannot be meaningfully simulated without taking its neighbourhood into account. A simple traffic simulation that considers this neighbourhood is then used to grow new major roads and to influence the locations of minor road growth. Waterways are introduced and used to help position the city nuclei on the map. The resulting cities are formed by allowing several smaller settlements to grow together and to form a rich road structure, much like in real world, and require only minimal per‐city input, allowing for batch generation.     

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.     

Laplace–Beltrami Operator on Point Clouds Based on Anisotropic Voronoi Diagram

The symmetrizable and converged Laplace–Beltrami operator () is an indispensable tool for spectral geometrical analysis of point clouds. The , introduced by Liu et al. [LPG12] is guaranteed to be symmetrizable, but its convergence degrades when it is applied to models with sharp features. In this paper, we propose a novel , which is not only symmetrizable but also can handle the point‐sampled surface containing significant sharp features. By constructing the anisotropic Voronoi diagram in the local tangential space, the can be well constructed for any given point. To compute the area of anisotropic Voronoi cell, we introduce an efficient approximation by projecting the cell to the local tangent plane and have proved its convergence. We present numerical experiments that clearly demonstrate the robustness and efficiency of the proposed for point clouds that may contain noise, outliers, and non‐uniformities in thickness and spacing. Moreover, we can show that its spectrum is more accurate than the ones from existing for scan points or surfaces with sharp features.     

A Statistical Model of Human Pose and Body Shape

Generation and animation of realistic humans is an essential part of many projects in today's media industry. Especially, the games and special effects industry heavily depend on realistic human animation. In this work a unified model that describes both, human pose and body shape is introduced which allows us to accurately model muscle deformations not only as a function of pose but also dependent on the physique of the subject. Coupled with the model's ability to generate arbitrary human body shapes, it severely simplifies the generation of highly realistic character animations. A learning based approach is trained on approximately 550 full body 3D laser scans taken of 114 subjects. Scan registration is performed using a non-rigid deformation technique. Then, a rotation invariant encoding of the acquired exemplars permits the computation of a statistical model that simultaneously encodes pose and body shape. Finally, morphing or generating meshes according to several constraints simultaneously can be achieved by training semantically meaningful regressors.     

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.     

Real‐time Animation of Sand‐Water Interaction

Recent advances in physically‐based simulations have made it possible to generate realistic animations. However, in the case of solid‐fluid coupling, wetting effects have rarely been noticed despite their visual importance especially in interactions between fluids and granular materials. This paper presents a simple particle‐based method to model the physical mechanism of wetness propagating through granular materials; Fluid particles are absorbed in the spaces between the granular particles and these wetted granular particles then stick together due to liquid bridges that are caused by surface tension and which will subsequently disappear when over‐wetting occurs. Our method can handle these phenomena by introducing a wetness value for each granular particle and by integrating those aspects of behavior that are dependent on wetness into the simulation framework. Using this method, a GPU‐based simulator can achieve highly dynamic animations that include wetting effects in real time.