Ho bisogno di un algoritmo di riempimento triangolo perfetto per pixel per evitare artefatti di aliasing

Question

Sto assistendo qualcuno con codice di interfaccia utente per visualizzare un'analisi matematica dell'immagine. Durante questo processo segmenteremo parte di una forma 2D in triangoli e riempi alcuni di questi triangoli nell'interfaccia utente.

Stiamo cercando un algoritmo di riempimento che garantisca che se due triangoli condividono un bordo (in particolare, se due vertici dei triangoli sono identici), indipendentemente dall'ordine di disegno e dall'aliasing non sarà vuoto, non sparpagliato pixel sulla linea tra i due. (Va bene se alcuni pixel vengono disegnati due volte.) Il risultato dovrebbe apparire OK sotto ridimensionamento arbitrario. Alcuni triangoli possono presentare scaglie estremamente sottili in luoghi, fino a 1 pixel di larghezza.

Idealmente dovrebbe anche essere un algoritmo di riempimento ragionevolmente efficiente!

L'anti-aliasing non verrà utilizzato nel rendering triangolare, in quanto l'immagine finale deve avere una profondità di 1 bit.

Il contesto è un'applicazione di riconoscimento immagini, quindi tutte le coordinate del vertice saranno precise per un pixel.

Answer 1

date le esigenze, sembra che ci sia una soluzione semplice.

Prima rasterizzare i bordi del triangolo. È possibile utilizzare l'algoritmo di disegno al tratto di Bresenham per quello (come nel codice seguente) o qualsiasi altra cosa che funzioni. Quindi riempire l'area in mezzo. Questo funzionerà con triangoli arbitrariamente sottili.

Per assicurarsi che non vi siano spazi vuoti indipendentemente dall'ordine in cui sono disegnati i triangoli e indipendentemente dall'ordine dei vertici forniti al codice del disegno a triangolo, si desidera rasterizzare i bordi condivisi allo stesso modo nei triangoli che condividono un bordo. Stesso modo significa gli stessi pixel ogni volta.

Per garantire che ogni volta che si ottengano gli stessi pixel dalle stesse coppie di coordinate del vertice, in pratica si vuole stabilire un ordine fisso, cioè stabilire una regola che sceglie sempre lo stesso vertice tra le due date indipendentemente dell'ordine in cui vengono dati.

Un modo semplice per far rispettare questo ordine consiste nel trattare la linea (bordo triangolare) come un vettore 2D e invertirne la direzione se punta nella direzione di y negativa o è parallela all'asse x e punti nel direzione delle x negative. Tempo per un'arte ASCII! :)

 3 2 1 
     \ |/
     \ |/
     \|/ 
4 --------+--------- 0 
     /|\ 
     /| \ 
    /| \ 
     5 6 7 

     4 -> 0 
     5 -> 1 
     6 -> 2 
     7 -> 3 

Sede, qui segmento di linea, per esempio, 1 e la linea segmento 5 sono in realtà lo stesso tipo di cosa, l'unica differenza è la direzione dal punto finale all'origine per gli altri endpoint. Quindi riduciamo questi casi a metà girando i segmenti da 4 a 7 nei segmenti da 0 a 3 e sbarazzandoci dell'ambiguità della direzione. IOW, scegliamo di andare nella direzione di aumentare l'OR di y, se y sono gli stessi sul bordo, nella direzione dell'aumento di x.

Ecco come si potrebbe fare nel codice:

#include <stddef.h> 
#include <limits.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 
#include <time.h> 

#define SCREEN_HEIGHT 22 
#define SCREEN_WIDTH 78 

// Simulated frame buffer 
char Screen[SCREEN_HEIGHT][SCREEN_WIDTH]; 

void SetPixel(long x, long y, char color) 
{ 
    if ((x < 0) || (x >= SCREEN_WIDTH) || 
     (y < 0) || (y >= SCREEN_HEIGHT)) 
    { 
    return; 
    } 

    if (Screen[y][x] == ' ') 
    Screen[y][x] = color; 
    else 
    Screen[y][x] = '*'; 
} 

void Visualize(void) 
{ 
    long x, y; 

    for (y = 0; y < SCREEN_HEIGHT; y++) 
    { 
    for (x = 0; x < SCREEN_WIDTH; x++) 
    { 
     printf("%c", Screen[y][x]); 
    } 

    printf("\n"); 
    } 
} 

typedef struct 
{ 
    long x, y; 
    unsigned char color; 
} Point2D; 


// min X and max X for every horizontal line within the triangle 
long ContourX[SCREEN_HEIGHT][2]; 

#define ABS(x) ((x >= 0) ? x : -x) 

// Scans a side of a triangle setting min X and max X in ContourX[][] 
// (using the Bresenham's line drawing algorithm). 
void ScanLine(long x1, long y1, long x2, long y2) 
{ 
    long sx, sy, dx1, dy1, dx2, dy2, x, y, m, n, k, cnt; 

    sx = x2 - x1; 
    sy = y2 - y1; 

/* 
     3 2 1 
     \ |/
     \ |/
     \|/ 
4 --------+--------- 0 
     /|\ 
     /| \ 
    /| \ 
     5 6 7 

     4 -> 0 
     5 -> 1 
     6 -> 2 
     7 -> 3 
*/ 
    if (sy < 0 || sy == 0 && sx < 0) 
    { 
    k = x1; x1 = x2; x2 = k; 
    k = y1; y1 = y2; y2 = k; 
    sx = -sx; 
    sy = -sy; 
    } 

    if (sx > 0) dx1 = 1; 
    else if (sx < 0) dx1 = -1; 
    else dx1 = 0; 

    if (sy > 0) dy1 = 1; 
    else if (sy < 0) dy1 = -1; 
    else dy1 = 0; 

    m = ABS(sx); 
    n = ABS(sy); 
    dx2 = dx1; 
    dy2 = 0; 

    if (m < n) 
    { 
    m = ABS(sy); 
    n = ABS(sx); 
    dx2 = 0; 
    dy2 = dy1; 
    } 

    x = x1; y = y1; 
    cnt = m + 1; 
    k = n/2; 

    while (cnt--) 
    { 
    if ((y >= 0) && (y < SCREEN_HEIGHT)) 
    { 
     if (x < ContourX[y][0]) ContourX[y][0] = x; 
     if (x > ContourX[y][1]) ContourX[y][1] = x; 
    } 

    k += n; 
    if (k < m) 
    { 
     x += dx2; 
     y += dy2; 
    } 
    else 
    { 
     k -= m; 
     x += dx1; 
     y += dy1; 
    } 
    } 
} 

void DrawTriangle(Point2D p0, Point2D p1, Point2D p2) 
{ 
    long y; 

    for (y = 0; y < SCREEN_HEIGHT; y++) 
    { 
    ContourX[y][0] = LONG_MAX; // min X 
    ContourX[y][1] = LONG_MIN; // max X 
    } 

    ScanLine(p0.x, p0.y, p1.x, p1.y); 
    ScanLine(p1.x, p1.y, p2.x, p2.y); 
    ScanLine(p2.x, p2.y, p0.x, p0.y); 

    for (y = 0; y < SCREEN_HEIGHT; y++) 
    { 
    if (ContourX[y][1] >= ContourX[y][0]) 
    { 
     long x = ContourX[y][0]; 
     long len = 1 + ContourX[y][1] - ContourX[y][0]; 

     // Can draw a horizontal line instead of individual pixels here 
     while (len--) 
     { 
     SetPixel(x++, y, p0.color); 
     } 
    } 
    } 
} 

int main(void) 
{ 
    Point2D p0, p1, p2, p3; 

    // clear the screen 
    memset(Screen, ' ', sizeof(Screen)); 

    // generate random triangle coordinates 

    srand((unsigned)time(NULL)); 

    // p0 - p1 is going to be the shared edge, 
    // make sure the triangles don't intersect 
    for (;;) 
    { 
    p0.x = rand() % SCREEN_WIDTH; 
    p0.y = rand() % SCREEN_HEIGHT; 

    p1.x = rand() % SCREEN_WIDTH; 
    p1.y = rand() % SCREEN_HEIGHT; 

    p2.x = rand() % SCREEN_WIDTH; 
    p2.y = rand() % SCREEN_HEIGHT; 

    p3.x = rand() % SCREEN_WIDTH; 
    p3.y = rand() % SCREEN_HEIGHT; 

    { 
     long vsx = p0.x - p1.x; 
     long vsy = p0.y - p1.y; 
     long v1x = p0.x - p2.x; 
     long v1y = p0.y - p2.y; 
     long v2x = p0.x - p3.x; 
     long v2y = p0.y - p3.y; 
     long z1 = vsx * v1y - v1x * vsy; 
     long z2 = vsx * v2y - v2x * vsy; 
     // break if p2 and p3 are on the opposite sides of p0-p1 
     if (z1 * z2 < 0) break; 
    } 
    } 

    printf("%ld:%ld %ld:%ld %ld:%ld %ld:%ld\n\n", 
     p0.x, p0.y, 
     p1.x, p1.y, 
     p2.x, p2.y, 
     p3.x, p3.y); 

    // draw the triangles 

    p0.color = '-'; 
    DrawTriangle(p0, p3, p1); 
    p1.color = '+'; 
    DrawTriangle(p1, p2, p0); 

    Visualize(); 

    return 0; 
} 

