A hierarchical boundary model for solid object representation

ABSTRACT

A new hierarchical model for solid object representation is described. This model, called a hierarchical face adjacency hypergraph (HFAH), is based on a relational description of the object boundary, called a face adjacency hypergraph (FAH), which considers faces as the primary topological entities defining the object boundary. The HFAH consists of a hierarchy of FAHs describing the decomposition of the boundary of an object into form features. In this paper the HFAH is described together with its internal encoding structure. Two basic transformations, called refinement and abstraction, are defined on the hierarchical model; these allow effective and efficient modifications of the hierarchical boundary model.

REFERENCES

• 1: ANCONA, M., DE FLORIANI, L., AND DEOGUN, J.S. Path problems in structured graphs. Comput. J. 29, 6 (1986), 553-563.
• 2: ANSALDI, S., DEFLORIANI, L., AND FALCIDIENO, B. Edge-face graph representation of solid objects. In Proceedings of the Workshop in Computer Vision, Representation and Control (Annapolis, Md., Apr. 30-May 2). IEEE, Silver Spring, Md., 1984, pp. 164-169.
• 3: Silvia Ansaldi , Leila De Floriani , Bianca Falcidieno, Geometric modeling of solid objects by using a face adjacency graph representation, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.131-139, Jul. 1985
• 4: ANSALDI, S., DE FLORIANI, L., AND FALCIDIENO, B. Form feature representation in a structured boundary model. In Image Armlysis and Processing, V. Cantoni, S. Levialdi, and G. Musso, Eds. Plenum, New York, 1986, pp. 111-120.
• 5: Bruce G. Baumgart, Winged edge polyhedron representation., Stanford University, Stanford, CA, 1972
• 6: BERGE, C. Graphes et Hypergraphes. Dunod, Paris, 1977.
• 7: CARIMATI, M. Data structure and Euler operators of the FAH representation. Tech. Rep. 12/86 PFTM CADME, Politecnico di Milano, Milan, Italy, 1986 (in Italian).
• 8: L. De Floriani, A graph based approach to object feature recognition, Proceedings of the third annual symposium on Computational geometry, p.100-109, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41968]
• 9: FALCIDIENO, B., AND GIANNINI, F. Feature extraction and organization into a structured boundary model. In Proceedings of EUROGRAPHICS '87 (Amsterdam, Sept. 1987). North Holland, Amsterdam, pp. 249-269.
• 10: Patrick M. Hanrahan, Creating volume models from edge-vertex graphs, Proceedings of the 9th annual conference on Computer graphics and interactive techniques, p.77-84, July 26-30, 1982, Boston, Massachusetts, United States
• 11: HARARY, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.
• 12: MEAGHER, D. Geometric modeling using octree encoding. Comput. Graph. Image Process. 19 {1982), 129-147.
• 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: SXLVA, C. Alternative definitions of faces in boundary representations of solid objects. Tech. Memo. 36, Production Automation Project, Univ. of Rochester, Rochester, N.Y., 1981.
• 15: WEILER, K. Edge-based data structures for solid modeling in curved-surface environment. IEEE Comput. Graph. Appl. 5, 1 (1985), 21-40.
• 16: WEILER, K. Topological structures for geometric modeling. Ph.D. dissertation, Rensselaer Polytechnic Institute, Troy, N.Y., Aug. 1986.
• 17: WXLSON, P. W., AND PRATT, ~d. Requirements for support of form features in a solid modelling system. Tech. Rep., Geometric Modelling Project, Computer Aided Manufacturing International, Arlington, Tex., 1985.
• 18: Woo, T. C. A combinatorial analysis of boundary data structure schemata. IEEE Comput. Graph. Appl. 5, 3 (1985), 19-27.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

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

General Terms:
Algorithms, Design