Addition of Bezier curves

[bvenn]

Description

Bezier curves can be found in sketching software, optimization algorithms and game/movie animations. A curve is drawn between two points that is controlled by m ={1,2,3 .. } control points. If m=1 the resulting curve is quadratic, m=2 results in cubic curves etc.. Nested LERPs are used to identify the desired y-value from an given x value.

Quadratic:

Cubic:

Fourth-order curve:

De Casteljau's algorithm allows the efficient calculation of these curves.

Pointers

• The implementation should take collections of x and y values and may return a function that takes an x value of which the corresponding y value should be predicted.
• Note that the first and last x,y tuple are the points that are interpolated.
• The degree of the resulting curve can be easily inferred from the number of x,y coordinates present in the input data
  • if xValues.Length = 4, the first and last point mark the start and end of the curve, while the internal two points serve as control points, leading the resulting curve to be cubic (n-1).
• Attention: In computer graphics the x coordinate is often used as t, that describes the percentage of traversal. You can add two separate functions, that either takes x (bezier) or t (bezierFromPercentage).

• let bezier (xValues: float [] <or any other appropriate collection type>) (yValues: float []): (float -> float) =
      fun x -> 
         // iteratively LERP the points until you end up with the final y coordinate for the given x coordinate

• There are several pseudocode examples and implementations that you can use as coding hint!
• I think the bezier function would best fit here (but of course you can first develop in notebooks and we assist in in coorperate it into FSharp.Stats):

  FSharp.Stats/src/FSharp.Stats/Interpolation.fs

  Line 2304 in 8fb5d6d
• Note the following example works, but is limited to cubic bezier curves. If you want to use it, you have to generalize it to work on collections of any length (recursion).

#r "nuget: Plotly.NET.Interactive, 4.2.1"
#r "nuget: FSharp.Stats, 0.5.0"

open Plotly.NET
open Plotly.NET.StyleParam
open FSharp.Stats

let t = 0.3
let p0 = vector [|1.;1.|] //point 0 that should be traversed
let c0 = vector [|1.1;2.1|] //control point 0
let c1 = vector [|3.8;1.6|] //control point 1
let p1 = vector [|3.;2.|] //point 1 that should be traversed

let lerp (p1: vector) (p2: vector) (t: float) = 
    p1 + t * (p2 - p1)

let a = lerp p0 c0 t
let b = lerp c0 c1 t
let c = lerp c1 p1 t
let d = lerp a b t
let e = lerp b c t
let f = lerp d e t

let assemble t = 
    let a = lerp p0 c0 t
    let b = lerp c0 c1 t
    let c = lerp c1 p1 t
    let d = lerp a b t
    let e = lerp b c t
    let f = lerp d e t
    f.[0],f.[1]

let chart = 
    [
        Chart.Point([p0.[0]],[p0.[1]],Name="Point_0",MarkerColor=Color.fromHex "#1f77b4") |> Chart.withMarkerStyle(Size=12)
        Chart.Point([c0.[0]],[c0.[1]],Name="Control_0",MarkerColor=Color.fromHex "#ff7f0e")|> Chart.withMarkerStyle(Size=10)
        Chart.Point([c1.[0]],[c1.[1]],Name="Control_1",MarkerColor=Color.fromHex "#ff7f0e")|> Chart.withMarkerStyle(Size=10)
        Chart.Point([p1.[0]],[p1.[1]],Name="Point_1",MarkerColor=Color.fromHex "#1f77b4") |> Chart.withMarkerStyle(Size=12)

        Chart.Line([p0.[0];c0.[0]],[p0.[1];c0.[1]],Name="LERP_A",MarkerColor=Color.fromHex "#919191")
        Chart.Line([c0.[0];c1.[0]],[c0.[1];c1.[1]],Name="LERP_B",MarkerColor=Color.fromHex "#919191")
        Chart.Line([c1.[0];p1.[0]],[c1.[1];p1.[1]],Name="LERP_C",MarkerColor=Color.fromHex "#919191")

        Chart.Point([a.[0]],[a.[1]],Name="A_t",MarkerColor=Color.fromHex "#000000")
        Chart.Point([b.[0]],[b.[1]],Name="B_t",MarkerColor=Color.fromHex "#000000")
        Chart.Point([c.[0]],[c.[1]],Name="C_t",MarkerColor=Color.fromHex "#000000")

        Chart.Line([a.[0];b.[0]],[a.[1];b.[1]],Name="LERP_D",MarkerColor=Color.fromHex "#5d5d5d")
        Chart.Line([b.[0];c.[0]],[b.[1];c.[1]],Name="LERP_E",MarkerColor=Color.fromHex "#5d5d5d")
        
        Chart.Point([d.[0]],[d.[1]],Name="D_t",MarkerColor=Color.fromHex "#000000")
        Chart.Point([e.[0]],[e.[1]],Name="E_t",MarkerColor=Color.fromHex "#000000")

        Chart.Line([d.[0];e.[0]],[d.[1];e.[1]],Name="LERP_F",MarkerColor=Color.fromHex "#292929")

        Chart.Point([f.[0]],[f.[1]],Name="F_t",MarkerColor=Color.fromHex "#1f77b4") |> Chart.withMarkerStyle(Size=12)

        [0. .. 0.01 .. 0.3] |> List.map (fun t -> assemble t) |> Chart.Line |> Chart.withTraceInfo "Bezier" |> Chart.withLineStyle(Color=Color.fromHex "#1f77b4",Width=4.)
    ]
    |> Chart.combine
    |> Chart.withTemplate ChartTemplates.lightMirrored
    |> Chart.show

