Saturday, March 12, 2011

Software occlusion culling pt.2: Implementation

In the previous post i’ve described occlusion culling technique that tries to take tad different steps on resolving visibility information. In this one i’m gonna share basic implementation that performs pretty well. Following steps are performed:

  • Transform objects (occluder / test geometry) bounding boxes to viewport space. Determine whether we should clip its triangles or not and tile bounds that object is in. Invisible objects are skipped. Also calculate view space Z bounds that later will used as sort key.
  • Transform vertices ( for objects intersecting frustum planes do transformation and clipping ) to viewport space.
  • Allocate output triangles and in each tile that triangle intersects store allocated triangle indices. We choose to store triangles in groups of four in SoA style. Also the backface mask is calculated during this step so backfacing triangles could be skipped in rasterizer
    Now as we have triangle lists for each tile we sort them using previously stored Z value.
  • Sorted lists are drawn, where occluder triangle scanlines are merely ORed with corresponding scanline of occlusion buffer of tile and test triangles are checked whether any pixels of scanline are visible.

Performance of the rasterizer is greatly affected by the resolution. In the demo i use 720p which can be easily reduced. Triangle list sorting can be expensive if all triangles are in same tiles. Also it could be beneficial to split tiles vertically and have masks for each tile so we can quickly check if tile is already full. I’m currently working on MT implementation and performance is scaled linearly with number of working threads just as expected. Though it seems making fast and reliable job manager on Windows is not that easy but that’s completely different topic.

Demo with source code

Monday, February 28, 2011

Software occlusion culling

Occlusion culling seems to be the obvious feature every mature engine should have these days. Some use HW occlusion queries but they introduce another sync point with GPU, others prefer using software occlusion. That is one can rasterise depth of nearby occluders ( special geomery or maybe even the one been rendered ) and check bound boxes of objects to be drawn againt this depth buffer. Its not necessary to use full resolution buffer. Memory/performance could be saved by using smaller one. There’s basically two approaches to rasterise triangles - scanlines and halfspaces. In scanline approach we draw horizontal lines between pair of triangles edges. When using halfspaces we build bound box of projected triangle and iterate its pixels checking if current one is inside triangle or not. But since all we care about is determining whether given triangle is visible or not some tricks can be used.

On a local forum (yes, its time to learn russian), infamous comrade IronPeter suggested a smart approach to do the occlusion culling. The idea is very simple - we have a queue of triangles. Triangles can be of two types - occluder-triangles which write occlusion info and occludee-triangles which only test it. Occlusion info is written in tiled bit-buffer. This allows us to write 128 pixels at a time at most using some SIMD extension like SSE. Rasterisation procedure works like in convinient scanline rasterisers except for we only need to know start and end coordinate of each scanline clipped by current tile bounds. With this assumptions in mind all is left is to sort triangle queues front-to-back using minimum z value for occludee triangles and maximum one for occluder triangles and then rasterise those triangles in order.

  1. Transform triangles to viewport space
  2. Determine tile bounds
  3. Push triangles into tile triangle queues
  4. Sort front-to-back each triangle queue of each tile ( using zmin for test triangles and zmax for occluders )
  5. Draw sorted triangle queues ( for test triangles check if any pixel of scanline is visible for occluders just OR scanline bits with tile buffer )

The algorithm is pretty simple and straightforward to implement and besides it can be easily threaded. My initial implementation can draw a scene with actual render geometry with more than 300k triangles in 20msec ( 12msec transform + 8msec rasterisation) in 720p. Lower resolution can be used to futher speedup processing. There’s a number improvements to be made. In my expectations SPU and VMX versions should be faster. After porting to other platforms and adding multithreading support i’m planning to do some reseach on automatic occluder and test geometry generation which seems to be pretty interesting topic as well. And i’m gonna share source code when there’ll be enough functionality to be usable in other engines.

P.S. Many thanks to IronPeter for neat idea and some insights on implementation.




Wednesday, September 30, 2009

bugs life

This is a story from my previous life about one funny bug i fixed. We had a base scene object class SceneObject_c which contained number of flags ( like visible, active, occluded, killed ). And in dtor there's a check, something like Assert( IsKilled() );. For a number of reasons, we've been rewriting stuff to work in two threads: main( update) thread and render thread. Each frame those threads run in parallel and the fastest one waits till slowest completes. Update thread sets some flags ( killed is set only there), render thread sets other flags. Same flags are never accessed from different threads during frame processing. But after some time the above assert was triggered. I've spent like whole day debugging it. Checked that everything was accessed from correct threads, and a number of other necessary conditions - all of them were just fine. And the next day when i was complaining to a friend about this issue i suddenly realized that flags were stored in single bitfield which apparently was written/read as word. That was... confusing, especially cause i wasnt able to identify the bug from the very beggining. But still i think it was pretty fun and not that obvious as it seems now.

Friday, September 25, 2009

breakquest on psp

it took me 3 weeks to do initial port from bcb + sw renderer to vc++ + ogl, wrap all allocations to own memory manager and fix bugs i made when migrating to hw render) another 1.5 month were spent doing actual psp port, writing small tools to convert assets, optimizing performance, making it trc ready and fixing more bugs) not bad for first psp project, more to come i hope!

Tuesday, December 19, 2006

first entry

so here we go. i'm starting this blog to post some technical stuff which i generally never posted in my ordinary blog. hope it'll stimulate me to write more code at home