Share
Evnen til å dynamisk dele en konveks form i to separate former er en svært verdifull ferdighet eller verktøy å ha i gamedev arsenalen. Denne splittingen gir mulighet for avanserte typer simuleringer, for eksempel binære rompartisjoner for grafikk eller fysikk, dynamisk ødeleggende miljøer (sprø brudd!), Hav- eller vann simulering, kollisjonsoppløsning for fysikkmotorer, binær romlig deling, og listen fortsetter. Et godt eksempel er spillet Fruit Ninja for Kinect.
Hva betyr det egentlig å dele en konveks form? I to dimensjoner refererer vi til en form som en polygon; I tre dimensjoner refererer vi til en form som en polyhedron. (polyhedra er ordet referert til mer enn en polyhedron.)
Tips: Generelt forenkler konvekse polygoner og polyeder mange aspekter ved volum- eller maskemanipulering og styring. På grunn av denne forenkling antar hele artikkelen konvekse polygoner og konvekse polyeder. Konkave former er ikke fra hverandre av noen diskusjon her. Generelt kompliserte konkave former simuleres som en samling av sammenføyde konvekse former.
For å få mening om ideene som presenteres i denne artikkelen, trenger du et arbeidskunnskap om noen programmeringsspråk, og en enkel forståelse av punktproduktet.
En fin måte å splitte former i både to og tre dimensjoner på er å benytte seg av Sutherland-Hodgman clipping rutine. Denne rutinen er ganske enkel og svært effektiv, og kan også utvides til å være så liten for å ta hensyn til numerisk robusthet. Hvis du ikke er kjent med algoritmen, sjekk ut min forrige artikkel om emnet.
En forståelse av fly i enten to eller tre dimensjoner er også et must. Det skal bemerkes at et todimensjonalt plan kunne betraktes som et projeksjon av et tredimensjonalt plan i to dimensjoner - eller med andre ord en linje.
Vennligst forstå at et fly også kan betraktes som en halv plass. Beregning av avstanden eller skjæringspunktet mellom punkter til mellomrom er en nødvendig forutsetning: se den siste delen av Hvordan lage en tilpasset 2D-fysikkmotor: Kjernemotoren for informasjon om dette.
Vennligst referer til demonstrasjonskilden (også på Bitbucket) som jeg har opprettet mens du leser gjennom denne opplæringen. Jeg brukte denne demoen for å lage alle GIF-bildene i artikkelen. Kilden koden er i C ++ (og bør være kompatibel på tvers av plattformen), men er skrevet på en måte som enkelt kan overføres til hvilket som helst programmeringsspråk.
Før vi løser problemet med å dele et helt polygon, la oss se på problemet med å dele en trekant gjennom et skjæreplan. Dette vil danne grunnlag for forståelse for å gå videre til en robust og generalisert løsning.
Det fine med form splitting er at ofte algoritmer i 2D kan utvides uten mye trøbbel direkte inn i 3D. Her presenterer jeg en veldig enkel triangelsplitningsalgoritme for både to og tre dimensjoner.
Når en trekant skjærer med et splittingsplan, skal tre nye trekanter genereres. Her er et bilde som viser en trekant før og etter spalting langs et fly:
Gitt et splittingsplan, blir tre nye trekanter utmatet under skjæreoperasjonen. La oss kaste noen koden inn i det åpne, forutsatt at de tre toppene av en trekant er a, b, c i moturs (CCW) rekkefølge, og at vi vet at kanten ab (kanten av punktene a til b) har krysset splittingsplanet:
// Klipp en trekant mot et fly som vet at // a til b krysser klippeplanet // Referanse: Exact Bouyancy for Polyhedra av // Erin Catto i Game Programming Gems 6 ugyldig SliceTriangle (std :: vector & out, const Vec2 & a, // Første punkt på trekanten, CCW rekkefølge Vec2 & b, // Andre punkt på trekanten, CCW rekkefølge Vec2 & c, // Tredje punkt på trekant, CCW rekkefølge f32 d1, // Avstand av punkt a til splittingsplanet f32 d2 , // Avstand av punkt b til splittingsplanet f32 d3 // Avstand av punkt c til splittningsplanet // Beregn skjæringspunktet fra a til 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 );
Forhåpentligvis har koden ovenfor skremt deg litt. Men vær ikke redd; alt vi gjør her er å beregne noen skjæringspunkter for å vite hvordan å generere tre nye trekanter. Hvis man hadde undersøkt det forrige bildet nøye, kan skjæringspunktene være åpenbare: de er hvor den stiplede linjen møter splittingsplanet, og hvor kanten ab skjærer splittingsplanet. Her er et diagram for bekvemmelighet:
Fra dette diagrammet er det enkelt å se at utgangstrekanter skal inneholde toppunktene a, ac, ab, ac, c, b, og ab, ac, b. (Men ikke nødvendigvis i dette eksakte formatet, for eksempel, a, b, c ville være den samme trekant som c, b, a fordi kniplinger bare var skiftet til høyre.)
For å bestemme hvilke vinkler som bidrar til hvilken av de tre nye trekanter, må vi avgjøre om vertexet en og toppunktet c ligge over eller under flyet. Siden vi antar at kanten ab er kjent for å være skjærende, kan vi utlede implisitt det b er på motsatt side av klippeplanet fra en.
Hvis konvensjonen med en negativ avstand fra et splittingsplan betyr trengende flyet, kan vi formulere et predikat for å avgjøre om et punkt krysser et halvrom: #define HitHalfspace (avstand) ((avstand) < 0.0f). Dette predikatet brukes innen hver hvis setning for å sjekke og se om et punkt er innenfor halvplassen av klippeplanet.
Det er fire saker som eksisterer av kombinasjoner av en og b treffer halvdel av klippeplanet:
a | T T F F ----------- b | T F T F
Siden vår funksjon krever det begge en og b være på motsatte sider av flyet, to av disse tilfellene blir tapt. Alt som er igjen er å se på hvilken side c legger. Herfra er orienteringen av alle tre toppene kjent; skjæringspunkter og utgangspunkter kan beregnes direkte.
For å kunne bruke SliceTriangle () funksjon, må vi finne en kryssende kant av en trekant. Nedre implementering er effektiv, og kan brukes på alle trekantene i simuleringen som potensielt kan deles:
// Skiver alle trekanter gitt en vektor trekanter. // En ny utgangstrekantliste er generert. Den gamle // listen over trekanter er kassert. // n - Klipsplanets normale // d - Avstand til klippeplanet fra opprinnelsen // Referanse: Exakt Bouyancy for Polyhedra av // Erin Catto i Game Programming Gems 6 ugyldige SliceAllTriangles (const Vec2 & n, f32 d) std :: vektor ut; for (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;
Etter beregning av den signerte avstanden for hver trekantvertex til splittingsplanet, kan multiplikasjon brukes for å se om to forskjellige punkter lå på motsatte sider av et plan. Siden avstandene vil være av en positiv og negativ flyt i et par, må produktet av de to multiplisert sammen være negativt. Dette muliggjør bruk av et enkelt predikat for å se om to punkter ligger på hver side av et fly: #define OnOppositeSides (avstandA, avstandB) ((avstandA) * (avstandB) < 0.0f).
En gang noen Kanten er funnet å skjære med splittingsplanet, trekanten blir omdøpt og skiftet og umiddelbart passert til interiøret SliceTriangle funksjon. På denne måten blir den første kryssende kanten omdøpt til ab.
Her er hva et endelig arbeidsprodukt kan se ut som:
Splitting triangler på denne måten står for hver triangel uavhengig, og algoritmen som presenteres her strekker seg uten to forfattere fra to til tre dimensjoner. Denne form for triangelklipping er ideell når adjacency-informasjonen av trekanter ikke er nødvendig, eller når klippede trekanter ikke lagres hvor som helst i minnet. Dette er ofte tilfelle ved beregning av skjæringsvolum, som i oppdriftsimulering.
Det eneste problemet med å dele trekantene i isolasjon er at det ikke er noen opplysninger om trekanter som er ved siden av til hverandre. Hvis du nøye undersøker ovenstående GIF, kan du se at mange trekanter deler kollinære hjørner, og som et resultat kan kollapses i en enkelt trekant for å bli gjort effektivt. Den neste delen av denne artikkelen tar opp dette problemet med en annen, mer kompleks algoritme (som bruker alle taktikkene som er tilstede i denne delen).
Nå for det siste emnet. Hvis man antar en fungerende forståelse av Sutherland-Hodgman-algoritmen, er det ganske enkelt å forlenge denne forståelsen for å dele en form med et plan og utgangspunkter på både sider av flyet. Numerisk robusthet kan (og burde) også bli vurdert.
La oss kort undersøke de gamle Sutherland-Hodgman-kappene:
// InFront = plan.Distance (punkt)> 0.0f // Bak = planetDistance (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
Disse tre tilfellene fungerer anstendig, men tar ikke hensyn til tykkelsen på splittingsplanet. Som et resultat, kan numerisk feil svinge inn når objekter beveger seg, noe som forårsaker lav temporær ramme-sammenheng. Denne typen numerisk ustabilitet kan føre til at et hjørne blir klippet en ramme og ikke i en annen ramme, og denne typen jittering kan være ganske stygg visuelt eller uakseptabel for fysisk simulering.
En annen fordel ved denne tykke flyetesten er at poeng som ligger svært nær flyet faktisk kan anses å være på flyet, noe som gjør den klippete geometrien litt mer nyttig. Det er helt mulig at et beregnet skjæringspunkt ligger numerisk på feil side av et fly! Tykke fly unngår slike rare problemer.
Ved å bruke tykke fly til skjæringsprøver, kan en ny type tilfelle legges til: en punktlegging direkte på på et fly.
Sutherland-Hodgman bør endres som slik (med flytende punkt EPSILON å tegne tykke fly):
// InFront = plan.Distance (punkt)> EPSILON // Bak = planetDistance (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
Denne utgaven av Sutherland-Hodgman utsender imidlertid bare utganger på en side av splittingsplanet. Disse fem sakene kan enkelt utvides til et sett med ni til utgangspunkter på hver side av et splittingsplan:
// InFront = plan.Distance (punkt)> EPSILON // Bak = planetDistance (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 )
En implementering av disse ni tilfellene kan se ut som følger (avledet av Ericsons kollisionsgjenkjenning i sanntid):
// Splitter en polygon i et halvt langs et splittingsplan ved hjelp av en klipping algoritme // ring Sutherland-Hodgman clipping // Ressurs: Side 367 av Ericson (Real-Time Collision Detection) tomrom 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 = prikk (n, a) - d; for (uint32 i = 0; i < s; ++i) Vec2 b = poly->toppunkter [i]; f32 db = prikk (n, b) - d; hvis (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); annet hvis (Bak (b)) hvis (InFront (a)) Vec2 i = Intersect (a, b, da, db); frontPoly.vertices.push_back (i); backPoly.vertices.push_back (i); annet hvis (På (a)) backPoly.vertices.push_back (a); backPoly.vertices.push_back (b); ellers frontPoly.vertices.push_back (b); hvis (På (a)) backPoly.vertices.push_back (b); a = b; da = db; hvis (frontPoly.vertices.size ()) ut-> push_back (frontPoly); hvis (backPoly.vertices.size ()) ut-> push_back (backPoly);
Her er et eksempel på Sutherland-Hodgman i aksjon:
Det er verdt å merke seg at de endelige polygonene kan gjengis som en vertexliste med formatet trekantvifte.
Det er ett problem du bør være oppmerksom på: når du beregner et skjæringspunkt for ab og et splittingsplan, dette punktet lider av numerisk kvantisering. Dette betyr at enhver kryssningsverdi er en tilnærming av den faktiske kryssingsverdien. Det betyr også at skjæringspunktet BA er ikke numerisk det samme; liten numerisk drift vil faktisk resultere i to forskjellige verdier!
Eksempel på en synlig sprekk mellom trekanter som følge av inkonsekvent klipping (bilde inspirert av Ericsons realtids kollisionsdeteksjonsbok). En naiv klipping rutine kan gjøre en stor feil med å beregne skjæringspunktene blindt, noe som kan resultere i T-kryss eller andre hull i geometri. For å unngå et slikt problem må en konsistent skjæringsretning brukes. Ved konvensjon bør punkter klippes fra en side av et fly til et annet. Denne strenge krysningsbestillingen sikrer at det samme skjæringspunktet blir beregnet, og vil løse potensielle hull i geometri (som vist i bildet ovenfor, er det et konsistent klipsresultat til høyre).
For å faktisk gjengi teksturer over splittede former (kanskje når du deler sprites), trenger du en forståelse av UV-koordinater. En komplett diskusjon av UV-koordinater og teksturkartlegging ligger langt utover denne artiklens omfang, men hvis du allerede har denne forståelsen, bør det være enkelt å forvandle skjæringspunkter til UV-rom.
Vennligst forstå at en transformasjon fra verdensrommet til UV-rom krever en endring av grunntransformasjon. Jeg la UV-transformasjoner som en øvelse for leseren!
I denne opplæringen så vi på noen enkle lineære algebra teknikker for å takle problemet med dynamisk splitting av generiske former. Jeg har også tatt opp noen numeriske robusthetsproblemer. Du bør nå kunne implementere din egen form splitting-kode, eller bruke demonstrasjonskilden, for å oppnå mange avanserte og interessante effekter eller funksjoner for generell spillprogrammering.
Accentsconagua