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)
170 current_polygon = poly;
171 dict_t*d = dict_new2(&point_type);
173 gfxpolystroke_t*stroke = poly->strokes;
174 for(;stroke;stroke=stroke->next) {
175 /* In order to not confuse the fill/wind logic, existing segments must have
176 a non-zero edge style */
179 /* put all the segments into dictionaries so that we can check
180 that the endpoint multiplicity is two */
181 for(s=0;s<stroke->num_points;s++) {
182 point_t p = stroke->points[s];
183 int num = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
184 if(!dict_contains(d, &p)) {
185 dict_put(d, &p, (void*)(ptroff_t)num);
187 int count = (ptroff_t)dict_lookup(d, &p);
190 dict_put(d, &p, (void*)(ptroff_t)count);
194 DICT_ITERATE_ITEMS(d, point_t*, p, void*, c) {
195 int count = (ptroff_t)c;
197 fprintf(stderr, "Point (%d,%d) occurs %d times\n", p->x, p->y, count);
199 assert(count%2 == 0);
206 void gfxpoly_dump(gfxpoly_t*poly)
209 double g = poly->gridsize;
210 fprintf(stderr, "polyon %p (gridsize: %f)\n", poly, poly->gridsize);
211 gfxpolystroke_t*stroke = poly->strokes;
212 for(;stroke;stroke=stroke->next) {
213 fprintf(stderr, "%11p", stroke);
214 if(stroke->dir==DIR_UP) {
215 for(s=stroke->num_points-1;s>=1;s--) {
216 point_t a = stroke->points[s];
217 point_t b = stroke->points[s-1];
218 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,
219 s==1?"]":"", a.y==b.y?"H":"");
222 for(s=0;s<stroke->num_points-1;s++) {
223 point_t a = stroke->points[s];
224 point_t b = stroke->points[s+1];
225 fprintf(stderr, "%s (%f,%f) -> (%f,%f)%s%s\n", s?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
226 s==stroke->num_points-2?"]":"", a.y==b.y?"H":"");
232 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
234 FILE*fi = fopen(filename, "wb");
235 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
236 fprintf(fi, "%% begin\n");
238 gfxpolystroke_t*stroke = poly->strokes;
239 for(;stroke;stroke=stroke->next) {
240 fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
241 point_t p = stroke->points[0];
242 fprintf(fi, "%d %d moveto\n", p.x, p.y);
243 for(s=1;s<stroke->num_points;s++) {
244 p = stroke->points[s];
245 fprintf(fi, "%d %d lineto\n", p.x, p.y);
247 fprintf(fi, "stroke\n");
249 fprintf(fi, "showpage\n");
253 void gfxpoly_save_arrows(gfxpoly_t*poly, const char*filename)
255 FILE*fi = fopen(filename, "wb");
256 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
257 fprintf(fi, "%% begin\n");
259 double l = 5.0 / poly->gridsize;
260 double g = poly->gridsize;
261 gfxpolystroke_t*stroke = poly->strokes;
262 for(;stroke;stroke=stroke->next) {
263 fprintf(fi, "%g setgray\n", 0);
265 int s = stroke->dir==DIR_UP?stroke->num_points-1:0;
266 int end = stroke->dir==DIR_UP?-1:stroke->num_points;
267 int dir = stroke->dir==DIR_UP?-1:1;
269 point_t p = stroke->points[s];
272 fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
273 for(;s!=end;s+=dir) {
274 p = stroke->points[s];
277 double d = sqrt(lx*lx+ly*ly);
281 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
282 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 + (ly*d))*g,
283 (p.y - ly*d2 - (lx*d))*g);
284 fprintf(fi, "%f %f lineto\n", p.x * g, p.y * g);
285 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 - (ly*d))*g,
286 (p.y - ly*d2 + (lx*d))*g);
287 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
288 fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
291 fprintf(fi, "stroke\n");
293 fprintf(fi, "showpage\n");
297 inline static event_t* event_new()
299 event_t*e = rfx_calloc(sizeof(event_t));
302 inline static void event_free(event_t*e)
307 static void event_dump(event_t*e)
309 if(e->type == EVENT_HORIZONTAL) {
310 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);
311 } else if(e->type == EVENT_START) {
312 fprintf(stderr, "event: segment [%d] starts at (%d,%d)\n", (int)e->s1->nr, e->p.x, e->p.y);
313 } else if(e->type == EVENT_END) {
314 fprintf(stderr, "event: segment [%d] ends at (%d,%d)\n", (int)e->s1->nr, e->p.x, e->p.y);
315 } else if(e->type == EVENT_CROSS) {
316 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);
322 static inline int32_t max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
323 static inline int32_t min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
325 static void segment_dump(segment_t*s)
327 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", (int)s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
328 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f fs=%p\n", s->delta.x, s->delta.y, s->k,
329 (double)s->delta.x / s->delta.y, s->fs);
332 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)
338 /* We need to make sure horizontal segments always go from left to right.
339 "up/down" for horizontal segments is handled by "rotating"
340 them 90° anticlockwise in screen coordinates (tilt your head to
346 int32_t x = x1;x1=x2;x2=x;
347 int32_t y = y1;y1=y2;y2=y;
354 s->k = (double)x1*y2-(double)x2*y1;
355 s->left = s->right = 0;
358 s->minx = min32(x1,x2);
359 s->maxx = max32(x1,x2);
362 s->polygon_nr = polygon_nr;
363 static int segment_count=0;
364 s->nr = segment_count++;
367 /* notice: on some systems (with some compilers), for the line
368 (1073741823,-1073741824)->(1073741823,1073741823)
369 we get LINE_EQ(s->a, s) == 1.
370 That's why we now clamp to 26 bit.
372 assert(LINE_EQ(s->a, s) == 0);
373 assert(LINE_EQ(s->b, s) == 0);
375 /* check that all signs are in order:
383 p.x = min32(s->a.x, s->b.x);
384 assert(LINE_EQ(p, s) <= 0);
385 p.x = max32(s->a.x, s->b.x);
386 assert(LINE_EQ(p, s) >= 0);
389 #ifndef DONT_REMEMBER_CROSSINGS
390 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
394 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
396 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
397 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
401 static void segment_clear(segment_t*s)
403 #ifndef DONT_REMEMBER_CROSSINGS
404 dict_clear(&s->scheduled_crossings);
407 static void segment_destroy(segment_t*s)
413 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos)
418 /* we need to queue multiple segments at once because we need to process start events
419 before horizontal events */
420 while(pos < stroke->num_points-1) {
421 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
422 s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
430 fprintf(stderr, "[%d] (%d,%d) -> (%d,%d) %s (stroke %p, %d more to come)\n",
431 s->nr, s->a.x, s->a.y, s->b.x, s->b.y,
432 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
434 event_t* e = event_new();
435 e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
440 if(queue) queue_put(queue, e);
441 else hqueue_put(hqueue, e);
443 if(e->type != EVENT_HORIZONTAL) {
453 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
456 gfxpolystroke_t*stroke = p->strokes;
457 for(;stroke;stroke=stroke->next) {
458 assert(stroke->num_points > 1);
462 for(s=0;s<stroke->num_points-1;s++) {
463 assert(stroke->points[s].y <= stroke->points[s+1].y);
466 advance_stroke(queue, hqueue, stroke, polygon_nr, 0);
470 static void schedule_endpoint(status_t*status, segment_t*s)
472 // schedule end point of segment
473 assert(s->b.y > status->y);
474 event_t*e = event_new();
479 queue_put(&status->queue, e);
482 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
484 /* the code that's required (and the checks you can perform) before
485 it can be said with 100% certainty that we indeed have a valid crossing
486 amazes me every time. -mk */
489 assert(s1->right == s2);
490 assert(s2->left == s1);
491 int32_t miny1 = min32(s1->a.y,s1->b.y);
492 int32_t maxy1 = max32(s1->a.y,s1->b.y);
493 int32_t miny2 = min32(s2->a.y,s2->b.y);
494 int32_t maxy2 = max32(s2->a.y,s2->b.y);
495 int32_t minx1 = min32(s1->a.x,s1->b.x);
496 int32_t minx2 = min32(s2->a.x,s2->b.x);
497 int32_t maxx1 = max32(s1->a.x,s1->b.x);
498 int32_t maxx2 = max32(s2->a.x,s2->b.x);
499 /* check that precomputation is sane */
500 assert(minx1 == s1->minx && minx2 == s2->minx);
501 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
502 /* both segments are active, so this can't happen */
503 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
504 /* we know that right now, s2 is to the right of s1, so there's
505 no way the complete bounding box of s1 is to the right of s1 */
506 assert(!(s1->minx > s2->maxx));
507 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
510 if(s1->maxx <= s2->minx) {
512 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
514 /* bounding boxes don't intersect */
518 #ifndef DONT_REMEMBER_CROSSINGS
519 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
520 /* FIXME: this whole segment hashing thing is really slow */
522 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
523 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
524 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
527 return; // we already know about this one
531 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
534 // lines are exactly on top of each other (ignored)
536 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
541 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
543 /* lines are parallel */
548 double asign2 = LINE_EQ(s1->a, s2);
550 // segment1 touches segment2 in a single point (ignored)
552 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
556 double bsign2 = LINE_EQ(s1->b, s2);
558 // segment1 touches segment2 in a single point (ignored)
560 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
565 if(asign2<0 && bsign2<0) {
566 // segment1 is completely to the left of segment2
568 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);
572 if(asign2>0 && bsign2>0) {
573 // segment1 is completely to the right of segment2
574 #ifndef DONT_REMEMBER_CROSSINGS
578 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);
583 double asign1 = LINE_EQ(s2->a, s1);
585 // segment2 touches segment1 in a single point (ignored)
587 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
591 double bsign1 = LINE_EQ(s2->b, s1);
593 // segment2 touches segment1 in a single point (ignored)
595 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
600 if(asign1<0 && bsign1<0) {
601 // segment2 is completely to the left of segment1
602 #ifndef DONT_REMEMBER_CROSSINGS
606 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);
610 if(asign1>0 && bsign1>0) {
611 // segment2 is completely to the right of segment1
613 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);
618 #ifdef DONT_REMEMBER_CROSSINGS
619 /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
620 there's not way s2 would be to the left of s1 otherwise */
621 if(asign1<0 && bsign1>0) return;
622 if(asign2>0 && bsign2<0) return;
625 assert(!(asign1<0 && bsign1>0));
626 assert(!(asign2>0 && bsign2<0));
628 /* TODO: should we precompute these? */
629 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
630 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
633 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
634 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
636 assert(p.y >= status->y);
638 assert(p.x >= s1->minx && p.x <= s1->maxx);
639 assert(p.x >= s2->minx && p.x <= s2->maxx);
644 #ifndef DONT_REMEMBER_CROSSINGS
645 assert(!dict_contains(status->seen_crossings, &pair));
646 dict_put(status->seen_crossings, &pair, 0);
650 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
653 #ifndef DONT_REMEMBER_CROSSINGS
654 /* we insert into each other's intersection history because these segments might switch
655 places and we still want to look them up quickly after they did */
656 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
657 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
660 event_t* e = event_new();
661 e->type = EVENT_CROSS;
665 queue_put(&status->queue, e);
669 static void exchange_two(status_t*status, event_t*e)
671 //exchange two segments in list
672 segment_t*s1 = e->s1;
673 segment_t*s2 = e->s2;
675 if(!dict_contains(status->intersecting_segs, s1))
676 dict_put(status->intersecting_segs, s1, 0);
677 if(!dict_contains(status->intersecting_segs, s2))
678 dict_put(status->intersecting_segs, s2, 0);
680 assert(s2->left == s1);
681 assert(s1->right == s2);
682 actlist_swap(status->actlist, s1, s2);
683 assert(s2->right == s1);
684 assert(s1->left == s2);
685 segment_t*left = s2->left;
686 segment_t*right = s1->right;
688 schedule_crossing(status, left, s2);
690 schedule_crossing(status, s1, right);
693 typedef struct _box {
694 point_t left1, left2, right1, right2;
696 static inline box_t box_new(int32_t x, int32_t y)
699 box.right1.x = box.right2.x = x;
700 box.left1.x = box.left2.x = x-1;
701 box.left1.y = box.right1.y = y-1;
702 box.left2.y = box.right2.y = y;
706 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
708 assert(s->pos.x != p.x || s->pos.y != p.y);
711 if(!dict_contains(status->segs_with_point, s))
712 dict_put(status->segs_with_point, s, 0);
713 assert(s->fs_out_ok);
718 fprintf(stderr, "[%d] receives next point (%d,%d)->(%d,%d) (drawing)\n", s->nr,
719 s->pos.x, s->pos.y, p.x, p.y);
721 edgestyle_t*fs = s->fs_out;
722 segment_dir_t dir = s->wind.is_filled?DIR_DOWN:DIR_UP;
724 // omit horizontal lines
725 if(s->pos.y != p.y) {
730 gfxpolystroke_t*stroke = status->strokes;
731 /* find a stoke to attach this segment to. It has to have an endpoint
732 matching our start point, and a matching edgestyle */
734 point_t p = stroke->points[stroke->num_points-1];
735 if(p.x == a.x && p.y == a.y && stroke->fs == fs && stroke->dir == dir)
737 stroke = stroke->next;
740 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
743 stroke->next = status->strokes;
744 status->strokes = stroke;
745 stroke->points_size = 2;
746 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
747 stroke->points[0] = a;
748 stroke->num_points = 1;
749 } else if(stroke->num_points == stroke->points_size) {
751 stroke->points_size *= 2;
752 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
754 stroke->points[stroke->num_points++] = b;
758 fprintf(stderr, "[%d] receives next point (%d,%d) (omitting)\n", s->nr, p.x, p.y);
764 typedef struct _segrange {
771 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
773 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
774 segment_t*min = range->segmin;
775 segment_t*max = range->segmax;
777 /* we need this because if two segments intersect exactly on
778 the scanline, segrange_test_segment_{min,max} can't tell which
779 one is smaller/larger */
780 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
783 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
789 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
792 /* we need to calculate the xpos anew (and can't use start coordinate or
793 intersection coordinate), because we need the xpos exactly at the end of
796 double x = XPOS(seg, y);
797 if(!range->segmin || x<range->xmin) {
802 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
805 double x = XPOS(seg, y);
806 if(!range->segmax || x>range->xmax) {
821 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
823 segment_t*first=0, *last = 0;
825 for(t=0;t<status->xrow->num;t++) {
826 box_t box = box_new(status->xrow->x[t], y);
827 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
829 seg = actlist_right(status->actlist, seg);
832 // this segment started in this scanline, ignore it
833 seg->changed = 1;last = seg;if(!first) {first=seg;}
834 } else if(seg->delta.x <= 0) {
835 // ignore segment w/ negative slope
837 last = seg;if(!first) {first=seg;}
838 double d1 = LINE_EQ(box.right1, seg);
839 double d2 = LINE_EQ(box.right2, seg);
842 insert_point_into_segment(status, seg, box.right2);
844 /* we unfortunately can't break here- the active list is sorted according
845 to the *bottom* of the scanline. hence pretty much everything that's still
846 coming might reach into our box */
853 segrange_test_segment_min(range, first, y);
854 segrange_test_segment_max(range, last, y);
864 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
866 segment_t*first=0, *last = 0;
868 for(t=status->xrow->num-1;t>=0;t--) {
869 box_t box = box_new(status->xrow->x[t], y);
870 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
874 // this segment started in this scanline, ignore it
875 seg->changed = 1;last = seg;if(!first) {first=seg;}
876 } else if(seg->delta.x > 0) {
877 // ignore segment w/ positive slope
879 last = seg;if(!first) {first=seg;}
880 double d1 = LINE_EQ(box.left1, seg);
881 double d2 = LINE_EQ(box.left2, seg);
884 insert_point_into_segment(status, seg, box.right2);
892 segrange_test_segment_min(range, last, y);
893 segrange_test_segment_max(range, first, y);
896 /* segments ending in the current scanline need xrow treatment like everything else.
897 (consider an intersection taking place just above a nearly horizontal segment
898 ending on the current scanline- the intersection would snap down *below* the
899 ending segment if we don't add the intersection point to the latter right away)
900 we need to treat ending segments seperately, however. we have to delete them from
901 the active list right away to make room for intersect operations (which might
902 still be in the current scanline- consider two 45° polygons and a vertical polygon
903 intersecting on an integer coordinate). but once they're no longer in the active list,
904 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
905 them to the active list just for point snapping would be overkill.
906 (One other option to consider, however, would be to create a new active list only
909 static void add_points_to_ending_segments(status_t*status, int32_t y)
911 segment_t*seg = status->ending_segments;
913 segment_t*next = seg->right;seg->right=0;
915 assert(seg->b.y == status->y);
917 if(status->xrow->num == 1) {
919 assert(seg->b.x == status->xrow->x[0]);
920 point_t p = {status->xrow->x[0], y};
921 insert_point_into_segment(status, seg, p);
924 int start=0,end=status->xrow->num,dir=1;
925 if(seg->delta.x < 0) {
926 start = status->xrow->num-1;
929 for(t=start;t!=end;t+=dir) {
930 box_t box = box_new(status->xrow->x[t], y);
931 double d0 = LINE_EQ(box.left1, seg);
932 double d1 = LINE_EQ(box.left2, seg);
933 double d2 = LINE_EQ(box.right1, seg);
934 double d3 = LINE_EQ(box.right2, seg);
935 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
936 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
937 insert_point_into_segment(status, seg, box.right2);
943 /* we *need* to find a point to insert. the segment's own end point
944 is in that list, for Pete's sake. */
948 // now that this is done, too, we can also finally free this segment
949 segment_destroy(seg);
952 status->ending_segments = 0;
955 static void recalculate_windings(status_t*status, segrange_t*range)
958 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
960 segrange_adjust_endpoints(range, status->y);
962 segment_t*s = range->segmin;
963 segment_t*end = range->segmax;
967 s = actlist_leftmost(status->actlist);
969 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
970 s == range->segmin?"S":(
971 s == range->segmax?"E":""));
974 fprintf(stderr, "\n");
978 /* test sanity: verify that we don't have changed segments
979 outside of the given range */
980 s = actlist_leftmost(status->actlist);
981 while(s && s!=range->segmin) {
985 s = actlist_rightmost(status->actlist);
986 while(s && s!=range->segmax) {
990 /* in check mode, go through the whole interval so we can test
991 that all polygons where the edgestyle changed also have seg->changed=1 */
992 s = actlist_leftmost(status->actlist);
1003 segment_t* left = actlist_left(status->actlist, s);
1004 windstate_t wind = left?left->wind:status->windrule->start(status->context);
1005 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
1006 edgestyle_t*fs_old = s->fs_out;
1007 s->fs_out = status->windrule->diff(&wind, &s->wind);
1010 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",
1011 fs_old?"draw":"omit", s->fs_out?"draw":"omit",
1012 fs_old!=s->fs_out?"CHANGED":"");
1014 assert(!(!s->changed && fs_old!=s->fs_out));
1025 /* we need to handle horizontal lines in order to add points to segments
1026 we otherwise would miss during the windrule re-evaluation */
1027 static void intersect_with_horizontal(status_t*status, segment_t*h)
1029 segment_t* left = actlist_find(status->actlist, h->a, h->a);
1030 segment_t* right = actlist_find(status->actlist, h->b, h->b);
1032 /* not strictly necessary, also done by the event */
1033 xrow_add(status->xrow, h->a.x);
1041 left = actlist_right(status->actlist, left); //first seg to the right of h->a
1042 right = right->right; //first seg to the right of h->b
1043 segment_t* s = left;
1047 int32_t x = XPOS_INT(s, status->y);
1049 fprintf(stderr, "...into [%d] (%d,%d) -> (%d,%d) at (%d,%d)\n", s->nr,
1055 assert(x >= h->a.x);
1056 assert(x <= h->b.x);
1057 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
1058 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
1059 xrow_add(status->xrow, x);
1065 static void event_apply(status_t*status, event_t*e)
1068 case EVENT_HORIZONTAL: {
1069 segment_t*s = e->s1;
1073 intersect_with_horizontal(status, s);
1074 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1075 segment_destroy(s);e->s1=0;
1079 //delete segment from list
1080 segment_t*s = e->s1;
1085 dict_del(status->intersecting_segs, s);
1086 dict_del(status->segs_with_point, s);
1087 assert(!dict_contains(status->intersecting_segs, s));
1088 assert(!dict_contains(status->segs_with_point, s));
1090 segment_t*left = s->left;
1091 segment_t*right = s->right;
1092 actlist_delete(status->actlist, s);
1094 schedule_crossing(status, left, right);
1096 /* schedule segment for xrow handling */
1097 s->left = 0; s->right = status->ending_segments;
1098 status->ending_segments = s;
1099 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos);
1103 //insert segment into list
1107 segment_t*s = e->s1;
1108 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1109 actlist_insert(status->actlist, s->a, s->b, s);
1110 segment_t*left = s->left;
1111 segment_t*right = s->right;
1113 schedule_crossing(status, left, s);
1115 schedule_crossing(status, s, right);
1116 schedule_endpoint(status, s);
1120 // exchange two segments
1124 if(e->s1->right == e->s2) {
1125 assert(e->s2->left == e->s1);
1126 exchange_two(status, e);
1128 assert(e->s2->left != e->s1);
1130 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1132 #ifndef DONT_REMEMBER_CROSSINGS
1133 /* ignore this crossing for now (there are some line segments in between).
1134 it'll get rescheduled as soon as the "obstacles" are gone */
1135 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1136 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1137 assert(del1 && del2);
1143 #ifndef DONT_REMEMBER_CROSSINGS
1144 assert(dict_contains(status->seen_crossings, &pair));
1145 dict_del(status->seen_crossings, &pair);
1154 static void check_status(status_t*status)
1156 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1157 if((s->pos.x != s->b.x ||
1158 s->pos.y != s->b.y) &&
1159 !dict_contains(status->segs_with_point, s)) {
1160 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1162 s->delta.x<0?"-":"+",
1170 static void add_horizontals(gfxpoly_t*poly, windrule_t*windrule, windcontext_t*context)
1173 |..| |...........| | |
1174 |..| |...........| | |
1175 |..+ + +..| +--+ +--+
1176 |...........| |..| | |
1177 |...........| |..| | |
1181 fprintf(stderr, "========================================================================\n");
1184 hqueue_init(&hqueue);
1185 gfxpoly_enqueue(poly, 0, &hqueue, 0);
1187 actlist_t* actlist = actlist_new();
1189 event_t*e = hqueue_get(&hqueue);
1194 fprintf(stderr, "HORIZONTALS ----------------------------------- %d\n", y);
1195 actlist_dump(actlist, y-1);
1198 actlist_verify(actlist, y-1);
1200 edgestyle_t*fill = 0;
1206 if(fill && x != e->p.x) {
1208 fprintf(stderr, "%d) draw horizontal line from %d to %d\n", y, x, e->p.x);
1211 assert(dir_up || dir_down);
1213 gfxpolystroke_t*stroke = rfx_calloc(sizeof(gfxpolystroke_t));
1214 stroke->next = poly->strokes;
1215 poly->strokes = stroke;
1217 stroke->num_points = 2;
1218 stroke->points = malloc(sizeof(point_t)*2);
1219 if(dir_up < 0 || dir_down > 0) {
1220 stroke->dir = DIR_UP;
1222 stroke->dir = DIR_DOWN;
1228 /* we draw from low x to high x so that left/right fillstyles add up
1229 (because the horizontal line's fill style controls the area *below* the line)
1233 stroke->points[0] = a;
1234 stroke->points[1] = b;
1236 /* the output should always be intersection free polygons, so check this horizontal
1237 line isn't puncturing any segments in the active list */
1238 segment_t* start = actlist_find(actlist, b, b);
1239 segment_t* s = actlist_find(actlist, a, a);
1241 assert(s->a.y == y || s->b.y == y);
1247 segment_t*s = e->s1;
1252 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1253 actlist_insert(actlist, s->a, s->b, s);
1254 event_t* e = event_new();
1255 e->type = EVENT_END;
1259 hqueue_put(&hqueue, e);
1260 left = actlist_left(actlist, s);
1261 dir_down += e->s1->dir==DIR_UP?1:-1;
1265 left = actlist_left(actlist, s);
1266 actlist_delete(actlist, s);
1267 advance_stroke(0, &hqueue, s->stroke, s->polygon_nr, s->stroke_pos);
1268 dir_up += e->s1->dir==DIR_UP?1:-1;
1276 fill = fill?0:&edgestyle_default;
1278 if(windrule==&windrule_evenodd) {
1279 if(!!fill != !!fill2) {
1282 printf("at y=%d x=%d (hline:%p)\n", e->p.y, x, old_fill);
1283 if(e->type==EVENT_END) {
1284 printf(" %9p\n", s->fs);
1287 printf(" %3d %c%2d \n", before1.is_filled, e->type==EVENT_END?'|':' ', after1.is_filled);
1288 printf("%12p -----+----- %p\n", old_fill, fill2);
1289 printf(" %3d %c%2d \n", before2.is_filled, e->type==EVENT_START?'|':' ', after2.is_filled);
1290 if(e->type==EVENT_START) {
1292 printf(" %9p\n", s->fs);
1295 assert(!!fill == !!fill2);
1300 fprintf(stderr, "%d) event=%s[%d] left:[%d] x:%d\n",
1301 y, e->type==EVENT_START?"start":"end",
1307 if(e->type == EVENT_END)
1311 e = hqueue_get(&hqueue);
1312 } while(e && y == e->p.y);
1315 edgestyle_t*bleeding = fill;
1320 actlist_destroy(actlist);
1321 hqueue_destroy(&hqueue);
1324 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context)
1326 current_polygon = poly1;
1329 memset(&status, 0, sizeof(status_t));
1330 queue_init(&status.queue);
1331 gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1333 assert(poly1->gridsize == poly2->gridsize);
1334 gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1337 status.windrule = windrule;
1338 status.context = context;
1339 status.actlist = actlist_new();
1342 status.seen_crossings = dict_new2(&point_type);
1343 int32_t lasty=-0x80000000;
1346 status.xrow = xrow_new();
1348 event_t*e = queue_get(&status.queue);
1353 assert(status.y>=lasty);
1355 status.intersecting_segs = dict_new2(&ptr_type);
1356 status.segs_with_point = dict_new2(&ptr_type);
1360 fprintf(stderr, "----------------------------------- %d\n", status.y);
1361 actlist_dump(status.actlist, status.y-1);
1364 actlist_verify(status.actlist, status.y-1);
1366 xrow_reset(status.xrow);
1368 xrow_add(status.xrow, e->p.x);
1369 event_apply(&status, e);
1371 e = queue_get(&status.queue);
1372 } while(e && status.y == e->p.y);
1374 xrow_sort(status.xrow);
1376 memset(&range, 0, sizeof(range));
1378 actlist_dump(status.actlist, status.y);
1380 add_points_to_positively_sloped_segments(&status, status.y, &range);
1381 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1382 add_points_to_ending_segments(&status, status.y);
1384 recalculate_windings(&status, &range);
1386 check_status(&status);
1387 dict_destroy(status.intersecting_segs);
1388 dict_destroy(status.segs_with_point);
1392 dict_destroy(status.seen_crossings);
1394 actlist_destroy(status.actlist);
1395 queue_destroy(&status.queue);
1396 xrow_destroy(status.xrow);
1398 gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1399 p->gridsize = poly1->gridsize;
1400 p->strokes = status.strokes;
1403 /* we only add segments with non-empty edgestyles to strokes in
1404 recalculate_windings, but better safe than sorry */
1405 gfxpolystroke_t*stroke = p->strokes;
1408 stroke = stroke->next;
1412 add_horizontals(p, &windrule_evenodd, context); // output is always even/odd
1413 //add_horizontals(p, windrule, context);
1417 static windcontext_t twopolygons = {2};
1418 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1420 return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons);
1422 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1424 return gfxpoly_process(p1, p2, &windrule_union, &twopolygons);