CAPITULO 4.
FASE DE PREPROCESAMIENTO
La etapa de preprocesamiento consiste en crear las estructuras jerárquicas de
cada uno de los objetos de los que se desea saber si existe colisión entre ellos,
mismas estructuras que posteriormente se utilizaran en la etapa de verificación.
Esta fase generó tres problemas a resolver, los cuales describiremos a
continuación.
4.1 PROBLEMAS A RESOLVER
1. Encontrar un método que calcule la esfera de menor radio para cubrir un
triángulo en 3D.
2. Dadas dos esferas cualesquiera, seleccionar un método que encuentre la
esfera de menor radio capaz de cubrir a estas dos.
3. Encontrar el orden en el que se deberán colocar los triángulos en el nivel de
hojas en la estructura jerárquica.
Esfera de menor radio
Este fue el primer problema al cual nos enfrentamos. Al recibir la malla de
triángulos con la cual se encuentra modelado el objeto, esta no presenta todos sus
triángulos de la misma forma, sino varían en forma y tamaño.
Propusimos tres métodos a los cuales les llamamos Baricentro, Máximos y
mínimos, y Lado Mayor. Debido a la forma de los triángulos ninguno de los
métodos propuestos genera las esferas de menor radio para todos los triángulos
que modelan el objeto.
Cada uno de ellos se explica en la sección 4.2.
Esfera de menor radio para cubrir dos esferas
Este fue el segundo problema a resolver. Se requería de un método que
encontrara la esfera de menor radio capaz de envolver a las dos esferas dadas.
17
De la misma manera para este problema propusimos tres métodos a los cuales les
llamamos Radio mayor, Máximos y mínimos, Vectorización. Al igual que en el
problema anterior, la decisión se tomo después de probar los métodos con varias
muestras de pares de esferas. Cada uno de estos métodos se describe en la
sección 4.3.
Como colocar los triángulos en el nivel de hojas de la estructura jerárquica
Al recibir las mallas que modelan los objetos, nada nos garantiza que los
triángulos traigan un orden determinado en la lista.
Uno de las características de los algoritmos que utilizan estructuras jerárquicas es
ir quitando aquellas partes del objeto donde no existe probabilidad de intersección,
conservando solamente las áreas de mayor posibilidad. Por lo que colocar
adecuada a los triángulos en el nivel de hojas ayudara a que esta técnica nos
permita llegar a la verificación de nivel de hojas solo en aquellos casos en donde
sea necesario.
1 2 3 0
5 6 7 4
1 a
2 b c
3 d e f g
4 0 1 2 3 7 4 5 6
Figura 4.1. Estructura jerárquica del tetraedro con un ordenamiento en el nivel de hojas
En la figura 4.1, observamos que el tetraedro esta presentando una posible
colisión con el cubo en la parte superior, si la estructura jerárquica en su último
nivel se encuentra ordenada como se muestra a la derecha, el método podaría
toda la rama c, ya que la esfera c cubre a los todos los triángulos de la parte
18
inferior del tetraedro, los cuales no presentan intersección alguna con los
triángulos que pertenecen al cubo.
1 2 3 0
5 6 7 4
1 a
2 b c
3 d e f g
4 0 6 2 4 7 3 5 1
Figura 4.2. Estructura del tetraedro sin ordenamiento en el nivel de hojas
Por otro lado, si no hiciéramos ningún ordenamiento sobre los triángulos que
recibimos de la malla, el método no podría podar de la misma manera ya que las
esferas b y c tiene triángulos que pertenecen a la parte superior e inferior del
tetraedro. Esto puede observarse en la figura 4.2. El algoritmo intentaría con el
siguiente nivel con las esferas d, e, f y g, pero estas también cubren triángulos de
ambas partes. El algoritmo tendría que ir hasta el último nivel donde se encuentran
las esferas que cubren a los triángulos de la malla y tendrá que verificar todos
contra todos, lo que provocara que el tiempo de respuesta sea mayor.
Este ordenamiento se explica en la sección 4.4.2
A continuación describiremos cada uno de los métodos propuestos y
seleccionados para resolver los problemas descritos anteriormente.
4.2 ESFERA DE MENOR RADIO
El primer problema de la etapa de preprocesamiento fue encontrar el método que
nos calculara la esfera de menor radio para cubrir un triángulo.
Los métodos sobre los que se experimento fueron:
• Baricentro
• Máximos y mínimos
• Lado Mayor
19
BARICENTRO
El baricentro es el punto de corte de las medianas. Las medianas son las rectas
que unen un vértice con el punto medio del lado opuesto.
figura 9. Baricentro de un triángulo
Sea un triángulo cuyos vértices son:
V 1( x1, y1) V 2( x 2, y 2 ) V 3(x3, y3)
El Baricentro del triángulo se obtiene como el promedio de las coordenadas en X y
el promedio de las coordenadas en Y
x1 + x 2 + x3 y1 + y 2 + y3
B ,
3 3
Obtenido el baricentro del triángulo, se determina cual es la distancia mayor entre
el baricentro y los tres vértices y esa distancia se toma como el radio de la esfera.
Radio = Dis _ mayor (d (B, V 1), d (B, V 2 ), d (B, V 3))
Las pruebas se realizaron en 2D y posteriormente en 3D, un ejemplo en 2D de ello
se muestra en la figura 4.3.
figura 4.3. Esfera generada por Baricentro en 2D
20
MÁXIMOS Y MÍNIMOS
El método de máximo y mínimos consiste en obtener la caja envolvente del
triángulo para calcular el punto central de la misma.
figura 4.4. Caja envolvente de un triángulo
El punto central de la caja envolvente se calcula como:
max x + min x max y + min y
cx = cy =
2 2
pc = (cx, cy )
Obtenido el centro de la caja (pc), se obtiene el radio para la esfera, determinando
la distancia a cualquiera de los vértices de la caja.
vc = (min x, min y )
Radio = dis ( pc, vc )
De igual forma, las pruebas se realizaron en 2D y posteriormente en 3D, un
ejemplo de ello en 2D se muestra en la figura 4.5.
figura 4.5. Esfera generada por Max. y Mín. en 2D
21
LADO MAYOR
El método del lado mayor se basa en la longitud de los lados del triángulo. Primero
se determina cual es el lado de la longitud mayor.
figura 4.6 Lado mayor de un triángulo
lm = long _ mayor (l1, l 2, l 3)
Determinado el lado mayor (lm) del triángulo, se obtiene el centro de la esfera (ce)
que es el punto medio de este lado.
x1 + x 2 y1 + y 2
ce = ,
2 2
El radio de la esfera se calcula, obteniendo la distancia de ce al cualquiera de los
vértices de los que forma parte este lado, o bien como la mitad de la longitud del
lado.
radio1 = lm
2
Este radio se tomará como válido si la distancia del centro de la esfera al otro
vértice que no forma parte del lado mayor es menor, en caso contrario, el radio
será la distancia del centro al vértice (v) que no pertenece al lado de mayor.
radio 2 = d (ce, v )
Radio = Dis _ mayor (radio1, radio 2 )
Las pruebas realizadas para estos métodos fueron en 2D y posteriormente en 3D.
22
figura 4.7. Esfera generada por el lado mayor en 2D
A continuación se muestran dos ejemplos en 3D sobre los tres métodos
anteriores, se genera un triángulo aleatoriamente y se le aplican los tres métodos.
En este primer ejemplo se muestra en 3D y en forma conjunta los tres métodos
que calculan la esfera que cubre al triángulo, donde el color de la esfera indica
cual es el método con el cual fue generada, el rojo corresponde a Baricentro, el
verde Lado Mayor y el azul a Max y Min.
figura4.8 El valor del radio de cada una de las 3 esferas generadas por los tres métodos en 3D
23
Otro ejemplo se muestra a continuación
figura 4.9 El valor del radio de cada una de las 3 esferas generadas por los tres métodos en 3D
figura 4.10 El valor del radio de cada una de las 3 esferas generadas por los tres métodos en 3D, y
se muestra la esfera generada por ellos en forma separada.
De las pruebas realizadas a los tres métodos se decide que método que genero
las esferas de menor radio fue el de Lado Mayor, como se reporta en la tabla del
apéndice A, por lo que será éste el que se utilice para resolver el problema.
24
4.3 ESFERA QUE CUBRE A DOS ESFERAS
Otro problema a resolver fue encontrar el método que calcule la esfera de menor
radio que cubra dos esferas cualesquiera, para ello se probaron tres métodos:
• Radio mayor
• Máximos y mínimos
• Vectorización
RADIO MAYOR
Este método obtiene la esfera basándose en la distancia entre sus centros y el
radio de la esfera mayor.
Primero obtiene la distancia entre los centros de las esferas.
Sean c1 y c2 los centros de las esferas y r1 y r2 los radios de las esferas,
respectivamente
Se obtiene la distancia que existe entre los dos centros
d = Dis (c1, c 2 )
Se verifica cual radio es el mayor
rm = Radio _ mayor (r1, r 2 )
Se obtiene el centro de la esfera que cubre las otras dos esferas, éste se calcula
obteniendo el punto medio entre los dos centros de las esferas
x1 + x 2 y1 + y 2
ce = ,
2 2
Y por último se obtiene el radio de la esfera que cubre a las dos esferas
radio = d 2 + rm
Este método genera una esfera cuya dimensión garantiza cubrir a las dos esferas
dadas, pero esta esfera no será de radio menor.
25
Un ejemplo de este método en 2D se muestra en la figura 4.11, el valor del radio y
el centro de las esferas se indican a la izquierda, las esferas de color negro y gris
son las esferas a las que se les calculará la esfera envolvente.
figura 4.11 A la izq. Se presentan el centro y el radio de las esferas a cubrirse y a la der. los
mismos parámetros para la esfera que las envuelve utilizando el método de radio mayor.
MÁXIMOS Y MÍNIMOS
Este método calcula la caja envolvente que cubre a las dos esferas.
figura 4.12. Ejemplo de la caja envolvente para 2D y 3D
Obteniendo los valores máximos y mínimos en X, Y en 2D y X, Y, Z en 3D.
Posteriormente se calculan las coordenadas del centro de la caja, el cual será el
centro de la nueva esfera.
max x + min x max y + min y
cx = cy =
2 2
pc = (cx, cy )
26
Obtenido el centro de la caja, se obtiene el radio para la esfera determinando la
distancia a cualquiera de los vértices de la caja.
vc = (min x, min y )
Radio = dis ( pc, vc )
Un ejemplo de este método en 2D se muestra a continuación.
figura 4.13. A la izq. Se presentan el centro y el radio de las esferas a cubrirse y a la der. los
mismos parámetros para la esfera que las envuelve utilizando el método de máximos y mínimos.
VECTORIZACIÓN
Este método lo que hace es prolongar la línea recta que forman los centros de las
esferas y localizar el punto en el que intersecta con la superficie de las esferas,
obteniendo con ello el diámetro de la esfera que cubre a ambas esferas, figura
4.14.
C1
P1 d
C2
P2
figura 4.14. Prolongación de la línea recta que une los dos centros, hasta unirla con los límites de
las esferas
27
Después de haber obtenido los puntos de la recta prolongada, se calcula el centro
de la esfera como el punto medio de los puntos calculados.
x1 + x 2 y1 + y 2
ce = ,
2 2
Se calcula la distancia que existe entre estos dos puntos para determinar con ella
el radio de la esfera.
d = Dis( p1, p 2 )
Y por último se obtiene el radio de la esfera como:
radio = d 2
Un ejemplo en 2D se muestra a continuación en la figura 4.15.
figura 4.15 . A la izq. Se presentan el centro y el radio de las esferas a cubrirse y a la der. los
mismos parámetros para la esfera que las envuelve utilizando el método de Vectorización.
Este método demostró en las pruebas, ser el más eficiente de los tres ya que la
esfera generada por él, es la de menor radio, así como se muestran en el
apéndice B, estos tres métodos fueron probados en 2D y 3D.
28
Un ejemplo de los tres métodos en 3D se muestra a continuación.
figura 4.16. El valor del radio generado por tres métodos en 3D, para la esfera que cubre otras dos
figura 4.17. El valor del radio generado por tres métodos en 3D, para la esfera que cubre otras
dos, mostrándose las esferas de cada método separadamente.
29
4.4 ÁRBOL DE ESFERAS
Dos estructuras relacionadas para una eficiente detección de colisión son los
modelos jerárquicos y las representaciones envolventes.
La herramienta de detección de colisión que desarrollamos utiliza una estructura
jerárquica basada en un árbol binario y las representaciones envolventes están
basadas en esferas.
4.4.1 ÚLTIMO NIVEL
La primera parte para la construcción del árbol es la generación de las esferas del
último nivel, cubriendo con ellas la superficie del objeto con las esferas más
pequeñas.
Cada una de las esferas cubre una de las figuras geométricas que forman la
totalidad de la malla del objeto, el número de esferas del último nivel corresponde
con el número de figuras geométricas que forman al objeto.
Supongamos que nuestro objeto es un cubo el cual tiene 12 triángulos que
conforman su malla.
3
2
11 1 7
4
5
10 0 6
8 9
figura 4.18 El cubo en dos perspectivas
Se construyen las esferas que cubren a cada uno de los triángulos
1 3 5
0 2 4
7 9 11
6 8 10
figura 4.19 El último nivel del árbol (nivel de hojas) y su representación gráfica en el objeto.
30
El método que se utiliza para calcular las esferas es el del lado mayor descrito en
la sección 4.2. La construcción de esferas del último nivel consiste en tomar cada
uno de los triángulos que forman la malla y calcularles la esfera que los cubre, sin
considerar un orden especifico, figura 26.
4.4.2 ORDENAMIENTO DEL NIVEL DE HOJAS
Después de haber calculado las esferas del último nivel y antes de crear el
penúltimo nivel del árbol se aplicará un algoritmo para ordenar los triángulos.
El criterio del ordenamiento es el siguiente, para cada triángulo del nivel de hojas
• La hoja-esfera que se encuentra a su derecha contienen un triángulo que
tiene un lado adyacente a él.
• La esfera que cubre las dos hojas-esferas de los triángulos es la de menor
radio.
Es decir el triángulo colocado a la derecha tiene un lado en común con el triángulo
que esta colocado a la izquierda.
1
10 0
8
figura 4.20 Triángulo 0 y los triángulos que tiene un lado en común (adyacente), a él.
En la figura 4.20 se muestra a un triángulo, junto con los triángulos adyacentes a
él. Pero son tres, así que la pregunta es: ¿Cuál se consideraría para ser colocado
a la derecha?. Para esto se utiliza el segundo criterio.
31
1 Esfera que cubre triángulo 0
10 0 Esferas que cubren los triángulos 1, 8, 10
Esfera que cubre las esferas 0 y 1
8 Esfera que cubre las esferas 0 y 10
Esfera que cubre las esferas 0 y 8
figura 4.21. Triángulo con sus triángulos adyacentes y las esferas que los cubren
Para este segundo requisito se seleccionará al triángulo que cumpla que la esfera
que cubre a las dos esferas de ambos triángulos sea la de menor radio. En la
figura 4.21, vemos que la esfera de menor radio es aquella que cubre a las
esferas de los triángulos 0 y 1, por lo que el triángulo que se coloca a la derecha
del 0 será el 1.
La manera en la que se realiza el ordenamiento es la siguiente, de la lista de
triángulos que forman la malla que modela al objeto, se toma el primer triángulo de
esta la lista.
0
figura 4.22 Primer triángulo de la lista
Se localizan los triángulos que tengan un lado adyacente al él.
1
10 0
8
figura 4.23 Triángulo 0 con los triángulos que tiene un lado en común (adyacente)
32
Posteriormente se calcula para cada par de ellos (triangulo a tratar con sus tres
triángulos adyacentes) la esfera que cubre a las dos esferas de cada uno de los
triángulos, como lo muestra la siguiente figura.
1 Esfera que cubre triángulo 0
10 0 Esferas que cubren los triángulos 1, 8, 10
Esfera que cubre las esferas 0 y 1
8 Esfera que cubre las esferas 0 y 10
Esfera que cubre las esferas 0 y 8
figura 4.24. Triángulo y sus triángulos adyacentes, y las esferas que los cubren
De las esferas calculadas vemos que la esfera que cubre las esferas de los
triángulos 10 y 0, es la que presenta mayor radio, posteriormente la que cubre a
los triángulos 0 y 8, y la de menor radio es la que cubre a las esferas de los
triángulos 0 y 1. figura 4.24.
Entonces la esfera que contiene el triángulo 1 será la segunda hoja del árbol en el
primer nivel, ya que como se menciono antes la hoja que se colocará a la derecha
de otra será la que contenga a uno de sus triángulos adyacentes y además sea la
esfera de menor radio que cubra a las dos. Por lo tanto las dos primeras hojas del
último nivel serán las que se muestran en la figura 4.25.
1
0
figura 4.25. Primeras dos hojas del árbol
Ahora se hará lo mismo para el triángulo 1, primero se buscaran los triángulos que
tengan un lado adyacente a él, en esta ocasión sólo se encontrarán dos triángulos
ya que uno de los tres adyacentes al triángulo 1 es el 0 y este ya fue colocado en
el árbol.
En la siguiente figura se muestran los triángulos adyacentes al triángulo 1, los
cuales son el triángulo 2 y 6. La figura 4.26, esta mostrando los triángulos en un
33
mismo plano, pero solo es para fines de explicación, porque los triángulos se
toman con la orientación que presentan en el objeto
6 1
2
1
2
figura 4.26. Triángulo 0 con los triángulos que tiene un lado en común (adyacente) a él.
Los triángulos adyacentes al 1 son el 2 y el 6. Ahora se le calcula la esfera que
cubre a las parejas 2 y1 y a la pareja 1 y 6. figura 4.27
6
Esfera que cubre triángulo 1
1 Esferas que cubren los triángulos 2 y 6
2 Esfera que cubre las esferas 1 y 2
Esfera que cubre las esferas 1 y 6
figura 4.27 Triangulo y sus triángulos adyacentes, y las esferas que los cubren
Ahora el triángulo 2 es el que asociado con el triángulo 1 generan la esfera de
menor radio, por lo que el siguiente triángulo a colocarse en el árbol es el triángulo
2, esto se puede ver en la figura 4.28.
1
0 2
figura 4.28 Primeras tres hojas del árbol
Lo mismo sucederá con el triángulo 2, y así sucesivamente hasta quedar
conformado el nivel de las hojas, como se muestra a continuación en l figura 4.29.
1 3 5 6 9 10
0 2 4 7 8 11
figura 4.29. Nivel de hojas del árbol
34
4.4.3 NIVELES DEL PENÚLTIMO AL PRIMER NIVEL
Los siguientes niveles son construidos de la forma siguiente, una vez calculado el
nivel de hojas o último nivel, el penúltimo nivel se forma uniendo por pares el
último nivel empezando de izquierda a derecha.
1
0
figura 4.30. La esfera de un nivel superior cubre a dos esferas del nivel inferior
La esfera debe cubrir a las dos esferas del nivel inferior que esta uniendo, como
se muestra en la figura 4.30.
1 3 5 6 9 10
0 2 4 7 8 11
figura 4.31. Penúltimo nivel del árbol
En la figura 4.31, se muestra la estructura del árbol hasta el penúltimo nivel, así
como su representación a nivel del objeto.
35
Lo mismo se hará para el siguiente nivel, se unirán, por pares las esferas, de
izquierda a derecha.
1 3 5 6 9 10
0 2 4 7 8 11
figura 4.32 Siguiente nivel del árbol
figura 4.33 Nivel 3 y 4 de esferas
Como podemos observar en la figura 4.33, el nivel 3 cubre en su totalidad al nivel
4 de esferas, siempre se debe ir cubriendo el nivel inferior con las esferas del nivel
superior, ya que cada nivel, es un nivel de ajuste que representará al objeto en la
fase de verificación de colisión
Los siguientes niveles se crean de la misma forma.
36
Si al unir por pares, alguna de las esferas no puede formar par, entonces la esfera
del siguiente nivel tendrá la mismas características que su descendiente.
1 3 5 6 9 10
0 2 4 7 8 11
figura 4.34. Siguiente nivel del árbol y esferas
figura 4.35. Niveles 2 y 3 de esferas
En la figura 4.35 podemos observar como una de las esferas tiene el mismo
tamaño que su esfera hija. En el nivel 2, hay 2 esferas y el nivel 3 presenta 3
esferas, al no poderse unir por pares una de ellas, la esfera padre toma las
características de ubicación y tamaño de la esfera del nivel inferior.
El árbol se ira formando de nivel en nivel hasta llegar a la raíz, que tiene a la
esfera que cubre en su totalidad al objeto.
37
1 3 5 6 9 10
0 2 4 7 8 11
figura 4.36 Árbol que representa la estructura jerárquica del cubo y la esfera raíz
El nivel del árbol de cada objeto dependerá del número de triángulos que
conforman la malla que forma al objeto.
h = log2 n
Donde,
h es la altura del árbol
n es el número de triángulos que conforman el objeto
El árbol binario se crea de abajo hacia arriba “Bottom-up”
3
2
1 11 1
10 0
2
7
4
5
6
3 8 9
4
5 0
1
2
3
4
5
7
6
8
9
11
10
figura 4.37. Árbol construido del nivel más bajo hasta el primero
38
4.5 PSEUDOCÓDIGO. ETAPA DE PREPOCESAMIENTO
El siguiente pseudocódigo presenta la forma de construcción de la etapa de
prepocesamiento
Entrada: Malla de triángulos
Salida: Estructura del árbol
1. Genera_esferas(malla)
2. posicion[0] <-Triángulo[0]
3. trian <- Triángulo[0]
4. Para i = 1 a num_trian
a. adya = Localiza_adyacentes(trian)
b. Genera esf_cubre(trian,adya)
c. t_m <-Verifica menor_tamaño(trian,adya)
d. posicion[i] <- t_m
e. trian <- t_m
5. arbol <- Gen_sigu_nivel(posicion)
En el paso 1, se generan las esferas del nivel de hojas, entrando las mallas de
triángulos y obteniendo las esferas que cubren a cada uno de los triángulos
En el paso 2, se inicializa una lista llamada posición donde se irán colocando la
posición de cada triángulo en el árbol.
En el paso 3, trian tiene el triángulo a analizar
El paso 4, se realiza el ordenamiento del nivel de hojas.
• En el inciso a: se localizan los triángulos que tengan un lado adyacente a
él.
• En el inciso b: se generan las esferas que cubren a los pares de esferas
de los triángulos adyacentes.
• En el inciso c: se verifica la esfera de menor tamaño
• En el inciso d: el triángulo que cumple estas dos características (lado
adyacente y esfera de menor radio) se colocará en la siguiente posición
• En el inciso e: ahora se considera como trian el triángulo t_m que cumplió
con las dos características.
En el paso 5, se generan los niveles del penúltimo al primero.
39
4.6 CONCLUSIONES DEL CAPITULO
En este capitulo se describieron los problemas que tuvimos al desarrollar la
primera parte de nuestro algoritmo. Como ya se menciono en la sección 4.1,
fueron tres.
En el primero de ellos, en cual era calcular la esfera de menor radio que cubriese
a un triángulo, estudiamos tres métodos a los cuales como hemos mencionado
anteriormente en la sección 4.2, le dimos los nombres de Baricentro, Máximos y
mínimos y Lado mayor, realizamos varias pruebas para determinar cual de ellos
sería el más óptimo, ninguno de los método demostró en las pruebas calcular
siempre la esferas de menor radio que cubriese a un triángulo, esto nos llevo a
decidirnos por el método que en la totalidad de las pruebas, fue el que obtuvo en
la mayoría de las veces la esfera de menor radio, el resultado de las pruebas se
muestra en el apéndice A. El método que implementamos en nuestro algoritmo fue
el que llamamos lado mayor.
Para el segundo problema, realizamos pruebas con tres métodos los cuales ya
fueron descritos en la sección 4.3, Radio Mayor, Máximos y mínimos y
Vectorización. Con estos tres métodos también realizamos pruebas para
determinar cual sería el óptimo e implementarlo en nuestro algoritmo. Las pruebas
demostraron que ninguno obtuvo al cien por ciento de cada prueba la esfera de
menor radio que cubriese a dos esferas, por que implementamos el que en la
mayoría de las pruebas, obtuvo el mayor número de veces la esfera de menor
radio, pueden observar los resultados de estas pruebas en el apéndice B.
El tercer problema al que nos enfrentamos fue decidir como colocar los triángulos
en el nivel de hojas del árbol binario, implementamos la forma descrita en la
sección 4.4.2. La malla de triángulos, no tiene un ordenamiento, es importante
considerar uno, para colocar los triángulos en el último nivel de la estructura.
Debemos garantizar que una rama del árbol tiene los triángulos que forman una
parte del objeto. Si ordenamos los triángulos de un conejo de tal forma que una
rama de la estructura jerárquica tiene los triángulos de la oreja izquierda y otra
rama tiene los triángulos de la oreja derecha. Y supongamos que la oreja derecha
esta en colisión con algún objeto, podemos podar la rama que contiene la oreja
izquierda, sin ningún problema. Pero en el caso que ambas ramas tuvieran
triángulos de ambas orejas no podríamos podar el árbol más rápidamente.
Es importante este ordenamiento, nosotros estamos proponiendo que los
triángulos al irse formando tengan a sus lados triángulos adyacentes, para
garantizar que las esferas están uniendo partes cercanas del objeto
40
