ARRAY-BASED COMPACT DATA STRUCTURES FOR TRIANGULATIONS

ARRAY-BASED COMPACT DATA STRUCTURES FOR TRIANGULATIONS:
PRACTICAL SOLUTIONS WITH THEORETICAL GUARANTEES

(Luca Castelli Aleardi and Olivier Devillers)

We consider the problem of designing space efficient solutions for representing triangle meshes. Our main result is a new explicit data structure for compactly representing planar triangulations: if one is allowed to permute input vertices, then a triangulation with n vertices requires at most 4n references (5n references if vertex permutations are not allowed). Our solution combines existing techniques from mesh encoding with a novel use of maximal Schnyder woods. Our approach extends to higher genus triangulations and could be applied to other families of meshes (such as quadrangular or polygonal meshes). As far as we know, our solution provides the most parsimonious data structures for triangulations, allowing constant time navigation. Our data structures require linear construction time, and are fast decodable from a standard compressed format without using additional memory allocation. All bounds, concerning storage requirements and navigation performances, hold in the worst case. We have implemented and tested our results, and experiments confirm the practical interest of compact data structures.

(preliminary version in Int. Symposium on Algorithms and Computation, ISAAC 2011, Springer LNCS)

Data sets (3d meshes and random planar triangulations)

3D meshes in binary OFF and compressed format (original OFF files are made available by AIM@SHAPE project)
Random planar triangulations in binary OFF and compressed format (generated according to uniform distribution, with the random sampler by Poulalhon and Schaeffer)

Decoding and constructing compact data structures

Documentation, source code and libraries to download (100% java code, Java 1.8 required):

compactTriangulations.zip: source code of compact data structures for triangulations (by L. Castelli Aleardi)
Jcg_src.zip: minimal Jcg library (minimal version of the java library for computational geometry, by L. Castelli Aleardi and S. Oudot)
ArraybasedDS.zip: array-based implementation of standard mesh data structures (by L. Castelli Aleardi)
TC.jar (for dealing with input/output)
core.jar (Processing library for 3d rendering: version 1.5)
javadoc (documentation)

Runnable Jar files to download for tests and benchmarks (including all required java libraries)

ConvertOFFToBinary: .jar file for converting an OFF file in binary format (only for genus 0 triangle meshes)
TestEncoding: .jar file for encoding a triangulation in a compressed format (based on Schnyder wood edge orientations)
TestDecoding: .jar file for decoding a triangulation from compressed format (based on Schnyder wood edge orientations). This program performs the decoding and construction in main memory of the CDS6n compact data structure
TestVertexDegree: .jar file measuring runtime performances of all data structures: this program read a triangle mesh from binary OFF format and run benchmarks for the computation of vertex degrees. The supported data structures can be selected with the following options:
```
-HE -WE -CDS6nslow -CDS6n -CDS5n -CDS4n
```

Usage examples (from a Terminal):

java -Xms6G - Xmx6G -jar TestEncoding.jar egea.binoff

java -Xms6G - Xmx6G -jar ConvertOFFToBinary.jar egea.off

java -Xms1G - Xmx1G -jar TestVertexDegree.jar eros_950k.binoff -CDS6n

java -Xss100m -Xms800M - Xmx800M -jar TestDecoding.jar hand_400k.binzip

Output example (for the encoding in compressed format):

java -Xms6G - Xmx6G -jar TestEncoding.jar egea.binoff

Compressing triangulations: the triangulation is compressed and saved in text and binary formats
Building a pointer-based half-edge data structure (for genus 0 triangle meshes) from a binary OFF file: datasets/egea.binoff
Reading binary file...done
[loadede binary compressed file in main memory]    memory : 0.29 MB (307144 bytes)
	Reading header n=8268
	Reading coordinates...done
	Reading faces...done
Mesh loaded from binary OFF format (0.058643462 seconds)
[total used memory]    memory : 2.34 MB (2461288 bytes)
Running garbage collector...done
Initialize Schnyder wood computation: 
	 root face (v2, v0, v1)
	 root edge (v2, v0)
Computing Schnyder wood (for planar triangulations)...done (0.006925735 seconds)
Checking edge orientations and vertex labels...ok
Encoding a planar triangulation...done (0.00828051 s)
Writing compressed format to binary file (triangulation.binzip)done (0.004075102 s)
Checking mesh encoding string: red word  (ok) - black word (ok) [max depth in red word = 2133]
--- encoding done ---

Output example (for the decoding from compressed format):

java -Xss100m -Xms800M - Xmx800M -jar TestDecoding.jar hand_400k.binzip

--- Testing decoding procedure (from compressed binary format) ---
--- evaluate the performances of decoding the CDS6n compact representation ---
--- tests are repeated 5 times ---


	------ run  1 ------	
Reading a compressed triangle mesh from binary file: datasets/hand_400k.binzip
Reading binary file...done
[loadede binary compressed file in main memory]    memory : 2.33 MB (2452960 bytes)
	Reading the header n=195557
	Reading vertex coordinates from file...done (0.037758425 seconds)
	Reading connectivity from file...done (0.002290897 seconds)
	Total duration (reading binary file): 0.040049322 seconds)
