3D software rasterizer from scratch

Problem

A digital image is a grid of small colored elements, the pixels. A three-dimensional model can instead be described by many triangles. The problem is transforming these triangles into an image: understanding where they appear, which ones are visible when they overlap and how much they are lit. This operation is called rasterization and is part of how real-time graphics engines work.

The application performs this operation entirely in software, with a serial C++17 program that uses only the standard library. The scene is generated by the program, without external models:

The distribution of the triangles is deliberately irregular, both on the terrain and among the objects. This makes it possible to study load balancing: assigning screen areas of equal size to different processors does not mean assigning them the same amount of work. Instances can overlap or interpenetrate: the scene serves to study rendering and visibility, not a physical simulation of collisions or gravity.

Currently the whole project runs on a single core, entirely serial, as per specifications, so at the moment the difference in distribution does not serve to evaluate parallelism, but simply to prepare the environment for the subsequent optimizations.

How the baseline code works

The program is split into five source files, all required to compile:

The headers have include guards and include their own dependencies. The definitions in the headers are inline to allow their inclusion in multiple compilation units without multiple definitions; they are not directives that force optimizations on the compiler. scene.h is independent of rendering, pipeline.h uses scene and reporting, while selftest.h uses the modules it verifies. Vertices, triangles and pixels are stored in contiguous vectors. No threads, OpenMP, explicit SIMD instructions or GPU code are used. The loops are simple and serial; -O3 enables the normal compiler optimizations.

The baseline is deliberately simple: it contains no manual optimizations (for example the incremental computation of the edge functions or a cache-oriented data layout). It serves as a correctness and performance reference for the subsequent versions, which will be able to introduce them and measure them one at a time.

1. Scene construction

generate_scene creates a terrain and then exactly N instances.

--objects N excludes the terrain: N=0 shows only the plane; from N=3 all types are present. The order of the types is cyclic: torus, cube, sphere, torus, cube, sphere, … Each instance has its own vertices and triangles in the scene vectors.

The numbers of vertices and triangles are computed in closed form before generating the scene (scene_counts). The vectors are sized in advance with reserve, so there are no reallocations during generation; at the end the program verifies that the actual counts match the expected ones.

Xorshift32 is a hand-written pseudo-random generator, with XOR and shift operations on 32-bit unsigned integers. The fixed seed is 0x12345678; it is reset at the start of each generation. <random> is not used and there are no file inputs. make_instance uses the sequence to distribute about 70% of the instances in the left group, 20% in the right one and 10% in the background. These are assignment probabilities, not exact percentages for every N. The draws occur in an explicit order.

Increasing N preserves the previous instances; changing S (Subdivision) does not change their placement.

The scene units are arbitrary. The interval x=[-4,-1] has 4*S segments and z=[4,9] has 2*S, while each axis has only 12 segments in the outer parts. The product of the two coordinate sequences, produced by terrain_axis, forms a non-uniform grid: the area at the intersection of the dense intervals is much more detailed. The vertices are shared also at the transitions, avoiding cracks and joins between incompatible triangles. The terrain does not rotate.

The counts for each geometry are:

Geometry Vertices Triangles
Terrain, only once (4*S+13)*(2*S+13) 2*(4*S+12)*(2*S+12)
Each torus 8*S*S 16*S*S
Each cube 24 12
Each sphere 4*S*(2*S-1)+2 8*S*(2*S-1)

The total is obtained by adding the terrain and the N instances. The program prints the actual counts of vertices, triangles and instances of the three types. Each vertex has a normal, a vector perpendicular to the surface, used for lighting. Tori and spheres have a smooth appearance; the normals of the cubes are separate between the faces, so the edges remain sharp.

2. Transformation and projection

For each frame, transform_vertices applies to each instance a uniform scale, a rotation about its own center and a translation. Each instance has a fixed angular velocity between 0.004 and 0.016 radians per frame. The additional angle is spin * frame, with the first frame numbered zero: the animation does not depend on real time. The terrain uses an identity transformation and zero velocity.

The camera looks along the positive z axis.

The perspective projection uses coordinates proportional to x/z and y/z: distant objects appear smaller. The scale uses the smaller of the two image dimensions, so it does not distort the objects when the width/height ratio changes.

The near plane is the plane z=0.1. Each instance has a radius r that contains all its vertices after scaling: for the torus it derives from 0.78+0.26, for the cube from sqrt(3)*0.6 and for the sphere from 1. A small numerical margin is added. The position of the center satisfies center.z-r >= 0.1+1.0. A rotation does not change the distances from the center, so no instance can cross the near plane in any frame. The heights also guarantee distance from the terrain plane. The terrain is static and always has z>=1.

