[Parallel Computing] Sorting

I adopted the odd even sort for sorting on GPU. I use NVIDIA GeForece 9400M, which has the spec (only list related):
CUDA capability 1.1:
1. Max number of threads per block: 512
2. Max blocks in x direction of a grid: 512
3. Shared memory size: 16K
4. Global memory size: 256M

For my application:
Each item in the list: 16 bytes
Usually the size of the list is larger than 1024.

In my implementation, a thread is assigned with two elements in the list. A block containing maximum number of threads (512) can manage 1024 items. In my implementation, the whole list doesn't fit in one block, and inside a block, the elements don't fit in the shared memory. Therefore, I had to use multiple blocks (usually 30~60 blocks) to accomodate the list. Unfortunately, CUDA only provides with us thread synchronization within a block. For interblock synchronization, I have no choice to relaunch the kernel multiple times.


Result:
Sorting 438270 items
CPU version: 86s (This version is not optimized, just want to verify the correctness of GPU version)
GPU version: 504ms

[Parallel Computing] Indexing tricks

When making device kernels (shaders,) how to assign threads to some tasks is very important.

Since the GPU has really little support of recursion, how to turn your recursive program into a non-recursive one becomes very important as well.

I saw this approach when I was working on GPU sorting.

The original Odd Even Merge Sort is described here

I'm not gonna describe the iterative version in detail but mention some tricks to accustom your code to the GPU kernel.

1. When your code has the thread assignment with a circular pattern:

For example:

8 Threads:

Thread Id 0 1 2 3 4 5 6 7

Activate/no n n y y n n y y

Solution:

Here we have a circular pattern with a period of 4.

Of course we can use something like if(Idx.x==xxx), but if the case is making an iterative execution, there will be too many cases to be considered.

A better way is to use (Idx & (period-1)) and set a threshold.

In our example, we can use (Idx&3) and set a threshold equal to 2.

So the values become:

Thread Id 0 1 2 3 4 5 6 7

Activate/no n n y y n n y y

Value 0 1 2 3 0 1 2 3

Thresholded n n y y n n y y

So it's exactly what we want for our program.

[Feature]Photon Mapping

I use photon mapping to do the indirect illumination. Indeed, it's way faster than path tracing.Following image is rendered with global photon map and caustic photon map.

[Cornell Box]

Parameters:1000 samples direct lighting
10000 photons
1000 photons for irradiance estimation

Parameters:1000 samples direct lighting
10000 photons
1000 photons for irradiance estimation

Parameters:
2000 samples direct lighting
1500x1500 HDR image as background
10000 photons
1000 photons for irradiance estimation

[Path Tracing]Environment Mapping

After adding environment mapping, everything looks good ^^.

Path tracing isn't a good method to do caustic, so it's noisy for the caustic even though I use comparably more samples.

Parameters:

700 samples path tracing

1500x1500 HDR image as background

Image based Lighting

Parameters:

700 samples path tracing

50 samples image based lighting

1500x1500 HDR image as background

Image based Lighting

Parameters:

1500 samples path tracing

50 samples image based lighting

1500x1500 HDR image as background

[Progress]Path Tracing

After I review the whole concept about path tracing, now I'm more aware of it.

1. Original path tracing doesn't separate direct illumination part from indirect illumination part.

2. Direct illumination part is for smoothing the result. (Because if the sampled ray doesn't hit the luminaire, it'll be totally black and otherwise it'll be really bright.)

Here is the result. Path tracing with a glass ball.

Parameters:

1 shadow ray

1 hemisphere sample

15 times max bounce (if none of bounces hits the light)

200 samples per pixel

[Progress]BVH with SSE

Finally I finish my BVH with SSE implementation, but the outcome for a simple model (66454 triangles) doesn't seem like helpful.

Here is the outcome:

Without SSE

==BVH Info==

1-element leaf: 1838

2-element leaf: 18209

3-element leaf: 2876

4-element leaf: 2811

Total: 27047 bounding boxes

Building time: 2.453573 sec

==Rendering Info==

Rendering time: 1.565233 sec

Ray-Box intersection: 19658128

Ray-Triangle intersection: 1393575

With SSE

==BVH Info==

1-element leaf: 0

2-element leaf: 1

3-element leaf: 0

4-element leaf: 16613

Total: 16614 bounding boxes

Building time: 2.569810 sec

==Rendering Info==

Rendering time: 1.429016 sec

Ray-Box intersection: 19821888

Ray-Triangle intersection: 673405

Two weeks for 0.1 sec improvement. Cool!!

BVH(dark blue lines) for Sponza model

Rendered Image

[Note]VTK InputConnection

My final solution is to use vtkFixedPointVolumeMapper to map the 4-channel data input into the 4-channel renderable volume.

//==following is perhaps wrong guessing==

According to my experiment, the latest version (>5.0) vtk supports 3 channel color transfer function in the class "vtkVolumeProperty". Question is that it seems like no matter how many components are input (I input a 4-component data, and I checked it's still 4-component data after read by the reader), the mapper(vtkVolumeMapper) will merge the 4 component as one. I checked the source code of vtkVolumeMapper.cxx. I think it's very likely it's done at

vtkImageData *Input = vtkImageData::SafeDownCast(genericInput);//it might lose the four channels here when it down casts to vtkImageData.

and the following

this->setInputConnection(0, input);//then it pass the merged data to the 0 port (first port).

It might be the reason that the 3-channeled color transfer function doesn't work.