¿Usar BSP en Doom es realmente un movimiento ingenioso?

El pináculo de la tecnología de la época.

En 1993, id Software lanzó Doom , un juego de disparos en primera persona que rápidamente se convirtió en un fenómeno. Hoy se cree que este es uno de los juegos que más impacto ha tenido en la historia.

Diez años después del lanzamiento de Doom , en 2003, el periodista David Kouchner publicó un libro de id Software llamado Masters of Doom , que desde entonces se ha convertido en una descripción canónica del proceso de creación de Doom . Hace unos años leí Masters of Doom y no recuerdo casi nada, pero una historia de un libro sobre el programador principal John Carmack se ha conservado en mi memoria. Mi descripción no será del todo precisa (ver más abajo para más detalles), pero en resumen, en la etapa inicial del desarrollo de Doom , Carmack se dio cuenta de que el renderizador 3D que escribió para el juego comenzó a disminuir cuando se renderizaban ciertos niveles. Esto era inaceptable, porque Doom tuvo que convertirse en un juego activo e incluso frenético. Al darse cuenta de que el problema del renderizador era tan fundamental que tendría que buscar un algoritmo de renderizado más óptimo, Carmack comenzó a leer artículos de investigación. Como resultado, implementó una técnica llamada partición de espacio binario (BSP), que nunca antes se había utilizado en videojuegos, y por lo tanto aceleró significativamente el motor Doom .

Esta historia de cómo Carmack aplicó la investigación científica de vanguardia a los videojuegos siempre me ha impresionado. En mi opinión, fue gracias a esto que Carmack se convirtió en una figura tan legendaria. Merece ser conocido como un brillante programador arquetípico de videojuegos por muchas razones, pero como el principal, siempre recuerdo el episodio con la lectura de artículos científicos y la partición binaria del espacio.

Obviamente, esta historia es impresionante, porque el término "partición binaria del espacio" parece ser algo complicado no solo para la implementación, sino incluso para la comprensión. Durante mucho tiempo supuse que Carmack dio un salto intelectual hacia adelante, pero como no sabía qué es una partición binaria del espacio y qué tan nueva era esta técnica cuando Carmack decidió usarla, no estaba completamente seguro. ¿Qué tan ingeniosa fue la adición de una partición de espacio binario a Doom en una escala de Homer Simpson a Albert Einstein?

También me preguntaba de dónde venía el BSP y cómo llegó la idea a Carmack. Por lo tanto, esta publicación estará dedicada no solo a John Carmack y Doom , sino también a la historia de la estructura de datos del "árbol de partición de espacio binario" (o árbol BSP). Resultó que el árbol BSP, como muchos otros aspectos de las ciencias computacionales, se origina en la investigación realizada para los militares.

Sí, es cierto: E1M1, el primer nivel de Doom , apareció gracias a la Fuerza Aérea de EE. UU.

Tarea VSD

El árbol BSP es una solución a una de las tareas más difíciles en gráficos por computadora. Para representar una escena tridimensional, el renderizador debe determinar qué es visible y qué no es visible desde el punto actual. Esto no es particularmente difícil si tienes mucho tiempo, pero un motor de juego en tiempo real que se respete a sí mismo debería determinar las partes visibles e invisibles del mundo al menos 30 veces por segundo.

Esta tarea a menudo se denomina tarea de determinación de superficie visible (VSD). El programador Michael Abrash, que trabajó con Carmack en Quake (el próximo juego de software de identificación después de Doom ), escribió sobre la tarea VSD en su famoso libro Graphics Programming Black Book :

Quiero hablar sobre la tarea de gráficos 3D más difícil, en mi opinión: determinar las superficies visibles (dibujando la superficie deseada en cada píxel) y su pariente cercano: la tarea de eliminación (lo más rápido posible para lanzar polígonos invisibles para acelerar la determinación de las superficies visibles). En aras de la brevedad, denotaré por la abreviatura VSD tanto la definición de superficies visibles como el recorte.