The check during the transformation also remains: if a vertex had z<=0.1, the program would report an error. For this scene there is no need to clip the triangles against the near plane. The lateral limits of the image are handled by limiting the pixels visited.

3. Rasterization and visibility

clear_framebuffer initializes color and depth. render_frame visits all the triangles in order and calls rasterize_triangle.

For each triangle the rectangle that contains it on screen (Bounding Box) is considered. Three edge functions establish whether the center of each pixel of the rectangle is inside the triangle. A rule called top-left decides which edges to include when the pixel center falls exactly on an edge. Zero-area triangles are ignored. Both face orientations are drawn.

From the edge functions three weights are derived, the barycentric coordinates. These weights make it possible to interpolate the vertex attributes at the pixel. To respect perspective, 1/z is interpolated, not z directly; for the normals, normal/z is interpolated first and then divided by 1/z.

The z-buffer stores for each pixel the depth of the winning surface.

In the code it contains 1/z: a larger value indicates a closer surface. If two triangles have exactly the same computed depth, the one with the smaller original identifier wins. That identifier is also stored, so the result does not depend on the processing order when the computations are equal.

4. Lighting and image

shade normalizes the interpolated normal and computes its dot product with the direction of a fixed light. A surface facing the light is brighter; one facing elsewhere keeps a small ambient component.

The model uses 0.15 + 0.85 * max(0, normal · light) and the object’s color. For this initial version there are no textures, cast shadows, transparency or antialiasing, which may be added at the professor’s request, in case this initial application turns out to be too simple.

The colors are rounded to 8 bits per channel without gamma correction.

write_ppm saves the last frame in binary PPM P6 format. In the notebook the file is converted with convert image.ppm image.png and displayed. The options described below also make it possible to save a sequence of frames for a GIF, without changing the scene.

Sizes, execution and measurements

Compilation, after the module ... line of the notebook cell and cd code:

clang++ -O3 -Wall -std=c++17 rasterizer.cc -o rasterizer

The headers are included by rasterizer.cc: they must not be passed to the compiler as separate sources.

The compiler, the flags and the SHA-256 hash of the five source files and of the executable are recorded in build.json; before each run workflow.py verifies that nothing has changed since the compilation.

Examples to run on Miyabi with %%sub, after cd code:

# Small analytical checks, without writing images.
./rasterizer --self-test

# Sample image: 6,603,640 triangles, a single frame.
./rasterizer --width 1920 --height 1080 --subdiv 64 --objects 150 --frames 1 --output image.ppm

Without arguments the values are 960 x 720, S=64, N=24, 60 frames and image.ppm.

--help shows the limits: dimensions from 1 to 32768, S from 2 to 1024, N from 0 to 10000 and frames from 1 to 1000000. The available time and memory limit the combinations that can actually be used; the maximums are not a recommendation to run all parameters at their maximum simultaneously.

The timers with std::chrono::steady_clock measure three phases separately, accumulating the seconds over all frames:

render_seconds is the sum of the three times and seconds_per_frame the average. Geometry generation, initial buffer allocation, checksum and PPM writing are excluded. The total process time is therefore greater.

Memory estimate and limit

Before generating the scene the program prints estimated_memory_gib, computed from the analytical counts: each vertex takes 56 bytes in the scene and 48 bytes in the projected version, each triangle 32 bytes and each pixel 19 bytes (color, depth and triangle identifier), plus the per-frame records and the instances.

With --work-map a second framebuffer is added.

The memory therefore grows as O((N+1)*S*S + width*height). If the estimate exceeds 64 GiB the program refuses to start, with a message that suggests reducing S, N or the image, instead of failing halfway through the execution due to exhausted memory.

Configuration measured on Miyabi

The reference series uses 3840 x 2160, N=150, 20 frames and seven values of S: 4, 8, 16, 32, 75, 150 and 300, with three repetitions each (21 runs).

The three repetitions of each S give the same vertices, triangles and checksums. The largest value is also the heaviest configuration:

./rasterizer --width 3840 --height 2160 --subdiv 300 --objects 150 --frames 20 --output image.ppm

The times are averages of the three repetitions; ± indicates the sample standard deviation. Rasterization, transformation and clearing are the share of the total render_seconds.

