scene graph traversal, and node design

OpenGL Development JOGL Development
#1

gurus:

i am designing an object to walk my scenegraph, and have run into some design choices to make:

  1. what do you like more, recursive depth first traversal, or breadth first search queue style?

for anyone checking out this thread who is not familiar with these terms or what the heck i’m asking, here is a very brief summary. the tree is a data structure found many places in computing, and is central to computer grpahics. most common is the scenegraph, a structure all here are probably very familiar with. in a program using this structure, one has to design a way of traversing the tree. traversal means that the object walking the tree structure will visit each node in the tree. there are two basic ways to accomplish this: depth-first, or breadth-first. depth-first is where the tree walker uses a recursive algorithm to search down the branches until it hits a leaf node, marking each node as visited = true along the way. kind of the hanzel and gretel approach. the breadth-first approach looks at a node and all of it’s siblings, records in a list which ones need to be visited, and works it’s way through the tree, level by level. interestingly, from a mathematical perspective, both techniques are equivalent. however, implementation means everything so i wanted to ask the gurus which way they do it so i don’t reinvent the wheel. the description i’ve given is just a tad terse – about the same as saying: “the constitution says people should be free.”

for more info try these keywords: tree data structure, depth-first, breadth-first, recursive

  1. do you like one way nodes, or “smart” nodes?

it seems that some like to design nodes to be one-way, that is keeping a list of children, but being ignorant of parent or sibling. from my very limited understanding, this is the essence of the tree data structure. when you keep track of the parent of a node, you can achieve a graph structure ( a more complex and general structure related to a tree ). i like to think of a node that know’s who it’s parent is as “smart.” when working with xml in the past, i often have worked with these kinds of nodes. they usually keep track of something like this: children[], firstChild(), lastChild(), siblings[], parent() – whereas a one-way node only knows of it’s children. typically, i try to make my objects as “dumb” as possible – they don’t know anything about the world around them – they are encapsulated bubble boy objects. sometimes however, it makes sense for objects to know a little about their environment: is this one of them?

so gurus, what kind of nodes do you use? is there some intrinsic benefit to the node-style you like?

#2

Ok, I’m no guru, but here’s my opinions none-the-less:

If you are designing a scenegraph, then most probably you will be concerned about culling large parts of the graph when possible, eg: the traditional quad-tree terrain where if your camera is facing east, and you are east of the midpoint, you can instantly discard 2 of the 4 initial child nodes. So, you are going depth-first, and testing whether to traverse further at each node.

You’re always moving down the tree, never going up (until you exhaust the children of the current node), so by virtue of this fact you will always have access to the “parent” node. Therefore you only need one-way references to the child nodes.

#3

Another argument for one way nodes is the possibility to add a node to different parents, so you get shallow copies of graph subtrees.

#4

great stuff guys. i have also noticed that the scenegraph itself has come under disfavor with some game engine designers in that not every game object should be in them. clearly, the biggest benefit of a scenegraph is it’s ability to map state information such as transform, appearance, etc. are their game object you would keep out of the scenegraph, and what kind of data structures would you use for them?

#5

IMHO, theres a difference between graphics, and an entity system. If your looking for a graphics presentation that is optimal, a scene graph is pretty much there. If your looking at game entities, like rocks and cars that have different properties, like a car has damage, acceleration…etc while rock has nothing, then a scenegraph, or even a heirarchy approach is wrong IMHO. A component based approach is better suited, sorta like a copy/paste of the components into a game object using some data is dam attractive to me…

Follow this thread http://www.java-gaming.org/forums/index.php?topic=14022.0 and you will find interesting things about game objects, but be aware that i dont think they apply to graphics…

DP

#6

fantastic link. i spent some time looking into the component idea. it’s unbelievable how timely your link is:

i have been wrestling with this issue for a week or so now. all the books, articles, papers and source code digging, one does to tackle all the programming challenges of a game engine. so much effort. so many dead ends. no magic bullets. i think your blogger mentions this too. and the deeper i dug into the design and testbed process, the worse it got. all i could see was this endlessly growing heirarchy and a very complex scenegraph. luckily i’m not working on a game per se ( my needs are a little more humble ), but my work shares many of the same concerns. clearly, one needs a pattern or methodology able to utilize the computational, mathematical, and human-understandability benefits of a graph, while creating the freedom and complexity which autonomous components working in networks ( and together over networks ) can provide. whew. long sentence.

