skip to main content
article
Free Access

Solid representation and operation using extended octrees

Published:01 April 1990Publication History
Skip Abstract Section

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. 1 AYALA, D., BRUNET, P., JUAN, R., AND NAVAZO, I. Object representation by means of non minimal division quadtrees and octrees. ACM Trans. Gr. 4, 1 (1985), 41-59. Google ScholarGoogle Scholar
  2. 2 BRUNET, P., AND AYALA, }'L Extended octtree representation of free form surfaces. Comput.- Aided Geom. Des. 4, 1-2 (1987), 141-154. Google ScholarGoogle Scholar
  3. 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.Google ScholarGoogle Scholar
  4. 4 CARLBOM, I. An algorithm for geometric set operations using cellular subdivision techniques. IEEE Comput. Gr. Appl. 7, 5 (1987), 44-55. Google ScholarGoogle Scholar
  5. 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.Google ScholarGoogle Scholar
  6. 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.)Google ScholarGoogle Scholar
  7. 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).Google ScholarGoogle Scholar
  8. 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.Google ScholarGoogle Scholar
  9. 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.)Google ScholarGoogle Scholar
  10. 10 Gargantini, I. Linear octtrees for fast processing of three dimensional objects. Comput. Gr. Image Process. 20 (1982), 365-374.Google ScholarGoogle Scholar
  11. 11 HOFFMANN, C. M., HOPCROFT, J. E., AND KARASICK, M.S. Robust set operations on polyhedral solids. Rep. 87-875, Dept. of Computer Science, Cornell Univ., Ithaca, N.Y., 1987. Google ScholarGoogle Scholar
  12. 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.Google ScholarGoogle Scholar
  13. 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.Google ScholarGoogle Scholar
  14. 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.Google ScholarGoogle Scholar
  15. 15 MANTYLA, M. Boolean ope~:ations of 2-manifolds through vertex neighborhood classification. ACM Trans. Gr. 5, 1 (1986), }.-29. Google ScholarGoogle Scholar
  16. 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.Google ScholarGoogle Scholar
  17. 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.Google ScholarGoogle Scholar
  18. 18 MEAGHER, D. Geometric modeling using octree encoding. Comput. Gr. image Process. 19 (1982), 129-147.Google ScholarGoogle Scholar
  19. 19 NAVAZO, i. Geometric modelling of octree encoded polyhedral objects. Doct. thesis, Sistemes inform~ties Universitat Politecnica de Catalunya, Barcelona, Spain, 1986.Google ScholarGoogle Scholar
  20. 20 NAVAZO, I. Extended octree representation of general solids with plane faces: Model structure and algorithms. Comput. Gr. 13, 1 (1989), 5-16.Google ScholarGoogle Scholar
  21. 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.)Google ScholarGoogle Scholar
  22. 22 NAVAZO, I., AYALA, D., AND BRUNET, P. A geometric modeller based on the exact octree representation of polyhedra. Comput. Gr. Forum 5, 2 (1986), 91-104. Google ScholarGoogle Scholar
  23. 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.Google ScholarGoogle Scholar
  24. 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.Google ScholarGoogle Scholar
  25. 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).)Google ScholarGoogle Scholar
  26. 26 SAMF.T, H. Region representation: Quadtrees from boundary codes. Commun. ACM 23, 3 (1980), 163-170. Google ScholarGoogle Scholar
  27. 27 SAMET, H. The quadtree and related hierarchical data structures. A CM Comput. Surv. 16, 2 (1984), 187-260. Google ScholarGoogle Scholar
  28. 28 SAMET, H., AND TAMMINEN, M. Bintrees, CSG trees and time. Comput. Gr. ACM 19~ 3 (1985), 121-130. Google ScholarGoogle Scholar
  29. 29 SAMET, H,, AND WEBBER, R. E. Hierarchical data structures and algorithms for computer graphics, part i: Fundamentals. IEEE Comput. Gr. Appl. 8, 3 (1988), 48-68. Google ScholarGoogle Scholar
  30. 30 SAMET, H., AND WEBBER, R. E. Hierarchical data structures and algorithms for computer grahics, part II: Applications. IEEE Comput. Gr. Appl. 8, 4 (1988), 59-75. Google ScholarGoogle Scholar
  31. 31 WYVILL, G., AND KUNII, W.L. Space division for ray tracing in CSG. IEEE Comput. Gr. Appl. 6, 4 (1986), 28-34. Google ScholarGoogle Scholar
  32. 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.Google ScholarGoogle Scholar

Index Terms

  1. Solid representation and operation using extended octrees

              Recommendations

              Comments

              Login options

              Check if you have access through your login credentials or your institution to get full access on this article.

              Sign in

              Full Access

              • Published in

                cover image ACM Transactions on Graphics
                ACM Transactions on Graphics  Volume 9, Issue 2
                April 1990
                86 pages
                ISSN:0730-0301
                EISSN:1557-7368
                DOI:10.1145/78956
                Issue’s Table of Contents

                Copyright © 1990 ACM

                Publisher

                Association for Computing Machinery

                New York, NY, United States

                Publication History

                • Published: 1 April 1990
                Published in tog Volume 9, Issue 2

                Permissions

                Request permissions about this article.

                Request Permissions

                Check for updates

                Qualifiers

                • article

              PDF Format

              View or Download as a PDF file.

              PDF

              eReader

              View online with eReader.

              eReader