~eliasnaur/gio

5 3

Affine transforms

Péter Szilágyi
Details
Message ID
<CANBVciLXCcBAK7EV5o7nfQfMcS86fo8ojZB7R=FnAXmjM0tYRw@mail.gmail.com>
DKIM signature
pass
Download raw message
Hey all,

  Wanted to play around a bit with Gio, add some basic widget to get
the hang of it (spinner). I did manage to get my spinner to look and
render ok, but my little project fell short when wanting to animate it
as there is no built in rotation transform currently.

  So, I figured how hard can it be, an replaced the op.TransformOp
from it's current TODO form into a proper matrix version supporting
translation, rotation, scaling and shearing. Then all hell broke
loose.

  Turns out that Gio uses the inverse of the transform for some reason
in the pointer implementation. Calculating the inverse for offset-only
transforms is trivial, but with my generic matrix implementation, the
inverse would be insanely expensive. Does Gio really really need the
inverse of the transform matrix to handle user input?

  My second issue is that the GPU layout seems to be completely borked
with regard to transforms. As far as I see the code, the layout engine
modifies the origin-point according to the transform op, and then uses
it as a plain offset. This cannot work for any other transformation
type, since we'd need to transform the objects being rendered, not the
0 coordinate.

  Lastly the code seems to be using the wrong order for matrix
multiplication. Offsetting a point P by O and then rotating by R
should be calculated as RxOxP, not OxRxP (as the current code does).

Not sure how to proceed with fixing these issues. Maybe we should take
it one step at a time and figure out if we can get rid of the inverse,
then that will allow proper matrix ops, then we can fix the layout
engine. Unfortunately I'm way over my head already so I need some help
figuring the internals out.

Cheers,
  Peter
Details
Message ID
<BYN2VO3Y6NG8.1O17B1SW4DM16@testmac>
In-Reply-To
<CANBVciLXCcBAK7EV5o7nfQfMcS86fo8ojZB7R=FnAXmjM0tYRw@mail.gmail.com> (view parent)
DKIM signature
pass
Download raw message
On Sat Nov 23, 2019 at 3:39 AM Péter Szilágyi wrote:
> 
>   Turns out that Gio uses the inverse of the transform for some reason
> in the pointer implementation. Calculating the inverse for offset-only
> transforms is trivial, but with my generic matrix implementation, the
> inverse would be insanely expensive. Does Gio really really need the
> inverse of the transform matrix to handle user input?
> 

I think so. The reason is that TransformOps affect (pointer) input as
well as drawing. The inverse transformation is needed to transform a
pointer coordinate to the pointer.AreaOps that define hit areas.

Most programs use very few if any affine transforms, so a way to
optimize the common offset case is to let TransformOp know its own
complexity and only activate the expensive paths when needed.

Further, inverting a general matrix is expensive, but inverting an
affine transformation is not. See for example

	http://negativeprobability.blogspot.com/2011/11/affine-transformations-and-their.html

>   My second issue is that the GPU layout seems to be completely borked
> with regard to transforms. As far as I see the code, the layout engine
> modifies the origin-point according to the transform op, and then uses
> it as a plain offset. This cannot work for any other transformation
> type, since we'd need to transform the objects being rendered, not the
> 0 coordinate.
> 
>   Lastly the code seems to be using the wrong order for matrix
> multiplication. Offsetting a point P by O and then rotating by R
> should be calculated as RxOxP, not OxRxP (as the current code does).
> 

Yes, the GPU code is one of the reasons affine transforms were left as a
TODO :) The good news is that the underlying algorithm from Pathfinder
does work with affine transform, so it's "just" a question of fixing the
GPU shortcuts I took.

> Not sure how to proceed with fixing these issues. Maybe we should take
> it one step at a time and figure out if we can get rid of the inverse,
> then that will allow proper matrix ops, then we can fix the layout
> engine. Unfortunately I'm way over my head already so I need some help
> figuring the internals out.
> 

A starting point is to change the representation of TransformOp to fit
affine 3D transformations and add corresponding methods. Perhaps
encoding into op.Ops should be optimized so offset transformations
only take up, say, a type byte and 2 float32s. Meanwhile we can fix
the RxOxP ordering bugs you mentioned above.

Then, change the GPU shaders to use matrices, not just offsets.
Check that programs still work (with offset transformations, not
yet with affine transformations).

