Abstract: In view of the high computational complexity and less related calculation methods between surfaces, a triangular patch bounding box method is proposed to compute approximate Hausdorff distance rapidly between parametric surfaces. Triangular patches discretized from surface is a good way to approach the surface, so the Hausdorff distance between surfaces can be approximated by the Hausdorff distance between triangles. In order to improve computational efficiency, bounding box technology is used to eliminate the invalid triangles in the process of computing. At the same time, in order to further simplify the distance calculation between two triangles, an approximate calculation method of sampling points is put forward and the error is under control. The experiments show that the proposed method is simpler, easier to implement and has a higher exclusion rate compared with the surface surrounded bounding box method, also the computational efficiency is significantly improved without affecting the results, so the method has a wide application value.

Key words: parametric surfaces, Hausdorff distance, triangular patches, hierarchical bounding volumes

摘要： 针对曲面间Hausdorff距离计算复杂度高、相关计算方法少的问题，提出一种三角面片-包围盒方法快速计算参数曲面间Hausdorff距离的近似值。曲面离散化后的三角面片集合可以较好地逼近曲面，借助这一特性，将曲面间的Hausdorff距离近似转化为三角面片集合间的Hausdorff距离。在具体计算过程中，辅之以包围盒技术对无效的三角面片进行排除，以提高计算效率。为进一步简化两三角面片间的距离计算，在误差可控范围内提出采样点近似计算方法。实验表明，与曲面直接构造包围盒方法相比，该方法简便、易于实现、排除率高，在不影响计算结果的情况下，计算效率显著提高，有广泛的应用价值。

关键词: 参数曲面, Hausdorff距离, 三角面片, 层次包围盒