14
\$\begingroup\$

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.

square chunks method

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.

icosahedron method

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.

\$\endgroup\$
  • \$\begingroup\$ Before I start writing, is your world a sphere? Are you trying to impose a grid on a sphere where each grid has properties saved to a file? \$\endgroup\$ – Alec Teal Sep 22 '15 at 10:15
  • \$\begingroup\$ @AlecTeal I'm trying to simulate a planet. So it is globally a sphere. And the main problem is that the player can try to ground on any point, on a pole or along equator. \$\endgroup\$ – Aracthor Sep 22 '15 at 11:43
  • 2
    \$\begingroup\$ So.... gotta ask did you search for "spherical world game engine" as there are loads of implementations there. Why don't they work? Additionally this is why we have cube maps, they're the standard charts on any topological manifold homeomorphic to a sphere for this reason! \$\endgroup\$ – Alec Teal Sep 22 '15 at 11:54
  • 1
    \$\begingroup\$ suggest to evaluate also quad sphere option \$\endgroup\$ – dnk drone.vs.drones Sep 22 '15 at 12:54
  • \$\begingroup\$ maths.kisogo.com/index.php?title=Notes:Spherical_coordinates preliminary draft. Needs pictures and to be finished off. \$\endgroup\$ – Alec Teal Sep 23 '15 at 11:41
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ @Alec_Teal I'm on your answer since you posted it, complex and hard to understand (I'm not used of so much maths formulas) but I think I have to understand... Is your method really different from a cube-based sphere as described above? I didn't understand if your "charts" are square projections or something more... \$\endgroup\$ – Aracthor Sep 24 '15 at 13:53
  • \$\begingroup\$ @Aracthor it's more general. A chart is literally like a chart in a book (of maps) all it does is impose a grid on some area. Say you had a torus for example, or a 2 holed torus, you'd need these methods. None of the answers here deal with coordinates on a sphere as much as regular ways to create the geometry, which is a different task. I can help with the formulas, I've tried to write it as accessible as possible, but this is my bread and butter, so I don't see the complexity. \$\endgroup\$ – Alec Teal Sep 24 '15 at 16:59
  • \$\begingroup\$ @Alec_Teal I validated it, but I still don't think I got everything. But let's continue this discussion in a chat room. \$\endgroup\$ – Aracthor Sep 28 '15 at 3:39
12
\$\begingroup\$

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)

Sphere subdivided based on a cube

(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.

Varying the mapping function to improve uniformity

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:

Flattening geodesic tessellations onto a regular triangular grid Net of an icosahedron on a triangular grid

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

Triangular-square grid isomorphism

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:

Unwrapping a geosphere into rectangular charts

(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.

\$\endgroup\$
  • 1
    \$\begingroup\$ There's some good stuff here. I would +1 but I plan to write an answer later (I try to stay out of the early phases of voting when I also answer). My only comments would be that this approach is better for rendering spheres than modeling the surface \$\endgroup\$ – Alec Teal Sep 22 '15 at 14:16
  • \$\begingroup\$ Just incase you are curious, I have now finished my answer. \$\endgroup\$ – Alec Teal Sep 23 '15 at 19:11
3
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This circumvents the problem by opening up the option to not design the explorable planet surface as a sphere, but doesn't solve it. \$\endgroup\$ – Philipp Sep 23 '15 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.