Análise da detecção de colisões com coerência semântica em ambientes robóticos simulados

Análise da Detecção de Colisões com Coerência Semântica em Ambientes Robóticos Simulados Rodrigo Miguel, Marcelo da Silva Hounsell, Roberto Sílvio Ubertino Rosso Jr. LARVA – Laboratório de Realidade Virtual Aplicada, DCC – Departamento de Ciência da Computação, UDESC – Universidade do Estado de Santa Catarina. Campus Universitário “Avelino Marcante”, Bom Retiro, Joinville, 89223-100, Brasil [email protected], {marcelo,rosso}@joinville.udesc.br

Abstract - This article presents the application of a new concept for collision detection into robotic virtual environments. This concept, named Semantic Coherence, aims to make an earlier evaluation of the virtual environment as a mean to foresee true cases of non-collision or situations of major probabilities of collision. The proposed approach was implemented in two case study environments: (i) an isolated robot arm simulator and, (ii) a collaborative telerobotic environment. Functional tests have shown reduction on the number of paired tests for the first case but another rationale have to be applied to the second environment. It is concluded that Semantic Coherence brings benefit to robot environment but require careful planning and implementation.

I.

manipulados. Já o Collbot4us é uma evolução desse ambiente e apresenta em cena dois robôs que possuem um espaço de trabalho compartilhado, sendo que os robôs são controlados por dois operadores distintos, em computadores geograficamente separados. Além disso, podem existir em cena não apenas objetos fixos, mas também objetos móveis. Em termos de colisão estas características fazem uma grande diferença, pois no ambiente Virbot4u só podem ocorrer colisões do robô com os objetos fixos e entre os próprios elos do robô. No Collbot4us, além destas colisões também podem ocorrer colisões dos robôs com os objetos móveis na cena e entre os dois robôs. Imagens desses dois ambientes podem ser vistas na Fig. 1.

INTRODUÇÃO

O problema da detecção de colisão existe em toda aplicação gráfica que lida com vários objetos geométricos na mesma cena onde alguns possuem mobilidade, tais como simulações de robótica ou automação, ambientes de realidade virtual, animação por computador, etc. A detecção de colisão é o algoritmo responsável por (i) identificar se dois objetos da cena colidem e, (ii) identificar as condições da colisão (direções, momento, ângulo, etc.). É um problema que demanda esforço computacional, pois precisa avaliar a relação de todos os objetos com todos os demais, o que implica num crescimento exponencial da demanda computacional, diretamente relacionada com a complexidade da cena (número de objetos e número de triângulos constituintes destes objetos). O conceito apresentado neste artigo foi desenvolvido sobre dois simuladores do robô manipulador Scorbot ER-4PC, chamados de Virbot4u [1] e Collbot4us [2]. Estes ambientes são freeware e open source e simulam robôs com cinco graus de liberdade e foram modelados em X3D [3], uma linguagem que permite a modelagem geométrica através de objetos poliédricos. O modelo geométrico do simulador é carregado em um navegador web X3D a partir de uma aplicação Java. Estes ambientes podem ser executados via internet. Portanto, é necessário dispor-se de técnicas eficientes de detecção de colisão que diminuam a quantidade de testes efetuados entre pares de objetos, uma vez que os recursos computacionais são sempre finitos. O Virbot4u é um ambiente que possui apenas um robô e permite a criação de objetos virtuais fixos na cena para serem

Fig. 1. Simulador Virbot4u à esquerda e Collbot4us à direita.

Vários ambientes, em especial os ambientes que simulam cenas robotizadas, requerem que o simulador deva identificar principalmente se há ocorrência de colisão ou não, pois esta deve ser evitada a todo custo devido à segurança dos equipamentos e também dos operadores. Identificar a repercussão da colisão (como a forma da quebra da garra, o dano causado no produto, etc.) nem sempre é relevante. Isto se deve ao fato de que, em simuladores estão sendo testadas situações que devem ser evitadas na operação rotineira do equipamento. Apesar disso a detecção de colisão não é um recurso amplamente disponível nos simuladores encontrados na literatura, como é o caso do DLR apresentado por [4]. Este artigo discute a implementação da estratégia da Coerência Semântica em dois ambientes robotizados e está dividido como segue. A seção II apresenta uma pesquisa bibliográfica dos conceitos e técnicas relacionados à detecção de colisão. A seção III define o conceito de Coerência Semântica, as seções IV e V mostram a implementação nos dois ambientes. A seção VI mostra alguns resultados comparativos com outras abordagens de detecção de colisão.

