La demanda en aumento de realismo en los juego de 3D - en términos de ambas la complejidad de la escena y la velocidad de la animación - están presentando un esfuerzo excesivo en las operaciones actuales de bajo nivel, operaciones computacionalmente costosas de dibujo de gráficos. A pesar de que estas rutinas siendo ampliamente optimizadas, especializadas, y a menudo siendo implementadas en lenguaje ensamblador o aún en hardware, número en aumento constante de requerimientos de dibujo para un solo marco de animación causa que estos sistemas se sobrecarguen, degradando el desempeño global. Para balancear estas demandas y reducir dramáticamente la carga en el subsistema de gráficos, presentamos un sistema que rápida e eficientemente encuentra una gran porción del mundo del juego que no es visible para el observador para cada marco de animación, y simplemente lo previene de ser mandado al sistema de gráficos. Construimos este mecanismo de búsqueda para partes que no se ven de algoritmos de gráficos comunes y fácilmente implementados.
En los últimos años, la mayoría del esfuerzo en escribir juegos de 3D basados en polígonos en máquinas de bajo nivel involucraba implementar un dibujo de escena especializado, o representación, canalización, típicamente consistiendo en las siguientes gradas, burdamente en este orden:
Cada estado proporciona una rutina muy básica de bajo nivel que potencialmente puede ser computacionalmente muy costosa. Los etapas de observar, de perspectiva y de recortar requieren de un gran número de operaciones aritméticas para los vértices y los bordes de cada polígono recibido; típicamente, la etapa más costosa involucra el rellenar y sombrear los polígonos, y resolver las relaciones de visibilidad en una base por pixel. Las operaciones básicas de canalización proceden como sigue: cada polígono en el mundo es
Esta es una muy costosa canalización que con frecuencia requiere implementación en lenguaje ensamblador o en hardware a fin de lograr el nivel de funcionamiento deseado.
Estas rutinas de nivel de pixel (o rastreo) prohibitivamente costosas han impuesto restricciones severas en la complejidad del mundo de 3D y en la generalidad del sistema global de gráficos. Con frecuencia, a fin de conformar estas restricciones los mundos de juego tenían que ser tan simples que la calidad de la escena desplegada era severamente impedida; aquellos de calidad de imagen más alta con frecuencia carecían suavidad de la animación o a veces ni podían ser animados (considere el caso de Myst.) Los motores de gráficos de tiempo real más sofisticados como (tales como esos utilizados en los juegos como Doom, Descent, y Quake) que son capaces de calidad más alta mientras que logran razones de marcos muy rápidas tienen canalizaciones de gráficos extremadamente especializadas; estas con frecuencia se diferencian dramáticamente de la que se describió previamente, y restringen la generalidad de los modelos usados imponiendo una estructura más compleja. Claramente, para los juegos, esta parece ser una muy ingeniosa estrategia que ha funcionado asombrosamente bien. De cualquier modo, estos tipos de motores de gráficos se pueden ser bastante difíciles de implementar, son con frecuencia no muy fácilmente llevados a diferentes sistemas de gráficos de computación, y sólo se benefician de la aceleración del hardware después de alguna modificación significante.
Más recientemente, con un desempeño mejorado a nivel base, una selección más grande de favorablemente bibliotecas de gráficos estandarizadas (OpenGL [ver http://www.sgi.com/Technology/openGL/] y Direct3D [ver http://www.microsoft.com/mediadev/graphics/D3Dintro.html]), y la llegada de las tarjetas de aceleración de gráficos de 3D, los esfuerzos de escribir motores de gráficos de juegos de 3D pueden ser en una manera más abstractos, grandemente simplificados y más fácilmente generalizados. Dentro de este apenas establecido marco de trabajo, al programador de juegos promedio se le permite asumir que tal canalización de gráficos de nivel bajo ya existe en todos los sistemas. Esto les permite enfocarse en los aspectos de niveles más altos del diseño de juegos sin ser sobrecargados por los detalles de nivel bajo. Estas operaciones básicas serán proporcionadas con una interfaz de programación justamente común, y el programador puede tener la confianza añadida de que sus motores de juego lograrán una mejor ejecución no sólo por los avances del CPU, pero también significativamente por la aceleración del hardware de este común conjunto de rutinas básicas de gráficos.
Sin embargo, estas rutinas de bajo nivel - ya sea que sean rutinas de ensamblador especializadas o de hardware - todavía no son lo suficientemente rápidas cuando se les da una grande escena compleja para dibujarla. Muy pronto, es muy probable que habrá tarjetas de gráficos capaces de representar hasta 100, 000 polígonos en un sálo segundo; sin embargo, para la animación esta razón de rapidez aún no es lo suficientemente alta. Para la animación suave, necesitamos lograr aproximadamente 30 marcos por segundos. Por nuestra estimación del funcionamiento previo, esto resulta en sólo un poco más de 3, 000 polígonos capaces de ser representados por marco. Las cuentas de polígonos para los mundos de juegos más nuevos empujan más allá de estos límites, y las demandas futuras están seguras de subir rápidamente. El problema se convierte muy obvio: en una estrategia ingenua de dibujo de escena, todos los polígonos de la escena son mandados a estas rutinas de bajo nivel a pesar del punto de vista actual. Inevitablemente, aún con escenas bastante pequeñas rápidamente somos limitados por la tasa de canalización de gráficos del procesamiento de estos polígonos. La solución es simplemente evitar mandar a la canalización esos polígonos que no podemos ver.
La idea de no dibujar las cosas que no podemos ver parece tan obvia. Así es que ¿porqué hablar de ella? La razón es que esta idea trae un concepto ligeramente diferente llamado visibilidad conservativa donde conservativamente estimamos el conjunto de polígonos visibles. La meta aquí es finalmente evitar mandar los polígonos a una canalización de gráficos potencialmente sobrecargada. Ya que puede ser muy caro determinar el conjunto exacto de polígonos que podemos ver, podemos sobreestimar ligeramente para reducir en gran parte la complejidad del problema y proporcionar una solución mucho más rápida. La técnica más simple y más común, llamada entresacado de la vista de pirámide (view-frustrum culling), involucra el descartar los polígonos que están fuera del campo-de-vista del observador.
En el entresacado de la vista de pirámide, deseamos formar un volumen de observación (o la vista de la pirámide) en la forma de una pirámide de cuatro lados extendiéndose infinitamente formada desde la cima de la posición del observador, con una ventana rectangular hacia el mundo (representando la ventana de la pantalla de despliegue) en la base (esto no es realmente un volumen o una pirámide en este contexto ya que no está acotado, pero la terminología todavía es usada ya que otra variaciones usaron volúmenes acotados). Antes de dibujar la escena completa para el marco actual, podemos probar cada polígono para ver si está adentro del campo-de-vista del observador y simplemente descartar esos que no están. Si los polígonos yacen afuera de la vista de la pirámide podemos removerlos o entresacarlos de la lista de polígonos que van a ser dibujados. Los polígonos que están dentro o parcialmente sobrepuestos en la pirámide tendrán que ser dibujados ya que ellos pueden ser potencialmente vistos por el observador. Esto explica porque le llamamos a esto algoritmo de visibilidad conservativa: los polígonos que son mandados al subsistema de gráficos pueden todavía ser invisibles al observador ya que pueden estar detrás de otros polígonos (por ejemplo, otro cuarto o el resto de un edificio detrás de una pared). Claramente, podemos evitar mandar muchos de los polígonos a las rutinas de bajo nivel más caras, pero ¿hasta que punto puede esta prueba de translape convertirse tan cara al grado de no ganar nada? Obviamente si todos los polígonos están en el campo-de-vista del obsevador, tendrán que ser examinados sin razón. Sin embargo, en las grandes escenas sumergidas que son típicamente de los mundos de juegos de 3D, mantenemos un alto promedio de tasa de entresacado. Sin embargo, esta prueba de translape no es trivial en términos de complejidad computacional, y el examinar cada polígono individualmente con frecuencia lleva a resultados aminorados, especialmente ya que cada polígono mandado a la canalización de gráficos que está fuera de la pirámide típicamente solo sufrirá una transformación de matriz para cada vértice y una operación de ser recortado (la etapa más cara es el rellenado del polígono, el remover la superficie escondida, y el sombreado, la cual es sólo ejecutada para los polígonos en la pirámide). Así es que ¿qué podemos hacer como una alternativa?
A menudo en los juegos de 3D y los programas de CAD, tenemos alguna estructura para el mundo que puede ser explotada por el sistema de entresacado de la vista de pirámide. Si podemos formar agrupamientos de polígonos que puedan ser entresacados juntos, podemos crear una prueba de translape mucho más eficiente. Imaginémonos poniendo un simple volumen acotado (una esfera o un cubo) alrededor de una colección de polígonos formando un solo objeto en la escena. Si simplemente examinamos el volumen acotado para ver si tiene traslapes con la observación de pirámide, podemos potencialmente entresacar trivialmente o aceptar el grupo entero de polígonos una sola prueba de traslape! Si (en el caso desafortunado), determinamos que el volumen esta parcialmente traslapado, debemos entonces retroceder a nuestras pruebas individuales previas de cada uno de los polígonos en el volumen acotado. Sin embargo, esto proporciona un método poderoso para hacer pruebas rápidamente que fácilmente pueden ser extendidas en una manera recursiva o jerárquica.
Previamente, tomamos colecciones de polígonos y los envolvimos con volúmenes acotados. El entresacado de la vista de pirámide empieza con primero examinar los volúmenes acotados simples del nivel más alto y luego examinar los polígonos individuales contenidos en los volúmenes que fueron determinados a ser parcialmente traslapados. Esto resulta en ahorros dramáticos, pero si hay un número grande de objetos en la escena, todavía puede ser prohibitivamente caro. Imaginémonos ahora agrupamientos de un nivel más alto formándose recursivamente formados al unir los agrupamientos de volúmenes acotados en volúmenes más grandes hasta que la escena completa es contenida en una estructura de árbol, con la raíz del volumen acotado que contiene la escena completa. El entresacado de la vista de pirámide puede ahora proceder primero a examinar la raíz del árbol. Si la raíz está completamente adentro o completamente afuera, podemos aceptar trivialmente o rechazar respectivamente todos los hijos. En el caso de un nodo de raíz parcialmente traslapado, debemos viajar hacia abajo a los hijos y examinar sus subárboles. Este proceso es repetido recursivamente hacia abajo hacia las hojas hasta que la prueba de traslape sea resuelta para todos los polígonos en la escena. Al principio esto parece como mucho más trabajo, pero los ahorros potenciales son ahora más altos ya que muchos polígonos pueden ser entresacados con sólo unas pocas pruebas de translapes. De hecho, inspeccionando solamente los volúmenes acotados que cruzan las fronteras de la vista de pirámide estos serán trasladados a las profundidades más hondas del árbol; en la práctica, esto mejora dramáticamente la realización del entresacado, especialmente para las escenas muy grandes con alta complejidad. Es muy común obtener tasas de 60% o más en promedio del entresacado. Sin embargo, esto todavía no hace nada para todos los polígonos en la vista de pirámide que no podemos ver; estos se mandan a la canalización de gráficos sólo para que se cubran por los polígonos ocultos. El entresacar estos polígonos requiere de un entendimiento de más profunda concepción.
Si la escena es estructurada de tal manera que el observador nunca ve la parte trasera del polígono, con seguridad podemos entresacar todos los polígonos los cuales su frente está en dirección opuesta al observador. Al principio, este tipo de estructura parece un tanto limitante, pero es muy común tener escenas compuestas de modelos sólidos, opacos y pegados como esas formadas por cuartos, pasillos y los marcos de las puertas. Estos ejemplos pueden ser fácilmente modelados para que el usuario sólo pueda ver la parte de enfrente de un polígono, y son bastante típicos en la mayoría de los juegos y diseños de CAD. Como un simple ejemplo, imaginémonos una esfera opaca enfrente del observador. Todos los polígonos que forman la esfera están claramente en la vista de pirámide así es que no serán entresacados con únicamente el método previo; sin embargo, todos los polígonos completamente en el hemisferio volteados hacia el lado opuesto del observador son efectivamente invisibles y pueden ser entresacados. Esta idea en verdad se extiende a todos los modelos sólidos pegados sin importar si son convexos o no (asumiendo que ellos no se autointersectan). ¿Cómo sabemos a que lado esta volteado el polígono? Cada polígono tiene una superficie normal (un vector perpendicular al plano del polígono) que apunta a la dirección de la cara de enfrente del polígono. Si el ángulo entre la superficie normal y el vector formado desde el observador al polígono es menor que 90 grados, entonces el polígono debe de estar volteando hacia atrás. Esta es una prueba muy simple que puede entresacar una gran porción de la escena que yace en la vista de pirámide. Usando la vista de pirámide y el entresacado de la cara trasera juntos, parece que tenemos en ello una muy poderosa y potencialmente efi ciente canalización de entresacado que grandemente reducirá la carga sobre el nivel más bajo del sistema de graficación. En efecto, esto forma la base del sistema clásico de entresacado que ha sido usado por muchos años; sin embargo, para las gráficas de juegos, esto aún no es suficiente.
En el sistema actual que combina la vista de pirámide y el entresacado de la cara trasera, a menudo realizamos un gran número de relativamente pruebas caras de cotas de volúmenes y traslapes de polígonos para el entresacado de la vista de pirámide y la cantidad de tiempo para realizar la prueba del polígono que está dando la cara trasera pudo aún ser bastante alta debido al potencialmente alto número de polígonos que aún yacen en la pirámide. ¿Existe una mejor manera? Sí, si podemos restringir nuestros modelos a favorablemente mundos de juegos 3D de inmersión o diseños CAD de gran escala arquitectónica que tengan cuartos o espacios separados por marcos de puertas o otras estructuras de conexión. Previamente, hicimos el entresacado de la vista de pirámide más eficiente por el agrupamiento de grupos de polígonos; podemos ahora agrupar por cuartos o celdas. Cada celda es separada por algún marco de puerta, o portal, y de cualquier celda en particular, otras celdas son solamente visibles a través de una secuencia de portales. Mientras esto puede parecer sobre restrictivo, imaginémonos las escenas en cualquier máquina de juego sofisticada o en el diseño arquitectónico; ellos a menudo caen naturalmente en los marcos de celdas y portales. Esta estructura permite una increíblemente eficiente estrategia de entresacado que puede ser usada con o sin los métodos previos descritos. El enfoque básico es muy simple. Primero encontrar en cual celda está el observador. Entonces encontrar cual portal conduciendo a esa celda está en el campo-de-vista del observador (uso de la estrategia VFC). Recursivamente aplicamos los previos pasos para cada celda visible, pero restringimos la vista de campo del observador para realizar solo la prueba de traslape de portales contra el de pirámide for mado del observador a través de los portales. Finalmente, se representan todas las celdas visitadas. La recursión es necesaria ya que es posible ver un portal dejando un cuarto adyacente. Las pruebas de entresacado de la vista de pirámide pueden ser realizadas entre las pirámides de observador/portal entrando en una celda en particular y en los objetos dentro de esa celda. Cada celda puede tener una representación de volumen acotado jerárquico de los objetos contenidos. También, las pruebas del entresacado de la cara trasera pueden ser aplicadas a los polígonos visibles a través de las pirámides de observador/portal.
Satisfacer los requerimientos en aumento para los juegos de 3D de hoy en día requiere técnicas sofisticadas para reducir la carga sobre la graficación de bajo nivel de las canalizaciones; de una manera ingenua enviando todos los polígonos a estas rutinas potencialmente caras simplemente no es suficiente. En respuesta, hemos presentado un sistema que no sólo encuentra estas demandas, sino que también proporciona un marco general simple, fácilmente expandible, y portátil que puede grandemente reducir la carga sobre cualquier graficación de tipo canalización. Al combinar estos algoritmos relativamente simples, podemos lograr un sistema que dramáticamente reduce la carga sobre el subsistema gráfico. Hemos mostrado la aplicabilidad del sistema a sistemas de presentación basado en polígonos pero este también es generalmente aplicable a escenas conteniendo primitivas arbitrarias tales como las superficies curvas, cónicas, etc. El sistema puede no obstante ser usado como una etapa de entresacado antes de aplicar esquemas de presentación realística de alta calidad, imagen fija tales como los métodos basados en el seguimiento de rayos o radiosidad.