Deteccao de Colisao de Objetos em Ambientes Virtuaispara Treinamento Medico Utilizando JOGL

Marcello KeraUniversidade Federal do ParanaDepartamento de Informatica

Curitiba-PR, Brasil, 81531-990

Fatima L. S. NunesUniversidade de Sao Paulo

Escola de Artes, Ciencias e HumanidadesSao Paulo-SP, Brasil, 03828-000

Helio PedriniUniversidade Estadual de Campinas

Instituto de ComputacaoCampinas-SP, Brasil, 13084-971

Resumo

O treinamento de procedimentos medicos pode ser benefi-ciado com o uso de ambientes virtuais interativos que si-mulam com realismo as acoes do usuario. A simulacaodeve emitir respostas rapidas ao usuario relativas ao en-contro de objetos, deformacao, restricao de movimentoou mesmo produzir forcas e vibracoes. Este artigo des-creve a criacao de um prototipo de ambiente virtual paratreinamento medico. Classes e metodos sao projetadose implementados no ambiente por meio da linguagem deprogramacao Java. A detecao de colisao entre objetos ebaseada na subdivisao hierarquica do espaco com octrees.

1 Introducao

Detectar uma colisao e verificar a aproximacao entre ob-jetos de um ambiente virtual. Essa aproximacao deve ser su-ficientemente pequena a ponto de possibilitar a ocorrenciade uma sobreposicao entre objetos, fornecendo assim ummaior realismo as aplicacoes de Realidade Virtual (RV).

A deteccao de colisao e um dos itens mais complexose dependentes das informacoes de interacao monitoradasem um Ambiente Virtual (AV). O problema da deteccaode colisao e fundamental em qualquer simulacao do mundofısico, sendo estudado por diversas comunidades, incluindorobotica, computacao grafica e geometria computacional.

A criacao de um metodo de deteccao de colisao de ob-jetos e um grande desafio, pois na literatura existem muitosmetodos propostos e com boa qualidade. Apesar do grandenumero de algoritmos para a deteccao de colisao, nao ha

ainda um metodo que combine satisfatoriamente dois as-pectos importantes: precisao e desempenho.

Com o proposito de simular um ambiente para treinarprofissionais da area da saude, este trabalho descreve acriacao de um prototipo de ambiente virtual implementadoem linguagem de programacao Java. A ferramenta e debaixo custo, possui alta precisao na deteccao de objetos eapresenta bom desempenho computacional, conforme de-monstrado nos resultados experimentais.

A secao 2 descreve alguns metodos de deteccao de co-lisao de objetos encontrados na literatura. A metodologiaproposta e apresentada na secao 3. Os resultados obtidos apartir da metodologia sao ilustrados e discutidos na secao 4.Finalmente, a secao 5 apresenta a conclusao do trabalho ealgumas sugestoes de trabalhos futuros.

2 Metodos de Deteccao de Colisao

Devido ao fato de que a deteccao de colisao depende ex-tremamente das informacoes provenientes das interacoes dousuario com o AV, algoritmos eficientes devem ser desen-volvidos para alcancar precisao com tempos de respostasaceitaveis. Esse requisito pode demandar programas es-pecıficos para gerenciar as informacoes de interacao, en-volvendo rotinas de controle e computacao grafica [13].

As secoes a seguir descrevem sucintamente um conjuntode algoritmos de deteccao de colisao existentes na literaturae agrupados por tipo de algoritmos.

2.1 Volumes Limitantes

A deteccao de colisao por volumes limitantes sao algo-ritmos que utilizam primitivas simples para delimitacao do

espaco de colisao do objeto, tais como esferas, caixas ali-nhadas aos eixos (Axis-Aligned Bounding Boxes - AABB) ecaixa orientada (Oriented Bounding Box - OBB). A princi-pal ideia desse tipo de abordagem e verificar os pontos maisafastados do objeto e inserir a primitiva nesse espaco.

2.1.1 Caixas Envoltorias Alinhadas aos Eixos (AABB)

