Sub-pixel Positioning Question - Smooth Scroll / Parallax (solved)

[Ali]

Some of you may be familiar with my smooth scrolling module: http://www.adventuregamestudio.co.uk/forums/index.php?topic=33142.0

I'm using it to create an ocean wave effect - the camera going up and down gently. However, the module doesn't allow very slow movement. When movement gets near to 1 pixel per second it looks very jerky, like stair-step aliasing but for movement. To get around that, I have a line which cuts off the movement when it gets slow:

Code: AGS

if (Centring == false && ScrollSpeedY < 0.7 && ScrollSpeedY > -0.7) ScrollSpeedY = 0.0;

Now, I can create a passable ocean effect by temporarily changing those 0.7s to 0.3s. But it's still quite jerky and jerkiness is not what the smooth scroll module is about! The jerkiness is accentuated by the parallax effect, because when the camera makes a single 1 pixel jump, the foreground objects make a 1 or more pixel jump in the opposite direction.

What I'm wondering about is whether, what with all the AGS changes afoot, there will be any prospect of setting an object's position, or even the viewport, using floats rather than ints? Or might there be a cosmetic way around this which I haven't considered?

I would appreciate any input!

[Khris]

The only thing I can think of is faking sub-pixel positioning/AA by using two semi-transparent objects.

Say the object is supposed to be placed at Y = 122.3
Place the object at 122 with a transparency of 30, and place a copy of it at 123 with a transparency of 70.

However, I've done a quick test and the problem is that transparency isn't additive. If my calculations are correct, the area covered by both objects is 21% transparent, not 0%.

Without changes to the engine, I don't think there's a simple way to achieve this effect without rendering the entire sprite yourself.

[Ali]

Ooh, the transparency idea is quite ingenious, even if it doesn't work right now.

Back when AGS only moved objects in 2 pixel jumps I added in a hack to allow 1 pixel jumps (by creating sprites of the same object with 1 pixel difference). I suppose you could pre-render a 9 frame transition from 0.0 to 0.9 and assign the appropriate frame depending on the value after decimal place. So in the case of Y = 122.3 the object would be placed at 122 showing a frame which shifts it upwards by 30% of a pixel...

I'm not a very maths-y person. What would be a good way of getting just the decimal at the end of the float?

[DoorKnobHandle]

Code: AGS

float position = 122.3;
int rem = FloatToInt ( position * 10.0 ) % 10;

Completely untested and I'm in a rush but that should work. rem is the first decimal point (0-9) of float position.

[Snarky]

Take a look at this.

[Ali]

Snarky's technique sounds really interesting, but it doesn't sound like it would work well with the parallax module because it uses objects.

With a bit of experimentation, Khris's suggestion seems to work. Or at least, it stops parallax objects from exaggerating the jerkiness of slow scrolling. Thanks!

[Snarky]

I don't see how Khris's method can avoid the problem of the resulting sprite being partially transparent.

[Vince Twelve]

In Resonance, to get slow-moving, smooth-scrolling sky backgrounds in some of the scenes, I took the sky background image, blew it up 10x, made 10 frames of animation each shifting the sprite 1px left, then saved them all back to their original sizes.  The result was a 10 frame animation of the item moving 1 pixel (after playing the 10 frames, you shift the object one pixel and return to the first frame).  I used these frames for the tenth-of-a-pixel sprite movement.

Might be hard to integrate that into the parallax module, I'm not familiar with how it's written, but the big drawback would be swollen file sizes if you use this technique liberally.  I only used it in a few scenes.

[Ali]

I don't see how Khris's method can avoid the problem of the resulting sprite being partially transparent.

Sorry I wasn't clear. I didn't do an on-the-fly blend, I did something like what Vince did but using a different technique to render the frames.

It shouldn't be a problem to integrate it into the module. At the moment there is a PxView property which is pretty redundant. I could make the module assume that the first two loops were 10 frame animations vertically and horizontally. Because of the hassle to render and set up, I'm not sure how many people would actually use it...

[Calin Leafshade]

get yourself a bilinear filter algorithm and prerender the frames in the module?

[Snarky]

I don't see how Khris's method can avoid the problem of the resulting sprite being partially transparent.

Sorry I wasn't clear. I didn't do an on-the-fly blend, I did something like what Vince did but using a different technique to render the frames.

It shouldn't be a problem to integrate it into the module. At the moment there is a PxView property which is pretty redundant. I could make the module assume that the first two loops were 10 frame animations vertically and horizontally. Because of the hassle to render and set up, I'm not sure how many people would actually use it...

Not to make this into a big thing, but didn't I suggest the same solution four years ago? I thought you'd already integrated it into the module, in fact.

[Ali]

