Psychopath Renderer

a slightly psychotic path tracer

Low Discrepancy Sequences

As a follow-up to my post about random numbers, I'd like to ramble a bit about low discrepancy sequences.

Low discrepency sequences (or LDS's as I'll refer to them) are deterministic sequences of points in an n-dimensional space that attempt to be as well distributed and evenly spaced as possible. That's quite a mouthful, but the high-level idea is pretty simple. For a more complete introduction to LDS's I recommend reading chapter 7 of Physically Based Rendering: From Theory to Implementation by Matt Pharr and Greg Humphreys (it's an amazing book, by the way, which you should totally buy if you're at all interested in 3d rendering).

But, suffice it to say, LDS's are really useful. In many contexts they can be used as a drop-in replacement for random numbers to reduce variance. In my case, with a unidirectional path tracer like Psychopath, if I plug an LDS where I otherwise would use random numbers, I get some nice reductions in noise.

Random numbers @ 16spp:

Low discrepency sequence @ 16spp:

Notice the significant reduction in variance in the LDS render compared to the random one. But also notice the patterned appearance of the variance in the LDS render, especially around the edges of shadows. This is an artifact of using the LDS directly.

Another drawback of using LDS's directly is that you have to decide ahead of time how many samples you're taking. A lot of the time this doesn't matter. But if you're doing progressive rendering or adaptive sampling that can be a real limitation.

Fortunately there is a single solution that addresses both of these problems, and that is to decorrelate the samples between pixels. The idea is that each pixel still draws from a single continuous LDS sequence, but the pixels are each randomized with respect to each other. That way you still have good convergance within each pixel, but each pixel is random with respect to all other pixels.

One popular way to do this is called "Cranley Patterson Rotation". The idea behind Cranley Patterson Rotation is to randomly generate a vector, and use that vector to offset the values of all the LDS points. To keep the resulting values within the interval [0,1], you do the offset modulo 1.0 so that resulting values greater than 1 wrap back to start at zero again.

If you do Cranley Patterson Rotation using the same vector for all pixels, you don't gain anything. But if you use a different random vector for each pixel then you get a noisy non-patterned image that still has less noise and converges faster than a truly randomly sampled image.

But Psychopath doesn't use Cranley Patterson Rotation. It uses a different technique to accomplish essentially the same thing.

Some LDS sequences are endless. You can keep drawing points from them forever, and they will never run out. Such LDS's have an interesting property: any contiguous subset of the sequence is also an LDS. A cool implication of this is that you can start drawing samples from anywhere in the sequence, and it's just as good as if you started at the beginning.

Psychopath exploits that by giving each pixel a random offset into the LDS. So, for example, the first pixel might have an offset of 42, meaning that it starts drawing samples at the 42nd sample. The second pixel might have an offset of 518,364,163, meaning that it starts drawing samples at the 518,364,163rd sample. Both pixels will get equally good samples, but they are both totally random with respect to each other.

The end result is this (@16spp):

It's slightly higher variance than using the LDS sequence directly (but still much lower variance than random sampling), but it has the same convergence properties and it avoids the pattern artifacts. It also allows us to draw endless samples for each pixel without worrying about the number of samples being drawn for other pixels, which is a big win if you want to do e.g. adaptive sampling.

The main benefit of this technique over Cranley Patterson Rotation is computation. You only need to generate a single random value with this technique, and do a single integer addition. With Cranley Patterson Rotation you have to generate an entire vector of random values, and as many floating point additions and modulo.

The main drawback compared to Cranley Patterson Rotation is that this only works with endless LDS's. But in practice that's not a significant restriction, because most practical LDS's (at least that I'm aware of) are endless.

Finally, credit and a huge thanks must go to Leonhard Grünschloß for the LDS code I'm using. Psychopath uses his Faure-permuted Halton sequence, which is available on his site. I am extremely grateful to him for making his LDS code freely available, because I am, frankly, not smart enough to implement anything more complex than a simple Halton sequence.

Ray Tracing Micropolygons

I feel like I have a lot of catching up to do blogging-wise. I've been working on Psychopath for quite a while now, and I've learned a lot in the process already. I'd like to write about some of that stuff, so for starters I'm going to make a few posts covering how Psychopath's ray tracing kernel has evolved so far.

As I mentioned in my first post, I started Psychopath with the goal of building a proof-of-concept micropolygon path tracer. From the very beginning that goal guided me to make some atypical choices with Psychopath's architecture, and I've continued to make a few atypical choices as the architecture has evolved.

Here's a fun picture:
Colorful Patches

This is an early render from Psychopath. In fact, if you build the earliest commit in the github repo and run the resulting executable, it will produce this image.

But what the hell is it?

