Terremoto interior: definición de superficies visibles

El veterano de la programación de gráficos tridimensionales Michael Abrash, usando el ejemplo del desarrollo del primer Quake, habla sobre la necesidad de un pensamiento creativo en la programación.

Hace muchos años, trabajé para la difunta compañía de adaptadores de video Video Seven. Allí ayudé a desarrollar un clon de VGA. Mi colega Tom Wilson, que trabajó durante muchos meses durante todo el día para desarrollar el chip Video Seven VGA, trató de hacer VGA lo más rápido posible y estaba seguro de que su rendimiento se optimizó casi al máximo. Sin embargo, cuando Tom ya estaba introduciendo los toques finales al diseño del chip, escuchamos rumores de que nuestro competidor Paradise había logrado un rendimiento aún mayor en su clon de desarrollo al agregar FIFO.

Este fue el final de los rumores: no sabíamos qué era FIFO, ni cuánto ayudó, nada más. Sin embargo, Tom, generalmente una persona amable y relajada, se convirtió en un fanático activo y obsesionado con demasiada cafeína en la sangre. Basado en estos fragmentos de información, trató de descubrir qué podía hacer Paradise. Al final, llegó a la conclusión de que Paradise probablemente insertó un búfer de escritura FIFO entre el bus del sistema y VGA, de modo que cuando la CPU estaba grabando en la memoria de video, los datos que se escribían irían inmediatamente a FIFO, y esto permitiría que la CPU continúe procesando en lugar de permanecer inactiva cada vez cuando estaba escribiendo en la memoria de la pantalla.

Tom no tenía elementos lógicos ni tiempo suficiente para implementar una FIFO completa, pero logró implementar FIFO con una sola profundidad de operación, lo que permitió que el procesador superara el chip VGA en una operación de escritura. Tom no estaba seguro de que esto daría buenos resultados, pero eso era lo único que podía hacer, por lo que implementó este sistema y transfirió el chip a producción.

Resultó que FIFO para una operación funciona increíblemente genial: en ese momento los chips Video Seven VGA eran los más rápidos del mercado; se convirtieron en evidencia del genio de Tom y evidencia de lo que el creador es capaz bajo la presión de las circunstancias. Sin embargo, lo mejor de esta historia es que el diseño Paradise FIFO no tuvo nada que ver con el diseño de Tom, y no funcionó en absoluto . Paradise insertó un búfer de lectura FIFO entre la memoria de la pantalla y la etapa de salida de video del chip VGA, lo que le permitió leer previamente la salida de video para que cuando la CPU necesitara acceder a la memoria de la pantalla, los píxeles pudieran tomarse de FIFO y el comando de la CPU se ejecutara instantáneamente. Esto realmente mejoró el rendimiento, pero no tanto como el búfer de escritura FIFO de Tom.

Y este caso puede considerarse una buena parábola sobre la naturaleza misma del proceso creativo que una persona puede lograr. Las noticias sobre el chip Paradise casi no contenían ninguna información objetiva, pero obligaron a Tom a ir más allá de los límites que él subconscientemente estableció, desarrollando el diseño inicial del chip. Creo que este es el elemento más importante de cualquier diseño ingenioso, ya sea en el campo del hardware, el software o cualquier otra esfera creativa, y fue él quien nació en las noticias de Tom sobre Paradise: la capacidad de detectar los límites que construiste en el proceso de trabajar en el proyecto y superarlos. fronteras

El problema, por supuesto, es cómo superar las fronteras, cuya existencia ni siquiera se conoce. No existe una fórmula para el éxito, pero dos principios pueden servir bien a este propósito: en primer lugar, simplificar, en segundo lugar, probar constantemente algo nuevo.

Por lo general, cuando siente que el código se está complicando, comienza a realizar cambios menores en la estructura congelada, y existe una alta probabilidad de que pueda aumentar la productividad y reducir la cantidad de código inventando nuevamente el diseño. Una estructura realmente buena debería brindar un momento de profunda satisfacción cuando todo encaja, y le sorprende lo pequeña que es la cantidad de código que se necesita y lo bien que funcionan todos los casos límite.

En el proceso de revisar la estructura, es importante estudiar cualquier idea que se le ocurra, sin importar cuán locas puedan parecer. Muchas de las ideas realmente grandiosas que escuché al principio parecían absurdas porque no encajaban en mi imagen actual del mundo. A menudo, estas ideas son realmente locas, pero al igual que las noticias de Paradise Chip estimularon la imaginación de Tom, la exploración agresiva de ideas aparentemente delirantes puede abrir nuevas posibilidades para usted.

