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

What it says on the tin: a place to discuss proposed new features.
nfz
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 1263
Joined: Wed Sep 24, 2003 4:00 pm
Location: Halifax, Nova Scotia, Canada

Post by nfz »

Hey, I like long posts. There is nothing wrong with sharing your ideas because someone always benefits, like me. I am learning lots from this discussion so keep it up.
User avatar
sinbad
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 19269
Joined: Sun Oct 06, 2002 11:19 pm
Location: Guernsey, Channel Islands
x 66
Contact:

Post by sinbad »

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...
Nodes in the scene graph are hierarchical for positioning - not necessarily for spatial partitioning. It's a very important concept, and it means that SMs can implement strategies spatial which do not involve hierarchical nesting. For example, the 'tube' scene manager I mentioned is an obvious one, but the concept is generally applicable.

Cascading down a tree is a recursive algorithm and is therefore inherently prone to inefficiency as that tree becomes large. You certainly would not want to manager the entire scene by cascading all the time. Ogre deliberately does not cascade during the scene graph update unless it has to; and it makes a significant performance difference when dealing with large trees.

You're looking at it from a generic scene graph position (used in some academic systems I've seen) where the nodes contain positioning, partitioning, material settings perhaps, all in one. They're very nice in theory, but they're not very efficient in my experience, because they try to pack every concept into one structure, accessible one way (cascade). SMs need more flexibility than that. Ogre separates the concept of positioning and spatial partitioning in order to allow the SM to optimise each individually.

You can see this quite simply in the comparison of the standard SceneManager, which uses hierarchical node bounds, versus the OctreeSceneManager, which uses OctreeNode simply as a 'hook' to place objects in a completely different spatial structure which is unrelated to the positioning nodes. BspSceneManager does the same. If both were constrained to cascading down the positioning tree they would not be as efficient, since the SM needs to have the flexibility to drive all calculations from a consolidated spatial structure built from data derived from a combination of world geometry and movables.

When I said 'node soup' I was really talking about using a single scene structure to achieve all aims. I don't believe there is such a structure which allows efficient processing of all types. There are some which are more generally applicable than others (abt for example) but it is not the case that all of them can be combined in an arbitrary way and still retain their performance characteristics that made you choose them in the first place.
User avatar
Lee04
Minaton
Posts: 945
Joined: Mon Jul 05, 2004 4:06 pm
Location: Sweden
x 1

Movables objects should have it's own scene manager object

Post by Lee04 »

Sinabd said
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?

I think we should have the movable objects in there own scene manager query object. That only handles the movable objects. This way we can disregard the problem of having an movable object moving and bellonging to different BSP, octree, nature scene manager objects.


In the end the user won't see that the movable objects are handled sepratelly.
User avatar
sinbad
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 19269
Joined: Sun Oct 06, 2002 11:19 pm
Location: Guernsey, Channel Islands
x 66
Contact:

Post by sinbad »

I disagree entirely - you need to exploit the given partitioning / organisation of the specific scene manager (octree / bsp) to make queries fast in the first place. They cannot be separated.
User avatar
Lee04
Minaton
Posts: 945
Joined: Mon Jul 05, 2004 4:06 pm
Location: Sweden
x 1

Adding movable objects into the mix ofmixed scenemgrs is bad

Post by Lee04 »

Well I don't know a first thing about Ogres query system.
That said I can't figure out the reason why a otherwize so object orgented engine wouldn't have a query system for movable objects
that are seperated from static geometry. Espacially when programmers wnats to mix between, BSP, Octree, Lanscape, etc. And perhaps like my self have multiple instancies of the Octrees.

Having code that tracks and inserts movable objects in and out of each scene manager type is just wasted cycles and code and abouve all results in messier and a none object orgiented design.

And for what puropse would you like to have the movable objects integrated like that. Is it to get to know in which room / space a
movable object are in or going in between or is it just to avoid an
extra query call when you want a chunck of geometry in a given space.

