Un gráfico de escena es una estructura de datos general comúnmente utilizada por aplicaciones de edición de gráficos basados en vectores y juegos de computadora 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 estructura de árbol . Un nodo de árbol puede tener muchos hijos pero solo un padre, con el efecto de padre aplicado 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 (ver también transformación y matriz ) en cada nivel de grupo y concatenar dichas matrices es una forma eficiente y natural de procesar tales operaciones. Una característica común, por ejemplo, es la capacidad de agrupar formas y objetos relacionados en un objeto compuesto que luego puede manipularse tan fácilmente como un solo objeto.
En la edición de gráficos basada en vectores, cada nodo de hoja en un gráfico de escena representa alguna unidad atómica del documento, generalmente una forma como una elipse o una ruta Bézier . Aunque las formas mismas (particularmente los caminos) se pueden descomponer aún más en nodos como 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 e impulsado por el usuario es la capa . Una capa actúa como una hoja transparente sobre la que se pueden colocar cualquier número de formas y grupos de formas. Luego, el documento se convierte en un conjunto de capas, cualquiera de las cuales puede hacerse invisible, atenuada o bloqueada (convertida en de sólo lectura). Algunas aplicaciones colocan todas las capas en una lista lineal, mientras que otras admiten capas dentro de capas hasta cualquier profundidad deseada.
Internamente, puede que no haya ninguna diferencia estructural real entre capas y grupos, ya que ambos son solo 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 escenas son útiles para juegos modernos que utilizan gráficos 3D y mundos o niveles cada vez más grandes. En tales aplicaciones, los nodos en un gráfico de escena (generalmente) representan entidades u objetos en la escena.
Por ejemplo, un juego podría definir una relación lógica entre un caballo y un caballo de modo que el caballo se considere una extensión del caballo. El gráfico de escena tendría un nodo de "caballo" con un nodo de "caballero" adjunto.
El gráfico de escena también puede describir la relación espacial, así como lógica, de las distintas entidades: el caballero se mueve a través del espacio 3D mientras el caballo se mueve.
En estas aplicaciones de gran tamaño, los requisitos de memoria son consideraciones importantes al diseñar un gráfico de escena. Por esta razón, muchos sistemas de gráficos de escenas de gran tamaño utilizan 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 reducir el presupuesto de memoria y aumentar la velocidad, ya que cuando se crea un nuevo nodo caballero, no es necesario duplicar los datos de apariencia.
La forma más simple de gráfico de escena utiliza una estructura de datos de matriz o lista vinculada , y mostrar sus formas es simplemente una cuestión de iterar linealmente los nodos uno por uno. Otras operaciones comunes, como verificar qué forma se cruza con el puntero del mouse, también se realizan mediante búsquedas lineales. Para gráficos de escenas pequeñas, esto suele ser suficiente.
Aplicar una operación en un gráfico de escena requiere alguna forma de distribuir una operación según el 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 de vectores, cuaterniones o ángulos de Euler . Después de lo cual, un nodo hoja envía el objeto para su renderización al renderizador. Algunas implementaciones pueden representar el objeto directamente, lo que invoca la API de representación subyacente , como DirectX u OpenGL . Pero dado que la implementación subyacente de la API de renderizado generalmente carece de portabilidad, en su lugar se podrían separar el gráfico de escena y los sistemas de renderizado. 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. Alternativamente, se puede utilizar el patrón de visitante . Esto tiene una desventaja similar: es igualmente difícil agregar nuevos tipos de nodos.
Otras técnicas implican el uso de RTTI ( Información de tipo de tiempo de ejecución ). La operación se puede realizar como una clase que se pasa al nodo actual; luego consulta el tipo de nodo usando RTTI y busca la operación correcta en una serie de devoluciones de llamada o functores . Esto requiere que el mapa de tipos de devoluciones de llamada o functores se inicialice en tiempo de ejecución, pero ofrece más flexibilidad, velocidad y extensibilidad.
Existen variaciones de estas técnicas y nuevos métodos pueden ofrecer beneficios adicionales. Una alternativa es la reconstrucción del gráfico de escena, donde el gráfico de escena se reconstruye para cada una de las operaciones realizadas. Esto, sin embargo, puede ser muy lento, pero produce un gráfico de escena altamente optimizado. Demuestra que una buena implementación de un gráfico de escena depende en gran medida de la aplicación en la que se utiliza.
Los recorridos son la clave del poder de aplicar operaciones a gráficos de escena. Un recorrido generalmente consiste en comenzar en algún 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 renderizado se aplican una tras otra) y moverse recursivamente hacia abajo en el gráfico de escena (árbol). ) a los nodos secundarios, hasta llegar a un nodo hoja. En este punto, muchos motores de gráficos de escenas regresan al árbol y aplican una operación similar. Por ejemplo, considere una operación de renderizado que tenga en cuenta las transformaciones: mientras se recorre recursivamente hacia abajo la jerarquía del gráfico de escena, se llama a una operación previa al renderizado. 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 atravesar todos los hijos de un nodo, llama a la operación posterior al renderizado 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 necesaria ]
Algunas operaciones de gráficos de escena son en realidad más eficientes cuando los nodos se atraviesan en un orden diferente; aquí es donde algunos sistemas implementan la reconstrucción de gráficos de escena para reordenar el gráfico de escena en un formato o árbol más fácil de analizar.
Por ejemplo, en casos 2D, los gráficos de escena normalmente se representan a sí mismos comenzando en el nodo raíz del árbol y luego dibujando recursivamente los nodos secundarios. Las hojas del árbol representan los objetos más destacados. Dado que el dibujo se realiza de atrás hacia adelante y los objetos más cercanos simplemente sobrescriben los más lejanos, el proceso se conoce como empleo del algoritmo de Painter . En los sistemas 3D, que a menudo emplean buffers 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 renderizarse realmente, porque están ocluidos por objetos más cercanos.
Las jerarquías de volumen delimitador (BVH) son útiles para numerosas tareas, incluida la selección eficiente y la aceleración de la detección de colisiones entre objetos. Un BVH es una estructura espacial, pero no tiene que 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 estrechamente un solo objeto (o posiblemente incluso una fracción más pequeña de un objeto en BVH de alta resolución). A medida que uno asciende en la jerarquía, cada nodo tiene su propio volumen que abarca estrechamente 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 intersecta un volumen superior en el árbol, no puede intersectar ningún objeto debajo de ese nodo (por lo que todos se rechazan muy rápidamente).
Existen algunas similitudes entre los BVH y los gráficos de escenas. 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 hay un "nodo vinculado" especialmente diseñado agregado en una ubicación conveniente de 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 ventajas.
Una forma eficaz de combinar la partición espacial y los gráficos de escena es crear un nodo de hoja de escena que contenga los datos de la partición espacial. [ se necesita aclaración ] Esto puede aumentar la eficiencia computacional del renderizado.
Los datos espaciales suelen ser estáticos y generalmente contienen datos de escenas inmóviles en alguna forma particionada. [ se necesita aclaración ] Algunos sistemas pueden tener los sistemas y su representación por separado. Esto está bien y ninguno de los métodos tiene ventajas reales. 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. [ la neutralidad está en disputa ]
Los dibujos muy grandes, o gráficos de escenas que se generan únicamente en tiempo de ejecución (como ocurre 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 construirá una representación interna que dividirá sus partes individuales en cuadros delimitadores (también llamados losas delimitadoras). Estos cuadros están agrupados jerárquicamente para que las pruebas de intersección de rayos (como parte de la determinación de la visibilidad) puedan calcularse de manera eficiente. Un cuadro de grupo que no cruza un rayo ocular, por ejemplo, puede omitir por completo la prueba de cualquiera de sus miembros.
Una eficiencia similar también se aplica en aplicaciones 2D. Si el usuario ha ampliado un documento para que sólo una parte sea visible en la pantalla de su computadora y luego se desplaza por él, es útil usar un cuadro delimitador (o en este caso, un esquema de rectángulo delimitador) para determinar rápidamente qué escena Los elementos del gráfico son visibles y, por lo tanto, es necesario dibujarlos.
Dependiendo de los detalles 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 videojuegos 3D como Quake , se prefieren los árboles de partición de espacio binario (BSP) para minimizar las pruebas de visibilidad. Sin embargo, los árboles BSP tardan mucho tiempo en calcularse a partir de los gráficos de la escena de diseño y deben recalcularse si el gráfico de la escena de diseño cambia, por lo que los niveles tienden a permanecer estáticos y los caracteres 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 octárboles , que son variantes especializadas de una jerarquía de cuadros delimitadores 3D. Dado que un campo de altura ocupa un volumen de caja en sí, subdividir recursivamente esta caja en ocho subcajas (de ahí el 'oct' en octree) hasta alcanzar elementos individuales del campo de altura es eficiente y natural. Un quadtree es simplemente un octree 2D.
PHIGS fue la primera especificación comercial de gráficos de escenas 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 escenas proporcionada por un único proveedor de software. Fue diseñado para ejecutarse en interfaces 2D y 3D de nivel inferior dispares, y la primera versión de producción principal (v3.0) se completó en 1991.
Silicon Graphics (SGI) lanzó OpenGL Performer o más comúnmente llamado Performer en 1991, que fue el principal sistema de gráficos de escena para la mayoría de los productos SGI en el futuro. SGI lanzó IRIS Inventor 1.0 (1992), que era un gráfico de escena de alto nivel construido sobre Performer. Le siguió Open Inventor en 1994, otra iteración del gráfico de escena de alto nivel construido sobre las versiones más recientes de Performer. Se pueden encontrar más bibliotecas de gráficos de escenas 3D en Categoría: API de gráficos de escenas 3D .
X3D es un formato de archivo de estándares abiertos y una arquitectura de tiempo de ejecución libre de regalías para representar y comunicar escenas y objetos 3D mediante XML . Es un estándar ratificado por ISO que proporciona un sistema para el almacenamiento, recuperación y 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.