QUADRATIC APPROXIMATE OFFSET CURVES FOR QUADRATIC CURVE SEGMENTS

• US 20130018636A1
• Filed: 07/14/2011
• Published: 01/17/2013
• Est. Priority Date: 07/14/2011
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ruf, Erik S.
• Application Number:
  US13/182,453
• Publication Number:
  US 20130018636A1
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06F 17/17 Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method G06F17/18 takes precedence ; interpolation for numerical control G05B19/18
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

A system is described herein that produces at least one approximate offset curve that is separated by an original curve segment S_o by at least a distance d, thus defining a bounding region between the original curve segment S_o and the approximate offset curve. The original curve segment S_o and the approximate offset curve both have a quadratic form. In view of this quadratic form, the system can represent the approximate offset curve in an efficient manner (e.g., using three control points). Further, the system can perform calculations with respect to the approximate offset curve in an efficient manner.

Claims

1. A method for producing an offset curve, implemented using tangible and physical computing functionality, comprising:

receiving data that describes an original control triangle, the original control triangle defining an original curve segment, the original curve segment, in turn, defining a portion of a parabola having an axis a;

constructing an original axis-symmetric control triangle based on the original control triangle, the original axis-symmetric control triangle being symmetric with respect to the axis a of the parabola;

constructing a new control triangle by adjusting positions of control points associated with the original axis-symmetric control triangle, the new control triangle also being symmetric with respect to the axis a of parabola, the new control triangle defining an approximate offset curve, and all points on the approximate offset curve being separated from all points on the original curve segment by at least a distance d; and

performing an application-specific action based on the approximate offset curve.

2. The method of claim 1, wherein the computing functionality comprises at least one processing device for processing instructions maintained in a computer-readable storage medium.

3. The method of claim 1, wherein said constructing of the new control triangle comprises moving the positions of the control points associated with the original axis-symmetric control triangle in an outward direction, such that the new control triangle is larger than the original axis-symmetric control triangle.

4. The method of claim 1, wherein said constructing of the new control triangle comprises moving the positions of the control points associated with the original axis-symmetric control triangle in an inward direction, such that the new control triangle is smaller than the original axis-symmetric control triangle.

5. The method of claim 1, wherein said constructing of the new control triangle comprises:

constructing a first new control triangle which defines a first approximate offset curve; and

constructing a second new control triangle which defines a second approximate offset curve.

6. The method of claim 5, wherein the original curve segment lies between the first approximate offset curve and the second approximate offset curve.

7. The method of claim 1, wherein the application-specific action comprises generating a graphical image based on at least the original curve segment and one or more corresponding approximate offset curves.

8. The method of claim 1, wherein the application-specific action comprises controlling a path taken by a machine based on at least the original curve segment and one or more corresponding approximate offset curves.

9. The method of claim 1, wherein said application specific action comprises:

receiving a query point;

determining whether the query point lies in a region bounded by the approximate offset curve and the original curve segment;

if the query point lies in the region, performing an analysis operation; and

if the query point does not lie in the region, avoiding the analysis operation.

10. The method of claim 9, wherein the analysis operation comprises determining a distance between the query point and the original curve segment using a distance-determination technique.

11. The method of claim 10, further comprising using the distance to perform an anti-aliasing operation within a graphical image.

12. The method of claim 10, further comprising using the distance to render a brushed path within a graphical image.

13. A system for producing and applying an offset curve, implemented using tangible and physical computing functionality, comprising:

an offset curve determination module for;

receiving data that describes an original control triangle, the original control triangle defining an original curve segment; and

producing an approximate offset curve based on the original control triangle, all points on the approximate offset curve being separated from all points on the original curve segment by at least a distance d, the original curve segment and the approximate offset curve each representing quadratic curves; and

an application module for performing an application-specific action based on the approximate offset curve.

14. The system of claim 13, wherein the offset curve determination module comprises:

a symmetric control triangle determination module for constructing an original axis-symmetric control triangle based on the original control triangle, the original axis-symmetric control triangle being symmetric with respect to an axis a of a parabola associated with the original curve segment; and

a control triangle extension module for constructing a new control triangle by adjusting positions of control points associated with the original axis-symmetric control triangle, the new control triangle also being symmetric with respect to the axis a of the parabola,

the new control triangle defining the approximate offset curve.

15. The system of claim 13, wherein the application-specific action comprises generating a graphical image based on at least the original curve segment and one or more corresponding approximate offset curves.

16. The system of claim 13, wherein the application-specific action comprises controlling a path taken by a machine based on at least the original curve segment and one or more corresponding approximate offset curves.

17. The system of claim 13, wherein the application module comprises:

a query point determining module for receiving a query point and determining whether the query point lies in a region bounded by the approximate offset curve and the original curve segment; and

an action-taking module for, if the query point lies in the region, determining a distance between the query point and the original curve segment using a distance-determination technique.

18. A computer readable storage medium for storing computer readable instructions, the computer readable instructions providing an offset curve determination module when executed by one or more processing devices, the computer readable instructions comprising:

logic configured to receive data that describes an original control triangle associated with control points p₀, p₁, and p₂, the original control triangle defining an original curve segment S_o;

logic configured to determine a line m which connects a midpoint of a line segment p₀p₂ to the control point p₁;

logic configured to draw a chord that is perpendicular to the line m which intersects an extended version of the original curve segment S_o twice, defining new control points q₀ and q₂;

logic configured to extend tangent lines at the new control points q₀ and q₂, yielding a new control point q₁ at an intersection of the tangent lines, the control points q₀, q₁, and q₂ together describing an original axis-symmetric control triangle; and

logic configured to displace the new control points (q₀, q₁, q₂) in an inward or outward direction to produce new control points (q′

₀, q′

₁, q′

₂), the new control points (q′

₀, q′

₁, q′

₂) defining a new control triangle and an associated approximate offset curve.

19. The computer-readable storage medium of claim 18, wherein the chord intersects either the control point p₀ or the control point p₂.

20. The computer-readable storage medium of claim 18, wherein the computer-readable instructions further implement an application module, the computer readable instructions comprising:

logic for receiving a query point and determining whether the query point lies in a region bounded by the approximate offset curve and the original curve segment; and

logic for, if the query point lies in the region, determining a distance between the query point and the original curve segment using a distance-determination technique.