Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Spherical Trees?

This topic is 5579 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

I have a few ideas regarding these, but since Yann L mentioned them in this thread, I was wonderring if anyone knows where I can find some info on them? Yann? I tried to google a bit, but didn''t find anything useful... Michael K., Designer and Graphics Programmer of "The Keepers"
We come in peace... surrender or die!

Share this post


Link to post
Share on other sites
Advertisement
While spherical trees are technically possible, it does not necessarilly mean that they are useful But it depends on your exact scene type.

Essentially, they are the same as an AABB or OBB tree, but instead of a box hierarchy, you use a sphere hierarchy. Sphere trees are not so much used as visibility culling structure, but more as a collision system, since checking for collision is extremely fast with a sphere. Building the tree is more complicated through. The biggest drawback is that typically the localization behaviour is pretty bad. But as always, that depends on the exact details of your geometry. If you extend it to eliptic-trees, then it can actually work pretty well for organic objects, such as humanoid characters.

We use them to get nice round and organic looking collisions between a character and a cloth simulation. It''s not always totally accurate, but very efficient.

Share this post


Link to post
Share on other sites
Oh.. Ok then.

Well, this is not what I was thinking about. I was thinking more in the direction of something like an ordinary octree, but using polar coordinates (lattitude, longtitude, altitude). This would make the tree represent a spherecal volume instead of a cubic volume, which may be very useful in my case, since my game ivolves the simulation of a planet (which is, of course, spherical). With a couple of adjustments, it would also create a continueous surface, meaning that you can go around the planet without worying about wrapping around the edge of the data structure. This should be rather useful for things like weather simulation, which can benefit from a continueous representation...

Michael K.,
Designer and Graphics Programmer of "The Keepers"



We come in peace... surrender or die!

Share this post


Link to post
Share on other sites
Ah yes, I see. Interesting thought. I guess such a structure could be usefull for planetary scale engines. You wouldn't even need a whole sphere, the outer shell of the planetary surface (along with it's atmosphere) should be enough. Basically, it is a standard octree, but build in a non-standard (ie. non-cartesian) coordinate space. Instead of (x,y,z) you would have (alpha,beta,distance). Horizon culling and such would be pretty efficient. I would definitely encourage you to try that system out, and report about your results.


[edited by - Yann L on February 10, 2003 1:23:34 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Yann L
You wouldn''t even need a whole sphere, the outer shell of the planetary surface (along with it''s atmosphere) should be enough.

Yes, of course. The root node would simply go from altitude internal-crust-radius to outer-atmosphere-radius (or somthing like that), instead of from 0 to outer-atmosphere-radius.
quote:

Basically, it is a standard octree, but build in a non-standard (ie. non-cartesian) coordinate space. Instead of (x,y,z) you would have (alpha,beta,distance).

It might get a bit more complicated than that, but basically yes. Also, I am considerring to combine that with ABT''s (i.e. use a polar-coordinate ABT instead of a polar-coordinate octtree).
quote:

Horizon culling and such would be pretty efficient. I would definitely encourage you to try that system out, and report about your results.

Thanks. Athough I''m a bit worried about the polar-coordinate math performance, and trasitios between polar coordinates for simulation and such, and cartesian coordinates for rendering. So far, it doesn''t look like too much of an issue, but I haven''t figured out all the math yet, so I''m not entrirely sure... This is what I''ll be thinking about over the following several days, I suppose.



Michael K.,
Designer and Graphics Programmer of "The Keepers"



We come in peace... surrender or die!

Share this post


Link to post
Share on other sites
I''m writing a fractal planet generator... I split my "planet" into 8 initial triangles (one per axis-aligned octant), each fractal division splits each triangle 4 ways.

I''m using rectangular coordinate system... spherical seems like too much of a pain.

My end goal is to have a player on the surface somewhere, and have high division count near them, and lower division counts elsewhere.

So far I''m having a fist-fight with removing T-vertices conditions where I divide one triangle and not it''s neighbor, but it is promising other than that.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!