CG-Projects

Project Report - Ray Tracing

Taiki Yoshino, David Choi
University of California San Diego, Computer Scinece and Engineering
CSE167 Computer Graphics (2024 Winter)
Used Tools: C++, OpenGL

Ray Tracing

We implemented ray tracing algorithm (Whitted 1980) from scratch in C++. Thoese rendering includes the transformation of spheres and triangles, a single point light source, a maximum of five reflections, and material properties.

Additionally, we implemented a Bounding Volume Hierarchy to speed up the rendering process. This acceleration structure halved the rendering time for scene 2 from 20 minutes to 10 minutes, and significantly reduced the rendering time for scene 4 (+50K vertices) from roughly 14 hours to just 2.5 hour. For those implementing bounding volume heirarchy in the future its worth noting that if only 1/4 of your image is rendering properly chances are you just need to check maxT and minT for you bounding volume intersection.

Rendered Images

Scene 1

Scene 2

Scene 3

Scene 4

Ray Tracing Method

Ray Tracing Overview (NVIDIA’19):

1. Cast a ray into every pixel.
2. Determine if it intersects any object, and find the nearest one.
3. Find the color of intesected point based on the materials and light position.
4. Recursively generate a new ray to the reflection direction.
5. Determine the final color of the pixel.

Code Snippet:

RayTrace(Camera cam, Scene scene, int width, int height)
{
    Image image = new Image (width, height);
    for(int h = 0; h < height; h++){
        for(int w = 0; w < width; w++){
            Ray ray = RayThruPixel (cam, h, w);
            Intersection hit = Intersect (ray, scene);
            image[h][w] = FindColor (hit);
        }
    }
    return image;
}

Acceleration Structure

Bounding Volume Hierarchy: (BVH)

Testing every primitive for ray intersection is extremely slow as the number of objects increases. An acceleration structure efficiently selects only some potential primitives for intersection with the ray. BVH first builds a hierarchy of bounding volumes as a binary tree and uses it to accelerate ray intersection. BVH allows the ray to find the intersection in at most O(log(n)).

Reference

1. https://developer.nvidia.com/discover/ray-tracing
2. https://en.wikipedia.org/wiki/Bounding_volume_hierarchy
3. https://tavianator.com/2014/ellipsoid_bounding_boxes.html