Geometric Searching in Extended CSG Models: Application to Solid Modeling and Viewing

In this paper, the CSG representation scheme is augmented with the'cartesian product.'The sweep method of generating solids is encompassed by this'Extended CSG'formalism. The point inclusion problem encountered in the area of geometric searching in computational geometry is discussed in the context to solid models represented by'extended CSG.'A simple algorithm to solve it that has a time complexity O(n), where n is the number of primitives, is presented. Allowing for preprocessing and extra storage, a second efficient algorithm, having a time complexity O(log n), is developed. The relevance of point inclusion problem in solid modelling techniques is indicated. An extended CSG based solid modelling method is proposed. A solution to the problem of hidden line removal, that uses the faster algorithm for the point inclusion problem, is also presented in the pape