O algoritmo de caixas envoltorias alinhadas aos eixos (AxisAlign Bounding Boxes - AABB) verifica os dois pontos maisafastados do objeto e envolve esse objeto com uma caixa,alinhando-a com os eixos de coordenada do sistema [12,16]. A figura 1 mostra um exemplo do metodo de caixasenvoltorias alinhadas (AABB).

Figura 1: Exemplo do metodo AABB. Fonte: [9].

2.1.2 Caixas Orientadas (OBB)

O algoritmo de caixas orientadas ou OBB (Oriented Boun-ding Box) corresponde a uma caixa que possui sua propriaorientacao. A OBB e definida pelos seguintes atributos:centro, tres vetores unitarios que representam a direcao dacaixa e a extensao em cada direcao. A OBB verifica os pon-tos mais afastados do objeto para definir seu volume limitee faz com que esse volume se oriente pela forma do objetoe se encaixe de tal forma que sua area fique a mais proximapossıvel da forma do objeto [8].

Em relacao ao ajuste, a OBB apresenta resultados signifi-cativamente melhores do que uma AABB, porem, o calculode intersecao e muito mais complexo e lento, requerendo as-sim muito mais processamento comparado com as esferas ecom a AABB.

A figura 2 mostra a diferenca entre o envolvimento deuma AABB com relacao a uma OBB, bem como a diferencana orientacao dos eixos de coordenadas. A AABB e ali-nhada aos eixos de coordenadas espaciais e a OBB com seuseixos alinhados as coordenadas locais do objeto.

Figura 2: Objeto envolvido com (a) uma AABB e (b) umaOBB. Fonte: [3].

2.1.3 Esferas

Similar ao algoritmo AABB, o metodo de esferas (spheres)testa os pontos mais afastados do objeto e envolve o mesmocom uma esfera. Esferas envolventes sao representadas porum centro e um raio. Uma esfera e definida pelo conjuntode todos os pontos equidistantes de um ponto central.

A desvantagem e que esse metodo pode nao envolveradequadamente um objeto longo e fino, o que pode resul-tar em falsa deteccao de colisao. Nesses casos, um segundoteste poderia ser realizado.

2.2 Subdivisao Hierarquica do Espaco

Nesta abordagem, o ambiente e subdividido em umespaco hierarquico. Objetos no ambiente sao agrupados deacordo com a regiao em que se encontram.

Quando um objeto no ambiente se movimenta e trocade posicao, movendo-se para uma outra regiao do espaco,apenas os objetos do novo espaco precisam ser verificadosse colidem ou nao com o objeto em movimento (figura 3).

Figura 3: Metodo de subdivisao hierarquica do espaco.Fonte: [9].

O ambiente virtual pode ser subdividido utilizando-sealguns metodos conhecidos, tais como octrees, arvoresk-dimensionais e arvores de particionamento do espacobinario, descritos a seguir.

2.2.1 Octrees

Segundo Hearn e Baker [10], octrees sao estruturas dearvores hierarquicas em que cada no interno tem ate oito

filhos e e organizada para que cada no corresponda a umaregiao do espaco tridimensional. O esquema de codificacaodivide regioes de espacos tridimensionais, normalmente cu-bos, em octantes e armazena elementos em cada no daarvore. A figura 4 ilustra um espaco virtual particionadopor uma octree.

Figura 4: Representacao de espaco particionado por umaoctree. Fonte: [7].

2.2.2 Arvores k-dimensionais

Arvores k-dimensionais (K-d trees), em que k e o numerode dimensoes, sao estruturas de arvores multi-dimensionaisbalanceadas que particionam o espaco para organizacao depontos de um espaco k-dimensional [4].

Uma k-d tree usa apenas planos de divisao que sao per-pendiculares a um dos eixos de coordenadas do sistema,em contraste com uma arvore BSP, que pode se utilizar deplanos de divisao arbitrarios. Como consequencia, cadaplano de divisao deve atravessar um dos outros pontos daarvore [5]. A figura 5 mostra um exemplo de particiona-mento de espaco por arvores k-d.

Figura 5: Representacao de espaco 2D particionado poruma k-d tree. Fonte: [9].

2.2.3 Arvores de Particionamento do Espaco Binario

