“Fast image generation of construcitve solid geometry using a cellular array processor” by Inoue, Hirota, Kakimoto, Ishihata, Ikesaka, et al. …

A general purpose Cellular Array Processor(CAP) with distributed frame buffers for fast parallel subimage generation has been developed. CAP consists of many processor elements called cells. A cell has video memory for subimage storage, a window controller to map each subimage to an area on the monitor screen, and communication devices, in addition to ordinary microcomputer components such as MPU, RAM, and ROM. Image data in a cell is directly displayed via the video bus. The mapping pattern and the position on the screen of subimages can be changed dynamically. Various hidden surface algorithms can be implemented in CAP using mapping patterns appropriate for the algorithm.Our goal is an efficient interactive visual solid modeler. We adopted a general CSG hidden surface algorithm that enables display of both Boundary representation and Constructive Solid Geometry. A technique for hidden surface removal of general CSG models, requiring less memory space for large models in many cases, has been proposed. This technique subdivides the model into submodels by dividing the CSG tree at union nodes. Imagse of each submodel are generated by a CSG or a z-buffer algorithm. If a submodel is just a primitive, it is processed by the z-buffer algorithm, otherwise by the CSG algorithm. Hidden surface removal between submodels is done by comparing the z values for each pixel which are saved in the z-buffer.

1. Kaplan, M., and Greenberg, D.P.: “Parallel Processing Techniques for Hidden Surface Removal,” ACM Computer Graphics, Vol.~3, NO.2(Aug.1979), pp. 300- 307.
2. Fiume, E., Fournier, A., and Rudolph, L.: “A Parallel Scan Conversion Algorithm With Anti-Aliasing for a General-Purpose U1 t ra comput e r,” ACM Computer Graphics, Voi.17, No.3(Jul. 1983), pp.141-150.
3. Fuchs, H., and Johnson, B.W.: “An Expandable Multiprocessor Architecture for Video Graphics(Preliminary Report),” IEEE 6th conf. on Computer Architecture(1979), pp. 58-67.
4. Parke, F.I. :”Simulation and Expected Performance Analysis of Multi Processor Z- Buffer System, “ACM Computer Graphics(Jul.1980), pp.48-56.
5. Fuchs, H., and Poulton, J.: “Pixel-Planes: A VLSI-Oriented Design for a Raster Graphics Engine, VLSI Design, No.3, ~ 98~ , pp. 20-28.
6. Nishimura, H. ,Ohno, H.,Kawata, T., Shirakawa, I., and 0mura, K. : “LINKS-I : A Parallel Pipelined Multimicrocomputer System for Image Creation,” Proceedings of the I Oth Symposium on Computer Architecture, SIGARCH( 1983 ), pp. 387-394.
7. Dipp~, M., and Swensen, J.: “An Adaptive Subdivision Algorithm and Parallel Architecture for Realistic Image Synthesis,” ACM Computer Graphics, Vol. 18, No.3(Jul.1984), pp.149-158.
8. Niimi, H., Imai, Y., Murakami, M., Tomita, S., and Hagiwara, H. : “A Parallel Processor System for Three-Dimensional Color Graphics,” ACM Computer Graphics, Vol. 18, No.3(Jul. 1 984), pp. 67-76.
9. Hoshino, T., Shirakawa, T., Kamimura, T., Kageyama, T,, Takenouchi, K., Sekiguchi, T., and Kawai, T.:”Highly Parallel Processor Array PAX for Wide Scientific Applications, International Conference on Parallel Processing IEEE, pp. 95- 105, (Aug. 1 983)
10. Requicha, A.A.G., Voelcker, H.B. : “Solid Modeling: A Historical Summary and,, Contemporary Assessment,IEEE Computer Graphics and Applications, Vol.2, No.2, Mar. I 982, pp. 9-24.
11. Sutherland,I.E., Sproull,R.F.,and Schumacker, R.A. : “A Characterization of Ten Hidden-Surface Algorithms, ” ACM Computing Surveys, Vol.6, No.,(Mar. 1974), pp. 1-55.
12. Whitted, T.: “An Improved Illumination Model for Shaded Display, Comm., ACM, Vol.23, No. 6, 1980, pp. 343-349.
13. Atherton, P.R.: “A Scan-line Hidden Surface Removal Procedure for Constructive Solid Geometry,” ACM Computer Graphics, Vol.17, No.3(Jul. 1 983), pp. 73-82.
14. Crocker, G.A.: “Invisibility Coherence for Faster Scan-line Hidden Surface Algorithms,” ACM Computer Graphics, Vol. 18, No. 3 ( Jul. 1 984), pp. 95-1 02.
15. Roth, S.D.: “Ray Casting for Modeling Solids,” Computer Graphics and Image Processing, No. 18, 1982, pp. 109-144.
16. Foley, J.D. and Van Dam, A., Fundamentals of Interactive Computer Graphics, Addison- Wesley, 1982.
17. Murakami, K., Matsumoto, H.: “Ray tracing for CSG representation using status tree technique, ” 27th Information Processing Conference (Oct. 1 983), pp. 1535-1537(in Japanese)
18. Nelson, D. ,L. and Leach, P. ,J. : “The Architecture and Applications of the Apollo Domain,” IEEE Computer Graphics and Applications, Vol.4, No.4(Apr. 1984), pp.58-66