Why not implementing Octrees BSP-trees Terrain etc. as objec

What it says on the tin: a place to discuss proposed new features.
balu
Gnoblar
Posts: 1
Joined: Sun Aug 08, 2004 6:24 pm

Why not implementing Octrees BSP-trees Terrain etc. as objec

Post by balu » Thu Sep 02, 2004 11:23 am

Hi!

I just wonder why the octrees,bsp-trees and terrain etc. are not implemented as objects that can be added to a scene manager, instead of creating special scene managers for such objects?
Then it would not be a problem to add as many terrains and bsp-trees etc. as necessary!

Never mind! :)

balu
0 x

User avatar
ggambett
Kobold
Posts: 32
Joined: Tue May 25, 2004 3:03 pm
Location: Montevideo, Uruguay

Post by ggambett » Thu Sep 02, 2004 2:54 pm

Funny, I was going to post a similar question after reading today's posts :) What's the advantage of a specialized Terrain scene manager when what they do after all is create renderables? Why not use the Octree manager (not its Terrain subclass) and add patches as objects, taking advantage of the culling done by the octree?
0 x
Gabriel Gambetta
Mystery Studio - Home of Betty's Beer Bar and Wild West Wendy

janders
Gnoblar
Posts: 15
Joined: Wed Oct 09, 2002 12:13 am
Location: My backporch, Minnesota

Post by janders » Thu Sep 02, 2004 4:50 pm

What's the advantage of a specialized Terrain scene manager when what they do after all is create renderables?
Well, there is a little bit of additional book keeping going on. For instance, each terrain tile needs to know who it's neighbors are, so it can stitch the tiles together when they have a different LOD. The SceneManager seems to me the place to do this. BSPs and Octrees have similar book keeping to do.

Jon
0 x

User avatar
ggambett
Kobold
Posts: 32
Joined: Tue May 25, 2004 3:03 pm
Location: Montevideo, Uruguay

Post by ggambett » Thu Sep 02, 2004 5:18 pm

janders wrote:For instance, each terrain tile needs to know who it's neighbors are, so it can stitch the tiles together when they have a different LOD. The SceneManager seems to me the place to do this.
Why not let a PatchManager (such as the NaturePatchManager) insert the patch renderables into some scene manager (to take advantage of octree culling, for example) and do the book keeping? The NatureSceneManager is quite shallow as a SceneManager, after all, and you could get the benefits of the Octree manager for the other meshes in the scene.
0 x
Gabriel Gambetta
Mystery Studio - Home of Betty's Beer Bar and Wild West Wendy

User avatar
Noiprox
Halfling
Posts: 64
Joined: Mon Apr 05, 2004 6:25 am
Location: North Vancouver, Canada

Post by Noiprox » Thu Sep 02, 2004 6:17 pm

I have always felt that having to write a custom SceneManager that combines two or more of BSP, Octree, Terrain or other algorithms is a clumsy way of doing it. It is a case of square peg --> round hole. Having them merely be "objects" seems a little too little as well, though. Maybe we just need something above SceneManager, a SceneManagerManager? :)
0 x
Dieter Buys
Image
"Death, be not proud, though some have called thee mighty and dreadful, for thou art not so." - John Donne

User avatar
Antiarc
Greenskin
Posts: 120
Joined: Thu Jan 23, 2003 8:40 am
Contact:

Post by Antiarc » Thu Sep 02, 2004 6:47 pm

Noiprox wrote:I have always felt that having to write a custom SceneManager that combines two or more of BSP, Octree, Terrain or other algorithms is a clumsy way of doing it. It is a case of square peg --> round hole. Having them merely be "objects" seems a little too little as well, though. Maybe we just need something above SceneManager, a SceneManagerManager? :)
Well, that's what the MultiSceneManager was going to be. Dunno how far it got.
0 x

User avatar
ggambett
Kobold
Posts: 32
Joined: Tue May 25, 2004 3:03 pm
Location: Montevideo, Uruguay

Post by ggambett » Thu Sep 02, 2004 7:38 pm

