Orezávanie bodu je pomerne jednoduché. Na zložitejšie
objekty však potrebujeme vždy viac operácii, a preto sa ich počet snažíme
minimalizovať. Tak je to aj s úsečkou vo všeobecnom tvare.
Najprv otestujeme jej koncové body, a ak patria do okna, tak aj celá úsečka
leží v okne. V prípade, že úsečka leží mimo, otestujeme jej prienik s
oknom. Ak úsečka pretína okno, tak ju orezávame, a na to potrebujeme zistiť
body prieniku (tj. kde úsečka pretne hranice
okna).
Podstatnou vlastnosťou
pri orezávaní je rýchlosť algoritmu na nájdenie bodov prieniku (pri vykresľovaní scény môžeme
mať rádovo tisíce objektov, ktoré treba orezať za čo najkratší
čas). Preto vzniklo niekoľko algoritmov na orezávanie. Najprv ale musíme
urobiť testy, či naozaj treba nájsť bod prieniku. Úsečky, ktoré ležia
v okne orezávať netreba, tie môžeme rovno vykresliť. Ak oba koncové body
úsečky ležia nad oknom, tj. majú súradnicu y < ymin
okna tak ich nevykreslime.
Podobne ak ležia pod oknom, naľavo či napravo od okna.
Prvá časť tohto algoritmu slúži práve na vylúčenie úsečiek, u ktorých netreba počítať prienik s oknom. Najprv si rozdelíme rovinu na 9 častí, pričom prostredná časť bude predstavovať okno. Každej časti priradíme 4-bitový kód, ktorý dostane aj bod úsečky, ktorý do tejto oblasti padne.
Jednotlivé bity
pre bod [x, y] sa nastavia nasledovne:
1. bit - bod leží naľavo od okna ( xmin > x )
2. bit - bod leží napravo od okna ( xmax < x
)
3. bit - bod leží nižšie od okna ( ymin > y
)
4. bit - bod leží vyššie od okna ( ymax < y
)
Bod ktorý sa nachádza vo vnútri okna, má kód 0000. Úsečka je celá v okne ak oba jej koncové body majú kód 0000. Môžeme ju vylúčiť, ak oba jej body sú vľavo, vpravo, hore alebo dole od okna. Ľahko to identifikujeme práve podľa kódov koncových bodov. Zoberieme oba kódy koncových bodov úsečky a urobme ich logický súčin ( (1 and 1) = 1, inak 0). Ak je rôzny od 0000 tak úsečka nepretína okno a teda ju môžeme vylúčiť. V opačnom prípade úsečku nemôžeme vylúčiť a musíme ju otestovať na prienik vzhľadom na hranicu okna, v najhoršom prípade 4 - krát.
Pri Cohen-Sutherlandovom algoritme sa môže stať, že budeme orezávať úsečku až 4-krát. V roku 1978 Cyrus a Beck [CYRU78] redukovali orezávanie maximálne na dvakrát, a to pri vstupe úsečky do okna a pri výstupe z okna. Základnú myšlienku si popíšme podľa [FER95].
Nech D je smerový vektor úsečky AB, potom móžeme zapísať úsečku AB v parametrickom tvare : P(t)=A+t.D, kde parameter t∈ <0,1>. Označme bod na hrane P a normálový vektor hraničnej priemky okna N. Ak sa bod úsečky P(t) nachádza mimo okn, potom normálový vektor N s vektorom ( P(t) - P) zviera uhol menší ako 90 a skalárný súčin je kladný. Aby bod P(t) ležal na hrane musí platiť : N. (P(t) -P) = 0. Nahradením P(t) parametrickým
Applet displays result of Liang-Barsky's Line Clipping Algorithm solution. There is initial line and clipping rectangle projected. The clipped part of initial line is highlighted by bolder and more contrast color.
Interactivity affords to change parameters (positions of outer points and cornes) of initial line and clipping rectangle comfortably using mouse functionality:
- finding and marking closest flexible point
- drag & drop idea of relocation outer points of initial line and clipping rectangle corners
In fact, line clipping means finding two outer points of intersection between rectangle(clipping) and line(clipped). Line segment acquired by junction of these two points is then called clipped line.
Liang-Barsky's Line Clipping Algorithm uses the parametric equations for a line and solves four inequalities to find the range of the parameter for which the line is in the intersection with rectangle.
In steps:
Pri Cohen-Sutherlandovom algoritme používame násobenie a delenie. Algoritmus postupného delenia sa snaží vyhnúť týmto operáciám. Jeho základný postup spočíva v prevedení úsečky z užívateľských súradníc na celočíselné súradnice, a potom postupnom delení úsečky na polovicu [1]. Počet iterácií delenia úsečky môže byť dosť veľký, ale samotné výpočty pre absenciu násobenia a delenia sú podstatne rýchlejšie. Pre úsečku s bodmi A[x1,y1] a B[x2,y2] najprv určíme stredový bod úsečky S. Ten má súradnice (x1+x2)/2 a (y1+y2)/2. Takto rozdelíme úsečku na dve, ktoré potom otestujeme tak ako pri Cohen-Sutherlandovom algoritme. Stratégia tejto metódy spočíva na delení úsečky na polovice. Pri každom kroku sa zvyčajne jedna polovica delenej úsečky vylúči (ak oba jej koncové body padnú to tej istej oblasti) a pokračujeme v delení druhej časti.