Identity statement area
Reference TypeConference Paper (Conference Proceedings)
Last Update2012:
Metadata Last Update2020: administrator
Citation KeyAleardiDeviRoss:2012:EdSQRe
TitleESQ: Editable SQuad representation for triangle meshes
FormatDVD, On-line.
Access Date2021, Jan. 28
Number of Files1
Size623 KiB
Context area
Author1 Aleardi, Luca Castelli
2 Devillers, Olivier
3 Rossignac, Jarek
Affiliation1 Ecole Polytechnique
2 INRIA Sophia-Antipolis
3 Georgia Institute of Technology
EditorFreitas, Carla Maria Dal Sasso
Sarkar, Sudeep
Scopigno, Roberto
Silva, Luciano
Conference NameConference on Graphics, Patterns and Images, 25 (SIBGRAPI)
Conference LocationOuro Preto
DateAug. 22-25, 2012
Book TitleProceedings
PublisherIEEE Computer Society
Publisher CityLos Alamitos
Tertiary TypeFull Paper
History2012-09-20 16:45:34 :: -> administrator :: 2012
2020-02-19 02:18:28 :: administrator -> :: 2012
Content and structure area
Is the master or a copy?is the master
Content Stagecompleted
Content TypeExternal Contribution
Keywordstriangle meshes, compact representations, mesh data structures.
AbstractWe 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 reordering 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.
source Directory Contentthere are no files
agreement Directory Content
agreement.html 12/07/2012 03:45 0.7 KiB 
Conditions of access and use area
data URL
zipped data URL
Target FilePID2444419.pdf
Allied materials area
Notes area
Empty Fieldsaccessionnumber archivingpolicy archivist area callnumber copyholder copyright creatorhistory descriptionlevel dissemination documentstage doi edition electronicmailaddress group holdercode isbn issn label lineage mark nextedition nexthigherunit notes numberofvolumes orcid organization pages parameterlist parentrepositories previousedition previouslowerunit progress project readergroup readpermission resumeid rightsholder secondarydate secondarykey secondarymark secondarytype serieseditor session shorttitle sponsor subject tertiarymark type url versiontype volume