超大三维模型的快速离散测地线算法研究

Processing of large scale models is highly demanded in modern graphics society. Exact geodesics take huge computation cost. The serial geodesic algorithms meet their limitation on modern CPUs, while the lack of parallel algorithms abandoned the power of modern GPUs. This project focuses on efficient geodesic algorithms for large scale models in both exact and approximate manner. We aims to develop (1) a fully parallel algorithm based on local structure only, which could be strengthened by the modern GPUs. The rapid growth of parallel processors empowers the parallel algorithm for even larger models in the future, (2) an approximate geodesic algorithm for large scale models, which is appropriate for time-critical but accuracy-insensitive applications.

随着三维图形媒体的高速发展，超大三维模型的分析和计算已经成为主流。精确的离散测地线算法需要非常高昂的计算成本。CPU处理能力的瓶颈限制了现有串行算法在超大模型上的计算速度，而并行测地线算法的缺失限制了现代并行处理器在测地线计算中的发挥。本项目从测地线的精确算法和近似算法两方面着手， 构建适用于超大三维模型的快速离散测地线算法：（1）设计只依赖于局部信息的完全并行的测地线算法，使之能充分利用现代GPU的并行计算性能，从而使测地线计算不受硬件发展的制约。并行的测地线算法可以随着并行处理器日益增长的计算能力而处理更加巨大的三维模型。（2）针对超大三维模型设计快速近似测地线算法，以适用于对精度不敏感但对时间敏感的测地线应用。