Java-Gaming.org Hi !
 Featured games (91) games approved by the League of Dukes Games in Showcase (757) Games in Android Showcase (229) games submitted by our members Games in WIP (844) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Moving at a constant speed along a Bézier Curve  (Read 10154 times) 0 Members and 1 Guest are viewing this topic.
kappa
« League of Dukes »

JGO Kernel

Medals: 120
Projects: 15

★★★★★

 « Posted 2014-05-04 17:09:45 »

I've been playing with quadratic bezier curves recently, its easy enough to draw and get the points along it using something like:

 1  2 `float x = (1 - t) * (1 - t) * startX + 2 * (1 - t) * t * cx + t * t * endX;float y = (1 - t) * (1 - t) * startY + 2 * (1 - t) * t * cy + t * t * endY;`

Where start/end is the beginning/end point on the curve and c being the control point.

t is a value between 0 and 1 which can be used to move along the curve, 0 being the start and 1 being the end, however the problem is that this value can't be used to move along the curve at a constant speed since t=0.5 is not necessarily at the middle of the curve or t=0.25 the first quarter.

I've got an approximation of the length of the curve using

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22 `public float getApproxLength() {      float t = 0;      length = 0; // reset length            float oldX = startX;      float oldY = startY;            // scroll through curve and update length      for (int i = 0; i < 100; i++) {         t += 0.01f;                  float x = (1 - t) * (1 - t) * startX + 2 * (1 - t) * t * cx1 + t * t * endX;         float y = (1 - t) * (1 - t) * startY + 2 * (1 - t) * t * cy1 + t * t * endY;                  length += getLineLength(x, y, oldX, oldY);                  oldX = x;         oldY = y;      }            return length;   }`

Are there any easy solutions to achieve this other than to use a whole ton of look up tables and memory? doesn't need to be super accurate just something good enough to get a decent constant looking movement along the curve.
Riven

« JGO Overlord »

Medals: 1341
Projects: 4
Exp: 16 years

 « Reply #1 - Posted 2014-05-04 17:59:37 »

You used my code, about 6 years ago, which used a whole ton of lookup tables and memory. There are no shortcuts, as far as I know.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
philfrei
 « Reply #2 - Posted 2014-05-04 18:07:41 »

Interesting problem!

This may be computationally too intensive, but perhaps use some sort of binary search algorithm to test the distance travelled for a given fraction of t? In other words, measure the distance for a given t-fraction. If too large (or too small) vary and try again to hit the target distance within a given tolerance.

There may be optimizations to help this algorithm, like only using the squares not the square roots in the distance calculation (which will make overshooting a bit less accurate than undershooting [do I have that backwards?], but maybe still good enough), and starting the search with the previous t-fraction or a t-fraction with the increment or decrement previously successful.

[EDIT: maybe I didn't fully grasp the question. I was looking at it via having a set distance you wish to travel per frame, and thus was not worried about the problem of computing the total distance of the curve.]

[EDIT2: Roquen's article looks like a bullseye. But I had another thought that maybe is worthless, but here goes: convert the bezier curve into a GeneralPath for transversal purposes?]

Roquen

JGO Kernel

Medals: 517

 « Reply #3 - Posted 2014-05-04 19:45:55 »

http://homepage.cs.uiowa.edu/~kearney/pubs/CurvesAndSurfacesArcLength.pdf
kappa
« League of Dukes »

JGO Kernel

Medals: 120
Projects: 15

★★★★★

 « Reply #4 - Posted 2014-05-05 10:55:01 »

You used my code, about 6 years ago, which used a whole ton of lookup tables and memory. There are no shortcuts, as far as I know.
Yup remember that super awesome spline class well (still have it in my workspace), used it many times and would probably use it again here if I could, however limited to working with quadratic bezier curves directly in this case.

Cool, that looks like pretty much what I need, some pretty dense math representation of the formula's there though, will see if I can write some code from it.
Riven

« JGO Overlord »

Medals: 1341
Projects: 4
Exp: 16 years

 « Reply #5 - Posted 2014-05-05 11:12:37 »

What's the use case of these curves? Presumably simply:
Quote
move along the curve at a constant speed

Especially when travelling along the curve (not requiring random access) it seems that making something stateful, that remembers its last t and distance, is 'good enough' (as in: fast and accurate)

 1  2 `traveller = new CurveTraveller(curve);Vec2 pos = traveller.advance(1.2);`

There would be no lookup tables involed.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
delt0r

JGO Wizard

Medals: 143
Exp: 18 years

Computers can do that?

 « Reply #6 - Posted 2014-05-05 14:51:37 »

I have done this accurately enough and fairly fast with just short 3rd order Gaussian quadrature integration, and doing a stepwise pre integration when the curve is created for a "global scale". Its plenty accurate enough for games. I use Hermite splines.

There is no short cut, there are proofs of this out there that there is no simple formula.

I have no special talents. I am only passionately curious.--Albert Einstein
kappa
« League of Dukes »

JGO Kernel

Medals: 120
Projects: 15

★★★★★

 « Reply #7 - Posted 2014-05-05 15:11:25 »

I use Hermite splines.
just curious, why Hermite curves over Bézier curves? Noticed a lot of people using them, is there some extra advantage in using them?
Roquen

JGO Kernel

Medals: 517

 « Reply #8 - Posted 2014-05-05 19:21:10 »

Quote
I use Hermite splines.
This.  Very much this.  I'd go so far as to say if you're thinking about a problem and "spline?" pops in your head then the next thought is hopefully "cubic hermite?"

Quote
just curious, why Hermite curves over Bézier curves?
Dead simple to design on-the-fly.  Cubic is end-points and end-point tangents (or direction & speed...not saying velocity because of parameterization).  The down side of cubic hermite is that they are only first order continuous. Not a big deal in most situations.  The basis of cubic hermite is what Perlin's original ease function was and the quintic for improved noise.

Wintermuet

Innocent Bystander

 « Reply #9 - Posted 2014-05-19 06:36:11 »

On line 224 of this procedural map generator I wrote, there is the math for a carefully incremented Bezier if you'd like to check it out.

http://pastebin.com/1Jb6dHTk

It draws beziers paths across a grid, which was kinda hard to figure out for me.
Here is the approximate end result:
Pages: [1]
 ignore  |  Print

 EgonOlsen (79 views) 2018-06-10 19:43:48 EgonOlsen (59 views) 2018-06-10 19:43:44 EgonOlsen (78 views) 2018-06-10 19:43:20 DesertCoockie (261 views) 2018-05-13 18:23:11 nelsongames (160 views) 2018-04-24 18:15:36 nelsongames (158 views) 2018-04-24 18:14:32 ivj94 (901 views) 2018-03-24 14:47:39 ivj94 (162 views) 2018-03-24 14:46:31 ivj94 (813 views) 2018-03-24 14:43:53 Solater (177 views) 2018-03-17 05:04:08
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org