Detecting the Observation Region: The Coupled Ring Adjacency Search

This post builds on the concepts contained in “Rendering the Static Icosphere in Unity Gaming Engine.”

Why We Need to Detect an Observation Region

At this point, we have an Icosphere which we can uniformly recurse to any depth we like. We also know that we can asymetrically recurse any arbitrary face of the icosphere, but we have no system for detecting or determining which face(s) to recurse.

Ultimately, we want the faces directly “below” the observer to be the faces under recursion – and the rest of the icosphere to remain unaffected. We want these faces to recurse only within a certain proximity of the user – when the user “zooms” in on these faces.

In order to do this, we will have to detect an “observation region;” a roughly circular region, centered on the icosphere directly beneath the user, consisting of some number of the icosphere’s exposed triangular faces.

Detecting the Observation Center

The first order of business will be not to detect the observation region, but to detect the Observation center.

Let us define the Observation Center as the triangular face of the icosphere directly beneath the observer. More specifically, if we fire a ray from the observer normal to the unit sphere upon which the icosphere is projected, the triangle which that ray pierces is the observation center.

We discover this observation center with a Unity API known as the Raycast. The Raycast is an invisible beam fired from a designated position in a designated direction for a designated distance. If the Raycast intersects a GameObject, the Raycast produces a RaycastHit.

Note: for the Raycast to actually hit your GameObject, the GameObject must have a collider attached to it (this caused me hours of pain).

The RaycastHit contains a collection of information about the collider which was hit by the ray. The particular piece of information that we are interested in is RaycastHit.triangleIndex. This returns the index of the mesh triangle of the collider that was hit.

If you remember in the last post, we were careful to maintain a mapping of Mesh triangles to Abstract Triangles. This is why.

Detecting the observation center is just a simple few lines of code, run during Unity’s “Update” method:

void Update()
{
    // Monitor which face is under direct observation.
    forwardRay = new Ray(camera.transform.position, camera.transform.forward);
    if (GetComponent<Collider>().Raycast(forwardRay, out hit, 1000))
    {
        observationCenter = hit.triangleIndex;
    }
}

At this point, if you would like to skip ahead to how I eventually successfully detect the observation region, please scroll ahead to the section: “The Coupled Ring Adjacency Search.”

Detecting the Observation Region: Everything That Did Not Work

The reason I include these failed methods is because they actually contain a number of common unity practices and tools that I believe are useful to keep in the back pocket for future development. It may be that one of these methods can help you in your own personal development, even though they weren’t what I needed.

If you would like to skip ahead to how I eventually successfully detect the observation region, please scroll ahead to the section: “The Coupled Ring Adjacency Search.”

Raycast Cone [Unity]

One of the first strategies I attempted was a Raycast “cone.” This is not a Unity API, but rather something I home-baked: a fanning cone of raycasts, of a configurable “fanning angle.”

This strategy “worked,” but because of the dispersal of the Rays, ways unable to consistently pick up all triangles within the fanning angle. By ratcheting up the ray count to about 1000, the cone was able to pick up all triangles within a 20 degree fanning angle at a recursive depth of 8, but this number of rays fired every frame absolutely crushed performance.

Spherecast and SpherecastAll [Unity]

Another Unity API that seemed promising was Spherecast. Spherecast, unlike Raycast, fires a sphere of configurable radius along a vector, and picks up GameObjects within its radius.

Spherecast only picks up a single game object, which might be suitable for our task (our Icosphere is a single game object), but the RaycastHit returned by Spherecast only holds data on a single impacted triangle, not all triangles within radius.

SpherecastAll[] returns an array of RaycastHits – but only one per game object, which still leaves us with the same problem.

Spherecast is a handy tool to keep in the back pocket for general Unity development, however.

Brute Vertex Search [Unity]

The simplest, most straight forward approach to detecting all triangles within a given radius from the observation center is to iterate through all vertices of the Mesh and evaluate their distance to the observation center.

Remember, when we created our Icosphere in Unity, we retained mappings of mesh triangles to abstract triangles: this is why. Mesh triangles, in turn, are directly related to the vertices array. With a little bit of thought, we can easily correlate an arbitrary vertex with its mesh triangle, and correspond that mesh triangle with an Abstract Triangle.

This “brute force” search worked, but unfortunately crushed performance once again – there was almost a quarter-second pause every time the observation center moved.

Bounded Volume Vertex Search [Unity & Abstract Icosphere]

What if we performed the Brute Vertex Search, but only in the coarse area directly surrounding the observation center?

Our triangles are already somewhat organized into “bounded regions:” the 20 R0 Icosahedral faces of our icosphere.

If we re-tool our Triangle object to maintain a pointer to its R0 Ancestor, equip our Triangle object with a method to “return ALL descendants,” and give our Triangle a new field, “centroid,” we can try the following:

  1. Scan all R0 Triangles and determine which subset of R0 triangles have centroids within the desired radius of the observation center.
  2. Obtain all descendants of the R0 triangles within range.
  3. Perform a brute vertex search on all implicated Triangles.

