1
2#include "edge-coloring.h"
3
4#include <cstdlib>
5#include <cmath>
6#include <cstring>
7#include <cfloat>
8#include <queue>
9#include "arithmetics.hpp"
10
11namespace msdfgen {
12
13static bool isCorner(const Vector2 &aDir, const Vector2 &bDir, double crossThreshold) {
14 return dotProduct(aDir, bDir) <= 0 || fabs(crossProduct(aDir, bDir)) > crossThreshold;
15}
16
17static double estimateEdgeLength(const EdgeSegment *edge) {
18 double len = 0;
19 Point2 prev = edge->point(0);
20 for (int i = 1; i <= MSDFGEN_EDGE_LENGTH_PRECISION; ++i) {
21 Point2 cur = edge->point(1./MSDFGEN_EDGE_LENGTH_PRECISION*i);
22 len += (cur-prev).length();
23 prev = cur;
24 }
25 return len;
26}
27
28static void switchColor(EdgeColor &color, unsigned long long &seed, EdgeColor banned = BLACK) {
29 EdgeColor combined = EdgeColor(color&banned);
30 if (combined == RED || combined == GREEN || combined == BLUE) {
31 color = EdgeColor(combined^WHITE);
32 return;
33 }
34 if (color == BLACK || color == WHITE) {
35 static const EdgeColor start[3] = { CYAN, MAGENTA, YELLOW };
36 color = start[seed%3];
37 seed /= 3;
38 return;
39 }
40 int shifted = color<<(1+(seed&1));
41 color = EdgeColor((shifted|shifted>>3)&WHITE);
42 seed >>= 1;
43}
44
45void edgeColoringSimple(Shape &shape, double angleThreshold, unsigned long long seed) {
46 double crossThreshold = sin(angleThreshold);
47 std::vector<int> corners;
48 for (std::vector<Contour>::iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) {
49 // Identify corners
50 corners.clear();
51 if (!contour->edges.empty()) {
52 Vector2 prevDirection = contour->edges.back()->direction(1);
53 int index = 0;
54 for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge, ++index) {
55 if (isCorner(prevDirection.normalize(), (*edge)->direction(0).normalize(), crossThreshold))
56 corners.push_back(index);
57 prevDirection = (*edge)->direction(1);
58 }
59 }
60
61 // Smooth contour
62 if (corners.empty())
63 for (std::vector<EdgeHolder>::iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge)
64 (*edge)->color = WHITE;
65 // "Teardrop" case
66 else if (corners.size() == 1) {
67 EdgeColor colors[3] = { WHITE, WHITE };
68 switchColor(colors[0], seed);
69 switchColor(colors[2] = colors[0], seed);
70 int corner = corners[0];
71 if (contour->edges.size() >= 3) {
72 int m = (int) contour->edges.size();
73 for (int i = 0; i < m; ++i)
74 contour->edges[(corner+i)%m]->color = (colors+1)[int(3+2.875*i/(m-1)-1.4375+.5)-3];
75 } else if (contour->edges.size() >= 1) {
76 // Less than three edge segments for three colors => edges must be split
77 EdgeSegment *parts[7] = { };
78 contour->edges[0]->splitInThirds(parts[0+3*corner], parts[1+3*corner], parts[2+3*corner]);
79 if (contour->edges.size() >= 2) {
80 contour->edges[1]->splitInThirds(parts[3-3*corner], parts[4-3*corner], parts[5-3*corner]);
81 parts[0]->color = parts[1]->color = colors[0];
82 parts[2]->color = parts[3]->color = colors[1];
83 parts[4]->color = parts[5]->color = colors[2];
84 } else {
85 parts[0]->color = colors[0];
86 parts[1]->color = colors[1];
87 parts[2]->color = colors[2];
88 }
89 contour->edges.clear();
90 for (int i = 0; parts[i]; ++i)
91 contour->edges.push_back(EdgeHolder(parts[i]));
92 }
93 }
94 // Multiple corners
95 else {
96 int cornerCount = (int) corners.size();
97 int spline = 0;
98 int start = corners[0];
99 int m = (int) contour->edges.size();
100 EdgeColor color = WHITE;
101 switchColor(color, seed);
102 EdgeColor initialColor = color;
103 for (int i = 0; i < m; ++i) {
104 int index = (start+i)%m;
105 if (spline+1 < cornerCount && corners[spline+1] == index) {
106 ++spline;
107 switchColor(color, seed, EdgeColor((spline == cornerCount-1)*initialColor));
108 }
109 contour->edges[index]->color = color;
110 }
111 }
112 }
113}
114
115struct EdgeColoringInkTrapCorner {
116 int index;
117 double prevEdgeLengthEstimate;
118 bool minor;
119 EdgeColor color;
120};
121
122void edgeColoringInkTrap(Shape &shape, double angleThreshold, unsigned long long seed) {
123 typedef EdgeColoringInkTrapCorner Corner;
124 double crossThreshold = sin(angleThreshold);
125 std::vector<Corner> corners;
126 for (std::vector<Contour>::iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour) {
127 // Identify corners
128 double splineLength = 0;
129 corners.clear();
130 if (!contour->edges.empty()) {
131 Vector2 prevDirection = contour->edges.back()->direction(1);
132 int index = 0;
133 for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge, ++index) {
134 if (isCorner(prevDirection.normalize(), (*edge)->direction(0).normalize(), crossThreshold)) {
135 Corner corner = { index, splineLength };
136 corners.push_back(corner);
137 splineLength = 0;
138 }
139 splineLength += estimateEdgeLength(*edge);
140 prevDirection = (*edge)->direction(1);
141 }
142 }
143
144 // Smooth contour
145 if (corners.empty())
146 for (std::vector<EdgeHolder>::iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge)
147 (*edge)->color = WHITE;
148 // "Teardrop" case
149 else if (corners.size() == 1) {
150 EdgeColor colors[3] = { WHITE, WHITE };
151 switchColor(colors[0], seed);
152 switchColor(colors[2] = colors[0], seed);
153 int corner = corners[0].index;
154 if (contour->edges.size() >= 3) {
155 int m = (int) contour->edges.size();
156 for (int i = 0; i < m; ++i)
157 contour->edges[(corner+i)%m]->color = (colors+1)[int(3+2.875*i/(m-1)-1.4375+.5)-3];
158 } else if (contour->edges.size() >= 1) {
159 // Less than three edge segments for three colors => edges must be split
160 EdgeSegment *parts[7] = { };
161 contour->edges[0]->splitInThirds(parts[0+3*corner], parts[1+3*corner], parts[2+3*corner]);
162 if (contour->edges.size() >= 2) {
163 contour->edges[1]->splitInThirds(parts[3-3*corner], parts[4-3*corner], parts[5-3*corner]);
164 parts[0]->color = parts[1]->color = colors[0];
165 parts[2]->color = parts[3]->color = colors[1];
166 parts[4]->color = parts[5]->color = colors[2];
167 } else {
168 parts[0]->color = colors[0];
169 parts[1]->color = colors[1];
170 parts[2]->color = colors[2];
171 }
172 contour->edges.clear();
173 for (int i = 0; parts[i]; ++i)
174 contour->edges.push_back(EdgeHolder(parts[i]));
175 }
176 }
177 // Multiple corners
178 else {
179 int cornerCount = (int) corners.size();
180 int majorCornerCount = cornerCount;
181 if (cornerCount > 3) {
182 corners.begin()->prevEdgeLengthEstimate += splineLength;
183 for (int i = 0; i < cornerCount; ++i) {
184 if (
185 corners[i].prevEdgeLengthEstimate > corners[(i+1)%cornerCount].prevEdgeLengthEstimate &&
186 corners[(i+1)%cornerCount].prevEdgeLengthEstimate < corners[(i+2)%cornerCount].prevEdgeLengthEstimate
187 ) {
188 corners[i].minor = true;
189 --majorCornerCount;
190 }
191 }
192 }
193 EdgeColor color = WHITE;
194 EdgeColor initialColor = BLACK;
195 for (int i = 0; i < cornerCount; ++i) {
196 if (!corners[i].minor) {
197 --majorCornerCount;
198 switchColor(color, seed, EdgeColor(!majorCornerCount*initialColor));
199 corners[i].color = color;
200 if (!initialColor)
201 initialColor = color;
202 }
203 }
204 for (int i = 0; i < cornerCount; ++i) {
205 if (corners[i].minor) {
206 EdgeColor nextColor = corners[(i+1)%cornerCount].color;
207 corners[i].color = EdgeColor((color&nextColor)^WHITE);
208 } else
209 color = corners[i].color;
210 }
211 int spline = 0;
212 int start = corners[0].index;
213 color = corners[0].color;
214 int m = (int) contour->edges.size();
215 for (int i = 0; i < m; ++i) {
216 int index = (start+i)%m;
217 if (spline+1 < cornerCount && corners[spline+1].index == index)
218 color = corners[++spline].color;
219 contour->edges[index]->color = color;
220 }
221 }
222 }
223}
224
225// EDGE COLORING BY DISTANCE - EXPERIMENTAL IMPLEMENTATION - WORK IN PROGRESS
226#define MAX_RECOLOR_STEPS 16
227#define EDGE_DISTANCE_PRECISION 16
228
229static double edgeToEdgeDistance(const EdgeSegment &a, const EdgeSegment &b, int precision) {
230 if (a.point(0) == b.point(0) || a.point(0) == b.point(1) || a.point(1) == b.point(0) || a.point(1) == b.point(1))
231 return 0;
232 double iFac = 1./precision;
233 double minDistance = (b.point(0)-a.point(0)).length();
234 for (int i = 0; i <= precision; ++i) {
235 double t = iFac*i;
236 double d = fabs(a.signedDistance(b.point(t), t).distance);
237 minDistance = min(minDistance, d);
238 }
239 for (int i = 0; i <= precision; ++i) {
240 double t = iFac*i;
241 double d = fabs(b.signedDistance(a.point(t), t).distance);
242 minDistance = min(minDistance, d);
243 }
244 return minDistance;
245}
246
247static double splineToSplineDistance(EdgeSegment * const *edgeSegments, int aStart, int aEnd, int bStart, int bEnd, int precision) {
248 double minDistance = DBL_MAX;
249 for (int ai = aStart; ai < aEnd; ++ai)
250 for (int bi = bStart; bi < bEnd && minDistance; ++bi) {
251 double d = edgeToEdgeDistance(*edgeSegments[ai], *edgeSegments[bi], precision);
252 minDistance = min(minDistance, d);
253 }
254 return minDistance;
255}
256
257static void colorSecondDegreeGraph(int *coloring, const int * const *edgeMatrix, int vertexCount, unsigned long long seed) {
258 for (int i = 0; i < vertexCount; ++i) {
259 int possibleColors = 7;
260 for (int j = 0; j < i; ++j) {
261 if (edgeMatrix[i][j])
262 possibleColors &= ~(1<<coloring[j]);
263 }
264 int color = 0;
265 switch (possibleColors) {
266 case 1:
267 color = 0;
268 break;
269 case 2:
270 color = 1;
271 break;
272 case 3:
273 color = (int) seed&1;
274 seed >>= 1;
275 break;
276 case 4:
277 color = 2;
278 break;
279 case 5:
280 color = ((int) seed+1&1)<<1;
281 seed >>= 1;
282 break;
283 case 6:
284 color = ((int) seed&1)+1;
285 seed >>= 1;
286 break;
287 case 7:
288 color = int((seed+i)%3);
289 seed /= 3;
290 break;
291 }
292 coloring[i] = color;
293 }
294}
295
296static int vertexPossibleColors(const int *coloring, const int *edgeVector, int vertexCount) {
297 int usedColors = 0;
298 for (int i = 0; i < vertexCount; ++i)
299 if (edgeVector[i])
300 usedColors |= 1<<coloring[i];
301 return 7&~usedColors;
302}
303
304static void uncolorSameNeighbors(std::queue<int> &uncolored, int *coloring, const int * const *edgeMatrix, int vertex, int vertexCount) {
305 for (int i = vertex+1; i < vertexCount; ++i) {
306 if (edgeMatrix[vertex][i] && coloring[i] == coloring[vertex]) {
307 coloring[i] = -1;
308 uncolored.push(i);
309 }
310 }
311 for (int i = 0; i < vertex; ++i) {
312 if (edgeMatrix[vertex][i] && coloring[i] == coloring[vertex]) {
313 coloring[i] = -1;
314 uncolored.push(i);
315 }
316 }
317}
318
319static bool tryAddEdge(int *coloring, int * const *edgeMatrix, int vertexCount, int vertexA, int vertexB, int *coloringBuffer) {
320 static const int FIRST_POSSIBLE_COLOR[8] = { -1, 0, 1, 0, 2, 2, 1, 0 };
321 edgeMatrix[vertexA][vertexB] = 1;
322 edgeMatrix[vertexB][vertexA] = 1;
323 if (coloring[vertexA] != coloring[vertexB])
324 return true;
325 int bPossibleColors = vertexPossibleColors(coloring, edgeMatrix[vertexB], vertexCount);
326 if (bPossibleColors) {
327 coloring[vertexB] = FIRST_POSSIBLE_COLOR[bPossibleColors];
328 return true;
329 }
330 memcpy(coloringBuffer, coloring, sizeof(int)*vertexCount);
331 std::queue<int> uncolored;
332 {
333 int *coloring = coloringBuffer;
334 coloring[vertexB] = FIRST_POSSIBLE_COLOR[7&~(1<<coloring[vertexA])];
335 uncolorSameNeighbors(uncolored, coloring, edgeMatrix, vertexB, vertexCount);
336 int step = 0;
337 while (!uncolored.empty() && step < MAX_RECOLOR_STEPS) {
338 int i = uncolored.front();
339 uncolored.pop();
340 int possibleColors = vertexPossibleColors(coloring, edgeMatrix[i], vertexCount);
341 if (possibleColors) {
342 coloring[i] = FIRST_POSSIBLE_COLOR[possibleColors];
343 continue;
344 }
345 do {
346 coloring[i] = step++%3;
347 } while (edgeMatrix[i][vertexA] && coloring[i] == coloring[vertexA]);
348 uncolorSameNeighbors(uncolored, coloring, edgeMatrix, i, vertexCount);
349 }
350 }
351 if (!uncolored.empty()) {
352 edgeMatrix[vertexA][vertexB] = 0;
353 edgeMatrix[vertexB][vertexA] = 0;
354 return false;
355 }
356 memcpy(coloring, coloringBuffer, sizeof(int)*vertexCount);
357 return true;
358}
359
360static int cmpDoublePtr(const void *a, const void *b) {
361 return sign(**reinterpret_cast<const double * const *>(a)-**reinterpret_cast<const double * const *>(b));
362}
363
364void edgeColoringByDistance(Shape &shape, double angleThreshold, unsigned long long seed) {
365
366 std::vector<EdgeSegment *> edgeSegments;
367 std::vector<int> splineStarts;
368
369 double crossThreshold = sin(angleThreshold);
370 std::vector<int> corners;
371 for (std::vector<Contour>::iterator contour = shape.contours.begin(); contour != shape.contours.end(); ++contour)
372 if (!contour->edges.empty()) {
373 // Identify corners
374 corners.clear();
375 Vector2 prevDirection = contour->edges.back()->direction(1);
376 int index = 0;
377 for (std::vector<EdgeHolder>::const_iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge, ++index) {
378 if (isCorner(prevDirection.normalize(), (*edge)->direction(0).normalize(), crossThreshold))
379 corners.push_back(index);
380 prevDirection = (*edge)->direction(1);
381 }
382
383 splineStarts.push_back((int) edgeSegments.size());
384 // Smooth contour
385 if (corners.empty())
386 for (std::vector<EdgeHolder>::iterator edge = contour->edges.begin(); edge != contour->edges.end(); ++edge)
387 edgeSegments.push_back(&**edge);
388 // "Teardrop" case
389 else if (corners.size() == 1) {
390 int corner = corners[0];
391 if (contour->edges.size() >= 3) {
392 int m = (int) contour->edges.size();
393 for (int i = 0; i < m; ++i) {
394 if (i == m/2)
395 splineStarts.push_back((int) edgeSegments.size());
396 if (int(3+2.875*i/(m-1)-1.4375+.5)-3)
397 edgeSegments.push_back(&*contour->edges[(corner+i)%m]);
398 else
399 contour->edges[(corner+i)%m]->color = WHITE;
400 }
401 } else if (contour->edges.size() >= 1) {
402 // Less than three edge segments for three colors => edges must be split
403 EdgeSegment *parts[7] = { };
404 contour->edges[0]->splitInThirds(parts[0+3*corner], parts[1+3*corner], parts[2+3*corner]);
405 if (contour->edges.size() >= 2) {
406 contour->edges[1]->splitInThirds(parts[3-3*corner], parts[4-3*corner], parts[5-3*corner]);
407 edgeSegments.push_back(parts[0]);
408 edgeSegments.push_back(parts[1]);
409 parts[2]->color = parts[3]->color = WHITE;
410 splineStarts.push_back((int) edgeSegments.size());
411 edgeSegments.push_back(parts[4]);
412 edgeSegments.push_back(parts[5]);
413 } else {
414 edgeSegments.push_back(parts[0]);
415 parts[1]->color = WHITE;
416 splineStarts.push_back((int) edgeSegments.size());
417 edgeSegments.push_back(parts[2]);
418 }
419 contour->edges.clear();
420 for (int i = 0; parts[i]; ++i)
421 contour->edges.push_back(EdgeHolder(parts[i]));
422 }
423 }
424 // Multiple corners
425 else {
426 int cornerCount = (int) corners.size();
427 int spline = 0;
428 int start = corners[0];
429 int m = (int) contour->edges.size();
430 for (int i = 0; i < m; ++i) {
431 int index = (start+i)%m;
432 if (spline+1 < cornerCount && corners[spline+1] == index) {
433 splineStarts.push_back((int) edgeSegments.size());
434 ++spline;
435 }
436 edgeSegments.push_back(&*contour->edges[index]);
437 }
438 }
439 }
440 splineStarts.push_back((int) edgeSegments.size());
441
442 int segmentCount = (int) edgeSegments.size();
443 int splineCount = (int) splineStarts.size()-1;
444 if (!splineCount)
445 return;
446
447 std::vector<double> distanceMatrixStorage(splineCount*splineCount);
448 std::vector<double *> distanceMatrix(splineCount);
449 for (int i = 0; i < splineCount; ++i)
450 distanceMatrix[i] = &distanceMatrixStorage[i*splineCount];
451 const double *distanceMatrixBase = &distanceMatrixStorage[0];
452
453 for (int i = 0; i < splineCount; ++i) {
454 distanceMatrix[i][i] = -1;
455 for (int j = i+1; j < splineCount; ++j) {
456 double dist = splineToSplineDistance(&edgeSegments[0], splineStarts[i], splineStarts[i+1], splineStarts[j], splineStarts[j+1], EDGE_DISTANCE_PRECISION);
457 distanceMatrix[i][j] = dist;
458 distanceMatrix[j][i] = dist;
459 }
460 }
461
462 std::vector<const double *> graphEdgeDistances;
463 graphEdgeDistances.reserve(splineCount*(splineCount-1)/2);
464 for (int i = 0; i < splineCount; ++i)
465 for (int j = i+1; j < splineCount; ++j)
466 graphEdgeDistances.push_back(&distanceMatrix[i][j]);
467 int graphEdgeCount = (int) graphEdgeDistances.size();
468 if (!graphEdgeDistances.empty())
469 qsort(&graphEdgeDistances[0], graphEdgeDistances.size(), sizeof(const double *), &cmpDoublePtr);
470
471 std::vector<int> edgeMatrixStorage(splineCount*splineCount);
472 std::vector<int *> edgeMatrix(splineCount);
473 for (int i = 0; i < splineCount; ++i)
474 edgeMatrix[i] = &edgeMatrixStorage[i*splineCount];
475 int nextEdge = 0;
476 for (; nextEdge < graphEdgeCount && !*graphEdgeDistances[nextEdge]; ++nextEdge) {
477 int elem = (int) (graphEdgeDistances[nextEdge]-distanceMatrixBase);
478 int row = elem/splineCount;
479 int col = elem%splineCount;
480 edgeMatrix[row][col] = 1;
481 edgeMatrix[col][row] = 1;
482 }
483
484 std::vector<int> coloring(2*splineCount);
485 colorSecondDegreeGraph(&coloring[0], &edgeMatrix[0], splineCount, seed);
486 for (; nextEdge < graphEdgeCount; ++nextEdge) {
487 int elem = (int) (graphEdgeDistances[nextEdge]-distanceMatrixBase);
488 tryAddEdge(&coloring[0], &edgeMatrix[0], splineCount, elem/splineCount, elem%splineCount, &coloring[splineCount]);
489 }
490
491 const EdgeColor colors[3] = { YELLOW, CYAN, MAGENTA };
492 int spline = -1;
493 for (int i = 0; i < segmentCount; ++i) {
494 if (splineStarts[spline+1] == i)
495 ++spline;
496 edgeSegments[i]->color = colors[coloring[spline]];
497 }
498}
499
500}
501