CHC octree scene manager Release & Hybrid spatial Tree i

[tuan kuranes]

It's Loose Coherent Hierarchical Culling Octree scene manager that was part of PLSM2, but enhanced. (near ready to implement CHC++ which is the fastest visibility mechanism possible.)

Added an abstract spatial tree implementation to a SM is a matter of hours now, as all SM queries uses the Tree Visitor, and don't need to be reimplemented.

So you implement the spatial subdivision you want just inheriting from Tree and/or Treenode, and that's it, no need to code queries, tree render or anything.

Developer talk:
-----------------

After some not selected gsoc submission reading, I tried to implement hybrid-tree in Ogre SM, and did succeed on prototyping, but did not ended it, just miss final hybridation sample implementation (making mchildnodes being looped generically and being of treenode class).

A good resulting example would be code that add "static geometry" spatial subdivison as kdtree child of a loose octree leaf.

If you read code you'll get the idea, It's what I proposed here, which is about generic spatial tree Visitor pattern that abstract any form of tree (even flat tree which is a list.).

So final idea would be to integrate that abstract Tree/list visitor pattern into Ogre, which would give
- A sample scene manager that give possibility to have quadtree, loose quadtree, octree, loose octree, flat list, aabtree, kdtree, etc.... inside the tree, upon user choice at startup.
- better static geometry spatial subdivision (kdtree, aabtree)
- An easier way to implement Scene Manager, or any tree parsing (CHC code is written once, but can work on any spatial subdivision, code also contains experimental frustum culling code)
- Perhaps a better way to handle mutliple scene manager (Zone ? )
- A way for user to implement spatial parsing code. (using the visitor pattern?)

(adding it or part of it to Ogre could be a gsoc subject)

-------------
Installation:
------------
Put the chc folder inside the folder containing OgreSDK.
Open .sln (vc8). Build.
run demo_chc.exe


----------
Readme:
----------

Hit corresponding Keys to parse tree to extract visibility.
----------------------------------------------------------------

Culling frustum modes:
1 : cullmode = "VIEW_FRUSTUM_DIRECT";
2 : cullmode = "VIEW_FRUSTUM";
3 : cullmode = "VIEW_FRUSTUM__MASK";
4 : cullmode = "VIEW_FRUSTUM_MASK_TEMPORAL";

Using Hardware occlusion queries:
5 : cullmode = "CHC";
6 : cullmode = "CHC_CONSERVATIVE";

Debug Visualisation
---------------------
8 : show bbox
9 : show octree
C : change camera
- : remove some entities
+ : add some entities
K : switch to complex shaders (increase per entity visibility impact on FPS)
I : test intersection query
O : test ray query.


Download Source

Further reading :
Near Optimal Hierarchical Culling: Performance Driven Use of CHC
[edit]link fixed, thanks beaugard ![/edit]

[beaugard]

Very good news, I'll try it immediately.

The link returns a 404 for me, is it misspelled?

EDIT: http://tuan.kuranes.free.fr/chc works, it was just the extension.

[steven]

Sounds very good

I was just wondering if this would not overlap with the SceneManager redesign planned by Sinbad... or if both could be merged.
http://www.ogre3d.org/wiki/index.php/TindalosNotes

bye

[jingjie]

Using culling mode "CHC" or "CHC_CONSERVATIVE" , the rendering of entity will be flickered and culling incorrectly? (Ogre version 1.4.4)

[beaugard]

No. Probably you don't have the material location in your resources.cfg file. The material for the bounding boxes is defined there, with colour_write off and depth_write off. With the default material all bounding box queries will be drawn as solid boxes.

[jingjie]

No. Probably you don't have the material location in your resources.cfg file. The material for the bounding boxes is defined there, with colour_write off and depth_write off. With the default material all bounding box queries will be drawn as solid boxes.

I look for the source code of CHC Scene Manager.
I am sure that the default material "CHCSolidOcclusion " all bounding box queries is defined in OctreeCHCSceneManagerFactory::createInstance(const Ogre::String& instanceName)?