¿Por qué considero VSD la tarea 3D más difícil? Aunque los problemas de rasterización, como el mapeo de texturas, también son tareas sorprendentes e importantes, estas son tareas de una escala bastante finita, cuya solución se desplaza a la aparición de aceleradores 3D en el equipo; Además, solo se escalan cuando aumenta la resolución de la pantalla, lo que es bastante soportable.

En contraste, VSD es una tarea ilimitada, y ahora se utilizan docenas de soluciones para resolverlo. Aún más importante, el rendimiento ingenuo de VSD se escala directamente con la complejidad de la escena, que generalmente aumenta como una función cuadrada o cúbica, por lo que rápidamente se convierte en el factor limitante para representar mundos realistas.

Abrash escribió sobre la complejidad del problema de VSD a finales de los 90, unos años después de que Doom demostrara que la gente común quiere poder jugar juegos gráficamente pesados ​​en las computadoras de su hogar. A principios de los años 90, cuando id Software recién comenzaba a publicar juegos, tenían que trabajar de manera efectiva en computadoras inapropiadas: las máquinas domésticas fueron diseñadas para trabajar con texto, hojas de cálculo y otras aplicaciones similares. Para lograr este objetivo, la compañía tuvo que abordar la ficción, especialmente en el caso de varios juegos 3D publicados por id Software antes de Doom . En estos juegos, el diseño de todos los niveles estaba limitado de manera que simplificara la solución del problema VSD.

Por ejemplo, en Wolfenstein 3D , el juego que id Software lanzó justo antes de Doom , cada nivel consistía en paredes alineadas a lo largo de los ejes. En otras palabras, en el universo Wolfenstein podría haber muros norte / sur o muros este / oeste, y no otros. Además, los muros se pueden colocar a distancias fijas en la cuadrícula: todos los corredores tienen un ancho de una celda de la cuadrícula, o dos, etc., pero nunca 2.5 celdas. Aunque significaba que el equipo de id Software podía crear niveles que se veían casi iguales, esta restricción facilitó a Carmack escribir un procesador para Wolfenstein .

El procesador de Wolfenstein resolvió el problema de VSD moviendo rayos (marcha de rayos) al mundo virtual desde la pantalla. Por lo general, los renderizadores renderizados por rayos son renderizadores de emisión de rayos: a menudo son lentos porque resolver el problema VSD en raycaster requiere encontrar la primera intersección entre el rayo y algún objeto en el mundo, lo que requiere muchos cálculos. Pero como todas las paredes en Wolfenstein están alineadas con una cuadrícula, los únicos lugares donde una viga puede cruzar la pared serán las líneas de la cuadrícula. Por lo tanto, es suficiente que el renderizador verifique cada uno de estos puntos de intersección. Si el renderizador comienza verificando el punto de intersección más cercano al punto de vista del jugador, luego verifica el segundo en proximidad, y así sucesivamente, y termina cuando encuentra el primer muro, entonces el problema VSD se resuelve de la manera más trivial. El rayo simplemente se movió hacia adelante desde cada píxel hasta que se topó con algo, lo cual es muy económico en términos de velocidades de reloj del procesador. Y como todas las paredes tienen la misma altura, es suficiente para que emitamos rayos para cada columna de píxeles.

Esta simplificación del renderizado hizo que Wolfenstein fuera lo suficientemente rápido como para trabajar en PC domésticas débiles de la época cuando no había tarjetas gráficas especializadas. Pero ese enfoque no funcionaría en Doom , porque el equipo de identificación decidió que en su nuevo juego habría elementos tan nuevos como paredes diagonales, escaleras y techos con diferentes alturas. La marcha de rayos ya no era adecuada, por lo que Carmack escribió un tipo diferente de renderizador. El renderizador Wolfenstein , donde se usaba el haz para cada columna de píxeles, fue rechazado de la imagen, y se suponía que el renderizador Doom era rechazado de los objetos. Esto significaba que en lugar de atravesar los píxeles de la pantalla y determinar su color, el renderizador de Doom tenía que iterar sobre los objetos en la escena y proyectar cada uno de ellos en la pantalla.

