Offset Bezier curves

We have spent some time here to convert a stroke path to a fill path. We made a first version of 1 pixel width strokes in 100 100 moveto 200 300 lineto stroke and improved it in Rethinking stroke to discover later A bug in the stroke algorithm and to fix it. We had to review the code when we added transparency Transparency does not work with Stroke and had to check again when we were Implementing zero winding.

In any of these algorithms, the stroke algorithm is implemented very late on chain because it works only on straight lines. So you have to convert Bezier curves to straight lines first before applying ist. It would be more elegant if we could do this directly with the Bezier curves.

This problem is called offsetting Bezier curves. It is considered as a hard problem.

We consider a parallel curve a second curve at a constant normal distance. There is not always a solution to this as shown in the Wikipedia article on parallel curves. It has been proven by Tiller and Hanson in 1984 that in general, the parallel curve of a Bézier curve is not another Bézier curve. As an approximation, they propose to offset the legs of the control polygon in perpendicular directions.

For practical applications, there are to points to consider: First, Bezier curves are only approximations of real curves in graphic design. For example, there is no combination of Bezier curves that exactly matches a circle. However, we see circles drawn with Bezier curves every day because the approximation is good enough. Second, the general case of Bezier curves deals with control points in extreme directions which are rarely used. The control points used in fonts and by professional artists in Illustrator follow some recommandations which can be handled by an approximation.

We try the following approximation: The endpoint are offset a 90 degrees from the line to the control point. A cubic interpolation point is calculated. This point is offset at 90 degrees to the line between the control points. Then the control point vectors are scaled by the relative distances between the midpoints and the endpoints. This works better for angles less than 180 degrees but less if both control points are on the opposite side.

Javascript Editor

rpnPostScriptEditor(`
10 dict begin /transparent 0 def /height 600 def /console 0 def currentdict setpagedevice end
/dot {  4 0 360 arc fill 
} def
/red { 1 0 0 setrgbcolor 1 setalpha } def
/blue { 0 0 1 setrgbcolor 1 setalpha } def
/black { 0 0 0 setrgbcolor 1 setalpha } def
/gray { 0.5 0.5 0.5 setrgbcolor 0.3 setalpha } def
/doublecurve { /d exch def /y exch def /x exch def /qy exch def /qx exch def /py exch def /px exch def /cy exch def /cx exch def

/mx cx px 3 mul add qx 3 mul add x add 8 div def
/my cy py 3 mul add qy 3 mul add y add 8 div def

/pa py cy sub px cx sub atan def
/cx0 pa 90 add cos d mul cx add def
/cy0 pa 90 add sin d mul cy add def
/cx1 pa 90 sub cos d mul cx add def
/cy1 pa 90 sub sin d mul cy add def

/qa y qy sub x qx sub atan def 
/x0 qa 90 add cos d mul x add def
/y0 qa 90 add sin d mul y add def
/x1 qa 90 sub cos d mul x add def
/y1 qa 90 sub sin d mul y add def

/ma qy py sub qx px sub atan 90 add def
/mx0 mx ma cos d mul add def
/my0 my ma sin d mul add def
/mx1 mx ma cos d mul sub def
/my1 my ma sin d mul sub def

/mm0 mx0 cx0 sub dup mul my0 cy0 sub dup mul add
mx0 x0 sub dup mul add my0 y0 sub dup mul add sqrt 
mx cx sub dup mul my cy sub dup mul add
mx x sub dup mul add my y sub dup mul add sqrt div def 
/px0 px cx sub mm0 mul cx0 add def
/py0 py cy sub mm0 mul cy0 add def
/qx0 qx x sub mm0 mul x0 add def
/qy0 qy y sub mm0 mul y0 add def
/mm1 mx1 cx1 sub dup mul my1 cy1 sub dup mul add
mx1 x1 sub dup mul add my1 y1 sub dup mul add sqrt 
mx cx sub dup mul my cy sub dup mul add
mx x sub dup mul add my y sub dup mul add sqrt div def  
/px1 px cx sub mm1 mul cx1 add def
/py1 py cy sub mm1 mul cy1 add def
/qx1 qx x sub mm1 mul x1 add def
/qy1 qy y sub mm1 mul y1 add def

cx0 cy0 moveto px0 py0 qx0 qy0 x0 y0 curveto 
x1 y1 lineto qx1 qy1 px1 py1 cx1 cy1 curveto
cx0 cy0 lineto gray fill

cx cy moveto px py qx qy x y curveto black stroke
cx0 cy0 moveto px0 py0 qx0 qy0 x0 y0 curveto red stroke 
cx1 cy1 moveto px1 py1 qx1 qy1 x1 y1 curveto blue stroke

cx cy black dot
px py black dot
qx qy black dot
x y black dot
mx my black dot

cx0 cy0 red dot
px0 py0 red dot
mx0 my0 red dot
qx0 qy0 red dot
x0 y0 red dot

cx1 cy1 blue dot
px1 py1 blue dot
mx1 my1 blue dot
qx1 qy1 blue dot
x1 y1 blue dot

} def

100 150 100 250 200 250 200 150 25 doublecurve

300 250 360 250 400 210 400 150 25 doublecurve

100 350 150 350 200 400 250 450 25 doublecurve

300 350 400 350 400 450 500 450 25 doublecurve

showpage

`);

