Necesito un algoritmo de relleno de triángulo perfecto para evitar aliasing artefactos

Question

Estoy ayudando a alguien con código de interfaz de usuario para visualizar un análisis matemático de imágenes. Durante este proceso, segmentaremos parte de una figura 2D en triángulos y llenaremos algunos de estos triángulos en la interfaz de usuario.

Estamos buscando un algoritmo de relleno que garantice que si dos triángulos comparten un borde (específicamente, si dos vértices de los triángulos son idénticos), independientemente del orden de dibujo y el alias no habrá espacios en blanco, sin dibujar píxeles en la línea entre los dos. (Está bien si algunos píxeles se dibujan dos veces). El resultado debería verse bien en escalas arbitrarias. Algunos triángulos pueden ser astillas muy delgadas en algunos lugares, hasta 1 píxel de ancho.

Idealmente, ¡también debería ser un algoritmo de relleno razonablemente eficiente!

El antialias no se utilizará en la representación de triángulos, ya que la imagen final debe tener una profundidad de 1 bit.

El contexto es una aplicación de reconocimiento de imágenes, por lo que todas las coordenadas de los vértices tendrán una precisión de un píxel.

Answer 1

Teniendo en cuenta los requisitos, parece que hay una solución simple.

En primer lugar, rasterice los bordes del triángulo. Puede usar el algoritmo de dibujo de líneas de Bresenham para eso (como en el código a continuación) o cualquier cosa que funcione. Luego completa el área intermedia. Esto funcionará con triángulos arbitrariamente delgados.

Para asegurarse de que no hay lagunas, independientemente del orden en que se dibujan los triángulos e independientemente del orden de los vértices suministrados al código de trazado triangular, desea rasterizar bordes compartidos de la misma manera en los triángulos que comparten una borde. Igual que significa los mismos píxeles todo el tiempo.

Para garantizar que cada vez que obtenga los mismos píxeles de los mismos pares de coordenadas de vértice, básicamente desea establecer un orden fijo, es decir, establecer una regla que siempre elija el mismo vértice de los dos dados independientemente del orden en que se les da.

Una forma simple de aplicar este orden es tratar su línea (borde triangular) como un vector bidimensional y voltear su dirección si apunta en la dirección de y negativa o es paralela al eje xy los puntos en el dirección de x negativos. ¡Tiempo para un poco de arte ASCII! :)

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

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

Sede, aquí segmento de línea, por ejemplo, 1 a la línea segmento 5 son realmente el mismo tipo de cosas, la única diferencia es la dirección del punto final en el origen hasta el otro extremo. Así que reducimos estos casos a la mitad al convertir los segmentos 4 a 7 en los segmentos 0 a 3 y eliminamos la ambigüedad de la dirección. IOW, elegimos ir en la dirección de aumentar y's O, si y's son iguales en el borde, en la dirección de aumentar x's.

Así es como podría hacerlo en código:

#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; 
} 

Salida de ejemplo:

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







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

Leyenda:

• "+" - píxeles del triángulo 1
• " - "- píxeles del triángulo 2
• "*" - píxeles del borde compartidos entre triángulos 1 y 2

Tenga en cuenta que a pesar de que no habrá ningún hueco sin llenar (píxeles), el triángulo cuyos píxeles (en el borde compartido) sobrescribirá (debido el otro triángulo dibujado sobre él) puede aparecer disjunto o tener una forma torpe si es demasiado delgado. Ejemplo:

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









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

Answer 2

Lo que está buscando es un algoritmo floodfill.

Here's one.

Another link.

Puede google 'floodfill-algorithm' para más.

[editar]

Tal this site [Shader-Based de carcasa Dibujo] puede ofrecer algunas ideas más.

Answer 3

No es el más eficiente, pero podría recorrer un cuadrado que contenga el triángulo y probar si cada píxel está dentro del triángulo.

Pseudocódigo:

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

Dónde minX es la coordenada X mínima entre los tres vértices y de manera similar para maxX, miny y maxY.

Para un algoritmo más rápido, primero puede hacer un relleno rápido y sucio (por ejemplo, relleno de slashmais) y luego hacer esto para los píxeles alrededor de los bordes.

La prueba de punto en triángulo se describe en here.

Answer 4

Su preocupación acerca de los triángulos adyacentes es válida. Si dos triángulos comparten un borde, debes asegurarte de que cada píxel a lo largo de ese borde "pertenece" exclusivamente a un triángulo u otro. Si uno de esos píxeles no pertenece a ningún triángulo, tiene un espacio. Si pertenece a ambos triángulos, tiene sobregiro (que es ineficiente) y el color puede depender del orden en que se representan los triángulos (que puede no ser determinista).

Dado que no está utilizando anti-aliasing, esto en realidad no es demasiado difícil. No es tanto un algoritmo inteligente como una implementación cuidadosa.

La forma típica de rasterizar un triángulo es calcular los segmentos horizontales que forman parte del triángulo desde la parte superior hasta la parte inferior.Para ello, haga un seguimiento de los bordes actuales izquierdo y derecho, y esencialmente hacer un cálculo de intersección en X para cada borde en cada línea de exploración. También se puede hacer con dos algoritmos de dibujo de líneas al estilo Bresenhem que se ejecutan juntos. Efectivamente, la rasterización equivale a varias llamadas a una función que dibuja un segmento de línea horizontal en alguna línea de escaneo y desde alguna coordenada izquierda x0 a alguna coordenada a la derecha x1.

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

Normalmente lo que se hace es asegurarse de que las rondas Rasterizer fuera de las intersecciones x de una manera consistente, de manera que las coordenadas x se calculan correctamente con independencia de si son parte del borde derecho de un triángulo o el borde izquierdo del triángulo adyacente. Esto garantiza que cada píxel a lo largo del borde compartido pertenecerá a ambos triángulos.

Resolvemos la doble propiedad mediante la deformación de DrawHLine de modo que llene los píxeles de x0 incluido hasta x1 exclusiva. De modo que todos esos píxeles de doble propiedad en el borde compartido se definen como pertenecientes al triángulo a la derecha del borde compartido.

Answer 5

Este es un problema bien estudiado. Aprende sobre el algoritmo de dibujo de líneas bresenham.

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