En tal procesador, una forma simple de resolver el problema de VSD es usar un z-buffer. Cada vez que proyectamos un objeto en la pantalla, se realiza una verificación para cada píxel que queremos dibujar. Si la parte del objeto a dibujar está más cerca del jugador que el objeto ya dibujado en el píxel, entonces podemos reescribir su información. De lo contrario, debe dejar el píxel sin cambios. Este enfoque es simple, pero el z-buffer requiere mucha memoria, y el procesador aún puede gastar un montón de relojes de procesador en proyectar geometría de nivel que el jugador no verá.

A principios de la década de 1990, la solución z-buffer tenía un inconveniente más: en las PC compatibles con IBM que usaban un sistema de adaptador de video llamado VGA, escribir en el buffer de cuadro de salida era una operación costosa. Por lo tanto, el tiempo dedicado a renderizar píxeles, que luego simplemente se sobrescribirá, redujo en gran medida el rendimiento del renderizador.

Dado que escribir en el búfer de cuadros era muy costoso, el renderizador ideal era comenzar dibujando los objetos más cercanos al jugador, luego los objetos inmediatamente detrás de ellos, y así sucesivamente, hasta completar la escritura en cada píxel de la pantalla. En esta etapa, el renderizador debería haber entendido que era hora de detenerse, ahorrando así todo el tiempo que podía pasar explorando objetos distantes que el jugador no veía. Pero ordenar objetos de escena de esta manera, desde el más cercano al más lejano, equivale a resolver el problema VSD. La pregunta nuevamente surge ante nosotros: ¿qué puede ver un jugador?


Al principio, Carmack intentó resolver este problema confiando en el esquema de nivel de Doom . Su renderizador comenzó dibujando las paredes de la habitación en la que se encuentra el jugador, y luego se vertió en las habitaciones vecinas para dibujar paredes en estas habitaciones, que podrían ser visibles desde la habitación actual. Si cada habitación fuera convexa, esto resolvería el problema de VSD. Las salas no convexas podrían dividirse en "sectores" convexos. Puede ver cómo esta técnica de representación podría haber parecido una fuerte desaceleración en el video que se muestra arriba , donde un usuario de YouTuber con el apodo Bisqwit demuestra su propio renderizador que funciona de acuerdo con el mismo algoritmo general. Este algoritmo se utilizó con éxito en el juego Duke Nukem 3D, lanzado tres años después de Doom , cuando los procesadores se volvieron más potentes. Pero en 1993, en ese momento, el renderizador de Doom que usaba este algoritmo experimentó problemas con niveles complejos. Esto era especialmente obvio cuando los sectores se integraban entre sí, y esta era la única forma de crear, por ejemplo, escaleras circulares. Las escaleras circulares requerían múltiples descensos recursivos al sector ya dibujado, reduciendo drásticamente la velocidad del motor.

Casi al mismo tiempo, cuando el equipo de identificación se dio cuenta de que el motor de Doom podría ser demasiado lento, se le pidió a id Software que transfiriera Wolfenstein 3D a Super Nintendo. SNES era incluso menos potente que las PC compatibles con IBM de la época, y resultó que el renderizador Wolfenstein con tecnología de marcha de rayos, a pesar de su simplicidad, no funcionaba en equipos Super Nintendo con suficiente velocidad. Por lo tanto, Carmack comenzó a buscar un algoritmo mejor. De hecho, fue para el puerto de Super Nintendo de Wolfenstein que Carmack primero exploró e implementó la partición de espacio binario. En Wolfenstein fue bastante simple porque todas las paredes eran paralelas a los ejes; Doom lo hace más difícil. Pero Carmack se dio cuenta de que los árboles BSP también resolverían problemas de velocidad en Doom .

División de espacio binario

La partición del espacio binario simplifica la solución al problema VSD al dividir previamente la escena 3D. Por ahora, es suficiente que comprenda por qué la partición es útil: si dibuja una línea (que en realidad es un plano en 3D) a través de toda la escena, sabiendo con qué lado de la línea está el reproductor o la cámara, entonces también sabremos que no hay nada el otro lado de la línea no podrá obstruir objetos desde el lado de la línea donde se encuentra la cámara. Si repite el proceso muchas veces, obtenemos una escena 3D, dividida en muchas secciones. Esto no será una mejora con respecto a la escena original, excepto que ahora sabemos más sobre cómo pueden superponerse diferentes partes de la escena.

