Botsingsdetectie is de meest natuurlijke game-dev-toepassing van signed distance fields. Het veld dat een vorm voor rendering beschrijft, beschrijft het ook voor contactquery’s: evalueer de SDF op elk punt en je krijgt twee antwoorden tegelijk, hoe ver het punt van het oppervlak is en aan welke kant het ligt. Dit artikel behandelt de drie querytypen die fysica-engines op dat contract bouwen (puntinsluiting, penetratiediepte met scheidingsrichting en sphere casting voor continue botsingsdetectie), met de GLSL-code, uitgewerkte voorbeelden, randgevallen en de prestatievergelijking met mesh-gebaseerde benaderingen.

Voor het overkoepelende beeld van SDF’s in de engine, zie SDF’s in game-ontwikkeling . Als de tekenconventie of het gradiëntconcept een opfrisser nodig heeft, bouwt het Signed Distance Fields overzicht beide op vanuit de eerste principes.

Het Querycontract

Drie feiten over een SDF $d(\mathbf{p})$ maken elke botsingsquery hieronder een zuivere rekenkundige expressie:

1. Teken: $d(\mathbf{p}) < 0$ betekent binnen, $> 0$ betekent buiten, $0$ betekent op het oppervlak.
2. Grootte: $|d(\mathbf{p})|$ is de afstand tot het dichtstbijzijnde oppervlak, exact voor analytische SDF’s, benaderd voor gesampelde.
3. Gradiënt: $\nabla d(\mathbf{p})$ wijst weg van het dichtstbijzijnde oppervlak, dus aan de grens is het de naar buiten gerichte normaal.

Geen van deze vereist het doorlopen van een boom of het testen van driehoekparen. De kost van een query is de kost van het evalueren van de veldeexpressie.

Punt-in-volume-query’s

De eenvoudigste botsingsvraag is of een punt binnen een volume ligt. Met een SDF is het antwoord een enkele tekencontrole:

bool isInside(vec3 point, SDF volume) {
    return evaluateSDF(point, volume) < 0.0;
}

Die ene regel vervangt wat anders een punt-in-mesh-test zou zijn die ray casting of winding-number-berekening vereist. Voor een bol-SDF kost de afstandsevaluatie één vectorsubtractie en één lengteberekening. Voor een complexe CSG-boom opgebouwd uit tientallen primitieven schaalt de kost met de boomdiepte, maar blijft het een zuivere rekenkundige expressie zonder vertakkende zoekstructuur.

Een uitgewerkt voorbeeld maakt de rekenkunde concreet. Neem een bol-SDF gecentreerd op de oorsprong met straal 2:

$$d(\mathbf{p}) = \|\mathbf{p}\| - 2$$

Test het punt $\mathbf{p} = (0.5, 1.0, 0)$. De afstand tot het middelpunt is $\sqrt{0.5^2 + 1.0^2} = \sqrt{1.25} \approx 1.118$. De SDF-waarde is $1.118 - 2 = -0.882$, dus het punt ligt binnen, en het bevindt zich 0.882 eenheden onder het oppervlak. Dezelfde query tegen een driehoeksmesh zou de dichtstbijzijnde driehoek moeten vinden en het dichtstbijzijnde punt daarop moeten berekenen, een veel duurdere operatie voor hetzelfde antwoord.

Penetratiediepte en Scheidingsrichting

Een binair binnen/buiten-antwoord is zelden genoeg voor een fysica-engine. Wanneer twee objecten overlappen, moet de solver weten hoe diep ze elkaar binnendringen en in welke richting ze uit elkaar moeten worden geduwd. De SDF levert beide.

Voor een punt $\mathbf{p}$ binnen een volume is de penetratiediepte $|d(\mathbf{p})|$ en de scheidingsrichting de genormaliseerde gradiënt $\nabla d(\mathbf{p})$ die naar het oppervlak wijst. Samen vormen ze de minimale translatievector $|d(\mathbf{p})| \cdot \hat{\nabla}d(\mathbf{p})$: verplaats het punt met die vector en het komt precies op het oppervlak terecht.

