1 Algorytmy rastrowe Algorytmy konwersji Rysowanie odcinkówalgorytm przyrostowy algorytm z punktem środkowym Rysowanie okręgów Algorytm konwersji oblicza współrzędnie pikseli leżących najbliżej idealnej (nieskończenie cienkiej) linii(bądź krzywej) nałożonej na siatkę dwuwymiarowego rastra Nachylenie odcinka 0 - poziome ; [-1, 1] ; >1 Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

2 Algorytm przyrostowy (DDA - digital differential analyzer)Równanie prostej yi= mxi + B m = y/x yi+1= mxi+1 + B = m(xi + x) + B = mxi + B + mx = yi + mx ponieważ x = 1, to yi+1 = yi + m Jeśli m> 1 => dziury w odcinku Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

3 void Linie(int x0, int y0, int x1, int y1){ int x; /* x0 < x1 */ float dy, dx, y , m; /* -1  m  1 */ dy = y1-y0; dx = x1-x0; m = dy / dx; y = y0; for (x = x0; x <= x1; x++) { WritePixel(x, round(y)); /* zaokrąglenie do wartości int */ y += m; } Wady: - y, m :zmienne ułamkowe - m : trzeba dzielić - trzeba zaokrąglać y ( float => int ) Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

4 Algorytm z punktem środkowymZakładamy 0 < m < 1 początek: lewy dolny (x0 , y0) koniec: górny prawy (x1 , y1) Algorytm Bresenhama Mod. Alg. Bresenhama Omówić całość postępowania ! Współrzędne M( xp + 1, yp + 1/2) F(x,y) = ax + by +c ( wymagamy aby a > 0 !!!) dla nas a = dy; b = -dx; Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

5 Opis odcinka w postaci funkcji uwikłanejF (x,y) = ax + by + c = 0 mx - y + B = 0 Własności: F (x,y) = 0 dla punktów należących do odcinka F (x,y) > 0 dla punktów poniżej odcinka F (x,y) < 0 dla punktów powyżej odcinka y = (dy/dx)* x + B (dy/dx) * x + B - y = 0 dy * x - dx * y + B*dx = 0 Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

6 Obliczanie zmiennej decyzyjnej dF(M) = F(xp+1, yp + 1/2) d = F(M) = F(xp+1, yp + 1/2) = a (xp+1) + b (yp + 1/2) + c Jeśli d  0 wybieramy E Jeśli d > 0 wybieramy NE Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

7 Obliczanie zmiennej decyzyjnej dnewJeśli E (to M przesuwa się w prawo o 1) dnew = F(xp+2, yp + 1/2) = a (xp+2) + b( yp + 1/2) + c = a (xp+1) + b( yp + 1/2) + c + a = d + a Jeśli NE (to M przesuwa się w prawo o 1 i w górę o 1) dnew = F(xp+2, yp + 3/2) = a (xp+2) + b( yp + 3/2) + c = a (xp+1) + b( yp + 1/2) + c + a + b = d + a + b Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

8 Obliczanie wartości startowychInicjacja d = dstart dnew = d + a Jeśli E dnew = d + a + b Jeśli NE dstart = F(x0+1, y0 + 1/2) = = F(x0, y0) + a + b/ = a + b/2 F (x,y) = ax + by + c = 0 (dy/dx) * x + B - y = 0 dy * x - dx * y + B*dx = 0 a = dy ; b = - dx; Koniec? Stop T (E) N (NE) d <= 0 ? d += a+b x++;y++ d += a x++ y = (dy/dx)* x + B (dy/dx) * x + B - y = 0 dy * x - dx * y + B*dx = 0 a = dy b = - dx c = B* dx Rysuj(x,y) Aby uniknąć dzielenia, zmienne decyzyjne możemy pomnożyć przez 2 Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

9 void MidLinie(int x0, int y0, int x1, int y1){ int dx, dy, incE, incNE, d, x, y; dy = y1-y0; dx = x1-x0; /*0 < dy/dx < 1 */ d = 2 * dy - dx; incE = 2 * dy; incNE = 2 * (dy -dx); x = x0; y = y0; WritePixel(x, y); while (x < x1) { if (d <= 0) { /* piksel E */ d += incE; x++; } else { /* piksel NE */ d += incNE; y++; } Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

10 Problemy kierunek rysowania obcinanie jasność odcinka łamanekierunek rysowanie - d = 0 to wybor E ->; a wybor SE <- styl linii (nie można zamieniac) Obcinanie - inne nachylenie !!! Zmiana jasnosci łamane - nie można rysowac dwukrotnie tego samego piksela np.. XOR ! Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

11 Rysowanie okręgów (1) x2 + y2 = R2 y =  x2 - R2- rysunek generowany z krokiem jednostkowym - zaokrąglanie y - przerwy Bardzo nieefektywne R cos(), R sin() - też zle dla  0-90 , lepiej ale osmiorotna symetria ( 8 pkt. Jednocesnie) x2 + y2 = R2 y =  x2 - R2 Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

12 Rysowanie okręgów (2) F(x,y) = x2 + y2 - R2 Instytutu Informatyki P.W.Rysowanie w drugim ? Oktancie przestrzeni F(x,y) = 0 na okręgu F(x,y) < 0 wewnątrz okręgu F(x,y) = x2 + y2 - R2 Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

13 Obliczanie zmiennych decyzyjnych (1)d = F(M) = F(xp+1, yp-1/2) = (xp+1) 2 + (yp-1/2) 2 - R2 Jeśli E (to M przesuwa się w prawo o 1) dnew = F(xp+2, yp - 1/2) = (xp+2) 2 + (yp-1/2) 2 - R2 = (xp 2 +4 xp +4) + (yp-1/2) 2 - R2 = (xp 2 +2 xp +1) +2 xp (yp-1/2) 2 - R2 = (xp+1) xp (yp-1/2) 2 - R2 + = d + 2 xp +3 Przyrost zależą od xp, yp!!! Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

14 Obliczanie zmiennych decyzyjnych (2)Jeśli SE (to M przesuwa się w prawo o 1 i w dół o 1) dnew = F(xp+2, yp - 3/2) = (xp+2) 2 + (yp-3/2) 2 - R2 = (xp 2 +4 xp +4) + (yp2 - 3yp + 9/4) - R2 = (xp+1)2 + 2 xp (yp2-yp + 1/4) -2 yp + 8/4 - R2 = (xp+1) xp (yp-1/2) yp R2 = d + 2 xp - 2 yp + 5 Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

15 Obliczenia wartości startowychPunkt startu ( xp , yp ) = (0, R) d = F (xp +1, yp -1/2) = F (1, R-1/2) = 12 + (R-1/2) 2 - R2 = 12 + (R2 - R + 1/4) - R2 = 5/4 - R Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

16 void MidCircle(int R) { int x, y; float d; x = 0; y = r;d = 5.0 / 4 - R; CirclePoints(x, y); while (y > x) { if (d < 0) { /* piksel E */ d += x * ; x++; } else { /* piksel SE */ d += (x - y)* ; y--; } Różnice 2-go rzedu Eold = 2 xp+3; Enew = 2 (xp+1) + 3 dla pkt. (xp+1, yp); Enew - Eold = 2 Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

17 Rysowanie okręgów Modyfikacje algorytmu zmiana środka okręguaspekt monitora Inne zagadnienia kierunek rysowania pogrubianie linii styl linii Instytutu Informatyki P.W. Zakład Grafiki Komputerowej

18 Przykład Narysować okrąg o środku w punkcie (0,0) i promieniu R = 6;(0,6) d<0 to E d = d + 2x+3 = -19/4 + 12/4 = -7/4 x = 1 (1,6) d<0 to E d = -7/4 + 8/4 + 12/4 = 13/4 x = 2 (2,6) d>0 to SE d = d + 2(x-y) + 5 = 13/4 -32/4 + 20/4 = 1/4 x = 3; y = 5 (3,5) d > 0 to SE d = 1/4 -8/4 + 20/4 = 13/4 x = 4; y = 4 (4,4) Instytutu Informatyki P.W. Zakład Grafiki Komputerowej