algoritmos de aceleración. (cap19 -rtr4)

Gonzalo Rey – 5.020.146-2

Algoritmos deaceleración.(Cap 19 - RTR4)

Computación Gráfica Avanzada 2020.

Ingeniería en Computación.

Facultad de Ingeniería – Universidad de la República.

Pedro Armijo 2

Temas:• Estructuras de datos espaciales.

• Técnicas de Culling.

• Nivel de Detalle.

• Renderizado de escenas

grandes.

INTRODUCCIÓN

Pedro Armijo 3

Introducción

INTRODUCCIÓN

• A la hora de hacer representaciones en tiempo real tenemos al menos estas

cuatro grandes metas de rendimiento:

o Mantener una alta tasa de frames por segundo.(60-90 fps suficientemente rápido)

o Alta definición y frecuencia de muestreo. (4K – 3840x2160 – 140-150PPI)

o Luz y materiales más realistas. (algoritmos pesados para lograrlo)

o Alta complejidad geométrica de las escenas.

• El frame rate, la resolución y el sombreado siempre se puede seguir complejizando,

pero no se obtienen significativos cambios para el coste que sugieren.

En cambio, la complejidad geométrica no tiene límite. A modo de ejemplo, el

render del Boeing 777 mostrado tiene más de 500.000.000 polígonos.

Pedro Armijo

Estructuras de datos espaciales

4Estructuras de datos espaciales

• Son estructuras que organizan la geometría en el espacio y son utilizadas para

acelerar las consultas sobre los objetos geométricos y relacionarlos.

Usualmente tienen una organización jerárquica, quedando representadas como árboles

y teniendo una naturaleza recursiva. Esto logra que muchas consultas pasen de ser

O(n) a O(log n) mejorando significativamente el rendimiento.

• La desventaja que tienen es su alto costo de construcción, que depende de la

cantidad de geometría y de la complejidad de la estructura. Sin embargo es un

foco de trabajo y están logrando reducirlo gracias a evaluación perezosa y

actualizaciones incrementales.

Pedro Armijo 5

Bounding Volume Hieranchies (BVH)


• Los volúmenes acotantes contienen conjuntos de objetos y son sencillos.

Usualmente pueden ser esferas, AABB´s o OBB´s.

La escena se organiza en un árbol donde en las hojas se encuentra la geometría

a ser renderizada. Cada nodo tiene un volumen acotante que encapsula todo el

sub-árbol. Esto quiere decir que el nodo raíz encapsula toda la escena.

También se pueden usar para escenas dinámicas, pero por lo general dejan de estar

balanceados y pierden eficiencia.

Pedro Armijo 6

Binary Space Partition Trees (BSP)


• El árbol se forma dividiendo el espacio en dos recursivamente.

Existen dos tipos:

Alineado a los ejes:

• Primero se encapsula toda la escena en un AABB y luego recursivamente se divide

en dos hasta alcanzar una condición para detenerse.

• Existen variantes en cuanto a la división, puede ser fija por la mitad de alguna

dimensión del AABB o puede desplazarse, logrando un árbol más balanceado, pero

teniendo que almacenar información extra.

Pedro Armijo 7Estructuras de datos espaciales

Alineado a los polígonos:

• En este caso, se selecciona un polígono como divisor y parte el espacio en dos.

Si otro polígono es intersecado por éste plano, se lo considera dos polígonos

diferentes, uno en cada mitad. En cada mitad del espacio nuevamente se selecciona

un divisor y se repite el proceso.

• La creación de este árbol es costosa, ya que seleccionar un buen polígono divisor

es fundamental, por lo tanto es más útil es escenas estáticas.

Tiene la propiedad de que de dado un punto de vista dado, la estructura puede ser

recorrida en orden (back to front o front to back).

Pedro Armijo

Octrees


• Nuevamente se contiene a la escena en un AABB pero se divide simultáneamente en

los tres ejes tomando como punto de división el centro de la caja, creando ocho

nuevas cajas. Es una estructura muy regular, lo cual tiene ventajas y desventajas.

• Por un lado, no requiere memoria extra para almacenar la posición de los planos,

pero por otro, al ser tan rígido, los planos pueden quedar en posiciones poco

convenientes.

• Quadtree es análogo a octree pero para 2D

Pedro Armijo

Representaciones Cache-Oblivious y Cache-Aware


• Como el salto entre el ancho de banda de la memoria y el poder de cómputo de las

CPU´s incrementa con el tiempo es inevitable pensar en diseñar algoritmos y

estructuras que consideren la caché.

Cache-Aware:

• Asume que el tamaño de los bloques de la caché es conocido y optimiza para esa

arquitectura. Por ejemplo, Ericson muestra como almacenar un nodo de un k-d tree

