 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Understanding and Implementing Scene Graphs |
|
 |
INVERSED Member since: 8/18/1999 From: Annapolis, MD, United States |
|||
 Posted - 12/21/2003 8:35:01 PM |
||||
| I'm curious, how does one implement a scenegraph in conjunction with a complex shading and material system. The shading and material thread has gotten me all geared up to do a flexible shading system, but that seems to be sorted on shaders while a scenegraph is sorted by transforms. How do you bring the two together without wasting a ton of processing time. I suppose that as your traverse down your scene tree, any nodes of renderable data could be sorted by shader based on which pass it needs to go in. But further, how do you account for proper depth sorting? |
||||
|
||||
|
Ecko Member since: 9/7/2000 From: Etiwanda, USA!!!!!!! |
|||
 Posted - 12/21/2003 8:41:27 PM |
||||
| I'd try to keep your rendering seperate from your game. This way the renderer will keep an internal tree of state changes and shaders, etc while the game tree will supply the rendering objects with proper transforms. -Garret |
||||
|
||||
|
Jeranon Member since: 10/10/1999 |
|||
 Posted - 12/21/2003 9:17:02 PM |
||||
| So... the scene graph is the model and you need to separate the view (ie rendering) from it? Recursive or iterative traversal? Or perhaps Visitor? I'm curious... Are there any (commercial) games out there that are known to use a scene graph implementation? |
||||
|
||||
|
psykr Member since: 7/25/2003 |
|||
|
Posted - 12/21/2003 9:58:50 PM |
||||
| My engine design is still in the design stage, but I came up with this idea: each Object in the scene graph has an ObjectID, to prevent multiple loading of objects, but its position is determined by its parent Frame, or CSceneNode in this article. The Object's parent stores a matrix containing the entire world-to-local transformation, so when I iterate through the entire scene graph, I just keep track of the pointers to visible objects, and put them in a list to sort by MaterialID. INVERSED, the important part is that you should isolate your rendering from your octree (or whatever you're using to organize your objects), even if it means having them completely separated: i.e., having each object be an octree node, and another unrelated shader-related scene graph. |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 12/22/2003 3:20:02 AM |
||||
| Explain to me, please. What is the connection between a scene graph, a bsp tree (in the sense of quake level), a game level and the rest of the game/world structure? |
||||
|
||||
|
Koshmaar Member since: 11/21/2003 From: Cracovia, Poland |
|||
|
Posted - 12/22/2003 3:53:45 AM |
||||
quote: As far as I understood, there is no connection. BSP is algorithm that you use to improve your rendering speed and is done on map level, you convert map to BSP format. Scene graph allows you to manage your rendering and logic code in a more flexible and easier way, it's done internaly in engine code. |
||||
|
||||
|
Jeranon Member since: 10/10/1999 |
|||
|
Posted - 12/22/2003 10:52:30 AM |
||||
quote: Hmm... As far as I understand... A scene graph represents the spatial relationship between a group of objects for the scene like in the star system example. They are separate objects but they are each also a part of the same having come from a parent node (which in turn eventually links to the root). A BSP tree (or related tech) represents the spatial relationship between distinct objects. So a car represented by a scene graph of body and four wheels can be related to another car (scene graph of body and four wheels - actually the two car bodies are sibling nodes or something). Then you can do things like collision detection, visibility etc by using the BSP tree whose nodes link into the appropriate scene graph nodes (so now you can see which object collided with what or where your line of sight ray has intersected or whatever). The following is guessing... Quake doesn't use a scene graph as such. It uses BSP as you say, but Quake's BSP files do not represent just a BSP. It includes a lot of other stuff as well like models, AI, lighting, etc. So I suppose if you were to flatten a scene graph on to a BSP, you'd get what Quake uses. The BSP is used to work out what you can see and from that, it renders what you do see using all the other information in the visible BSP nodes. A game level is pretty much some layout that may use a BSP tree and a scene graph. It contains information on all the models for that level intended to be stored in a scene graph as well as how they would interact with each other and with the player through the use of the level's BSP tree. Note however, that this is just one way to do it. The game world is made up of these levels. (If you're crazy, you might want to put everything into the one world file.) |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 12/22/2003 12:38:58 PM |
||||
Thank you  now I'm even more confused than before. I'll read the article a few more times and your comments.I really can't see much difference between any world data structure like .bsp and scene graphs for now. To me it looks all the same, just "scene graph" sound more academic. "If you're crazy, you might want to put everything into the one world file." Isn't that what Dungeon Siege is doing ...hm, well something like that? |
||||
|
||||
|
deepdene Member since: 3/12/2001 From: Australia |
|||
|
Posted - 12/22/2003 12:56:14 PM |
||||
| I'm going to quote out of Game Code Complete for the following: A scene graph is a dynamic data structure, similar to a multiway tree. Each node represents an object in a 3D world or perhaps an instruction to the renderer. Every node can have zero or more children nodes. The scene graph is traversed every frame to draw the visible world. Basically the difference between a BSP/Octtree etc is that a bsp tree/octtree etc are used for accelerating things like collision detection and frustum culling. that's not the purpose of the scene graph -- it organizes objects on a more conceptual level. |
||||
|
||||
|
Jeranon Member since: 10/10/1999 |
|||
|
Posted - 12/22/2003 7:42:45 PM |
||||
| The scene graph represents the objects in the world - just the 3D objects be it model, lighting, camera, or whatever like a decision branch as mentioned in the article regarding the level of damage to the car door. A scene graph is just one possible implementation of a data structure to store the objects used. Quake's is another kind as is Unreal's. The BSP tree kind of sits over it like a mask and does what deepdene quoted. The BSP is just another data structure that references the scene graph. This is speculation, but for Dungeon Siege, no, it isn't one big world level (though it might look it - I don't own the game - the world file is probably not one big world file but merely several compiled into one like a WAD). DS gets tricky and does background level loading during realtime play to make everything appear as one big world (if your PC is slow enough, you might see when it happens). A question is why would you want to split up a world? A possible answer is to be more productive given the team structure. Only one person can work on a level, so you are better off splitting it into component levels for parallel development between more than one person. |
||||
|
||||
|
Seriema Member since: 6/15/2001 From: Stockholm, Sweden |
|||
 Posted - 12/22/2003 11:00:33 PM |
