Proceedings: GI 2005

A pattern-based data structure for manipulating meshes with regular regions

Le-Jeng Shiue , Jörg Peters

Proceedings of Graphics Interface 2005: Victoria, British Columbia, Canada, 9 - 11 May 2005, 153-160

DOI 10.20380/GI2005.19

  • Bibtex

    author = {Shiue, Le-Jeng and Peters, J{\"o}rg},
    title = {A pattern-based data structure for manipulating meshes with regular regions},
    booktitle = {Proceedings of Graphics Interface 2005},
    series = {GI 2005},
    year = {2005},
    issn = {0713-5424},
    isbn = {1-56881-265-5},
    location = {Victoria, British Columbia, Canada},
    pages = {153--160},
    numpages = {8},
    doi = {10.20380/GI2005.19},
    publisher = {Canadian Human-Computer Communications Society},
    address = {School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada},


Automatically generated or laser-scanned surfaces typically exhibit large clusters with a uniform pattern. To take advantage of the regularity within clusters and still be able to edit without decompression, we developed a two-level data structure that uses an enumeration by orbits and an individually adjustable stencil to flexibly describe connectivity. The structure is concise for storing mesh connectivity; efficient for random access, interactive editing, and recursive refinement; and it is flexible by supporting a large assortment of connectity patterns and subdivision schemes.