Scotty 3D: A 3D Graphics Software Package

Students' work

This is a course project for CMU 15-462/662: Computer Graphics.

The project has four major modules, each of which took me roughly three weeks to complete. The sections below show what each module produced once it was working, and the Learnings at the end are what I took away from the whole thing.

At a glance
Course: CMU 15-462/662 Computer Graphics, Spring 2023
Stack: C++ (Scotty3D, CMU's teaching renderer/modeler)
Scope: software rasterizer, halfedge mesh editor, path tracer, animation system
My role: solo project
Code: not public (course integrity policy)

Module 1: Rasterizer

Modern GPUs implement an abstraction called the rasterization pipeline. It breaks the process of converting 3D triangles into 2D pixels into several highly parallel stages, which is what allows for so many efficient hardware implementations. In this module I implemented parts of a simplified version of that pipeline in software, enough for Scotty3D to produce preview renders without a GPU.

Different graphics APIs present this pipeline in different ways, but the core steps stay the same: a GPU draws things by running code (in parallel) on a list of vertices to produce homogeneous screen positions (+ extra varying data), building triangles from that list of vertices, clipping the triangles to remove parts not visible on the screen, performing a division to compute screen positions, computing a list of "fragments" covered by those triangles, running code on each fragment, and composing the results into a framebuffer.

Fig-1 Sample images generated by renderer

Module 2: Mesh Editor

In this module, I wrote code to support the interactive editing of meshes in Scotty3D. Scotty3D stores and manipulates meshes using a halfedge mesh structure -- a local connectivity description which allows for fast local topology changes and has clear storage locations for data associated with vertices, edges, faces, and face-corners (/edge-sides).

Halfedges store the bulk of the connectivity information: a reference to the halfedge on the other side of their edge in Halfedge::twin, a reference to the halfedge that follows them in their current face in Halfedge::next, a reference to the vertex they leave in Halfedge::vertex, a reference to the edge they border in Halfedge::edge, and a reference to the face they circulate in Halfedge::face:

Fig-2 Halfedge Data Structure Illustration

I implemented a long list of mesh-editing operations in this module. Here are four of them, two local and two global.

Local::erase_vertex

Local::erase_edge

Global::loop_subdivide

Global::simplify

Module 3: Ray Tracer

The ray tracer is made of the sub-routines shown in Fig-3; each gets a short section below.

Fig-3 Ray Tracer Roadmap

Camera Rays

"Camera rays" emanate from the camera and measure the amount of scene radiance that reaches a point on the camera's sensor plane. (Given a point on the virtual sensor plane, there is a corresponding camera ray that is traced into the scene.) Generating these rays is the first step of the ray tracer.

Fig-4 Camera Rays Illustration

Visualized camera rays:

Fig-5 Camera Rays Visualization

Intersections

The first intersection routine is the ray-triangle hit test for meshes:

Fig-6 Triangle Intersections Illustration

The second is the ray-sphere hit test:

Fig-7 Sphere Intersections Illustration

Results:

Fig-8 Normals Visualization 1

Fig-9 Normals Visualization 2

Path Tracing

Up to this point the renderer only computed visibility with ray tracing. Path tracing simulates the complicated paths light takes through the scene, bouncing off many surfaces before it reaches the camera. This multi-bounce light is what people mean by global illumination, and it is critical for realistic images, especially when specular surfaces are present.

Implementation steps:

Lambertian
Sample indirect lighting
Sample direct lighting

Reference images below show the time-quality tradeoff on an Intel Core i7-8086K (max ray depth 8). The second from the last image was rendered with a sample rate of 1024 camera rays per pixel and a max ray depth of 8. This will produce a relatively high quality result, but will take quite some time to render.

Fig-10 Reference Path Tracer Output

Fig-11 Samples: 32, Max Ray Depth: 8

Fig-12 Samples: 1024, Max Ray Depth: 8

Materials

With multi-bounce paths in place, the next step was more kinds of materials. This part adds two specular materials: mirrors and glass.

Implementation steps:

Materials::Mirror
Materials::Refract
Materials::Glass

Fig-13 Reference rendering of mirror and glass materials

Direct Lighting

This sub-routine changes the sampling strategy by splitting samples between BSDF scatters and the surface of area lights, a procedure commonly known as next event estimation.

Why is sampling lights useful? Up to here the renderer only importance-samples the BSDF term of the rendering equation (in which we have included the cosine term). However, each sample we take will also be multiplied by incoming radiance. If we could sample the full product, the Monte Carlo estimator would have far lower variance. Sampling lights is one way to importance sample incoming radiance, but there are some caveats.

Fig-14 Reference direct-lighting rendering

My results:

Fig-15 Samples: 32, Area Light: Off

Fig-16 Samples: 32, Area Light: On

Environment Lighting

The last task of the ray tracer module was a new type of light source: an infinite environment light. An environment light is a light that supplies incident radiance from all directions on the sphere. Rather than using a predefined collection of explicit lights, an environment light is a capture of the actual incoming light from some real-world scene; rendering using environment lighting can be quite striking.

My result:

Fig-17 Environment lighting, 32 importance samples

Module 4: Animation System

This module completes Scotty3D's animation system, including skeletal animation, linear-blend skinning, and a particle simulation.

A quick piece of "art" I made once the module was working:

Spline Interpolation

Data points in time can be interpolated by constructing an approximating piecewise polynomial or spline. This part implements a particular kind of spline, the Catmull-Rom spline. A Catmull-Rom spline is a piecewise cubic spline defined purely in terms of the points it interpolates. It is a popular choice in animation systems, because the animator does not need to define additional data like tangents, etc.

Result:

Skeleton Kinematics

A Skeleton is what drives the animation. Think of it as the set of bones in our own bodies plus the joints that connect them. For convenience, Scotty3D merges bones and joints into a single Bone class which holds the orientation of the bone relative to its parent as Euler angles (Bone::pose), and an extent that specifies where its child bones start. Each Skinned_Mesh has an associated Skeleton class which holds a rooted tree of Boness, where each Bone can have an arbitrary number of children.

Forward Kinematics

Result:

Inverse Kinematics

Result:

Linear Blend Skinning

With a skeleton in place, the mesh has to be linked to it so that it follows the skeleton's movement. I implemented linear blend skinning in Skeleton::skin, using per-vertex weights computed by Skeleton::assign_bone_weights (which in turn relies on Skeleton::closest_point_on_line_segment).

Result (rig on the top and skinned model on the bottom):

Fig-18 Rig (top) and skinned model (bottom)

Particle Systems

A particle system in Scotty3D is a collection of non-self-interacting, physics-simulated spherical particles that collide with the rest of the scene.

Result:

Learnings

Four modules, four different kinds of problem. What stuck with me:

Rasterization is a precision problem before it is a performance problem. Most of my rasterizer bugs were about coverage rules and sample positions (which pixels a triangle edge owns, where the supersamples sit), not speed. Once the rules were exactly right, the optimizations were easy.
Write the mesh validator before the mesh operations. The halfedge structure has invariants (the twin of a twin is the original halfedge, every face is a closed loop) that a single wrong pointer breaks without any visible sign. A validator I could run after every local operation caught more bugs than any amount of staring at the viewport.
In a path tracer, the acceleration structure and the sampling strategy dominate, and the shading code barely matters. BVH build quality decided render time; importance sampling (direct lighting, environment maps) decided the noise at a given sample count. Both were worth more than any micro-optimization in the material code.
Animation is numerics first. Spline continuity, IK convergence and skinning weights that don't sum to one all show up as visual artifacts, and each is a small numerical issue that is easy to test in isolation once you know to look for it.
Next time I would write small unit tests per module from day one instead of trusting the picture. Half the time an image looked fine while a value was wrong.