||||
| I've worked on a game using a scene graph, more specifically a directed acyclic graph (DAG for short). That means that the relations is only one way, like the example in this article. Meaning a parent node can't be a child node to it's first childs. Example: A -> B -> A (leading to: A <-> B) Because that would create a redundancy, try to render by calling A::Render(). That would call B that would call A that would call B that would ... you get the picture So DAG only allows A -> B. Of course you still could do A -> B -> C -> A, but then you're just begging for it  And that kind of scene graph really rocks me thinks! hehe One interesting aspect is "diamond dependencies" also know as the "dreaded diamond" in OOP inheritance talk. More conceptually you can make Flyweight's. For example: you can have your Star and two DOF as childs, each having the same planet as a child. Meaning you'll get two planets rendered on screen in two places, but only using memory allocated for one planet. Oki so planets might not be so good because they're few and kinda unique. But lets say chairs in a dinner room? Or rabbits in a forest? Or AK-47s in a weapon storage room? About the rendering part. This game engine I worked on had Geometry nodes just like this article. Each Geometry node had a "shader" assigned to it, telling it what material and texture etc to use. So when you called Root->Render() it would call the Render() function on all SceneNodes and the Geometry nodes would simply add themselves to the 'renderer'. The renderer would then sort and cull the nodes as they are passed to it, meaning only accepting/keeping those that actually will be visible on screen. And finally when the Root->Render() call is done you call Renderer::Render(). }-- Programmer/Gamer/Dreamer --{  sh1t, I didn't choose to code. coding choose me. [edited by - Seriema on December 22, 2003 11:07:33 PM] [edited by - Seriema on December 22, 2003 11:12:21 PM] |
||||
|
||||
 |
