   Occlusion Culling
  This topic just cropped up in the Yann worship thread but I thought I''d start a new thread to discuss it.Yann mentions that with Occlusion Culling he is able to get a general and reliable algorithm that applies for both indoor and outdoor culling. What I''m interested in is what techniques he, and others here are using. Also how do most people merge this technique with an Octree or other spatial data structures (unlike Hierarchical Z-Buffering which relies on it).In other words point or cell based? Image, object or Ray Space? Hardware or Software based? Occlusion Horizens, or Shaft Occlusion Culling? Hierarchical Z-Buffering or HOM? etc... What have you guys found easiest to implement and practical, yet effective?Also, you''d have to sort front-to-back to have your occluders work at all, how do you deal with semi-transparent objects then? What other issues might come up because of this?    "Love all, trust a few. Do wrong to none." - Shakespearewww.CodeFortress.com
  Yann uses a modified HOM algorithm for his Culling system. That along with his ABT yields a pretty nice system.The main prospect to get OC working with your spacial subdivision algorithm, is that each of your nodes contain a chunk of geometry unique to that node. Therefore, any nodes visible in your frustum can easily be depth sorted as an entire node, and sub sorted if you desire. From there, walking node by node, rendering Cullers etc becomes quite easy.I actually use a modified version of the cPLP algorithm (Check out Game Programming Gems 2/3) Additionally, for models that aren''t 100% culled or unculled, models are broken down into sub models via an additional ABT. Which creates a tightly bounded box around given chunks of the model. This allows me to do sub chunk testing, so i only have to render what''s REALLY visible.~Main    ==Colt "MainRoach" McAnlisProgrammerwww.badheat.com/sinewave  ;  Anyone else?  ;  software depth map here    ;  I can't speak for others, but I have made highly satisfying experiences with an essentially very simple approach. Perhaps I should quickly outline how I ended up with that method, and why I think it is the best choice on current hardware.I started, as surely many other people, with a portal system. Unfortunately, the inherent complexity of our levels made the portal approach very difficult. Automatic portalization was no option, so the artists needed to place the portals manually. The portals could have any coplanar shape. We used a portal/anti-portal approach, connecting sectors in both directions. A special sector, the NPS (non-portalized space), grouped all the geometry that did not fit into a specific sector. At runtime, the system would recursively go through the list of visible portals, and clip them to yield depth dependent visibility masks for each sector. So far, so good. Performance was OK, culling was good too.But our artists were everything else than happy. First, placing all the portals manually is a pain in the ass. And second, being the most important point, it limited them tremendeously in their creativity: everything they modelled, had to fit into this rigid portal/sector concept. Everything that didn't was thrown into the NPS. Now, on our first scene, we (the programmers) had quite a shock, when we compiled the level: the artists had put around 90% of the level geometry into the NPS ! It was just not portalizeable. If you have a large forest, how do you portalize it ? Or a village, seen from the outside, where do you put the portals ? We needed an alternative. We first tried a kind of full 3D version of a PVS: precomputed volumetric visibility lists, using fuzzy projections. That works very well, but takes an insane amount of memory for large scenes. It also takes too much preprocessing time.So I tried shaft culling. Basically, very easy, and fully object space. But the time used to cull objects against thousands of shafts was far too much. Furthermore, since occluder fusion is very hard to achieve with this technique, culling results were far below our expectations. And not to forget: being a geometrical algorithm, it is prone to mathematical instabilities due to floating point accuracy problems. Not good. And the idea to merge the shafts into a fusioned occlusion volume in realtime, resulted in a total nightmare.And so I ended up using HOMs: image space method, easy to generate, totally stable under all circumstances, and implicit occluder fusion. The first tests delivered excellent results, both in terms of occlusion map generation, as well as culling efficiency. I modified the well known Zhang-algorithm a little, exclusively using a high accuracy 32bit depthmap (ignoring the coverage map). The approach fitted perfectly in our spatial ABT structure: since the ABT offers tightly bound  objects in AABB's, and feature local vertex/index pools, they can directly be culled against the HOM, by a simple 4x4 transform/project. The culled nodes are simply not send to the render scheduler. Extremely efficient.Now, a few months ago, I decided to reimplement the occlusion system on the GPU, using this HP/NV occlusion query stuff. Well, to make it short, I trashed the code pretty fast. Due to the bubbles introduced into the command stream (even by using multiple deferred queries with the NV extension in OGL), it was slower than the software approach. Esp, if the later uses CPU/GPU concurrency.So our current system renders the next frame's occlusion map on the CPU, in parallel to the GPU rendering the currently scheduled frame. Basically, I get the occlusion map for free. Rendering is done by using a very fast software rasterizer, written in hand optimized ASM. Same for the query system (comparing a projected AABB against the HOM). I'm very happy with that configuration: activating both rendering and querying will generally drop the framerate by about 10%, but considering the fact that the visible geometry is often reduced by amount as high as 95%, it's more than worth it.[edited by - Yann L on April 30, 2003 11:41:37 AM];  Yann:Are you saying you don''t use the method of opacity/transparency threshold based testing against HOMs that Zhang generates, and only use a higher resolution depth estimation buffer, or something else?;quote:Original post by Yann L   And how the HOMs are being generated? Having one (ABT) node, we know its BV, i.e. test model. But what is its write model (occlusion model)?It isn''t the original geometry resterized by CPU, I am pretty sure... ;  I think he uses virtual occluders. Simplified geometry that works well as an occluder.  ;quote:Are you saying you don''t use the method of opacity/transparency threshold based testing against HOMs that Zhang generates, and only use a higher resolution depth estimation buffer, or something else?  That''s right, I only use a zbuffer for the test. Since I''m rendering the occ-map in software, rasterizing only a single 32bit channel is almost twice as fast as when rendering the additional opacity channel. I can still take advantage of non-conservative culling, by using the ratio of failed to succeeded depth tests when comparing the projected AABB against the HOM.quote:And how the HOMs are being generated? Having one (ABT) node, we know its BV, i.e. test model. But what is its write model (occlusion model)?It isn''t the original geometry resterized by CPU, I am pretty sure...   Depends. As blue_knight mentioned, I use virtual occluders (in object space) for the general occlusion (for static geometry, as well as for dynamic). You can see it as a kind of occlusion skin. For problematic things like trees, vegetation, and all complex ''fuzzy'' objects that do not have a large occlusion footprint by themselves (but generate a considerable fusioned occlusion, think of a forest, for example), I use a low-poly LOD version of the object (with conservative volume). For a tree, that would be a set of alpha patches. Now, this can sometimes lead to false positives (eg. a tree can sometimes dissappear, if lots of small foliage from another tree is infront of it), but in practice you don''t really notice that (it''s only a few pixels). And it only happens with complex organic objects, that do not have an adequate virtual occluder.;  Do the artists create the occlusion geometry by hand, or is it created automatically? I''ve been thinking of writing a similar system for years (ever since i read about dPVS/Umbra), but never get the time for it.Do you use geometric tests to supplement the HOM, as in dPVS? I vaguely remember them using ray-casts to track visible points on an object (corners of the bounding box), as a positive early out for the visibility test.  