Los primeros en escribir sobre esta división de la escena 3D fueron los investigadores que intentaron averiguar para la Fuerza Aérea de los EE. UU. Si los gráficos por computadora son lo suficientemente progresivos para su uso en simuladores de vuelo. Publicaron sus hallazgos en un informe de 1969 titulado "Investigación sobre el uso de imágenes generadas por computadora en la simulación visual". El informe concluyó que los gráficos por computadora se pueden usar para entrenar a los pilotos; Al mismo tiempo, los investigadores advirtieron que la implementación del sistema sería complicada por la tarea de VSD:

Una de las tareas más importantes que deberá resolverse al calcular imágenes en tiempo real es la tarea prioritaria o las líneas ocultas. En nuestra percepción visual cotidiana del mundo que nos rodea, la naturaleza misma resuelve este problema con sencillez trivial; La punta de un objeto opaco se superpone a todos los demás puntos que se encuentran a lo largo de la misma línea de visión y están más lejos. En el caso de una computadora, esta tarea es muy difícil. La cantidad de cómputo necesaria para determinar la prioridad, en el caso general, crece exponencialmente con la creciente complejidad del entorno, y pronto excede la carga computacional asociada con la búsqueda de imágenes de objetos teniendo en cuenta la perspectiva.

Una solución mencionada por estos investigadores, que según dijeron fue utilizada previamente en un proyecto de la NASA, se basa en crear lo que llamaré la "matriz de superposición". Los investigadores señalan que un avión que divide una escena en dos partes puede usarse para resolver "cualquier conflicto de prioridades" entre objetos en lados opuestos del avión. En el caso general, es posible que deba agregar estos planos a la escena explícitamente, pero para una determinada estructura geométrica, puede confiar en las caras existentes de los objetos. Los investigadores demuestran el siguiente ejemplo, donde p1 , p2 y p3 son superficies divisorias. Si el punto de vista de la cámara está en el lado frontal o "verdadero" de uno de estos planos, entonces pi es 1. La matriz muestra la relación entre los tres objetos dependiendo de los tres planos de separación y la ubicación del punto de vista de la cámara; si el objeto ai se superpone al objeto aj , entonces El elemento aij de la matriz será igual a 1.


Los investigadores han propuesto implementar esta matriz en hardware y volver a calcularla en cada marco. De hecho, la matriz debe actuar como un interruptor grande o una especie de búfer z integrado. Al renderizar el objeto actual, el video no se emite para partes del objeto cuando 1 está en la columna del objeto, pero se dibuja el objeto de fila correspondiente.

Un inconveniente grave de este enfoque es que ^se necesita una matriz de tamaño n ² para describir una escena con n objetos. Por lo tanto, los investigadores decidieron verificar si es posible presentar la matriz de superposición en forma de una "lista de prioridades", que tendrá un tamaño de solo n y especificar el orden en que deben dibujarse los objetos. Inmediatamente notaron que en ciertas escenas, por ejemplo, en la que se muestra arriba, es imposible completar el pedido (ya que hay un ciclo de superposición), por lo que dedicaron mucho tiempo a la definición matemática de escenas "correctas" e "incorrectas". Al final, llegaron a la conclusión de que al menos para las escenas "correctas" (y el diseñador de la escena puede evitar fácilmente los casos "incorrectos"), se puede generar una lista de prioridades. Pero dejaron la generación de la lista como un ejercicio para el lector. Parece que la principal contribución de este trabajo de 1969 es indicar que, al menos en teoría, debería existir la posibilidad de utilizar planos divisorios para organizar los objetos en la escena.

Y solo en un artículo de 1980 titulado “Sobre la generación de superficies visibles por estructuras de árbol a priori” se demostró un algoritmo específico para esto. En este artículo, escrito por Henry Fuchs, Zvi Kedem y Bruce Naylor, se describió por primera vez el árbol BSP. Los autores dicen que su nueva estructura de datos es "una solución, un enfoque alternativo, utilizado por primera vez hace diez años, pero debido a algunas dificultades no tan generalizadas", por lo que responden a la decisión elegida en el trabajo de la Fuerza Aérea de los Estados Unidos en 1969. Después de construir un árbol BSP, puede usarse fácilmente para organizar objetos con prioridad en la escena.

