Zig-Zag-Dreieck Traversal Implementierung

Question

ich versuchte "On the Hardware Implementation of Triangle Traversal Algorithms for Graphics Processing" (Royer, Ituero, Lopez-Vallejo, & Barrio) (Seite 4) zu folgen Zig-Zag-Traversal-Algorithmus für Dreieck triversal/Rasterung zu implementieren. Jedoch ist die Erklärung in dem Papier für mich kontraintuitiv und ich konnte es nicht zum Laufen bringen.

Ich habe versucht, eine endliche Zustandsmaschine zu implementieren, aber ich kann nicht genau die genauen Zustände herausfinden. Im Moment habe ich (Richtung, e_1, e_2, e_3) wo e_n für jede Kante einen Kantentest-Ausgang darstellt. Pseudocode:

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. 

Jede Hilfe würde geschätzt werden!

Bearbeiten: Meine bisherigen Bemühungen: Während der Kantentest ordnungsgemäß funktioniert, wurden nur wenige Teile des Diagramms gerastert.

/// 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

So sehe ich Zustandsmaschine:

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 ;