Ray Tracing Performance and Practice Part 3

When last we left the ray tracer, it could read in PLY files and then render a scene.  But while it rendered, you'd probably want to get dinner, read some blogs, and write some code.  Very slow.  Improving performance is very straight forward: either reduce the work done or find a way to do the same work faster.

At the time of original development, I knew that there existed further performance opportunities via Oct Trees.  The idea behind these and other similar structures is to partition the scene into sub-scenes that can be treated in the aggregate.  Let's work through a simple example.

While the actual ray tracer is in 3D, we'll reason through a 2D tracer.  We'll have lots of circles and triangles in standard XY coordinates.  We can start partitioning the scene into quadrants: +X +Y, +X -Y, etc.  Now, when we draw a line (i.e., the ray) through the scene, rather than checking whether the ray is intersecting every circle and triangle, we can first check whether it is passing through any quadrant.  If the ray doesn't pass through the quadrant, then the ray will also not pass through any object in the quadrant.  The Oct Trees work very similarly, except besides X and Y, the scene is also split by +/- Z.

If the scene is split just once, this can likely provide some benefit, but for real practicality each octant of the tree must also be split repeatedly until only a few scene objects (i.e., spheres and triangles) remain in each octant.  This is all well and good; however, four particular problems arise: first, where should each octant be split.  Second, how many scene objects should be in each octant.  Third, how should objects that straddle octant boundaries be handled?  Finally, how does one practically render with an Oct Tree?

Where?  Two possibilities were tried: splitting in the "center" of the objects and splitting in the center of the octant.  If the split point is based on the objects, then each octant should have a similar number of objects.  This bounds the depth of the Oct Tree by making each octant have a subset of the parent octant.  However, this also forces every ray to traverse several levels of the Oct Tree, as every octant should contain scene objects.  Instead, if each octant is split at its center, then many octants may be empty, but the ones with scene objects may have significant number of levels in the tree before reaching individual objects.

How many?  Ideally, this number would be reached based on considerable experimentation and analysis.  At present, the code just splits an octant when it contains more than 16 scene objects.  Given the 50k triangle scene from the previous post, this would create roughly 3000 final octants, 375 parent octants, 47 grandparents, 6 great grandparents, and 1 root.  Ideally.

Yet, the split points are never ideal and so the octants are imbalanced.  Especially as some scene objects will cross the octant boundaries.  For example, a sphere placed at the origin is present in all 8 octants.  So the Oct Tree places the scene object into every octant that it is present within.  Rather than computing whether the object is precisely within the octant, the Oct Tree creates a bounding cube around the object.  Back to the 2D space, draw a triangle from (1,1), (-1, 1), and (-1, -1).  A square around this triangle would also include (1, -1), and therefore the triangle would also be "part" of the +X -Y quadrant.  I would be happy to switch to computing whether the object intersects the octant boundary planes; however, that would be when I understand the math involved.

The final issue is how to put the Oct Tree into practice.  In the immediate, the intersect code follows:

    if (No Octants) 

        foreach SceneObject in OctTree

        {

            Compute Distance for Ray to Intersect Object

        }

        Return closest object or none

    foreach Octant in OctTree {

        Compute Distance for Ray to intersect Octant

    }

    Sort Distances

    Select closest octant

    do {

        Recurse on octant

        if (Object returned) return object

        Select next closest octant

    } while (Octants remain)

    return none

A potential optimization is to handle shadows, reflected rays, etc from the lowest octant rather than starting at the root.  However, implementing such an optimization requires significant state tracking, which also impedes making the ray tracer multi-threaded.

In a future part 4, I'll explore the hurdles of making the tracer multi-threaded rather than its current implementation of one thread.

