Adjacency Data Structures - Navigating a Mesh


Adjacency Data Structures Adjacency - Navigating a Mesh

III. Adjacency - Navigating a Mesh

  1. Simple Adjacency

    • Vertex, Edge, and Face Structures
    • Each element has list of pointers to all incident elements
    • Queries depend only on local complexity of mesh!
    • Slow! Big! Too much work to maintain!
    • Data structures do not have fixed size

    Vertex

    Edge

    Face

  2. We've Added a Third Kind of Data

    • Geometric Information
    • Attribute Information
    • Topological Information

  3. Winged Edge Data Structure (Baumgart, 1975)

    • Main Data Structure: Edge
    • 4 Adjacent Edges -> 4 Pointers




      • Vertex

      Edge

      Face


    • Vertices and Faces have a single pointer to one incident Edge
    • Fixed size data structures
    • No consistent way to order pointers

  4. Another Look at Adjacency

    • Four ways to look at an Edge (demo)


This page created and maintained by Justin Legakis
legakis@graphics.lcs.mit.edu
Last modified: 2/14/98