Fast constructive-solid geometry display in the pixel-powers graphics system

ABSTRACT

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.

REFERENCES

• 1: Peter R Atherton, A scan-line hidden surface removal procedure for constructive solid geometry, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.73-82, July 25-29, 1983, Detroit, Michigan, United States
• 2: Henry Fuchs , Jack Goldfeather , Jeff P. Hultquist , Susan Spach , John D. Austin , Frederick P. Brooks, Jr. , John G. Eyles , John Poulton, Fast spheres, shadows, textures, transparencies, and imgage enhancements in pixel-planes, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.111-120, Jul. 1985
• 3: Jack Goldfeather , Henry Fuchs, Quadratic surface rendering on a logic-enhanced frame-buffer memory system, IEEE Computer Graphics and Applications, v.6 n.1, p.48-59, Jan.1986 [doi>10.1109/MCG.1986.276610]
• 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: Aristides G. Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, ACM Computing Surveys (CSUR), v.12 n.4, p.437-464, Dec. 1980 [doi>10.1145/356827.356833]
• 8: Hiroyuki Sato , Mitsuo Ishii , Keiji Sato , Morio Ikesaka , Hiroaki Ishihata , Masanori Kakimoto , Katsuhiko Hirota , Kouichi Inoue, Fast image generation of construcitve solid geometry using a cellular array processor, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.95-102, Jul. 1985

INDEX TERMS

Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms