Pileus Git - ~andy/gtk/blob - gdk-pixbuf/pixops/README

   1 The code in this directory implements optimized, filtered scaling
   2 for pixmap data.
   3
   4 This code is copyright Red Hat, Inc, 2000 and licensed under the terms
   5 of the GNU Lesser General Public License (LGPL).
   6
   7 (If you want to use it in a project where that license is not
   8 appropriate, please contact me, and most likely something can be
   9 worked out.)
  10
  11 Owen Taylor <otaylor@redhat.com>
  12
  13 PRINCIPLES
  14 ==========
  15
  16 The general principle of this code is that it first computes a filter
  17 matrix for the given filtering mode, and then calls a general driver
  18 routine, passing in functions to composite pixels and lines.
  19
  20 (The pixel functions are used for handling edge cases, and the line
  21 functions are simply used for the middle parts of the image.)
  22
  23 The system is designed so that the line functions can be simple,
  24 don't have to worry about special cases, can be selected to
  25 be specific to the particular formats involved. This allows them
  26 to be hyper-optimized. Since most of the compution time is
  27 spent in these functions, this results in an overall fast design.
  28
  29 MMX assembly code for Intel (and compatible) processors is included
  30 for a number of the most common special cases:
  31
  32  scaling from RGB to RGB
  33  compositing from RGBA to RGBx
  34  compositing against a color from RGBA and storing in a RGBx buffer
  35
  36 Alpha compositing 8 bit RGBAa onto RGB is defined in terms of
  37 rounding the exact result (real values in [0,1]):
  38
  39  cc = ca * aa + (1 - aa) * Cb
  40
  41  Cc = ROUND [255. * (Ca/255. * Aa/255. + (1 - Aa/255.) * Cb/255.)]
  42
  43 ROUND(i / 255.) can be computed exactly for i in [0,255*255] as:
  44
  45  t = i + 0x80; result = (t + (t >> 8)) >> 8;  [ call this as To8(i) ]
  46
  47 So,
  48
  49  t = Ca * Aa + (255 - Aa) * Cb + 0x80;
  50  Cc = (t + (t >> 8)) >> 8;
  51
  52 Alpha compositing 8 bit RaGaBaAa onto RbGbBbAa is a little harder, for
  53 non-premultiplied alpha. The premultiplied result is simple:
  54
  55  ac = aa + (1 - aa) * ab
  56  cc = ca + (1 - aa) * cb
  57
  58 Which can be computed in integers terms as:
  59
  60  Cc = Ca + To8 ((255 - Aa) * Cb)
  61  Ac = Aa + To8 ((255 - Aa) * Ab)
  62
  63 For non-premultiplied alpha, we need divide the color components by
  64 the alpha:
  65
  66        +- (ca * aa + (1 - aa) * ab * cb)) / ac; aa != 0
  67   cc = |
  68        +- cb; aa == 0
  69
  70 To calculate this as in integer, we note the alternate form:
  71
  72  cc = cb + aa * (ca - cb) / ac
  73
  74 [ 'cc = ca + (ac - aa) * (cb - ca) / ac' can also be useful numerically,
  75   but isn't important here ]
  76
  77 We can express this as integers as:
  78
  79  Ac_tmp = Aa * 255 + (255 - Aa) * Ab;
  80
  81       +- Cb + (255 * Aa * (Ca - Cb) + Ac_tmp / 2) / Ac_tmp ; Ca > Cb
  82  Cc = |
  83       +- Cb - (255 * Aa * (Cb - Ca) + Ac_tmp / 2) / Ac_tmp ; ca <= Cb
  84
  85 Or, playing bit tricks to avoid the conditional
  86
  87  Cc = Cb + (255 * Aa * (Ca - Cb) + (((Ca - Cb) >> 8) ^ (Ac_tmp / 2)) ) / Ac_tmp
  88
  89 TODO
  90 ====
  91
  92 * ART_FILTER_HYPER is not correctly implemented. It is currently
  93   implemented as a filter that is derived by doing linear interpolation
  94   on the source image and then averaging that with a box filter.
  95
  96   It should be defined as followed (see art_filterlevel.h)
  97
  98    "HYPER is the highest quality reconstruction function. It is derived
  99     from the hyperbolic filters in Wolberg's "Digital Image Warping,"
 100     and is formally defined as the hyperbolic-filter sampling the ideal
 101     hyperbolic-filter interpolated image (the filter is designed to be
 102     idempotent for 1:1 pixel mapping). It is the slowest and highest
 103     quality."
 104
 105   The current HYPER is probably as slow, but lower quality. Also, there
 106   are some subtle errors in the calculation current HYPER that show up as dark
 107   stripes if you scale a constant-color image.
 108
 109 * There are some roundoff errors in the compositing routines.
 110   the _nearest() variants do it right, most of the other code
 111   is wrong to some degree or another.
 112
 113   For instance, in composite_line_22_4a4(), we have:
 114
 115     dest[0] = ((0xff0000 - a) * dest[0] + r) >> 24;
 116
 117    if a is 0 (implies r == 0), then we have:
 118
 119     (0xff0000 * dest[0]) >> 24
 120
 121    which gives results which are 1 to low:
 122
 123        255 => 254,   1 => 0.
 124
 125    So, this should be something like:
 126
 127      ((0xff0000 - a) * dest[0] + r + 0xffffff) >> 24;
 128
 129    (Not checked, caveat emptor)
 130
 131    An alternatve formulation of this as:
 132
 133      dest[0] + (r - a * dest[0] + 0xffffff) >> 24
 134
 135    may be better numerically, but would need consideration for overflow.
 136
 137 * The generic functions could be sped up considerably by
 138   switching around conditionals and inner loops in various
 139   places.
 140
 141 * Right now, in several of the most common cases, there are
 142   optimized mmx routines, but no optimized C routines.
 143
 144   For instance, there is a
 145
 146     pixops_composite_line_22_4a4_mmx()
 147
 148   But no
 149
 150     pixops_composite_line_22_4a4()
 151
 152   Also, it may be desirable to include a few more special cases - in particular:
 153
 154     pixops_composite_line_22_4a3()
 155
 156   May be desirable.
 157
 158 * Scaling down images by large scale factors is _slow_ since huge filter
 159   matrixes are computed. (e.g., to scale down by a factor of 100, we compute
 160   101x101 filter matrixes. At some point, it would be more efficent to
 161   switch over to subsampling when scaling down - one should never need a filter
 162   matrix bigger than 16x16.
 163