Fuchs, Kedem y Naylor proporcionaron una descripción bastante clara del funcionamiento del árbol BSP, pero intentaré dar una descripción menos formal, pero breve.

Comenzamos seleccionando un polígono en la escena, y hacemos que el plano en el que se encuentra el polígono sea un plano divisorio. Este único polígono también se convierte en el nodo raíz del árbol. Los polígonos restantes de la escena estarán en uno u otro lado del plano divisorio de la raíz. Los polígonos en el lado "frontal" o en el medio espacio "frontal" del plano aparecen en el subárbol izquierdo del nodo raíz, y los polígonos en el lado "posterior" o en el medio espacio "posterior" del plano aparecen en el subárbol derecho. Luego repetimos este proceso de forma recursiva, seleccionando polígonos de los subárboles izquierdo y derecho como las nuevas superficies divisorias para sus propios medios espacios, que generan más semiespacios y subárboles. El proceso finaliza cuando finalizan los polígonos.

Digamos que queremos renderizar la geometría de la escena de atrás hacia adelante.(Esto se llama el "algoritmo del artista" porque significa que los polígonos más alejados de la cámara se rellenarán con polígonos más cercanos a la cámara, creando la representación correcta). Para hacer esto, solo tenemos que rodear nuestro árbol BSP en orden; la decisión sobre si se debe dibujar el subárbol izquierdo o derecho se basa en el lugar donde se encuentra el punto de vista de la cámara, en el medio espacio frontal o posterior en relación con el plano divisorio asociado con este nodo. Es decir, en cada nodo del árbol, primero representamos todos los polígonos en el lado "lejano" del plano, luego el polígono en el plano de separación y luego los polígonos en el lado "cercano" del plano. Los polígonos "cercano" y "lejano" se definen en relación con el punto de vista de la cámara. Esto resuelve el problema de VSD porque, como aprendimos hace unos párrafos,los polígonos en el lado lejano del plano de separación no pueden solaparse con nada en el lado frontal.

El siguiente diagrama muestra la construcción y el recorrido de un árbol BSP que describe una escena 2D simple. En 2D, se usan líneas divisorias en lugar de dividir planos, pero la idea básica sigue siendo la misma.




Una característica muy conveniente del árbol BSP que Fuchs, Kedem y Naylor enfatizan varias veces es que solo debe construirse una vez. Esto parece sorprendente, pero se puede usar un árbol BSP para renderizar la escena independientemente del punto de vista de la cámara. El árbol BSP permanece en uso hasta que se mueven los polígonos de la escena. Es por eso que el árbol BSP es tan útil para la representación en tiempo real: todo el trabajo complejo de construir un árbol se puede hacer por adelantado, y no en el momento de la representación.

Fuchs, Kedem y Naylor informan que la investigación adicional requiere la creación de un "buen" árbol BSP. La calidad del árbol BSP depende de los polígonos que elija para definir los planos de separación. Anteriormente, omití este punto, pero si usa un plano que se cruza con otros polígonos cuando se divide, entonces para que el algoritmo BSP funcione, debe dividir los polígonos cruzados en dos, de modo que una mitad pertenezca a un medio espacio y la otra al otro. Si esto sucede con frecuencia, entonces construir un árbol BSP aumenta significativamente el número de polígonos en la escena.

Bruce Naylor, uno de los autores de un artículo de 1980, escribió más tarde sobre este tema en su artículo de 1993 Construyendo buenos árboles de partición. Según el colega de Carmack y cofundador de id Software, John Romero, este artículo fue uno de los trabajos que Carmack leyó cuando intentó implementar árboles BSP en Doom .

Árboles BSP en Doom

Recuerde que en el primer borrador del renderizador de Doom , Carmack intentó establecer el orden de renderizado para la geometría de nivel llenando el renderizador de la sala donde el jugador está en las habitaciones vecinas. Los árboles BSP eran una forma más conveniente de determinar este orden, ya que evitaban el problema de que el procesador tuviera que visitar repetidamente una habitación (o sector), desperdiciando los ciclos del procesador.

