lambdaspeech :: decasteljau

_h1 de casteljau 1 | [[2|?view=decasteljau2]] | [[3|?view=decasteljau3]] | [[4|?view=decasteljau4]] |

{svg
 {@ width="100%" height="300" style="background:#eee"}
 {polyline
  {@ points="{#.2svg {curve}}" 
     stroke="#f00" stroke-width="9" fill="transparent"}}
 {polyline
  {@ points="{#.2svg {scurve}}" 
     stroke="#aaa" stroke-width="3" fill="transparent"}}
 {polyline
  {@ points="{#.2svg {pol}}" 
     stroke="#888" stroke-width="1" fill="transparent"}} 
}

{p A {a {@ href="https://www.scratchapixel.com/lessons/advanced-rendering/bezier-curve-rendering-utah-teapot"}Bézier curve} is defined by a set of control points, {b [p0 p1  ... pn]}. The de Casteljau’s algorithm takes the control points and finds the midpoints along each line, then joins these midpoints. After that, it takes the midpoints along the newly drawn lines and finds the midpoints again, then draws a line connecting these. By doing this until we are down to only one point, we can approximate the Bézier curve. This is a schema of the de Casteljau algorithm for a cubic curve controled by 4 points {b [p0 p1 p2 p3]} and leading to the point at t=1/2:}

{pre
.     [{b p0}  p1  p2  {b p3}]     the control polygon
        [{b q0}  q1  {b q2}]       q{sub i} = (p{sub i}+p{sub i+1})/2  i in [0,1,2]
          [{b r0}  {b r1}]         r{sub i} = (q{sub i}+q{sub i+1})/2  i in [0,1]
            [{b s0}]           s{sub 1} = (r{sub i}+r{sub i+1})/2  i in [0]
}

{img {@ src="https://www.scratchapixel.com/images/upload/bezier/decasteljau.gif" width="100%"}}

