Ray tracing & acceleration structures光线追踪与加速结构

Rasterization (lesson 04) only ever answers one question well: what does the eye see? Its loop starts every ray at the camera. But shadows start at a surface and point toward a lamp; reflections start at a surface and point into the mirror; the recursive rendering equation of lesson 01 needs rays from arbitrary origins in arbitrary directions. So we switch to lesson 01's transposed loop — one ray per pixel, then follow rays wherever physics sends them — and spend the rest of the lesson making that loop fast enough to actually use, because the naive version tests every object against every ray. 光栅化（第 04 课）真正答得好的只有一个问题：眼睛看到什么？它的循环让每条光线都从相机出发。但阴影从表面出发、指向一盏灯；反射从表面出发、指进镜子里；第 01 课那个递归的渲染方程，需要从任意原点、朝任意方向发出的光线。于是我们切换到第 01 课那个转置的循环——每个像素一条光线，然后让光线随物理去往任何地方——并用这一课余下的篇幅，把这个循环变得足够快、真能用起来，因为它的朴素版本要拿每个物体去和每条光线都测一遍。

The plan本课计划

Five moves. (1) Write the ray as r(t) = o + t·d over an explicit interval [t_min,t_max], and generate one primary ray per pixel through the image plane, reusing lesson 02's camera. (2) Do the geometry: ray–sphere (a quadratic in t) and ray–triangle via Möller–Trumbore (barycentric u,v and t from cross/dot products); the nearest valid t is the visible hit. (3) Follow the rays: the Whitted recursive tracer casts shadow, reflection, and refraction rays at each hit, weights reflect/refract by Fresnel, and caps recursion depth. (4) Confront the cost: naive tracing is O(N) per ray, O(P·N) for the frame — hopeless at millions of triangles. (5) Fix the typical case with acceleration structures: bound primitives in AABBs, build a BVH, and descend only into boxes a ray hits. A good balanced BVH often approaches logarithmic work for simple rays, but traversal is still O(N) in the worst case. The widget makes the "skip whole subtrees" idea literal. Then lesson 11 turns the one reflection ray into a spray of random ones.

五步走。(1) 把光线写成 r(t) = o + t·d，并显式限定在区间 [t_min,t_max] 上，再沿成像平面为每个像素生成一条主光线，复用第 02 课的相机。(2) 做几何：光线–球（关于 t 的二次方程）与经 Möller–Trumbore 的光线–三角形（由叉积/点积解出重心坐标 u,v 与 t）；最小的有效 t 就是可见命中。(3) 让光线继续走：Whitted 递归追踪器在每个命中处投出阴影、反射、折射光线，用 Fresnel 给反射/折射加权，并给递归深度设上限。(4) 正视开销：朴素追踪每条光线是 O(N)，一帧是 O(P·N)——面对数百万三角形时毫无希望。(5) 用加速结构改善典型情况：把图元装进 AABB，建一棵 BVH，光线只往它命中的盒子里下降。优质且平衡的 BVH 对简单光线往往接近对数开销，但遍历最坏仍是 O(N)。控件会把“跳过整棵子树”这件事画得明明白白。随后第 11 课把那一条反射光线，变成一把随机的光线。

1 · A ray is r(t) = o + t·d — and one per pixel光线就是 r(t) = o + t·d——每像素一条

A ray is the simplest object in the whole field: a starting point plus a direction, parameterized by a single scalar t.

光线是整个领域里最简单的对象：一个起点加一个方向，用单个标量 t 参数化。

r(t) = o + t·d , t ∈ [t_min, t_max] .

Here o is the origin and d the direction (we keep it unit-length so t reads as true distance). A renderer should not use the mathematical test t>0 literally: it gives every ray an acceptance interval. t_min rejects the numerically ambiguous neighborhood of the origin; t_max stops a shadow ray at its light or keeps a previously found closer hit. Primary rays commonly use a near value and infinity; secondary rays need a robust origin offset plus a small positive t_min. A single fixed world-space epsilon is fragile across a scene spanning micrometers and kilometers, so production renderers use scale-aware or floating-point-aware offsets.

这里 o 是原点，d 是方向（我们让它单位长，这样 t 就读作真实距离）。渲染器不应照搬数学上的 t>0 测试，而应给每条光线一个可接受区间。t_min 排除原点附近数值上模糊的区域；t_max 让阴影光线停在光源处，或利用已找到的更近命中缩短搜索。主光线通常用近端值到无穷；次级光线既需要稳健的原点偏移，也需要一个小的正 t_min。同一个固定世界空间 epsilon 无法同时适应横跨微米与千米的场景，所以生产渲染器采用随尺度变化或感知浮点精度的偏移。

