29-Issue 5

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/156

Browse

Now showing 1 - 20 of 25

Barycentric Coordinates on Surfaces
(2010) Raif M. Rustamov
This paper introduces a method for defining and efficiently computing barycentric coordinates with respect to polygons on general surfaces. Our construction is geared towards injective polygons (polygons that can be enclosed in a metric ball of an appropriate size) and is based on replacing the linear precision property of planar coordinates by a requirement in terms of center of mass, and generalizing this requirement to the surface setting. We show that the resulting surface barycentric coordinates can be computed using planar barycentric coordinates with respect to a polygon in the tangent plane. We prove theoretically that the surface coordinates properly generalize the planar coordinates and carry some of their useful properties such as unique reconstruction of a point given its coordinates, uniqueness for triangles, edge linearity, similarity invariance, and smoothness; in addition, these coordinates are insensitive to isometric deformations and can be used to reconstruct isometries. We show empirically that surface coordinates are shape-aware with consistent gross behavior across different surfaces, are well-behaved for different polygon types/locations on variety of surface forms, and that they are fast to compute. Finally, we demonstrate effectiveness of surface coordinates for interpolation, decal mapping, and correspondence refinement.
Closed-form Blending of Local Symmetries
(2010) Deboshmita Ghosh; Nina Amenta; Michael Kazhdan
We present a closed-form solution for the symmetrization problem, solving for the optimal deformation that reconciles a set of local bilateral symmetries. Given as input a set of point-pairs which should be symmetric, we first compute for each local neighborhood a transformation which would produce an approximate bilateral symmetry. We then solve for a single global symmetry which includes all of these local symmetries, while minimizing the deformation within each local neighborhood. Our main motivation is the symmetrization of digitized fossils, which are often deformed by a combination of compression and bending. In addition, we use the technique to symmetrize articulated models.
Designing Quad-dominant Meshes with Planar Faces
(2010) Mirko Zadravec; Alexander Schiftner; Johannes Wallner
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.
Enhancing Bounding Volumes using Support Plane Mappings for Collision Detection
(2010) Athanasios Vogiannou; Konstantinos Moustakas; Dimitrios Tzovaras; Michael G. Strintzis
In this paper we present a new method for improving the performance of the widely used Bounding Volume Hierarchies for collision detection. The major contribution of our work is a culling algorithm that serves as a generalization of the Separating Axis Theorem for non parallel axes, based on the well-known concept of support planes. We also provide a rigorous definition of support plane mappings and implementation details regarding the application of the proposed method to commonly used bounding volumes. The paper describes the theoretical foundation and an overall evaluation of the proposed algorithm. It demonstrates its high culling efficiency and in its application, significant improvement of timing performance with different types of bounding volumes and support plane mappings for rigid body simulations.
Fast and Scalable CPU/GPU Collision Detection for Rigid and Deformable Surfaces
(2010) Simon Pabst; Artur Koch; Wolfgang Strasser
We present a new hybrid CPU/GPU collision detection technique for rigid and deformable objects based on spatial subdivision. Our approach efficiently exploits the massive computational capabilities of modern CPUs and GPUs commonly found in off-the-shelf computer systems. The algorithm is specifically tailored to be highly scalable on both the CPU and the GPU sides. We can compute discrete and continuous external and self-collisions of nonpenetrating rigid and deformable objects consisting of many tens of thousands of triangles in a few milliseconds on a modern PC. Our approach is orders of magnitude faster than earlier CPU-based approaches and up to twice as fast as the most recent GPU-based techniques.
Fast Generation of Pointerless Octree Duals
(2010) Thomas Lewiner; Vinicius Mello; Adelailson Peixoto; Sinesio Pesco; Helio Lopes
Geometry processing applications frequently rely on octree structures, since they provide simple and efficient hierarchies for discrete data. However, octrees do not guarantee direct continuous interpolation of this data inside its nodes. This motivates the use of the octree's dual structure, which is one of the simplest continuous hierarchical structures. With the emergence of pointerless representations, with their ability to reduce memory footprint and adapt to parallel architectures, the generation of duals of pointerless octrees becomes a natural challenge. This work proposes strategies for dual generation of static or dynamic pointerless octrees. Experimentally, those methods enjoy the memory reduction of pointerless representations and speed up the execution by several factors compared to the usual recursive generation.
Feature Preserving Mesh Generation from 3D Point Clouds
(2010) Nader Salman; Mariette Yvinec; Quentin Merigot
We address the problem of generating quality surface triangle meshes from 3D point clouds sampled on piecewise smooth surfaces. Using a feature detection process based on the covariance matrices of Voronoi cells, we first extract from the point cloud a set of sharp features. Our algorithm also runs on the input point cloud a reconstruction process, such as Poisson reconstruction, providing an implicit surface. A feature preserving variant of a Delaunay refinement process is then used to generate a mesh approximating the implicit surface and containing a faithful representation of the extracted sharp edges. Such a mesh provides an enhanced trade-off between accuracy and mesh complexity. The whole process is robust to noise and made versatile through a small set of parameters which govern the mesh sizing, approximation error and shape of the elements. We demonstrate the effectiveness of our method on a variety of models including laser scanned datasets ranging from indoor to outdoor scenes.
Fuzzy Geodesics and Consistent Sparse Correspondences For Deformable Shapes
(2010) Jian Sun; Xiaobai Chen; Thomas A. Funkhouser
A geodesic is a parameterized curve on a Riemannian manifold governed by a second order partial differential equation. Geodesics are notoriously unstable: small perturbations of the underlying manifold may lead to dramatic changes of the course of a geodesic. Such instability makes it difficult to use geodesics in many applications, in particular in the world of discrete geometry. In this paper, we consider a geodesic as the indicator function of the set of the points on the geodesic. From this perspective, we present a new concept called fuzzy geodesics and show that fuzzy geodesics are stable with respect to the Gromov-Hausdorff distance. Based on fuzzy geodesics, we propose a new object called the intersection configuration for a set of points on a shape and demonstrate its effectiveness in the application of finding consistent correspondences between sparse sets of points on shapes differing by extreme deformations.
Globally Consistent Space-Time Reconstruction
(2010) Tiberiu Popa; Ian South-Dickinson; Derek Bradley; Alla Sheffer; Wolfgang Heidrich
Most objects deform gradually over time, without abrupt changes in geometry or topology, such as changes in genus. Correct space-time reconstruction of such objects should satisfy this gradual change prior. This requirement necessitates a globally consistent interpretation of spatial adjacency. Consider the capture of a surface that comes in contact with itself during the deformation process, such as a hand with different fingers touching one another in parts of the sequence. Naive reconstruction would glue the contact regions together for the duration of each contact and keep them apart in other parts of the sequence. However such reconstruction violates the gradual change prior as it enforces a drastic intrinsic change in the object's geometry at the transition between the glued and unglued sub-sequences. Instead consistent global reconstruction should keep the surfaces separate throughout the entire sequence. We introduce a new method for globally consistent space-time geometry and motion reconstruction from video capture. We use the gradual change prior to resolve inconsistencies and faithfully reconstruct the geometry and motion of the scanned objects. In contrast to most previous methods our algorithm doesn't require a strong shape prior such as a template and provides better results than other template-free approaches.
Guest Editorial
(The Eurographics Association and Blackwell Publishing Ltd, 2010)
High Fidelity Scan Merging
(2010) Julie Digne; Jean-Michel Morel; Nicolas Audfray; Claire Lartigue
For each scanned object 3D triangulation laser scanners deliver multiple sweeps corresponding to multiple laser motions and orientations. The problem of aligning these scans has been well solved by using rigid and, more recently, non-rigid transformations. Nevertheless, there are always residual local offsets between scans which forbid a direct merging of the scans, and force to some preliminary smoothing. Indeed, the tiling and aliasing effects due to the tiniest normal displacements of the scans can be dramatic. This paper proposes a general method to tackle this problem. The algorithm decomposes each scan into its high and low frequency components and fuses the low frequencies while keeping intact the high frequency content. It produces a mesh with the highest attainable resolution, having for vertices all raw data points of all scans. This exhaustive fusion of scans maintains the finest texture details. The method is illustrated on several high resolution scans of archeological objects.
Iso-geometric Finite Element Analysis Based on Catmull-Clark Subdivision Solids
(2010) Daniel Burkhart; Bernd Hamann; Georg Umlauf
We present a volumetric iso-geometric finite element analysis based on Catmull-Clark solids. This concept allows one to use the same representation for the modeling, the physical simulation, and the visualization, which optimizes the design process and narrows the gap between CAD and CAE. In our method the boundary of the solid model is a Catmull-Clark surface with optional corners and creases to support the modeling phase. The crucial point in the simulation phase is the need to perform efficient integration for the elements. We propose a method similar to the standard subdivision surface evaluation technique, such that numerical quadrature can be used. Experiments show that our approach converges faster than methods based on tri-linear and tri-quadratic elements. However, the topological structure of Catmull-Clark elements is as simple as the structure of linear elements. Furthermore, the Catmull-Clark elements we use are C2-continuous on the boundary and in the interior except for irregular vertices and edges.
Localized Delaunay Refinement for Sampling and Meshing
(2010) Tamal K. Dey; Joshua A. Levine; Andrew Slatton
The technique of Delaunay renement has been recognized as a versatile tool to generate Delaunay meshes of a variety of geometries. Despite its usefulness, it suffers from one lacuna that limits its application. It does not scale well with the mesh size. As the sample point set grows, the Delaunay triangulation starts stressing the available memory space which ultimately stalls any effective progress. A natural solution to the problem is to maintain the point set in clusters and run the renement on each individual cluster. However, this needs a careful point insertion strategy and a balanced coordination among the neighboring clusters to ensure consistency across individual meshes. We design an octtree based localized Delaunay refinement method for meshing surfaces in three dimensions which meets these goals. We prove that the algorithm terminates and provide guarantees about structural properties of the output mesh. Experimental results show that the method can avoid memory thrashing while computing large meshes and thus scales much better than the standard Delaunay refinement method.
Mixed Finite Elements for Variational Surface Modeling
(2010) Alec Jacobson; Elif Tosun; Olga Sorkine; Denis Zorin
Many problems in geometric modeling can be described using variational formulations that define the smoothness of the shape and its behavior w.r.t. the posed modeling constraints. For example, high-qualityC2 surfaces that obey boundary conditions on positions, tangents and curvatures can be conveniently defined as solutions of high-order geometric PDEs; the advantage of such a formulation is its conceptual representation-independence. In practice, solving high-order problems efficiently and accurately for surfaces approximated by meshes is notoriously difficult. For modeling applications, the preferred approach is to use discrete geometric schemes which are efficient and robust, but their convergence properties are less well understood compared to higher-order FEM. In this paper, we explore discretizations of common geometric PDEs on meshes using mixed finite elements, where additional variables for the derivatives in the problem are introduced. Such formulations use first-order derivatives only, allowing a discretization with simple linear elements. Various boundary conditions can be naturally discretized in this setting. We formalize continuous region constraints commonly used in modeling applications, and show that these seamlessly fit into the mixed framework. We demonstrate that some of the commonly used discrete geometric discretizations can be regarded as a particular case of mixed finite elements. We study the convergence behavior of our discretizations, and how they can be applied to implement common modeling tasks.
Moebius Transformations For Global Intrinsic Symmetry Analysis
(2010) Vladimir G. Kim; Yaron Lipman; Xiaobai Chen; Thomas Funkhouser
The goal of our work is to develop an algorithm for automatic and robust detection of global intrinsic symmetries in 3D surface meshes. Our approach is based on two core observations. First, symmetry invariant point sets can be detected robustly using critical points of the Average Geodesic Distance (AGD) function. Second, intrinsic symmetries are self-isometries of surfaces and as such are contained in the low dimensional group of Moebius transformations. Based on these observations, we propose an algorithm that: 1) generates a set of symmetric points by detecting critical points of the AGD function, 2) enumerates small subsets of those feature points to generate candidate Moebius transformations,and 3) selects among those candidate Moebius transformations the one(s) that best map the surface onto itself. The main advantages of this algorithm stem from the stability of the AGD in predicting potential symmetric point features and the low dimensionality of the Moebius group for enumerating potential self-mappings. During experiments with a benchmark set of meshes augmented with human-specified symmetric correspondences, we find that the algorithm is able to find intrinsic symmetries for a wide variety of object types with moderate deviations from perfect symmetry.
Moving Least Squares Coordinates
(2010) Josiah Manson; Scott Schaefer
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.
Multi-scale Geometric Modeling of Ambiguous Shapes with Toleranced Balls and Compoundly Weighted a-shapes
(2010) Frederic Cazals; Tom Dreyfus
Dealing with ambiguous data is a challenge in Science in general and geometry processing in particular. One route of choice to extract information from such data consists of replacing the ambiguous input by a continuum, typically a one-parameter family, so as to mine stable geometric and topological features within this family. This work follows this spirit and introduces a novel framework to handle 3D ambiguous geometric data which are naturally modeled by balls. First, we introduce toleranced balls to model ambiguous geometric objects. A toleranced ball consists of two concentric balls, and interpolating between their radii provides a way to explore a range of possible geometries. We propose to model an ambiguous shape by a collection of toleranced balls, and show that the aforementioned radius interpolation is tantamount to the growth process associated with an additively-multiplicatively weighted Voronoi diagram (also called compoundly weighted or CW). Second and third, we investigate properties of the CW diagram and the associated CW a-complex, which provides a filtration called the lambda-complex. Fourth, we sketch a naive algorithm to compute the CW VD. Finally, we use the lambdal-complex to assess the quality of models of large protein assemblies, as these models inherently feature ambiguities.
On Discrete Killing Vector Fields and Patterns on Surfaces
(2010) Mirela Ben-Chen; Adrian Butscher; Justin Solomon; Leonidas Guibas
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.
One Point Isometric Matching with the Heat Kernel
(2010) Maks Ovsjanikov; Quentin Merigot; Facundo Memoli; Leonidas Guibas
A common operation in many geometry processing algorithms consists of finding correspondences between pairs of shapes by finding structure-preserving maps between them. A particularly useful case of such maps is isometries, which preserve geodesic distances between points on each shape. Although several algorithms have been proposed to find approximately isometric maps between a pair of shapes, the structure of the space of isometries is not well understood. In this paper, we show that under mild genericity conditions, a single correspondence can be used to recover an isometry defined on entire shapes, and thus the space of all isometries can be parameterized by one correspondence between a pair of points. Perhaps surprisingly, this result is general, and does not depend on the dimensionality or the genus, and is valid for compact manifolds in any dimension. Moreover, we show that both the initial correspondence and the isometry can be recovered efficiently in practice. This allows us to devise an algorithm to find intrinsic symmetries of shapes, match shapes undergoing isometric deformations, as well as match partial and incomplete models efficiently.
Persistent Heat Signature for Pose-oblivious Matching of Incomplete Models
(2010) Tamal K. Dey; Kuiyu Li; Chuanjiang Luo; Pawas Ranjan; Issam Safa; Yusu Wang
Although understanding of shape features in the context of shape matching and retrieval has made considerable progress in recent years, the case for partial and incomplete models in presence of pose variations still begs a robust and efficient solution. A signature that encodes features at multi-scales in a pose invariant manner is more appropriate for this case. The Heat Kernel Signature function from spectral theory exhibits this multi-scale property. We show how this concept can be merged with the persistent homology to design a novel efficient poseoblivious matching algorithm for all models, be they partial, incomplete, or complete. We make the algorithm scalable so that it can handle large data sets. Several test results show the robustness of our approach.

Browse

Browsing 29-Issue 5 by Title

Results Per Page

Sort Options