Share
Möjligheten att dynamiskt dela en konvex form i två separata former är en mycket värdefull färdighet eller verktyg att ha i din gamedev arsenal. Denna splittring möjliggör avancerade typer av simuleringar, t.ex. binära rymdpartitioner för grafik eller fysik, dynamiskt destruktiva miljöer (spröd sprickbildning!), Ocean- eller vatten simulering, kollisionsupplösning för fysikmotorer, binär rumslig deling och listan fortsätter bara. Ett bra exempel är spelet Fruit Ninja för Kinect.
Vad betyder det egentligen att dela en konvex form? I två dimensioner hänvisar vi till en form som en polygon; i tre dimensioner hänvisar vi till en form som en polyeder. (Polyhedra är ordet refererat till mer än en polyhedron.)
Tips: Generellt förenar konvexa polygoner och polyeder många aspekter av volym- eller maskindrivning och hantering. På grund av denna förenkling förutsätter hela artikeln konvexa polygoner och konvexa polyeder. Konkade former skiljer sig inte från någon diskussion här. I allmänhet simuleras komplicerade konkava former som en samling förenade konvexa former.
För att förnuftiga de idéer som presenteras i denna artikel behöver du en fungerande kunskap om vissa programmeringsspråk och en enkel förståelse av punktprodukten.
Ett bra sätt att dela upp former i både två och tre dimensioner är att använda sig av Sutherland-Hodgman klippningsrutinen. Denna rutin är ganska enkel och mycket effektiv, och kan också förlängas någonsin så lite för att ta hänsyn till numerisk robusthet. Om du inte känner till algoritmen, kolla in min tidigare artikel om ämnet.
En förståelse av plan i antingen två eller tre dimensioner är också ett måste. Det bör noteras att ett tvådimensionellt plan skulle kunna betraktas som en projicering av ett tredimensionellt plan i två dimensioner ?? - eller med andra ord en linje.
Vänligen förstå att ett plan också kan betraktas som ett halvt utrymme. Att beräkna avståndet eller korsningen av punkter till halvrum är en nödvändig förutsättning: se den sista delen av Hur man skapar en anpassad 2D-fysikmotor: Kärnmotorn för information om detta.
Vänligen hänvisa till demonstrationskällan (även på Bitbucket) som jag har skapat när du läser igenom denna handledning. Jag använde denna demo för att skapa alla GIF-bilderna i artikeln. Källkoden är i C ++ (och ska vara plattformskompatibel), men skrivs på ett sätt som enkelt kan överföras till något programmeringsspråk.
Innan vi löser problemet med att dela upp en hel polygon, låt oss ta en titt på problemet med att dela en triangel genom ett skärplan. Detta kommer att ligga till grund för förståelsen för att gå vidare till en robust och generaliserad lösning.
Det fina med formuppdelning är att ofta algoritmer i 2D kan utökas utan stora problem direkt i 3D. Här presenterar jag en mycket enkel triangelsplitningsalgoritm för både två och tre dimensioner.
När en triangel skär med ett delningsplan, ska tre nya trianglar genereras. Här är en bild som visar en triangel före och efter splittring längs ett plan:
Med ett splittningsplan matas tre nya trianglar under skivoperationen. Låt oss kasta några koden i det öppna, förutsatt att de tre hörnen av en triangel är a, b, c i moturs (CCW) ordning, och att vi vet att kanten ab (kant av hörn a till b) har korsat klyvplanet:
// Klipp en triangel mot ett plan som vet att // a till b korsar klippplanet // Referens: Exakt Bouyancy för Polyhedra av // Erin Catto i Game Programming Gems 6 tomt SliceTriangle (std :: vector & out, const Vec2 & a, // Första punkten på triangeln, CCW order const Vec2 & b, // Andra punkten på triangeln, CCW order const Vec2 & c, // Tredje punkt på triangel, CCW order f32 d1, // Avstånd av punkt a till delningsplanet f32 d2 , // Avstånd av punkt b till klyvplanet f32 d3 // Avstånd av punkt c till klyvplanet // Beräkna korsningspunkten från a till b Vec2 ab = a + (d1 / (d1 - d2)) * (b - a); Triangel 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 );
Förhoppningsvis räddade ovannämnda kod dig lite. Men frukta inte; allt vi gör här är att beräkna några skärningspunkter för att veta hur man genererar tre nya trianglar. Om man hade granskat den tidigare bilden noggrant kan skärningspunkterna vara uppenbara: de är där den prickade linjen möter klyvplanet och där kanten ab skär klyvplanet. Här är ett diagram för bekvämlighet:
Från det här diagrammet är det lätt att se att utmatningstrianglarna borde innehålla spetsarna a, ac, ab, ac, c, b, och ab, ac, b. (Men inte nödvändigtvis i detta exakta format, till exempel, a, b, c skulle vara samma triangel som c, b, a eftersom snören var helt enkelt skiftas till höger.)
För att bestämma vilka vinklar som bidrar till vilken av de tre nya trianglarna, måste vi bestämma om vertexen en och vertex c ligga ovanför eller under planet. Eftersom vi antar att kanten ab Det är känt att det skärs, vi kan implicit utgå ifrån b ligger på motsatt sida av klippplanet från en.
Om konventionen av ett negativt avstånd från ett delningsplan betyder genomträngande planet, vi kan formulera ett predikat för att avgöra om en punkt korsar en halvrymd: #define HitHalfspace (avstånd) ((avstånd) < 0.0f). Detta predikat används inom varje om uttalande för att kontrollera och se om en punkt ligger inom halvplanet av klippplanet.
Det finns fyra fall som existerar av kombinationer av en och b träffar klipplanets halvrum:
a | T T F F ----------- b | T F T F
Eftersom vår funktion kräver det båda en och b vara på motsatta sidor av planet, två av dessa fall tappas. Allt som är kvar är att se på vilken sida c fastställs. Härifrån är orienteringen av alla tre toppunkter kända; skärningspunkter och utgångspunkter kan beräknas direkt.
För att kunna använda SliceTriangle () funktion måste vi hitta en korsning av en triangel. Nedre implementeringen är effektiv och kan användas vid alla trianglar i simuleringen som kan splittras:
// Skivar alla trianglar med en vektor av trianglar. // En ny utmatningstriangellista skapas. Den gamla //-listan över trianglar kasseras. // n - Klipplanets normala // d - Avståndet till klippplanet från ursprunget // Referens: Exakt Bouyancy för Polyhedra av // Erin Catto i Spelprogrammering Gems 6 Void SliceAllTriangles (const Vec2 & n, f32 d) std :: vektor ut; för (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;
Efter att ha beräknat det signerade avståndet för varje triangelvärde till delningsplanet kan multiplikation användas för att se om två distinkta punkter låg på motsatta sidor av ett plan. Eftersom avstånden kommer att vara av en positiv och negativ flottör inom ett par måste produkten av de två multiplicerade tillsammans vara negativa. Detta möjliggör användningen av ett enkelt predikat för att se om två punkter ligger på vardera sidan av ett plan: #define OnOppositeSides (avståndA, avståndB) ((distanceA) * (avståndB) < 0.0f).
En gång några Kanten befinner sig i korsning med klyvplanet, triangeln hörnar omdämnas och flyttas och omedelbart passerade in i interiören SliceTriangle fungera. På detta sätt omges den första korsningskanten som omnämns ab.
Här är vad en slutlig arbetsprodukt kan se ut:
Splitting trianglar på detta sätt står för varje triangel oberoende, och den algoritm som presenteras här sträcker sig, utan ytterligare författande, från två till tre dimensioner. Denna form av triangelklippning är idealisk när adjacencyinformation av trianglar inte behövs, eller när klippade trianglar inte lagras någonstans i minnet. Detta är ofta fallet vid beräkning av korsningsvolymer, som i flytmodulering.
Det enda problemet med att dela trianglar i isolation är att det inte finns några uppgifter om trianglar som är intilliggande till varandra. Om du granskar ovanstående GIF försiktigt kan du se att många trianglar delar kollinära snurrar och som ett resultat kan kollapsas i en enda triangel för att bli effektiviserad. Nästa avsnitt i denna artikel behandlar detta problem med en annan, mer komplex algoritm (som utnyttjar all taktik som finns i detta avsnitt).
Nu för det sista ämnet. Om man antar en fungerande förståelse för Sutherland-Hodgman-algoritmen är det ganska lätt att utvidga denna förståelse för att dela en form med ett plan och en utgångspunkt på både sidor av planet. Numerisk robusthet kan (och bör) också övervägas.
Låt oss kortfattat undersöka de gamla Sutherland-Hodgman-klippen:
// InFront = plan.Distance (punkt)> 0.0f // Bakom = planDistance (punkt) < 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
Dessa tre fall fungerar ordentligt, men tar inte hänsyn till tjockleken på klyvplanet. Som ett resultat kan numeriskt fel drivas in när objekt rör sig, vilket medför låg temporal ramsammanhang. Denna typ av numerisk instabilitet kan resultera i att ett hörn klipps en ram och inte i en annan ram, och den här typen av jittering kan vara ganska ful visuell eller oacceptabel för fysisk simulering.
En annan fördel med detta tjocka flygprov är att punkter som ligger väldigt nära planet faktiskt kan anses vara på planet, vilket gör den klippta geometrin lite mer användbar. Det är helt möjligt att en beräknad korsningspunkt ligger numeriskt på den motsatta sidan av ett plan! Tjocka planer undviker så konstiga problem.
Genom att använda tjocka plan för korsningstest kan en ny typ av fall läggas till: en punktläggning direkt på på ett plan.
Sutherland-Hodgman bör modifieras som så (med en flytpunkt EPSILON att redogöra för tjocka plan):
// InFront = plan.Distance (punkt)> EPSILON // Bakom = plan.Distance (punkt) < -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
Emellertid utmatar denna form av Sutherland-Hodgman endast vertices på en sida av klyvplanet. Dessa fem fall kan enkelt utökas till en uppsättning av nio till utgångspunkter på vardera sidan av ett delningsplan:
// InFront = plan.Distance (punkt)> EPSILON // Bakom = plan.Distance (punkt) < -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 )
Ett genomförande av dessa nio fall kan se ut som följer (härledd från Ericsons kollisionsdetektering i realtid):
// Splits en polygon i halva längs ett delningsplan med en klippningsalgoritm // Sutherland-Hodgman-klippning // Resurs: Sid 367 av Ericson (Real-time Collision Detection) void SutherlandHodgman (const Vec2 & n, f32 d, const Poly * poly, std :: vektor * ut) Poly frontPoly; Poly backPoly; uint32 s = poly-> vertices.size (); Vec2 a = poly-> vertices [s - 1]; f32 da = punkt (n, a) - d; för (uint32 i = 0; i < s; ++i) Vec2 b = poly->vertex [i]; f32 db = punkt (n, b) - d; om (InFront (b)) if (Bak (a)) Vec2 i = Intersect (b, a, db, da); frontPoly.vertices.push_back (i); backPoly.vertices.push_back (i); frontPoly.vertices.push_back (b); annars om (Bakom (b)) om (InFront (a)) Vec2 i = Intersect (a, b, da, db); frontPoly.vertices.push_back (i); backPoly.vertices.push_back (i); annars om (På (a)) backPoly.vertices.push_back (a); backPoly.vertices.push_back (b); annars frontPoly.vertices.push_back (b); om (På (a)) backPoly.vertices.push_back (b); a = b; da = db; om (frontPoly.vertices.size ()) out-> push_back (frontPoly); om (backPoly.vertices.size ()) out-> push_back (backPoly);
Här är ett exempel på Sutherland-Hodgman i aktion:
Det är värt att notera att de slutgiltiga polygonerna kan göras som en vertexlista med formatet av triangelfläkt.
Det finns ett problem som du bör vara medveten om: när du beräknar en korsningspunkt för ab och ett klyvplan, lider denna punkt numerisk kvantisering. Detta innebär att varje korsningsvärde är en approximation av det aktuella korsningsvärdet. Det betyder också att korsningspunkten ba är inte numeriskt densamma; liten numerisk drift kommer faktiskt att resultera i två olika värden!
Exempel på en synlig spricka mellan trianglarna som ett resultat av inkonsekvent klippning (bild inspirerad av Ericsons realtids kollisionsdetektering bok). En naiv kliprutin kan göra ett stort misstag av dators skärningspunkter blint, vilket kan resultera i T-korsningar eller andra luckor i geometri. För att undvika ett sådant problem måste en konsekvent korsningsorientering användas. Enligt konventionen bör punkter klippas från ena sidan av ett plan till ett annat. Denna stränga skärningsposition garanterar att samma skärningspunkt beräknas och löser eventuella luckor i geometrin (som visas i bilden ovan finns det ett konsekvent klippresultat till höger).
För att faktiskt göra texturer över delade former (kanske när du delar sprites) behöver du förståelse av UV-koordinater. En fullständig diskussion om UV-koordinater och texturmappning ligger långt bortom omfattningen av denna artikel, men om du redan har denna förståelse, ska det vara enkelt att förvandla skärningspunkter till UV-utrymme.
Vänligen förstå att en omvandling från världsutrymme till UV-utrymme kräver en förändring av grundtransformationen. Jag lämnar UV-transformationer som en övning för läsaren!
I denna handledning såg vi på några enkla linjära algebra tekniker för att ta itu med problemet med dynamiskt splittring av generiska former. Jag tog också upp några numeriska robusthetsfrågor. Du ska nu kunna implementera din egen form splittringskod eller använda demonstrationskällan för att uppnå många avancerade och intressanta effekter eller funktioner för allmän spelprogrammering.
Accentsconagua