[submitted] Scene manager
Posted: Tue May 16, 2006 12:03 am
Introduction
============
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: http://glbook.gamedev.net/moglgp/
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.
Pre-process:
------------
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: http://www.inf.ethz.ch/personal/giesen/pub/wads03.pdf, 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
============
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: http://glbook.gamedev.net/moglgp/
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.
Pre-process:
------------
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: http://www.inf.ethz.ch/personal/giesen/pub/wads03.pdf, 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