Looking back, you did!

But back then AGS moved objects in 2 pixel jumps, so the module was INCREDIBLY jerky. I used your suggestion to get it down to 1-pixel jumps, which seemed satisfactory at the time.

Calin: I have no idea how to do what you're suggesting. Do you have any tips?

[Vince Twelve]

Hey, you know what, Snarky? I think reading that post several years ago gave me the idea to do it that way!  I forgot about that, thanks!

[Misj']

It's been a while since I've done any programming in AGS; for my work I've mostly worked with MatLab (which is at times dreadful but it gets me where I need to go to analyze my images)...so my apologies if this answer is not applicable in this case.

But the way I would approach this problem is similar to Calin's remark: 'get yourself a bilinear filter algorithm and prerender the frames in the module?'. Assuming we can do some basic image convolution (and Fourier transforms) the fastest way to create subpixel-shift would be with a convolution matrix of:

convolution Matrix = 

0    0    0

i    1-i  0

0    0    0

where i is a value between 0 and 1.

This way it will blend each pixel with the left neighbouring pixel with a ration of i to 1-i. The upside: in general, image-convolution is the fastest way to do this; in the case of most AGS use-cases this should work in real-time and would not require any pre-rendering . The downside: you get a border-artefact (in this case you will get a single pixel black black border to the right that you would need to remove).

Hope this is useful


EDIT: typo in the convolution matrix

[Monsieur OUXX]

Considering that the intro of "How they found silence Deluxe" is an ocean wave effect exactly like yours, and that it looks horrible (per-pixel movement), and that I knew that eventually I'd have to implement what you describe... You have my blessing for this

[Ali]

I appreciate your blessing!

However I'm afraid I don't know what a convolution matrix is, never mind how to implement one in AGS. My module just moves objects around - it's very simple!

What would be the best way to approach this? I'm inclined to go pre-rendered, purely because I understand that approach. However your suggestions sound better, but I'm nto sure where to begin with them.

- Ali

[Snarky]

Well, the first step would be to implement Fast Fourier Transform and convolution functions in AGS. Those are standard algorithms and it should be easy to find implementations in other languages to use as examples. Then you'd just write a module that reads in the sprite, performs the appropriate convolution in frequency space, and writes out the subpixel-shifted version of the sprite to another sprite slot.

A FFT solution would be nice, but unfortunately I don't think you can in fact do it in a module. The only way to read in the original sprite and then create the modified sprite after you've done the convolution would be to loop over all the pixels doing getpixel/drawpixel, which would hardly be very efficient. More seriously, you can't read or write the alpha channel, so any alpha-blended pixels would have to render as opaque; this would play havoc with the edges of any subpixel-positioned sprites.

I'm sure it could be done, but it would have to be done as a plugin (unless the engine API were updated).

[Monsieur OUXX]

Well, the first step would be to implement Fast Fourier Transform and convolution functions in AGS.

LOL.
Even though that would be really nice, my advice is this: Ali, don't let yourself be terrified by Snarky's post.

For short: A convolution Matrix is a small 3x3 array containing the values of the color-change you must apply to each pixel in the picture, and to its 8 surrounding pixels. You need to do a big loop and apply this color change to every pixel in the picture. You will notice that a consequence of the Matrix's size (3x3) is that some color changes will be applied to each pixel several times : when the matrix is applied to the pixel before them, then when it's applied on them, then when it's applied to the pixel after them, etc. Except the color change won't have the same value each time, since the 3x3 array doesn't store the same value in every cell.
If you convolution Matrix contains the right fine-tuned values, then it will create the transformation effect you seek. That's pretty much the concrete implementation of a shader.

Then, all the FFT stuff is to optimize (you stop seeing your input picture as an array of pixels, but instead you see it as a "wave" in a different "space" (in the mathematical sense of the word)). There's a lot of mathematical theory behind it, but for short, it's like you're Neo and you're inside the Matrix, and you see only the essence of the picture. You don't need to look closely at every pixel to get the picture, instead you apply some mathematical functions to it, that will apply some bulk-processing to the relevant pixels at once, in a super-optimized manner. Think of JPEG compression, for example : instead of storing every pixel, it calculates only some raw variations in the picture's contrast (and stores them as sinusoidal "waves" or "curves"), and when you superimpose those variations on top of eachother (at rendering time), then BOOM, an image magically appears (the drawback being that you can't keep all the details, hence the blocky/dirty effect wherever there is a sudden contrast change). I'm not saying Snarky suggested you implement JPEG, I'm just giving an example of FFT (and all that "wave" magic) in everyday life.

Having said all that, the convolution matrix approach is a per-pixel approach (unless I missed something). I don't know if it's very optimized (unless you write a plugin -- in that case I'd recommend the EXCELLENT "AGSEasyPlugin" tool ;-) ... or you could just add some features to Calin's Blending plugin, I'm pretty sure all the code base you need is there). Your/others' idea of relying on hardware-accelerated features (transparency, etc.) and manipulate entire pictures is nice as well, and has the virtue of keeping it simple, and at module level.

[Misj']

Having said all that, the convolution matrix approach is a per-pixel approach (unless I missed something).

You missed something. - convolution is by definition a Fourier-space based approach and not a per-pixel approach (although many of the same effect can be achieved in a loop, as you described, but it will be very ineffective). 

You can compare the convolution-matrix to the point spread function: it describes how each single pixel is distorted in the image. Convolution then basically multiplies the original image with it's distortion. This is very cost-efficient, as it is a single operation for the entire image (rather than a per-pixel operation). The other advantage is, that each convoluted/distorted image can be deconvoluted if you know the original distortion...this is something that is fairly difficult with per-pixel manipulation.

All that being said: applicability to AGS might not, as Snarky pointed out, be that feasible; although I've seen Calin do some amazing stuff, and he might have some ideas about this.

[Monsieur OUXX]

Having said all that, the convolution matrix approach is a per-pixel approach (unless I missed something).

You missed something. - convolution is by definition a Fourier-space based approach and not a per-pixel approach

Yeah, I contradicted myself, after having explained at length why the convolution stuff was not per-pixel Bottom line is : Ali, do as you like, but good luck if you go the Fourier way!

[SSH]

Can't you just blow up all the sprites and BG by 10x, draw at appropriate place and then scale it all down again?

[Snarky]

You missed something. - convolution is by definition a Fourier-space based approach and not a per-pixel approach (although many of the same effect can be achieved in a loop, as you described, but it will be very ineffective).

This is not quite accurate. Convolution is a coordinate-space operation that is usually (in this context) implemented by converting to frequency-space using a Fourier transform, multiplying, and converting back, which works because of a theorem that says convolution in coordinate-space is equivalent to multiplication in frequency-space.

[Misj']

This is not quite accurate. Convolution is a coordinate-space operation that is usually (in this context) implemented by converting to frequency-space using a Fourier transform, multiplying, and converting back, which works because of a theorem that says convolution in coordinate-space is equivalent to multiplication in frequency-space.

Even that is not quite correct - Convolution is strictly speaking the result of two functions that are 'combined' into a third (by summation in real space which equals multiplication in frequency/Fourier space).

In image processing this normally means that the first 'function' is the original image and the second function is the distortion (point spread function) which together result in a 3rd function (the distorted image). One can, however, argue that the original image is only (described as) a function upon converting it to frequencies/Fourier space and not while it's still in real/coordinate space. As a result, only the frequency-space operation is convolution, while the coordinate-space operation produces the same result but is not convolution - in the strictest sense - because the operation of combining two functions was not performed. That is of course a discussion on semantics.

And I'm afraid we (or at least I) are not really helping Ali anymore

[Snarky]

One can, however, argue that the original image is only (described as) a function upon converting it to frequencies/Fourier space and not while it's still in real/coordinate space.

You could argue that, but you'd be wrong. An image is a perfectly respectable function from x*y coordinate space into color space (or color + alpha, if you have transparency).

[Misj']

You could argue that, but you'd be wrong. An image is a perfectly respectable function from x*y coordinate space into color space (or color + alpha, if you have transparency).

One could argue that (I won't concede my defeat, but won't deny you your victory on this either* )

Still...ideally AGS would support FFT and some basic convolution algorithms to achieve these kinds of effects (like blurring and sub-pixel movement) on RGBa images. On the other hand I also understand - and agree - that (the core) AGS might not be the right place to include this since it doesn't really add to the actual AGS business which is: making adventure games.



* My wife is a mathematician/statistician. She agrees with you that you can consider an image a function...since I'm not allowed to disagree with my wife (it was somewhere in the marriage fine-print) I have to agree with her and thus (indirectly) with you...darn

[Snarky]

Mathmo 4 Life!

We actually discussed sub-pixel positioning (and transformations) at Mittens, and I was surprised that even ProgZmax (who I always thought of as a hardcore pixel-art guy who'd have no time for anything that messed with the individual pixels) thought it's an important area for improvement in AGS.

As AGS games get more ambitious and polished, the number of useful applications for sub-pixel operations and rendering (as well as other effect and filters, like blurring, desaturation, etc.) increase. (Another obvious one is for scrolling credits, which look jerkier than they ought to in the current, whole-pixel implementation.) And with AGS becoming more cross-platform, implementing them in plug-ins becomes less desirable. So I think it's worth to consider adding it to the engine.

[Calin Leafshade]

This would be trivial to implement if we discontinued the DD5 rendering mode.

In DX9 you can just draw the texture at a sub pixel position and you dont have to worry about anything. The filtering is done on the GPU.

Then we just set the object and character positions to be floats and not ints.

Problem solved.

[Shane 'ProgZmax' Stevens]

I was surprised that even ProgZmax (who I always thought of as a hardcore pixel-art guy who'd have no time for anything that messed with the individual pixels) thought it's an important area for improvement in AGS.

I was rather surprised that you were surprised since I don't think I've ever given the sense to people that I'm against improvements of this nature .

In DX9 you can just draw the texture at a sub pixel position and you dont have to worry about anything. The filtering is done on the GPU.

This is true, though the current d3d 9 implementation in the engine feels a bit sluggish and inefficient to me for certain operations and could do with a look at first.  I just have my doubts when I watch 50-frame 320x240 looped animations skip and stutter occasionally on a dual core 3 ghz with 8 gb of ddr3, not to mention fullscreen translucent images.  This is a discussion for another thread, though.

[Snarky]

I was rather surprised that you were surprised since I don't think I've ever given the sense to people that I'm against improvements of this nature .

Not that you'd be against it; I just didn't think it was something you'd have any personal interest in.

Can't you just blow up all the sprites and BG by 10x, draw at appropriate place and then scale it all down again?

In-engine? No. You would need to do a nearest-neighbor upscaling and a bilinear downscaling (otherwise the process ends up blurring the result), and the AGS scaling functions don't give you control over what sort of sampling function to use.

[Monsieur OUXX]

Can't you just blow up all the sprites and BG by 10x, draw at appropriate place and then scale it all down again?

In-engine? No. You would need to do a nearest-neighbor upscaling and a bilinear downscaling (otherwise the process ends up blurring the result), and the AGS scaling functions don't give you control over what sort of sampling function to use.

I'd also add that I tried that manually using a Paint program, and I was not very happy with the result. when the movement is really really slow, then it's like each row of pixels slowly fades in, one after the other. As soon as a row has finished fading in, the next one starts fading in above it (if the sea is moving up). In the end it looks like a weird Tetris game (with rows of pixels piling up) rather than an actual movement.
But I must admit there is virtually no other solution.

[Snarky]

That's probably unavoidable whatever method you use, though. (All the methods discussed should give "pretty much"/exactly the same result.) When you place a sprite by sub-pixel, it'll cover only a fraction of the pixels on the edges, which must be rendered as part transparency. As you keep moving it up, it will cover more and more of the top edge pixels, so the effect will be that the row is slowly fading in. When the resolution is low and the pixels big, that becomes noticeable.

I get a similar artifact with my blending method. I tried to counter it by reducing the update frequency to about 10 frames per second (so that it would fade in step-wise rather than smoothly, but still more smoothly than full-pixel movement). I didn't end up using it, but maybe you'll like it better that way.

The other point to keep in mind is that when movement is that slow it doesn't draw the eye (you know those psych experiments where you stare at a picture to try and see what part is changing and it's almost impossible because it's so slow that you have to look at the same spot for several seconds to notice it), so it's not going to be as noticeable to a player watching the scene as a whole as it is to the designer staring at it, particularly if you add other, more dramatically animated elements to the scene as a distraction. Or just animate the sea itself: if it' actually changing as it's sliding up and down, I don't think it will look like it's fading any more.

[Monsieur OUXX]

My point was (advice to Ali) : Avoid a straight-line sea. Maybe use an animated sea, or something. Or a trick of any sort. A sub-pixel movement applied to a straight line looks crap, and a sub-pixel movement applied to a texture movement looks blurry.

[Snarky]

Although if this is for Nelly Cootalot 2, which I think is being made in 800x600, I don't think those problems will be very noticeable.

[Ali]

I was away from the internet for two days and a debate about maths I don't understand kicked off!

My point was (advice to Ali) : Avoid a straight-line sea. Maybe use an animated sea, or something. Or a trick of any sort. A sub-pixel movement applied to a straight line looks crap, and a sub-pixel movement applied to a texture movement looks blurry.

It was actually foreground objects that were most noticeably jerky, but as Snarky says the sub-pixel fading is not noticeable at 800x600 and at the speeds I'm moving the screen. I have a hack that works, and if I can find the time to get to grips with convolution, I'll try integrating something much cleverer into the engine. Although I'm secretly hoping that this will happen and I don't have to:

This would be trivial to implement if we discontinued the DD5 rendering mode.

[BigMc]

One more reason to consider porting the engine to Allegro 5, which is inherently sub-pixel accurate.