Abstract We present physically based algorithms for interactive deformable shape and motion modelling. We coarsely sample the objects with simulation nodes, and apply a meshless finite element method to obtain realistic deformations at interactive frame rates. This shape deformation algorithm is then used to specify keyframe poses and a smooth interpolating motion is obtained by solving for an energy‐minimizing trajectory. We show how to handle collisions between different deformable objects as well as with static or moving scene objects. Secondary motion is added as a post‐process by running a meshless elastic solid simulation. We enforce precomputed trajectories using control forces computed using shape matching. Key to the efficiency of our method is a sparse deformation representation and an adaptive optimization algorithm that automatically introduces new degrees of freedom in problematic regions. An accurate temporal interpolation scheme that exactly recovers rigid motions keeps the number of unknowns low and achieves realistic deformations with very few keyframes. We also show how the algorithm allows combining purely physical simulation with keyframe‐based scripted animation. The presented results illustrate that our framework can handle complex shapes at interactive rates, making it a valuable tool for animators to realistically model deformable 3D shapes and their motion.

Abstract We introduce a novel algorithm that decomposes a deformable shape into meaningful parts requiring only a single input pose. Using modal analysis, we are able to identify parts of the shape that tend to move rigidly. We define a deformation energy on the shape, enabling modal analysis to find the typical deformations of the shape. We then find a decomposition of the shape such that the typical deformations can be well approximated with deformation fields that are rigid in each part of the decomposition. We optimize for the best decomposition, which captures how the shape deforms. A hierarchical refinement scheme makes it possible to compute more detailed decompositions for some parts of the shape. Although our algorithm does not require user intervention, it is possible to control the process by directly changing the deformation energy, or interactively refining the decomposition as necessary. Due to the construction of the energy function and the properties of modal analysis, the computed decompositions are robust to changes in pose as well as meshing, noise, and even imperfections such as small holes in the surface.

We present a framework and algorithms for robust geometry and motion reconstruction of complex deforming shapes. Our method makes use of a smooth template that provides a crude approximation of the scanned object and serves as a geometric and topological prior for reconstruction. Large-scale motion of the acquired object is recovered using a novel space-time adaptive, non-rigid registration method. Fine-scale details such as wrinkles and folds are synthesized with an efficient linear mesh deformation algorithm. Subsequent spatial and temporal filtering of detail coefficients allows transfer of persistent geometric detail to regions not observed by the scanner. We show how this two-scale process allows faithful recovery of small-scale shape and motion features leading to a high-quality reconstruction. We illustrate the robustness and generality of our algorithm on a variety of examples composed of different materials and exhibiting a large range of dynamic deformations.

We present a new technique for reconstructing a single shape and its nonrigid motion from 3D scanning data. Our algorithm takes a set of time-varying unstructured sample points that capture partial views of a deforming object as input and reconstructs a single shape and a deformation field that fit the data. This representation yields dense correspondences for the whole sequence, as well as a completed 3D shape in every frame. In addition, the algorithm automatically removes spatial and temporal noise artifacts and outliers from the raw input data. Unlike previous methods, the algorithm does not require any shape template but computes a fitting shape automatically from the input data. Our reconstruction framework is based upon a novel topology-aware adaptive subspace deformation technique that allows handling long sequences with complex geometry efficiently. The algorithm accesses data in multiple sequential passes, so that long sequences can be streamed from hard disk, not being limited by main memory. We apply the technique to several benchmark datasets, significantly increasing the complexity of the data that can be handled efficiently in comparison to previous work.

The number of wireless networks that coexist in space is increasing steeply. To allow coexistence while avoiding interference, it becomes important to properly characterize the propagation contour where the received power of wireless transmitters reaches a certain threshold. Detailed channel modeling taking into account the specificities of typical urban scenarios is however a very complex task. Thanks to the widespread use of wireless access technology, it becomes feasible to use network nodes to estimate and communicate these propagation contours. In this paper, we propose a lightweight practical scheme for local contour estimation of a given transmitter. The local estimate is efficiently propagated to all other secondary transmitters that can then meet interference constraints optimally, i.e., without having to consider large safety margins that limit spatial reuse gains. This optimality is obtained through iterative power control based on true propagation contour distances and local pathloss estimates. The overhead of the estimation and communication phases is simulated to be close to linear in the number of nodes, so that the solution scales well. The scheme can be used for optimal power control in practical wireless networks, or for the deployment of secondary networks in areas with primary transmitters that should be protected.

Abstract 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.

This paper presents the simulation of a fluid flowing through a porous deformable material. We introduce the physical principles governing porous flow, expressed by the Law of Darcy, into the Smoothed Particle Hydrodynamics (SPH) framework for simulating fluids and deformable objects. Contrary to previous SPH approaches, we simulate porous flow at a macroscopic scale, making abstraction of individual pores or cavities inside the material. Thus, the number of computational elements is kept low, while at the same time realistic simulations can be achieved. Our algorithm models the changing behavior of the wet material as well as the full two-way coupling between the fluid and the porous material. This enables various new effects, such as the simulation of sponge-like elastic bodies and water-absorbing sticky cloth.

This paper introduces a novel technique for joint surface reconstruction and registration. Given a set of roughly aligned noisy point clouds, it outputs a noise-free and watertight solid model. The basic idea of the new technique is to reconstruct a prototype surface at increasing resolution levels, according to the registration accuracy obtained so far, and to register all parts with this surface. We derive a non-linear optimization problem from a Bayesian formulation of the joint estimation problem. The prototype surface is represented as a partition of unity implicit surface, which is constructed from piecewise quadratic functions defined on octree cells and blended together using B-spline basis functions, allowing the representation of objects with arbitrary topology with high accuracy. We apply the new technique to a set of standard data sets as well as especially challenging real-world cases. In practice, the novel prototype surface based joint reconstruction-registration algorithm avoids typical convergence problems in registering noisy range scans and substantially improves the accuracy of the final output.

We present novel adaptive sampling algorithms for particle-based fluid simulation. We introduce a sampling condition based on geometric local feature size that allows focusing computational resources in geometrically complex regions, while reducing the number of particles deep inside the fluid or near thick flat surfaces. Further performance gains are achieved by varying the sampling density according to visual importance. In addition, we propose a novel fluid surface definition based on approximate particle-to-surface distances that are carried along with the particles and updated appropriately. The resulting surface reconstruction method has several advantages over existing methods, including stability under particle resampling and suitability for representing smooth flat surfaces. We demonstrate how our adaptive sampling and distance-based surface reconstruction algorithms lead to significant improvements in time and memory as compared to single resolution particle simulations, without significantly affecting the fluid flow behavior.

We present efficient data structures and caching schemes to accelerate ray-surface intersections for deforming point-sampled surfaces.By exploiting spatial and temporal coherence of the deformation during the animation, we are able to improve rendering performance by a factor of two to three compared to existing techniques.Starting from a tight bounding sphere hierarchy for the undeformed object, we use a lazy updating scheme to adapt the hierarchy to the deformed surface in each animation step.In addition, we achieve a significant speedup for ray-surface intersections by caching per-ray intersection points.We also present a technique for rendering sharp edges and corners in point-sampled models by introducing a novel surface clipping algorithm.

We present a new meshless animation framework for elastic and plastic materials that fracture. Central to our method is a highly dynamic surface and volume sampling method that supports arbitrary crack initiation, propagation, and termination, while avoiding many of the stability problems of traditional mesh-based techniques. We explicitly model advancing crack fronts and associated fracture surfaces embedded in the simulation volume. When cutting through the material, crack fronts directly affect the coupling between simulation nodes, requiring a dynamic adaptation of the nodal shape functions. We show how local visibility tests and dynamic caching lead to an efficient implementation of these effects based on point collocation. Complex fracture patterns of interacting and branching cracks are handled using a small set of topological operations for splitting, merging, and terminating crack fronts. This allows continuous propagation of cracks with highly detailed fracture surfaces, independent of the spatial resolution of the simulation nodes, and provides effective mechanisms for controlling fracture paths. We demonstrate our method for a wide range of materials, from stiff elastic to highly plastic objects that exhibit brittle and/or ductile fracture.

In this paper we present an algorithm to perform interactive boolean operations on free-form solids bounded by surfels. We introduce a fast inside-outside test to check whether surfels lie within the bounds of another surfel-bounded solid. This enables us to add, subtract and intersect complex solids at interactive rates. Our algorithm is fast both in displaying and constructing the new geometry resulting from the boolean operation.We present a resampling operator to solve problems resulting from sharp edges in the resulting solid. The operator resamples the surfels intersecting with the surface of the other solid. This enables us to represent the sharp edges with great detail.We believe our algorithm to be an ideal tool for interactive editing of free-form solids.