Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1996-07-17
2001-10-16
Field, Joseph H (Department: 2176)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S441000, C345S443000
Reexamination Certificate
active
06304270
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates in general to computers, and more particularly to a method and apparatus for detecting simple convex polygons.
BACKGROUND OF THE INVENTION
The speed at which a personal computer operates is dependent upon a number of factors. Naturally, the speed of the microprocessor has a significant influence on the speed of operation of the overall computer system. Next to processor speed, in many cases, the video graphics subsystem has the most influence on the performance of the overall computer system. This is particularly true when a graphical user interface, such as MICROSOFT WINDOWS (by Microsoft Corporation of Redmond, Wash.) is used. In order to boost performance, most modem day personal computers use either a local video bus (which has a higher data bandwidth than the main peripheral bus) and an accelerated video card which increases the speed of certain operations. An accelerated video card allows the video card to perform selected video operations at high speed, rather than using the CPU to perform the operation. Hardware acceleration improves the operation of the computer system in two ways: (1) the CPU no longer needs to perform low-level video operations handled by the video card and (2) the data bandwidth for certain operations is greatly reduced, resulting in less bus traffic.
In order for acceleration to increase the responsiveness of the system, the operating environment, such as WINDOWS, must know the capabilities of the accelerated video subsystem. When the operating environment is loaded, it initiates the loading of a video driver, which is a program which acts as an intermediary between the operating environment and accelerated video hardware. The driver passes parameters to the operating environment which specify the accelerated capabilities of the video subsystem. Thereafter, when the operating environment needs to perform a video operation which could benefit from one of the accelerated capabilities, it passes the necessary data to the driver. The driver interprets the information from the operating environment, processes the information and passes data via the bus to the video subsystem. The video subsystem then performs the video operation by writing data to its frame buffer. As the market for accelerated video subsystems has matured, it has become apparent that the speed of the video subsystem is in large part dependent upon the operation of the video driver.
One class of driver functions (or “primitive”) which can have a significant affect on the overall speed of the driver involves the polygon functions. WINDOWS supports two polygon primitives: Alternate Fill Polygon( ) and Winding Fill Polygon( ). These primitives are used to draw solid and outline polygon figures. In support of the primitive call, WINDOWS passes information relating to the desired polygon, such as (1) an ordered list of vertices in screen coordinates (the last coordinate may be omitted; if so, the first coordinate is assumed to be the last coordinate as well), pattern information, color information and border information. Based on this information the driver draws the polygon. The speed at which the driver can draw the polygon is dependent upon the efficiency of the code and whether the video board provides hardware support.
In certain instances, it would be beneficial to know if the polygon is convex, and if so, whether the polygon is simple convex.
FIG. 1
a
illustrates a simple convex polygon
10
(defined by vertices
11
and edges
13
) and
FIG. 1
b
illustrates a complex convex polygon
12
. A simple convex polygon has no intersecting lines, and therefore, a video driver primitive may be able to take advantage of simpler code in performing functions relating to the polygon, such as using a Cohen-Sutherland clipping method for clipping a polygon which is partially outside of a window. Further, certain hardware acceleration features may by exploited by the driver software in instances where the polygon is simple convex.
A method of determining whether a polygon is convex is described in “Procedural Elements for Computer Graphics” by David F. Rogers, pages 146-151 (McGraw-Hill 1985). This text provides two methods for determining if a polygon is convex. However, the first method (computing and comparing the cross products of adjacent edges of the polygon) does not accurately identify the distinction between simple and complex convex polygons. A second method described in the reference cited above, involves repeatedly translating the polygon such that the ith vertex is positioned on an origin and rotating the polygon about the origin to place the (i+1)th vertex is on the positive x-axis. After the rotation, the sign of the y component of the (i+2)th vertex is noted. This procedure is repeated for each vertex. While the translation steps can be done at high speed, the rotation steps are time consuming due to sine and cosine computations. Thus, while this second method can correctly identify the distinction between simple and complex convex polygons, the slowness of the method when implemented in the driver software makes it undesirable.
Therefore, a need has arisen in the industry for a method and apparatus for determining whether a polygon is a simple convex polygon.
SUMMARY OF THE INVENTION
In the present invention, the driver software distinguishing between simple and complex convex polygons in a computer to determine whether a requested operation can be executed at a faster speed. To determine whether a polygon is simple or complex convex the video driver, after receiving information on the vertices of the polygon, determines whether the polygon is convex. If so, a starting vertex is selected and the number of direction changes relative to a predetermined coordinate axis which result from tracing the polygon are determined. The number of direction changes are compared to a threshold number. If the number of direction changes exceed the threshold number, then the polygon is complex convex.
The present invention provides significant advantages over the prior art. First, the method can determine whether a polygon is simple or complex convex with little overhead with regard to either speed or code complexity. By quickly determining whether or not the polygon is simple convex, the driver can invoke certain techniques to speed operations which are not available to complex convex polygons.
REFERENCES:
patent: 4899294 (1990-02-01), Easton et al.
patent: 4901251 (1990-02-01), Sfarti
patent: 4951230 (1990-08-01), Dalrymple et al.
patent: 4962468 (1990-10-01), Beauregard
patent: 0323558A2 (1989-07-01), None
patent: 0487060A2 (1992-05-01), None
patent: 0511835A2 (1992-11-01), None
Miller et al., “Mesh Computer Algorithms for Computational Geometry”,IEEE Transactions on Computers, vol. 38, No. 3, Mar. 1989, pp 321-340.*
Jeong et al., “An Optimal Parallel Algorithm for Finding the Smallest Enclosing Rectangle on a Mesh-connected Computer”,Parallel Processing, 1992 Symposium, 1992, pp. 138-141.*
DePano et al., “Minimum Enclosing Rectangles: A Comparative Investigation of Two Optimizing Criteria (Reprise)”,Southeastcon, 1991, IEEE Conference Proceedings, 1991, pp. 60-64.*
Liou et al., “Minimum Rectangle Partition Problem for Simple Rectilinear Polygons”, IEEE Transactions on Computer-aided Design of Integ. Circuit, vol. 9, No. 7, pp 720-733.*
“Efficient fracturing of all angle shaped VLSI mask pattern data”, Pelz et al., VLSI Journal 10, (1991) Jan., No. 2, Amsterdam, NL, pp. 143-154.
Danielson Brian H.
Dyches David A.
Compaq Computer Corporation
Field Joseph H
Sharp Comfort & Merrett P.C.
LandOfFree
Method and apparatus for determining simple convex polygons does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining simple convex polygons, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining simple convex polygons will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2606337