[Algorithms] object oriented scene graph traversal

[Matthew M. <ma...@me...>]

I'm (re) building a scene graph and have made some strange choices with
uncertain implications. These are partly motivated by my desire to see the
benefits of a "highly OOP" approach to a scene graph, avoiding for the
moment my knee-jerk tendency to overoptimize immature architectures. At any
rate, I ran into a thorny (and hopefully interesting) architectural decision
recently which I'd like some input on.

The basic approach:

A scene graph is a nodes & arcs data structure used for affecting rendering
state. The screen is considered to be state.

Each node in a scenegraph has any number of incoming arcs. The most basic
level of node has one outgoing arc.

Arcs are directed.

Subgraphs may be cyclic. It is incumbent upon the node to conditionalize
traversal of outgoing arcs to effect loop termination. This is where we
insert culling, including portals and octree neighbors.

Rendering is effected by calling "render" on the root of the graph, which
then recurses on the targets of outgoing arcs.

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)

This brought up an interesting issue. Since the "basic" node has a single
outgoing arc, how do we have a classic one parent/many children
relationship.

The two choices are:
	- a special type of node with multiple outgoing arcs (group nodes)
	- a special type of arc with multiple terminating nodes (multi-arcs)

The advantage of multi-arcs is that nodes don't have to support "groupness,"
simplifying their implementation. Classes designed to support a single
outgoing arc can be fitted with multiple outgoing arcs.

The disadvantage of multi-arcs is that they need to be made aware of the
rendering protocol, thereby conflating "rendering" with "connecting," two
previously orthagonal concepts.

The advantage of group nodes is that arc traversal decisions are centralized
into the node. For example, imagine a cell (as in portals and cells) that's
deciding which of its portal links to traverse. If the number of portals is
"hidden" from the cell, the logic becomes less intuitive.

For these (and other reasons,) I went with the group nodes approach, but not
without some regret for the simple elegance of multi-arcs.

The hard-core among us will, I'm sure, look askance at the cache-pessimizing
effect of having pointers all over creation. My plan for this is a
"graph-crushing" algorithm which will pack a graph into a contiguous chunk
of RAM based on a more-or-less "standard" traversal. This is extremely easy
to effect at load time. I will, however, still have to support fragmentation
and relocation for (hopefully rare) cases of dynamic graph modification.