It's a bunch of bilinear patches, rendered by first dicing them into sub-pixel-sized polygons and then tracing rays against them. The rendering architecture at this point was basically a direct (but simplified) implementation of the approach described in "Ray Differentials and Multiresolution Geometry Caching for Distribution Ray Tracing in Complex Scenes". It traced one ray at a time, and used a geometry cache to store the results of dicing for use by later rays.

For splitting, I stored the results directly in the scene's acceleration structure (in Psychopath's case, a BVH), modifying the structure in the process.

(If you're confused when I talk about "splitting" and "dicing", I recommend reading the original Reyes paper by Cook et al., which explains the concepts and how they are used together.)

You might notice that there isn't any lighting. That's because at this point Psychopath only did visibility testing. The two different patch colors represent whether the surface normal is facing towards or away from the camera.

It's interesting to see that even in this early version I implemented motion blur. I think that's because I'm an animator. When I think of "important" rendering features, motion blur pops to the top of my list pretty quickly. It always frustrates me to see an otherwise feature-complete renderer that I could never use for character animation, simply because it doesn't support deformation motion blur. So I made that a core part of the renderer from the beginning. (There is, in fact, deformation motion blur going on in that image, though it's masked by the extreme camera motion blur.)

Anyway... so this is pretty much the beginnings of Psychopath. It took me quite a while to even get to this point. I wish I still had the early ray-triangle intersection tests I did, because it's not as if I just sat down and spit this out in a weekend. Even getting this far was a large undertaking that involved a lot of learning and trial-and-error. But this was the point where I really reached my first goal with Psychopath: micropolygon ray tracing.

Random Numbers

(I'm copying this post over from my personal blog, as it seems relevant. Note that C++11 actually defines a quite robust RNG suite that includes the Mersenne twister. Nevertheless, having a simple, robust, purpose-made RNG class can still be handy.)

For most simulation applications (global illumination rendering being a good example) the included random functions in e.g. most C or C++ standard libraries are insufficient. Moreover, it is important to be able to guarantee that the RNG you are using is consistent across platforms and satisfies specific properties of randomness. Therefore it is generally a good idea, in these applications, to include a custom RNG implementation and use that.

The go-to RNG for such purposes these days is the Mersenne Twister, and as such that is the RNG I've been using in Psychopath up to this point. But the code for it is quite complex. And as it turns out, there are other RNG's out there that are pretty much just as good, but have far simpler code.

Several such RNG's are covered in the short and accessible paper "Good Practice in (Pseudo) Random Number Generation for Bioinformatics Applications" by David Jones. I have opted to use his JKISS generator, which is a variation on George Marsaglia's KISS (Keep It Simple Stupid) RNG.

You can see my implementation here.

The generator has very good statistical properties, passing a large battery of intensive tests as outlined in the paper. In fact, it appears to be just as robust as the Mersenne Twister in almost every respect. The only way in which is it less robust is period length. Mersenne Twister has the enormous period 2^19937-1, whereas JKISS has a period of roughly 2^127. JKISS's period is still very large, however, and is very appropriate for most practical applications, 3d rendering included.

For applications that require larger periods, several other simple-yet-robust generators are also listed in the paper, some of which have enormous periods exceeding even the Mersenne Twister.

Welcome! And a Little History

A little over three years ago I read the paper "Ray Differentials and Multiresolution Geometry Caching for Distribution Ray Tracing in Complex Scenes" by Christensen et al.

I was inspired.

I was (and am) a huge fan of the Reyes rendering architecture, but the industry was clearly moving away from Reyes towards global illumination ray tracing. I didn't see that as a bad thing—ray tracing clearly has a lot of benefits over Reyes. But Reyes has a lot of cool properties that are lost in that move to ray tracing.

Reading that paper by Christensen et al. gave me the idea that it might be possible to merge both worlds: ray tracing and on-the-fly micropolygons. And I was curious how a renderer built on that paper's algorithms would perform when used as the basis for a path tracer. So I set out to write a simple proof-of-concept, just to see if I could make it work. The idea seemed kind of crazy, so I decided to call the renderer "Psychopath", for "Psychotic Path Tracer". I was just tinkering for fun, after all.

Three years later and I'm still working on it. It's been long enough (and addictive enough) that I'm pretty sure I'm not going to stop any time soon. So I'm making a website for it.

I have pie-in-the-sky hopes that I'll be able to turn it into a genuinely useful 3d renderer. But who knows. Ultimately, Psychopath is a platform for me to experiment with weird/crazy rendering ideas.

At this point there is very little (if any) of the Christensen et al. paper left in Psychopath. But I nevertheless owe the authors a debt of gratitude for the inspiration. It's a really cool paper.