12 Replies Latest reply on Aug 17, 2007 11:50 AM by Rothrock

    [Math] Finding points along a bezier curve

    abeall Level 3
      This isn't specific to ActionScript.

      I have the 4 points that make up a http://en.wikipedia.org/wiki/B%C3%A9zier_curve. I want to:
      1) Determine the length of the bezier curve
      2) Determine a point along the bezier curve based on a distance from the start point
      3) Determine the angle/direction/orientation of a point along the bezier curve - basically like a motion guide does.

      I can determine a point along the bezier curve based on a percentage, using http://pupius.co.uk/download/articles/bezier_curves/ or AS3 fl.motion.BezierSegment, but I haven't solved any of the above 3.

      If any math whiz out there has any advice, I'd greatly appreciate it. Thanks!
        • 1. Re: [Math] Finding points along a bezier curve
          Rothrock Level 5
          It seems there is no easy answer closed form answer to 1 and 2. Pretty much everyone does an estimation of many short line segments.

          And 3 is just the animated blue (tangent) line in that wiki page. Exactly how to calculate that I'm not sure.
          • 2. Re: [Math] Finding points along a bezier curve
            Greg Dove Level 4
            By coincidence I was looking at a bezier stuff yesterday trying to understand why something I was doing wasn't working as it should. Here's where I found what I needed to know:

            http://timotheegroleau.com/Flash/articles/cubic_bezier_in_flash.htm

            I'm not sure about 1 or 2 (there are some cubic bezier methods in here that also show a point at a percentage /proportion along the curve - I think - didn't try them)

            But I think there is a getCubicTgt method in the file that might do 3 above for cubic beziers... in the bezier_lib.as link off the above page.

            • 3. Re: [Math] Finding points along a bezier curve
              Rothrock Level 5
              GWD, I'm imagining the percent is the percentage of the line as described in the Generic MidPoint approach. In other words, (referring to the diagram in that section) the percentage of Pa and Pb along their routes, but it won't be the same percentage that Pc is along its route. It could be for certain "less interesting" curves, but in most cases they won't be the same.

              Depending upon how precises a tangent is needed, you could just use the line between any two arbitrarily close percentages, say .5 and .5001. I used the following code to draw a nice bezier. I've got two small dots in the library set for export "Dot1" and "Dot2." I like different colors. I've also got a long thin line called tangent, but it easily could have been a car or a bird or what have you that was supposed to be oriented to the path.
              • 4. Re: [Math] Finding points along a bezier curve
                Greg Dove Level 4
                @Rothrock : I really don't know much about beziers or the math involved - I'm pretty sure you and kglad are way ahead of me there....and so I didn't understand how accurate anything was in the equations I saw in that code (although I didn't really attempt to either....I enjoyed reading that article but probably only retained the implications for CPU and accuracy tradeoffs!) - I noticed the getTangent method and it seemed like it might be relevant for abeall - but perhaps it isn't.

                FYI All I was trying to do yesterday was solve a problem converting Cubic to Quad beziers for the drawing API which occurred with someone else's conversion code for a specific cubic bezier type - actually I think it was a just for quadratic beziers masquerading as a cubic - where one of the control points of the cubic bezier was equal to one of the end points - or at least that's how I 'solved' it in the end - I'm not even sure if that's correct, but I haven't noticed any visual difference for what I was doing.
                • 5. Re: [Math] Finding points along a bezier curve
                  Rothrock Level 5
                  Yeah that link look great and I'm going to download the as and see what I can see. My tangent approach would be quick and easy to implement, but probably has a whole set of cases where it would fail awfully. So it really depends upon the purpose. I'm going to start with the getTangent method in those files.

                  I am totally in love with Beziers and would nominate them as the best thing that came out of the 20th Century. (present company excluded of course!) But I don't really understand the math all that well myself. A little more all the time…

                  Sounds like you had an interesting problem. My current interest in Beziers is for a given x what is the y? It can be done. Andre Michele has done it – in spades – but I want to try and figure it out on my own.

                  http://lab.andre-michelle.com/bezier-clipping
                  • 6. Re: [Math] Finding points along a bezier curve
                    Rothrock Level 5
                    Don't know why my code didn't attach.
                    • 7. Re: [Math] Finding points along a bezier curve
                      Greg Dove Level 4
                      Ahh... if you like all that kinda stuff, you should probably take a look inside Alex Uhlman's animationpackage too - that's what I've just been using. Its great. Its got motion along path, bezier utilities etc.
                      http://www.alex-uhlmann.de/flash/animationpackage/ap2/index.htm

                      As for beziers, I understand your amorous inclinations towards them, but I kinda prefer them for what they do and not what they are (even though they're really clever and I also find curves quite pleasing in general, lol). Mostly that means I don't have to try to understand them too much and it leaves more room for empty space in my head. I guess I left my math too far behind me. lol
                      • 8. Re: [Math] Finding points along a bezier curve
                        abeall Level 3
                        Timothée's article is a real life saver, he even provides the .fla source so that I can render cubic beziers using Flash's funky quadratic bezier API. I don't think I could have figured that out on my own.

                        As far as what I'm trying to do now, it looks like you're right, Rothrock -- after some heavy googling, it appears there is no straight forward formula to calculate any of those(a surprise to me -- I thought math could solve anything? :- ). So, in order to do those three things, I'm going to:
                        1) Step through using a small increment for 't' to create a series of small lines, and add up all line lengths(egad!)
                        2) At some point during the above sequence, when the current line length sum is greater than the desired curve length, I know the desired point is between the current point and the previous point along the bezier curve. I can either drill down further between those two points, or approximate it as being one of those two points.
                        3) Angle will just be determined by using the line sequence above. Any given point's angle would be the angle between it and the previous point.

                        Result:
                        http://abeall.com/files/flash/tests/cubicBeziers.swf

                        Source(CS3, but AS2 -- warning, it's messy):
                        http://abeall.com/files/flash/tests/cubicBeziers.fla

                        I wish there was a smarter, more adaptive way to determine a given point at a certain distance along a bezier other than stepping through at a small increment, but I can't think of any. I would want to subdivide in half recursively, but because the distance would be measured as a straight line it wouldn't be accurate at all, and would completely mess up dealing with curves that overlap itself. I guess i could still make it step through adaptively, say walk at an increment of .1, then when I overstep, back up and walk at an increment of .01, and so forth. I'm seeing this project suddenly becoming much more staining on the CPU, though!
                        • 9. Re: [Math] Finding points along a bezier curve
                          Greg Dove Level 4
                          @abeall : If you convert cubic to quads (within acceptable limits) as per the the method outlined, then quads don't overlap - do they?. So doing it this way should avoid that risk.... but not the CPU one.
                          • 10. Re: [Math] Finding points along a bezier curve
                            abeall Level 3
                            Sorry guys, I wrote that and in the meantime you all had a whole conversation a missed. ;-) Reading it now. You're mostly talking over my head. :-)

                            As far as converting to quads... you're right, they wouldn't overlap. However, I really need to know the distance along a cubic bezier curve, not a quad. Not sure how I would get that all to work together...
                            • 11. Re: [Math] Finding points along a bezier curve
                              Greg Dove Level 4
                              I don't know how much accuracy you would lose... but the point of using quads (apart from being able to draw them easier in flash) might be that you can measure each quad easier than the cubic (because they don't overlap). So split the cubic into quads... using the midpoint method outlined in the article... measure each quad with a segment approach and add them all up to approximate the cubic they came from. I have no idea if it makes sense... its just that I read the article recently and its the question I would ask myself. For the record when I'm suggesting it I am also talking over my own head. :-)
                              • 12. Re: [Math] Finding points along a bezier curve
                                Rothrock Level 5
                                I was blown away when I found out there isn't a simple equation for the perimeter of an ellipse. I mean really, something as "simple" as an ellipse? c'mon!

                                abeall – Nice example. I like it. And yup, that is pretty much the only solution I can think of too.

                                GWD – I will have to take a look at that package. Seems like there are a lot of goodies in there.