Buena ilustración: la evolución del motor gráfico Quake 3D.

La tarea de gráficos 3D más compleja del mundo.

Pasé los últimos siete meses trabajando en Quake, el heredero de DOOM de id Software, y supongo que tres meses más tarde, cuando lea este artículo, Quake se lanzará como shareware.

En términos de gráficos, Quake será para DOOM lo que DOOM fue para su predecesor, Wolfenstein 3D. Quake agrega 3D arbitrario real (el jugador puede mirar hacia arriba y hacia abajo, inclinarse hacia los lados e incluso caer hacia un lado), luces y sombras detalladas, monstruos y personajes en 3D en lugar de sprites DOOM. Pronto hablaré de todo esto con más detalle, pero este mes quiero hablar sobre la tarea, que en mi libro llamo la más difícil en los gráficos tridimensionales: determinar las superficies visibles (dibujar la superficie correspondiente para cada píxel) y sobre una tarea muy cercana a ella, sobre recorte (lo más rápido posible descartando polígonos invisibles como una forma de acelerar la determinación de superficies visibles). En aras de la brevedad, utilizaré la abreviatura VSD para denotar la definición de determinación de superficie visible y eliminación.

¿Por qué considero VSD la tarea más difícil de los gráficos 3D? Aunque las tareas de rasterización, por ejemplo, el mapeo de texturas, son igual de sorprendentes e importantes, su alcance es bastante limitado y, después del advenimiento de los aceleradores 3D, su solución se transferirá al hardware; Además, su escala depende solo de la resolución de la pantalla, es decir, son bastante modestos.

Por el contrario, VSD es una tarea ilimitada y se están utilizando docenas de enfoques para resolverlo. Pero lo que es más importante, el rendimiento de VSD en una solución ingenua aumenta según la complejidad de la escena, que generalmente aumenta como una función cuadrática o cúbica, y por lo tanto se convierte rápidamente en el factor limitante para crear mundos realistas. Creo que en los próximos años, VSD se convertirá en un problema cada vez más dominante en los gráficos 3D en tiempo real para PC, porque los detalles de los mundos 3D aumentarán constantemente. Ya hoy, un nivel de tamaño sólido de Quake puede contener aproximadamente 10,000 polígonos, es decir, casi tres veces más que un nivel de DOOM comparable en tamaño.

Estructura de nivel de terremoto

Antes de profundizar en el VSD, permítanme mencionar que cada nivel de Quake se almacena como un gran árbol BSP tridimensional. Este árbol BSP, como cualquier otro BSP, divide el espacio, en este caso, a lo largo de los planos de los polígonos. Sin embargo, a diferencia del árbol BSP que demostré anteriormente, el árbol Quake BSP no almacena polígonos en los nodos del árbol como parte de los planos divisorios, sino en hojas vacías (sin llenar), como se muestra en la Figura 1 en la vista superior.


Figura 1. En Quake, los polígonos se almacenan en hojas vacías. Las áreas oscuras son hojas rellenas (volúmenes rellenos, como el interior de las paredes)

El orden correcto de renderizado se puede obtener renderizando las hojas en el orden BSP "de adelante hacia atrás" o "de atrás hacia adelante". Además, dado que las hojas BSP son siempre convexas, y los polígonos son los límites de las hojas BSP que miran hacia adentro, los polígonos de cualquier hoja nunca pueden superponerse y pueden dibujarse en cualquier orden. (Esta es una propiedad general de los poliedros convexos).

Recorte y definición de superficies visibles

Idealmente, el proceso VSD debería funcionar de la siguiente manera: primero, debe descartar todos los polígonos que están fuera de la pirámide de visibilidad, y también cortar todas las partes invisibles de los polígonos que son parcialmente visibles. Luego, debe dibujar solo los píxeles de cada polígono que son realmente visibles desde el punto de vista actual, como se muestra en la Figura 2 en la vista superior, sin perder el tiempo redibujando repetidamente los píxeles; observe cuántos polígonos en la Figura 2 necesita dibujar. Y, por último, en un mundo ideal, verificar la visibilidad de las partes de los polígonos debería ser económico, y el tiempo de procesamiento debería ser el mismo para todos los puntos de vista posibles, para que el juego funcione sin problemas.


Figura 2. La arquitectura VSD ideal representa solo las partes visibles de los polígonos visibles.

