What is a Ray Tracer?

Glossy gold

A ray tracer is software that can create images resembling real life scenes or images.

The quality of these images and how good a ray tracer is at achieving this goal, entirely depends on how good the coder(s) behind the ray tracer is.

Writing a serious ray tracer (for a single person) takes years. Writing a basic ray tracer can be done in weeks or less.

Ray tracing is writing software (most commonly in C/C++), that simulates images using mathematically defined objects, camears, lights etc. and have a computer show us, what it looks like, after our code has had its say.

To achieve it it's all about math, and in particular, vectors. Vectors form the fundamentals of ray tracing.

We can't mimic the real world yet... not even close. Even with the incredible power our home computers boast today, we are very very VERY far from anything, that mimics real life scenes.

A standard home computer is capable of doing about 60 GFLOPS (2016/2017) (Giga Floating Point Operations Per Second)... or sixty BILLION floating point ops/sec.

That is a lot of computing power indeed but still, in effect, impossibly far from enough to do real time ray tracing of real scenes.

Hollywood companies use thousands upon thousands of XEON based multiprocessor servers in strings, to generate the 24 or 60 images/second they need. Add 3D movies to that.

A single 18 core XEON based server is about $10000. There's a reason Hollywood animated movies have a heavy price tag.

90+ percent of bulding a ray tracer is optimizing and making it smarter, because ray tracing eats computer power for breakfeast.

Ray tracing has given us "Rattatouille", "Finding Nemo", "Ice Age", "Cars", "Planes" etc., and resulted in the first ever academy award for a danish dude, Henrik Van Jensen, for his extreme new technologies, "Sub surface scattering" (Gollum in "The lord of the Rings), and "Photon Mapping" (an efficient and accurate Global Illumination technique).

I don't know if he directly contributed to "The Martian" with "Matt Damon", but he did a lot of the ground work.

Henrik Van Jensen, academy award winner!.. and a ray tracing coder at heart, looking at his code, and just watching his results. (Gollum for his realistically looking skin, sub surface scattering)

So. Bottom line, ray tracing tries to recreate real life images, using math.

Everything in rayracing is math: The camera, shapes, environment, movement, materials, lights etc.

Example of a real life scene:

In your living room you have a lamp on your table top. It has a standard light bolb that emits light (photons in every direction).

So this light source emits an endless amount of photons in a virtually infinite number of directions from where it is located.

We _could_ write a program, that recreated this scene... but it would never get finished rendering.

It would need to follow every single (an infinite number) photon emitted by the light source, bounce the photon around in the scene, determine hits on reflective or refractive shapes, and maybe.... _maybe_ camera hits.

A photon would register only when it mathematiclly _exactly_ hit the eye (single 3D point) of the camera. So, in other words, only an extremely small number of samples would ever meet the camera and we would be wasting an enormous amount of computing power on nothing.

So... we need another technique, and it is not that complex: Reverse (or backward) ray tracing:

The principle is rather simple: You fire a ray from the eye or camera, and gather the information from whatever that ray hits, to finally shade the pixel you are currently rendering.

THIS is basically it. Send a ray into the scene, and find the color of what ever it hits... including reflection and refraction,

So, let's stick with _backward_ ray tracing.

We send rays into the scene, from our eye (camera) and our camera looks through all the pixels of our screen, pixel by pixel.

Lets say we have a monitor that has a resolution of 1920x1080, the camera would start shooting rays through the upper left corner of the screen, (x, y) = (0,0), and continue onto (x, y) = (1,0) and so on.

Based on the 3D position of the camera, and the definition of the camera plane, a ray vector is generated for each point, and shot into the scene.

From here on, using each ray shot from the camera:

Loop through every pixel on the screen and shoot a ray from the camera

The most simple rendering routine, iterating every pixel on your screen:

void RenderScene()
{
    Ray ray;
    ColorRGB color;
    for (int y = 0; y < heigth; y++)
    {
        for (int x = 0; x < widtht; x++)
        {
            ray = scene->camera->GetEyeRay(x, y);
            if (intersect(ray, &color))
            {
                putpixel(color);
            }
        }
    }
}

In that example ColorRGB is a simple class that holds the R, G and B values.

Th Ray class is more complex, because I use it to also keep track of where it is (inside or outside an object), direction, where it came from (position and object and, possibly, which polygon), the normal of the last hit, etc.

class Ray
{

public:
    Ray()
    {
        nofShapesInList = 0;
        Reset();
    }

    Ray(Point_3D& origin, Vector_3D& dir)
    {
        nofShapesInList = 0;
        PSetP(origin, origin);
        VSetV(this->dir, dir);
        closestIntersect = FLT_MAX;
        insideShape = false;
        rayDepth = 0;
    }

    ~Ray() {}

    // The direction of the ray
    Vector_3D dir;

    /**
    * The point from which the ray originated. This may be the camera
    * or any object surface, eg. a mirror ray
    * */
    Point_3D origin;

    /**
    * The intersect is the 'final result' after determining the intersection
    * (if any) that is closest to the origin point
    * */
    Point_3D intersect;

    // The normal vector at the surface we hit
    Vector_3D normalAtHit;

    // If the shape we hit is a mesh, this is the polygon in the mesh
    Poly* hitPoly;

    /**
    * closestIntersect is the 'final result' after determining
    * the intersection (if any) that is closest to the origin point
    * */
    double closestIntersect;

    // Which object (if any, ie. not the camera) did the ray come from?
    Shape* fromShape;

    // The object (closest) hit by the ray
    Shape* hitShape;

    // Specifies whether the ray currently travels inside an object, eg. a glass sphere
    bool insideShape;

    // 2D screen coords
    double traceX, traceY;

    // 2D coords with offset used for antialiasing
    double offsetX, offsetY;

    // Complete list of shapes in the scene
    Shape* shapeList[MAX_SHAPES];

    // Used to iterate over all the shapes in the sceneww
    unsigned int nofShapesInList;

    // Unused for now
    BoundingRectangle* hitBR;

    // Keeps track of the depth the ray is at right now
    BYTE rayDepth;

    // Lets us know where to look in the texture buffer for the hit object
    int textureBufferX, textureBufferY;

    void Reset();
};


If you had enough computer power at your disposal, it wouldn't be about anything else than just vectors. Dissapointingly it's not that simple. We (not even Hollywood) do not have that kind of computer power. We have to be smart about it.

Acceleration techs.

In ray tracing we talk about 'scenes'. "We render a scene". So what is a scene?

A scene is everything our camera sees through its lens... all the objects, dirt in the air, flies flying around, dirt on the table.

So like a scene in the theatre, everything is set up, and your eyes are the camera. Take a still picture with an actual camera, and it would take a picture of the 'scene'.

This picture is what ray tracing is all about. Ray tracing attempts to recreate real life 'scenes' using _math_!

A vector describes an origin point and a direction, that is, a straight line that moves from a three dimensional point to another three dimensional point... a line in 'space'.

Just playing around with LEGO ;-)

What does it take?

Coding a ray tracer of _any_ quality takes a lot of time and effort. It does not come easy.... you have to want it.

Coding a basic ray tracer is relatively simple.

If you don't care about scenes, flexibility, repeatability, GUI, acceleration techs etc. you can do it in a few hundred lines and get impressive results, only using mathematically defined spheres, planes etc.

When you expand your ray tracer to use distribution ray tracing tehniques, it is a whole different ball game.

The sheer number of computations/pixel needed for distributed ray tracing of any sort (antialiasing/DOF/softShados/Gloss/Translucensy/MotionBlur) is staggering, and you cannot continue without using acceleration techniques.

Ray tracing really shows how computers can be used to do stuff other than bored-to-death spread sheets, word processing and project management softwares.

Imagine using just _math_ as your paint brush to create paintings.

Ray tracing is, not just in a sense, an art !

I guarantee: Every single person, who ever built a ray tracer, has spent hundreds, or more likely, thousands of hours looking at the images his ray tracer generated...astonished at how a new technique worked out or just learning new things from errors in the image... then perfecting, optimizing and enhancing his code.

My ray tracer

So far, I've covered the basics plus a little, including a flexible pinhole camera, reflection, transmission, shadows with multiple lights and a few distribution ray tracing techniques.

I use mathematially defined objects, like spheres and planes (for speed) (only convex so far, and I don't have a generic quadratic intersetion function) and I've implemented importing meshes based on various formats, e.g. .3ds, .obj, .fbx etc. using the ASSIMP library. This opens up an entirely new world of possibilities.

I've just succeded in compiling the assimp lib (v 3.2) to 64 bits, pretty much eliminating my previous memory-problems.

(For opengl users, assimp is the god of library gods. If you have your own model (mesh model) however, it is not that easy.

One bottleneck is the the mapping of the imported data to your own mesh-model, but there are a lot of examples out there on how to read the data.

Assimp is, in my humble opinion, poorly documented however.

A lot of people have serious problems getting textures working. I am among them, but maybe it's simply due to a lack of brain cells but it's very fustrating.

So far

Included in my ray tracer are a lot of techniques to speed up the rendering process.

Among the most important are:

  • Octree based axis aligned bounding boxes
        // Depths/ Nof AABB children:
        // 0:    1
        // 1:    8
        // 2:    64
        // 3:    512
        // 4:    4096
        // 5:    32.768
        // 6:    262.144
        // 7:    2.097.152
  • List of smallest intersected AABBs
  • Only test against polys in the smallest interseted AABBs
  • Multithreading
  • Primary ray bounding rectangles
  • Last hit shadow shape
  • Visible shapes in normal direction (polys)
  • Visible lights in normal direction (polys)
  • Threshold for depth of field (if a predefined number of rays do not differ more than threshold, discontinue)
  • Threshold for soft shadows (as above)
  • Threshold for anti aliasing (as above)
  • Threshold for glossy surfaces (as above)

Any ideas are welcome, because my sphere intersection tests are in the hundreds of billions in a relatively simple scene with only about 100 spheres (using Depth Of Field and Soft Shadows). Even though I immediately use a dot-product test to check whether the sphere is behind the origin, several 100 billion tests are costly.

Beyond that, I've done

  • Antialiasing
  • Soft shadows
  • Depth of field
  • Glossy surfaes (not nearly done, but I've had ok results)

 Future

  • Multi-processing in a network (only a vague idea of how to do it, but the potential is there to solve any speed issues)
  • Translucency (oh, ooh.... another exponential inrease in pixel-time)
  • Photon mapping (Henrik Van Jensen, the god and creator of Photon Mapping. Bought his book, and it presents the basic code for a basic Photon Mapping class)
  • Sub surface scattering (Again, Henrik Van Jensen, father of Photon Mapping, comes to the rescue)
  • Motion blur... well this implies motion, i.e. that my stuff actually moves.... so there's a lot of work to be done before motion blur is even needed
  • ...

Glossy golden flat 'boxes', just to see how it worked with different values. I notice a problem though:
If you look at the reflection of the boxes in the spheres, they are clearly more reflective (or less glossy ;-). This is very likely because the (single) light is in front of the boxes. Maybe some tweaking around with the diffuse and ambient part of the surfaces will lessen this.
This image took a little over two hours to render with two threads.

Partially finished glossy surface test

The finished image... about three hours to render. Glossy surfaces are expensive ;-)

A pretty ok example of a glossy surface. A max of 220 samples/pixel were shot.

Ray tracing... a life style

 


 

I've been at it for years, writing my ray tracer. I've had periods also lasting years, where I didn't touch the code. But it was always there, in my thoughts, haunting me, since I started.

Recently I revived it, and tried porting my old C-code to run in a WPF (Windows Presentation Foundation) environment.

God help me... but I had to revert to MFC (Microsoft Foundation Class), simply to be able to run on Windows, have a GUI, real-time output and have the benefits of C++ vs C#.

WPF was fantastic, as far as creating the user interface goes. WPF _rocks_ on the UI front, but C# lets you down HARD on the performance part, if you insist on not using DirectX, opengl etc, but want your own code to do the math and be completely independant of OS's and rendering technologies that target GPUs.

Note 1:
I may be wrong, but my guess is, that Hollywood does not rely on GPU power, and rather on multiple core CPU power.... maxed out beyond belief. That is really the difference between games "simulating" ray tracing and "real ray tracing".

Note 2:
I know the games do not just simulate the ray tracing stuff... its real alright, to some extend.

Games are not likely to do distribution ray tracing any more than they absolutely have to, to get great results, including antialiasing, and probably 'fakes' (to some degree) others types of distribution ray tracing.

Bottom line though: Photo realistic ray tracing, and distribution ray tracing techniques are way way way too slow, for even hundreds of the fastest GPU's to render realtime.

Gaming "ray tracing" is suited for _one_ GPU (Graphics Processing Unit), and most importantly, its not meant to be 'as beautiful' as possible, but a mix that must also be as efficient as possible... and again....based on _one_ GPU... the gaming machine, it lacks in beauty.

Even in the Hollywood film industry, they have to 'cut corners'. The animation movie "Cars" (McQueen) was rendered with a maximum ray depth of 2, and only when zooming in on stuff where it really showed, like chrome bumpers etc.

Hence, 'real' ray tracing is based on CPU, not GPU performane.

 

Back to WPF/C#:
I literally tried for _months_ tweaking the code, googling, investigating, and using every (dirty) trick, to get it up to par.

Turns out, that my old C-code was just extremely much faster and, no matter how hard I tried, I could not get C# to do anything even close. There are many reasons for this... managed code, exception handling, intelligent lists vs 'dum' one-way-pointer-linked lists ec.

A suggestion for anyone with serious speed problems in your ray tracer.... if you use built in lists of any kind, including "vector" from the standard library.... drop it. We are talkng factors of 20+, that you can gain, by making your own linked pointer lists.

I can easily live with my own linked lists (classes with next-pointers) and they kick ass in comparison, by a factor of about well many... 20 easly, more likely 50 (!!)

Also, and perhaps even more significant, if a method is called literally hundreds of billions of times, the overhead of the method call (allocation on the stack) starts to matter very significantly, so the bless of C/C++ macros comes in to play.

I C# you cannot use macros.

The general (and great) rule is, that you never access member variables of a class directly (fields in C#), but use getters/setters.... in C#, you can use properties that handle it for you.

Thing is... C# properties also do method calls behind the curtain, when you set or get a value and thus do a method call => overhead.

The solution is not as pretty, but it _is_ extremely effecient: declare the member variables you need access to, public, and access them directly!

It takes a little more discipline in your code, if you want to keep an OO design, but it kicks butt performance wise.

SPEED paramount in ray tracing, but it requires self discipline.... or it'll bite ya.

Glass tank (solid glass) and tile floor. Soft Shadows, Antialiasing. Click to enlarge.

Couple'a spheres, Red brick floor, glass tank (solid glass), Antialiasing. Click to enlarge.

Couple'a spheres, Red brick floor, glass tank (solid glass), Antialiasing, top view. Click to enlarge.

Background image... one of my first using depth of field