physics - How does one avoid the "staircase effect" in pixel art motion?

I am rendering sprites at exact pixel coordinates to avoid the blurring effect caused by antialiasing (the sprites are pixel-art and would look awful if filtered). However, since the movement of the objects involves variable velocity, gravity, and physical interactions, the trajectory is computed with subpixel precision.

At large enough screenspace velocities (vΔt larger than 2 or 3 pixels) this works very well. However, when velocity is small, a noticeable staircase effect can appear, especially along diagonal lines. This is no longer a problem at very slow screenspace velocities (v << 1 pixel per second) so I am only looking for a solution for intermediate velocity values.

On the left is the plotted trajectory for a large velocity, obtained by simple rounding of the object coordinates. In the middle you can see what happens when velocity becomes smaller, and the staircase effect I am talking about. On the right, the locus of the trajectory I would like to get.

I am interested in algorithm ideas to filter the trajectory in order to minimise the aliasing, while retaining the original behaviour at large and small velocities. I have access to Δt, instant position and velocity, as well as an arbitrary number of previous values, but since it is a realtime simulation, I do not know about future values (though if necessary, an estimation could be extrapolated under certain assumptions). Note that because of the physics simulation, sudden direction changes can also happen.

Answer

Here's a quick outline, off the top of my head, of an algorithm that ought to work reasonably well.

1. First, calculate the direction the object is moving, and check whether it's closer to horizontal or vertical.


2. If the direction is closer to vertical (horizontal), adjust the position of the object along the direction vector to the center of the nearest pixel row (column).


3. Round the position to the center of the nearest pixel.

In pseudocode:

if ( abs(velocity.x) > abs(velocity.y) ) {
    x = round(position.x);

    y = round(position.y + (x - position.x) * velocity.y / velocity.x);
} else {
    y = round(position.y);
    x = round(position.x + (y - position.y) * velocity.x / velocity.y);
}

Edit: Yep, tested, works quite nicely.