Let's try Tiller and Hanson, if the offsetting legs is getting better results. Lines are not really better and there is an ugly edge case if the leg line is parallel to the angle of the two control points.

Javascript Editor

rpnPostScriptEditor(`
10 dict begin /transparent 0 def /height 600 def /console 0 def currentdict setpagedevice end
/dot {  4 0 360 arc fill } def
/red { 1 0 0 setrgbcolor 1 setalpha } def
/blue { 0 0 1 setrgbcolor 1 setalpha } def
/black { 0 0 0 setrgbcolor 1 setalpha } def
/gray { 0.5 0.5 0.5 setrgbcolor 0.3 setalpha } def

/lineintersection { 10 dict begin
/y4 exch def /x4 exch def /y3 exch def /x3 exch def
/y2 exch def /x2 exch def /y1 exch def /x1 exch def
/denom x1 x2 sub y3 y4 sub mul y1 y2 sub x3 x4 sub mul sub def
denom {
/nom1 x1 y2 mul y1 x2 mul sub def
/nom2 x3 y4 mul y3 x4 mul sub def
/x nom1 x3 x4 sub mul nom2 x1 x2 sub mul sub denom div def
/y nom1 y3 y4 sub mul nom2 y1 y2 sub mul sub denom div def
x y
} { 0 0 } ifelse 
end } def

/doublecurve { /d exch def /y exch def /x exch def /qy exch def /qx exch def /py exch def /px exch def /cy exch def /cx exch def

/pa py cy sub px cx sub atan def
/cx0 pa 90 add cos d mul cx add def
/cy0 pa 90 add sin d mul cy add def
/cx0e pa 90 add cos d mul px add def
/cy0e pa 90 add sin d mul py add def
/cx1 pa 90 sub cos d mul cx add def
/cy1 pa 90 sub sin d mul cy add def
/cx1e pa 90 sub cos d mul px add def
/cy1e pa 90 sub sin d mul py add def

/qa y qy sub x qx sub atan def 
/x0 qa 90 add cos d mul x add def
/y0 qa 90 add sin d mul y add def
/x0e qa 90 add cos d mul qx add def
/y0e qa 90 add sin d mul qy add def
/x1 qa 90 sub cos d mul x add def
/y1 qa 90 sub sin d mul y add def
/x1e qa 90 sub cos d mul qx add def
/y1e qa 90 sub sin d mul qy add def

/ma qy py sub qx px sub atan def
/px00 ma 90 add cos d mul px add def
/py00 ma 90 add sin d mul py add def
/qx00 ma 90 add cos d mul qx add def
/qy00 ma 90 add sin d mul qy add def
/px10 ma 90 sub cos d mul px add def 
/py10 ma 90 sub sin d mul py add def
/qx10 ma 90 sub cos d mul qx add def
/qy10 ma 90 sub sin d mul qy add def

cx0 cy0 cx0e cy0e px00 py00 qx00 qy00 lineintersection
/py0 exch def /px0 exch def 
x0 y0 x0e y0e px00 py00 qx00 qy00 lineintersection
/qy0 exch def /qx0 exch def  
cx1 cy1 cx1e cy1e px10 py10 qx10 qy10 lineintersection
/py1 exch def /px1 exch def 
x1 y1 x1e y1e px10 py10 qx10 qy10 lineintersection
/qy1 exch def /qx1 exch def

cx0 cy0 moveto px0 py0 qx0 qy0 x0 y0 curveto 
x1 y1 lineto qx1 qy1 px1 py1 cx1 cy1 curveto
cx0 cy0 lineto gray fill

cx cy black dot
px py black dot
qx qy black dot
x y black dot

cx0 cy0 red dot
cx0e cy0e red dot
cx0 cy0 moveto cx0e cy0e lineto red stroke
px00 py00 red dot
qx00 qy00 red dot
px00 py00 moveto qx00 qy00 lineto red stroke
x0 y0 red dot
x0e y0e red dot
x0 y0 moveto x0e y0e lineto red stroke
px0 py0 red dot
qx0 qy0 red dot

cx1 cy1 blue dot
cx1e cy1e blue dot
cx1 cy1 moveto cx1e cy1e lineto blue stroke
px10 py10 blue dot
qx10 qy10 blue dot
px10 py10 moveto qx10 qy10 lineto blue stroke
x1 y1 blue dot  
x1e y1e blue dot  
x1 y1 moveto x1e y1e lineto blue stroke
px1 py1 blue dot
qx1 qy1 blue dot

cx cy moveto px py qx qy x y curveto black stroke
cx0 cy0 moveto px0 py0 qx0 qy0 x0 y0 curveto red stroke
cx1 cy1 moveto px1 py1 qx1 qy1 x1 y1 curveto blue stroke
} def

100 150 100 250 200 250 200 150 25 doublecurve

300 250 360 250 400 210 400 150 25 doublecurve

100 350 150 350 200 400 250 450 25 doublecurve

300 350 400 350 400 450 500 450 25 doublecurve

showpage

`);

