Sometimes it’s the little things that make all the difference in an application. That’s probably why I’ve rewritten our kinetic scrolling in some fashion three different times. Kinetic scrolling is the animation you see on touchscreen phones when you move your finger across a web page and let go. The content will continue to scroll for a couple of seconds, slowing down to a halt at the end. This gives scrolling a feeling of physical weight, as if you had pushed a coin across your desktop and friction slowed it to a stop. It’s one of those algorithms anyone can implement, but few manage to perfect.
Fennec’s kinetic scroller needed some tweaking, though I didn’t start out knowing exactly what it needed. As I played with a few algorithms I eventually came up with three goals:
- Predictability. The same gesture should roughly get you exactly the same distance every time, independent of outside factors like frame skipping.
- Smoothness. Your eyes are good at noticing changes in distance. If a frame or two is out of step, you will notice or possibly even see something unexpected! More on that later.
- Speed. The total time the animation takes should be reigned in; the animation is there to give weight to the content with subtlety, and stay out of the way.
Each goal isn’t so hard in itself, but I found when I focused on one the other two would slip out of my grasp. As far as I’ve seen, only the iPhone really gets it right. You can spin an hour or minute scroll wheel with amazing consistency once you get the hang of it. Android gets it all wrong. The friction is so low that the animation can last forever. If Android misses a few beats while you are dragging your fingers, it will interpret that as a super-fast finger pan and will set your initial velocity to infinity minus one. Android also has poor responsiveness: sometimes on my Cliq I don’t know if I’ve panned until I’ve let go of my finger. By then it’s far too late.
My work focused on changing how we determine the distance moved in every frame of the animation. In Fennec, we keep it simple and assume we can get away with friction being a constant deceleration. Given an initial velocity and deceleration rate, how do we get from our start position to our end position?
Previous solution: Newtonian approximations with fixed dt
Don’t let any of those words scare you if your math is a little rusty. Think of the position of the scrollbox as a function of time. At the beginning, position(t=0) is where the scrollbox was at before moving. At some final time, the scrollbox’s position will have settled to a stop further down the page. Newton’s approximation is just a very simple application of a derivative:
# general application
f(x+dx)=f(x) + dx*f'(dx)
# physics application
# note: velocity is the derivative of position
pos(t+dt)=pos(t) + dt*vel(t)
vel(t+dt)=vel(t) + dt*acc
Derivatives tell how a function’s value changes. For this algorithm, a derivative helps approximate a function’s value at nearby places. If I know the velocity at a given time (vel(t)) and the position at a given time (pos(t)), I can make a really good guess about what the position will be at a small time increment from now (pos(t+dt)). Set dt to a fixed constant (like if the position is updating every 15 msecs, 15 msecs might be a good value for dt). So subtract a fraction of the velocity from the position, subtract a fraction of the acceleration from the velocity, and bam! Newtonian approximation. Many programmers have written this algorithm without knowing an iota of calculus just because it’s so intuitive. Maybe Newton and his fancy calculus aren’t so precious after all. You going to take that Newton? Oh, you have to because you’re dead!
Downsides
By fixing dt, the animation is not over until the fat lady sings. And operas last a really long time. Yeah the sets are cool and the singer-actors are amazing virtuosos, but god don’t you get tired of watching the subtexts? It’s like Italian is only capable of conveying shock and melancholy. If my phone is crunching and each frame takes an average of 100 milliseconds, the scrolling animation is going to last more than six times longer than it should! Although holding a note 12 seconds is nothing for an opera superstar, an animation of similar length isn’t acceptable.
Newtonian with varying dt
The first fix I tried is the obvious one. Plug the real elapsed time between frames into dt and problem solved. This is where the reality of programming comes in and shouts “oh no you didn’t” and twists your tidy algorithm into the user experience equivalent of a pretzel. All of the sudden, everything’s jerking around a lot! And oh crap how did I get to the bottom of the stupid-long planet.mozilla.org so fast? All I did was smudge my finger on the screen.
Downsides
Let’s plug in some numbers and see what happens:
50msec elapse: pos(0+.050) = 0 + .050 * 600 = 30 respectable pixels
800msec elapse: pos(0+.8) = 0 + .8 * 600 = 480 I guess that's OK pixels
3200msec elapse: pos(0+3.2)=0 + 3.2 * 600 = 1920 ridiculous pixels
Unfortunately during intensive operations like page load, Fennec can often see three second delays between timer callbacks. This is the antithesis of smooth; it’s possible to completely lose your context of what you are reading. Not only that, but the total distance traveled is now dependent on how much time Fennec spent teleporting goats or whatever the hell it’s doing. This is why I consider good kinetic panning a “slippery” problem; here I’ve fixed the speed problem at the total expense of predictability and smoothness.
Verlet integration
This is a more sophisticated way of calculating the scroll position based on the previous step, with less error. I won’t delve into the details, but verlet integration had the same basic problems as Newtonian approximation did. Ultimately, step-based solutions were not getting me the results I wanted. Taking a step back, I realized I was using approximations of a function that I could easily calculate myself.
Closed form of position: a parabola
If the scrolling animation has a velocity that decelerates constantly, the movement is actually that of a parabola. I don’t want to dive into integration methods here, but there’s an easier way to explain it. If you are a gorilla and you’re throwing exploding bananas at buildings, the arc that your banana makes with deadly grace as it moves through the air is a parabola. The banana initially has an upward velocity, but gravity decelerates the velocity at a constant rate causing the banana to come down and hit unsuspecting office workers, detonating on impact. This motion is analogous to our scrollbox movement over time, except at the peak of the scrollbox’s parabola the motion is cut off.
Here’s the formula:
pos(t) = v0*t + 1/2*a*t^2
vel(t) = v0 + a*t
Now I was getting somewhere. I could calculate the time and position at which the movement is at its peak, when the velocity is zero:
vel(tf) = 0 = v0 + a * t
tf = -v0 / a
pos(-v0 / a) = v0 * (-v0 / a) + 1/2 * a * (-v0 / a) ^ 2
pos(-v0 / a) = -1/2 * v0^2 / a
So I now have an equation that gives me exactly what I want: when the animation should end, and more importantly, where the animation should end. Assuming the initial velocity is calculated robustly, I can pan down a page and consistently get the same distance covered every time.
Downsides
This formula nails down the animation’s speed and predictability as best as anything can, but smoothness has suffered. To add insult to injury, our mobile VP Jay noticed something bizarre: the scrolling sometimes sped up in the middle! I checked my algorithm with a data dump:
time 30 distance -50
time 72 distance -67
time 119 distance -70
time 167 distance -67
time 215 distance -63
time 263 distance -58
time 310 distance -52
time 358 distance -49
time 405 distance -44
time 463 distance -48
time 510 distance -34
time 558 distance -30
time 606 distance -25
time 655 distance -21
time 703 distance -16
time 750 distance -11
time 798 distance -7
time 856 distance -2
The numbers look pretty good, but unfortunately the time dumps are in Javascript and don’t reflect exactly when the screen is repainted. If the times between the scroll call and the repaint are constant, the graph would just shift (and still look like a parabola). My theory is that this time offset varies in a specific way per animation causing the velocity hump.
Parabola with time mean
I then fudged time a little, like I imagine the protagonist in Braid would do in a similar spot. I wanted all the smoothness of a fixed dt solution but with the ability to control how long the animation takes like in varying dt. The velocity hump also needed to be flattened out. After some experimentation, it hit me that I could literally blend the two solutions together with a time average:
time = (elapsed time + elapsed frames * update interval) / 2)
It’s immediately obvious that the animation can last no longer than two times the “ideal time” the animation should take (plug in final time for time, 0 for elapsed frames as a worst case, and solve for elapsed time). In contrast, if the animation is lagging behind the ideal time, the frame skipping will be blended in with a smoother animation. If the above formula is made to be a weighted average, the trade-off between smoothness and total animation time can be tweaked with predictable results.
Putting the algorithm to the test, I noticed that the velocity hump is smoothed out by the time interpolation as well, so I had finally approached a robust kinetic panning algorithm that hit all three of my goals.
Final thoughts
Because I’m fortunate enough to be at Mozilla, you can find the distilled version of my efforts in code. If you’re a Javascript hacker, you’ll find this a satisfying thing to play with because you don’t really need to know a lot about Fennec beforehand. It might be a great way to get into Fennec development (here’s how to set up a build; ignore anything Maemo-specific to build on your desktop).
This problem required lots of neat stuff: basic calculus, data analysis, attention to detail and polish, a surprising roadblock, and a neatly contained end result. These are the kinds of problems that keep me excited about programming.
