TEMA 8: Visibilidad

Índice 1.

Visibilidad. Concepto y técnicas generales

2.

Eliminación de líneas ocultas

3.

1.

Algoritmo del horizonte flotante

2.

Eliminación de superficies poliédricas

Eliminación de superficies p ocultas 1.

Algoritmo del z-buffer

2.

Algoritmo de línea de rastreo

3.

Métodos basados en prioridad

4.

Algoritmos para superficies curvas

5.

Ray - tracing

Problema a resolver •

Una vez modelada la escena, compuesta por miles de polígonos, hay que visualizarla en pantalla

Rendering: Proceso de generación automático de una imagen mediante la cual el modelo matemático de un objeto o escena ll llega a aparentar t ser un objeto bj t o una escena reall •

Se divide en dos fases: –

determinación de las partes visibles de la escena

–

simulación de las propiedades físicas de los objetos atendiendo a la interacción de la luz con las superficies para mostrar su color

Definición de visibilidad •

Sea S un conjunto de puntos de R3, y un observador

•

Diremos que Q ∈ S es visible desde P si el segmento t PQ no intersecta i t t aS

PQ = R(t ) = tQ + (1 − t ) P •

P P∉S

∀t ∈ (0,1)

Q1

Q es visible i ibl sii

R (t ) ∉ S

∀t ∈ (0,1)

Q2

•

Se trata de un problema de cálculo de intersecciones

•

Sería impracticable determinar la condición de visibilidad para cada punto de la escena –

Son infinitos puntos

–

Para cada uno habría un montón de intersecciones

•

Averiguar si un segmento intersecta al objeto S, posiblemente compuesto por miles de polígonos o superficies paramétricas, conlleva mucho cálculo

•

Por tanto tanto, los algoritmos no van a ser simples simples, y deberán sacarle el máximo partido a las propiedades específicas de cada escena

Visibilidad en objetos poliédricos • •

Una propiedad interesante que cumplen muchos objetos poliédricos es:

N

Sea N lla normall exterior S t i de d una de d sus caras Æ esta cara será visible si

( P − Q) ⋅ N > 0 • •

Es decir, las caras visibles son las orientadas hacia el plano de proyección

N

Esta propiedad sólo es cierta en un sentido

•

Esta propiedad también se cumple en la mayoría de superficies curvas

•

Los puntos donde (P (P-Q)N=0 Q)N=0 delimitan una linea llamada CONTORNO APARENTE

•

Son todos los puntos Q en los que la recta PQ está tá sobre b ell plano l ttangente t en Q

Contorno aparente •

Para una superficie regular, los bordes también cuenta como contorno aparente

•

Para un objeto poliédrico, el contorno no puede definirse en términos del vector normal, pues éste sólo existe en el interior de las caras

•

Por lo tanto, sólo se produce sobre las aristas

•

El problema es cuando queremos representar una superficie regular mediante di curvas, d donde d ell contorno no queda correctamente dibujado

•

Si se conoce el contorno aparente se podría dibujar como una curva más

Parte anterior y posterior •

Sea un punto Q invisible

•

Por lo tanto, el segmento PQ intersecta a la superficie fi i en un número ú finito fi it de d puntos, t n –

Si n es impar Æ Q pertenece a la parte posterior

–

Si n es par Æ Q pertenece a la parte anterior

•

OJO: los puntos de la parte posterior son siempre p o no serlo invisibles,, y los anteriores pueden

•

Si la superficie posee normal en todos sus puntos, un punto pertenece a la cara posterior si N(P-Q)H(x) ó y Z(u,v) Z( ) Æ ell polígono lí está á más á lejos l j que algún l ú otro

•

Lo bueno L b de d esta condición di ió es que es fácil fá il d de añadir ñ di all código ódi d dell algoritmo l i d de relleno ll de scan-line, de forma que se puede implementar por hardware para ejecutarse rápidamente

Algoritmo del z-buffer (5) •

El algoritmo va procesando secuencialmente todos los polígonos, y al finalizar la matriz F contiene la imagen final Frame buffer

Z-buffer

Frame buffer

Z-buffer

Algoritmo del z-buffer (6) Ventajas del método: •

El tiempo de ejecución no depende de la complejidad de la escena, sino sólo de su parte visible i ibl

•

Puede utilizarse cualquier tipo de objeto

•

N se necesitan No it algoritmos l it d de iintersección t ió

•