hplus0603 Moderator - Multiplayer and Network Programming Member since: 6/3/2003 |
|||
|
Posted - 12/23/2003 12:24:52 AM |
||||
| Recursion: I'm luke-warm. At best. However, keeping a single interface through which your renderer can extract all geometry and state that goes with it, and sort it into some kind of cohesion (necessary with multi-pass, multi-target rendering, for example) is great. What scene graphs give us is such an interface, but then most implementation takes that goodness and sullies it with arbitrary hierarchy and all kinds of hacky node-ness, which just gets in the way. |
||||
|
||||
|
jamessharpe Member since: 1/6/2003 From: Bristol, United Kingdom |
|||
|
Posted - 12/23/2003 12:07:51 PM |
||||
quote: I think that if you want a shader kind of system you need to loose the idea of including transforms etc. as nodes in the tree. The scene graph is there to show the heirarchy of objects within the world. I think the best way to represent transforms and rotation(I try to avoid scaling since it messes with normals in the renderer) is to store within each object a position and rotation, which is based upon the parent objects position i.e. the movement is relative to the parent(much like the transform scenenodes). You can then make each object store a combined matrix that represents the total world transform. If an object is moved/rotated etc.. then you mark it as 'dirty'. Then when you come to render the node, you recurse into the children and update their positions/rotations based upon the new parents transform matrix. This minimizes matrix rebuilds to when they are needed. Regarding links between BSP/Octree's and scenegraphs - they are two different representations of your world. One is based upon the spatial location of objects, the other on the heirarchy of objects. Note the heirarchy system is more suited to dynamic objects i.e you move one object and all attached objects move, plus collision detection is relatively easy. BSP/Octree's are designed for the efficient culling of geometry for sending to the renderer(okay BSP's are useful for other things and probably NOT a good choice for scene representation with the speed of todays GFX cards.) Now the ultimate representation of a scene would combine the two aspects - be accessible as a spatial tree for rendering and a heirarchy for world dynamics. One way I'm looking at doing this is basing my scene representation as a heirarchy as described in the article - having a Object class as the base. Then the derived classes can specialise for certain things e.g. you may have a BSP object which contatins a whole BSP tree, but yet can still have children objects in the normal sense, but could also contain another entire tree at one of the leafs e.g. it could contain a WaterSurface Object at the leaf of a BSP tree which in turn has a heirarchy of WaterAlgae Object. I hope you see the fleixibility of combining the two representations. That's enough for now, any questions, just ask. James |
||||
|
||||
 |
superpig GDNet Technical Lead Member since: 5/26/2001 From: Oxford, United Kingdom |
|||
|
Posted - 12/24/2003 1:11:29 PM |
||||
| Interesting article. Might I ask what 'DOF' stands for? As far as scenegraphs along with material/shader systems go, I'd possibly go for a multiple graph approach. (Incidentally, just so nobody ends up with erroneous definitions, 'graph' is not synonymous with 'tree' - a 'graph' is any set of nodes and connections (a.k.a. 'edges') while a 'tree' is distinctly hierarchical). Let's say that you do just have all the objects in your world in a simple list. You can then create as many trees as you want, each with nodes referencing those objects. You can have a culling tree, a transformations tree, whatever - each one with references to nodes in the list, combined with DOFs and so on. So I'd probably have one tree for transformations - which, when traversed, calculates the world matrix for each object and stores it in that object - and then another for materials, where I can group objects to minimize texture/shader changes. The transformation details are already in each object, so I don't need to worry about parent/child relationships like that. You can extend it as far as you want. Perhaps a culling tree would be a useful third tree to have - each frame you'd flag objects for visibility, then process transformations, then render. An important consideration is that the different trees don't have to be structured the same ways (and indeed, probably won't be). So if you determine that a given node in your culling tree isn't visible, then you can mark all children as invisible; but you can't then use that culling information to skip nodes in other trees. In your rendering tree, you can only use the culling information to skip rendering the current node; you can't make any assumptions about the children of that node, they might be visible. Richard "Superpig" Fine - saving pigs from untimely fates, and when he's not doing that, runs The Binary Refinery. Enginuity1 | Enginuity2 | Enginuity3 | Enginuity4 | Enginuity5 ry. .ibu cy. .y'ybu. .abu ry. dy. "sy. .ubu py. .ebu ry. py. .ibu gy." fy. .ibu ny. .ebu "Don't document your code; code your documentation." -me "I'm not a complete idiot; parts of me are missing." -}}i{{ |
||||
|
||||
|
Ecko Member since: 9/7/2000 From: Etiwanda, USA!!!!!!! |
|||
|
Posted - 12/28/2003 8:16:53 PM |
||||
quote: Degrees of freedom, while "Frame" or something along those lines would be more appropriate. At the time (almost 2 years ago when I wrote this) it seemed to work; now it doesn't. |
||||
|
||||
|
NatasDM Member since: 8/8/2002 From: Tampa, USA |
|||
|
Posted - 12/29/2003 4:04:04 PM |
||||
| Here's what I think of when I read this article: Stray away from model hierarchial rendering. At least for the moment. Stop thinking of the scenegraph as simply a transformation heirarchy. Rather, consern yourself with state changes. Transformations involve a state change. So do texture changes, blending operations, stencil operations, aplha ops, vertex stream formats, shaders, etc.. State management can mean the difference between rendering a scene at 100 FPS and 30 FPS. To illustrate this, imagine rendering a scene in a typical castle. The walls, stairs, and moveable box is done all with the same texture. However, since the walls are apart of the map, the box is certainly an interactive object, and the stairs a common model, all three of them maybe rendered sepeartely with different world translations. In the sample model, this would mean you would have to traverse each branch and reset the world matrix (no problem in speed). However, if you set the texture 3 seperate times (especially with different objects inbetween) rendering the same texture, you start to encounter hicups from loading the texture state. If you read optimization articles (check nVidia for ppt(powerpoint) lectures) you want to minimize the state changes, with the texture change the most costly. Now imagine the top level of children being sorted by texture. Now all three geometry sets are rendered without changing the texture state. Throw in some batch rendering and you've got a descent framerate. So How Do I orgainze my scene graph? Textures first, definately. This allows you to ignore texture changes for special prerendering, for instance in shadow volume rendering (doom III rendering sequence). After that you might want to look up a cost table (something C programmers used to do back in the day) for state changes. I refer agian to the nVidia article. Organizing the data is simple as pie. Just give each state a numeric value (enumerate). Then sort each branch accordingly. Here's an example of states: 123456 12456 124567 12345 1234 12345 23456 34 5 Pretend the 1 is a common texture, the 2 is a common world state, the 3 special blending operation or shader and so on and so forth. Batch State Changes Some drivers are optimized to make 1 batch state change cost the same as the longest change. DirectX has a way of saving a state and restoring it. Infact, you can save the rendering state batch in the parent node. http://www.nvidia.com/object/gdc_d3dperf.html |
||||
|
||||
|
sashang Member since: 8/21/2003 From: New Zealand |
|||
|
Posted - 1/12/2004 10:22:28 PM |
||||
| The equation given for linear interpolatian (http://www.gamedev.net/reference/programming/features/scenegraph/page2.asp) is wrong. It should be f1.val + (f2.val - f1.val)((current - f1.time)/(f2.time - f1.time)) The way it's written in the article won't give the correct answer when current = f1.time (or at any other time between f1.time and f2.time). Just think about what would happen if the following was given: f1.time = 0 f2.time = 10 current = 0.1 f1.val = 2 f2.val = 3 then using the formula in the article results in 2 + 1*(10/0.1) = 2 + 100 = 102 which is much too far away from f2.val (the value you should be approaching from f1.val). The interpolated values should lie between f1.val and f2.val. Also linear interpolation as you've given it doesn't work for rotations (causes shearing i think). |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 2/10/2004 10:07:11 AM |
||||
| If I understand the thread to this point, a 'very good' solution is to traverse a scene graph to build a render queue of (transform + geometry + shader) render packets, and then sort them by geometry, shader. My question, is how are things like a SkyBox, Lens Flares, Shadows, and Reflections handled? They require 'special' actions like turning on/off the depth and stencil buffers tests. Should multiple traversals be performed? Are these kind of things handled "outside" the scope of the traversal? Or is there a way to include this info in the render packets so it can all happen in one pipeline? Anyone have any insight? |
||||
|
||||
|
LizardCPP Member since: 7/14/2003 |
|||
|
Posted - 2/10/2004 10:33:06 AM |
||||
quote: See the material/shader implementation thread and the thoughts on bouncing. LizardCPP |
||||
|
||||
|
zfod Member since: 5/13/2003 From: California, USA |
|||
|
Posted - 2/11/2004 8:35:28 AM |
||||
OGRE ( http://www.ogre3d.org ) is a great thing to pour through if you wish to see scene graphs in action. FYI, .z |
||||
|
||||
|
Pipo DeClown Member since: 2/16/2002 From: Amsterdam, Netherlands |
|||
|
Posted - 5/6/2004 6:18:03 AM |
||||
quote: Note the bold text (near the end). This is where you want to sort on your own way, I guess. -- About the article, extremely well written. This is just what I needed to read in my learning path. Thanks! -- You're Welcome, Rick Wong - sitting in his chair doing the most time-consuming thing.. [edited by - Pipo DeClown on May 6, 2004 6:20:24 AM] |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 11/21/2004 4:06:31 PM |
||||
| I've just gotten into scene graphs. So waht it sounds like the scene graph is a data strucutre, and BSP is the function that uses the scene graph? LIke the STL, the scene graph would be the data structure and BSP would be the algorithm to access it? |
||||
|
||||
|
Subotron Member since: 1/13/2002 From: Nijmegen, Netherlands |
|||
|
Posted - 3/21/2007 8:48:48 AM |
||||
| since this article is quite old (I think you wrote it like almost ten years ago?) I'm not sure if you'll read this, but thanks a lot for this! It is (one of) the best articles I've read, and it totally boosted my insight on scene management (something I was struggling with). I'm now implementing my own scene graph, and things are really looking up. You have my gratitude :) |
||||
|
||||
|
sunrisefe Member since: 9/16/2007 From: wuhan, China |
|||
|
Posted - 10/1/2008 4:35:39 AM |
||||
| http://en.wikipedia.org/wiki/Scene_graph the website explain much about scenegraph and other spatial partitioning. |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