A arvore de particionamento do espaco binario (BSP tree,do ingles binary space partitioning tree) representa uma di-visao recursiva hierarquica ou a subdivisao de um espacon-dimensional em subespacos convexos. A construcao daBSP tree e um processo que considera um subespaco e oparticiona por qualquer hiperplano que intersecta o interiordo subespaco. O resultado disso sao dois novos espacos que

podem ser particionados novamente por um metodo recur-sivo.

As BSP trees podem ser usadas desde a remocao de su-perfıcies escondidas e hierarquias de ray tracing ate a mo-delagem de solidos e o planejamento de um movimento deum robo [15]. A figura 6 mostra o exemplo de uma BSPtree no espaco bidimensional.

Figura 6: Espaco particionado por uma BSP tree. Fonte: [9].

2.3 Subdivisao Hierarquica do Objeto

Na subdivisao hierarquica do objeto, este e subdivididoem regioes, sendo que a deteccao de colisao e feita quandouma dessas regioes e intersectada por um outro objeto.

A hierarquia de volumes envolventes e baseada em doistipos de nos. Nos internos e nos folhas. Cada no, indepen-dentemente do tipo, possui um volume envolvente associ-ado. Nos folhas possuem volumes envolventes que englo-bam somente a geometria (ou seja a malha de triangulos)enquanto nos internos possuem volumes envolventes queenglobam todos os volumes envolventes de seus filhos. Porisso, pode-se descartar todos os filhos se o volume envol-vente do no pai nao colidir com outro no.

Algumas abordagens para subdivisao hierarquica do ob-jeto sao sphere-trees, AABB-trees e OBB-trees. Ha outrosalgoritmos conhecidos e eficientes encontrados na litera-tura, mas sao variacoes desses metodos fundamentais uti-lizados em deteccao de colisao.

2.3.1 Sphere-trees

O metodo de sphere-trees e um dos mais simples, sendoesse um motivo por torna-lo muito popular em aplicacoes deRV. Hubbard [11] implementa esse metodo, onde o objetoe envolvido por uma esfera (nıvel 0) e, recursivamente, hauma uniao sucessiva de mais esferas fazendo com que elasse aproximem ao maximo da resolucao do objeto. Conside-rando que as esferas sao invariantes quanto a rotacao, entao,para um objeto rıgido, a hierarquia e construıda por meiode um pre-processamento e as transformacoes da hierarquiasao as mesmas transformacoes lineares aplicadas ao objeto.A figura 7 mostra um exemplo de sphere-trees.

Figura 7: Exemplos do metodo de sphere-trees. Fonte: [6].

2.3.2 AABB-trees

O metodo de arvores AABB basicamente divide o objetoem sub-regioes a partir de um AABB (no raiz). Uma caixaAABB nao pode ser colocada livremente no objeto, pois oAABB e orientado aos eixos de coordenadas do espaco.

Uma arvore AABB e construıda de cima para baixo (top-down), por subdivisoes recursivas. Em cada passo da re-cursao, o menor AABB do conjunto de primitivas e com-putado e o conjunto e dividido respeitando-se a escolha domelhor plano. O processo continua ate que cada subcon-junto contenha apenas um elemento. A imagem 8 mostra asequencia para construcao de uma AABB-tree.

Figura 8: Construcao de uma AABB-tree. Fonte: [8].

2.3.3 OBB-trees

OBB-tree e uma arvore onde cada no possui uma OBB. Autilizacao de arvores OBB representa um ganho em relacaoao desempenho e precisao na deteccao de colisao. ArvoresOBB garantem um ajuste muito superior em relacao a ou-tros volumes envolventes.

A construcao de uma arvore OBB possui dois compo-nentes basicos: a colocacao da OBB ao redor do grupo depolıgonos para que estes tenham um encaixe justo e o agru-pamento das OBB encaixados em uma arvore hierarquica.A figura 9 mostra a construcao de uma arvore OBB.

3 Metodo Proposto

