41-Issue 1

Permanent URI for this collection

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

Browse

Browsing 41-Issue 1 by Subject "computational geometry"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    At‐Most‐Hexa Meshes
    (© 2022 Eurographics ‐ The European Association for Computer Graphics and John Wiley & Sons Ltd, 2022) Bukenberger, Dennis R.; Tarini, Marco; Lensch, Hendrik P. A.; Hauser, Helwig and Alliez, Pierre
    Volumetric polyhedral meshes are required in many applications, especially for solving partial differential equations on finite element simulations. Still, their construction bears several additional challenges compared to boundary‐based representations. Tetrahedral meshes and (pure) hex‐meshes are two popular formats in scenarios like CAD applications, offering opposite advantages and disadvantages. Hex‐meshes are more intricate to construct due to the global structure of the meshing, but feature much better regularity, alignment, are more expressive, and offer the same simulation accuracy with fewer elements. Hex‐dominant meshes, where most but not all cell elements have a hexahedral structure, constitute an attractive compromise, potentially unlocking benefits from both structures, but their generality makes their employment in downstream applications difficult. In this work, we introduce a strict subset of general hex‐dominant meshes, which we term ‘at‐most‐hexa meshes’, in which most cells are still hexahedral, but no cell has more than six boundary faces, and no face has more than four sides. We exemplify the ease of construction of at‐most‐hexa meshes by proposing a frugal and straightforward method to generate high‐quality meshes of this kind, starting directly from hulls or point clouds, for example, from a 3D scan. In contrast to existing methods for (pure) hexahedral meshing, ours does not require an intermediate parameterization of other costly pre‐computations and can start directly from surfaces or samples. We leverage a Lloyd relaxation process to exploit the synergistic effects of aligning an orientation field in a modified 3D Voronoi diagram using the norm for cubical cells. The extracted geometry incorporates regularity as well as feature alignment, following sharp edges and curved boundary surfaces. We introduce specialized operations on the three‐dimensional graph structure to enforce consistency during the relaxation. The resulting algorithm allows for an efficient evaluation with parallel algorithms on GPU hardware and completes even large reconstructions within minutes.
  • Thumbnail Image
    Item
    Complex Functional Maps: A Conformal Link Between Tangent Bundles
    (© 2022 Eurographics ‐ The European Association for Computer Graphics and John Wiley & Sons Ltd, 2022) Donati, Nicolas; Corman, Etienne; Melzi, Simone; Ovsjanikov, Maks; Hauser, Helwig and Alliez, Pierre
    In this paper, we introduce complex functional maps, which extend the functional map framework to conformal maps between tangent vector fields on surfaces. A key property of these maps is their . More specifically, we demonstrate that unlike regular functional maps that link of two manifolds, our complex functional maps establish a link between , thus permitting robust and efficient transfer of tangent vector fields. By first endowing and then exploiting the tangent bundle of each shape with a complex structure, the resulting operations become naturally orientation‐aware, thus favouring across shapes, without relying on descriptors or extra regularization. Finally, and perhaps more importantly, we demonstrate how these objects enable several practical applications within the functional map framework. We show that functional maps and their complex counterparts can be estimated jointly to promote orientation preservation, regularizing pipelines that previously suffered from orientation‐reversing symmetry errors.
  • Thumbnail Image
    Item
    Economic Upper Bound Estimation in Hausdorff Distance Computation for Triangle Meshes
    (© 2022 Eurographics ‐ The European Association for Computer Graphics and John Wiley & Sons Ltd, 2022) Zheng, Yicun; Sun, Haoran; Liu, Xinguo; Bao, Hujun; Huang, Jin; Hauser, Helwig and Alliez, Pierre
    The Hausdorff distance is one of the most fundamental metrics for comparing 3D shapes. To compute the Hausdorff distance efficiently from a triangular mesh to another triangular mesh , one needs to cull the unnecessary triangles on quickly. These triangles have no chance to improve the Hausdorff distance estimation, that is the parts with local upper bound smaller than the global lower bound. The local upper bound estimation should be tight, use fast distance computation, and involve a small number of triangles in during the reduction phase for efficiency. In this paper, we propose to use point‐triangle distance, and only involve at most four triangles in in the reduction phase. Comparing with the state‐of‐the‐art proposed by Tang et al. in 2009, which uses more costly triangle‐triangle distance and may involve a large number of triangles in reduction phase, our local upper bound estimation is faster, and with only a small impact on the tightness of the bound on error estimation. Such a more economic strategy boosts the overall performance significantly. Experiments on the Thingi10K dataset show that our method can achieve several (even over 20) times speedup on average. On a few models with different placements and resolutions, we show that close placement and large difference in resolution bring big challenges to Hausdorff distance computation, and explain why our method can achieve more significant speedup on challenging cases.