Above maxVelocity changes direction to diagonal, workaround

Question

The flaw here in Android's VelocityTracker class that if your velocity in the X direction exceeds the maxVelocity it is changed equal maxVelocity and the same for the Y. But, that means that if we are going at 20° angle and at a speed of 200, and our maxVelocity is 20. Our velocity is changed to be 20*sqrt (2) at a 45° angle. The correct answer is to scale the mXVelocity and mYVeloicity by the ratio of the actual velocity and maxVelocity.

My question is do I have to resort to two square-roots to fix this error?

Velocity is the direction and speed of an object. Changing the direction because of the maximum velocity was reached must be considered a defect. This also clearly causes a flaw in that a diagonal velocity is faster than the orthogonal one.

The problematic bit of code akin to:

mXVelocity = accumX < 0.0f ? Math.max(accumX, -maxVelocity) : Math.min(accumX, maxVelocity);
mYVelocity = accumY < 0.0f ? Math.max(accumY, -maxVelocity) : Math.min(accumY, maxVelocity);

To work around this I use:

tracker.computeCurrentVelocity(units); //maxVelocity
double velocityX = tracker.getXVelocity();
double velocityY = tracker.getYVelocity();
double actualVelocitySq = velocityX * velocityX  + velocityY * velocityY;
double maxVelocitySq = maxVelocity * maxVelocity;
if (actualVelocitySq > maxVelocitySq) {
    //double excessFactor = Math.sqrt(maxVelocitySq) / Math.sqrt(actualVelocitySq);
    double excessFactor = Math.sqrt(maxVelocitySq/actualVelocitySq); //leewz's optimization
    velocityX *= excessFactor;
    velocityY *= excessFactor;
}

Is there some way to do avoid the double square-root? Or some other thing that otherwise fixes this screwy bug?

Update:

The answer seems to be scale both components according to the one component that exceeds the maximum velocity by the most. This isn't strictly scaling according to the actual velocity but it fixes the bulk of the problem with easy math.

double scale;
double vectorX = Math.abs(velocityX);
double vectorY = Math.abs(velocityY);
if (vectorX > maxVelocity) {
    scale = maxVelocity / vectorX;
    if (vectorY > maxVelocity) {
        scale = Math.min(scale, maxVelocity / vectorY);
    }
    velocityX *= scale;
    velocityY *= scale;
} else {
    if (vectorY > maxVelocity) {
        scale = maxVelocity / vectorY;
        velocityX *= scale;
        velocityY *= scale;
    }
}

Note to readers: The code with the flaw in the question is in Android's `VelocityTracker.computeCurrentVelocity(units, maxVelocity)`, not the asker's code. — leewz, Jan 03 '17 at 15:48

score 1 · Accepted Answer · edited May 23 '17 at 11:46

1

You can cut away Math.sqrt(maxVelocitySq), because you know maxVelocitySq = maxVelocity * maxVelocity. Even without that, you can use a single sqrt() by doing the division first:

double excessFactor = Math.sqrt(maxVelocitySq / actualVelocitySq);

Mathematically, I believe taking a square root is required, but how you take the square root is still open to you. In particular, Fast Inverse Square Root works for your usecase. Here's the code using fisr().

if (actualVelocitySq > maxVelocitySq) {
    double excessFactor = fisr(actualVelocitySq / maxVelocitySq);
    velocityX *= excessFactor;
    velocityY *= excessFactor;
}

Here's a Java implementation of FISR.

Caveat: FISR was designed for an older generation of Intel CPUs which were slow at floating point operations (especially division, which the above code still uses), not a JIT'd virtual machine (such as Java's) running on ARM (a common architecture for Android). Remember to profile your code to see if the square root cost is significant enough to optimize, and then to measure whether FISR gives a worthwhile improvement.

edited May 23 '17 at 11:46

Community

1
1

answered Dec 29 '16 at 20:51

leewz

3,201
1
18
38

I swear I had run the numbers and couldn't do the division first, but apparently not as it's clearly the case. Just checked the graphs and yeah, must have done it wrong by hand. I swear there's some vector math that can effectively avoid square-roots in cases that I thought they should be needed in. Though guessing and checking would end up with the square-root algorithm again. So unless there's some way to solve the result of the magnitude without solving for the magnitude, it might require such things. – Tatarize Dec 30 '16 at 21:41
1. You may have used integer division in your tests. 2. A way of normalizing without a sqrt would mean FISR didn't need to exist. You can avoid it in cases where the vector gets multiplied by its length, though. 3. Are you sure the square root is costly? Computing velocity is already costly. 4. Not guess and check, but Newton's approximation. A custom sqrt can do fewer iterations than the built-in sqrt. – leewz Jan 03 '17 at 15:57
The goal would be to not normalize in theory. But, come to the same general answer that normalizing would give you. Even if you cheated and normalized at maxX and maxY to maxVelocity. Since the triangles x,y,v is congruent with X,Y,V. If we scale according to maxX or maxY rather than V we can simply scale according to max required scaling factor of the component. And apply that max to the other as well. Thereby leaving X or Y at maxVelocity but not changing the actual vector, without using a square root anywhere. – Tatarize Jan 03 '17 at 21:25

score 0 · Answer 2 · answered Jan 03 '17 at 21:58

The trick is to not to scale according to the magnitude of the actual vector but rather the component that exceeded the requirement by the largest amount. Then scale both x and y by that. It requires no math harder than division. And doesn't fubar the angle of the vector at all. While the result of the maxVelocity could, at an angle, exceed the actual velocity by a factor of sqrt(2). It conforms better to the documentation of what maxVelocity does.

maxVelocity float: The maximum velocity that can be computed by this method. This value must be declared in the same unit as the units parameter. This value must be positive.

double scale;
double vectorX = Math.abs(velocityX);
double vectorY = Math.abs(velocityY);
if (vectorX > maxVelocity) {
    scale = maxVelocity / vectorX;
    if (vectorY > maxVelocity) {
        scale = Math.min(scale, maxVelocity / vectorY);
    }
    velocityX *= scale;
    velocityY *= scale;
} else {
    if (vectorY > maxVelocity) {
        scale = maxVelocity / vectorY;
        velocityX *= scale;
        velocityY *= scale;
    }
}

Above maxVelocity changes direction to diagonal, workaround

2 Answers2