II.

CONCEITOS RELACIONADOS

Na detecção de colisão entre os modelos geométricos dos objetos a complexidade do teste de força bruta, onde se testa todos os objetos contra todos os outros, é de O(n²), sendo n o número de objetos na cena. Diversos conceitos para a otimização dos testes de detecção de colisão podem ser encontrados na literatura. Em [5, 6] pode-se encontrar uma abordagem conhecida como Coerência Temporal. Este conceito explora o fato de que, em um ambiente dinâmico, as características dos objetos não mudam significativamente entre dois passos de tempo consecutivos. Portanto, pode-se tentar prever a situação, sem calculá-la efetivamente, e assim estimar quando ocorrerá colisão. Algumas técnicas que exploram o conceito de Coerência Temporal são a Sort Moving Boxes [7] e Sweep and Prune [8]. A Coerência Espacial [9, 10] consiste em uma otimização que decompõe ou divide o espaço ocupado pelos objetos, de forma que a colisão só precise ser checada entre objetos que estão na mesma célula de decomposição. Algumas técnicas que utilizam o conceito de Coerência Espacial são as divisões em grids e octrees [10], R-trees [11], BSP-trees [12] e árvores K-d [13]. Para melhorar ainda mais a eficiência do teste de colisão, ao invés de se considerar a geometria detalhada do objeto em si normalmente é utilizado seu volume envolvente [14], que consiste em envolver o objeto alvo do teste em um volume convexo de geometria mais simples. O teste de colisão é feito primeiramente no volume envolvente; caso o par de volumes testados não estejam se colidindo tem-se que as entidades envolvidas também não estão [15]. Por tratar-se de formas geométricas mais simples, a detecção de colisão nestes volumes é mais rápida. Os volumes envolventes mais utilizados são Esferas [14], Axis Aligned Bounding Boxes (AABB) [16] e Oriented Bounding Boxes (OBB) [17], mas existem também as representações por k-DOPs (Discrete Orientable Polytopes) [16], Envoltórios Convexos ou Convex Hull [18] e os Swept Volumes [19]. Pode-se verificar que quanto melhor o volume se ajusta ao objeto, melhor é a certeza no cálculo da colisão entre os volumes, mas a técnica requererá mais esforço computacional. Estes volumes podem envolver o objeto como um todo ou partes decompostas deste. A partir disto surge o conceito de hierarquia de volumes envolventes (HVEs). Esta hierarquia é representada na forma de uma árvore, onde a raiz é o volume envolvente do objeto inteiro e as folhas são os volumes envolventes de suas partes menores [20]. Os testes são efetuados recursivamente a partir da raiz da hierarquia. Apenas se os volumes envolventes raízes se colidem é que é necessário testar o próximo nível com os filhos do volume colidente. Dessa seqüência de testes surge uma árvore chamada de Árvore de Testes de Volumes Envolventes (ATVE). Com esta técnica é possível aumentar a precisão dos testes de colisão sem usar ainda o modelo geométrico do objeto.

O estudo das técnicas de otimização do cálculo de detecção de colisão evidencia o fato de que elas são soluções genéricas e, portanto não levam em consideração eventuais especificidades da cena. Como as cenas robotizadas têm características que repercutem diretamente sobre a eventual (ou não) colisão, aparece uma lacuna a qual [21] contribui com a proposição de uma nova técnica de otimização da detecção de colisão: a Coerência Semântica. III.

DEFININDO A COERÊNCIA SEMÂNTICA