En el proceso de lograr esta tarea, es fácil determinar cuáles de los polígonos están completamente fuera del alcance de la pirámide de visibilidad o parcialmente cortados, y es completamente posible averiguar exactamente qué píxeles dibujar. Por desgracia, el mundo está lejos de ser ideal, y todas estas comprobaciones son costosas, por lo que el truco es acelerar u omitir diferentes comprobaciones, creando el resultado necesario.

Como expliqué en detalle en artículos anteriores, con un BSP, puede dar la vuelta al mundo de manera fácil y económica en orden frontal o posterior. La solución VSD más simple es simplemente atravesar el árbol de atrás hacia adelante, truncar cada polígono con una pirámide de visibilidad y dibujarlo si su cara se dirige a la cámara y no se corta por completo (algoritmo del artista). ¿Pero es esta una solución adecuada?

Para mundos relativamente simples, es bastante aplicable. Sin embargo, no escala bien. Uno de los problemas es que cuando se agregan nuevos polígonos al mundo para cortar polígonos invisibles, se requieren más y más transformaciones y controles; después de cierto umbral, esto comenzará a disminuir significativamente el rendimiento.

Afortunadamente, este problema en particular tiene una buena solución. Como se mencionó anteriormente, cada hoja en el árbol BSP describe un subespacio convexo, y los nodos conectados a la hoja limitan el espacio. Menos obvio es que cada nodo en el árbol BSP también describe un subespacio, un subespacio que consiste en todos los elementos secundarios del nodo, como se muestra en la Figura 3. Puede tomarlo de esta manera: cada nodo divide en dos partes el subespacio creado por los nodos ubicados arriba en árbol, y los elementos secundarios del nodo enmarcan aún más este subespacio en todas las hojas que provienen del nodo.


Figura 3: El nodo E describe un subespacio oscuro que contiene las hojas 5, 6, 7 y el nodo F.

Dado que el subespacio del nodo es acotado y convexo, podemos verificar si está completamente fuera de la pirámide de visibilidad. Si es así, todos los elementos secundarios del nodo definitivamente se cortarán por completo y se pueden descartar sin procesamiento adicional. Dado que la parte principal del mundo generalmente se encuentra fuera de la pirámide de visibilidad, muchos polígonos del mundo se pueden cortar casi sin costo por enormes fragmentos de subespacios de nodos. Realizar una verificación ideal para los subespacios de recorte es bastante costoso, por lo tanto, generalmente para cada nodo, se utilizan paralelogramos o esferas de restricción para las verificaciones de recorte.

Es decir, el recorte a lo largo de la pirámide de visibilidad no es un problema, y ​​puede usar BSP para retroceder. Entonces, ¿cuál es el problema?

Redibujando

El problema que enfrentó el autor principal de las tecnologías DOOM y Quake John Carmack al desarrollar Quake fue que en un mundo complejo, muchas escenas en la pirámide de visibilidad tienen una gran cantidad de polígonos. La mayoría de estos polígonos se superponen parcial o completamente con otros polígonos, pero el algoritmo del artista descrito anteriormente requiere dibujar cada píxel de cada polígono en la pirámide de visibilidad. Sin embargo, a menudo solo se vuelven a dibujar para que otros los vuelvan a dibujar. Con un nivel de terremoto de 10,000 polígonos, es fácil obtener el peor caso de volver a dibujar cuando los píxeles se dibujan 10 o más veces; es decir, en algunos cuadros, cada píxel en promedio se dibujará 10 o más veces. Ningún rasterizador es lo suficientemente rápido como para compensar el orden de magnitud necesario para representar una escena; peor aún, el algoritmo del artista crea grandes diferencias de rendimiento entre el mejor y el peor de los casos, lo que conduce a un cambio significativo en la velocidad de fotogramas al mover al espectador.

Entonces, John se enfrentó al problema de reducir la cantidad de redibujos a niveles aceptables. Idealmente, cada píxel debe dibujarse solo una vez, pero no más de dos o tres veces en el peor de los casos. En cuanto al recorte a través de la pirámide de visibilidad, idealmente se requería que todos los polígonos invisibles en la pirámide se cortaran casi sin costo adicional. Una ventaja también sería que sería posible dibujar solo las partes visibles de polígonos parcialmente visibles, pero al mismo tiempo se debería mantener un equilibrio: la operación debería gastar menos que volver a dibujar.

Cuando llegué a la identificación a principios de marzo, John ya tenía un prototipo del motor y un plan general, por lo que asumí que nuestro trabajo sería simplemente completar y optimizar este motor. Sin embargo, si supiera la historia de la identificación, podría descubrir qué es qué. John creó no solo DOOM, sino también motores para Wolf 3D y varios otros juegos anteriores, y durante el proceso de desarrollo realizó varias versiones diferentes de cada motor (una vez que creó cuatro motores en cuatro semanas), es decir, en cuatro años escribió alrededor de 20 motores . El deseo infatigable de John de obtener cada vez más tecnologías nuevas y de alta calidad del motor Quake terminará solo después del lanzamiento del juego.

Tres meses después de mi llegada, solo quedaba un elemento de la estructura VSD original en el motor, y el deseo de John de "probar cosas nuevas" llegó tan lejos que nunca antes había visto algo así.

Manojo de árboles

En el proyecto Quake original de John, el renderizado se realizó de adelante hacia atrás utilizando un segundo árbol BSP que rastrea las partes de la pantalla ya dibujadas y aún vacías que debían llenarse con los polígonos restantes. Lógicamente, este árbol BSP puede considerarse un área bidimensional que describe las partes llenas y vacías de la pantalla, como se muestra en la Figura 4, pero de hecho es un árbol tridimensional, conocido como el "árbol de vigas". Un árbol de vigas es un conjunto de sectores 3D (grupos) delimitados por planos proyectados desde algún punto central (en nuestro caso, el punto de vista), como se muestra en la Figura 5.


Figura 4. El árbol de vigas de Quake divide efectivamente la pantalla en un área 2D


Figura 5. El árbol de vigas Quake consiste en sectores 3D, o vigas, proyectadas desde el punto de vista a los bordes de los polígonos.

En el proyecto de John, un árbol de gavilla inicialmente consiste en una gavilla única que describe la pirámide de visibilidad; todo lo que está fuera de este paquete se considera lleno (es decir, no es necesario dibujar nada allí), y todo lo que está dentro del paquete se considera vacío. Al alcanzar un nuevo polígono dando la vuelta al árbol BSP del mundo de adelante hacia atrás, este polígono se transformó en una viga dibujando planos desde sus bordes a través del punto de vista, y todas las partes de la viga que cruzan vigas vacías en el árbol de vigas se consideraron dibujadas y agregadas al árbol de vigas como una viga llena. Esto continuó, hasta que los polígonos terminaron o hasta que el árbol de la gavilla se llenó por completo. Después de completar el árbol de vigas, se dibujaron las partes visibles de los polígonos atrapados en el árbol de vigas.

La ventaja de trabajar con un árbol de haz tridimensional en lugar de la región 2D fue que para determinar en qué lado del plano de haz está el vértice del polígono, es suficiente verificar el signo del producto vectorial del rayo hacia el vértice y lo normal al plano, porque todos los planos de haz pasan por el principio coordenadas (punto de vista). Además, dado que el plano del haz está completamente descrito por una sola normal, para generar un haz desde el borde del polígono, solo el producto escalar del borde y el haz desde este borde hasta el punto de vista es suficiente. Finalmente, para el recorte de grupo por la pirámide de visibilidad descrita anteriormente, se pueden usar las esferas delimitadoras de los nodos BSP.

Al principio, la propiedad del árbol de paquetes (que finaliza cuando el árbol de paquetes se llena) parecía atractiva porque parecía que limitaría el rendimiento en los peores casos. Desafortunadamente, todavía eran posibles las escenas en las que se podía ver todo hasta el cielo o la pared del fondo del mundo, por lo que en el peor de los casos, aún tenía que verificar todos los polígonos en la pirámide de visibilidad con respecto al árbol de racimos. También pueden ocurrir problemas similares con pequeñas grietas debido a limitaciones en la precisión numérica. Se pasa mucho tiempo recortando el árbol de vigas y, por ejemplo, en escenas con un alto rango de visibilidad, visto desde la parte superior del nivel, el costo total de procesamiento de las vigas redujo la velocidad de fotogramas de Quake a la velocidad de las tortugas. Es decir, al final resultó que la solución con los paquetes de árboles padece casi las mismas enfermedades que el algoritmo del artista: el peor de los casos es mucho peor que el caso promedio, y no se adapta bien con la creciente complejidad del nivel.

Nuevo motor 3D todos los días

