Created attachment 78925 [details]
A program illustrating the problem

I can confirm this bug. It also seems that misalignment varies in an unpredictable way depending on the scale. The error seems to be almost 20 pixels in the most severe cases and greater the higher the scale factor. Scale 200 produces a very great error.

I've been investigating this bug and I've found that the problem is
caused by pixops_scale_nearest():s use of fixed point math. It
calculates the x_step and y_step using:

    #define SCALE_SHIFT 16
    ...
    int x_step = (1 << SCALE_SHIFT) / scale_x;
    int y_step = (1 << SCALE_SHIFT) / scale_y;

which truncates the value if the scale != 2**n. For example: (1 << 16)
/ 64 = 1024, but (1 << 16) / 65 = 1008.246 which is a non-integer
value which causes the misalignment. Incidentally, the use of fixed
point also causes bug #163090 because the integer value overflows.

There is no perfect way to solve this problem. A fixed point math
algorithm will always suffer these kinds of problems. You could
replace the fixed point with floating point math and get the correct
result, but then you'll get a huge slowdown. On my computer the speed
for nearest scaling to a 500x500 pixbuf decreased from 700 ops/sec to
100/ops sec. The speed for bilinear scaling is 200 ops/sec.

On the other hand, this bug only shows itself when scale > 30, so it
is possible to special case and ue a floating point algorithm better
optimized for that case:

        /* Only for the RGB -> RGB case */
        float x_coll = 0;
        while (x < xstop)
        {
            p = src + (int)x * 3;
            int runs = ceil ((1.0 - x_coll) / x_step);
            for (int n = 0; n < runs; n++)
            {
                dst[0] = p[0];
                dst[1] = p[1];
                dst[2] = p[2];
                dst += 3;
            }
            x += x_step * runs;
            x_coll += x_step * runs;
            x_coll -= 1.0;
        }

The above loop roughly replaces the loop:

      while (x < xstop)                                         \
        {                                                       \
          p = src + (x >> SCALE_SHIFT) * SRC_CHANNELS;          \
          ASSIGN_PIXEL;                                         \
          dest += DEST_CHANNELS;                                \
          x += x_step;                                          \
        }                                                       \

in the INNER_LOOP macro. Using the above float version, with scale 100
and good gcc optimizations, throughput increases from 700 to 950
ops/sec.

So in theory, it should be possible to fix this bug (and also #163090
which also needs floating point) without hurting performance. The
catch is that the code size doubles because you need a special case
loop for scale > 30 scale operations.

I finally decided to code around this bug and wrote the following code:

            // Bug workaround for huge zooms
            if (scale_x >= 30)
                fix_gdk_pixbuf_scale_nn(selfp->image,
                                        img_scaled,
                                        0,0,
                                        copy_w,
                                        copy_h,
                                        offs_x,
                                        offs_y,
                                        scale_x, scale_y);
            else
                gdk_pixbuf_scale(selfp->image,
                                 :

where:


 static void
fix_gdk_pixbuf_scale_nn(const GdkPixbuf *src,
                        GdkPixbuf *dest,
                        int dest_x,
                        int dest_y,
                        int dest_width,
                        int dest_height,
                        double offset_x,
                        double offset_y,
                        double scale_x,
                        double scale_y)
{
    int nch_src = gdk_pixbuf_get_n_channels(src);
    int nch_dest = gdk_pixbuf_get_n_channels(dest);
    int row_idx, col_idx;
    guchar *buf_dest = gdk_pixbuf_get_pixels(dest);
    guchar *buf_src = gdk_pixbuf_get_pixels(src);
    gint dest_row_stride = gdk_pixbuf_get_rowstride(dest);
    gint src_row_stride = gdk_pixbuf_get_rowstride(src);
    gint src_height = gdk_pixbuf_get_height(src);
    gint src_width = gdk_pixbuf_get_width(src);

    // Create a cache of column addresses so we don't have to
    // do floating point calculations for each pixel.
    gint *dest_addr = (gint*)g_new0(gint, dest_width);
    for (col_idx= 0; col_idx<dest_width; col_idx++) {
        gint col_src = (int)((1.0*col_idx - offset_x)/scale_x+0.5);
        if (col_src >= 0 && col_src < src_width) 
            dest_addr[col_idx] = col_src;
        else
            col_src = -1;
    }

    // Loop over destination pixels and pull out the source
    // pixel info. If source is outside of image, I simply
    // set all pixel info to 0. Currently does nearest neighbor
    // only. 
    for (row_idx=0; row_idx<dest_height; row_idx++) {
        guchar *p = buf_dest + dest_row_stride * row_idx;
        gint row_src = (int)((1.0*row_idx - offset_y)/scale_y+0.5);
        guchar *psrc_row = buf_src + row_src * src_row_stride;
        if (row_src < 0 || row_src >= src_height) {
            memset(p, 0, dest_row_stride);
            continue;
        }
        for (col_idx= 0; col_idx<dest_width; col_idx++) {
            gint col_src = dest_addr[col_idx];
            guchar rr=0, gg=0, bb=0, alpha=255;
            if (col_src >= 0) {
                guchar *psrc = psrc_row + col_src * nch_src;
                
                rr = *psrc++;
                gg = *psrc++;
                bb = *psrc++;
                if (nch_src==4)
                    alpha = *psrc++;
            }

            *p++ = rr;
            *p++ = gg;
            *p++ = bb;
            if (nch_dest == 4)
                *p++ = alpha;
        }
    }
    g_free(dest_addr);
}

This solution seem to work perfectly for me including giving no noticible delay when zooming interactively at a full screen.

While thinking about this problem it reminded me about Bresenham's line drawing algorithm, since scaling -- just like line drawing -- means that you have two independent variables that should increase from their respective minima to their respective maxima. A bit of Googling confirmed that I wasn't the first to think of this:

http://www.ddj.com/architect/184405045

I have no idea of how this could be implemented with MMX, but does solve the problem of not having to use any floating point math.

Tend to think that the pixops code should be left alone to die in peace.

-- GitLab Migration Automatic Message --

This bug has been migrated to GNOME's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.gnome.org/GNOME/gdk-pixbuf/issues/10.