Terremoto interno: siempre considere alternativas

El programador Michael Abrash, quien fue invitado por John Carmack para trabajar en el motor del primer Quake a mediados de los 90, escribió una serie de artículos durante el proceso de desarrollo. Esta es la segunda columna de esta serie. La traducción del primero está aquí .

Debo admitir: me cansé del rock clásico. La última vez que estuve feliz de escuchar algo de Cars o Boston hace mucho tiempo, hace unos 20 años. Además, nunca me sentí particularmente atraído por Bob Seager y Queen, por no mencionar a Elvis, tan poco ha cambiado. Pero me di cuenta de que algo cambió cuando quise cambiar la radio cuando escuché a Allman Brothers, o Steely Dan, o Pink Floyd, o, Dios, perdóname, los Beatles (pero solo en cosas como "Hola adiós" y "Voy a En cambio, llora, no Ticket to Ride o A Day in the Life; todavía no he llegado tan lejos). No tardó mucho en encontrar las razones para esto; Escuché las mismas canciones durante un cuarto de siglo y me cansé de ellas.

Lo cuento todo esto porque cuando mi hija y yo salimos del café una noche, la estación de radio "No hay alternativa" se encendió por primera vez en el automóvil.

Estamos hablando de una niña de diez años que creció con una dieta constante de viejos éxitos. Le gustan las melodías, las canciones pegadizas y los buenos cantantes. No encontrará nada de esto cuando escuche una estación de rock alternativa. Por lo tanto, no es sorprendente que cuando encendí la radio, ella dijo primero: "¡Fu!"

Pero esto es lo que me sorprendió: después de escuchar por un tiempo, ella dijo: "Sabes, papá, pero eso es realmente interesante".

Esto no solo me insinuó sobre qué tipo de música sonaría en la casa cuando se convirtiera en una adolescente. Su rápida adopción del rock alternativo (en comparación con mi fascinación por la música de mi propia juventud durante diez años) me recordó algo que se olvida fácilmente cuando envejeces y el estilo de vida se establece. Esto me recordó que era necesario mantener una mente abierta y estar preparado, además, esforzarse, para probar cosas nuevas. Los programadores tienden a apegarse a enfoques familiares y son propensos a usarlos si hacen frente adecuadamente a las tareas. Pero siempre hay alternativas a la programación, y creo que a menudo vale la pena explorarlas.

Pero dada la naturaleza siempre cambiante de Quake , realmente no debería necesitar ese recordatorio.

Flujo creativo

En enero, describí una secuencia creativa que llevó a John Carmack a decidir utilizar polígonos de conjuntos potencialmente visibles (PVS) precalculados para cada punto de vista posible en Quake (un juego que estamos desarrollando conjuntamente en id Software). El cálculo preliminar de PVS significa que, en lugar de pasar mucho tiempo buscando en la base de datos de polígonos visibles desde el punto de vista actual en la base de datos mundial, simplemente podemos dibujar todos los polígonos en el PVS de atrás hacia adelante (tomando el orden del árbol BSP del mundo; discusión de BSP- vea árboles en nuestras columnas para mayo, julio y noviembre de 1995), y obtenga la escena renderizada correctamente por completo sin buscar, permitiendo que el renderizado hacia atrás realice el último paso de eliminación de superficie oculta (HSR). Fue una idea increíble, pero para la arquitectura Quake, el camino aún no se ha completado.

Dibujando objetos en movimiento

Por ejemplo, todavía ha habido una pregunta sobre cómo ordenar y dibujar correctamente los objetos en movimiento; de hecho, esta pregunta después de la columna de enero se hizo sobre todo, así que le daré tiempo. El principal problema es que un modelo en movimiento puede caer en varias hojas BSP, y cuando el modelo se mueve, estas hojas cambian; junto con la posibilidad de encontrar varios modelos en una hoja, esto significa que no hay una manera fácil de usar el orden BSP para dibujar modelos en un orden ordenado correctamente. Cuando escribí la columna de enero, dibujamos sprites (como explosiones), modelos BSP móviles (como puertas) y modelos poligonales (como monstruos), truncando cada uno de ellos con las hojas que tocan, y luego dibujando las partes correspondientes cuando cada hoja BSP alcanzó tu turno cuando vas de atrás hacia adelante. Sin embargo, esto no resolvió el problema de clasificar varios modelos en movimiento en una hoja uno con respecto al otro, y también dejó problemas desagradables con modelos poligonales complejos.

John resolvió el problema de clasificación de sprites y modelos de polígonos de una manera sorprendentemente de baja tecnología: ahora los escribimos en el z-buffer. (Es decir, antes de renderizar cada píxel, comparamos la distancia al mismo, o z, con el valor z del píxel que ya está en la pantalla. Un nuevo píxel se dibuja solo si está más cerca que el existente). Primero, dibujamos el mundo principal: paredes, techos, etc. así En esta etapa, no se utilizan pruebas del z-buffer (como veremos pronto, la definición de las superficies visibles del mundo se realiza de otra manera); sin embargo, llenamos el búfer z con valores z (en realidad, valores 1 / z, como se describe a continuación) para todos los píxeles del mundo. Llenar un búfer Z es un proceso mucho más rápido que el búfer z que sería todo el mundo, porque no hay lectura, no hay comparaciones, solo se escriben valores z. Después de completar el dibujo y completar el z-buffer del mundo, simplemente podemos dibujar sprites y modelos poligonales usando z-buffering y obtener el tipo perfecto.

Cuando se usa el z-buffer, inevitablemente surgen preguntas: ¿cómo afecta esto a la memoria ocupada y al rendimiento? Con una resolución de 320x200, requiere 128 KB de memoria, lo cual no es trivial, pero no tanto para un juego que requiere 8 MB para funcionar. Impacto en el rendimiento: aproximadamente el 10% al llenar el z-buffer del mundo, y aproximadamente el 20% (los indicadores varían mucho) al renderizar sprites y modelos poligonales. A cambio, obtenemos un mundo perfectamente ordenado, así como la capacidad de crear efectos adicionales, por ejemplo, explosiones y humo de partículas, porque el z-buffer le permite clasificar fácilmente estos efectos en el mundo. En general, el uso de z-buffer aumentó significativamente la calidad visual y la flexibilidad del motor Quake, así como también simplificó significativamente el código, a costa de costos de memoria y rendimiento bastante razonables.

Nivelación y aumento de la productividad

Como dije anteriormente, la arquitectura Quake primero dibuja el mundo mismo, sin leer o comparar el búfer z, simplemente rellenando el búfer z con los valores de los polígonos del mundo en z. Después de eso, los objetos en movimiento se dibujan en la cima del mundo utilizando el z-buffering completo. Hasta ahora solo he hablado sobre cómo dibujar objetos en movimiento. En el resto de la columna, hablaré sobre otra parte de la ecuación de representación: dibujar el mundo mismo, cuando todo el mundo se almacena como un árbol BSP y nunca se mueve.

Como puede recordar en la columna de enero, estábamos preocupados por el rendimiento bruto y su promedio. Es decir, queríamos que el código de renderizado se ejecutara lo más rápido posible, pero al mismo tiempo, para que la diferencia entre la velocidad de renderizado de la escena central y la más lenta en renderizar la escena fuera lo más pequeña posible. No hay nada bueno en el promedio de 30 cuadros por segundo si el 10% de las escenas se dibujan a 5 fps, porque la sacudida en tales escenas será extremadamente notable en comparación con la escena promedio. Es mejor promediar la frecuencia con 15 cuadros por segundo en el 100% de los casos, a pesar de que la velocidad promedio de renderizado será la mitad.

Los PVS precalculados fueron un paso importante hacia un rendimiento más alto y más equilibrado, porque eliminaron la necesidad de determinar los polígonos visibles, una etapa bastante lenta que se manifestó peor en las escenas más complejas. Sin embargo, en algunos lugares de niveles de juego reales, los PVS precalculados contienen cinco veces más polígonos de lo que se ve realmente; junto con la eliminación de la superficie de ocultación hacia atrás (HSR), esto creó "zonas calientes" en las que la velocidad de fotogramas se redujo notablemente. Cientos de polígonos fueron dibujados de atrás hacia adelante, y la mayoría de ellos fueron rediseñados inmediatamente por polígonos más cercanos. El rendimiento bruto en su conjunto también disminuyó en un promedio del 50% de la redibujada causada por mostrar todo en el PVS. Por lo tanto, aunque renderizar conjuntos PVS hacia atrás funcionó como la última etapa del HSR y fue una mejora con respecto a la arquitectura anterior, no era ideal. John pensó que probablemente había una mejor manera de usar PVS que dibujando de adelante hacia atrás.

Y en realidad fue encontrado.

Intervalos ordenados

La última etapa ideal de HSR para Quake fue descartar todos los polígonos en el PVS que en realidad resultaron ser invisibles, y dibujar solo los píxeles visibles de los polígonos restantes sin volver a dibujar. Es decir, cada píxel se dibujaría exactamente una vez y sin pérdida de rendimiento, por supuesto. Sin embargo, una solución (que requiere costos) es dibujar de adelante hacia atrás, guardar el área que describe las partes superpuestas de la pantalla y truncar cada polígono con los bordes de esta área antes de renderizar. Suena prometedor, pero de hecho recuerda más o menos la solución del árbol de paquetes que describí en la columna de enero. Como descubrimos, este enfoque requiere un desperdicio de recursos adicionales y tiene serios problemas con el equilibrio de carga.

Puede hacerlo mucho mejor si mueve el último paso de HSR desde el nivel de polígono al nivel de intervalo y usa la solución con intervalos ordenados. En esencia, este enfoque consiste en convertir cada polígono en un conjunto de intervalos, como se muestra en la Figura 1, seguido de ordenar y truncar los intervalos entre sí, hasta que solo las partes visibles de los intervalos visibles permanezcan para renderizar, como se muestra en la Figura 2. Esto puede parecer muy similar al z-buffering (que, como dije anteriormente, es demasiado lento para ser usado en la representación del mundo, aunque es adecuado para objetos en movimiento más pequeños), pero hay diferencias importantes. A diferencia del almacenamiento en búfer en z, solo las partes visibles de los intervalos visibles se escanean píxel por píxel (aunque todos los bordes de los polígonos aún deben rasterizarse). Aún mejor, la clasificación realizada por z-buffering para cada píxel se convierte en una operación de intervalo con intervalos ordenados, y dado que una propiedad integral de la lista de intervalos es la conectividad, cada borde se ordena solo en relación con algunos intervalos en la misma fila, y se trunca solo por unos pocos intervalos cuando Superposición horizontal. Aunque las escenas complejas aún tardaron más en procesarse que las escenas simples, los peores casos no fueron tan malos como cuando se usaban árboles de vigas o cuando se ordenaba de atrás hacia adelante, porque no hay que volver a dibujar y escanear en busca de píxeles ocultos, la complejidad está limitada por la resolución de píxeles y la conectividad de intervalos limita la clasificación de los peores casos en cualquier área de la pantalla. Como beneficio adicional, la salida de los intervalos ordenados tiene exactamente la forma que necesita un rasterizador de bajo nivel: en el formato de un conjunto de descriptores de intervalos, cada uno de los cuales consiste en una coordenada del comienzo y la longitud.



Generación de intervalos

En resumen, la solución con intervalos ordenados está bastante cerca de nuestros criterios originales; aunque no ahorra costos, todavía no son del todo terribles. Elimina completamente el rediseño y escaneo de píxeles de las partes superpuestas de los polígonos, y es propenso a igualar el rendimiento en los peores casos. No dependeríamos solo de los intervalos ordenados como mecanismo para eliminar las superficies ocultas, sino que los PVS precalculados reducen el número de polígonos a un nivel que los intervalos ordenados manejan suficientemente bien.

Entonces, hemos encontrado el enfoque que necesitamos; solo queda escribir el código y esto ha terminado, ¿verdad? Si y no El enfoque conceptual con intervalos ordenados es simple, pero sorprendentemente difícil de implementar: debe tomar un par de decisiones de diseño importantes, requiere un poco de matemática y hay trampas astutas. Veamos primero las soluciones de diseño.

Costillas vs intervalos

La primera decisión es elegir qué clasificar: intervalos o aristas (ambos conceptos pertenecen a la categoría general de "intervalos ordenados"). Aunque los resultados en ambos casos serán los mismos (una lista de intervalos que deben dibujarse sin volver a dibujar), las implementaciones y las implicaciones de rendimiento son muy diferentes, ya que la clasificación y el truncamiento se realizan mediante estructuras de datos muy diferentes.

Al ordenar los intervalos, estos intervalos se almacenan en segmentos de memoria ordenados por x listas vinculadas, generalmente un segmento por línea de trama. Cada polígono, a su vez, se rasteriza en intervalos, como se muestra en la Figura 1. Cada intervalo se ordena y trunca en el segmento de memoria de la línea de trama en la que se encuentra el intervalo, como se muestra en la Figura 2, de modo que en cualquier momento cada segmento contenga los intervalos encontrados más cercanos , siempre sin superposiciones. Con este enfoque, es necesario generar todos los intervalos para cada polígono, y cada intervalo se ordena, trunca y agrega de inmediato al segmento de memoria correspondiente.



Figura 2: los intervalos del polígono A de la Figura 1 se ordenan y truncan a intervalos del polígono B, mientras que el polígono A está a una distancia constante de 100 a lo largo del eje Z, y el polígono B está a una distancia constante de 50 a lo largo del eje Z (el polígono B está más cerca de la cámara) )

Al ordenar los bordes, estos bordes se almacenan en segmentos de memoria ordenados por x listas vinculadas de acuerdo con su línea ráster inicial. Cada polígono, a su vez, se divide en bordes, juntos creando una lista de todos los bordes de la escena. Cuando todos los bordes de todos los polígonos en la pirámide de visibilidad se agregan a la lista de bordes, la lista completa se escanea en una pasada de arriba a abajo, de izquierda a derecha. Se guarda una lista de bordes activos (AEL). En cada paso hacia una nueva línea ráster, los bordes que aparecen en esta línea ráster se eliminan del AEL, los bordes activos van a sus nuevas coordenadas x, los bordes que comienzan desde la nueva línea ráster se agregan al AEL y los bordes se ordenan por la coordenada x actual.

Para cada línea ráster, se almacena una lista de polígonos activos (APL) ordenada por z. Va en orden ordenado por x AEL. Cuando se encuentra con cada borde nuevo (es decir, cuando cada polígono comienza o termina cuando se mueve de izquierda a derecha), el polígono asociado con él se activa y clasifica en APL (en el caso de un borde inicial), como se muestra en la Figura 3, o se desactiva y elimina de APL ( en el caso de un borde posterior), como se muestra en la Figura 4. Si el polígono más cercano ha cambiado (es decir, el más cercano es un nuevo polígono o el polígono más cercano ha terminado), para el polígono que acaba de dejar de ser el más cercano, se crea un intervalo a partir del punto donde el polígono no está vym porque son los más cercanos y terminando x coordenadas de los bordes y la corriente de la coordenada x se registra en el vertedero, que ahora es el más cercano. Esta coordenada almacenada se usa más tarde como el comienzo del intervalo creado cuando el nuevo polígono más cercano deja de estar al frente.



Figura 3: activación del polígono cuando se detecta un borde inicial en AEL.



Figura 4: desactivación del polígono cuando se detecta un borde posterior en AEL.

No se preocupe si no comprende completamente lo anterior; Esta es solo una descripción general rápida de la clasificación de bordes para que el resto de la columna sea más claro. Una explicación detallada estará en la siguiente columna.

Los intervalos generados al ordenar los bordes parecen ser exactamente los mismos intervalos que resultarían de la clasificación de los intervalos; La diferencia está en las estructuras de datos intermedios utilizados para ordenar los intervalos en la escena. Al ordenar las aristas, los intervalos se almacenan dentro de las aristas hasta que se genera el conjunto final de intervalos visibles, por lo que la ordenación, el recorte y la creación de intervalos se realizan cuando cada arista agrega o elimina un polígono, en función del estado del intervalo definido por la arista y el conjunto de polígonos activos. Al ordenar intervalos, los intervalos se vuelven aparentes instantáneamente cuando cada polígono se rasteriza, y estos intervalos intermedios se ordenan y truncan en relación con los intervalos en la línea de trama para crear los intervalos finales; por lo tanto, los estados de los intervalos se establecen constantemente de manera explícita, y todo el trabajo se realiza directamente a intervalos.

Tanto la clasificación por intervalos como la clasificación por bordes funcionan bien; se han utilizado con éxito en proyectos comerciales. Para Quake, elegimos la clasificación de bordes, en parte porque parece ser más eficiente y tiene una excelente conectividad horizontal que proporciona el tiempo de clasificación mínimo, en contraste con la clasificación potencialmente costosa en listas vinculadas, que puede ser necesaria al ordenar los intervalos.Sin embargo, una razón más importante fue que al ordenar los bordes, podemos dividir los bordes entre polígonos adyacentes, y esto reduce la clasificación, el recorte y la rasterización de los bordes a la mitad, y también reduce significativamente la base de datos mundial debido al hecho de que los bordes se vuelven comunes.

