Techniques for Reducing Boolean Evaluation Time in Constructive Solid Geometry (CSG) Scan-Line Algorithms

摘要

Techniques to reduce Boolean evaluation time in Atherton's (1983) scan-line hidden surface algorithms for combinations of plane-faced primitives for image generation of complex models were developed. A straighforward implementation of Atherton's algorithm with top-down Boolean evaluation; and Boolean evaluation done bottom-up with a pruned constructive solid geometry (CSG) tree, and with an extension to reduce the number of Boolean evaluations were tested. Results show that the time needed for Boolean evaluation in a CSG scan-line algorithm can be reduced by more than 90%, and the total drawing time by 65% to 80%.