38-Issue 1

Permanent URI for this collection

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

Browse

Browsing 38-Issue 1 by Subject "computational geometry"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Incremental Labelling of Voronoi Vertices for Shape Reconstruction
    (© 2019 The Eurographics Association and John Wiley & Sons Ltd., 2019) Peethambaran, J.; Parakkat, A.D.; Tagliasacchi, A.; Wang, R.; Muthuganapathy, R.; Chen, Min and Benes, Bedrich
    We present an incremental Voronoi vertex labelling algorithm for approximating contours, medial axes and dominant points (high curvature points) from 2D point sets. Though there exist many number of algorithms for reconstructing curves, medial axes or dominant points, a unified framework capable of approximating all the three in one place from points is missing in the literature. Our algorithm estimates the normals at each sample point through poles (farthest Voronoi vertices of a sample point) and uses the estimated normals and the corresponding tangents to determine the spatial locations (inner or outer) of the Voronoi vertices with respect to the original curve. The vertex classification helps to construct a piece‐wise linear approximation to the object boundary. We provide a theoretical analysis of the algorithm for points non‐uniformly (ε‐sampling) sampled from simple, closed, concave and smooth curves. The proposed framework has been thoroughly evaluated for its usefulness using various test data. Results indicate that even sparsely and non‐uniformly sampled curves with outliers or collection of curves are faithfully reconstructed by the proposed algorithm.We present an incremental Voronoi vertex labelling algorithm for approximating contours, medial axes and dominant points (high curvature points) from 2D point sets. Though there exist many number of algorithms for reconstructing curves, medial axes or dominant points, a unified framework capable of approximating all the three in one place from points is missing in the literature. Our algorithm estimates the normals at each sample point through poles (farthest Voronoi vertices of a sample point) and uses the estimated normals and the corresponding tangents to determine the spatial locations (inner or outer) of the Voronoi vertices with respect to the original curve. The vertex classification helps to construct a piece‐wise linear approximation to the object boundary. We provide a theoretical analysis of the algorithm for points non‐uniformly (ε‐sampling) sampled from simple, closed, concave and smooth curves.
  • Thumbnail Image
    Item
    Selective Padding for Polycube‐Based Hexahedral Meshing
    (© 2019 The Eurographics Association and John Wiley & Sons Ltd., 2019) Cherchi, G.; Alliez, P.; Scateni, R.; Lyon, M.; Bommes, D.; Chen, Min and Benes, Bedrich
    Hexahedral meshes generated from polycube mapping often exhibit a low number of singularities but also poor‐quality elements located near the surface. It is thus necessary to improve the overall mesh quality, in terms of the minimum scaled Jacobian (MSJ) or average SJ (ASJ). Improving the quality may be obtained via global padding (or pillowing), which pushes the singularities inside by adding an extra layer of hexahedra on the entire domain boundary. Such a global padding operation suffers from a large increase of complexity, with unnecessary hexahedra added. In addition, the quality of elements near the boundary may decrease. We propose a novel optimization method which inserts sheets of hexahedra so as to perform selective padding, where it is most needed for improving the mesh quality. A sheet can pad part of the domain boundary, traverse the domain and form singularities. Our global formulation, based on solving a binary problem, enables us to control the balance between quality improvement, increase of complexity and number of singularities. We show in a series of experiments that our approach increases the MSJ value and preserves (or even improves) the ASJ, while adding fewer hexahedra than global padding.
  • Thumbnail Image
    Item
    A Survey of Simple Geometric Primitives Detection Methods for Captured 3D Data
    (© 2019 The Eurographics Association and John Wiley & Sons Ltd., 2019) Kaiser, Adrien; Ybanez Zepeda, Jose Alonso; Boubekeur, Tamy; Chen, Min and Benes, Bedrich
    The amount of captured 3D data is continuously increasing, with the democratization of consumer depth cameras, the development of modern multi‐view stereo capture setups and the rise of single‐view 3D capture based on machine learning. The analysis and representation of this ever growing volume of 3D data, often corrupted with acquisition noise and reconstruction artefacts, is a serious challenge at the frontier between computer graphics and computer vision. To that end, segmentation and optimization are crucial analysis components of the shape abstraction process, which can themselves be greatly simplified when performed on lightened geometric formats. In this survey, we review the algorithms which extract simple geometric primitives from raw dense 3D data. After giving an introduction to these techniques, from the acquisition modality to the underlying theoretical concepts, we propose an application‐oriented characterization, designed to help select an appropriate method based on one's application needs and compare recent approaches. We conclude by giving hints for how to evaluate these methods and a set of research challenges to be explored.
  • Thumbnail Image
    Item
    A Variational Approach to Registration with Local Exponential Coordinates
    (© 2019 The Eurographics Association and John Wiley & Sons Ltd., 2019) Paman, Ashish; Rangarajan, Ramsharan; Chen, Min and Benes, Bedrich
    We identify a novel parameterization for the group of finite rotations (SO), consisting of an atlas of exponential maps defined over local tangent planes, for the purpose of computing isometric transformations in registration problems that arise in machine vision applications. Together with a simple representation for translations, the resulting system of coordinates for rigid body motions is proper, free from singularities, is unrestricted in the magnitude of motions that can be represented and poses no difficulties in computer implementations despite their multi‐chart nature. Crucially, such a parameterization helps to admit varied types of data sets, to adopt data‐dependent error functionals for registration, seamlessly bridges correspondence and pose calculations, and inspires systematic variational procedures for computing optimal solutions. As a representative problem, we consider that of registering point clouds onto implicit surfaces without introducing any discretization of the latter. We derive coordinate‐free stationarity conditions, compute consistent linearizations, provide algorithms to compute optimal solutions and examine their performance with detailed examples. The algorithm generalizes naturally to registering curves and surfaces onto implicit manifolds, is directly adaptable to handle the familiar problem of pairwise registration of point clouds and allows for incorporating scale factors during registration.We identify a novel parameterization for the group of finite rotations (SO), consisting of an atlas of exponential maps defined over local tangent planes, for the purpose of computing isometric transformations in registration problems that arise in machine vision applications. Together with a simple representation for translations, the resulting system of coordinates for rigid body motions is proper, free from singularities, is unrestricted in the magnitude of motions that can be represented and poses no difficulties in computer implementations despite their multi‐chart nature. Crucially, such a parameterization helps to admit varied types of data sets, to adopt data‐dependent error functionals for registration, seamlessly bridges correspondence and pose calculations, and inspires systematic variational procedures for computing optimal solutions. As a representative problem, we consider that of registering point clouds onto implicit surfaces without introducing any discretization of the latter. We derive coordinate‐free stationarity conditions, compute consistent linearizations, provide algorithms to compute optimal solutions and examine their performance with detailed examples. The algorithm generalizes naturally to registering curves and surfaces onto implicit manifolds, is directly adaptable to handle the familiar problem of pairwise registration of point clouds and allows for incorporating scale factors during registration.