2D rotation question

[monoman]

Given a bounding box of a shape, I can calculate the width and height of the bounding box after the object has been rotated with the following formulas:

New Height = H * cos(angle) + W * sin(angle)
New Width  = H * sin(angle) + W * cos(angle)

Where H and W are the original height and width of the bounding box.

I need a formula for working in reverse. Given New Height, New Width and angle, I want to find H and W (for the same angle).

With some messing around, I came up with the following formulas:

temp = sqr(cos(angle)) - sqr(sin(angle))
H = (newHeight * cos(angle) - newWidth * sin(angle)) / temp
W = (newWidth * cos(angle) - newHeight * sin(angle)) / temp

These work for some angles but start misbehaving for other angles. Also, it can be seen that it wont work for certain angles, such as 45, because I'll be dividing by zero.

Any ideas how I can get it to work for any angle?

 

[NewtonTrino]

Basically you are rotating a point around the origin with the original coordinates H, W. So logically you should be able to just rotate back using -angle and starting with your post rotated H', W'.

Your terminology is pretty confusing though so maybe you are trying to do something else?

 

[monoman]

I don't think I can simply reverse the rotation. If I start with a 100x100 square and rotate it through 45 degrees, I'll end up with a bounding box of approx 141x141.

So, the information I have at hand is an angle of 45 degrees and a resultant box of 141x141. I need to discover that it came from an original bounding box of size 100x100. If I rotate the 141x141 box through -45 degrees, I presume it will get larger still, not smaller.

ETA: A bounding box is the smallest rectangle needed to contain the shape that is being rotated.

 

[NewtonTrino]

You are simply rotating a point. And change in the size of the box is just because you are getting the axis aligned bounding box. The box itself doesn't change size when you rotate it but the ABB does. If you throw away the actual coordinates then of course you can't reverse it because you've lost information.

Basically you need to determine what is actually is that you are trying to do because it sounds like you are bit confused. Try making a diagram. If I had more time I would draw something up for you but I'm working atm and just have time to write between compile/test cycles.

 

[jojonete]

So, the information I have at hand is an angle of 45 degrees and a resultant box of 141x141. I need to discover that it came from an original bounding box of size 100x100.

You can't. The information you have (45, 141, 141) could come from any bounding box as long as H+W=200. If you don't believe me, try H=150, W=50, angle=45.

 

[nathan]

Given a bounding box of a shape, I can calculate the width and height of the bounding box after the object has been rotated with the following formulas:

no, you cannot. What you could do is calculate the smallest (axis-aligned) box that is guaranteed to contain the rotated object. But that's not necessarily the same as the (axis-aligned) bounding box of the rotated object.

Or in other words you are presuming the original object projects to at least the four corners of the original bounding box. What if your original object was a diagonal line across that bounding box?

 

[nathan]

anyway, back to box rotations. Expressing your original formula in matrix notation gives
[latex]\left| \begin{array}{c}w' \\ h'\end{array} \right| = \left| \begin{array}{cc} \cos \phi, \sin \phi \\ \sin \phi, \cos \phi \end{array} \right| \left| \begin{array}{c}w \\ h\end{array} \right|[/latex]

So, you need to find the inverse of that 2x2 matrix -- do you know matrices? I'm not sure if this is a homework problem, so I'm not doing all your work for you

ETA: oh, your original formula only works for rotations between 0 and pi/2

 

[Dave Rogers]

Given a bounding box of a shape, I can calculate the width and height of the bounding box after the object has been rotated with the following formulas:

New Height = H * cos(angle) + W * sin(angle)
New Width  = H * sin(angle) + W * cos(angle)

Where H and W are the original height and width of the bounding box.

I think your problem starts right here. You're not calculating the width and height of the bounding box of your initial shape, but the width and height of the new bounding box of your rotated original bounding box. To take a trivial example, suppose your initial shape is a circle of radius 50, giving a bounding box 100 x 100. Rotate this shape 45º, and its bounding box is still 100 x 100.

What you are, in fact, calculating is the minimum sufficient bounding box to entirely contain the initial shape. Since, by doing so, you're not retaining any information on the actual shape, then you can't do the back transformation; you haven't retained the information necessary. Therefore, having performed the initial transformation, further transformations can only increase the size of your minimum sufficient bounding box; it can never decrease unless you incorporate information on the original shape.

