Line data Source code
1 : /**
2 : Copyright (c) 2022 Roman Katuntsev <sbkarr@stappler.org>
3 : Copyright (c) 2023 Stappler LLC <admin@stappler.dev>
4 :
5 : Permission is hereby granted, free of charge, to any person obtaining a copy
6 : of this software and associated documentation files (the "Software"), to deal
7 : in the Software without restriction, including without limitation the rights
8 : to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 : copies of the Software, and to permit persons to whom the Software is
10 : furnished to do so, subject to the following conditions:
11 :
12 : The above copyright notice and this permission notice shall be included in
13 : all copies or substantial portions of the Software.
14 :
15 : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 : FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 : AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 : LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 : OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21 : THE SOFTWARE.
22 : **/
23 :
24 : #include "SPTess.h"
25 : #include "SPLog.h"
26 : #include "SPTessTypes.h"
27 : #include "SPTessSimd.hpp"
28 :
29 : namespace STAPPLER_VERSIONIZED stappler::geom {
30 :
31 : static constexpr VerboseFlag TessVerbose = VerboseFlag::None;
32 :
33 : struct Tesselator::Data : ObjectAllocator {
34 : // potential root face edges (connected to right non-convex angle)
35 : Vec2 _bmax, _bmin, _event;
36 :
37 : TessResult *_result = nullptr;
38 : EdgeDict* _edgeDict = nullptr;
39 : VertexPriorityQueue *_vertexQueue = nullptr;
40 :
41 : float _mathTolerance = std::numeric_limits<float>::epsilon() * 4.0f;
42 :
43 : Winding _winding = Winding::NonZero;
44 : float _antialiasValue = 0.0f;
45 : uint32_t _nvertexes = 0;
46 : uint8_t _markValue = 0;
47 :
48 : RelocateRule _relocateRule = RelocateRule::Auto;
49 :
50 : bool _dryRun = false;
51 : bool _valid = true;
52 :
53 : Vertex *_eventVertex = nullptr;
54 :
55 : memory::vector<Vertex *> _protectedVertexes;
56 : memory::vector<HalfEdge *> _protectedEdges;
57 :
58 : Data(memory::pool_t *p);
59 :
60 : void computeInterior();
61 :
62 : // Compute boundary face contour, also - split vertexes in subboundaries for antialiasing
63 : uint32_t computeBoundary();
64 :
65 : bool tessellateInterior();
66 : bool tessellateMonoRegion(HalfEdge *, uint8_t);
67 : void sweepVertex(VertexPriorityQueue &pq, EdgeDict &dict, Vertex *v);
68 : HalfEdge * processIntersect(Vertex *, const EdgeDictNode *, HalfEdge *, Vec2 &, IntersectionEvent ev);
69 : HalfEdge * processIntersect(Vertex *, const EdgeDictNode *, Vec2 &, IntersectionEvent ev);
70 :
71 : Edge *makeEdgeLoop(const Vec2 &origin);
72 :
73 : Vertex *makeVertex(HalfEdge *eOrig);
74 :
75 : HalfEdge *pushVertex(HalfEdge *e, const Vec2 &, bool clockwise = false, bool returnNew = false);
76 : HalfEdge *connectEdges(HalfEdge *eOrg, HalfEdge *eDst);
77 :
78 : Vertex *splitEdge(HalfEdge *, const Vec2 &);
79 : Vertex *splitEdge(HalfEdge *, HalfEdge *eOrg2, const Vec2 &);
80 :
81 : HalfEdge *getFirstEdge(Vertex *org) const;
82 : bool mergeVertexes(Vertex *org, Vertex *merge);
83 : HalfEdge * removeEdge(HalfEdge *);
84 :
85 : HalfEdge * removeDegenerateEdges(HalfEdge *, uint32_t *nedges, bool safeRemove);
86 : bool removeDegenerateEdges(FaceEdge *, size_t &removed);
87 :
88 : bool processEdgeOverlap(Vertex *v, HalfEdge *e1, HalfEdge *e2);
89 :
90 : bool isDegenerateTriangle(HalfEdge *);
91 :
92 : uint32_t followBoundary(FaceEdge *, HalfEdge *, uint8_t);
93 : void splitVertex(HalfEdge *first, HalfEdge *last);
94 : void displaceBoundary(FaceEdge *);
95 : };
96 :
97 257418 : Tesselator::~Tesselator() {
98 128709 : if (_data) {
99 128709 : auto pool = _data->_pool;
100 128709 : _data->~Data();
101 128468 : _data = nullptr;
102 128468 : memory::pool::destroy(pool);
103 : }
104 257162 : }
105 :
106 128520 : bool Tesselator::init(memory::pool_t *pool) {
107 128520 : auto p = memory::pool::create(pool);
108 128386 : memory::pool::context ctx(p);
109 :
110 128348 : _data = new (p) Data(p);
111 128325 : return true;
112 128329 : }
113 :
114 5693 : void Tesselator::setAntialiasValue(float value) {
115 5693 : _data->_antialiasValue = value;
116 5693 : }
117 :
118 0 : float Tesselator::getAntialiasValue() const {
119 0 : return _data->_antialiasValue;
120 : }
121 :
122 5665 : void Tesselator::setRelocateRule(RelocateRule rule) {
123 5665 : _data->_relocateRule = rule;
124 5665 : }
125 :
126 0 : Tesselator::RelocateRule Tesselator::getRelocateRule() const {
127 0 : return _data->_relocateRule;
128 : }
129 :
130 128596 : void Tesselator::setWindingRule(Winding winding) {
131 128596 : _data->_winding = winding;
132 128596 : }
133 :
134 0 : Winding Tesselator::getWindingRule() const {
135 0 : return _data->_winding;
136 : }
137 :
138 0 : void Tesselator::preallocate(uint32_t n) {
139 0 : _data->preallocateVertexes(n);
140 0 : _data->preallocateEdges(n);
141 0 : }
142 :
143 444898 : Tesselator::Cursor Tesselator::beginContour(bool clockwise) {
144 444898 : return Cursor{nullptr, nullptr, clockwise};
145 : }
146 :
147 2913501 : bool Tesselator::pushVertex(Cursor &cursor, const Vec2 &vertex) {
148 2913501 : if (!vertex.isValid()) {
149 : return false;
150 : }
151 :
152 2897376 : if (!cursor.closed) {
153 2839831 : if (cursor.count == 0) {
154 180128 : cursor.origin = vertex;
155 : }
156 :
157 : if constexpr (TessVerbose != VerboseFlag::None) {
158 : std::cout << std::setprecision(std::numeric_limits<float>::digits10 + 1)
159 : << "Push: " << vertex << "\n";
160 : }
161 :
162 2839831 : cursor.edge = _data->pushVertex(cursor.edge, vertex, cursor.isClockwise);
163 2800794 : ++ cursor.count;
164 2800794 : return true;
165 : }
166 :
167 : return false;
168 : }
169 :
170 3659750 : bool Tesselator::pushStrokeVertex(Cursor &cursor, const Vec2 &vertex, const Vec2 &offset) {
171 3659750 : if (!vertex.isValid() || !offset.isValid()) {
172 241350 : return false;
173 : }
174 :
175 3418400 : if (!cursor.closed) {
176 3347725 : if (cursor.count == 0) {
177 264950 : cursor.origin = vertex;
178 : }
179 :
180 : if constexpr (TessVerbose != VerboseFlag::None) {
181 : std::cout << std::setprecision(std::numeric_limits<float>::digits10 + 1)
182 : << "Push (stroke): " << vertex << ", " << offset << "\n";
183 : }
184 :
185 3347725 : if (!cursor.edge) {
186 264950 : cursor.root = cursor.edge = _data->pushVertex(cursor.edge, vertex + offset, cursor.isClockwise);
187 264950 : cursor.edge = _data->pushVertex(cursor.edge, vertex - offset, cursor.isClockwise);
188 : } else {
189 3082775 : _data->pushVertex(cursor.edge->getLeftLoopPrev(), vertex - offset, cursor.isClockwise);
190 3082775 : cursor.edge = _data->pushVertex(cursor.edge->getLeftLoopPrev(), vertex + offset, cursor.isClockwise, true);
191 : }
192 :
193 3347725 : ++ cursor.count;
194 3347725 : return true;
195 : }
196 : return false;
197 : }
198 :
199 5875 : bool Tesselator::pushStrokeTop(Cursor &cursor, const Vec2 &vertex) {
200 5875 : if (!vertex.isValid()) {
201 : return false;
202 : }
203 :
204 5875 : if (!cursor.closed) {
205 5875 : if (cursor.count == 0) {
206 0 : cursor.origin = vertex;
207 : }
208 :
209 : if constexpr (TessVerbose != VerboseFlag::None) {
210 : std::cout << std::setprecision(std::numeric_limits<float>::digits10 + 1)
211 : << "Push (stroke-top): " << vertex << "\n";
212 : }
213 :
214 5875 : if (!cursor.edge) {
215 0 : cursor.root = cursor.edge = _data->pushVertex(cursor.edge, vertex, cursor.isClockwise);
216 : } else {
217 5875 : cursor.edge = _data->pushVertex(cursor.edge->getLeftLoopPrev(), vertex, cursor.isClockwise, true);
218 : }
219 :
220 5875 : ++ cursor.count;
221 5875 : return true;
222 : }
223 : return false;
224 : }
225 :
226 7550 : bool Tesselator::pushStrokeBottom(Cursor &cursor, const Vec2 &vertex) {
227 7550 : if (!vertex.isValid()) {
228 : return false;
229 : }
230 :
231 7500 : if (!cursor.closed) {
232 7500 : if (cursor.count == 0) {
233 0 : cursor.origin = vertex;
234 : }
235 :
236 : if constexpr (TessVerbose != VerboseFlag::None) {
237 : std::cout << std::setprecision(std::numeric_limits<float>::digits10 + 1)
238 : << "Push (stroke-bottom): " << vertex << "\n";
239 : }
240 :
241 7500 : if (!cursor.edge) {
242 0 : cursor.root = cursor.edge = _data->pushVertex(cursor.edge, vertex, cursor.isClockwise);
243 : } else {
244 7500 : _data->pushVertex(cursor.edge->getLeftLoopPrev(), vertex, cursor.isClockwise);
245 : }
246 :
247 7500 : ++ cursor.count;
248 7500 : return true;
249 : }
250 : return false;
251 : }
252 :
253 237399 : bool Tesselator::closeContour(Cursor &cursor) {
254 237399 : if (cursor.closed) {
255 : return false;
256 : }
257 :
258 180068 : cursor.closed = true;
259 :
260 180068 : cursor.edge = _data->removeDegenerateEdges(cursor.edge, &cursor.count, true);
261 :
262 180576 : if (cursor.edge) {
263 : if constexpr (TessVerbose != VerboseFlag::None) {
264 : std::cout << "Contour:\n";
265 : cursor.edge->foreachOnFace([&] (HalfEdge &e) {
266 : std::cout << TessVerbose << "\t" << e << "\n";
267 : });
268 : }
269 179782 : _data->trimVertexes();
270 179215 : return true;
271 : } else {
272 : if constexpr (TessVerbose != VerboseFlag::None) {
273 : std::cout << "Fail to add empty contour\n";
274 : }
275 : }
276 794 : _data->trimVertexes();
277 796 : return false;
278 : }
279 :
280 259400 : bool Tesselator::closeStrokeContour(Cursor &cursor) {
281 259400 : if (cursor.closed) {
282 : return false;
283 : }
284 :
285 259400 : cursor.closed = true;
286 :
287 259400 : if (cursor.root) {
288 259400 : _data->_vertexes[cursor.root->vertex]->relocate(cursor.edge->origin);
289 259400 : _data->_vertexes[cursor.root->sym()->vertex]->relocate(cursor.edge->getLeftLoopPrev()->origin);
290 : }
291 :
292 259400 : cursor.edge = _data->removeDegenerateEdges(cursor.edge, &cursor.count, true);
293 :
294 259400 : if (cursor.edge) {
295 : if constexpr (TessVerbose != VerboseFlag::None) {
296 : std::cout << "Contour:\n";
297 : cursor.edge->foreachOnFace([&] (HalfEdge &e) {
298 : std::cout << TessVerbose << "\t" << e << "\n";
299 : });
300 : }
301 : return true;
302 : } else {
303 : if constexpr (TessVerbose != VerboseFlag::None) {
304 : std::cout << "Fail to add empty contour\n";
305 : }
306 : }
307 25 : _data->trimVertexes();
308 25 : return false;
309 : }
310 :
311 128612 : bool Tesselator::prepare(TessResult &res) {
312 128612 : _data->_result = &res;
313 128612 : _data->_vertexOffset = res.nvertexes;
314 :
315 128612 : if (_data->_relocateRule == RelocateRule::Monotonize && _data->_antialiasValue > 0.0f) {
316 225 : _data->_dryRun = true;
317 : }
318 :
319 128612 : _data->computeInterior();
320 :
321 128504 : if (_data->_antialiasValue > 0.0f) {
322 5675 : auto nBoundarySegments = _data->computeBoundary();
323 :
324 : if constexpr (TessVerbose != VerboseFlag::None) {
325 : for (auto &it : _data->_boundaries) {
326 : if (!it->_degenerate) {
327 : std::cout << "Boundary:\n";
328 : it->foreach([&] (const FaceEdge &edge) {
329 : std::cout << "\t" << edge << "\n";
330 : });
331 : }
332 : }
333 : }
334 :
335 5706 : if (_data->_relocateRule == RelocateRule::Monotonize) {
336 450 : for (auto &it : _data->_boundaries) {
337 225 : if (it->_degenerate) {
338 0 : continue;
339 : }
340 : auto e = it;
341 : do {
342 950 : _data->displaceBoundary(e);
343 950 : e = e->_next;
344 950 : } while (e != it);
345 : }
346 :
347 225 : _data->_dryRun = false;
348 :
349 1175 : for (auto &it : _data->_vertexes) {
350 950 : if (!it) {
351 0 : continue;
352 : }
353 :
354 : if constexpr (TessVerbose != VerboseFlag::None) {
355 : std::cout << "Vertex: " << *it << "\n";
356 : }
357 :
358 950 : auto e = it->_edge;
359 : do {
360 1900 : auto edge = e->getEdge();
361 1900 : SPASSERT(!edge->invalidated, "Tess: failed: edge was invalidated but still in use");
362 1900 : edge->direction = nan();
363 1900 : edge->node = nullptr;
364 1900 : e->origin = it->_origin;
365 1900 : e->_realWinding = 0;
366 1900 : e = e->_originNext;
367 1900 : } while (e != it->_edge);
368 : }
369 :
370 225 : _data->computeInterior();
371 : }
372 :
373 5706 : if (!_data->tessellateInterior()) {
374 0 : _data->_valid = false;
375 0 : _data->_result = nullptr;
376 0 : return false;
377 : }
378 :
379 5697 : res.nvertexes += _data->_exportVertexes.size() + nBoundarySegments;
380 5695 : res.nfaces += _data->_faceEdges.size() + nBoundarySegments * 2;
381 5691 : return true;
382 : } else {
383 122829 : if (!_data->tessellateInterior()) {
384 175 : _data->_valid = false;
385 175 : _data->_result = nullptr;
386 175 : return false;
387 : }
388 :
389 122737 : res.nvertexes += _data->_exportVertexes.size();
390 122703 : res.nfaces += _data->_faceEdges.size();
391 122681 : return true;
392 : }
393 : return false;
394 : }
395 :
396 128680 : bool Tesselator::write(TessResult &res) {
397 128680 : if (!_data->_valid) {
398 : return false;
399 : }
400 :
401 128505 : uint32_t triangle[3] = { 0 };
402 :
403 230886 : auto exportQuad = [&, this] (uint32_t tl, uint32_t tr, uint32_t bl, uint32_t br) {
404 230886 : triangle[0] = _data->_vertexOffset + tl;
405 116012 : triangle[1] = _data->_vertexOffset + bl;
406 116012 : triangle[2] = _data->_vertexOffset + tr;
407 :
408 116012 : res.pushTriangle(res.target, triangle);
409 :
410 114874 : triangle[0] = _data->_vertexOffset + bl;
411 114874 : triangle[1] = _data->_vertexOffset + br;
412 114874 : triangle[2] = _data->_vertexOffset + tr;
413 :
414 114874 : res.pushTriangle(res.target, triangle);
415 243587 : };
416 :
417 128505 : if (_data->_antialiasValue > 0.0f) {
418 : uint32_t tl, tr, bl, br, origin;
419 :
420 5714 : uint32_t nexports = _data->_exportVertexes.size();
421 :
422 11434 : for (auto &it : _data->_boundaries) {
423 5707 : if (it->_degenerate) {
424 0 : continue;
425 : }
426 :
427 : origin = nexports;
428 : auto e = it;
429 :
430 5707 : if (_data->_relocateRule == RelocateRule::Monotonize) {
431 : // boundaries already relocated
432 225 : e = e->_next;
433 :
434 225 : res.pushVertex(res.target, nexports + _data->_vertexOffset, e->_displaced, e->_value);
435 225 : ++ nexports;
436 :
437 : do {
438 : // e and e->next should be ready
439 725 : tl = nexports - 1;
440 : tr = nexports;
441 725 : bl = e->_vertex->_exportIdx;
442 :
443 725 : e = e->_next;
444 :
445 725 : br = e->_vertex->_exportIdx;
446 :
447 725 : res.pushVertex(res.target, nexports + _data->_vertexOffset, e->_displaced, 0.0f);
448 :
449 725 : exportQuad(tl, tr, bl, br);
450 725 : ++ nexports;
451 725 : } while (e != it);
452 :
453 : // export first edge
454 : tl = tr;
455 : tr = origin;
456 : bl = br;
457 225 : br = e->_next->_vertex->_exportIdx;
458 225 : exportQuad(tl, tr, bl, br);
459 : } else {
460 5482 : _data->displaceBoundary(e);
461 :
462 5494 : e = e->_next;
463 :
464 5494 : res.pushVertex(res.target, nexports + _data->_vertexOffset, e->_displaced, e->_value);
465 5495 : ++ nexports;
466 :
467 : do {
468 108730 : _data->displaceBoundary(e);
469 :
470 : // e and e->next should be ready
471 109778 : tl = nexports - 1;
472 : tr = nexports;
473 109778 : bl = e->_vertex->_exportIdx;
474 :
475 109778 : e = e->_next;
476 :
477 109778 : br = e->_vertex->_exportIdx;
478 :
479 109778 : res.pushVertex(res.target, nexports + _data->_vertexOffset, e->_displaced, 0.0f);
480 :
481 109594 : exportQuad(tl, tr, bl, br);
482 108732 : ++ nexports;
483 108732 : } while (e != it);
484 :
485 : // export first edge
486 : tl = tr;
487 : tr = origin;
488 : bl = br;
489 5497 : br = e->_next->_vertex->_exportIdx;
490 5497 : exportQuad(tl, tr, bl, br);
491 : }
492 : }
493 : }
494 :
495 9091480 : for (auto &it : _data->_exportVertexes) {
496 8958560 : if (it) {
497 8958560 : res.pushVertex(res.target, it->_exportIdx + _data->_vertexOffset, it->_origin, 1.0f);
498 : }
499 : }
500 :
501 128539 : auto mark = ++ _data->_markValue;
502 8845270 : for (auto &it : _data->_faceEdges) {
503 8725504 : if (it->_mark != mark && isWindingInside(_data->_winding, it->_realWinding)) {
504 8727157 : uint32_t vertex = 0;
505 :
506 8727157 : it->foreachOnFace([&, this] (HalfEdge &edge) {
507 26035040 : if (vertex < 3) {
508 : #if DEBUG
509 26035897 : if (_data->_vertexes.size() >= edge.vertex) {
510 26034578 : const auto v = _data->_vertexes[edge.vertex];
511 25996865 : if (v) {
512 25996865 : const auto qidx = v->_exportIdx;
513 25996865 : triangle[vertex] = qidx + _data->_vertexOffset;
514 : } else {
515 0 : std::cout << "Invalid vertex: " << edge.vertex << "\n";
516 0 : ::abort();
517 : }
518 : } else {
519 0 : std::cout << "Invalid vertex index: " << edge.vertex << " of " << _data->_vertexes.size() << "\n";
520 0 : ::abort();
521 : }
522 : #else
523 : triangle[vertex] = _data->_vertexes[edge.vertex]->_exportIdx + _data->_vertexOffset;
524 : #endif
525 : }
526 25996008 : edge._mark = mark;
527 25996008 : ++ vertex;
528 25996008 : });
529 :
530 8707361 : if (vertex == 3) {
531 8707182 : res.pushTriangle(res.target, triangle);
532 : /*if (skipTriangles > 0) {
533 : -- skipTriangles;
534 : } else {
535 : if (ntriangles > 0) {
536 : res.pushTriangle(res.target, triangle);
537 : -- ntriangles;
538 : } else {
539 : break;
540 : }
541 : }*/
542 : }
543 : }
544 : }
545 :
546 128467 : return true;
547 : }
548 :
549 128406 : Tesselator::Data::Data(memory::pool_t *p)
550 128406 : : ObjectAllocator(p) { }
551 :
552 128839 : void Tesselator::Data::computeInterior() {
553 128839 : _exportVertexes.clear();
554 :
555 128766 : EdgeDict dict(_pool, 8);
556 128878 : VertexPriorityQueue pq(_pool, _vertexes);
557 :
558 128958 : _edgeDict = &dict;
559 128958 : _vertexQueue = &pq;
560 :
561 : Vertex *v, *vNext;
562 8977985 : while ((v = pq.extractMin()) != nullptr) {
563 : for (;;) {
564 9125324 : vNext = pq.getMin();
565 9139623 : if (vNext == NULL || !VertEq(vNext, v, _mathTolerance)) {
566 : break;
567 : }
568 :
569 263845 : vNext = pq.extractMin();
570 263842 : mergeVertexes(v, vNext);
571 : }
572 :
573 8878064 : dict.update(v, _mathTolerance);
574 :
575 8928295 : sweepVertex(pq, dict, v);
576 : }
577 :
578 128708 : _edgeDict = nullptr;
579 128708 : _vertexQueue = nullptr;
580 128708 : }
581 :
582 5676 : uint32_t Tesselator::Data::computeBoundary() {
583 5676 : _nvertexes = _vertexes.size(); // for new vertexes handling
584 : uint32_t nsegments = 0;
585 5671 : auto mark = ++ _markValue;
586 :
587 11391 : for (auto &it : _edgesOfInterests) {
588 5672 : if (!it) {
589 0 : continue;
590 : }
591 5672 : auto e = it->getEdge();
592 5694 : if (e->left._mark != mark) {
593 5693 : if (!isWindingInside(_winding, e->left._realWinding)) {
594 3920 : nsegments += followBoundary(nullptr, &e->left, mark);
595 : } else {
596 1773 : e->left._mark = mark;
597 : }
598 : }
599 5712 : if (e->right._mark != mark) {
600 5710 : if (!isWindingInside(_winding, e->right._realWinding)) {
601 1770 : nsegments += followBoundary(nullptr, &e->right, mark);
602 : } else {
603 3940 : e->right._mark = mark;
604 : }
605 : }
606 : }
607 :
608 11422 : for (auto &it : _boundaries) {
609 5701 : size_t removed = 0;
610 5701 : if (!removeDegenerateEdges(it, removed)) {
611 0 : it->_degenerate = true;
612 0 : nsegments -= removed;
613 : }
614 : }
615 :
616 5704 : return nsegments;
617 : }
618 :
619 128548 : bool Tesselator::Data::tessellateInterior() {
620 128548 : auto mark = ++ _markValue;
621 :
622 2286915 : for (auto &it : _edgesOfInterests) {
623 2157944 : if (!it) {
624 15 : continue;
625 : }
626 2157929 : auto e = it->getEdge();
627 2158741 : if (e->left._mark != mark) {
628 966330 : if (isWindingInside(_winding, e->left._realWinding)) {
629 : if constexpr (TessVerbose != VerboseFlag::None) {
630 : uint32_t vertex = 0;
631 : std::cout << "Inside Face: \n";
632 : e->left.foreachOnFace([&](HalfEdge &edge) {
633 : std::cout << "\t" << TessVerbose << vertex ++ << "; " << edge << "\n";
634 : });
635 : }
636 :
637 883967 : if (!tessellateMonoRegion(&e->left, mark)) {
638 175 : return false;
639 : }
640 : } else {
641 82363 : e->left._mark = mark;
642 : }
643 : }
644 2158366 : if (e->right._mark != mark) {
645 1480536 : if (isWindingInside(_winding, e->right._realWinding)) {
646 : if constexpr (TessVerbose != VerboseFlag::None) {
647 : uint32_t vertex = 0;
648 : std::cout << "Inside Face: \n";
649 : e->right.foreachOnFace([&](HalfEdge &edge) {
650 : std::cout << "\t" << TessVerbose << vertex ++ << "; " << edge << "\n";
651 : });
652 : }
653 :
654 344509 : if (!tessellateMonoRegion(&e->right, mark)) {
655 : return false;
656 : }
657 : } else {
658 1136027 : e->right._mark = mark;
659 : }
660 : }
661 : }
662 128421 : return true;
663 : }
664 :
665 1228314 : bool Tesselator::Data::tessellateMonoRegion(HalfEdge *edge, uint8_t v) {
666 1228314 : if (edge->_leftNext->_leftNext == edge) {
667 : return true;
668 : }
669 :
670 1228239 : edge = removeDegenerateEdges(edge, nullptr, false);
671 1228882 : if (!edge) {
672 : return true;
673 : }
674 :
675 : HalfEdge *up = edge, *lo;
676 :
677 : /* All edges are oriented CCW around the boundary of the region.
678 : * First, find the half-edge whose origin vertex is rightmost.
679 : * Since the sweep goes from left to right, face->anEdge should
680 : * be close to the edge we want.
681 : */
682 1932729 : for (; VertLeq(up->getDstVec(), up->getOrgVec()); up = up->getLeftLoopPrev())
683 : ;
684 6471180 : for (; VertLeq(up->getOrgVec(), up->getDstVec()); up = up->getLeftLoopNext())
685 : ;
686 1228609 : lo = up->getLeftLoopPrev();
687 :
688 : if constexpr (TessVerbose == VerboseFlag::Full) {
689 : std::cout << "Start: Up: " << *up << "\n";
690 : std::cout << "Start: Lo: " << *lo << "\n";
691 : }
692 :
693 1228864 : up->_mark = v;
694 1228864 : lo->_mark = v;
695 :
696 : const Vec2 * v0, *v1, *v2;
697 :
698 10051327 : while (up->getLeftLoopNext() != lo) {
699 8805087 : if (VertLeq(up->getDstVec(), lo->getOrgVec())) {
700 : if constexpr (TessVerbose == VerboseFlag::Full) {
701 : std::cout << "Lo: " << *lo << "\n";
702 : std::cout << "Up: " << *up << "\n";
703 : }
704 :
705 : /* up->Dst is on the left. It is safe to form triangles from lo->Org.
706 : * The EdgeGoesLeft test guarantees progress even when some triangles
707 : * are CW, given that the upper and lower chains are truly monotone.
708 : */
709 4355380 : v0 = &lo->getOrgVec();
710 4380378 : v1 = &lo->getDstVec();
711 4381653 : v2 = &lo->getLeftLoopNext()->getDstVec();
712 :
713 7907203 : while (lo->getLeftLoopNext() != up // invariant is not reached
714 7908789 : && (lo->getLeftLoopNext()->goesLeft()
715 1625623 : || Vec2::isCounterClockwise(*v0, *v1, *v2))) {
716 3535861 : auto tempHalfEdge = connectEdges(lo->getLeftLoopNext(), lo);
717 3536382 : if (tempHalfEdge == nullptr) {
718 100 : return false;
719 : }
720 :
721 3536282 : lo = tempHalfEdge->sym();
722 3536609 : v0 = &lo->getOrgVec();
723 3536599 : v1 = &lo->getDstVec();
724 3536501 : v2 = &lo->getLeftLoopNext()->getDstVec();
725 :
726 3536862 : if (!isDegenerateTriangle(tempHalfEdge)) {
727 3484275 : _faceEdges.emplace_back(tempHalfEdge);
728 : }
729 : }
730 4377290 : lo = lo->getLeftLoopPrev();
731 4377527 : lo->_mark = v;
732 : } else {
733 : if constexpr (TessVerbose == VerboseFlag::Full) {
734 : std::cout << "Up: " << *up << "\n";
735 : std::cout << "Lo: " << *lo << "\n";
736 : }
737 :
738 4452466 : v0 = &up->getDstVec();
739 4449410 : v1 = &up->getOrgVec();
740 4449793 : v2 = &up->getLeftLoopPrev()->getOrgVec();
741 :
742 : /* lo->Org is on the left. We can make CCW triangles from up->Dst. */
743 8106062 : while (lo->getLeftLoopNext() != up
744 8108155 : && (up->getLeftLoopPrev()->goesRight()
745 1709514 : || !Vec2::isCounterClockwise(*v0, *v1, *v2))) {
746 3668156 : auto tempHalfEdge = connectEdges(up, up->getLeftLoopPrev());
747 3669097 : if (tempHalfEdge == nullptr) {
748 75 : return false;
749 : }
750 :
751 3669022 : up = tempHalfEdge->sym();
752 3669290 : v0 = &up->getDstVec();
753 3669168 : v1 = &up->getOrgVec();
754 3669163 : v2 = &up->getLeftLoopPrev()->getOrgVec();
755 :
756 3669379 : if (!isDegenerateTriangle(tempHalfEdge)) {
757 3664166 : _faceEdges.emplace_back(tempHalfEdge);
758 : }
759 : }
760 4443920 : up = up->getLeftLoopNext();
761 4444936 : up->_mark = v;
762 : }
763 : }
764 :
765 : /* Now lo->Org == up->Dst == the leftmost vertex. The remaining region
766 : * can be tessellated in a fan from this leftmost vertex.
767 : */
768 1636251 : while (lo->getLeftLoopNext()->getLeftLoopNext() != up) {
769 408233 : auto tempHalfEdge = connectEdges(lo->getLeftLoopNext(), lo);
770 408245 : if (tempHalfEdge == nullptr) {
771 0 : return false;
772 : }
773 408245 : if (!isDegenerateTriangle(tempHalfEdge)) {
774 408239 : _faceEdges.emplace_back(tempHalfEdge);
775 : }
776 408197 : lo = tempHalfEdge->sym();
777 408200 : lo->_mark = v;
778 : }
779 :
780 1228180 : if (!isDegenerateTriangle(lo)) {
781 1228329 : _faceEdges.emplace_back(lo);
782 : }
783 : return true;
784 : }
785 :
786 8925853 : void Tesselator::Data::sweepVertex(VertexPriorityQueue &pq, EdgeDict &dict, Vertex *v) {
787 1679380 : auto doConnectEdges = [&, this] (HalfEdge *source, HalfEdge *target) {
788 : if constexpr (TessVerbose != VerboseFlag::None) {
789 : std::cout << "\t\tConnect: \n\t\t\t" << *source << "\n\t\t\t" << *target << "\n";
790 : }
791 839576 : auto eNew = connectEdges(source->getLeftLoopPrev(), target);
792 839804 : _edgesOfInterests.emplace_back(eNew);
793 839124 : return eNew;
794 8925853 : };
795 :
796 9588757 : auto onVertex = [&, this] (VertexType type, Edge *fullEdge, HalfEdge *e, HalfEdge *eNext) {
797 9588757 : if (_dryRun) {
798 : return;
799 : }
800 9587820 : auto ePrev = e->getLeftLoopPrev();
801 9591925 : auto ePrevEdge = ePrev->getEdge();
802 9611868 : switch (type) {
803 817559 : case VertexType::Start:
804 : // 1. Insert e(i) in T and set helper(e, i) to v(i).
805 817559 : if (!fullEdge->node) {
806 817540 : fullEdge->node = dict.push(fullEdge, e->_realWinding);
807 : }
808 817399 : fullEdge->node->helper = Helper{e, eNext, type };
809 817399 : break;
810 827429 : case VertexType::End:
811 : // 1. if helper(e, i-1) is a merge vertex
812 : // 2. then Insert the diagonal connecting v(i) to helper(e, i~1) in T.
813 : // 3. Delete e(i-1) from T.
814 827429 : if (auto dictNode = ePrevEdge->node) {
815 827354 : if (dictNode->helper.type == VertexType::Merge) {
816 71980 : doConnectEdges(e, dictNode->helper.e1);
817 : }
818 :
819 : // dict.pop(dictNode);
820 : // ePrev->getEdge()->node = nullptr;
821 : }
822 : break;
823 435925 : case VertexType::Split:
824 : // 1. Search in T to find the edge e(j) directly left of v(i)
825 : // 2. Insert the diagonal connecting v(i) to helper(e, j) in D.
826 : // 3. helper(e, j) <— v(i)
827 : // 4. Insert e(i) in T and set helper(e, i) to v(i)
828 : if constexpr (TessVerbose == VerboseFlag::Full) {
829 : std::cout << "\t\te: " << *e << "\n";
830 : }
831 435925 : if (auto edgeBelow = dict.getEdgeBelow(e->origin, e->vertex)) {
832 : if constexpr (TessVerbose != VerboseFlag::None) {
833 : std::cout << "\t\tedgeBelow: " << *edgeBelow << "\n";
834 : }
835 435904 : if (edgeBelow->helper.e1) {
836 435904 : auto tmpE = doConnectEdges(e, edgeBelow->helper.e1);
837 435768 : edgeBelow->helper = Helper{tmpE, eNext, type };
838 : }
839 : }
840 435768 : if (!fullEdge->node) {
841 435769 : fullEdge->node = dict.push(fullEdge, e->_realWinding);
842 : }
843 435793 : fullEdge->node->helper = Helper{e, eNext, type };
844 435793 : break;
845 426395 : case VertexType::Merge:
846 : // 1. if helper(e, i-1) is a merge vertex
847 : // 2. then Insert the diagonal connecting v, to helper(e, i-1) in D.
848 : // 3. Delete e(i - 1) from T.
849 : if constexpr (TessVerbose == VerboseFlag::Full) {
850 : std::cout << "\t\tePrevEdge: " << *ePrevEdge << "\n";
851 : }
852 426395 : if (auto dictNode = ePrevEdge->node) {
853 4849 : if (dictNode->helper.type == VertexType::Merge) {
854 4849 : doConnectEdges(e, dictNode->helper.e1);
855 4851 : dictNode->helper.type = VertexType::RegularTop;
856 : }
857 :
858 : // dict.pop(dictNode);
859 : // ePrev->getEdge()->node = nullptr;
860 : }
861 :
862 : // 4. Search in T to find the edge e(j) directly left of v(i)
863 : // 5. if helper(e, j) is a merge vertex
864 : // 6. then Insert the diagonal connecting v, to helper(e, j) in D.
865 : // 7. helper(e, j) <— v(i)
866 426397 : if (auto edgeBelow = dict.getEdgeBelow(e->origin, e->vertex)) {
867 : if constexpr (TessVerbose != VerboseFlag::None) {
868 : std::cout << "\t\tedgeBelow: " << *edgeBelow << "\n";
869 : }
870 426336 : if (edgeBelow->helper.type == VertexType::Merge) {
871 4355 : e = doConnectEdges(e, edgeBelow->helper.e1);
872 : }
873 426334 : edgeBelow->helper = Helper{e, eNext, type };
874 : }
875 : break;
876 3511943 : case VertexType::RegularBottom: // boundary above vertex
877 : // 2. if helper(e, i-1) is a merge vertex
878 : // 3. then Insert the diagonal connecting v, to helper(e, i-1) in D
879 : // 4. Delete e(i-1) from T.
880 : // 5. Insert e(i) in T and set helper(e, i) to v(i)
881 : if constexpr (TessVerbose == VerboseFlag::Full) {
882 : std::cout << "\t\tePrevEdge: " << *ePrevEdge << "\n";
883 : }
884 3511943 : if (auto dictNode = ePrevEdge->node) {
885 213555 : if (dictNode->helper.type == VertexType::Merge) {
886 213428 : doConnectEdges(e, dictNode->helper.e1);
887 : }
888 :
889 213493 : dict.pop(dictNode);
890 213481 : ePrevEdge->node = nullptr;
891 : }
892 3511869 : if (!fullEdge->node) {
893 3510482 : fullEdge->node = dict.push(fullEdge, e->_realWinding);
894 : }
895 3511898 : fullEdge->node->helper = Helper{e, eNext, type };
896 3511898 : break;
897 3592617 : case VertexType::RegularTop: // boundary below vertex
898 : // 6. Search in T to find the edge e(j) directly left of v(i)
899 : // 7. if helper(e, j) is a merge vertex
900 : // 8. then Insert the diagonal connecting v(i) to helper(e, j) in D.
901 : // 9. helper(e, j) <- v(i)
902 3592617 : if (auto edgeBelow = dict.getEdgeBelow(e->origin, e->vertex)) {
903 3581845 : if (edgeBelow->helper.type == VertexType::Merge) {
904 109153 : e = doConnectEdges(e, edgeBelow->helper.e1);
905 : }
906 3581801 : edgeBelow->helper = Helper{e, eNext, type };
907 : }
908 : break;
909 : }
910 8925853 : };
911 :
912 : if constexpr (TessVerbose != VerboseFlag::None) {
913 : std::cout << "Sweep event: " << v->_uniqueIdx << ": " << v->_origin << "\n";
914 : }
915 :
916 8925853 : _event = v->_origin;
917 :
918 8925853 : Vec2 tmp;
919 : IntersectionEvent event;
920 :
921 : // first - process intersections
922 : // Intersection can split some edge in dictionary with event vertex,
923 : // so, event vertex will no longer be valid for iteration
924 : do {
925 8925853 : if (auto node = dict.checkForIntersects(v, tmp, event, _mathTolerance)) {
926 : //if (VertLeq(v->_origin, tmp)) {
927 604 : if (processIntersect(v, node, tmp, event) == nullptr) {
928 50 : return;
929 : }
930 : //} else {
931 : // std::cout << "Test\n";
932 : //}
933 : }
934 : } while (0);
935 :
936 : VertexType type;
937 8951549 : HalfEdge * e = v->_edge, *eEnd = v->_edge, *eNext = nullptr;
938 : Edge *fullEdge = nullptr;
939 :
940 8951549 : _eventVertex = v;
941 :
942 : do {
943 18590476 : e->getEdge()->updateInfo();
944 18571819 : fullEdge = e->getEdge();
945 18577976 : if (e->goesRight()) {
946 : // push outcoming edge
947 9330492 : if (auto node = dict.checkForIntersects(e, tmp, event, _mathTolerance)) {
948 : // edges in dictionary should be still valid
949 : // intersections preserves left subedge, and no
950 : // intersection points can be at the left of sweep line
951 : //if (VertLeq(v->_origin, tmp)) {
952 77565 : processIntersect(v, node, e, tmp, event);
953 : //} else {
954 : // std::cout << "Test\n";
955 : //}
956 77566 : if (!_eventVertex) {
957 : return;
958 : }
959 77516 : e = v->_edge;
960 : }
961 : }
962 18588000 : e = e->_originNext;
963 18588000 : } while (e != v->_edge);
964 :
965 : // rotate to first left non-convex angle counterclockwise
966 : // its critical for correct winding calculations
967 8949073 : eEnd = e = getFirstEdge(v);
968 :
969 : do {
970 18538843 : fullEdge = e->getEdge();
971 :
972 : // save original next to prevent new edges processing
973 : // new edges always added between e and eNext around origin
974 18481223 : eNext = e->_originNext;
975 :
976 18481223 : if (e->goesRight()) {
977 9252785 : if (e->_originNext->goesRight()) {
978 4629277 : if (AngleIsConvex(e, e->_originNext)) {
979 : // winding can be taken from edge below bottom (next) edge
980 : // or 0 if there is no edges below
981 991492 : auto edgeBelow = dict.getEdgeBelow(e->_originNext->getEdge());
982 991077 : if (!edgeBelow) {
983 217240 : e->_realWinding = e->_originNext->_realWinding = 0;
984 : } else {
985 773837 : e->_realWinding = e->_originNext->sym()->_realWinding = edgeBelow->windingAbove;
986 : }
987 :
988 : if constexpr (TessVerbose != VerboseFlag::None) {
989 : std::cout << "\tright-convex: " << e << " " << e->getDstVec() << " - " << e->getOrgVec() << " - " << e->_originNext->getDstVec()
990 : << " = " << e->_realWinding;
991 : }
992 :
993 : type = VertexType::Split;
994 991095 : if (isWindingInside(_winding, e->_realWinding)) {
995 : if constexpr (TessVerbose != VerboseFlag::None) {
996 : std::cout << "; Split\n";
997 : }
998 435925 : onVertex(VertexType::Split, fullEdge, e, e->_originNext);
999 : } else {
1000 : if constexpr (TessVerbose != VerboseFlag::None) {
1001 : std::cout << "\n";
1002 : }
1003 : }
1004 : } else {
1005 1323427 : _edgesOfInterests.emplace_back(e);
1006 :
1007 1322665 : e->_realWinding = e->_originNext->sym()->_realWinding = e->sym()->_realWinding + e->sym()->_winding;
1008 :
1009 : if constexpr (TessVerbose != VerboseFlag::None) {
1010 : std::cout << "\tright: " << e << " " << e->getDstVec() << " - " << e->getOrgVec() << " - " << e->_originNext->getDstVec()
1011 : << " = " << e->_realWinding << "(" << e->sym()->_realWinding << "+" << e->sym()->_winding << ")";
1012 : }
1013 :
1014 : type = VertexType::Start;
1015 1322935 : if (isWindingInside(_winding, e->_realWinding)) {
1016 : if constexpr (TessVerbose != VerboseFlag::None) {
1017 : std::cout << "; Start\n";
1018 : }
1019 817606 : onVertex(VertexType::Start, fullEdge, e, e->_originNext);
1020 : } else {
1021 : if constexpr (TessVerbose != VerboseFlag::None) {
1022 : std::cout << "\n";
1023 : }
1024 : }
1025 : }
1026 : } else {
1027 : // right-to-left
1028 6951693 : e->_realWinding = e->_originNext->sym()->_realWinding;
1029 :
1030 : if constexpr (TessVerbose != VerboseFlag::None) {
1031 : std::cout << "\tright-to-left: " << e << " " << e->getDstVec() << " - " << e->getOrgVec() << " - " << e->_originNext->getDstVec()
1032 : << " = " << e->_realWinding << "(" << e->_originNext->sym()->_realWinding << ":" << e->_originNext->_realWinding << ")";
1033 : }
1034 :
1035 : type = VertexType::RegularBottom;
1036 6952481 : if (isWindingInside(_winding, e->_realWinding)) {
1037 : if constexpr (TessVerbose != VerboseFlag::None) {
1038 : std::cout << "; RegularBottom\n";
1039 : }
1040 3510874 : onVertex(VertexType::RegularBottom, fullEdge, e, e->_originNext);
1041 : } else {
1042 : if constexpr (TessVerbose != VerboseFlag::None) {
1043 : std::cout << "\n";
1044 : }
1045 : }
1046 : }
1047 :
1048 : // std::cout << "\t\tpush edge" << fullEdge->getLeftVec() << " - " << fullEdge->getRightVec()
1049 : // << " winding: " << e->_realWinding << "\n";
1050 :
1051 : // push outcoming edge
1052 9267202 : if (!fullEdge->node) {
1053 4528481 : fullEdge->node = dict.push(fullEdge, e->_realWinding);
1054 4527748 : if (isWindingInside(_winding, e->_realWinding)) {
1055 475 : fullEdge->node->helper = Helper{e, e->_originNext, type };
1056 : }
1057 : }
1058 : } else {
1059 : // remove incoming edge
1060 9297442 : if (e->_originNext->goesRight()) {
1061 : // left-to-right
1062 6993490 : e->_originNext->sym()->_realWinding = e->_realWinding;
1063 :
1064 : if constexpr (TessVerbose != VerboseFlag::None) {
1065 : std::cout << "\tleft-to-right: " << e << " " << e->getDstVec() << " - " << e->getOrgVec() << " - " << e->_originNext->getDstVec()
1066 : << " = " << e->_realWinding;
1067 : }
1068 :
1069 : type = VertexType::RegularTop;
1070 6992844 : if (isWindingInside(_winding, e->_realWinding)) {
1071 : if constexpr (TessVerbose != VerboseFlag::None) {
1072 : std::cout << "; RegularTop\n";
1073 : }
1074 3592658 : onVertex(VertexType::RegularTop, fullEdge, e, e->_originNext);
1075 : } else {
1076 : if constexpr (TessVerbose != VerboseFlag::None) {
1077 : std::cout << "\n";
1078 : }
1079 : }
1080 :
1081 : } else {
1082 4628454 : if (AngleIsConvex(e, e->_originNext)) {
1083 : if constexpr (TessVerbose != VerboseFlag::None) {
1084 : std::cout << "\tleft-convex: " << e << " " << e->getDstVec() << " - " << e->getOrgVec() << " - " << e->_originNext->getDstVec()
1085 : << " = " << e->_realWinding;
1086 : }
1087 :
1088 : type = VertexType::Merge;
1089 977687 : if (isWindingInside(_winding, e->_realWinding)) {
1090 : if constexpr (TessVerbose != VerboseFlag::None) {
1091 : std::cout << "; Merge\n";
1092 : }
1093 426375 : onVertex(VertexType::Merge, fullEdge, e, e->_originNext);
1094 : } else {
1095 : if constexpr (TessVerbose != VerboseFlag::None) {
1096 : std::cout << "\n";
1097 : }
1098 : }
1099 :
1100 : } else {
1101 : if constexpr (TessVerbose != VerboseFlag::None) {
1102 : std::cout << "\tleft: " << e << " " << e->getDstVec() << " - " << e->getOrgVec() << " - " << e->_originNext->getDstVec()
1103 : << " = " << e->_realWinding;
1104 : }
1105 :
1106 : type = VertexType::End;
1107 1336844 : if (isWindingInside(_winding, e->_realWinding)) {
1108 : if constexpr (TessVerbose != VerboseFlag::None) {
1109 : std::cout << "; End\n";
1110 : }
1111 827637 : onVertex(VertexType::End, fullEdge, e, e->_originNext);
1112 : } else {
1113 : if constexpr (TessVerbose != VerboseFlag::None) {
1114 : std::cout << "\n";
1115 : }
1116 : }
1117 : }
1118 : }
1119 :
1120 9297252 : if (fullEdge->node) {
1121 9296812 : if (fullEdge->node->helper.type != VertexType::Merge) {
1122 9003769 : dict.pop(fullEdge->node);
1123 8941237 : fullEdge->node = nullptr;
1124 : }
1125 : }
1126 : }
1127 18501189 : e = eNext;
1128 18501189 : } while( e != eEnd );
1129 :
1130 8915703 : _eventVertex = nullptr;
1131 :
1132 8915703 : v->_exportIdx = _exportVertexes.size();
1133 8862948 : _exportVertexes.emplace_back(v);
1134 : }
1135 :
1136 82668 : HalfEdge *Tesselator::Data::processIntersect(Vertex *v, const EdgeDictNode *edge1, HalfEdge *edge2, Vec2 &intersect, IntersectionEvent ev) {
1137 : if constexpr (TessVerbose != VerboseFlag::None) {
1138 : if (edge2) {
1139 : std::cout << "Intersect: " << edge1->org << " - " << edge1->dst() << " X "
1140 : << edge2->getOrgVec() << " - " << edge2->getDstVec() << " = " << intersect << ": " << ev << "\n";
1141 : } else {
1142 : std::cout << "Intersect: " << edge1->org << " - " << edge1->dst() << " X "
1143 : << v->_origin << " = " << intersect << ": " << ev << "\n";
1144 : }
1145 : }
1146 :
1147 82562 : auto fixDictEdge = [&] (const EdgeDictNode *e) {
1148 82562 : e->edge->direction = nan();
1149 82556 : e->edge->updateInfo();
1150 82559 : auto &org = e->edge->getOrgVec();
1151 82559 : auto &dst = e->edge->getDstVec();
1152 : auto tmp = const_cast<EdgeDictNode *>(e);
1153 82559 : if (e->edge->inverted) {
1154 36319 : tmp->norm = org - dst;
1155 36319 : tmp->value.z = org.x;
1156 36319 : tmp->value.w = org.y;
1157 36319 : tmp->horizontal = std::abs(tmp->norm.x) > std::numeric_limits<float>::epsilon();
1158 : } else {
1159 46240 : tmp->norm = dst - org;
1160 46240 : tmp->value.z = dst.x;
1161 46240 : tmp->value.w = dst.y;
1162 46240 : tmp->horizontal = std::abs(tmp->norm.x) > std::numeric_limits<float>::epsilon();
1163 : }
1164 82556 : };
1165 :
1166 87523 : auto checkRecursive = [&, this] (HalfEdge *e) {
1167 82423 : if (auto node = _edgeDict->checkForIntersects(e, intersect, ev, _mathTolerance)) {
1168 5100 : processIntersect(v, node, e, intersect, ev);
1169 : }
1170 165092 : };
1171 :
1172 : Vertex *vertex = nullptr;
1173 :
1174 82668 : switch (ev) {
1175 82427 : case IntersectionEvent::Regular:
1176 : // split both edge1 and edge2, recursive check on new edge2 segments
1177 82427 : vertex = splitEdge(edge1->edge->inverted ? &edge1->edge->right : &edge1->edge->left, edge2, intersect);
1178 : if constexpr (TessVerbose != VerboseFlag::None) {
1179 : std::cout << "\tVertex: " << *vertex << "\n";
1180 : }
1181 82428 : fixDictEdge(edge1);
1182 82423 : checkRecursive(edge2);
1183 82427 : _vertexQueue->insert(vertex);
1184 : break;
1185 0 : case IntersectionEvent::EventIsIntersection:
1186 : // two cases: edges overlap or edge2 starts on edge1
1187 : // in either cases we just split edge1, then merge vertexes
1188 : // if edges is overlapping - it will be processed when new edge1 segment checked for intersections
1189 : // edge2 can be null here
1190 0 : vertex = splitEdge(edge1->edge->getPostitive(), intersect);
1191 0 : fixDictEdge(edge1);
1192 0 : if (!mergeVertexes(v, vertex)) {
1193 0 : releaseVertex(v);
1194 0 : return nullptr;
1195 : }
1196 : break;
1197 107 : case IntersectionEvent::EdgeConnection1:
1198 : // Edge2 ends somewhere on Edge1
1199 : // split Edge1, next segment will be checked on next sweep event
1200 107 : vertex = splitEdge(edge2->getEdge()->getPostitive(), intersect);
1201 107 : if (!mergeVertexes(_vertexes[edge1->edge->getNegative()->vertex], vertex)) {
1202 0 : releaseVertex(_vertexes[edge1->edge->getNegative()->vertex]);
1203 0 : return nullptr;
1204 : }
1205 : break;
1206 134 : case IntersectionEvent::EdgeConnection2:
1207 : // Edge1 ends somewhere on Edge2
1208 : // split Edge2, perform recursive checks on new segment
1209 134 : vertex = splitEdge(edge1->edge->getPostitive(), intersect);
1210 134 : fixDictEdge(edge1);
1211 134 : if (!mergeVertexes(_vertexes[edge2->getEdge()->getNegative()->vertex], vertex)) {
1212 0 : releaseVertex(_vertexes[edge2->getEdge()->getNegative()->vertex]);
1213 0 : return nullptr;
1214 : }
1215 : break;
1216 : }
1217 :
1218 : return edge2;
1219 : }
1220 :
1221 604 : HalfEdge *Tesselator::Data::processIntersect(Vertex *v, const EdgeDictNode *edge1, Vec2 &intersect, IntersectionEvent ev) {
1222 : if constexpr (TessVerbose != VerboseFlag::None) {
1223 : std::cout << "Intersect: " << edge1->org << " - " << edge1->dst() << " X "
1224 : << v->_origin << " = " << intersect << ": " << ev << "\n";
1225 : }
1226 :
1227 604 : auto fixDictEdge = [&] (const EdgeDictNode *e) {
1228 604 : e->edge->direction = nan();
1229 604 : e->edge->updateInfo();
1230 604 : auto &org = e->edge->getOrgVec();
1231 604 : auto &dst = e->edge->getDstVec();
1232 : auto tmp = const_cast<EdgeDictNode *>(e);
1233 604 : if (e->edge->inverted) {
1234 184 : tmp->norm = org - dst;
1235 184 : tmp->value.z = org.x;
1236 184 : tmp->value.w = org.y;
1237 184 : tmp->horizontal = std::abs(tmp->norm.x) > std::numeric_limits<float>::epsilon();
1238 : } else {
1239 420 : tmp->norm = dst - org;
1240 420 : tmp->value.z = dst.x;
1241 420 : tmp->value.w = dst.y;
1242 420 : tmp->horizontal = std::abs(tmp->norm.x) > std::numeric_limits<float>::epsilon();
1243 : }
1244 604 : };
1245 :
1246 : Vertex *vertex = nullptr;
1247 :
1248 604 : switch (ev) {
1249 604 : case IntersectionEvent::EventIsIntersection:
1250 : // two cases: edges overlap or edge2 starts on edge1
1251 : // in either cases we just split edge1, then merge vertexes
1252 : // if edges is overlapping - it will be processed when new edge1 segment checked for intersections
1253 : // edge2 can be null here
1254 604 : vertex = splitEdge(edge1->edge->getPostitive(), intersect);
1255 604 : fixDictEdge(edge1);
1256 604 : if (!mergeVertexes(v, vertex)) {
1257 0 : releaseVertex(v);
1258 0 : return nullptr;
1259 : }
1260 : break;
1261 : default:
1262 : return nullptr;
1263 : }
1264 :
1265 604 : return edge1->edge->getPostitive();
1266 : }
1267 :
1268 445124 : Edge *Tesselator::Data::makeEdgeLoop(const Vec2 &origin) {
1269 445124 : Edge *edge = allocEdge();
1270 :
1271 445129 : makeVertex(&edge->left)->_origin = origin;
1272 444429 : edge->right.copyOrigin(&edge->left);
1273 :
1274 444472 : edge->left.origin = edge->right.origin = origin;
1275 444472 : edge->left._leftNext = &edge->left; edge->left._originNext = &edge->right;
1276 444472 : edge->right._leftNext = &edge->right; edge->right._originNext = &edge->left;
1277 :
1278 444472 : return edge;
1279 : }
1280 :
1281 9649822 : Vertex *Tesselator::Data::makeVertex(HalfEdge *eOrig) {
1282 9649822 : Vertex *vNew = allocVertex();
1283 9582280 : vNew->insertBefore(eOrig);
1284 9588959 : return vNew;
1285 : }
1286 :
1287 9554119 : HalfEdge *Tesselator::Data::pushVertex(HalfEdge *e, const Vec2 &origin, bool clockwise, bool returnNew) {
1288 9554119 : if (!e) {
1289 : /* Make a self-loop (one vertex, one edge). */
1290 445111 : auto edge = makeEdgeLoop(origin);
1291 :
1292 444467 : edge->left._winding = (clockwise ? -1 : 1);
1293 444467 : edge->right._winding = (clockwise ? 1 : -1);
1294 444467 : e = &edge->left;
1295 : } else {
1296 : // split primary edge
1297 :
1298 9109008 : Edge *eNew = allocEdge(); // make new edge pair
1299 9123500 : Vertex *v = makeVertex(&eNew->left); // make _sym as origin, because _leftNext will be clockwise
1300 9069932 : v->_origin = origin;
1301 :
1302 9069932 : HalfEdge::splitEdgeLoops(e, &eNew->left, v);
1303 :
1304 9072018 : if (returnNew) {
1305 : e = &eNew->left;
1306 : }
1307 : }
1308 :
1309 9516485 : if (origin.x < _bmin.x) _bmin.x = origin.x;
1310 9516485 : if (origin.x > _bmax.x) _bmax.x = origin.x;
1311 9516485 : if (origin.y < _bmin.y) _bmin.y = origin.y;
1312 9516485 : if (origin.y > _bmax.y) _bmax.y = origin.y;
1313 :
1314 9516485 : ++ _nvertexes;
1315 :
1316 9516485 : return e;
1317 : }
1318 :
1319 8426670 : HalfEdge *Tesselator::Data::connectEdges(HalfEdge *eOrg, HalfEdge *eDst) {
1320 8426670 : if (eOrg->sym()->vertex == eDst->vertex) {
1321 175 : std::cout << "ERROR: connectEdges on same vertex:\n\t" << *eOrg << "\n\t" << *eOrg->sym() << "\n\t" << *eDst << "\n";
1322 175 : return nullptr;
1323 : }
1324 :
1325 : // for triangle cut - eDst->lnext = eOrg
1326 8427591 : Edge *edge = allocEdge();
1327 8422333 : HalfEdge *eNew = &edge->left; // make new edge pair
1328 8422333 : HalfEdge *eNewSym = eNew->sym();
1329 8423730 : HalfEdge *ePrev = eDst->_originNext->sym();
1330 8423651 : HalfEdge *eNext = eOrg->_leftNext;
1331 :
1332 8423651 : eNew->_realWinding = eNewSym->_realWinding = eOrg->_realWinding;
1333 :
1334 8423651 : eNew->copyOrigin(eOrg->sym());
1335 8423916 : eNew->sym()->copyOrigin(eDst);
1336 :
1337 8424042 : ePrev->_leftNext = eNewSym; eNewSym->_leftNext = eNext; // external left chain
1338 8424042 : eNew->_leftNext = eDst; eOrg->_leftNext = eNew; // internal left chain
1339 :
1340 8424042 : eNew->_originNext = eOrg->sym(); eNext->_originNext = eNew; // org vertex chain
1341 8421700 : eNewSym->_originNext = ePrev->sym(); eDst->_originNext = eNewSym; // dst vertex chain
1342 :
1343 : if constexpr (TessVerbose != VerboseFlag::None) {
1344 : std::cout << "\t\t\tConnected: " << *eNew << "\n";
1345 : }
1346 :
1347 8420448 : edge->updateInfo();
1348 :
1349 8443640 : return eNew;
1350 : }
1351 :
1352 1230 : Vertex *Tesselator::Data::splitEdge(HalfEdge *eOrg1, const Vec2 &vec) {
1353 : Vertex *v = nullptr;
1354 :
1355 : if constexpr (TessVerbose != VerboseFlag::None) {
1356 : std::cout << "SplitEdge:\n\t" << *eOrg1 << "\n";
1357 : }
1358 :
1359 1230 : HalfEdge *eNew = &allocEdge()->left; // make new edge pair
1360 1230 : v = makeVertex(eNew); // make _sym as origin, because _leftNext will be clockwise
1361 1230 : v->_origin = vec;
1362 :
1363 1230 : auto v2 = _vertexes[eOrg1->sym()->vertex];
1364 :
1365 1230 : HalfEdge::splitEdgeLoops(eOrg1, eNew, v);
1366 :
1367 1230 : if (v2->_edge == eOrg1->sym()) {
1368 598 : v2->_edge = eNew->sym();
1369 : }
1370 :
1371 1229 : eNew->getEdge()->direction = nan();
1372 1229 : eNew->getEdge()->updateInfo();
1373 :
1374 : if constexpr (TessVerbose != VerboseFlag::None) {
1375 : std::cout << "\t" << *eOrg1 << "\n\t" << *eNew << "\n";
1376 : }
1377 :
1378 1230 : return v;
1379 : }
1380 :
1381 82425 : Vertex *Tesselator::Data::splitEdge(HalfEdge *eOrg1, HalfEdge *eOrg2, const Vec2 &vec2) {
1382 : Vertex *v = nullptr;
1383 : HalfEdge *oPrevOrg = nullptr;
1384 : HalfEdge *oPrevNew = nullptr;
1385 :
1386 82425 : const Edge *fullEdge1 = eOrg1->getEdge();
1387 82421 : const Edge *fullEdge2 = eOrg2->getEdge();
1388 :
1389 : // swap edges if eOrg2 will be upper then eOrg1
1390 82424 : if (fullEdge2->direction > fullEdge1->direction) {
1391 : auto tmp = eOrg2;
1392 : eOrg2 = eOrg1;
1393 : eOrg1 = tmp;
1394 : }
1395 :
1396 : do {
1397 : // split primary edge
1398 82424 : HalfEdge *eNew = &allocEdge()->left; // make new edge pair
1399 82427 : v = makeVertex(eNew); // make _sym as origin, because _leftNext will be clockwise
1400 82410 : v->_origin = vec2;
1401 :
1402 82410 : auto v2 = _vertexes[eOrg1->sym()->vertex];
1403 :
1404 82411 : HalfEdge::splitEdgeLoops(eOrg1, eNew, v);
1405 :
1406 82407 : if (v2->_edge == eOrg1->sym()) {
1407 39322 : v2->_edge = eNew->sym();
1408 : }
1409 :
1410 : oPrevOrg = eNew;
1411 82410 : oPrevNew = eOrg1->sym();
1412 :
1413 82412 : eNew->getEdge()->updateInfo();
1414 : } while (0);
1415 :
1416 : do {
1417 82428 : auto v2 = _vertexes[eOrg2->sym()->vertex];
1418 :
1419 : // split and join secondary edge
1420 82414 : HalfEdge *eNew = &allocEdge()->left; // make new edge pair
1421 :
1422 82414 : HalfEdge::splitEdgeLoops(eOrg2, eNew, v);
1423 82413 : HalfEdge::joinEdgeLoops(eOrg2, oPrevOrg);
1424 82417 : HalfEdge::joinEdgeLoops(eNew->sym(), oPrevNew);
1425 :
1426 82418 : if (v2->_edge == eOrg2->sym()) {
1427 35729 : v2->_edge = eNew->sym();
1428 : }
1429 :
1430 82416 : eNew->getEdge()->direction = nan();
1431 82418 : eNew->getEdge()->updateInfo();
1432 : } while (0);
1433 :
1434 82428 : return v;
1435 : }
1436 :
1437 : // rotate to first left non-convex angle counterclockwise
1438 8949166 : HalfEdge *Tesselator::Data::getFirstEdge(Vertex *v) const {
1439 8949166 : auto e = v->_edge;
1440 : do {
1441 13975394 : if (e->goesRight()) {
1442 8638983 : if (e->_originNext->goesRight()) {
1443 3308986 : if (AngleIsConvex(e, e->_originNext)) {
1444 : // convex right angle is solution
1445 991450 : return e;
1446 : } else {
1447 : // non-convex right angle, skip
1448 : }
1449 : } else {
1450 : // right-to-left angle, next angle is solution
1451 6991877 : return e->_originNext;
1452 : }
1453 : } else {
1454 5341409 : if (e->_originNext->goesLeft()) {
1455 3476625 : if (AngleIsConvex(e, e->_originNext)) {
1456 : // convex left angle, next angle is solution
1457 978488 : return e->_originNext;
1458 : } else {
1459 : // non-convex left angle, skip
1460 : }
1461 : } else {
1462 : // left-to-right angle, skip
1463 : }
1464 : }
1465 5026278 : e = e->_originNext;
1466 5026278 : } while ( e != v->_edge );
1467 : return e;
1468 : }
1469 :
1470 2717838 : static bool Tesselator_checkConnectivity(HalfEdge *eOrg) {
1471 : if constexpr (TessVerbose != VerboseFlag::None) {
1472 : auto eOrgTmp = eOrg;
1473 : auto n = 0;
1474 : while (n < 100) {
1475 : eOrgTmp = eOrgTmp->_originNext;
1476 : if (eOrgTmp == eOrg) {
1477 : break;
1478 : }
1479 : ++ n;
1480 : }
1481 :
1482 : if (n >= 100) {
1483 : return false;
1484 : }
1485 : }
1486 :
1487 2717838 : return true;
1488 : }
1489 :
1490 543581 : bool Tesselator::Data::mergeVertexes(Vertex *org, Vertex *merge) {
1491 543581 : if (std::find(_protectedVertexes.begin(), _protectedVertexes.end(), org) != _protectedVertexes.end()) {
1492 : return true;
1493 : }
1494 :
1495 543579 : if (std::find(_protectedVertexes.begin(), _protectedVertexes.end(), merge) != _protectedVertexes.end()) {
1496 : return true;
1497 : }
1498 :
1499 : if constexpr (TessVerbose != VerboseFlag::None) {
1500 : std::cout << TessVerbose << "Merge:\n\t" << *org << "\n";
1501 : org->foreach([&] (const HalfEdge &e) {
1502 : std::cout << "\t\t" << e << "\n";
1503 : });
1504 :
1505 : std::cout << "\t" << *merge << "\n";
1506 : merge->foreach([&] (const HalfEdge &e) {
1507 : std::cout << "\t\t" << e << "\n";
1508 : });
1509 : }
1510 :
1511 1087287 : auto insertNext = [&] (HalfEdge *l, HalfEdge *r) {
1512 1087287 : auto lNext = l->_originNext;
1513 :
1514 1087287 : if (r->_originNext != r) {
1515 543757 : auto rOriginPrev = r->getOriginPrev();
1516 543757 : auto rLeftPrev = r->getLeftLoopPrev();
1517 :
1518 543757 : rOriginPrev->_originNext = r->_originNext;
1519 543757 : rLeftPrev->_leftNext = rOriginPrev;
1520 : }
1521 :
1522 1087287 : r->_originNext = lNext; r->sym()->_leftNext = l;
1523 1087285 : lNext->sym()->_leftNext = r; l->_originNext = r;
1524 1087283 : return r;
1525 : };
1526 :
1527 561033 : auto mergeEdges = [&] (HalfEdge *eOrg, HalfEdge *eMerge) {
1528 561033 : if (eOrg->_leftNext->sym() == eMerge) {
1529 : if constexpr (TessVerbose != VerboseFlag::None) {
1530 : std::cout << "Merge next (auto):\n\t" << *eOrg << "\n\t" << *eMerge << "\n";
1531 : }
1532 :
1533 1406 : return insertNext(eOrg, eMerge);
1534 559626 : } else if (eMerge->_leftNext->sym() == eOrg) {
1535 : if constexpr (TessVerbose != VerboseFlag::None) {
1536 : std::cout << "Merge prev (auto):\n\t" << *eOrg << "\n\t" << *eMerge << "\n";
1537 : }
1538 :
1539 279056 : insertNext(eOrg->getOriginPrev(), eMerge);
1540 279056 : return eOrg;
1541 : } else {
1542 280572 : auto eOrgCcw = Vec2::isCounterClockwise(org->_origin, eOrg->getDstVec(), eOrg->_leftNext->getDstVec());
1543 280572 : auto eMergeCcw = Vec2::isCounterClockwise(org->_origin, eMerge->getDstVec(), eMerge->_leftNext->getDstVec());
1544 280571 : if (eOrgCcw == eMergeCcw) {
1545 88586 : if (eOrg->goesRight() && eMerge->goesRight()) {
1546 79280 : if (VertLeq(eOrg->getDstVec(), eMerge->getDstVec())) {
1547 : if constexpr (TessVerbose != VerboseFlag::None) {
1548 : std::cout << "Merge prev (direct):\n\t" << *eOrg << "\n\t" << *eMerge << "\n";
1549 : }
1550 :
1551 79059 : insertNext(eOrg->getOriginPrev(), eMerge);
1552 79059 : return eOrg;
1553 : } else {
1554 : if constexpr (TessVerbose != VerboseFlag::None) {
1555 : std::cout << "Merge next (direct):\n\t" << *eOrg << "\n\t" << *eMerge << "\n";
1556 : }
1557 :
1558 219 : return insertNext(eOrg, eMerge);
1559 : }
1560 : } else {
1561 9306 : if (VertLeq(eOrg->getDstVec(), eMerge->getDstVec())) {
1562 : if constexpr (TessVerbose != VerboseFlag::None) {
1563 : std::cout << "Merge next (reverse):\n\t" << *eOrg << "\n\t" << *eMerge << "\n";
1564 : }
1565 :
1566 9183 : return insertNext(eOrg, eMerge);
1567 : } else {
1568 : if constexpr (TessVerbose != VerboseFlag::None) {
1569 : std::cout << "Merge prev (reverse):\n\t" << *eOrg << "\n\t" << *eMerge << "\n";
1570 : }
1571 :
1572 125 : insertNext(eOrg->getOriginPrev(), eMerge);
1573 125 : return eOrg;
1574 : }
1575 : }
1576 191985 : } else if (eOrgCcw) {
1577 : if constexpr (TessVerbose != VerboseFlag::None) {
1578 : std::cout << "Merge prev (ccw):\n\t" << *eOrg << "\n\t" << *eMerge << "\n";
1579 : }
1580 :
1581 99556 : auto r = insertNext(eOrg, eMerge);
1582 99556 : return r;
1583 : } else {
1584 : if constexpr (TessVerbose != VerboseFlag::None) {
1585 : std::cout << "Merge next (ccw):\n\t" << *eOrg << "\n\t" << *eMerge << "\n";
1586 : }
1587 :
1588 92429 : insertNext(eOrg->getOriginPrev(), eMerge);
1589 92429 : return eOrg;
1590 : }
1591 : }
1592 543573 : };
1593 :
1594 543573 : auto eOrg = org->_edge;
1595 543573 : auto eMerge = merge->_edge;
1596 : auto eMergeEnd = eMerge;
1597 :
1598 1087155 : float lA = EdgeAngle(eOrg->getNormVec(), eOrg->getOriginNext()->getNormVec());
1599 :
1600 : // merge common edges, if any
1601 : do {
1602 1087385 : auto eMergeNext = eMerge->_originNext;
1603 :
1604 1087385 : if (eMerge->sym()->vertex == org->_uniqueIdx && eMergeNext->_originNext == eMerge) {
1605 50 : org->_edge = removeEdge(eMerge);
1606 50 : releaseVertex(merge);
1607 : if constexpr (TessVerbose == VerboseFlag::Full) {
1608 : std::cout << TessVerbose << "Out:\n\t" << *org << "\n";
1609 : }
1610 50 : return true;
1611 : }
1612 :
1613 : eMerge = eMergeNext;
1614 1087332 : } while (eMerge != eMergeEnd);
1615 :
1616 543529 : if (!Tesselator_checkConnectivity(org->_edge)) {
1617 0 : log::error("geom::Tesselator", "Pizdets");
1618 : }
1619 :
1620 : do {
1621 1087289 : auto eMergeNext = eMerge->_originNext;
1622 :
1623 : do {
1624 : if constexpr (TessVerbose != VerboseFlag::None) {
1625 : std::cout << "eMerge: " << *eMerge << "\n";
1626 : }
1627 1813623 : auto rA = EdgeAngle(eOrg->getNormVec(), eMerge->getNormVec());
1628 1813620 : if (EdgeAngleIsBelowTolerance(rA, _mathTolerance)) {
1629 561031 : auto tmpOrg = mergeEdges(eOrg, eMerge);
1630 :
1631 : /*if (eMerge == eMerge->_originNext) {
1632 : std::cout << "Final:\n\t" << *eMerge << "\n";
1633 : }*/
1634 :
1635 561028 : if (!Tesselator_checkConnectivity(org->_edge)) {
1636 0 : log::error("geom::Tesselator", "Pizdets");
1637 : }
1638 :
1639 561028 : eMerge->origin = eOrg->origin;
1640 561028 : eMerge->vertex = eOrg->vertex;
1641 : eOrg = tmpOrg;
1642 561028 : lA = EdgeAngle(eOrg->getNormVec(), eOrg->getOriginNext()->getNormVec());
1643 561032 : break;
1644 1252589 : } else if (rA < lA) {
1645 : if constexpr (TessVerbose != VerboseFlag::None) {
1646 : std::cout << "Insert next:\n\t" << *eOrg << "\n\t" << *eMerge << "\n";
1647 : }
1648 :
1649 : /*if (eMerge == eMerge->_originNext) {
1650 : std::cout << "Final:\n\t" << *eMerge << "\n";
1651 : }
1652 :
1653 : std::cout << "Final2:"
1654 : << "\n\tnext-next: " << *eMergeNext->_originNext
1655 : << "\n\tnext: " << *eMergeNext
1656 : << "\n\tmerge: " << *eMerge
1657 : << "\n\tprev: " << *eMerge->getOriginPrev()
1658 : << "\n";*/
1659 526257 : auto tmpOrg = insertNext(eOrg, eMerge);
1660 :
1661 : /*std::cout << "Final3:\n\tmerge: " << *eMergeNext
1662 : << "\n\tnext: " << *eMergeNext->_originNext
1663 : << "\n\tprev: " << *eMergeNext->getOriginPrev()
1664 : << "\n";*/
1665 526256 : if (eMergeNext->_originNext == eMerge) {
1666 0 : std::cout << "Final4:\n\t" << *eMerge << "\n";
1667 : }
1668 :
1669 526256 : if (!Tesselator_checkConnectivity(org->_edge)) {
1670 0 : log::error("geom::Tesselator", "Pizdets");
1671 : }
1672 :
1673 526256 : eMerge->origin = eOrg->origin;
1674 526256 : eMerge->vertex = eOrg->vertex;
1675 : eOrg = tmpOrg;
1676 526256 : lA = EdgeAngle(eOrg->getNormVec(), eOrg->getOriginNext()->getNormVec());
1677 526258 : break;
1678 : } else {
1679 726332 : eOrg = eOrg->_originNext;
1680 726332 : lA = EdgeAngle(eOrg->getNormVec(), eOrg->getOriginNext()->getNormVec());
1681 : }
1682 726334 : } while (true);
1683 :
1684 1087290 : if (eMerge == eMergeNext) {
1685 : break;
1686 : }
1687 : eMerge = eMergeNext;
1688 543760 : } while (eMerge != eMergeEnd);
1689 :
1690 543530 : if (!Tesselator_checkConnectivity(org->_edge)) {
1691 0 : log::error("geom::Tesselator", "Pizdets");
1692 : }
1693 :
1694 543530 : if (merge->_queueHandle != maxOf<QueueHandle>()) {
1695 278529 : _vertexQueue->remove(merge->_queueHandle);
1696 278529 : merge->_queueHandle = maxOf<QueueHandle>();
1697 : }
1698 :
1699 543528 : releaseVertex(merge);
1700 :
1701 : // remove degenerates
1702 :
1703 : // remove ears - edge cycles on same vertex
1704 543524 : auto eOrgEnd = eOrg = org->_edge;
1705 :
1706 543524 : if (!Tesselator_checkConnectivity(eOrg)) {
1707 0 : log::error("geom::Tesselator", "Pizdets");
1708 : }
1709 :
1710 : do {
1711 : if constexpr (TessVerbose != VerboseFlag::None) {
1712 : std::cout << TessVerbose << "\t\tRemoveEars: " << *eOrg << "\n";
1713 : }
1714 :
1715 2175636 : auto eOrgNext = eOrg->_originNext;
1716 :
1717 2175636 : if (eOrg->_leftNext->sym() == eOrg->_originNext && eOrg->_originNext->_leftNext->sym() == eOrg) {
1718 : auto eOrgJoin = eOrgNext;
1719 :
1720 : if constexpr (TessVerbose != VerboseFlag::None) {
1721 : std::cout << TessVerbose << "\t\t\t: " << *eOrg << "\n";
1722 : std::cout << TessVerbose << "\t\t\t: " << *eOrgJoin << "\n";
1723 : }
1724 141 : eOrgNext = eOrgJoin->_originNext;
1725 :
1726 141 : auto orgPrev = eOrg->getOriginPrev();
1727 141 : auto orgLeftPrev = eOrg->getLeftLoopPrev();
1728 141 : auto joinLeftPrev = eOrgJoin->getLeftLoopPrev();
1729 :
1730 141 : orgPrev->_originNext = eOrgJoin->_originNext;
1731 141 : orgLeftPrev->_leftNext = eOrg->_leftNext->_leftNext;
1732 141 : joinLeftPrev->_leftNext = eOrgJoin->_leftNext->_leftNext;
1733 :
1734 141 : auto vertex = _vertexes[eOrg->_leftNext->vertex];
1735 :
1736 141 : auto orgEdge = eOrg->getEdge();
1737 141 : if (orgEdge->node) {
1738 0 : _edgeDict->pop(orgEdge->node);
1739 0 : orgEdge->node = nullptr;
1740 : }
1741 141 : releaseEdge(orgEdge);
1742 :
1743 141 : auto joinEdge = eOrgJoin->getEdge();
1744 141 : if (joinEdge->node) {
1745 0 : _edgeDict->pop(joinEdge->node);
1746 0 : joinEdge->node = nullptr;
1747 : }
1748 141 : releaseEdge(joinEdge);
1749 :
1750 : // we can not touch vertexes, that was already exported
1751 : if (VertLeq(_event, vertex->_origin)) {
1752 141 : if ( vertex->_queueHandle != maxOf<QueueHandle>()) {
1753 91 : _vertexQueue->remove(vertex->_queueHandle);
1754 91 : vertex->_queueHandle = maxOf<QueueHandle>();
1755 : }
1756 141 : if (vertex == _eventVertex) {
1757 50 : _eventVertex = nullptr;
1758 : }
1759 : }
1760 :
1761 141 : releaseVertex(vertex);
1762 :
1763 141 : if (eOrg == eOrgEnd || eOrgJoin == eOrgEnd) {
1764 16 : eOrgEnd = org->_edge = eOrgNext->getOriginPrev();
1765 : }
1766 :
1767 141 : if (eOrg == eOrgEnd || eOrgJoin == eOrgEnd || eOrg == eOrgNext) {
1768 : // origin vertex is empty
1769 0 : if (org == _eventVertex) {
1770 0 : _eventVertex = nullptr;
1771 : }
1772 :
1773 0 : org->_edge = nullptr;
1774 0 : log::error("geom::Tesselator", "Pizdets");
1775 0 : return false;
1776 : }
1777 : }
1778 :
1779 : eOrg = eOrgNext;
1780 2175640 : } while (eOrg != eOrgEnd);
1781 :
1782 : if constexpr (TessVerbose != VerboseFlag::None) {
1783 : std::cout << "\tResult (pre): " << eOrg->vertex << "\n";
1784 : org->foreach([&] (const HalfEdge &e) {
1785 : std::cout << "\t\t" << e << "\n";
1786 : if constexpr (TessVerbose == VerboseFlag::Full) {
1787 : e.foreachOnFace([&] (const HalfEdge &e) {
1788 : std::cout << "\t\t\t" << e << "\n";
1789 : });
1790 : }
1791 : });
1792 : }
1793 :
1794 : // process overlaps
1795 543528 : _protectedVertexes.emplace_back(org);
1796 :
1797 543523 : eOrgEnd = eOrg = org->_edge;
1798 : if constexpr (TessVerbose != VerboseFlag::None) {
1799 : std::cout << "Start: " << eOrg->vertex << " (" << _protectedVertexes.size() << "): " << *eOrg << "\n";
1800 : }
1801 : do {
1802 : //std::cout << "\tOverlaps: " << eOrg->vertex << " (" << _protectedVertexes.size() << "): " << *eOrg << "\n";
1803 1924697 : auto eOrgNext = eOrg->_originNext;
1804 :
1805 1924697 : float a = EdgeAngle(eOrg->getNormVec(), eOrgNext->getNormVec());
1806 1924735 : if (EdgeAngleIsBelowTolerance(a, _mathTolerance)) {
1807 : auto eOrgJoin = eOrgNext;
1808 :
1809 541193 : eOrgNext = eOrgJoin->_originNext;
1810 :
1811 541193 : if (processEdgeOverlap(org, eOrg, eOrgJoin)) {
1812 278883 : eOrgEnd = eOrg = org->_edge;
1813 278883 : eOrgNext = eOrg->_originNext;
1814 : } else {
1815 262282 : if (eOrgJoin == eOrgEnd) {
1816 : break;
1817 : }
1818 : }
1819 : }
1820 :
1821 : eOrg = eOrgNext;
1822 1888522 : } while (eOrg != eOrgEnd);
1823 :
1824 : // remove loops
1825 543533 : eOrgEnd = eOrg = org->_edge;
1826 : do {
1827 1858036 : auto eOrgNext = eOrg->_originNext;
1828 :
1829 1858036 : if (eOrg->_leftNext->_leftNext == eOrg) {
1830 280346 : auto next = eOrg->_leftNext->sym();
1831 280350 : if (next == eOrgNext) {
1832 280348 : if (org->_edge == eOrg || eOrgEnd == eOrg) {
1833 18582 : eOrgEnd = org->_edge = eOrgNext;
1834 : }
1835 :
1836 280348 : auto eOrgPrev = eOrg->getOriginPrev();
1837 280348 : auto eOrgSym = eOrg->sym();
1838 280348 : auto eOrgSymPrev = eOrgSym->getLeftLoopPrev();
1839 280348 : auto eOrgSymOrgPrev = eOrgSym->getOriginPrev();
1840 280348 : auto eNextSym = next->sym();
1841 :
1842 280348 : if (next->_winding != eOrg->_winding) {
1843 258789 : next->_winding += eOrg->_winding;
1844 : }
1845 280348 : if (eNextSym->_winding != eOrgSym->_winding) {
1846 258789 : eNextSym->_winding += eOrgSym->_winding;
1847 : }
1848 :
1849 : if constexpr (TessVerbose != VerboseFlag::None) {
1850 : std::cout << "Remove loop: " << eOrg->vertex << " (" << _protectedVertexes.size() << "):\n"
1851 : "\t" << *eOrg << "\n\t" << *eOrg->_leftNext << "\n";
1852 : }
1853 :
1854 280348 : eOrgSymPrev->_leftNext = eNextSym;
1855 280348 : eNextSym->_leftNext = eOrgSym->_leftNext;
1856 :
1857 280348 : eOrgPrev->_originNext = eOrg->_originNext;
1858 280348 : eOrgSymOrgPrev->_originNext = eOrgSym->_originNext;
1859 :
1860 280348 : _vertexes[eOrgSymOrgPrev->vertex]->_edge = eOrgSym->_originNext;
1861 :
1862 : if constexpr (TessVerbose != VerboseFlag::None) {
1863 : _vertexes[eOrgSymOrgPrev->vertex]->foreach([&] (const HalfEdge &e) {
1864 : std::cout << "\tVertex " << eOrgSymOrgPrev->vertex << ": " << e << "\n";
1865 : });
1866 : }
1867 :
1868 280345 : auto joinEdge = eOrg->getEdge();
1869 280345 : if (joinEdge->node) {
1870 40 : _edgeDict->pop(joinEdge->node);
1871 40 : joinEdge->node = nullptr;
1872 : }
1873 280345 : releaseEdge(joinEdge);
1874 : }
1875 : }
1876 :
1877 : eOrg = eOrgNext;
1878 1858027 : } while (eOrg != eOrgEnd);
1879 :
1880 : if constexpr (TessVerbose != VerboseFlag::None) {
1881 : std::cout << "\tResult (post): " << eOrg->vertex << "\n";
1882 : org->foreach([&] (const HalfEdge &e) {
1883 : std::cout << "\t\t" << e << "\n";
1884 : if constexpr (TessVerbose == VerboseFlag::Full) {
1885 : e.foreachOnFace([&] (const HalfEdge &e) {
1886 : std::cout << "\t\t\t" << e << "\n";
1887 : });
1888 : }
1889 : });
1890 : }
1891 :
1892 543524 : _protectedVertexes.pop_back();
1893 : return true;
1894 : }
1895 :
1896 163000 : HalfEdge *Tesselator::Data::removeEdge(HalfEdge *e) {
1897 163000 : auto eSym = e->sym();
1898 :
1899 163037 : auto eLeftPrev = e->getLeftLoopPrev();
1900 163068 : auto eSymLeftPrev = eSym->getLeftLoopPrev();
1901 163115 : auto eOriginPrev = e->getOriginPrev();
1902 163127 : auto eSymOriginPrev = eSym->getOriginPrev();
1903 :
1904 163226 : e->_originNext->origin = e->_leftNext->origin;
1905 163226 : e->_originNext->vertex = e->_leftNext->vertex;
1906 :
1907 163226 : e->_originNext->getEdge()->direction = nan();
1908 163169 : e->_originNext->getEdge()->updateInfo();
1909 :
1910 163724 : eLeftPrev->_leftNext = e->_leftNext;
1911 163724 : eSymLeftPrev->_leftNext = eSym->_leftNext;
1912 :
1913 163724 : eOriginPrev->_originNext = eSym->_originNext;
1914 163724 : eSymOriginPrev->_originNext = e->_originNext;
1915 :
1916 163724 : releaseEdge(e->getEdge());
1917 :
1918 162465 : return eSymOriginPrev->_originNext;
1919 : }
1920 :
1921 1667580 : HalfEdge * Tesselator::Data::removeDegenerateEdges(HalfEdge *e, uint32_t *nedges, bool safeRemove) {
1922 : auto eEnd = e;
1923 :
1924 : do {
1925 20631554 : if (!e) {
1926 : break;
1927 : }
1928 20631554 : auto eLnext = e->_leftNext;
1929 :
1930 20631554 : auto edge = e->getEdge();
1931 20631654 : auto edgeNext = eLnext->getEdge();
1932 :
1933 20632025 : edge->updateInfo();
1934 20619068 : edgeNext->updateInfo();
1935 :
1936 41585283 : while (VertEq(e->getOrgVec(), e->getDstVec(), _mathTolerance) && e->_leftNext->_leftNext != e) {
1937 : if constexpr (TessVerbose != VerboseFlag::None) {
1938 : std::cout << "Remove degenerate: " << *e << "\n";
1939 : }
1940 :
1941 160291 : if (eEnd == e) {
1942 : eEnd = eLnext;
1943 : }
1944 :
1945 160291 : auto vertex = _vertexes[e->sym()->vertex];
1946 159500 : auto merge = _vertexes[e->vertex];
1947 :
1948 : auto tmp = e;
1949 : e = eLnext;
1950 159531 : eLnext = e->_leftNext;
1951 :
1952 159531 : vertex->_edge = removeEdge(tmp);
1953 :
1954 159074 : if (safeRemove) {
1955 159015 : releaseVertex(merge);
1956 : }
1957 :
1958 159083 : if (nedges) {
1959 159033 : -- *nedges;
1960 : }
1961 :
1962 159083 : edge = e->getEdge();
1963 159135 : edgeNext = eLnext->getEdge();
1964 :
1965 159203 : edge->updateInfo();
1966 159146 : edgeNext->updateInfo();
1967 : }
1968 :
1969 20632709 : if (eLnext->_leftNext == e) {
1970 : // Degenerate contour (one or two edges)
1971 :
1972 823 : if (eLnext != e) {
1973 784 : if (safeRemove) {
1974 784 : releaseVertex(_vertexes[eLnext->vertex]);
1975 781 : releaseVertex(_vertexes[eLnext->sym()->vertex]);
1976 : }
1977 783 : releaseEdge(eLnext->getEdge());
1978 782 : if (nedges) {
1979 782 : -- *nedges;
1980 : }
1981 : }
1982 821 : if (safeRemove) {
1983 821 : releaseVertex(_vertexes[e->vertex]);
1984 820 : releaseVertex(_vertexes[e->sym()->vertex]);
1985 : }
1986 820 : releaseEdge(e->getEdge());
1987 819 : if (nedges) {
1988 819 : -- *nedges;
1989 : }
1990 819 : return nullptr; // last edge destroyed
1991 : }
1992 :
1993 : // check and remove tail-like structs
1994 20631886 : if (FloatEq(edge->direction, edgeNext->direction, _mathTolerance)) {
1995 79597 : if (safeRemove) {
1996 3405 : if (eEnd == eLnext) {
1997 : eEnd = eLnext->_leftNext;
1998 : }
1999 :
2000 : HalfEdge *tmp = eLnext;
2001 :
2002 : // we need to recheck e for another degenerate cases
2003 3405 : if (e == eEnd) {
2004 279 : eEnd = e = e->getLeftLoopPrev();
2005 : } else {
2006 3126 : e = e->getLeftLoopPrev();
2007 : }
2008 :
2009 : if (safeRemove) {
2010 3405 : auto vertex = _vertexes[tmp->sym()->vertex];
2011 3403 : auto merge = _vertexes[tmp->vertex];
2012 :
2013 3404 : vertex->_edge = removeEdge(tmp);
2014 3401 : releaseVertex(merge);
2015 : } else {
2016 : auto vertex = _vertexes[tmp->sym()->vertex];
2017 : vertex->_edge = removeEdge(tmp);
2018 : }
2019 :
2020 3402 : if (nedges) {
2021 3402 : -- *nedges;
2022 : }
2023 76192 : } else if (eLnext->_leftNext->_leftNext == e) {
2024 : return nullptr;
2025 : }
2026 : }
2027 20631833 : e = e->_leftNext;
2028 20631833 : } while (e && e != eEnd);
2029 :
2030 : return eEnd;
2031 : }
2032 :
2033 541174 : bool Tesselator::Data::processEdgeOverlap(Vertex *org, HalfEdge *e1, HalfEdge *e2) {
2034 541174 : if (std::find(_protectedEdges.begin(), _protectedEdges.end(), e1) != _protectedEdges.end()) {
2035 : return false;
2036 : }
2037 :
2038 280457 : if (std::find(_protectedEdges.begin(), _protectedEdges.end(), e2) != _protectedEdges.end()) {
2039 : return false;
2040 : }
2041 :
2042 :
2043 : if constexpr (TessVerbose != VerboseFlag::None) {
2044 : std::cout << "processEdgeOverlap:\n\t" << *e1 << "\n\t" << *e2 << "\n";
2045 : }
2046 :
2047 280429 : if (e1->goesLeft()) {
2048 10723 : if (!VertLeq(e2->getDstVec(), e1->getDstVec())) {
2049 75 : std::swap(e1, e2); // split e2
2050 : }
2051 : } else {
2052 269709 : if (!VertLeq(e1->getDstVec(), e2->getDstVec())) {
2053 279 : std::swap(e1, e2); // split e2
2054 : }
2055 : }
2056 :
2057 : Vertex *vMerge;
2058 560863 : if (!VertEq(e1->getDstVec(), e2->getDstVec(), _mathTolerance)) {
2059 385 : vMerge = splitEdge(e2, e1->getDstVec());
2060 : } else {
2061 280046 : vMerge = _vertexes[e2->sym()->vertex];
2062 : }
2063 :
2064 : if constexpr (TessVerbose != VerboseFlag::None) {
2065 : std::cout << "Overlap: " << *e2 << "\n";
2066 : }
2067 :
2068 280425 : auto vOrgIdx = e1->sym()->vertex;
2069 280427 : auto vOrg = _vertexes[vOrgIdx];
2070 :
2071 280424 : _protectedEdges.emplace_back(e2->sym());
2072 280422 : _protectedEdges.emplace_back(e1->sym());
2073 :
2074 280425 : if (vOrg != vMerge) {
2075 278913 : if (std::find(_protectedVertexes.begin(), _protectedVertexes.end(), vOrg) != _protectedVertexes.end()) {
2076 : return false;
2077 : }
2078 :
2079 278890 : if (std::find(_protectedVertexes.begin(), _protectedVertexes.end(), vMerge) != _protectedVertexes.end()) {
2080 : return false;
2081 : }
2082 :
2083 278892 : mergeVertexes(vOrg, vMerge);
2084 :
2085 278887 : _protectedEdges.pop_back();
2086 278885 : _protectedEdges.pop_back();
2087 :
2088 278883 : return true;
2089 : }
2090 :
2091 1512 : _protectedEdges.pop_back();
2092 1513 : _protectedEdges.pop_back();
2093 :
2094 : return false;
2095 : }
2096 :
2097 8832940 : bool Tesselator::Data::isDegenerateTriangle(HalfEdge *e) {
2098 8832940 : if (e->_leftNext->_leftNext == e) {
2099 : return true;
2100 : }
2101 :
2102 : auto eEnd = e;
2103 :
2104 : do {
2105 26260887 : auto eLnext = e->_leftNext;
2106 :
2107 26260887 : auto edge = e->getEdge();
2108 26265589 : auto edgeNext = eLnext->getEdge();
2109 :
2110 26268800 : edge->updateInfo();
2111 26246712 : edgeNext->updateInfo();
2112 :
2113 : // check and remove tail-like structs
2114 26242037 : if (FloatEq(edge->direction, edgeNext->direction, _mathTolerance)) {
2115 : return true;
2116 : }
2117 : e = eLnext;
2118 26194248 : } while (e != eEnd);
2119 :
2120 : return false;
2121 : }
2122 :
2123 5703 : bool Tesselator::Data::removeDegenerateEdges(FaceEdge *e, size_t &removed) {
2124 5703 : if (e->_next->_next == e) {
2125 : return true;
2126 : }
2127 :
2128 : auto eEnd = e;
2129 :
2130 : do {
2131 116368 : auto eLnext = e->_next;
2132 :
2133 116368 : while (VertEq(e->_vertex, eLnext->_vertex, _mathTolerance) && e->_next->_next != e) {
2134 : eLnext = e->_next->_next;
2135 :
2136 0 : if (eEnd == e->_next) {
2137 : eEnd = eLnext;
2138 : }
2139 :
2140 0 : e->_next = e->_next->_next;
2141 0 : ++ removed;
2142 : }
2143 :
2144 116380 : if (eLnext->_next == e) {
2145 0 : if (eLnext != e) {
2146 0 : ++ removed;
2147 : }
2148 0 : ++ removed;
2149 0 : return false; // last edge destroyed
2150 : }
2151 :
2152 : // check and remove tail-like structs
2153 116380 : if (FloatEq(e->_direction, eLnext->_direction, _mathTolerance)) {
2154 0 : if (eLnext->_next->_next == e) {
2155 0 : removed += 3;
2156 0 : return false;
2157 : }
2158 : }
2159 : e = eLnext;
2160 116380 : } while (e != eEnd);
2161 :
2162 : return true;
2163 : }
2164 :
2165 5673 : uint32_t Tesselator::Data::followBoundary(FaceEdge *face, HalfEdge *e, uint8_t mark) {
2166 113456 : auto findNext = [&, this] (HalfEdge *eNext) {
2167 113444 : if (eNext->_originNext->_originNext == eNext) {
2168 : // simple vertex
2169 : return eNext;
2170 : } else {
2171 : // find next boundary in opposite direction to separate subboundaries
2172 : auto prev = eNext->_originNext;
2173 12 : while (isWindingInside(_winding, prev->_realWinding) && prev != eNext) {
2174 8 : prev = prev->_originNext;
2175 : }
2176 4 : if (prev != eNext) {
2177 0 : splitVertex(eNext, prev);
2178 : }
2179 4 : return prev;
2180 : }
2181 : return eNext;
2182 5673 : };
2183 :
2184 : uint32_t nsegments = 0;
2185 : // assume left loop is outside
2186 119123 : while (e->_mark != mark) {
2187 113409 : auto target = e->_leftNext;
2188 113409 : auto eNext = findNext(target);
2189 :
2190 113624 : if (!face) {
2191 5674 : face = allocFaceEdge();
2192 5667 : _boundaries.emplace_back(face);
2193 5667 : face->_next = face;
2194 : } else {
2195 107950 : auto tmp = allocFaceEdge();
2196 107585 : tmp->_next = face->_next;
2197 107585 : face->_next = tmp;
2198 107585 : face = tmp;
2199 : }
2200 :
2201 113252 : ++ nsegments;
2202 113252 : face->_vertex = _vertexes[e->vertex];
2203 113354 : face->_displaced = face->_origin = e->origin;
2204 113354 : face->_direction = e->getEdge()->direction;
2205 :
2206 113450 : if (target != eNext) {
2207 0 : face->_splitVertex = true;
2208 : } else if (face->_vertex->_uniqueIdx >= _nvertexes) {
2209 :
2210 : }
2211 :
2212 113450 : e->_mark = mark;
2213 : e = eNext;
2214 : }
2215 5714 : return nsegments;
2216 : }
2217 :
2218 0 : void Tesselator::Data::splitVertex(HalfEdge *first, HalfEdge *last) {
2219 : // create new vertex for first->orgNext -> last
2220 0 : auto org = _vertexes[first->vertex];
2221 0 : auto vertex = allocVertex();
2222 :
2223 0 : auto front = first->_originNext;
2224 0 : auto back = last->_originNext;
2225 :
2226 0 : first->getLeftLoopPrev()->_leftNext = last;
2227 0 : first->_originNext = back;
2228 :
2229 0 : last->getLeftLoopPrev()->_leftNext = first;
2230 0 : last->_originNext = front;
2231 :
2232 0 : org->_edge = front;
2233 0 : vertex->_edge = first;
2234 0 : vertex->_origin = front->origin;
2235 :
2236 : auto e = first;
2237 : do {
2238 0 : e->vertex = vertex->_uniqueIdx;
2239 0 : e = e->_originNext;
2240 0 : } while (e != first);
2241 :
2242 0 : if (org->_exportIdx != maxOf<uint32_t>()) {
2243 0 : vertex->_exportIdx = uint32_t(_exportVertexes.size());
2244 0 : _exportVertexes.emplace_back(vertex);
2245 : }
2246 0 : }
2247 :
2248 115187 : void Tesselator::Data::displaceBoundary(FaceEdge *edge) {
2249 : auto &v0 = edge->_origin;
2250 115187 : auto &v1 = edge->_next->_origin;
2251 115187 : auto &v2 = edge->_next->_next->_origin;
2252 :
2253 : // use optimized combined direction/normal func
2254 115187 : Vec4 result;
2255 115187 : getVertexNormal(&v0.x, &v1.x, &v2.x, &result.x);
2256 :
2257 115457 : if (std::isnan(result.y) || result.y > 4.0f) {
2258 420 : edge->_next->_value = 1.0f - 4.0f / result.y;
2259 420 : result.y = 4.0f;
2260 : }
2261 :
2262 115296 : float offsetValue = _antialiasValue;
2263 : bool shouldRelocate = false;
2264 115296 : switch (_relocateRule) {
2265 650 : case RelocateRule::Never: offsetValue += _antialiasValue * 0.5f; break;
2266 1600 : case RelocateRule::Always:
2267 : case RelocateRule::Monotonize:
2268 1600 : shouldRelocate = true; break;
2269 113046 : case RelocateRule::Auto:
2270 113046 : if (edge->_next->_splitVertex) {
2271 : shouldRelocate = true;
2272 : } else {
2273 113089 : offsetValue += _antialiasValue * 0.5f;
2274 : }
2275 : break;
2276 : }
2277 :
2278 115296 : const float mod = copysign(result.y * offsetValue, result.x);
2279 :
2280 115296 : edge->_next->_displaced = Vec2(v1.x + result.z * mod, v1.y + result.w * mod);
2281 :
2282 116101 : if (shouldRelocate) {
2283 1600 : if (edge->_next->_vertex) {
2284 1600 : edge->_next->_vertex->relocate(Vec2(v1.x - result.z * mod, v1.y - result.w * mod));
2285 1600 : SPASSERT(!std::isnan(edge->_next->_vertex->_origin.x) && !std::isnan(edge->_next->_vertex->_origin.y),
2286 : "Tess: displaced vertex is NaN");
2287 : }
2288 : }
2289 116101 : }
2290 :
2291 : }
|
