SGP10: Eurographics Symposium on Geometry Processing

Permanent URI for this collection

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

Browse

Now showing 1 - 20 of 25

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.
Guest Editorial
(The Eurographics Association and Blackwell Publishing Ltd, 2010)
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.
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.
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.
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.
Polygonal Mesh Watermarking Using Laplacian Coordinates
(2010) Ying Yang; Ioannis Ivrissimtzis
We propose a watermarking algorithm for polygonal meshes based on the modification of the Laplacian coordinates. More specifically, we first compute the Laplacian coordinates (x, y, z) of the mesh vertices, then construct the histogram of the lengths of the (x, y, z) vectors, and finally, insert the watermark by altering the shape of that histogram. The watermark extraction is carried out blindly, with no reference to the host model. The proposed method is more robust than several existing high capacity watermarking algorithms. In particular, it is able to resist attacks such as translations, rotations, uniform scaling and vertex reordering, due to the invariance of the histogram of the Laplacian vector lengths under such transformations. Compared to the existing robust watermarking methods, our experiments show that the proposed method can better resist common mesh editing attacks, due to the good behaviour of the Laplacian coordinates under such operations.
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.
Signing the Unsigned: Robust Surface Reconstruction from Raw Pointsets
(2010) Patrick Mullen; Fernando de Goes; Mathieu Desbrun; David Cohen-Steiner; Pierre Alliez
We propose a modular framework for robust 3D reconstruction from unorganized, unoriented, noisy, and outlierridden geometric data. We gain robustness and scalability over previous methods through an unsigned distance approximation to the input data followed by a global stochastic signing of the function. An isosurface reconstruction is finally deduced via a sparse linear solve. We show with experiments on large, raw, geometric datasets that this approach is scalable while robust to noise, outliers, and holes. The modularity of our approach facilitates customization of the pipeline components to exploit specific idiosyncracies of datasets, while the simplicity of each component leads to a straightforward implementation.
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.
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.
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.
Scales and Scale-like Structures
(2010) Eric Landreneau; Scott Schaefer
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.
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.
Trivial Connections on Discrete Surfaces
(2010) Keenan Crane; Mathieu Desbrun; Peter Schroeder
This paper presents a straightforward algorithm for constructing connections on discrete surfaces that are as smooth as possible everywhere but on a set of isolated singularities with given index. We compute these connections by solving a single linear system built from standard operators. The solution can be used to design rotationally symmetric direction fields with user-specified singularities and directional constraints.
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.
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.
Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes
(2010) Marcel Campen; Leif Kobbelt
Abstract 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.
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.

Browse

Browsing SGP10: Eurographics Symposium on Geometry Processing by Issue Date

Results Per Page

Sort Options