Re: Image transformations

[Alan Third <alan@idiocy.org>]

[-- Attachment #1: Type: text/plain, Size: 3606 bytes --]

On Sat, Jun 15, 2019 at 02:31:41PM +0300, Eli Zaretskii wrote:
> > Date: Sat, 15 Jun 2019 11:42:42 +0100
> > From: Alan Third <alan@idiocy.org>
> > Cc: emacs-devel@gnu.org
> > 
> > > The matrix is defined according to XRender, AFAIU.  NS and Cairo need
> > > to transpose/invert/etc. the matrix to use it, and so will the
> > > MS-Windows code, IIUC.  The matrix fuses the actual primitive
> > > transformations into a construct which we currently don't seem to
> > > understand well, whose only "documentation" is in a tutorial that is
> > > not part of XRender's official docs.
> > 
> > I was first taught affine transformation matrices in a Mathematics for
> > Engineers course at university.
> 
> We are mis-communicating.  I know what affine transformations are, and
> I have no problems with matrix multiplication and vector algebra in
> general.  I majored in physics, so even tensors of General Relativity
> aren't a problem for me.

I know nothing of your background other than what I’ve read on here,
so I apologise for being patronising. I’ve clearly misunderstood what
you were asking for repeatedly.

> The issue I'm worried about is the geometrical meaning of each element
> of the matrix, as applied to image transformations in Emacs: whether
> it needs to be transposed before multiplying vectors by it, whether
> vectors should be left-multiplied or right-multiplied, whether the Y
> axis is assumed to go up or down, whether the [1][2] member is the
> sine of the rotation angle or its negative, etc.
> 
> Even Richard and Alp were confused for a moment about this stuff.
> Which is a clear sign that these aspects are not as trivial as it
> might sound.  IMO, we need clear documentation of that, to allow
> people make changes in the code without making mistakes.  But maybe
> I'm the only one to be bothered by that.

I think as long as we’re consistent with our own representation then
we can treat the question of whether the toolkits have transposed the
matrix terms as implementation details. The code IS consistent,
unfortunately my first attempt at documenting it WASN’T, which is
entirely on me. That caused at least some of the confusion.

The attached patch has more, hopefully better, documentation.

> > BTW, are you really keen to get rid of the matrix multiplications?
> > Anything we replace them with for XRender will simply be matrix
> > multiplications written out in long form, keeping track of each
> > element separately.
> 
> This is again a misunderstanding: I was merely suggesting to make all
> of those multiplications in image_set_transform, that's all.

OK. Do you want me to go ahead and do that? I don’t want to start
making big changes if you’re working on the Windows side. I have a
suggestion that will simplify this job though.

In another part of this thread you pointed out that crop and image
slices are doing basically the same thing. I hadn’t realised that.
Given that that’s the case, I think we should just get rid of the crop
function.

Getting rid of it will also get rid of that difficult to understand
resize ‐> crop ‐> rotate process where crop parameters have to take
the effects of the resize into account.

> Maybe I should stop talking about this and just go ahead and write the
> best code I can.  Because instead of improving things, this discussion
> seems to just proliferate misunderstandings and bad feelings.  Most
> probably, my fault, sorry.

No bad feelings on my part, just confusion, which was largely my own
fault anyway. I hope we can finish this off without any more
misunderstandings.
-- 
Alan Third

[-- Attachment #2: 0001-Document-image-transforms.patch --]
[-- Type: text/plain, Size: 14075 bytes --]

From bcd6c010f5fe78d4254d9c5e8181d37415f9744c Mon Sep 17 00:00:00 2001
From: Alan Third <alan@idiocy.org>
Date: Tue, 11 Jun 2019 20:31:24 +0100
Subject: [PATCH] Document image transforms

* doc/lispref/display.texi (Image Descriptors): Document :crop and
update :rotation.
* src/image.c: Describe the image transform matrix layout.
* test/manual/image-transforms-tests.el: New file.
---
 doc/lispref/display.texi              |  23 +++-
 src/image.c                           |  80 ++++++++++++
 test/manual/image-transforms-tests.el | 176 ++++++++++++++++++++++++++
 3 files changed, 278 insertions(+), 1 deletion(-)
 create mode 100644 test/manual/image-transforms-tests.el

diff --git a/doc/lispref/display.texi b/doc/lispref/display.texi
index 93c5217c36..5a5b77e709 100644
--- a/doc/lispref/display.texi
+++ b/doc/lispref/display.texi
@@ -5181,8 +5181,29 @@ Image Descriptors
 specified, the height/width will be adjusted by the specified scaling
 factor.
 
+@item :crop @var{geometry}
+This should be a list of the form @code{(@var{width} @var{height}
+@var{x} @var{y})}.  @var{width} and @var{height} specify the width
+and height of the cropped image.  If @var{x} is a positive number it
+specifies the offset of the cropped area from the left of the original
+image, and if negative the offset from the right. If @var{y} is a
+positive number it specifies the offset from the top of the original
+image, and if negative from the bottom. If @var{x} or @var{y} are
+@code{nil} or unspecified the crop area will be centred on the
+original image.
+
+If the crop area is outside or overlaps the edge of the image it will
+be reduced to exclude any areas outside of the image.  This means it
+is not possible to use @code{:crop} to increase the size of the image
+by entering large @var{width} or @var{height} values.
+
+Cropping is performed after scaling but before rotation.
+
 @item :rotation @var{angle}
-Specifies a rotation angle in degrees.
+Specifies a rotation angle in degrees.  Only multiples of 90 degrees
+are supported, unless the image type is @code{imagemagick}.  Positive
+values rotate clockwise, negative values counter-clockwise.  Rotation
+is performed after scaling and cropping.
 
 @item :index @var{frame}
 @xref{Multi-Frame Images}.
diff --git a/src/image.c b/src/image.c
index 86f8e8f4bb..6dc14db880 100644
--- a/src/image.c
+++ b/src/image.c
@@ -1967,6 +1967,86 @@ compute_image_size (size_t width, size_t height,
 }
 #endif /* HAVE_IMAGEMAGICK || HAVE_NATIVE_TRANSFORMS */
 
+/* image_set_rotation, image_set_crop, image_set_size and
+   image_set_transform use affine transformation matrices to perform
+   various transforms on the image.  The matrix is a 2D array of
+   doubles.  It is laid out like this:
+
+   m[0][0] = m11 | m[1][0] = m12 | m[2][0] = tx
+   --------------+---------------+-------------
+   m[0][1] = m21 | m[1][1] = m22 | m[2][1] = ty
+   --------------+---------------+-------------
+   m[0][2] = 0   | m[1][2] = 0   | m[2][2] = 1
+
+   tx and ty represent translations, m11 and m22 represent scaling
+   transforms and m21 and m12 represent shear transforms.  Most
+   graphics toolkits don't require the third row, however it is
+   necessary for multiplication.
+
+   Transforms are done by creating a matrix for each action we wish to
+   take, then multiplying the transformation matrix by each of those
+   matrices in order (matrix multiplication is not commutative).
+   After we’ve done that we can use our modified transformation matrix
+   to transform points.  We take the x and y coordinates and convert
+   them into a 3x1 matrix and multiply that by the transformation
+   matrix and it gives us a new set of coordinates:
+
+       [x]   [m11 m12 tx]   [x']
+       [y] X [m21 m22 ty] = [y']
+       [1]   [  0   0  1]   [1 ]
+
+   Luckily we don’t have to worry about the last step as the graphics
+   toolkit will do it for us.
+
+   The three transforms we are concerned with are translation, scaling
+   and rotation.  The translation matrix looks like this:
+
+       [1 0 tx]
+       [0 1 ty]
+       [0 0  1]
+
+   Where tx and ty are the amount to translate the origin in the x and
+   y coordinates, respectively.  Since we are translating the origin
+   and not the image data itself, it can appear backwards in use, for
+   example to move the image 10 pixels to the right, you would set tx
+   to -10.
+
+   To scale we use:
+
+       [x 0 0]
+       [0 y 0]
+       [0 0 1]
+
+   Where x and y are the amounts to scale in the x and y dimensions.
+   Values larger than 1 make the image larger, values smaller than 1
+   make it smaller.  Negative values flip the image.
+
+   To rotate we use:
+
+       [ cos(r) sin(r) 0]
+       [-sin(r) cos(r) 0]
+       [      0      0 1]
+
+   Where r is the angle of rotation required.  Rotation occurs around
+   the origin, not the centre of the image.  Note that mathematically
+   this is considered a counter-clockwise rotation, however because
+   our y axis is reversed, (0, 0) at the top left, it works as a
+   clockwise rotation.
+
+   The full process of rotating an image is to move the origin to the
+   centre of the image (width/2, height/2), perform the rotation, and
+   finally move the origin back to the top left of the image, which
+   may now be a different corner.
+
+   Cropping is easier as we just move the origin to the top left of
+   where we want to crop and set the width and height accordingly.
+   The matrices don’t know anything about width and height.
+
+   It's possible to pre-calculate the matrix multiplications and just
+   generate one transform matrix that will do everything we need in a
+   single step, but the maths for each element is much more complex
+   and I thought it was better to perform the steps separately.  */
+
 typedef double matrix3x3[3][3];
 
 static void
diff --git a/test/manual/image-transforms-tests.el b/test/manual/image-transforms-tests.el
new file mode 100644
index 0000000000..d601b9397e
--- /dev/null
+++ b/test/manual/image-transforms-tests.el
@@ -0,0 +1,176 @@
+;;; image-transform-tests.el --- Test suite for image transforms.
+
+;; Copyright (C) 2019 Free Software Foundation, Inc.
+
+;; Author: Alan Third <alan@idiocy.org>
+;; Keywords:       internal
+;; Human-Keywords: internal
+
+;; This file is part of GNU Emacs.
+
+;; GNU Emacs is free software: you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+
+;; GNU Emacs is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+;; GNU General Public License for more details.
+
+;; You should have received a copy of the GNU General Public License
+;; along with GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;; Type M-x test-transforms RET to generate the test buffer.
+
+;;; Code:
+
+(defun test-rotation ()
+  (let ((up "<svg height='9' width='9'><polygon points='0,8 4,0 8,8'/></svg>")
+        (down "<svg height='9' width='9'><polygon points='0,0 4,8 8,0'/></svg>")
+        (left "<svg height='9' width='9'><polygon points='8,0 0,4 8,8'/></svg>")
+        (right "<svg height='9' width='9'><polygon points='0,0 8,4 0,8'/></svg>"))
+    (insert-header "Test Rotation: rotating an image")
+    (insert-test "0" up up '(:rotation 0))
+    (insert-test "360" up up '(:rotation 360))
+    (insert-test "180" down up '(:rotation 180))
+    (insert-test "-90" left up '(:rotation -90))
+    (insert-test "90" right up '(:rotation 90))
+    (insert-test "90.0" right up '(:rotation 90.0))
+
+    ;; This should log a message and display the unrotated image.
+    (insert-test "45" up up '(:rotation 45)))
+  (insert "\n\n"))
+
+(defun test-cropping ()
+  (let ((image "<svg height='30' width='30'>
+                  <rect x='0' y='0' width='10' height='10'/>
+                  <rect x='10' y='10' width='10' height='10'
+                        style='fill:none;stroke-width:1;stroke:#000'/>
+                  <line x1='10' y1='10' x2='20' y2='20' style='stroke:#000'/>
+                  <line x1='20' y1='10' x2='10' y2='20' style='stroke:#000'/>
+                  <rect x='20' y='20' width='10' height='10'
+                        style='fill:none;stroke-width:1;stroke:#000'/>
+                </svg>")
+        (top-left "<svg height='10' width='10'>
+                     <rect x='0' y='0' width='10' height='10'/>
+                   </svg>")
+        (middle "<svg height='10' width='10'>
+                   <rect x='0' y='0' width='10' height='10'
+                         style='fill:none;stroke-width:1;stroke:#000'/>
+                   <line x1='0' y1='0' x2='10' y2='10' style='stroke:#000'/>
+                   <line x1='10' y1='0' x2='0' y2='10' style='stroke:#000'/>
+                 </svg>")
+        (bottom-right "<svg height='10' width='10'>
+                         <rect x='0' y='0' width='10' height='10'
+                               style='fill:none;stroke-width:1;stroke:#000'/>
+                       </svg>"))
+    (insert-header "Test Crop: cropping an image")
+    (insert-test "all params" top-left image '(:crop (10 10 0 0)))
+    (insert-test "width/height only" middle image '(:crop (10 10)))
+    (insert-test "negative x y" middle image '(:crop (10 10 -10 -10)))
+    (insert-test "all params" bottom-right image '(:crop (10 10 20 20))))
+  (insert "\n\n"))
+
+(defun test-scaling ()
+  (let ((image "<svg height='10' width='10'>
+                  <rect x='0' y='0' width='10' height='10'
+                        style='fill:none;stroke-width:1;stroke:#000'/>
+                  <line x1='0' y1='0' x2='10' y2='10' style='stroke:#000'/>
+                  <line x1='10' y1='0' x2='0' y2='10' style='stroke:#000'/>
+                </svg>")
+        (large "<svg height='20' width='20'>
+                  <rect x='0' y='0' width='20' height='20'
+                        style='fill:none;stroke-width:2;stroke:#000'/>
+                  <line x1='0' y1='0' x2='20' y2='20'
+                        style='stroke-width:2;stroke:#000'/>
+                  <line x1='20' y1='0' x2='0' y2='20'
+                        style='stroke-width:2;stroke:#000'/>
+                </svg>")
+        (small "<svg height='5' width='5'>
+                  <rect x='0' y='0' width='4' height='4'
+                        style='fill:none;stroke-width:1;stroke:#000'/>
+                  <line x1='0' y1='0' x2='4' y2='4' style='stroke:#000'/>
+                  <line x1='4' y1='0' x2='0' y2='4' style='stroke:#000'/>
+                </svg>"))
+    (insert-header "Test Scaling: resize an image (pixelization may occur)")
+    (insert-test "1x" image image '(:scale 1))
+    (insert-test "2x" large image '(:scale 2))
+    (insert-test "0.5x" image large '(:scale 0.5))
+    (insert-test ":max-width" image large '(:max-width 10))
+    (insert-test ":max-height" image large '(:max-height 10))
+    (insert-test "width, height" image large '(:width 10 :height 10)))
+  (insert "\n\n"))
+
+(defun test-scaling-rotation ()
+  (let ((image "<svg height='20' width='20'>
+                  <rect x='0' y='0' width='20' height='20'
+                        style='fill:none;stroke-width:1;stroke:#000'/>
+                  <rect x='0' y='0' width='10' height='10'
+                        style='fill:#000'/>
+                </svg>")
+        (x2-90 "<svg height='40' width='40'>
+                  <rect x='0' y='0' width='40' height='40'
+                        style='fill:none;stroke-width:1;stroke:#000'/>
+                  <rect x='20' y='0' width='20' height='20'
+                        style='fill:#000'/>
+                </svg>")
+        (x2--90 "<svg height='40' width='40'>
+                   <rect x='0' y='0' width='40' height='40'
+                         style='fill:none;stroke-width:1;stroke:#000'/>
+                   <rect x='0' y='20' width='20' height='20'
+                         style='fill:#000'/>
+                 </svg>")
+        (x0.5-180 "<svg height='10' width='10'>
+                     <rect x='0' y='0' width='10' height='10'
+                           style='fill:none;stroke-width:1;stroke:#000'/>
+                     <rect x='5' y='5' width='5' height='5'
+                           style='fill:#000'/>
+                   </svg>"))
+    (insert-header "Test Scaling and Rotation: resize and rotate an image (pixelization may occur)")
+    (insert-test "1x, 0 degrees" image image '(:scale 1 :rotation 0))
+    (insert-test "2x, 90 degrees" x2-90 image '(:scale 2 :rotation 90.0))
+    (insert-test "2x, -90 degrees" x2--90 image '(:scale 2 :rotation -90.0))
+    (insert-test "0.5x, 180 degrees" x0.5-180 image '(:scale 0.5 :rotation 180.0)))
+  (insert "\n\n"))
+
+(defun insert-header (description)
+  (insert description)
+  (insert "\n")
+  (indent-to 38)
+  (insert "expected")
+  (indent-to 48)
+  (insert "result")
+  (when (fboundp #'imagemagick-types)
+    (indent-to 58)
+    (insert "ImageMagick"))
+  (insert "\n"))
+
+(defun insert-test (description expected image params)
+  (indent-to 2)
+  (insert description)
+  (indent-to 40)
+  (insert-image (create-image expected 'svg t))
+  (indent-to 50)
+  (insert-image (apply #'create-image image 'svg t params))
+  (when (fboundp #'imagemagick-types)
+    (indent-to 60)
+    (insert-image (apply #'create-image image 'imagemagick t params)))
+  (insert "\n"))
+
+(defun test-transforms ()
+  (interactive)
+  (let ((buf (get-buffer "*Image Transform Test*")))
+    (if buf
+	(kill-buffer buf))
+    (switch-to-buffer (get-buffer-create "*Image Transform Test*"))
+    (erase-buffer)
+    (unless #'imagemagick-types
+      (insert "ImageMagick not detected.  ImageMagick tests will be skipped.\n\n"))
+    (test-rotation)
+    (test-cropping)
+    (test-scaling)
+    (test-scaling-rotation)
+    (goto-char (point-min))))
-- 
2.21.0