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 _status {
136 windcontext_t*context;
137 segment_t*ending_segments;
139 gfxpolystroke_t*strokes;
141 dict_t*seen_crossings; //list of crossing we saw so far
142 dict_t*intersecting_segs; //list of segments intersecting in this scanline
143 dict_t*segs_with_point; //lists of segments that received a point in this scanline
148 int gfxpoly_num_segments(gfxpoly_t*poly)
150 gfxpolystroke_t*stroke = poly->strokes;
152 for(;stroke;stroke=stroke->next) {
157 int gfxpoly_size(gfxpoly_t*poly)
161 gfxpolystroke_t*stroke = poly->strokes;
162 for(;stroke;stroke=stroke->next) {
163 edges += stroke->num_points-1;
168 char gfxpoly_check(gfxpoly_t*poly, char updown)
170 current_polygon = poly;
171 dict_t*d1 = dict_new2(&point_type);
172 dict_t*d2 = dict_new2(&point_type);
174 gfxpolystroke_t*stroke = poly->strokes;
175 for(;stroke;stroke=stroke->next) {
176 /* In order to not confuse the fill/wind logic, existing segments must have
177 a non-zero edge style */
180 /* put all the segments into dictionaries so that we can check
181 that the endpoint multiplicity is two */
182 for(s=0;s<stroke->num_points;s++) {
183 point_t p = stroke->points[s];
184 int num_xor = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
185 int num_circ = (s>=1 && s<stroke->num_points-1)?0:(s==0?1:-1);
186 if(stroke->dir==DIR_UP)
189 if(!dict_contains(d1, &p)) {
190 dict_put(d1, &p, (void*)(ptroff_t)num_xor);
192 assert(!dict_contains(d2, &p));
193 dict_put(d2, &p, (void*)(ptroff_t)num_circ);
196 int count = (ptroff_t)dict_lookup(d1, &p);
199 dict_put(d1, &p, (void*)(ptroff_t)count);
202 assert(dict_contains(d2, &p));
203 count = (ptroff_t)dict_lookup(d2, &p);
206 dict_put(d2, &p, (void*)(ptroff_t)count);
211 DICT_ITERATE_ITEMS(d1, point_t*, p1, void*, c1) {
212 int count = (ptroff_t)c1;
214 fprintf(stderr, "Point (%d,%d) occurs %d times\n", p1->x, p1->y, count);
220 DICT_ITERATE_ITEMS(d2, point_t*, p2, void*, c2) {
221 int count = (ptroff_t)c2;
223 if(count>0) fprintf(stderr, "Point (%d,%d) has %d more incoming than outgoing segments\n", p2->x, p2->y, count);
224 if(count<0) fprintf(stderr, "Point (%d,%d) has %d more outgoing than incoming segments\n", p2->x, p2->y, -count);
235 void gfxpoly_dump(gfxpoly_t*poly)
238 double g = poly->gridsize;
239 fprintf(stderr, "polyon %p (gridsize: %f)\n", poly, poly->gridsize);
240 gfxpolystroke_t*stroke = poly->strokes;
241 for(;stroke;stroke=stroke->next) {
242 fprintf(stderr, "%11p", stroke);
243 if(stroke->dir==DIR_UP) {
244 for(s=stroke->num_points-1;s>=1;s--) {
245 point_t a = stroke->points[s];
246 point_t b = stroke->points[s-1];
247 fprintf(stderr, "%s (%f,%f) -> (%f,%f)%s%s\n", s!=stroke->num_points-1?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
248 s==1?"]":"", a.y==b.y?"H":"");
251 for(s=0;s<stroke->num_points-1;s++) {
252 point_t a = stroke->points[s];
253 point_t b = stroke->points[s+1];
254 fprintf(stderr, "%s (%f,%f) -> (%f,%f)%s%s\n", s?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
255 s==stroke->num_points-2?"]":"", a.y==b.y?"H":"");
261 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
263 FILE*fi = fopen(filename, "wb");
264 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
265 fprintf(fi, "%% begin\n");
267 gfxpolystroke_t*stroke = poly->strokes;
268 for(;stroke;stroke=stroke->next) {
269 fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
270 point_t p = stroke->points[0];
271 fprintf(fi, "%d %d moveto\n", p.x, p.y);
272 for(s=1;s<stroke->num_points;s++) {
273 p = stroke->points[s];
274 fprintf(fi, "%d %d lineto\n", p.x, p.y);
276 fprintf(fi, "stroke\n");
278 fprintf(fi, "showpage\n");
282 void gfxpoly_save_arrows(gfxpoly_t*poly, const char*filename)
284 FILE*fi = fopen(filename, "wb");
285 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
286 fprintf(fi, "%% begin\n");
288 double l = 5.0 / poly->gridsize;
289 double g = poly->gridsize;
290 gfxpolystroke_t*stroke = poly->strokes;
291 for(;stroke;stroke=stroke->next) {
292 fprintf(fi, "%g setgray\n", 0);
294 int s = stroke->dir==DIR_UP?stroke->num_points-1:0;
295 int end = stroke->dir==DIR_UP?-1:stroke->num_points;
296 int dir = stroke->dir==DIR_UP?-1:1;
298 point_t p = stroke->points[s];
301 fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
302 for(;s!=end;s+=dir) {
303 p = stroke->points[s];
306 double d = sqrt(lx*lx+ly*ly);
310 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
311 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 + (ly*d))*g,
312 (p.y - ly*d2 - (lx*d))*g);
313 fprintf(fi, "%f %f lineto\n", p.x * g, p.y * g);
314 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 - (ly*d))*g,
315 (p.y - ly*d2 + (lx*d))*g);
316 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
317 fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
320 fprintf(fi, "stroke\n");
322 fprintf(fi, "showpage\n");
326 inline static event_t* event_new()
328 event_t*e = rfx_calloc(sizeof(event_t));
331 inline static void event_free(event_t*e)
336 static void event_dump(event_t*e)
338 if(e->type == EVENT_HORIZONTAL) {
339 fprintf(stderr, "Horizontal [%d] (%d,%d) -> (%d,%d)\n", (int)e->s1->nr, e->s1->a.x, e->s1->a.y, e->s1->b.x, e->s1->b.y);
340 } else if(e->type == EVENT_START) {
341 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", (int)e->s1->nr, e->p.x, e->p.y);
342 } else if(e->type == EVENT_END) {
343 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", (int)e->s1->nr, e->p.x, e->p.y);
344 } else if(e->type == EVENT_CROSS) {
345 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%d,%d)\n", (int)e->s1->nr, (int)e->s2->nr, e->p.x, e->p.y);
351 static inline int32_t max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
352 static inline int32_t min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
354 static void segment_dump(segment_t*s)
356 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", (int)s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
357 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f fs=%p\n", s->delta.x, s->delta.y, s->k,
358 (double)s->delta.x / s->delta.y, s->fs);
361 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)
367 /* We need to make sure horizontal segments always go from left to right.
368 "up/down" for horizontal segments is handled by "rotating"
369 them 90° anticlockwise in screen coordinates (tilt your head to
375 int32_t x = x1;x1=x2;x2=x;
376 int32_t y = y1;y1=y2;y2=y;
383 s->k = (double)x1*y2-(double)x2*y1;
384 s->left = s->right = 0;
387 s->minx = min32(x1,x2);
388 s->maxx = max32(x1,x2);
391 s->polygon_nr = polygon_nr;
392 static int segment_count=0;
393 s->nr = segment_count++;
396 /* notice: on some systems (with some compilers), for the line
397 (1073741823,-1073741824)->(1073741823,1073741823)
398 we get LINE_EQ(s->a, s) == 1.
399 That's why we now clamp to 26 bit.
401 assert(LINE_EQ(s->a, s) == 0);
402 assert(LINE_EQ(s->b, s) == 0);
404 /* check that all signs are in order:
412 p.x = min32(s->a.x, s->b.x);
413 assert(LINE_EQ(p, s) <= 0);
414 p.x = max32(s->a.x, s->b.x);
415 assert(LINE_EQ(p, s) >= 0);
418 #ifndef DONT_REMEMBER_CROSSINGS
419 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
423 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
425 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
426 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
430 static void segment_clear(segment_t*s)
432 #ifndef DONT_REMEMBER_CROSSINGS
433 dict_clear(&s->scheduled_crossings);
436 static void segment_destroy(segment_t*s)
442 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
447 /* we need to queue multiple segments at once because we need to process start events
448 before horizontal events */
449 while(pos < stroke->num_points-1) {
450 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
451 s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
459 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %p, %d more to come)\n",
460 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
461 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
463 event_t* e = event_new();
464 e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
469 if(queue) queue_put(queue, e);
470 else hqueue_put(hqueue, e);
472 if(e->type != EVENT_HORIZONTAL) {
482 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
485 gfxpolystroke_t*stroke = p->strokes;
486 for(;stroke;stroke=stroke->next) {
487 assert(stroke->num_points > 1);
491 for(s=0;s<stroke->num_points-1;s++) {
492 assert(stroke->points[s].y <= stroke->points[s+1].y);
495 advance_stroke(queue, hqueue, stroke, polygon_nr, 0);
499 static void schedule_endpoint(status_t*status, segment_t*s)
501 // schedule end point of segment
502 assert(s->b.y > status->y);
503 event_t*e = event_new();
508 queue_put(&status->queue, e);
511 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
513 /* the code that's required (and the checks you can perform) before
514 it can be said with 100% certainty that we indeed have a valid crossing
515 amazes me every time. -mk */
518 assert(s1->right == s2);
519 assert(s2->left == s1);
520 int32_t miny1 = min32(s1->a.y,s1->b.y);
521 int32_t maxy1 = max32(s1->a.y,s1->b.y);
522 int32_t miny2 = min32(s2->a.y,s2->b.y);
523 int32_t maxy2 = max32(s2->a.y,s2->b.y);
524 int32_t minx1 = min32(s1->a.x,s1->b.x);
525 int32_t minx2 = min32(s2->a.x,s2->b.x);
526 int32_t maxx1 = max32(s1->a.x,s1->b.x);
527 int32_t maxx2 = max32(s2->a.x,s2->b.x);
528 /* check that precomputation is sane */
529 assert(minx1 == s1->minx && minx2 == s2->minx);
530 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
531 /* both segments are active, so this can't happen */
532 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
533 /* we know that right now, s2 is to the right of s1, so there's
534 no way the complete bounding box of s1 is to the right of s1 */
535 assert(!(s1->minx > s2->maxx));
536 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
539 if(s1->maxx <= s2->minx) {
541 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
543 /* bounding boxes don't intersect */
547 #ifndef DONT_REMEMBER_CROSSINGS
548 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
549 /* FIXME: this whole segment hashing thing is really slow */
551 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
552 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
553 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
556 return; // we already know about this one
560 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
563 // lines are exactly on top of each other (ignored)
565 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
570 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
572 /* lines are parallel */
577 double asign2 = LINE_EQ(s1->a, s2);
579 // segment1 touches segment2 in a single point (ignored)
581 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
585 double bsign2 = LINE_EQ(s1->b, s2);
587 // segment1 touches segment2 in a single point (ignored)
589 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
594 if(asign2<0 && bsign2<0) {
595 // segment1 is completely to the left of segment2
597 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);
601 if(asign2>0 && bsign2>0) {
602 // segment1 is completely to the right of segment2
603 #ifndef DONT_REMEMBER_CROSSINGS
607 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);
612 double asign1 = LINE_EQ(s2->a, s1);
614 // segment2 touches segment1 in a single point (ignored)
616 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
620 double bsign1 = LINE_EQ(s2->b, s1);
622 // segment2 touches segment1 in a single point (ignored)
624 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
629 if(asign1<0 && bsign1<0) {
630 // segment2 is completely to the left of segment1
631 #ifndef DONT_REMEMBER_CROSSINGS
635 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);
639 if(asign1>0 && bsign1>0) {
640 // segment2 is completely to the right of segment1
642 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);
647 #ifdef DONT_REMEMBER_CROSSINGS
648 /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
649 there's not way s2 would be to the left of s1 otherwise */
650 if(asign1<0 && bsign1>0) return;
651 if(asign2>0 && bsign2<0) return;
654 assert(!(asign1<0 && bsign1>0));
655 assert(!(asign2>0 && bsign2<0));
657 /* TODO: should we precompute these? */
658 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
659 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
662 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
663 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
665 assert(p.y >= status->y);
667 assert(p.x >= s1->minx && p.x <= s1->maxx);
668 assert(p.x >= s2->minx && p.x <= s2->maxx);
673 #ifndef DONT_REMEMBER_CROSSINGS
674 assert(!dict_contains(status->seen_crossings, &pair));
675 dict_put(status->seen_crossings, &pair, 0);
679 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
682 #ifndef DONT_REMEMBER_CROSSINGS
683 /* we insert into each other's intersection history because these segments might switch
684 places and we still want to look them up quickly after they did */
685 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
686 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
689 event_t* e = event_new();
690 e->type = EVENT_CROSS;
694 queue_put(&status->queue, e);
698 static void exchange_two(status_t*status, event_t*e)
700 //exchange two segments in list
701 segment_t*s1 = e->s1;
702 segment_t*s2 = e->s2;
704 if(!dict_contains(status->intersecting_segs, s1))
705 dict_put(status->intersecting_segs, s1, 0);
706 if(!dict_contains(status->intersecting_segs, s2))
707 dict_put(status->intersecting_segs, s2, 0);
709 assert(s2->left == s1);
710 assert(s1->right == s2);
711 actlist_swap(status->actlist, s1, s2);
712 assert(s2->right == s1);
713 assert(s1->left == s2);
714 segment_t*left = s2->left;
715 segment_t*right = s1->right;
717 schedule_crossing(status, left, s2);
719 schedule_crossing(status, s1, right);
722 typedef struct _box {
723 point_t left1, left2, right1, right2;
725 static inline box_t box_new(int32_t x, int32_t y)
728 box.right1.x = box.right2.x = x;
729 box.left1.x = box.left2.x = x-1;
730 box.left1.y = box.right1.y = y-1;
731 box.left2.y = box.right2.y = y;
735 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
737 assert(s->pos.x != p.x || s->pos.y != p.y);
740 if(!dict_contains(status->segs_with_point, s))
741 dict_put(status->segs_with_point, s, 0);
742 assert(s->fs_out_ok);
747 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
748 s->pos.x, s->pos.y, p.x, p.y);
750 edgestyle_t*fs = s->fs_out;
751 segment_dir_t dir = s->wind.is_filled?DIR_DOWN:DIR_UP;
753 // omit horizontal lines
754 if(s->pos.y != p.y) {
759 gfxpolystroke_t*stroke = status->strokes;
760 /* find a stoke to attach this segment to. It has to have an endpoint
761 matching our start point, and a matching edgestyle */
763 point_t p = stroke->points[stroke->num_points-1];
764 if(p.x == a.x && p.y == a.y && stroke->fs == fs && stroke->dir == dir)
766 stroke = stroke->next;
769 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
772 stroke->next = status->strokes;
773 status->strokes = stroke;
774 stroke->points_size = 2;
775 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
776 stroke->points[0] = a;
777 stroke->num_points = 1;
778 } else if(stroke->num_points == stroke->points_size) {
780 stroke->points_size *= 2;
781 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
783 stroke->points[stroke->num_points++] = b;
787 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
793 typedef struct _segrange {
800 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
802 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
803 segment_t*min = range->segmin;
804 segment_t*max = range->segmax;
806 /* we need this because if two segments intersect exactly on
807 the scanline, segrange_test_segment_{min,max} can't tell which
808 one is smaller/larger */
809 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
812 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
818 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
821 /* we need to calculate the xpos anew (and can't use start coordinate or
822 intersection coordinate), because we need the xpos exactly at the end of
825 double x = XPOS(seg, y);
826 if(!range->segmin || x<range->xmin) {
831 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
834 double x = XPOS(seg, y);
835 if(!range->segmax || x>range->xmax) {
850 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
852 segment_t*first=0, *last = 0;
854 for(t=0;t<status->xrow->num;t++) {
855 box_t box = box_new(status->xrow->x[t], y);
856 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
858 seg = actlist_right(status->actlist, seg);
861 // this segment started in this scanline, ignore it
862 seg->changed = 1;last = seg;if(!first) {first=seg;}
863 } else if(seg->delta.x <= 0) {
864 // ignore segment w/ negative slope
866 last = seg;if(!first) {first=seg;}
867 double d1 = LINE_EQ(box.right1, seg);
868 double d2 = LINE_EQ(box.right2, seg);
871 insert_point_into_segment(status, seg, box.right2);
873 /* we unfortunately can't break here- the active list is sorted according
874 to the *bottom* of the scanline. hence pretty much everything that's still
875 coming might reach into our box */
882 segrange_test_segment_min(range, first, y);
883 segrange_test_segment_max(range, last, y);
893 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
895 segment_t*first=0, *last = 0;
897 for(t=status->xrow->num-1;t>=0;t--) {
898 box_t box = box_new(status->xrow->x[t], y);
899 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
903 // this segment started in this scanline, ignore it
904 seg->changed = 1;last = seg;if(!first) {first=seg;}
905 } else if(seg->delta.x > 0) {
906 // ignore segment w/ positive slope
908 last = seg;if(!first) {first=seg;}
909 double d1 = LINE_EQ(box.left1, seg);
910 double d2 = LINE_EQ(box.left2, seg);
913 insert_point_into_segment(status, seg, box.right2);
921 segrange_test_segment_min(range, last, y);
922 segrange_test_segment_max(range, first, y);
925 /* segments ending in the current scanline need xrow treatment like everything else.
926 (consider an intersection taking place just above a nearly horizontal segment
927 ending on the current scanline- the intersection would snap down *below* the
928 ending segment if we don't add the intersection point to the latter right away)
929 we need to treat ending segments seperately, however. we have to delete them from
930 the active list right away to make room for intersect operations (which might
931 still be in the current scanline- consider two 45° polygons and a vertical polygon
932 intersecting on an integer coordinate). but once they're no longer in the active list,
933 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
934 them to the active list just for point snapping would be overkill.
935 (One other option to consider, however, would be to create a new active list only
938 static void add_points_to_ending_segments(status_t*status, int32_t y)
940 segment_t*seg = status->ending_segments;
942 segment_t*next = seg->right;seg->right=0;
944 assert(seg->b.y == status->y);
946 if(status->xrow->num == 1) {
948 assert(seg->b.x == status->xrow->x[0]);
949 point_t p = {status->xrow->x[0], y};
950 insert_point_into_segment(status, seg, p);
953 int start=0,end=status->xrow->num,dir=1;
954 if(seg->delta.x < 0) {
955 start = status->xrow->num-1;
958 for(t=start;t!=end;t+=dir) {
959 box_t box = box_new(status->xrow->x[t], y);
960 double d0 = LINE_EQ(box.left1, seg);
961 double d1 = LINE_EQ(box.left2, seg);
962 double d2 = LINE_EQ(box.right1, seg);
963 double d3 = LINE_EQ(box.right2, seg);
964 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
965 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
966 insert_point_into_segment(status, seg, box.right2);
972 /* we *need* to find a point to insert. the segment's own end point
973 is in that list, for Pete's sake. */
977 // now that this is done, too, we can also finally free this segment
978 segment_destroy(seg);
981 status->ending_segments = 0;
984 static void recalculate_windings(status_t*status, segrange_t*range)
987 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
989 segrange_adjust_endpoints(range, status->y);
991 segment_t*s = range->segmin;
992 segment_t*end = range->segmax;
996 s = actlist_leftmost(status->actlist);
998 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
999 s == range->segmin?"S":(
1000 s == range->segmax?"E":""));
1003 fprintf(stderr, "\n");
1007 /* test sanity: verify that we don't have changed segments
1008 outside of the given range */
1009 s = actlist_leftmost(status->actlist);
1010 while(s && s!=range->segmin) {
1011 assert(!s->changed);
1014 s = actlist_rightmost(status->actlist);
1015 while(s && s!=range->segmax) {
1016 assert(!s->changed);
1019 /* in check mode, go through the whole interval so we can test
1020 that all polygons where the edgestyle changed also have seg->changed=1 */
1021 s = actlist_leftmost(status->actlist);
1032 segment_t* left = actlist_left(status->actlist, s);
1033 windstate_t wind = left?left->wind:status->windrule->start(status->context);
1034 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
1035 edgestyle_t*fs_old = s->fs_out;
1036 s->fs_out = status->windrule->diff(&wind, &s->wind);
1039 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",
1040 fs_old?"draw":"omit", s->fs_out?"draw":"omit",
1041 fs_old!=s->fs_out?"CHANGED":"");
1043 assert(!(!s->changed && fs_old!=s->fs_out));
1054 /* we need to handle horizontal lines in order to add points to segments
1055 we otherwise would miss during the windrule re-evaluation */
1056 static void intersect_with_horizontal(status_t*status, segment_t*h)
1058 segment_t* left = actlist_find(status->actlist, h->a, h->a);
1059 segment_t* right = actlist_find(status->actlist, h->b, h->b);
1061 /* not strictly necessary, also done by the event */
1062 xrow_add(status->xrow, h->a.x);
1070 left = actlist_right(status->actlist, left); //first seg to the right of h->a
1071 right = right->right; //first seg to the right of h->b
1072 segment_t* s = left;
1076 int32_t x = XPOS_INT(s, status->y);
1078 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
1084 assert(x >= h->a.x);
1085 assert(x <= h->b.x);
1086 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
1087 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
1088 xrow_add(status->xrow, x);
1094 static void event_apply(status_t*status, event_t*e)
1097 case EVENT_HORIZONTAL: {
1098 segment_t*s = e->s1;
1102 intersect_with_horizontal(status, s);
1103 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1104 segment_destroy(s);e->s1=0;
1108 //delete segment from list
1109 segment_t*s = e->s1;
1114 dict_del(status->intersecting_segs, s);
1115 dict_del(status->segs_with_point, s);
1116 assert(!dict_contains(status->intersecting_segs, s));
1117 assert(!dict_contains(status->segs_with_point, s));
1119 segment_t*left = s->left;
1120 segment_t*right = s->right;
1121 actlist_delete(status->actlist, s);
1123 schedule_crossing(status, left, right);
1125 /* schedule segment for xrow handling */
1126 s->left = 0; s->right = status->ending_segments;
1127 status->ending_segments = s;
1128 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1132 //insert segment into list
1136 segment_t*s = e->s1;
1137 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1138 actlist_insert(status->actlist, s->a, s->b, s);
1139 segment_t*left = s->left;
1140 segment_t*right = s->right;
1142 schedule_crossing(status, left, s);
1144 schedule_crossing(status, s, right);
1145 schedule_endpoint(status, s);
1149 // exchange two segments
1153 if(e->s1->right == e->s2) {
1154 assert(e->s2->left == e->s1);
1155 exchange_two(status, e);
1157 assert(e->s2->left != e->s1);
1159 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1161 #ifndef DONT_REMEMBER_CROSSINGS
1162 /* ignore this crossing for now (there are some line segments in between).
1163 it'll get rescheduled as soon as the "obstacles" are gone */
1164 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1165 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1166 assert(del1 && del2);
1172 #ifndef DONT_REMEMBER_CROSSINGS
1173 assert(dict_contains(status->seen_crossings, &pair));
1174 dict_del(status->seen_crossings, &pair);
1183 static void check_status(status_t*status)
1185 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1186 if((s->pos.x != s->b.x ||
1187 s->pos.y != s->b.y) &&
1188 !dict_contains(status->segs_with_point, s)) {
1189 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1191 s->delta.x<0?"-":"+",
1199 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1202 |..| |...........| | |
1203 |..| |...........| | |
1204 |..+ + +..| +--+ +--+
1205 |...........| |..| | |
1206 |...........| |..| | |
1210 fprintf(stderr, "========================================================================\n");
1213 hqueue_init(&hqueue);
1214 gfxpoly_enqueue(poly, 0, &hqueue, 0);
1216 actlist_t* actlist = actlist_new();
1218 event_t*e = hqueue_get(&hqueue);
1223 fprintf(stderr, "HORIZONTALS ----------------------------------- %d\n", y);
1224 actlist_dump(actlist, y-1);
1227 actlist_verify(actlist, y-1);
1229 edgestyle_t*fill = 0;
1234 if(fill && x != e->p.x) {
1235 assert(abs(wind)==1);
1238 gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
1239 stroke->next = poly->strokes;
1240 poly->strokes = stroke;
1242 stroke->num_points = 2;
1243 stroke->points = malloc(sizeof(point_t)*2);
1246 stroke->dir = DIR_DOWN;
1248 stroke->dir = DIR_UP;
1251 fprintf(stderr, "%d) draw horizontal line from %d to %d (dir=%s)\n", y, x, e->p.x, stroke->dir==DIR_UP?"up":"down");
1259 stroke->points[0] = a;
1260 stroke->points[1] = b;
1262 /* the output should always be intersection free polygons, so check this horizontal
1263 line isn't puncturing any segments in the active list */
1264 segment_t* start = actlist_find(actlist, a, a);
1265 segment_t* s = actlist_find(actlist, b, b);
1267 assert(s->a.y == y || s->b.y == y);
1273 segment_t*s = e->s1;
1278 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1279 actlist_insert(actlist, s->a, s->b, s);
1280 event_t* e = event_new();
1281 e->type = EVENT_END;
1285 hqueue_put(&hqueue, e);
1286 left = actlist_left(actlist, s);
1287 wind += e->s1->dir==DIR_DOWN?-1:1;
1291 left = actlist_left(actlist, s);
1292 actlist_delete(actlist, s);
1293 advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos);
1294 wind += e->s1->dir==DIR_DOWN?1:-1;
1302 fill = fill?0:&edgestyle_default;
1304 if(windrule==&windrule_evenodd) {
1305 if(!!fill != !!fill2) {
1308 printf("at y=%d x=%d (hline:%p)\n", e->p.y, x, old_fill);
1309 if(e->type==EVENT_END) {
1310 printf(" %9p\n", s->fs);
1313 printf(" %3d %c%2d \n", before1.is_filled, e->type==EVENT_END?'|':' ', after1.is_filled);
1314 printf("%12p -----+----- %p\n", old_fill, fill2);
1315 printf(" %3d %c%2d \n", before2.is_filled, e->type==EVENT_START?'|':' ', after2.is_filled);
1316 if(e->type==EVENT_START) {
1318 printf(" %9p\n", s->fs);
1321 assert(!!fill == !!fill2);
1326 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d dir:%s\n",
1327 y, e->type==EVENT_START?"start":"end",
1330 x, s->dir==DIR_UP?"up":"down");
1333 if(e->type == EVENT_END)
1337 e = hqueue_get(&hqueue);
1338 } while(e && y == e->p.y);
1341 edgestyle_t*bleeding = fill;
1343 segment_t*s = actlist_leftmost(actlist);
1346 dir += s->dir==DIR_UP?-1:1;
1347 s = actlist_right(actlist, s);
1353 actlist_destroy(actlist);
1354 hqueue_destroy(&hqueue);
1357 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context)
1359 current_polygon = poly1;
1362 memset(&status, 0, sizeof(status_t));
1363 queue_init(&status.queue);
1364 gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1366 assert(poly1->gridsize == poly2->gridsize);
1367 gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1370 status.windrule = windrule;
1371 status.context = context;
1372 status.actlist = actlist_new();
1375 status.seen_crossings = dict_new2(&point_type);
1376 int32_t lasty=-0x80000000;
1379 status.xrow = xrow_new();
1381 event_t*e = queue_get(&status.queue);
1386 assert(status.y>=lasty);
1388 status.intersecting_segs = dict_new2(&ptr_type);
1389 status.segs_with_point = dict_new2(&ptr_type);
1393 fprintf(stderr, "----------------------------------- %d\n", status.y);
1394 actlist_dump(status.actlist, status.y-1);
1397 actlist_verify(status.actlist, status.y-1);
1399 xrow_reset(status.xrow);
1401 xrow_add(status.xrow, e->p.x);
1402 event_apply(&status, e);
1404 e = queue_get(&status.queue);
1405 } while(e && status.y == e->p.y);
1407 xrow_sort(status.xrow);
1409 memset(&range, 0, sizeof(range));
1411 actlist_dump(status.actlist, status.y);
1413 add_points_to_positively_sloped_segments(&status, status.y, &range);
1414 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1415 add_points_to_ending_segments(&status, status.y);
1417 recalculate_windings(&status, &range);
1419 check_status(&status);
1420 dict_destroy(status.intersecting_segs);
1421 dict_destroy(status.segs_with_point);
1425 dict_destroy(status.seen_crossings);
1427 actlist_destroy(status.actlist);
1428 queue_destroy(&status.queue);
1429 xrow_destroy(status.xrow);
1431 gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1432 p->gridsize = poly1->gridsize;
1433 p->strokes = status.strokes;
1436 /* we only add segments with non-empty edgestyles to strokes in
1437 recalculate_windings, but better safe than sorry */
1438 gfxpolystroke_t*stroke = p->strokes;
1441 stroke = stroke->next;
1445 add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1446 //add_horizontals(p, windrule, context);
1450 static windcontext_t twopolygons = {2};
1451 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1453 return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons);
1455 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1457 return gfxpoly_process(p1, p2, &windrule_union, &twopolygons);