Key Algorithms Of Solids' Boolean Operations And Their Solution Of Singular Cases

Three-dimensional solid modeling technology is an important part of computer graphics. Meanwhile it is also the core technology to build model in virtual animation area. Three-dimensional solid modeling technology has gradually become the mainstream of graphics technology. It has been widely used in many fields. The Boolean operations of three-dimensional solid such as union, intersection and subtraction are the most important and complex issues in the area of solid modeling. According to the law of Boolean operations, if the algorithm of intersection is worked out, the problems of union and subtraction can be solved easily. So the main aim of this paper is to study the algorithm of intersection.This paper mainly focuses on the section-extraction algorithm, plane polygon-clipping(two-dimensional intersection) algorithm and singular cases among Boolean operations of three-dimensional solid. Aimed at section-extraction, this paper presents algorithms to extract sections, which consist of preprocessing of the intersection of planes, section-extending, intersection curve extraction and construction of plane loops. Aimed at plane polygon-clipping and based on the research of Weiler-Atherton algorithm, this paper summarize treatment principles of four clipping singular cases which are intersection point on the edge, intersection point on the vertex, edge overlap and loose polygon. This paper also gives the method to estimate whether the loose polygons are separated or within each other by using Bounding Box and counting intersection point.Algorithms mentioned in this paper has been tested by using c ++ language and Open GL library functions based on Visual c + + 6.0 development environment. The validity and feasibility of the algorithms presented in this paper has been proved successfully.