
Hi!
I've made a drawingAPI that draws beziers with an unlimited number of controll points. Now, I've solved this with geometry and not algebra since I'm not that good at math. But this is very slow... To draw a bezier with four controll points it takes 60ms, while it takes less then 15ms with this code:
Code:
onClipEvent(enterFrame){
for (i=0;i<50;i++) this["d"+i].BezierPosition(bezier1, i/50)
}
...and...
Code:
Object.prototype.BezierPosition = function(bez, t){
t = Math.min(Math.max(t,0),1)
var c = 3* (bez.x1  bez.x0)
var b = 3* (bez.x2  bez.x1)  c
var a = bez.x3  bez.x0  c  b
this._x = a*t*t*t + b*t*t + c*t + bez.x0
c = 3* (bez.y1  bez.y0)
b = 3* (bez.y2  bez.y1)  c
a = bez.y3  bez.y0  c  b
this._y = a*t*t*t + b*t*t + c*t + bez.y0
}
(this code was written by someone at this board by I don't remember the name right now)
Well.. I could translate this to my drawingAPI, but this is only for four controll points... What about n controll points? With 5 controll points I know that the last line should be:
Code:
this._y = a*t*t*t*t + b*t*t*t + c*t*t + d*t + bez.y0
but other then that I don't understand much...
anyone?
.bobo

but this is only for four controll points... What about n controll points? With 5 controll points I know that the last line should be:
As I know, Bezier curve consists of 1 startPoint, 1 controlPoint for startPoint, 1 endPoint and 1 controlPoint for endPoint. There are 4 points.
I dont know what do you mean by "5 control points" ?

Originally posted by ericlin
As I know, Bezier curve consists of 1 startPoint, 1 controlPoint for startPoint, 1 endPoint and 1 controlPoint for endPoint. There are 4 points.
I dont know what do you mean by "5 control points" ?
I just posted a long replay to this, but when I was about to send it, it just dissapeared... =(
well, anyway. The basic rules for a Bezier will work with any number of points. curveTo in Flash MX is a Bezier using 3 points.
If you check http://www.elstudion.com/bobo/index2.html you can see my example of beziers using a random number of points from 3 to 8...
peace
.bobo

Oh, thank you.
I learn "Bezier curve" from Graph and Flash tutorial. When they talked about Bezier curve and showed examples, they always use 4 points model. So I thought Bezier curve is always 4 points.
If I had not replied, I wouldnt have got this corrected. Thank you.

Yes we can
check out the file of august 11th
http://www.bit101.com/lab.html

thanks, but it doesn't help me much...
first, I couldn't find any source code and
second and most important; that's not beziers... =)
I guess what he does is moving to the point in the middle of point A and B and curves to the middle of point B and C (using B as the controll point) and so on...
but thanks anyway! =)
.bobo

Yes we can
the page i mentioned also has a source directory,but you´re right about the used method in the file i mentioned,sorry if it was no good for you.
so i guess Quadratic Bezier Vertex code/source like this one
http://www.werehere.com/forums/show...hreadid=154837
fails because of the same reason,right?
and what about
bezier segment code for subnodes?
like
http://www.werehere.com/forums/show...bezier+segment

just by looking at the swf's i think that it isn't good for what i need... but I will investigate the .fla's as soon as i get a chance...
even if it doesn't help me it is interesting reading...
thanks!
.bobo

Yes we can
Originally posted by elstudion
just by looking at the swf's i think that it isn't good for what i need... but I will investigate the .fla's as soon as i get a chance...
even if it doesn't help me it is interesting reading...
thanks!
.bobo
no prob,by the way,the "misfitting file i mentioned in my first post can be downloaded here:
http://www.bit101.com/flafiles/020811.fla
(i´m working on a simple 3d editor where you can set points,select two to connect them and select several ones to build a shape or draw curved things and that source inspired me to do that,so i still like it )
check out the vapor example here (press on render)
http://www.outmoded.com/index.php
that´s the most impressive bezier thing i´ve seen done in flash up to date

This is a long post, but I thought it would be wise to take the logic through the powers to explain the syntax more clearly.
Firstly, I'll post an example by ahab that will show you expansion of 2 binomials using the FOIL method from this thread:
Bezier curves  http://board.flashkit.com/board/show...threadid=58629
/////////////////////////////////
 To get the Bernstein basis functions, 1 can be rewritten like this:
1 = t + [1  t]
 use this substitution to square 1, resulting in a quadratic equation:
1^2 = (t + [1  t])(t + [1  t])
 FOIL out the 2 binomials  (First, Outside, Inside, Last):
1 = t^2 + t(1  t) + t(1  t) + (1  t)^2
 combine like terms 
1 = t^2 + 2t(1  t) + (1  t)^2
/////////////////////////////////
Now, as the next link will advise, the FOIL method is a particular example of the Distributive Property for the expansion of polynomials:
http://mathforum.org/library/drmath/view/57480.html
/////////////////////////////////
Now we'll use the Distributive Property to expand the cube of 1, resulting in a cubic equation:
1^3 = (t + [1  t])(t + [1  t])(t + [1  t])
First, expand the product of the first 2 factors, resulting in the same quadratic equation as in ahab's example above:
(t + [1  t])(t + [1  t]) = t^2 + t*[1t] + [1t]*t + [1t]^2
Below is the same right operand as above, split into our basis functions, each found between :
= ~B0~(t^2) + ~B1~( t*[1t] + [1t]*t) + ~B2~([1t]^2)
Then combine like terms and list:
B0(t) = t^2
B1(t) = 2*t*[1t]
B2(t) = [1t]^2
Now replace the first 2 factors with the above expansion, and expand the product of that expansion and the 3rd factor:
(t^2 + 2*(t*[1t]) + [1t]^2)(t+[1t])
= t^3 + t^2*[1t] + (2*(t*[1t])*t) + (2*(t*[1t])*[1t]) + ([1t]^2)*t + [1t]^3
= ~B0~(t^3) + ~B1~(t^2*[1t]) + (2*(t*[1t])*t) + ~B2~(2*(t*[1t])*[1t]) + (([1t]^2)*t) + ~B3~([1t]^3)
B0(t) = t^3
B1(t) = 3*t^2*[1t]
B2(t) = 3*t*[1t]^2
B3(t) = [1t]^3
/////////////////////////////////
Now we'll take the equation to the 4th power, resulting in a quartic equation:
1^4 = (t + [1  t])(t + [1  t])(t + [1  t])(t + [1  t])
Using the cubic results, replace the first 3 factors, then find the product of that equation and the 4th factor:
((t^3) + (3*t^2*[1t]) + (3*t*[1t]^2) + [1t]^3)(t+[1t])
= (t^4) + (t^3*[1t]) + ((3*t^2*[1t])*t) + ((3*t^2*[1t])*[1t]) + ((3*t*[1t]^2)*t) + ((3*t*[1t]^2)*[1t]) +( [1t]^3*t) +( [1t]^3*[1t])
= ~B0~(t^4) + ~B1~(t^3*[1t]) + ((3*t^2*[1t])*t) + ~B2~((3*t^2*[1t])*[1t]) + ((3*t*[1t]^2)*t) + ~B3~((3*t*[1t]^2)*[1t]) +( [1t]^3*t) +~B4~( [1t]^3*[1t])
B0(t) = t^4
B1(t) = 4*t^3*[1t]
B2(t) = 6*t^2*[1t]^2
B3(t) = 4*t*[1t]^3
B4(t) = [1t]^4
/////////////////////////////////
Finally, we'll take the equation to the 5th power, resulting in a quintic equation:
1^5 = (t + [1  t])(t + [1  t])(t + [1  t])(t + [1  t])(t + [1  t])
Again, we'll now use the quartic results to find the product of that equation and the 5th factor:
((t^4) + (4*t^3*[1t]) + (6*t^2*[1t]^2) + (4*t*[1t]^3) + ([1t]^4))(t+[1t])
= (t^5) + (t^4*[1t]) + ((4*t^3*[1t])*t) + ((4*t^3*[1t])*[1t]) + ((6*t^2*[1t]^2)*t) + ((6*t^2*[1t]^2)*[1t]) + ((4*t*[1t]^3)*t) + ((4*t*[1t]^3)*[1t]) + ([1t]^4*t) + ([1t]^4*[1t])
= ~B0~(t^5) + ~B1~(t^4*[1t]) + ((4*t^3*[1t])*t) + ~B2~((4*t^3*[1t])*[1t]) + ((6*t^2*[1t]^2)*t) + ~B3~((6*t^2*[1t]^2)*[1t]) + ((4*t*[1t]^3)*t) + ~B4~((4*t*[1t]^3)*[1t]) + (([1t]^4)*t) + ~B5~(([1t]^4)*[1t])
B0(t) = t^5
B1(t) = 5*t^4*[1t]
B2(t) = 10*t^3*[1t]^2
B3(t) = 10*t^2*[1t]^3
B4(t) = 5*t*[1t]^4
B5(t) = [1t]^5
/////////////////////////////////
Of course, you can extrapolate this syntax to as many powers as required, although you may find that cpu usage may rise with the extra complexity. Each basis function represents the arc between 2 points, resulting in (n)arcs and (n+1)points. I'll post the main code for the quintic bezier below ... you can download the quadratic, cubic and quartic bezier examples by Den Ivanov, written for Flash5, from Flashkit's download area. I'll also provide links to the quintic swf/fla below (the code is still Flash5, although published in FlashMX) ... BTW, many thanks to Den for providing the original source code.
After completing this post, I read your new message that states you are working on a 3d version. owel, you may find this post useful ... Den also has a 3d bezier version which I haven't yet explored, posted at his site ... http://flash.onego.ru ...under 'my new Flash MX stuff'.
edit
I took a quick look at Den's 3dsplines code, and found that he's used 'curveTo' to draw the splines ... so the integrated quadratic 3point method has been utilized.
http://members.shaw.ca/flashmath101/quinticBezier.swf
http://members.shaw.ca/flashmath101/quinticBezier.fla
Code:
// quinticBezier
// adapted from: Den Ivanov  http://flash.onego.ru
// Bernstein basis functions
function B1 (t) {
return (t * t * t * t * t);
}
function B2 (t) {
return (5 * t * t * t * t * (1  t));
}
function B3 (t) {
return (10 * t * t * t * (1  t) * (1  t));
}
function B4 (t) {
return (10 * t * t * (1  t) * (1  t) * (1  t));
}
function B5 (t) {
return (5 * t * (1  t) * (1  t) * (1  t) * (1  t));
}
function B6 (t) {
return ((1  t) * (1  t) * (1  t) * (1  t) * (1  t));
}
// draw spline routine : called from RedrawClip
function DrawSpline () {
count = 0;
// change this for smooth line
detailBias = 1/30;
level = 1;
do {
x = cP1._x*B1(count)+cP2._x*B2(count)+cP3._x*B3(count)+cP4._x*B4(count)+cP5._x*B5(count)+cP6._x*B6(count);
y = cP1._y*B1(count)+cP2._y*B2(count)+cP3._y*B3(count)+cP4._y*B4(count)+cP5._y*B5(count)+cP6._y*B6(count);
if (level>1) {
attachMovie("line", "line"+level, level+10);
_root["line"+level]._x = x;
_root["line"+level]._y = y;
_root["line"+level]._rotation = Math.atan2(yoldy, xoldx)*180/(Math.PI);
_root["line"+level]._xscale = _root["line"+level]._yscale = Math.sqrt((xoldx)*(xoldx)+(yoldy)*(yoldy));
}
yold = y;
xold = x;
++level;
count += detailBias;
} while (count<=1);
}
// main init : put 6 control point to stage
for (i=1; i<=6; i++) {
attachMovie("cdot", "cP"+i, i);
_root["cP"+i]._x = random(540);
_root["cP"+i]._y = random(400);
_root["cP"+i].n = i;
}
stop();
Richard
[Edited by Dickee on 08232002 at 02:21 PM]

Thank you so very much... I think I love you
I've been desperate for that math thing so long, but havn't been able to find it anywhere!
But one thing; you say that the cpu usage will rise if you use many controllpoints... Is it possible that it will be faster to use geometry if you're using many controllpoints?
Using 8 points with geometry takes ~250ms, but it will too get slower and slower...
If you have a 3d enviroment allready, it would be easy enough to do a 3d bezier... to calculate the z you do exactly as you did with x and y... so there would be no difference that I know of...
I still like my drawingAPI for the beziers with unlimited controlpoints, but maybe it will be hard to implement the math if I'm sticking to it beeing unlimited....? What do you think?
as a little selfpromotion once more:
http://www.elstudion.com/bobo/index2.html
for my bezier thing... There is also another more basic at:
http://www.elstudion.com/bobo/
thanks everyone for helping me out! =) =) =)
.bobo

That's just lovely! Whatever you're doing ... keep doing it!
I didn't do any speed tests on the quintic ... I just noticed a speed decrease in comparison to Den's quartic example.
Have fun!
Richard

Yes we can
Originally posted by elstudion
If you have a 3d enviroment allready, it would be easy enough to do a 3d bezier... to calculate the z you do exactly as you did with x and y... so there would be no difference that I know of...
I still like my drawingAPI for the beziers with unlimited controlpoints, but maybe it will be hard to implement the math if I'm sticking to it beeing unlimited....? What do you think?
yep,i implemented the bezier part now,quite fun to play around with it,but quite useless unless i find a way to save the generated models (maybe as xml)...
about your bezier thingy: there´s no way around,it will always get slower the more controlpoints you add,but congrats on it,nevertheless fast,smooth,nice one

Originally posted by tomsamson
yep,i implemented the bezier part now,quite fun to play around with it,but quite useless unless i find a way to save the generated models (maybe as xml)...
about your bezier thingy: there´s no way around,it will always get slower the more controlpoints you add,but congrats on it,nevertheless fast,smooth,nice one
Can't you just save the controll points and then generate the beziers again at runtime? Or mabe that's what you had in mind all the time...
What I ment about my beziers and the speed of them was f it eventually would be faster to calculate them with geometry instead of algebra? I don't think so though... When I've implemented the algebra into my project I will run some tests and get back to you...
thanks for helping me out and thank you Dickee for liking what I've done... =)
.b

Yes we can
Originally posted by elstudion
Originally posted by tomsamson
yep,i implemented the bezier part now,quite fun to play around with it,but quite useless unless i find a way to save the generated models (maybe as xml)...
about your bezier thingy: there´s no way around,it will always get slower the more controlpoints you add,but congrats on it,nevertheless fast,smooth,nice one
Can't you just save the controll points and then generate the beziers again at runtime? Or mabe that's what you had in mind all the time...
yes,you´re right,that´s what i want to do.i´ve got everything working (the drawing mode,the different viewpoint windows etc.and the output window that creates a string with the positions of all controllpoints),except the possibiltiy to save the generated output.
it wouldn´t be any problem if i´d use that app like thingy in a browser and send the generated data via php/xml to a server,but i want this to be used as offline/standalone app and i don´t have a solution how to save that for this case...
(but i won´t give up before finding a solution after coming up to this point )
Originally posted by elstudion
What I ment about my beziers and the speed of them was f it eventually would be faster to calculate them with geometry instead of algebra? I don't think so though... When I've implemented the algebra into my project I will run some tests and get back to you...
thanks for helping me out and thank you Dickee for liking what I've done... =)
.b [/B]
no problem,always with joy ,
to geometry instead of algebra way?
i´d say it won´t change a lot but i´m not sure as i didn´t do direct comparisons with the same settings,so i´m looking forward to your comparion results

madskool.wordpress.com
Wow! thanks
What a wonderful thread!  I found it just at the time I wanted to know all about Bezier curves, and it told me everything I wanted to know.
tomsamson: I liked the August 11th Example. I too want to fit a curve around a set of points. I can see that the technique used here is quite simple.
Actually I want to generate a smooth curve from a dragged mouse path. Similar to the MX pencil tool. I'm thinking about filtering the many points obtained from this drag, to just a few representative ones. Then treating these as control points  as you have done. My filtering will retain more points where path of points changes direction more rapidly (and less for smoother sections)  this seems sensible. Anyone done this already?
Dickee: Thanks, this was VERY informative. This is what I was looking for. By the way, rather than doing all that multiplication of polynomials, you just have to use successive lines of pascal's triangle:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
(Can also be derived using 'combinations' formula)
So the 6th power equation is:
B0(t) = t^6
B1(t) = 6*t^5*(1t)
B2(t) = 15*t^4*(1t)^2
B3(t) = 20*t^3*(1t)^3
B4(t) = 15*t^2*(1t)^4
B5(t) = 6*t*(1t)^5
B6(t) = (1t)^6
I just love mathematical patterns like this

madskool.wordpress.com
I'm having fun with Bezier curves, but there's something I've yet to figure out.
Suppose I have two quadratic bezier curves on the screen. How do I determine their points of intersection?
What's stumpted me is that the bezier equations are parametric (in terms of t). What I need is an equalty in terms of both x and y (I suspect this will boil down to solving a quadratic).
Help anyone?

Hey brutfood et al!
Well, I've been researching 'determining intersection of two Bezier curves', with very little information to glean from the net. The links I've provided below will advise that the solution to this problem is very complex ... way over my head, using calculus integration, partial derivitives, etc. to return accurate results.
So, what I've produced is an approximation technique based on the increment of 't' and a tolerance factor, both adjustable onscreen. However, not only does this technique derive results in an inappropriate manner (by finding the mean of a pair of points from each curve's nearpoint that lies within the tolerance factor), but also I haven't followed any of the procedures suggested in the links ... let the kludge banners fly!
I've utilized Den's Flash 5 coding for this file, but perhaps a more efficient solution could be found with either Robert Penner's or Timothee Groleau's cubic Bezier recursion methods. The last two links below take you to their respective solutions.
I may indeed be on the right track with my file (except for the mean kludge finish!) ... perhaps I may find a way to further refine my coordinates by implementing the hint from the quote below.
Please explore/alter my file to see if I'm missing something that's glaring, but presently hiding from me, to achieve more consistent and accurate results. Or perhaps the links will spill the beans for you to produce a more precise algorithm applying deCasteljau, NURBS or some other method!
http://members.shaw.ca/flashmath101/...rIntersect.swf
http://members.shaw.ca/flashmath101/...rIntersect.fla
From the 1st link below ... he tempts us with the solution thoughout the page, then leaves us hanging without providing the algorithm:
So if "there are no good, general methods for solving systems of more than one nonlinear equation," then what hope do we have in this matter of Bezier intersection? The key is to recognize that we need a good, specific (as opposed to general) method, specific to the Bezier equations. Indeed, there is another algorithm altogether, which avoids the inherent numerical confusion of bisection, and which allows us to find the peaks, no more and no less. I am not going to reveal that unpublished algorithm here, but I will give you a hint: one avoids the mire of a swamp by reformulating it as a large set of problems that have a small number of fast, closedform solutions.
http://truetex.com/bezint.htm
http://www.magicsoftware.com/Commun...es.Mar2001.txt
http://www.cs.unc.edu/~yanghua/Assignment3.htm
http://www.math.niu.edu/~rusin/knownmath/99/meets
http://www.tinaja.com/cubic01.asp
http://www.gamasutra.com/features/19...deloura_01.htm
http://www.cs.huji.ac.il/~arik/java/ex2/
http://www.tinaja.com/text/bezchord.html
http://www.engineering.uiowa.edu/~am...apers/CAD1.pdf
http://www.magicsoftware.com/Docume...OfEllipses.pdf
http://www.whizkidtech.net/bezier/circle/
http://chattyfig.figleaf.com/ezmlm/e...inefbenjodddmo // Penner
http://www.timotheegroleau.com/Flash...r_in_flash.htm // Groleau
Richard
[Edited by Dickee on 09052002 at 08:34 AM]

madskool.wordpress.com
Hmmm
Thanks Dickie. I suspected it wasn't easy and that I may need to iterate to an approximation.
I devised a quick and dirty method. (but haven't tested it extensively yet). My method only needs be as accurate as the eye can perceive on a screen.
I know how to arrive at the intersection of a quadratic bezier curve and a straight line.
y=mx+c
y=at^2+bt+d
x=et^2+ft+g
so solve: (ame)t^2+(bmf)t+(dmgc)=0
So my solution is to approximate the second quadratic bezier curve by straight line segments.
(by the way  I'm using quadratic curves so I can utilise curveTo to draw them).

Hey brutfood!
OK, I'm not finished yet, but I thought I would post this as is to see if anyone else can come up with more or better code to increase intersect accuracy. I've switched to Lifaros' (we'rehere forum id) 'bezierLibLifaros.as' to map quadratic bezier segments drawn with Flash's 'curveTo' function, since you stated that your explorations will concentrate on this function.
I'm using arrays, with each quadratic bezier populating it's array with 120 points along it's path, and the length of each bezier segment determining the accuracy factor, which is used in an equation to place intersect flags. At present, results range from quite accurate, to no flags showing in spite of actual intersections onstage, to many flags showing false but close coordinates due to 'level' and 'tolerance' settings, to 'over the time limit, freeze the progy' if 'level' is set too high!
I've used framebased animation to show the progression through the coordinates, so speed of the app to reach the final computation is slower than what could be accomplished. Both 'level' and 'factor' can be adjusted onscreen, so please experiment with different values to see if more accuracy can be obtained. After altering the variables, clicking on any of the control points will start the animation and preserve the bezier positioning (the points are also draggable), and clicking the button will refresh with new randomly placed control points.
I've also included Gary Fixler's 'nearBezFixler.as' in the zip file, which I plan to explore next to increase intersect flag accuracy. His .as file uses recursive bisection of the bezier curve to find the nearest point to the target point, and I think it will be adaptable for 2 bezier curves as well.
I've also been working on a new cubicBezierIntersect.fla, which breaks up the cubic into quadratic segments, drawn with 'curveTo'. But I want to increase accuracy on the quadratic file first, then apply the algorithm to the cubic file, since the more complex cubic file will also need to flag 'selfintersecting' points.
edit
I've been exploring various scenarios, and I made a file that uses 'hitTest' instead of array comparison. The file also includes commentedout code on frame 2 using Gary Fixler's 'nearBezFixler.as' (found in the zip above) that uses trace for the results. You can compare both ways in the authoring environment by uncommenting the code, but you'll need to modify 'level' to about 4050 instead of 200, or the file will stall. I haven't explored factoring 'level' via 'quadLength' to get more accurate results, thus this edit rather than a new post.
The hitTest method's code can be simplified much more than this ... eg. no need for the includes if 'quadLength' is not used to factor 'level'. HitTest is proving to be much faster, but not as accurate ... I've used 'false' in the arguments, so there is no fudging of the points. We muster onward ...
..edit2..
Still not satisfied with accuracy, so I've just updated the file from v7 to v10 ... but it's much better using a level factor based on each bezier's length. Still using the 'hitTest' routine, and I've updated the commentedout 'nrstBezPt()' code, but it doesn't work as yet. Also, I've updated the Fixler.as file, so I've zipped it up in v10.
http://members.shaw.ca/flashmath101/...ntersect10.swf
http://members.shaw.ca/flashmath101/...ntersect10.zip
Richard
[Edited by Dickee on 09152002 at 02:22 AM]
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