Esempio di output:

30:10 5:16 16:6 59:17 







       +++ 
       ++++++++ 
       ++++++++++++ 
      +++++++++++++++++ 
      +++++++++++++++****--- 
      +++++++++++++****----------- 
     ++++++++++****------------------- 
     ++++++*****---------------------------- 
     +++****------------------------------------- 
     ****--------------------------------------------- 
    *----------------------------------------------------- 
                  - 

Legenda:

• "+" - pixel del triangolo 1
• " - "- pixel del triangolo 2
• "*" - pixel del bordo condiviso tra triangoli 1 e 2

Attenzione che anche se non ci saranno vuoti vuoti (pixel), il triangolo i cui pixel (sul bordo comune) sovrascritto (a causa di l'altro triangolo disegnato sopra) può apparire disgiunto o goffo se è troppo sottile. Esempio:

2:20 12:8 59:15 4:17 









      *++++++ 
      *+++++++++++++ 
      *+++++++++++++++++++++ 
     -*++++++++++++++++++++++++++++ 
     -*++++++++++++++++++++++++++++++++++++ 
     *+++++++++++++++++++++++++++++++++++++++++++ 
     *+++++++++++++++++++++++++++++++++++++++++++++++++++ 
     *+++++++++++++++++++++++++++++++++++++++++++++++++++++ 
    *+++++++++++++++++++++++++++++++++++++++++++ 
    -*+++++++++++++++++++++++++++++++ 
    -*+++++++++++++++++++++ 
    *++++++++++ 
    * 

Answer 2

Quello che stai cercando è un algoritmo floodfill.

Here's one.

Another link.

Puoi google 'floodfill-algorithm' per ulteriori informazioni.

[modifica]

Forse this site [Shader-Based Wireframe Disegno] in grado di offrire qualche idea in più.

Answer 3

Non è il più efficiente, ma è possibile eseguire il loop su un quadrato contenente il triangolo e verificare se ciascun pixel si trova all'interno del triangolo.

Pseudocode:

for(x : minX -> maxX) 
    for(y : minY -> maxY) 
     if(triangle.contains(x,y)) 
      drawPixel(x,y); 

Dove minX è la coordinata X minima tra i tre vertici e analogamente per maxX, miny e maxy.

Per un algoritmo più veloce, è possibile eseguire un riempimento rapido e sporco (ad esempio riempimento di riempimento di slashmais), quindi eseguire i pixel attorno ai bordi.

Il test point-in-triangle è descritto here.

Answer 4

La tua preoccupazione per i triangoli adiacenti è valida. Se due triangoli condividono un bordo, si vuole essere sicuri che ogni pixel lungo quel bordo "appartenga" esclusivamente a un triangolo o all'altro. Se uno di quei pixel non appartiene a nessuno dei due triangoli, hai uno spazio vuoto. Se appartiene a entrambi i triangoli, hai un overdraw (che è inefficiente) e il colore potrebbe dipendere dall'ordine di rendering dei triangoli (che potrebbe non essere deterministico).

Dato che non si sta utilizzando l'anti-alias, questo in realtà non è troppo difficile. Non è tanto un algoritmo intelligente di cui hai bisogno come un'implementazione attenta.

Il modo tipico di rasterizzare un triangolo consiste nel calcolare i segmenti orizzontali che fanno parte del triangolo dall'alto verso il basso.Lo fai tenendo traccia degli attuali bordi sinistro e destro e facendo essenzialmente un calcolo di intercettazione x per ogni spigolo in ciascuna linea di scansione. Può anche essere fatto con due algoritmi di disegno di linee in stile Bresenhem che funzionano insieme. In effetti, la rasterizzazione equivale a diverse chiamate a una funzione che disegna un segmento di linea orizzontale su una scanline da una qualche coordinata di sinistra x0 a qualche coordinata destra x1.

void DrawHLine(int y, int x0, int x1); 

Tipicamente ciò che è fatto è quello di assicurarsi il giro Rasterizer largo delle x-intercetta in modo coerente, in modo che le ascisse sono calcolate coerente indipendentemente dal fatto che siano parte del bordo destro di un triangolo o il bordo sinistro del triangolo adiacente. Ciò garantisce che ogni pixel lungo il bordo condiviso appartenga a entrambi i triangoli.

Risolviamo il doppio di proprietà modificando DrawHLine in modo da riempire i pixel x0 compreso fino a x1esclusiva. Quindi tutti i pixel con doppia proprietà sul bordo condiviso sono definiti per appartenere al triangolo a destra del bordo condiviso.

Answer 5

Questo è un problema ben studiato. Ulteriori informazioni sull'algoritmo di disegno della linea di bresenham.

http://en.wikipedia.org/wiki/Bresenham's_line_algorithm