14 static gfxpoly_t*current_polygon = 0;
15 void gfxpoly_fail(char*expr, char*file, int line, const char*function)
17 if(!current_polygon) {
18 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
22 void*md5 = initialize_md5();
25 gfxpolystroke_t*stroke = current_polygon->strokes;
26 for(;stroke;stroke=stroke->next) {
27 for(t=0;t<stroke->num_points;t++) {
28 update_md5(md5, (unsigned char*)&stroke->points[t].x, sizeof(stroke->points[t].x));
29 update_md5(md5, (unsigned char*)&stroke->points[t].y, sizeof(stroke->points[t].y));
33 char filename[32+4+1];
35 sprintf(filename, "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x.ps",
36 h[0],h[1],h[2],h[3],h[4],h[5],h[6],h[7],h[8],h[9],h[10],h[11],h[12],h[13],h[14],h[15]);
38 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
39 fprintf(stderr, "I'm saving a debug file \"%s\" to the current directory.\n", filename);
41 gfxpoly_save(current_polygon, filename);
45 static char point_equals(const void*o1, const void*o2)
47 const point_t*p1 = o1;
48 const point_t*p2 = o2;
49 return p1->x == p2->x && p1->y == p2->y;
51 static unsigned int point_hash(const void*o)
56 static void* point_dup(const void*o)
59 point_t*n = malloc(sizeof(point_t));
64 static void point_free(void*o)
78 typedef struct _event {
85 /* compare_events_simple differs from compare_events in that it schedules
86 events from left to right regardless of type. It's only used in horizontal
87 processing, in order to get an x-wise sorting of the current scanline */
88 static inline int compare_events_simple(const void*_a,const void*_b)
90 event_t* a = (event_t*)_a;
91 event_t* b = (event_t*)_b;
92 int d = b->p.y - a->p.y;
99 static inline int compare_events(const void*_a,const void*_b)
101 event_t* a = (event_t*)_a;
102 event_t* b = (event_t*)_b;
103 int d = b->p.y - a->p.y;
105 /* we need to schedule end after intersect (so that a segment about
106 to end has a chance to tear up a few other segs first) and start
107 events after end (in order not to confuse the intersection check, which
108 assumes there's an actual y overlap between active segments, and
109 because ending segments in the active list make it difficult to insert
110 starting segments at the right position)).
111 Horizontal lines come last, because the only purpose
112 they have is to create snapping coordinates for the segments (still)
113 existing in this scanline.
115 d = b->type - a->type;
119 /* I don't see any reason why we would need to order by x- at least as long
120 as we do horizontal lines in a seperate pass */
121 //d = b->p.x - a->p.x;
125 #define COMPARE_EVENTS(x,y) (compare_events(x,y)>0)
126 #define COMPARE_EVENTS_SIMPLE(x,y) (compare_events_simple(x,y)>0)
127 HEAP_DEFINE(queue,event_t,COMPARE_EVENTS);
128 HEAP_DEFINE(hqueue,event_t,COMPARE_EVENTS_SIMPLE);
130 typedef struct _horizontal {
138 typedef struct _horizdata {
144 typedef struct _status {
151 windcontext_t*context;
152 segment_t*ending_segments;
156 gfxpolystroke_t*strokes;
158 dict_t*seen_crossings; //list of crossing we saw so far
159 dict_t*intersecting_segs; //list of segments intersecting in this scanline
160 dict_t*segs_with_point; //lists of segments that received a point in this scanline
165 int gfxpoly_num_segments(gfxpoly_t*poly)
167 gfxpolystroke_t*stroke = poly->strokes;
169 for(;stroke;stroke=stroke->next) {
174 int gfxpoly_size(gfxpoly_t*poly)
178 gfxpolystroke_t*stroke = poly->strokes;
179 for(;stroke;stroke=stroke->next) {
180 edges += stroke->num_points-1;
185 char gfxpoly_check(gfxpoly_t*poly, char updown)
187 current_polygon = poly;
188 dict_t*d1 = dict_new2(&point_type);
189 dict_t*d2 = dict_new2(&point_type);
191 gfxpolystroke_t*stroke = poly->strokes;
192 for(;stroke;stroke=stroke->next) {
193 /* In order to not confuse the fill/wind logic, existing segments must have
194 a non-zero edge style */
197 /* put all the segments into dictionaries so that we can check
198 that the endpoint multiplicity is two */
199 for(s=0;s<stroke->num_points;s++) {
200 point_t p = stroke->points[s];
201 int num_xor = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
202 int num_circ = (s>=1 && s<stroke->num_points-1)?0:(s==0?1:-1);
203 if(stroke->dir==DIR_UP)
206 if(!dict_contains(d1, &p)) {
207 dict_put(d1, &p, (void*)(ptroff_t)num_xor);
209 assert(!dict_contains(d2, &p));
210 dict_put(d2, &p, (void*)(ptroff_t)num_circ);
213 int count = (ptroff_t)dict_lookup(d1, &p);
216 dict_put(d1, &p, (void*)(ptroff_t)count);
219 assert(dict_contains(d2, &p));
220 count = (ptroff_t)dict_lookup(d2, &p);
223 dict_put(d2, &p, (void*)(ptroff_t)count);
228 DICT_ITERATE_ITEMS(d1, point_t*, p1, void*, c1) {
229 int count = (ptroff_t)c1;
231 fprintf(stderr, "Error: Point (%.2f,%.2f) occurs %d times\n", p1->x * poly->gridsize, p1->y * poly->gridsize, count);
239 DICT_ITERATE_ITEMS(d2, point_t*, p2, void*, c2) {
240 int count = (ptroff_t)c2;
242 if(count>0) fprintf(stderr, "Error: Point (%.2f,%.2f) has %d more incoming than outgoing segments\n", p2->x * poly->gridsize, p2->y * poly->gridsize, count);
243 if(count<0) fprintf(stderr, "Error: Point (%.2f,%.2f) has %d more outgoing than incoming segments\n", p2->x * poly->gridsize, p2->y * poly->gridsize, -count);
253 void gfxpoly_dump(gfxpoly_t*poly)
256 double g = poly->gridsize;
257 fprintf(stderr, "polyon %p (gridsize: %.2f)\n", poly, poly->gridsize);
258 gfxpolystroke_t*stroke = poly->strokes;
259 for(;stroke;stroke=stroke->next) {
260 fprintf(stderr, "%11p", stroke);
261 if(stroke->dir==DIR_UP) {
262 for(s=stroke->num_points-1;s>=1;s--) {
263 point_t a = stroke->points[s];
264 point_t b = stroke->points[s-1];
265 fprintf(stderr, "%s (%.2f,%.2f) -> (%.2f,%.2f)%s%s\n", s!=stroke->num_points-1?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
266 s==1?"]":"", a.y==b.y?"H":"");
269 for(s=0;s<stroke->num_points-1;s++) {
270 point_t a = stroke->points[s];
271 point_t b = stroke->points[s+1];
272 fprintf(stderr, "%s (%.2f,%.2f) -> (%.2f,%.2f)%s%s\n", s?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
273 s==stroke->num_points-2?"]":"", a.y==b.y?"H":"");
279 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
281 FILE*fi = fopen(filename, "wb");
282 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
283 fprintf(fi, "%% begin\n");
285 gfxpolystroke_t*stroke = poly->strokes;
286 for(;stroke;stroke=stroke->next) {
287 fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
288 point_t p = stroke->points[0];
289 fprintf(fi, "%d %d moveto\n", p.x, p.y);
290 for(s=1;s<stroke->num_points;s++) {
291 p = stroke->points[s];
292 fprintf(fi, "%d %d lineto\n", p.x, p.y);
294 fprintf(fi, "stroke\n");
296 fprintf(fi, "showpage\n");
300 void gfxpoly_save_arrows(gfxpoly_t*poly, const char*filename)
302 FILE*fi = fopen(filename, "wb");
303 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
304 fprintf(fi, "%% begin\n");
306 double l = 5.0 / poly->gridsize;
307 double g = poly->gridsize;
308 gfxpolystroke_t*stroke = poly->strokes;
309 for(;stroke;stroke=stroke->next) {
310 fprintf(fi, "%g setgray\n", 0);
312 int s = stroke->dir==DIR_UP?stroke->num_points-1:0;
313 int end = stroke->dir==DIR_UP?-1:stroke->num_points;
314 int dir = stroke->dir==DIR_UP?-1:1;
316 point_t p = stroke->points[s];
319 fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
320 for(;s!=end;s+=dir) {
321 p = stroke->points[s];
324 double d = sqrt(lx*lx+ly*ly);
328 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
329 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 + (ly*d))*g,
330 (p.y - ly*d2 - (lx*d))*g);
331 fprintf(fi, "%f %f lineto\n", p.x * g, p.y * g);
332 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 - (ly*d))*g,
333 (p.y - ly*d2 + (lx*d))*g);
334 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
335 fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
338 fprintf(fi, "stroke\n");
340 fprintf(fi, "showpage\n");
344 inline static event_t* event_new()
346 event_t*e = rfx_calloc(sizeof(event_t));
349 inline static void event_free(event_t*e)
354 static void event_dump(status_t*status, event_t*e)
356 if(e->type == EVENT_HORIZONTAL) {
357 fprintf(stderr, "Horizontal [%d] (%.2f,%.2f) -> (%.2f,%.2f)\n", (int)e->s1->nr,
358 e->s1->a.x * status->gridsize, e->s1->a.y * status->gridsize, e->s1->b.x * status->gridsize, e->s1->b.y * status->gridsize);
359 } else if(e->type == EVENT_START) {
360 fprintf(stderr, "event: segment [%d] starts at (%.2f,%.2f)\n", (int)e->s1->nr,
361 e->p.x * status->gridsize, e->p.y * status->gridsize);
362 } else if(e->type == EVENT_END) {
363 fprintf(stderr, "event: segment [%d] ends at (%.2f,%.2f)\n", (int)e->s1->nr,
364 e->p.x * status->gridsize, e->p.y * status->gridsize);
365 } else if(e->type == EVENT_CROSS) {
366 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%.2f,%.2f)\n", (int)e->s1->nr, (int)e->s2->nr,
367 e->p.x * status->gridsize, e->p.y * status->gridsize);
373 static inline int32_t max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
374 static inline int32_t min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
376 static void segment_dump(segment_t*s)
378 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", (int)s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
379 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f fs=%p\n", s->delta.x, s->delta.y, s->k,
380 (double)s->delta.x / s->delta.y, s->fs);
383 static void segment_init(segment_t*s, int32_t x1, int32_t y1, int32_t x2, int32_t y2, int polygon_nr, segment_dir_t dir)
385 static int segment_count=0;
386 s->nr = segment_count++;
391 /* We need to make sure horizontal segments always go from left to right.
392 "up/down" for horizontal segments is handled by "rotating"
393 them 90° counterclockwise in screen coordinates (tilt your head to
394 the right). In other words, the "normal" direction (what's positive dy for
395 vertical segments) is positive dx for horizontal segments ("down" is right).
398 s->dir = DIR_INVERT(s->dir);
399 int32_t x = x1;x1=x2;x2=x;
400 int32_t y = y1;y1=y2;y2=y;
402 fprintf(stderr, "Scheduling horizontal segment [%d] (%.2f,%.2f) -> (%.2f,%.2f) %s\n",
404 x1 * 0.05, y1 * 0.05, x2 * 0.05, y2 * 0.05, s->dir==DIR_UP?"up":"down");
410 s->k = (double)x1*y2-(double)x2*y1;
411 s->left = s->right = 0;
414 s->minx = min32(x1,x2);
415 s->maxx = max32(x1,x2);
418 s->polygon_nr = polygon_nr;
421 /* notice: on some systems (with some compilers), for the line
422 (1073741823,-1073741824)->(1073741823,1073741823)
423 we get LINE_EQ(s->a, s) == 1.
424 That's why we now clamp to 26 bit.
426 assert(LINE_EQ(s->a, s) == 0);
427 assert(LINE_EQ(s->b, s) == 0);
429 /* check that all signs are in order:
437 p.x = min32(s->a.x, s->b.x);
438 assert(LINE_EQ(p, s) <= 0);
439 p.x = max32(s->a.x, s->b.x);
440 assert(LINE_EQ(p, s) >= 0);
443 #ifndef DONT_REMEMBER_CROSSINGS
444 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
448 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
450 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
451 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
455 static void segment_clear(segment_t*s)
457 #ifndef DONT_REMEMBER_CROSSINGS
458 dict_clear(&s->scheduled_crossings);
461 static void segment_destroy(segment_t*s)
467 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos, double gridsize)
472 /* we need to queue multiple segments at once because we need to process start events
473 before horizontal events */
474 while(pos < stroke->num_points-1) {
475 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
476 s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
484 fprintf(stderr, "[%d] (%.2f,%.2f) -> (%.2f,%.2f) %s (stroke %p, %d more to come)\n",
485 s->nr, s->a.x * gridsize, s->a.y * gridsize,
486 s->b.x * gridsize, s->b.y * gridsize,
487 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
489 event_t* e = event_new();
490 e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
495 if(queue) queue_put(queue, e);
496 else hqueue_put(hqueue, e);
498 if(e->type != EVENT_HORIZONTAL) {
508 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
511 gfxpolystroke_t*stroke = p->strokes;
512 for(;stroke;stroke=stroke->next) {
513 assert(stroke->num_points > 1);
517 for(s=0;s<stroke->num_points-1;s++) {
518 assert(stroke->points[s].y <= stroke->points[s+1].y);
521 advance_stroke(queue, hqueue, stroke, polygon_nr, 0, p->gridsize);
525 static void schedule_endpoint(status_t*status, segment_t*s)
527 // schedule end point of segment
528 assert(s->b.y > status->y);
529 event_t*e = event_new();
534 queue_put(&status->queue, e);
537 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
539 /* the code that's required (and the checks you can perform) before
540 it can be said with 100% certainty that we indeed have a valid crossing
541 amazes me every time. -mk */
544 assert(s1->right == s2);
545 assert(s2->left == s1);
546 int32_t miny1 = min32(s1->a.y,s1->b.y);
547 int32_t maxy1 = max32(s1->a.y,s1->b.y);
548 int32_t miny2 = min32(s2->a.y,s2->b.y);
549 int32_t maxy2 = max32(s2->a.y,s2->b.y);
550 int32_t minx1 = min32(s1->a.x,s1->b.x);
551 int32_t minx2 = min32(s2->a.x,s2->b.x);
552 int32_t maxx1 = max32(s1->a.x,s1->b.x);
553 int32_t maxx2 = max32(s2->a.x,s2->b.x);
554 /* check that precomputation is sane */
555 assert(minx1 == s1->minx && minx2 == s2->minx);
556 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
557 /* both segments are active, so this can't happen */
558 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
559 /* we know that right now, s2 is to the right of s1, so there's
560 no way the complete bounding box of s1 is to the right of s1 */
561 assert(!(s1->minx > s2->maxx));
562 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
565 if(s1->maxx <= s2->minx) {
567 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
569 /* bounding boxes don't intersect */
573 #ifndef DONT_REMEMBER_CROSSINGS
574 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
575 /* FIXME: this whole segment hashing thing is really slow */
577 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
578 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
579 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
582 return; // we already know about this one
586 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
589 // lines are exactly on top of each other (ignored)
591 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
596 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
598 /* lines are parallel */
603 double asign2 = LINE_EQ(s1->a, s2);
605 // segment1 touches segment2 in a single point (ignored)
607 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
611 double bsign2 = LINE_EQ(s1->b, s2);
613 // segment1 touches segment2 in a single point (ignored)
615 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
620 if(asign2<0 && bsign2<0) {
621 // segment1 is completely to the left of segment2
623 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);
627 if(asign2>0 && bsign2>0) {
628 // segment1 is completely to the right of segment2
629 #ifndef DONT_REMEMBER_CROSSINGS
633 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);
638 double asign1 = LINE_EQ(s2->a, s1);
640 // segment2 touches segment1 in a single point (ignored)
642 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
646 double bsign1 = LINE_EQ(s2->b, s1);
648 // segment2 touches segment1 in a single point (ignored)
650 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
655 if(asign1<0 && bsign1<0) {
656 // segment2 is completely to the left of segment1
657 #ifndef DONT_REMEMBER_CROSSINGS
661 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);
665 if(asign1>0 && bsign1>0) {
666 // segment2 is completely to the right of segment1
668 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);
673 #ifdef DONT_REMEMBER_CROSSINGS
674 /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
675 there's not way s2 would be to the left of s1 otherwise */
676 if(asign1<0 && bsign1>0) return;
677 if(asign2>0 && bsign2<0) return;
680 assert(!(asign1<0 && bsign1>0));
681 assert(!(asign2>0 && bsign2<0));
683 /* TODO: should we precompute these? */
684 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
685 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
688 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
689 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
691 assert(p.y >= status->y);
693 assert(p.x >= s1->minx && p.x <= s1->maxx);
694 assert(p.x >= s2->minx && p.x <= s2->maxx);
699 #ifndef DONT_REMEMBER_CROSSINGS
700 assert(!dict_contains(status->seen_crossings, &pair));
701 dict_put(status->seen_crossings, &pair, 0);
705 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
708 #ifndef DONT_REMEMBER_CROSSINGS
709 /* we insert into each other's intersection history because these segments might switch
710 places and we still want to look them up quickly after they did */
711 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
712 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
715 event_t* e = event_new();
716 e->type = EVENT_CROSS;
720 queue_put(&status->queue, e);
724 static void exchange_two(status_t*status, event_t*e)
726 //exchange two segments in list
727 segment_t*s1 = e->s1;
728 segment_t*s2 = e->s2;
730 if(!dict_contains(status->intersecting_segs, s1))
731 dict_put(status->intersecting_segs, s1, 0);
732 if(!dict_contains(status->intersecting_segs, s2))
733 dict_put(status->intersecting_segs, s2, 0);
735 assert(s2->left == s1);
736 assert(s1->right == s2);
737 actlist_swap(status->actlist, s1, s2);
738 assert(s2->right == s1);
739 assert(s1->left == s2);
740 segment_t*left = s2->left;
741 segment_t*right = s1->right;
743 schedule_crossing(status, left, s2);
745 schedule_crossing(status, s1, right);
748 typedef struct _box {
749 point_t left1, left2, right1, right2;
751 static inline box_t box_new(int32_t x, int32_t y)
754 box.right1.x = box.right2.x = x;
755 box.left1.x = box.left2.x = x-1;
756 box.left1.y = box.right1.y = y-1;
757 box.left2.y = box.right2.y = y;
761 static void store_horizontal(status_t*status, point_t p1, point_t p2, edgestyle_t*fs, segment_dir_t dir, int polygon_nr);
763 static void append_stroke(status_t*status, point_t a, point_t b, segment_dir_t dir, edgestyle_t*fs)
765 gfxpolystroke_t*stroke = status->strokes;
766 /* find a stoke to attach this segment to. It has to have an endpoint
767 matching our start point, and a matching edgestyle */
769 point_t p = stroke->points[stroke->num_points-1];
770 if(p.x == a.x && p.y == a.y && stroke->fs == fs && stroke->dir == dir)
772 stroke = stroke->next;
775 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
778 stroke->next = status->strokes;
779 status->strokes = stroke;
780 stroke->points_size = 2;
781 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
782 stroke->points[0] = a;
783 stroke->num_points = 1;
784 } else if(stroke->num_points == stroke->points_size) {
786 stroke->points_size *= 2;
787 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
789 stroke->points[stroke->num_points++] = b;
792 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
794 assert(s->pos.x != p.x || s->pos.y != p.y);
797 if(!dict_contains(status->segs_with_point, s))
798 dict_put(status->segs_with_point, s, 0);
799 assert(s->fs_out_ok);
802 if(s->pos.y != p.y) {
803 /* non horizontal line- copy to output */
806 fprintf(stderr, "[%d] receives next point (%.2f,%.2f)->(%.2f,%.2f) (drawing)\n", s->nr,
807 s->pos.x * status->gridsize, s->pos.y * status->gridsize,
808 p.x * status->gridsize, p.y * status->gridsize);
810 segment_dir_t dir = s->wind.is_filled?DIR_DOWN:DIR_UP;
811 assert(s->pos.y != p.y);
812 append_stroke(status, s->pos, p, dir, s->fs_out);
815 fprintf(stderr, "[%d] receives next point (%.2f,%.2f) (omitting)\n", s->nr,
816 p.x * status->gridsize,
817 p.y * status->gridsize);
821 /* horizontal line. we need to look at this more closely at the end of this
823 store_horizontal(status, s->pos, p, s->fs, s->dir, s->polygon_nr);
829 typedef struct _segrange {
836 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
838 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
839 segment_t*min = range->segmin;
840 segment_t*max = range->segmax;
842 /* we need this because if two segments intersect exactly on
843 the scanline, segrange_test_segment_{min,max} can't tell which
844 one is smaller/larger */
845 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
848 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
854 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
857 /* we need to calculate the xpos anew (and can't use start coordinate or
858 intersection coordinate), because we need the xpos exactly at the end of
861 double x = XPOS(seg, y);
862 if(!range->segmin || x<range->xmin) {
867 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
870 double x = XPOS(seg, y);
871 if(!range->segmax || x>range->xmax) {
886 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
888 segment_t*first=0, *last = 0;
890 for(t=0;t<status->xrow->num;t++) {
891 box_t box = box_new(status->xrow->x[t], y);
892 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
894 seg = actlist_right(status->actlist, seg);
897 // this segment started in this scanline, ignore it
898 seg->changed = 1;last = seg;if(!first) {first=seg;}
899 } else if(seg->delta.x <= 0) {
900 // ignore segment w/ negative slope
902 last = seg;if(!first) {first=seg;}
903 double d1 = LINE_EQ(box.right1, seg);
904 double d2 = LINE_EQ(box.right2, seg);
907 insert_point_into_segment(status, seg, box.right2);
909 /* we unfortunately can't break here- the active list is sorted according
910 to the *bottom* of the scanline. hence pretty much everything that's still
911 coming might reach into our box */
918 segrange_test_segment_min(range, first, y);
919 segrange_test_segment_max(range, last, y);
929 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
931 segment_t*first=0, *last = 0;
933 for(t=status->xrow->num-1;t>=0;t--) {
934 box_t box = box_new(status->xrow->x[t], y);
935 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
939 // this segment started in this scanline, ignore it
940 seg->changed = 1;last = seg;if(!first) {first=seg;}
941 } else if(seg->delta.x > 0) {
942 // ignore segment w/ positive slope
944 last = seg;if(!first) {first=seg;}
945 double d1 = LINE_EQ(box.left1, seg);
946 double d2 = LINE_EQ(box.left2, seg);
949 insert_point_into_segment(status, seg, box.right2);
957 segrange_test_segment_min(range, last, y);
958 segrange_test_segment_max(range, first, y);
961 /* segments ending in the current scanline need xrow treatment like everything else.
962 (consider an intersection taking place just above a nearly horizontal segment
963 ending on the current scanline- the intersection would snap down *below* the
964 ending segment if we don't add the intersection point to the latter right away)
965 we need to treat ending segments seperately, however. we have to delete them from
966 the active list right away to make room for intersect operations (which might
967 still be in the current scanline- consider two 45° polygons and a vertical polygon
968 intersecting on an integer coordinate). but once they're no longer in the active list,
969 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
970 them to the active list just for point snapping would be overkill.
971 (One other option to consider, however, would be to create a new active list only
974 static void add_points_to_ending_segments(status_t*status, int32_t y)
976 segment_t*seg = status->ending_segments;
978 segment_t*next = seg->right;seg->right=0;
980 assert(seg->b.y == status->y);
982 if(status->xrow->num == 1) {
984 assert(seg->b.x == status->xrow->x[0]);
985 point_t p = {status->xrow->x[0], y};
986 insert_point_into_segment(status, seg, p);
989 int start=0,end=status->xrow->num,dir=1;
990 if(seg->delta.x < 0) {
991 start = status->xrow->num-1;
994 for(t=start;t!=end;t+=dir) {
995 box_t box = box_new(status->xrow->x[t], y);
996 double d0 = LINE_EQ(box.left1, seg);
997 double d1 = LINE_EQ(box.left2, seg);
998 double d2 = LINE_EQ(box.right1, seg);
999 double d3 = LINE_EQ(box.right2, seg);
1000 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
1001 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
1002 insert_point_into_segment(status, seg, box.right2);
1008 /* we *need* to find a point to insert. the segment's own end point
1009 is in that list, for Pete's sake. */
1013 // now that this is done, too, we can also finally free this segment
1014 segment_destroy(seg);
1017 status->ending_segments = 0;
1020 static void recalculate_windings(status_t*status, segrange_t*range)
1023 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
1025 segrange_adjust_endpoints(range, status->y);
1027 segment_t*s = range->segmin;
1028 segment_t*end = range->segmax;
1032 s = actlist_leftmost(status->actlist);
1034 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
1035 s == range->segmin?"S":(
1036 s == range->segmax?"E":""));
1039 fprintf(stderr, "\n");
1043 /* test sanity: verify that we don't have changed segments
1044 outside of the given range */
1045 s = actlist_leftmost(status->actlist);
1046 while(s && s!=range->segmin) {
1047 assert(!s->changed);
1050 s = actlist_rightmost(status->actlist);
1051 while(s && s!=range->segmax) {
1052 assert(!s->changed);
1055 /* in check mode, go through the whole interval so we can test
1056 that all polygons where the edgestyle changed also have seg->changed=1 */
1057 s = actlist_leftmost(status->actlist);
1068 segment_t* left = actlist_left(status->actlist, s);
1069 windstate_t wind = left?left->wind:status->windrule->start(status->context);
1070 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
1071 edgestyle_t*fs_old = s->fs_out;
1072 s->fs_out = status->windrule->diff(&wind, &s->wind);
1075 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",
1076 fs_old?"draw":"omit", s->fs_out?"draw":"omit",
1077 fs_old!=s->fs_out?"CHANGED":"");
1079 assert(!(!s->changed && fs_old!=s->fs_out));
1090 /* we need to handle horizontal lines in order to add points to segments
1091 we otherwise would miss during the windrule re-evaluation */
1092 static void intersect_with_horizontal(status_t*status, segment_t*h)
1094 segment_t* left = actlist_find(status->actlist, h->a, h->a);
1095 segment_t* right = actlist_find(status->actlist, h->b, h->b);
1097 /* h->a.x is not strictly necessary, as it's also done by the event */
1098 xrow_add(status->xrow, h->a.x);
1099 xrow_add(status->xrow, h->b.x);
1106 left = actlist_right(status->actlist, left); //first seg to the right of h->a
1107 right = right->right; //first seg to the right of h->b
1108 segment_t* s = left;
1113 int32_t x = XPOS_INT(s, status->y);
1114 point_t p = {x, status->y};
1116 fprintf(stderr, "...intersecting with [%d] (%.2f,%.2f) -> (%.2f,%.2f) at (%.2f,%.2f)\n",
1118 s->a.x * status->gridsize, s->a.y * status->gridsize,
1119 s->b.x * status->gridsize, s->b.y * status->gridsize,
1120 x * status->gridsize, status->y * status->gridsize
1123 assert(x >= h->a.x);
1124 assert(x <= h->b.x);
1125 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
1126 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
1127 xrow_add(status->xrow, x);
1134 /* while, for a scanline, we need both starting as well as ending segments in order
1135 to *reconstruct* horizontal lines, we only need one or the other to *process*
1136 horizontal lines from the input data.
1138 So horizontal lines are processed twice: first they create hotpixels by intersecting
1139 all segments on the scanline (EVENT_HORIZTONAL). Secondly, they are processed for
1140 their actual content. The second also happens for all segments that received more than
1141 one point in this scanline.
1143 void horiz_reset(horizdata_t*horiz)
1148 void horiz_destroy(horizdata_t*horiz)
1150 if(horiz->data) rfx_free(horiz->data);
1154 static int compare_horizontals(const void *_h1, const void *_h2)
1156 horizontal_t*h1 = (horizontal_t*)_h1;
1157 horizontal_t*h2 = (horizontal_t*)_h2;
1158 return h1->x1 - h2->x1;
1161 static void process_horizontals(status_t*status)
1163 horizdata_t*horiz = &status->horiz;
1164 qsort(horiz->data, horiz->num, sizeof(horizontal_t), compare_horizontals);
1167 for(t=0;t<horiz->num;t++) {
1168 horizontal_t*h = &horiz->data[t];
1170 fprintf(stderr, "horizontal (y=%.2f): %.2f -> %.2f dir=%s fs=%p\n",
1171 h->y * status->gridsize,
1172 h->x1 * status->gridsize,
1173 h->x2 * status->gridsize,
1174 h->dir==DIR_UP?"up":"down", h->fs);
1176 assert(h->y == status->y);
1177 assert(xrow_contains(status->xrow, h->x1));
1178 assert(xrow_contains(status->xrow, h->x2));
1180 int pos = xrow_find(status->xrow, h->x1);
1182 assert(pos <= status->xrow->num);
1183 assert(pos == status->xrow->num || status->xrow->x[pos] > x);
1186 int next_x = pos < status->xrow->num ? status->xrow->x[pos] : h->x2;
1191 point_t p1 = {x,h->y};
1192 point_t p2 = {next_x,h->y};
1193 segment_t* left = actlist_find(status->actlist, p1, p2);
1194 assert(!left || left->fs_out_ok);
1196 fprintf(stderr, " fragment %.2f..%.2f edge=%08x\n",
1197 x * status->gridsize,
1198 next_x * status->gridsize,
1201 fprintf(stderr, " segment [%d] (%.2f,%.2f -> %.2f,%2f, at %.2f,%.2f) is to the left\n",
1203 left->a.x * status->gridsize,
1204 left->a.y * status->gridsize,
1205 left->b.x * status->gridsize,
1206 left->b.y * status->gridsize,
1207 left->pos.x * status->gridsize,
1208 left->pos.y * status->gridsize
1210 /* this segment might be a distance away from the left point
1211 of the horizontal line if the horizontal line belongs to a stroke
1212 with segments that just ended (so this horizontal line appears to
1213 be "floating in space" from our current point of view)
1214 assert(left->pos.y == h->y && left->pos.x == h->x1);
1218 windstate_t below = left?left->wind:status->windrule->start(status->context);
1219 windstate_t above = status->windrule->add(status->context, below, h->fs, h->dir, h->polygon_nr);
1220 edgestyle_t*fs = status->windrule->diff(&above, &below);
1223 fprintf(stderr, " ...storing\n");
1225 append_stroke(status, p1, p2, DIR_INVERT(h->dir), fs);
1228 fprintf(stderr, " ...ignoring (below: (wind_nr=%d, filled=%d), above: (wind_nr=%d, filled=%d) %s\n",
1229 below.wind_nr, below.is_filled,
1230 above.wind_nr, above.is_filled,
1231 h->dir==DIR_UP?"up":"down"
1240 static void store_horizontal(status_t*status, point_t p1, point_t p2, edgestyle_t*fs, segment_dir_t dir, int polygon_nr)
1242 assert(p1.y == p2.y);
1243 assert(p1.x != p2.x); // TODO: can this happen?
1246 dir = DIR_INVERT(dir);
1253 if(status->horiz.size == status->horiz.num) {
1254 if(!status->horiz.size)
1255 status->horiz.size = 16;
1256 status->horiz.size *= 2;
1257 status->horiz.data = rfx_realloc(status->horiz.data, sizeof(status->horiz.data[0])*status->horiz.size);
1259 horizontal_t*h = &status->horiz.data[status->horiz.num++];
1265 h->polygon_nr = polygon_nr;
1269 static void event_apply(status_t*status, event_t*e)
1272 event_dump(status, e);
1276 case EVENT_HORIZONTAL: {
1277 segment_t*s = e->s1;
1278 intersect_with_horizontal(status, s);
1279 store_horizontal(status, s->a, s->b, s->fs, s->dir, s->polygon_nr);
1280 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos, status->gridsize);
1281 segment_destroy(s);e->s1=0;
1285 //delete segment from list
1286 segment_t*s = e->s1;
1288 dict_del(status->intersecting_segs, s);
1289 dict_del(status->segs_with_point, s);
1290 assert(!dict_contains(status->intersecting_segs, s));
1291 assert(!dict_contains(status->segs_with_point, s));
1293 segment_t*left = s->left;
1294 segment_t*right = s->right;
1295 actlist_delete(status->actlist, s);
1297 schedule_crossing(status, left, right);
1299 /* schedule segment for xrow handling */
1300 s->left = 0; s->right = status->ending_segments;
1301 status->ending_segments = s;
1302 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos, status->gridsize);
1306 //insert segment into list
1307 segment_t*s = e->s1;
1308 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1309 actlist_insert(status->actlist, s->a, s->b, s);
1310 segment_t*left = s->left;
1311 segment_t*right = s->right;
1313 schedule_crossing(status, left, s);
1315 schedule_crossing(status, s, right);
1316 schedule_endpoint(status, s);
1320 // exchange two segments
1321 if(e->s1->right == e->s2) {
1322 assert(e->s2->left == e->s1);
1323 exchange_two(status, e);
1325 assert(e->s2->left != e->s1);
1327 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1329 #ifndef DONT_REMEMBER_CROSSINGS
1330 /* ignore this crossing for now (there are some line segments in between).
1331 it'll get rescheduled as soon as the "obstacles" are gone */
1332 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1333 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1334 assert(del1 && del2);
1340 #ifndef DONT_REMEMBER_CROSSINGS
1341 assert(dict_contains(status->seen_crossings, &pair));
1342 dict_del(status->seen_crossings, &pair);
1351 static void check_status(status_t*status)
1353 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1354 if((s->pos.x != s->b.x ||
1355 s->pos.y != s->b.y) &&
1356 !dict_contains(status->segs_with_point, s)) {
1357 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1359 s->delta.x<0?"-":"+",
1367 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context)
1369 current_polygon = poly1;
1372 memset(&status, 0, sizeof(status_t));
1373 status.gridsize = poly1->gridsize;
1375 gfxpoly_dump(poly1);
1377 queue_init(&status.queue);
1378 gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1380 assert(poly1->gridsize == poly2->gridsize);
1381 gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1384 status.windrule = windrule;
1385 status.context = context;
1386 status.actlist = actlist_new();
1389 status.seen_crossings = dict_new2(&point_type);
1390 int32_t lasty=-0x80000000;
1393 status.xrow = xrow_new();
1395 event_t*e = queue_get(&status.queue);
1400 assert(status.y>=lasty);
1402 status.intersecting_segs = dict_new2(&ptr_type);
1403 status.segs_with_point = dict_new2(&ptr_type);
1407 fprintf(stderr, "----------------------------------- %.2f\n", status.y * status.gridsize);
1408 actlist_dump(status.actlist, status.y-1, status.gridsize);
1411 actlist_verify(status.actlist, status.y-1);
1413 xrow_reset(status.xrow);
1414 horiz_reset(&status.horiz);
1417 xrow_add(status.xrow, e->p.x);
1418 event_apply(&status, e);
1420 e = queue_get(&status.queue);
1421 } while(e && status.y == e->p.y);
1423 xrow_sort(status.xrow);
1425 memset(&range, 0, sizeof(range));
1427 actlist_dump(status.actlist, status.y, status.gridsize);
1429 xrow_dump(status.xrow, status.gridsize);
1430 add_points_to_positively_sloped_segments(&status, status.y, &range);
1431 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1432 add_points_to_ending_segments(&status, status.y);
1434 recalculate_windings(&status, &range);
1435 process_horizontals(&status);
1437 check_status(&status);
1438 dict_destroy(status.intersecting_segs);
1439 dict_destroy(status.segs_with_point);
1443 dict_destroy(status.seen_crossings);
1445 actlist_destroy(status.actlist);
1446 queue_destroy(&status.queue);
1447 horiz_destroy(&status.horiz);
1448 xrow_destroy(status.xrow);
1450 gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1451 p->gridsize = poly1->gridsize;
1452 p->strokes = status.strokes;
1455 /* we only add segments with non-empty edgestyles to strokes in
1456 recalculate_windings, but better safe than sorry */
1457 gfxpolystroke_t*stroke = p->strokes;
1460 stroke = stroke->next;
1466 static windcontext_t twopolygons = {2};
1467 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1469 return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons);
1471 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1473 return gfxpoly_process(p1, p2, &windrule_union, &twopolygons);