// Is thsi so bad
Result1 = QueryStaticSystem(SpaceA);
Result2 = QueryMovableSystem(SpaceA);
TotalResult = Result1 + Result2;


Instead of what you are sudgesting

QueryGlobaöSystem(SpaceA);
User avatar
sinbad
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 19269
Joined: Sun Oct 06, 2002 11:19 pm
Location: Guernsey, Channel Islands
x 66
Contact:

Post by sinbad »

Because there's no merit in querying the static and movable environments separately. They both involve the same kind of query. I think you're thinking that you can somehow make the 'movable' part of the query generic across scene managers - well, you can't - not if you want it to be fast, anyway. And by having a combined query that does both, you only need one pass of the scene graph to detect both, instead of 2.

The fact is that scene quering, whether it's for static objects or movable objects, should take advantage of the scene structure for speed. That requires scene-specialised query objects. And doing them together means the same optimisations can be used together, in one pass. For example, if you asked for the 'closest hit only' on a RaySceneQuery, and you have a BSP structure, this can be answered _very_ fast for both movables and the world, by querying only a small subset. If they were separate, you'd only have the static part optimised for BSP, and the movables would have to be queried using a slower, more generic method, and then you'd just have to merge the results to get the closets one anyway. Makes no sense to me at all.

If you actually want results separately, that's what the query mask options are for, which is more flexible than a simple movable / static split in any case.
User avatar
Lee04
Minaton
Posts: 945
Joined: Mon Jul 05, 2004 4:06 pm
Location: Sweden
x 1

Well you are right

Post by Lee04 »

You are propblaly right about this it just seams like a hard feat to get different scene mangers types to work together in the same scene manger just beacuse some moveble objects are destroying the symmetry a bit.
Avihay
Gnoblar
Posts: 16
Joined: Tue Oct 05, 2004 12:17 am

Post by Avihay »

I don't belive that portals are a reasonable approach to this problem.