I see the point of having a BSP scene manager since it can do meaningful stuff with the objects it contains and the "scene data" (for example cull the movable objects using the BSP's visibility data).

But it doesn't seem so natural when applied to the terrain manager; at least with the NatureSceneManager, which I'm heavily hacking lately, which doesn't do anything besides adding a new renderable type for the patches and delegating the rest to the generic scene manager.

I decided to remove the SceneManager part of the NatureSceneManager and just have a PatchManager to add the renderables to the Octree manager, but I wanted to ask this question first, to see if I was missing something important. I know the Nature plugin retesellates the patches based on camera position but I prefer to do that (calls) manually and be free to use the tessellation algorithm (the valuable part of the Nature manager, IMO) with the Octree manager.
0 x
Gabriel Gambetta
Mystery Studio - Home of Betty's Beer Bar and Wild West Wendy

User avatar
Noiprox
Halfling
Posts: 64
Joined: Mon Apr 05, 2004 6:25 am
Location: North Vancouver, Canada

Post by Noiprox » Thu Sep 02, 2004 9:59 pm

Antiarc:
Indeed it was, but I was saying:
Noiprox wrote:... a custom SceneManager ... is a clumsy way of doing it.
I just don't like the idea of castrating the SceneManager interface and forcing a different structure in its place, and then delegating to the SceneManagers anyway. I am proposing something that there be something above individual SceneManagers, something that fulfills the role that they currently play, but which acts like MultiSceneManager in that it has a list of SceneManagers to which it delegates as needed. In most applications, the list would contain only one SceneManager.
0 x
Dieter Buys
Image
"Death, be not proud, though some have called thee mighty and dreadful, for thou art not so." - John Donne

User avatar
Kencho
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 4011
Joined: Fri Sep 19, 2003 6:28 pm
Location: Burgos, Spain
x 1
Contact:

Post by Kencho » Thu Sep 02, 2004 11:16 pm

The mission of SceneManager's is managing scenes (quite obvious, right?). If you have a SuperSceneManager that manages SceneManagers, then what's the mission of scene managers? After all, the SuperSceneManager would manage the whole scene, just splitting the scene in other sub-scenes, but it's still managing the scenes.
I think that there is a mid-way between both ideas: A scene manager that splits the scene into subscenes, and then using different objects/implementations (Bridge pattern, or maybe Strategy pattern) to treat each sub-scene.
Don't forget that you create classes with certain objetives in mind. If you do another class that already does that work, why using two instead of just one? If you have two classes doing the same, then someone would suggest merging them, and reaching the starting point again ;)
0 x
Image

User avatar
Noiprox
Halfling
Posts: 64
Joined: Mon Apr 05, 2004 6:25 am
Location: North Vancouver, Canada

Post by Noiprox » Fri Sep 03, 2004 7:48 am

I took a closer look and can now be more specific.

I was not proposing a SuperSceneManager. MultiSceneManager is the SuperSceneManager. What I am proposing will not do what SceneManager does. I don't know if this is necessarily the best way to go about it, but I think it is at least worth considering:
Root currently has only a single SceneManager. Why not turn that pointer into a list? That way, one could simply add as many different SceneManagers as desired, or have only one. I know it might be interface-breaking, although I can suggest a way that it would not be. Keep SetSceneManager() in the interface, just make it delete the list of SceneManagers and replace it with the one passed in. Add new methods to Root for adding and removing SceneManagers to/from the list.
0 x
Dieter Buys
Image
"Death, be not proud, though some have called thee mighty and dreadful, for thou art not so." - John Donne

Lioric
Google Summer of Code Mentor
Google Summer of Code Mentor
Posts: 295
Joined: Fri Aug 06, 2004 10:25 pm

Post by Lioric » Sat Sep 04, 2004 12:44 am

In another engine, i implemented the bsp and the octree methods as object specific, i mean, the object was loaded like all other objects (3d objects, i mean), but the are processed as bsp or octree(each object had aflag), using the bounding box to see if the bsp scene is in the viewport and doing the render optimizations, that way i was able to have a terrain and a bsp map in the same scene

Lioric
0 x

User avatar
Kencho
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 4011
Joined: Fri Sep 19, 2003 6:28 pm
Location: Burgos, Spain
x 1
Contact:

Post by Kencho » Sat Sep 04, 2004 12:07 pm

I think I understand where you're trying to go. But doing that way, you still need a way to choose one or more of the scene managers from the list. The problem is that task being responsability of the scene manager too. If you keep an eye on what I'm proposing, it's simply the same, but the list is stored in the SceneManager. The scene manager is still creating/destroying objects, changing the sky boxes/domes/planes, modifying the ambient light... but also having a list of "sub SceneManagers". The SubSceneManager just handles the optimizations of the scene manager (BSP sorting, Octree culling...). This way, you don't need to modify any API, and the responsability of managing the scenes is still of the SceneManager ;)
In any case, the solution you proposed is valid, I just suggest reallocating the list in another place :)
0 x
Image

