Click or drag to resize
Topologies

The core of the Make It Tile framework is a topology, a data structure for representing the relations between vertices, edges, and faces.

This topic contains the following sections:

Overview

In terms of the primary use case for this framework, faces are typically synonymous with tiles, while vertices are the corners of each tile. Edges are the boundaries between two adjacent faces/tiles, and they can simultaneously be treated as the connections between two adjacent vertices/corners.

Below is an example topology for a hexagonal grid. It consists of 16 faces, 48 vertices, and 63 edges (split into 126 half-edge pairs).

hex-grid-1
A topology for a hexagonal grid.

The Topology class is responsible for storing all the raw data of the topology data structure. It provides access to the elements of this data structure through collections of the nested types TopologyVertex, TopologyFace, and TopologyHalfEdge. Edges can also be access through the types TopologyVertexEdge and TopologyFaceEdge for special behavior as will be explained below.

The majority of faces in a topology will be ordinary internal faces, but depending on the shape and edge-wrapping behavior of the topology, some faces might be external. This means that they are not really part of the surface described by the topology, but are included to simplify behavior of the data structure along the boundaries of the topology. In the above hexagonal grid example, there is a single unmarked external face that surrounds the the other faces.

Accessing the elements of a topology.
Topology topology = ...; // Create a topology.

// Element collections can be enumerated using a foreach loop:
foreach (Topology.Vertex vertex in topology.vertices)
{
    // do something with the vertex
}

// They can also be accessed by integer indices:
for (int i = 0; i < topology.faces.Count; ++i)
{
    Topology.Face face = topology.faces[i];
    // do something with the face
}

// The two subsets of faces, internal and external, can also be enumerated:
foreach (Topology.Face face in topology.internalFaces)
{
    // do something with the face
}

// The edges are accessible in three varieties, all representing
// the same set of edges, but producing different behavior in
// certain cases, as will be explained in other topics.
foreach (Topology.HalfEdge edge in topology.halfEdges)
{
    // do something with the edge
}
Neighbors & Edges

Edges are the elements of the topology data structure that express neighbor relationships among vertices and faces, as well as among other edges.

hex-grid-vertex-neighbors
The neighboring edges of a vertex.

In the above diagram, a single vertex, 32, has been highlighted in blue. Around it, three half-edges have been highlighted in red, 52, 56, and 84. These are the neighboring edges of the vertex. It is through these edges that one can observe the relations to other vertices and to the faces around the vertex.

For each vertex, only one of its neighboring edges is stored. This is the vertex's first edge. In the above case, let's assume that egde 52 is the first edge of vertex 32. (It could have been any of the three; nothing prioritizes any edge over any other as being the first.) The rest of the vertex's neighboring edges can be found by following what is essentially a circular linked list starting from the first edge. It is guaranteed to proceed clockwise around the vertex, when viewed from above the surface. Thus, the next edge would by 84, followed by 56. And 56 will just link back to 52 since the list is circular. To get the first edge for a vertex, you can access the propety firstEdge.

When using the TopologyHalfEdge type, the property nextAroundVertex can be used to traverse this linked list. If backwards traversal is needed, prevAroundVertex is also available, but is a bit slower. If the TopologyVertexEdge type is used instead, then visiting the neighboring edges of a vertex is simplified a bit through the properties next and prev.

Most of the time, you can simplify this process of visiting a vertex's neighboring edges even further by using the property edges. This returns an enumerable object of instances of TopologyVertexEdge, ideal for use in a foreach loop.

Accessing the neighboring edges of a vertex.
Topology topology = ...; // Create a topology.

foreach (Topology.Vertex vertex in topology.vertices)
{
    // Automatic enumeration using the edges property
    foreach (Topology.VertexEdge edge in vertex.edges)
    {
        // do something with the edge
    }

    // Manual enumeration using the firstEdge and next properties
    var firstEdge = vertex.firstEdge;
    var currentEdge = firstEdge;
    do
    {
        // do something with currentEdge
        currentEdge = currentEdge.next;
    } while (currentEdge != firstEdge);
}
hex-grid-face-neighbors
The neighboring edges of a face.

Faces behave just like vertices in regard to neighboring edges. The neighboring edges of face 6 above are 36, 37, 38, 39, 40, and 41. The order of the neighboring edges is clockwise, just as with the neighboring edges of a vertex. The property firstEdge gives one access to head of the linked list of neighboring faces. The properties nextAroundFace and prevAroundFace are available on the type TopologyHalfEdge, and next and prev are the shorthand properties available on the type TopologyFaceEdge. Finally, the property edges returns an enumerable object of instances of TopologyFaceEdge, ideal for use in a foreach loop.

Accessing the neighboring edges of a face.
Topology topology = ...; // Create a topology.

foreach (Topology.Face face in topology.internalFaces)
{
    // Automatic enumeration using the edges property
    foreach (Topology.FaceEdge edge in face.edges)
    {
        // do something with the edge
    }

    // Manual enumeration using the firstEdge and next properties
    var firstEdge = face.firstEdge;
    var currentEdge = firstEdge;
    do
    {
        // do something with currentEdge
        currentEdge = currentEdge.next;
    } while (currentEdge != firstEdge);
}
Edge Relations

To use edges to access further elements of a topology, there are the properties vertex and face. These properties access the target objects at the far end of the edge. For vertices, the target is obvious; it is the vertex that the edge's arrow is pointing to, in the diagrams above. The target face is a bit less intuitive, however. It is the face immediately adjacent to the half-edge, into which the half-arrow line is extended.

