lambdaway :: decasteljau2

6 | list | login |load

| |

_img http://epsilonwiki.free.fr/epsilonwiki/data/elan.png

{require lib_list}

_h1 de casteljau ( [[array|?view=decasteljau]] | list1 | [[list2|?view=decasteljau3]] )

_p This is a first list based version equivalent to the array version.
  
_p A [[Bézier curve|https://www.scratchapixel.com/lessons/advanced-rendering/bezier-curve-rendering-utah-teapot]] 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 [p1 p2 p3 p4]} 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]
}

_p This process is recursively done on the left and right control polygons {b [p1 q1 r1 s1]} and {b [s1 r2 q3 p4]}. The depth of recursion is controlled either by a "flatness/smoothness" condition 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.

_p The main function is {b '{CASTEL.blossom pol n}} which returns a level {b n} binary tree of control polygons, {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 '{tree2svg 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 are stored in a library page in order to be used everywhere in the wiki via a {b require} command. Points are defined as pairs and polygons as lists.

{prewrap {L.lib} }

{prewrap
'{def CASTEL.interpol {lambda {:p0 :p1 :t}
  {P.new {+ {* {P.left :p0} {- 1 :t}} {* {P.left :p1} :t}}
         {+ {* {P.right :p0} {- 1 :t}} {* {P.right :p1} :t}} } }} 
-> {def CASTEL.interpol {lambda {:p0 :p1 :t}
  {P.new {+ {* {P.left :p0} {- 1 :t}}
            {* {P.left :p1} :t}}
         {+ {* {P.right :p0} {- 1 :t}}
            {* {P.right :p1} :t}} } }}

'{def CASTEL.sub {lambda {:l :acc :t}
  {if {< {L.length :l} 2}
   then :acc
   else {CASTEL.sub
         {L.rest :l} 
         {L.concat :acc 
                   {L.new {CASTEL.interpol
                               {L.first :arr}
                               {L.first {L.rest :l}} :t}} } :t} }}} 
-> {def CASTEL.sub {lambda {:arr :acc :t}
  {if {< {L.length :arr} 2}
   then :acc
   else {CASTEL.sub
         {L.rest :arr} 
         {L.concat :acc {L.new {CASTEL.interpol {L.first :arr}
                                      {L.first {L.rest :arr}} :t}} } :t} }}}

'{def CASTEL.split {lambda {:l :acc :t :lr}
  {if {< {L.length :l} 1}
   then :acc
   else {CASTEL.split
         {CASTEL.sub :l nil :t}
         {if :lr
          then {L.concat :acc {L.new {L.first :l}}}
          else {L.concat {L.new {L.last :l}} :acc}} :t :lr} }}} 
-> {def CASTEL.split {lambda {:arr :acc :t :lr}
  {if {< {L.length :arr} 1}
   then :acc
   else {CASTEL.split
         {CASTEL.sub :arr nil :t}
         {if :lr
          then {L.concat :acc {L.new {L.first :arr}}}
          else {L.concat {L.new {L.last :arr}} :acc}} :t :lr} }}}

'{def CASTEL.stretch {lambda {:l :t0 :t1}
  {CASTEL.split
   {CASTEL.split :l nil :t0 false} nil :t1 true}}}
-> {def CASTEL.stretch {lambda {:arr :t0 :t1}
  {CASTEL.split
   {CASTEL.split :arr nil :t0 false} nil :t1 true}}}

'{def CASTEL.blossom {lambda {:l :n}
  {if {< :n 1}
   then {L.disp :l}
   else
    {L.disp {CASTEL.blossom {CASTEL.split :l nil 0.5 true} {- :n 1}}}
    {L.disp {CASTEL.blossom {CASTEL.split :l nil 0.5 false} {- :n 1}}} }}}
-> {def CASTEL.blossom {lambda {:arr :n}
  {if {< :n 1}
   then {L.disp :arr}
   else  {L.disp {CASTEL.blossom {CASTEL.split :arr nil 0.5 true} {- :n 1}}}
         {L.disp {CASTEL.blossom {CASTEL.split :arr nil 0.5 false} {- :n 1}}} }}}
}

_p SVG related functions 
  
{pre

'{def tree2svg
 {lambda {:l}
  {S.map {lambda {:p} {P.left :p} {P.right :p}}
         {S.replace \(|\) by in :l}}}}
-> {def tree2svg
 {lambda {:arr}
  {S.map {lambda {:p} {P.left :p} {P.right :p}} {S.replace \(|\) by in :arr}}}}

