Automated conversion of curvilinear wire-frame models to surface boundary models; a topological approach

ABSTRACT

An algorithm is presented for automatically converting data representing unambiguous, three-dimensional objects in wire-frame form with curvilinear edges into a boundary representation. The method is an important extension to a previously published algorithm based on graph theory and topology. The new method automatically detects and resolves anomalies, such as necks which may appear to be faces, that formerly required human intervention. The topological basis for the solution to this problem is given along with a description of what topological properties a well defined three-dimensional object should have. An implementation has been coded and examples of results are included.

REFERENCES

• BREW83a: Brewer, J. A., "User's Guide: Computer Graphics Program for Generation of Engineering Geometry (SKETCH)", Waterways Experiment Station Report No. k-83-2, June 1983.
• BREW83b: Brewer, J. A., "Reference Manual: Computer Graphics Program for Generation of Engineering Geometry (SKETCH)", Waterways Experiment Station Report No. k-83-2, September 1983.
• COBB78: Cobb, E. C., "On the Extraction of Solid Geometry from a Wire Frame Geometric Data Base", M.S. Thesis, University of Wisconsin-Madison, 1978.
• DEO74: Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science (Prentice Hall Series in Automatic Computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1974
• DUTT83: Dutton, R. D. and R. C. Brigham, "Efficiently Identifying the Faces of a Solid", COMPUTERS AND GRAPHICS IN MECHANICAL ENGINEERING"-- 7(2): 143-147; 1983.
• GANT83: Ganter, M. A. and J. J. Uicker, "From Wire-Frame to Solid Geometric: Automated Conversion of Data Representations", COMPUTERS IN MECHANICAL ENGINEERING-- 2(2):40-45 (Sept. '83).
• HANR82: Patrick M. Hanrahan, Creating volume models from edge-vertex graphs, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.77-84, July 1982
• HOCK61: Hocking, J. G. and G. S. Young, TOPOLOGY, Addison-Wesley, Reading, MA, 1061.
• IDES73: Idesawa, M., "A System to Generate a Solid Figure from a Three View", BULL. JSME-- 16:216-225 (Feb. '73).
• LAFU76: Gilles Lafue, Recognition of three-dimensional objects from orthographic views, Proceedings of the 3rd annual conference on Computer graphics and interactive techniques, p.103-108, July 14-16, 1976, Philadelphia, Pennsylvania
• MARK80: Markowski, G. and M. A. Wesley, "Fleshing Out Wire Frames", IBM JOURNAL OF RESEARCH AND DEVELOPMENT -- 24(5):582-597 (Sept. '80).
• PATO69: Keith Paton, An algorithm for finding a fundamental set of cycles of a graph, Communications of the ACM, v.12 n.9, p.514-518, Sept. 1969 [doi>10.1145/363219.363232]
• TARJ71: Tarjan, R., "An Efficient Planarity Algorithm", Computer Science Department, Report No. CS-244-71, Stanford University, November 1971.

INDEX TERMS

Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Digitizing and scanning; Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms