36-Issue 5

Permanent URI for this collection

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

Browse

Browsing 36-Issue 5 by Subject "Computational Geometry and Object Modeling"

Now showing 1 - 7 of 7
  • No Thumbnail Available
    Item
    A Constrained Resampling Strategy for Mesh Improvement
    (The Eurographics Association and John Wiley & Sons Ltd., 2017) Abdelkader, Ahmed; Mahmoud, Ahmed H.; Rushdi, Ahmad A.; Mitchell, Scott A.; Owens, John D.; Ebeida, Mohamed S.; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
    In many geometry processing applications, it is required to improve an initial mesh in terms of multiple quality objectives. Despite the availability of several mesh generation algorithms with provable guarantees, such generated meshes may only satisfy a subset of the objectives. The conflicting nature of such objectives makes it challenging to establish similar guarantees for each combination, e.g., angle bounds and vertex count. In this paper, we describe a versatile strategy for mesh improvement by interpreting quality objectives as spatial constraints on resampling and develop a toolbox of local operators to improve the mesh while preserving desirable properties. Our strategy judiciously combines smoothing and transformation techniques allowing increased flexibility to practically achieve multiple objectives simultaneously. We apply our strategy to both planar and surface meshes demonstrating how to simplify Delaunay meshes while preserving element quality, eliminate all obtuse angles in a complex mesh, and maximize the shortest edge length in a Voronoi tessellation far better than the state-of-the-art.
  • No Thumbnail Available
    Item
    Fast and Memory-Efficient Voronoi Diagram Construction on Triangle Meshes
    (The Eurographics Association and John Wiley & Sons Ltd., 2017) Qin, Yipeng; Yu, Hongchuan; Zhang, Jiangjun; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
    Geodesic based Voronoi diagrams play an important role in many applications of computer graphics. Constructing such Voronoi diagrams usually resorts to exact geodesics. However, exact geodesic computation always consumes lots of time and memory, which has become the bottleneck of constructing geodesic based Voronoi diagrams. In this paper, we propose the window-VTP algorithm, which can effectively reduce redundant computation and save memory. As a result, constructing Voronoi diagrams using the proposed window-VTP algorithm runs 3-8 times faster than Liu et al.'s method [LCT11], 1.2 times faster than its FWP-MMP variant and more importantly uses 10-70 times less memory than both of them.
  • No Thumbnail Available
    Item
    Fast Planar Harmonic Deformations with Alternating Tangential Projections
    (The Eurographics Association and John Wiley & Sons Ltd., 2017) Hefetz, Eden Fedida; Chien, Edward; Weber, Ofir; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
    We present a planar harmonic cage-based deformation method with local injectivity and bounded distortion guarantees, that is significantly faster than state-of-the-art methods with similar guarantees, and allows for real-time interaction. With a convex proxy for a near-convex characterization of the bounded distortion harmonic mapping space from [LW16], we utilize a modified alternating projection method (referred to as ATP) to project to this proxy. ATP draws inspiration from [KABL15] and restricts every other projection to lie in a tangential hyperplane. In contrast to [KABL15], our convex setting allows us to show that ATP is provably convergent (and is locally injective). Compared to the standard alternating projection method, it demonstrates superior convergence in fewer iterations, and it is also embarrassingly parallel, allowing for straightforward GPU implementation. Both of these factors combine to result in unprecedented speed. The convergence proof generalizes to arbitrary pairs of intersecting convex sets, suggesting potential use in other applications. Additional theoretical results sharpen the near-convex characterization that we use and demonstrate that it is homeomorphic to the bounded distortion harmonic mapping space (instead of merely being bijective).
  • No Thumbnail Available
    Item
    GWCNN: A Metric Alignment Layer for Deep Shape Analysis
    (The Eurographics Association and John Wiley & Sons Ltd., 2017) Ezuz, Danielle; Solomon, Justin; Kim, Vladimir G.; Ben-Chen, Mirela; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
    Deep neural networks provide a promising tool for incorporating semantic information in geometry processing applications. Unlike image and video processing, however, geometry processing requires handling unstructured geometric data, and thus data representation becomes an important challenge in this framework. Existing approaches tackle this challenge by converting point clouds, meshes, or polygon soups into regular representations using, e.g., multi-view images, volumetric grids or planar parameterizations. In each of these cases, geometric data representation is treated as a fixed pre-process that is largely disconnected from the machine learning tool. In contrast, we propose to optimize for the geometric representation during the network learning process using a novel metric alignment layer. Our approach maps unstructured geometric data to a regular domain by minimizing the metric distortion of the map using the regularized Gromov-Wasserstein objective. This objective is parameterized by the metric of the target domain and is differentiable; thus, it can be easily incorporated into a deep network framework. Furthermore, the objective aims to align the metrics of the input and output domains, promoting consistent output for similar shapes. We show the effectiveness of our layer within a deep network trained for shape classification, demonstrating state-of-the-art performance for nonrigid shapes.
  • No Thumbnail Available
    Item
    Modeling and Exploring Co-variations in the Geometry and Configuration of Man-made 3D Shape Families
    (The Eurographics Association and John Wiley & Sons Ltd., 2017) Laga, Hamid; Tabia, Hedi; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
    We introduce co-variation analysis as a tool for modeling the way part geometries and configurations co-vary across a family of man-made 3D shapes. While man-made 3D objects exhibit large geometric and structural variations, the geometry, structure, and configuration of their individual components usually do not vary independently from each other but in a correlated fashion. The size of the body of an airplane, for example, constrains the range of deformations its wings can undergo to ensure that the entire object remains a functionally-valid airplane. These co-variation constraints, which are often non-linear, can be either physical, and thus they can be explicitly enumerated, or implicit to the design and style of the shape family. In this article, we propose a data-driven approach, which takes pre-segmented 3D shapes with known component-wise correspondences and learns how various geometric and structural properties of their components co-vary across the set. We demonstrate, using a variety of 3D shape families, the utility of the proposed co-variation analysis in various applications including 3D shape repositories exploration and shape editing where the propagation of deformations is guided by the co-variation analysis. We also show that the framework can be used for context-guided orientation of objects in 3D scenes.
  • No Thumbnail Available
    Item
    A Parallel Approach to Compression and Decompression of Triangle Meshes using the GPU
    (The Eurographics Association and John Wiley & Sons Ltd., 2017) Jakob, Johannes; Buchenau, Christoph; Guthe, Michael; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
    Most state-of-the-art compression algorithms use complex connectivity traversal and prediction schemes, which are not efficient enough for online compression of large meshes. In this paper we propose a scalable massively parallel approach for compression and decompression of large triangle meshes using the GPU. Our method traverses the input mesh in a parallel breadth-first manner and encodes the connectivity data similarly to the well known cut-border machine. Geometry data is compressed using a local prediction strategy. In contrast to the original cut-border machine, we can additionally handle triangle meshes with inconsistently oriented faces. Our approach is more than one order of magnitude faster than currently used methods and achieves competitive compression rates.
  • No Thumbnail Available
    Item
    Ternary Sparse Matrix Representation for Volumetric Mesh Subdivision and Processing on GPUs
    (The Eurographics Association and John Wiley & Sons Ltd., 2017) Mueller-Roemer, Johannes Sebastian; Altenhofen, Christian; Stork, André; Bærentzen, Jakob Andreas and Hildebrandt, Klaus
    In this paper, we present a novel volumetric mesh representation suited for parallel computing on modern GPU architectures. The data structure is based on a compact, ternary sparse matrix storage of boundary operators. Boundary operators correspond to the first-order top-down relations of k-faces to their (k-1)-face facets. The compact, ternary matrix storage format is based on compressed sparse row matrices with signed indices and allows for efficient parallel computation of indirect and bottomup relations. This representation is then used in the implementation of several parallel volumetric mesh algorithms including Laplacian smoothing and volumetric Catmull-Clark subdivision. We compare these algorithms with their counterparts based on OpenVolumeMesh and achieve speedups from 3x to 531x, for sufficiently large meshes, while reducing memory consumption by up to 36%.