32-Issue 5

Permanent URI for this collection

https://diglib7.eg.org/handle/10.2312/183
Geometry Processing Proceedings

BibTeX (32-Issue 5)
                
@article{
http::/diglib.eg.org/handle/10.1111/000_frontmatter_sgp2013.pdf,

journal = {Computer Graphics Forum},
title = {{
Preface and Table of Contents}},

author = {},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
http://diglib.eg.org/handle/10.1111/000_frontmatter_sgp2013.pdf}

}
                
@article{
10.1111:cgf.12167,

journal = {Computer Graphics Forum},
title = {{
Shape Matching via Quotient Spaces}},

author = {
Ovsjanikov, Maks
 and 
Mérigot, Quentin
 and 
Patraucean, Viorica
 and 
Guibas, Leonidas
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12167}

}
                
@article{
10.1111:cgf.12168,

journal = {Computer Graphics Forum},
title = {{
PHOG: Photometric and Geometric Functions for Textured Shape Retrieval}},

author = {
Biasotti, Silvia
 and 
Cerri, Andrea
 and 
Giorgi, Daniela
 and 
Spagnuolo, Michaela
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12168}

}
                
@article{
10.1111:cgf.12170,

journal = {Computer Graphics Forum},
title = {{
Semantizing Complex 3D Scenes using Constrained Attribute Grammars}},

author = {
Boulch, Alexandre
 and 
Houllier, Simon
 and 
Marlet, Renaud
 and 
Tournaire, Olivier
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12170}

}
                
@article{
10.1111:cgf.12169,

journal = {Computer Graphics Forum},
title = {{
Weak Convex Decomposition by Lines-of-sight}},

author = {
Asafi, Shmuel
 and 
Goren, Avi
 and 
Cohen-Or, Daniel
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12169}

}
                
@article{
10.1111:cgf.12171,

journal = {Computer Graphics Forum},
title = {{
Connectivity Editing for Quad-Dominant Meshes}},

author = {
Peng, Chi-Han
 and 
Wonka, Peter
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12171}

}
                
@article{
10.1111:cgf.12174,

journal = {Computer Graphics Forum},
title = {{
An Operator Approach to Tangent Vector Field Processing}},

author = {
Azencot, Omri
 and 
Ben-Chen, Mirela
 and 
Chazal, Frédéric
 and 
Ovsjanikov, Maks
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12174}

}
                
@article{
10.1111:cgf.12173,

journal = {Computer Graphics Forum},
title = {{
Practical Anisotropic Geodesy}},

author = {
Campen, Marcel
 and 
Heistermann, Martin
 and 
Kobbelt, Leif
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12173}

}
                
@article{
10.1111:cgf.12172,

journal = {Computer Graphics Forum},
title = {{
Discrete Line Congruences for Shading and Lighting}},

author = {
Wang, Jun
 and 
Jiang, Caigui
 and 
Bompas, Philippe
 and 
Wallner, Johannes
 and 
Pottmann,  Hellmut
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12172}

}
                
@article{
10.1111:cgf.12176,

journal = {Computer Graphics Forum},
title = {{
Fast and Robust Approximation of Smallest Enclosing Balls in Arbitrary Dimensions}},

author = {
Larsson, Thomas
 and 
Källberg, Linus
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12176}

}
                
@article{
10.1111:cgf.12175,

journal = {Computer Graphics Forum},
title = {{
Approximating Functions on a Mesh with Restricted Voronoï Diagrams}},

author = {
Nivoliers, Vincent
 and 
Lévy, Bruno
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12175}

}
                
@article{
10.1111:cgf.12177,

journal = {Computer Graphics Forum},
title = {{
Fitting Polynomial Volumes to Surface Meshes with Voronoï Squared Distance Minimization}},

author = {
Paillé, Gilles-Philippe
 and 
Poulin, Pierre
 and 
Lévy, Bruno
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12177}

}
                
@article{
10.1111:cgf.12178,

journal = {Computer Graphics Forum},
title = {{
Sparse Iterative Closest Point}},

author = {
Bouaziz, Sofien
 and 
Tagliasacchi, Andrea
 and 
Pauly, Mark
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12178}

}
                
