Continuous-curvature rational curves for drawing applications

Techniques of generating curves in drawing applications involve generating rational interpolating curves in response input points being specified on a display such that the rational interpolating curves have an adjustable sharpness at each of the input points. Along these lines, a user specifies control points of a curve in a drawing application by, e.g., moving these control points on a display. In response, a computer running the drawing application generates a rational interpolating curve that intersects the input points such that the curvature of each curve at its input point is a local maximum and such that the user's sharpness values change the roundness of the curve around corresponding control points.

TECHNICAL FIELD

This description relates to generating curves in computer drawing applications.

BACKGROUND

Some computer-based drawing applications provide controls that enable a user to draw arbitrary curves on a display. For example, when a user of a drawing application specifies distinct control points by which a curve may be manipulated, the drawing application outputs a curve that intersects some of the control points. When the user moves a control point on the display using an input device (e.g., a mouse), the drawing application outputs a new curve.

Such a curve may take the form of an interpolating curve. Interpolating curves are continuous curves that intersect a set of specified points. The generation of an interpolating curve may involve the specification of polynomial coefficients that intersect the set of specified points and satisfy certain criteria. For example, a Lagrange interpolation produces a single interpolating polynomial curve of minimum degree that goes through each of the specified points. Conventional approaches to outputting curves in a drawing application involve generating an interpolating curve specified by the drawing application in response to a user specifying points on a display.

SUMMARY

In one general aspect, a method can include receiving, by processing circuitry configured to display user-specified drawings on a display device, point data input by a user on the display device, the point data representing a set of input points through which a rational interpolating curve is configured to intersect. The method can also include obtaining, by the processing circuitry, sharpness data representing a shape of the rational interpolating curve. The method can further include generating, by the processing circuitry, rational interpolating curve data representing the rational interpolating curve based on the point data and the sharpness data, the rational interpolating curve data including a set of weights, each of the set of weights corresponding to a respective input point and modulating an effect of a change of shape of the rational interpolating curve. The method can further include displaying as a drawing on the display device, by the processing circuitry, the rational interpolating curve based on the rational interpolating curve data, the rational interpolating curve having a local maximum of a curvature at each of the set of input points.

DETAILED DESCRIPTION

The above-described conventional approaches to outputting curves in a drawing application result in curves that are difficult for the user to control. For instance, interpolating curves used in such conventional approaches exhibit discontinuous behavior in response to continuous changes to the position of a control point on the display. For example, suppose that a user wants to invoke a slight change to a curve by dragging a control point on the screen a small distance. Some curves may instead exhibit large changes in curvature in response to such small changes to the input. Some interpolating curves may exhibit other undesirable behaviors such as cusps and loops away from control points. Such undesirable discontinuous behavior of the interpolating curves is difficult for the user to understand and control and may lead to a frustrating user experience in drawing curves on a display.

Other conventional approaches to outputting curves in a drawing application involve defining piecewise quadratic interpolating curves whose curvature has a local maximum at an interior control point. While such interpolating curves avoid problems such as cusps and loops, the resulting interpolating curves are constrained in the possible shapes they allow to user to produce. For example, such curves cannot reproduce a circle because they are represented by a quadratic (i.e., parabolic) function. Further, the requirement of the curvature maximum being at the interior control point removes a degree of freedom from the user to control the shape of such curves. Accordingly, while these quadratic interpolating curves provide a better experience for a novice user, they provide a less satisfying, relatively inflexible experience of a more experienced user.

In accordance with the implementations described herein and in contrast to the above-described conventional approaches to outputting curves in a drawing application, improved techniques of generating curves in drawing applications involve generating rational interpolating curves in response to input points being specified on a display such that the rational interpolating curves have a curvature maximum at each of the input points. Each input point corresponds to a simple rational curve: a rational quadratic interpolating curve. Each rational quadratic interpolating curve is a quadratic function in both the numerator and denominator. Such curves avoid the pitfalls of those generated according to the above-described conventional techniques: small changes to an input point produces small changes to the output curve.

