Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (497)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Moving at a constant speed along a Bézier Curve  (Read 1705 times)
0 Members and 1 Guest are viewing this topic.
Offline kappa
« League of Dukes »

JGO Kernel


Medals: 77
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.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline 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?]

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #3 - Posted 2014-05-04 19:45:55 »

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

JGO Kernel


Medals: 77
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.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 799
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Offline delt0r

JGO Knight


Medals: 27
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
Offline kappa
« League of Dukes »

JGO Kernel


Medals: 77
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?
Offline 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. 



Offline 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  
 
 

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

BurntPizza (22 views)
2014-09-19 03:14:18

Dwinin (35 views)
2014-09-12 09:08:26

Norakomi (62 views)
2014-09-10 13:57:51

TehJavaDev (90 views)
2014-09-10 06:39:09

Tekkerue (44 views)
2014-09-09 02:24:56

mitcheeb (65 views)
2014-09-08 06:06:29

BurntPizza (48 views)
2014-09-07 01:13:42

Longarmx (35 views)
2014-09-07 01:12:14

Longarmx (40 views)
2014-09-07 01:11:22

Longarmx (37 views)
2014-09-07 01:10:19
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!