@article{
10.1111:cgf.12179,

journal = {Computer Graphics Forum},
title = {{
Locally Injective Mappings}},

author = {
Schüller, Christian
 and 
Kavan, Ladislav
 and 
Panozzo, Daniele
 and 
Sorkine-Hornung, Olga
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12179}

}
                
@article{
10.1111:cgf.12180,

journal = {Computer Graphics Forum},
title = {{
Bijective Composite Mean Value Mappings}},

author = {
Schneider, Teseo
 and 
Hormann, Kai
 and 
Floater, Michael S.
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12180}

}
                
@article{
10.1111:cgf.12182,

journal = {Computer Graphics Forum},
title = {{
An Algorithm for Triangulating Multiple 3D Polygons}},

author = {
Zou, Ming
 and 
Ju, Tao
 and 
Carr, Nathan
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12182}

}
                
@article{
10.1111:cgf.12181,

journal = {Computer Graphics Forum},
title = {{
Consistent Volumetric Discretizations Inside Self-Intersecting Surfaces}},

author = {
Sacht, Leonardo
 and 
Jacobson, Alec
 and 
Panozzo, Daniele
 and 
Schüller, Christian
 and 
Sorkine-Hornung, Olga
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12181}

}
                
@article{
10.1111:cgf.12183,

journal = {Computer Graphics Forum},
title = {{
Animation-Aware Quadrangulation}},

author = {
Marcias, Giorgio
 and 
Pietroni, Nico
 and 
Panozzo, Daniele
 and 
Puppo, Enrico
 and 
Sorkine-Hornung, Olga
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12183}

}
                
@article{
10.1111:cgf.12184,

journal = {Computer Graphics Forum},
title = {{
Consistent Shape Maps via Semidefinite Programming}},

author = {
Huang, Qi-Xing
 and 
Guibas, Leonidas
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12184}

}
                
@article{
10.1111:cgf.12185,

journal = {Computer Graphics Forum},
title = {{
Dynamic Maps for Exploring and Browsing Shapes}},

author = {
Kleiman, Yanir
 and 
Fish, Noa
 and 
Lanir, Joel
 and 
Cohen-Or, Daniel
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12185}

}
                
@article{
10.1111:cgf.12186,

journal = {Computer Graphics Forum},
title = {{
Dirichlet Energy for Analysis and Synthesis of Soft Maps}},

author = {
Solomon, Justin
 and 
Guibas, Leonidas
 and 
Butscher, Adrian
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12186}

}
                
@article{
10.1111:cgf.12187,

journal = {Computer Graphics Forum},
title = {{
Consolidation of Low-quality Point Clouds from Outdoor Scenes}},

author = {
Wang, Jun
 and 
Xu, Kai
 and 
Liu, Ligang
 and 
Cao, Junjie
 and 
Liu, Shengjun
 and 
Yu, Zeyun
 and 
Gu, Xianfeng David
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12187}

}
                
@article{
10.1111:cgf.12188,

journal = {Computer Graphics Forum},
title = {{
Watertight Scenes from Urban LiDAR and Planar Surfaces}},

author = {
Kreveld, Marc van
 and 
Lankveld, Thijs van
 and 
Veltkamp, Remco C.
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12188}

}
                
@article{
10.1111:cgf.12189,

journal = {Computer Graphics Forum},
title = {{
Noise-Adaptive Shape Reconstruction from Raw Point Sets}},

author = {
Giraudot, Simon
 and 
Cohen-Steiner, David
 and 
Alliez, Pierre
},
year = {
2013},

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


ISSN = {1467-8659},

DOI = {
10.1111/cgf.12189}

}

Browse

Recent Submissions

