Curve contour smoothing

• US 6,483,509 B1
• Filed: 04/09/1999
• Issued: 11/19/2002
• Est. Priority Date: 04/09/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rabenhorst, David Alan
• Primary Examiner(s): BRIER, JEFFERY A
• Application Number:
  US09/288,585
• Time in Patent Office: 1,320 Days
• Field of Search: 345/442, 345/611, 345/156, 345/856, 345/858, 382/242
• US Class Current: 345/442
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

A system and method for dramatically reducing the number of vertices defining a polygon on a grid, without significantly changing its effective enclosed area is disclosed. A smoothing process is executed on any general purpose computer system to operate on one or more representations of one or more curves. 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 being sequential 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, new vertices are selected along the curve and the process is repeated. 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 before a new set of vertices is selected. The reduced set of only the important vertices needed may effectively substitute for the complete set when processing the vertices and/or when rendering the curve. This is repeated along the curve until a stop criteria is reached.

Claims

1. A computer system having one or more central process units, one or more memories, and one or more graphical user interfaces, the system further comprising:

a representation of one or more curves in one or more of the memories, each of the curves being represented by a set of vertices;

a smoothing process for reducing memory needed for smoothed said curves, said smoothing process comprising the steps of;

a. selecting from a vertex set representing an unsmoothed curve, a first vertex, a third vertex, and a second middle vertex, the first, second middle, and third vertices being on a sequence of traversal of the curve;

b. determining the area of a triangle formed by the first, second, and third vertices;

c. comparing the area to a threshold;

d. discarding the second middle vertex if the area is less than the threshold, and selecting a next vertex as the third vertex, and redetermining a new second middle vertex;

e. marking the second middle vertex as an important vertex if the area of the triangle is greater than or equal to the threshold, and replacing the first vertex with the second middle vertex, the third vertex with the next vertex, and redetermining a new second middle vertex;

f. repeating steps b through e until a stop criteria is reached; and

g. replacing in memory said vertex set for said unsmoothed curve with a set of important vertices for a smoothed said curve.

2. A system, as in claim 1, where the vertices are determined from outputs of a positional input device.

3. A system, as in claim 2, where the positional input device is any one or more of the following:

a mouse, a pointer key, a track ball, a pen input, and a track point.

4. A system, as in claim 1, where the stop criteria is any one or more of the following:

receiving a controlling event, reaching a last vertex on the curve, returning to the initial vertex, processing a given number of vertices, and the passing of a time period.

5. A system, as in claim 1, where the important vertices are used to represent the curve in one or more application programs.

6. A system, as in claim 1, that further comprises a network interface that connects to one or more networks.

7. A system, as in claim 6, where the important vertices represent the curve and are communicated through the network interface over one or more of the networks.

8. A system, as in claim 7, where duplex information about one or more of the important vertices is received from the network through the network interface.

9. A system, as in claim 1, where the next vertex is consecutive in the sequence of traversal of the curve.

10. A system, as in claim 1, where the next vertex is not consecutive in the sequence of traversal of the curve.

11. A computer system as in claim 1 wherein at least one curve is a closed curve represented by a polygon, a selected area object enclosed by said closed curve being substantially enclosed by a smoothed said closed curve, whereby complexity of calculation for determining whether said objects are enclosed by said smoothed closed curve is substantially reduced from said closed curve.

12. A computer system as in claim 11 wherein vertices in said vertex set are generated in real time as said closed curve is drawn on a scene displayed on a client display.

13. A smoothing process for smoothing a curve represented as a set of vertices, a smoothed said curve being represented by a subset of said set of vertices, said smoothing process comprising the steps of:

a. selecting a first vertex, a third vertex, and a second middle vertex from a vertex set representing a curve, the first, second middle, and third vertices being on a sequence of traversal of the curve;

b. determining the area of a triangle formed by the first, second middle, and third vertices;

c. comparing the area to a threshold;

d. discarding the second middle vertex if the area is less than the threshold, selecting a next vertex as the third vertex, and redetermining a new second middle vertex;

e. marking the second middle vertex as an important vertex if the area of the triangle is greater than or equal to the threshold, and replacing the first vertex with the second middle vertex, the third vertex with the next vertex, and redetermining a new second middle vertex; and

f. repeating steps b through e until a stop criteria is reached; and

g. providing a set of important vertices representing a smoothed said curve.

14. A smoothing process as in claim 13 wherein at least one curve is a closed curve represented by a polygon, a selected area object enclosed by said closed curve being substantially enclosed by a smoothed said closed curve, whereby complexity of calculation for determining whether said objects are enclosed by said smoothed closed curve is substantially reduced from said closed curve.

15. A smoothing process as in claim 14 wherein vertices in said vertex set are generated in real time as said closed curve is drawn on a scene displayed on a client display.

16. A system for smoothing curves each represented as a vertex set, said system comprising:

means for selecting from a vertex set a first vertex, a third vertex, and a second middle vertex, the first, second, and third vertices being on a sequence of traversal of the curve;

means for determining whether the area of a triangle formed by the first, second middle, and third vertices is less than a threshold;

means for discarding the second middle vertex if the area is less than the threshold, a next vertex being selected as the third vertex, and a new second middle vertex being determined;

means for marking the second middle vertex as an important vertex if the area of the triangle is greater than or equal to the threshold, the first vertex being replaced with the second middle vertex, the third vertex being replaced with the next consecutive vertex, and a new second middle vertex being determined; and

means for replacing said vertex set with an important vertex set representative of a smoothed said curve.

17. A system as in claim 16 wherein at least one curve is a closed curve represented by a polygon, a selected area object enclosed by said closed curve being substantially enclosed by a smoothed said closed curve, whereby complexity of calculation for determining whether said objects are enclosed by said smoothed closed curve is substantially reduced from said closed curve.

18. A system as in claim 17 wherein vertices in said vertex set are generated in real time as said closed curve is drawn on a scene displayed on a client display.

19. A computer program product that performs the steps of:

a) receiving a vertex set representative of an unsmoothed curve;

b) selecting from said vertex set a first vertex, a third vertex, and a second middle vertex, the first, second middle, and third vertices being on a sequence of traversal of the curve;

c) determining whether the area of a triangle formed by the first, second middle, and third vertices is less than a threshold;

d) discarding the second vertex if the area is less than the threshold, and selecting a next vertex as the third vertex, and redetermining a new second middle vertex;

e) marking the second middle vertex as an important vertex if the area of the triangle is greater than or equal to the threshold, and replacing the first vertex with the second vertex, the third vertex with the next vertex, and redetermining a new second middle vertex;

f) repeating steps c through e until a stop criteria is reached; and

g) providing an important vertex set representative of a smooth said curve.

20. A computer program product as in claim 19 wherein at least one curve is a closed curve represented by a polygon, a selected area object enclosed by said closed curve being substantially enclosed by a smoothed said closed curve, whereby complexity of calculation for determining whether said objects are enclosed by said smoothed closed curve is substantially reduced from said closed curve.

21. A computer program product as in claim 20 wherein vertices in said vertex set are generated in real time as said closed curve is drawn on a scene displayed on a client display.