Samavati, FaramarzMahdavi-Amiri, Ali2015-05-052015-11-202015-05-052015Mahdavi-Amiri, A. (2015). ACM: Atlas of Connectivity Maps (Doctoral thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/24660http://hdl.handle.net/11023/2247Semiregular models are an important subset of the graphical models used in computer graphics. They are typically obtained by applying repetitive regular refinements on an initial arbitrary model and, as a result, their connectivity exhibits a high degree of regularity. Although data structures exist for regular or irregular models, a data structure designed to take advantage of this semiregularity is desirable. We introduce such a data structure called the atlas of connectivity maps (ACM), which efficiently represents semiregular models resulting from various types of refinements. This atlas maps the connectivity information of vertices and faces onto separate 2D domains called connectivity maps, and handles connectivity queries within each connectivity map using simple algebraic operations or between connectivity maps using a set of linear transformations. We demonstrate the effectiveness of ACM for use in subdivision, multiresolution, and Digital Earth applications. In addition, the generality of ACM has been examined on a variety of face-types (e.g. triangles, hexagons, quads) as well as uniform and adaptive refinements. We compare the performance of ACM to various data structures including the standard half-edge, and show that the performance of ACM is better than these available data structures in supporting important queries such as neighborhood finding and hierarchical traversal.engUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.Computer ScienceSemiregularConnectivity MapsData StructureSubdivisionMultiresolutionDigital EarthDiscrete Global Grid Systemsdoctoral thesis10.11575/PRISM/24660