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

摘要

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