{"id":43,"date":"2013-07-22T17:06:44","date_gmt":"2013-07-22T17:06:44","guid":{"rendered":"https:\/\/blogs.scummvm.org\/t0by\/?p=43"},"modified":"2022-05-24T17:08:07","modified_gmt":"2022-05-24T17:08:07","slug":"interpolation-made-stupid","status":"publish","type":"post","link":"https:\/\/blogs.scummvm.org\/t0by\/2013\/07\/22\/interpolation-made-stupid\/","title":{"rendered":"Interpolation made stupid"},"content":{"rendered":"

Here we are again.
\nWe left talking about transforms and rotations.
\nSee, all in there is good and well, but there is a slight problem in practice I hinted at.<\/p>\n

If you remember we said how the fact that we are working in the discrete poses a problem: we have to approximate real coordintes of the destination point with integer coordinates \u2013 this, using the naive method, nearest neighbor approximation (aka: simply rounding to the next pixel) causes aliasing.<\/strong><\/p>\n

That\u2019s where interpolation kicks in.<\/strong><\/p>\n

A warning for those unaware: once again, signal processing is terribly big field and everything has vast theoretical implications (and vast practical applications too, e.g. most concepts apply to audio processing as well).
\nWe deal with the matter in an extremely practical fashion, hence the post title.<\/p>\n

Now \u2013 specifically, we deal with bilinear transform.<\/p>\n

Intuitively,<\/em> the idea is: we try to infer what colour would be a pixel at the given coordinates if there actually were one.<\/em>
\nWe can\u2019t add new information<\/strong> \u2013 this is immediately apparent by the fact that interpolated transforms are inevitably slightly \u201cblurry\u201d -, but we can eliminate the aliasing caused by abruptly rounding to the closest value.<\/p>\n

If I am not mistaken, \u201cabruptly\u201d has a special meaning in this context, and means: \u201cupper bound in frequency as per the Shannon-Nyquist theorem\u201d: http:\/\/en.wikipedia.org\/wiki\/Nyquist%E2%80%93Shannon_sampling_theorem<\/a><\/p>\n

Now, let\u2019s get going. Look at this:<\/p>\n

\"\"<\/a>(You will excuse me for posting a pic of a whiteboard, but my parallel scanner from 1997 has apprently just died)<\/p>\n

In the example, out projected source is (4\/5, 4\/5).
\nWhat would look like a pixel in (4\/5, 4\/5)?
\nWe don\u2019t really know,<\/strong> but we can estimate<\/strong> its color to be a weighted average of its neighbors.<\/p>\n

So, the math (from Wikipedia):<\/p>\n

\"\"<\/a>And now let\u2019s see some code from transparent_surface.cpp \u2013 this time you don\u2019t get the pseudocode since it\u2019s really a matter of carrying out the above and checking for a few edge cases and avoiding division by zero:<\/p>\n

\r\nvoid TransparentSurface::copyPixelBilinear(float projX, float projY, int dstX, int dstY, const Common::Rect &srcRect, const Common::Rect &dstRect, const TransparentSurface *src, TransparentSurface *dst) {\r\n            int srcW = srcRect.width();\r\n            int srcH = srcRect.height();\r\n            int dstW = dstRect.width();\r\n            int dstH = dstRect.height();\r\n \r\n            assert(dstX >= 0 && dstX < dstW);\r\n            assert(dstY >= 0 && dstY < dstH);\r\n \r\n            float x1 = floor(projX);\r\n            float x2 = ceil(projX);\r\n            float y1 = floor(projY);\r\n            float y2 = ceil(projY);\r\n \r\n            uint32 Q11, Q12, Q21, Q22;\r\n \r\n            if (x1 >= srcW || x1 < 0 || y1 >= srcH || y1 < 0) { \r\n                Q11 = 0;\r\n            } else {\r\n                Q11 = READ_UINT32((const byte *)src->getBasePtr((int)(x1 + srcRect.left),(int)(y1 + srcRect.top)));\r\n            }\r\n \r\n            if (x1 >= srcW || x1 < 0 || y2 >= srcH || y2 < 0) { \r\n                Q12 = 0;\r\n            } else {\r\n                Q12 = READ_UINT32((const byte *)src->getBasePtr((int)(x1 + srcRect.left), (int)(y2 + srcRect.top)));\r\n            }\r\n \r\n            if (x2 >= srcW || x2 < 0 || y1 >= srcH || y1 < 0) { \r\n                Q21 = 0;\r\n            } else {\r\n                Q21 = READ_UINT32((const byte *)src->getBasePtr((int)(x2 + srcRect.left), (int)(y1 + srcRect.top)));\r\n            }\r\n \r\n            if (x2 >= srcW || x2 < 0 || y2 >= srcH || y2 < 0) { \r\n                Q22 = 0;\r\n            } else {\r\n                Q22 = READ_UINT32((const byte *)src->getBasePtr((int)(x2 + srcRect.left), (int)(y2 + srcRect.top)));\r\n            }\r\n \r\n            byte *Q11s = (byte *)&Q11;\r\n            byte *Q12s = (byte *)&Q12;\r\n            byte *Q21s = (byte *)&Q21;\r\n            byte *Q22s = (byte *)&Q22;\r\n \r\n            uint32 color;\r\n            byte *dest = (byte *)&color;\r\n             \r\n            float q11x = (x2 - projX);\r\n            float q11y = (y2 - projY);\r\n            float q21x = (projX - x1);\r\n            float q21y = (y2 - projY);\r\n            float q12x = (x2 - projX);\r\n            float q12y = (projY - y1);\r\n \r\n            if (x1 == x2 && y1 == y2) {\r\n                for (int c = 0; c < 4; c++) {\r\n                    dest[c] = ((float)Q11s[c]);\r\n                }\r\n            } else {\r\n \r\n                if (x1 == x2) { \r\n                    q11x = 0.5; \r\n                    q12x = 0.5; \r\n                    q21x = 0.5; \r\n                } else if (y1 == y2) { \r\n                    q11y = 0.5; \r\n                    q12y = 0.5; \r\n                    q21y = 0.5; \r\n                } \r\n \r\n                for (int c = 0; c < 4; c++) {\r\n                    dest[c] = (byte)(\r\n                                ((float)Q11s[c]) * q11x * q11y +\r\n                                ((float)Q21s[c]) * q21x * q21y +\r\n                                ((float)Q12s[c]) * q12x * q12y +\r\n                                ((float)Q22s[c]) * (1.0 - \r\n                                                     q11x * q11y - \r\n                                                     q21x * q21y - \r\n                                                     q12x * q12y)\r\n                              );\r\n                }                   \r\n            }\r\n            WRITE_UINT32((byte *)dst->getBasePtr(dstX + dstRect.left, dstY + dstRect.top), color);\r\n}\r\n<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Here we are again. We left talking about transforms and rotations. See, all in there is good and well, but there is a slight problem in practice I hinted at. If you remember we said how the fact that we are working in the discrete poses a problem: we have to approximate real coordintes of […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-43","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/posts\/43","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/comments?post=43"}],"version-history":[{"count":2,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/posts\/43\/revisions"}],"predecessor-version":[{"id":47,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/posts\/43\/revisions\/47"}],"wp:attachment":[{"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/media?parent=43"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/categories?post=43"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/tags?post=43"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}