Active zones in CSG for accelerating boundary evaluation, redundancy elimination, interference detection, and shading algorithms

ABSTRACT

Solids defined by Boolean combinations of solid primitives may be represented in constructive solid geometry (CSG) as binary trees. Most CSG-based algorithms (e.g., for boundary evaluation, graphic shading, interference detection) do various forms of set-membership classification by traversing the tree associated with the solid. These algorithms usually generate intermediate results that do not contribute to the final result, and hence may be regarded as redundant and a source of inefficiency. To reduce such inefficiencies, we associate with each primitive A in a tree S an active zone Z that represents the region of space where changes to A affect the solid represented by S, and we use a representation of Z instead of S for set-membership classification. In the paper we develop a mathematical theory of active zones, prove that they correspond to the intersection of certain nodes of the original trees, and show how they lead to efficient new algorithms for boundary evaluation, for detecting and eliminating redundant nodes in CSG trees, for interference (null-set) detection, and for graphic shading.

REFERENCES

• 1: David C Anderson, Closing the gap: A workstation-mainframe connection, Computers in Mechanical Engineering, v.4 n.6, p.16-24, May 1986
• 2: R. K. Brayton, Factoring logic functions, IBM Journal of Research and Development, v.31 n.2, p.187-198, March 1987
• 3: Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
• 4: CAMERON, S.A. Modelling solids in motion. Ph.D. thesis, Dept. of Artificial Intelligence, Univ. of Edinburgh, Scotland, 1984.
• 5: CAMERON, ~ " A ~,~-,,A,, ,-,e +h~. ,.,l~oh Aa~-.-.o+; ...... hla,~ ;~., ,.nkr,~-;~o T,~ Proceedings "~ ~- kJ. l-l. IL O~I~.A~J.V IJ~. ULA~,~ ~.~IUOII UV~,~VJ.UlI..~JI',,,rP,JA',~I*.I IlL lu~vwwll~,o. J.IA ui ~t~-~. International Conference on Robotics and Automation (St. Louis, Mar.). IEEE, 1985, pp. 488-493.
• 6: Stephen Cameron, Efficient intersection tests for objects defined constructively, International Journal of Robotics Research, v.8 n.1, p.3-25, February 1989 [doi>10.1177/027836498900800101]
• 7: 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
• 8: Frederick J. Hill , Gerald R. Peterson, Introduction to Switching Theory and Logical Design, John Wiley & Sons, Inc., New York, NY, 1981
• 9: HILLYARD, R.C. The BUILD group of solid modellers. IEEE Comput. Graph. Appl. 2, 2 (Mar. 1982), 43-52.
• 10: JANSEN, F.W. Solid modelling with faceted primitives. Doctoral dissertation, Dept. of Industry Design, Technische Universiteit Delft, The Netherlands, Sept. 1987.
• 11: KEDEM, G., AND ELLIS, J. L. Computer structures for curve-solid classification in geometric modelling. Tech. Rep. TR84-37, Microelectronic Center of North Carolina, Research Triangle Park, N.C., 1984.
• 12: Yong Tsui Lee , Aristides A. G. Requicha, Algorithms for computing the volume and other integral properties of solids. I. known methods and open issues, Communications of the ACM, v.25 n.9, p.635-641, Sept 1982 [doi>10.1145/358628.358643]
• 13: NACKMAN, L. R., LAVIN, M. A., TAYLOR, R. H., AND DIETRICH, W.C. AML/X user's manual. Res. Rep. RA 175, IBM T. J. Watson Research Center, Yorktown Heights, N.Y., 1986.
• 14: Leo R. Nackman , Mark A. Lavin , Russell H. Taylor , Walter C. Dietrich, Jr. , David D. Grossman, AML/X: a programming language for design and manufacturing, Proceedings of 1986 ACM Fall joint computer conference, p.145-159, November 1986, Dallas, Texas, United States
• 15: OKINO, N., et al. TIPS-1. Institute of Precision Engineering, Hokkaido University, Sapporo, Japan, 1978.
• 16: D P Peterson, Boundary to constructive solid geometry mappings: a focus on 2D issues, Computer-Aided Design, v.18 n.1, p.3-14, Jan/Feb. 1986 [doi>10.1016/S0010-4485(86)80003-3]
• 17: REQUICHA, A. A.G. Mathematical models of rigid solid objects. Tech. Memo. 28, Production Automation Project, Univ. of Rochester, Rochester, N.Y., Nov. 1977. (Reports of the Production Automation Project are no lounger available from the University of Rochester, but may be obtained from CPA, 304 Kimball Hall, Cornell University, Ithaca, NY 14853.)
• 18: REQUICHA, A. A. G., AND TILOVE, R.B. Mathematical foundation of constructive solid geometry: General topology of closed regular sets. Tech. Memo. 27a, Production Automation Project, Univ. of Rochester, Rochester, N.Y., June 1978. (Reports of the Production Automation Project are no longer available from the University of Rochester, but may be obtained from CPA, 304 Kimball Hall, Cornell University, Ithaca, NY 14853.)
• 19: REQUICHA, A. A. G., AND VOELCKER, U.B. Constructive solid geometry. Tech. Memo. 25, Production Automation Project, Univ. of Rochester, Rochester, N.Y., Nov. 1977. (Reports of the Production Automation Project are no longer available from the University of Rochester, but may be obtained from CPA, ;304 Kimball Hall, Cornell University, Ithaca, NY 14853.)
• 20: REQUICHA, A. A. G., AND VOELCKER, H.B. Boolean operations in solid modelling:. Boundary evaluation and merging algorithms. In Proc. IEEE 73, 1 (Jan. 1985), 30-44.
• 21: Jaroslaw Roman Rossignac, Blending and offsetting solid models (cad/cam, computational geometry, representations, curves, surfaces, approximation), 1985
• 22: Jaroslaw R. Rossignac, Constraints in constructive solid geometry, Proceedings of the 1986 workshop on Interactive 3D graphics, p.93-110, January 1987, Chapel Hill, North Carolina, United States [doi>10.1145/319120.319129]
• 23: ROSSIGNAC, J. R., AND O'CONNOR, M.A. Selective geometric complexes: Representations and algorithms for processing and combining mixed dimensional geometric objects. IBM Research Division, T. J. Watson Research Center, Yorktown Heights, N.Y. In preparation.
• 24: ROSSIGNAC, J. R., AND REQUICHA, A. A. G. Constant radius blending in solid modelling. Comput. Mech. Eng. 3, 1 (July 1984), 65-73.
• 25: J R Rossignac , A A G Requicha, Offsetting operations in solid modelling, Computer Aided Geometric Design, v.3 n.2, p.129-148, August 1986 [doi>10.1016/0167-8396(86)90017-8]
• 26: ROSSIGNAC, J. R., AND REQUICHA, A. A.G. Depth buffering display techniques for constructive solid geometry. IEEE Comput. Graph. Appl. 6, 9 (Sept. 1986), 29-39.
• 27: ROTH, S.D. Ray casting for modeling solids. Comput. Graph. Image Process. 18, 2 (Feb. 1982), 109-144.
• 28: RUDEANU, S. Boolean Functions and Equations. North-Holland, Amsterdam, 1974.
• 29: SHANNON, C.E. A symbolic analysis of relay and switching circuits. Trans. A.I.E.E. 57 (1938), 713-723.
• 30: SHIRMA, Y., OKINO, N., AND KAKAZU, Y. Research on 3-D geometric modelling by sweep primitives. In Proceedings o/CAD '82 (Brighton, U.K., Mar. 30-Apr. 17). 1982, pp. 671-680.
• 31: SUNGURTEKIN, U. A., AND VOELCKER, H.B. Graphical simulation and automatic verification of NC machining programs. In Proceedings of the IEEE International Conference on Robots and Automation, vol. 1 (San Francisco, Apr. 7-10). 1986, IEEE, New York, pp. 156-165.
• 32: TILOVE, R. B. Set membership classification: A unified approach to geometric intersection problems. IEEE Trans. Comput. C-29, 10 (Oct. 1980), 874-883.
• 33: TILOVE, R.B. Exploiting spatial and structural locality in geometric modelling. Tech. Memo. 38, Production Automation Project, University of Rochester, Rochester, N.Y., Oct. 1981. {Reports of the Production Automation Project are no longer available from the University of Rochester, but may be obtained from CPA, 304 Kimball Hall, Cornell University, Ithaca, NY 14853.)
• 34: Robert B. Tilove, A null-object detection algorithm for constructive solid geometry, Communications of the ACM, v.27 n.7, p.684-694, July 1984 [doi>10.1145/358105.358195]
• 35: TILOVE, R. B., REQUICHA, A. A. G., AND HOPKINS, M.R. Efficient editing of solid models by exploiting structural and spatial locality. Tech. Memo. 46, Production Automation Project, Univ. of Rochester, Rochester, N.Y., May 1984. (Reports of the Production Automation Project are no longer available from the University of Rochester, but may be obtained from CPA, 304 Kimball Hall, Cornell University, Itbaca, NY 14853.)
• 36: VAN WIJK, J.J. Ray tracing objects defined by sweeping a sphere. In Proceedings of Eurographics '84 (Copenhagen, Sept. 12-14). Elseviers Science Publishers, Amsterdam, 1984, pp. 73-82.
• 37: VOSSLER, D.L. Sweep-to-CSG conversion using pattern recognition techniques. IEEE Comput. Graph. Appl. 5, 8 (Aug. 1985), 61-68.
• 38: Robert N. Wolfe , Michael A. Wesley , James C. Kyle Jr , Franklin Gracer , William J. Fitzgerald, Solid modeling for production design, IBM Journal of Research and Development, v.31 n.3, p.277-295, May 1, 1987
• 39: John R. Woodwark, Eliminating Redundant Primitives from Set-Theoretic Solid Models by a Consideration of Constituents, IEEE Computer Graphics and Applications, v.8 n.3, p.38-47, May 1988 [doi>10.1109/38.512]
• 40: WOODWARK, J. R., AND QDINLAN, K.M. Reducing the effect of complexity on volume model evaluation. Comput.-Aided Des. 14, 2 (Mar. 1982), 89-95.

INDEX TERMS

Primary 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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Simplification of expressions
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture; Visible line/surface algorithms

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

General Terms:
Algorithms, Design, Performance, Theory