Posible EWA speed improvement

[NicolasRobidoux]

It would seem to me that using the intersection of the bounding box (with all sides parallel to the axes) and the bounding parallelogram (with horizontal top and bottom, but not necessarily vertical sides) to select which pixels to select would be a cheap way of speeding up the computation when the ellipse is slanted. (Probably not a huge improvement, and certainly no difference when resizing, but easy and cheap, so why not.)

(Unfortunately, I have no time for this now.)

[anthony]

First I moved this discussion to Digital Image Processing as it is very general and not specific to IM and its implementation.

Actually I looked at that bounds solution, and was in fact implementing that bounds when I realised I could simplify it a little, leading to the parallelogram bounds.

As a FYI here is my parallelogram bounds diagram...

Essentially it equivalent to a square bounds of a circle that is sheared to form the ellipse, which is why it has a fixed hit/miss ratio, compared to the previous method of using orthogonal X,Y bounds.

The question is how affordable is the calculation of the bounding box.

WIth the parallelogram, I the extraction of a row of pixels is quite straight forward. floating point start point, which is offset by a fixed amount form one row to the next row. and it has a fixed floating point length, the result mapped to integers for the access to the data.

Relative straight forward extention of the incremental code used for the quadratic distance formula (no sqrt is performed for that).

For a bounding box aligned with the major and minor axis, you actually have to work out the union of two parallelograms. So instead of on set of values (start,increment,length), you need the union of two sets, one for the major axis bounds and one for the minor axis.

Of course you can clip the Y axis directly by the orthogonal bounds of the ellipse.

So to combine that with the parallelogram, you get a union of three parallelogram bounds when implementing.

You could also add the X bounds to that union too, seeing you are doing unions.

So for each row, you want the maximum of 4 possible start points, and minimum of 4 possible end points.
With unions you no longer have a fixed length!

Now I could be wrong, but its seems to me, that it is a lot of work, for very little reward. Especially when an orthogonally aligned ellipse (simple resize) generally results in the all three bounding boxes aligning anyway!

Now pixel extraction in IM (and other images) can be complex and Virtual pixels become involved. You can't just reference the image data directly in that case.

As such when Virtual-Pixels become involved, reducing the length of each row of pixels may have a major benefit. But it will have no benefit if all the pixels are real, and as such you can reference the image data directly (IM allows both in its pixel cache processing! Or at least did at one point.)

So how beneficial this is open for debate, a test implementation may be useful as a comparison.

However as IM pixel cache for IMv7 is in alpha level development, now is probably not a good time for testing it.

[NicolasRobidoux]

Anthony:

Thank you for the clear and detailed reply.

I get your point. And I agree that using the intersection of the bounding box and of the parallelogram is likely to be a low bang for the buck "improvement."

[NicolasRobidoux]

However, the computation of the bounding box is extremely cheap:

http://git.gnome.org/browse/gegl/tree/g ... 6943#n2220