Jump to content
  • Advertisement


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


Is it possible to have one tree for all the data in the scene?

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

So here I'm, I have a few quadtree implementations for my terrain and I'm happy with them for terrain, however now that I'm putting models into the terrain and buildings I have come to a problem. One tree or two trees? While I could have all the "static" stuff (terrain, buildings, trees) in the quadtree (the game is isometric) and then I could put all the moving objects into another type of tree. The terrain is for mechs and I'd want to have up to 50 mechs in the scenery (more is plus) and while the mechs are now low-poly (low enough to have single bounding sphere test) I'd like to have the possibility of having high poly mechs in case I ever find decent artist. Now why not having everything in lets say one structure, Octree? Has anyone attempted this? I'd appreciate any practical information . Edit: what about lods? I completely forgot that. [edited by - Captain Goatse on June 17, 2003 9:06:50 AM]

Share this post

Link to post
Share on other sites
While it''s possible to have everything in a single tree, it is generally not very practical/optimal, since data for collision det/path finding/rendering/static vs dynamic is handled and sorted differently.

Example: coldet vs rendering: while it is good for rendering to have some leaf nodes whith hundreds or thousands of triangles, it is not the case for col det. However one could create a tree where col det leaf nodes are deeper (and contain less triangles) than rendering leaf nodes into a single shared tree.

Share this post

Link to post
Share on other sites
I've been using a method for the outdoor portion of my engine that is simple and probably old tech now, but seems to work well for me.

What I do is I use the grid approach instead of a quad/oct tree.

What I do is start with terrain blocks (mine 32x32), for each terrain block have three lists attached to it, a static non-collider, static-collider and dynamic object list. The static non-collider contains things like plants, shrubs and grass. The collider list containing things like buildings, trees, rocks, triggers, doors, etc. The dynamic list contains players, projectiles, etc.

Since statics can't collide with other statics, you only need to check the dynamic objects against the static collider list and dynamic object list. As dynamic objects move they update/insert themselves into what grid square(s) list they exist in. Each object also maintains a last_time field to keep them from being rendered twice.

For both local collision and rendering, just take the player object's location on the grid and project out a bit. For example:

grid[i][j].render; // Frustum cull/render


For a server, you do basically the same thing except you have a player list which you process similarly to the loop above. This also acts to minimize the network traffic to the area just around that player.

LOD works well here too if you want to increase the render_radius. I have not implemented it yet, but might at some point.

You can also have the render function insert the objects into another list which you can sort by shader state and/or transparency/Z-depth and then render. (I think this should work, but have not tried yet.)

So, while I don't think anything here is new, it seems to me to be a very simple and effective way to deal with large outdoor scenes.

[edited by - Zarmax on June 17, 2003 11:09:33 AM]

Share this post

Link to post
Share on other sites
But is it practical to have just one Octree?

For example it would be unpractical to store all the indices and vertices in one array since they change and also it would require major tweaking. I can''t see how you could do this otherwise.

Would my best bet to be static scenery and dynamic scenery?

I''m pretty sure quadtree would be best for my isometric view and then have a linked tree or linked node list (every model is separate octree?) type of thing for everything else?

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.

GameDev.net 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!