Start decoding (no use of additional memory)
First phase (constructing red and black trees)...ok
Decoding and construction done (0.085314164 s)
[total used memory]    memory : 7.14 MB (7487192 bytes)
[total free memory]    memory : 759.85 MB (796770920 bytes)
Checking vertex degrees...ok

	------ run  2 ------	
Reading a compressed triangle mesh from binary file: datasets/hand_400k.binzip
Reading binary file...done
[loadede binary compressed file in main memory]    memory : 2.33 MB (2444488 bytes)
	Reading the header n=195557
	Reading vertex coordinates from file...done (0.014532459 seconds)
	Reading connectivity from file...done (5.49619E-4 seconds)
	Total duration (reading binary file): 0.015082077999999999 seconds)
Start decoding (no use of additional memory)
First phase (constructing red and black trees)...ok
Decoding and construction done (0.019469164 s)
[total used memory]    memory : 7.14 MB (7486848 bytes)
[total free memory]    memory : 759.85 MB (796770944 bytes)
Checking vertex degrees...ok

	------ run  3 ------	
Reading a compressed triangle mesh from binary file: datasets/hand_400k.binzip
Reading binary file...done
[loadede binary compressed file in main memory]    memory : 2.33 MB (2444488 bytes)
	Reading the header n=195557
	Reading vertex coordinates from file...done (0.024701489 seconds)
	Reading connectivity from file...done (3.10895E-4 seconds)
	Total duration (reading binary file): 0.025012384 seconds)
Start decoding (no use of additional memory)
First phase (constructing red and black trees)...ok
Decoding and construction done (0.02919298 s)
[total used memory]    memory : 7.14 MB (7486848 bytes)
[total free memory]    memory : 759.85 MB (796770944 bytes)
Checking vertex degrees...ok

	------ run  4 ------	
Reading a compressed triangle mesh from binary file: datasets/hand_400k.binzip
Reading binary file...done
[loadede binary compressed file in main memory]    memory : 2.33 MB (2444488 bytes)
	Reading the header n=195557
	Reading vertex coordinates from file...done (0.012357951 seconds)
	Reading connectivity from file...done (6.6969E-5 seconds)
	Total duration (reading binary file): 0.01242492 seconds)
Start decoding (no use of additional memory)
First phase (constructing red and black trees)...ok
Decoding and construction done (0.013521 s)
[total used memory]    memory : 7.14 MB (7486920 bytes)
[total free memory]    memory : 759.85 MB (796770872 bytes)
Checking vertex degrees...ok

	------ run  5 ------	
Reading a compressed triangle mesh from binary file: datasets/hand_400k.binzip
Reading binary file...done
[loadede binary compressed file in main memory]    memory : 2.33 MB (2444488 bytes)
	Reading the header n=195557
	Reading vertex coordinates from file...done (0.01542705 seconds)
	Reading connectivity from file...done (7.0978E-5 seconds)
	Total duration (reading binary file): 0.015498027999999999 seconds)
Start decoding (no use of additional memory)
First phase (constructing red and black trees)...ok
Decoding and construction done (0.014008267 s)
[total used memory]    memory : 7.14 MB (7486920 bytes)
[total free memory]    memory : 759.85 MB (796770872 bytes)
Checking vertex degrees...ok

Output example (for the benchmarking the vertex degree computation):

java -Xms1G - Xmx1G -jar TestVertexDegree.jar eros_950k.binoff -CDS6n


---Testing performances of triangle mesh representations (vertex degree computation)---

Building a pointer-based half-edge data structure (for genus 0 triangle meshes) from a binary OFF file: datasets/eros_950k.binoff
Reading binary file...done
[loadede binary compressed file in main memory]    memory : 16.37 MB (17175072 bytes)
	Reading header n=476596
	Reading coordinates...done
	Reading faces...done
Mesh loaded from binary OFF format (0.435882493 seconds)
[total used memory]    memory : 116.68 MB (122358144 bytes)
Running garbage collector...done
Initialize Schnyder wood computation: 
	 root face (v436584, v436428, v436514)
	 root edge (v436584, v436428)
Computing Schnyder wood (for planar triangulations)...done (0.088867538 seconds)
Checking edge orientations and vertex labels...ok
Creating a compact triangle mesh DS (6n rpv) from a Polyhedron [CDS6n]...done (0.093659704 s)
Checking vertex degrees...ok
	Starting benchmarks
Compact triangle 6n: 	vertex degree (ns): 28.205324677504635
Compact triangle 6n: 	vertex degree (ns): 27.167892827468126
Compact triangle 6n: 	vertex degree (ns): 27.33799404527105
Compact triangle 6n: 	vertex degree (ns): 27.368393880771137
Compact triangle 6n: 	vertex degree (ns): 27.36065304786444
Compact triangle 6n: 	vertex degree (ns): 27.365165234286483
	--- benchmarks done --- (CDS6n)