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);
242 typedef struct svp_segment_part
247 } svp_segment_part_t;
249 int compare_double(const void*_y1, const void*_y2)
251 const double*y1 = _y1;
252 const double*y2 = _y2;
253 if(*y1<*y2) return -1;
254 if(*y1>*y2) return 1;
258 int compare_seg_start(const void*_s1, const void*_s2)
260 svp_segment_part_t*s1 = *(svp_segment_part_t**)_s1;
261 svp_segment_part_t*s2 = *(svp_segment_part_t**)_s2;
262 if(s1->y1 < s2->y1) return -1;
263 if(s1->y1 > s2->y1) return 1;
267 int compare_seg_end(const void*_s1, const void*_s2)
269 svp_segment_part_t*s1 = *(svp_segment_part_t**)_s1;
270 svp_segment_part_t*s2 = *(svp_segment_part_t**)_s2;
271 if(s1->y2 < s2->y2) return -1;
272 if(s1->y2 > s2->y2) return 1;
276 void clean_svp(ArtSVP*svp)
283 for(t=0;t<svp->n_segs;t++) {
284 ArtSVPSeg* seg = &svp->segs[t];
288 oldpoints += seg->n_points;
289 for(p=0;p<seg->n_points;p++) {
290 ArtPoint* p1 = &seg->points[p];
291 if(!p || lasty!=p1->y) {
292 seg->points[pos] = seg->points[p];
298 newpoints += seg->n_points;
301 oldsegs = svp->n_segs;
302 for(t=0;t<svp->n_segs;t++) {
303 if(svp->segs[t].n_points > 1) {
304 svp->segs[pos++] = svp->segs[t];
308 newsegs = svp->n_segs;
309 if(newsegs < oldsegs || newpoints < oldpoints) {
310 msg("<verbose> Simplified polygon from %d points to %d points, %d to %d segs",
311 oldpoints, newpoints, oldsegs, newsegs);
315 int check_svp(ArtSVP*svp)
317 /* count number of y coordinates and segs */
321 for(t=0;t<svp->n_segs;t++) {
322 if(!svp->segs[t].n_points) {
323 msg("<error> svp contains segment with zero points\n");
326 num_points += svp->segs[t].n_points;
327 num_segs += svp->segs[t].n_points - 1;
330 /* create segs and ys */
331 double*y = malloc(sizeof(double)*num_points);
332 svp_segment_part_t*segs = malloc(sizeof(svp_segment_part_t)*num_segs);
333 svp_segment_part_t**seg_start = malloc(sizeof(svp_segment_part_t*)*num_segs);
334 svp_segment_part_t**seg_end = malloc(sizeof(svp_segment_part_t*)*num_segs);
338 for(t=0;t<svp->n_segs;t++) {
339 ArtSVPSeg* seg = &svp->segs[t];
341 for(p=0;p<seg->n_points;p++) {
342 y[c1++] = seg->points[p].y;
343 assert(c1 <= num_points);
345 for(p=0;p<seg->n_points-1;p++) {
346 ArtPoint* p1 = &seg->points[p];
347 ArtPoint* p2 = &seg->points[p+1];
350 msg("<error> bad svp, y in seg is non-increasing %.16f -> %.16f\n", p1->y, p2->y);
352 segs[num_segs].y1 = p1->y;
353 segs[num_segs].y2 = p2->y;
354 segs[num_segs].active = 0;
355 seg_start[num_segs] = &segs[num_segs];
356 seg_end[num_segs] = &segs[num_segs];
362 qsort(y, num_points, sizeof(double), compare_double);
363 qsort(seg_start, num_segs, sizeof(svp_segment_part_t*), compare_seg_start);
364 qsort(seg_end, num_segs, sizeof(svp_segment_part_t*), compare_seg_end);
366 double lasty = y[0]+1;
369 double bleedy1=0,bleedy2 = 0;
370 for(t=0;t<num_points;t++) {
374 for(s=0;s<num_segs;s++) {
375 if(segs[s].y1==y[t]) {
376 /* segment is starting */
379 } else if(segs[s].y2==y[t]) {
396 msg("<warning> svp bleeds from y=%.16f to y=%.16f (%d/%d active segments)\n",
399 free(y);free(segs);free(seg_start);free(seg_end);
411 void write_svp_postscript(const char*filename, ArtSVP*svp)
415 printf("writing %s\n", filename);
416 FILE*fi = fopen(filename, "wb");
418 double xmin=0,ymin=0,xmax=0,ymax=0;
419 fprintf(fi, "%% begin\n");
420 for (i = 0; i < svp->n_segs; i++) {
421 for (j = 0; j < svp->segs[i].n_points; j++) {
422 double x = svp->segs[i].points[j].x;
423 double y = svp->segs[i].points[j].y;
428 if(x < xmin) xmin = x;
429 if(x > xmax) xmax = x;
430 if(y < ymin) ymin = y;
431 if(y > ymax) ymax = y;
435 if(xmax == xmin) xmax=xmin+1;
436 if(ymax == ymin) ymax=ymin+1;
438 for (i = 0; i < svp->n_segs; i++)
440 fprintf(fi, "%g setgray\n", svp->segs[i].dir ? 0.7 : 0);
441 for (j = 0; j < svp->segs[i].n_points; j++)
443 //fprintf(fi, "%g %g %s\n",
444 // 20 + 550*(svp->segs[i].points[j].x-xmin)/(xmax-xmin),
445 // 820 - 800*(svp->segs[i].points[j].y-ymin)/(ymax-ymin),
446 // j ? "lineto" : "moveto");
447 fprintf(fi, "%.32f %.32f %s\n",
448 svp->segs[i].points[j].x,
449 svp->segs[i].points[j].y,
450 j ? "lineto" : "moveto");
452 fprintf(fi, "stroke\n");
455 fprintf(fi, "showpage\n");
459 void write_vpath_postscript(const char*filename, ArtVpath*path)
461 FILE*fi = fopen(filename, "wb");
463 double xmin=0,ymin=0,xmax=0,ymax=0;
464 fprintf(fi, "%% begin\n");
467 while(p->code != ART_END) {
468 if(p->code == ART_MOVETO || p->code == ART_MOVETO_OPEN) {
470 fprintf(fi, "stroke\n");
472 fprintf(fi, "0.0 setgray\n");
473 fprintf(fi, "%.32f %.32f moveto\n", p->x, p->y);
475 fprintf(fi, "%.32f %.32f lineto\n", p->x, p->y);
480 fprintf(fi, "stroke\n");
481 fprintf(fi, "showpage\n");
485 void write_gfxline_postscript(const char*filename, gfxline_t*line)
487 FILE*fi = fopen(filename, "wb");
489 fprintf(fi, "%% begin\n");
492 if(line->type == gfx_moveTo) {
494 fprintf(fi, "stroke\n");
496 fprintf(fi, "0.0 setgray\n");
497 fprintf(fi, "%.32f %.32f moveto\n", line->x, line->y);
499 fprintf(fi, "%.32f %.32f lineto\n", line->x, line->y);
504 fprintf(fi, "stroke\n");
505 fprintf(fi, "showpage\n");
509 static int vpath_len(ArtVpath*svp)
512 while(svp->code != ART_END) {
519 int gfxline_len(gfxline_t*line)
530 static ArtVpath*pvpath= 0;
531 static int cmppos(const void*_p1, const void*_p2)
535 ArtVpath*v1 = &pvpath[*p1];
536 ArtVpath*v2 = &pvpath[*p2];
539 else if(v1->y > v2->y)
541 else if(v1->x < v2->x)
543 else if(v1->x > v2->x)
549 #define PERTURBATION 2e-3
550 static void my_perturb(ArtVpath*vpath)
553 int len = vpath_len(vpath);
554 int*pos = (int*)malloc(len*sizeof(int));
558 qsort(pos, len, sizeof(int), cmppos);
562 while(t2<len && !cmppos(&pos[t],&pos[t2])) {
566 double dx = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
567 double dy = (PERTURBATION * rand ()) / RAND_MAX - PERTURBATION * 0.5;
570 vpath[pos[s]].x += dx;
571 vpath[pos[s]].y += dy;
579 static ArtSVP* gfxfillToSVP(gfxline_t*line, int perturb)
581 ArtVpath* vec = gfxline_to_ArtVpath(line, 1);
582 msg("<verbose> Casting gfxline of %d segments (%d line segments) to a gfxpoly", gfxline_len(line), vpath_len(vec));
585 //ArtVpath* vec2 = art_vpath_perturb(vec);
590 ArtSVP *svp = art_svp_from_vpath(vec);
597 // double shear = find_shear_value(svp);
598 // gfxline_t*line = gfxpoly_to_gfxline((gfxpoly_t*)svp);
599 // gfxline_t*l = line;
601 // l->y += l->x*shear;
602 // l->sy += l->sx*shear;
605 // svp = (ArtSVP*)gfxpoly_fillToPoly(line);
606 // printf("shearing svp by %.16f\n", shear);
610 // art_svp_free(svp);
611 // shear_svp(result, -shear);
616 extern const ArtSVP* current_svp;
617 extern void art_report_error();
618 extern int art_error_in_intersector;
620 ArtSVP* run_intersector(ArtSVP*svp, ArtWindRule rule)
622 ArtSvpWriter * swr = art_svp_writer_rewind_new(rule);
624 art_svp_intersector(svp, swr);
625 ArtSVP*result = art_svp_writer_rewind_reap(swr);
627 if(!check_svp(result)) {
628 msg("<warning> Error in polygon processing");
629 current_svp = result;
630 art_report_error(); // might set art_error_in_intersector
632 if(art_error_in_intersector) {
633 art_svp_free(result);
634 art_error_in_intersector=0;
640 gfxline_t* gfxpoly_to_gfxline(gfxpoly_t*poly)
642 ArtSVP*svp = (ArtSVP*)poly;
647 msg("<verbose> Casting polygon of %d segments back to gfxline", svp->n_segs);
649 for(t=0;t<svp->n_segs;t++) {
650 size += svp->segs[t].n_points;
653 gfxline_t* lines = (gfxline_t*)rfx_alloc(sizeof(gfxline_t)*size);
655 for(t=0;t<svp->n_segs;t++) {
656 ArtSVPSeg* seg = &svp->segs[t];
658 for(p=0;p<seg->n_points;p++) {
659 lines[pos].type = p==0?gfx_moveTo:gfx_lineTo;
660 ArtPoint* point = &seg->points[p];
661 lines[pos].x = point->x;
662 lines[pos].y = point->y;
663 lines[pos].next = &lines[pos+1];
668 lines[pos-1].next = 0;
675 gfxpoly_t* gfxpoly_fillToPoly(gfxline_t*line)
677 /* I'm not sure whether doing perturbation here is actually
678 a good idea- if that line has been run through the machine
679 several times already, it might be safer to leave it alone,
680 since it should already be in a format libart can handle */
682 ArtSVP* svp = gfxfillToSVP(line, 1);
684 ArtSVP* svp = gfxfillToSVP(line, 0);
689 static int counter = 0;
690 sprintf(filename, "svp%d.ps", counter);
691 write_svp_postscript(filename, svp);
692 sprintf(filename, "gfxline%d.ps", counter);
693 write_gfxline_postscript(filename, line);
696 /* we do xor-filling by default, so dir is always 1
697 (actually for oddeven rewinding it makes no difference, but
701 for(t=0; t<svp->n_segs; t++) {
702 svp->segs[t].dir = 1;
705 /* for some reason, we need to rewind / self-intersect the polygons that gfxfillToSVP
706 returns- art probably uses a different fill mode (circular?) for vpaths */
707 ArtSVP*svp_uncrossed=0;
710 sprintf(filename, "svp%d_in.ps", counter);
711 write_svp_postscript(filename, svp);
715 svp_uncrossed = run_intersector(svp, ART_WIND_RULE_ODDEVEN);
720 return (gfxpoly_t*)svp;
723 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*poly1, gfxpoly_t*poly2)
727 static int counter = 0;
729 ArtSVP* svp1 = (ArtSVP*)poly1;
730 ArtSVP* svp2 = (ArtSVP*)poly2;
731 msg("<verbose> Intersecting two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
735 sprintf(filename, "isvp%d_src1.ps", counter);
736 write_svp_postscript(filename, svp1);
737 sprintf(filename, "isvp%d_src2.ps", counter);
738 write_svp_postscript(filename, svp2);
741 ArtSVP* svp3 = art_svp_merge (svp1, svp2);
744 sprintf(filename, "isvp%d_src.ps", counter);
745 write_svp_postscript(filename, svp3);
748 //write_svp_postscript("svp.ps", svp3);
749 ArtSVP*svp_new = run_intersector(svp3, ART_WIND_RULE_INTERSECT);
751 art_free (svp3); /* shallow free because svp3 contains shared segments */
754 sprintf(filename, "isvp%d.ps", counter);
755 write_svp_postscript(filename, svp_new);
760 //write_svp_postscript("svp_new.ps", svp_new);
762 return (gfxpoly_t*)svp_new;
765 gfxpoly_t* gfxpoly_union(gfxpoly_t*poly1, gfxpoly_t*poly2)
767 ArtSVP* svp1 = (ArtSVP*)poly1;
768 ArtSVP* svp2 = (ArtSVP*)poly2;
769 msg("<verbose> Unifying two polygons of %d and %d segments", svp1->n_segs, svp2->n_segs);
771 ArtSVP* svp = art_svp_union(svp1, svp2);
772 return (gfxpoly_t*)svp;
775 gfxpoly_t* gfxpoly_strokeToPoly(gfxline_t*line, gfxcoord_t width, gfx_capType cap_style, gfx_joinType joint_style, double miterLimit)
777 ArtVpath* vec = gfxline_to_ArtVpath(line, 0);
778 msg("<verbose> Casting gfxline of %d segments to a stroke-polygon", gfxline_len(line));
780 ArtVpath* vec2 = art_vpath_perturb(vec);
784 ArtSVP *svp = art_svp_vpath_stroke (vec,
785 (joint_style==gfx_joinMiter)?ART_PATH_STROKE_JOIN_MITER:
786 ((joint_style==gfx_joinRound)?ART_PATH_STROKE_JOIN_ROUND:
787 ((joint_style==gfx_joinBevel)?ART_PATH_STROKE_JOIN_BEVEL:ART_PATH_STROKE_JOIN_BEVEL)),
788 (cap_style==gfx_capButt)?ART_PATH_STROKE_CAP_BUTT:
789 ((cap_style==gfx_capRound)?ART_PATH_STROKE_CAP_ROUND:
790 ((cap_style==gfx_capSquare)?ART_PATH_STROKE_CAP_SQUARE:ART_PATH_STROKE_CAP_SQUARE)),
792 miterLimit, //miter_limit
796 return (gfxpoly_t*)svp;
799 gfxline_t* gfxline_circularToEvenOdd(gfxline_t*line)
801 msg("<verbose> Converting circular-filled gfxline of %d segments to even-odd filled gfxline", gfxline_len(line));
802 ArtSVP* svp = gfxfillToSVP(line, 1);
804 /* TODO: ART_WIND_RULE_POSITIVE means that a shape is visible if
805 positive and negative line segments add up to something positive.
806 I *think* that clockwise fill in PDF is defined in a way, however,
807 that the *last* shape's direction will determine whether something
809 ArtSVP* svp_rewinded;
811 svp_rewinded = run_intersector(svp, ART_WIND_RULE_POSITIVE);
817 gfxline_t* result = gfxpoly_to_gfxline((gfxpoly_t*)svp_rewinded);
819 art_svp_free(svp_rewinded);
823 gfxpoly_t* gfxpoly_createbox(double x1, double y1,double x2, double y2)
825 ArtVpath *vec = art_new (ArtVpath, 5+1);
826 vec[0].code = ART_MOVETO;
829 vec[1].code = ART_LINETO;
832 vec[2].code = ART_LINETO;
835 vec[3].code = ART_LINETO;
838 vec[4].code = ART_LINETO;
841 vec[5].code = ART_END;
844 ArtSVP *svp = art_svp_from_vpath(vec);
846 return (gfxpoly_t*)svp;
849 void gfxpoly_free(gfxpoly_t*poly)
851 ArtSVP*svp = (ArtSVP*)poly;