src/dialogs/unclump.cpp

   1 #define __UNCLUMP_C__
   2
   3 /*
   4  * Unclumping objects
   5  *
   6  * Authors:
   7  *   bulia byak
   8  *
   9  * Copyright (C) 2005 Authors
  10  * Released under GNU GPL
  11  */
  12
  13
  14 #include <map>
  15 #include "libnr/nr-matrix-ops.h"
  16 #include "sp-item.h"
  17
  18
  19 // Taking bbox of an item is an expensive operation, and we need to do it many times, so here we
  20 // cache the centers, widths, and heights of items
  21
  22 //FIXME: make a class with these cashes as members instead of globals
  23 std::map<const gchar *, NR::Point> c_cache;
  24 std::map<const gchar *, NR::Point> wh_cache;
  25
  26 /**
  27 Center of bbox of item
  28 */
  29 NR::Point
  30 unclump_center (SPItem *item)
  31 {
  32     std::map<const gchar *, NR::Point>::iterator i = c_cache.find(SP_OBJECT_ID(item));
  33     if ( i != c_cache.end() ) {
  34         return i->second;
  35     }
  36
  37     NR::Rect const r = item->invokeBbox(sp_item_i2d_affine(item));
  38     NR::Point const c = r.midpoint();
  39     c_cache[SP_OBJECT_ID(item)] = c;
  40     return c;
  41 }
  42
  43 NR::Point
  44 unclump_wh (SPItem *item)
  45 {
  46     NR::Point wh;
  47     std::map<const gchar *, NR::Point>::iterator i = wh_cache.find(SP_OBJECT_ID(item));
  48     if ( i != wh_cache.end() ) {
  49         wh = i->second;
  50     } else {
  51         NR::Rect const r = item->invokeBbox(sp_item_i2d_affine(item));
  52         wh = r.dimensions();
  53         wh_cache[SP_OBJECT_ID(item)] = wh;
  54     }
  55
  56     return wh;
  57 }
  58
  59 /**
  60 Distance between "edges" of item1 and item2. An item is considered to be an ellipse inscribed into its w/h,
  61 so its radius (distance from center to edge) depends on the w/h and the angle towards the other item.
  62 May be negative if the edge of item1 is between the center and the edge of item2.
  63 */
  64 double
  65 unclump_dist (SPItem *item1, SPItem *item2)
  66 {
  67         NR::Point c1 = unclump_center (item1);
  68         NR::Point c2 = unclump_center (item2);
  69
  70         NR::Point wh1 = unclump_wh (item1);
  71         NR::Point wh2 = unclump_wh (item2);
  72
  73         // angle from each item's center to the other's, unsqueezed by its w/h, normalized to 0..pi/2
  74         double a1 = atan2 ((c2 - c1)[NR::Y], (c2 - c1)[NR::X] * wh1[NR::Y]/wh1[NR::X]);
  75         a1 = fabs (a1);
  76         if (a1 > M_PI/2) a1 = M_PI - a1;
  77
  78         double a2 = atan2 ((c1 - c2)[NR::Y], (c1 - c2)[NR::X] * wh2[NR::Y]/wh2[NR::X]);
  79         a2 = fabs (a2);
  80         if (a2 > M_PI/2) a2 = M_PI - a2;
  81
  82         // get the radius of each item for the given angle
  83         double r1 = 0.5 * (wh1[NR::X] + (wh1[NR::Y] - wh1[NR::X]) * (a1/(M_PI/2)));
  84         double r2 = 0.5 * (wh2[NR::X] + (wh2[NR::Y] - wh2[NR::X]) * (a2/(M_PI/2)));
  85
  86         // dist between centers minus angle-adjusted radii
  87         double dist_r =  (NR::L2 (c2 - c1) - r1 - r2);
  88
  89         double stretch1 = wh1[NR::Y]/wh1[NR::X];
  90         double stretch2 = wh2[NR::Y]/wh2[NR::X];
  91
  92         if ((stretch1 > 1.5 || stretch1 < 0.66) && (stretch2 > 1.5 || stretch2 < 0.66)) {
  93
  94                 std::vector<double> dists;
  95                 dists.push_back (dist_r);
  96
  97                 // If both objects are not circle-like, find dists between four corners
  98                 std::vector<NR::Point> c1_points(2);
  99                 {
 100                         double y_closest;
 101                         if (c2[NR::Y] > c1[NR::Y] + wh1[NR::Y]/2) {
 102                                 y_closest = c1[NR::Y] + wh1[NR::Y]/2;
 103                         } else if (c2[NR::Y] < c1[NR::Y] - wh1[NR::Y]/2) {
 104                                 y_closest = c1[NR::Y] - wh1[NR::Y]/2;
 105                         } else {
 106                                 y_closest = c2[NR::Y];
 107                         }
 108                         c1_points[0] = NR::Point (c1[NR::X], y_closest);
 109                         double x_closest;
 110                         if (c2[NR::X] > c1[NR::X] + wh1[NR::X]/2) {
 111                                 x_closest = c1[NR::X] + wh1[NR::X]/2;
 112                         } else if (c2[NR::X] < c1[NR::X] - wh1[NR::X]/2) {
 113                                 x_closest = c1[NR::X] - wh1[NR::X]/2;
 114                         } else {
 115                                 x_closest = c2[NR::X];
 116                         }
 117                         c1_points[1] = NR::Point (x_closest, c1[NR::Y]);
 118                 }
 119
 120
 121                 std::vector<NR::Point> c2_points(2);
 122                 {
 123                         double y_closest;
 124                         if (c1[NR::Y] > c2[NR::Y] + wh2[NR::Y]/2) {
 125                                 y_closest = c2[NR::Y] + wh2[NR::Y]/2;
 126                         } else if (c1[NR::Y] < c2[NR::Y] - wh2[NR::Y]/2) {
 127                                 y_closest = c2[NR::Y] - wh2[NR::Y]/2;
 128                         } else {
 129                                 y_closest = c1[NR::Y];
 130                         }
 131                         c2_points[0] = NR::Point (c2[NR::X], y_closest);
 132                         double x_closest;
 133                         if (c1[NR::X] > c2[NR::X] + wh2[NR::X]/2) {
 134                                 x_closest = c2[NR::X] + wh2[NR::X]/2;
 135                         } else if (c1[NR::X] < c2[NR::X] - wh2[NR::X]/2) {
 136                                 x_closest = c2[NR::X] - wh2[NR::X]/2;
 137                         } else {
 138                                 x_closest = c1[NR::X];
 139                         }
 140                         c2_points[1] = NR::Point (x_closest, c2[NR::Y]);
 141                 }
 142
 143                 for (int i = 0; i < 2; i ++) {
 144                         for (int j = 0; j < 2; j ++) {
 145                                 dists.push_back (NR::L2 (c1_points[i] - c2_points[j]));
 146                         }
 147                 }
 148
 149                 // return the minimum of all dists
 150                 return *std::min_element(dists.begin(), dists.end());
 151         } else {
 152                 return dist_r;
 153         }
 154 }
 155
 156 /**
 157 Average unclump_dist from item to others
 158 */
 159 double unclump_average (SPItem *item, GSList *others)
 160 {
 161     int n = 0;
 162     double sum = 0;
 163
 164     for (GSList *i = others; i != NULL; i = i->next) {
 165         SPItem *other = SP_ITEM (i->data);
 166
 167         if (other == item)
 168             continue;
 169
 170         n++;
 171         sum += unclump_dist (item, other);
 172     }
 173
 174     if (n != 0)
 175         return sum/n;
 176     else
 177         return 0;
 178 }
 179
 180 /**
 181 Closest to item among others
 182  */
 183 SPItem *unclump_closest (SPItem *item, GSList *others)
 184 {
 185     double min = HUGE_VAL;
 186     SPItem *closest = NULL;
 187
 188     for (GSList *i = others; i != NULL; i = i->next) {
 189         SPItem *other = SP_ITEM (i->data);
 190
 191         if (other == item)
 192             continue;
 193
 194         double dist = unclump_dist (item, other);
 195         if (dist < min && fabs (dist) < 1e6) {
 196             min = dist;
 197             closest = other;
 198         }
 199     }
 200
 201     return closest;
 202 }
 203
 204 /**
 205 Most distant from item among others
 206  */
 207 SPItem *unclump_farest (SPItem *item, GSList *others)
 208 {
 209     double max = -HUGE_VAL;
 210     SPItem *farest = NULL;
 211
 212     for (GSList *i = others; i != NULL; i = i->next) {
 213         SPItem *other = SP_ITEM (i->data);
 214
 215         if (other == item)
 216             continue;
 217
 218         double dist = unclump_dist (item, other);
 219         if (dist > max && fabs (dist) < 1e6) {
 220             max = dist;
 221             farest = other;
 222         }
 223     }
 224
 225     return farest;
 226 }
 227
 228 /**
 229 Removes from the \a rest list those items that are "behind" \a closest as seen from \a item,
 230 i.e. those on the other side of the line through \a closest perpendicular to the direction from \a
 231 item to \a closest. Returns a newly created list which must be freed.
 232  */
 233 GSList *
 234 unclump_remove_behind (SPItem *item, SPItem *closest, GSList *rest)
 235 {
 236     NR::Point it = unclump_center (item);
 237     NR::Point p1 = unclump_center (closest);
 238
 239     // perpendicular through closest to the direction to item:
 240     NR::Point perp = NR::rot90(it - p1);
 241     NR::Point p2 = p1 + perp;
 242
 243     // get the standard Ax + By + C = 0 form for p1-p2:
 244     double A = p1[NR::Y] - p2[NR::Y];
 245     double B = p2[NR::X] - p1[NR::X];
 246     double C = p2[NR::Y] * p1[NR::X] - p1[NR::Y] * p2[NR::X];
 247
 248     // substitute the item into it:
 249     double val_item = A * it[NR::X] + B * it[NR::Y] + C;
 250
 251     GSList *out = NULL;
 252
 253     for (GSList *i = rest; i != NULL; i = i->next) {
 254         SPItem *other = SP_ITEM (i->data);
 255
 256         if (other == item)
 257             continue;
 258
 259         NR::Point o = unclump_center (other);
 260         double val_other = A * o[NR::X] + B * o[NR::Y] + C;
 261
 262         if (val_item * val_other <= 1e-6) {
 263             // different signs, which means item and other are on the different sides of p1-p2 line; skip
 264         } else {
 265             out = g_slist_prepend (out, other);
 266         }
 267     }
 268
 269     return out;
 270 }
 271
 272 /**
 273 Moves \a what away from \a from by \a dist
 274  */
 275 void
 276 unclump_push (SPItem *from, SPItem *what, double dist)
 277 {
 278     NR::Point it = unclump_center (what);
 279     NR::Point p = unclump_center (from);
 280     NR::Point by = dist * NR::unit_vector (- (p - it));
 281
 282     NR::Matrix move = NR::Matrix (NR::translate (by));
 283
 284     std::map<const gchar *, NR::Point>::iterator i = c_cache.find(SP_OBJECT_ID(what));
 285     if ( i != c_cache.end() ) {
 286         i->second *= move;
 287     }
 288
 289     //g_print ("push %s at %g,%g from %g,%g by %g,%g, dist %g\n", SP_OBJECT_ID(what), it[NR::X],it[NR::Y], p[NR::X],p[NR::Y], by[NR::X],by[NR::Y], dist);
 290
 291     sp_item_set_i2d_affine(what, sp_item_i2d_affine(what) * move);
 292     sp_item_write_transform(what, SP_OBJECT_REPR(what), what->transform, NULL);
 293 }
 294
 295 /**
 296 Moves \a what towards \a to by \a dist
 297  */
 298 void
 299 unclump_pull (SPItem *to, SPItem *what, double dist)
 300 {
 301     NR::Point it = unclump_center (what);
 302     NR::Point p = unclump_center (to);
 303     NR::Point by = dist * NR::unit_vector (p - it);
 304
 305     NR::Matrix move = NR::Matrix (NR::translate (by));
 306
 307     std::map<const gchar *, NR::Point>::iterator i = c_cache.find(SP_OBJECT_ID(what));
 308     if ( i != c_cache.end() ) {
 309         i->second *= move;
 310     }
 311
 312     //g_print ("pull %s at %g,%g to %g,%g by %g,%g, dist %g\n", SP_OBJECT_ID(what), it[NR::X],it[NR::Y], p[NR::X],p[NR::Y], by[NR::X],by[NR::Y], dist);
 313
 314     sp_item_set_i2d_affine(what, sp_item_i2d_affine(what) * move);
 315     sp_item_write_transform(what, SP_OBJECT_REPR(what), what->transform, NULL);
 316 }
 317
 318
 319 /**
 320 Unclumps the items in \a items, reducing local unevenness in their distribution. Produces an effect
 321 similar to "engraver dots". The only distribution which is unchanged by unclumping is a hexagonal
 322 grid. May be called repeatedly for stronger effect.
 323  */
 324 void
 325 unclump (GSList *items)
 326 {
 327     c_cache.clear();
 328     wh_cache.clear();
 329
 330     for (GSList *i = items; i != NULL; i = i->next) { //  for each original/clone x:
 331         SPItem *item = SP_ITEM (i->data);
 332
 333         GSList *nei = NULL;
 334
 335         GSList *rest = g_slist_copy (items);
 336         rest = g_slist_remove (rest, item);
 337
 338         while (rest != NULL) {
 339             SPItem *closest = unclump_closest (item, rest);
 340             if (closest) {
 341                 nei = g_slist_prepend (nei, closest);
 342                 rest = g_slist_remove (rest, closest);
 343                 GSList *new_rest = unclump_remove_behind (item, closest, rest);
 344                 g_slist_free (rest);
 345                 rest = new_rest;
 346             } else {
 347                 g_slist_free (rest);
 348                 break;
 349             }
 350         }
 351
 352         if (g_slist_length (nei) >= 2) {
 353             double ave = unclump_average (item, nei);
 354
 355             SPItem *closest = unclump_closest (item, nei);
 356             SPItem *farest = unclump_farest (item, nei);
 357
 358             double dist_closest = unclump_dist (closest, item);
 359             double dist_farest = unclump_dist (farest, item);
 360
 361             //g_print ("NEI %d for item %s    closest %s at %g  farest %s at %g  ave %g\n", g_slist_length(nei), SP_OBJECT_ID(item), SP_OBJECT_ID(closest), dist_closest, SP_OBJECT_ID(farest), dist_farest, ave);
 362
 363             if (fabs (ave) < 1e6 && fabs (dist_closest) < 1e6 && fabs (dist_farest) < 1e6) { // otherwise the items are bogus
 364                 // increase these coefficients to make unclumping more aggressive and less stable
 365                 // the pull coefficient is a bit bigger to counteract the long-term expansion trend
 366                 unclump_push (closest, item, 0.3 * (ave - dist_closest));
 367                 unclump_pull (farest, item, 0.35 * (dist_farest - ave));
 368             }
 369         }
 370     }
 371 }