Share
Klippning är processen att bestämma vilken region av rymden som ligger inom en annan region av rymden. Detta är särskilt viktigt inom områdena studie, som datorgrafik och fysik simulering. När du till exempel gör en värld till skärmen är det bäst att veta vad som kommer att finnas på skärmen innan du bearbetar data. Detta gör att många externa data kan ignoreras, medan de bara behandlar och presenterar vad som kommer att ses av användaren.
I fysisk simulering förefaller ofta styva kroppar vara interpenetrerande - det vill säga två separata objekt överlappar varandra. Det här är dåligt. Interpenetration är något som aldrig händer i den verkliga världen, men är ett problem som måste hanteras vid kollisionsdetektering. Ofta är en form klippt mot en annan för att bestämma vilka funktioner som faktiskt rör. Härifrån kan ett kollisionssvar initieras.
Avancerade funktioner hos spelmotorer kan implementeras med någon form av klippning; flytkraft simulering, kamera visa planer; spröd frakturering, kontaktgenerering med separationsaxeltestet; alla dessa saker (och mycket mer) kan uppnås med klippningsalgoritmer. Faktum är att klipping av detta var nödvändigt i min tidigare handledning om att bygga en styv kroppsfysikmotor.
Denna artikel kräver att du har en anständig förståelse för:
Ovanstående studieområden kan läras av en mängd olika resurser på internet (som Wolfires guide till linjär algebra eller Khan Academy - och de är inte så svåra att lära sig!
Många komplexa kliprutiner innebär att man använder en enda typ av operation: splittrar en form med ett plan. Att splittra en form med ett plan innebär att man tar en form och skär i två delar genom ett fast plan.
Det är viktigt att inse att splittring av en form med ett plan är ett grundläggande verktyg i denna klippningsrutin.
Se Davide Cervones utmärkta animationer för en tydlig demonstration av detta:
Sutherland Hodgman klippning är min favorit klippning rutin, som det fungerar för att klippa linjeloppar mot plan. Med den här algoritmen kan man, med en lista med ingångshöjdpunkter och en lista över plan, beräkna en utmatning av nya toppunkter som existerar rent inom uppsättningen plan..
Termen planet kan användas för att referera till både ett plan i 3D och 2D. Ett 2D-plan kan också kallas a linje.Vi kan föreställa oss listorna med vertikaler som en enda polygon. Vi kan föreställa oss (för nu) listan över plan som en enda rad. Visualisering av detta i två dimensioner kan se ut som följande bild:
Med Sutherland Hodgman klippning är polygonen till höger den önskade formen, medan den röda polygonen till vänster är inmatningsformen och har ännu inte klippts. Den blå linjen representerar ett delningsplan i två dimensioner. Eventuellt antal klyvplan kan användas; i det ovanstående exemplet används bara ett enda splittningsplan. Om många klyvplan används, skulle klippning ske ett plan i taget, skära bort mer och mer av en original form för att mata ut en ny:
För enkelhet, låt oss arbeta i strikta två dimensioner. När man delar upp en polygon mot ett plan är det viktigt att veta vilken sida av planet som helst, vilken punkt som helst.
Ovan är det vanligaste sättet att hitta avståndet från en punkt till ett plan. Observera att prick-symbolen i ovanstående ekvation representerar punktprodukten.
Avståndet behöver inte beräknas explicit; den normala vektorn n behöver inte normaliseras (det betyder att det inte behöver ha en längd på exakt en enhet). Allt som behöver kontrolleras är tecknet på distansresultatet d. Om n Normaliseras då inte d kommer att ligga i enheter av längden på n. Om n Normaliseras då d kommer att vara i enheter som motsvarar världsutrymmeenheter. Detta är viktigt att inse eftersom det tillåter att beräkningen görs för att se om d är positiv eller negativ. Positiv d betecknar den punkten p är på framsidan av planet. Negativ betyder att det finns på baksidan.
Nu vad menar vi med "framsidan" och "baksidan" av ett plan? Jo det beror verkligen på vad du definierar fram och tillbaka som. Vanligtvis betyder "front" att det är på samma sida av planet som normalt.
Låt oss dyka in i algoritmen. Ta en snabbsökning över pseudokoden:
Polygon SutherlandHodgman (const Polygon startPolygon, Plane [] clippingPlanes) Polygon output = startPolygon för varje Plane clippingPlane i clippingPlanes input = output output.Clear () Vec2 startPoint = input.Last () för varje Vec2 endPoint i inmatning om startPoint och endPoint in framför clippingPlane out.push (endPoint) annars om startPoint framför och endPoint bakom clippingPlane out.push (Intersection (clippingPlan, startPoint, endPoint)) annars om startPoint och endPoint bakom clippingPlane out.push (Intersection (clippingPlan, startPoint, endPoint) ) out.push (endPoint) endPoint = startpunkts returutgång
Algoritmen tar en inmatningspolygon och några klippplan och matar ut en ny polygon. Tanken är att klippa varje linjesegment av ingångs-polygonen mot ett klippningsplan åt gången. Den här bilden från Wikimedia Commons visar det här ganska bra:
Varje klippning har endast ett fåtal olika fall där du kan mata ut kryssningar och kan beskrivas som så:
// 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
Det bästa sättet att förstå denna algoritm är att rita en 2D-form på ett papper och rita en rak linje genom formen. Sedan slinga längs polygonens spetsar och utföra Sutherland-Hodgman-algoritmen och dra resultaten. Detta kommer att bygga intuition om hur algoritmen bara går längs varje rad i följd, se till att hålla alla hörn bakom planet.
Efter din egen penna och papperskörning, prova den här stora webbsidan. Det finns några fantastiska bilder och en Java-applet (överst på sidan) som låter användaren se att delar av algoritmen faktiskt körs!
Beräkning av skärningspunkten för ett plan som ges två punkter är mycket enkelt. Tanken är att använda distansberäkningen för att hitta avståndet för varje punkt till ett plan. Med tanke på dessa avstånd kan en korsning sedan beräknas med användning av linjär interpolering.
Tips: Linjär interpolering är ett extremt användbart koncept för att förstå, ha produktiv applikation i all grafikprogramvara och i fysisk simuleringsprogram. Linjär interpolering kan kallas referens till lerp. Allting kan linjärt interpoleras från startposition till slutläge, så länge som rörelse ekvation är linjär.I allmänhet är formeln för linjärt interpolering från Start till slutet med skärnings alfa är:
Lerp (start, slut, alfa) retur start * (1 - alfa) + slut * alfaTips: I ovanstående exempel,
Accentsconagua
alfa är det som kallas en interpolant. Interpolanter används i linjära interpolationsberäkningar för att beräkna positioner mellan start- och slutpunkter. Genom att veta detta kan avstånden från planet till varje punkt användas som värden för att beräkna en alfa interpolant. Variablerna t1 och t2 kan representera avstånden till planet av p1 och p2 respektive.
I detta avseende är skärningspunkten helt enkelt en Lerp från utgångspunkten till slutpunkten, givet en korsningstid.
Denna algoritm kan enkelt utökas till tredimensionellt utrymme och utförs där. (Den här algoritmen kan utföras i vilken högre dimension som helst.) I praktiska tillämpningar är denna algoritm vanligtvis aldrig faktiskt utförd i 3D. Genom att använda smarta inversa transformationer kan problemet med att klippa en 3D-polyhedron mot en planburk (i vissa scenarier) förenklas till en 2D-polygon till polygonklippningsrutin. Detta möjliggör en väsentlig databasoptimering.
På samma sätt, om man skulle studera Bullet Physics källkod, skulle man finna att klippning faktiskt görs i ett enda dimensionellt utrymme, även om full 3D-klippning verkligen utförs. Detta beror på möjligheten att beräkna en giltig interpolant som ges endast en enda dimension av problemutrymmet.
Till exempel, om man vet korsningstiden för x värden av ett enkelt problem kan denna skärningstid användas som en interpolant för att utföra en Lerp på en tredimensionell punkt.
Låt oss undersöka det här i lite mer detalj. Ta en titt på följande diagram:
Antag att den gula linjen är marken vid en y-position på 0. Antag nu att startpositionen är vid 10, och den slutliga y-positionen är vid -1. Låt oss beräkna en giltig interpolations- och skärningsposition längs y-koordinaten:
// alpha = 0,9 / 10,0f float alfa = 0,9f // finalY = 0.0f float finalY = Lerp (y1, y2, alfa);
Ovanstående kan läsas som "90% av vägen från 10 till -1", vilket skulle vara noll. Denna interpolant kan appliceras på godtyckliga datatyper, innefattande en tvådimensionell vektor:
// alpha = 9.0f / 10.0f float alfa = 0,9f Vec2 finalPosition = Lerp (p1, p2, alfa);
Ovanstående kod skulle faktiskt beräkna den korrekta x-koordinaten för stötstiden, utan att ens utföra operationer med x-koordinaten för att bestämma interpolanten. Denna ide att beräkna interpolanter och tillämpa dem på högre dimensioner än från vilka de beräknades är ett bra sätt att optimera kod.
Det finns några problem som kan kvarstå när du kör en naiv implementering av denna klippningsrutin. När man beräknar skärningspunkten kryper numeriskt fel i beräkningen. Detta utgör ett stort problem när man delar en polygon med ett plan samtidigt som man genererar uteffekt båda sidor av planet. För att generera produktion för båda sidor av ett splittningsplan behöver den ursprungliga Sutherland-Hodgman-algoritmen ändras något, och det är här problem kommer att uppstå.
När en korsningspunkt beräknas, krypterar numeriskt fel i. Detta är ett problem som korspunkten beräknad från punkten en att peka B kommer att vara något annorlunda än beräkningen från punkten B att peka en. För att undvika sådana problem måste korsningen beräknas på ett konsekvent sätt. Detta undviker en fruktansvärd T-korsningen problem. Det är okej om det finns numeriskt fel så länge felet är konsekvent.
T-Junction problem: Ett mellanrum mellan två maskor som medför att triangelrasterisering lämnar ett synligt mellanrum mellan tre trianglar. Vanligtvis orsakad av dålig hantering av maskinens epsilon under flytpunktsberäkning. Möjliga lösningar: konsekventa vertextransformationer; vertex svetsning efterbehandling.
Ett annat problem är att bestämma om en punkt är på ena sidan av ett plan eller ett annat. För en hel massa skäl bör tjocka flygkontroller göras. Tanken är att behandla ett plan som ett tjockt plan, snarare än en med en oändligt liten bredd. Detta möjliggör ett ytterligare fall att uppstå inom Sutherland-Hodgman rutin: på planet fall.
float D = plan.Distance (punkt); // EPSILON är ett numeriskt signifikant och visuellt obetydligt antal. Kanske 0.00001f. bool OnPlane (float D) return D> -EPSILON och D < EPSILON;
Om någon punkt hittas på klippplanet, tryck bara på ändpunkten. Detta kommer att få 3 fall att räkna till totalt 4. För mer information om EPSILON, kolla här.
Den bästa referensen för denna klippningsalgoritm finns i Christer Ericsons realtids kollisionsdetektering bok (aka Orange Book). Du kan hitta den här boken i stort sett varje spelstudio som existerar.
Utöver beskjutning ut mycket pengar för en bok finns det ett par lediga resurser:
Sutherland-Hodgman klippning är ett utmärkt sätt att utföra klippning i både 2D och 3D-utrymme. Denna typ av rutin kan tillämpas för att lösa många olika problem, vissa problem är tillämpliga i ganska avancerade studier. Som alltid är du välkommen att ställa frågor i kommentarfältet nedan!
