La representación de líneas de escaneo (también representación de líneas de escaneo y representación de líneas de escaneo ) es un algoritmo para la determinación de superficies visibles , en gráficos de computadora 3D , 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 representar primero se ordenan por la coordenada y superior en la que aparecen por primera vez, luego cada fila o línea de escaneo de la imagen se calcula utilizando la intersección de una línea de escaneo con los polígonos en el frente de la lista ordenada, mientras que la lista ordenada se actualiza para descartar polígonos que ya no son visibles a medida que la línea de escaneo 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 escaneo 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é , por lo que evitar volver a acceder a los vértices en 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 Phong o el algoritmo Z-buffer .
El método habitual comienza con los bordes de los polígonos proyectados insertados en contenedores, uno por línea de escaneo; el rasterizador mantiene una tabla de bordes activos ( AET ). Las entradas mantienen vínculos de ordenación, coordenadas X, gradientes y referencias a los polígonos que delimitan. Para rasterizar la siguiente línea de escaneo, se eliminan los bordes que ya no son relevantes; se agregan nuevos bordes del contenedor Y de las líneas de escaneo actuales, insertados ordenados por coordenada X. Las entradas de la tabla de bordes activos tienen información de X y otros parámetros incrementados. Las entradas de la tabla de bordes activos se mantienen en una lista ordenada por X, lo que efectúa 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 por Z, insertando y eliminando las superficies cuando se cruzan los bordes. [ cita requerida ]
Un híbrido entre esto y el buffer Z elimina la ordenación de la tabla de bordes activos y, en su lugar, rasteriza una línea de escaneo a la vez en un buffer Z, manteniendo los intervalos de polígonos activos de una línea de escaneo a la siguiente.
En otra variante, se rasteriza un buffer de identificación 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 representación de líneas de exploración fue probablemente realizada por Wylie, Romney, Evans y Erdahl en 1967. [1]
Otros desarrollos tempranos del método de renderizado de líneas de exploración 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 .
La primera línea de generadores de imágenes (IG) de Evans & Sutherland ESIG empleaba la técnica en hardware "sobre la marcha" para generar imágenes de a una línea de trama por vez sin un búfer de cuadros , lo que ahorraba la necesidad de memoria, que en ese entonces era costosa. Las variantes posteriores utilizaban un enfoque híbrido.
La Nintendo DS es el último hardware que permite renderizar escenas 3D de esta manera, con la opción de almacenar en caché las imágenes rasterizadas en VRAM.
El hardware de sprites predominante en las máquinas de juegos de la década de 1980 puede considerarse una forma simple 2D de representación de líneas de exploración.
La técnica se utilizó en el primer motor Quake para la representación de entornos mediante software (pero los objetos en movimiento se almacenaban en el búfer Z por encima). Los escenarios estáticos utilizaban una clasificación derivada de BSP para la prioridad. Resultó mejor que los algoritmos de tipo Z-buffer / painting para manejar 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íneas de escaneo de software en un segundo procesador Cell durante el desarrollo de la PlayStation 3 , antes de decidirse por una disposición convencional de CPU/GPU.
Un principio similar se emplea en la renderización en mosaico (el más famoso es el chip PowerVR 3D); es decir, los elementos primitivos se clasifican en el espacio de la pantalla y luego se renderizan en la memoria rápida del 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, lo que ahorra la necesidad de un búfer de cuadros completo, algo similar al espíritu de la renderización de líneas de escaneo de hardware.
Algunos rasterizadores de software utilizan "almacenamiento en búfer de intervalos" (o "almacenamiento en búfer de cobertura"), en el que se almacena una lista de intervalos ordenados y recortados en contenedores de líneas de escaneo. Las primitivas se agregarían sucesivamente a esta estructura de datos, antes de rasterizar solo los píxeles visibles en una etapa final.
La principal ventaja de la representación de líneas 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 utilizan efectos de transparencia, lo que es un beneficio para el caso de alta resolución o cálculos de sombreado costosos.
En los sistemas de búfer Z modernos, se pueden obtener beneficios similares a través de una clasificación aproximada de adelante hacia atrás (que se acerca 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 escaneo que trabajan en el raster tienen el inconveniente de que la sobrecarga no se maneja con elegancia.
Se considera que la técnica no se escala bien a medida que aumenta el número de primitivos. Esto se debe al tamaño de las estructuras de datos intermedias necesarias durante la renderización, que pueden superar el tamaño de un búfer Z para una escena compleja.
En consecuencia, en las aplicaciones de gráficos interactivos contemporáneas, el búfer Z se ha vuelto omnipresente. El búfer Z permite recorrer volúmenes mayores de primitivas de forma lineal, en paralelo, de una manera compatible 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.