Along these lines, suppose that a user specifies input points of a curve in a drawing application by, e.g., moving these control points on a display of a computer with an input device such as a mouse. When the curve to be drawn is an aggregation of rational quadratic interpolating curves, a computer running the drawing application generates exterior control points, i.e., the endpoints of each such curve, an off-curve control point for each rational quadratic interpolating curve. Each pair of exterior control points and an off-curve control point define a rational quadratic interpolating curve that intersects a respective input point such that the curvature of each curve at its input points is a local maximum. The generation of the control points for one rational quadratic interpolating curve depends on the control points for neighboring rational quadratic interpolating curves of a rational interpolating curve. This leads to a tridiagonal linear system to solve for the control points.

The computer may also generate a weight associated with the off-curve control point of a rational quadratic interpolating curve based on additional constraints. In some implementations, the user may also specify a sharpness (or tension) value that varies a sharpness or roundness of the rational interpolating curve. The generated and user-input shape of the curve modulate an effect of a change of position of the input point and control the sharpness or roundness of that curve in the neighborhood of the input point.

In some implementations, the computer may generate a critical weight for a curve that minimizes an eccentricity of that curve, i.e., makes the curve as close to a circular arc as possible. (NB a rational quadratic curve is equivalent to a conic; the eccentricity of such a conic depends on the weight.)

In some implementations, the computer may generate, as the weight, a power of the critical weight based on a user-specified sharpness value, i.e., according to whether the user specifies a sharper or rounder curve. In some implementations, the power may be based on an angle formed by the intersection at an off-curve control point of the tangents to the curve at the exterior control points. In some implementations, the power may be based on the discrete curvature of the curve at each of the input points. In some implementations, the power being greater than one indicates a sharper curve and the power being less than one indicates a rounder curve.

In some implementations, the computer may generate, as the weight, a multiplier of the critical weight based on a user-specified sharpness value.

In some implementations, the computer may generate, as the weight, the greater of a given weight and a quantity that is based on a specified minimum angle formed by the intersection of the tangents to the curve at the exterior control points. In some implementations, the quantity is the sine of half of the specified minimum angle.

The above-defined rational interpolating curves provide a satisfying experience for both novice and more experienced users. Such curves exhibit continuous behavior in response to continuous changes in the positions of control points. Further, such curves also provide flexibility in defining overall shape by generating to make the curve sharper or rounder in the neighborhood of specified input points as desired.

The following definitions are used for clarity in the discussion hereinafter. Input points refer to those points pi(see, e.g.,FIG. 2) input by the user to define a curve. A rational interpolating curve (210inFIG. 2) refers to the desired curve that goes through the input points and includes a set of rational quadratic interpolating curves. Each rational quadratic interpolating curve (see, e.g.,210(1) and210(2) inFIG. 2) corresponds to an input point and is a ratio of two quadratic functions. Exterior control points ci,0and ci,2(see, e.g.,FIG. 2) refer to the ends of a rational quadratic interpolating curve—these are not input by the user but are generated instead. Off-curve control points ci,1(see, e.g.,FIG. 2) are points not on the curve but used, in concert with the exterior control points, to define the shape of each of rational quadratic interpolating curve.

FIG. 1is a diagram that illustrates an example electronic environment100in which the above-described improved techniques may be implemented. As shown, inFIG. 1, the electronic environment100includes a computer120and a display180viewed by a user182.

The computer120is configured to display user-specified drawings on a display device. The computer120includes a network interface122, one or more processing units124, memory126, and a display interface128. The network interface122includes, for example, Ethernet adaptors, Token Ring adaptors, and the like, for converting electronic and/or optical signals received from a network to electronic form for use by the editing computer120. The set of processing units124include one or more processing chips and/or assemblies. The memory126includes both volatile memory (e.g., RAM) and non-volatile memory, such as one or more ROMs, disk drives, solid state drives, and the like. The set of processing units124and the memory126together form control circuitry, which is configured and arranged to carry out various methods and functions as described herein.