Camera ray generation. We reuse lesson 02's camera exactly, just run backwards. Instead of projecting a 3D point onto the image plane, we take each pixel center on the image plane and shoot the ray from the eye through it into the scene — one primary ray per pixel. Put the eye at e looking down −z, image plane at focal length f; for pixel (i, j) on a W×H grid, map to normalized screen coordinates (s_x, s_y) ∈ [−1, 1] (accounting for aspect ratio and the field of view), and:

相机光线生成。我们原样复用第 02 课的相机，只是倒着跑。不是把一个三维点投影到成像平面，而是取成像平面上每个像素的中心，从眼睛穿过它把光线射入场景——每像素一条主光线。把眼睛放在 e 处、朝 −z 看，成像平面在焦距 f 处；对 W×H 网格上的像素 (i, j)，映射到归一化屏幕坐标 (s_x, s_y) ∈ [−1, 1]（计入宽高比与视场角），于是：

o = e , d = normalize( s_x·right + s_y·up − f·forward ) .

This is exactly lesson 01's picture — "a ray per pixel, fanning out from the eye through the grid" — now written as code. Notice the loop has already flipped: rasterization's outer loop was triangles, here the outer loop is pixels. That flip is the whole reason arbitrary rays (shadow, reflection) come for free: once "trace a ray" is a subroutine, it does not care whether the origin is the eye or a mirror.

这恰恰就是第 01 课那幅画面——“每像素一条光线，从眼睛出发穿过网格扇形散开”——如今写成了代码。注意循环已经翻转：光栅化的外层循环是三角形，这里外层循环是像素。正是这个翻转，让任意光线（阴影、反射）唾手可得：一旦“追一条光线”成了子程序，它就不在乎原点是眼睛还是镜子。

2 · Ray–primitive intersection: sphere and triangle光线–图元求交：球与三角形

Tracing a ray means solving, for each primitive, "at what t does r(t) touch this surface?" — then keeping the smallest t inside the ray's acceptance interval. Two primitives cover almost everything.

追一条光线，就是对每个图元解“r(t) 在哪个 t 触到这个表面？”——然后在所有图元里保留光线可接受区间内最小的 t。两种图元几乎涵盖了一切。

Ray–sphere. A sphere of center c, radius R is the set of points with |p − c|² = R². Substitute p = r(t) = o + t·d and expand — because |d| = 1, you get a clean quadratic in t:

光线–球。圆心 c、半径 R 的球，是满足 |p − c|² = R² 的点集。代入 p = r(t) = o + t·d 展开——因为 |d| = 1，你会得到一个关于 t 的干净二次方程：

t² + 2(d·(o−c)) t + (|o−c|² − R²) = 0 , t = −b ± √(b² − c₀) .

The discriminant tells the story: negative → the ray misses; zero → it grazes (tangent); positive → two roots, entry and exit. Take the smallest root inside the ray interval. If neither root lies in [t_min,t_max], there is no valid hit for this ray. Worked case: eye at origin, d = (0,0,−1), sphere at c = (0,0,−5), R = 1. Then o−c = (0,0,5), b = d·(o−c) = −5, c_0 = 25 − 1 = 24, discriminant = 25 − 24 = 1, roots t = 5 ± 1 = {4, 6} — front face at 4, back face at 6. For a primary ray whose interval contains both, we keep t = 4.

判别式道出全部：负 → 光线错过；零 → 相切（掠过）；正 → 两个根，入点与出点。取光线区间内最小的根。若两根都不在 [t_min,t_max] 内，这条光线就没有有效命中。算一例：眼睛在原点，d = (0,0,−1)，球心 c = (0,0,−5)，R = 1。则 o−c = (0,0,5)，b = d·(o−c) = −5，c_0 = 25 − 1 = 24，判别式 = 25 − 24 = 1，根 t = 5 ± 1 = {4, 6}——正面在 4，背面在 6。对同时包含两根的主光线，我们保留 t = 4。

Ray–triangle (Möller–Trumbore). Triangles are the universal primitive (lesson 03), so this test is the workhorse. A point inside triangle (v_0, v_1, v_2) is v_0 + u·(v_1−v_0) + v·(v_2−v_0) in barycentric coordinates. Set that equal to o + t·d — three equations, three unknowns (t, u, v) — and solve with Cramer's rule expressed as cross and dot products (no matrix inverse needed):