El coste es O(n), en lugar de O(n2) como la gran mayoría

•

Ó ti Óptimo para ser iimplementado l t d en h hardware d

Algoritmo de línea de rastreo (1) •

Si se intersecta la escena con un plano horizontal, correpondiente a una línea de barrido (scan-line) de la pantalla, aparecen polígonos 2D

y

z z

x x a

x1

x2

x3

x5

x4

x6

x7

b

•

Ahora para esa línea, obtenemos varios intervalos Æ SPANS

•

(a,x1), (x1, x2) …. (x7, b)

Algoritmo de línea de rastreo (2) Para cada span: 1.

Si no contiene ningún elemento Æ pintamos color l de d f fondo d

2.

Si sólo contiene 1 segmento Æ pintamos del color de ese polígono

3.

•

Si hay más de 1 segmento Æ pintamos con el color del más cercano

z

x a

x1

x2

x3

x5

x4

x6

x7

Para calcular cuál, testeamos la componente z en la mitad del span X = (x4 + x5) / 2 Z = f (x, (x yk)

x x4

x5

b

Algoritmo de línea de rastreo (3) •

El algoritmo anterior es rápido y potente, pero ineficiente, pues en cada línea de barrido debe calcular la intersección del plano con toda la escena

•

E i t una versión Existe ió optimizada, ti i d similar i il all algoritmo l it d de relleno ll scan-line li

•

Creamos una tabla de aristas (ya proyectadas en 2D)

•

C d arista Cada i t viene i representada t d por cinco i valores l

•

–

Coordenada y del punto más alto

–

Coordenada x del punto más bajo

–

I Inversa de d lla pendiente di t

–

Identificador del polígono al que pertenece

–

Puntero a otra arista en la misma scan-line

ymax

x

1/m /

pol po

color

in/out

Además existe una tabla de polígonos, con estos valores –

Identificador

–

Ecuación del plano

–

Color

–

Flag in / out

pol

(A,B,C,D)

Algoritmo de línea de rastreo (4) •

Se crea un vector vacío, con tantas posiciones como filas tenga la pantalla, y se coloca cada arista en la posición de la scan-line del punto más bajo

•

T d esto Todo t se hace h en preproceso, y es bastante b t t rápido á id y

B E

DE

D

CB C

F

A x

FD

FE

AB

AC

Algoritmo de línea de rastreo (5) •

La gran ventaja ahora es que en cada scan-line, sólo comparo con las aristas que me hacen falta

•

Además, Ad á no necesito it calcular l l ninguna i iintersección, t ió ya que llas coordenadas d d se deducen d d a partir de las de la iteración anterior y

B E D

C

F

A x

–

(AB, DE) Æ se activa pol. azul

–

(DE, CB) Æ se activa pol. rojo Æ test de profundidad

–

(CB, FE) Æ se desactiva pol. azul

–

(…, AB) Æ no hay polígono

–

(AB, AC) Æ se activa pol. azul

–

(AC, FD) Æ se desactiva pol. azul

–

(FD, FE) Æ se activa pol. rojo

–

(…, AB) Æ no hay polígono

–

(AB AC) Æ se activa pol. (AB, pol azul

–

(AC, …) Æ se desactiva pol. azul

Métodos basados en prioridad (1) •

Una vez transformados los polígonos, se ordenan según la máxima profundidad de cada uno

•

N es exactamente No t t la l definición d fi i ió d de propiedad, i d d pero se calcula l l muy rápido á id

•

El algoritmo es similar a la técnica del pintor Æ los polígonos se procesan en orden

•

En la E l etapa t k, k llos polígonos lí P1 P1, P2, P2 …, Pk-1 Pk 1 ya h han sido id correctamente t t dib dibujados, j d yh hay que ver si Pk está bien ordenado, o hay que moverlo hacia delante

z

Pj

Pi

Inicialmente, Pi estaría ordenado en la lista por delante de Pj

Métodos basados en prioridad (2) z

El algoritmo para cada iteración k sería: •

Si zmin(Pk) > zmax(Pk+1) Æ Pk está bien colocado

Pk

zmin zmax

•

Si no, hay realizar más comprobaciones, ordenadas y dificultad de menor a mayor

•

Desde que se incumpla uno ÆPk está bien colocado

1 1.

¿Son disjuntos Pk y Pk+1 k 1 en x?

2.

¿Son disjuntos Pk y Pk+1 en y?

3 3.

¿Está Pk por detrás del plano de Pk+1 k 1?

4.

¿Está Pk+1 por delante del plano de Pk?

5 5.

¿Son disjuntas sus proyecciones sobre XY?

•

Si todas las preguntas son negativas, se intercambian Pk con Pk+1 en la lista, y se vuelven a hacer las comprobaciones m b i s para ell nuevo Pk

Pk+1

Métodos basados en prioridad (3) •

Existen casos en los que se entra en un bucle

•

Hay que saber detectarlos, y romper un polígono por el plano que contiene a otro

•

Se usa mucho en simuladores de vuelo y de coches, coches donde los elementos del fondo tienen un orden fijo y conocido de antemano

Algoritmo para superficies curvas

Trazado de rayos (ray-tracing) •

La filosofía es totalmente distinta a los anteriores algoritmos

•

No utiliza propiedades de coherencia, tratando cada punto individualmente

•

Es de los más costosos, pero permite escenas con objetos de cualquier tipo

•

Simula con facilidad reflexiones, refracciones, sombras, texturas, transparencias, etc.

•

Se supone p conocido el plano p de proyección en el espacio, ya discretizado en pixels

•

El procedimiento consiste en lanzar rayos a través de cada pixel, propagándolos a través de la escena, hasta que intersecten un objeto

•

El primer punto detectado determina el color del pixel

Ray-tracing (2) •

Cuando se definió la visibilidad, se consideraba un punto Q sobre un objeto, y se trataba de deducir si era visible o no, y cuál era su proyección

•

Ahora es all revés Ah é Æ conozco la l proyección, ió y quiero i ver qué é punto t de d la l escena se proyecta sobre él

•

Sea F(x,y,z)=0 la ecuación de un objeto

•

Sea (a,b,c) (a b c) las posición del ojo

•

Para cada pixel se define el vector v que va del ojo a ese pixel Æ r =

•

La ecuación del rayo será

v

(x,y,z) = (a,b,c) + t (rx, ry, rz) •

Para cada objeto calculamos las intersecciones F(a+trx, b+try, c+trz) = 0

(a,b,c)

Ray-tracing (3) •

Al resolver la intersección t, pueden salir 0, 1 ó varias intersecciones

•

Si no existe ninguna, es que el rayo no intersecta el objeto

•

Si sólo existe una, ése es el punto que nos interesa

•

Si existen varias, habrá que coger la solución positiva más pequeña

•

Cuando tenemos las intersecciones calculadas con todos los objetos, nos quedamos con ell valor l positivo iti más á pequeño ñ

•

La ventaja es que el cálculo de intersecciones para cada tipo de objeto diferente puede ser una rutina distinta

•

En ocasiones harán falta algoritmos numéricos para hallar las intersecciones

Ray-tracing (4) •

A veces, un sólido tiene un rango limitado de sus variables en la ecuación implícita F(x,y,z) = 0

•

Por ejemplo, P j l un polígono lí viene i d dado d por lla ecuación ió d dell plano l A Ax + B By + C Cz + D = 0 0, junto j t con la restricción de que sus puntos están en el interior

Solución: 1 1.

Evaluamos la intersección con el plano

2.

Testeamos si el punto pertenece al interior del polígono

Ray-tracing (5) •

En definitiva, el algoritmo no sigue el proceso usual:

•

Transformación de Vista Æ no hace falta, ya que se conoce la posición del observador ( b ) ell plano (a,b,c), l d de proyección, ió y lla posición i ió d de llos objetos bj t

•

Recorte Æ no hace falta, ya que al buscar soluciones con los rayos que van a los pixels, los objetos que caigan fueran del volumen de vista nunca intersectará con ninguno

•

Proyección Æ es automática, ya que cada rayo indica en qué punto hay que proyectar

•

Visibilidad Æ se resuelve automáticamente al elegir el valor mínimo de t

•

El problema es que es muy costoso Æ Ejemplo: una imagen 1024 x 768 pixels necesita 800.000 rayos que lanzar, y cada uno debe intersectarse con n objetos (y aún no hemos hablado nada de calcular el color!!)

•

Ventajas: –

Visualiza realísticamente superficies regulares

–

Permite incorporar modelos de iluminación para simular fenómenos ópticos

–

Permite rm t tra trabajar ajar con cua cualquier qu r tipo t po de o objetos j tos

Ray-tracing (6)