O metodo de colisao utilizado no ambiente virtual foibaseado no algoritmo desenvolvido por Antonio [1]. Paraa construcao do AV, utilizou-se o pacote JOGL (JavaOpenGL). A figura 10 mostra um diagrama com as princi-pais etapas do metodo de colisao desenvolvido, enumeradasa seguir:

Figura 9: Exemplo do metodo de OBB-trees em 2D.Fonte: [9].

• os objetos sao inseridos na cena, ou seja, no AV;

• o AV ou cena e dividido em octantes, utilizando o con-ceito de divisao espacial (octrees);

• os objetos na AV sao distribuıdos nos octantes;

• a cada movimento do objeto e utilizada a computacaoincremental da distancia para verificar se os objetosestao no mesmo octante;

• teste de colisao face a face.

Figura 10: Passos do metodo de colisao.

Na classe de deteccao de colisao sao implementadasfuncoes (metodos) que sao responsaveis por carregar os ob-jetos na cena, dividir a cena em octantes, dividir objetos oufaces nos octantes, calculo de colisao e verificacao da co-lisao entre os objetos.

Para carregar um objeto na cena, o ambiente desenvol-vido utiliza modelos triangulares no formato OBJ [14] ou3ds [2], que consiste em um arquivo contendo informacoesbasicas do modelo 3D: vertices, faces e normais. Com essesdados e possıvel recriar o modelo no ambiente. Os verticessao guardados em uma lista que contem as coordenadas x,y e z.

Apos carregado o objeto na cena, a mesma e dividida emoito partes (octantes). Essas partes servirao para identifi-car onde o objeto (ou parte dele) se encontra, facilitando averificacao da colisao. A divisao da cena e feita de acordocom a posicao dos objetos, tal que os objetos mais afasta-dos na cena sao detectados e suas coordenadas maximas emınimas sao usadas na subdivisao. A figura 11 ilustra adivisao da cena.

Figura 11: Divisao do espaco utilizando octree.

Apos a divisao da cena, realiza-se o posicionamento dosobjetos em cada octante. Se um objeto ocupar mais que umoctante, as faces do objeto sao divididas entre os octantes.Ao movimentar um objeto na cena e possıvel verificar comoesses octantes sao dinamicamente alterados. Se dois objetosestiverem no mesmo octante, faz-se uma nova subdivisaodo mesmo ate que o objeto ou suas faces nao compartilhemesse octante com outro objeto.

Para verificar a colisao entre os objetos, o metodo in-clui os seguintes passos: verificacao da coplanaridade dostriangulos, teste entre os pontos dos triangulos e teste deum ponto sobre o triangulo. Esse metodo foi baseado noalgoritmo de Antonio [1].

Os pseudocodigos de 1 a 4 mostram os passos seguidospara a obtencao da colisao no ambiente virtual.

inıcioMain() {constroiCena();enquanto renderCena faca

divideCenaEmOctree();renderizaCena();verificaColisao();

fim}

fimAlgoritmo 1: Modulo principal.

inıciodivideCenaEmOctree() {calculaRaizOctree;subdivideOctree posicionaFacesNaOctree;}

fimAlgoritmo 2: Modulo de divisao da cena e posiciona-mento de faces na octree.

inıcioverificaColisao() {verificaAlturaMaximaOctree;verificaDiametroOctree;verificaColisaoFaceFace();}

fimAlgoritmo 3: Modulo de verificacao de colisao.

inıcioverificaColisaoFaceFace() {verificaCoplanaridade;testaArestasEntreTriangulos;testaPontoNoTriangulo;}

fimAlgoritmo 4: Modulo de colisao baseado em [1].

4 Resultados Experimentais

O ambiente desenvolvido neste trabalho visa a simulacao doprocedimento de puncao mamaria em exames de biopsia, o qualconsiste na extracao de pequenas partes de tecidos do orgao emquestao para auxiliar a elaboracao do diagnostico medico. A par-tir dessa experiencia, pretende-se tornar possıvel a utilizacao doambiente em novas aplicacoes para treinamento medico.

4.1 Criterios para os Testes

