1 #include <stdlib.h>
2 #include <memory.h>
3 #include <math.h>
4 #include <limits.h>
5 #include <time.h>
6 #include "../mem.h"
7 #include "../types.h"
8 #include "poly.h"
9 #include "active.h"
10 #include "xrow.h"
11 #include "wind.h"
12 #include "convert.h"
13 #include "heap.h"
14 #include "moments.h"
15
16 #ifdef HAVE_MD5
17 #include "MD5.h"
18 #endif
19
20 static gfxpoly_t*current_polygon = 0;
gfxpoly_fail(char * expr,char * file,int line,const char * function)21 void gfxpoly_fail(char*expr, char*file, int line, const char*function)
22 {
23 if(!current_polygon) {
24 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
25 exit(1);
26 }
27
28 char filename[32+4+1];
29 #ifdef HAVE_MD5
30 void*md5 = initialize_md5();
31
32 int s,t;
33 gfxpolystroke_t*stroke = current_polygon->strokes;
34 for(;stroke;stroke=stroke->next) {
35 for(t=0;t<stroke->num_points;t++) {
36 update_md5(md5, (unsigned char*)&stroke->points[t].x, sizeof(stroke->points[t].x));
37 update_md5(md5, (unsigned char*)&stroke->points[t].y, sizeof(stroke->points[t].y));
38 }
39 }
40 unsigned char h[16];
41 finish_md5(md5, h);
42 sprintf(filename, "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x.ps",
43 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]);
44 #else
45 sprintf(filename, "%d", (int)time(0));
46 #endif
47
48 fprintf(stderr, "assert(%s) failed in %s in line %d: %s\n", expr, file, line, function);
49 fprintf(stderr, "I'm saving a debug file \"%s\" to the current directory.\n", filename);
50
51 gfxpoly_save(current_polygon, filename);
52 exit(1);
53 }
54
point_equals(const void * o1,const void * o2)55 static char point_equals(const void*o1, const void*o2)
56 {
57 const point_t*p1 = o1;
58 const point_t*p2 = o2;
59 return p1->x == p2->x && p1->y == p2->y;
60 }
point_hash(const void * o)61 static unsigned int point_hash(const void*o)
62 {
63 const point_t*p = o;
64 return p->x^p->y;
65 }
point_dup(const void * o)66 static void* point_dup(const void*o)
67 {
68 const point_t*p = o;
69 point_t*n = malloc(sizeof(point_t));
70 n->x = p->x;
71 n->y = p->y;
72 return n;
73 }
point_free(void * o)74 static void point_free(void*o)
75 {
76 point_t*p = o;
77 p->x = 0;
78 p->y = 0;
79 free(p);
80 }
81 type_t point_type = {
82 equals: point_equals,
83 hash: point_hash,
84 dup: point_dup,
85 free: point_free,
86 };
87
88 typedef struct _event {
89 eventtype_t type;
90 point_t p;
91 segment_t*s1;
92 segment_t*s2;
93 } event_t;
94
95 /* compare_events_simple differs from compare_events in that it schedules
96 events from left to right regardless of type. It's only used in horizontal
97 processing, in order to get an x-wise sorting of the current scanline */
compare_events_simple(const void * _a,const void * _b)98 static inline int compare_events_simple(const void*_a,const void*_b)
99 {
100 event_t* a = (event_t*)_a;
101 event_t* b = (event_t*)_b;
102 int d = b->p.y - a->p.y;
103 if(d) return d;
104 d = b->p.x - a->p.x;
105 if(d) return d;
106 return 0;
107 }
108
compare_events(const void * _a,const void * _b)109 static inline int compare_events(const void*_a,const void*_b)
110 {
111 event_t* a = (event_t*)_a;
112 event_t* b = (event_t*)_b;
113 int d = b->p.y - a->p.y;
114 if(d) return d;
115 /* we need to schedule end after intersect (so that a segment about
116 to end has a chance to tear up a few other segs first) and start
117 events after end (in order not to confuse the intersection check, which
118 assumes there's an actual y overlap between active segments, and
119 because ending segments in the active list make it difficult to insert
120 starting segments at the right position)).
121 Horizontal lines come last, because the only purpose
122 they have is to create snapping coordinates for the segments (still)
123 existing in this scanline.
124 */
125 d = b->type - a->type;
126 if(d) return d;
127 return 0;
128
129 /* I don't see any reason why we would need to order by x- at least as long
130 as we do horizontal lines in a seperate pass */
131 //d = b->p.x - a->p.x;
132 //return d;
133 }
134
135 #define COMPARE_EVENTS(x,y) (compare_events(x,y)>0)
136 #define COMPARE_EVENTS_SIMPLE(x,y) (compare_events_simple(x,y)>0)
137 HEAP_DEFINE(queue,event_t,COMPARE_EVENTS);
138 HEAP_DEFINE(hqueue,event_t,COMPARE_EVENTS_SIMPLE);
139
140 typedef struct _horizontal {
141 int32_t y;
142 int32_t x1, x2;
143 edgestyle_t*fs;
144 segment_dir_t dir;
145 int polygon_nr;
146 int xpos;
147 int pos;
148 } horizontal_t;
149
150 typedef struct _horizdata {
151 horizontal_t*data;
152 int num;
153 int size;
154 } horizdata_t;
155
156 typedef struct _status {
157 int32_t y;
158 double gridsize;
159 actlist_t*actlist;
160 queue_t queue;
161 xrow_t*xrow;
162 windrule_t*windrule;
163 windcontext_t*context;
164 segment_t*ending_segments;
165
166 horizdata_t horiz;
167
168 gfxpolystroke_t*strokes;
169 #ifdef CHECKS
170 dict_t*seen_crossings; //list of crossing we saw so far
171 dict_t*intersecting_segs; //list of segments intersecting in this scanline
172 dict_t*segs_with_point; //lists of segments that received a point in this scanline
173 #endif
174 } status_t;
175
176
gfxpoly_num_segments(gfxpoly_t * poly)177 int gfxpoly_num_segments(gfxpoly_t*poly)
178 {
179 gfxpolystroke_t*stroke = poly->strokes;
180 int count = 0;
181 for(;stroke;stroke=stroke->next) {
182 count++;
183 }
184 return count;
185 }
gfxpoly_size(gfxpoly_t * poly)186 int gfxpoly_size(gfxpoly_t*poly)
187 {
188 int s,t;
189 int edges = 0;
190 gfxpolystroke_t*stroke = poly->strokes;
191 for(;stroke;stroke=stroke->next) {
192 edges += stroke->num_points-1;
193 }
194 return edges;
195 }
196
gfxpoly_check(gfxpoly_t * poly,char updown)197 char gfxpoly_check(gfxpoly_t*poly, char updown)
198 {
199 dict_t*d1 = dict_new2(&point_type);
200 dict_t*d2 = dict_new2(&point_type);
201 int s,t;
202 gfxpolystroke_t*stroke = poly->strokes;
203 for(;stroke;stroke=stroke->next) {
204 /* In order to not confuse the fill/wind logic, existing segments must have
205 a non-zero edge style */
206 assert(stroke->fs);
207
208 /* put all the segments into dictionaries so that we can check
209 that the endpoint multiplicity is two */
210 for(s=0;s<stroke->num_points;s++) {
211 point_t p = stroke->points[s];
212 int num_xor = (s>=1 && s<stroke->num_points-1)?2:1; // mid points are two points (start+end)
213 int num_circ = (s>=1 && s<stroke->num_points-1)?0:(s==0?1:-1);
214 if(stroke->dir==DIR_UP)
215 num_circ=-num_circ;
216
217 if(!dict_contains(d1, &p)) {
218 dict_put(d1, &p, (void*)(ptroff_t)num_xor);
219 if(updown) {
220 assert(!dict_contains(d2, &p));
221 dict_put(d2, &p, (void*)(ptroff_t)num_circ);
222 }
223 } else {
224 int count = (ptroff_t)dict_lookup(d1, &p);
225 dict_del(d1, &p);
226 count+=num_xor;
227 dict_put(d1, &p, (void*)(ptroff_t)count);
228
229 if(updown) {
230 assert(dict_contains(d2, &p));
231 count = (ptroff_t)dict_lookup(d2, &p);
232 dict_del(d2, &p);
233 count+=num_circ;
234 dict_put(d2, &p, (void*)(ptroff_t)count);
235 }
236 }
237 }
238 }
239 DICT_ITERATE_ITEMS(d1, point_t*, p1, void*, c1) {
240 int count = (ptroff_t)c1;
241 if(count&1) {
242 fprintf(stderr, "Error: Point (%.2f,%.2f) occurs %d times\n", p1->x * poly->gridsize, p1->y * poly->gridsize, count);
243 dict_destroy(d1);
244 dict_destroy(d2);
245 return 0;
246 }
247 }
248 if(updown) {
249 DICT_ITERATE_ITEMS(d2, point_t*, p2, void*, c2) {
250 int count = (ptroff_t)c2;
251 assert(dict_contains(d1, p2));
252 int ocount = (ptroff_t)dict_lookup(d1, p2);
253 if(count!=0) {
254 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);
255 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);
256 gfxpolystroke_t*stroke = poly->strokes;
257 for(;stroke;stroke=stroke->next) {
258 for(s=0;s<stroke->num_points-1;s++) {
259 point_t a = stroke->points[s];
260 point_t b = stroke->points[s+1];
261 if(a.x == p2->x && a.y == p2->y ||
262 b.x == p2->x && b.y == p2->y) {
263 fprintf(stderr, "%.2f,%.2f -> %.2f,%.2f\n",
264 a.x * poly->gridsize,
265 a.y * poly->gridsize,
266 b.x * poly->gridsize,
267 b.y * poly->gridsize);
268 }
269 }
270 }
271 dict_destroy(d2);
272 return 0;
273 }
274 }
275 }
276 dict_destroy(d1);
277 dict_destroy(d2);
278 return 1;
279 }
280
gfxpoly_dump(gfxpoly_t * poly)281 void gfxpoly_dump(gfxpoly_t*poly)
282 {
283 int s,t;
284 double g = poly->gridsize;
285 fprintf(stderr, "polyon %p (gridsize: %.2f)\n", poly, poly->gridsize);
286 gfxpolystroke_t*stroke = poly->strokes;
287 for(;stroke;stroke=stroke->next) {
288 fprintf(stderr, "%11p", stroke);
289 if(stroke->dir==DIR_UP) {
290 for(s=stroke->num_points-1;s>=1;s--) {
291 point_t a = stroke->points[s];
292 point_t b = stroke->points[s-1];
293 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,
294 s==1?"]":"", a.y==b.y?"H":"");
295 }
296 } else {
297 for(s=0;s<stroke->num_points-1;s++) {
298 point_t a = stroke->points[s];
299 point_t b = stroke->points[s+1];
300 fprintf(stderr, "%s (%.2f,%.2f) -> (%.2f,%.2f)%s%s\n", s?" ":"", a.x*g, a.y*g, b.x*g, b.y*g,
301 s==stroke->num_points-2?"]":"", a.y==b.y?"H":"");
302 }
303 }
304 }
305 }
306
gfxpoly_save(gfxpoly_t * poly,const char * filename)307 void gfxpoly_save(gfxpoly_t*poly, const char*filename)
308 {
309 FILE*fi = fopen(filename, "wb");
310 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
311 fprintf(fi, "%% begin\n");
312 int s,t;
313 gfxpolystroke_t*stroke = poly->strokes;
314 for(;stroke;stroke=stroke->next) {
315 fprintf(fi, "%g setgray\n", stroke->dir==DIR_UP ? 0.7 : 0);
316 point_t p = stroke->points[0];
317 fprintf(fi, "%d %d moveto\n", p.x, p.y);
318 for(s=1;s<stroke->num_points;s++) {
319 p = stroke->points[s];
320 fprintf(fi, "%d %d lineto\n", p.x, p.y);
321 }
322 fprintf(fi, "stroke\n");
323 }
324 fprintf(fi, "showpage\n");
325 fclose(fi);
326 }
327
gfxpoly_save_arrows(gfxpoly_t * poly,const char * filename)328 void gfxpoly_save_arrows(gfxpoly_t*poly, const char*filename)
329 {
330 FILE*fi = fopen(filename, "wb");
331 fprintf(fi, "%% gridsize %f\n", poly->gridsize);
332 fprintf(fi, "%% begin\n");
333 int t;
334 double l = 5.0 / poly->gridsize;
335 double g = poly->gridsize;
336 gfxpolystroke_t*stroke = poly->strokes;
337 for(;stroke;stroke=stroke->next) {
338 fprintf(fi, "0 setgray\n");
339
340 int s = stroke->dir==DIR_UP?stroke->num_points-1:0;
341 int end = stroke->dir==DIR_UP?-1:stroke->num_points;
342 int dir = stroke->dir==DIR_UP?-1:1;
343
344 point_t p = stroke->points[s];
345 s+=dir;
346 point_t o = p;
347 fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
348 for(;s!=end;s+=dir) {
349 p = stroke->points[s];
350 int lx = p.x - o.x;
351 int ly = p.y - o.y;
352 double d = sqrt(lx*lx+ly*ly);
353 if(!d) d=1;
354 else d = l / d;
355 double d2 = d*1.5;
356 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
357 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 + (ly*d))*g,
358 (p.y - ly*d2 - (lx*d))*g);
359 fprintf(fi, "%f %f lineto\n", p.x * g, p.y * g);
360 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2 - (ly*d))*g,
361 (p.y - ly*d2 + (lx*d))*g);
362 fprintf(fi, "%f %f lineto\n", (p.x - lx*d2) * g, (p.y - ly*d2) * g);
363 fprintf(fi, "%f %f moveto\n", p.x * g, p.y * g);
364 o = p;
365 }
366 fprintf(fi, "stroke\n");
367 }
368 fprintf(fi, "showpage\n");
369 fclose(fi);
370 }
371
event_new()372 inline static event_t* event_new()
373 {
374 event_t*e = rfx_calloc(sizeof(event_t));
375 return e;
376 }
event_free(event_t * e)377 inline static void event_free(event_t*e)
378 {
379 free(e);
380 }
381
event_dump(status_t * status,event_t * e)382 static void event_dump(status_t*status, event_t*e)
383 {
384 if(e->type == EVENT_HORIZONTAL) {
385 fprintf(stderr, "Horizontal [%d] (%.2f,%.2f) -> (%.2f,%.2f)\n", (int)e->s1->nr,
386 e->s1->a.x * status->gridsize, e->s1->a.y * status->gridsize, e->s1->b.x * status->gridsize, e->s1->b.y * status->gridsize);
387 } else if(e->type == EVENT_START) {
388 fprintf(stderr, "event: segment [%d] starts at (%.2f,%.2f)\n", (int)e->s1->nr,
389 e->p.x * status->gridsize, e->p.y * status->gridsize);
390 } else if(e->type == EVENT_END) {
391 fprintf(stderr, "event: segment [%d] ends at (%.2f,%.2f)\n", (int)e->s1->nr,
392 e->p.x * status->gridsize, e->p.y * status->gridsize);
393 } else if(e->type == EVENT_CROSS) {
394 fprintf(stderr, "event: segment [%d] and [%d] intersect at (%.2f,%.2f)\n", (int)e->s1->nr, (int)e->s2->nr,
395 e->p.x * status->gridsize, e->p.y * status->gridsize);
396 } else {
397 assert(0);
398 }
399 }
400
max32(int32_t v1,int32_t v2)401 static inline int32_t max32(int32_t v1, int32_t v2) {return v1>v2?v1:v2;}
min32(int32_t v1,int32_t v2)402 static inline int32_t min32(int32_t v1, int32_t v2) {return v1<v2?v1:v2;}
403
segment_dump(segment_t * s)404 static void segment_dump(segment_t*s)
405 {
406 fprintf(stderr, "[%d] (%d,%d)->(%d,%d) ", (int)s->nr, s->a.x, s->a.y, s->b.x, s->b.y);
407 fprintf(stderr, " dx:%d dy:%d k:%f dx/dy=%f fs=%p\n", s->delta.x, s->delta.y, s->k,
408 (double)s->delta.x / s->delta.y, s->fs);
409 }
410
segment_init(segment_t * s,int32_t x1,int32_t y1,int32_t x2,int32_t y2,int polygon_nr,segment_dir_t dir)411 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)
412 {
413 static int segment_count=0;
414 s->nr = segment_count++;
415 s->dir = dir;
416 if(y1!=y2) {
417 assert(y1<y2);
418 } else {
419 /* We need to make sure horizontal segments always go from left to right.
420 "up/down" for horizontal segments is handled by "rotating"
421 them 90° counterclockwise in screen coordinates (tilt your head to
422 the right). In other words, the "normal" direction (what's positive dy for
423 vertical segments) is positive dx for horizontal segments ("down" is right).
424 */
425 if(x1>x2) {
426 s->dir = DIR_INVERT(s->dir);
427 int32_t x = x1;x1=x2;x2=x;
428 int32_t y = y1;y1=y2;y2=y;
429 }
430 #ifdef DEBUG
431 fprintf(stderr, "Scheduling horizontal segment [%d] (%.2f,%.2f) -> (%.2f,%.2f) %s\n",
432 segment_count,
433 x1 * 0.05, y1 * 0.05, x2 * 0.05, y2 * 0.05, s->dir==DIR_UP?"up":"down");
434 #endif
435 }
436 s->a.x = x1;
437 s->a.y = y1;
438 s->b.x = x2;
439 s->b.y = y2;
440 s->k = (double)x1*y2-(double)x2*y1;
441 s->left = s->right = 0;
442 s->delta.x = x2-x1;
443 s->delta.y = y2-y1;
444 s->minx = min32(x1,x2);
445 s->maxx = max32(x1,x2);
446
447 s->pos = s->a;
448 s->polygon_nr = polygon_nr;
449
450 #ifdef CHECKS
451 /* notice: on some systems (with some compilers), for the line
452 (1073741823,-1073741824)->(1073741823,1073741823)
453 we get LINE_EQ(s->a, s) == 1.
454 That's why we now clamp to 26 bit.
455 */
456 assert(LINE_EQ(s->a, s) == 0);
457 assert(LINE_EQ(s->b, s) == 0);
458
459 /* check that all signs are in order:
460 a a
461 |\ /|
462 | \ / |
463 minx-b b--maxx
464 < 0 > 0
465 */
466 point_t p = s->b;
467 p.x = min32(s->a.x, s->b.x);
468 assert(LINE_EQ(p, s) <= 0);
469 p.x = max32(s->a.x, s->b.x);
470 assert(LINE_EQ(p, s) >= 0);
471 #endif
472
473 #ifndef DONT_REMEMBER_CROSSINGS
474 dict_init2(&s->scheduled_crossings, &ptr_type, 0);
475 #endif
476 }
477
segment_new(point_t a,point_t b,int polygon_nr,segment_dir_t dir)478 static segment_t* segment_new(point_t a, point_t b, int polygon_nr, segment_dir_t dir)
479 {
480 segment_t*s = (segment_t*)rfx_calloc(sizeof(segment_t));
481 segment_init(s, a.x, a.y, b.x, b.y, polygon_nr, dir);
482 return s;
483 }
484
segment_clear(segment_t * s)485 static void segment_clear(segment_t*s)
486 {
487 #ifndef DONT_REMEMBER_CROSSINGS
488 dict_clear(&s->scheduled_crossings);
489 #endif
490 }
segment_destroy(segment_t * s)491 static void segment_destroy(segment_t*s)
492 {
493 segment_clear(s);
494 free(s);
495 }
496
advance_stroke(queue_t * queue,hqueue_t * hqueue,gfxpolystroke_t * stroke,int polygon_nr,int pos,double gridsize)497 static void advance_stroke(queue_t*queue, hqueue_t*hqueue, gfxpolystroke_t*stroke, int polygon_nr, int pos, double gridsize)
498 {
499 if(!stroke)
500 return;
501 segment_t*s = 0;
502 /* we need to queue multiple segments at once because we need to process start events
503 before horizontal events */
504 while(pos < stroke->num_points-1) {
505 assert(stroke->points[pos].y <= stroke->points[pos+1].y);
506 s = segment_new(stroke->points[pos], stroke->points[pos+1], polygon_nr, stroke->dir);
507 s->fs = stroke->fs;
508 pos++;
509 s->stroke = 0;
510 s->stroke_pos = 0;
511 #ifdef DEBUG
512 /*if(l->tmp)
513 s->nr = l->tmp;*/
514 fprintf(stderr, "[%d] (%.2f,%.2f) -> (%.2f,%.2f) %s (stroke %p, %d more to come)\n",
515 s->nr, s->a.x * gridsize, s->a.y * gridsize,
516 s->b.x * gridsize, s->b.y * gridsize,
517 s->dir==DIR_UP?"up":"down", stroke, stroke->num_points - 1 - pos);
518 #endif
519 event_t* e = event_new();
520 e->type = s->delta.y ? EVENT_START : EVENT_HORIZONTAL;
521 e->p = s->a;
522 e->s1 = s;
523 e->s2 = 0;
524
525 if(queue) queue_put(queue, e);
526 else hqueue_put(hqueue, e);
527
528 if(e->type != EVENT_HORIZONTAL) {
529 break;
530 }
531 }
532 if(s) {
533 s->stroke = stroke;
534 s->stroke_pos = pos;
535 }
536 }
537
gfxpoly_enqueue(gfxpoly_t * p,queue_t * queue,hqueue_t * hqueue,int polygon_nr)538 static void gfxpoly_enqueue(gfxpoly_t*p, queue_t*queue, hqueue_t*hqueue, int polygon_nr)
539 {
540 int t;
541 gfxpolystroke_t*stroke = p->strokes;
542 for(;stroke;stroke=stroke->next) {
543 assert(stroke->num_points > 1);
544
545 #ifdef CHECKS
546 int s;
547 for(s=0;s<stroke->num_points-1;s++) {
548 assert(stroke->points[s].y <= stroke->points[s+1].y);
549 }
550 #endif
551 advance_stroke(queue, hqueue, stroke, polygon_nr, 0, p->gridsize);
552 }
553 }
554
schedule_endpoint(status_t * status,segment_t * s)555 static void schedule_endpoint(status_t*status, segment_t*s)
556 {
557 // schedule end point of segment
558 assert(s->b.y > status->y);
559 event_t*e = event_new();
560 e->type = EVENT_END;
561 e->p = s->b;
562 e->s1 = s;
563 e->s2 = 0;
564 queue_put(&status->queue, e);
565 }
566
schedule_crossing(status_t * status,segment_t * s1,segment_t * s2)567 static void schedule_crossing(status_t*status, segment_t*s1, segment_t*s2)
568 {
569 /* the code that's required (and the checks you can perform) before
570 it can be said with 100% certainty that we indeed have a valid crossing
571 amazes me every time. -mk */
572 #ifdef CHECKS
573 assert(s1!=s2);
574 assert(s1->right == s2);
575 assert(s2->left == s1);
576 int32_t miny1 = min32(s1->a.y,s1->b.y);
577 int32_t maxy1 = max32(s1->a.y,s1->b.y);
578 int32_t miny2 = min32(s2->a.y,s2->b.y);
579 int32_t maxy2 = max32(s2->a.y,s2->b.y);
580 int32_t minx1 = min32(s1->a.x,s1->b.x);
581 int32_t minx2 = min32(s2->a.x,s2->b.x);
582 int32_t maxx1 = max32(s1->a.x,s1->b.x);
583 int32_t maxx2 = max32(s2->a.x,s2->b.x);
584 /* check that precomputation is sane */
585 assert(minx1 == s1->minx && minx2 == s2->minx);
586 assert(maxx1 == s1->maxx && maxx2 == s2->maxx);
587 /* both segments are active, so this can't happen */
588 assert(!(maxy1 <= miny2 || maxy2 <= miny1));
589 /* we know that right now, s2 is to the right of s1, so there's
590 no way the complete bounding box of s1 is to the right of s1 */
591 assert(!(s1->minx > s2->maxx));
592 assert(s1->minx != s2->maxx || (!s1->delta.x && !s2->delta.x));
593 #endif
594
595 if(s1->maxx <= s2->minx) {
596 #ifdef DEBUG
597 fprintf(stderr, "[%d] doesn't intersect with [%d] because: bounding boxes don't intersect\n", s1->nr, s2->nr);
598 #endif
599 /* bounding boxes don't intersect */
600 return;
601 }
602
603 #ifndef DONT_REMEMBER_CROSSINGS
604 if(dict_contains(&s1->scheduled_crossings, (void*)(ptroff_t)s2->nr)) {
605 /* FIXME: this whole segment hashing thing is really slow */
606 #ifdef DEBUG
607 fprintf(stderr, "[%d] doesn't intersect with [%d] because: we already scheduled this intersection\n", s1->nr, s2->nr);
608 // DICT_ITERATE_KEY(&s1->scheduled_crossings, void*, x) {
609 // fprintf(stderr, "[%d]<->[%d]\n", s1->nr, (int)(ptroff_t)x);
610 // }
611 #endif
612 return; // we already know about this one
613 }
614 #endif
615
616 double det = (double)s1->delta.x*s2->delta.y - (double)s1->delta.y*s2->delta.x;
617 if(!det) {
618 if(s1->k == s2->k) {
619 // lines are exactly on top of each other (ignored)
620 #ifdef DEBUG
621 fprintf(stderr, "Notice: segments [%d] and [%d] are exactly on top of each other\n", s1->nr, s2->nr);
622 #endif
623 return;
624 } else {
625 #ifdef DEBUG
626 fprintf(stderr, "[%d] doesn't intersect with [%d] because: they are parallel to each other\n", s1->nr, s2->nr);
627 #endif
628 /* lines are parallel */
629 return;
630 }
631 }
632
633 double asign2 = LINE_EQ(s1->a, s2);
634 if(asign2==0) {
635 // segment1 touches segment2 in a single point (ignored)
636 #ifdef DEBUG
637 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s1->nr, s2->nr);
638 #endif
639 return;
640 }
641 double bsign2 = LINE_EQ(s1->b, s2);
642 if(bsign2==0) {
643 // segment1 touches segment2 in a single point (ignored)
644 #ifdef DEBUG
645 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s1->nr, s2->nr);
646 #endif
647 return;
648 }
649
650 if(asign2<0 && bsign2<0) {
651 // segment1 is completely to the left of segment2
652 #ifdef DEBUG
653 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);
654 #endif
655 return;
656 }
657 if(asign2>0 && bsign2>0) {
658 // segment1 is completely to the right of segment2
659 #ifndef DONT_REMEMBER_CROSSINGS
660 assert(0);
661 #endif
662 #ifdef DEBUG
663 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);
664 #endif
665 return;
666 }
667
668 double asign1 = LINE_EQ(s2->a, s1);
669 if(asign1==0) {
670 // segment2 touches segment1 in a single point (ignored)
671 #ifdef DEBUG
672 fprintf(stderr, "Notice: segment [%d]'s start point touches segment [%d]\n", s2->nr, s1->nr);
673 #endif
674 return;
675 }
676 double bsign1 = LINE_EQ(s2->b, s1);
677 if(asign2==0) {
678 // segment2 touches segment1 in a single point (ignored)
679 #ifdef DEBUG
680 fprintf(stderr, "Notice: segment [%d]'s end point touches segment [%d]\n", s2->nr, s1->nr);
681 #endif
682 return;
683 }
684
685 if(asign1<0 && bsign1<0) {
686 // segment2 is completely to the left of segment1
687 #ifndef DONT_REMEMBER_CROSSINGS
688 assert(0);
689 #endif
690 #ifdef DEBUG
691 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);
692 #endif
693 return;
694 }
695 if(asign1>0 && bsign1>0) {
696 // segment2 is completely to the right of segment1
697 #ifdef DEBUG
698 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);
699 #endif
700 return;
701 }
702
703 #ifdef DONT_REMEMBER_CROSSINGS
704 /* s2 crosses s1 from *left* to *right*. This is a crossing we already processed-
705 there's not way s2 would be to the left of s1 otherwise */
706 if(asign1<0 && bsign1>0) return;
707 if(asign2>0 && bsign2<0) return;
708 #endif
709
710 assert(!(asign1<0 && bsign1>0));
711 assert(!(asign2>0 && bsign2<0));
712
713 /* TODO: should we precompute these? */
714 double la = (double)s1->a.x*(double)s1->b.y - (double)s1->a.y*(double)s1->b.x;
715 double lb = (double)s2->a.x*(double)s2->b.y - (double)s2->a.y*(double)s2->b.x;
716
717 point_t p;
718 p.x = (int32_t)ceil((-la*s2->delta.x + lb*s1->delta.x) / det);
719 p.y = (int32_t)ceil((+lb*s1->delta.y - la*s2->delta.y) / det);
720
721 assert(p.y >= status->y);
722 #ifdef CHECKS
723 assert(p.x >= s1->minx && p.x <= s1->maxx);
724 assert(p.x >= s2->minx && p.x <= s2->maxx);
725
726 point_t pair;
727 pair.x = s1->nr;
728 pair.y = s2->nr;
729 #ifndef DONT_REMEMBER_CROSSINGS
730 assert(!dict_contains(status->seen_crossings, &pair));
731 dict_put(status->seen_crossings, &pair, 0);
732 #endif
733 #endif
734 #ifdef DEBUG
735 fprintf(stderr, "schedule crossing between [%d] and [%d] at (%d,%d)\n", s1->nr, s2->nr, p.x, p.y);
736 #endif
737
738 #ifndef DONT_REMEMBER_CROSSINGS
739 /* we insert into each other's intersection history because these segments might switch
740 places and we still want to look them up quickly after they did */
741 dict_put(&s1->scheduled_crossings, (void*)(ptroff_t)(s2->nr), 0);
742 dict_put(&s2->scheduled_crossings, (void*)(ptroff_t)(s1->nr), 0);
743 #endif
744
745 event_t* e = event_new();
746 e->type = EVENT_CROSS;
747 e->p = p;
748 e->s1 = s1;
749 e->s2 = s2;
750 queue_put(&status->queue, e);
751 return;
752 }
753
exchange_two(status_t * status,event_t * e)754 static void exchange_two(status_t*status, event_t*e)
755 {
756 //exchange two segments in list
757 segment_t*s1 = e->s1;
758 segment_t*s2 = e->s2;
759 #ifdef CHECKS
760 if(!dict_contains(status->intersecting_segs, s1))
761 dict_put(status->intersecting_segs, s1, 0);
762 if(!dict_contains(status->intersecting_segs, s2))
763 dict_put(status->intersecting_segs, s2, 0);
764 #endif
765 assert(s2->left == s1);
766 assert(s1->right == s2);
767 actlist_swap(status->actlist, s1, s2);
768 assert(s2->right == s1);
769 assert(s1->left == s2);
770 segment_t*left = s2->left;
771 segment_t*right = s1->right;
772 if(left)
773 schedule_crossing(status, left, s2);
774 if(right)
775 schedule_crossing(status, s1, right);
776 }
777
778 typedef struct _box {
779 point_t left1, left2, right1, right2;
780 } box_t;
box_new(int32_t x,int32_t y)781 static inline box_t box_new(int32_t x, int32_t y)
782 {
783 box_t box;
784 box.right1.x = box.right2.x = x;
785 box.left1.x = box.left2.x = x-1;
786 box.left1.y = box.right1.y = y-1;
787 box.left2.y = box.right2.y = y;
788 return box;
789 }
790
791 static void store_horizontal(status_t*status, point_t p1, point_t p2, edgestyle_t*fs, segment_dir_t dir, int polygon_nr);
792
append_stroke(status_t * status,point_t a,point_t b,segment_dir_t dir,edgestyle_t * fs)793 static void append_stroke(status_t*status, point_t a, point_t b, segment_dir_t dir, edgestyle_t*fs)
794 {
795 gfxpolystroke_t*stroke = status->strokes;
796 /* find a stoke to attach this segment to. It has to have an endpoint
797 matching our start point, and a matching edgestyle */
798 while(stroke) {
799 point_t p = stroke->points[stroke->num_points-1];
800 if(p.x == a.x && p.y == a.y && stroke->fs == fs && stroke->dir == dir)
801 break;
802 stroke = stroke->next;
803 }
804 if(!stroke) {
805 stroke = rfx_calloc(sizeof(gfxpolystroke_t));
806 stroke->dir = dir;
807 stroke->fs = fs;
808 stroke->next = status->strokes;
809 status->strokes = stroke;
810 stroke->points_size = 2;
811 stroke->points = rfx_calloc(sizeof(point_t)*stroke->points_size);
812 stroke->points[0] = a;
813 stroke->num_points = 1;
814 } else if(stroke->num_points == stroke->points_size) {
815 assert(stroke->fs);
816 stroke->points_size *= 2;
817 stroke->points = rfx_realloc(stroke->points, sizeof(point_t)*stroke->points_size);
818 }
819 stroke->points[stroke->num_points++] = b;
820 }
821
insert_point_into_segment(status_t * status,segment_t * s,point_t p)822 static void insert_point_into_segment(status_t*status, segment_t*s, point_t p)
823 {
824 assert(s->pos.x != p.x || s->pos.y != p.y);
825
826 #ifdef CHECKS
827 if(!dict_contains(status->segs_with_point, s))
828 dict_put(status->segs_with_point, s, 0);
829 assert(s->fs_out_ok);
830 #endif
831
832 if(s->pos.y != p.y) {
833 /* non horizontal line- copy to output */
834 if(s->fs_out) {
835 segment_dir_t dir = s->wind.is_filled?DIR_DOWN:DIR_UP;
836 #ifdef DEBUG
837 fprintf(stderr, "[%d] receives next point (%.2f,%.2f)->(%.2f,%.2f) (drawing (%s))\n", s->nr,
838 s->pos.x * status->gridsize, s->pos.y * status->gridsize,
839 p.x * status->gridsize, p.y * status->gridsize,
840 dir==DIR_UP?"up":"down"
841 );
842 #endif
843 assert(s->pos.y != p.y);
844 append_stroke(status, s->pos, p, dir, s->fs_out);
845 } else {
846 #ifdef DEBUG
847 fprintf(stderr, "[%d] receives next point (%.2f,%.2f) (omitting)\n", s->nr,
848 p.x * status->gridsize,
849 p.y * status->gridsize);
850 #endif
851 }
852 } else {
853 /* horizontal line. we need to look at this more closely at the end of this
854 scanline */
855 store_horizontal(status, s->pos, p, s->fs, s->dir, s->polygon_nr);
856 }
857
858 s->pos = p;
859 }
860
861 typedef struct _segrange {
862 double xmin;
863 segment_t*segmin;
864 double xmax;
865 segment_t*segmax;
866 } segrange_t;
867
segrange_adjust_endpoints(segrange_t * range,int32_t y)868 static void segrange_adjust_endpoints(segrange_t*range, int32_t y)
869 {
870 #define XPOS_EQ(s1,s2,ypos) (XPOS((s1),(ypos))==XPOS((s2),(ypos)))
871 segment_t*min = range->segmin;
872 segment_t*max = range->segmax;
873
874 /* we need this because if two segments intersect exactly on
875 the scanline, segrange_test_segment_{min,max} can't tell which
876 one is smaller/larger */
877 if(min) while(min->left && XPOS_EQ(min, min->left, y)) {
878 min = min->left;
879 }
880 if(max) while(max->right && XPOS_EQ(max, max->right, y)) {
881 max = max->right;
882 }
883 range->segmin = min;
884 range->segmax = max;
885 }
segrange_test_segment_min(segrange_t * range,segment_t * seg,int32_t y)886 static void segrange_test_segment_min(segrange_t*range, segment_t*seg, int32_t y)
887 {
888 if(!seg) return;
889 /* we need to calculate the xpos anew (and can't use start coordinate or
890 intersection coordinate), because we need the xpos exactly at the end of
891 this scanline.
892 */
893 double x = XPOS(seg, y);
894 if(!range->segmin || x<range->xmin) {
895 range->segmin = seg;
896 range->xmin = x;
897 }
898 }
segrange_test_segment_max(segrange_t * range,segment_t * seg,int32_t y)899 static void segrange_test_segment_max(segrange_t*range, segment_t*seg, int32_t y)
900 {
901 if(!seg) return;
902 double x = XPOS(seg, y);
903 if(!range->segmax || x>range->xmax) {
904 range->segmax = seg;
905 range->xmax = x;
906 }
907 }
908
909 /*
910 SLOPE_POSITIVE:
911 \+ \ +
912 ------ I \I
913 -I\---- I
914 I \ --I\---
915 I \ I \ -------
916 + \ + \
917 */
add_points_to_positively_sloped_segments(status_t * status,int32_t y,segrange_t * range)918 static void add_points_to_positively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
919 {
920 segment_t*first=0, *last = 0;
921 int t;
922 for(t=0;t<status->xrow->num;t++) {
923 box_t box = box_new(status->xrow->x[t], y);
924 segment_t*seg = actlist_find(status->actlist, box.left2, box.left2);
925
926 seg = actlist_right(status->actlist, seg);
927 while(seg) {
928 if(seg->a.y == y) {
929 // this segment started in this scanline, ignore it
930 seg->changed = 1;last = seg;if(!first) {first=seg;}
931 } else if(seg->delta.x <= 0) {
932 // ignore segment w/ negative slope
933 } else {
934 last = seg;if(!first) {first=seg;}
935 double d1 = LINE_EQ(box.right1, seg);
936 double d2 = LINE_EQ(box.right2, seg);
937 if(d1>0 || d2>=0) {
938 seg->changed = 1;
939 insert_point_into_segment(status, seg, box.right2);
940 } else {
941 /* we unfortunately can't break here- the active list is sorted according
942 to the *bottom* of the scanline. hence pretty much everything that's still
943 coming might reach into our box */
944 //break;
945 }
946 }
947 seg = seg->right;
948 }
949 }
950 segrange_test_segment_min(range, first, y);
951 segrange_test_segment_max(range, last, y);
952 }
953 /* SLOPE_NEGATIVE:
954 | + /| + / /
955 | I / | I / /
956 | I / | I/ /
957 | I/ | I /
958 | I | /I /
959 | /+ |/ + /
960 */
add_points_to_negatively_sloped_segments(status_t * status,int32_t y,segrange_t * range)961 static void add_points_to_negatively_sloped_segments(status_t*status, int32_t y, segrange_t*range)
962 {
963 segment_t*first=0, *last = 0;
964 int t;
965 for(t=status->xrow->num-1;t>=0;t--) {
966 box_t box = box_new(status->xrow->x[t], y);
967 segment_t*seg = actlist_find(status->actlist, box.right2, box.right2);
968
969 while(seg) {
970 if(seg->a.y == y) {
971 // this segment started in this scanline, ignore it
972 seg->changed = 1;last = seg;if(!first) {first=seg;}
973 } else if(seg->delta.x > 0) {
974 // ignore segment w/ positive slope
975 } else {
976 last = seg;if(!first) {first=seg;}
977 double d1 = LINE_EQ(box.left1, seg);
978 double d2 = LINE_EQ(box.left2, seg);
979 if(d1<0 || d2<0) {
980 seg->changed = 1;
981 insert_point_into_segment(status, seg, box.right2);
982 } else {
983 //break;
984 }
985 }
986 seg = seg->left;
987 }
988 }
989 segrange_test_segment_min(range, last, y);
990 segrange_test_segment_max(range, first, y);
991 }
992
993 /* segments ending in the current scanline need xrow treatment like everything else.
994 (consider an intersection taking place just above a nearly horizontal segment
995 ending on the current scanline- the intersection would snap down *below* the
996 ending segment if we don't add the intersection point to the latter right away)
997 we need to treat ending segments seperately, however. we have to delete them from
998 the active list right away to make room for intersect operations (which might
999 still be in the current scanline- consider two 45° polygons and a vertical polygon
1000 intersecting on an integer coordinate). but once they're no longer in the active list,
1001 we can't use the add_points_to_*_sloped_segments() functions anymore, and re-adding
1002 them to the active list just for point snapping would be overkill.
1003 (One other option to consider, however, would be to create a new active list only
1004 for ending segments)
1005 */
add_points_to_ending_segments(status_t * status,int32_t y)1006 static void add_points_to_ending_segments(status_t*status, int32_t y)
1007 {
1008 segment_t*seg = status->ending_segments;
1009 while(seg) {
1010 segment_t*next = seg->right;seg->right=0;
1011
1012 assert(seg->b.y == status->y);
1013
1014 if(status->xrow->num == 1) {
1015 // shortcut
1016 assert(seg->b.x == status->xrow->x[0]);
1017 point_t p = {status->xrow->x[0], y};
1018 insert_point_into_segment(status, seg, p);
1019 } else {
1020 int t;
1021 int start=0,end=status->xrow->num,dir=1;
1022 if(seg->delta.x < 0) {
1023 start = status->xrow->num-1;
1024 end = dir = -1;
1025 }
1026 #ifdef CHECKS
1027 char ok = 0;
1028 #endif
1029 for(t=start;t!=end;t+=dir) {
1030 box_t box = box_new(status->xrow->x[t], y);
1031 double d0 = LINE_EQ(box.left1, seg);
1032 double d1 = LINE_EQ(box.left2, seg);
1033 double d2 = LINE_EQ(box.right1, seg);
1034 double d3 = LINE_EQ(box.right2, seg);
1035 if(!(d0>=0 && d1>=0 && d2>=0 && d3>0 ||
1036 d0<=0 && d1<=0 && d2<=0 && d3<0)) {
1037 insert_point_into_segment(status, seg, box.right2);
1038 //break;
1039 #ifdef CHECKS
1040 ok = 1;
1041 #endif
1042 }
1043 }
1044
1045 #ifdef CHECKS
1046 /* we *need* to find a point to insert. the segment's own end point
1047 is in that list, for Pete's sake. */
1048 assert(ok);
1049 #endif
1050 }
1051 // now that this is done, too, we can also finally free this segment
1052 segment_destroy(seg);
1053 seg = next;
1054 }
1055 status->ending_segments = 0;
1056 }
1057
recalculate_windings(status_t * status,segrange_t * range)1058 static void recalculate_windings(status_t*status, segrange_t*range)
1059 {
1060 #ifdef DEBUG
1061 fprintf(stderr, "range: [%d]..[%d]\n", SEGNR(range->segmin), SEGNR(range->segmax));
1062 #endif
1063 segrange_adjust_endpoints(range, status->y);
1064
1065 segment_t*s = range->segmin;
1066 segment_t*end = range->segmax;
1067 segment_t*last = 0;
1068
1069 #ifdef DEBUG
1070 s = actlist_leftmost(status->actlist);
1071 while(s) {
1072 fprintf(stderr, "[%d]%d%s ", s->nr, s->changed,
1073 s == range->segmin?"S":(
1074 s == range->segmax?"E":""));
1075 s = s->right;
1076 }
1077 fprintf(stderr, "\n");
1078 s = range->segmin;
1079 #endif
1080 #ifdef CHECKS
1081 /* test sanity: verify that we don't have changed segments
1082 outside of the given range */
1083 s = actlist_leftmost(status->actlist);
1084 while(s && s!=range->segmin) {
1085 assert(!s->changed);
1086 s = s->right;
1087 }
1088 s = actlist_rightmost(status->actlist);
1089 while(s && s!=range->segmax) {
1090 assert(!s->changed);
1091 s = s->left;
1092 }
1093 /* in check mode, go through the whole interval so we can test
1094 that all polygons where the edgestyle changed also have seg->changed=1 */
1095 s = actlist_leftmost(status->actlist);
1096 end = 0;
1097 #endif
1098
1099 if(end)
1100 end = end->right;
1101 while(s!=end) {
1102 #ifndef CHECKS
1103 if(s->changed)
1104 #endif
1105 {
1106 segment_t* left = actlist_left(status->actlist, s);
1107 windstate_t wind = left?left->wind:status->windrule->start(status->context);
1108 s->wind = status->windrule->add(status->context, wind, s->fs, s->dir, s->polygon_nr);
1109 edgestyle_t*fs_old = s->fs_out;
1110 s->fs_out = status->windrule->diff(&wind, &s->wind);
1111
1112 #ifdef DEBUG
1113 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",
1114 fs_old?"draw":"omit", s->fs_out?"draw":"omit",
1115 fs_old!=s->fs_out?"CHANGED":"");
1116 #endif
1117 assert(!(!s->changed && fs_old!=s->fs_out));
1118 s->changed = 0;
1119
1120 #ifdef CHECKS
1121 s->fs_out_ok = 1;
1122 #endif
1123 }
1124 s = s->right;
1125 }
1126 }
1127
1128 /* we need to handle horizontal lines in order to add points to segments
1129 we otherwise would miss during the windrule re-evaluation */
intersect_with_horizontal(status_t * status,segment_t * h)1130 static void intersect_with_horizontal(status_t*status, segment_t*h)
1131 {
1132 segment_t* left = actlist_find(status->actlist, h->a, h->a);
1133 segment_t* right = actlist_find(status->actlist, h->b, h->b);
1134
1135 /* h->a.x is not strictly necessary, as it's also done by the event */
1136 xrow_add(status->xrow, h->a.x);
1137 xrow_add(status->xrow, h->b.x);
1138
1139 if(!right) {
1140 assert(!left);
1141 return;
1142 }
1143
1144 left = actlist_right(status->actlist, left); //first seg to the right of h->a
1145 right = right->right; //first seg to the right of h->b
1146 segment_t* s = left;
1147
1148 point_t o = h->a;
1149 while(s!=right) {
1150 assert(s);
1151 int32_t x = XPOS_INT(s, status->y);
1152 point_t p = {x, status->y};
1153 #ifdef DEBUG
1154 fprintf(stderr, "...intersecting with [%d] (%.2f,%.2f) -> (%.2f,%.2f) at (%.2f,%.2f)\n",
1155 s->nr,
1156 s->a.x * status->gridsize, s->a.y * status->gridsize,
1157 s->b.x * status->gridsize, s->b.y * status->gridsize,
1158 x * status->gridsize, status->y * status->gridsize
1159 );
1160 #endif
1161 assert(x >= h->a.x);
1162 assert(x <= h->b.x);
1163 assert(s->delta.x > 0 && x >= s->a.x || s->delta.x <= 0 && x <= s->a.x);
1164 assert(s->delta.x > 0 && x <= s->b.x || s->delta.x <= 0 && x >= s->b.x);
1165 xrow_add(status->xrow, x);
1166
1167 o = p;
1168 s = s->right;
1169 }
1170 }
1171
1172 /* while, for a scanline, we need both starting as well as ending segments in order
1173 to *reconstruct* horizontal lines, we only need one or the other to *process*
1174 horizontal lines from the input data.
1175
1176 So horizontal lines are processed twice: first they create hotpixels by intersecting
1177 all segments on the scanline (EVENT_HORIZTONAL). Secondly, they are processed for
1178 their actual content. The second also happens for all segments that received more than
1179 one point in this scanline.
1180 */
horiz_reset(horizdata_t * horiz)1181 void horiz_reset(horizdata_t*horiz)
1182 {
1183 horiz->num = 0;
1184 }
1185
horiz_destroy(horizdata_t * horiz)1186 void horiz_destroy(horizdata_t*horiz)
1187 {
1188 if(horiz->data) rfx_free(horiz->data);
1189 horiz->data = 0;
1190 }
1191
get_horizontal_first_windstate(status_t * status,int x1,int x2)1192 static windstate_t get_horizontal_first_windstate(status_t*status, int x1, int x2)
1193 {
1194 point_t p1 = {x1,status->y};
1195 point_t p2 = {x2,status->y};
1196 segment_t*left = actlist_find(status->actlist, p1, p2);
1197
1198 segment_t*a = actlist_right(status->actlist, left);
1199 while(a) {
1200 if(a->pos.y == status->y) {
1201 /* we need to iterate through all segments that received a point in this
1202 scanline, as actlist_find above will miss (positively sloped) segments
1203 that are to the right of (x1,y) only as long as we don't take the
1204 hotpixel re-routing into account
1205 TODO: this is inefficient, we should probably be iterating through the
1206 hotpixels on this scanline.
1207 */
1208 if(a->pos.x == x1)
1209 left = a;
1210 if(a->pos.x > x1)
1211 break;
1212 }
1213 a = a->right;
1214 }
1215
1216 assert(!left || left->fs_out_ok);
1217 #ifdef DEBUG
1218 fprintf(stderr, " fragment %.2f..%.2f\n",
1219 x1 * status->gridsize,
1220 x2 * status->gridsize);
1221 if(left) {
1222 fprintf(stderr, " segment [%d] (%.2f,%.2f -> %.2f,%2f, at %.2f,%.2f) is to the left\n",
1223 SEGNR(left),
1224 left->a.x * status->gridsize,
1225 left->a.y * status->gridsize,
1226 left->b.x * status->gridsize,
1227 left->b.y * status->gridsize,
1228 left->pos.x * status->gridsize,
1229 left->pos.y * status->gridsize
1230 );
1231 /* this segment might be a distance away from the left point
1232 of the horizontal line if the horizontal line belongs to a stroke
1233 with segments that just ended (so this horizontal line appears to
1234 be "floating in space" from our current point of view)
1235 assert(left->pos.y == h->y && left->pos.x == h->x1);
1236 */
1237 }
1238 #endif
1239 return left?left->wind:status->windrule->start(status->context);
1240 }
1241
process_horizontal_fragment(status_t * status,horizontal_t * h,int x1,int x2,windstate_t below)1242 static windstate_t process_horizontal_fragment(status_t*status, horizontal_t*h, int x1, int x2, windstate_t below)
1243 {
1244 windstate_t above = status->windrule->add(status->context, below, h->fs, h->dir, h->polygon_nr);
1245 edgestyle_t*fs = status->windrule->diff(&above, &below);
1246
1247 segment_dir_t dir = above.is_filled?DIR_DOWN:DIR_UP;
1248 point_t p1 = {x1,h->y};
1249 point_t p2 = {x2,h->y};
1250
1251 if(fs) {
1252 //append_stroke(status, p1, p2, DIR_INVERT(h->dir), fs);
1253 append_stroke(status, p1, p2, dir, fs);
1254 }
1255 #ifdef DEBUG
1256 fprintf(stderr, " ...%s (below: (wind_nr=%d, filled=%d), above: (wind_nr=%d, filled=%d) %s %d-%d\n",
1257 fs?"storing":"ignoring",
1258 below.wind_nr, below.is_filled,
1259 above.wind_nr, above.is_filled,
1260 dir==DIR_UP?"up":"down", x1, x2);
1261 #endif
1262 return above;
1263 }
1264
1265 typedef enum {hevent_hotpixel,hevent_end,hevent_start} horizontal_event_type_t;
1266 typedef struct _hevent {
1267 int32_t x;
1268 horizontal_t*h;
1269 horizontal_event_type_t type;
1270 } hevent_t;
1271
1272 typedef struct _hevents {
1273 hevent_t*events;
1274 int num;
1275 } hevents_t;
1276
compare_hevents(const void * _e1,const void * _e2)1277 static int compare_hevents(const void *_e1, const void *_e2)
1278 {
1279 hevent_t*e1 = (hevent_t*)_e1;
1280 hevent_t*e2 = (hevent_t*)_e2;
1281 int diff = e1->x - e2->x;
1282 if(diff) return diff;
1283 return e1->type - e2->type; //schedule hotpixel before hend
1284 }
1285
hevents_fill(status_t * status)1286 static hevents_t hevents_fill(status_t*status)
1287 {
1288 horizdata_t*horiz = &status->horiz;
1289 xrow_t*xrow = status->xrow;
1290
1291 hevents_t e;
1292 e.events = malloc(sizeof(hevent_t)*(horiz->num*2 + xrow->num));
1293 e.num = 0;
1294
1295 int t;
1296 for(t=0;t<horiz->num;t++) {
1297 assert(horiz->data[t].x1 != horiz->data[t].x2);
1298 e.events[e.num].x = horiz->data[t].x1;
1299 e.events[e.num].h = &horiz->data[t];
1300 e.events[e.num].type = hevent_start;
1301 e.num++;
1302 e.events[e.num].x = horiz->data[t].x2;
1303 e.events[e.num].h = &horiz->data[t];
1304 e.events[e.num].type = hevent_end;
1305 e.num++;
1306 }
1307 for(t=0;t<xrow->num;t++) {
1308 e.events[e.num].x = status->xrow->x[t];
1309 e.events[e.num].h = 0;
1310 e.events[e.num].type = hevent_hotpixel;
1311 e.num++;
1312 }
1313 qsort(e.events, e.num, sizeof(hevent_t), compare_hevents);
1314 return e;
1315
1316 }
1317
process_horizontals(status_t * status)1318 static void process_horizontals(status_t*status)
1319 {
1320 horizdata_t*horiz = &status->horiz;
1321
1322 if(!horiz->num)
1323 return;
1324
1325 hevents_t events = hevents_fill(status);
1326 int num_open = 0;
1327 horizontal_t**open = malloc(sizeof(horizontal_t*)*horiz->num);
1328
1329 int s,t;
1330 for(t=0;t<events.num;t++) {
1331 hevent_t*e = &events.events[t];
1332 switch(e->type) {
1333 case hevent_start:
1334 e->h->pos = num_open;
1335 open[num_open++] = e->h;
1336 #ifdef DEBUG
1337 fprintf(stderr, "horizontal (y=%.2f): %.2f -> %.2f dir=%s fs=%p\n",
1338 e->h->y * status->gridsize,
1339 e->h->x1 * status->gridsize,
1340 e->h->x2 * status->gridsize,
1341 e->h->dir==DIR_UP?"up":"down", e->h->fs);
1342 #endif
1343 assert(e->h->y == status->y);
1344 assert(xrow_contains(status->xrow, e->h->x1));
1345 assert(xrow_contains(status->xrow, e->h->x2));
1346 break;
1347 case hevent_end:
1348 num_open--;
1349 if(num_open) {
1350 open[num_open]->pos = e->h->pos;
1351 open[e->h->pos] = open[num_open];
1352 }
1353 break;
1354 case hevent_hotpixel:
1355 {
1356 windstate_t below;
1357 for(s=0;s<num_open;s++) {
1358 int x1 = open[s]->xpos;
1359 int x2 = e->x;
1360 assert(status->y == open[s]->y);
1361 if(!s)
1362 below = get_horizontal_first_windstate(status, x1, x2);
1363 open[s]->xpos = e->x;
1364 assert(x1 < x2);
1365 below = process_horizontal_fragment(status, open[s], x1, x2, below);
1366 }
1367 }
1368 break;
1369 }
1370 }
1371 free(open);
1372 free(events.events);
1373 }
1374
store_horizontal(status_t * status,point_t p1,point_t p2,edgestyle_t * fs,segment_dir_t dir,int polygon_nr)1375 static void store_horizontal(status_t*status, point_t p1, point_t p2, edgestyle_t*fs, segment_dir_t dir, int polygon_nr)
1376 {
1377 assert(p1.y == p2.y);
1378 assert(p1.x != p2.x); // TODO: can this happen?
1379
1380 if(p1.x > p2.x) {
1381 dir = DIR_INVERT(dir);
1382 point_t p_1 = p1;
1383 point_t p_2 = p2;
1384 p1 = p_2;
1385 p2 = p_1;
1386 }
1387
1388 /* TODO: convert this into a linked list */
1389 if(status->horiz.size == status->horiz.num) {
1390 if(!status->horiz.size)
1391 status->horiz.size = 16;
1392 status->horiz.size *= 2;
1393 status->horiz.data = rfx_realloc(status->horiz.data, sizeof(status->horiz.data[0])*status->horiz.size);
1394 }
1395 horizontal_t*h = &status->horiz.data[status->horiz.num++];
1396 h->y = p1.y;
1397 h->xpos = p1.x;
1398 h->x1 = p1.x;
1399 h->x2 = p2.x;
1400 h->fs = fs;
1401 h->dir = dir;
1402 h->polygon_nr = polygon_nr;
1403 }
1404
1405
event_apply(status_t * status,event_t * e)1406 static void event_apply(status_t*status, event_t*e)
1407 {
1408 #ifdef DEBUG
1409 event_dump(status, e);
1410 #endif
1411
1412 switch(e->type) {
1413 case EVENT_HORIZONTAL: {
1414 segment_t*s = e->s1;
1415 intersect_with_horizontal(status, s);
1416 store_horizontal(status, s->a, s->b, s->fs, s->dir, s->polygon_nr);
1417 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos, status->gridsize);
1418 segment_destroy(s);e->s1=0;
1419 break;
1420 }
1421 case EVENT_END: {
1422 //delete segment from list
1423 segment_t*s = e->s1;
1424 #ifdef CHECKS
1425 dict_del(status->intersecting_segs, s);
1426 dict_del(status->segs_with_point, s);
1427 assert(!dict_contains(status->intersecting_segs, s));
1428 assert(!dict_contains(status->segs_with_point, s));
1429 #endif
1430 segment_t*left = s->left;
1431 segment_t*right = s->right;
1432 actlist_delete(status->actlist, s);
1433 if(left && right)
1434 schedule_crossing(status, left, right);
1435
1436 /* schedule segment for xrow handling */
1437 s->left = 0; s->right = status->ending_segments;
1438 status->ending_segments = s;
1439 advance_stroke(&status->queue, 0, s->stroke, s->polygon_nr, s->stroke_pos, status->gridsize);
1440 break;
1441 }
1442 case EVENT_START: {
1443 //insert segment into list
1444 segment_t*s = e->s1;
1445 assert(e->p.x == s->a.x && e->p.y == s->a.y);
1446 actlist_insert(status->actlist, s->a, s->b, s);
1447 segment_t*left = s->left;
1448 segment_t*right = s->right;
1449 if(left)
1450 schedule_crossing(status, left, s);
1451 if(right)
1452 schedule_crossing(status, s, right);
1453 schedule_endpoint(status, s);
1454 break;
1455 }
1456 case EVENT_CROSS: {
1457 // exchange two segments
1458 if(e->s1->right == e->s2) {
1459 assert(e->s2->left == e->s1);
1460 exchange_two(status, e);
1461 } else {
1462 assert(e->s2->left != e->s1);
1463 #ifdef DEBUG
1464 fprintf(stderr, "Ignore this crossing ([%d] not next to [%d])\n", e->s1->nr, e->s2->nr);
1465 #endif
1466 #ifndef DONT_REMEMBER_CROSSINGS
1467 /* ignore this crossing for now (there are some line segments in between).
1468 it'll get rescheduled as soon as the "obstacles" are gone */
1469 char del1 = dict_del(&e->s1->scheduled_crossings, (void*)(ptroff_t)e->s2->nr);
1470 char del2 = dict_del(&e->s2->scheduled_crossings, (void*)(ptroff_t)e->s1->nr);
1471 assert(del1 && del2);
1472 #endif
1473 #ifdef CHECKS
1474 point_t pair;
1475 pair.x = e->s1->nr;
1476 pair.y = e->s2->nr;
1477 #ifndef DONT_REMEMBER_CROSSINGS
1478 assert(dict_contains(status->seen_crossings, &pair));
1479 dict_del(status->seen_crossings, &pair);
1480 #endif
1481 #endif
1482 }
1483 }
1484 }
1485 }
1486
1487 #ifdef CHECKS
check_status(status_t * status)1488 static void check_status(status_t*status)
1489 {
1490 DICT_ITERATE_KEY(status->intersecting_segs, segment_t*, s) {
1491 if((s->pos.x != s->b.x ||
1492 s->pos.y != s->b.y) &&
1493 !dict_contains(status->segs_with_point, s)) {
1494 fprintf(stderr, "Error: segment [%d] (%sslope) intersects in scanline %d, but it didn't receive a point\n",
1495 SEGNR(s),
1496 s->delta.x<0?"-":"+",
1497 status->y);
1498 assert(0);
1499 }
1500 }
1501 }
1502 #endif
1503
gfxpoly_process(gfxpoly_t * poly1,gfxpoly_t * poly2,windrule_t * windrule,windcontext_t * context,moments_t * moments)1504 gfxpoly_t* gfxpoly_process(gfxpoly_t*poly1, gfxpoly_t*poly2, windrule_t*windrule, windcontext_t*context, moments_t*moments)
1505 {
1506 current_polygon = poly1;
1507
1508 status_t status;
1509 memset(&status, 0, sizeof(status_t));
1510 status.gridsize = poly1->gridsize;
1511 status.windrule = windrule;
1512 status.context = context;
1513 status.actlist = actlist_new();
1514
1515 queue_init(&status.queue);
1516 gfxpoly_enqueue(poly1, &status.queue, 0, /*polygon nr*/0);
1517 if(poly2) {
1518 assert(poly1->gridsize == poly2->gridsize);
1519 gfxpoly_enqueue(poly2, &status.queue, 0, /*polygon nr*/1);
1520 }
1521
1522 #ifdef CHECKS
1523 status.seen_crossings = dict_new2(&point_type);
1524 #endif
1525 int32_t lasty = INT_MIN;
1526 if(moments) {
1527 memset(moments, 0, sizeof(moments_t));
1528 }
1529
1530 status.xrow = xrow_new();
1531
1532 event_t*e = queue_get(&status.queue);
1533 while(e) {
1534 assert(e->s1->fs);
1535 status.y = e->p.y;
1536 #ifdef CHECKS
1537 assert(status.y > lasty);
1538 status.intersecting_segs = dict_new2(&ptr_type);
1539 status.segs_with_point = dict_new2(&ptr_type);
1540 #endif
1541
1542 #ifdef DEBUG
1543 fprintf(stderr, "----------------------------------- %.2f\n", status.y * status.gridsize);
1544 actlist_dump(status.actlist, status.y-1, status.gridsize);
1545 #endif
1546 #ifdef CHECKS
1547 actlist_verify(status.actlist, status.y-1);
1548 #endif
1549 if(moments && lasty > INT_MIN) {
1550 moments_update(moments, status.actlist, lasty, status.y);
1551 }
1552
1553 xrow_reset(status.xrow);
1554 horiz_reset(&status.horiz);
1555
1556 do {
1557 xrow_add(status.xrow, e->p.x);
1558 event_apply(&status, e);
1559 event_free(e);
1560 e = queue_get(&status.queue);
1561 } while(e && status.y == e->p.y);
1562
1563 xrow_sort(status.xrow);
1564 segrange_t range;
1565 memset(&range, 0, sizeof(range));
1566 #ifdef DEBUG
1567 actlist_dump(status.actlist, status.y, status.gridsize);
1568 xrow_dump(status.xrow, status.gridsize);
1569 #endif
1570 add_points_to_positively_sloped_segments(&status, status.y, &range);
1571 add_points_to_negatively_sloped_segments(&status, status.y, &range);
1572 add_points_to_ending_segments(&status, status.y);
1573
1574 recalculate_windings(&status, &range);
1575
1576 actlist_verify(status.actlist, status.y);
1577 process_horizontals(&status);
1578 #ifdef CHECKS
1579 check_status(&status);
1580 dict_destroy(status.intersecting_segs);
1581 dict_destroy(status.segs_with_point);
1582 #endif
1583 lasty = status.y;
1584 }
1585 #ifdef CHECKS
1586 dict_destroy(status.seen_crossings);
1587 #endif
1588 actlist_destroy(status.actlist);
1589 queue_destroy(&status.queue);
1590 horiz_destroy(&status.horiz);
1591 xrow_destroy(status.xrow);
1592
1593 gfxpoly_t*p = (gfxpoly_t*)malloc(sizeof(gfxpoly_t));
1594 p->gridsize = poly1->gridsize;
1595 p->strokes = status.strokes;
1596
1597 #ifdef CHECKS
1598 /* we only add segments with non-empty edgestyles to strokes in
1599 recalculate_windings, but better safe than sorry */
1600 gfxpolystroke_t*stroke = p->strokes;
1601 while(stroke) {
1602 assert(stroke->fs);
1603 stroke = stroke->next;
1604 }
1605 #endif
1606 return p;
1607 }
1608
1609 static windcontext_t onepolygon = {1};
1610 static windcontext_t twopolygons = {2};
gfxpoly_intersect(gfxpoly_t * p1,gfxpoly_t * p2)1611 gfxpoly_t* gfxpoly_intersect(gfxpoly_t*p1, gfxpoly_t*p2)
1612 {
1613 return gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons, 0);
1614 }
gfxpoly_union(gfxpoly_t * p1,gfxpoly_t * p2)1615 gfxpoly_t* gfxpoly_union(gfxpoly_t*p1, gfxpoly_t*p2)
1616 {
1617 return gfxpoly_process(p1, p2, &windrule_union, &twopolygons, 0);
1618 }
gfxpoly_area(gfxpoly_t * p)1619 double gfxpoly_area(gfxpoly_t*p)
1620 {
1621 moments_t moments;
1622 gfxpoly_t*p2 = gfxpoly_process(p, 0, &windrule_evenodd, &onepolygon, &moments);
1623 gfxpoly_destroy(p2);
1624 moments_normalize(&moments, p->gridsize);
1625 return moments.area;
1626 }
gfxpoly_intersection_area(gfxpoly_t * p1,gfxpoly_t * p2)1627 double gfxpoly_intersection_area(gfxpoly_t*p1, gfxpoly_t*p2)
1628 {
1629 moments_t moments;
1630 gfxpoly_t*p3 = gfxpoly_process(p1, p2, &windrule_intersect, &twopolygons, &moments);
1631 gfxpoly_destroy(p3);
1632
1633 moments_normalize(&moments, p1->gridsize);
1634 return moments.area;
1635 }
1636