Renderizado por líneas de exploración

El renderizado por líneas de exploración (también conocido como renderizado por línea de exploración o renderizado de línea de exploración ) es un algoritmo para la determinación de superficies visibles en gráficos 3D por computadora , que funciona fila por fila en lugar de polígono por polígono o píxel por píxel. Todos los polígonos que se van a renderizar se ordenan primero según la coordenada y superior en la que aparecen por primera vez; luego, cada fila o línea de exploración de la imagen se calcula utilizando la intersección de una línea de exploración con los polígonos que se encuentran al frente de la lista ordenada, mientras que la lista ordenada se actualiza para descartar los polígonos que ya no son visibles a medida que la línea de exploración activa avanza hacia abajo en la imagen.

La principal ventaja de este método es que ordenar los vértices según la normal del plano de escaneo reduce el número de comparaciones entre aristas. Otra ventaja es que no es necesario transferir las coordenadas de todos los vértices de la memoria principal a la memoria de trabajo ; solo los vértices que definen las aristas que intersecan la línea de escaneo actual deben estar en la memoria activa, y cada vértice se lee solo una vez. La memoria principal suele ser muy lenta en comparación con la conexión entre la unidad central de procesamiento y la memoria caché , por lo que evitar el acceso repetido a los vértices en la memoria principal puede proporcionar una mejora sustancial en la velocidad.

Este tipo de algoritmo se puede integrar fácilmente con muchas otras técnicas gráficas, como el modelo de reflexión de Phong o el algoritmo de búfer Z.

El método habitual comienza con los bordes de los polígonos proyectados insertados en cubos, uno por línea de exploración; el rasterizador mantiene una tabla de bordes activos ( AET ). Las entradas mantienen enlaces de ordenación, coordenadas X, gradientes y referencias a los polígonos que delimitan. Para rasterizar la siguiente línea de exploración, se eliminan los bordes que ya no son relevantes; se añaden nuevos bordes del cubo Y de la línea de exploración actual, insertados ordenados por coordenada X. Las entradas de la tabla de bordes activos tienen X y otra información de parámetros incrementada. Las entradas de la tabla de bordes activos se mantienen en una lista ordenada por X, lo que produce un cambio cuando 2 bordes se cruzan. Después de actualizar los bordes, la tabla de bordes activos se recorre en orden X para emitir solo los tramos visibles, manteniendo una tabla de tramos activos ordenada por Z, insertando y eliminando las superficies cuando se cruzan los bordes.

Un sistema híbrido entre este método y el almacenamiento en búfer Z elimina la clasificación de la tabla de bordes activos y, en su lugar, rasteriza una línea de exploración a la vez en un búfer Z, manteniendo los tramos de polígonos activos de una línea de exploración a la siguiente.

En otra variante, un búfer de ID se rasteriza en un paso intermedio, lo que permite el sombreado diferido de los píxeles visibles resultantes.

La primera publicación de la técnica de renderizado por líneas de escaneo fue probablemente de Wylie, Romney, Evans y Erdahl en 1967. ^{[ 1 ]}

Otros desarrollos tempranos del método de renderizado de líneas de escaneo fueron realizados por Bouknight en 1969, ^{[ 2 ]} y Newell, Newell y Sancha en 1972. ^{[ 3 ]} Gran parte del trabajo inicial sobre estos métodos se realizó en el grupo de gráficos de Ivan Sutherland en la Universidad de Utah y en la empresa Evans & Sutherland en Salt Lake City .

Los primeros generadores de imágenes (IG) de la línea ESIG de Evans & Sutherland empleaban esta técnica en hardware "sobre la marcha", para generar imágenes línea por línea sin necesidad de un búfer de fotogramas , lo que evitaba la necesidad de una memoria que, en aquel entonces, era costosa. Las variantes posteriores utilizaron un enfoque híbrido.

La Nintendo DS es el hardware más reciente capaz de renderizar escenas 3D de esta manera, con la opción de almacenar en caché las imágenes rasterizadas en la VRAM.

El hardware de sprites predominante en las máquinas de videojuegos de los años 80 puede considerarse una forma simple de renderizado por líneas de exploración en 2D.

Esta técnica se utilizó en el primer motor de Quake para la renderización por software de entornos (aunque los objetos en movimiento se renderizaban mediante búfer Z ). Los escenarios estáticos empleaban una clasificación basada en BSP para la priorización. Demostró ser superior a los algoritmos de tipo búfer Z / pintor para el manejo de escenas de alta complejidad de profundidad con costosas operaciones de píxeles (es decir, mapeo de texturas con corrección de perspectiva sin asistencia de hardware). Este uso precedió a la adopción generalizada de las GPU basadas en búfer Z, ahora comunes en los PC.

Durante el desarrollo de la PlayStation 3 , Sony experimentó con renderizadores de líneas de exploración por software en un segundo procesador Cell , antes de decantarse por una configuración convencional de CPU/GPU.

Se emplea un principio similar en la renderización por mosaicos (el ejemplo más conocido es el chip PowerVR 3D); es decir, las primitivas se organizan en el espacio de la pantalla y luego se renderizan en la memoria rápida del chip, un mosaico a la vez. La Dreamcast ofrecía un modo para rasterizar una fila de mosaicos a la vez para la exploración directa de tramas, lo que evitaba la necesidad de un búfer de fotogramas completo, en cierto modo siguiendo la línea de la renderización por líneas de exploración de hardware.

Algunos rasterizadores de software utilizan el «almacenamiento en búfer de intervalos» (o «almacenamiento en búfer de cobertura»), en el que una lista de intervalos ordenados y recortados se almacena en cubos de líneas de exploración. Las primitivas se añadirían sucesivamente a esta estructura de datos, antes de rasterizar solo los píxeles visibles en una etapa final.

La principal ventaja de la renderización por líneas de exploración sobre el búfer Z es que el número de veces que se procesan los píxeles visibles se mantiene al mínimo absoluto, que siempre es una vez si no se utilizan efectos de transparencia; una ventaja en el caso de alta resolución o cálculos de sombreado costosos.

En los sistemas modernos de búfer Z, se pueden obtener beneficios similares mediante una clasificación aproximada de adelante hacia atrás (que se aproxima al "algoritmo de pintores inversos"), el rechazo temprano de Z (junto con Z jerárquico) y técnicas de renderizado diferido menos comunes posibles en GPU programables.

Las técnicas de escaneo lineal que funcionan sobre la trama tienen el inconveniente de que la sobrecarga no se maneja de forma adecuada.

Esta técnica no se considera escalable a medida que aumenta el número de primitivas. Esto se debe al tamaño de las estructuras de datos intermedias necesarias durante el renderizado, que pueden superar el tamaño de un búfer Z para una escena compleja.

En consecuencia, en las aplicaciones gráficas interactivas contemporáneas, el búfer Z se ha vuelto omnipresente. Este búfer permite recorrer grandes volúmenes de primitivas de forma lineal y paralela, de una manera que facilita el uso del hardware moderno. Las coordenadas transformadas, los gradientes de atributos, etc., nunca necesitan salir del chip gráfico; solo se almacenan los píxeles visibles y los valores de profundidad.

• escaneo raster
• trazado de rayos
• Almacenamiento en búfer Z
• Adaptador de interfaz de televisión , el chip de la Atari 2600, que procesaba los gráficos línea por línea sin un búfer de fotogramas.

• Historia del Grupo de Diseño Gráfico de la Universidad de Utah