Rellenar un triángulo es elegir píxeles
Rellenar un triángulo es decidir qué píxeles de la pantalla quedan dentro de sus tres lados. Es la tarea más repetida en gráficos por computador, porque cualquier superficie de un videojuego en 3D se dibuja con triángulos.
Con una cuenta de tres productos puedes decidirlo para cada píxel.
Al final de esta lección
Nota
Puedo decir qué píxeles están dentro de un triángulo.
Palabras clave
| Palabra | Qué significa |
|---|---|
| Arista | cada uno de los tres lados del triángulo |
| Función de borde | un número que dice a qué lado de una arista cae un punto |
| Dentro | el punto está del mismo lado de las tres aristas |
| Peso baricéntrico | cuánto pesa un vértice en un punto del triángulo |
| Área doble | el doble del área, que sale de la función de borde |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
La función de borde da el lado
Una arista va de un vértice a a otro b. Para un punto p, la función de borde es (bx - ax) * (py - ay) - (by - ay) * (px - ax).
El resultado es positivo a un lado de la arista, negativo al otro y cero sobre ella. Un punto está dentro del triángulo si las tres aristas dan el mismo signo.
Ejemplo resuelto: dos puntos y un triángulo
| Punto | Borde A a B | Borde B a C | Borde C a A | ¿Dentro? |
|---|---|---|---|---|
| (2, 2) | 16 | 32 | 16 | Sí: los tres son positivos |
| (6, 6) | 48 | -32 | 48 | No: uno es negativo |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Calcula los tres bordes del punto (2, 2)
docker exec jupyter python3 -c "e = lambda a, b, p: (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]); A, B, C, P = (0, 0), (8, 0), (0, 8), (2, 2); print(e(A, B, P), e(B, C, P), e(C, A, P), e(A, B, C))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Qué imprime el cálculo de los tres bordes
Imprime 16 32 16 64. Los tres primeros son positivos, así que el punto está dentro. Cuenta como dentro un punto con valor 0, porque cae sobre una arista.
El cuarto número es la función de borde de A a B para el vértice C. Vale 64, el doble del área del triángulo: 8 por 8 entre 2 es 32, y 32 por 2 es 64.
Rellena un triángulo en una cuadrícula de texto
docker exec jupyter python3 -c "e = lambda a, b, p: (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]); A, B, C = (1, 1), (9, 1), (1, 9); print('\n'.join(''.join('#' if min(e(A, B, (x, y)), e(B, C, (x, y)), e(C, A, (x, y))) >= 0 else '.' for x in range(11)) for y in range(11)))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Cómo se lee el triángulo de texto
Imprime once filas de once signos. La fila 0 y la fila 10 son todo puntos. La fila 1 tiene nueve #, de la columna 1 a la 9. Cada fila siguiente tiene uno menos, hasta la fila 9, que tiene uno solo.
Es un triángulo con el ángulo recto arriba a la izquierda. Suman 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 píxeles.
Basta probar los píxeles de una caja
No hace falta probar los píxeles de toda la pantalla. Basta con la caja más pequeña que contiene los tres vértices. Va de la x menor a la x mayor y de la y menor a la y mayor.
Dentro de esa caja pruebas cada píxel con las tres aristas. Así un triángulo pequeño cuesta poco.
Los pesos baricéntricos dicen cuánto pesa cada vértice
Cada borde, dividido entre el área doble, da un peso. El peso de A es el borde de B a C del punto, entre el área doble. Lo mismo para B (borde de C a A) y para C (borde de A a B).
Los tres pesos suman 1. Con ellos puedes mezclar los colores de los vértices en cada píxel.
Ejemplo resuelto: los pesos del punto (2, 2)
| Vértice | Borde del punto | Área doble | Peso |
|---|---|---|---|
| A (0, 0) | 32 | 64 | 0,5 |
| B (8, 0) | 16 | 64 | 0,25 |
| C (0, 8) | 16 | 64 | 0,25 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Calcula los pesos de un punto
# Pesos baricéntricos del punto (2, 2) en el triángulo (0, 0), (8, 0), (0, 8).
def borde(a, b, p):
return (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0])
A = (0, 0)
B = (8, 0)
C = (0, 8)
P = (2, 2)
area = borde(A, B, C)
print(borde(B, C, P) / area, borde(C, A, P) / area, borde(A, B, P) / area)
# Cambia P a (8, 0): el peso de B será 1 y los demás 0.
Un error muy común
Advertencia
Mucha gente cree que un píxel sobre una arista no pertenece al triángulo. Aquí, un valor 0 cuenta como dentro. Así los triángulos que comparten una arista no dejan una línea de huecos entre ellos.
Guarda el triángulo relleno como imagen
docker exec jupyter python3 -c "from PIL import Image; e = lambda a, b, p: (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]); A, B, C = (1, 1), (9, 1), (1, 9); im = Image.new('L', (11, 11), 255); im.putdata([0 if min(e(A, B, (x, y)), e(B, C, (x, y)), e(C, A, (x, y))) >= 0 else 255 for y in range(11) for x in range(11)]); im.resize((165, 165), Image.NEAREST).save('triangulo.png'); print(im.getpixel((2, 2)), im.getpixel((9, 9)), im.getpixel((0, 0)), im.getpixel((1, 9)))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Para ir más lejos: abre el triángulo
El comando de la imagen guarda triangulo.png, de 165 por 165 píxeles. Ábrelo en JupyterLab desde la carpeta de trabajo.
Verás un triángulo negro sobre blanco, con el ángulo recto arriba a la izquierda y el lado largo bajando hacia la izquierda. Cambia los vértices y comprueba cuántos píxeles salen.