ジグザグトライアングルトラバーサルの実装

Question

私は三角triversal /ラスタライゼーションのためのジグザグトラバーサルアルゴリズムを実装するために"On the Hardware Implementation of Triangle Traversal Algorithms for Graphics Processing" (Royer, Ituero, Lopez-Vallejo, & Barrio)（4ページ）に追従しようとしていました。しかし、この論文の説明はわかりやすく、私はそれを機能させることができませんでした。

私は有限状態機械を実装しようとしましたが、正確な状態を把握することはできません。ここで、e_nは各エッジのエッジテスト出力を表す（direction、e_1、e_2、e_3）です。擬似コード：

if (right, true, true, true): 
    x++; // Move towards right 
else if (left, true, true, true): 
    x--; // Move towards left 
else: 
    // This is where I stuck. There should be two cases where in one of them 
    // y goes down and x doesn't change direction, in the other case x simply 
    // flips its direction. But I wasn't able to figure it out. 

助けてください！

編集：これまでの努力： エッジテストが正しく機能している間に、グラフのわずかな部分がラスタライズされました。私は、ステートマシン方法を参照してください

/// Zig Zag (not working) 
int top_row = floor(fmin(y0, fmin(y1, y2))); 
int bot_row = floor(fmax(y0, fmax(y1, y2))); 
if (y0 > y1) { 
    swap(x0, x1); swap(y0, y1); 
} 
if (y0 > y2) { 
    swap(x0, x2); swap(y0, y2); 
} 
if (y1 > y2) { 
    swap(x1, x2); swap(y1, y2); 
} 
assert(top_row == floor(y0)); 
assert(bot_row == floor(y2)); 

bool direction = true; 
bool changed = false; 
int x = floor(x0); int y = floor(y0); 
while (y <= bot_row) { 
    bool e1, e2, e3; 
    e1 = edge_test((float)x+0.5, (float)y+0.5, x0, y0, x1, y1) < 0.0f; 
    e2 = edge_test((float)x+0.5, (float)y+0.5, x1, y1, x2, y2) < 0.0f; 
    e3 = edge_test((float)x+0.5, (float)y+0.5, x2, y2, x0, y0) < 0.0f; 

    if ((e1 == e2) && (e2 == e3)) { 
    if (x < 0 || x >= width) continue; 
    if (y < 0 || y >= height) continue; 
    samplebuffer[y][x].fill_pixel(color); 

    if (direction) x++; 
    else x--; 
    } else if (changed) { 
    y++; 
    changed = false; 
    } else { 
    direction = !direction; 
    changed = true; 
    if (direction) x++; 
    else x--; 
    } 
} 

Answer 1

：

Dir = +1/-1 

State 0: (moving inside) 
EdgeTest: 
    0 => State 1 ; y++ 
    1 => State 0 ; x = x + Dir 

State 1: (outside) 
EdgeTest: 
    0 => State 3 ; Dir = - Dir 
    1 => State 2 ; 

State 2: (inside moving the same dir) 
EdgeTest: 
    0 => State 3 ; Dir = - Dir 
    1 => State 2 ; x= x + Dir 

State 3: (outside) 
EdgeTest: 
    0 => State 3 ; x = x + Dir 
    1 => State 0 ;