14 static gfxpoly_t*current_polygon = 0;
15 void gfxpoly_fail(char*expr, char*file, int line, const char*function)
17 if(!current_polygon) {
18 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
22 void*md5 = initialize_md5();
25 gfxpolystroke_t*stroke = current_polygon->strokes;
26 for(;stroke;stroke=stroke->next) {
27 for(t=0;t<stroke->num_points;t++) {
28 update_md5(md5, (unsigned char*)&stroke->points[t].x, sizeof(stroke->points[t].x));
29 update_md5(md5, (unsigned char*)&stroke->points[t].y, sizeof(stroke->points[t].y));
33 char filename[32+4+1];
35 sprintf(filename, "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x.ps",
36 h[0],h[1],h[2],h[3],h[4],h[5],h[6],h[7],h[8],h[9],h[10],h[11],h[12],h[13],h[14],h[15]);
38 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
39 fprintf(stderr, "I'm saving a debug file \"%s\" to the current directory.\n", filename);
41 gfxpoly_save(current_polygon, filename);
45 static char point_equals(const void*o1, const void*o2)
47 const point_t*p1 = o1;
48 const point_t*p2 = o2;
49 return p1->x == p2->x && p1->y == p2->y;
51 static unsigned int point_hash(const void*o)
56 static void* point_dup(const void*o)
59 point_t*n = malloc(sizeof(point_t));
64 static void point_free(void*o)
78 typedef struct _event {
85 /* compare_events_simple differs from compare_events in that it schedules
86 events from left to right regardless of type. It's only used in horizontal
87 processing, in order to get an x-wise sorting of the current scanline */
88 static inline int compare_events_simple(const void*_a,const void*_b)
90 event_t* a = (event_t*)_a;
91 event_t* b = (event_t*)_b;
92 int d = b->p.y - a->p.y;
99 static inline int compare_events(const void*_a,const void*_b)
101 event_t* a = (event_t*)_a;
102 event_t* b = (event_t*)_b;
103 int d = b->p.y - a->p.y;
105 /* we need to schedule end after intersect (so that a segment about
106 to end has a chance to tear up a few other segs first) and start
107 events after end (in order not to confuse the intersection check, which
108 assumes there's an actual y overlap between active segments, and
109 because ending segments in the active list make it difficult to insert
110 starting segments at the right position)).
111 Horizontal lines come last, because the only purpose
112 they have is to create snapping coordinates for the segments (still)
113 existing in this scanline.
115 d = b->type - a->type;
119 /* I don't see any reason why we would need to order by x- at least as long
120 as we do horizontal lines in a seperate pass */
121 //d = b->p.x - a->p.x;
125 #define COMPARE_EVENTS(x,y) (compare_events(x,y)>0)
126 #define COMPARE_EVENTS_SIMPLE(x,y) (compare_events_simple(x,y)>0)
127 HEAP_DEFINE(queue,event_t,COMPARE_EVENTS);
128 HEAP_DEFINE(hqueue,event_t,COMPARE_EVENTS_SIMPLE);
130 typedef struct _horizontal {
138 typedef struct _horizdata {
144 typedef struct _status {
151 windcontext_t*context;
152 segment_t*ending_segments;
156 gfxpolystroke_t*strokes;
158 dict_t*seen_crossings; //list of crossing we saw so far
159 dict_t*intersecting_segs; //list of segments intersecting in this scanline
160 dict_t*segs_with_point; //lists of segments that received a point in this scanline
165 int gfxpoly_num_segments(gfxpoly_t*poly)
167 gfxpolystroke_t*stroke = poly->strokes;
169 for(;stroke;stroke=stroke->next) {
174 int gfxpoly_size(gfxpoly_t*poly)
178 gfxpolystroke_t*stroke = poly->strokes;
179 for(;stroke;stroke=stroke->next) {
180 edges += stroke->num_points-1;
185 char gfxpoly_check(gfxpoly_t*poly, char updown)
187 current_polygon = poly;
188 dict_t*d1 = dict_new2(&point_type);
189 dict_t*d2 = dict_new2(&point_type);
191 gfxpolystroke_t*stroke = poly->strokes;
192 for(;stroke;stroke=stroke->next) {
193 /* In order to not confuse the fill/wind logic, existing segments must have
194 a non-zero edge style */
197 /* put all the segments into dictionaries so that we can check
198 that the endpoint multiplicity is two */
199 for(s=0;s<stroke->num_points;s++) {
200 point_t p = stroke->points[s];
201 int num_xor = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
202 int num_circ = (s>=1 && s<stroke->num_points-1)?0:(s==0?1:-1);
203 if(stroke->dir==DIR_UP)
206 if(!dict_contains(d1, &p)) {
207 dict_put(d1, &p, (void*)(ptroff_t)num_xor);
209 assert(!dict_contains(d2, &p));
210 dict_put(d2, &p, (void*)(ptroff_t)num_circ);
213 int count = (ptroff_t)dict_lookup(d1, &p);
216 dict_put(d1, &p, (void*)(ptroff_t)count);
219 assert(dict_contains(d2, &p));
220 count = (ptroff_t)dict_lookup(d2, &p);
223 dict_put(d2, &p, (void*)(ptroff_t)count);
228 DICT_ITERATE_ITEMS(d1, point_t*, p1, void*, c1) {
229 int count = (ptroff_t)c1;
231 fprintf(stderr, "Error: Point (%.2f,%.2f) occurs %d times\n", p1->x * poly->gridsize, p1->y * poly->gridsize, count);
239 DICT_ITERATE_ITEMS(d2, point_t*, p2, void*, c2) {
240 int count = (ptroff_t)c2;
242 if(count>0) fprintf(stderr, "Error: Point (%d,%d) has %d more incoming than outgoing segments\n", p2->x, p2->y, count);
243 if(count<0) fprintf(stderr, "Error: Point (%d,%d) has %d more outgoing than incoming segments\n", p2->x, p2->y, -count);
253 void gfxpoly_dump(gfxpoly_t*poly)
256 double g = poly->gridsize;
257 fprintf(stderr, "polyon %p (gridsize: %.2f)\n", poly, poly->gridsize);
258 gfxpolystroke_t*stroke = poly->strokes;
259 for(;stroke;stroke=stroke->next) {
260 fprintf(stderr, "%11p", stroke);
261 if(stroke->dir==DIR_UP) {
262 for(s=stroke->num_points-1;s>=1;s--) {
263 point_t a = stroke->points[s];
264 point_t b = stroke->points[s-1];
265 fprintf(stderr, "%s (%.2f,%.2f) -> (%.2f,%.2f)%s%s\n", s!=stroke->num_points-1?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
266 s==1?"]":"", a.y==b.y?"H":"");
269 for(s=0;s<stroke->num_points-1;s++) {
270 point_t a = stroke->points[s];
271 point_t b = stroke->points[s+1];
272 fprintf(stderr, "%s (%.2f,%.2f) -> (%.2f,%.2f)%s%s\n", s?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
273 s==stroke->num_points-2?"]":"", a.y==b.y?"H":"");
279 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
281 FILE*fi = fopen(filename, "wb");
282 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
283 fprintf(fi, "%% begin\n");
285 gfxpolystroke_t*stroke = poly->strokes;
286 for(;stroke;stroke=stroke->next) {
287 fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
288 point_t p = stroke->points[0];
289 fprintf(fi, "%d %d moveto\n", p.x, p.y);
290 for(s=1;s<stroke->num_points;s++) {
291 p = stroke->points[s];
292 fprintf(fi, "%d %d lineto\n", p.x, p.y);
294 fprintf(fi, "stroke\n");
296 fprintf(fi, "showpage\n");
300 void gfxpoly_save_arrows(gfxpoly_t*poly, const char*filename)
302 FILE*fi = fopen(filename, "wb");
303 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
304 fprintf(fi, "%% begin\n");
306 double l = 5.0 / poly->gridsize;
307 double g = poly->gridsize;
308 gfxpolystroke_t*stroke = poly->strokes;
309 for(;stroke;stroke=stroke->next) {
310 fprintf(fi, "%g setgray\n", 0);
312 int s = stroke->dir==DIR_UP?stroke->num_points-1:0;
313 int end = stroke->dir==DIR_UP?-1:stroke->num_points;
314 int dir = stroke->dir==DIR_UP?-1:1;
316 point_t p = stroke->points[s];
319 fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
320 for(;s!=end;s+=dir) {
321 p = stroke->points[s];
324 double d = sqrt(lx*lx+ly*ly);
328 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
329 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 + (ly*d))*g,
330 (p.y - ly*d2 - (lx*d))*g);
331 fprintf(fi, "%f %f lineto\n", p.x * g, p.y * g);
332 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 - (ly*d))*g,
333 (p.y - ly*d2 + (lx*d))*g);
334 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
335 fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
338 fprintf(fi, "stroke\n");
340 fprintf(fi, "showpage\n");
344 inline static event_t* event_new()
346 event_t*e = rfx_calloc(sizeof(event_t));
349 inline static void event_free(event_t*e)
354 static void event_dump(status_t*status, event_t*e)
356 if(e->type == EVENT_HORIZONTAL) {
357 fprintf(stderr, "Horizontal [%d] (%.2f,%.2f) -> (%.2f,%.2f)\n", (int)e->s1->nr,
358 e->s1->a.x * status->gridsize, e->s1->a.y * status->gridsize, e->s1->b.x * status->gridsize, e->s1->b.y * status->gridsize);
359 } else if(e->type == EVENT_START) {
360 fprintf(stderr, "event: segment [%d] starts at (%.2f,%.2f)\n", (int)e->s1->nr,
361 e->p.x * status->gridsize, e->p.y * status->gridsize);
362 } else if(e->type == EVENT_END) {
363 fprintf(stderr, "event: segment [%d] ends at (%.2f,%.2f)\n", (int)e->s1->nr,
364 e->p.x * status->gridsize, e->p.y * status->gridsize);
365 } else if(e->type == EVENT_CROSS) {
366 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%.2f,%.2f)\n", (int)e->s1->nr, (int)e->s2->nr,
367 e->p.x * status->gridsize, e->p.y * status->gridsize);
373 static inline int32_t max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
374 static inline int32_t min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
376 static void segment_dump(segment_t*s)
378 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", (int)s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
379 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f fs=%p\n", s->delta.x, s->delta.y, s->k,
380 (double)s->delta.x / s->delta.y, s->fs);
383 static void segment_init(segment_t*s, int32_t x1, int32_t y1, int32_t x2, int32_t y2, int polygon_nr, segment_dir_t dir)
389 /* We need to make sure horizontal segments always go from left to right.
390 "up/down" for horizontal segments is handled by "rotating"
391 them 90° anticlockwise in screen coordinates (tilt your head to
397 int32_t x = x1;x1=x2;x2=x;
398 int32_t y = y1;y1=y2;y2=y;
405 s->k = (double)x1*y2-(double)x2*y1;
406 s->left = s->right = 0;
409 s->minx = min32(x1,x2);
410 s->maxx = max32(x1,x2);
413 s->polygon_nr = polygon_nr;
414 static int segment_count=0;
415 s->nr = segment_count++;
418 /* notice: on some systems (with some compilers), for the line
419 (1073741823,-1073741824)->(1073741823,1073741823)
420 we get LINE_EQ(s->a, s) == 1.
421 That's why we now clamp to 26 bit.
423 assert(LINE_EQ(s->a, s) == 0);
424 assert(LINE_EQ(s->b, s) == 0);
426 /* check that all signs are in order:
434 p.x = min32(s->a.x, s->b.x);
435 assert(LINE_EQ(p, s) <= 0);
436 p.x = max32(s->a.x, s->b.x);
437 assert(LINE_EQ(p, s) >= 0);
440 #ifndef DONT_REMEMBER_CROSSINGS
441 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
445 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
447 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
448 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
452 static void segment_clear(segment_t*s)
454 #ifndef DONT_REMEMBER_CROSSINGS
455 dict_clear(&s->scheduled_crossings);
458 static void segment_destroy(segment_t*s)
464 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
469 /* we need to queue multiple segments at once because we need to process start events
470 before horizontal events */
471 while(pos < stroke->num_points-1) {
472 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
473 s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
481 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %p, %d more to come)\n",
482 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
483 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
485 event_t* e = event_new();
486 e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
491 if(queue) queue_put(queue, e);
492 else hqueue_put(hqueue, e);
494 if(e->type != EVENT_HORIZONTAL) {
504 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
507 gfxpolystroke_t*stroke = p->strokes;
508 for(;stroke;stroke=stroke->next) {
509 assert(stroke->num_points > 1);
513 for(s=0;s<stroke->num_points-1;s++) {
514 assert(stroke->points[s].y <= stroke->points[s+1].y);
517 advance_stroke(queue, hqueue, stroke, polygon_nr, 0);
521 static void schedule_endpoint(status_t*status, segment_t*s)
523 // schedule end point of segment
524 assert(s->b.y > status->y);
525 event_t*e = event_new();
530 queue_put(&status->queue, e);
533 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
535 /* the code that's required (and the checks you can perform) before
536 it can be said with 100% certainty that we indeed have a valid crossing
537 amazes me every time. -mk */
540 assert(s1->right == s2);
541 assert(s2->left == s1);
542 int32_t miny1 = min32(s1->a.y,s1->b.y);
543 int32_t maxy1 = max32(s1->a.y,s1->b.y);
544 int32_t miny2 = min32(s2->a.y,s2->b.y);
545 int32_t maxy2 = max32(s2->a.y,s2->b.y);
546 int32_t minx1 = min32(s1->a.x,s1->b.x);
547 int32_t minx2 = min32(s2->a.x,s2->b.x);
548 int32_t maxx1 = max32(s1->a.x,s1->b.x);
549 int32_t maxx2 = max32(s2->a.x,s2->b.x);
550 /* check that precomputation is sane */
551 assert(minx1 == s1->minx && minx2 == s2->minx);
552 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
553 /* both segments are active, so this can't happen */
554 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
555 /* we know that right now, s2 is to the right of s1, so there's
556 no way the complete bounding box of s1 is to the right of s1 */
557 assert(!(s1->minx > s2->maxx));
558 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
561 if(s1->maxx <= s2->minx) {
563 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
565 /* bounding boxes don't intersect */
569 #ifndef DONT_REMEMBER_CROSSINGS
570 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
571 /* FIXME: this whole segment hashing thing is really slow */
573 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
574 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
575 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
578 return; // we already know about this one
582 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
585 // lines are exactly on top of each other (ignored)
587 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
592 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
594 /* lines are parallel */
599 double asign2 = LINE_EQ(s1->a, s2);
601 // segment1 touches segment2 in a single point (ignored)
603 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
607 double bsign2 = LINE_EQ(s1->b, s2);
609 // segment1 touches segment2 in a single point (ignored)
611 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
616 if(asign2<0 && bsign2<0) {
617 // segment1 is completely to the left of segment2
619 fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s1->nr, s2->nr);
623 if(asign2>0 && bsign2>0) {
624 // segment1 is completely to the right of segment2
625 #ifndef DONT_REMEMBER_CROSSINGS
629 fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s2->nr, s1->nr);
634 double asign1 = LINE_EQ(s2->a, s1);
636 // segment2 touches segment1 in a single point (ignored)
638 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
642 double bsign1 = LINE_EQ(s2->b, s1);
644 // segment2 touches segment1 in a single point (ignored)
646 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
651 if(asign1<0 && bsign1<0) {
652 // segment2 is completely to the left of segment1
653 #ifndef DONT_REMEMBER_CROSSINGS
657 fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s1->nr, s2->nr);
661 if(asign1>0 && bsign1>0) {
662 // segment2 is completely to the right of segment1
664 fprintf(stderr, "[%d] doesn't intersect with [%d] because: [%d] is completely to the left of [%d]\n", s1->nr, s2->nr, s2->nr, s1->nr);
669 #ifdef DONT_REMEMBER_CROSSINGS
670 /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
671 there's not way s2 would be to the left of s1 otherwise */
672 if(asign1<0 && bsign1>0) return;
673 if(asign2>0 && bsign2<0) return;
676 assert(!(asign1<0 && bsign1>0));
677 assert(!(asign2>0 && bsign2<0));
679 /* TODO: should we precompute these? */
680 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
681 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
684 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
685 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
687 assert(p.y >= status->y);
689 assert(p.x >= s1->minx && p.x <= s1->maxx);
690 assert(p.x >= s2->minx && p.x <= s2->maxx);
695 #ifndef DONT_REMEMBER_CROSSINGS
696 assert(!dict_contains(status->seen_crossings, &pair));
697 dict_put(status->seen_crossings, &pair, 0);
701 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
704 #ifndef DONT_REMEMBER_CROSSINGS
705 /* we insert into each other's intersection history because these segments might switch
706 places and we still want to look them up quickly after they did */
707 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
708 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
711 event_t* e = event_new();
712 e->type = EVENT_CROSS;
716 queue_put(&status->queue, e);
720 static void exchange_two(status_t*status, event_t*e)
722 //exchange two segments in list
723 segment_t*s1 = e->s1;
724 segment_t*s2 = e->s2;
726 if(!dict_contains(status->intersecting_segs, s1))
727 dict_put(status->intersecting_segs, s1, 0);
728 if(!dict_contains(status->intersecting_segs, s2))
729 dict_put(status->intersecting_segs, s2, 0);
731 assert(s2->left == s1);
732 assert(s1->right == s2);
733 actlist_swap(status->actlist, s1, s2);
734 assert(s2->right == s1);
735 assert(s1->left == s2);
736 segment_t*left = s2->left;
737 segment_t*right = s1->right;
739 schedule_crossing(status, left, s2);
741 schedule_crossing(status, s1, right);
744 typedef struct _box {
745 point_t left1, left2, right1, right2;
747 static inline box_t box_new(int32_t x, int32_t y)
750 box.right1.x = box.right2.x = x;
751 box.left1.x = box.left2.x = x-1;
752 box.left1.y = box.right1.y = y-1;
753 box.left2.y = box.right2.y = y;
757 static void store_horizontal(status_t*status, point_t p1, point_t p2, edgestyle_t*fs, segment_dir_t dir, int polygon_nr);
759 static void append_stroke(status_t*status, point_t a, point_t b, segment_dir_t dir, edgestyle_t*fs)
761 gfxpolystroke_t*stroke = status->strokes;
762 /* find a stoke to attach this segment to. It has to have an endpoint
763 matching our start point, and a matching edgestyle */
765 point_t p = stroke->points[stroke->num_points-1];
766 if(p.x == a.x && p.y == a.y && stroke->fs == fs && stroke->dir == dir)
768 stroke = stroke->next;
771 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
774 stroke->next = status->strokes;
775 status->strokes = stroke;
776 stroke->points_size = 2;
777 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
778 stroke->points[0] = a;
779 stroke->num_points = 1;
780 } else if(stroke->num_points == stroke->points_size) {
782 stroke->points_size *= 2;
783 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
785 stroke->points[stroke->num_points++] = b;
788 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
790 assert(s->pos.x != p.x || s->pos.y != p.y);
793 if(!dict_contains(status->segs_with_point, s))
794 dict_put(status->segs_with_point, s, 0);
795 assert(s->fs_out_ok);
798 if(s->pos.y != p.y) {
799 /* non horizontal line- copy to output */
802 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
803 s->pos.x, s->pos.y, p.x, p.y);
805 segment_dir_t dir = s->wind.is_filled?DIR_DOWN:DIR_UP;
806 assert(s->pos.y != p.y);
807 append_stroke(status, s->pos, p, dir, s->fs_out);
810 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
814 /* horizontal line. we need to look at this more closely at the end of this
816 store_horizontal(status, s->pos, p, s->fs, s->dir, s->polygon_nr);
822 typedef struct _segrange {
829 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
831 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
832 segment_t*min = range->segmin;
833 segment_t*max = range->segmax;
835 /* we need this because if two segments intersect exactly on
836 the scanline, segrange_test_segment_{min,max} can't tell which
837 one is smaller/larger */
838 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
841 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
847 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
850 /* we need to calculate the xpos anew (and can't use start coordinate or
851 intersection coordinate), because we need the xpos exactly at the end of
854 double x = XPOS(seg, y);
855 if(!range->segmin || x<range->xmin) {
860 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
863 double x = XPOS(seg, y);
864 if(!range->segmax || x>range->xmax) {
879 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
881 segment_t*first=0, *last = 0;
883 for(t=0;t<status->xrow->num;t++) {
884 box_t box = box_new(status->xrow->x[t], y);
885 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
887 seg = actlist_right(status->actlist, seg);
890 // this segment started in this scanline, ignore it
891 seg->changed = 1;last = seg;if(!first) {first=seg;}
892 } else if(seg->delta.x <= 0) {
893 // ignore segment w/ negative slope
895 last = seg;if(!first) {first=seg;}
896 double d1 = LINE_EQ(box.right1, seg);
897 double d2 = LINE_EQ(box.right2, seg);
900 insert_point_into_segment(status, seg, box.right2);
902 /* we unfortunately can't break here- the active list is sorted according
903 to the *bottom* of the scanline. hence pretty much everything that's still
904 coming might reach into our box */
911 segrange_test_segment_min(range, first, y);
912 segrange_test_segment_max(range, last, y);
922 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
924 segment_t*first=0, *last = 0;
926 for(t=status->xrow->num-1;t>=0;t--) {
927 box_t box = box_new(status->xrow->x[t], y);
928 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
932 // this segment started in this scanline, ignore it
933 seg->changed = 1;last = seg;if(!first) {first=seg;}
934 } else if(seg->delta.x > 0) {
935 // ignore segment w/ positive slope
937 last = seg;if(!first) {first=seg;}
938 double d1 = LINE_EQ(box.left1, seg);
939 double d2 = LINE_EQ(box.left2, seg);
942 insert_point_into_segment(status, seg, box.right2);
950 segrange_test_segment_min(range, last, y);
951 segrange_test_segment_max(range, first, y);
954 /* segments ending in the current scanline need xrow treatment like everything else.
955 (consider an intersection taking place just above a nearly horizontal segment
956 ending on the current scanline- the intersection would snap down *below* the
957 ending segment if we don't add the intersection point to the latter right away)
958 we need to treat ending segments seperately, however. we have to delete them from
959 the active list right away to make room for intersect operations (which might
960 still be in the current scanline- consider two 45° polygons and a vertical polygon
961 intersecting on an integer coordinate). but once they're no longer in the active list,
962 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
963 them to the active list just for point snapping would be overkill.
964 (One other option to consider, however, would be to create a new active list only
967 static void add_points_to_ending_segments(status_t*status, int32_t y)
969 segment_t*seg = status->ending_segments;
971 segment_t*next = seg->right;seg->right=0;
973 assert(seg->b.y == status->y);
975 if(status->xrow->num == 1) {
977 assert(seg->b.x == status->xrow->x[0]);
978 point_t p = {status->xrow->x[0], y};
979 insert_point_into_segment(status, seg, p);
982 int start=0,end=status->xrow->num,dir=1;
983 if(seg->delta.x < 0) {
984 start = status->xrow->num-1;
987 for(t=start;t!=end;t+=dir) {
988 box_t box = box_new(status->xrow->x[t], y);
989 double d0 = LINE_EQ(box.left1, seg);
990 double d1 = LINE_EQ(box.left2, seg);
991 double d2 = LINE_EQ(box.right1, seg);
992 double d3 = LINE_EQ(box.right2, seg);
993 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
994 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
995 insert_point_into_segment(status, seg, box.right2);
1001 /* we *need* to find a point to insert. the segment's own end point
1002 is in that list, for Pete's sake. */
1006 // now that this is done, too, we can also finally free this segment
1007 segment_destroy(seg);
1010 status->ending_segments = 0;
1013 static void recalculate_windings(status_t*status, segrange_t*range)
1016 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
1018 segrange_adjust_endpoints(range, status->y);
1020 segment_t*s = range->segmin;
1021 segment_t*end = range->segmax;
1025 s = actlist_leftmost(status->actlist);
1027 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
1028 s == range->segmin?"S":(
1029 s == range->segmax?"E":""));
1032 fprintf(stderr, "\n");
1036 /* test sanity: verify that we don't have changed segments
1037 outside of the given range */
1038 s = actlist_leftmost(status->actlist);
1039 while(s && s!=range->segmin) {
1040 assert(!s->changed);
1043 s = actlist_rightmost(status->actlist);
1044 while(s && s!=range->segmax) {
1045 assert(!s->changed);
1048 /* in check mode, go through the whole interval so we can test
1049 that all polygons where the edgestyle changed also have seg->changed=1 */
1050 s = actlist_leftmost(status->actlist);
1061 segment_t* left = actlist_left(status->actlist, s);
1062 windstate_t wind = left?left->wind:status->windrule->start(status->context);
1063 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
1064 edgestyle_t*fs_old = s->fs_out;
1065 s->fs_out = status->windrule->diff(&wind, &s->wind);
1068 fprintf(stderr, "[%d] dir=%s wind=%d wind.filled=%s fs_old/new=%s/%s %s\n", s->nr, s->dir==DIR_UP?"up":"down", s->wind.wind_nr, s->wind.is_filled?"fill":"nofill",
1069 fs_old?"draw":"omit", s->fs_out?"draw":"omit",
1070 fs_old!=s->fs_out?"CHANGED":"");
1072 assert(!(!s->changed && fs_old!=s->fs_out));
1083 /* we need to handle horizontal lines in order to add points to segments
1084 we otherwise would miss during the windrule re-evaluation */
1085 static void intersect_with_horizontal(status_t*status, segment_t*h)
1087 segment_t* left = actlist_find(status->actlist, h->a, h->a);
1088 segment_t* right = actlist_find(status->actlist, h->b, h->b);
1090 /* not strictly necessary, also done by the event */
1091 xrow_add(status->xrow, h->a.x);
1098 left = actlist_right(status->actlist, left); //first seg to the right of h->a
1099 right = right->right; //first seg to the right of h->b
1100 segment_t* s = left;
1105 int32_t x = XPOS_INT(s, status->y);
1106 point_t p = {x, status->y};
1107 store_horizontal(status, o, p, h->fs, h->dir, h->polygon_nr);
1109 fprintf(stderr, "...intersecting with [%d] (%.2f,%.2f) -> (%.2f,%.2f) at (%.2f,%.2f)\n",
1111 s->a.x * status->gridsize, s->a.y * status->gridsize,
1112 s->b.x * status->gridsize, s->b.y * status->gridsize,
1113 x * status->gridsize, status->y * status->gridsize
1116 assert(x >= h->a.x);
1117 assert(x <= h->b.x);
1118 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
1119 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
1120 xrow_add(status->xrow, x);
1127 /* while, for a scanline, we need both starting as well as ending segments in order
1128 to *reconstruct* horizontal lines, we only need one or the other to *process*
1129 horizontal lines from the input data.
1131 So horizontal lines are processed twice: first they create hotpixels by intersecting
1132 all segments on the scanline (EVENT_HORIZTONAL). Secondly, they are processed for
1133 their actual content. The second also happens for all segments that received more than
1134 one point in this scanline.
1136 void horiz_reset(horizdata_t*horiz)
1141 void horiz_destroy(horizdata_t*horiz)
1143 if(horiz->data) rfx_free(horiz->data);
1147 static int compare_horizontals(const void *_h1, const void *_h2)
1149 horizontal_t*h1 = (horizontal_t*)_h1;
1150 horizontal_t*h2 = (horizontal_t*)_h2;
1151 return h1->x1 - h2->x1;
1154 static void process_horizontals(status_t*status)
1156 horizdata_t*horiz = &status->horiz;
1157 qsort(horiz->data, horiz->num, sizeof(horizontal_t), compare_horizontals);
1159 for(t=0;t<horiz->num;t++) {
1160 horizontal_t*h = &horiz->data[t];
1162 fprintf(stderr, "horizontal (y=%.2f): %.2f -> %.2f dir=%s fs=%p\n",
1163 h->y * status->gridsize,
1164 h->x1 * status->gridsize,
1165 h->x2 * status->gridsize,
1166 h->dir==DIR_UP?"up":"down", h->fs);
1168 assert(h->y == status->y);
1169 assert(xrow_contains(status->xrow, h->x1));
1170 assert(xrow_contains(status->xrow, h->x2));
1172 point_t p1 = {h->x1,h->y};
1173 point_t p2 = {h->x2,h->y};
1174 segment_t* left = actlist_find(status->actlist, p1, p2);
1175 assert(!left || left->fs_out_ok);
1178 fprintf(stderr, " segment [%d] (%.2f,%.2f -> %.2f,%2f, at %.2f,%.2f) is to the left\n",
1180 left->a.x * status->gridsize,
1181 left->a.y * status->gridsize,
1182 left->b.x * status->gridsize,
1183 left->b.y * status->gridsize,
1184 left->pos.x * status->gridsize,
1185 left->pos.y * status->gridsize
1187 /* this segment might be a distance away from the left point
1188 of the horizontal line if the horizontal line belongs to a stroke
1189 with segments that just ended (so this horizontal line appears to
1190 be "floating in space" from our current point of view)
1191 assert(left->pos.y == h->y && left->pos.x == h->x1);
1195 windstate_t below = left?left->wind:status->windrule->start(status->context);
1196 windstate_t above = status->windrule->add(status->context, below, h->fs, DIR_INVERT(h->dir), h->polygon_nr);
1197 edgestyle_t*fs = status->windrule->diff(&above, &below);
1200 fprintf(stderr, " ...storing\n");
1202 append_stroke(status, p1, p2, h->dir, fs);
1205 fprintf(stderr, " ...ignoring\n");
1211 static void store_horizontal(status_t*status, point_t p1, point_t p2, edgestyle_t*fs, segment_dir_t dir, int polygon_nr)
1213 assert(p1.y == p2.y);
1214 assert(p1.x != p2.x); // TODO: can this happen?
1217 dir = DIR_INVERT(dir);
1224 if(status->horiz.size == status->horiz.num) {
1225 if(!status->horiz.size)
1226 status->horiz.size = 16;
1227 status->horiz.size *= 2;
1228 status->horiz.data = rfx_realloc(status->horiz.data, sizeof(status->horiz.data[0])*status->horiz.size);
1230 horizontal_t*h = &status->horiz.data[status->horiz.num++];
1236 h->polygon_nr = polygon_nr;
1240 static void event_apply(status_t*status, event_t*e)
1243 event_dump(status, e);
1247 case EVENT_HORIZONTAL: {
1248 segment_t*s = e->s1;
1249 intersect_with_horizontal(status, s);
1250 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1251 segment_destroy(s);e->s1=0;
1255 //delete segment from list
1256 segment_t*s = e->s1;
1258 dict_del(status->intersecting_segs, s);
1259 dict_del(status->segs_with_point, s);
1260 assert(!dict_contains(status->intersecting_segs, s));
1261 assert(!dict_contains(status->segs_with_point, s));
1263 segment_t*left = s->left;
1264 segment_t*right = s->right;
1265 actlist_delete(status->actlist, s);
1267 schedule_crossing(status, left, right);
1269 /* schedule segment for xrow handling */
1270 s->left = 0; s->right = status->ending_segments;
1271 status->ending_segments = s;
1272 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1276 //insert segment into list
1277 segment_t*s = e->s1;
1278 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1279 actlist_insert(status->actlist, s->a, s->b, s);
1280 segment_t*left = s->left;
1281 segment_t*right = s->right;
1283 schedule_crossing(status, left, s);
1285 schedule_crossing(status, s, right);
1286 schedule_endpoint(status, s);
1290 // exchange two segments
1291 if(e->s1->right == e->s2) {
1292 assert(e->s2->left == e->s1);
1293 exchange_two(status, e);
1295 assert(e->s2->left != e->s1);
1297 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1299 #ifndef DONT_REMEMBER_CROSSINGS
1300 /* ignore this crossing for now (there are some line segments in between).
1301 it'll get rescheduled as soon as the "obstacles" are gone */
1302 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1303 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1304 assert(del1 && del2);
1310 #ifndef DONT_REMEMBER_CROSSINGS
1311 assert(dict_contains(status->seen_crossings, &pair));
1312 dict_del(status->seen_crossings, &pair);
1321 static void check_status(status_t*status)
1323 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1324 if((s->pos.x != s->b.x ||
1325 s->pos.y != s->b.y) &&
1326 !dict_contains(status->segs_with_point, s)) {
1327 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1329 s->delta.x<0?"-":"+",
1337 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1340 |..| |...........| | |
1341 |..| |...........| | |
1342 |..+ + +..| +--+ +--+
1343 |...........| |..| | |
1344 |...........| |..| | |
1348 fprintf(stderr, "========================================================================\n");
1351 hqueue_init(&hqueue);
1352 gfxpoly_enqueue(poly, 0, &hqueue, 0);
1354 actlist_t* actlist = actlist_new();
1356 event_t*e = hqueue_get(&hqueue);
1361 fprintf(stderr, "HORIZONTALS ----------------------------------- %f\n", y);
1362 actlist_dump(actlist, y-1, 1.0);
1365 actlist_verify(actlist, y-1);
1367 edgestyle_t*fill = 0;
1372 if(fill && x != e->p.x) {
1373 assert(abs(wind)==1);
1376 gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
1377 stroke->next = poly->strokes;
1378 poly->strokes = stroke;
1380 stroke->num_points = 2;
1381 stroke->points = malloc(sizeof(point_t)*2);
1384 stroke->dir = DIR_DOWN;
1386 stroke->dir = DIR_UP;
1389 fprintf(stderr, "%d) draw horizontal line from %d to %d (dir=%s)\n", y, x, e->p.x, stroke->dir==DIR_UP?"up":"down");
1397 stroke->points[0] = a;
1398 stroke->points[1] = b;
1400 /* the output should always be intersection free polygons, so check this horizontal
1401 line isn't puncturing any segments in the active list */
1402 segment_t* start = actlist_find(actlist, a, a);
1403 segment_t* s = actlist_find(actlist, b, b);
1405 assert(s->a.y == y || s->b.y == y);
1411 segment_t*s = e->s1;
1416 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1417 actlist_insert(actlist, s->a, s->b, s);
1418 event_t* e = event_new();
1419 e->type = EVENT_END;
1423 hqueue_put(&hqueue, e);
1424 left = actlist_left(actlist, s);
1425 wind += e->s1->dir==DIR_DOWN?-1:1;
1429 left = actlist_left(actlist, s);
1430 actlist_delete(actlist, s);
1431 advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos);
1432 wind += e->s1->dir==DIR_DOWN?1:-1;
1440 fill = fill?0:&edgestyle_default;
1442 if(windrule==&windrule_evenodd) {
1443 if(!!fill != !!fill2) {
1446 printf("at y=%d x=%d (hline:%p)\n", e->p.y, x, old_fill);
1447 if(e->type==EVENT_END) {
1448 printf(" %9p\n", s->fs);
1451 printf(" %3d %c%2d \n", before1.is_filled, e->type==EVENT_END?'|':' ', after1.is_filled);
1452 printf("%12p -----+----- %p\n", old_fill, fill2);
1453 printf(" %3d %c%2d \n", before2.is_filled, e->type==EVENT_START?'|':' ', after2.is_filled);
1454 if(e->type==EVENT_START) {
1456 printf(" %9p\n", s->fs);
1459 assert(!!fill == !!fill2);
1464 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d dir:%s\n",
1465 y, e->type==EVENT_START?"start":"end",
1468 x, s->dir==DIR_UP?"up":"down");
1471 if(e->type == EVENT_END)
1475 e = hqueue_get(&hqueue);
1476 } while(e && y == e->p.y);
1479 edgestyle_t*bleeding = fill;
1481 segment_t*s = actlist_leftmost(actlist);
1484 dir += s->dir==DIR_UP?-1:1;
1485 s = actlist_right(actlist, s);
1491 actlist_destroy(actlist);
1492 hqueue_destroy(&hqueue);
1495 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context)
1497 current_polygon = poly1;
1500 memset(&status, 0, sizeof(status_t));
1501 status.gridsize = poly1->gridsize;
1503 queue_init(&status.queue);
1504 gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1506 assert(poly1->gridsize == poly2->gridsize);
1507 gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1510 status.windrule = windrule;
1511 status.context = context;
1512 status.actlist = actlist_new();
1515 status.seen_crossings = dict_new2(&point_type);
1516 int32_t lasty=-0x80000000;
1519 status.xrow = xrow_new();
1521 event_t*e = queue_get(&status.queue);
1526 assert(status.y>=lasty);
1528 status.intersecting_segs = dict_new2(&ptr_type);
1529 status.segs_with_point = dict_new2(&ptr_type);
1533 fprintf(stderr, "----------------------------------- %.2f\n", status.y * status.gridsize);
1534 actlist_dump(status.actlist, status.y-1, status.gridsize);
1537 actlist_verify(status.actlist, status.y-1);
1539 xrow_reset(status.xrow);
1540 horiz_reset(&status.horiz);
1543 xrow_add(status.xrow, e->p.x);
1544 event_apply(&status, e);
1546 e = queue_get(&status.queue);
1547 } while(e && status.y == e->p.y);
1549 xrow_sort(status.xrow);
1551 memset(&range, 0, sizeof(range));
1553 actlist_dump(status.actlist, status.y, status.gridsize);
1555 add_points_to_positively_sloped_segments(&status, status.y, &range);
1556 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1557 add_points_to_ending_segments(&status, status.y);
1559 recalculate_windings(&status, &range);
1560 process_horizontals(&status);
1562 check_status(&status);
1563 dict_destroy(status.intersecting_segs);
1564 dict_destroy(status.segs_with_point);
1568 dict_destroy(status.seen_crossings);
1570 actlist_destroy(status.actlist);
1571 queue_destroy(&status.queue);
1572 horiz_destroy(&status.horiz);
1573 xrow_destroy(status.xrow);
1575 gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1576 p->gridsize = poly1->gridsize;
1577 p->strokes = status.strokes;
1580 /* we only add segments with non-empty edgestyles to strokes in
1581 recalculate_windings, but better safe than sorry */
1582 gfxpolystroke_t*stroke = p->strokes;
1585 stroke = stroke->next;
1589 //add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1590 //add_horizontals(p, windrule, context);
1594 static windcontext_t twopolygons = {2};
1595 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1597 return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons);
1599 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1601 return gfxpoly_process(p1, p2, &windrule_union, &twopolygons);