Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Bézier Curve Algorithm

Hi everyone,

I need help to solve my uneven Bézier curve plotter, here’s a little explanation:
So I wanted to create a dancing line and started to apply Bernstein polynomial to my code. Although the algorithm is working, I can’t figure it out why my lines are distributed unevenly throughout the whole curve?
How do I make the length even?
Do I need to apply De Casteljau's algorithm?
Below I attached my project and screenshots.

Thank you,
marcelliino

Comments

  • Sorry I forgot to include the code

    function Math:factorial(n)
        f = n
        for i = 1, n-1 do
            f = f * (n-i)
        end
        return f
    end
    
    function Math:binomialCoefficient(n, k)
        if k < 1 or k == n then return 1 else
            return Math:factorial(n)/(Math:factorial(k)*Math:factorial(n-k))
        end
    end
    
    function Math:polynomial(P, n, t)
        B = vec2(0, 0)
        for i = 0, n-1 do
            B = B + Math:binomialCoefficient(n, i) * math.pow(1 - t, n - i) * math.pow(t, i) * P[i]
        end
        B = B + math.pow(t, n) * P[n-1]
        return B
    end
    
  • dave1707dave1707 Mod
    Posts: 7,861

    @marcelliino The zip file doesn't have all the code and pictures of the code can't be included. Post the full code like you did above.

  • dave1707dave1707 Mod
    Posts: 7,861

    @marcelliino Here's a link to some bezier code I wrote awhile back. Scroll down to the last code listing. You have to include Cameras as a dependency.

    https://codea.io/talk/discussion/8560/computer-aided-designs
    
  • Thank you @dave1707 I’ll check that out!

  • edited August 25 Posts: 46

    Hi @marcelliino I have Bezier code I wrote in Codea (see: https://brianolive.github.io/programming/Bezier-Fibonacci-and-Newton/) If you’d like the code, I can post it as soon as I have the chance.

  • Posts: 447

    The lines are distributed unevenly because the standard parameter in a Bezier curve is not an arc-length parameter, so it will travel along the curve at different speeds at different places. Bernstein polynomials "suffer" from the same problem (I put "suffer" in inverted commas because it is questionable as to whether this is actually a drawback). There are various ways to compensate for this, one of which is to make the intervals sufficiently small that no-one notices. The other is to vary the sizes of the parameter steps so that they are more evenly distributed when drawn.

    The first method is only practical if having a high number of steps doesn't slow down the rendering. One way to achieve this is by using a shader to do the drawing since those are much faster than direct drawing commands. Since everyone is sharing their bezier code, here's mine which uses shaders to do the rendering.

    The second method is complicated if done with full accuracy, but with estimates can be done quite quickly. When figuring out the next parameter step, we use the current derivative to estimate the current scaling between the parameter and the actual distance in space.

    So if we're at a point with parameter t_k then the scaling from parameter space to real space is given by the length of the vector b'(t_k), so we divide our desired length, say d, by that to get the next step in parameter space. Hence we set:

    t_{k+1} = t_k + d/|b'(t_k)|
    

    The formula for the derivative is simple as the derivative of a bezier curve of order n is one of order n-1.

  • Posts: 46

    @LoopSpace Do you have some code that showcases your Bezier library?

  • SimeonSimeon Admin Mod
    Posts: 5,054

    @brianolive we used @LoopSpace's bezier code in Shade (https://shade.to) to render the graph connections

  • edited August 28 Posts: 46

    Sweet! When it’s a good UX, it’s easy to forget the hard work that goes into the design and implementation.

    I grabbed the code from @LoopSpace ‘s github. Admittedly I was (lazily) hoping for some basic lines of code that would show the right way to call into the bezier code. There’s aren’t many code comments, and ‘thinking in Bezier’ isn’t always an exciting prospect, unless you clearly excel in the math of it all, as clearly @LoopSpace does.

    A few side thoughts:
    Can Shade itself be used to spin up this kind of shader code (bezier curves)? I am surely a beginner at shaders, but I suppose you’d need to work directly in glsl and tie that to your functions as @LoopSpace does in his code? Is Shade more for entity materials, less for rendering objects (e.g., the connectors in Shade) in pure shader code?

    I am sure the breadth and depth of available Shade in-app tutorials will increase (at least I hope!). In the meantime, I’d love someone’s recommendation on a resource (book, website, youtube series, etc.) that would build up my skills incrementally in creating shaders using the visual approach that Shade provides. I realize most sources would probably be tool-specific (Unity, etc.) but if it has a quality, in-depth coverage of principles that could be extended to Shade, that would be great. Even good blog sites that offer a range of shaders that could be created in Shade (I am thinking of the site that @John got the wireframe shader from) would be useful.

    Thanks!

  • Posts: 447

    Yeah, sorry about that! I'm not great at commenting for others.

    There are two ways to use the bezier code from that file. One is as a drawing command, the other is as an instance of a class.

    For the former, the command is:

    bezier(<start>, <first control>, <second control>, <end>, [<taper>])
    

    The points should be vec2s. The taper is an optional 0 or 1 to control whether the bezier is constant width or tapers. There are a few other possible inputs, in that it can handle quadratic and linear beziers.

    This version picks up the current strokewidth, colour, and linecapmode.

    For the latter, you start by instantiating a bezier object:

    b = Bezier(<start>, <first control>, <second control>, <end>)
    

    then you can set various attributes

    b:setStyle({<table of style options>})
    

    Once this one has been set up, after the first time it has been drawn, via b:draw(), then those options are "baked in".

    If drawing the same bezier (with the same options) many times then the OO approach is best. If the bezier will vary, then the functional version will be better.

  • Posts: 46

    Great! Thanks.

Sign In or Register to comment.