Después de que el árbol de vigas comenzó a funcionar, John trabajó incansablemente para acelerar el motor 3D, tratando constantemente de mejorar su estructura, en lugar de hacer cambios en la implementación. , , : « , ...», , . , , , . , . , . . , , , FIFO- Paradise .

raycast: los rayos se emiten en una pantalla dividida en una cuadrícula de 8x8; Esta es una operación muy efectiva porque la primera intersección con la superficie se puede encontrar simplemente restringiendo el haz al árbol BSP, comenzando desde el punto de vista, hasta llegar a la hoja llena. Si los rayos vecinos no caen en la misma superficie, se emite un haz en el medio entre ellos, y esto continúa hasta que todos los rayos vecinos caen en una superficie o están en píxeles vecinos; entonces se dibuja un bloque alrededor de cada rayo del polígono en el que cayó el rayo. Este enfoque escala muy bien y está limitado por el número de píxeles, y no se vuelve a dibujar. Su problema se está cayendo: existe una alta probabilidad de que aparezcan pequeños polígonos entre los rayos y desaparezcan.

Superficies sin pico: El mundo se representa como un conjunto de planos de superficie. Los polígonos aparecen indirectamente en las intersecciones de los planos y se eliminan de los planos en la última etapa antes del renderizado. Esto proporciona un recorte rápido y una cantidad muy pequeña de datos (en comparación con los polígonos, los planos se describen de manera mucho más compacta), pero lleva mucho tiempo extraer los polígonos de los planos.

Draw buffer : z-, , , . , , , , . : , 256 0-8 ; x86 8 .

: Los polígonos se rasterizan en intervalos, que se agregan a la lista global de intervalos y se cortan de esta lista para que solo quede el intervalo más cercano en cada píxel. Se necesita un poco de clasificación yendo de adelante hacia atrás, porque si hay intersecciones, el intervalo que ya está en la lista está más cerca. Esto elimina la necesidad de volver a dibujar, pero a costa de los intervalos de cálculo aritméticos; Además, cada polígono debe convertirse a intervalos.

Portales: se rastrean agujeros en los que no hay polígonos en las superficies, porque el rango de visibilidad solo se puede expandir a través de dichos portales. El renderizado se realiza de adelante hacia atrás, y cuando se detecta un portal, los polígonos y portales detrás de él se limitan a sus límites hasta que no haya polígonos y portales visibles. Con la aplicación recursiva de este principio, le permite dibujar solo las partes visibles de los polígonos visibles, pero a costa de una cantidad significativa de recorte a través de los portales.

Avance

, — , , BSP- , BSP- . , DOOM (2D), BSP- DOOM 2D- . 3D , . BSP , , . , , BSP.

, , , - . BSP, , , . 3:30 , , , , , , , .

La complejidad estaba en tamaño: el conjunto inicialmente no comprimido de conjunto potencialmente visible (PVS) tomó varios megabytes. Sin embargo, PVS podría almacenarse como un vector de bits con 1 bit por hoja. Es muy fácil comprimir dicha estructura con una simple compresión de cero bytes. John también sugirió cambiar la heurística de BSP para que genere menos hojas. Esto fue lo opuesto a lo que propuse hace varios meses, a saber, la elección del próximo separador de polígonos, separando la menor cantidad de otros polígonos, y según los últimos datos, resultó ser la mejor heurística. El enfoque de John permitió limitar el espacio fuera del nivel para que el controlador BSP pudiera eliminar superficies externas que el jugador nunca vería,como resultado, reduciendo el tamaño de PVS para un nivel suficientemente grande a 20 kilobytes.

A cambio de estos 20 kilobytes, se acelera el recorte de las hojas fuera del alcance de la pirámide de visibilidad (porque solo se tienen en cuenta las hojas en el PVS), y para el recorte dentro de la pirámide de visibilidad, solo necesita un pequeño redibujo (el PVS para la hoja contiene todas las hojas visibles desde cualquier parte de la hoja, por lo tanto un pequeño redibujo, generalmente del orden del 50%, pero capaz de alcanzar hasta el 150%). Aún mejor, calcular previamente el PVS resulta en una ecualización del rendimiento; el peor de los casos ahora no es mucho peor que el mejor, porque ya no necesita procesamiento VSD adicional, solo más polígonos y quizás un poco de rediseño adicional en el caso de escenas complejas. Cuando John me mostró por primera vez su prototipo funcional, lancé especialmente la escena más difícil: el lugar donde la velocidad de fotogramas disminuyó a números de un solo dígito, y funcionó sin problemas,Sin desaceleraciones notables.

