Hi everyone,
long time no planetary terrain update in one of the best I-Novae threads :-). I am currenty revisiting planetary bodies using cubespheres and quadtrees, and thought I might revive this thread for some new “best strategies” or “common approaches”. While currently re-implementing (in current Unity3D 2019 version) I want consider hints in some previous comments in this thread, but already noticed they raise some questions.
Idea is to aks for critics, hints, corrections, different approaches.
Lets lets try to structure the topc into quadtrees, terrain-plane pipeline and maybe some CPU vs GPU discussion.
QuadTree Structure
- Each quadtree deals with one plane of the non-normalized cube.
- Each cubesphere has six independend quadtrees. Each quadtree manages one side of the cube.
- A rendered plane (=its vertice data etc) is available (only) in the leafnodes of the quadtree. Once we split a node, we destroy its current plane data (including vertices) and calculate the new plane data in realtime in the 4 childsnodes (leafs).
- We traverse each of the 4 quadtree recursively completely and check if we have to split or merge quadtree nodes based our LOD strategies.
- The very basic components of a quadtree node are:
public interface IQuadTreeNode
{
// QuadTree
string UUID { get; }
IQuadTreeNode Parent { get; set; }
IQuadTreeNode Child1 { get; set; }
IQuadTreeNode Child2 { get; set; }
IQuadTreeNode Child3 { get; set; }
IQuadTreeNode Child4 { get; set; }
bool isLeaf { get; set; }
int Level { get; set; }
// Functions
void Split();
void Merge();
void Expand(int level);
int NumberOfLeafs();
IQuadTreeNode[] Leafs();
}
Additional to the “core” elements we store the very basic information about a plane in the node.
{
// QuadTree
string UUID { get; }
IQuadTreeNode Parent { get; set; }
IQuadTreeNode Child1 { get; set; }
IQuadTreeNode Child2 { get; set; }
IQuadTreeNode Child3 { get; set; }
IQuadTreeNode Child4 { get; set; }
bool isLeaf { get; set; }
int Level { get; set; }
// Plane
Vector3 OuterVector1 { get; set; }
Vector3 OuterVector2 { get; set; }
Vector3 OuterVector3 { get; set; }
Vector3 OuterVector4 { get; set; }
Vector3 CenterVector { get; }
float Width { get; }
float Azimuth { get; set; }
float Elevaltion { get; set; }
// <- Custom member that stores the vertice/triangle/… data
// Functions
void Split();
void Merge();
void Expand(int level);
int NumberOfLeafs();
IQuadTreeNode[] Leafs();
}
“OuterVector1-4” store the non-normalized outer edges of a plane/node within [-1|+1] range. Each vector (or vertice) lies on one of the planes of the non-normalized cube within its [-1|+1]. Normalization and radius are not involved yet.
“CenterVector” is the center of the plane. It is not stored but calculated on demand using OuterVector1 and OuterVector3.
“Width” is the distance between two OuterVectors which together connected make the edge of the plane, not the diameter. E.g. OuterVector1 and OuterVector2. Its also calculated, not stored.
“Azimuth” and “Elevation” are the rotations required to rotate the (normalized) plane so that its (normalized) CenterVector now lies on Y-up. Although these values could also be calculated on demand we store them once at creation of the quadtree node due to the computations required.
All further values, e.g. OuterVector1-4 values normalized or multiplied by the sphere’s radius can be derived. However it depends on the caching/implementation strategy if these additional values (normalized ones, final worldspace position) should be stored as well in the node or calculated on demand.
Plane Pipeline
In general when creatig a cubesphere we multiply all cube’s vertices on its surface in [-1|+1] value range by normalizing them first and then multiply them by the desired radius. Additional noise can either be added after normalization or after multiplying by the radius.
1.1 Cube plane in [-1|+1]
1.2 Normalize all vertices
1.3 Multiply vertices by radius
1.4 Multiply vertices with +/-noise value for terrain
or
2.1 Cube plane in [-1|+1]
2.2 Normalize all vertices
2.3 Multiply vertices with +/-noise value for terrain
2.4 Multiply vertices by radius
Approach 1.x might be prefered as chance is lower we get into precision issues and working with height information in the right radius scale might feel more intuitive.
But:
I am torn what an overall best strategie is. Maybe this also depends on the question if you are going to calculate your plane vertices on the CPU or GPU (and if on the GPU, how you use it to render the result).
GPU)
A previous approach here was to calculate the vertice worldspace position on the GPU using a compute shader. The calculations result remained on the GPUs memory and rendering these positions happended in the shader. In that case we needed vertices being prepared on the CPU only as “container” till that moment when they shall be rendered (and then displaced by the shader using the GPU data). In that case all planes can initially and throughout all planes consequently be created in e.g. Y-up. for all vertice data, as final positions are defined individually by GPU data.
CPU)
In this scenario you need, at some point, your vertices to be at their final worldspace position, including rotation and normalization of the plane and all vertices in the desired world radius.
This leads to the question if you really want to create your plane vertices initially in the Y-Up direction (and centered at e.g. 0,1,0) when you “know” that during the planepipeline process you have to rotate your plane (or all vertices) to one of the directions of the cube’s faces, center them to the node’s CenterVector, then normalize, apply radius and apply noise.
The process would read:
1.1.1 Create plane in Y-Up (centered at 0,1,0) (in already correct width so that it fits with depth of node)
1.1.2 Rotate planes/vertices to face into the same direction as the quadtrees centervector normal.
1.1.3 Center the plane to the CenterVector
1.2 Normalize all vertices
1.3 Multiply vertices by radius
1.4 Multiply vertices with +/-noise value for terrain
1.5 Calculate Elevation & Azimuth and store it for later use.
So we apply the normalization and terrain noise after the plane has reached its “desired” position on the cube (non-normalized) by using rotation and such
So the question is, why do we want to create the plane data in Y-up at (0,1,0) instead of simply creating the vertice positions directly in the right rotation and centered at centervector on the cubesphere’s [-1|+1] surface during initial creation of plane?
One argument would be that that at some point you want the plane in Y-up for AABB collision tests (e.g. for NavyFish’s LODSphere strategy). However Azimuth and Elevation can still be calculated by using just CenterVector.normalized. Am I overseeing something?
CPU vs GPU
As we desperately need some of the plane data on the CPU for LODing (at very least the bounds of the plane that holds the plane at its world position (including normalization, radius and noise) I feel I want this time to stick to CPU creation of the plane when it comes to vertice data. Knowing that calculating these planes take longer, my feeling is that having a good LOD in place with threaded CPU based plane creation might be more important. Terrain data taking longer to load worries me less than FPS spikes due to asynch readback of CPU data or non-sufficient LOD in place for very depth quadtree situation where the observer is close to the terrain surface. And I would like to to test how far I can push details down when using CPU’s double precision through most of the process to create the plane, as this up to now payed out a lot when re-implementing Unity stuff with hardly and performance impact (double vs. float on CPU).
So, how about the GPU? Creating material textures is obvious. But, I wonder if some clever approach could be found to use the GPU for more detail none the less.
I have to questions in my head and would wonder about your thoughts.
- Do you know how likely it is to achive some identical noise implementations both on the CPU and GPU so that based on same parameters they deliver identical results? I know it feels odd to create the vertice position on the GPU and do the same to get to the normal map (which you want for higher details) on the GPU.
- I wonder if there is a good way to use the GPU to interpolate rawer CPU data for finer details. So you provide the result of the CPU calculations (e.g. a plane in 12x12 resolution) to calculate the details between them. I am currently stuck at thinking you will need again to achive identical noise implementations because otherwise, even though it wouldnt be a problem to create details once, you would notice terrain changes when splitting vertices where GPU results wouldnt reflect CPU vertice positions when creating them for the next quadtree depth.
But maybe you have some ideas or thoughts about this?
Looking forward to anyones comment or thought.
PS: Hope everyone is healthy and fine!!
, but the performance involved some work :-).
