Scarst data structure: see related publication in the proceedings of SoCG 2024

This readme file illustrates how to run the executable jar files for computing benchmarks on compact data structures

Available files:
-) RuntimeBenchmark.jar: for evaluating runtime performances
-) StorageBenchmark.jar: for evaluating storage performances

Requirements and remarks:
Input meshes must be provided in OFF format: only triangle meshes of genus 0 without boundaries (closed manifold) are accepted

Geometric coordinates: there is no distinction between 2D and 3D graphs.
For every vertex 3 geometric coordinates (x, y, z) are stored (single floating coordinates: 32 bits each)

--------------------------------------------------
1) To perform Runtime benchmarks of compact data structure for triangle meshes execute the program RuntimeBenchmark.jar, as illustrated below.

Two arguments are required to run the tests:
	argument 1: an input file storing a triangle mesh (OFF format)
	argument 2: name of the data structure to test

Supported options are listed below
	-HE		 [Half-edge data structure, 19 rpv]
	-CHE		 [Compact Half-edge data structure, 13 rpv]
	-CT		 [Corner Table data structure, 13 rpv]
	-SOT		 [SOT data structure, 6 rpv]
	-SQUAD		 [SQUAD data structure, between 4 and 6 rpv]
	-CDS5n		 [Compact data structure, Castelli & Devillers (JoCG2018), 5 rpv]
	-SCARST-OS	 [O(d) time navigation, 3 rpv]
	-SCARST-RS	 [O(d) time navigation, 2 rpv]
	-SCARST-OT	 [O(1) time navigation, between 3 and 5 rpv]

Optional argument (name of the operator to test): if none, all operators will be tested
Supported navigational operators are listed below
	-degree		 compute vertex degrees
	-listing	 return the list of neighbors
	-normal		 compute vertex normals
	-adjacent	 test vertex adjacency between pairs of vertices
	-bfs		 perform a BFS graph traversal

Optional argument (number of tests: 50 runs per test are performed): -repeat=4
Optional argument (starting seed: a non negative number): -seed=10

Usage examples:
 	 java -server -Xmx4G -jar RuntimeBenchmark.jar sphere.off -HE -repeat=4
 	 java -server -Xmx4G -jar RuntimeBenchmark.jar sphere.off -CHE -listing -normal -adjacent
 	 java -server -Xmx4G -jar RuntimeBenchmark.jar sphere.off -SCARST-OT -degree -bfs -seed=10

Remark: the executable RuntimeBenchmark.jar file above has been compiled with Java 1.8

--------------------------------------------------
2) To perform storage benchmarks of compact data structures for triangle meshes execute the program StorageBenchmark.jar, as illustrated below.

Two arguments are required to run the tests:
	argument 1: an input file storing a triangle mesh (OFF format)
	argument 2: name of the data structure to test

Supported options are listed below (data structure with a fixed storage cost per vertex are omitted)
	-SQUAD		 [SQUAD data structure, between 4 and 6 rpv]
	-LR		 [LR data structure]
	-SCARST-OT	 [O(1) time navigation, between 3 and 5 rpv]
	-SCARST-RT	 [O(1) time navigation, between 2 and 3.67 rpv]
	
Usage examples:
 	 java -server -Xmx4G -jar StorageBenchmark.jar sphere.off -LR
 	 java -server -Xmx4G -jar StorageBenchmark.jar sphere.off -SCARST-OT

Remark: the executable RuntimeBenchmark.jar file above has been compiled with Java 1.8