Fast, precise flattening of cubic Bezier path and offset curves

摘要

We present two related algorithms for flattening (generating polyline approximations for) curves associated with planar cubic Bezier segments. One flattens the path curve, and the other flattens the left and right offset curves. The algorithm for flattening path curves yields an average of 67% of the vertices generated by recursive subdivision, while maintaining flatness to within 4% of the specified value, and runs 37% faster. The algorithm for flattening offset curves generates 70% of the vertices as the methods based on recursive subdivision, such that 94% of all subsegments fall within 20% of the flatness criterion. This latter code runs as fast as recursive subdivision.