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 /* 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 static void
  29 bernstein_develop(const real p[4],real *A,real *B,real *C,real *D)
  30 {
  31   *A = -p[0]+3*p[1]-3*p[2]+p[3];
  32   *B = 3*p[0]-6*p[1]+3*p[2];
  33   *C = 3*p[1]-3*p[0];
  34   *D = p[0];
  35   /* if Q(u)=Sum(i=0..3)piBi(u) (Bi(u) being the Bernstein stuff),
  36      then Q(u)=Au^3+Bu^2+Cu+p[0]. */
  37 }
  38
  39 static real
  40 bezier_eval(const real p[4],real u) {
  41   real A,B,C,D;
  42   bernstein_develop(p,&A,&B,&C,&D);
  43   return A*u*u*u+B*u*u+C*u+D;
  44 }
  45
  46 static real
  47 bezier_eval_tangent(const real p[4],real u) {
  48   real A,B,C,D;
  49   bernstein_develop(p,&A,&B,&C,&D);
  50   return 3*A*u*u+2*B*u+C;
  51 }
  52
  53 static int
  54 bicubicbezier_extrema(const real p[4],real u[2])
  55 {
  56   real A,B,C,D,delta;
  57
  58   bernstein_develop(p,&A,&B,&C,&D);
  59   delta = 4*B*B - 12*A*C;
  60
  61   u[0] = u[1] = 0.0;
  62   if (delta<0) return 0;
  63
  64   u[0] = (-2*B + sqrt(delta)) / (6*A);
  65   if (delta==0) return 1;
  66   u[1] = (-2*B - sqrt(delta)) / (6*A);
  67   return 2;
  68 }
  69
  70 static void
  71 add_arrow_rectangle(Rectangle *rect,
  72                     const Point *vertex,
  73                     const Point *normed_dir,
  74                     real extra_long,real extra_trans)
  75 {
  76   Point vl,vt,pt;
  77   vl = *normed_dir;
  78
  79   point_get_perp(&vt,&vl);
  80   point_copy_add_scaled(&pt,vertex,&vl,extra_long);
  81   point_add_scaled(&pt,&vt,extra_trans);
  82   rectangle_add_point(rect,&pt);
  83   point_add_scaled(&pt,&vt,-2.0 * extra_trans);
  84   rectangle_add_point(rect,&pt);
  85   point_add_scaled(&pt,&vl,-2.0 * extra_long);
  86   rectangle_add_point(rect,&pt);
  87   point_add_scaled(&pt,&vt,2.0 * extra_trans);
  88   rectangle_add_point(rect,&pt);
  89 }
  90
  91 void
  92 bicubicbezier2D_bbox(const Point *p0,const Point *p1,
  93                      const Point *p2,const Point *p3,
  94                      const PolyBBExtras *extra,
  95                      Rectangle *rect)
  96 {
  97   real x[4],y[4];
  98   Point vl,vt,p,tt;
  99   real *xy;
 100   int i,extr;
 101   real u[2];
 102
 103   rect->left = rect->right = p0->x;
 104   rect->top = rect->bottom = p0->y;
 105
 106   rectangle_add_point(rect,p3);
 107   /* start point */
 108   point_copy_add_scaled(&vl,p0,p1,-1);
 109   point_normalize(&vl);
 110   add_arrow_rectangle(rect,p0,&vl,extra->start_long,MAX(extra->start_trans,
 111                                                          extra->middle_trans));
 112
 113   /* end point */
 114   point_copy_add_scaled(&vl,p3,p2,-1);
 115   point_normalize(&vl);
 116   add_arrow_rectangle(rect,p3,&vl,extra->end_long,MAX(extra->end_trans,
 117                                                       extra->middle_trans));
 118
 119   /* middle part */
 120   x[0] = p0->x; x[1] = p1->x; x[2] = p2->x; x[3] = p3->x;
 121   y[0] = p0->y; y[1] = p1->y; y[2] = p2->y; y[3] = p3->y;
 122
 123   for (xy = x; xy ; xy=(xy==x?y:NULL) ) { /* sorry */
 124     extr = bicubicbezier_extrema(xy,u);
 125     for (i=0;i<extr;i++) {
 126       if ((u[i]<0) || (u[i]>1)) continue;
 127       p.x = bezier_eval(x,u[i]);
 128       vl.x = bezier_eval_tangent(x,u[i]);
 129       p.y = bezier_eval(y,u[i]);
 130       vl.y = bezier_eval_tangent(y,u[i]);
 131       point_normalize(&vl);
 132       point_get_perp(&vt,&vl);
 133
 134       point_copy_add_scaled(&tt,&p,&vt,extra->middle_trans);
 135       rectangle_add_point(rect,&tt);
 136       point_copy_add_scaled(&tt,&p,&vt,-extra->middle_trans);
 137       rectangle_add_point(rect,&tt);
 138     }
 139   }
 140 }
 141
 142
 143 void
 144 line_bbox(const Point *p1, const Point *p2,
 145           const LineBBExtras *extra,
 146           Rectangle *rect)
 147 {
 148   Point vl;
 149
 150   rect->left = rect->right = p1->x;
 151   rect->top = rect->bottom = p1->y;
 152
 153   rectangle_add_point(rect,p2); /* as a safety */
 154
 155   point_copy_add_scaled(&vl,p1,p2,-1);
 156   point_normalize(&vl);
 157   add_arrow_rectangle(rect,p1,&vl,extra->start_long,extra->start_trans);
 158   point_scale(&vl,-1);
 159   add_arrow_rectangle(rect,p2,&vl,extra->end_long,extra->end_trans);
 160 }
 161
 162 void
 163 ellipse_bbox(const Point *centre, real width, real height,
 164              const ElementBBExtras *extra,
 165              Rectangle *rect)
 166 {
 167   Rectangle rin;
 168   rin.left = centre->x - width/2;
 169   rin.right = centre->x + width/2;
 170   rin.top = centre->y - height/2;
 171   rin.bottom = centre->y + height/2;
 172
 173   rectangle_bbox(&rin,extra,rect);
 174 }
 175
 176 static BezPoint *
 177 alloc_polybezier_space(int numpoints) {
 178   /* Allocate some SCRATCH space to hold a big enough Bezier.
 179    That space is not guaranteed to be preserved upon the next allocation
 180    (in fact it's guaranteed it's not). */
 181   static int alloc_np = 0;
 182   static BezPoint *alloced = NULL;
 183
 184   if (alloc_np < numpoints) {
 185     g_free(alloced);
 186     alloc_np = numpoints;
 187     alloced = g_new0(BezPoint,numpoints);
 188   }
 189   return alloced;
 190 }
 191
 192 static void free_polybezier_space(BezPoint *points) { /* dummy */ }
 193
 194 void
 195 polyline_bbox(const Point *pts, int numpoints,
 196               const PolyBBExtras *extra, gboolean closed,
 197               Rectangle *rect)
 198 {
 199   /* It's much easier to re-use the Bezier code... */
 200   int i;
 201   BezPoint *bpts = alloc_polybezier_space(numpoints + 1);
 202
 203   bpts[0].type = BEZ_MOVE_TO;
 204   bpts[0].p1 = pts[0];
 205
 206   for (i=1;i<numpoints;i++) {
 207     bpts[i].type = BEZ_LINE_TO;
 208     bpts[i].p1 = pts[i];
 209   }
 210   /* This one will be used only when closed==TRUE... */
 211   bpts[numpoints].type = BEZ_LINE_TO;
 212   bpts[numpoints].p1 = pts[0];
 213
 214   polybezier_bbox(bpts,numpoints + (closed?1:0),extra,closed,rect);
 215   free_polybezier_space(bpts);
 216 }
 217
 218 void
 219 polybezier_bbox(const BezPoint *pts, int numpoints,
 220                 const PolyBBExtras *extra, gboolean closed,
 221                 Rectangle *rect)
 222 {
 223   Point vx,vp,vn,vsc;
 224   int i,prev,next;
 225   Rectangle rt;
 226   PolyBBExtras bextra,start_bextra,end_bextra;
 227   LineBBExtras lextra,start_lextra,end_lextra,full_lextra;
 228   gboolean start,end;
 229
 230   g_assert(pts[0].type == BEZ_MOVE_TO);
 231
 232   rect->left = rect->right = pts[0].p1.x;
 233   rect->top = rect->bottom = pts[0].p1.y;
 234
 235   /* First, we build derived BBExtras structures, so we have something to feed
 236      the primitives. */
 237   if (!closed) {
 238     start_lextra.start_long = extra->start_long;
 239     start_lextra.start_trans = MAX(extra->start_trans,extra->middle_trans);
 240     start_lextra.end_long = 0;
 241     start_lextra.end_trans = extra->middle_trans;
 242
 243     end_lextra.start_long = 0;
 244     end_lextra.start_trans = extra->middle_trans;
 245     end_lextra.end_long = extra->end_long;
 246     end_lextra.end_trans = MAX(extra->end_trans,extra->middle_trans);
 247   }
 248
 249   full_lextra.start_long = extra->start_long;
 250   full_lextra.start_trans = MAX(extra->start_trans,extra->middle_trans);
 251   full_lextra.end_long = extra->end_long;
 252   full_lextra.end_trans = MAX(extra->end_trans,extra->middle_trans);
 253
 254   if (!closed) {
 255     lextra.start_long = 0;
 256     lextra.start_trans = extra->middle_trans;
 257     lextra.end_long = 0;
 258     lextra.end_trans = extra->middle_trans;
 259
 260     start_bextra.start_long = extra->start_long;
 261     start_bextra.start_trans = extra->start_trans;
 262     start_bextra.middle_trans = extra->middle_trans;
 263     start_bextra.end_long = 0;
 264     start_bextra.end_trans = extra->middle_trans;
 265
 266     end_bextra.start_long = 0;
 267     end_bextra.start_trans = extra->middle_trans;
 268     end_bextra.middle_trans = extra->middle_trans;
 269     end_bextra.end_long = extra->end_long;
 270     end_bextra.end_trans = extra->end_trans;
 271   }
 272
 273   bextra.start_long = 0;
 274   bextra.start_trans = extra->middle_trans;
 275   bextra.middle_trans = extra->middle_trans;
 276   bextra.end_long = 0;
 277   bextra.end_trans = extra->middle_trans;
 278
 279
 280   for (i=1;i<numpoints;i++) {
 281     next = (i+1) % numpoints;
 282     prev = (i-1) % numpoints;
 283     if (closed && (next == 0)) next=1;
 284     if (closed && (prev == 0)) prev=numpoints-1;
 285
 286     /* We have now:
 287        i = index of current vertex.
 288        prev,next: index of previous/next vertices (of the control polygon)
 289
 290        We want:
 291         vp, vx, vn: the previous, current and next vertices;
 292         start, end: TRUE if we're at an end of poly (then, vp and/or vn are not
 293         valid, respectively).
 294
 295        Some values *will* be recomputed a few times across iterations (but stored in
 296        different boxes). Either gprof says it's a real problem, or gcc finally gets
 297        a clue.
 298     */
 299
 300     if (pts[i].type == BEZ_MOVE_TO) {
 301       continue;
 302     }
 303
 304     switch(pts[i].type) {
 305     case BEZ_MOVE_TO:
 306       g_assert_not_reached();
 307       break;
 308     case BEZ_LINE_TO:
 309       point_copy(&vx,&pts[i].p1);
 310       switch(pts[prev].type) {
 311       case BEZ_MOVE_TO:
 312       case BEZ_LINE_TO:
 313         point_copy(&vsc,&pts[prev].p1);
 314         point_copy(&vp,&pts[prev].p1);
 315         break;
 316       case BEZ_CURVE_TO:
 317         point_copy(&vsc,&pts[prev].p3);
 318         point_copy(&vp,&pts[prev].p3);
 319         break;
 320       }
 321       break;
 322     case BEZ_CURVE_TO:
 323       point_copy(&vx,&pts[i].p3);
 324       point_copy(&vp,&pts[i].p2);
 325       switch(pts[prev].type) {
 326       case BEZ_MOVE_TO:
 327       case BEZ_LINE_TO:
 328         point_copy(&vsc,&pts[prev].p1);
 329         break;
 330       case BEZ_CURVE_TO:
 331         point_copy(&vsc,&pts[prev].p3);
 332         break;
 333       } /* vsc is the start of the curve. */
 334
 335       break;
 336     }
 337     start = (pts[prev].type == BEZ_MOVE_TO);
 338     end = (pts[next].type == BEZ_MOVE_TO);
 339     point_copy(&vn,&pts[next].p1); /* whichever type pts[next] is. */
 340
 341     /* Now, we know about a few vertices around the one we're dealing with.
 342        Depending on the shape of the (previous,current) segment, and whether
 343        it's a middle or end segment, we'll be doing different stuff. */
 344     if (closed) {
 345       if (pts[i].type == BEZ_LINE_TO) {
 346         line_bbox(&vsc,&vx,&full_lextra,&rt);
 347       } else {
 348         bicubicbezier2D_bbox(&vsc,
 349                              &pts[i].p1,&pts[i].p2,&pts[i].p3,
 350                              &bextra,
 351                              &rt);
 352       }
 353     } else if (start) {
 354       if (pts[i].type == BEZ_LINE_TO) {
 355         if (end) {
 356           line_bbox(&vsc,&vx,&full_lextra,&rt);
 357         } else {
 358           line_bbox(&vsc,&vx,&start_lextra,&rt);
 359         }
 360       } else { /* BEZ_MOVE_TO */
 361         if (end) {
 362           bicubicbezier2D_bbox(&vsc,
 363                                &pts[i].p1,&pts[i].p2,&pts[i].p3,
 364                                extra,
 365                                &rt);
 366         } else {
 367           bicubicbezier2D_bbox(&vsc,
 368                                &pts[i].p1,&pts[i].p2,&pts[i].p3,
 369                                &start_bextra,
 370                                &rt);
 371         }
 372       }
 373     } else if (end) { /* end but not start. Not closed anyway. */
 374       if (pts[i].type == BEZ_LINE_TO) {
 375         line_bbox(&vsc,&vx,&end_lextra,&rt);
 376       } else {
 377         bicubicbezier2D_bbox(&vsc,
 378                              &pts[i].p1,&pts[i].p2,&pts[i].p3,
 379                              &end_bextra,
 380                              &rt);
 381       }
 382     } else { /* normal case : middle segment (not closed shape). */
 383       if (pts[i].type == BEZ_LINE_TO) {
 384         line_bbox(&vsc,&vx,&lextra,&rt);
 385       } else {
 386         bicubicbezier2D_bbox(&vsc,
 387                              &pts[i].p1,&pts[i].p2,&pts[i].p3,
 388                              &bextra,
 389                              &rt);
 390       }
 391     }
 392     rectangle_union(rect,&rt);
 393
 394     /* The following code enlarges a little the bounding box (if necessary) to
 395        account with the "pointy corners" X (and PS) add when LINEJOIN_MITER mode is
 396        in force. */
 397
 398     if ((!start) && (!end)) { /* We have a non-extremity vertex. */
 399       Point vpx,vxn;
 400       real co,alpha;
 401
 402       point_copy_add_scaled(&vpx,&vx,&vp,-1);
 403       point_normalize(&vpx);
 404       point_copy_add_scaled(&vxn,&vn,&vx,-1);
 405       point_normalize(&vxn);
 406
 407       co = point_dot(&vpx,&vxn);
 408       alpha = acos(-co);
 409       if ((co > -0.9816) && (finite(alpha))) { /* 0.9816 = cos(11deg) */
 410         /* we have a pointy join. */
 411         real overshoot = extra->middle_trans / sin(alpha/2.0);
 412         Point vovs,pto;
 413
 414         point_copy_add_scaled(&vovs,&vpx,&vxn,-1);
 415         point_normalize(&vovs);
 416         point_copy_add_scaled(&pto,&vx,&vovs,overshoot);
 417
 418         rectangle_add_point(rect,&pto);
 419       } else {
 420         /* we don't have a pointy join. */
 421         Point vpxt,vxnt,tmp;
 422
 423         point_get_perp(&vpxt,&vpx);
 424         point_get_perp(&vxnt,&vxn);
 425
 426         point_copy_add_scaled(&tmp,&vx,&vpxt,1);
 427         rectangle_add_point(rect,&tmp);
 428         point_copy_add_scaled(&tmp,&vx,&vpxt,-1);
 429         rectangle_add_point(rect,&tmp);
 430         point_copy_add_scaled(&tmp,&vx,&vxnt,1);
 431         rectangle_add_point(rect,&tmp);
 432         point_copy_add_scaled(&tmp,&vx,&vxnt,-1);
 433         rectangle_add_point(rect,&tmp);
 434       }
 435     }
 436   }
 437 }
 438
 439 void rectangle_bbox(const Rectangle *rin,
 440                     const ElementBBExtras *extra,
 441                     Rectangle *rout)
 442 {
 443   rout->left = rin->left - extra->border_trans;
 444   rout->top = rin->top - extra->border_trans;
 445   rout->right = rin->right + extra->border_trans;
 446   rout->bottom = rin->bottom + extra->border_trans;
 447 }
 448
 449
 450 /* TODO: text_bbox ? */
 451
 452