Page 1 of 7

[submitted] Scene manager

Posted: Tue May 16, 2006 12:03 am
by farakon

Scene management techniques in OGRE are good, but could be better. Currently the code I v seen is using either octrees or bsp. It seems that a portal scene manager exits but is commercial. My entry would be adding an hybrid scene management technique that allows both indoor and outdoor scenes to be handled in one structure. This can be done through a hybrid BSP/portal and uses the hardware occlusion queries as well (if needed).

Why Me?
I m currently a PhD student doing a thesis in computational geometry, so I m very familiar with spatial subdivision techniques and geometric structures generation as well. I have basically implemented a basic version of this technique for the 'More OpenGL Game Programming' book by Dave Astle et al. (chapter 12 - Scene Management)

The book website where you can find information about the book and download the code is:

The basic implementation that illustrates this principle (hybrid technique that uses portal/BSP and occlusion queries) can be found in the code on the website (chapter 12).

Description of the technique

The technique requires portal meshes and a low res mesh representing the scene occluders (- it will work without problems for both indoor and outdoor - need to have a bit of attention). The mesh itself should be closed and of legal topology (note that of a requirement as legal topologies are required for shadow volumes - GPU Gems). The portals should be placed manually, where the level designer sees fit (depending on the level, but for an indoor scene like in a doom 3 level, the number of portals is usually less than 20, and it's not hard to model a plane for a portal). He will not go through linking the portals manually, that is left for the level compiler to do.

There are 2 pre-processes once the level is modelled and the portals are placed:
1. we do a CSG operation between portals and the low resolution level mesh, this is necessary to extract cells and portals adjacencies. The next thing is to build a BSP tree for this low res mesh.

2. Now we loop through the level object and for each one we can determine to what room/cell it belongs (the BSP is for that actually)

Real-time Rendering:
Once the level is loaded we have everything we need, the bsp is there to determine the room the camera is in, from that we extract the list of portals/rooms linked to the current room. Once thing I used is the hardware occlusion query for the level mesh + portals (flat shaded, no write for portals and on a small scale 1/16), the query was checked after 1+ frames and with it I could determine which rooms are visible directly, using the hardware without the overhead of occlusion query algorithms that use bounding volumes. We can use frustum culling instead of occlusion query, and thus visibility is done completely on the CPU.

Visibility extension:
The current model requires that the low res mesh of occluders is closed, but we can cheat the visibility system in case of some open holes, or open areas buy labelling the corresponding faces in the occlusion mesh as transparent so the GPU won't render them (this is when using the GPU for visibility determination)

* Each room can have its own rendering subsystem or scene management; this can be made easier using some sort of a minimal level editor in .NET to mark the properties for each room, or can be set in the level editor/modeller directly. So the previous code in ogre concerning scene management can be still used.

The same algo can be used to determine the position of other objects in the scene for other purposes than rendering, like collision detection, proximity queries...

List of deliverables:

1 - Scene management study and design: study the current available scene managers, design the portal scene manager (so we ca incorporate the octree/terrain scene managers). (1-2 weeks)

2 – BSP compiler: going to implement a solid node BSP compiler. (1 week)

3 – CSG via BSP tree: CSG between the occluder mesh and the portals. (2 weeks)

4 – Adjacency extraction and location query: extract adjacencies between the portals and cells, query the cell for each objects. (1-2 weeks)

5 – Visibility query:
a - via occlusion query (few days – 1 week)
b – Recursive frustum culling (1 week)

6 – Octree/Terrain scene managers incorporation: incorporate them as sub-scene managers (3 weeks)

project time: 10 – 12 weeks

To note that the code found on glbook site involves a BSP compiler, adjacency extraction and visibility via occlusion query. CSG was done in the modeller via an automated script (maxscript).

Asked Questions:
Q: This technique requires a pre-process step that makes dynamic scenes not possible!

The reason why to use a low res mesh is to make dynamic scene possible. As pointed earlier, this is an occlusion mesh, and the whole point of it is to reduce occlusion queries sent to the GPU. In the bounding volumes techniques (GPU gems I & II) the process for determining visibility was to render bounding volumes and as well query the state of rendered objects which leads to of query overhead although it allows dynamic scenes. In a portal based system such as the ones used in unreal based engines, or Doom 3, objects are dynamic within a limit. This limit is a cell, and a cell ranges from a room to a whole outdoor terrain.

Q: it (the technique) requires a low res scene mesh to do the CSG process, how to handle terrains or the PLSM2 where terrains can be very large? How a specific scene manager is implemented in each room? do you need to create a global scene layout mesh to do the CSG? in this case how to handle scene managers inside other scene managers (octree buildings in the middle of a TSM geometry)

A: The CSG operation is done on the low res mesh, the low res mesh is for the occluders. This mesh is modelled apart, it has to be modelled manually (a couple of boxes/low res spheres, etc...), and the portals has to be put manually too. Currently there is no practically fast and easy algorithm that can extract level skeleton and low number of portals (yes the BSP generates a lot of portals, a lot more than really needed, why check the visibility of 500 portals when we can check the visibility of just 10 without compromising the load level on the GPU). [a paper by T.K. Dey, J. Giesen and S. Goswami on the subject of segmentation can be applied to cut a mesh into submeshes (in our case cells) and maybe extracting portals, this paper can be found:, the algo would rather require an important amount of time implementing and is going to be an adventure, to note that the result is not unique and depends on parameters given by the user].
The cell is rather a container, it can contain a scene manager, of course the challenge is going to push the scene manager interface to do that, and that’s what I intend to do. Portals are there to help cull the hidden cells and other scenes, theoretically a cell with its own scene manager can have other occluders and portals, and the CSG is done on the top level of the scene manager. When the project reaches the final stage, we should be able to embed all scene managers into it, even embedding 2 portal scene managers within each other.

Q: Does it require a new and specific editor?

A: Not necessarily, the modeller will be used to make the level, an exporter will export this level, and the low res mesh is modelled in the same modeller. A level editor can be made though using .Net to save the time, and it’ll be used to place objects in the scene. I cannot promise that I can code it within time, but who knows?

Questions, comments and suggestions are welcome

Posted: Tue May 16, 2006 12:10 am
by xavier
Biggest problem I see is....

...application deadline has passed for SoC AFAIK....

Posted: Tue May 16, 2006 2:19 am
by Lioric
Thanks for the answers

If more questions/comments are made, they will be posted here

Posted: Tue May 16, 2006 8:45 am
by tuan kuranes
@xavier: it's an already submitted project...


- User Idea is to integrate dotsceneOctree (scene optimal batching oriented) with an outdoor scene management that also include some static geometry on top of heightmap (considering not only map tiles but user static geometry on that tile.).
Is there a way to handle those batching consideration when preprocessing ? Can modeler handle this using the low mesh and portals placment ? Or does preprocessor will know when partitionning is less performant than letting a room to be a big mesh ? (that would surely need preprocessor aware of the high lod mesh).

- Can you give a typical user scenario when creating a level with 2 in-door scenes being contained in a outdour scene (heightmap + forest+ etc...). From its modeler/heightmap/sceneEditor to final rendering.

Posted: Tue May 16, 2006 11:14 am
by Chris Jones
bsp is old and not that fast on modern GPUs, would it be possible for a different method to be used on indoor areas?

Posted: Tue May 16, 2006 4:47 pm
by jacmoe
Chris Jones wrote:bsp is old and not that fast on modern GPUs, would it be possible for a different method to be used on indoor areas?
BSP is very suitable for pre-processing of level geometry, especially the portal generation and pvs computation from these portals.
The underlying geometry doesn't have to be BSPed at all.

Posted: Tue May 16, 2006 6:45 pm
by sinbad
Yep, agreed, I've used this method myself. It's quite useful to store a BSP structure for the basis of further processing before grouping the results into more suitable structures for rendering. You might also want to keep the bsp structure for things like fast ray tests later even though the final geometry is not structured like that anymore. The problem with typical BSP implementations (like Q3A) is that the BSP structure is used for rendering too which results in way too many small geometry fragments.

Posted: Tue May 16, 2006 7:40 pm
by farakon
Apparently there are still some unclear issues, ok, I ll try to explain it, please bare with me :)

