[FIXED] Make bezier curve pass through control points

prince_polka

UPDATE 2: If you come here looking for a solution to the same problem I had, look no further.
Squeezed the messy class into a short and simple void function called bezier2(),
Works just as bezier , just that the curve goes through the control points.

/* bezier2(), a beizer() that passes through control points
 * Ported to processing by prince polka,
 * from C# code by Gabe @ Stackoverflow, http://stackoverflow.com/a/2316440
 */ 
void bezier2(float x0,float y0,float x1,float y1,float x2,float y2,float x3,float y3){
float c1=dist(x0,y0,x1,y1),c2=dist(x1,y1,x2,y2),c3=dist(x3,y3,x2,y2),t1=c1/(c1+c2+c3),
t2=(c1+c2)/(c1+c2+c3),a=t1*(1-t1)*(1-t1)*3,b=(1-t1)*t1*t1*3,d=t2*(1-t2)*(1-t2)*3,e=(1-t2)*t2*t2*3,
c=x1-(x0*pow(1-t1,3.0))-(x3*pow(t1,3)),f=x2-(x0*pow(1-t2,3.0))-(x3*pow(t2,3)),
g=y1-(y0*pow(1-t1,3.0))-(y3*pow(t1,3)),h=y2-(y0*pow(1-t2,3.0))-(y3*pow(t2,3));
x2=(c-a/d*f)/(b-a*e/d);x1=(c-(b*x2))/a;y2=(g-a/d*h)/(b-a*e/d);y1=(g-(b*y2))/a;
bezier(x0,y0,x1,y1,x2,y2,x3,y3);
}

UPDATE: Typical.. been struggling with this for hours but just minutes after I posted this I fixed it

openprocessing sketch

Letting original question stay to not get banned

This is what I wan't to accomplish.. fixed

I wan't a bezier() function that takes 4 xy coordinates like the regular one, but the line passing through the middle control points.

I found detailed explanations of how to achieve this, but I don't understand them so don't even try to explain, I have a code further down....

Javascript + SVG example
Math explained for the above example
PDF with explanation and PostScript code

This math and the javascript and postscript examples gives me a headache :(

But I found something better on stackoverflow :)
The C# code, although I'we never written C# , looks pretty much as processing code,
with a few minor differences such as using "out-arguments"
So assuming the C# code works I'd like to port it into processing, and made an attempt but can't get it to work for me.

The C# port of the PostScript I'd like to use

static class DrawingUtility
{
    // linear equation solver utility for ai + bj = c and di + ej = f
    static void solvexy(double a, double b, double c, double d, double e, double f, out double i, out double j)
    {
        j = (c - a / d * f) / (b - a * e / d);
        i = (c - (b * j)) / a;
    }

    // basis functions
    static double b0(double t) { return Math.Pow(1 - t, 3); }
    static double b1(double t) { return t * (1 - t) * (1 - t) * 3; }
    static double b2(double t) { return (1 - t) * t * t * 3; }
    static double b3(double t) { return Math.Pow(t, 3); }

    static void bez4pts1(double x0, double y0, double x4, double y4, double x5, double y5, double x3, double y3, out double x1, out double y1, out double x2, out double y2)
    {
        // find chord lengths
        double c1 = Math.Sqrt((x4 - x0) * (x4 - x0) + (y4 - y0) * (y4 - y0));
        double c2 = Math.Sqrt((x5 - x4) * (x5 - x4) + (y5 - y4) * (y5 - y4));
        double c3 = Math.Sqrt((x3 - x5) * (x3 - x5) + (y3 - y5) * (y3 - y5));
        // guess "best" t
        double t1 = c1 / (c1 + c2 + c3);
        double t2 = (c1 + c2) / (c1 + c2 + c3);
        // transform x1 and x2
        solvexy(b1(t1), b2(t1), x4 - (x0 * b0(t1)) - (x3 * b3(t1)), b1(t2), b2(t2), x5 - (x0 * b0(t2)) - (x3 * b3(t2)), out x1, out x2);
        // transform y1 and y2
        solvexy(b1(t1), b2(t1), y4 - (y0 * b0(t1)) - (y3 * b3(t1)), b1(t2), b2(t2), y5 - (y0 * b0(t2)) - (y3 * b3(t2)), out y1, out y2);
    }

    static public PathFigure BezierFromIntersection(Point startPt, Point int1, Point int2, Point endPt)
    {
        double x1, y1, x2, y2;
        bez4pts1(startPt.X, startPt.Y, int1.X, int1.Y, int2.X, int2.Y, endPt.X, endPt.Y, out x1, out y1, out x2, out y2);
        PathFigure p = new PathFigure { StartPoint = startPt };
        p.Segments.Add(new BezierSegment { Point1 = new Point(x1, y1), Point2 = new Point(x2, y2), Point3 = endPt } );
        return p;
    }
}

My failed attempt at porting it to processing

class DrawingUtility
{
  DrawingUtility(){}
    float out1x,out1y,out2x,out2y; 
    // linear equation solver utility for ai + bj = c and di + ej = f
    void solvexy(float a, float b, float c, float d, float e, float f) 
    {
        out2x = (c - a / d * f) / (b - a * e / d);
        out1x = (c - (b * out2x)) / a;
        out2y = (c - a / d * f) / (b - a * e / d);
        out1y = (c - (b * out2y)) / a;
    }

    // basis functions
    float b0(float t) { return pow(1.0 - t, 3.0); }
    float b1(float t) { return t * (1.0 - t) * (1.0 - t) * 3.0; }
    float b2(float t) { return (1.0 - t) * t * t * 3.0; }
    float b3(float t) { return pow(t, 3.0); }

