29-Issue 5

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/156
Geometry Processing Proceedings

BibTeX (29-Issue 5)
                
@article{
10.1111:j.1467-8659.2010.01823.x,

journal = {Computer Graphics Forum},
title = {{
Guest Editorial}},

author = {},
year = {
2010},

publisher = {
The Eurographics Association and Blackwell Publishing Ltd},


DOI = {
10.1111/j.1467-8659.2010.01823.x}

}
                
@article{
10.1111:j.1467-8659.2010.01759.x,

journal = {Computer Graphics Forum},
title = {{
Barycentric Coordinates on Surfaces}},

author = {
Raif M. Rustamov
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01759.x}

}
                
@article{
10.1111:j.1467-8659.2010.01760.x,

journal = {Computer Graphics Forum},
title = {{
Moving Least Squares Coordinates}},

author = {
Josiah Manson
 and 
Scott Schaefer
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01760.x}

}
                
@article{
10.1111:j.1467-8659.2010.01762.x,

journal = {Computer Graphics Forum},
title = {{
Fuzzy Geodesics and Consistent Sparse Correspondences For Deformable Shapes}},

author = {
Jian Sun
 and 
Xiaobai Chen
 and 
Thomas A. Funkhouser
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01762.x}

}
                
@article{
10.1111:j.1467-8659.2010.01761.x,

journal = {Computer Graphics Forum},
title = {{
Trivial Connections on Discrete Surfaces}},

author = {
Keenan Crane
 and 
Mathieu Desbrun
 and 
Peter Schroeder
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01761.x}

}
                
@article{
10.1111:j.1467-8659.2010.01763.x,

journal = {Computer Graphics Forum},
title = {{
Persistent Heat Signature for Pose-oblivious Matching of Incomplete Models}},

author = {
Tamal K. Dey
 and 
Kuiyu Li
 and 
Chuanjiang Luo
 and 
Pawas Ranjan
 and 
Issam Safa
 and 
Yusu Wang
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01763.x}

}
                
@article{
10.1111:j.1467-8659.2010.01764.x,

journal = {Computer Graphics Forum},
title = {{
One Point Isometric Matching with the Heat Kernel}},

author = {
Maks Ovsjanikov
 and 
Quentin Merigot
 and 
Facundo Memoli
 and 
Leonidas Guibas
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01764.x}

}
                
@article{
10.1111:j.1467-8659.2010.01765.x,

journal = {Computer Graphics Forum},
title = {{
Mixed Finite Elements for Variational Surface Modeling}},

author = {
Alec Jacobson
 and 
Elif Tosun
 and 
Olga Sorkine
 and 
Denis Zorin
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01765.x}

}
                
@article{
10.1111:j.1467-8659.2010.01766.x,

journal = {Computer Graphics Forum},
title = {{
Iso-geometric Finite Element Analysis Based on Catmull-Clark Subdivision Solids}},

author = {
Daniel Burkhart
 and 
Bernd Hamann
 and 
Georg Umlauf
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01766.x}

}
                
@article{
10.1111:j.1467-8659.2010.01767.x,

journal = {Computer Graphics Forum},
title = {{
Polygonal Mesh Watermarking Using Laplacian Coordinates}},

author = {
Ying Yang
 and 
Ioannis Ivrissimtzis
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01767.x}

}
                
@article{
10.1111:j.1467-8659.2010.01768.x,

journal = {Computer Graphics Forum},
title = {{
Enhancing Bounding Volumes using Support Plane Mappings for Collision Detection}},

author = {
Athanasios Vogiannou
 and 
Konstantinos Moustakas
 and 
Dimitrios Tzovaras
 and 
Michael G. Strintzis
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01768.x}

}
                
@article{
10.1111:j.1467-8659.2010.01769.x,

journal = {Computer Graphics Forum},
title = {{
Fast and Scalable CPU/GPU Collision Detection for Rigid and Deformable Surfaces}},

author = {
Simon Pabst
 and 
Artur Koch
 and 
Wolfgang Strasser
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01769.x}

}
                
@article{
10.1111:j.1467-8659.2010.01771.x,

journal = {Computer Graphics Forum},
title = {{
Feature Preserving Mesh Generation from 3D Point Clouds}},

author = {
Nader Salman
 and 
Mariette Yvinec
 and 
Quentin Merigot
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01771.x}

}
                
