Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1999-04-09
2002-11-19
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
C345S611000, C382S242000
Reexamination Certificate
active
06483509
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the area of computer graphical user interfaces (GUIs). More specifically, the invention relates to smoothing contours of curves and/or polygons as used by GUIs and/or as communicated over networks.
BACKGROUND OF THE INVENTION
A graphical user interface (GUI) is a computer program which uses pictures or images to represent its input and output. A user interacts with the software application by moving a pointer (typically controlled by a pointing device such as a mouse), and selecting objects while pointing to them. The objects are often buttons in windows containing buttons and pictures, but certain applications may support pointing at and selecting parts of pictures or objects in the pictures themselves (eg—painting).
When the selected object or picture part has a non-trivial, non-analytic shape, it may be defined by a closed curve. Closed curves as drawn on computer screens are actually many-sided polygons, where each vertex is a discrete pixel. The most general definition of a typical such closed curve may consist of enumerating all the pixels through which the curve passes. In order for a user of a GUI to select an arbitrary part of a picture or an arbitrary subset of things in the picture, the application may support drawing a closed curve with the pointing device around a portion of the picture. This may be called a “lasso” operation, and involves recording and processing all the pointer device movements generated by the operating system.
Problems with the Prior Art
When a closed curve is used by a GUI for a lasso operation, the list of vertices for the defining polygon are obtained from the operating system (OS) by “mouse movement” events. An operating system will generate a new mouse movement event whenever it detects the mouse moving even a tiny bit, whether or not that movement may actually be significant to the application. In general, such a list of vertices may be quite long, and the number of defining pixels for a such closed curve polygon may easily be in the hundreds, thousands, tens of thousands, or even more. The very large number of vertices required to define such a general polygon at this finest detail consumes storage space, computational power, and perhaps network bandwidth for a distributed software application.
Computationally, processing a long list of pixels could potentially be enormously slow and/or complicated. A software application's processing of a lasso operation may often involve an enumeration of all the objects in the picture, and making a decision for each about whether or not it is inside the lasso (and therefore selected), or outside the lasso (and therefore not selected). The computational complexity of such decisions is not only proportional to the number of objects in the picture for which the decision must be made, but may very well be proportional to the number of vertices defining the enclosing polygon or closed curve.
The real-time interactive processing of a distributed client/server software application is limited by the bandwidth of the computer network over which it must operate. Typical round-trip transmission times may be so slow as to normally preclude real-time iterative processing of all mouse movement events, and thus lasso type operations. “Rubber band” lines forming enclosing polygons on an image thus cannot currently be processed in real time over the network.
OBJECTS OF THE INVENTION
An object of this invention is an improved system and method for smoothing the contour of a curve and/or polygon by reducing the number of vertices in a piece-wise linear representation of the curve/polygon.
An object of this invention is an improved system and method for smoothing the contour of a curve and/or polygon by reducing the number of defining vertices in a piece-wise linear representation of the curve/polygon so that processing of the curve/polygon by an application is simplified and/or made practical.
An object of this invention is an improved system and method for smoothing the contour of a curve and/or polygon by reducing the number of defining vertices in a piece-wise linear representation of the curve/polygon so that communication of a representation of curve/polygon over a network is simplified and/or made practical.
SUMMARY OF THE INVENTION
This invention is a system and method for dramatically reducing the number of vertices defining a polygon on a grid, without significantly changing its effective enclosed area. Benefits include a possibly dramatic reduction of processing required by an application program to perform operations using the polygon and facilitation of storing and/or transmitting this polygon information, e.g. in real time over a network. A smoothing process is executed on any general purpose computer system, typically having one or more central process units, one or more memories, and one or more graphical user interfaces. Usually, the system will have one or more representations of one or more curves stored in one or more of the memories and/or other memories associated with the system (e.g. connected over a network). Each of the curves has a set of a plurality of vertices. The smoothing process first selects a first vertex, a third vertex, and a second middle vertex, the first, second, and third vertices are sequential in a traverse of the curve but not necessarily consecutive on the curve. Then the smoothing process determines the area of a triangle formed by the first, second, and third vertices. This triangular area is compared to a threshold area. If the area is less than the threshold, the second vertex is discarded, a next possibly consecutive vertex is selected as the third vertex, and a new second vertex is determined (in the middle). However if the area of the triangle is greater than or equal to the threshold, the second (middle) vertex is marked as an important vertex and the first vertex is replaced with the second vertex. The next vertex after the previous third vertex becomes the new third vertex, and a new second (middle) vertex is determined. These steps are repeated along the curve until a stop criteria is reached.
REFERENCES:
patent: 5500927 (1996-03-01), Sander-Cederlof et al.
patent: 5661502 (1997-08-01), Cheng
patent: 5668894 (1997-09-01), Hamano et al.
patent: 5933149 (1999-08-01), Mori et al.
Brier Jeffery
Herzberg Louis P.
International Business Machines Corp.
Percello Louis J.
Peterson, Jr. Charles W.
LandOfFree
Curve contour smoothing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Curve contour smoothing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Curve contour smoothing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2927247