'{def svg.frame
 {lambda {:w :h}
  svg {@ width=":w" height=":h" 
    style="border:1px solid #888; box-shadow:0 0 8px;"}}}
-> {def svg.frame
 {lambda {:w :h}
  svg {@ width=":w" height=":h" 
    style="border:1px solid #888; box-shadow:0 0 8px;"}}}

'{def svg.stroke
 {lambda {:c :e}
  stroke=":c" stroke-width=":e" fill="transparent"}}
-> {def svg.stroke
 {lambda {:c :e}
  stroke=":c" stroke-width=":e" fill="transparent"}}

'{def svg.dot
 {lambda {:p}
  {circle {@ cx="{P.left :p}" cy="{P.right :p}" r="5" 
             {svg.stroke #000 3}}} }}
-> {def svg.dot
 {lambda {:p}
  {circle {@ cx="{P.left :p}" cy="{P.right :p}" r="5" 
             {svg.stroke #000 3}}} }}
}

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

{pre
{def p0 {P.new 50 60}} -> {p0}
{def p1 {P.new 100 200}} -> {p1}
{def p2 {P.new 300 200}} -> {p2}
{def p3 {P.new 200 280}} -> {p3}

'{{svg.frame 320 320}
{polyline {@ points="{tree2svg
 {CASTEL.blossom {L.new {p0} {p1} {p2} {p3}} 3}}"
 {svg.stroke #f00 12} }}
{polyline {@ points="{tree2svg
 {CASTEL.blossom {L.new {p0} {p1} {p2} {p3}} 0}}"
 {svg.stroke #888 1} }}
{polyline {@ points="{tree2svg
 {CASTEL.blossom
 {CASTEL.stretch {L.new {p0} {p1} {p2} {p3}} 0.25 0.85} 3}}"
 {svg.stroke #ff0 5}}}
{polyline {@ points="{tree2svg
 {CASTEL.blossom
 {CASTEL.stretch {L.new {p0} {p1} {p2} {p3}}  -0.1 1.1} 4}}"
 {svg.stroke #888 2}}}
{polyline {@ points="{tree2svg
 {CASTEL.blossom
 {CASTEL.stretch {L.new {p1} {p0} {p2} {p3}}  -0.1 1.1} 4}}"
 {svg.stroke #888 2}}}
{polyline {@ points="{tree2svg
 {CASTEL.blossom
 {CASTEL.stretch {L.new {p0} {p1} {p3} {p2}}  -0.1 1.1} 4}}"
 {svg.stroke #888 2}}}
{polyline {@ points="{tree2svg
 {CASTEL.blossom
 {CASTEL.stretch {L.new {p0} {p2} {p1} {p3}}  -0.1 1.1} 4}}"
 {svg.stroke #888 2}}}
{svg.dot {p0}} {svg.dot {p1}} {svg.dot {p2}} {svg.dot {p3}}
}
}
   
{center {{svg.frame 320 320} 
{polyline {@ points="{tree2svg {CASTEL.blossom {L.new {p0} {p1} {p2} {p3}} 3}}" {svg.stroke #f00 12} }}
{polyline {@ points="{tree2svg {CASTEL.blossom {L.new {p0} {p1} {p2} {p3}} 0}}" {svg.stroke #888 1} }}
{polyline {@ points="{tree2svg {CASTEL.blossom {CASTEL.stretch {L.new {p0} {p1} {p2} {p3}} 0.25 0.85} 3}}" {svg.stroke #ff0 5}}}
{polyline {@ points="{tree2svg {CASTEL.blossom {CASTEL.stretch {L.new {p0} {p1} {p2} {p3}}  -0.1 1.1} 3}}" {svg.stroke #888 2}}}
{polyline {@ points="{tree2svg {CASTEL.blossom {CASTEL.stretch {L.new {p1} {p0} {p2} {p3}}  -0.1 1.1} 3}}" {svg.stroke #888 2}}}
{polyline {@ points="{tree2svg {CASTEL.blossom {CASTEL.stretch {L.new {p0} {p1} {p3} {p2}}  -0.1 1.1} 4}}" {svg.stroke #888 2}}}
{polyline {@ points="{tree2svg {CASTEL.blossom {CASTEL.stretch {L.new {p0} {p2} {p1} {p3}}  -0.1 1.1} 4}}" {svg.stroke #888 2}}}
{svg.dot {p0}} {svg.dot {p1}} {svg.dot {p2}} {svg.dot {p3}}
}}