Un gráfico de escena es una estructura de datos general que se utiliza habitualmente en aplicaciones de edición de gráficos basados en vectores y en juegos de ordenador modernos, que organiza la representación lógica y a menudo espacial de una escena gráfica. Es una colección de nodos en un gráfico o una estructura de árbol . Un nodo de árbol puede tener muchos hijos pero un solo padre, y el efecto de un padre se aplica a todos sus nodos hijos; una operación realizada en un grupo propaga automáticamente su efecto a todos sus miembros. En muchos programas, asociar una matriz de transformación geométrica (véase también transformación y matriz ) en cada nivel de grupo y concatenar dichas matrices es una forma eficiente y natural de procesar dichas operaciones. Una característica común, por ejemplo, es la capacidad de agrupar formas y objetos relacionados en un objeto compuesto que luego se puede manipular con la misma facilidad que un objeto único.
En la edición de gráficos basados en vectores, cada nodo de hoja en un gráfico de escena representa una unidad atómica del documento, generalmente una forma como una elipse o una ruta de Bézier . Aunque las formas en sí mismas (en particular las rutas) se pueden descomponer en nodos como los nodos spline , es práctico pensar en el gráfico de escena como compuesto de formas en lugar de ir a un nivel inferior de representación.
Otro concepto de nodo útil y controlado por el usuario es el de capa . Una capa actúa como una hoja transparente sobre la que se puede colocar cualquier cantidad de formas y grupos de formas. El documento se convierte entonces en un conjunto de capas, cualquiera de las cuales se puede hacer invisible, atenuar o bloquear (convertir en solo lectura) de manera conveniente. Algunas aplicaciones colocan todas las capas en una lista lineal, mientras que otras admiten capas dentro de capas con cualquier profundidad deseada.
Internamente, puede que no haya ninguna diferencia estructural real entre capas y grupos, ya que ambos son simplemente nodos de un gráfico de escena. Si se necesitan diferencias, una declaración de tipo común en C++ sería crear una clase de nodo genérica y luego derivar capas y grupos como subclases. Un miembro de visibilidad, por ejemplo, sería una característica de una capa, pero no necesariamente de un grupo.
Los gráficos de escena son útiles para los juegos modernos que utilizan gráficos en 3D y mundos o niveles cada vez más grandes. En dichas aplicaciones, los nodos de un gráfico de escena (por lo general) representan entidades u objetos en la escena.
Por ejemplo, un juego podría definir una relación lógica entre un caballero y un caballo, de modo que el caballero se considere una extensión del caballo. El gráfico de escena tendría un nodo "caballo" con un nodo "caballero" adjunto.
El gráfico de escena también puede describir la relación espacial y lógica de las distintas entidades: el caballero se mueve a través del espacio 3D mientras el caballo se mueve.
En estas grandes aplicaciones, los requisitos de memoria son consideraciones importantes al diseñar un gráfico de escena. Por este motivo, muchos sistemas de gráficos de escena de gran tamaño utilizan la creación de instancias de geometría para reducir los costos de memoria y aumentar la velocidad. En nuestro ejemplo anterior, cada caballero es un nodo de escena independiente, pero se crea una instancia de la representación gráfica del caballero (compuesta por una malla 3D, texturas, materiales y sombreadores). Esto significa que solo se conserva una única copia de los datos, a la que luego hacen referencia los nodos "caballero" en el gráfico de escena. Esto permite un presupuesto de memoria reducido y una mayor velocidad, ya que cuando se crea un nuevo nodo de caballero, no es necesario duplicar los datos de apariencia.
La forma más simple de un gráfico de escena utiliza una estructura de datos de matriz o lista enlazada , y mostrar sus formas es simplemente una cuestión de iterar linealmente los nodos uno por uno. Otras operaciones comunes, como verificar qué forma interseca el puntero del mouse , también se realizan mediante búsquedas lineales. Para gráficos de escena pequeños, esto suele ser suficiente.
La aplicación de una operación en un gráfico de escena requiere alguna forma de enviar una operación en función del tipo de nodo. Por ejemplo, en una operación de renderizado, un nodo de grupo de transformación acumularía su transformación mediante multiplicación de matrices, desplazamiento vectorial, cuaterniones o ángulos de Euler . Después de lo cual, un nodo de hoja envía el objeto para que se renderice en el renderizador. Algunas implementaciones pueden renderizar el objeto directamente, lo que invoca la API de renderizado subyacente , como DirectX u OpenGL . Pero como la implementación subyacente de la API de renderizado generalmente carece de portabilidad, se pueden separar los sistemas de renderizado y gráfico de escena. Para lograr este tipo de envío, se pueden adoptar varios enfoques diferentes.
En lenguajes orientados a objetos como C++ , esto se puede lograr fácilmente mediante funciones virtuales , donde cada una representa una operación que se puede realizar en un nodo. Las funciones virtuales son fáciles de escribir, pero normalmente es imposible agregar nuevas operaciones a los nodos sin acceso al código fuente. Como alternativa, se puede utilizar el patrón visitante . Esto tiene una desventaja similar, ya que es igualmente difícil agregar nuevos tipos de nodos.
Otras técnicas implican el uso de RTTI ( Run-Time Type Information ). La operación se puede realizar como una clase que se pasa al nodo actual; luego consulta el tipo del nodo utilizando RTTI y busca la operación correcta en una matriz de devoluciones de llamadas o funtores . Esto requiere que el mapa de tipos a devoluciones de llamadas o funtores se inicialice en tiempo de ejecución, pero ofrece más flexibilidad, velocidad y extensibilidad.
Existen variaciones de estas técnicas y los nuevos métodos pueden ofrecer beneficios adicionales. Una alternativa es la reconstrucción del gráfico de escena, en la que el gráfico de escena se reconstruye para cada una de las operaciones realizadas. Sin embargo, esto puede ser muy lento, pero produce un gráfico de escena altamente optimizado. Esto demuestra que una buena implementación del gráfico de escena depende en gran medida de la aplicación en la que se utiliza.
Los recorridos son la clave para la potencia de la aplicación de operaciones a los gráficos de escena. Un recorrido generalmente consiste en comenzar en un nodo arbitrario (a menudo la raíz del gráfico de escena), aplicar la(s) operación(es) (a menudo las operaciones de actualización y renderización se aplican una tras otra) y moverse recursivamente hacia abajo en el gráfico de escena (árbol) hasta los nodos secundarios, hasta que se llega a un nodo hoja. En este punto, muchos motores de gráficos de escena vuelven a recorrer el árbol, aplicando una operación similar. Por ejemplo, considere una operación de renderización que tenga en cuenta las transformaciones: mientras se recorre recursivamente hacia abajo en la jerarquía del gráfico de escena, se llama a una operación de pre-renderización. Si el nodo es un nodo de transformación, agrega su propia transformación a la matriz de transformación actual. Una vez que la operación termina de recorrer todos los hijos de un nodo, llama a la operación de post-renderización del nodo para que el nodo de transformación pueda deshacer la transformación. Este enfoque reduce drásticamente la cantidad necesaria de multiplicación de matrices. [ cita requerida ]
Algunas operaciones de gráficos de escena son en realidad más eficientes cuando los nodos se recorren en un orden diferente: aquí es donde algunos sistemas implementan la reconstrucción del gráfico de escena para reordenarlo en un formato o árbol más fácil de analizar.
Por ejemplo, en los casos 2D, los gráficos de escena normalmente se renderizan a sí mismos comenzando en el nodo raíz del árbol y luego dibujan recursivamente los nodos secundarios. Las hojas del árbol representan los objetos más en primer plano. Dado que el dibujo procede de atrás hacia adelante y los objetos más cercanos simplemente sobrescriben a los más lejanos, el proceso se conoce como empleo del algoritmo Painter . En los sistemas 3D, que a menudo emplean búferes de profundidad , es más eficiente dibujar primero los objetos más cercanos, ya que los objetos más lejanos a menudo solo necesitan ser probados en profundidad en lugar de renderizados realmente, porque están ocluidos por objetos más cercanos.
Las jerarquías de volumen delimitador (BVH) son útiles para numerosas tareas, entre ellas, la eliminación eficiente de objetos y la aceleración de la detección de colisiones entre objetos. Una BVH es una estructura espacial, pero no tiene por qué dividir la geometría (consulte la partición espacial a continuación).
Un BVH es un árbol de volúmenes delimitadores (a menudo esferas, cuadros delimitadores alineados con ejes o cuadros delimitadores orientados). En la parte inferior de la jerarquía, el tamaño del volumen es lo suficientemente grande como para abarcar un único objeto de forma ajustada (o posiblemente incluso una fracción más pequeña de un objeto en los BVH de alta resolución). A medida que se asciende en la jerarquía, cada nodo tiene su propio volumen que abarca de forma ajustada todos los volúmenes que se encuentran debajo de él. En la raíz del árbol hay un volumen que abarca todos los volúmenes del árbol (toda la escena).
Los BVH son útiles para acelerar la detección de colisiones entre objetos. Si el volumen delimitador de un objeto no interseca un volumen superior en el árbol, no puede intersectar ningún objeto que se encuentre por debajo de ese nodo (por lo que todos se rechazan muy rápidamente).
Existen algunas similitudes entre los BVH y los gráficos de escena. Un gráfico de escena se puede adaptar fácilmente para incluir/convertirse en un BVH, si cada nodo tiene un volumen asociado o si se agrega un "nodo vinculado" creado específicamente en una ubicación conveniente en la jerarquía. Puede que esta no sea la vista típica de un gráfico de escena, pero incluir un BVH en un gráfico de escena tiene sus ventajas.
Una forma eficaz de combinar la partición espacial y los gráficos de escena es mediante la creación de un nodo de hoja de escena que contenga los datos de partición espacial. [ aclaración necesaria ] Esto puede aumentar la eficiencia computacional de la representación.
Los datos espaciales suelen ser estáticos y generalmente contienen datos de escenas que no se mueven en algún formato particionado. [ Se necesita aclaración ] Algunos sistemas pueden tener los sistemas y su representación por separado. Esto está bien y no hay ventajas reales para ninguno de los dos métodos. En particular, es malo tener el gráfico de escena contenido dentro del sistema de partición espacial, ya que es mejor considerar el gráfico de escena como el sistema más amplio de la partición espacial. [ Se discute la neutralidad ]
Los dibujos muy grandes o los gráficos de escena que se generan únicamente en tiempo de ejecución (como sucede en los programas de renderizado con trazado de rayos ) requieren la definición de nodos de grupo de una manera más automatizada. Un trazador de rayos, por ejemplo, tomará una descripción de escena de un modelo 3D y creará una representación interna que divide sus partes individuales en cuadros delimitadores (también llamados bloques delimitadores). Estos cuadros se agrupan jerárquicamente para que las pruebas de intersección de rayos (como parte de la determinación de la visibilidad) se puedan calcular de manera eficiente. Un cuadro de grupo que no intersecta un rayo ocular, por ejemplo, puede omitir por completo la prueba de cualquiera de sus miembros.
Una eficacia similar se aplica también a las aplicaciones 2D. Si el usuario ha ampliado un documento de modo que solo una parte de él sea visible en la pantalla de su ordenador y luego se desplaza por él, resulta útil utilizar un cuadro delimitador (o en este caso, un esquema de rectángulo delimitador) para determinar rápidamente qué elementos del gráfico de escena son visibles y, por lo tanto, es necesario dibujarlos.
Según las particularidades del rendimiento de dibujo de la aplicación, una gran parte del diseño del gráfico de escena puede verse afectado por consideraciones de eficiencia de renderizado. En los videojuegos 3D como Quake , los árboles de partición espacial binaria (BSP) son muy preferidos para minimizar las pruebas de visibilidad. Sin embargo, los árboles BSP tardan mucho tiempo en calcularse a partir de los gráficos de escena de diseño y deben volver a calcularse si el gráfico de escena de diseño cambia, por lo que los niveles tienden a permanecer estáticos y los personajes dinámicos generalmente no se consideran en el esquema de partición espacial.
Los gráficos de escena para objetos regulares densos, como campos de altura y mallas poligonales, tienden a emplear árboles cuádruples y octrees , que son variantes especializadas de una jerarquía de cuadros delimitadores 3D. Dado que un campo de altura ocupa un volumen de cuadro en sí mismo, la subdivisión recursiva de este cuadro en ocho subcuadros (de ahí el "oct" en octree) hasta que se alcancen los elementos individuales del campo de altura es eficiente y natural. Un árbol cuádruple es simplemente un octree 2D.
PHIGS fue la primera especificación comercial de gráficos de escena y se convirtió en un estándar ANSI en 1988. Los proveedores de hardware Unix proporcionaron implementaciones dispares . El sistema de gráficos 3D HOOPS parece haber sido la primera biblioteca comercial de gráficos de escena proporcionada por un solo proveedor de software. Fue diseñado para ejecutarse en diferentes interfaces 2D y 3D de nivel inferior, y la primera versión de producción importante (v3.0) se completó en 1991.
Silicon Graphics (SGI) lanzó OpenGL Performer , más comúnmente llamado Performer, en 1991, que fue el sistema principal de gráficos de escena para la mayoría de los productos de SGI en el futuro. SGI lanzó IRIS Inventor 1.0 (1992), que era un gráfico de escena de alto nivel creado sobre Performer. Le siguió Open Inventor en 1994, otra iteración del gráfico de escena de alto nivel creado sobre las versiones más nuevas de Performer. Se pueden encontrar más bibliotecas de gráficos de escena 3D en Categoría:API de gráficos de escena 3D .
X3D es un formato de archivo de estándares abiertos y libre de regalías y una arquitectura de tiempo de ejecución para representar y comunicar escenas y objetos 3D mediante XML . Es un estándar ratificado por ISO que proporciona un sistema para el almacenamiento, la recuperación y la reproducción de contenido gráfico en tiempo real integrado en aplicaciones, todo dentro de una arquitectura abierta para admitir una amplia gama de dominios y escenarios de usuario.