>> Visibilidad <<
LINK
http://www.sc.ehu.es/ccwgamoa/docencia/Material/Presentaciones
Visibilidad
A. García-Alonso
1
Introducción
•
•
•
•
Hearn Cap. 13, Foley Cap. 15
Visibilidad de líneas o elementos de superficie
Polígono, cara o faceta (libre o en sólido)
Aspectos a considerar
– Complejidad de la escena ++++
• Objeto, sala, piso, casa, ciudad, mundo
• Objeto, robot, célula, planta (barco, refinería, ...)
– Modelo geométrico: polígonos, superficies, voxels, (...)
– Conocimiento previo de elementos móviles
• Restricciones, o posiciones relativas
• Juegos, simuladores
Visibilidad
A. García-Alonso
2
Conceptos previos de geometría
• Sistemas de referencia
– modelado, mundo, cámara, pantalla
• Asumimos sistema cámara dextrógiro
– Dextrógiro/levógiro: eje Z saliente/entrante en pantalla
– V: punto de vista
A: punto hacia el que se mira
yc
yc
xc
A
V
V
zc
Levógiro
Dextrógiro
Visibilidad
xc
A
zc
A. García-Alonso
3
Conceptos
•
•
•
•
•
•
•
Volúmenes contenedores
Definición y ecuación del plano (semi-espacios)
Angulo entre dos vectores
Descripción y propiedades polígonos
Descripción y propiedades poliedros
Espacio objeto y espacio imagen
Coherencia
Visibilidad
A. García-Alonso
4
Prioridad (ejemplos)
• Videojuegos (nivel objeto)
• Luego veremos a nivel de caras




Visibilidad
A. García-Alonso
5
Prioridad
• Causa de dificultad
– Número de objetos
– Complejidad en las posiciones relativas
• Niveles
– Edificios en urbanismo (fácil)
– Piezas de un motor (difícil)
– Entramado de tuberías (imposible, salvo partición)
Visibilidad
A. García-Alonso
6
Algoritmos
• Volumen de visión: recorte (perspectiva o paralela)
• Detectar caras traseras (back-culling)
• Prioridad
– Polígonos
• Ordenamiento en profundidad (depth-sorting)
• BSP (binary space partitioning trees)
– Objetos o conjuntos (clusters)
– Terreno
Visibilidad
A. García-Alonso
7
...
• Precisión de imagen
– z-buffer
– Línea de barrido (scan-line)
– Lanzamiento de rayos (ray-casting)
• Dibujo de grandes modelos
• Líneas ocultas
Visibilidad
A. García-Alonso
8
Caras Traseras
• Si un polígono pertenece a un poliedro
– Condición suficiente de no visibilidad : v.n ≥ 0
– Si un poliedro es convexo y no es tapado por ningún otro
objeto, v.n < 0 es condición necesaria y suficiente de
visibilidad de una cara
n1
v
Visibilidad
A. García-Alonso
9
Caras Traseras (OpenGL)
• Activar glEnable( GL_CULL_FACE )
• Es posible invertir el “cull” front / back
– glCullFace()
– Permite ver “el interior”
• Si no se especifica la normal del polígono, realiza el
cálculo en base a las coordenadas de los vértices
proyectadas sobre la pantalla (esto puede ser más lento,
depende del flujo en el proceso gráfico)
– glFrontFace()
Visibilidad
A. García-Alonso
10
Pintor (fundamentos)
• Ordenación en profundidad ó depth-sorting
1
2
– Lista ordenada polígonos
– Condición: i no tapa a ningún polígono [i+1, n]
• (está por detrás)
– Se dibujan los polígonos en orden 1 a n
i
• Aplicación
– Escena
• Se genera la lista para cada frame (cualquier cambio relativo)
• Coste puede ser excesivo (nº polígonos, en cada cuadro)
n
– Objeto
• Nueva lista al moverse respecto a la cámara
• Coste puede ser competitivo
Visibilidad
A. García-Alonso
11
ver nota
Pintor (pre-ordenación)
• Ordenar en zmin, que es distinta de la ordenación final
en profundidad
 orden en zmin
 orden en profundidad



Visibilidad
A. García-Alonso