光线–三角形（Möller–Trumbore）。三角形是通用图元（第 03 课），所以这个测试是主力。三角形 (v_0, v_1, v_2) 内一点，用重心坐标写作 v_0 + u·(v_1−v_0) + v·(v_2−v_0)。令它等于 o + t·d——三个方程、三个未知数 (t, u, v)——用克拉默法则、以叉积与点积表达来解（无需求矩阵逆）：

e₁ = v₁−v₀, e₂ = v₂−v₀, p = d×e₂, det = e₁·p
u = (o−v₀)·p / det , q = (o−v₀)×e₁ , v = d·q / det , t = e₂·q / det

The hit is valid iff u ≥ 0, v ≥ 0, u + v ≤ 1 (inside the triangle), and t_min ≤ t ≤ t_max (inside this ray's interval). If det ≈ 0 the ray is parallel to the triangle's plane — no hit. The pay-off of barycentrics: the same (u, v) that decide "inside?" also interpolate per-vertex normals, UVs, and colors (lesson 05) at the hit point, for free.

当且仅当 u ≥ 0、v ≥ 0、u + v ≤ 1（在三角形内）且 t_min ≤ t ≤ t_max（落在这条光线的区间内）时，命中有效。若 det ≈ 0，光线平行于三角形所在平面——不命中。重心坐标的红利：那对判定“在内吗？”的 (u, v)，还能在命中点免费插值逐顶点的法线、UV 与颜色（第 05 课）。

The nearest valid t wins最小的有效 t 获胜

Visibility for a ray is just a running minimum. Loop over primitives; keep the smallest intersection in [t_min,t_max], and shrink t_max to that value as soon as it is found. When the loop ends, that primitive is what the ray sees first — the ray-tracing analogue of rasterization's z-buffer, but resolved per ray instead of per pixel-stamp. This is exactly the inner loop of lesson 01's ray-tracing side, and section 4 is about how expensive that innocent "loop over primitives" becomes.

对一条光线而言，可见性不过是一次“实时求最小值”。遍历图元；保留落在 [t_min,t_max] 内的最小交点，并在找到它时立刻把 t_max 缩到该值。循环结束时，那个图元就是光线最先看到的东西——它是光栅化深度缓冲在光线追踪里的对应物，只是按每条光线、而非每次像素盖章来求解。这正是第 01 课光线追踪那一侧的内层循环，而第 4 节要讲的，就是这句看似无害的“遍历图元”会变得多么昂贵。

3 · The Whitted recursive ray tracerWhitted 递归光线追踪器

Finding the nearest hit only answers visibility. To shade it we ask what light reaches it — and Turner Whitted's 1980 insight was that the same "trace a ray" routine answers that too. At every hit point, cast three kinds of secondary ray:

找到最近命中只回答了可见性。要给它着色，得问有多少光到达它——而 Turner Whitted 在 1980 年的洞见是：同一个“追一条光线”的例程也能回答这个。在每个命中点，投出三种次级光线：

Shadow ray — from the hit toward each light. If anything blocks it before the light (an intersection inside [t_min,t_light)), the point is in shadow for that light and gets no direct contribution from it. This yields hard shadows for free — the effect rasterization must fake with shadow maps.阴影光线——从命中点射向每个光源。若在到达光源前有任何东西挡住它（在 [t_min,t_光源) 内有交点），该点对这个光源就处于阴影中，得不到它的直接贡献。这免费得到硬阴影——正是光栅化必须用阴影贴图去伪造的效果。
Reflection ray — for a mirror-like surface, reflect the incoming direction about the normal, r = d − 2(d·n)n, and recurse: trace that ray, shade its hit, bring the color back. A mirror shows the world by tracing more rays.反射光线——对镜面般的表面，把入射方向关于法线反射，r = d − 2(d·n)n，并递归：追这条光线、给它的命中着色、把颜色带回来。镜子靠追更多光线来映出世界。
Refraction ray — for glass/water, bend the ray across the interface by Snell's law η₁ sinθ₁ = η₂ sinθ₂ and recurse into the medium. Total internal reflection (no valid θ₂) turns it back into a pure reflection.折射光线——对玻璃/水，用斯涅尔定律 η₁ sinθ₁ = η₂ sinθ₂ 让光线在界面处弯折，并递归进入介质。全内反射（无有效 θ₂）会让它退化为纯反射。

A hit needs two normals and a medium state一次命中需要两种法线与介质状态

Store the true primitive's geometric normal n_g separately from the interpolated or normal-mapped shading normal n_s. n_g decides front versus back, which side to offset a spawned ray toward (p' = p ± δn_g, chosen from the outgoing direction), and whether a dielectric ray enters or exits. n_s shapes the BRDF for appearance; orient it consistently with n_g, but never let a bump map redefine inside versus outside. For refraction, carry the ray's current medium—or an IOR stack for nested glass—so Snell uses the actual pair η_i/η_t. Assuming every boundary is air-to-glass fails as soon as glass contains liquid or another dielectric.