Dave

 

[soylent]

What you are, in fact, calculating is the minimum sufficient bounding box to entirely contain the initial shape. Since, by doing so, you're not retaining any information on the actual shape, then you can't do the back transformation

Exactly. But if desired it is possible to rotate it back and calculate a new minimum sufficient axis-aligned bounding box, which will necessarily be bigger than the previous AABB and much bigger than the first.

As nathan suggested, his original formula only works between 0 and pi/2; the reason is that cos and sin are all positive in this range, in effect you are only considering the horizontal and vertical projection of one diagonal of the box for the new height, and the other diagonal for the new width. Try calculating the new width and height using the original formula with W = 100, H = 100, angle = -pi/4; it's zero for both.

Generally:
New minimum sufficient height = abs(H * cos(angle)) + abs(W * sin(angle))
New minimum sufficient width = abs(H * sin(angle)) + abs(W * cos(angle))

I believe the best simple answer is don't throw away the angle and don't throw away the width and height of the original AABB. Recalculate the minimum AABB when the angle is updated. A really lazy answer is to use the largest minimum sufficient bounding box, which occurs for pi/4, for all angles; then you can rotate it as much as you want and keep using the same AABB, but it is not an efficient choice of bounding box(it will in general contain lots of empty space). I.e. W' = H' = W*sqrt(2) + H*sqrt(2).

If you want to complicate things you can use object aligned boxes and the separating axis theorem(SAT). If you find any axis that separates the projections of the bounding volumes you have found a separating axis and the boxes do not touch each other. A necessary corollary, which does not follow from SAT is that for some simple objects like boxes there is a limited number of axes that can be tested to determine if any separating axis exists. In 2d it is not too narly, there are only four possible axes to test; they happen to coincide with the two perpendicular edges of each OBB.

In 3d it is harier; there are 15 axes to test, 3 perpendicular edges of box 1, 3 perpendicular edges of box 2, and the 9 possible cross-products of one axis from box 1 and one axis from box 2.

 

[monoman]

Thanks for the replies so far. Its refreshing that you seem to know what I'm talking about, though I think I need to explain what exactly I'm trying to do.

This is not a homework assignment, it's for a graphics program I'm writing where, like photoshop, an image can be rotated and stretched using the mouse. Here's a screenshot:



What's happened here is I've rotated the image about 45 degrees. Using the mouse I can then stretch the width, height, or both, depending on if the mouse is on an edge or corner.

When the image is not rotated, this is simple and all works fine. When it is rotated, I'm thinking I need to:

(1) Calculate how much the bounding box has changed. Simple.
(2) Work backwards to see how much I would need to change the original, non rotated, image's bounding box so that when it is rotated, it will result in the, erm, result.

So, for instance, if I dragged the right hand border 50 pixels, this is not the same as adding 50 pixels to the original image and rotating it. It's likely that the width and height of the original image need changing to result in that transformation of rotate 45 degrees and add 50 pixels.

I hope that's clearer!

ETA: Just to be clear, I retain all original information. Every time the image is drawn to screen, I start with the un-rotated, un-stretched image, apply the transforms, and draw.

 

[nathan]

(1) Calculate how much the bounding box has changed. Simple.
(2) Work backwards to see how much I would need to change the original, non rotated, image's bounding box so that when it is rotated, it will result in the, erm, result.

Ok, then you need to invert the matrix formula I provided. The inverse of a 2x2 matrix:
[latex]\left| \begin{array}{cc} A, B \\ C, D \end{array} \right|[/latex]
is:
[latex]\left| \begin{array}{cc} D, -B \\ -C, A \end{array} \right| / (AD - BC) [/latex]

What you're doing is not bounding box calculations, but coordinate transforms. You want to know how the mouse movements transform into the rotated coordinate system of the image. The 2D rotation transform is:
[latex]\left| \begin{array}{cc} \cos \phi, -\sin \phi \\ \sin \phi, \cos \phi \end{array} \right|[/latex]

Note the minus sign. You can reverse this transform either by doing the matrix inversion I mentioned, or by simply negating the angle of rotation -- you'll see they're equivalent.

 

[monoman]

Ok, then you need to invert the matrix formula I provided. The inverse of a 2x2 matrix:

is:

What you're doing is not bounding box calculations, but coordinate transforms. You want to know how the mouse movements transform into the rotated coordinate system of the image. The 2D rotation transform is:

Note the minus sign. You can reverse this transform either by doing the matrix inversion I mentioned, or by simply negating the angle of rotation -- you'll see they're equivalent.

Hi,

I don't think this will work.

In my image, lets say the dimensions of the box surrounding the image are 100x100. For the moment, I'll forget about stretching the box first, and just do a reverse transform on the box. This will result in a diamond shape whose enclosing box is of dimensions 141x141. The resulting box should be the dimensions of the un-rotated image, which looking at it would be around 100x50.

May be it's because I'm working with the four corners of the enclosing box but I should be working with the four corners of the rotated image? I'll have a think about that....

 

[monoman]

I'm beginning to think the way I want to do it may not possible and I may have to do it the way that photoshop does:



The image is a bit cruddy but you can see that with photoshop when you stretch the image, you are working with the actual un-rotated width and height and so there is no need to do any back calculations.

This is annoying because to do it this way, I have to mess around with finding out if the mouse cursor is within the bounds of diagonal lines!

 

[Modified]

This is annoying because to do it this way, I have to mess around with finding out if the mouse cursor is within the bounds of diagonal lines!

Just rotate the position of the mouse cursor the same as the image was rotated. That will make it easy.

 

[AvalonXQ]

Have you considered keeping the original values of the box and the angle, and calculating the increase in each of those original dimensions using the stretch and angle?
You could define a "horizontal stretch" of length x as increasing the original, un-rotated box by x*cos(theta) and x*sin(theta) and keep these data available for further rotation or un-rotation.

 

[monoman]

Have you considered keeping the original values of the box and the angle, and calculating the increase in each of those original dimensions using the stretch and angle?
You could define a "horizontal stretch" of length x as increasing the original, un-rotated box by x*cos(theta) and x*sin(theta) and keep these data available for further rotation or un-rotation.

I've had a look at that but I can't see how x*cos(theta) and x*sin(theta) can work it out for me.

Here's an example:

(1) Start with an enclosing box of 100x150.
(2) Rotate by 37 degrees
(3) The resulting enclosing box is approx. 170x180.
(4) Add 50 to the width to get 220x180.
(5) Using my equations from the OP, which sometimes work, I calculate that the original enclosing box should be approx. 245x41. That is if you rotate an enclosing box of 245x41 through 37 degrees, you end up with an enclosing box of 220x180.

 

[NewtonTrino]

You are throwing away too much information. Keep around the actual transform stack and retransform each frame instead of trying to go backwards.

I wish I had more time to draw a nice diagram for you.

 

[AvalonXQ]

I've had a look at that but I can't see how x*cos(theta) and x*sin(theta) can work it out for me.

Here's an example:

(1) Start with an enclosing box of 100x150.
(2) Rotate by 37 degrees
(3) The resulting enclosing box is approx. 170x180.
(4) Add 50 to the width to get 220x180.
(5) Using my equations from the OP, which sometimes work, I calculate that the original enclosing box should be approx. 245x41. That is if you rotate an enclosing box of 245x41 through 37 degrees, you end up with an enclosing box of 220x180.

Here's what I was recommending.
1) Start with an enclosing box of 100x50.
2) Rotate by 37 degrees. You now have an enclosing box of 170x180, and you remember (meaning, you have a variable somewhere that you keep) that your original inclosing box was 100x50 and has been rotated 37 degrees.
3) Add 50 to the width to get 220x180. You also ad 50*cos(37)=40 to the width and 50*sin(37)=30 to the height of the original box: 140x80.
4) If you want to unrotate, your enclosing box is whatever you have in memory -- in this case, 140x80.

You can double check this: rotate 140x80 by 37 degrees. What do you get?

 

[AvalonXQ]

Actually, when I do the math on rotating a 100x50 box by 37 degrees, I get 110x100. What am I doing wrong?

 

[AvalonXQ]

Here are my calculations.
Start with a 100x50 box.
Rotate it 37 degrees to get a 110x100 (100x50,37) box.
Increase the width by 50 to get a 160x100 (140x80,37) box.
If you unrotate the box, you have a 140x80 box.
To prove that you did it right, rotate the 140x80 box 37 degrees to get a... 160x150 box. Too big; where did I mess this up?