graphics(1) - hachem.wtf

name

graphics - the pipeline, rasterization, raycasting, bsp, and raytracing

synopsis

graphics [--pipeline-spaces] [--projection] [--rasterization] [--raycasting-wolfenstein-3d] [--bsp-doom-2-5-d] [--raytracing]

description

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.

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

author

hachem <im@hachem.wtf>