Recursing and Repacking the Observation Region

This post builds on the concepts outlined through out the previous Icospherical World Model posts.

Personal Update

Hello everyone! It’s been a while since my last post (four months)! Life has been pretty wild with the pandemic, and I have had a lot of music work going on. In addition to this, I’ve been applying to grad school for physics! However, I have been continuing work on PISES and also forking its icosphere for use on other projects.

Recursing the Observation Region

In the last technical post about the Icosphere, we designed and employed a Coupled Ring Search to detect the observation region. This is the region that we will break down into descendant triangles when the observer draws near enough – and eventually, pack back up into ancestor triangles when the observer retreats far enough.

Aside: Increasing Unity’s Vertex Limit

By default, Unity’s Mesh Index Buffer only supports 65,535 vertices. For almost all ostensible purposes, there is no reason to increase this buffer size. In fact, once we work out repacking (packing up descendant triangles into their ancestors), we will not need this limit increased. However, in the interim, to avoid weird behavior and drop-outs, I suggest increasing this Mesh Index Buffer to 32 bits, increasing our vertex limit to about 4 billion. This is easily achieved at program start:

Observational Thresholds

When approaching and retreating from the icosphere, we will need to establish a set of altitudes at which to:

  1. On Descent, decompose the observation group into descendant triangles.
  2. On Ascent, recombine the observation group into their parent triangles.

Additionally, our adjacency search radius needs to adapt, shrinking and expanding based on altitude.

The following thresholds I have arrived at simply by experimentation – what “feels good” when I’m running the icosphere. They could be changed or tailored based on need.

It should also be noted that for PISES, these thresholds will need to be dynamically generated for planets of varying radius. That, or all planets can be transposed to 1 Earth-Radius for the sake of their icospherical exploration (this has some consequences, more on that later). In this example, these constants are based on an icosphere being used for an Earth-model, for a different project. In any case, whether they are statically determined or dynamically produced, we need a set of thresholds.

Depth Tracking

In our Update() method, we will need to continuously track the recursive depth of the observer.

Note that “scale” here has been set to EARTH_RADIUS_KM in the Awake() method.

Now that we know the observer’s depth, we can check to make sure that all observed Triangles are of the correct depth. If they’re not, we will call a new method on AbstractIcosphere : “recurseSingleFaceAndDescendants().”

If you are wondering how the Observation Group was determined, please refer to the post, “Detecting the Observation Region: The Coupled Ring Adjacency Search.”

Recursion of a Single Face and Descendants

Now that we know exactly which triangles need to be recursed, and by how much, we can get into the technical grit of breaking down the faces of our icosphere. This process we have actually already covered, in the post: Recursion of the Icosphere and Maintaining Adjacency.” There are just two differences now:

  1. This time, we have an entire Observation Group to recurse.
  2. With the interest of being able to repack this icosphere, we now need to perform some checks before recursing to make sure that there aren’t already descendants. This could be possible if we start at recursive depth A, descend to depth B, triggering descendants, retreat to depth A, packing up those descendants, and then descending once again to depth B. If we don’t check for the presence of descendants, we could create duplicate Triangles and all hell would break loose.

With this being said, here is our updated “recurseSingleFace()” method, and its recursive caller, “recurseSingleFaceAndDescendants().

At this point, we can descend the icosphere, recursing triangles as we go. Now, we need to be able to get back out and repack triangles in our wake.

Ascending the Icosphere

As it turns out, we have already done pretty much all of the work we need in order to cleanly ascend and repack the icosphere. All of our triangles have knowledge of their parents and descendants – and all of our triangles have a ‘visible’ flag, meaning we can simply switch them on and off. When it’s time to constitute our mesh for Unity, we can harvest only the visible triangles and neglect the invisible ones – they’ll remain in the Abstract Icosphere, simply not rendered.

First, we check for an ascension event.

Second, we scan all triangles in the icosphere for those that are below the current recursive depth. The reason we must scan the entire icosphere is because we may have triggered a recursion event in one region, and then panned to another, while remaining at the same depth, such that the first triangles we recursed are no longer in the observation group, but still need to be packed up on ascent.

A way to streamline this in the future would be to immediately repack anything not inside the observation region – but this has some complicated folds, and we’ll save it for another time.

For now, we scan the icosphere for triangles below the observer’s depth. We set them, and their adjacencies of matching depth, to invisible.

Then, we climb up the quad tree to find their parent triangle at the target depth. We set this to visible.

Updating the Mesh

Last, we must update the physical mesh in unity. Throughout this entire process, you will notice that for recursion or ascension events, we have been toggling a flag, ‘updateMesh.’ It simply activates this block at the end of the update() method:

The methods “HarvestMeshData()” and “CreateMesh()” are explained in detail in the post, “Rendering the Static Icosphere in Unity Gaming Engine.”

Video Demonstration

See the repacking icosphere in realtime action at the link below.

3 thoughts on “Recursing and Repacking the Observation Region

  1. How many triangles do you actually use? The same as in the video, or many more than that? I always thought that with modern GPUs it was generally more efficient to just draw a million triangles rather than have to iterate over individual triangles on the CPU to determine what to draw. That’s why LOD alogrithms such as ROAM have been replaced with things like clipmaps and brute force rendering. Or are you really rendering patches of triangles? Maybe that would be a good trade-off.

    Like

    1. This is a little tough to answer, partly because I’m not sure what you’re asking. I’m sure you’re right that it’s much more efficient to make use of the GPU to generate hundreds of thousands of triangles. It may also be that 1. UGE is already offloading work to the GPU (I’m not sure!), or that 2. I could optimize this process by manually dispatching tasks to the GPU (I don’t know how to do that in UGE yet or if UGE even exposes that ability).

      To answer your other question, in the realm of PISES, yes – I am only rendering “patches of triangles.” The triangles below the base recursive layer do not exist until they are generated. So, zooming in on one region, we generate a “patch” of finer triangles, only in that single region. There are many reasons I want to run with this concept, outside the scope of this thread.

      I guess I’m not really sure what you’re suggesting I do with my GPU, aside from just being smart and allocating rendering tasks to it. As things stand now, I get a fully performant icosphere doing exactly what I want it to do at a smooth 40-60 fps. Are you suggesting that if I ran this on the GPU, I could simply have the finest-grain icosphere outright, without the need for all this decomposition and recomposition?

      Like

      1. I’m not sure exactly how your system works. I guess you know that better than I do! I was thinking that maybe you can manage the higher level groups of triangles on the CPU, and then manage the lower level of actual triangles on the GPU somehow. That’s often how advanced games do it, but you may not need that level of performance (or that many triangles). Or maybe it actually does work that way now. I don’t use Unity, so I can’t tell how it’s implemented or what you can actually do with the engine.

        But anyway, great project! You definitely have some interesting and unique content in your posts, even though I don’t understand all of 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