Universidade Federal de Goiás
Mestrado em Ciência da Computação
Disciplina: Projeto e Análise de Algorítmos
Profa. Diane Castonguay
WAR STORY
Stripping Triangulations
Luciana Oliveira e Silva
Goiânia, 18 de outubro de 2005
A maneira mais comum utilizada na computação gráfica para representar
modelos geométricos é a triangulação.
Equipamentos e sistemas específicos, de alta performance, são utilizados para
renderizar e sombrear os triângulos. Dessa forma, o gargalo dessa atividade está
em alimentar a estrutura de triangulação dentro do sistema.
Cada triângulo pode ser descrito através das informações abaixo:
 Especificação de seus três pontos;
 Especificação da normal;
 Sombreamento.
Eficiência: O maior problema consiste em encontrar uma representação
alternativa mais eficiente para os triângulos, de forma a minimizar o tempo de
renderização e sombreamento do objeto.
Solução Proposta: Particionar os triângulos em faixas (strips) de triângulos
adjacentes e caminhar ao longo destas faixas.
Na prática: Cada triângulo compartilha dois vértices em comum com seus
vizinhos, desta forma o custo de retransmitir os dois vértices e a normal associada é
salvo.
Pode-se imaginar uma representação como um grafo:
Uma vez tendo o grafo dual disponível, deve-se procurar particionar os seus
vértices do grafo no menor número de caminhos possíveis.
Particionar o grafo em um caminho implica que encontramos o Caminho
Hamiltoniano, que por definição, visita cada vértice exatamente uma vez.
Encontrar um caminho Halmiltoniano, é um problema NP-Completo, dessa
forma devemos nos concentrar em hipóteses (heurística).
Podemos utilizar as seguintes heurísticas:
1) Simples: A heurística mais natural para cobertura das faixas seria iniciar de
um triângulo qualquer e fazer a caminhada da esquerda para a direita,
marcando as bordas do objeto ou um triângulo previamente visitado. Essa
heurística é rápida e simples, porém não afirma que encontrou o menor
caminho possível para uma triangulação.
2) Ambiciosa: Uma heurística ambiciosa é mais provável que encontre um
número pequeno de faixas. No caso da triangulação, a heurística ambiciosa
encontraria a faixa esquerda-direita mais longa e a preencheria primeiro.
Seja k o comprimento da caminhada a partir de um vértice médio. Usando a
implementação mais simples possível, poderíamos caminhar a partir de cada
um dos n vértices por iteração para encontrar a maior faixa num tempo
O( k * n ).
Para o número total de faixas do objeto teríamos uma implementação da ordem
de O ( n2 ).
Algorítmo:
Mantemos os comprimentos de todas as possíveis
faixas numa estrutura de dados. Toda vez que
uma faixa fosse retirada, os comprimentos de
todas as outras são atualizadas (as faixas
restantes são “encurtadas” por que antes elas
caminhavam por um triângulo que agora não
existe mais).
a)
Fila de Prioridades: poderíamos armazenar as faixas ordenadas de acordo com o
comprimento. A próxima faixa a ser preenchida seria sempre a do topo da fila.
b)
Dicionário: para cada triângulo da área precisaríamos de um método para
localizá-lo na fila. Isso significa armazenar um ponteiro para cada triângulo.
Visto que cada triângulo é composto por vértices compostos por três números
inteiros, ou uma tabela hash ou um vetor de listas bastaria. Integrando o
dicionário com a fila de prioridade, pode-se construir uma estrutura de dados
capaz de fazer um conjunto maior de operações.
O novo tempo de execução é O ( n * k ), onde n é o número de triângulos e k
o tamanho da maior faixa.
Outros Métodos de Triangulação
• Triangulação de superfícies difeomorfas à esfera
Método para triangulação de superfícies difeomorfas à esfera, de forma que a malha de triângulos
obtida chegue bem próximo da homogeneidade, ou seja, cada triângulo desta triangulação deve
ser uma "boa" aproximação de um triângulo equilátero, e todos os triângulos devem ter
aproximadamente a mesma área.
Esse método de triangulação tem a vantagem diminuir o efeito de falsa ilusão de perspectiva,
permitindo melhor noção de profundidade, e portanto melhor percepção da superfície.
• Triangulação de Delaunay
Uma triangulação de Delaunay de um conjunto de pontos é uma triangulação onde cada triângulo
satisfaz a propriedade de que seu círculo circunscrito (passa por três pontos) é vazio, isto é, não
contém pontos do conjunto em seu interior. A triangulação de Delaunay maximiza o menor
ângulo dentre todas as triangulações.
• Diagrama de Voronoi
Um diagrama de Voronoi de um conjunto de pontos é uma subdivisão do plano em regiões
poligonais (algumas podem ser infinitas), onde cada região é o conjunto dos vértices no plano
que estão mais perto de algum ponto da entrada do que a todos os outros pontos da entrada. (o
diagrama de Voronoi é o dual geométrico do diagrama de Delaunay)