5
\$\begingroup\$

I'm trying to rotate some structures that are locked on a grid-like structure. This means I'm looking for lossless ways to rotate the tiles. Maintaining proper distances are not important, I'm aware that diagonals will be longer if we maintain the same number of filled tiles.

Here's a few examples of what I want to do (done by hand, so might be slightly off), where the red block is the front:

Example of rotations

On the left are the four cardinal directions, which are East(0°/0.0π rad), North(90°/0.5π rad), West(180°/1.0π rad) and South(270°/1.5π rad).

On the right there's ~22.5° in the top and 315° in the bottom.

Right now I'm looking mostly to do rotations in ~22.5° increments, so a full circle in 16 steps, but a general solution for the problem would be great.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think Bresenham's Line Algorithm might be a possible solution to the problem, and then treat the object as multiple lines. It's not a complete solution though as it could possible result in some loss or overlaps depending on the angles. \$\endgroup\$ – William Mariager Dec 25 '17 at 22:08
  • \$\begingroup\$ I'm under the impression that the only way to be truly lossless requires angular increments equal to the number of sides of your grid. In this case 90 degrees at a time. Everything else requires approximations unless you subdivide the grid into smaller local grids that rotate freely in the world space \$\endgroup\$ – Stephan Dec 26 '17 at 3:51
4
\$\begingroup\$

It sounds like you might be looking for Rotation by Shearing, or Alan Paeth's "A Fast Algorithm for General Raster Rotation"

I first learned about this technique via the excellent DataGenetics blog. Rather than resample an image into a new (interpolated) raster the way we'd tend to do today, rotation by shearing just shuffles the existing raster values around the grid using 3 axis-aligned shear operations (the first & last repeated):

Diagram from DataGenetics, illustrating the 3 shears

Mathematically it means breaking down the rotation matrix like so:

$$\begin{align} \begin{bmatrix}x' \\ y'\end{bmatrix} &= R_\theta \begin{bmatrix}x \\ y \end{bmatrix} \\ &= \begin{bmatrix} cos\theta & sin\theta \\ -sin\theta & cos\theta\end{bmatrix}\begin{bmatrix}x \\ y \end{bmatrix} \\ &= \begin{bmatrix} 1 & -tan(\theta/2) \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ sin\theta & 1 \end{bmatrix} \begin{bmatrix} 1 & -tan(\theta/2) \\ 0 & 1 \end{bmatrix} \begin{bmatrix}x \\ y \end{bmatrix} \\ \end{align}$$

Each of these three component matrices is an axis-aligned shear with determinant 1 (so we're not stretching the source to include more or fewer tiles of area at any step)

Each of these shears can be approximated to within the accuracy of our tile grid (subject to some aliasing & stairstep, like anytime we try to draw diagonals on a grid) by shifting whole rows (or columns) of tiles by full-tile increments (rounding the results of the tan & sin above when multiplied by the row or column indices, respectively).

Here's what that might look like in code (depending on your coordinate system, etc)...

Point PseudoRotateTile(Point original, Point center, float angle) {
    Point transformed;

    float vertical = -Tan(angle * 0.5f);

    // First shear.
    transformed.y = Round(original.y + vertical * (original.x - center.x));

    // Second shear.
    transformed.x = Round(original.x + Sin(angle) * (transformed.y - center.y));

    // Third shear
    transformed.y = Round(transformed.y + vertical * (transformed.x - center.x));

    return transformed;    
}

Just note that if you want to perform multiple rotations one after another, you should always start from the initial untransformed layout. Because of the rounding, errors can pile up and scramble the arrangement if you try to rotate a rotated result, rather than applying the total net rotation from scratch each time.

\$\endgroup\$
  • \$\begingroup\$ That looks very promising. From the looks of it, it rotates on the center of the pixel. Is it possible to rotate around a different origin point? I assume a simple way to do it would be to include some air/empty tiles in the structure so the origin point I'd like to use becomes the center. \$\endgroup\$ – William Mariager Dec 26 '17 at 11:52
  • \$\begingroup\$ You can offset the row and column indices you use by any positive or negative number to move the origin of the transformation, including fractions to shift the center in sub-tile increments. \$\endgroup\$ – DMGregory Dec 26 '17 at 11:54
  • \$\begingroup\$ Looks like there isn't going to come more answers. The update with some psuedocode was a nice improvement to the answer and the tip on always rotating from unrotated makes perfect sense. \$\endgroup\$ – William Mariager Dec 28 '17 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.