A: I said earlier that the final stage is making the cells some sort of containers for other scene managers, so basically it would be a top level abstraction of the level. Actually, terrain will reside in its own cell, and this cell happens to be a box with all the faces made portals. For batching I didn’t anticipate letting the cell do the batching work, nor to do it on the pre-processor side (since I want it to handle dynamic scene), so I sought it’s better to leave the cells/portal as a top level container system and for rendering push visible objects into a list where we can do more processing, for example sort by material, shaders, or any other property.

Q: Can you give a typical user scenario when creating a level with 2 in-door scenes being contained in a outdour scene (heightmap + forest+ etc...). From its modeler/heightmap/sceneEditor to final rendering.

A: There is something important I didn’t give details on: “the portals”. The portals that fall between 2 rooms, and portals that connect to a parent room. So the problem above can be remodelled as follow: One room contains the outdoor scene and the 2 indoor scenes. Portals in this case will link between the 2 indoors child cells and their parent outdoor cell. You put the objects in scene as you see fit, the pre-processor will use the BSP to determine in which cell they reside. Connectivity between cells and portals would have been done earlier after the CSG (on the pre-processor side as well). When rendering the camera position is fed to the BSP to extract the room it resides in, from there we extract visibility (which rooms are visible) (we get previous occlusion query and setup a new one for next frame), after we do frustum culling (recursive) and the objects are fed to the list. We sort this list, we feed objects to the GPU with minimal state changes, and we go again.

