## Source Code and Binaries

By tarjan, April 8, 2010 7:43 pm

If you are interested in the source code or binaries you can download both here.
The project is in an early stage, so forgive me any ugly code…

## Surface Area Heuristic

By tarjan, April 5, 2010 10:53 pm

Long time no post. Now i finally managed to implement a BIH Tree Builder using the surface area heuristic as described here. The basic idea is simple but the implementation has been tricky. Maybe i will post the gritty details here sometime.

I tested three different models with shadow tracing enabled at the resolution of 768×480.

The results are as follows:

 Scene Cessna Elephant Temple Picture SAH 55 fps 28 fps 4.75 fps Median of 3 18.5 fps 13.8 fps 0.39 fps Factor x 2.97 x 2.03 x 12.18

Since the two first scenes dont have many primary ray hits, the third scene gives a good impression of the achieved performance boost. As you can see there are still some numerical issues that look like the division by zero problem. Therefore this problem is not solved. I implemented specular highlights to the surface shader.

Next task will be to increase the building time. The building takes several seconds for model with 300000 triangles.

## Path Tracing

By tarjan, January 31, 2010 6:12 pm

Though performance is still low, i wanted to try out path tracing. To do so you need some kind of sampling algorithm, that samples the hemisphere for a surface point. These samples are used as directions for secondary rays which gather the incident indirect light for every surface point that is hit by a primary ray. In a first shot i took the hemicube rejection method. It works as follows:

1. choose a random point in the hemicube
2. repeat first step until point is in hemisphere

If you know how to produce random directions you still have to transform them in the local coordinate system of the surface. To do so i created a rotation matrix which rotates around the cross product of the surface normal and the up vector (random points are created in the upper hemicube) by the angle between the normal vector and the up vector. By multiplication with the matrix, every random direction gets transformed as wished.

Here are the results of path tracing with 16 random secondary rays per primary ray. The first image shows the direct light contribution, the second the indirect light contribution and the third both together:

## OpenMP

By tarjan, January 20, 2010 4:38 pm

To improve performance i decided to do parallelism and that by using OpenMP since it is very straightforward to apply. To utilize cache reuse i did not apply the parallel call on every single pixel. Instead i subdivided the screen into regular blocks of a power of two and assigned one separate thread to each block. For simplicity reasons i changed the screen size to a power of two as well.

Initially i used exactly four threads, so that in theory each one can be executed on a distinct core. However this did not give the optimal result. Instead 16 and 32 threads gave significantly better results. The following table plots the frame rate for different thread counts and block sizes:

 Block size 512 256 128 64 32 16 8 4 # Thread 1 0,79 0,79 0,79 0,79 0,79 2 1,44 1,44 1,45 1,45 4 1,42 1,68 1,68 1,68 1,72 1,72 1,7 8 1,65 2,4 2,37 2,5 2,5 2,4 16 1,64 2,3 2,7 2,85 2,8 2,75 32 2,35 2,83 2,9 2,82 2,8

As you can see the more threads the more fps. What you cant see in the table is, that using more threads leads to a very unstable fps rate. At this time i have no explanation for this behaviour, i can only assume that one thread per core does not fully load the core. I think the result will change when the raytracing core will be optimized using simd/packet tracing/frustum tracing.

Nevertheless i was able to increase the frame rate from 0,79 to 2,9 (factor 3,67).

## Modeling

By tarjan, January 16, 2010 4:44 am

I added this page which shows some 3d models i have created in the past. Feel free to use them:

## Perlin Noise

By tarjan, January 2, 2010 3:42 pm

How to use perlin noise to generate procedural terrain is well described here. To test the implementation, i decided to implement in c++ first. To output and view images the CImg library is used. Once compiled it takes two lines of code to create an image and view or output it unlike other libs like libpng, which requires a lot of boilerplate cooking. So i was able to create the first nxn height map:

Well, this is a rectangular grid which still has to be mapped on a sphere. To minimize distortions and singularities i decided to do a mapping as follows:

The six sides of a cube are mapped onto the sphere. In that way distortions occur on the edges and there are no singularities. Furthermore each side can be organized in a regular grid, which makes it more easy to apply erosion.

