Simple scene graph in 2D, without matrices?

Question

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.

Answer 1

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.

Answer 2

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?