Recursion of the Icosphere and Maintaining Adjacency

This post builds on the concepts contained in the previous post: “Building the Unit Icosahedron.”

Now that we have a basic unit Icosahedron, consisting of twenty indexed Triangle objects, all of which have adjacency knowledge, we are ready to begin recursing the faces of our Icosahedron to form an Icosphere.

The recursing of the Icosphere would be a relatively simple task were it not for the fact that our triangles must maintain Adjacency data at all times. Maintaining adjacency data would also not be too daunting a task, were it not for the fact that we are planning on asymmetrically recursing this Icosphere.

Simple Uniform and Non-Uniform Recursion

To recurse a single face of the Icosphere, we must create three midpoints in that face:

  • a, between v1 and v2, projected to the unit sphere.
  • b, between v2 and v3, projected to the unit sphere.
  • c, between v3 and v1, projected to the unit sphere.

We then can define descendants 1 – 4 by using our three vertices and three midpoints. Recall our diagram from “Problem Specification and Preliminary Data Structure:”

For each descendant, the order of vertices is critically important. The direction in which we “wind” the vertices determines where the descendant’s adjacencies will lie. We will rely on this knowledge later.

With this diagram in mind, we can easily construct four new triangles.

// Recurse a single face of the icosphere.
public void recurseSingleFace(int index)
{
    // Obtain the face to recurse.
    Triangle faceToRecurse = faces[index];

    // Determine the recursive depth of these triangles.
    int newDepth = faceToRecurse.recursiveDepth + 1;

    // Obtain the midpoints of each side of the triangle.
    Vector3 a = addVertexToUnitSphere(obtainMidpoint(faceToRecurse.v1, faceToRecurse.v2));
    Vector3 b = addVertexToUnitSphere(obtainMidpoint(faceToRecurse.v2, faceToRecurse.v3));
    Vector3 c = addVertexToUnitSphere(obtainMidpoint(faceToRecurse.v3, faceToRecurse.v1));

    // Construct four triangles.
    // uniqueIndex, parent, recursive depth, vertex 1, vertex 2, vertex 3 
    Triangle t1 = new Triangle(latestIndex++, faceToRecurse, newDepth, faceToRecurse.v1, a, c); 
    Triangle t2 = new Triangle(latestIndex++, faceToRecurse, newDepth, a, faceToRecurse.v2, b);
    Triangle t3 = new Triangle(latestIndex++, faceToRecurse, newDepth, c, b, faceToRecurse.v3);
    Triangle t4 = new Triangle(latestIndex++, faceToRecurse, newDepth, b, c, a);

    // Assign these triangles as descendants of the parent.
    faceToRecurse.descendant1 = t1;
    faceToRecurse.descendant2 = t2;
    faceToRecurse.descendant3 = t3;
    faceToRecurse.descendant4 = t4;

    // Add the new faces to the dictionary.
    faces.Add(t1.uniqueIndex, t1);
    faces.Add(t2.uniqueIndex, t2);
    faces.Add(t3.uniqueIndex, t3);
    faces.Add(t4.uniqueIndex, t4);

    // Set the parent to invisible.
    faceToRecurse.visible = false;
}

Note that we are using the private helper method, “obtainMidpoint.”

// Find the midpoint between two 3D points.
private Vector3 obtainMidpoint(Vector3 p1, Vector3 p2)
{
    return new Vector3(
        (p1.X + p2.X) / 2.0f,
        (p1.Y + p2.Y) / 2.0f,
        (p1.Z + p2.Z) / 2.0f
    );
} 

With this new method, “recurseSingleFace,” we can now construct an Icosphere of any recursive depth we like. AbstractIcosphere‘s constructor would look something like this:

public AbstractIcosphere(int recursiveDepth) 
{
    // Intialize 
    faces = new Dictionary<int, Triangle>();
    
    // Generate the base 20 faces of the Icosphere. (See the last blog post)
    generateUnitIcosahedron();

    // Recurse the icosphere.
    for (int i = 0; i < recursiveDepth; i++)
    {
        uniformlyRecurseIcosphere();
    }

    // We will come to this later
    purgeAncestry();
}

The constructor employs the private hepler method, UniformlyRecurseIcosphere.

