Study On STL Boolean Operation Based On Two-level Voxel Model

With the rapid development of 3D printing technology,3D printing in the industrial field is also more widely used,STL(Stereolithography)model has become more refined and complex.The Boolean operation of the STL model is a key step in model preprocessing and reprocessing in 3D printing.The traditional Boolean operation algorithm has high time complexity,and it is difficult to meet the data processing requirements of complex STL models.Therefore,the research of an efficient Boolean operation algorithm is of great significance to the data processing of 3D printing.In the process of Boolean operation,the method of collision detection determines its efficiency.On the basis of researching various collision detection algorithms,this dissertation proposes a Boolean operation algorithm based on the two-level voxel model to solve the problem of insufficient Boolean operation time efficiency of the complex STL model.The research of this dissertation is as follows:Firstly,the Boolean operation based on the hierarchical bounding box method and the Boolean operation based on the space division method are analyzed and compared.The advantages and disadvantages of the two methods are discussed,and the reasons why the above methods cannot meet the Boolean operation requirements of large-scale STL models are discussed.Then from four aspects of numerical precision,algorithm stability,space complexity and optimization of triangle classification process,the optimization ideas of Boolean operation based on voxel model are discussed,which lays a theoretical foundation for subsequent research.Secondly,the proposed Boolean operation algorithm based on the two-level voxel model are researched.This algorithm takes advantage of the high efficiency of Boolean operation of the voxel model,and further improves the voxel model in combination with the bounding box technology,so that the time complexity of searching for collision triangles is O(n).First construct AABB(Axis Aligned Bounding Box)bounding box and intersect to determine the voxel space area of Boolean operation,which can reduce the space complexity of the algorithm at the same time.Then,the first-level voxel model is constructed and the mapping relationship between it and the solid model is established.A fine voxelization delay strategy is proposed to optimize the voxelization process and improve the efficiency of the voxelization process.After the first-level voxel model is intersected,the second-level voxel model is established by sampling and analyzing the triangular data in the collision voxel,which solves the problem of the instability of the voxel model Boolean operation algorithm.The triangles in the collision voxel are extracted through the mapping relationship to accurately find the intersection,and the obtained intersection line set is connected into multiple intersection line rings.According to intersection line rings,the collision triangle is divided into multiple polygons,and the Ear Clipping algorithm is used to subdivide the polygon into triangles.The triangles are quickly classified according to their positions in the voxel space,and the triangles are reassembled according to the selected Boolean operation,then the results of Boolean operation can be obtained.Finally,the Boolean operation algorithm based on the two-level voxel model mentioned in this paper is compared with the Boolean operation based on OBB(Oriented Bounding Box)hierarchical bounding box in the well-known open source library VTK(Visualization Toolkit)of computer graphics.The performance test results of the algorithm show that the collision detection efficiency of the proposed algorithm is improved by 90% at least compared to the VTK algorithm,and the overall Boolean operation efficiency is improved by more than 70%.The efficiency of the Boolean algorithm based on the twolevel voxel model proposed in this paper is verified.