It is currently Fri May 26, 2017 8:07 am

All times are UTC - 5 hours




 Page 1 of 1 [ 20 posts ] 
Author Message
 Post subject: GameDev VMK 21 - Scene Graph
PostPosted: Sat Dec 30, 2006 7:09 am 
Site Admin

Joined: Sun Feb 11, 2007 8:59 am
Posts: 1094
Location: Ontario Canada
The VMK21 series of videos show how to create a scene graph structure for the game engine. The concept of a node will be explained which we will use to create transform Nodes, shape Nodes and Light Nodes.


Last edited by Marek on Tue Jan 05, 2010 6:24 am, edited 1 time in total.

Offline
 Profile  
 
 Post subject: Re: GameDev VMK 21 - Scene Graph
PostPosted: Wed Jan 31, 2007 7:51 am 
Site Admin

Joined: Sun Feb 11, 2007 8:59 am
Posts: 1094
Location: Ontario Canada
As I was making VMK 22 I noticed that the math formula in VMK21d is incorrect. It is the reverse of what it should be. I also found a new bug in VMK21c. Inside the Node::FindNode(char* szName) function.

I've just finished making a short video (VMK21H) showing how to correct these two bugs.


Offline
 Profile  
 
 Post subject: Re: GameDev VMK 21 - Scene Graph
PostPosted: Mon Feb 05, 2007 7:51 am 
Site Admin

Joined: Sun Feb 11, 2007 8:59 am
Posts: 1094
Location: Ontario Canada
Note that the limit in the number of nested Transform nodes that OpenGL will support is (at least) 32. If you try to make more than that, your program will probably crash.


Offline
 Profile  
 
 Post subject: A question - Do we really need vector< Node * > later
PostPosted: Wed Oct 29, 2008 11:43 am 

Joined: Wed Aug 06, 2008 7:53 pm
Posts: 182
Location: Russia
Hi, Marek.
Would you please answer a quick question?
In this VMK we create scene graph tree. We use the class Node (and descendants) that contains four pointers. Basically, our tree is a classical (double linked) binary tree. As a matter of fact such tree has all info to store associated objects, such as Geometry.
Is there any special purpose to have additional vectors: vector< Node* > and vector< Geometry* > ?

From this VMK’s perspective these vectors are used only to alleviate the cleaning. Certainly it is a little bit easier to delete objects in plain loop than via tree-walk, but I think that is not a sufficient cause for such redundancy.
Oh, yes, we can use indices of array (std::vector) to get access to the Node and Geometry objects. But we can achieve the same using the pointers directly. I mean:
UINT holly_hand_grenade = m_pNodes->Add( New Node( ... ) );
...
m_pNodes[ holly_hand_grenade ]->Boom();

and
Node * pHollyHandGrenade = New Node();
...
pHollyHandGrenade->Boom();

do the same. The access by pointer is even slightly faster.

I'm going to rid of those vectors, because I see no point in them from the perspective of current VMK. But I'm still not positive, because I'm used to the fact that in VMKs sometimes things are being changed significantly.

So, the question - is it harmless to rid of vector< Node * > and vector< Geometry *>, or they have some special destination later on? :?

There is a popular wisdom, that if in the 1st act of a performance a decorative rifle is hanging on the wall, it must fire in the last act. :)


Last edited by BugHunter on Wed Oct 29, 2008 6:02 pm, edited 2 times in total.

Offline
 Profile  
 
 Post subject:
PostPosted: Wed Oct 29, 2008 2:34 pm 
Site Admin

Joined: Sun Feb 11, 2007 8:59 am
Posts: 1094
Location: Ontario Canada
I use the vector< Node * > and vector< Geometry *> a little later on when parsing Caligari files. I think I pass the vector<Node*> to some other place too .... oh yes I remember now. Something I did for work, but that has not showed up in the VMK's (yet).