要把真实图元给出的几何法线 n_g，与插值或法线贴图得到的着色法线 n_s 分开保存。n_g 决定正反面、派生光线该向哪一侧偏移（p' = p ± δn_g，符号由出射方向决定），以及介质光线是在进入还是离开。n_s 只为外观塑造 BRDF；应让它与 n_g 朝向一致，却绝不能让凹凸贴图重定义内外。折射时还要携带光线当前所在的介质——嵌套玻璃则用 IOR 栈——让 Snell 真正使用 η_i/η_t 这对折射率。一旦玻璃里装了液体或另一层电介质，“每个界面都是空气到玻璃”的假设就会失效。

Fresnel equations set how much energy goes each way: at grazing angles a glass surface is almost a perfect mirror; head-on it is mostly transparent. So the shaded color at a hit is (direct light, gated by shadow rays) + F·(reflected color) + (1−F)·(refracted color), where F is the Fresnel reflectance. A classic Whitted renderer uses a recursion-depth cap (say 4–8 bounces) so two facing mirrors cannot recurse forever. That cap is a practical approximation, not a free theorem: it discards all deeper transport and therefore introduces truncation bias. Lesson 11 replaces hard termination with compensated Russian roulette when an unbiased Monte Carlo estimator is required.

Fresnel 方程决定各方向分走多少能量：掠射角下玻璃面几乎是完美镜子；正对时则大多透明。于是命中处的着色颜色是 (直接光，受阴影光线门控) + F·(反射色) + (1−F)·(折射色)，其中 F 是 Fresnel 反射率。经典 Whitted 渲染器会设置递归深度上限（比如 4–8 次弹跳），避免两面对着的镜子永远递归。但这只是实用近似，不是什么免费定理：它丢弃全部更深的传输，因此引入截断偏差。需要无偏蒙特卡洛估计器时，第 11 课会用带补偿的俄罗斯轮盘赌替代硬终止。

trace(ray, depth, media): hit = nearest_hit(ray, ray.tMin, ray.tMax) # nearest hit in the valid interval if no hit: return background ng = hit.geometricNormal ns = face_forward(hit.shadingNormal, ng) # appearance, not inside/outside color = 0 for each light L: # SHADOW ray — is L visible from hit? s = spawn_ray(hit.p, direction_to(L), ng, tMax=distance_to(L)) if not nearest_hit(s) before L: color += direct_shade(hit, L) if depth < MAX and hit.reflective: # REFLECTION ray, recurse r = spawn_ray(hit.p, reflect(ray.d, ns), ng) color += F * trace(r, depth+1, media) if depth < MAX and hit.transparent: # REFRACTION ray (Snell), recurse etaI, etaT, nextMedia = interface_iors(media, hit, ray.d, ng) t = spawn_ray(hit.p, refract(ray.d, ng, etaI/etaT), ng) color += (1-F) * trace(t, depth+1, nextMedia) return color

This is the whole classic ray tracer. Notice every line either calls nearest_hit or recurses into trace, which itself calls nearest_hit. The cost of the entire renderer therefore collapses onto one subroutine — and that subroutine's naive form is the problem section 4 confronts.

这就是整个经典光线追踪器。注意每一行要么调用 nearest_hit、要么递归进 trace，而后者本身又调用 nearest_hit。于是整台渲染器的开销全都坍缩到一个子程序上——而这个子程序的朴素形式，正是第 4 节要面对的问题。

4 · The cost problem — O(N) per ray, O(P·N) per frame开销问题——每光线 O(N)，每帧 O(P·N)

