{"id":37,"date":"2013-07-08T17:03:38","date_gmt":"2013-07-08T17:03:38","guid":{"rendered":"https:\/\/blogs.scummvm.org\/t0by\/?p=37"},"modified":"2022-05-24T17:06:27","modified_gmt":"2022-05-24T17:06:27","slug":"rotation-made-stupid","status":"publish","type":"post","link":"https:\/\/blogs.scummvm.org\/t0by\/2013\/07\/08\/rotation-made-stupid\/","title":{"rendered":"Rotation made stupid"},"content":{"rendered":"
\n
In many of the more relaxed civilizations on the Outer Eastern Rim of the Galaxy, the Hitchhiker\u2019s Guide<\/i> has already supplanted the great Encyclopaedia Galactica<\/i> as the standard repository of all knowledge and wisdom, for though it has many omissions and contains much that is apocryphal, or at least wildly inaccurate, it scores over the older, more pedestrian work in two important respects. First, it is slightly cheaper; and second, it has the words \u201cDON\u2019T PANIC\u201d inscribed in large friendly letters on its cover.<\/div>\n
\u2014Hitchhiker\u2019s Guide to the Galaxy<\/div>\n<\/blockquote>\n

This is post will go into some detail explaining how to actually rotate a sprite in practice.
\nIt\u2019s a good starting point if you are rolling your own rotozoom function.
\nIt has, naturally, zero academic value and I am also quite sure you can buy manuals that will give you a better idea for just a few dollars.
\nAnd you can always troll IRC.
\nBut still.<\/p>\n

Now, we assume a little knowledge of linear algebra.
\nYou can probably go ahead all the same if you haven\u2019t taken Algebra 101, but it makes much more sense if you have.
\nThere is countless algebra books which will teach you the basics. Try Strang\u2019s or Nicholson\u2019s.<\/p>\n

That said.
\nLet\u2019s dive in.
\nWell, a sprite is a matrix of pixels, all right?
\nTo rotate, zoom it and do all the nice things we want to do we need to match a pixel in the source matrix to a pixel in the destination matrix and copy its color<\/strong>.
\n\u201cThis goes here\u201d.<\/p>\n

So \u2013 look<\/strong> at the source pixel, calculate<\/strong> where it ends up and copy<\/strong> that color. [well, almost, hold on].<\/em><\/p>\n

Copying a byte is something very simple and your language of choice already offers support for that.
\nCalculating the destination, well, we need a function for that.
\nSo we have:<\/p>\n

(x\u2019, y\u2019) = f(x, y, phi)<\/p>\n

don\u2019t we?
\nThere is the textbook formula for rotation:<\/p>\n

\"\"<\/a>\"\"<\/a><\/p>\n

I\u2019m not giving you a proof or anything (hey, if books aren\u2019t enough you can easily trick a doctoral student into doing the job for you)- it just works.
\n<\/em>We assume that rotation is carried out around the origin and that no zooming is involved.<\/p>\n

Zooming is actually rather trivial (just multiply by the desidred amount), rotating around a custom point basically means shifting the whole thing so that the hotspot is the new origin, then rotating as above, then shifting again<\/em> so that the hotspot is where it was in the first place and everything else has moved.
\nOnce you\u2019ve got the simple case, it\u2019s rather simple, though.
\nSee also:<\/p>\n

That\u2019s it. Now we can match a point in our destination sprite to a point in our source sprite.<\/strong>
\nWell, this is not quite <\/em>it.
\nYou see, while rotating points<\/em> is a rather mundane matter, we are dealing with pixels, that is\u2026 we are working in the discrete.
\nAs you can see in the drawing below, P (x,y) in the destination sprite does not match exactly any <\/em>pixel in the source.<\/p>\n

Which means that we must do some approximation.
\nWhat do we do? Well, we can either round to the nearest integer or interpolate.
\nInterpolation will be the subject of the next post, for the moment, we round.
\nWe basically want something like a).<\/p>\n

\"\"<\/a>This also means that it\u2019s wonderfully more practical to scan the destination<\/strong>, calculate where the destination pixel would end up and copy that<\/em> instead of the other way around.<\/p>\n

Now, all we need to do is to scan the whole of the destination matrix and copy the correct color into each pixel.
\nA nice for() loop will do.
\nHere you are.
\nFirst in pseudocode:<\/p>\n

procedure rotate (angle, src, dst, zoom):\r\n  begin\r\n  invAngle = 2 * PI - angle; \/\/ We need to rotate in the opposite direction, remember?\r\n  for (y = 0; y < dstH; y++):\r\n    for (x = 0; x < dstW; x++):\r\n    begin\r\n    targX = ((x * cos(invAngle) - y * sin(invAngle))) * zoom\r\n    targY = ((x * sin(invAngle) + y * cos(invAngle))) * zoom\r\n    dst[x][y] = src[targX][targY]\r\n    end\r\n  end<\/pre>\n
And now for the actual code used in my patch.
\nIt is only marginally different in that it supports custom centering (omitted above for clarity) and works in degrees instead of radians because that\u2019s what the original Wintermute Engine does.<\/p>\n
TransparentSurface *TransparentSurface::rotate(Common::Rect aSrcRect, TransformStruct transform) const {\r\nPoint32 newHotspot;\r\nRect32 rect = TransformTools::newRect(Rect32 (aSrcRect), transform, &newHotspot);\r\nCommon::Rect srcRect(0, 0, (int16)(aSrcRect.right - aSrcRect.left), (int16)(aSrcRect.bottom - aSrcRect.top));\r\nCommon::Rect dstRect(0, 0, (int16)(rect.right - rect.left), (int16)(rect.bottom - rect.top));\r\n \r\nTransparentSurface *target = new TransparentSurface();\r\nassert(format.bytesPerPixel == 4);\r\n \r\nint dstW = dstRect.width();\r\nint dstH = dstRect.height();\r\n \r\ntarget->create((uint16)dstW, (uint16)dstH, this->format);\r\n \r\nuint32 invAngle = (360 - transform._angle) % 360;\r\nfloat invCos = cos(invAngle * M_PI \/ 180.0);\r\nfloat invSin = sin(invAngle * M_PI \/ 180.0);\r\n \r\nfor (int y = 0; y < dstH; y++) {\r\nfor (int x = 0; x < dstW; x++) {\r\nint x1 = x - newHotspot.x;\r\nint y1 = y - newHotspot.y;\r\n \r\nfloat targX = ((x1 * invCos - y1 * invSin)) * 100.0 \/ transform._zoom.x + srcRect.left;\r\nfloat targY = ((x1 * invSin + y1 * invCos)) * 100.0 \/ transform._zoom.y + srcRect.top;\r\n \r\ntargX += transform._hotspot.x;\r\ntargY += transform._hotspot.y;\r\n \r\nif (FAST_TRANSFORM) {\r\nnearestCopy(targX, targY, x, y, srcRect, dstRect, this, target);\r\n} else {\r\nbilinearCopy(targX, targY, x, y, srcRect, dstRect, this, target);\r\n}\r\n}\r\n}\r\nreturn target;\r\n}\r\n<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
In many of the more relaxed civilizations on the Outer Eastern Rim of the Galaxy, the Hitchhiker\u2019s Guide has already supplanted the great Encyclopaedia Galactica as the standard repository of all knowledge and wisdom, for though it has many omissions and contains much that is apocryphal, or at least wildly inaccurate, it scores over the […]<\/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-37","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/posts\/37","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=37"}],"version-history":[{"count":2,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/posts\/37\/revisions"}],"predecessor-version":[{"id":42,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/posts\/37\/revisions\/42"}],"wp:attachment":[{"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/media?parent=37"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/categories?post=37"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.scummvm.org\/t0by\/wp-json\/wp\/v2\/tags?post=37"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}