next »

[gimymblert]

Hello!

SO I have been working on a planetary terrain system for planet scale. My requirement is to have something compatible with strict gameplay metric. While it's not 100% possible to maintain metric around pole and edge due to mathematical reason and inflated cube (let's call it a geospshere) with adjustment of distortion is enough. Which is something I have already done.

Right now I'm going for a minimum cube face of 36km² (2x3x6) aka the macro tile, with the smallest metric unit being tile of 2m². Planet size are in macro tile increment, max size is arbitrarily 400 macro tile (roughly a bit bigger than earth).

Instead of going the usual Quadtree (don't seem to a allow for arbitrary size that aren't multiple of 2) I just want to use terrain as in usual, ie concentric LOD around the objects and below it's position. That is fixed foot print whatever the size of the planet (it only matter when you are close enough to ground  from the atmosphere). The idea is to have a circular array of terrain data to promote fast travel and quick generation (recycling mesh in a pool by only updating the heightmap, each lod use similar mesh, just bigger). There is LOD array that contain all the generated data for one level of details, they all have the same size but encode different frequency of data to be combine in generating the mesh heightmap, with low frequency being updated much faster that the low frequency (due to size to traverse).

The problem is that it seems trivial in the case of perfectly flat terrain ... I have trouble when it comes close to edge and corner of the geosphere. Basically how do I query the next neighbour across the seams, how to make sure the edge data are shared by the recursive tile,  and what are the best suggested data structure to hold that in a simple way?

The goal is to generate circulation (path, road, river) that flow across tile using local generation through correlation.

[BorisTheBrave]

You can use quadtrees on non powers of two. Just round up, and null out branches you don't need. While that sounds wasteful, the quad tree will only be max one branch deeper than something more optimal, which is fine.

---

In terms of edge data, as you know, the easiest way to store edge data for a planar tiling is to store the top and left edges of each tile with the tile. If you want to know the bottom or right edges, you move one tile down or right, then ask what their top/left edge is.

Turns out, you can do the same thing for a cube. There's 12 edges on a cube, and 6 faces, and if you pick the right rotations for each face, then each tile can have a "top" edge and a "left" edge, and you cover all all edges exactly once that way.

That extends very naturally to a tiled cube. Ultimately, every tile sees 4 tiles as neighbours, so you can locally treat it like a grid. But when a neighbour tile happens to be in another cube face, then there is a rotation in local co-ordinates when crossing the boundary.


----

Though I've not done exactly this, when writing these systems, I like to abstract the geometry into a library, so I don't have to think about it elsewhere. You have a class like TileLocationWithDirection, and then have methods Forward, Rotate90, etc. Then you need two dictionary like objects for storing per-location and per-edge information, which are keyed by TileLocation[WithDirection]. If you are working with levels of detail, then the same thing applies, but you have TilLocationWithDirectionAndLevel, and extra operations GetParent / GetChildren.

It's not a perfect abstraction, but you can get pretty far with it without having to worry about special cases.

[gimymblert]

I'm going to prototype it, thanks.