Abstract: To improve efficiency of calculating the signed distance between a point and a subdivision surface through large amounts of data, a new data structure which could represent subdivision surface patch was presented. Thus the divide-and-conquer strategy was used to control the scale of computation. Through using the topological characteristics of subdivision surface patch and multi-resolution sampling technology, a closest vertex on space in subdivision surface patch was searched by taking the minimum distance between a point and vertex of a subdivision surface as selection index. Parameter linear equation was established with position and normal vector of the closest vertex. On this basis, a method for precision analysis and sign estimation of minimum distance was presented. Combined with local subdivision, the precision of calculation was improved. The example was conducted to verify the feasibility and availability of the proposed algorithm. Compared with existing approaches, the presented algorithm had high efficiency and controllable accuracy.

Key words: minimum distance, data structure, divide and conquer, multi-resolution sampling, Catmull-Clark subdivision surface

摘要： 针对在海量细分曲面数据中计算空间点到细分曲面有符号最近距离效率较低的问题，创建一个新的细分曲面数据结构，实现细分曲面的分片表示，进而采用分治策略控制计算规模。利用细分曲面面片网格拓扑结构特性，结合多分辨率采样技术，以空间点和细分曲面极限网格顶点的最近距离作为择优指标，在细分曲面面片中搜索距离空间点最近的顶点。以最近顶点的位置和法向建立参数直线方程，以此为基础，进行最近距离的误差分析和符号判断。结合局部细分技术，提高最近距离的计算精度。基于Catmull-Clark细分模式，通过实例验证了算法的可行性和有效性。与常规方法相比，该算法计算效率高、精度可控，算法原理适用于多种细分模式。

关键词: 最近距离, 数据结构, 分治, 多分辨率采样, Catmull-Clark细分曲面