Post Reply 
Constant speed
04-04-2016, 10:33 PM
Post: #1
Constant speed
I recently came accross this simple question which I found difficult to answer.
Consider the very common function y=sin(x). When you draw it with a computer, you see that the plot is accelerating or decelerating. Nothing surprising since the derivate of sin is cos.
Now suppose you want to do an animation showing an ant walking on your sinus at constant speed. What would then be the equation to draw this?
Can you find a general answer applicable for any equation?
Find all posts by this user
Quote this message in a reply
04-05-2016, 07:01 AM
Post: #2
RE: Constant speed
Maybe the arc length of sin(x) can be the first step to the solution?

s= \(\int_{0}^{2\pi} \sqrt{1+cos^2(x)} dx \)

Bernhard

That's one small step for a man - one giant leap for mankind.
Find all posts by this user
Quote this message in a reply
04-05-2016, 07:19 AM (This post was last modified: 04-05-2016 07:24 AM by Tugdual.)
Post: #3
RE: Constant speed
For those who wonder, I have actually found a pretty comprehensive answer here
https://www.geometrictools.com/Documenta...dSpeed.pdf

This little problem surprises me, because a very simple and natural question related to our everyday life (ex: driving a car on a road) ends up into something much more complex than expected. I actually started thinking about this question when I played the PopCap game Zuma with balls rolling on a curve.
Find all posts by this user
Quote this message in a reply
04-05-2016, 11:14 AM
Post: #4
RE: Constant speed
(04-05-2016 07:19 AM)Tugdual Wrote:  I actually started thinking about this question when I played the PopCap game Zuma with balls rolling on a curve.

You're not the only one that's a complete nerd even while playing video games. Geometry Wars always gets me thinking about logarithms and exponential growth...
Visit this user's website Find all posts by this user
Quote this message in a reply
04-05-2016, 06:04 PM
Post: #5
RE: Constant speed
(04-05-2016 11:14 AM)Dave Britten Wrote:  
(04-05-2016 07:19 AM)Tugdual Wrote:  I actually started thinking about this question when I played the PopCap game Zuma with balls rolling on a curve.

You're not the only one that's a complete nerd even while playing video games. Geometry Wars always gets me thinking about logarithms and exponential growth...
Glad to know I'm not alone Smile
How about the liquid flow simulation in Pixel Junk Shooter? There is some material on the net explaining how this was done and it is really interesting. Game makers are very technical and knowledgeable people.
Find all posts by this user
Quote this message in a reply
04-06-2016, 11:16 AM
Post: #6
RE: Constant speed
(04-05-2016 06:04 PM)Tugdual Wrote:  Glad to know I'm not alone Smile
How about the liquid flow simulation in Pixel Junk Shooter? There is some material on the net explaining how this was done and it is really interesting. Game makers are very technical and knowledgeable people.

Yeah, that one always makes my head spin when I'm playing it. I'm guessing it's some kind of particle system under the hood, but I'm definitely not a game physics programmer. Just doing a decent Breakout engine without the ball passing through solid objects is tough enough.
Visit this user's website Find all posts by this user
Quote this message in a reply
04-07-2016, 06:13 AM
Post: #7
RE: Constant speed
(04-06-2016 11:16 AM)Dave Britten Wrote:  Yeah, that one always makes my head spin when I'm playing it. I'm guessing it's some kind of particle system under the hood, but I'm definitely not a game physics programmer. Just doing a decent Breakout engine without the ball passing through solid objects is tough enough.
Some reading for you:
http://fumufumu.q-games.com/gdc2010/shooterGDC.pdf

This document describes the version on PS3 operating with cells. Not sure how the PC version was done, it must have gone through heavy reprogramming.
Amazing stuff, truly.
Find all posts by this user
Quote this message in a reply
04-07-2016, 11:16 AM
Post: #8
RE: Constant speed
(04-07-2016 06:13 AM)Tugdual Wrote:  Some reading for you:
http://fumufumu.q-games.com/gdc2010/shooterGDC.pdf

