Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Patent
1990-05-09
1998-01-20
Fetting, Anton W.
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
345443, G06T 1140
Patent
active
057105782
ABSTRACT:
Two polygon fill algorithms are presented for filling polygons on a graphics display. The first polygon fill algorithm fills polygons that are strictly convex. The second polygon fill algorithm fills a larger class of polygons than the first polygon fill algorithm which includes polygons being concave in the x direction, and polygons having crossing lines. The first polygon fill algorithm tests the polygon for strict convexity by testing for a consistent turning direction, and by testing for once around in the y direction. The first polygon fill algorithm then stores the maximum and minimum value of the pel selected by the Bresenham algorithm for each scan line of the polygon. The fill line is drawn from the pel having the minimum value to the pel having the maximum value for each scan line of the polygon. The second polygon fill algorithm tests the polygon to ensure that it can be filled with one unique fill line for each scan line of the polygon. The second polygon fill algorithm stores both a minimum value and maximum value for each scan line of the polygon for each line of the polygon. A fill line is then drawn from the least minimum value to the greatest maximum value for each scan line of the polygon.
REFERENCES:
patent: 4481594 (1984-11-01), Staggs et al.
patent: 4646262 (1987-02-01), Smith
patent: 4667306 (1987-05-01), Smith
patent: 4677573 (1987-06-01), Brown et al.
patent: 4805116 (1989-02-01), Liang et al.
patent: 4808986 (1989-02-01), Mansfield et al.
patent: 4914729 (1990-04-01), Omori et al.
Liang, B.C.C.; Method to Determine the Convexity of Polygons, IBM TDB vol. 28, No. 5, Oct., 1985, pp. 2203-2208.
J. Simons & J. Gonzalez; Polygon Filling in Graphics Display System, IBM TDB vol. 24, No. 1A, Jun. 1981, pp. 235-236.
S. Boinodiris; Flag-Mapped Area Fill Algorithm; IBM TDB, vol. 29, No. 4, Sep., 1986, pp. 1441-1446.
Shinde, Yogesh N.; Mudur, S. P.; Algorithms for Handling the Fill Area Primitive of GKS; Computer Graphics Forum 5 (1986), pp. 105-117.
Chlamtac, Merav; Harary, Itzchak; The Shift X Parity Watch Algorithm for Raster Scan Displays; IEEE Transactions of Computers, vol. C-34, No. 7, Jul., 1985, pp. 666-673.
Foley, J. D.; Van Dam, A.; Fundamentals of Interactive Computer Grpahics; Addison-Wesley, 1982; pp. 456-460.
W. D. Little & R. Heuft; An Area Shading Graphics Display System, IEEE Transactions on Computers, vol. C-28, No. 7, Jul., 1979, pp. 528-531.
S. A. Dudani; Region Extraction Using Boudary Following, Pattern Recognition and Artificial Intelligence, Academic Press, 1976, pp. 216-232.
B. D. Ackland; The Edge Flag Algorithm-Fill Method for Raster Scan Displays, IEEE Transactions on Computers, Jan., 1981, pp. 41-47.
J. H. Potts, et al; The Decompostion of an Arbitrary Three-Dimensional Planar Polygon into a Set of Convex Polygons, Naval Postgraduate School Feb., 1987, pp. 1-76.
B. Kelleher, "MIPOLYCON", Digital Equipment Corporation and the Massachusetts Institute of Technology, Copyright 1987, 5 pages.
Beauregard Gary Michael
Loucks Larry Keith
Nguyen Khoa Dang
Urquhart Robert John
Dawkins Marilyn Smith
Fetting Anton W.
International Business Machines - Corporation
LandOfFree
Computer program product for utilizing fast polygon fill routine does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer program product for utilizing fast polygon fill routine, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer program product for utilizing fast polygon fill routine will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-729006