Programación en Lenguaje Ensamblador

-El Verdadero Lenguaje de las Máquinas-

Programación Gráfica: Fundamentos de Recorte

–Como Cortar Objetos 3D–

Como ya dije hace mucho, una de las técnicas que uso para ver que un libro sobre gráficas por computadora realmente toma el tema de la programación gráfica en serio es ver como manejan los algoritmos de recorte. El recorte en gráficas vectoriales es algo que se utiliza casi tanto como las ecuaciones de proyección pero que en la mayoría de los casos se hace de manera transparente al usuario. Lo interesante es que los algoritmos de recorte no solo se usan para rebanar figuras en el espacio sino que también se utilizan para validar contactos, física, simulación de linea de vista como cuando queremos saber si el jugador puede ser visto por una unidad enemiga o para algo tan elemental como separar lo que queda dentro de nuestro campo visual en un mundo 3D de lo que queda afuera, aunque esto último solo lo saben los que han intentado hacer su propio engine gráfico pues como dije al principio, los motores actuales hacen esto de manera completamente transparente al desarrollador. Pero antes de explicar como funciona el recorte veamos una pequeña historia que viví de propia mano hace no mucho tiempo.

Como ya dije, el recorte de lineas, polígonos y sólidos basados en vectores en el espacio es algo tan elemental en la programación gráfica como las ecuaciones de proyección en perspectiva o la transformación de coordenadas. Pues bueno, una vez estaba muy feliz en la comunidad de internet de desarrollo de videojuegos que todos los creadores de videojuegos de latinoamérica conocen y alguien llegó con la noticia de que los programadores (esos si son programadores) de Konami habían implementado un sistema de recorte arbitrario en tiempo real en su nuevo motor gráfico llamado entonces el Fox Engine. Si bien tiene un gran mérito implementar un sistema de recorte arbitrario y en tiempo real por la complejidad de las estructuras de datos que están involucradas hacer un recorte en el espacio no es algo tan sorprendente como suena. De hecho, si los programadores de ese sistema gráfico no hubieran sabido desde antes como hacer un recorte no habría sido ni siquiera capaces de programar el engine gráfico en primer lugar. Como es de esperarse tales declaraciones tuvieron revuelo y creo que por ahí hasta salieron rodando algunas sandias virtuales. En ese entonces no quise hacerla de pleito porque de todos modos la mayoría de la gente ahí presente no me iba a entender pero aquí que estoy entre programadores si que puedo explicar con toda tranquilidad en que consiste el recorte en 3D y toda la ciencia que hay detras de este.

Recorte de lineas rectas en el espacio

Lo primero que tenemos que saber sobre el recorte en 3D es que este se da exclusivamente entre rectas y planos en el espacio. En los casos que estemos trabajando con un espacio vectorial en dos dimensiones se considera que los planos de recorte son perpendiculares al plano donde se lleva a cabo la acción cual si se tratase de muros. Lo segundo es que siempre es el plano el que recorta a la linea recta, nunca se recortan dos lineas rectas porque hacer que dos rectas en el espacio 3D se crucen es casi imposible ni tampoco se cortan dos planos porque el resultado es una recta con un sinfin de ecuaciones posibles. En cambio, cuando un plano corta a una recta (o visto de otro modo cuando una recta perfora un plano) el resultado es un sencillo número que dependiendo de nuestras necesidades puede convertirse en las coordenadas de un punto en el espacio, un valor escalar o una simple bandera de decisión para la lógica del juego. En el caso del recorte se trata de lo primero, de obtener la coordenada del espacio donde el segmento de recta y el plano se intersectan. La última cosa que deben de saber del recorte es que no basta con ser capaces de calcular el punto donde la linea y el plano se encuentran sino que es necesario redefinir por completo el modelo 3D a nivel de sus estructuras de datos. Y cuando digo completamente me refiero desde la definición de sus vértices, aristas y caras hasta el detalle de superficie y la forma como lo afectan otros modelos cercanos. Incluso en algunos casos puede ocurrir que al cortar un objeto este se multiplique (se hagan dos o mas) aunque si se siguen ciertas reglas estos casos pueden presentarse muy pocas veces.

