 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Terrain and Scene Graphs |
|
 |
JimH Member since: 11/15/2001 From: USA |
|||
 Posted - 8/20/2002 4:40:17 PM |
||||
The more I read the more questions I have. (But I’ll try not to spam the forum with all my questions  )From another thread on this site, I just found the programmer’s guide to the OpenGL Performer engine at the SGI site. It’s very interesting reading. You get a good idea of how their scene graph works. I noted that they incorporate terrain as part of the normal graph. It’s not a separate thing. I haven’t read the chapter about ASD in detail yet so I don’t know how it works. But one question I had right away was: do most people treat the terrain as a separate thing? Or do they add it as part of the regular scene graph the way Performer does? I assumed it was always separate until I read this. The trouble I have is that every time I read something new, I start rethinking the code again. At some point you have to settle on what you’re gonna do I guess. |
||||
|
||||
|
Yann L Moderator Member since: 2/6/2002 From: Breizh |
|||
|
Posted - 8/21/2002 11:21:39 PM |
||||
| OK, I have to admit that I never worked with Performer, and have no idea how it handles terrains. Nevertheless, here some thoughs about terrain integration in general. First of all, the terrain is a 3D object as any other in the scene. Sure, some terrains might be rendered using different methods, but it still is a 3D entity. It should be treated as such, when inserting it into a scene graph. Now, I don't know how you set up your scene graph, but let's assume the classical OO approach: you have a generic 3D object/instance class, and you derive specific objects from it. Those nodes are then organized into a hierarchic tree. The tree is traversed, and each node is rendered/manipulated depending on the type of the geometry it contains (how you do that, eg. by an explicit ID or by using RTTI, etc, is not really important for the general concept). So a terrain would just be another type of object derived from your base instance class. That way, it smoothly integrates into your scenegraph. You can insert it, remove it, etc, without worries. Let's say you have a base class named INSTANCE. Derived from that is eg. BASIC_OBJECT, CHARACTER, etc, and finally TERRAIN. The exact details of the TERRAIN class ultimately depend on how you represent and render your terrain. Say you have a virtual member function called 'render', that each derived class overloads with the appropriate version for the 3D object type it represents. In case of a heightmap terrain, your TERRAIN render function will be some kind of tesselator (that transforms the heightmap into a mesh, perhaps copying it into a vertex array/buffer), and then once the mesh is created, it will simply treat it as a normal 3D mesh (and render it that way). You could of course treat your terrain as a totally seperate entity, and not integrate it into the scenegraph at all. But this is not a very elegant approach. You'd need special case code all over your engine, in order to treat your separate terrain entity. Imagine some shadow projection code, that will operate on all 3D objects and the terrain. If your terrain is a separate entity, you'd need two separate shadow functions (or one single, full of ugly if/else statements). But if your terrain is included in the scenegraph (as a derived class), you have one shadow function that will handle everything. Same goes for eg. HSR or collision detection. That might save you alot of redundant code. And even more important: it will make your hierachical scene management a lot simpler, cleaner and easier to understand. This will come in handy later, when you want to include new object types, perhaps some special effect, or animation. Conclusion of all that ? Treat your terrain just as any other entity or object in your game, from a high level scene management point of view. Of course, the lower level rendering might differ (perhaps even significantly, eg. in the case of ROAM), but a scenegraph does not deal with lowlevel details. It's a high level, standarized representation of your scene. And that should include every single object (even lightsources, cameras, etc). Of course, that only my personal opinion, other people might disagree / Yann |
||||
|
||||
|
JimH Member since: 11/15/2001 From: USA |
|||
|
Posted - 8/22/2002 2:26:23 AM |
||||
| Thanks for the thorough answer, Yann. I guess the reason I get thinking about terrain as being a separate thing is because there are some characteristics that are unique to it and so there could be the opportunity for applying a heuristic here or there. For example, just using a hightmap instead of defining all points with x, y, and z coordinates is a heuristic based on the fact that terrain is generally flat. Terrain might also be treated differently because you might want to have LOD, and in that case you need it to blend smoothly from one LOD to another. This is unlike other objects which are usually either one LOD or another. So because of unique characteristics like these (and maybe because people refer to “terrain engines”), I thought some people might deal with terrain by itself, perhaps for performance reasons. But your points are good. Treating the terrain as another object is certainly more elegant. I can see that, if you are going to treat terrain rendering differently, it would be nicer to do it at some lower level. I was sort of aware of that, actually. I guess I was just wondering if it was common to deal with terrain separately for performance reasons. Jim |
||||
|
||||
|
Yann L Moderator Member since: 2/6/2002 From: Breizh |
|||
|
Posted - 8/22/2002 10:39:32 AM |
||||
quote: Not really performance reasons. No engine will have a bottleneck in it's high level object representation (or if it does, then there is a serious problem). The bottlenecks are always in the lowlevel rendering functions. That's where tesselation, polycounts, etc become an issue. But the scenegraph is just an abstract representation of your scene, it's nothing performance critical. quote: Yes, of course. But the same thing applies to eg. particle systems, billboards, procedural objects, water surfaces, etc. You'd need to deal with a whole bunch of separate entities, each one with it's unique properties. You'd need separate lighting, collision detection, HSR code for every object type you have in your game. What a mess. That's why the concept of the scenegraph was created. It simply is a way to bring all those different object types together, in an abstract data structure. All those objects get a unified access interface, and on the level of abstraction of a scenegraph, they are just all the same (they are all 3D entities of some sort). Keep in mind, that you don't need to use a scenegraph for performance critical operations, such as culling of static geometry. This is often done using an octtree (or similar), a hierarchical structure that is independent of your scenegraph. A scenegraph is primarily interesting for dynamic and/or moving objects. If you don't want to explicitely include every static object of your scene (incl. terrain), you could just define a new abstract 3D type: octtree. And you insert the root node of that octtree into the scenegraph, which will then represent a whole collection of static objects in a single node. That's what a scenegraph is all about: it's a standard way of organizing your scene into nodes, giving them a unified access interface. That way, even totally unrelated entities (heightmap terrain, particle systems, volume fog boxes, lightsources, etc) can be accessed through common interfaces. Which makes your engine easier to understand, maintain and keep it expandable. / Yann |
||||
|
||||
|
JimH Member since: 11/15/2001 From: USA |
|||
|
Posted - 9/19/2002 3:53:13 PM |
||||
I’d like to resurrect this thread because I have more questions. I’m still trying to get a handle on how a scene graph is organized and how a terrain might fit into it. In general, objects in a scene graph are organized according to what criteria? Their location in the scene? What processes operate on the scene graph? Culling? Collision detection?quote: Well, that was my whole point. If you’re going to put static objects in one tree and dynamic objects in another, then where is the unified access? How do you do collision detection on static and dynamic objects if they are in different trees? Do you check through one tree first then the other? Same with shadows? I was looking at Open Scene Graph which is nice because it’s open source. In the FAQ documentation they refer you to an implementation of using terrain with OSG. It’s called Demeter. I skimmed through the code a bit and realized that Demeter doesn’t use OSG, rather it is a self-contained terrain engine that makes itself look like a standard OSG node. Therefore, you can create a Demeter terrain and insert into an OSG graph as one node in the graph. This is something I don’t understand yet. As an OSG node, the terrain node must provide a bounding box. In this case Demeter’s single bounding box includes the entire terrain! The box extends from the terrain’s lowest vertex to its highest. What is the point in that? You cannot do culling since the entire terrain would either be culled or not culled. You cannot do collision detection because you would always be colliding with the terrain’s bounding box. What is the purpose of putting a terrain into a scene graph as a single node? You just as well might treat it separately? It seems to me that the way things are organized in a scene graph depends on what operations you are trying to do on the scene graph. I assumed that you use it for culling and collision detection. In that case, you want to arrange things spatially. You want to be able to cull entire sections of the scene at once. You want to be able to only check for collisions with other objects that are in your nearby area. So you want a spatial arrangement. This would make a scene graph like a quadtree or an octtree. But in the implementations of scene graphs I’ve seen so far, I haven’t noticed any provision for arranging things this way. I didn’t see any “group node” that says “all objects in this branch are within coordinates x1, y1 and x2, y2”. So I’m not sure how things are meant to be arranged. (Sorry, I don’t know what HSR stands for) If you really want terrain to be abstracted like all other objects, shouldn’t the terrain “patches” or blocks be individually inserted into the scene graph as nodes? Can you explain this a bit more. [edited by - JimH on September 19, 2002 4:37:27 PM] |
||||
|
||||
|
Yann L Moderator Member since: 2/6/2002 From: Breizh |
|||
|
Posted - 9/20/2002 1:10:49 PM |
||||
| Hmm, the whole thing is not so easy to explain. OK, generally, if you have a spatial tree, then you don't have a scenegraph. They are two different things, although they can be combined (with various tradeoffs). A scenegraph, by definition, represents the hierarchical relationship between your scene objects. It is not necessarily spatially clustered. This of course, is primarily interesting for dynamic objects. Imagine a skeletal bone structure used to animate a human model. A scenegraph is similar, but extends the concept to your whole 3D world. The main focus on a scenegraph is not performance gain (eg. by spatial clustering for optimized HSR (= hidden surface removal = general term for all forms of culling). Other, better suited structures are used for that (octtrees, BSPs, Kd trees, etc). The primary idea of a scenegraph is high level organization. It gives all objects types, even if they are totally different, a unified access mechanism. Imagine the following scenario: The player in your game picks up a torch, and starts carrying it around. What parts of your scene are affected internally ? First, the 3D torch object must be hierarchically linked to the players hand. Then, the fire effect (perhaps a volume renderer) needs to be attached to the torch. The particle effect for the smoke needs to be attached to the fire effect. And last but not least (since we're talking about a kickass, Doom3 killing engine with full dynamic perpixel lighting and shadows  ) we also need to attach a lightsource and shadowmap projection system to the torch.In this example, 6 different object types are interacting: a character model, a solid 3D model (torch), a volume renderer (flame), a particle system (smoke), a lightsource and a shadow projector. If all those entities used seperate representations, then can you imagine the chaos and mess it would be to link them together ? But with a scenegraph, it is amazingly simple: All those 6 object types have the same base class, you change a few hierarchic links in the graph, and you are done. Now, the question remains how to combine this graph with efficient acceleration structures (for rendering, collision, etc). Each type of object might use a different approach, eg. an octree is good for a complex static 3D model, but totally useless on a particle system. But the interesting point is the unified access to those representations: the messy details are isolated in the derived object classes, from a high level point of view, you always see the same clean interface. Example: Our player (with his torch) is moving through a village, which is on a terrain. Here is the scenegraph:
ROOT
|
|--- terrain node (geomipmapped quadtree)
|
|--- geometry of the village (static, octtree)
|
|--- Player (deformable skinned mesh)
| |
| |--- Torch (solid 3D object)
| |
| |--- Flame (volume renderer)
| | |
| | |--- Smoke (particle system)
| |
| |--- torch Lightsource
| |
| |--- torch shadow projector
|
|--- Big bad guy behind the player (skinned mesh)
|
|--- Big battle axe in the hand of the bad guy OK, you get the idea. When it comes to rendering, you start at the root node, and follow the hierarchy (by applying appropriate matrix concatenation, state changes, etc, this can be included into the baseclass and will be common to all object types). At each node, you call the render method: CurrentNode->Render(). It will always be the same, regardless of the object type (unified interface, every type overloads the virtual method to hide to gory details). This method will then peform culling on the object (ie. traverse the quadtree for the terrain, apply LODs, go through the octtree for the static village, etc). You have similar methods for collision detection, lighting, shadowing, dynamics, etc. Eg: CurrentNode->isColliding(), CurrentNode->ApplyDynamicForce(...blah...). Every object type shares this common interface. Now, that's the basic concept. There are extensions to that. You can merge the hierarchical scenegraph structure with the spatial structure of static geometry, and directly perform HSR on the scenegraph nodes. The efficiency of such an approach highly depends on your engine design. It can be pretty efficient with octtrees, and portals, since both exhibit certain natural hierarchical relationships. Hope that explains it a bit better. If not, just ask / Yann |
||||
|
||||
|
JimH Member since: 11/15/2001 From: USA |
|||
|
Posted - 9/20/2002 6:03:36 PM |
||||
| Thanks for taking the time to explain that. It answers my original question and it really helps a lot. It seems to me there is a lack of information about such structures and organization, or at least I haven’t seen this type of thing discussed much in books or on the internet. I can see how this will work. In your example, if I want to see if the player collides with the terrain, I can pass the Players bounding box to the Terrain node. Then the terrain node will search down the quadtree to the appropriate terrain patch to compare it with the Player’s location that was given. Ok. I had thought this approach would have the disadvantage that your scene graph ends up being rather flat. So if you want to see if the Player collides with any other dynamic object, you need to compare with the entire list of dynamic objects in the Root node of the scene graph. You can’t rule out entire groups of dynamic objects that are far away. But on the other hand, you also don’t have to move those objects around in the scene graph just because they change position. And also, I suppose there will not be that many dynamic objects anyway. In your example, I’d say that object hierarchy is the primary criteria for organization and location is secondary. For example, the Terrain is a single node and under that the terrain is then organized by location. Another different approach I had thought was possible—and for the sake of discussion let me propose it—is to reverse those priorities. What if you make location the primary criterion for organization? Let’s say we start out with a quad tree as the main structure and within the nodes of the quadtree we have scene graphs.
ROOT
|
|---Quad 1 (a type of group node)
|
|---Quad 2
|
|---Quad 3
|
|---Quad 4
|
|---Quad 4.1
|
|---Quad 4.2
|
|---Quad 4.3
| |
| |---terrain patch
| |
| |---house (static object)
| |
| |---Player
| |
| |---Torch
| |
| |---Flame
| | |
| | |---Smoke
| |
| |---torch Lightsource
| |
| |---torch shadow projector
|
|
|---Quad 4.4
|
|---terrain patch
|
|---Big bad guy
|
|---Axe in the hand of the Big bad guy
Maybe this is what you mean about merging the spatial structure of static geometry with the scene graph. In this organization, you can cull entire groups of objects at once, including terrain, static and dynamic objects. During collision detection, you can reject entire sections of the scene regardless of node type. If you want to see if the Player collides with anything else, you can compare against objects in the current Quad and in the surrounding eight Quads and that’s it. A disadvantage, of course, is that when the Player moves out of Quad 4.3, you have to take him out of the tree and reinsert him somewhere else. I just mention this approach for the purpose of discussion and the relative pros and cons of each approach. I’m not arguing that one is better than the other myself. But I wouldn’t mind see a discussion about it. [edited by - JimH on September 20, 2002 6:05:55 PM] |
||||
|
||||
|
Yann L Moderator Member since: 2/6/2002 From: Breizh |
|||
|
Posted - 9/20/2002 7:16:05 PM |
||||
| Your example is exactly what I meant by merging hierarchical and spatial information into one tree. But the approach of inserting a helper node per quadrant (or octant in the case of an octree) will result in a lot of empty helper nodes. This might or might not be a problem, depending on the size of your tree structures. You still have to visit the entire helper node hierarchy, even if there is only one little object somewhere in a deep leaf of the tree. You have to visit it, even if a branch is entirely empty. An advantage is that you can exploit the regular grid structure of a quad or octree, to speed up the relocation of a moving object: just store a pointer to the scenegraph helper node in each quad/octtree cell. When your object enters a new cell, you can easily retrieve the position in the scenegraph where it needs to be inserted. One problem remains: what if the object is on the boundary of two cells ? Duplicating the scene graph branch from the objects local root would be very messy. You could walk up the helper node hierarchy instead, until you find a node that holds the entire object bounding box, and insert the object there. You would lose spatial coherency, but it would still be rather effective. But there is another (big) hidden problem with this approach: Imagine having a big world, with a pretty deep quadtree (let's take a quadtree for simplicity here). I'll denote each of the four sub quadrants like this: |---|---| | 1 | 2 | --------- | 3 | 4 | --------- Let's say there are two objects, one in cell 1.2.2.2 and one in cell 1.2.2.3 (each dot refers to a hierarchical level, it will be easier to understand what I mean, if you draw a fast sketch of this on a piece of paper). The relationship between the two objects is OK, because both cells are hierachically and spatially close. Now the first object moves by the distance of a single cell, from 1.2.2.2 to 2.1.1.1, that's spatially only one cell away. But hierarchically, it's an entirely different tree branch ! The regular (and fixed) subdivision create 'fault-lines' along the division edges, that break the spatial and hierarchical coherency. Anobject can be spatially close, but lightyears away in the hierarchy. This problem can tremendeously increase your tree traversal time. A different approach (the one we use in our game engine) are adaptive sparse binary trees. The idea is to merge an adpative spatial hierarchy into the scenegraph, but without pre-populating it with an empty regular grid of helper nodes. Instead, the hierarchy is generated and updated on the fly, as the objects move around. The advantage of that approach is, that spatially near objects will always be hierarchically near aswell. quote: Yes, unfortunately. But optimal hierachical clustering is a very complex topic. You can actually find academical papers about various approaches, but those are generally very theoretical and hard to understand. Finding the optimal scenegraph/spatial clustering algorithm is the holy grail of hierarchical HSR. The few who found it (if there is such a thing as 'optimal') aren't exactly shouting the solution around, that's a fact / Yann |
||||
|
||||
|
ZenoGD Member since: 3/2/2002 From: San Diego, CA, United States |
|||
|
Posted - 9/21/2002 1:47:52 AM |
||||
| Hi guys. I've been following this thread with great interest, as I have come upon these problems in my work as well. I was always able to come up with some solution, but it never seemed like the best one....there was always something not quite elegant about it. JimH - I share a lot of your concerns about scenegraphs. The choices one makes in this part of an engine are perhaps the most critical to good performance, yet the information about it is sparse at best. There are only a few tutorials out there, and they usually only cover one aspect of the many things you'd like a scenegraph to do. So anyway, I'll try to make some small contribution here before asking questions To me, the ideal scenegraph would do all of the following: 1) Aid in frustum culling 2) Aid in choosing collision detection pairs 3) Assist with hierarchical animation 4) Clump rendering states 5) Take advantage of frame-to-frame coherence in doing the above 6) Have an easy mechanism for moving things around 7) Be very fast For me, 1-4 are mostly solved (let me know if you want details), I haven't thought about 5 much, 6 is my biggest current problem, and 7 is difficult to measure (compare to what?). To solve problems 1-3 (keeping 7 in mind) I wouldn't use a system like the one Yann first proposed, for the reasons JimH mentioned. Organizing your scenegraph in such a flat way will leave you without an efficient way to do pairwise collision checks or scene culling. Given this, I think a system like what JimH diagrammed or Yann described wrt his engine is the only way to go. Yann's method sounds a lot like that suggested in "3D Game Engine Programming" by Eberly. Now for my questions. In a system with a fixed hiearchy with helper nodes (presumably based on some underlying static geometry, like a quadtree for terrain or BSP for indoors), it seems like you have to keep duplicate pointers to objects within the scenegraph when they straddle boundaries. Is there any way around this? It makes moving them a pain in the ass. If you use an adaptive tree (which is what I think Yann and Eberly suggest), the problem is figuring out how you would keep your tree from quickly becoming mangled. For instance, imagine this situation: You start off with some terrain and a bunch of people on it. You go ahead and build a bounding sphere hierarchy for this arrangement, with people at the lowest level. Now, as the people move around, you have to move their bounding spheres, which may change the shape or size of their parent bounding spheres. This will eventually cause the hierarchy to shift and cause big overlaps (tangled branches) which will cause you to lose most of your efficiency in doing culling. Further, you will miss potential collision pairs if you only look in one leaf-level node at a time since two people could be in entirely different branches of the tree yet very close to one another. How have you guys handled this issue? Thanks for sticking with the post this long -- Zeno [edited by - ZenoGD on September 21, 2002 2:00:01 AM] |
||||
|
||||
|
Yann L Moderator Member since: 2/6/2002 From: Breizh |
|||
|
Posted - 9/21/2002 11:10:51 AM |
||||
| ZenoGD: Actually flat graphs can have their very own benefits over deep trees, but more about that later. The best method I personally found is the adaptive one. I can't recommend the regular grid quad/octtree method, it just has too many drawbacks. It is the other extreme of a totally flat tree: you lose the hierarchical consistency in favor of a full spatial localization. But this generates huge and very deep trees, which are essentially empty. Also, hierarchical information (important for animation) is often broken up. About objects straddling cell boundaries: as I mentioned above, you could simply navigate up the graph hierarchy, until you find a parent node that can hold the whole bounding box without touching a boundary. Eg. if your object straddles the edge of cell 1.2.1 and 1.2.2, then you could check if cell 1.2 can hold the entire object. However, the obvious flaw in this approach is easy to spot: in the worst case, you'll have to navigate all up to the root, and insert your object there. Thus artificially flatting out your graph. quote: Yes, preventing tree degeneration is the key to truely making the adaptive approach work. There are several methods to that, but this is how we did it: each node has a degradation factor (d-factor), that states how much the node has shifted from it's optimal shape and position. Parent nodes include all d-factors from their children. Various heuristics are possible here, eg. sum or median value. It will influence to reaction of the tree to spatial delocalization. If an object is moved, it's d-factor is updated, and this change is propagated up the hierarchy. As soon as the d-factor of a node reaches a critical threshold, the whole subbranch (starting from that node and including all of it's children) is deleted from the tree, and rebuild from scratch. At this point, the rebuilt subtree is optimal again, so all d-factors are set to 0. This approach periodically renews parts of the tree that get too degenerated, and works pretty well. It also helps to minimize empty nodes: keep the tree as flat as possible (since flat trees are more efficient in terms of traversal speed and memory usage, if you have to visit every node), while still maintaining a good degree of spatial clustering. That said, we still run into a major problem while designing our engine. The problem are the lights, which are part of our scenegraph. Since we use full realtime shadow projection on dynamic lights, the bounding box of a lightsource represents it's maximal influence radius (used for perpixel shadowmapping optimization). But since light influence is typically much larger than the size of an object, you'll get huge bounding boxes for lightsources. Eg, in the above example, our character would have a bounding box of around 1m*1m*2m = 2m³. The torch lightsource, however, will have 10m*10m*10m = 100m³, because it's influence radius is 5m ! This obviously screws up the whole spatial tree. What we did, is separate the tree into a flat part (with only hierarchical information, almost no spatial localization) for the lightsources, and a deep part for the rest. Then we interlinked the nodes in such a way, that this 'split-tree' can actually behave in two distinct ways, depending on how it's accessed: for the purposes of animation and rendering, it acts like one big hierarchical tree, but without spatial information. For the purpose of culling, collision, etc, it acts like two separate trees. In the end, you'll have to find the type of scenegraph management that suits your engine best. Little implementation dependent details (see our light problem) can sometimes make an approach totally unsuitable for your engine, even if it is considered nearly optimal in other cases. / Yann |
||||
|
||||
|
JimH Member since: 11/15/2001 From: USA |
|||
|
Posted - 9/21/2002 6:20:40 PM |
||||
quote: Ha! I haven’t. I’m just a hobbyist doing this at home. I’m just trying to learn because I think it’s fun and interesting. quote: Well, no. Nodes only exist as far as the Player character can see. Or rather, just beyond the far clipping plane. So assuming you’re using a quadtree, one cell (or helper node) may have less than four children if it is on the edge of sight. As the Player moves, more objects and terrain are loaded in from disk. When needed, a new cell is added to the tree. A cell is removed from the tree when a cell becomes empty. quote: True. But the way I envisioned it working, it wouldn’t matter. I’ll explain below. Note I haven’t implemented this. It’s just an idea. First, only leaf nodes contain objects. An object has a center point which represents its location. If that object’s center point is in a cell, then the object is placed in the cell. It doesn’t matter if the object’s bounding volume would extend beyond the cell boundaries. The bounding volume for a cell is then formed by merging the bounding volumes of all the objects in it if it is a leaf cell, or by merging all the bounding volumes of child cells if it is an interior cell. You would have to update bounding volumes as dynamic objects moved. So the bounding volume of a cell might be larger than the area the cell is meant to represent. To make this work, you have to ensure that individual objects are not too large compared to cell size. For the case of collision, I imagined it would be safe to only check the nine cells in the local area. But if the largest object in your scene is larger than one cell, then you might have to check the surrounding 25 cells. In general, this is a problem because object size is limited and the collision and HSR algorithms become too coupled with the cell/object size ratio. If you want to have a big castle or large bridge in your scene…well, I don’t know how to handle it with this structure. It’s a problem and perhaps the biggest reason I’d like to ditch it in favor of something else. As for two objects that are spatially close but being in totally separate trees: I planned on doing all searching from the root down anyway. For example, when doing collision detection on the Player character, you would find the Player’s current cell based on its position. Then you could calculate the surrounding eight cells. So in Yann’s example, if the Player is in cell 1.2.2.2, you know that 2.1.1.1 is one of the adjacent cells and you need to find that cell and check it for collision detection of objects in that cell. So you start from the root of the tree to find cell 2.1.1.1. I never expected the tree to be that deep. The depth is really only dependent on the clipping distance. Therefore I expect that searching to find any cell is quick (log n). Another big problem with this approach is that the size of a terrain patch ends up being coupled with the size of the leaf cell. It would be nicer if they were independent. Having said all that, I also didn’t see how you solve these problems with the traditional scene graph in Yann’s first diagram. If you have the terrain organized as a quadtree in its own node and you have the static objects as an octtree in its own node, you still have the same situation. Terrain and static geometry might as well be in their own trees. You haven’t bought much by slapping them under the root node of the scene graph. You just push the problems further down. So the only place you’ve solved those problems is in the dynamic objects which aren’t spatial organized. quote: I’m not sure I understand how your tree works. I thought maybe I shouldn’t ask you any more about it if it’s proprietary information. But then I guess you can always decline to answer if you want. I couldn’t tell if, for each node, you are dividing space in half or the list of objects in half. (That is, does one branch of the root node contain all objects with a location X > 0 and the other branch all objects with a location X < 0? Or does one branch contain the northern-most half of all objects and the other branch the southern-most half of all objects.) I would guess the latter, that you are dividing the list of objects in half at each node; otherwise you’d still have the fault line problem. Although, I don’t know how you’d do that in 3D space. I guess I really don’t understand it.quote: So it sounds like you understand Yann’s graph, since you pointed out a possible problem with it. I downloaded the Eberly chapter on scene graphs. I skimmed through it and, unless I missed it, I didn’t see any discussion about how things are organized spatially. I did notice that scene graph nodes are derived from a class called Spatial, but there isn’t any more relevant detail about the Spatial class in that chapter. quote: As I mentioned above, I was thinking that objects would appear in the tree only once. They are in one cell or the other. But their bounding volume may extend outside of the cell boundary. So cell boundaries are not hard and fast rules, they are more like hints for collision and HSR. It’s the merged bounding volumes that are the hard and fast rules. And, of course, this approach causes its own set of problems.  The whole issue seems a lot like just a sorting problem. The way you sort things depends on what you want to do with them. For example, in a telephone book you can sort people according to their last name or according to their address. It depends on what you want to do. If you want to find the numbers all people on your street, then the latter organization would be better. The problem with scene graphs—at least as it seems to me—is that you are trying to find a single organization but you want to perform multiple operations on it. Those operations are contrary. It’s like trying to use a normal phone book to find the numbers of people by last name and also by address. You can have a kind of secondary sort order (and that what I think is going on in all the examples in this thread). But I also might give some thought to having different trees/graphs for each purpose. One for collision and culling that is organized spatially and another for state and object hierarchy. They would ultimately point to the same objects. Oh, well, just a wild thought. [edited by - JimH on September 21, 2002 6:30:35 PM] |
||||
|
||||
|
ZenoGD Member since: 3/2/2002 From: San Diego, CA, United States |
|||
|
Posted - 9/21/2002 10:14:40 PM |
||||
Lots of stuff to respond to here.quote: It's funny cuz I actually did exactly that in one of my programs. When I was making the post, I had a different (older) project of mine in mind where I hadn't solved this problem. That'll teach me to post late at night quote: Actually, I'd like to add to JimH's response to this. If you have a structure with a fixed number of nodes per level (i.e. a quadtree of a bintree) and a fixed depth, it's possible to just put all the nodes in an array and make a small function to look up the array index. For instance, given your current level and cell, you can look up the index for the cell at the same level directly to your north...there's no need to go hunting through the tree then. You can also use a formula to look up children, thus saving having to store pointers to them. quote: Yes, I think I understand it pretty well. I'll try to explain an example based on a binary tree: Given your whole scene, create a hierarchy of bounding nodes around it. Start with a large node that can hold the whole world. Split the world in half along one spatial dimension and put each half in one of the child nodes. Repeat this process, alternating spatial split dimensions, until you are satisfied with the amount of stuff in each of the leaf nodes. In this scheme, objects are only stored in leaf nodes, the rest are just helpers. Alternately, you could split things in half by number of objects instead of by space, which is probably a better idea unless things are evenly distributed, but it's a bit more complicated since you'll have to decide HOW to split your objects into two spatially separate groups...this may be nontrivial or not even possible, I think. Now, if one of your objects moves, the first thing you do is move that object's bounding volume (say a sphere) by the same amount and set a flag in the node to indicate that it has moved. At some later point, when your traversing your tree, when you return from recursing into a flagged (moved) node, you have to check to see if that flagged sphere still fits in the current bounding sphere (the moved sphere's parent). If yes, you're ok. If no, you have to re-create that bounding sphere based on it's children. The problem with this method is what I mentioned above (and what Yann proposed a solution to). That is, your tree can become entangled. When you start your tree, everything is nice and nothing that's in one branch overlaps with anything in another branch....not so after things have moved. -- Zeno [edited by - ZenoGD on September 21, 2002 10:16:05 PM] |
||||
|
||||
|
JimH Member since: 11/15/2001 From: USA |
|||
|
Posted - 9/23/2002 4:29:37 PM |
||||
| I think it started to click for me. The way to use the traditionally scene graph started to make sense to me—the scene graphs such as the one Yann diagrammed, the one in the Eberly book, the one in Open Scene Graph and OpenGL Performer, etc. I was out running the other night and that’s when it hit me. I guess it’s all that blood flowing to the old brain box. You need to make the hierarchy of the scene graph work for you. Use helper nodes to group objects and their bounding volumes. For example, say you have 100 trees in your scene and you put them all under the root of your scene graph. Then when you want to check for collisions, you need to check all 100 trees even if most of them are not close. This makes the graph flat; it’s more like a list. But then what you can do is take every 10 trees—trees that are spatially close to each other—and group them in a helper node. Now under your root node you have 10 nodes instead of 100. Then when you check for collisions, you still have to check all the children of the root, but there are now only 10 nodes. Most of them will be rejected. If that is still too flat, you can group helpers nodes inside other helper nodes. You can keep grouping objects this way to get the shape of the graph you want. That may seem obvious. I guess the reason this wasn’t clicking for me at first was because I was thinking that if you used such helper nodes, that you had to somehow dedicate them to a particular space. In other words, the helper nodes would have to divide up the space the way nodes in a quadtree or octtree do. But you don’t need to do that. I don’t know how practical this implementation will end up being. But it makes me think of a lot of possibilities. You can determine which objects need to be grouped at design time. I imagine you could even build some code to optimize your graph structure. It could go through and add helper nodes to deepen your hierarchy in places where the graph is too flat. You could also choose to place dynamic objects that move all the time—such as the Player or NPC characters—in the root node. That way you don’t have to update as many bounding volumes as they move around. Static items can be placed deeper. Well, anyway, this is good enough for me to move forward although maybe I’m still not absolutely sure about how to handle the original question: how terrain should be put into the scene graph. But I think I’m leaning toward putting individual terrain patches into the graph rather than putting the whole terrain in as a single node. If there is any special case stuff for terrain that needs to be done (like a special kind of LOD) that can be handled orthogonally within the “terrain node” class. [edited by - JimH on September 23, 2002 4:35:09 PM] |
||||
|
||||
|
TerranFury Member since: 2/19/2001 |
|||
|
Posted - 12/18/2002 4:52:25 PM |
||||
| The scenegraph is just a nice unified data structure to keep track of everything in your world, including the world itself. It's probably not too useful for rendering, but for game logic, AI, and physics, it's a wonderful tool. Use them. Just don't make the mistake of calling them magic HSR bullets like so many people, because it'd be a stretch to try to use them for anything like that. |
||||
|
||||
|
Zemedelec Member since: 4/30/2002 From: Bulgaria |
|||
|
Posted - 12/19/2002 4:50:52 AM |
||||
quote: There is a sense in what you said, I agree. But how you see a SG to be used by AI or physics? What is advantage here compared to distinct CD data base and distinct.. say Lights' SG. Easy traversal? One commercial engine I used, relies on its SG mainly for frustum culling and material/lighting properties propagation. And it was tree (like almost any other SG by the way). Properties propagation seems good at first, but after som troubles I decided it is evil. For example attaching light to some subtree and thus lighting it is just unnatural. Just easy to observe from a design point of view, but impractical in reality imho. Btw, see 'Need some help with scenegraph/octree concept' thread. |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
