Jitter in object movement when using subpixel positions

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems.

Moderator: Moderators

User avatar
thefox
Posts: 3141
Joined: Mon Jan 03, 2005 10:36 am
Location: Tampere, Finland
Contact:

Jitter in object movement when using subpixel positions

Post by thefox » Thu May 21, 2015 3:17 am

Consider the following scenario:

Camera "C" is moving right at speed 0.5 pixels/frame. An object "O" is also moving right at speed 0.5 pixels/frame. Both C and O have a subpixel position. C starts at 0, and O starts at 0.5 (so they have the same speed, but are in different phase).

O_c is the object transformed to camera space (by subtracting camera position)
t is time (frame number)

Code: Select all

t           C           O           O_c
---------------------------------------------
0           0           0.5         0.5
1           0.5         1.0         0.5
2           1.0         1.5         0.5
3           1.5         2.0         0.5
As you can see, the object stays still at 0.5 pixels, as it should. But if we floor the camera and object coordinates before transform (as often is natural):

Code: Select all

t           floor(C)    floor(O)    O_c
---------------------------------------------
0           0           0           0
1           0           1           1
2           1           1           0
3           1           2           1
Now the object coordinate jitters between 0 and 1 pixels. This looks bad, because the object is supposed to be moving right, but visually takes a step back every now and then.

Here's how it could look in practice. The camera is centered at the object at left, and the object at right is moving at the same speed, different phase. (This short animation doesn't really show the problem that well. The jitter looks quite annoying in practice at full speed.)
jitter.gif
jitter.gif (9.82 KiB) Viewed 3460 times
Is it possible to fix this problem without taking the subpixel position into account when calculating O_c?
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi

User avatar
rainwarrior
Posts: 7824
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Jitter in object movement when using subpixel positions

Post by rainwarrior » Thu May 21, 2015 10:08 am

Well, there's the obvious solution of locking the objects to the camera, or ensuring they're in phase.

If you can't do that, maybe you could fudge the subpixel position for anything moving at the same speed as the camera?

Code: Select all

if velocity == camera velocity:
    subpixel X = camera subpixel X
Another alternative is just to never let anything move at the same speed as the camera.

User avatar
thefox
Posts: 3141
Joined: Mon Jan 03, 2005 10:36 am
Location: Tampere, Finland
Contact:

Re: Jitter in object movement when using subpixel positions

Post by thefox » Thu May 21, 2015 10:50 am

Thanks for the input.

The problem is that this situation can arise "organically", without any explicit connection between the object's movement and the camera movement. E.g. when an object is being dropped downwards by gravity and the camera is moving down at the same time.

I guess I should take the subpixel position into account in the calculation, because all the other solutions are likely to be kludgy. The only reason I resisted it for a bit is that my current camera solution doesn't have a concept of subpixel position.

It might turn out that this isn't a big enough of a problem in real scenarios to warrant a fix even. I guess I got a bit lucky (or unlucky) with my test scene to even notice it.
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi

User avatar
rainwarrior
Posts: 7824
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Jitter in object movement when using subpixel positions

Post by rainwarrior » Thu May 21, 2015 11:26 am

I'm reminded of the skull-raft in Super Mario World (Vanilla Dome 3). One of the 4 skulls was always jittering, and if you stood on that one, the other 3 would jitter instead.
Last edited by rainwarrior on Thu May 21, 2015 1:18 pm, edited 1 time in total.

Sik
Posts: 1589
Joined: Thu Aug 12, 2010 3:43 am

Re: Jitter in object movement when using subpixel positions

Post by Sik » Thu May 21, 2015 11:56 am

Not an issue for faked subpixel precision (i.e. integer coordinates with non-integer speeds) since objects are always in phase.

In any case I don't think there's much you can do about it, most of the time it probably won't matter (and in some cases you can even attribute it to the fact that their movement isn't perfect in the first place - realism!). For the times it does matter, you should probably try to figure out why they end up out of phase in the first place, because it's obvious they should stay in sync.

User avatar
thefox
Posts: 3141
Joined: Mon Jan 03, 2005 10:36 am
Location: Tampere, Finland
Contact:

Re: Jitter in object movement when using subpixel positions

Post by thefox » Thu May 21, 2015 3:02 pm

