Filling gaps in the boundary of a polyhedron

non-geometric setting), we instead just check for consistency. As a DFS in a graph, it requires only O(m) time. If the collection of match suggestions is not consistent, we invoke the heuristic described in Section 5.3, that takes O(m logm + m (m; c)) time3, which is negligible. Stitching the borders, as merging sorted lists, is linear in their sizes. Thus, the required time for all these operations is, again, O(n). Finding the remaining holes is now done in O(k + n) time, since this is the size of the new version of the object. The triangulation of each hole is done in time cubic in its size. So the triangulation of all the holes requires O(Phi=1 `3i ) time. Since Phi=1 `i n, it follows from the averages inequality thatPhi=1 `3i n3=h2. In the worst case, where there is a hole whose complexity is proportional to that of the whole input, this term is O(n3). Nevertheless, these cases are very unlikely in practice. Usually, the number of holes is linear in the number of surfaces (and hence borders), and their size is very small. The size of a hole is usually bounded by some constant (especially with a proper choice of the proximity parameters that control the voting process), so this step, although it is asymptotically ine cient, does not require more than O(n) time in practice. To conclude, the whole algorithm runs on practical instances in average O(k + n) time, which is optimal. If we also count the connectivity computation in the preprocessing, the algorithm runs in expected O(k log k+n) time. In unrealistic cases, where the hole(s) are as complex as the polyhedral boundary itself, the running time may climb to as high as O(k + n3) (or to O(k log k + n3), when we also compute the connectivity). The following section describes our rather comprehensive experimentation with the algorithm. In all cases that we tried, the running time was indeed small, and the cost of the (theoretically expensive) hole-stitching step was invariably negligible. 8 Experimental Results We have implemented the whole algorithm on a Digital DECstation 5000/240 and on a Sun SparcStation II in C. We have experimented with dozens of CAD les whose boundaries contained gaps, and obtained excellent results in most of the cases. These CAD les were generated by various CAD systems, such as Euclid-IS (vendor: Matra Datavision), Unigraphics (McDonnell Douglas), Catia (IBM/Dassot), CADDS-4X (Computer Vision), ME (Hewlett Packard), Pro-Engineer (Parametric Technologies), and many others. We note that most of the problems occurred when stand-alone computer programs translated curved objects from neutral le format, e.g. VDAFS [VDA '87] or IGES [NIST '91], into their polyhedral approximations. Fewer problems appeared when the CAD systems performed the same task, using a built-in function which converts the internal data into an output le which contains a polyhedron description. The les described industrial models, primarily parts and subunits of the 3 (m;n) is an extremely slowly growing functional inverse of Ackermann's function. For all practical values of m and n, (m;n) does not exceed a very small constant; cf. . 17 automotive industry, which were extracted from CAD systems for the fabrication of three dimensional prototypes. Most of the models were speci ed in the STL [3DS '88] le format, which is the de-facto standard in the rapid prototyping industry. The tuning of the parameters was very robust, and large parameter ranges produced nearly identical results. We usually used 0.1 mm as the discretization parameter, and 0.5 mm for the voting threshold " (for models whose global size was between 2 to 20 cm in all dimensions). We allowed up to two successive point mismatches along a match. A point-to-point match contributed the amount of 1=(d+ 0:1) to the match score, where d was the distance between the two points. We considered only match suggestions which received more than 10 votes and whose scores were above 25:0. F was taken to be 0:85A+0:05P +0:10R, where A was the area of the triangle, P was its perimeter, and R was the ratio between the largest and the smallest of its three edges. All these parameters were user de ned, but modifying them did not achieve any better results. Therefore, the program set these defaults for the parameters, except for the voting threshold ". As noted above, this should be the user estimation of the physical size of the gaps between the original surfaces. Although there was a large enough range of valid " settings, the algorithm failed more often if this parameter was chosen improperly. A too small " resulted in the loss of matches due to the lack of votes. On the other hand, a too large " resulted in a noisy voting table. This usually caused \intuitive" matches not to have scores su ciently larger than incorrect match suggestions. Even when such intuitive matches were identi ed, they overlapped with erroneous match suggestions and were therefore eliminated. In all cases, too many unmatched border portions were passed to the triangulation step. When the remaining holes were not local (with respect to the geometric features of the original model), their triangulations constructed new surfaces far beyond the intention of the model designer. ) shows a synthetic example of an object similar to a cube, whose boundary was broken into eight components, none of which is planar. ) shows the same object in a wire-frame representation. Figures 5(c,d) show the object after the whole repairing process. Figures 5(e,f,g,h) show the di erent steps of the algorithm. The borders are shown in (e), the matches (after stitching the borders) are shown in (f), the remaining holes are shown (with the same perspective view) in (g), and their minimal area triangulations are shown in (h). ) shows another synthetic example, where a sphere contains very small holes in the poles. Figures 6(b,c) show one of the poles, before and after triangulating the hole, respectively. Real examples turned out to be simpler, since the matching borders were much longer and closer than in the synthetic examples. Many polyhedral approximations of surface-modeling objects were repaired using the algorithm described in this paper. A typical example (a hollowed trimmed box) is shown in Figure 7. The front side of the object is shown in Figure 7(a), whereas its bottom side is shown in Figure 7(b). 18 (a) (b) (c) (d) (e) (f) (g) (h)  A synthetic example (a) (b) (c)  A sphere with perforated poles 19 (a) (b) (c) (d) (e) (f) (g)  A real example 20 (a) (b)  Three intersecting \drums" The borders are shown in Figure 7(c), and all of them are matched, leaving only six holes. Since the holes are so small, they appear as dots in this scale. Figures 7(d,e) are closeups of the area near the left intersection of the two pairs of circular borders (as seen in (c)), before and after stitching, respectively. Figures 7(f,g) are closeups of a hole before and after its minimum-area triangulation. Figures 8 and 9 show two more real cases.  shows two intersecting \drums", where a third part protrudes out of the near drum. Figure 8(b) is a closeup of two tiled matches (from a di erent point of view), in a wire-frame representation. ) shows a complex of ve open hollowed cylinders. One long gap separates between the inner and outer surfaces of the complex. Two portions of the single border, that completely bounds this gap, were fully matched and tiled. Figure 9(b,c) are closeups of the tiled match. Figure 10 shows three more real examples which our algorithm fully cured. We summarize the performance of our implementation on all the examples described above in Table 1. All the time measurements were taken on a Digital DECstation 5000/240. 9  We have proposed in this paper an algorithm for solving a practical problem, namely the detection and repair of gaps in the boundary of a polyhedron. This problem arises quite frequently in practice, during the computation of polyhedral approximations of CAD models, whose boundaries are described using curved entities of higher levels. We applied several techniques in our solution. First, we used a partial curve matching technique, adapted from computer vision, for identifying matching border 21 (a) (b) (c)  A complex of ve open hollowed cylinders 22 (a) Impeller (b) Drawer (c) Adapter  Three more real examples 23 Complexity Border Hole Model Vertices Edges Facets Borders Points Matches Holes Points Synthetic 45 111 37 8 278 18 12 61 Sphere 432 2,448 816 2 48 0 2 48 Box 1,545 3,244 609 32 5,305 30 6 47 Drums 826 1,712 372 19 3,106 35 22 233 Cylinders 1,571 3,132 783 1 1,592 1 0 0 Impeller 7,284 43,635 14,545 11 47 0 11 47 Drawer 458 2,817 939 1 203 1 0 0 Adapter 6,539 44,682 14,894 27 84 0 27 84 Time (Seconds) Model Stitching Triangulation Total Synthetic 0.48 0.20 0.68 Sphere 0.13 0.06 0.19 Box 10.14 0.60 10.74 Drums 5.95 0.20 6.15 Cylinders 3.60 0.00 3.60 Impeller 1.12 0.35 1.47 Drawer 0.24 0.00 0.24 Adapter 2.48 0.06 2.54 Table 1: Performance of the algorithm 24 portions. Then, we chose a (nearly) maximal consistent set of match candidates, and stitched them together. Finally, we identi ed the remaining holes and employed a minimum area triangulation of 3-D polygons in order to ll them. This method can be applied to other geometric problems, where portions of 3dimensional polygonal curves should be matched. In a companion paper [Barequet & Sharir '93], we are presently investigating the extension of our research to the problem of piecewise linear interpolation between parallel polygonal slices. Acknowledgment The authors wish to thank Haim Wolfson for useful discussions concerning the geometric hashing technique and its applications. The rst author would also like to thank Cubital Ltd. for contributing data les.