Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

pixel coordinates for object trajectory

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.

share|improve this question
add comment

3 Answers

up vote 15 down vote accepted

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.

share|improve this answer
    
+1, exactly what i thought while reading the question. –  George Duckett Oct 21 '11 at 7:17
    
+1, this works surprisingly well! I notice weird backwards jumps with circular movement at slow velocities, because the adjustment can be done in the direction opposite to the velocity vector (which is usually OK, but not with small trajectory curvatures). That can be solved by multiplying velocity.y / velocity.x by a correction factor proportional to the velocity. –  Sam Hocevar Nov 16 '11 at 14:03
    
@Sam: You mean small turning radius (= high curvature), right? That could indeed cause issues with the linear extrapolation at low velocities. (Basically, it works as long as velocity squared per acceleration is much larger than 1 pixel.) One possible (klugey) solution might be to remember the last rounded position and reuse it if it's closer to the true position than the newly computed one. (One could also try higher-order extrapolation, but the formulas get pretty ugly.) –  Ilmari Karonen Nov 16 '11 at 20:41
    
Indeed, I meant small radius. My bad. And thanks for the additional hints; performance is not critical there, so I can afford to improve quality. –  Sam Hocevar Nov 16 '11 at 21:37
add comment

There's not much you can really do about that for a general physics-based world. If all of your objects were moving along lines or specific circles, you could do something. But you're operating under actual physics. The object is where the physics puts it; you are simply drawing a pixel-based approximation of that location.

It's generally something you have to accept if you want to stick with pixel coordinates. It shouldn't be too noticeable unless you're displaying at an incredibly small resolution (less than 640x480, though it depends on the display's native resolution and size).

share|improve this answer
    
Even at high resolutions, the rendering is upscaled (nearest neighbour) to enhance the oldschool appearance. This is an artistic direction decision. –  Sam Hocevar Oct 21 '11 at 8:58
    
@SamHocevar: If you want an "oldschool appearance", why don't you want a full "oldschool appearance"? Why is the stair-stepping, which any "oldschool" game would have had, not a part of the overall effect you want to achieve? –  Nicol Bolas Oct 21 '11 at 9:06
    
I don't think any decent oldschool game would have implemented a diagonal movement that has that staircase effect, because it would have looked like crap. Not looking like crap is a major part of the oldschool effect I wish to achieve :-) –  Sam Hocevar Oct 21 '11 at 13:16
    
@SamHocevar: Most old-school games are action games, and therefore don't move slowly enough to notice. They also tend to not move along curves. The game in particular that I was thinking of was Solar Jetman, which very much has this effect when moving slowly. Granted, the camera is always centered on you, so you notice it in world movement, but it very much is there. –  Nicol Bolas Oct 21 '11 at 17:15
add comment

When the pending movement is perpendicular to the last movement (in screen space), ignore it and use the last screen coordinates. If that lead to stutter that's as bad as the staircase, you might try moving the sum of the pending and last movement.

I think the problem lies in v < sqrt(2). v > sqrt(2) should always move at least a full diagonal, avoiding the staircase effect. Maybe useful for pruning which need the prior movement comparisons.

share|improve this answer
    
+1 for pointing out an upper bound for v. Ilmari's suggestion is more detailed but you're providing useful information. –  Sam Hocevar Oct 21 '11 at 9:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.