After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 389832 - gdk_pixbuf_scale offset wrong for scales != 2**n
gdk_pixbuf_scale offset wrong for scales != 2**n
Status: RESOLVED OBSOLETE
Product: gdk-pixbuf
Classification: Platform
Component: pixops
git master
Other All
: Normal normal
: ---
Assigned To: gdk-pixbuf-maint
gdk-pixbuf-maint
Depends on:
Blocks:
 
 
Reported: 2006-12-26 20:49 UTC by Dov Grobgeld
Modified: 2018-05-22 13:05 UTC
See Also:
GNOME target: ---
GNOME version: ---


Attachments
A program illustrating the problem (3.26 KB, text/plain)
2006-12-26 20:51 UTC, Dov Grobgeld
Details

Description Dov Grobgeld 2006-12-26 20:49:09 UTC
Please describe the problem:
There is a problem in the pixel-offset of images scaled by a large factor. I have only been able to reproduce the problem for scales!=2**n. To illustrate the problem I have created a program that does the following:

1. creates a 256x256 image where each pixel has its red channel corresponding to the column, the green channel to the row, and the blue channel creates a checker pattern.

2. This image is scaled by a factor of 75 (non-power of two) and clipped by the gdk_pixbuf_scale() function to create a 512x512 image that is a zoomed up image of the first image where the left-upper corner of the second image is at position (128,0) of the first image.

3. Both images are written to disk in ppm format under the names org.ppm and simg.ppm respectively.

It is expeced that simg.ppm will be aligned on the checker pattern that exists in org.ppm, but it is offset by approx 9 pixels.


Steps to reproduce:


Actual results:


Expected results:


Does this happen every time?


Other information:
Comment 1 Dov Grobgeld 2006-12-26 20:51:26 UTC
Created attachment 78925 [details]
A program illustrating the problem
Comment 2 Björn Lindqvist 2007-06-17 03:25:01 UTC
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.
Comment 3 Björn Lindqvist 2007-06-17 18:25:08 UTC
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.
Comment 4 Dov Grobgeld 2009-03-10 19:15:45 UTC
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.
Comment 5 Dov Grobgeld 2009-03-12 16:14:51 UTC
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.
Comment 6 Owen Taylor 2009-03-12 16:19:34 UTC
Tend to think that the pixops code should be left alone to die in peace.
Comment 7 GNOME Infrastructure Team 2018-05-22 13:05:03 UTC
-- 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.