Depth-order point classification techniques for CSG display algorithms

ABSTRACT

Constructive Solid Geometry (CSG) defines objects as Boolean combinations (CSG trees) of primitive solids. To display such objects, one must classify points on the surfaces of the primitive solids with respect to the resulting composite object, to test whether these points lie on the boundary of the composite object or not. Although the point classification is trivial compared to the surface classification (i.e., the computation of the composite object), for CSG models with a large number of primitive solids (large CSG trees), the point classification may still consume a considerable fraction of the total processing time. This paper presents an overview of existing and new efficiency-improving techniques for classifying points in depth order. The different techniques are compared through experiments.

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: BRONSVOORT, W. F., VAN WIJK, J. J., ANO JANSEN, F. W. Two methods for improving the efficiency of ray casting in solid modelling. Comput.-Aided Des. 16, 1 {1984), 51-55.
• 3: W F Bronsvoort, Techniques for reducing Boolean evaluation time in CSG scan-line algorithms, Computer-Aided Design, v.18 n.10, p.533-538, Dec. 1986 [doi>10.1016/0010-4485(86)90041-2]
• 4: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 5: Jack Goldfeather , Jeff P M Hultquist , Henry Fuchs, Fast constructive-solid geometry display in the pixel-powers graphics system, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.107-116, Aug. 1986
• 6: GOLOSTEIN, R. A., AND NAaEL, R. 3-D simulation. Simulation 16, I (1971), 25-31.
• 7: JANSEN, F.W. A CSG list priority hidden-surface algorithm. In Proceedings Eurographics '85 Con{erence, Elsevier Science, New York, 1985, 51-62.
• 8: JANSEN, F.W. A pixel-parallel hidden-surface algorithm for constructive solid geometry. In Proceedings Eurographics '86 Conference, Elsevier Science, New York, 1986, 29-40.
• 9: KEDEM, G., AND HAMMOND, S. W. The point classifier: A VLSI processor for displaying complex two dimensional objects. {n Proceedings of the I985 Chapel Hill Conference on VLSI, Computer Science Press, Rockville, Md., 1985, 377-392.
• 10: Yong Tsui Lee , Aristides A. G. Requicha, Algorithms for computing the volume and other integral properties of solids. II. A family of algorithms based on representation conversion and cellular approximation, Communications of the ACM, v.25 n.9, p.642-650, Sept 1982 [doi>10.1145/358628.358648]
• 11: NEWELL, M. E., NEWELL, R. G., AND SANCHA, T.L. A new approach to the shaded picture problem. In Proceedings o{ the ACM National Con{erence (1972). ACM, New York, 1972, 443-450.
• 12: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 13: OKINO, N., KAKAZU, Y., AND MOmMOTO, M. Extended depth-buffer algorithms for hiddensurface visualization. IEEE Comput. Gr. Appl. 4, 5 (1984), 79-88.
• 14: PLUNKEq~r, D. J., AND BAILEY, M.J. The vectorization of a ray tracing algorithm for improved execution speed. IEEE Comput. Gr. Appl. 5, 8 (1985), 53-60.
• 15: 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]
• 16: ROS$1GNAC, J. R., AND REQUICHA, A. A.G. Depth-buffering display techniques for constructive solid geometry. IEEE Comput. Gr. Appl. 6, 9 (1986), 29-39.
• 17: Jaroslaw R. Rossignac , Herbert B. Voelcker, Active zones in CSG for accelerating boundary evaluation, redundancy elimination, interference detection, and shading algorithms, ACM Transactions on Graphics (TOG), v.8 n.1, p.51-87, Jan. 1989 [doi>10.1145/49155.51123]
• 18: ROTH, S.D. Ray casting for modeling solids. Cornput. Gr. Image Process. 18, 2 {1982), 109-144.
• 19: Hanan Samet , Markku Tamminen, Bintrees, CSG trees, and time, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.121-130, Jul. 1985
• 20: 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
• 21: S~.ARS, K. H., AND MIDOLETICH, A.E. Set-theoretic volume model evaluation and pictureplane coherence. IEEE Cornput. Gr. AppL 4, 3 (1984), 41-46.
• 22: A. L. Thomas, Geometric modelling and display primitives towards specialised hardware, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.299-310, July 25-29, 1983, Detroit, Michigan, United States
• 23: TILOVE, R. B. Set membership classification: A unified approach to geometric intersection problems. IEEE Trans. Comput. C-29, 10 (1980), 874-883.
• 24: TILOVE, R. B., REQUICHA, A. A. G., AND HOPKINS, M.R. Efficient editing of solid models by exploiting structural and spatial locality. Comput.-Aided Geom. Des. l, 3 (1984), 227-239.
• 25: Hank Weghorst , Gary Hooper , Donald P. Greenberg, Improved Computational Methods for Ray Tracing, ACM Transactions on Graphics (TOG), v.3 n.1, p.52-69, Jan. 1984 [doi>10.1145/357332.357335]
• 26: Turner Whitted, An improved illumination model for shaded display, Communications of the ACM, v.23 n.6, p.343-349, June 1980 [doi>10.1145/358876.358882]
• 27: WOODWARK, J. R., AND QUINLAN, K.M. Reducing the effect of complexity on volume model evaluation. Comput. Aided Des. 14, 2 (1982), 89-95.
• 28: WIJK, J. J. VAN On new types of solid models and their visualization with ray tracing, Ph.D. dissertation, Delft University Press, 1986.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Constructive solid geometry (CSG)**

General Terms:
Algorithms, Design, Experimentation