[beaugard]

In that case maybe something is not working with programmatically setting this material. It is also defined in the colors.material file and in my OctreCHCSceneManager.cpp it is commented out - maybe I commented it, can't remember.

The problem you are describing fits exactly the problems I had that were caused by wrong material.

[PolyVox]

This looks very interesting - would it be hard to adapt the code to get CHC working with the default (bounding volume hierarchy) scene manager? Maybe it even belongs in the base SceneManager? With an option to switch it off, of course, as I realise it's not appropriatre for every scenario.

[tuan kuranes]

@jingjie: Are you sure your hardware support HOQ ? What GPU do you have? check Ogre.log for any problem.

@PolyVox : No, That's idea of of the abstract Tree/list and Visitor/traversal Code.

Once you write a traversal, it's done for any Spatial Subdivision. So DebugVizualizer, Queries, CHC, Frustum, are supposed to work out of the box.

You should only have to code the BVH. (or patch Ogre to support it natively as stated above.)

I uploaded a new version that allows switching real time between culling algo and have better debug Visualizer.

[jingjie]

@jingjie: Are you sure your hardware support HOQ ? What GPU do you have? check Ogre.log for any problem.

Yes, my video card is nvidia 6600GT.
Do I have lose some configures to cause it rendering flickered and culling incorrectly?

[Lord LoriK]

I'm having the same problem with the flickering. Even worse: the demo crashes when I set up CHC_CONSERVATIVE mode. I'm using Ogre 1.4.6 with Real defined as double (not float), but appart from that, nothing weird.

Before I could run the demo, I had a strange problem with the CHCSolidOcclusion material being defined twice (once in a script and once programatically). I tried removing the code fragment where the material is created, but for some strange reason the material file does not work and the demo crashes with a "material not defined" exception. If I rename the material file, it starts and looks good for frustum-culled modes, but looks ugly and slow with CHC. As I already said, some assertion crashes the demo on debug (never tested in release because the results where not what I expected).

My box is running WinXP SP2 and my graphics card is nVidia 8400GS (not so good, but does support HOQ). I hope you can tell me what could be wrong because I really need OC in my project to have a decent frame rate.

[tuan kuranes]

I do not succeed in reproducing any flickering, crash, etc...

But I'm not using double here, as I use OgreSDK, latest nvidia drivers.

Where does it crash ?

If you Hit '0' (zero) key you do get good debug view in all workings modes ?
I guess you'll have to try with single float and report after.

I have not much time fo that scene manager, so if you really need it, I guess you'll have anyway to learn how it work and try debugging it...

[beaugard]

I have it working, but as I said earlier I also had some initial problems exactly like you describe... I also had to make some changes, I think, but don't remember what exactly. I commented out the programmatically set material anyway - maybe something else but it wasn't much...

If you want to I can just zip and upload my version somewhere and you can test if it works better.

[Lord LoriK]

I have it working, but as I said earlier I also had some initial problems exactly like you describe... I also had to make some changes, I think, but don't remember what exactly. I commented out the programmatically set material anyway - maybe something else but it wasn't much...

If you want to I can just zip and upload my version somewhere and you can test if it works better.

I'd be really grateful if you did. I could try to debug it myself, but I have a thight schedule with my prototype and I'm already running out of time, so any help is very welcome.

[beaugard]

Ok here it is: http://martin.enge.googlepages.com/CHC.zip

