Hello!
I’m trying to make a poor’s man version of no man’s sky basically. I especially want similar terrain where I can go from space to surface seamlessly, but maybe less technically perfect.
My technical goal is planet up to roughly bigger than the diameter of earth (14k vs 12k), with tile resolution of 2m for the terrain, I used region of 6x6 km as an overall planet metric (aka 2600 regions of diameter for the biggest) and size are in increment of region.
The way I approach this is:
1 - I use the axis aligned cubic sphere,
2 - I find the planet to ship vector,
3 - I clamp this vector to the radius, to find the hovered surface point
4 - Using this point I detect which face of the cube it land on
5 - Using this point I want to find the “tile’s hashed coordinate”
6 - Using the tile’s hash, I want to build terrain LOD around that coordinate
7 - Technically I planned to use a circular array to allow for fast travel and generation of terrain, so having a fixed footprint of chunk is key I think.
My problem is the 5th point, I can’t seem to resolve that in a satisfying way, It’s basically the reverse of projecting the cube onto a sphere (ie projecting a sphere point into the cube).
The twist is that I use a “corrected projection of a cube on sphere” to generate the planet, it’s not the typical normalized coordinate. This is an important feature because it allows gameplay metric to be conserved!
Seen here: Cube Sphere, a Unity C# Tutorial
Does anyone has an idea or alternative to accomplish the same goal?
Note: Since 2017.3 you can use 32 bit meshes!
In what way does a circular array help here? What if you need more or less chunks beeing generated? Do you use a LOD system so creating chunks in different resolutions? Do you use an Octree or something similar?
In the worst case you could just brute force it and check the landing point against the centers of all chunks and find the closest. Since this seem to happen only once (when attempting to land) it should not really matter when you use squared distance and drop out once you find it. And you could also check which face of the cube the point lies on and only check chunks on this side.
The problem is, the landing point will never be exactly at the center of a chunk wich you seem to use as an hashed index. But I think calculating this is pretty hard because of the distortions of the projection. A sphere based on an Icosaeder should be regular. But again when this happens so rarely that I don’t think its worth all the time and effort. Just use the simplest approach. Or pay Jasper (Catlike coding) to do it ;).
I wish I had money to pay people, but I already try brute force and it’s brutal impractical it’s O(n²). Just the area on a big planet is 6 760 000 checks per faces, and we haven’t started the inner area which is 18 000 000, and we need to update every time there is movement (24 760 000 checks), a spaceship can travel pretty fast! While the ship only hover a single face at a time, we might need to calculate up to 3 faces when close to edges and corner to ensure continuity. If I could do it with less it will be a big plus because there is a lot of data to generate as fast as possible. Especially on mobile (I have entry level L-element 505 mobile with mali 400).
With just an axis aligned flat plane, spatial hashing is trivial, it’s just a matter of applying mod to position. But on a sphere I haven’t figure out a way to easily bucket position according to the mapping. I don’t generate the whole planet, just a regular LOD terrain but on a planet, the rest of the planet is just an analytical sphere with some placeholder visual.
I use a cube sphere because the cube mapping is friendly to generation and gameplay metric, all my procedural routine use local techniques tested on a grid, and it’s easy to understood and plan ahead, and other mapping introduce a lot of complication that mess up generation and gameplay.
For the circular array, I used a 3d array that is looped around in 2d, it hold the generated noise at different frequency along the depth. The data is then mix down on a per LOD chunks, far away LOD only use low frequency but the close one add up the higher frequency. Circular array allow the noise to be generated in small increment along the direction of movement, with high frequency being update more frequently and lower frequency less, it keep the memory consistent with a fixed footprint. All chunk have the same vertex count, only the height is updated and old chunk get recycled, close chunk are just smaller to represent denser data, because density scale down with size, the amount of data stay the same for low frequency and high frequency. It’s a technique used with voxel type of word to accelerate the generation, I used to trade data density for speed of generation (2d vs 3d noise). Also access is O(1) unlike octree which also introduce incoherent access, and it’s much simpler overall than maintaining a tree.
Just an extra:
I would have to generate the point grid on the surface before, since the planet only exist analytically, so the cost of creating all the point (then discarding them) is where the actual computational power is spend.
Maybe I did understand you wrong. From your first post:
So to me it sounds this is a single operation done infrequently. Why O(n²)? What I meant is you iterate over all chunks of your planet, calculate the squared distance to the “hovered surface point”, pick the one with the lowest distance and you have the chunk the ship will land on. This should be an O(n) operation.
The description in your second post confuses me. What do you mean with “inner area”? I thought the circular array is for storing the chunks not for the noise. What do you mean with analytical sphere? From what you write I can’t get an imagination of how your planet generation actually works. Maybe you want to elaborate a bit more in detail what happens when and how is the actual structure of the data representing the planet.
Keep in mind that procedural planet generation is a pretty complicated topic. So its likely there are no easy answers/solutions to complicated questions/issues.
Chunks are created around the player position AFTER it’s been hashed. Creating the PRIOR chunks position for the whole planet is the O(n²) cost, which is simply the number of chunks created for one planet cubic face. That mean there is no chunk to iterate from, they are generated AFTER the hash.
The chunk is basically a fixed mesh, with noise being used as height, so the y component is basically equivalent to the noise, since the mesh itself don’t change and only y, the array hold the data to update.
Analytical mean it’s not represented by mesh or chunk, it’s just the mathematical definition (radius). Ie there is no visual planet until the chunk are generated, or to be more correct, the visual planet is just a 2d circle defined by the math, it’s only when you get close than the actual 3d terrains is represented.
It might sound complicated, but all those extra data is not important, what’s important is the spatial hash, because everything else is rather trivial.
The problem is quite clear:
Given a point on a cubic sphere’s face, how to calculate the spatial hash (tile, chunk, whatever the name of) for a given projection!
Found something here: PETROCKET: Sphere to Cube Mapping
but it’s off:
public static Vector3 cubify( Vector3 s)
{
float xx2 = s.x * s.x * 2.0f;
float yy2 = s.y * s.y * 2.0f;
Vector2 v = new Vector2(xx2 - yy2, yy2 - xx2);
float ii = v.y - 3.0f;
ii *= ii;
float isqrt = -Mathf.Sqrt(ii - 12.0f * xx2) + 3.0f;
v = new Vector2( Mathf.Sqrt( v.x + isqrt), Mathf.Sqrt( v.y + isqrt) );
v *= isqrt2;
return new Vector3(
Mathf.Sign(s.x) * v.x,
Mathf.Sign(s.y) * v.y,
Mathf.Sign(s.z) * 1.0f);
}
public static Vector3 sphere2cube( Vector3 sphere)
{
Vector3 f = new Vector3 (
Mathf.Abs(sphere.x),
Mathf.Abs(sphere.y),
Mathf.Abs(sphere.z));
bool a = f.y >= f.x && f.y >= f.z;
bool b = f.x >= f.z;
Vector3 result;
if (a)
{
result = cubify( new Vector3(sphere.x,sphere.z,sphere.y));
result = new Vector3(result.x,result.z,result.y);
}
else if (b)
{
result = cubify( new Vector3(sphere.y,sphere.z,sphere.x));
result = new Vector3(result.z,result.x,result.y);
}
else
{
result = cubify(sphere);
}
return result;
}
The problem is located here:
v = new Vector2( Mathf.Sqrt( v.x + isqrt), Mathf.Sqrt( v.y + isqrt) );//v corruption
It produce some NaN data …line 13 of above post
Correction!
v = new Vector2(
Mathf.Sqrt(Mathf.Abs( v.x + isqrt) ),
Mathf.Sqrt(Mathf.Abs( v.y + isqrt) ));//v corruption
