We are about to switch to a new forum software. Until then we have removed the registration on this forum.
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
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);
}
}
Answers
Interesting. Thanks for this implementation, @prince_polka.
I found Gabe's explanation of the approach on StackOverflow very helpful:
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():
@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.
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.
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:
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
bezier2()
specifies a bezier curve using four 2D points (analogous to the 2D, 8-argument version ofbezier()
...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()
.Spontaneously, yes it can. Would that be useful to you or just wondering?
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.
@jeremydouglass 12 argument version
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
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
@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
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
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.
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.. ?
it's a bit long code and not perfect, but here is the demo sketch
needs the peasycam library to run
So, what's the performance of your functions?
What is your thought about adding something like this in line 30:
Kf
@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"
I guessed so much. Using it too much will lead to performance hits.
Started following this guide
antigrain.com/research/bezier_interpolation/
@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.
@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.
@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
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...
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
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.
Check this library. There are some examples for bezier already implemented there: https://github.com/processing/processing/issues/2919
Kf
@Lord_of_the_Galaxy
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
Everything is manageable, except the
bezierPoint_pow()
.I got single view working, not essential for the bezier but it's what I felt motivated to do.
Very nice interface, @prince_polka !