Share
Het vermogen om een convexe vorm dynamisch te splitsen in twee afzonderlijke vormen is een zeer waardevolle vaardigheid of hulpmiddel om in je gamedev-arsenaal te hebben. Deze splitsing maakt geavanceerde soorten simulatie mogelijk, zoals binaire ruimteverdelingen voor grafische afbeeldingen of fysica, dynamisch destructieve omgevingen (brosse breuken!), Oceaan- of watersimulatie, botsingsresolutie voor physics engines, binaire ruimtelijke partioning en de lijst gaat gewoon door. Een geweldig voorbeeld is de game Fruit Ninja voor Kinect.
Wat betekent het precies om een convexe vorm te splitsen? In twee dimensies verwijzen we naar een vorm als een veelhoek; in drie dimensies verwijzen we naar een vorm als een veelvlak. (veelvlakken is het woord dat wordt gebruikt om naar meer dan één veelvlak te verwijzen.)
Tip: Over het algemeen vereenvoudigen convexe polygonen en veelvlakken vele aspecten van volume- of mesh-manipulatie en -beheer. Vanwege deze vereenvoudiging gaat het hele artikel uit van convexe polygonen en convexe veelvlakken. Holle vormen zijn hier niet los van enige discussie. In het algemeen worden gecompliceerde concave vormen gesimuleerd als een verzameling samengevoegde convexe vormen.
Om een idee te krijgen van de ideeën die in dit artikel worden gepresenteerd, hebt u een praktische kennis nodig van een bepaalde programmeertaal en een eenvoudig begrip van het puntproduct..
Een geweldige manier om vormen in zowel twee als drie dimensies te splitsen, is om gebruik te maken van de kniproutine Sutherland-Hodgman. Deze routine is vrij eenvoudig en zeer efficiënt en kan ook enigszins worden uitgebreid om rekening te houden met de numerieke robuustheid. Als je onbekend bent met het algoritme, bekijk dan mijn vorige artikel over het onderwerp.
Een goed begrip van vlakken in twee of drie dimensies is ook een must. Opgemerkt moet worden dat een tweedimensionaal vlak kan worden beschouwd als een projectie van een driedimensionaal vlak in twee dimensies - of, met andere woorden, een lijn.
Begrijp alsjeblieft dat een vliegtuig ook als een halve ruimte kan worden beschouwd. Het berekenen van de afstand of kruising van punten tot halve spaties is een vereiste voorwaarde: zie het laatste deel van Een aangepaste 2D-physicsmotor maken: de kernengine voor informatie hierover.
Raadpleeg de demonstratiebron (ook op Bitbucket) die ik heb gemaakt terwijl u deze zelfstudie leest. Ik heb deze demo gebruikt voor het maken van alle GIF-afbeeldingen in het artikel. De broncode bevindt zich in C ++ (en moet platformonafhankelijk compatibel zijn), maar is geschreven op een manier die gemakkelijk kan worden geporteerd naar elke programmeertaal.
Voordat we het probleem van het splitsen van een volledige polygoon aanpakken, laten we eens kijken naar het probleem van het splitsen van een driehoek door een snijvlak. Dit zal de basis vormen voor het begrijpen van het overstappen naar een robuuste en algemene oplossing.
Het leuke van vormscheiding is dat vaak algoritmen in 2D zonder veel moeite direct in 3D kunnen worden uitgebreid. Hier zal ik een heel eenvoudig algoritme voor driehoekssplitsing presenteren voor zowel twee als drie dimensies.
Wanneer een driehoek een splijtvlak snijdt, moeten drie nieuwe driehoeken worden gegenereerd. Hier is een afbeelding met een driehoek voor en na het splijten langs een vlak:
Bij een splitsvlak worden drie nieuwe driehoeken weergegeven tijdens het snijden. Laten we wat code in de open lucht gooien, ervan uitgaande dat de drie hoekpunten van een driehoek zijn a, b, c in tegengestelde richting (CCW) volgorde, en dat we weten dat de rand ab (rand van hoekpunten a tot b) hebben het splijtvlak doorsneden:
// Clip een driehoek tegen een vlak wetende dat // a naar b het knipvlak kruist // Referentie: Exact Bouyancy for Polyhedra door // Erin Catto in Game Programming Gems 6 void SliceTriangle (std :: vector & out, const Vec2 & a, // Eerste punt op driehoek, CCW-volgorde const Vec2 & b, // Tweede punt op driehoek, CCW-volgorde const Vec2 & c, // Derde punt op driehoek, CCW-volgorde f32 d1, // Afstand van punt a op het splijtvlak f32 d2 , // Afstand van punt b tot het splijtvlak f32 d3 // Afstand van punt c tot het splijtvlak) // Bereken het snijpunt van a tot b Vec2 ab = a + (d1 / (d1 - d2)) * (b - a); Triangle tri; if (d1 < 0.0f) // b to c crosses the clipping plane if(d3 < 0.0f) // Calculate intersection point from b to c Vec2 bc = b + (d2 / (d2 - d3)) * (c - b); tri.Set( b, bc, ab ); out.push_back( tri ); tri.Set( bc, c, a ); out.push_back( tri ); tri.Set( ab, bc, a ); out.push_back( tri ); // c to a crosses the clipping plane else // Calculate intersection point from a to c Vec2 ac = a + (d1 / (d1 - d3)) * (c - a); tri.Set( a, ab, ac ); out.push_back( tri ); tri.Set( ab, b, c ); out.push_back( tri ); tri.Set( ac, ab, c ); out.push_back( tri ); else // c to a crosses the clipping plane if(d3 < 0.0f) // Calculate intersection point from a to c Vec2 ac = a + (d1 / (d1 - d3)) * (c - a); tri.Set( a, ab, ac ); out.push_back( tri ); tri.Set( ac, ab, b ); out.push_back( tri ); tri.Set( b, c, ac ); out.push_back( tri ); // b to c crosses the clipping plane else // Calculate intersection point from b to c Vec2 bc = b + (d2 / (d2 - d3)) * (c - b); tri.Set( b, bc, ab ); out.push_back( tri ); tri.Set( a, ab, bc ); out.push_back( tri ); tri.Set( c, a, bc ); out.push_back( tri );
Hopelijk maakte de code hierboven je een beetje bang. Maar vrees niet; het enige wat we hier doen is het berekenen van enkele snijpunten om te weten hoe we drie nieuwe driehoeken kunnen genereren. Als iemand de vorige afbeelding zorgvuldig had onderzocht, zouden de locaties van de snijpunten duidelijk kunnen zijn: ze zijn waar de stippellijn het splitsvlak treft en waar de rand ab kruist het splijtvlak. Hier is een diagram voor het gemak:
Uit dit diagram is het gemakkelijk om te zien dat uitvoerdriehoeken de hoekpunten moeten bevatten a, ac, ab, ac, c, b, en ab, ac, b. (Maar niet noodzakelijkerwijs in dit exacte formaat, bijvoorbeeld, a, b, c zou dezelfde driehoek zijn als c, b, a omdat hoekpunten eenvoudig naar rechts werden verschoven.)
Om te bepalen welke hoekpunten bijdragen aan welke van de drie nieuwe driehoeken, moeten we bepalen of de hoekpunt een en vertex c leg boven of onder het vlak. Omdat we aannemen dat de rand ab staat bekend als kruisend, we kunnen impliciet dat afleiden b bevindt zich aan de andere kant van het uitknipvlak een.
Als de conventie van een negatieve afstand van een splijtvlak betekent doordringend in het vlak, kunnen we een predikaat formuleren om te bepalen of een punt een halve spatie snijdt: #define HitHalfspace (afstand) (afstand) < 0.0f). Dit predikaat wordt in elk gebruikt als verklaring om te controleren en te zien of een punt zich binnen de halve ruimte van het uitknipvlak bevindt.
Er zijn vier gevallen die bestaan uit combinaties van een en b de halve spatie van het knipvlak raken:
a | T T F F ----------- b | T F T F
Omdat onze functie dat beide vereist een en b aan weerszijden van het vliegtuig zijn, twee van deze gevallen zijn gevallen. Het enige dat overblijft is om aan welke kant te zien c legt. Vanaf hier is de oriëntatie van alle drie hoekpunten bekend; snijpunten en uitvoervertices kunnen direct worden berekend.
Om de. Te gebruiken SliceTriangle () functie, we moeten een kruisende rand van een driehoek vinden. De onderstaande implementatie is efficiënt en kan worden gebruikt op alle driehoeken in de simulatie om mogelijk te worden gesplitst:
// Plak alle driehoeken met een vector van driehoeken. // Er wordt een nieuwe lijst met uitgaand driehoeken gegenereerd. De oude // lijst met driehoeken wordt weggegooid. // n - De normaal van het knipvlak // d - Afstand van het knipvlak vanaf de oorsprong // Referentie: Exact Bouyancy voor veelvlakken door // Erin Catto in Game Programming Gems 6 void SliceAllTriangles (const Vec2 & n, f32 d) std: vector out; voor (uint32 i = 0; i < g_tris.size( ); ++i) // Grab a triangle from the global triangle list Triangle tri = g_tris[i]; // Compute distance of each triangle vertex to the clipping plane f32 d1 = Dot( tri.a, n ) - d; f32 d2 = Dot( tri.b, n ) - d; f32 d3 = Dot( tri.c, n ) - d; // a to b crosses the clipping plane if(d1 * d2 < 0.0f) SliceTriangle( out, tri.a, tri.b, tri.c, d1, d2, d3 ); // a to c crosses the clipping plane else if(d1 * d3 < 0.0f) SliceTriangle( out, tri.c, tri.a, tri.b, d3, d1, d2 ); // b to c crosses the clipping plane else if(d2 * d3 < 0.0f) SliceTriangle( out, tri.b, tri.c, tri.a, d2, d3, d1 ); // No clipping plane intersection; keep the whole triangle else out.push_back( tri ); g_tris = out;
Na het berekenen van de ondertekende afstand van elke driehoekvertex tot het splijtvlak, kan vermenigvuldiging worden gebruikt om te zien of twee afzonderlijke punten op tegenovergestelde zijden van een vlak liggen. Omdat de afstanden binnen een paar positief en negatief zijn, moet het product van de twee vermenigvuldigd met elkaar negatief zijn. Dit maakt het gebruik van een eenvoudig predikaat mogelijk om te zien of twee punten aan beide zijden van een vlak liggen: #define OnOppositeSides (distanceA, distanceB) ((distanceA) * (distanceB) < 0.0f).
Een keer ieder de rand wordt doorkruist met het splitsvlak, de driehoekige hoekpunten worden hernoemd en verschoven en per direct doorgegeven aan het interieur SliceTriangle functie. Op deze manier wordt de eerste gevonden kruisingsrand hernoemd naar ab.
Dit is wat een definitief werkend product er kan uitzien:
Het splitsen van driehoeken op deze manier houdt rekening met elke driehoek afzonderlijk, en het hier gepresenteerde algoritme breidt, zonder enige vorm van authoring, zich uit van twee naar drie dimensies. Deze vorm van driehoeken knippen is ideaal wanneer aangrenzende info van driehoeken niet vereist is, of wanneer geknipte driehoeken niet ergens in het geheugen worden opgeslagen. Dit is vaak het geval bij het berekenen van volumes kruispunten, zoals in drijfvermogen-simulatie.
Het enige probleem met geïsoleerde splitsing van driehoeken is dat er geen informatie is over driehoeken aangrenzend aan elkaar. Als je de bovenstaande GIF zorgvuldig bekijkt, kun je zien dat veel driehoeken collineaire hoekpunten delen en als gevolg daarvan samengevouwen kunnen worden in een enkele driehoek om efficiënt te worden weergegeven. In de volgende sectie van dit artikel wordt dit probleem behandeld met een ander, complexer algoritme (dat gebruikmaakt van alle tactieken die in deze sectie worden genoemd)..
Nu voor het laatste onderwerp. Uitgaande van een goed begrip van het Sutherland-Hodgman-algoritme, is het vrij eenvoudig om dit begrip uit te breiden om een vorm te splitsen met een vlak en vertices uit te voeren op beide zijden van het vliegtuig. Numerieke robuustheid kan (en zou ook moeten worden overwogen).
Laten we de oude Sutherland-Hodgman-clichés kort bekijken:
// InFront = plane.Distance (punt)> 0.0f // Behind = plane.Distance (punt) < 0.0f Vec2 p1, p2; ClipPlane plane; case p1 InFront and p2 InFront push p2 case p1 InFront and p2 Behind push intersection case p1 Behind and p2 InFront push intersection push p2
Deze drie gevallen werken fatsoenlijk, maar houden geen rekening met de dikte van het splijtvlak. Dientengevolge kan numerieke fouten binnenkomen wanneer objecten bewegen, waardoor de samenhang in het frame tijdelijk is. Dit soort numerieke instabiliteit kan ertoe leiden dat een hoek één frame wordt afgekapt en niet in een ander frame, en dit soort jittering kan visueel nogal lelijk zijn of onaanvaardbaar voor fysieke simulatie.
Een ander voordeel van deze dikke vliegtuigtest is dat punten die vlak bij het vlak liggen feitelijk als zijnde kunnen worden beschouwd op het vlak, wat de geknipte geometrie iets nuttiger maakt. Het is heel goed mogelijk dat een berekend snijpunt numeriek op de verkeerde kant van een vlak ligt! Dikke vliegtuigen vermijden dergelijke rare problemen.
Door dikke vlakken voor kruisingstests te gebruiken, kan een nieuw type geval worden toegevoegd: een puntlegging direct aan op een vliegtuig.
Sutherland-Hodgman moet op dezelfde manier worden aangepast (met een zwevend punt EPSILON om rekening te houden met dikke vlakken):
// InFront = plane.Distance (punt)> EPSILON // Behind = plane.Distance (punt) < -EPSILON // OnPlane = !InFront( dist ) && !Behind( dist ) Vec2 p1, p2; ClipPlane plane; case p1 InFront and p2 InFront push p2 case p1 InFront and p2 Behind push intersection case p1 Behind and p2 InFront push intersection push p2 case any p1 and p2 OnPlane push p2
Echter, deze vorm van Sutherland-Hodgman voert alleen vertices uit een kant van het kloofvlak. Deze vijf gevallen kunnen eenvoudig worden uitgebreid tot een reeks van negen om vertices aan beide zijden van een splitsvlak uit te voeren:
// InFront = plane.Distance (punt)> EPSILON // Behind = plane.Distance (punt) < -EPSILON // OnPlane = !InFront( dist ) && !Behind( dist ) Vec2 p1, p2; Poly front, back; ClipPlane plane; case p1 InFront and p2 InFront front.push( p2 ) case p1 OnPlane and p2 InFront front.push( p2 ) case p1 Behind and p2 InFront front.push( intersection ) front.push( p2 ) back.push( intersection ) case p1 InFront and p2 OnPlane front.push( p2 ) case p1 OnPlane and p2 OnPlane front.push( p2 ) case p1 Behind and p2 OnPlane front.push( p2 ) back.push( p2 ) case p1 InFront and p2 Behind front.push( intersection ) back.push( intersection ) back.push( p2 ) case p1 OnPlane and p2 Behind back.push( p1 ) back.push( p2 ) case p1 Behind and p2 Behind back.push( p2 )
Een implementatie van deze negen gevallen kan er als volgt uitzien (afgeleid van Ericsons Real-Time Collision Detection):
// Splitst een polygoon in tweeën langs een splijtvlak met een clipping-algoritme // call Sutherland-Hodgman clipping // Resource: Pagina 367 van Ericson (real-time botsingsdetectie) void SutherlandHodgman (const Vec2 & n, f32 d, const Poly * poly, std :: vector * out) Poly frontPoly; Poly backPoly; uint32 s = poly-> vertices.size (); Vec2 a = poly-> hoekpunten [s - 1]; f32 da = Punt (n, a) - d; voor (uint32 i = 0; i < s; ++i) Vec2 b = poly->vertices [i]; f32 db = Dot (n, b) - d; if (InFront (b)) if (Behind (a)) Vec2 i = Intersect (b, a, db, da); frontPoly.vertices.push_back (i); backPoly.vertices.push_back (i); frontPoly.vertices.push_back (b); else if (Behind (b)) if (InFront (a)) Vec2 i = Intersect (a, b, da, db); frontPoly.vertices.push_back (i); backPoly.vertices.push_back (i); else if (On (a)) backPoly.vertices.push_back (a); backPoly.vertices.push_back (b); else frontPoly.vertices.push_back (b); if (On (a)) backPoly.vertices.push_back (b); a = b; da = db; if (frontPoly.vertices.size ()) out-> push_back (frontPoly); if (backPoly.vertices.size ()) out-> push_back (backPoly);
Hier is een voorbeeld van Sutherland-Hodgman in actie:
Het is vermeldenswaard dat de laatste polygonen kunnen worden gerenderd als een hoekpunt met het formaat van een driehoekige waaier.
Er is een probleem waar u rekening mee moet houden: bij het berekenen van een kruispunt van ab en een splijtvlak, waar dit punt onder lijdt numerieke kwantisering. Dit betekent dat elke kruisingwaarde een schatting is van de werkelijke kruisingwaarde. Het betekent ook dat het kruispunt ba is niet numeriek hetzelfde; kleine numerieke drift resulteert in twee verschillende waarden!
Voorbeeld van een zichtbare spleet tussen driehoeken als gevolg van inconsistent knippen (afbeelding geïnspireerd op Ericsons Real-Time Collision Detection-boek). Een naïef knipprogramma kan een grote vergissing zijn om blindelings snijpunten te berekenen, wat kan resulteren in T-juncties of andere gaten in de geometrie. Om een dergelijk probleem te voorkomen, moet een consistente intersectieoriëntatie worden gebruikt. Volgens afspraak moeten punten van de ene kant van een vlak naar een ander worden geknipt. Deze strikte snijpuntvolgorde zorgt ervoor dat hetzelfde snijpunt wordt berekend en mogelijke gaten in de geometrie oplost (zoals in de afbeelding hierboven te zien is, is er aan de rechterkant een consistent knipresultaat).
Om texturen daadwerkelijk over gesplitste vormen weer te geven (misschien bij het splitsen van sprites), moet u de UV-coördinaten begrijpen. Een volledige bespreking van UV-coördinaten en texture mapping valt ver buiten het bestek van dit artikel, maar als je dit al begrijpt, zou het gemakkelijk moeten zijn om snijpunten om te zetten in UV-ruimte..
Begrijp alsjeblieft dat een transformatie van wereldruimte naar UV-ruimte een verandering van basistransformatie vereist. Ik zal UV-transformaties verlaten als een oefening voor de lezer!
In deze zelfstudie hebben we gekeken naar enkele eenvoudige lineaire algebra-technieken voor het aanpakken van het probleem van het dynamisch splitsen van generieke vormen. Ik heb ook enkele problemen met de numerieke robuustheid aangepakt. U zou nu in staat moeten zijn om uw eigen vormsplitsingscode te implementeren, of de demonstratiebron te gebruiken, om veel geavanceerde en interessante effecten of functies voor algemene spelprogrammering te bereiken.
Accentsconagua