In some embodiments, one or more of the components of the computer120can be, or can include processors (e.g., processing units124) configured to process instructions stored in the memory126. Examples of such instructions as depicted inFIG. 1include a control point acquisition manager130, a rational interpolating curve generation manager140, a weight adjustment acquisition manager150, a continuity manager160, a curve rendering manager170, and a GUI manager172. Further, as illustrated inFIG. 1, the memory126is configured to store various data, which is described with respect to the respective managers that use such data.

The control point acquisition manager130is configured to obtain control point data132in response to a user input. For example, in the context of a drawing application running on the computer120, the GUI manager172may output data defining an application window on the display180via the display interface128. Within the application window, the user182may depress a “curve” button that outputs a first exterior control point in the window. The user may then click at another location in the window to produce an input point of the curve, and then a third location to produce a second exterior control point of the curve. Further clicks in the window may define other control points of an aggregate curve that is made from other curves.

The control point data132includes exterior control point data134and input point data136. Each of the control points represented in the control point data includes a coordinate pair representing a position within the application window. Each of the exterior control points represented in the exterior control point data134is an endpoint of an individual curve. Each of the input points represented in the input point data136is a point on an individual curve.

FIG. 2illustrates an example graphical user interface (GUI)200containing an application window in which these control points are defined. There are actually two curves in the application window210(1) and210(2). The exterior control points of the curve210(1) are denoted as ci,0and ci,2(the index i implying that the curve210(1) may be part of a larger aggregate curve). The input point of the curve210(1) is on the curve and is denoted as pi. Similarly, the exterior control points of the curve210(2) are denoted as ci+1,0and ci+1,2, and the input point is denoted as pi+1.

If the curve is closed (i.e., drawn as a loop), then the indexing described above is performed modulo the number of input points N of the curve. If the curve is open then the first and last input points are duplicated at either end, i.e., the first input point is used as a first exterior control point, and the last input point is likewise used as a last exterior control point.

Returning toFIG. 1, the rational interpolating curve generation manager140is configured to generate rational interpolating curve data142based on the control point data132. Each rational interpolating curve, here curve210(1) ofFIG. 2, takes the form of a rational quadratic as follows:

ci⁡(t)=(1-t)2⁢ci,0+2⁢t⁡(1-t)⁢wi⁢ci,1+t2⁢ci,2(1-t)2+2⁢t⁡(1-t)⁢wi+t2,(1)
where t∈[0,1], ci,1is an off-curve control point, and wiis a weight. Again, this curve is labeled as part of an aggregate curve containing many such rational quadratic interpolating curves. In some implementations (and those described herein), the off-curve control points are computed by the computer120based on the control point data132. Nevertheless, for the purposes of discussion, it will be assumed that the off-curve control point data144are known.

The rational interpolating curve generation manager140is configured to generate the rational interpolating curve data142based on the constraint that the curvature of the rational quadratic interpolating curve defined in Eq. (1) has a local maximum at the input point pi. Accordingly, when the input point pidefines a corresponding, unique value of the parameter t=ti, i.e., pi=ci(ti), the parameter value tiindicates the position of maximum curvature along the curve. Using the definition of curvature

κi⁡(t)=ci′⁡(t)×ci″⁡(t)ci′⁡(t)3,(2)
the computer120may determine this unique value tiby solving the equation

Combined with the equation pi=ci(ti), Eq. (4) represents two equations for the unknowns ci,1and tigiven the values ci,0, ci,2, and wi.

In some implementations, the computer120also generates a value of the weight, denoted herein as a critical weight146wi=wCsuch that the eccentricity of the rational quadratic interpolating curve defined in Eq. (1) is a minimum, i.e., is as close to a circular arc as possible. The critical weight may be expressed explicitly in terms of the exterior control points and the off-curve control point as follows:

where |ci,0ci,2| is the distance between the points ci,0and ci,2, and so on.

The weight adjustment acquisition manager150is configured to adjust the value of the weight based on sharpness value input from the user182relative to the critical weight146, i.e., weight adjustment data154. For example, the weight may be a power of the critical weight154, i.e., w=wCp, where p represents the power data156, based on the sharpness value input by the user182. Along these lines, when p=0, then w=1 and the curve is a parabola having an eccentricity of 1. When p=1, then the curve has a minimum eccentricity and the curve resembles a circular arc as closely as possible. Nevertheless, when p is increased or decreased away from 1, the curve becomes respectively rounder or sharper. An example of a control that may produce a user-defined power is shown inFIG. 2, as a slide-bar selector220in the GUI200.

In some implementations, the weight adjustment acquisition manager150may automatically generate a power based on the geometric properties of the curve. In one example, the weight adjustment acquisition manager150generates the power data146based on the angle of intersection between the tangents at each of the exterior control points of the curve. In another example, the weight adjustment acquisition manager150generates the power data146based on the discrete curvatures of the curve at each the input point. In the latter example, an expression for the power is as follows:

p=cos⁢⁢ϕcos⁢⁢ϕ+(d2-d1)2d22+(d0-d1)2d02,(6)
where ϕ is the angle of intersection between the tangents at an off-curve control point of each of the exterior control points ci,0and ci,2and djis the discrete curvature of the curve at the point pi. The discrete curvature djmay be computed as the inverse of the radius of the circle containing the point piand the input points of the neighboring curves pi−1and pi+1.

In another example, the weight may be a multiple of the critical weight (or a power thereof) based on the multiplier data158. The multiplier data158is generated in response to a sharpness value input from the user182when the user182indicates a rounder or sharper curve. An example of a control that may produce a user-defined multiplier is shown inFIG. 2, as a slide-bar selector230in the GUI200.

In some implementations, the weight adjustment acquisition manager150is configured to compare the resulting adjustable weight against a lower bound. The lower bound may be based on a minimum allowable angle of intersection ϕmbetween the tangents at each of the exterior control points of the curve. In one example, the adjustable weight may be computed as follows:

wi=max⁢{sin⁢ϕm2,swCp},(7)
where s is the multiple of the multiplier data158. The minimum angle ϕmmay be equal to π/4, or can take values smaller and larger.

The continuity manager160is configured to enforce continuity conditions across multiple rational quadratic interpolation curves. Such continuity conditions may take the form of G0continuity, i.e., a right exterior control point of a first curve is coincident with the left exterior control point of a second curve neighboring the first curve to the right. With respect to the diagram inFIG. 2, the G0continuity requirement translates to the condition
ci+1,0=ci,2.  (8)

Another continuity condition takes the form of G1continuity, i.e., the slope of the tangent line at the point of coincidence between two neighboring curves is continuous. Because the off-curve control points are at the points of intersections of the tangent lines at the exterior control points of the curves, then G1continuity implies that the point of coincidence and the respective off-curve control points of the curves lie on a straight line. Mathematically, this statement takes the following form:
ci,2=(1−λi)ci,1+λici+1,1,  (9)
where λiis a fraction of the distance along the line connecting the off-curve control points at which the point of coincidence lies. This geometry is illustrated inFIG. 2.

Still another continuity condition takes the form of G2continuity, i.e., the curvature of the first curve at the point of coincidence is equal to the curvature of the second curve at the point of coincidence. Mathematically, this statement takes the following form:
κi(1)=κi+1(0)  (10)
or, when combined with Eq. (9),

The curve rendering manager170is configured to render an aggregate rational interpolating curve (e.g., curve210inFIG. 2) in the GUI200. To accomplish this, the curve rendering manager170is configured to determine the off-curve control points ci,1given the control point data132and the constraints determined by the maximum curvature at the input points, the continuity conditions, and minimum eccentricity conditions. The resulting equation for these off-curve control points ci,1for i∈{0, 1, . . . , N−1} is a tridiagonal system as follows:

where λ−1=1 and wiis the weight for the ithcurve.

The system of equations in Eq. (12) is not straightforward to solve because the quantities λi−1, λi, and widepend on the off-curve control points ci,1. Accordingly, the curve rendering manager170is configured to solve the system in Eq. (12) iteratively until convergence is achieved. Such a solution is discussed in further detail with regard toFIG. 4.

The components (e.g., modules, processing units124) of the computer120can be configured to operate based on one or more platforms (e.g., one or more similar or different platforms) that can include one or more types of hardware, software, firmware, operating systems, runtime libraries, and/or so forth. In some implementations, the components of the computer120can be configured to operate within a cluster of devices (e.g., a server farm). In such an implementation, the functionality and processing of the components of the computer120can be distributed to several devices of the cluster of devices.

The components of the computer120can be, or can include, any type of hardware and/or software configured to process attributes. In some implementations, one or more portions of the components shown in the components of the computer120inFIG. 1can be, or can include, a hardware-based module (e.g., a digital signal processor (DSP), a field programmable gate array (FPGA), a memory), a firmware module, and/or a software-based module (e.g., a module of computer code, a set of computer-readable instructions that can be executed at a computer). For example, in some implementations, one or more portions of the components of the computer120can be, or can include, a software module configured for execution by at least one processor (not shown). In some implementations, the functionality of the components can be included in different modules and/or different components than those shown inFIG. 1.

In some embodiments, one or more of the components of the computer120can be, or can include, processors configured to process instructions stored in a memory. For example, an control point acquisition manager130(and/or a portion thereof), a rational interpolating curve generation manager140(and/or a portion thereof), a weight adjustment acquisition manager150(and/or a portion thereof), a continuity manager160(and/or a portion thereof), a curve rendering manager170(and/or a portion thereof), and a GUI manager172(and/or a portion thereof) can be a combination of a processor and a memory configured to execute instructions related to a process to implement one or more functions.

In some implementations, the memory126can be any type of memory such as a random-access memory, a disk drive memory, flash memory, and/or so forth. In some implementations, the memory126can be implemented as more than one memory component (e.g., more than one RAM component or disk drive memory) associated with the components of the editing computer120. In some implementations, the memory126can be a database memory. In some implementations, the memory126can be, or can include, a non-local memory. For example, the memory126can be, or can include, a memory shared by multiple devices (not shown). In some implementations, the memory126can be associated with a server device (not shown) within a network and configured to serve the components of the editing computer120. As illustrated inFIG. 1, the memory126is configured to store various data, including control point data132, rational interpolating curve data142, and weight adjustment data154.

FIG. 3is a flow chart depicting an example method300of displaying user-specified drawings on a display device. The method300may be performed by software constructs described in connection withFIG. 1, which reside in memory126of the computer120and are run by the set of processing units124.

At302, the control point acquisition manager130(FIG. 1) receives point data representing input points. Herein, as described above, the curve to be represented is an aggregation of rational quadratic interpolation curves as defined in Eq. (1). Each such curve is defined by a pair of exterior control points and an off-curve control point to be determined based on the set of input points.

At304, the weight adjustment acquisition manager150obtains weight data representing a value of each of a set of weights. Each of the set of weights corresponds to a respective input point. From Eq. (1), one may see that the weight most strongly modifies the coefficient of the off-curve control point. Again, the weight may be partially or completely specified by the user or may be partially or completely generated by the computer120based on the input points.

At306, the rational interpolating curve generation manager140and curve rendering manager170generate rational interpolating curve data based on the point data and the weight data, the rational interpolating curve data having a local maximum of a curvature at each of the set of input points. Each of the set of weights modulates an effect of a change of position of the off-curve control point to which that weight corresponds on the rational interpolating curve data.

