CUDA/OpenCL Programming

Ray-tracing vs Rasterization

Rasterization: The term refers to the popular rendering algorithm for displaying three-dimensional shapes on a computer. Rasterization is currently the most popular technique for producing real-time 3D computer graphics. Real-time applications need to respond immediately to user input, and generally need to produce frame rates of at least 24 frames per second to achieve smooth animation. This is used in Games, CAD, medical imaging, etc. Any application that needs interactive rendering of complex 3D scenes.

Ray-tracing: Ray-tracing is a technique for generating an image by tracing the path of light through pixels in an image plane and simulating the effects of its encounters with virtual objects. It is meant to produce much better quality images than rasterization but it’s also much slower because it’s much more CPU consuming.

Appetite for high quality visualization

Why do we need real-time and interactive visualization?

I don’t know if you know about that story but there was an experiment done by, I think, the American intelligence. They were asked to write an application that could quickly identify buildings on satellite pictures. So they started working on complex algorithms involving machine learning, neural networks, image processing and anything that can help identifying the shape of a building on a 2D image. But then they realized that, with brain analysis and electrodes, using humans was a much simpler and cheaper way to achieve what they wanted. So they hired people for a few dollars an hours, and as they were showing them the photos, some parts of their brain were activated when they could identify a building. And this was done in a matter of milliseconds. The human brain is just good at that and has a very optimized recognition algorithm. All this to say that our unconscious is very good at picking things up and can understand more when facing realistic images.

Also, our brain understands dynamic scenes better than static ones, and because the quality of what we see directly influences our comprehension of complex events, it has to be as high as possible.

Where is the challenge?

With Rasterization, every object is independent from each other. It’s very suitable for embarrassingly parallel algorithms and has a linear and predictable processing time, depending on the number of objects to process.

With Ray-tracing, every object potentially interacts with all of the others. So what you get is an exponential processing time, as the number of objects increases.

Solving this problem requires a specific management of the objects to be rendered, and this is what I am going to show you now.

Six degrees of separation

One day, a friend told me about the theory of “Six degrees of separation”. Do you know about this theory?

Six degrees of separation is the theory that everyone and everything is six or fewer steps away, by way of introduction, from any other person in the world, so that a chain of "a friend of a friend" statements can be made to connect any two people in a maximum of six steps

I did not take this sentence very seriously at the time but for some reason, it got stuck in my head. And a few years later, as I was encountering performance problems on one of my project, that theory came back to me as an evidence.

If we are 7 billion people on this planet, and if we never are more than 6 steps away from each other, why would it be different in the memory of my computer? If I have 7 billion objects to process in my rendering algorithm, it should not take more than 6 cycles to access the object that I need to work on…

Ok, that’s the theory. How do we do that in practice? And this is of course depending on the parameters that you can pass to this clever equation, as shown on the slide.

Bounding boxes

In order to apply this algorithm, the first thing to do is to group your objects, so that the group can be considered rather than the objects that it contains. In this example, we talk about “Bounding boxes”.

A bounding box is basically a 3D space that contains a number of objects.

Ray-tracing is all about intersections. In the previous slides, I told you that when you launch a ray, you need to find the intersection with the closest object. If you have 10’000 objects, then you need to compute the intersection between the ray and the object itself, for all of the objects, and then keep the closest intersection. By grouping objects in boxes, you can start with computing intersection between the ray and the boxes, and if there is an intersection with a box, only then you will look into that box and compute the intersections with the objects it contains.

Fine tuning

A box intersection takes 17 cycles, using the robust and efficient algorithm provided by the University of Utah ( http://people.csail.mit.edu/amy/papers/box-jgt.pdf )

A object intersection is a lot more expensive and can cost several hundred cycles. So then it’s a trade-off to identify between the number of boxes, and the number of objects.

OO vs Algorithm Specific Structure

Object Oriented Design is good, because it uses concepts that we, humans, are comfortable with. A car object is a set of wheels, tyres, seats, and it as a color, etc. You can define inheritance that prevents from replicating the code.

With OO, you can write readable and maintainable code, which is essential. But OO is not optimal for performance because it fragments memory and forces one to consider an object systematically as a whole.

If you take the example of a person with three attributes: a first name, a second name, and an age. Now imagine that you have a collection of persons and you want to compute the average age of that population. With OO, you will not only take the age attribute down to the processor but you will also take the first and the second name down to the CPU, even if you do not need them in your algorithm. Only because OO forces you do so, by design.

On the other hand, if you have an algorithm specific data structure, you will separate you “person” object in two parts. One for the name and family name, the other one for the age. And only the data structure containing the age will be taken down to the processor. This will dramatically increase the performance.

In the case of the ray-tracer, we do exactly the same. A primitive such as a sphere for example, is composed of a number of attributes such as the center, the radius, the material properties, texture coordinates, etc. But when processing intersection on the first pass of the algorithm, only the center and the radius are needed, and this can be represented in the form of a float4.

For the boxes, only the two corners of the box are needed, meaning two float3.

Order in RAM

Now that we have defined our data structures, this needs to be optimized them for computers.

In our case, we have boxes and we need to compute the ray-box intersection for each of them. So let’s make sure that boxes are aligned in memory.

As we go through our boxes, if an intersection is found, we need to get deeper into the box to make sure that there is an intersection with a primitive. Meaning that ordering primitives also is essential. This is what is being done at a second level. And as explained in the previous slide, only me minimal information is taken down to the processor.

Last week, I got my first Android phone: A Wiko Cink King! It's not a Samsung, it's not an Apple, but it's definitely worth the 200 EUR it cost me. And since I now have an Android device, I can develop my own apps, and my first implementation had to be related to ray-tracing in some way. Let's be honest, interactive ray-tracing on a 200 EUR device... the dual-core 1GHz CPU simply cannot handle it. But there is another solution: Why not use the GTX 480 sitting in my desktop box remotely? And since I already have an HTTP GPU server in stock, writing the mobile app making HTTP REST calls did not take more that a few hours, using the really cool Android Development Kit.

Sample code for the GPU HTTP server: https://github.com/cudaopencl/GPUHTTPServer
Android SDK: http://developer.android.com/sdk/index.html