12
Pintor (figuras)
Extents solapan,
caras no
Extents y caras
solapan
xmax < xmin 
no solapan extents
Visibilidad
A. García-Alonso
13
Posición relativa de caras +++
yc
i
La cara i está detrás del plano de la cara j
j
Visibilidad
zc
A. García-Alonso
14
Cara “delante” de un plano +++
• Si nz > 0, un polígono “está delante” del plano si todos
sus vértices están en el semiespacio +
• Si nz < 0, al revés
Visibilidad
A. García-Alonso
15
Solapes +++
– Solapes
Solape cíclico
Solape por
cara cóncava
Solape por intersección
entre caras
Visibilidad
A. García-Alonso
16
Modelos de placas (sin volumen) +++
– Polígonos contiguos en mallas
Modelos de placas (no
cierran volumen)
Visibilidad
A. García-Alonso
17
BSP (fundamentos)
• Fases : (Binary space partitioning trees)
– Crear árbol (si cambia posición relativa polígonos)
• Árbol binario de polígonos (nodos y hojas son Pol.)
• Nodo raíz divide en dos grupos el resto de polígonos, si hace
falta algunas caras se parten en dos
• En cada grupo se selecciona una cara (nuevo nodo)
• La cara vuelve a crear dos grupos
• Hojas contienen sólo una cara
– Recorrer árbol
• Permite recorrer el conjunto de polígonos de “atrás adelante”
• Permite dibujar por prioridad independientemente punto vista
Visibilidad
A. García-Alonso
18
BSP (aplicación)
• Escena
– Generar árbol: si cambio posición relativa entre objetos
– Coste puede ser excesivo (nº polígonos en la escena )
• Objeto
– Si es sólido : árbol constante en el tiempo
– Coste puede ser competitivo
– Combina con prioridad conocida entre objetos (BSP o
“Pintor”)
• Pseudo-código de Foley
Visibilidad
A. García-Alonso
19
BSP (implementación)
• Eficiencia en el dibujado:
– Evitar el incremento de polígonos
– Árbol equilibrado
• Eficiencia en la creación del árbol
– Elección rápida de los nuevos nodos
Visibilidad
A. García-Alonso
20
ver nota
Objetos o conjuntos (clusters)
• Prioridad en profundidad
– Conocida de antemano
– Evaluable
• Ejemplo de BSP entre objetos sin movimiento relativo
• Con cambio en la posición relativa
– Construcción del árbol
– Selección de los planos
– ¿ Compensa ?
Visibilidad
A. García-Alonso
21
Terreno
• Se asimila al dibujo de funciones de dos variables
• Sólido
– Prioridad de profundidad (extraplomo, cueva)
• Malla
– De adelante hacia atrás
– Usar líneas de horizonte superior e inferior
Visibilidad
A. García-Alonso
22
z-buffer (fundamentos)
• Sólo polígonos interiores al prisma de visión
• En un píxel : polígonos que se proyectan sobre él
• Visible : el “píxel” más próximo al ojo
– Aquel cuya componente Z en el sistema de la cámara tenga
un valor mayor
cj
ci
ck
ys
(x,y)
Polígonos que proyectan
sobre el pixel (x,y). El pixel
correspondiente a ck es el de
mayor valor en z.
Visibilidad
A. García-Alonso
xs
zs
23
ver nota
z-buffer (algoritmo)
• Pseudo-código de Foley
– Frame buffer (“color”)
– z-buffer (profundidad, 0 a 216 ó 232)
– Lista polígonos recortados y proyectados al sistema de la
pantalla (1024x1280pixels, etc. ) …
Arista 1
Arista 2
Scan-line
Visibilidad
A. García-Alonso
24
z-buffer (scan convert)
• Scan convert cada polígono
– Se conocen las coordenadas x,y,z de cada vértice en el
sistema de pantalla (píxeles x,y, mayor precisión en z)
– Recordar cómo se generan los píxeles de una línea partiendo
de las componentes x,y de sus extremos
– De igual modo se incrementa el valor z al avanzar en cada
línea de barrido
– En cada línea de barrido (y cte.) tendremos dos píxeles de
componentes (x,z) conocidas
– Al ir incrementando de unidad en unidad x, obtenemos la
componente z en cada pixel del tramo
Visibilidad
A. García-Alonso
25
z-buffer (implementación)
• Inicializar z-buffer (uso menor o mayor valor depende
sistema)
• Tener en cuenta sistema dextrógiro o levógiro
• Problema precisión “near & far planes” …
• OpenGL
–
–
–
–
–
–
glEnable( GL_DEPTH_TEST )
glClear( GL_COLOR_BUFFER_BIT | GL_DEPTH_TEST )
glClearDepth( [0,1] )
glDepthFunc( GL_LESS )
glDepthRange( near[0,1], far[0,1] )
glDepthMask( 0 disabled, 0 enabled )
Visibilidad
A. García-Alonso
26
z-buffer (planos frontal y trasero)