User avatar
sinbad
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 19265
Joined: Sun Oct 06, 2002 11:19 pm
Location: Guernsey, Channel Islands
x 2
Contact:

Post by sinbad » Sat Sep 04, 2004 4:07 pm

SceneManagers are there so that you can alter the way that the scene is structurally managed, and to handle world geometry. They allow you to specialise the way nodes work, the way cameras work, the way the render queues work, how scene queries are answered (both for simple moving objects and for world geometry) and basically implement any kind of scene strategy you like. No limits.

TerrainSceneManager and NatureSceneManager don't exploit much of this potential behaviour, but they do some. Nature implements it's own quadtree, TerrainSceneManager does a little extra processing at certain points in the scene rendering process, implements a specialised RaySceneQuery to do terrain collisions, but otherwise inserts fairly standard renderables into the scene.

Sure, it's possible that TSM could be implemented just as a provider of renderables. But that wouldn't solve the world geometry querying issue. It so happens that the TSM's world geometry can be rendered simply by re-using the Octree's nodes, but that's a happy coincidence. The ability to specialise other features regarding the world geometry is still very useful.

As an aside, a list of scene managers makes no sense unless one 'super' manager organises them all. When performing things like scene queries, it's important that there is one optimal way of answering, even if that involves delegating to others - some class must decide when enough is enough, to avoid potential ambiguity / disagreement / endless cascade that would likely occur when dealing with an arbitrary list of managers.

Anyway, the thing not to lose sight of is that in most scenes, there is a strong linkage between the structural organisation of the scene, and the immovable 'world geometry' that goes with it. That's why SceneManagers exist - to exploit that. The fact that TSM doesn't need to specialise so much to render a basic terrain is neither here nor there - the requirement to perform specialist operations on the world and on world geometry still remains. We already have a specialised RaySceneQuery, and in the future , paging will be added and that paging could also affect the movables (movables on pages which are being expired may as well be made invisible or ignored). Such changes affect more than just the terrain tiles, and the need to do this stems from the fact that you're dealing with a terrain-structured scene. It is the focal point, the underlying structure to the scene; and that pervades far more than the simplicity of the rendering belies.

You need to not get lost on the implementation details of a particular SM, and make conclusions about how it could be redesigned from the current usage, but look at the overall conceptual structure and how it might be used.
0 x

Vectrex
Ogre Magi
Posts: 1266
Joined: Tue Aug 12, 2003 1:53 am
Location: Melbourne, Australia
Contact:

Post by Vectrex » Sun Sep 05, 2004 3:17 am

"It is the focal point, the underlying structure to the scene"
not always, I mean the most common type of scene in games at the moment is a combo terrain and bsp indoors seamlessly combined. This is in just about every second game to come out but doesn't have a nice way of dealing with it in ogre.
Lioric's idea sounds nice though. Object specific delegation to one of the loaded scene managers.
0 x

User avatar
Kencho
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 4011
Joined: Fri Sep 19, 2003 6:28 pm
Location: Burgos, Spain
x 1
Contact:

Post by Kencho » Sun Sep 05, 2004 9:40 am

Errr.... it's exactly the same. What's the difference between the scene management done in those games and the one done with OGRE? After all, they just go through sub-scenes that are managed by different algorithms. A scene manager that manages sub-scenes using different optimizations does that and it's fully compatible with ogre.
It's like saying that you need a whole different programming language that manages different conditions in the same sentence, because 'switch' can't do that!

I know I'm not good with explanations, but I'm sure someone else has understood what I told :)
0 x
Image

User avatar
sinbad
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 19265
Joined: Sun Oct 06, 2002 11:19 pm
Location: Guernsey, Channel Islands
x 2
Contact:

Post by sinbad » Sun Sep 05, 2004 4:42 pm

Exactly. Indoor / outdoor combos can be done any number of ways, one of the most popular being a portal basis, but for example UT2004k uses Bsp all the time, even for outdoor areas.

No matter what your scene, the core SceneManager still represents the the toplevel structure of the scene, and whether you choose to have sublevels (delegation to Bsp / Octree perhaps) or do it like UT2004k, it's still very much a stretegic decision. Just trying to patch together multiple SMs arbitrarily with no overall management strategy is just not going to scale well. My point that there has to be one overall 'controlling' strategy, even if some detail is delegated, remains. Nobody has written a public SM that can do both indoor and outdoor yet, but they do exist (Jeff Leigh's portal manager for example). The absence of a public example does not in any way mean it cannot be done.
0 x

Vectrex
Ogre Magi
Posts: 1266
Joined: Tue Aug 12, 2003 1:53 am
Location: Melbourne, Australia
Contact:

Post by Vectrex » Mon Sep 06, 2004 2:09 am

well seeing as I don't ACTUALLY know what I'm talking about I won't argue ;) I understand that it's perfectly possible in ogre, I guess I'm just thinking it's a pity the existing scene managers are quite seperate at the moment. But no doubt there will be some projects that will combine them properly (and no I can't do one myself as I'm just a script monkey ;) )

btw who wants a gmail account?
0 x

jonnii
Halfling
Posts: 81
Joined: Sat Jun 19, 2004 1:10 am

Post by jonnii » Mon Sep 06, 2004 2:29 pm

surely if the world geometry was a node in the scene graph then it could be responsible for managing its own geometry data and returning the necessary renderables. equally it could interpret collision queries however it wanted. personally i feel that the a scenegraph should be a representation of the scene heirachy and not directly coupled with any particular HSR technique or responsible for collision detection, but that should be the job of each individual node.

if each node was responsible for it's own HSR then you could just drop in a terrain (which could use a quad tree), a village (which could use a bsp or an abt) and entities which could just use simple frustum culling or be grouped into one octree (for example).

you would still retain the heirachial structure of the scene graph by using the Kd tree structure you already have but remove the spacial aspect by making each node (or group of similar nodes) responsible for their own HSR.
0 x

User avatar
sinbad
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 19265
Joined: Sun Oct 06, 2002 11:19 pm
Location: Guernsey, Channel Islands
x 2
Contact:

Post by sinbad » Mon Sep 06, 2004 5:48 pm

What you propose sounds fine in theory, but it just doesn't work well in practice. The fact is that world geometry is used as a basis for the location and partitioning of far more than just it's own data.

In your terrain / village example, if asking for the results of a ray query (looking for moving objects for example), who do you ask? If the world is just one node-soup, with a complex village (with large interior areas), how do you propose to efficiently identify which nodes to ask in what order? Is a moving object that enters a room in the village managed by the village bsp, or by the terrain? Or both? If one or the other, what determines when ownership changes? These are not simple questions when you allow any node to do any management strategy. It's possible you could implement a basic controller SM over the top (say octree based), which delegates to the sub-elements, but this only works well if the bounds of the areas managed by the sub-scenemanagers don't overlap much (thus distinction between one or the other is bounds based). There are other techniques which might be more appropriate to make the sub-scenemanager distinction, like coarse area portals. Or perhaps a combination would work best - coarse bounds test plus portals. The point is that by doing it our way, the 'master' and the subsequent delegation can be implemented whichever way suits best. Just implementing a node-soup to delegate is frankly naive.

