Gupta-Sproullアルゴリズムの実装

ちょっと実装を行わないといけないことになったので、実装してみました。言語はJAVAです。

今回、アルゴリズムで使用した色のテーブルはGURGE.COMのAdam Doppelt氏が作成したのを利用しました。

読みやすさ優先の為、高速動作とかは特に考えていません。また、端点処理は含んでいません。
GuptaSproullCanvasインターフェースは指定した点に渡された濃度値で色を描画しろ、という命令です。

interface GuptaSproullCanvas{
    public void setColor(int x,int y,int alph);

}

class GuptaSproull{
    /*
     * GuptaSproull8ビットテーブル作成　Adam Doppelt氏
     * GURGE.COM (URL:http://gurge.com/blog/2006/11/29/gupta-sproull-antialiased-lines/)
     */

    static int[] table=
    { 0xc7, 0xc6, 0xc2, 0xbc,
        0xb3, 0xa9, 0x9c, 0x8e,
        0x7f, 0x70, 0x62, 0x54,
        0x46, 0x3a, 0x2f, 0x25,
        0x1c, 0x15, 0x0e, 0x09,
        0x05, 0x03, 0x01, 0x00 };


    int x0,y0,x1,y1;//始点終点
    int xl,yl;//abs(x0-x1),abs(y0-y1)
    boolean straight;//水平方向または垂直方向に一直線かどうか
    boolean vertical;//垂直方向に多く進むかどうか

    public GuptaSproull(Point from,Point to) {
        x0=from.x;
        x1=to.x;
        y0=from.y;
        y1=to.y;
        xl=x1-x0<0? -x1+x0:x1-x0;
        yl=y1-y0<0? -y1+y0:y1-y0;
        straight = yl==0 ||xl==0;
        vertical = straight?xl==0:yl>xl;
    }

    public void draw(GuptaSproullCanvas g){
        int xadd=x1-x0>0?1:-1;//座標更新時に正負どっちに進むか
        int yadd=y1-y0>0?1:-1;

        int x,y;

        if(straight){//垂直か水平に一直線
            if(vertical){
                for(y=y0;y!=y1;y+=yadd)g.setColor(x0, y, 0xff);
            }else{
                for(x=x0;x!=x1;x+=xadd)g.setColor(x, y0, 0xff);
            }
            return;
        }

        if(vertical){//tanθ>1
            int xweight=0;
            x=x0;
            for(y=y0;y!=y1;y+=yadd){//座標更新は単なるDDA
                g.setColor(x, y, getAlph(distance(x, y)));
                g.setColor(x+1, y, getAlph(distance(x+1, y)));
                g.setColor(x-1, y, getAlph(distance(x-1, y)));
                xweight+=xl;
                if(xweight*2 >= yl){//四捨五入を考慮
                    xweight-=yl;
                    x+=xadd;
                }
            }
            //最後に終点を描画
            g.setColor(x, y, getAlph(distance(x, y)));
            g.setColor(x+1, y, getAlph(distance(x+1, y)));
            g.setColor(x-1, y, getAlph(distance(x-1, y)));
        }else{
            int yweight=0;
            y=y0;

            for(x=x0;x!=x1;x+=xadd){
                g.setColor(x, y, getAlph(distance(x, y)));
                g.setColor(x, y+1, getAlph(distance(x, y+1)));
                g.setColor(x, y-1, getAlph(distance(x, y-1)));
                yweight+=yl;

                if(yweight*2 >= xl){
                    yweight-=xl;
                    y+=yadd;
                }
            }

            //最後に終点を描画
            g.setColor(x, y, getAlph(distance(x, y)));
            g.setColor(x, y+1, getAlph(distance(x, y+1)));
            g.setColor(x, y-1, getAlph(distance(x, y-1)));
        }
    }

    private double distance(int x,int y){
        return Math.abs((y1-y0)*x-(x1-x0)*y-y1*x0+x1*y0)/Math.hypot((x1-x0), (y1-y0));
    }

    private int getAlph(double distance){
        if(distance>=1)return 0;
        return table[(int)(distance*table.length)];
    }
}