Using the parametric domain for efficient computation

Abstract

O processo de parametrização de malhas em planos é um tópico de pesquisa bastante explorado. Apesar do grande esforço despendido no desenvolvimento de técnicas mais eficientes e robustas, pouco se tem investido no uso das representações paramétricas geradas por estas técnicas. Este trabalho apresenta contribuições relacionadas ao uso do espaço paramétrico para computações eficientes. A principal motivação vem do fato de alguns algoritmos serem mais eficientes quando aplicados sobre a versão paramétrica da malha. Algoritmos para o cálculo de distância mínima, por exemplo, podem ter um aumento significativo de eficiência quando aplicados em versões paramétricas de malhas. Nossos resultados demonstram que esses aumentos de eficiência podem chegar a cerca de uma ordem de magnitude em alguns casos. As contribuições deste trabalho possuem aplicação direta em três campos de pesquisa relacionados à computação gráfica: displacement mapping, cálculo de distâncias sobre superfícies e movimentação de agentes. A contribuição relacionada a displacement mapping, apresentada no capítulo 4, é utilizada para aumentar a performance de renderização e a qualidade visual de terrenos em jogos. O novo método de cálculo de distâncias proposto, apresentado no capítulo 5, aumenta a eficiência de vários algoritmos de cálculo de distância sobre superfícies de malhas. Este novo método também é utilizado em uma nova técnica para cálculo de movimentação de agentes em superfícies de malhas arbitrárias. Esta técnica é apresentada no capítulo 6. O potencial da nova técnica de cálculo de distância sobre malhas não está restrito aos exemplos apresentados. Em geral, qualquer técnica que utilize o cálculo de distância sobre superfícies de malhas de triângulos se beneficia das contribuições deste trabalho, podendo-se citar como exemplos a geração de texturas procedurais, rotulamento de superfícies, re-triangulação de malhas e segmentação de malhas, entre outros.

The process of parameterizing a mesh to the plane is an ongoing research topic. Although there are several works dedicated to parameterization techniques the use of the resulting parameterizations has received less attention. This work presents contributions related to the use of the parametric space to improve the computational efficiency of several algorithms. The main motivation comes from the fact that some algorithms are more efficiently computed on the parametric version of the mesh, compared to the 3-D version. For example, shortest distances can be computed, usually, an order of magnitude faster on the parametric space. The contributions of this work can be applied to at least three research fields related to computer graphics: displacement mapping, distance computation on the surface of triangular meshes and agent path planning. The contribution related to displacement mapping, presented in chapter 4, is used to increase the rendering performance and visual quality of terrains in games. The new method to compute distances, presented in chapter 5, increases the efficiency of several distance computation algorithms. This new method was also used on a novel agent path planning algorithm, to navigate agents on the surface of arbitrary meshes. This technique is presented in chapter 6. The potential of the new distance computation method is not restricted to the applications presented in this thesis. In general, any technique that uses distance computation on the surface of triangular meshes can have the performance improved by the method. We can cite the following applications: procedural texture generation, surface labeling, re-meshing, mesh segmentation, etc.