A possibilidade de uma avaliação prévia (manual) do ambiente virtual como forma de identificar casos certos de não colisão ou situações de maior probabilidade de colisão pela avaliação de cada uma das funcionalidades e significados dos eventos contidos nos ambientes podem trazer informações valiosas que levem à redução do número de testes de colisão necessários. Entretanto, este tipo de análise não está contemplado nem na Coerência Temporal e nem na Coerência Espacial. A partir daí surge o conceito de Coerência Semântica, que é o uso do significado relativo que certos objetos têm em uma cena específica para auxiliar na tomada de decisões de otimização do cálculo de colisão. A partir do momento que a Coerência Semântica elimina testes desnecessários entre pares de objetos impossíveis de se colidirem e prioriza os testes entre pares de objetos com maior probabilidade de colisão, ela contribui para diminuir a quantidade de testes para a detecção de uma colisão, principalmente nos momentos onde a colisão efetivamente ocorre. Uma quantidade menor de testes leva, por sua vez, a um tempo de resposta também menor. O conceito de Coerência Semântica [21] não visa substituir nenhuma das técnicas apresentadas na seção anterior, e sim, complementá-las. Esta abordagem faz o descarte das colisões impossíveis de acontecerem e a priorização daquelas com maior probabilidade, a partir daí é necessário a utilização de um algoritmo que faça a detecção da colisão em si. Para a aplicação da Coerência Semântica parte-se do princípio de que todos os objetos serão testados contra todos os outros objetos da cena. Com isso obtém-se uma matriz triangular, chamada de Matriz de Priorização e Descarte (MPD), de tamanho n x n, sendo n o número de objetos presentes na cena. Uma das bases da Coerência Semântica é a priorização dos testes com maior probabilidade de ocorrência, então esta matriz será utilizada também como forma de ordenação dos testes de colisão. A ordenação dos objetos na MPD indica a ordem em que o teste de cada par será efetuado, conforme ilustra a Fig. 2, onde +P indica o par com maior probabilidade de colisão e -P o par com menor probabilidade de colisão. A segunda base, a de descarte das colisões impossíveis é realizada através de uma análise semântica da cena. Tal análise exige um conhecimento prévio do ambiente e das funcionalidades e características dos objetos envolvidos. O resultado da análise, ou seja, a lista de pares de objetos que

não precisam ser testados um contra o outro será aplicada na MPD.

Fig. 2. Matriz de priorização e descarte.

Esta ordenação da matriz atende à primeira base da Coerência Semântica, a de priorização dos testes com maior probabilidade. O descarte das colisões impossíveis não deve ser confundido com aquele que é feito pela Coerência Espacial. Este último é realizado através do cálculo da distância de separação entre os objetos, como no caso da subdivisão espacial do ambiente: os objetos que se encontrarem em células de divisão diferentes não precisarão ser testados. O descarte obtido pela Coerência Semântica é diferente. Tratase de uma decisão obtida através do conhecimento do significado e da posição relativa entre os objetos na cena. Um exemplo é o caso que ocorre entre os elos adjacentes de um braço robótico. Sabe-se antecipadamente que esses elos não colidirão entre si, portanto, é possível descartar esses testes. O descarte pode ser efetuado observando-se três características de cada par de objetos: 1) Mobilidade: pares formados por objetos que permanecem estáticos durante todo o tempo podem ter seus testes de colisão descartados. Afinal, enquanto permanecerem parados no mesmo lugar nunca irão se colidir. 2) Alcance: pares formados por objetos que nunca alcançarão um ao outro também podem ter seus testes de colisão descartados. Essa característica exige um conhecimento maior da cena e do comportamento dos objetos envolvidos. 3) Adjacência: pares de objetos que são elos adjacentes de uma mesma estrutura articulada rígida também podem vir a ser descartados, pois geralmente não se interceptam. Podem existir algumas exceções e em cada caso é necessária a avaliação heurística do implementador para decidir se determinado par se encaixa nesta característica ou não. A análise heurística exigida pela Coerência Semântica é particular ao ambiente em que se deseja implementá-la, portanto, a exploração desse conceito nos dois simuladores propostos exige análise e construção específicas para cada um deles. As duas seções seguintes mostram como foram feitas estas abordagens. IV.

CENÁRIO 1: VIRBOT4U

O Virbot4u foi demonstrado por Hoss [1] e simula um robô com cinco graus de liberdade, onde o corpo, o braço e o antebraço rotacionam em um eixo cada um e a garra rotaciona em dois eixos. Este ambiente permite a manipulação do robô através de Cinemática Direta, onde o usuário informa as

