Context-Aware Skeletal Shape Deformation

We describe a system for the animation of a skeleton-controlled articulated object that preserves the fine geometric details of the object skin and conforms to the characteristic shapes of the object specified through a set of examples. The system provides the animator with an intuitive user interface and produces compelling results even when presented with a very small set of examples. In addition it is able to generalize well by extrapolating far beyond the examples.     

Geodesic-Controlled Developable Surfaces for Modeling Paper Bending

We present a novel and effective method for modeling a developable surface to simulate paper bending in interactive and animation applications. The method exploits the representation of a developable surface as the envelope of rectifying planes of a curve in 3D, which is therefore necessarily a geodesic on the surface. We manipulate the geodesic to provide intuitive shape control for modeling paper bending. Our method ensures a natural continuous isometric deformation from a piece of bent paper to its flat state without any stretching. Test examples show that the new scheme is fast, accurate, and easy to use, thus providing an effective approach to interactive paper bending. We also show how to handle non-convex piecewise smooth developable surfaces.     

Articulated Object Reconstruction and Markerless Motion Capture from Depth Video

We present an algorithm for acquiring the 3D surface geometry and motion of a dynamic piecewise‐rigid object using a single depth video camera. The algorithm identifies and tracks the rigid components in each frame, while accumulating the geometric information acquired over time, possibly from different viewpoints. The algorithm also reconstructs the dynamic skeleton of the object, thus can be used for markerless motion capture. The acquired model can then be animated to novel poses. We show the results of the algorithm applied to synthetic and real depth video.     

Conformal Flattening by Curvature Prescription and Metric Scaling

We present an efficient method to conformally parameterize 3D mesh data sets to the plane. The idea behind our method is to concentrate all the 3D curvature at a small number of select mesh vertices, called cone singularities, and then cut the mesh through those singular vertices to obtain disk topology. The singular vertices are chosen automatically. As opposed to most previous methods, our flattening process involves only the solution of linear systems of Poisson equations, thus is very efficient. Our method is shown to be faster than existing methods, yet generates parameterizations having comparable quasi‐conformal distortion.     

CHC++: Coherent Hierarchical Culling Revisited

We present a new algorithm for efficient occlusion culling using hardware occlusion queries. The algorithm significantly improves on previous techniques by making better use of temporal and spatial coherence of visibility. This is achieved by using adaptive visibility prediction and query batching. As a result of the new optimizations the number of issued occlusion queries and the number of rendering state changes are significantly reduced. We also propose a simple method for determining tighter bounding volumes for occlusion queries and a method which further reduces the pipeline stalls. The proposed method provides up to an order of magnitude speedup over the previous state of the art. The new technique is simple to implement, does not rely on hardware calibration and integrates well with modern game engines.     

Embedded Implicit Stand-Ins for Animated Meshes: A Case of Hybrid Modelling

In this paper, we address shape modelling problems, encountered in computer animation and computer games development that are difficult to solve just using polygonal meshes. Our approach is based on a hybrid-modelling concept that combines polygonal meshes with implicit surfaces. A hybrid model consists of an animated polygonal mesh and an approximation of this mesh by a convolution surface stand-in that is embedded within it or is attached to it. The motions of both objects are synchronised using a rigging skeleton. We model the interaction between an animated mesh object and a viscoelastic substance, which is normally represented in an implicit form. Our approach is aimed at achieving verisimilitude rather than physically based simulation. The adhesive behaviour of the viscous object is modelled using geometric blending operations on the corresponding implicit surfaces. Another application of this approach is the creation of metamorphosing implicit surface parts that are attached to an animated mesh. A prototype implementation of the proposed approach and several examples of modelling and animation with near real-time preview times are presented.     

Deformable 3D Shape Registration Based on Local Similarity Transforms

In this paper, a new method for deformable 3D shape registration is proposed. The algorithm computes shape transitions based on local similarity transforms which allows to model not only as‐rigid‐as‐possible deformations but also local and global scale. We formulate an ordinary differential equation (ODE) which describes the transition of a source shape towards a target shape. We assume that both shapes are roughly pre‐aligned (e.g., frames of a motion sequence). The ODE consists of two terms. The first one causes the deformation by pulling the source shape points towards corresponding points on the target shape. Initial correspondences are estimated by closest‐point search and then refined by an efficient smoothing scheme. The second term regularizes the deformation by drawing the points towards locally defined rest positions. These are given by the optimal similarity transform which matches the initial (undeformed) neighborhood of a source point to its current (deformed) neighborhood. The proposed ODE allows for a very efficient explicit numerical integration. This avoids the repeated solution of large linear systems usually done when solving the registration problem within general‐purpose non‐linear optimization frameworks. We experimentally validate the proposed method on a variety of real data and perform a comparison with several state‐of‐the‐art approaches.     

Variational 3D Shape Segmentation for Bounding Volume Computation

We propose a variational approach to computing an optimal segmentation of a 3D shape for computing a union of tight bounding volumes. Based on an affine invariant measure of e-tightness, the resemblance to ellipsoid, a novel functional is formulated that governs an optimization process to obtain a partition with multiple components. Refinement of segmentation is driven by application-specific error measures, so that the final bounding volume meets pre-specified user requirement. We present examples to demonstrate the effectiveness of our method and show that it works well for computing ellipsoidal bounding volumes as well as oriented bounding boxes.     

Provably Good 2D Shape Reconstruction from Unorganized Cross‐Sections

This paper deals with the reconstruction of 2‐dimensional geometric shapes from unorganized 1‐dimensional cross‐sections. We study the problem in its full generality following the approach of Boissonnat and Memari [ [BM07] ] for the analogous 3D problem. We propose a new variant of this method and provide sampling conditions to guarantee that the output of the algorithm has the same topology as the original object and is close to it (for the Hausdorff distance).     

Curvature-Domain Shape Processing

We propose a framework for 3D geometry processing that provides direct access to surface curvature to facilitate advanced shape editing, filtering, and synthesis algorithms. The central idea is to map a given surface to the curvature domain by evaluating its principle curvatures, apply filtering and editing operations to the curvature distribution, and reconstruct the resulting surface using an optimization approach. Our system allows the user to prescribe arbitrary principle curvature values anywhere on the surface. The optimization solves a nonlinear least‐squares problem to find the surface that best matches the desired target curvatures while preserving important properties of the original shape. We demonstrate the effectiveness of this processing metaphor with several applications, including anisotropic smoothing, feature enhancement, and multi‐scale curvature editing.     

On Discrete Killing Vector Fields and Patterns on Surfaces

Symmetry is one of the most important properties of a shape, unifying form and function. It encodes semantic information on one hand, and affects the shape's aesthetic value on the other. Symmetry comes in many flavors, amongst the most interesting being intrinsic symmetry, which is defined only in terms of the intrinsic geometry of the shape. Continuous intrinsic symmetries can be represented using infinitesimal rigid transformations, which are given as tangent vector fields on the surface – known as Killing Vector Fields. As exact symmetries are quite rare, especially when considering noisy sampled surfaces, we propose a method for relaxing the exact symmetry constraint to allow for approximate symmetries and approximate Killing Vector Fields, and show how to discretize these concepts for generating such vector fields on a triangulated mesh. We discuss the properties of approximate Killing Vector Fields, and propose an application to utilize them for texture and geometry synthesis.     

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.     

A Hierarchical Segmentation of Articulated Bodies

This paper presents a novel segmentation method to assist the rigging of articulated bodies. The method computes a coarse‐to‐fine hierarchy of segments ordered by the level of detail. The results are invariant to deformations, and numerically robust to noise, irregular tessellations, and topological short‐circuits. The segmentation is based on two key ideas. First, it exploits the multiscale properties of the diffusion distance on surfaces, and then it introduces a new definition of medial structures, composing a bijection between medial structures and segments. Our method computes this bijection through a simple and fast iterative approach, and applies it to triangulated meshes.     

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.     

Global Intrinsic Symmetries of Shapes

Although considerable attention in recent years has been given to the problem of symmetry detection in general shapes, few methods have been developed that aim to detect and quantify the intrinsic symmetry of a shape rather than its extrinsic, or pose‐dependent symmetry. In this paper, we present a novel approach for efficiently computing symmetries of a shape which are invariant up to isometry preserving transformations. We show that the intrinsic symmetries of a shape are transformed into the Euclidean symmetries in the signature space defined by the eigenfunctions of the Laplace‐Beltrami operator. Based on this observation, we devise an algorithm which detects and computes the isometric mappings from the shape onto itself. We show that our approach is both computationally efficient and robust with respect to small non‐isometric deformations, even if they include topological changes.     

Discrete Line Congruences for Shading and Lighting

Two‐parameter families of straight lines (line congruences) are implicitly present in graphics and geometry processing in several important ways including lighting and shape analysis. In this paper we make them accessible to optimization and geometric computing, by introducing a general discrete version of congruences based on piecewise‐linear correspondences between triangle meshes. Our applications of congruences are based on the extraction of a so‐called torsion‐free support structure, which is a procedure analogous to remeshing a surface along its principal curvature lines. A particular application of such structures are freeform shading and lighting systems for architecture. We combine interactive design of such systems with global optimization in order to satisfy geometric constraints. In this way we explore a new area where architecture can greatly benefit from graphics.     

Stability of Curvature Measures

We address the problem of curvature estimation from sampled compact sets. The main contribution is a stability result: we show that the Gaussian, mean or anisotropic curvature measures of the offset of a compact set K with positive μ-reach can be estimated by the same curvature measures of the offset of a compact set K' close to K in the Hausdorff sense. We show how these curvature measures can be computed for finite unions of balls. The curvature measures of the offset of a compact set with positive μ-reach can thus be approximated by the curvature measures of the offset of a point-cloud sample.     

Positional, Metric, and Curvature Control for Constraint-Based Surface Deformation

We present a geometry processing framework that allows direct manipulation or preservation of positional, metric, and curvature constraints anywhere on the surface of a geometric model. Target values for these properties can be specified point-wise or as integrated quantities over curves and surface patches embedded in the shape. For example, the user can draw several curves on the surface and specify desired target lengths, manipulate the normal curvature along these curves, or modify the area or principal curvature distribution of arbitrary surface patches. This user input is converted into a set of non-linear constraints. A global optimization finds the new deformed surface that best satisfies the constraints, while minimizing adaptable measures for metric and curvature distortion that provide explicit control of the deformation semantics. We illustrate how this approach enables flexible surface processing and shape editing operations not available in current systems.