ACM: Atlas of Connectivity Maps

Semiregular 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.

Name thesis:degree_name

Doctor of Philosophy (PhD)

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher.institution

Graduate Studies

Year dc:date.issued

2015

Author dc:creator

• Mahdavi-Amiri, Ali

Advisor dc:contributor.advisor

• Samavati, Faramarz

• Computer Science

Statement dc:rights

• University 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.

Language dc:language.iso

eng

DOI

http://dx.doi.org/10.11575/PRISM/24660

OAI identifier oai:identifier

oai:ucalgary.scholaris.ca:11023/2247