PDA

View Full Version : Nearest Neighbour image scaling



Mihail121
04-24-2003, 08:34 AM
Hi!

Can someone point me to a good tutorial or explanation for the Nearest Neighbour algorithm.Thanks!

Thr33d
04-25-2003, 10:19 AM
Hey,

I'm sure if you google for it you could pull something up. Either that or check out freespace.virgin.net/hugo.elias and check under graphics.


You don't really need a tutorial though, the algo is extremely simple.

ex.
Pretty much all it does is round the number to the nearest integer:

If we're working with a 1D texture map (just one coordinate) then, say the texture address it calculates is 15.4315

Nearest neighbor would round down to the pixel at location 15
[see the truncation? pretty much just (int)(value+.5) ]

It's the same for 2d textures (like we're used to) except that it "rounds" two values: for the (x,y) (or (u,v) if you prefer) coordinates.

That's all!

Another methods of texture sampling is Bilinear filtering. Check into that (google!)
You'll also want to look into MipMaps, and then Trilinear filtering (Tri is same as Bi but with 2 MipMaps... you'll understand when you look into what the stuff is)

Some sites with good info and articles (that come to mind) are www.gamedev.net (http://www.gamedev.net) and www.flipcode.com (http://www.flipcode.com)

If you're looking into *learning* to program gfx using OpenGL, you might check out neon helium's opengl tutorial site: nehe.gamedev.net (check out the tutorials on the left side of the page)

Hope this helps,
-Michael

marcus256
04-25-2003, 12:24 PM
Originally posted by Mihail121:
Hi!

Can someone point me to a good tutorial or explanation for the Nearest Neighbour algorithm.Thanks!

It sounds as if you are not too familiar with interpolation techniques or signal processing in general.

Hint: Nearest Neighbour is the worst possible interpolation technique (zeroth order) there is. The only reason to use it is if you want to do image scaling (or similar) in realtime with the CPU. For (nearly) all other applications, you should use higher order interpolation (1st order = linear/bilinear, 3rd order = cubic/bicubic etc, or use SINC interpolation if you really-really care about image quality).

Also note that interpolation is only useful (designed for) enlarging an image. If you want to make it smaller, you need to use adequate lowpass filtering in order to avoid spatial aliasing (which, for instance, is why OpenGL supports mipmaps for minification filters).


[This message has been edited by marcus256 (edited 04-25-2003).]

jwatte
04-25-2003, 07:07 PM
NEAREST is great for various sharp, crisp border effects.

marcus256
04-26-2003, 12:55 PM
jwatte,

Of course you are right... I'm going on and on with my signal processing based on the assumtion that you are working with real/natural images. Some synthetic textures can be better off with NEAREST (basically when you want to turn each "texel" into a quad).