Advertisement Jump to content
Sign in to follow this  

Efficiently parsing quadtree spheres for lod selection and collision detection

This topic is 2681 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

My final goal is to procedurally generate a whole planet, with rather extreme lod's.
Obviously I'm still quite far away from that goal, and my question is unrelated to terrain shaping.

My current situation
Right now I have a Quadtree which generates my geometry.
I start off with a cube (6 faces), each face is a node in my quadtree and can be tesselated by creating new children.
Each face can be projected to spherical coordinates using this method:
which produces very nice results.
All of this can be done asynchronously, without stalling the render thread, which is important since I want to generate terrain on the fly.
This seems like a rather straightforward approach, and I had no problems implementing this.

However, I'm a bit uncertain as to which method to use to parse this tree efficiently and safely
for lod selection and collision detection.

AABBs do not work for spheres
If I was working with flat terrain, I'd just make each node of the quad tree have an AABB.
I could easily find which leaf node the camera is in.
But this will not work for a sphere. The generated faces aren't axis aligned... they all point in different directions.

My nodes are not aligned with spherical coordinates
Another idea I had was to make every node store its spherical coordinate range.
I could easily find out what the camera's current spherical coordinate in relation to the sphere would be and parse the Quadtree accordingly.
Unfortunately, since I project a tesselated cube to a sphere, my nodes are not aligned to spherical coordinates, so this won't work either.

Can I do everything in 'cube space' ?
My final idea, which is the only one that actually has the potential to work, is to do these calculations in "cube space".
New nodes are created in cube space. I could at this point in time compute the AABB in cube space for this node.
The AABB will remain unchanged, even after the spherical projection and terrain shaping.
To parse the tree, I'll project the camera position into the sphere's cube space, which will allow me to check against the AABBs correctly.
I think this should work fine for lod selection, but I'm a bit scared that this could become a bit dodgy once I want to do collision detection.
(although right now, I don't see any major problems with it)

I'd be very happy about any input on this.


Share this post

Link to post
Share on other sites
I think that, at a coarse level, I'd work in your cube coordinates (to determine what sector you're in, LOD, etc), and that at a fine level (collisions with objects in your sector) I'd just work in 3d cartesian coordinates. Ultimately, I'd maintain all state information in 3d, and project into "cube coordinates" as needed.

In principle, it doesn't have to be "cube coordinates;" any convenient atlas will do. But "cube coordinates" are probably the most convenient. You can think of them as six coordinate charts, each defined on an open hemisphere, and overlapping with four others. In this way you get overlap maps and all the machinery of differential geometry, without having to worry about how to define what happens at cube edges and vertices.

Share this post

Link to post
Share on other sites
Could you elaborate on this?

For lod selection I don't really care where a node is, I just want to know which one is closest to my camera.
For collision detection I also need to find the closest node to a point. This node will contain the geometry (in 3d Cartesian coordinates) which I need to check against.
Finding the correct node needs to be safe and fast.

The only method I can think of where searching the correct node is done exclusively in 3d Cartesian coordinates
is my first suggestion (AABBs), but as I mentioned, this does not work for my sphere.
My 3rd method sort of enables to do exactly that though, except there is a projection involved.
The method still does the actual lookup in 3d Cartesian coordinates, except the bounding boxes are no longer in the same coordinates as the geometry
(but this shouldn't matter, because the node I find will contain the geometry I'm looking for in the correct space)

Share this post

Link to post
Share on other sites

Could you elaborate on this?

Hmm, apparently you replied while I was editing my first post, so I'm not sure what I should elaborate on. That's my fault; sorry. Anyway, it sounds like you have it all figured out, so I don't know how much I can really help.

I do like your cubemap approach. I think we're on the same page with it.

That said, I also don't see what would be wrong with a generic BVH in 3d. Sure, the volumes would overlap, but that doesn't need to be a problem...

Share this post

Link to post
Share on other sites
I did indeed reply whilst you were editing your post, we're definitely on the same page.

Thanks for your input!
This is sort of a critical decision for what I'm trying to achieve, and if taken improperly could come back to haunt me during later stages of development,
so it's good to hear that my approach sounds like it should work.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!