Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-10-07
2001-08-07
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S440000, C345S443000, C345S111000
Reexamination Certificate
active
06271862
ABSTRACT:
I. BACKGROUND OF THE INVENTION
A. Field of the Invention
The present invention relates generally to clipping in a graphics system and in particular to an apparatus and method for determining line clipping intersection points.
B. Description of the Related Art
In certain computer graphics systems, the portion of a line extending beyond the display area must be clipped. For example, a computer graphics system may perform line clipping to determine which pixels are to be drawn in a window in a computer screen. Line clipping thus determines which lines to draw in the display window, and which portion of a line is to draw if the line is located partially within the display window. In conventional systems, line clipping and line drawing are low-level graphics operations, but calculations involved in clipping lines are complex and time-consuming.
For example, one conventional clipping technique compares each point of a line to the four sides of a display window before drawing the line. This seemingly simple technique requires four comparisons for every point on the line. If the line is much larger than the window, this technique can be extremely time-consuming.
Several conventional line clipping techniques determine the intersection points of a line and the display window. One technique involves intersecting a line with each of the four edges of a clipping rectangle to determine the intersection points on those edges. These, too, can involve a great deal of calculations. Other conventional line clipping techniques, such as the Cohen-Sutherland line clipping algorithm, the Cyrus-Beck technique, and a method of clipping a line by solving linear equations, require extensive multiplication and division operations and are therefore computation intensive and time-consuming. For example, an integer division instruction may take as many as 40 CPU cycles, and one integer multiplication instructions may take as many as 10 cycles on an Intel PENTIUM CPU. Furthermore, some of these techniques require floating point multiplication or division, which require even more computing resources.
II. SUMMARY OF THE INVENTION
Apparatus consistent with this invention for clipping a graphics element comprises means for comparing a graphics element with a graphics area to determine whether the graphics element and the graphics area overlap; means for determining the need for a clipping operation according to the determination whether the graphics element and graphics area overlap; means for categorizing the overlap between the graphics element and the graphics area if there is a need for clipping; and means for clipping the graphics element based on the categorization of the overlap.
The clipping technique consistent with the present invention uses add, subtract and compare operations, each of which only requires a single cycle on an Intel PENTIUM CPU
REFERENCES:
patent: 4623880 (1986-11-01), Bresenham et al.
patent: 4982345 (1991-01-01), Callahan et al.
patent: 5012433 (1991-04-01), Callahan et al.
patent: 5161212 (1992-11-01), Littleton
patent: 5359347 (1994-10-01), Kim et al.
patent: 5369741 (1994-11-01), Hartog et al.
patent: 5455897 (1995-10-01), Nicholl et al.
patent: 5491494 (1996-02-01), Cornett et al.
patent: 5522020 (1996-05-01), Narayanaswami
patent: 5553210 (1996-09-01), Narayanaswami
patent: 5559532 (1996-09-01), Gardyne
patent: 5594848 (1997-01-01), Dao
patent: 5598183 (1997-01-01), Robertson et al.
patent: 5668571 (1997-09-01), Pai et al.
patent: 5720019 (1998-02-01), Koss et al.
patent: 5745099 (1998-04-01), Blomqvist
patent: 6012072 (2000-01-01), Lucas et al.
Addison-Wesley, “Programmer's Guide to the EGA, VGA and Super VGA Cards”, 3rdEdition, 1994, pp. 153, 154, 554-557 and 732-733, Richard F. Ferraro.
Victor J. Duvanenko, W.E. Robbins, and Ronald S. Gyurcsik, “Improving Line segment clipping”, Dr. Dobb's Journal, Jul. 1990, p. 36.
Havan Thu-Thao
Luu Matthew
Seiko Epson Corporation
LandOfFree
Apparatus and method for determining line clipping... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for determining line clipping..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for determining line clipping... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2475403