When you impose a structure upon it, and a hierarchy of responsibility, it can work. For example, lets say the terrain is the 'master' (because it's big), and the village is the 'slave'. When doing a query, if you're outside already, the terrain 'asks itself' first, and if it intersects the village before the terrain, then it delegates to the village scene manager to finalise the query (or return it back). It's a drill-down rather than a free-for-all. If the origin of the ray is in the village already, then the delegation starts immediately, and the terrain only checks if you shoot out an external portal. There's a subtle difference, but the key thing is the distinction between the controlling scene manager and the children it might delegate to makes it efficient.

Using a general set of nodes, it's impossible to know who to ask without knowing the details of the implementation - in essence I imply from your post that you'd be asking all of them, perhaps based on bounds. That's inefficient (say when your ray query does not shoot out a portal from the village - but you've already queried the terrain too because you don't know how to detect that case), and can give you ambiguous or redundant results in more complex cases.

Actually, your example is talking about bsp/abt/kdtree/octree - and that can make sense because they're all partitioning along similar bases, so they could play nice together. But actually, that's a special case - other scene managers may not partition in such a friendly way (e.g. racing game SMs are prone to use 'tube' managers). We probably have similar ideas, but you're thinking of it from a particular angle (combine octree/kdtree/bsp) which can work, but I think of that as a special case of a SM which is able to delegate well, whilst the general SM case may not.

So, in my world view there should be a 'composition friendly' SM subclass which can do what you ask (this is pretty much what I've been talking about all along). But to make a SM 'composition friendly' actually imposes restrictions on it (for it to work well - node soups don't), which I don't want to do for the generic SM interface, which is why this should be a specialisation, not the norm.

Hope that made sense...
0 x

User avatar
Noiprox
Halfling
Posts: 64
Joined: Mon Apr 05, 2004 6:25 am
Location: North Vancouver, Canada

Post by Noiprox » Mon Sep 06, 2004 7:53 pm

Sinbad's arguments are convincing. I see that simply a list of SceneManagers is not enough, and that the code involved in deciding which SceneManager to delegate is specific to the algorithms and data structures employed by each individual SceneManager, and thus cannot be implemented generically in Root, nor a MultiSceneManager. A MultiSceneManager could be handy, but it would be sub-optimal in many cases.

I also see that the bullet must be bitten and a single SceneManager which supports both indoor and outdoor scenes with portals for transitions would have to be implemented as a whole to achieve optimal efficiency. Seeing as such a SceneManager is in very high demand, perhaps it should be made a priority for us in the OGRE community to implement? That is, unless Jeff Leigh plans to release his publically.

Heh, sorry, it's almost silly how often we are called to arms. So much to do, so little time...
0 x
Dieter Buys
Image
"Death, be not proud, though some have called thee mighty and dreadful, for thou art not so." - John Donne

jonnii
Halfling
Posts: 81
Joined: Sat Jun 19, 2004 1:10 am

Post by jonnii » Mon Sep 06, 2004 10:02 pm

sinbad wrote:
The fact is that world geometry is used as a basis for the location and partitioning of far more than just it's own data.
This i agree with, but that is the purpose of the scene manager, to create a heirachy that doesnt impose a certain HSR method and therefore limit the "drop in" nature of the system.
sinbad wrote:
In your terrain / village example, if asking for the results of a ray query (looking for moving objects for example), who do you ask?
The way in which i would handle ray queries would be by working down the tree starting from the entity from which you want to cast the ray. You would continue to the base of the scene graph looking for intersections or stop after you found one depending on the cirumstances...
sinbad wrote:
If the world is just one node-soup, with a complex village (with large interior areas), how do you propose to efficiently identify which nodes to ask in what order?
I dont like to think of the system i described as being a node-soup as it would have heirachial information, the scene graph, but that wouldnt impose the way in which those nodes are rendered.
sinbad wrote:
Is a moving object that enters a room in the village managed by the village bsp, or by the terrain?
A moving object entering a room would move down the tree from the terrain into the house. The house would then be responsible for the moving object.
sinbad wrote:
Or both? If one or the other, what determines when ownership changes?
This is a question i have been pondering myself recently =) I believe that it is down to the entity that moves to decide where it belongs. When an entity moves it will: stay the child of the current parent node, move up the tree, move down the tree. I need to think about htis one more as i would like to keep my idea of a scene graph seperate from that of a spacial relationship between entities.
sinbad wrote:
These are not simple questions when you allow any node to do any management strategy. It's possible you could implement a basic controller SM over the top (say octree based), which delegates to the sub-elements, but this only works well if the bounds of the areas managed by the sub-scenemanagers don't overlap much (thus distinction between one or the other is bounds based). There are other techniques which might be more appropriate to make the sub-scenemanager distinction, like coarse area portals.
Would these need to be hand placed? I think the process of handing placing portals is tedious and something that should really be avoided.
sinbad wrote:
Or perhaps a combination would work best - coarse bounds test plus portals. The point is that by doing it our way, the 'master' and the subsequent delegation can be implemented whichever way suits best. Just implementing a node-soup to delegate is frankly naive.
This i agree with, a node soup is indeed a naive solution to the problem, but i think there should be a distinction between the spacial information in a scene and the relationship/ownership of entities.

