 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Dynamic 3D Scene Graphs |
|
 |
Codexus Member since: 11/11/2001 From: Geneva, Switzerland |
|||
 Posted - 12/10/2008 4:37:27 AM |
||||
| Inspiring! It's makes me want to code some procedurally generated thing that can be zoomed a lot. |
||||
|
||||
|
vicviper Member since: 7/1/2003 From: Spain |
|||
|
Posted - 12/11/2008 6:28:57 AM |
||||
| From years of experience with scene graphs, I have a series of issues against using hierarchical scene graphs for representing a world, and I would be glad if the article's author would give his opinion about these issues: 1- do we really need a hierarchical tree? These days, complex graphic assets like vehicles, animated characters with skeletons, etc, come with its own internal scene graph specifically designed for them, so you usually render them as a single instance, for example, you don't render the car and the wheels, you just render the car, which happens to expose an interface to adjust the wheels. Also, the sample of "Garage > Car > Wheel" assumes the car is going to stay always in the garage, if the car is going to move arround, it means that its going to switch parents every time it crosses a "parent boundary"... in other words, what you gain from having the world completely ordered in a tree, you loose it by having to "manage parenting" of dynamic objects that move arround. 2- physic scene graphs vs visual scene graphs. A scene graph is not used only to visually represent the world, it is also used to physically represent the world, and the requirements of a physics scene graph are very different from a visual representation... in fact, in a physics scene graph, there are no hierarchical trees at all, everything is at the root level. Of course, physics engines use internal optimizations like octrees and other structures, but from a global perspective, there are no child-parent relationships. At best, what you have is joints, that connect objects but do not assume one object is the parent of the other. Also, physics engines have a lot of problems processing objects at different scales, giving wrong results at best, and crashing at worst. We must keep in mind that the game's logic is based in the physical representation, not the visual representation. 3- tree structures are bad for multithreading. We live in a multiprocessor world, in which paralel processing is going to be the main trend for the coming years. An obvious optimization is to have a thread for rendering and another thread for physics-logic, and there's something I personally suffered, and it is to see how damn difficult is to make two threads to access all the data availiable in a scene graph. At that point, my solution was to have a physics only scene graph, and on every renderframe, I simply streamed a list of items to render in a single operation. I found this was faster than letting the rendering thread access a physics-visual scene graph. Any comments, please? Edit: I would not like to make people think that I don't give credit to the Author's idea, that kind of hierarchical scene graphs are indeed useful for the purposes of having infinite level of detail, but I think in practice can be used only for self contained, visual only, objects representations, like vegetation, organics, or any other complex structure. [Edited by - vicviper on December 11, 2008 12:28:03 PM] |
||||
|
||||
|
Matias Goldberg Member since: 7/2/2006 From: Mar del Plata, Argentina |
|||
|
Posted - 12/11/2008 8:23:34 AM |
||||
Quote: I was about to say that I just failed to see the reason of using this sort of hierarchical tree. I agree to everything you said. Multithreading, yes it's much better to have separate scene graphs rather than giving the render thread access to the physics thread Furthermore, I was thinking today that on many cases Physics are a lot different than rendering. For example in physics everything should be decoupled to allow better AABB hierachy, but rendering likes having everything batched as a single object to get less CPU overhead. Quote: In my opinion, if we need infinite zooming, I would use some specialized approach rather than a general one like this. There are some exceptions though, were I think this could be valid. Nice detailed article, but I think it's missing a "Why we want a scene graph in games?" on the very beggining, to keep my attention and convince me of reading it to the very end with enthusiasm. Just saying that they're usefull for tree and grass rendering isn't enough, because there are lots of specialized optimizations on that particular topic (like SpeedTree and PagedGeometry from OGRE, or Rendering Grass Terrains in Real-Time with Dynamic Lighting; Kévin Boulanger, Sumanta Pattanaik, Kadi Bouatouch; SIGGRAPH 2006 ) Cheers Dark Sylinc |
||||
|
||||
|
PaulEdwards Member since: 4/15/2006 From: Vancouver, Canada |
|||||
|
Posted - 12/11/2008 3:45:13 PM |
||||||
Hello, I'm the author of the article... I'm grateful for the feedback, thank you.Quote: No worries, it was not interpreted that way. I should first say that my interests were first drawn in to the project because of its ability to render fractal-like objects in such a way that they can be explored in 3 dimensions. While working on it, I realized that while these results were interesting, they weren't of practical value to games. As Matias points out, there are more specialized algorithms available for this. I demonstrate the feature now only to show the generality of the system. While working on the project, it became apparent that the more practical features were its ability to handle scene graphs which include objects of drastically different scale. I think that perhaps I emphasized the systems use for rendering continuous LOD objects too much in the article. Quote: I completely agree with what you're saying here. I didn't mean to convey that every object in your world should be exclusively structured under a hierarchical tree. This is not an all encompassing spatial data structure. Were you to use this system in a real game, it should be used to organize sets of objects of vastly differing scales. For example, a scene hierarchy consisting of galaxies, solar systems, planets, and cities. Within each node, you might have another spatial data structure for managing the elements within it. Once we are at the planet node, we might have that planet use a kD tree to sort its children. The assumption here is that the children of a planet really wouldn't interact with the children of another planet. Flying your spaceship from one planet to another would require re-parenting, but it is now a restricted and explicit case. In essence, I'm saying the Garage -> Car -> Wheel example is contrived, since they are all on the same order of scale. The Car -> Wheel should probably be maintained in an object-sized local hierarchy tree, and the Garage -> Car hierarchical relationship would probably not exist, and instead would be managed under a kD tree-style data structure. Quote: I think this might seem more reasonable when using the dynamic scene graph system in a more coarse grained frame-work, as described above. Ie: It is reasonable to assume that the children of one planet will not physically interact with those of another. If this happens, it is a special case, and can be dealt with explicitly. Realize though that the system still enables the planets themselves to interact with other planets, since they are all children of the solar system. In this sense, you can also use the system to represent physical interactions on different scales, without crashing or inaccurate behaviour. Quote: Yeah, this is a tough one. The generation of the dynamic scene graph is not easy to parallelize. That being said, the generation of the scene graph is seperate from its rendering and physics processing, so this period of serial processing can be fairly low, especially if you have a course scene graph. Most of the calculations involved in generating the scene graph will be screen-space area calculations and memory allocations. Once generated though, you effectively have a flattened list of nodes in your reference space, which allows for a much more parallel approach for rendering and physics processing (or at the very least, it is now another type of spatial data structure's problem). Quote: In hindsight, yes I agree that I should have put more emphasis on that question closer to the beginning of the article. Just to point out again though, tree and grass rendering are probably not the best practical uses of this system. I hope this helps with some of your concerns. If not though, definitely shoot something back at me. By the way, vicviper = Roderic Vicaire who wrote the 3D Engine Tech article on Beyond3D? Your post speaks many of the points mentioned in that article, that's why I ask. |
||||||
|
||||||
|
vicviper Member since: 7/1/2003 From: Spain |
|||
|
Posted - 12/12/2008 4:33:32 AM |
||||
Quote: No, I'm not Roderic ^_^; But it's not that rare to find people criticising scene graphs these days, years ago, a scene graph was the way to go, but now, everybody that tries to mix scene graphs with physics engines and/or tries to paralelize them, realizes the critical limitations a scene graph has. I think we have to find a new way to describe scenes, and one that is easy to connect to a physics engine, and easy to paralelize. I don't know how these structures would look like, but I know that 3d engine authors should start putting some thinking in finding new ways to describe scenes, other than scene graphs. Cheers Vic |
||||
|
||||
|
PaulEdwards Member since: 4/15/2006 From: Vancouver, Canada |
|||
|
Posted - 12/12/2008 4:15:45 PM |
||||
| Most games today are doing what they do very well... Perhaps, as you suggest, other spatial organization methods could be used to allow them to work even better. I agree. The dynamic scene graph is an enabling technology... There's not much reason to integrate it in to existing games, it won't make them run faster or better. Rather, it allows for a natural implementation of new features in potential games. A smooth transition from a galaxy-level view to a city-level view would be very difficult to implement without dynamic scene graphs. On the more artsy(perhaps less practical) side of things, dynamic scene graphs would allow for the creation of interesting zoom-quilt (http://zoomquilt2.madmindworx.com/zoomquilt2.swf) like scenes, except in 3D. |
||||
|
||||
|
GregDude Member since: 12/27/2003 |
|||
|
Posted - 12/13/2008 12:54:30 AM |
||||
| Homogenous scene graphs are of little value in modern video games. vicviper touches on some of the reasons. Tom Forsyth explains further on his blog http://home.comcast.net/~tom_forsyth/blog.wiki.html click on 'Scene Graphs - just say no' Aug 2006. Don't get me wrong, scene graphs are of value in some circumstances, connections, trees and hierarchies are useful tools, but homogenous classic scene graphs are the wrong way to organize data in a modern game engine. Game engines are not just about rendering. Networking, physics, collisions & clipping, navigation, rendering, animation, smoothing & effects and AI may need separate or shared representations of logical game objects. |
||||
|
||||
|
Sphet Member since: 9/16/1999 From: Vancouver, Canada |
|||
|
Posted - 12/13/2008 12:28:24 PM |
||||
Quote: First of all, PaulEdwards, thanks for the article - it was a great read and happy to see you pushing something out there that is a bit different for us to read. With regard to the generalized Scene Graph discussion, I'm in agreement here - a homogeneous scene graph has too many problems/not enough value for game engines anymore. However, I wanted to talk a bit about the application of scene graph in the specific area of games where we have a somewhat generic system that spans from toolset to gameplay. Our game engine contains various data structures and spatial partitioning systems that span rendering, audio, physics and game logic. We employ a scenegraph in our toolset for all of those assets, allowing artists to treat objects, be they static or dynamic, all the same. At runtime only the game-entities exist in the scene graph - the static geometry and static physics objects end up in their own partitioning system, effectively being folded into the root node of the Scene Graph. From that point on, the Scene Graph has become just a hierarchical entity tree. In contrast, all dynamic objects, including rendering, physics, ai and other behaviour, exist in a tree which is really there to generalize a child/parent transform relationship. As we employ a component-based entity system, objects in the scene graph, with parents and children, may contain physics and rendering components that exist in another spatial system - the tree is used simply to update the transforms, send messages between objects, and simplify the object search requirements of game play programmers. We like the mapping of a generic Scene Graph in our level editor to tree in game, and the component based entity system allows us to cache different aspects of the dynamic objects in the right spatial system, be it an internal physics system, or a PVS-driven solution for rendering. On create, each component is essentially 'hooked into' the list of other components of that type, and the subsystems managed the partitioning of and operation on those objects. The tree simply provides a generic interface for managing those objects and synchronizing transforms. Previously data was flattened into lists to simplify the dual task of search and submission for rendering, dynamics, etc. We've found the 'brain-friendly' structure of a Scene Graph to be a great benefit to development and runtime organization, but we don't use it as the be all and end all of partitioning and traversal. Just thought I would throw my 2cents in there since we're talking about 'different kinds of scene graphs'. Again, good article. S. |
||||
|
||||
|
Emanuele Russo Member since: 6/6/2007 |
|||
 Posted - 12/14/2008 7:30:45 AM |
||||
| Hi everybody, first of all compliments to the author, I found the article very interesting. I'm particularly interested in the "zooming solution" part of it, the change of frame reference. I read it, but I'm not sure I understood it perfectly. May I make a little example? So let's say that when I render an object I use the World * View * Projection matrix, where World is the matrix from the local to the world frame, View is the camera frame, Projection is the camera frustum. Let's consider a scene graph like this: Root | Ma | Mb | Mc | Md | Me Where Mx are the linear transformation that position a node relative to his parent. We can say that normally when we render an object with Me matrix we use Root as world frame coordinate, so our World * View * Projection will be: Ma * Mb * Mc * Md * Me * View * Projection Correct? Well what I understand from your article is: I can change my frame reference to any node of the chain, let's say I want to change to Mc. According to your pseudo code, Mc is the source node, and Me is the dest. Then you say: source to root is s2r = Ma^-1 * Mb^-1 * Mc^-1 root to dest is: r2d = Ma * Mb * Mc * Md * Me Then the transform matrix is: s2d = r2d * s2r Correct? Finally I want to render my friend Me with the new reference, you say: "By applying this transformation to the current model-view transformation, we obtain a new view transformation that is relative to the object we wish to re-focus on" So what should I do: render with s2d * World * View * Projection? render with s2d * View * Projection? render with World * s2d * View * Projection? So last question, when you say "If the new frame of reference is smaller than the old one, we have just made the entire universe bigger, but since the view matrix has been adjusted to account for this as well, the universe appears unchanged" I don't understand very well, because I think about, for example, a scene where you have the earth, 6M Km radius sphere, and your town, 20Km radius scene, and the town has a translate and rotate matrix to locate is on the earth. There's no scale here so how can the frame be smaller? Maybe you just move the camera in a certain way and it looks smaller or bigger; or does this system work only with scale factors in homogeneous matrices? I hope I was clear, and hope somebody will answer, Cheers, Ema |
||||
|
||||
|
PaulEdwards Member since: 4/15/2006 From: Vancouver, Canada |
|||||||
|
Posted - 12/14/2008 7:33:33 PM |
||||||||
EDIT: Whoops, particularly because of this post, I noticed a mistake in the pseudocode in the article. I will submit to have it fixed. The error is that the pseudocode spoken about in this post is[or was] multiplying the matrices in reverse order. Thanks Emanuele for bringing this up. Sorry for the confusion.Quote: Be cautious, I have been assuming column vectors in the article where it seems you are assuming row vectors. I would write "Projection * View * Me * Md * Mc * Mb * Ma" to intend that multiplying a vector with this matrix will have it first multiplied by Ma, then Mb, then Mc, etc... That being said, yes, this is correct. Quote: Well, the pseudocode doesn't specify that Mc is the source node... According to your previous question, Root would be the source node. But let's just say that Mc is the source node. Quote: This is where I made a mistake in the pseudocode within the article. (For which I will attempt to submit a correction)... Sorry! Coincidentally though, with vectors as rows, as you assume, what you have here is correct. Since I assumed vectors as columns in the pseudocode, it should have constructed the matrices in reverse order. Quote: Not quite... The root to dest matrix has its matrices applied in reverse order in the pseudocode, so this will result in (in row vector form): r2d = Me * Md * Mc * Mb * Ma Quote: Yes this is correct, but since you assume vectors as rows, you should write (s2d = s2r * r2d), it will expand to: s2d = Me * Md * Mc * Mb * Ma * Ma^-1 * Mb^-1 * Mc^-1 = Me * Md Which is the matrix that shrinks the unit cube in Mc to Me's frame of reference. Quote: Once again, be careful, I have been assuming column vectors in the article. I would write "Projection * View * World" to intend that multiplying a vector with this matrix will have it first multiplied by World, then by View, and finally by Projection. This is a good question, I should have elaborated in the article. I normally maintain a camera object seperately, so that I can naturally set its rotation and position. When it's time to render, I will convert the camera transform to the view transform by inverting it. In my case, I will then apply s2d as follows: Camera' = (s2d.Inverse() * Camera).NormalizeScale() So essentially, I am transforming the camera's current rotation and position. The s2d matrix will have a scaling component, so we should remove that when applying the matrix to the Camera. We only want to affect our camera's rotation and position (because those are the only two components of the view matrix). My view matrix is: view = Camera.Inverse() So I suppose that if I skip the Camera representation, we would have: view' = view * s2d And so, you should render with: Projection * View * s2d * World. Or, in row vector notation as you have phrased the question: World * s2d * View * Projection. But I would recommend that you continuously fold your s2d matrix in to your view matrix. In other words, each frame you should execute: "view = view * s2d" before rendering. Quote: I didn't mean to imply here that any kind of scale in the view matrix would be changed... Most view matrices do not have a scale component. What I mean to say here is that because the camera has been moved and rotated according to the new frame of reference, the fact that the world has scaled up at the triangle rendering layer will not be noticeable. The camera's position and rotation are the only components that will change, scale will always be 1. Thanks for the questions. I hope this helps, let me know if anything still doesn't make sense. [Edited by - PaulEdwards on December 26, 2008 9:33:27 PM] |
||||||||
|
||||||||
|
PaulEdwards Member since: 4/15/2006 From: Vancouver, Canada |
|||
|
Posted - 12/14/2008 7:39:38 PM |
||||
Quote: Yes. Scene graphs have their places, and perhaps their use is often abused. In any case, that's not the point of this article. The dynamic scene graphs discussed in the article allow you to implement features that you wouldn't be able to do any other way. There is a link on the Applications section page to a demo program showing off some of these features. Furthermore, implementing this dynamic scene graph (or even a standard scene graph) is not mutually exclusive with other spatial partitioning techniques. Mix and match options include having another spatial partitioning structure as a node of the scene graph, or having scene graphs as children of other spatial partitioning nodes. In this sense, you are free to use scene graphs only when it is natural to do so. |
||||
|
||||
|
PaulEdwards Member since: 4/15/2006 From: Vancouver, Canada |
|||
|
Posted - 12/14/2008 7:47:32 PM |
||||
Quote: Thanks. Quote: Yes, I think the new-fashioned crusade to rid the world of scene graphs is well-founded, but only because scene graphs are abused far more often than they are used correctly. It is these abuses that people like Tom Forsyth are targeting with their articles. |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
