graphics

the rendering math i look up mid-implementation. wolf3d is raycasting (grid dda), doom is bsp (2.5-d), and true raytracing gets its own section. all three are below.

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

pipeline & spaces

• the viewport maps $x_s = (\tfrac12 x_\text{ndc} + \tfrac12)\,W$ and $y_s = \big(1 - (\tfrac12 y_\text{ndc} + \tfrac12)\big)\,H$ (flipping y)
• the bugs live in the conventions, so pin them down. that's row- vs column-major, pre- vs post-multiply, lh vs rh, and the clip-z range ($[-1,1]$ in gl, $[0,1]$ in d3d/vk/metal)

projection

perspective, right-handed, clip $z\in[-1,1]$, with $c = \cot(\text{fovy}/2)$, aspect $a$, near $n$, and far $f$.

\begin{pmatrix}
c/a & 0 & 0 & 0 \\
0 & c & 0 & 0 \\
0 & 0 & \frac{f+n}{n-f} & \frac{2fn}{n-f} \\
0 & 0 & -1 & 0
\end{pmatrix}

• the $-1$ row makes $w = -z_\text{eye}$, so the divide carries eye-space depth
• depth is nonlinear ($z_\text{ndc}\propto 1/z_\text{eye}$), so precision bunches up near $n$. a float + reversed-z buffer gets it back
• for d3d/vk, clip $z\in[0,1]$ and the third row changes to $\frac{f}{f-n}$ and $-\frac{fn}{f-n}$

rasterization

• the edge function is $E(\mathbf{a},\mathbf{b},\mathbf{p}) = (p_x - a_x)(b_y - a_y) - (p_y - a_y)(b_x - a_x)$, and its sign says which side of $ab$ the point $\mathbf{p}$ is on
• barycentrics are $(\lambda_0,\lambda_1,\lambda_2) = (E_{bc}, E_{ca}, E_{ab})/(2\cdot\text{area})$, and $\mathbf{P} = \lambda_0\mathbf{A} + \lambda_1\mathbf{B} + \lambda_2\mathbf{C}$
• the top-left rule counts an edge pixel only on top or left edges, so shared edges don't get shaded twice
• for perspective-correct interpolation, lerp $\text{attr}/w$ and $1/w$ linearly in screen space, then $\text{attr} = \operatorname{lerp}(\text{attr}/w)\,/\,\operatorname{lerp}(1/w)$. lerping attr directly is affine and wrong (the classic warped-texture bug)

raycasting (wolfenstein 3d)

for each screen column $x$, $\text{cameraX} = 2x/W - 1$ and $\text{rayDir} = \text{dir} + \text{plane}\cdot\text{cameraX}$, where dir is forward and plane $\perp$ dir with $|\text{plane}| = \tan(\text{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 (projected onto the camera direction) and never the ray length, since euclidean distance gives you the fisheye warp
• the wall column height is $H/\text{perpDist}$, drawn centered on the horizon
• texX comes from the fractional hit along the wall, and $\text{texStep} = \text{texH}/\text{wallH}$

bsp / doom (2.5-d)

• walls are vertical only and sectors carry floor and ceiling heights, so there's no room-over-room
• the bsp tree splits the map along linedefs. traverse it front to back from the camera and you get exact occlusion with no z-buffer
• for occlusion, keep a per-column clip list (solidsegs), and each wall seg only fills the column spans that are still open
• walls are $1/z$-linear across the screen, so $\text{scale} = \text{focalLen}/\text{dist}$ per column, and texture $v$ steps linearly down the column
• floors and ceilings are visplanes drawn as horizontal spans, and since their height is constant, each row maps to a single distance

raytracing

• with the ray $\mathbf{O} + t\mathbf{D}$ and a sphere with center $\mathbf{C}$ and radius $r$, $a = \mathbf{D}\cdot\mathbf{D}$, $b = 2\mathbf{D}\cdot(\mathbf{O}-\mathbf{C})$, $c = |\mathbf{O}-\mathbf{C}|^2 - r^2$, and $t = \frac{-b\pm\sqrt{b^2-4ac}}{2a}$
• for a triangle, use 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 > ε

• refract with $\eta = \eta_1/\eta_2$ and $\cos\theta_i = -\mathbf{D}\cdot\mathbf{n}$ (snell). $k = 1 - \eta^2(1 - \cos^2\theta_i)$, and if $k < 0$ that's total internal reflection, otherwise $\mathbf{T} = \eta\mathbf{D} + (\eta\cos\theta_i - \sqrt{k})\,\mathbf{n}$
• fresnel (schlick) is $R(\theta) = R_0 + (1 - R_0)(1 - \cos\theta)^5$, with $R_0 = \left(\frac{\eta_1-\eta_2}{\eta_1+\eta_2}\right)^2$
• the rendering equation is

L_o(\mathbf{x},\boldsymbol{\omega}_o) = L_e + \int_\Omega f_r(\mathbf{x},\boldsymbol{\omega}_i,\boldsymbol{\omega}_o)\,L_i(\mathbf{x},\boldsymbol{\omega}_i)\,(\boldsymbol{\omega}_i\cdot\mathbf{n})\,d\omega_i