三维网格模型的布尔运算算法研究
发布时间：2018-08-01 15:48
【摘要】：三维布尔运算是计算机图形学建模领域的一个经典问题,并在三维地理信息系统、交互式可视化、虚拟现实等领域有着重要的应用。因此,三维布尔运算算法的研究工作有着重要的学术意义以及应用价值。利用三维布尔运算技术,可以对现有的三维几何模型进行组合操作得到新的模型。三维布尔运算作为一个重要的建模方式,已经成为计算机几何造型技术与CAD领域里不可或缺的工具之一。本文首先详细地对三维网格模型的布尔运算技术进行了全面的分析与总结。三维网格模型的布尔运算方法主要有基于交线提取的布尔运算方法与基于空间划分的布尔运算方法。基于BSP树的布尔运算方法是基于空间划分的布尔运算方法中的经典方法。相比于基于交线提取的布尔运算方法,该方法具有算法简洁明了,鲁棒性强的特点,但该方法也有构建得到的BSP树规模大,时间复杂度较高,不适用于大型模型间的缺点等特点,同时该方法依赖于模型网格的内外逻辑合法性,对于自相交网格模型、组合网格模型等的布尔运算结果无法保证正确性。本文对基于BSP树的布尔运算方法进行改进优化。首先在构建BSP树的划分面选取阶段,采用两阶段选取的策略,首先先规范化地选取划分面,当空间内的三角面片数低于预先设定的阈值k后,则转入第二阶段,选取网格模型中与三角面片共面的超平面作为划分面。同时,本文方法令BSP树的构建与后续布尔运算的判定操作同时进行,在BSP树构建过程中考虑另一个模型的空间位置,将BSP树的构建局限于模型相交处,实现布尔运算的自适应构建终止。对于特殊模型的布尔运算,本文方法将对构建得到的BSP树进行修复优化,从而确保布尔运算方法仍旧适用于该类网格模型,从而确保最终布尔运算结果的正确性本文的实验部分展示了两个网格模型之间的布尔运算结果对比分析。实验结果表明通过使用本文的策略,可以有效地降低构建得到的BSP树的高度,改善生成的BSP树的质量,减小构建BSP树所需的内存开销,最终提高布尔运算的运行效率。通过对构建得到的BSP树进行修复优化,保证布尔运算方法对于自相交模型等特殊模型的适用性。在本文的最后部分,将对本文提出的布尔运算方法的优缺点进行详细的分析。并对本文的内容以及布尔运算技术进行总结与展望。
[Abstract]:3D Boolean operation is a classical problem in the field of computer graphics modeling, and it has important applications in the fields of 3D GIS, interactive visualization, virtual reality and so on. Therefore, the research of three-dimensional Boolean algorithm has important academic significance and application value. A new 3D geometric model can be obtained by combining the existing 3D geometric models with the three-dimensional Boolean operation technology. As an important modeling method, 3D Boolean operation has become one of the indispensable tools in the field of computer geometry modeling and CAD. In this paper, the Boolean computing technology of three-dimensional mesh model is analyzed and summarized in detail. The Boolean operation method of 3D mesh model mainly includes Boolean operation method based on intersection line extraction and Boolean operation method based on space partition. Boolean operation method based on BSP tree is a classical method of Boolean operation based on space partition. Compared with the Boolean algorithm based on intersecting line extraction, this method has the advantages of simple and clear algorithm and strong robustness. However, this method also has the advantages of large scale of BSP tree and high time complexity. It is not applicable to the shortcomings of large scale models, and the method depends on the logic legitimacy of the model grid, and the Boolean operation results of self-intersecting mesh model and combined grid model can not guarantee the correctness. In this paper, the Boolean operation method based on BSP tree is improved and optimized. First of all, in the stage of selecting the partition surface of constructing BSP tree, the strategy of two-stage selection is adopted. First, the partition surface is normalized. When the number of triangular patches in the space is lower than the pre-set threshold k, then it goes to the second stage. The hyperplane coplanar with the triangular surface is selected as the partition surface in the mesh model. At the same time, the method of this paper makes the construction of BSP tree and the decision operation of subsequent Boolean operation proceed simultaneously. In the process of constructing BSP tree, the spatial position of another model is considered, and the construction of BSP tree is limited to the intersection of the model. The self-adaptive construction of Boolean operation is realized. For the Boolean operation of the special model, the method in this paper will repair and optimize the constructed BSP tree, so as to ensure that the Boolean operation method is still suitable for this kind of grid model. In order to ensure the correctness of the final Boolean operation results, the experimental part of this paper shows the comparison and analysis of the Boolean operation results between the two grid models. The experimental results show that the proposed strategy can effectively reduce the height of the constructed BSP tree, improve the quality of the generated BSP tree, reduce the memory overhead required to build the BSP tree, and ultimately improve the efficiency of Boolean operation. By repairing and optimizing the constructed BSP tree, the applicability of Boolean operation method to special models such as self-intersection model is ensured. In the last part of this paper, the advantages and disadvantages of the Boolean operation method proposed in this paper are analyzed in detail. The content of this paper and Boolean operation technology are summarized and prospected.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP391.41
本文编号：2158061
[Abstract]:3D Boolean operation is a classical problem in the field of computer graphics modeling, and it has important applications in the fields of 3D GIS, interactive visualization, virtual reality and so on. Therefore, the research of three-dimensional Boolean algorithm has important academic significance and application value. A new 3D geometric model can be obtained by combining the existing 3D geometric models with the three-dimensional Boolean operation technology. As an important modeling method, 3D Boolean operation has become one of the indispensable tools in the field of computer geometry modeling and CAD. In this paper, the Boolean computing technology of three-dimensional mesh model is analyzed and summarized in detail. The Boolean operation method of 3D mesh model mainly includes Boolean operation method based on intersection line extraction and Boolean operation method based on space partition. Boolean operation method based on BSP tree is a classical method of Boolean operation based on space partition. Compared with the Boolean algorithm based on intersecting line extraction, this method has the advantages of simple and clear algorithm and strong robustness. However, this method also has the advantages of large scale of BSP tree and high time complexity. It is not applicable to the shortcomings of large scale models, and the method depends on the logic legitimacy of the model grid, and the Boolean operation results of self-intersecting mesh model and combined grid model can not guarantee the correctness. In this paper, the Boolean operation method based on BSP tree is improved and optimized. First of all, in the stage of selecting the partition surface of constructing BSP tree, the strategy of two-stage selection is adopted. First, the partition surface is normalized. When the number of triangular patches in the space is lower than the pre-set threshold k, then it goes to the second stage. The hyperplane coplanar with the triangular surface is selected as the partition surface in the mesh model. At the same time, the method of this paper makes the construction of BSP tree and the decision operation of subsequent Boolean operation proceed simultaneously. In the process of constructing BSP tree, the spatial position of another model is considered, and the construction of BSP tree is limited to the intersection of the model. The self-adaptive construction of Boolean operation is realized. For the Boolean operation of the special model, the method in this paper will repair and optimize the constructed BSP tree, so as to ensure that the Boolean operation method is still suitable for this kind of grid model. In order to ensure the correctness of the final Boolean operation results, the experimental part of this paper shows the comparison and analysis of the Boolean operation results between the two grid models. The experimental results show that the proposed strategy can effectively reduce the height of the constructed BSP tree, improve the quality of the generated BSP tree, reduce the memory overhead required to build the BSP tree, and ultimately improve the efficiency of Boolean operation. By repairing and optimizing the constructed BSP tree, the applicability of Boolean operation method to special models such as self-intersection model is ensured. In the last part of this paper, the advantages and disadvantages of the Boolean operation method proposed in this paper are analyzed in detail. The content of this paper and Boolean operation technology are summarized and prospected.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP391.41
【参考文献】
相关期刊论文 前1条
1 吴明华，余勇翔，周济;采用空间分割技术的八叉树干涉检验算法[J];计算机学报;1997年09期
相关硕士学位论文 前3条
1 丁超;基于草图的三维建模系统综述[D];中国科学技术大学;2016年
2 杨兰;三维网格模型实体布尔运算方法的研究与实现[D];中南大学;2011年
3 陈辉;基于实体模型的布尔运算算法与实现[D];山东科技大学;2007年
，本文编号：2158061
本文链接：https://www.wllwen.com/shoufeilunwen/xixikjs/2158061.html
最近更新
教材专著