en 32 bits. Los dos bits menos significativos indican el tipo (interno indicando

en cual de los tres ejes está dividido u hoja). Si es una hoja los otros 30 son un

puntero a una lista de objetos. Si es interno representan un valor de división.

• Logrando así guardar 16 nodos de este tipo en un bloque de 64 bytes por ejemplo.

• La idea es mejorar el acceso a datos asegurándose de que el tamaño delas

estructuras sea coherente con la caché.

Pedro Armijo 10

Cache-Oblivious:


• Son diseñados para funcionar correctamente en cachés de cualquier tamaño y son

independientes de cualquier plataforma.

• Un ejemplo de Embde Boas es dado un árbol T de altura h, dividirlo recursivamente

hasta que un sub-árbol entre en la caché. Como los nodos del sub-árbol son cercanos

entre sí, respeta el principio de localidad y obtendrá una tasa alta de caché-hit.

Pedro Armijo

Scene Graphs


• Es una estructura similar a las anteriores, pero que contiene información extra,

ya sea texturas, transformaciones, nivel de detalle o cualquier información que sea

ocurrente.

• Las propiedades son puestas en nodos internos para aplicárselas a todo el sub-árbol

inferior, logrando generalizar. Incluso se puede representar animación aplicando

transformaciones.

• La estructura, gracias a que varios nodos pueden compartir hijos, se representa

como un directed acyclic graph (DAG). Esto permite instanciación, ahorrando en

réplicas de un mismo objeto.

Pedro Armijo

Técnicas de Culling

12Técnicas de Culling

• Son técnicas que permiten remover de la escena, porciones que no van a contribuir

en la imagen final. Sólo técnicas de culling en momento de representación serán

presentadas.

• Lo mejor es tratar de eliminar lo que es innecesario de manera temprana en el

rendering pipeline o incluso pre-computarla, para no gastar recursos

innecesariamente.

Pedro Armijo

Backface Culling


• Se tratan de no renderizar todos los triángulos de las caras posteriores de los

objetos, ya que (si la cámara no esta dentro del objeto y es opaco) no se verán.

• Para esto se determina si el triángulo esta de espaldas a la cámara o no, puede

hacerse observando que la numeración de los vértices sea en sentido anti horario o

viendo el signo del producto interno entre, un vector desde cualquier punto del

plano que contiene al triángulo hacia el observador y la normal del mismo.

Pedro Armijo

Clustered Backface Culling


• Esta técnica ofrece hacer el cálculo para saber si un grupo de triángulos está de

espaldas al punto de observación.

• Esto permite eliminar grandes porciones de objetos en conjunto, sin entrar en

detalle en cada triángulo, logrando mejorar la performance.

• Se utiliza el normal cone que se genera usando las normales de los triángulos

en cuestión y a partir de él y el punto de observación, puede determinarse si se

eliminan o no.

Pedro Armijo

View Frustrum Culling


• Se compara el BV de cada objeto con el view frustum. La gran ventaja es que al

ser sencillo el BV, la comparación es rápida. Si se encuentra completamente fuera,

se puede descartar, de lo contrario el contenido puede ser visible y debe ser

enviado a través del pipeline.

• Si usamos una estructura jerárquica, esta selección se puede hacer para grupos de

objetos y descartar sin adentrarse mucho en el árbol.

Pedro Armijo

Portal Culling


• Esta técnica nace de que los muros son

grandes objetos que interfieren en la

visibilidad, principalmente en interiores.

Cada vez que pasa el View Frustum por

un portal, ajusta sus dimensiones para

encajar por él.

• La escena se divide en celdas (usualmente habitaciones) que están conectadas por

portales (puertas y ventanas). Usualmente se usa un grafo de adyacencia para

representar que celdas son adyacentes.

Pedro Armijo

Detail and Small Triangle Culling


• Esta técnica se aprovecha de que pequeños detalles aportan poco a la imagen final,

sacrificando un poco de calidad por rendimiento. Por lo general se usa cuando el

usuario está en movimiento y se desactiva cuando se detiene.

• Un criterio es proyectar el BV del objeto en

el plano de proyección y estimar los pixeles

que ocupa. Si está por debajo de cierto número

definido, no se toma en cuenta.

• Otro es poner muestras en el centro de los

pixeles, y si el triángulo no cae sobre la

muestra, se elimina. Para hacer esto eficientemente,

Wihlidal presenta la siguiente ecuación:

Pedro Armijo

Occlusion Culling


• Es un método que evita procesar

objetos que no podemos ver

porque están detrás de otro/s.

Esto se resolvía en parte con

el z-buffer pero ésta es una

técnica más avanzada y

optimizada ya que evita enviar

los objetos a través del

rendering pipeline.

• Existen dos variantes