Q: bsp is old and not that fast on modern GPUs, would it be possible for a different method to be used on indoor areas?
A: Actually I agree with you, BSP is not sent to the GPU, the occluder (original) mesh is sent to the GPU, it’s static mesh and GPU friendly :D, BSP is used to determine in which cell the camera/objects lie, and from there you get the visible objects, close objects, etc...

I might have gone fast on some details, or I might not have given the proper answer simply because I didn’t quite understood what you mean, in such cases, please don’t hesitate to ask again :roll:

Posted: Tue May 16, 2006 9:01 pm
by Praetor
It sounds ambitious but promising. I must admit that I'm not quite sure how the system you describe works. It seems to me that the pre-processing is easily automated, and could be built into an exporter. This is great. The rest of it seems strange. Are you saying that what you are proposing is a technique to allow multiple dynamic scene managers to work simultaneously with each other? Kind of like a more advanced MultiSceneManager that runs multiple scene managers at the same time?

As an example, a regular OctreeSceneManager handles several buildings, each with their own rooms, and connected through portals, while the buildings themselves reside as children inside an even larger cell that is say, PLSM? And the player could move freely between them?

Posted: Tue May 16, 2006 11:10 pm
by farakon
Actually it’s not ambitious; the idea was rather simple, find a technique that allows you to benefit from occlusion culling on GPU if possible, in the same time not very expensive, and that can allow you to handle dynamic scenes. One of the first ideas you might get is to use bounding volume techniques, and update queries every couple of frames, downside of this technique is that it’s expensive in term of the queries sent, simply because you need to group and regroup your objects in a dynamic scene in every change. This led me to think of another way to regroup objects while still having a sort of dynamic scenes. I found that using an occluder mesh was a viable solution, this occluder mesh can be used as a way to group a large amount of objects especially if they are statically render related (visible and invisible in the same time). Next thing I didn’t want to send a lot of queries to the GPU, so y not only send portals, in that case instead of sending 1000 queries (the objects in a scene) you will only send 10-20 queries, these are the numbers of active portals in a scene! So now, you can have simple occluders per objects, per whole level and which you can group together in one mesh since they are very low res mesh (all would be << 3000 tri), send them to the GPU as one packet and only checks for 20 queries(portals only). Cells that have at least 1 connected portal visible are worth checking, if not they’re definitely invisible! Benefits: occluders can move around, except for the global level occluders, but even for those, we can actually get around this problem with some tricks (but for the moment better to assume they are static). For objects the occluders are dynamic however. Number of queries wise, the number is very low, and visibility can be check via portals connection. Objects can be of whatever nature, which is also good, they can even be whole subscenes. And before forgetting, BSP is used to get objects position in a scene and colouring the cells –I won’t go through explaining this now (the cell colouring), better u see the code ;)-

For the pre-processor, the version in the code only does BSP building and cell colouring; the code doesn’t perform CSG. The CSG is done via a script in the modeller (a maxscript). I think that this should be done however for ogre inside the pre-processor to keep the modeller code dependencies as small as possible, but we’ll see regarding the time we have and priorities.

For the reason y the manual portal placement: There are a lot of techniques concerning portal placement, ranging from placing them manually to completely automated systems. Y automated systems are bad: I v seen quite a lot of techniques for that, ranging from virtual flooding to the use of BSP and which generates hell a lot of portals for no real benefit, then the segmentation technique which I gave the link above. Frankly the technique in that paper is rather good if well adapted, but given my experience in computational geometry, I would say you need to think 10 times before going into such adventure. The technique uses delaunay to compute Gabriel graph, debugging delaunay connection in 3d is not really a funny experience, not to say it’s not native at all. I would prefer that 20 portals are placed manually rather than spending whole summer debugging 3d delaunay and Gabriel graphs.

Finally I do think that this technique would be cool and usable for the next 5 years at least, till better hardware come into action or other techniques are used. For the moment I can say that it will render the scene management system very open so you can use many scene managers within the same one, objects can move between them if they allow removing and adding objects, after all BSP is there for that.

