多角形塗りつぶし(3)・アンチエイリアス

アンチエイリアス
それでは、次に、多角形塗りつぶしをアンチエイリアス付きで描画してみます。
今までは、アンチエイリアス付きで描画するのに「オーバーサンプリング」を使いましたが、ここでもやはりオーバーサンプリングを使います。

ただし、多角形塗りつぶしに関しては、今までのように、単純に描画先の 1px をサブピクセルで分解することはできません。
なぜなら、各 Y 位置ごとに交点を見つけて水平線を描画する方法だからです。

いつものオーバーサンプリングとは、少し考え方を変えなければいけません。
Y 方向のオーバーサンプリング
描画先の任意の1点をそのままサブピクセル分解することはできませんが、とりあえず描画先の Y 位置に関しては、サブピクセル分解することができます。

今までは、ymin〜ymax までの各 Y 位置で交点を計算していましたが、この Y 位置を浮動小数点にして、各小数位置上での交点を計算すれば、各サブピクセル位置上での交点座標を得られます。

ただし、描画は、Y1列単位で水平線を描画することにより行われますから、オーバーサンプリングでの濃度の平均値を出すには、Y1列分の作業用バッファが必要です。
イメージ上に水平線を描画する代わりに、バッファの濃度を加算して、最終的にその値をサブピクセル分で割って平均値を出せば、Y1列における各 X 位置の濃度が求められそうです。
オーバーサンプリング用のバッファを作る
まずは、オーバーサンプリング用の作業用バッファを作る必要があります。

Y1列分のバッファと言っても、描画先の画像幅全体のサイズにする必要はありません。
多角形の描画範囲は各頂点から求めることができるので、すべての頂点の X 座標の最小値・最大値を求めれば、X 方向の描画幅を求めることができ、必要最小限のサイズのバッファを作ることが出来ます。
交点計算を浮動小数点で行う
交点処理を行う部分では、スキャンの Y 位置は浮動小数点になるので、交点計算も浮動小数点で行う必要があります。
ただし、交点の X 位置は整数で格納します。
描画部分
各サブピクセル位置における交点のリストを得たら、次は、バッファに対して水平線描画を行います。
点を打つ代わりに、バッファに値を加算します。

サブピクセルの回数分の処理が終わったら、バッファから平均値を算出し、各 X 位置における濃度を得て、その濃度で、実際に描画先に点を置いていきます。
X 方向の濃度
以上のように、Y 方向に関しては、サブピクセル分解してオーバーサンプリング処理をすることができますが、X 方向に関しては何も行われていません。
もちろん、Y 方向のオーバーサンプリングだけでもそれなりに綺麗にはなるのですが、水平に近い辺の輪郭部分を見ると、綺麗な結果にならないので、このままでは不十分です。
さらに綺麗なアンチエイリアスにするためには、X 方向の処理も必要です。

では、実際にはどうやるかというと、交点計算時には、浮動小数点で計算することにより、小数付きの X 座標を得ることができるので、それを使えば良さそうです。
小数付きの X 座標からピクセルの濃度を得て、それを X 方向の濃度として扱います。
水平線描画
Y 方向のオーバーサンプリングにおいては、水平線を描画する代わりに、バッファ上に濃度を加算していきました。
X 方向に関しても、得た濃度はバッファ上に加算していきます。

では、小数付きの X 座標を元に水平線描画を行う場合、各 X 位置の濃度はどうなるでしょうか。
例えば、5.48.3 の2つの交点 X があって、その間を水平線描画する場合は、各 X 位置の濃度は以下のようになります。

x : 5"5.0〜5.4" までは点がなく、"5.4〜6.0" までは点があるということなので、
x = 5 のピクセルにおける濃度は、「1.0 - 0.4 = 0.6」となります。
x : 6〜7最初のピクセルと最後のピクセル以外は、すべて濃度最大で塗りつぶされることになるので、
この間の濃度は「1.0」。
x : 8"8.0〜8.3" までは点があり、8.3 以降は点がないということなので、
x = 8 のピクセルにおける濃度は、「0.3」となります。

なお、3.23.6 のように、始点と終点が同じ X 位置上にある場合は、そのピクセルの濃度は「3.6 - 3.2 = 0.4」となります。

これで、小数付きの座標から濃度を得て、水平線描画する方法がわかりました。
あとは、この通りにバッファ上に濃度を加算するだけです。
スクリーンショット&ソースファイル


