lib/gfxpoly.c

   1 /* gfxpoly.c
   2
   3    Various boolean polygon functions.
   4
   5    Part of the swftools package.
   6
   7    Copyright (c) 2005 Matthias Kramm <kramm@quiss.org>
   8
   9    This program is free software; you can redistribute it and/or modify
  10    it under the terms of the GNU General Public License as published by
  11    the Free Software Foundation; either version 2 of the License, or
  12    (at your option) any later version.
  13
  14    This program is distributed in the hope that it will be useful,
  15    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17    GNU General Public License for more details.
  18
  19    You should have received a copy of the GNU General Public License
  20    along with this program; if not, write to the Free Software
  21    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  22
  23 #include "../config.h"
  24 #include "gfxdevice.h"
  25 #include "gfxtools.h"
  26 #include "gfxpoly.h"
  27 #include "art/libart.h"
  28 #include "art/art_svp_intersect.h"
  29 #include <assert.h>
  30 #include <memory.h>
  31 #include <math.h>
  32
  33 static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
  34 {
  35     ArtVpath *vec = NULL;
  36     int pos=0,len=0;
  37     gfxline_t*l2;
  38     double x=0,y=0;
  39
  40     /* factor which determines into how many line fragments a spline is converted */
  41     double subfraction = 2.4;//0.3
  42
  43     l2 = line;
  44     while(l2) {
  45         if(l2->type == gfx_moveTo) {
  46             pos ++;
  47         } if(l2->type == gfx_lineTo) {
  48             pos ++;
  49         } if(l2->type == gfx_splineTo) {
  50             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
  51             if(!parts) parts = 1;
  52             pos += parts + 1;
  53         }
  54         x = l2->x;
  55         y = l2->y;
  56         l2 = l2->next;
  57     }
  58     pos++;
  59     len = pos;
  60
  61     vec = art_new (ArtVpath, len+1);
  62
  63     pos = 0;
  64     l2 = line;
  65     while(l2) {
  66         if(l2->type == gfx_moveTo) {
  67             vec[pos].code = ART_MOVETO;
  68             vec[pos].x = l2->x;
  69             vec[pos].y = l2->y;
  70             pos++;
  71             assert(pos<=len);
  72         } else if(l2->type == gfx_lineTo) {
  73             vec[pos].code = ART_LINETO;
  74             vec[pos].x = l2->x;
  75             vec[pos].y = l2->y;
  76             pos++;
  77             assert(pos<=len);
  78         } else if(l2->type == gfx_splineTo) {
  79             int i;
  80             int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
  81             double stepsize = parts?1.0/parts:0;
  82             for(i=0;i<=parts;i++) {
  83                 double t = (double)i*stepsize;
  84                 vec[pos].code = ART_LINETO;
  85                 vec[pos].x = l2->x*t*t + 2*l2->sx*t*(1-t) + x*(1-t)*(1-t);
  86                 vec[pos].y = l2->y*t*t + 2*l2->sy*t*(1-t) + y*(1-t)*(1-t);
  87                 pos++;
  88                 assert(pos<=len);
  89             }
  90         }
  91         x = l2->x;
  92         y = l2->y;
  93         l2 = l2->next;
  94     }
  95     vec[pos].code = ART_END;
  96
  97     if(!fill) {
  98         /* Fix "dotted" lines. Those are lines where singular points are created
  99            by a moveto x,y lineto x,y combination. We "fix" these by shifting the
 100            point in the lineto a little bit to the right
 101            These should only occur in strokes, not in fills, so do this only
 102            when we know we're not filling.
 103          */
 104         int t;
 105         for(t=0;vec[t].code!=ART_END;t++) {
 106             if(t>0 && vec[t-1].code==ART_MOVETO && vec[t].code==ART_LINETO
 107                     && vec[t+1].code!=ART_LINETO
 108                 && vec[t-1].x == vec[t].x
 109                 && vec[t-1].y == vec[t].y) {
 110                 vec[t].x += 0.01;
 111             }
 112             x = vec[t].x;
 113             y = vec[t].y;
 114         }
 115     }
 116
 117     /* Find adjacent identical points. If an ajdacent pair of identical
 118        points is found, the second is removed.
 119        So moveto x,y lineto x,y becomes moveto x,y
 120           lineto x,y lineto x,y becomes lineto x,y
 121           lineto x,y moveto x,y becomes lineto x,y
 122           moveto x,y moveto x,y becomes moveto x,y
 123      */
 124     int t = 1;
 125     while(t < pos)
 126     {
 127         if ((vec[t-1].x == vec[t].x) && (vec[t-1].y == vec[t].y)) {
 128             // adjacent identical points; remove the second
 129             memcpy(&vec[t], &vec[t+1], sizeof(vec[0]) * (pos - t - 1));
 130             pos--;
 131         } else {
 132             t++;
 133         }
 134     }
 135
 136     /* adjacency remover disabled for now, pending code inspection */
 137     return vec;
 138
 139     // Check for further non-adjacent identical points. We don't want any
 140     // points other than the first and last points to exactly match.
 141     //
 142     // If we do find matching points, move the second point slightly. This
 143     // currently moves the duplicate 2% towards the midpoint of its neighbours
 144     // (easier to calculate than 2% down the perpendicular to the line joining
 145     // the neighbours) but limiting the change to 0.1 twips to avoid visual
 146     // problems when the shapes are large. Note that there is no minimum
 147     // change: if the neighbouring points are colinear and equally spaced,
 148     // e.g. they were generated as part of a straight spline, then the
 149     // duplicate point may not actually move.
 150     //
 151     // The scan for duplicates algorithm is quadratic in the number of points:
 152     // there's probably a better method but the numbers of points is generally
 153     // small so this will do for now.
 154     {
 155         int i = 1, j;
 156         for(; i < (pos - 1); ++i)
 157         {
 158             for (j = 0; j < i; ++j)
 159             {
 160                 if ((vec[i].x == vec[j].x)
 161                     && (vec[i].y == vec[j].y))
 162                 {
 163                     // points match; shuffle point
 164                     double dx = (vec[i-1].x + vec[i+1].x - (vec[i].x * 2.0)) / 100.0;
 165                     double dy = (vec[i-1].y + vec[i+1].y - (vec[i].y * 2.0)) / 100.0;
 166                     double dxxyy = (dx*dx) + (dy*dy);
 167                     if (dxxyy > 0.01)
 168                     {
 169                         // This is more than 0.1 twip's distance; scale down
 170                         double dscale = sqrt(dxxyy) * 10.0;
 171                         dx /= dscale;
 172                         dy /= dscale;
 173                     };
 174                     vec[i].x += dx;
 175                     vec[i].y += dy;
 176                     break;
 177                 }
 178             }
 179         }
 180     }
 181
 182     return vec;
 183 }
 184
 185 void show_path(ArtSVP*path)
 186 {
 187     int t;
 188     printf("Segments: %d\n", path->n_segs);
 189     for(t=0;t<path->n_segs;t++) {
 190         ArtSVPSeg* seg = &path->segs[t];
 191         printf("Segment %d: %d points, %s, BBox: (%f,%f,%f,%f)\n",
 192                 t, seg->n_points, seg->dir==0?"UP  ":"DOWN",
 193                 seg->bbox.x0, seg->bbox.y0, seg->bbox.x1, seg->bbox.y1);
 194         int p;
 195         for(p=0;p<seg->n_points;p++) {
 196             ArtPoint* point = &seg->points[p];
 197             printf("        (%f,%f)\n", point->x, point->y);
 198         }
 199     }
 200     printf("\n");
 201 }
 202
 203 ArtSVP* gfxfillToSVP(gfxline_t*line, int perturb)
 204 {
 205     ArtVpath* vec = gfxline_to_ArtVpath(line, 1);
 206     if(perturb) {
 207         ArtVpath* vec2 = art_vpath_perturb(vec);
 208         free(vec);
 209         vec = vec2;
 210     }
 211     ArtSVP *svp = art_svp_from_vpath(vec);
 212     free(vec);
 213
 214     // We need to make sure that the SVP we now have bounds an area (i.e. the
 215     // source line wound anticlockwise) rather than excludes an area (i.e. the
 216     // line wound clockwise). It seems that PDF (or xpdf) is less strict about
 217     // this for bitmaps than it is for fill areas.
 218     //
 219     // To check this, we'll sum the cross products of all pairs of adjacent
 220     // lines. If the result is positive, the direction is correct; if not, we
 221     // need to reverse the sense of the SVP generated. The easiest way to do
 222     // this is to flip the up/down flags of all the segments.
 223     //
 224     // This is approximate; since the gfxline_t structure can contain any
 225     // combination of moveTo, lineTo and splineTo in any order, not all pairs
 226     // of lines in the shape that share a point need be described next to each
 227     // other in the sequence. For ease, we'll consider only pairs of lines
 228     // stored as lineTos and splineTos without intervening moveTos.
 229     //
 230     // TODO is this a valid algorithm? My vector maths is rusty.
 231     //
 232     // It may be more correct to instead reverse the line before we feed it
 233     // into gfxfilltoSVP. However, this seems equivalent and is easier to
 234     // implement!
 235     double total_cross_product = 0.0;
 236     gfxline_t* cursor = line;
 237     if (cursor != NULL)
 238     {
 239         double x_last = cursor->x;
 240         double y_last = cursor->y;
 241         cursor = cursor->next;
 242
 243         while((cursor != NULL) && (cursor->next != NULL))
 244         {
 245             if (((cursor->type == gfx_lineTo) || (cursor->type == gfx_splineTo))
 246                 && ((cursor->next->type == gfx_lineTo) || (cursor->next->type == gfx_splineTo)))
 247             {
 248                 // Process these lines
 249                 //
 250                 // In this space (x right, y down) the cross-product is
 251                 // (x1 * y0) - (x0 * y1)
 252                 double x0 = cursor->x - x_last;
 253                 double y0 = cursor->y - y_last;
 254                 double x1 = cursor->next->x - cursor->x;
 255                 double y1 = cursor->next->y - cursor->y;
 256                 total_cross_product += (x1 * y0) - (x0 * y1);
 257             }
 258
 259             x_last = cursor->x;
 260             y_last = cursor->y;
 261             cursor = cursor->next;
 262         }
 263     }
 264     if (total_cross_product < 0.0)
 265     {
 266         int i = 0;
 267         for(; i < svp->n_segs; ++i)
 268         {
 269             if (svp->segs[i].dir != 0)
 270                 svp->segs[i].dir = 0;
 271             else
 272                 svp->segs[i].dir = 1;
 273         }
 274     }
 275     return svp;
 276 }
 277
 278 gfxline_t* gfxpoly_to_gfxline(gfxpoly_t*poly)
 279 {
 280     ArtSVP*svp = (ArtSVP*)poly;
 281     int size = 0;
 282     int t;
 283     int pos = 0;
 284     for(t=0;t<svp->n_segs;t++) {
 285         size += svp->segs[t].n_points + 1;
 286     }
 287     gfxline_t* lines = (gfxline_t*)rfx_alloc(sizeof(gfxline_t)*size);
 288
 289     for(t=0;t<svp->n_segs;t++) {
 290         ArtSVPSeg* seg = &svp->segs[t];
 291         int p;
 292         for(p=0;p<seg->n_points;p++) {
 293             lines[pos].type = p==0?gfx_moveTo:gfx_lineTo;
 294             ArtPoint* point = &seg->points[p];
 295             lines[pos].x = point->x;
 296             lines[pos].y = point->y;
 297             lines[pos].next = &lines[pos+1];
 298             pos++;
 299         }
 300     }
 301     if(pos) {
 302         lines[pos-1].next = 0;
 303         return lines;
 304     } else {
 305         return 0;
 306     }
 307 }
 308
 309 gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line)
 310 {
 311     ArtSVP* svp = gfxfillToSVP(line, 1);
 312     if (svp->n_segs > 500)
 313     {
 314         int lineParts = 0;
 315         gfxline_t* lineCursor = line;
 316         while(lineCursor != NULL)
 317         {
 318             if(lineCursor->type != gfx_moveTo) ++lineParts;
 319             lineCursor = lineCursor->next;
 320         }
 321         fprintf(stderr, "arts_fill abandonning shape with %d segments (%d line parts)\n", svp->n_segs, lineParts);
 322         art_svp_free(svp);
 323
 324         /* return empty shape */
 325         return (gfxpoly_t*)gfxpoly_strokeToPoly(0, 0, gfx_capButt, gfx_joinMiter, 0);
 326     }
 327
 328     /* for some reason, we need to rewind / self-intersect the polygons that gfxfillToSVP
 329        returns- art probably uses a different fill mode (circular?) for vpaths */
 330     ArtSVP*svp_uncrossed=0;
 331 #ifdef ART_USE_NEW_INTERSECTOR
 332     ArtSvpWriter * swr = art_svp_writer_rewind_new(ART_WIND_RULE_ODDEVEN);
 333     art_svp_intersector(svp, swr);
 334     svp_uncrossed = art_svp_writer_rewind_reap(swr);
 335 #else
 336     svp_uncrossed = art_svp_rewind_uncrossed(art_svp_uncross(svp),ART_WIND_RULE_ODDEVEN);
 337 #endif
 338     art_svp_free(svp);
 339     svp=svp_uncrossed;
 340
 341     return (gfxpoly_t*)svp;
 342 }
 343
 344 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*poly1, gfxpoly_t*poly2)
 345 {
 346     ArtSVP* svp1 = (ArtSVP*)poly1;
 347     ArtSVP* svp2 = (ArtSVP*)poly2;
 348
 349     ArtSVP* svp = art_svp_intersect(svp1, svp2);
 350     return (gfxpoly_t*)svp;
 351 }
 352
 353 gfxpoly_t* gfxpoly_union(gfxpoly_t*poly1, gfxpoly_t*poly2)
 354 {
 355     ArtSVP* svp1 = (ArtSVP*)poly1;
 356     ArtSVP* svp2 = (ArtSVP*)poly2;
 357
 358     ArtSVP* svp = art_svp_union(svp1, svp2);
 359     return (gfxpoly_t*)svp;
 360 }
 361
 362 gfxpoly_t* gfxpoly_strokeToPoly(gfxline_t*line, gfxcoord_t width, gfx_capType cap_style, gfx_joinType joint_style, double miterLimit)
 363 {
 364     ArtVpath* vec = gfxline_to_ArtVpath(line, 0);
 365     ArtSVP *svp = art_svp_vpath_stroke (vec,
 366                         (joint_style==gfx_joinMiter)?ART_PATH_STROKE_JOIN_MITER:
 367                         ((joint_style==gfx_joinRound)?ART_PATH_STROKE_JOIN_ROUND:
 368                          ((joint_style==gfx_joinBevel)?ART_PATH_STROKE_JOIN_BEVEL:ART_PATH_STROKE_JOIN_BEVEL)),
 369                         (cap_style==gfx_capButt)?ART_PATH_STROKE_CAP_BUTT:
 370                         ((cap_style==gfx_capRound)?ART_PATH_STROKE_CAP_ROUND:
 371                          ((cap_style==gfx_capSquare)?ART_PATH_STROKE_CAP_SQUARE:ART_PATH_STROKE_CAP_SQUARE)),
 372                         width, //line_width
 373                         miterLimit, //miter_limit
 374                         0.05 //flatness
 375                         );
 376     free(vec);
 377     return (gfxpoly_t*)svp;
 378 }
 379
 380 gfxline_t* gfxline_circularToEvenOdd(gfxline_t*line)
 381 {
 382     ArtSVP* svp = gfxfillToSVP(line, 1);
 383
 384     ArtSVP* svp_rewinded;
 385 #ifdef ART_USE_NEW_INTERSECTOR
 386     ArtSvpWriter * swr = art_svp_writer_rewind_new (ART_WIND_RULE_POSITIVE);
 387     art_svp_intersector(svp, swr);
 388     svp_rewinded = art_svp_writer_rewind_reap(swr);
 389 #else
 390     jjj
 391     svp_rewinded = art_svp_rewind_uncrossed(art_svp_uncross(svp),ART_WIND_RULE_POSITIVE);
 392 #endif
 393
 394     gfxline_t* result = gfxpoly_to_gfxline((gfxpoly_t*)svp_rewinded);
 395     art_svp_free(svp);
 396     art_svp_free(svp_rewinded);
 397     return result;
 398 }
 399
 400 gfxpoly_t* gfxpoly_createbox(double x1, double y1,double x2, double y2)
 401 {
 402     ArtVpath *vec = art_new (ArtVpath, 5+1);
 403     vec[0].code = ART_MOVETO;
 404     vec[0].x = x1;
 405     vec[0].y = y1;
 406     vec[1].code = ART_LINETO;
 407     vec[1].x = x1;
 408     vec[1].y = y2;
 409     vec[2].code = ART_LINETO;
 410     vec[2].x = x2;
 411     vec[2].y = y2;
 412     vec[3].code = ART_LINETO;
 413     vec[3].x = x2;
 414     vec[3].y = y1;
 415     vec[4].code = ART_LINETO;
 416     vec[4].x = x1;
 417     vec[4].y = y1;
 418     vec[5].code = ART_END;
 419     vec[5].x = 0;
 420     vec[5].y = 0;
 421     ArtSVP *svp = art_svp_from_vpath(vec);
 422     free(vec);
 423     return (gfxpoly_t*)svp;
 424 }
 425
 426 void gfxpoly_free(gfxpoly_t*poly)
 427 {
 428     ArtSVP*svp = (ArtSVP*)poly;
 429     art_svp_free(svp);
 430 }