Đồ họa máy tính

- 2yi - 1 (2-4) Pi = cx (d1 - d2) = Δx[2m(xi+1) + 2b - 2yi - 1] = Δx[2 x y   ( xi + 1 ) + 2b – 2 yi - 1] 27 = 2Δy(xi+1) - 2Δx.yi + Δx(2b - 1) = 2Δy.xi - 2Δx.yi + 2Δy + Δx(2b - 1) Vậy C = 2Δy + Δx(2b - 1) = Const ⇒ Pi = 2Δy.xi - 2Δx.yi + C (2-5) Nhận xét rằng nếu tại bước thứ i ta xác định được dấu của Pi thì xem như ta xác định được điểm cần chọn ở bước (i+1). Ta có : Pi +1 - Pi = (2Δy.xi+1 - 2Δx.yi+1 + C) - (2Δy.xi - 2Δx.yi + C ) ⇔ Pi +1 = Pi + 2Δy - 2Δx ( yi+1 - yi )  Nếu Pi < 0 : chọn điểm P1, tức là yi +1= yi và Pi +1= Pi + 2Δy  Nếu Pi ≥ 0 : chọn điểm P2, tức là yi +1= yi +1 và Pi +1= Pi + 2Δy - 2Δx (2-6) Giá trị P0 được tính từ điểm vẽ đầu tiên (xo, yo) theo công thức: Po = 2Δy.xo - 2Δx.yo + C Do (xo ,yo ) là điểm nguyên thuộc về đoạn thẳng nên ta có: yo mx o +b= bx x y    0 Thay yo vào phương trình trên ta được: Po = 2Δy - Δx Nhận xét: Thuật toán Bresenham chỉ thao tác trên số nguyên và chỉ tính toán trên phép cộng và phép nhân 2. Điều này là một cải tiến làm tăng tốc độ đáng kể so với thuật toán DDA. Ý tưởng chính của thuật toán này là ở chổ xét dấu Pi để quyết định điểm kế tiếp, và sử dụng còng thức truy hồi Pi +1 Pi để tính Pi bằng các phép toán đơn giản trên số nguyên. Tuy nhiên, việc xây dựng trường hợp tổng quát cho thuật toán Bresenham có phức tạp hơn thuật toán DDA. Tóm lại: Để vẽ đường thẳng theo thuật toán Bresenham cho trường hợp hệ số góc 0<m<1 như sau: 28  Nhập A(x1,y1), B(x2, y2)  Tính Δx=x2 - x1 , Δ y =y2 - y1, P=2Δy – Δx , C1=2Δy, C2=2(Δy – Δx)  Điểm đầu tiên: x=x1, y=y1;  Điểm tiếp theo: x=x1+1, y=y1, Pi=Pi+C1. Nếu Pi<0 x=x1+1, y=y1+1, Pi=Pi+C2. Nếu Pi>0  Quá trình tiếp tục cho đến khi x>=x2 Hình 2.4: Giải thuật Bresenham vẽ đƣờng thẳng 29 Ví dụ: Hãy tìm các hệ số p và tọa độ các điểm sẽ nảy sinh của đoạn thẳng được vẽ theo giải thuật Bresenham, nếu biết đoạn thẳng đi qua hai điểm A(2,4) và B(5,8) với 0<m<=1 Theo thuật toán Bresenham Dx=x2-x1=3, Dy=y2-y1=4 P=2dy-dx=8-3=5 C1=2dy=8 C2=2(dy-dx)=2 Điểm A: x1=2, y1=4 *P = 5>0 P = P + C2 = 5 + 2 = 7 Điểm A1: x2=3, y2=5 *P=7>0  P= P + C2 = 7 + 2= 9 Điểm A2: x3=4, y3=6 *P=9>0  P=P + C2 = 9 + 2=11 Điểm A3: x4=5, y4=7 Ví X4=Xb=5 nên quá trính sinh điểm dừng. Vậy có 2 điểm phát sinh khi vẽ đường thẳng theo thuật toán Bresenham 2.2.4. Thuật toán MidPoint Thuật toán Midpoint đưa ra cách chọn điểm y p+1 là y p hay y p +1 dựa vào so sánh điểm thực Q(x p +1,y) với trung điểm M(x p +1,y p +1/2) của đoạn thẳng 30 Hình 2.5. Mô tả thuật toán MidPoint  Nếu Q nằm trên M thí chọn điểm NE(x p +1, y p +1)  Nếu Q nằm dưới M thí chọn điểm E(x p +1,y p ) Cơ sở toán học  F(x,y)<0 nếu (x,y) nằm phìa trên đường thẳng  F(x,y)= 0 nếu (x,y) thuộc đường thẳng  F(x,y)>0 nếu (x,y) nằm phìa dưới đường thẳng Cách thực hiện: Đặt Pp = F(M) = F(xp+1,yp+1/2)  Nếu Pp < 0 thí M nằm trên đường thẳng, chọn E  Nếu Pp >= 0 thí M nằm dưới hoặc thuộc đường thẳng, chọn NE 31 P p gọi là tham số quyết định. Dấu của nó sẽ quyết định lựa chọn điểm tiếp theo Tính Pp: P p = A(x p +1)+B(y p +1/2)+C Đặt P old = P p P old = A(x p +1)+B(y p +1/2)+C Nếu chọn E thì trung điểm mới: Mnew(xp+2,yp+1/2) PnewE = A(xp+2)+B(yp+1/2)+C PnewE = A(xp+1)+B(yp+1/2)+C + A PnewE = Pold + dy (vì A= dy) Nếu chọn NE thì trung điểm mới: M new (x p +2, y p +3/2) PnewNE = A(xp+2)+B(yp+3/2)+C PnewNE = A(xp+1)+B(yp+1/2)+C + A + B PnewNE = Pold + dy – dx (vì A= dy, B = - dx) Tính P 1 : M(x 1 +1, y 1 +1/2) P 1 = A(x 1 +1)+B(y 1 +1/2)+C Thay: A = dy; B = -dx, C= x 2 y 1 - x 1 y 2 dy = y 2 - y 1 ; dx = x 2 - x 1 vào P 1 P 1 = dy(x 1 +1) - dx(y 1 + 1/2) + x 2 y 1 - x 1 y 2 P 1 = dyx 1 + dy - dxy 1 - dx1/2+ x 2 y 1 - x 1 y 2 P 1 = y 2 x 1 - y 1 x 1 + dy - x 2 y 1 + x 1 y 1 - dx1/2 + x 2 y 1 - x 1 y 2 P 1 = dy-(1/2)dx Do chỉ xét dấu và để tránh chia hai: P 1 = 2dy-dx Tóm lại: Để vẽ đường thẳng theo thuật toán MidPoint cho 32 trường hợp hệ số góc 0<m<1 như sau:  Nhập A(x1,y1), B(x2, y2)  Tính Δx=x2 - x1, Δ y =y2 - y1, D= Δ y – Δx/2  Điểm đầu tiên: x=x1, y=y1;  Điểm tiếp theo: x=x1+1, y=y1, D=D+Δ y. Nếu D<=0 x=x1+1, y=y1+1, D=D+Δ y - Δx. Nếu D>0  Quá trình tiếp tục cho đến khi x>=x2 Hình 2.6. Giải thuật MidPoint để vẽ đƣờng thẳng 33 Vì dụ: Cho 2 điểm A(20,10), B(24,13). Hãy xác định giá trị di, xi, yi ở mỗi bước khi vẽ đoạn thẳng AB theo thuật toán Midpoint Theo giải thuật MidPoint Dx=x2-x1= 4, Dy=y2-y1= 3 D=Dy- Dx/2= 3 - 2 = 1 Điểm A: x1=20, y1=10 *D = 1>0 D = D + Dy - Dx = 1 + 3 - 4 = 0 Điểm A1: x2 = 21, y2=11 *D = 0=0  D= D + Dy = 0 + 3 = 3 Điểm A2: x3=22, y3=11 *D=3>0  D = D + Dy - Dx = 3 + 3 - 4=2 Điểm A3: x4=23, y4=12 *D=2>0  D = D + Dy - Dx = 2 + 3 - 4=1 Điểm A4: x5=24, y5=13 Vì X5=Xb=24 nên quá trính sinh điểm dừng. Vậy có 3 điểm phát sinh khi vẽ đường thẳng theo thuật toán MidPoint 2.3. Thuật toán vẽ đƣờng tròn, elip 34 Hình2.7: Đƣờng tròn với các điểm đối xứng Trong hệ tọa độ Descartes, phương trình đường tròn bán kính R có dạng: Tâm O(0,0) : x 2 + y 2 = R 2 ; Tâm C(xc,yc): (x - xc ) 2 + (y - yc ) 2 = R 2 (2-7) Trong hệ tọa độ cực :    2,0, Rsin y y Rcos xx c c       Do tình đối xứng của đường tròn C, nên ta chỉ cần vẽ 1/8 cung tròn, sau đó lấy đối xứng qua 2 trục tọa độ và 2 đường phân giác thì ta vẽ được cả đường tròn. 35 2.3.1. Thuật toán xét trung điểm Hình 2.8 Đƣờng tròn với điểm Q(xi +1, y) và trung điểm. Thuật toán trung điểm đưa ra cách chọn yi+1 là yi hay yi -1 bằng cách so sánh điểm Q(xi+1,y) với điểm giữa là trung điểm (Midpoint) của S1 và S2. Chọn điểm bắt đầu để vẽ là (0,R). Giả sử (xi, yi) là điểm nguyên đã tím được ở bước thứ i (xem hình 2.7), thì điểm (xi+1, yi+1) ở bước i+1 là sự lựa chọn giữa S1 và S2.              i i i ii y y y xx 1 1 1 1 Đặt F(x,y) = x2 + y2 - R2 , ta có :  F(x,y) < 0 , nếu điểm (x,y) nằm trong đường tròn.  F(x,y) = 0 , nếu điểm (x,y) nằm trên đường tròn. 36  F(x,y) > 0 , nếu điểm (x,y) nằm ngoài đường tròn. Xét Pi = F(MidPoint) = F(xi +1, yi - 1/2). Ta có :  Nếu Pi < 0 : điểm MidPoint nằm trong đường tròn. Khi đó, điểm Q gần với điểm S1 hơn nên ta chọn yi+1 = yi .  Nếu Pi >= 0 : điểm MidPoint nằm ngoài đường tròn. Khi đó, điểm Q gần với điểm S2 hơn nên ta chọn yi+1 = yi - 1. Mặt khác : Pi+1 - Pi = F(xi+1 +1, yi+1 - 1/2) - F(xi + 1, yi - 1/2) = [(xi+1 +1)2 + (yi+1 - 1/2) 2 - R 2 ] - [(xi +1) 2 + (yi - 1/2) 2 - R 2 ] = 2xi + 3 + ((yi+1) 2 - (yi) 2 ) - (y i+1 - yi) Vậy: Nếu Pi < 0 : chọn yi+1 = yi. Khi đó Pi+1 = Pi + 2xi +3 (2-8) Nếu Pi >= 0 : chọn yi+1 = yi - 1. Khi đó Pi+1 = Pi + 2xi - 2yi +5 Pi ứng với điểm ban đầu (xo , yo) = (0,R) là: Po = F(xo + 1, yo - 1/2) = F(1, R - 1/2) = 5/4 -R 37 Hình 2.9. Giải thuật MidPoint để vẽ đƣờng tròn 38 2.3.2. Thuật toán Bresenham Hình 2.10. Đƣờng tròn với khoảng cách d1 và d2 Tương tự thuật toán vẽ đường thẳng Bresenham, các vị trí ứng với các tọa độ nguyên nằm trên đường tròn có thể tính được bằng cách xác định một trong hai pixel gần nhất với đường tròn hơn trong mỗi bước. Ta có: d1 = (yi) 2 - y 2 = (yi) 2 - (R 2 - (xi + 1) 2 ) và d2 = y 2 - (yi - 1) 2 = (R 2 - (xi + 1) 2 ) - (yi - 1) 2 Đặt Pi = d1 - d2, do đó Pi+1 = Pi + 4xi + 6 + 2((yi+1) 2 - (yi) 2 ) - 2(yi+1 - yi)  Nếu Pi < 0 : chọn yi+1 = yi. Khi đó Pi+1 = Pi + 4xi +6 (2-9) Nếu Pi >= 0 : chọn yi+1 = yi - 1. Khi đó Pi+1 = Pi + 4(xi - yi ) + 10 Po ứng với điểm ban đầu (xo , yo) = (0,R) là: Po= 3 - 2R 39 Tóm lại, vẽ đường tròn theo thuật toán Bresenham gồm các bước sau: Bước 1: Chọn điểm đầu tiên cần vẽ (x1,y1) = (0,R) Tình P đầu tiên: P1 = 3 – 2R Bước 2: Nếu P <0: Chọn điểm kế tiếp là (xi + 1, yi). P=P+4x+6 Ngược lại chọn điểm (xi + 1, yi - 1) và P=P+4x-4y+10 Bước 3: x=x+1, tính lại P để xác định y Quá trình lặp lại khi x=y 40 Hình 2.11. Giải thuật Bresenham vẽ đƣờng tròn 41 2.3.3. Thuật toán vẽ elip Tương tự thuật toán vẽ đường tròn, sử dụng thuật toán Bresenham để vẽ, ta chỉ cần vẽ 1/4 ellipse, sau đó lấy đối xứng qua các trục tọa độ sẽ vẽ được tòan bộ ellipse. Xét ellipse có tâm O, các bán kính là a và b phương trính là: 12 2 2 2  b y a x Chọn tọa độ pixel đầu tiên cần hiển thị là (xi ,yi) = (0,b). Cần xác định pixel tiếp theo là (xi+1 ,yi+1). Ta có :              i i i ii y y y xx 1 1 1 1 d1=(yi) 2 – y2; d2=y2 – (yi - 1) 2 Đặt Pi = d1- d2, có Pi+1=Pi + 2((yi+1) 2 – (y Nếu Pi < 0 : chọn yi+1 = yi, P i 1 P i ( 2x i 3) (2-10) Nếu Pi >= 0 : chọn yi+1 = yi - 1, Po ứng với điểm ban đầu (xo, yo) = (0, b) là: BÀI TẬP Bài 1: Tại sao phải so sánh giá trị Pi với 0 trong các giải thuật Bresenham hay Midpoint. Bản chất của so sánh là gì? Bài 2: Cặt đặt các giải thuật Bresenham, MidPoint vẽ đường tròn và vẽ đoạn thẳng với hệ số góc trong khoảng [-1, 1]. Bài 3: Giải thích tại sao chỉ chọn cung 1/8 để vẽ rồi lấy đối xứng mà không mở rộng cho cung 1/16 hay 1/32. Bài 4: Cài đặt giải thuật vẽ elip có tâm là gốc tọa độ, bán kính trục chính, trục phụ là a, b. Bài 5: Cài đặt thuật toán tô Màu đường biên cho đối tượng hình tròn.