“A scan-line hidden surface removal procedure for constructive solid geometry” by Atherton

This paper presents a new methodology for resolving visible surface images of solid models derived from Boolean combinations of volumetric building blocks. The algorithm introduced here is an extension of well-established scan-line hidden surface removal procedures, and it integrates knowledge of a Boolean construction tree in the surface resolution process. Several hidden surface coherence properties are discussed in terms of their possible exploitation in the intricate solid model visualization process. While many of the earlier coherence techniques depend on a polygon environment in which surfaces and volumes do not intersect, the Boolean process can not afford that luxury because it is inherently required to handle intersecting volumes and surfaces. Initial tests indicate that substantial performance improvements over previous methods can be achieved with the algorithm described in this paper, and that these improvements increase as model complexity increases. An underlying philosophy of a dual solid modeling system is proposed in this paper. It suggests that two solid modelers are necessary to successfully satisfy both analytical precision requirements and user interface visualization requirements. The visual solid modeling task addressed in this paper provides greatly improved response capabilities, as compared to other systems, by striving to optimize the constructive solid model (CSG) solid model computations specifically for display purposes.

1. Bouknight, W.J., “A Procedure for Generation of Three-Dimensional Half-Toned Computer Graphics Representations,” Comm. ACM, Vol. 13, No. 9, September 1970.
2. Boyse, J.W. and Gilchrist, J.E., “GMSolid: Interactive Modeling for Design and Analysis of Solids,” IEEE Computer Graphics and Applications, Vol. 2, No. 2, March 1982, pp. 86-97.
3. Brown, C.M., “PADL-2: A Technical Summary,” IEEE Computer Graphics and Applications, Vol. 2, No. 2, March 1982, pp. 69-84.
4. Hamlin, G. and Gear, C.W., “Raster-Scan Hidden Surface Algorithm Techniques,” Computer Graphics, Vol. 11, 1977, No. 2, pp. 206-213.
5. Foley, J.D. and VanDam, A., Fundamentals of Interactive Computer Graphics, Addison-Wesley, 1982.
6. Goldstein, R.A. and Malin, L., “3D Modeling with the Syntha Vision System,” First Annual Conference on Computer Graphics in CAD/CAM Systems, MIT, April 1979, pp. 244-247.
7. Hindel, B., Emulation and Invention, New York University Press, 1981.
8. Hubschman, H., and Zucker, S., “Frame-to-Frame Coherence and the Hidden Surface Computation: Constraints for a Convex World,” Computer Graphics, Vol. 15, No. 3, August 1981, pp. 45-54.
9. Myers, W., “An Industrial Perspective on Solid Modeling,” IEEE Computer Graphics and Applications, Vol. 2, No. 2, March 1982, pp. 86-97.
10. Requicha, A.A.G., and Voelcker, H.B., “Solid Modeling: A Historical Summary and Contemporary Assessment,” IEEE Computer Graphics and Applications, Vol. 2, No. 2, March 1982, pp. 9-24.
11. Romney, G.W., Computer Assisted Assembly and Rendering of Solids, Computer Science Department, University of Utah, TR-4-20, 1970.
12. Roth, S.D., “Ray Casting for Modeling Solids,” Computer Graphics and Image Processing, No. 18, 1982, pp. 109-144.
13. Sechrest, S., and Greenberg, D.P., “A Visible Polygon Reconstruction Algorithm,” Computer Graphics, Vol. 15, No. 3, August 1981, pp. 17-27.
14. Sutherland, I.E., Sproull, R.F., and Schumacher, R. A., “A Characterization of Ten Hidden-Surface Algorithms,” ACM Computing Surveys, Vol. 6, No. 1, March 1974, pp. 1-55.
15. Tilove, R.B., “Set Membership Clarification: A Unified Approach to Geometric Intersection Problems,” IEEE Transactions on Computers, Vol. C-29, No. 10, October 1980.
16. Voelcker, H.B., “Algorithms and Applications,” Tutorial on Solid Modeling, SIGGRAPH ’82 (ACM).
17. Watkins, G.S., A Real-Time Visible Surface Algorithm, Computer Science Department, University of Utah, UTECH-CSC-70-101, June 1970.
18. Wesley, M. A., Lozano-Perez, T., Lieberman, L. I., Lavin, M. A. and Grossman, D. D., “A Geometric Modeling System for Automated Mechanical Assembly,” IBM Journal of Research and Development, Vol. 24, No. 1, January 1980.
19. Wolfe, R., Fitzgerald, W., and Gracer, F., “Interactive Graphics for Volume Modeling” Proceedings of the IEEE Eighteenth Design Automation Conference, pp. 463-470.