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.
- 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 Scholar
- 2 BRUNET, P., AND AYALA, }'L Extended octtree representation of free form surfaces. Comput.- Aided Geom. Des. 4, 1-2 (1987), 141-154. Google Scholar
- 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 Scholar
- 4 CARLBOM, I. An algorithm for geometric set operations using cellular subdivision techniques. IEEE Comput. Gr. Appl. 7, 5 (1987), 44-55. Google Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 10 Gargantini, I. Linear octtrees for fast processing of three dimensional objects. Comput. Gr. Image Process. 20 (1982), 365-374.Google Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 15 MANTYLA, M. Boolean ope~:ations of 2-manifolds through vertex neighborhood classification. ACM Trans. Gr. 5, 1 (1986), }.-29. Google Scholar
- 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 Scholar
- 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 Scholar
- 18 MEAGHER, D. Geometric modeling using octree encoding. Comput. Gr. image Process. 19 (1982), 129-147.Google Scholar
- 19 NAVAZO, i. Geometric modelling of octree encoded polyhedral objects. Doct. thesis, Sistemes inform~ties Universitat Politecnica de Catalunya, Barcelona, Spain, 1986.Google Scholar
- 20 NAVAZO, I. Extended octree representation of general solids with plane faces: Model structure and algorithms. Comput. Gr. 13, 1 (1989), 5-16.Google Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 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 Scholar
- 26 SAMF.T, H. Region representation: Quadtrees from boundary codes. Commun. ACM 23, 3 (1980), 163-170. Google Scholar
- 27 SAMET, H. The quadtree and related hierarchical data structures. A CM Comput. Surv. 16, 2 (1984), 187-260. Google Scholar
- 28 SAMET, H., AND TAMMINEN, M. Bintrees, CSG trees and time. Comput. Gr. ACM 19~ 3 (1985), 121-130. Google Scholar
- 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 Scholar
- 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 Scholar
- 31 WYVILL, G., AND KUNII, W.L. Space division for ray tracing in CSG. IEEE Comput. Gr. Appl. 6, 4 (1986), 28-34. Google Scholar
- 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 Scholar
Index Terms
Solid representation and operation using extended octrees
Recommendations
Object representation by means of nonminimal division quadtrees and octrees
Quadtree representation of two-dimensional objects is performed with a tree that describes the recursive subdivision of the more complex parts of a picture until the desired resolution is reached. At the end, all the leaves of the tree are square cells ...
Quality isosurface mesh generation using an extended marching cubes lookup table
EuroVis'08: Proceedings of the 10th Joint Eurographics / IEEE - VGTC conference on VisualizationThe Marching Cubes Algorithm may return degenerate, zero area isosurface triangles, and often returns isosurface triangles with small areas, edges or angles. We show how to avoid both problems using an extended Marching Cubes lookup table. As opposed to ...
Topological simplification of isosurfaces in volumetric data using octrees
Volumetric data, such as output from CT scans or laser range scan processing methods, often have isosurfaces that contain topological noise-small handles and holes that are not present in the original model. Because this noise can significantly degrade ...
Comments