Solid representation and operation using extended octrees

ABSTRACT

Solid modelers must be based on reliable and fast algorithms for Boolean operations. The octree model, as well as several generalizations (polytrees, integrated polytrees, extended octrees), is specially well suited for these algorithms and can be used either as a primary or as a secondary model in solid modeling systems. This paper is concerned with a precise definition of the extended octree model that allows the representation of nonmanifold objects with planar faces and, consequently, is closed under Boolean operations on polyhedrons. Boolean nodes and nearly vertex nodes are introduced, and the model is discussed in comparison with related representations. A fast algorithm for the direct generation of the extended octree from the geometry of the base polygon in extrusion solids is presented, and its complexity is studied. Boolean operation algorithms are introduced.

REFERENCES

• 1: D. Ayala , P. Brunet , R. Juan , I. Navazo, Object representation by means of nonminimal division quadtrees and octrees, ACM Transactions on Graphics (TOG), v.4 n.1, p.41-59, Jan. 1985 [doi>10.1145/3973.3975]
• 2: Pere Brunet , Dolores Ayala, Extended octtree representation of free form surfaces, Computer Aided Geometric Design, v.4 n.1-2, p.141-154, July 1987 [doi>10.1016/0167-8396(87)90031-8]
• 3: BRUNET, P., AND NAVAZO, I. Geometric modelling using exact octree representation of polyhedral objects. In Proceedings of Eurographics-85 (Nice, Sept. 9-13, 1985). North-Holland, Amsterdam, 1985, pp. 159-169.
• 4: Ingrid Carlbom, An algorithm for geometric set operations using cellular subdivision techniques, IEEE Computer Graphics and Applications, v.7 n.5, p.44-55, May 1987 [doi>10.1109/MCG.1987.276987]
• 5: CARLBOM, I., CHAKRAVARTY, I., AND VANDERSCHEL, D.A. A heirarchical data structure for representing the spatial decomposition of 3D objects. IEEE Comput. Gr. Appl. 5, 4 (1985), 24-31.
• 6: DURST, M. J., AND KUNII, T. L. Integrated polytrees: A generalized model for integrating spatial decomposition and boundary representation. Tech. Rep. 88-002, Dept. of information Science, Faculty of Science, Univ. of Tokyo, Jan. 1988. (Also to appear as Theory and practice of solid modelling. In Proceedings of Theory and Practice of Solid Modeling. W. Strasser, Ed., (Tubingen, W. Germany). Springer-Verlag, New York.)
• 7: ESTERLING, D.M. 3D micro-computer graphic NC program verification. In Proceedings of the 5th Annual Computer Aided Engineering Program Users Meeting (San Diego, Calif., 1987).
• 8: FUJIMURA, K., AND KUNt{, T.L. A hierarchical space indexing method. In Computer Graphics: Visual Technology and Art, Proceedings of Computer Graphics Tokyo '85, T. L. Kunii, Ed. Springer- Verlag, New York, 1985, pp. 21-34.
• 9: FUJIMURA, K., TORIYA, H., YAMAGUCHI, K., AND KUNII, T.L. Oct-tree algorithms for solid modelling. In Computer Graphics: Theory and Appl&ations, Proceedings of InterGraphics-83, T. L. Kunii, Ed. Springer-Verlag, New York, 1983, pp. 96-110. (Shortened version in IEEE Comput. Gr. Appl. 4 (1984), 53-59.)
• 10: Gargantini, I. Linear octtrees for fast processing of three dimensional objects. Comput. Gr. Image Process. 20 (1982), 365-374.
• 11: Christoph M. Hoffmann , John E. Hopcroft , Michael S. Karasick, Robust Set Operations on Polyhedral Solids, Cornell University, Ithaca, NY, 1987
• 12: JACKINS, C. H., AND TANIMOTO, S.L. Oct-trees and their use in representing three dimensional objects. Comput. Gr. Image Process. 14 (1980), 249-270.
• 13: JUAN, R. Contribution to tim study of the conversion from the boundary representation model and the extended octree model into the constructive solid geometry. Doct. thesis, Dept. Llenguatgeri Polytechnical Univ. of Catalonia, Barcelona, Spain, 1988.
• 14: KAWAGUCHI, E.,ANDENDO, r{~. Ona method of binary-picture representation and its application to data compression. IEEE Trans. Pattern Anal. Mach. Intell. 2, 1 (1980), 27-35.
• 15: Martti Mäntylä, Boolean operations of 2-manifolds through vertex neighborhood classification, ACM Transactions on Graphics (TOG), v.5 n.1, p.1-29, Jan. 1986 [doi>10.1145/7529.7530]
• 16: MEAGHER, D. Octree encoding: A new technique for the representation, manipulation and display of arbitrary three dimensional objects by computer. Tech. Rep. IPL,TR-80-111, Rensselaer Polytechnic institute, Troy, N.Y., 1980.
• 17: MEAGHER, D. Efficient synthetic image generation of arbitrary 3-D objects. In Proceedings of the IEEE Computer Society, Conference on Pattern Recognition and Image Processing. IEEE, New York, 1982, pp. 473-478.
• 18: MEAGHER, D. Geometric modeling using octree encoding. Comput. Gr. image Process. 19 (1982), 129-147.
• 19: NAVAZO, i. Geometric modelling of octree encoded polyhedral objects. Doct. thesis, Sistemes inform~ties Universitat Politecnica de Catalunya, Barcelona, Spain, 1986.
• 20: NAVAZO, I. Extended octree representation of general solids with plane faces: Model structure and algorithms. Comput. Gr. 13, 1 (1989), 5-16.
• 21: NAVAZO, I., AND FONTDECABA, J. Boolean operations using extended octrees. Rep. DMI01-86, Dept. de Metodes Informatics, Polytechnical Univ. of Catalonia, Barcelona, Spain, 1986. (In Catalan.)
• 22: I Navazo , D Ayala , P Brunet, A geometric modeller based on the exact octtree representation of polyhedra, Computer Graphics Forum, v.5 n.2, p.91-104, June 1986 [doi>10.1111/j.1467-8659.1986.tb00278.x]
• 23: NAVAZO, I., BRUNET, P., AND FONTDECABA, J. Extended octrees, between CSG trees and boundary representations. In Proceedings o{ Eurographics-87. North-Holland, Amsterdam, 1987 pp. 239-247.
• 24: REQUICHA, A. A. G., AND VOELCKER, H.B. Solid modelling: Current status and research directions. IEEE Comput. Gr. Appl. 3, 7 (1983), 25-37.
• 25: REQUICHA, A. A. G., AND VOELCKER, H.B. Boolean operations in solid modelling: Boundary evaluations and merging algorithms. TM-26 Prod. Autom. Proj. Univ. of Rochester, N.Y., 1984. (Also in Proc. IEEE 73 (1985).)
• 26: Hanan Samet, Region representation: quadtrees from boundary codes, Communications of the ACM, v.23 n.3, p.163-170, March 1980 [doi>10.1145/358826.358836]
• 27: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
• 28: Hanan Samet , Markku Tamminen, Bintrees, CSG trees, and time, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.121-130, Jul. 1985
• 29: Hanan Samet , Robert E. Webber, Hierarchical Data Structures and Algorithms for Computer Graphics. Part I., IEEE Computer Graphics and Applications, v.8 n.3, p.48-68, May 1988 [doi>10.1109/38.513]
• 30: Hanan Samet , Robert E. Webber, Hierarchical Data Structures and Algorithms for Computer Graphics. Part I., IEEE Computer Graphics and Applications, v.8 n.3, p.48-68, May 1988 [doi>10.1109/38.513]
• 31: Geoff Wyvill , Tosiyasu L Kunii , Yasuto Shirai, Space division for ray tracing in CSG, IEEE Computer Graphics and Applications, v.6 n.4, p.28-34, April 1986 [doi>10.1109/MCG.1986.276717]
• 32: WOODWARK, J. R., AND WALLIS, A.F. Creating large solid models for NC toolpath verification. In Proceedings of the CAD 84 Conference (Brighton, England). 1984, pp. 455-460.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Modeling packages

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: Curve, surface, solid, and object representations
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

General Terms:
Algorithms, Design