{p This process is recursively done on the left and right control polygons {b [p0 q0 r0 s0]} and {b [s0 r1 q2 p3]}. The depth of recursion is controlled either by a "flatness/smoothness" condition, see [[adaptative_bezier]], or by a number, the choice taken in this page. The result is a {b binary tree} of polygon controls translated in a sequence of points, {b x0 y0 x1 y1 .... xp yp}, expected by the SVG polyline's {b points:"..."} attribute.}

{h3 details of the implementation}

{p The main function is {b '{CASTEL.blossom pol n}} which returns a level {b n} binary tree of polygon controls, {b [[x0,y0],...,[xp,yp]]}. The curve is defined in the interval {b [0,1]}. The second {b '{CASTEL.stretch pol t0 t1}} function returns a new equivalent control polygon stretched to any other interval {b [t0,t1]}. In order to display the curve, we define a third {b '{array.2svg pol}} function replacing the 3 characters {b "[",",","]"} by spaces in the array expression of the control polygon and returning a sequence of SVG formated points {b x0 y0 x1 y1 ... xp yp}.}

{p The following lambdatalk functions should be stored in a library page in order to be used everywhere in the wiki via a {b require} command.}

{pre 
'{def CASTEL.interpol
 {lambda {:p0 :p1 :t}
  {#.new {+ {* {#.get :p0 0} {- 1 :t}}
            {* {#.get :p1 0} :t}}
         {+ {* {#.get :p0 1} {- 1 :t}}
            {* {#.get :p1 1} :t}} } 
}}
-> {def CASTEL.interpol {lambda {:p0 :p1 :t}
  {#.new {+ {* {#.get :p0 0} {- 1 :t}}
            {* {#.get :p1 0} :t}}
         {+ {* {#.get :p0 1} {- 1 :t}}
            {* {#.get :p1 1} :t}} } }}

'{def CASTEL.sub
 {lambda {:arr :acc :t}
  {if {< {#.length :arr} 2}
   then :acc
   else {CASTEL.sub
         {#.rest :arr} 
         {#.addlast! :acc
         {CASTEL.interpol {#.get :arr 0}
                          {#.get :arr 1} :t} } :t} }}}
-> {def CASTEL.sub {lambda {:arr :acc :t}
  {if {< {#.length :arr} 2}
   then :acc
   else {CASTEL.sub
         {#.rest :arr} 
         {#.addlast! :acc
         {CASTEL.interpol {#.get :arr 0}
                          {#.get :arr 1} :t} } :t} }}}

'{def CASTEL.split
 {lambda {:arr :acc :t :lr}
  {if {< {#.length :arr} 1}
   then :acc
   else {CASTEL.split
         {CASTEL.sub :arr {#.new} :t}
         {if :lr
          then {#.addlast! :acc {#.first :arr}}
          else {#.addfirst! :acc {#.last :arr}} } :t :lr} }}}
->  {def CASTEL.split {lambda {:arr :acc :t :lr}
  {if {< {#.length :arr} 1}
   then :acc
   else {CASTEL.split
         {CASTEL.sub :arr {#.new} :t}
         {if :lr
          then {#.addlast! :acc {#.first :arr}}
          else {#.addfirst! :acc {#.last :arr}} } :t :lr} }}}

'{def CASTEL.stretch
 {lambda {:arr :t0 :t1}
  {CASTEL.split
   {CASTEL.split :arr {#.new} :t0 right}
                      {#.new} :t1 left}}}
-> {def CASTEL.stretch {lambda {:arr :t0 :t1}
  {CASTEL.split
   {CASTEL.split :arr {#.new} :t0 right}
                      {#.new} :t1 left}}}

'{def CASTEL.blossom
 {lambda {:arr :n}
  {if {< :n 1}
   then :arr
   else {array 
    {CASTEL.blossom {CASTEL.split :arr {array} 0.5 true} {- :n 1}}
    {CASTEL.blossom {CASTEL.split :arr {array} 0.5 false} {- :n 1}}}}}}
-> {def CASTEL.blossom {lambda {:arr :n}
  {if {< :n 1}
   then :arr
   else {#.new {CASTEL.blossom {CASTEL.split :arr {#.new} 0.5 left} {- :n 1}}
               {CASTEL.blossom {CASTEL.split :arr {#.new} 0.5 right} {- :n 1}}
 }}}}

'{def #.2svg
 {lambda {:arr}
  {replace (\[|\]|,) by space in {#.disp :arr}}}}
-> {def #.2svg {lambda {:arr}
  {replace (\[|\]|,) by space in {#.disp :arr}}}}
}

_p Using these functions, we can feed the SVG polyline's points:"..." attributes

{pre
'{def pol
 {#.new {#.new 100 100} {#.new 300 100}
        {#.new 300 0}   {#.new 0 0}
        {#.new 0 300}   {#.new 300 300} 
        {#.new 300 200} {#.new 500 200}}}
'{def curve {CASTEL.blossom {pol} 3}}
'{def scurve {CASTEL.blossom {CASTEL.stretch {pol} -0.05 1.05} 3}}

'{svg
 {@ width="100%" height="300" style="background:#eee"}
 {polyline
  {@ points="{#.2svg {curve}}" 
     stroke="#f00" stroke-width="9" fill="transparent"}}
 {polyline
  {@ points="{#.2svg {scurve}}" 
     stroke="#aaa" stroke-width="3" fill="transparent"}}
 {polyline
  {@ points="{#.2svg {pol}}" 
     stroke="#444" stroke-width="1" fill="transparent"}}
}

}

{{hide}
{def pol 
 {#.new {#.new 100 100} {#.new 300 100}
        {#.new 300 0} {#.new 0 0}
        {#.new 0 300} {#.new 300 300} 
        {#.new 300 200} {#.new 500 200}}}

{def curve {CASTEL.blossom {pol} 3}}

{def scurve {CASTEL.blossom
             {CASTEL.stretch {pol} -0.05 1.05} 3}}
}