Rotating line gets shorter

[thomas430]

Hi guys,

I wrote the following function to rotate a line (x1,y1)->(x2,y2) about a point anchor:

void Line::rotate(float angle, Point anchor)
{
    //translation of points and anchor so that the anchor is at the origin
    translate(-anchor.x(), -anchor.y());
    
    //rotation of points about the orgin using http://en.wikipedia.org/wiki/Transformation_matrix#Rotation
    x1 = x1*cos(angle) - y1*sin(angle);
    y1 = y1*cos(angle) + x1*sin(angle);
    x2 = x2*cos(angle) - y2*sin(angle);
    y2 = y2*cos(angle) + x2*sin(angle);
    
    std::cout << "line length = " << len() << std::endl;
    
    //translation of points and anchor so that the anchor is at its original position
    translate(anchor.x(), anchor.y());
}

After successive calls with angle parameter of 0.1 rad, the following is ouptut:

line length = 248.232
line length = 246.272
line length = 244.15
etc.

After successive calls with angle parameter of 0.8 rad, the following is output:

line length = 118.008
line length = 107.056
line length = 92.1782
etc.

The line is shrinking, and more rapidly with angles that result in larger sine values (the line starts to grow past an angle of pi, where the sine is negative, and less rapidly when the angle is close to 2pi; smaller sine value).

I am confident that the rotation is occurring properly as I'm drawing the resulting line to the screen and seeing what I expect, it's just that the line is shrinking.

Can anyone explain what is happening here, or how I could avoid this?

[thomas430]

Oh :-(

I modified x1 and then tried to use it to determine a value for y1. And similarly for x2 and y2.

*headdesk*


The line is still getting shorter, but now at an angle-independent rate. So this is probably just due to accumulated rounding errors? Is there a way around this that doesn't require me to return a new line, or store a rotation value?

[Disch]

I very much doubt it's rounding error. Can you post you latest function?

EDIT: new output would be nice too

[simeonz]

If x1, y1, x2, y2 are integers, it is impossible to avoid the rounding errors without increasing the payload in the class. However, you can reduce the rounding effect by using floating point type for the coordinates, or by using fixed point arithmetic (i.e. work as if x1, y1 etc. as if they are in scale 1/256 for example).

PS: If you store the rotation angle as info this will avoid the rounding error, but will complicate the entire thing. If you want to be able to change one of the vertexes after the rotation, then the rotation parameter has to be saved on a per-vertex (Point) basis. Not to mention that if you decide to go this way, you will not be able to apply translation afterward without loosing precision.

On the other hand, if the transformation is applied to some large set of geometric objects, like a scene description, then you can store it globally, and process it for each object upon request. That is, instead of transforming each object, you could have affine transformation matrix (or linear transformation matrix and translation vector) stored somewhere, and when someone tries to query the properties of some geometric entity, you apply the transformation on this entity and report the query after the transformation. If several transformations are applied one after another, you can compress them into one. The transformation data will suffer from rounding errors, but it could be saved with big precision - say long double.

[thomas430]

Here's my revised code - it's now working perfectly, with a consistent line length (not even slight rounding error for at least 100 calls).

void Line::rotate(float angle, Point anchor, bool radians)
{
    //operate in radians (other option is degrees if radians==false)
    if (!radians)
        angle = angle*TO_RADIANS;
    
    //translation of points and anchor so that the anchor is at the origin
    translate(-anchor.x(), -anchor.y());
    
    //rotation of points about the orgin
    float x = x1;
    float y = y1;
    x1 = x * cos(angle) - y * sin(angle);
    y1 = y * cos(angle) + x * sin(angle);
    
    x = x2;
    y = y2;
    x2 = x * cos(angle) - y * sin(angle);
    y2 = y * cos(angle) + x * sin(angle);
    
    std::cout << "line length: " << len() << std::endl;
    
    //translation of points and anchor so that the anchor is at its original position
    translate(anchor.x(), anchor.y());
}

line length: 250
line length: 250
line length: 250
       .
       .
       .

Simeonz, thanks for your suggestions they were good food for thought! And I think they would be applicable to other examples I have seen.

Tom.

[simeonz]

Just curious. Do you use integer or floating point coordinates for Point and Line? If you use integers, then this must be accidental from the combination of angles and points. The line should become shorter.

I mean, imagine some circle centered at the origin. Suppose that your line is aligned with the abscissa, has one vertex at the origin and the other one lying on the circle. This implies that the circle has integer radius. Only very few points on this circle will have integer coordinates, but you can move the second vertex of your line to any point on the circle using rotation. In other words, after rotation, the second vertex will most probably end up not on the integer grid and will need to be 'snapped' to it. This is rounding and it will change the length of the line.

If you use integers to represent the coordinates, try with different coordinates and rotation angles and it should still become shorter.

Regards

[ne555]

It doesn't matter how many transformations you make, you could always replace them by a matrix multiplication (a single transformation).
If you work in homogeneous coordinates, that will include translation.

Edit: I got lost. What is the difference between the two codes?
Maybe storing a transformation matrix for every object is too much, why are they moving so independently?

[simeonz]

True. My earlier point was that if several transformations are applied one after another, the matrix for the equivalent transformation is going to be inexact, due to rounding errors in matrix multiplication. In fact, if I want to rotate with angle pi/7, I can not even represent the respective transformation matrix (with say, long double components) exactly in the computer.

On the positive side, it saves a lot of time to compress a bunch of transformations performed on a collection of geometric objects into a single equivalent transformation. And you can avoid homogeneous coordinates if you want, but they suffer less from the rounding errors.

Regards

[thomas430]

@simeonz Point and Line have float representation. But you're right - in my second code where I declare float x and float y, I accidentally declared these as ints! So it was no wonder there was such huge rounding :P

As a point of interest... I saw an article somewhere with a tally of the multiplications required for applying each transformation matrix individually, as compared with finding a single transformation matrix and applying it at the end. I didn't check the math, but it turned out that applying each matrix individually required less multiplications when there were < 7 transforms ( i.e. < 7 matrices). For more than 7 transforms, it is more efficient to replace them with a single matrix.

[simeonz]

The trade-off is actually easy to see.

Suppose you have n x n matrices. Multiplying two matrices comes at the cost of multiplying n column vectors by a single n x n matrix:

A x B = A x [b1 b2 ... bn] = [(A x b1) (A x b2) ... (A x bn)]

If I have to transform m points, this requires m multiplications of type "matrix by vector" - one for each radius vector. This means a total of (m + n) such multiplications for the transformation "A times B": n for multiplying A and B to produce the equivalent transformation, and m for applying it to the radius vectors of the m points. On the other hand, applying the matrices consecutively requires m multiplications for the first transformation and m multiplications for the second (on the transformed m points) - 2m total.

2m will be slower to (m + n) when the points (m in this case) are more than the components of the vector (i.e. n). In homogeneous coordinates, the points in the plane have 3 components. So, any time you have to transform more than 3 points, you will be faster if you pre-compute the equivalent transformation first. I think the conclusion does not depend on the number of consecutive transformations. (The trade-off is again dependent on m and n only.)

The trick may not work though. If you want to rotate a single line independently of the other objects, because you want to animate it, then you will be dealing only with the two vertexes of the line and applying the transformations consecutively will be faster.

Regards