private void uniformlyRecurseIcosphere()
{
    // Create a temporary dictionary of all visible faces.  We will recurse this temporary collection so we don't
    // cross-contaminate our master collection while we are in the process iterating through it.
    Dictionary<int, Triangle> temporaryFaces = new Dictionary<int, Triangle>();

    // Pull out the visible faces.
    foreach (Triangle t in faces.Values)
    {
        if (t.visible)
        {
            temporaryFaces.Add(t.uniqueIndex, t);
        }
    }

    // Each of these Triangles is a reference.  Thus, updating it in our temporary collection
    // will also update it in our master collection.
    foreach (Triangle t in temporaryFaces.Values)
    {
        recurseSingleFace(t.uniqueIndex);
    }
}

We have not gotten to rendering yet, but if we were to render our AbstractIcosphere at this point, here is how it might appear being initialized with a variety of recursive depths.

Additionally, if we chose to employ RecurseSingleFace() on only a specific face, we can asymmetrically recurse the icosphere. It might appear like this:

The Four Cases of Adjacency

When we recurse a face of the icosahedron, we must determine the adjacencies of the four descendants. In order to do this, we can use the adjacency data of the parent triangle and our knowledge of the descendant triangle’s position and orientation.

The Descendant will find itself in one of four situations:

Case 1: The descendant has Co-Descendants of matching recursive depth. These co-descendants will be the descendants of the Parent Triangle’s Adjacencies.

In this picture, you can see the R0 Triangular layer highlighted in blue. A descendant of the central parent is filled with white. Its adjacencies are filled with grey. Its adjacencies are all of a matching depth: R1.

Case 2: Descendant has no Co-Descendants of matching recursive depth. Its adjacencies will be of a shallower depth.

In this picture, you can see that the Parent Triangle’s second adjacency has no descendants. Thus, it is Descendant 3’s second adjacency.

Case 3: Imagine the parent’s second adjacency becomes twice recursed. Now, Descendant 3 will have numerous second-adjacencies, of a deeper recursive depth.

Case 4: The fourth descendant always has three guaranteed adjacencies: the first, second and third descendants.

Of these four cases, Case 3 is the problematic case. If we are allowing a triangle to have multiple adjacencies on one side, we are in essence opening the gates of hell. A triangle, now instead of having three guaranteed adjacencies no matter what, could now have N adjacencies. While this is theoretically maintainable, I believe it is much simpler and much cleaner to simply say: A Triangle’s adjacency is always the deepest co-descendant which does not exceed the Triangle’s own depth.

This means that in our Case 3, Descendant 3 would take an invisible ancestor triangle as its adjacency. It would take the three R2 triangles’ shared Parent triangle as its adjacency.

This is why it is imperative that we maintain knowledge of invisible triangles. If you remember, we raised this question in an earlier discussion and I deferred it to later: that time is now.

By retaining knowledge of a triangle’s invisible parents, we have in essence created a Quadtree Data Structure. To discover adjacencies of a newly produced triangle, we can climb up the current tree to the new triangle’s parent, step into neighboring branches of the tree by visiting the parent’s adjacencies, and descend these neighboring branches to discover adjacencies.

Finding Adjacencies

Now that we have decided how to handle all four cases of adjacency, it’s time to put it into code.

Because we’ve made sure that our Triangles abide by a strict internal ordering system (ordered vertices, adjacencies and descendants), there is a lot of information we have up front.

  • Descendant 1’s first adjacency is always either the parent’s first adjacency, or among that Triangle’s descendants.
  • Descendant 1’s second adjacency is always Descendant 4.
  • Descendant 1’s third adjacency is always either the parent’s third adjacency, or among that Triangle’s descendants.

We can come up for a similar set of rules for each descendant; I will not list them all here. By referencing our “map” at the top of this blog post, each descendant will have a set of three rules very similar to Descendant 1’s rules. The exception is Descendant 4, the easiest case: Descendant 4’s three adjacencies, in order, are Descendants 3, 1 and 2.

However, despite all of our internal knowledge about our ordered triangle, we do not know what the orientation of the parent’s adjacencies are. For this reason, we will need to do some vertex search and comparison.

Additionally, before we get to code, there is one more wrinkle that we have not considered. When we create a new Descendant, not only must we discover that descendant’s adjacencies, we must update all of those adjacencies with knowledge of descendant 1.

The following method will scan for Descendant 1’s adjacencies. It also will update those adjacencies with knowledge of Descendant 1.

