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

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