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