This method performed better than the brute vertex search, but still wasn’t great. Additionally, it produced some very strange, non-spherical Observation Regions.

This deformed region could be corrected by expanding the search radius for the R0 centroids and collecting a larger subset of them, but this would exacerbate the performance issue.

I believe that with some more work, tweaking or balancing, this method could have been made to work and possibly perform well, but I wound up finding a much better solution by harnessing the data structure of the Abstract Icosphere.

Naive Abstract Adjacency Search [Abstract Icosphere]

After trying numerous methods in Unity-space (raycasting, vertex searching), I decided to try some methods inside the Abstract Icosphere itself.

Given the Observation Center, we know that every triangle has three adjacencies. The simplest, naive approach to discover all adjacencies within radius would be:

  1. Get the Adjacencies of the Observation Center. Add them to the list of adjacencies.
  2. Get the adjacencies of all adjacencies we just discovered, incrementing a “radius” counter by 1.
  3. Recursively continue this process until our “radius counter” reaches the desired radius.

This method works, but performs even worse than all of the aforementioned methods.

However, this method can be optimized: by using the naive method above, there is a lot of redundancy in this search. By getting all of a triangle’s adjacencies, there is nothing to stop the search from backtracking and recursively searching a triangle that it’s already visited. In some cases of this search, triangles were being redundantly scanned hundreds of times.

“No Lookback” Adjacency Search [Abstract Icosphere]

We can attempt to optimize the abstract adjacency search by simply blocking the recursive method from revisiting a Triangle that it has already visited. This will in turn stop the method from recursing further in the wrong direction.

The “no lookback” adjacency search “worked,” and performed really well – sortof.

For a search radius of 1, 2 or 3, the No Lookback search produced the roughly circular region as expected.

For search radii greater than 3, I started to receive some extremely odd, amorphous regions that took me quite some time to understand.

Because of how the “no lookback” search was being called, in essence, the “tree” of adjacencies stemming from the observation center’s first adjacency looked something like this:

This looks correct (so far). However, all of these triangles are part of the “no lookback” set – they can never be revisited. That means, when we explore the tree of adjacencies stemming from the observation center’s second adjacency, we get “choked out” by the A1 adjacencies:

The region that we should be getting would include these purple cells:

Furthermore, adjacency 3 of the observation center is now a “no lookback” zone, so we won’t get to explore anywhere below the highlighted region.

This discrepancy snowballs into quite an odd looking region when we expand the search to a radius of 10 and beyond. It would even generate weird “islands” that were missed by the adjacency search.

The Coupled Ring Adjacency Search [Abstract Icosphere]

What finally worked and performed was a method called the “coupled ring search.”

  1. Find all adjacencies to the observation center: these are “Ring 1”. Save these off to an “All Adjacencies” collection.

2. Find all adjacencies to Ring 1 excluding any Triangles in the “All Adjacencies” collection. Call these “Ring 2.” Add them to “All Adjacencies.”

3. Find all adjacencies to Ring 2, excluding any triangles in the “All Adjacencies” collection. Call these “Ring 1.” Add them to “All Adjacencies.”

4. Repeat this process, leapfrogging outward using Ring 1 and Ring 2 as buffers, until we reach the desired radius.

This adjacency search, I believe, will not only serve us now, while establishing the Observation Region, but later when we need to generate planetary maps. Therefore, this method lives in Abstract Icosphere, so that we can make repeated use of it in the backend data system.

The method looks something like this:

private HashSet<Triangle> coupledRingSearch(Triangle center, int radius)
{
    // Initialize Collections
    HashSet<Triangle> adjacencies = new HashSet<Triangle>();
    HashSet<Triangle> ring1 = new HashSet<Triangle>();
    HashSet<Triangle> ring2 = new HashSet<Triangle>();

    // Add the origin to the collection of all adjacencies and make it ring 1
    adjacencies.Add(center);
    ring1.Add(center);

    // Begin coupled ring search
    ring1Search(adjacencies, ring1, ring2, radius, 0);

    return adjacencies;
}