Cheers :)

Posted: Wed May 17, 2006 10:28 am
by tuan kuranes
I really need a clear Step-by-Step user process... so here's mine :

1) user makes low res mesh of its different SubScenes and place portal between any conjunction of them.
2) user load each SubScenes low res mesh into 3DS Max.
3) 3DS Max script will do a CSG between SubScenes low res mesh and portals (and will export what ?)
4) Preprocessor tool will generate a BSP tree for each low-res Mesh.
5) Preprocessor tool will loop trough the "level object" (which is the GlobalScene?) and determine for each lowres mesh Cells it belong to.

Run Time
6) at run time scene manger (SM) will render subscene which camera is in as "Master" SM and load/render "Slaves" SM of which portals connecting to becomes visible into a RenderTexture applied as material on the portal.
Once portal is been traversed by the camera, the Master/Slaves SM changes.

Is that OK ?
(take care of terms, or redefine them if necessary.)

And some New Questions:
- Can list differences with previous implementation you did in the the book code ?

- Having everything inside the pre-processor seems pretty essential in order to have a good basis of users here... can you estimates Time it would take to make all the process outside of a modeller ?

- By batching I was meaning to check when its even interesting enough to check visibility for a cell/subcell. But that would indeed be part of the "optimal portal placement" done by modelers. My guess is that you should add some deliverables in the list and planning : Manual, HowTo and Faq

Btw, here is some bugs in the book code :

1. You should not use "," as a separator, has localized operating system considers it as a float notation in certain country (France is one), so all the loading code fails in this case. (try to set your WinXP country notation to french.) That's the why of ";" in most CSV format. Here binary version was just segfaulting without exception before I made this change.

2. I had to add in glee.h just before _WIN32 "#include <GL/gl.h>"

Code: Select all

#define __glext_h_  //prevent glext.h from being included
#define __glxext_h_ //prevent glxext.h from being included

Posted: Thu May 18, 2006 1:48 am
by farakon
I m going to rewrite what you have said:

1) user makes an occluder mesh representing main closed occluders (rooms, skydoms, ...) and place portal. (same as in the book code)
modeller export the occluder mesh and the portal from the modeller (what I intend to do now)

2) In the book the modeller will do a CSG between occluder mesh and the portals, the result mesh is the rooms, but they are not marked or decomposed, so preprocessor tool will decompose the rooms mesh into rooms and generates a BSP tree for the rooms. (I want to make the CSG goes inside the preprocessor)
In the book we export original occluder mesh, portals and the rooms mesh

3) now we can determine in which room every object lies thx to the BSP

Run Time
4) The first step (actually previous frame will have to do that) the original occlusion mesh grouped with other occluders are sent to the GPU as one bach, later portals queries are issued (all that after frustum culling), the result is sent to determine which cells are visible.
The visible Master/Slaves SM changes or push the objects into a list and batch them if the SM decides to let a main batcher do the job for it (this is faster and more GPU friendly, less resoruces from GPU as well). The Master will ask the slaves for occluders and queries also if they have any (in the visibility check).

Q: Can list differences with previous implementation you did in the the book code ?
A: In the book i did the CSG in the modeler, i think it was ok to illustrate the concept and it would still be ok if not to some issues concerning proximity where the result mesh is a whole mess in some cases in 3dsmax. That's y I think it might be better to do the CSG in the preprocessor as well.
In the book I didn't make multiple scene manager, and here I intend to do since it's more general, and allows a better degree of freedom.

Q: Having everything inside the pre-processor seems pretty essential in order to have a good basis of users here... can you estimates Time it would take to make all the process outside of a modeller ?
A: In the list of deliverables, I estimate 3-4 weeks for the preprocessor which should be enough to move the CSG to the preprocessor.

Q: By batching I was meaning to check when its even interesting enough to check visibility for a cell/subcell. But that would indeed be part of the "optimal portal placement" done by modelers. My guess is that you should add some deliverables in the list and planning : Manual, HowTo and Faq
A: For the optimal portal placement we can rely on statistics, I mean how much a portal is seen from other surrunding portals, if it's seen all the time it's useless, and should be removed. For the Manual, HowTo and Faq, I need to know if possible what points do you need more info on?

For the bugs, I m very thankfull (credits ;)), I ll fix them soon and have the code reposted.

Posted: Fri May 19, 2006 11:17 am
by okki
just some more references to convex decomposition and interesting papers:

good overview of the different algos
another approach

something different using ellipsoides ... psoids.pdf

