graphics

the rendering math i look up mid-implementation. wolf3d is raycasting (grid DDA), doom is BSP (2.5-D), true raytracing is its own section --; all three below.

jump to: pipeline · projection · rasterization · raycasting · bsp / doom · raytracing

pipeline & spaces

• model →[M] world →[V] eye →[P] clip →(÷w) NDC →[viewport] screen
• clip = P·V·M·(x,y,z,1)ᵀ; NDC = clip.xyz / clip.w
• viewport: xₛ = (½·ndc.x + ½)·W; yₛ = (1 − (½·ndc.y + ½))·H (flip y)
• conventions to pin down (where the bugs live): row- vs column-major, pre- vs post-multiply, LH vs RH, and clip-z range — [−1,1] (GL) vs [0,1] (D3D/VK/Metal)

projection

perspective, right-handed, clip z ∈ [−1,1]; c = cot(fovy/2), a = aspect, near n, far f:

[ c/a   0    0              0            ]
[ 0     c    0              0            ]
[ 0     0   (f+n)/(n−f)    2fn/(n−f)     ]
[ 0     0   −1              0            ]

• the −1 row puts w = −z_eye, so the divide carries eye-space depth
• depth is nonlinear: z_ndc ∝ 1/z_eye, so precision bunches near n → use a float + reversed-Z buffer to reclaim it
• D3D/VK clip z ∈ [0,1]: the third row differs — f/(f−n) and −fn/(f−n)

rasterization

• edge function: E(a,b,p) = (p.x−a.x)(b.y−a.y) − (p.y−a.y)(b.x−a.x); its sign is which side of ab
• inside test: all three edge functions share the triangle's winding sign; 2·area = E(a,b,c)
• barycentrics: (λ₀,λ₁,λ₂) = (E_bc, E_ca, E_ab)/(2·area); P = λ₀A + λ₁B + λ₂C
• top-left rule: count an edge pixel only on top/left edges → shared edges don't double-shade
• perspective-correct interp: lerp attr/w and 1/w linearly in screen space, then attr = (attr/w)ₗₑᵣₚ / (1/w)ₗₑᵣₚ — lerping attr directly is affine-wrong (the classic warped-texture bug)
• backface cull: the sign of the screen-space signed area is the winding; drop the back-facing sign

raycasting (wolfenstein 3d)

per screen column x: cameraX = 2x/W − 1; rayDir = dir + plane·cameraX (dir = forward, plane ⟂ dir with |plane| = tan(fov/2)).

deltaDist.x = |1 / rayDir.x|              # dist between x grid lines
step, sideDist = initial cell + direction
loop:
    advance on the axis with the smaller sideDist
    sideDist[axis] += deltaDist[axis];  side = axis
until map[cell] is solid
perpDist = sideDist[side] − deltaDist[side]   # perpendicular, NOT euclidean

• use perpDist (project onto the camera direction), never the ray length — euclidean distance gives the fisheye warp
• wall column height = H / perpDist, drawn centered on the horizon
• texX from the fractional hit along the wall; texStep = texH / wallH

bsp / doom (2.5-d)

• vertical walls only, sectors carry floor/ceiling heights — no room-over-room
• BSP tree splits the map along linedefs; traverse front-to-back from the camera → exact occlusion with no z-buffer
• occlusion: keep a per-column clip list (solidsegs); each wall seg fills only still-open column spans
• walls are 1/z-linear across the screen → column scale = focalLen / dist; texture v steps linearly down the column
• floors/ceilings: visplanes drawn as horizontal spans (constant height ⇒ row maps to a distance)

raytracing

• ray: P(t) = O + tD, t > 0
• sphere (center C, radius r): a = D·D, b = 2D·(O−C), c = |O−C|² − r²; t = (−b ± √(b²−4ac)) / 2a
• plane (point p₀, normal n): t = (p₀−O)·n / (D·n)
• triangle — Möller–Trumbore:

e1 = v1−v0;  e2 = v2−v0
h = D × e2;   a = e1 · h           # |a| < ε  ⇒  ray ∥ triangle
f = 1/a;  s = O − v0
u = f (s · h);        miss if u < 0 or u > 1
q = s × e1
v = f (D · q);        miss if v < 0 or u+v > 1
t = f (e2 · q);       hit if t > ε

• reflect: R = D − 2(D·n)n
• refract (Snell, η = η₁/η₂, cosθᵢ = −D·n): k = 1 − η²(1 − cosθᵢ²); k < 0 ⇒ total internal reflection; else T = ηD + (η cosθᵢ − √k)n
• fresnel (schlick): R(θ) = R₀ + (1−R₀)(1−cosθ)⁵, with R₀ = ((η₁−η₂)/(η₁+η₂))²
• rendering equation: Lₒ(x,ωₒ) = Lₑ + ∫_Ω f_r(x,ωᵢ,ωₒ) Lᵢ(x,ωᵢ)(ωᵢ·n) dωᵢ