Raytracing at last...

(Red Plane: 10x10 Splats)

(Red Plane: 1600x1600 Splats)

My CPU ray tracer finally works. Um... well, it only traces primary rays right now, and it is single threaded... and there is no filtering... ok ok, its not that big a deal, but I will blog about it anyway :P

The ray tracer is for point based scenes. The only primitive we deal with are splats (points with radii, colour and normal vectors). The acceleration structure is an octree, but I feel the traversal algorithms we use right now can be extended to kd-trees as well. This is my first working ray tracer. It will serve as a precursor to a faster, cooler ray tracer implemented entirely on the GPU. It also provides me with a test bed to debug ideas before implementing them in CUDA.

The octree traversal algorithm is one I came up with last year while doing a quad-tree traversal assignment. It involves storing pointers to nearest common ancestors, at each wall in the tree. Some modifications were required to implement a sparse octree, where empty nodes are not stored at all, but in all, it was not too messy to implement this.

The first thing I noticed about the implementation was that it is still a bit buggy. In the rendering with 1600x1600 points, there seem to be small holes in the plane, where rays are escaping out into the background. It turns out to be a problem caused due to the discretization of space that the octree produces. Some splats have their center in one node, but their radius causes them to 'spill over' into nearby nodes. This is not tracked by the current octree construction algorithm, due to which some splats are missed.

The next thing, which is the cool part is that the code truly seems to run in log(objects) time. The run time for various scene sizes (512x512 render window, no super sampling):

Points	Render Time	Octree Creation Time	Memory	Naive Render Time
10x10	0.39	---	5	0.42
100x100	0.52	0.02	6	0.58
200x200	0.54	0.04	9	0.6
400x400	0.59	0.18	21	0.63
800x800	0.65	0.82	71	0.7
1600x1600	0.7	3.5	271	0.76
5000x5000	0.85	37	1700	??

(Time in seconds, memory in mega bytes)

The timings in the last column refer to the naive algorithm of traversing the tree from the root each time, without using the least common ancestor idea. It turns out to be a very small benefit. Maybe further optimizations are in order...

Of course, there is the memory issue: It takes around 270 MegaBytes for a scene with 2.56 million splats in it. Octree generation also seems to take more time than the actual raytrace, for such large scenes. (We will not go into the details of how much swapping I experienced with the 25 million points scene. I am never running that again)

What remains now is to add the usual raytracing frills like secondary rays, shading, supersampling etc...