Representación de línea de exploración

Ejemplo de algoritmo de línea de exploración

Representación de línea de exploración (también representación de línea de exploración y representación 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 a representar se ordenan primero por 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 usando la intersección de una línea de exploración con los polígonos en el 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 a lo largo de la normal del plano de exploración reduce el número de comparaciones entre los bordes. Otra ventaja es que no es necesario traducir las coordenadas de todos los vértices de la memoria principal a la memoria de trabajo: solo los vértices que definen los bordes 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 el enlace entre la unidad central de procesamiento y la memoria caché y, por lo tanto, evitar volver a acceder a los vértices de la memoria principal puede proporcionar una aceleración sustancial.

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 Z-buffer.

Algoritmo

El método habitual comienza con bordes de polígonos proyectados insertados en cubos, uno por línea de exploración; el rasterizador mantiene una tabla de borde activa (AET). Las entradas mantienen vínculos de clasificación, coordenadas X, degradados 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; nuevos bordes de las líneas de exploración actuales' Se agregan cubos Y, se insertan ordenados por coordenada X. Las entradas de la tabla de borde activo tienen X y otra información de parámetros incrementada. Las entradas de la tabla de borde activo se mantienen en una lista ordenada por X por ordenación de burbujas, lo que produce un cambio cuando se cruzan 2 bordes. Después de actualizar los bordes, la tabla de bordes activos se recorre en X para emitir solo los tramos visibles, manteniendo una tabla de tramos activa ordenada en Z, insertando y eliminando las superficies cuando se cruzan los bordes.

Variantes

Un híbrido entre esto y el almacenamiento en búfer Z elimina la clasificación activa de la tabla de borde y, en su lugar, rasteriza una línea de escaneo a la vez en un búfer Z, manteniendo tramos de polígonos activos de una línea de escaneo 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.

Historia

La primera publicación de la técnica de renderizado scanline fue probablemente de Wylie, Romney, Evans y Erdahl en 1967.

Otros desarrollos tempranos del método de renderizado scanline fueron realizados por Bouknight en 1969 y Newell, Newell y Sancha en 1972. 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 el Evans &Amp; Compañía Sutherland en Salt Lake City.

Usar en renderizado en tiempo real

Los primeros Evans & La línea ESIG de generadores de imágenes (IG) de Sutherland empleó la técnica en hardware 'sobre la marcha', para generar imágenes una línea de trama a la vez sin un búfer de fotogramas, ahorrando la necesidad de una memoria costosa. Las variantes posteriores utilizaron un enfoque híbrido.

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

El hardware de sprites que prevalecía en las máquinas de juegos de la década de 1980 puede considerarse una forma 2D simple de representación de línea de exploración.

La técnica se usó en el primer motor de Quake para la representación de entornos por software (pero los objetos en movimiento tenían un búfer Z en la parte superior). El escenario estático utilizó la clasificación derivada de BSP para la prioridad. Resultó mejor que los algoritmos tipo Z-buffer/painter en el manejo de escenas de alta complejidad de profundidad con costosas operaciones de píxeles (es decir, mapeo de texturas con perspectiva correcta sin asistencia de hardware). Este uso precedió a la adopción generalizada de GPU basadas en búfer Z que ahora son comunes en las PC.

Sony experimentó con renderizadores de línea de exploración de software en un segundo procesador Cell durante el desarrollo de PlayStation 3, antes de decidirse por una disposición de CPU/GPU convencional.

Técnicas similares

Se emplea un principio similar en el renderizado en mosaico (el más famoso es el chip PowerVR 3D); es decir, las primitivas se clasifican en el espacio de la pantalla y luego se procesan en la memoria rápida en el chip, un mosaico a la vez. Dreamcast proporcionó un modo para rasterizar una fila de mosaicos a la vez para el escaneo de trama directo, ahorrando la necesidad de un búfer de cuadros completo, algo en el espíritu de la representación de línea de escaneo de hardware.

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

Comparación con el algoritmo Z-buffer

La principal ventaja del renderizado de línea de exploración sobre el almacenamiento en búfer Z es que la cantidad de veces que se procesan los píxeles visibles se mantiene al mínimo absoluto, que siempre es una vez si no se usan efectos de transparencia, un beneficio para el caso de alta resolución o costosos cálculos de sombreado.

En los sistemas Z-buffer modernos, se pueden obtener beneficios similares a través de una clasificación aproximada de adelante hacia atrás (acercándose al 'algoritmo de pintores inversos'), rechazo Z temprano (junto con Z jerárquico), y técnicas de renderizado diferido menos comunes posibles en GPU programables.

Las técnicas de línea de exploración que funcionan en el ráster tienen el inconveniente de que la sobrecarga no se maneja correctamente.

Se considera que la técnica no escala bien a medida que aumenta el número de primitivas. Esto se debe al tamaño de las estructuras de datos intermedias requeridas durante el renderizado, que pueden exceder 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. El búfer Z permite que grandes volúmenes de primitivas se atraviesen linealmente, en paralelo, de una manera amigable con el 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.