多角形塗りつぶし(1)

多角形塗りつぶし
ここからは、スキャンライン法による「多角形の塗りつぶし」をやっていきたいと思います。

スキャンライン法」とは、描画先の Y1列 ごとに点があるかどうかを判定して、塗っていくやり方です。
多角形の場合は、各 Y 位置ごとに、多角形の各辺との交点を求め、それを元に水平線を描画して、塗りつぶしを行っていきます。
多角形の定義
まずは、多角形がどういう風に形成されるかを考えておきます。

ペイントソフトで描画する場合は、多角形の各頂点を指定し、それを直線で繋いで、その内側を塗りつぶすことになります。
まずは、描画する多角形のすべての頂点が必要ですね。



頂点を得た後は、各頂点を順番につなげて、辺を作ります。
上の画像の場合は、「辺 1-2、2-3、3-4、4-5、5-1」というように、5つの辺が出来上がります。

この状態で、描画先の描画位置と多角形の各辺との関係を見つけ、それを元に塗りつぶしていきます。
実際の手順
多角形塗りつぶしの実際の処理手順を、以下に示します。


描画の Y 位置と多角形の各辺との交点を求め、その交点間を塗りつぶすことで、全体的に多角形塗りつぶしを実現させます。
1.描画範囲を求める
まずは、描画先における、図形の描画範囲が必要です。
多角形の各頂点の X, Y 位置の最小値・最大値を求めれば、描画範囲は得られます。
しかし、ここでは Y1列ごとに処理を行うのですから、実際には、Y の描画範囲だけ求めれば OK です。
2.辺との交点を求める
次に、描画範囲 Ymin〜Ymax の各 Y 位置を対象にして、処理を行っていきます。

現在の Y 位置と、多角形の各辺との交点 X を見つけ、その X 座標を記録しておきます。
交点計算は、多角形のすべての辺を対象に行います。

なお、直線 (x1,y1)-(x2,y2) と任意の Y 位置との交点 X は、以下の計算で求められます。

X = x1 + (Y - y1) * (x2 - x1) / (y2 - y1)

ただし、これは Y が y1 〜 y2 の範囲内にある場合です。
Y が y1 〜 y2 の範囲外の場合、交点はないということですから、交点処理は行いません。

また、注意しなければならないことがもう一つあります。
y1 == y2 の場合は、/ (y2 - y1) がゼロ除算になるので、避けなければなりません。
辺が y1 == y2 ということは、水平な直線ですね。
多角形の辺における水平線は、一つ前と一つ次の辺との交点により塗りつぶされることになるので、ここでは、水平線との交点は処理する必要はありません。
3.交点を値の小さい順に並べ替える&描画
交点 X をすべて求められたら、その交点を値の小さい順に並べ替えます。
これで、交点間を塗りつぶす準備ができました。

あとは、交点の2点を一組として、順番に、「0-1 間、2-3 間...」の間を水平線として塗りつぶしていきます。


理論的には上記の手順で多角形を描画できるのですが、実際にちゃんとした多角形塗りつぶしになるようにするには、これにもう少し手を加える必要があります。
スクリーンショット
とりあえず、先に実際のコードで試してみてくだい。



左クリックで、多角形の頂点を追加します。
右クリックで、現在の頂点から多角形塗りつぶしを実行します。
一度描画されると、初期状態に戻り、頂点選択を最初から再開できます。
ソースコード
031_fillpoly1.c
#include "sptk.h"

#define WIDTH  300
#define HEIGHT 300

SPTK_IMAGE *winimg;
SPTK_POINT pt[100];
int ptcnt = 0;

/** y 位置との交点リストを作成
 * return : 交点数 (-1 で処理なし) */

int get_intersection(int y,int *xlist,int maxcnt)
{
    int i,j,min_index,cnt,ntmp;
    SPTK_POINT pt1,pt2,pttmp;
        
    /* 交点リストを作る */
    
    cnt = 0;

    for(i = 0; i < ptcnt; i++)
    {
        /* 辺の始点と終点 */
        
        pt1 = pt[i];
        pt2 = pt[(i + 1) % ptcnt];
        
        /* 水平線は除外 */
        
        if(pt1.y == pt2.y) continue;
        
        /* Y 位置が、現在の辺の終点と、次の辺の始点である場合、
         * 両辺が上方向、または下方向の場合は交点から除外 */
        
        if(y == pt2.y)
        {
            pttmp = pt[(i + 2) % ptcnt];
            
            if((pt2.y - pt1.y < 0 && pttmp.y - pt2.y < 0) ||
                (pt2.y - pt1.y > 0 && pttmp.y - pt2.y > 0))
                continue;
        }
        
        /* Y が下方向になるように入れ替え */
        
        if(pt1.y > pt2.y)
            pttmp = pt1, pt1 = pt2, pt2 = pttmp;

        /* Y の範囲外 */
        
        if(y < pt1.y || y > pt2.y) continue;
        
        /* 交点追加 */
        
        if(cnt >= maxcnt) return -1;
        
        xlist[cnt++] = pt1.x + (y - pt1.y) * (pt2.x - pt1.x) / (pt2.y - pt1.y);
    }

    if(cnt == 0 || (cnt & 1)) return -1;
    
    /* 小さい順に並べ替え */
    
    for(i = 0; i < cnt - 1; i++)
    {
        min_index = i;
    
        for(j = i + 1; j < cnt; j++)
        {
            if(xlist[j] < xlist[min_index])
                min_index = j;
        }
        
        if(i != min_index)
        {
            ntmp = xlist[i];
            xlist[i] = xlist[min_index];
            xlist[min_index] = ntmp;
        }
    }
    
    return cnt;
}

