Chương I. Các yếu tố cơ sở của ñồ họa • Bước 4: Tiếp tục tăng x lên 1 Pixel. Ở vị trí xi +1, ta tính: pi+1 = pi + 2∆y nếu pi < 0 pi+1 = pi + 2.( ∆y - ∆x) nếu pi ≥ 0 Nếu pi+1 < 0 thì ta chọn toạ ñộ y kế tiếp là yi+1 Ngược lại thì ta chọn yi+1 +1 • Bước 5: Lặp lại bước 4 cho ñến khi x = x2. Sau ñây là thủ tục cài ñặt thuật toán: Procedure LINE(x1,y1,x2,y2:integer); { 0<m<1} var dx,dy,x,y,p,c1,c2,xMax:integer; Begin dx:=abs(x1-x2); dy:=abs(y1-y2); c1:=2*dy; c2:=2*(dy-dx); p:=2*dy-dx; if x1>x2 then begin x:=x2; y:=y2; xMax:=x1; end else begin x:=x1;y:=y1;xMax:=x2; end; putpixel(x,y,red); while x<xMax do begin x:=x+1; if p<0 then p:=p+c1 else begin y:=y+1; p:=p+c2; end; 11 Chương I.
Các yếu tố cơ sở của ñồ họa putpixel(x,y,red); end; end; 1. Thuật toán MidPoint Ta chỉ xét trường hợp hệ số góc 0<m<1. Thuật toán này ñưa ra cách chọn ñiểm S(xi+1,yi) hay P(xi+1,yi+1) bằng cách so sánh ñiểm thực Q(xi+1,y) với ñiểm M (trung ñiểm của S và P). Nếu ñiểm Q nằm dưới ñiểm M thì chọn ñiểm S Ngược lại, chọn ñiểm P.3) Ta có dạng tổng quát của phương trình ñường thẳng: Ax + By + C = 0 với A = y2 – y1 , B = –(x2 – x1) , C = x2.y2 ðặt F(x,y) = Ax + By + C, ta có nhận xét: < 0 nếu (x,y) nằm phía trên ñường thẳng F(x,y) = 0 nếu (x,y) thuộc về ñường thẳng > 0 nếu (x,y) nằm phía dưới ñường thẳng Lúc này, việc chọn các ñiểm S hay P ñược ñưa về việc xét dấu của: 1 pi = F(M) = F(xi + 1,yi + ) 2 Nếu pi < 0 ⇒ M nằm trên ñoạn thẳng ⇒ Q nằm dưới M ⇒ Chọn S P Nếu pi ≥ 0 ⇒ M nằm dưới ñoạn yi+ 1 Q thẳng ⇒ Q nằm trên M ⇒ Chọn P M Mặt khác: yi S 1 pi = F(xi + 1,yi + ) 2 1 xi pi+1 = F(xi+1 + 1,yi+1 + ) xi+1 2 Hình 1.3 nên 1 1 pi+1 - pi = F(xi+1 + 1,yi+1 + ) - F(xi + 1,yi + ) 2 2 12 Chương I.
Các yếu tố cơ sở của ñồ họa 1 1 = A(xi+1+1) + B(yi+1 + ) + C - A(xi+1) - B(yi + ) - C 2 2 = A(xi+1 - xi) + B(yi+1 - yi) = A + B(yi+1 - yi) (vì xi+1 - xi =1) Suy ra: pi+1 = pi + A + B(yi+1 - yi) (*) *Nhận xét:. Nếu pi < 0: Chọn ñiểm S: yi+1 = yi Từ (*) suy ra pi+1 = pi + A. Nếu pi ≥ 0: Chọn ñiểm P: yi+1 = yi + 1 Từ (*) suy ra pi+1 = pi + A + B Với ñiểm mút ñầu tiên, ta có: 1 1 p1 = F(x1 + 1,y1 + ) = A(x1+1) + B(y1 + ) + C 2 2 B B = Ax1 + Bx1 + C + A + =A+ (vì Ax1 + Bx1 + C = 0) 2 2 Thuật toán MidPoint cho kết quả tương tự như thuật toán Bresenham. THUẬT TOÁN VẼ ðƯỜNG TRÒN Xét ñường tròn (C) tâm O(xc,yc) bán kính R.
x) y,- * Ý tưởng: Hình Do tính ñối xứng của ñường tròn nên nếu ñiểm 1.4) Vì vậy, ta chỉ cần vẽ một phần tám cung tròn rồi lấy ñối xứng qua gốc O và 2 trục toạ ñộ thì ta có ñược toàn bộ ñường tròn. Thuật toán Bresenham Giả sử (xi,yi) ñã vẽ ñược. Cần chọn ñiểm kế tiếp là (xi +1,yi) hoặc (xi +1,yi -1) (Hình 1.5) Từ phương trình: x2 + y2 = R2 ta tính ñược giá trị y thực ứng với xi +1 là: 13 Chương I. Các yếu tố cơ sở của ñồ họa y2 = R2 - (xi +1)2 ðặt: d1 = yi2 - y2 = yi2 - R2 + (xi + 1)2 d2 = y2 - (yi - 1)2 = R2 - (xi + 1)2 - (yi - 1)2 yi y Suy ra: yi- pi = d1 - d2 = 2.(xi+1 + 1)2 + y2i+1 + (yi+1 - 1)2 - 2R2 (3) Từ (2) và (3) ta có: xi xi+1 pi+1 - pi = 4xi + 6 + 2.5 ⇒ pi+1 = pi + 4xi + 6 + 2.
Ngược lại chọn ñiểm (xi + 1,yi - 1) • Bước 3: x:=x + 1, tính lại p: Nếu pi < 0: pi+1 = pi + 4xi + 6. Ngược lại: pi+1 = pi + 4. Ngược lại chọn ñiểm (xi+1,yi+1-1) • Bước 4: Lặp lại bước 3 cho ñến khi x = y. Sau ñây là thủ tục ñể cài ñặt thuật toán: Procedure Circle(x0,y0,r:Integer); Var p,x,y:Integer; Procedure VeDiem; Begin PutPixel( x0 + x , y0 + y , color); PutPixel( x0 - x , y0 + y , color); PutPixel( x0 + x , y0 - y , color); PutPixel( x0 - x , y0 - y , color); 14 Chương I.
Các yếu tố cơ sở của ñồ họa PutPixel( x0 + y , y0 + x , color); PutPixel( x0 - y , y0 + x , color); PutPixel( x0 + y , y0 - x , color); PutPixel( x0 - y , y0 - x , color); End; Begin x:=0; y:=r; p:=3 - 2*r; While x<=y do Begin VeDiem; If p<0 then p:=p + 4*x + 6 Else Begin p:=p + 4*(x-y) + 10; y:=y-1; End; x:=x+1; End; End; 1. Thuật toán MidPoint Từ phương trình ñường tròn: x2 + y2 = R2 S 2 2 2 yi ðặt F(x,y) = x + y - R ,ta có: M < 0 nếu (x,y) ở trong ñường tròn Q yi- P F(x,y) = 0 nếu (x,y) ở trên ñường tròn 1 > 0 nếu (x,y) ở ngoàiñường tròn Lúc này, việc chọn các ñiểm S(xi+1,yi) hay xi xi+1 P(xi+1,yi-1) ñược ñưa về việc xét dấu của: Hình 1.6) 2 Nếu pi < 0 ⇒ M nằm trong ñường tròn ⇒ Q gần S hơn ⇒ Chọn S Nếu pi ≥ 0 ⇒ M nằm ngoài ñường tròn ⇒ Q gần P hơn ⇒ Chọn P 15 Chương I. Các yếu tố cơ sở của ñồ họa Mặt khác: 1 pi = F(xi + 1,yi - ) 2 1 pi+1 = F(xi+1 + 1,yi+1 - ) 2 nên 1 1 pi+1 - pi = F(xi+1 + 1,yi+1 - ) - F(xi + 1,yi - ) 2 2 1 2 1 = [(xi+1+1)2 + (yi+1 - ) - R2] - [(xi+1)2 + (yi - )2 - R2] 2 2 1 2 1 = [(xi+2)2 + (yi+1 - ) - R2] - [(xi+1)2 + (yi - )2 - R2] 2 2 = 2xi + 3 + (yi+12 - yi2) - (yi+1 - yi) Suy ra: pi+1 = pi + 2xi + 3 + (yi+12 - yi2) - (yi+1 - yi) (*) *Nhận xét:. Nếu pi < 0: Chọn ñiểm S : yi+1 = yi Từ (*) ⇒ pi+1 = pi + 2xi + 3.
Nếu pi ≥ 0: Chọn ñiểm P: yi+1 = yi - 1 Từ (*) ⇒ pi+1 = pi + 2(xi - yi) + 5 Với ñiểm ñầu tiên (0,R), ta có: 1 1 1 5 p1 = F(x1 + 1,y1 - ) = F(1,R - ) = 1 + (R - )2 - R2 = - R 2 2 2 4 1. THUẬT TOÁN VẼ ELLIPSE ðể ñơn giản, ta chọn Ellipse có tâm ở gốc tọa ñộ. Phương trình của nó có dạng: x2 y2 + =1 a2 b2 b2 2 Ta có thể viết lại: y2 = - 2 .x + b2 (*) a *Ý tưởng: Giống như thuật toán vẽ ñường tròn.7 Chỉ có sự khác biệt ở ñây là ta phải vẽ 2 nhánh: Một nhánh từ trên xuống và một nhánh từ dưới lên và 2 nhánh này sẽ gặp nhau tại ñiểm mà ở ñó hệ số góc của tiếp tuyến với Ellipse = -1 (Hình 1. Phương trình tiếp tuyến với Ellipse tại ñiểm (x0,y0) ∈ (E) : 16 Chương I.
Các yếu tố cơ sở của ñồ họa x y x0 .b 2 Suy ra, hệ số góc của tiếp tuyến tại ñiểm ñó là: -. Thuật toán Bresenham Ở ñây, ta chỉ xét nhánh vẽ từ trên xuống. Giả sử ñiểm (xi,yi) ñã ñược vẽ. ðiểm tiếp theo cần chọn sẽ là (xi+1,yi) hoặc (xi+1,yi-1) b2 Thay (xi +1) vào (*): y2 = - 2 .(xi +1)2 + b2 a ðặt: b2 d1= yi2 - y2 = yi2 + 2 .(yi+12 + yi+1) -1 a Suy ra: b2 pi+1 - pi = 2.(2x + 3) - 4yi a2 Với ñiểm ñầu tiên (0,b), ta có: b2 p1 = 2 - 2b + 1 a2 Từ ñó, ta có thủ tục vẽ Ellipse như sau: 17 Chương I.
Các yếu tố cơ sở của ñồ họa Procedure Ellipse(xc,yc,a,b:Integer;Color:Byte); Var p,a2,b2:real; x,y:integer; (*-------------------*) Procedure VeDiem; Begin PutPixel(xc+x,yc+y,Color); PutPixel(xc-x,yc+y,Color); PutPixel(xc-x,yc-y,Color); PutPixel(xc+x,yc-y,Color); End; (*-------------------*) Begin a2:=a*a; b2:=b*b; {Nhanh 1} x:=0; y:=b; p:=2*b2/a2 - 2*b + 1; While (b2/a2)*(x/y)<1 do Begin VeDiem; If p<0 then p:=p + 2*(b2/a2)*(2*x+3) else Begin p:=p - 4*y + 2*(b2/a2)*(2*x+3); y:=y-1; End; x:=x+1; End; {Nhanh 2} y:=0; x:=a; p:=2*(a2/b2) - 2*a + 1; While (a2/b2)*(y/x)<=1 do 18 Chương I. Các yếu tố cơ sở của ñồ họa Begin VeDiem; If p<0 then p:=p + 2*(a2/b2)*(2*y+3) else Begin p:=p - 4*x + 2*(a2/b2)*(2*y+3); x:=x-1; End; y:=y+1; End; End; 1. Thuật toán MidPoint Gợi ý: x2 y2 Phương trình Ellipse: + =1 a2 b2 Nhánh 1: 1 2 p1 = b2 - a 2 b + .a 4 If pi < 0 Then pi+1 = pi + b2 + 2b2xi+1 else pi+1 = pi + b2 + 2b2xi+1 - 2a2yi+1 Nhánh 2: 1 2 p1 = b2(xi + ) + a2(yi - 1)2 - a2b2 2 If pi > 0 Then pi+1 = pi + a2 - 2a2yi+1 else pi+1 = pi + a2 + 2b2xi+1 - 2a2yi+1 Procedure MidEllipse(xc,yc,a,b:Integer;Color:Byte); Var p,a2,b2:real; x,y:Integer; (*-------------------*) Procedure VeDiem; Begin PutPixel(xc+x,yc+y,Color); PutPixel(xc-x,yc+y,Color); PutPixel(xc-x,yc-y,Color); 19 Chương I. Các yếu tố cơ sở của ñồ họa PutPixel(xc+x,yc-y,Color); End; (*-------------------*) Begin a2:=a*a; b2:=b*b; {Nhanh 1} x:=0; y:=b; Vediem; p:=b2 - a2*b + 0.25*a2; While (b2/a2)*(x/y)<1 do Begin x:=x+1; If p<0 Then p:=p + b2 + 2*b2*x else begin y:=y-1; p:=p + b2 + 2*b2*x - 2*a2*y; end; Vediem; End; {Nhanh 2} p:=b2*(x+0.5) + a2*(y-1)*(y-1)- a2*b2 ; While y>0 do Begin y:=y-1; If p>0 Then p:=p + a2 - 2*a2*y else begin x:=x+1; p:=p + a2 + 2*b2*x - 2*a2*y; end; Vediem; End; 20 Chương I.
Các yếu tố cơ sở của ñồ họa End; 1. PHƯƠNG PHÁP VẼ ðỒ THỊ HÀM SỐ 1. Bài toán: Vẽ ñồ thị của hàm số y = f(x) trên ñoạn [Min,Max]. *Ý tưởng: Cho x chạy từ ñầu ñến cuối ñể lấy các tọa ñộ (x,f(x)) sau ñó làm tròn thành số nguyên rồi nối các ñiểm ñó lại với nhau.
Giải thuật: • Bước 1: Xác ñịnh ñoạn cần vẽ [Min,Max]. • Bước 2: - ðặt gốc tọa ñộ lên màn hình (x0,y0). - Chia tỷ lệ vẽ trên màn hình theo hệ số k. - Chọn bước tăng dx của mỗi ñiểm trên ñoạn cần vẽ.
• Bước 3: Chọn ñiểm ñầu cần vẽ: x = Min, tính f(x) ðổi qua tọa ñộ màn hình và làm tròn: x1:=x0 + Round(x.k); Di chuyển ñến (x1,y1): MOVETO(x1,y1); • Bước 4: Tăng x lên với số gia dx: x:=x + dx; ðổi qua tọa ñộ màn hình và làm tròn: x2:=x0 + Round(x.k); Vẽ ñến (x2,y2): LINETO(x2,y2); • Bước 5: Lặp lại bước 4 cho ñến khi x > Max thì dừng.