linkAntecedentes

El proceso de raterización se origina por la necesidad de representar objetos continuos y bien definidos de manera gráfica en una computadora. Para este cometido es necesario realizar la conversión de vectores a pixeles.

Existen diversos métodos para realizar rasterización en función de las figuras o elementos a procesar; para el caso de los triangulos, existe un enfoque basado en las llamadas Coordenadas Baricéntricas.

El concepto de las coordenadas baricéntricas data del año 1827 cuando el matemático alemán August F. Möbius lo introdujo. Como concepto básico las coordenadas baricéntricas permiten identificar si un punto está dentro o fuera de un triángulo.

Si un plano posee un triángulo $T$ con vértices $a, b$ y $c$ ; y un punto $p = (x, y)$ entonces el punto se puede expresar como:

Por tanto si $\alpha , \beta , \gamma \in [ 0,1 ]$ entonces $p$ se encuentra dentro del triángulo. Los valores $\alpha , \beta , \gamma$ son llamadas las coordenadas baricentricas de $p$. En la práctica tenemos que $a = (ax, ay), b = (bx, by)$ y $c = (cx, cy)$ son los puntos que forman $T$ mientas que para el punto $p = (x, y)$ sus coordenadas Baricéntricas se calculan como:

donde

De esta manera es posible verificar si un punto se encuentra o no dentro de un triángulo. A partir de aquí se puede plantear la estrategia de rasterización. A saber, dibujar el triangulo en una cuadricula, analizar que cuadrados de la cuadricula se encuentran dentro del triangulo por medio de las coordenadas baricentricas , en caso de que este dentro, sombrear el cuadrado correspondiente, y así sucesivamente hasta recorrer toda la cuadricula.

A continuación en la pestaña Coordenadas Baricéntricas se puede observar el resultado del alrotirmo de las coordenadas baricéntricas al situar el cursor sobre el triángulo dibujado, se podrán observar los valores de $\alpha (\lambda_0), \beta (\lambda_1)$ y $\gamma (\lambda_2)$ incluso si el cursor esta fuera de la figura (esto causará que uno de los valores sea menos a 0 o mayor a 1).

Por su parte en la pestaña Rasterización Completa se mostrará la aplicación de las coordenadas en el proceso de rasterización, juntando este cálculo con la generación de la cuadrícula en la que se identificará cuales cuadrados están dentro del triángulo (sobrepasando su punto medio), coloreando de blanco aquellos que no se encuentren dentro, y de color los que si se encuentren. Se podrá alterar la figura del triángulo al deseado por el usuario en ambas pestañas por medio de los botones derecho, izquierdo y central del mouse.

Como caso especial,en la pestaña Rasterización Antialiasing se realiza una implementación de antialiasing para suavizar la rasterización del triángulo al analizar los sub-cuadrados dentro de cada celda y su punto medio verificando si este reside dentro o fuera del polígono, resultando así en una aproximación más cercana al triángulo original ya que se colorean los sub-cuadrados necesarios. La técnica del antialiasing se caracteriza por disminuir los cambios bruscos de color y atenuar las transiciones suaves en la frontera de representaciones gráficas, con esto se crea la ilusión de la mezcla de pixeles o difuminado de bordes.

En las pestañas Instrucciones y Código se detallará en la implementación que sigue este proceso con sus comandos y código fuente (comentado para mayor claridad).

linkSolución y Resultados

rasterizationFull.js
1linkfunction draw() {

2link   //Poner fondo blanco en el canvas

3link   background(255);

4link   //Dibujar la cuadricula y rasterizar el triangulo actual

5link   drawSquares();

6link   //Grosor del trazado 

7link   strokeWeight(1);

8link   //Trazar con color negro el triangulo actual

9link   stroke(0);

10link   triangle(ax, ay, bx, by, cx, cy);

11link   //Marcador de punto en la ubicacion del cursor en el canvas

12link   point(mouseX, mouseY);

13link   //Cambio de coordenadas de los vertices del triangulo segun el click con los botones central, derecho e izquierdo

14link   if (mouseIsPressed) {

15link       if (mouseButton == LEFT) {

16link           ax = mouseX;

17link           ay = mouseY;

18link       }

19link       if (mouseButton == RIGHT) {

20link           bx = mouseX;

21link           by = mouseY;

22link       }

23link       if (mouseButton == CENTER) {

24link           cx = mouseX;

25link           cy = mouseY;

26link       }

27link   }

28link}

29link

30link//Algoritmo de Rasterizacion que emplea coordenadas baricentricas