void draw_fill_polygon()
{
    int ymin,ymax,i,x,y,xlist[100],xcnt;

    /* Y の描画範囲 */
    
    ymin = ymax = pt[0].y;
    
    for(i = 1; i < ptcnt; i++)
    {
        if(pt[i].y < ymin) ymin = pt[i].y;
        if(pt[i].y > ymax) ymax = pt[i].y;
    }
    
    /* 各 Y 位置処理 */
    
    for(y = ymin; y <= ymax; y++)
    {
        xcnt = get_intersection(y, xlist, 100);
        if(xcnt == -1) continue;
        
        /* 交点間を塗りつぶし */
        
        for(i = 0; i < xcnt; i += 2)
        {
            for(x = xlist[i]; x <= xlist[i + 1]; x++)
                sptk_image_setpixel(winimg, x, y, 0);
        }
    }
}

void winhandle(SPTK_EVENT *ev)
{
    switch(ev->type)
    {
        case SPTK_EVENT_BTTDOWN:
            if(!sptk_isgrab())
            {
                if(ev->mouse.btt == SPTK_MOUSEBTT_LEFT)
                {
                    if(ptcnt < 100)
                    {
                        pt[ptcnt].x = ev->mouse.x;
                        pt[ptcnt].y = ev->mouse.y;
                        ptcnt++;
                        
                        sptk_image_fillbox(winimg, ev->mouse.x - 1, ev->mouse.y - 1, 3, 3, 0xff0000);
                        sptk_update(NULL, ev->mouse.x - 1, ev->mouse.y - 1, 3, 3, 0);
                    }
                }
                else if(ev->mouse.btt == SPTK_MOUSEBTT_RIGHT)
                {
                    if(ptcnt >= 3)
                    {
                        sptk_image_clear(winimg, 0xffffff);
                        
                        draw_fill_polygon();
                        
                        sptk_update(NULL, 0, 0, WIDTH, HEIGHT, 0);
                        
                        ptcnt = 0;
                    }
                }
            }
            break;
        case SPTK_EVENT_WINDOW_CLOSE:
            sptk_quit();
            break;
    }
}

int main()
{
    sptk_init("test", WIDTH, HEIGHT);
    
    sptk_window_set_handle(winhandle);
    
    winimg = sptk_window_get_image();
    sptk_image_clear(winimg, 0xffffff);
    
    sptk_run();

    return 0;
}
解説
SPTK_POINT pt[100] に多角形の各頂点の位置を、ptcnt に現在の頂点数を格納します。
メイン部分
draw_fill_polygon() で、現在の頂点から多角形塗りつぶしを描画します。

なお、多角形の塗りつぶしには、最低でも頂点が3つ必要です。
頂点が3つ未満の場合は処理を行わないようにしてください。

void draw_fill_polygon()
{
    int ymin,ymax,i,x,y,xlist[100],xcnt;

    /* Y の描画範囲 */
    
    ymin = ymax = pt[0].y;
    
    for(i = 1; i < ptcnt; i++)
    {
        if(pt[i].y < ymin) ymin = pt[i].y;
        if(pt[i].y > ymax) ymax = pt[i].y;
    }
    
    /* 各 Y 位置処理 */
    
    for(y = ymin; y <= ymax; y++)
    {
        xcnt = get_intersection(y, xlist, 100);
        if(xcnt == -1) continue;
        
        /* 交点間を塗りつぶし */
        
        for(i = 0; i < xcnt; i += 2)
        {
            for(x = xlist[i]; x <= xlist[i + 1]; x++)
                sptk_image_setpixel(winimg, x, y, 0);
        }
    }
}

まずは、描画先における Y の描画範囲を求めます。
全ての頂点の最小値・最大値を求めて、ymin, ymax にセットしています。

次に、ymin〜ymax までの各 Y 位置において、処理を行います。

get_intersection() で、現在の Y 位置における、多角形の各辺との交点 X のリストを得ます。
交点がない場合や、交点が配列内に収まらない場合は、なにもせずに次の位置へ進みます。
ここでは、int xlist[100] に交点の X 座標を格納します。
また、見つかった交点の数は、関数の戻り値で得ます。

なお、今回は交点を格納する配列を固定数にしていますが、実際の実装では、交点が多い場合にも対応できるように、可変個数の配列にするべきです。

そして、取得した交点の X 座標を元に、水平線塗りつぶしを行います。
交点の2つを一組として、左から右の位置までを塗りつぶします。
xlist[0]-xlist[1]、xlist[2]-xlist[3]、...
交点のリストを得る
get_intersection() で、指定 Y 位置と多角形のすべての辺との交点を得ます。

