Speeding up convergence: am I reinventing the wheel?

Question

I'm trying to learn about raytracing by implementing things in Python 3. I know this is always going to be slower than something like C++, and I know the speed could also be improved by using GPU raytracing, but for this question I'm not looking for general ways of speeding up, but specifically ways of reducing the number of samples required, which will then be useful for any language I may work with in future.

---

I have a partly formed idea which I'd like to work on, but first I wanted to run this past the experts to see if this is a pre-existing technique so I don't repeat work that has already been done.

I've searched for "sampling solid angle" and "voronoi sphere sampling" but I can't see any sign of prior work. I'll describe my idea in case it goes by a name I can't think of.

Example image

This is an image of three spheres on a plane (which is actually a very large sphere). One is emissive, one is reflective, and one is matt (as is the floor). Sampling is adaptive so that pixels that quickly reach a stable colour do not take up much time. I limit the total number of samples per pixel to avoid the rendering continuing for too long. Even allowed to run overnight, the resulting image is very grainy, and experimenting with smaller images suggests this size image (1366 by 768) would take weeks to converge with my current approach.

My idea: concentrating samples along colour boundaries

I'd like to be able to concentrate samples where they are needed, and to do this adaptively based on previous samples for the same intersection point or pixel. This will give an unknown bias in the distribution of samples, which means taking the average of the samples will give an inaccurate result. Instead I would like to consider the size of the voronoi cell on the surface of the unit hemisphere centred on the point of intersection (for sampling light incident at a point on a matt surface) or on the surface of a small circle (for sampling around a pixel).

Assume that all points within that voronoi cell are receiving rays of the same colour as the centre of the voronoi cell. Now an estimate of the average colour can be obtained by weighting according to the area of each voronoi cell. Choosing new samples on the boundary between the two voronoi cells with the greatest difference in colour leads to an improvement in the estimate without needing to sample the entire hemisphere. Samples should end up more densely concentrated in areas of higher colour gradient. Areas of flat colour should end up being ignored once they have a few points near their boundary.

The extra complication is that in both cases (sampling from a point on a matt surface, or sampling over a circle around a pixel centre) the simplified approach I have described is roughly equivalent to a large number of samples distributed uniformly. To make this work I would need to be able to bias the average by both the voronoi cell areas and the required distribution (cosine around the surface normal for a matt surface or gaussian around a pixel centre).

So I have some more thinking to do before I could test this idea, but I wanted to check first if this has either already been done, or already ruled out as unworkable.

Answer 1

It sounds like you're trying to do adaptive subdivision on the surface of a hemisphere.

This has indeed been tried before, although perhaps not in the exact way you're thinking. Usually for hemispheric integration, people use some well-distributed, pre-defined sampling density over the hemisphere and forget about adaptive subdivision.

---

But you may be missing the point.

The whole idea of doing such things is to get a better estimate of the integral. But it's not the integral over the hemisphere you care about. You're integrating over the pixel to get AA, over the aperture to get depth-of-field, over the lights to get soft-shadowing, over the hemisphere to get GI, over time to get motion blur, over wavelength to get dispersion, and so on. You're integrating over all that. This is an absurdly high-dimensional space, and decades of development have shown that you need to be exploring it not more carefully, but faster. That is, you get better results from breadth, not depth.

All very abstract.

The point is this: you don't want to sample over the hemisphere with lots of samples. You want to sample over your hemisphere with one sample and then move on. This is called path tracing. It differs from ray tracing in that the maximum width of the ray tree is 1 (or maybe 2).

The key insight is that if your random samples are well-distributed with respect to all dimensions, other rays will "fill-in" the rest of your missing tree.

For an intuitive example: say you're doing 4x AA. So you shoot four rays through a pixel. Probably, they hit in very similar points (creating similar reflectance hemispheres). Then, they each shoot exactly one recursive ray. But, since the four hemispheres are in almost the same place, the recursive rays (kindof) count for all the hemispheres. So each of the four paths gets some of the benefit of the other three.

That's sortof handwavy math, but since each path is actually independent of the others, and the color you get is an unbiased estimate of the entire scene's illumination, averaging them together is unbiased. It just converges much faster in practice.

Obviously, if a cheap estimate of the hemisphere's integral is available, you can just use that--this is preintegration (cone tracing, etc.), importance sampling (next event estimation, light sampling), or better paths (BDPT, photon mapping)--but for a simple approach, it's basically always better to use path tracing instead of stochastic ray tracing.

---

_{Also matt -> matte (or mat, in a pinch). It's a French loanword, not a person's name, and I don't care what the American dictionaries say.}