Page 1 of 1

non-affine transformations

Posted: Wed Aug 22, 2012 9:26 pm
by sicivsibro
Support for non-affine transformations would by nifty. I am thinking right now about circle inversions, but this opens up lots of other new opportunities.

You would need an infinite stack to store all the transformations, but this would still be context-free.

If you are willing to draw point-by-point (CIRCLE) then non-affine transformations can be simulated by disabling context-free purity... but thats really really hard.

Re: non-affine transformations

Posted: Thu Aug 30, 2012 5:06 am
by kipling
Nice idea.

Technically it should be possible for a minor variant of CF where the allowed transformations were the Möbius transformations of the complex plane. This would have a similar implementation to the current CF. In CF the transformations are easy to handle since the group of affine transformations is easily parameterised by a small number (6) of real numbers in a matrix, and the composition of many affine transformations is an affine transformation.

The same goes for Möbius transformations - a group with 4 complex parameters i.e. 8 real parameters (actually only 6 degrees of freedom, so it is a 6-dimensional real Lie group), nicely able to be represented via matrix algebra. If you also allowed reflection, then you get inversion in a circle, since z/|z|^2 (the inversion in the unit circle) is the conjugate of 1/z, a Möbius transformation.

The other nice thing about Möbius transformations is that they are conformal, and they include any translation, rotation, scaling.

If you wanted to allow Möbius transformations as well as something non-conformal, such as skewing and different x/y scaling, then I think all bets are off. I suspect that the group of these transformations (i.e. the group that CF would have to keep track of) would be infinite dimensional, and so CF couldn't keep track of them the way it does with affine. Something like you suggest (descending down the tree each time) would be required, and I think that CF has discarded much of this info as it goes - it could stack up pretty quickly.

Am I right that the reason for asking this is to get CF to inhabit hyperbolic geometry via the Poincaré disk or Poincaré half-plane? That would be remarkably cool.

Implementation? I think I'm dreaming. I couldn't do it - I've trawled through the CF source, and only understand bits, and I've only got one life. If MVJ was sufficiently excited by the idea, he might be convinced to introduce a CF::Mobius mode into v4.

Cheers, AK

Re: non-affine transformations

Posted: Thu Aug 30, 2012 8:09 pm
by MtnViewJohn
I do want to add support for perspective transforms. Once we have more than one type of transformation then adding Möbius transformations would probably be easy. I don't think I even have to write too much code. The AGG graphics template library has support for bilinear transformations.

Re: non-affine transformations

Posted: Fri Aug 31, 2012 6:50 am
by kipling
Yes I remember you saying perspective calculations were one of the things you were considering. I can see that this would be relatively easy - you just start putting things other than [0 0 1] in the bottom row of the 3x3 matrix. (I think that's right - maybe the rightmost column if you are doing it that way around)

With Möbius transformations, one advantage is that circles stay circles. The problem would be that you can't easily combine them with non-conformal transformations like skewing, etc, without having to remember and evaluate the whole list of transformations. But this could be global mode-switch for the design OR be rely on an inherited property of shapes so that warnings are thrown when the two types of transformations are mixed in a given shape's ancestry.

Re: non-affine transformations

Posted: Fri Aug 31, 2012 10:41 am
by MtnViewJohn
I like the idea of the transformation type being an inherited shape property. It's easier to implement than trying to store a global switch in a global variable that needs to be accessed everywhere. And it would be cool if a design mixed perspective, affine, and Möbius transformations. The root transformation would be a conformal transformation.

Re: non-affine transformations

Posted: Tue Sep 04, 2012 5:56 am
by kipling
OK - that would be nice. The neat thing is that similarity transformations (shift, rot, scale, flip) are in both* categories, so the decision as to what type of transformation a shape and its descendents uses could be deferred until you hit one that forces the decision one way or the other.

* - here I have perspective and affine in the same category, as each can be handled by real 3x3 matrix multiplication.

I was thinking about how I would prove to myself that the two types of transformation are genuinely irreconcilable -- i.e. that there is no simple representation of an arbitrary composition of mobius and affine transformations. The crunch is that you can come up with a version of the Smale horseshoe map, which basically wrecks any possibility of doing it.