交点を見つけるために、まずは辺を作ります。
頂点が「1,2,3,4...」とあれば、辺は「1-2、2-3、3-4...」というように、現在の位置と次の位置で直線を作ることになりますから、頂点の数だけループさせ、現在の位置とその次の位置で辺を作ります。

for(i = 0; i < ptcnt; i++)
{
    pt1 = pt[i];
    pt2 = pt[(i + 1) % ptcnt];
    
    if(pt1.y == pt2.y) continue;

pt1 が辺の始点、pt2 が辺の終点です。
最後の頂点の次は、配列の先頭へ戻るので、次の位置は % ptcnt することで、0〜ptcnt-1 内に収まるようにしています。
また、「始点と終点の Y 位置が同じ=水平線」の場合には、交点を求める必要はないので、はじきます。

次の if(y == pt2.y)... の部分は後述するので、その次へ行きます。

if(pt1.y > pt2.y)
    pttmp = pt1, pt1 = pt2, pt2 = pttmp;

if(y < pt1.y || y > pt2.y) continue;

if(cnt >= maxcnt) return -1;

xlist[cnt++] = pt1.x + (y - pt1.y) * (pt2.x - pt1.x) / (pt2.y - pt1.y);

まず、辺が上方向の場合は、pt1.y < pt2.y として下方向になるように、位置を入れ替えます。
これは、交点計算時に正しく計算できるようにするために、必要です。

その後、処理する Y 位置が、現在の辺の範囲内にあるかどうかを判定します。
pt1.y〜pt2.y の範囲外であれば、交点がないことになるので、次の辺へと進みます。

あとは、交点の計算処理を行って、処理する Y 位置と現在の辺との交点 X を求め、配列に追加します。


これで、すべての辺との交点が配列に格納されました。
なお、描画時には、交点は2つ一組で使用するので、交点の数が奇数の場合は、以降の描画処理を行わないようにします。

現在の交点リスト内では、X 座標の値がバラバラに並んでいるので、これを、値が小さい順になるように並べ替えます。
これで、交点リストの作成は終了です。
問題点
以上の処理で実際に多角形塗りつぶしを行ってみると、形によっては、塗りつぶされない部分があったりして、正しく描画されない場合があります。

これは、何が問題なのかというと、スキャンの Y 位置が、辺の始点または終点と同じ位置にある場合に、同じ値の交点が2つ追加されてしまい、交点数が奇数になったりするからです。



例えば、上の図の場合を見てください。
もしもスキャンの Y 位置が頂点 B と同じ位置の場合、得られる交点としては、まず C-A の辺との交点。そして、A-B の辺と、B-C の辺の交点です。
この場合は、交点が3つになってしまいます。

問題なのは、A-B の辺と、B-C の辺の交点です。
ここでは、スキャンの Y 位置が、A-B の終点、さらに B-C の始点と交わっているので、交点が一つ余計に追加されることになります。

これを防ぐには、余計な交点を追加しないようにしなければならないのですが、同じ位置が2つ続いている場合に1つを取り除く、といった単純なやり方では、正しく処理できません。

例えば、図形の一部が Y 方向に山なりになっている場合を考えてください。
山の頂点の 1px 部分は、交点の2つの同じ位置を元に水平線描画を行うことにより、1px の点を描画することになります。
この場合、交点が一つなくなると、逆におかしなことになります。

というわけで、図形の形によって、交点を取り除くか否かを判断する必要があります。

交点が余分に増える可能性があるのは、図形が X 方向に山なりになる場合。
つまり、A-B-C の頂点があった場合、辺 A-B と 辺 B-C の Y 方向が同じ向きの場合に、いずれかの交点を一つ取り除く必要があります。

そこで、交点計算の部分で説明を省いたところのコードを見てみます。

if(y == pt2.y)
{
    pttmp = pt[(i + 2) % ptcnt];
    
    if((pt2.y - pt1.y < 0 && pttmp.y - pt2.y < 0) ||
        (pt2.y - pt1.y > 0 && pttmp.y - pt2.y > 0))
        continue;
}

2つの辺の Y 方向を判断するためには、現在の辺の前の位置か次の位置の頂点が必要なので、ここでは、次の位置 (i + 2) の頂点を判断材料として使います。

頂点は [i],[i+1],[i+2] の3つがあることになるので、もしもスキャンの Y 位置が [i+1] の Y 位置と同じ場合は、今説明した、交点を省く処理が必要です。
2つの辺の Y 方向の向きが同じであれば、交点を追加しないようにします。

ところで、もしも辺が水平線の場合はどうなるでしょうか。
pt1-pt2 の辺が水平線の場合は、この前に弾かれているので除くとして、次の辺が水平線の場合、その辺の交点そのものが計算されませんから、ここでは、交点は必要です。
なので、pttmp.y - pt2.y が 0 の場合は、交点を取り除いてはいけません。

【追記】
水平線の辺が含まれる場合は、この処理では足りませんでした。
しかし、水平線の判定も含めると結構ややこしくなりそうです。
水平線が含まれない場合は、この処理でも問題ありません。