Y la última ventaja de ordenar los bordes es que no distingue entre polígonos convexos y cóncavos. Para la mayoría de los motores gráficos, este no es un aspecto muy importante, pero en Quake, recortar, transformar, proyectar y clasificar los bordes se ha convertido en el principal cuello de botella, por lo que estamos haciendo todo lo posible para reducir la cantidad de polígonos y bordes, y los polígonos cóncavos son muy útiles a este respecto. Aunque los polígonos cóncavos también se pueden procesar mediante intervalos de clasificación, esto implica una disminución significativa en el rendimiento.

Sin embargo, no hay una respuesta definitiva sobre el mejor enfoque. Al final, los intervalos de clasificación y los bordes de clasificación cumplen una función, y elegir entre ellos es una cuestión de usabilidad. En la siguiente columna, hablaré más sobre cómo ordenar los bordes con su implementación completa. En el resto de esta columna, sentaré las bases para la próxima hablando sobre las claves de clasificación y el cálculo de 1 / z. En el proceso, haré varias referencias a los aspectos de clasificación de bordes, que aún no se han discutido en detalle; Pido disculpas, pero esto es inevitable, y todo se aclarará solo al final de la próxima columna.

Teclas de clasificación de costillas

Ahora que sabemos que seleccionaremos la clasificación de los bordes y la usaremos para crear los intervalos de los polígonos más cercanos al espectador, surge la pregunta: ¿cómo saber si estos polígonos son los más cercanos? Idealmente, simplemente almacenaríamos la clave de clasificación de cada polígono, y cuando aparezca un nuevo borde, compararíamos la clave de su superficie con las claves de otros polígonos activos actuales para determinar fácilmente cuál de los polígonos está más cerca.

Eso suena demasiado bien, pero es posible. Si, por ejemplo, su base de datos mundial se almacena como un árbol BSP, y todos los polígonos se truncan en hojas BSP, entonces el orden transversal de BSP será el orden de representación correcto. Por lo tanto, por ejemplo, si recorre BSP de adelante hacia atrás, asignando a cada polígono un valor de clave incrementalmente mayor cuando lo alcanza, entonces los polígonos con valores de clave más altos estarían garantizados frente a polígonos con claves más pequeñas. Este enfoque se ha utilizado en Quake durante algún tiempo, pero ahora se está aplicando una solución diferente por razones que explicaré en breve.

Si no tiene un BSP o estructura de datos similar, o si tiene muchos polígonos en movimiento (BSP no procesa polígonos en movimiento de manera muy eficiente), entonces otra forma de lograr objetivos es ordenar todos los polígonos entre sí antes de renderizar la escena y asignar las teclas correspondientes de acuerdo con su espacio relaciones en la ventana gráfica. Desafortunadamente, en el caso general, esta es una tarea extremadamente lenta, porque cada polígono necesita ser comparado entre sí. Existen técnicas para mejorar el rendimiento de la clasificación de polígonos, pero no conozco a nadie que realice una clasificación general de polígonos en una PC en tiempo real.