Verdergaand met het bolvoorbeeld: het punt $(0.5, 1.0, 0)$ heeft diepte 0.882 en gradiëntrichting $\mathbf{p}/\|\mathbf{p}\| = (0.447, 0.894, 0)$. Het punt 0.882 eenheden in die richting duwen geeft $(0.894, 1.789, 0)$, waarvan de afstand tot de oorsprong $\sqrt{0.799 + 3.201} = \sqrt{4.0} = 2.0$ is, precies de straal. De rekenkunde klopt: één query leverde zowel de overlaphoeveelheid als de correctie op.

In de praktijk sample je de SDF op elk hoekpunt van het binnendringende object en neem je de diepste penetratie:

struct PenetrationResult {
    float depth;
    vec3 direction;
    vec3 contactPoint;
};

PenetrationResult computePenetration(MeshVolume mesh, SDF volume) {
    PenetrationResult result;
    result.depth = 0.0;

    for (int i = 0; i < mesh.vertexCount; i++) {
        vec3 p = mesh.vertices[i];
        float d = evaluateSDF(p, volume);
        if (d < result.depth) {
            result.depth = d;
            result.direction = normalize(gradientSDF(p, volume));
            result.contactPoint = p;
        }
    }
    return result;
}

Omdat de SDF-gradiënt naar buiten wijst vanaf het oppervlak, duwt de scheidingsrichting het penetrerende punt van nature naar de dichtstbijzijnde grens.

De randgevallen zijn waar de benadering zorg vereist. Voor convexe volumes gedefinieerd door exacte SDF’s wijst het diepst penetrerende hoekpunt altijd in de juiste scheidingsrichting. Voor niet-convexe of gesampelde SDF’s kan sampling die alleen hoekpunten gebruikt dunne penetraties missen: een blok kan een niet-convex oppervlak binnendringen via een rand of vlak zonder dat een van zijn hoekpunten de grens overschrijdt. Een productiesolver voegt daarom rand-rand- en vlak-hoekpunt-sampling toe, en bij gesampelde velden behandelt hij de geïnterpoleerde afstand als benadering, vertrouwend op een kleine veiligheidsmarge zodat de solver niet trilt op ruizige waarden. Extra punten samplen vermenigvuldigt de querykost, daarom is de constante-tijd-eigenschap per evaluatie zo belangrijk: je kunt je meerdere samples per object veroorloven wanneer elke sample een grid-lookup is.

Sphere Casting voor Continue Botsingsdetectie

Snel bewegende objecten kunnen tussen frames door dunne geometrie tunnelen wanneer je discrete botsingscontroles gebruikt. Een kogel die 50 eenheden per frame beweegt tegen een muur van 0,1 eenheden dik kan aan het begin van het frame aan de ene kant zitten en aan het einde aan de andere, zonder dat een discrete test de overlap ooit ziet. De standaardoplossing is continue botsingsdetectie (CCD), die een volume langs het bewegingspad veegt en het vroegste tijdstip van impact vindt.

Met een SDF kun je CCD implementeren met sphere casting. Het idee is om een punt langs de bewegingsvector te marcheren met het afstandsveld als stapgrootte, precies zoals sphere tracing maar langs een verplaatsingsvector in plaats van een zichtstraal:

float sphereCast(vec3 origin, vec3 direction, float maxDist, float radius,
                 SDF volume) {
    float t = 0.0;
    for (int i = 0; i < MAX_STEPS; i++) {
        vec3 p = origin + direction * t;
        float d = evaluateSDF(p, volume) - radius;
        if (d < EPSILON) return t;  // Hit
        t += d;
        if (t > maxDist) break;  // No hit within the motion segment
    }
    return -1.0;  // No hit
}

De aanroeper geeft de verplaatsingslengte van het frame door als maxDist en een eenheidsbewegingsrichting als direction. De teruggegeven t is de hitsafstand langs die richting, en t / maxDist is de tijd van het eerste contact als een fractie van de framebeweging, die de fysica-engine gebruikt om het object precies op het botsingsoppervlak te stoppen.

Twee details doen ertoe. Het aftrekken van de straal van het bewegende object van de veldwaarde krimpt de vorm waarin wordt geveegd: de cast behandelt het wereldoppervlak alsof het met de straal van het projectiel is opgeblazen, wat precies het oppervlak is waarmee het middelpunt van het projectiel botst. En de stapgarantie geldt omdat de SDF afstand nooit overschat, dus geen enkele stap kan over een oppervlak springen.

