   cubic bezier calculus
  Hey, guys.I'm reparameterizing a cubic Bezier curve such that I can calculate points on it in terms of distance along the curve from the first control point.  Why bother with this?  Well, for those who do not know, there are many reasons, a good one being that the velocity/acceleration of bodies traveling along an un-reparameterized bezier curve will not be linear, i.e. even though the parameter t may exhibit a known behavior, such as a particular velocity/acceleration, the distance of bodies travelling along the curve based on the parameter t may or may not be proportional to t at all times and they will thus tend to speed up or slow down at times based on their position in the curve.  Heh, it sucks when that happens...  Personally I am making a curved text renderer, which means drawing normal characters about a curve instead of a straight line.  In order to properly space the characters along the curve, I must reparametrize the curve in terms of length.It works great for short curves, and most of the way through long curves, but at the end of a long, highly curved curve, the parameterization starts to stretch and again become dependant on the un-arc-length-reparameterized curve.  Ok, here's the high level overview w/o the specific algorithms used for the individual parts:find s in terms of t*invert this function, to describe t in terms of s*find t for each character, based on the width of all previous characters.* = there is no closed form solution, so approximation is necessarySpecifics:Finding s here is all calculus, and there is no closed form solution.  s(t) is basically the integral, from 0 to t, of the magnitude of the derivative of the curve...  It is way too hard to type in here, so if that english isn't enough for you, then don't worry about it, cuz this part isn't that important.  The important part is that the only way to find s in terms of t is to approximate this integral.  The closest approximations I've found are using Simpson's rule (found in HS and college calc texts), or Legendre-Gauss quadrature, both of which are prohibitively slow.  After a google search I found a beautiful 1996 paper by Marcelo Walter and Alain Fournier here.  Now this is some heavy duty real-time!The basic premiss these guys use is to evaluate s(t) in a few discrete places, using the -slow- method, and, from these, construct a 2nd bezier curve ("a length curve") to approximate the relationship between t and s(t).  The length curve is forced to act like a true function (x = t, in all cases).  This is great because it reduces finding the length to any arbitrary point t to a closed form function s(t) where s(t) is the y of LengthCurve( t ).Alright, so here you have a way to get the length at any point on the curve.  This function needs to be inverted, so that t can be found in terms of s.  Again, there is no analytical solution to this, so you have to use another approximation method (their paper said that the Newton-Raphson method would work best).Ok, so, now it is possible to figure out t in terms of s, so all i have to do is draw a character, find it's length along the curve, then find the t value for that next position.  This works great at first, but starts to stretch out...Things I figure are wrong:  1) there is too much error involved in the approximations, though the paper said < 8.3%, i believe.2) my math is wrong3) this method won't work for all situations.Anybody ever do anything like this?  Have any ideas?  Should I post the code?  I always hate it when people say, "here debug my code for me, because I can't" and post 1000 lines of illegible, intangible c.  I would rather work on concepts, but if posting my c code will help, I'll be glad to.  // EDIT: btw, here is a screenshot:Thank you for your bandwidth.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~Succinct Demos Online~    Edited by - Succinct on May 19, 2001 3:40:55 PM  
  Let me see if I understand the problem correctly. You want to find a value of t that is a specific distance along the curve from another value of t? Is this a curve in 2D or 3D? It is a bit late tonight, but I''ll try to find the time to play with the equations tomorrow. I think I have a basic understanding of what you are doing, but I need to play with the formulas a bit to understand the details.  ;  Ok, I understand a little bit better. I don''t understand the reparameterization and need to read the article you referance. I found a discussion of the problem in Computer Graphics & Geometric Modeling by David Salomon. His approach was to create a polyline approximating the curve and use it to approximate the distance along the curve. I assume that is what the article means by lookup tables.  