Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
2001-11-30
2003-11-18
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06650328
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 placing curves within an electronic version of a drawing using refinement and obstacle avoidance techniques.
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 in the form 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.
Although drawing software modules have the ability to draw curves, there are several limitations concerning the accuracy and precision with which the curves are placed on an electronic document. First, the curves drawn by conventional drawing software modules do not have the ability to avoid other objects on the page. That is, when a curve is drawn connecting a source object and a target object, it also may undesirably intersect other objects on the page. The inability to draw curves that automatically avoid other objects on the page results in garbled and confusing drawings. Second, the curves drawn by conventional drawing software modules can fail to show details in the path of the orthogonal line segments. For instance, when a short line segment is adjacent to a relatively long line segment, the conventional curve follows the general path of the orthogonal line segments. However, important details of the orthogonal line segment path can be lost in the conventional generalized curve.
In view of the foregoing, there is a need in the art for a method that will support the precise and accurate placement of curved connectors in an electronic drawing. Specifically, a need exists to be able to create drawings and flowcharts with curves that avoid intersecting unintended objects. A further need exists to be able to refine curves used in drawings so that they accurately capture the drafters intent.
SUMMARY OF THE INVENTION
The present invention is generally directed to a software module for placing smooth splines in an electronic diagram. The present invention improves upon existing drawing software modules which draw splines that may be inaccurate or intersect other objects on the page. Specifically, the present invention uses an obstacle-avoidance function to draw smooth splines that connect a source object and a target object without intersecting other objects on the page. The present invention also employs a refinement function to ensure that details of a path, represented by relatively smaller line segments, are reflected in the spline that is ultimately displayed.
In one aspect, the invention comprises a method for creating a spline using the obstacle avoidance function. The method includes connecting a source object and a target object on a page with orthogonal line segments. The drawing software module places initial control points along the orthogonal line segments and uses these control points to create a proposed spline connecting the source and target objects. A user can decide which types of obstacles on the page the proposed spline should not intersect. If the proposed spline does not intersect any of the designated obstacles, it can be displayed as the final spline. If the proposed spline does intersect user-designated obstacles, additional control points can be added to the initial control points and the proposed spline can be redrawn. This process can be repeated until the proposed spline does not intersect any designated obstacles or until it approximates the original orthogonal line segments.
The invention further provides a method for creating an accurate spline that shows the inflection points of the path between two objects. A software module manipulating an electronic diagram can connect a source object and a target object with orthogonal line segments and place initial control points along the line segments. In order to prevent loss of inflection details in the spline provided by relatively smaller line segments, the software module can compare the lengths of contiguous pairs of line segments. If the ratio of the lengths of the line segments is greater than a predetermined value, a refinement control point can be added to the longer line segment to ensure that that spline accurately traces the path of the orthogonal line segments. Once the refinement control point is added, the spline is placed using both the initial control points and the refinement control point.
In yet another aspect, the invention provides a computer-implemented method for creating smooth, accurate splines that incorporate both the refinement and obstacle avoidance features previously discussed. Typically, the refinement function is implemented first, so that a more accurate proposed spline is placed on the diagram. Then the obstacle avoidance function can be implemented until a spline is created that does not intersect designated obstacles.
REFERENCES:
patent: 4953106 (1990-08-01), Gansner et al.
patent: 5594855 (1997-01-01), Von Her, II et al.
patent: 6483509 (2002-11-01), Rabenhorst
Fuhr Richard David
Hobbs Craig Alan
Le Gendre Scott Morgan
King & Spalding LLP
Luu Matthew
Microsoft Corporation
LandOfFree
System and method for placing splines using refinement and... 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 placing splines using refinement and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for placing splines using refinement and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3165651