Boolean Operation Algorithm On Mesh Models

Boolean set operation is a traditional problem in the computer graphics field.It has been widely used in the Virtual Reality(VR),3D Geography Visualization 3D Geography Information Systematic(GIS)fields,etc.Therefore,the research of 3D boolean operation techniques has important academic significance and application value.Using the 3D boolean operation techniques,we assemble several existing simple object models to create a much more complex model.As an important modeling technique,the 3D boolean operation technique is an essential tool in the computer geometry modeling technology field and CAD field.In the first part of paper,we conduct a comprehensive summary and analysis on research related to the 3D boolean operation technique.Most of the 3D boolean operation techniques could be seperated into two groups:methods based on intersection and methods based on space-partition.The binary space partitioning(BSP)methods is an important method in the space-partition category.Compared to the volumetric-grid approached,BSP methods increase mesh complexity more moderately and the input geometry is better preserved.Compared to methods based on intersection,BSP methods could do most computations more robustly.Then the paper introduces our adaptive BSP tree constructing algorithm.Our method firstly use the two-stage strategy during the BSP tree construction process.In the first stage,we choose the hyperplane along the axis-direction regularly to partition the mesh model until the number of faces of mesh in the sub-region is smaller than the given the threshold parameter.In the second stage,we choose the hyperplane that embeds one of the mesh faces as the partition plane.Moreover,our method conduct the BSP tree construction process adaptively according to the position of the models which we operate boolean operation on.In our method,we don't consider the BSP tree construction stage as the preprocess stage.Instead,we perform the tree construction and the tree division process simultaneouslyThe efficiency and effectiveness of our method are demonstrated in the experiments part of the paper.The experiment results show that the BSP tree constructed by our algorithm is adaptive.Using our strategies during the boolean operation stage,we reduce the size of the constructed BSP tree and improve the time consuming remarkably.In the last part of the paper,we conduct a comprehensive summary and analysis on the strength and shortcoming of our approach and discuss about some of our future work.