Filling gaps in the boundary of a polyhedron. (English) Zbl 0875.68921
Summary: We present an algorithm for detecting and repairing defects in the boundary of a polyhedron. These defects, usually caused by problems in CAD software, consist of small gaps bounded by edges that are incident to only one polyhedron face. The algorithm uses a partial curve matching technique for matching parts of the defects, and an optimal triangulation of 3-D polygons for resolving the unmatched parts. It is also shown that finding a consistent set of partial curve matches with maximum score, a subproblem which is related to our repairing process, is NP-hard. Experimental results on several polyhedra are presented.
MSC:
| 68U07 | Computer science aspects of computer-aided design |
References:
| [1] | 3DS, Stereolithography Interface Specification, CA (1988), 3D Systems, Inc. |
| [2] | Barequet, G.; Sharir, M., Piecewise-linear interpolation between polygonal slices, (Technical Report 275/93 (1993), Department of Computer Science, Tel Aviv University) · Zbl 0859.68120 |
| [3] | Bøhn, J. H.; Wozny, M. J., Automatic CAD-model repair: Shell-closure, (Proc. Symp. on Solid Freeform Fabrication (1992), Dept. of Mech. Eng., Univ. of Texas at Austin), 86-94 |
| [4] | Chazelle, B., A functional approach to data structures and its use in multidimensional searching, SIAM J. Comput., 17, 427-462 (1988) · Zbl 0679.68074 |
| [5] | Christiansen, H. N.; Sederberg, T. W., Conversion of complex contour line definitions into polygonal element mosaics, Comput. Graph., 13, 187-192 (1978) |
| [6] | Dolenc, A.; Mäkelä, I., Optimized triangulation of parametric surfaces, (Technical Report TKO-B74 (1991), Helsinki University of Technology), to appear in Mathematics of Surfaces IV |
| [7] | Foley, J. D.; Van Dam, A., Fundamentals of Interactive Computer Graphics (1984), Addison-Wesley,: Addison-Wesley, Reading, MA |
| [8] | Galler, B. A.; Fischer, M. J., An improved equivalence algorithm, Comm. ACM, 7, 301-303 (1964) · Zbl 0129.10302 |
| [9] | Ganapathy, S.; Dennehy, T. G., A new general triangulation method for planar contours, ACM Trans. Comput. Graph., 16, 69-75 (1982) |
| [10] | Garey, M. R.; Johnson, D. S., Computers and Intractability, A Guide to the Theory of NP-Completeness (1979), Freeman,: Freeman, San Francisco · Zbl 0411.68039 |
| [11] | Guibas, L.; Stolfi, J., Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Trans. Graph., 4, 74-123 (1985) · Zbl 0586.68059 |
| [12] | Ho-Le, K., Finite element mesh generation methods: A review and classification, Computer-Aided Design, 20, 27-38 (1988) · Zbl 0661.65124 |
| [13] | Hong, J.; Wolfson, H. J., An improved model-based matching method using footprints, (Proc. 9th Internat. Conf. on Pattern Recognition (1988)), 72-78 |
| [14] | Kalvin, A.; Schonberg, E.; Schwartz, J. T.; Sharir, M., Two-dimensional, model-based, boundary matching using footprints, Internat. J. Robotics Res., 5, 38-55 (1986) |
| [15] | Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press,: Plenum Press, New York), 85-103 · Zbl 0366.68041 |
| [16] | Kishon, E.; Hastie, T.; Wolfson, H., 3-D curve matching using splines, J. Robotic Systems, 8, 723-743 (1991) |
| [17] | Klincsek, G. T., Minimal triangulations of polygonal domains, Ann. Discrete Math., 9, 121-123 (1980) · Zbl 0452.05002 |
| [18] | Mäkelä, I.; Dolenc, A., Some efficient procedures for correcting triangulated models, (Proc. Symp. on Solid Freeform Fabrication (1993), Dept. of Mech. Eng., Univ. of Texas at Austin) |
| [19] | Mehlhorn, K., Data Structures and Algorithms 3: Multi-Dimensional Searching and Computational Geometry (1984), Springer,: Springer, Berlin · Zbl 0556.68003 |
| [20] | NIST, National Institute of Standards and Technology, (The Initial Graphics Exchange Specification (IGES), Version 5.1, MD (1991)) |
| [21] | Pratt, W. K., Digital Image Processing (1978), Wiley,: Wiley, New York |
| [22] | Rock, S. J.; Wozny, M. J., Generating topological information from a “bucket of facets”, (Proc. Symp. on Solid Freeform Fabrication (1992), Dept. of Mech. Eng., Univ. of Texas at Austin), 86-94 |
| [23] | Samet, H.; Webber, R. E., Hierarchical data structures and algorithms for computer graphics; Part II: Applications, IEEE Comput. Graph. Appl., 8, 59-75 (1988) |
| [24] | Schwartz, J. T.; Sharir, M., Identification of partially obscured objects in two and three dimensions by matching noisy characteristic curves, Internat. J. Robotics Res., 6, 29-44 (1987) |
| [25] | Sheng, X.; Hirsch, B. E., Triangulation of trimmed surfaces in parametric space, Computer-Aided Design, 24, 437-444 (1992) · Zbl 0756.65168 |
| [26] | Sheng, X.; Tucholke, U., On triangulating surface model for SLA, (Proc. 2nd Internat. Conf. on Rapid Prototyping. Proc. 2nd Internat. Conf. on Rapid Prototyping, Dayton, OH (1991)), 236-239 |
| [27] | Snyder, W. E.; Groshong, R.; Hsiao, M.; Boone, K. L.; Hudacko, T., Closing gaps in edges and surfaces, Image and Vision Comput., 10, 523-531 (1992) |
| [28] | Tarjan, R. E., Data Structures and Network Algorithms (1983), SIAM,: SIAM, Philadelphia, PA · Zbl 0584.68077 |
| [29] | VDA, Verband der Automobilindustrie e.V., (VDA Surface Interface (1987)), Germany |
| [30] | Wolfson, H. J., On curve matching, IEEE Trans. Pattern Anal. Mach. Intel., 12, 483-489 (1990) |
| [31] | Yerry, M. A.; Shephard, M. S., A modified quadtree approach to finite element mesh generation, IEEE Comput. Graph. Appl., 3, 39-46 (1983) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