A good solution could be made with a MutiSceneManager, but one that does not use a tree, but rather a sort of simple (I don't know the technical term here so go with me) proximity linking/neighbour linking.
this will enforce some limitations that we could probably all live with, the obvious one is not being able to have two SceneManagers overlapping.
In the simple case of forcing all SMs to be box-shaped (like the TSM allways has to be) in a "2D"/flat world, and every SM will have only 4 immediate neighbours (corners would be the neighbour's problem), to take the village example, you would of-course have to complete the surrounding terrain in the BSP (like Sinbad had mentioned), but you would get better results than adding the whole terrain to the BSP or using a large terrain and adding meshes for all the complex structures.
You could also turn some SMs off if they aren't needed...

What about raypick and collision detection and culling?
Well, an entity node should be assigned to an SM according to his x/z position, and move from SM to SM if he changes his position to utilize the best optimization.
Raypicks that get over the edge of it's origin SM would be quarid in the neighboring SM (nothing that can't be handeld with 4 simple"If"s).
As for collisions, well if the object in question is small and noncomplex, then it could be easily moved from SM to SM but if it is complex or larg, that a seperate colition for each SM that it travels in (one of the things I'd let the programer decide).

Expanding the idea:
First thing is that it wouldn't hurt to remove the limitation on one neighborg per side. it would have great advanteges like not limiting the scene to a set size of tiles, reducing the number of tiles, or making "aggresive" LOD:
(my attempt at some ascii graphics)
+---+---+---+
|xxx|xxx|xxx|
+---+---+---+
|xxx|xxx|xxx|
+---+---+---+
|xxx|xxx|xxx|
+---+---+---+
could be turned into:
+-------+---+
|xxxxxx|xxx|
+---+--+xxx|
|xxx|xx|xxx|
|xxx+--+---+
|xxx|xxxxxx|
+---+-------+

and

+------------+
|\_infront_ /|
|_\_ of __/_|
|__\cam/__|
|___\ /____|
|____V____|
+------------+

to
+-------------+
|xxxxxxxxxx|
+--+--+--+--+
|xx|xx|xx|xx|
|xx+--+--+xx|
|xx|xx|xx|xx|
+--+--+--+--+
___|xxVxx|
___+------+

hope you get the picture...
the cost would be to do a search in a one list array that will usualy be very short, compared to searching a tree.

so far we get to the point of being able to address the most comon scene, that is bouth multiple terrains with diffrent textures and levels of details and what we human call normal scenery built from simple or complex terrains and indoor areas.

What if we want to make a building that is dug into the terrain? for that you need a terrain SM on top of a BSP SM.
What if we want a cave in a mountain? for that we would need three terrain SMs, the middle one up side down.

Top and buttom neighborgs: in this case I think it would be suficient to limit it to one neighbor for up and one for down, and here comes another limitation, the cavetop musn't pass the line between the cavetop and the cave bottom and viceversa or else...
and it also gets messier, cuz now you have to consider neighborgs's hight and I get a head aick just thinking about it, so i'd drop it at that, but i guess you get the picture.

boto
Gnoblar
Posts: 9
Joined: Tue Jan 11, 2005 10:50 am

Post by boto »

hi,

i see mixing indoor/outdoor scenes by the mean of two different scene managers is not as easy.

i would like to create an outdoor scene of size, say 1000 m2. the question is which scene manager should i use and how should i build up the world?

here my three ideas

1. i model my world in a q3-map manner, convert it to bsp and use the bsp scene manager.

- the problem is that modelling a q3-conform map means a lot of mesh geometry limitations, at least afaik (e.g. no smooth and round meshes). i would have to model all nice meshes seperately and import / place them into scene manager during startup. all in all i could live with this solution, although it is not the most convenient one for me.

2. i use the terrain manager to get the ground.

- my problem is that the terrain manager only handles the terrain, no other meshes as trees, rocks, etc. again i would have to import / place my additional meshes by hand into the scene manager.

3. i use only the octree manager, which contains the terrain ground as a big mesh, and all other meshes such as trees, rocks, etc.

- i don't know whether the octree manager can handle a 1000 m2 big scene with a river including nice fishes, trees, rocks, and some other visual suger -- i don't have any doubts on the ogre octree manager, it is rather a general question due to missing knowledge in my brain :-)


what do you mean, which way should i go?

cheers
boto
iq
Greenskin
Posts: 125
Joined: Mon Oct 20, 2003 8:25 pm

Post by iq »

That does depend on the scene (do you want it all visible at once or do you have a rather small vis range & fogging, how detailed is the ground, do you need stuff like overhangs/cliffs & caves - btw I'm sure you mean 1kmx1km not 1000m^2 ;) )

That should cut down your choices ( ie is a heighmap based scene enough, do you need paging, tiling or can you simple render the whole ground all the time etc.) Once you know what managers you can use and what features are overkill I would choose the one I can best produce content for (licensing issues aside)

With the rather small level size I'm not sure you need a full blown terrain scene manager at all ...
boto
Gnoblar
Posts: 9
Joined: Tue Jan 11, 2005 10:50 am

Post by boto »

hi iq,

indeed, i meant 1km x 1km :-)
i think the camera range will be about 500 meters. a river, partially surrounded with cliffs ( with various textures ) are in plan. the scene will be in middle of a kind of canion with one or two little caves. imaging an outdoor scene with appealing atmosphere appropriate for a virtual chat room ( i hope once with voice over ip functionality ).

cheers
boto
iq
Greenskin
Posts: 125
Joined: Mon Oct 20, 2003 8:25 pm

Post by iq »

Well, octree is your safest bet then I guess - BSP is meant to speed up rendering with heavy occlusion, and heightmap terrains do not allow caves and overhangs - with the .scene format you should even have a (solid? never used it) base for the development toolchain.
boto
Gnoblar
Posts: 9
Joined: Tue Jan 11, 2005 10:50 am

Post by boto »

great, i will try that.

thanks :-)
Post Reply