Khi lập trình đồ họa máy tính, bạn hay sử dụng các hàm tô màu được định nghĩa sẵn trong thư viện <graphics.h> như: fillpoly và drawpoly chẳng hạn. Các hàm này hỗ trợ việc tô màu rất tốt, rất nhanh. Liệu khi sử dụng nó, bạn có bao giờ thắc mắc bên dưới các hàm đó được thực hiện như nào, sử dụng thuật toán gì để tô màu chưa? Trong bài viết này, chúng ta sẽ cùng đi tìm hiểu về 1 trong các thuật toán được dùng để tô màu trong đồ họa máy tính. Đó chính là thuật toán tô màu Scanline nha!

1. Giới thiệu:

Thuật toán tô màu Scanline (hay còn gọi là thuật toán tô màu theo dòng quét) được áp dụng để tô màu các đa giác lồi, lõm hay đa giác tự cắt.

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 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 bởi từng cặp giao điểm một.

2. Ý tưởng của thuật toán:

-Tìm y_min, y_max 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, k thay đổi từ y_min đến y_max, 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₀, x₁, …
• Tô màu các đoạn thẳng y=k trên đường thẳng lần lượt được giới hạn bởi các cặp ( x₀, x₁), ( x₂, x₃), ….(x_2k, x_2k+1).

*Một vài lưu ý:

Nhưng nếu chỉ dừng ở mức này và chuyển sang cài đặt thì chúng ta sẽ gặp phải một số vấn đề như sau:

• Ứ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 cắt dòng quét. Do đó để cải thiện tốc độ, ta phải tìm ra cách hạn chế 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ác 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.

• Nếu số giao điểm tìm được giữa các cạnh của đ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 nữa. Điều này chỉ xảy ra khi dòng quét đi ngang qua các đỉnh đa giác.

• Việc tìm giao điểm của dòng quét với các cạnh nằm ngang là 1 trường hợp đặc biệt, cần phải có cách xử lý thích hợp.

*Hướng giải quyết:

• Để hạn chế số cạnh cần tìm giao điểm ứng với dòng quét, ta áp dụng công thức hệ số góc sau:

x_k+1 = x_k + 1/m

trong đó: m là hệ số góc của cạnh; x_k+1 , x_k lần lượt là hoành độ giao điểm của một cạnh nào đó với dòng quét y=k và y=k+1.

• Giải quyết trường hợp số giao điểm đi qua đỉnh đơn điệu thì ta tính số giao điểm là 1 ; Đi qua đỉnh cực trị thì tính số giao điểm là 0 (hoặc 2).

3. Lưu đồ thuật toán

4. Code minh họa

#include <conio.h>
#include <iostream>
#include <graphics.h>
#include <stdlib.h>
using namespace std;

struct ToaDo
{
    int x,y;
};
//==============================================
void nhapDaGiac(ToaDo p[], int v)
{
    int i;
    for(i=0;i<v; i++){
        cout<<"\nNhap toa do dinh "<<i+1<<" : ";
        cout<<"\n\tx["<<(i+1)<<"] = "; cin>>p[i].x;
        cout<<"\n\ty["<<(i+1)<<"] = "; cin>>p[i].y;
    }
    p[i].x=p[0].x;
    p[i].y=p[0].y;
}
//==============================================
void veDaGiac(ToaDo p[], int v)
{
    for(int i=0;i<v;i++)
        line(p[i].x,p[i].y,p[i+1].x,p[i+1].y);
}
//==============================================
void ScanLine(ToaDo p[], int v)
{
    int xmin,xmax,ymin,ymax,c,mang[50];
    xmin=xmax=p[0].x;
    ymin=ymax=p[0].y;
    for(int i=0;i<v;i++){ if(xmin>p[i].x) xmin=p[i].x;
        if(xmax<p[i].x) xmax=p[i].x; if(ymin>p[i].y) ymin=p[i].y;
        if(ymax<p[i].y) ymax=p[i].y;
    }
    float y;
    y=ymin+0.01;
    while(y<=ymax){ //với y tăng dần từ ymin > ymax,tìm các giao điểm của từng y với các cặp cạnh
        int x,x1,x2,y1,y2,tg;
        c=0;    //chỉ số của mảng phần tử
        for(int i=0;i<v;i++){ //xét trên tất cả các đỉnh
            //xét 2 đỉnh liền kề nhau
            x1=p[i].x;
            y1=p[i].y;
            x2=p[i+1].x;
            y2=p[i+1].y;
            if(y2<y1){ //sắp xếp lại y của 2 điểm liên tiếp
                tg=x1;x1=x2;x2=tg;
                tg=y1;y1=y2;y2=tg;
            }
            //mảng giao điểm
            if(y<=y2&&y>=y1){
                if(y1==y2)  x=x1; //nếu y của 2 đỉnh liên tiếp trùng nhau => bỏ qua
                else{
                    x=((y-y1)*(x2-x1))/(y2-y1); //hệ số góc
                    x+=x1; //300
                }
                if(x<=xmax && x>=xmin)
                    mang[c++]=x;   //cho phần tử c = x sau đó c++
            }
        }
        //với từng y tăng dần ta vẽ luôn đường thằng nối 2 giao điểm
        for(int i=0; i<c;i+=2){
                delay(30);
                line(mang[i],y,mang[i+1],y);
        }   //line(302,91,300,91
        y++;
    }
}
//nhap 10 dinh:
//1.(75,250),2.(210,250),3.(250,128),4.(291,250),5.(425,250)
//6.(318,331),7.(360,460),8.(249,380),9.(140,460),10.(182,331)
//3 7 1 5 9
int main()
{
    int cl,v;
    do{
        cout<<"\n Nhap so dinh da giac:"; cin>>v;
    }while(v<3);
    ToaDo p[v];
    nhapDaGiac(p,v);
    cout<<"\nChon mau (0-15) : "; cin>>cl;
    initwindow(500,600);
    veDaGiac(p,v);
    setcolor(cl);
    ScanLine(p, v);
    getch();
}

5. Hình minh họa

Cảm ơn các bạn đã đọc bài viết . Mong bài viết giúp ích cho việc học tập của các bạn !