"Agregar árboles BSP a Doom " en la práctica significaba agregar un generador de árboles BSP al editor de niveles de Doom . Después de completar la creación del nivel DoomSe generó un árbol BSP a partir de la geometría de nivel. Según Fabien Sanglar, el proceso de generación podría tomar hasta ocho segundos para un nivel y 11 minutos para todos los niveles del primer Doom . El proceso de generación fue tan largo en parte debido al hecho de que el algoritmo de generación Carmack BSP está tratando de encontrar un "buen" árbol BSP utilizando diversas heurísticas. Un retraso de ocho segundos sería imperdonable durante el juego, pero después de la generación preliminar parecía bastante aceptable, dado el aumento en el rendimiento que los árboles BSP proporcionaron al renderizador. El árbol BSP generado de un nivel individual se guardó como parte de los datos de nivel cargados en el juego cuando se lanzó.

Carmack realizó un cambio importante en el algoritmo del árbol BSP descrito en un artículo de 1980: después del lanzamiento de Doomy al leer el árbol BSP de nivel actual en la memoria, el renderizador usa este árbol para dibujar objetos no de adelante hacia atrás, sino de adelante hacia atrás. En un artículo de 1980, Fuchs, Kedem y Naylor demostraron cómo se puede utilizar un árbol BSP para implementar el algoritmo de un artista con renderizado continuo, pero se produce una gran cantidad de repintado en el algoritmo del artista, lo que podría ser costoso en las PC compatibles con IBM. Por lo tanto, el renderizador de Doom comienza con una geometría más cercana al jugador, y luego dibuja el más alejado. Tal orden inverso es fácil de implementar usando un árbol BSP, porque simplemente puede tomar una decisión de seguimiento en cada nodo del árbol. Para evitar que la geometría más lejana se dibuje encima del cerrador, el renderizador de Doomusa un tipo de z-buffer implícito, que proporciona muchos de los beneficios de un z-buffer regular, mientras consume mucha menos memoria. Hay una matriz que rastrea la superposición en la dimensión horizontal y otras dos matrices que rastrean la superposición en la dirección vertical arriba y debajo de la pantalla. El renderizador de Doom podría funcionar sin usar un verdadero z-buffer, porque Doom , estrictamente hablando, no era un juego completamente tridimensional. Las estructuras de datos menos costosas funcionaron porque ciertos elementos no eran posibles en Doom : la matriz de superposición horizontal funcionaba porque no había paredes inclinadas, y las matrices de superposición vertical funcionaban porque no había paredes en las que, por ejemplo, había dos ubicadas uno encima de las otras ventanas.


Doom II , tan complejo como su predecesor.


Pero nadie se quejó de la repetición de la sangre.


Una nueva palabra en Quake Technologies La

única tarea difícil que queda es cómo integrar los personajes Doom en movimiento en la geometría estática de los niveles dibujados usando el árbol BSP. Los enemigos en Doom no podían ser parte del árbol BSP porque se estaban moviendo; El árbol BSP solo funciona con geometría fija. Por lo tanto, el renderizador de Doomprimero dibuja la geometría estática del nivel, rastreando (usando otra estructura de datos eficiente en memoria) los segmentos de la pantalla en la que se realizó el dibujo. Luego, atrae a los enemigos de atrás hacia adelante y los trunca a lo largo de los segmentos de la pantalla que los superponen. Este proceso no es tan óptimo como el renderizado con un árbol BSP, pero dado que generalmente hay menos enemigos que la geometría, la velocidad no es un problema aquí.

Usar árboles BSP en Doom fue una gran victoria. Obviamente, Carmack fue lo suficientemente ingenioso como para darse cuenta de que los árboles BSP serían la solución ideal. ¿Pero fue esta decisión ingeniosa ?

