Theoretical and Empirical Analysis of a Fast Algorithm for Extracting Polygons from Signed Distance Bounds

• URL: http://arxiv.org/abs/2111.05778v2
• Date: Fri, 5 Apr 2024 09:19:41 GMT
• Title: Theoretical and Empirical Analysis of a Fast Algorithm for Extracting Polygons from Signed Distance Bounds
• Authors: Nenad Markuš, Mirko Sužnjević,
• Abstract summary: We introduce and investigate anally fast method for transforming signed distance bounds into polygon meshes. We provide theoretical and experimental evidence that this approach is of the $O(N2log N)$ computational complexity for a polygonization grid with $N3$ cells. Given its speed, implementation simplicity and portability, we argue that it could prove useful during the modelling stage as well as in shape compression for storage.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Recently there has been renewed interest in signed distance bound representations due to their unique properties for 3D shape modelling. This is especially the case for deep learning-based bounds. However, it is beneficial to work with polygons in most computer-graphics applications. Thus, in this paper we introduce and investigate an asymptotically fast method for transforming signed distance bounds into polygon meshes. This is achieved by combining the principles of sphere tracing (or ray marching) with traditional polygonization techniques, such as Marching Cubes. We provide theoretical and experimental evidence that this approach is of the $O(N^2\log N)$ computational complexity for a polygonization grid with $N^3$ cells. The algorithm is tested on both a set of primitive shapes as well as signed distance bounds generated from point clouds by machine learning (and represented as neural networks). Given its speed, implementation simplicity and portability, we argue that it could prove useful during the modelling stage as well as in shape compression for storage. The code is available here: https://github.com/nenadmarkus/gridhopping

Related papers

• DPPD: Deformable Polar Polygon Object Detection [3.9236649268347765]
  We develop a novel Deformable Polar Polygon Object Detection method (DPPD) to detect objects in polygon shapes. DPPD has been demonstrated successfully in various object detection tasks for autonomous driving.
  arXiv  Detail & Related papers  (2023-04-05T06:43:41Z)
• GeoUDF: Surface Reconstruction from 3D Point Clouds via Geometry-guided Distance Representation [73.77505964222632]
  We present a learning-based method, namely GeoUDF, to tackle the problem of reconstructing a discrete surface from a sparse point cloud. To be specific, we propose a geometry-guided learning method for UDF and its gradient estimation. To extract triangle meshes from the predicted UDF, we propose a customized edge-based marching cube module.
  arXiv  Detail & Related papers  (2022-11-30T06:02:01Z)
• Towards General-Purpose Representation Learning of Polygonal Geometries [62.34832826705641]
  We develop a general-purpose polygon encoding model, which can encode a polygonal geometry into an embedding space. We conduct experiments on two tasks: 1) shape classification based on MNIST; 2) spatial relation prediction based on two new datasets - DBSR-46K and DBSR-cplx46K. Our results show that NUFTspec and ResNet1D outperform multiple existing baselines with significant margins.
  arXiv  Detail & Related papers  (2022-09-29T15:59:23Z)
• A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matching [69.14632473279651]
  We present a scalable algorithm for globally optimizing over the space of geometrically consistent mappings between 3D shapes. We propose a novel primal coupled with a Lagrange dual problem that is several orders of magnitudes faster than previous solvers.
  arXiv  Detail & Related papers  (2022-04-27T09:47:47Z)
• PolyWorld: Polygonal Building Extraction with Graph Neural Networks in Satellite Images [10.661430927191205]
  This paper introduces PolyWorld, a neural network that directly extracts building vertices from an image and connects them correctly to create precise polygons. PolyWorld significantly outperforms the state-of-the-art in building polygonization.
  arXiv  Detail & Related papers  (2021-11-30T15:23:17Z)
• PolyNet: Polynomial Neural Network for 3D Shape Recognition with PolyShape Representation [51.147664305955495]
  3D shape representation and its processing have substantial effects on 3D shape recognition. We propose a deep neural network-based method (PolyNet) and a specific polygon representation (PolyShape) Our experiments demonstrate the strength and the advantages of PolyNet on both 3D shape classification and retrieval tasks.
  arXiv  Detail & Related papers  (2021-10-15T06:45:59Z)
• Molecule3D: A Benchmark for Predicting 3D Geometries from Molecular Graphs [79.06686274377009]
  We develop a benchmark, known as Molecule3D, that includes a dataset with precise ground-state geometries of approximately 4 million molecules. We implement two baseline methods that either predict the pairwise distance between atoms or atom coordinates in 3D space. Our method can achieve comparable prediction accuracy but with much smaller computational costs.
  arXiv  Detail & Related papers  (2021-09-30T22:09:28Z)
• CenterPoly: real-time instance segmentation using bounding polygons [11.365829102707014]
  We present a novel method, called CenterPoly, for real-time instance segmentation using bounding polygons. We apply it to detect road users in dense urban environments, making it suitable for applications in intelligent transportation systems like automated vehicles. Most of the network parameters are shared by the network heads, making it fast and lightweight enough to run at real-time speed.
  arXiv  Detail & Related papers  (2021-08-19T21:31:30Z)
• PUGeo-Net: A Geometry-centric Network for 3D Point Cloud Upsampling [103.09504572409449]
  We propose a novel deep neural network based method, called PUGeo-Net, to generate uniform dense point clouds. Thanks to its geometry-centric nature, PUGeo-Net works well for both CAD models with sharp features and scanned models with rich geometric details.
  arXiv  Detail & Related papers  (2020-02-24T14:13:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.