Construyamos un motor gráfico 3D: Rasterización de segmentos de líneas y círculos

Hola, esta es la cuarta parte de nuestra serie sobre motores gráficos 3D. En esta ocasión, cubriremos la rasterización: el proceso de tomar una forma descrita por fórmulas matemáticas y convertirla en una imagen en tu pantalla.

Recapitulemos

Aquí tienes un repaso a las clases que hemos hecho hasta ahora:

1

Point Class

2

{

3

	Variables:

4

		num tuple[3]; //(x,y,z)

5

	Operators:

6

		Point AddVectorToPoint(Vector);

7

		Point SubtractVectorFromPoint(Vector);

8

		Vector SubtractPointFromPoint(Point);

9

		Null SetPointToPoint(Point);

10

	Functions:

11

		drawPoint; //draw a point at its position tuple

12

}

13

14

Vector Class

15

{

16

	Variables:

17

		num tuple[3]; //(x,y,z)

18

	Operators:

19

		Vector AddVectorToVector(Vector);

20

		Vector SubtractVectorFromVector(Vector);

21

		Vector RotateXY(degrees);

22

		Vector RotateYZ(degrees);

23

		Vector RotateXZ(degrees);

24

		Vector Scale(s0,s1,s2); //receives a scaling 3-tuple, returns the scaled vector

25

}

26

27

Camera Class

28

{

29

	Vars:

30

		int minX, maxX;

31

		int minY, maxY;

32

		int minZ, maxZ;

33

		array objectsInWorld; //an array of all existent objects

34

	Functions:

35

		null drawScene(); //draws all needed objects to the screen

36

}

Puedes consultar el programa de ejemplo de la tercera parte de la serie para ver cómo funcionan juntos.

Ahora, ¡vamos a ver algunas novedades!

Rasterización

La rasterización (o rasterización, si se quiere) es el proceso de tomar una forma descrita en un formato gráfico vectorial (o en nuestro caso, matemático) y convertirla en una imagen rasterizada (donde la forma se ajusta a una estructura de píxeles).

Como las matemáticas no siempre son tan precisas como necesitamos para los gráficos por ordenador, debemos utilizar algoritmos para ajustar las formas que describen a nuestra pantalla basada en números enteros. Por ejemplo, un punto puede caer en la coordenada \((3,2, 4,6)\) en matemáticas, pero cuando lo representamos, debemos empujarlo a \((3, 5)\) para que pueda encajar en la estructura de píxeles de nuestra pantalla.

Cada tipo de forma que rastericemos tendrá su propio algoritmo para hacerlo. Empecemos con una de las formas más sencillas de rasterizar: el segmento de línea.

Segmentos de línea

Los segmentos de línea son una de las formas más sencillas que se pueden dibujar, por lo que suelen ser una de las primeras cosas que se tratan en cualquier clase de geometría. Están representados por dos puntos distintos (uno inicial y otro final) y la línea que los une. El algoritmo más utilizado para rasterizar un segmento de línea se llama Algoritmo de Bresenham.

Paso a paso, el Algoritmo de Bresenham funciona así:

1. Recibe como entrada los puntos inicial y final de un segmento de línea.
2. Identificamos la dirección de un segmento de línea determinando sus propiedades \(dx\) y \(dy\) (\(dx = x_{1} - x_{0}\), \(dy = y_{1} - y_{0}\).
3. Determina las propiedades sx, sy, y la captura de errores (mostraré la definición matemática de estas a continuación).
4. Redondea cada punto del segmento de línea al píxel superior o inferior.

Antes de implementar el Algoritmo de Bresenham, vamos a crear una clase básica de segmento de línea para utilizarla en nuestro motor:

1

LineSegment Class

2

{

3

	Variables:

4

		int startX, startY; //the starting point of our line segment

5

		int endX, endY; //the ending point of our line segment

6

	Function:

7

		array returnPointsInSegment; //all points lying on this line segment

8

}

Si quieres realizar una transformación en nuestra nueva clase LineSegment, todo lo que tienes que hacer es aplicar la transformación elegida a los puntos inicial y final del LineSegment y luego colocarlos de nuevo en la clase. Todos los puntos intermedios se procesarán cuando se dibuje el propio LineSegment, ya que el Algoritmo de Bresenham solo requiere los puntos inicial y final para encontrar cada punto posterior.

Para que la clase LineSegment se adapte a nuestro motor actual, no podemos tener una función draw() integrada en la clase, por lo que he optado por utilizar una función returnPointsInSegment en su lugar. Esta función devolverá un array de todos los puntos que existen dentro del segmento de línea, permitiéndonos dibujar y seleccionar fácilmente el segmento de línea según sea necesario.

Nuestra función returnPointsInSegment() se parece un poco a esto (en JavaScript):

1

function returnPointsInSegment()

2

{

3

	//create a list to store all of the line segment's points in

4

	var pointArray = new Array();

5

	//set this function's variables based on the class's starting and ending points

6

	var x0 = this.startX;

7

	var y0 = this.startY;

8

	var x1 = this.endX;

9

	var y1 = this.endY;

10

	//define vector differences and other variables required for Bresenham's Algorithm

11

	var dx = Math.abs(x1-x0);

12

	var dy = Math.abs(y1-y0);

13

	var sx = (x0 & x1) ? 1 : -1; //step x

14

	var sy = (y0 & y1) ? 1 : -1; //step y

15

	var err = dx-dy; //get the initial error value

16

	//set the first point in the array

17

	pointArray.push(new Point(x0,y0));

18

19

	//Main processing loop

20

	while(!((x0 == x1) && (y0 == y1)))

21

	{

22

		var e2 = err * 2; //hold the error value

23

		//use the error value to determine if the point should be rounded up or down

24

 		if(e2 => -dy)

25

		{

26

			err -= dy;

27

			x0 += sx;

28

		}

29

		if(e2 < dx)

30

		{

31

			err += dx;

32

			y0 += sy;

33

		}

34

		//add the new point to the array

35

		pointArray.push(new Point(x0, y0));

36

	}

37

	return pointArray;

38

}

La forma más sencilla de añadir el renderizado de nuestros segmentos de línea en nuestra clase de cámara es añadir una simple estructura if, similar a la siguiente:

1

	//loop through array of objects

2

	if (class type == Point)

3

	{

4

		//do our current rendering code

5

	}

6

	else if (class type == LineSegment)

7

	{

8

		var segmentArray = LineSegment.returnPointsInSegment();

9

		//loop through points in the array, drawing and culling them as we have previously

10

	}

Eso es todo lo que necesitas para poner en marcha tu primera clase de forma. Si quieres aprender más sobre los aspectos más técnicos del Algoritmo de Bresenham (en particular las secciones de error), puedes consultar el artículo de Wikipedia sobre el mismo.

Círculos

Rasterizar un círculo es un poco más difícil que rasterizar un segmento de línea, pero no mucho. Utilizaremos el algoritmo del círculo de punto medio para hacer todo el trabajo pesado, que es una extensión del ya mencionado Algoritmo de Bresenham. Como tal, sigue pasos similares a los enumerados anteriormente, con algunas diferencias menores.

Nuestro nuevo algoritmo funciona así:

1. Recibe el punto central y el radio de un círculo.
2. Fijar a la fuerza los puntos en cada dirección cardinal
3. Recorre cada uno de nuestros cuadrantes, dibujando sus arcos

Nuestra clase de círculo será muy similar a nuestra clase de segmento de línea, con un aspecto similar al siguiente:

1

Circle Class

2

{

3

	Variables:

4

		int centerX, centerY; //the center point of our circle

5

		int radius; //the radius of our circle

6

	Function:

7

		array returnPointsInCircle; //all points within this Circle

8

}

Nuestra función returnPointsInCircle() se va a comportar de la misma manera que la función de nuestra clase LineSegment, devolviendo un array de puntos para que nuestra cámara pueda renderizarlos y seleccionarlos según sea necesario. Esto permite a nuestro motor manejar una variedad de formas, con solo pequeños cambios necesarios para cada uno.

Este es el aspecto que tendrá nuestra función returnPointsInCircle() (en JavaScript):

1

function returnPointsInCircle()

2

{

3

	//store all of the circle's points in an array

4

	var pointArray = new Array();

5

	//set up the values needed for the algorithm

6

	var f = 1 - radius; //used to track the progress of the drawn circle (since its semi-recursive)

7

	var ddFx = 1; //step x

8

	var ddFy = -2 * this.radius; //step y

9

	var x = 0;

10

	var y = this.radius;

11

12

	//this algorithm doesn't account for the farthest points, 

13

	//so we have to set them manually

14

	pointArray.push(new Point(this.centerX, this.centerY + this.radius));

15

	pointArray.push(new Point(this.centerX, this.centerY - this.radius));

16

	pointArray.push(new Point(this.centerX + this.radius, this.centerY));

17

	pointArray.push(new Point(this.centerX - this.radius, this.centerY));

18

19

	while(x < y) {

20

	 	if(f >= 0) {

21

			y--;

22

			ddFy += 2;

23

			f += ddFy;

24

		}

25

		x++;

26

		ddFx += 2;

27

		f += ddFx;

28

29

		//build our current arc

30

		pointArray.push(new Point(x0 + x, y0 + y));

31

		pointArray.push(new Point(x0 - x, y0 + y));

32

		pointArray.push(new Point(x0 + x, y0 - y));

33

		pointArray.push(new Point(x0 - x, y0 - y));

34

		pointArray.push(new Point(x0 + y, y0 + x));

35

		pointArray.push(new Point(x0 - y, y0 + x));

36

		pointArray.push(new Point(x0 + y, y0 - x));

37

		pointArray.push(new Point(x0 - y, y0 - x));

38

	}

39

40

	return pointArray;

41

}

Ahora, ¡solo tenemos que añadir otra sentencia if a nuestro bucle de dibujo principal, y estos círculos estarán totalmente integrados!

Así es como puede verse el bucle de dibujo actualizado:

1

	//loop through array of objects

2

	if(class type == point)

3

	{

4

		//do our current rendering code

5

	}

6

	else if(class type == LineSegment)

7

	{

8

		var segmentArray = LineSegment.returnPointsInSegment();

9

		//loop through points in the array, drawing and culling them as we have previously

10

	}

11

	else if(class type == Circle)

12

	{

13

		var circleArray = Circle.returnPointsInCircle();

14

		//loop through points in the array, drawing and culling them as we have previously

15

	}

Ahora que hemos sacado nuestras nuevas clases, ¡vamos a hacer algo!

Maestro de Rasterización

Nuestro programa va a ser sencillo esta vez. Cuando el usuario haga clic en la pantalla, vamos a dibujar un círculo cuyo punto central es el punto en el que se ha hecho clic, y cuyo radio es un número aleatorio.

Echemos un vistazo al código:

1

main{

2

	//setup for your favorite Graphics API here

3

	//setup for keyboard input (may not be required) here

4

5

	var camera = new Camera(); //create an instance of the camera class

6

	camera.objectsInWorld[]; //create 100 object spaces within the camera's array

7

8

	//set the camera's view space

9

	camera.minX = 0;

10

	camera.maxX = screenWidth;

11

	camera.minY = 0;

12

	camera.maxY = screenHeight;

13

	camera.minZ = 0;

14

	camera.maxZ = 100;

15

16

	while(key != esc) {

17

		if(mouseClick) {

18

			//create a new circle

19

			camera.objectsInWorld.push(new Circle(mouse.x,mouse.y,random(3,10));

20

			//render everything in the scene

21

			camera.drawScene();

22

		}

23

	}

24

}

Con un poco de suerte, ahora deberías ser capaz de utilizar tu motor actualizado para dibujar algunos círculos impresionantes.

Conclusión

Ahora que tenemos algunas características básicas de rasterización en nuestro motor, ¡podemos finalmente empezar a dibujar algunas cosas útiles en nuestra pantalla! Nada demasiado complicado todavía, pero si quisieras, podrías juntar algunas figuras de palo, o algo por el estilo.

En el siguiente post, vamos a echar otro vistazo a la rasterización. Solo que esta vez, vamos a configurar dos clases más para ser utilizadas dentro de nuestro motor: triángulos y cuadriláteros. ¡Sigue atento!