dipityPix app

Tuesday, May 3, 2016

Machine learning in one weekend?

I was excited to see the title of this quora answer: What would be your advice to a software engineer who wants to learn machine learning?   However, I was a bit intimidated by the length of the answer.

What I would love to see is Machine Learning in One Weekend.    I cannot write that book; I want to rread it!    If you are a machine learning person, please write it!   If not, send this post to your machine learning friends.

For machine learning people: my Ray Tracing in One Weekend has done well and people seem to have liked it.    It basically finds the sweet spot between a "toy" ray tracer and a "real" ray tracer, and after a weekend people "get" what a ray tracer is, and whether they like it enough to continue in the area.   Just keep the real stuff that is easy, and skip the worst parts, and use a real language that is used in the discipline.   Make the results satisfying in a way that is similar to really working in the field.   Please feel free to contact me about details of my experience.  

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.

Thursday, March 31, 2016

Converting area-based pdf to direction-based pdf

One thing I covered in my new mini-book is dealing with pdf management in a path tracer.     Most of my ray tracers (and many others do it too) are set up to sample directions.   So at a point being shaded, the integral is over directions:

color(direction_out) = INTEGRAL   brdf(direction_in, direction_out) cosine

the domain of integration is all direction_in coming from the sphere of all directions.   Often the brdf is zero for directions from inside the surface so it's the hemisphere.

Basic Monte Carlo integration says that if you choose a random direction_in with pdf pdf(direction_in), the unbiased estimate is:

       color(direction_out)  =  brdf(direction_in, direction_out) cosine / pdf(direction_in)

As long as you can generate random direction_in, and can compute pdf(direction_in) then you have a working ray tracer.   It works best when you are likely to cast random rays toward bright areas like lights.    If you sample a polygonal light, you normally just sample q uniformly on the area.   The direction is just q-p.    The key observation to get from the pdf in area space p_area(q) = 1/A (where A is the area of the light) is that by definition the probability of q being in a small area dA is

       probability = p_area(q) dA

Similarly the directional pdf of a direction toward dA is:

       probability = pdf(q-p) dw

Those probabilities must be the same:

      p_area(q) dA =  pdf(q-p) dw

By algebra:

pdf(q-p) =  p_area(q) dA/dw = (1/A) (dA/dw)

But what is (dA/dw)?

Let's do some basic geometry.   As is so often the case, the right figure makes that tons easier: 


You pick a point q on the light with pdf 1/A in area space, but what is the pdf in directional space?   Drawn in limnu whitboarding program.

If dA faces p dead-on (so its normal faces p), then it's foreshotening:

      dw = dA/distance_squared

But if dA is tilted then we get a cosine shift:

      dw = dA*cosine / distance_squared

So recall we are after

      pdf(q-p) = (1/A) (dA/dw)

So we can plug and chug to get:

       pdf(q-p) =length_sqaured(q-p) / (A*cosine)

We just apply this formula directly in our code.   For my xz rectangle class this is:



Third and final ray tracing mini-book is out

My third and final Kindle ray tracing mini-book is out.    It will be free April 1-5, 2016.

Ray Tracing: The Rest Of Your Life (Ray Tracing Minibooks Book 3)

From the intro:

In this volume, I assume you will be pursuing a career related to ray tracing and we will dive into the math of creating a very serious ray tracer. When you are done you should be ready to start messing with the many serious commercial ray tracers underlying the movie and product design industries. There are many many things I do not cover in this short volume; I dive into only one of many ways to write a Monte Carlo rendering program.   I don’t do shadow rays (instead I make rays more likely to go toward lights), bidirectional methods, Metropolis methods, or photon mapping.   What I do is speak in the language of the field that studies those methods.   I think of this book as a deep exposure that can be your first of many, and it will equip you with some of the concepts, math, and terms you will need to study the others.

Friday, March 18, 2016

My buggy implimentation of Schlick approximation

One of the most used approximations in all of graphics is the Schlick approximation by Christophe Schlick.    It says the Fresnel reflectance of a surface can be approximated by a simple polynomial of cosine(theta).    For dielectrics, a key point is that this theta is the bigger of the two regardless of which direction the ray is traveling.
Regardless of light direction, the blue path is followed.   Regardless of light direction, the larger of the two angles (pictured as theta) is used for the Schlick approximation.

A sharp reader of my mini-book pointed out I have a bug related to this in my code.   I was surprised at this because the picture looked right (sarcasm).      The bug in my code and my initial fix is shown below.
The old code shown in blue is replaced with the next two lines.
My mistake was to pretend that if snell's law applies to sines,  n1*sin(theta1) = n2*sin(theta2), it must also apply to cosines.   It doesn't.    (The fix is just to use cos^2 = 1 - sin^2 and do some algebra) I make mistakes like this all the time, but usually the wonky-looking picture, but in this case it didn't.    It only affected internal reflections, and it just picked some somehwhat arbitrary value that was always between 0 and 1.   Since real glass balls look a little odd in real life, this is not something I can pick up.   In fact I am not sure which picture looks right!

Old picture before bug fix.
New picture after bug fix.

I am reminded of spherical harmonic approximation to diffuse lighting.   It looks different than the "correct" lighting, but not worse.  (In fact I think it looks better).    What matters about hacks is their robustness.    It's best to do them on purpose though...