Jump to content
  • Advertisement
Sign in to follow this  
mark-w

nearest neighbor interpolation speedup

This topic is 4839 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I wanted to write the simple nearest neighbor interpolation method for use with my application. It works fine, but when I get to a really big zoom magnification, the interactive zoom starts getting choppy. Are there any ways to speedup the algorithm once the zoom gets big, because it is just constantly copying over the same pixel data at that big magnification:
for (int y = 0; y < nZoomedCy; y++) 
for (int x = 0; x < nZoomedCx; x++) {
    int nOriginalPixIdx = (int)(y / m_fZoom) * m_cx + (int)(x / m_fZoom);

    this->m_Img.SetPixelColor(x, y, 
                              img_data[nOriginalPixIdx * 3 + 0],
                              img_data[nOriginalPixIdx * 3 + 1],
                              img_data[nOriginalPixIdx * 3 + 2]);
}
My original image data sits in memory in an array (img_data), and I do the arithmetic on it and store the result image in a bitmap object (m_Img) to BitBlt() to screen. Thanks

Share this post


Link to post
Share on other sites
Advertisement
Callign a separate pixel plot function is probably a bad idea. I suggest treating the destination buffer the same as you do the source (i.e. manual buffer manipulation) and handle clipping outside of the inner loop (if necessary).
This should be fairly easy if you use a DIB section as destination bitmap. And it'd probably be good idea to use full 32-bit pixels too, so that the pixels can be copied with a single instruction and everything is neatly aligned.

You should also gain a speed increase by switching to fixed point.
Float-to-int conversions tend to be fairly slow and you wouldn't have to perform two full multiplications (or two divisions and a multiplication if the compiler isn't clever enough to optimize them away) per pixel, just two additions and right shifts.

You're aware of that Win32 has hardware accelerated scaling functions in GDI (StretchBlt) and DirectDraw/Direct3D already, right?

Share this post


Link to post
Share on other sites
Hi doynax,

First, thanks for the reply. I had the complete wrong idea about StretchBlt(). I thought since it only accepts integers for the destintation size, it couldn't do anything besides integer magnification. However I guess it does the exact same type of interpolation I was trying to do all along, nearest neighbor.

Now when I use StretchBlt() I definitely see a speed increase. It is still a little sluggish when I magnify a great deal, or if I try panning when it is magnified a great deal (compiled in release mode). My draw loop is simply:


void CMyApp::OnDraw(CDC* pDC)
{
m_Img.StretchBlt(*pDC, m_nPanX, m_nPanY, (m_cx * m_fZoom), (m_cy * m_fZoom), 0, 0, m_Img.GetWidth(), m_Img.GetHeight(), SRCCOPY);
}


I guess since I am asking for a StretchBlt() every draw it may be too much. Maybe I should StretchBlt() into an HDC one time per zoom operation then just BitBlt() that?


Now as for direct draw / d3d - I originally had been using opengl, pasting my bitmap on a texture mapped quad for fast panning/zooming. However I have 16 viewports in which I'd like to display separate images, and this implementation because really awful when it came to resizing or moving the app around. I posted asking if switching to direct draw would speed this up, posters said it would not since I still need to create a device context per viewport, which is where I incurred that penalty. What do you think?

Thanks again

Share this post


Link to post
Share on other sites
You know, you can treat 16 viewports as one viewport, that is one rendering context. Divide up the space and
draw in the same window. Don't create 16 RCs. Just create one RC.

And StretchBlt() is not exactly hardware-accelerated like OpenGL and DirectX, so I would guess this is much slower.
And if you're passing large dimensions to StretchBlt(), it will try to create a huge bitmap in memory. OpenGL and DirectX is much more better.

Share this post


Link to post
Share on other sites
Hi JakeM,

I would try creating each viewport within the same device context, but I'm supposed to use windows splitter windows to separate each port, thus each port needs to be its own CView class, sadly.

Doynax, can you please explain how I could do the fixed point math here? I took clipping into consideration, and moved whatever I could to the outer loop, but it's still a little sluggish at the huge magnifications. I agree that the pixel plot may also be slowing me down, but it is from a bitmap class in Petzold's programming win 98 book and is pretty speedy - but if I could somehow directly manually alter the pixels on screen that would be way faster, is there any material on that that you know of?

Also I've noticed that the scaling is perfectly smooth if I leave all the calculations in, but just leave the raw image array indexing out:


nPixIdx = (y * m_cx + x) * 3;

m_Img.SetPixelColor(x,y,
pv[nPixIdx],
pv[nPixIdx + 1],
pv[nPixIdx + 2]);

// replace by:

m_Img.SetPixelColor(x,y, 255, 128, 64);
// now scaling is perfectly smooth without my raw array indexing!


"You should also gain a speed increase by switching to fixed point.
Float-to-int conversions tend to be fairly slow and you wouldn't have to perform two full multiplications (or two divisions and a multiplication if the compiler isn't clever enough to optimize them away) per pixel, just two additions and right shifts."

Thanks

Share this post


Link to post
Share on other sites
Yes as far as I can tell in my testing, that random access of my reference array is killing the speed. If I just put a static color in for each channel it is extremely smooth. It is just an unsigned char array, nothing special.

Since I'm only allowing uniform scaling along each axis, would it be possible to just traverse on the diagnol somehow to stop repeatedly accessing my array, and save a lot of pointless calculations?

Share this post


Link to post
Share on other sites
Ok considering I only allow the scale factor to be identical for both axes, I modified the code to the following, and now it is smooth, but I would REALLY like some opinions or suggestions. I'm also 100% sure I'm not the first to invent this speedup, so if anyone has any links to papers/articles on that I would really appreciate it. This code works when the magnification is greater than 1 - if it is less than 1, the regular old nearest neighbor will do.


// How wide/tall will a pixel now be after scaling?
int nBiggestStepSize = (int)this->m_fZoom;

// Do the magnification
for (int y = 0; y < cy; y += nBiggestStepSize) {

int yOffset = (int)(y / this->m_fZoom) * this->m_cx;

for (int x = 0; x < cx; x += nBiggestStepSize) {

int nOriginalPixIdx = (yOffset + (int)(x / this->m_fZoom)) * 3;

DWORD dwClr = 0 << 24 |
m_pvImg[nOriginalPixIdx + 0] << 16 |
m_pvImg[nOriginalPixIdx + 1] << 8 |
m_pvImg[nOriginalPixIdx + 2];

// Now I can assign all the pixels in this 'block'.
for (int i = y; i < y + nBiggestStepSize && i < cy; i++)
for (int j = x; j < x + nBiggestStepSize && j < cx; j++) {
DibSetPixel32(this->m_hDib, j, i, dwClr);
}
}
}


The basic idea is that since the scaling is the same along both axes, I can copy in both the x and y directions the same color for each 'block length'. This saves recalculating many many rows and columns, and my biggest killer of accessing my original image data array. I also stop the calculation if the borders go past my clipping area of the window which saves a lot, I didn't show that for clarity though. Thanks for any opinions suggestions,

Mark

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!