Using a bezier curve as a boundary

edited July 2017 in How To...

Hi All,

I would like to draw some shapes to the screen, and use a bezier curve as a boundary to 'contain' the shapes... but i'm struggling to think how i can do that. I would like to make the shapes appear at random positions on the correct side of the curve, but never to appear on the wrong side... and to complicate it further, the bezier curve will always be changing its form.

Can anyone suggest how i might be able to do this? I actually have no ideas on this one!

thanks!

Answers

  • the correct side of the curve

    how do you define correct?

  • It will be the right hand side in this case, as the curve will be drawn vertically (in a nonchalant bendy bezier kind of a way). I wasn't sure how to phrase it before. :)

  • Answer ✓

    https://processing.org/reference/bezierPoint_.html

    This let's you access the points at any given point

    combine this with xLeft=map(0,height, 0,1);

    place the shapes at random (xLeft, width);

  • Thanks Chrisir, thats exactly what i was looking for... now i feel i should have done some more googling. I didn't know what to search for before, but this should give me everything i need. Thanks a lot!

  • Answer ✓

    There is no simple way to determine which side of a smooth Bezier curve a point is consider this Bezier curve (it was created using the bezier() function).

    bezier

    The green dot is to the right of the curve and the yellow dot is to the left of the curve, but the yellow dot is to the right of the green dot. :(

    There is a solution but it will be challenging.

    1) Create an array of bezier points along the curve. (Use the bezierPoint method to get the XY coordinates)

    2) Assume that the bezier curve, instead of being smooth, is made up of straight lines (the lines between adjacent points from step 1)

    3) To determine whether a point [x, y] is on the left or right of the curve we count the number of times the line [0, height/2]-[x, y] intersects with the lines from step 2

    4) If the number of intersections is n then the point is to the left of the line in n % 2 == 0 and to the right if n % 2 == 1

    We can see what I mean in this picture

    Yellow line 2 intersections : yellow spot on left side

    Green line 1 intersection : green spot on right side

    bezier

  • Answer ✓

    I have some functions that may help if you want to do quarks example

    /* checks wheter a point is on left/right side of line */
    boolean side( PVector A, PVector B, PVector C) {
        return PVector.dot(new PVector(B.y-A.y,A.x-B.x),PVector.sub(C,A))>=0.;
    }
    /* checks wheter line AB intersects with line CD 
     if both lines end-points are on different sides of the other line they are */
    boolean sectline(PVector A, PVector B, PVector C, PVector D){
        return side(A,B,C) != side(A,B,D) && side(C,D,A) != side(C,D,B);
    }
    /* checks wheter point is inside a polygon, a PVector array of vertices
     if a line from the point to another arbitrary far-away point...
     intersects with an odd number of polygon-lines it is*/
    boolean pip(PVector point, PVector... poly){
      int len = poly.length;
      int sects=0;
      PVector far = new PVector(9999,9999);
      for(int i=0; i<len; i++){
        sects+=sectline(point,far,poly[i],poly[(i+1)%len])?1:0;
      }
      return sects%2==1;
    }
    
  • edited July 2017 Answer ✓

    Another alternative is to draw the curve and then use the flood full algorithm on one side. This creates a mask that tells you left / right.

    Simple to implement, but might get expensive if you are updating the curve every frame.

  • Hi All,

    wow, thanks for all the added information... there's some good stuff here which i had never really thought about! but i expect i would have run into the problems you mention pretty quickly.

    With regards to the flood fill algorithm - can anyone give a link to a good example of this? flood filling the area would look super cool!

    Cheers!

  • You could just follow my advice do a for loop from 0 to height and

    Say line (xLeft,i,width,i);

  • Hi Again - i just found this page https://processing.org/discourse/beta/num_1138719727.html .. it looks pretty long and complex, and the last post was from 2009.

    Is this still a good reference, or is there a simpler way of doing flood fill in processing these days?

  • edited July 2017

    @Chrisir -- I think quark's first post shows that this won't always work.

  • There is a magic fill here:

    https://forum.processing.org/two/discussion/18902/magic-wand-flood-fill-question

    I thought I had posted a flood fill example sketch to that thread. Odd.

  • Okay, I contributed a demo Flood Fill sketch to that discussion:

    https://forum.processing.org/two/discussion/comment/101833/#Comment_101833

  • @jeremydouglass: Awesome! I've just gone through the code you posted line by line, and I'm relieved to say it makes sense to me. Thanks a lot! I'll incorporate that into my code and see how i get on... Thanks All, this has been hugely helpful!

  • edited September 2017 Answer ✓
    float rlerp2(float A, float B, float C, float D) {
      if (A-2*B+C==0)return 0;
      return (sqrt(-(A*C)+A*D+B*B-2*B*D+C*D)-A+B)/(-A+2*B-C);
    }
    float init(float Ax, float Bx, float Cx, float Ay, float By, float Cy) {
      float xm, ym;
      xm =(Ax+2*Bx+Cx)*0.25;
      ym =(Ay+2*By+Cy)*0.25;
      xm = rlerp2(Ax, Bx, Cx, xm);
      ym = rlerp2(Ay, By, Cy, ym);
      return abs(xm-ym);
    }
    float diff;
    float Ax = 0, Bx=100, Cx=500, Ay=0, By=500, Cy=400;
    void setup() {
      size(500, 500);
      diff=init(Ax, Bx, Cx, Ay, By, Cy);
    }
    void draw() {
      float a=rlerp2(Ax, Bx, Cx, mouseX);
      float b=rlerp2(Ay, By, Cy, mouseY);
      background(abs(a-b)>diff?#00ff00:#ff0000);
      noFill();
      strokeWeight(4);
      beginShape();
      vertex(Ax, Ay);
      quadraticVertex(Bx, By, Cx, Cy);
      endShape();
    }
    

    Shader example of cove above
    thebookofshaders.com/edit.php?log=170903153233

    I solved it for quadratic beziers (one controlpoint) by posting
    De Casteljau's algorithm into wolframalpha as such
    D=((A*(1-T)+B*T)*(1-T)+(B*(1-T)+C*T)*T) solve T

    For cubic beziers it would have to solve this

    E = ((A*(1-T)+B*T)*(1-T)+(B*(1-T)+C*T)*T)*(1-T)+((B*(1-T)+C*T)*(1-T)+(C*(1-T)+D*T)*T)*T solve T

    Which it wasn't as happy with...

    EDIT:

    E = T (3 B (T - 1)^2 - T (3 C (T - 1) - D T)) - A (T - 1)^3 solve T
    or
    E = A * (1-T)^3 + B * 3 *(1-T)^2 * T + C * 3 * (1-T) * T^2 + D * T^3 solve T

    gives a long solution, the one on the bottom doesn't work doesn't take A into account,
    I will try to implement it, it will be challenging but worth it if it works

    To find wheter Point is to the left or right of bezier(x0,y0,x1,y1,x2,y2,x3,y3)

    Find the (upto 3) solutions for T where bezierPoint(y0,y1,y2,y3,T) == Point.y

    Count how many times bezierPoint(x0,x1,x2,x3, solutions for T) < Point.x

    If even point is on right side, else left

  • @prince_polka - I must admit, you lost me on all the maths equations, but that sketch runs very nicely! I'll go through it carefully to make sure i understand it... I think this will be very useful for me and the larger community!

  • Don't pay too much attention to it as my math is not correct,
    the diff() thing will not be needed if done correctly for example.
    It just happens to work approximately for some quadratic curves.

    The cubic solution is a clusterfuck with four point variables, but replacing A,B,C, and D with constants gives a more manageable solution. And if you plot it you get a curve going from 0.0 at A to 1.0 at D.
    I don't get the same result writing it as code though and I supspect that's because I don't treat the results of sqrt() as a complex number, but I might be wrong about that and done some other misstake.

  • edited September 2017 Answer ✓

    I think I solved it

    EDIT: removed superfluous complex class and functions

    EDIT2 : simplified calculation of variable F

    double[] bezierTime( double A, double B, double C, double D, double E ) {
      double[] T = new double[3];
      double F, G, H, J, FG, s, r, n, multr;
      final double U, HALF_PI, TWO_PI, SIXTH_PI;
    
      H =  3*(C-B) + A-D;
    
      F = 27*((B-C-C)*(B*(B+B+C)-C*(A*3+C))+D*(A*(A+D-3*(B+C))+B*(6*B-3*C))-(H*H*E));
    
      G =  9 * ( A*(C-D) + B*(D+C-B) - C*C );
    
      J = ( A + C - B - B )/H;
    
      U = 1.5874010519681994747517056392723; //2^2/3
    
      HALF_PI = 1.5707963267948966192313216916397;
    
      TWO_PI = 6.28318530717958647692528676655;
    
      SIXTH_PI = 0.5235987755982988730771072305465;
    
      FG = F*F+4*G*G*G;
    
      s = Math.sqrt(Math.abs(FG));
      if (FG>=0) {
        r =   Math.cbrt(Math.abs(F+s));
        n = ( Math.atan2(0, F+s) + TWO_PI )/3;
      } else {
        r = Math.cbrt(Math.abs(F)+s);
        n = ( Math.atan2(s, F) + TWO_PI )/3;
      }
    
      multr = (4*G - r*r *U*U)/(6*H*r*U);
    
      T[0] = Math.sin( -n - HALF_PI  ) * multr + J;
      T[1] = Math.sin(  n + SIXTH_PI ) * multr + J;
      T[2] = Math.sin( -n + SIXTH_PI ) * multr + J;
    
      return T;
    }
    
    double bezierPoint (double a, double b, double c, double d, double t) {
      double t1 = t-1.0f;
      return t * ( 3*t1*(b*t1-c*t) + d*t*t ) - a*t1*t1*t1;
    }
    
    double[] bezierPoints (double a, double b, double c, double d, double[] times ) {
      double[] out = new double[times.length];
      for(int i=0;i<times.length;i++){
      double t = times[i];
      double t1 = t-1.0D;
      out[i] = t * ( 3*t1*(b*t1-c*t) + d*t*t ) - a*t1*t1*t1;
      }
      return out;
    }
    
    boolean bezierSide(double x0, double y0, double x1, double y1,
                       double x2, double y2, double x3, double y3,
                       double px,double py){
     double [] points = bezierPoints(x0,x1,x2,x3,bezierTime(y0,y1,y2,y3,py));
     int sum=0;
     for(double p:points)if( px>p )sum++;
    
     return (sum&1)==1; 
    }
    
    void setup() {
      size(400, 400);
      noFill();
    }
    void draw() {
      background(150);
      float x0, x1, x2, x3;
      x0=300;
      x1=-50;
      x2=550;
      x3=100;
    
      double[] sol = bezierTime(x0, x1, x2, x3, mouseX);
      bezier(x0, 0, x1, 133, x2, 266, x3, 400);
      noFill();
      fill(#ff0000);
      text( sol[0] +"", 10, 10);
      fill(#00ff00);
      text( sol[1] +"", 10, 40);
      fill(#0000ff);
      text( sol[2] +"", 10, 70);
    
      if(bezierSide(x0, 0, x1, 133, x2, 266, x3, 400,mouseX,mouseY)){
        line(mouseX, 0, mouseX, height);
      }
    
      float x = bezierPoint(x0, x1, x2, x3, (float)sol[0]);
      float y = bezierPoint(0, 133, 266, 400, (float)sol[0]);
      fill(#ff0000);
      ellipse(x, y, 10, 10);
      x = bezierPoint(x0, x1, x2, x3, (float)sol[1]);
      y = bezierPoint(0, 133, 266, 400, (float)sol[1]);
      fill(#00ff00);
      ellipse(x, y, 10, 10);
    
      x = bezierPoint(x0, x1, x2, x3, (float)sol[2]);
      y = bezierPoint(0, 133, 266, 400, (float)sol[2]);
      fill(#0000ff);
      ellipse(x, y, 10, 10);
      noFill();
    }
    
  • @prince_polka - only one thing i can say - you got skills!

Sign In or Register to comment.