RE: [Algorithms] object oriented scene graph traversal

[Stefan B. <ste...@te...>]

> My First Weird Decision is to make arcs first-class objects. Nodes never
> contain pointers (in the C sense) to other nodes, but only
> pointers to arcs.
> 	- to provide a point of indirection for loading scenes over
> the network (functionality)
> 	- to allow lazy evaluation of inter-object references (performance)
> 	- to separate inter-object reference semantics from node semantics
> (simplicity)

  Interesting. I have something similar, but effectively in the reverse. In
my scene graph design (inspired by XSG), the interior nodes are typically
all of the same class (XInteriorNode), but can have a "core" node plugged
into it (or a chain of cores, even). The core node modifies the traversal
behaviour, so f.ex. instead of having a dedicated transform or switch node,
we have an interior node with a "Matrix" core or "Switch" core plugged into
it.

       Traditional:

        +-------+                   +--------+    +------+
        | Xform |                   |Interior|<---|Matrix|
        +-------+                   +--------+    +------+
       /    |    \                 /    |    \
 +----+  +----+   +----+     +----+  +----+   +----+
 |Geom|  |Geom|   |Geom|     |Geom|  |Geom|   |Geom|
 +----+  +----+   +----+     +----+  +----+   +----+

  This simplifies and enables you to do a lot of things, but it's kind of
hard to describe everything here. To take one example, imagine having a
scene graph describing a number of different levels-of-detail of a car.
During the game you will want to update the scene graph to rotate the
wheels. Now if you had a graph where the interior nodes themselves stored
the matrix as well as the child node list, you would have to update ALL
transform nodes in each level-of-detail subgraph. Using the plug-in approach
instead, you would only have one transform plugged into all LOD instances,
so you would only have to poke the rotation matrix into one place, without
caring which LOD subgraph is picked at traversal time.

  This is, I think, similar to what you have done -- only different :). The
interior node objects typically only describe the topology and bounding
volumes of the graph, with geometry at the leaf nodes and behaviour
modifiers ("cores") plugged into the interior nodes.

  I don't allow cycles in my scene graphs though. I keep separate node
graphs for higher-level culling and visibility purposes. I like to keep my
graphs "clean" and single-purpose.

  Another thing you may want to look at is using a more generic dispatch
system rather than having virtual functions (I'm assuming that's what you
are doing now) on the nodes themselves. By separating behaviour from data
you gain a lot of power. I use a Action/Node double-dispatch system similar
to the one used in XSG and Inventor. In my previous scene-graph prototype I
used virtual functions and it got messy real quick. I have had no such
problems with the double-dispatch approach. It works incredibly well
actually.

Cheers,
Stefan
--
Stefan Boberg, R&D Manager, Team17 Software Ltd.
bo...@te...