Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (575) Games in Android Showcase (154) games submitted by our members Games in WIP (623) 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 2538 times) 0 Members and 1 Guest are viewing this topic.
kappa
« League of Dukes »

JGO Kernel

Medals: 85
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
« League of Dukes »

« JGO Overlord »

Medals: 954
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?]

"We all secretly believe we are right about everything and, by extension, we are all wrong." W. Storr, The Unpersuadables
Roquen
 « 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: 85
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
« League of Dukes »

« JGO Overlord »

Medals: 954
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 Knight

Medals: 33
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: 85
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
 « 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

You cannot reply to this message, because it is very, very old.

 BurntPizza (28 views) 2015-04-23 03:42:11 theagentd (32 views) 2015-04-22 16:23:07 Riven (45 views) 2015-04-16 10:48:47 Duke0200 (56 views) 2015-04-16 01:59:01 Fairy Tailz (40 views) 2015-04-14 20:13:12 Riven (42 views) 2015-04-12 21:36:37 bus hotdog (58 views) 2015-04-10 02:39:32 CopyableCougar4 (63 views) 2015-04-10 00:51:04 BurntPizza (62 views) 2015-04-06 22:06:58 ags1 (65 views) 2015-04-02 10:58:48
 theagentd 23x BurntPizza 16x wessles 15x 65K 11x alwex 11x kingroka123 11x Rayvolution 8x kevglass 8x Olo 7x ra4king 7x Ecumene 7x KevinWorkman 7x Roquen 7x chrislo27 7x Riven 7x Hanksha 7x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 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