Pela possibilidade de o ambiente possibilitar a visualizacao dosobjetos no ambiente com as malhas poligonais destacadas (wire-frame) e esse recurso pode alterar a media de quadros por segundo(FPS, frames per second), os testes tambem mostraram a media deFPS com a visualizacao das malhas poligonais.

Os objetos carregados na cena podem estar no formato 3ds [2]ou obj [14], consistindo em informacoes sobre os vertices, faces evetores normais dos polıgonos que formam os objetos.

Duas plataformas diferentes foram testadas nos experimentospara avaliar o desempenho do metodo: um computador com sis-tema operacional Windows Vista com processador Intel Core2DuoT5250 1.50 GHz, 3 GB de memoria RAM e placa de vıdeo Intelx3100 on-board e um computador com sistema operacional Li-nux Debian 2.6.18-6-686 com processador Intel Pentium 4 Xeon3.20GHz, 2GB de memoria RAM e placa de vıdeo G-Force4MX4000 de 64 bits.

4.2 Deteccao de Colisao entre Objetos

Esta secao apresenta os resultados do metodo de colisao de ob-jetos nas plataformas citadas anteriormente. Duas categorias deobjetos foram utilizadas nos testes, a primeira formada por objetosregulares simples e a segunda formada por objetos complexos comgrande numero de faces poligonais.

4.2.1 Testes com Objetos Simples

Estes testes utilizaram objetos com baixo numero de vertices efaces, a saber: Diamante com 18 vertices e 8 faces e Toroide com119 vertices e 140 faces. A figura 12 mostra os dois objetos emsuas posicoes iniciais na cena apos serem carregados no ambiente.

Figura 12: Objetos simples em estado inicial.

Na plataforma Windows, a taxa media de renderizacao paraesses objetos estaticos na cena e sem colisao foi igual a 62 FPS ena plataforma Linux, a taxa media de renderizacao foi de 61 FPS,ou seja, taxas similares.

Desde a etapa inicial da aplicacao que e carregar o objeto nacena, o calculo da divisao do espaco (octree) e realizada. Essecalculo consiste em verificar a posicao dos objetos na cena e di-vidir a mesma em octantes, posicionando os objetos ou parte dele(faces do objeto) nos octantes.

Com a movimentacao de um objeto em direcao a outro objeto,a aplicacao pode dividir a cena em espacos menores com a octreeate a possıvel colisao entre os objetos (verificacao face a face).A figura 13 ilustra a aproximacao dos objetos e a subdivisao doespaco, mas sem haver a colisao.

Figura 13: Movimentacao de um objeto na cena.

A taxa media de renderizacao apenas com o deslocamento dosobjetos sem se colidirem e apenas com o recalculo do particio-namento da cena foi igual a 62 FPS nas plataformas Windows eLinux, portanto, taxa similar para o teste anterior com os objetosestaticos na cena.

Como um dos objetos escolhidos possui um orifıcio (Toroide),fez-se se entao um teste no qual se introduz o Diamante nessalacuna para verificar se ha uma falsa deteccao de colisao. Arealizacao desse teste e importante pois um grande desafio encon-trado nos metodos de colisao e a deteccao de colisao em objetosconcavos, onde o espaco interno do objeto pode nao colidir comoutro objeto.

Na figura 14, o objeto Diamante esta localizado exatamente nocentro do objeto Toroide, demonstrando, assim, que a verificacaode colisao e realizada corretamente.

Figura 14: Objetos sem colisao sobrepostos com octree.

Tem-se que, durante todo o processo de movimentar o objetoDiamante ao orifıcio do objeto Toroide, nao ha uma diminuicaona quantidade media de renderizacao tanto para a plataforma Win-dows quanto para plataforma Linux, mantendo-se assim a mediade 62 FPS para ambas as plataformas.

E importante ressaltar que a movimentacao do objeto Diamanteatraves do objeto Toroide tem a mesma media de processamentoque a simples movimentacao do objeto Diamante pela cena.

A deteccao de colisao e indicada para o usuario atraves de umamensagem na cena, indicando se houve ou nao a colisao dos ob-jetos na cena. O processo de detectar colisao no ambiente segueos passos de subdivisao hierarquica do espaco, distancia entre osobjetos e verificacao face a face.

