We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
IndexProgramming Questions & HelpPrograms › convert vectors to curve (bezier)
Page Index Toggle Pages: 1
convert vectors to curve (bezier) (Read 1377 times)
convert vectors to curve (bezier)
Jul 20th, 2005, 8:36pm
 
When I draw freehand on Illustrator or Flash, the points drawn are converted into a bezier curve.

I want to work on capturing paths. I would like to make this work more polished by having the option of applying this type of conversion to my paths.

I would like to know if anyone has any resources on the subject or if they have the algorithm to hand.

Thankyou for your time.
Re: convert vectors to curve (bezier)
Reply #1 - Jul 21st, 2005, 10:32am
 
I would also be interested in this algorithm.

I don't have the time right now to look for the algorithm, nor do I have internet at home. Next week I'm moving and I might find a lonely wifi connection floating in the air...

cheers
Re: convert vectors to curve (bezier)
Reply #2 - Jul 29th, 2005, 4:04pm
 
I have some info, though I'm afraid none of it is in Java.

In Javascript, I wrote this program, using Bezier curves. However, in order to shorten the code, it's slightly complex.

Code:
function spline (a, b, c, d) {
var i = Math.min(a.length, b.length, c.length, d.length), list = [];

while(i--)
list.unshift(function (A, B, C, D) {
return function (t) { return D + (t * (C + t * (B + (t * A)))); };
}(d[i] - 3 * c[i] + 3 * b[i] - a[i], 3 * c[i] - 6 * b[i] + 3 * a[i], 3 * b[i] - 3 * a[i], a[i]));

return list;
}


What that does is, for each dimension in the input vectors, create a spline function vector (a vector of functions, since in Javascript, you can assign functions to variables), which I can then use to generate the spline.

Some other links:
This one is openGL specific, but describes bezier curves in detail. You want cubic curves.
Another link, that describes the equations fairly well.

EDIT: Yay, I have more time to explain stuff now.

A bezier curve is a 1-dimensional function. This means, you give it a bunch of positions on a 1-dimensional line, and it will produce a function that smoothly goes along that line. To do this in 2 (or more) dimensions, to make a real curve, all you need to do is use a bezier function for the x axis and the y axis (and, possibly, a z axis as well).

Say you have 4 points, a, b, c, and d. In one dimension, then, a bezier function is given by:

Code:
f(t) = t^3 * e + t^2 * f + t * g + h, where:

e = d - 3c + 3b - a
f = 3c - 6b + 3a
g = 3b - 3a
h = a


That's in one dimension, so a, b, c, and d are each single numbers. Now, in two dimensions, you'll have (assuming you have points defined by ax, ay, bx, by, etc...):

Code:
x(t) = t^3 * e + t^2 * f + t * g + h
y(t) = t^3 * i + t^2 * j + t * k + l

e = dx - 3cx + 3bx - ax
f = 3cx - 6bx + 3ax
g = 3bx - 3ax
h = ax
i = dy - 3cy + 3by - ay
j = 3cy - 6by + 3ay
k = 3by - 3ay
l = ay