// Update the adjacencies of the triangle t, and also update the adjacencies of every neighboring triangle.
// If recurse is set to true, we need to update neighbors.  If it is false, then this is a neighbor's update; don't update neighbors.
private void updateDescendant1Adjacencies(Triangle t, bool recurse)
{
    // Obtain relevant parental adjacencies.
    Triangle parentalNeighbor1 = t.parent.adjacency1;
    Triangle parentalNeighbor3 = t.parent.adjacency3;

    // Set adjacency to child 4.
    t.adjacency2 = t.parent.descendant4;

    // See how deeply parental neighbor 1 recurses.
    Triangle deepestDescendantOfParentalNeighbor1 = descendToRecursiveLevel(parentalNeighbor1, t.recursiveDepth);

    // Either we will reach a matching depth, or we will reach a more shallow depth.
    if (deepestDescendantOfParentalNeighbor1.recursiveDepth < t.recursiveDepth)
    {
        // If we have reached a more shallow depth, this triangle is t's neighbor.
        t.adjacency1 = deepestDescendantOfParentalNeighbor1;

        // In this case, the deepest descendant of parental neighbor 1 needs no adjacency update.  
        // It's adjacency is at a level more shallow than t.
    }
    else
    {
        // If we have reached a matching depth, we must scan all co-descendants for an adjacency.
        t.adjacency1 = scanForSharedVertices(t, deepestDescendantOfParentalNeighbor1.parent);

        // In this case, the co-descendants of the parental neighbor need an adjacency update; they need knowledge of t and its siblings.
        // TODO: This seems like a heavy handed solution.  Maybe there is a more graceful way to update these co-descendants.
        if (recurse)
        {
            updateDescendant1Adjacencies(deepestDescendantOfParentalNeighbor1.parent.descendant1, false);
            updateDescendant2Adjacencies(deepestDescendantOfParentalNeighbor1.parent.descendant2, false);
            updateDescendant3Adjacencies(deepestDescendantOfParentalNeighbor1.parent.descendant3, false);
        }
    }

    // See how deeply parental neighbor 3 recurses. 
    Triangle deepestDescendantOfParentalNeighbor3 = descendToRecursiveLevel(parentalNeighbor3, t.recursiveDepth);

    // Either we will reach a matching depth, or we will reach a more shallow depth.
    if (deepestDescendantOfParentalNeighbor3.recursiveDepth < t.recursiveDepth)
    {
        // If we have reached a more shallow depth, this triangle is t's neighbor.
        t.adjacency3 = deepestDescendantOfParentalNeighbor3;

        // In this case, the deepest descendant of parental neighbor 3 needs no adjacency update.  
        // It's adjacency is at a level more shallow than t.
    }
    else 
    {
        // If we have reached a matching depth, we must scan all co-descendants for an adjacency.
        t.adjacency3 = scanForSharedVertices(t, deepestDescendantOfParentalNeighbor3.parent);

        // In this case, the co-descendants of the parental neighbor need an adjacency update; they need knowledge of t and its siblings.
        // TODO: This seems like a heavy handed solution.  Maybe there is a more graceful way to update these co-descendants.
        if (recurse)
        {
            updateDescendant1Adjacencies(deepestDescendantOfParentalNeighbor3.parent.descendant1, false);
            updateDescendant2Adjacencies(deepestDescendantOfParentalNeighbor3.parent.descendant2, false);
            updateDescendant3Adjacencies(deepestDescendantOfParentalNeighbor3.parent.descendant3, false);
        }
    }
}

We of course will need to create corresponding methods, UpdateDescendant2Adjacencies(), UpdateDescendant3Adjacencies() and UpdateDescendant4Adjacencies(), which are similar enough to the above method that I do not believe they need to be notated here.


This method uses the private helper method descendToRecursiveLevel. This method, given a triangle of depth A and a target depth B, will do its best to descend the Quad Tree to depth B. If it cannot reach depth B, it will return a Triangle of the deepest recursive depth it was able to reach.