This document describes the version on PS3 operating with cells. Not sure how the PC version was done, it must have gone through heavy reprogramming.
Amazing stuff, truly.

That's pretty close to how I imagined they were doing it: particles with fuzzy collision detection, to oversimplify it.

The PS3's Cell processor is something like a 7-way parallel chip, and I've heard it described as resembling programming a DSP. The PC version probably gets away with running the simulation on whatever (more recent) CPU cores it has available, or maybe offloading some of it to the GPU. I'm guessing it's the former, since they also got Shooter running on the Vita, which is nowhere near as powerful as the PS3 in terms of number crunching.
Visit this user's website Find all posts by this user
Quote this message in a reply
04-11-2016, 02:01 PM
Post: #9
RE: Constant speed
The function \(y=sin(x)\) has the slope \({dy\over dx}=cos(x)\) which yields
\[dy=cos(x) \cdot dx\]
The arc length of a segment with components \(dx\) by \(dy\) is given by
\[ds = \sqrt{dx^2+dy^2}\]
Substituting \(dy\) into the above yields
\[ds = \sqrt{dx^2+(cos(x) \cdot dx)^2}\]
and solving for \(dx\) gives
\[dx = {ds \over \sqrt{cos(x)^2 + 1}}\]
For any station \(x\) this defines the required \(dx\) to obtain the desired \(ds\). Useful for plotting curves using constant segment lengths or constant speed driving on a curved road ;-)
The "General" answer depends on the equation - not all have simple Solutions for \(dx\). Then some nonlinear solver resp. iteration would be needed.
Find all posts by this user
Quote this message in a reply
04-11-2016, 03:53 PM
Post: #10
RE: Constant speed
(04-11-2016 02:01 PM)Martin Hepperle Wrote:  The function \(y=sin(x)\) has the slope \({dy\over dx}=cos(x)\) which yields
\[dy=cos(x) \cdot dx\]
The arc length of a segment with components \(dx\) by \(dy\) is given by
\[ds = \sqrt{dx^2+dy^2}\]
Substituting \(dy\) into the above yields
\[ds = \sqrt{dx^2+(cos(x) \cdot dx)^2}\]
and solving for \(dx\) gives
\[dx = {ds \over \sqrt{cos(x)^2 + 1}}\]
For any station \(x\) this defines the required \(dx\) to obtain the desired \(ds\). Useful for plotting curves using constant segment lengths or constant speed driving on a curved road ;-)
The "General" answer depends on the equation - not all have simple Solutions for \(dx\). Then some nonlinear solver resp. iteration would be needed.
Thanks Martin, sounds like a good answer but I struggle with further conclusions.
First, at constant speed, I would assume that ds/dt = 0 so dx = 0?
Other question is how do you move from your expressions to a parametric equation for x(t) and y(t) over the time?
Find all posts by this user
Quote this message in a reply
04-13-2016, 03:29 PM (This post was last modified: 04-13-2016 03:30 PM by Martin Hepperle.)
Post: #11
RE: Constant speed
(04-11-2016 03:53 PM)Tugdual Wrote:  ...
Thanks Martin, sounds like a good answer but I struggle with further conclusions.
First, at constant speed, I would assume that ds/dt = 0 so dx = 0?
Other question is how do you move from your expressions to a parametric equation for x(t) and y(t) over the time?

Almost ... constant speed would be \(v = {ds \over dt} = const.\) not zero.
where: \(ds\) ... distance and, \(dt\) ... time interval.

Using a given (constant) speed \(v\) and a (user selected) time step \(dt\) you would determine \(ds = v \cdot dt\) and then use the equation above to find \(dx\).
You would start at e.g. time \(t=0\) at position \(x=0\), calculate \(dx\) for the given speed, march to \(x=x+dx\) and plot \(f(x)\) at the new point (for time \(t=t+dt\). Then repeat for the next time step.

My simple equations will work as long as the function is monotonic \(y=f(x)\). For a parametric curve (e.g. a circle) one would have to rewrite with the parameter \(t\) or \(s\) (arc length) to obtain \(dx\) as well as \(dy\) as a result.
This is left as an exercise to the inclined reader ... ;-)

