How to load a spherical planet and its regions?

Question

I'm designing a game partially composed of planets exploration. I want to use pseudo-random generation for them, regenerating from a defined seed when I have to load them rather than store every detail, which would be too heavy. So I will just store in a file the random seed and modifications done by the player if any.

The player must be able to see the planet from orbit (with very low level of details, then go down to the ground, increasing slowly the level of details of the region where he/she is landing, and unloading the ones on the other sides of the planet, which go outside the player's field of view.

If I had to do it on a plane ground, I would do it easily with a square chunk system. But the problem here is that planets are - almost - spheres.

So what would be the best way to load ground details (relief and grounded objects) around a precise point ?
I already though on two solutions, but both have a weak point:

1. Cutting the sphere in square chunks.

Once the player is close enough of the ground, I just have to improve details of closest squares from his/her position.
If it is not enough, I still can cut each square in sub-squares to load when the players is on or really close of the ground.

But as you can see on the picture, there is a problem if the player try to land on a pole: squares become very slim rectangles, or even triangles for the last line, and additionally to the fact that they would be many to load, generation would appear distorted.

2. Starting from an icosahedron.

Here, I could just increase triangle tessellation around player's position when he/she is getting close.

But I don't know how to locate triangles close than player's position. I heard Cartesian coordinates could be usefull in that case, but I don't know how to use them.

---

I'm using C++/OpenGL for it, so the main thing to generate and load here are vertices representing the surface relief and color/texture.

Answer 1

Okay, so I wrote it out here:

http://www.maths.kisogo.com/index.php?title=Notes:Spherical_coordinates

(I needed the math-markup and also it's really quite long)

---

Applying the document

The document starts by introducing the notion of a manifold, a manifold is this thing where chunks of it are "homeomorphic" (basically: the same as) chunks of R^n (R^2 is the x/y plane, as you might know)

A chart covers some (possibly all, although in the case of a sphere it CANNOT cover all) of a manifold.

In the article I develop 4 charts for the sphere that preserve angles, that is they keep regular distance.

As you've found out giving coordinates to points on a sphere is actually quite difficult! What we do instead (although on a circle in the example) is give each point a coordinate of the form (i,x,y) where i is a number between 1 and 6 for a sphere, 1 and 4 for a circle. This is the chart number.

The x and y refer to the angles on that chart (or just x if it's a circle).

The 6 charts of a sphere are the top/bottom hemispheres, left/right and front/back hemispheres.

---

Coordinates

Now you can give evey point a "nice" coordinate that is well behaved. In mathematical terms the domains of the charts are "open" maps, this means there exists some positive number such that a ball around each point is also in the set. For example the range (0,1) (the set that contains x if 0< x<1) is open, take any p in (0,1) (for example 0.001) then there is a number (for example 0.0005) such that any point within 0.0005 of 0.001 is also in (0,1).

What this means is you can pass directions through charts.

Now there is 45 degrees of overlap in the charts we develop. This means if you have a feature at coordinates (i,x,y) you can SAFELY specify points of the form (i,x+a,y+b) as long as a and b are between -45 and +45 (in degrees)

Any point of the form (i,x+a,y+b) can be easily transformed to a point in "normal" 3-dimensional space without problem.

---

Implementation

You now have a way to store coordinates for something on a sphere, and denote regions large swaths of space with these coordinates, they also behave like coordinates, they're open for example (which is a problem if you use 2 angles instead)

You can also totally discard "how to create a regular sphere" answers now because all you have to do is do 6 planes, and make sure the edges of them align (which is trivial) and the result is:

You'll have a nice sphere with easy to use coordinates

Any questions please comment, I've tried to assume little prior knowledge. I'm also new to teaching people

Answer 2

As you've already shown, there are a number of solutions to this problem, but none 100% ideal. Spheres are tricky.

Cube-based

One common route, used by Spore and quite likely other games (though it's hard to tell for certain without peeking under the hood), is to project the sphere onto a cube, and use a square grid over each cube face.

(This is what Alec Teal and dnk drone.vs.drones are describing in the comments above)

(Image from this post which describes using a cubic representation for LoD)

This has a lot of the advantages of the latitude-longitude method, with much less peak distortion. It's easy to convert back-and-forth between positions on the face grid and positions on the sphere, by either normalizing a vector or dividing by its greatest component in absolute value. It also aligns nicely with cube mapping texturing techniques, which can be useful when viewing the whole planet from a distance.

The typical mapping approach is called gnomonic projection, and it still has a density mismatch problem as you can see in the image above. The grid is much more dense near the cube corners than at the centers of the faces. If uniformity is important, you can reduce this with the right mapping formulae, but this usually makes the mapping harder to reverse.

In all cases, you'll still have an angular distortion at the corners, where an ordinary grid intersection of four squares with 90-degree angles becomes a meeting of 3 rhombuses with 120-degree angles.

Icosahedron-based

My personal favourite aproach would be the icosahedral version that you described, because it makes the peak angular distortion as small as possible. Where the triangular grid would ordinarily have six triangles meeting at 60-degree angles, the icosahedron vertices have 5 triangles meeting at 72-degree angles. So each one has less distortion than the squares in the cube example.

It's not quite as familiar territory as the squares of the cube version, which is probably why it's not as popular. It takes a bit more math to work through.

Identifying nearby points isn't quite as tricky as it might appear though. Any icosahedron-based geodesic sphere can be flattened onto a regular triangular grid:

And a regular triangular grid can be treated like a square grid, as discussed here.

So once you determine which face of the icosahedron you're on (which can be done with a raycast against an icosahedral mesh - I don't know of any clever mathematical way to simplify that part), the surroundings can be filled in using familiar grid traversal. :)

Edit:

If you use a Class-I geodesic, you can unwrap your planets into five rectangular charts for storing level chunks/textures/heightmaps efficiently, similar to the six square charts you'd use for storing a cube-based version:

(This may help address the concern raised by Fuzzy Logic in another answer. This is also possible but a little more complicated for Class-II geodesics. I haven't investigated Class-III)

The trick is that the axes of these charts aren't really perpendicular in use, so existing authoring and streaming tools/tech won't support it out of the box. If you're planning on writing your own chunk streaming anyway or using on-the-fly procedural generation then that might not be an issue. You might also be able to work around the authoring problem by generating your source maps in higher resolution than you need using more conventional tools, then running them through a baking process that samples along the chart grid to build a dense, efficient representation that plugs directly into the icosahedral structure.

Answer 3

Quad-sphere with chunked LOD is the preferred method if you want to be able to go from space to ground with any level of detailed terrain, either procedural or predefined heightmapping and textures.

Icosasphere provides a more uniform mesh and is easy to tessellate but poses problems trying to map textures and heightmaps which you will need to cache and won't be very compact or simple that way.

Quad-sphere has pinch points but with enough tessellation you won't see them anyhow. Then you can map textures and implement DLOD effectively as if each region (chunk) is a square grid with little problem. This is simpler to implement compared to an icosasphere and will be more efficient, both in computation and resources.

See Sean O'Neil's articles about generating a procedural universe on Gamasutra:
- Part 1 Perlin Noise and Fractal Brownian Motion for heightmaps and textures.
- Part 2 ROAM Algorithm for procedural mesh with DLOD for planet generation. Suffers from performance problems. Not recommended but good for educational value.
- Part 3 Addresses problems with massive scale, optimization and floating point issues. Mainly related to universe scale but also applicable for planets when transitioning from scales of light years to centimetres if you want.
- Part 4 Discusses implementation of Quad-sphere with chunked (quad-tree) DLOD for planet generation <-- see this article in particular

Answer 4

I'm no expert on programming, but you could have some sort of checkpoint. While you are cleared through a security checkpoint, with animation of course, the surface of the planet can load, and vice versa.