Monday, April 25, 2016

Level of noise in unstratified renderers

When you get noise in a renderer a key question, often hard to answer, is is it a bug or just normal outliers?   With an unstratified renderer, which I often favor, the math is more straightforward.   Don Mitchell has a nice paper on the convergence rates of stratified sampling which is better than the inverse square root of unstratified.

In a brute force ray tracer it is often true that a ray either gets the color of the light L, or a zero because it is terminated in some Russian Roulette.   Because we average the N samples the actual computation looks something like:

Color = (0 + 0 + 0 + L + 0 + 0 + 0 + 0 + L + .... + 0 + L + 0 + 0) / N

Note that this assumes Russian Roulette rather than downweighting.   With downweighting there are more non-zeros and they are things like R*R'*L.   Note this assumes Color is a float, so pretend it's a grey scene or think of just each component of RGB.

The expected color is just pL where p is the probability of hitting the light.    There will be noise because sometimes luck makes you miss the light a lot or hit it a lot.

The standard statistical measure of error is variance.    This is the average squared error.   Variance is used partially because it is meaningful in some important ways, but largely because it has a great math property:

The variance of a sum of two random quantities is the sum of the variances of the individual quantities

We will get to what is a good intuitive error message later.   For now let's look at the variance of our "zero or L" renderer.   For that we can use the definition of variance:

the expected (average) value of the squared deviation from the mean 

Or in math notation (where the average or expected value of a variable X is E(X):

variance(Color) =  E[ (Color - E(Color))^2 ]

That is mildly awkward to compute so we can use the most commonly used and super convenient variance identity:

variance(X) = E(X^2) - (E(X))^2

We know E(Color) =  pL.    We also know that E(Color^2) = pL^2, so:

variance(Color) =  pL^2 - (pL)^2 = p(1-p)L^2

So what is the variance of N samples (N is the number of rays we average)?

First it is the sum of a bunch of these identical samples, so the variance is just the sum of the individual variances:

variance(Sum) = Np(1-p)L^2

But we don't sum the colors of the individual rays-- we average them by dividing by N.   Because variance is about the square of the error, we can use the identity:

variance(X / constant) = variance(X) / constant^2

So for our actual estimate of pixel color we get:

variance(Color) =   (p(1-p)L^2) / N

This gives a pretty good approximation to squared error.   But humans are more sensitive to contrast and we can get close to that by relative square-root-of-variance.   Trying to get closer to intuitive absolute error is common in many fields, and the square-root-of-variance is called standard deviation.   Not exactly expected absolute error, but close enough and much easier to calculate.    Let's divide by E(Color) to get our approximation to relative error:

relative_error(Color) is approximately   Q = sqrt((p(1-p)L^2) / N) / ( pL)

We can do a little algebra to get:

Q = sqrt((p(1-p)L^2) / (p^2 L^2 N) ) = sqrt( (1-p) / ( pN) )

If we assume a bright light then p is small,  then

Q is approximately sqrt(1/(pN))

So the perceived error for a given N (N is the same for a given image) ought to be approximately proportional to the inverse squareroot of pixel brightness, so we ought to see more noise in the darks.

If we look at an almost converged brute force cornell box we'd expect the dark areas to look a bit noisier than the bright ones.   Maybe we do.   What do you think?









Sunday, April 3, 2016

Debugging by sweeping under rug

Somebody already found several errors in my new minibook (still free for until Apr 5 2016).    There are some pesky black pixels in the final images.

All Monte Carlo Ray Tracers have this as a main loop:

pixel_color = average(many many samples)

If you find yourself getting some form of acne in the images, and this acne is white or black, so one "bad" sample seems to kill the whole pixel, that sample is probably a huge number or a NaN.   This particular acne is probably a NaN.   Mine seems to come up once in every 10-100 million rays or so.

So big decision: sweep this bug under the rug and check for NaNs, or just kill NaNs and hope this doesn't come back to bite us later.   I will always opt for the lazy strategy,  especially when I know floating point is hard.

So I added this:


 There may be some isNaN() function supported in standard C-- I don't know.   But in the spirit of laziness I didn't look it up.   I like to chase these with low-res images because I can see the bugs more easily.    It doesn't really make it faster-- you need to run enough total rays to randomly trip the bug.   This worked (for now!):

Left: 50x50 image with 10k samples per pixel (not enough for bug).    Middle 100k samples per pixel.   Right: with the NaN check. 



 

Now if you are skeptical you will not that by increasing the number of samples 10X I went from 0 bugs to 20+ bugs.   But I wont think about the possibly troublesome implications of that.   MISSION ACCOMPLISHED!

Saturday, April 2, 2016

Making an "In One Weekend" Kindle Book


Over the last few months my side project has been a series of three Kindle mini-books on ray tracing.   Ray tracing is a computer graphics programming area to produce nice images and ray tracing has been hot lately (most computer animated films are now ray traced, are are many of the special effects shots in regular movies).   This post is not about those books specifically, but is instead describing my experiences and encouraging others to write similar mini-books on other subjects. I promote and document the books at in1weekend.com If you have something (book, youtube, blog, whatever) to help people learn something in a weekend, let me know and if I can learn from it I will promote it on my site!


Here are the books at Amazon: 

Ray Tracing: The Rest of Your Life

I set my price for each book at $2.99.   Conversions for other countries Amazon does automatically for you.   You get 70% of the sales if your book is priced from $2.99 to $9.99.   Amazon will let you give away the book for free for five days every quarter, and I began each book with a free promotion.   So far since early 2016 when I started, I have sold about 700 books and given away almost 3000.

CALL TO ACTION: It is easy and fun to make such books, and they make money, and give others a mechanism to see if they love the same things you do with just a weekend commitment.   I will show you the mechanics of how I wrote my instance of this.

THE MECHANICS WRITING THE TEXT:  Just write a Word file or a Google Doc and “download as” a Word file.    Really that’s it! Here is an example of my book on the Amazon cloud reader:
Two kindle pages with code screen shots, ray tracer output, and limnu drawing


THE MECHANICS OF CREATING FIGURES:  For drawings I used the shared whiteboard program from limnu.com.    I drew the figures on a tablet, and then opened them on my laptop (limnu stores your boards in the cloud so no file copying needed), and did a screen capture of the part of the image I wanted to make a figure (command-shift-4 on a mac), and then dragged the file into google docs.    For code samples I just screen-captured the code from vim. Here is my favorite limnu figure in the books:



THE MECHANICS OF CREATING A KINDLE BOOK:  Go to https://kdp.amazon.com/ and create an account.    Upload the word file.    Upload a cover image which must be tif or jpeg.   Amazon also has some tools for cover creation. It is all super-easy and has a great interface and here is a screen shot of the style of data entry:


ADVERTISING THE BOOK:   I used word of mouth and twitter and hackernews and facebook.   I also created a website in1weekend.com to promote the book.    If you do a book and I try it out and like it, I will make an article about your book and point to it.   You can feel free to use the “in one weekend” phrase in your title.

IT IS THAT EASY!   And now I feel like I have done some good spreading how-to information, made some cash, and helped my resume.   And it was surprisingly fun; I looked forward to working on the books when done with my other work.   I encourage you to try it, and if you write one please let me know and I will see if I can learn something new in a weekend.