Browsing by Author "Ohrhallinger, Stefan"

Now showing 1 - 8 of 8
  • Thumbnail Image
    Item
    2D Points Curve Reconstruction Survey and Benchmark
    (The Eurographics Association, 2022) Ohrhallinger, Stefan; Peethambaran, Jiju; Parakkat, Amal Dev; Dey, Tamal K.; Muthuganapathy, R.; Hahmann, Stefanie; Patow, Gustavo A.
    Curve reconstruction from unstructured points in a plane is a fundamental problem with many applications that has generated research interest for decades. Involved aspects like handling open, sharp, multiple and non-manifold outlines, run-time and provability as well as potential extension to 3D for surface reconstruction have led to many different algorithms. We survey the literature on 2D curve reconstruction and then present an open-sourced benchmark for the experimental study. Our unprecedented evaluation of a selected set of planar curve reconstruction algorithms aims to give an overview of both quantitative analysis and qualitative aspects for helping users to select the right algorithm for specific problems in the field. Our benchmark framework is available online to permit reproducing the results and easy integration of new algorithms.
  • Thumbnail Image
    Item
    2D Points Curve Reconstruction Survey and Benchmark
    (The Eurographics Association and John Wiley & Sons Ltd., 2021) Ohrhallinger, Stefan; Peethambaran, Jiju; Parakkat, Amal Dev; Dey, Tamal Krishna; Muthuganapathy, Ramanathan; Bühler, Katja and Rushmeier, Holly
    Curve reconstruction from unstructured points in a plane is a fundamental problem with many applications that has generated research interest for decades. Involved aspects like handling open, sharp, multiple and non-manifold outlines, run-time and provability as well as potential extension to 3D for surface reconstruction have led to many different algorithms. We survey the literature on 2D curve reconstruction and then present an open-sourced benchmark for the experimental study. Our unprecedented evaluation of a selected set of planar curve reconstruction algorithms aims to give an overview of both quantitative analysis and qualitative aspects for helping users to select the right algorithm for specific problems in the field. Our benchmark framework is available online to permit reproducing the results and easy integration of new algorithms.
  • Thumbnail Image
    Item
    Fast Out-of-Core Octree Generation for Massive Point Clouds
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Schütz, Markus; Ohrhallinger, Stefan; Wimmer, Michael; Eisemann, Elmar and Jacobson, Alec and Zhang, Fang-Lue
    We propose an efficient out-of-core octree generation method for arbitrarily large point clouds. It utilizes a hierarchical counting sort to quickly split the point cloud into small chunks, which are then processed in parallel. Levels of detail are generated by subsampling the full data set bottom up using one of multiple exchangeable sampling strategies.We introduce a fast hierarchical approximate blue-noise strategy and compare it to a uniform random sampling strategy. The throughput, including out-of-core access to disk, generating the octree, and writing the final result to disk, is about an order of magnitude faster than the state of the art, and reaches up to around 6 million points per second for the blue-noise approach and up to around 9 million points per second for the uniform random approach on modern SSDs.
  • Thumbnail Image
    Item
    Feature-Sized Sampling for Vector Line Art
    (The Eurographics Association, 2023) Ohrhallinger, Stefan; Parakkat, Amal Dev; Memari, Pooran; Chaine, Raphaëlle; Deng, Zhigang; Kim, Min H.
    By introducing a first-of-its-kind quantifiable sampling algorithm based on feature size, we present a fresh perspective on the practical aspects of planar curve sampling. Following the footsteps of e-sampling, which was originally proposed in the context of curve reconstruction to offer provable topological guarantees [ABE98] under quantifiable bounds, we propose an arbitrarily precise e-sampling algorithm for sampling smooth planar curves (with a prior bound on the minimum feature size of the curve). This paper not only introduces the first such algorithm which provides user-control and quantifiable precision but also highlights the importance of such a sampling process under two key contexts: 1) To conduct a first study comparing theoretical sampling conditions with practical sampling requirements for reconstruction guarantees that can further be used for analysing the upper bounds of e for various reconstruction algorithms with or without proofs, 2) As a feature-aware sampling of vector line art that can be used for applications such as coloring and meshing.
  • No Thumbnail Available
    Item
    Parameter-Free and Improved Connectivity for Point Clouds
    (The Eurographics Association, 2023) Marin, Diana; Ohrhallinger, Stefan; Wimmer, Michael; Singh, Gurprit; Chu, Mengyu (Rachel)
    Determining connectivity in unstructured point clouds is a long-standing problem that is still not addressed satisfactorily. In this poster, we propose an extension to the proximity graph introduced in [MOW22] to three-dimensional models. We use the spheres-of-influence (SIG) proximity graph restricted to the 3D Delaunay graph to compute connectivity between points. Our approach shows a better encoding of the connectivity in relation to the ground truth than the k-nearest neighborhood (kNN) for a wide range of k values, and additionally, it is parameter-free. Our result for this fundamental task offers potential for many applications relying on kNN, e.g., improvements in normal estimation, surface reconstruction, motion planning, simulations, and many more.
  • Thumbnail Image
    Item
    SIG-based Curve Reconstruction
    (The Eurographics Association, 2022) Marin, Diana; Ohrhallinger, Stefan; Wimmer, Michael; Sauvage, Basile; Hasic-Telalovic, Jasminka
    We introduce a new method to compute the shape of an unstructured set of two-dimensional points. The algorithm exploits the to-date rarely used proximity-based graph called spheres-of-influence graph (SIG). We filter edges from the Delaunay triangulation belonging to the SIG as an initial graph and apply some additional processing plus elements from the Connect2D algorithm. This combination already shows improvements in curve reconstruction, yielding the best reconstruction accuracy compared to state-of-the-art algorithms from a recent comprehensive benchmark, and offers potential of further improvements.
  • Thumbnail Image
    Item
    SIGDT: 2D Curve Reconstruction
    (The Eurographics Association and John Wiley & Sons Ltd., 2022) Marin, Diana; Ohrhallinger, Stefan; Wimmer, Michael; Umetani, Nobuyuki; Wojtan, Chris; Vouga, Etienne
    Determining connectivity between points and reconstructing their shape boundaries are long-standing problems in computer graphics. One possible approach to solve these problems is to use a proximity graph. We propose a new proximity graph computed by intersecting the to-date rarely used proximity-based graph called spheres-of-influence graph (SIG) with the Delaunay triangulation (DT). We prove that the resulting graph, which we name SIGDT, contains the piece-wise linear reconstruction for a set of unstructured points in the plane for a sampling condition superseding current bounds and capturing well practical point sets' properties. As an application, we apply a dual of boundary adjustment steps from the CONNECT2D algorithm to remove the redundant edges. We show that the resulting algorithm SIG-CONNECT2D yields the best reconstruction accuracy compared to state-of-the-art algorithms from a recent comprehensive benchmark, and the method offers the potential for further improvements, e.g., for surface reconstruction.
  • Thumbnail Image
    Item
    StretchDenoise: Parametric Curve Reconstruction with Guarantees by Separating Connectivity from Residual Uncertainty of Samples
    (The Eurographics Association, 2018) Ohrhallinger, Stefan; Wimmer, Michael; Fu, Hongbo and Ghosh, Abhijeet and Kopf, Johannes
    We reconstruct a closed denoised curve from an unstructured and highly noisy 2D point cloud. Our proposed method uses a two-pass approach: Previously recovered manifold connectivity is used for ordering noisy samples along this manifold and express these as residuals in order to enable parametric denoising. This separates recovering low-frequency features from denoising high frequencies, which avoids over-smoothing. The noise probability density functions (PDFs) at samples are either taken from sensor noise models or from estimates of the connectivity recovered in the first pass. The output curve balances the signed distances (inside/outside) to the samples. Additionally, the angles between edges of the polygon representing the connectivity become minimized in the least-square sense. The movement of the polygon's vertices is restricted to their noise extent, i.e., a cut-off distance corresponding to a maximum variance of the PDFs. We approximate the resulting optimization model, which consists of higher-order functions, by a linear model with good correspondence. Our algorithm is parameter-free and operates fast on the local neighborhoods determined by the connectivity. This enables us to guarantee stochastic error bounds for sampled curves corrupted by noise, e.g., silhouettes from sensed data, and we improve on the reconstruction error from ground truth. Source code is available online. An extended version is available at: https://arxiv.org/abs/1808.07778