Boolean operations of 2-manifolds through vertex neighborhood classification

ABSTRACT

A topologically complete set operations algorithm for planar polyhedral Z-manifold objects is described; that is, under the assumption that all numerical tests required can be correctly evaluated, the algorithm is capable of solving all “special cases." The central component of the algorithm is a module here called the vertex neighborhood classifier. By virtue of the classifier, the various special cases can be reduced into a collection of classification problems involving a pair of coincident vertices. The classifier works by means of decision rules that guarantee the topological consistency and regularity of the resulting polyhedron. If the result is not a 2-manifold, a relaxed polyhedron will be produced.

REFERENCES

• 1: BAIJMC, ART, R Geometric modeling for computer vision. Ph.D. dissertation, Computer Science Dept., Stanford Univ. Stanford, Calif., 1974. Also as Tech. Rep. CS-463, Computer Science Dept., Stanford Univ.
• 2: BRAIn, I.C. Notes on a geometric modeller. CAD Group Document 101, Computer Laboratory._, Univ. of Cambridge, Cambridge, England, June 1979. (Revised 1980.)
• 3: BROWN, C.M. PADL-2: A technical summary. IEEE Comput. Graph. Appl. 2, 2 (Mar. 1982), 69-84.
• 4: HILLYARD, R. The BUILD family of solid modelers. IEEE Comput. Graph. Appl. 2, 2 (Mar. 1982), 43-52.
• 5: HOSAKA, M., KIMURA, F., AND KAKISHITA, N. A unified method for processing polyhedra. In Information Processing 1974. North-Holland Publ., Amsterdam, 1974.
• 6: HUNT, W. A. An explanatory study of automatic verification of programs for numerically controlled machine tools. M.S. thesis, Mechanical and Aerospace Sciences Dept., Univ. of Rochester, Rochester, N. Y., 1979.
• 7: KALAY, Y., AND EASTMAN, C.M. Shape operations, an algorithm for spatial set manipulations of solid objects. Res. Rep, 10, Dept. of Architecture, Carnegie-Mellon Univ., Pittsburgh, Pa., July 1~8o.
• 8: LANUSSE, A. A general algorithm for performing polyhedral set operations. Presentation given in SIAM Conference on Geometric Modeling and Robotics (Albany, N. Y., July 15-19). 1985.
• 9: lvlnr~TYLn, tvJ. Set operations algorithm oI t,w 5. t~omput. Graph. Forum 2, 2/3 (Aug. 1983), 122-134.
• 10: MhNTYLh, M. A note on the modeling space of Euler operators. Comput. Vision, Graph. Image Process. 26, 1 (Apr. 1984), 45-60.
• 11: M~.NTYL$,, M., AND SULONEN, R. GWB: A solid modeler with Euler operators. IEEE Comput. Graph. Appl. 2, 7 {Sept. 1982), 17-31.
• 12: Martti Mäntylä , Markku Tamminen, Localized set operations for solid modeling, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.279-288, July 1983
• 13: 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]
• 14: REQUICHA, A. A. G., AND VOELCKER, H.B. Constructive solid geometry. Tech. Memo. No. 27, Production Automation Project, Univ. of Rochester, Rochester, N. Y., 1977.
• 15: REQUlCHA, A. A. G., AND VOELCKER, H. B. Solid modeling: Current status and research directions. IEEE Comput. Graph. Appl. 3, 7 (Oct. 1983), 25-37.
• 16: REQUICHA, A. A. G., AND VOELCKER, H.B. Boolean operations in solid modeling: Boundary evaluation and merging algorithms. Proc. IEEE 73, 1 (Jan. 1985), 30-44.
• 17: Mark Segal , Carlo H. Séquin, Consistent calculations for solids modeling, Proceedings of the first annual symposium on Computational geometry, p.29-38, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323238]
• 18: STEINBERG, H.A. Overlap and separation calculations using the SynthaVision three dimensional solid modeling system. In Proceedings of the Conference on CAD/CAM Technology in Mechanical Engineering (Cambridge Mass., March 24-26). 1982, pp. 13-19.
• 19: STROWEIS, J., AND HANRAHAN, P. Spatial set operations on manifolds. Presentation given in SIAM Conference on Geometric Modeling and Robotics (Albany, N. Y., July 15-19). 1985.
• 20: TILOVE, R.B. Set membership classification: a unified approach to geometric intersection problems. IEEE Trans. Comput. C-29, 10 {Oct, 1982), 847-883.
• 21: VOELCKER, H. B., AND REQUICHA, A. A.G. Geometric modeling of physical parts and processes. IEEE Comput. 10, 2 {Dec. 1977), 48-57.
• 22: YAMAGUCHI F., AND TOKIEDA, T. A unified algorithm for Boolean shape operations. IEEE Comput. Graph. Appl. 4, 6 (June 1984), 24-37.

INDEX TERMS

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

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

General Terms:
Algorithms