SCARST

SCARST: Schnyder Compact And Regularity Sensitive Triangulation Data Structure

(Luca Castelli Aleardi and Olivier Devillers, presented at the 40th. Int. Symp. on Computational Geometry 2024, [www] )

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.

License (LGPL version 3.0)

The Java implementation of the Scarst and related data structures is made available under the terms of the GNU Lesser General Public License (LGPL version 3.0)
This library is distributed for academic purposes in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Data sets (genus 0 triangulations with no boundaries, stored in OFF format)

Input datasets (for download): examples of 3D and planar triangle meshes (genus 0 closed meshes) in OFF format are provided here

SCARST: files to download (for running tests and benchmarks: Java 1.8 or higher required)

Source code and required libraries (100% pure Java code)

scarst.zip: source code of the Scarst library, including the implementaion of all data structures
javadoc.zip: javadoc of the Scarst library
Jcg.jar: minimal Jcg library for computational geometry (developped by Luca Castelli Aleardi and Steve Oudot)
TC.jar: java library for input/output operations on text files (written by Philippe Chassignet, Ecole Polytechnique)

Runnable files (the .jar files below include all required java libraries)

RuntimeBenchmark.jar (compiled with Java 1.8): a runnable .jar file for the evaluating the runtime performances of triangle mesh data structures
StorageBenchmark.jar (compiled with Java 1.8): a runnable .jar file for the evaluating the storage performances of triangle mesh data structures
readme.txt: readme file illustrating how to run the .jar files

Usage examples (running from a Terminal): at least 2 parameters are required (input file in OFF format, name of the data structure)

java -server -Xmx4G -jar RuntimeBenchmark.jar sphere.off -SCARST-OT (perform all runtime benchmarks for Scart-OT data structure, with a random seed)

java -server -Xmx4G -jar RuntimeBenchmark.jar sphere.off -CHE -listing -normal (evaluate the listing and Compact Half-edge data structure, with a random seed)

java -server -Xmx4G -jar StorageBenchmark.jar sphere.off -LR (evaluate the storage performances of the LR data structure, with 50 random seeds)

Output example (runtime performances of the SCARST-OS data structure for the Egea 3d model):

---   Testing runtime performances of SCARST data structures ---
Current JVM version - 1.8.0_412

Navigational operators to be tested:
	all navigational operators will be tested
Input file: /home/amturing/ownCloud/datasets/OFF/LargePlanarTri/egea.off
Starting seed: 0
Maximum amount of memory in the JVM (Mbytes): 7440
Total memory used (Mbytes): 502
	----------------

Building an Compact Halfedge representation of a closed surface triangle mesh (from OFF file) - memory efficient
	Reading vertices...done 8268 vertices
	Reading faces...20%...40%...60%...80%...100%
	Reading geometric coordinates...done 8268 vertices
Construction time: 0.205310365 seconds
Memory cost (Compact Half-edge data structure):
	 connectivity (13 ref/vertex)=0.4 Mbytes
	 total cost (with geometry)= 5.29E5 bytes (0.5 Mbytes)
Maximum amount of memory in the JVM (Mbytes): 7440
Total memory used (Mbytes): 634
	----------------

(Fast) Schnyder wood initialization: 	 root face (v2, v0, v1)	 root edge e6 (v2, v0)
Fast computation of a minimal Schnyder wood (for planar triangulations)...done (0.005107276 seconds)
Checking edge orientations...ok

	--- Creating data structure [SCARST-OS] from Compact Half-edge (13rpv)
Memory allocation (for combinatorics): 0.0947113037109375 MB
Data structure initialized (0.02729188 s)
Checking (combinatorial) correctness of compact data structures
- Test 1: computing vertex degree sequence...ok
	 min degree=3
	 max degree=13
	 #degree 6 vertices=2076
- Test 2: checking neighbor lists...ok

	--- Starting benchmarks ---
Timigs are expressed in nanoseconds (ns) per vertex (mean/median values over 100 runs)
Tested data structure: SCARST-OS (3 rpv)
Java memory footprint (when starting the JVM): 0.30066680908203125 MB
Total memory size (for combinatorics): Memory cost (SCARST-OS data structure):
	 connectivity (rpv)=3.0
	 connectivity (Mbytes)=0.09 Mbytes
	 total cost with geometry (bytes)= 1.98E5 bytes (0.18 Mbytes)
Total memory used (combinatorics + geometry + memory footprint): 0.7043609619140625 MB

Test 0: 50 runs
Compact triangle DS (3n): 	vertex degree - 	 (CW): 94.89577890662797	 (CCW): 94.58648766328011	 average: 94.74113328495403
SCARST-OS (3 rpv)	Running warming phase...done		computing degree CW (ns): 82.5 [mean] 	 76.48 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing degree CCW (ns): 78.11 [mean] 	 75.23 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing normal (ns): 235.48 [mean] 	 235.86 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing listing (ns): 217.71 [mean] 	 214.81 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing adjacent for real edges (ns): 89.32 [mean] 	 87.47 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing adjacent for non adjacent vertices (ns): 133.72 [mean] 	 132.44 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing BFS traversal  (seconds): 0.0019 [mean] 	 0.0019 [median]
Test 1: 50 runs
Compact triangle DS (3n): 	vertex degree - 	 (CW): 78.18766086115143	 (CCW): 75.76656507014997	 average: 76.97711296565069
SCARST-OS (3 rpv)	Running warming phase...done		computing degree CW (ns): 79.07 [mean] 	 77.8 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing degree CCW (ns): 73.83 [mean] 	 71.82 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing normal (ns): 186.03 [mean] 	 183.92 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing listing (ns): 216.45 [mean] 	 212.78 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing adjacent for real edges (ns): 85.11 [mean] 	 82.2 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing adjacent for non adjacent vertices (ns): 131.08 [mean] 	 128.45 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing BFS traversal  (seconds): 0.0019 [mean] 	 0.0019 [median]
Test 2: 50 runs
Compact triangle DS (3n): 	vertex degree - 	 (CW): 78.58147314949203	 (CCW): 75.40140783744557	 average: 76.9914404934688
SCARST-OS (3 rpv)	Running warming phase...done		computing degree CW (ns): 79.54 [mean] 	 76.66 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing degree CCW (ns): 73.5 [mean] 	 70.84 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing normal (ns): 182.94 [mean] 	 179.82 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing listing (ns): 201.24 [mean] 	 200.14 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing adjacent for real edges (ns): 85.54 [mean] 	 84.43 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing adjacent for non adjacent vertices (ns): 131.86 [mean] 	 131.56 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing BFS traversal  (seconds): 0.0019 [mean] 	 0.0019 [median]
Test 3: 50 runs
Compact triangle DS (3n): 	vertex degree - 	 (CW): 76.93069908079342	 (CCW): 73.6373923560716	 average: 75.28404571843251
SCARST-OS (3 rpv)	Running warming phase...done		computing degree CW (ns): 77.52 [mean] 	 75.72 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing degree CCW (ns): 71.44 [mean] 	 70.45 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing normal (ns): 180.34 [mean] 	 178.47 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing listing (ns): 199.55 [mean] 	 195.66 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing adjacent for real edges (ns): 84.11 [mean] 	 82.47 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing adjacent for non adjacent vertices (ns): 131.19 [mean] 	 129.14 [median]
SCARST-OS (3 rpv)	Running warming phase...done		computing BFS traversal  (seconds): 0.0019 [mean] 	 0.0018 [median]
	--- benchmarks done --- (SCARST-OS (3 rpv))