With that done, we can start chipping away at the various offset
assumptions in the GPU code.

-- elias
Details
Message ID
<CANBVci+QGyU=kdrmbNhUDQoaLZG7mmq2YoMzVZ6ZnWZJitp7Uw@mail.gmail.com>
In-Reply-To
<BYN2VO3Y6NG8.1O17B1SW4DM16@testmac> (view parent)
DKIM signature
pass
Download raw message
Hey there,

> Further, inverting a general matrix is expensive, but inverting an
> affine transformation is not. See for example
>
>         http://negativeprobability.blogspot.com/2011/11/affine-transformations-and-their.html

I'm not sure that article is completely accurate. It only talks about
inverting 1 rotation and 1 translation. Generally you can do multiple
translation-rotation-translation rounds, and also scaling and (less
likely) shearing come into play. I doubt that it would be so easy to
invert a long chain of transforms.

> A starting point is to change the representation of TransformOp to fit
> affine 3D transformations and add corresponding methods. Perhaps
> encoding into op.Ops should be optimized so offset transformations
> only take up, say, a type byte and 2 float32s. Meanwhile we can fix
> the RxOxP ordering bugs you mentioned above.

Done, sent in a patch.

Cheers,
  Peter
Details
Message ID
<CAMQ7dq6JjRN7BqoK9aU3_aBZL2KB0oZGgu0pdHvVKK=WCh1JYw@mail.gmail.com>
In-Reply-To
<CANBVci+QGyU=kdrmbNhUDQoaLZG7mmq2YoMzVZ6ZnWZJitp7Uw@mail.gmail.com> (view parent)
DKIM signature
pass
Download raw message
You don't necessarily have to compute the inverse. You could always
keep an inverse matrix alongside each forward transform, and
reverse-append inverse transformations to it whenever you append
transformations to the main matrix.

Also, I think repeated affine transformations are no more complex than
a single affine transformation in the end…

On Sat, Nov 23, 2019 at 9:28 AM Péter Szilágyi <peterke@gmail.com> wrote:
>
> Hey there,
>
> > Further, inverting a general matrix is expensive, but inverting an
> > affine transformation is not. See for example
> >
> >         http://negativeprobability.blogspot.com/2011/11/affine-transformations-and-their.html
>
> I'm not sure that article is completely accurate. It only talks about
> inverting 1 rotation and 1 translation. Generally you can do multiple
> translation-rotation-translation rounds, and also scaling and (less
> likely) shearing come into play. I doubt that it would be so easy to
> invert a long chain of transforms.
>
> > A starting point is to change the representation of TransformOp to fit
> > affine 3D transformations and add corresponding methods. Perhaps
> > encoding into op.Ops should be optimized so offset transformations
> > only take up, say, a type byte and 2 float32s. Meanwhile we can fix
> > the RxOxP ordering bugs you mentioned above.
>
> Done, sent in a patch.
>
> Cheers,
>   Peter
Details
Message ID
<CANBVci+QOh_AegqkFoDPCHF3+q3GrPy=5B3jhE3U4tBw9762KQ@mail.gmail.com>
In-Reply-To
<CAMQ7dq6JjRN7BqoK9aU3_aBZL2KB0oZGgu0pdHvVKK=WCh1JYw@mail.gmail.com> (view parent)
DKIM signature
pass
Download raw message
> You don't necessarily have to compute the inverse. You could always
> keep an inverse matrix alongside each forward transform, and
> reverse-append inverse transformations to it whenever you append
> transformations to the main matrix.

Ah, that's a good idea. I can compute the inverse on the fly just by
inverting the ops individually and doing a reverse order
multiplication. Cool, will update the PR with that :)
Details
Message ID
<CANBVciLj=gLTt=4GO6izsgM1jupeOzb+472eF5gExKeDMNAN=g@mail.gmail.com>
In-Reply-To
<CANBVci+QOh_AegqkFoDPCHF3+q3GrPy=5B3jhE3U4tBw9762KQ@mail.gmail.com> (view parent)
DKIM signature
pass
Download raw message
> Ah, that's a good idea. I can compute the inverse on the fly just by
> inverting the ops individually and doing a reverse order
> multiplication. Cool, will update the PR with that :)

Updated the PR so that the inverse matrices are maintained too
https://lists.sr.ht/~eliasnaur/gio-patches/patches/9128. PTAL