These vectors and the ones to store lights, materials, textures, texture transforms, are there so I can quickly search for things, without having to traverse through the tree. Oh, btw, the scene graph is not a binary tree. It is an n-ary tree since you can stuff as much as you like per node.


Offline
 Profile  
 
 Post subject: Thank you + two gifts encoded in the answer :)
PostPosted: Wed Oct 29, 2008 6:01 pm 

Joined: Wed Aug 06, 2008 7:53 pm
Posts: 182
Location: Russia
Thank you Marek for response. Searching per se is a good reason to have parallel structures, although it takes additional time and space to support them.

I also noticed that we can keep the textual name of the node not inside the node but separately, for instance in std::map< TCHAR*, Node* > to get fast access to the node. But this has a sense only if the search by name is a frequent operation.

Btw, one useful function for us is called _strdup( const char * str ). It effectively duplicates the string. Don't forget to return the memory back to the system later on – call “free()”. _strdup() is a good replacement for the code that is far too frequent in VMKs:
void foo( const char * pszString ) {
    ...
    if ( !pszString )
        return;
    m_pszName = new char [ strlen( pszString ) + 1];
    strcpy( m_pszName );
    ...
}

// in dtor:
SAFE_DELETE( m_pszName );

Now we can write:
void foo( const char * pszString ) {
    ...
    m_pszString = _strdup( pszString );
    ...
}

// in dtor:
free( m_pszName );

If one has the source of compiler's CRT it is possible to look at the internals of _strdup(). It does exactly the same as the former code ( strlen() + allocating the memory ).

Back to the roots:
It is obvious that the search in a tree (unsorted by given attribute) is as slow as in a plain array, notably linear, i.e. C * O(N). But the constant C is bigger for trees than for arrays due to higher housekeeping overhead (recursive search in a tree uses the stack etc).

That is a little bit academically, but from the base class Node {} standpoint scene-graph is exactly 2-ary tree (bin-tree) since we have only two pointers to the children (theorists call them left and right child). Yes, if any descendant of the class Node has at least one additional pointer Node* we don't have bin-tree any more. Right now I know only two descendants: NodeTransform and NodeShape and both of them don't have additional pointers of the type Node*. (Pointers to the data are not counted).
Anyway, to relax we can recall that there is a possibility to encode any n-ary tree as binary tree.
http://en.wikipedia.org/wiki/Binary_tree
8)

Besides all that grunt of mine I would love to present to everyone a very entertaining article:
«Optimization: Your Worst Enemy»
http://www.flounder.com/optimization.htm
I've read it first five-something years ago and recently found it again by mere chance. And every time I'm reading it touches something deep in my inveterate programmer's soul. That is a genuine detective story for all of us. :)


Offline
 Profile  
 
 Post subject: vectors, maps, trees, and hashish
PostPosted: Sat Nov 15, 2008 4:45 am 

Joined: Wed Aug 06, 2008 7:53 pm
Posts: 182
Location: Russia
Working on VMK 21 I have discovered another good reason to have dedicated vectors (for geometries, texture-transformations etc). This architecture solution makes it easy to share stuff between different nodes, effectively solving the ownership problem. Additionally, this sharing opens interesting and powerful possibilities. First, we save memory not duplicating equivalent objects (i.e. one geometry house object but many virtual instances of it on the scene). Second, the modification of one shared object is immediately reflected in each place when it is used.

Ok, Marek, now a question. I have mentioned above that it may worth to add a map< char *, Node *> for fast access to the node by name. Or we can exploit boost::unordered_map (e.g. hash map). As we know map means O(log N), hash O(1), and current walk-tree is O(N). But right now I just don't know how often we are going to use the access to the arbitrary node by name. If it is something marginal, i.e. mainly for case studies, I would leave walk-tree. But if in full fledged simulator it is the main way to reach the nodes, then it worth to be optimized (map or hash map). What do you think?



