Deel door diepte voor direct 3D

Toen ik begon met het maken van games, gebruikte ik frameworks op hoog niveau die een Camera leverden die gewoon werkte. Maar naarmate ik meer leerde en creatievere technieken wilde toepassen, merkte ik dat ik niet eens de juiste termen kende om te zoeken naar wat ik wilde doen. Pas nadat ik graphics-code op een lager niveau had geschreven, begreep ik dat camera's gebaseerd zijn op zeer eenvoudige wiskunde.

In het uitstekende artikel One Formula That Demystifies 3D Graphics (via @tsoding) wordt het volgende gepresenteerd:

$(x, y, z)$ $x' = x/z$ $y' = y/z$

In essentie: als we zeggen dat $y$ omhoog is en $z$ vooruit, kunnen 3D-coördinaten $(x, y, z)$ worden geprojecteerd naar 2D-coördinaten $(x', y')$ door $x$ en $y$ te delen door $z$. Bijvoorbeeld, als we een reeks 3D-punten hebben die alleen variëren in diepte, komen hun geprojecteerde posities dichter bij het verdwijnpunt $(0,0)$ naarmate de diepte toeneemt:

Dit kan worden gedemonstreerd door een bal die beweegt en schaalt met de diepte terwijl hij om de op-as van de camera draait, verschoven langs de $z$-as door 'forward':

const float forward = 2.0;
vec3 camera_pos = vec3(sin(iTime), 0., cos(iTime) + forward);
vec2 projected_pos = camera_pos.xy / camera_pos.z;
float radius = 0.5 / camera_pos.z;

void mainImage(out vec4 c, vec2 p) {
    vec2 uv = (p * 2.0 - iResolution.xy) / iResolution.y;

    const float forward = 2.0;
    vec3 camera_pos = vec3(sin(iTime), 0., cos(iTime) + forward);
    vec2 projected_pos = camera_pos.xy / camera_pos.z;
    float radius = 0.5 / camera_pos.z;

    c = iForeground * step(length(uv - projected_pos), radius);
}

Met hetzelfde principe kunnen we zelfs complexere "geometrie" op dezelfde manier tekenen:

float sdSegment(vec2 point, vec2 start, vec2 end) {
    vec2 offset = point - start;
    vec2 segment = end - start;
    float along = clamp(dot(offset, segment) / max(dot(segment, segment), 1e-8), 0.0, 1.0);
    return length(offset - segment * along);
}

float line(vec2 point, vec2 start, vec2 end) {
    float width = fwidth(point.y) * 1.5;
    return smoothstep(width, 0.0, sdSegment(point, start, end));
}

void mainImage(out vec4 fragColor, in vec2 fragCoord) {
    vec2 uv = (fragCoord * 2.0 - iResolution.xy) / iResolution.y;

    const vec3 c[8] = vec3[](
        vec3(-1., -1., -1.), vec3(-1., -1., 1.),
        vec3(-1., 1., -1.), vec3(-1., 1., 1.),
        vec3(1., -1., -1.), vec3(1., -1., 1.),
        vec3(1., 1., -1.), vec3(1., 1., 1.)
    );

    const ivec2 e[12] = ivec2[](
        ivec2(0, 1), ivec2(0, 2), ivec2(0, 4), ivec2(1, 3),
        ivec2(1, 5), ivec2(2, 3), ivec2(2, 6), ivec2(3, 7),
        ivec2(4, 5), ivec2(4, 6), ivec2(5, 7), ivec2(6, 7)
    );

    mat3 r = mat3(
        cos(iTime), 0., sin(iTime),
        0., 1., 0.,
        -sin(iTime), 0., cos(iTime)
    );

    const vec3 fwd = vec3(0.0, 0.0, 1.0);
    const float z = 2.5;
    float d = 0.0;

    for (int i = 0; i < 12; i++) {
        vec3 a = r * c[e[i].x] + fwd * z, b = r * c[e[i].y] + fwd * z;
        d = max(d, line(uv, a.xy / a.z, b.xy / b.z));
    }

    fragColor = iForeground * d;
}

Natuurlijk zijn dit zeer beperkte en naïeve voorbeelden die in bijna alle gevallen onpraktisch zijn. Bij elk serieus 3D-werk moeten we rekening houden met zaken als de richting waarin de camera wijst, de positie, het gezichtsveld (field of view), enzovoort. Hoewel we deze shaders theoretisch zouden kunnen aanpassen om deze functies te ondersteunen, is er een manier die minder moeite kost en praktischer is: de perspectivische projectiematrix. Dit is de magie achter de krachtige Camera.

Perspectivische Projectie

Er zijn verschillende manieren om een perspectivische projectiematrix te construeren, afhankelijk van het gebruiksscenario. Computer vision en computergraphics hebben bijvoorbeeld verschillende conventies voor de lay-out, wat het lastig maakt om naar één enkel Wikipedia-artikel te verwijzen voor een universele vorm.

