Skip to main navigation Skip to search Skip to main content

SCARST: Schnyder Compact and Regularity Sensitive Triangulation Data Structure

  • Nancy Université

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Citations (Scopus)

Abstract

We consider the design of fast and compact representations of the connectivity information of triangle meshes. Although traditional data structures (Half-Edge, Corner Table) are fast and user-friendly, they tend to be memory-expensive. On the other hand, compression schemes, while meeting information-theoretic lower bounds, do not support navigation within the mesh structure. Compact representations provide an advantageous balance for representing large meshes, enabling a judicious compromise between memory consumption and fast implementation of navigational operations. We propose new representations that are sensitive to the regularity of the graph while still having worst case guarantees. For all our data structures we have both an interesting storage cost, typically 2 or 3 r.p.v. (references per vertex) in the case of very regular triangulations, and provable upper bounds in the worst case scenario. One of our solutions has a worst case cost of 3.33 r.p.v., which is currently the best-known bound improving the previous 4 r.p.v. [Castelli et al. 2018]. Our representations have slightly slower running times (factors 1.5 to 4) than classical data structures. In our experiments we compare on various meshes runtime and memory performance of our representations with those of the most efficient existing solutions.

Original languageEnglish
Title of host publication40th International Symposium on Computational Geometry, SoCG 2024
EditorsWolfgang Mulzer, Jeff M. Phillips
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959773164
DOIs
Publication statusPublished - 1 Jun 2024
Event40th International Symposium on Computational Geometry, SoCG 2024 - Athens, Greece
Duration: 11 Jun 2024 → 14 Jun 2024

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume293
ISSN (Print)1868-8969

Conference

Conference40th International Symposium on Computational Geometry, SoCG 2024
Country/TerritoryGreece
CityAthens
Period11/06/24 → 14/06/24

Keywords

  • Meshes
  • compact representations
  • compression
  • triangulations

Fingerprint

Dive into the research topics of 'SCARST: Schnyder Compact and Regularity Sensitive Triangulation Data Structure'. Together they form a unique fingerprint.

Cite this