-
-
Notifications
You must be signed in to change notification settings - Fork 412
/
Shape.cpp
200 lines (180 loc) · 8.56 KB
/
Shape.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include "Shape.h"
#include <cstdlib>
#include "arithmetics.hpp"
#define DECONVERGE_OVERSHOOT 1.11111111111111111 // moves control points slightly more than necessary to account for floating-point errors
namespace msdfgen {
Shape::Shape() : inverseYAxis(false) { }
void Shape::addContour(const Contour &contour) {
contours.push_back(contour);
}
#ifdef MSDFGEN_USE_CPP11
void Shape::addContour(Contour &&contour) {
contours.push_back((Contour &&) contour);
}
#endif
Contour &Shape::addContour() {
contours.resize(contours.size()+1);
return contours.back();
}
bool Shape::validate() const {
for (std::vector<Contour>::const_iterator contour = contours.begin(); contour != contours.end(); ++contour) {
if (!contour->edges.empty()) {
Point2 corner = contour->edges.back()->point(1);
for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) {
if (!*edge)
return false;
if ((*edge)->point(0) != corner)
return false;
corner = (*edge)->point(1);
}
}
}
return true;
}
static void deconvergeEdge(EdgeHolder &edgeHolder, int param, Vector2 vector) {
switch (edgeHolder->type()) {
case (int) QuadraticSegment::EDGE_TYPE:
edgeHolder = static_cast<const QuadraticSegment *>(&*edgeHolder)->convertToCubic();
// fallthrough
case (int) CubicSegment::EDGE_TYPE:
{
Point2 *p = static_cast<CubicSegment *>(&*edgeHolder)->p;
switch (param) {
case 0:
p[1] += (p[1]-p[0]).length()*vector;
break;
case 1:
p[2] += (p[2]-p[3]).length()*vector;
break;
}
}
}
}
void Shape::normalize() {
for (std::vector<Contour>::iterator contour = contours.begin(); contour != contours.end(); ++contour) {
if (contour->edges.size() == 1) {
EdgeSegment *parts[3] = { };
contour->edges[0]->splitInThirds(parts[0], parts[1], parts[2]);
contour->edges.clear();
contour->edges.push_back(EdgeHolder(parts[0]));
contour->edges.push_back(EdgeHolder(parts[1]));
contour->edges.push_back(EdgeHolder(parts[2]));
} else {
// Push apart convergent edge segments
EdgeHolder *prevEdge = &contour->edges.back();
for (std::vector<EdgeHolder>::iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) {
Vector2 prevDir = (*prevEdge)->direction(1).normalize();
Vector2 curDir = (*edge)->direction(0).normalize();
if (dotProduct(prevDir, curDir) < MSDFGEN_CORNER_DOT_EPSILON-1) {
double factor = DECONVERGE_OVERSHOOT*sqrt(1-(MSDFGEN_CORNER_DOT_EPSILON-1)*(MSDFGEN_CORNER_DOT_EPSILON-1))/(MSDFGEN_CORNER_DOT_EPSILON-1);
Vector2 axis = factor*(curDir-prevDir).normalize();
// Determine curve ordering using third-order derivative (t = 0) of crossProduct((*prevEdge)->point(1-t)-p0, (*edge)->point(t)-p0) where p0 is the corner (*edge)->point(0)
if (crossProduct((*prevEdge)->directionChange(1), (*edge)->direction(0))+crossProduct((*edge)->directionChange(0), (*prevEdge)->direction(1)) < 0)
axis = -axis;
deconvergeEdge(*prevEdge, 1, axis.getOrthogonal(true));
deconvergeEdge(*edge, 0, axis.getOrthogonal(false));
}
prevEdge = &*edge;
}
}
}
}
void Shape::bound(double &l, double &b, double &r, double &t) const {
for (std::vector<Contour>::const_iterator contour = contours.begin(); contour != contours.end(); ++contour)
contour->bound(l, b, r, t);
}
void Shape::boundMiters(double &l, double &b, double &r, double &t, double border, double miterLimit, int polarity) const {
for (std::vector<Contour>::const_iterator contour = contours.begin(); contour != contours.end(); ++contour)
contour->boundMiters(l, b, r, t, border, miterLimit, polarity);
}
Shape::Bounds Shape::getBounds(double border, double miterLimit, int polarity) const {
static const double LARGE_VALUE = 1e240;
Shape::Bounds bounds = { +LARGE_VALUE, +LARGE_VALUE, -LARGE_VALUE, -LARGE_VALUE };
bound(bounds.l, bounds.b, bounds.r, bounds.t);
if (border > 0) {
bounds.l -= border, bounds.b -= border;
bounds.r += border, bounds.t += border;
if (miterLimit > 0)
boundMiters(bounds.l, bounds.b, bounds.r, bounds.t, border, miterLimit, polarity);
}
return bounds;
}
void Shape::scanline(Scanline &line, double y) const {
std::vector<Scanline::Intersection> intersections;
double x[3];
int dy[3];
for (std::vector<Contour>::const_iterator contour = contours.begin(); contour != contours.end(); ++contour) {
for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge) {
int n = (*edge)->scanlineIntersections(x, dy, y);
for (int i = 0; i < n; ++i) {
Scanline::Intersection intersection = { x[i], dy[i] };
intersections.push_back(intersection);
}
}
}
#ifdef MSDFGEN_USE_CPP11
line.setIntersections((std::vector<Scanline::Intersection> &&) intersections);
#else
line.setIntersections(intersections);
#endif
}
int Shape::edgeCount() const {
int total = 0;
for (std::vector<Contour>::const_iterator contour = contours.begin(); contour != contours.end(); ++contour)
total += (int) contour->edges.size();
return total;
}
void Shape::orientContours() {
struct Intersection {
double x;
int direction;
int contourIndex;
static int compare(const void *a, const void *b) {
return sign(reinterpret_cast<const Intersection *>(a)->x-reinterpret_cast<const Intersection *>(b)->x);
}
};
const double ratio = .5*(sqrt(5)-1); // an irrational number to minimize chance of intersecting a corner or other point of interest
std::vector<int> orientations(contours.size());
std::vector<Intersection> intersections;
for (int i = 0; i < (int) contours.size(); ++i) {
if (!orientations[i] && !contours[i].edges.empty()) {
// Find an Y that crosses the contour
double y0 = contours[i].edges.front()->point(0).y;
double y1 = y0;
for (std::vector<EdgeHolder>::const_iterator edge = contours[i].edges.begin(); edge != contours[i].edges.end() && y0 == y1; ++edge)
y1 = (*edge)->point(1).y;
for (std::vector<EdgeHolder>::const_iterator edge = contours[i].edges.begin(); edge != contours[i].edges.end() && y0 == y1; ++edge)
y1 = (*edge)->point(ratio).y; // in case all endpoints are in a horizontal line
double y = mix(y0, y1, ratio);
// Scanline through whole shape at Y
double x[3];
int dy[3];
for (int j = 0; j < (int) contours.size(); ++j) {
for (std::vector<EdgeHolder>::const_iterator edge = contours[j].edges.begin(); edge != contours[j].edges.end(); ++edge) {
int n = (*edge)->scanlineIntersections(x, dy, y);
for (int k = 0; k < n; ++k) {
Intersection intersection = { x[k], dy[k], j };
intersections.push_back(intersection);
}
}
}
if (!intersections.empty()) {
qsort(&intersections[0], intersections.size(), sizeof(Intersection), &Intersection::compare);
// Disqualify multiple intersections
for (int j = 1; j < (int) intersections.size(); ++j)
if (intersections[j].x == intersections[j-1].x)
intersections[j].direction = intersections[j-1].direction = 0;
// Inspect scanline and deduce orientations of intersected contours
for (int j = 0; j < (int) intersections.size(); ++j)
if (intersections[j].direction)
orientations[intersections[j].contourIndex] += 2*((j&1)^(intersections[j].direction > 0))-1;
intersections.clear();
}
}
}
// Reverse contours that have the opposite orientation
for (int i = 0; i < (int) contours.size(); ++i)
if (orientations[i] < 0)
contours[i].reverse();
}
}