Scene Graphs

Scene Graph hierarchy is an absolute necessary method for organizing data in any sort of program that uses rendering. Actually its not that necessary, I mean you could totally use some sort of tree hierarchy or heck. In my first few games, i am pretty sure our objects were just stored in an array for sorting, But believe me that is bad.Now let me explain to you why that was bad, and scene graphs are good!so.. what exactly is a scene graph?As I said before it is a data structure that organizes data using a child to parent hierarchy. so you would start with a root node and all subsequent objects would be attached to the root node and act according to the behavior of that root node. It is essentially the same as an n tree but the scene graph updates before it traverses to the next node of the scene graph. before we get too far in. lets look at why a scene graph is useful..One of my recent homework questions involved making a scene with a solar system, where all the planets rotate the sun at the appropriate rotation and orbit speeds, and moons rotate the planets. Without the use of scene graphs this would have potentially been a nightmare, involving complex Newtonian physics based functions, and obscure movement functions for the moons.however by using a scene graph, we could just make the moons rotation relative to its parented Node. heres a diagram to help me explain.as you can see the Star (or the sun) would be the root node which manages all of our matrices. you would then want to attach a child node to the star which rotates it around the star at a certain translation. there is another option to add another child node to this with no translation, this will make the planet rotate in its place as well as around the star. now we just need to make the moon nodes as children of its planets node with a certain translation and rotation around its parent. thus creating a system where we don't need to do any serious physics calculations to approximate this behavior. the grate thing is if you want a planet to exhibit a certain behavior, you need only to add a node which emulates that behavior and attach it to the correct parent, (ie a wobble or an axis rotation)Implementationthe coding for the most basic of scene graph hierarchies is quite simple. all you really need for it to have is an addChild function and removetParent function; (for a very limited but workable functionality) don't even worry about Cartesian coordinates, textures and geometry right now.so our class may look like thisClass Node{public Node(const char* nodeName){: m_name(a_nodeName)}void AddChild(Node childNode){m_children.pushback(childNode);childNode->m_Parent= this;}void RemoveChild(Node* childNode){if(NULL!=childNode && m_Children.empty()){for (int i = 0, i <m_Children.size(); ++i){if(m_Children[i]==childNode) {m_Children.erase(i);}}}Node* m_Parentstd::vector <Node*> m_Childrenconst char* m_Name;}Here we use alot of powerful functionality from the std<vector> library to help use manage our nodes, such as erasing and getting the size.on top of this however you will probably want  an update function a getParentNode and setParentNode, among other things to make our code more robust and usable.Some other uses.When it comes to computer graphics there are so many different components that you need to keep in mind, here are a few things that nodes can handle for you to help keep things a little more organisedGeometrythe bare bones of 3D graphics, you can store all your objects into a node and then make them children of the root node, similar to how I did for the solar system.Degrees of Freedomthis is more for organization but I find that to be a huge help, this type of node will allow you to specify a transformation, rotation or scale, to any of its child nodes. it is just nicer to do this in a different node than the one in which we draw our geometry.AnimationAnimating is usually where things get real tricky, so I will start of simple. You can easily animate using the Degrees of Freedom nodes, and just updating between changing that information, but that makes for very some not-so-smooth animations that look rugged and super lame.so we can add things like an interpolation function that fills in the blanks between our transforms, and makes things look pretty. this will more than likely include, time stamps and Cartesian coordinates for values in the nodes.Switchthis is a clever way to use nodes, and the best way to think about it is like AI behaviorssay you have a base AI behavior as your parent node, but then it has multiple children that observe different variables from our scene like; character location, character health, enemy health, obstacle location etc. and based on these it can either switch or( if you are suuuper fancy) interpolate, between its children.Now this list is by no means exhaustive, I can think of tonnes more uses that a scene node hierarchy could have like particles and camera behaviors, and collisions and... well we could actually sit here all day talking about more ways to take advantage of nodes but the point is they are a very useful way to render your scene and a much more efficient data structure for organizing a it than say an array (lol). Hopefully this serves as an underlying understanding of what those different uses may be, and also remember that the more functions you include in the Node class the more uses you can potentially get out of it. (other than add and removing children)