Martin
Find all posts by this user
Quote this message in a reply
04-13-2016, 06:30 PM
Post: #12
RE: Constant speed
(04-13-2016 03:29 PM)Martin Hepperle Wrote:  Almost ... constant speed would be \(v = {ds \over dt} = const.\) not zero.
where: \(ds\) ... distance and, \(dt\) ... time interval.
oOops, my bad, I'm definitely rusty.

Thanks for the clarification Martin!
Find all posts by this user
Quote this message in a reply
04-18-2016, 07:27 AM (This post was last modified: 04-18-2016 08:07 AM by Martin Hepperle.)
Post: #13
RE: Constant speed
... and for illustration ... a Series-80 BASIC implementation for drawing a curve at "constant speed". You supply the two functions for x(p) and y(p) at the end of the code.

Besides the pure plotting data some additional values are calculated (e.g. the arc length of the curve). For speed you could strip some code and I also have left in some duplicated subexpressions for clarity.

The ticks option can be used to draw monorail tracks if you want to describe the track layout mathematically...

Code:

10 ! HP-85
20 ! Constant speed plotter
30 ! and path length integrator
40 ! for parametric function
50 ! Martin Hepperle, 2016 
60 !
70 ! initial values  
80 T=0 ! time
90 S=0 ! distance
100 P=0 ! parameter at time T
110 V=.5 ! velocity (const.)
120 ! integration parameters
130 T0=.1 ! time step
140 C0=.01 ! fin. diff. step
150 P9=4*PI ! end of parameter
160 ! distance for dt (const.)
170 S0=V*T0
180 C2=2*C0 ! speed up calc.
190 ! -- isotropic plotting --
200 GCLEAR
210 SCALE -(1.1*RATIO),1.1*RATIO,-1.1,1.1
220 MOVE FNX(P),FNY(P)
230 ! integration loop       
240 ! derivative dx/dp
250 D0=(FNX(P+C0)-FNX(P-C0))/C2
260 ! derivative dy/dp
270 D1=(FNY(P+C0)-FNY(P-C0))/C2
280 ! calculate dp
290 ! required for given dt
300 P0=S0/SQR(D0^2+D1^2)
310 ! -- plotting --
320 DRAW FNX(P),FNY(P)
330 ! --- ticks (optional)
340 ! derivative dy/dx
350 D2=D1/D0
360 F=ATN(D2)
370 F0=SIN(F)*.03
380 F1=COS(F)*.03
390 MOVE FNX(P)-F0,FNY(P)+F1
400 DRAW FNX(P)+F0,FNY(P)-F1
410 MOVE FNX(P),FNY(P)
420 ! --- end of ticks
430 ! advance to next
440 P=P+P0 ! parameter
450 T=T+T0 ! time
460 S=S+S0 ! distance so far
470 ! check for termination
480 IF P<=P9 THEN 250
490 PRINT "End Time  t=";T
500 PRINT "Distance  s=";S
510 PRINT "Parameter p=";P
520 ! accuracy check:
530 ! circle: sin(p),cos(p)
540 ! S/PI should be 2.0
550 PRINT "s/PI=";S/PI
560 END
570 ! ----------------
580 ! function x(p)
590 DEF FNX(P)
600 FNX=SIN(P)
610 FN END
620 ! ----------------
630 ! function y(p)
640 DEF FNY(P)
650 FNY=COS(P*.5)
660 FN END
670 ! ----------------
680 END

Of course, one could replace \(arctan()\), \(sin()\) and \(cos()\) by \(sqrt()\) expressions and simplify further.
Then you could replace
Code:

350 ! deleted
360 ! deleted
370 F0=D1*P0/S0*.03
380 F1=D0*P0/S0*.03
which leaves further room for simplification (common subexpressions ) but you must be aware of cases where \(dx/dp=0\) or \(dy/dp=0\).
The implementation will also hang if both derivatives are zero at the same time (singular point).

Martin
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)