Simplification of Articulated Meshes

We present a method for simplifying a polygonal character with an associated skeletal deformation such that the simplified character approximates the original shape well when deformed. As input, we require a set of example poses that are representative of the types of deformations the character undergoes and we produce a multi-resolution hierarchy for the simplified character where all simplified vertices also have associated skin weights. We create this hierarchy by minimizing an error metric for a simplified set of vertices and their skin weights, and we show that this quartic error metric can be effectively minimized using alternating quadratic minimization for the vertices and weights separately. To enable efficient GPU accelerated deformations of the simplified character, we also provide a method that guarantees the maximum number of bone weights per simplified vertex is less than a user specified threshold at all levels of the hierarchy.     

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.     

A Condition Number for Non‐Rigid Shape Matching

Despite the large amount of work devoted in recent years to the problem of non‐rigid shape matching, practical methods that can successfully be used for arbitrary pairs of shapes remain elusive. In this paper, we study the hardness of the problem of shape matching, and introduce the notion of the shape condition number, which captures the intuition that some shapes are inherently more difficult to match against than others. In particular, we make a connection between the symmetry of a given shape and the stability of any method used to match it while optimizing a given distortion measure. We analyze two commonly used classes of methods in deformable shape matching, and show that the stability of both types of techniques can be captured by the appropriate notion of a condition number. We also provide a practical way to estimate the shape condition number and show how it can be used to guide the selection of landmark correspondences between shapes. Thus we shed some light on the reasons why general shape matching remains difficult and provide a way to detect and mitigate such difficulties in practice.     

Scales and Scale‐like Structures

We present a method for generating scales and scale‐like structures on a polygonal mesh through surface replacement. As input, we require a triangular mesh that will be covered with scales and one or more proxy‐models to be used as the scale's shape. A user begins scale generation by drawing a lateral line on the model to control the distribution and orientation of scales on the surface. We then create a vector field over the surface to control an anisotropic Voronoi tessellation, which represents the region occupied by each scale. Next we replace these regions by cutting the proxy model to match the boundary of the Voronoi region and deform the cut model onto the surface. The result is a fully connected 2‐manifold that is suitable for subsequent post‐processing applications like surface subdivision.     

Noise‐Adaptive Shape Reconstruction from Raw Point Sets

We propose a noise‐adaptive shape reconstruction method specialized to smooth, closed shapes. Our algorithm takes as input a defect‐laden point set with variable noise and outliers, and comprises three main steps. First, we compute a novel noise‐adaptive distance function to the inferred shape, which relies on the assumption that the inferred shape is a smooth submanifold of known dimension. Second, we estimate the sign and confidence of the function at a set of seed points, through minimizing a quadratic energy expressed on the edges of a uniform random graph. Third, we compute a signed implicit function through a random walker approach with soft constraints chosen as the most confident seed points computed in previous step.     

Moving Least Squares Coordinates

We propose a new family of barycentric coordinates that have closed‐forms for arbitrary 2D polygons. These coordinates are easy to compute and have linear precision even for open polygons. Not only do these coordinates have linear precision, but we can create coordinates that reproduce polynomials of a set degree m as long as degree m polynomials are specified along the boundary of the polygon. We also show how to extend these coordinates to interpolate derivatives specified on the boundary.     

Sketching MLS Image Deformations On the GPU

In this paper, we present an image editing tool that allows the user to deform images using a sketch‐based interface. The user simply sketches a set of source curves in the input image, and also some target curves that the source curves should be deformed to. Then the moving least squares (MLS) deformation technique [ [SMW06] ] is adapted to produce realistic deformations while satisfying the curves' positional constraints. We also propose a scheme to reduce image fold‐overs in MLS deformations. Our system has a very intuitive user interface, generates physically plausible deformations, and can be easily implemented on the GPU for real‐time performance.     

gProximity: Hierarchical GPU‐based Operations for Collision and Distance Queries

We present novel parallel algorithms for collision detection and separation distance computation for rigid and deformable models that exploit the computational capabilities of many‐core GPUs. Our approach uses thread and data parallelism to perform fast hierarchy construction, updating, and traversal using tight‐fitting bounding volumes such as oriented bounding boxes (OBB) and rectangular swept spheres (RSS). We also describe efficient algorithms to compute a linear bounding volume hierarchy (LBVH) and update them using refitting methods. Moreover, we show that tight‐fitting bounding volume hierarchies offer improved performance on GPU‐like throughput architectures. We use our algorithms to perform discrete and continuous collision detection including self‐collisions, as well as separation distance computation between non‐overlapping models. In practice, our approach (gProximity) can perform these queries in a few milliseconds on a PC with NVIDIA GTX 285 card on models composed of tens or hundreds of thousands of triangles used in cloth simulation, surgical simulation, virtual prototyping and N‐body simulation. Moreover, we observe more than an order of magnitude performance improvement over prior GPU‐based algorithms.     

On the shape of a set of points and lines in the plane

Detailed geometric models of the real world are in increasing demand. LiDAR data is appropriate to reconstruct urban models. In urban scenes, the individual surfaces can be reconstructed and connected to form the scene geometry. There are various methods for reconstructing the free‐form shape of a point sample on a single surface. However, these methods do not take the context of the surface into account. We present the guided α‐shape: an extension of the well known α‐shape that uses lines (guides) to indicate preferred locations for the boundary of the shape. The guided α‐shape uses (parts of) these lines as boundary where the points suggest that this is appropriate. We prove that the guided α‐shape can be constructed in O((n + m) log (n + m)) time, from an input of n points and m guides. We apply guided α‐shapes to urban reconstruction from LiDAR, where neighboring surfaces can be connected conveniently along their intersection lines into adjacent surfaces of a 3D model. We analyze guided α‐shapes of both synthetic and real data and show they are consistently better than α‐shapes for this application.     

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.     