posições de cada parte do robô separadamente, Cinemática Inversa, onde o usuário informa a posição alvo do ponto distal da garra e as articulações se posicionam automaticamente de forma a atingir o alvo desejado, ou movimentação diretamente na interface 3D. Além disso, é possível manipular a garra com formas de abordagem prédefinidas ou com orientação fixa. As formas de abordagem referem-se ao posicionamento da garra para a manipulação de um objeto, que pode ser pela frente, por trás ou por cima do objeto. Este simulador permite também a criação de objetos virtuais fixos na cena. Para implementação da detecção de colisão no Virbot4u foi utilizado o volume envolvente OBB, pois se conhece antecipadamente as geometrias envolvidas, tanto dos objetos da cena quanto dos elos do próprio robô. O algoritmo utilizado para executar o teste de colisão entre duas OBBs é baseado no Teorema da Separação dos Eixos (Separating Axis Theorem – SAT) [22]. Para todos os membros do robô foram definidas HVEs de um único nível, com exceção da garra, que foi modelada com dois níveis da árvore, que é dividida em dedos, suporte dos dedos e eixo/servomotor da garra. Para detecção de colisão entre as hierarquias de volumes envolventes dos pares de objetos candidatos à colisão é utilizada uma ATVE. Os objetos dispostos sobre a mesa só se movem quando são manipulados pelo braço robótico. Portanto, o único objeto capaz de produzir uma colisão é o próprio robô. Com o objetivo de explorar a Coerência Espacial, a mesa de trabalho foi dividida em duas partes iguais, estando o robô ao centro da mesa. Desta forma, os testes das partes móveis do robô precisam ser realizados apenas contra os objetos fixos que estejam do mesmo lado da mesa no qual se encontra o braço manipulador. Para isto, é necessária a utilização de uma estrutura de dados representando o particionamento espacial da mesa, de forma a enumerar os objetos que estejam de um lado e outro da mesa. Assim, é possível saber quais os objetos candidatos à colisão em determinado momento. A configuração das estruturas de dados sofrerá alterações quando forem inseridos novos objetos no ambiente ou quando o robô movimentá-las para um novo local na mesa. É preciso atentar ao fato de que um objeto pode se encontrar em mais de uma lista se ele estiver posicionado sobre a região de fronteira da divisão da mesa. Para a aplicação do conceito de Coerência Semântica é necessário estudar o ambiente para que se possa obter o conhecimento necessário em relação ao significado e função dos objetos na cena. O que se conhece do ambiente virtual é que ele possui uma representação virtual do robô manipulador Scorbot ER-4PC sobre uma mesa na qual podem ser dispostos vários objetos a serem manipulados pelo braço robótico. Os objetos que podem ser dispostos sobre a mesa são fixos. Na cena pode-se encontrar além da mesa e dos objetos dispostos sobre ela, as cinco partes que compõem o robô:

base, corpo, antebraço, braço e garra, conforme pode ser visto na Fig. 3.

Fig. 3. Partes do robô manipulador: a) Base, b) Corpo, c) Braço, d) Antebraço, e) Garra.

Observando-se as três características importantes para a aplicação da CS, através de uma análise heurística do ambiente conclui-se: 1) Mobilidade: Existem alguns objetos fixos na cena, o que torna desnecessário qualquer teste de colisão entre eles ou seus volumes envolventes. Desta forma, podem-se eliminar os testes entre os pares: objeto-objeto, objeto-mesa, objetobase e mesa-base; 2) Alcance: As articulações do robô restringem alguns movimentos do mesmo de forma que alguns elos não podem colidir entre si. Nem o corpo do robô e nem o seu braço conseguem atingir a mesa; 3) Adjacência: Dois elos adjacentes de um robô articulado não se interceptam, como é o caso dos pares base-corpo, corpo-braço, braço-antebraço e antebraço-garra. A partir destas características é possível montar a MPD conforme demonstrado em [21]. Após a análise da Coerência Semântica, ficou constatado que o número total de testes eliminados é: 14 + 5n / 2 + n² / 2. (1) Sendo que, na detecção de força bruta, há um total de testes de: (n + 6)² / 2. (2) Onde n é o número de modelos geométricos que compõem a cena. V. CENÁRIO 2: COLLBOT4US A partir do Virbot4u desenvolveu-se o ambiente colaborativo Collbot4us [2]. Este ambiente não possui apenas um, mas dois robôs na cena. Estes dois robôs possuem uma área de trabalho comum, o que permite que eles colaborem na execução de tarefas. No ambiente Collbot4us existem objetos móveis na cena, de forma que possam ser simuladas operações de células de manufatura entre os robôs. Os objetos móveis inseridos no ambiente atravessam a cena em duas filas paralelas que passam próximas aos robôs. Esta montagem simula um ambiente de manufatura onde os objetos passariam próximos aos robôs manipuladores sobre esteiras ou suspensos em ganchos. Dessa maneira como estão

