Constructive topological representations

ABSTRACT

Constructive representations, such as Constructive Solid Geometry (CSG) and its various feature-based extensions are inherently parametric in nature and are well suited for defining parametric family of solids. On the other hand, cell complex representations contain explicit shape elements (cells) and also their topology. However they are non-constructive, difficult to parameterize, and it is extremely difficult to enforce continuity in the usual cell complex topology (considered as a sub-space of Euclidean space). When cell complexes are used in conjunction with constructive representations, even if we can enforce continuity in limited cases, it is impossible to relate cellular operations with global semantics of constructive operations (such as Boolean and feature operations).Using the framework developed in our earlier work for defining part families on any solid representation, we propose constructive topological representations by identifying every constructive representation with its corresponding unique spatial decomposition. By applying the proposed definitions to spatial CSG representations we will systematically develop algorithms for topologizing a CSG and also enforcing continuity between two given topologized CSG representations. These algorithms have been implemented in a prototype system about which we will briefly discuss. Finally, we will illustrate some interesting applications of the proposed constructive topological representations: specification of constructive families and the enforcement of global semantics of feature operations.

REFERENCES

• 1: Capoyleas, V., Chen, X., and Hoffmann, C. M. 1996. Generic naming in generative, constraint-based design. Computer-Aided Design 28, 1, 17--26.
• 2: Chen, X., and Hoffmann, C. M. 1995. Towards feature attachment. Computer-Aided Design 27, 675--702.
• 3: Jänich, K. 1983. Topology. Springer-Verlag, New York.
• 4: Kinsey, C. 1993. Topology of Surfaces. Springer-Verlag, New York.
• 5: Kripac, J. 1997. A mechanism for persistently naming topological entities in history-based parametric solid models. Computer-Aided Design 29, 2, 113--122.
• 6: M. Mantyla, Introduction to Solid Modeling, W. H. Freeman & Co., New York, NY, 1988
• 7: Munkres, J. R. 1975. Topology A First Course. Prentice Hall, Englewood Cliffs, New Jersey.
• 8: Pro-Engineer. 1998. Pro-Engineer Documentation, Version 20. PTC, Waltham, MA.
• 9: Srinivas Raghothama , Vadim Shapiro, Models and representations for parametric families of parts, 2000
• 10: Ari Rappoport, Geometric modeling: a new fundamental framework and its practical implications, Proceedings of the third ACM symposium on Solid modeling and applications, p.31-41, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218027]
• 11: Requicha, A. A. G., and Tilove, R. B. 1978. Mathematical foundations of constructive solid geometry: General topology of closed regular sets. Tech. rep., TM-27a, PAP, University of Rochester, Rochester, NY, June.
• 12: 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]
• 13: Rossignac, J. R., Borrel, P., and Nackman, L. R. 1988. Interactive design with sequences of parameterized transformations. In Proc. of 2nd Eurographics Workshop in Intelligent CAD Systems: Implementation Issues.
• 14: Jaroslaw Roman Rossignac, Blending and offsetting solid models (cad/cam, computational geometry, representations, curves, surfaces, approximation), 1985
• 15: Vadim Shapiro , Donald L. Vossler, Construction and optimization of CSG representations, Computer-Aided Design, v.23 n.1, p.4-20, Jan./Feb. 1991 [doi>10.1016/0010-4485(91)90077-A ]
• 16: Shapiro, V., and Vossler, D. L. 1991. Efficient CSG representations of two dimensional solids. Transactions of the ASME, Journal of mechanical design 113 (Sept.), 292--305.
• 17: Vadim Shapiro , Donald L. Vossler, Separation for boundary to CSG conversion, ACM Transactions on Graphics (TOG), v.12 n.1, p.35-55, Jan. 1993 [doi>10.1145/169728.169723]
• 18: Vadim Shapiro , Donald L. Vossler, What is a parametric family of solids?, Proceedings of the third ACM symposium on Solid modeling and applications, p.43-54, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218029]
• 19: Shapiro, V. 1997. Maintenance of geometric representations through space decompositions. International Journal of Computational Geometry and Applications 7, 4, 383--418.
• 20: Solidworks. 2000. SolidWorks 2000 Documentation. Solid-Works Corp, Concord, MA.
• 21: Srinivas Raghothama , Vadim Shapiro, Boundary representation deformation in parametric solid modeling, ACM Transactions on Graphics (TOG), v.17 n.4, p.259-286, Oct. 1998 [doi>10.1145/293145.293148]
• 22: S. Raghothama, and V. Shapiro. 2000. Consistent updates in dual representation systems. Computer-Aided Design 32, 8--9 (Aug.), 463--477.
• 23: S. Raghothama, and V. Shapiro. 2003. Topological framework for part families. ASME Journal of Computing and Information Sciences 32, 8--9 (Mar.).
• 24: Unigraphics. 2004. NX4.0 Documentation. UGS Corp, Cypress, CA.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Modeling and recovery of physical attributes

General Terms:
Algorithms, Theory