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

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.

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 Bèzier curve segment to fill a stroke region specified by the stroke width and the approximated path. 
 
     
     
         2 . The method of  claim 1 , wherein the stroking of the approximated path further comprises constructing a bounding hull geometry that encloses the approximating quadratic Bèzier curve segment. 
     
     
         3 . The method of  claim 2 , wherein the stroking of the approximated path further comprises:
 rendering the bounding hull geometry;   identifying sample points within the bounding hull geometry that are inside of a portion of the stroke region of the approximating quadratic Bèzier curve segment; and   writing a color buffer to fill pixels that are inside of the portion of the stroke region of the approximating quadratic Bèzier curve segment.   
     
     
         4 . The method of  claim 3 , wherein the step of identifying sample points within the bounding hull geometry that are inside of the portion of the stroke region of the approximating quadratic Bèzier curve segment comprises writing a stencil buffer. 
     
     
         5 . 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. 
     
     
         6 . The method of  claim 1 , further comprising the steps of:
 identifying key features of the path; and   subdividing the path at each key feature.   
     
     
         7 . The method of  claim 6 , 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. 
     
     
         8 . 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. 
     
     
         9 . 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. 
     
     
         10 . The method of  claim 1 , further comprising replacing a collinear cubic Bèzier path segment of the path with a line 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 to fill a stroke region specified by the stroke width and the approximated path. 
 
     
     
         12 . The non-transitory computer-readable storage medium of  claim 11 , wherein the stroking of the approximated path further comprises constructing a bounding hull geometry that encloses the approximating quadratic Bèzier curve segment. 
     
     
         13 . The non-transitory computer-readable storage medium of  claim 12 , wherein the stroking of the approximated path further comprises:
 rendering the bounding hull geometry;   identifying sample points within the bounding hull geometry that are inside of a portion of the stroke region of the approximating quadratic Bèzier curve segment; and   writing a color buffer to fill pixels that are inside of the portion of the stroke region of the approximating quadratic Bèzier curve segment.   
     
     
         14 . The non-transitory computer-readable storage medium of  claim 13 , wherein the step of identifying sample points within the bounding hull geometry that are inside of the portion of the stroke region of the approximating quadratic Bèzier curve segment comprises writing a stencil buffer. 
     
     
         15 . 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. 
     
     
         16 . 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.   
     
     
         17 . The non-transitory computer-readable storage medium of  claim 16 , 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. 
     
     
         18 . 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. 
     
     
         19 . 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. 
     
     
         20 . 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 to fill a stroke region specified by the stroke width and the approximated path.