31linkfunction drawSquares() {

32link    //Inicializacion de contadores

33link    i = 0;

34link    j = 0;

35link    col = 0;

36link    row = squaresF;

37link    //Recorrer las columnas y las filas

38link    for (i = 0; i <= squares; i++) {

39link        col = 0;

40link        for (j = 0; j <= squares; j++) {

41link            //Grosor del trazo

42link            strokeWeight(1);

43link            //Si el punto medio de la celda que estoy analizando esta dentro del area cubierta por el triangulo

44link            if (inside_triangle(ax, ay, bx, by, cx, cy, col + pointA, row + pointA)) {

45link                //Calcular las coordenadas baricentricas del punto medio de la celda

46link                barycentric(ax, ay, bx, by, cx, cy, col + pointA, row + pointA);

47link                //Rellenar la celda con la interpolacion entre las coordenadas baricentricas y los colores definidos

48link                fill(239 * alpha, 247 * beta, 255 * gamma );

49link                //Dibujar la celda recien analizada

50link                rect(col, row, squaresF, squaresF);

51link            } else {

52link                //Si el punto medio no esta en el area cubierta por el triangulo

53link                //Rellenar de color blanco la celda

54link                fill(255, 255, 255);

55link                //Dibujar la celda recien analizada

56link                rect(col, row, squaresF, squaresF);

57link            }

58link            //Pintar el en canvas el punto medio de la celda analizada

59link            strokeWeight(3);

60link            strokeCap(ROUND);

61link            fill(0, 224, 0);

62link            //Poner el color de trazo en negro para el siguiente ciclo

63link            stroke(153, 153, 255);

64link            point(col + pointA, row + pointA);

65link            stroke(0);

66link            //Actualizar la variable col con el valor de la ubicacion del inicio de la siguiente columna de celdas

67link            col += squaresF;

68link        }

69link        //Actualizar la variable row con el valor de la ubicacion del inicio de la siguiente fila de celdas

70link        row += squaresF;

71link    }

72link    //Poner el rellenado en transparente para el siguiente ciclo del canvas

73link    fill(255, 255, 255, 0);

74link}

75link

76link//Definicion de coordenadas baricentricas a partir de tres puntos de un triangulo (a, b, c) y un punto arbitrario p=(x,y)

77linkfunction barycentric(ax, ay, bx, by, cx, cy, x, y) {

78link   var d = (by - cy) * (ax - cx) + (cx - bx) * (ay - cy);

79link   alpha = ((by - cy) * (x - cx) + (cx - bx) * (y - cy)) / d;

80link   beta = ((cy - ay) * (x - cx) + (ax - cx) * (y - cy)) / d;

81link  gamma = 1.0 - alpha - beta;

82link   alphaS = nf(alpha, 1, 2);

83link   betaS = nf(beta, 1, 2);

84link   gammaS = nf(gamma, 1, 2);

85link}

86link

87link// Comprobacion de si un punto (x, y) dado esta dentro del area que cubre un triangulo con vertices a, b, c

88link// 1. Calcula coordenadas baricentricas del punto p

89link// 2. Comprueba si los valores de alpha, beta y gamma tienen valores entre 0 y 1, es decir demostrando que p esta dentro del triangulo

90linkfunction inside_triangle(ax, ay, bx, by, cx, cy, x, y) {

91link    var d = (by - cy) * (ax - cx) + (cx - bx) * (ay - cy);

92link    var alpha = ((by - cy) * (x - cx) + (cx - bx) * (y - cy)) / d;

93link    var beta = ((cy - ay) * (x - cx) + (ax - cx) * (y - cy)) / d;

94link    var gamma = 1.0 - alpha - beta;

95link    return !(alpha < 0 || alpha > 1 || beta < 0 || beta > 1 || gamma < 0 || gamma > 1);

96link}

Se mostró exitosamente como es la implementación lógica y fundamentación teórica de la rasterización por medio de coordenadas baricéntricas.

A pesar de visualizar un acercamiento en 2D, se resalta la capacidad de este proceso de representación de figuras 3D ya que es capaz de mapear geometrias hasta los pixeles; de igual manera se tiene la posibilidad de paralelizar este proceso en caso de necesitar el procesamiento de figuras poligonales grandes o con gran cantidad de figuras componiendolo.

Entre las aplicaciones de la rasterización además de las mencionadas anteriormente, se encuentran el filtrado de texturas, donde se toma en cuenta la distancia de los objetos con relación al observador sobre los cuales se aplica la textura para mejorar la definición de la misma; el mapeado del entorno empleado cuando la posición de las texturas dependen del punto de vista (por ejemplo los reflejos de un espejo); el mapeado de rugosidad o variaciones de texturas según la profundidad proporcionada por las coordenadas.

Particularmente se considera la industria del entretenimiento de videojuegos como el nicho de aplicación más grande debido a la demanda de procesamiento de gráficos de manera veloz, considerando que las texturas en el diseño de videojuegos modernas son mucho más detallasas y con comportamientos realistas que requieren de un alto rendimiento al transformar objetos en pixeles de manera rápida.

Finalmente se resalta la utilidad de la técnica de antialiasing al permitir una mejor aproximación y definición de los polígonos al momento de rasterizarce.

linkReferencias y Fuentes:

Razterization Definicion

Razterization Tutorial

Razterization Aplications

Antialiasing