Line data Source code
1 : /*
2 : * Copyright (c) 2012-2015: G-CSC, Goethe University Frankfurt
3 : * Author: Sebastian Reiter
4 : *
5 : * This file is part of UG4.
6 : *
7 : * UG4 is free software: you can redistribute it and/or modify it under the
8 : * terms of the GNU Lesser General Public License version 3 (as published by the
9 : * Free Software Foundation) with the following additional attribution
10 : * requirements (according to LGPL/GPL v3 §7):
11 : *
12 : * (1) The following notice must be displayed in the Appropriate Legal Notices
13 : * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14 : *
15 : * (2) The following notice must be displayed at a prominent place in the
16 : * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17 : *
18 : * (3) The following bibliography is recommended for citation and must be
19 : * preserved in all covered files:
20 : * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21 : * parallel geometric multigrid solver on hierarchically distributed grids.
22 : * Computing and visualization in science 16, 4 (2013), 151-164"
23 : * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24 : * flexible software system for simulating pde based models on high performance
25 : * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26 : *
27 : * This program is distributed in the hope that it will be useful,
28 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 : * GNU Lesser General Public License for more details.
31 : */
32 :
33 : #include <list>
34 : #include <vector>
35 : #include <cassert>
36 : #include <map>
37 : #include <stack>
38 : #include <algorithm>
39 : #include "lib_grid/lg_base.h"
40 : #include "triangle_fill_sweep_line.h"
41 :
42 : using namespace std;
43 :
44 : namespace ug
45 : {
46 :
47 : struct SweepLineEdge;
48 :
49 : enum SweepLineVertexStatus{
50 : SLVS_NONE = 0,
51 : SLVS_START,
52 : SLVS_END,
53 : SLVS_REGULAR,
54 : SLVS_SPLIT,
55 : SLVS_MERGE
56 : };
57 :
58 : enum SweepLineEdgeStatus{
59 : SLES_UNKNOWN = 0,
60 : SLES_RIM
61 : };
62 :
63 : /** Please note that the connections array has to be maintained manually.
64 : * This is important to reduce unnecessary overhead.
65 : */
66 0 : struct SweepLineVertex
67 : {
68 0 : SweepLineVertex() : m_status(SLVS_NONE), isRimVertex(false) {}
69 : SweepLineVertex(int ind, vector2* ptr) :
70 : vrtInd(ind), vrtPtr(ptr), m_status(SLVS_NONE), isRimVertex(false) {}
71 :
72 : int vrtInd;
73 : const vector2* vrtPtr;
74 : unsigned char m_status;
75 : std::vector<SweepLineEdge*> connections;
76 : bool isRimVertex;
77 : };
78 :
79 : /** Please note that edges do not automatically register them selves at
80 : * their vertices connections array. This would make problems with
81 : * temporary edge objects and copy-construction.*/
82 : struct SweepLineEdge
83 : {
84 0 : SweepLineEdge(SweepLineVertex* v1, SweepLineVertex* v2) :
85 0 : m_status(SLES_UNKNOWN), m_v1(v1), m_v2(v2), m_helper(NULL), m_numConnectedPolygons(0)
86 : {}
87 :
88 : SweepLineVertex* get_connected(const SweepLineVertex* v) const
89 : {
90 0 : if(m_v1 == v)
91 0 : return m_v2;
92 0 : else if(m_v2 == v)
93 0 : return m_v1;
94 : return NULL;
95 : }
96 :
97 : vector2 direction() const
98 : {
99 0 : return vector2(m_v2->vrtPtr->x() - m_v1->vrtPtr->x(),
100 0 : m_v2->vrtPtr->y() - m_v1->vrtPtr->y());
101 : }
102 :
103 : bool contains(const SweepLineVertex* v)
104 : {
105 0 : return (m_v1 == v) || (m_v2 == v);
106 : }
107 :
108 : unsigned char m_status;
109 : SweepLineVertex* m_v1;
110 : SweepLineVertex* m_v2;
111 : SweepLineVertex* m_helper;
112 : int m_numConnectedPolygons;
113 : };
114 :
115 :
116 : typedef list<SweepLineEdge> SweepLineEdgeList;
117 : typedef SweepLineEdgeList::iterator SweepLineEdgeIter;
118 : typedef multimap<number, SweepLineEdge*> MapEdgeCuts;
119 :
120 :
121 0 : inline bool cmp_slv(const SweepLineVertex& v1, const SweepLineVertex& v2)
122 : {
123 0 : if(v1.vrtPtr->y() > v2.vrtPtr->y())
124 : return true;
125 0 : else if(v1.vrtPtr->y() == v2.vrtPtr->y())
126 0 : if(v1.vrtPtr->x() < v2.vrtPtr->x())
127 0 : return true;
128 : return false;
129 : }
130 :
131 : /// returns a value between -1 and 1, determining the magnitude of the right bend.
132 : /** (-1, 0): left bend,
133 : * 0: no bend,
134 : * (0, 1): right bend
135 : */
136 0 : number CalculateRightBendVal(vector2& dirOut,
137 : number& normDotOut,
138 : SweepLineEdge& e,
139 : SweepLineVertex* firstVrt,
140 : vector2 lastDir,
141 : bool lastDirNormalized = false)
142 : {
143 0 : if(!lastDirNormalized)
144 0 : VecNormalize(lastDir, lastDir);
145 :
146 : // the direction has to point away from lastVrt
147 : dirOut = e.direction();
148 0 : if(e.m_v1 != firstVrt)
149 : VecScale(dirOut, dirOut, -1.);
150 :
151 0 : VecNormalize(dirOut, dirOut);
152 :
153 : // automatically normalized
154 0 : vector2 lastNorm(lastDir.y(), -lastDir.x());
155 :
156 : // calculate the value for this configuration.
157 : // the result will be between -1 and 1.
158 : // The higher the better.
159 : number dDir = VecDot(lastDir, dirOut);
160 0 : normDotOut = VecDot(lastNorm, dirOut);
161 : number val;
162 0 : if(normDotOut <= 0)
163 0 : val = 0.5 * dDir - 0.5;
164 : else
165 0 : val = 0.5 - 0.5 * dDir;
166 0 : return val;
167 : }
168 :
169 : /**
170 : * For each entry in vrtsIn an entry in vrtsOut is created.
171 : * However, vertices in vrtsOut are sorted from top to bottom.
172 : * Each vertex in vrtsOut references all edges in edgesOut, to
173 : * which it is connected.
174 : * Directions of edges in edgesOut are CCW, but only if sorting
175 : * was possible (this is always the case for the outer rim).
176 : */
177 0 : bool CreateSweepLineStructs(vector<SweepLineVertex>& vrtsOut,
178 : SweepLineEdgeList& edgesOut,
179 : const vector<vector2>& vrtsIn,
180 : const vector<int>& edgesIn)
181 : {
182 0 : if(vrtsIn.size() < 3)
183 : return false;
184 :
185 0 : vrtsOut.resize(vrtsIn.size());
186 :
187 : // fill entries
188 0 : for(size_t i = 0; i < vrtsIn.size(); ++i){
189 0 : vrtsOut[i].vrtInd = i;
190 0 : vrtsOut[i].vrtPtr = &vrtsIn[i];
191 : }
192 :
193 : // sort the sweeplinevertices
194 0 : sort(vrtsOut.begin(), vrtsOut.end(), cmp_slv);
195 :
196 : // redirect all connection indices for the SweepLineVertices
197 : {
198 : // an array for index indirections.
199 : // associates the index of a normal vertex with the index of a slv
200 0 : vector<int> slvInd(vrtsOut.size());
201 0 : for(size_t i = 0; i < vrtsOut.size(); ++i){
202 0 : slvInd[vrtsOut[i].vrtInd] = i;
203 : }
204 :
205 : // add connections
206 0 : for(size_t i = 0; i < edgesIn.size(); i+=2){
207 0 : edgesOut.push_back(SweepLineEdge(&vrtsOut[slvInd[edgesIn[i]]],
208 0 : &vrtsOut[slvInd[edgesIn[i+1]]]));
209 0 : vrtsOut[slvInd[edgesIn[i]]].connections.push_back(&edgesOut.back());
210 0 : vrtsOut[slvInd[edgesIn[i+1]]].connections.push_back(&edgesOut.back());
211 : }
212 0 : }
213 :
214 : // now make sure that the outer rim is in ccw order
215 : // start at the first vertex (this is the top vertex)
216 : // for each vertex follow the edge, that makes the sharpest turn to the right.
217 : // relative to the last checked edge. the initial direction is left. This is fine,
218 : // since we start at the top.
219 : SweepLineVertex* comingFromVrt = NULL;
220 : vector2 lastDir(-1, 0);
221 : SweepLineVertex* lastVrt = &vrtsOut[0];
222 0 : lastVrt->m_status = SLVS_START;
223 0 : lastVrt->isRimVertex = true;
224 :
225 : // the start vertex has to have at least one connection
226 0 : if(lastVrt->connections.empty()){
227 : // theres nothing we can do.
228 : return false;
229 : }
230 :
231 : while(1){
232 : // find the edge that makes the sharpest turn to the right (even if it is a left turn)
233 : // normally a vertex has to have two connections. However, we make an exception for the first one.
234 0 : if((lastVrt != &vrtsOut[0]) && (lastVrt->connections.size() < 2)){
235 : // we're at the end of the road - this means the outer rim is open.
236 : // close it and break
237 0 : edgesOut.push_back(SweepLineEdge(lastVrt, &vrtsOut[0]));
238 0 : lastVrt->connections.push_back(&edgesOut.back());
239 0 : vrtsOut[0].connections.push_back(&edgesOut.back());
240 0 : break;
241 : }
242 :
243 : number bestVal = -2;
244 : vector2 nextDir(0, 0);
245 : SweepLineEdge* nextEdge = NULL;
246 : number bestNormDot = 0;
247 0 : for(size_t i = 0; i < lastVrt->connections.size(); ++i){
248 0 : SweepLineEdge* tmpEdge= lastVrt->connections[i];
249 0 : if(tmpEdge->get_connected(lastVrt) == comingFromVrt)
250 0 : continue;
251 :
252 : vector2 tDir;
253 : number dNorm;
254 0 : number val = CalculateRightBendVal(tDir, dNorm, *tmpEdge, lastVrt, lastDir, true);
255 :
256 0 : if(val > bestVal){
257 : bestVal = val;
258 : nextDir = tDir;
259 : nextEdge = tmpEdge;
260 0 : bestNormDot = dNorm;
261 : }
262 : }
263 :
264 : assert((nextEdge != NULL) && "a new direction should have been found!");
265 :
266 : // make sure that nextIter points into the right direction
267 0 : if(nextEdge->m_v1 != lastVrt)
268 : swap(nextEdge->m_v1, nextEdge->m_v2);
269 :
270 : // based on lastDir and nextDir we can assign the new status to lastVrt, if none has been
271 : // previously assigned.
272 0 : if(lastVrt->m_status == SLVS_NONE){
273 0 : if(lastDir.y() > 0){
274 0 : if(nextDir.y() < 0){
275 0 : if(bestNormDot < 0)
276 0 : lastVrt->m_status = SLVS_START;
277 : else
278 0 : lastVrt->m_status = SLVS_SPLIT;
279 : }
280 0 : else if(nextDir.y() > 0)
281 0 : lastVrt->m_status = SLVS_REGULAR;
282 : else{
283 0 : if(nextDir.x() < 0)
284 0 : lastVrt->m_status = SLVS_REGULAR;
285 : else
286 0 : lastVrt->m_status = SLVS_SPLIT;
287 : }
288 :
289 : // if an inner edge leaves lastVrt upwards, then we have to
290 : // regard it as a regular vertex.
291 0 : if(lastVrt->m_status == SLVS_SPLIT){
292 0 : for(size_t i = 0; i < lastVrt->connections.size(); ++i){
293 0 : if(cmp_slv(*lastVrt->connections[i]->get_connected(lastVrt), *lastVrt)){
294 0 : lastVrt->m_status = SLVS_REGULAR;
295 0 : break;
296 : }
297 : }
298 : }
299 : }
300 0 : else if(lastDir.y() < 0){ // lastDir.y() < 0 from now on
301 0 : if(nextDir.y() > 0){
302 0 : if(bestNormDot > 0)
303 0 : lastVrt->m_status = SLVS_MERGE;
304 : else
305 0 : lastVrt->m_status = SLVS_END;
306 : }
307 0 : else if(nextDir.y() < 0)
308 0 : lastVrt->m_status = SLVS_REGULAR;
309 : else{
310 0 : if(nextDir.x() > 0)
311 0 : lastVrt->m_status = SLVS_REGULAR;
312 : else
313 0 : lastVrt->m_status = SLVS_MERGE;
314 : }
315 :
316 : // if an inner edge leaves lastVrt downwards, then we have to
317 : // regard it as a regular vertex.
318 0 : if(lastVrt->m_status == SLVS_MERGE){
319 0 : for(size_t i = 0; i < lastVrt->connections.size(); ++i){
320 0 : if(!cmp_slv(*lastVrt->connections[i]->get_connected(lastVrt), *lastVrt)){
321 0 : lastVrt->m_status = SLVS_REGULAR;
322 0 : break;
323 : }
324 : }
325 : }
326 : }
327 : else{ // lastDir.y() == 0 from now on
328 0 : if(lastDir.x() < 0){
329 0 : if(nextDir.y() >= 0)
330 0 : lastVrt->m_status = SLVS_REGULAR;
331 : else
332 0 : lastVrt->m_status = SLVS_START;
333 : }
334 : else{
335 0 : if(nextDir.y() <= 0)
336 0 : lastVrt->m_status = SLVS_REGULAR;
337 : else
338 0 : lastVrt->m_status = SLVS_END;
339 : }
340 : }
341 : }
342 :
343 : // mark the current edge as a rim edge
344 0 : nextEdge->m_status = SLES_RIM;
345 :
346 : // get the next vertex
347 : comingFromVrt = lastVrt;
348 0 : lastVrt = nextEdge->m_v2;
349 0 : lastVrt->isRimVertex = true;
350 : lastDir = nextDir;
351 : // if the vertex has already been processed, we have to quit here
352 0 : if(lastVrt->m_status != SLVS_NONE)
353 : break;
354 0 : }
355 :
356 : // now make sure that vertices that do not lie on the outer rim have a correct status
357 0 : for(size_t i = 0; i < vrtsOut.size(); ++i){
358 : SweepLineVertex& vrt = vrtsOut[i];
359 0 : if(vrt.m_status == SLVS_NONE){
360 : // check the position of connected vertices
361 : bool gotUpper = false;
362 : bool gotLower = false;
363 : bool gotEqualYLeft = false;
364 : bool gotEqualYRight = false;
365 : bool gotRight = false;
366 0 : for(size_t j = 0; j < vrt.connections.size(); ++j){
367 0 : SweepLineVertex& connVrt = *(vrt.connections[j]->get_connected(&vrt));
368 :
369 0 : if(connVrt.vrtPtr->x() > vrt.vrtPtr->x())
370 : gotRight = true;
371 :
372 0 : if(connVrt.vrtPtr->y() < vrt.vrtPtr->y())
373 : gotLower = true;
374 0 : else if(connVrt.vrtPtr->y() > vrt.vrtPtr->y())
375 : gotUpper = true;
376 : else{
377 0 : if(connVrt.vrtPtr->x() > vrt.vrtPtr->x())
378 : gotEqualYRight = true;
379 : else
380 : gotEqualYLeft = true;
381 : }
382 : }
383 :
384 : // if there is only one connection, we have to treat the vertex specially
385 0 : if(vrt.connections.size() == 1){
386 0 : if(gotUpper)
387 0 : vrt.m_status = SLVS_MERGE;
388 0 : else if(gotLower)
389 0 : vrt.m_status = SLVS_SPLIT;
390 : else{
391 0 : if(gotRight)
392 0 : vrt.m_status = SLVS_SPLIT;
393 : else
394 0 : vrt.m_status = SLVS_MERGE;
395 : }
396 : }
397 : else{ // more than one connection from now on
398 0 : if(gotUpper && gotLower)
399 0 : vrt.m_status = SLVS_REGULAR;
400 : else{
401 0 : if(gotEqualYLeft && gotEqualYRight)
402 0 : vrt.m_status = SLVS_REGULAR;
403 0 : else if(gotUpper){
404 0 : if(gotEqualYRight)
405 0 : vrt.m_status = SLVS_REGULAR;
406 : else
407 0 : vrt.m_status = SLVS_MERGE;
408 : }
409 0 : else if(gotLower){
410 0 : if(gotEqualYLeft)
411 0 : vrt.m_status = SLVS_REGULAR;
412 : else
413 0 : vrt.m_status = SLVS_SPLIT;
414 : }
415 : else
416 0 : vrt.m_status = SLVS_REGULAR;
417 : }
418 : }
419 :
420 : assert((vrt.m_status != SLVS_NONE) && "no status found");
421 0 : if(vrt.m_status == SLVS_NONE){
422 : UG_LOG("ERROR in CreateSweeplineStructs: Could not assign status.\n");
423 0 : return false;
424 : }
425 : }
426 : }
427 :
428 : // we're finally through with it!!!
429 : return true;
430 : }
431 :
432 0 : void PrintDebugInfos(const vector<SweepLineVertex>& vrts,
433 : const list<SweepLineEdge>& edges)
434 : {
435 : UG_LOG("SweepLine debug infos:");
436 : UG_LOG(" num vrts: " << vrts.size() << endl);
437 : UG_LOG(" vertex types (top to bottom): ");
438 0 : for(size_t i = 0; i < vrts.size(); ++i){
439 0 : if(vrts[i].isRimVertex){
440 : UG_LOG("rim-");
441 : }
442 : else{
443 : UG_LOG("inner-");
444 : }
445 :
446 0 : switch(vrts[i].m_status){
447 : case SLVS_NONE: UG_LOG("none"); break;
448 : case SLVS_START: UG_LOG("start"); break;
449 : case SLVS_END: UG_LOG("end"); break;
450 : case SLVS_REGULAR: UG_LOG("regular"); break;
451 : case SLVS_SPLIT: UG_LOG("split"); break;
452 : case SLVS_MERGE: UG_LOG("merge"); break;
453 : default: UG_LOG("unknown"); break;
454 : }
455 : UG_LOG(", ");
456 : }
457 :
458 : // log inner edges
459 : UG_LOG("\n inner edges:\n");
460 0 : for(list<SweepLineEdge>::const_iterator iter = edges.begin(); iter != edges.end(); ++iter){
461 0 : if(iter->m_status != SLES_RIM)
462 : {
463 0 : UG_LOG(" - " << *iter->m_v1->vrtPtr << ", " << *iter->m_v2->vrtPtr << endl);
464 : }
465 : }
466 : UG_LOG(endl);
467 :
468 : UG_LOG(" connections:\n");
469 0 : for(size_t i = 0; i < vrts.size(); ++i){
470 : const SweepLineVertex& v = vrts[i];
471 0 : UG_LOG(" vertex " << *v.vrtPtr << " is connected to: ");
472 0 : for(size_t j = 0; j < v.connections.size(); ++j){
473 0 : UG_LOG(*v.connections[j]->get_connected(&v)->vrtPtr << ", ");
474 : }
475 : UG_LOG("\n");
476 : }
477 :
478 0 : }
479 :
480 0 : bool SweepLineEdgeIntersectsSweepLine(number& xOut,
481 : const SweepLineEdge& edge,
482 : number sweepLineY)
483 : {
484 : // first check whether both points lie above or below the sweepline
485 0 : if((edge.m_v1->vrtPtr->y() < sweepLineY)
486 0 : && (edge.m_v2->vrtPtr->y() < sweepLineY))
487 : return false;
488 :
489 : if((edge.m_v1->vrtPtr->y() >= sweepLineY)
490 0 : && (edge.m_v2->vrtPtr->y() >= sweepLineY))
491 : return false;
492 :
493 : vector2 dir = edge.direction();
494 0 : if(dir.y() != 0){
495 0 : number s = (sweepLineY - edge.m_v1->vrtPtr->y()) / dir.y();
496 : //if((s >= 0) && (s <= 1.)){
497 0 : if(s < 0) s = 0;
498 0 : if(s > 1.) s = 1.;
499 :
500 0 : xOut = edge.m_v1->vrtPtr->x() + s * dir.x();
501 0 : return true;
502 : }
503 :
504 : return false;
505 : }
506 :
507 0 : SweepLineEdge* GetEdgeOnTheLeft(MapEdgeCuts& edgeCuts, SweepLineVertex& v)
508 : {
509 : // find the edge in edgeCuts which is directly left of v
510 : SweepLineEdge* leftEdge = NULL;
511 : number leftEdgeVal = 0;
512 :
513 0 : for(MapEdgeCuts::iterator iter = edgeCuts.begin();
514 0 : iter != edgeCuts.end(); ++iter)
515 : {
516 0 : if(iter->first < v.vrtPtr->x()){
517 0 : if(!iter->second->contains(&v)){
518 : bool takeNew = true;
519 : // if a second edge with identical cut exists (this can happen
520 : // if two edges are cut at their upper vertex), we have to make
521 : // sure to return the edge, which points farther to the right.
522 0 : if(leftEdge){
523 0 : if(leftEdgeVal == iter->first){
524 : // check whether iter->second points farther to the right.
525 : vector2 dirOld = leftEdge->direction();
526 : vector2 dirNew = iter->second->direction();
527 0 : if(dirOld.y() > 0)
528 : VecScale(dirOld, dirOld, -1);
529 0 : if(dirNew.y() > 0)
530 : VecScale(dirNew, dirNew, -1);
531 :
532 0 : VecNormalize(dirOld, dirOld);
533 0 : VecNormalize(dirNew, dirNew);
534 :
535 0 : if(dirOld.x() > dirNew.x())
536 : takeNew = false;
537 : }
538 : }
539 :
540 : if(takeNew){
541 : leftEdge = iter->second;
542 : leftEdgeVal = iter->first;
543 : }
544 : }
545 : }
546 : else
547 : break;
548 : }
549 0 : return leftEdge;
550 : }
551 :
552 0 : bool EdgeExists(SweepLineVertex* v0, SweepLineVertex* v1)
553 : {
554 0 : for(size_t i = 0; i < v0->connections.size(); ++i){
555 0 : if(v0->connections[i]->contains(v1)){
556 : return true;
557 : }
558 : }
559 : return false;
560 : }
561 :
562 : /// inserts new edges so that edges contains a set of monotone polynomes
563 0 : bool SweepLine_CreateMonotones(vector<SweepLineVertex>& vrts,
564 : list<SweepLineEdge>& edges)
565 : {
566 : // create sets of monotone polynomes.
567 : MapEdgeCuts edgeCuts;
568 :
569 0 : for(size_t i_vrt = 0; i_vrt < vrts.size(); ++i_vrt){
570 : SweepLineVertex& v = vrts[i_vrt];
571 :
572 0 : number sweepLineY = v.vrtPtr->y();
573 : // update the edgeCutsMap.
574 : MapEdgeCuts tmap;
575 0 : for(MapEdgeCuts::iterator iter = edgeCuts.begin();
576 0 : iter != edgeCuts.end(); ++iter)
577 : {
578 : // if the helper was set to NULL, we'll ignore the edge
579 0 : if(iter->second->m_helper){
580 : // make sure that the edge still intersects the sweepLine.
581 : number x;
582 0 : if(SweepLineEdgeIntersectsSweepLine(x, *iter->second, sweepLineY))
583 0 : tmap.insert(make_pair(x, iter->second));
584 : }
585 : }
586 : //only for debugging!
587 : //vector2 tmpPos = *v.vrtPtr;
588 :
589 : edgeCuts.swap(tmap);
590 :
591 0 : switch(v.m_status){
592 : case SLVS_NONE:
593 : break;
594 : case SLVS_START:
595 : // rim-edges that leave v and that have v as their first
596 : // vertex, have to be added to edgeCuts.
597 :
598 : // add all edges connected to the start vertex to edgeCuts.
599 : // Note that at least one edge with has exterior to its right
600 : // will be added.
601 0 : for(size_t i = 0; i < v.connections.size(); ++i){
602 0 : edgeCuts.insert(make_pair(v.vrtPtr->x(), v.connections[i]));
603 0 : v.connections[i]->m_helper = &v;
604 : /*
605 : if((v.connections[i]->m_status == SLES_RIM)
606 : && (v.connections[i]->m_v1 == &v))
607 : {
608 : edgeCuts.insert(make_pair(v.vrtPtr->x(), v.connections[i]));
609 : v.connections[i]->m_helper = &v;
610 : }
611 : else if(v.connections[i]->m_status != SLES_RIM){
612 : // inner edges that go down have to be added, too
613 : if(v.connections[i]->get_connected(&v)->vrtPtr->y() < v.vrtPtr->y()){
614 : edgeCuts.insert(make_pair(v.vrtPtr->x(), v.connections[i]));
615 : v.connections[i]->m_helper = &v;
616 : }
617 : }*/
618 : }
619 : break;
620 : case SLVS_END:
621 : {
622 : // get the incoming edge
623 : SweepLineEdge* incoming = NULL;
624 0 : for(size_t i = 0; i < v.connections.size(); ++i){
625 0 : if((v.connections[i]->m_status == SLES_RIM)
626 0 : && (v.connections[i]->m_v2 == &v))
627 : {
628 : incoming = v.connections[i];
629 : break;
630 : }
631 : }
632 :
633 : //assert((incoming != NULL) && "An incoming edge has to exist!");
634 0 : if(!incoming){
635 : UG_LOG("ERROR in SweepLine_CreateMonotones: couldn't find incoming-edge.\n");
636 : return false;
637 : }
638 :
639 0 : if(incoming->m_helper != NULL){
640 0 : if(incoming->m_helper->m_status == SLVS_MERGE){
641 : // insert a diagonal between helper and v
642 0 : edges.push_back(SweepLineEdge(incoming->m_helper, &v));
643 0 : incoming->m_helper->connections.push_back(&edges.back());
644 0 : v.connections.push_back(&edges.back());
645 : }
646 : }
647 :
648 : // remove incoming from the set of edge-cuts.
649 : // This can be done by setting its helper to NULL.
650 : // The rest will be handled later on
651 0 : incoming->m_helper = NULL;
652 0 : }break;
653 0 : case SLVS_REGULAR:
654 : {
655 : // get the direction of the incoming edge
656 0 : if(v.isRimVertex && (v.connections.size() == 2)){
657 : SweepLineEdge* incoming = NULL;
658 0 : for(size_t i = 0; i < v.connections.size(); ++i){
659 0 : if((v.connections[i]->m_status == SLES_RIM)
660 0 : && (v.connections[i]->m_v2 == &v))
661 : {
662 : incoming = v.connections[i];
663 : break;
664 : }
665 : }
666 :
667 : //assert((incoming != NULL) && "An incoming edge has to exist!");
668 :
669 0 : if(!incoming){
670 : UG_LOG("ERROR in SweepLine_CreateMonotones: couldn't find incoming-edge.\n");
671 : return false;
672 : }
673 :
674 : vector2 dir = incoming->direction();
675 : bool areaIsToTheRight = false;
676 0 : if(dir.y() < 0)
677 : areaIsToTheRight = true;
678 0 : else if(dir.y() == 0){
679 0 : if(dir.x() > 0)
680 : areaIsToTheRight = true;
681 : }
682 :
683 : if(areaIsToTheRight){
684 0 : if(!incoming->m_helper){
685 0 : UG_LOG("ERROR in SweepLine_CreateMonotones (SLVS_REGULAR-rim): incoming-edge has no helper at vertex " << vrts[i_vrt].vrtInd << ".\n");
686 : return false;
687 : }
688 0 : if(incoming->m_helper->m_status == SLVS_MERGE){
689 : // insert a diagonal between helper and v
690 0 : edges.push_back(SweepLineEdge(incoming->m_helper, &v));
691 0 : incoming->m_helper->connections.push_back(&edges.back());
692 0 : v.connections.push_back(&edges.back());
693 :
694 : // delete incoming from edgeCuts
695 0 : incoming->m_helper = NULL;
696 : }
697 :
698 : // add the outgoing edge to edgeCuts
699 : SweepLineEdge* outgoing = NULL;
700 0 : for(size_t i = 0; i < v.connections.size(); ++i){
701 0 : if((v.connections[i]->m_status == SLES_RIM)
702 0 : && (v.connections[i]->m_v1 == &v))
703 : {
704 : outgoing = v.connections[i];
705 : break;
706 : }
707 : }
708 :
709 : //assert((outgoing != NULL) && "An outgoing edge has to exist!");
710 0 : if(!outgoing){
711 : UG_LOG("ERROR in SweepLine_CreateMonotones: couldn't find outgoing-edge.\n");
712 : return false;
713 : }
714 :
715 0 : edgeCuts.insert(make_pair(v.vrtPtr->x(), outgoing));
716 0 : outgoing->m_helper = &v;
717 : }
718 : else{ // area is on the left
719 : // find the edge in edgeCuts which is directly left of v
720 0 : SweepLineEdge* leftEdge = GetEdgeOnTheLeft(edgeCuts, v);
721 :
722 0 : if(leftEdge){
723 0 : if(!leftEdge->m_helper){
724 0 : UG_LOG("ERROR in SweepLine_CreateMonotones (SLVS_REGULAR-rim): left-edge has no helper at vertex " << vrts[i_vrt].vrtInd << ".\n");
725 : return false;
726 : }
727 0 : if(leftEdge->m_helper->m_status == SLVS_MERGE){
728 : // add a diagonal and replace the helper
729 0 : edges.push_back(SweepLineEdge(leftEdge->m_helper, &v));
730 0 : leftEdge->m_helper->connections.push_back(&edges.back());
731 0 : v.connections.push_back(&edges.back());
732 : }
733 0 : leftEdge->m_helper = &v;
734 : }
735 : }
736 : }
737 : else{
738 : // the vertex is an inner regular vertex or a rim-vertex which is connected to
739 : // inner edges.
740 : // check all incoming edges (edges that come from above)
741 : // make sure to not check the new ones
742 : size_t initialSize = v.connections.size();
743 0 : for(size_t i = 0; i < initialSize; ++i){
744 0 : SweepLineEdge& incoming = *v.connections[i];
745 : SweepLineVertex* conn = incoming.get_connected(&v);
746 :
747 : // rim vertices have to be treated specially
748 0 : if(v.isRimVertex){
749 : // if the edge is a rim edge, then it has to end at v
750 0 : if((incoming.m_status == SLES_RIM)
751 0 : && (incoming.m_v1 == &v))
752 : {
753 0 : continue;
754 : }
755 : }
756 :
757 : // make sure that the edge is really an incoming edge
758 0 : if(conn->vrtPtr->y() < v.vrtPtr->y())
759 0 : continue;
760 0 : else if(conn->vrtPtr->y() == v.vrtPtr->y()){
761 0 : if(conn->vrtPtr->x() > v.vrtPtr->x())
762 0 : continue;
763 : }
764 :
765 : // ok. it is.
766 : //assert((incoming.m_helper != NULL) && "a helper has to exist");
767 0 : if(incoming.m_helper)
768 : {
769 0 : if(incoming.m_helper->m_status == SLVS_MERGE){
770 : // insert a diagonal between helper and v
771 0 : edges.push_back(SweepLineEdge(incoming.m_helper, &v));
772 0 : incoming.m_helper->connections.push_back(&edges.back());
773 0 : v.connections.push_back(&edges.back());
774 :
775 : // delete incoming from edgeCuts
776 0 : incoming.m_helper = NULL;
777 : }
778 : }
779 : }
780 :
781 : // now find the edge in edgeCuts, which is directly left of v
782 0 : SweepLineEdge* leftEdge = GetEdgeOnTheLeft(edgeCuts, v);
783 :
784 0 : if(leftEdge){
785 0 : if(!leftEdge->m_helper){
786 : UG_LOG("ERROR in SweepLine_CreateMonotones (SLVS_REGULAR): left-edge has no helper at vertex " << i_vrt << ".\n");
787 : return false;
788 : }
789 0 : if(leftEdge->m_helper->m_status == SLVS_MERGE){
790 : // add a diagonal and replace the helper
791 0 : edges.push_back(SweepLineEdge(leftEdge->m_helper, &v));
792 0 : leftEdge->m_helper->connections.push_back(&edges.back());
793 0 : v.connections.push_back(&edges.back());
794 : }
795 0 : leftEdge->m_helper = &v;
796 : }
797 :
798 : // finally add all outgoing edges to edgeCuts
799 0 : for(size_t i = 0; i < v.connections.size(); ++i){
800 0 : SweepLineEdge& outgoing = *v.connections[i];
801 : SweepLineVertex* conn = outgoing.get_connected(&v);
802 :
803 : // make sure that the edge is really an outgoing edge
804 0 : if(conn->vrtPtr->y() > v.vrtPtr->y())
805 0 : continue;
806 0 : else if(conn->vrtPtr->y() == v.vrtPtr->y()){
807 0 : if(conn->vrtPtr->x() < v.vrtPtr->x())
808 0 : continue;
809 : }
810 :
811 : // ok. it is outgoing
812 0 : edgeCuts.insert(make_pair(v.vrtPtr->x(), v.connections[i]));
813 0 : outgoing.m_helper = &v;
814 : }
815 : }
816 : }break;
817 0 : case SLVS_SPLIT:
818 : {
819 : // find the edge in edgeCuts which is directly left of v
820 0 : SweepLineEdge* leftEdge = GetEdgeOnTheLeft(edgeCuts, v);
821 :
822 : //assert((leftEdge != NULL) && "a edge on the left has to exist.");
823 :
824 0 : if(!leftEdge){
825 : UG_LOG("ERROR in SweepLine_CreateMonotones: couldn't find left-edge.\n");
826 : return false;
827 : }
828 :
829 0 : if(!leftEdge->m_helper){
830 : UG_LOG("ERROR in SweepLine_CreateMonotones (SLVS_SPLIT): left-edge has no helper at vertex " << i_vrt << ".\n");
831 : return false;
832 : }
833 :
834 : // create a new diagonal from leftEdges helper to v
835 0 : edges.push_back(SweepLineEdge(leftEdge->m_helper, &v));
836 0 : leftEdge->m_helper->connections.push_back(&edges.back());
837 0 : v.connections.push_back(&edges.back());
838 :
839 : // replace the helper by v
840 0 : leftEdge->m_helper = &v;
841 : // add the outgoing edges of v to the map
842 : // if the vertex is an inner vertex, we have to add all connected edges.
843 0 : for(size_t i = 0; i < v.connections.size(); ++i){
844 0 : if((!v.isRimVertex) || (v.connections[i]->m_v1 == &v))
845 : {
846 0 : edgeCuts.insert(make_pair(v.vrtPtr->x(), v.connections[i]));
847 0 : v.connections[i]->m_helper = &v;
848 : }
849 : }
850 : }break;
851 0 : case SLVS_MERGE:
852 : {
853 : // we differentiate between rim vertices and inner vertices, since this gives a speedup.
854 0 : if(v.isRimVertex){
855 : // get the incoming edge
856 : SweepLineEdge* incoming = NULL;
857 0 : for(size_t i = 0; i < v.connections.size(); ++i){
858 0 : if((v.connections[i]->m_status == SLES_RIM)
859 0 : && (v.connections[i]->m_v2 == &v))
860 : {
861 : incoming = v.connections[i];
862 : break;
863 : }
864 : }
865 : //assert((incoming != NULL) && "An incoming edge has to exist!");
866 : //assert((incoming->m_helper != NULL) && "The edge has to have a helper!");
867 :
868 0 : if(!incoming){
869 : UG_LOG("ERROR in SweepLine_CreateMonotones: couldn't find incoming-edge.\n");
870 : return false;
871 : }
872 :
873 0 : if(!incoming->m_helper){
874 : UG_LOG("ERROR in SweepLine_CreateMonotones (SLVS_MERGE): incoming-edge has no helper at vertex " << i_vrt << ".\n");
875 : return false;
876 : }
877 :
878 0 : if(incoming->m_helper->m_status == SLVS_MERGE){
879 : // insert a diagonal between helper and v
880 0 : edges.push_back(SweepLineEdge(incoming->m_helper, &v));
881 0 : incoming->m_helper->connections.push_back(&edges.back());
882 0 : v.connections.push_back(&edges.back());
883 : }
884 :
885 : // remove incoming from the set of edge-cuts.
886 : // This can be done by setting its helper to NULL.
887 : // The rest will be handled later on
888 0 : incoming->m_helper = NULL;
889 : }
890 : else{
891 : // check all incoming edges
892 0 : for(size_t i = 0; i < v.connections.size(); ++i){
893 0 : SweepLineEdge* incoming = v.connections[i];
894 0 : if(incoming->m_helper){
895 0 : if(incoming->m_helper->m_status == SLVS_MERGE){
896 0 : edges.push_back(SweepLineEdge(incoming->m_helper, &v));
897 0 : incoming->m_helper->connections.push_back(&edges.back());
898 0 : v.connections.push_back(&edges.back());
899 : }
900 : // remove incoming from the set of edge-cuts.
901 : // This can be done by setting its helper to NULL.
902 : // The rest will be handled later on
903 0 : incoming->m_helper = NULL;
904 : }
905 : }
906 : }
907 :
908 : // find the edge in edgeCuts which is directly left of v
909 0 : SweepLineEdge* leftEdge = GetEdgeOnTheLeft(edgeCuts, v);
910 :
911 : //assert((leftEdge != NULL) && "an edge on the left has to exist.");
912 : //assert(leftEdge->m_helper && "edge has no helper");
913 :
914 0 : if(!leftEdge){
915 : UG_LOG("ERROR in SweepLine_CreateMonotones: couldn't find left-edge.\n");
916 : return false;
917 : }
918 :
919 0 : if(!leftEdge->m_helper){
920 : UG_LOG("ERROR in SweepLine_CreateMonotones (SLVS_MERGE): left-edge has no helper at vertex " << i_vrt << ".\n");
921 : return false;
922 : }
923 :
924 0 : if(leftEdge->m_helper != &v
925 0 : && leftEdge->m_helper->m_status == SLVS_MERGE)
926 : {
927 : // add a diagonal and replace the helper
928 0 : edges.push_back(SweepLineEdge(leftEdge->m_helper, &v));
929 0 : leftEdge->m_helper->connections.push_back(&edges.back());
930 0 : v.connections.push_back(&edges.back());
931 : }
932 :
933 0 : leftEdge->m_helper = &v;
934 :
935 0 : }break;
936 : }
937 : }
938 :
939 : return true;
940 : }
941 :
942 0 : bool TriangleFill_SweepLine(vector<int>& facesOut,
943 : const vector<vector2>& srcVrtsOrig,
944 : /*const */vector<int>& srcEdges)
945 : {
946 : // first check, that all edges are fine
947 : size_t numVrts = srcVrtsOrig.size();
948 0 : for(size_t i = 0; i < srcEdges.size(); ++i){
949 0 : if(srcEdges[i] < 0 || srcEdges[i] >= (int)numVrts){
950 0 : UG_LOG("Bad edge index " << srcEdges[i] << " at index "
951 : << i << " in srcEdges in TriangleFill_SweepLine. "
952 : "Please check your edge-input array!\n");
953 0 : return false;
954 : }
955 : }
956 :
957 : // THIS IS A NASTY HACK: By casting all the values to float, we can avoid
958 : // some rounding issues... This has to be improved!
959 : // At the same time we're transforming the pointset, to improve the algorithm
960 : // for axis aligned geometries (which occur quite often...)
961 0 : vector<vector2> srcVrts(srcVrtsOrig.size());
962 0 : for(size_t i = 0; i < srcVrtsOrig.size(); ++i){
963 0 : srcVrts[i].x() = (float)(srcVrtsOrig[i].x());
964 0 : srcVrts[i].y() = (float)(srcVrtsOrig[i].y() - 0.333213214 * srcVrtsOrig[i].x());
965 : }
966 :
967 : // create an array with SweepLineVertices
968 : // be careful not to change this array after it has been set up,
969 : // since otherwise pointers might be invalidated.
970 : vector<SweepLineVertex> vrts;
971 : list<SweepLineEdge> edges;
972 :
973 0 : if(!CreateSweepLineStructs(vrts, edges, srcVrts, srcEdges)){
974 : UG_LOG("CreateSweepLineStructs failed.\n");
975 : //UG_LOG("Make sure not to select vertices that don't have connected edges.\n");
976 : UG_LOG("Make sure to select a closed outer edge-chain!\n");
977 : UG_LOG("Aborting.\n");
978 : return false;
979 : }
980 :
981 : //PrintDebugInfos(vrts, edges);
982 :
983 0 : if(!SweepLine_CreateMonotones(vrts, edges)){
984 : UG_LOG("SweepLine_CreateMonotones failed.\n");
985 : UG_LOG("Make sure to select a closed outer edge-chain!\n");
986 : //PrintDebugInfos(vrts, edges);
987 : return false;
988 : }
989 :
990 : /*
991 : //DEBUG BEGIN
992 : PrintDebugInfos(vrts, edges);
993 : // write all edges to srcEdges for debug purposes
994 :
995 : srcEdges.clear();
996 : for(SweepLineEdgeIter iter = edges.begin(); iter != edges.end(); ++iter){
997 : srcEdges.push_back(iter->m_v1->vrtInd);
998 : srcEdges.push_back(iter->m_v2->vrtInd);
999 : }
1000 : //return false;
1001 : //DEBUG END
1002 : */
1003 :
1004 : // triangulate monotone polygons
1005 : // start at the top
1006 : // while there is a candidate
1007 : // - find its two rightmost edges that are not yet complete.
1008 : // - if there are no, pick the next candidate and restart the iteration (or quit if none is left)
1009 : // - there are two. Follow them until they reach a common point by always taking sharp left corners for the
1010 : // left branch and sharp right corners for the right branch (if viewed in direction of travel.
1011 : // edges can only be used if they are not yet complete.)
1012 : // both branches are then stored in a monotone-polygon and the polygonCounter of each edge is increased by 1.
1013 : int branchInd = 0; // used for error-logging...
1014 0 : for(size_t i_main = 0; i_main < vrts.size();)
1015 : {
1016 : SweepLineVertex& monotoneTop = vrts[i_main];
1017 : // find its two rightmost edges which have not yet been processed
1018 : number bestVal[2] = {-2, -2};
1019 0 : SweepLineEdge* branch[2] = {NULL, NULL};
1020 : vector2 downDir(0, -1);//compare to straight down ray.
1021 0 : for(size_t i = 0; i < monotoneTop.connections.size(); ++i){
1022 0 : SweepLineEdge& e = *monotoneTop.connections[i];
1023 : // e is only a candidate for a branch, if it meets the following reqirements:
1024 : // - e is a rim edge and hasn't yet got a connected polygon.
1025 : // - e is an inner edge and has at most one connected polygon
1026 0 : if(((e.m_status == SLES_RIM) && e.m_numConnectedPolygons == 0)
1027 0 : || ((e.m_status != SLES_RIM) && (e.m_numConnectedPolygons < 2)))
1028 : {
1029 : vector2 tDir;
1030 : number dNorm;
1031 0 : number val = CalculateRightBendVal(tDir, dNorm, e, &monotoneTop, downDir, true);
1032 0 : if(val > bestVal[0]){
1033 : // move content of branch[0] to branch[1]
1034 : bestVal[1] = bestVal[0];
1035 0 : branch[1] = branch[0];
1036 : // set new values
1037 : bestVal[0] = val;
1038 0 : branch[0] = &e;
1039 : }
1040 0 : else if(val > bestVal[1]){
1041 : // set new values
1042 : bestVal[1] = val;
1043 0 : branch[1] = &e;
1044 : }
1045 : }
1046 : }
1047 :
1048 : // if we didn't find two valid branches, we have to continue with the next vertex
1049 : // from top to bottom. (Checking branch[1] is enough here).
1050 0 : if(!branch[1]){
1051 0 : ++i_main;
1052 0 : continue;
1053 : }
1054 :
1055 : // we found two. We have to increase their connectedPolygons member
1056 0 : branch[0]->m_numConnectedPolygons++;
1057 0 : branch[1]->m_numConnectedPolygons++;
1058 :
1059 : // branch[0] now contains the first edge of the left branch and branch[1]
1060 : // the first edge of the right branch.
1061 : // since the branches are monotone, we can follow them from top to bottom.
1062 : // on the fly we increase the connectedPolygons counter of each edge.
1063 : // we use a stack for all encountered but unprocessed vertices
1064 : stack<SweepLineVertex*> stk;
1065 0 : stk.push(&monotoneTop);
1066 :
1067 : int lastBranchInd = -1; //0: left, 1:right
1068 : while(1){
1069 : // check whether we walk on the left or on the right branch
1070 : // first get the lower vertex of each branch
1071 : SweepLineVertex* vLeft = NULL;
1072 : SweepLineVertex* vRight = NULL;
1073 :
1074 0 : if(cmp_slv(*branch[0]->m_v1, *branch[0]->m_v2))
1075 : vLeft = branch[0]->m_v2;
1076 : else
1077 : vLeft = branch[0]->m_v1;
1078 :
1079 0 : if(cmp_slv(*branch[1]->m_v1, *branch[1]->m_v2))
1080 : vRight = branch[1]->m_v2;
1081 : else
1082 : vRight = branch[1]->m_v1;
1083 :
1084 : // the higher vertex is the next one to take
1085 : SweepLineVertex* cur;
1086 : int curBranchInd;
1087 : if(cmp_slv(*vLeft, *vRight)){
1088 0 : cur = vLeft;
1089 : curBranchInd = 0;
1090 : }
1091 : else{
1092 0 : cur = vRight;
1093 : curBranchInd = 1;
1094 : }
1095 :
1096 : // if cur is equal to the top of the stack, we reached the bottom and
1097 : // are done. This normally shouldn't happen, since we exit at another
1098 : // check when searching for the next branch normally.
1099 : //assert((cur != stk.top()) && "the loop should have already been terminated!");
1100 0 : if(cur == stk.top()){
1101 0 : UG_LOG("exiting since current vertex was already on the stack: " << *cur->vrtPtr);
1102 0 : UG_LOG(" with index: " << cur->vrtInd << "\n");
1103 0 : UG_LOG("branchIndex: " << branchInd << "\n");
1104 : UG_LOG("ERROR in TriangleFill_SweepLine: Algorithm failed."
1105 : " Make sure that your geometry does not contain multiple vertices"
1106 : " at the same position (invoke RemoveDoubles on the whole selection)!\n");
1107 0 : return false;
1108 : break;
1109 : }
1110 :
1111 : // if there was no last branch, we'll simply insert the vertex into the
1112 : // stack and do some administrative stuff
1113 0 : if(lastBranchInd == -1){
1114 : stk.push(cur);
1115 : //lastBranchInd = curBranchInd; // never used
1116 : }
1117 : else{
1118 : // if the last branch was on the other side we can now build triangles
1119 : // for all stack-members
1120 0 : if(lastBranchInd != curBranchInd){
1121 : // pop all elements from the stack and build triangles
1122 : // we need the first
1123 : SweepLineVertex* v1 = stk.top(); stk.pop();
1124 : assert((!stk.empty()) && "at least two vertices should lie in the stack at this position.");
1125 :
1126 0 : SweepLineVertex* oldTop = v1;// we have to readd this later on
1127 0 : while(!stk.empty()){
1128 : // get the next vertex
1129 0 : SweepLineVertex* v2 = stk.top(); stk.pop();
1130 :
1131 : // create a triangle with correct orientation
1132 0 : if(curBranchInd == 0){
1133 0 : facesOut.push_back(cur->vrtInd);
1134 0 : facesOut.push_back(v1->vrtInd);
1135 0 : facesOut.push_back(v2->vrtInd);
1136 : }
1137 : else{
1138 0 : facesOut.push_back(cur->vrtInd);
1139 0 : facesOut.push_back(v2->vrtInd);
1140 0 : facesOut.push_back(v1->vrtInd);
1141 : }
1142 :
1143 : // prepare the next iteration
1144 : v1 = v2;
1145 : }
1146 :
1147 : // readd the last two vertices
1148 : stk.push(oldTop);
1149 : stk.push(cur);
1150 : }
1151 : else{
1152 : // pop vertices from the stack and try to build triangles.
1153 : // if a triangle can't be build, we're done.
1154 0 : SweepLineVertex* v1 = stk.top(); stk.pop();
1155 : assert((!stk.empty()) && "at least two vertices should lie in the stack at this position.");
1156 :
1157 0 : while(!stk.empty()){
1158 : // get the next vertex
1159 0 : SweepLineVertex* v2 = stk.top(); stk.pop();
1160 : // check whether the triangle can be build
1161 : vector2 dir;
1162 0 : VecSubtract(dir, *v1->vrtPtr, *cur->vrtPtr);
1163 0 : vector2 norm(dir.y(), -dir.x());
1164 0 : VecNormalize(norm, norm);
1165 0 : VecSubtract(dir, *v2->vrtPtr, *v1->vrtPtr);
1166 0 : VecNormalize(dir, dir);
1167 : number dot = VecDot(dir, norm);
1168 :
1169 : // the result has to be interpreted depending on the branch
1170 0 : if(curBranchInd == 0){
1171 0 : if(dot > 0.0001){
1172 : // create the triangle
1173 0 : facesOut.push_back(cur->vrtInd);
1174 0 : facesOut.push_back(v2->vrtInd);
1175 0 : facesOut.push_back(v1->vrtInd);
1176 : // v2 is the new v1
1177 0 : v1 = v2;
1178 : }
1179 : else{
1180 : // can't build triangle. restore and exit
1181 : stk.push(v2);
1182 0 : break;
1183 : }
1184 : }
1185 : else{
1186 0 : if(dot < -0.0001){
1187 : // create the triangle
1188 0 : facesOut.push_back(cur->vrtInd);
1189 0 : facesOut.push_back(v1->vrtInd);
1190 0 : facesOut.push_back(v2->vrtInd);
1191 : // v2 is the new v1
1192 0 : v1 = v2;
1193 : }
1194 : else{
1195 : // can't build triangle. restore and exit
1196 : stk.push(v2);
1197 : break;
1198 : }
1199 : }
1200 : }
1201 :
1202 : // readd v1 and cur to the stack
1203 : stk.push(v1);
1204 : stk.push(cur);
1205 : }
1206 : }
1207 :
1208 : // now get the next branch edge
1209 : // if cur was on the left branch, we have to get the next edge which makes the
1210 : // hardest turn to the left (in direction of travel). The opposite is the case
1211 : // if we are on the right branch.
1212 : // in any case - if the next edge points upwards, we're done.
1213 : number multiplyer = 1; // left-right helper
1214 0 : if(curBranchInd == 0)
1215 : multiplyer = -1;
1216 :
1217 0 : SweepLineVertex* conn = branch[curBranchInd]->get_connected(cur);
1218 : vector2 lastDir;
1219 0 : VecSubtract(lastDir, *cur->vrtPtr, *conn->vrtPtr);
1220 0 : VecNormalize(lastDir, lastDir);
1221 : number bestVal = -2;
1222 : SweepLineEdge* nextEdge = NULL;
1223 : vector2 newDir(0, 1);
1224 0 : for(size_t i = 0; i < cur->connections.size(); ++i){
1225 0 : SweepLineEdge& e = *cur->connections[i];
1226 : // make sure not to readd the current branch-edge.
1227 0 : if(&e == branch[curBranchInd])
1228 0 : continue;
1229 :
1230 : vector2 tDir;
1231 : number dNorm;
1232 0 : number val = multiplyer * CalculateRightBendVal(tDir, dNorm, e, cur, lastDir, true);
1233 :
1234 0 : if(val > bestVal){
1235 : // set new values
1236 : bestVal = val;
1237 : nextEdge = &e;
1238 : newDir = tDir;
1239 : }
1240 : }
1241 :
1242 : // if no new edge has been found we have to quit.
1243 0 : if(!nextEdge){
1244 : break;
1245 : }
1246 :
1247 : // if a new edge has been found which points upwards, we're done, too
1248 0 : if(newDir.y() > 0){
1249 : break;
1250 : }
1251 0 : else if((newDir.y() == 0) && (newDir.x() < 0)){
1252 : break;
1253 : }
1254 :
1255 : // everythings fine. replace the branch edge with the new edge
1256 0 : branch[curBranchInd] = nextEdge;
1257 : // increase the connectedPolygonCount
1258 0 : branch[curBranchInd]->m_numConnectedPolygons++;
1259 : lastBranchInd = curBranchInd;
1260 0 : }
1261 :
1262 : //if(branchInd == 3) break;
1263 0 : ++branchInd;
1264 : }
1265 :
1266 : return true;
1267 0 : }
1268 :
1269 0 : bool TriangleFill_SweepLine(std::vector<int>& facesOut,
1270 : const std::vector<vector3>& srcVrts,
1271 : /*const */std::vector<int>& srcEdges)
1272 : {
1273 : // transform the pointset to 2d
1274 0 : std::vector<vector2> vrts2d(srcVrts.size());
1275 0 : TransformPointSetTo2D(&vrts2d.front(), &srcVrts.front(),
1276 : srcVrts.size());
1277 :
1278 0 : return TriangleFill_SweepLine(facesOut, vrts2d, srcEdges);
1279 0 : }
1280 :
1281 : }// namespace ug
|