Poisson‐Based Weight Reduction of Animated Meshes

While animation using barycentric coordinates or other automatic weight assignment methods has become a popular method for shape deformation, the global nature of the weights limits their use for real‐time applications. We present a method that reduces the number of control points influencing a vertex to a user‐specified number such that the deformations created by the reduced weight set resemble that of the original deformation. To do so we show how to set up a Poisson minimization problem to solve for a reduced weight set and illustrate its advantages over other weight reduction methods. Not only does weight reduction lower the amount of storage space necessary to deform these models but also allows GPU acceleration of the resulting deformations. Our experiments show that we can achieve a factor of 100 increase in speed over CPU deformations using the full weight set, which makes real‐time deformations of large models possible.     

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.     

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.     

Adaptive Space Deformations Based on Rigid Cells

We propose a new adaptive space deformation method for interactive shape modeling. A novel energy formulation based on elastically coupled volumetric cells yields intuitive detail preservation even under large deformations. By enforcing rigidity of the cells, we obtain an extremely robust numerical solver for the resulting nonlinear optimization problem. Scalability is achieved using an adaptive spatial discretization that is decoupled from the resolution of the embedded object. Our approach is versatile and easy to implement, supports thin-shell and solid deformations of 2D and 3D objects, and is applicable to arbitrary sample-based representations, such as meshes, triangle soups, or point clouds.     

Fast Parallel Construction of Smooth Surfaces from Meshes with Tri/Quad/Pent Facets

Polyhedral meshes consisting of triangles, quads, and pentagons and polar configurations cover all major sampling and modeling scenarios. We give an algorithm for efficient local, parallel conversion of such meshes to an everywhere smooth surface consisting of low‐degree polynomial pieces. Quadrilateral facets with 4‐valent vertices are ‘regular’ and are mapped to bi‐cubic patches so that adjacent bi‐cubics join C² as for cubic tensor‐product splines. The algorithm can be implemented in the vertex and geometry shaders of the GPU pipeline and does not use the fragment shader. Its implementation in DirectX 10 achieves conversion plus rendering at 659 frames per second with 42.5 million triangles per second on input of a model of 1300 facets of which 60% are not regular.     

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.     

Global Correspondence Optimization for Non‐Rigid Registration of Depth Scans

We present a registration algorithm for pairs of deforming and partial range scans that addresses the challenges of non‐rigid registration within a single non‐linear optimization. Our algorithm simultaneously solves for correspondences between points on source and target scans, confidence weights that measure the reliability of each correspondence and identify non‐overlapping areas, and a warping field that brings the source scan into alignment with the target geometry. The optimization maximizes the region of overlap and the spatial coherence of the deformation while minimizing registration error. All optimization parameters are chosen automatically; hand‐tuning is not necessary. Our method is not restricted to part‐in‐whole matching, but addresses the general problem of partial matching, and requires no explicit prior correspondences or feature points. We evaluate the performance and robustness of our method using scan data acquired by a structured light scanner and compare our method with existing non‐rigid registration algorithms.     

Deformation Grammars: Hierarchical Constraint Preservation Under Deformation

Deformation grammars are a novel procedural framework enabling to sculpt hierarchical 3D models in an object‐dependent manner. They process object deformations as symbols thanks to user‐defined interpretation rules. We use them to define hierarchical deformation behaviours tailored for each model, and enabling any sculpting gesture to be interpreted as some adapted constraint‐preserving deformation. A variety of object‐specific constraints can be enforced using this framework, such as maintaining distributions of subparts, avoiding self‐penetrations or meeting semantic‐based user‐defined rules. The operations used to maintain constraints are kept transparent to the user, enabling them to focus on their design. We demonstrate the feasibility and the versatility of this approach on a variety of examples, implemented within an interactive sculpting system.     

Perfect Matching Quad Layouts for Manifold Meshes

This paper introduces a new approach to automatically generate pure quadrilateral patch layouts on manifold meshes. The algorithm is based on a careful construction of a singularity graph of a given input frame field or a given periodic global parameterization. A pure quadrilateral patch layout is then derived as a constrained minimum weight perfect matching of that graph. The resulting layout is optimal relative to a balance between coarseness and geometric feature alignment. We formulate the problem of finding pure quadrilateral patch layouts as a global optimization problem related to a well‐known concept in graph theory. The main advantage of the new method is its simplicity and its computation speed. Patch layouts generated by the present algorithm are high quality and are very competitive compared to current state of the art.     

Implicit Hierarchical Quad‐Dominant Meshes

We present a method for producing quad‐dominant subdivided meshes, which supports both adaptive refinement and adaptive coarsening. A hierarchical structure is stored implicitly in a standard half‐edge data structure, while allowing us to efficiently navigate through the different level of subdivision. Subdivided meshes contain a majority of quad elements and a moderate amount of triangles and pentagons in the regions of transition across different levels of detail. Topological LOD editing is controlled with local conforming operators, which support both mesh refinement and mesh coarsening. We show two possible applications of this method: we define an adaptive subdivision surface scheme that is topologically and geometrically consistent with the Catmull–Clark subdivision; and we present a remeshing method that produces semi‐regular adaptive meshes.