FILLING GAPS IN THE BOUNDARY OF A POLYHEDRON

被引：127

作者：

BAREQUET, G ^{[1
]}

SHARIR, M ^{[1
]}

机构：

[1] NYU,COURANT INST MATH SCI,NEW YORK,NY 10012

来源：

COMPUTER AIDED GEOMETRIC DESIGN | 1995年 / 12卷 / 02期

基金：

美国国家科学基金会;

关键词：

CAD; POLYHEDRA; GAP FILLING; CURVE MATCHING; GEOMETRIC HASHING; TRIANGULATION;

D O I：

10.1016/0167-8396(94)00011-G

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In this paper 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.

引用

页码：207 / 229

页数：23

共 31 条

[1] [Anonymous], 1983, DATA STRUCTURES NETW, DOI DOI 10.1137/1.9781611970265
[2] BAREQUET G, 1993, 27593 TEL AV U DEP C
[3] Bohn JH, 1992, P SOL FREEF FABR S 1, P86
[4] A FUNCTIONAL-APPROACH TO DATA-STRUCTURES AND ITS USE IN MULTIDIMENSIONAL SEARCHING
CHAZELLE, B
[J]. SIAM JOURNAL ON COMPUTING, 1988, 17 (03) : 427 - 462
[5] CHRISTIANSEN HN, 1978, COMPUT GRAPH, V13, P187
[6] DOLENC A, 1991, IN PRESS MATH SURFAC, V4
[7] Foley JD, 1984, FUNDAMENTALS INTERAC
[8] AN IMPROVED EQUIVALENCE ALGORITHM
GALLER, BA
FISHER, MJ
[J]. COMMUNICATIONS OF THE ACM, 1964, 7 (05) : 301 - 303
[9] GANAPATHY S, 1982, COMPUT GRAPHICS ACM, V16, P69
[10] Garey M.R., 1979, COMPUTERS INTRACTABI, V174

← 1 2 3 4 →