En la primera imagen tenemos la situación en la que un segmento de recta definido por sus dos extremos inicial y final son cortados por un plano en el espacio. Y en la segunda imagen tenemos dos representaciones de un plano y un segmento de recta. Repasemos como se definan matemáticamente estas dos entidades. Como recordarán, un segmento de recta o arista tiene un punto inicial p0 y un punto final p1 y si la definimos en forma paramétrica existe un parámetro t que va de cero a uno entre estos dos puntos. Por su parte un plano se define por un punto en el espacio y un vector perpendicular que lo traspasa del mismo modo que un clavo a un trozo de madera. Aunque como ya saben es posible obtener estos dos datos a partir de 3 puntos en el espacio que no estén alineados que es como suelen definirse las superficies planas en los juegos 3D. El recorte de lineas toma como entradas los 2 puntos extremos del segmento de la linea que queremos cortar y el punto y el vector que definen el plano de recorte. El algoritmo de recorte regresa como resultado el valor del parámetro t en el que el plano recorta a la linea. Existen muchos algoritmos usados para hacer el recorte pero los dos mas usados y del que todos estos descienden son los algoritmos de recorte de Cohen-Sutherland y el de Liang-Barsky. El algoritmo de Cohen-Sutherland es bueno para computadoras muy sencillas que solo puedan manejar valores enteros y obtiene el punto de intersección por medio de la búsqueda de raices conocida como Método Bolzano mientras que el de Liang-Barsky aplica una fórmula directa y sencilla pero que requiere que el equipo tenga capacidad de procesamiento de punto flotante. En las siguientes entradas vamos a examinar ambos algoritmos y tomaremos lo mejor de cada uno. De momento solo necesitamos saber que los algoritmos de recorte toman como entrada una recta definida por dos puntos y un plano de recorte que ha de funcionar como una navaja. La función retorna el parámetro t en el que el segmento de recta y el plano de recorte se intersectan. Función que veremos con detalle en la siguiente entrada.

Con el parámetro t devuelto podemos hacer muchas cosas. La mas obvia es obtener la coordenada espacial en la que se da el corte. Para hacer esto basta sustituir el valor de t en las ecuaciones paramétricas de la recta. Aunque puede darse también el caso en el que la recta y el plano sean paralelos entre si y nunca se corten o incluso que la linea sea coplanar al plano de corte que al final es como si no se cortara. Otra cosa que puede pasar y de hecho pasa la mayoría de las veces si no se hace una buena validación es que el parámetro t devuelto por la función de recorte de un valor fuera del rango de 0 a 1. Cuando esto sucede la linea si es cortada por el plano, pero en un punto que está mas allá de sus extremos finales. Recuerden que matemáticamente las lineas rectas en el espacio tienen longitud y delgadez infinitas. Y para colmo de males, encontrar el punto en el espacio en los que un plano y una linea se intersectan es apenas una muy pequeña parte de lo que es el recorte.

Antes y despues de recortar

Resulta que hay que hacer una larga cantidad de validaciones y cálculos previos antes de hacer un recorte y una vez obtenidos los puntos en los que las lineas son cortadas es necesario reconstruir todo el modelo para poder representarlo en pantalla. Como ambos temas son demasiado extensos y esta entrada ya me quedó muy larga solo voy a mencionar las técnicas que hacen esto y en otra ocasión las describiré en detalle. La primera de las validaciones es conocida como la prueba dentro-fuera en donde nos aseguramos que la linea tenga sus extremos en lados opuestos del plano de recorte. Esto se hace evaluando las coordenadas de los vértices en la ecuación del plano y comparando el signo. Proceso que en los procesadores Intel actuales se resume a una sola instrucción de ensamblador. Si los signos son opuestos la linea puede ser cortada. Esta prueba dentro-fuera se extiende a algo llamado Prueba de Eliminación de Cohen-Sutherland que se usa para generar vistas de mundos complejos y determinar contactos en el espacio de varios miles o millones de vectores. Otra validación, que en realidad es una potente optimización consiste en aprovecharse de que hacer recortes usando planos perpendiculares a los ejes coordenados toma la tercera parte de las operaciones matemáticas que requiere hacerlo respecto a un plano cualquiera, así que es posible escalar y sesgar todos los objetos de nuestro mundo 3D y minimizar las operaciones de recorte. Esto puede parecer un esfuerzo inutil pero reescalar el mundo usando matrices es mucho mas eficiente que hacer recortes arbitrarios e incluso puede agregarse este escalamiento a la matriz de transformación de vista de modo que cambiaríamos lo que podrían ser varios millones de validaciones y dos tercios de otros millones de cálculos de punto flotante por una humilde multiplicación de matrices de 4 por 4 que podemos hacer en menos de una docena de ciclos de reloj.

De acuerdo, lo anterior fue apenas la preparación para cortar los modelos 3D. Ahora veamos que ocurre luego de que hemos dado el hachazo. En realidad hacer un recorte en 3D es mas parecido a una amputación quirúrgica de una extremidad que a un simple corte de un material sin vida, pues no solo debemos de ser cuidadosos para no cortar si no hay necesidad sino que después de haberlo hecho necesitamos hacer toda una reconstrucción. Lo primero que obtenemos luego de hacer un recorte es una lista de coordenadas xyz en la que cada una de las aristas se cruza con el plano de recorte. Si solo queremos obtener el punto donde se cruzan no necesitamos hacer nada mas pero lo mas probable es que queramos quedarnos con las piezas separadas. Y ahí es donde comienzan los problemas porque ahora cada una de las aristas se habrá duplicado. Digamos que tenemos una arista cuyos puntos extremos son p0 y p1 y que el recorte se da en un punto intermedio que llamaremos pR que obtuvimos sustituyendo el parámetro t dado por la ecuación paramétrica pR = p0 + (p1-p0)*t. Ahora tendremos 2 aristas separadas. La primera va del punto p0 a pR y la segunda va de pR a p1. Si mas adelante queremos reposicionar estas nuevas aristas obtenidas basta con cambiar sus nuevos valores iniciales y finales. Pero el problema de la reconstrucción no termina aquí.

