Integer coordinates for intrinsic geometry processing
Integer coordinates for intrinsic geometry processing
复制标题
DOI：
10.1145/3478513.3480522
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
M. Gillespie;Nicholas Sharp;Keenan Crane
中科院分区：
文献类型：
--
作者：
M. Gillespie;Nicholas Sharp;Keenan Crane
本文描述了一种用于对多面体表面的内蕴三角剖分进行编码的数值鲁棒的数据结构。许多应用需要内蕴三角剖分与输入表面之间存在对应关系，但现有的数据结构要么依靠浮点值来编码这种对应关系，要么不支持除基本的边翻转之外的重新网格化操作。相反，我们提供了一种基于整数的数据结构，即使对于含有近乎退化元素的网格，它也能保证有效的对应关系。我们的出发点是几何拓扑中的法坐标框架，我们将其扩展到网格处理所需的更广泛的操作集（顶点插入、边分割等）。由此产生的数据结构可作为早期方案的直接替代品，在各种各样的应用中自动提高可靠性。作为一项压力测试，我们成功地为Thingi10k数据集中的所有流形网格计算了内蕴德劳内细化及相关细分。反过来，即使在质量极低的网格上，我们也能够计算偏微分方程可靠且高度精确的解。
This paper describes a numerically robust data structure for encoding intrinsic triangulations of polyhedral surfaces. Many applications demand a correspondence between the intrinsic triangulation and the input surface, but existing data structures either rely on floating point values to encode correspondence, or do not support remeshing operations beyond basic edge flips. We instead provide an integer-based data structure that guarantees valid correspondence, even for meshes with near-degenerate elements. Our starting point is the framework of normal coordinates from geometric topology, which we extend to the broader set of operations needed for mesh processing (vertex insertion, edge splits, etc.). The resulting data structure can be used as a drop-in replacement for earlier schemes, automatically improving reliability across a wide variety of applications. As a stress test, we successfully compute an intrinsic Delaunay refinement and associated subdivision for all manifold meshes in the Thingi10k dataset. In turn, we can compute reliable and highly accurate solutions to partial differential equations even on extremely low-quality meshes.