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 la superficie visible , en gráficos por computadora en 3D , que funciona fila por fila en lugar de polígono por polígono o píxel por píxel. base. Todos los polígonos que se van a representar se ordenan primero 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 usando la intersección de una línea de escaneo con los polígonos al frente de la lista ordenada, mientras 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 escaneo reduce el número de comparaciones entre aristas. 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 intersectan la línea de exploración 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 .
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 borde activa ( AET ). Las entradas mantienen vínculos de clasificación, coordenadas X, gradientes y referencias a los polígonos que unen. Para rasterizar la siguiente línea de exploración, se eliminan los bordes que ya no son relevantes; Se agregan nuevos bordes del depósito Y de las líneas de exploración actuales, insertados ordenados por coordenada X. Las entradas de la tabla perimetral activa tienen X y otra información de parámetros incrementada. Las entradas activas de la tabla de bordes se mantienen en una lista ordenada en 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 en Z, insertando y eliminando las superficies cuando se cruzan los bordes. [ cita necesaria ]
Un híbrido entre esto y el almacenamiento en búfer Z elimina la clasificación activa de la tabla de bordes y, en su lugar, rasteriza una línea de exploración a la vez en un búfer Z, manteniendo tramos de polígonos activos de una línea de exploración a la siguiente.
En otra variante, se rasteriza un búfer de ID en un paso intermedio, lo que permite un sombreado diferido de los píxeles visibles resultantes.
La primera publicación de la técnica de renderizado de líneas de exploración fue probablemente de 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) ESIG de Evans & Sutherland empleaba la técnica en hardware "sobre la marcha", para generar imágenes una línea rasterizada a la vez sin un framebuffer , ahorrando la necesidad de una memoria entonces costosa. Las variantes posteriores utilizaron un enfoque híbrido.
La Nintendo DS es el último hardware que renderiza 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 renderizado de líneas de exploración.
La técnica se utilizó en el primer motor 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ó clasificación derivada de BSP como prioridad. Resultó mejor que los algoritmos tipo Z-buffer / pintor 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 escaneo de software en un segundo procesador Cell durante el desarrollo de PlayStation 3 , antes de decidirse por una disposición de CPU/GPU convencional.
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 del chip, un mosaico a la vez. Dreamcast proporcionó un modo para rasterizar una fila de mosaicos a la vez para un escaneo ráster directo, ahorrando la necesidad de un framebuffer completo, algo en el espíritu del renderizado de líneas de escaneo por hardware .
Algunos rasterizadores de software utilizan 'almacenamiento en búfer de tramos' (o 'almacenamiento en búfer de cobertura'), en el que se almacena una lista de tramos ordenados y recortados en depósitos de líneas de escaneo. Se agregarían sucesivamente primitivos a esta estructura de datos, antes de rasterizar solo los píxeles visibles en una etapa final.
La principal ventaja del renderizado de línea de exploración sobre el almacenamiento en 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 para el caso de alta resolución o cálculos de sombreado costosos. .
En los sistemas Z-buffer modernos, se pueden obtener beneficios similares mediante una clasificación aproximada de adelante hacia atrás (acercándose al 'algoritmo de pintores inversos'), un 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 línea de exploración que trabajan 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 de gráficos interactivos contemporáneas, el Z-buffer se ha vuelto omnipresente. El Z-buffer permite recorrer linealmente, en paralelo, volúmenes más grandes de primitivas, de una manera amigable para el hardware moderno. Las coordenadas transformadas, los gradientes de atributos, etc., nunca necesitan salir del chip gráfico; sólo se almacenan los píxeles visibles y los valores de profundidad.