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 {
140 typedef struct _horizdata {
146 typedef struct _status {
153 windcontext_t*context;
154 segment_t*ending_segments;
158 gfxpolystroke_t*strokes;
160 dict_t*seen_crossings; //list of crossing we saw so far
161 dict_t*intersecting_segs; //list of segments intersecting in this scanline
162 dict_t*segs_with_point; //lists of segments that received a point in this scanline
167 int gfxpoly_num_segments(gfxpoly_t*poly)
169 gfxpolystroke_t*stroke = poly->strokes;
171 for(;stroke;stroke=stroke->next) {
176 int gfxpoly_size(gfxpoly_t*poly)
180 gfxpolystroke_t*stroke = poly->strokes;
181 for(;stroke;stroke=stroke->next) {
182 edges += stroke->num_points-1;
187 char gfxpoly_check(gfxpoly_t*poly, char updown)
189 dict_t*d1 = dict_new2(&point_type);
190 dict_t*d2 = dict_new2(&point_type);
192 gfxpolystroke_t*stroke = poly->strokes;
193 for(;stroke;stroke=stroke->next) {
194 /* In order to not confuse the fill/wind logic, existing segments must have
195 a non-zero edge style */
198 /* put all the segments into dictionaries so that we can check
199 that the endpoint multiplicity is two */
200 for(s=0;s<stroke->num_points;s++) {
201 point_t p = stroke->points[s];
202 int num_xor = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
203 int num_circ = (s>=1 && s<stroke->num_points-1)?0:(s==0?1:-1);
204 if(stroke->dir==DIR_UP)
207 if(!dict_contains(d1, &p)) {
208 dict_put(d1, &p, (void*)(ptroff_t)num_xor);
210 assert(!dict_contains(d2, &p));
211 dict_put(d2, &p, (void*)(ptroff_t)num_circ);
214 int count = (ptroff_t)dict_lookup(d1, &p);
217 dict_put(d1, &p, (void*)(ptroff_t)count);
220 assert(dict_contains(d2, &p));
221 count = (ptroff_t)dict_lookup(d2, &p);
224 dict_put(d2, &p, (void*)(ptroff_t)count);
229 DICT_ITERATE_ITEMS(d1, point_t*, p1, void*, c1) {
230 int count = (ptroff_t)c1;
232 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;
241 assert(dict_contains(d1, p2));
242 int ocount = (ptroff_t)dict_lookup(d1, p2);
244 if(count>0) fprintf(stderr, "Error: Point (%.2f,%.2f) has %d more incoming than outgoing segments (%d incoming, %d outgoing)\n", p2->x * poly->gridsize, p2->y * poly->gridsize, count, (ocount+count)/2, (ocount-count)/2);
245 if(count<0) fprintf(stderr, "Error: Point (%.2f,%.2f) has %d more outgoing than incoming segments (%d incoming, %d outgoing)\n", p2->x * poly->gridsize, p2->y * poly->gridsize, -count, (ocount+count)/2, (ocount-count)/2);
246 gfxpolystroke_t*stroke = poly->strokes;
247 for(;stroke;stroke=stroke->next) {
248 for(s=0;s<stroke->num_points-1;s++) {
249 point_t a = stroke->points[s];
250 point_t b = stroke->points[s+1];
251 if(a.x == p2->x && a.y == p2->y ||
252 b.x == p2->x && b.y == p2->y) {
253 fprintf(stderr, "%.2f,%.2f -> %.2f,%.2f\n",
254 a.x * poly->gridsize,
255 a.y * poly->gridsize,
256 b.x * poly->gridsize,
257 b.y * poly->gridsize);
271 void gfxpoly_dump(gfxpoly_t*poly)
274 double g = poly->gridsize;
275 fprintf(stderr, "polyon %p (gridsize: %.2f)\n", poly, poly->gridsize);
276 gfxpolystroke_t*stroke = poly->strokes;
277 for(;stroke;stroke=stroke->next) {
278 fprintf(stderr, "%11p", stroke);
279 if(stroke->dir==DIR_UP) {
280 for(s=stroke->num_points-1;s>=1;s--) {
281 point_t a = stroke->points[s];
282 point_t b = stroke->points[s-1];
283 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,
284 s==1?"]":"", a.y==b.y?"H":"");
287 for(s=0;s<stroke->num_points-1;s++) {
288 point_t a = stroke->points[s];
289 point_t b = stroke->points[s+1];
290 fprintf(stderr, "%s (%.2f,%.2f) -> (%.2f,%.2f)%s%s\n", s?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
291 s==stroke->num_points-2?"]":"", a.y==b.y?"H":"");
297 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
299 FILE*fi = fopen(filename, "wb");
300 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
301 fprintf(fi, "%% begin\n");
303 gfxpolystroke_t*stroke = poly->strokes;
304 for(;stroke;stroke=stroke->next) {
305 fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
306 point_t p = stroke->points[0];
307 fprintf(fi, "%d %d moveto\n", p.x, p.y);
308 for(s=1;s<stroke->num_points;s++) {
309 p = stroke->points[s];
310 fprintf(fi, "%d %d lineto\n", p.x, p.y);
312 fprintf(fi, "stroke\n");
314 fprintf(fi, "showpage\n");
318 void gfxpoly_save_arrows(gfxpoly_t*poly, const char*filename)
320 FILE*fi = fopen(filename, "wb");
321 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
322 fprintf(fi, "%% begin\n");
324 double l = 5.0 / poly->gridsize;
325 double g = poly->gridsize;
326 gfxpolystroke_t*stroke = poly->strokes;
327 for(;stroke;stroke=stroke->next) {
328 fprintf(fi, "0 setgray\n");
330 int s = stroke->dir==DIR_UP?stroke->num_points-1:0;
331 int end = stroke->dir==DIR_UP?-1:stroke->num_points;
332 int dir = stroke->dir==DIR_UP?-1:1;
334 point_t p = stroke->points[s];
337 fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
338 for(;s!=end;s+=dir) {
339 p = stroke->points[s];
342 double d = sqrt(lx*lx+ly*ly);
346 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
347 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 + (ly*d))*g,
348 (p.y - ly*d2 - (lx*d))*g);
349 fprintf(fi, "%f %f lineto\n", p.x * g, p.y * g);
350 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 - (ly*d))*g,
351 (p.y - ly*d2 + (lx*d))*g);
352 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
353 fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
356 fprintf(fi, "stroke\n");
358 fprintf(fi, "showpage\n");
362 inline static event_t* event_new()
364 event_t*e = rfx_calloc(sizeof(event_t));
367 inline static void event_free(event_t*e)
372 static void event_dump(status_t*status, event_t*e)
374 if(e->type == EVENT_HORIZONTAL) {
375 fprintf(stderr, "Horizontal [%d] (%.2f,%.2f) -> (%.2f,%.2f)\n", (int)e->s1->nr,
376 e->s1->a.x * status->gridsize, e->s1->a.y * status->gridsize, e->s1->b.x * status->gridsize, e->s1->b.y * status->gridsize);
377 } else if(e->type == EVENT_START) {
378 fprintf(stderr, "event: segment [%d] starts at (%.2f,%.2f)\n", (int)e->s1->nr,
379 e->p.x * status->gridsize, e->p.y * status->gridsize);
380 } else if(e->type == EVENT_END) {
381 fprintf(stderr, "event: segment [%d] ends at (%.2f,%.2f)\n", (int)e->s1->nr,
382 e->p.x * status->gridsize, e->p.y * status->gridsize);
383 } else if(e->type == EVENT_CROSS) {
384 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%.2f,%.2f)\n", (int)e->s1->nr, (int)e->s2->nr,
385 e->p.x * status->gridsize, e->p.y * status->gridsize);
391 static inline int32_t max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
392 static inline int32_t min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
394 static void segment_dump(segment_t*s)
396 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", (int)s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
397 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f fs=%p\n", s->delta.x, s->delta.y, s->k,
398 (double)s->delta.x / s->delta.y, s->fs);
401 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)
403 static int segment_count=0;
404 s->nr = segment_count++;
409 /* We need to make sure horizontal segments always go from left to right.
410 "up/down" for horizontal segments is handled by "rotating"
411 them 90° counterclockwise in screen coordinates (tilt your head to
412 the right). In other words, the "normal" direction (what's positive dy for
413 vertical segments) is positive dx for horizontal segments ("down" is right).
416 s->dir = DIR_INVERT(s->dir);
417 int32_t x = x1;x1=x2;x2=x;
418 int32_t y = y1;y1=y2;y2=y;
421 fprintf(stderr, "Scheduling horizontal segment [%d] (%.2f,%.2f) -> (%.2f,%.2f) %s\n",
423 x1 * 0.05, y1 * 0.05, x2 * 0.05, y2 * 0.05, s->dir==DIR_UP?"up":"down");
430 s->k = (double)x1*y2-(double)x2*y1;
431 s->left = s->right = 0;
434 s->minx = min32(x1,x2);
435 s->maxx = max32(x1,x2);
438 s->polygon_nr = polygon_nr;
441 /* notice: on some systems (with some compilers), for the line
442 (1073741823,-1073741824)->(1073741823,1073741823)
443 we get LINE_EQ(s->a, s) == 1.
444 That's why we now clamp to 26 bit.
446 assert(LINE_EQ(s->a, s) == 0);
447 assert(LINE_EQ(s->b, s) == 0);
449 /* check that all signs are in order:
457 p.x = min32(s->a.x, s->b.x);
458 assert(LINE_EQ(p, s) <= 0);
459 p.x = max32(s->a.x, s->b.x);
460 assert(LINE_EQ(p, s) >= 0);
463 #ifndef DONT_REMEMBER_CROSSINGS
464 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
468 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
470 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
471 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
475 static void segment_clear(segment_t*s)
477 #ifndef DONT_REMEMBER_CROSSINGS
478 dict_clear(&s->scheduled_crossings);
481 static void segment_destroy(segment_t*s)
487 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos, double gridsize)
492 /* we need to queue multiple segments at once because we need to process start events
493 before horizontal events */
494 while(pos < stroke->num_points-1) {
495 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
496 s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
504 fprintf(stderr, "[%d] (%.2f,%.2f) -> (%.2f,%.2f) %s (stroke %p, %d more to come)\n",
505 s->nr, s->a.x * gridsize, s->a.y * gridsize,
506 s->b.x * gridsize, s->b.y * gridsize,
507 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
509 event_t* e = event_new();
510 e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
515 if(queue) queue_put(queue, e);
516 else hqueue_put(hqueue, e);
518 if(e->type != EVENT_HORIZONTAL) {
528 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
531 gfxpolystroke_t*stroke = p->strokes;
532 for(;stroke;stroke=stroke->next) {
533 assert(stroke->num_points > 1);
537 for(s=0;s<stroke->num_points-1;s++) {
538 assert(stroke->points[s].y <= stroke->points[s+1].y);
541 advance_stroke(queue, hqueue, stroke, polygon_nr, 0, p->gridsize);
545 static void schedule_endpoint(status_t*status, segment_t*s)
547 // schedule end point of segment
548 assert(s->b.y > status->y);
549 event_t*e = event_new();
554 queue_put(&status->queue, e);
557 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
559 /* the code that's required (and the checks you can perform) before
560 it can be said with 100% certainty that we indeed have a valid crossing
561 amazes me every time. -mk */
564 assert(s1->right == s2);
565 assert(s2->left == s1);
566 int32_t miny1 = min32(s1->a.y,s1->b.y);
567 int32_t maxy1 = max32(s1->a.y,s1->b.y);
568 int32_t miny2 = min32(s2->a.y,s2->b.y);
569 int32_t maxy2 = max32(s2->a.y,s2->b.y);
570 int32_t minx1 = min32(s1->a.x,s1->b.x);
571 int32_t minx2 = min32(s2->a.x,s2->b.x);
572 int32_t maxx1 = max32(s1->a.x,s1->b.x);
573 int32_t maxx2 = max32(s2->a.x,s2->b.x);
574 /* check that precomputation is sane */
575 assert(minx1 == s1->minx && minx2 == s2->minx);
576 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
577 /* both segments are active, so this can't happen */
578 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
579 /* we know that right now, s2 is to the right of s1, so there's
580 no way the complete bounding box of s1 is to the right of s1 */
581 assert(!(s1->minx > s2->maxx));
582 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
585 if(s1->maxx <= s2->minx) {
587 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
589 /* bounding boxes don't intersect */
593 #ifndef DONT_REMEMBER_CROSSINGS
594 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
595 /* FIXME: this whole segment hashing thing is really slow */
597 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
598 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
599 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
602 return; // we already know about this one
606 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
609 // lines are exactly on top of each other (ignored)
611 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
616 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
618 /* lines are parallel */
623 double asign2 = LINE_EQ(s1->a, s2);
625 // segment1 touches segment2 in a single point (ignored)
627 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
631 double bsign2 = LINE_EQ(s1->b, s2);
633 // segment1 touches segment2 in a single point (ignored)
635 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
640 if(asign2<0 && bsign2<0) {
641 // segment1 is completely to the left of segment2
643 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);
647 if(asign2>0 && bsign2>0) {
648 // segment1 is completely to the right of segment2
649 #ifndef DONT_REMEMBER_CROSSINGS
653 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);
658 double asign1 = LINE_EQ(s2->a, s1);
660 // segment2 touches segment1 in a single point (ignored)
662 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
666 double bsign1 = LINE_EQ(s2->b, s1);
668 // segment2 touches segment1 in a single point (ignored)
670 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
675 if(asign1<0 && bsign1<0) {
676 // segment2 is completely to the left of segment1
677 #ifndef DONT_REMEMBER_CROSSINGS
681 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);
685 if(asign1>0 && bsign1>0) {
686 // segment2 is completely to the right of segment1
688 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);
693 #ifdef DONT_REMEMBER_CROSSINGS
694 /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
695 there's not way s2 would be to the left of s1 otherwise */
696 if(asign1<0 && bsign1>0) return;
697 if(asign2>0 && bsign2<0) return;
700 assert(!(asign1<0 && bsign1>0));
701 assert(!(asign2>0 && bsign2<0));
703 /* TODO: should we precompute these? */
704 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
705 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
708 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
709 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
711 assert(p.y >= status->y);
713 assert(p.x >= s1->minx && p.x <= s1->maxx);
714 assert(p.x >= s2->minx && p.x <= s2->maxx);
719 #ifndef DONT_REMEMBER_CROSSINGS
720 assert(!dict_contains(status->seen_crossings, &pair));
721 dict_put(status->seen_crossings, &pair, 0);
725 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
728 #ifndef DONT_REMEMBER_CROSSINGS
729 /* we insert into each other's intersection history because these segments might switch
730 places and we still want to look them up quickly after they did */
731 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
732 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
735 event_t* e = event_new();
736 e->type = EVENT_CROSS;
740 queue_put(&status->queue, e);
744 static void exchange_two(status_t*status, event_t*e)
746 //exchange two segments in list
747 segment_t*s1 = e->s1;
748 segment_t*s2 = e->s2;
750 if(!dict_contains(status->intersecting_segs, s1))
751 dict_put(status->intersecting_segs, s1, 0);
752 if(!dict_contains(status->intersecting_segs, s2))
753 dict_put(status->intersecting_segs, s2, 0);
755 assert(s2->left == s1);
756 assert(s1->right == s2);
757 actlist_swap(status->actlist, s1, s2);
758 assert(s2->right == s1);
759 assert(s1->left == s2);
760 segment_t*left = s2->left;
761 segment_t*right = s1->right;
763 schedule_crossing(status, left, s2);
765 schedule_crossing(status, s1, right);
768 typedef struct _box {
769 point_t left1, left2, right1, right2;
771 static inline box_t box_new(int32_t x, int32_t y)
774 box.right1.x = box.right2.x = x;
775 box.left1.x = box.left2.x = x-1;
776 box.left1.y = box.right1.y = y-1;
777 box.left2.y = box.right2.y = y;
781 static void store_horizontal(status_t*status, point_t p1, point_t p2, edgestyle_t*fs, segment_dir_t dir, int polygon_nr);
783 static void append_stroke(status_t*status, point_t a, point_t b, segment_dir_t dir, edgestyle_t*fs)
785 gfxpolystroke_t*stroke = status->strokes;
786 /* find a stoke to attach this segment to. It has to have an endpoint
787 matching our start point, and a matching edgestyle */
789 point_t p = stroke->points[stroke->num_points-1];
790 if(p.x == a.x && p.y == a.y && stroke->fs == fs && stroke->dir == dir)
792 stroke = stroke->next;
795 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
798 stroke->next = status->strokes;
799 status->strokes = stroke;
800 stroke->points_size = 2;
801 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
802 stroke->points[0] = a;
803 stroke->num_points = 1;
804 } else if(stroke->num_points == stroke->points_size) {
806 stroke->points_size *= 2;
807 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
809 stroke->points[stroke->num_points++] = b;
812 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
814 assert(s->pos.x != p.x || s->pos.y != p.y);
817 if(!dict_contains(status->segs_with_point, s))
818 dict_put(status->segs_with_point, s, 0);
819 assert(s->fs_out_ok);
822 if(s->pos.y != p.y) {
823 /* non horizontal line- copy to output */
825 segment_dir_t dir = s->wind.is_filled?DIR_DOWN:DIR_UP;
827 fprintf(stderr, "[%d] receives next point (%.2f,%.2f)->(%.2f,%.2f) (drawing (%s))\n", s->nr,
828 s->pos.x * status->gridsize, s->pos.y * status->gridsize,
829 p.x * status->gridsize, p.y * status->gridsize,
830 dir==DIR_UP?"up":"down"
833 assert(s->pos.y != p.y);
834 append_stroke(status, s->pos, p, dir, s->fs_out);
837 fprintf(stderr, "[%d] receives next point (%.2f,%.2f) (omitting)\n", s->nr,
838 p.x * status->gridsize,
839 p.y * status->gridsize);
843 /* horizontal line. we need to look at this more closely at the end of this
845 store_horizontal(status, s->pos, p, s->fs, s->dir, s->polygon_nr);
851 typedef struct _segrange {
858 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
860 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
861 segment_t*min = range->segmin;
862 segment_t*max = range->segmax;
864 /* we need this because if two segments intersect exactly on
865 the scanline, segrange_test_segment_{min,max} can't tell which
866 one is smaller/larger */
867 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
870 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
876 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
879 /* we need to calculate the xpos anew (and can't use start coordinate or
880 intersection coordinate), because we need the xpos exactly at the end of
883 double x = XPOS(seg, y);
884 if(!range->segmin || x<range->xmin) {
889 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
892 double x = XPOS(seg, y);
893 if(!range->segmax || x>range->xmax) {
908 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
910 segment_t*first=0, *last = 0;
912 for(t=0;t<status->xrow->num;t++) {
913 box_t box = box_new(status->xrow->x[t], y);
914 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
916 seg = actlist_right(status->actlist, seg);
919 // this segment started in this scanline, ignore it
920 seg->changed = 1;last = seg;if(!first) {first=seg;}
921 } else if(seg->delta.x <= 0) {
922 // ignore segment w/ negative slope
924 last = seg;if(!first) {first=seg;}
925 double d1 = LINE_EQ(box.right1, seg);
926 double d2 = LINE_EQ(box.right2, seg);
929 insert_point_into_segment(status, seg, box.right2);
931 /* we unfortunately can't break here- the active list is sorted according
932 to the *bottom* of the scanline. hence pretty much everything that's still
933 coming might reach into our box */
940 segrange_test_segment_min(range, first, y);
941 segrange_test_segment_max(range, last, y);
951 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
953 segment_t*first=0, *last = 0;
955 for(t=status->xrow->num-1;t>=0;t--) {
956 box_t box = box_new(status->xrow->x[t], y);
957 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
961 // this segment started in this scanline, ignore it
962 seg->changed = 1;last = seg;if(!first) {first=seg;}
963 } else if(seg->delta.x > 0) {
964 // ignore segment w/ positive slope
966 last = seg;if(!first) {first=seg;}
967 double d1 = LINE_EQ(box.left1, seg);
968 double d2 = LINE_EQ(box.left2, seg);
971 insert_point_into_segment(status, seg, box.right2);
979 segrange_test_segment_min(range, last, y);
980 segrange_test_segment_max(range, first, y);
983 /* segments ending in the current scanline need xrow treatment like everything else.
984 (consider an intersection taking place just above a nearly horizontal segment
985 ending on the current scanline- the intersection would snap down *below* the
986 ending segment if we don't add the intersection point to the latter right away)
987 we need to treat ending segments seperately, however. we have to delete them from
988 the active list right away to make room for intersect operations (which might
989 still be in the current scanline- consider two 45° polygons and a vertical polygon
990 intersecting on an integer coordinate). but once they're no longer in the active list,
991 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
992 them to the active list just for point snapping would be overkill.
993 (One other option to consider, however, would be to create a new active list only
996 static void add_points_to_ending_segments(status_t*status, int32_t y)
998 segment_t*seg = status->ending_segments;
1000 segment_t*next = seg->right;seg->right=0;
1002 assert(seg->b.y == status->y);
1004 if(status->xrow->num == 1) {
1006 assert(seg->b.x == status->xrow->x[0]);
1007 point_t p = {status->xrow->x[0], y};
1008 insert_point_into_segment(status, seg, p);
1011 int start=0,end=status->xrow->num,dir=1;
1012 if(seg->delta.x < 0) {
1013 start = status->xrow->num-1;
1019 for(t=start;t!=end;t+=dir) {
1020 box_t box = box_new(status->xrow->x[t], y);
1021 double d0 = LINE_EQ(box.left1, seg);
1022 double d1 = LINE_EQ(box.left2, seg);
1023 double d2 = LINE_EQ(box.right1, seg);
1024 double d3 = LINE_EQ(box.right2, seg);
1025 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
1026 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
1027 insert_point_into_segment(status, seg, box.right2);
1036 /* we *need* to find a point to insert. the segment's own end point
1037 is in that list, for Pete's sake. */
1041 // now that this is done, too, we can also finally free this segment
1042 segment_destroy(seg);
1045 status->ending_segments = 0;
1048 static void recalculate_windings(status_t*status, segrange_t*range)
1051 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
1053 segrange_adjust_endpoints(range, status->y);
1055 segment_t*s = range->segmin;
1056 segment_t*end = range->segmax;
1060 s = actlist_leftmost(status->actlist);
1062 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
1063 s == range->segmin?"S":(
1064 s == range->segmax?"E":""));
1067 fprintf(stderr, "\n");
1071 /* test sanity: verify that we don't have changed segments
1072 outside of the given range */
1073 s = actlist_leftmost(status->actlist);
1074 while(s && s!=range->segmin) {
1075 assert(!s->changed);
1078 s = actlist_rightmost(status->actlist);
1079 while(s && s!=range->segmax) {
1080 assert(!s->changed);
1083 /* in check mode, go through the whole interval so we can test
1084 that all polygons where the edgestyle changed also have seg->changed=1 */
1085 s = actlist_leftmost(status->actlist);
1096 segment_t* left = actlist_left(status->actlist, s);
1097 windstate_t wind = left?left->wind:status->windrule->start(status->context);
1098 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
1099 edgestyle_t*fs_old = s->fs_out;
1100 s->fs_out = status->windrule->diff(&wind, &s->wind);
1103 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",
1104 fs_old?"draw":"omit", s->fs_out?"draw":"omit",
1105 fs_old!=s->fs_out?"CHANGED":"");
1107 assert(!(!s->changed && fs_old!=s->fs_out));
1118 /* we need to handle horizontal lines in order to add points to segments
1119 we otherwise would miss during the windrule re-evaluation */
1120 static void intersect_with_horizontal(status_t*status, segment_t*h)
1122 segment_t* left = actlist_find(status->actlist, h->a, h->a);
1123 segment_t* right = actlist_find(status->actlist, h->b, h->b);
1125 /* h->a.x is not strictly necessary, as it's also done by the event */
1126 xrow_add(status->xrow, h->a.x);
1127 xrow_add(status->xrow, h->b.x);
1134 left = actlist_right(status->actlist, left); //first seg to the right of h->a
1135 right = right->right; //first seg to the right of h->b
1136 segment_t* s = left;
1141 int32_t x = XPOS_INT(s, status->y);
1142 point_t p = {x, status->y};
1144 fprintf(stderr, "...intersecting with [%d] (%.2f,%.2f) -> (%.2f,%.2f) at (%.2f,%.2f)\n",
1146 s->a.x * status->gridsize, s->a.y * status->gridsize,
1147 s->b.x * status->gridsize, s->b.y * status->gridsize,
1148 x * status->gridsize, status->y * status->gridsize
1151 assert(x >= h->a.x);
1152 assert(x <= h->b.x);
1153 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
1154 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
1155 xrow_add(status->xrow, x);
1162 /* while, for a scanline, we need both starting as well as ending segments in order
1163 to *reconstruct* horizontal lines, we only need one or the other to *process*
1164 horizontal lines from the input data.
1166 So horizontal lines are processed twice: first they create hotpixels by intersecting
1167 all segments on the scanline (EVENT_HORIZTONAL). Secondly, they are processed for
1168 their actual content. The second also happens for all segments that received more than
1169 one point in this scanline.
1171 void horiz_reset(horizdata_t*horiz)
1176 void horiz_destroy(horizdata_t*horiz)
1178 if(horiz->data) rfx_free(horiz->data);
1182 static windstate_t get_horizontal_first_windstate(status_t*status, int x1, int x2)
1184 point_t p1 = {x1,status->y};
1185 point_t p2 = {x2,status->y};
1186 segment_t*left = actlist_find(status->actlist, p1, p2);
1188 segment_t*a = actlist_right(status->actlist, left);
1190 if(a->pos.y == status->y) {
1191 /* we need to iterate through all segments that received a point in this
1192 scanline, as actlist_find above will miss (positively sloped) segments
1193 that are to the right of (x1,y) only as long as we don't take the
1194 hotpixel re-routing into account
1195 TODO: this is inefficient, we should probably be iterating through the
1196 hotpixels on this scanline.
1206 assert(!left || left->fs_out_ok);
1208 fprintf(stderr, " fragment %.2f..%.2f\n",
1209 x1 * status->gridsize,
1210 x2 * status->gridsize);
1212 fprintf(stderr, " segment [%d] (%.2f,%.2f -> %.2f,%2f, at %.2f,%.2f) is to the left\n",
1214 left->a.x * status->gridsize,
1215 left->a.y * status->gridsize,
1216 left->b.x * status->gridsize,
1217 left->b.y * status->gridsize,
1218 left->pos.x * status->gridsize,
1219 left->pos.y * status->gridsize
1221 /* this segment might be a distance away from the left point
1222 of the horizontal line if the horizontal line belongs to a stroke
1223 with segments that just ended (so this horizontal line appears to
1224 be "floating in space" from our current point of view)
1225 assert(left->pos.y == h->y && left->pos.x == h->x1);
1229 return left?left->wind:status->windrule->start(status->context);
1232 static windstate_t process_horizontal_fragment(status_t*status, horizontal_t*h, int x1, int x2, windstate_t below)
1234 windstate_t above = status->windrule->add(status->context, below, h->fs, h->dir, h->polygon_nr);
1235 edgestyle_t*fs = status->windrule->diff(&above, &below);
1237 segment_dir_t dir = above.is_filled?DIR_DOWN:DIR_UP;
1238 point_t p1 = {x1,h->y};
1239 point_t p2 = {x2,h->y};
1242 //append_stroke(status, p1, p2, DIR_INVERT(h->dir), fs);
1243 append_stroke(status, p1, p2, dir, fs);
1246 fprintf(stderr, " ...%s (below: (wind_nr=%d, filled=%d), above: (wind_nr=%d, filled=%d) %s %d-%d\n",
1247 fs?"storing":"ignoring",
1248 below.wind_nr, below.is_filled,
1249 above.wind_nr, above.is_filled,
1250 dir==DIR_UP?"up":"down", x1, x2);
1255 typedef enum {hevent_hotpixel,hevent_end,hevent_start} horizontal_event_type_t;
1256 typedef struct _hevent {
1259 horizontal_event_type_t type;
1262 typedef struct _hevents {
1267 static int compare_hevents(const void *_e1, const void *_e2)
1269 hevent_t*e1 = (hevent_t*)_e1;
1270 hevent_t*e2 = (hevent_t*)_e2;
1271 int diff = e1->x - e2->x;
1272 if(diff) return diff;
1273 return e1->type - e2->type; //schedule hotpixel before hend
1276 static hevents_t hevents_fill(status_t*status)
1278 horizdata_t*horiz = &status->horiz;
1279 xrow_t*xrow = status->xrow;
1282 e.events = malloc(sizeof(hevent_t)*(horiz->num*2 + xrow->num));
1286 for(t=0;t<horiz->num;t++) {
1287 assert(horiz->data[t].x1 != horiz->data[t].x2);
1288 e.events[e.num].x = horiz->data[t].x1;
1289 e.events[e.num].h = &horiz->data[t];
1290 e.events[e.num].type = hevent_start;
1292 e.events[e.num].x = horiz->data[t].x2;
1293 e.events[e.num].h = &horiz->data[t];
1294 e.events[e.num].type = hevent_end;
1297 for(t=0;t<xrow->num;t++) {
1298 e.events[e.num].x = status->xrow->x[t];
1299 e.events[e.num].h = 0;
1300 e.events[e.num].type = hevent_hotpixel;
1303 qsort(e.events, e.num, sizeof(hevent_t), compare_hevents);
1308 static void process_horizontals(status_t*status)
1310 horizdata_t*horiz = &status->horiz;
1315 hevents_t events = hevents_fill(status);
1317 horizontal_t**open = malloc(sizeof(horizontal_t*)*horiz->num);
1320 for(t=0;t<events.num;t++) {
1321 hevent_t*e = &events.events[t];
1324 e->h->pos = num_open;
1325 open[num_open++] = e->h;
1327 fprintf(stderr, "horizontal (y=%.2f): %.2f -> %.2f dir=%s fs=%p\n",
1328 e->h->y * status->gridsize,
1329 e->h->x1 * status->gridsize,
1330 e->h->x2 * status->gridsize,
1331 e->h->dir==DIR_UP?"up":"down", e->h->fs);
1333 assert(e->h->y == status->y);
1334 assert(xrow_contains(status->xrow, e->h->x1));
1335 assert(xrow_contains(status->xrow, e->h->x2));
1340 open[num_open]->pos = e->h->pos;
1341 open[e->h->pos] = open[num_open];
1344 case hevent_hotpixel:
1347 for(s=0;s<num_open;s++) {
1348 int x1 = open[s]->xpos;
1350 assert(status->y == open[s]->y);
1352 below = get_horizontal_first_windstate(status, x1, x2);
1353 open[s]->xpos = e->x;
1355 below = process_horizontal_fragment(status, open[s], x1, x2, below);
1362 free(events.events);
1365 static void store_horizontal(status_t*status, point_t p1, point_t p2, edgestyle_t*fs, segment_dir_t dir, int polygon_nr)
1367 assert(p1.y == p2.y);
1368 assert(p1.x != p2.x); // TODO: can this happen?
1371 dir = DIR_INVERT(dir);
1378 /* TODO: convert this into a linked list */
1379 if(status->horiz.size == status->horiz.num) {
1380 if(!status->horiz.size)
1381 status->horiz.size = 16;
1382 status->horiz.size *= 2;
1383 status->horiz.data = rfx_realloc(status->horiz.data, sizeof(status->horiz.data[0])*status->horiz.size);
1385 horizontal_t*h = &status->horiz.data[status->horiz.num++];
1392 h->polygon_nr = polygon_nr;
1396 static void event_apply(status_t*status, event_t*e)
1399 event_dump(status, e);
1403 case EVENT_HORIZONTAL: {
1404 segment_t*s = e->s1;
1405 intersect_with_horizontal(status, s);
1406 store_horizontal(status, s->a, s->b, s->fs, s->dir, s->polygon_nr);
1407 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos, status->gridsize);
1408 segment_destroy(s);e->s1=0;
1412 //delete segment from list
1413 segment_t*s = e->s1;
1415 dict_del(status->intersecting_segs, s);
1416 dict_del(status->segs_with_point, s);
1417 assert(!dict_contains(status->intersecting_segs, s));
1418 assert(!dict_contains(status->segs_with_point, s));
1420 segment_t*left = s->left;
1421 segment_t*right = s->right;
1422 actlist_delete(status->actlist, s);
1424 schedule_crossing(status, left, right);
1426 /* schedule segment for xrow handling */
1427 s->left = 0; s->right = status->ending_segments;
1428 status->ending_segments = s;
1429 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos, status->gridsize);
1433 //insert segment into list
1434 segment_t*s = e->s1;
1435 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1436 actlist_insert(status->actlist, s->a, s->b, s);
1437 segment_t*left = s->left;
1438 segment_t*right = s->right;
1440 schedule_crossing(status, left, s);
1442 schedule_crossing(status, s, right);
1443 schedule_endpoint(status, s);
1447 // exchange two segments
1448 if(e->s1->right == e->s2) {
1449 assert(e->s2->left == e->s1);
1450 exchange_two(status, e);
1452 assert(e->s2->left != e->s1);
1454 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1456 #ifndef DONT_REMEMBER_CROSSINGS
1457 /* ignore this crossing for now (there are some line segments in between).
1458 it'll get rescheduled as soon as the "obstacles" are gone */
1459 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1460 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1461 assert(del1 && del2);
1467 #ifndef DONT_REMEMBER_CROSSINGS
1468 assert(dict_contains(status->seen_crossings, &pair));
1469 dict_del(status->seen_crossings, &pair);
1478 static void check_status(status_t*status)
1480 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1481 if((s->pos.x != s->b.x ||
1482 s->pos.y != s->b.y) &&
1483 !dict_contains(status->segs_with_point, s)) {
1484 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1486 s->delta.x<0?"-":"+",
1494 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context)
1496 current_polygon = poly1;
1499 memset(&status, 0, sizeof(status_t));
1500 status.gridsize = poly1->gridsize;
1502 queue_init(&status.queue);
1503 gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1505 assert(poly1->gridsize == poly2->gridsize);
1506 gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1509 status.windrule = windrule;
1510 status.context = context;
1511 status.actlist = actlist_new();
1514 status.seen_crossings = dict_new2(&point_type);
1515 int32_t lasty=-0x80000000;
1518 status.xrow = xrow_new();
1520 event_t*e = queue_get(&status.queue);
1525 assert(status.y>=lasty);
1527 status.intersecting_segs = dict_new2(&ptr_type);
1528 status.segs_with_point = dict_new2(&ptr_type);
1532 fprintf(stderr, "----------------------------------- %.2f\n", status.y * status.gridsize);
1533 actlist_dump(status.actlist, status.y-1, status.gridsize);
1536 actlist_verify(status.actlist, status.y-1);
1538 xrow_reset(status.xrow);
1539 horiz_reset(&status.horiz);
1542 xrow_add(status.xrow, e->p.x);
1543 event_apply(&status, e);
1545 e = queue_get(&status.queue);
1546 } while(e && status.y == e->p.y);
1548 xrow_sort(status.xrow);
1550 memset(&range, 0, sizeof(range));
1552 actlist_dump(status.actlist, status.y, status.gridsize);
1553 xrow_dump(status.xrow, 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);
1561 actlist_verify(status.actlist, status.y);
1562 process_horizontals(&status);
1564 check_status(&status);
1565 dict_destroy(status.intersecting_segs);
1566 dict_destroy(status.segs_with_point);
1570 dict_destroy(status.seen_crossings);
1572 actlist_destroy(status.actlist);
1573 queue_destroy(&status.queue);
1574 horiz_destroy(&status.horiz);
1575 xrow_destroy(status.xrow);
1577 gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1578 p->gridsize = poly1->gridsize;
1579 p->strokes = status.strokes;
1582 /* we only add segments with non-empty edgestyles to strokes in
1583 recalculate_windings, but better safe than sorry */
1584 gfxpolystroke_t*stroke = p->strokes;
1587 stroke = stroke->next;
1593 static windcontext_t twopolygons = {2};
1594 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1596 return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons);
1598 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1600 return gfxpoly_process(p1, p2, &windrule_union, &twopolygons);