hex-grid-vertex-neighbors
The neighboring edges of a vertex.

Revisiting the diagram with the neighbors of the vertex, we can see that the neighboring vertices are therefore 19, 31, and 33, which are respectively the target vertices of edges 52, 84, and 56. Likewise, the neighboring faces are 9, 8, 14, corresponding to the same edges.

For clarity when it is appropriate, TopologyVertexEdge provides the properties farVertex and nearVertex. The former is identical to vertex, and the latter provides (slightly slower) access to the vertex at the source end of the edge. Similarly, prevFace is equivalent to face, and nextFace provides access to the face on the other side of the edge. (Note that "prev" and "next" continue to consistently refer to counter-clockwise and clockwise movement around the reference element, vertex 32 in this case.)

Accessing the neighbors of a vertex.
Topology topology = ...; // Create a topology.

foreach (Topology.Vertex vertex in topology.vertices)
{
    foreach (Topology.VertexEdge edge in vertex.edges)
    {
        Topology.Vertex neighborVertex = edge.vertex;
        Topology.Face neighborFace = edge.face;

        Topology.Vertex currentVertex = edge.nearVertex; // same as the local vertex variable
        Topology.Vertex farVertex = edge.farVertex; // same as edge.vertex

        Topology.Face prevFace = edge.prevFace; // face on CCW side of edge, same as edge.face
        Topology.Face nextFace = edge.nextFace; // face on CW side of edge
    }
}
hex-grid-face-neighbors
The neighboring edges of a face.

Looking at the neighbors of a face, we can see that the neighboring vertices are 13, 26, 27, 28, 15, and 14, which are respectively the target vertices of edges 36, 37, 38, 39, 40, and 41. Likewise, the neighboring faces are 0, 5, 11, 12, 7, and 1, corresponding to the same edges.

As with vertices, the following additional properties are available on the type TopologyFaceEdge: farFace, nearFace, nextVertex, and prevVertex. farFace is the same as face, but note that, in a reversal from vertices, it is not prevVertex that is the same as vertex, but nextVertex. This is simply a necessary artifact of how the geometry of the winding order works out, in order to maintain consistency with clockwise ordering.

Accessing the neighbors of a face.
Topology topology = ...; // Create a topology.

foreach (Topology.Face face in topology.faces)
{
    foreach (Topology.FaceEdge edge in face.edges)
    {
        Topology.Face neighborFace = edge.face;
        Topology.Vertex neighborVertex = edge.vertex;

        Topology.Face currentFace = edge.nearFace; // same as the local face variable
        Topology.Face farFace = edge.farFace; // same as edge.face

        Topology.Vertex prevVertex = edge.prevVertex; // vertex on CCW side of edge
        Topology.Vertex nextVertex = edge.nextVertex; // vertex on CW side of edge, same as edge.vertex
    }
}

Finally, edges have the property twin, which simply returns the adjacent half-edge pointing in the opposite direction. The twin of edge 38, for example, is 71. It is through the twin, in fact, that the near vertex and near face can be determined, as well as the previous edge around either the vertex or face, since edges only directly store data regarding the far vertex and face, and the next edges in the clockwise direction.

Outer Edges

The properties Vertex.edges and Face.edges serve to provide access to neighboring vertices and faces that are immediately connected to the source vertex or face through a single edge. Sometimes the concept of adjacency needs to expand out a little further, however. A very common case is with square grids for which squares in diagonal directions are considered adjacent. The above two properties will only enumerate the four neighbors that share an edge with a vertex or face.

The properties Vertex.outerEdges and Face.outerEdges enable you to enumerate neighbors in such a way that diagonal connections are included. Below you can see the difference between the normal set of neighboring edges, in blue, and the larger set of outer edges, in red.

square-grid-outer-edges
Neighbor edges in blue, and outer edges in red, for a vertex on left, and face on right.

The left diagram shows the edges and outer edges of vertex 5. If the far vertex of each ordinary edge is accessed, you can see that the immediate neighbors of vertex 5 are vertices 1, 4, 9, and 6. Looking at the far vertices of the outer edges, the neighboring vertices become 0, 4, 8, 9, 10, 6, 2, and 1, so the four diagonal vertices are included with the first four. In essence, these are the vertices that share at least one face with the source vertex, even if they do not share an edge.

Enumerating the outer neighbors of a vertex.
Topology topology = ...; // Create a topology.

Topology.Vertex vertex = topology.vertices[5];
foreach (Topology.VertexEdge edge in vertex.outerEdges)
{
    Debug.LogFormat("Edge {0}, Vertex {1}", edge.index, edge.vertex.index);
}

Likewise, the diagram on the right shows the edges and outer edges of face 4. It is a little harder to follow, but you can see that the four ordinary neighboring edges 16, 17, 18, and 19 face outward toward the direct neighboring faces 1, 3, 7, and 5. But the outer edges 3, 12, 24, 29, 33, 22, 10, and 7 face outward toward faces 1, 0, 3, 6, 7, 8, 5, and 2. Just as with vertices, all eight neighboring faces are included. And again, in essence, these are the faces that share at least one vertex with the source face, even if they do not share an edge.

Enumerating the outer neighbors of a face.
Topology topology = ...; // Create a topology.

Topology.Face face = topology.faces[4];
foreach (Topology.FaceEdge edge in face.outerEdges)
{
    Debug.LogFormat("Edge {0}, Face {1}", edge.index, edge.face.index);
}
See Also