Radiosity Visibility Preprocessing

Do you already have any visibility information for your map, such as a PVS set? Because you can use that to cull entire regions that aren't visibility to one another before you trace rays between them. Instead of ray tracing, you could try an image-based approach where you render the scene from the perspective of the source patch, and see how many pixels from the destination patch are in the final image. That might be faster since simple triangle rendering is blazing fast on modern cards. There are also methods you can use to cut down on the number of patches in general, such as non-uniform subdivision -- areas with low-frequency light variation have larger patches than areas with high-frequency light variation.

These are just a few general ideas off the top of my head that others will surely expand on or add to.

No, I don't have a PVS. That's basically what I'm trying to calculate. The way I'm doing it is just too slow at the moment. I will use a hemicube technique for my radiosity renderer, as you are advising, only if I can't find any faster solution.

The problem with the hemicube technique is that it's an approximation. If you add on top of that the approximation from interpolating lighting between the patches, etc... I don't know if I can get a solution that looks any good. To add to that, I am trying to reproduce "Radiosity Normal Mapping" as seen in the Source engine. And to do that, if I understood correctly, the radiosity calculation has to be done three times, changing the normal of each patch every time. Femicubes do not really allow that because they embed the form factor calculation into a texture.

Re: slow visibility calculations.

I saw an enormous increase in speed from simply preprocessing a per-polygon dotproduct visibility test. For all triangles or polygons in the scene, store a flag for which other polygons that faces away from it (and therefore has a formfactor of zero. For each patch in the scene, keep a reference to which polygon / triangle it is part of. That way, when you do all the patch-to-patch checks, you can discard huge piles of patches simply by reading through the poly-see-poly data. Very easy to code, and sees huge improvements.

First, patch to patch type of radiosity solvers with explicit form factor calculations (such as hemicubes) aren't really well suited for any moderatly complex environment. They're inherently slow due to their essentially O(n²) behaviour. This can be somewhat alleviated by using adaptive shooting or gathering hierarchies, but the main problem remains. And many aggressive hierarchical solutions (such as those required to get O(n log n) time complexity) will introduce heavy artifacts. The real world (and keep in mind that radiosity is a physically based technique) doesn't subdivide adaptively ;)

Second, stay away from hemicubes as a way to evaluate the form factor, unless you are writing a realtime radiosity renderer on the GPU. They introduce very annoying artifacts, and aren't as efficient as they used to be in the past. On todays multi core CPUs, using a good raytracing approach will be much faster in most cases.

That said, there are solutions you can try. The most straight forward speed up is heavy space subdivision. I guess you have already done that, but I'll mention it nonetheless.

The most important drawback however, is the whole patch-to-patch approach with explicit form factor evaluation. This is a very slow process, however you might turn it. The only real solution, and the one used by almost all 'professional' global illumination packages (ie. V-Ray, Maxwell, Mental ray, etc), is replacing the explicit FF by an implicit evaluation approach. I'm talking about multi-stage stochastic/QMC radiosity with irradiance maps.

This approach has several very important advantages over simple patch-to-patch radiosity:

* Much, much faster. Speedups of x100 are not uncommon on large scenes

* Better quality, since adaptive subdivision is usually not required

* No mathematical singularity in the equation, such as the one in common patch-to-patch systems (the 1 / (pi*r²) term). This means that you will not get any artifacts on very close edges. On explicit formfactor systems, these will often manifest themselves are bright spots near object edges, that are both ugly and almost impossible to get rid off.

* Easy to implement and to parallelize onto multiple CPU cores.

I would really suggest you dig into this direction.