1
\$\begingroup\$

So I'm trying to getting to grips with using Scene graphs and nodes in my code (game coding in C++) and I think I understand the basics of them and how they are used (and I can definitely see the benefits), but I'm coming across the term "Graph Edge" and I can't find any reading material explaining exactly what they are and how they fit in with Scene Graphs/trees/nodes in object hierarchy structures.

If anyone knows of any good material or has their own answer on what graph edges are and how they fit in (in use and implementation) that would be great.

Thanks

\$\endgroup\$
  • \$\begingroup\$ "Graph" refers to a relationship of "nodes" and "edges", usually drawn as circles and connecting lines, respectively. An edge goes between exactly two nodes, and for a scene graph is usually "directed", meaning which end is at which node makes a difference. Nodes and edges can each hold some settings & information. \$\endgroup\$ – david van brink Jan 28 '15 at 17:59
1
\$\begingroup\$

You probably don't need to worry about the edge concept explicitly, in scene graphs.

Any time that a parent object in the scene graph holds a reference to one or more children, that reference (pointer) is itself the connection that would be termed an "edge". It it is likely that the child also holds a reference back to the parent. These are just pointers. Being a trivial connection, we need no additional information in the connection other than the target it points to. So a pointer alone suffices.

This is very different from graph applications such as often used in planning utilities networks, which seek the most cost-effective paths across a graph; see MSTs for more. These sorts of graphs require explicit edge information... in this case, edge weights representing (monetary) cost. Nodes are usually explicit in code, as represented by a class or struct (a block of memory). Edges OTOH are usually implicit for the reason described above.

Be aware that with explicit nodes and implicit edges, a path across a graph might be node->node->node; this is compact. When both nodes and edges are explicit, the same path would be node->edge->node->edge->node. This latter form increases the number of memory jumps (the arrows) to get from first to last node, increasing the chance of a cache miss. So unless you explicitly need edges, just reference one node from another, keeping memory access tight.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the reply. Some of the systems I'm having to look over and maintain have base classes for graph node as well as graph edges so am guessing they are using explicit edges \$\endgroup\$ – unknownSPY Jan 29 '15 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.