Point containment for quadratic bèzier strokes

Abstract

One embodiment of the present invention sets forth a technique for stroking rendered paths. Path rendering may be accelerated when a graphics processing unit or other processor is configured to identify pixels that are within half of the stroke width of any point along a path to be stroked. The path is represented by quadratic Bèzier segments and a cubic equation is evaluated to determine whether or not each point in a conservative hull that bounds the quadratic Bèzier segment is within the stroke width.

1 . A method of stroking quadratic Bèzier path segments, the method comprising:
 receiving a quadratic Bèzier path segment and a stroke width that defines a stroke region of the quadratic Bèzier path segment; 
 generating a conservative hull geometry that bounds the quadratic Bèzier path segment; 
 computing a set of parameters for the quadratic Bèzier path segment; and 
 for each sample point within the conservative hull geometry, evaluating a sample point-specific cubic equation based on the set of parameters to determine whether the sample point is within the stroke region. 
 
     
     
         2 . The method of  claim 1 , further comprising:
 receiving a second quadratic Bèzier path segment; and   replacing the second quadratic Bèzier path segment with a line segment or a point when the second quadratic Bèzier path segment is degenerate.   
     
     
         3 . The method of  claim 1 , wherein the set of parameters are computed based vertex positions of the conservative hull geometry. 
     
     
         4 . The method of  claim 1 , further comprising interpolating the set of parameters over the conservative hull geometry to generate scalar linear coefficients. 
     
     
         5 . The method of  claim 4 , wherein the interpolating is performed using centroid sampling. 
     
     
         6 . The method of  claim 4 , wherein the interpolating is performed at pixel centers. 
     
     
         7 . The method of  claim 1 , wherein the quadratic Bèzier path segment is a portion of a path defined by the quadratic Bèzier path segment and additional quadratic Bèzier path segments, and further comprising
 generating additional conservative hull geometries that bound the additional quadratic Bèzier path segments; 
 computing additional sets of parameters for the additional quadratic Bèzier path segments; and 
 for each sample point within the additional conservative hull geometries, evaluating a sample point-specific cubic equation based on the respective additional set of parameters to determine whether the sample point is within a stroke region of the path. 
 
     
     
         8 . The method of  claim 7 , wherein a stencil buffer stores data indicating the sample points that are within the stroke region of the path and the stroke region of the quadratic Bèzier path segment. 
     
     
         9 . The method of  claim 8 , further comprising
 generating a second conservative hull geometry that bounds the path; and   processing the second conservative hull geometry to stroke the path based on the stencil buffer.   
     
     
         10 . The method of  claim 1 , further comprising discarding sample points that are outside of a parametric range of the quadratic Bèzier path segment. 
     
     
         11 . The method of  claim 1 , further comprising writing a color buffer for sample points that are determined to be within the stroke region. 
     
     
         12 . A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to stroke quadratic Bèzier path segments, by performing the steps of:
 receiving a quadratic Bèzier path segment and a stroke width that defines a stroke region of the quadratic Bèzier path segment; 
 generating a conservative hull geometry that bounds the quadratic Bèzier path segment; 
 computing a set of parameters for the quadratic Bèzier path segment; and 
 for each sample point within the conservative hull geometry, evaluating a sample point-specific cubic equation based on the set of parameters to determine whether the sample point is within the stroke region. 
 
     
     
         13 . The non-transitory computer-readable storage medium of  claim 12 , further comprising:
 receiving a second quadratic Bèzier path segment; and   replacing the second quadratic Bèzier path segment with a line segment or a point when the second quadratic Bèzier path segment is degenerate.   
     
     
         14 . The non-transitory computer-readable storage medium of  claim 12 , wherein the set of parameters are computed based vertex positions of the conservative hull geometry. 
     
     
         15 . The non-transitory computer-readable storage medium of  claim 12 , further comprising interpolating the set of parameters over the conservative hull geometry to generate scalar linear coefficients. 
     
     
         16 . The non-transitory computer-readable storage medium of  claim 12 , wherein the quadratic Bèzier path segment is a portion of a path defined by the quadratic Bèzier path segment and additional quadratic Bèzier path segments, and further comprising
 generating additional conservative hull geometries that bound the additional quadratic Bèzier path segments; 
 computing additional sets of parameters for the additional quadratic Bèzier path segments; and 
 for each sample point within the additional conservative hull geometries, evaluating a sample point-specific cubic equation based on the respective additional set of parameters to determine whether the sample point is within a stroke region of the path. 
 
     
     
         17 . The non-transitory computer-readable storage medium of  claim 16 , wherein a stencil buffer stores data indicating the sample points that are within the stroke region of the path and the stroke region of the quadratic Bèzier path segment. 
     
     
         18 . The non-transitory computer-readable storage medium of  claim 17 , further comprising
 generating a second conservative hull geometry that bounds the path; and   processing the second conservative hull geometry to stroke the path based on the stencil buffer.   
     
     
         19 . The non-transitory computer-readable storage medium of  claim 12 , further comprising writing a color buffer for sample points that are determined to be within the stroke region. 
     
     
         20 . A system for stroking quadratic Bèzier path segments, the system comprising:
 a memory that is configured to store data indicating whether sample points are within a stroke region of a path; and 
 a processor that is coupled to the memory and configured to:
 receive a quadratic Bèzier path segment and a stroke width that defines the stroke region; 
 generate a conservative hull geometry that bounds the quadratic Bèzier path segment; 
 compute a set of parameters for the quadratic Bèzier path segment; and 
 for each sample point within the conservative hull geometry, evaluate a sample point-specific cubic equation based on the set of parameters to determine whether the sample point is within the stroke region.