[gegl] transform-core.c comments: explanation of how the left 2 right and top 2 bottom speed trick works fo
- From: Nicolas Robidoux <nrobidoux src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gegl] transform-core.c comments: explanation of how the left 2 right and top 2 bottom speed trick works fo
- Date: Sun, 9 Dec 2012 02:38:06 +0000 (UTC)
commit 032e47d9b7211704fd7cdec52d19eb4a79931599
Author: Nicolas Robidoux <nrobidoux git gnome org>
Date: Sat Dec 8 21:37:58 2012 -0500
transform-core.c comments: explanation of how the left 2 right and top 2 bottom speed trick works for affine transformations
operations/transform/transform-core.c | 77 +++++++++++++++++++++++++++++++-
1 files changed, 74 insertions(+), 3 deletions(-)
---
diff --git a/operations/transform/transform-core.c b/operations/transform/transform-core.c
index 96d0b84..1dc2d20 100644
--- a/operations/transform/transform-core.c
+++ b/operations/transform/transform-core.c
@@ -826,6 +826,74 @@ transform_affine (GeglBuffer *dest,
GEGL_BUFFER_WRITE,
GEGL_ABYSS_NONE);
+ /*
+ * This code uses a (novel?) trick by Nicolas Robidoux that
+ * minimizes tile buffer reallocation when affine transformations
+ * "flip" things.
+ *
+ * Explanation:
+ *
+ * GEGL uses square buffer tiles in "output space", which this
+ * function fills with data. Pulling a scanline (within such a
+ * square tile) back to input space (with the inverse
+ * transformation) with an arbitrary affine transformation may make
+ * the scanline go from right to left in input space even though it
+ * goes form left to right in input space. Similarly, a scanline
+ * which is below the first one in output space may be above in
+ * input space. Unfortunately, input buffer tiles (which are square)
+ * are allocated with a bias: less elbow room around the
+ * context_rect (square of data needed by the sampler) is put at the
+ * left and top than at the right and bottom. (Such asymetrical
+ * elbow room is beneficial when resizing, for example, since input
+ * space is then traversed from left to right and top to bottom,
+ * which means that the left and top elbow room is not used in this
+ * situation.) When the affine transformation "flips" things,
+ * however, the elbow room is "on the wrong side", and for this
+ * reason such transformations run much much slower because many
+ * more input buffer tiles get created. One way to make things
+ * better is to traverse the output buffer tile in an appropriate
+ * chosen "reverse order" so that the "short" elbow room is "behind"
+ * instead of "ahead".
+ *
+ * Things are actually a bit more complicated than that. Here is a
+ * terse description of what's actually done, without a full
+ * explanation of why.
+ *
+ * Let's consider a scanline of the output tile which we want to
+ * fill. Pull this scanline back to input space. Assume that we are
+ * using a freshly created input tile. What direction would maximize
+ * the number of pulled back input pixels that we can fit in the
+ * input tile? Because the input tile is square and most of the
+ * extra elbow room is at the bottom and right, the "best" direction
+ * is going down the diagonal of the square, approximately from top
+ * left to bottom right.
+ *
+ * Of course, we do not have control over the actual line traced by
+ * the output scanline in input space. But what the above tells us
+ * is that if the inner product of the pulled back "scanline vector"
+ * with the vector (1,1) (which corresponds to going diagonally from
+ * top-left to bottom-right in images) is negative, we are going
+ * opposite to "best". This can be rectified by filling the output
+ * scanline in reverse order: from right to left in output space.
+ *
+ * Similarly, when one computes the next scanline, one can ask
+ * whether it's the one above or below in output space which is most
+ * likely to "stick out". Repeating the same argument used for a
+ * single scanline, we see that the sign of the inner product of the
+ * inverse image of the vector that points straight down in output
+ * space with the input space vector (1,1) tells us whether we
+ * should fill the output tile from the top down or from the bottom
+ * up.
+ *
+ * Making the "best" happen requires stepping in the "right
+ * direction" both w.r.t. to data pointers and geometrical steps.
+ * In the following code, adjusting the "geometrical steps" so they
+ * go in the right direction is done by modifying the inverse
+ * Jacobian matrix to minimize the number of "geometrical
+ * quantities" floating around. It could be done leaving the
+ * Jacobian matrix alone.
+ */
+
while (gegl_buffer_iterator_next (i))
{
GeglRectangle *roi = &i->roi[0];
@@ -840,9 +908,12 @@ transform_affine (GeglBuffer *dest,
* that support it. The inverse jacobian will be "flipped" if
* the direction in which the ROI is filled is flipped. Flipping
* the inverse jacobian is not necessary for the samplers' sake,
- * but it makes the following code shorter. "Sane" use of the
- * inverse jacobian by a sampler only cares for its effect on
- * sets, irrespective of orientation issues.
+ * but it makes the following code shorter. Anyway, "sane" use
+ * of the inverse jacobian by a sampler only cares for its
+ * effect on sets: only the image of a centered square with
+ * sides aligned with the coordinate axes, or a centered disc,
+ * matters, irrespective of orientation ("left-hand" VS
+ * "right-hand") issues.
*/
inverse_jacobian.coeff [0][0] = inverse.coeff [0][0];
inverse_jacobian.coeff [0][1] = inverse.coeff [0][1];
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]