    void bez4pts1(float x0, float y0, float x4, float y4, float x5, float y5, float x3, float y3)
    {
        // find chord lengths
        float c1 = sqrt((x4 - x0) * (x4 - x0) + (y4 - y0) * (y4 - y0));
        float c2 = sqrt((x5 - x4) * (x5 - x4) + (y5 - y4) * (y5 - y4));
        float c3 = sqrt((x3 - x5) * (x3 - x5) + (y3 - y5) * (y3 - y5));
        // guess "best" t
        float t1 = c1 / (c1 + c2 + c3);
        float t2 = (c1 + c2) / (c1 + c2 + c3);
        // transform x1 and x2
        solvexy(b1(t1), b2(t1), x4 - (x0 * b0(t1)) - (x3 * b3(t1)), b1(t2), b2(t2), x5 - (x0 * b0(t2)) - (x3 * b3(t2)));
        // transform y1 and y2
        solvexy(b1(t1), b2(t1), y4 - (y0 * b0(t1)) - (y3 * b3(t1)), b1(t2), b2(t2), y5 - (y0 * b0(t2)) - (y3 * b3(t2)));
    }

    void BezierFromIntersection(float start_x,float start_y,  float x1, float y1, float x2, float y2,  float end_x,float end_y)
    {   out1x=out1y=out2x=out2y=0;
        bez4pts1( start_x,start_y, x1,y1, x2,y2, end_x,end_y);
        bezier( start_x,start_y ,  out1x,out1y , out2x,out2y ,  end_x,end_y);
    }
}

openprocessing sketch of my work in progress

jeremydouglass

Interesting. Thanks for this implementation, @prince_polka.

I found Gabe's explanation of the approach on StackOverflow very helpful:

There are an infinite number of solutions to a curve passing through 4 points, but the best simple solution is to try to make the curve segment lengths proportional to the chord lengths.

I could see that actually being a useful addition to the Processing core. It certainly seems like it might be more intuitive for beginners to best-fit a curve to points along a line.

I've created a simple test sketch that visually demonstrates how the function automatically computes control points and passes them to the built-in bezier():

/** BezierFit
  * test of bezier2(), a beizer() that passes through control points
  * test sketch by jeremydouglass - ported to processing by prince polka,
  * from C# code by Gabe @ Stackoverflow: stackoverflow.com/a/2316440
  * 2017-03-19 Processing 3.2.3
  * forum.processing.org/two/discussion/21355/fixed-make-bezier-curve-pass-through-control-points#latest
 **/
void setup(){
  size(400,400);
}
void draw(){
  background(192);
  noFill();
  bezier2(
    0,height/2,
    width/3,height/3,
    mouseX,mouseY,
    width,height/2
  );
  ellipse(0,height/2,10,10);
  ellipse(width/3,height/3,10,10);
  ellipse(width,height/2,10,10);
  fill(0,255,0);
  ellipse(mouseX,mouseY,10,10);
}

/** bezier2(), a beizer() that passes through control points
  * Ported to processing by prince polka,
  * from C# code by Gabe @ Stackoverflow, <a href="http://stackoverflow.com/a/2316440" target="_blank" rel="nofollow">http://stackoverflow.com/a/2316440</a>;
 **/
void bezier2(float x0, float y0, float x1, float y1, float x2, float y2, float x3, float y3) {
  // measure chord lengths
  float c1=dist(x0, y0, x1, y1);
  float c2=dist(x1, y1, x2, y2);
  float c3=dist(x3, y3, x2, y2);
  // make curve segment lengths proportional to chord lengths
  float t1=c1/(c1+c2+c3);
  float t2=(c1+c2)/(c1+c2+c3);
  float a=t1*(1-t1)*(1-t1)*3;
  float b=(1-t1)*t1*t1*3;
  float d=t2*(1-t2)*(1-t2)*3;
  float c=x1-(x0*pow(1-t1, 3.0))-(x3*pow(t1, 3));
  float e=(1-t2)*t2*t2*3;
  float f=x2-(x0*pow(1-t2, 3.0))-(x3*pow(t2, 3));
  float g=y1-(y0*pow(1-t1, 3.0))-(y3*pow(t1, 3));
  float h=y2-(y0*pow(1-t2, 3.0))-(y3*pow(t2, 3));
  // find bezier control points
  x2=(c-a/d*f)/(b-a*e/d);
  x1=(c-(b*x2))/a;
  y2=(g-a/d*h)/(b-a*e/d);
  y1=(g-(b*y2))/a;
  // draw control points
  pushStyle();
  fill(255,0,0);
  ellipse(x1,y1,10,10);
  ellipse(x2,y2,10,10);
  stroke(255,0,0);
  line(x0, y0, x1, y1);
  line(x2, y2, x3, y3);
  popStyle();
  // draw bezier curve using control points
  bezier(x0, y0, x1, y1, x2, y2, x3, y3);
}

prince_polka

@jeremydouglass
I'm glad you like it.
Sorry for obfuscating the code so much, I did not expect anyone interested in reading it so tried to make it compact for copy-paste purposes.
That pushStyle(); and popStyle() thing looks very useful and convenient,
I thought you had to use getGraphics() to do stuff like that.

