Linjeklippning
I datorgrafik är linjeklipp processen att ta bort ( klippa ) linjer eller delar av linjer utanför ett område av intresse (en visningsport eller vyvolym ) . Typiskt tas varje del av en linje som är utanför visningsområdet bort.
Det finns två vanliga algoritmer för linjeklippning: Cohen–Sutherland och Liang–Barsky .
En linjeklippningsmetod består av olika delar. Tester utförs på ett visst linjesegment för att ta reda på om det ligger utanför synområdet eller volymen. Därefter utförs korsningsberäkningar med en eller flera klippgränser . Att bestämma vilken del av linjen som är innanför eller utanför klippvolymen görs genom att bearbeta ändpunkterna på linjen med avseende på skärningspunkten.
Cohen–Sutherland
Inom datorgrafik är Cohen–Sutherland-algoritmen (uppkallad efter Danny Cohen och Ivan Sutherland) en linjeklippningsalgoritm. Algoritmen delar upp ett 2D-utrymme i 9 regioner, av vilka endast mittdelen (viewport) är synlig.
År 1967 ledde flygsimuleringsarbete av Danny Cohen till utvecklingen av Cohen–Sutherlands datorgrafiska två- och tredimensionella linjeklippningsalgoritmer, skapade med Ivan Sutherland.
Liang-Barsky
Liang–Barsky-algoritmen använder den parametriska ekvationen för en linje och olikheter som beskriver räckvidden för urklippsrutan för att bestämma skärningspunkterna mellan linjen och urklippsrutan. Med dessa skärningar vet den vilken del av linjen som ska dras. Den här algoritmen är betydligt effektivare än Cohen–Sutherland, men Cohen–Sutherland gör triviala accepter och avvisar mycket snabbare, så det bör istället övervägas om de flesta raderna du behöver klippa skulle vara helt in i eller utanför klippfönstret .
Cyrus-Beck
Mycket lik Liang–Barskys linjeklippningsalgoritm. Skillnaden är att Liang–Barsky är en förenklad Cyrus–Beck-variant som var optimerad för ett rektangulärt klippfönster.
Cyrus-Beck-algoritmen är i första hand avsedd för att klippa en linje i parametrisk form mot en konvex polygon i 2 dimensioner eller mot en konvex polyeder i 3 dimensioner.
Nicholl–Lee–Nicholl
Nicholl–Lee–Nicholl-algoritmen är en snabb linjeklippningsalgoritm som minskar chanserna att klippa ett enda linjesegment flera gånger, vilket kan hända i Cohen–Sutherland-algoritmen. Klippningsfönstret är uppdelat i ett antal olika områden, beroende på positionen för den första punkten på linjen som ska klippas.
Snabb klippning
Denna algoritm har likheter med Cohen–Sutherland. Start- och slutpositionerna klassificeras efter vilken del av rutnätet med 9 områden de upptar. En stor switch-sats hoppar till en specialiserad hanterare för det fallet. Däremot kan Cohen–Sutherland behöva iterera flera gånger för att hantera samma fall.
O (lg N ) algoritm
Denna algoritm klassificerar hörn mot den givna linjen i den implicita formen p : ax + by + c = 0. Eftersom polygonen antas vara konvex och hörn är ordnade medurs eller moturs, kan binär sökning tillämpas och leder till ett O (lg N ) körtidskomplexitet.
Skala
Denna algoritm är baserad på homogena koordinater och dualitet . Den kan användas för linje- eller linjesegmentklippning mot ett rektangulärt fönster, såväl som mot en konvex polygon. Algoritmen är baserad på att klassificera en vertex av klippfönstret mot ett halvrum givet av en linje p : ax + by + c = 0. Resultatet av klassificeringen bestämmer kanterna som skärs av linjen p . Algoritmen är enkel, lätt att implementera och kan utökas till ett konvext fönster också. Linjen eller linjesegmentet p kan beräknas från punkterna r 1 , r 2 givna i homogena koordinater direkt med hjälp av korsprodukten som
- p = r 1 × r 2 = ( x 1 , y 1 , w 1 ) × ( x 2 , y 2 , w 2 )
eller som
- p = r 1 x r 2 = ( x 1 , y , 1 ) x ( x 2 , y 2 , 1 ) .