The naive nearest_hit tests every primitive against every ray. With N primitives that is O(N) intersection tests per ray. Now count the rays. A P-pixel image casts P primary rays; each hit spawns shadow rays (one per light) and reflection/refraction rays, and those recurse — so the real ray count is several times P. Even counting only primary rays, the frame is O(P·N).

朴素的 nearest_hit 拿每个图元去和每条光线都测。N 个图元，就是每条光线 O(N) 次求交测试。再数光线数量。一幅 P 像素的图像投出 P 条主光线；每个命中又派生阴影光线（每光源一条）与反射/折射光线，它们还递归——所以真实光线数是 P 的好几倍。哪怕只数主光线，一帧也是 O(P·N)。

Put numbers on it. A 1080p frame is P ≈ 2×10⁶ pixels; a modest scene has N ≈ 10⁶ triangles. Naive primary-ray visibility alone is P·N ≈ 2×10¹² ray–triangle tests per frame — trillions, before a single shadow or reflection. At even a billion tests per second that is over half an hour for one frame. This is why the plausible-sounding "just shoot rays" was, for decades, a non-starter for anything but tiny scenes. The primitive count grows; the linear scan does not scale. We need to stop testing primitives that a ray obviously cannot hit.

给它填上数字。一帧 1080p 是 P ≈ 2×10⁶ 像素；一个不算大的场景有 N ≈ 10⁶ 三角形。仅朴素的主光线可见性就是每帧 P·N ≈ 2×10¹² 次光线–三角形测试——数万亿次，还没算一条阴影或反射。哪怕每秒十亿次测试，一帧也要半个多钟头。这就是为什么听着挺靠谱的“直接发光线”，几十年来对除小场景以外的一切都是行不通的。图元数在涨；线性扫描扛不住。我们必须停止去测那些光线明显不可能命中的图元。

5 · Acceleration structures — BVH pruning, not a complexity guarantee加速结构——BVH 剪枝，而非复杂度保证

The key move is a bounding volume: wrap a group of primitives in a cheap shape, and test the ray against the cheap shape first. If the ray misses the box, it misses everything inside — one test rejects the whole group. The favorite box is the axis-aligned bounding box (AABB), tested by the slab method: an AABB is the intersection of three "slabs" (one per axis, between a min and max plane); intersect the ray with each slab to get a [t_{near}, t_{far}] interval, and the ray hits the box iff the three intervals overlap, i.e. max(t_{near}) ≤ min(t_{far}). It is a handful of subtractions, multiplies, and min/max — no square roots.

关键一招是包围体：把一组图元裹进一个廉价形状，先拿光线去测那个廉价形状。若光线错过盒子，它就错过里面的一切——一次测试就否掉整组。最受欢迎的盒子是轴对齐包围盒（AABB），用slab（板）法测：一个 AABB 是三块“板”的交（每轴一块，夹在一个 min 面与 max 面之间）；把光线与每块板求交得到一个 [t_{near}, t_{far}] 区间，当且仅当三个区间重叠——即 max(t_{near}) ≤ min(t_{far})——光线命中盒子。它只是几次减、乘和 min/max——没有平方根。

// Ray–AABB slab test over the ray's current acceptance interval.
function hitAABB(o, d, box, rayTMin, rayTMax){
  var tmin = rayTMin, tmax = rayTMax;
  for (var a = 0; a < 3; a++){          // three axes / three slabs
    if (Math.abs(d[a]) < 1e-15){         // parallel: origin must lie in slab
      if (o[a] < box.min[a] || o[a] > box.max[a]) return false;
      continue;
    }
    var t1 = (box.min[a] - o[a]) / d[a];
    var t2 = (box.max[a] - o[a]) / d[a];
    if (t1 > t2){ var tmp = t1; t1 = t2; t2 = tmp; }  // order near/far
    tmin = Math.max(tmin, t1);
    tmax = Math.min(tmax, t2);
    if (tmax < tmin) return false;
  }
  return true;
}

One box helps a little; a tree of boxes is the win. A Bounding Volume Hierarchy (BVH) is a binary tree whose every node stores an AABB enclosing all primitives beneath it; leaves hold a few actual primitives. To trace a ray: test the root box; visit children in near-first order; if a box is missed—or begins beyond the closest hit already found—prune its entire subtree. A balanced tree has depth O(\log N), but that is not the same as saying every ray costs O(\log N): overlapping boxes, a ray crossing many leaves, or a degenerate build can force O(N) node/primitive work. The useful claim is empirical and distribution-dependent: a well-built BVH usually prunes most geometry, often making ordinary rays near-logarithmic rather than linear. SAH is valuable precisely because traversal cost depends on ray and scene geometry, not tree depth alone.