So we stay with our first method and define a rounded pen, that is a stroke with rounded ends and even straight lines.

Javascript Editor

rpnPostScriptEditor(`

10 dict begin /transparent 0 def /height 600 def  currentdict setpagedevice end
/dot {  4 0 360 arc fill 
} def
/red { 1 0 0 setrgbcolor 1 setalpha } def
/blue { 0 0 1 setrgbcolor 1 setalpha } def
/black { 0 0 0 setrgbcolor 1 setalpha } def
/gray { 0.5 0.5 0.5 setrgbcolor 0.3 setalpha } def

/doublecurve { 64 dict begin
/d exch def /y exch def /x exch def /qy exch def /qx exch def /py exch def /px exch def /cy exch def /cx exch def

/mx cx px 3 mul add qx 3 mul add x add 8 div def
/my cy py 3 mul add qy 3 mul add y add 8 div def

/pa py cy sub px cx sub atan def
/cx0 pa 90 add cos d mul cx add def
/cy0 pa 90 add sin d mul cy add def
/cx1 pa 90 sub cos d mul cx add def
/cy1 pa 90 sub sin d mul cy add def

/qa y qy sub x qx sub atan def 
/x0 qa 90 add cos d mul x add def
/y0 qa 90 add sin d mul y add def
/x1 qa 90 sub cos d mul x add def
/y1 qa 90 sub sin d mul y add def

/ma qy py sub qx px sub atan 90 add def
/mx0 mx ma cos d mul add def
/my0 my ma sin d mul add def
/mx1 mx ma cos d mul sub def
/my1 my ma sin d mul sub def

/f 0.552284749831 def
/sx cx pa 180 add cos d mul add def
/sy cy pa 180 add sin d mul add def
/sp0x sx pa 90 add cos d mul f mul add def
/sp0y sy pa 90 add sin d mul f mul add def 
/sp1x sx pa 90 sub cos d mul f mul add def
/sp1y sy pa 90 sub sin d mul f mul add def
/sq0x cx0 pa 180 add cos d mul f mul add def
/sq0y cy0 pa 180 add sin d mul f mul add def   
/sq1x cx1 pa 180 add cos d mul f mul add def
/sq1y cy1 pa 180 add sin d mul f mul add def        
sx sy black dot
sp0x sp0y black dot
sp1x sp1y black dot
sq0x sq0y black dot
sq1x sq1y black dot

/ex x qa cos d mul add def
/ey y qa sin d mul add def
/ep0x ex qa 90 add cos d mul f mul add def
/ep0y ey qa 90 add sin d mul f mul add def 
/ep1x ex qa 90 sub cos d mul f mul add def
/ep1y ey qa 90 sub sin d mul f mul add def
/eq0x x0 qa cos d mul f mul add def
/eq0y y0 qa sin d mul f mul add def   
/eq1x x1 qa cos d mul f mul add def
/eq1y y1 qa sin d mul f mul add def        
ex ey black dot
ep0x ep0y black dot
ep1x ep1y black dot
eq0x eq0y black dot
eq1x eq1y black dot

cx0 cy0 moveto px0 py0 qx0 qy0 x0 y0 curveto 
eq0x eq0y ep0x ep0y ex ey curveto 
ep1x ep1y eq1x eq1y x1 y1 curveto
qx1 qy1 px1 py1 cx1 cy1 curveto
sq1x sq1y sp1x sp1y sx sy curveto
sp0x sp0y sq0x sq0y cx0 cy0 curveto gray fill

cx cy moveto px py qx qy x y curveto black stroke
cx0 cy0 moveto px0 py0 qx0 qy0 x0 y0 curveto red stroke 
cx1 cy1 moveto px1 py1 qx1 qy1 x1 y1 curveto blue stroke

end

} def

/pencurveto { 10 dict begin /d exch def /y exch def /x exch def /qy exch def /qx exch def /py exch def /px exch def
currentpoint px py qx qy x y d doublecurve end } def

/penlineto { 10 dict begin /d exch def /y exch def /x exch def
currentpoint x y currentpoint x y d doublecurve end } def

100 150 moveto 100 250 200 250 200 150 25 pencurveto

300 250 moveto 360 250 400 210 400 150 25 pencurveto

100 350 moveto 150 350 200 400 250 450 25 pencurveto

300 350 moveto 400 350 400 450 500 450 25 pencurveto

100 500 moveto 300 550 25 penlineto

showpage

`);

Having this, we can define glyphs of a simple rounded font

Javascript Editor

rpnPostScriptEditor(`

10 dict begin /transparent 0 def /height 600 def  currentdict setpagedevice end

/doublecurve { 64 dict begin
/d exch def /y exch def /x exch def /qy exch def /qx exch def /py exch def /px exch def /cy exch def /cx exch def

/mx cx px 3 mul add qx 3 mul add x add 8 div def
/my cy py 3 mul add qy 3 mul add y add 8 div def

/pa py cy sub px cx sub atan def
/cx0 pa 90 add cos d mul cx add def
/cy0 pa 90 add sin d mul cy add def
/cx1 pa 90 sub cos d mul cx add def
/cy1 pa 90 sub sin d mul cy add def

/qa y qy sub x qx sub atan def 
/x0 qa 90 add cos d mul x add def
/y0 qa 90 add sin d mul y add def
/x1 qa 90 sub cos d mul x add def
/y1 qa 90 sub sin d mul y add def

/ma qy py sub qx px sub atan 90 add def
/mx0 mx ma cos d mul add def
/my0 my ma sin d mul add def
/mx1 mx ma cos d mul sub def
/my1 my ma sin d mul sub def

end

} def

/pencurveto { 10 dict begin /y exch def /x exch def /qy exch def /qx exch def /py exch def /px exch def
currentpoint px py qx qy x y currentlinewidth doublecurve x y moveto end } def

/penlineto { 10 dict begin /y exch def /x exch def
currentpoint x y currentpoint x y currentlinewidth doublecurve x y moveto end } def

5 setlinewidth 
%A 
20 500 translate
0 0 moveto 30 80 penlineto 60 0 penlineto 
15 30 moveto 45 30 penlineto fill
80 0 translate
%B
0 0 moveto 0 80 penlineto 
20 80 penlineto 31 80 40 73 40 60 pencurveto
40 51 31 42 20 42 pencurveto 0 42 penlineto
20 42 penlineto 31 42 40 31 40 20 pencurveto
40  9 31  0 22  0 pencurveto 0 0 penlineto
60 0 translate
%C
00 20 moveto 00 60 penlineto
00 72 08 80 20 80 pencurveto
32 80 40 72 40 60 pencurveto
40 20 moveto
40 08 32 00 20 00 pencurveto
08 00 00 08 00 20 pencurveto
60 0 translate
%D
0 0 moveto 0 80 penlineto 
20 80 penlineto 
32 80 40 68 40 60 pencurveto 40 20 penlineto
40 08 32 00 20 00 pencurveto 00 00 penlineto 
60 0 translate
%E
0 0 moveto 0 80 penlineto 40 80 penlineto 
0 42 moveto 35 42 penlineto
0 0 moveto 40 0 penlineto
60 0 translate
%F
0 0 moveto 0 80 penlineto 40 80 penlineto 
0 42 moveto 35 42 penlineto
60 0 translate
%G
00 20 moveto 00 60 penlineto
00 72 08 80 20 80 pencurveto
32 80 40 72 40 60 pencurveto
20 40 moveto 40 40 penlineto 40 20 penlineto
40 08 32 00 20 00 pencurveto
08 00 00 08 00 20 pencurveto 
60 0 translate
%F
0 0 moveto 0 80 penlineto
0 42 moveto 40 42 penlineto
40 0 moveto 40 80 penlineto
80 0 translate
-510 -100 translate
%I
0 0 moveto 0 80 penlineto
30 0 translate
%J
00 20 moveto 00 08 12 00 20 00 pencurveto
32 00 40 08 40 20 pencurveto 40 80 penlineto
60 0 translate
%K
0 0 moveto 0 80 penlineto
40 80 moveto 5 42 penlineto 40 0 penlineto
60 0 translate
%L
0 80 moveto 0 0 penlineto 40 0 penlineto
60 0 translate
%M
0 0 moveto 0 80 penlineto 30 0 penlineto 60 80 penlineto 60 0 penlineto
90 0 translate
%N
0 0 moveto 0 80 penlineto 40 0 penlineto 40 80 penlineto 
60 0 translate
%0
00 20 moveto 00 60 penlineto
00 72 08 81 20 81 pencurveto
32 81 40 72 40 60 pencurveto
40 20 penlineto
40 08 32 -01 20 -01 pencurveto
08 -01 00 08 00 20 pencurveto
60 0 translate
%P
0 0 moveto 0 80 penlineto 
20 80 penlineto 31 80 40 73 40 60 pencurveto
40 51 31 42 20 42 pencurveto 0 42 penlineto
60 0 translate
%Q
00 20 moveto 00 60 penlineto
00 72 08 81 20 81 pencurveto
32 81 40 72 40 60 pencurveto
40 20 penlineto
40 08 32 -01 20 -01 pencurveto
08 -01 00 08 00 20 pencurveto
25 15 moveto 40 0 penlineto
80 0 translate
-560 -100 translate
%R
0 0 moveto 0 80 penlineto 
20 80 penlineto 31 80 40 73 40 60 pencurveto
40 51 31 42 20 42 pencurveto 5 42 penlineto
10 42 moveto
40 0 penlineto
60 0 translate
%S
0 20 moveto 
0 08 12 -01 20 -01 pencurveto
32 -01 40 8 40 20 pencurveto
40 32 28 40 20 40 pencurveto
12 40 0 48 0 60 pencurveto
0 72 8 81 20 81 pencurveto
32 81 40 68 40 60 pencurveto
60 0 translate
%T 
0 80 moveto 50 80 penlineto
25 80 moveto 25 0 penlineto
70 0 translate
%U
0 80 moveto 0 20 penlineto
0 8 12 0 20 0 pencurveto
32 0 40 8 40 20 pencurveto
40 80 penlineto
60 0 translate
%V
0 80 moveto 20 0 penlineto 40 80 penlineto
60 0 translate
%W
0 80 moveto 18 0 penlineto 35 80 penlineto
52 0 penlineto 70 80 penlineto
90 0 translate
%X
0 80 moveto 40 0 penlineto 
0 0 moveto 40 80 penlineto
60 0 translate
%X
0 80 moveto 20 40 penlineto 40 80 penlineto
20 40 moveto 20 0 penlineto
60 0 translate
-520 -100 translate
%Z
0 80 moveto 40 80 penlineto 0 0 penlineto 40 0 penlineto
60 0 translate
%1
20 60 moveto 40 80 penlineto 40 0 penlineto 
60 0 translate
%2
0 60 moveto 0 72 08 80 20 80 pencurveto 
32 80 40 72 40 60 pencurveto
40 48 32 38 20 31 pencurveto
08 31 00 18 00 10 pencurveto
00 00 penlineto
40 00 penlineto
60 00 translate
%3
0 60 moveto 0 71 8 80 20 80 pencurveto 
32 80 40 71 40 60 pencurveto
40 48 24 42 20 42 pencurveto
28 42 40 28 40 20 pencurveto
40 08 32 00 20 00 pencurveto
08 00 00 08 00 20 pencurveto
60 0 translate
%4
30 80 moveto 00 35 penlineto 40 35 penlineto
30 80 moveto 30 0 penlineto
60 0 translate
%5 
40 80 moveto 0 80 penlineto 0 45 penlineto
20 45 penlineto 32 45 40 28 40 20 pencurveto
40 08 32 00 20 00 pencurveto
08 00 00 08 00 20 pencurveto
60 0 translate
%6
40 60 moveto 40 72 32 80 20 80 pencurveto
08 80 00 72 00 60 pencurveto 0 20 penlineto
00 08 08 00 20 00 pencurveto
32 00 40 08 40 20 pencurveto
40 32 32 42 20 42 pencurveto
08 42 00 32 00 20 pencurveto
60 0 translate
%7 
00 80 moveto 40 80 penlineto 00 00 penlineto
60 00 translate
%8
20 42 moveto 
08 42 00 52 00 60 pencurveto
00 72 08 80 20 80 pencurveto
28 80 40 72 40 60 pencurveto
40 48 32 42 20 42 pencurveto
08 42 00 28 00 20 pencurveto
00 08 08 00 20 00 pencurveto
32 00 40 08 40 20 pencurveto
40 32 32 42 20 42 pencurveto
60 0 translate
-540 -100 translate
%9
40 60 moveto 
40 72 32 80 20 80 pencurveto
08 80 00 72 00 60 pencurveto
00 48 08 38 20 38 pencurveto
32 38 40 48 40 60 pencurveto
40 20 penlineto
40 08 32 00 20 00 pencurveto
08 00 00 08 00 20 pencurveto
60 0 translate
%0 translate
00 20 moveto 00 60 penlineto
00 72 08 80 20 80 pencurveto
32 80 40 72 40 60 pencurveto
40 20 penlineto
40 08 32 00 20 00 pencurveto
08 00 00 08 00 20 pencurveto

fill
showpage

`);

My Journey to PostScript