Jump to content
  • Advertisement

Archived

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

klajntib

Totally newbish question on scenegraphs, trees, etc..

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

OK, so I''ve read every bloody topic on this forum - including the ones with Yann''s wisdom. I''m currently in the process of designing a simple engine and I''m currently thinking about scene management. This is what I have in mind so far: - Have a scenegraph for a hierarchycal representation of the scene - The scenegraph would contain indices/pointers into a global list of all dynamic objects - It would contain (at the root level) an octree for static indoor geometry and a quadtree for outdoor terrain geometry This is all very basic stuff. But I''m having problems with incorporation collision detection into all this. Collision detection would require somekind of a structure with dynamic objects grouped in relation to their position, and that would mean a dynamic tree. Yann''s ideas about using degeneration factor and stuff are very interesting. But would I have to build a second tree for collision detection? How do you manage your scene in your engines/games? Bah.. the more I read, the more lost i feel

Share this post


Link to post
Share on other sites
Advertisement
quote:
Original post by klajntib
Bah.. the more I read, the more lost i feel


Same here...

Anyway, don''t you think portals, bsp or abt might be better for indoor areas? (abt can also be used for outdoor).

Octtree/quadtree/abt are all dynamic. I don''t think you need another tree for collision detection. Check the collider with every collidee in the same node.

I''m very noob, and haven''t started to implement trees, but the above is what I think, based on what I''ve read (Including YannL''s excellent posts).

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
i haven''t written any scenegraph implementations yet, but I usually insert dynamic objects into leaf nodes of the tree. A direct access quatree can make this very simple as the leafnode to insert in to can be determined using the players x,z locations. once all dynamic objects are in the tree you just need to test objects that exist in the same leaf nodes against each other for collision.

Share this post


Link to post
Share on other sites
quote:
Original post by frostburn
Octtree/quadtree/abt are all dynamic.


not true, necessarily. the standard implimentation of the above is dynamic at build time, but static at run-time. this is the same as with BSPs. at build time you dynamically throw your polygons into the data structure, but at run-time you statically load them from a file already in the structure. they are intended for non-moving objects. there are a few methods that i''ve seen/used for keeping dynamic objects in the correct tree node, but they''re largely inefficient. you definitely don''t want to be splitting your geometry up between tree nodes at runtime b/c it''s a really slow process. if you''re using the tree for your dynamic objects as well as the static ones, you''ll end up with multiple instances of your dynamic objects in the tree at the same time. i.e. an object can potentially occupy up to 8 leaf nodes in and oct-tree or 4 nodes in a quad treee. it can still help with collision detection, but there are better algorithms for the implementation of collision detection amongst dynamic objects.

on a first pass you check the dynamic objects each against the octtree/quadtree, then you check them amongst eachother using something like a .... searching for term... called something like a prune sweep or pruning (don''t know the algorithm i''ve just heard the term )...

-me

Share this post


Link to post
Share on other sites
Yeah, that''s the problem. Inserting object dynamically is a pain in the ass and also very slow. So, whats that pruning stuff?

You''re probably talking about this:
http://parallel.vub.ac.be/documentation/pvm/Example/Marc_Ramaekers/node3.html

Hm... what about culling? I would use frustum culling, but that''s probably not enough. Any tips?

And also - sorting by shader and texture - how would I go about integrating that into my scenegraph? Blah.. so many problems

Share this post


Link to post
Share on other sites
You don''t exactly integrate the spatial division (i.e., octree) with your scenegraph; the two are basically independent, and just happen to hold pointers to the same objects. Your scenegraph simply helps you organize objects conceptually (and apply hierarchical transformations), while your spatial division scheme helps you decide which objects to render this frame (among other purposes, including perhaps collision detection). Sorting of the objects is accomplished by your graphics engine, so it''s not really integrated with your scenegraph / octree at all.*

* I''ve seen some people sort objects within octree nodes, but whichever way you choose really depends on your engine.

Share this post


Link to post
Share on other sites
Yeah that''s what I was thinking, but didn''t know how to put it in words

So I should use an octree or something for dynamic objects too? And rebuild it when it gets too deformed of what? How costly is ti to constantly update the tree? Yann talked about ABTrees or something - but I have no clue what that is - and how he rebuilds certain branches from time to time...

And about sorting - what I''m having problems is the fact that if I apply transformations and draw everything as I traverse the scene graph, I have no way of sorting by texture and stuff... so I should traverse the scene graph and store world transformation matrices and compute other stuff (skeletal animation matrices and soforth) and then have another class (for example the renderer) go through all objects, sort them by shader for example and then draw them using the data previously computed by the scene graph traversal?

Share this post


Link to post
Share on other sites
Octtrees/Quadtrees static at runtime? I definitely need to read more before trying to implement it
I''d rather go with ABTs anyway..

ABT: Axial Binary Tree.

Fore each branc you split either along the X, Y or Z axis.