// Probe from Triangle t to the specified recursive depth.
// If the level of depth does not exist, return the deepest available depth.
private Triangle descendToRecursiveLevel(Triangle t, int targetDepth)
{
    // If we are at the target depth, return this triangle.
    if (t.recursiveDepth == targetDepth)
    {
        return t;
    }

    // If this triangle has no descendants, return this triangle.
    if (t.descendant1 == null || t.descendant2 == null || t.descendant3 == null || t.descendant4 == null)
    {
        return t;
    }

    // Otherwise, scan for descendants.
    int currentDepth = t.recursiveDepth;

    // Get the deepest level available of each descendant.
    Triangle deepestDescendant1 = descendToRecursiveLevel(t.descendant1, targetDepth);
    Triangle deepestDescendant2 = descendToRecursiveLevel(t.descendant2, targetDepth);
    Triangle deepestDescendant3 = descendToRecursiveLevel(t.descendant3, targetDepth);
    Triangle deepestDescendant4 = descendToRecursiveLevel(t.descendant4, targetDepth);

    // Find the deepest descendant of the deepest descendants.
    Triangle deepest = deepestDescendant1;
    deepest = (deepestDescendant2.recursiveDepth > deepest.recursiveDepth) ? deepestDescendant2 : deepest;
    deepest = (deepestDescendant3.recursiveDepth > deepest.recursiveDepth) ? deepestDescendant3 : deepest;
    deepest = (deepestDescendant4.recursiveDepth > deepest.recursiveDepth) ? deepestDescendant4 : deepest;

    return deepest;
}

This method also relies on scanForSharedVertices. This method scans the a triangle for any descendants which share two vertices with a target triangle.

private Triangle scanForSharedVertices(Triangle scanningFrom, Triangle scanDescendantsOf)
{
    // For each codescendant,
    Triangle adjacency = null;
    foreach (Triangle potentialAdjacency in scanDescendantsOf.descendants)
    {
        // If we have not yet found an adjacency,
        if (adjacency != null)
        {
            break;
        }

        // For each vertex of this codescendant,
        int sharedVertices = 0;
        foreach (System.Numerics.Vector3 vertex in potentialAdjacency.vertices)
        {
            // If the vertex matches one of the vertices of the triangle we are scanning from, log it
            if (vertex.Equals(scanningFrom.v1) || vertex.Equals(scanningFrom.v2) || vertex.Equals(scanningFrom.v3))
            {
                sharedVertices++;
            }
            // If we have found two vertex matches, this is our adjacency; break
            if (sharedVertices >= 2)
            {
                adjacency = potentialAdjacency;
                break;
            }
        }
    }
    return adjacency;
}

Now that we are equipped with the ability to scan for adjacencies, we need to go back to recurseSingleFace and make sure we’re employing this ability. All that we need to add to recurseSingleFace is the following:

// Determine the adjacencies of each new triangle
updateAdjacencies(t1, true);
updateAdjacencies(t2, true);
updateAdjacencies(t3, true);
updateAdjacencies(t4, true);

At this point, we can recurse our icosphere uniformly and non-uniformly, all the while, retaining our knowledge of adjacency with a Quad-Tree structure.

Rejoice, for if this seemed confusing, rendering the Icosphere in Unity (our next step) will turn out to be be far worse.

6 thoughts on “Recursion of the Icosphere and Maintaining Adjacency

  1. Hi Keegan, I just discovered this fascinating series — thanks so much for posting this! Quick question: In descendToRecursiveLevel(), you say

    // If this triangle has no descendants, return this triangle.
    if (t.descendant1 == null || t.descendant2 == null || t.descendant3 == null || t.descendant4 == null) …

    The comment “has no descendants” implies that you’re checking that *all* the descendants are null. But the code returns if *any* one of them is null. If some are assigned but one is not, you return. Why?

    Is it just that you’re guaranteed that there are always either 4 or 0 descendants, and so the OR checks will either all pass or fail? If so, I don’t see it’s more efficient — all the conditions still have to be checked, just as with AND — and a bit confusing. Am I missing something?

    Thanks again, I’m really enjoying this — very impressive work!

    Liked by 1 person

    1. Hey Val –

      You’re absolutely right, the code comment does not match the actual behavior of the code here! I’ll have to fix it.

      You are correct in assuming that a triangle will either have zero or four descendants – nothing in between. If it DOES have 1-3 descendants, something has gone terribly wrong, probably a poorly handled reference somewhere.

      I do believe that technically, at least in Java, if the a condition of a string of OR statements is true, the rest are ignored. So while you are right, there are 3 redundant checks here, I think in terms of runtime performance we are not generating three superfluous method calls.

      That being said, your observation is correct: the check does not match the comment, I’ll have to update it!

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s