_________________
«Computer scientists deal with algorithms that you may call practical in theory but unpractical in practice.» © Timothy Gowers
Offline
 Profile  
 
 Post subject:
PostPosted: Mon Nov 17, 2008 6:00 am 

Joined: Sat Jun 23, 2007 7:56 pm
Posts: 145
It would be best not to continually search for nodes during runtime.

Say your scene has a specifc node for an object which you want to keep updating and checking each frame, then it's better to do the searching at load time and save a reference to it.

The engine can then perform the calculations for the whole scene.
However,you can add support to the engine to give back a list of node that a specific event effect e.g a list of nodes in a collision. That way you don't need to go looking for them.

I think searching the tree for nodes is based on an applications needs.


Offline
 Profile  
 
 Post subject: Re: vectors, maps, trees, and hashish
PostPosted: Mon Nov 17, 2008 8:23 am 
Site Admin

Joined: Sun Feb 11, 2007 8:59 am
Posts: 1094
Location: Ontario Canada
BugHunter wrote:
Ok, Marek, now a question. I have mentioned above that it may worth to add a map< char *, Node *> for fast access to the node by name. Or we can exploit boost::unordered_map (e.g. hash map). As we know map means O(log N), hash O(1), and current walk-tree is O(N). But right now I just don't know how often we are going to use the access to the arbitrary node by name. If it is something marginal, i.e. mainly for case studies, I would leave walk-tree. But if in full fledged simulator it is the main way to reach the nodes, then it worth to be optimized (map or hash map). What do you think?


I find myself creating a reference pointer (as codeslasher suggested) to any nodes that I use often in my applications. This way I don't need to do a search to find what I need. The search method that I implemented is recursive so you also don't always have to start your search at the root node. If so example, you are looking for the right finger of a character, and you already know where the characters root node is, you can just start from there and search only his hierarchy rather than having to search the entire scene graph each time.

Now if you are building a generic game engine that you want to distribute without source code, then you may have no choice but to implement some sort of O(log N) sorting/searching technique to be able to get at the appropriate nodes in the scene. It really depends on the application that you are making.


Offline
 Profile  
 
 Post subject: "Ignoramus en ignorabimus"
PostPosted: Thu Nov 20, 2008 7:08 am 

Joined: Wed Aug 06, 2008 7:53 pm
Posts: 182
Location: Russia
Thanks for your opinions and elucidations. I’m going to stay with "search tree by name" method anyway (since it has a nice property to work with sub-trees) and will add something else if I meet a real need to faster access. Agreed that the fastest way is direct referencing. However there might be the cases when we do not have such luxury (I think about 3d files parsing, scripts loading, designers soft with human readable names for objects etc).
PS. consider C declaration:
double trouble;



_________________
«Computer scientists deal with algorithms that you may call practical in theory but unpractical in practice.» © Timothy Gowers
Offline
 Profile  
 
 Post subject: About Scene::AddNode()
PostPosted: Mon Jan 05, 2009 5:26 pm 

Joined: Sat Aug 16, 2008 7:58 am
Posts: 447
As I am writing this function, I can not see the rest of the ErrorMessage()s
Could you let me know what the ErrorMessages Are. I think it is VMK 21h or 21i. Thank You


Offline
 Profile  
 
 Post subject: Node as point at issue! Redundancy or Too Much pointers.
PostPosted: Tue Jan 06, 2009 4:00 pm 

Joined: Wed Aug 06, 2008 7:53 pm
Posts: 182
Location: Russia
Hi Marek and all guys & gals.

I desperately need to discuss the following issue. I've noticed that each Node has got one and only one active pointer to the parent, either m_pOut or m_pPrev, but not both (if, say, m_pOut points to the parent then m_pPrev = 0 and vice versa).
AFAIK the classical bin-tree node looks like this:
class Node {
    Node * parent;      // now two pointers play this role: m_pOut & m_pPrev
    Node * left_child;  // m_pNext
    Node * right_child; // m_pIn
};