pushStyle();
  fill(255,0,0);
  ellipse(x1,y1,10,10);
  ellipse(x2,y2,10,10);
  stroke(255,0,0);
  line(x0, y0, x1, y1);
  line(x2, y2, x3, y3);
  popStyle();

  int temp_fill = getGraphics().fillColor;  
  fill(255,0,0);
  ellipse(x1,y1,10,10);
  ellipse(x2,y2,10,10);
  fill(temp_fill);
  int temp_stroke = getGraphics().strokeColor;
  stroke(255,0,0);
  line(x0, y0, x1, y1);
  line(x2, y2, x3, y3);
  stroke(temp_stroke);

You may be interested in my exercise in futility, of collecting "tools" useful for a train-game, without actually making a train game... ? ...
Make a track with right click, and drag the train with leftclick.
https://openprocessing.org/sketch/413075
it does some very strange things..
Bounding-box of beizer (very crude) And "half and half" algorthm, finding the beizerPoint closest to a set point faster (haven't benchmarked it but atleast in less iterations) than incrementally iterating through beizerPoints. Also a crude algorithm but the results it get's are pretty exact. And is what's used for pulling the train along the track.

kfrajer

This is an interesting alternative to the Bezier curve provided by Processing. To understand how they implemented their version, this link is very useful https://en.wikipedia.org/wiki/Bézier_curve and you need to scroll down to the animation part, specially comparing the quadratic and the higher order spline animation (in this case they have the cubic and other higher orders).

In general, every point is generated between two anchor points and every drawn point lays on the tangent line generated from moving points that slides along the lines between the anchor and control points. Those animations do a better job that trying to write an explanation.

In your alternative case, they are based on a cubic bezier polynomial as 4 points requires a level n=3 (starts from n=0). For continuity at the provided points, it is required for the first and second derivative to be the same at those points. This is a mathematical requirement. That is how they generated more equations that act as constrains to the final answer (otherwise you can get infinite solutions).

To compare bezier and bezier2 curves, one can add this to @jeremydouglass'es previous post before or after bezier2 function call:

  bezier(
    0,height/2,
    width/3,height/3,
    mouseX,mouseY,
    width,height/2
  );

Thanks for sharing. By the way, the train link does not work. You could also provide a link to your original post where you discussed your train algorithm, if possible.

Kf

jeremydouglass

bezier2() specifies a bezier curve using four 2D points (analogous to the 2D, 8-argument version of bezier()...

I wonder if that approach could be extended to a 3D curve through four 3D points (analogous to the 3D, 12-argument version of bezier().

prince_polka

Spontaneously, yes it can. Would that be useful to you or just wondering?

jeremydouglass

I don't have an immediate use for it myself.

I was just thinking that if such a form of bezier2 was proposed as an addition to Processing in the future then it would probably need both 8 and 12 argument versions for consistency with other 2D/3D language features.

prince_polka

@jeremydouglass 12 argument version

void bezier2( float x0,float y0,float z0,
              float x1,float y1,float z1,
              float x2,float y2, float z2,
              float x3,float y3, float z3 ) {
  // measure chord lengths
  float c1,c2,c3;
        c1=dist( x0,y0,z0, x1,y1,z1 );
        c2=dist( x1,y1,z1, x2,y2,z2 );
        c3=dist( x2,y2,z2, x3,y3,z3 );

  float t1,t2;
        t1=c1/(c1+c2+c3);
        t2=(c1+c2)/(c1+c2+c3);

  float b0,b1,b2,b3;
  b0 = pow( 1 - t1 , 3 );
  b1 = pow( 1 - t2 , 3);
  b2 = pow( t1 , 3 );
  b3 = pow( t2 , 3 );

  // make curve segment lengths proportional to chord lengths
  float a,b,c,d;
  a = t1 * ( 1 - t1 ) * ( 1 - t1 ) * 3;
  b = ( 1 - t1 ) * t1 * t1 * 3;
  c = t2 * ( 1 - t2 ) * ( 1 - t2 ) * 3;
  d = ( 1 - t2 ) * t2 *t2 *3;

  float e,f,g,h,i,j;

  e = x1 - ( x0 * b0 ) - ( x3 * b2 );
  f = x2 - ( x0 * b1 ) - ( x3 * b3 );
  g = y1 - ( y0 * b0 ) - ( y3 * b2 );
  h = y2 - ( y0 * b1 ) - ( y3 * b3 );
  i = z1 - ( z0 * b0 ) - ( z3 * b2 );
  j = z2 - ( z0 * b1 ) - ( z3 * b3 );

  x2 = ( e - a / c * f ) / ( b - a * d / c);
  x1 = ( e - ( b * x2 ) ) / a;
  y2 = ( g - a / c * h ) / ( b - a * d / c);
  y1 = ( g - ( b * y2 ) ) / a;
  z2 = ( i - a / c * j ) / ( b - a * d / c);
  z1 = ( i - ( b * z2 ) ) / a;

  bezier(x0,y0,z0, x1,y1,z1, x2,y2,z2, x3,y3,z3);
}

prince_polka

I'm working on a sketch to showcase it.

https://youtube.com/watch?v=Ca3G6Nvrtvk&feature=youtu.be

I am having problems with drag and drop in 3D thus 3 viewports

prince_polka

There are an infinite number of solutions to a curve passing through 4 points, but the best simple solution is to try to make the curve segment lengths proportional to the chord lengths.

I discovered trying to simplify the code a couple variations that although passing through all points created very ugly curves.
i.imgur.com/Eme1WKR.png

kfrajer

@prince_polka

I think this could be packed in a library. A cool demo just like the video is helpful. I prefer using two perpendicular grids to see the action of the points in 3D. One extra feature of this curves is not only to draw them but to also get their values. Imagine a version of lerp but along the whole curve. Or for a requested x value, obtain all the y values. What do you think?

Kf

prince_polka

I prefer one view rather than split but only got the points clickable using ScreenX() , but not draggable as that would require the opposite of that function so it'll be easier to make a split view example.

@kfrajer
Yes I have had "invisible" curves in mind for a while but kept focusing on drawing the curves as I like the immediate feedback of seeing them.

The invisible lines will just be a converting of the control points, so 12 inputs 6 outputs and used by stuff like.
bezierPoint(), bezierTangent() and some new utility functions I have in mind

float [] thomasAlgorithm(float[] IN){
  float c1,c2,c3;
    c1=dist( IN[0],IN[1],IN[2], IN[3],IN[4],IN[5] );
    c2=dist( IN[3],IN[4],IN[5], IN[6],IN[7],IN[8] );
    c3=dist( IN[6],IN[7],IN[8], IN[9],IN[10],IN[11] );

  float t1,t2;
        t1=c1/(c1+c2+c3);
        t2=(c1+c2)/(c1+c2+c3);

  float b0,b1,b2,b3;

  b0 = pow( 1 - t1 ,3);
  b1 = pow( 1 - t2 ,3);
  b2 = pow( t1 ,3);
  b3 = pow( t2 ,3);

  // make curve segment lengths proportional to chord lengths
  float a,b,c,d;
  a = t1 * ( 1 - t1 ) * ( 1 - t1 ) * 3;
  b = ( 1 - t1 ) * t1 * t1 * 3;
  c = t2 * ( 1 - t2 ) * ( 1 - t2 ) * 3;
  d = ( 1 - t2 ) * t2 *t2 *3;

  float e,f,g,h,i,j;

  e = IN[3] - ( IN[0] * b0 ) - ( IN[9] * b2 );
  f = IN[6] - ( IN[0] * b1 ) - ( IN[9] * b3 );
  g = IN[4] - ( IN[1] * b0 ) - ( IN[10] * b2 );
  h = IN[7] - ( IN[1] * b1 ) - ( IN[10] * b3 );
  i = IN[5] - ( IN[2] * b0 ) - ( IN[11] * b2 );
  j = IN[8] - ( IN[2] * b1 ) - ( IN[11] * b3 );
  float foo = a / c;
  float bar = ( b - a * d / c);

  IN[6] = ( e - foo * f ) / bar;
  IN[3] = ( e - ( b * IN[6] ) ) / a;
  IN[7] = ( g - foo * h ) / bar;
  IN[4] = ( g - ( b * IN[7] ) ) / a;
  IN[8] = ( i - foo * j ) / bar;
  IN[5] = ( i - ( b * IN[8] ) ) / a;

  return new float[] {IN[3],IN[4],IN[5], IN[6],IN[7],IN[8]};
}


float bezier2Point()( float x0,float y0,float z0,
              float x1,float y1,float z1,
              float x2,float y2, float z2,
              float x3,float y3, float z3) {
              float [] IN = thomasAlgorithm(new float [] {x0,y0,z0, x1,y1,z1, x2,y2,z2, x3,y3,z3});
              x1=IN[0]; y1=IN[1]; z1=IN[2];
              x2=IN[3]; y2=IN[4]; z2=IN[5];
              return bezierPoint(x0,y0,z0, x1,y1,z1, x2,y2,z2, x3,y3,z3);
              }

One extra feature of this curves is not only to draw them but to also get their values. Imagine a version of lerp but along the whole curve. Or for a requested x value, obtain all the y values. What do you think?

I'll be able to do lerping, it's similar to what the function alp_point() does in my train example.
Also there's many utilities I thought of but it takes more time and energy than I have, checking whether a curve is overlapping with itself.
Making this loop tips/inflection points thing
polymathprogrammer.com/2010/07/01/nicely-shaped-reverse-engineered-bezier-curve/

I'll try and prioritize easy stuff like this "polymorphism function" of calling the functions using 4 vectors rather than 12 coordinates, if one so wishes.

void bezier2(PVector knot0, PVector knot1,PVector knot2,PVector knot3){
      bezier2( knot0.x,knot0.y,knot0.z,
               knot1.x,knot1.y,knot1.z,
               knot2.x,knot2.y, knot2.z,
               knot3.x,knot3.y, knot3.z );
    }

Also I wonder what I shall call it, bezier2 is a bit unimaginative, beizer (flipped e and i) but might be a bit strange and far fetched, PCurve, Apportioned Chords, thomas algorithm etc.. ?

prince_polka

it's a bit long code and not perfect, but here is the demo sketch
needs the peasycam library to run

import peasy.*;
PeasyCam camera;
viewport XY;
viewport XZ;
PGraphics XYZ;
int counter=0;
knot [] track;
void setup(){
  size(800,800, P3D);
  track = new knot[4];
  XY = new viewport(0,0,width/2,height/2,P2D,"XY");
  XZ = new viewport(0,height/2,width/2,height/2,P2D,"XZ");
  XYZ = createGraphics(width/2,height,P3D);
  camera = new PeasyCam(this,XYZ, width/4,height/4,height/4, height);
  camera.setCenterDragHandler(null);
  while(counter<4){track[counter] = new knot(width/16+(width/8)*counter,height/4,height/4,counter++);}
  camera.reset();
}
void draw(){
  camera.setActive(mouseX>width/2);
  XY.go();
  XZ.go();
  view3D();
  image(XYZ,width/2,0);
}
void view3D(){
  XYZ.beginDraw();
  XYZ.background(180);
  XYZ.noFill();
  bezier2(XYZ,
          track[0].x,track[0].y,track[0].z,
          track[1].x,track[1].y,track[1].z,
          track[2].x,track[2].y,track[2].z,
          track[3].x,track[3].y,track[3].z);
  for(knot i:track){i.XYZ();}
  XYZ.endDraw();
}

void bezier2(PGraphics canvas,
             float x0,float y0,
             float x1,float y1,
             float x2,float y2,
             float x3,float y3) {
             bezier2 (
             canvas,
             x0,y0,0,
             x1,y1,0,
             x2,y2,0,
             x3,y3,0 );
           }
void bezier2( PGraphics canvas,
              float x0,float y0,float z0,
              float x1,float y1,float z1,
              float x2,float y2, float z2,
              float x3,float y3, float z3) {
              float [] IN = thomasAlgorithm(new float [] {x0,y0,z0, x1,y1,z1, x2,y2,z2, x3,y3,z3});
              x1=IN[0]; y1=IN[1]; z1=IN[2];
              x2=IN[3]; y2=IN[4]; z2=IN[5];
              if( canvas.is3D() ) { 
                canvas.bezier(x0,y0,z0, x1,y1,z1, x2,y2,z2, x3,y3,z3);
              }
              else if( canvas.is2D() ) {
                canvas.bezier(x0,y0, x1,y1, x2,y2, x3,y3);
              }
              }
float [] thomasAlgorithm(float[] IN){
  float c1,c2,c3;
    c1=dist( IN[0],IN[1],IN[2], IN[3],IN[4],IN[5] );
    c2=dist( IN[3],IN[4],IN[5], IN[6],IN[7],IN[8] );
    c3=dist( IN[6],IN[7],IN[8], IN[9],IN[10],IN[11] );

  float t1,t2;
        t1=c1/(c1+c2+c3);
        t2=(c1+c2)/(c1+c2+c3);

  float b0,b1,b2,b3;

  b0 = pow( 1 - t1 ,3);
  b1 = pow( 1 - t2 ,3);
  b2 = pow( t1 ,3);
  b3 = pow( t2 ,3);

  // make curve segment lengths proportional to chord lengths
  float a,b,c,d;
  a = t1 * ( 1 - t1 ) * ( 1 - t1 ) * 3;
  b = ( 1 - t1 ) * t1 * t1 * 3;
  c = t2 * ( 1 - t2 ) * ( 1 - t2 ) * 3;
  d = ( 1 - t2 ) * t2 *t2 *3;

  float e,f,g,h,i,j;

  e = IN[3] - ( IN[0] * b0 ) - ( IN[9] * b2 );
  f = IN[6] - ( IN[0] * b1 ) - ( IN[9] * b3 );
  g = IN[4] - ( IN[1] * b0 ) - ( IN[10] * b2 );
  h = IN[7] - ( IN[1] * b1 ) - ( IN[10] * b3 );
  i = IN[5] - ( IN[2] * b0 ) - ( IN[11] * b2 );
  j = IN[8] - ( IN[2] * b1 ) - ( IN[11] * b3 );
  float foo = a / c;
  float bar = ( b - a * d / c);

  IN[6] = ( e - foo * f ) / bar;
  IN[3] = ( e - ( b * IN[6] ) ) / a;
  IN[7] = ( g - foo * h ) / bar;
  IN[4] = ( g - ( b * IN[7] ) ) / a;
  IN[8] = ( i - foo * j ) / bar;
  IN[5] = ( i - ( b * IN[8] ) ) / a;

  return new float[] {IN[3],IN[4],IN[5], IN[6],IN[7],IN[8]};
}
boolean closerThan(float len, float x0, float y0, float x1, float y1){
  float delx = x0-x1;
  float dely = y0-y1;
  delx*=delx;
  dely*=dely;
  len*=len;
  return delx+dely < len;
}
class vec2 {
     float x; float y;
vec2(float X, float Y) {
         x=X;     y=Y; }
}
class viewport{
  PGraphics canvas;
  vec2 pos;
  vec2 size;
  boolean mob;
  String name;
  int dice;
  int a,b;
  viewport(int X, int Y, int W, int H,String RENDERER, String NAME){
    pos = new vec2(X,Y);
    size = new vec2(W,H);
    canvas = createGraphics(W,H,RENDERER);
    name = NAME;
    /* why can I not use string in case loop? */
    if(name=="XZ"){dice=0;}
    if(name=="XY"){dice=1;}
    if(name=="YX"){dice=2;}
    if(name=="YZ"){dice=3;}
    if(name=="ZY"){dice=4;}
    if(name=="ZX"){dice=5;}
    a=dice/2;
    b=(5-dice)%3;
  }
  void go(){
  mob = (abs(mouseX-pos.x-size.x/2)<size.x/2 && abs(mouseY-pos.y-size.y/2)<size.y/2);
  canvas.beginDraw();
  canvas.background(180);
  canvas.noFill();
  bezier2(canvas,track[0].c[a],track[0].c[b],track[1].c[a],track[1].c[b],track[2].c[a],track[2].c[b],track[3].c[a],track[3].c[b]);
  if(mob){ for(knot i:track){i.XY(canvas,pos,dice);} } 
  canvas.endDraw();
  image(canvas,pos.x,pos.y);
  }
}
class knot{
float x,y,z,xinit,yinit,zinit,size;
float [] c;
int id;
int box_x;
int box_y;
float mx,my;
boolean mob,follow,sect;
boolean mobxz,followxz,sectxz;
int xzpos=height/4;
  knot(float X,   float Y,float Z,int ID) {
     xinit=x=X; yinit=y=Y; zinit=z=Z; 
     c = new float[] {x,y,z};
     id=ID; 
     size=20.0;
   }
 void reset() { c[0]=x=xinit; c[1]=y=yinit; c[2]=z=zinit; }
 void XY(PGraphics canvas,vec2 pos, int dice){
   mx=mouseX-pos.x;
   my=mouseY-pos.y;
   int a=dice/2,b=(5-dice)%3;
   float xd=c[a], yd=c[b];
   mob=closerThan(size,xd,yd,mx,my);
   follow = (mousePressed && mob || follow);
   if (!mousePressed){follow=false;}
   if(follow){
     sect=false;
     for(knot i:track){if( i.id != id && closerThan(size,xd,yd,i.c[a],i.c[b]) ){sect=true; follow=false; reset(); break;}}
     if(!sect){
     c[a]=mx; c[b]=my;
   }
     }
     canvas.stroke(0);
     canvas.fill(#ffff00);
     canvas.ellipse(c[a],c[b],size,size);
 }
 void crosshair(float x, float y, float z, float size){
  XYZ.pushStyle();
  XYZ.noStroke();
  XYZ.fill(#ffff00);
  XYZ.pushMatrix();
  XYZ.translate(x,y,z);
  XYZ.sphere(size/4);
  XYZ.popMatrix();
  XYZ.popStyle();
  XYZ.stroke(0);fill(#ffff00);
  XYZ.line(x-size,y,z,x+size,y,z);
  XYZ.line(x,y-size,z,x,y+size,z);
  XYZ.line(x,y,z-size,x,y,z+size);
}
    void XYZ() {
    x=c[0]; y=c[1]; z=c[2];
    XYZ.stroke(0);
    XYZ.fill(#ffff00);
    crosshair(c[0],c[1],c[2],size);
  }
}

Lord_of_the_Galaxy

So, what's the performance of your functions?

kfrajer

What is your thought about adding something like this in line 30:

  for (int ii=-width>>1; ii<width>>1; ii+=15)
    for (int jj=-height>>1; jj<height>>1; jj+=15) {
      XYZ.point(ii, 0, jj);
      XYZ.point(ii, jj, 0);
    }

Kf

prince_polka

@Lord_of_the_Galaxy
Slow but not noticeably slow.

@krajfer
Not at computer now but ill check it when i get home. I assume that's some kind of "landmark"

Lord_of_the_Galaxy

I guessed so much. Using it too much will lead to performance hits.

prince_polka

Started following this guide
antigrain.com/research/bezier_interpolation/

PVector [] shape;
PVector prev;
import peasy.*;
PeasyCam camera;
void setup(){
  size(700,700,P3D);
  camera = new PeasyCam(this, width/2,height/2,height/2, height);
  shape = new PVector[10];
  int j=0;
for(PVector i:shape){
    shape[j++] = new PVector(random(width),random(height),random(height));
  }
prev=new PVector(5,5);
}
void draw() {
  background(51);
  //translate(mouseX, mouseY);
  fill(102);
  stroke(255);
  strokeWeight(2);
  for (int i=1; i<8;i++){
    PVector A=shape[i-1];
    PVector B=shape[i];
    PVector C=shape[i+1];
    //line (A.x,A.y,B.x,B.y);
    //line (B.x,B.y,C.x,C.y);
    //float x0,y0,x1,y1,x2,y2,x3,y3;
    PVector P0,P1,mp;
    float mid;
    //P0=(PVector.add(A,B).div(2));
    P0=PVector.lerp(A,B,0.5);
    P1=PVector.lerp(B,C,0.5);
    //line (P0.x,P0.y,P1.x,P1.y);
    float L1,L2,d1,d2;
    L1 = PVector.dist(A,B);
    L2 = PVector.dist(B,C);
    d1=L1/(L1+L2);
    d2=L2/(L1+L2);
    mp=PVector.lerp(P0,P1,d1);
    //ellipse(mp.x,mp.y,2,2);
    P0.sub(PVector.sub(mp,B));
    P1.sub(PVector.sub(mp,B));
    //line (P0.x,P0.y,P1.x,P1.y);
    noFill();
    bezier(A.x,A.y,A.z,prev.x,prev.y,prev.z,P0.x,P0.y,P0.z,B.x,B.y,B.z);
    prev=P1;
    ;
  }
  beginShape();
  noFill();
  stroke(#00ff00);
  endShape(CLOSE);
}

void mouseClicked(){
  int j=0;
for(PVector i:shape){
    shape[j++] = new PVector(random(width),random(height),random(height));
  }
}
    }

jeremydouglass

@prince_polka -- very cool 3-pane demo sketch -- and the peasycam view made it much clearer how the two input panes were interacting to create a 3D curve.

prince_polka

@jeremydouglas,
@kfrajer

I'm thinking on how to do implement lerping.
What I think will do the trick is simply doing the train thing.
Creating a lookup table (array) using BezierPoints, converted into points at equal distance (crude arc length parametrization)
When initialization is done, you'll be able to search through that table very efficiently.
The "problem" is if you need lerping to work simultaneously while editing/automating the curve as then the table would have to be re-initialized at blazing speed.
I think for most use cases there being a small delay of the lerp when editing the curve won't matter too much.
If using thousands of curves creating arrays for all of them could also take a very long time, (or possibly but unlikely alot of memory) but that's not a huge issue as that could be worked around with a noLerp() or updateLerp() function.

What behavior should be the default though?
And how should it behave at values outside of the range 0-1 ?
Regular lerp contiues, lerpColor is constrained, BezierPoint acts strangely.
What will work best depends on taste and use-case, maybe you have some input on this?

https://en.wikipedia.org/wiki/Skeleton_(computer_programming)

And what's a reasonable scope of the project?
It would be helpful to be if I had a "skeleton-library" to fill in the blanks and call it done.
I fear doing one idea for a function after another and coming up with new ideas during that process. Will result in more ideas than solutions, and a project so messy I'll abandon it.

kfrajer

@prince_polka

I will get back to you about this. I like to think you have calculated the parameters of the curve so it is a matter of choosing a value for t based on one of your provided links. I will need to review the resources to be able to provide good feedback :D

Kf

prince_polka

I looked at github and in the processing download if I could find the code how the regular beziers are implemented but didn't find it, anyways I think I have an idea of how they're implemented anyways.
I did take a look at the arc-length-parametrization example, which just does the train thing, but i'll take a closer look at it later see if I can use some off it anyways.
I'm starting to understand bezier curves much better, specifically this video De Casteljau's algorithm Which I understood as it's basicaly just nested lerps.

So I think lerp() and bezierPoint is doing just this...

/*float lerp(float  A, float B, float C) { // lerp name not allowed
  return A*(1-C)+B*C;
}*/

float bezierPoint_lerp(float A, float B, float C, float D, float T) { 
  return lerp( lerp( lerp(A,B,T),lerp(B,C,T), T), 
               lerp( lerp(B,C,T),lerp(C,D,T), T), T);
}

If one can get an alp-point without brute-forcing a new lookup table, every time the curve changes I don't know yet, I expect it's possible but we'll see, maybe next year?

EDIT:
Cleared up the function and found an alternative using pow() instead of lerp() , still gives the same "non-alp" result though, as expected

float bezierPoint_pow(float A, float B, float C, float D, float T) { 
  return A * pow(1-T,3) + 
         B * 3 * pow(1-T,2) * T +
         C * 3 * (1-T) * pow(T,2) + 
         D * pow(T,3);
}

Found it on this open source e-book, think it's also a good scope of the project to just follow the guides described there and implement it into processing-code, and when that's done, then the library is done.
Whenever that may be, no deadline.
A Primer on Bézier Curves
Also the ArcLengthParametrization example seems a bit better than what I had in mind.

kfrajer

Check this library. There are some examples for bezier already implemented there: https://github.com/processing/processing/issues/2919

Kf

prince_polka

@Lord_of_the_Galaxy

So, what's the performance of your functions?

Did a crude benchmark, take it with a grain of salt
bezier2() compared to bezier(), ≈ 10% slower (obviously as it's calling bezier())
closerThan() vs ( dist() < someDistance ) , ≈ 20% faster bezierPoint() copies...
bezierPoint_lerp() ≈ 5 % slower, and bezierPoint_pow() ≈ 5 times slower.
alp_point I expect will be hundreds times slower on refresh, but fine if lookups outweighs refresheses by a huge margin

Lord_of_the_Galaxy

Everything is manageable, except the bezierPoint_pow().

prince_polka

I got single view working, not essential for the bezier but it's what I felt motivated to do.

import peasy.*;
PeasyCam camera;
boolean mpa, click;
color mouseC,pickcolor = #ffff00; //
PVector UL,UR,BL,BR, mouse, pmouse,camposV;
float ratio,hovdis;
 PImage crosshair;
 pickable [] knot;
 int H,Npickables=0;
float [] node0,node1,node2,node3;
float [][] nodes;
void rotateZ3D (float theta) {
    float sin_t = sin(theta);
    float cos_t = cos(theta);
    for (int n=0; n<nodes.length; n++) {
        float [] node = nodes[n];
        float x = node[0];
        float y = node[1];
        node[0] = x * cos_t - y * sin_t;
        node[1] = y * cos_t + x * sin_t;
    }
};
void rotateY3D (float theta) {
    float sin_t = sin(theta);
    float cos_t = cos(theta);
    for (int n=0; n<nodes.length; n++) {
        float [] node = nodes[n];
        float x = node[0];
        float z = node[2];
        node[0] = x * cos_t - z * sin_t;
        node[2] = z * cos_t + x * sin_t;
    }
};
void rotateX3D (float theta) {
    float sin_t = sin(theta);
    float cos_t = cos(theta);
    for (int n=0; n<nodes.length; n++) {
        float [] node = nodes[n];
        float y = node[1];
        float z = node[2];
        node[1] = y * cos_t - z * sin_t;
        node[2] = z * cos_t + y * sin_t;
    }
};
class pickable {
  color id;
  PVector pos;
  boolean hover;
  boolean follow;
  pickable(){
    id=pickcolor+Npickables++;
    pos = new PVector(-250+Npickables*100,0,0);
  }
  void go(){
    hover = (mouseC==id);
    if(hover && click){follow=true;}
    if(!mousePressed){follow=false;}
    if (follow){pos=mouse.copy();}
    pushMatrix();
    translate(pos.x,pos.y,pos.z);
    stroke(id);
    sphere(20);
    popMatrix();
  }
}
PVector project(PVector A, PVector B, PVector C) {
    PVector L = PVector.sub(B,A);
    float K = PVector.dot( PVector.sub(C,A) , L);
          K/= PVector.dot(L,L);
    return A.add(PVector.mult(L,K));
 }
void bezier2(PVector knot0, PVector knot1,PVector knot2,PVector knot3){
      bezier2( knot0.x,knot0.y,knot0.z,
               knot1.x,knot1.y,knot1.z,
               knot2.x,knot2.y, knot2.z,
               knot3.x,knot3.y, knot3.z );
    }
void bezier2( float x0,float y0,float z0,
              float x1,float y1,float z1,
              float x2,float y2, float z2,
              float x3,float y3, float z3 ) {
  // measure chord lengths
  float c1,c2,c3;
        c1=dist( x0,y0,z0, x1,y1,z1 );
        c2=dist( x1,y1,z1, x2,y2,z2 );
        c3=dist( x2,y2,z2, x3,y3,z3 );
  float t1,t2;
        t1=c1/(c1+c2+c3);
        t2=(c1+c2)/(c1+c2+c3);
  float b0,b1,b2,b3;
  b0 = pow( 1 - t1 , 3 );
  b1 = pow( 1 - t2 , 3);
  b2 = pow( t1 , 3 );
  b3 = pow( t2 , 3 );
  // make curve segment lengths proportional to chord lengths
  float a,b,c,d;
  a = t1 * ( 1 - t1 ) * ( 1 - t1 ) * 3;
  b = ( 1 - t1 ) * t1 * t1 * 3;
  c = t2 * ( 1 - t2 ) * ( 1 - t2 ) * 3;
  d = ( 1 - t2 ) * t2 *t2 *3;
  float e,f,g,h,i,j;
  e = x1 - ( x0 * b0 ) - ( x3 * b2 );
  f = x2 - ( x0 * b1 ) - ( x3 * b3 );
  g = y1 - ( y0 * b0 ) - ( y3 * b2 );
  h = y2 - ( y0 * b1 ) - ( y3 * b3 );
  i = z1 - ( z0 * b0 ) - ( z3 * b2 );
  j = z2 - ( z0 * b1 ) - ( z3 * b3 );
  x2 = ( e - a / c * f ) / ( b - a * d / c);
  x1 = ( e - ( b * x2 ) ) / a;
  y2 = ( g - a / c * h ) / ( b - a * d / c);
  y1 = ( g - ( b * y2 ) ) / a;
  z2 = ( i - a / c * j ) / ( b - a * d / c);
  z1 = ( i - ( b * z2 ) ) / a;
  bezier(x0,y0,z0, x1,y1,z1, x2,y2,z2, x3,y3,z3);
}
void setup(){
  size(400,400,P3D);
  bezierDetail(50);
  ratio = (float)width/height;
  camera = new PeasyCam(this, 400);
  camera.setCenterDragHandler(null);
  knot = new pickable [] {new pickable(),new pickable(),new pickable(),new pickable()};
}
void draw() {
  click=(!mpa && mousePressed);
  float DX = (float)camera.getDistance()*width/695.*ratio;
  float DY = (float)camera.getDistance()*height/695.*ratio;
  node0 = new float [] {-DX, -DY,  0};
  node1 = new float [] { DX, -DY,  0};
  node2 = new float [] {-DX,  DY,  0};
  node3 = new float [] { DX,  DY,  0};
  nodes = new float [][] {node0, node1, node2, node3};
    background(100);
    float[] rot; 
    rot = camera.getRotations();
    float yaw=rot[0], pitch=rot[1], roll=rot[2];
    rotateZ3D(roll);
    rotateY3D(-pitch);
    rotateX3D(yaw);
    float [] camposF=camera.getPosition();
    camposV = new PVector (camposF[0],camposF[1],camposF[2]);
    UL = new PVector (node0[0],node0[1],node0[2]);
    UR = new PVector (node1[0],node1[1],node1[2]);
    BL = new PVector (node2[0],node2[1],node2[2]);
    BR = new PVector (node3[0],node3[1],node3[2]);
    UL = PVector.lerp(camposV,UL,hovdis);
    UR = PVector.lerp(camposV,UR,hovdis);
    BL = PVector.lerp(camposV,BL,hovdis);
    BR = PVector.lerp(camposV,BR,hovdis);
    noFill();
    stroke(10);
    bezier2(knot[0].pos,knot[1].pos,knot[2].pos,knot[3].pos);
    for(pickable i : knot){ i.go(); }
    stroke(#ff0000);
    line(0,0,0,100,0,0);
    stroke(#00ff00);
    line(0,0,0,0,100,0);
    stroke(#0000ff);
    line(0,0,0,0,0,100);
    float xlerp = (float)mouseX/(float)width;
    float ylerp = (float)mouseY/(float)height;
    mouse = PVector.lerp (
    PVector.lerp(UL,UR,xlerp) ,
    PVector.lerp(BL,BR,xlerp) , ylerp);
    strokeWeight(5);
    mouseC = get(mouseX,mouseY);
    if(mouseC >= pickcolor && mouseC <= pickcolor+Npickables){
    if(click){camera.setActive(false);}
    if(H != mouseC-pickcolor){
    H = mouseC-pickcolor;
    PVector origin = new PVector( 0,0,0);
    hovdis = PVector.dist( camposV , project(origin,camposV,knot[H].pos) ); 
    hovdis/=(float)camera.getDistance();
    }
  }
    else if(mpa && !mousePressed){camera.setActive(true);}
    pmouse=mouse.copy();
    mpa=mousePressed;
}

jeremydouglass

Very nice interface, @prince_polka !