【摘要】：三維布爾運算是計算機圖形學(xué)建模領(lǐng)域的一個經(jīng)典問題,并在三維地理信息系統(tǒng)、交互式可視化、虛擬現(xiàn)實等領(lǐng)域有著重要的應(yīng)用。因此,三維布爾運算算法的研究工作有著重要的學(xué)術(shù)意義以及應(yīng)用價值。利用三維布爾運算技術(shù),可以對現(xiàn)有的三維幾何模型進行組合操作得到新的模型。三維布爾運算作為一個重要的建模方式,已經(jīng)成為計算機幾何造型技術(shù)與CAD領(lǐng)域里不可或缺的工具之一。本文首先詳細(xì)地對三維網(wǎng)格模型的布爾運算技術(shù)進行了全面的分析與總結(jié)。三維網(wǎng)格模型的布爾運算方法主要有基于交線提取的布爾運算方法與基于空間劃分的布爾運算方法�；贐SP樹的布爾運算方法是基于空間劃分的布爾運算方法中的經(jīng)典方法。相比于基于交線提取的布爾運算方法,該方法具有算法簡潔明了,魯棒性強的特點,但該方法也有構(gòu)建得到的BSP樹規(guī)模大,時間復(fù)雜度較高,不適用于大型模型間的缺點等特點,同時該方法依賴于模型網(wǎng)格的內(nèi)外邏輯合法性,對于自相交網(wǎng)格模型、組合網(wǎng)格模型等的布爾運算結(jié)果無法保證正確性。本文對基于BSP樹的布爾運算方法進行改進優(yōu)化。首先在構(gòu)建BSP樹的劃分面選取階段,采用兩階段選取的策略,首先先規(guī)范化地選取劃分面,當(dāng)空間內(nèi)的三角面片數(shù)低于預(yù)先設(shè)定的閾值k后,則轉(zhuǎn)入第二階段,選取網(wǎng)格模型中與三角面片共面的超平面作為劃分面。同時,本文方法令BSP樹的構(gòu)建與后續(xù)布爾運算的判定操作同時進行,在BSP樹構(gòu)建過程中考慮另一個模型的空間位置,將BSP樹的構(gòu)建局限于模型相交處,實現(xiàn)布爾運算的自適應(yīng)構(gòu)建終止。對于特殊模型的布爾運算,本文方法將對構(gòu)建得到的BSP樹進行修復(fù)優(yōu)化,從而確保布爾運算方法仍舊適用于該類網(wǎng)格模型,從而確保最終布爾運算結(jié)果的正確性本文的實驗部分展示了兩個網(wǎng)格模型之間的布爾運算結(jié)果對比分析。實驗結(jié)果表明通過使用本文的策略,可以有效地降低構(gòu)建得到的BSP樹的高度,改善生成的BSP樹的質(zhì)量,減小構(gòu)建BSP樹所需的內(nèi)存開銷,最終提高布爾運算的運行效率。通過對構(gòu)建得到的BSP樹進行修復(fù)優(yōu)化,保證布爾運算方法對于自相交模型等特殊模型的適用性。在本文的最后部分,將對本文提出的布爾運算方法的優(yōu)缺點進行詳細(xì)的分析。并對本文的內(nèi)容以及布爾運算技術(shù)進行總結(jié)與展望。
[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.
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP391.41

【參考文獻】

相關(guān)期刊論文 前1條

1 吳明華，余勇翔，周濟;采用空間分割技術(shù)的八叉樹干涉檢驗算法[J];計算機學(xué)報;1997年09期

相關(guān)碩士學(xué)位論文 前3條

1 丁超;基于草圖的三維建模系統(tǒng)綜述[D];中國科學(xué)技術(shù)大學(xué);2016年

2 楊蘭;三維網(wǎng)格模型實體布爾運算方法的研究與實現(xiàn)[D];中南大學(xué);2011年

3 陳輝;基于實體模型的布爾運算算法與實現(xiàn)[D];山東科技大學(xué);2007年

，

本文編號：2158061