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.     

Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes

We present a novel technique for the efficient boundary evaluation of sweep operations applied to objects in polygonal boundary representation. These sweep operations include Minkowski addition, offsetting, and sweeping along a discrete rigid motion trajectory. Many previous methods focus on the construction of a polygonal superset (containing self‐intersections and spurious internal geometry) of the boundary of the volumes which are swept. Only few are able to determine a clean representation of the actual boundary, most of them in a discrete volumetric setting. We unify such superset constructions into a succinct common formulation and present a technique for the robust extraction of a polygonal mesh representing the outer boundary, i.e. it makes no general position assumptions and always yields a manifold, watertight mesh. It is exact for Minkowski sums and approximates swept volumes polygonally. By using plane‐based geometry in conjunction with hierarchical arrangement computations we avoid the necessity of arbitrary precision arithmetics and extensive special case handling. By restricting operations to regions containing pieces of the boundary, we significantly enhance the performance of the algorithm.     

Fast and Robust Normal Estimation for Point Clouds with Sharp Features

This paper presents a new method for estimating normals on unorganized point clouds that preserves sharp features. It is based on a robust version of the Randomized Hough Transform (RHT). We consider the filled Hough transform accumulator as an image of the discrete probability distribution of possible normals. The normals we estimate corresponds to the maximum of this distribution. We use a fixed‐size accumulator for speed, statistical exploration bounds for robustness, and randomized accumulators to prevent discretization effects. We also propose various sampling strategies to deal with anisotropy, as produced by laser scans due to differences of incidence. Our experiments show that our approach offers an ideal compromise between precision, speed, and robustness: it is at least as precise and noise‐resistant as state‐of‐the‐art methods that preserve sharp features, while being almost an order of magnitude faster. Besides, it can handle anisotropy with minor speed and precision losses.     

A Global Parity Measure for Incomplete Point Cloud Data

Shapes with complex geometric and topological features such as tunnels, neighboring sheets, and cavities are susceptible to undersampling and continue to challenge existing reconstruction techniques. In this work we introduce a new measure for point clouds to determine the likely interior and exterior regions of an object. Specifically, we adapt the concept of parity to point clouds with missing data and introduce the parity map, a global measure of parity over the volume. We first examine how parity changes over the volume with respect to missing data and develop a method for extracting topologically correct interior and exterior crusts for estimating a signed distance field and performing surface reconstruction. We evaluate our approach on real scan data representing complex shapes with missing data. Our parity measure is not only able to identify highly confident interior and exterior regions but also localizes regions of missing data. Our reconstruction results are compared to existing methods and we show that our method faithfully captures the topology and geometry of complex shapes in the presence of missing data.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

Hybrid Simulation of Miscible Mixing with Viscous Fingering

By modeling mass transfer phenomena, we simulate solids and liquids dissolving or changing to other substances. We also deal with the very small‐scale phenomena that occur when a fluid spreads out at the interface of another fluid. We model the pressure at the interfaces between fluids with Darcy's Law and represent the viscous fingering phenomenon in which a fluid interface spreads out with a fractal‐like shape. We use hybrid grid‐based simulation and smoothed particle hydrodynamics (SPH) to simulate intermolecular diffusion and attraction using particles at a computable scale. We have produced animations showing fluids mixing and objects dissolving.     

Realtime Two‐Way Coupling of Meshless Fluids and Nonlinear FEM

In this paper, we present a novel method to couple Smoothed Particle Hydrodynamics (SPH) and nonlinear FEM to animate the interaction of fluids and deformable solids in real time. To accurately model the coupling, we generate proxy particles over the boundary of deformable solids to facilitate the interaction with fluid particles, and develop an efficient method to distribute the coupling forces of proxy particles to FEM nodal points. Specifically, we employ the Total Lagrangian Explicit Dynamics (TLED) finite element algorithm for nonlinear FEM because of many of its attractive properties such as supporting massive parallelism, avoiding dynamic update of stiffness matrix computation, and efficient solver. Based on a predictor‐corrector scheme for both velocity and position, different normal and tangential conditions can be realized even for shell‐like thin solids. Our coupling method is entirely implemented on modern GPUs using CUDA. We demonstrate the advantage of our two‐way coupling method in computer animation via various virtual scenarios.     

Polyhedral Finite Elements Using Harmonic Basis Functions

Finite element simulations in computer graphics are typically based on tetrahedral or hexahedral elements, which enables simple and efficient implementations, but in turn requires complicated remeshing in case of topological changes or adaptive refinement. We propose a flexible finite element method for arbitrary polyhedral elements, thereby effectively avoiding the need for remeshing. Our polyhedral finite elements are based on harmonic basis functions, which satisfy all necessary conditions for FEM simulations and seamlessly generalize both linear tetrahedral and trilinear hexahedral elements. We discretize harmonic basis functions using the method of fundamental solutions, which enables their flexible computation and efficient evaluation. The versatility of our approach is demonstrated on cutting and adaptive refinement within a simulation framework for corotated linear elasticity.     

Fitting Polynomial Volumes to Surface Meshes with Voronoï Squared Distance Minimization

We propose a method for mapping polynomial volumes. Given a closed surface and an initial template volume grid, our method deforms the template grid by fitting its boundary to the input surface while minimizing a volume distortion criterion. The result is a point‐to‐point map distorting linear cells into curved ones. Our method is based on several extensions of Voronoi Squared Distance Minimization (VSDM) combined with a higher‐order finite element formulation of the deformation energy. This allows us to globally optimize the mapping without prior parameterization. The anisotropic VSDM formulation allows for sharp and semi‐sharp features to be implicitly preserved without tagging. We use a hierarchical finite element function basis that selectively adapts to the geometric details. This makes both the method more efficient and the representation more compact. We apply our method to geometric modeling applications in computer‐aided design and computer graphics, including mixed‐element meshing, mesh optimization, subdivision volume fitting, and shell meshing.     

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.     

Approximate on‐Surface Distance Computation using Quasi‐Developable Charts

There is a vast number of applications that require distance field computation over triangular meshes. State‐of‐the‐art algorithms have quadratic or sub‐quadratic worst‐case complexity, making them impractical for interactive applications. While most of the research on this subject has been focused on reducing the computation complexity of the algorithms, in this work we propose an approximate algorithm that achieves similar results working in lower resolutions of the input meshes. The creation of lower resolution meshes is the essence of our proposal. The idea is to identify regions on the input mesh that can be unfolded into planar regions with minimal area distortion (i.e. quasi‐developable charts). Once charts are computed, their interior is re‐triangulated to reduce the number of triangles, which results in a collection of simplified charts that we call a base mesh. Due to the properties of quasi‐developable regions, we are able to compute distance fields over the base mesh instead of over the input mesh. This reduces the memory footprint and data processed for distance computations, which is the bottleneck of these algorithms. We present results that are one order of magnitude faster than current exact solutions, with low approximation errors.     

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.