To compensate the distortions you do the following. Instead of using 2D perlin noise you can use 3D noise and project the pixel in the texture onto the sphere with radius one. This coordinates are used for a 3D perlin noise lookup. Here is the result:

## OpenCL

By tarjan, December 28, 2009 1:12 pm

Well, OpenCL (via ATI Stream SDK) may not be difficult but it requires a huge amount of code to do even the simplest tasks like e.g. vector addition. The most of this is handling of the cpu and gpu interaction and creation of memory buffers. The GPU program itself is supposed to be very short for simple tasks and is stored in a string or in a separate file.

It turned out that there are c++ bindings,which wrapps many of the c style API calls and dramatically reduces code size. There are python bindings (PyOpenCL). The examples suggest, that this is the simplest and quickest way to get started. Sadly, i wasn’t able to get it to run, so i will stick with c++. May be i give it a try later.

This Reference Card is very useful if you want to quickly find an API function.

These Webcasts at macresearch by David W. Gohara are a must see when you want to understand the concepts of OpenCL.

## Starting with Procedural Planetal Surface Generator

By tarjan, December 28, 2009 12:34 pm

A dream of mine is to create a generator that is able to calculate the surface of a whole planet (earth size), which can be used as a texture for realtime rendering. It should be capable to create countless different planets for example for games where you can travel in space from one planet to the other. This should be achieved by generating a height map and different types of terrain types like Forest, Desert, Sea, Mountain, Snow, Plains, River (if resolution is sufficient) leaving the believable impression of an extra solar planet.

At first it may be sufficient to limit the resolution to a fixed value of lets say one km. This is still much data. If you assume a surface of approx 500000000 kmĀ² and you manage to store the data for each position in one byte you need almost 500MByte memory. In a later version it may be possible to increase the resolution adaptively dependent on the viewing position. I may even be possible, to do this in real time while rendering the planet. But in a first shot this should be done offline. The height map is generated with perlin noise or a more realistic simulation of plate tectonics and vulcanism. Secondary thermal and hydraulic erosion should make the result more believable and add river networks. At least the second task is computational expensive therefore it is wise to be done on the GPU using OpenCL. Modern GPUs like my Radeon 5870 have a computing power of over 2 Teraflop. This is more than any of the current CPUs are capable of, assumed that the problem can be well devided to data parallel tasks.

This idea is not new. Have a look here:

Real-Time Editing, Synthesis, and Rendering of Infinite Landscapes on GPUs

Fast Hydraulic Erosion Simulation and Visualization on GPU

Water Erosion Simulator

The only point that my generator may be different is the large scale. If it turns out to be out of reach, than this still serves as a exercise for OpenCL.

## Tree Optimization

By tarjan, December 19, 2009 10:07 pm

To improve performance i moved to the original node layout as proposed here.

This is the layout i used so far:

```struct BIHNode
{
bool isLeaf;
union {
struct Leaf
{
unsigned int item;
unsigned int count;
} leaf;
struct Inner
{
unsigned char axis;
BIHNode* childs[2];
float boundaries[2];
} inner;
};
};```

This is the original one:

```struct BIHNode2
{
unsigned int index; // 2 bits are used to indicate a leaf node or inner node plus axis
union {
struct Leaf
{
unsigned int count;
} leaf;
struct Inner
{
float boundaries[2];
} inner;
} data;
};```

The main difference is, that the nodes are organized in an array instead dynamically on the heap. Pointers to the children become one index, which indicates the position to the first child. The second child is always stored next to the first one.
The key benefits are as follows:

• more compact memory footprint (12 bytes instead of 26(for x64 systems))
• both children are next to each other, so they can be read to the cache at once

The performance win is small but noticeable.

Furthermore the quality of the tree can be optimized. As a splitting plane i used the midpoint of a randomly chosen triangle. To improve this, i took three randomly chosen ones and then calculated the median of the three (median of three as proposed by Robert Sedgewick). This optimization gave a small performance improvement.

Framerates are still poor. A short look at the tree has revealed, that the depth is 196 while storing 17758 triangles. The tree has 1603 nodes and the max triangle count for the leaves is 10. The depth has to be decreased significantly.