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 "SPTessTypes.h"
25 : #include "SPLog.h"
26 :
27 : namespace STAPPLER_VERSIONIZED stappler::geom {
28 :
29 : static constexpr VerboseFlag TessTypesVerbose = VerboseFlag::None;
30 : static constexpr bool IntersectDebug = false;
31 : static constexpr bool DictDebug = false;
32 :
33 : int TessVerboseInfo = std::ios_base::xalloc();
34 :
35 89880108 : bool EdgeDictNode::operator < (const EdgeDictNode &other) const {
36 89880108 : if (value.y == other.value.y) {
37 11947265 : return edge->direction < other.edge->direction;
38 : } else {
39 77932843 : return value.y < other.value.y;
40 : }
41 : }
42 :
43 2616737 : bool EdgeDictNode::operator < (const Edge &other) const {
44 2616737 : auto &left = other.getLeftVec();
45 2617038 : if (value.y == left.y) {
46 20 : return edge->direction < other.direction; // dst.y
47 : } else {
48 2617018 : return value.y < left.y;
49 : }
50 : }
51 :
52 14420123 : bool EdgeDictNode::operator < (const Vec2 &other) const {
53 14420123 : return value.y < other.y;
54 : }
55 :
56 10531885 : bool EdgeDictNode::operator <= (const EdgeDictNode &other) const {
57 10531885 : if (value.y == other.value.y) {
58 10525113 : return value.w == other.value.w || edge->direction < other.edge->direction; // dst.y
59 : } else {
60 6797 : return value.y < other.value.y;
61 : }
62 : }
63 :
64 0 : bool EdgeDictNode::operator== (const EdgeDictNode &other) const {
65 0 : return value.y == other.value.y && value.w == other.value.w;
66 : }
67 :
68 9584141 : void Vertex::insertBefore(HalfEdge *eOrig) {
69 9584141 : _edge = eOrig;
70 :
71 : /* fix other edges on this vertex loop */
72 : HalfEdge *e = eOrig;
73 : do {
74 9584141 : e->setOrigin(this);
75 9588701 : e = e->_originNext;
76 9588701 : } while( e != eOrig );
77 9588701 : }
78 :
79 0 : void Vertex::removeFromList(Vertex *newOrg) {
80 0 : HalfEdge *e, *eStart = _edge;
81 : e = eStart;
82 : do {
83 0 : e->setOrigin(newOrg);
84 0 : e = e->_originNext;
85 0 : } while( e != eStart );
86 0 : }
87 :
88 0 : void Vertex::foreach(const Callback<void(const HalfEdge &)> &cb) const {
89 0 : auto e = _edge;
90 : do {
91 0 : cb(*e);
92 0 : e = e->_originNext;
93 0 : } while( e != _edge );
94 0 : }
95 :
96 520400 : void Vertex::relocate(const Vec2 &vec) {
97 520400 : _origin = vec;
98 520400 : auto e = _edge;
99 : do {
100 1041200 : e->origin = vec;
101 1041200 : e = e->_originNext;
102 1041200 : } while( e != _edge );
103 520400 : }
104 :
105 0 : void FaceEdge::foreach(const Callback<void(const FaceEdge &)> &cb) const {
106 : auto e = this;
107 : do {
108 0 : cb(*e);
109 0 : e = e->_next;
110 0 : } while( e != this );
111 0 : }
112 :
113 9236827 : void HalfEdge::splitEdgeLoops(HalfEdge *eOrg, HalfEdge *eNew, Vertex *v) {
114 9236827 : eNew->sym()->copyOrigin(eOrg->sym());
115 9242975 : eOrg->sym()->setOrigin(v);
116 9242747 : eNew->setOrigin(v);
117 :
118 9246556 : HalfEdge *a = eOrg, *b = eOrg->sym(), // original edge
119 9245900 : *c = eNew, *d = eNew->sym(), // new edge
120 9248605 : *e = eOrg->_leftNext, // next edge in left loop
121 9248605 : *g = b->_originNext, *h = g->sym(); // prev edge in right loop
122 :
123 9250114 : e->_originNext = d; d->_originNext = g; // vertex cycle around dest vertex;
124 9250114 : c->_originNext = b; b->_originNext = c; // cycle around new vertex;
125 9250114 : a->_leftNext = c; c->_leftNext = e; // left face loop
126 9250114 : h->_leftNext = d; d->_leftNext = b; // right face loop
127 9250114 : c->_winding = a->_winding; d->_winding = b->_winding;
128 9250114 : c->_realWinding = a->_realWinding; d->_realWinding = b->_realWinding;
129 9250114 : }
130 :
131 164824 : void HalfEdge::joinEdgeLoops(HalfEdge *eOrg, HalfEdge *oPrev) {
132 : // connect eOrg into vertex
133 164824 : HalfEdge *a = eOrg, *b = eOrg->sym(), // original edge
134 : *e = oPrev, // next edge in left loop
135 164833 : *g = oPrev->_originNext, *h = g->sym(); // prev edge in right loop
136 :
137 164832 : e->_originNext = b; b->_originNext = g; // cycle around new vertex;
138 164832 : a->_leftNext = e; h->_leftNext = b; // left and right loops
139 164832 : }
140 :
141 292313285 : HalfEdge *HalfEdge::sym() const {
142 292313285 : return (HalfEdge *)((char *)this - sizeof(HalfEdge) * isRight);
143 : }
144 :
145 1050 : uint32_t HalfEdge::getIndex() const {
146 1050 : return ((uintptr_t)this >> 5) % 1024;
147 : }
148 :
149 27919396 : void HalfEdge::setOrigin(const Vertex *v) {
150 27919396 : origin = v->_origin;
151 27919396 : vertex = v->_uniqueIdx;
152 27919396 : }
153 :
154 26459228 : void HalfEdge::copyOrigin(const HalfEdge *e) {
155 26459228 : origin = e->origin;
156 26459228 : vertex = e->vertex;
157 26459228 : }
158 :
159 2357178 : HalfEdge *HalfEdge::getOriginNext() const {
160 2357178 : return _originNext;
161 : }
162 :
163 1881165 : HalfEdge *HalfEdge::getOriginPrev() const {
164 1881165 : return sym()->_leftNext;
165 : }
166 :
167 0 : HalfEdge *HalfEdge::getDestinationNext() const {
168 0 : return sym()->_originNext->sym();
169 : }
170 :
171 0 : HalfEdge *HalfEdge::getDestinationPrev() const {
172 0 : return _leftNext->sym();
173 : }
174 :
175 54483625 : HalfEdge *HalfEdge::getLeftLoopNext() const {
176 54483625 : return _leftNext;
177 : }
178 :
179 40088845 : HalfEdge *HalfEdge::getLeftLoopPrev() const {
180 40088845 : return _originNext->sym();
181 : }
182 :
183 0 : HalfEdge *HalfEdge::getRightLoopNext() const {
184 0 : return sym()->_leftNext->sym();
185 : }
186 :
187 0 : HalfEdge *HalfEdge::getRightLoopPrev() const {
188 0 : return sym()->_originNext;
189 : }
190 :
191 121790555 : const Vec2 &HalfEdge::getOrgVec() const {
192 121790555 : return origin;
193 : }
194 :
195 85291366 : const Vec2 &HalfEdge::getDstVec() const {
196 85291366 : return sym()->origin;
197 : }
198 :
199 0 : float HalfEdge::getLength() const {
200 0 : return origin.distance(sym()->origin);
201 : }
202 :
203 177685542 : Edge *HalfEdge::getEdge() const {
204 177685542 : return (Edge *)((char *)this - sizeof(HalfEdge) * edgeOffset);
205 : }
206 :
207 9590838 : bool HalfEdge::goesLeft() const {
208 9590838 : return ((Edge *)((char *)this - sizeof(HalfEdge) * edgeOffset))->inverted != static_cast<bool>(edgeOffset);
209 : }
210 :
211 81641690 : bool HalfEdge::goesRight() const {
212 81641690 : return ((Edge *)((char *)this - sizeof(HalfEdge) * edgeOffset))->inverted == static_cast<bool>(edgeOffset);
213 : }
214 :
215 8719214 : void HalfEdge::foreachOnFace(const Callback<void(HalfEdge &)> &cb) {
216 : auto e = this;
217 : do {
218 26081132 : cb(*e);
219 26067988 : e = e->_leftNext;
220 26067988 : } while( e != this );
221 8706070 : }
222 :
223 0 : void HalfEdge::foreachOnVertex(const Callback<void(HalfEdge &)> &cb) {
224 : auto e = this;
225 : do {
226 0 : cb(*e);
227 0 : e = e->_originNext;
228 0 : } while( e != this );
229 0 : }
230 :
231 0 : void HalfEdge::foreachOnFace(const Callback<void(const HalfEdge &)> &cb) const {
232 : auto e = this;
233 : do {
234 0 : cb(*e);
235 0 : e = e->_leftNext;
236 0 : } while( e != this );
237 0 : }
238 :
239 0 : void HalfEdge::foreachOnVertex(const Callback<void(const HalfEdge &)> &cb) const {
240 : auto e = this;
241 : do {
242 0 : cb(*e);
243 0 : e = e->_originNext;
244 0 : } while( e != this );
245 0 : }
246 :
247 0 : float HalfEdge::getDirection() const {
248 0 : return getEdge()->direction;
249 : }
250 :
251 18092797 : Edge::Edge() {
252 18122895 : left.isRight = -1;
253 18122895 : left.edgeOffset = 0;
254 18122895 : left._originNext = &left;
255 18122895 : left._leftNext = &right;
256 18122895 : right.isRight = 1;
257 18122895 : right.edgeOffset = 1;
258 18122895 : right._originNext = &right;
259 18122895 : right._leftNext = &left;
260 18122895 : }
261 :
262 20913585 : const Vec2 &Edge::getLeftVec() const {
263 20913585 : return inverted ? right.getOrgVec() : left.getOrgVec();
264 : }
265 :
266 18307128 : const Vec2 &Edge::getRightVec() const {
267 18307128 : return inverted ? left.getOrgVec() : right.getOrgVec();
268 : }
269 :
270 9333321 : const Vec2 &Edge::getOrgVec() const {
271 9333321 : return left.origin;
272 : }
273 :
274 9331025 : const Vec2 &Edge::getDstVec() const {
275 9331025 : return right.origin;
276 : }
277 :
278 0 : uint32_t Edge::getLeftOrg() const {
279 0 : return inverted ? right.vertex : left.vertex;
280 : }
281 :
282 71838871 : uint32_t Edge::getRightOrg() const {
283 71838871 : return inverted ? left.vertex : right.vertex;
284 : }
285 :
286 120760638 : void Edge::updateInfo() {
287 120760638 : if (std::isnan(direction)) {
288 18259756 : inverted = !EdgeGoesRight(&left);
289 36595270 : direction = EdgeDirection(getRightVec() - getLeftVec());
290 : }
291 120663478 : };
292 :
293 0 : int16_t Edge::getLeftWinding() const {
294 0 : return inverted ? right._realWinding : left._realWinding;
295 : }
296 :
297 0 : int16_t Edge::getRightWinding() const {
298 0 : return inverted ? left._realWinding : right._realWinding;
299 : }
300 :
301 128404 : ObjectAllocator::ObjectAllocator(memory::pool_t *pool) : _pool(pool), _vertexes(pool) {
302 128375 : _vertexes.reserve(VertexSetPrealloc);
303 128241 : }
304 :
305 18127044 : Edge *ObjectAllocator::allocEdge() {
306 : Edge *edge = nullptr;
307 18127044 : if (!_freeEdges) {
308 617138 : preallocateEdges(EdgeAllocBatch);
309 : }
310 :
311 18126381 : auto node = _freeEdges;
312 18126381 : _freeEdges = (Edge *)node->node;
313 18126381 : edge = new (node) Edge();
314 :
315 18129706 : return edge;
316 : }
317 :
318 9650888 : Vertex *ObjectAllocator::allocVertex() {
319 9650888 : Vertex *vertex = nullptr;
320 9650888 : if (!_freeVertexes) {
321 362577 : preallocateVertexes(VertexAllocBatch);
322 : }
323 :
324 9650543 : auto node = _freeVertexes;
325 9650543 : _freeVertexes = (Vertex *)node->_edge;
326 9650543 : vertex = new (node) Vertex();
327 9607122 : vertex->_uniqueIdx = _vertexes.size();
328 :
329 9572640 : _vertexes.emplace_back(vertex);
330 :
331 9578921 : return vertex;
332 : }
333 :
334 113432 : FaceEdge *ObjectAllocator::allocFaceEdge() {
335 : FaceEdge *face = nullptr;
336 113432 : if (!_freeFaces) {
337 7079 : preallocateFaceEdges(VertexAllocBatch);
338 : }
339 :
340 113416 : auto node = _freeFaces;
341 113416 : _freeFaces = node->_next;
342 113416 : face = new (node) FaceEdge();
343 113076 : return face;
344 : }
345 :
346 445925 : void ObjectAllocator::releaseEdge(Edge *eDel) {
347 445925 : removeEdgeFromVec(_edgesOfInterests, &eDel->left);
348 445152 : removeEdgeFromVec(_edgesOfInterests, &eDel->right);
349 445139 : removeEdgeFromVec(_faceEdges, &eDel->left);
350 445214 : removeEdgeFromVec(_faceEdges, &eDel->right);
351 :
352 445250 : auto lVertex = _vertexes[eDel->left.vertex];
353 444814 : if (lVertex && lVertex->_edge == &eDel->left) {
354 159729 : lVertex->_edge = eDel->left._originNext;
355 : }
356 :
357 444814 : auto rVertex = _vertexes[eDel->right.vertex];
358 444640 : if (rVertex && rVertex->_edge == &eDel->right) {
359 853 : rVertex->_edge = eDel->right._originNext;
360 : }
361 :
362 444640 : if (eDel->node) {
363 0 : const_cast<EdgeDictNode *>(eDel->node)->edge = nullptr;
364 : }
365 :
366 444640 : eDel->~Edge();
367 :
368 444640 : eDel->node = (EdgeDictNode *)_freeEdges;
369 444640 : eDel->invalidated = true;
370 444640 : _freeEdges = eDel;
371 444640 : }
372 :
373 0 : void ObjectAllocator::releaseVertex(uint32_t vDelId, uint32_t vNewId) {
374 0 : auto it1 = _vertexes[vDelId];
375 0 : auto it2 = _vertexes[vNewId];
376 :
377 0 : if (it1 && it2) {
378 : auto vDel = it1;
379 :
380 0 : vDel->removeFromList(it2);
381 0 : vDel->~Vertex();
382 0 : _vertexes[vDelId] = nullptr;
383 :
384 0 : vDel->_edge = (HalfEdge *)_freeVertexes;
385 0 : _freeVertexes = vDel;
386 : }
387 0 : }
388 :
389 709350 : void ObjectAllocator::releaseVertex(Vertex *vDel) {
390 709350 : if (vDel) {
391 : if constexpr (TessTypesVerbose != VerboseFlag::None) {
392 : std::cout << "releaseVertex: " << vDel->_uniqueIdx << ": " << vDel->_exportIdx << "\n";
393 : }
394 707750 : if (vDel->_exportIdx != maxOf<uint32_t>()) {
395 0 : _exportVertexes[vDel->_exportIdx] = nullptr;
396 : }
397 :
398 707739 : _vertexes[vDel->_uniqueIdx] = nullptr;
399 707666 : vDel->~Vertex();
400 :
401 707666 : vDel->_edge = (HalfEdge *)_freeVertexes;
402 707666 : _freeVertexes = vDel;
403 : }
404 709266 : }
405 :
406 180602 : void ObjectAllocator::trimVertexes() {
407 : size_t offset = 0;
408 186084 : for (auto it = _vertexes.rbegin(); it != _vertexes.rend(); ++ it) {
409 184651 : if (*it == nullptr) {
410 5482 : ++ offset;
411 : } else {
412 : break;
413 : }
414 : }
415 :
416 180033 : if (offset > 0) {
417 2930 : _vertexes.resize(_vertexes.size() - offset);
418 : }
419 180032 : }
420 :
421 362513 : void ObjectAllocator::preallocateVertexes(uint32_t n) {
422 362513 : if (auto vertsMem = (Vertex *)memory::pool::palloc(_pool, sizeof(Vertex) * n)) {
423 11944901 : for (uint32_t i = 0; i < n; ++ i) {
424 11582880 : auto mem = vertsMem + i;
425 11582880 : mem->_edge = (HalfEdge *)(mem + 1);
426 : }
427 :
428 362021 : Vertex *vtmp = _freeVertexes;
429 362021 : _freeVertexes = vertsMem;
430 362021 : (vertsMem + n - 1)->_edge = (HalfEdge *)vtmp;
431 : }
432 :
433 362021 : _vertexes.reserve(n);
434 362207 : _exportVertexes.reserve(n);
435 362205 : }
436 :
437 617163 : void ObjectAllocator::preallocateEdges(uint32_t n) {
438 617163 : if (auto edgesMem = (Edge *)memory::pool::palloc(_pool, sizeof(Edge) * n)) {
439 20340266 : for (uint32_t i = 0; i < n; ++ i) {
440 19723808 : auto mem = edgesMem + i;
441 19723808 : mem->node = (EdgeDictNode *)(mem + 1);
442 : }
443 :
444 616458 : Edge *etmp = _freeEdges;
445 616458 : _freeEdges = edgesMem;
446 616458 : (edgesMem + n - 1)-> node = (EdgeDictNode *)(etmp);
447 : }
448 616458 : }
449 :
450 7075 : void ObjectAllocator::preallocateFaceEdges(uint32_t n) {
451 7075 : if (auto edgesMem = (FaceEdge *)memory::pool::palloc(_pool, sizeof(FaceEdge) * n)) {
452 232659 : for (uint32_t i = 0; i < n; ++ i) {
453 225600 : auto mem = edgesMem + i;
454 225600 : mem->_next = (FaceEdge *)(mem + 1);
455 : }
456 :
457 7059 : FaceEdge *etmp = _freeFaces;
458 7059 : _freeFaces = edgesMem;
459 7059 : (edgesMem + n - 1)->_next = (FaceEdge *)(etmp);
460 : }
461 7059 : }
462 :
463 1780081 : void ObjectAllocator::removeEdgeFromVec(memory::vector<HalfEdge *> &vec, HalfEdge *e) {
464 1780081 : auto eOIt = std::find(vec.begin(), vec.end(), e);
465 1779270 : if (eOIt != vec.end()) {
466 65 : *eOIt = nullptr;
467 : }
468 1778653 : }
469 :
470 128804 : VertexPriorityQueue::Heap::Heap(memory::pool_t *p, uint32_t s) : max(s), pool(p) {
471 128804 : nodes = (Node *)memory::pool::palloc(pool, (max + 1) * sizeof(Node));
472 128670 : handles = (Elem *)memory::pool::palloc(pool, (max + 1) * sizeof(Elem));
473 :
474 128710 : nodes[1].handle = 1; /* so that Minimum() returns NULL */
475 128710 : handles[1].key = nullptr;
476 128710 : }
477 :
478 128734 : VertexPriorityQueue::Heap::~Heap() {
479 128734 : memory::pool::free(pool, nodes, (max + 1) * sizeof(Node));
480 128744 : memory::pool::free(pool, handles, (max + 1) * sizeof(Elem));
481 128761 : }
482 :
483 128876 : void VertexPriorityQueue::Heap::init() {
484 : /* This method of building a heap is O(n), rather than O(n lg n). */
485 :
486 128876 : for (uint32_t i = size; i >= 1; --i) {
487 0 : floatDown( i );
488 : }
489 :
490 128876 : initialized = true;
491 128876 : }
492 :
493 : /* returns INV_HANDLE iff out of memory */
494 82426 : VertexPriorityQueue::Handle VertexPriorityQueue::Heap::insert(Key keyNew) {
495 : uint32_t curr;
496 : Handle free;
497 :
498 82426 : curr = ++size;
499 82426 : if ((curr * 2) > max) {
500 0 : Node *saveNodes = nodes;
501 0 : Elem *saveHandles = handles;
502 :
503 : // If the heap overflows, double its size.
504 : auto tmpSize = max;
505 :
506 0 : max <<= 1;
507 :
508 0 : nodes = (Node*) memory::pool::palloc(pool, ((max + 1) * sizeof(Node)));
509 0 : if (nodes != NULL) {
510 0 : memcpy(nodes, saveNodes, ((tmpSize + 1) * sizeof(Node)));
511 : }
512 :
513 0 : handles = (Elem*) memory::pool::palloc(pool, ((max + 1) * sizeof(Elem)));
514 0 : if (handles != NULL) {
515 0 : memcpy(handles, saveHandles, (size_t) ((tmpSize + 1) * sizeof(Elem)));
516 : }
517 :
518 0 : memory::pool::free(pool, saveNodes, (tmpSize + 1) * sizeof(Node));
519 0 : memory::pool::free(pool, saveHandles, (tmpSize + 1) * sizeof(Elem));
520 : }
521 :
522 82426 : if (freeList == 0) {
523 39060 : free = curr;
524 : } else {
525 : free = freeList;
526 43366 : freeList = handles[free].node;
527 : }
528 :
529 82426 : nodes[curr].handle = free;
530 82426 : handles[free].node = curr;
531 82426 : handles[free].key = keyNew;
532 :
533 82426 : if (initialized) {
534 82422 : floatUp(curr);
535 : }
536 82431 : SPASSERT(free != InvalidHandle, "pqHeapInsert");
537 82431 : return free;
538 : }
539 :
540 : /* really pqHeapExtractMin */
541 211100 : VertexPriorityQueue::Key VertexPriorityQueue::Heap::extractMin() {
542 211100 : Node *n = nodes;
543 211100 : Elem *h = handles;
544 211100 : Handle hMin = n[1].handle;
545 211100 : Key min = h[hMin].key;
546 :
547 211100 : if (size > 0) {
548 82409 : n[1].handle = n[size].handle;
549 82409 : h[n[1].handle].node = 1;
550 :
551 82409 : h[hMin].key = NULL;
552 82409 : h[hMin].node = freeList;
553 82409 : freeList = hMin;
554 :
555 82409 : if (--size > 0) {
556 21354 : floatDown(1);
557 : }
558 : }
559 211100 : if (min) {
560 82408 : min->_queueHandle = maxOf<QueueHandle>();
561 : }
562 211097 : return min;
563 : }
564 :
565 : /* really pqHeapDelete */
566 0 : void VertexPriorityQueue::Heap::remove(Handle hCurr) {
567 0 : Node *n = nodes;
568 0 : Elem *h = handles;
569 : uint32_t curr;
570 :
571 0 : SPASSERT( hCurr >= 1 && hCurr <= Handle(max) && h[hCurr].key != nullptr, "pqHeapDelete");
572 :
573 0 : curr = h[hCurr].node;
574 0 : n[curr].handle = n[size].handle;
575 0 : h[n[curr].handle].node = curr;
576 :
577 0 : if (curr <= --size) {
578 0 : if (curr <= 1 || VertLeq(h[n[curr >> 1].handle].key, h[n[curr].handle].key)) {
579 0 : floatDown(curr);
580 : } else {
581 0 : floatUp(curr);
582 : }
583 : }
584 0 : h[hCurr].key = NULL;
585 0 : h[hCurr].node = freeList;
586 0 : freeList = hCurr;
587 0 : }
588 :
589 :
590 21354 : void VertexPriorityQueue::Heap::floatDown(int curr) {
591 21354 : Node *n = nodes;
592 21354 : Elem *h = handles;
593 : Handle hCurr, hChild;
594 : uint32_t child;
595 :
596 21354 : hCurr = n[curr].handle;
597 : for (;;) {
598 23804 : child = curr << 1;
599 23804 : if (child < size && VertLeq(h[n[child + 1].handle].key, h[n[child].handle].key)) {
600 : ++child;
601 : }
602 :
603 23804 : SPASSERT(child <= this->max, "FloatDown");
604 :
605 23804 : hChild = n[child].handle;
606 23804 : if (child > size || VertLeq(h[hCurr].key, h[hChild].key)) {
607 21354 : n[curr].handle = hCurr;
608 21354 : h[hCurr].node = curr;
609 : break;
610 : }
611 2450 : n[curr].handle = hChild;
612 2450 : h[hChild].node = curr;
613 2450 : curr = child;
614 : }
615 21354 : }
616 :
617 82424 : void VertexPriorityQueue::Heap::floatUp(int curr) {
618 82424 : Node *n = nodes;
619 82424 : Elem *h = handles;
620 : Handle hCurr, hParent;
621 : uint32_t parent;
622 :
623 82424 : hCurr = n[curr].handle;
624 : for (;;) {
625 94073 : parent = curr >> 1;
626 94073 : hParent = n[parent].handle;
627 94073 : if (parent == 0 || VertLeq(h[hParent].key, h[hCurr].key)) {
628 82424 : n[curr].handle = hCurr;
629 82424 : h[hCurr].node = curr;
630 : break;
631 : }
632 11649 : n[curr].handle = hParent;
633 11649 : h[hParent].node = curr;
634 : curr = parent;
635 : }
636 82424 : }
637 :
638 128888 : VertexPriorityQueue::VertexPriorityQueue(memory::pool_t *p, const memory::vector<Vertex *> &vec)
639 128888 : : heap(p, vec.size()), max(vec.size()), pool(p) {
640 128697 : keys = (Key*) memory::pool::palloc(p, max * sizeof(Key));
641 :
642 9719614 : for (auto &v : vec) {
643 9590368 : if (v) {
644 9430816 : v->_queueHandle = insert(v);
645 9431346 : if (v->_queueHandle == InvalidHandle) {
646 0 : return;
647 : }
648 : }
649 : }
650 :
651 128888 : if (init()) {
652 128948 : initialized = true;
653 : }
654 0 : }
655 :
656 128713 : VertexPriorityQueue::~VertexPriorityQueue() {
657 128713 : memory::pool::free(pool, keys, max * sizeof(Key));
658 128730 : }
659 :
660 :
661 : #define LT(x,y) (! VertLeq(y,x))
662 : #define GT(x,y) (! VertLeq(x,y))
663 : #define KeySwap(a,b) if(1){Key *tmp = *a; *a = *b; *b = tmp;}else
664 :
665 128899 : bool VertexPriorityQueue::init() {
666 : Key **p, **r, **i, **j, *piv;
667 : struct {
668 : Key **p, **r;
669 : } Stack[50], *top = Stack;
670 : unsigned int seed = 2016473283;
671 :
672 : /* Create an array of indirect pointers to the keys, so that we
673 : * the handles we have returned are still valid. */
674 : /*
675 : pq->order = (PQkey **)memAlloc( (size_t)
676 : (pq->size * sizeof(pq->order[0])) );
677 : */
678 128899 : order = (Key**) memory::pool::palloc(pool, size_t((size + 1) * sizeof(Key*)));
679 :
680 : p = order;
681 128823 : r = p + size - 1;
682 9580064 : for (piv = keys, i = p; i <= r; ++piv, ++i) {
683 9451241 : *i = piv;
684 : }
685 :
686 : /* Sort the indirect pointers in descending order,
687 : * using randomized Quicksort */
688 128823 : top->p = p;
689 128823 : top->r = r;
690 : ++top;
691 1723974 : while (--top >= Stack) {
692 1595151 : p = top->p;
693 1595151 : r = top->r;
694 3062539 : while (r > p + 10) {
695 1467388 : seed = seed * 1539415821 + 1;
696 1467388 : i = p + seed % (r - p + 1);
697 1467388 : piv = *i;
698 1467388 : *i = *p;
699 1467388 : *p = piv;
700 1467388 : i = p - 1;
701 1467388 : j = r + 1;
702 : do {
703 : do {
704 25065100 : ++i;
705 25065100 : } while (GT(**i, *piv));
706 : do {
707 25893817 : --j;
708 25893817 : } while (LT(**j, *piv));
709 10241130 : KeySwap(i, j);
710 10241130 : } while (i < j);
711 1467388 : KeySwap(i, j); /* Undo last swap */
712 1467388 : if (i - p < r - j) {
713 738393 : top->p = j + 1;
714 738393 : top->r = r;
715 738393 : ++top;
716 : r = i - 1;
717 : } else {
718 728995 : top->p = p;
719 728995 : top->r = i - 1;
720 728995 : ++top;
721 : p = j + 1;
722 : }
723 : }
724 : /* Insertion sort small lists */
725 9388158 : for (i = p + 1; i <= r; ++i) {
726 7793007 : piv = *i;
727 24195776 : for (j = i; j > p && LT(**(j - 1), *piv); --j) {
728 16402769 : *j = *(j - 1);
729 : }
730 7793007 : *j = piv;
731 : }
732 : }
733 128823 : max = size;
734 128823 : initialized = true;
735 :
736 128823 : heap.init();
737 :
738 : #ifndef NDEBUG
739 128875 : p = order;
740 128875 : r = p + size - 1;
741 9448573 : for (i = p; i < r; ++i) {
742 9319578 : SPASSERT( VertLeq( **(i+1), **i ), "pqInit");
743 : }
744 : #endif
745 :
746 128935 : return 1;
747 : }
748 :
749 : #undef LT
750 : #undef GT
751 : #undef KeySwap
752 :
753 0 : bool VertexPriorityQueue::empty() const {
754 0 : return size == 0 && heap.empty();
755 : }
756 :
757 9513217 : VertexPriorityQueue::Handle VertexPriorityQueue::insert(Key keyNew) {
758 : int curr;
759 :
760 9513217 : if (initialized) {
761 82428 : return heap.insert(keyNew);
762 : }
763 9430789 : curr = size;
764 9430789 : if( ++ size >= max ) {
765 82973 : Key *saveKey = keys;
766 : // If the heap overflows, double its size.
767 : auto tmpSize = max;
768 82973 : max <<= 1;
769 82973 : keys = (Key*) memory::pool::palloc(pool, max * sizeof(Key));
770 82968 : if (keys) {
771 82968 : memcpy(keys, saveKey, (size_t) (tmpSize * sizeof(Key)));
772 : }
773 :
774 82968 : memory::pool::free(pool, saveKey, tmpSize * sizeof(Key));
775 : }
776 9430786 : SPASSERT(curr != InvalidHandle, "pqInsert");
777 9430786 : keys[curr] = keyNew;
778 :
779 : /* Negative handles index the sorted array. */
780 9430786 : return -(curr+1);
781 : }
782 :
783 278620 : void VertexPriorityQueue::remove(Handle curr) {
784 278620 : if (curr >= 0) {
785 0 : heap.remove(curr);
786 0 : return;
787 : }
788 278620 : curr = -(curr + 1);
789 278620 : SPASSERT(curr < Handle(max) && keys[curr] != nullptr, "pqDelete");
790 :
791 278620 : keys[curr] = nullptr;
792 348232 : while (size > 0 && *(order[size - 1]) == nullptr) {
793 69612 : --size;
794 : }
795 : }
796 :
797 9258541 : VertexPriorityQueue::Key VertexPriorityQueue::extractMin() {
798 : Key sortMin, heapMin;
799 :
800 9258541 : if (size == 0) {
801 128678 : return heap.extractMin();
802 : }
803 9129863 : sortMin = *(order[size - 1]);
804 9129863 : if (!heap.empty()) {
805 254871 : heapMin = heap.getMin();
806 : if (VertLeq(heapMin, sortMin)) {
807 82406 : return heap.extractMin();
808 : }
809 : }
810 : do {
811 9222286 : --size;
812 9222286 : } while (size > 0 && *(order[size - 1]) == NULL);
813 9047457 : sortMin->_queueHandle = maxOf<QueueHandle>();
814 9039735 : return sortMin;
815 : }
816 :
817 9132747 : VertexPriorityQueue::Key VertexPriorityQueue::getMin() const {
818 : Key sortMin, heapMin;
819 :
820 9132747 : if (size == 0) {
821 128075 : return heap.getMin();
822 : }
823 9004672 : sortMin = *(order[size - 1]);
824 9004672 : if (!heap.empty()) {
825 193819 : heapMin = heap.getMin();
826 : if (VertLeq(heapMin, sortMin)) {
827 44343 : return heapMin;
828 : }
829 : }
830 : return sortMin;
831 : }
832 :
833 128780 : EdgeDict::EdgeDict(memory::pool_t *p, uint32_t size) : nodes(p), pool(p) {
834 128876 : nodes.reserve(size);
835 128858 : nodes.set_memory_persistent(true);
836 128869 : }
837 :
838 9247375 : const EdgeDictNode * EdgeDict::push(Edge *edge, int16_t windingAbove) {
839 : if constexpr (DictDebug) {
840 : std::cout << "\t\tDict push: " << *edge << "\n";
841 : }
842 :
843 : const EdgeDictNode *ret;
844 9247375 : auto &dst = edge->getDstVec();
845 9249269 : auto &org = edge->getOrgVec();
846 :
847 9251190 : if (org == event) {
848 4781387 : auto norm = dst - event;
849 4780115 : ret = & (*nodes.emplace(EdgeDictNode{
850 : event, norm,
851 4799155 : Vec4(event.x, event.y, dst.x, dst.y),
852 : edge, windingAbove,
853 4787163 : std::abs(norm.x) > std::numeric_limits<float>::epsilon()
854 4791493 : }).first);
855 4506891 : } else if (dst == event) {
856 4508837 : auto norm = org - event;
857 4507490 : ret = & (*nodes.emplace(EdgeDictNode{
858 : event, norm,
859 4526563 : Vec4(event.x, event.y, org.x, org.y),
860 : edge, windingAbove,
861 4516794 : std::abs(norm.x) > std::numeric_limits<float>::epsilon()
862 4518367 : }).first);
863 : } else {
864 : ret = nullptr;
865 0 : std::cout << "Fail to add edge: " << *edge << " for " << event << "\n";
866 : }
867 :
868 : /*for (auto &it : nodes) {
869 : std::cout << "Edge: " << it.org << " - " << Vec2(it.value.z, it.value.w)
870 : << " - " << Vec2(it.value.x, it.value.y) << " - " << it.windingAbove << "\n";
871 : }*/
872 :
873 9287605 : return ret;
874 : }
875 :
876 9217373 : void EdgeDict::pop(const EdgeDictNode *node) {
877 : if constexpr (DictDebug) {
878 : std::cout << "\t\tDict pop: " << *node->edge << "\n";
879 : for (auto &it : nodes) {
880 : std::cout << "\t\t\t\tpop: " << it << "\n";
881 : }
882 : }
883 :
884 9217373 : auto it = nodes.lower_bound(*node);
885 9184279 : auto end = nodes.end();
886 10558930 : while (it != end && *it <= *node && &(*it) != node) {
887 1369102 : ++ it;
888 : }
889 9171142 : if (it != end && &(*it) == node) {
890 9167429 : it->edge->node = nullptr;
891 9164612 : nodes.erase(it);
892 : }
893 9149680 : }
894 :
895 8874329 : void EdgeDict::update(Vertex *v, float tolerance) {
896 : if constexpr (DictDebug) {
897 : for (auto &it : nodes) {
898 : std::cout << "\t\t\t\tupdate: " << it << "\n";
899 : }
900 : }
901 :
902 8874329 : event = v->_origin;
903 8874329 : auto it = nodes.begin();
904 77821278 : while (it != nodes.end()) {
905 69020289 : auto &n = *it;
906 68712324 : if (it->edge->getRightOrg() == v->_uniqueIdx) {
907 : //if (n.helper.type == VertexType::Merge) {
908 9259196 : n.value.x = n.value.z;
909 9259196 : n.value.y = n.value.w;
910 : /*} else {
911 : if constexpr (DictDebug) {
912 : std::cout << "\t\t\tDict pop (v): " << *it->edge << "\n";
913 : }
914 : it->edge->node = nullptr;
915 : it = nodes.erase(it);
916 : continue;
917 : }*/
918 59829021 : } else if (n.horizontal) {
919 59825784 : const float tValue = (event.x - n.org.x) / (n.norm.x);
920 : // std::cout << "\t\t\t: " << *it->edge << " " << tValue << "\n";
921 59825784 : if (tValue < 0.0f || tValue > 1.0f) {
922 : if constexpr (DictDebug) {
923 : std::cout << "\t\t\tDict pop (t): " << *it->edge << "\n";
924 : }
925 60199 : it->edge->node = nullptr;
926 60198 : it = nodes.erase(it);
927 70157 : continue;
928 : } else {
929 59765585 : n.value.x = n.org.x + n.norm.x * tValue;
930 59765585 : n.value.y = n.org.y + n.norm.y * tValue;
931 : }
932 : } else {
933 3237 : const float sValue = (event.y - n.org.y) / (n.norm.y);
934 : // std::cout << "\t\t\t: " << *it->edge << " " << sValue << "\n";
935 3237 : if (sValue < 0.0f || sValue > 1.0f) {
936 : if constexpr (DictDebug) {
937 : std::cout << "\t\t\tDict pop (s): " << *it->edge << "\n";
938 : }
939 2772 : it->edge->node = nullptr;
940 2773 : it = nodes.erase(it);
941 2771 : continue;
942 : } else {
943 465 : n.value.x = n.org.x + n.norm.x * sValue;
944 465 : n.value.y = n.org.y + n.norm.y * sValue;
945 : }
946 : }
947 :
948 69025246 : auto curr = n.current();
949 69237974 : auto dst = n.dst();
950 69334094 : if (curr.x == dst.x && std::abs(curr.y - dst.y) < tolerance) {
951 12565039 : if (n.value.y < event.y) {
952 : if constexpr (DictDebug) {
953 : std::cout << "\t\t\tDict pop (y): " << *it->edge << "\n";
954 : }
955 7195 : it->edge->node = nullptr;
956 7197 : it = nodes.erase(it);
957 7189 : continue;
958 : }
959 : }
960 :
961 69313511 : ++ it;
962 : }
963 8924981 : }
964 :
965 8925396 : const EdgeDictNode * EdgeDict::checkForIntersects(Vertex *v, Vec2 &intersectPoint, IntersectionEvent &ev, float tolerance) const {
966 8925396 : if (nodes.empty()) {
967 : return nullptr;
968 : }
969 :
970 8769788 : auto &org = v->_origin;
971 :
972 : if constexpr (IntersectDebug) {
973 : std::cout << "\t\t\t\tcheckForIntersects: " << *v << "\n";
974 : }
975 :
976 78447868 : for (auto &n : nodes) {
977 69099624 : auto nCurr = n.current();
978 69429510 : auto nDst = n.dst();
979 :
980 : if constexpr (IntersectDebug) {
981 : std::cout << "\t\t\t\t\t: " << *n.edge << "\n";
982 : }
983 :
984 69676473 : if (VertEq(nCurr, org, tolerance) && !VertEq(n.org, org, tolerance)) {
985 9321821 : if (VertEq(nCurr, nDst, tolerance)) {
986 9321217 : continue; // no intersection, just line end
987 : }
988 604 : intersectPoint = event;
989 604 : ev = IntersectionEvent::EventIsIntersection;
990 604 : return &n;
991 : }
992 : }
993 :
994 8807107 : return nullptr;
995 : }
996 :
997 9413359 : const EdgeDictNode * EdgeDict::checkForIntersects(HalfEdge *edge, Vec2 &intersectPoint, IntersectionEvent &ev, float tolerance) const {
998 9413359 : if (nodes.empty()) {
999 : return nullptr;
1000 : }
1001 :
1002 9102096 : auto &org = edge->getOrgVec(); // == event
1003 9105414 : auto &dst = edge->getDstVec();
1004 :
1005 9109314 : auto simdVec1 = simd::load(org.x, org.y, dst.x, dst.y);
1006 :
1007 : if constexpr (IntersectDebug) {
1008 : std::cout << "\t\t\t\tcheckForIntersects: " << *edge << "\n";
1009 : }
1010 :
1011 81284520 : for (auto &n : nodes) {
1012 71606287 : auto nCurr = n.current();
1013 71921978 : auto nDst = n.dst();
1014 : if constexpr (IntersectDebug) {
1015 : std::cout << "\t\t\t\t\t: " << *n.edge << "\n";
1016 : }
1017 : // overlap check should be made in mergeVertexes
1018 : // so, should never happen
1019 144095064 : if (VertEq(n.org, org, tolerance) || VertEq(nDst, org, tolerance)) {
1020 9265996 : continue; // common org, not interested
1021 64410201 : } else if (VertEq(nCurr, org, tolerance)) {
1022 0 : if (VertEq(nCurr, nDst, tolerance)) {
1023 0 : continue; // no intersection, just line end
1024 : }
1025 0 : intersectPoint = event;
1026 0 : ev = IntersectionEvent::EventIsIntersection;
1027 82664 : return &n;
1028 : }
1029 :
1030 64433121 : if (VertEq(dst, nDst, tolerance)) {
1031 1449410 : continue; // common dst
1032 : }
1033 :
1034 : simd::f32x4 intersect;
1035 : if (simd::isVec2BboxIntersects(simdVec1, simd::load(&n.value.x), intersect)) {
1036 : Vec4 isect; simd::store(&isect.x, intersect);
1037 31829677 : if (VertEq(nCurr, nDst, tolerance)) {
1038 55096 : if (std::abs(isect.x) < tolerance) {
1039 349 : if (std::abs(isect.y) < tolerance) {
1040 0 : intersectPoint = nCurr;
1041 0 : ev = IntersectionEvent::EdgeConnection1; // n ends on edge;
1042 0 : return &n;
1043 : }
1044 : } else {
1045 54729 : auto S = (nDst.x - org.x) / (isect.x);
1046 54729 : if (S >= 0.0f && S <= 1.0f) {
1047 54713 : auto y = org.y + S * isect.y;
1048 54713 : if (std::abs(nDst.y - y) <= tolerance) {
1049 0 : intersectPoint = nCurr;
1050 0 : ev = IntersectionEvent::EdgeConnection1; // n ends on edge;
1051 0 : return &n;
1052 : }
1053 : }
1054 : }
1055 : continue;
1056 55078 : }
1057 :
1058 31774581 : const float denom = isect.w * isect.x - isect.z * isect.y; // crossProduct2Vector(A, B, C, D);
1059 31774581 : if (denom != 0.0f) {
1060 30360811 : const auto CAx = org.x - n.value.x;
1061 30360811 : const auto CAy = org.y - n.value.y;
1062 :
1063 30360811 : auto S = (CAy * isect.z - CAx * isect.w) / denom;
1064 30360811 : auto T = (CAy * isect.x - CAx * isect.y) / denom;
1065 :
1066 : //if (S > 0.5f) { S = 1.0f - S; }
1067 : //if (T > 0.5f) { T = 1.0f - T; }
1068 :
1069 30360811 : if (S >= 0.0f && S <= 1.0f && T >= 0.0f && T <= 1.0f) {
1070 82666 : intersectPoint = Vec2(org.x + S * isect.x, org.y + S * isect.y);
1071 82667 : if (VertEq(intersectPoint, dst, tolerance)) {
1072 134 : ev = IntersectionEvent::EdgeConnection2; // edge ends on n;
1073 82530 : } else if (VertEq(intersectPoint, nDst, tolerance)) {
1074 107 : intersectPoint = nDst;
1075 107 : ev = IntersectionEvent::EdgeConnection1; // n ends on edge;
1076 : } else {
1077 82423 : ev = IntersectionEvent::Regular;
1078 : }
1079 82664 : return &n;
1080 : }
1081 : }
1082 : }
1083 : }
1084 :
1085 9043131 : return nullptr;
1086 : }
1087 :
1088 991510 : const EdgeDictNode * EdgeDict::getEdgeBelow(const Edge *e) const {
1089 : if constexpr (DictDebug) {
1090 : auto nIt = nodes.begin();
1091 : while (nIt != nodes.end()) {
1092 : std::cout << "\t\t\t\t" << (void *)nIt._node << " " << *nIt << "\n";
1093 : ++ nIt;
1094 : }
1095 : }
1096 :
1097 991510 : if (nodes.empty()) {
1098 : return nullptr;
1099 : }
1100 :
1101 848059 : auto it = nodes.lower_bound(*e); // first not less then e
1102 847713 : if (it == nodes.begin()) {
1103 : // first edge in dict greater or equal then e, no edges below
1104 : return nullptr;
1105 : } else {
1106 773826 : -- it;
1107 773897 : while (it != nodes.begin() && it->current() == event) {
1108 0 : -- it;
1109 : }
1110 : // edge before it is less then e
1111 774012 : return &(*it);
1112 : }
1113 : }
1114 :
1115 4453512 : const EdgeDictNode * EdgeDict::getEdgeBelow(const Vec2 &vec, uint32_t vertex) const {
1116 : if constexpr (DictDebug) {
1117 : for (auto &it : nodes) {
1118 : std::cout << "\t\t\t\t" << it << "\n";
1119 : }
1120 : }
1121 :
1122 4453512 : if (nodes.empty()) {
1123 : return nullptr;
1124 : }
1125 :
1126 4448645 : auto it = nodes.lower_bound(vec); // first not less then e
1127 4440681 : if (it == nodes.begin()) {
1128 : // first edge in dict greater or equal then e, no edges below
1129 : return nullptr;
1130 : } else {
1131 4438020 : -- it;
1132 4440804 : while (it != nodes.begin() && (it->edge->getRightOrg() == vertex || it->current() == vec)) {
1133 4 : -- it;
1134 : }
1135 : // edge before it is less then e
1136 4447359 : return &(*it);
1137 : }
1138 : }
1139 :
1140 0 : std::ostream &operator<<(std::ostream &out, const Vertex &v) {
1141 0 : switch (VerboseFlag(out.iword( TessVerboseInfo ))) {
1142 0 : case VerboseFlag::None:
1143 0 : out << "Vertex (" << v._uniqueIdx << ") : " << v._origin;
1144 0 : break;
1145 0 : case VerboseFlag::General:
1146 0 : out << "Vertex (" << v._uniqueIdx << ") : " << v._origin;
1147 0 : break;
1148 0 : case VerboseFlag::Full:
1149 0 : out << "Vertex (" << v._uniqueIdx << ") : " << v._origin << "\n";
1150 0 : v.foreach([&] (const HalfEdge &e) {
1151 0 : Vec2 orgVec = e.origin;
1152 0 : Vec2 dstVec = e.sym()->origin;
1153 0 : uint32_t orgIdx = e.vertex;
1154 0 : uint32_t dstIdx = e.sym()->vertex;
1155 :
1156 0 : out << "\tEdge (" << e.getIndex() << ":" << e.sym()->getIndex() << ") : " << orgVec << " - " << dstVec << "\n";
1157 0 : out << "\t\tDir: (" << e.getIndex() << "; org: " << orgIdx << "; left: " << e._leftNext->getIndex()
1158 0 : << "; ccw: " << e._originNext->getIndex() << ")\n";
1159 0 : out << "\t\tSym: (" << e.sym()->getIndex() << "; org: " << dstIdx << "; left: " << e.sym()->_leftNext->getIndex()
1160 0 : << "; ccw: " << e.sym()->_originNext->getIndex() << ")\n";
1161 0 : });
1162 0 : break;
1163 : }
1164 :
1165 0 : return out;
1166 : }
1167 :
1168 525 : std::ostream &operator<<(std::ostream &out, const HalfEdge &e) {
1169 525 : Vec2 orgVec = e.origin;
1170 525 : Vec2 dstVec = e.sym()->origin;
1171 525 : uint32_t orgIdx = e.vertex;
1172 525 : uint32_t dstIdx = e.sym()->vertex;
1173 :
1174 525 : switch (VerboseFlag(out.iword( TessVerboseInfo ))) {
1175 525 : case VerboseFlag::None:
1176 525 : out << "Edge (" << e.getIndex() << ":" << e.sym()->getIndex() << ") : " << orgVec << " - " << dstVec
1177 525 : << "; " << e.vertex << " - " << e.sym()->vertex;
1178 : break;
1179 0 : case VerboseFlag::General:
1180 0 : out << "Edge (" << e.getIndex() << ":" << e.sym()->getIndex() << ") : " << orgVec << " - " << dstVec
1181 0 : << "; " << e.vertex << " - " << e.sym()->vertex
1182 0 : << " winding: " << e._realWinding << ":" << e._winding << ";";
1183 0 : if (e.goesLeft()) {
1184 0 : out << " goes left; ";
1185 0 : } else if (e.goesRight()) {
1186 0 : out << " goes right; ";
1187 : } else {
1188 0 : out << " unknown direction; ";
1189 : }
1190 0 : out << (void *)&e;
1191 : break;
1192 0 : case VerboseFlag::Full:
1193 0 : out << "Edge (" << e.getIndex() << ":" << e.sym()->getIndex() << ") : " << orgVec << " - " << dstVec
1194 0 : << "; " << e.vertex << " - " << e.sym()->vertex
1195 0 : << " winding: " << e._realWinding << ":" << e._winding << ";\n";
1196 0 : out << "\tDir: (" << e.getIndex() << "; org: " << orgIdx << "; left: " << e._leftNext->getIndex()
1197 0 : << "; ccw: " << e._originNext->getIndex() << ")";
1198 0 : if (e.goesLeft()) {
1199 0 : out << " goes left;";
1200 0 : } else if (e.goesRight()) {
1201 0 : out << " goes right;";
1202 : } else {
1203 0 : out << " unknown direction;";
1204 : }
1205 0 : out << "\n";
1206 0 : out << "\tSym: (" << e.sym()->getIndex() << "; org: " << dstIdx << "; left: " << e.sym()->_leftNext->getIndex()
1207 0 : << "; ccw: " << e.sym()->_originNext->getIndex() << ")";
1208 0 : if (e.sym()->goesLeft()) {
1209 0 : out << " goes left; ";
1210 0 : } else if (e.sym()->goesRight()) {
1211 0 : out << " goes right; ";
1212 : } else {
1213 0 : out << " unknown direction; ";
1214 : }
1215 0 : out << (void *)&e << "\n";
1216 : break;
1217 : }
1218 525 : return out;
1219 : }
1220 :
1221 0 : std::ostream &operator<<(std::ostream &out, const FaceEdge &e) {
1222 0 : Vec2 orgVec = e._vertex->_origin;
1223 0 : Vec2 dstVec = e._next->_vertex->_origin;
1224 0 : uint32_t orgIdx = e._vertex->_uniqueIdx;
1225 0 : uint32_t dstIdx = e._next->_vertex->_uniqueIdx;
1226 0 : out << "FaceEdge (" << orgIdx << " - " << dstIdx << ") : " << orgVec << " - " << dstVec << ";";
1227 0 : return out;
1228 : }
1229 :
1230 0 : std::ostream &operator<<(std::ostream &stream, VerboseFlag e) {
1231 0 : stream.iword( TessVerboseInfo ) = toInt(e);
1232 0 : return stream;
1233 : }
1234 :
1235 0 : std::ostream &operator<<(std::ostream &stream, const EdgeDictNode &e) {
1236 0 : stream << "EdgeDictNode(" << e.org << "; " << e.dst() << "; cur: " << e.current() << ");";
1237 0 : return stream;
1238 : }
1239 :
1240 0 : std::ostream &operator<<(std::ostream &stream, const Edge &e) {
1241 0 : if (e.inverted) {
1242 0 : stream << e.right;
1243 : } else {
1244 0 : stream << e.left;
1245 : }
1246 0 : return stream;
1247 : }
1248 :
1249 : }
|
