The Icospherical World Model: Problem Specification and Preliminary Data Structure

Problem Specification

PISES currently contains worlds and planetary systems which are completely abstract and without geometry. Worlds at the moment can only be interacted with by rifling through thousands of lines of log output, a task which I often relegate to scripts.

Ultimately, we would like for worlds in PISES to be tactile and visual. We want worlds with geometry, that can be spun about like a globe, panned across, zoomed in upon.

Additionally, we want worlds with scaling detail. Creating a static globe, unable to expand or collapse in detail, would be a very flat experience. A user must be able to zoom in to a region of the globe and expose new detail which was invisible from orbit. Additionally, we wish to only scale the singular, isolated region of the globe that is directly under observation: not the globe in its entirety, which would be a waste of time and memory.

Moreover, when the user leaves this region, the region must be packed away (but remembered). What we are talking about, any gaming enthusiast will have already realized, is a procedural environment: a globe that scales and de-scales with the user as they proceed through its environment.

Geodesic and icospherical world models are not limited to gaming in their application however. There are countless digital world-models developed and employed by private enterprise, government and military organizations, and the scientific community.

Where our goal becomes slightly more unique is in the asymmetrical nature of our icospherical world model. We wish to procedurally develop asymmetrical regions of our world-model, which did not previously exist (they are not loaded from a standing database). Another mandatory feature of our icospherical world model is that each icospherical face of our world model must have adjacency data on its neighboring faces. This will become very important later, when we task ourselves with synthesizing geometrical maps from the abstract planetary data we already have.

In essence, our icospherical world model must meet the following criteria:

  • Scale downward in fractal detail with the user’s proximity
  • Scale upward as the user moves away
  • Scale asymmetrically, only in the region of observation
  • Maintain adjacency knowledge among its various triangular faces

What is an Icosphere?

An icosphere is a type of geodesic polyhedron which is derived from an icosahedron. An Icosphere is generated by subdividing each face of the preliminary icosahedron into four equilateral triangles and then projecting these newly generated vertices outward to the unit sphere. The following image demonstrates this concept.

This process can be repeated, recursively, any number of times in order to create an icosphere of recursive depth N.

The Preliminary Data Structure

An Icosphere can be thought of as consisting of some number of triangular faces. Let us name this class “Triangle.” Each triangular face must, at a minimum, consist of three vertices, which can be represented by Vector3s: v1, v2 and v3.

The Preliminary Triangle, defined by its Vertices.

With this data alone, we can articulate the polyhedral representation of an icosphere. However, we have specified that each triangular face of our icosphere must maintain adjacency data of its neighbors. Therefore, in addition to three vertices, each Triangle must reference three other Triangles; adjacency 1, adjacency 2, and adjacency 3.

It is not enough to simply declare vertices and adjacencies. These adjacencies must be directional adjacencies. Otherwise, when referencing a Triangle, how would we know the orientation of adjacency1 and adjacency2?

Therefore we must establish some rules for adjacencies. We can declare that

  • adjacency1 is always the adjacency which lies between v1 and v2;
  • adjacency2 is always the adjacency which lies between v2 and v3;
  • adjacency3 is always the adjacency which lies between v3 and v1.
The Triangle and its Ordered Adjacencies.

Moreover, if we are to recurse a Triangle into four sub-triangles in order to create a more dense icosphere, Triangle must have knowledge of its four sub-triangles – its Descendants. Like Triangle‘s adjacencies, its descendants will simply be pointers to other Triangle instances. Let us say that a Triangle has four descendants: descendant1, descendant2, descendant3 and descendant4.

The existence of descendant triangles reveals the need for Parent triangles. Every Triangle will therefore have four descendant references and a singular Parent reference. Additionally, our triangles will now need to be equipped with a boolean flag: visible. This is because once we recurse a Triangle, creating four descendants, the original triangle should no longer be visible; if it were, it would simply be obscured by its four descendants anyways.

This raises the important question: why retain knowledge of parent triangles, especially if they are going to become invisible?

The answer to this question will become explicit later in our development of the icospherical world model, but there are two short answers:

  1. A new descendant has no knowledge, geometrically, of what triangles are adjacent to it. In order to discover its adjacencies, it will have to “climb” the ancestry tree to its parent Triangle and survey its Parent’s adjacencies for “co-descendants” who might be adjacent to it.
  2. As the user pulls away from a heavily recursed region, we will want to “pack up” our descendants and re-expose their ancestors.

The existence of descendants also reveals the need for them to be situated in a reliable order, much like adjacencies. This will allow us to always, upon recursing a Triangle, have some starting adjacency knowledge.

Descendants are generated by bisecting the triangle between v1 and v2, creating a midpoint a, bisecting the triangle between v2 and v3, creating a midpoint b, and bisecting the triangle between v3 and v1, creating a midpoint c. Let us establish the following positional rules, then, for our descendants:

  • Descendant 1 is always defined by its parent’s first vertex, a, and c.
  • Descendant 2 is always defined by a, its parent’s second vertex, and b.
  • Descendant 3 is always defined by c, b, and its parents third vertex.
  • Descendant 4 is always defined by b, c, and a.

The order of the vertices is important, as it drives the adjacency data for the descendants. This particular problem we will discuss in explicit detail later in our development.

Lastly, every Triangle will require a unique identifying index.

The Triangle and its ordered Descendants.

With this, we have built up our Icosphere’s basic data structure: the icosphere itself will simply consist of a Dictionary (or Map (choose your language)) of uniqueIndex : Triangle.

From here, we can advance to the next step: the construction of a preliminary Icosahedron with the recursive depth zero.

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