A figura 15 ilustra a colisao dos objetos na cena, cuja taxamedia de renderizacao foi de 62 FPS na plataforma Windows ede 60 FPS na plataforma Linux.

A figura 16 ilustra uma ampliacao da regiao de colisao. Nestavisualizacao e possıvel mostrar a proximidade atingida entre osobjetos para se obter uma resposta de colisao, tendo assim umaprecisao bem proxima ao real.

4.2.2 Testes com Objetos Complexos

Nestes testes foram utilizados objetos para simulacao do proce-dimento de puncao em exames de biopsia. Este procedimentoconsiste na extracao de pequenas partes de tecidos do orgao sobinvestigacao. O material coletado e entao enviado para examespatologicos para a elaboracao do diagnostico.

Figura 15: Objetos se colidindo.

Figura 16: Deteccao de colisao com ampliacao.

Dois objetos foram modelados: um para representar o instru-mento medico (neste trabalho, uma Seringa) e o outro para re-presentar o orgao (neste trabalho, uma Mama). A quantidade depolıgonos presentes na cena foi de 964 vertices e 1.817 faces paraa Seringa e de 8.872 vertices e 17.490 faces para a Mama.

A figura 17 mostra os objetos em suas posicoes iniciais apos se-rem carregados no ambiente. Inicialmente, a taxa de renderizacaoesta em torno de 28 FPS na plataforma Windows e de 27 FPS naplataforma Linux.

Figura 17: Objetos em posicoes iniciais.

A figura 18 mostra os objetos na cena em posicao inicial com arepresentacao octree, onde se pode notar que, mesmo estando emsua posicao inicial, a aplicacao ja determina em qual octante cadaobjeto ou parte dele esta inserido. Pode-se observar que, ja nesteprimeiro momento, uma parte da mama estava no mesmo octanteque a seringa. Com isso, esse octante foi dividido em outros 8

octantes, fazendo com que cada octante contenha apenas partes domesmo objeto. A taxa media de renderizacao foi compatıvel coma mostrada na cena anterior de 28 FPS na plataforma Windows ede 27 FPS na plataforma Linux.

Figura 18: Objetos em posicoes iniciais com sobreposicaoda octree.

Ao apresentar os objetos com malhas poligonais visıveis, tem-se uma taxa media de 16 FPS na plataforma Windows e uma mediade 15 FPS na plataforma Linux. A figura 19 mostra a cena com osobjetos em suas posicoes iniciais.

Figura 19: Objetos em posicoes iniciais com malhas poli-gonais visıveis.

Havendo uma colisao entre os objetos, verifica-se uma taxa de24 FPS para a plataforma Windows e de 23 FPS para Linux. Afigura 20 ilustra o momento da colisao entre os objetos. A co-lisao e verificada apos a divisao recursiva dos octantes ate quese atinja um tamanho mınimo. Apos essa divisao, o calculo desobreposicao de faces e efetuado. Havendo colisao entre as facesou se um valor pre-especificado de distancia mınima for alcancadoentre as faces, entao a colisao e detectada.

A figura 21 mostra uma regiao ampliada proxima ao pontode colisao detectado pelo metodo proposto, podendo-se observara proximidade dos objetos. A figura 22 mostra uma ampliacaoda regiao de deteccao com as malhas poligonais visıveis. Nestavisualizacao, pode ser observada a colisao entre a extremidade doobjeto Seringa e a face do objeto Mama.

5 Conclusoes e Trabalhos Futuros

Este trabalho apresentou o desenvolvimento de um prototipode ambiente virtual interativo para treinamento medico. O desen-

Figura 20: Colisao entre os objetos com sobreposicao daoctree.

Figura 21: Detalhe da colisao.

Figura 22: Detalhe da colisao com malhas poligonaisvisıveis.

volvimento utilizou pacotes livres, abertos e multiplataforma.A subdivisao hierarquica do espaco baseada em octrees foi uti-

lizada na implementacao do metodo de deteccao de colisao dosobjetos. O metodo se mostrou preciso e com adequadas taxas derenderizacao, permitindo uma simulacao com realismo.

