Research And Implementation Of 3D Entities Boolean Operation Algorithm Based On 3D Grid Model

3D Boolean operational technology is one of the most important and complex problem in structuring complex entity of computer 3D modelling technology, and has important application in 3D Geography Information Systematic (GIS), Virtual Reality (VR), Interactive Visualizationcan fields, etc. Therefore, the research of 3D Boolean operational technology has important academic meaning and application value. After the analysis of surface reconstruction technology, the thesis is mainly centered on the following two issues:Firstly, the efficiency problem of fast collision detection based on OBB (Oriented Bounding Box) collision detection algorithm. Secondly, the accuracy problem of accurate intersection is based on 3D mesh model Boolean operational algorithm.Aiming at the first problem, this thesis studys traditional collision detection algorithm, and presents an improved fast collision detection algorithm based on OBB hierarchy bounding boxes constructed method. This algorithm inherits the advantages of traditional collision detection algorithm, and break through its limitations. It can handle the collision detection problem in arbitrary-shaped polyhedra, save half stock space, and can fast detect intersecting triangles. Therefore, it has raised efficiency of boolean operation. The algorithm triangulates the data of orebody surface points in advance, and organizes the OBB hierarchical binary tree reasonably. Secondly, through top-down principle, construct OBB tree that eliminates the bounding box of leaf nodes to realize fast collision detection.Aiming at the second problem, a kind of Boolean operational method based on 3D mesh model is proposed. Firstly, this algorithm is through collision detection algorithm based on OBB hierarchical bounding box tree to get the intersecting triangles. Through the intersection test of the triangles, to obtain intersecting lines and establish intersecting lines topology relations with the triangles. Secondly, process the three types of intersecting lines and make a region division for the intersecting triangles, get a series of polygons, and carry out Delaunay Triangulation for polygon to get the result area. Lastly, based on solid containing relation construct relation adjacency list, judge the polygon's internal and external relation with other entities. Judge the position of the triangles according to the mesh model topology relations.Simultaneously, under the intersection, union, and difference of Boolean operations, it can choose the result region and get the final results.Experimental results show that this algorithm can achieve better results.