principales. Point-based es la

representación donde se utiliza

solo un punto de vista. Por otra

parte, en Cell-based se hace la

representación para una celda con

varias posiciones de vista.

Pedro Armijo

Pseudocódigo


• Notar que el rendimiento del

algoritmo es muy dependiente

del orden en que estén los

objetos almacenados, por lo

tanto ordenarlos front to back

sería muy conveniente.

Pedro Armijo

Occlusion Queries


• El usuario puede consultar a la GPU para averiguar si un conjunto de triángulos

está visible comparándolo al z-buffer. Este conjunto por lo general es un BV de un

objeto y si ninguno es visible, entonces puede ser ignorado para el resto del

pipeline.

• Cuando resulta estar tapado por otro objeto, terminamos ganando en rendimiento,

ya que no se tuvo que seguir procesando. Pero en cambio, si no se puede determinar

si esta completamente tapado o no, perdemos un poco performance, porque el testeo

resultó inútil.

• Por lo tanto, estaría bueno hacer esas consultas en objetos que potencialmente no

sean visibles. Por ejemplo Kovaleík y Sochor llevan las estadísticas en tiempo real

de occlusion. La cantidad de veces que fue encontrado tapado por otros objetos

infiere en que tan seguido se pregunte por él.

Pedro Armijo

Culling Systems


• Un sistema de culling trabaja en diversas granularidades como se ve en la imagen.

En cada paso, se pueden emplear una o varias técnicas de las mencionadas

anteriormente.

Como un cluster es geométricamente más pequeño que un objeto, se pueden usar las

mismas técnicas para éstos sin todavía trabajar a nivel de triángulo.

• Por ejemplo, se puede hacer culling de detalle, frustum, backface, y occlusion

en clusters.

Pedro Armijo 22Técnicas de Culling

• Luego de hacer el culling a nivel de cluster, se puede trabajar a nivel de

triángulo. Se le aplican las técnicas de culling deseadas y el conjunto de

triángulos resultante de los test anteriores, se compacta en una lista

minimal.

• La selección de que técnica aplicar en cada nivel es compleja y aún no se ha

descubierto la fórmula perfecta. Además muchas veces depende de la escena o de

la arquitectura a utilizar. Lo cierto es que actualmente se está trabajando

fuertemente en encontrar optimizar este apartado.

Pedro Armijo

Nivel de Detalle

23Nivel de Detalle

• La idea principal es usar modelos más sencillos de los objetos a medida que

contribuyen menos en la imagen final. Para reducir el trabajo invertido en

esta técnica, se realiza después de aplicar las técnicas de culling.

• También pueden ser usadas para mantener una tasa de fotogramas alta en

diferentes dispositivos.

Pedro Armijo 24Nivel de Detalle

• Otra ocasión donde participa el LOD (level of detail) es cuando hay

niebla, incluso pudiendo ignorar completamente el objeto a la hora del

representación si este se encuentra en niebla completamente opaca.

• El mecanismo se divide en tres etapas: generation, selection y switching.

Pedro Armijo

LOD Switching

25Nivel de Detalle

• El cambio entre modelos debe ser atenuado, ya que un cambio repentino puede ser

notorio por el usuario, generando disconformidad. A continuación veremos

diversas formas de cambio de modelo y sus características.

Discrete Geometry LOD:

• Se crean varios modelos del mismo objeto con distinta cantidad de primitivas y

se pueden almacenar en la memoria de la GPU para reutilizarse.

• El cambio entre modelos es repentino

por lo que de un frame a otro se

puede apreciar el cambio. A pesar de

no ser la mejor, es una técnica

sencilla y si el cambio se hace

cuando el objeto esta bastante lejos

del observador, puede disminuirse el

efecto negativo del cambio.


Blend LOD:

• Para atenuar el cambio repentino, propone extender el cambio linealmente en

un corto período de tiempo. La principal desventaja es que se están

renderizando dos modelos en vez de uno, pero se estima que será en

intervalos de tiempo muy reducidos y además es muy poco probable que se

dupliquen muchos objetos de la escena al mismo tiempo.

• La tarea de hacer el cambio no es sencilla, solo disminuir la opacidad del

modelo saliente mientras se incrementa la del entrante no genera un efecto

visualmente atractivo. Supongamos LOD2 entrante y LOD1 saliente.

• Giegl y Wimmer sugieren incorporar LOD2 de a poco aumentando su opacidad

hasta que la alcance completamente. Luego se establece como modelo actual y

de la misma manera se retira LOD1. El LOD que esté transparente debe ser

renderizado con z-test activado pero z-write desactivado.

• Scherzer y Wimmer evitan renderizar ambos LODs ya que actualizan uno por

frame y el que no, lo reutilizan del frame anterior.


