A POLYGONAL APPROACH TO HIDDEN-LINE AND HIDDEN-SURFACE ELIMINATION

被引：21

作者：

GOODRICH, MT

机构：

[1] Department of Computer Science, Johns Hopkins University, Baltimore

来源：

CVGIP-GRAPHICAL MODELS AND IMAGE PROCESSING | 1992年 / 54卷 / 01期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/1049-9652(92)90029-W

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present algorithms for the well-known hidden-line and hidden-surface elimination problems. Our algorithms are optimal in the worst case, and are also able to take advantage of problem instances that are "simpler" than in the worst case. Specifically, our algorithms run in O(n log n + k + t) time, where n is the number of edges, and k (resp. t) is the number of intersecting pairs of line segments (resp. polygons) in the projection plane π. Our algorithms are based on a polygon-based strategy, rather than an edge-based strategy, and are quite simple. © 1992.

引用

页码：1 / 12

页数：12

共 32 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2]

[Anonymous], 1983, DATA STRUCTURES NETW, DOI DOI 10.1137/1.9781611970265

[3]

Baumgart BG, 1975, AFIPS P, P589, DOI DOI 10.1145/1499949.1500071

[4]

BENTLEY JL, 1979, IEEE T COMPUT, V28, P643, DOI 10.1109/TC.1979.1675432

[5]

BENTLEY JL, 1980, IEEE T COMPUT, V29, P571, DOI 10.1109/TC.1980.1675628

[6] HIDDEN SURFACE REMOVAL FOR RECTANGLES [J].

BERN, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1990, 40 (01) :49-69

[7]

Chazelle B., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P590, DOI 10.1109/SFCS.1988.21975

[8]

CLARKSON, 1988, 4TH P ANN S COMP GEO, P1

[9]

DEBERG M, 1990, RUUCS9021 UTR U DEP

[10]

DEVAI F, 1986, 2ND P ACM S COMP GEO, V2, P269

← 1 2 3 4 →