Review: Measurement Bias (ASPLOS'09)

Given that I read 150 - 200 research papers a year, it seems only reasonable that I point out papers that I find particularly interesting.  One of the first papers that I read in grad school (and still one of the most interesting) is the subject of this post, Producing wrong data without doing anything obviously wrong!

We know of many sources of variance in our measurements, like whether other applications or processing is occurring.  Or second order items like, where is the data laid out on disk (inner versus outer tracks) or what are the specific pages of memory allocated (as it can influence caching)? But these variations are (usually) different from run to run, so by taking many measurements we can see an accurate performance where the events above occur with some frequency.

The paper tests the following comparison: what benefit does -O3 provide over -O2 in gcc?  Beyond the variations above, what items may affect performance of which we aren't aware, particularly those that don't vary over runs.  The danger is that these artifacts can result in this "wrong data" without our knowing it.  Two artifacts are analyzed in the paper: linking order and environment size.  Taking these in order.

The authors found that changing the order that the libraries are linked in the applications showed a performance variation of 15%.  On further analysis, they found that certain performance critical sections of code would have different alignments depending on the linking order.  Sometimes the code would be in one cache line, other times two.  This bias persists in both gcc and ICC (Intel's compiler).

Environment size also has unpredictable effects on application performance.  On the UNIX systems tested, environment variables are loaded onto the stack before the call into the application's main() function.  As the variables increase in size, the alignment of the stack changes and this causes performance effects throughout the code.  Some applications have minimal effects, others will vary by +/- 10%.

While these are but two cautionary tales of how small changes to program state can have significant performance impacts, the main take-away is that these effects will always be present.  But they call us to action in preparing more diverse workloads that can address these biases, like conducting multiple runs address interrupts, context switches, etc.

From C to C#

My recent work has lead me to port several programs that I'd previously developed in C into C#.  In a previous post, I explained some of my preference for C, but work being work (or research)....  After these efforts, I thought I'd expand upon some of my joys and sorrows experienced during this effort.

First, overall the process was surprisingly easy.  Most code required little to no changes.  Often, entire code bodies were copied between projects with a single find / replace: "." in place of "->".

Second, the minor changes were basically those within the object-based model.  Fields of a struct become public (or private).  And global functions need to be assigned to a class.

Third, some types and constructs do not have an easy conversion.  While not difficult, it was nonetheless annoying to have to redo arrays as having run-time defined length.  Or to change types to UInt32.

The final aspect to porting between languages is the run-time / OS / system interfaces that do change.  So while the internals of the magical program box remain relatively constant.  The externals of how it interacts with the system to take in / send out data change.  Fortunately, for my porting tasks, this code was relatively modest.  (One of the more difficult parts of this step is covered in Ray Tracing ... Part 2).

A Pointer on Pointers Part 2

In the second part to the series on pointers, we'll be covering what they point to and how it relates to reality.  Let's consider four pointers: void*, char[], struct*, and (void *)f(int) (i.e., a function pointer).  With each pointer, we'll learn something further about C, assembly and how a processor interacts with memory.

To begin, there is the all purpose void* pointer (and yes, void* means pointer to void, but I'll keep writing void* pointer for emphasis).  A C type that means a pointer to nothing, or anything.  This pointer is important for allocating space and casting (changing the type of) the space.  This second piece is something that only has representation in the programming language, in assembly every pointer has no type information.  So by casting, the programmer tells the compiler that this block of memory is now to be treated differently.  Therefore, void* pointers are used when the type is not known, (e.g., pthread_create(..., void* arg) or CreateThread(..., LPVOID lpParameter, ...)) or to discard existing type information.

A char[] is the next C type that will be discussed here.  Every array in C is a pointer.  Learn this fact.  Internalize it.  They are so identical that you can use them interchangeably, like so:

char* foo = (char*) malloc(1024 * sizeof(char));

foo[0] = '\0'; // 1
*(foo + 0) = '\0'; // 2

Line 1 and 2 are equivalent.  So a pointer to many chars is an array of chars.  And we can access any array offset with the pointer.  Or we can use pointer arithmetic to access specific elements.  Now, next time you see char*, you can think of it as an array of characters.  (In a later post, we'll cover char** and other more complex pointers).

Working with the third type, a struct* pointer.  Structs are merely logical arrangements of data that a programmer specifies.  So accessing this data via a pointer will set up assembly to be at some offset from the base pointer.  If you want to ignore this compiler support, such things are your purview.  And in seeing how you can do this, we'll learn what the compiler is doing and what a struct* pointer is.  We want a struct with two shorts, followed by a long.  And we'll assign 'A', 'B', and 1024 to the three fields respectively.

typedef struct _pop2 {

    short a, b;

    long c;

} POP2, *PPOP2;

// Option 1

PPOP2 structP = (PPOP2) malloc(sizeof(POP2));

structP->a = 'A';

structP->b = 'B';

structP->c = 1024;

// Or option 2

char* no_struct = (char*) malloc(8);

*(short*)(no_struct + 0) = 'A';

*(short*)(no_struct + 2) = 'B';

*(long*)(no_struct + 4) = 1024;

You might be scratching your head, but option 1 and 2 do the same thing.  Option 1 is how a programmer should write the code.  Option 2 is roughly what the computer will actually be executing.  So just remember that structs and struct* pointers are just logical arrangements of the data for your conveince.

Lastly, the function pointer cannot be ignored.  A vital tool in modern architectures is the ability to call functions.  Most calls use built in addresses (established at compiler time), but sometimes where the code wants to go isn't known until runtime.  Function pointers are what enables inheritance in OO development, dynamic linking, and often finds its use in switch statements and other constructs.  (Especially fun to use them with runtime code generation, but that's another post).  And at their core, a programmer is merely telling the computer that execution should continue at some address.

To summarize, memory is just sequences of bytes that are given meaning by the types and usage that exist in the source code and consequently the program itself.  To be different types of pointers is to look at memory through different lenses.

Ray Tracing Performance and Practice Part 2

In this post, we shall explore creating a scene worth rendering.  In my prior work, my ray tracers were creating simple assemblages of spheres and triangles, with some having textures and others mirrored surfaces, etc.  This time, I wanted to have a scene that others might enjoy.  So for my first step, I turned to the Stanford 3D Scanning Repository and selected the angel model, Lucy.

The first problem in rendering is that the model is about 116 million triangles, or over 500MB in size.  Perhaps slightly more detail than is required for all but the largest of images.  Some time was spent searching for a tool that would provide a simplified model, and I settled on MeshLab.  However, the GUI version would crash trying to load the initial model, so I had to create a script of the required transformations and have the command-line application create the reduced model.  This reduced down to a 250k model, and subsequent transformations in the GUI gave a 50k triangle model and oriented appropriately for the ray tracer.

The second problem in rendering is that the model is stored in the ply file format.  I extended my scene parser to handle ply files without really understanding them. While I would like to have a generalized parser, I confined my work to the specific format that MeshLab was generating and did not worry about whether there were triangles or rectangles, normals present, colors specified, etc.  Yet, even this single format took some work.

Initially, the parser took in a text version of the ply file; however, the time to parse 100k lines of text and convert to the appropriate representations was approaching the time to render the scene.  Switching to a binary representation seemed a reasonable step; however, how does one take a stream of bytes and convert to a specific type?  In C, you could do the following:

Vec3f v;  // Struct of three floats

fread(&v, sizeof(float), 3, sceneFile);

But in C#?  I eventually settled on reading each value and converting via the "BitConverter" class.

Support.Assert(4 == pFile.BaseStream.Read(data, 0, 4), 
    "INVALID Ply - Fail to parse vertex");
newV.x = BitConverter.ToSingle(data, 0);

Great!  The statue is now in the tracer.  However, 50k triangles is too much for my naive ray tracer.  So there was performance work to be done.  At the time, I would render a 5k triangle version as a test model, as seen below (pending while in flight).

Ray Tracing Performance and Practice Part 1

As the MICRO conference came to a close, my thoughts were stimulated toward new projects and undertakings.  One task in particular was developing a ray tracer as an additional workload for my research.  The first cause for specifically a ray tracer is that I developed one in C many years ago that used now deprecated libraries.  Secondly, prior to my last paper deadline, another professor suggested ray tracers as having many useful characteristics.  So I've been porting my old code from C to C#.  This series of posts will discuss some design decisions relating to the porting, additional optimizations that have been introduced, and other interesting headaches / pitfalls.

On the first order, porting the implementations was fairly straight forward.  The original code had some level of object-oriented (OO) design with triangles and spheres both encapsulated within "ray objects" (see Object Oriented C Part1).  But much of the implementation was a mangled mess.  For example, both colors and positions were represented by float triplets.  And so, some glue logic was required to convert from the ARGB color mode into the float space used by the tracer.  But being object-oriented, I could setup type conversions and operator overloads that significantly reduced the inelegance of the original implementation.

Now with a reasonable working port of the original code, the question arose: how to make it perform well?  The original used all sorts of tricks some useful like bounding spheres around the triangles and some not, like preallocating the intermediate space.  As always, there are a variety of levels of abstraction to target for performance work.  My original implementation only focused on micro optimizations like avoiding memory allocations, etc.  (And performance profiles showed that the largest single contributor was sqrt, but I didn't have a "fix" for that.)  However, especially within a higher-level language, many of these choices are denied and so my improvements have taken first to the algorithmic level.

Two (or more) posts will yet follow.  The first on finding and handling a sufficiently interesting scene to render.  And the second will be focused on reducing the computations required to render this scene.

Conference Time: MICRO-43 Day 2

I went to several talks yesterday, but my main purpose was achieved by meeting and discussing my research with the other attendees.  Most conversations are positive and constructive; however, one person remained thoroughly convinced that my research is without purpose.  Nonetheless, these opinions provide me with further guidance for how to present my work to others and provide better motivation for my work.