“Fast constructive-solid geometry display in the pixel-powers graphics system” by Goldfeather, Hultquist and Fuchs

We present two algorithms for the display of CSG-defined objects on Pixel-Powers, an extension of the Pixel-Planes logic-enhanced memory architecture, which calculates for each and every pixel on the screen (in parallel) the value of any quadratic function in the screen coordinates (x,y). The first algorithm restructures any CSG tree into an equivalent, but possibly larger, tree whose display can be achieved by the second algorithm. The second algorithm traverses the restructured tree and generates quadratic coefficients and opcodes for Pixel-Powers. These opcodes instruct Pixel-Powers to generate the boundaries of primitives and perform set operations using the standard Z-buffer algorithm.Several externally-supplied CSG data sets have been processed with the new tree-traversal algorithm and an associated Pixel-Powers simulator. The resulting images indicate that good results can be obtained very rapidly with the new system. For example, the commonly used MBB test part (at right) with 24 primitives is translated into approximately 1900 quadratic equations. On a Pixel-Powers system running at 10MHz (the speed at which our current Pixel-Planes memories run), the image should be rendered in about 7.5 milliseconds.

1. Atherton, P.R., “A Scan-line Hidden Surface Removal Procedure for Constructive Solid Geometry” Computer Graphics, Vol. 17, No. 3, pp. 73-82, 1983. (Proceedings of SIGGP~APH ’83)
2. Fuchs, H., J. Goldfeather, J.P. Hultquist, S. Spach, J. A’ustin, F.P. Brooks, Jr., J. Eyles, and J.Poulton. “Fast Spheres, Textures, Transparencies, and Image Enhancements in Pixel-Planes” Computer Graphics, VoI. 19, No. 3, pp. 111-120, 1985. (Proceedings of SIGGRAPH ’85)
3. Goldfeather, J., H. Fuchs. “Quadratic Surface Rendering on a Logic-Enhanced Frame-Buffer Memory” IEEE Computer Graphics and Applications, pp. 48- 59, January, 1986.
4. Kedem, G., J.L. Ellis. “Computer Structures for Curve-Solid Classification in Geometric Modelling” Technical Report TR84-37, Microelectronic Center of North Carolina, Research Triangle Park, N.C., 1984.
5. Okino, N., Y. Kakazu, M. Morimoto. “Extended Depth Buffer Algorithms for Hidden Surface Visualization” IEEE Computer Graphics and Applications, pp. 79-88, May, 1984.
6. Poulton, J., H. Fuchs, J.D. Austin, J.G. Eyles, J. Heinecke, C. Hsieh, J. Goldfeather, J.P. Hultquist, and S. Spach. “PIXEL-PLANES: Building a VLSI Based Raster Graphics System” Proceeding8 of the i985 Chapel Hill Conference on VLSI, pp. 35-60.
7. Requicha, A.A.G. “Representation for Rigid Objects: Theory, Methods, and Systems” A CM Computing Surveys, Vol. 12, No. 4, Dec. 1980, pp. 437-464.
8. Sato, H., H. Ishihata, M. ishii, M. Kakimoto, K. Sato, K. Hirota, M. Ikesaka, K. Inoue. “Fast Image Generation of Constructive Solid Geometry Using A Cellular Array Processor” Computer Graphics, Vol. 19, No. 3, pp. 95-102, 1985. (Proceedings of SIG- GRAPH ’85)