LeafNodes saving their world transforms?
Author
I'm in need of some input here...
I'm thinking about possibly having all my LeafNodes keep track of their worldtransforms. Is this a bad thing?
I don't think all my LeafNodes will be in need of this information, but anything with a BoundingBox or Sphere (either for collision dectection, culling, or something else) would need their worldtransform, right?
Also, my EmitterNodes (also a LeafNode) are in need of their world position, since the particles need it. (otherwise my particles will follow the emitter when i move it)
My LeafNodes cannot have any children (thereof the name), and any form of geometry will be a LeafNode.
Note: My engine is only for 2D so far, but i would like to be able to extend it to 3D at some point.
I don't know if you need any other info... if you do, i'll try to fill you in.
Assuming you have a hierarchy of nested bounding volumes (which is typical of scene graphs) then you don't need to cache a computed world transform to update bounding volumes (when transforms are modified). I suggest updating BVs in a lazy manner i.e. on an as needed basis.
It's a quite simple thing to do, your SG node base not only maintains a bounding volume in world coordinates but also a "dirty bounds" flag, every time something like a transform node is updated/modified/created/etc you mark the bounds dirty (set the "dirty bounds" flag to true) for later on.
When the world BV of a particular SG node is actually needed your "get bounds" method checks whether the bounds is dirty before returning and if it is then you trigger a "recompute bounds" method. This method must work polymorphically and may be recursive depending on the type of the node in which you called the "get bounds" method and also the way it overrides the "recompute bounds" method.
Okay it's a bit of a mouthful to explain but should be simple in code:
Note! that this code is intentionally missing information...
Caching a concatenated, computed world transform this is useful for other tasks like preparing to render later on etc, etc but only applicable to a strict n-ary tree, if it's a DAG then you'll have to do it outside the structure using stacks etc, etc.
[Edited by - snk_kid on December 1, 2005 4:43:00 PM]
It's a quite simple thing to do, your SG node base not only maintains a bounding volume in world coordinates but also a "dirty bounds" flag, every time something like a transform node is updated/modified/created/etc you mark the bounds dirty (set the "dirty bounds" flag to true) for later on.
When the world BV of a particular SG node is actually needed your "get bounds" method checks whether the bounds is dirty before returning and if it is then you trigger a "recompute bounds" method. This method must work polymorphically and may be recursive depending on the type of the node in which you called the "get bounds" method and also the way it overrides the "recompute bounds" method.
Okay it's a bit of a mouthful to explain but should be simple in code:
struct matrix4f { ... };struct BV { // .... BV merge(const BV& b) const { // TODO! } template < typename VertexInputIterator > void fit_bounds(VertexInputIterator first, VertexInputIterator last) { // TODO! } // ...};class base_node { friend class grouping_node; grouping_node* parent_; mutable BV world_bounds_; mutable bool is_bounds_dirty; // ...protected: virtual bool compute_bounds() const = 0; // all sub-types must override void set_bounds(const BV&) const { /* TODO! */ } void transform_bounds(const matrix4f&) const { /* TODO! */ } template < typename VertexInputIterator > void fit_bounds(VertexInputIterator first, VertexInputIterator last) const { world_bounds_.fit_bounds(first, last); } // ....public: //... bool is_bounds_valid() const { return !is_bounds_dirty; } void mark_bounds_dirty(); const BV& get_world_bounds() const { if(is_bounds_dirty) is_bounds_dirty = !compute_bounds(); return world_bounds_; } virtual ~base_node() {} //.....};//....#include <algorithm>#include <deque>#include <boost/shared_ptr.hpp>// an internal node of an n-treeclass grouping_node : public base_node { // ... typedef boost::shared_ptr<base_node> node_ptr; typedef std::deque<node_ptr> child_list; child_list kids; //....protected: // ... struct merger { // utility functor BV operator()(const BV& s, const node_ptr& n) const { return s.merge(n->get_world_bounds()); } }; bool compute_bounds() const { if(kids.empty()) return false; child_list::const_iterator itr = kids.begin(); // get the first child's bounds BV s = (*itr)->get_world_bounds(); // now replace group's old BV with a new one // which is the result of all children's world bound volumes set_bounds(std::accumulate(++itr, kids.end(), s, merger())); return true; } // ...};// defined after the definitions of the "group" class existsvoid node::mark_bounds_dirty() { if(is_bounds_valid()) { is_bounds_dirty = true; if(parent_ != 0) parent_->mark_bounds_dirty(); // note recursion! }}class transform : public group { matrix4f trs; // .... protected: // override group's imp bool compute_bounds() const { if(!group::compute_bounds()) // invoke base's imp return false; // transform_bounds(trs); return true; } // ...};//....#include <vector>struct Vertex { ... };// leaf node type representing geometryclass geo_node : base_node { typedef std::vector<Vertex> VertexBuffer; typedef boost::shared_ptr<VertexBuffer> VertexBufferPtr; // shared vertex buffer; VertexBufferPtr vertices; // ....protected: bool compute_bounds() const { if(vertices == 0) return false; fit_bounds(vertices->begin(), vertices->end()); return true; } // .....};Note! that this code is intentionally missing information...
Caching a concatenated, computed world transform this is useful for other tasks like preparing to render later on etc, etc but only applicable to a strict n-ary tree, if it's a DAG then you'll have to do it outside the structure using stacks etc, etc.
[Edited by - snk_kid on December 1, 2005 4:43:00 PM]
Author
yes, this was quite a mouthful for me. I understand most of it, but since this is my first attempt at a simple engine, some of this is over my head right now.
1.
---------
But you suggest that all SG Nodes of any kind has its own BV in world coordinates, for starters. This would mean that my AppearanceNodes, that right now only changes textures, would have a BV, although it doesn't have a world position. That doesn't seem optimal.
2.
---------
Also, my scenegraph has no spatial hierarchy of any kind right now, and it will probably never have that for this 2D game i'm making atm.
All my SGManager-class can do right now is optimize the number of texture-switches. (Basically to put all my Enemies with the same texture under the same AppearanceNode. It doesn't matter how far from eachother they are, or anything like that)
I see that hierarchial BVs can be useful for culling. (If you cull something, you cull all its children aswell, because they are contained within the parents BV, right?) But then i would need a spatial SG.
Right now i can't even see how i can build my scenegraph spatially, but there's probably loads of info on spatial SGs out there.
Perhaps for my game it would be best to let all my LeafNodes have a BV in world coordinates? What do you think? Btw, the game is a 2D Space Shoot 'em Up à la Gradius, and i intend to use BVs for collision dection.
The CD is of this type: Ship hits Ship. Bullet hits Ship. and so forth...
1.
---------
But you suggest that all SG Nodes of any kind has its own BV in world coordinates, for starters. This would mean that my AppearanceNodes, that right now only changes textures, would have a BV, although it doesn't have a world position. That doesn't seem optimal.
2.
---------
Also, my scenegraph has no spatial hierarchy of any kind right now, and it will probably never have that for this 2D game i'm making atm.
All my SGManager-class can do right now is optimize the number of texture-switches. (Basically to put all my Enemies with the same texture under the same AppearanceNode. It doesn't matter how far from eachother they are, or anything like that)
I see that hierarchial BVs can be useful for culling. (If you cull something, you cull all its children aswell, because they are contained within the parents BV, right?) But then i would need a spatial SG.
Right now i can't even see how i can build my scenegraph spatially, but there's probably loads of info on spatial SGs out there.
Perhaps for my game it would be best to let all my LeafNodes have a BV in world coordinates? What do you think? Btw, the game is a 2D Space Shoot 'em Up à la Gradius, and i intend to use BVs for collision dection.
The CD is of this type: Ship hits Ship. Bullet hits Ship. and so forth...
Quote:Original post by SimonTheSorcerer
yes, this was quite a mouthful for me. I understand most of it, but since this is my first attempt at a simple engine, some of this is over my head right now.
if your interested then check this for better understanding of most of the issues involved with scene graphs.
Quote:Original post by SimonTheSorcerer
1.
---------
But you suggest that all SG Nodes of any kind has its own BV in world coordinates, for starters.
Well no not as such, leaf node types like shape/geometry nodes have there bounding volume be in model/object coordinate space. Every BV is nested with-in it's parent's BV thus relative to it kind of like how hierarchical transforms are.
Quote:Original post by SimonTheSorcerer
This would mean that my AppearanceNodes, that right now only changes textures, would have a BV, although it doesn't have a world position. That doesn't seem optimal.
Typically you don't have world transforms as such those are computed from concatenation of transforms in the graph from root to leaf.
What is your definition of an AppearanceNode? something to do with materials? if that is the case i personally wouldn't put those in the SG itself those are more like node attributes than nodes to me, there external state that can be shared among certain leaf node types.
Quote:Original post by SimonTheSorcerer
2.
---------
Also, my scenegraph has no spatial hierarchy of any kind right now, and it will probably never have that for this 2D game i'm making atm.
All my SGManager-class can do right now is optimize the number of texture-switches. (Basically to put all my Enemies with the same texture under the same AppearanceNode. It doesn't matter how far from eachother they are, or anything like that)
I see that hierarchial BVs can be useful for culling. (If you cull something, you cull all its children aswell, because they are contained within the parents BV, right?) But then i would need a spatial SG.
Right now i can't even see how i can build my scenegraph spatially, but there's probably loads of info on spatial SGs out there.
If you have transforms in a scene graph then you have spatial information within it, having nested BVs is like bounding volume hierarchies (BVH), BVHs are not spatial partitioning structures (like BSP/Octrees) they are object partitioning and that is what SGs are object partitioning so they can go well together.
The main reason for doing this is not for complete HSR or CD solution or replacement although it can be used for those most of the time it depends on the context, the main reason is to prevent redundantly traversing/iterating the entire scene for the majority of operations you will preform on the SG. It takes you from O(N) to ~O(log N) for some operations you'll do.
It's not that i am fond of it but it's something that is done in some SG APIs.
Quote:Original post by SimonTheSorcerer
Perhaps for my game it would be best to let all my LeafNodes have a BV in world coordinates? What do you think? Btw, the game is a 2D Space Shoot 'em Up à la Gradius, and i intend to use BVs for collision dection.
Yeah it might be fine for what you are doing it might be worth looking into loose quadtrees later on though.
Quote:Original post by SimonTheSorcerer
The CD is of this type: Ship hits Ship. Bullet hits Ship. and so forth...
Read about multimethods and/or visitor pattern unless the language you are using already supports multimethods [wink].
Author
Quote:Original post by snk_kidQuote:Original post by SimonTheSorcerer
yes, this was quite a mouthful for me. I understand most of it, but since this is my first attempt at a simple engine, some of this is over my head right now.
if your interested then check this for better understanding of most of the issues involved with scene graphs.
I've read a few of those. Seems like i could benefit from reading some more :)
Quote:Original post by snk_kidQuote:Original post by SimonTheSorcerer
1.
---------
But you suggest that all SG Nodes of any kind has its own BV in world coordinates, for starters.
Well no not as such, leaf node types like shape/geometry nodes have there bounding volume be in model/object coordinate space. Every BV is nested with-in it's parent's BV thus relative to it kind of like how hierarchical transforms are.
Hmm, i'll probably have to look into this aswell...
Quote:Original post by snk_kidQuote:Original post by SimonTheSorcerer
This would mean that my AppearanceNodes, that right now only changes textures, would have a BV, although it doesn't have a world position. That doesn't seem optimal.
Typically you don't have world transforms as such those are computed from concatenation of transforms in the graph from root to leaf.
What is your definition of an AppearanceNode? something to do with materials? if that is the case i personally wouldn't put those in the SG itself those are more like node attributes than nodes to me, there external state that can be shared among certain leaf node types.
Yes, my definition of an AppearanceNode has to do with materials. So all it would do is gl-StateChanges i think. (as i said, right now all the node does is change texture when you pass it in the scenegraph)
Quote:Original post by snk_kidQuote:Original post by SimonTheSorcerer
2.
---------
Also, my scenegraph has no spatial hierarchy of any kind right now, and it will probably never have that for this 2D game i'm making atm.
All my SGManager-class can do right now is optimize the number of texture-switches. (Basically to put all my Enemies with the same texture under the same AppearanceNode. It doesn't matter how far from eachother they are, or anything like that)
I see that hierarchial BVs can be useful for culling. (If you cull something, you cull all its children aswell, because they are contained within the parents BV, right?) But then i would need a spatial SG.
Right now i can't even see how i can build my scenegraph spatially, but there's probably loads of info on spatial SGs out there.
If you have transforms in a scene graph then you have spatial information within it, having nested BVs is like bounding volume hierarchies (BVH), BVHs are not spatial partitioning structures (like BSP/Octrees) they are object partitioning and that is what SGs are object partitioning so they can go well together.
The main reason for doing this is not for complete HSR or CD solution or replacement although it can be used for those most of the time it depends on the context, the main reason is to prevent redundantly traversing/iterating the entire scene for the majority of operations you will preform on the SG. It takes you from O(N) to ~O(log N) for some operations you'll do.
It's not that i am fond of it but it's something that is done in some SG APIs.
Geez, seems like i have a lot to learn :) I thought BVH's would primarily be used for HSR or Object-Culling (don't know if they're exactly the same thing).
What (if any) is the difference between nested BV's and BVH's? Seems like i should read up on object partitioning and how nested BV's can help with traversing the SG (i can only think of object-culling).
Right now, i traverse (almost)the whole SG for Rendering. The only other operation i have atm is Blending.
During my Render-pass i skip BlendNodes.
And during my Blend-pass i skip AppearanceNodes if i haven't already passed a BlendNode.
It's not any more advanced than that :D
Quote:Original post by snk_kidQuote:Original post by SimonTheSorcerer
Perhaps for my game it would be best to let all my LeafNodes have a BV in world coordinates? What do you think? Btw, the game is a 2D Space Shoot 'em Up à la Gradius, and i intend to use BVs for collision dection.
Yeah it might be fine for what you are doing it might be worth looking into loose quadtrees later on though.
Yep, those might be worth looking into.
Quote:Original post by snk_kidQuote:Original post by SimonTheSorcerer
The CD is of this type: Ship hits Ship. Bullet hits Ship. and so forth...
Read about multimethods and/or visitor pattern unless the language you are using already supports multimethods [wink].
Programming Language: C++ (Cplusplus)
I did actually hit quite an obstacle with the CD (which i'm working om atm).
i found a solution in the book "More Effective C++" (Cplusplus) at
"Item 31: Making functions virtual with respect to more than one object."
It helps me determine the sub-classes of two "GameObjects" that have collided. (i need the game to behave differently for different kinds of collisions.. Ship-Ship, Ship-Bullet etc) i think the whole problem of this sort is called Double-Dispatching.
the best solution was something like building vtbl-like arrays of function-pointers. Also keeping these functions, not as members of any of the "GameObjects", but having a separate "Manager" who has those functions so that "GameObjects" won't have to be recompiled every time you decide to add a new "GameObject" to your game. (i won't go into any more specs now)
Do you think multimethods or visitor-patterns are a better solution than this one?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
