三角形のラスタライズ

三角形のラスタライズを行うには以下の手順を踏む
１．三角形の上下分割
２．Yスキャン
３．Xスキャン

・三角形の上下分割
三角形を上下２つに分けることでスキャン変換がしやすくなる
１．３つの頂点を縦方向にソートする
２．真ん中の頂点の高さと最上点から最下点への辺と交差する位置を計算

・Yスキャン
Y座標ごとに切片を生成する。
これを先に分けた二つの３角形それぞれで行う。
このとき、ピクセルの中心点(Y+0.5)を通る位置に切片を生成する。
また一般的にコヒーレンシを生かすため、増分アルゴリズムを用いるが
スタート位置は頂点位置とは一致しない点に注意が必要だ。

・Xスキャン
Yスキャン変換で生成した各切片を今度はX座標ごとにピクセルを置いていく。

以上でひとつの三角形をラスタライズすることができるはずだ。

・実装
Zバッファー法を実装した。

以下にソースコード(C++)を示す。

//３つの頂点からなる３角形のラスタライズを行う
//--------------------------------------------------------------------------------------
//型定義

//Y座標ごとの切片
struct scan_entry{
    vector2 min;
    vector2 max;
};

//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//整数座標を求める
static inline int top_int(real x){
    return (int)floor(x+real(0.5));
}
//増分を求める
static inline vector2 delta_xz(const vector3& edge){
    static const real EPSILON = value::epsilon()*1000;
    
    assert(edge[1]>EPSILON);

    real ily = real(1)/edge[1];
    
    real dx = edge[0]*ily;
    real dz = edge[2]*ily;

    return vector2(dx,dz);
}

//--------------------------------------------------------------------------------------
//X
static void scan_horizontal(image<real>* img, int y, const scan_entry& se){
    static const real EPSILON = value::epsilon()*1000;

    int l,r;
    l = top_int(se.min[0]);
    r = top_int(se.max[0]);

    int w = img->get_width();
    if(l<0)l=0;
    if(w<r)r=w;

    if(l<r){
        real gap_x = real(l+0.5)-se.min[0];
        assert(gap_x>=0);
       
        vector2 e = se.max - se.min;
        
        assert(e[0]>EPSILON);
        //if(e[0]<EPSILON)return;
        
        real dz = e[1]/e[0];

        real sz = se.min[1]+dz*gap_x;

        int x = l;
        do{
            real z = img->get(x,y);
            if(z>sz){
                img->set(x,y,sz);
            }
            sz+=dz;

            x++;
        }while(x<r);
    }
}

//--------------------------------------------------------------------------------------
//abのYでの位置を求める
static inline vector3 branch(const vector3& a, const vector3& b, real Y){
    assert(b[1]!=a[1]);
    real t = (Y-a[1])/(b[1]-a[1]);
    return vector3(a[0]*(1-t)+b[0]*t,Y,a[2]*(1-t)+b[2]*t);
}
static void scan_vertical(image<real>* img, const vector3& pt, const vector3& pm, const vector3& pb){
    static const real EPSILON = value::epsilon()*1000;

    if(pb[1]-pt[1]<EPSILON)return;

    int t,b;
    t = top_int(pt[1]);
    b = top_int(pb[1]);

    if(!(t<b))return;
    
    int h = img->get_height();
    if(t<0)t=0;
    if(h<b)b=h;

    real mid = pm[1];

    vector3 pl,pr;
    vector3 tmp = branch(pt,pb,mid);//pt->
    if(tmp[0]<pm[0]){
        pl = tmp;
        pr = pm;
    }else{
        pl = pm;
        pr = tmp;           
    }

    int m = top_int(mid);
    if(m<0)m=0;
    if(h<m)m=h;

    if(t<m){//upper 
        vector3 el = pl-pt;//pt->pl
        vector3 er = pr-pt;//pt->pr
        vector2 dl = delta_xz(el);
        vector2 dr = delta_xz(er);
        //
        real gap_y = real(t+0.5)-pt[1];
        assert(gap_y>=0);
        //
        //start position
        vector2 sl = vector2(pt[0],pt[2])+dl*gap_y;
        vector2 sr = vector2(pt[0],pt[2])+dr*gap_y;

        int y=t;
        do{
            scan_entry se;
            se.min = sl;
            se.max = sr;
            scan_horizontal(img,y,se);
            sl+=dl;//
            sr+=dr;//

            y++;
        }while(y<m);
    }
    if(m<b){//lower
        vector3 el = pb-pl;//pl->pb
        vector3 er = pb-pr;//pr->pb
        vector2 dl = delta_xz(el);
        vector2 dr = delta_xz(er);
        //
        real gap_y = real(m+0.5)-mid;
        assert(gap_y>=0);
        //
        //start position
        vector2 sl = vector2(pl[0],pl[2])+dl*gap_y;
        vector2 sr = vector2(pr[0],pr[2])+dr*gap_y;

        int y=m;
        do{
            scan_entry se;
            se.min = sl;
            se.max = sr;
            scan_horizontal(img,y,se);
            sl+=dl;//
            sr+=dr;//

            y++;
        }while(y<b);
    }
}
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//ソート関数
template<class T>
static inline void swap_(T&a, T&b){T t = a;a=b;b=t;}
template<class T>
static inline void sort_index_(T t[3], int i){
    if(t[0][i]>t[1][i])swap_(t[0],t[1]);
    if(t[1][i]>t[2][i])swap_(t[1],t[2]);
    if(t[0][i]>t[1][i])swap_(t[0],t[1]);
}

//
//３つの頂点からなる３角形のラスタライズを行う
void rasterize_triangle(image<real>* img, const vector3& p0, const vector3& p1, const vector3& p2){
    vector3 points[3] = {p0, p1, p2};
    sort_index_(points,1);//ys
    scan_vertical(img, points[0], points[1], points[2]);        
}