ESQ: Editable SQuad Representation for Triangle Meshes

Abstract : We consider the problem of designing space efficient solutions for representing the connectivity information of manifold triangle meshes. Most mesh data structures are quite redundant, storing a large amount of information in order to efficiently support mesh traversal operators. Several compact data structures have been proposed to reduce storage cost while supporting constant-time mesh traversal. Some recent solutions are based on a global re-ordering approach, which allows to implicitly encode a map between vertices and faces. Unfortunately, these compact representations do not support efficient updates, because local connectivity changes (such as edge-contractions, edge-flips or vertex insertions) require re-ordering the entire mesh. Our main contribution is to propose a new way of designing compact data structures which can be dynamically maintained. In our solution, we push further the limits of the re-ordering approaches: the main novelty is to allow to re-order vertex data (such as vertex coordinates), and to exploit this vertex permutation to easily maintain the connectivity under local changes. We describe a new class of data structures, called Editable SQuad (ESQ), offering the same navigational and storage performance as previous works, while supporting local editing in amortized constant time. As far as we know, our solution provides the most compact dynamic data structure for triangle meshes. We propose a linear-time and linear-space construction algorithm, and provide worst-case bounds for storage and time cost.
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download


https://hal.inria.fr/hal-00793592
Contributor : Luca Castelli Aleardi <>
Submitted on : Friday, February 22, 2013 - 4:38:05 PM
Last modification on : Wednesday, July 31, 2019 - 3:24:15 PM
Long-term archiving on: Sunday, April 2, 2017 - 4:28:59 AM

Files

ESQ_Sibgrapi2012.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Luca Castelli Aleardi, Olivier Devillers, Jarek Rossignac. ESQ: Editable SQuad Representation for Triangle Meshes. 25th SIBGRAPI Conference on Graphics, Patterns and Images, SIBGRAPI 2012, Aug 2012, Ouro Preto, Brazil. pp.110-117, ⟨10.1109/SIBGRAPI.2012.24⟩. ⟨hal-00793592⟩

Share

Metrics

Record views

621

Files downloads

445