A null-object detection algorithm for constructive solid geometry

ABSTRACT

Constructive solid geometry (CSG) is the primary scheme used for representing solid objects in many contemporary solid modeling systems. A CSG representation is a binary tree whose nonterminal nodes represent Boolean operations and whose terminal nodes represent primitive solids. This paper deals with algorithms that operate directly on CSG representations to solve two computationally difficult geometric problems—null-object detection (NOD) and same-object detection (SOD). The paper also shows that CSG trees representing null objects may be reduced to null trees through the use of a new concept called primitive redundancy, and that, on average, tree reduction can be done efficiently by a new technique called spatial localization. Primitive redundancy and spatial localization enable a single complex instance of NOD to be converted into a number of simpler subproblems and lead to more efficient algorithms than those previously known.

REFERENCES

• 1: Bentley, J.L. and Ottman, T.A. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. C-28, 9 (Sept. 1979), 643-647.
• 2: Bentley, J.L. and Wood, D. An optimal worst case algorithm for reporting intersections of rectangles. IEEE Trans. Comput. C-29, 7 (July 1980), 571-576.
• 3: Boyse, J.W. Preliminary design for a geometric modeller. Res. Pub. GMR-2768, Computer Science Dept., General Motors Research Laboratories, July 1978.
• 4: John W. Boyse, Interference detection among solids and surfaces, Communications of the ACM, v.22 n.1, p.3-9, Jan. 1979 [doi>10.1145/359046.359048]
• 5: Boyse, J.W. and Gilchrist, J.E. GMSolid: Interactive modeling for design and analysis of solids. IEEE Comput Gr. Appl. 2, 2 (March 1982), 27-40.
• 6: Brown, C.M. PADL-2: A technical summary. IEEE Comput. Gr. Appl. 2, 2 (March 1982), 69-84.
• 7: Eastman, C.M. and Lividini, J. Spatial search. Workshop on Computer Representation of Physical Systems, Pittsburgh, PA, August 1976.
• 8: Edelsbrunner, H. A time- and space-optimal solution for the planar all intersecting rectangles problem. Tech. Rept. Institut fur lnformatik, Technisch Universitat Graz, Graz, Austria, April 1980.
• 9: Franklin, W.R. Combinatories of hidden surface algorithms. Ph.D. dissertation Dept. Mathematics, Harvard University, Cambridge, MA, May 1978.
• 10: Goldstein, R. and Malin, L. 3-D modelling with the synthavision system. Proceedings of the 1st Annual Conference on Computer Graphics in CAD-CAM Systems (Cambridge, MA, April 1979), pp. 244-247.
• 11: Hunt, W.A. and Voelcker, H.B. An exploratory study of automatic verification of programs for numerically controlled machine tools. Tech. Memo. 34, Production Automation Project, Univ. of Rochester, Rochester, NY, Jan. 1982.
• 12: Kohli, U.S. An experimental study of null object detection algorithms (NOD) in E2. Int. Tech. Memo. 39, Production Automation Project, Univ. of Rochester, Rochester, NY, May 1981.
• 13: Mendelson, B. Introduction to Topology. Allyn & Bacon Inc., Boston, MA, 1975.
• 14: Okino, N., Kakazu, Y., and Kubo, H. TIPS-l: Technical information processing system for computer-aided design, drawing and manufacturing. In Computer Languages for Numerical Control, J. Hatvany, Ed, North-Holland, Amsterdam, 1973, pp. 141-150.
• 15: Requicha, A.G. and Tilove, R.B. Mathematical foundations of constructive solid geometry: General topology of regular closed sets. Tech. Memo. 27, Production Automation Project, Univ. of Rochester, Rochester, NY, March 1978.
• 16: 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]
• 17: Michael Ian Shamos, Computational geometry., 1978
• 18: Tilove, R.B. Set membership classification: A unified approach to geometric intersection problems. IEEE Trans. Comput. C-29, 10 (Oct. 1980), 874-883.
• 19: Tilove, R.B. Line/polygon classification: A study of the complexity of geometric computation. IEEE Comput. Gr. Appl. 1, 2 (April 1981), 75-88.
• 20: Tilove, R.B. Exploiting spatial and structural locality in geometric modelling. Ph.D. dissertation, Dept. of Electrical Engineering, Univ. of Rochester, Rochester, NY, October 1981. (Available as Tech. Memo. 38, Production Automation Project, Univ. of Rochester, Rochester, NY}, October 1981.
• 21: H. Voelcker , A. Requicha , E. Hartquist , W. Fisher , J. Metzger , R. Tilove , N. Birrell , W. Hunt , G. Armstrong , T. Check , R. Moote , J. McSweeney, The PADL-1.0/2 system for defining and displaying solid objects, Proceedings of the 5th annual conference on Computer graphics and interactive techniques, p.257-263, August 23-25, 1978

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

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

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
computational geometry, constructive geometry, geometric modeling, interference detection