You can optimize the calulations a bit (as I did in my code -- sorry it's so obtuse), but you should simply be able to iterate along the defined functions for x and y and get your curve.

I hope that makes more sense!
Re: convert vectors to curve (bezier)
Reply #3 - Jul 29th, 2005, 4:12pm
 
check Graphics Gems I, "An Algorithm for Automatically Fitting Digitized Curves" by Schneider.

the gems site is at:
http://www.acm.org/tog/GraphicsGems/

and c code can be seen here:
http://www.acm.org/pubs/tog/GraphicsGems/gems/FitCurves.c
Re: convert vectors to curve (bezier)
Reply #4 - Jul 30th, 2005, 7:48pm
 

code for a different approach to the same problem can be found in the sources for inkscape - it does a pretty good job of fitting curves... (look in livarot)  

http://www.inkscape.org/

-zach

Re: convert vectors to curve (bezier)
Reply #5 - Aug 31st, 2005, 2:40pm
 
Thank you for the response. I wasn't aware of any comprehensive expanation of how beziers worked but that helped. I sat down and put a demo together to help me get my head around it.
Code:

Draggable [] anchor = new Draggable[2];
Draggable [] control = new Draggable[2];
float t = 0.0;
void setup(){
 size(400,400,P3D);
 anchor[0] = new Draggable (100,100,100,10,color(100,100,200),color(100,200,200),"rect");
 anchor[1] = new Draggable (300,300,0,10,color(100,100,200),color(100,200,200),"rect");
 control[0] = new Draggable (100,300,-100,10,color(100,100,200),color(100,200,200),"ellipse");
 control[1] = new Draggable (300,100,0,10,color(100,100,200),color(100,200,200),"ellipse");
 ellipseMode(CENTER);
 rectMode(CENTER);
}
void draw(){
 background(144,130,140);
 directionalLight(100,100,100,0,0,-1);
 stroke(0);
 t = (t+0.01)%1.0;
 noStroke();
 fill(255);
 pushMatrix();
 translate(
 bezierPoint(anchor[0].x,control[0].x,control[1].x,anchor[1].x,t),
 bezierPoint(anchor[0].y,control[0].y,control[1].y,anchor[1].y,t),
 bezierPoint(anchor[0].z,control[0].z,control[1].z,anchor[1].z,t));
 sphere(10);
 popMatrix();
 pointLight(255,255,255,
 bezierPoint(anchor[0].x,control[0].x,control[1].x,anchor[1].x,t),
 bezierPoint(anchor[0].y,control[0].y,control[1].y,anchor[1].y,t),
 bezierPoint(anchor[0].z,control[0].z,control[1].z,anchor[1].z,t));
 stroke(0);
 bezier(
 anchor[0].x,anchor[0].y,anchor[0].z,control[0].x,control[0].y,control[0].z,
 control[1].x,control[1].y,control[1].z,anchor[1].x,anchor[1].y,anchor[1].z);
 for (int i = 0; i < 2; i++){
   anchor[i].draw();
   control[i].draw();
   anchor[i].update();
   control[i].update();
 }
}
class Draggable {
 int x,y,z,size,c1,c2;
 String mode;
 boolean locked = false;
 Draggable (int x, int y, int z, int size, color c1, color c2, String mode) {
   this.x = x;
   this.y = y;
   this.size = size;
   this.c1 = c1;
   this.c2 = c2;
   this.mode = mode;
 }
 void draw(){
   noStroke();
   if (locked || over()){
     fill(c1);
   }
   else{
     fill(c2);
   }
   if (mode == "rect"){
     pushMatrix();
     translate(x,y,z);
     box(size*2,size*2,size*2);
     popMatrix();
     noFill();
     stroke(c1);
     rect(x,y,size*2,size*2);
   }
   if (mode == "ellipse"){
     pushMatrix();
     translate(x,y,z);
     sphere(size);    
     popMatrix();
     noFill();
     stroke(c1);
     ellipse(x,y,size*2,size*2);
   }
 }
 void update(){
   if (over() && mousePressed){
     locked = true;
   }
   if (locked){
     x = mouseX;
     y = mouseY;
   }
   if (!mousePressed){
     locked = false;
   }
   if (over() && keyPressed){
     switch(key){
     case '-':
     case '_':
       z -= 2;
       break;
     case '=':
     case '+':
       z += 2;
       break;
     }
   }
 }
 boolean over(){
   if (mouseX <= x+size && mouseX >= x-size && mouseY <= y+size && mouseY >= y-size){
     return true;
   }
   else{
     return false;
   }
 }
}
float BezierPoint (float anchor0, float control0, float control1, float anchor1, float t) {
 float a = anchor1 - 3 * control1 + 3 * control0 - anchor0;
 float b = 3 * control1 - 6 * control0 + 3 * anchor0;
 float c = 3 * control0 - 3 * anchor0;
 float d = anchor0;
 return pow(t,3) * a + pow(t,2) * b + t * c + d;
}

I did a site search of inkscape (google - site:inkscape.org livarot) but couldn't find anything that was blatant anough for me to spot or understand.
I found the curve fitting algorithm in the graphics gems but it was a nine page hike of code so I've yet to sit down and pick through it. I also have forgotten what asterisks in front of variables mean in C. Hopefully if I just separate the functions into a flowchart on a big piece of paper it may start to make sense.

Thanks again for the feed back, if there is any more advice I am attentive.

-

I've cut up the list of code and taped all the individual functions together. I haven't the slightest clue what it does.

I don't have the intelligence or experience to tackle this. Sad
Page Index Toggle Pages: 1