I'm currently implementing my own scene graph structure in my engine and have decided to keep the idea of the scene graph seperate from that of the HSR and collision. I'll see how it goes and report back when i know.

Currently my biggest problem is trying to keep the spacial information seperate. Currently when it comes to submitting entities for rendering i'm working down the tree and rendering at each level so that i can reduce the amount of matrices that i need to multiply. This isnt working so well, so i'm thinking i might need to start caching parent matrices and forcing children to update when a parent node moves... however this is once again making my spacial information public. I think the scene graph is one aspect of computer graphics that is currently heavily in debate with the people that have the best solutions keeping them very close to their chests.

Anyway, i just thought i'd stir up the discussion a little bit :D[/code]
0 x

User avatar
Noiprox
Halfling
Posts: 64
Joined: Mon Apr 05, 2004 6:25 am
Location: North Vancouver, Canada

Post by Noiprox » Tue Sep 07, 2004 4:49 am

So you have a scene graph that does not contain spatial information? Fine, but that leaves the rendering and collision-detection optimization problems unaddressed. You do seem to mention that your scene tree does have connectivity information. How else could a ray be propagated down the tree, from the terrain to the house? What is such connectivity information if not topological (i.e. spatial)? How would you know when to send the ray "down" or "up" the tree without any spatial information? What is more, there are cases where a tree is not sufficient to represent the topology, particularly when connectivity is cyclic. The simplest case is illustrated by the following example: Consider a room with a mirror in it. The mirror refers back to the room, so you have a node referring to itself, which is not possible in a tree.

Portals need not be placed manually, and good tools can reduce the burden of manual portal placement considerably. It is hardly a gargantuan task even in the worst case, is it?
0 x
Dieter Buys
Image
"Death, be not proud, though some have called thee mighty and dreadful, for thou art not so." - John Donne

jonnii
Halfling
Posts: 81
Joined: Sat Jun 19, 2004 1:10 am

Post by jonnii » Tue Sep 07, 2004 5:18 am

Noiprox wrote:
So you have a scene graph that does not contain spatial information? Fine, but that leaves the rendering and collision-detection optimization problems unaddressed.

[\quote]

To render stuff you walk the tree and for each entity you find out if it is visible and if it is you request its render operation from a function that takes the current camera, just like in ogre.

As for collision detection i havn't thought enough about that yet to give you a proper answer.
Noiprox wrote:
You do seem to mention that your scene tree does have connectivity information. How else could a ray be propagated down the tree, from the terrain to the house?

[\quote]

I never said that the tree doesnt contain connectivity data. Surely all trees contain connectivity data otherwise they arent trees! I said that they dont contain any spacial data.
Noiprox wrote:
What is such connectivity information if not topological (i.e. spatial)?

[\quote]

A good example of this would be a man holding a gun, where the gun would be a child node of the soldier.
Again that depends, however i agree that portals are definitely a good space partition technique and would make the implementation of an interior/exterior scenemanager a hell of a lot simpler.
0 x

User avatar
Noiprox
Halfling
Posts: 64
Joined: Mon Apr 05, 2004 6:25 am
Location: North Vancouver, Canada

Post by Noiprox » Tue Sep 07, 2004 7:25 am

jonnii wrote:To render stuff you walk the tree and for each entity you find out if it is visible and if it is you request its render operation from a function that takes the current camera, just like in ogre.
So you traverse the entire tree and query every single node individually about whether it is visible or not for every frame? This is like having no SceneManager at all. The reason we have SceneManagers specialized to use particular (spatial) data structures is to optimize scene queries so that we do not have to test every individual object.

jonnii wrote:As for collision detection i havn't thought enough about that yet to give you a proper answer.
Collision detection is very similar to rendering as far as the SceneManager is concerned. The main difference is merely that we are peforming a frustrum cull instead of a ray intersection.

