Programación en Lenguaje Ensamblador

-El Verdadero Lenguaje de las Máquinas-

Programación Gráfica y los Polígonos en 3D

–Triángulos y Planos en el Espacio–

En los juegos 3D es muy común escuchar que tal o cual modelo está compuesto por no se cuantos miles y miles de polígonos. Cuando escuchamos sobre las capacidades de algún coprocesador gráfico normalmente se nos dice que puede procesar una determinada cantidad de polígonos por segundo y hace algunas entradas vimos aquí que las figuras en los juegos 3D se componen de vértices, aristas y polígonos. Hoy vamos a ver todo lo que un programador de videojuegos debe de saber sobre los polígonos planos en el espacio.

Lo primero que tenemos que dejar claro es que los famosos “polígonos” que forman nuestros amados modelos 3D en realidad son todos triángulos. Los triángulos tienen una serie de propiedades matemáticas que los hacen especialmente eficientes en el campo de la programación gráfica. Por ejemplo, los 3 puntos que definen los vértices de un triángulo siempre se encontrarán en un mismo plano en el espacio (a menos que estén todos dispuestos en linea recta). Cualquier figura que se nos ocurra puede ser subdividida en triángulos, los triángulos pueden ser procesados de un solo paso en sistemas de procesamiento vectorial, siempre son convexos, pueden ser recortados con muy pocas operaciones y muchas otras cosas mas que ya verán cuando tengan que programar estas cosas en una PC. En la primera imagen vemos un triángulo formado por 3 vértices (en plastilina blanca) y 3 aristas (en madera). Como pueden ver, pueden poner ese triángulo en la posición que ustedes quieran y siempre quedará plano.

Como ya saben las caras poligonales se definen como una lista de índices a los 3 vértices que lo conforman. Pero un plano a nivel matemático es mucho mas que eso, lo bueno es que podemos obtener toda la información del plano en el espacio en el que se encuentra este polígono con tan solo los 3 vértices que forman el polígono. Para eso lo primero que tenemos que hacer es convertir esos 3 vértices en dos vectores a los que les podamos aplicar un producto vectorial. Si recuerdan en la nota sobre como modelar objetos en 3D, se dijo que los vértices del polígono se escribian en sentido contrario al de las manecillas del reloj cuando uno los veía de frente. Entonces tenemos los 3 puntos que forman el polígono como P0, P1 y P2. Para obtener los dos vectores U y V hacemos una resta vectorial de modo que U = P1 – P0 y V = P2 – P1. La diferencia entre las coordenadas entre 2 vértices es igual a las componentes del vector que los une. O lo que es lo mismo, se hace una minitraslación. En fin, ya con los vectores U y V podemos hacer un producto vectorial y obtener un vector normal al plano al que llamaremos aquí vector N. Por cierto, el vector N puede llegar a tener una magnitud de cero o un valor muy cercano a este en caso de que los 3 puntos proporcionados estén en linea recta. En cuyo caso no podríamos representar un plano, pues el seno del ángulo entre los 2 vectores U y V sería cero.

En la segunda imagen se ve junto con el triángulo que define nuestro polígono otra pequeña flecha vertical de punta roja. Ese es nuestro vector normal N. Ese vector atraviesa el plano por completo como si fuera un clavo. No importa que punto del plano elijamos, como se trata de una superficie plana este vector va a ser siempre el mismo. Piensen en una de esas camas de clavos en las que descansan los magos de la India. Ahora bien, a menos que el plano que contiene al polígono pase por el origen todavía nos falta un último paso para obtener toda la información del plano. Las coordenadas de cualquiera de los 3 vértices. Aunque nos habría servido igual cualquier otro punto de los infinitos que caben dentro del plano. Ahora veamos la ecuación del plano a nivel matemático.

Ecuación del Plano
Ax + By + Cz + D = 0

Para obtener la ecuación del plano que contiene el polígono definido por los 3 vértices necesitamos calcular los valores de A, B, C y D. Los 3 primeros corresponden a las componentes x,y,z del vector normal N. Para calcular D necesitamos las coordenadas de cualquiera de los 3 puntos que componen el triángulo. Digamos que elegimos P0. Sus coordenadas serían P0_X, P0_Y y P0_Z. Entonces hacemos lo siguiente:

A * (x – P0_x) + B * (y – P0_Y) + C * (z – P0_Z) = 0

