Giáo trình Đồ họa

Nội dung text: Giáo trình Đồ họa

1. một hình khép kín và các đoạn có thể cắt lẫn nhau. Điểm giao của hai đoạn thẳng đƣợc gọi là đỉnh. Các đƣờng gấp khúc đƣợc xác định qua danh sách các đỉnh, mỗi đỉnh đƣợc cho bởi các cặp tọa độ xi , yi . Một đa giác là một đƣờng gấp khúc có điểm đầu và điểm cuối trùng nhau. (a) (b) Hình 2.6 – Đƣờng gấp khúc (a) và đa giác (b) Các thuộc tính của đoạn thẳng bao gồm : Màu sắc Độ rộng của nét vẽ. Kiểu nét vẽ của đoạn thẳng : có thể là một trong các dạng nhƣ hình 2.7. Hầu hết các công cụ đồ họa đều định nghĩa tập các kiểu nét vẽ đoạn thẳng có thể dùng và cho phép ngƣời dùng định nghĩa kiểu đoạn thẳng của mình thông qua một mẫu (pattern) gồm các số 0, 1. Đối với đƣờng gấp khúc, các đoạn thẳng trong cùng một đƣờng gấp khúc thì có cùng một thuộc tính. Hình 2.7 – Một số kiểu nét vẽ của đoạn thẳng 4.4. Vùng tô Một vùng tô bao gồm đƣờng biên và vùng bên trong. Đƣờng biên là một đƣờng khép kín ví dụ nhƣ đa giác. Các thuộc tính của vùng tô bao gồm: Thuộc tính của đƣờng biên : chính là các thuộc tính nhƣ thuộc tính của đoạn thẳng. Thuộc tính của vùng bên trong : bao gồm màu tô và mẫu tô. Hình 2.8 – Vùng tô với các dạng đƣờng biên và mẫu tô khác nhau 4.5. Kí tự, chuỗi kí tự Các chuỗi kí tự giúp hiển thị nội dung các thông điệp theo một ngôn ngữ nào đó. Các thuộc tính của kí tự bao gồm : Màu sắc của các kí tự. Font chữ : bộ kí tự dùng hiển thị; Nó định nghĩa kiểu, kích thƣớc của kí tự hiển thị. Hình dạng của mỗi kí tự có thể đƣợc xác định bởi một tập các đƣờng gấp khúc (trƣờng hợp font vector) hay là mẫu các pixel (font bitmap). Có nhiều loại font khác nhau nhƣ font bitmap, font truetype, font CHR, Kích thƣớc : chiều cao và chiều rộng của kí tự. Các kí tự định nghĩa bằng đƣờng gấp khúc có thể dễ dàng thay đổi kích thƣớc hơn là các kí tự định nghĩa bằng mẫu các pixel. Khoảng cách giữa các kí tự. Sự canh chỉnh (gióng lề) : canh trái (left text), canh phải (right text), canh giữa (center text), canh đều nhau (justify text). Cách hiển thị tuần tự của các kí tự : có thể là phải sang trái, từ trên xuống dƣới, từ trái sang phải, từ dƣới lên trên. Hƣớng của kí tự. Hình 2.9 – Dạng bitmap và vector của font kí tự B 5. CÁC THUẬT TOÁN VẼ ĐƢỜNG Giả sử tọa độ các điểm nguyên sau khi xấp xỉ đối tƣợng thực lần lƣợt là xi , yi ,i 0, Đây là các điểm nguyên sẽ đƣợc hiển thị trên màn hình. Bài toán đặt ra là nếu biết đƣợc xi , yi là tọa độ nguyên xác định ở bƣớc thứ i, điểm nguyên tiếp theo xi 1 , yi 1 sẽ 13
2. đƣợc xác định nhƣ thế nào. Nhận xét rằng để đối tƣợng hiển thị trên lƣới nguyên đƣợc liền nét, các điểm mà 4 3 2 xi 1 , yi 1 có thể chọn chỉ là một trong tám điểm đƣợc đánh số từ 1 đến 8 trong hình 2.10 (điểm đen chính là xi , yi ).Hay nói cách khác : xi 1 , yi 1 xi 1, yi 1 . 5 1 Dáng điệu của đƣờng sẽ cho ta gợi ý khi chọn một trong tám điểm trên. Cách chọn các 6 7 8 điểm nhƣ thế nào sẽ tùy thuộc vào từng thuật toán trên cơ sở xem xét tới vấn đề tối ƣu tốc độ. Hình 2.10 – Các điểm có thể chọn ở bƣớc (i+1) 5.1. Thuật toán vẽ đoạn thẳng Xét đoạn thẳng có hệ số góc 0 m 1và Dx 0. (xi+1, yi+1) Với các đoạn thẳng dạng này, nếu là điểm đã xác định đƣợc ở bƣớc thứ i 2 (điểm màu đen) thì điểm cần chọn x , y ở bƣớc thứ (i+1) sẽ là một trong hai trƣờng y (x +1, y ) i 1 i 1 i 1 i i hợp nhƣ hình vẽ sau : Hình 2.11 – Các điểm chọn ở bƣớc (i+1) cho trƣờng hợp x đoạn thẳng có hệ số góc 0<m<1 i xi 1 xi 1 Nhƣ vậy : yi 1 yi , yi 1 Vấn đề còn lại là cách chọn một trong hai điểm trên nhƣ thế nào để có thể tối ƣu về mặt tốc độ. 5.1.1. Thuật toán DDA (Digital Differential Analyzer) Với thuật toán DDA, việc quyết định chọn yi 1 là yi hay yi 1 , dựa vào phƣơng trình (xi+1, Round(y)) của đoạn thẳng y mx b. Nghĩa là, ta sẽ tính tọa độ của điểm xi 1, y thuộc về đoạn thẳng thực. Tiếp đó, sẽ là giá trị sau khi làm tròn giá trị tung độ y. (x +1, y) y m x 1 b i Nhƣ vậy : i yi 1 Round y (xi, yi) Hình 2.12 – Minh họa thuật toán DDA Nếu tính trực tiếp giá trị thực y ở mỗi bƣớc từ phƣơng trình thì phải cần một phép toán nhân và một phép toán cộng số Begin thực. Để cải thiện tốc độ, ngƣời ta tính giá trị thực của y ở mỗi bƣớc theo cách sau để khử phép tính nhân trên số thực : Nhận xét rằng : ysau mxi 1 b m xi 1 b m=Dy/Dx; x=x1; ytröôùc mxi b y=y1; putpixel(x, Round(y), c); ysau ytröôùc m x<x2 No Yes x=x+1; y=y+m; putpixel(x, Round(y),c); Lƣu đồ thuật toán DDA vẽ đoạn thẳng qua hai điểm (x , y ) và (x ,y ) 1 1 2 2 End 14
3. Cài đặt minh họa thuật toán DDA #define Round(a) int(a+0.5) int Color = GREEN; void LineDDA (int x1, int y1, int x2, int y2) { int x = x1; float y = y1; float m = float(y2-y1)/(x2-x1); putpixel(x, Round(y), Color); for(int i=x1; i<x2; i++) { x++; y +=m; putpixel(x, Round(y), Color); } } // LineDDA Nhận xét Việc sử dụng công thức ysau ytröôùc m để tính giá trị y tại mỗi bƣớc đã giúp cho thuật toán DDA nhanh hơn hẳn so với cách tính y từ phƣơng trình y mx b do khử đƣợc phép nhân trên số thực. Tuy nhiên, việc cộng dồn giá trị thực m vào y có thể sẽ tích lũy sai số làm cho hàm làm tròn có kết quả sai dẫn tới việc xác định vị trí của điểm vẽ ra bị chệch hƣớng so với đƣờng thẳng thực. Điều này chỉ xảy ra khi vẽ đoạn thẳng khá dài. Tuy đã khử đƣợc phép nhân số thực nhƣng thuật toán DDA vẫn còn bị hạn chế về mặt tốc độ do vẫn còn phép toán cộng số thực và làm tròn. Có thể khắc phục thao tác cộng số thực m và làm tròn trong Dy thuật toán bằng cách nhận xét m với Dy, Dx là các số nguyên. (xi+1, y) Dx P yi+1 d2 5.1.2. Thuật toán Bresenham y d Thuật toán Bresenham đƣa ra cách chọn y là y hay y 1 theo 1 i 1 i i y S một hƣớng khác sao cho có thể tối ƣu hóa về mặt tốc độ so với thuật toán i DDA. Vấn đề mấu chốt ở đây là làm thế nào để hạn chế tối đa các phép toán trên số thực trong thuật toán. xi xi+1 Hình 2.13 – Minh họa thuật toán Bresenham Gọi xi 1, y là điểm thuộc đoạn thẳng. Ta có: y m xi 1 b . d y y Đặt 1 i d2 yi 1 y Xét tất cả các vị trí tƣơng đối của y so với và , việc chọn điểm xi 1 , yi 1 là S hay P phụ thuộc vào việc so sánh d1 và d2 hay dấu của d1 d2 : Nếu d1 d2 0 , ta sẽ chọn điểm S, tức là yi 1 yi . Ngƣợc lại, nếu d1 d2 0 , ta sẽ chọn điểm P, tức là yi 1 yi 1 . Xét pi Dx d1 d2 Dx 2y 2yi 1 pi Dx2 m xi 1 b 2yi 1 15
4. Dy Thay m vào phƣơng trình trên ta đƣợc : p 2Dyx 2Dxy c , với c 2Dy 2b 1 Dx . Dx i i i Nhận xét rằng do Dx 0 nên dấu của biểu thức d1 d2 cũng chính là dấu của pi . Hay nói một cách khác, 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). Vấn đề còn lại là làm thế nào để tính đƣợc tại mỗi bƣớc thật nhanh. Ta có : pi 1 pi 2Dyxi 1 2Dxyi 1 c 2Dyxi 2Dxyi c pi 1 pi 2Dy xi 1 xi 2Dx yi 1 yi pi 1 pi 2Dy 2Dx yi 1 yi , do xi 1 xi 1 Từ đây ta có thể suy ra cách tính pi 1 từ nhƣ sau : Nếu pi 0 thì pi 1 pi 2Dy do ta chọn yi 1 yi . Ngƣợc lại, nếu pi 0, thì pi 1 pi 2Dy 2Dx , do ta chọn yi 1 yi 1 . Giá trị p0 đƣợc tính từ điểm vẽ đầu tiên x0 , y0 theo công thức : p0 2Dyx0 2Dxy0 c 2Dyx0 2Dxy0 2Dy 2b 1 Dx Dy Do là điểm nguyên thuộc về đoạn thẳng nên ta có y mx b x b . Thế vào phƣơng trình trên ta 0 0 Dx 0 suy ra : p0 2Dy Dx . Lƣu đồ thuật toán Bresenham Begin p=2Dy-Dx; Const1=2Dy; Const2=2(Dy-Dx); x=x1; y=y1; putpixel(x, y, c); x<x2 No Yes p<0 No Yes p=p+Const1; p=p+Const2; y=y+1 x=x+1; putpixel(x,y,c); End 16
5. Cài đặt minh họa thuật toán Bresenham void LineBres (int x1, int y1, int x2, int y2) { int Dx, Dy, p, Const1, Const2; int x, y; Dx = x2 - x1; Dy = y2 - y1; p = 2*Dy - Dx; // Dy <<1 - Dx Const1 = 2*Dy; // Dy <<1 Const2 = 2*(Dy-Dx); // (Dy-Dx) <<1 x = x1; y = y1; putpixel(x, y, Color); for(i=x1; i<x2; i++) { if (p<0) p += Const1; else { p += Const2; y++; } x++; putpixel(x, y, Color); } } // LineBres Nhận xét Thuật toán Bresenham chỉ làm việc trên số nguyên và các thao tác trên số nguyên chỉ là phép cộng và phép dịch bit (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ằm ở 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 bằng các phép toán đơn giản trên số nguyên. Thuật toán này cho kết quả tƣơng tự nhƣ thuật toán DDA. 5.1.3. Thuật toán MidPoint Q(xi+1, y) y+1 P Thuật toán MidPoint đƣa ra cách chọn yi 1 là yi hay yi 1 bằng cách so sánh i điểm thực Q xi 1, y với điểm MidPoint là trung điểm của S và P. Ta có : MidPoint y S Nếu điểm Q nằm dƣới điểm MidPoint, ta chọn S. i Ngƣợc lại nếu điểm Q nằm trên điểm MidPoint ta chọn P. xi xi+1 Hình 2.14 – Minh họa thuật toán MidPoint 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 y1 x1 y2 Đặt F x, y Ax By C , ta có nhận xét : 17
6. 0,neáu x, y naèm phía treân ñöôøng thaúng F x, y 0,neáu x, y thuoäc veà ñöôøng thaúng 0,neáu x, y naèm phía döôùi ñöôøng thaúng. 1 Lúc này việc chọn các điểm S, P ở trên đƣợc đƣa về việc xét dấu của pi 2F MidPoint 2F xi 1, yi . 2 Nếu pi 0, điểm MidPoint nằm phía trên đoạn thẳng. Lúc này điểm thực Q nằm dƣới điểm MidPoint nên ta chọn S, tức là yi 1 yi . Ngƣợc lại, nếu pi 0, điểm MidPoint nằm phía dƣới đoạn thẳng. Lúc này điểm thực Q nằm trên điểm MidPoint nên ta chọn P, tức là yi 1 yi 1 . Mặt khác : 1 1 pi 1 pi 2F xi 1 1, yi 1 2F xi 1, yi 2 2 1 1 pi 1 pi 2 A xi 1 1 B yi 1 C 2 A xi 1 B yi C 2 2 pi 1 pi 2A 2B yi 1 yi 2Dy 2Dx yi 1 yi Vậy : pi 1 pi 2Dy , nếu do ta chọn . pi 1 pi 2Dy 2Dx , nếu do ta chọn . Ta tính giá trị p0 ứng với điểm ban đầu x0 , y0 , với nhận xét rằng x0 , y0 là điểm thuộc về đoạn thẳng, tức là có : Ax 0 By0 C 0 1 1 p0 2F x0 1, y0 2 A x0 1 B y0 C 2 2 p0 2 Ax 0 By0 C 2A B 2A B 2Dy Dx Nhận xét rằng thuật toán MidPoint cho kết quả tƣơng tự nhƣ thuật toán Bresenham. 5.2. Thuật toán vẽ đƣờng tròn Phƣơng trình đƣờng tròn có tâm là gốc tọa độ, bán kính R là : x2 y2 R2 . Từ phƣơng trình này ta có thể đƣa về 2 2 dạng y R x . Để vẽ các đƣờng tròn có tâm xC , yC bất kì, đơn giản chỉ cần tịnh tiến các điểm sau khi vẽ xong đƣờng tròn có tâm là gốc tọa độ theo vector tịnh tiến . 5.2.1. Một số cách tiếp cận vẽ đƣờng tròn Do tính đối xứng nên để vẽ toàn bộ đƣờng tròn, ta chỉ cần vẽ cung ¼ đƣờng tròn sau đó lấy đối xứng để xác định các điểm còn lại. Một trong những cách đơn giản nhất là cho x chạy từ 0 đến R, sau đó tính y từ công thức trên (chỉ lấy giá trị dƣơng) rồi làm tròn để xác định giá trị nguyên tƣơng ứng. Cách làm này không hiệu quả do gặp phải các phép toán nhân và lấy căn làm hạn chế tốc độ, ngoài ra đƣờng tròn vẽ ra theo cách này có thể không liền nét (trừ trƣờng hợp R lớn) khi x gần R (do chỉ có một giá trị y duy nhất cho một giá trị x). Chúng ta có thể khắc phục điều này bằng cách điều chỉnh đối tƣợng thay đổi là x (rồi tính y theo x) hay y (rồi tính x theo y) tùy vào giá trị tuyệt đối của hệ số góc đƣờng tròn là lớn hơn hay nhỏ hơn 1, nhƣng cách làm này đòi hỏi thêm các phép tính toán và kiểm tra nên làm cho thuật toán phức tạp thêm. (Xem hình 2.15) Một cách tiếp cận khác là vẽ các điểm Rcos  , Rsin  , với  chạy từ 00 đến 0 90 . Cách này sẽ khắc phục hạn chế đƣờng không liền nét của thuật toán trên, tuy nhiên (0,17) điểm hạn chế chính của thuật toán này đó là chọn bƣớc nhảy cho nhƣ thế nào cho phù hợp khi bán kính thay đổi. Hình 2.15 – Đƣờng tròn vẽ ra không liền nét theo cách vẽ trên 5.2.2. Thuật toán MidPoint Do tính đối xứng của đƣờng tròn (C) nên ta chỉ cần vẽ cung (C1/8) là cung 1/8 đƣờng 18 (17,0)
7. tròn, sau đó lấy đối xứng. Cung (C1/8) đƣợc mô tả nhƣ sau (cung của phần tô xám (-x,y) (x,y) trong hình vẽ) : (-y,x) (y,x) 2 0 x R 2 R 2 (-y,-x) 2 (y,-x) R y R 2 Hình 2.16 – Các vị trí đối xứng trên đƣờng tròn (C) tƣơng ứng với (x,y) (-x,-y) (x,-y) Nhƣ vậy nếu có (x, y) (C1/8) thì các điểm : (y, x), (y,-x), (x,-y), (-x,-y), (-y,- x), (-y,x), (-x,y) sẽ thuộc (C). Chọn điểm bắt đầu để vẽ là điểm (0,R). Dựa vào hình vẽ, nếu xi , yi là Q(xi+1, y) điểm nguyên đã tìm đƣợc ở bƣớc thứ i, thì điểm x y ở bƣớc thứ (i+1) là S i 1 , i 1 yi sự lựa chọn giữa S và P. MidPoint xi 1 xi 1 y-1 P Nhƣ vậy : i yi 1 yi , yi 1 Tƣơng tự nhƣ thuật toán MidPoint vẽ đoạn thẳng, việc quyết định chọn một trong hai điểm S và P sẽ đƣợc thực hiện thông qua việc xét dấu của một hàm nào đó tại điểm MidPoint là điểm nằm giữa chúng. Hình 2.17 – Thuật toán MidPoint vẽ đƣờng tròn xi xi+1 Đặt F x, y x2 y2 R2 , ta có : 0,neáu x, y naèm trong ñöôøng troøn F x, y 0,neáu x, y naèm treân ñöôøng troøn 0,neáu x, y naèm ngoaøi ñöôøng troøn. 1 Xét pi F MidPoint F xi 1, yi . Ta có : 2 Nếu pi 0, điểm MidPoint nằm trong đƣờng tròn. Lúc này điểm thực Q gần S hơn nên ta chọn S, tức là yi 1 yi . Ngƣợc lại, nếu pi 0, điểm MidPoint nằm ngoài đƣờng tròn. Lúc này điểm thực Q gần P hơn nên ta chọn P, tức là yi 1 yi 1. Mặt khác : 1 1 pi 1 pi F xi 1 1, yi 1 F xi 1, yi 2 2 2 2 2 1 2 2 1 2 pi 1 pi xi 1 1 yi 1 R xi 1 yi R 2 2 2 2 2 1 2 1 p p x 2 y R2 x 1 y R2 i 1 i i i 1 i i 2 2 2 2 pi 1 pi 2xi 3 yi 1 yi yi 1 yi Vậy : pi 1 pi 2xi 3, nếu do ta chọn . pi 1 pi 2xi 2yi 5 , nếu do ta chọn yi 1 yi 1. Ta tính giá trị p0 ứng với điểm ban đầu x0 , y0 0, R . 1 1 5 p0 F x0 1, y0 F 1, R R 2 2 4 19
8. Lƣu đồ thuật toán MidPoint vẽ đƣờng tròn Begin p=5/4-R; x=0; y=R; Put8Pixel(x, y, c); x<y No Yes p<0 No Yes p=p+2*x+3; p=p+2(x-y)+5; y=y-1 x=x+1; Put8Pixel(x,y,c); End Cài đặt minh họa thuật toán MidPoint vẽ đƣờng tròn // Ve 8 diem doi xung void Put8Pixel(int x, int y) { putpixel(x, y, Color); putpixel(y, x, Color); putpixel(y, -x, Color); putpixel(x, -y, Color); putpixel(-x, -y, Color); putpixel(-y, -x, Color); putpixel(-y, x, Color); putpixel(-x, y, Color); } // Put8Pixel void CircleMidPoint (int R) 20
9. { int x, y; x = 0; y = R; Put8Pixel(x, y); p = 1 - R; // 5/4-R while (x < y) { if (p < 0) p += 2*x + 3; else { p += 2*(x -y) + 5; y ; } x++; Put8Pixel(x, y); } } // CircleMidPoint 5.3. Thuật toán vẽ các đƣờng conics và một số đƣờng cong khác Phƣơng trình tổng quát của các đƣờng conics có dạng : Ax 2 Bxy Cy 2 Dx Ey F 0 . Giá trị của các hằng số A, B, C, D, E, F sẽ quyết định dạng của đƣờng conics, cụ thể là nếu: 0, daïng ñöôøng troøn (neáu A C vaø B 0 ) hay ellipse B2 4AC 0, daïng parabol 0, daïng hyperbol. Ta sẽ áp dụng ý tƣởng của thuật toán MidPoint để vẽ các đƣờng conics và một số đƣờng cong khác, theo các bƣớc tuần tự sau: Bƣớc 1 : Dựa vào dáng điệu và phƣơng trình đƣờng cong, để xem thử có thể rút gọn phần đƣờng cong cần vẽ hay không. Điều này sẽ làm tăng tốc độ vẽ so với việc phải vẽ toàn bộ đƣờng cong. Một trong những cách đơn giản nhất là dựa vào tính đối xứng, tính chất của hàm chẵn, hàm lẻ,  Bƣớc 2 : Tính đạo hàm để từ đó phân thành các vùng vẽ : xi 1 xi 1 Nếu 0 f '(x) 1 thì yi 1 yi , yi 1 (*) xi 1 xi 1 Nếu 1 f '(x) 0 thì yi 1 yi , yi 1 (*) yi 1 yi 1 Nếu f '(x) 1 thì xi 1 xi , xi 1 (*) yi 1 yi 1 Nếu f '(x) 1 thì xi 1 xi , xi 1 (*) Đây là bƣớc quan trọng vì với việc xác định đối tƣợng x hay y biến thiên theo dáng điệu của đƣờng cong sẽ đảm bảo đƣờng sau khi đƣợc vẽ ra sẽ liền nét, không bị hở. 21
10. Bƣớc 3 : Xác định công thức của pi cho từng trƣờng hợp để quyết định (*) dựa trên dấu của pi . pi thƣờng là hàm đƣợc xây dựng từ phƣơng trình đƣờng cong để cho pi 0 nếu xi ,yi thuộc về đƣờng cong. Việc chọn cần phải chú ý sao cho thao tác tính sau này hạn chế phép toán trên số thực. Bƣớc 4 : Tìm mối liên quan của pi 1 và bằng cách xét hiệu pi 1 pi . Bƣớc 5 : Tính p0 và hoàn chỉnh thuật toán. 6. CÁC THUẬT TOÁN TÔ MÀU Các vùng tô là một trong những đối tƣợng đồ họa cơ sở đƣợc hầu hết các công cụ lập trình đồ họa hỗ trợ. Có hai dạng vùng tô thƣờng gặp đó là : tô bằng một màu thuần nhất (solid fill) hay tô theo một mẫu tô (fill-pattern) nào đó. Một vùng tô thƣờng đƣợc xác định bởi một đƣờng khép kín nào đó gọi là đƣờng biên. Một trong những dạng đƣờng biên đơn giản nhất đó là đa giác. Để tô màu một vùng tô, ngƣời ta thƣờng chia làm hai công đoạn : công đoạn thứ nhất là xác định các điểm nào để tô và công đoạn còn lại đơn giản hơn đó là quyết định tô các điểm đó bằng giá trị màu nào. Công đoạn thứ hai chỉ thực sự phức tạp nếu ta tô theo một mẫu tô nào đó không phải là tô thuần một màu. Có hai cách tiếp cận chính để tô màu một vùng tô đối với thiết bị hiển thị dạng điểm đó là : tô theo dòng quét (scan-line fill) và tô dựa theo đƣờng biên (boundary fill). Phƣơng pháp tô theo dòng quét sẽ xác định các phần giao của các dòng quét kế tiếp nhau với đƣờng biên của vùng tô, sau đó sẽ tô màu các điểm thuộc về phần giao này. Cách tiếp cận này thƣờng đƣợc dùng để tô màu các đa giác, đƣờng tròn, ellipse, và một số đƣờng cong đơn giản khác. Phƣơng pháp tô dựa theo đƣờng biên sẽ bắt đầu từ một điểm ở bên trong vùng tô và từ đó loang dần ra cho tới khi ta gặp các điểm biên. Cách tiếp cận này thƣờng đƣợc dùng cho các vùng tô có dạng đƣờng biên phức tạp hơn. 6.1. Thuật toán tô màu dựa theo dòng quét y ytop Giả sử vùng tô đƣợc cho bởi một đa giác N đỉnh : Pi xi , yi ,i 0, N 1 . Đa giác này có thể là đa giác lồi, đa giác lõm, và cả đa giác tự cắt, Hình 2.18 sau minh họa ý tƣởng chính của thuật toán. Với mỗi dòng quét, ta sẽ xác định phần giao của đa giác và dòng quét rồi tô màu các pixel thuộc đoạn 0 1 2 3 giao đó. Để xác định các đoạn giao ta tiến hành việc tìm giao điểm của dòng quét với các cạnh của đa giác, sau đó các giao điểm này sẽ đƣợc sắp theo thứ tự tăng dần của hoành độ giao điểm. Các đoạn giao chính là các đoạn thẳng đƣợc giới hạn ybottom bởi từng cặp giao điểm một, ví dụ nhƣ (0,1), (2,3), . O x Hình 2.18 – Thuật toán scan-line với một dòng quét nào đó Ta có thể tóm bắt các bƣớc chính của thuật toán : Tìm ytop , ybottom lần lƣợt là giá trị lớn nhất, nhỏ nhất của tập các tung độ của các đỉnh của đa giác đã cho ytop max yi , xi , yi P, ybottom min yi , xi , yi P. Ứng với mỗi dòng quét y k , với k thay đổi từ đến ytop , lặp :  Tìm tất cả các hoành độ giao điểm của dòng quét y k với các cạnh của đa giác.  Sắp xếp các hoành độ giao điểm theo thứ tự tăng dần : x0, x1,  Tô màu các đoạn thẳng trên đƣờng thẳng y k lần lƣợt đƣợc giới hạn bởi các cặp x0 , x1 , x2 , x3 , , x2k , x2k 1 . Nếu chỉ dừng ở mức này và chuyển sang cài đặt, chúng ta sẽ gặp một số vấn đề sau : Nhận xét rằng, ứng với mỗi dòng quét, không phải lúc nào tất cả các cạnh của đa giác cũng tham gia cắt dòng quét. Do đó để cải thiện tốc độ cần phải có một cách nào đó để hạn chế đƣợc số cạnh cần tìm giao điểm ứng với mỗi dòng quét. Việc tìm giao điểm của cạnh đa giác với mỗi dòng quét sẽ gặp các phép toán phức tạp nhƣ nhân, chia, trên số thực nếu ta dùng cách giải hệ phƣơng trình tìm giao điểm. Điều này sẽ làm giảm tốc độ thuật toán khi phải lặp đi lặp lại nhiều lần thao tác này khi dòng quét quét qua đa giác. Nếu số giao điểm tìm đƣợc giữa các cạnh đa giác và dòng quét là lẻ thì việc nhóm từng cặp giao điểm kế tiếp nhau để hình thành các đoạn tô có thể sẽ không chính xác. Điều này chỉ xảy ra khi dòng quét đi ngang qua các đỉnh của đa giác. Nếu tính số giao điểm tại đỉnh dòng quét đi ngang qua là hai thì có thể sẽ cho kết quả tô không chính xác nhƣ trong trƣờng hợp của hình 2.19. Ngoài ra, việc tìm giao điểm của dòng quét với các cạnh nằm ngang là một trƣờng hợp đặc biệt cần phải có cách xử lí thích hợp. 22