Orezávanie úsečky

    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.

Algoritmus orezávania Cohena-Sutherlanda

    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 )

$$$APPLET

Applet Kódy oblastí určené oknom

    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. 

$$$APPLET

Applet Orezávanie zadanej úsečky vzhľadom na okno a určenie bodov prieniku

Parametrické orezávanie - Cyrus-Beck algoritmus

    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

Applet Orezávanie zadanej úsečky vzhľadom na okno a určenie bodov prieniku

Parametrické orezávanie - Liang-Barsky algoritmus

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

$$$APPLET

Applet Drawing point, in corner right bottom are co-ordinates current point. Authors: Branislav Malinovsky

Source code



Specificaton of algorithm

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:

  • 1. Let P(x1,y1) and Q(x2,y2) be the outer points of initial line
  • 2. Set Tmin = 0 and Tmax = 1 (Tmin represents the starting position and Tmax represents ending position of actual phase of clipping the line relatively to initial line; at beginning positions of initial line)
  • 3. Use coordinates of clipping edges to find values of individual inequalities (generally t or individualy tL,tR,tT,tB)
    From parametric equation x = x1 + (x2-x1)*t, y = y1 + (y2-y1)*t (0<=t<=1):
    - let R (R = x1 + t*(x2 - x1)) is x coordinate of right edge - tL = (L-x1)/(x2-x1)
    - let L (L = x1 + t*(x2 - x1))is x coordinate of left edge - tR = (R-x1)/(x2-x1)
    - let T is y coordinate of top edge - tT = (T-y1)/(y2-y1)
    - let B is y coordinate of bottom edge - tB = (B-y1)/(y2-y1)
    If ttmax ignore it and go to the next edge otherwise classify the value of t as entering or exiting value (using inner product to classify). If t is entering value set tmin = t. If t is exiting value set tmax =t.
  • 4. If tmin < tmax then draw a line from (x1 + dx*tmin, y1 + dy*tmin) to (x1 + dx*tmax, y1 + dy*tmax).
  • 5. If the line crosses over the rectangle, you will see
    (x1 + dx*tmin, y1 + dy*tmin) and (x1 + dx*tmax, y1 + dy*tmax)
    are intersection between line and edge.

Algoritmus postupného delenia

    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.

$$$APPLET

Applet Orezávanie zadanej úsečky delením na polovicu

    Algoritmus v najhoršom prípade skončí za log(n) krokov, kde n je dĺžka maximálnej strany okna v pixloch.