jonnii wrote:I never said that the tree doesnt contain connectivity data. Surely all trees contain connectivity data otherwise they arent trees! I said that they dont contain any spacial data.
I didn't say you said the tree doesn't contain connectivity information. I said your connectivity information is spatial.

jonnii wrote:A good example of this would be a man holding a gun, where the gun would be a child node of the soldier.
That example does not illustrate the rendering problem very well, though. According to your previous example, does the house belong to the terrain in the same way as the gun belongs to the man? If that is the case, then does your tree have anything to say about where the house is relative to the terrain? If yes, that's spatial information. If no, how can you render or perform collision detection on that structure without knowing the position of the house?

jonnii wrote:This depends on what kind of query you are doing. If you are shooting a ray from the camera you would work down the tree starting from the root, if you are checking to see where a current object would intersect the world by casting a ray downwards you would work up the tree from that node.
Ok, suppose the man with the gun is inside the house and fires a bullet. The bullet is a child of the gun (?) which is a child of the man which is a child of the house (?) which is a child of the terrain. The bullet hits a plant in the house. How would you ever visit the plant node if you are travelling up the tree only? Here is an attempt at an ASCII illustration.

Code: Select all

   Terrain
      ^
      |
    House
     ^ \
    /   ?
  Man   Plant
   ^
   |
  Gun
   ^
   |
 Bullet
Or, for that matter, what if you are standing in the terrain and you shoot a bullet into the house? Obviously you can't reach the house by going up from the terrain.

jonnii wrote:This i think is a bad example as a reflection is just a rendering trick. A mirror is a physical object so it would just be a member of the room. There is no way round having cyclic connectivity, so i think the easiest way is just to avoid it.
Well, pardon me, but I thought this whole thread is about using scene managers for rendering. :roll:
Ok, how about a magic portal then? I mean the kind of thing that you can step through that transports you to another place. That has a physical significance in the game and can affect collision detection as well as rendering.

jonnii wrote:Again that depends, however i agree that portals are definitely a good space partition technique and would make the implementation of an interior/exterior scenemanager a hell of a lot simpler.
Yes. Portals are an intuitive concept that artists can easily grasp and apply effectively in level design, given proper tools. So what's the problem?
0 x
Dieter Buys
Image
"Death, be not proud, though some have called thee mighty and dreadful, for thou art not so." - John Donne

jonnii
Halfling
Posts: 81
Joined: Sat Jun 19, 2004 1:10 am

Post by jonnii » Tue Sep 07, 2004 3:41 pm

Noiprox wrote: So you traverse the entire tree and query every single node individually about whether it is visible or not for every frame?
Basically yes, however nodes can be marked as to whether or not you want to render their children if they are visible or not (for example you dont want to render a man holding a torch if he is not visible). However in this case you might still want to visit the children node as that torch might need to cast shadows.
Noiprox wrote:
This is like having no SceneManager at all. The reason we have SceneManagers specialized to use particular (spatial) data structures is to optimize scene queries so that we do not have to test every individual object.
I'll give a few examples to make my idea clearer.

Code: Select all


Terrain (heightmap with a quad tree)
    |
    | - Village (static geometry, octree)
             |
             | - Soldier
                      |
                      | - Gun
 
In this case your static geometry would be the terrain and the village, to perform collision detection against them you would just query the octree or the heightmap. If the plant is a piece of static geometry then you get that collision detection done when you check the village.