Alpha LOD:

• Se puede utilizar junto

otras técnicas de LOD

Switching y propone que a

medida que la métrica usada

para la selección aumenta

(ej: distancia al

observador) disminuye la

transparencia del objeto

hasta el punto de

desaparecer y no necesita

ser mandado por el

rendering pipeline.

Pedro Armijo 28

CLOD y Geomorph LOD:

Nivel de Detalle

• Ambos usan la técnica de colapsar aristas para generar modelos simplificados.

Esto refiere a encoger la arista hasta que sus vértices se juntan y desaparece.

Al almacenar cada colapso, se puede revertir, pudiendo volver a complejizar los

modelos.

• De esta forma, al variar el criterio de selección, se puede definir una cantidad

de triángulos, definiendo un continous level of detail (CLOD). Entonces hay una

gran cantidad de modelos a disposición, cada uno con menos triángulos que su

vecino complejo.

• Por otra parte Geomorph LOD usa un conjunto discreto de simplificaciones. Al

pasar de un modelo complejo a uno simple, la posición de los vértices se

interpola entre la original y la del modelo simple. Al completar la transición,

se utiliza este último para representar el objeto.

Pedro Armijo

LOD Selection

29Nivel de Detalle

Este concepto es básicamente seleccionar que modelo renderizar y cuales mezclar.

Existe una métrica llamada benefit function evaluada desde el punto de vista

hacia el objeto en cuestión y permite decidir que modelo tomar. Por ejemplo

puede estar basada en la distancia al objeto o en el área proyectada de su BV.

El valor de retorno de esta función lo llamaremos r.

Range-based:

Es muy común asociar directamente el modelo a utilizar con la distancia de éste

al punto de vista. Se definen intervalos según el valor de la distancia que

parezcan convenientes y se le asocia a cada uno un modelo a renderizar.


Projected Area-Based:

Otra métrica popular es usar el área proyectada del BV del objeto para decidir

que modelo lo representa. Este área se puede estimar para los casos de esferas

y cajas. La desventaja es que a veces el BV no es tan representativo del objeto

y puede estar usándose un LOD más caro del debido.

Otros métodos de selección:

Además de los mencionados anterioremente, existe una amplia diversidad

métodos de selección.

Funkhouser y Séquin involucran en la benefit function la importancia del

objeto. Por ejemplo en un juego de fútbol, las miradas van a estar más

centralizadas en la zona cercana al balón, por lo cual objetos cercanos

probablemente requieran un modelo bastante detallado.

Pedro Armijo

Time-Critical LOD Rendering

31Nivel de Detalle

• Otra aplicación de LOD es para mantener el frame rate por encima de algún

valor esperado.

• En los sistemas de tiempo real hard, al transcurrir cierto tiempo, la tarea

debe ser terminada de manera estricta, no se puede seguir procesando.

• Muchas veces es preferible mostrar la escena completa usando modelos

simplificados, a dar una escena con pocos objetos detallados.

• Funkerhouser y Séquin dan un algoritmo que adapta la selección de LOD para

cada objeto a un frame rate constante, tratando de maximizar la calidad.

• Maximizar:

• Bajo la siguiente condición:

• Problema más sencillo:

Pedro Armijo

Renderizado de Escenas Grandes:

32Renderizado de Escenas Grandes

• No siempre la escena a renderizar entra completamente en la memoria principal

de la computadora. Por suerte existen técnicas que junto a todo lo visto hasta

ahora permiten completar la representación.

Pedro Armijo

Virtual Texturing and Straming

33Renderizado de Escenas Grandes

• Existen texturas suficientemente grandes como para no entrar en la memoria de la

GPU. Para poder trabajar con ellas se hace de la misma forma como se hace cuando

la CPU no tiene suficiente memoria para operar, se usa el disco como backing

store.

• Para obtener un sistema eficiente de texturas usando mipmaping, es requerido que

el número de texels necesario sea proporcional a la resolución de la imagen final

independientemente de la resolución de las texturas. Esto permite que solo los

texels visibles estén alojados en memoria de GPU.

Pedro Armijo 34Renderizado de Escenas Grandes

Texture Transcoding

• Este proceso consiste en que la

GPU obtenga las imágenes del disco

de forma comprimida (como JPEG).

• Las grandes ventajas de usar esta técnica son que un nivel más alto de

compresión puede ser alcanzado cuando las texturas están en el disco y que el

formato usado es compatible para la GPU al acceder a las texturas a través del

texture sampler.

Gracias!

Yo

Consultas

Fin

Fuente: Real Time Rendering

Edición°4 - Cap.19

Docentes:

Eduardo Fernández

Jose Pedro Aguerre

28/09/2020

algoritmos de aceleración. (cap19 -rtr4)

Documents