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