S Triangles/frame Vertices Seconds/frame Mtriangles/s Raster Transf. Clearing Estimated memory
4 25,720 13,909 0.367 ± 0.003 0.07 96.6% 0.0% 3.3% 0.15 GiB
8 102,264 52,205 0.393 ± 0.002 0.26 96.8% 0.1% 3.1% 0.15 GiB
16 410,488 206,365 0.431 ± 0.003 0.95 96.9% 0.2% 2.9% 0.18 GiB
32 1,647,480 824,957 0.490 ± 0.004 3.37 96.7% 0.8% 2.5% 0.28 GiB
75 9,071,688 4,537,319 0.680 ± 0.001 13.34 95.0% 3.2% 1.8% 0.86 GiB
150 36,322,488 18,163,169 1.211 ± 0.005 30.00 91.9% 7.2% 1.0% 2.99 GiB
300 145,364,088 72,684,869 2.951 ± 0.027 49.25 87.8% 11.8% 0.4% 11.52 GiB

The estimated memory rises by about 0.15 GiB (a second framebuffer) in the first repetition of each S, the one that also produces the work map.

Reference checksums (RGB of the last frame / sequence of the 20 frames), to be compared with the subsequent versions at equal S:

S checksum_rgb checksum_sequence
4 b32ad3c65e989a0e 9a067294c8e8dd65
8 d54c1d66af009cc3 28384246f2318fe0
16 060489adedc9f263 a8c010db3aa94959
32 9d29c8ea67b5765a 861aabb2725458ea
75 1b3f1e830bfee83a a6d6f12c1f442026
150 525660f7e138498a a6554ab44a86a9e6
300 2e400110c6324210 854e138d3bd41ade

What the measurements show:

The printed estimate estimated_frames_180s is ceil(180 / seconds_per_frame), limited to the range allowed by the CLI.

It is not a timed stop and it does not influence rendering: number of frames and checksum remain determined by the execution arguments. The rotations can change the average cost, so the estimate must be verified. The scene is identified in the output by scene=clustered_terrain_v2.

Stable outputs for comparison and animation

All the new options are optional. --variant NAME is baseline by default, and --threads N is 1

In the current state of the application they are only labels, they do not change the rendering nor activate threads. The name can contain commas and quotes, correctly escaped in the CSV, but not control characters or line breaks.

All the destinations (--output, --timings, --summary, --work-map) are checked before rendering: the folder must exist, the path cannot be a directory, the files must be distinct from each other and must not collide with the saved frames.

A wrong path makes the program fail immediately, not after minutes of computation.

--timings FILE.csv overwrites a file with a header and one row for each frame, from zero to frames-1, in the original order:

variant,width,height,subdiv,objects,frames,frame,clear_s,transform_s,raster_s,total_s,frame_hash

The times are in seconds. total_s is the sum of the three phases of that frame; frame_hash is FNV-1a of its RGB bytes. The records are collected outside the timers, and the CSV is written right after the frame loop. The additional memory of the records grows linearly with the number of frames, without keeping their images.

--summary FILE.csv appends one row per execution:

variant,threads,width,height,subdiv,objects,frames,vertices,triangles_per_frame,covered_pixels_last,clear_total_s,transform_total_s,raster_total_s,render_seconds,seconds_per_frame,triangles_per_second,checksum_rgb,checksum_sequence

A new (or empty) file receives the header only once. An existing file with a different header or an incomplete last row is rejected. A single writer process per file is required: for concurrent jobs I use distinct files.

triangles_per_second = triangles_per_frame * frames / render_seconds: it counts all the triangles submitted to the pipeline, not only the visible ones, and it uses the overall rendering time, not only the rasterization time.

The writing order is deliberate: first timings.csv, then the PPM image and the work map (the saved frames are written during the loop), and last summary.csv. The summary is written only once the run is completed, so its presence is the sign that all the other files of the run exist; workflow.py uses it to skip the runs already completed.

The three CSVs use commas, LF line endings and a locale-independent decimal point. The times and the speeds are in scientific notation with 17 digits after the point; the counts are decimal integers.

All the hashes have exactly 16 lowercase hexadecimal digits, including the leading zeros. The names and the order of the columns are the contract to be maintained in the parallel implementations. In the CSVs the hashes are called checksum_rgb and checksum_sequence; on the terminal the program prints them as checksum_rgb_fnv1a64 and checksum_sequence_fnv1a64.

--save-frames DIR --save-every K saves the frames whose index is a multiple of K, plus the last one, only once each. K is 1 by default.