Una alternativa es ordenar por distancia z desde el visor en el espacio de la pantalla; Esta solución encaja bien con la conectividad espacial superior de los bordes de clasificación. Al reunirse con cada nueva arista en la línea de trama, puede calcular la distancia z del polígono correspondiente y compararla con las distancias de otros polígonos, después de lo cual el polígono se puede guardar en APL.

Sin embargo, obtener distancias a lo largo de z puede ser una tarea difícil. No olvide que necesitamos poder calcular z en cualquier punto arbitrario del polígono, porque puede ocurrir un borde y hacer que el polígono se clasifique en el APL en cualquier lugar de la pantalla. Podemos calcular z directamente desde las coordenadas de pantalla x e y y las ecuaciones del plano del polígono, pero, desafortunadamente, esto no se puede hacer muy rápidamente, porque z para el plano no cambia linealmente en el espacio de la pantalla; sin embargo, 1 / z varía linealmente, por lo que usamos este valor. (Para una discusión sobre linealidad en el espacio de pantalla y gradientes para 1 / z, vea la serie de Chris Hecker sobre mapeo de texturas en la revista Game Developer el año pasado.) Otra ventaja de usar 1 / z es que la resolución aumenta al disminuir la distancia, es decir, con 1 / z siempre tendremos la mejor resolución de profundidad para objetos cercanos que son más importantes.

La forma obvia de obtener el valor 1 / z en cualquier punto arbitrario del polígono es calcular 1 / z en los vértices, interpolarlos sobre ambos bordes del polígono e interpolar entre los bordes para obtener el valor en el punto deseado. Desafortunadamente, esto requiere mucho trabajo a lo largo de cada costilla; peor, esto requiere división para calcular el paso 1 / z por píxel en cada intervalo.

Sería mejor calcular 1 / z directamente a partir de la ecuación del plano y la pantalla x e y del píxel que nos interesa. La ecuación tiene la siguiente forma:

$$

$$1/z = (a/d)x' - (b/d)y' + c/d$$

donde z es la coordenada en el espacio z del punto en el plano que se proyecta en las coordenadas de la pantalla (x ', y') (el origen de las coordenadas para estos cálculos es el centro de proyección, el punto en la pantalla justo en frente del punto de vista), [abc] es normal al plano en la ventana gráfica, y d es la distancia desde el origen de la ventana gráfica al plano a lo largo de la normal. La división se realiza solo una vez para cada plano, porque a, b, cyd son constantes para los planos.

