   My occlusion culling algorithm
  It''s an idea I had some time ago for occlusion culling. I don''t know how well it''ll work and I doubt I ever get the time to actually implement it so I''d figure I''d share it and see what other thought about it..maybe it can spark someone else with some good idea I come up with the idea while reading obout hierarchial (however that''s spelled) z-buffers. But as far as I know, there''s no way of implementing them in a real-time games because of the bottleneck of reading back the z-buffer to system memory. But I figured (I haven''t tested this), reading back a few bytes won''t cause a very big performance hit, so why not just shrink the viewport to a smaller size and read back much less data?The whole algorithm looks something like this:For each frame:1. Turn off all textures, effects and just draw into the alpha channel. Polygon anti-aliasing has to be turned _on_2. Set the viewport to something like 16*9 pixels. (or relatively small enough to be read back without a speed hit)3. Draw the scene (within the view frustrum of course) in front-to-back order to a certain depth. Mark therse nodes as rendered. (I designed this with an back-to-front sorted octree in mind)4. Read back viewport.5. Since polygon antialiasing is turned on. Those pixels of the read back viewport that''s not completely covered would be some state of grey (or black), while those fully covered would be completely white.6. Continue drawing the scene from where it was last left off, only drawing those nodes which will fall in an area that was not completely covered when read back. Mark rendered nodes.*. Repeat step 5&6 until all areas of the read back image is completely covered, or the far clipping plane is reached.7. Switch back to normal drawing, render the whole scene with only the nodes that is marked.The thing, I''m a little doubtfull of is wheter all cards support the polygon antialiasing the same way (Not drawing the pixels which is not covered completely at full intensity)IF, the algorithm works, some optimization like drawing less nodes the next pass in the areas of the screen where it''s almost completely white and drawing more nodes where it''s almost empty could be done..Ok, that''s it. I don''t claim to be some graphics guru, but if it''s any good and you''d like to give me a pat in the back, or if you can modify it to usefullness, please feel free to comment.   -LuctusStatisticly seen, most things happens to other people.[Mail]
  1. Turn off all textures, effects and just draw into the alpha channel. Polygon anti-aliasing has to be turned _on_2. Set the viewport to something like 16*9 pixels. (or relatively small enough to be read back without a speed hit)3. Draw the scene (within the view frustrum of course) in front-to-back order to a certain depth. Mark therse nodes as rendered. (I designed this with an back-to-front sorted octree in mind)--Hmm... Sorting all of the nodes front to back is not good.4. Read back viewport.--Part of the time taken up is waiting for the rendering to be completed before anything can start to be read back.  That''s as much of a problem as the amount of data to be transfered.5. Since polygon antialiasing is turned on. Those pixels of the read back viewport that''s not completely covered would be some state of grey (or black), while those fully covered would be completely white.6. Continue drawing the scene from where it was last left off, only drawing those nodes which will fall in an area that was not completely covered when read back. Mark rendered nodes.--Gives good screen space coverage and implicit depth info, but the multiple readbacks from repeating 5 and 6 would more than likely cause worse performance than reading both screen projection and depth only once.You seem to grasp some of the concepts that could be useful in the future if a readback of the screen buffer could be eliminated(conditional instructions/rendering on the graphics card would be great), but with today''s hardware, and software drivers, the best tradeoff seems to be a fast software renderer for very simple virtual occluders and a fast occluder selector for one depth/screen space rendering(occlusion map).  Then quick screen space bounding box tests against this occlusion map.This isn''t to say that other methods aren''t valid or "bad", just that current equipment doesn''t support it as well.karg ;quote:Original post by Luctus  I come up with the idea while reading obout hierarchial (however that''s spelled) z-buffers. But as far as I know, there''s no way of implementing them in a real-time games because of the bottleneck of reading back the z-buffer to system memory. It''s usually done either by software rendering, or by using hardware occlusion queries.quote:But I figured (I haven''t tested this), reading back a few bytes won''t cause a very big performance hit, Incorrect assumption. The problem is not so much the readback itself, although reading back through AGP is in fact slow, a few bytes won''t really matter. BUT, you will create a command FIFO bubble. And that''s the real problem. It doesn''t matter if you read back the whole screen, or only a single byte: you will always create the bubble, and the (huge) performance hit due to the bubble is independent of the number of pixels read. The simple process of issuing a read command will trigger it.;quote:But as far as I know, there''s no way of implementing them in a real-time games because of the bottleneck of reading back the z-buffer to system memory Link 1 Link 2 Link 3 Link 4 Link 5Research is fun. ~Main   ==Colt "MainRoach" McAnlisProgrammerwww.badheat.com/sinewave ;quote:Original post by Karg  --Hmm... Sorting all of the nodes front to back is not good.It just comes down to traversing the octree nodes in the right order, just like a BSP is(/can be) used for back-to-front rendering.quote:But as far as I know, there''s no way of implementing them in a real-time games because of the bottleneck of reading back the z-buffer to system memory.quote:It''s usually done either by software rendering, or by using hardware occlusion queries.I kindof meant doing it without using software rendering.quote:Incorrect assumption. The problem is not so much the readback itself, although reading back through AGP is in fact slow, a few bytes won''t really matter. BUT, you will create a command FIFO bubble. And that''s the real problem. It doesn''t matter if you read back the whole screen, or only a single byte: you will always create the bubble, and the (huge) performance hit due to the bubble is independent of the number of pixels read. The simple process of issuing a read command will trigger it.According to this thread regarding CPU/GPU concurrency. The FIFO bubble is caused because any read() operation causes the card to wait for all the triangles to be rendered. But nothing stops us from doing other things in the meantime, or? Something like:while (!done){  RenderNodes( somedepth );  DoSomeGameLogicProcessing( deltaTime ); //Doing game logic while the GPU is working  ReadBackBuffer();  if ( FullyCovered() )    done = true;}DrawAllVisibleNodes();DoSomeGameLogicProcessing( deltaTime );SwapBuffers();  But I guess it maybe still might be rather impractical? -LuctusStatisticly seen, most things happens to other people.[Mail];  Actually, (either using standard read, or hardware occlusion quearies )it would be more along the lines of:RenderOccluders(g_Objects);RenderOccludeeTests(g_Objects);CalculateMathPhysicsSound();ReadHWOccludeeTest(&g_Objects);Not really impractical, just  different . Most people don''t design an engine this way. I''ve seen some tests using this method however, that have resulted in very, very nice results using hardware quearies. Again however, problem arises when you consider that this doesn''t fit into a normal pipeline very well. Usually, you''d design your pipeline so that all your visibility determination could be caclulated within one swoop (to eliminate redudant passes). Breaking it up like this sometimes causes an error.quote:I kindof meant doing it without using software rendering.Why? Software rasterizer is very quick, and very efficient. Took me about a weekend to write mine up, and even with the un-optomized algorithm, was still an instant improvement to my frame rate and overhead. Even if you just don''t like to do a software rasterizer, the hardware queries (if implimented correctly) can eliminate the bottleneck ''bubbles'' caused from the readback. Hell, if you''re really looking for a speed increase, you can do the visibility determination in a per-pixel shader, and pass the results to the screen image. Then you only have to do single image read. quote:4. Read back viewport.You still read back the visibility information from the hardware, which is no different than any other algorithm out (unless you use software rasterization). If you do an image read, you have a problem with ''bubbles'' and would have to impliment the above algorithm. But that''s nothing special.quote: 5. Since polygon antialiasing is turned on. Those pixels of the read back viewport that''s not completely covered would be some state of grey (or black), while those fully covered would be completely white.Step 5 is an assumption that the multisampling that will take place, won''t impact performance, which isn''t always true. My applications show a dramatic hit in performance when using higher passes of anti-aliasing. Doing this render multiple times could be a pain.quote:6. Continue drawing the scene from where it was last left off, only drawing those nodes which will fall in an area that was not completely covered when read back. Mark rendered nodes.How exactially do you plan to determine what areas of your Occlusion map haven''t been drawn to? Regardless of implimentation, you still have to do a pixel check on the CPU once the data is read back from the GPU.So basicly, you''re doing a hardware read, and a looping pixel check on the CPU. Not really any different than the normal approach. Honestly though, The software rasterizer eliminates the hardware read, which can get rid of the bottleneck. (but causes CPU overhead, which is extreamly minimal in my research)Your hardware tests eliminate the CPU per-pixel loop, but require a hardware read back, which could cause bubbles. These two solutions are extreams for an answer, but anything in the middle ground is going to be hindered by both problems.~Main   ==Colt "MainRoach" McAnlisProgrammerwww.badheat.com/sinewave ;  If I''m not mistaken there are alternatives to using a hardware occlusion queries and writing a software renderer. You can use different geometric methods.  One possibility is to do object space occlusion culling like in this Gamasutra article.  Basically you do something like stencil shadow volume extrusion and test objects against that shadow volume. Another possibility is to use the image space projected 2D edges of the occluder instead of rasterizing it.  The test can be done with a 2D BSP and should be pretty fast.  I''m not sure if this method will be any faster than a software renderer. If you use HOM, the tests against the occluder should be pretty fast. Creating a 2D BSP for a complex object may be slower than rasterizing it, although if your occluders are large and low poly (fill limited) the edge based method should be a lot faster. There could be other ways to do the check besides using a BSP (2D triangle intersection?)  I''m not so sure about using screen space edges. I''ve heard it mentioned a couple of times and have played with it a little myself but I haven''t read any papers or articles on how to do it or how practical it is.While using a software renderer is popular on Gamedev.net (largely do to Yann L''s influence I''m thinking) it seems like a lot of people in the industry favor geometric approaches over rasterization.  The software renderer is probably more robust than geometric methods, but the geometry based approaches may be faster.  Yann L said he ran into precision problems when trying a geometric approach, does anyone else have experience with something other than a software renderer?  ;  Occlusion Culling can be broken into the following catagories:Image Space Vs. Object Spacesubsets: From-Point Vs. From-Areasubsets: Online Vs. Offlineneedless to say, there are plenty of alternitives to the image space algorithms.I implimented an object space method, namely the PLP and cPLP algorithms, and had to agree with Yann, that there was precision problems. Namely due to the gross overestimation of Occluders. I also tried a hybrid approach of shadow volumes for culling. It basicly amounted to an edge detection algorithm, then attempting to create a crude frustum from the process. The visibility check then just became a standard frustum check. This however ran into problems of redundancy (N! to be exact).The edge algorithm that impossible talked about is an interesting one, essencailly you''re just testing for 2d intersection of lines. Or testnig lines against the Occlusion Map. If you''re just doing a 2d line intersection, you run into problems of depth and fill, as the edges of an object can not touch an occluder, but still be blocked by it. The solution of just tracing the lines agains the Occlusion map is a valid one. As you reduce the number of pixels checked, and still get pretty decient results. Bad thing is though, that you need to calculate the lines against the Occlusion Map, which results in more floating point math.I''ve stuck with an image space test, using a software rasterizer. I overcame the occludee vis test by using SIMD/SSE2 MAX/MIN functions. I reduced the amount of checking by 60%, which means the only slowdown on my occlusion process is the creation of my occlusion map, which for a 256x256 map, is quite minimal.As for more methods, here''s an interesting list:Image Space (all run time): HOM, HZB, Depth Peeling, Software RasterizerGeo Space: PLP, cPLP, Shadow Volumes, PVS(offline), portals(Offline)needless to say, the final deicision of occlusion culling algorithm depends on the software. There''s plenty of options to choose from.~Main   ==Colt "MainRoach" McAnlisProgrammerwww.badheat.com/sinewave 