1 | // [Blend2D] |
2 | // 2D Vector Graphics Powered by a JIT Compiler. |
3 | // |
4 | // [License] |
5 | // Zlib - See LICENSE.md file in the package. |
6 | |
7 | #include "./blapi-build_p.h" |
8 | #include "./bltables_p.h" |
9 | #include "./blgeometry_p.h" |
10 | #include "./blmath_p.h" |
11 | #include "./blmatrix_p.h" |
12 | #include "./blpath_p.h" |
13 | #include "./blpathstroke_p.h" |
14 | |
15 | // ============================================================================ |
16 | // [Constants] |
17 | // ============================================================================ |
18 | |
19 | // Default minimum miter-join length that always bypasses any other join-type. |
20 | // The reason behind this is to prevent emitting very small line segments in |
21 | // case that normals of joining segments are almost equal. |
22 | static constexpr double BL_STROKE_MITER_MINIMUM = 1e-10; |
23 | static constexpr double BL_STROKE_MITER_MINIMUM_SQ = blSquare(BL_STROKE_MITER_MINIMUM); |
24 | |
25 | // Minimum length for a line/curve the stroker will accept. If the segment is |
26 | // smaller than this it would be skipped. |
27 | static constexpr double BL_STROKE_LENGHT_EPSILON = 1e-10; |
28 | static constexpr double BL_STROKE_LENGTH_EPSILON_SQ = blSquare(BL_STROKE_LENGHT_EPSILON); |
29 | |
30 | static constexpr double BL_STROKE_COLLINEARITY_EPSILON = 1e-10; |
31 | static constexpr double BL_STROKE_COLLINEARITY_EPSILON_SQ = blSquare(BL_STROKE_COLLINEARITY_EPSILON); |
32 | |
33 | static constexpr double BL_STROKE_CUSP_T_THRESHOLD = 1e-10; |
34 | static constexpr double BL_STROKE_DEGENERATE_FLATNESS = 1e-6; |
35 | |
36 | // Minimum vertices that would be required for any join + additional line. |
37 | // |
38 | // Calculated from: |
39 | // JOIN: |
40 | // bevel: 1 vertex |
41 | // miter: 3 vertices |
42 | // round: 7 vertices (2 cubics at most) |
43 | // ADDITIONAL: |
44 | // end-point: 1 vertex |
45 | // line-to : 1 vertex |
46 | static constexpr size_t BL_STROKE_MIN_JOIN_VERTICES = 9; |
47 | |
48 | struct BLStrokeCapVertexCountGen { |
49 | static constexpr uint8_t value(size_t cap) noexcept { |
50 | return cap == BL_STROKE_CAP_SQUARE ? 3 : |
51 | cap == BL_STROKE_CAP_ROUND ? 6 : |
52 | cap == BL_STROKE_CAP_ROUND_REV ? 8 : |
53 | cap == BL_STROKE_CAP_TRIANGLE ? 2 : |
54 | cap == BL_STROKE_CAP_TRIANGLE_REV ? 4 : |
55 | cap == BL_STROKE_CAP_BUTT ? 1 : 1; // Default if not known. |
56 | } |
57 | }; |
58 | |
59 | static const auto blStrokeCapVertexCountTable = |
60 | blLookupTable<uint8_t, BL_STROKE_CAP_COUNT, BLStrokeCapVertexCountGen>(); |
61 | |
62 | // ============================================================================ |
63 | // [BLPathStroker - Utilities] |
64 | // ============================================================================ |
65 | |
66 | static BL_INLINE uint32_t blSanityStrokeCap(uint32_t cap) noexcept { |
67 | return cap < BL_STROKE_CAP_COUNT ? cap : BL_STROKE_CAP_BUTT; |
68 | } |
69 | |
70 | static BL_INLINE bool blIsMiterJoinCategory(uint32_t joinType) noexcept { |
71 | return joinType == BL_STROKE_JOIN_MITER_CLIP || |
72 | joinType == BL_STROKE_JOIN_MITER_BEVEL || |
73 | joinType == BL_STROKE_JOIN_MITER_ROUND ; |
74 | } |
75 | |
76 | static BL_INLINE uint32_t blMiterJoinToSimpleJoin(uint32_t joinType) { |
77 | if (joinType == BL_STROKE_JOIN_MITER_BEVEL) |
78 | return BL_STROKE_JOIN_BEVEL; |
79 | else if (joinType == BL_STROKE_JOIN_MITER_ROUND) |
80 | return BL_STROKE_JOIN_ROUND; |
81 | else |
82 | return joinType; |
83 | } |
84 | |
85 | static BL_INLINE bool blTestInnerJoinIntersecion(const BLPoint& a0, const BLPoint& a1, const BLPoint& b0, const BLPoint& b1, const BLPoint& join) noexcept { |
86 | BLPoint min = blMax(blMin(a0, a1), blMin(b0, b1)); |
87 | BLPoint max = blMin(blMax(a0, a1), blMax(b0, b1)); |
88 | |
89 | return (join.x >= min.x) & (join.y >= min.y) & |
90 | (join.x <= max.x) & (join.y <= max.y) ; |
91 | } |
92 | |
93 | // TODO: ??? |
94 | template<typename T> |
95 | BL_INLINE T signBySide(const T& in, uint32_t side) noexcept { |
96 | return side ? in : -in; |
97 | } |
98 | |
99 | // ============================================================================ |
100 | // BLPathStroker - Implementation] |
101 | // ============================================================================ |
102 | |
103 | class BLPathStroker { |
104 | public: |
105 | enum Flags : uint32_t { |
106 | kFlagIsOpen = 0x01, |
107 | kFlagIsClosed = 0x02 |
108 | }; |
109 | |
110 | enum Side : uint32_t { |
111 | kSideA = 0, |
112 | kSideB = 1 |
113 | }; |
114 | |
115 | // Stroke input. |
116 | BLPathIterator _iter; |
117 | |
118 | // Stroke options. |
119 | const BLStrokeOptions& _options; |
120 | const BLApproximationOptions& _approx; |
121 | |
122 | double _d; // Distance (StrokeWidth / 2). |
123 | double _d2; // Distance multiplied by 2. |
124 | double _miterLimit; // Miter limit possibly clamped to a safe range. |
125 | double _miterLimitSq; // Miter limit squared. |
126 | uint32_t _joinType; // Simplified join type. |
127 | |
128 | // Stroke output. |
129 | BLPath* _aPath; // Output path A (contains offsetted figure and possible end cap). |
130 | BLPath* _bPath; // Output path B (contains offsetted figure that has to be reversed). |
131 | BLPath* _cPath; // Output path C (contains possible start cap). |
132 | |
133 | BLPathAppender _aOut; // Appender of `_aPath`. |
134 | BLPathAppender _bOut; // Appender of `_bPath`. |
135 | size_t _aInitialSize; // Initial size of `_aPath`. |
136 | |
137 | // Global state. |
138 | BLPoint _p0; // Current point. |
139 | BLPoint _n0; // Unit normal of `_p0`. |
140 | BLPoint _pInitial; // Initial point (MoveTo). |
141 | BLPoint _nInitial; // Unit normal of `_pInitial`. |
142 | uint32_t _flags; // Work flags. |
143 | |
144 | BL_INLINE BLPathStroker(const BLPathView& input, const BLStrokeOptions& options, const BLApproximationOptions& approx, BLPath* a, BLPath* b, BLPath* c) noexcept |
145 | : _iter(input), |
146 | _options(options), |
147 | _approx(approx), |
148 | _d(options.width * 0.5), |
149 | _d2(options.width), |
150 | _joinType(options.join), |
151 | _aPath(a), |
152 | _bPath(b), |
153 | _cPath(c), |
154 | _aOut(), |
155 | _bOut(), |
156 | _aInitialSize(0) { |
157 | |
158 | // Initialize miter calculation options. What we do here is to change |
159 | // `_joinType` to a value that would be easier for us to use during |
160 | // joining. We always honor `_miterLimitSq` even when the `_joinType` |
161 | // is not miter to prevent emitting very small line segments next to |
162 | // next other, which saves vertices and also prevents border cases in |
163 | // additional processing. |
164 | if (blIsMiterJoinCategory(_joinType)) { |
165 | // Simplify miter-join type to non-miter join, if possible. |
166 | _joinType = blMiterJoinToSimpleJoin(_joinType); |
167 | |
168 | // Final miter limit is `0.5 * width * miterLimit`. |
169 | _miterLimit = _d * options.miterLimit; |
170 | _miterLimitSq = blSquare(_miterLimit); |
171 | } |
172 | else { |
173 | _miterLimit = BL_STROKE_MITER_MINIMUM; |
174 | _miterLimitSq = BL_STROKE_MITER_MINIMUM_SQ; |
175 | } |
176 | } |
177 | |
178 | BL_INLINE bool isOpen() const noexcept { return (_flags & kFlagIsOpen) != 0; } |
179 | BL_INLINE bool isClosed() const noexcept { return (_flags & kFlagIsClosed) != 0; } |
180 | |
181 | BL_INLINE BLResult stroke(BLPathStrokeSinkFunc sink, void* closure) noexcept { |
182 | size_t estimatedSize = _iter.remainingForward() * 2u; |
183 | BL_PROPAGATE(_aPath->reserve(_aPath->size() + estimatedSize)); |
184 | |
185 | while (!_iter.atEnd()) { |
186 | // Start of the figure. |
187 | if (BL_UNLIKELY(_iter.cmd[0] != BL_PATH_CMD_MOVE)) { |
188 | return blTraceError(BL_ERROR_INVALID_GEOMETRY); |
189 | } |
190 | |
191 | _aInitialSize = _aPath->size(); |
192 | BL_PROPAGATE(_aOut.begin(_aPath, BL_MODIFY_OP_APPEND_GROW, _iter.remainingForward())); |
193 | BL_PROPAGATE(_bOut.begin(_bPath, BL_MODIFY_OP_ASSIGN_GROW, 48)); |
194 | |
195 | BLPoint polyPts[4]; |
196 | size_t polySize; |
197 | |
198 | _p0 = *_iter.vtx; |
199 | _pInitial = _p0; |
200 | _flags = 0; |
201 | |
202 | // Content of the figure. |
203 | _iter++; |
204 | while (!_iter.atEnd()) { |
205 | BL_PROPAGATE(_aOut.ensure(_aPath, BL_STROKE_MIN_JOIN_VERTICES)); |
206 | BL_PROPAGATE(_bOut.ensure(_bPath, BL_STROKE_MIN_JOIN_VERTICES)); |
207 | |
208 | uint8_t cmd = _iter.cmd[0]; // Next command. |
209 | BLPoint p1 = _iter.vtx[0]; // Next line-to or control point. |
210 | BLPoint v1; // Vector of `p1 - _p0`. |
211 | BLPoint n1; // Unit normal of `v1`. |
212 | |
213 | if (cmd == BL_PATH_CMD_ON) { |
214 | // Line command, collinear curve converted to line or close of the figure. |
215 | _iter++; |
216 | LineTo: |
217 | v1 = p1 - _p0; |
218 | if (blLengthSq(v1) < BL_STROKE_LENGTH_EPSILON_SQ) |
219 | continue; |
220 | |
221 | n1 = blNormal(blUnitVector(v1)); |
222 | if (!isOpen()) |
223 | BL_PROPAGATE(openLineTo(p1, n1)); |
224 | else |
225 | BL_PROPAGATE(joinLineTo(p1, n1)); |
226 | continue; |
227 | |
228 | // This is again to minimize inline expansion of `smoothPolyTo()`. |
229 | SmoothPolyTo: |
230 | BL_PROPAGATE(smoothPolyTo(polyPts, polySize)); |
231 | continue; |
232 | } |
233 | else if (cmd == BL_PATH_CMD_QUAD) { |
234 | // Quadratic curve segment. |
235 | _iter += 2; |
236 | if (BL_UNLIKELY(_iter.afterEnd())) |
237 | return BL_ERROR_INVALID_GEOMETRY; |
238 | |
239 | const BLPoint* quad = _iter.vtx - 3; |
240 | BLPoint p2 = quad[2]; |
241 | BLPoint v2 = p2 - p1; |
242 | |
243 | v1 = p1 - _p0; |
244 | n1 = blNormal(blUnitVector(v1)); |
245 | |
246 | double cm = blCrossProduct(v2, v1); |
247 | if (blAbs(cm) <= BL_STROKE_COLLINEARITY_EPSILON) { |
248 | // All points are [almost] collinear (degenerate case). |
249 | double dot = blDotProduct(-v1, v2); |
250 | |
251 | // Check if control point lies outside of the start/end points. |
252 | if (dot > 0.0) { |
253 | // Rotate all points to x-axis. |
254 | double r1 = blDotProduct(p1 - _p0, v1); |
255 | double r2 = blDotProduct(p2 - _p0, v1); |
256 | |
257 | // Parameter of the cusp if it's within (0, 1). |
258 | double t = r1 / (2.0 * r1 - r2); |
259 | if (t > 0.0 && t < 1.0) { |
260 | polyPts[0] = blGetQuadValueAt(quad, t); |
261 | polyPts[1] = p2; |
262 | polySize = 2; |
263 | goto SmoothPolyTo; |
264 | } |
265 | } |
266 | |
267 | // Collinear without cusp => straight line. |
268 | p1 = p2; |
269 | goto LineTo; |
270 | } |
271 | |
272 | // Very small curve segment => straight line. |
273 | if (blLengthSq(v1) < BL_STROKE_LENGTH_EPSILON_SQ || blLengthSq(v2) < BL_STROKE_LENGTH_EPSILON_SQ) { |
274 | p1 = p2; |
275 | goto LineTo; |
276 | } |
277 | |
278 | if (!isOpen()) |
279 | BL_PROPAGATE(openCurve(n1)); |
280 | else |
281 | BL_PROPAGATE(joinCurve(n1)); |
282 | |
283 | BL_PROPAGATE(offsetQuad(_iter.vtx - 3)); |
284 | } |
285 | else if (cmd == BL_PATH_CMD_CUBIC) { |
286 | // Cubic curve segment. |
287 | _iter += 3; |
288 | if (BL_UNLIKELY(_iter.afterEnd())) |
289 | return BL_ERROR_INVALID_GEOMETRY; |
290 | |
291 | BLPoint p[7]; |
292 | |
293 | int cusp = 0; |
294 | double tCusp = 0; |
295 | |
296 | p[0] = _p0; |
297 | p[1] = _iter.vtx[-3]; |
298 | p[2] = _iter.vtx[-2]; |
299 | p[3] = _iter.vtx[-1]; |
300 | |
301 | // Check if the curve is flat enough to be potentially degenerate. |
302 | if (blIsCubicFlat(p, BL_STROKE_DEGENERATE_FLATNESS)) { |
303 | double dot1 = blDotProduct(p[0] - p[1], p[3] - p[1]); |
304 | double dot2 = blDotProduct(p[0] - p[2], p[3] - p[2]); |
305 | |
306 | if (!(dot1 < 0.0) || !(dot2 < 0.0)) { |
307 | // Rotate all points to x-axis. |
308 | const BLPoint r = blGetCubicStartTangent(p); |
309 | |
310 | double r1 = blDotProduct(p[1] - p[0], r); |
311 | double r2 = blDotProduct(p[2] - p[0], r); |
312 | double r3 = blDotProduct(p[3] - p[0], r); |
313 | |
314 | double a = 1.0 / (3.0 * r1 - 3.0 * r2 + r3); |
315 | double b = 2.0 * r1 - r2; |
316 | double s = blSqrt(r2 * (r2 - r1) - r1 * (r3 - r1)); |
317 | |
318 | // Parameters of the cusps. |
319 | double t1 = a * (b - s); |
320 | double t2 = a * (b + s); |
321 | |
322 | // Offset the first and second cusps (if they exist). |
323 | polySize = 0; |
324 | if (t1 > BL_STROKE_CUSP_T_THRESHOLD && t1 < 1.0 - BL_STROKE_CUSP_T_THRESHOLD) |
325 | polyPts[polySize++] = blGetCubicValueAt(p, t1); |
326 | |
327 | if (t2 > BL_STROKE_CUSP_T_THRESHOLD && t2 < 1.0 - BL_STROKE_CUSP_T_THRESHOLD) |
328 | polyPts[polySize++] = blGetCubicValueAt(p, t2); |
329 | |
330 | if (polySize == 0) { |
331 | p1 = p[3]; |
332 | goto LineTo; |
333 | } |
334 | |
335 | polyPts[polySize++] = p[3]; |
336 | goto SmoothPolyTo; |
337 | } |
338 | else { |
339 | p1 = p[3]; |
340 | goto LineTo; |
341 | } |
342 | } |
343 | else { |
344 | double tl; |
345 | blGetCubicInflectionParameter(p, tCusp, tl); |
346 | |
347 | if (tl == 0.0 && tCusp > 0.0 && tCusp < 1.0) { |
348 | blSplitCubic(p, p, p + 3); |
349 | cusp = 1; |
350 | } |
351 | } |
352 | |
353 | for (;;) { |
354 | v1 = p[1] - _p0; |
355 | if (blIsZero(v1)) |
356 | v1 = p[2] - _p0; |
357 | n1 = blNormal(blUnitVector(v1)); |
358 | |
359 | if (!isOpen()) |
360 | BL_PROPAGATE(openCurve(n1)); |
361 | else if (cusp >= 0) |
362 | BL_PROPAGATE(joinCurve(n1)); |
363 | else |
364 | BL_PROPAGATE(joinCusp(n1)); |
365 | |
366 | BL_PROPAGATE(offsetCubic(p)); |
367 | if (cusp <= 0) |
368 | break; |
369 | |
370 | // Second part of the cubic after the cusp. We assign `-1` to `cusp` |
371 | // so we can call `joinCusp()` later. This is a special join that we |
372 | // need in this case. |
373 | BL_PROPAGATE(_aOut.ensure(_aPath, BL_STROKE_MIN_JOIN_VERTICES)); |
374 | BL_PROPAGATE(_bOut.ensure(_bPath, BL_STROKE_MIN_JOIN_VERTICES)); |
375 | |
376 | cusp = -1; |
377 | p[0] = p[3]; |
378 | p[1] = p[4]; |
379 | p[2] = p[5]; |
380 | p[3] = p[6]; |
381 | } |
382 | } |
383 | else { |
384 | // Either invalid command or close of the figure. If the figure is |
385 | // already closed it means that we have already jumped to `LineTo` |
386 | // and we should terminate now. Otherwise we just encountered close |
387 | // or something else which is not part of the current figure. |
388 | if (isClosed()) |
389 | break; |
390 | |
391 | if (cmd != BL_PATH_CMD_CLOSE) |
392 | break; |
393 | |
394 | // The figure is closed. We just jump to `LineTo` to minimize inlining |
395 | // expansion and mark the figure as closed. Next time we terminate on |
396 | // `isClosed()` condition above. |
397 | _flags |= kFlagIsClosed; |
398 | p1 = _pInitial; |
399 | goto LineTo; |
400 | } |
401 | } |
402 | |
403 | // Don't emit anything if the figure has no points (and thus no direction). |
404 | _iter += size_t(isClosed()); |
405 | if (!isOpen()) |
406 | continue; |
407 | |
408 | if (isClosed()) { |
409 | // The figure is closed => the end result is two closed figures without |
410 | // caps. In this case only paths A and B have a content, path C will be |
411 | // empty and should be thus ignored by the sink. |
412 | |
413 | // Allocate space for the end join and close command. |
414 | BL_PROPAGATE(_aOut.ensure(_aPath, BL_STROKE_MIN_JOIN_VERTICES + 1)); |
415 | BL_PROPAGATE(_bOut.ensure(_bPath, BL_STROKE_MIN_JOIN_VERTICES + 1)); |
416 | |
417 | BL_PROPAGATE(joinEndPoint(_nInitial)); |
418 | _aOut.close(); |
419 | _bOut.close(); |
420 | _cPath->clear(); |
421 | } |
422 | else { |
423 | // The figure is open => the end result is a single figure with caps. |
424 | // In this case the paths contain the following: |
425 | // A - Offset of the figure and end cap. |
426 | // B - Offset of the figure that MUST BE reversed. |
427 | // C - Start cap (not reversed). |
428 | uint32_t startCap = blSanityStrokeCap(_options.startCap); |
429 | uint32_t endCap = blSanityStrokeCap(_options.endCap); |
430 | |
431 | BL_PROPAGATE(_aOut.ensure(_aPath, blStrokeCapVertexCountTable[endCap])); |
432 | BL_PROPAGATE(addCap(_aOut, _p0, _bOut.vtx[-1], endCap)); |
433 | |
434 | BLPathAppender cOut; |
435 | BL_PROPAGATE(cOut.begin(_cPath, BL_MODIFY_OP_ASSIGN_GROW, blStrokeCapVertexCountTable[startCap] + 1)); |
436 | cOut.moveTo(_bPath->vertexData()[0]); |
437 | BL_PROPAGATE(addCap(cOut, _pInitial, _aPath->vertexData()[_aInitialSize], startCap)); |
438 | cOut.done(_cPath); |
439 | } |
440 | |
441 | _aOut.done(_aPath); |
442 | _bOut.done(_bPath); |
443 | |
444 | // Call the path to the provided sink with resulting paths. |
445 | BL_PROPAGATE(sink(_aPath, _bPath, _cPath, closure)); |
446 | } |
447 | |
448 | return BL_SUCCESS; |
449 | } |
450 | |
451 | // Opens a new figure with a line segment starting from the current point |
452 | // and ending at `p1`. The `n1` is a normal calculated from a unit vector |
453 | // of `p1 - _p0`. |
454 | // |
455 | // This function can only be called after we have at least two vertices that |
456 | // form the line. These vertices cannot be a single point as that would mean |
457 | // that we cannot calculate unit vector and then normal for the offset. This |
458 | // must be handled before calling `openLineTo()`. |
459 | // |
460 | // NOTE: Path cannot be open when calling this function. |
461 | BL_INLINE BLResult openLineTo(const BLPoint& p1, const BLPoint& n1) noexcept { |
462 | BL_ASSERT(!isOpen()); |
463 | BLPoint w = n1 * _d; |
464 | |
465 | _aOut.moveTo(_p0 + w); |
466 | _bOut.moveTo(_p0 - w); |
467 | |
468 | _p0 = p1; |
469 | _n0 = n1; |
470 | _nInitial = n1; |
471 | |
472 | _aOut.lineTo(_p0 + w); |
473 | _bOut.lineTo(_p0 - w); |
474 | |
475 | _flags |= kFlagIsOpen; |
476 | return BL_SUCCESS; |
477 | } |
478 | |
479 | // Joins line-to segment described by `p1` point and `n1` normal. |
480 | BL_INLINE BLResult joinLineTo(const BLPoint& p1, const BLPoint& n1) noexcept { |
481 | BLPoint w1 = n1 * _d; |
482 | BLPoint a1 = p1 + w1; |
483 | BLPoint b1 = p1 - w1; |
484 | |
485 | if (_n0 == n1) { |
486 | // Collinear case - patch the previous point(s) if they connect lines. |
487 | _aOut.back(_aOut.cmd[-2] <= BL_PATH_CMD_ON); |
488 | _bOut.back(_bOut.cmd[-2] <= BL_PATH_CMD_ON); |
489 | } |
490 | else { |
491 | BLPoint m = _n0 + n1; |
492 | BLPoint k = (_d2 * m) / blLengthSq(m); |
493 | |
494 | double dir = blCrossProduct(_n0, n1); |
495 | size_t miterFlag = 0; |
496 | |
497 | if (dir < 0) { |
498 | // A is outer, B is inner. |
499 | outerJoin(_aOut, kSideA, n1, w1, k, miterFlag); |
500 | _aOut.back(miterFlag); |
501 | innerJoinLineTo(_bOut, _p0 - w1, b1, _p0 - k); |
502 | } |
503 | else { |
504 | // B is outer, A is inner. |
505 | outerJoin(_bOut, kSideB, n1, -w1, -k, miterFlag); |
506 | _bOut.back(miterFlag); |
507 | innerJoinLineTo(_aOut, _p0 + w1, a1, _p0 + k); |
508 | } |
509 | } |
510 | |
511 | _aOut.lineTo(a1); |
512 | _bOut.lineTo(b1); |
513 | |
514 | _p0 = p1; |
515 | _n0 = n1; |
516 | return BL_SUCCESS; |
517 | } |
518 | |
519 | // Opens a new figure at the current point `_p0`. The first vertex (MOVE) is |
520 | // calculated by offsetting `_p0` by the given unit normal `n0`. |
521 | // |
522 | // NOTE: Path cannot be open when calling this function. |
523 | BL_INLINE BLResult openCurve(const BLPoint& n0) noexcept { |
524 | BL_ASSERT(!isOpen()); |
525 | BLPoint w = n0 * _d; |
526 | |
527 | _aOut.moveTo(_p0 + w); |
528 | _bOut.moveTo(_p0 - w); |
529 | |
530 | _n0 = n0; |
531 | _nInitial = n0; |
532 | |
533 | _flags |= kFlagIsOpen; |
534 | return BL_SUCCESS; |
535 | } |
536 | |
537 | // Joins curve-to segment. |
538 | BL_INLINE BLResult joinCurve(const BLPoint& n1) noexcept { |
539 | BLPoint w1 = n1 * _d; |
540 | |
541 | if (_n0 == n1) { |
542 | // Collinear case - do nothing. |
543 | } |
544 | else { |
545 | BLPoint m = _n0 + n1; |
546 | BLPoint k = (_d2 * m) / blLengthSq(m); |
547 | |
548 | double dir = blCrossProduct(_n0, n1); |
549 | size_t miterFlag; |
550 | |
551 | if (dir < 0) { |
552 | // A is outer, B is inner. |
553 | outerJoin(_aOut, kSideA, n1, w1, k, miterFlag); |
554 | innerJoinCurveTo(_bOut, _p0 - w1); |
555 | } |
556 | else { |
557 | // B is outer, A is inner. |
558 | outerJoin(_bOut, kSideB, n1, -w1, -k, miterFlag); |
559 | innerJoinCurveTo(_aOut, _p0 + w1); |
560 | } |
561 | |
562 | _n0 = n1; |
563 | } |
564 | |
565 | return BL_SUCCESS; |
566 | } |
567 | |
568 | BL_INLINE BLResult joinCusp(const BLPoint& n1) noexcept { |
569 | BLPoint w1 = n1 * _d; |
570 | |
571 | double dir = blCrossProduct(_n0, n1); |
572 | if (dir < 0) { |
573 | // A is outer, B is inner. |
574 | dullRoundJoin(_aOut, kSideA, n1, w1); |
575 | _bOut.lineTo(_p0 - w1); |
576 | } |
577 | else { |
578 | // B is outer, A is inner. |
579 | dullRoundJoin(_bOut, kSideB, n1, -w1); |
580 | _aOut.lineTo(_p0 + w1); |
581 | } |
582 | |
583 | _n0 = n1; |
584 | return BL_SUCCESS; |
585 | } |
586 | |
587 | BL_INLINE BLResult smoothPolyTo(const BLPoint* poly, size_t count) noexcept { |
588 | BL_ASSERT(count >= 2); |
589 | |
590 | BLPoint p1 = poly[0]; |
591 | BLPoint v1 = p1 - _p0; |
592 | BLPoint n1 = blNormal(blUnitVector(v1)); |
593 | |
594 | if (!isOpen()) |
595 | BL_PROPAGATE(openLineTo(p1, n1)); |
596 | else |
597 | BL_PROPAGATE(joinLineTo(p1, n1)); |
598 | |
599 | // We have already ensured vertices for `openLineTo()` and `joinLineTo()`, |
600 | // however, we need more vertices for consecutive joins and line segments. |
601 | BL_PROPAGATE(_aOut.ensure(_aPath, (count - 1) * BL_STROKE_MIN_JOIN_VERTICES)); |
602 | BL_PROPAGATE(_bOut.ensure(_bPath, (count - 1) * BL_STROKE_MIN_JOIN_VERTICES)); |
603 | |
604 | for (size_t i = 1; i < count; i++) { |
605 | p1 = poly[i]; |
606 | v1 = p1 - _p0; |
607 | n1 = blNormal(blUnitVector(v1)); |
608 | |
609 | BL_PROPAGATE(joinCusp(n1)); |
610 | BLPoint w1 = n1 * _d; |
611 | |
612 | _aOut.lineTo(p1 + w1); |
613 | _bOut.lineTo(p1 - w1); |
614 | |
615 | _p0 = p1; |
616 | _n0 = n1; |
617 | } |
618 | |
619 | return BL_SUCCESS; |
620 | } |
621 | |
622 | // Joins end point that is only applied to closed figures. |
623 | BL_INLINE BLResult joinEndPoint(const BLPoint& n1) noexcept { |
624 | BLPoint w1 = n1 * _d; |
625 | |
626 | if (_n0 == n1) { |
627 | // Collinear case - patch the previous point(s) if they connect lines. |
628 | _aOut.back(_aOut.cmd[-2] <= BL_PATH_CMD_ON); |
629 | _bOut.back(_bOut.cmd[-2] <= BL_PATH_CMD_ON); |
630 | return BL_SUCCESS; |
631 | } |
632 | |
633 | BLPoint m = _n0 + n1; |
634 | BLPoint k = (_d2 * m) / blLengthSq(m); |
635 | |
636 | BLPoint* aStartVtx = _aPath->impl->vertexData + _aInitialSize; |
637 | uint8_t* aStartCmd = _aPath->impl->commandData + _aInitialSize; |
638 | |
639 | BLPoint* bStartVtx = _bPath->impl->vertexData; |
640 | uint8_t* bStartCmd = _bPath->impl->commandData; |
641 | |
642 | double dir = blCrossProduct(_n0, n1); |
643 | size_t miterFlag = 0; |
644 | |
645 | if (dir < 0) { |
646 | // A is outer, B is inner. |
647 | outerJoin(_aOut, kSideA, n1, w1, k, miterFlag); |
648 | |
649 | // Shift the start point to be at the miter intersection and remove the |
650 | // Line from the intersection to the start of A path if miter was applied. |
651 | if (miterFlag) { |
652 | if (aStartCmd[1] == BL_PATH_CMD_ON) { |
653 | _aOut.back(); |
654 | aStartVtx[0] = _aOut.vtx[-1]; |
655 | _aOut.back(_aOut.cmd[-2] <= BL_PATH_CMD_ON); |
656 | } |
657 | } |
658 | |
659 | if (bStartCmd[1] <= BL_PATH_CMD_ON) |
660 | innerJoinEndPoint(_bOut, bStartVtx[0], bStartVtx[1], _p0 - k); |
661 | } |
662 | else { |
663 | // B is outer, A is inner. |
664 | outerJoin(_bOut, kSideB, n1, -w1, -k, miterFlag); |
665 | |
666 | // Shift the start point to be at the miter intersection and remove the |
667 | // Line from the intersection to the start of B path if miter was applied. |
668 | if (miterFlag) { |
669 | if (bStartCmd[1] == BL_PATH_CMD_ON) { |
670 | _bOut.back(); |
671 | bStartVtx[0] = _bOut.vtx[-1]; |
672 | _bOut.back(_bOut.cmd[-2] <= BL_PATH_CMD_ON); |
673 | } |
674 | } |
675 | |
676 | if (aStartCmd[1] == BL_PATH_CMD_ON) |
677 | innerJoinEndPoint(_aOut, aStartVtx[0], aStartVtx[1], _p0 + k); |
678 | } |
679 | |
680 | return BL_SUCCESS; |
681 | } |
682 | |
683 | BL_INLINE void innerJoinCurveTo(BLPathAppender& out, const BLPoint& p1) noexcept { |
684 | out.lineTo(_p0); |
685 | out.lineTo(p1); |
686 | } |
687 | |
688 | BL_INLINE void innerJoinLineTo(BLPathAppender& out, const BLPoint& lineP0, const BLPoint& lineP1, const BLPoint& innerPt) noexcept { |
689 | if (out.cmd[-2] <= BL_PATH_CMD_ON && blTestInnerJoinIntersecion(out.vtx[-2], out.vtx[-1], lineP0, lineP1, innerPt)) { |
690 | out.vtx[-1] = innerPt; |
691 | } |
692 | else { |
693 | out.lineTo(_p0); |
694 | out.lineTo(lineP0); |
695 | } |
696 | } |
697 | |
698 | BL_INLINE void innerJoinEndPoint(BLPathAppender& out, BLPoint& lineP0, const BLPoint& lineP1, const BLPoint& innerPt) noexcept { |
699 | if (out.cmd[-2] <= BL_PATH_CMD_ON && blTestInnerJoinIntersecion(out.vtx[-2], out.vtx[-1], lineP0, lineP1, innerPt)) { |
700 | lineP0 = innerPt; |
701 | out.back(1); |
702 | } |
703 | else { |
704 | out.lineTo(_p0); |
705 | out.lineTo(lineP0); |
706 | } |
707 | } |
708 | |
709 | // Calculates outer join to `pb`. |
710 | BL_INLINE BLResult outerJoin(BLPathAppender& out, uint32_t side, const BLPoint& n1, const BLPoint& w1, const BLPoint& k, size_t& miterFlag) noexcept { |
711 | BLPoint pb = _p0 + w1; |
712 | |
713 | if (blLengthSq(k) <= _miterLimitSq) { |
714 | // Miter condition is met. |
715 | out.back(out.cmd[-2] <= BL_PATH_CMD_ON); |
716 | out.lineTo(_p0 + k); |
717 | out.lineTo(pb); |
718 | |
719 | miterFlag = 1; |
720 | return BL_SUCCESS; |
721 | } |
722 | |
723 | if (_joinType == BL_STROKE_JOIN_MITER_CLIP) { |
724 | double b2 = blAbs(blCrossProduct(k, _n0)); |
725 | |
726 | // Avoid degenerate cases and NaN. |
727 | if (b2 > 0) |
728 | b2 = b2 * _miterLimit / blLength(k); |
729 | else |
730 | b2 = _miterLimit; |
731 | |
732 | out.back(out.cmd[-2] <= BL_PATH_CMD_ON); |
733 | if (side == kSideA) { |
734 | out.lineTo(_p0 + _d * _n0 - b2 * blNormal(_n0)); |
735 | out.lineTo(_p0 + _d * n1 + b2 * blNormal(n1)); |
736 | } |
737 | else { |
738 | out.lineTo(_p0 - _d * _n0 - b2 * blNormal(_n0)); |
739 | out.lineTo(_p0 - _d * n1 + b2 * blNormal(n1)); |
740 | } |
741 | |
742 | miterFlag = 1; |
743 | out.lineTo(pb); |
744 | return BL_SUCCESS; |
745 | } |
746 | |
747 | if (_joinType == BL_STROKE_JOIN_ROUND) { |
748 | BLPoint pa = out.vtx[-1]; |
749 | if (blDotProduct(_p0 - pa, _p0 - pb) < 0.0) { |
750 | // Dull angle. |
751 | BLPoint n2 = blNormal(blUnitVector(pb - pa)); |
752 | BLPoint m = _n0 + n2; |
753 | BLPoint k = _d2 * m / blLengthSq(m); |
754 | BLPoint q = _d * n2; |
755 | |
756 | BLPoint pc1 = side == kSideA ? _p0 + k : _p0 - k; |
757 | BLPoint pp1 = side == kSideA ? _p0 + q : _p0 - q; |
758 | BLPoint pc2 = blLerp(pc1, pp1, 2.0); |
759 | |
760 | auto arcTo = [&](const BLPoint& p0, const BLPoint& pa, const BLPoint& pb, const BLPoint& intersection) noexcept { |
761 | BLPoint pm = (pa + pb) * 0.5; |
762 | |
763 | double w = blSqrt(blLength(p0 - pm) / blLength(p0 - intersection)); |
764 | double a = 4 * w / (3.0 * (1.0 + w)); |
765 | |
766 | BLPoint c0 = pa + a * (intersection - pa); |
767 | BLPoint c1 = pb + a * (intersection - pb); |
768 | |
769 | out.cubicTo(c0, c1, pb); |
770 | }; |
771 | |
772 | arcTo(_p0, pa, pp1, pc1); |
773 | arcTo(_p0, pp1, pb, pc2); |
774 | } |
775 | else { |
776 | // Acute angle. |
777 | BLPoint pm = blLerp(pa, pb); |
778 | BLPoint pi = _p0 + k; |
779 | |
780 | double w = blSqrt(blLength(_p0 - pm) / blLength(_p0 - pi)); |
781 | double a = 4.0 * w / (3.0 * (1.0 + w)); |
782 | |
783 | BLPoint c0 = pa + a * (pi - pa); |
784 | BLPoint c1 = pb + a * (pi - pb); |
785 | |
786 | out.cubicTo(c0, c1, pb); |
787 | } |
788 | return BL_SUCCESS; |
789 | } |
790 | |
791 | // Bevel or unknown `_joinType`. |
792 | out.lineTo(pb); |
793 | return BL_SUCCESS; |
794 | } |
795 | |
796 | // Calculates round join to `pb` (dull angle), only used by offseting cusps. |
797 | BL_INLINE BLResult dullRoundJoin(BLPathAppender& out, uint32_t side, const BLPoint& n1, const BLPoint& w1) noexcept { |
798 | BLPoint pa = out.vtx[-1]; |
799 | BLPoint pb = _p0 + w1; |
800 | BLPoint n2 = blNormal(blUnitVector(pb - pa)); |
801 | BLPoint m = _n0 + n2; |
802 | BLPoint k = _d2 * m / blLengthSq(m); |
803 | BLPoint q = _d * n2; |
804 | |
805 | BLPoint pc1 = side == kSideA ? _p0 + k : _p0 - k; |
806 | BLPoint pp1 = side == kSideA ? _p0 + q : _p0 - q; |
807 | BLPoint pc2 = blLerp(pc1, pp1, 2.0); |
808 | |
809 | auto arcTo = [&](const BLPoint& p0, const BLPoint& pa, const BLPoint& pb, const BLPoint& intersection) noexcept { |
810 | BLPoint pm = (pa + pb) * 0.5; |
811 | |
812 | double w = blSqrt(blLength(p0 - pm) / blLength(p0 - intersection)); |
813 | double a = 4.0 * w / (3.0 * (1.0 + w)); |
814 | |
815 | BLPoint c0 = pa + a * (intersection - pa); |
816 | BLPoint c1 = pb + a * (intersection - pb); |
817 | |
818 | out.cubicTo(c0, c1, pb); |
819 | }; |
820 | |
821 | arcTo(_p0, pa, pp1, pc1); |
822 | arcTo(_p0, pp1, pb, pc2); |
823 | return BL_SUCCESS; |
824 | } |
825 | |
826 | BL_INLINE BLResult offsetQuad(const BLPoint bez[3]) noexcept { |
827 | double ts[3]; |
828 | size_t tn = blGetQuadOffsetCuspTs(bez, _d, ts); |
829 | ts[tn++] = 1.0; |
830 | |
831 | BLQuadCurveTsIter iter(bez, ts, tn); |
832 | double m = _approx.offsetParameter; |
833 | |
834 | do { |
835 | for (;;) { |
836 | BL_PROPAGATE(_aOut.ensure(_aPath, 2)); |
837 | BL_PROPAGATE(_bOut.ensure(_bPath, 2)); |
838 | |
839 | double t = blGetQuadParameterAtAngle(iter.part, m); |
840 | if (t <= blEpsilon<double>() || t > 1.0 - blEpsilon<double>()) |
841 | t = 1.0; |
842 | |
843 | BLPoint part[3]; |
844 | blSplitQuad(iter.part, part, iter.part, t); |
845 | offsetQuadSimple(part[0], part[1], part[2]); |
846 | |
847 | if (t == 1.0) |
848 | break; |
849 | } |
850 | } while (iter.next()); |
851 | |
852 | return BL_SUCCESS; |
853 | } |
854 | |
855 | BL_INLINE void offsetQuadSimple(const BLPoint& p0, const BLPoint& p1, const BLPoint& p2) noexcept { |
856 | if (p0 == p2) |
857 | return; |
858 | |
859 | BLPoint v0 = p1 - p0; |
860 | BLPoint v1 = p2 - p1; |
861 | |
862 | BLPoint m0 = blNormal(blUnitVector(p0 != p1 ? v0 : v1)); |
863 | BLPoint m2 = blNormal(blUnitVector(p1 != p2 ? v1 : v0)); |
864 | |
865 | _p0 = p2; |
866 | _n0 = m2; |
867 | |
868 | BLPoint m = m0 + m2; |
869 | BLPoint k1 = _d2 * m / blLengthSq(m); |
870 | BLPoint k2 = _d * m2; |
871 | |
872 | _aOut.quadTo(p1 + k1, p2 + k2); |
873 | _bOut.quadTo(p1 - k1, p2 - k2); |
874 | } |
875 | |
876 | BL_INLINE BLResult offsetCubic(const BLPoint bez[4]) noexcept { |
877 | return blApproximateCubicWithQuads(bez, _approx.simplifyTolerance, [&](BLPoint quad[3]) noexcept -> BLResult { |
878 | return offsetQuad(quad); |
879 | }); |
880 | } |
881 | |
882 | BL_INLINE BLResult addCap(BLPathAppender& out, BLPoint pivot, BLPoint p1, uint32_t capType) noexcept { |
883 | BLPoint p0 = out.vtx[-1]; |
884 | BLPoint q = blNormal(p1 - p0) * 0.5; |
885 | |
886 | switch (capType) { |
887 | case BL_STROKE_CAP_BUTT: |
888 | default: { |
889 | out.lineTo(p1); |
890 | break; |
891 | } |
892 | |
893 | case BL_STROKE_CAP_SQUARE: { |
894 | out.lineTo(p0 + q); |
895 | out.lineTo(p1 + q); |
896 | out.lineTo(p1); |
897 | break; |
898 | } |
899 | |
900 | case BL_STROKE_CAP_ROUND: { |
901 | out.arcQuadrantTo(p0 + q, pivot + q); |
902 | out.arcQuadrantTo(p1 + q, p1); |
903 | break; |
904 | } |
905 | |
906 | case BL_STROKE_CAP_ROUND_REV: { |
907 | out.lineTo(p0 + q); |
908 | out.arcQuadrantTo(p0, pivot); |
909 | out.arcQuadrantTo(p1, p1 + q); |
910 | out.lineTo(p1); |
911 | break; |
912 | } |
913 | |
914 | case BL_STROKE_CAP_TRIANGLE: { |
915 | out.lineTo(pivot + q); |
916 | out.lineTo(p1); |
917 | break; |
918 | } |
919 | |
920 | case BL_STROKE_CAP_TRIANGLE_REV: { |
921 | out.lineTo(p0 + q); |
922 | out.lineTo(pivot); |
923 | out.lineTo(p1 + q); |
924 | out.lineTo(p1); |
925 | break; |
926 | } |
927 | } |
928 | |
929 | return BL_SUCCESS; |
930 | } |
931 | }; |
932 | |
933 | // ============================================================================ |
934 | // [BLPathStroker - Interface] |
935 | // ============================================================================ |
936 | |
937 | BLResult blPathStrokeInternal( |
938 | const BLPathView& input, |
939 | const BLStrokeOptions& options, |
940 | const BLApproximationOptions& approx, |
941 | BLPath* a, |
942 | BLPath* b, |
943 | BLPath* c, |
944 | BLPathStrokeSinkFunc sink, void* closure) noexcept { |
945 | |
946 | return BLPathStroker(input, options, approx, a, b, c).stroke(sink, closure); |
947 | } |
948 | |