// Search ring 1 for adjacencies.
private void ring1Search(HashSet<Triangle> allAdjacencies, HashSet<Triangle> ring1, HashSet<Triangle> ring2, int radius, int currentBreadth)
{
    // If we have not yet reached the search radius,
    if (currentBreadth < radius)
    {
        // Set up a buffer
        HashSet<Triangle> buffer =  new HashSet<Triangle>();

        // For each triangle in ring 1,
        foreach (Triangle t in ring1)
        {
            // Add adjacencies (duplicates will be skipped).
            if (t.adjacency1.visible)
            {
                // Add adjacency 1 to all adjacencies.
                allAdjacencies.Add(t.adjacency1);
                
                // If adjacency 1 is not present in ring 2, save it to be added to the next ring 2.
                if (!ring2.Contains(t.adjacency1))
                {
                    // Save adjacency 1 to be added to Ring 2.
                    buffer.Add(t.adjacency1);
                }
            }
            if (t.adjacency2.visible)
            {
                // Add adjacency 2 to all adjacencies.
                allAdjacencies.Add(t.adjacency2);

                // If adjacency 2 is not present in ring 2, save it to be added to the next ring 2.
                if (!ring2.Contains(t.adjacency2))
                {
                    // Save adjacency 2 to be added to Ring 2.
                    buffer.Add(t.adjacency2);
                }
            }
            if (t.adjacency3.visible)
            {
                // Add adjacency 3 to all adjacencies.
                allAdjacencies.Add(t.adjacency3);

                // If adjacency 3 is not present in ring 2, save it to be added to the next ring 2.
                if (!ring2.Contains(t.adjacency3))
                {
                    // Save adjacency 3 to be added to Ring 2.
                    buffer.Add(t.adjacency3);
                }
            }
        }

        // Now that we are done with the old Ring 2, we can clear it and reset it to the new ring 2.
        ring2.Clear();
        ring2 = buffer;

        // Initiate Ring 2 Search.
        ring2Search(allAdjacencies, ring1, ring2, radius, currentBreadth + 1);
    }
}

// Search Ring 2 for adjacencies.
private void ring2Search(HashSet<Triangle> allAdjacencies, HashSet<Triangle> ring1, HashSet<Triangle> ring2, int radius, int currentBreadth)
{
    // If we have not yet reached the search radius,
    if (currentBreadth < radius)
    {
        // Set up a buffer
        HashSet<Triangle> buffer =  new HashSet<Triangle>();

        // For each triangle in ring 2,
        foreach (Triangle t in ring2)
        {
            // Add adjacencies (duplicates will be skipped).
            if (t.adjacency1.visible)
            {
                // Add adjacency 1 to all adjacencies.
                allAdjacencies.Add(t.adjacency1);

                // If adjacency 1 is not present in ring 1, save it to be added to the next ring 1.
                if (!ring1.Contains(t.adjacency1))
                {
                    buffer.Add(t.adjacency1);
                }
            }
            if (t.adjacency2.visible)
            {
                // Add adjacency 2 to all adjacencies.
                allAdjacencies.Add(t.adjacency2);

                // If adjacency 2 is not present in ring 1, save it to be added to the next ring 1.
                if (!ring1.Contains(t.adjacency2))
                {
                    buffer.Add(t.adjacency2);
                }
            }
            if (t.adjacency3.visible)
            {
                // Add adjacency 3 to all adjacencies.
                allAdjacencies.Add(t.adjacency3);
                
                // If adjacency 3 is not present in ring 1, save it to be added to the next ring 1.
                if (!ring1.Contains(t.adjacency3))
                {
                    buffer.Add(t.adjacency3);
                }
            }
        }

        // Now that we are done with the old ring 1, we can clear it and reset it to the new ring 1.
        ring1.Clear();
        ring1 = buffer;

        // Initialize Ring 1 search
        ring1Search(allAdjacencies, ring1, ring2, radius, currentBreadth + 1);
    }
}

Making Use of the Results

We now have a fast method of detecting the observation region. We need to set up our Update method to make use of it.

void Update() 
{
    // Monitor which face is under direct observation.
    forwardRay = new Ray(camera.transform.position, camera.transform.forward);
    if (GetComponent<Collider>().Raycast(forwardRay, out hit, 1000))
    {
        observationCenter = hit.triangleIndex;
    }

    // If the observation center has changed, update ring 1
    if (observationCenter != previousObservationCenter)
    {
        observationGroup.Clear();

        foreach (Triangle t in icosphere.coupledRingSearch(meshToAbstractIcosphereMap[meshIndex], searchRadius))
        {
            observationGroup.Add(t.uniqueIndex);
        }

        HighlightObservationGroup();
    }

    previousObservationCenter = hit.triangleIndex;
}

At this point, the observer can navigate about the Icosphere and we can always maintain knowledge of their observation region.

The radius of the observation region can be adjusted dynamically based on the observer’s “altitude” as well.

However, our work is not yet done. At this point, we need to begin recursing the observation region. As we will quickly come to learn, this is not straightforward when we are observing a region of uneven detail.

2 thoughts on “Detecting the Observation Region: The Coupled Ring Adjacency Search

    1. Hey Vivek, you can learn all about the Triangle class here. The source code isn’t on the page, but this post describes all of the required elements and aspects of the Triangle class.

      The Icospherical World Model: Problem Specification and Preliminary Data Structure

      Performing a ring search for a square / rectangle shape would be a totally different problem with different challenges and solutions. I’m not even sure the ring search would be the best option for this. You should investigate and let me know if you learn anything!

      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