Now showing 1 - 24 of 24
  • Thumbnail Image
    Item
    Preface and Table of Contents
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Yaron Lipman and Hao Zhang
  • Thumbnail Image
    Item
    Shape Matching via Quotient Spaces
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Ovsjanikov, Maks; Mérigot, Quentin; Patraucean, Viorica; Guibas, Leonidas; Yaron Lipman and Hao Zhang
    We introduce a novel method for non-rigid shape matching, designed to address the symmetric ambiguity problem present when matching shapes with intrinsic symmetries. Unlike the majority of existing methods which try to overcome this ambiguity by sampling a set of landmark correspondences, we address this problem directly by performing shape matching in an appropriate quotient space, where the symmetry has been identified and factored out. This allows us to both simplify the shape matching problem by matching between subspaces, and to return multiple solutions with equally good dense correspondences. Remarkably, both symmetry detection and shape matching are done without establishing any landmark correspondences between either points or parts of the shapes. This allows us to avoid an expensive combinatorial search present in most intrinsic symmetry detection and shape matching methods. We compare our technique with state-of-the-art methods and show that superior performance can be achieved both when the symmetry on each shape is known and when it needs to be estimated.
  • Thumbnail Image
    Item
    PHOG: Photometric and Geometric Functions for Textured Shape Retrieval
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Biasotti, Silvia; Cerri, Andrea; Giorgi, Daniela; Spagnuolo, Michaela; Yaron Lipman and Hao Zhang
    In this paper we target the problem of textured 3D object retrieval. As a first contribution, we show how to include photometric information in the persistence homology setting, also proposing a novel theoretical result about multidimensional persistence spaces. As a second contribution, we introduce a generalization of the integral geodesic distance which fuses shape and color properties. Finally, we adopt a purely geometric description based on the selection of geometric functions that are mutually independent. The photometric, hybrid and geometric descriptions are combined into a signature, whose performance is tested on a benchmark dataset.
  • Thumbnail Image
    Item
    Semantizing Complex 3D Scenes using Constrained Attribute Grammars
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Boulch, Alexandre; Houllier, Simon; Marlet, Renaud; Tournaire, Olivier; Yaron Lipman and Hao Zhang
    We propose a new approach to automatically semantize complex objects in a 3D scene. For this, we define an expressive formalism combining the power of both attribute grammars and constraint. It offers a practical conceptual interface, which is crucial to write large maintainable specifications. As recursion is inadequate to express large collections of items, we introduce maximal operators, that are essential to reduce the parsing search space. Given a grammar in this formalism and a 3D scene, we show how to automatically compute a shared parse forest of all interpretations - in practice, only a few, thanks to relevant constraints. We evaluate this technique for building model semantization using CAD model examples as well as photogrammetric and simulated LiDAR data.
  • Thumbnail Image
    Item
    Weak Convex Decomposition by Lines-of-sight
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Asafi, Shmuel; Goren, Avi; Cohen-Or, Daniel; Yaron Lipman and Hao Zhang
    We define the convexity rank of a set of points to be the portion of mutually visible pairs of points out of the total number of pairs. Based on this definition of weak convexity, we introduce a spectral method that decomposes a given shape into weakly convex regions. The decomposition is applied without explicitly measuring the convexity rank. The method merely amounts to a spectral clustering of a matrix representing the all-pairs line of sight. Our method can be directly applied on an oriented point cloud and does not require any topological information, nor explicit concavity or convexity measures. We demonstrate the efficiency of our algorithm on a large number of examples and compare them qualitatively with competitive approaches.
  • Thumbnail Image
    Item
    Connectivity Editing for Quad-Dominant Meshes
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Peng, Chi-Han; Wonka, Peter; Yaron Lipman and Hao Zhang
    We propose a connectivity editing framework for quad-dominant meshes. In our framework, the user can edit the mesh connectivity to control the location, type, and number of irregular vertices (with more or fewer than four neighbors) and irregular faces (non-quads). We provide a theoretical analysis of the problem, discuss what edits are possible and impossible, and describe how to implement an editing framework that realizes all possible editing operations. In the results, we show example edits and illustrate the advantages and disadvantages of different strategies for quad-dominant mesh design.
  • Thumbnail Image
    Item
    An Operator Approach to Tangent Vector Field Processing
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Azencot, Omri; Ben-Chen, Mirela; Chazal, Frédéric; Ovsjanikov, Maks; Yaron Lipman and Hao Zhang
    In this paper, we introduce a novel coordinate-free method for manipulating and analyzing vector fields on discrete surfaces. Unlike the commonly used representations of a vector field as an assignment of vectors to the faces of the mesh, or as real values on edges, we argue that vector fields can also be naturally viewed as operators whose domain and range are functions defined on the mesh. Although this point of view is common in differential geometry it has so far not been adopted in geometry processing applications. We recall the theoretical properties of vector fields represented as operators, and show that composition of vector fields with other functional operators is natural in this setup. This leads to the characterization of vector field properties through commutativity with other operators such as the Laplace-Beltrami and symmetry operators, as well as to a straight-forward definition of differential properties such as the Lie derivative. Finally, we demonstrate a range of applications, such as Killing vector field design, symmetric vector field estimation and joint design on multiple surfaces.
  • Thumbnail Image
    Item
    Practical Anisotropic Geodesy
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Campen, Marcel; Heistermann, Martin; Kobbelt, Leif; Yaron Lipman and Hao Zhang
    The computation of intrinsic, geodesic distances and geodesic paths on surfaces is a fundamental low-level building block in countless Computer Graphics and Geometry Processing applications. This demand led to the development of numerous algorithms - some for the exact, others for the approximative computation, some focussing on speed, others providing strict guarantees. Most of these methods are designed for computing distances according to the standard Riemannian metric induced by the surface's embedding in Euclidean space. Generalization to other, especially anisotropic, metrics - which more recently gained interest in several application areas - is not rarely hampered by fundamental problems. We explore and discuss possibilities for the generalization and extension of well-known methods to the anisotropic case, evaluate their relative performance in terms of accuracy and speed, and propose a novel algorithm, the Short-Term Vector Dijkstra. This algorithm is strikingly simple to implement and proves to provide practical accuracy at a higher speed than generalized previous methods.
  • Thumbnail Image
    Item
    Discrete Line Congruences for Shading and Lighting
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Wang, Jun; Jiang, Caigui; Bompas, Philippe; Wallner, Johannes; Pottmann, Hellmut; Yaron Lipman and Hao Zhang
    Two-parameter families of straight lines (line congruences) are implicitly present in graphics and geometry processing in several important ways including lighting and shape analysis. In this paper we make them accessible to optimization and geometric computing, by introducing a general discrete version of congruences based on piecewise-linear correspondences between triangle meshes. Our applications of congruences are based on the extraction of a so-called torsion-free support structure, which is a procedure analogous to remeshing a surface along its principal curvature lines. A particular application of such structures are freeform shading and lighting systems for architecture. We combine interactive design of such systems with global optimization in order to satisfy geometric constraints. In this way we explore a new area where architecture can greatly benefit from graphics.
  • Thumbnail Image
    Item
    Fast and Robust Approximation of Smallest Enclosing Balls in Arbitrary Dimensions
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Larsson, Thomas; Källberg, Linus; Yaron Lipman and Hao Zhang
    In this paper, an algorithm is introduced that computes an arbitrarily fine approximation of the smallest enclosing ball of a point set in any dimension. This operation is important in, for example, classification, clustering, and data mining. The algorithm is very simple to implement, gives reliable results, and gracefully handles large problem instances in low and high dimensions, as confirmed by both theoretical arguments and empirical evaluation. For example, using a CPU with eight cores, it takes less than two seconds to compute a 1:001-approximation of the smallest enclosing ball of one million points uniformly distributed in a hypercube in dimension 200. Furthermore, the presented approach extends to a more general class of input objects, such as ball sets.
  • Thumbnail Image
    Item
    Approximating Functions on a Mesh with Restricted Voronoï Diagrams
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Nivoliers, Vincent; Lévy, Bruno; Yaron Lipman and Hao Zhang
    We propose a method that computes a piecewise constant approximation of a function defined on a mesh. The approximation is associated with the cells of a restricted Voronoï diagram. Our method optimizes an objective function measuring the quality of the approximation. This objective function depends on the placement of the samples that define the restricted Voronoï diagram and their associated function values. We study the continuity of the objective function, derive the closed-form expression of its derivatives and use them to design a numerical solution mechanism. The method can be applied to a function that has discontinuities, and the result aligns the boundaries of the Voronoï cells with the discontinuities. Some examples are shown, suggesting potential applications in image vectorization and compact representation of lighting.
  • Thumbnail Image
    Item
    Fitting Polynomial Volumes to Surface Meshes with Voronoï Squared Distance Minimization
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Paillé, Gilles-Philippe; Poulin, Pierre; Lévy, Bruno; Yaron Lipman and Hao Zhang
    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.
  • Thumbnail Image
    Item
    Sparse Iterative Closest Point
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Bouaziz, Sofien; Tagliasacchi, Andrea; Pauly, Mark; Yaron Lipman and Hao Zhang
    Rigid registration of two geometric data sets is essential in many applications, including robot navigation, surface reconstruction, and shape matching. Most commonly, variants of the Iterative Closest Point (ICP) algorithm are employed for this task. These methods alternate between closest point computations to establish correspondences between two data sets, and solving for the optimal transformation that brings these correspondences into alignment. A major difficulty for this approach is the sensitivity to outliers and missing data often observed in 3D scans. Most practical implementations of the ICP algorithm address this issue with a number of heuristics to prune or reweight correspondences. However, these heuristics can be unreliable and difficult to tune, which often requires substantial manual assistance. We propose a new formulation of the ICP algorithm that avoids these difficulties by formulating the registration optimization using sparsity inducing norms. Our new algorithm retains the simple structure of the ICP algorithm, while achieving superior registration results when dealing with outliers and incomplete data. The complete source code of our implementation is provided at http://lgg.epfl.ch/sparseicp.
  • Thumbnail Image
    Item
    Locally Injective Mappings
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Schüller, Christian; Kavan, Ladislav; Panozzo, Daniele; Sorkine-Hornung, Olga; Yaron Lipman and Hao Zhang
    Mappings and deformations are ubiquitous in geometry processing, shape modeling, and animation. Numerous deformation energies have been proposed to tackle problems like mesh parameterization and volumetric deformations. We present an algorithm that modifies any deformation energy to guarantee a locally injective mapping, i.e., without inverted elements. Our formulation can be used to compute continuous planar or volumetric piecewise-linear maps and it uses a barrier term to prevent inverted elements. Differently from previous methods, we carefully design both the barrier term and the associated numerical techniques to be able to provide immediate feedback to the user, enabling interactive manipulation of inversion-free mappings. Stress tests show that our method robustly handles extreme deformations where previous techniques converge very slowly or even fail. We demonstrate that enforcing local injectivity increases fidelity of the results in applications such as shape deformation and parameterization.
  • Thumbnail Image
    Item
    Bijective Composite Mean Value Mappings
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Schneider, Teseo; Hormann, Kai; Floater, Michael S.; Yaron Lipman and Hao Zhang
    We introduce the novel concept of composite barycentric mappings and give theoretical conditions under which they are guaranteed to be bijective. We then focus on mean value mappings and derive a simple procedure for computing their Jacobians, leading to an efficient GPU-assisted implementation for interactively designing composite mean value mappings which are bijective up to pixel resolution. We provide a number of examples of 2D image deformation and an example of 3D shape deformation based on a natural extension of the concept to spatial mappings.
  • Thumbnail Image
    Item
    An Algorithm for Triangulating Multiple 3D Polygons
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Zou, Ming; Ju, Tao; Carr, Nathan; Yaron Lipman and Hao Zhang
    We present an algorithm for obtaining a triangulation of multiple, non-planar 3D polygons. The output minimizes additive weights, such as the total triangle areas or the total dihedral angles between adjacent triangles. Our algorithm generalizes a classical method for optimally triangulating a single polygon. The key novelty is a mechanism for avoiding non-manifold outputs for two and more input polygons without compromising optimality. For better performance on real-world data, we also propose an approximate solution by feeding the algorithm with a reduced set of triangles. In particular, we demonstrate experimentally that the triangles in the Delaunay tetrahedralization of the polygon vertices offer a reasonable trade off between performance and optimality.
  • Thumbnail Image
    Item
    Consistent Volumetric Discretizations Inside Self-Intersecting Surfaces
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Sacht, Leonardo; Jacobson, Alec; Panozzo, Daniele; Schüller, Christian; Sorkine-Hornung, Olga; Yaron Lipman and Hao Zhang
    Decades of research have culminated in a robust geometry processing pipeline for surfaces. Most steps in this pipeline, like deformation, smoothing, subdivision and decimation, may create self-intersections. Volumetric processing of solid shapes then becomes difficult, because obtaining a correct volumetric discretization is impossible: existing tet-meshing methods require watertight input. We propose an algorithm that produces a tetrahedral mesh that overlaps itself consistently with the self-intersections in the input surface. This enables volumetric processing on self-intersecting models. We leverage conformalized mean-curvature flow, which removes self-intersections, and define an intrinsically similar reverse flow, which prevents them. We tetrahedralize the resulting surface and map the mesh inside the original surface. We demonstrate the effectiveness of our method with applications to automatic skinning weight computation, physically based simulation and geodesic distance computation.
  • Thumbnail Image
    Item
    Animation-Aware Quadrangulation
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Marcias, Giorgio; Pietroni, Nico; Panozzo, Daniele; Puppo, Enrico; Sorkine-Hornung, Olga; Yaron Lipman and Hao Zhang
    Geometric meshes that model animated characters must be designed while taking into account the deformations that the shape will undergo during animation. We analyze an input sequence of meshes with point-to-point correspondence, and we automatically produce a quadrangular mesh that fits well the input animation. We first analyze the local deformation that the surface undergoes at each point, and we initialize a cross field that remains as aligned as possible to the principal directions of deformation throughout the sequence. We then smooth this cross field based on an energy that uses a weighted combination of the initial field and the local amount of stretch. Finally, we compute a field-aligned quadrangulation with an off-the-shelf method. Our technique is fast and very simple to implement, and it significantly improves the quality of the output quad mesh and its suitability for character animation, compared to creating the quad mesh based on a single pose. We present experimental results and comparisons with a state-of-the-art quadrangulation method, on both sequences from 3D scanning and synthetic sequences obtained by a rough animation of a triangulated model.
  • Thumbnail Image
    Item
    Consistent Shape Maps via Semidefinite Programming
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Huang, Qi-Xing; Guibas, Leonidas; Yaron Lipman and Hao Zhang
    Recent advances in shape matching have shown that jointly optimizing the maps among the shapes in a collection can lead to significant improvements when compared to estimating maps between pairs of shapes in isolation. These methods typically invoke a cycle-consistency criterion - the fact that compositions of maps along a cycle of shapes should approximate the identity map. This condition regularizes the network and allows for the correction of errors and imperfections in individual maps. In particular, it encourages the estimation of maps between dissimilar shapes by compositions of maps along a path of more similar shapes. In this paper, we introduce a novel approach for obtaining consistent shape maps in a collection that formulates the cycle-consistency constraint as the solution to a semidefinite program (SDP). The proposed approach is based on the observation that, if the ground truth maps between the shapes are cycle-consistent, then the matrix that stores all pair-wise maps in blocks is low-rank and positive semidefinite. Motivated by recent advances in techniques for low-rank matrix recovery via semidefinite programming, we formulate the problem of estimating cycle-consistent maps as finding the closest positive semidefinite matrix to an input matrix that stores all the initial maps. By analyzing the Karush-Kuhn-Tucker (KKT) optimality condition of this program, we derive theoretical guarantees for the proposed algorithm, ensuring the correctness of the recovery when the errors in the inputs maps do not exceed certain thresholds. Besides this theoretical guarantee, experimental results on benchmark datasets show that the proposed approach outperforms state-of-the-art multiple shape matching methods.
  • Thumbnail Image
    Item
    Dynamic Maps for Exploring and Browsing Shapes
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Kleiman, Yanir; Fish, Noa; Lanir, Joel; Cohen-Or, Daniel; Yaron Lipman and Hao Zhang
    Large datasets of 3D objects require an intuitive way to browse and quickly explore shapes from the collection. We present a dynamic map of shapes where similar shapes are placed next to each other. Similarity between 3D models exists in a high dimensional space which cannot be accurately expressed in a two dimensional map. We solve this discrepancy by providing a local map with pan capabilities and a user interface that resembles an online experience of navigating through geographical maps. As the user navigates through the map, new shapes appear which correspond to the specific navigation tendencies and interests of the user, while maintaining a continuous browsing experience. In contrast with state of the art methods which typically reduce the search space by selecting constraints or employing relevance feedback, our method enables exploration of large sets without constraining the search space, allowing the user greater creativity and serendipity. A user study evaluation showed a strong preference of users for our method over a standard relevance feedback method.
  • Thumbnail Image
    Item
    Dirichlet Energy for Analysis and Synthesis of Soft Maps
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Solomon, Justin; Guibas, Leonidas; Butscher, Adrian; Yaron Lipman and Hao Zhang
    Soft maps taking points on one surface to probability distributions on another are attractive for representing surface mappings in the presence of symmetry, ambiguity, and combinatorial complexity. Few techniques, however, are available to measure their continuity and other properties. To this end, we introduce a novel Dirichlet energy for soft maps generalizing the classical map Dirichlet energy, which measures distortion by computing how soft maps transport probabilistic mass from one distribution to another. We formulate the computation of the Dirichlet energy in terms of a differential equation and provide a finite elements discretization that enables all of the quantities introduced to be computed. We demonstrate the effectiveness of our framework for understanding soft maps arising from various sources. Furthermore, we suggest how these energies can be applied to generate continuous soft or point-to-point maps.
  • Thumbnail Image
    Item
    Consolidation of Low-quality Point Clouds from Outdoor Scenes
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Wang, Jun; Xu, Kai; Liu, Ligang; Cao, Junjie; Liu, Shengjun; Yu, Zeyun; Gu, Xianfeng David; Yaron Lipman and Hao Zhang
    The emergence of laser/LiDAR sensors, reliable multi-view stereo techniques and more recently consumer depth cameras have brought point clouds to the forefront as a data format useful for a number of applications. Unfortunately, the point data from those channels often incur imperfection, frequently contaminated with severe outliers and noise. This paper presents a robust consolidation algorithm for low-quality point data from outdoor scenes, which essentially consists of two steps: 1) outliers filtering and 2) noise smoothing. We first design a connectivitybased scheme to evaluate outlierness and thereby detect sparse outliers. Meanwhile, a clustering method is used to further remove small dense outliers. Both outlier removal methods are insensitive to the choice of the neighborhood size and the levels of outliers. Subsequently, we propose a novel approach to estimate normals for noisy points based on robust partial rankings, which is the basis of noise smoothing. Accordingly, a fast approach is exploited to smooth noise, while preserving sharp features. We evaluate the effectiveness of the proposed method on the point clouds from a variety of outdoor scenes.
  • Thumbnail Image
    Item
    Watertight Scenes from Urban LiDAR and Planar Surfaces
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Kreveld, Marc van; Lankveld, Thijs van; Veltkamp, Remco C.; Yaron Lipman and Hao Zhang
    The demand for large geometric models is increasing, especially of urban environments. This has resulted in production of massive point cloud data from images or LiDAR. Visualization and further processing generally require a detailed, yet concise representation of the scene's surfaces. Related work generally either approximates the data with the risk of over-smoothing, or interpolates the data with excessive detail. Many surfaces in urban scenes can be modeled more concisely by planar approximations. We present a method that combines these polygons into a watertight model. The polygon-based shape is closed with free-form meshes based on visibility information. To achieve this, we divide 3-space into inside and outside volumes by combining a constrained Delaunay tetrahedralization with a graph-cut. We compare our method with related work on several large urban LiDAR data sets. We construct similar shapes with a third fewer triangles to model the scenes. Additionally, our results are more visually pleasing and closer to a human modeler's description of urban scenes using simple boxes.
  • Thumbnail Image
    Item
    Noise-Adaptive Shape Reconstruction from Raw Point Sets
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Giraudot, Simon; Cohen-Steiner, David; Alliez, Pierre; Yaron Lipman and Hao Zhang
    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.