# Simple scene graph in 2D, without matrices?

First of all, I think I roughly know how a scene graph works. Please correct me if I'm wrong.

It is a tree based structure, with each branch/leaf being a node. It means you can better organise children, like tyres on a car or something. I want to use a simple version of it, which makes me think matrices, but the graphics API I'm using (SFML) doesn't allow them. I would use GL here, but the project has to be done in a reasonable time frame.

Instead, I only have the ability to set 'absolute' window coords by default. Without anything, it would be something like:
 carBody.position(10,10); carWheel1.position(9.5f, 8.7f);//etc. I think that's a badly placed wheel. :P 

How could I go about this? Have each object/renderable thing/entity be a node, obviously, but then how would I handle position changes? I would think passing down the branch, somehow.

Is there some kind of tree structure in the STL containers? Would I have to make my own?

There's one other thing that's hit me. Is all of this overkill? All I really need is some way to control more of 'local' positioning, which this does, but this seems OTT for what I need. So it's sort of organization + positioning vs the sheer complexity for a 2D side scroller.

If you need to support rotation or scale of parent nodes I would use matrices. Even if they're not supported you can implement them yourself. If not, you could just, upon rendering, add the local translation to the parent node's translation? Transfer the tree from the top, when you enter a child you add it's translation, when you go back to a parent you either subtract it again (bad, as you will get small errors adding up) or restore the previous translation (use a stack and push the current translation when you go into a child, and pop it when you return.
I don't know if there's a tree structure in STL, but you can just use any vector and store the index of the first child of a node, and the index of the next sibling of a node. You can then traverse the tree by starting at the root, and do
If (firstChild) push translation - visit child; pop translation
If (firstSibling) visit firstSibling
This will do a depth-first traversal.

• That sounds great, thanks. One thing; how would the local position be handled? i.e. Would it be easier to treat each parent as a separate screen, sort of like in the car example, have wheel have a position of 200,400 or something? The local position is the bit that's got me confused. Aug 10 '10 at 19:23
• If there is no scale or rotation involved then you can just add the local position to the parent's global position, but your local position have to be in the correct scale. Does that answer your question? As I am not quite sure what you're asking. The parents can all live in the same screen, just give them one common parent (sceneroot) with translation (0,0). Changing the translation of sceneroot will move your whole world around.
– Kaj
Aug 10 '10 at 19:26
• No, I feel I badly worded it. Sorry. What I meant was I was asking a good way to handle the local positions; if I have a 2d car with a position of 100,100 for the top left and a length of 100, would a wheel have a position of 20,20 locally, or would it have a position of 200 locally, and keep the 'local' at a same sort of scale as the global? I really am not doing well at getting a point across, and I don't want to edit the question because it'll mess up answers. Aug 10 '10 at 19:28
• Since you don't incorporate scale I would define local offset in global coordinates. So if you want the wheel to be 50 pixels to the left of the center of the car, and 20 below, I'd give it a position of (-50,20). If you want to incorporate scale I'd always consider the parent size to be 1.0 by 1.0 and have the local coords adjusted to that (like -0.5, 0.2) but it would make it harder to place pixel art so I'd go for the former (global coord system for local objects), especially since it gets tricky if you go deeper than one level.
– Kaj
Aug 10 '10 at 19:40

Matrices are the 'right' way to approach this - but if you really can't use them, you can still create a hierarchy of nodes (as a tree) and do something along the lines of:

scale    = parent_scale    * local_scale
rotation = parent_rotation + local_rotation
pos      = parent_pos + rotate( parent_rotation, local_pos )


(Where positions are 2D vectors, rotations/scales are scalars, and 'rotate' rotates a position vector by a rotation angle)

As you would with matrices, do a depth-first traversal of the hierarchy to update pos/rotation/scale of each node before rendering

However, without matrices, I think you'll struggle to handle non-uniform scaling?