Adaptive Atlas of Connectivity Maps

Ali Mahdavi-Amiri, Faramarz F. SamavatiCurves and Surfaces 2014 · DOI

TL;DR

This paper introduces an extension to the Atlas of Connectivity Maps (ACM) data structure to support adaptive subdivision. This new "Adaptive ACM" allows for meshes with varying levels of detail across different regions, improving efficiency and enabling more complex modeling scenarios.

What Problem Does This Paper Address?

Computer graphics often deals with semiregular meshes, which are composed of regular patches. The original Atlas of Connectivity Maps (ACM) is an efficient data structure for these meshes, particularly when they are uniformly refined. However, many real-world applications require adaptive refinement, where different parts of a mesh need different levels of detail (e.g., to represent fine details in one area while keeping another area coarser). The original ACM formulation, which assumes uniform resolution across all patches, struggles to handle this adaptivity. This leads to challenges in efficiently representing and manipulating such meshes, potentially creating cracks or requiring inefficient data structures.

Methods

The core contribution of this paper is the extension of the ACM to support adaptive subdivision. This is achieved by:

  • Allowing patches at different resolutions: The structure is modified to accommodate connectivity maps (CMs) that represent patches at varying levels of detail. This is primarily done by adding a resolution indicator to each CM.
  • Handling one-to-many attachments: Unlike the original ACM where patches have a strict one-to-one neighbor relationship, the adaptive version supports one-to-many attachments between CMs at different resolutions. This is crucial for bridging gaps created by adaptive refinement.
  • Introducing "zippers": To resolve visual discontinuities (cracks) that can arise at the boundaries of patches with different resolutions, the paper proposes using transitional quadrangulations or triangulations called "zippers." These act as smooth connectors between coarse and fine regions.
  • Linear interpolation: As an alternative to zippers, linear interpolation is proposed to smoothly connect vertices along the boundary edges of adjacent patches with different resolutions.
  • Compact ACM algorithm: The paper also presents an algorithm to create a more compact ACM by combining adjacent patches into larger quadrilateral domains. This reduces redundancy and improves efficiency. The algorithm involves three main functions: Pair (combining neighboring CMs), Union (combining CMs with matching boundary vertex counts), and CleanUp (restructuring small CMs).

Datasets

Not discussed in the paper. The paper focuses on the data structure and algorithms themselves, using example models (Teddy, Monster Frog, Big Guy, Bullet) for illustration and evaluation.

Key Insights and Ideas

  • Adaptive subdivision is crucial for realistic modeling: The ability to represent varying levels of detail is essential for modeling complex objects and scenes efficiently.
  • One-to-many attachments are a fundamental requirement for adaptive ACM: The strict one-to-one neighbor mapping of the original ACM is insufficient for adaptive scenarios.
  • "Zippers" offer a robust solution for bridging resolution gaps: These transitional elements are key to maintaining visual continuity and mesh regularity when connecting areas of different detail.
  • Compactness through patch merging significantly improves efficiency: By intelligently combining patches, the number of connectivity maps and redundant vertices can be drastically reduced.
  • Regularity is a key advantage: The adaptive ACM leverages the inherent regularity of semiregular meshes to achieve its efficiency, outperforming more general structures like half-edge for such cases.

Key Results

  • The proposed adaptive ACM successfully supports adaptive subdivision, allowing for varying resolutions within a mesh.
  • The compact ACM algorithm significantly reduces the number of connectivity maps. For example, for the "Big Guy" model after three Catmull-Clark subdivisions, approximately 30,000 redundant vertices were removed.
  • The adaptive ACM is shown to be more memory-efficient than a half-edge structure for certain mesh configurations, by avoiding the need for explicit edge pointers and leveraging patch regularity.
  • Zippers are demonstrated to be more effective than red-green rules or incremental adaptive subdivision in maintaining mesh regularity, producing fewer extraordinary vertices and triangles.

Limitations and Future Work

  • Not the best for arbitrary connectivity: The paper acknowledges that the adaptive ACM does not offer a significant advantage over structures like the half-edge for models with highly irregular connectivity.
  • Optimizing patch combination: While the proposed algorithm for creating a compact ACM performs well, it does not guarantee the absolute best set of regular patches. Future work could focus on discovering more optimized algorithms for this.
  • Optimal zipper design: Determining the optimal zippers for specific face types, refinement strategies, or applications is suggested as a direction for future research.

Summary updated

BibTeX
@inproceedings{mahdaviamiri2014adaptive,
  author = {Ali Mahdavi-Amiri and Faramarz F. Samavati},
  title = {{Adaptive Atlas of Connectivity Maps}},
  booktitle = {Curves and Surfaces},
  year = {2014},
  doi = {10.1007/978-3-319-22804-4\_23},
}
Figure