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:
N instances of tori (doughnut-shaped
surfaces), cubes and spheres, with different positions, sizes, colors,
heights and orientations;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.
The program is split into five source files, all required to compile:
rasterizer.cc: argument parsing, help and
main;scene.h: shared geometric types, PRNG, scene generation
and analytical count of vertices and triangles;pipeline.h: transformations, framebuffer,
rasterization, shading, checksum, PPM images, timers, work map and
memory estimate;selftest.h: all self-tests, including those for
resources and output;reporting.h: shared options and records, CSV formats
and validation of the output destinations.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.
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.
add_torus samples two angles, with 4*S
samples around the doughnut and 2*S around its
cross-section.add_sphere uses 4*S meridians and
2*S latitude intervals; each pole has a single vertex,
without zero-area triangles.add_cube generates two triangles per face.
S, passed with --subdiv, is a resolution
parameter, not the number of recursive subdivisions.add_terrain creates the plane y=-1.8, with
x between -12 and 12 and z between 1 and
30.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.
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.
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.
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.
Compilation, after the module ... line of the notebook
cell and cd code:
clang++ -O3 -Wall -std=c++17 rasterizer.cc -o rasterizerThe 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.ppmWithout 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.
S increases approximately quadratically the
triangles of terrain, tori and spheres. Those of the cubes remain 12 per
instance.N adds objects in the clusters, also
increasing overlaps and work on already covered pixels; the terrain is
added only once.--frames increases the overall work without
keeping all the images in memory. By default only the last one is
saved.The timers with std::chrono::steady_clock measure three
phases separately, accumulating the seconds over all frames:
clear_seconds: clearing of colors, depth and
identifiers;transform_seconds: transformation and projection of the
vertices;raster_seconds: rasterization, depth test, shading and
writing to the buffers.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.
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.
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.ppmThe 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:
Fixed pixel cost. With only 25,720 triangles
(S=4) a frame already costs about 0.37 s, almost all in rasterization.
About 4.7 million pixels turn out to be covered and must be
interpolated, lit and written: this cost does not depend on
S. This is why from S=4 to S=32 the triangles increase 64
times but the time only by about a third.
Per-triangle cost. When the triangles become many the time grows almost linearly: between S=150 and S=300 about 16 ns more are needed for each added triangle (about 19 ns between S=75 and S=150). The apparent throughput rises from 0.07 to 49 Mtriangles/s simply because the fixed cost is amortized.
Phases. Rasterization always dominates (from 88% to 97%). The vertex transformation rises up to about 12% at S=300; the buffer clearing costs about 0.012 s per frame, constant.
Size suitable for the subsequent work. At S=300 the baseline takes about 59 s for 20 frames, enough to see a speedup and short enough to repeat the measurement within the 15-minute per-job limit, with about 11.5 GiB of memory. The small meshes instead show where the gain stops because the per-pixel work does not decrease.
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.
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 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.
fragments: number of samples at the pixel centers that
pass the triangle coverage, before the depth test. It
includes hidden surfaces and overlaps, so it can exceed the number of
pixels in the tile.triangles: number of distinct triangles that produce at
least one covered sample in the tile, counted only once per triangle and
tile. It does not count the mere intersection of the bounding boxes nor
triangles without covered samples.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.
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:
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;build.json;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;status checks that all the runs are complete and
consistent;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.
covered_pixels_last counts the pixels covered by
geometry in the last frame (about 4.7 million out of 8.29 million at
3840 x 2160).checksum_rgb is a 64-bit FNV-1a checksum on the RGB
bytes of the last frame, by rows from top to bottom and pixels from left
to right, without the PPM header.checksum_sequence combines the checksums of all the
frames, each encoded with eight bytes from the least significant to the
most significant. It makes it possible to check also the previous
frames, without saving them.--self-test checks a reference xorshift sequence and
rejects the zero seed. It verifies counts, data reproducibility,
preservation of the instances when increasing N and
independence of the layout from S.--self-test compiled with clang++ was
successful on Miyabi after the split into scene.h,
pipeline.h and selftest.h.reserve, tile_size, early check of the
destinations, memory estimate) I re-ran S=75,
S=150 and S=300 on Miyabi: the checksums match
those obtained before the changes, so the numerical result has not
changed.S have identical
checksums to each other, and this is the determinism check that the
loading of the summaries in plots.py enforces.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.
S: with coarse meshes the
per-covered-pixel work dominates, with fine meshes the per-triangle
work, and only then does the vertex transformation become a visible
share of the total.The baseline keeps the loops serial in order to have a simple reference with which to compare correctness and performance of the subsequent implementations.
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.