Un cálculo completo de 1 / z requiere dos multiplicaciones y dos adiciones, y cada operación debe realizarse con un punto flotante para evitar errores de rango. Tal volumen de cálculos de coma flotante parece costoso, pero en realidad no lo es, especialmente en los procesadores Pentium, donde el valor del plano 1 / z en cualquier punto se puede calcular en lenguaje ensamblador en solo seis ciclos.

Si está interesado, aquí hay una derivación rápida de la ecuación 1 / z. La ecuación del plano para el plano tiene la siguiente forma:

$$

$$ax + by + cz - d = 0$$

donde x e y son las coordenadas del espacio de vista, a, b, c, d y z se definen arriba. Si hacemos la sustitución$$$x=x'z$ y $$$y=-y'z$(desde la definición de proyección en perspectiva; y cambia de signo porque aumenta en la ventana gráfica, pero disminuye en el espacio de la pantalla). Realizando una permutación, obtenemos:

$$

$$z = d / (ax' - by' + c)$$

Al invertir y expandir la ecuación, obtenemos:

$$

$$1/z = ax'/d - by'/d + c/d$$

Más tarde mostraré la clasificación 1 / z en acción.

Temblor y ordenar por z

Mencioné anteriormente que Quake ya no usa el orden BSP como una clave de clasificación; de hecho, 1 / z ahora se aplica como clave. A pesar de la elegancia de los gradientes, calcular 1 / z a partir de ellos es obviamente más lento que simplemente compararlo con la clave de orden BSP, entonces, ¿por qué cambiamos a usar 1 / z en Quake?

La razón principal es la disminución en el número de polígonos. Para renderizar en orden BSP, es necesario seguir ciertas reglas, incluidos los polígonos cuando se intersecan con planos BSP deben dividirse. Esta separación aumenta significativamente el número de polígonos y bordes. Gracias a la clasificación por 1 / z, podemos dejar los polígonos sin dividir, pero aún así obtener el orden de dibujo correcto, por lo que debemos procesar muchos menos bordes; mientras que el renderizado generalmente se acelera, a pesar del costo adicional de ordenar por 1 / z.

Otra ventaja de la clasificación 1 / z es que resuelve los problemas de clasificación mencionados al principio de este artículo: modelos en movimiento, que en sí mismos son pequeños árboles BSP. La clasificación en el orden mundial BSP no funcionará aquí porque estos modelos son BSP separados, y no hay formas fáciles de integrarlos en el orden secuencial del mundo BSP. No queremos utilizar el almacenamiento en búfer en z para estos modelos, ya que a menudo son objetos grandes (por ejemplo, puertas), y no queremos perder los beneficios de reducir el rediseño que proporcionan las puertas cerradas al procesar a través de la lista de bordes. Cuando se usan intervalos ordenados, los bordes de los modelos BSP en movimiento simplemente se colocan en la lista de bordes (primero truncando los polígonos para que no se crucen con superficies sólidas del mundo para evitar la complejidad,relacionado con la penetración mutua) en lugar de todos los bordes del mundo, y el resto se ordena por 1 / z.

Seguir adelante

El artículo, sin duda, presenta una gran cantidad de información, y aún no se le ha metido mucha información. El código y la explicación del próximo artículo ayudarán; si desea consultar con anticipación, para cuando lea este artículo, el código debe estar disponible en ftp.idsoftware.com/mikeab/ddjsort.zip. También vale la pena echar un vistazo a Computer Graphics Foley y Van Dam o Elementos de procedimiento para Computer Graphics Rogers.

Por el momento no está claro cómo el resultado del terremotodebe ordenar los bordes, en orden BSP o 1 / z. De hecho, no hay garantía de que los intervalos ordenados en cualquier forma sean la solución final. A veces parece que cambiamos los motores gráficos con tanta frecuencia como ponen a Elvis en las estaciones de radio dedicadas a los éxitos de los años 50 (pero, con suerte, ¡con resultados mucho más estéticamente agradables!), Y sin duda consideraremos alternativas hasta la fecha de lanzamiento los juegos