4

Given a DOM element el to which we've applied the transform matrix M (an instance of DOMMatrix), and its current bounding rectangle rect, how can we obtain the bounding rectangle rect_init that corresponds to the untransformed element?

i.e. given this code:

let rect = el.getBoundingClientRect();
el.style.transform = '';
let rect_init = el.getBoundingClientRect();
el.style.transform = M.toString();

Knowing rect and M, can we obtain rect_init?

The matrix contains only translation, uniform scale, and rotation transforms. In the illustration below the element is represented by the blue rectangle, and its post-transform bounding rectangle is the red one.

There's an older, related question whose answers don't seem to cover all combinations of translation, scale and rotation.

enter image description here

In the demo below, given M and current bbox, I'm looking for initial bbox.

let target_element = document.querySelector('#target');
let M = new DOMMatrix()
  .translate(20, 30)
  .rotate(30)
  .scale(1.25);

let init_rect = target_element.getBoundingClientRect();

target_element.style.transform = M.toString();

let rect = target_element.getBoundingClientRect();

document.querySelector('#rect-init').textContent = serialize(init_rect);
document.querySelector('#rect').textContent = serialize(rect);
document.querySelector('#matrix').textContent = M.toString();

function serialize(rect) {
  return `x: ${rect.x}; y: ${rect.y}, w: ${rect.width}, h: ${rect.height}`;
}
#target {
  background: red;
  width: 200px;
  height: 100px;
  position: absolute;
  left: 30px;
  top: 50px;
}

#info {
  background: #eee;
  padding: 1em;
  margin-top: 250px;
  font: 0.9em monospace;
}
<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width">
  <title>JS Bin</title>
</head>
<body>
  <div id='target'>Target</div>
  
  <dl id='info'>
    <dt>initial bbox: </dt>
    <dd id='rect-init'></dd>
    <dt>current bbox: </dt>
    <dd id='rect'></dd>
    <dt>M:</dt>
    <dd id='matrix'></dd>
  </dl>