Sik wrote:Not an issue for faked subpixel precision (i.e. integer coordinates with non-integer speeds) since objects are always in phase.
Sorry, but I don't understand what is the difference between "faked" and a "non-faked" subpixel precision? As far as I see, it's always "faked", because we have to align the graphics to the pixel grid (unless you're on modern hardware, where you can actually try to fake more precision a la http://freespace.virgin.net/hugo.elias/ ... wupixl.htm). Having a subpixel component in position is just an easy way to update the pixel grid aligned component of the position at a certain interval.

For a simple example where this can happen:
- Object 1 is created (subpixel position initialized to 0) and starts moving at 0.5 pixels/frame. Camera follows object 1 rigidly.
- A frame later, object 2 is created (subpixel position 0) and starts moving at 0.5 pixels/frame. At this point object 1's position is 0.5, and object 2's position is 0, so they are out of phase and will exhibit the problem.

I don't think I can prevent such situations from happening in the general case.
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi

User avatar
rainwarrior
Posts: 7824
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Jitter in object movement when using subpixel positions

Post by rainwarrior » Thu May 21, 2015 3:08 pm

Faked means your subpixel velocity is treated as a probability to increment position (with no subpixel) each frame. If you implement the probability test in a way that's consistent across all objects the phase is maintained. (e.g. generate one random number and use it for all comparisons against sub-velocity)

tepples
Posts: 22019
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Jitter in object movement when using subpixel positions

Post by tepples » Thu May 21, 2015 5:39 pm

Essentially what happens is you bit-reverse the 8-bit retrace count, call it bias, and use that as the subpixel position for all objects. To update an object's position, you add bias to the subpixel velocity, discard the value, but keep the carry for adding to the whole-pixel position.

User avatar
tokumaru
Posts: 11771
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Jitter in object movement when using subpixel positions

Post by tokumaru » Thu May 21, 2015 5:55 pm

tepples wrote:Essentially what happens is you bit-reverse the 8-bit retrace count, call it bias, and use that as the subpixel position for all objects. To update an object's position, you add bias to the subpixel velocity, discard the value, but keep the carry for adding to the whole-pixel position.
I honestly can't see how that works out as a replacement for actual sub-pixel positions. I would expect jerky movement as a result of doing this.

tepples
Posts: 22019
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Jitter in object movement when using subpixel positions

Post by tepples » Thu May 21, 2015 6:13 pm

It's the same principle as adding dither noise. If the dither noise is high enough in spatial or temporal frequency, the user is less likely to notice any jerkiness. Do I need to make a GIF or code a test ROM demonstrating the dither technique?

User avatar
tokumaru
Posts: 11771
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Jitter in object movement when using subpixel positions

Post by tokumaru » Thu May 21, 2015 6:37 pm

I just coded it in JavaScript and it does appear to work (not that I didn't believe you guys, I just had to see for myself), but I honestly still can't see how a reversed counter could substitute proper accumulation of fractional increments and cause overflows at the correct frequency.

User avatar
rainwarrior
Posts: 7824
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Jitter in object movement when using subpixel positions

Post by rainwarrior » Thu May 21, 2015 6:42 pm

tokumaru wrote:I honestly can't see how that works out as a replacement for actual sub-pixel positions. I would expect jerky movement as a result of doing this.
You're going through a regular sequence of biases every 256 frames, so the motion will increment at a regular sequence of intervals for any given value. A bias of 0 means nothing increments, a bias of 255 means anything with sub-velocity > 1 increments. The velocity number means "increment on X/256 frames", which over the course of 256 frames is the same amount of increment you'd get from addition with extra bits.

Tepples suggested bit reverse I think because this sequence has an ordering that frequently alternates high and low values. Is it more optimal than that? I haven't really looked too deep into it. My naive approach would have been to add 157 mod 256 each frame (prime close to golden ratio).

Using sub-pixel position, you get an interval that jitters by 1 frame (similar to the steps in a line drawing algorithm). Using this method, the jitter is a bit higher, but it might be within tolerance.

You could also reduce your bits of sub-pixel precision to get more regularity. 4-bit velocity would be a 16-frame sequence, cycling around more quickly, reducing the sequence jitter, but raising the visibility of the sequence itself. One of the properties of this is that objects tend to move together with this algorithm (which is why it was suggested here). e.g. when a high number comes up for bias everything increments on the same frame. This property also probably draws attention to the sequence jitter, but everything is a trade-off.


User avatar
tokumaru
Posts: 11771
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Jitter in object movement when using subpixel positions

Post by tokumaru » Thu May 21, 2015 8:34 pm

Thanks for the explanation, rainwarrior, I think I'm finally wrapping my head around this... Since we're going through all 256 values in a constant order, X times out of every 256 we'll get overflows, which is as many as we'd get from adding X 256 times. 256 frames is a lot of time though (4.26 seconds at 60Hz), so I imagine that a good bias is essential to spread out the overflows more evenly.
rainwarrior wrote:My naive approach would have been to add 157 mod 256 each frame (prime close to golden ratio).
I just tested in my crappy JavaScript implementation and guess what resulted in the smoothest movement? Adding 157 AND reversing the bits. That's with a velocity of 0.25, at least.
snarfblam wrote:There is a post on nesdev that explains how it works.
Yeah, I was already very interested in this trick back then, but my complete inability to understand it back at the time forced me to ignore it, but since it was brought up again, I decided to ask more about it. I'm glad I did, because I'm finally understanding it.
snarfblam wrote:It even links to a video showing it in action.
Yeah, the motion in this video looks perfectly normal, which is why I was so interested.

User avatar
rainwarrior
Posts: 7824
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: Jitter in object movement when using subpixel positions

Post by rainwarrior » Thu May 21, 2015 10:15 pm

It also helps that the sprites are animated. That would tend to hide jitter beneath the noise of the flipbook animation.

Post Reply