dispostos na cena só podem ser alcançados pela garra, antebraço e braço de cada um dos robôs. A detecção de colisão no Collbot4us é a mesma desenvolvida no Virbot4u, com diferenças apenas na exploração da Coerência Semântica. Ou seja, utilizam-se HVEs de OBBs e a Coerência Espacial é explorada dividindo-se a mesa em duas partes, desta forma os testes de colisão serão efetuados apenas entre os pares de objetos que estejam no mesmo lado da mesa. A evolução do ambiente de um para dois robôs colaborativos e, além disso, a possibilidade de existirem objetos móveis na cena exigiu uma evolução no conceito de Coerência Semântica. O conceito foi então reavaliado e algumas premissas foram estendidas de forma que se adequasse a um ambiente mais dinâmico e, desta forma, tivesse sua aplicabilidade ampliada. Através de uma análise heurística pôde-se concluir dois fatos que são fundamentais na priorização dos testes. A probabilidade de colisão de um objeto com os demais objetos da cena será mais alta quanto maior for a combinação de duas variáveis particulares do objeto envolvido: 1) Hd: heurística relativa ao deslocamento do objeto em um passo de tempo; 2) Hv: heurística relativa ao volume do objeto. Como o espaço percorrido pelos objetos varia com o decorrer do tempo, tem-se que a matriz deve ser dinâmica de forma que a ordenação de probabilidade seja atualizada a cada momento. Os objetos dispostos na MPD podem ser separados em três grupos de acordo com Hd: primeiro, o grupo de objetos móveis, com maior probabilidade de colisão; segundo, o grupo de objetos articulados, que se possuem uma movimentação mais restrita e, portanto menos probabilidade de colisão; e em terceiro o grupo de objetos estáticos, com menor probabilidade de colisão. Para a ordenação dos objetos dentro do grupo dos objetos móveis deve-se levar em conta Hd e Hv. A soma de Hd (deslocamento) por Hv (volume) forma o que pode ser chamado de arrasto. Quanto maior for o volume do arrasto, ou Swept Volume (SV), formado pelo deslocamento do objeto em cada passo de tempo, maior será a probabilidade deste colidir com outro objeto qualquer. Os objetos que não estiverem em movimento terão um SV igual ao seu próprio volume, e assim como os demais é este volume que será considerado para a ordenação. O que se pretende é que os objetos que ocupam um maior espaço na cena sejam testados prioritariamente, seja este espaço o volume do próprio objeto ou o volume do seu deslocamento em um passo de tempo. Entretanto há que se considerar que o cálculo do volume do arrasto de um objeto é complexo. Segundo [19] o cálculo do SV de um objeto pode ter complexidade combinatorial superior à quadrática. Alguns algoritmos têm sido propostos para resolver o problema do cálculo do SV [23, 24], entretanto “estes algoritmos podem levar alguns minutos para o cálculo do SV de um único objeto rígido e isso torna totalmente inviável a sua utilização para a detecção de