i have read a few papers on these component based approaches, and also some on asynchronous real time networks like COSA ( which has many similarities ) as possible methods of working. from what i gathered, the component view of development addresses two huge areas of computing: how to exploit the processing power of networked computers and how to deal with the ever growing complexity and bugginess of massive software systems. it’s no accident that this approach is found a lot in grid computing, it looks really expensive. cpu’s love heirarchy. it seems that the component model seeks to do exactly what the developer in the blog was asking for: how can i create complex behaviors out of simpler ones ( ironically a hierarchy ), in a way that will create interesting and complex capabilities for the games system. at the same time, i want to providing a high-level toolbox to use more as an artist’s palette than the programmer’s complex code library, i.e. scripting. interestingly, i ran into this topic while looking at grid-based processing systems.

to me at least, this component-view of programming smacks of something that is next generation, and is very exciting. it’s been around for a while, but it’s new territory in graphics programming. while i don’t pretend to be a CS wizard, the ideas are not hard to grasp.however, what really jumps out when you start looking at the connection models and illustrations of component systems is how foreign it is to the way people design things. the component idea itself is pretty intuitive to understand. the problem though is that while the “component” part is easy to understand, how to make them do things you want to do is not. how do you design with these things? i suspect that this is not so much a problem of the component-view, but more one of the heirarchical way humans think ( at least when we’re designing things )! when the blogger said, “you just have to change your way of thinking,” i think he was totally correct. but that’s easier said than done. this kind of technology may only become practical with the creation of languages and tools designed to translate the heirarchical approach ( we humans really seem to like hierarchy ) into complex networks of autonomous, asynchronous ( even if only simulated ) components doing wonderfully complex things. this seems to be becoming the aim of many new languages and methodologies.

if you think of truly complex engineering projects like say an aircraft carrier, clearly the component based approach is the only way to go. each object has inputs and outputs and does it’s thing. a valve doesn’t have to know anything about heads up displays on the jets, and vice versa. a scenegraph approach to building an aircraft carrier would be crazy, but it’s probably the best way to organize the drawings and plans. the challenge seems to come when applying either heirarchy or component thinking to a totally different goal than an aircraft carrier: an image. those engineers don’t have to render their world, or worry about antialiasing – they get that for free. a game engine must model both interaction and representation, a serious challenge that neither heirarchy or autonomous components seem to be 100% tailor made for. how does one blend them? how does a programmer create a system that they can have some hope of understanding or working with? more important to me, and i think to the blogger you refer to, and perhaps to you, is how do i create a system that i can be really creative with? game engines to me are about interactivity. not just for the end user, but for the mind that created it. i, the designer, want to play with the system and make it do cool things, now. if you have to create a heirarchy, i think the heirarchy tends to bleed into what you can do with it. a hierarchy disincentivises ( had to look that one up ) a fun, creative, artistic approach to make amazing interactive visuals. it’s hard for the programmer to experiment and create or even discover fun new things when you really have to plan everything out ahead of time.

i agree that when you start to really dig into the guts of some of the design and programming challenges of creating interaction and representation, you see the terrible inadequacy of today’s languages and tools. it’s not the tools fault. they just work the way we want them to. we have to figure out something new. as you can see, this really struck a chord with me. hopefully the internet-forum-crank-o-meter on my username hasn’t gone up…

so what’s a guy who needs to build a really fast cubic path renderer supposed to do? lol.

#7

While I agree with you, you will at least need one kind of hierarchy for spatial partitioning of you game world, so you can cull entities completely before they are considered for rendering. Another use for this is the suspension of AI logic for currently unseen entities and collision management.

This use of hierarchy is mostly connected to transformations or dependent animations. While there is need for them, they must not necessarily be expressed in a scene graph or an hierachical object model. Think of them more like a formula. You can easily make up a formula that produces a “hierarchical movement” (keep in mind, that english is not my native language, so you might have to correct phrases while you read :wink: ) by using other entities properties as input variables. If you want to play with the effects, you can even create a hierarchical formula builder, that allows you to interactively discover cool effects, but there is no need to use hierachies at your engines runtime.

Other visual effects that are not related to animation are nowerdays mostly based on shaders or particle engines, which don’t need an hierarchical object model at all.

#8

[quote]a scenegraph approach to building an aircraft carrier would be crazy, but it’s probably the best way to organize the drawings and plans
[/quote]
I have the feeling you think things like this are much more hierarchical than they really are. I once worked for a research instute that was investigating exactly that problem: how to manage all the information that is available when constructing large ships and buildings.

You might think there are plans that cover the entire project from the biggest level up to the tiniest details but that just isn’t true (although this was many years ago, the situation might have changed although I doubt it has changed much). There are drawings for a ship’s hull structure and there are diagrams for the ship’s engine and designs for the interior of the ship’s cabins but it is extremely unlikely you will see this information together in any meaningfull way. They might refer to eachother but that’s just about it.

It was one of the problems they were trying to resolve in the institute I talked about: in practise it happens a lot that while designing a factory for example, that when the electricians come in that they find out that the guys who put in the plumbing have already used the space they had thought they could use for their cables. The idea was that if you have one enormous information model that contains every last bit of information you could prevent that kind of problems but it turned out that making such a model is extremely difficult (and we’re not even thinking about the real world problems of convincing all the contractors to use the system!).

