Close
Metadata

@InProceedings{AleardiDeviRoss:2012:EdSQRe,
               author = "Aleardi, Luca Castelli and Devillers, Olivier and Rossignac, 
                         Jarek",
          affiliation = "{Ecole Polytechnique} and {INRIA Sophia-Antipolis} and {Georgia 
                         Institute of Technology}",
                title = "ESQ: Editable SQuad representation for triangle meshes",
            booktitle = "Proceedings...",
                 year = "2012",
               editor = "Freitas, Carla Maria Dal Sasso and Sarkar, Sudeep and Scopigno, 
                         Roberto and Silva, Luciano",
         organization = "Conference on Graphics, Patterns and Images, 25. (SIBGRAPI)",
            publisher = "IEEE Computer Society",
              address = "Los Alamitos",
             keywords = "triangle meshes, compact representations, mesh data structures.",
             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 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.",
  conference-location = "Ouro Preto",
      conference-year = "Aug. 22-25, 2012",
             language = "en",
           targetfile = "PID2444419.pdf",
        urlaccessdate = "2021, Jan. 24"
}


Close