colisão” [19]. Para resolver esse problema, uma simplificação possível seria realizar os cálculos de volume com base nos volumes envolventes dos objetos. Entretanto, mesmo utilizando-se objetos mais simples como OBBs ou AABBs, tem-se a mesma complexidade de cálculo. As OBBs rotacionam juntamente com o objeto envolvido, gerando desta forma volumes não tão simples ao se considerar o arrasto entre um passo de tempo e outro. As AABBs não rotacionam juntamente com o objeto, mas isso não significa que elas sejam invariáveis rotacionalmente. Conforme o objeto envolvido rotaciona, elas são recalculadas e podem sofrer redimensionamentos, o que leva à mesma complexidade das OBBs. Já no caso de volumes envolventes esféricos, independente da rotação sofrida pelo objeto envolvido, não há rotação e nem redimensionamento dos mesmos; ocorre apenas a translação entre um passo de tempo e outro. Desta forma as operações realizadas para se calcular o volume são sempre as mesmas, seja qual for o movimento efetuado pelo objeto. Por outro lado, esse não é um volume envolvente que oferece um dos melhores encaixes nos casos de objetos longitudinais, como ocorre na maioria dos casos de braços robóticos. Mas, levando-se em conta que o que interessa é descobrir qual objeto efetuou um deslocamento maior para fins de priorização de testes, é tolerável abrir mão de cálculos mais precisos a fim de não haver perda de tempo com overheads desnecessários. O cálculo do arrasto será o mesmo para todos os objetos e a análise do volume será comparativa entre eles. O volume do arrasto do envoltório esférico será calculado multiplicando-se a área do círculo máximo da esfera pelo deslocamento efetuado entre um passo de tempo e outro e somando-se a isso o volume da esfera. Os objetos do primeiro grupo da MPD serão ordenados de forma decrescente por este volume, de forma que, quanto maior o volume do arrasto maior a priorização dada aos testes neste objeto. Além disso, a informação do deslocamento efetuado pelos objetos em cada passo de tempo traz informações suficientes para que se possa explorar também a Coerência Temporal. Em um dado passo de tempo, dois objetos que não tenham se deslocado não precisam ser testados um contra o outro, afinal se ambos não se moveram, a situação de colisão ou nãocolisão continua a mesma do passo de tempo anterior. Com isso, além da priorização obtida através do cálculo do SV, os mesmo cálculos permitem obter vantagens explorando-se a CT. Além da priorização do testes com maior probabilidade, efetuou-se o descarte das colisões impossíveis da mesma maneira que foi efetuado no Virbot4u. Esta análise levou ao descarte dos seguintes pares, onde n é a quantidade de objetos fixos e m é a quantidade de objetos móveis: 1) Eliminados por adjacência: 8 casos (4 em cada robô), 2) Eliminados pelo critério da mobilidade: os testes das bases com a mesa e das bases entre si (3 casos), dos objetos fixos com as bases e com a mesa (3n casos), dos objetos fixos entre si ((n²-n)/2 casos). Ou seja:

n²/2 + 5n/2 + 3. (3) 4) Eliminados pelo critério do alcance: os braços não alcançam a sua própria base (2 casos), os antebraços não alcançam seus próprios braços (2 casos), os braços não alcançam a mesa (2 casos), os corpos não alcançam a mesa (2 casos), o corpo e a base de um robô não atinge nenhuma das partes do outro robô (15 casos), e os objetos móveis não alcançam as bases, os corpos e a mesa (5m). Ou seja: 5m + 23 (4) O número total de testes eliminados é: n²/2 + 5n/2 + 5m + 34 (5) Sendo que, na detecção de força bruta, há um total de testes de: ((n+m+11)² - (n+m+11))/2 (6) VI. DESEMPENHO Para obter um resultado comparativo de desempenho foram montados quatro ambientes de testes. O primeiro ambiente utilizou apenas as técnicas de OBBs e HVEs. Neste ambiente todos os objetos seriam testados um contra o outro em cada momento da cena. Este ambiente foi chamado de Força Bruta (FB). O segundo ambiente (CE) utilizou, além das OBBs e HVEs, também o conceito de Coerência Espacial. O terceiro ambiente (CS) utilizou o conceito da Coerência Semântica, além das OBBS e HVEs. O quarto ambiente (CSE) utilizou OBBs, HVEs, Coerência Espacial e Coerência Semântica juntas. Em todos os ambientes foram adicionados 20 objetos fixos sobre a mesa, estando 10 no Lado A e 10 no Lado B segundo a divisão espacial mostrada na Figura 21. Foram montados oito cenários de teste. Cada cenário previa a colisão entre dois objetos diferentes da cena: Garra x Objeto Fixo, Garra x Mesa, Garra x Braço, Garra x Corpo, Garra x Base, Antebraço x Mesa, Antebraço x Corpo e Antebraço x Base. Em cada cenário de teste o robô foi posicionado automaticamente em posições predefinidas de forma que com apenas um comando ele atingisse a situação de colisão esperada, garantindo assim que a mesma situação fosse reproduzida para todos os ambientes de teste. Neste momento eram contados a quantidade de testes de colisão efetuados pelo ambiente. A aplicação do conceito proposto no simulador Virbot4u levou a uma redução na quantidade de testes de colisão de 99,69%, no melhor caso, e de 85,54%, no pior caso, no ambiente de melhor desempenho, o CSE. A aplicação no simulador Collbot4us levou a uma redução de 98,2% no melhor caso e de 82,35% no pior caso, também no ambiente CSE. A redução em termos de tempo dependerá do teste efetivo nos modelos geométricos, bem como do fato de estarem sendo aplicadas as técnicas de volumes envolventes e HVEs e um computador com uma configuração específica. Demonstrou-se que uma avaliação do contexto da cena e o conhecimento do significado de cada objeto na mesma podem diminuir consideravelmente a quantidade de testes de colisão efetuados.

