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"
30 #include "art/art_svp_ops.h"
40 static ArtVpath* gfxline_to_ArtVpath(gfxline_t*line, char fill)
47 /* factor which determines into how many line fragments a spline is converted */
48 double subfraction = 2.4;//0.3
52 if(l2->type == gfx_moveTo) {
54 } else if(l2->type == gfx_lineTo) {
56 } else if(l2->type == gfx_splineTo) {
57 int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
68 vec = art_new (ArtVpath, len+1);
73 if(l2->type == gfx_moveTo) {
74 vec[pos].code = ART_MOVETO_OPEN;
79 } else if(l2->type == gfx_lineTo) {
80 vec[pos].code = ART_LINETO;
85 } else if(l2->type == gfx_splineTo) {
87 int parts = (int)(sqrt(fabs(l2->x-2*l2->sx+x) + fabs(l2->y-2*l2->sy+y))*subfraction);
89 double stepsize = 1.0/parts;
90 for(i=0;i<=parts;i++) {
91 double t = (double)i*stepsize;
92 vec[pos].code = ART_LINETO;
93 vec[pos].x = l2->x*t*t + 2*l2->sx*t*(1-t) + x*(1-t)*(1-t);
94 vec[pos].y = l2->y*t*t + 2*l2->sy*t*(1-t) + y*(1-t)*(1-t);
103 vec[pos++].code = ART_END;
107 /* Fix "dotted" lines. Those are lines where singular points are created
108 by a moveto x,y lineto x,y combination. We "fix" these by shifting the
109 point in the lineto a little bit to the right
110 These should only occur in strokes, not in fills, so do this only
111 when we know we're not filling.
114 for(t=0;vec[t].code!=ART_END;t++) {
115 if(t>0 && (vec[t-1].code==ART_MOVETO_OPEN || vec[t-1].code==ART_MOVETO)
116 && vec[t].code==ART_LINETO && vec[t+1].code!=ART_LINETO &&
117 vec[t-1].x == vec[t].x &&
118 vec[t-1].y == vec[t].y) {
124 /* Find adjacent identical points. If an ajdacent pair of identical
125 points is found, the second is removed.
126 So moveto x,y lineto x,y becomes moveto x,y
127 lineto x,y lineto x,y becomes lineto x,y
128 lineto x,y moveto x,y becomes lineto x,y
129 moveto x,y moveto x,y becomes moveto x,y
130 lineto x,y lineto x2,y2 becomes lineto x2,y2 (if dir(x,y) ~= dir(x2,y2))
136 if(vec[pos].code == ART_END) {
137 vec[outpos++] = vec[pos++];
141 char samedir = 0, samepoint = 0;
143 double dx = vec[pos].x-vec[pos-1].x;
144 double dy = vec[pos].y-vec[pos-1].y;
145 /*if(pos<len-1 && vec[pos].code == ART_LINETO && vec[pos+1].code == ART_LINETO) {
146 double dx2 = vec[pos+1].x-vec[pos].x;
147 double dy2 = vec[pos+1].y-vec[pos].y;
148 if(fabs(dx*dy2 - dy*dx2) < 0.0001 && dx*dx2 + dy*dy2 >= 0) {
152 if(fabs(dx) + fabs(dy) < 0.0001) {
156 if(!samepoint && !samedir) {
157 vec[outpos++] = vec[pos++];
166 static void shear_svp(ArtSVP*svp, double v)
168 /* do a "shearing on the polygon. We do this to eliminate all
169 horizontal lines (which libart can't handle properly, even though
173 for(t=0;t<svp->n_segs;t++) {
174 ArtSVPSeg* seg = &svp->segs[t];
176 for(s=0;s<seg->n_points;s++) {
177 ArtPoint* point = &seg->points[s];
178 point->y += point->x*v;
183 static double find_shear_value(ArtSVP*svp)
185 /* We try random values until we find one
186 where there's no slope below a given value, or if that fails,
187 at least no slope of 0 */
194 for(t=0;t<svp->n_segs;t++) {
195 ArtSVPSeg* seg = &svp->segs[t];
197 for(s=0;s<seg->n_points-1;s++) {
198 ArtPoint* p1 = &seg->points[s];
199 ArtPoint* p2 = &seg->points[s+1];
200 double dx = p2->x - p1->x;
201 double dy = p2->y - p1->y;
207 if(tries<100 && dx && fabs(dy / dx) < 1e-5) {
217 v = lrand48() / 2000000000.0;
223 void show_path(ArtSVP*path)
226 printf("Segments: %d\n", path->n_segs);
227 for(t=0;t<path->n_segs;t++) {
228 ArtSVPSeg* seg = &path->segs[t];
229 printf("Segment %d: %d points, %s, BBox: (%f,%f,%f,%f)\n",
230 t, seg->n_points, seg->dir==0?"UP ":"DOWN",
231 seg->bbox.x0, seg->bbox.y0, seg->bbox.x1, seg->bbox.y1);
233 for(p=0;p<seg->n_points;p++) {
234 ArtPoint* point = &seg->points[p];
235 printf(" (%f,%f)\n", point->x, point->y);
241 void check_svp(ArtSVP*svp)
244 for(t=0;t<svp->n_segs;t++) {
245 ArtSVPSeg* seg = &svp->segs[t];
247 for(p=0;p<seg->n_points-1;p++) {
248 ArtPoint* p1 = &seg->points[p];
249 ArtPoint* p2 = &seg->points[p+1];
251 fprintf(stderr, "bad svp, y in seg %08x is non-increasing\n");
258 void write_svp_postscript(const char*filename, ArtSVP*svp)
260 printf("writing %s\n", filename);
261 FILE*fi = fopen(filename, "wb");
263 double xmin=0,ymin=0,xmax=0,ymax=0;
264 fprintf(fi, "%% begin\n");
265 for (i = 0; i < svp->n_segs; i++) {
266 for (j = 0; j < svp->segs[i].n_points; j++) {
267 double x = svp->segs[i].points[j].x;
268 double y = svp->segs[i].points[j].y;
273 if(x < xmin) xmin = x;
274 if(x > xmax) xmax = x;
275 if(y < ymin) ymin = y;
276 if(y > ymax) ymax = y;
280 if(xmax == xmin) xmax=xmin+1;
281 if(ymax == ymin) ymax=ymin+1;
283 for (i = 0; i < svp->n_segs; i++)
285 fprintf(fi, "%g setgray\n", svp->segs[i].dir ? 0.7 : 0);
286 for (j = 0; j < svp->segs[i].n_points; j++)
288 //fprintf(fi, "%g %g %s\n",
289 // 20 + 550*(svp->segs[i].points[j].x-xmin)/(xmax-xmin),
290 // 820 - 800*(svp->segs[i].points[j].y-ymin)/(ymax-ymin),
291 // j ? "lineto" : "moveto");
292 fprintf(fi, "%.32f %.32f %s\n",
293 svp->segs[i].points[j].x,
294 svp->segs[i].points[j].y,
295 j ? "lineto" : "moveto");
297 fprintf(fi, "stroke\n");
300 fprintf(fi, "showpage\n");
304 void write_vpath_postscript(const char*filename, ArtVpath*path)
306 FILE*fi = fopen(filename, "wb");
308 double xmin=0,ymin=0,xmax=0,ymax=0;
309 fprintf(fi, "%% begin\n");
312 while(p->code != ART_END) {
313 if(p->code == ART_MOVETO || p->code == ART_MOVETO_OPEN) {
315 fprintf(fi, "stroke\n");
317 fprintf(fi, "0.0 setgray\n");
318 fprintf(fi, "%.32f %.32f moveto\n", p->x, p->y);
320 fprintf(fi, "%.32f %.32f lineto\n", p->x, p->y);
325 fprintf(fi, "stroke\n");
326 fprintf(fi, "showpage\n");
330 void write_gfxline_postscript(const char*filename, gfxline_t*line)
332 FILE*fi = fopen(filename, "wb");
334 fprintf(fi, "%% begin\n");
337 if(line->type == gfx_moveTo) {
339 fprintf(fi, "stroke\n");
341 fprintf(fi, "0.0 setgray\n");
342 fprintf(fi, "%.32f %.32f moveto\n", line->x, line->y);
344 fprintf(fi, "%.32f %.32f lineto\n", line->x, line->y);
349 fprintf(fi, "stroke\n");
350 fprintf(fi, "showpage\n");
354 static int vpath_len(ArtVpath*svp)
357 while(svp->code != ART_END) {
364 int gfxline_len(gfxline_t*line)
375 static ArtVpath*pvpath= 0;
376 static int cmppos(const void*_p1, const void*_p2)
380 ArtVpath*v1 = &pvpath[*p1];
381 ArtVpath*v2 = &pvpath[*p2];
384 else if(v1->y > v2->y)
386 else if(v1->x < v2->x)
388 else if(v1->x > v2->x)
394 #define PERTURBATION 2e-3
395 static void my_perturb(ArtVpath*vpath)
398 int len = vpath_len(vpath);
399 int*pos = (int*)malloc(len*sizeof(int));
403 qsort(pos, len, sizeof(int), cmppos);
407 while(t2<len && !cmppos(&pos[t],&pos[t2])) {
411 double dx = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
412 double dy = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
415 vpath[pos[s]].x += dx;
416 vpath[pos[s]].y += dy;
424 static ArtSVP* gfxfillToSVP(gfxline_t*line, int perturb)
426 ArtVpath* vec = gfxline_to_ArtVpath(line, 1);
427 msg("<verbose> Casting gfxline of %d segments (%d line segments) to a gfxpoly", gfxline_len(line), vpath_len(vec));
430 //ArtVpath* vec2 = art_vpath_perturb(vec);
435 ArtSVP *svp = art_svp_from_vpath(vec);
441 ArtSVP* run_intersector(ArtSVP*svp, ArtWindRule rule)
443 ArtSvpWriter * swr = art_svp_writer_rewind_new(rule);
446 double shear = find_shear_value(svp);
447 gfxline_t*line = gfxpoly_to_gfxline((gfxpoly_t*)svp);
451 l->sy += l->sx*shear;
454 svp = (ArtSVP*)gfxpoly_fillToPoly(line);
455 printf("shearing svp by %.16f\n", shear);
458 art_svp_intersector(svp, swr);
459 ArtSVP*result = art_svp_writer_rewind_reap(swr);
464 shear_svp(result, -shear);
471 gfxline_t* gfxpoly_to_gfxline(gfxpoly_t*poly)
473 ArtSVP*svp = (ArtSVP*)poly;
478 msg("<verbose> Casting polygon of %d segments back to gfxline", svp->n_segs);
480 for(t=0;t<svp->n_segs;t++) {
481 size += svp->segs[t].n_points;
484 gfxline_t* lines = (gfxline_t*)rfx_alloc(sizeof(gfxline_t)*size);
486 for(t=0;t<svp->n_segs;t++) {
487 ArtSVPSeg* seg = &svp->segs[t];
489 for(p=0;p<seg->n_points;p++) {
490 lines[pos].type = p==0?gfx_moveTo:gfx_lineTo;
491 ArtPoint* point = &seg->points[p];
492 lines[pos].x = point->x;
493 lines[pos].y = point->y;
494 lines[pos].next = &lines[pos+1];
499 lines[pos-1].next = 0;
506 gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line)
508 /* I'm not sure whether doing perturbation here is actually
509 a good idea- if that line has been run through the machine
510 several times already, it might be safer to leave it alone,
511 since it should already be in a format libart can handle */
513 ArtSVP* svp = gfxfillToSVP(line, 1);
515 ArtSVP* svp = gfxfillToSVP(line, 0);
520 static int counter = 0;
521 sprintf(filename, "svp%d.ps", counter);
522 write_svp_postscript(filename, svp);
523 sprintf(filename, "gfxline%d.ps", counter);
524 write_gfxline_postscript(filename, line);
527 /* we do xor-filling by default, so dir is always 1
528 (actually for oddeven rewinding it makes no difference, but
532 for(t=0; t<svp->n_segs; t++) {
533 svp->segs[t].dir = 1;
536 /* for some reason, we need to rewind / self-intersect the polygons that gfxfillToSVP
537 returns- art probably uses a different fill mode (circular?) for vpaths */
538 ArtSVP*svp_uncrossed=0;
541 sprintf(filename, "svp%d_in.ps", counter);
542 write_svp_postscript(filename, svp);
546 svp_uncrossed = run_intersector(svp, ART_WIND_RULE_ODDEVEN);
551 return (gfxpoly_t*)svp;
554 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*poly1, gfxpoly_t*poly2)
558 static int counter = 0;
560 ArtSVP* svp1 = (ArtSVP*)poly1;
561 ArtSVP* svp2 = (ArtSVP*)poly2;
562 msg("<verbose> Intersecting two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
566 sprintf(filename, "isvp%d_src1.ps", counter);
567 write_svp_postscript(filename, svp1);
568 sprintf(filename, "isvp%d_src2.ps", counter);
569 write_svp_postscript(filename, svp2);
572 ArtSVP* svp3 = art_svp_merge (svp1, svp2);
575 sprintf(filename, "isvp%d_src.ps", counter);
576 write_svp_postscript(filename, svp3);
579 //write_svp_postscript("svp.ps", svp3);
580 ArtSVP*svp_new = run_intersector(svp3, ART_WIND_RULE_INTERSECT);
582 art_free (svp3); /* shallow free because svp3 contains shared segments */
585 sprintf(filename, "isvp%d.ps", counter);
586 write_svp_postscript(filename, svp_new);
591 //write_svp_postscript("svp_new.ps", svp_new);
593 return (gfxpoly_t*)svp_new;
596 gfxpoly_t* gfxpoly_union(gfxpoly_t*poly1, gfxpoly_t*poly2)
598 ArtSVP* svp1 = (ArtSVP*)poly1;
599 ArtSVP* svp2 = (ArtSVP*)poly2;
600 msg("<verbose> Unifying two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
602 ArtSVP* svp = art_svp_union(svp1, svp2);
603 return (gfxpoly_t*)svp;
606 gfxpoly_t* gfxpoly_strokeToPoly(gfxline_t*line, gfxcoord_t width, gfx_capType cap_style, gfx_joinType joint_style, double miterLimit)
608 ArtVpath* vec = gfxline_to_ArtVpath(line, 0);
609 msg("<verbose> Casting gfxline of %d segments to a stroke-polygon", gfxline_len(line));
611 ArtVpath* vec2 = art_vpath_perturb(vec);
615 ArtSVP *svp = art_svp_vpath_stroke (vec,
616 (joint_style==gfx_joinMiter)?ART_PATH_STROKE_JOIN_MITER:
617 ((joint_style==gfx_joinRound)?ART_PATH_STROKE_JOIN_ROUND:
618 ((joint_style==gfx_joinBevel)?ART_PATH_STROKE_JOIN_BEVEL:ART_PATH_STROKE_JOIN_BEVEL)),
619 (cap_style==gfx_capButt)?ART_PATH_STROKE_CAP_BUTT:
620 ((cap_style==gfx_capRound)?ART_PATH_STROKE_CAP_ROUND:
621 ((cap_style==gfx_capSquare)?ART_PATH_STROKE_CAP_SQUARE:ART_PATH_STROKE_CAP_SQUARE)),
623 miterLimit, //miter_limit
627 return (gfxpoly_t*)svp;
630 gfxline_t* gfxline_circularToEvenOdd(gfxline_t*line)
632 msg("<verbose> Converting circular-filled gfxline of %d segments to even-odd filled gfxline", gfxline_len(line));
633 ArtSVP* svp = gfxfillToSVP(line, 1);
635 /* TODO: ART_WIND_RULE_POSITIVE means that a shape is visible if
636 positive and negative line segments add up to something positive.
637 I *think* that clockwise fill in PDF is defined in a way, however,
638 that the *last* shape's direction will determine whether something
640 ArtSVP* svp_rewinded;
642 svp_rewinded = run_intersector(svp, ART_WIND_RULE_POSITIVE);
644 gfxline_t* result = gfxpoly_to_gfxline((gfxpoly_t*)svp_rewinded);
646 art_svp_free(svp_rewinded);
650 gfxpoly_t* gfxpoly_createbox(double x1, double y1,double x2, double y2)
652 ArtVpath *vec = art_new (ArtVpath, 5+1);
653 vec[0].code = ART_MOVETO;
656 vec[1].code = ART_LINETO;
659 vec[2].code = ART_LINETO;
662 vec[3].code = ART_LINETO;
665 vec[4].code = ART_LINETO;
668 vec[5].code = ART_END;
671 ArtSVP *svp = art_svp_from_vpath(vec);
673 return (gfxpoly_t*)svp;
676 void gfxpoly_free(gfxpoly_t*poly)
678 ArtSVP*svp = (ArtSVP*)poly;