In graphics gebaseerd op driehoeken is een veelvoorkomende conventie de parametrisering van het gezichtsveld (FOV), de beeldverhouding (aspect ratio) en de nabije en verre clipping-vlakken (near and far clipping planes). Deze waarden zijn essentieel omdat ze ook dienen als een manier om eenvoudig te bepalen wat er in beeld is en wat niet. Dit stelt ons in staat om scènes efficiënt te renderen, bijvoorbeeld door geometrie buiten het scherm weg te laten (culling).

Hoewel dit varieert per coördinatenconventie (er is weinig consensus over welke assen overeenkomen met boven, rechts en vooruit), is de algemene structuur grotendeels consistent:

\[P = \begin{bmatrix} \frac{f}{a} & 0 & 0 & 0 \\ 0 & f & 0 & 0 \\ 0 & 0 & A & B \\ 0 & 0 & 1 & 0 \end{bmatrix}\]

Dit beschrijft een camera met een focale schaal $f$ (afgeleid van de verticale FOV-hoek $\theta$) en een beeldverhouding $a$:

\[f = \frac{1}{\tan(\theta/2)},\quad a = \frac{width}{height}\]

Hierbij vertegenwoordigen $A$ en $B$ de dieptemapping, afgeleid van respectievelijk het nabije clipping-vlak $n$ en het verre clipping-vlak $F$:

\[A = \frac{F+n}{F-n}, \quad B = -\frac{2Fn}{F-n}\]

float sdSegment(vec2 p, vec2 a, vec2 b) {
    vec2 pa = p - a, ba = b - a;
    float h = clamp(dot(pa, ba) / max(dot(ba, ba), 1e-8), 0.0, 1.0);
    return length(pa - ba * h);
}

vec2 project(mat4 m, vec3 p) {
    vec4 q = m * vec4(p, 1.0);
    return q.xy / q.w;
}

vec2 iso(vec3 p, float s) {
    return vec2(dot(p, normalize(vec3(1., 0., 1.))),
                dot(p, normalize(vec3(-.5, 1., .5)))) * s;
}

vec3 frustumPoint(vec3 c, vec3 near, vec3 far) {
    vec3 s = mix(near, far, c.z);
    return vec3(c.xy * s.xy, s.z);
}

void mainImage(out vec4 fragColor, in vec2 fragCoord) {
    vec2 uv = (fragCoord * 2.0 - iResolution.xy) / iResolution.y;

    const float fov = 60.0;
    const float aspect = 0.8;
    const float nearClip = 1.0;
    const float farClip = 5.0;
    const float z = 3.5;

    float t = tan(radians(fov) * 0.5);
    float screenAspect = iResolution.x / iResolution.y;
    float s = 1.65 / (8.0 * max(t * aspect, 1.0));

    float f = 1.0 / tan(radians(fov) * 0.5);
    mat4 p = mat4(
        f / aspect, 0., 0., 0.,
        0., f, 0., 0.,
        0., 0., (farClip + nearClip) / (farClip - nearClip), 1.,
        0., 0., -2. * farClip * nearClip / (farClip - nearClip), 0.
    );

    const vec3 c[8] = vec3[](
        vec3(-1., -1., 0.), vec3(1., -1., 0.),
        vec3(-1., 1., 0.), vec3(1., 1., 0.),
        vec3(-1., -1., 1.), vec3(1., -1., 1.),
        vec3(-1., 1., 1.), vec3(1., 1., 1.)
    );

    const ivec2 e[12] = ivec2[](
        ivec2(0, 1), ivec2(0, 2), ivec2(1, 3), ivec2(2, 3),
        ivec2(4, 5), ivec2(4, 6), ivec2(5, 7), ivec2(6, 7),
        ivec2(0, 4), ivec2(1, 5), ivec2(2, 6), ivec2(3, 7)
    );

    vec3 n = vec3(nearClip * t * aspect, nearClip * t, nearClip);
    vec3 F = vec3(farClip * t * aspect, farClip * t, farClip);
    vec3 ball = vec3(sin(iTime), 0.0, z + cos(iTime));
    const float ballRadius = 0.35;

    vec4 clip = p * vec4(ball, 1.0);
    vec3 q = clip.xyz / clip.w;
    float visible = step(-1.0, q.z) * step(q.z, 1.0);

    bool diagram = uv.x < 0.0;
    vec2 lo = vec2(1e6), hi = -lo;
    for (int i = 0; i < 8; i++) {
        vec2 corner = iso(frustumPoint(c[i], n, F), s);
        lo = min(lo, corner); hi = max(hi, corner);
    }

    vec2 offset = vec2(-screenAspect * 0.5, 0.0) - (lo + hi) * 0.5;
    vec2 viewport = vec2(screenAspect * 0.5, 0.0);
    vec2 size = 0.72 * vec2(aspect, 1.0) / max(aspect, 1.0);

    float d = 0.0;
    for (int i = 0; i < 12; i++) {
        vec3 a = frustumPoint(c[e[i].x], n, F), b = frustumPoint(c[e[i].y], n, F);
        vec2 pa = diagram ? iso(a, s) + offset : viewport + project(p, a) * size;
        vec2 pb = diagram ? iso(b, s) + offset : viewport + project(p, b) * size;
        float opacity = diagram ? mix(1.0, 0.4, (a.z + b.z) * 0.5 / farClip) : 0.25;
        d = max(d, smoothstep(fwidth(uv.y) * 1.5, 0.0, sdSegment(uv, pa, pb)) * opacity);
    }

    float w = fwidth(uv.y) * 1.5;
    if (diagram) {
        vec2 center = iso(ball, s) + offset;
        float radius = length(iso(ball + vec3(ballRadius, 0., 0.), s) - iso(ball, s));
        float outline = smoothstep(w * 1.5, w, abs(length(uv - center) - radius));
        d = max(d, mix(outline, smoothstep(radius + w, radius, length(uv - center)), visible));
    } else {
        vec2 center = viewport + q.xy * size;
        float radius = length((project(p, ball + vec3(ballRadius, 0., 0.)) - q.xy) * size);
        d = max(d, smoothstep(radius + w, radius, length(uv - center)) * visible);
    }

    d = max(d, (1.0 - smoothstep(0.0, fwidth(uv.x), abs(uv.x))) * 0.2);
    fragColor = iForeground * d;
}

De verbinding met de dieptedeling

Hoe hangt dit samen met de dieptedeling-truc van eerder? Het blijkt dat die truc een speciale vorm is van de perspectivische projectiematrix.

Gegeven een punt ergens in de 3D-ruimte, beschrijven we eerst de positie ten opzichte van de camera. Dit brengt ons van de world space (wereldruimte), waar coördinaten gedeeld worden door de hele scène, naar de view space (view-ruimte), waar de camera zich op de oorsprong bevindt. Vervolgens vermenigvuldigen we dit met de perspectivische projectiematrix, wat resulteert in clip-space coördinaten die klaar zijn voor de perspectivische deling.

\[\begin{bmatrix} \frac{f}{a} & 0 & 0 & 0 \\ 0 & f & 0 & 0 \\ 0 & 0 & A & B \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix} = \begin{bmatrix} \frac{f}{a}x + 0y + 0z + 0(1) \\ 0x + fy + 0z + 0(1) \\ 0x + 0y + Az + B(1) \\ 0x + 0y + z + 0(1) \end{bmatrix} = \begin{bmatrix} \frac{f}{a}x \\ fy \\ Az + B \\ z \end{bmatrix}\]

Waar is die extra 1 voor?

Een 4x4 matrix verwacht viercomponenten homogene coördinaten voor vermenigvuldiging. Voor elke niet-nul $w$ vertegenwoordigt de vector $(x,y,z,w)$ het 3D-punt $(x/w,y/w,z/w)$. Door $(x,y,z,1)$ te schrijven, behouden we het punt waar we mee begonnen. Als we $w=0$ stellen, vertegenwoordigt dit in plaats daarvan een richting, waardoor het niet beïnvloed wordt door translatie.

Na het delen van de eerste drie clip-space componenten door $w$, beschrijven de coördinaten niet langer afstanden in de scène. In plaats daarvan beschrijven ze waar het punt valt binnen de zichtbare grenzen van de camera. Dit zijn de Normalized Device Coordinates (NDC), die later in staat maken om punten uiteindelijk te mappen naar de output-resolutie van het scherm.

\[x{ndc} = \frac{\frac{f}{a}x}{z}, \qquad y{ndc} = \frac{fy}{z}\]

In het eerdere voorbeeld werden zowel de focale schaal $f$ als de beeldverhouding $a$ weggelaten. Als we deze beide vervangen door 1, komen we exact uit bij de oorspronkelijke dieptedeling-truc:

\[x{ndc} = \frac{\frac{1}{1}x}{z} = \frac{x}{z}, \qquad y{ndc} = \frac{1y}{z} = \frac{y}{z}\]

Hoewel de dieptedeling-truc werkt voor camera-relatieve punten in eenvoudige scenario's, is het in feite slechts één stap in de volledige graphics-pipeline:

$\mathrm{world} \rightarrow \mathrm{view} \rightarrow \mathrm{clip} \xrightarrow{\,/w\,} \mathrm{NDC} \rightarrow \mathrm{pixels} \rightarrow \mathrm{rasterization}$

Alles samenbrengen

De belangrijkste conclusie van dit betoog is dat camera's simpelweg een paar eenvoudige transformaties uitvoeren. Als je begrijpt waar elke transformatie voor dient, kun je zelf kiezen welke delen je implementeert op basis van je eigen behoeften en beperkingen. Soms heb je de volledige pipeline nodig, en soms is die ene dieptedeling voldoende.