Interactive vizualization of constructive solid geometry scenes on graphic processors

A ray-tracing algorithm for interactive visualization of very large and structurally complicated scenes presented in the constructive solid geometry (CSG) form is suggested. The algorithm is capable of visualizing such scenes in real time by using a graphic processor. As primitives, classical shapes and objects represented in an analytical form (in particular, second-order surfaces and implicit functions) are used. Unlike other similar algorithms, our algorithm produces the final image in a single pass and has no constraints on the maximum number of primitives and on the CSG tree depth. The key feature of the algorithm is a method for optimizing CSG models, which converts the input tree to an equivalent spatially coherent and well-balanced form (a completely balanced equivalent tree may not exist). The performance of visualization after applying the optimization technique is shown to depend on only the computational resource of the GPU (in contrast to multi-pass algorithms whose performance is restricted by memory capacity). It has been shown experimentally that our algorithm is capable of rendering CSG models consisting of more than a million CSG primitives with the tree depth up to 24.