At308, the GUI manager172displays representations of the exterior control points, the set of input points, and a rational interpolating curve representing the rational interpolating curve data on the display device. The rational interpolating curve intersects the exterior control points and the set of input points as shown inFIG. 2. Nevertheless, the curves that are rendered by the computer120are partially defined by the off-curve control points and the computer120determines those via the system of equations in Eq. (12). A solution of this system is discussed with regard toFIG. 4.

FIG. 4is a flow chart illustrating an example process400of rendering an aggregate rational interpolating curve. The process400may be performed by software constructs described in connection withFIG. 1, which reside in memory126of the computer120and are run by the set of processing units124.

At402, the computer120receives the input points pifor each curve.

At404, the computer120initializes the position of the off-curve control point ci,1to be, e.g., p1.

At406, the computer120estimates the value of λibased on the solution to Eq. (11).

At408, the computer120estimates the value of the critical weight wCbased on the result in Eq. (5).

At410, the computer120estimates the value of the parameter tibased on the curvature maximization equation in Eq. (4).

At412, the computer120solves the system in Eq. (12) to produce new estimates of the off-curve control points ci,1.

At416, the computer120compares the previous values of the exterior control points and off-curve control points to the current values of the exterior control points and off-curve control points and determines whether there has been sufficient convergence. One criterion of sufficient convergence takes the form of whether the sum of the square distances between previous and current exterior control points and off-curve control points is less than some specified tolerance. If such convergence has been achieved, then the curve is considered rendered. If not, then the process returns to406and iterates.

The process400results in a curve that automatically renders on the display180without any input from the user182besides the control points. Nevertheless, the user182still has degrees of freedom to exploit as discussed above. The integration of this user input into the rendering of the curve is discussed with regard toFIG. 5.

FIG. 5is a flow chart illustrating another example process500of rendering an aggregate rational interpolating curve. The process400may be performed by software constructs described in connection withFIG. 1, which reside in memory126of the computer120and are run by the set of processing units124.

At502, the computer120receives an indication of an adjustment to the sharpness or roundness of the curve210at some control point. For example, the user182may use the slider control230to generate a multiplier for the weight.

At504, the computer120obtains tangent angle of intersection (i.e., subtending angle at the off-curve control point) information and curvature values at the control points. This information may be used in conjunction with determining a value of the power of the critical weight.

At506, the computer120computes the power of the critical weight based on the information obtained at504using Eq. (6).

At508, the computer120computes the weight using the multiplier times the critical weight raised to the power. The computer120then compares this weight with a lower bound as defined in Eq. (7), with the larger of the two quantities being the weight used in re-rendering the curve.

At510, the computer120redraws the curve on the display180.

FIG. 6is a diagram illustrating an example set of ellipses600that vary according to the value of the weight. The critical weight at which the weight is equal to ⅔ represents the ellipse620that has the smallest eccentricity, i.e., the most circular. Note that this least-eccentric ellipse is not a circle necessarily. Decreasing the weight to 0.5 increases the eccentricity of the ellipse610in one direction (i.e., essentially horizontal) while increasing the weight to 0.8 increases the eccentricity of the ellipse630in the other direction.

FIG. 7is a diagram illustrating example set of curves710,720,730, and740that vary based on the power of the critical weight.

At710, the curve has a power value p=0. In this case, the individual rational quadratic interpolating curves reduce to parabolas used in some conventional approaches described above. Accordingly, these curves are difficult to manipulate from a user perspective and do not offer very much flexibility.

At720, the curve has a power value p=1. In this case, the individual curves resemble circular arcs rather than parabolas. This curve may be the curve seen initially by the user and may be adjusted to be sharper accordingly.

At730, the curve has a power value depending on angle subtended by the off-curve control point. At740, the curve has a power value depending on the curvatures at each of the control points as described above in Eq. (6).