Un gráfico de escena es una estructura de datos utilizada principalmente en editores de gráficos vectoriales y juegos de computadora . Ejemplos de tales programas incluyen Acrobat 3D, Adobe Illustrator , AutoCAD , CorelDRAW , OpenSceneGraph , VRML97 y X3D .
Un escenario gráfico representa una estructura que contiene una representación lógica y a menudo (pero no necesariamente) espacial de una escena gráfica. La definición de un gráfico de escena es confusa porque los programadores que lo implementan en las aplicaciones, y en particular en la industria del desarrollo de juegos, toman los principios básicos y los adaptan para su aplicación en aplicaciones específicas. Esto significa que no hay acuerdo sobre cuál debería ser el escenario gráfico.
Un gráfico de escena es un conjunto de nodos en una estructura como un gráfico o un árbol . Un nodo de árbol (en la estructura de árbol límite de un gráfico de escena) puede tener muchos hijos, pero a menudo solo un padre, y la acción del padre se extiende a todos sus nodos hijos; el efecto de una acción realizada sobre un grupo se distribuye automáticamente a todos sus elementos. En muchos programas, asociar una matriz de transformación (ver también transformaciones y matrices) al nivel de cualquier grupo y multiplicar dichas matrices es una forma eficiente y natural de manejar tales operaciones. Una característica común, por ejemplo, es la capacidad de agrupar formas/objetos relacionados en un objeto compuesto que se puede mover, transformar, seleccionar, etc. tan fácilmente como un solo objeto.
También a veces sucede que en algunos escenarios gráficos un nodo puede estar vinculado a cualquier otro nodo, incluido él mismo, o al menos contiene una extensión que hace referencia a otro nodo (por ejemplo, PhotoRealistic RenderMan de Pixar gracias al algoritmo de renderizado de Reyes y Acrobat 3D de Adobe Systems gracias a las manipulaciones interactivas mejoradas).
En los editores de gráficos vectoriales, cada nodo de hoja del gráfico de escena representa alguna unidad de documento indivisible, generalmente una forma como una elipse o una ruta Bézier. Aunque las formas en sí mismas (particularmente las rutas) se pueden descomponer en elementos tales como nodos spline, en la práctica es más conveniente pensar en el escenario gráfico como formas que no descienden a un nivel de representación más bajo.
Otro concepto de nodo útil y definido por el usuario es la capa. Actúa como una hoja transparente en la que se pueden colocar cualquier número de formas y sus grupos. Luego, el documento se convierte en un conjunto de capas, cada una de las cuales se puede hacer invisible, translúcida o bloqueada (solo lectura) según sea necesario. Algunas aplicaciones organizan todas las capas en una lista lineal, mientras que otras admiten subniveles (es decir, capas dentro de capas de cualquier nivel de anidamiento deseado).
Puede que no haya ninguna diferencia inherente en la estructura entre las capas y los grupos, ya que tanto las capas como los grupos son solo nodos en el escenario gráfico. Si se necesitaran diferencias, se declararía una clase de nodo genérico usando la declaración de tipo genérico de C++ y luego las capas y los grupos se heredarían como subclases. La visibilidad de un elemento, por ejemplo, sería una propiedad de la capa, pero no necesariamente del grupo.
El gráfico de escena es útil en los juegos modernos que usan gráficos 3D y mundos y niveles enormes en constante crecimiento. En tales aplicaciones, los nodos de gráficos de escena (generalmente) representan entidades u objetos en la escena.
Por ejemplo, un juego puede definir una relación lógica entre un caballero y un caballero, tratando así al caballero como una extensión del caballero. El escenario gráfico tendría un nodo "caballo" con un nodo "caballero" asociado.
Además de describir relaciones lógicas, el escenario gráfico también puede describir las relaciones espaciales de varias entidades: el caballero se mueve a través del espacio tridimensional junto con el caballo. En aplicaciones tan grandes, los requisitos de memoria son críticos durante el diseño de escenarios gráficos. Por esta razón, muchos sistemas con grandes escenarios gráficos utilizan la clonación para ahorrar memoria y aumentar la velocidad. En el ejemplo anterior, cada caballero es un nodo de escena independiente, pero su representación gráfica (que consta de una malla 3D, texturas, materiales y sombreadores) está clonada. Esto significa que los datos solo se almacenan en una sola instancia, a la que luego hacen referencia todos los nodos de caballero del escenario gráfico. Esto reduce los requisitos de memoria y aumenta la velocidad, ya que al crear un nuevo nodo de caballero, no es necesario duplicar la información de apariencia.
La forma más simple de un gráfico de escena utiliza una matriz o una estructura de datos de lista enlazada, y la visualización de sus formas es solo una iteración secuencial de los nodos uno por uno. Otras operaciones comunes, como determinar qué forma se cruza con el cursor del mouse (por ejemplo, en aplicaciones basadas en GUI) también se realizan mediante búsqueda lineal. Para gráficos de escena pequeños, esto suele ser suficiente.
Los gráficos de escena más grandes conducen a una ralentización notable en las operaciones lineales, por lo que se utilizan estructuras más complejas para almacenar datos básicos, la forma más popular y común es un árbol. En estos gráficos de escena, el patrón de diseño compuesto a menudo se diseña para crear una representación jerárquica de nodos de grupo y nodos de hoja. Los nodos agrupados pueden tener cualquier número de nodos secundarios adjuntos. Los nodos agrupados incluyen nodos de transformación y nodos de conmutación. Los nodos hoja son nodos que en realidad se renderizan o nodos que muestran el resultado de alguna acción. Estos incluyen objetos, sprites, sonidos, luces y cualquier cosa que pueda considerarse "representable" en algún sentido abstracto.
La aplicación de operaciones a un gráfico de escena requiere alguna forma de reenviar la operación según el tipo de nodo. Por ejemplo, en el caso de la representación, un nodo de transformación de grupo acumularía información de transformación mediante multiplicaciones de matrices, desplazamientos de vectores, cuaterniones o ángulos de Euler. Después de eso, el nodo hoja envía el objeto para renderizar. En algunas implementaciones, la representación se puede realizar directamente mediante la API de representación utilizada, como DirectX u OpenGL. Pero, dado que la API de la implementación utilizada suele generar dificultades para migrar a otras plataformas, es posible separar el escenario gráfico y el sistema de renderizado. Para lograr este tipo de transferencia, se pueden tomar varios enfoques.
En lenguajes orientados a objetos como C++, esto se hace fácilmente con funciones virtuales, cada una de las cuales representa una operación que se puede aplicar a un nodo. Las funciones virtuales son fáciles de escribir, pero normalmente no es posible agregar nuevas operaciones sin acceso al código fuente. Como alternativa, se puede utilizar el patrón de diseño Visitante. Pero este enfoque no deja de tener el mismo inconveniente debido a la imposibilidad de agregar nuevos tipos de nodos.
Otros métodos utilizan 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 la información del tipo de nodo mediante RTTI y busca la operación correcta en una matriz de devoluciones de llamada o funtores. Esto requiere que se inicialice una matriz asociativa de devolución de llamada o tipos de funtor en tiempo de ejecución, pero proporciona más flexibilidad, velocidad y extensibilidad. Existen variaciones de estos métodos y los nuevos métodos pueden ofrecer beneficios adicionales. Una de esas opciones es reconstruir el escenario gráfico durante cada una de las operaciones ejecutables. Esto da como resultado una velocidad más lenta y un gráfico de escena bien optimizado. Esto demuestra que una buena implementación de un escenario gráfico depende en gran medida de la aplicación en la que se utilice.
Tipos de omisiónEl recorrido del gráfico de escena es un punto clave para lograr el rendimiento de la aplicación de operaciones a los gráficos de escena. Un recorrido generalmente consiste en un nodo de inicio arbitrario (a menudo el nodo raíz del escenario gráfico), la aplicación de una operación u operaciones (a menudo, las operaciones de actualización y representación se aplican una tras otra) y se mueve recursivamente hacia abajo en el escenario gráfico (árbol). a los nodos secundarios hasta que se alcance un nodo hoja. Después de eso, muchas herramientas de gestión de escenarios gráficos atraviesan el árbol en la dirección opuesta, aplicando una operación similar. Por ejemplo, considere una operación de representación que recibe información: durante un recorrido descendente recursivo de la jerarquía del escenario gráfico, se invoca la operación que precede a la representación. Si el nodo es un nodo de transformación, agrega su propia información de transformación a la matriz de transformación actual. Una vez que la operación termina de atravesar todos los nodos secundarios, llama a la operación que sigue al procesamiento, de modo que el nodo de transformación pueda deshacer la transformación. Este enfoque reduce drásticamente el número de multiplicaciones de matrices requeridas.
Algunas operaciones de gráficos de escena son en realidad más eficientes cuando los nodos se recorren en un orden diferente, como cuando algunos sistemas aplican la reconstrucción del gráfico de escena para convertirlo en un formato o árbol más analizable.
En el caso 2D, por ejemplo, el gráfico de escena generalmente se representa comenzando en el nodo raíz y luego representando recursivamente todos los nodos secundarios. Los nodos hoja representan los objetos más cercanos al observador. Debido a que el renderizado ocurre desde el fondo hacia el primer plano, con los objetos más cercanos superpuestos a los más lejanos, este proceso también se conoce como el "algoritmo del pintor". En los sistemas 3D que a menudo usan zonas de influencia de profundidad, es más eficiente dibujar primero los objetos más cercanos, ya que los objetos distantes a menudo solo necesitan recortarse en lugar de renderizarse porque están cubiertos por objetos más cercanos.
Las jerarquías de volumen delimitador (BVH) son útiles para una serie de tareas, incluido el recorte eficiente y la detección rápida de colisiones entre objetos. La jerarquía de volúmenes delimitadores es una estructura espacial, sin embargo, no requiere partición geométrica (ver más abajo sobre partición espacial).
Una jerarquía de volúmenes delimitadores es un árbol de volúmenes delimitadores (a menudo esferas, cuadros delimitadores alineados con el eje ( AABB ) o cuadros delimitadores orientados). En la parte inferior de esta jerarquía, el volumen delimitador es el tamaño mínimo necesario para contener exactamente un solo objeto (quizás incluso una pequeña parte del objeto en el caso de jerarquías de volumen delimitador de alta resolución). Subiendo por esta jerarquía, cada nodo tiene su propio volumen, lo cual es necesario para cubrir con precisión todos los volúmenes contenidos. El nodo raíz contiene un volumen que contiene todos los demás volúmenes del árbol (la escena completa).
Las jerarquías de volúmenes delimitadores son útiles para acelerar la detección de colisiones entre objetos. Si el volumen delimitador de un objeto no interseca con un volumen superior en la jerarquía del árbol, no puede intersecar con ningún objeto debajo de ese nodo (por lo que todos se descartan muy rápidamente).
Obviamente, existen muchas similitudes entre las jerarquías de volúmenes delimitadores y los gráficos de escena. El gráfico de escena se puede adaptar fácilmente para incluir o convertirse en una jerarquía de volúmenes delimitadores; si cada nodo tiene un volumen asociado o un "nodo de volumen" incorporado agregado a un lugar adecuado en la jerarquía. Esto puede diferir de un gráfico de escena típico, pero hay beneficios al incluir una jerarquía de volúmenes delimitadores en un gráfico de escena.
Una forma eficiente de combinar una partición de espacio y un gráfico de escena es crear un nodo de escena de hoja que contenga datos sobre la partición de espacio. Estos datos suelen ser estáticos y contienen datos sobre objetos no móviles en el nivel en alguna forma separada. Algunos sistemas pueden contener sistemas separados y su visualización. Esto es normal y no existen ventajas particulares en ninguno de los dos métodos. En particular, es una mala práctica almacenar el escenario gráfico en un sistema de partición espacial, ya que es mejor entender el escenario gráfico como un sistema por encima de la partición espacial.
En resumen: la partición del espacio está diseñada para acelerar significativamente el procesamiento y la representación del gráfico de escena.
La necesidad de renderizar muchos objetos o gráficos que se generan completamente en tiempo de ejecución (como sucede en los programas que utilizan ray tracing para renderizar) requiere la definición de grupos de nodos con automatización adicional. Un trazador de rayos, por ejemplo, tomará una descripción de un modelo 3D en una escena y compilará su representación interna dividiendo partes individuales en cuadros delimitadores. Se agrupan jerárquicamente para que la prueba de intersección de rayos (como parte del proceso de visibilidad) se pueda calcular de manera eficiente. Un cuadro de grupo que no se cruza con un rayo, por ejemplo, puede omitir por completo la verificación de todos sus componentes.
Se logra una eficiencia similar en aplicaciones bidimensionales. Si el usuario ha ampliado el documento para que solo una parte sea visible en la pantalla de la computadora y luego se desplaza dentro de esa parte, es útil usar un cuadro delimitador (o, en este caso, un cuadro delimitador) para determinar rápidamente qué los elementos del escenario gráfico son visibles y, por lo tanto, deben renderizarse.
Según el rendimiento de representación específico de una aplicación, la mayor parte del gráfico de escena se puede diseñar para adaptarse a ella. En los videojuegos 3D (como Quake), los árboles de partición de espacio binario (BSP) son los preferidos para minimizar el número de pruebas de visibilidad. Sin embargo, los árboles de partición espacial requieren mucho tiempo para calcular el esquema del gráfico de escena y deben volver a calcularse si el esquema del gráfico de escena cambia; por lo tanto, los niveles tienden a permanecer estáticos y los objetos dinámicos generalmente no se consideran en un esquema de división del espacio.
Los gráficos de escena para objetos de vértice densos regulares, como mapas de altura y mallas de polígonos, generalmente usan quadtrees y octrees, que son versiones especializadas de la jerarquía de cuadros delimitadores 3D. Debido a que el mapa de altura en sí ocupa un volumen delimitador, se divide recursivamente en ocho partes hasta que se alcanzan los elementos individuales del mapa de altura. Un quadtree es una versión bidimensional de un octtree.
PHIGS fue la primera especificación comercial para un gráfico de escena y se convirtió en un estándar ANSI en 1988. Los proveedores de hardware de Unix proporcionaron implementaciones bastante diferentes. El sistema de gráficos 3D HOOPS fue la primera biblioteca comercial de gráficos de escena de un solo proveedor de software. Estaba destinado a ejecutarse en interfaces 2D y 3D completamente diferentes, y la primera versión destinada a la distribución con un número principal de 3.0 se completó en 1991. Muy pronto, Silicon Graphics lanzó el sistema IRIS Inventor 1.0 (1992), que era un gráfico de escena. Construido sobre la API IRIS GL 3D. Le siguió en 1994 Open Inventor, un gráfico de escena multiplataforma construido sobre OpenGL.
X3D es un formato de archivo de estándares abiertos libre de regalías y una arquitectura de tiempo de ejecución para representar y comunicar escenas y objetos 3D mediante XML. Se adopta como un estándar ISO que proporciona un sistema para almacenar, recuperar y representar contenido gráfico en tiempo real integrado en las aplicaciones; todo dentro de una arquitectura abierta para admitir una amplia gama de aplicaciones y escenarios de usuario.