Jump to content
  • Advertisement

Archived

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

SnprBoB86

Rethinking My Scene Graph and Spatial Partitioning

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

Recently, I have returned to my hobby 3d engine after many long months of no time to work on it. I had to re-familiarize myself with the code and in the process have begun to rethink my engine’s design. The engine is currently extremely simplistic; it consists of a standard scene graph of "Entities" which can have a parent and many children entities, but so far I have not utilized the hierarchical nature of it nor have I tested it (but I suspect it does not work, so I am very open to completely recoding it). My spatial partitioning algorithm is a barebones implementation of an ABT (Adaptive Binary Tree) as outlined by Yann L. I do not support primitive geometry, but instead scene geometry is composed by many small static mesh type entities which are fitting into the ABT instead of the individual polygons. It seems to work fairly well on my flat (non-hierarchical) scene. I also intend to implement occlusion culling instead of portals. Should there be a top level ABT that ALL entities exist in? Or should there be an ABT of top level entities and then each entity’s children arranged in a smaller (and potentially optional) ABT built within the AABB of the parent entity? In addition to that question, I am trying to better understand the pros and cons of my ABT and scene graph implementation. So feel free to ignore that question and just discuss these concepts in general. Thank you, SniperBoB

Share this post


Link to post
Share on other sites
Advertisement
You really have a number of choices. You seem to have a good understanding of the possibilities, just let me expand a little more upon what you can do with this.

Basically a top level ABT for all entities is a good idea, however you may find that you may be using some specialised techniques for an entity or group of entities this is where you can possibly have another spatial partition that is bounded by an external AABB that you can pass to the parent tree. This seems to be the basis of your question. I would say that generally everything should be in the high level of the ABT. In fact I can''t really see a need for a ABT in one of the entities as it should generate a very similar if not identical tree when run from the parent tree. Some things I can see being useful is things like a quadtree entity for a terrain section of your world or maybe you use a BSP tree to describe the buildings in your world - these are all suited to be held within an ''entity'' in the global ABT tree. Note that it is still possible for you to define other relationships between the entities i.e. you could also store heirarchial relationships for kinematics etc.. i.e. provide more than one ''interface'' to access the elements that have different underlying graph based structures.

Another issue you may want to consider is that of dynamic geometry i.e. do you try to combine it into one ABT and rebuild as things move, or do you build two seperate ones, for dynamic and static geometry?

James

Share this post


Link to post
Share on other sites
Thinking about it more, it seems that sticking with my top level flat ABT is the best way to go and that I should finish implementing the hierarchical system where even children entities will appear in the singular ABT.

The dynamic vs. static objects is another interesting issue. Ultimately, I would like every entity in my scene to be potentially dynamic, but of course some will remain static although they do not have to be.

With this is mind, I think I need to understand the way ABTs work with that whole "degeneration factor" idea that I saw elsewhere on these forms. What are the possible options (and pro/cons of each) for handling this? All I can think of is that there must be some sort of measurement of how much an ABT node has moved and then a threshold on that before regeneration, but the direction in which it moves (perpendicular or parallel to the last split plane) seems like it could make a large difference. How could I make this degeneration factor/threshold more intelligent?

-SniperBoB-

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!