/// font should be monospace for correct arrangement ///

  CLASSICAL NODE        |        HOPEFUL MONSTER (?)
                        |
                        |        parent    parent       
      parent            |        pPrev     pOut                 
        |               |          \        /           
        |               |            \    /     
    +---+----+          |          +---+----+           
    |  NODE  |          |          |  NODE  |           
    +--------+          |          +--------+           
      /    \            |            /    \             
    /        \          |          /        \           
   left      right      |         left      right       
  child      child      |        child      child       
  (pNext)    (pIn)      |        (pNext)    (pIn)       


Each node has only one parent and it does not matter for the node per ce, whether it is left or right child. If necessary it can be figured out quickly:
inline bool Node::IsRoot() const {
    return NULL == parent;
}
inline bool Node::IsLeftChild() const {
    return IsRoot() ? false : parent->left_child == this;
}
inline bool Node::IsRightChild() const {
    return IsRoot() ? false : parent->right_child == this;
}


I beg of you Marek answer my question:
Isn't it enough to have only one pointer to the parent node (therefore, shall we rid of redundancy having two pointers to the parent node instead of one)?


The reason why I'm anxious about this is as follows (this is not only about extra space). I discovered that it could be useful to add the rollback functionality in Scene Graph, e.g. an ability to restore the state of the scene which it had prior to some certain action, i.e. parsing procedure and the like. In case some irreversible error occurred during the parsing (i.e. user's lvl-file was ill-formed), we could restore the previous state (rollback) instead of terminating the program. For restoration we only need to remember the sizes of the vectors (material, lights, geometry etc). But to restore tree (scene-graph) state we additionally need to assign NULL to the pointers of the parents of being deleted child-nodes.
When I was thinking/implementing the details of rollback procedure, I have noticed the redundancy (if my conjecture is correct).

What is Hopeful monster


Last edited by BugHunter on Wed Jan 07, 2009 1:51 am, edited 2 times in total.

Offline
 Profile  
 
 Post subject:
PostPosted: Tue Jan 06, 2009 5:31 pm 
Site Admin

Joined: Sun Feb 11, 2007 8:59 am
Posts: 1094
Location: Ontario Canada
Your question goes back to what I way saying earlier on the forums about the scene graph not being a binary tree. I don't remember if I was talking to you or some other member about this.

The way that the scene graph is designed in the VMK's, you can have multiple children under one parent. Not just two as in a binary tree. Because of this we end up having extra pointers.

Please refer back to VMK 21G for an image and description of how the original scene graph is constructed.

http://www.marek-knows.com/downloadSect ... #GameDev43


Offline
 Profile  
 
 Post subject: This time ... about the link(s) to the parent-Node
PostPosted: Wed Jan 07, 2009 1:50 am 

Joined: Wed Aug 06, 2008 7:53 pm
Posts: 182
Location: Russia
You right, it was me, and the discussion came about in this branch (posts at Oct 29, 2008 7:43 pm, Oct 29, 2008 10:34 pm, Oct 30, 2008 2:01 am).
I am fully agreed that if we have more than 2 children under one parent it is 100% n-ary tree (1 child => list; 2 children => bin-tree = 2-ary tree; N childred => N-ary tree). OK, blow the type of the tree! ;)

This time I am speaking not about the quantity of child-Node links, but about parent-Node links, or to be specific, about the fact that above any Node we are allowed to have 1 and only 1 parent => one link to the parent, whereas our Node has two links to (the same) parent: m_pPrev and m_pOut. This is the difference. My question/suggestion is that we can leave only one pointer!

No insult was intended (e.g. "Hopeful Monster" is just standard term of evolutionary-biology and an interesting conception, maybe fallacious). I just want to better understand stuff, and / or share some curious detections.


Offline
 Profile  
 
 Post subject:
PostPosted: Wed Jan 07, 2009 7:44 am 
Site Admin

Joined: Sun Feb 11, 2007 8:59 am
Posts: 1094
Location: Ontario Canada
You can delete one of these pointers however you'll need to restructure the way that the tree is constructed in memory and how you can traverse the scenegraph.

As it is now, when you are at any node, you can quickly determine if this node has any siblings by looking at the next and previous pointers.

If you delete the previous pointer and only keep the out pointer then that means that each node will not know about their siblings, only about their parent. I then assume that each parent would keep track of how many children they have. In that case, if you would like to traverse backwards through the tree, you would need to know which child (id) you are, go to the parent and ask the parent to return to you child (id - 1).

If you plan on implementing the code this way, then you might as well get rid of the next pointer as well, that way you can do the same search code when trying to traverse forward OR backward through the tree.


Offline
 Profile  
 
 Post subject: that gives a new turn to the situation
PostPosted: Wed Jan 07, 2009 11:00 am 

Joined: Wed Aug 06, 2008 7:53 pm
Posts: 182
Location: Russia
Quote:
... when you are at any node, you can quickly determine if this node has any siblings by looking at the next and previous pointers...
Nice, this does make sense, as far as such functionality is useful in the sequel. I do agree that without both pointers (prev and out) we can’t determine easily how many siblings are under some mother-node (same about back traverse).

Quote:
If you plan on implementing the code this way, then you might as well get rid of the next pointer as well...

Oh, no. In no way this is in my plans, since if we deleted both pPrev and pNext, we would degrade to the (double-linked) list. I’m absolutely happy with the tree structure ( bin-tree :P ).

The last question is about ROLLBACK functionality in the Scene (this is more relevant at VMK31 and below). Do you find it useful anyhow?
(The idea, again, that if in the middle of the parsing, when some objects were created and added in the containers already, we encounter a fatal error, we can then restore the state of the scene, as it was before the parsing was started, if punctually delete what was created).

Thanks for response.


Offline
 Profile  
 
 Post subject:
PostPosted: Wed Jan 07, 2009 11:11 am 
Site Admin

Joined: Sun Feb 11, 2007 8:59 am
Posts: 1094
Location: Ontario Canada
A roll back feature would be nice however in a real game situation, if there is something wrong with the scene graph you will not want to continue onward anyway since the game will be corrupt (missing pieces). It would be better to gracefully terminate the program and display some error code so that the problem can be fixed.


Offline
 Profile  
 
 Post subject:
PostPosted: Wed Jan 07, 2009 11:20 am 

Joined: Wed Aug 06, 2008 7:53 pm
Posts: 182
Location: Russia
Yup, I'd say so! But for some viewer app it might be still useful.


Offline
 Profile  
 
 Post subject:
PostPosted: Tue Jan 05, 2010 3:25 am 

Joined: Fri Sep 04, 2009 3:24 am
Posts: 30
I just want to make sure I understand this...

Your using 2 double-linked lists for the node?

The first one, m_pNext, m_pPrev is a normal double-linked list and corresponds to the Y-axis.

The second one, m_pIn, m_pOut is the same, but corresponds to the X-axis.

So in essence, you have a grid and depending on where you're at in either list, tells you where you're at in the grid?


Offline
 Profile  
 
 Post subject:
PostPosted: Tue Jan 05, 2010 6:19 am 
Site Admin

Joined: Sun Feb 11, 2007 8:59 am
Posts: 1094
Location: Ontario Canada
Sure, you can think of this as a grid. The advantage of using linked lists rather than a 2D array to represent the "grid" is that you save some memory (since most of the grid will be empty when you have a lot of nested nodes) and inserting nodes will be faster if this would cause the grid to be reshuffled to make room for a specific node branch.


Offline
 Profile  
 
Display posts from previous:  Sort by  
 Page 1 of 1 [ 20 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Jump to:  

cron