Bài giảng Cơ sở đồ họa máy tính (Phần 1)

a thuận được biết đến như là toàn bộ khoảng RGB. Thông thường, RGB cho video kỹ thuật số không phải là toàn bộ khoảng này. Thay vì thế video RGB sử dụng thỏa thuận với thang độ và các giá trị tương đối chẳng hạn như (16, 16, 16) là màu đen, (235, 235, 235) là màu trắng v.v.  Kiểu 16 bit: Còn có kiểu 16 bpp, trong đó hoặc là có 5 bit cho mỗi màu, gọi là kiểu 555 hay thêm một bit còn lại cho màu xanh lá cây (vì mắt có thể cảm nhận màu này tốt hơn so với các màu khác), gọi là kiểu 565. Kiểu 24 bpp nói chung được gọi là thật màu, trong khi kiểu 16 bpp được gọi là cao màu.  Kiểu 32 bit: Cái gọi là kiểu 32 bpp phần lớn là sự đồng nhất chính xác với kiểu 24 bpp, do ở đây thực sự cũng chỉ có 8 bit cho mỗi màu thành phần, tám bit dư đơn giản là không sử dụng (ngoại trừ khả năng sử dụng như là kênh alpha). Lý do của việc mở rộng của kiểu 32 bpp là vận tốc cao hơn mà phần lớn các phần cứng ngày nay có thể truy cập các dữ liệu được sắp xếp trong các địa chỉ byte có thể chia được ngang nhau theo cấp số của 2, so với các dữ liệu không được sắp xếp như vậy.  Kiểu 48 bit: "Kiểu 16-bit" cũng có thể để chỉ tới 16 bit cho mỗi màu thành phần, tạo ra trong kiểu 48 bpp. Kiểu này làm cho nó có khả năng biểu thị 65.535 sắc thái mỗi màu thành phần thay vì chỉ có 255. Nó đầu tiên được sử dụng trong chỉnh sửa hình ảnh chuyên nghiệp, như Photoshop của Adobe để duy trì sự chính xác cao hơn khi có hơn một thuật toán lọc hình ảnh được sử dụng đối với hình ảnh đó. Với chỉ có 8 bit cho mỗi màu, các sai số làm tròn có xu hướng tích lũy sau mỗi thuật toán lọc hình ảnh được sử dụng và làm biến dạng kết quả cuối cùng. 2.2.1.3. Ứng dụng RGB Được ứng dụng trong công nghệ chế tạo màn hình tivi, màn hình máy vi tính, kỹ thuật video, chiếu sáng 2.2.2. Mô hình màu CMY 2.2.2.1. Khái niệm  Mô hình CMY: là mô hình màu bù (Subtractive color models) hiển thị ánh sáng và màu sắc phản xạ từ mực in. - C=Cyan trong tiếng Anh có nghĩa là màu xanh lơ hay cánh chả Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 33 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông - M=Magenta trong tiếng Anh có nghĩa là màu cánh sen hay hồng sẫm - Y=Yellow trong tiếng Anh có nghĩa là màu vàng Khi bề mặt không phủ mực thì ánh sáng phản xạ là ánh sáng trắng. Khi có 3 màu có cùng giá trị cho ra màu xám. Khi các giá trị đạt max cho màu đen.  Mô hình màu bù (subtractive): sử dụng mực in - printing inks. Màu sắc cảm nhận được là từ ánh sáng phản xạ- reflected light (lấy màu trội). Từ lý thuyết cộng màu (1) ta có Hình 2.7. Lý thuyết trừ màu trắng – lục = magenta, (2) trắng – đỏ = cyan, (3) trắng – lam = vàng, (4) Điều này có nghĩa là loại 1 màu sơ cấp (thứ cấp) ra khỏi màu trắng thì được màu thứ cấp (sơ cấp) đối diện với nó qua trọng tâm tam giác màu. Đây là cơ sở của lý thuyết trừ màu.  Ví dụ 1: Hoa fuchsia Hình 2.8. Hoa fuchsia Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 34 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông Ví dụ đóa hoa fuchsia có màu magenta vì khi ánh sáng trắng chiếu vào, nó hấp thụ tia lục, chỉ phản xạ lại tia đỏ và lam. Đỏ và lam hòa với nhau tạo ra màu magenta trong thị giác: trắng – lục = (đỏ + lục + lam) – lục = đỏ + lam = magenta. Đây chính là quy tắc (2) ở trên.  Ví dụ 2: Đá ngọc lam Hình 2.9. Đá ngọc lam (turquoise) Viên ngọc lam (turquoise) có màu cyan vì khi ánh sáng trắng chiếu lên, nó hấp thụ ánh sáng đỏ và phản chiếu lại ánh sáng lục và lam. Ánh sáng lục và lam hoà với nhau trong thị giác thành màu cyan: trắng – đỏ = (đỏ + lục + lam) – đỏ = lục + lam = cyan. Đây chính là quy tắc (3) ở trên.  Ví dụ 3: Cái áo có màu vàng vì khi ánh sáng trắng chiếu vào, nó hấp thụ tia lam, chỉ phản xạ tia đỏ và lục. Đỏ và lục hòa với nhau tạo ra màu vàng trong thị giác: trắng – lam = (đỏ + lục + lam) – lam = đỏ + lục = vàng. Đây chính là quy tắc (4) ở trên. Từ các quy tắc (2) và (4) ta được: magenta + vàng = trắng – lục – lam =(đỏ + lục + lam) – lục – lam = đỏ (5) Từ các quy tắc (3) và (4) ta được: vàng + cyan = trắng – lam – đỏ =(đỏ + lục + lam) – lam – đỏ = lục (6) Từ các quy tắc (2) và (3) ta được: Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 35 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông cyan + magenta = trắng – đỏ – lục =(đỏ + lục + lam) – đỏ – lục = lam (7) Khi 3 màu magenta, cyan và vàng được trộn với nhau, magenta hấp thụ lục, cyan hấp thụ đỏ, còn vàng hấp thụ lam, tức là cả 3 ánh sáng sơ cấp đỏ, lục và lam đều bị hấp thụ, không có màu nào được phản xạ lại. Kết quả thị giác nhìn thấy màu đen: trắng – đỏ – lục – lam =(đỏ + lục + lam) – đỏ – lục – lam = đen (8) (5), (6), (7) và (8) chính là các quy tắc hòa sắc của 3 màu magenta, cyan, và vàng của phẩm nhuộm và chất màu tạo nên các màu hoá chất như màu vẽ và mực in – tức vật chất chỉ hấp thụ, phản xạ, và truyền ánh sáng chứ không phải là nguồn phát sáng. Quy tắc cộng màu của ánh sáng và trừ màu của màu hoá chất thường được biểu thị qua 2 sơ đồ dưới đây: Hình 2.10. Quy tắc cộng màu và trừ màu Tương tự như tam giác cộng màu cuả Maxwell ở H. 20, ta có tam giác trừ màu như sau: Hình 2.11. Tam giác trừ màu Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 36 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông Quy tắc trừ màu là âm bản của quy tắc cộng màu. Các màu sơ cấp (thứ cấp) trong quy tắc cộng màu là các màu thứ cấp (sơ cấp) trong quy tắc trừ màu. Vì thế quy tắc trừ màu với 3 màu sơ cấp là cyan (C), magenta (M) và vàng (Y) rất tiện lợi cho công nghệ in ấn khi chuyển đổi màu từ hệ thống RGB của trên màn hình, phim màu sang CMY của mực in. Hình 2.12. Mô hình màu CMY Trên thực tế, vì mực in không “tinh khiết” nên pha trộn C, M và Y chỉ cho màu xám. Do đó màu đen được thêm vào và ký hiệu là K (key). Tổ hợp của 4 màu CMYK cho tất cả các màu trong gam màu. Mô hình CMYK được Alexander Murray đề xuất áp dụng cho in ấn vào năm 1934. Trước đó người ta chưa tổng hợp được màu magenta dùng cho mực in (process magenta = magenta xử lý) bền với ánh sáng. Mô hình RGB và mô hình CMY chẳng qua chỉ là hai "cách nhìn" đối với màu sắc. Trong mô hình RGB, màu sắc được tạo ra bởi sự đóng góp của các thành phần RGB với cường độ khác nhau. Cường độ cao của các thành phần RGB cho ta màu trắng. Khi cường độ của chúng bằng 0, ta có màu đen (không có ánh sáng). Trong mô hình CMY, ta lại chú ý đến hiệu quả của các thành phần CMY trong việc trừ khử các thành phần RGB của ánh sáng tới. Liều lượng cao của các thành phần CMY cho ta màu đen. Liều lượng của chúng bằng 0 cho ta màu trắng (không có mực). Do vậy, người ta gọi mô hình RGB là mô hình màu cộng tính (additive) và mô hình CMY là mô hình màu hiệu tính (subtractive). Tuy hai mô hình màu này khác nhau như "mặt trời với mặt trăng", có công thức chính xác để chuyển đổi bộ ba trị số RGB thành bộ ba trị số CMY tương đương. Corel DRAW tính toán chuyện này cực nhanh, bạn không phải lo chi cả. Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 37 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông 2.2.2.2. Ứng dụng CMY - Dùng trong in ấn, in offset, in phun màu. Trong in ấn người ta dùng hệ màu CMYK vì các vật liệu in ấn (giấy, vải, gỗ, nilon) khổng thể tự phát sáng. Bằng việc phối trộn và thay đổi định lượng ba màu CMY ta có thể tạo ra được những màu khác nhau. Trên lý thuyết, khi phối trộn 3 màu này với nhau với cùng định lượng sẽ tạo ra màu đen. Tuy nhiên trong in ấn, người ta thêm màu Black(K) vào để tăng độ tương phản và giảm bớt lượng mực CMY để tạo ra màu đen. Khi thiết kế cho một sản phẩm in ấn, chúng ta nên dùng hệ màu CMYK nhằm giảm thiểu khả năng sai lệch màu của thiết kế sau in. Việc sửa màu là cần thiết vì các dữ liệu về màu có thể chuyển tới thiết bị in ấn trong các định dạng khác nhau như RGB hay CMYK. Vì các thiết bị in ấn điện tử hiện nay là thiết bị hỗ trợ CMYK, nên mọi dữ liệu màu sắc chuyển tới thiết bị in phải được chuyển đổi sang định dạng CMYK để chúng có thể sử dụng được bởi các thiết bị in ấn để đưa ra bản in chấp nhận được. Ví dụ phần lớn các ứng dụng thương mại nói chung có định dạng màu theo hệ RGB, nhưng các ứng dụng đồ họa như CorelDraw, Adobe Photoshop, Adobe Illustrator... nói chung định dạng màu sắc theo các giá trị CMYK, tuy có hỗ trợ chế độ màu RGB. Vì thế các chế độ sửa chữa màu khác nhau có thể được sử dụng phụ thuộc vào nguồn dữ liệu cũng như chất lượng bản in dự kiến. 2.2.3. Mô hình màu HSV 2.2.3.1. Khái niệm Các mô hình màu RGB, CMY, YIQ được định hướng cho phần cứng. HSV (Hue, Saturation, Value) = HSB (Hue, Saturation, Brightness) định hướng người sử dụng dựa trên cơ sở nền tảng về trực giác về tông màu, sắc độ và sắc thái mỹ thuật. - Hue – sắc màu: để phân biệt sự khác nhau giữa các màu như xanh, đỏ, vàng.. - Saturation – độ bão hòa: chỉ ra mức độ thuần của một màu hay khoảng cách của màu tới điểm có cường độ cân bằng (màu xám) - Value – độ sáng: hiện thân về mô tả cường độ sáng từ ánh sáng phản xạ nhận được từ đối tượng. Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 38 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông - Brightness – độ phát sáng: cường độ ánh sáng mà tự đối tượng phát ra chứ không phải do phản xạ từ các nguồn khác. Mô hình màu HSV được Alvey Ray Smith đưa ra năm 1978. Hệ thống tọa độ có dạng hình trụ và tập màu thành phần của không gian bên trong mô hình màu được xác định là hình nón hoặc hình chóp sáu cạnh như trong hình 2.13. Đỉnh hình chóp là sáu cạnh khi V = 1 chứa đựng mối quan hệ giữa các màu sáng và những màu trên mặt phẳng với V = 1 đều có màu sáng. Hình 2.13. Mô hình màu HSV - Sắc màu (Hue) hoặc H: màu sắc 00 - 3600 được đo bởi góc quanh trục đứng với màu đỏ là 0o, màu lục là 120o, màu lam là 240o (xem hình 2.13). Các màu bổ sung trong hình chóp HSV ở 180o đối diện với màu khác. - Saturation: Độ bão hoà 0-1, giá trị của S là tập các giá trị từ 0 trên đường trục tâm (trục V) đến 1 trên các mặt bên tại đỉnh của chóp 6 cạnh. Sự bão hòa được đo tương đối cho gam màu tương ứng với mô hình màu này. Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 39 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông - Value-Brightness: (độ sáng) 0-1 đường cao V với đỉnh là các điểm gốc toạ độ (0,0). Điểm ở đỉnh là màu đen và giá trị V=0, tại các điểm này giá trị của H và S không liên quan đến nhau. Khi điểm có S=0 và V=1 là điểm màu trắng, những giá trị trung gian của V đối với S=0 (trên đường thẳng qua tâm) là các màu xám. Khi S=0 giá trị của H phụ thuộc được gọi bởi các qui ước không xác định. Ngược lại khi S khác 0 giá trị H sẽ là phụ thuộc. Hình 2.14. Mô hình màu HSV Ví dụ: - Red được biểu diễn (00, 1, 1) - Green được biểu diễn (1200, 1, 1) 2.2.3.2. Ứng dụng Mô hình này được sử dụng nhiều trong các ứng dụng xử lý ảnh. 2.2.4. Mô hình màu HLS Mô hình màu HLS (Hue, Lightness, Saturation Model) – không gian màu trực quan. Mô hình thường được sử dụng trong kỹ thuật đồ hoạ. Ưu điểm là rất trực giác, ví dụ ta có thể chọn màu, thay đổi độ sáng và thay đổi độ bão hoà. Nhược điểm là khi chuyển đổi với không gian màu RGB sẽ có sai số (cube stood on end) thay đổi trên các loại màn hình khác nhau, rõ ràng không cảm nhận đều các màu. Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 40 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông Hình 2.15. Mô hình màu HLS Chúng ta có thể coi mô hình HLS như một sự biến dạng của mô hình HSV mà trong đó mô hình này màu trắng được kéo hướng lên hình chóp sáu cạnh phía trên từ mặt V=1. Độ sáng (Lightness)=0 cho màu đen (tại điểm mút thấp nhất của hình chóp sáu cạnh đôi) và bằng 1 cho màu trắng (tại đầu mút cao nhất). 2.2.5. Mô hình màu YIQ Mô hình màu YIQ là mô hình màu được ứng dụng trong truyền hình màu băng tần rộng tại Mỹ và do đó nó có mối quan hệ chặt chẽ với màn hình đồ họa màu raster. YIQ là sự thay đổi của RGB do khả năng truyền phát và tính tương thích với tivi đen trắng thế hệ trước. Tín hiệu truyền sử dụng trong hệ thống NTSC (National Television System Committe). Sự biến đổi RGB thành YIQ được xác định theo công thức sau: Y độ chói, I và Q đại lượng về màu sắc Những đại lượng trong ma trận biến đổi được tìm bằng cách sử dụng các phosphor NTSC RGB chuẩn có các tọa độ sắc phổ là R(0.67 0.33), G (0.21 0.71) và B (0.14 0.08). Người ta cũng giả định rằng điểm trắng nằm ở xw = 0.31, yw = 0.316 và Yw =1.0 Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 41 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông 2.2.6. Mô hình màu CIE - CIE là viết tắt của Comission Internationale de l’Eclairage, được thành lập năm 1913 với chức năng như một diễn đàn quốc tế cung cấp, trao đổi thông tin và các ý tưởng về mọi vấn đề liên quan đến chiếu sáng. Trong đó, nghiên cứu màu sắc là một trong những nhiệm vụ chính của tổ chức này. - Mô hình màu CIE phát triển trên cơ sở hoàn toàn độc lập thiết bị và dựa trên cảm nhận của mắt người về màu sắc. - Yếu tố cơ bản của mô hình CIE định nghĩa trên chuẩn về nguồn sáng và chuẩn về quan sát.  Nguồn sáng chuẩn: được định nghĩa bao gồm các nguồn: - Nguồn A: Bóng đèn sợi tóc Tungsten với nhiệt độ màu 285k - Nguồn B: Mô hình ánh sáng mặt trời vào buổi trưa với nhiệt độ 4800k - Nguồn C: Mô hình ánh sáng mặt trời vào ban ngày với nhiệt độ 6500k  Người quan sát chuẩn: Là sự tổng hợp của những nhóm nhỏ từ 15 – 20 người và như thế đại diện cho sự quan sát màu sắc của con người bình thường. Các đặc tả sử dụng kỹ thuật tương tự để thu được những màu có 3 giá trị kích thích tương đương với 3 kích thích tố RGB. Các giá trị RGB thu được này sẽ được sử dụng trong mô hình mẫu của màu sắc. Do sự ràng buộc của các gam màu, mô hình màu sắc RGB không thể sao chép toàn bộ ánh sáng quang phổ mà không đưa vào các giá trị thông số RGB âm. CIE đã chuyển đổi các giá trị của bộ 3 thông số vào trong một hệ khác chỉ sử dụng hoàn toàn các giá trị dương, được gọi là XYZ = > đây là mô hình đầu tiên của CIE gọi là mô hình màu CIE XYZ. Mô hình CIE XYZ được chấp nhận năm 1931 Sau đó các năm khác họ đã phát triển thêm các không gian màu khác của mô hình CIE như: CIELUV: là mô hình thiết lập năm 1960 và bổ sung năm 1976. Đây là mô hình thay đổi và mở rộng sơ đồ màu gốc để hiệu chỉnh tính không đồng đều. CIELAB: Một cách tiếp cận khác và phát triển của Richard Hunter vào năm 1942. Mô hình này định nghĩa màu theo 2 trục phân cực cho 2 màu (a và b) và đại lượng thứ ba là ánh sáng (L). Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 42 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông 2.3. Các thuật toán tô màu Tô màu một vùng là thay đổi màu sắc của các điểm vẽ nằm trong vùng cần tô. 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. Dạng đường biên đơn giản thường gặp là đa giác. Việc tô màu thường chia làm 2 công đoạn: - Xác định vị trí các điểm cần tô màu. - Quyết định tô các điểm trên bằng màu nào. Công đoạn này sẽ trở nên phức tạp khi ta cần tô theo một mẫu tô nào đó chứ không phải tô thuần một màu. Có 3 cách tiếp cận chính để tô màu: - Tô màu theo từng điểm (có thể gọi là tô đơn giản) - Tô màu theo dòng quét - Tô màu dựa theo đường biên. 2.3.1. Tô màu đơn giản Thuật toán này bắt đầu từ việc xác định một điểm có thuộc vùng cần tô hay không. Nếu đúng là điểm thuộc vùng cần tô thì sẽ tô với màu muốn tô.  Tô đƣờng tròn - Để tô đường tròn thì ta tìm hình vuông nhỏ nhất ngoại tiếp đường tròn bằng cách xác định điểm trên bên trái (xc-r, yc-r) và điểm dưới bên phải (xc+r, yc+r) của hình vuông (xem hình 2.16). - Cho i đi từ xc-r đến xc+r Cho j đi từ yc-r đến yc+r Tính khoảng cách d giữa hai điểm (i,j) và tâm (xc,yc) Nếu d<r thì tô điểm (i,j) với màu muốn tô Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 43 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông Hình 2.16. Tô màu đơn giản  Tô đa giác - Tìm hình chữ nhật nhỏ nhất có các cạnh song song với hai trục tọa độ chứa đa giác cần tô dưa vào hai tọa độ (xmin, ymin), (xmax, ymax). Trong đó, xmin, ymin là hoành độ và tung độ nhỏ nhất, xmax, ymax là hoành độ và tung độ lớn nhất của các đỉnh của đa giác. - Cho x đi từ xmin đến xmax, y đi từ ymin đến ymax (hoặc ngược lai). Xét điểm P(x,y) có thuộc đa giác không? Nếu có thì tô với màu cần tô (xem hình 2.17). Hình 2.17: Nội tiếp đa giác hình chữ nhật Thông thường một điểm nằm trong đa giác thì số giao điểm từ một tia bất kỳ xuất phát từ điểm đó cắt biên của đa giác phải là một số lẻ lần. Đặc biệt, tại các đỉnh Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 44 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông cực trị (cực đại hay cực tiểu ) thì một giao điểm phải được tính 2 lần (xem hình 2.18). Tia có thể qua phải hay qua trái. Thông thường ta chọn tia qua phải. Ví dụ : Xét đa giác gồm 13 đỉnh là P 0 , P 1 , ....., P 12 = P 0 (xem hình 2.18). Hình 2.18: Đa giác có 13 đỉnh Lưu ý: Gọi tung độ của đỉnh P i là P i .y . Nếu: - P i .y < Min ( P i+1 .y, P i-1 .y) hay P i .y > Max ( P i+1 .y, P i-1 .y) thì P i là đỉnh cực trị ( cực tiểu hay cực đại ). - P i-1 .y < P i .y < P i+1 .y hay P i-1 > P i .y > P i+1 .y thì P i là đỉnh đơn điệu. - P i = P i+1 và P i .y < Min ( P i+2 .y, P i-1 .y) hay P i > Max ( P i+2 .y, P i-1 .y) thì đoạn [P i ,P i+1 ] là đoạn cực trị ( cực tiểu hay cực đại ). - P i = P i+1 và P i-1 .y < P i .y < P i+2 .y hay P i-1 > P i .y > P i+2 .y thì đoạn [P i ,P i+1 ] là đoạn đơn điệu.  Thuật toán kiểm tra điểm có nằm trong đa giác - Với mỗi đỉnh của đa giác ta đánh dấu là 0 hay 1 theo qui ước như sau: nếu là đỉnh cực trị hay đoạn cực trị thì đánh số 0. Nếu là đỉnh đơn điệu hay đoạn đơn điệu thì đánh dấu 1. - Xét số giao điểm của tia nửa đường thẳng từ P là điểm cần xét với biên của đa giác. Nếu số giao điểm là chẳn thì kết luận điểm không thụôc đa giác. Ngược lại, số giao điểm là lẻ thì điểm thuộc đa giác. Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 45 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông  Nhận xét: Thuật toán tô đơn giản có ưu điểm là tô rất mịn và có thể sử dụng được cho đa giác lồi hay đa giác lõm, hoặc đa giác tự cắt, đường tròn, ellipse. Tuy nhiên, giải thuật này sẽ trở nên chậm khi ta phải gọi hàm PointInpoly nhiều lần. Để khắc phục nhược điểm này người ta đưa ra thuật toán tô màu theo dòng quét. 2.3.2. Tô màu theo dòng quét - Phương pháp này sẽ xác định 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ẽ tiến hành tô màu các điểm thuộc phần giao này. - Phương pháp này thường được dùng để tô màu đa giác lồi, lõm hay đa giác tự cắt, đường tròn, ellipse, và một số đường cong đơn giản khác.  Các bƣớc chính của thuật toán - Tìm ymin, ymax lần lượt là giá trị nhỏ nhất, lớn nhất của tập các tung độ của các đỉnh của đa giác đã cho. - Ứng với mỗi dòng quét y = k với k thay đổi từ ymin đến ymax, 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 : x 0 ,x 1 ,..., x n ,...  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 (x 0 , x 1 ), ( x 1 ,x 2 ), ....(xem hình 2.19). Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 46 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông Hình 2.19 : Tô màu đa giác bằng giải thuật scan – line  Các vấn đề cần lƣu ý: - Hạn chế được số cạnh cần tìm giao điểm ứng với mỗi dòng quét vì ứng với mỗi dòng quét không phải lúc nào cũng giao điểm với các cạnh của đa giác. - Xác định nhanh hoành độ giao điểm vì nếu lặp lại thao tác tìm giao điểm của cạnh đa giác với mỗi dòng quét sẽ tốn rất nhiều thời gian. - Giải quyết trường hợp số giao điểm đi qua đỉnh đơn điệu thì tính số giao điểm là 1 hay đi qua đỉnh cực trị.thì tính số giao điểm là 0 (hoặc 2). 2.3.3. Tô màu theo đƣờng biên Bài toán đặt ra : Cần tô màu một vùng nếu biết được màu của đường biên vùng tô và một điểm nằm bên trong vùng tô. Ý tƣởng : Bắt đầu từ một điểm nằm bên trong vùng tô, kiểm tra các điểm lân cận của nó đã được tô với màu muốn tô, hay điểm lân cận có màu trùng với màu biên không? Nếu cả hai trường hợp đều không phải thì ta sẽ tô điểm đó với màu muốn tô. Quá trình này được lặp lại cho đến khi không còn tô được nữa thì dừng (xem hình 2.20). Bài giảng Cơ sở đồ họa máy tính – Ngành CNTRT, TKĐH 47 Bộ môn Truyền thông Đa phương tiện – Đại học Công nghệ thông tin và Truyền thông Hình 2.20: Tô màu theo đường biên Có 2 quan điểm về cách tô này. Đó là dùng 4 điểm lân cận (có thể gọi là 4 liên thông) hay 8 điểm lân cận (8 liên thông) (xem hình 2.21). Hình 2.21: 4 liên thông và 8 liên thông  Nhận xét Thuật toán này có thể sẽ không hoạt động chính xác khi có một số điểm nằm trong vùng tô có màu là màu cần tô của vùng (FillColor). Để khắc phục điều này, trước khi tô màu cần phải đảm bảo rằng toàn bộ các điểm thuộc về vùng tô có màu khác màu tô.