中文摘要：

煤矿床地表与地质层面模型通常采用TIN表示，交线作为层面模型交叉部分的特征描述，在模型构建及后续的应用分析中都具有十分重要的作用。根据基于层面模型编制露天煤矿采剥计划的需要，提出并实现了一种基于空间索引与碰撞检测的TIN快速求交算法。算法通过建立TIN空间格网索引，使相交测试仅限于映射在同一个空间格网单元内的三角形对之间，在计算交线时，进一步应用AABB包围盒碰撞检测技术快速剔除不相交三角形对，并分别采用边一面及改进的边-边求交算法计算异面与共面三角形交线，最后根据交线段之间的空间邻接关系实现交线的快速分离。实验分析表明，算法整体时间效率高于基于OBBTree的TIN求交算法。该算法在露天煤矿采剥计划CAD软件系统中成功应用于计划线生成、运输道路设计、追踪等值线、切割剖面等设计实践，提高了在三维图形环境下采剥计划设计的精度与可靠性。

英文摘要：

Coal bed surface and stratum models are usually expressed by TIN, as the feature level model cross section description, the intersection lines of TIN plays a very important role in the model constructing and the subsequent application analysis. According to the need for planning the open-cast stripping and mining based on the constructed surface and stratum models, this paper designed and implemented a TIN fast intersection algorithm applying collision detection and spatial index technology. The algorithm established a spatial grid index of TIN model, then it limited the intersection testing and calculation to those pairs of triangles which mapped to a same grid unit, during the calculation of intersection, applied the AABB bounding box col- lision detection technology to remove the non-intersect triangles quickly, calculated the intersection lines applying line-plane and improved line-line algorithm to the non-coplanar and coplanar triangles respectively. Finally, it separated efficiently according to their spatial adjacent information. Experimental results show that the algorithm is more efficient than the TIN intersection algorithm based OBBTree. The algorithm has been applied to generate plan line, design transportation road, generate isolines, cut profile in stripping and mining plan CAD softrware system of open-cast coal mine, its application improves the design accuracy and reliability under the 3D graphics environment.