lib/boundingbox.c

   1 /* Dia -- an diagram creation/manipulation program
   2  * Support for computing bounding boxes
   3  * Copyright (C) 2001 Cyrille Chepelov
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18  */
  19
  20 /** \file boundingbox.c This code is nothing but a fancy pile of FPU crap. */
  21
  22 #include <config.h>
  23 #include <glib.h>
  24 #include <math.h>
  25 #include "geometry.h"
  26 #include "boundingbox.h"
  27
  28 /**
  29  * @param p
  30  * @param A
  31  * @param B
  32  * @param C
  33  * @param D
  34  * @bug I don't know what this does.
  35  */
  36 static void
  37 bernstein_develop(const real p[4], real *A, real *B, real *C, real *D)
  38 {
  39   *A = -p[0]+3*p[1]-3*p[2]+p[3];
  40   *B = 3*p[0]-6*p[1]+3*p[2];
  41   *C = 3*p[1]-3*p[0];
  42   *D = p[0];
  43   /* if Q(u)=Sum(i=0..3)piBi(u) (Bi(u) being the Bernstein stuff),
  44      then Q(u)=Au^3+Bu^2+Cu+p[0]. */
  45 }
  46
  47 /** ?
  48  * @param p
  49  * @param u
  50  * @returns
  51  * @bug I don't know what this does.
  52  */
  53 static real
  54 bezier_eval(const real p[4], real u)
  55 {
  56   real A,B,C,D;
  57   bernstein_develop(p,&A,&B,&C,&D);
  58   return A*u*u*u+B*u*u+C*u+D;
  59 }
  60
  61 /** ?
  62  * @param p
  63  * @param u
  64  * @return
  65  * @bug I don't know what this does.
  66  */
  67 static real
  68 bezier_eval_tangent(const real p[4], real u)
  69 {
  70   real A,B,C,D;
  71   bernstein_develop(p,&A,&B,&C,&D);
  72   return 3*A*u*u+2*B*u+C;
  73 }
  74
  75 /** ?
  76  * @param p
  77  * @param u
  78  * @return
  79  * @bug I don't know what this does.
  80  */
  81 static int
  82 bicubicbezier_extrema(const real p[4],real u[2])
  83 {
  84   real A,B,C,D,delta;
  85
  86   bernstein_develop(p,&A,&B,&C,&D);
  87   delta = 4*B*B - 12*A*C;
  88
  89   u[0] = u[1] = 0.0;
  90   if (delta<0) return 0;
  91
  92   u[0] = (-2*B + sqrt(delta)) / (6*A);
  93   if (delta==0) return 1;
  94   u[1] = (-2*B - sqrt(delta)) / (6*A);
  95   return 2;
  96 }
  97
  98 /** Add to a bounding box the area covered by a standard arrow.
  99  * @param rect The bounding box to adjust
 100  * @param vertex The end point of the arrow.
 101  * @param normed_dir The normalized direction of the arrow (i.e. 1 cm in the
 102  * direction the arrow points from.
 103  * @param extra_long ???
 104  * @param extra_trans ???
 105  * @bug I don't know what the last two arguments do.
 106  */
 107 static void
 108 add_arrow_rectangle(Rectangle *rect,
 109                     const Point *vertex,
 110                     const Point *normed_dir,
 111                     real extra_long,real extra_trans)
 112 {
 113   Point vl,vt,pt;
 114   vl = *normed_dir;
 115
 116   point_get_perp(&vt,&vl);
 117   point_copy_add_scaled(&pt,vertex,&vl,extra_long);
 118   point_add_scaled(&pt,&vt,extra_trans);
 119   rectangle_add_point(rect,&pt);
 120   point_add_scaled(&pt,&vt,-2.0 * extra_trans);
 121   rectangle_add_point(rect,&pt);
 122   point_add_scaled(&pt,&vl,-2.0 * extra_long);
 123   rectangle_add_point(rect,&pt);
 124   point_add_scaled(&pt,&vt,2.0 * extra_trans);
 125   rectangle_add_point(rect,&pt);
 126 }
 127
 128 /** Calculate the boundingbox for a 2D bezier curve segment.
 129  * @param p0
 130  * @param p1
 131  * @param p2
 132  * @param p3
 133  * @param extra
 134  * @param rect The rectangle that the segment fits inside.
 135  * @bug I don't know exactly what the other parameters are.
 136  */
 137 void
 138 bicubicbezier2D_bbox(const Point *p0,const Point *p1,
 139                      const Point *p2,const Point *p3,
 140                      const PolyBBExtras *extra,
 141                      Rectangle *rect)
 142 {
 143   real x[4],y[4];
 144   Point vl,vt,p,tt;
 145   real *xy;
 146   int i,extr;
 147   real u[2];
 148
 149   rect->left = rect->right = p0->x;
 150   rect->top = rect->bottom = p0->y;
 151
 152   rectangle_add_point(rect,p3);
 153   /* start point */
 154   point_copy_add_scaled(&vl,p0,p1,-1);
 155   point_normalize(&vl);
 156   add_arrow_rectangle(rect,p0,&vl,extra->start_long,MAX(extra->start_trans,
 157                                                          extra->middle_trans));
 158
 159   /* end point */
 160   point_copy_add_scaled(&vl,p3,p2,-1);
 161   point_normalize(&vl);
 162   add_arrow_rectangle(rect,p3,&vl,extra->end_long,MAX(extra->end_trans,
 163                                                       extra->middle_trans));
 164
 165   /* middle part */
 166   x[0] = p0->x; x[1] = p1->x; x[2] = p2->x; x[3] = p3->x;
 167   y[0] = p0->y; y[1] = p1->y; y[2] = p2->y; y[3] = p3->y;
 168
 169   for (xy = x; xy ; xy=(xy==x?y:NULL) ) { /* sorry */
 170     extr = bicubicbezier_extrema(xy,u);
 171     for (i=0;i<extr;i++) {
 172       if ((u[i]<0) || (u[i]>1)) continue;
 173       p.x = bezier_eval(x,u[i]);
 174       vl.x = bezier_eval_tangent(x,u[i]);
 175       p.y = bezier_eval(y,u[i]);
 176       vl.y = bezier_eval_tangent(y,u[i]);
 177       point_normalize(&vl);
 178       point_get_perp(&vt,&vl);
 179
 180       point_copy_add_scaled(&tt,&p,&vt,extra->middle_trans);
 181       rectangle_add_point(rect,&tt);
 182       point_copy_add_scaled(&tt,&p,&vt,-extra->middle_trans);
 183       rectangle_add_point(rect,&tt);
 184     }
 185   }
 186 }
 187
 188 /** Calculate the bounding box for a simple line.
 189  * @param p1 One end of the line.
 190  * @param p2 The other end of the line.
 191  * @param extra Extra information
 192  * @param rect The box that the line and extra stuff fits inside.
 193  */
 194 void
 195 line_bbox(const Point *p1, const Point *p2,
 196           const LineBBExtras *extra,
 197           Rectangle *rect)
 198 {
 199   Point vl;
 200
 201   rect->left = rect->right = p1->x;
 202   rect->top = rect->bottom = p1->y;
 203
 204   rectangle_add_point(rect,p2); /* as a safety */
 205
 206   point_copy_add_scaled(&vl,p1,p2,-1);
 207   point_normalize(&vl);
 208   add_arrow_rectangle(rect,p1,&vl,extra->start_long,extra->start_trans);
 209   point_scale(&vl,-1);
 210   add_arrow_rectangle(rect,p2,&vl,extra->end_long,extra->end_trans);
 211 }
 212
 213 /** Calculate the bounding box of an ellipse.
 214  * @param centre The center point of the ellipse.
 215  * @param width The width of the ellipse.
 216  * @param height The height of the ellipse.
 217  * @param extra Extra information required.
 218  * @param rect The bounding box that the ellipse fits inside.
 219  * @bug describe what the extra information is.
 220  */
 221 void
 222 ellipse_bbox(const Point *centre, real width, real height,
 223              const ElementBBExtras *extra,
 224              Rectangle *rect)
 225 {
 226   Rectangle rin;
 227   rin.left = centre->x - width/2;
 228   rin.right = centre->x + width/2;
 229   rin.top = centre->y - height/2;
 230   rin.bottom = centre->y + height/2;
 231
 232   rectangle_bbox(&rin,extra,rect);
 233 }
 234
 235 /**  Allocate some scratch space to hold a big enough Bezier.
 236  * That space is not guaranteed to be preserved upon the next allocation
 237  * (in fact it's guaranteed it's not).
 238  * @param numpoints How many points of bezier to allocate space for.
 239  * @returns Newly allocated array of points.
 240  */
 241 static BezPoint *
 242 alloc_polybezier_space(int numpoints)
 243 {
 244   static int alloc_np = 0;
 245   static BezPoint *alloced = NULL;
 246
 247   if (alloc_np < numpoints) {
 248     g_free(alloced);
 249     alloc_np = numpoints;
 250     alloced = g_new0(BezPoint,numpoints);
 251   }
 252   return alloced;
 253 }
 254
 255 /** Free the scratch space allocated above.
 256  * @param points Previously allocated list of points.
 257  * @note Doesn't actually free it, as alloc_polybezier_space does that.
 258  * @bug Should explain the strange freeing model, or fix it.
 259  */
 260 static void
 261 free_polybezier_space(BezPoint *points)
 262 { /* dummy */ }
 263
 264 /** Calculate the boundingbox for a polyline.
 265  * @param pts Array of points.
 266  * @param numpoints Number of elements in `pts'.
 267  * @param extra Extra space information
 268  * @param closed Whether the polyline is closed or not.
 269  * @param rect Return value: The bounding box that includes the points and
 270  * extra spacing.
 271  * @bug Surely doesn't need to use bezier code, but remember extra stuff.
 272  */
 273 void
 274 polyline_bbox(const Point *pts, int numpoints,
 275               const PolyBBExtras *extra, gboolean closed,
 276               Rectangle *rect)
 277 {
 278   /* It's much easier to re-use the Bezier code... */
 279   int i;
 280   BezPoint *bpts = alloc_polybezier_space(numpoints + 1);
 281
 282   bpts[0].type = BEZ_MOVE_TO;
 283   bpts[0].p1 = pts[0];
 284
 285   for (i=1;i<numpoints;i++) {
 286     bpts[i].type = BEZ_LINE_TO;
 287     bpts[i].p1 = pts[i];
 288   }
 289   /* This one will be used only when closed==TRUE... */
 290   bpts[numpoints].type = BEZ_LINE_TO;
 291   bpts[numpoints].p1 = pts[0];
 292
 293   polybezier_bbox(bpts,numpoints + (closed?1:0),extra,closed,rect);
 294   free_polybezier_space(bpts);
 295 }
 296
 297 /** Calculate a bounding box for a set of bezier points.
 298  * @param pts The bezier points
 299  * @param numpoints The number of elements in `pts'
 300  * @param extra Extra spacing information.
 301  * @param closed True if the bezier points form a closed line.
 302  * @param rect Return value: The enclosing rectangle will be stored here.
 303  * @bug This function is way too long (214 lines) and should be split.
 304  */
 305 void
 306 polybezier_bbox(const BezPoint *pts, int numpoints,
 307                 const PolyBBExtras *extra, gboolean closed,
 308                 Rectangle *rect)
 309 {
 310   Point vx,vp,vn,vsc;
 311   int i,prev,next;
 312   Rectangle rt;
 313   PolyBBExtras bextra,start_bextra,end_bextra;
 314   LineBBExtras lextra,start_lextra,end_lextra,full_lextra;
 315   gboolean start,end;
 316
 317   g_assert(pts[0].type == BEZ_MOVE_TO);
 318
 319   rect->left = rect->right = pts[0].p1.x;
 320   rect->top = rect->bottom = pts[0].p1.y;
 321
 322   /* First, we build derived BBExtras structures, so we have something to feed
 323      the primitives. */
 324   if (!closed) {
 325     start_lextra.start_long = extra->start_long;
 326     start_lextra.start_trans = MAX(extra->start_trans,extra->middle_trans);
 327     start_lextra.end_long = 0;
 328     start_lextra.end_trans = extra->middle_trans;
 329
 330     end_lextra.start_long = 0;
 331     end_lextra.start_trans = extra->middle_trans;
 332     end_lextra.end_long = extra->end_long;
 333     end_lextra.end_trans = MAX(extra->end_trans,extra->middle_trans);
 334   }
 335
 336   full_lextra.start_long = extra->start_long;
 337   full_lextra.start_trans = MAX(extra->start_trans,extra->middle_trans);
 338   full_lextra.end_long = extra->end_long;
 339   full_lextra.end_trans = MAX(extra->end_trans,extra->middle_trans);
 340
 341   if (!closed) {
 342     lextra.start_long = 0;
 343     lextra.start_trans = extra->middle_trans;
 344     lextra.end_long = 0;
 345     lextra.end_trans = extra->middle_trans;
 346
 347     start_bextra.start_long = extra->start_long;
 348     start_bextra.start_trans = extra->start_trans;
 349     start_bextra.middle_trans = extra->middle_trans;
 350     start_bextra.end_long = 0;
 351     start_bextra.end_trans = extra->middle_trans;
 352
 353     end_bextra.start_long = 0;
 354     end_bextra.start_trans = extra->middle_trans;
 355     end_bextra.middle_trans = extra->middle_trans;
 356     end_bextra.end_long = extra->end_long;
 357     end_bextra.end_trans = extra->end_trans;
 358   }
 359
 360   bextra.start_long = 0;
 361   bextra.start_trans = extra->middle_trans;
 362   bextra.middle_trans = extra->middle_trans;
 363   bextra.end_long = 0;
 364   bextra.end_trans = extra->middle_trans;
 365
 366
 367   for (i=1;i<numpoints;i++) {
 368     next = (i+1) % numpoints;
 369     prev = (i-1) % numpoints;
 370     if (closed && (next == 0)) next=1;
 371     if (closed && (prev == 0)) prev=numpoints-1;
 372
 373     /* We have now:
 374        i = index of current vertex.
 375        prev,next: index of previous/next vertices (of the control polygon)
 376
 377        We want:
 378         vp, vx, vn: the previous, current and next vertices;
 379         start, end: TRUE if we're at an end of poly (then, vp and/or vn are not
 380         valid, respectively).
 381
 382        Some values *will* be recomputed a few times across iterations (but stored in
 383        different boxes). Either gprof says it's a real problem, or gcc finally gets
 384        a clue.
 385     */
 386
 387     if (pts[i].type == BEZ_MOVE_TO) {
 388       continue;
 389     }
 390
 391     switch(pts[i].type) {
 392     case BEZ_MOVE_TO:
 393       g_assert_not_reached();
 394       break;
 395     case BEZ_LINE_TO:
 396       point_copy(&vx,&pts[i].p1);
 397       switch(pts[prev].type) {
 398       case BEZ_MOVE_TO:
 399       case BEZ_LINE_TO:
 400         point_copy(&vsc,&pts[prev].p1);
 401         point_copy(&vp,&pts[prev].p1);
 402         break;
 403       case BEZ_CURVE_TO:
 404         point_copy(&vsc,&pts[prev].p3);
 405         point_copy(&vp,&pts[prev].p3);
 406         break;
 407       }
 408       break;
 409     case BEZ_CURVE_TO:
 410       point_copy(&vx,&pts[i].p3);
 411       point_copy(&vp,&pts[i].p2);
 412       switch(pts[prev].type) {
 413       case BEZ_MOVE_TO:
 414       case BEZ_LINE_TO:
 415         point_copy(&vsc,&pts[prev].p1);
 416         break;
 417       case BEZ_CURVE_TO:
 418         point_copy(&vsc,&pts[prev].p3);
 419         break;
 420       } /* vsc is the start of the curve. */
 421
 422       break;
 423     }
 424     start = (pts[prev].type == BEZ_MOVE_TO);
 425     end = (pts[next].type == BEZ_MOVE_TO);
 426     point_copy(&vn,&pts[next].p1); /* whichever type pts[next] is. */
 427
 428     /* Now, we know about a few vertices around the one we're dealing with.
 429        Depending on the shape of the (previous,current) segment, and whether
 430        it's a middle or end segment, we'll be doing different stuff. */
 431     if (closed) {
 432       if (pts[i].type == BEZ_LINE_TO) {
 433         line_bbox(&vsc,&vx,&full_lextra,&rt);
 434       } else {
 435         bicubicbezier2D_bbox(&vsc,
 436                              &pts[i].p1,&pts[i].p2,&pts[i].p3,
 437                              &bextra,
 438                              &rt);
 439       }
 440     } else if (start) {
 441       if (pts[i].type == BEZ_LINE_TO) {
 442         if (end) {
 443           line_bbox(&vsc,&vx,&full_lextra,&rt);
 444         } else {
 445           line_bbox(&vsc,&vx,&start_lextra,&rt);
 446         }
 447       } else { /* BEZ_MOVE_TO */
 448         if (end) {
 449           bicubicbezier2D_bbox(&vsc,
 450                                &pts[i].p1,&pts[i].p2,&pts[i].p3,
 451                                extra,
 452                                &rt);
 453         } else {
 454           bicubicbezier2D_bbox(&vsc,
 455                                &pts[i].p1,&pts[i].p2,&pts[i].p3,
 456                                &start_bextra,
 457                                &rt);
 458         }
 459       }
 460     } else if (end) { /* end but not start. Not closed anyway. */
 461       if (pts[i].type == BEZ_LINE_TO) {
 462         line_bbox(&vsc,&vx,&end_lextra,&rt);
 463       } else {
 464         bicubicbezier2D_bbox(&vsc,
 465                              &pts[i].p1,&pts[i].p2,&pts[i].p3,
 466                              &end_bextra,
 467                              &rt);
 468       }
 469     } else { /* normal case : middle segment (not closed shape). */
 470       if (pts[i].type == BEZ_LINE_TO) {
 471         line_bbox(&vsc,&vx,&lextra,&rt);
 472       } else {
 473         bicubicbezier2D_bbox(&vsc,
 474                              &pts[i].p1,&pts[i].p2,&pts[i].p3,
 475                              &bextra,
 476                              &rt);
 477       }
 478     }
 479     rectangle_union(rect,&rt);
 480
 481     /* The following code enlarges a little the bounding box (if necessary) to
 482        account with the "pointy corners" X (and PS) add when LINEJOIN_MITER mode is
 483        in force. */
 484
 485     if ((!start) && (!end)) { /* We have a non-extremity vertex. */
 486       Point vpx,vxn;
 487       real co,alpha;
 488
 489       point_copy_add_scaled(&vpx,&vx,&vp,-1);
 490       point_normalize(&vpx);
 491       point_copy_add_scaled(&vxn,&vn,&vx,-1);
 492       point_normalize(&vxn);
 493
 494       co = point_dot(&vpx,&vxn);
 495       alpha = acos(-co);
 496       if ((co > -0.9816) && (finite(alpha))) { /* 0.9816 = cos(11deg) */
 497         /* we have a pointy join. */
 498         real overshoot = extra->middle_trans / sin(alpha/2.0);
 499         Point vovs,pto;
 500
 501         point_copy_add_scaled(&vovs,&vpx,&vxn,-1);
 502         point_normalize(&vovs);
 503         point_copy_add_scaled(&pto,&vx,&vovs,overshoot);
 504
 505         rectangle_add_point(rect,&pto);
 506       } else {
 507         /* we don't have a pointy join. */
 508         Point vpxt,vxnt,tmp;
 509
 510         point_get_perp(&vpxt,&vpx);
 511         point_get_perp(&vxnt,&vxn);
 512
 513         point_copy_add_scaled(&tmp,&vx,&vpxt,1);
 514         rectangle_add_point(rect,&tmp);
 515         point_copy_add_scaled(&tmp,&vx,&vpxt,-1);
 516         rectangle_add_point(rect,&tmp);
 517         point_copy_add_scaled(&tmp,&vx,&vxnt,1);
 518         rectangle_add_point(rect,&tmp);
 519         point_copy_add_scaled(&tmp,&vx,&vxnt,-1);
 520         rectangle_add_point(rect,&tmp);
 521       }
 522     }
 523   }
 524 }
 525
 526 /** Figure out a bounding box for a rectangle (fairly simple:)
 527  * @param rin A rectangle to find bbox for.
 528  * @param extra Extra information required to find bbox.
 529  * @param rout Return value: The enclosing bounding box.
 530  * @bug Describe extra info better.
 531  */
 532 void
 533 rectangle_bbox(const Rectangle *rin,
 534                const ElementBBExtras *extra,
 535                Rectangle *rout)
 536 {
 537   rout->left = rin->left - extra->border_trans;
 538   rout->top = rin->top - extra->border_trans;
 539   rout->right = rin->right + extra->border_trans;
 540   rout->bottom = rin->bottom + extra->border_trans;
 541 }
 542
 543
 544 /* TODO: text_bbox ? */
 545
 546