Un gráfico de escena es una estructura de datos general utilizada comúnmente 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 un 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 la concatenación de dichas matrices juntas es una forma eficaz 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 puede manipularse tan fácilmente como un solo objeto.
Gráficos de escena en herramientas de edición de gráficos
En la edición de gráficos basada en vectores, cada nodo hoja en un gráfico de escena representa alguna 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 aún más 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 e impulsado por el usuario es la capa . Una capa actúa como una hoja transparente sobre la que se puede colocar cualquier número de formas y grupos de formas. El documento se convierte entonces en un conjunto de capas, cualquiera de las cuales puede hacerse invisible, atenuarse o bloquearse convenientemente (convertirse en solo lectura). Algunas aplicaciones colocan todas las capas en una lista lineal, mientras que otras admiten capas dentro de capas a la 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 hacer 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.
Gráficos de escena en juegos y aplicaciones 3D
Los gráficos de escena son útiles para juegos modernos que utilizan gráficos en 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 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 la escena también puede describir la relación espacial, así como la lógica, de las diversas entidades: el caballero se mueve a través del espacio 3D como se mueve el caballo.
En estas grandes aplicaciones, los requisitos de memoria son consideraciones importantes al diseñar un escenario gráfico. Por esta razón, muchos sistemas de gráficos de escena grandes 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 separado, pero se instancia la representación gráfica del caballero (compuesta por una malla 3D, texturas, materiales y sombreadores). Esto significa que solo se guarda una única copia de los datos, que luego es referenciada por cualquier nodo '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.
Implementación de gráficos de escena
La forma más simple de gráfico de escena usa una matriz o una estructura de datos de 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 escena pequeños, esto suele ser suficiente.
Operaciones y despacho de gráficos de escena
La aplicación de una operación en un gráfico de escena requiere alguna forma de distribuir 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 por multiplicación de matrices, desplazamiento de vector, cuaterniones o ángulos de Euler . Después de lo cual, un nodo hoja envía el objeto para renderizarlo en el 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, uno podría separar el gráfico de escena y los sistemas de renderizado. Para lograr este tipo de envío, se pueden tomar 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 simples de escribir, pero generalmente 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 en el sentido de que 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 del nodo usando RTTI y busca la operación correcta en una matriz de devoluciones de llamada o functors . Esto requiere que el mapa de tipos a devoluciones de llamada o functores se inicialice en tiempo de ejecución, pero ofrece más flexibilidad, velocidad y extensibilidad.
Existen variaciones en estas técnicas y los nuevos métodos pueden ofrecer beneficios adicionales. Una alternativa es la reconstrucción del escenario gráfico, donde el escenario gráfico 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. Demuestra que una buena implementación de gráficos de escena depende en gran medida de la aplicación en la que se utiliza.
Recorridos
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 las operaciones (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 ) a los nodos secundarios, hasta que se alcanza un nodo hoja. En este punto, muchos motores de gráficos de escena luego retroceden por el árbol, aplicando una operación similar. Por ejemplo, considere una operación de renderizado que tenga en cuenta las transformaciones: mientras se recorre recursivamente la jerarquía del gráfico de escena, se llama a una operación de renderizado previo. 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 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 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 de forma recursiva los nodos secundarios. Las hojas del árbol representan la mayoría de los objetos en primer plano. Dado que el dibujo procede de atrás hacia adelante con objetos más cercanos simplemente sobrescribiendo los más lejanos, el proceso se conoce como emplear el algoritmo del pintor . En los sistemas 3D, que a menudo emplean zonas de influencia 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.
Gráficos de escena y jerarquías de volumen delimitador (BVH)
Las jerarquías de volumen límite (BVH) son útiles para numerosas tareas, incluida la eliminació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 división espacial a continuación).
Un BVH es un árbol de volúmenes delimitadores (a menudo esferas, cuadros delimitadores alineados con el eje 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 solo objeto de manera ajustada (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 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 se cruza con un volumen más alto en el árbol, no puede cruzarse con 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 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" especialmente diseñado 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 hay ventajas de incluir un BVH en un gráfico de escena.
Gráficos de escena y particiones espaciales
Una forma eficaz de combinar la partición espacial y los gráficos de escena es crear un nodo hoja de escena que contenga los datos de la partición espacial. [ aclaración necesaria ] Esto puede aumentar la eficiencia computacional del renderizado.
Los datos espaciales suelen ser estáticos y, por lo general, contienen datos de escenas que no se mueven en alguna forma particionada. [ aclaración necesaria ] Algunos sistemas pueden tener los sistemas y su representación por separado. Esto está bien y no hay ventajas reales para ninguno de los métodos. En particular, es malo tener el escenario gráfico contenido dentro del sistema de partición espacial, ya que el escenario gráfico se considera mejor como el sistema más grandioso de la partición espacial. [ se disputa 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 de trazado de rayos ) requieren la definición de nodos de grupo de una manera más automatizada. Un raytracer, por ejemplo, tomará una descripción de la escena de un modelo 3D y construirá una representación interna que dividirá sus partes individuales en cuadros delimitadores (también llamados losas delimitadores). 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) se puedan calcular de manera eficiente. Un cuadro de grupo que no se cruza con un rayo ocular, por ejemplo, puede omitir por completo la prueba de cualquiera de sus miembros.
Una eficiencia similar se mantiene también en aplicaciones 2D. Si el usuario ha ampliado un documento para que solo una parte de él sea visible en la pantalla de su computadora y luego se desplaza en é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 los videojuegos 3D como Quake , los árboles de partición de espacio binario (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 caracteres dinámicos generalmente no se consideran en el esquema de partición espacial.
Escenarios gráficos para los objetos regulares densos, como campos de alturas y mallas poligonales tienden a emplear quadtrees y octrees , que son variantes de una jerarquía cuadro delimitador 3D especializados. Dado que un campo de altura ocupa un volumen de caja en sí mismo, subdividir recursivamente esta caja en ocho subcajas (de ahí el 'oct' en octárbol) hasta que se alcanzan los elementos individuales del campo de altura es eficiente y natural. Un quadtree es simplemente un octárbol 2D.
Estándares
PHIGS
PHIGS fue la primera especificación de gráficos de escena comercial y se convirtió en un estándar ANSI en 1988. Los proveedores de hardware Unix proporcionaron implementaciones distintas. El sistema de gráficos 3D HOOPS parece haber sido la primera biblioteca de gráficos de escena comercial 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.
SGI
Silicon Graphics (SGI) lanzó OpenGL Performer o más comúnmente llamado Performer en 1991, que fue el principal sistema de gráficos de escenas para la mayoría de los productos SGI en el futuro. IRIS Inventor 1.0 (1992) fue lanzado por SGI, que era un gráfico de escena de alto nivel construido sobre Performer. Fue seguido con 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
X3D es un formato de archivo de estándares abiertos libre de regalías y una arquitectura en 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, 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.
Ver también
- Gráfico (estructura de datos)
- Teoría de grafos
- Partición del espacio
- Árbol (estructura de datos)
Referencias
Libros
- Leler, Wm y Merry, Jim (1996) 3D con HOOPS , Addison-Wesley
- Wernecke, Josie (1994) El mentor del inventor: Programación de gráficos 3D orientados a objetos con Open Inventor , Addison-Wesley, ISBN 0-201-62495-8 (Versión 2)
Artículos
- Bar-Zeev, Avi. "Scenegraphs: Pasado, Presente y Futuro"
- Carey, Rikk y Bell, Gavin (1997). "Manual de referencia de VRML 97 anotado"
- James H. Clark (1976). "Modelos geométricos jerárquicos para algoritmos de superficie visible" . Comunicaciones de la ACM . 19 (10): 547–554. doi : 10.1145 / 360349.360354 .
- Helman, Jim; Rohlf, John (1994). "IRIS Performer: un conjunto de herramientas de multiprocesamiento de alto rendimiento para gráficos 3D en tiempo real"
- PEXTimes : "Extraoficialmente, la extensión PHIGS a X. Oficialmente, PEX no era un acrónimo".
- Strauss, Paul (1993). "IRIS Inventor, un kit de herramientas de gráficos 3D"
enlaces externos
- Java3D
- Aviatrix3D
- LG3D
- OpenSG
- IRISPerformer
- OpenSceneGraph
- Biblioteca de visualización