Embed Size (px)
Citation preview
CAPITULO 5. FASE DE VERIFICACION 5.1 INTERSECCIÓN DE ESFERAS La fase de verificación es aquella donde nuestro algoritmo utiliza las estructuras jerárquicas generadas en la fase anterior para descartar donde NO EXISTE colisión entre los objetos.
Este procedimiento se basa en verificar la intersección entre esferas. Un par de esferas se intersectan si la distancia entre sus centros es menor que la suma de sus radios.
r1 r2 r1 r2 P Q
figura 5.1. Intersección de esferas
Para esferas con centro P y Q y radios r1 y r2, la verificación de la intersección es se realiza calculando como: | P – Q | < r1 + r2. Tenemos que | P – Q | = (Q - P ) (Q - P) Por lo tanto (Q - P ).(Q - P) < r1 + r2 estas operaciones son rápidas de ejecutar. Al utilizar las estructuras jerárquicas en esta fase, el algoritmo irá podando las ramas de los árboles, donde las esferas de un determinado nivel no se intersectan con ninguna esfera del mismo nivel del otro árbol. Al final sólo quedarán en ambos árboles las ramas cuyas hojas envuelven a los triángulos que tienen mayor posibilidad de intersección.
41
5.2 OBJETOS EN POSICIONES ALEJADAS Supongamos dos objetos en el ambiente un cubo y un tetraedro. A los cuales se les ha construido en la etapa de preprocesamiento su árbol (estructura jerárquica).
0 12
34
57
6 89
1110
0
1
10
11
23
45
7
6
8 9
figura 5.2. Estructura Jerárquica del cubo
En la figura 5.2 se muestra el árbol asociado al cubo, y en el nivel de hojas se colocan de cada uno de los triángulos que conforman la malla del objeto.
1 2
5 6
3 0
7 4
0 2 3 7 4 5 61
figura 5.3 Estructura Jerárquica del tetraedro
Al igual que el cubo la figura 5.3 muestra la estructura jerárquica del tetraedro, y de los triángulos en el nivel de hojas. En la fase de verificación se utilizaran estas estructuras para comprobar si existe una colisión entre los dos cuerpos. En primera instancia se verifica si las esferas raíces de ambos objetos colisionan.
42
figura 5.4 Los dos cuerpos en posiciones alejadas
Si los dos objetos se encuentran lejos, sus esferas raíces no se intersectan(figura 5.4), por lo tanto en este caso, la detección de colisión será muy rápida, ya que verificar que dos esferas se intersectan no es muy costoso como se menciono anteriormente. El algoritmo al detectar que no existe intersección entre las dos esferas entra a una fase de podar los dos árboles. El objetivo principal de los métodos que utilizan estructuras jerárquicas es la de detectar de una forma simple y rápida cuando dos objetos NO COLISIONAN, evitando con ello, una verificación de colisión mas profunda, lo cual tomaría mayor tiempo. De esta forma se pueden desechar todas las posiciones donde los objetos no presenten una posibilidad de colisión.
43
5.3 OBJETOS EN POSICIONES CERCANAS Si los objetos se encuentran en una posición cercana pero no existe colisión entre ellos, a través de los diferentes niveles del árbol podemos determinar si realmente los objetos no colisionan.
figura 5.5. Esferas raíces presentando intersección
Esto lo podemos ver en el ejemplo de la figura 5.5. En donde los objetos están uno cerca del otro y sus esferas raíces presentan intersección entre ellas, en este caso se realizará una verificación de intersección de esferas hasta poder descartar o asegurar la intersección. Si las esferas raíces se intersectan, entonces nuestro algoritmo verificará si algún par de esferas (una perteneciente a un árbol y la otra al otro) del segundo nivel presentan intersección. Si alguna esfera perteneciente a este nivel no presenta intersección con ninguna esfera del otro árbol del mismo nivel, esta esfera se podaría del árbol (junto con todo la rama que cuelgue de ella).
44
Veamos en nuestro ejemplo como quedarían los árboles
figura 5.6 En el segundo nivel, las esferas presentan intersección
Los árboles quedarían iguales ya que no se poda ninguna rama, porque en la figura anterior se muestra como las cuatro esferas (dos de un árbol y las otras dos del otro) presentan intersección.
0 1 2 34
57
6 89
1110 0 2 3 7 4 5 615
4
3
2
1
4
3
2
1
figura 5.7. Estructuras de los árboles después de verificarse el segundo nivel
Al existir intersección entre esferas, se verifica ahora las esferas del siguiente nivel, pero solo las pertenecientes a las esferas que presentan una intersección en el nivel anterior.
45
Como las esferas del segundo nivel presentan todas intersección entonces, pasaríamos a las esferas del tercer nivel, y haríamos la verificación de intersección por pares (una perteneciente a un árbol y la otra al otro). Dejando solo las ramas del árbol donde las esferas presentan una intersección al menos con una esfera del otro árbol. En nuestro ejemplo vemos que existen esferas que presentan intersección y otras que son podadas del árbol.
figura 58. Tercer nivel de esferas (antes y después de podar)
En la figura 5.8 la imagen de la izquierda muestra el nivel 3 antes de ser podado, y en la imagen de la derecha muestra las esferas del mismo nivel después de podarse las ramas que no presentaron intersección. En nuestro ejemplo para el cubo en el tercer nivel tiene 3 esferas de las cuales se ha podado una de ellas y para el tetraedro el tercer nivel tiene cuatro esferas de las cuales se podaron dos, quedando los árboles como se muestran a continuación.
0 1 2 3 8
911
10
2 3 7 4
5
4
3
2
1
4
3
2
1
figura 5.9. Árboles podados, después de la verificación del tercer nivel
46
Al igual que los niveles anteriores mientras se presente intersección entre esferas se ira bajando de nivel en nivel verificando solo aquellas que presenten intersección en el nivel anterior, ya que las demás ramas se irán podando.
figura 5.10. Cuarto nivel de esferas (antes y después de podar)
En nuestro ejemplo la figura 5.10 muestra el cuarto nivel antes de podarse el árbol (imagen a la izquierda) y después de podarse las ramas (imagen a la derecha). Si observamos, ninguna esfera del cuarto nivel se intersecta, están muy aproximadas algunas de ellas, pero no se intersectan, por lo tanto los árboles se podan en este nivel en su totalidad, como lo muestra la imagen de la derecha. A continuación se muestran los árboles después de verificarse el cuarto nivel.
5
4
3
2
1
4
3
2
1
figura 5.11. Árboles podados, después de la verificación del cuarto nivel
El nivel 4 y 5 de la estructura del árbol asociada al cubo se podo y para el árbol del tetraedro el nivel 4 se elimino por no existir intersección de esferas en el cuarto nivel. El nivel de hojas en ambos árboles se elimina y esto nos determina que NO EXISTE COLISION entre objetos.
47
5.4 OBJETOS EN COLISIÓN Si los objetos se encuentran en colisión, al verificar la intersección de esferas en cada uno de los niveles, se irán podando los árboles hasta dejar las esferas-hojas, las cuales cubren a los triángulos en los que existe una posibilidad de intersección. Veamos un ejemplo de la verificación de colisión, con dos objetos el cubo y el tetraedro, a los cuales su estructura jerárquica (árbol) se les calculo durante la etapa de prepocesamiento.
0 1 2 34
57
6 89
1110 0 2 3 7 4 5 615
4
3
2
1
4
3
2
1
A
B C
D E F
G H I J K L
a
b c
d e f g
0
1
10
11
23
45
7
6
8 91 2
5 6
3 0
7 4
figura 5.12 La estructura jerárquica del cubo y del tetraedro
figura 5.13 Los dos cuerpos en posiciones cercanas
48
Primero se verificará la intersección de las esferas raíces, si estas presentan una intersección se verificará el siguiente nivel.
figura 5.14 Primer nivel, esferas raíces
En nuestro ejemplo se verifica si la esfera A intersecta a la esfera a (figura 5.14), si esto sucede, se pasará al siguiente nivel de ambos árboles para verificar las esferas en el segundo nivel.
0 1 2 34
57
6 89
1110 0 2 3 7 4 5 615
4
3
2
1
4
3
2
1
A
B C
D E F
G H I J K L
a
b c
d e f g
figura 515. Estructuras de los árboles después de verificar el primer nivel
Ahora se pasa a verificar las esferas del segundo nivel
49
La esfera B se verifica primero con la esfera b y posteriormente con c, si no presentará ninguna intersección el subárbol que forma la esfera B se podaría, pero si al menos una esfera del otro árbol presenta una intersección este subárbol (rama) no se podrá podar. Posteriormente se haría lo mismo con la esfera C y las esferas b y c. Si no se presenta ninguna intersección con alguna de ellas se poda. Terminadas de analizar las del primer árbol, ahora se verifican las esferas del segundo árbol. La esfera b con las esferas B y C, se maneja el mismo criterio para podar, si no intersecta con ninguna esfera se poda del árbol, a continuación se verifica c con B y C utilizando el mismo criterio para podar esta rama. En nuestro ejemplo: Al menos B y b se intersectan, C y b, para c esta se intersecta con B, por lo que vemos que las cuatro esferas B, C, b y c presentan intersección y ninguna rama es podada de los árboles, quedando las estructuras iguales en este nivel.
0 12
34
57
6 89
1110
0 2 3 7 4 5 61
5
4
3
2
1
4
3
2
1A
B C
D E F
G H I J K L
a
b c
d e f g
figura 5.16. Estructuras de los árboles después de verificar el segundo nivel
50
Después de terminar de verificar el segundo nivel, se realizará lo mismo para el tercer nivel. Se hacen pares (una esfera del un árbol con una esfera del otro árbol) y se verifica si existe intersección en alguna par de ellas. Si alguna esfera de este nivel no intersecta con ninguna esfera del mismo nivel pero del otro árbol, entonces la rama que forma se poda del árbol. Para nuestro ejemplo se hicieron las siguientes verificaciones:
D con d, e, f y g E con d, e, f, y g F con d, e, f, y g
Dejando las tres esferas ya que estas presentan intersección con esferas del otro árbol, lo mismo sucedió con las esferas d, e, f y g, las cuales también presentaron intersección con las esferas del otro árbol. Por lo tanto hasta el tercer nivel las estructuras se conservaron iguales.
figura 5.17 Tercer nivel de esferas de ambos objetos
En la figura 5.17, se puede observar las tres esferas del árbol del cubo y las cuatro esferas del árbol del tetraedro. Para nuestro ejemplo se realizo la verificación del 4 nivel del árbol del cubo con el cuarto nivel (nivel de hojas) del árbol del tetraedro. G se verificó por pares con las esferas 0, 1, 2, 3, 4, 5, 6, 7 del árbol del tetraedro. H, I, J, K, L igualmente se verificaron con las esferas 0, 1, 2, 3, 4, 5, 6, 7 del árbol del tetraedro.
51
Y posteriormente 0, 1, 2, 3, 4, 5, 6, 7 con respecto a las esferas del cuarto nivel de árbol del cubo. En este cuarto nivel sólo se poda la esfera 5 que es la que no tiene intersección con ninguna esfera. Quedando los árboles de la manera siguiente.
0 1 2 34
57
6 89
1110
0 2 3 7 4 61
5
4
3
2
1
4
3
2
1A
B C
D E F
G H I J K L
a
b c
d e f g
figura 5.18 Estructuras de los árboles después de verificar el cuarto nivel
Si las estructuras fueran del mismo tamaño, ambos árboles se podarían igualmente, pero en el caso del ejemplo los árboles presentan diferente número de niveles. Por lo que nuestro algoritmo pasaría a verificar el siguiente nivel del árbol de mayor tamaño con respecto al último nivel del árbol de menor tamaño. En nuestro ejemplo se verificaría el quinto nivel del árbol del cubo con respecto al último nivel del árbol del tetraedro. Si la estructura presentara más niveles, se iría haciendo lo mismo hasta cubrir todos los niveles del árbol de mayor tamaño. Para nuestro ejemplo, al verificar los niveles 5 y 4 respectivamente los árboles quedaron de la siguiente manera.
52
0 1 6 8
2 3 7 6
5
4
3
2
1
4
3
2
1A
B C
D E F
G H I J K L
a
b c
d e f g
figura 5.19 Estructuras de los árboles después de verificar el quinto y cuarto nivel
figura 5.20. Esferas resultantes después de verificar el quinto y cuarto nivel
En las estructuras se puede apreciar que quedaron cuatro esferas hojas en cada uno de los árboles, y en las esferas se puede apreciar las cuatro esferas de cada uno de los cuerpos, en donde cada una de ellas contiene al triángulo con posibilidad de intersección. Llegando ambas estructuras al nivel de triángulos, la verificación se completa con el método de triángulo VS triángulo para comprobar si existe o no colisión entre los objetos. Se podría pensar que no tiene mucho sentido el utilizar el método de esferas, porque al final se realiza la verificación de triángulos VS triángulo, sin embargo este método se aplicará a un número reducido de triángulos.
53
5.5 PSEUDOCÓDIGO. ETAPA DE VERIFICACIÓN El siguiente pseudocódigo presenta la forma de construcción de la etapa de verificación Entrada: Malla de triángulos de dos objetos Estructuras de árbol de ambos objetos Salida: “Colisión” o “No Colisión” /* Detección de colisión entre árboles de esferas */ colisión (árbol1, árbol2) if (intersección(esfe-raiz1,esfe-raiz2) = intersectan) if (detección_colisión(arbol1,arbol2) = colisión) return colisión else return no colisión else return no colisión /* Verifica la intersección de las esferas entre los árboles */ /* nivel1 y nivel2, el número de nivel de los árboles respectivamente */ /* l1 y l2, el número de nivel que se esta verificando */ detección_colisión( arbol1, arbol2)
// Verifica los niveles de ambos árboles // pero solo hasta el nivel del árbol de menor tamaño while (l1 < nivel1 and l2 < nivel2 and l1 = l2 and not colisión)
// Poda árbol 1 for cada esfe1 del árbol1 de l1
for cada esfe2 del árbol2 de l2 estado intersección(esfe1, esfe2)
if (estado = colision) return collision if (estado = not intersecta) poda(esfe1) // Poda árbol 2 for cada esfe2 del árbol2 de l2
for cada esfe1 del árbol1 de l1 estado intersección(esfe1, esfe2)
if (estado = colision) return collision if (estado = not intersecta) poda(esfe2)
54
55
// Verifica el resto del árbol1 si este es el de mayor tamaño if (nivel1 > nivel2)
while (l1 < nivel1 and not colisión) // Poda árbol 1 for cada esfe1 del árbol1 de l1
for cada esfe2 del árbol2 de l2 estado intersección(esfe1, esfe2)
if (estado = colision) return collision if (estado = not intersecta) poda(esfe1)
// Verifica el resto del árbol2 si este es el de mayor tamaño if (nivel2 > nivel1)
while (l2 < nivel2 and not colisión) // Poda árbol 1 for cada esfe2 del árbol2 de l2
for cada esfe1 del árbol1 de l1 estado intersección(esfe1, esfe2)
if (estado = colision) return collision if (estado = not intersecta) poda(esfe1)
return not collision
Este algoritmo indica las partes importantes de la implementación de la fase de verificación. La rutina de colisión es el primer filtro para detectar si dos objetos en posiciones alejadas no presentan colisión, esto se realiza verificando si las esferas raíces no se intersectan. La verificación es rápida y desecha todas las posiciones donde los objetos se encuentran colocados sin posibilidad de COLISIÓN. La rutina de detección_colisión, es la encargada de determinar si dos cuerpos que se encuentran en posiciones cercanas presentan Colisión o no. Ésta se determinará verificando desde el nivel dos hasta el último nivel de ambos árboles cuales son las esferas que se intersectan y podar las ramas donde las esferas no presentan ninguna intersección. El primer while verifica las esferas de los árboles, hasta el nivel del árbol de menor tamaño, si ambos árboles presentan el mismo número de niveles, la rutina con ese while termina. Por otro lado, si los árboles presentan niveles diferentes, el segundo while se encargará de terminar los niveles del arbol1 en el caso que el árbol1 sea el mayor, y el tercer while se encargará de terminar de verificar el arbol2, si el arbol2 es el mayor.
