Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
2001-11-30
2003-11-25
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06654016
ABSTRACT:
TECHNICAL FIELD
The present invention is generally directed to a software module used for drawing diagrams. More specifically, the present invention provides a system and method for efficiently creating splines by eliminating unnecessary control points.
BACKGROUND OF THE INVENTION
Computer software modules that enable users to produce drawings are widely available. These drawing software modules typically have functions that allow users to place and manipulate shapes and lines on a display screen to create a variety of drawings including pictures, charts, diagrams, and figures. After producing the drawings with the software module, users can store the drawings electronically, transmit them electronically, or print hard copies of the drawings.
One common use for drawing software modules is to create diagrams and flowcharts that represent structures and processes. The diagrams and flowcharts often consist of objects of varying shapes that represent elements of a structure or steps in a process. The objects can be placed on the electronic “page” either automatically by a function within the software module or they can be “drawn” by a user with a pointing device such as a mouse. The objects on the electronic page can then be connected in a variety of ways to show how they are inter-related. Traditionally, objects could be connected using a single, straight line or multiple, orthogonal line segments. The advantage of orthogonal line segments is that the paths of the connections could connect two objects while avoiding unwanted intersections with other objects on the page.
More recently, some commercially available drawing software modules enabled objects to be connected with curves or splines. A spline is generally defined as a smooth curve that actually or approximately connects a set of points, although it may not intersect all of the points. Typically, Bezier splines are used by drawing software modules to draw curves connecting shapes on an electronic page. A Bezier spline is a well-known type of curve generally defined by four points, often referred to as the control points, and a set of polynomial equations. The drawing software module creates the spline using the coordinates of the control points and the set of polynomial equations.
Although drawing software modules have the ability to draw splines, there are several limitations concerning the accuracy and precision with which the splines are placed on an electronic document. The primary method for improving the accuracy and precision of placing splines is to increase the number of control points that define the spline. That is, additional control points can assist in the “fine tuning” of a spline's position. Although an increased number of control points allows for more refined manipulation of the spline, it also increases the number of calculations needed to create the spline. Increasing the calculations used in creating the spline slows the processing speed and detracts from the overall performance of the drawing software module.
In view of the foregoing, there is a need in the art for a method that will enable drawing software modules to efficiently create splines. Specifically, a need exists to be able to differentiate between control points that fine tune the spline and those that are redundant. Redundant control points have little or no effect on the position of the spline. A further need exists to isolate the redundant points so that they will not be used in the calculations performed to create the spline. Reducing unneeded control points supports more efficient processing.
SUMMARY OF THE INVENTION
The present invention is generally directed to a software module for placing splines in an electronic diagram. The present invention improves upon existing drawing software modules by eliminating unnecessary control points before drawing or modifying the spline. Specifically, the exemplary embodiment described herein uses two methods to identify unneeded points. One method identifies newly added control points that are useless and have no effect on the spline. The other method locates pre-existing control points that have been replaced by newer control points and are no longer needed. Once redundant control points are identified and isolated, the spline can be created using only the necessary control points. By excluding unnecessary control points, the calculations for creating the spline are reduced and the drawing software module can operate more efficiently.
In one aspect, the invention comprises a computer-implemented method for efficiently creating a spline. Beginning with a source object and target object connected by orthogonal line segments, the drawing software module can place control points that define the position of a proposed spline. The position of the proposed spline can be modified for a more complex or precise path by adding control points along the line segments. Typically, control points are continually added on a heuristic basis until the spline traces the desired path. Added control points can be examined in conjunction with adjacent control points to determine whether they affect the position of the spline. If an added point does not affect the spline, it can be designated useless and isolated from the calculations of the position of the revised spline. Similarly, existing control points that are replaced by newly added control points can be identified and isolated from the calculation of the revised spline. Once the useless and replaced control points are isolated, the revised spline is created using only relevant control points. Reducing the number of control points improves the performance of the drawing software module.
In another aspect, the invention comprises an efficient method for the filtering of useless control points in order to increase the processing speed for placing the spline. A drawing software module can place initial control points that define a spline along a line segment on an electronic page. When additional control points are added to the initial control points to modify the path of the spline, the resulting group of control points can contain redundancies. The adding of points can result in an excess of points that unnecessarily slows the calculation of the ultimate spline. The drawing software module can analyze newly added control points to determine whether they have little or no effect on the position of the spline. Useless control points can be filtered out of the group of control points used to create the spline.
The invention further provides an efficient method for creating a spline by filtering out replaced control points from those used to calculate the position of the spline. The spline can be created adjacent to a line segment on which control points are placed. As new control points are added to the line segment to adjust the position of the spline, the initial control points can be analyzed to determine whether they have been replaced. Replaced control points can be filtered out of the calculation of the revised spline. The filtering process reduces the number of calculations that must be performed and enables the drawing software module to calculate the position of the revised spline more quickly.
REFERENCES:
patent: 4953106 (1990-08-01), Gansner et al.
patent: 5594855 (1997-01-01), Von Her, II et al.
patent: 6278445 (2001-08-01), Tanaka et al.
patent: 6483509 (2002-11-01), Rabenhorst
King & Spalding LLP
Luu Matthew
Microsoft Corporation
LandOfFree
System and method for efficiently creating splines does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for efficiently creating splines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for efficiently creating splines will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3166885