It depends on the occlusion buffer dimensions.

On a 2GHz Core i7, I take less than 1 millisecond to rasterize 2000 triangles of terrain geometry into a 256 pixel wide occlusion buffer. Increasing the resolution to 1024 pixels also increases the time taken to 2.5 ms. My routine is depth only rasterization, and is not optimized to the max, C++ code only and no SIMD instructions.

I've found it hard to thread the occlusion rendering though, as the way I use it is a sequential operation: find out visible occluders, rasterize them, then use the result to check object AABB's for visibility.

In the occlusion rasterizer that I'm using, my frame-buffer is only 1 bit per pixel (drawn to yet, or not drawn to). I render all the triangles for occluders and occludees from front-to-back, with occluders filling pixels, and occludees testing if all their pixels are filled or not (if any of their pixels aren't filled, the occludee is visible).

Using SSE, you can fill 128 pixels at a time with this algorithm, so the actual rasterization is not at all a bottleneck. I can run at pretty much any resolution without much difference in speed. The real bottleneck for me is actually transforming all of the vertices from model space into screen space (i.e. the 'vertex shader').

I break the frame-buffer into 'tiles', each of them 128 pixels wide and <height> pixels tall. Each of these tiles can then be independently rasterized by a different thread.

How you are sorting triangles? How about intersections? Or do sort by using max z and raster whole triangle with that? Sound great technique but I want to hear more details.

Yeah you use a single z value for each triangle, which means that large triangles on glancing angles don't act as effective occluders.
To ensure conservative results (no false occlusion), you use the maximum z value for occluder triangles and the minimum z value for occludee triangles, which allows intersecting triangles to work without errors.
First you project all the triangles into screen space, determine their z values as above, bucket them into the "tiles", then sort the triangle lists in each tile according to their z value. And then rasterize the tiles
When rasterizing a triangle, you iterate through the scanlines generating a bitmask of the pixels covered by the triangle on that line. Occluders then simply OR this mask with the framebuffer. Occludees AND this mask with "NOT framebuffer" and if the result is true, they write a non-zero value into some address indicating this object is visible (when submitting a group of occludee triangles, you also pass an int*, etc, where this value will be written to if the object is visible. The int at this address is initialized to zero beforehand).

P.S. I didn't come up with this, I've shamelessly taken the idea from Vadim Shcherbakov, who got it from another guy, IronPeter. There's a full explanation and a demo with source code on his blog. His code uses SSE intrinsics so it's a bit unreadable in places, and it contains a few bugs, but it's very fast Eventually, I'd like to release my own open source version of this algorithm, but I've got other things to be working on at the moment.

[edit]
P.P.S. I contacted Vadim about the copyright on his demo, because there is no explicit licensed contained in the ZIP, and got this response:

On 05/10/13 8:11 AM, Vadim Shcherbakov wrote:
--------------------
Hey, you can use the code as you like, there is no license or any limitations.
Regards, Vadim

I am gonna try to implement this myself since Vadim S. demo is crashing for me at certain camera position/angles, also his code is hard to follow and unreadable so i cannot fix it

I think the problem is in the clipping algorithm, sometimes, when triangles intersect the near plane (an assert in there is the cause of the crash)... but yeah, his code is very hard to follow.

i could test just 4 pixels/corners of occludees axis aligned 2D rectangle?

I'm not sure that would work -- e.g if the occludee is just beyond a window, but is larger than the window. It's four corners will be occluded by the wall, but it's centre will be visible through the window.

If you're rasterizing a traditional depth buffer instead of one of these 1-bit occlusion buffers, then you can create a hierarchical Z-buffer from it, which does allow you to test any occluder with just 4 samples. This is a very old technique (1993?), but was used very recently in a splinter cell game.

I always found that the memory bandwidth was the biggest issue with software rasterization, which would link the performance to the frame buffer size. However, using one bit per pixel like Hodgman would probably alleviate that issue nicely...