Plano frontal mal colocado,
se ve “el interior”

Plano trasero mal colocado, no se
ve todo lo que se debería
Visibilidad
A. García-Alonso

Planos bien ajustados
27
z-buffer (Problema precisión)
Problema precisión

Visibilidad

A. García-Alonso
28
Memoria gráfica
• True color requiere 8x3 bits/pixel
• Alpha channel requiere otros 8 bits/pixel
• Usar double buffering requiere duplicar la memoria de
imagen por píxel
• Usar visión estereoscópica requiere otra duplicación
• z-buffer requiere 16 ó 32 bits/pixel
• Memoria de texturas (no depende del nº de píxeles de
imagen)
Visibilidad
A. García-Alonso
29
Lanzamiento de rayos : ray-casting
•
•
•
•
Por cada píxel se lanza un rayo (F)
Se determina con que superficie choca primero
Se determina “el color” en ese punto
No confundir con “trazado de rayos” (ray-tracing)
Punto de vista y rayo
Malla de píxeles
Visibilidad
A. García-Alonso
30
Grandes modelos
• Dibujo de grandes bases de datos
• Ejemplos
–
–
–
–
–
–
Arquitectura, urbanismo, mundo virtual (walk-through)
Fábricas, procesos productivos
Redes tuberías
Motores, maquinaria, vehículos, barcos, aviación
Simulación
etc
Visibilidad
A. García-Alonso
31
Grandes modelos (técnicas)
• Carga y descarga de la descripción de objetos (disco,
red)
• Discriminar rápidamente qué elementos son
potencialmente visibles y cuáles no
• Jerarquías de contenedores
– Elementos contenidos en otros (cajón, motor,...)
• Oclusión (occluded surfaces)
Visibilidad
A. García-Alonso
32
...
• Niveles de detalle
– Uso de superficies paramétricas
– Niveles discretos
– Variación continua
http://www.best.com/~rikk/Book/
Visibilidad
A. García-Alonso
33
...
http://gts.sourceforge.net
A multi-resolution model
obtained by simplification of
the original model (in the top
left corner).
The "memoryless
simplification" algorithm of
Lindstrom and Turk was used.
The number of triangles are
respectively 96966, 13334,
3334 and 668.
(video disponible)
Visibilidad
A. García-Alonso
34
Líneas ocultas
• Uso en análisis y modelado
– Visualizar aristas
• Efectos especiales
• Visualizar densidad de las mallas
– Velocidad de generación de imagen en aceleradores
– Radiosidad gradiente iluminación
• Polígonos : aristas de un color, interior otro color
– OpenGL
– Algoritmo prioridad
• Tener cuidado con el sombreado
Visibilidad
A. García-Alonso
35
Coherencia
• Comparar objetos, no sus elementos (si separados)
• Las propiedades varían suavemente en caras (interpolación
lineal)
• Arista: cambia su visibilidad sólo al pasar detrás de otra
visible
• Arista de intersección : bastan dos puntos para calcularla
• Scan-line : varían poco de uno al siguiente
• Área : un grupo de píxeles adyacentes tiende a estar cubierto
por la misma cara visible
• En superficies, áreas adyacentes suelen estar a profundidad
parecida
• Cuadro (frame): dos imágenes sucesivas tienden a ser
parecidas
Visibilidad
A. García-Alonso
36
Resumen
• Determinar características del problema :
–
–
–
–
Objetos móviles (uno o todos) o estáticos
Número de objetos
Número de polígonos
Con o sin acelerador gráfico (prioridad, back-culling, zbuffer,...)
– Nivel de realismo (trazado de rayos vs. z-buffer)
Visibilidad
A. García-Alonso
37
Descargar

Document