Een uitgewerkt voorbeeld: een projectiel met straal 0,25 start op $(4, 0, 0)$ en beweegt in richting $(-1, 0, 0)$ naar een bol met straal 1 gecentreerd op de oorsprong, met maxDist = 4. Op $t = 0$ is de veldwaarde $\|(4, 0, 0)\| - 1 - 0.25 = 2.75$, dus de cast stapt naar $t = 2.75$. Op die positie, $(1.25, 0, 0)$, is de waarde $1.25 - 1 - 0.25 = 0$, en meldt de cast een hit op $t = 2.75$. Het analytische antwoord is $4 - 1 - 0.25 = 2.75$, dus de cast vond het eerste contact exact, in één stap.

De randgevallen van sphere casting spiegelen die van sphere tracing. Als het veld een gesampelde of vereffende SDF is die de afstandsgarantie alleen benadert, kan de mars over dunne kenmerken schieten, dus houd je ofwel een conservatieve epsilon aan, begrens je het aantal stappen, of val je terug op een discrete test wanneer de cast geen hit meldt. Objecten die het frame al binnendringend beginnen (de veldwaarde is negatief bij de oorsprong) geven een onmiddellijke hit op $t = 0$, die de engine moet behandelen als een overlap om op te lossen, niet als een nieuw botsingsgebeurtenis.

Ray- en Capsule-casts

Sphere casting generaliseert naar andere geveegde vormen. Een ray cast is een sphere cast met straal nul, nuttig voor line-of-sight-controles en wapen-hitscan. Een capsule cast vervangt de mars vanaf een punt-oorsprong door een segment dat een vaste afstand tot een lijn aanhoudt, wat vereist dat je de SDF op de eindpunten van het segment samplest en het minimum neemt, of een capsule-SDF direct gebruikt voor het geveegde volume. Dezelfde veilige-staplus werkt in elk geval; alleen de afstandsquery binnen de lus verandert. Deze uniformiteit is een praktische winst: één castlus, veel querytypen, geen nieuwe botsingsstructuren.

Prestatieprofiel

SDF-botsingsquery’s schalen anders dan traditionele benaderingen. Een mesh-tegen-mesh-botsingstest vereist het doorlopen van bounding volume hierarchies voor beide objecten en het testen van driehoekparen. Een SDF-tegen-mesh-test vervangt één hiërarchie door een constante-tijd afstandsevaluatie per hoekpunt van de andere vorm.

Dit maakt SDF’s bijzonder sterk voor scenario’s waarin één vorm eenvoudig is en de andere complex, of waarin veel objecten botsingsquery’s nodig hebben tegen dezelfde statische omgeving. Veel games bakken afstandsvelden voor statische levelgeometrie en query’en ze tijdens runtime tegen honderden dynamische objecten. De bakkosten worden eenmalig betaald tijdens het bouwen; de runtime-kosten zijn een handvol grid-lookups per query. Wanneer de omgeving statisch is, hoeft het veld nooit te worden bijgewerkt. Wanneer het verandert, is het herbouwen of lokaal bijwerken van het gebakken veld een aparte pijplijnkwestie, behandeld in voorgebakken signed distance fields .

SDF’s zijn niet het juiste gereedschap voor elk botsingspaar. Twee dichte dynamische meshes die met elkaar botsen blijven goedkoper als mesh-tegen-mesh, omdat het evalueren van een gesampeld veld voor beide vormen nog steeds grid-lookups en interpolatie kost terwijl het mesh-pad fixed-function hardware gebruikt. De sweet spot is één vaste, query-zware vorm (het level) tegen veel goedkope dynamische vormen (projectielen, personages, voertuigen).

Samenvatting

Het SDF-contract zet de drie werkpaardbotsingsquery’s om in rekenkunde:

• Insluiting is een tekencontrole.
• Penetratiediepte en scheidingsrichting zijn de grootte en gradiënt op het diepst gesampelde punt, gecombineerd tot een minimale translatievector.
• Continue botsingsdetectie is een sphere cast met dezelfde veilige-stapgarantie als sphere tracing, met de veldwaarde minus de bewegende straal als stapgrootte.

Dezelfde gradiënt- en penetratiewiskunde voedt het volgende enginesubsysteem: deeltjesbotsingsrespons en krachtvelden lossen precies deze overlaps op op per-deeltje-schaal.