Te damos la bienvenida a nuestra comunidad, ahora encontrarás la solucíon de lo que buscabas.
Solución:
Dados los requisitos, parece que hay una solución sencilla.
Primero, rasteriza los bordes del triángulo. Puede usar el algoritmo de dibujo lineal de Bresenham para eso (como en el código a continuación) o cualquier cosa que funcione. Luego, complete el área intermedia. Esto funcionará con triángulos arbitrariamente delgados.
Para asegurarse de que no haya espacios, independientemente del orden en el que se dibujen los triángulos e independientemente del orden de los vértices suministrados al código de dibujo de triángulos, desea rasterizar los bordes compartidos de la misma manera en los triángulos que comparten un borde. Mismo camino significa los mismos píxeles cada vez.
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 sencilla de hacer cumplir este orden es tratar la línea (borde del triángulo) como un vector bidimensional y cambiar su dirección si apunta en la dirección de las y negativas o si es paralela al eje xy apunta en la dirección de las x negativas. . ¡Es hora de un poco de arte ASCII! 🙂
3 2 1
| /
| /
|/
4 --------+--------- 0
/|
/ |
/ |
5 6 7
4 -> 0
5 -> 1
6 -> 2
7 -> 3
Mira, aquí el segmento de línea, digamos, 1 y el segmento de línea 5 son realmente el mismo tipo de cosas, la única diferencia es la dirección desde el punto final en el origen hasta el otro punto final. Así que reducimos estos casos a la mitad convirtiendo los segmentos 4 a 7 en segmentos 0 a 3 y eliminamos la ambigüedad de dirección. IOW, elegimos ir en la dirección de incrementar y’s OR, si y’s son iguales en el borde, en la dirección de incrementar x’s.
Así es como puede hacerlo en código:
#include
#include
#include
#include
#include
#include
#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)
(y < 0)
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)
5 6 7
4 -> 0
5 -> 1
6 -> 2
7 -> 3
*/
if (sy < 0
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:%ldnn",
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 muestra:
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 compartido entre los triángulos 1 y 2
Tenga en cuenta que, aunque no habrá espacios sin rellenar (píxeles), el triángulo cuyos píxeles (en el borde compartido) se sobrescriben (debido al otro triángulo dibujado encima) puede aparecer como disjunto o con una forma extraña si es demasiado delgado . Ejemplo:
2:20 12:8 59:15 4:17
*++++++
*+++++++++++++
*+++++++++++++++++++++
-*++++++++++++++++++++++++++++
-*++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++++++++++++
*+++++++++++++++++++++++++++++++++++++++++++
-*+++++++++++++++++++++++++++++++
-*+++++++++++++++++++++
*++++++++++
*
Su preocupación por los triángulos adyacentes es válida. Si dos triángulos comparten un borde, querrás estar seguro de que cada píxel a lo largo de ese borde "pertenece" exclusivamente a un triángulo o al otro. Si uno de esos píxeles no pertenece a ninguno de los triángulos, tiene un espacio. Si pertenece a ambos triángulos, tiene sobredimensionado (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 suavizado, esto en realidad no es demasiado difícil. No es tanto un algoritmo inteligente lo que necesita, sino una implementación cuidadosa.
La forma típica de rasterizar un triángulo es calcular los segmentos horizontales que forman parte del triángulo de arriba a abajo. Para ello, realiza un seguimiento de los bordes izquierdo y derecho actuales y, en esencia, realiza un cálculo de intersección con el eje 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 exploración y desde alguna coordenada izquierda x0 a alguna coordenada correcta x1.
void DrawHLine(int y, int x0, int x1);
Por lo general, lo que se hace es asegurarse de que el rasterizador redondea las intersecciones x de manera coherente, de modo que las coordenadas x se calculen de forma coherente independientemente de si son parte del borde derecho de un triángulo o del borde izquierdo del triángulo adyacente. . Esto garantiza que cada píxel a lo largo del borde compartido pertenecerá a ambos triangulos.
Resolvemos la doble propiedad ajustando DrawHLine para que llene los píxeles de x0 inclusive hasta x1exclusivo. Entonces, todos esos píxeles de doble propiedad en el borde compartido se definen como pertenecientes al triángulo a la derecha del borde compartido.
Me doy cuenta de que no se recomiendan las respuestas de solo enlace, pero he escrito sobre este problema exacto en mi blog. Fabian Giesen también lo comenta como parte de su excelente serie, Optimización de la eliminación de oclusiones de software.
La esencia de esto es que debe seleccionar un regla de relleno, que determina cómo romper el empate para píxeles compartidos entre dos caras. Una de estas reglas de relleno está especificada y bien documentada para la API Direct3D de Microsoft. Se puede implementar utilizando un algoritmo similar al algoritmo de línea de Bresenham, pero se debe prestar un poco de cuidado adicional a los casos de redondeo y borde.
Incluso la respuesta aceptada aquí no maneja pendientes x negativas de manera consistente, aunque dado que su salida es de solo 1 bit y no necesita interpolar ninguna attributes, probablemente no importe mucho.
Te mostramos las comentarios y valoraciones de los lectores
Acuérdate de que tienes permiso de decir si diste con el resultado.