En su excelente libro sobre el motor del juego DoomFabien Sanglar cita a John Romero, quien dijo que el artículo de Bruce Naylor "Construyendo buenos árboles de partición" se refería principalmente al uso de árboles BSP para recortar las caras posteriores de los modelos 3D. Según Romero, Carmack pensó que el algoritmo podría seguir siendo útil para Doom , por lo que lo implementó. Esto es bastante recomendable para Carmack porque implica que vio la utilidad de los árboles BSP en los videojuegos en tiempo real, incluso cuando otras personas todavía usaban esta técnica para representar escenas estáticas. La misma historia halagadora está en Masters of Doom: Kouchner sugirió que Carmack leyera el artículo de Naylor y se preguntó: "¿y si puede usar el árbol BSP para crear no solo una imagen 3D, sino un mundo virtual completo?"

Estos hallazgos ignoran la historia del árbol BSP. Cuando los investigadores de la Fuerza Aérea de los Estados Unidos se dieron cuenta por primera vez de que dividir una escena podría ayudar a acelerar el renderizado, estaban interesados en la aceleración en tiempo real del renderizado., porque al final intentaron crear un simulador de vuelo. El ejemplo del simulador de vuelo se menciona nuevamente en un artículo de 1980. Fuchs, Kedem y Naylor escriben que el árbol BSP puede ser útil en un simulador de vuelo que los pilotos usan para realizar múltiples aterrizajes en el mismo aeropuerto. Como la geometría del aeropuerto nunca cambia, un árbol BSP solo puede generarse una vez. Obviamente, estaban pensando en la simulación en tiempo real. En la introducción del artículo, incluso explican su investigación probando la posibilidad de usar un sistema gráfico en tiempo real para crear imágenes en no más de 1/30 de segundo.

Es decir, Carmack no fue el primero en pensar en usar árboles BSP en la simulación gráfica en tiempo real. Por supuesto, para predecir que los árboles BSP se pueden usar de esta manera, y para implementar esto, son cosas completamente diferentes. Pero incluso con la implementación, Carmack podría tener más información de fondo de lo que generalmente se piensa. El artículo de WSP sobre árboles BSP sugiere que Carmack se refirió al artículo de 1991 de Chen y Gordon, así como al libro de texto de 1990 Computer Graphics: Principles and Practice . Aunque esta declaración no está respaldada por una cita, puede ser cierta. Un artículo de 1991 de Chen y Gordon describe el renderizado de adelante hacia atrás usando árboles BSP, que es esencialmente la misma solución utilizada por Doom, hasta la estructura de datos "z-buffer implícito", que no permite dibujar polígonos distantes encima de los vecinos. El artículo proporciona una excelente visión general de los árboles BSP, así como un seudocódigo para construir y mostrar un árbol. (Gracias a la maravillosa biblioteca de mi universidad, pude ver la edición de 1990). El libro de texto Computer Graphics: Principles and Practice es un trabajo clásico sobre gráficos por computadora, por lo que Carmack también podría tener uno.


Nivel subsector E1M1: Hangar.

Sea como fuere, Carmack se enfrentó a una nueva tarea: "¿Cómo puedo crear un juego de disparos en primera persona que se ejecute en una computadora con un procesador que ni siquiera es capaz de realizar operaciones de punto flotante?", Realizó su propia investigación y demostró que los árboles BSP son Esta es una estructura de datos útil para videojuegos en tiempo real. Sigo pensando que este es un resultado impresionante, a pesar de que el árbol BSP fue inventado diez años antes, y ha sido estudiado teóricamente con suficiente detalle cuando Carmack leyó sobre él. Quizás el principal logro que debemos elogiar es el motor de Doom en su conjunto, que se ha convertido en un gran ejemplo de código. Ya he hablado sobre esto una vez, pero repito que el libro de Fabien Sanglar sobre el motor del juegoDoom ( Game Engine Black Book: DOOM ) es una excelente descripción de todos los componentes reflexivos del motor del juego y su interacción. No debemos olvidar que la tarea VSD fue solo una de las muchas tareas que Carmack tuvo que resolver para que el motor Doom funcionara . Y que fue capaz, además de todo, de leer sobre la compleja estructura de datos desconocida para la mayoría de los programadores e implementarla. Esto dice mucho sobre el nivel de su conocimiento técnico y compromiso con el ideal.