</body>
</html>
Dan
  • 9,912
  • 18
  • 49
  • 70
  • 2
    the transform of point `P` is usually done by `Q = M*P` (in homogenuous coordinates `w=1` ) and the reverse is simple `P = Inverse(M)*Q` where `M` is your transform matrix... In case you got different notation it can be inverted `Q = Inverse(M)*P; P = M*Q;` or if transposed then `Q = Transpose(P)*M; P = Transpose(Q)*Inverse(M);` or both ... so simply transform your vertexes of BBOX to coordinates you want ... – Spektre Jan 13 '21 at 20:49
  • @Spektre I'm trying to find the coordinates of the rectangle's top-left corner given the following: (1) The transform matrix M (2) the coordinates of the top-left corner of the transformed rectangle's _bounding box_. Applying the inverse of M to it gives us something that may aid in the computation, but does not produce the final solution. – Dan Jan 18 '21 at 13:53
  • provide a sample: so I can try ... so I need the BBOX, the matrix and preview how it should look so I can match the correct equations as there are 4 combinations for the transform alone ... – Spektre Jan 18 '21 at 16:05
  • I've updated the question to include a code snippet that produces some sample values for _current bbox_ and _M_. – Dan Jan 19 '21 at 15:21
  • can you also add the matrix? right now you are constructing it using basic operations like scale,translate,rotate however the result can have 4 possible notations ... to know which you are using I need the 9 values of the 3x3 2D transform matrix (some XMLs use 2x3=6 elements as the last row is usually `0,0,1` – Spektre Jan 19 '21 at 17:04
  • The output of the snippet includes the serialized matrix M in the form `matrix(a, b, c, d, e, f)`, which is equivalent to this transform matrix: https://drafts.csswg.org/css-transforms/images/matrix.png – Dan Jan 20 '21 at 11:22
  • :) do you have the `a,b,c,d,e,f` values ? that image just tells me that columns are vectors (just like in OpenGL) in case matrix is direct (case its `M*V`) but I think it also can be `Transpose(V)*Inv(M)` that is why I want the matrix and preview ... so I can clearly decide which of the notations you got exactly and not to factor all posibilities by 2 or 4 on each operation ... and build the reverse transform from there ... instead of assuming everything ... – Spektre Jan 20 '21 at 12:10
  • 1
    Sorry if I don't 100% follow... If you run the above code snippet, its visual output includes (in a grey box under the red rectangle) the value for the matrix M: `matrix(1.0825317547305484, 0.6249999999999999, -0.6249999999999999, 1.0825317547305484, 20, 30)`; the numbers correspond to the `a-f` values. Is this the information you need? – Dan Jan 20 '21 at 14:04
  • ok finally we can get somewhere ... your screen coordinates are x going right and y going down ? – Spektre Jan 20 '21 at 14:09
  • yep, the origin of the coordinate system is at the top-left corner. – Dan Jan 20 '21 at 14:27
  • I managed to mimic your transformation so now which points you want in the rectangle local coordinates? I assuming the RED rectangle on the left... – Spektre Jan 20 '21 at 14:30
  • Given the coordinates of the _transformed_ rectangle's bounding box (red circle on the right-hand side of the illustration), and the matrix M, I want to find the coordinates of the untransformed rectangle, i.e. the top-left corner of the rectangle prior to applying M to it. In the code sample, given _rect_ and _M_, find _init_rect_. – Dan Jan 20 '21 at 15:23
  • Another formulation of the problem: Given a transformed rectangle, for which you can only obtain its bounding box (and not the coordinates of its vertices), and having the matrix M that was applied to it, can we compute the coordinates of its vertices prior to the transform, mathematically? (pragmatically, the DOM has mechanisms of undoing the transformation and obtaining the original bbox, but if we wanted to avoid the overhead) – Dan Jan 20 '21 at 15:30
  • check my answer ... if the `m` you provided and the axises description from your comments match then it should work ... beware your transformation uses Inverse of `m` like in DirectX ... however the angle of rectangle does not match your preview so either aspect ratio correction messed that or the `m` was not used to create your preview – Spektre Jan 20 '21 at 15:33

1 Answers1

0

I managed to get it working ...

so I did a small C++/OpenGL example where I test this:

//---------------------------------------------------------------------------
//--- input data ------------------------------------------------------------
//---------------------------------------------------------------------------
double m[16]=       // matrix
    {
    1.0825317547305484,-0.6249999999999999,0.0,20.0,
    0.6249999999999999, 1.0825317547305484,0.0,30.0,
    0.0               , 0.0               ,1.0,0.0 ,
    0.0               , 0.0               ,0.0,1.0
    };
double a[4][3]=     // your un-transformed rectangle
    {
    { 30    ,50    ,0 },
    { 30+200,50    ,0 },
    { 30+200,50+100,0 },
    { 30    ,50+100,0 },
    };
//---------------------------------------------------------------------------
//--- just matrix and vector math you can ignore this -----------------------
//---------------------------------------------------------------------------
void  vector_copy      (double *c,double *a) { for(int i=0;i<3;i++) c[i]=a[i]; }
void  matrix_mul       (double *c,double *a,double *b)  // c[16] = a[16]*b[16]
    {
    double q[16];
    q[ 0]=(a[ 0]*b[ 0])+(a[ 1]*b[ 4])+(a[ 2]*b[ 8])+(a[ 3]*b[12]);
    q[ 1]=(a[ 0]*b[ 1])+(a[ 1]*b[ 5])+(a[ 2]*b[ 9])+(a[ 3]*b[13]);
    q[ 2]=(a[ 0]*b[ 2])+(a[ 1]*b[ 6])+(a[ 2]*b[10])+(a[ 3]*b[14]);
    q[ 3]=(a[ 0]*b[ 3])+(a[ 1]*b[ 7])+(a[ 2]*b[11])+(a[ 3]*b[15]);
    q[ 4]=(a[ 4]*b[ 0])+(a[ 5]*b[ 4])+(a[ 6]*b[ 8])+(a[ 7]*b[12]);
    q[ 5]=(a[ 4]*b[ 1])+(a[ 5]*b[ 5])+(a[ 6]*b[ 9])+(a[ 7]*b[13]);
    q[ 6]=(a[ 4]*b[ 2])+(a[ 5]*b[ 6])+(a[ 6]*b[10])+(a[ 7]*b[14]);
    q[ 7]=(a[ 4]*b[ 3])+(a[ 5]*b[ 7])+(a[ 6]*b[11])+(a[ 7]*b[15]);
    q[ 8]=(a[ 8]*b[ 0])+(a[ 9]*b[ 4])+(a[10]*b[ 8])+(a[11]*b[12]);
    q[ 9]=(a[ 8]*b[ 1])+(a[ 9]*b[ 5])+(a[10]*b[ 9])+(a[11]*b[13]);
    q[10]=(a[ 8]*b[ 2])+(a[ 9]*b[ 6])+(a[10]*b[10])+(a[11]*b[14]);
    q[11]=(a[ 8]*b[ 3])+(a[ 9]*b[ 7])+(a[10]*b[11])+(a[11]*b[15]);
    q[12]=(a[12]*b[ 0])+(a[13]*b[ 4])+(a[14]*b[ 8])+(a[15]*b[12]);
    q[13]=(a[12]*b[ 1])+(a[13]*b[ 5])+(a[14]*b[ 9])+(a[15]*b[13]);
    q[14]=(a[12]*b[ 2])+(a[13]*b[ 6])+(a[14]*b[10])+(a[15]*b[14]);
    q[15]=(a[12]*b[ 3])+(a[13]*b[ 7])+(a[14]*b[11])+(a[15]*b[15]);
    for(int i=0;i<16;i++) c[i]=q[i];
    }
void  matrix_mul_vector(double *c,double *a,double *b)      // c[3] = a[16]*b[3]
    {
    double q[3];
    q[0]=(a[ 0]*b[0])+(a[ 4]*b[1])+(a[ 8]*b[2])+(a[12]);
    q[1]=(a[ 1]*b[0])+(a[ 5]*b[1])+(a[ 9]*b[2])+(a[13]);
    q[2]=(a[ 2]*b[0])+(a[ 6]*b[1])+(a[10]*b[2])+(a[14]);
    for(int i=0;i<3;i++) c[i]=q[i];
    }
void  matrix_subdet    (double *c,double *a);               // c[16] = all subdets of a[16]
double matrix_subdet   (          double *a,int r,int s);   //       = subdet(r,s) of a[16]
double matrix_det      (          double *a);               //       = det of a[16]
double matrix_det      (          double *a,double *b);     //       = det of a[16] and subdets b[16]
void  matrix_inv2       (double *c,double *a);              // c[16] = a[16] ^ -1
void  matrix_subdet    (double *c,double *a)
        {
        double   q[16];
        int     i,j;
        for (i=0;i<4;i++)
         for (j=0;j<4;j++)
          q[j+(i<<2)]=matrix_subdet(a,i,j);
        for (i=0;i<16;i++) c[i]=q[i];
        }
double matrix_subdet    (         double *a,int r,int s)
        {
        double   c,q[9];
        int     i,j,k;
        k=0;                            // q = sub matrix
        for (j=0;j<4;j++)
         if (j!=s)
          for (i=0;i<4;i++)
           if (i!=r)
                {
                q[k]=a[i+(j<<2)];
                k++;
                }
        c=0;
        c+=q[0]*q[4]*q[8];
        c+=q[1]*q[5]*q[6];
        c+=q[2]*q[3]*q[7];
        c-=q[0]*q[5]*q[7];
        c-=q[1]*q[3]*q[8];
        c-=q[2]*q[4]*q[6];
        if (int((r+s)&1)) c=-c;       // add signum
        return c;
        }
double matrix_det       (         double *a)
        {
        double c=0;
        c+=a[ 0]*matrix_subdet(a,0,0);
        c+=a[ 4]*matrix_subdet(a,0,1);
        c+=a[ 8]*matrix_subdet(a,0,2);
        c+=a[12]*matrix_subdet(a,0,3);
        return c;
        }
double matrix_det       (         double *a,double *b)
        {
        double c=0;
        c+=a[ 0]*b[ 0];
        c+=a[ 4]*b[ 1];
        c+=a[ 8]*b[ 2];
        c+=a[12]*b[ 3];
        return c;
        }
void  matrix_inv(double *c,double *a)
        {
        double   d[16],D;
        matrix_subdet(d,a);
        D=matrix_det(a,d);
        if (D) D=1.0/D;
        for (int i=0;i<16;i++) c[i]=d[i]*D;
        }
//---------------------------------------------------------------------------
//--- render ----------------------------------------------------------------
//---------------------------------------------------------------------------
void TForm1::draw()
    {
    int i;
    double xs=ClientWidth,ys=ClientHeight; // just my GL view resolution
    double p[3],im[16]; // some temp point and inverse matrix
    double b[4][3];     // your rectangle
    matrix_inv(im,m);   // im=Inverse(m)

    glClear(GL_COLOR_BUFFER_BIT);
    glDisable(GL_CULL_FACE);
    glDisable(GL_DEPTH_TEST);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glTranslated(-0.5,+0.5,0.0);
    glScaled(2.0/xs,-2.0/ys,1.0);
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();

    // render transformed a and compute its BBOX into b
    glColor3d(0.0,0.5,0.5); // aqua
    glBegin(GL_LINE_LOOP);
    for (i=0;i<4;i++)
        {
        // transform and render rectangle a
        matrix_mul_vector(p,im,a[i]);   // p = inverse(m)*a[i]
        glVertex2dv(p);
        // compute transformed BBOX b[0]=min(p) b[2]=max(p)
        if (i==0)
            {
            vector_copy(b[0],p);
            vector_copy(b[2],p);
            }
        if (b[0][0]>p[0]) b[0][0]=p[0];
        if (b[2][0]<p[0]) b[2][0]=p[0];
        if (b[0][1]>p[1]) b[0][1]=p[1];
        if (b[2][1]<p[1]) b[2][1]=p[1];
        }
    glEnd();
    // convert BBOX b[0],b[2] to rectangle
    b[1][0]=b[2][0];
    b[1][1]=b[0][1];
    b[3][0]=b[0][0];
    b[3][1]=b[2][1];

    // render transformed b
    glColor3d(0.8,0.0,0.0); // red
    glBegin(GL_LINE_LOOP);
    for (i=0;i<4;i++) glVertex2dv(b[i]); glEnd();

    // untransform b to rectangle local coordinates
    for (i=0;i<4;i++) matrix_mul_vector(b[i],m,b[i]);   // b[i] = m*b[i]

    // render a,b in local coordiantes (untransformed)
    glColor3d(0.0,0.25,0.25); // aqua
    glBegin(GL_LINE_LOOP);
    for (i=0;i<4;i++) glVertex2dv(a[i]);
    glEnd();
    glColor3d(0.4,0.0,0.0); // red
    glBegin(GL_LINE_LOOP);
    for (i=0;i<4;i++) glVertex2dv(b[i]);
    glEnd();


    glFlush();
    SwapBuffers(hdc);
    }
//---------------------------------------------------------------------------

And tweaked the transformation notation of yours until it matched your preview:

preview

the more lighter colors correspond to stuff transformed by m and the darker are without transformation (rectangle local).

I figured out that your notation for transformation of p into canvas coordinates is:

p' = Inverse(m)*p

So to transform back you would normaly be done with:

p = m*p`

However if your inverse matrix is just pseudo inverse (like this) to get it working you need to divide the inverted matrix by scale.

So if you got the points of BBOX you just multiply m with them and the result is what you seek.

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Thanks for taking the time to write this up. In your code, if _a_ is the original rectangle, _m_ is the matrix transformation that was applied to it, and _b_ is the bounding box of the transformed rectangle — how can I obtain (if there's even any way) the original rectangle _a_ if I only have _m_ and _b_? That is the gist of my question. – Dan Jan 20 '21 at 15:45
  • @DanBurzo `b` is min/max of `Inverse(m)*a` so you just do `b' = m*b`. Hope my matrix math is not transponated to yours (its in OpenGL style as matrices are column major there so just in case I provided the math functions too)... beware you need to use points !!! if you have vectors (or deltas rec sizes) instead then you need to use `w=0` for those instead of `w=1` – Spektre Jan 20 '21 at 15:51
  • I'm sorry, just to reiterate: understand I can compute `b'` by applying the inverse of `m`. But it's not what I am looking for. I am looking to obtain `a` from this `b'`. I don't already have `a`, I'm looking to find it if I only have `b` and `m`. Does that make sense? – Dan Jan 20 '21 at 15:53
  • @DanBurzo applying `m` will get you from screen into object local coordinates... applying `Inverse(m)` will get you from object local to screen .... You want the first. – Spektre Jan 20 '21 at 15:54
  • This is my last attempt to describe the problem as I'm running out of ideas: You have an normal, axis-aligned rectangle `a` that's at the `(50,30)` coords, it has a width of `200`, and a height of `100`. You transform it using a matrix `m` to obtain the rectangle `a'`. You read `a'`'s bounding box `b`, then then boom! A COMPUTER GLITCH DESTROYS `a` and `a'` and you've lost your original rectangle. You only have `b` and `m`. How can you obtain `a` back, how can you compute that it was located at the `(50, 30)` coordinates? Applying the inverse to the bounding box is not the answer. – Dan Jan 20 '21 at 16:04
  • Either that or I'm severely misunderstanding something about your proposed solution... – Dan Jan 20 '21 at 16:05
  • @DanBurzo 1. your notations uses inverse matrix so in order to get `a'` you apply inverse of `m` instead of `m` !!! 2. width and height are deltas (like vector) so you need to convert those and position into 4 point of your rectangle first and transform that (using `Inverse(m)`. 3. by transforming `b` back `b' = m*b` you obtain the BBOX of `a'` in a rectangle local coordinates but you can not obtain `a` from it directly !!! you might fit axis aligned rectangle inside it but there are infinite number of those ... unless you got some more info.4. I was understanding you wanted just the `b'` – Spektre Jan 20 '21 at 16:14
  • @DanBurzo for example if you got aspect ratio of the `a` then its possible to reconstruct – Spektre Jan 20 '21 at 16:18
  • Yes, that is exactly where I was going with this question! Can we reconstruct `a` given the information at hand, and if yes, how. I suspected that the infinite number of axis-aligned rectangles can be narrowed down to a single solution if we can look at aspects of `M` (e.g. rotation angle), and wanted to find out if someone has a mathematically-sound solution to this problem. – Dan Jan 20 '21 at 16:21
  • @DanBurzo hmm maybe but not sure if it would be a single solution more like range – Spektre Jan 20 '21 at 16:24
  • 1
    @DanBurzo need t think about that for a while – Spektre Jan 20 '21 at 16:27
  • 1
    @DanBurzo Hmm the only thing I can think of is to fit some function that would estimate the angle difference between red and aqua rectangles diagonals from angle m is rotated with and red rectangle aspect ratio... but can not figure it out. maybe something hit me latter on ... however no matter what I tried for now infinite number of solutions popped up ... – Spektre Jan 20 '21 at 17:42
  • 1
    @Spektre: I believe I have a sibling here: https://stackoverflow.com/questions/64402167/how-to-get-back-the-original-aabb-from-obb – deblocker Feb 05 '21 at 15:22
  • @deblocker looks like it ... however your tags are not in my favourite list so I didn't see it before – Spektre Feb 05 '21 at 17:13