Now lets say that the plant is another dynamic object that you want to fall over when you shoot it. Here i am going to have to admit that i was both unclear and incorrect in my previous post (sorry :D), you would start from the root of the tree checking each node to see if it was colliding with your ray. I guess your main concern with this is that you are not optimising this query spacially, for example using an octree. This is something that i have been thinking about. For static geometry you can query the quad tree/octree/bsp that it uses for paritioning its geometry, however for dynamic objects in the tree because there is no spacial information, so one node does not necessarily "contain" its children, you cannot assume that because a ray does not intersect a particular node that it will not intersect with one of that node's children. I believe the best solution to this is to keep the collision information seperate from the scenegraph, for example is a sphere tree, and to query that when you ask an object if it is visible. So for example when you ask a dynamic object if it is visible it can ask the sphere tree for which it belongs whether or not it is visible. You can then cull this object spacially. However you still need to visit all the nodes in the scene graph, which is my main hang up with this solution might involve you visiting the same node in the sphere tree more than once. One possible optimisation is to do the same thing that you do for rendering and mark objects so that you dont have to check their children if they dont collide, however this is sort of a spacial technique and one that i have applied to rendering (as i stated above) and one that i'm not too happy about. I need to think about this aspect a little bit more and then i'll get back to you :D
Noiprox wrote:
That example does not illustrate the rendering problem very well, though. According to your previous example, does the house belong to the terrain in the same way as the gun belongs to the man? If that is the case, then does your tree have anything to say about where the house is relative to the terrain?
Again this is something that i have been thinking about a lot recently and am currently undecided. In my goal to separate the spacial information from the scenegraph i have had to try to unlean a lot of things. In my first implementation each node had a bounding box/sphere, a position and an orientation. However this is spacial information so i ended up taking it out. However surely if you have a terrain with a house on it when you move the terrain you move the house too, but this is a spacial operation so does it belong in this concept of a scene graph? When rendering you concatonate the matrices as you walk the tree, right? So if an object is renderable then it must have some way of getting a world matrix from its position/orientation... but how does that relate to its parent nodes position/orientation? Also, what abouts if you have an object in the world that you want to be able to collide with and must have a physical presence in the world but is not renderable (like a mime in an invisible box...)? Or the inverse, for example a ghost that can float through walls?

Currently my line of thinking is that as a collidable object you need some kind of bounding box and a position/orientation and for a renderable object you need the same... however the way in you check for collisions or whether or not to render the object is totally dependant on the way in which it is implemented, for example delegating to a sphere tree or working your way down an octree.

Right now i think my biggest goal is to find a way to group similar objects into seperate spacial heirachies while keeping the logical scene graph non-spacial. This should help speed up the collision and rendering processes dramatically.
Noiprox wrote:
Ok, suppose the man with the gun is inside the house and fires a bullet. The bullet is a child of the gun (?) which is a child of the man which is a child of the house (?) which is a child of the terrain. The bullet hits a plant in the house. How would you ever visit the plant node if you are travelling up the tree only? Here is an attempt at an ASCII illustration.

Code: Select all

   Terrain
      ^
      |
    House
     ^ \
    /   ?
  Man   Plant
   ^
   |
  Gun
   ^
   |
 Bullet
Or, for that matter, what if you are standing in the terrain and you shoot a bullet into the house? Obviously you can't reach the house by going up from the terrain.
Ok ok you got me. I admit i was wrong. I'm going to blame this one on late night stupour :D You will need to check the children of each node that you pass, however the idea of working up the tree is probably totally wrong anyway. It makes a lot more sense just to visit each node starting from teh root applying branch culling where appropriate (i said something about this already).
Noiprox wrote:
Well, pardon me, but I thought this whole thread is about using scene managers for rendering. :roll:
Ok, how about a magic portal then? I mean the kind of thing that you can step through that transports you to another place. That has a physical significance in the game and can affect collision detection as well as rendering.
We seem to be talking a lot about collision detection too :D However i stand by my original statement that a cyclic structure would probably not work with my system. Instead you could implement a magical portal by sticking a camera at its destination and rendering its view to a texture, which you then paint onto your portal model. I guess what you are saying is how does the camera relate to the portal, is it a child node of the portal or a child node of where it is (for example in another house, assuming you have a camera as a member of your scenegraph, which i do)? I'm not sure of the correct answer to this one, but i think the easiest way would be the latter, where you have the camera as a node in the destination. You can then create a link between the camera and portal which isnt necessarily a logical link (ie a branch of the scene graph), but a symbolic link... This is a really good question and one i'll think about more.

As you can probably guess from reading this stupidily long post this idea is relatively new to me and I am still trying to think about it and formulate my ideas. Originally I wasnt going to post in this thread as I felt it was too early to open my mouth, but i couldnt resist :D I hope to god this thread doesnt give you the impression that i'm so some kind of crazy ogre basher, which would be very far from the truth. I'm just trying to spark some debate.

^_^
0 x

Post Reply