Using a bezier curve as a boundary

ianweston · July 2017

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!

koogs · July 2017

the correct side of the curve

how do you define correct?

ianweston · July 2017

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. :)

Chrisir · July 2017

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);

ianweston · July 2017

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!

quark · July 2017

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

prince_polka · July 2017

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;
}

jeremydouglass · July 2017

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.

ianweston · July 2017

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!

Chrisir · July 2017

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

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

ianweston · July 2017

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?

jeremydouglass · July 2017

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

jeremydouglass · July 2017

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.

jeremydouglass · July 2017

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

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

ianweston · July 2017

@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!

prince_polka · September 2017

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

ianweston · September 2017

@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!

prince_polka · September 2017

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.

prince_polka · September 2017

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();
}

ianweston · September 2017

@prince_polka - only one thing i can say - you got skills!

Howdy, Stranger!

Categories

In this Discussion

Using a bezier curve as a boundary

Best Answers

Answers