An extension of manifold boundary representations to the r-sets

ABSTRACT

In this paper we study the relationship between manifold solids (r-sets whose boundaries are two-dimensional closed manifolds) and r-sets. We begin by showing that an r-set may be viewed as the limit of a certain sequence of manifold solids, where distance is measured using the Hausdorff metric. This permits us to introduce a minimal set of generalized Euler operators, sufficient for the construction and manipulation of r-sets. The completeness result for ordinary Euler operators carries over immediately to the generalized Euler operators on the r-sets and the modification of the usual boundary data structures, corresponding to our extension to nonmanifold r-sets, is straightforward. We in fact describe a modification of a well-known boundary data structure in order to illustrate how the extension can be used in typical solid modeling algorithms, and describe an implementation. The results described above largely eliminate what has been called an inherent mismatch between the modeling spaces defined by manifold solids and by r-sets. We view the r-sets as a more appropriate choice for a modeling space: in particular, the r-sets provide closure with respect to regularized set operations and a complete set of generalized Euler operators for the manipulation of boundary representations, for graphics and other purposes. It remains to formulate and prove a theorem on the soundness of the generalized Euler operators.

REFERENCES

• 1: Bruce G. Baumgart, GEOMED - a geometric editor., Stanford University, Stanford, CA, 1974
• 2: B^VMGART, B. Geometric modeling for computer vision. PhD thesis, Standford Univ. (also as Tech. Rep. CS-463), 1974.
• 3: Bruce G. Baumgart, Winged edge polyhedron representation., Stanford University, Stanford, CA, 1972
• 4: BRAID, I. C., HILLYARD, R. C., AND STROUD, I. A. Stepwise construction of polyhedra in geometric modelling. In Mathematical Methods in Computer Graphics and Design, K. W. Brodlie, Ed., Academic Press, 1980, 123-141.
• 5: DIEUDONN~, J. Foundations of Modern Analysis. Academic Press, New York, 1960.
• 6: JXNICH, K. Topology. Springer Verlag, 1980.
• 7: LIGHTmLL, M. J. Introduction to Fourier analysis and generalised functions. Cambridge Univ. Press, 1970.
• 8: LOJASmWlCZ, S. Triangulation of semi-analytic sets. Annali della Scuola Normale Superiore de Pisa, Annali Scienze, Fisiche i Mathimatiche Serie III 18 (1964), 449-474.
• 9: 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]
• 10: MJtNTYL~, M. Computational topology. In Acta Polytechnica Scandinavica, Mathematics and Computer Science Series, No. 37, Helsinki, 1983, 1-49.
• 11: Martti Mäntylä, An inversion algorithm for geometric models, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.51-59, July 1982
• 12: M.~NTYLA, M. A note on the modeling space of Euler operators. Comput. Vision Graph. Image Process. 26, 1 (Apr. 1984), 45-60.
• 13: MANTYLA, M., AND SULONEN, R. GWB: A solid modeler with Euler operators. IEEE Comput. Graph. Appl. 2, 7 (Sept. 1982), 17-31.
• 14: M~NTYn)~, M. Solid Modeling. Computer Science Press, 1988.
• 15: REQUICHA, A. A.G. Mathematical models of rigid solid objects. Technical Memo TM-28, Univ. of Rochester, 1977.
• 16: REQUICHA, A. A. G., AND VOELCKER, H.B. Boolean operations in solid modeling: boundary evaluation and merging algorithms. Proc. IEEE. 73, I (Jan. 1985), 30-44.
• 17: REQUICHA, A. A. G. AND VOELCKER, H. B. Solid Modeling: current status and research directions. 1EEE Comput. Graph. Appl. 3, 7 (Oct. 1983), 25-37.
• 18: ROHLIN, V., AND FUCHS, D. Premier Cours de Topologie. Editions MIR, Moscow, 1977.
• 19: ROSSIGNAC, J. R. aND O'CONNOR, M.A. SGC: A dimension-independent model for peintsets with internal structures and incomplete boundaries. In Geometric Modeling for Product Engineering, M. J. Wozny, J. U. Turner and K. Preiss, Eds., North-Holland, 1990, 145-180.
• 20: SP^Nma, E.H. Algebraic Topology. McGraw Hill, 1966.
• 21: Thomas A. Standish, Data Structure Techniques, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1980
• 22: WEmSR, K. Boundary graph operators for non-manifold geometric modeling topology representations. In Geometric Modeling for CAD Applications, M. J. Wozny, H. W. McLaughlin and J. L. Encarna~ao, Eds., North-Holland, 1988, 37-66.
• 23: WEILER, K. The radial edge structure: A topological representation for non-manifold geometric boundary modeling. In Geometric Modeling for CAD Applications, M. J. Wozny, H. W. McLaughlin and J.L. Encarna~ao, Eds., North-Holland, 1988, 3-36.
• 24: WEILER, K. Topological structures for geometric modeling. PhD thesis, Rensselaer Polytechnic Institute, Troy, N.Y., 1986,
• 25: Wu, SmN-TING. A new combinatorial model for boundary representations. Comput. Graph. 13, 4 (1989), 477-486.

INDEX TERMS

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

General Terms:
Algorithms, Design, Theory

Keywords:
Euler operators, data structures, manifold object, nonmanifold objects, r-set