System, method, and computer program product for angular subdivision of quadratic bezier curves

Abstract

A system, method, and computer program product are provided for subdividing a quadratic Bezier curve. The method includes the steps of receiving a quadratic Bezier curve defined by a plurality of control points including at least a first endpoint and a second endpoint. The quadratic Bezier curve is uniformly subdivided based on an angle between a first tangent at the first endpoint and a second tangent at the second endpoint to produce a piecewise representation of the quadratic Bezier curve including two or more Bezier curve segments.

What is claimed is: 
     
         1 . A method comprising:
 receiving a Bezier curve defined by a plurality of control points including at least a first endpoint and a second endpoint; and   subdividing, by a processor, the Bezier curve uniformly based on an angle between a first tangent at the first endpoint and a second tangent at the second endpoint to produce a piecewise representation of the Bezier curve including two or more Bezier curve segments.   
     
     
         2 . The method of  claim 1 , wherein the Bezier curve is a quadratic Bezier curve that defines a portion of a two-dimensional path and the two or more Bezier curve segments are quadratic Bezier curves. 
     
     
         3 . The method of  claim 2 , further comprising, prior to receiving the Bezier curve, approximating the two-dimensional path to produce a set of quadratic Bezier curves including the quadratic Bezier curve. 
     
     
         4 . The method of  claim 1 , further comprising determining a pair of approximate offset curves corresponding to the two or more Bezier curve segments based on a stroke width parameter. 
     
     
         5 . The method of  claim 4 , further comprising filling a region between the pair of approximate offset curves to stroke a portion of the two-dimensional path that is represented by the two or more Bezier curve segments. 
     
     
         6 . The method of  claim 1 , further comprising, prior to subdividing, determining a number of Bezier curve segments into which the Bezier curve is subdivided. 
     
     
         7 . The method of  claim 6 , wherein the number is computed based on the angle and a predetermined error value. 
     
     
         8 . The method of  claim 7 , wherein the predetermined error value is based on a curve offset parameter. 
     
     
         9 . The method of  claim 1 , wherein each Bezier curve segment is defined by a first segment endpoint and a second segment endpoint, and the angles between a first segment tangent at the first segment endpoint and a second segment tangent at the second segment endpoint for each Bezier curve segment are equal. 
     
     
         10 . The method of  claim 9 , wherein the first and the second relative angles equal the angle divided by a quantity of the two or more Bezier curve segments into which the Bezier curve is subdivided. 
     
     
         11 . The method of  claim 1 , wherein each processing thread in a set of processing threads is assigned to calculate one Bezier curve segment of the Bezier curve segments. 
     
     
         12 . A system comprising:
 a memory configured to store a Bezier curve defined by a plurality of control points including at least a first endpoint and a second endpoint; and   a processor that is configured to:
 receive the Bezier curve; and 
 subdivide the Bezier curve uniformly based on an angle between a first tangent at the first endpoint and a second tangent at the second endpoint to produce a piecewise representation of the Bezier curve including two or more Bezier curve segments. 
   
     
     
         13 . The system of  claim 12 , wherein the Bezier curve is a quadratic Bezier curve that defines a portion of a two-dimensional path and the two or more Bezier curve segments are quadratic Bezier curves. 
     
     
         14 . The system of  claim 13 , wherein the processor is further configured to, prior to receiving the Bezier curve, approximate the two-dimensional path to produce a set of quadratic Bezier curves including the quadratic Bezier curve. 
     
     
         15 . The system of  claim 12 , wherein the processor is further configured to determine a pair of approximate offset curves corresponding to the two or more quadratic Bezier curve segments based on a stroke width parameter. 
     
     
         16 . The system of  claim 15 , wherein the processor is further configured to fill a region between the pair of approximate offset curves to stroke a portion of the two-dimensional path that is represented by the two or more Bezier curve segments. 
     
     
         17 . The system of  claim 12 , wherein the processor is further configured to, prior to subdividing, determine a number of Bezier curve segments into which the Bezier curve is subdivided. 
     
     
         18 . The system of  claim 17 , wherein the number is computed based on the angle and a predetermined error value. 
     
     
         19 . The system of  claim 12 , wherein each Bezier curve segment is defined by a first segment endpoint and a second segment endpoint, and the angles between a first segment tangent at the first segment endpoint and a second segment tangent at the second segment endpoint for each Bezier curve segment are equal. 
     
     
         20 . A computer-readable storage medium storing instructions that, when executed by a processor, causes the processor to perform steps comprising:
 receiving a Bezier curve defined by a plurality of control points including at least a first endpoint and a second endpoint; and   subdividing, by a processor, the Bezier curve uniformly based on an angle between a first tangent at the first endpoint and a second tangent at the second endpoint to produce a piecewise representation of the Bezier curve including two or more Bezier curve segments.