Share
klipping er prosessen med å bestemme hvilken region av rommet som er innenfor en annen region av rommet. Dette er spesielt viktig innen studieområder som datagrafikk og fysikk simulering. For eksempel, når du gjør en verden til skjermen, er det best å vite hva som vil være på skjermen før du behandler data. Dette gjør det mulig å ignorere mange utenlandske data, mens bare behandling og presentasjon av hva som vil bli sett av brukeren.
I fysisk simulering er det ofte funnet stive legemer interpenetrating - det vil si at to separate objekter overlapper. Dette er dårlig. Interpenetrasjon er noe som aldri skjer i den virkelige verden, men er et problem som må håndteres ved kollisjonssporing. Ofte er en form klippet mot en annen for å avgjøre hvilke funksjoner som faktisk berører. Herfra kan et kollisionsrespons påbegynnes.
Avanserte funksjoner i spillmotorer kan implementeres med en eller annen form for klipping; oppdrift simulering, kamera visning fly; sprø brudd, kontaktgenerering med seperating akse test; alle disse tingene (og mye mer) kan oppnås med klipping algoritmer. Faktisk var klipping som dette nødvendig i min tidligere veiledning om å bygge en stiv kroppsfysikkmotor.
Denne artikkelen krever noen du har en anstendig forståelse av:
Ovennevnte studieområder kan læres av et bredt spekter av ressurser på internett (for eksempel Wolfires guide til lineær algebra eller Khan Academy - og de er ikke så vanskelig å lære!
Mange komplekse klippingrutiner innebærer å benytte en enkelt type operasjon: splitte en form med et enkelt plan. Splitting en form av et fly innebærer å ta en form og skjære i to stykker gjennom et solidt plan.
Det er viktig å innse at splittelse av en form med et fly er et grunnleggende verktøy i denne klippeprosessen.
Se Davide Cervones utmerkede animasjoner for en klar demonstrasjon av dette:
Sutherland Hodgman clipping er min favoritt klipping rutine, som det fungerer for å klippe linje looper mot fly. Med denne algoritmen, gitt en liste over inngangspunkter og en liste over fly, kan en utgang av nye vinkler som eksisterer rent innenfor settet av fly beregnes.
Begrepet planet kan brukes til å referere til både et fly i 3D og 2D. Et 2D-plan kan også kalles a linje.Vi kan forestille oss listen over vertices som en enkelt polygon. Vi kan forestille oss (for nå) listen over fly som en enkelt linje. Visualisere dette i to dimensjoner kan se ut som følgende bilde:
Med Sutherland Hodgman clipping, er polygonen til høyre den ønskede formen, mens den røde polygonen til venstre er inngangsformen, og har ennå ikke blitt klippet. Den blå linjen representerer et splittingsplan i to dimensjoner. Et hvilket som helst antall skillefly kan brukes; i eksemplet ovenfor brukes bare et enkelt splittingsplan. Hvis mange splittingsplaner blir brukt, vil klipping skje et plan i tide, kutte bort mer og mer av en originalform for å sende ut en ny:
For enkelhet, la oss jobbe i strenge to dimensjoner. Når man deler et polygon mot et fly, vil det være viktig å vite hvilken side av flyet et hvilket som helst punkt er på.
Ovenfor er den mest brukte måten å finne avstanden fra et punkt til et fly. Merk at prikksymbolet i ovennevnte ligning representerer prikkproduktet.
Avstanden trenger ikke å beregnes eksplisitt; den normale vektoren n trenger ikke å bli normalisert (det vil si, det trenger ikke å ha en lengde på nøyaktig en enhet). Alt som må kontrolleres er tegn på avstandsresultatet d. Hvis n er ikke normalisert da d vil være i enheter av lengden på n. Hvis n Normaliseres da d vil være i enheter som tilsvarer verdensromsenheter. Dette er viktig å innse da det gjør det mulig for beregningen å bli gjort for å se om d er positiv eller negativ. positiv d Betegner det punktet p er på forsiden av flyet. Negativ betyr at det er på baksiden.
Nå, hva betyr det egentlig med "front" og "tilbake" sider av et fly? Vel, det avhenger virkelig av hva du definerer foran og tilbake som. Vanligvis betyr "front" at det er på samme side av flyet som det normale.
Lar deg dykke rett inn i algoritmen. Ta en rask skanning over pseudokoden:
Polygon SutherlandHodgman (const Polygon startPolygon, Plane [] clippingPlanes) Polygon output = startingPolygon for hver Plane clippingPlane i clippingPlanes input = output output.Clear () Vec2 startPoint = input.Last () for hver Vec2 endPoint i inngang hvis startPoint og endPoint i foran clippingPlane out.push (endPoint) ellers hvis startPoint foran og endPoint bak clippingPlane out.push (Intersection (clippingPlane, startPoint, endPoint)) ellers hvis startPoint og endPoint bak clippingPlane out.push (Intersection (clippingPlane, startPoint, endPoint) ) out.push (endPoint) endPoint = startpunkts returutgang
Algoritmen tar en inngangspolygon og noen klippeplaner, og gir ut et nytt polygon. Tanken er å klippe hvert linjesegment av inngangspolygonen mot ett klippeplan om gangen. Dette bildet fra Wikimedia Commons viser dette ganske bra:
Hver utklippsoperasjon har bare noen få forskjellige tilfeller der du kan utgjøre hjørner og kan skisseres slik:
// 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
Den beste måten å forstå denne algoritmen på er å tegne en 2D-form på et stykke papir og tegne en rett linje gjennom formen. Deretter går du langs polygonens hjørner og utfører Sutherland-Hodgman-algoritmen og trekker resultatene. Dette vil bygge intuisjon om hvordan algoritmen bare kjører langs hver linje i rekkefølge, og sørg for å holde alle hjørner bak flyet.
Etter din egen blyant og papir løp, prøv denne flotte nettsiden. Det er noen flotte visualer og en Java-applet (øverst på siden) som lar brukeren se deler av algoritmen faktisk løper!
Beregning av krysset mellom et plan gitt to punkter er veldig enkelt. Tanken er å bruke avstandsberegningen for å finne avstanden til hvert punkt til et fly. Gitt disse avstandene kan en kryssing beregnes ved bruk av lineær interpolering.
Tips: Linjær interpolering er et ekstremt nyttig konsept for å forstå, ha produktiv applikasjon i all grafikkprogramvare og i fysisk simuleringsprogramvare. Linjær interpolering kan omtales som lerp. Alt kan bli lineært interpolert fra en startposisjon til sluttposisjon, så lenge som bevegelsesligning er lineær.Generelt sett er formelen for lineær interpolering fra start til slutt med kryss alfa er:
Lerp (start, slutt, alfa) retur start * (1 - alfa) + ende * alfaTips: I eksemplet ovenfor,
Accentsconagua
alfa er det som kalles en interpol. Interpolanter brukes i lineære interpolasjonsberegninger for å beregne posisjoner mellom start- og sluttpunkter. Å vite dette, kan avstandene fra flyet til hvert punkt brukes som verdier for å beregne en alfa interpolasjon. Variablene t1 og t2 kan representere avstandene til flyet til p1 og p2 henholdsvis.
I dette henseende er skjæringspunktet rett og slett a Lerp fra startpunkt til sluttpunkt, gitt en kryssetid.
Denne algoritmen kan enkelt utvides til tredimensjonalt rom og utføres der. (Denne algoritmen kan utføres i en hvilken som helst høyere dimensjon, uansett hva det betyr.) Men i praktiske applikasjoner er denne algoritmen vanligvis aldri faktisk utført i 3D. Ved å bruke klare inverse transformasjoner, kan problemet med å klippe en 3D-polyhedron mot et fly kan (i visse scenarier) forenkles til en 2D-polygon til til polygonekliprutine. Dette tillater betydelig beregningsoptimalisering.
På samme måte, hvis man skulle studere kildekoden for Bullet Physics, ville man finne ut at klipping faktisk er gjort i et enkeltdimensjonalt rom, selv om full 3D-klipping virkelig blir utført. Dette skyldes muligheten til å beregne en gyldig interpolant gitt bare en enkelt dimensjon av problemrommet.
For eksempel, hvis man kjenner kryssetiden til x verdier av et enkelt problem, kan denne kryssetiden brukes som en interpolant for å utføre en Lerp på et tredimensjonalt punkt.
La oss undersøke dette litt mer detaljert. Ta en titt på følgende diagram:
Anta at den gule linjen er bakken i en y-posisjon på 0. Anta nå at start-posisjonen er på 10, og den endelige y-stillingen er på -1. La oss beregne en gyldig interpolasjons- og skjæringsposisjon langs y-koordinaten:
// alpha = 0,9 / 10,0f float alfa = 0,9f // finalY = 0.0f float finalY = Lerp (y1, y2, alfa);
Ovennevnte kan leses som "90% av veien fra 10 til -1", som ville være null. Denne interpolanten kan brukes til vilkårlig datatyper, inkludert en todimensjonal vektor:
// alpha = 9.0f / 10.0f flyt alfa = 0,9f Vec2 finalPosition = Lerp (p1, p2, alfa);
Ovennevnte kode ville faktisk beregne riktig x-koordinat for tidspunktet for støt, uten å utføre operasjoner med x-koordinaten for å bestemme interpolanten. Denne ideen om å beregne interpolanter og bruke dem til høyere dimensjoner enn fra hvilken de ble beregnet, er en fin måte å optimalisere kode på.
Det er noen problemer som kan vedvare når du kjører en naiv implementering av denne klippingrutinen. Når kalkuleringspunktet beregnes, kryper numerisk feil inn i beregningen. Dette utgjør et stort problem når du deler et polygon med et fly mens du genererer utgang på begge sider av flyet. For å generere produksjon på begge sider av et splittingsplan må den opprinnelige Sutherland-Hodgman-algoritmen endres litt, og det er her problemer vil oppstå.
Når et skjæringspunkt beregnes, kryper numerisk feil inn. Dette er et problem som skjæringspunktet beregnes fra punkt EN å peke B vil være litt annerledes enn beregningen fra punkt B å peke EN. For å unngå slike problemer må krysset beregnes på en konsistent måte. Dette unngår en forferdelig T-kryss utgave. Det er greit hvis det er numerisk feil så lenge feilen er konsistent.
T-Junction problemet: Et gap mellom to masker som forårsaker trekantrasterisering å legge et synlig mellomrom mellom tre trekanter. Vanligvis forårsaket av dårlig håndtering av maskinens epsilon under flytende punktberegning. Mulige løsninger: konsistente vertex transformasjoner; verteks sveising etterbehandling.
Et annet problem er å bestemme om et punkt er på den ene siden av et fly eller et annet. For en hel del grunner, bør tykk flykontroll kontrolleres. Ideen er å behandle et fly som et tykt fly, i stedet for en med en uendelig liten bredde. Dette gjør det mulig for en ekstra sak å oppstå i Sutherland-Hodgman-rutinen: på flyet sak.
flyte D = planet. Avstand (punkt); // EPSILON er et numerisk signifikant og visuelt ubetydelig tall. Kanskje 0.00001f. bool OnPlane (float D) return D> -EPSILON og D < EPSILON;
Hvis noe er funnet på klippeplanet, trykk bare på endepunktet. Dette vil bringe de 3 saken til totalt 4. For mer informasjon om EPSILON, se her.
Den beste referansen for denne klippalgoritmen ligger i Christer Ericsons realtids kollisionsdeteksjonsbok (aka Orange Book). Du kan finne denne boken i stort sett hver spillstudio i eksistens.
Utover å sprute ut mye penger for en bok, finnes det et par gratis ressurser:
Sutherland-Hodgman clipping er en fin måte å utføre klipping på både 2D og 3D-plass. Denne typen rutine kan brukes for å løse mange forskjellige problemer, hvorav noen problemer er anvendelige i ganske avanserte studieområder. Som alltid vær så snill å stille spørsmål i kommentarfeltet nedenfor!