Embora os quesitos de precisao e desempenho tenham sidoadequadamente alcancados, novos testes devem ser realizados paraotimizar os metodos por meio da modificacao dos parametros uti-lizados. Pretende-se realizar testes em conjunto com profissionaisda area de saude para auxiliar na validacao das tecnicas e melhoraro realismo da simulacao. Finalmente, outra proposta de trabalhofuturo e a incorporacao de equipamentos nao convencionais, me-lhorando a interacao entre o usuario e o ambiente.

Referencias

[1] F. Antonio. Faster Line Segment Intersection, pages 199–202. Academic Press Professional, Inc., San Diego, CA, Es-tados Unidos, 1992.

[2] AutoDesk. Autodesk 3ds Max, 2008. http://usa.autodesk.com/adsk/servlet/index?siteID=123112&id=5659302.

[3] C. Basdogan and C.-H. Ho. Principles of Hap-tic Rendering for Virtual Environments, 2008.http://network.ku.edu.tr/∼cbasdogan/Tutorials/haptic tutorial.html.

[4] J. L. Bentley. Multidimensional binary search trees usedfor associative searching. Communications of the ACM,18(9):509–517, 1975.

[5] J. L. Bentley. K-d trees for semidynamic point sets. In SCG’90: Proceedings of the sixth annual symposium on Compu-tational geometry, pages 187–197, New York, NY, EstadosUnidos, 1990. ACM Press.

[6] G. Bradshaw and C. O’Sullivan. Sphere-tree Constructionusing Dynamic Medial Axis Approximation. In SCA ’02:Proceedings of the 2002 ACM SIGGRAPH/EurographicsSymposium on Computer animation, pages 33–40, NewYork, NY, Estados Unidos, 2002.

[7] S. Giesecke. Seminar Algorithmen fur Compu-terspiele: Raumliche Sortierung, 2008. http://www.vis.uni-stuttgart.de/eng/teaching/lecture/ws04/seminar spiele/bsp/.

[8] S. Gottschalk, M. C. Lin, and D. Manocha. OBBTree: AHierarchical Structure for Rapid Interference Detection. InSIGGRAPH’96: Proceedings of the 23rd Annual Conferenceon Computer Graphics and Interactive Techniques, pages171–180, New York, NY, Estados Unidos, 1996. ACM Press.

[9] S. Hadap, D. Eberle, P. Volino, M. C. Lin, S. Redon, andC. Ericson. Collision Detection and Proximity Queries.In SIGGRAPH’04: ACM SIGGRAPH 2004 Course Notes,page 15, Los Angeles, CA, Estados Unidos, 2004.

[10] D. Hearn and M. P. Baker. Computer Graphics, C Version.Prentice Hall, 1996.

[11] P. M. Hubbard. Collision Detection for Interactive GraphicsApplications. IEEE Transactions on Visualization and Com-puter Graphics, 1(3):218–230, 1995.

[12] J. T. Klosowski, M. Held, J. S. Mitchell, H. Sowizral, andK. Zikan. Efficient Collision Detection Using Bounding Vo-lume Hierarchies of k-DOPs. IEEE Transactions on Visuali-zation and Computer Graphics, 4(1):21–36, 1998.

[13] L. Machado, M. Zuffo, M. Moraes, and R. Lopes. Mo-delagem Tatil, Visualizacao Estereoscopica e Aspectos deAvaliacao em um Simulador de Coleta de Medula Ossea.In IV Simposio de Realidade Virtual, pages 23–31, Flo-rianopolis-SC, Oct. 2001.

[14] O’Reilly. Online Mirror of the Encyclopedia of GraphicsFile Formats. http://www.fileformat.info/format/wavefrontobj/.

[15] W. C. Thibault and B. F. Naylor. Set Operations on Polyhe-dra using Binary Space Partitioning Trees. ACM SIGGRAPHComputer Graphics, 21(4):153–162, 1987.

[16] G. van den Bergen. Efficient Collision Detection of ComplexDeformable Models using AABB Trees. Journal of GraphicsTools, 2(4):1–13, 1997.