Observando-se as análises efetuadas para construção da MPD percebe-se que à medida que a cena fica mais rica em características funcionais (objetos móveis e vários articulados) há uma necessidade de gerenciamento dinâmico e uma maior estruturação dos possíveis casos de teste. Isto pode consumir mais tempo de processamento, mas também pode identificar de forma mais precoce as situações de colisão para os casos mais prováveis. Analisando-se as fórmulas (1) contra (5) e (2) contra (6) percebe-se que à medida que mais objetos são adicionados à cena e mais comportamentos diferenciados aparecem há um aumento no número fixo de testes eliminados e, em ambos os casos, a economia de testes cresce exponencialmente. Isso ocorre, entretanto, ao custo de um maior gerenciamento entre objetos móveis e fixos e da constante organização entre eles.

[5] [6] [7] [8]

[9]

[10]

[11]

VII. CONCLUSÃO Apesar de existirem vários métodos clássicos para otimização de detecção de colisão entre objetos, percebeu-se que as informações específicas da cena sendo simulada não são utilizadas na maioria dos casos. Ambientes como os de simuladores de robôs fixos articulados apresentam características que são úteis para este processamento. Neste contexto testou-se o conceito de Coerência Semântica. A aplicação da Coerência Semântica em ambientes robotizados (que dispunham de objetos articulados, fixos e móveis) permitiu constatar mais eficiência nos momentos em que efetivamente ocorre a colisão sem perda de eficiência nos demais momentos. Entretanto, isto resulta em codificação específica para cada cena, o que leva a uma perda de generalidade que também depende de como o programador percebe a dinâmica do ambiente. Apesar disso é possível observar que, mesmo no pior caso, não houve aumento na quantidade de testes efetuados. Vê-se também que a aplicação da Coerência Semântica não leva a uma extensão direta e óbvia mesmo para ambientes muito semelhantes (e de mesma origem tecnológica). Assim, cada caso de aplicação mostra benefícios, mas requer um estudo particular. REFERÊNCIAS [1] [2]

[3] [4]

Hoss, A., Hounsell, M. S., Leal, A. B. (2009) Virbot4u: Um Simulador de Robô usando X3D. In: I Simpósio de Computação Aplicada, 2009, Passo Fundo - RS. I SCA. Porto Alegre - RS: SBC, 2009. p. 1-15. Dias, C.; Hounsell, M. S.; Rosso Jr, R. S. U. Análise de Colaboratividade usando telerobótica. In: IEEE/IGIP-INTERTECH, 2010, Ilhéus-BA. XI International Conference on Engineering and Technology Education. Santos-SP: COPEC, 2010. v. 1. p. 538-542. Web3d Consortium. X3D Specifications. Disponível em: http://www.web3d.org/x3d/specifications/. Ultimo acesso em 03 de fevereiro de 2010. Rohrmeier, M. (2000) Interactive simulation using virtual systems: web based robot simulation using VRML. Winter Simulation Conference – WSC, p.p. 1525-1528.

[12] [13]

[14] [15]

[16] [17] [18] [19]

[20] [21] [22]

[23] [24]