Some notes:
This is the earliest version Tuan Kuranes released, so it has some additional bugs (notably you can't change culling mode in the demo).

I am using OctreeCHCSceneManager_vc8_CVS.sln, I changed the settings so you should unzip the CHC folder alongside the ogrenew folder.

Also, testing it right now I noticed some artifacts in debug mode using CHC_CONSERVATIVE (no flickering but occationally something is invisible at a certain angle). I couldn't see this in release.

...still maybe it's worth a try.

[beaugard]

btw, I think I found a bug (maybe not a bug, but a design problem)

The culling bouning boxes each have their own vertex/index data, which takes up a lot of graphics memory. They really only need their own transform.

[tuan kuranes]

@beaugard: Indeed. Forgot that one.
Was more for debugging purpose rather than speed.
That really should be some cube just transformed each time on the fly. (the same goes for debugging overlay view that should aslo)

[beaugard]

Come to think of it, changing this might really boost performance because of caching and because it removes the costly buffer locks (only first time, but it's a lot of cubes).

[Lord LoriK]

Thanks, beaugard. Just downloaded your code, but I don't have Ogre here (nor the time to set it up). I'll test it at home.

[jingjie]

The culling bouning boxes each have their own vertex/index data, which takes up a lot of graphics memory. They really only need their own transform.

Was more for debugging purpose rather than speed.
That really should be some cube just transformed each time on the fly. (the same goes for debugging overlay view that should aslo)

To tuan kuranes :
When did you plan to release stable and optimised version ?
About some Optimised sugguestions:
1. Needs more robust method to reduce hardware occlusion queries.
2. Needs more effiecient vertex and index buffer using.
3. Needs various implementation of static geometry spatial subdivision like kdtree, aabtree.
4. Needs none-static geometry spatial subdivision strategy?

[tuan kuranes]

When did you plan to release stable and optimised version ?

Not even planned.

1. Needs more robust method to reduce hardware occlusion queries.

Any idea ?

2. Needs more effiecient vertex and index buffer using.

3. Needs various implementation of static geometry spatial subdivision like kdtree, aabtree.
4. Needs none-static geometry spatial subdivision strategy?

Hybrid Tree must be finished first.

Now it's opensource, perhaps someone that needs it may find it end enhance it. I'll be happy to help anyone.

[beaugard]

Now it's opensource, perhaps someone that needs it may find it end enhance it. I'll be happy to help anyone.

It seems so many people want/need this... I will eventually attempt it (maybe when my son starts school - in five years ). Anyway, it should be a fun project that will give whoever finishes it a lot of credit from the community.

1. Needs more robust method to reduce hardware occlusion queries.

Any idea ?

The solution should be something like in the "near-optimal chc" paper - only issue queries when the geometry that would be potentially culled is complex enough. I'm not sure how this works with the visitor idea, though. Also, one should use the "conservative" method, not issuing queries for previously visible geometry at once.

The way I am thinking about implementing this is for a portal system (or cell-system, maybe more accurately), where I can do a search down the portals, aggregating geometry until I have enough to make it worth doing a query. But this is all very sketchy still, and would probably not work in the generic setting.

[tuan kuranes]

The solution should be something like in the "near-optimal chc" paper - only issue queries when the geometry that would be potentially culled is complex enough.

You can already tag certain geometry as:
- occluder
- occludable (therefore non-occludable doesn't issue geometry)

Cannot remember if you could combine this (non-occludable occluder), but it does give flexibility you need upon needs.

The way I am thinking about implementing this is for a portal system (or cell-system, maybe more accurately), where I can do a search down the portals, aggregating geometry until I have enough to make it worth doing a query. But this is all very sketchy still, and would probably not work in the generic setting.

Some inspiration perhaps in 2006 portal gsoc from farakon which used hoq.

[beaugard]

Yes, carefully selecting what to make occluder/occludee should make a big difference - in a "real" scenario it should perform much better than in the demo.

Some inspiration perhaps in 2006 portal gsoc from farakon which used hoq.

I didn't realize he reached the point where he started using hoq.

How do I get the project? Do I have to download ogre branch "soc06-scenemanagement", or is it a self-contained project?

[jingjie]

I didn't realize he reached the point where he started using hoq.

How do I get the project? Do I have to download ogre branch "soc06-scenemanagement", or is it a self-contained project?

I think you are a reference of well implementation of portal system that currently is "The Portal Connected Zone Scene Manager".
You maybe modify into CHC octree Zone to use traversal through portals to have enough to make it worth doing a query.