Los datos en 3D pueden ser muy complejos para representar en tiempo real



Descargar 20,92 Kb.
Fecha de conversión07.05.2017
Tamaño20,92 Kb.

Estrategias de Optimización

  • Visualización II – 2009
  • Ing. Juan P.D’Amato

Los datos en 3D pueden ser muy complejos para representar en tiempo real

  • Los datos en 3D pueden ser muy complejos para representar en tiempo real
  • Se necesita reducir la cantidad de triángulos a renderizar en la escena
  • Una solución, elegir los datos a representar
  • Otra solución, simplificar el modelo
    • Como evaluar la fidelidad de los modelos simplificados ?
  • >200,000 Triángulos

Frustum

  • Frustum
  • División del espacio
    • N-Trees, Grillas, Planos
  • LODS
    • Discreto, Continuo, View-Dependent
  • Otros métodos
  • Detección de colisiones

Relación Eficiencia del método con respecto a Eficiencia ganada

  • Relación Eficiencia del método con respecto a Eficiencia ganada
  • Espacio utilizado por las estructuras intermedias
  • Reacción ante cambios

La posicion y dirección de la vista genera un volumen -> El Frustum de Vista

  • La posicion y dirección de la vista genera un volumen -> El Frustum de Vista
  • Los elementos que nos interesan se deben encontrar dentro de este volumen

Estrategias de clasificación de los elementos para accederlos eficientemente

  • Estrategias de clasificación de los elementos para accederlos eficientemente
    • Grillas Regulares
    • N-Trees (Quadtrees / Octrees /Kd-Trees / BSP Trees )
    • Bounding volumes

Los BSP(Binary Space Partition) son una generalización de los kD-trees: los planos no necesariamente deben estar alineados a los ejes

  • Los BSP(Binary Space Partition) son una generalización de los kD-trees: los planos no necesariamente deben estar alineados a los ejes
  • Los elementos se clasifican por planos
  • El motor del Half Life 2 se basa en BSP

Para todos los triángulos T del Objeto

  • Para todos los triángulos T del Objeto
    • Hang(root, T)
    • Hang (node , triangle)
    • If (node.isLeaf)
      • Node.add(triangle)
    • else
      • Pos = classify ( node.plane, triangle)
      • If (pos = Front)
        • Hang(node.front,triangle)
      • Else
        • Hang(node.back, triangle)
  • Los elementos que nos interesan se deben encontrar dentro de este volumen

Render(node, eyePos)

  • Render(node, eyePos)
  • Pos = classify (node.plane, eyePos)
  • //estoy frente al plano
  • If (pos = Front)
    • Render(node.front, eyePos)
    • renderElements() <- chequea que son visibles
    • Render(node.back, eyePos)
  • Else
    • Render(node. back, eyePos)
    • renderElements()
    • Render(node. front, eyePos)

Es una grilla regular, organizada jerárquicamente

  • Es una grilla regular, organizada jerárquicamente
  • Se divide la escena en cuatro bloques, con dos planos alineados, y en forma recursiva
  • Se crea un árbol con cuatro nodos hijos

Número de bloques en un nivel:

  • Número de bloques en un nivel:
    • n(nivel) = 4nivel
  • Número total de bloques:
  • N(nivel) = 40 + 41 + 42 + … + 4nivel = (4 (nivel+1) – 1) / 3
  • El overhead final en comparación a una grilla regular:
    • 33% de bloqueas extras

Ventajas

Idea : solo procesar los bloques cercanos al observador.

  • Idea : solo procesar los bloques cercanos al observador.
  • Los bloques lejanos pueden eliminarse
  • La carga/descarga de los bloques varía de acuerdo a la posición de la cámara
  • El uso de memoria es constante

Ventajas:

  • Ventajas:
    • Es simple implementarlo con arreglos 2D, y también para llevarlo a 3D
  • Desventajas:
    • Sirve cuando la distribución en el espacio es homogénea
  • Ideal para organizar objetos en escenas

El espacio se divide por volúmenes

  • El espacio se divide por volúmenes
    • Se usan representaciones matemáticas simples(Esferas, cubos, prismas (boxes))
    • Los volúmenes pueden subdivirse en secciones más pequeñas
    • Usado generalmente con objetos completos
    • El bounding volume óptimo se calcula durante el pre-procesamiento
  • Lo más común es utilizarse en colisiones de objetos

Requiere dos datos únicamente:

AABB (Axis Aligned Bounded Box):

  • AABB (Axis Aligned Bounded Box):
    • Rápido para calcular las colisiones, pero no se adecuan perfectamente al objeto
    • AABB se re calcula cuando el objeto rota o se mueve

Los “convex hull” pueden utizarse

  • Los “convex hull” pueden utizarse
  • Es más costoso su manejo:
    • Rotación
    • Cálculo de intersección
    • Punto interno al volumen

