← All projectsComputer graphics project · 2026

SAH k-d Tree Ray Tracer

A CPU ray tracer with an SAH-optimized k-d tree and an adaptive bucketing strategy for fast construction.

Explore source code ↗Jump to results ↓

X axisY axis

scene bounds

SAH split

bucket candidate

FULL SAH

BUCKETS

// construction strategy

Spend precision where it matters.

Large nodes use a fixed number of sampled buckets to keep construction practical. Near the leaves, the implementation switches back to exact SAH evaluation so the final splits stay precise.

10test scenes

218kpolygons in A10

02SAH strategies

CPUANSI C++ implementation

// technical problem

Accelerate the expensive part of ray tracing

A naive ray tracer tests every triangle against every ray. The k-d tree reduces that work by recursively partitioning space, but constructing a high-quality tree can itself become expensive.

I implemented the Surface Area Heuristic as the cost model for choosing split planes. The exact variant evaluates all triangle bounds; the approximate variant uses bucketing to limit the number of candidates in large nodes. This creates a controlled trade-off between build time and traversal quality.

// implementation

From triangle bounds to traversal

Candidate planes

Each triangle contributes minimum and maximum bounds on all three axes, producing six possible split events.

SAH cost

For each candidate, the implementation estimates left and right surface areas, primitive counts and traversal cost.

Adaptive buckets

Large nodes use sampled buckets. When a node becomes small enough, construction switches to FULL SAH.

Stable partition

Sorted primitive lists are propagated into child nodes with a linear stable pass instead of repeated full sorting.

Measured traversal

Build time, traversal steps and ray–triangle intersection tests are recorded for every scene and strategy.

// measured results

SAH versus naive intersection work

The clearest baseline is the number of triangle intersection tests per ray. The cards use one consistent configuration — Approx. SAH with bucketing — and compare it first with the naive estimate, then with the report's reference TDBVH (a BVH-style hierarchy). Against TDBVH I show both traversal steps, hit tests and total trace time.

Representative Sponza atrium render — Representative Sponza render

2,418× fewertriangle tests / ray vs naive

SAH vs naive · hit tests

~67,697 → 28 hit tests / ray

SAH vs TDBVH

Traversal: 95 vs 293 / ray
Hit tests: 28 vs 27 / ray
1.77× faster trace (3.62 s vs 6.40 s)

Approx. SAH · build 6.5 s · trace 3.62 s · 135,394 triangles from repository OBJ

Representative Asian Dragon scene render — Representative Asian Dragon render

902,363× fewertriangle tests / ray vs naive

SAH vs naive · hit tests

~3,609,453† → 4 hit tests / ray

SAH vs TDBVH

Traversal: 33 vs 32 / ray
Hit tests: 4 vs 3 / ray
0.87× trace time · TDBVH is 1.15× faster (1.07 s vs 0.93 s)

Approx. SAH · build 150.1 s · trace 1.07 s · ~7.22M-triangle benchmark estimate†

Representative PowerPlant scene render — Representative PowerPlant view

288,636× fewertriangle tests / ray vs naive

SAH vs naive · hit tests

~6,350,000† → 22 hit tests / ray

SAH vs TDBVH

Traversal: 55 vs 146 / ray
Hit tests: 22 vs 10 / ray
1.37× faster trace (2.62 s vs 3.60 s)

Approx. SAH · build 223.8 s · trace 2.62 s · ~12.7M triangles†

Scene	FULL SAH			Approx. SAH
	Build s	Trace s	Tests / ray	Build s	Trace s	Tests / ray
Conference	7.3	2.40	23	6.5	2.50	24
A10	5.4	0.48	2	3.9	0.47	2
Sponza	7.5	3.51	28	6.5	3.62	28
Šibenik	1.2	1.71	11	1.1	1.67	10
PowerPlant	286.7	2.71	23	223.8	2.62	22
HairBall	154.7	4.90	37	112.3	5.10	39
Armadillo	6.7	0.91	5	4.7	0.93	5
Asian Dragon	233.5	1.07	4	150.1	1.07	4
Gallery	30.0	2.79	15	21.6	2.78	14
City	1.7	1.03	7	1.5	0.94	6

The large multipliers are reductions in hit tests per ray against the naive estimate, not end-to-end render-time speedups. The TDBVH comparison uses measured traversal steps / ray, hit tests / ray and total trace time. All values come from the single mode / single-threaded CPU measurement; no GPU acceleration is involved. All SAH values use the Approx. SAH row from the report. † Sponza is counted from the repository OBJ, while Asian Dragon and PowerPlant polygon counts are standard public benchmark estimates.

// engineering notes

What the measurements exposed

SAH makes the reduction visible

Across the selected scenes, the measured SAH result stays between four and 28 triangle tests per ray while the naive estimate grows into the millions.

Traversal order matters

The final implementation uses a stack-based traversal. HairBall shows the cost of not visiting the nearest node first when many bounding volumes overlap.

Approximation can be enough

Bucket sampling reduces construction time while keeping the number of tests per ray close to FULL SAH in most of the tested scenes.

// project evidence

Source repositoryANSI C++ ray tracer and SAH k-d tree implementation ↗

Interested in graphics performance?

Let's build the structure behind the image.

Work with me →