Approximation of stroked higher-order curved segments by quadratic bèzier curve segments

• US 8,773,439 B2
• Filed: 04/29/2011
• Issued: 07/08/2014
• Est. Priority Date: 05/21/2010
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Kilgard, Mark J., Moreton, Henry Packard
• Primary Examiner(s): Tung, Kee M
• Assistant Examiner(s): Wilson, Nicholas R
• Application Number:
  US13/098,102
• Publication Number:
  US 20110285722A1
• Time in Patent Office: 1,166 Days
• Field of Search: None
• US Class Current: 345/442
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 15/005 General purpose rendering architectures

Abstract

One embodiment of the present invention sets forth a technique for subdividing stroked higher-order curved segments into quadratic Bèzier curve segments. Path stroking may be accelerated when a GPU or other processor is configured to perform the subdivision operations. Cubic Bèzier path segments are subdivided into quadratic Bèzier curve segments and other lower-order segments at key features. The quadratic Bèzier curve segments approximate the cubic Bèzier path segments. A variance metric is computed for each quadratic Bèzier curve segment, and when the variance metric indicates that the quadratic Bèzier curve segment deviates by more than a threshold from the corresponding portion of the cubic Bèzier path segment, the quadratic Bèzier curve segment is further subdivided. The path composed of the quadratic Bèzier curve segments is then stroked by rendering hull geometry that encloses the path.

Claims

1. A method of approximating cubic Bè

zier path segments, the method comprising;

receiving a stroke width and a path including a cubic Bè

zier path segment;

computing a first endpoint position, a second endpoint position, a first tangent at the first endpoint, and a second tangent at the second endpoint for the cubic Bè

zier path segment

fitting an approximating quadratic Bè

zier curve segment to the endpoint positions and tangents computed for the cubic Bè

zier path segment;

determining whether the approximating quadratic Bè

zier curve segment is an accurate approximation of the cubic Bè

zier path segment based on a variance metric; and

stroking an approximated path including the approximating quadratic Bezier curve segment by;

constructing a bounding hull geometry that encloses the approximating quadratic Bè

zier curve segment;

writing results to a stencil buffer indicating whether sample points within the bounding hull geometry are inside of a stroke region specified by the stroke width and the approximated path; and

filling the stroke region by writing a color buffer using the results stored in the stencil buffer.

2. The method of claim 1, wherein the variance metric is based on the deviation between the cubic Bè

zier path segment and the approximating quadratic Bè

zier curve segment.

3. The method of claim 1, further comprising the steps of:

identifying key features of the path; and

subdividing the path at each key feature.

4. The method of claim 3, wherein the key features include one or more of a cusp point, a point of self-intersection, and a point of maximum curvature of the path.

5. The method of claim 1, further comprising subdividing the cubic Bè

zier path segment into two or more quadratic Bè

zier curve segments when the variance metric is not within a tolerance threshold.

6. The method of claim 1, further comprising the step of fitting a second approximating quadratic Bè

zier curve segment to the first endpoint and a third endpoint while maintaining geometric tangent continuity with the first tangent.

7. The method of claim 1, further comprising replacing a collinear cubic Bè

zier path segment of the path with a line segment.

8. The method of claim 1, wherein writing the results to the stencil buffer indicating whether the sample points within the bounding hull geometry are inside of the stroke region is performed by evaluating a point containment algorithm for each of the sample points.

9. The method of claim 8, wherein the point containment algorithm comprises a sample point-specific cubic equation.

10. The method of claim 9, wherein parameters of the sample point-specific cubic equation are computed based on the approximating quadratic Bè

zier curve segment.

11. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to approximate cubic Bè

zier path segments, by performing the steps of;

receiving a stroke width and a path including a cubic Bè

zier path segment;

computing a first endpoint position, a second endpoint position, a first tangent at the first endpoint, and a second tangent at the second endpoint for the cubic Bè

zier path segment

fitting an approximating quadratic Bè

zier curve segment to the endpoint positions and tangents computed for the cubic Bè

zier path segment;

determining whether the approximating quadratic Bè

zier curve segment is an accurate approximation of the cubic Bè

zier path segment based on a variance metric; and

stroking an approximated path including the approximating quadratic Bè

zier curve segment by;

constructing a bounding hull geometry that encloses the approximating quadratic Bè

zier curve segment;

writing results to a stencil buffer indicating whether sample points within the bounding hull geometry are inside of a stroke region specified by the stroke width and the approximated path; and

filling the stroke region by writing a color buffer using the results stored in the stencil buffer.

12. The non-transitory computer-readable storage medium of claim 11, wherein the variance metric is based on the deviation between the cubic Bè

zier path segment and the approximating quadratic Bè

zier curve segment.

13. The non-transitory computer-readable storage medium of claim 11, further comprising the steps of:

identifying key features of the path; and

subdividing the path at each key feature.

14. The non-transitory computer-readable storage medium of claim 13, wherein the key features include one or more of a cusp point, a point of self-intersection, and a point of maximum curvature of the path.

15. The non-transitory computer-readable storage medium of claim 11, further comprising subdividing the cubic Bè

zier path segment into two or more quadratic Bè

zier curve segments when the variance metric is not within a tolerance threshold.

16. The non-transitory computer-readable storage medium of claim 11, further comprising the step of fitting a second approximating quadratic Bè

zier curve segment to the first endpoint and a third endpoint while maintaining geometric tangent continuity with the first tangent.

17. A system for approximate cubic Bè

zier path segments, the system comprising;

a memory that is configured to store a stroke width and a path including a cubic Bè

zier path segment; and

a processor that is coupled to the memory and configured to;

receive the stroke width and the path including the cubic Bè

zier path segment;

compute a first endpoint position, a second endpoint position, a first tangent at the first endpoint, and a second tangent at the second endpoint for the cubic Bè

zier path segment

fit an approximating quadratic Bè

zier curve segment to the endpoint positions and tangents computed for the cubic Bè

zier path segment;

determine whether the approximating quadratic Bè

zier curve segment is an accurate approximation of the cubic Bè

zier path segment based on a variance metric; and

stroke an approximated path including the approximating quadratic Bè

zier curve segment by;

constructing a bounding hull geometry that encloses the approximating quadratic Bè

zier curve segment;

writing results to a stencil buffer indicating whether sample points within the bounding hull geometry are inside of a stroke region specified by the stroke width and the approximated path; and

filling the stroke region by writing a color buffer using the results stored in the stencil buffer.