Recortar un modelo 3D de estructura de alambre es el caso mas sencillo de reconstrucción de un modelo post-corte. El caso mas común y verdaderamente complicado es cuando queremos recortar un modelo construido a partir de polígonos con detalle de superficie. Pues a la hora de reconstruir el polígono no solo se corre el riesgo de que estos se dividan en muchos mas pequeños sino que deben de reconstruirse. Esta es una de las muchas razones por la que usamos caras triangulares para construir objetos complejos. Los triángulos al ser recortados respecto a planos de recorte rara vez se dividen en mas de dos partes, sus coordenadas de textura y normales son mucho mas sencillas de ajustar luego de ser cortados y en el caso del recorte de volumen de vista que es la aplicación mas importante del recorte ya existen muchos algoritmos para cortar estos triángulos de manera eficiente e incluso eliminarlos por completo sin necesidad de cortarlos. En el caso del recorte de vista no importa mucho si recortamos un polígono y lo dejamos abierto. El problema es cuando queremos recortar un sólido en un editor 3D o peor aun hacerlo en tiempo real como en el Fox Engine de Konami. Pues no solo hay que redefinir por completo vértices, aristas y polígonos sino que incluso es necesario definir polígnos y aun sólidos que antes no existían. Piensen un momento en el caso de una sandia. En su versión original se usa una textura verde con blanco para simular la cáscara de la fruta. Pero a la hora de cortarla necesitamos una textua roja que muestre el interior de la fruta. A menos que de inicio hubiéramos definido un conjunto de propiedades internas de la sandia esta ni sus polígonos van a existir cuando hagamos el recorte. Otro buen ejemplo del recorte es la madera. Podemos usar una textura para la parte externa pero si usamos la misma imagen va a parecer como si la pieza de madera estuviera forrada con papel adhesivo color madera. Ahora veamos como se hace para cerrar una figura que ha sido cortada de esta manera.

Recorte y Reconstrucción de Sólidos 3D

Cuando recién cortamos una figura hecha por polígonos con detalle de superficie y solo tenemos la lista de puntos donde cada arista es cortada por los planos tenemos que reconstruir cada polígono de manera individual. Afortunadamente existe un algoritmo que hace esto al momento de recortar que se llama Algoritmo de Sutherland-Hodgman que para explicarlo en pocas palabras funciona igual que uno de esos plásticos adhesivos que se usan para sellar los recipientes de comida. Ese algoritmo recorre los vértices del polígono en forma circular y agrega o elimina vértices dependiendo de los puntos obtenidos luego de recortar. Para los casos en los que quedan huecos en el modelo 3D se aplica una variante del algoritmo de Sutherland-Hodgman basado en el conocido (aunque no por todos los titulados) Algoritmo del Cerco Envolvente en el que se van creando nuevas caras conforme un plano ‘envolvente cubre las partes abiertas del modelo 3D. Una vez obtenidos los datos sobre vértices, aristas y caras de estos nuevos polígonos que antes no existian ya tenemos un modelo 3D usable, aunque por regla general los recortes nunca se hacen uno solo a la vez y en muchos casos es necesario repetir el proceso una y otra vez como en el caso del viejo recorte de vista.

Ya para terminar porque esta entrada quedó demasiado larga y no encuentro por donde recortarla quiero dejar claro el porqué los algoritmos de recorte son tan necesarios en Programación Gráfica y a la vez tan poco conocidos por quienes reciben dinero por dedicarse a estas cosas. Resulta que la aplicación mas elemental del recorte 3D es la creación del volumen de vista. Tema que veremos en un futuro espero no muy lejano. Las tecnologías actuales usadas por los aficionados hacen este recorte de manera automática y los que usan software de modelado 3D ni siquiera son conscientes de que hay que recortar aquello que queda fuera de nuestro campo visual. Es por eso que esto del recorte no es entendido por cualquiera. Sobre todo por la parte de la redefinición de datos involucrada en un buen corte. Recuerdo en tiempos de los primeros editores 3D que el ponerle nombre a cada sólido luego de cortarlo era un proceso tedioso y desconcertante. Manejar esta redefinición de datos requiere mucho conocimiento de programación gráfica y no solo de como hacer llamadas a una API. Es decir, de cosas que no cualquiera que diga dedicarse a esto de los juegos 3D domina realmente. Es por eso que mi último consejo es que si quien está leyendo esto tiene bajo su mando a un equipo de desarrollo de videojuegos y quiere reducir costos mandando a algunos empleados de vacaciones forzadas páselos de uno en uno a su oficina donde tiene su computadora con monitor dual y dígale que le explique como funcionan los algoritmos de recorte. Verá como estos algoritmos no solo sirven para recortar lineas y polígonos. ¡También sirven para hacer recorte de personal!

Anuncios

enero 27, 2012 - Posted by | Uncategorized | , ,

Aún no hay comentarios.

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: