← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/gimp/jaunty-security

« back to all changes in this revision

Viewing changes to app/core/gimp-transform-resize.c

  • Committer: Bazaar Package Importer
  • Author(s): Daniel Holbach
  • Date: 2007-05-02 16:33:03 UTC
  • mfrom: (1.1.4 upstream)
  • Revision ID: james.westby@ubuntu.com-20070502163303-bvzhjzbpw8qglc4y
Tags: 2.3.16-1ubuntu1
* Resynchronized with Debian, remaining Ubuntu changes:
  - debian/rules: i18n magic.
* debian/control.in:
  - Maintainer: Ubuntu Core Developers <ubuntu-devel@lists.ubuntu.com>
* debian/patches/02_help-message.patch,
  debian/patches/03_gimp.desktop.in.in.patch,
  debian/patches/10_dont_show_wizard.patch: updated.
* debian/patches/04_composite-signedness.patch,
  debian/patches/05_add-letter-spacing.patch: dropped, used upstream.

Show diffs side-by-side

added added

removed removed

Lines of Context:
app/core/gimp-transform-resize.c
 
1
/* GIMP - The GNU Image Manipulation Program
 
2
 * Copyright (C) 1995-2001 Spencer Kimball, Peter Mattis, and others
 
3
 *
 
4
 * This program is free software; you can redistribute it and/or modify
 
5
 * it under the terms of the GNU General Public License as published by
 
6
 * the Free Software Foundation; either version 2 of the License, or
 
7
 * (at your option) any later version.
 
8
 *
 
9
 * This program is distributed in the hope that it will be useful,
 
10
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
11
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
12
 * GNU General Public License for more details.
 
13
 *
 
14
 * You should have received a copy of the GNU General Public License
 
15
 * along with this program; if not, write to the Free Software
 
16
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 
17
 */
 
18
 
 
19
#include "config.h"
 
20
 
 
21
#include <glib-object.h>
 
22
 
 
23
#include "libgimpmath/gimpmath.h"
 
24
 
 
25
#include "core-types.h"
 
26
 
 
27
#include "gimp-transform-resize.h"
 
28
 
 
29
 
 
30
#if defined (HAVE_FINITE)
 
31
#define FINITE(x) finite(x)
 
32
#elif defined (HAVE_ISFINITE)
 
33
#define FINITE(x) isfinite(x)
 
34
#elif defined (G_OS_WIN32)
 
35
#define FINITE(x) _finite(x)
 
36
#else
 
37
#error "no FINITE() implementation available?!"
 
38
#endif
 
39
 
 
40
#define MIN4(a,b,c,d) MIN(MIN((a),(b)),MIN((c),(d)))
 
41
#define MAX4(a,b,c,d) MAX(MAX((a),(b)),MAX((c),(d)))
 
42
 
 
43
 
 
44
typedef struct
 
45
{
 
46
  gint      x, y;
 
47
} Point;
 
48
 
 
49
typedef struct
 
50
{
 
51
  gint      xmin, xmax;
 
52
  gint      ymin, ymax;
 
53
  gdouble   m, b;  /* y = mx + b */
 
54
  gboolean  top, right;
 
55
} Edge;
 
56
 
 
57
 
 
58
 
 
59
static void  gimp_transform_resize_adjust (gdouble  dx1,
 
60
                                           gdouble  dy1,
 
61
                                           gdouble  dx2,
 
62
                                           gdouble  dy2,
 
63
                                           gdouble  dx3,
 
64
                                           gdouble  dy3,
 
65
                                           gdouble  dx4,
 
66
                                           gdouble  dy4,
 
67
                                           gint    *x1,
 
68
                                           gint    *y1,
 
69
                                           gint    *x2,
 
70
                                           gint    *y2);
 
71
static void  gimp_transform_resize_crop   (gdouble  dx1,
 
72
                                           gdouble  dy1,
 
73
                                           gdouble  dx2,
 
74
                                           gdouble  dy2,
 
75
                                           gdouble  dx3,
 
76
                                           gdouble  dy3,
 
77
                                           gdouble  dx4,
 
78
                                           gdouble  dy4,
 
79
                                           gdouble  aspect,
 
80
                                           gint    *x1,
 
81
                                           gint    *y1,
 
82
                                           gint    *x2,
 
83
                                           gint    *y2);
 
