三维网格上的测地线距离压缩与快速查询

"这篇论文提出了一种新型方法，用于压缩并快速检索三维网格表面上点对之间的测地线距离信息。作者克雷格·格茨曼和凯·霍尔曼探讨了如何有效地存储这些数据，以便在需要时能高效地进行点对点的测地线距离查询。他们开发了一个数据库，其大小为O(mnlogn)，可以在O(f(n)+m3N)时间内处理N次查询，其中m与表面的几何复杂性有关，而f(n)代表预处理的复杂性。通过计算嵌套的分割曲线和存储紧凑的描述，他们的方法能够近似网格顶点之间的距离，并在最坏情况下以O(mlogn)的时间和平均情况下以O(m)的时间解决单变量最小化问题，从而获得良好的逼近结果。这种方法适用于压缩精确或近似测地线距离，无论是由VTP、快速DGG、快速行军还是热法计算得出的。" 本文首先强调了在3D几何处理任务中，计算点对之间的测地线距离的重要性以及现有方法的效率问题。传统的计算方法，如快速行进法和热法，虽然有效，但涉及到复杂的离散化和偏微分方程求解。另一方面，基于图的方法通过添加额外的边来构建稀疏图，但这同样需要预处理和存储。 论文介绍的新方法采用了一种创新的策略，通过递归地使用分割曲线来平分网格表面，生成一个数据库，用于存储每个顶点的距离域。这种方法允许在需要时快速获取点对间的测地线距离，而无需重新计算整个距离场。这极大地提高了效率，特别是对于需要频繁进行距离查询的应用来说，如三维模型分析、几何变形或碰撞检测等。 此外，该方法的效率和精度之间达到了很好的平衡。尽管数据库的大小与表面复杂性和顶点数量有关，但查询速度非常快，且对结果的近似误差可接受。这意味着在牺牲一定的存储空间的同时，换取了实时性能的提升，这对于实时渲染和交互式应用至关重要。 "Compressing Geodesic Information for Fast Point-to-Point Geodesic Distance"提出了一种优化策略，旨在解决三维网格上的测地线距离计算难题，为几何处理任务提供了更高效的数据结构和算法，有助于推动3D图形学和相关领域的技术进步。