3 Various boolean polygon functions.
5 Part of the swftools package.
7 Copyright (c) 2005 Matthias Kramm <kramm@quiss.org>
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.
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.
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 */
23 #include "../config.h"
24 #include "gfxdevice.h"
28 #include "art/libart.h"
29 #include "art/art_svp_intersect.h"
35 static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
42 /* factor which determines into how many line fragments a spline is converted */
43 double subfraction = 2.4;//0.3
47 if(l2->type == gfx_moveTo) {
49 } if(l2->type == gfx_lineTo) {
51 } if(l2->type == gfx_splineTo) {
52 int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
63 vec = art_new (ArtVpath, len+1);
68 if(l2->type == gfx_moveTo) {
69 vec[pos].code = ART_MOVETO;
74 } else if(l2->type == gfx_lineTo) {
75 vec[pos].code = ART_LINETO;
80 } else if(l2->type == gfx_splineTo) {
82 int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
83 double stepsize = parts?1.0/parts:0;
84 for(i=0;i<=parts;i++) {
85 double t = (double)i*stepsize;
86 vec[pos].code = ART_LINETO;
87 vec[pos].x = l2->x*t*t + 2*l2->sx*t*(1-t) + x*(1-t)*(1-t);
88 vec[pos].y = l2->y*t*t + 2*l2->sy*t*(1-t) + y*(1-t)*(1-t);
97 vec[pos].code = ART_END;
100 /* Fix "dotted" lines. Those are lines where singular points are created
101 by a moveto x,y lineto x,y combination. We "fix" these by shifting the
102 point in the lineto a little bit to the right
103 These should only occur in strokes, not in fills, so do this only
104 when we know we're not filling.
107 for(t=0;vec[t].code!=ART_END;t++) {
108 if(t>0 && vec[t-1].code==ART_MOVETO && vec[t].code==ART_LINETO
109 && vec[t+1].code!=ART_LINETO &&
110 vec[t-1].x == vec[t].x &&
111 vec[t-1].y == vec[t].y) {
119 /* Find adjacent identical points. If an ajdacent pair of identical
120 points is found, the second is removed.
121 So moveto x,y lineto x,y becomes moveto x,y
122 lineto x,y lineto x,y becomes lineto x,y
123 lineto x,y moveto x,y becomes lineto x,y
124 moveto x,y moveto x,y becomes moveto x,y
125 lineto x,y lineto x2,y2 becomes lineto x2,y2 (if dir(x,y) ~= dir(x2,y2))
130 double dx = vec[t].x-vec[t-1].x;
131 double dy = vec[t].y-vec[t-1].y;
133 if(t<pos-1 && vec[t].code == ART_LINETO && vec[t+1].code == ART_LINETO) {
134 double dx2 = vec[t+1].x-vec[t].x;
135 double dy2 = vec[t+1].y-vec[t].y;
136 if(fabs(dx*dy2 - dy*dx2) < 0.001) {
140 if(fabs(dx) + fabs(dy) < 0.01 || samedir) {
141 // adjacent identical points; remove the second
142 memcpy(&vec[t], &vec[t+1], sizeof(vec[0]) * (pos - t - 1));
149 /* adjacency remover disabled for now, pending code inspection */
152 // Check for further non-adjacent identical points. We don't want any
153 // points other than the first and last points to exactly match.
155 // If we do find matching points, move the second point slightly. This
156 // currently moves the duplicate 2% towards the midpoint of its neighbours
157 // (easier to calculate than 2% down the perpendicular to the line joining
158 // the neighbours) but limiting the change to 0.1 twips to avoid visual
159 // problems when the shapes are large. Note that there is no minimum
160 // change: if the neighbouring points are colinear and equally spaced,
161 // e.g. they were generated as part of a straight spline, then the
162 // duplicate point may not actually move.
164 // The scan for duplicates algorithm is quadratic in the number of points:
165 // there's probably a better method but the numbers of points is generally
166 // small so this will do for now.
169 for(; i < (pos - 1); ++i)
171 for (j = 0; j < i; ++j)
173 if ((vec[i].x == vec[j].x)
174 && (vec[i].y == vec[j].y))
176 // points match; shuffle point
177 double dx = (vec[i-1].x + vec[i+1].x - (vec[i].x * 2.0)) / 100.0;
178 double dy = (vec[i-1].y + vec[i+1].y - (vec[i].y * 2.0)) / 100.0;
179 double dxxyy = (dx*dx) + (dy*dy);
182 // This is more than 0.1 twip's distance; scale down
183 double dscale = sqrt(dxxyy) * 10.0;
198 void show_path(ArtSVP*path)
201 printf("Segments: %d\n", path->n_segs);
202 for(t=0;t<path->n_segs;t++) {
203 ArtSVPSeg* seg = &path->segs[t];
204 printf("Segment %d: %d points, %s, BBox: (%f,%f,%f,%f)\n",
205 t, seg->n_points, seg->dir==0?"UP ":"DOWN",
206 seg->bbox.x0, seg->bbox.y0, seg->bbox.x1, seg->bbox.y1);
208 for(p=0;p<seg->n_points;p++) {
209 ArtPoint* point = &seg->points[p];
210 printf(" (%f,%f)\n", point->x, point->y);
216 void write_svp_postscript(const char*filename, ArtSVP*svp)
218 FILE*fi = fopen(filename, "wb");
220 double xmin=0,ymin=0,xmax=0,ymax=0;
221 fprintf(fi, "%% begin\n");
222 for (i = 0; i < svp->n_segs; i++) {
223 for (j = 0; j < svp->segs[i].n_points; j++) {
224 double x = svp->segs[i].points[j].x;
225 double y = svp->segs[i].points[j].y;
230 if(x < xmin) xmin = x;
231 if(x > xmax) xmax = x;
232 if(y < ymin) ymin = y;
233 if(y > ymax) ymax = y;
237 if(xmax == xmin) xmax=xmin+1;
238 if(ymax == ymin) ymax=ymin+1;
240 for (i = 0; i < svp->n_segs; i++)
242 fprintf(fi, "%g setgray\n", svp->segs[i].dir ? 0.7 : 0);
243 for (j = 0; j < svp->segs[i].n_points; j++)
245 fprintf(fi, "%g %g %s\n",
246 20 + 550*(svp->segs[i].points[j].x-xmin)/(xmax-xmin),
247 820 - 800*(svp->segs[i].points[j].y-ymin)/(ymax-ymin),
248 j ? "lineto" : "moveto");
250 fprintf(fi, "stroke\n");
253 fprintf(fi, "showpage\n");
257 void write_vpath_postscript(const char*filename, ArtVpath*path)
259 FILE*fi = fopen(filename, "wb");
261 double xmin=0,ymin=0,xmax=0,ymax=0;
262 fprintf(fi, "%% begin\n");
265 while(p->code != ART_END) {
266 if(p->code == ART_MOVETO || p->code == ART_MOVETO_OPEN) {
268 fprintf(fi, "stroke\n");
270 fprintf(fi, "1 setgray\n");
271 fprintf(fi, "%.32f %.32f moveto\n", p->x, p->y);
273 fprintf(fi, "%.32f %.32f lineto\n", p->x, p->y);
278 fprintf(fi, "stroke\n");
279 fprintf(fi, "showpage\n");
283 static int vpath_len(ArtVpath*svp)
286 while(svp->code != ART_END) {
293 int gfxline_len(gfxline_t*line)
305 static int debug = 0;
306 static ArtSVP* gfxfillToSVP(gfxline_t*line, int perturb)
308 ArtVpath* vec = gfxline_to_ArtVpath(line, 1);
309 msg("<verbose> Casting gfxline of %d segments (%d line segments) to a gfxpoly", gfxline_len(line), vpath_len(vec));
312 ArtVpath* vec2 = art_vpath_perturb(vec);
316 ArtSVP *svp = art_svp_from_vpath(vec);
318 write_vpath_postscript("vpath.ps", vec);
319 write_svp_postscript("polygon.ps", svp);
324 // We need to make sure that the SVP we now have bounds an area (i.e. the
325 // source line wound anticlockwise) rather than excludes an area (i.e. the
326 // line wound clockwise). It seems that PDF (or xpdf) is less strict about
327 // this for bitmaps than it is for fill areas.
329 // To check this, we'll sum the cross products of all pairs of adjacent
330 // lines. If the result is positive, the direction is correct; if not, we
331 // need to reverse the sense of the SVP generated. The easiest way to do
332 // this is to flip the up/down flags of all the segments.
334 // This is approximate; since the gfxline_t structure can contain any
335 // combination of moveTo, lineTo and splineTo in any order, not all pairs
336 // of lines in the shape that share a point need be described next to each
337 // other in the sequence. For ease, we'll consider only pairs of lines
338 // stored as lineTos and splineTos without intervening moveTos.
340 // TODO is this a valid algorithm? My vector maths is rusty.
342 // It may be more correct to instead reverse the line before we feed it
343 // into gfxfilltoSVP. However, this seems equivalent and is easier to
345 double total_cross_product = 0.0;
346 gfxline_t* cursor = line;
349 double x_last = cursor->x;
350 double y_last = cursor->y;
351 cursor = cursor->next;
353 while((cursor != NULL) && (cursor->next != NULL))
355 if (((cursor->type == gfx_lineTo) || (cursor->type == gfx_splineTo))
356 && ((cursor->next->type == gfx_lineTo) || (cursor->next->type == gfx_splineTo)))
358 // Process these lines
360 // In this space (x right, y down) the cross-product is
361 // (x1 * y0) - (x0 * y1)
362 double x0 = cursor->x - x_last;
363 double y0 = cursor->y - y_last;
364 double x1 = cursor->next->x - cursor->x;
365 double y1 = cursor->next->y - cursor->y;
366 total_cross_product += (x1 * y0) - (x0 * y1);
371 cursor = cursor->next;
374 if (total_cross_product < 0.0)
377 for(; i < svp->n_segs; ++i)
379 if (svp->segs[i].dir != 0)
380 svp->segs[i].dir = 0;
382 svp->segs[i].dir = 1;
390 gfxline_t* gfxpoly_to_gfxline(gfxpoly_t*poly)
392 ArtSVP*svp = (ArtSVP*)poly;
397 msg("<verbose> Casting polygon of %d segments back to gfxline", svp->n_segs);
399 for(t=0;t<svp->n_segs;t++) {
400 size += svp->segs[t].n_points + 1;
402 gfxline_t* lines = (gfxline_t*)rfx_alloc(sizeof(gfxline_t)*size);
404 for(t=0;t<svp->n_segs;t++) {
405 ArtSVPSeg* seg = &svp->segs[t];
407 for(p=0;p<seg->n_points;p++) {
408 lines[pos].type = p==0?gfx_moveTo:gfx_lineTo;
409 ArtPoint* point = &seg->points[p];
410 lines[pos].x = point->x;
411 lines[pos].y = point->y;
412 lines[pos].next = &lines[pos+1];
417 lines[pos-1].next = 0;
423 gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line)
425 ArtSVP* svp = gfxfillToSVP(line, 1);
427 /* we do xor-filling by default, so dir is always 1
428 (actually for oddeven rewinding it makes no difference, but
432 for(t=0; t<svp->n_segs; t++) {
433 svp->segs[t].dir = 1;
436 /* for some reason, we need to rewind / self-intersect the polygons that gfxfillToSVP
437 returns- art probably uses a different fill mode (circular?) for vpaths */
438 ArtSVP*svp_uncrossed=0;
439 #ifdef ART_USE_NEW_INTERSECTOR
440 ArtSvpWriter * swr = art_svp_writer_rewind_new(ART_WIND_RULE_ODDEVEN);
441 art_svp_intersector(svp, swr);
442 svp_uncrossed = art_svp_writer_rewind_reap(swr);
444 svp_uncrossed = art_svp_rewind_uncrossed(art_svp_uncross(svp),ART_WIND_RULE_ODDEVEN);
449 return (gfxpoly_t*)svp;
452 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*poly1, gfxpoly_t*poly2)
454 ArtSVP* svp1 = (ArtSVP*)poly1;
455 ArtSVP* svp2 = (ArtSVP*)poly2;
456 msg("<verbose> Intersecting two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
458 ArtSVP* svp = art_svp_intersect(svp1, svp2);
459 return (gfxpoly_t*)svp;
462 gfxpoly_t* gfxpoly_union(gfxpoly_t*poly1, gfxpoly_t*poly2)
464 ArtSVP* svp1 = (ArtSVP*)poly1;
465 ArtSVP* svp2 = (ArtSVP*)poly2;
466 msg("<verbose> Unifying two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
468 ArtSVP* svp = art_svp_union(svp1, svp2);
469 return (gfxpoly_t*)svp;
472 gfxpoly_t* gfxpoly_strokeToPoly(gfxline_t*line, gfxcoord_t width, gfx_capType cap_style, gfx_joinType joint_style, double miterLimit)
474 ArtVpath* vec = gfxline_to_ArtVpath(line, 0);
475 msg("<verbose> Casting gfxline of %d segments to a stroke-polygon", gfxline_len(line));
477 ArtSVP *svp = art_svp_vpath_stroke (vec,
478 (joint_style==gfx_joinMiter)?ART_PATH_STROKE_JOIN_MITER:
479 ((joint_style==gfx_joinRound)?ART_PATH_STROKE_JOIN_ROUND:
480 ((joint_style==gfx_joinBevel)?ART_PATH_STROKE_JOIN_BEVEL:ART_PATH_STROKE_JOIN_BEVEL)),
481 (cap_style==gfx_capButt)?ART_PATH_STROKE_CAP_BUTT:
482 ((cap_style==gfx_capRound)?ART_PATH_STROKE_CAP_ROUND:
483 ((cap_style==gfx_capSquare)?ART_PATH_STROKE_CAP_SQUARE:ART_PATH_STROKE_CAP_SQUARE)),
485 miterLimit, //miter_limit
489 return (gfxpoly_t*)svp;
492 gfxline_t* gfxline_circularToEvenOdd(gfxline_t*line)
494 msg("<verbose> Converting circular-filled gfxline of %d segments to even-odd filled gfxline", gfxline_len(line));
495 ArtSVP* svp = gfxfillToSVP(line, 1);
497 /* TODO: ART_WIND_RULE_POSITIVE means that a shape is visible if
498 positive and negative line segments add up to something positive.
499 I *think* that clockwise fill in PDF is defined in a way, however,
500 that the *last* shape's direction will determine whether something
502 ArtSVP* svp_rewinded;
503 #ifdef ART_USE_NEW_INTERSECTOR
504 ArtSvpWriter * swr = art_svp_writer_rewind_new (ART_WIND_RULE_POSITIVE);
505 art_svp_intersector(svp, swr);
506 svp_rewinded = art_svp_writer_rewind_reap(swr);
509 svp_rewinded = art_svp_rewind_uncrossed(art_svp_uncross(svp),ART_WIND_RULE_POSITIVE);
512 gfxline_t* result = gfxpoly_to_gfxline((gfxpoly_t*)svp_rewinded);
514 art_svp_free(svp_rewinded);
518 gfxpoly_t* gfxpoly_createbox(double x1, double y1,double x2, double y2)
520 ArtVpath *vec = art_new (ArtVpath, 5+1);
521 vec[0].code = ART_MOVETO;
524 vec[1].code = ART_LINETO;
527 vec[2].code = ART_LINETO;
530 vec[3].code = ART_LINETO;
533 vec[4].code = ART_LINETO;
536 vec[5].code = ART_END;
539 ArtSVP *svp = art_svp_from_vpath(vec);
541 return (gfxpoly_t*)svp;
544 void gfxpoly_free(gfxpoly_t*poly)
546 ArtSVP*svp = (ArtSVP*)poly;