NOTE: The location of the split can vary. the splits aren''t linearly spaced. Any split objects will be wholly contained in the "current" and the nabouring node.

Luvly ASCII art:

2D ABT:

Root
+-------+
| |
| a |
| |
+-------+

1: split along Y axis
+---+---+
| | |
| b | c |
| | |
+---+---+

2: split along X axis (right branch shown)
+---+---+
| | d |
| b +---+
| | e |
+---+---+

(The next are enlarged to make it easier to see and "draw")

3: Split along Y axis (Right top shown) - For 3D split Z instead
+-------+---+---+
| | | |
| | f | g |
| | | |
| b +---+---+
| | |
| | e |
| | |
+-------+-------+

4: Split along X axis (Right top left shown) - For 3D split Y instead
+-------+---+---+
| | h | |
| +---+ g |
| | i | |
| b +---+---+
| | |
| | e |
| | |
+-------+-------+

a (root)
+ b (left)
+ c (right)
| + d (top)
| | + f (left)
| | | + h (top)
| | | + i (bottom)
| | + g (right)
| + e (bottom)

(I only made one part of the tree)

for a 3d tree it could be:
(root)
(left)
(top)
(bottom)
(in)
(out)
(left)
(right)
(right)

etc.

Problem with Quadtree:
a b c d
+---+---+---+---+
1 | | ### | |
+---+---+---+---+
2 | | | | |
+---+---+---+---+
3 | | | | |
+---+---+---+---+
4 | | | | |
+---+---+---+---+
(### = object)
The object gets split and ends up in b1 and c1. These nodes are spatially neighbors, but not hierarchially neighbors.

Tree:
(root)
(12ab)
(1a)
(1b)
(2a)
(2b)
## (1/2 object)
(12cd)
(1c)
## (1/2 object)
(1d)
(2e)
(2f)
(34ab)
(34cd)

An ABT would AFIK avoid splitting the object by moving the split.


If someone could correct any mistakes that would be great.. The only source I have for ABTs are Yann''s and other''s posts here on GameDev.

Share this post


Link to post
Share on other sites
Oh, thank you veryveryvery much This explains a lot!
PS: You''re a talented artist

This tree is initially created on runtime, then it is constantly checked for degeneration and when it gets too degenerated, you just rebuild certain branches. Correct me if I''m wrong somewhere

This seems very cool. So basicly I should have 2 spatial partitioning trees - one for static geometry that always remains the same and one for dynamic objects, that is constantly checked for validity and "repaired" if objects move around too much. (this is how yann does it I think..)

And have a scenegraph for a purely logical representation of the scene.

The I would do this every update:
- Go throught the scenegraph and calculate all transformations etc. and store it.
- Go through the ABT for dynamic objects and check for collisions and simultaneously determine visibilty and add visible objects to a renderlist
- Go throught the tree of static geometry and find visible parts and add them to the renderlist
- Sort the render list by shader and maybe by texture so as to minimize state changes
- Draw

But this could be very ineffective for various reasons:
1. There''s tons of tree traversal going on - how slow is this?
2. Sorting could take a while, but a simple bucket sort should be fast enough
3. Doing things in this order kind of breaks CPU-GPU parallelism or at least I think so... because I first do purely CPU work and the purely GPU work...

Thoughts? Ideas? Sugggestions?

Share this post


Link to post
Share on other sites
quote:
Original post by klajntib
So I should use an octree or something for dynamic objects too? And rebuild it when it gets too deformed of what? How costly is ti to constantly update the tree? Yann talked about ABTrees or something - but I have no clue what that is - and how he rebuilds certain branches from time to time...


One possibility is a "loose octree" by Thatcher Ulrich - google will find it.

quote:

And about sorting - what I''m having problems is the fact that if I apply transformations and draw everything as I traverse the scene graph, I have no way of sorting by texture and stuff... so I should traverse the scene graph and store world transformation matrices and compute other stuff (skeletal animation matrices and soforth) and then have another class (for example the renderer) go through all objects, sort them by shader for example and then draw them using the data previously computed by the scene graph traversal?

Yes.
quote:

3. Doing things in this order kind of breaks CPU-GPU parallelism or at least I think so... because I first do purely CPU work and the purely GPU work...


It''s ok for PCs because (at least with Direct3D) the driver buffers up to 3 frames worth of render commands (even with vsync enabled). So if your CPU is running ahead of the GPU it doesn''t matter whether the CPU is traversing your scenegraph or sending the sorted renderlist to d3d/ogl because the GPU is still working on the previous frame or the frame before that even. And if the CPU spikes temporarily due to, say, a fixed 20Hz physics update then it has up to 3 frames of padding where it doesn''t have to feed anything to d3d/ogl.
If your CPU is running behind your GPU (ie no frames are buffered) then it''s probably because the CPU can''t keep up (on average) but you''re still getting CPU/GPU parallelism.

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!