Posted: Tue Jun 13, 2006 2:18 pm
by farakon
So here is a screenshot of the progress done so far, the CSG is done in the code, and it seems to be working good. I won't be surprised if there remain few bugs here and there.


The next step which I hope to finish before the week-end would be the cell coloring and position query (the cell the camera is in). I need to clean the code and make a better OGRE sample.

For the level file format, I m going to take a look into .dotScene format, it should be sufficient for rendering information.

Currently we are investigating wether to create a kindof .dotProc ;) file format for processed and compiled levels

Posted: Tue Jun 13, 2006 3:27 pm
by Chris Jones
looks cool but can u explain (briefly) the 2 parts of the image, what are they showing exactly?

thanks, and keep up the good work :)

Posted: Tue Jun 13, 2006 3:38 pm
by tuan kuranes
left : CSG extracted from the mesh using the code
right : viewport of mesh in a modeler

Posted: Tue Jun 13, 2006 4:07 pm
by farakon
Thx tuan for commenting the shot :)

CSG stands for Constructive Solid Geometry: boolean operations on solid objects like union, intersection, subtraction

The right object is supposed to be a level occluder modelled as torus, the boxes are supposed to be portals (I exagerated their thickness, they should be thinner). Unlike other CSG programs that require u to use convex objects to model ur level like in Radiant, Quark, Unreal 2... u can use any suitable modeler to model ur level infrastructure (occluders and portals) as long as what u model has a correct topology (no shears nor self intersection), for example the occluder can intersect the portal, but it should not intersect itself.

If you are wondering why are we going into all this trouble! it's because portals and cells are one of the best ways to cull what is not visible from a scene (modern engines use them), so we don't have to draw it and loose speed in rendering (the fastest object to draw is the one you don't draw).

Posted: Tue Jun 13, 2006 5:11 pm
by Chris Jones
ah right, thanks, thats cool, hope you can complete it :)

good luck!

Posted: Tue Jun 13, 2006 5:20 pm
by jacmoe
This is looking and sounding good! Looks like you've got some great CSG code running there! :)
farakon wrote:Currently we are investigating wether to create a kindof .dotProc ;) file format for processed and compiled levels
No, please don't call it anything with dot or scene in it! :?
We have enough trouble explaining the difference between dotscene and dotsceneOctree..
No need to call it .dotProc, because the dot is there already: .proc (dotproc).

Posted: Tue Jun 13, 2006 8:51 pm
by sinbad
Looking very nice, keep it up :)

Posted: Wed Jun 14, 2006 5:01 pm
by farakon
Cell colouring is now complete and is holding well when the topology is right: after the CSG between occluder and portals is done we get groups of polygons. Each group of connected polygons represents a cell (connected polygons belong to the same cell), and each group is disconnected from other groups.


Left: the scene in a modeler program, Right: the scene after CSG and cell colouring.

Posted: Wed Jun 14, 2006 9:31 pm
by Kentamanos
I think you have Left and Right reversed:
farakon wrote:Right: the scene in a modeler program, Left: the scene after CSG and cell colouring.
Sweet looking project by the way. :)

Posted: Wed Jun 14, 2006 11:59 pm
by sinbad
Looking good. I'm curious though, you say 'connecting polygons' - what if inside one of those cells you have a floating region, touching none of the walls? Will the polys of that region be correctly picked up as a part of the cell? Or are you required to connect it to one of the walls?

Posted: Thu Jun 15, 2006 10:02 am
by farakon
@Kentamanos: u'r right, corrected it, thx :roll:

@sinbad: actually since the portal has a thickness, when you do the CSG, the intersection between a portal and the occluder is solid space while inside the cell is hollow. This means, that there are discontinuities between cells, which is used later to decompose the resulting CSG mesh into different cells. This solid space has the thickness of a portal, which is in this case 0.2 units. To overcome this discontinuity problem, we will look up the area of a sphere with radius 0.11 for example.

Posted: Thu Jun 15, 2006 8:08 pm
by Bloodypriest
Three small questions :

1. You said the side of the portal which the camera isn't in will be rendered as a render texture which looks ok to me because this is how I would do it too. But what if there is an object that doesn't lies completely within a cell but halfway between a cell and another, how do you handle that?

2. What happen when the camera is moved through the mesh representing the portal? Does the portal disappeared and are both cells rendered?

3. Same goes for portal thickness. If I have a big parent cell (like an outdoor scene) containing a smaller cell and a thick portal which is located halfway in the smaller cell and halfway in the bigger parent cell, how do you handle that?

I thought it was necessary to ask because question 1 & 2 are frequent use-cases and as bizarre a use-case as question 3 is, it could happen.