>> 033_fillpoly3.c.txt
解説
交点の X 座標は浮動小数点にしなければならないので、INTERSECTION 構造体の X 座標を double にしました。

typedef struct
{
    double x;
    int dir;
}INTERSECTION;

交点リスト作成の部分に関しては、スキャンの Y 位置が double になっただけで、基本的に前回と変わっていません。
図形の描画範囲
オーバーサンプリング用のバッファを作成するため、新たに xmin, xmax に X の最小・最大位置を求めています。
ただ、今回は交点の X 座標が小数付きになるということで、バッファへの描画時などに配列外にアクセスする可能性をなくすため、範囲を余分に 1px 拡張しています。
スキャンの各 Y 処理
draw_fill_polygon() において、ymin〜ymax までの各 Y 位置で処理を行うのは同じですが、Y 方向のオーバーサンプリングが加わり、また、交点間の水平線描画が、バッファへの描画に変わっています。
そして、最終的には、バッファから濃度値を得て、点を描画しています。

for(y = ymin; y <= ymax; y++)
{
    /* バッファクリア */

    memset(buf, 0, w * sizeof(int));
    
    /* Y 方向のサブピクセル処理 */

    for(i = 0; i < SUBPIXEL_Y; i++)
    {
        /* 交点取得 */
    
        xcnt = get_intersection(y + i * (1.0 / SUBPIXEL_Y), list, 100);
        if(xcnt == -1) continue;
    
        /* 交点間を塗りつぶし(バッファに) */
        
        drawbuf_hline(buf, xmin, list, xcnt);
    }
    
    /* バッファから各点描画 */
    
    for(i = 0; i < w; i++)
    {
        c = 255 - buf[i] / SUBPIXEL_Y;
        
        sptk_image_setpixel(winimg, xmin + i, y, SPTK_RGB(c,c,c));
    }
}

交点の取得は、Y の各サブピクセル位置ごとに行っています。
交点の X 座標は浮動小数点なので、その座標を元に、バッファ上へ水平線を描画します。
バッファへの水平線描画
drawbuf_hline() が、交点リストを元に、濃度バッファへ水平線描画を行う関数です。

void drawbuf_hline(int *buf,int xleft,INTERSECTION *list,int xcnt)
{
    int i,j,v,x1,x2;
    double dx1,dx2;

    v = 0;
    
    for(i = 0; i < xcnt - 1; i++)
    {
        v += list[i].dir;
        if(v == 0) continue;
        
        dx1 = list[i].x;
        dx2 = list[i + 1].x;
        
        x1 = (int)dx1;
        x2 = (int)dx2;
        
        if(x1 == x2)
            buf[x1 - xleft] += (int)(255 * (dx2 - dx1));
        else
        {
            /* 始点 */
            
            buf[x1 - xleft] += (int)(255 * (1.0 - (dx1 - x1)));
            
            /* 間 */
            
            for(j = x1 + 1; j < x2; j++)
                buf[j - xleft] += 255;
            
            /* 終点 */
            
            buf[x2 - xleft] += (int)(255 * (dx2 - x2));
        }
    }
}

ここでは、濃度の最大を 255 として、X 座標の小数部分を濃度に適用しています。
実際の描画
得られた濃度バッファを元に、実際に描画先に点を置いているのが、以下の部分です。

for(i = 0; i < w; i++)
{
    c = 255 - buf[i] / SUBPIXEL_Y;
    
    sptk_image_setpixel(winimg, xmin + i, y, SPTK_RGB(c,c,c));
}

まず、Y 方向のオーバーサンプリング処理を完了するため、バッファの値をサブピクセル分で割って、濃度の平均値を出します。
ここでは、濃度の最大値を 255 として扱っているので、値の範囲は 0〜255 となります。

実際に描画する際は、この濃度値をアルファ値として描画するのですが、今回は直接、「濃度0=白、濃度MAX=黒」として描画するので、255 から引いて、RGB 値に変換しています。
まとめ
多角形塗りつぶしに関しては以上ですが、自由線を描くのと同じように、ドラッグ中のすべての座標を頂点として加えて、それを多角形として描画すると、より自由な形状を描くことができます。

また、ペンタブレットなどの場合は、カーソル座標として浮動小数点の座標を得られるので、頂点の座標を浮動小数点にすれば、より精密な形状を描くことができます。