Yeah, this has nothing to do with 3D graphics :wink:

If there is a moral to this story it probably is: don’t try to over-design what you are trying to build. Use object trees and scene graphs where they make sense, don’t try too hard to make this one super-model that will fit everything that you’re trying to do.

#9

[quote]If there is a moral to this story it probably is: don’t try to over-design what you are trying to build. Use object trees and scene graphs where they make sense, don’t try too hard to make this one super-model that will fit everything that you’re trying to do.
[/quote]
well that’s the thing, and this addresses cylab’s comment as well, i’m trying to simplify. i’m trying to figure out how to get the maximum out of the minimum programming. also, i’m trying to reduce the overall complexity of the application so that it’s structure and behavior is more human understandable. as i mentioned, the scenegraph is perfect for storing state information ( that i need to perform graphics calculations ), and is a very good structure from a mathematical perspective for culling etc. clearly i will use a scenegraph.

but what is your approach to achieving behavior and interaction among your entitiies in the game as a whole? and how do you jump back and forth between the heirarchy and your other elements? what kind of data structures are they stored in? does anyone use a component-based approach? also, when working on the game in its entirety, do you end up creating huge inheritance heirarchies with many sub-sub-sub-classes ( that’s what i’ve run into and am looking for alternatives, or just plain design ideas )?

thanks much guys.

#10

this sounds a lot like the approach of something like maya, where one works with nodes, and nodes have inputs and attributes. the inputs and attributes can be easily redefined and connected to other nodes quickly to build up behavior and effects. interestingly, the developer blog that darkprophet referes to actually worked with an engine that was based on maya’s node connection approach. this is a very flexible approach, and i have explored implementing this somewhat. i noticed that in a system like this, there is a limit to how complex a network is before one starts to loose track of what everything does. i’m not even sure if you are referring to something like this. hopefully i’m not too far off the mark. a maya-like approach definitely is one way to couple heirarchy and components, and makes experimenting easier ( just create new inputs and outputs – a way of blending heirarchy and component-like approach ), but seems to suffer performance-wise in a real-time system. in a system like maya, they don’t have to worry about how long it takes to calculate or solve the graph. also, it tends to make everything kind of expression driven because you are coupling in a node both data organization ( the inputs and attributes ) with the calculation of those data parts in a nice, neat node package. what i mean by expression driven, is that you have to kind of think of the system more like an mechanical engineer than a designer. everything has to be thought of as a chain of calculations, which requires a lot of pre-planning.

#11

just wanted to say one thing: this topic kind of drifted a little, but this subject just struck a nerve. i tend to dislike rambling, philosophical threads on what is the ultimate language, or construct that we all see. my favorite threads are the ones that detail someone’s investigation into a problem where they post test images, benchmarks, snippets and diagrams – truly helpful stuff. i hope to contribute some of that as my application progresses.

it’s just that i’m at that spot in the process ( and i’m sure many here can sympathize because they’ve been there ) where you have done the work: you have been writing lots of code, digging out your calculus reference ( and dusting it off ), reading papers, sketching diagrams – even talking into a recorder to organize your thoughts. but after truly rolling up your sleeves you realize: what a mess this is going to be! so you slap your wrist and go back and look at what’s already out there: don’t reivent the wheel. but everywhere you look there are some great wheels – but they have five lugs not four, or are low-profile when you need off-road. so you say to yourself: “OK, you’re going to have to dig in to this.” so i’m just at that point, and so i’m looking for a guiding design principle that can get me through the really complex stuff. i just find that if there is some overarching principle that you are following – some methodology or process – that it makes getting through the nights when your program just looks like a huge mess of wires ( using an engineering metaphor, again ) just a little more sane.

cheers guys and thanks for reading my rants.

#12

Be careful tho, graphics and game entities are two entirely seperate things IMHO. Its all and well having a components based everything, but it wont help your graphics. A scenegraph is a good model for graphics because:

  1. Transformations, easy to propogate and it just makes total sense; if you were to rely on OGL’s own stack, your only guaranteed a depth of 16 pushes and pops of the modelview stack
  2. Containers, for frustum culling allow a heirarchial approach which is known to be a reliable and quick way to determining visibility (not the quickets, but still dam quick).
  3. Copies, simply attach the same object under different branches to get automagical “duplication” (although for animations, that probably wont help you much).

What ive said up there has nothing to do with the amount of fuel a jet has, or how far your hero can throw their arrow; this is purely from a technical point of view. And IMHO, a Game Entity would reference a chunk of the scenegraph tree and add components ontop of that; so really, the graphics “chunk” is a sort of special component of the game entity object.

DP