一个盒子帮不上多少；一棵盒子树才是胜负手。包围体层次结构（BVH）是一棵二叉树，每个节点存一个包住其下方所有图元的 AABB；叶子里放几个真实图元。追一条光线：测根盒子；按由近到远访问孩子；错过某盒，或盒子的起点已远于当前最近命中，就剪掉它整棵子树。平衡树的深度是 O(\log N)，但这不等于每条光线都只花 O(\log N)：盒子大量重叠、光线穿过许多叶子或构建退化时，节点/图元工作仍会达到 O(N)。真正有用的是一个依赖分布的经验结论：建得好的 BVH 通常能剪掉绝大多数几何，让普通光线常常接近对数而不是线性。SAH 之所以重要，正因为遍历开销取决于光线与场景几何，而不只取决于树深。

BVH: why a ray needn't test every objectBVH：为什么一条光线不必测试每个物体

24 fixed circles, deterministically placed and partitioned into four AABBs (a 2-level BVH: a root box over four leaf boxes). Aim the ray with the sliders. In BRUTE FORCE every circle is tested — all 24 light up. In BVH the ray first runs the slab test on each box; only circles inside boxes the ray actually enters get tested (highlighted), the rest are pruned (dimmed). The nearest hit is ringed. Watch the two test counts: BVH ≪ brute, and the harder the scene, the wider the gap.24 个固定圆，确定性地摆放并划入四个 AABB（一棵两层 BVH：一个根盒罩住四个叶盒）。用滑块瞄准光线。在暴力模式下每个圆都被测试——全部 24 个亮起。在 BVH 模式下，光线先对每个盒子跑 slab 测试；只有落在光线真正进入的盒子里的圆才被测试（高亮），其余被剪除（变暗）。最近命中被圈出。看这两个测试计数：BVH ≪ 暴力，且场景越难，差距越大。

ray angle光线角度: 8° ray origin y光线原点 y: 180

Brute tests

—

BVH tests

—

Boxes entered

—

Nearest hit?

—

Show the core JS查看核心 JS

// BVH trace: box test gates the circle tests. box test is cheap; circle test isn't.
var tests = 0, boxesEntered = 0, best = Infinity, hit = null, tMin = 1e-6;
for (var b = 0; b < boxes.length; b++){
  if (!hitAABB(o, invd, boxes[b])) continue;   // MISS box -> prune all its circles
  boxesEntered++;
  for (var k = 0; k < boxes[b].items.length; k++){
    tests++;                                    // only now do the expensive test
    var t = hitCircle(o, d, circles[boxes[b].items[k]]);
    if (t >= tMin && t < best){ best = t; hit = boxes[b].items[k]; }
  }
}
// BRUTE FORCE for comparison: test all N circles, no boxes.
var bruteTests = circles.length;               // always N

How you build the tree matters. A BVH is built top-down: take a set of primitives, pick an axis and a split position, partition into two child sets, recurse. The cheap heuristic is a median split — sort along the longest axis, cut at the middle primitive. It is fast to build and gives a balanced tree, but ignores geometry: it can produce fat, overlapping boxes that a ray enters often. The quality heuristic is the Surface Area Heuristic (SAH), which estimates the expected cost of a split as P(\text{hit left})·N_L + P(\text{hit right})·N_R, using the fact that the probability a random ray hits a child box is proportional to its surface area. SAH tries many candidate splits and keeps the cheapest; it builds slower but produces trees that trace markedly faster — the standard trade for offline renderers.

树怎么建，很要紧。BVH 自顶向下建：取一组图元，选一条轴和一个分割位置，划成两个孩子集合，递归。廉价的启发式是中位数分割——沿最长轴排序，从中间那个图元切开。建得快、给出平衡树，但忽略几何：它可能产出又胖又重叠的盒子，光线常常一进就进俩。高质量的启发式是表面积启发式（SAH），它把一次分割的期望开销估为 P(\text{命中左})·N_L + P(\text{命中右})·N_R，用到“随机光线命中某个孩子盒的概率正比于其表面积”这一事实。SAH 试许多候选分割、保留最便宜的；它建得慢，却产出追踪明显更快的树——离线渲染器的标准取舍。