@article{
10.1111:j.1467-8659.2010.01770.x,

journal = {Computer Graphics Forum},
title = {{
Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes}},

author = {
Marcel Campen
 and 
Leif Kobbelt
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01770.x}

}
                
@article{
10.1111:j.1467-8659.2010.01772.x,

journal = {Computer Graphics Forum},
title = {{
Globally Consistent Space-Time Reconstruction}},

author = {
Tiberiu Popa
 and 
Ian South-Dickinson
 and 
Derek Bradley
 and 
Alla Sheffer
 and 
Wolfgang Heidrich
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01772.x}

}
                
@article{
10.1111:j.1467-8659.2010.01773.x,

journal = {Computer Graphics Forum},
title = {{
High Fidelity Scan Merging}},

author = {
Julie Digne
 and 
Jean-Michel Morel
 and 
Nicolas Audfray
 and 
Claire Lartigue
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01773.x}

}
                
@article{
10.1111:j.1467-8659.2010.01774.x,

journal = {Computer Graphics Forum},
title = {{
Scales and Scale-like Structures}},

author = {
Eric Landreneau
 and 
Scott Schaefer
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01774.x}

}
                
@article{
10.1111:j.1467-8659.2010.01775.x,

journal = {Computer Graphics Forum},
title = {{
Fast Generation of Pointerless Octree Duals}},

author = {
Thomas Lewiner
 and 
Vinicius Mello
 and 
Adelailson Peixoto
 and 
Sinesio Pesco
 and 
Helio Lopes
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01775.x}

}
                
@article{
10.1111:j.1467-8659.2010.01776.x,

journal = {Computer Graphics Forum},
title = {{
Designing Quad-dominant Meshes with Planar Faces}},

author = {
Mirko Zadravec
 and 
Alexander Schiftner
 and 
Johannes Wallner
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01776.x}

}
                
@article{
10.1111:j.1467-8659.2010.01777.x,

journal = {Computer Graphics Forum},
title = {{
Closed-form Blending of Local Symmetries}},

author = {
Deboshmita Ghosh
 and 
Nina Amenta
 and 
Michael Kazhdan
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01777.x}

}
                
@article{
10.1111:j.1467-8659.2010.01779.x,

journal = {Computer Graphics Forum},
title = {{
On Discrete Killing Vector Fields and Patterns on Surfaces}},

author = {
Mirela Ben-Chen
 and 
Adrian Butscher
 and 
Justin Solomon
 and 
Leonidas Guibas
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01779.x}

}
                
@article{
10.1111:j.1467-8659.2010.01778.x,

journal = {Computer Graphics Forum},
title = {{
Moebius Transformations For Global Intrinsic Symmetry Analysis}},

author = {
Vladimir G. Kim
 and 
Yaron Lipman
 and 
Xiaobai Chen
 and 
Thomas Funkhouser
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01778.x}

}
                
@article{
10.1111:j.1467-8659.2010.01781.x,

journal = {Computer Graphics Forum},
title = {{
Localized Delaunay Refinement for Sampling and Meshing}},

author = {
Tamal K. Dey
 and 
Joshua A. Levine
 and 
Andrew Slatton
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01781.x}

}
                
@article{
10.1111:j.1467-8659.2010.01780.x,

journal = {Computer Graphics Forum},
title = {{
Multi-scale Geometric Modeling of Ambiguous Shapes with Toleranced Balls and Compoundly Weighted a-shapes}},

author = {
Frederic Cazals
 and 
Tom Dreyfus
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01780.x}

}
                
@article{
10.1111:j.1467-8659.2010.01782.x,

journal = {Computer Graphics Forum},
title = {{
Signing the Unsigned: Robust Surface Reconstruction from Raw Pointsets}},

author = {
Patrick Mullen
 and 
Fernando de Goes
 and 
Mathieu Desbrun
 and 
David Cohen-Steiner
 and 
Pierre Alliez
},
year = {
2010},

publisher = {

DOI = {
10.1111/j.1467-8659.2010.01782.x}

}

Browse

Recent Submissions

Now showing 1 - 25 of 25
  • Thumbnail Image
    Item
    Guest Editorial
    (The Eurographics Association and Blackwell Publishing Ltd, 2010)
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.