笛卡尔网格生成中的相交算法

Intersection algorithms on Cartesian mesh generation

研究三维空间笛卡尔网格与三角形面网格的相交判断算法———ADT(Alternating DigitalTree)算法和KD(K-Dimensional)树算法,分别用球体模型和飞机模型对ADT与KD树进行分析,比较二者快速相交判断时的查找效率.结果表明:同一种模型下ADT比KD树平衡,树的深度小;ADT的查找效率明显比KD树高;影响KD树查找时间的主要因素是查找次数.整体来看,在快速相交判断中采用ADT性能更高.

To study the intersection judgment algorithms on Cartesian meshes and triangle surface meshes in 3D space, that is Alternating Digital Tree（ADT） algorithm and K-Dimensional（KD） tree algorithm, the sphere model and aircraft model are separately used to analyze ADT and KD tree, and the searching efficiency of the two trees during the quick intersection judgment process are compared. The results show that, ADT is more balanced and efficient than KD tree under the same model, and ADT has a less depth; the primary factor that influences the searching time of KD trees is the number of searching times. ADT has a higher performance for the quick intersection judgment.