84
 
 
85
 
 
86
/*
 
87
 * This function wants to be passed the inverse transformation matrix!!
 
88
 */
 
89
void
 
90
gimp_transform_resize_boundary (const GimpMatrix3   *inv,
 
91
                                GimpTransformResize  resize,
 
92
                                gint                 u1,
 
93
                                gint                 v1,
 
94
                                gint                 u2,
 
95
                                gint                 v2,
 
96
                                gint                *x1,
 
97
                                gint                *y1,
 
98
                                gint                *x2,
 
99
                                gint                *y2)
 
100
{
 
101
  gdouble dx1, dx2, dx3, dx4;
 
102
  gdouble dy1, dy2, dy3, dy4;
 
103
 
 
104
  g_return_if_fail (inv != NULL);
 
105
 
 
106
  /*  initialize with the original boundary  */
 
107
  *x1 = u1;
 
108
  *y1 = v1;
 
109
  *x2 = u2;
 
110
  *y2 = v2;
 
111
 
 
112
  if (resize == GIMP_TRANSFORM_RESIZE_CLIP)
 
113
    return;
 
114
 
 
115
  gimp_matrix3_transform_point (inv, u1, v1, &dx1, &dy1);
 
116
  gimp_matrix3_transform_point (inv, u2, v1, &dx2, &dy2);
 
117
  gimp_matrix3_transform_point (inv, u1, v2, &dx3, &dy3);
 
118
  gimp_matrix3_transform_point (inv, u2, v2, &dx4, &dy4);
 
119
 
 
120
  /*  check if the transformation matrix is valid at all  */
 
121
  if (! FINITE (dx1) || ! FINITE (dy1) ||
 
122
      ! FINITE (dx2) || ! FINITE (dy2) ||
 
123
      ! FINITE (dx3) || ! FINITE (dy3) ||
 
124
      ! FINITE (dx4) || ! FINITE (dy4))
 
125
    {
 
126
      g_warning ("invalid transform matrix");
 
127
      resize = GIMP_TRANSFORM_RESIZE_CLIP;
 
128
    }
 
129
 
 
130
  switch (resize)
 
131
    {
 
132
    case GIMP_TRANSFORM_RESIZE_ADJUST:
 
133
      gimp_transform_resize_adjust (dx1, dy1, dx2, dy2, dx3, dy3, dx4, dy4,
 
134
                                    x1, y1, x2, y2);
 
135
      break;
 
136
 
 
137
    case GIMP_TRANSFORM_RESIZE_CLIP:
 
138
      /*  we are all done already  */
 
139
      break;
 
140
 
 
141
    case GIMP_TRANSFORM_RESIZE_CROP:
 
142
      gimp_transform_resize_crop (dx1, dy1, dx2, dy2, dx3, dy3, dx4, dy4,
 
143
                                  0.0,
 
144
                                  x1, y1, x2, y2);
 
145
      break;
 
146
 
 
147
    case GIMP_TRANSFORM_RESIZE_CROP_WITH_ASPECT:
 
148
      gimp_transform_resize_crop (dx1, dy1, dx2, dy2, dx3, dy3, dx4, dy4,
 
149
                                  ((gdouble) u2 - u1) / (v2 - v1),
 
150
                                  x1, y1, x2, y2);
 
151
      break;
 
152
    }
 
153
 
 
154
  if (*x1 == *x2)
 
155
    (*x2)++;
 
156
 
 
157
  if (*y1 == *y2)
 
158
    (*y2)++;
 
159
}
 
160
 
 
161
static void
 
162
gimp_transform_resize_adjust (gdouble  dx1,
 
163
                              gdouble  dy1,
 
164
                              gdouble  dx2,
 
165
                              gdouble  dy2,
 
166
                              gdouble  dx3,
 
167
                              gdouble  dy3,
 
168
                              gdouble  dx4,
 
169
                              gdouble  dy4,
 
170
                              gint    *x1,
 
171
                              gint    *y1,
 
172
                              gint    *x2,
 
173
                              gint    *y2)
 
174
{
 
175
  *x1 = (gint) floor (MIN4 (dx1, dx2, dx3, dx4));
 
176
  *y1 = (gint) floor (MIN4 (dy1, dy2, dy3, dy4));
 
177
 
 
178
  *x2 = (gint) ceil (MAX4 (dx1, dx2, dx3, dx4));
 
179
  *y2 = (gint) ceil (MAX4 (dy1, dy2, dy3, dy4));
 
180
}
 
181
 
 
182
static void
 
183
edge_init (Edge        *edge,
 
184
           const Point *p,
 
185
           const Point *q)
 
186
{
 
187
  gdouble den;
 
188
 
 
189
  edge->xmin  = MIN ((p->x), (q->x));
 
190
  edge->xmax  = MAX ((p->x), (q->x));
 
191
 
 
192
  edge->ymin  = MIN ((p->y), (q->y));
 
193
  edge->ymax  = MAX ((p->y), (q->y));
 
194
 
 
195
  edge->top   = p->x > q->x;
 
196
  edge->right = p->y > q->y;
 
197
 
 
198
  den = q->x - p->x;
 
199
 
 
200
  if (den == 0)
 
201
    den = 0.001;
 
202
 
 
203
  edge->m = ((gdouble) q->y - p->y) / den;
 
204
  edge->b = p->y - edge->m * p->x;
 
205
}
 
206
 
 
207
static const Edge *
 
208
find_edge (const Edge *edges,
 
209
           gint        x,
 
210
           gboolean    top)
 
211
{
 
212
  const Edge *emax = edges;
 
213
  const Edge *e = edges;
 
214
  gint        i;
 
215
 
 
216
  for (i = 0; i < 4; i++)
 
217
    {
 
218
      if ((e->xmin == x) && (e->xmax != e->xmin) &&
 
219
          ((e->top && top) || (!e->top && !top)))
 
220
        emax = e;
 
221
 
 
222
      e++;
 
223
    }
 
224
 
 
225
  return emax;
 
226
}
 
227
 
 
228
/* find largest pixel completely inside;
 
229
 * look through all edges for intersection
 
230
 */
 
231
static gint
 
232
intersect_x (const Edge *edges,
 
233
             gint        y)
 
234
{
 
235
  gdouble x0 = 0;
 
236
  gdouble x1 = 0;
 
237
  gint    i;
 
238
 
 
239
  for (i = 0; i < 4; i++)
 
240
    if (edges[i].right && edges[i].ymin <= y && edges[i].ymax >= y)
 
241
      {
 
242
        x0 = (y + 0.5 - edges[i].b) / edges[i].m;
 
243
        x1 = (y - 0.5 - edges[i].b) / edges[i].m;
 
244
      }
 
245
 
 
246
  return (gint) floor (MIN (x0, x1));
 
247
}
 
248
 
 
249
static gint
 
250
intersect_y (const Edge *edge,
 
251
             gint        xi)
 
252
{
 
253
  gdouble yfirst = edge->m * (xi - 0.5) + edge->b;
 
254
  gdouble ylast  = edge->m * (xi + 0.5) + edge->b;
 
255
 
 
256
  return (gint) (edge->top ?
 
257
                 ceil (MAX (yfirst, ylast)) : floor (MIN (yfirst, ylast)));
 
258
}
 
259
 
 
260
static void
 
261
gimp_transform_resize_crop (gdouble  dx1,
 
262
                            gdouble  dy1,
 
263
                            gdouble  dx2,
 
264
                            gdouble  dy2,
 
265
                            gdouble  dx3,
 
266
                            gdouble  dy3,
 
267
                            gdouble  dx4,
 
268
                            gdouble  dy4,
 
269
                            gdouble  aspect,
 
270
                            gint    *x1,
 
271
                            gint    *y1,
 
272
                            gint    *x2,
 
273
                            gint    *y2)
 
274
{
 
275
  Point        points[4];
 
276
  gint         ax, ay;
 
277
  int          min;
 
278
  gint         tx, ty;
 
279
 
 
280
  Edge         edges[4];
 
281
  const Point *a;
 
282
  const Point *b;
 
283
  const Edge  *top;
 
284
  const Edge  *bottom;
 
285
  gint         cxmin, cymin;
 
286
  gint         cxmax, cymax;
 
287
  Point       *xint;
 
288
 
 
289
  gint         ymin, ymax;
 
290
  gint         maxarea = 0;
 
291
  gint         xi;
 
292
  gint         i;
 
293
 
 
294
  /*  fill in the points array  */
 
295
  points[0].x = floor (dx1);
 
296
  points[0].y = floor (dy1);
 
297
  points[1].x = floor (dx2);
 
298
  points[1].y = floor (dy2);
 
299
  points[2].x = floor (dx3);
 
300
  points[2].y = floor (dy3);
 
301
  points[3].x = floor (dx4);
 
302
  points[3].y = floor (dy4);
 
303
 
 
304
  /*  first, translate the vertices into the first quadrant */
 
305
 
 
306
  ax = 0;
 
307
  ay = 0;
 
308
 
 
309
  for (i = 0; i < 4; i++)
 
310
    {
 
311
      if (points[i].x < ax)
 
312
        ax = points[i].x;
 
313
      if (points[i].y < ay)
 
314
        ay = points[i].y;
 
315
    }
 
316
 
 
317
  for (i = 0; i < 4; i++)
 
318
    {
 
319
      points[i].x += (-ax) * 2;
 
320
      points[i].y += (-ay) * 2;
 
321
    }
 
322
 
 
323
  /* find the convex hull using Jarvis's March as the points are passed
 
324
   * in different orders due to gimp_matrix3_transform_point()
 
325
   */
 
326
 
 
327
  min = 0;
 
328
  for (i = 0; i < 4; i++)
 
329
    {
 
330
      if (points[i].y < points[min].y)
 
331
        min = i;
 
332
    }
 
333
 
 
334
  tx = points[0].x;
 
335
  ty = points[0].y;
 
336
 
 
337
  points[0].x = points[min].x;
 
338
  points[0].y = points[min].y;
 
339
 
 
340
  points[min].x = tx;
 
341
  points[min].y = ty;
 
342
 
 
343
  for (i = 1; i < 4; i++)
 
344
    {
 
345
      gdouble theta, theta_m = 2 * G_PI;
 
346
      gdouble theta_v = 0;
 
347
      gint    j;
 
348
 
 
349
      min = 3;
 
350
 
 
351
      for (j = i; j < 4; j++)
 
352
        {
 
353
          gdouble sy = points[j].y - points[i - 1].y;
 
354
          gdouble sx = points[j].x - points[i - 1].x;
 
355
          theta = atan2 (sy, sx);
 
356
 
 
357
          if ((theta < theta_m) &&
 
358
              ((theta > theta_v) || ((theta == theta_v) && (sx > 0))))
 
359
            {
 
360
              theta_m = theta;
 
361
              min = j;
 
362
            }
 
363
        }
 
364
 
 
365
      theta_v = theta_m;
 
366
 
 
367
      tx = points[i].x;
 
368
      ty = points[i].y;
 
369
 
 
370
      points[i].x = points[min].x;
 
371
      points[i].y = points[min].y;
 
372
 
 
373
      points[min].x = tx;
 
374
      points[min].y = ty;
 
375
    }
 
376
 
 
377
  /* reverse the order of points */
 
378
 
 
379
  tx = points[0].x; ty = points[0].y;
 
380
  points[0].x = points[3].x; points[0].y = points[3].y;
 
381
  points[3].x = tx; points[3].y = ty;
 
382
 
 
383
  tx = points[1].x; ty = points[1].y;
 
384
  points[1].x = points[2].x; points[1].y = points[2].y;
 
385
  points[2].x = tx; points[2].y = ty;
 
386
 
 
387
 
 
388
  /* now, find the largest rectangle using the method described in
 
389
   * "Computing the Largest Inscribed Isothetic Rectangle" by
 
390
   * D. Hsu, J. Snoeyink, et al.
 
391
   */
 
392
 
 
393
  /*  first create an array of edges  */
 
394
 
 
395
  cxmin = cxmax = points[3].x;
 
396
  cymin = cymax = points[3].y;
 
397
 
 
398
  for (i = 0, a = points + 3, b = points; i < 4; i++, a = b, b++)
 
399
    {
 
400
      if (G_UNLIKELY (i == 0))
 
401
        {
 
402
          cxmin = cxmax = a->x;
 
403
          cymin = cymax = a->y;
 
404
        }
 
405
      else
 
406
        {
 
407
          if (a->x < cxmin)
 
408
            cxmin = a->x;
 
409
 
 
410
          if (a->x > cxmax)
 
411
              cxmax = a->x;
 
412
 
 
413
          if (a->y < cymin)
 
414
            cymin = a->y;
 
415
 
 
416
          if (a->y > cymax)
 
417
            cymax = a->y;
 
418
        }
 
419
 
 
420
      edge_init (edges + i, a, b);
 
421
    }
 
422
 
 
423
  xint = g_new (Point, cymax);
 
424
 
 
425
  for (i = 0; i < cymax; i++)
 
426
    {
 
427
      xint[i].x = intersect_x (edges, i);
 
428
      xint[i].y = i;
 
429
    }
 
430
 
 
431
  top    = find_edge (edges, cxmin, TRUE);
 
432
  bottom = find_edge (edges, cxmin, FALSE);
 
433
 
 
434
  for (xi = cxmin; xi < cxmax; xi++)
 
435
    {
 
436
      gint ylo, yhi;
 
437
 
 
438
      ymin = intersect_y (top, xi);
 
439
      ymax = intersect_y (bottom, xi);
 
440
 
 
441
      for (ylo = ymax; ylo > ymin; ylo--)
 
442
        {
 
443
          for (yhi = ymin; yhi < ymax; yhi++)
 
444
            {
 
445
              if (yhi > ylo)
 
446
                {
 
447
                  gint xlo, xhi;
 
448
                  gint xright;
 
449
                  gint height, width, fixed_width;
 
450
                  gint area;
 
451
 
 
452
                  xlo = xint[ylo].x;
 
453
                  xhi = xint[yhi].x;
 
454
 
 
455
                  xright = MIN (xlo, xhi);
 
456
 
 
457
                  height = yhi - ylo;
 
458
                  width = xright - xi;
 
459
 
 
460
                  if (aspect != 0)
 
461
                    {
 
462
                      fixed_width = (gint) ceil ((gdouble) height * aspect);
 
463
 
 
464
                      if (fixed_width <= width)
 
465
                        width = fixed_width;
 
466
                      else
 
467
                        width = 0;
 
468
                    }
 
469
 
 
470
                  area = width * height;
 
471
 
 
472
                  if (area > maxarea)
 
473
                    {
 
474
                      maxarea = area;
 
475
 
 
476
                      *x1 = xi;
 
477
                      *y1 = ylo;
 
478
                      *x2 = xi + width;
 
479
                      *y2 = ylo + height;
 
480
                    }
 
481
                }
 
482
            }
 
483
        }
 
484
 
 
485
      if (xi == top->xmax)
 
486
        top = find_edge (edges, xi, TRUE);
 
487
 
 
488
      if (xi == bottom->xmax)
 
489
        bottom = find_edge (edges, xi, FALSE);
 
490
    }
 
491
 
 
492
  g_free (xint);
 
493
 
 
494
  /* translate back the vertices */
 
495
 
 
496
  *x1 = *x1 - ((-ax) * 2);
 
497
  *y1 = *y1 - ((-ay) * 2);
 
498
  *x2 = *x2 - ((-ax) * 2);
 
499
  *y2 = *y2 - ((-ay) * 2);
 
500
}