62ª Reunião Anual da SBPC

A. Ciências Exatas e da Terra - 2. Ciência da Computação - 12. Simulação

DESENVOLVIMENTO DE SISTEMA DE GERAÇÃO AUTOMÁTICA DE MALHA DELAUNAY

Thomaz Maia de Almeida 1 Alyson Bezerra Nogueira Ribeiro 2 Jéssyca Almeida Bessa 2 Edson Cavalcanti Neto 2 Auzuir Ripardo de Alexandria 2

1. Universidade Federal do Ceará - UFC, Fortaleza/CE 2. Instituto Federal de Educação, Ciência e Tecnologia - IFCE, Fortaleza/CE

INTRODUÇÃO:

A computação traz cada vez mais, novos métodos para resolução, simulação e modelagem de problemas. Uma das melhorias proporcionadas pelo avanço da computação é a triangulação. A geração automática de malhas triangulares é uma ferramenta que pode ser utilizada em diversas áreas. Suas aplicações vão desde a modelagem de personagens de jogos para a Computação Gráfica, demarcação de espaço na Topografia/Cartografia até a geração de malhas para resolução de problemas eletromagnéticos e segmentação de imagens médicas. As técnicas mais avançadas para a geração de malha não estruturada da atualidade são os algoritmos Delaunay e avanço de fronteira. Os algoritmos Delaunay, em especial, se baseiam em regras a fim de obter uma malha de refinamento positivo e adequado ao propósito estabelecido.

METODOLOGIA:

O trabalho foi elaborado mediante uma prévia revisão bibliográfica e desenvolvido em C++ por ser uma linguagem consistente e orientada a objetos, facilitand o assim, a implementação do algoritmo. Baseado na revisão bibliográfica foi detectada a necessidade do cumprimento de algumas regras propostas pelo matemático Boris Delaunay, quais sejam: i) a interseção de dois triângulos de uma determinada malha é um vértice, uma aresta ou vazia; ii) sabendo que dado um determinado triângulo existe uma circunferência que o circunscreve, não deve existir nenhum vértice de nenhum outro triângulo dentro de qualquer circunferência da malha. A partir das orientações dadas, o matemático B. Delaunay provou que existe apenas uma maneira de ligar pontos formadores de triângulos (vértices) na qual maximize o menor ângulo dos triângulos. A técnica de maximizar o menor dos ângulos se deve ao fato de existir uma maior probabilidade de se obter triângulos equiláteros e, por sua vez, malhas mais refinadas. O algoritmo foi divido em quatro classes. Cada classe simula um componente da malha: i) Classe "Nodo" é responsável por simular os vértices dos triângulos guardando suas coordenadas; ii) Classe "Segment" representa os segmentos de reta (arestas) dos triângulos; iii) Classe "Triangles" é encarregada de unir as classes "Nodo" e "Segment" formando assim os triângulos da malha; iv) Classe "Delaunay" é a que tem acesso a todas as outras e gerencia os triângulos da malha. É na classe "Delaunay" que se encontram as funções de adesão de um novo ponto (vértice), verificação de circunferências e algumas outras necessárias dependendo da aplicação.

RESULTADOS:

Para efeito de testes foi elaborado um programa gerador de malha no qual o critério de adesão de um novo ponto visava a segmentação de objetos mediante técnica split and merge. O algoritmo buscou características nos pontos médios e baricentro dos triângulos e à medida que novos pontos eram adicionados novos triângulos foram formados. O programa teve uma boa eficiência conseguindo segmentar os objetos sem muitos detalhes e gerar até mais de mil triângulos por malha.

CONCLUSÃO:

O algoritmo teve sucesso em seu propósito, desde que gerou malhas triangulares obedecendo a todos os critérios de uma malha Delaunay. Viu-se, porém, a necessidade de reduzir o tempo de processamento do algoritmo, pois o aumento de funções à malha é inevitável tendo em vista que, como já foi explorado, a malha é apenas uma ferramenta para uma posterior aplicação. Atualmente vê-se a aplicação da triangulação em conjunto com a técnica de contornos ativos T-Snakes na segmentação de imagens médicas de tomografia computadorizada.

Instituição de Fomento: Conselho Nacional de Desenvolvimento Científico e Tecnológico - CNPq

Palavras-chave: Triangulação, Delaunay , Gerador Automático.