Not the only structure. A kd-tree splits space with axis-aligned planes (tight cells, pricier build, and a primitive can straddle two cells); a uniform grid buckets primitives into equal voxels and marches the ray cell-by-cell (great for evenly-spread scenes, bad for a few dense clumps — the "teapot in a stadium" problem). The BVH's virtue is that it partitions objects, not space, so boxes shrink to fit geometry and it copes with wildly non-uniform density. And the whole descend-a-tree-of-boxes dance is now baked into silicon: modern GPU RT cores do BVH traversal and ray–triangle tests in hardware, which is what makes real-time ray tracing possible — we return to that convergence in lesson 15.

并非唯一结构。kd-tree 用轴对齐平面切空间（格子更紧、建得更贵，且一个图元可能横跨两格）；均匀网格把图元分进等大体素、让光线逐格前进（对均匀铺开的场景极好，对少数密集团块很糟——即“体育场里的茶壶”问题）。BVH 的长处在于它划分的是物体而非空间，所以盒子会收缩去贴合几何，也能应付极不均匀的密度。而这整套“下降一棵盒子树”的舞步如今已刻进硅片：现代 GPU 的 RT 核心用硬件做 BVH 遍历与光线–三角形测试，这正是实时光线追踪成为可能的原因——我们在第 15 课再回到这场融合。

Structure	Partitions	Build cost	Best for
BVH (median split)	objects	cheap, fast	dynamic scenes, quick rebuilds
BVH (SAH)	objects	expensive	offline, trace-time wins
kd-tree	space (planes)	expensive	tight static scenes
Uniform grid	space (voxels)	very cheap	evenly-spread geometry

结构	划分对象	构建开销	擅长
BVH（中位数分割）	物体	便宜、快	动态场景、快速重建
BVH（SAH）	物体	昂贵	离线、追踪期取胜
kd-tree	空间（平面）	昂贵	紧凑的静态场景
均匀网格	空间（体素）	极便宜	均匀铺开的几何

Where this points next接下来指向何处

We now have a working ray tracer: rays as r(t)=o+t·d, closed-form intersection for spheres and triangles, the Whitted recursion for shadows/reflections/refractions, and a BVH that makes the inner loop affordable. But Whitted's tracer casts exactly one reflection ray, one refraction ray, one shadow ray per light — it captures mirror-perfect reflection and hard, point-light shadows, and nothing softer. Real materials scatter light over a whole lobe (lesson 09's BRDF), real lights have area (soft shadows), and the rendering equation of lesson 01 was an integral over the hemisphere, not a single direction. Lesson 11 replaces the one ray with many random rays and averages them — Monte Carlo path tracing — turning this recursive tracer into an unbiased estimator of the full equation. Every ray it fires still rides on exactly the intersection machinery and BVH built here.

现在我们有了一台能用的光线追踪器：光线 r(t)=o+t·d，球与三角形的闭式求交，处理阴影/反射/折射的 Whitted 递归，以及让内层循环负担得起的 BVH。但 Whitted 追踪器恰好只投一条反射光线、一条折射光线、每光源一条阴影光线——它捕捉镜面般完美的反射与硬的点光源阴影，仅此而已，再柔一点都没有。真实材质把光散射到整个波瓣上（第 09 课的 BRDF），真实光源有面积（软阴影），而第 01 课的渲染方程是半球上的一个积分、不是单一方向。第 11 课把那一条光线换成许多条随机光线并求平均——蒙特卡洛路径追踪——把这台递归追踪器变成对完整方程的无偏估计器。它发出的每一条光线，仍然完全跑在这里搭起的求交机制与 BVH 之上。

Takeaway要点

