Debian Codegraph @

podofo/3rdparty/adobe/afdko/source/absfont/absfont_path.c

raw
1 /* Copyright 2014 Adobe Systems Incorporated (http://www.adobe.com/). All Rights Reserved.
2 This software is licensed as OpenSource, under the Apache License, Version 2.0.
3 This license is available at: http://opensource.org/licenses/Apache-2.0. */
4
5 /*
6 * Path support.
7 */
8
9 #include "absfont.h"
10 #include "dynarr.h"
11 #include "supportexcept.h"
12
13 #include <string.h>
14 #include <math.h>
15 #include <stdlib.h>
16 #include <float.h>
17
18 #ifndef MAXFLOAT
19 #define MAXFLOAT FLT_MAX
20 #endif
21
22 #define RND(v) ((float)floor((v) + 0.5))
23
24 /* Scale to thousandths of an em */
25 #define MILLIEM(v) ((float)(h->top->sup.UnitsPerEm * (v) / 1000.0))
26
27 /* Macro switches */
28 #define ROUND_ISECT_COORDS 0 /* Rounding intersection coordinates appear to have negative impact. Disabled */
29 #define CLAMP_ISECT_T 0 /* Clamp "t" if the calculated intersection is close to a segment end */
30
31 /* Heuristics constants */
32
33 #define BEZ_SPLIT_DEPTH 6 /* Split 6 times; bbox < .002 em; don't split */
34 #define BEZ_SPLIT_MILLIEM MILLIEM(16) /* MILLIEM(64) is not small enough for FiraSans-TwoItalic */
35 #define ISECT_EPSILON 1.0f
36 #define WIND_TEST_EPSILON 1.0f
37 #define EXTREMUM_EPSILON 0.5f
38 #define MISMATCH_SEGMENT_PENALTY 0.5f
39 #define FIXED_SCORE_INCREMENT 0.1f
40 #define EXTRA_OUTLET_PENALTY 0.5f
41 #define MAX_SWEEP_FIX_JUNC 100
42 #define SHORT_LINE_LIMIT 1
43
44 #if ABF_DEBUG
45 static void dbglyph(abfCtx h, long iGlyph);
46 static void dbisects(abfCtx h);
47 static void dbjuncs(abfCtx h);
48 #endif
49
50 typedef struct /* Coordinate point */
51 {
52 float x;
53 float y;
54 } Point;
55
56 typedef struct /* Rectangle */
57 {
58 float left;
59 float bottom;
60 float right;
61 float top;
62 } Rect;
63
64 typedef struct /* Straight line */
65 {
66 Point p0;
67 Point p1;
68 float t0; /* Split start t */
69 float t1; /* Split end t */
70 long iSeg; /* Original segment */
71 } Line;
72
73 typedef struct /* Bezier curve */
74 {
75 Point p0;
76 Point p1;
77 Point p2;
78 Point p3;
79 float t0; /* Split start t */
80 float t1; /* Split end t */
81 long depth; /* Recursion depth */
82 long iSeg; /* Original segment */
83 Rect bounds;
84 } Bezier;
85
86 typedef struct /* Intersect */
87 {
88 float t; /* Intercept on segment */
89 Point p; /* intersection point */
90 long iSeg; /* Segment index */
91 long iSplit; /* Split segment index */
92 long id; /* Pair identifier */
93 long flags; /* Status flags */
94 #define ISECT_DUP (1 << 0) /* Duplicate intersection */
95 } Intersect;
96
97 typedef struct /* Outlet */
98 {
99 long seg; /* Segment index */
100 long otherJunc; /* Junction index on the other side */
101 long otherSeg; /* Segment index on the other side */
102 float angle; /* angle */
103 float score; /* segment score */
104 long flags; /* Status flags */
105 #define OUTLET_DELETE (1 << 0) /* Outlet deleted */
106 #define OUTLET_OUT (1 << 1) /* Outlet outgoing */
107 #define OUTLET_VISITED (1 << 2) /* Outlet visited */
108 } Outlet;
109
110 typedef dnaDCL(Outlet, OutletList);
111
112 typedef struct /* Junction */
113 {
114 Point p; /* intersection point */
115 OutletList outlets; /* list of incoming or outgoing segments */
116 int inCount; /* number of incoming segments */
117 int outCount; /* number of outgoing segments */
118 } Junction;
119
120 typedef struct /* Glyph */
121 {
122 abfGlyphInfo *info; /* General info */
123 float hAdv; /* Horizontal advance width */
124 long iPath; /* First path index; -1 if no path */
125 } Glyph;
126
127 typedef struct /* Path */
128 {
129 Rect bounds; /* Path bounds */
130 long flags; /* Status flags */
131 #define PATH_ISECT (1 << 0) /* Path intersected */
132 long iSeg; /* First segment index */
133 long iPrev; /* Previous path index */
134 long iNext; /* Next path index */
135 } Path;
136
137 typedef struct
138 {
139 int cnt; /* Number of extrema (up to 2) */
140 float t[2]; /* t corresponding to extrema on curve */
141 float v[2]; /* coordinates at extrema */
142 } Extrema;
143
144 typedef struct /* Segment */
145 {
146 Rect bounds; /* Segment bounds */
147 Point p0; /* Line: p0, p3; curve: p0, p1, p2, p3 */
148 Point p1;
149 Point p2;
150 Point p3;
151 Extrema xExtrema; /* Curve extrema */
152 Extrema yExtrema;
153 long flags; /* Status flags */
154 #define SEG_DELETE (1 << 0) /* Segment deleted */
155 #define SEG_LINE (1 << 1) /* Line segment (else curve segment) */
156 #define SEG_ISECT (1 << 2) /* Segment intersected */
157 #define SEG_WIND_TEST (1 << 3) /* Segment winding tested */
158 #define SEG_REVERSE (1 << 4) /* Segment to be reversed */
159 #define SEG_VISITED (1 << 5) /* Segment has been visited during path reconstruction */
160 long iPrev; /* Previous segment index */
161 long iNext; /* Next segment index */
162 long iPath; /* Parent path */
163 long inJunc; /* ingoing junction index */
164 long outJunc; /* outgoing junction index */
165 float score; /* Confidence level of delete/undelete status (non-negative) */
166 } Segment;
167
168 typedef dnaDCL(float, ValueList);
169
170 struct abfCtx_ /* Context */
171 {
172 long flags;
173 abfTopDict *top;
174 dnaDCL(Glyph, glyphs);
175 dnaDCL(Path, paths);
176 dnaDCL(Segment, segs);
177 dnaDCL(Intersect, isects);
178 dnaDCL(Junction, juncs);
179 ValueList xExtremaList;
180 ValueList yExtremaList;
181 long iGlyph; /* Current glyph index */
182 long iPath; /* Current path index */
183 long iSeg; /* Current segment index */
184 Point p; /* Current point */
185 ctlMemoryCallbacks mem;
186 dnaCtx fail; /* Failing dna context */
187 dnaCtx safe; /* Safe dna context */
188 struct /* Error handling */
189 {
190 _Exc_Buf env;
191 int code;
192 } err;
193 };
194
195 static void isectGlyph(abfCtx h, long iGlyph);
196 static void splitBez(Bezier *a, Bezier *b, float t);
197
198 /* ----------------------------- Error Handling ---------------------------- */
199
200 /* Handle fatal error. */
201 static void fatal(abfCtx h, int err_code) {
202 h->err.code = err_code;
203 RAISE(&h->err.env, h->err.code, NULL);
204 }
205
206 /* -------------------------- Fail dynarr Context -------------------------- */
207
208 /* Initialize failing dynarr context. Return 1 on failure else 0. */
209 static dnaCtx dna_FailInit(abfCtx h) {
210 return dnaNew(&h->mem, DNA_CHECK_ARGS);
211 }
212
213 /* -------------------------- Safe dynarr Context -------------------------- */
214
215 /* Manage memory. */
216 static void *dna_SafeManage(ctlMemoryCallbacks *cb, void *old, size_t size) {
217 abfCtx h = (abfCtx)cb->ctx;
218 void *ptr = h->mem.manage(&h->mem, old, size);
219 if (size > 0 && ptr == NULL)
220 fatal(h, abfErrNoMemory);
221 return ptr;
222 }
223
224 /* Initialize safe dynarr context. Return 1 on failure else 0. */
225 static dnaCtx dna_SafeInit(abfCtx h) {
226 ctlMemoryCallbacks cb;
227 cb.ctx = h;
228 cb.manage = dna_SafeManage;
229 return dnaNew(&cb, DNA_CHECK_ARGS);
230 }
231
232 /* --------------------------- Context Management -------------------------- */
233
234 /* Create new library context. */
235 abfCtx abfNew(ctlMemoryCallbacks *mem_cb, CTL_CHECK_ARGS_DCL) {
236 abfCtx h;
237
238 /* Check client/library compatibility */
239 if (CTL_CHECK_ARGS_TEST(ABF_VERSION))
240 return NULL;
241
242 /* Allocate context */
243 h = (abfCtx)mem_cb->manage(mem_cb, NULL, sizeof(struct abfCtx_));
244 if (h == NULL)
245 return NULL;
246
247 /* Safety initialization */
248 memset(h, 0, sizeof(*h));
249 h->err.code = abfErrNoMemory;
250
251 DURING_EX(h->err.env)
252 /* Copy callbacks */
253 h->mem = *mem_cb;
254
255 /* Initialize service libraries */
256 h->fail = NULL;
257 h->safe = NULL;
258 h->fail = dna_FailInit(h);
259 h->safe = dna_SafeInit(h);
260 if (h->fail == NULL || h->safe == NULL) {
261 goto cleanup;
262 }
263
264 /* Initialize */
265 h->flags = 0;
266 dnaINIT(h->fail, h->glyphs, 1, 250);
267 dnaINIT(h->fail, h->paths, 20, 500);
268 dnaINIT(h->fail, h->segs, 100, 5000);
269 dnaINIT(h->safe, h->isects, 10, 20);
270 dnaINIT(h->safe, h->juncs, 10, 20);
271 dnaINIT(h->safe, h->xExtremaList, 100, 100);
272 dnaINIT(h->safe, h->yExtremaList, 100, 100);
273 h->iGlyph = -1;
274 h->iPath = -1;
275 h->iSeg = -1;
276 h->err.code = abfSuccess;
277
278 cleanup:;
279 HANDLER
280 END_HANDLER
281 if (h->err.code != abfSuccess) {
282 abfFree(h);
283 h = NULL;
284 }
285
286 return h;
287 }
288
289 static void freeOutlets(abfCtx h) {
290 long i;
291
292 for (i = 0; i < h->juncs.cnt; i++)
293 dnaFREE(h->juncs.array[i].outlets);
294 }
295
296 /* Free library context. */
297 int abfFree(abfCtx h) {
298 if (h == NULL)
299 return abfSuccess;
300
301 dnaFREE(h->glyphs);
302 dnaFREE(h->paths);
303 dnaFREE(h->segs);
304 dnaFREE(h->isects);
305 freeOutlets(h);
306 dnaFREE(h->juncs);
307 dnaFREE(h->xExtremaList);
308 dnaFREE(h->yExtremaList);
309 dnaFree(h->fail);
310 dnaFree(h->safe);
311 h->mem.manage(&h->mem, h, 0);
312
313 return abfSuccess;
314 }
315
316 /* Begin new font. */
317 int abfBegFont(abfCtx h, abfTopDict *top) {
318 h->top = top;
319 h->glyphs.cnt = 0;
320 h->paths.cnt = 0;
321 h->segs.cnt = 0;
322
323 return abfSuccess;
324 }
325
326 /* End font. */
327 int abfEndFont(abfCtx h, long flags, abfGlyphCallbacks *glyph_cb) {
328 long i;
329
330 if (h->err.code == abfErrNoMemory)
331 return abfErrNoMemory;
332
333 /* Set error handler */
334 DURING_EX(h->err.env)
335
336 if (flags & ABF_PATH_REMOVE_OVERLAP)
337 for (i = 0; i < h->glyphs.cnt; i++)
338 isectGlyph(h, i);
339
340 /* Callback glyphs */
341 for (i = 0; i < h->glyphs.cnt; i++) {
342 long iPath;
343 Glyph *glyph = &h->glyphs.array[i];
344
345 /* Callback glyph begin and handle return value */
346 switch (glyph_cb->beg(glyph_cb, glyph->info)) {
347 case ABF_CONT_RET:
348 break;
349 case ABF_WIDTH_RET:
350 glyph_cb->width(glyph_cb, glyph->hAdv);
351 glyph_cb->end(glyph_cb);
352 continue;
353 case ABF_SKIP_RET:
354 continue;
355 case ABF_QUIT_RET:
356 return abfErrCstrQuit;
357 case ABF_FAIL_RET:
358 return abfErrCstrFail;
359 }
360
361 /* Callback width */
362 glyph_cb->width(glyph_cb, glyph->hAdv);
363
364 iPath = glyph->iPath;
365 if (iPath != -1)
366 do {
367 /* Callback path */
368 Path *path = &h->paths.array[iPath];
369 long iFirst = path->iSeg;
370 Segment *first = &h->segs.array[iFirst];
371 long iLast = first->iPrev;
372 long iStop =
373 (h->segs.array[iLast].flags & SEG_LINE) ? iLast : iFirst;
374 Segment *seg = first;
375 long segcnt = 0;
376
377 /* Callback initial move */
378 glyph_cb->move(glyph_cb, first->p0.x, first->p0.y);
379
380 /* Callback remaining segments */
381 for (;;) {
382 long iSeg;
383
384 if (seg->flags & SEG_LINE)
385 glyph_cb->line(glyph_cb, seg->p3.x, seg->p3.y);
386 else
387 glyph_cb->curve(glyph_cb,
388 seg->p1.x, seg->p1.y,
389 seg->p2.x, seg->p2.y,
390 seg->p3.x, seg->p3.y);
391
392 if (++segcnt > h->segs.cnt)
393 /* Infinite loop! */
394 fatal(h, abfErrCantHandle);
395
396 iSeg = seg->iNext;
397 if (iSeg == iStop)
398 break;
399 seg = &h->segs.array[iSeg];
400 }
401
402 iPath = path->iNext;
403 } while (iPath != glyph->iPath);
404
405 /* Callback glyph end */
406 glyph_cb->end(glyph_cb);
407 }
408
409 HANDLER
410 return h->err.code;
411 END_HANDLER
412
413 return abfSuccess;
414 }
415
416 /* ---------------------------- Glyph Callbacks ---------------------------- */
417
418 /* Begin new glyph. */
419 static int glyphBeg(abfGlyphCallbacks *cb, abfGlyphInfo *info) {
420 abfCtx h = (abfCtx)cb->direct_ctx;
421 Glyph *glyph;
422
423 cb->info = info;
424
425 /* Allocate new glyph */
426 h->iGlyph = dnaNext(&h->glyphs, sizeof(Glyph));
427 if (h->iGlyph == -1) {
428 h->err.code = abfErrNoMemory;
429 return ABF_FAIL_RET;
430 }
431
432 /* Initialize */
433 glyph = &h->glyphs.array[h->iGlyph];
434 glyph->info = info;
435 glyph->iPath = h->paths.cnt;
436
437 h->iPath = -1;
438 h->iSeg = 1;
439
440 return ABF_CONT_RET;
441 }
442
443 /* Add glyph width. */
444 static void glyphWidth(abfGlyphCallbacks *cb, float hAdv) {
445 abfCtx h = (abfCtx)cb->direct_ctx;
446
447 if (h->iGlyph == -1) {
448 h->err.code = abfErrBadPath;
449 return;
450 }
451
452 h->glyphs.array[h->iGlyph].hAdv = hAdv;
453 }
454
455 /* Get new segment. */
456 static Segment *newSegment(abfCtx h) {
457 Segment *seg;
458
459 /* Allocate new segment */
460 h->iSeg = dnaNext(&h->segs, sizeof(Segment));
461 if (h->iSeg == -1) {
462 h->err.code = abfErrNoMemory;
463 return NULL;
464 }
465
466 /* Initialize */
467 seg = &h->segs.array[h->iSeg];
468 seg->iPrev = h->iSeg - 1;
469 seg->iNext = h->iSeg + 1;
470 seg->iPath = h->iPath;
471 seg->inJunc = -1;
472 seg->outJunc = -1;
473 seg->score = 0;
474
475 return seg;
476 }
477
478 /* Add line segment to path. */
479 static void glyphLine(abfGlyphCallbacks *cb, float x1, float y1) {
480 abfCtx h = (abfCtx)cb->direct_ctx;
481 Segment *seg;
482
483 if (x1 == h->p.x && y1 == h->p.y)
484 return; /* Ignore zero-length lines */
485
486 seg = newSegment(h);
487 if (seg == NULL)
488 return;
489
490 /* Fill segment */
491 seg->flags = SEG_LINE;
492 seg->p0 = h->p;
493 seg->p3.x = x1;
494 seg->p3.y = y1;
495 h->p = seg->p3;
496 }
497
498 /* Close the current path */
499 static void closepath(abfGlyphCallbacks *cb) {
500 abfCtx h = (abfCtx)cb->direct_ctx;
501 long iBeg;
502 long iEnd;
503 Point *p;
504
505 if (h->iPath == -1)
506 return; /* First move */
507
508 /* Get first point on path */
509 iBeg = h->paths.array[h->iPath].iSeg;
510 if (iBeg == h->segs.cnt) {
511 /* Remove empty path */
512 h->paths.cnt--;
513 return;
514 }
515 p = &h->segs.array[iBeg].p0;
516
517 if (fabs(p->x - h->p.x) < 1 && fabs(p->y - h->p.y) < 1) {
518 /* Avoid adding almost zero length line segment to close a path */
519 *p = h->p;
520 } else {
521 /* Insert line segment to close path */
522 glyphLine(cb, p->x, p->y);
523 if (h->iSeg == -1)
524 return;
525 }
526
527 /* Make loop */
528 iEnd = h->iSeg;
529 h->segs.array[iBeg].iPrev = iEnd;
530 h->segs.array[iEnd].iNext = iBeg;
531
532 h->iPath = -1;
533 }
534
535 /* Add move to path. */
536 static void glyphMove(abfGlyphCallbacks *cb, float x0, float y0) {
537 abfCtx h = (abfCtx)cb->direct_ctx;
538 Path *path;
539
540 closepath(cb);
541 if (h->iSeg == -1)
542 return;
543
544 /* Allocate new path */
545 h->iPath = dnaNext(&h->paths, sizeof(Path));
546 if (h->iPath == -1) {
547 h->err.code = abfErrNoMemory;
548 return;
549 }
550
551 /* Initialize */
552 path = &h->paths.array[h->iPath];
553 path->flags = 0;
554 path->iSeg = h->segs.cnt;
555 path->iPrev = h->iPath - 1;
556 path->iNext = h->iPath + 1;
557
558 /* Set current point */
559 h->p.x = x0;
560 h->p.y = y0;
561 }
562
563 /* Add curve segment to path. */
564 static void glyphCurve(abfGlyphCallbacks *cb,
565 float x1, float y1,
566 float x2, float y2,
567 float x3, float y3) {
568 abfCtx h = (abfCtx)cb->direct_ctx;
569 Segment *seg;
570
571 if (x1 == h->p.x && y1 == h->p.y && x1 == x2 && y1 == y2 && x2 == x3 && y2 == y3)
572 return; /* Ignore zero-length curves */
573
574 seg = newSegment(h);
575 if (seg == NULL)
576 return;
577
578 /* Fill segment */
579 seg->flags = 0;
580 seg->p0 = h->p;
581 seg->p1.x = x1;
582 seg->p1.y = y1;
583 seg->p2.x = x2;
584 seg->p2.y = y2;
585 seg->p3.x = x3;
586 seg->p3.y = y3;
587 h->p = seg->p3;
588 }
589
590 /* Glyph path general operator. */
591 static void glyphGenop(abfGlyphCallbacks *cb,
592 int cnt, float *args, int op) {
593 abfCtx h = (abfCtx)cb->direct_ctx;
594 h->err.code = abfErrGlyphGenop;
595 }
596
597 /* Glyph path seac. */
598 static void glyphSeac(abfGlyphCallbacks *cb,
599 float adx, float ady, int bchar, int achar) {
600 abfCtx h = (abfCtx)cb->direct_ctx;
601 h->err.code = abfErrGlyphSeac;
602 }
603
604 /* Set bounds on line segment. */
605 static void setLineBounds(Rect *r, Point *u0, Point *u1) {
606 if (u0->x < u1->x) {
607 r->left = u0->x;
608 r->right = u1->x;
609 } else {
610 r->left = u1->x;
611 r->right = u0->x;
612 }
613 if (u0->y < u1->y) {
614 r->bottom = u0->y;
615 r->top = u1->y;
616 } else {
617 r->bottom = u1->y;
618 r->top = u0->y;
619 }
620 }
621
622 /* Set horizontal or vertical limits (other than end points) on Bezier curve.*/
623 static void setBezLimits(float p0, float p1, float p2, float p3,
624 float *lo, float *hi) {
625 float t[2];
626 int i = 0;
627 float a = p3 - 3 * (p2 - p1) - p0;
628 float b = p2 - 2 * p1 + p0;
629 float c = p1 - p0;
630 if (a == 0) {
631 if (b != 0)
632 t[i++] = -c / (2 * b);
633 } else {
634 float r = b * b - a * c;
635 if (r >= 0) {
636 r = (float)sqrt(r);
637 t[i++] = (-b + r) / a;
638 t[i++] = (-b - r) / a;
639 }
640 }
641 while (i--)
642 if (t[i] > 0 && t[i] < 1) {
643 float limit = t[i] * (t[i] * (t[i] * a + 3 * b) + 3 * c) + p0;
644 if (limit < *lo)
645 *lo = limit;
646 else if (limit > *hi)
647 *hi = limit;
648 }
649 }
650
651 /* Set bounds on Bezier curve. */
652 static void setCurveBounds(Rect *r, Point *p0, Point *p1, Point *p2, Point *p3) {
653 /* Set initial bounds from end points */
654 setLineBounds(r, p0, p3);
655
656 if (p1->x < r->left || p1->x > r->right ||
657 p2->x < r->left || p2->x > r->right)
658 /* Grow left and/or right bounds */
659 setBezLimits(p0->x, p1->x, p2->x, p3->x, &r->left, &r->right);
660
661 if (p1->y < r->bottom || p1->y > r->top ||
662 p2->y < r->bottom || p2->y > r->top)
663 /* Grow top and/or bottom bounds */
664 setBezLimits(p0->y, p1->y, p2->y, p3->y, &r->bottom, &r->top);
665 }
666
667 /* Find curve extrema using sub-division of Bezier curve.
668 The derivative quadratic equation may not necessarily produce accurate results
669 with a curve with a sharp turn. */
670 static void findBezExtrema(float *min, float *max, float *mint, float *maxt,
671 float v0, float v1, float v2, float v3, float t0, float t1) {
672 if (v0 < *min) {
673 *min = v0;
674 *mint = t0;
675 }
676 if (v3 < *min) {
677 *min = v3;
678 *mint = t1;
679 }
680 if (v0 > *max) {
681 *max = v0;
682 *maxt = t0;
683 }
684 if (v3 > *max) {
685 *max = v3;
686 *maxt = t1;
687 }
688
689 if (v1 < *min - EXTREMUM_EPSILON || v2 < *min - EXTREMUM_EPSILON ||
690 v1 > *max + EXTREMUM_EPSILON || v2 > *max + EXTREMUM_EPSILON) {
691 float s, t, u, c, ct;
692
693 /* Compute intermediate point */
694 s = (v2 + v3) / 2;
695 t = (v1 + v2) / 2;
696 u = (v0 + v1) / 2;
697 c = (s + 2 * t + u) / 4;
698 ct = (t0 + t1) / 2;
699
700 /* First half of split */
701 findBezExtrema(min, max, mint, maxt, v0, u, (t + u) / 2, c, t0, ct);
702
703 /* Second half of split */
704 findBezExtrema(min, max, mint, maxt, c, (s + t) / 2, s, v3, ct, t1);
705 } else {
706 if (v1 < *min)
707 *min = v1;
708 if (v2 < *min)
709 *min = v2;
710 if (v1 > *max)
711 *max = v1;
712 if (v2 > *max)
713 *max = v2;
714 }
715 }
716
717 static void setBezExtrema(Extrema *ex, float *lo, float *hi, float v0, float v1, float v2, float v3) {
718 float min, max;
719 float mint, maxt;
720 int i;
721
722 ex->cnt = 0;
723 if (v0 < v3) {
724 min = v0;
725 max = v3;
726 } else {
727 min = v3;
728 max = v0;
729 }
730
731 mint = maxt = 0;
732 findBezExtrema(&min, &max, &mint, &maxt, v0, v1, v2, v3, 0, 1);
733 i = 0;
734 if (mint > 0) {
735 ex->t[i] = mint;
736 ex->v[i] = min;
737 i++;
738 }
739 if (maxt > 0) {
740 ex->t[i] = maxt;
741 ex->v[i] = max;
742 i++;
743 }
744 ex->cnt = i;
745 if (i == 2 && mint > maxt) {
746 ex->t[0] = maxt;
747 ex->v[0] = max;
748 ex->t[1] = mint;
749 ex->v[1] = min;
750 }
751
752 *lo = min;
753 *hi = max;
754 }
755
756 /* Set bounds on Bezier curve. */
757 static void setCurveBoundsAndExtrema(Segment *seg) {
758 setBezExtrema(&seg->xExtrema, &seg->bounds.left, &seg->bounds.right, seg->p0.x, seg->p1.x, seg->p2.x, seg->p3.x);
759 setBezExtrema(&seg->yExtrema, &seg->bounds.bottom, &seg->bounds.top, seg->p0.y, seg->p1.y, seg->p2.y, seg->p3.y);
760 }
761
762 /* Set segment bounds and curve extrema. */
763 static void setSegBounds(Segment *seg) {
764 if (seg->flags & SEG_LINE)
765 setLineBounds(&seg->bounds, &seg->p0, &seg->p3);
766 else
767 setCurveBoundsAndExtrema(seg);
768 }
769
770 /* Grow bounds of rect r to include bounds of rect r1. */
771 static void rectGrow(Rect *r, Rect *r1) {
772 if (r->left > r1->left)
773 r->left = r1->left;
774 if (r->bottom > r1->bottom)
775 r->bottom = r1->bottom;
776 if (r->right < r1->right)
777 r->right = r1->right;
778 if (r->top < r1->top)
779 r->top = r1->top;
780 }
781
782 /* Set path bounds. */
783 static void setPathBounds(abfCtx h, Path *path) {
784 Segment *seg = &h->segs.array[path->iSeg];
785
786 /* Set and copy first segment bounds */
787 setSegBounds(seg);
788 path->bounds = seg->bounds;
789
790 /* Grow bounds for remaining segments */
791 for (;;) {
792 long iSeg = seg->iNext;
793 if (iSeg == path->iSeg)
794 break;
795 seg = &h->segs.array[iSeg];
796 setSegBounds(seg);
797 rectGrow(&path->bounds, &seg->bounds);
798 }
799 }
800
801 /* Glyph path end. */
802 static void glyphEnd(abfGlyphCallbacks *cb) {
803 abfCtx h = (abfCtx)cb->direct_ctx;
804 long i;
805 long iFirst;
806 long iLast;
807
808 /* Close last path */
809 closepath(cb);
810 if (h->iSeg == -1)
811 return;
812
813 iFirst = h->glyphs.array[h->iGlyph].iPath;
814 iLast = h->paths.cnt - 1;
815 if (iFirst > iLast) {
816 /* Non-marking glyph */
817 h->glyphs.array[h->iGlyph].iPath = -1;
818 return;
819 }
820
821 /* Make loop */
822 h->paths.array[iFirst].iPrev = iLast;
823 h->paths.array[iLast].iNext = iFirst;
824
825 /* Set bounds */
826 for (i = iFirst; i <= iLast; i++)
827 setPathBounds(h, &h->paths.array[i]);
828
829 h->iGlyph = -1;
830 }
831
832 /* Return 1 if rectangles intersect else 0. */
833 static int rectOverlap(Rect *r1, Rect *r2) {
834 return !(r1->right < r2->left ||
835 r1->left > r2->right ||
836 r1->top < r2->bottom ||
837 r1->bottom > r2->top);
838 }
839
840 /* Intersect rects r1 and r2 to produce rect r. */
841 static void rectIsect(Rect *r, Rect *r1, Rect *r2) {
842 r->left = MAX(r1->left, r2->left);
843 r->bottom = MAX(r1->bottom, r2->bottom);
844 r->right = MIN(r1->right, r2->right);
845 r->top = MIN(r1->top, r2->top);
846 }
847
848 /* Intersect lines u0->u1 and v0->v1. Returns as follows:
849
850 0 lines don't intersect
851 1 lines intersect; line0 at t[0]
852 line1 at t[1]
853 2 lines intersect; line0 at t[0] and t[2]
854 line1 at t[1] and t[3]
855 */
856 static int isectLines(Point *u0, Point *u1, Point *v0, Point *v1, float t[4]) {
857 float a0 = u1->y - u0->y;
858 float b0 = u1->x - u0->x;
859 float a1 = v1->y - v0->y;
860 float b1 = v1->x - v0->x;
861 float d = a1 * b0 - b1 * a0;
862 float j = u0->y - v0->y;
863 float k = u0->x - v0->x;
864 float n0 = b1 * j - a1 * k;
865
866 if (d == 0) {
867 /* Lines are parallel */
868 if (n0 == 0) {
869 /* Lines are coincident; compute intersection rect */
870 Rect r;
871 Rect r1;
872 Rect r2;
873
874 setLineBounds(&r1, u0, u1);
875 setLineBounds(&r2, v0, v1);
876 if (!rectOverlap(&r1, &r2))
877 return 0;
878
879 rectIsect(&r, &r1, &r2);
880
881 if (r.left == r.right && r.bottom == r.top) {
882 /* Lines touch at end points */
883 if (b0 != 0) {
884 /* Compute t horizontally */
885 t[0] = (float)(u1->x == r.left);
886 t[1] = (float)(v1->x == r.left);
887 } else {
888 /* Compute t vertically */
889 t[0] = (float)(u1->y == r.bottom);
890 t[1] = (float)(v1->y == r.bottom);
891 }
892 return 1;
893 } else if (r.right - r.left > r.top - r.bottom) {
894 /* Compute t horizontally */
895 t[0] = (r.left - u0->x) / b0;
896 t[1] = (r.left - v0->x) / b1;
897 t[2] = (r.right - u0->x) / b0;
898 t[3] = (r.right - v0->x) / b1;
899 return 2;
900 } else {
901 /* Compute t vertically */
902 t[0] = (r.bottom - u0->y) / a0;
903 t[1] = (r.bottom - v0->y) / a1;
904 t[2] = (r.top - u0->y) / a0;
905 t[3] = (r.top - v0->y) / a1;
906 return 2;
907 }
908 } else
909 return 0;
910 }
911
912 /* Non-parallel lines; check they both have intercepts */
913 t[0] = n0 / d;
914 if (t[0] < 0 || t[0] > 1)
915 return 0;
916
917 t[1] = (b0 * j - a0 * k) / d;
918 if (t[1] < 0 || t[1] > 1)
919 return 0;
920
921 return 1;
922 }
923
924 /* Compute intersection point on line segment. */
925 static Point calcLineIsectPoint(float t, Segment *seg) {
926 Point p;
927 p.x = seg->p0.x + t * (seg->p3.x - seg->p0.x);
928 p.y = seg->p0.y + t * (seg->p3.y - seg->p0.y);
929 return p;
930 }
931
932 /* Compute intersection point on Bezier segment. */
933 static Point calcCurveIsectPoint(float t, Segment *seg) {
934 Point p;
935 p.x = t * (t * (t * (seg->p3.x - 3 * (seg->p2.x - seg->p1.x) - seg->p0.x) +
936 3 * (seg->p2.x - 2 * seg->p1.x + seg->p0.x)) +
937 3 * (seg->p1.x - seg->p0.x)) + seg->p0.x;
938 p.y = t * (t * (t * (seg->p3.y - 3 * (seg->p2.y - seg->p1.y) - seg->p0.y) +
939 3 * (seg->p2.y - 2 * seg->p1.y + seg->p0.y)) +
940 3 * (seg->p1.y - seg->p0.y)) + seg->p0.y;
941 return p;
942 }
943
944 /* Search for insertion position. Returns an index where a new intersection point is added.
945 * if the point exactly matches an existing intersection, its index is returned and match is set to 2
946 * if a close match is found, match is set to 1
947 */
948 static long checkIsect(abfCtx h, Point *p, Segment *seg, float t, int *match) {
949 long i;
950
951 /* Search for insertion position for the same segment */
952 for (i = 0; i < h->isects.cnt; i++) {
953 Intersect *isect = &h->isects.array[i];
954 Segment *isectSeg = &h->segs.array[isect->iSeg];
955 long iPath = isectSeg->iPath;
956
957 if (iPath == seg->iPath) {
958 if (seg == isectSeg && t == isect->t) {
959 *match = 2; /* Matches previous intersection */
960 return i;
961 }
962 }
963 }
964
965 /* Search for an close enough intersection */
966 for (i = 0; i < h->isects.cnt; i++) {
967 Intersect *isect = &h->isects.array[i];
968 Point u;
969 Point v;
970
971 u = *p;
972 v = isect->p;
973 if ((fabs(v.x - u.x) <= ISECT_EPSILON) &&
974 (fabs(v.y - u.y) <= ISECT_EPSILON)) {
975 *p = isect->p;
976 *match = 1; /* Closely matches previous intersection */
977 return i;
978 }
979 }
980 *match = 0;
981 return i;
982 }
983
984 /* Insert intersection at the index. */
985 static void insertIsect(abfCtx h, long i, Point *p, Segment *seg, float t, long id) {
986 Intersect *_new;
987
988 /* Insert new record */
989 _new = &dnaGROW(h->isects, h->isects.cnt)[i];
990 memmove(_new + 1, _new, (h->isects.cnt++ - i) * sizeof(Intersect));
991 _new->t = t;
992 _new->iSeg = (long)(seg - h->segs.array);
993 _new->iSplit = -1;
994 _new->p = *p;
995 _new->id = id;
996 _new->flags = 0;
997
998 /* Mark path as intersected */
999 h->paths.array[seg->iPath].flags |= PATH_ISECT;
1000 }
1001
1002 /* Save intersection pair. */
1003 static void saveIsectPair(abfCtx h,
1004 Segment *seg0, float t0, Segment *seg1, float t1) {
1005 Point p;
1006 long id = h->isects.cnt;
1007 long i0, i1;
1008 int match0, match1;
1009
1010 /* If the intersection point is at the split point for self-intersecting curve test, ignore it */
1011 if ((seg0 == seg1) && (t0 == t1))
1012 return;
1013
1014 /* Compute intersection point */
1015 if (t0 == 0)
1016 p = seg0->p0;
1017 else if (t0 == 1)
1018 p = seg0->p3;
1019 else if (t1 == 0)
1020 p = seg1->p0;
1021 else if (t1 == 1)
1022 p = seg1->p3;
1023 else if (seg0->flags & SEG_LINE)
1024 p = calcLineIsectPoint(t0, seg0);
1025 else if (seg1->flags & SEG_LINE)
1026 p = calcLineIsectPoint(t1, seg1);
1027 else
1028 p = calcCurveIsectPoint(t0, seg0);
1029
1030 #if CLAMP_ISECT_T
1031 {
1032 /* If intersection is very close to end of segment, force it to end */
1033 float x = RND(p.x);
1034 float y = RND(p.y);
1035 if (0 < t0 && t0 < 1 &&
1036 ((x == seg0->p0.x && y == seg0->p0.y) ||
1037 (x == seg0->p3.x && y == seg0->p3.y)))
1038 t0 = RND(t0);
1039 if (0 < t1 && t1 < 1 &&
1040 ((x == seg1->p0.x && y == seg1->p0.y) ||
1041 (x == seg1->p3.x && y == seg1->p3.y)))
1042 t1 = RND(t1);
1043 }
1044 #endif
1045
1046 /* If the intersection is actually the end point between two adjacent segments in the same path, ignore it */
1047 if (seg0->iPath == seg1->iPath) {
1048 long iSeg1 = (long)(seg1 - h->segs.array);
1049 if ((seg0->iNext == iSeg1) && (t0 == 1 || t1 == 0))
1050 return;
1051 if ((seg0->iPrev == iSeg1) && (t0 == 0 || t1 == 1))
1052 return;
1053 }
1054
1055 i0 = checkIsect(h, &p, seg0, t0, &match0);
1056 i1 = checkIsect(h, &p, seg1, t1, &match1);
1057
1058 /* assign the same id of an existing matching intersection if there is one */
1059 if (match0 || match1) {
1060 int m = match0;
1061 long i = i0;
1062 /* Prefer an exact match */
1063 if (match0 < match1) {
1064 m = match1;
1065 i = i1;
1066 }
1067 id = h->isects.array[i].id;
1068
1069 /* If it was a close-match, unify the intersection points
1070 to prevent further close matches from floating away */
1071 if (m == 1)
1072 p = h->isects.array[i].p;
1073
1074 /* If the two exact matches happen to have distinct intersection IDs, unify them altogether */
1075 if (match0 == 2 && match1 == 2 && h->isects.array[i0].id != h->isects.array[i1].id) {
1076 long id1 = h->isects.array[i1].id;
1077 long j;
1078 for (j = 0; j < h->isects.cnt; j++)
1079 if (h->isects.array[j].id == id1)
1080 h->isects.array[j].id = id;
1081 }
1082 }
1083
1084 insertIsect(h, i0, &p, seg0, t0, id);
1085 /* recalculate insertion index as it might have changed */
1086 if (i0 <= i1)
1087 i1 = checkIsect(h, &p, seg1, t1, &match1);
1088 insertIsect(h, i1, &p, seg1, t1, id);
1089 }
1090
1091 /* Intersect a line/line segments. */
1092 static void isectLineLineSegs(abfCtx h, Segment *s0, Segment *s1) {
1093 float t[4];
1094 switch (isectLines(&s0->p0, &s0->p3, &s1->p0, &s1->p3, t)) {
1095 case 0:
1096 break;
1097 case 2:
1098 saveIsectPair(h, s0, t[2], s1, t[3]);
1099 /* Fall through */
1100 case 1:
1101 saveIsectPair(h, s0, t[0], s1, t[1]);
1102 break;
1103 }
1104 }
1105
1106 /* Check if line u0->u1 intersects with rectangle r. Return 1 if intersection
1107 else 0. Cohen-Sutherland algorithm. */
1108 static int isectLineRect(Point *u0, Point *u1, Rect *r) {
1109 enum /* Clip codes */
1110 {
1111 Left = 1,
1112 Right = 2,
1113 Bottom = 4,
1114 Top = 8
1115 };
1116 int c0;
1117 int c1;
1118
1119 if (u0->x < r->left)
1120 c0 = Left;
1121 else if (u0->x > r->right)
1122 c0 = Right;
1123 else
1124 c0 = 0;
1125
1126 if (u0->y > r->top)
1127 c0 |= Top;
1128 else if (u0->y < r->bottom)
1129 c0 |= Bottom;
1130
1131 if (c0 == 0)
1132 return 1;
1133
1134 if (u1->x < r->left)
1135 c1 = Left;
1136 else if (u1->x > r->right)
1137 c1 = Right;
1138 else
1139 c1 = 0;
1140
1141 if (u1->y > r->top)
1142 c1 |= Top;
1143 else if (u1->y < r->bottom)
1144 c1 |= Bottom;
1145
1146 if (c1 == 0)
1147 return 1;
1148
1149 return (c0 & c1) == 0;
1150 }
1151
1152 /* Return 1 if curve flat enough else 0. Adapted from the flatten.c in Type 1
1153 rasterizer. */
1154 static int bezFlatEnough(abfCtx h, Bezier *q) {
1155 if (q->depth == BEZ_SPLIT_DEPTH)
1156 return 1;
1157 else if (fabs(q->bounds.right - q->bounds.left) > BEZ_SPLIT_MILLIEM ||
1158 fabs(q->bounds.top - q->bounds.bottom) > BEZ_SPLIT_MILLIEM) {
1159 /* BBox eighth em or bigger, split */
1160 q->depth = 0;
1161 return 0;
1162 } else if (((q->p0.x > q->p1.x || q->p1.x > q->p2.x || q->p2.x > q->p3.x) &&
1163 (q->p3.x > q->p2.x || q->p2.x > q->p1.x || q->p1.x > q->p0.x)) ||
1164 ((q->p0.y > q->p1.y || q->p1.y > q->p2.y || q->p2.y > q->p3.y) &&
1165 (q->p3.y > q->p2.y || q->p2.y > q->p1.y || q->p1.y > q->p0.y)))
1166 /* Points not monotonic in x and y; split */
1167 return 0;
1168 else {
1169 /* Split if control points not spaced evenly within .003 em */
1170 float eps3 = MILLIEM(9);
1171 float c1x = (float)fabs(q->p1.x - q->p0.x);
1172 float c3x = (float)fabs(q->p3.x - q->p0.x);
1173 if (fabs(c3x - 3 * c1x) > eps3)
1174 return 0;
1175 else {
1176 float c2x = (float)fabs(q->p2.x - q->p0.x);
1177 if (fabs(2 * (c3x - c2x) - c2x) > eps3)
1178 return 0;
1179 else {
1180 float c1y = (float)fabs(q->p1.y - q->p0.y);
1181 float c3y = (float)fabs(q->p3.y - q->p0.y);
1182 if (fabs(c3y - 3 * c1y) > eps3)
1183 return 0;
1184 else {
1185 float c2y = (float)fabs(q->p2.y - q->p0.y);
1186 if (fabs(2 * (c3y - c2y) - c2y) > eps3)
1187 return 0;
1188 }
1189 }
1190 }
1191 }
1192 return 1;
1193 }
1194
1195 /* Split Bezier curve a at the midpoint into Bezier curves b and a. */
1196 static void splitBezMid(Bezier *a, Bezier *b) {
1197 Point s;
1198 Point t;
1199 Point u;
1200 Point c;
1201 float ct;
1202
1203 /* Compute intermediate points */
1204 s.x = (a->p2.x + a->p3.x) / 2;
1205 s.y = (a->p2.y + a->p3.y) / 2;
1206 t.x = (a->p1.x + a->p2.x) / 2;
1207 t.y = (a->p1.y + a->p2.y) / 2;
1208 u.x = (a->p0.x + a->p1.x) / 2;
1209 u.y = (a->p0.y + a->p1.y) / 2;
1210 c.x = (s.x + 2 * t.x + u.x) / 4;
1211 c.y = (s.y + 2 * t.y + u.y) / 4;
1212 ct = (a->t0 + a->t1) / 2;
1213
1214 /* Compute first half of split (curve b) */
1215 b->p0 = a->p0;
1216 b->p1 = u;
1217 b->p2.x = (t.x + u.x) / 2;
1218 b->p2.y = (t.y + u.y) / 2;
1219 b->p3 = c;
1220 b->t0 = a->t0;
1221 b->t1 = ct;
1222 b->iSeg = a->iSeg;
1223 b->depth = ++a->depth;
1224 setCurveBounds(&b->bounds, &b->p0, &b->p1, &b->p2, &b->p3);
1225
1226 /* Compute second half of split (curve a) */
1227 a->p0 = c;
1228 a->p1.x = (s.x + t.x) / 2;
1229 a->p1.y = (s.y + t.y) / 2;
1230 a->p2 = s;
1231 a->t0 = ct;
1232 setCurveBounds(&a->bounds, &a->p0, &a->p1, &a->p2, &a->p3);
1233 /* p3, t1, and iSeg unchanged */
1234 }
1235
1236 /* Intersect line/curve by recursive subdivision of curve. */
1237 static void isectLineCurve(abfCtx h, Line *l, Bezier a) {
1238 for (;;)
1239 if (bezFlatEnough(h, &a)) {
1240 float t[4];
1241 switch (isectLines(&l->p0, &l->p1, &a.p0, &a.p3, t)) {
1242 case 0:
1243 return;
1244 case 2:
1245 saveIsectPair(h,
1246 &h->segs.array[a.iSeg],
1247 a.t0 + t[3] * (a.t1 - a.t0),
1248 &h->segs.array[l->iSeg],
1249 l->t0 + t[2] * (l->t1 - l->t0));
1250 /* Fall through */
1251 case 1:
1252 saveIsectPair(h,
1253 &h->segs.array[a.iSeg],
1254 a.t0 + t[1] * (a.t1 - a.t0),
1255 &h->segs.array[l->iSeg],
1256 l->t0 + t[0] * (l->t1 - l->t0));
1257 return;
1258 }
1259 } else if (isectLineRect(&l->p0, &l->p1, &a.bounds)) {
1260 /* Split a into b and a */
1261 Bezier b;
1262 splitBezMid(&a, &b);
1263 isectLineCurve(h, l, b);
1264 } else
1265 return;
1266 }
1267
1268 /* Make a Bezier record from curve segment. */
1269 static void makeBez(abfCtx h, Segment *s, Bezier *a) {
1270 a->p0 = s->p0;
1271 a->p1 = s->p1;
1272 a->p2 = s->p2;
1273 a->p3 = s->p3;
1274 a->t0 = 0;
1275 a->t1 = 1;
1276 a->depth = 0;
1277 a->iSeg = (long)(s - h->segs.array);
1278 a->bounds = s->bounds;
1279 }
1280
1281 /* Make a Line record from line segment. */
1282 static void makeLine(abfCtx h, Segment *s, Line *l) {
1283 l->p0 = s->p0;
1284 l->p1 = s->p3;
1285 l->t0 = 0;
1286 l->t1 = 1;
1287 l->iSeg = (long)(s - h->segs.array);
1288 }
1289
1290 /* Intersect a line/curve segments. */
1291 static void isectLineCurveSegs(abfCtx h, Segment *l, Segment *c) {
1292 Line u;
1293 Bezier q;
1294 makeLine(h, l, &u);
1295 makeBez(h, c, &q);
1296 isectLineCurve(h, &u, q);
1297 }
1298
1299 /* Intersect curve/curve by alternate recursive subdivision of curves. */
1300 static void isectCurveCurve(abfCtx h, Bezier a, Bezier b) {
1301 if (!rectOverlap(&a.bounds, &b.bounds))
1302 return;
1303 else if (bezFlatEnough(h, &a)) {
1304 Line l;
1305 l.p0 = a.p0;
1306 l.p1 = a.p3;
1307 l.iSeg = a.iSeg;
1308 l.t0 = a.t0;
1309 l.t1 = a.t1;
1310 isectLineCurve(h, &l, b);
1311 } else {
1312 /* Split a into c and a */
1313 Bezier c;
1314 splitBezMid(&a, &c);
1315 isectCurveCurve(h, b, c);
1316 isectCurveCurve(h, b, a);
1317 }
1318 }
1319
1320 /* Intersect a curve/curve segments. */
1321 static void isectCurveCurveSegs(abfCtx h, Segment *s0, Segment *s1) {
1322 if (s0->p0.x == s1->p0.x && s0->p0.y == s1->p0.y &&
1323 s0->p1.x == s1->p1.x && s0->p1.y == s1->p1.y &&
1324 s0->p2.x == s1->p2.x && s0->p2.y == s1->p2.y &&
1325 s0->p3.x == s1->p3.x && s0->p3.y == s1->p3.y) {
1326 /* Coincident identical curves; intersect endpoints */
1327 saveIsectPair(h, s0, 0, s1, 0);
1328 saveIsectPair(h, s0, 1, s1, 1);
1329 } else if (s0->p0.x == s1->p3.x && s0->p0.y == s1->p3.y &&
1330 s0->p1.x == s1->p2.x && s0->p1.y == s1->p2.y &&
1331 s0->p2.x == s1->p1.x && s0->p2.y == s1->p1.y &&
1332 s0->p3.x == s1->p0.x && s0->p3.y == s1->p0.y) {
1333 /* Reversed coincident identical curves; intersect endpoints */
1334 saveIsectPair(h, s0, 0, s1, 1);
1335 saveIsectPair(h, s0, 1, s1, 0);
1336 } else {
1337 /* Complex intersection */
1338 Bezier a;
1339 Bezier b;
1340 makeBez(h, s0, &a);
1341 makeBez(h, s1, &b);
1342 isectCurveCurve(h, a, b);
1343 }
1344 }
1345
1346 /* Intersect pair of segments. */
1347 static void isectSegPair(abfCtx h, Segment *s0, Segment *s1) {
1348 if (s0->flags & SEG_LINE) {
1349 if (s1->flags & SEG_LINE)
1350 isectLineLineSegs(h, s0, s1);
1351 else
1352 isectLineCurveSegs(h, s0, s1);
1353 } else {
1354 if (s1->flags & SEG_LINE)
1355 isectLineCurveSegs(h, s1, s0);
1356 else
1357 isectCurveCurveSegs(h, s0, s1);
1358 }
1359 }
1360
1361 /* Intersect pair of paths. */
1362 static void isectPathPair(abfCtx h, Path *h0, Path *h1) {
1363 long i;
1364 long j;
1365 long iEnd0 = h->segs.array[h0->iSeg].iPrev;
1366 long iEnd1 = h->segs.array[h1->iSeg].iPrev;
1367
1368 for (i = h0->iSeg; i <= iEnd0; i++) {
1369 Segment *s0 = &h->segs.array[i];
1370 for (j = h1->iSeg; j <= iEnd1; j++) {
1371 Segment *s1 = &h->segs.array[j];
1372 if (rectOverlap(&s0->bounds, &s1->bounds))
1373 isectSegPair(h, s0, s1);
1374 }
1375 }
1376 }
1377
1378 /* Check if a curve may be self-intersecting.
1379 If a curve is self-intersecting, lines from p0 to p1 and from p2 to p3 must be intersecting.
1380 Note that the opposite is not necessarily is true */
1381 static int checkSelfIsectCurve(Point *p0, Point *p1, Point *p2, Point *p3) {
1382 float t[4];
1383 if (p0->x == p3->x && p0->y == p3->y) return 0;
1384 if (p0->x == p1->x && p0->y == p1->y) return 0;
1385 if (p2->x == p2->x && p3->y == p3->y) return 0;
1386 return isectLines(p0, p1, p2, p3, t) != 0;
1387 }
1388
1389 /* Find the intersection of a self-intersecting curve. */
1390 static void selfIsectCurve(abfCtx h, Segment *seg) {
1391 float lo = 0, hi = 1;
1392 Bezier a = {0}, b, c = {0};
1393 int foundSplit = 0;
1394
1395 /* First find a point to split the curve in two
1396 so that the split curves are no longer intersecting each other.
1397 */
1398 makeBez(h, seg, &c);
1399 b = c; /* initialize bounds */
1400 while (lo < hi) {
1401 int isecta, isectb;
1402 float t;
1403
1404 t = (lo + hi) / 2;
1405 a = c;
1406 splitBez(&a, &b, t);
1407 isecta = checkSelfIsectCurve(&a.p0, &a.p1, &a.p2, &a.p3);
1408 isectb = checkSelfIsectCurve(&b.p0, &b.p1, &b.p2, &b.p3);
1409
1410 if (isecta && isectb)
1411 fatal(h, abfErrCantHandle); /* shouldn't happen */
1412 else if (isecta)
1413 hi = t;
1414 else if (isectb)
1415 lo = t;
1416 else {
1417 foundSplit = 1;
1418 break;
1419 }
1420 }
1421 if (!foundSplit)
1422 fatal(h, abfErrCantHandle); /* shouldn't happen */
1423
1424 /* the self-intersecting curve split in two as a and b which are no longer intersecting.
1425 find an intersection between two which must be the intersection of the original curve */
1426 isectCurveCurve(h, a, b);
1427 }
1428
1429 /* Self-intersect path segments. */
1430 static void selfIsectPath(abfCtx h, Path *path) {
1431 long i;
1432 long j;
1433 long iEnd = h->segs.array[path->iSeg].iPrev;
1434
1435 for (i = path->iSeg; i < iEnd; i++) {
1436 Segment *s0 = &h->segs.array[i];
1437 for (j = i + 1; j <= iEnd; j++) {
1438 Segment *s1 = &h->segs.array[j];
1439 if (rectOverlap(&s0->bounds, &s1->bounds))
1440 isectSegPair(h, s0, s1);
1441 }
1442 }
1443
1444 /* Check self-intersecting curves. */
1445 for (i = path->iSeg; i < iEnd; i++) {
1446 Segment *s = &h->segs.array[i];
1447 if (!(s->flags & SEG_LINE) &&
1448 checkSelfIsectCurve(&s->p0, &s->p1, &s->p2, &s->p3)) {
1449 selfIsectCurve(h, s);
1450 }
1451 }
1452 }
1453
1454 /* Compare intersections by ISECT_DUP, segment, t. */
1455 static int CTL_CDECL cmpSegs(const void *first, const void *second) {
1456 Intersect *a = (Intersect *)first;
1457 Intersect *b = (Intersect *)second;
1458 int da = (a->flags & ISECT_DUP) != 0;
1459 int db = (b->flags & ISECT_DUP) != 0;
1460
1461 if (da < db)
1462 return -1;
1463 else if (da > db)
1464 return 1;
1465 else if (a->iSeg < b->iSeg)
1466 return -1;
1467 else if (a->iSeg > b->iSeg)
1468 return 1;
1469 else if (a->t < b->t)
1470 return -1;
1471 else if (a->t > b->t)
1472 return 1;
1473 else
1474 return 0;
1475 }
1476
1477 /* Return 1 if curve is can be converted into a line else 0. */
1478 static int curveIsLine(abfCtx h, Segment *seg) {
1479 float a = seg->p3.y - seg->p0.y;
1480 float b = seg->p3.x - seg->p0.x;
1481 if (fabs(a) <= 1 && fabs(b) <= 1)
1482 return 1; /* Segment within unit square */
1483 else {
1484 float s = a * (seg->p1.x - seg->p0.x) + b * (seg->p0.y - seg->p1.y);
1485 float t = a * (seg->p2.x - seg->p0.x) + b * (seg->p0.y - seg->p2.y);
1486 float tol = MILLIEM(1);
1487 return (s * s + t * t) < tol * tol * (a * a + b * b);
1488 }
1489 }
1490
1491 /* Split segment at intersection point. */
1492 static void splitSegment(abfCtx h, Intersect *last, Intersect *isect) {
1493 long iNew;
1494 Segment *_new;
1495 Segment *seg;
1496 float t = isect->t;
1497 long iSeg = isect->iSeg;
1498
1499 if (last != NULL && last->iSeg == isect->iSeg) {
1500 /* Second or subsequent intercept on same segment */
1501 if (t == last->t || t == 1) {
1502 isect->iSplit = last->iSplit;
1503 return;
1504 } else if (last->iSplit != -1) {
1505 t = (t - last->t) / (1 - last->t);
1506 iSeg = last->iSplit;
1507 }
1508 } else if (t == 0 || t == 1)
1509 return;
1510
1511 /* Split segment; allocate new segment */
1512 iNew = dnaNext(&h->segs, sizeof(Segment));
1513 if (iNew == -1)
1514 fatal(h, abfErrNoMemory);
1515 _new = &h->segs.array[iNew];
1516 seg = &h->segs.array[iSeg];
1517
1518 if (seg->flags & SEG_LINE) {
1519 /* Split line segment */
1520 _new->p0 = isect->p;
1521 _new->p3 = seg->p3;
1522 seg->p3 = isect->p;
1523
1524 _new->flags = SEG_LINE;
1525 } else {
1526 /* Split curve segment */
1527 Point p0 = seg->p0;
1528 Point p1 = seg->p1;
1529 Point p2 = seg->p2;
1530 Point p3 = seg->p3;
1531
1532 seg->p1.x = t * (p1.x - p0.x) + seg->p0.x;
1533 seg->p1.y = t * (p1.y - p0.y) + seg->p0.y;
1534 seg->p2.x = t * t * (p2.x - 2 * p1.x + p0.x) + 2 * seg->p1.x - seg->p0.x;
1535 seg->p2.y = t * t * (p2.y - 2 * p1.y + p0.y) + 2 * seg->p1.y - seg->p0.y;
1536 seg->p3 = isect->p;
1537 if (curveIsLine(h, seg))
1538 seg->flags |= SEG_LINE; /* Make line segment */
1539
1540 t = 1 - t;
1541 _new->p3 = p3;
1542 _new->p2.x = t * (p2.x - p3.x) + _new->p3.x;
1543 _new->p2.y = t * (p2.y - p3.y) + _new->p3.y;
1544 _new->p1.x = t * t * (p1.x - 2 * p2.x + p3.x) + 2 * _new->p2.x - _new->p3.x;
1545 _new->p1.y = t * t * (p1.y - 2 * p2.y + p3.y) + 2 * _new->p2.y - _new->p3.y;
1546 _new->p0 = seg->p3;
1547 _new->flags = 0;
1548 if (curveIsLine(h, _new))
1549 _new->flags |= SEG_LINE; /* Make line segment */
1550 }
1551
1552 /* Link _new segment */
1553 _new->iPrev = iSeg;
1554 _new->iNext = seg->iNext;
1555 _new->iPath = seg->iPath;
1556 _new->inJunc = -1;
1557 _new->outJunc = -1;
1558
1559 /* Set _new bounds */
1560 setSegBounds(seg);
1561 setSegBounds(_new);
1562
1563 seg->iNext = iNew;
1564 h->segs.array[_new->iNext].iPrev = iNew;
1565
1566 isect->iSplit = iNew;
1567 }
1568
1569 #if ROUND_ISECT_COORDS
1570 /* Round points in segment to nearest integer. */
1571 static void roundSegment(abfCtx h, long iSeg, int beg) {
1572 Segment *seg = &h->segs.array[iSeg];
1573
1574 /* Don't round an unsplit end point otherwise it may make a gap */
1575 if (beg) {
1576 seg->p0.x = RND(seg->p0.x);
1577 seg->p0.y = RND(seg->p0.y);
1578 } else {
1579 seg->p3.x = RND(seg->p3.x);
1580 seg->p3.y = RND(seg->p3.y);
1581 }
1582 if (!(seg->flags & SEG_LINE)) {
1583 seg->p1.x = RND(seg->p1.x);
1584 seg->p1.y = RND(seg->p1.y);
1585 seg->p2.x = RND(seg->p2.x);
1586 seg->p2.y = RND(seg->p2.y);
1587 if (curveIsLine(h, seg))
1588 seg->flags |= SEG_LINE; /* Make line segment */
1589 }
1590 setSegBounds(seg);
1591 }
1592 #endif
1593
1594 /* Squash a short negligible segment and update intersections. Returns 1 if any segment is squashed. */
1595 static int squashShortSeg(abfCtx h, Intersect *isect, int isSplit, int atBeg, int *isectSquashed) {
1596 long iSeg = isSplit ? isect->iSplit : isect->iSeg;
1597 Segment *seg = &h->segs.array[iSeg];
1598 int segSquashed = 0;
1599
1600 if ((seg->flags & SEG_LINE) &&
1601 (seg->bounds.right - seg->bounds.left <= SHORT_LINE_LIMIT) &&
1602 (seg->bounds.top - seg->bounds.bottom <= SHORT_LINE_LIMIT)) {
1603 /* Remove this short segment at an intersection from linked segments, isect, and path */
1604
1605 if (seg->iNext != iSeg && seg->iPrev != iSeg) {
1606 Path *path;
1607 long iRep;
1608 Segment *rep;
1609 long i;
1610
1611 segSquashed = 1;
1612 /* Replace the short segment with the next/previous segment in the link */
1613 if (isSplit ^ atBeg) {
1614 iRep = seg->iNext;
1615 rep = &h->segs.array[iRep];
1616 rep->p0 = isect->p;
1617 } else {
1618 iRep = seg->iPrev;
1619 rep = &h->segs.array[iRep];
1620 rep->p3 = isect->p;
1621 }
1622 if (isSplit)
1623 isect->iSplit = iRep;
1624 else
1625 isect->iSeg = iRep;
1626 rep->flags |= SEG_ISECT;
1627
1628 /* Update segment link and bounds */
1629 h->segs.array[seg->iPrev].iNext = seg->iNext;
1630 h->segs.array[seg->iNext].iPrev = seg->iPrev;
1631 setSegBounds(rep);
1632
1633 /* Update path if necessary */
1634 path = &h->paths.array[seg->iPath];
1635 if (path->iSeg == iSeg)
1636 path->iSeg = iRep;
1637
1638 /* Delete the short segment */
1639 seg->flags |= SEG_DELETE;
1640
1641 for (i = 0; i < h->isects.cnt; i++) {
1642 Intersect *i2 = &h->isects.array[i];
1643
1644 if (!(i2->flags & ISECT_DUP)) {
1645 if (i2->iSeg == iSeg)
1646 i2->iSeg = iRep;
1647 if (i2->iSplit == iSeg)
1648 i2->iSplit = iRep;
1649
1650 /* If removing the segment degenerates an intersection, squash it as well */
1651 if (i2->iSeg == i2->iSplit) {
1652 i2->flags |= ISECT_DUP;
1653 *isectSquashed = 1;
1654 }
1655 }
1656 }
1657 }
1658 }
1659 return segSquashed;
1660 }
1661
1662 /* Split intersecting segments. */
1663 static void splitIsectSegs(abfCtx h) {
1664 long i;
1665 Intersect *last;
1666 Intersect *isect;
1667 int isectSquashed = 0;
1668
1669 /* Sort list by segment */
1670 qsort(h->isects.array, h->isects.cnt, sizeof(Intersect), cmpSegs);
1671
1672 /* Look for a segment intersecting at its end. If there is one,
1673 check if the next segment in the same path is intersecting at its beginning.
1674 Such an interseciton is a duplicate and marked as such and merged together
1675 with the same intersection ID. */
1676 for (i = 0; i < h->isects.cnt; i++) {
1677 long iSeg, iNextSeg, j;
1678 Intersect *next = NULL;
1679 int found = 0;
1680
1681 isect = &h->isects.array[i];
1682 if ((isect->flags & ISECT_DUP) || isect->t != 1)
1683 continue;
1684 iSeg = isect->iSeg;
1685 iNextSeg = h->segs.array[iSeg].iNext;
1686
1687 j = (iNextSeg > iSeg) ? i + 1 : 0;
1688 for (; j < h->isects.cnt; j++) {
1689 next = &h->isects.array[j];
1690 if (next->iSeg == iNextSeg && next->t == 0) {
1691 found = 1;
1692 break;
1693 } else if (next->iSeg > iNextSeg)
1694 break;
1695 }
1696 if (found) {
1697 long origId = isect->id;
1698 isect->flags |= ISECT_DUP;
1699 if (isect->id != next->id) {
1700 for (j = 0; j < h->isects.cnt; j++) {
1701 Intersect *i1 = &h->isects.array[j];
1702 if (i1->id == origId)
1703 i1->id = next->id;
1704 }
1705 }
1706 }
1707 }
1708
1709 /* Split segments */
1710 last = NULL;
1711 for (i = 0; i < h->isects.cnt; i++) {
1712 isect = &h->isects.array[i];
1713 if (last && isect->id == last->id &&
1714 isect->iSeg == last->iSeg) {
1715 isect->flags |= ISECT_DUP;
1716 continue;
1717 }
1718 splitSegment(h, last, isect);
1719 last = isect;
1720 }
1721
1722 /* Move duplicate intersections to end */
1723 qsort(h->isects.array, h->isects.cnt, sizeof(Intersect), cmpSegs);
1724
1725 /* Update connection of multi-split segments */
1726 for (i = h->isects.cnt - 1; i > 0; i--) {
1727 last = &h->isects.array[i - 1];
1728 isect = &h->isects.array[i];
1729
1730 /* Remove duplicate intersections from list */
1731 if (isect->flags & ISECT_DUP) {
1732 dnaSET_CNT(h->isects, i);
1733 continue;
1734 }
1735 if (isect->iSplit != -1 &&
1736 last->iSeg == isect->iSeg && last->iSplit != -1) {
1737 isect->iSeg = last->iSplit;
1738 isect->iSplit = h->segs.array[isect->iSeg].iNext;
1739 }
1740 }
1741
1742 /* Update unsplit segment connections and round end coordinates */
1743 for (i = 0; i < h->isects.cnt; i++) {
1744 Segment *seg;
1745 int atBeg;
1746 isect = &h->isects.array[i];
1747 seg = &h->segs.array[isect->iSeg];
1748
1749 #if ROUND_ISECT_COORDS
1750 isect->p.x = RND(isect->p.x);
1751 isect->p.y = RND(isect->p.y);
1752 #endif
1753 atBeg = (isect->t == 0);
1754 if (isect->iSplit == -1)
1755 isect->iSplit = atBeg ? seg->iPrev : seg->iNext;
1756 #if ROUND_ISECT_COORDS
1757 roundSegment(h, isect->iSeg, atBeg);
1758 roundSegment(h, isect->iSplit, !atBeg);
1759 #endif
1760 /* Mark segments as intersected */
1761 seg->flags |= SEG_ISECT;
1762 h->segs.array[isect->iSplit].flags |= SEG_ISECT;
1763 }
1764 /* Remove short segments from each intersection. */
1765 retry:
1766 for (i = 0; i < h->isects.cnt; i++) {
1767 isect = &h->isects.array[i];
1768
1769 if (!(isect->flags & ISECT_DUP)) {
1770 int atBeg = (isect->t == 0);
1771 int segSquashed = 0;
1772 segSquashed |= squashShortSeg(h, isect, 0, atBeg, &isectSquashed);
1773 segSquashed |= squashShortSeg(h, isect, 1, atBeg, &isectSquashed);
1774 if (segSquashed)
1775 goto retry; /* restart scan for short segments */
1776 }
1777 }
1778
1779 /* If any intersections are squashed above, remove them from list */
1780 if (isectSquashed) {
1781 qsort(h->isects.array, h->isects.cnt, sizeof(Intersect), cmpSegs);
1782 for (i = h->isects.cnt - 1; i > 0; i--) {
1783 isect = &h->isects.array[i];
1784
1785 /* Remove squashed intersections from list */
1786 if (!(isect->flags & ISECT_DUP))
1787 break;
1788 else
1789 dnaSET_CNT(h->isects, i);
1790 }
1791 }
1792 }
1793
1794 /* Compare intersections by id. */
1795 static int CTL_CDECL cmpIds(const void *first, const void *second) {
1796 long a = ((Intersect *)first)->id;
1797 long b = ((Intersect *)second)->id;
1798 if (a < b)
1799 return -1;
1800 else if (a > b)
1801 return 1;
1802 else
1803 return 0;
1804 }
1805
1806 /* Get winding for beg and end values. */
1807 static int getWind(float beg, float end) {
1808 return (beg > end) ? 1 : -1;
1809 }
1810
1811 /* Split Bezier curve at t. */
1812 static void splitBez(Bezier *a, Bezier *b, float t) {
1813 Point p0 = a->p0;
1814 Point p1 = a->p1;
1815 Point p2 = a->p2;
1816 Point p3 = a->p3;
1817
1818 a->p1.x = t * (p1.x - p0.x) + a->p0.x;
1819 a->p1.y = t * (p1.y - p0.y) + a->p0.y;
1820 a->p2.x = t * t * (p2.x - 2 * p1.x + p0.x) + 2 * a->p1.x - a->p0.x;
1821 a->p2.y = t * t * (p2.y - 2 * p1.y + p0.y) + 2 * a->p1.y - a->p0.y;
1822 a->p3.x = t * t * t * (p3.x - 3 * (p2.x - p1.x) - p0.x) +
1823 3 * (a->p2.x - a->p1.x) + a->p0.x;
1824 a->p3.y = t * t * t * (p3.y - 3 * (p2.y - p1.y) - p0.y) +
1825 3 * (a->p2.y - a->p1.y) + a->p0.y;
1826 b->t1 = a->t1;
1827 b->t0 = a->t1 = t;
1828
1829 t = 1 - t;
1830 b->p3 = p3;
1831 b->p2.x = t * (p2.x - p3.x) + b->p3.x;
1832 b->p2.y = t * (p2.y - p3.y) + b->p3.y;
1833 b->p1.x = t * t * (p1.x - 2 * p2.x + p3.x) + 2 * b->p2.x - b->p3.x;
1834 b->p1.y = t * t * (p1.y - 2 * p2.y + p3.y) + 2 * b->p2.y - b->p3.y;
1835 b->p0 = a->p3;
1836 }
1837
1838 /* Find t value that yields the target value from Bezier equation. */
1839 static float solveBezAtValue(float value,
1840 float p3, float p2, float p1, float p0) {
1841 float a = p3 - 3 * (p2 - p1) - p0;
1842 float b = 3 * (p2 - 2 * p1 + p0);
1843 float c = 3 * (p1 - p0);
1844 float lo = 0;
1845 float hi = 1;
1846 float t;
1847
1848 /* Binary search for solution */
1849 for (;;) {
1850 float delta;
1851
1852 t = (lo + hi) / 2;
1853 delta = t * (t * (t * a + b) + c) + p0 - value;
1854 if (fabs(delta) < 0.125)
1855 break;
1856 else if (delta < 0)
1857 lo = t;
1858 else
1859 hi = t;
1860 }
1861 return t;
1862 }
1863
1864 /* Solve segment for x value(s) at given y. */
1865 static int solveSegAtY(Segment *seg, float y, float icepts[3], int wind[3]) {
1866 Bezier q[3];
1867 Extrema *ex;
1868 int cnt;
1869 int i;
1870 int j;
1871
1872 memset(q, 0, sizeof(q));
1873
1874 if (seg->flags & SEG_LINE) {
1875 icepts[0] = seg->p0.x +
1876 (y - seg->p0.y) * (seg->p3.x - seg->p0.x) / (seg->p3.y - seg->p0.y);
1877 wind[0] = getWind(seg->p0.y, seg->p3.y);
1878 return 1;
1879 }
1880
1881 /* Copy curve */
1882 q[0].p0 = seg->p0;
1883 q[0].p1 = seg->p1;
1884 q[0].p2 = seg->p2;
1885 q[0].p3 = seg->p3;
1886
1887 /* Split curve at extrema */
1888 ex = &seg->yExtrema;
1889 cnt = ex->cnt;
1890
1891 /* Split curve(s) */
1892 if (cnt > 0)
1893 splitBez(&q[0], &q[1], ex->t[0]);
1894 if (cnt > 1)
1895 splitBez(&q[1], &q[2], (ex->t[1] - ex->t[0]) / (1 - ex->t[0]));
1896 cnt++;
1897
1898 j = 0;
1899 for (i = 0; i < cnt; i++) {
1900 Point p0;
1901 Point p1;
1902 Point p2;
1903 Point p3;
1904
1905 /* Orient curve */
1906 if (q[i].p3.y > q[i].p0.y) {
1907 p0 = q[i].p0;
1908 p1 = q[i].p1;
1909 p2 = q[i].p2;
1910 p3 = q[i].p3;
1911 } else {
1912 p0 = q[i].p3;
1913 p1 = q[i].p2;
1914 p2 = q[i].p1;
1915 p3 = q[i].p0;
1916 }
1917
1918 wind[j] = getWind(q[i].p0.y, q[i].p3.y);
1919
1920 if (y < p0.y || y > p3.y)
1921 continue;
1922 else if (y == p0.y)
1923 icepts[j++] = p0.x;
1924 else if (y == p3.y)
1925 icepts[j++] = p3.x;
1926 else {
1927 float t = solveBezAtValue(y, p3.y, p2.y, p1.y, p0.y);
1928 icepts[j++] = t * (t * (t * (p3.x - 3 * (p2.x - p1.x) - p0.x) +
1929 3 * (p2.x - 2 * p1.x + p0.x)) +
1930 3 * (p1.x - p0.x)) +
1931 p0.x;
1932 }
1933 }
1934
1935 return j;
1936 }
1937
1938 /* Solve segment for y value(s) at given x. */
1939 static int solveSegAtX(Segment *seg, float x, float icepts[3], int wind[3]) {
1940 Bezier q[3];
1941 Extrema *ex;
1942 int cnt;
1943 int i;
1944 int j;
1945
1946 memset(q, 0, sizeof(q));
1947
1948 if (seg->flags & SEG_LINE) {
1949 icepts[0] = seg->p0.y +
1950 (x - seg->p0.x) * (seg->p3.y - seg->p0.y) / (seg->p3.x - seg->p0.x);
1951 wind[0] = getWind(seg->p0.x, seg->p3.x);
1952 return 1;
1953 }
1954
1955 /* Copy curve */
1956 q[0].p0 = seg->p0;
1957 q[0].p1 = seg->p1;
1958 q[0].p2 = seg->p2;
1959 q[0].p3 = seg->p3;
1960
1961 /* Split curve at extrema */
1962 ex = &seg->xExtrema;
1963 cnt = ex->cnt;
1964
1965 /* Split curve(s) */
1966 if (cnt > 0)
1967 splitBez(&q[0], &q[1], ex->t[0]);
1968 if (cnt > 1)
1969 splitBez(&q[1], &q[2], (ex->t[1] - ex->t[0]) / (1 - ex->t[0]));
1970 cnt++;
1971
1972 j = 0;
1973 for (i = 0; i < cnt; i++) {
1974 Point p0;
1975 Point p1;
1976 Point p2;
1977 Point p3;
1978
1979 /* Orient curve */
1980 if (q[i].p3.x > q[i].p0.x) {
1981 p0 = q[i].p0;
1982 p1 = q[i].p1;
1983 p2 = q[i].p2;
1984 p3 = q[i].p3;
1985 } else {
1986 p0 = q[i].p3;
1987 p1 = q[i].p2;
1988 p2 = q[i].p1;
1989 p3 = q[i].p0;
1990 }
1991
1992 wind[j] = getWind(q[i].p0.x, q[i].p3.x);
1993
1994 if (x < p0.x || x > p3.x)
1995 continue;
1996 else if (x == p0.x)
1997 icepts[j++] = p0.y;
1998 else if (x == p3.x)
1999 icepts[j++] = p3.y;
2000 else {
2001 float t = solveBezAtValue(x, p3.x, p2.x, p1.x, p0.x);
2002 icepts[j++] = t * (t * (t * (p3.y - 3 * (p2.y - p1.y) - p0.y) +
2003 3 * (p2.y - 2 * p1.y + p0.y)) +
2004 3 * (p1.y - p0.y)) +
2005 p0.y;
2006 }
2007 }
2008
2009 return j;
2010 }
2011
2012 /* Get segment winding at specified value. */
2013 static int getWindAtValue(float beg, float end, float value) {
2014 if ((value < beg && value < end) || (value > beg && value > end))
2015 return 0;
2016 else
2017 return (beg > end) ? 1 : -1;
2018 }
2019
2020 static float penalizeCloseCross(float v1, float v2) {
2021 float diff = (float)fabs(v1 - v2);
2022 if (diff < WIND_TEST_EPSILON)
2023 return WIND_TEST_EPSILON - diff;
2024 else
2025 return 0;
2026 }
2027
2028 static long searchValueList(ValueList *list, float val) {
2029 long lo = 0;
2030 long hi = list->cnt - 1;
2031 long t = 0;
2032
2033 /* Binary search for value */
2034 while (lo <= hi) {
2035 float test;
2036
2037 t = (lo + hi) / 2;
2038 test = list->array[t] - val;
2039 if (test == 0)
2040 return t;
2041 else if (test < 0)
2042 lo = t + 1;
2043 else
2044 hi = t - 1;
2045 }
2046 return t;
2047 }
2048
2049 /* Pick a coordinate value for a segment winding test.
2050 Any value between the two ends of the segment should work in theory,
2051 however in order to minimize the chance of math errors, avoid proximity of
2052 end points and extrema of other segments utilizing extrema lists collected earlier. */
2053 static void chooseTargetPoint(abfCtx h, Segment *seg, Point *mid, int testvert) {
2054 float v;
2055 float min, max;
2056 ValueList *list;
2057
2058 if (testvert) {
2059 min = seg->p0.x;
2060 max = seg->p3.x;
2061 list = &h->xExtremaList;
2062 } else {
2063 min = seg->p0.y;
2064 max = seg->p3.y;
2065 list = &h->yExtremaList;
2066 }
2067
2068 if (min == max)
2069 v = min;
2070 else {
2071 float gapVal;
2072 long i, gapIndex = 0;
2073
2074 if (min > max) {
2075 float temp = min;
2076 min = max;
2077 max = temp;
2078 }
2079
2080 /* Search the extrema list for the widest gap between the segment ends. */
2081 i = searchValueList(list, min);
2082 gapVal = -MAXFLOAT;
2083 for (; list->array[i] < max; i++) {
2084 float w = list->array[i + 1] - list->array[i];
2085
2086 /* penalize gaps at both ends of this segment */
2087 if (list->array[i] <= min || list->array[i + 1] >= max)
2088 w -= 5.0f;
2089 if (gapVal < w) {
2090 gapVal = w;
2091 gapIndex = i;
2092 }
2093 }
2094 v = (list->array[gapIndex] + list->array[gapIndex + 1]) / 2;
2095 #if ABF_DEBUG
2096 if (v <= min || v >= max)
2097 fatal(h, abfErrCantHandle);
2098 #endif
2099 }
2100
2101 /* Determine the other coordinate value corresponding to v. */
2102 if (seg->flags & SEG_LINE) {
2103 if (testvert) {
2104 mid->x = v;
2105 mid->y = ((seg->p3.y - seg->p0.y) * (v - seg->p0.x) + (seg->p3.x - seg->p0.x) * seg->p0.y) / (seg->p3.x - seg->p0.x);
2106 } else {
2107 mid->x = ((seg->p3.x - seg->p0.x) * (v - seg->p0.y) + (seg->p3.y - seg->p0.y) * seg->p0.x) / (seg->p3.y - seg->p0.y);
2108 mid->y = v;
2109 }
2110 } else {
2111 int cnt;
2112 float icepts[3];
2113 int wind[3]; /* unused */
2114
2115 memset(icepts, 0, sizeof(icepts));
2116
2117 if (testvert) {
2118 mid->x = v;
2119 cnt = solveSegAtX(seg, v, icepts, wind);
2120 #if ABF_DEBUG
2121 if (cnt <= 0)
2122 fatal(h, abfErrCantHandle);
2123 #endif
2124 mid->y = icepts[0];
2125 } else {
2126 mid->y = v;
2127 cnt = solveSegAtY(seg, v, icepts, wind);
2128 #if ABF_DEBUG
2129 if (cnt <= 0)
2130 fatal(h, abfErrCantHandle);
2131 #endif
2132 mid->x = icepts[0];
2133 }
2134 }
2135 }
2136
2137 /* Rough estimate of segment length for heuristics use. */
2138 static float estSegLen(Segment *seg) {
2139 return (float)(fabs(seg->bounds.right - seg->bounds.left) + fabs(seg->bounds.top - seg->bounds.bottom));
2140 }
2141
2142 /* Set segment score from winding count, its confidence, and the segment length */
2143 static void setWindScore(Segment *seg, int windCount, float conf) {
2144 float score = (float)windCount / 2 + conf;
2145 float len = estSegLen(seg);
2146
2147 score = (float)((score * 0.5) + 1.0);
2148 score = MAX(score, 0);
2149
2150 /* Less confident with short segments */
2151 score *= log10f(len);
2152
2153 seg->score = score;
2154 }
2155
2156 /* Test segment winding on both sides and set flags accordingly.
2157 If both sides are filled/unfilled, delete the segment.
2158 If the wrong side of the segment is filled, reverse its direction. */
2159 static void windTestSeg(abfCtx h, long iTarget) {
2160 Point p;
2161 float icepts[3];
2162 long iPath;
2163 long iBegPath;
2164 int i;
2165 int wind[3];
2166 int testvert;
2167 int windTotalLo, windTotalHi;
2168 float score;
2169 int windtarget;
2170 Segment *target = &h->segs.array[iTarget];
2171
2172 if (target->flags & (SEG_WIND_TEST | SEG_DELETE))
2173 return; /* Ignore checked or deleted segments */
2174
2175 windTotalLo = windTotalHi = 0;
2176 score = 0;
2177 testvert = (fabs(target->p3.x - target->p0.x) >
2178 fabs(target->p3.y - target->p0.y));
2179 if (testvert)
2180 windtarget = getWind(target->p0.x, target->p3.x);
2181 else
2182 windtarget = getWind(target->p0.y, target->p3.y);
2183
2184 /* Choose a target point geometrically between the two ends of the segment */
2185 chooseTargetPoint(h, target, &p, testvert);
2186
2187 iBegPath = target->iPath;
2188 iPath = iBegPath;
2189 do {
2190 long iBegSeg;
2191 long iSeg;
2192 Path *path = &h->paths.array[iPath];
2193 /* Ignore paths that can't affect winding */
2194 if (testvert) {
2195 if (path->bounds.left > p.x ||
2196 path->bounds.right <= p.x)
2197 goto nextpath;
2198 } else {
2199 if (path->bounds.bottom > p.y ||
2200 path->bounds.top <= p.y)
2201 goto nextpath;
2202 }
2203 iBegSeg = path->iSeg;
2204 iSeg = iBegSeg;
2205 do {
2206 Segment *seg = &h->segs.array[iSeg];
2207 if (iSeg == iTarget && (seg->flags & SEG_LINE))
2208 ; /* Winding test with the self-curve is taken care of below */
2209 else if (testvert) {
2210 /* Consider only non-vertical segments below or above. */
2211 if (seg->bounds.left > p.x ||
2212 seg->bounds.right <= p.x ||
2213 seg->bounds.left == seg->bounds.right)
2214 ;
2215 else if (seg->bounds.top < p.y - WIND_TEST_EPSILON)
2216 windTotalLo += getWindAtValue(seg->p0.x, seg->p3.x, p.x);
2217 else if (seg->bounds.bottom > p.y + WIND_TEST_EPSILON)
2218 windTotalHi += getWindAtValue(seg->p0.x, seg->p3.x, p.x);
2219 else {
2220 /* Check coincident segments. Delete all except at most one undeleted. */
2221 if ((iSeg != iTarget) &&
2222 ((seg->flags & SEG_LINE) == (target->flags & SEG_LINE)) &&
2223 /* Coincident in opposite direction */
2224 (((seg->p0.x == target->p3.x &&
2225 seg->p0.y == target->p3.y &&
2226 seg->p3.x == target->p0.x &&
2227 seg->p3.y == target->p0.y) &&
2228 (seg->flags & SEG_LINE ||
2229 (seg->p1.x == target->p2.x &&
2230 seg->p1.y == target->p2.y &&
2231 seg->p2.x == target->p1.x &&
2232 seg->p2.y == target->p1.y)))
2233 /* Coincident in same direction */
2234 || ((seg->p0.x == target->p0.x &&
2235 seg->p0.y == target->p0.y &&
2236 seg->p3.x == target->p3.x &&
2237 seg->p3.y == target->p3.y) &&
2238 (seg->flags & SEG_LINE ||
2239 (seg->p1.x == target->p1.x &&
2240 seg->p1.y == target->p1.y &&
2241 seg->p2.x == target->p2.x &&
2242 seg->p2.y == target->p2.y))))) {
2243 if (!(seg->flags & SEG_DELETE)) {
2244 target->flags |= (SEG_DELETE | SEG_WIND_TEST);
2245 setWindScore(target, 1, score);
2246 return;
2247 }
2248 } else {
2249 int cnt = solveSegAtX(seg, p.x, icepts, wind);
2250 int self = -1;
2251 float mindiff = MAXFLOAT;
2252 if (iTarget == iSeg) {
2253 if (cnt == 1)
2254 self = 0;
2255 else
2256 for (i = 0; i < cnt; i++) {
2257 float d = (float)fabs(icepts[i] - p.y);
2258 if (d < mindiff) {
2259 self = i;
2260 mindiff = d;
2261 }
2262 }
2263 }
2264 for (i = 0; i < cnt; i++) {
2265 int w = wind[i];
2266 if (i != self && w) {
2267 float iy = icepts[i];
2268 if (iy != p.y) {
2269 if (iy < p.y)
2270 windTotalLo += w;
2271 else
2272 windTotalHi += w;
2273
2274 score -= penalizeCloseCross(iy, p.y);
2275 } else
2276 score -= 1.0f; /* overlapping */
2277 }
2278 }
2279 }
2280 }
2281 } else {
2282 /* Consider only non-horizontal segments on the left or on the right */
2283 if (seg->bounds.bottom > p.y ||
2284 seg->bounds.top <= p.y ||
2285 seg->bounds.top == seg->bounds.bottom)
2286 ;
2287 else if (seg->bounds.right < p.x - WIND_TEST_EPSILON)
2288 windTotalLo += getWindAtValue(seg->p0.y, seg->p3.y, p.y);
2289 else if (seg->bounds.left > p.x + WIND_TEST_EPSILON)
2290 windTotalHi += getWindAtValue(seg->p0.y, seg->p3.y, p.y);
2291 else {
2292 /* Check coincident segments. Delete all except at most one undeleted. */
2293 if ((iSeg != iTarget) &&
2294 ((seg->flags & SEG_LINE) == (target->flags & SEG_LINE)) &&
2295 /* Coincident in opposite direction */
2296 (((seg->p0.x == target->p3.x &&
2297 seg->p0.y == target->p3.y &&
2298 seg->p3.x == target->p0.x &&
2299 seg->p3.y == target->p0.y) &&
2300 (seg->flags & SEG_LINE ||
2301 (seg->p1.x == target->p2.x &&
2302 seg->p1.y == target->p2.y &&
2303 seg->p2.x == target->p1.x &&
2304 seg->p2.y == target->p1.y)))
2305 /* Coincident in same direction */
2306 || ((seg->p0.x == target->p0.x &&
2307 seg->p0.y == target->p0.y &&
2308 seg->p3.x == target->p3.x &&
2309 seg->p3.y == target->p3.y) &&
2310 (seg->flags & SEG_LINE ||
2311 (seg->p1.x == target->p1.x &&
2312 seg->p1.y == target->p1.y &&
2313 seg->p2.x == target->p2.x &&
2314 seg->p2.y == target->p2.y))))) {
2315 if (!(seg->flags & SEG_DELETE)) {
2316 target->flags |= (SEG_DELETE | SEG_WIND_TEST);
2317 setWindScore(target, 1, score);
2318 return;
2319 }
2320 } else {
2321 int cnt = solveSegAtY(seg, p.y, icepts, wind);
2322 int self = -1;
2323 float mindiff = MAXFLOAT;
2324 if (iTarget == iSeg) {
2325 if (cnt == 1)
2326 self = 0;
2327 else
2328 for (i = 0; i < cnt; i++) {
2329 float d = (float)fabs(icepts[i] - p.x);
2330 if (d < mindiff) {
2331 self = i;
2332 mindiff = d;
2333 }
2334 }
2335 }
2336 for (i = 0; i < cnt; i++) {
2337 int w = wind[i];
2338 if (i != self && w) {
2339 float ix = icepts[i];
2340 if (ix != p.x) {
2341 if (ix < p.x)
2342 windTotalLo += w;
2343 else
2344 windTotalHi += w;
2345
2346 score -= penalizeCloseCross(ix, p.x);
2347 } else
2348 score -= 1.0f; /* overlapping */
2349 }
2350 }
2351 }
2352 }
2353 }
2354 iSeg = seg->iNext;
2355 } while (iSeg != iBegSeg);
2356 nextpath:
2357 iPath = path->iNext;
2358 } while (iPath != iBegPath);
2359
2360 /* If both sides of the segment is to be filled or unfilled, delete it */
2361 if ((windTotalLo != 0) == (windTotalHi != 0)) {
2362 /* A segment with (almost) overlapping segments is a candidate for undeletion later. */
2363 setWindScore(target, MIN(abs(windTotalLo), abs(windTotalHi)), score);
2364 target->flags |= SEG_DELETE;
2365 } else {
2366 /* A segment with (almost) overlapping segments is a candidate for deletion later */
2367 setWindScore(target, MAX(abs(windTotalLo), abs(windTotalHi)), score);
2368
2369 /* If the wrong side (i.e., not on the left) of the segment is filled,
2370 set the flag so that the segment will be reversed */
2371 if ((testvert && ((windtarget > 0) == (windTotalHi != 0))) ||
2372 (!testvert && ((windtarget < 0) == (windTotalHi != 0))))
2373 target->flags |= SEG_REVERSE;
2374 }
2375
2376 target->flags |= SEG_WIND_TEST;
2377 }
2378
2379 static float segmentAngle(Segment *seg, int end) {
2380 Point vec;
2381
2382 if (seg->flags & SEG_LINE) {
2383 if (end) {
2384 vec.x = seg->p0.x - seg->p3.x;
2385 vec.y = seg->p0.y - seg->p3.y;
2386 } else {
2387 vec.x = seg->p3.x - seg->p0.x;
2388 vec.y = seg->p3.y - seg->p0.y;
2389 }
2390 } else {
2391 if (end) {
2392 vec.x = seg->p2.x - seg->p3.x;
2393 vec.y = seg->p2.y - seg->p3.y;
2394 } else {
2395 vec.x = seg->p1.x - seg->p0.x;
2396 vec.y = seg->p1.y - seg->p0.y;
2397 }
2398 }
2399
2400 return atan2f(vec.y, vec.x);
2401 }
2402
2403 /* Connect a segment to a junction. */
2404 static Junction *connectSegToJunction(abfCtx h, Intersect *isect, long iJunc, Junction *junc, long iSeg, int in) {
2405 Segment *seg = &h->segs.array[iSeg];
2406 int reverse;
2407 int del;
2408 int init = iJunc >= h->juncs.cnt;
2409 Outlet *outlet;
2410
2411 junc = dnaMAX(h->juncs, iJunc);
2412
2413 if (init) {
2414 dnaINIT(h->safe, junc->outlets, 2, 5);
2415 junc->p = isect->p;
2416 junc->inCount = junc->outCount = 0;
2417 }
2418
2419 del = (seg->flags & SEG_DELETE) != 0;
2420 reverse = (seg->flags & SEG_REVERSE) != 0;
2421 outlet = dnaNEXT(junc->outlets);
2422 outlet->seg = iSeg;
2423 outlet->otherJunc = -1;
2424 outlet->otherSeg = -1;
2425 outlet->score = 0;
2426 outlet->flags = 0;
2427
2428 if (del)
2429 outlet->flags |= OUTLET_DELETE;
2430 if (in == !reverse) {
2431 if (!del)
2432 junc->inCount++;
2433 outlet->angle = segmentAngle(seg, !reverse);
2434 seg->inJunc = iJunc;
2435 } else {
2436 if (!del)
2437 junc->outCount++;
2438 outlet->flags |= OUTLET_OUT;
2439 outlet->angle = segmentAngle(seg, reverse);
2440 seg->outJunc = iJunc;
2441 }
2442
2443 return junc;
2444 }
2445
2446 /* Compare outlets by angle. */
2447 static int CTL_CDECL cmpAngles(const void *first, const void *second) {
2448 float a = ((Outlet *)first)->angle;
2449 float b = ((Outlet *)second)->angle;
2450 if (a < b)
2451 return -1;
2452 else if (a > b)
2453 return 1;
2454 else
2455 return 0;
2456 }
2457
2458 /* Sort outlet segments at each junction by angle */
2459 static void sortOutlets(abfCtx h) {
2460 long i, j, k;
2461 Junction *junc;
2462
2463 for (j = 0; j < h->juncs.cnt; j++) {
2464 OutletList *list;
2465 junc = &h->juncs.array[j];
2466 list = &junc->outlets;
2467 qsort(list->array, junc->outlets.cnt, sizeof(Outlet), cmpAngles);
2468
2469 /* Remove duplicate outlets if any */
2470 for (i = 0; i < list->cnt; i++) {
2471 long flags = list->array[i].flags;
2472 for (k = i + 1; k < list->cnt; k++) {
2473 if (list->array[i].seg == list->array[k].seg &&
2474 list->array[i].angle == list->array[k].angle &&
2475 list->array[i].flags == list->array[k].flags) {
2476 memmove(&list->array[k], &list->array[k + 1], sizeof(Outlet) * (list->cnt - k - 1));
2477 list->cnt--;
2478 if (!(flags & OUTLET_DELETE)) {
2479 if (flags & OUTLET_OUT)
2480 junc->outCount--;
2481 else
2482 junc->inCount--;
2483 }
2484 }
2485 }
2486 }
2487 }
2488 }
2489
2490 /* Reset all path and segment flags */
2491 static void resetSegFlags(abfCtx h, long iBeg, long pathFlags, long segFlags) {
2492 long iPath = iBeg;
2493 do {
2494 long i;
2495 Path *path = &h->paths.array[iPath];
2496 path->flags &= ~pathFlags;
2497 iPath = path->iNext;
2498 i = path->iSeg;
2499 do {
2500 Segment *seg = &h->segs.array[i];
2501 seg->flags &= ~segFlags;
2502 i = seg->iNext;
2503 } while (i != path->iSeg);
2504 } while (iPath != iBeg);
2505 }
2506
2507 static long lookupOutlet(abfCtx h, Junction *junc, long iSeg, long flags) {
2508 long i, segMatch = -1;
2509 OutletList *list = &junc->outlets;
2510 Outlet *outlet = NULL;
2511 long mask = OUTLET_OUT;
2512
2513 for (i = 0; i < list->cnt; i++) {
2514 outlet = &list->array[i];
2515 if (outlet->seg == iSeg) {
2516 segMatch = i;
2517 if ((outlet->flags & mask) == (flags & mask))
2518 return i;
2519 }
2520 }
2521 return segMatch;
2522 }
2523
2524 static void modifyOutlet(abfCtx h, Junction *junc, long iSeg, long oldFlags, long newFlags, float adjustScore) {
2525 long i;
2526 // OutletList *list = &junc->outlets;
2527 Outlet *outlet;
2528 long mask = OUTLET_OUT | OUTLET_DELETE;
2529
2530 i = lookupOutlet(h, junc, iSeg, oldFlags);
2531 if (i < 0)
2532 fatal(h, abfErrCantHandle);
2533
2534 outlet = &junc->outlets.array[i];
2535 outlet->flags = (outlet->flags & ~mask) | newFlags;
2536 outlet->score += adjustScore;
2537
2538 if (!(oldFlags & OUTLET_DELETE)) {
2539 if (oldFlags & OUTLET_OUT)
2540 junc->outCount--;
2541 else
2542 junc->inCount--;
2543 }
2544 if (!(newFlags & OUTLET_DELETE)) {
2545 if (newFlags & OUTLET_OUT)
2546 junc->outCount++;
2547 else
2548 junc->inCount++;
2549 }
2550 }
2551
2552 /* Modify flags of segments in a sequence. */
2553 static void modifySegSeqFlags(abfCtx h, long iSeg, long iEndSeg, int forw, long mask, long flags) {
2554 for (;;) {
2555 Segment *seg = &h->segs.array[iSeg];
2556 if ((seg->flags & mask & SEG_REVERSE) != (flags & SEG_REVERSE)) {
2557 long inJunc = seg->inJunc;
2558 seg->inJunc = seg->outJunc;
2559 seg->outJunc = inJunc;
2560 }
2561 seg->flags = (seg->flags & ~mask) | flags;
2562 if (iSeg == iEndSeg)
2563 break;
2564
2565 if (forw)
2566 iSeg = seg->iNext;
2567 else
2568 iSeg = seg->iPrev;
2569 }
2570 }
2571
2572 /* Check consistency of a sequence of segments starting from this outlet. */
2573 static void polishOutlet(abfCtx h, long iJunc, Outlet *begOutlet) {
2574 Junction *begJunc = &h->juncs.array[iJunc];
2575 long iBegSeg = begOutlet->seg;
2576 long iSeg = iBegSeg;
2577 long iEndSeg;
2578 Segment *begSeg = &h->segs.array[iBegSeg];
2579 Segment *seg;
2580 int out = (begOutlet->flags & OUTLET_OUT) != 0;
2581 long begRevFlag = (begSeg->flags & SEG_REVERSE);
2582 int forw = out ^ (begRevFlag != 0);
2583 long revFlag, endRevFlag;
2584 int segCount;
2585 int undelCount = 0;
2586 int delCount = 0;
2587 int revCount = 0;
2588 float totalRevScore = 0;
2589 float totalUndelScore = 0;
2590 float totalDelScore = 0;
2591 float totalScore;
2592 long iEndJunc;
2593 long iEndOutlet;
2594 Outlet *endOutlet;
2595 Junction *endJunc = NULL;
2596 float score = 0;
2597
2598 if (begOutlet->flags & OUTLET_VISITED)
2599 return;
2600 begOutlet->flags |= OUTLET_VISITED;
2601
2602 seg = begSeg;
2603 for (;;) {
2604 int revmis;
2605
2606 /* Check consistency of segments in a sequence. */
2607 seg->flags |= SEG_VISITED;
2608 if (seg->flags & SEG_DELETE) {
2609 delCount++;
2610 totalDelScore += seg->score;
2611 } else {
2612 undelCount++;
2613 totalUndelScore += seg->score;
2614 }
2615
2616 revFlag = (seg->flags & SEG_REVERSE);
2617 revmis = (revFlag != begRevFlag);
2618 if (revmis) {
2619 revCount++;
2620 totalRevScore += seg->score;
2621 }
2622
2623 if (out ^ revmis)
2624 iEndJunc = seg->inJunc;
2625 else
2626 iEndJunc = seg->outJunc;
2627 if (iEndJunc >= 0) {
2628 endJunc = &h->juncs.array[iEndJunc];
2629 iEndSeg = iSeg;
2630 endRevFlag = revFlag;
2631 break;
2632 }
2633
2634 if (forw)
2635 iSeg = seg->iNext;
2636 else
2637 iSeg = seg->iPrev;
2638 seg = &h->segs.array[iSeg];
2639 }
2640
2641 segCount = delCount + undelCount;
2642 totalScore = totalDelScore + totalUndelScore;
2643 score = totalScore / segCount;
2644
2645 /* Set other junction/outlet indices in outlets at both ends */
2646 begOutlet->otherJunc = iEndJunc;
2647 begOutlet->otherSeg = iEndSeg;
2648 iEndOutlet = lookupOutlet(h, endJunc, iEndSeg, begOutlet->flags ^ OUTLET_OUT);
2649 endOutlet = &endJunc->outlets.array[iEndOutlet];
2650 endOutlet->otherJunc = iJunc;
2651 endOutlet->otherSeg = iBegSeg;
2652 endOutlet->flags |= OUTLET_VISITED;
2653
2654 if (delCount > 0 && undelCount <= 0) {
2655 /* All segments are deleted. */
2656 begOutlet->score = score;
2657 endOutlet->score = score;
2658 return;
2659 }
2660
2661 /* Fix inconsistency problems */
2662
2663 /* If deletion status is inconsistent among segments in a sequence,
2664 * delete or undelete the entire sequence depending the average scores between two. */
2665 if (undelCount > 0 && delCount > 0) {
2666 long segFlag = 0;
2667 long segMask = SEG_DELETE;
2668
2669 if (totalDelScore > totalUndelScore) {
2670 segFlag = SEG_DELETE;
2671 segMask = (SEG_DELETE | SEG_REVERSE);
2672 score -= totalUndelScore / undelCount;
2673 } else
2674 score -= totalDelScore / delCount;
2675
2676 /* Delete/undelete the outgoing outlet. */
2677 if ((h->segs.array[iBegSeg].flags & SEG_DELETE) != segFlag) {
2678 begOutlet->score += score;
2679 modifyOutlet(h, begJunc, iBegSeg, begOutlet->flags, begOutlet->flags ^ OUTLET_DELETE, 0);
2680 }
2681
2682 /* Delete/undelete the incoming outlet. */
2683 if ((h->segs.array[iEndSeg].flags & SEG_DELETE) != segFlag) {
2684 endOutlet->score += score;
2685 modifyOutlet(h, endJunc, iEndSeg, endOutlet->flags, endOutlet->flags ^ OUTLET_DELETE, 0);
2686 }
2687
2688 modifySegSeqFlags(h, iBegSeg, iEndSeg, forw, segMask, segFlag);
2689 if (segFlag)
2690 return;
2691
2692 score = 0;
2693 }
2694
2695 /* If any segments have inconsistent reverse flags, then correct minority segments */
2696 if (revCount > 0) {
2697 if (totalScore > totalRevScore * 2) {
2698 revFlag = begRevFlag;
2699 score -= totalRevScore / segCount;
2700 } else {
2701 revFlag = begRevFlag ^ SEG_REVERSE;
2702 score -= (totalScore - totalRevScore) / segCount;
2703 }
2704
2705 modifySegSeqFlags(h, iBegSeg, iEndSeg, forw, SEG_REVERSE, revFlag);
2706
2707 if (revFlag != begRevFlag)
2708 modifyOutlet(h, begJunc, iBegSeg, begOutlet->flags, begOutlet->flags ^ OUTLET_OUT, score);
2709 if (revFlag != endRevFlag)
2710 modifyOutlet(h, endJunc, iEndSeg, endOutlet->flags, endOutlet->flags ^ OUTLET_OUT, score);
2711 score = 0;
2712 }
2713
2714 begOutlet->score += score;
2715 endOutlet->score += score;
2716 }
2717
2718 static int signCountDiff(Junction *junc) {
2719 if (junc->outCount > junc->inCount)
2720 return 1;
2721 else if (junc->outCount < junc->inCount)
2722 return -1;
2723 else
2724 return 0;
2725 }
2726
2727 /* Check consistency of all outlets and segments in between, and score outlets, and fix problems. */
2728 static void polishOutlets(abfCtx h, long iBeg) {
2729 long iJunc, i;
2730 Junction *junc;
2731
2732 for (iJunc = 0; iJunc < h->juncs.cnt; iJunc++) {
2733 junc = &h->juncs.array[iJunc];
2734 for (i = 0; i < junc->outlets.cnt; i++)
2735 polishOutlet(h, iJunc, &junc->outlets.array[i]);
2736 }
2737
2738 /* If the numbers of outlets and inlets at both end junctions of a segment are inconsistent
2739 in the opposite directions, penalize the outlets so that fixBadJunctions will consider
2740 the segment as a candidate for flipping its direction or deletion. */
2741 for (iJunc = 0; iJunc < h->juncs.cnt; iJunc++) {
2742 junc = &h->juncs.array[iJunc];
2743 for (i = 0; i < junc->outlets.cnt; i++) {
2744 Outlet *begOutlet = &junc->outlets.array[i];
2745 Junction *endJunc = &h->juncs.array[begOutlet->otherJunc];
2746 int begDiff = signCountDiff(junc);
2747 int endDiff = signCountDiff(endJunc);
2748
2749 if (begDiff && begDiff == -endDiff) {
2750 int out = (begOutlet->flags & OUTLET_OUT) != 0;
2751 if (((begOutlet->flags & OUTLET_DELETE) != 0) ||
2752 (out && begDiff > 0 && endDiff < 0) ||
2753 (!out && begDiff < 0 && endDiff > 0))
2754 begOutlet->score -= MISMATCH_SEGMENT_PENALTY;
2755 }
2756 }
2757 }
2758
2759 /* Reset visited flag */
2760 resetSegFlags(h, iBeg, 0, SEG_VISITED);
2761 }
2762
2763 /* try fixing junctions by deleting or undeleting an outlet with the least score
2764 Return 1 if all junctions become good (i.e., inlets and outlets are balanced) */
2765 static int fixWorstOutlet(abfCtx h) {
2766 int good = 1;
2767 long i;
2768 long iJunc, iWorstJunc = 0;
2769 Junction *endJunc = NULL, *worstJunc = NULL;
2770 float worstScore;
2771 Outlet *worstOutlet = NULL;
2772 long badFlag = 0;
2773 long iBegSeg, iEndSeg;
2774 Segment *seg;
2775
2776 /* Find the worst outlet */
2777 worstScore = MAXFLOAT;
2778 for (iJunc = 0; iJunc < h->juncs.cnt; iJunc++) {
2779 Junction *junc = &h->juncs.array[iJunc];
2780 int sign = signCountDiff(junc);
2781
2782 if (sign) {
2783 good = 0;
2784
2785 for (i = 0; i < junc->outlets.cnt; i++) {
2786 Outlet *outlet = &junc->outlets.array[i];
2787 float score;
2788 int otherSign;
2789
2790 /* Don't choose an outlet with a segment sequence returning to the same junction */
2791 if (junc == &h->juncs.array[outlet->otherJunc])
2792 continue;
2793
2794 score = outlet->score;
2795
2796 if (!(outlet->flags & OUTLET_DELETE)) {
2797 if (((outlet->flags & OUTLET_OUT) != 0) != (sign > 0))
2798 continue;
2799
2800 score -= EXTRA_OUTLET_PENALTY * (((sign > 0) ? junc->outCount : junc->inCount) - 1);
2801 }
2802
2803 /* If the other junction has an opposite extra outlet, give it penalty */
2804 endJunc = &h->juncs.array[outlet->otherJunc];
2805 otherSign = signCountDiff(endJunc);
2806 if (otherSign && otherSign != sign)
2807 score -= EXTRA_OUTLET_PENALTY;
2808
2809 if (score < worstScore) {
2810 iWorstJunc = iJunc;
2811 worstOutlet = outlet;
2812 worstScore = score;
2813 badFlag = (sign > 0) ? OUTLET_OUT : 0;
2814 }
2815 }
2816 }
2817 }
2818
2819 if (good || !worstOutlet)
2820 return good;
2821
2822 /* Fix a bad junction by flipping deletion flag of an outlet with the least score. */
2823 iBegSeg = worstOutlet->seg;
2824 endJunc = &h->juncs.array[worstOutlet->otherJunc];
2825 iEndSeg = worstOutlet->otherSeg;
2826 worstJunc = &h->juncs.array[iWorstJunc];
2827
2828 if (worstOutlet->flags & OUTLET_DELETE) {
2829 /* Undelete a deleted outlet and the segment sequence starting from it */
2830 long segFlag;
2831 int forw;
2832
2833 seg = &h->segs.array[iBegSeg];
2834 forw = (seg->outJunc == iWorstJunc) ^ ((seg->flags & SEG_REVERSE) != 0);
2835 segFlag = seg->flags & SEG_REVERSE;
2836 if ((seg->inJunc == iWorstJunc) == (badFlag == 0))
2837 segFlag ^= SEG_REVERSE;
2838 modifyOutlet(h, endJunc, iEndSeg, OUTLET_DELETE, badFlag, FIXED_SCORE_INCREMENT);
2839 modifyOutlet(h, worstJunc, iBegSeg, OUTLET_DELETE, badFlag ^ OUTLET_OUT, FIXED_SCORE_INCREMENT);
2840 modifySegSeqFlags(h, iBegSeg, iEndSeg, forw, SEG_REVERSE | SEG_DELETE, segFlag);
2841 } else {
2842 /* Delete an outlet and the segment sequence starting from it */
2843 int forw = ((worstOutlet->flags & OUTLET_OUT) != 0) ^ ((h->segs.array[iBegSeg].flags & SEG_REVERSE) != 0);
2844
2845 modifyOutlet(h, endJunc, iEndSeg, worstOutlet->flags ^ OUTLET_OUT, OUTLET_DELETE, FIXED_SCORE_INCREMENT);
2846 modifyOutlet(h, worstJunc, iBegSeg, worstOutlet->flags, OUTLET_DELETE, FIXED_SCORE_INCREMENT);
2847 modifySegSeqFlags(h, iBegSeg, iEndSeg, forw, SEG_DELETE, SEG_DELETE);
2848 }
2849
2850 return good;
2851 }
2852
2853 /* Each junction must have the same number of incoming and outgoing outlets.
2854 They may become inconsistent due to math errors during intersection and winding order tests
2855 with barely intersecting/overlapping segments.
2856 Fix such junctions heuristically if the numbers of outlets don't match. */
2857 static void fixBadJunctions(abfCtx h, long iBeg) {
2858 int sweep;
2859 int good = 0;
2860
2861 for (sweep = 0; !good && sweep < h->segs.cnt; sweep++)
2862 good = fixWorstOutlet(h);
2863
2864 if (!good) {
2865 /* Last resort: Undelete all segments and restore the path direction. */
2866 resetSegFlags(h, iBeg, PATH_ISECT, SEG_ISECT | SEG_DELETE | SEG_REVERSE);
2867 freeOutlets(h);
2868 h->juncs.cnt = 0;
2869 }
2870 }
2871
2872 static void reverseSeg(Segment *seg) {
2873 Point p0 = seg->p0;
2874 Point p1 = seg->p1;
2875 Point p2 = seg->p2;
2876 Point p3 = seg->p3;
2877 long next = seg->iNext;
2878 long prev = seg->iPrev;
2879
2880 seg->p0 = p3;
2881 seg->p1 = p2;
2882 seg->p2 = p1;
2883 seg->p3 = p0;
2884 seg->iNext = prev;
2885 seg->iPrev = next;
2886 }
2887
2888 static void windTestPaths(abfCtx h, long iBeg) {
2889 /* Check all segments for winding order. */
2890 long iPath = iBeg;
2891
2892 do {
2893 long i;
2894 Path *path = &h->paths.array[iPath];
2895 iPath = path->iNext;
2896 i = path->iSeg;
2897 do {
2898 windTestSeg(h, i);
2899 i = h->segs.array[i].iNext;
2900 } while (i != path->iSeg);
2901 } while (iPath != iBeg);
2902 }
2903
2904 static void addPointToExtremaLists(abfCtx h, Point *p) {
2905 *dnaNEXT(h->xExtremaList) = p->x;
2906 *dnaNEXT(h->yExtremaList) = p->y;
2907 }
2908
2909 static void addExtremaToExtremaList(abfCtx h, Extrema *extrema, ValueList *extremaList) {
2910 long i;
2911 for (i = 0; i < extrema->cnt; i++)
2912 *dnaNEXT(*extremaList) = extrema->v[i];
2913 }
2914
2915 /* Compare intersections by id. */
2916 static int CTL_CDECL cmpVals(const void *first, const void *second) {
2917 float a = *(float *)first;
2918 float b = *(float *)second;
2919 if (a < b)
2920 return -1;
2921 else if (a > b)
2922 return 1;
2923 else
2924 return 0;
2925 }
2926
2927 static void sortValueList(ValueList *list) {
2928 float lastVal = -MAXFLOAT;
2929 long i, j;
2930
2931 qsort(list->array, list->cnt, sizeof(list->array[0]), cmpVals);
2932
2933 /* remove duplicates */
2934 for (i = j = 0; i < list->cnt; i++) {
2935 float val;
2936 val = list->array[i];
2937 if (val != lastVal) {
2938 list->array[j++] = val;
2939 lastVal = val;
2940 }
2941 }
2942 list->cnt = j;
2943 }
2944
2945 /* Collect all x and y values of segment ends and extrema
2946 sort each list for later use in choosing a coordinate value
2947 for winding test with a segment */
2948 static void collectExtrema(abfCtx h) {
2949 long iBeg = h->glyphs.array[h->iGlyph].iPath;
2950 long iPath = iBeg;
2951
2952 do {
2953 long iSeg;
2954 Path *path = &h->paths.array[iPath];
2955 iPath = path->iNext;
2956 iSeg = path->iSeg;
2957 do {
2958 Segment *seg = &h->segs.array[iSeg];
2959
2960 addPointToExtremaLists(h, &seg->p0);
2961 addPointToExtremaLists(h, &seg->p3);
2962 addExtremaToExtremaList(h, &seg->xExtrema, &h->xExtremaList);
2963 addExtremaToExtremaList(h, &seg->yExtrema, &h->yExtremaList);
2964
2965 iSeg = h->segs.array[iSeg].iNext;
2966 } while (iSeg != path->iSeg);
2967 } while (iPath != iBeg);
2968
2969 /* sort both extrema list and remove duplicates */
2970 sortValueList(&h->xExtremaList);
2971 sortValueList(&h->yExtremaList);
2972 }
2973
2974 /* Delete overlapped segments
2975 Check each intersection for in and out non-deleted segments (their counts must match)
2976 Collect them in a junction list */
2977 static void deleteBadSegs(abfCtx h, long iBeg) {
2978 long i, j;
2979 Segment *seg;
2980 long iJunc;
2981
2982 freeOutlets(h);
2983 iJunc = h->juncs.cnt = 0;
2984
2985 /* Sort list by id */
2986 qsort(h->isects.array, h->isects.cnt, sizeof(Intersect), cmpIds);
2987
2988 windTestPaths(h, iBeg);
2989
2990 /* Collect non-deleted segments intersecting at the same point in a junction list */
2991 {
2992 Intersect *firstisect, *lastisect;
2993 long beg, end;
2994 Junction *junc = NULL;
2995 firstisect = lastisect = NULL;
2996 for (i = 0; i < h->isects.cnt; i++) {
2997 Intersect *isect = &h->isects.array[i];
2998
2999 /* Beginning of a series of intersections */
3000 if (firstisect == NULL)
3001 firstisect = isect;
3002
3003 /* Order intersection path from beg to end.
3004 Test isect->t > 0 is to prevent confusion about a path consisting of
3005 only two path segments intersecting at both ends. */
3006 if (h->segs.array[isect->iSeg].iNext == isect->iSplit && isect->t > 0) {
3007 beg = isect->iSeg;
3008 end = isect->iSplit;
3009 } else {
3010 beg = isect->iSplit;
3011 end = isect->iSeg;
3012 }
3013
3014 /* Connect segments to a junction. Count the number of incoming/outgoing segments (outlets). */
3015 junc = connectSegToJunction(h, isect, iJunc, junc, beg, 1);
3016 junc = connectSegToJunction(h, isect, iJunc, junc, end, 0);
3017
3018 /* Check the end of a series of intersections sharing the same id */
3019 if (i + 1 >= h->isects.cnt || isect->id != isect[1].id) {
3020 /* There must be N*2 segments on N paths surrounding an intersection */
3021 /* Start a new series of intersections at the same point */
3022 if (junc) {
3023 iJunc++;
3024 junc = NULL;
3025 }
3026 firstisect = lastisect = NULL;
3027 }
3028 }
3029 }
3030 sortOutlets(h);
3031 polishOutlets(h, iBeg);
3032 fixBadJunctions(h, iBeg);
3033
3034 /* relink segments starting from each junction
3035 Follow the original segment link possibly backwards if a segment is marked SEG_REVERSE
3036 At a junction, choose one of untaken segments in the opposite direction */
3037 for (j = 0; j < h->juncs.cnt; j++) {
3038 long beg;
3039 Junction *junc = &h->juncs.array[j];
3040
3041 for (i = 0; i < junc->outlets.cnt; i++) {
3042 Outlet *outlet1 = &junc->outlets.array[i];
3043 long iSeg, iLastSeg;
3044
3045 if ((outlet1->flags & OUTLET_DELETE) || !(outlet1->flags & OUTLET_OUT))
3046 continue;
3047
3048 /* Pick the next segment to start from */
3049 beg = outlet1->seg;
3050 iLastSeg = -1;
3051 iSeg = beg;
3052 seg = &h->segs.array[iSeg];
3053
3054 if (seg->flags & SEG_VISITED)
3055 continue;
3056
3057 for (;;) {
3058 seg->flags |= SEG_VISITED;
3059 if (seg->flags & SEG_REVERSE)
3060 reverseSeg(seg);
3061 seg->iPrev = iLastSeg;
3062
3063 if (seg->inJunc == j) {
3064 /* reached the starting junction. link the beginning segment
3065 and the ending segment closing a loop */
3066 h->segs.array[beg].iPrev = iSeg;
3067 seg->iNext = beg;
3068 break;
3069 }
3070
3071 /* At a junction, choose an untaken outgoing segment as the next one */
3072 if (seg->inJunc >= 0) {
3073 Junction *junc1 = &h->juncs.array[seg->inJunc];
3074 long k;
3075 float angle = segmentAngle(seg, 1);
3076 long iOutSeg = -1;
3077 long iAnySeg = -1;
3078
3079 /* If there are multiple outgoing segments to choose from at the junction,
3080 choose the closest one to the left so that newly built paths are
3081 touching rather than intersecting at junctions */
3082 for (k = 0; k < junc1->outlets.cnt; k++) {
3083 Outlet *outlet = &junc1->outlets.array[k];
3084
3085 if ((outlet->flags & OUTLET_DELETE) || !(outlet->flags & OUTLET_OUT))
3086 continue;
3087 if (!(h->segs.array[outlet->seg].flags & SEG_VISITED)) {
3088 iAnySeg = outlet->seg;
3089 if (outlet->angle < angle)
3090 iOutSeg = outlet->seg;
3091 }
3092 }
3093
3094 if (iOutSeg < 0)
3095 iOutSeg = iAnySeg;
3096 if (iOutSeg < 0)
3097 fatal(h, abfErrCantHandle); /* shouldn't happen */
3098
3099 /* link the segments */
3100 seg->iNext = iOutSeg;
3101 seg->iPrev = iLastSeg;
3102 }
3103
3104 iLastSeg = iSeg;
3105 iSeg = seg->iNext;
3106 seg = &h->segs.array[iSeg];
3107 if (seg->flags & (SEG_DELETE | SEG_VISITED))
3108 fatal(h, abfErrCantHandle); /* shouldn't happen */
3109 }
3110 }
3111 }
3112 }
3113
3114 /* Create new path starting from iSeg. Path bounds and links must be set by
3115 caller. Returns pointer to new path. */
3116 static Path *newPath(abfCtx h, long iSeg) {
3117 long segcnt;
3118 Path *path;
3119 long iPath = h->paths.cnt;
3120 long i = dnaNext(&h->paths, sizeof(Path));
3121 if (i == -1)
3122 fatal(h, abfErrNoMemory);
3123
3124 path = &h->paths.array[i];
3125 path->flags = 0;
3126 path->iSeg = iSeg;
3127 segcnt = 0;
3128 do {
3129 Segment *seg = &h->segs.array[iSeg];
3130 seg->iPath = iPath;
3131 if (++segcnt > h->segs.cnt)
3132 /* Infinite loop! I've not seen this occur in practice but it seems
3133 prudent to guard against it */
3134 fatal(h, abfErrCantHandle);
3135 iSeg = seg->iNext;
3136 } while (iSeg != path->iSeg);
3137 return path;
3138 }
3139
3140 /* Build new path from junction segment. */
3141 static void buildPath(abfCtx h, long iBegNewPaths, long iSeg) {
3142 Path *path;
3143 Segment *seg = &h->segs.array[iSeg];
3144
3145 if (seg->flags & SEG_DELETE || /* Segment deleted */
3146 seg->iPath >= iBegNewPaths) /* Segment already added to new path */
3147 return;
3148
3149 path = newPath(h, iSeg);
3150 path->bounds = seg->bounds;
3151
3152 /* Build a new path by walking along segments following the original link
3153 if a segment is marked SEG_REVERSE traverse the link backwards
3154 at a junction, choose one of remaining segments in the opposite direction */
3155
3156 /* Grow bounds for remaining segments */
3157 for (;;) {
3158 iSeg = seg->iNext;
3159 if (iSeg == path->iSeg)
3160 break;
3161 seg = &h->segs.array[iSeg];
3162 rectGrow(&path->bounds, &seg->bounds);
3163 }
3164 }
3165
3166 /* Returns 1 if a non-intersecting path should be preserved;
3167 Returns 0 if it should be deleted. */
3168 static int isMarkingPath(abfCtx h, Path *path) {
3169 int segCount, delCount;
3170 long iSeg, iStartSeg;
3171 Segment *seg;
3172
3173 segCount = delCount = 0;
3174 iSeg = iStartSeg = path->iSeg;
3175 for (;;) {
3176 seg = &h->segs.array[iSeg];
3177 segCount++;
3178 if (seg->flags & SEG_DELETE)
3179 delCount++;
3180
3181 iSeg = seg->iNext;
3182 if (iSeg == iStartSeg)
3183 break;
3184 }
3185 return (delCount * 2 <= segCount);
3186 }
3187
3188 /* Delete non-marking, non-intersecting paths */
3189 static void deleteNonMarkingPaths(abfCtx h, long iBeg, long iGlyph) {
3190 long iEnd = h->paths.array[iBeg].iPrev;
3191 long iFirstPath = -1;
3192 long iPrevPath = -1;
3193 long i;
3194
3195 for (i = iBeg; i <= iEnd; i++) {
3196 Path *path;
3197 path = &h->paths.array[i];
3198 #if ABF_DEBUG
3199 if (path->flags & PATH_ISECT)
3200 fatal(h, abfErrCantHandle);
3201 #endif
3202 if (isMarkingPath(h, path)) {
3203 if (iPrevPath != -1) {
3204 path->iPrev = iPrevPath;
3205 h->paths.array[iPrevPath].iNext = i;
3206 }
3207 iPrevPath = i;
3208 if (iFirstPath == -1)
3209 iFirstPath = i;
3210 }
3211 }
3212 if (iFirstPath != -1) {
3213 h->paths.array[iFirstPath].iPrev = iPrevPath;
3214 h->paths.array[iPrevPath].iNext = iFirstPath;
3215 h->glyphs.array[iGlyph].iPath = iFirstPath;
3216 } else /* Unlikely but may happen */
3217 h->glyphs.array[iGlyph].iPath = -1;
3218 }
3219
3220 /* Build new path list. */
3221 static void buildNewPaths(abfCtx h, long iPath, long iGlyph) {
3222 long i, j;
3223 long iBegPath = iPath;
3224 long iBegNewPaths = h->paths.cnt;
3225 long iEndNewPaths;
3226
3227 /* Copy non-intersected, non-deleted paths to new list */
3228 do {
3229 Path *path = &h->paths.array[iPath];
3230 iPath = path->iNext;
3231 if (!(path->flags & PATH_ISECT) && isMarkingPath(h, path)) {
3232 /* Copy bounds since newPath() may invalidate path pointer */
3233 Rect bounds = path->bounds;
3234 newPath(h, path->iSeg)->bounds = bounds;
3235 }
3236 } while (iPath != iBegPath);
3237
3238 /* Build new paths from junctions */
3239 for (j = 0; j < h->juncs.cnt; j++) {
3240 Junction *junc = &h->juncs.array[j];
3241 for (i = 0; i < junc->outlets.cnt; i++) {
3242 Outlet *outlet = &junc->outlets.array[i];
3243 if ((outlet->flags & OUTLET_DELETE) || !(outlet->flags & OUTLET_OUT))
3244 continue;
3245 buildPath(h, iBegNewPaths, outlet->seg);
3246 }
3247 }
3248
3249 /* Use original path start points with new paths if possible */
3250 iPath = iBegPath;
3251 do {
3252 Path *path = &h->paths.array[iPath];
3253 if (path->flags & PATH_ISECT) {
3254 Segment *seg = &h->segs.array[path->iSeg];
3255 if (seg->iPath >= iBegNewPaths)
3256 h->paths.array[seg->iPath].iSeg = path->iSeg;
3257 }
3258 iPath = path->iNext;
3259 } while (iPath != iBegPath);
3260
3261 /* Coalesce co-linear line segments */
3262 for (i = iBegNewPaths; i < h->paths.cnt; i++) {
3263 Path *path = &h->paths.array[i];
3264 int lastdir = 0; /* Suppress optimizer warning */
3265 long iSeg = path->iSeg;
3266 long segcnt = 0;
3267 do {
3268 int thisdir = 0;
3269 Segment *seg = &h->segs.array[iSeg];
3270 if (seg->flags & SEG_LINE) {
3271 if (seg->p0.x == seg->p3.x)
3272 thisdir = 1;
3273 else if (seg->p0.y == seg->p3.y)
3274 thisdir = -1;
3275 else
3276 goto nextseg;
3277
3278 if (iSeg != path->iSeg && thisdir == lastdir) {
3279 /* Remove this segment from path */
3280 Segment *last = &h->segs.array[seg->iPrev];
3281 Segment *next = &h->segs.array[seg->iNext];
3282 last->iNext = seg->iNext;
3283 next->iPrev = seg->iPrev;
3284 last->p3 = seg->p3;
3285 setLineBounds(&last->bounds, &last->p0, &last->p3);
3286 }
3287 }
3288 nextseg:
3289 if (++segcnt > h->segs.cnt)
3290 /* Infinite loop! */
3291 fatal(h, abfErrCantHandle);
3292 lastdir = thisdir;
3293 iSeg = seg->iNext;
3294 } while (iSeg != path->iSeg);
3295 }
3296
3297 /* Link new paths */
3298 iEndNewPaths = h->paths.cnt - 1;
3299 if (iBegNewPaths > iEndNewPaths) {
3300 /* Non-marking glyph */
3301 h->glyphs.array[iGlyph].iPath = -1;
3302 return;
3303 }
3304
3305 /* Make loop */
3306 h->paths.array[iBegNewPaths].iPrev = iEndNewPaths;
3307 h->paths.array[iEndNewPaths].iNext = iBegNewPaths;
3308
3309 /* Link intermediate paths */
3310 for (i = iBegNewPaths; i < iEndNewPaths; i++)
3311 h->paths.array[i].iNext = i + 1;
3312 for (i = iEndNewPaths; i > iBegNewPaths; i--)
3313 h->paths.array[i].iPrev = i - 1;
3314
3315 h->glyphs.array[iGlyph].iPath = iBegNewPaths;
3316 }
3317
3318 /* Intersect glyph paths. */
3319 static void isectGlyph(abfCtx h, long iGlyph) {
3320 long i;
3321 long j;
3322 long iEnd;
3323 long iBeg = h->glyphs.array[iGlyph].iPath;
3324
3325 if (iBeg == -1)
3326 return; /* No path */
3327
3328 iEnd = h->paths.array[iBeg].iPrev;
3329 h->isects.cnt = 0;
3330 h->xExtremaList.cnt = 0;
3331 h->yExtremaList.cnt = 0;
3332 h->iGlyph = iGlyph;
3333
3334 /* Check paths for self-intersection */
3335 for (i = iBeg; i <= iEnd; i++)
3336 selfIsectPath(h, &h->paths.array[i]);
3337
3338 /* Check if different paths intersect each other */
3339 for (i = iBeg; i < iEnd; i++) {
3340 Path *h0 = &h->paths.array[i];
3341 for (j = i + 1; j <= iEnd; j++) {
3342 Path *h1 = &h->paths.array[j];
3343 if (rectOverlap(&h0->bounds, &h1->bounds))
3344 isectPathPair(h, h0, h1);
3345 }
3346 }
3347
3348 if (h->isects.cnt != 0) {
3349 /* Glyph contained intersecting paths */
3350 splitIsectSegs(h);
3351 collectExtrema(h);
3352 deleteBadSegs(h, iBeg);
3353 buildNewPaths(h, iBeg, iGlyph);
3354 } else {
3355 collectExtrema(h);
3356 windTestPaths(h, iBeg);
3357 deleteNonMarkingPaths(h, iBeg, iGlyph);
3358 }
3359 }
3360
3361 /* Glyph path callbacks */
3362 const abfGlyphCallbacks abfGlyphPathCallbacks =
3363 {
3364 NULL,
3365 NULL,
3366 NULL,
3367 glyphBeg,
3368 glyphWidth,
3369 glyphMove,
3370 glyphLine,
3371 glyphCurve,
3372 NULL,
3373 NULL,
3374 glyphGenop,
3375 glyphSeac,
3376 glyphEnd,
3377 NULL,
3378 NULL,
3379 NULL,
3380 };
3381
3382 /* ----------------------------- Debug Support ----------------------------- */
3383
3384 #if ABF_DEBUG
3385
3386 #include <stdio.h>
3387
3388 /* Debug bounds. */
3389 static void dbbounds(Rect *r) {
3390 printf("bounds={%g,%g,%g,%g}\n", r->left, r->bottom, r->right, r->top);
3391 }
3392
3393 /* Debug segment. */
3394 static void dbseg(abfCtx h, long iSeg) {
3395 long i = iSeg;
3396 long segCount = 0;
3397 int seenGoodSeg = 0;
3398
3399 do {
3400 Segment *seg = &h->segs.array[i];
3401 if (segCount++ > h->segs.cnt)
3402 fatal(h, abfErrCantHandle);
3403 printf("--- segment[%ld]\n", i);
3404 dbbounds(&seg->bounds);
3405 printf("p0={%g,%g}\n", seg->p0.x, seg->p0.y);
3406 if (!(seg->flags & SEG_LINE)) {
3407 printf("p1={%g,%g}\n", seg->p1.x, seg->p1.y);
3408 printf("p2={%g,%g}\n", seg->p2.x, seg->p2.y);
3409 }
3410 printf("p3={%g,%g}\n", seg->p3.x, seg->p3.y);
3411 printf("flags=%08lx%s\n", seg->flags, (seg->flags & SEG_DELETE) ? " << DEL " : ((seg->flags & SEG_REVERSE) ? " << REV " : ""));
3412 printf("score={%g}\n", seg->score);
3413 printf("iPrev=%ld\n", seg->iPrev);
3414 printf("iNext=%ld\n", seg->iNext);
3415 printf("iPath=%ld\n", seg->iPath);
3416
3417 if (!seenGoodSeg && !(seg->flags & SEG_DELETE)) {
3418 seenGoodSeg = 1;
3419 iSeg = i;
3420 }
3421 i = seg->iNext;
3422 } while (i != iSeg);
3423 }
3424
3425 /* Debug path. */
3426 static void dbpath(abfCtx h, long iPath) {
3427 Path *path = &h->paths.array[iPath];
3428 printf("--- path[%ld]\n", iPath);
3429 dbbounds(&path->bounds);
3430 printf("flags=%08lx\n", path->flags);
3431 printf("iSeg =%ld\n", path->iSeg);
3432 printf("iPrev=%ld\n", path->iPrev);
3433 printf("iNext=%ld\n", path->iNext);
3434 dbseg(h, path->iSeg);
3435 }
3436
3437 /* Debug glyph. */
3438 static void dbglyph(abfCtx h, long iGlyph) {
3439 Glyph *glyph = &h->glyphs.array[iGlyph];
3440 long iPath = glyph->iPath;
3441 printf("--- glyph[%ld]\n", iGlyph);
3442 if (iPath == -1)
3443 printf("no path\n");
3444 else {
3445 long iFirst = iPath;
3446 do {
3447 dbpath(h, iPath);
3448 iPath = h->paths.array[iPath].iNext;
3449 } while (iPath != iFirst);
3450 }
3451 }
3452
3453 /* Debug intersects. */
3454 static void dbisects(abfCtx h) {
3455 printf("--- isects[index]={t,p.x,p.y,iSeg,iSplit,id,flags}\n");
3456 if (h->isects.cnt == 0)
3457 printf("empty\n");
3458 else {
3459 long i;
3460 for (i = 0; i < h->isects.cnt; i++) {
3461 Intersect *isect = &h->isects.array[i];
3462 char delSeg =
3463 (h->segs.array[isect->iSeg].flags & SEG_DELETE) ? '*' : ' ';
3464 char delSplit = (isect->iSplit == -1) ? ' ' : ((h->segs.array[isect->iSplit].flags & SEG_DELETE) ? '*' : ' ');
3465 printf("[%2ld]={%-10g,%-10g,%-10g,%2ld%c,%2ld%c,%2ld,%2ld}\n", i,
3466 isect->t, isect->p.x, isect->p.y,
3467 isect->iSeg, delSeg, isect->iSplit, delSplit, isect->id, isect->flags);
3468 }
3469 }
3470 }
3471
3472 /* Debug Junctions. */
3473 static void dbjuncs(abfCtx h) {
3474 printf("--- juncs[index]={p.x,p.y,total/in/out} - {seg i/o/* => (other junc,seg), angle,score}, ...\n");
3475 if (h->juncs.cnt == 0)
3476 printf("empty\n");
3477 else {
3478 long j, i;
3479 for (j = 0; j < h->juncs.cnt; j++) {
3480 Junction *junc = &h->juncs.array[j];
3481 printf("[%2ld]={%-10g,%-10g,%-2ld,%-2d,%-2d} - ", j,
3482 junc->p.x, junc->p.y, junc->outlets.cnt, junc->inCount, junc->outCount);
3483 for (i = 0; i < junc->outlets.cnt; i++) {
3484 Outlet *outlet = &junc->outlets.array[i];
3485 char type;
3486 if (outlet->flags & OUTLET_DELETE)
3487 type = '*';
3488 else if (outlet->flags & OUTLET_OUT)
3489 type = 'o';
3490 else
3491 type = 'i';
3492 printf("%s{%ld%c => (%ld, %ld), %g, %g}", ((i == 0) ? "" : ", "),
3493 outlet->seg, type, outlet->otherJunc, outlet->otherSeg, outlet->angle, outlet->score);
3494 }
3495 printf("\n");
3496 }
3497 }
3498 }
3499
3500 /* This function just serves to suppress annoying "defined but not used"
3501 compiler messages when debugging */
3502 static void CTL_CDECL dbuse(int arg, ...) {
3503 dbuse(0, dbglyph, dbisects, dbjuncs);
3504 }
3505
3506 #endif /* ABF_DEBUG */