Lin, M. C., Manocha, D., Cohen, J., Gottschalk, S. (1997) Collision detection algorithms and applications. In: Algorithms for Robotic Motion and Manipulation, Wellesley, MA, p. 129-142. Li, C. F., Feng, Y. T., Owen, D. R. J. (2006) “SMB: Collision detection based on temporal coherence” In: Computer Methods in Applied Mechanics and Engineering. 195 (19-22): 2252-2269. Tropp, O., Tal, A., Shimshoni, I., Dobkin, D. P. (2006) Temporal Coherence in Bounding Volume Hierarchies for Collision Detection. In: International Journal of Shape Modeling 12(2): 159-178. Cohen, J. D., Lin, M. C., Manocha D., Ponamgi M. K. (1994) “Interactive and Exact Collision Detection for Large-Scaled Environments” In: Technical report, University of North Carolina at Chapel Hill, p 28. Klosowski, J., Held, M., Mitchell, J., Sowizral, H., Zikan, K. (1998) “Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs” In: IEEE Transactions on Visualization and Computer Graphics, Volume 4, Issue 1, ISSN:1077-2626. Taddeo, L. da S. (2005) Detecção de colisão utilizando grids e octrees esféricas para ambientes gráficos interativos. Dissertação do Curso de Mestrado em Informática Aplicada da Universidade de Fortaleza, Ceará, p 103. Figueiredo, M.; Fernando, T. (2003) An Unified Framework to Solve the Broad and Narrow phases of the Collision Detection Problem in Virtual Prototype Environments. In: Proc. of International Conference on Geometric Modeling and Graphics, Salford University, UK, p130136, 16-18 July. Luque, R. G., Comba, J. L. D., Freitas, C. M. S. (2006) Broad-Phase Collision Detection Using Semi-Adjusting BSP-trees. In: SIBIGRAPI, Brazil, p 8. Hofmam, M. Da S. (2002) Tratamento Eficiente de Visibilidade Através de Árvores de Volumes Envolventes. Dissertação de Mestrado do Departamento de Informática Pontifícia Universidade Católica do Rio de Janeiro (PUC-RJ), p 148. Bradshaw, G., O’Sullivan, C. (2004) “Adaptive Medial-Axis Approximation for Sphere-Tree Construction”, In: ACM Transactions, Vol. 23, No.1, p 1–26. Janeiro. Lin, M.C. (1993) Efficient Collision Detection for animation and robotics. Dissertation of Doctor of Philosophy in Electrical Engineering and Computer Sciences of the University of California and Berkeley, p 59. Lin, M., Manocha, D. (2003) Collision and proximity queries. In: CRC Handbook of Discrete and Computational Geometry, 2 ed., Boca Raton, FL, 2003. Gottschalk, S. (2000) Collision Queries using Oriented Bounding Boxes, PhD Thesis in the Department of Computer Science, University of North Carolina, Chapel Hill. Mezger, J. (2005) Tutorial 2 - Collision Handling in Dynamic Simulation Environments. In: Eurographics, p 54, 2005. Redon, S., Kim, Y. J., Lin, M. C., Manocha, D. (2005) “Fast Continuous Collision Detection for Articulated Models”, In: J. Comput. Inf. Sci. Eng., Volume 5, Issue 2, 126 (12 pages) DOI:10.1115/1.1884133. Jiménez, P.; Thomas, F.; Torras, C. (2001) 3D collision detection a survey. In: Computer and Graphics, Volume 25, Number 2, p. 269-285, Abril. Gottschalk, S., Lin, M. and Manocha, D. (1996) OBB Tree: A hierarchical structure for rapid interference detection. In: Proc. Siggraph’96, p 171-180, 1996. Miguel, R.; Hounsell, M. S.; Rosso Júnior, R. S. U. (2010) Aplicação da Coerência Semântica na Detecção de Colisões em um Simulador de Robô, In: XVII Congresso Brasileiro de Automática, Bonito – MS. In press. Kim, Y.; Varadhan, G.; Lin, M.; Manocha D. (2003) Efficient swept volume approximation of complex polyhedral models. Proc. of ACM Symposium on Solid Modeling and Applications. Redon, S.; Kheddar, A.; Coquillart, S. (2000) An algebraic solution to the problem of collision detection for rigid polyhedral objects. Proc. of IEEE Conference on Robotics and Automation.