• Advertisement
Sign in to follow this  

3D Adapting planar quadtree for spheres

Recommended Posts

Adapting planar quadtree for sphere

 

Hi everyone,

 

I'm quite used to working with quadtrees for flat, 'infinite' terrain where I just have a coherent noise function that returns a height for a given x, z position and quadtree cells are split based on camera distance to their centre (where the centre takes into account the height as well).

 

I'd like to expand this to work for spherical planets using the common method of having 6 quadtrees which form a cube, then normalising the vertex positions to make a sphere. I have a few questions though which none of the tutorials for this seem to answer:

 

  1. What coordinates should I use to sample my noise function? The raw (x, y, z) coordinates of the vertex positions in the cube, or should I use the same coordinates but after I've 'spherified' them?
  2. What distance should I use to decide if quadtree nodes should split/merge? Should I use distance from camera of the node in its cube position, or should I work out where the node's centre is on the sphere and then use the distance to that?

 

Thanks for the help :)

Share this post


Link to post
Share on other sites
Advertisement

1. Make your noise function 3D and use coords from sphere surface (easier / nicer than trying to make corners and edges seamless).

2. Use sphere positions, otherwise the error becomes large if you are close to the surface.

Share this post


Link to post
Share on other sites

Thanks for the reply - makes sense! For the second point, I guess that means a given LOD in the quadtree will have a slightly differing vertex density across the sphere due to the deformation when the tiles are projected onto the sphere? I suppose it's a minor problem though.

Share this post


Link to post
Share on other sites
32 minutes ago, george7378 said:

Thanks for the reply - makes sense! For the second point, I guess that means a given LOD in the quadtree will have a slightly differing vertex density across the sphere due to the deformation when the tiles are projected onto the sphere? I suppose it's a minor problem though.

I am not sure what you mean what i think, but if you map a tesselated cube to a sphere the result is never uniform.

You can improve some things at the cost of others, e.g. you can make sure all quads on the sphere end up having equal area, which sounds nice, but comes at the cost of more distortion at the edge angles of the resulting quads. Normalizing the tesselated cube vertices is simple and a good compromise of anything - i always came back to that after messing with more complex mapping approaches.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By PhillipHamlyn
      Hi
      I have a procedurally generated tiled landscape, and want to apply 'regional' information to the tiles at runtime; so Forests, Roads - pretty much anything that could be defined as a 'region'. Up until now I've done this by creating a mesh defining the 'region' on the CPU and interrogating that mesh during the landscape tile generation; I then add regional information to the landscape tile via a series of Vertex boolean properties. For each landscape tile vertex I do a ray-mesh intersect into the 'region' mesh and get some value from that mesh.

      For example my landscape vertex could be;
      struct Vtx { Vector3 Position; bool IsForest; bool IsRoad; bool IsRiver; } I would then have a region mesh defining a forest, another defining rivers etc. When generating my landscape veretexes I do an intersect check on the various 'region' meshes to see what kind of landscape that vertex falls within.

      My ray-mesh intersect code isn't particularly fast, and there may be many 'region' meshes to interrogate, and I want to see if I can move this work onto the GPU, so that when I create a set of tile vertexes I can call a compute/other shader and pass the region mesh to it, and interrogate that mesh inside the shader. The output would be a buffer where all the landscape vertex boolean values have been filled in.

      The way I see this being done is to pass in two RWStucturedBuffer to a compute shader, one containing the landscape vertexes, and the other containing some definition of the region mesh, (possibly the region might consist of two buffers containing a set of positions and indexes). The compute shader would do a ray-mesh intersect check on each landscape vertex and would set the boolean flags on a corresponding output buffer.

      In theory this is a parallelisable operation (no one landscape vertex relies on another for its values) but I've not seen any examples of a ray-mesh intersect being done in a compute shader; so I'm wondering if my approach is wrong, and the reason I've not seen any examples, is because no-one does it that way. If anyone can comment on;
      Is this a really bad idea ? If no-one does it that way, does everyone use a Texture to define this kind of 'region' information ? If so - given I've only got a small number of possible types of region, what Texture Format would be appropriate, as 32bits seems really wasteful. Is there a common other approach to adding information to a basic height-mapped tile system that would perform well for runtime generated tiles ? Thanks
      Phillip
    • By GytisDev
      Hello,
      without going into any details I am looking for any articles or blogs or advice about city building and RTS games in general. I tried to search for these on my own, but would like to see your input also. I want to make a very simple version of a game like Banished or Kingdoms and Castles,  where I would be able to place like two types of buildings, make farms and cut trees for resources while controlling a single worker. I have some problem understanding how these games works in the back-end: how various data can be stored about the map and objects, how grids works, implementing work system (like a little cube (human) walks to a tree and cuts it) and so on. I am also pretty confident in my programming capabilities for such a game. Sorry if I make any mistakes, English is not my native language.
      Thank you in advance.
  • Advertisement