References

• [1] Youtube - The Continuity of Splines <- impressive visual presentation of bezier curves
• [2] LMU - cg1-tutorial-3-geometry slide 17
• [3] De Casteljau algorithm

Hints (click to expand if you need additional pointers)

• To be able to contribute to this library you'll need

  • an GitHub account
  • an IDE like Visual Studio Community or Visual Studio Code
  • dotnet 6 sdk

• to build the binaries yourself follow the instructions

• while working on the FSharp.Stats documentation (any file within https://github.com/fslaborg/FSharp.Stats/tree/developer/docs) you can navigate to the project folder with a prompt of your choice and use the command ./build watchdocs

• unit tests can be executed via ./build runtests

• 3D example

let t = 0.3
let p0 = vector [|1.;1.;1.|] //point 0 that should be traversed
let c0 = vector [|1.1;2.1;2.|] //control point 0
let c1 = vector [|3.8;1.6;1.4|] //control point 1
let p1 = vector [|3.;2.;0.|] //point 1 that should be traversed

let lerp (p1: vector) (p2: vector) (t: float) = 
    p1 + t * (p2 - p1)

let a = lerp p0 c0 t
let b = lerp c0 c1 t
let c = lerp c1 p1 t

let d = lerp a b t
let e = lerp b c t

let f = lerp d e t

let assemble t = 
    let a = lerp p0 c0 t
    let b = lerp c0 c1 t
    let c = lerp c1 p1 t
    let d = lerp a b t
    let e = lerp b c t
    let f = lerp d e t
    f.[0],f.[1],f.[2]

let chart = 
    [
        Chart.Point3D([p0.[0]],[p0.[1]],[p0.[2]],Name="Point_0",MarkerColor=Color.fromHex "#1f77b4") |> Chart.withMarkerStyle(Size=12)
        Chart.Point3D([c0.[0]],[c0.[1]],[c0.[2]],Name="Control_0",MarkerColor=Color.fromHex "#ff7f0e")|> Chart.withMarkerStyle(Size=10)
        Chart.Point3D([c1.[0]],[c1.[1]],[c1.[2]],Name="Control_1",MarkerColor=Color.fromHex "#ff7f0e")|> Chart.withMarkerStyle(Size=10)
        Chart.Point3D([p1.[0]],[p1.[1]],[p1.[2]],Name="Point_1",MarkerColor=Color.fromHex "#1f77b4") |> Chart.withMarkerStyle(Size=12)

        Chart.Line3D([p0.[0],p0.[1],p0.[2];c0.[0],c0.[1],c0.[2]],Name="LERP_A",MarkerColor=Color.fromHex "#919191")
        Chart.Line3D([c0.[0],c0.[1],c0.[2];c1.[0],c1.[1],c1.[2]],Name="LERP_B",MarkerColor=Color.fromHex "#919191")
        Chart.Line3D([c1.[0],c1.[1],c1.[2];p0.[1],p1.[1],p1.[2]],Name="LERP_C",MarkerColor=Color.fromHex "#919191")

        Chart.Point3D([a.[0]],[a.[1]],[a.[2]],Name="A_t",MarkerColor=Color.fromHex "#000000")
        Chart.Point3D([b.[0]],[b.[1]],[b.[2]],Name="B_t",MarkerColor=Color.fromHex "#000000")
        Chart.Point3D([c.[0]],[c.[1]],[c.[2]],Name="C_t",MarkerColor=Color.fromHex "#000000")

        Chart.Line3D([a.[0],a.[1],a.[2];b.[0],b.[1],b.[2]],Name="LERP_D",MarkerColor=Color.fromHex "#5d5d5d")
        Chart.Line3D([b.[0],b.[1],b.[2];c.[0],c.[1],c.[2]],Name="LERP_E",MarkerColor=Color.fromHex "#5d5d5d")
        
        Chart.Point3D([d.[0]],[d.[1]],[d.[2]],Name="D_t",MarkerColor=Color.fromHex "#000000")
        Chart.Point3D([e.[0]],[e.[1]],[e.[2]],Name="E_t",MarkerColor=Color.fromHex "#000000")

        Chart.Line3D([d.[0],d.[1],d.[2];e.[0],e.[1],e.[2]],Name="LERP_F",MarkerColor=Color.fromHex "#292929")

        Chart.Point3D([f.[0]],[f.[1]],[f.[2]],Name="F_t",MarkerColor=Color.fromHex "#1f77b4") |> Chart.withMarkerStyle(Size=12)

        [0. .. 0.01 .. 0.3] |> List.map (fun t -> assemble t) |> Chart.Line3D |> Chart.withTraceInfo "Bezier" |> Chart.withLineStyle(Color=Color.fromHex "#1f77b4",Width=10.)
    ]
    |> Chart.combine
    |> Chart.withTemplate ChartTemplates.lightMirrored
    |> Chart.show

[pirrmann]

I'm interested by this issue, is someone else going to work on that today?