A ray is r(t) = o + t·d over [t_min,t_max]; ray tracing casts one primary ray per pixel (lesson 02's camera, run backwards). Intersection is closed-form: ray–sphere is a quadratic and ray–triangle is Möller–Trumbore; the nearest valid t is visible. Secondary rays need scale-aware offsets along the geometric normal, while the shading normal controls appearance; refraction also needs the current medium / IOR stack. The Whitted recursion casts shadow, reflection, and refraction rays weighted by Fresnel; a hard depth cap makes it finite but introduces truncation bias. Naive tracing is O(N) per ray, O(P·N) per frame. A BVH uses AABB slab tests to prune subtrees. A good build makes typical traversal dramatically sublinear and often near-logarithmic, but the worst case remains O(N). Median splits favor build speed; SAH spends more work to reduce expected trace cost; RT cores accelerate traversal and intersection in hardware.

光线是定义在 [t_min,t_max] 上的 r(t) = o + t·d；光线追踪每像素投一条主光线（第 02 课的相机倒着跑）。求交是闭式的：光线–球是二次方程，光线–三角形用 Möller–Trumbore；最小的有效 t 可见。次级光线要沿几何法线做尺度感知的偏移，而着色法线控制外观；折射还需当前介质 / IOR 栈。Whitted 递归投出由 Fresnel 加权的阴影、反射与折射光线；硬深度上限让它有限，却引入截断偏差。朴素追踪每光线 O(N)、每帧 O(P·N)。BVH 用 AABB slab 测试剪掉子树。好的构建能让典型遍历显著次线性、常接近对数，但最坏仍是 O(N)。中位数分割偏向构建速度；SAH 多花构建功夫以降低期望追踪开销；RT 核心则用硬件加速遍历与求交。

Interview prompts面试题

Derive the ray–sphere intersection and say what the discriminant's sign means. (§2 — substitute o+t·d into |p−c|²=R² → quadratic in t; discriminant <0 miss, =0 tangent, >0 two roots — keep the smallest root inside the ray interval.) 推导光线–球求交，并说明判别式的符号各代表什么。(§2 — 把 o+t·d 代入 |p−c|²=R² → 关于 t 的二次方程；判别式 <0 错过、=0 相切、>0 两根——取光线区间内最小的根。)
In Möller–Trumbore, what conditions on u, v, t make a hit valid, and why are barycentrics a bonus? (§2 — u ≥ 0, v ≥ 0, u+v ≤ 1 (inside), t ∈ [t_min,t_max]; the same u,v interpolate per-vertex normals/UVs/colors for free.) 在 Möller–Trumbore 中，u, v, t 满足什么条件命中才有效？为什么重心坐标是额外红利？(§2 — u ≥ 0, v ≥ 0, u+v ≤ 1（在内）、t ∈ [t_min,t_max]；同一组 u,v 免费插值逐顶点法线/UV/颜色。)
Name the three Whitted ray types and explain the depth-cap trade-off. (§3 — shadow (toward each light → hard shadows), reflection (mirror), refraction (Snell); Fresnel weights reflect/refract; a cap guarantees finite work but discards deeper transport and is biased.) 说出 Whitted 的三种光线类型，并解释深度上限的取舍。(§3 — 阴影（射向每个光源 → 硬阴影）、反射（镜面）、折射（斯涅尔）；Fresnel 给反射/折射加权；上限保证有限开销，却丢弃更深传输并引入偏差。)
Why is naive ray tracing O(P·N), and give order-of-magnitude numbers. (§4 — O(N) tests per ray × P pixels; e.g. 1080p (~2×10⁶ px) over 10⁶ triangles ≈ 2×10¹² tests per frame for primary rays alone.) 为什么朴素光线追踪是 O(P·N)？给出数量级估计。(§4 — 每光线 O(N) 次测试 × P 个像素；例如 1080p（约 2×10⁶ 像素）面对 10⁶ 三角形，仅主光线每帧就约 2×10¹² 次测试。)
Why is BVH traversal often near-logarithmic yet O(N) in the worst case, and what is the slab test's role? (§5 — a balanced tree has logarithmic depth, but overlapping boxes or a ray crossing many leaves can visit the whole tree; the cheap ray–AABB interval test gates descent and prunes a missed or farther subtree.) 为何 BVH 遍历常接近对数、最坏却仍是 O(N)？slab 测试起什么作用？(§5 — 平衡树深度为对数，但盒子重叠或光线穿过许多叶子时仍可能访问整棵树；廉价的光线–AABB 区间测试门控下降，并剪掉错过或更远的子树。)
Median split vs SAH — what does each optimize, and when do you pick which? (§5 — median split cuts at the middle primitive: fast build, balanced but geometry-blind; SAH minimizes expected traversal cost P·N_L + P·N_R via surface-area probabilities: slower build, faster trace — pick SAH offline, median split for fast dynamic rebuilds.) 中位数分割 vs SAH——各自优化什么，何时选哪个？(§5 — 中位数分割从中间图元切开：建得快、平衡但对几何盲；SAH 用表面积概率最小化期望遍历开销 P·N_L + P·N_R：建得慢、追踪快——离线选 SAH，需快速动态重建时选中位数分割。)