, PVS , , «» . , , , , , «» , .

-

¿Qué significa esto?Exactamente lo que dije al principio: simplificar y probar algo nuevo. Los PVS precalculados son más simples que cualquier otro esquema que revisamos anteriormente (aunque precalcular los PVS es una tarea interesante que discutiremos en otro momento). En esencia, los PVS precalculados son solo una versión limitada del algoritmo del artista durante la ejecución del programa. ¿Significa esto que este enfoque no es particularmente profundo?

En absolutoTodas las estructuras realmente excelentes parecen simples e incluso obvias, pero solo después de que se inventan. Pero el proceso de invención en sí mismo requiere una increíble perseverancia y disposición para probar muchas ideas diferentes hasta encontrar la correcta, como sucedió en este caso.

Mi amigo Chris Hecker tiene la teoría de que todos los enfoques finalmente se reducen a uno, porque todos reflejan el mismo estado interno y funcionalidad. Desde el punto de vista de las teorías subyacentes, esto es cierto: no importa cómo calcules el mapeo de texturas en perspectiva: usando cálculos hiperbólicos incrementales o de división, los números realizan la misma tarea. Sin embargo, cuando se trata de la implementación, se puede hacer una gran diferencia con un simple cambio de la solución en el tiempo o una mejora en la optimización de las capacidades de hardware o el almacenamiento en caché. A mi amigo Terje Mathisen le gusta repetir que "casi toda la programación puede verse como ejercicios de almacenamiento en caché"; eso es exactamente lo que hizo John. No importa cuán rápido haga sus cálculos de VSD, nunca serían tan rápidos como la precomputación y la búsqueda de visibilidad.Su movimiento más inteligente fue que se alejó de la mentalidad de "aceleración de código" y se dio cuenta de que, de hecho, puede calcular previamente (esencialmente caché) PVS y buscarlos.

Lo más difícil del mundo es alejarse de la solución habitual y bastante buena para un problema complejo e intentar encontrar otra solución mejor. Me parece que para esto es mejor probar nuevas ideas locas y siempre, siempre tratar de simplificar. Uno de los objetivos de John era tener menos código en cada juego 3D posterior que en el anterior; creía que si aprende más, podrá resolver problemas de manera más eficiente en una cantidad menor de código.

Y aunque este sistema está funcionando bastante bien para él.

Aprende ahora, paga por adelantado

Hay una cosa más que me gustaría mencionar al final del artículo. ¿Cuánto recuerdo, Dr. El Dobb's Journal siempre ha dicho que compartir información de programación es una bendición. Conozco a muchos programadores que dieron un salto en su desarrollo gracias a Tiny C Hendrix o D-Flat Stevens, o simplemente por leer la carpeta anual de DDJ . (Entre ellos, por ejemplo, lo estoy). Muchas compañías consideran el intercambio de información de una manera completamente diferente, como una posible pérdida de ganancias, y esto es lo que hace que DDJ sea tan valioso para la comunidad de programadores.

Gracias a esta filosofía, id Software me permitió decir en este artículo cómo funciona Quake incluso antes de su lanzamiento. Y es por eso que id publicó el código fuente completo de Wolfenstein 3D en ftp.idsoftware.com/idstuff/source [aprox. traducción: ahora los códigos fuente se presentan en github ] ; no puedes simplemente recompilar el código y venderlo, sino que puedes descubrir cómo funciona un juego exitoso a gran escala; examine el archivo wolfsrc.txt del directorio anterior para obtener detalles sobre cómo se puede usar el código.

Por lo tanto, recuerde: cuando es legal, a la larga, el intercambio de información nos beneficia a todos. Puede pagar la deuda por adelantado por la información recibida aquí y en otros lugares, compartiendo todo lo que pueda escribiendo un artículo o un libro, o publicando conocimientos en la Web. Ninguno de nosotros aprende en el vacío; Todos estamos sobre los hombros de gigantes: Wirth, Knut y miles de otros. ¡Sustituye tus hombros para construir el futuro!

Referencias

Foley, James D., et al. , Computer Graphics: Principles and Practice , Addison Wesley, 1990, ISBN 0-201-12110-7 (, BSP-, VSD).

Teller, Seth, Visibility Computations in Densely Occluded Polyhedral Environments (), http://theory.lcs.mit.edu/~seth/ .

Teller, Seth, Visibility Preprocessing for Interactive Walkthroughs , SIGGRAPH 91 proceedings, pp. 61-69.