Friday, 17 April 2009

Terrain 2

The algorithm I will implement is based on a restrictive quad tree approach. All this means is that for each node in the tree, each of its directly adjacent neighbours will need to be only one LOD level different. The reason for this is that the index buffers can be computed in advance and simply re-used for the 16 (2^4) different cases. Each of north, east, south and west can either be the same level or one less (if a neighbour is of a higher level then we would be a lower level to it and hence we would join two seams of the same detail - see figure 1).

Figure 1. Paint rocks

In regard to calculating the vertices, I'm thinking it might be a good idea to separate the load across cores (everyone uses multicore now right?). The general idea is to:-

  1. Traverse the tree splitting nodes as usual.
    1. Create child nodes, update neighbour pointers, etc. This may be recursive to keep the quadtree restricted to one LOD difference (note: pain, if not impossible, to parallelise).
    2. Add a pointer to each node that needs its vertices calculated to a list and defer actual calculation until after the tree has been processed.
  2. Simply dispatch calculation jobs to threads, these jobs are independent and nicely parallelisable.
  3. Vertex buffers also need to be created to please direct3d, shouldn't be too hard to squeeze them in somewhere.

Geomorphing is causing me to think, I can't find much on the internet to base my implementation from. I have never done anything to do with vertex interpolation before so this could be a horrible way of doing it. I'm thinking of sending the vertex shader: x, y, z, base_y where base_y is the value of y at the previous LOD level. This can be simply calculated by either taking the value as-is (for when the point coincides with the same point in the last LOD) or interpolating between two values from the last LOD (i.e. where there was an edge on a triangle). It's then just a case of interpolating between base_y and y for each vertex using a per frame shader constant.

Results soon.

1 comment: