Jump to content
  • Advertisement
Sign in to follow this  
littlekid

How should I build a Spatial Tree?

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

Hi, I have read up the threads on the diccussion of ABT/Octree (mostly by Yann) and have tried to implement it. However I am met with a few problems as to how the Nodes of the Spatial Tree stores the information. Mainly as a group of polygons or as a pointer to the Mesh Method 1: Does it stores a pointer to the Mesh/Object, and when I do a frustum culling against the Node's AABB, if the node is visible, I render the Meshes pointer stored in the node. This would result in meshes that may span across many spatial nodes. My instinctive feeling is that this would not be very efficient. Method 2: Hence I thought I would split up the Mesh itself, thus there would be no sense of a Object in the Node of a spatial tree. Meaning at the Nodes of the spatial tree, I store a list of triangles/polygons. Which Method would be better? If I am to use Method2, would I need to strip the object and rebuild the vertex & index buffer? Resulting in each node having its own Vertex & Index Buffers.

Share this post


Link to post
Share on other sites
Advertisement
You can just make sure that an object completely fits in the node that it's in. If you do that, no object will span multiple nodes, but the objects will be "higher up" in the tree.

For static geometry you might want to avoid this and split meshes so that they will be in "lower" nodes. for dynamic (i.e., moving) geometry you can't do this (too slow), but you can use a "loose" data structure where some of the nodes overlap each other and then you'll be able to push the objects further down.

I think the ABT handles all this more elegantly, but I don't know much about it so I'll leave that to someone else.

Share this post


Link to post
Share on other sites
A question on the subject:
Lets say i have two objects obj1 and obj2 stored in a node in a octree as a list of polygons. Obj1 has texture tex1 and uses shader sh1 and obj 2 tex2 and sh2. how
would i render the polygon list correctly? I mean how do i say that this triangle uses sh1 and tex1 and this other one sh2 and tex2

Share this post


Link to post
Share on other sites
Thanks for the reply.

If I have understood correctly, I would need at least 2 trees maybe 3 of them. This is what I came up with that I should need:

SceneManager that controls these:
A SceneGraph
A Dynamic Tree
A Static Tree
A SemiStaticDynamic Tree

The SceneGraph will work closely with the Dynamic Tree. The former being a hierarchial graph, while the dyanmic tree would be for spatial/culling purpose.
Hence If say I remove a node+children from the SceneGraph, all corresponding node+children will be remove from the dynamic tree.

For the Static Tree I would have it in a parition at a polygon basis, hence no object sense.
For the SemiStaticDynamic Tree, it would be partition at object level.
For the Dynamic Tree, it would also be partition at object level just that it can be subjected to rebuild of the trees.

Is my idea practical? Or are there better ways to handle them?

Thanks alot

Share this post


Link to post
Share on other sites
For static geometry you partition at the polygon level as a pre-process.
To handle the situation of multiple materials per node you have to associate each polygon with a material/shader/shader-state; you then group polygon faces with the same shader states together into chunks - all this as part of the pre-process. At run-time you traverse the structure, applying HSM as necessary, and collect together all the chunks, sort them to reduce state changes and render as usual.

For dynamic geometry you partition at the object level.
Either, you use a rigid structure and objects that don't fit into a node are moved up the hierarchy until they do so. Or, you use a loose structure and if an object doesn't fit into a node then you resize the node, even if that means it overlaps; you can periodically rebuild the hierarchy to prevent it becoming too degenerate.

One other thing to note: If you plan on implementing collision detection yourself then you may want a separate spatial tree for that purpose; good spatial culling for rendering doesn't imply good spatial culling for collision detection.

Quote:
For the Static Tree I would have it in a parition at a polygon basis, hence no object sense.
For the SemiStaticDynamic Tree, it would be partition at object level.
For the Dynamic Tree, it would also be partition at object level just that it can be subjected to rebuild of the trees.

I don't understand how you plan on using the Dynamic Tree differently to the SemiStaticDynamic Tree, it seems they're full-filling the same job?

Share this post


Link to post
Share on other sites
Thanks dmatter.

Well I am not too sure myself of the difference myself as it just a gut feeling of the need to have a tree for SemiStaticDynamic Trees.

I was kind off thinking along the line that objects that goes into these tree are objects that cannot be transformed in real world, but are animated. Like a swaying tree or a key fixed npc character that cannot move but can be animated.

Hence since such objects can't be transform in real world, they can be pre-computed and would not need rebuilding at realtime.

Is it a good idea?

Share this post


Link to post
Share on other sites
Quote:
Original post by littlekid
Is it a good idea?

Making the distinction is more of an optimisation really, so it's your decision to make based on if you need it. [smile]
Whether or not you choose to use a separate structure for these entities is a matter of taste vs implementation. It's certainly the least important compared to the scene-graph, static-graph and dynamic-graph.

Share this post


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

  • 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!