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

Intersection algorithms on Cartesian mesh generation

作　　者：张立[1] 何冰[1] 封卫兵[1] 张武[1] 

机构地区：[1]上海大学计算机工程与科学学院,上海200072

出　　处：《计算机辅助工程》2013年第1期71-76,78,共7页Computer Aided Engineering

基　　金：国家自然科学基金(11002086);上海市科学技术委员会重点项目(10510500600);上海市重点学科建设项目(J50103)

摘　　要：研究三维空间笛卡尔网格与三角形面网格的相交判断算法———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.

关 键 词：笛卡尔网格 三角形面网格 体网格 格子BOLTZMANN方法 ADT KD树 相交算法 查找效率 

分 类 号：O241.82[理学—计算数学] O35[理学—数学]