Bounding boxes orientados (OBB) son más adecuados al objeto pero más costosos para hacer los cálculos:

  • Bounding boxes orientados (OBB) son más adecuados al objeto pero más costosos para hacer los cálculos:
    • Los OBBs para objetos estáticos pueden calcularse previamente
    • Alternativa : aplicar las mismas transformaciones que el objeto antes de aplicar los cálculos
  • Conclusión: balancear las diversas técnicas de BV

Ventajas:

  • Ventajas:
    • Cálculos simples
    • Requieren poco espacio en memoria (para la esfera es una posicion y un radio)
  • Desventajas
    • No tienen buena precisión
    • No reducen la cantidad de polígonos a representar

Para todos los objetos3D O de la escena

  • Para todos los objetos3D O de la escena
    • //Método abstracto de la clase Bound
    • If (O.bounding.insideFrustum()
      • O.Render
    • Else
      • Continue;

El problema:

  • El problema:
    • Conjuntos de datos pueden ser muy complejos para representar en tiempo real
  • Una solución:
    • Usar geometría mas simples de modelos pequeños o distantes.
    • Eso es lo conocido como Level of Detail or LOD

Crear levels of detail (LODs) de los objetos:

  • Crear levels of detail (LODs) de los objetos:
  • 69,451 polígonos
  • 2,502 p
  • 251 p
  • 76 p

Level of detail (LOD) es una herramienta para mantener la interacción

  • Level of detail (LOD) es una herramienta para mantener la interacción
    • Balancea la relación perfomance/fidelidad de las mallas
    • Puede usarse junto con otras técnicas:
      • Parallel rendering
      • Occlusion culling
      • Image-based rendering
  • Tipos principales de LOD
    • Discreto/sustitución (1976)
    • Continuo (1996)

LOD tradicional:

  • LOD tradicional:
    • Los LODs de cada objeto se crean previamente con una resolución determinada
    • En tiempo de ejecución se elije el LOD adecuado de acuerdo a la distancia (o por otro criterio)

Ventajas

  • Ventajas
    • Granularidad adecuada:
      • Utiliza los polígonos más representativos
      • La fidelidad es la más elevada
    • La mejor aproximación para objetos muy detallados
      • Permite simplificarlos drásticamente
  • Desventajas
    • Es costoso en tiempo real

Combinar con otras técnicas (BSP, Octree)

  • Combinar con otras técnicas (BSP, Octree)
  • Cuando usar esta técnica en la escena, y con qué objetos?
    • LOD discretos : objetos muy replicados y con un número razonable de polígonos
    • LOD continuo : Mapas, grillas de agua (espacios navegables y uniformes)

Texturas (mippmaps)

  • Texturas (mippmaps)

Utilizar texturas en lugar de triángulos

  • Utilizar texturas en lugar de triángulos
  • Se aplican mapas de normales (bumpmaps) calculados para recrear las “sombras” del elemento
  • Se puede automatizar el cálculo de los mapas de normales si la topología de la malla es relativamente simple
  • 1683 k Triangulos
  • 10 k Triangulos
  • 10 k Triangulos + Shading

Se tienen varias instancias del mismo objeto, del que solo cambian las transformaciones o atributos mínimos, como el color

  • Se tienen varias instancias del mismo objeto, del que solo cambian las transformaciones o atributos mínimos, como el color
  • Por cada nuevo objeto
    • Se hace referencia a la misma estructura de la geometría (vértices, triángulos, texturas )
    • Se crean las transformaciones propias a cada objeto

Renderizar el objeto a textura

  • Renderizar el objeto a textura
  • En el momento del render, se dibuja un polígono con la textura mapeada
  • Útil para objetos estáticos, como árboles o edificios
  • Técnicas
  • Pros
  • Cons
  • LOD
  • Discreto
  • Continuo
  • Jerárquico
  • En general, la visualización no depende de la técnica
  • No existe una técnica general
  • No es viable cuando los objetos se deforman
  • SP
  • Grillas
  • Quadtree/Octree
  • BSP
  • Genera una buena distribución de los elementos
  • El costo de búsquedas es de ln #Elementos
  • Mayor complejidad para visualizar
  • Las modificaciones tienen un costo elevado
  • Bound
  • Esferas
  • AABB
  • OBB
  • Sencilla
  • Conveniente para objetos deformables
  • Eficiente
  • No son dependientes de la visualización
  • Son malas aproximaciones

No provee estructuras tipo Octrees o BSP pero provee mecanismos para el manejo de datos

  • No provee estructuras tipo Octrees o BSP pero provee mecanismos para el manejo de datos
    • Estructuras + eficientes
    • LODs de Textura (Mippmaps)
    • Culling Queries
    • Splines variables en GPU (sólo en placas nuevas)
    • Planos de corte

Render :

  • Render :
  • // Cada cara es un triangulo
  • while (i
  • glBegin(GL_TRIANGLES)
  • glVertex3fv( Vertexes[ Faces[i] ])
  • glVertex3fv( Vertexes[ Faces[i+1] ])
  • glVertex3fv( Vertexes[ Faces[i+2] ])
  • i+=3
  • glEnd()

OffLine

  • OffLine
  • genLists(listID); //offline
  • while (i
  • glBegin(GL_TRIANGLES)
  • glVertex3fv( Vertexes[ Faces[i] ])
  • glVertex3fv( Vertexes[ Faces[i+1] ])
  • glVertex3fv( Vertexes[ Faces[i+2] ])
  • i+=3
  • glEnd()
  • Render
  • glCallList(listID);
  • -> transfer\Transfer.exe

La idea : Verificar que un objeto será dibujado en pantalla

  • La idea : Verificar que un objeto será dibujado en pantalla
    • 1ro.- Se renderizan objetos simples, tipo esferas o cajas
    • 2do.- Se leen cuantos píxeles afectaron del Buffer
    • Si la cantidad de pixeles > cota
      • 3ro.- Se renderiza la escena final
    • Código OpenGL :
    • // Deshabilito la profundidad
    • glDepthMask(GL_FALSE);
    • // Habilito el test de Occlusion
    • glEnable(GL_OCCLUSION_TEST_HP);
    • // Dibujo el Bounded
    • glutSolidCube(S_SIZE*2);
    • glDisable(GL_OCCLUSION_TEST_HP);
    • // Obtengo el resultado
    • glGetBooleanv(GL_OCCLUSION_TEST_RESULT_HP, @isVisible);
  • Detección de colisiones comprende encontrar donde dos (o más) primitivas se intersecan
  • Las colisiones pueden ser muy complejas

Los problemas principales:

  • Los problemas principales:
    • Una detección correcta requiere chequear cada polígono de un objeto con todos los del otro :
    • O(#polígonos2),
    • Calcular el tiempo en que se producirá una colisión
    • Encontrar el punto de intersección entre ambos

Detección de colisiones con Bounding Spheres. Eficiente para calcular si un punto p es interno

  • Detección de colisiones con Bounding Spheres. Eficiente para calcular si un punto p es interno
    • |p – Scentre| < Sradius
  • Detección de colisiones con bounding boxes alineados a los ejes (eng: AABB)
    • Intersección muy simple AABBs
    • Dados dos AABBs A & B, no existe intersección si:
      • (AXmax < BXmin) || // A totalmente a la izquierda B
      • (AXmin > BXmax) || // A totalmente a la derecha B
      • (AYmax < BYmin) || // A totalmente por debajoB
      • (AYmin > BYmax) || // A totalmente por arriba B
      • (AZmax < BZmin) || // A totalmente al frente B
      • (AZmin > BZmax) // A totalmente por detrás B

El problema del time stamp fijo:

  • El problema del time stamp fijo:
    • Si la intersección se calcula en cada frame => Ciertas colisiones pueden perderse.
    • Un objeto a gran velocidad puede atravesar totalmente a otro objeto en ese plazo de tiempo.

Se debe calcular un tiempo correcto

  • Se debe calcular un tiempo correcto
  • Una colisión errónea puede producir efectos diferentes a los esperados

Soluciones al problema del timestamp

  • Soluciones al problema del timestamp
    • Cálculo de colisiones no dependientes del Frame Rate
    • Estimar el tiempo posible de la colisión
    • Usar un volumen mayor para las colisiones
    • Clasificar los objetos de acuerdo a la velocidad

Remover pares de objetos que nunca colisionarán

  • Remover pares de objetos que nunca colisionarán
  • Realizar pruebas con BOs simples
  • No testear objetos que se encuentran muy separados
  • Obviar objetos no-visibles

Se distribuyen los objetos utilizando grillas regulares.

  • Se distribuyen los objetos utilizando grillas regulares.
  • Se comparan los objetos con no más de una celda de distancia:
    • for all objects O
      • for y = O.grid_y-1 to O.grid_y+1
      • for x = O.grid_x-1 to O.grid_x+1
      • for all objects O’ in grid(x,y)
        • check collision O <-> O’

Árboles de Bounding volumes: BSP u Octrees

  • Árboles de Bounding volumes: BSP u Octrees
  • Chequear entre dos árboles A y B:
    • Chequear intersección entre los nodos de A y B
    • Si no hay intersección
      • Exit
    • Si A o B son hojas
      • Retornar intersección más cercana
    • Sino
      • 1. Para cada par de hijos de A, B
        • chquear Intersección

Tutorial Frustum

  • Tutorial Frustum
    • http://www.lighthouse3d.com/opengl/tutorials/
  • http://graphics.cs.cmu.edu/projects/


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal