基于动态空间索引结构的三角网格模型布尔运算

Accelerated Boolean Operations on Triangular Mesh Models Based on Dynamic Spatial Indexing

针对目前三角网格模型布尔运算运行效率低的问题,提出了一种三角网格模型的动态空间索引结构,基于该结构可快速定位2个网格模型之间的相交区域,求解其交线;进而沿交线将每一三角网格模型分割成2个子网格模型,通过子网格模型的不同拼接生成三角网格模型的布尔运算结果.实例结果证明,该算法可准确地求解交线数据,有效地提高三角网格模型的布尔运算效率,并适用于各种复杂型面三角网格模型.

A novel data structure to accelerate the Boolean operations of triangular mesh models is proposed. It presents an extension to R＊-tree to organize the triangular meshes of each model into a hierarchical data structure based on their spatial locations. The spatial indexing facilities provided by the new data structure not only make the intersection calculation to be performed locally, but also accelerate the tracing of discrete intersection segments into a continuous line. Each triangular mesh model is then partitioned into two sub-meshes along the intersection line and the desired Boolean operation result can be obtained as a specific composition of these sub-meshes. Experimental results show the efficiency and the robustness of our approach.