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