Diana Marin, Stefan Ohrhallinger, Michael Wimmer
SIGDT: 2D Curve Reconstruction
Computer Graphics Forum, 41(7):25-36, October 2022. [Paper] [Paper]

Information

  • Publication Type: Journal Paper with Conference Talk
  • Workgroup(s)/Project(s):
  • Date: October 2022
  • Call for Papers: Call for Paper
  • Date (from): 5. October 2022
  • Date (to): 8. October 2022
  • DOI: 10.1111/cgf.14654
  • Event: Pacific Graphics 2022
  • ISSN: 1467-8659
  • Journal: Computer Graphics Forum
  • Lecturer: Diana Marin
  • Location: Kyoto, Japan
  • Number: 7
  • Open Access: yes
  • Pages (from): 25
  • Pages (to): 36
  • Volume: 41
  • Keywords: Curve reconstruction, Spheres-of-influence graph

Abstract

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.

Additional Files and Images

Additional images and videos

Additional files

Weblinks

BibTeX

@article{marin-2022-sigdt,
  title =      " SIGDT: 2D Curve Reconstruction",
  author =     "Diana Marin and Stefan Ohrhallinger and Michael Wimmer",
  year =       "2022",
  abstract =   "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.",
  month =      oct,
  doi =        "10.1111/cgf.14654",
  issn =       "1467-8659",
  journal =    "Computer Graphics Forum",
  number =     "7",
  volume =     "41",
  pages =      "25--36",
  keywords =   "Curve reconstruction, Spheres-of-influence graph",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2022/marin-2022-sigdt/",
}