1
2#include "Scanline.h"
3
4#include <algorithm>
5#include "arithmetics.hpp"
6
7namespace msdfgen {
8
9static int compareIntersections(const void *a, const void *b) {
10 return sign(reinterpret_cast<const Scanline::Intersection *>(a)->x-reinterpret_cast<const Scanline::Intersection *>(b)->x);
11}
12
13bool interpretFillRule(int intersections, FillRule fillRule) {
14 switch (fillRule) {
15 case FILL_NONZERO:
16 return intersections != 0;
17 case FILL_ODD:
18 return intersections&1;
19 case FILL_POSITIVE:
20 return intersections > 0;
21 case FILL_NEGATIVE:
22 return intersections < 0;
23 }
24 return false;
25}
26
27double Scanline::overlap(const Scanline &a, const Scanline &b, double xFrom, double xTo, FillRule fillRule) {
28 double total = 0;
29 bool aInside = false, bInside = false;
30 int ai = 0, bi = 0;
31 double ax = !a.intersections.empty() ? a.intersections[ai].x : xTo;
32 double bx = !b.intersections.empty() ? b.intersections[bi].x : xTo;
33 while (ax < xFrom || bx < xFrom) {
34 double xNext = min(ax, bx);
35 if (ax == xNext && ai < (int) a.intersections.size()) {
36 aInside = interpretFillRule(a.intersections[ai].direction, fillRule);
37 ax = ++ai < (int) a.intersections.size() ? a.intersections[ai].x : xTo;
38 }
39 if (bx == xNext && bi < (int) b.intersections.size()) {
40 bInside = interpretFillRule(b.intersections[bi].direction, fillRule);
41 bx = ++bi < (int) b.intersections.size() ? b.intersections[bi].x : xTo;
42 }
43 }
44 double x = xFrom;
45 while (ax < xTo || bx < xTo) {
46 double xNext = min(ax, bx);
47 if (aInside == bInside)
48 total += xNext-x;
49 if (ax == xNext && ai < (int) a.intersections.size()) {
50 aInside = interpretFillRule(a.intersections[ai].direction, fillRule);
51 ax = ++ai < (int) a.intersections.size() ? a.intersections[ai].x : xTo;
52 }
53 if (bx == xNext && bi < (int) b.intersections.size()) {
54 bInside = interpretFillRule(b.intersections[bi].direction, fillRule);
55 bx = ++bi < (int) b.intersections.size() ? b.intersections[bi].x : xTo;
56 }
57 x = xNext;
58 }
59 if (aInside == bInside)
60 total += xTo-x;
61 return total;
62}
63
64Scanline::Scanline() : lastIndex(0) { }
65
66void Scanline::preprocess() {
67 lastIndex = 0;
68 if (!intersections.empty()) {
69 qsort(&intersections[0], intersections.size(), sizeof(Intersection), compareIntersections);
70 int totalDirection = 0;
71 for (std::vector<Intersection>::iterator intersection = intersections.begin(); intersection != intersections.end(); ++intersection) {
72 totalDirection += intersection->direction;
73 intersection->direction = totalDirection;
74 }
75 }
76}
77
78void Scanline::setIntersections(const std::vector<Intersection> &intersections) {
79 this->intersections = intersections;
80 preprocess();
81}
82
83#ifdef MSDFGEN_USE_CPP11
84void Scanline::setIntersections(std::vector<Intersection> &&intersections) {
85 this->intersections = (std::vector<Intersection> &&) intersections;
86 preprocess();
87}
88#endif
89
90int Scanline::moveTo(double x) const {
91 if (intersections.empty())
92 return -1;
93 int index = lastIndex;
94 if (x < intersections[index].x) {
95 do {
96 if (index == 0) {
97 lastIndex = 0;
98 return -1;
99 }
100 --index;
101 } while (x < intersections[index].x);
102 } else {
103 while (index < (int) intersections.size()-1 && x >= intersections[index+1].x)
104 ++index;
105 }
106 lastIndex = index;
107 return index;
108}
109
110int Scanline::countIntersections(double x) const {
111 return moveTo(x)+1;
112}
113
114int Scanline::sumIntersections(double x) const {
115 int index = moveTo(x);
116 if (index >= 0)
117 return intersections[index].direction;
118 return 0;
119}
120
121bool Scanline::filled(double x, FillRule fillRule) const {
122 return interpretFillRule(sumIntersections(x), fillRule);
123}
124
125}
126