Luego de sumar y multiplicar se obtiene el valor de D. Aunque bien hubiéramos calculado D directamente con la expresión -1*(A*P0_X + B*P0_Y + C*P0_Z). Ahora bien, seguro se preguntarán para que demonios queremos esta aburrida expresión. Pues esta aburrida expresión puede servirnos para mas cosas que solo dibujar un simple polígono. Lo mas directo es sustituir los valores de x,y,z por cualquier punto en el espacio. Si el resultado de la expresión es cero o muy cercano a cero (la precisión en una computadora es finita) entonces el punto está dentro del plano. Si el resultado es positivo el punto se encuentra por encima del plano y si es negativo entonces es un lugar por debajo de este. Esta información es muy util para saber de que lado del plano nos encontramos y se usa para detectar colisiones y recortar figuras. La normal del plano nos da información hacia donde apunta la cara del plano. Podemos por ejemplo saber que dos planos son perpendiculares entre si cuando hacemos un producto escalar entre sus normales y el resultado es igual a cero. Si quisiéramos crear por ejemplo una figura alargada (lo que en arte digital llaman extrusión o ‘lofting’ basta tan solo con cambiar el valor de D y redibujar la figura. El vector normal al plano se usa para cálculos de textura e iluminación sobre el polígono, aunque existe una técnica conocida como Normal Mapping en la que se asigna un vector arbitrario a cada punto del polígono para dar la apariencia de que este no es plano. Pero el uso mas interesante de la ecuación de los planos en el espacio es sin duda la proyección geométrica. Pues lo que vemos en pantalla cuando jugamos un videojuego 3D es la proyección sobre un plano de una parte de ese mundo vectorial, como si viéramos por una ventana. Esa ventana es un plano en el espacio y necesitamos lo visto hasta ahora para poder hacerlo.

Algunas otras cosas que deben de tener en cuenta con esto de los planos es que a nivel matemático los planos tienen una extensión infinita y su grosor es infinitamente pequeño. Cuando un plano es perpendicular a uno de los ejes coordenados los valores de A, B o C excepto el del eje que lo traspasa son iguales a cero. Por ejemplo, si hacen esta operación con cualquier polígono en el plano z = 0 que se puede desplegar en la hoja de libreta A y B y D siempre les va a dar cero. Es posible calcular el punto en el que el plano corta los ejes coordenados si dividen los valores de A, B o C entre -D. Por cierto, un mismo plano en el espacio puede ser definido por lo que parecen un sinfin de ecuaciones diferentes. Pero esto siempre va a poder descubrirse si existe un factor por el cual A, B, C y D puedan multiplicarse. Se recomienda en ciertos casos dividir el vector N entre su longitud para evitar errores de pérdida de precisión a la hora de hacer los cálculos.

Por cierto, no está de mas una pequeña advertencia, hay una correspondencia entre los planos en el espacio 3D y las lineas rectas en el mundo 2D. Se considera que el 2D es el plano XY donde Z es igual a cero. La ecuación de este plano es precisamente Z = 0. Una recta en ese plano es en realidad un plano perpendicular a Z = 0 que se alza sobre la hoja como lo haría un muro. Esto es importante que lo tengan en cuenta porque esto tiene muy poco que ver con lo que consideramos una linea recta en el espacio. En la siguiente entrada vamos a hablar sobre las rectas y otras curvas sencillas en el espacio, por ahora esperemos a que salga la nueva nota mientras rezamos a nuestros respectivos dioses que la reciente hola de inactividad en las redes mexicanas de desarrollo de videojuegos se deban a que están planeando algo grande o por lo menos que estén trabajando en algún nuevo juego que pueda pagar sus nóminas atrasadas.

Anuncios

noviembre 2, 2011 - Posted by | Uncategorized | , ,

13 comentarios »

  1. Desde luego te lo estás currando mucho. Es una lástima que actualmente no tenga mucho tiempo para poder ponerlo en práctica pero lo tengo pendiente seguro

    Comentario por JuDelCo | noviembre 3, 2011 | Responder

    • no hay prisa, si no ocurre nada raro esta nota va a seguir aqui por mucho pero mucho tiempo, ademas las matematicas para el 3D nunca se hacen obsoletas

      Comentario por asm86 | noviembre 3, 2011 | Responder

  2. que gran post tienes cumpa, quisiera que dentro de los temas que estas tratando en Computacion Grafica, hables de un temita llamado “Cuaterniones”, y dentro de ello rotacion en 3D usandolos….como solo hasta ahi he ahondado, creo que pedirte que tambien hables de escalamiento usando cuaterniones, seria abusar de tu buena voluntad, bueno me despido mandandote un fuerte abrazo y buenos deseos!!!

    Comentario por JuanD | noviembre 15, 2011 | Responder

    • Voy a tomarlo en cuenta, los cuaterniones aceleran los calculos en algunas computadoras pero no en otras. De momento no puedo escribir mucho asi que mejor que esperen sentados

      Comentario por asm86 | noviembre 16, 2011 | Responder

  3. Donde dices:

    “Para obtener los dos vectores U y V hacemos una resta vectorial de modo que U = P1 – P0 y V = P2 – P1. La diferencia entre las coordenadas entre 2 vértices es igual a las componentes del vector que los une. O lo que es lo mismo, se hace una minitraslación. En fin, ya con los vectores U y V podemos hacer un producto vectorial…”

    Es necesario hacer esa minitraslación o no ? (lo pregunto pues no lo indicas y luego en el modelo de la plastilina el vector perpendicular aparece en el CENTRO del polígono y no en uno de sus vértices….

    Comentario por JuDelCo | julio 21, 2012 | Responder

    • A nivel matematico un plano se extiende de manera infinita y su normal es la misma en cualquiera de sus puntos. Si la normal variara en sus puntos no seria un plano. Entonces el vector normal puede representarse en el centro, en uno de los vertices o incluso fuera del poligono subcontenido en el plano infinito en el que se encuentra.

      La minitraslacion no es necesaria, basta con obtener las componentes vectoriales de las aristas restando los vertices. Nota que si uno de los vertices fuera el origen y tomaras ese vertice como la cola de los vectores. Las coordenadas de los otros 2 vertices serian directamente las componentes vectoriales de los 2 vectores que necesitas para obtener la normal. Recuerda que el orden en que tomas estos vectores indican el signo del vector normal resultante que te da el producto cruz.

      Comentario por asm86 | julio 21, 2012 | Responder

  4. Por otro lado… indicas que la ecucación del plano es Ax + By + Cz + D = 0 (ahí todo bien). Que ABC son las coord del vector normal N, de acuerdo, lo que no entiendo es el paso a la siguiente ecucación para calcular D

    A * (x – P0_x) + B * (y – P0_Y) + C * (z – P0_Z) = 0

    Si ABC es lo dicho anteriormente y P0_x/y/z son las coord de uno de los puntos del polígono, ¿qué es x / y / z?

    En cambio la expresión D = -1*(A*P0_X + B*P0_Y + C*P0_Z) sí que la veo lógica…

    Comentario por JuDelCo | julio 21, 2012 | Responder

    • Para construir un plano necesitas dos cosas, un punto cualquiera del plano y un vector normal. P0_x, P0_y, P0_z son las coordenadas de ese punto en el plano y A, B, C las componentes del vector normal. X/Y/Z son todas las tercias de valores que cumplen la ecuacion del plano. Cualquier conjunto de 3 valores que hagan la ecuacion del plano igual a cero son parte del plano y si pruebas la ecuacion con los otros 2 vertices debe de darte cero o algo muy cercano por aquello de la precision.

      D = 0 cuando el plano pasa por el origen. D es una relacion entre la distancia del origen al plano y los coeficentes de A, B y C.

      Comentario por asm86 | julio 21, 2012 | Responder

      • De acuerdo, pero para que esa expresión pueda ser usada antes se necesita calcular D con la segunda expresión, y en caso de dar 0 pues entonces si que se usaría, si da distinto a 0 entonces hay que incluirla en la primera expresión para que cuadre todo… (imagino que mi lió mental venía de ahí, del orden en el que han aparecido las ecuaciones)

        Comentario por JuDelCo | julio 22, 2012

      • D = 0 en los planos que pasan por el origen.

        Comentario por asm86 | julio 22, 2012

      • Otra observación a la que llegué ayer es que si realizas la mini-traslación de uno de los vectores que obtienes con los 3 vértices y ajustas su origen al del otro vector, y ENCIMA coges el punto del vértice donde coincide el origen de ambos vectores, no te va a servir para crear un plano (o si?)

        Comentario por JuDelCo | julio 22, 2012

      • Trasladar un plano para que pase por el origen no altera su vector normal.

        Digamos que tienes los vértices p0, p1 y p2 y necesitas obtener los dos vectores U y V a partir de ellos. El vector U se obtiene al tomar las coordenadas de p1 y restarle las de p0 y el V de tomar las coordenadas de p2 y restarle las de p0. Eso en matemático seria:

        U = p1 – p0
        V = p2 – p0

        Ahora, si trasladáramos los 3 vértices de modo que p0 fuera el origen usando una matriz de traslación T(-p0) las nuevas coordenadas que aquí llamaremos p0′, p1′ y p2′ quedarian así:

        p1′ = p1 – p0
        p2′ = p2 – p0
        p0′ = p0 – p0 = 0

        entonces:

        U = p1′
        V = p2′

        De este modo conviertes las coordenadas de los vértices directamente en las componentes vectoriales que necesitas para calcular la normal del plano que contiene el polígono con un producto vectorial. Digamos que la normal es N

        N = U x V

        Luego usas las componentes del vector N para obtener la ecuación del plano y para obtener D simplemente tomas cualquiera de los vértices originales (antes de trasladarlos) y los sustituyes en la ecuación. Si las componentes vectoriales de N son Nx, Ny y Nz y las coordenadas del punto del polígono son Px, Py y Pz entonces tienes

        Nx(x-Px) + Ny(y-Py) + Nz(z-Pz) = 0

        que desarrollado es:

        Nx*x + Ny*y + Nz*z + (-Nx*Px -Ny*Py -Nz*z) = 0

        Recuerda que el orden en que se multiplican los vectores U y V define hacia donde apunta la normal del plano. UxV = -(VxU). Esta propiedad se usa para eliminación de partes ocultas o para determinar contacto de sólidos.

        Comentario por asm86 | julio 22, 2012

      • Vale no he dicho nada, si que debería poderse. El punto está solo para indicar a que altura corta el plano al vector (o eso entiendo) xD

        Comentario por JuDelCo | julio 22, 2012


Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: