CPU Path Tracer Project

In October 2020, as part of a project at HKA (Hochschule Karlsruhe), I developed a CPU Path Tracer, a fascinating journey into the world of computer graphics. Path tracing is a rendering algorithm that simulates the way light interacts with surfaces to create realistic images. By simulating the physics of light, it produces highly accurate lighting, shadows, reflections, and refractions, although at the cost of significant computational resources. My path tracer was built to run solely on the CPU, making it a challenge to optimize the rendering speed while maintaining visual fidelity.

Key Features

The CPU Path Tracer I developed includes several advanced features that enhance its performance and the quality of the rendered images:

• Multi-threaded Rendering
• Anti-aliasing
• K-d Tree with Surface Area Heuristic (SAH)

How Path Tracing Works

Path tracing works by sending rays from the camera into the scene. These rays bounce around as they interact with objects—reflecting, refracting, or being absorbed. Each time a ray hits an object, a shading model determines the color of that interaction, and over many samples, these rays build up an accurate picture of how light behaves in the scene.

The key to path tracing is Monte Carlo integration. For each pixel, multiple rays are cast, and their results are averaged to compute the final color. The more rays (or "samples") we trace, the smoother and more realistic the final image becomes, but this also increases the computational load.

Multi-threaded Rendering

Rendering a scene using path tracing is computationally expensive. To speed up the process, I implemented multi-threaded rendering. By utilizing all available CPU cores, the rendering workload is distributed across multiple threads. This parallelism helps reduce render times, especially for high-resolution images with many samples per pixel. The implementation uses C++’s std::thread library for parallel execution. Because the image is partitioned into separate tiles, the threats do not access the same memory areas, so no data synchronization was required, making path tracing highly performant in multi-threaded environments.

std::vector<std::thread> threads;
for (int t = 0; t < num_threads; ++t) {
    threads.push_back(std::thread([&] {
        for (int y = t; y < height; y += num_threads) {
            for (int x = 0; x &lt; width; ++x) {
                // Compute color for each pixel
                Color color = traceRay(camera.generateRay(x, y), scene, max_depth);
                accumulateColor(x, y, color);
            }
        }
    }));
}

for (std::thread &t : threads) {
    t.join();
}

Multi-threading efficiently divides the image into chunks that are processed concurrently, resulting in faster rendering times.

Anti-aliasing

To achieve smooth and realistic images, I implemented anti-aliasing. Without anti-aliasing, sharp edges in the image can appear jagged due to the discrete nature of pixels. The method I used is called multisample anti-aliasing (MSAA), where multiple rays are shot per pixel, each with a slightly offset direction. The average of all these samples is used to compute the final color of the pixel. This technique reduces the jaggedness, producing smoother edges and a more visually appealing image.

// Anti-aliasing by shooting multiple samples per pixel
for (int s = 0; s < samples_per_pixel; ++s) {
    float u = (x + random_float()) / image_width;
    float v = (y + random_float()) / image_height;
    Ray ray = camera.getRay(u, v);
    color += traceRay(ray, scene);
}
color /= float(samples_per_pixel);

K-d Tree with Surface Area Heuristic (SAH)

One of the most challenging aspects of path tracing is optimizing the ray-scene intersection tests, which determine which object a ray interacts with. To improve performance, I implemented a k-d tree, a spatial data structure that organizes the scene's geometry in a way that reduces the number of ray-triangle intersection tests.

The k-d tree recursively partitions the scene along different axes (x, y, or z), allowing the algorithm to quickly discard large portions of the scene that a ray won't intersect. I also used the Surface Area Heuristic (SAH) to guide how the k-d tree is built. The SAH optimizes the splitting of nodes based on the probability of a ray hitting an object in a given partition, which improves traversal efficiency and minimizes the number of intersection tests.

SAH works by calculating the cost of a ray intersecting each child tree. The cost of a given splitting plane can be calculated by the number of triangles on each side times the probability that a ray will intersect that subtree. Constants (TRAVERSIAL_COST and INTERSECTION_COST) are introduced to account for traversing the tree structure and calculating the intersection of each triangle.

float costHeuristic(float probLeft, float probRight, int trisCountLeft, int trisCountRight) {
    return (TRAVERSIAL_COST + INTERSECTION_COST *
           ((probLeft * trisCountLeft) + (probRight * trisCountRight)));
}

This cost function can be used to calculate the cost of the specific split plane and take into account the overlapping triangles. All possible split planes are tested until the one with the lowest cost (aka the optimal plane) is found.

BoundingBox lBox;
BoundingBox rBox;
box.split(lBox, rBox, plane);

const float probLeft = lBox.getSurfaceArea() / box.getSurfaceArea();
const float probRight = rBox.getSurfaceArea() / box.getSurfaceArea();

int64_t overlapLeft = trisCountLeft + trisCountOverlap;
int64_t overlapRight = trisCountRight + trisCountOverlap;

const float costLeft = costHeuristic(probLeft, probRight, countLeft, trisCountRight);
const float costRight = costHeuristic(probLeft, probRight, overlapLeft, overlapRight);

This technique significantly improves the rendering speed, especially for complex scenes with many objects.

Image 1: Path Traced Cornell Box

This is a rendering of the classic Cornell Box, a scene used frequently to test lighting algorithms. The path tracer successfully captured global illumination, soft shadows, color bleeding, caustics, and light diffusion. Notice how light reflects off the orange and blue walls, subtly tinting the nearby surfaces, while the shadows retain a realistic softness.

Image 2: Path Traced Scene with Depth of Field

One of the more advanced features I implemented was depth of field (DOF). This effect simulates the behavior of a real camera lens, where objects outside the focal plane appear blurred. In the image above, you can see the sharpness in the focused area (first and second cube), while other regions become softly blurred, adding to the realism of the scene. Achieving DOF in path tracing requires shooting rays in slightly different directions from a simulated aperture, increasing the complexity of each frame but yielding photorealistic results.

Image 3: Cornell Box in Blender

This is the same Cornell Box scene shown in Blender, before being processed by the path tracer. Blender was used to model, texture and position the objects, but all the lighting and shading in the final images are entirely the result of the custom CPU path tracer. The scene here is rendered using Blender's real-time viewport, which is a far cry from the physically accurate simulation that path tracing offers.

Technical Details

The project was written in C++ to take advantage of its performance and control over memory. With multi-threaded rendering, anti-aliasing, and a k-d tree optimized with SAH, the path tracer achieves a balance of image quality and performance. Despite the limitations of running entirely on the CPU, these optimizations allowed for photorealistic rendering in a reasonable amount of time.

for (int i = 0; i < num_samples; ++i) {
    Ray ray = camera.generateRay(pixelX, pixelY);
    Color color = traceRay(ray, scene, max_depth);
    accumulateColor(pixelX, pixelY, color);
}

Conclusion

The CPU Path Tracer project was a rewarding and challenging experience that taught me a lot about computer graphics, physics simulation, and performance optimization. Despite the heavy computational requirements of path tracing, the results speak for themselves in terms of visual quality. The project also provided a deeper understanding of rendering pipelines and how real-world light interactions can be simulated on a computer. I look forward to exploring GPU-based path tracing in the future to further enhance performance.