The directory must already exist; it is advisable to use a new one to avoid leftover images from other runs. The names are frame_00000.ppm, frame_00001.ppm, etc., with at least five digits for the index. The saving happens after the end-of-rasterization timestamp.

--output keeps saving the last frame even when a sequence is exported. All the frames, even those not saved, contribute to the sequence checksum.

For the GIF I use a preview run at 960 x 540, S=32, N=150 and 120 frames. Positions, colors and angles remain the same as in the benchmark.

In the notebook I reduce the images to 50% with convert, set a delay of 5 hundredths of a second per frame (20 fps) and display the GIF. The playback duration is independent of the time taken to compute the images. The checksums of the preview are 288b8521ad274ffa (last frame) and 99f08edad7b164b5 (sequence).

Work map on the tiles

--work-map FILE.csv performs a second complete pass on the last frame, reusing the projected vertices and a separate framebuffer. This pass is not included in the times or in the throughput counts of the benchmark; its checksum must match that of the normal rendering.

It writes:

tile_x,tile_y,fragments,triangles

Each tile measures 32 x 32 pixels (constant WorkMap::tile_size, used by the map as well as by the rasterization and by the tests). The coordinates are tile indices starting from zero; the rows are sorted by tile_y, then tile_x. The empty tiles and the partial ones at the image edges are also included.

The normal path uses a C++ specialization without counting instructions or runtime branches for the map. The map describes the coverage work: it is not a measure of the per-tile times and it does not show the cost of the subpixel triangles that do not cover any pixel center.

Analysis from the notebook and of the execution flow

The compilation/scaling, GIF and plot cells belong to the notebook, outside code/.

The results are written under results/, with one directory per batch and variant/thread, a summary and a distinct CSV for each repetition. The flow is:

  1. clean at the start deletes the results of the current variant (only results/run01/baseline_t1, never other variants), so every complete execution starts from scratch;
  2. the compilation records compiler version, flags, source hashes and parameters in build.json;
  3. the 21 runs (7 values of S times 3 repetitions) run with %%sub; the small runs (S ≤ 32) are grouped in jobs of six, the large ones are launched in separate jobs, to stay within the 15-minute per-job limit;
  4. status checks that all the runs are complete and consistent;
  5. the preview, the GIF, the plots and the work maps are generated from the CSVs;
  6. prune at the end deletes the heavy objects (the PPMs of the last frame, the preview frames, the executable in code/ and image.ppm), keeping CSVs, logs, metadata, GIF and image.png.

The GIF is generated in a separate run, to prevent the image I/O from affecting the state of the caches between the benchmark frames, while still remaining outside the timers.

The analysis functions read multiple CSVs, compute the average of the repetitions of the same configuration and compare variants with equal resolution, S, N and frames. They show time per frame, throughput and stacked phases as a function of the triangles (logarithmic scale on the x-axis, with also a log-log view), the frame trace without automatically discarding the warm-up, and the maps with common color scales.

The speedup is time_baseline / time_variant; the efficiency is speedup / threads, relative to baseline with threads=1. This last measure is meaningful only if the label really indicates the number of CPU workers; modifying --threads is not enough to obtain an efficiency of a parallel or GPU version.

The comparison of the per-frame CSVs checks the hashes as strings and reports the first differing index. The hashes remain separate from the times in the checks.

Verification of the results

The pseudo-randomness has a fixed seed: with equal parameters and executable the results are repeatable. The checksums are compared only with equal scene, S, N, resolution and frames.

For a parallel version the same triangle identifiers, edge rules and numerical operations must be maintained. The checksum is a practical check, not a proof of equality: for an exact verification the files can also be compared byte by byte.

Different compilers or architectures, in particular CPU and GPU, can introduce differences in rounding, FMA or trigonometric functions. The mere use of a stable identifier does not guarantee bit-for-bit identity between these environments.

Where is parallelism

The baseline keeps the loops serial in order to have a simple reference with which to compare correctness and performance of the subsequent implementations.

Use of AI

For this work Jupyter AI was used with the specific setting of “GPT-6 Astra”, both in build and in plan mode, to write the base code, to receive explanations of it and to modify the folder structure once the code reached a satisfactory level of complexity. The draft of this document was also created in Italian thanks to ASTRA. It was subsequently reread and revised manually to avoid gross errors in the writing, and translated into English with “CLAUDE OPUS 5.5 High” on the student’s personal computer before being re-uploaded to Jupyter.