4a7b0af2d39309c521deca07140334e5aaceef36
1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 *
6 * Copyright (C) 2009 Monash University
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 * See the file LICENSE.LGPL distributed with the library.
13 *
14 * Licensees holding a valid commercial license may use this file in
15 * accordance with the commercial license agreement provided with the
16 * library.
17 *
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
21 *
22 * Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net>
23 */
26 #include <cstdlib>
27 #include <cfloat>
28 #include <cmath>
29 #include <set>
30 #include <list>
31 #include <algorithm>
33 #include "libavoid/router.h"
34 #include "libavoid/geomtypes.h"
35 #include "libavoid/shape.h"
36 #include "libavoid/orthogonal.h"
37 #include "libavoid/connector.h"
38 #include "libavoid/vpsc.h"
39 #include "libavoid/assertions.h"
41 #ifdef LIBAVOID_SDL
42 #include <SDL_gfxPrimitives.h>
43 #endif
46 namespace Avoid {
49 static const double CHANNEL_MAX = 100000000;
51 static const size_t XDIM = 0;
52 static const size_t YDIM = 1;
55 class ShiftSegment
56 {
57 public:
58 // For shiftable segments.
59 ShiftSegment(ConnRef *conn, const size_t low, const size_t high,
60 bool isSBend, const size_t dim, double minLim, double maxLim)
61 : connRef(conn),
62 indexLow(low),
63 indexHigh(high),
64 sBend(isSBend),
65 fixed(false),
66 dimension(dim),
67 variable(NULL),
68 minSpaceLimit(minLim),
69 maxSpaceLimit(maxLim)
70 {
71 }
73 // For fixed segments.
74 ShiftSegment(ConnRef *conn, const size_t low, const size_t high,
75 const size_t dim)
76 : connRef(conn),
77 indexLow(low),
78 indexHigh(high),
79 sBend(false),
80 fixed(true),
81 dimension(dim),
82 variable(NULL)
83 {
84 // This has no space to shift.
85 minSpaceLimit = lowPoint()[dim];
86 maxSpaceLimit = lowPoint()[dim];
87 }
89 Point& lowPoint(void)
90 {
91 return connRef->displayRoute().ps[indexLow];
92 }
94 Point& highPoint(void)
95 {
96 return connRef->displayRoute().ps[indexHigh];
97 }
99 const Point& lowPoint(void) const
100 {
101 return connRef->displayRoute().ps[indexLow];
102 }
104 const Point& highPoint(void) const
105 {
106 return connRef->displayRoute().ps[indexHigh];
107 }
109 int fixedOrder(bool& isFixed) const
110 {
111 if (fixed)
112 {
113 isFixed = true;
114 return 0;
115 }
116 if (lowC())
117 {
118 return 1;
119 }
120 else if (highC())
121 {
122 return -1;
123 }
124 return 0;
125 }
127 int order(void) const
128 {
129 if (lowC())
130 {
131 return -1;
132 }
133 else if (highC())
134 {
135 return 1;
136 }
137 return 0;
138 }
140 bool operator<(const ShiftSegment& rhs) const
141 {
142 const Point& lowPt = lowPoint();
143 const Point& rhsLowPt = rhs.lowPoint();
145 if (lowPt[dimension] != rhsLowPt[dimension])
146 {
147 return lowPt[dimension] < rhsLowPt[dimension];
148 }
149 return this < &rhs;
150 }
152 // This counts segments that are colliear and share an endpoint as
153 // overlapping. This allows them to be nudged apart where possible.
154 bool overlapsWith(const ShiftSegment& rhs, const size_t dim) const
155 {
156 size_t altDim = (dim + 1) % 2;
157 const Point& lowPt = lowPoint();
158 const Point& highPt = highPoint();
159 const Point& rhsLowPt = rhs.lowPoint();
160 const Point& rhsHighPt = rhs.highPoint();
161 if ( (lowPt[altDim] <= rhsHighPt[altDim]) &&
162 (rhsLowPt[altDim] <= highPt[altDim]))
163 {
164 if ( (minSpaceLimit <= rhs.maxSpaceLimit) &&
165 (rhs.minSpaceLimit <= maxSpaceLimit))
166 {
167 return true;
168 }
169 }
170 return false;
171 }
173 ConnRef *connRef;
174 size_t indexLow;
175 size_t indexHigh;
176 bool sBend;
177 bool fixed;
178 size_t dimension;
179 Variable *variable;
180 double minSpaceLimit;
181 double maxSpaceLimit;
182 private:
183 bool lowC(void) const
184 {
185 // This is true if this is a cBend and its adjoining points
186 // are at lower positions.
187 if (!sBend && !fixed && (minSpaceLimit == lowPoint()[dimension]))
188 {
189 return true;
190 }
191 return false;
192 }
194 bool highC(void) const
195 {
196 // This is true if this is a cBend and its adjoining points
197 // are at higher positions.
198 if (!sBend && !fixed && (maxSpaceLimit == lowPoint()[dimension]))
199 {
200 return true;
201 }
202 return false;
203 }
204 };
205 typedef std::list<ShiftSegment> ShiftSegmentList;
207 bool cmpShiftSegment(const ShiftSegment& u, const ShiftSegment& v)
208 {
209 return u < v;
210 }
213 struct Node;
214 struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; };
216 typedef std::set<Node*,CmpNodePos> NodeSet;
217 struct Node
218 {
219 ShapeRef *v;
220 VertInf *c;
221 ShiftSegment *ss;
222 double pos;
223 double min[2], max[2];
224 Node *firstAbove, *firstBelow;
225 NodeSet::iterator iter;
227 Node(ShapeRef *v, const double p)
228 : v(v),
229 c(NULL),
230 ss(NULL),
231 pos(p),
232 firstAbove(NULL),
233 firstBelow(NULL)
234 {
235 //COLA_ASSERT(r->width()<1e40);
236 v->polygon().getBoundingRect(&min[0], &min[1], &max[0], &max[1]);
237 }
238 Node(VertInf *c, const double p)
239 : v(NULL),
240 c(c),
241 ss(NULL),
242 pos(p),
243 firstAbove(NULL),
244 firstBelow(NULL)
245 {
246 min[0] = max[0] = c->point.x;
247 min[1] = max[1] = c->point.y;
248 }
249 Node(ShiftSegment *ss, const double p)
250 : v(NULL),
251 c(NULL),
252 ss(ss),
253 pos(p),
254 firstAbove(NULL),
255 firstBelow(NULL)
256 {
257 // These values shouldn't ever be used, so they don't matter.
258 min[0] = max[0] = min[1] = max[1] = 0;
259 }
260 ~Node()
261 {
262 }
263 // Find the first Node above in the scanline that is a shape edge,
264 // and does not have an open or close event at this position (meaning
265 // it is just about to be removed).
266 double firstObstacleAbove(size_t dim)
267 {
268 Node *curr = firstAbove;
269 while (curr && (curr->ss || (curr->max[dim] > pos)))
270 {
271 curr = curr->firstAbove;
272 }
274 if (curr)
275 {
276 return curr->max[dim];
277 }
278 return -DBL_MAX;
279 }
280 // Find the first Node below in the scanline that is a shape edge,
281 // and does not have an open or close event at this position (meaning
282 // it is just about to be removed).
283 double firstObstacleBelow(size_t dim)
284 {
285 Node *curr = firstBelow;
286 while (curr && (curr->ss || (curr->min[dim] < pos)))
287 {
288 curr = curr->firstBelow;
289 }
291 if (curr)
292 {
293 return curr->min[dim];
294 }
295 return DBL_MAX;
296 }
297 // Mark all connector segments above in the scanline as being able
298 // to see to this shape edge.
299 void markShiftSegmentsAbove(size_t dim)
300 {
301 Node *curr = firstAbove;
302 while (curr && (curr->ss || (curr->pos > min[dim])))
303 {
304 if (curr->ss && (curr->pos <= min[dim]))
305 {
306 curr->ss->maxSpaceLimit =
307 std::min(min[dim], curr->ss->maxSpaceLimit);
308 }
309 curr = curr->firstAbove;
310 }
311 }
312 // Mark all connector segments below in the scanline as being able
313 // to see to this shape edge.
314 void markShiftSegmentsBelow(size_t dim)
315 {
316 Node *curr = firstBelow;
317 while (curr && (curr->ss || (curr->pos < max[dim])))
318 {
319 if (curr->ss && (curr->pos >= max[dim]))
320 {
321 curr->ss->minSpaceLimit =
322 std::max(max[dim], curr->ss->minSpaceLimit);
323 }
324 curr = curr->firstBelow;
325 }
326 }
327 bool findFirstPointAboveAndBelow(const size_t dim, double& firstAbovePos,
328 double& firstBelowPos, double& lastAbovePos, double& lastBelowPos)
329 {
330 bool clearVisibility = true;
331 firstAbovePos = -DBL_MAX;
332 firstBelowPos = DBL_MAX;
333 // We start looking left from the right side of the shape,
334 // and vice versa.
335 lastAbovePos = max[dim];
336 lastBelowPos = min[dim];
338 // Find the first blocking edge above this point. Don't count the
339 // edges as we are travelling out of shapes we are inside, but then
340 // mark clearVisibility as false.
341 Node *curr = firstAbove;
342 while (curr && (curr->max[dim] > min[dim]))
343 {
344 lastAbovePos = std::min(curr->min[dim], lastAbovePos);
345 if ((curr->max[dim] >= min[dim]) && (curr->max[dim] <= max[dim]))
346 {
347 lastAbovePos = std::min(curr->max[dim], lastAbovePos);
348 }
349 lastBelowPos = std::max(curr->max[dim], lastBelowPos);
350 clearVisibility = false;
351 curr = curr->firstAbove;
352 }
353 if (curr)
354 {
355 firstAbovePos = curr->max[dim];
356 }
357 while (curr)
358 {
359 // There might be a larger shape after this one in the ordering.
360 if (curr->max[dim] < min[dim])
361 {
362 firstAbovePos = std::max(curr->max[dim], firstAbovePos);
363 }
364 curr = curr->firstAbove;
365 }
367 // Find the first blocking edge below this point. Don't count the
368 // edges as we are travelling out of shapes we are inside, but then
369 // mark clearVisibility as false.
370 curr = firstBelow;
371 while (curr && (curr->min[dim] < max[dim]))
372 {
373 lastBelowPos = std::max(curr->max[dim], lastBelowPos);
374 if ((curr->min[dim] >= min[dim]) && (curr->min[dim] <= max[dim]))
375 {
376 lastBelowPos = std::max(curr->min[dim], lastBelowPos);
377 }
378 lastAbovePos = std::min(curr->min[dim], lastAbovePos);
379 clearVisibility = false;
380 curr = curr->firstBelow;
381 }
382 if (curr)
383 {
384 firstBelowPos = curr->min[dim];
385 }
386 while (curr)
387 {
388 // There might be a larger shape after this one in the ordering.
389 if (curr->min[dim] > max[dim])
390 {
391 firstBelowPos = std::min(curr->min[dim], firstBelowPos);
392 }
393 curr = curr->firstBelow;
394 }
396 return clearVisibility;
397 }
398 double firstPointAbove(size_t dim)
399 {
400 Node *curr = firstAbove;
401 while (curr && (curr->max[dim] >= pos))
402 {
403 curr = curr->firstAbove;
404 }
406 if (curr)
407 {
408 return curr->max[dim];
409 }
410 return -DBL_MAX;
411 }
412 double firstPointBelow(size_t dim)
413 {
414 Node *curr = firstBelow;
415 while (curr && (curr->min[dim] <= pos))
416 {
417 curr = curr->firstBelow;
418 }
420 if (curr)
421 {
422 return curr->min[dim];
423 }
424 return DBL_MAX;
425 }
426 // This is a bit inefficient, but we won't need to do it once we have
427 // connection points.
428 bool isInsideShape(size_t dimension)
429 {
430 for (Node *curr = firstBelow; curr; curr = curr->firstBelow)
431 {
432 if ((curr->min[dimension] < pos) && (pos < curr->max[dimension]))
433 {
434 return true;
435 }
436 }
437 for (Node *curr = firstAbove; curr; curr = curr->firstAbove)
438 {
439 if ((curr->min[dimension] < pos) && (pos < curr->max[dimension]))
440 {
441 return true;
442 }
443 }
444 return false;
445 }
446 };
449 bool CmpNodePos::operator() (const Node* u, const Node* v) const
450 {
451 if (u->pos != v->pos)
452 {
453 return u->pos < v->pos;
454 }
456 // Use the pointers to the base objects to differentiate them.
457 void *up = (u->v) ? (void *) u->v :
458 ((u->c) ? (void *) u->c : (void *) u->ss);
459 void *vp = (v->v) ? (void *) v->v :
460 ((v->c) ? (void *) v->c : (void *) v->ss);
461 return up < vp;
462 }
465 // Note: Open must come first.
466 typedef enum {
467 Open = 1,
468 SegOpen = 2,
469 ConnPoint = 3,
470 SegClose = 4,
471 Close = 5
472 } EventType;
475 struct Event
476 {
477 Event(EventType t, Node *v, double p)
478 : type(t),
479 v(v),
480 pos(p)
481 {};
482 EventType type;
483 Node *v;
484 double pos;
485 };
487 Event **events;
490 // Used for quicksort. Must return <0, 0, or >0.
491 int compare_events(const void *a, const void *b)
492 {
493 Event *ea = *(Event**) a;
494 Event *eb = *(Event**) b;
495 if (ea->pos != eb->pos)
496 {
497 return (ea->pos < eb->pos) ? -1 : 1;
498 }
499 if (ea->type != eb->type)
500 {
501 return ea->type - eb->type;
502 }
503 COLA_ASSERT(ea->v != eb->v);
504 return ea->v - eb->v;
505 }
508 // Returns a bitfield of the direction of visibility (in this dimension)
509 // made up of ConnDirDown (for visibility towards lower position values)
510 // and ConnDirUp (for visibility towards higher position values).
511 //
512 static ConnDirFlags getPosVertInfDirection(VertInf *v, size_t dim)
513 {
514 if (dim == XDIM) // X-dimension
515 {
516 unsigned int dirs = v->visDirections & (ConnDirLeft | ConnDirRight);
517 if (dirs == (ConnDirLeft | ConnDirRight))
518 {
519 return (ConnDirDown | ConnDirUp);
520 }
521 else if (dirs == ConnDirLeft)
522 {
523 return ConnDirDown;
524 }
525 else if (dirs == ConnDirRight)
526 {
527 return ConnDirUp;
528 }
529 }
530 else if (dim == YDIM) // Y-dimension
531 {
532 unsigned int dirs = v->visDirections & (ConnDirDown | ConnDirUp);
533 if (dirs == (ConnDirDown | ConnDirUp))
534 {
535 return (ConnDirDown | ConnDirUp);
536 }
537 else if (dirs == ConnDirDown)
538 {
539 // For libavoid the Y-axis points downwards, so in terms of
540 // smaller or larger position values, Down is Up and vice versa.
541 return ConnDirUp;
542 }
543 else if (dirs == ConnDirUp)
544 {
545 // For libavoid the Y-axis points downwards, so in terms of
546 // smaller or larger position values, Down is Up and vice versa.
547 return ConnDirDown;
548 }
549 }
551 // Can occur for ConnDirNone visibility.
552 return ConnDirNone;
553 }
556 struct PosVertInf
557 {
558 PosVertInf(double p, VertInf *vI, ConnDirFlags d = ConnDirNone)
559 : pos(p),
560 vert(vI),
561 dir(d)
562 {
563 }
565 bool operator<(const PosVertInf& rhs) const
566 {
567 if (pos != rhs.pos)
568 {
569 return pos < rhs.pos;
570 }
571 return vert < rhs.vert;
572 }
574 double pos;
575 VertInf *vert;
577 // A bitfield marking the direction of visibility (in this dimension)
578 // made up of ConnDirDown (for visibility towards lower position values)
579 // and ConnDirUp (for visibility towards higher position values).
580 //
581 ConnDirFlags dir;
582 };
585 struct CmpVertInf
586 {
587 bool operator()(const VertInf* u, const VertInf* v) const
588 {
589 // Comparator for VertSet, an ordered set of VertInf pointers.
590 // It is assumed vertical sets of points will all have the same
591 // x position and horizontal sets all share a y position, so this
592 // method can be used to sort both these sets.
593 COLA_ASSERT((u->point.x == v->point.x) || (u->point.y == v->point.y));
594 if (u->point.x != v->point.x)
595 {
596 return u->point.x < v->point.x;
597 }
598 else if (u->point.y != v->point.y)
599 {
600 return u->point.y < v->point.y;
601 }
602 return u < v;
603 }
604 };
607 typedef std::set<VertInf *, CmpVertInf> VertSet;
609 // A set of points to break the line segment,
610 // along with vertices for these points.
611 typedef std::set<PosVertInf> BreakpointSet;
613 // Temporary structure used to store the possible horizontal visibility
614 // lines arising from the vertical sweep.
615 class LineSegment
616 {
617 public:
618 LineSegment(const double& b, const double& f, const double& p,
619 bool /*ss*/ = false, VertInf *bvi = NULL, VertInf *fvi = NULL)
620 : begin(b),
621 finish(f),
622 pos(p),
623 shapeSide(false)
624 {
625 COLA_ASSERT(begin < finish);
627 if (bvi)
628 {
629 vertInfs.insert(bvi);
630 }
631 if (fvi)
632 {
633 vertInfs.insert(fvi);
634 }
635 }
637 LineSegment(const double& bf, const double& p, VertInf *bfvi = NULL)
638 : begin(bf),
639 finish(bf),
640 pos(p),
641 shapeSide(false)
642 {
643 if (bfvi)
644 {
645 vertInfs.insert(bfvi);
646 }
647 }
649 // Order by begin, pos, finish.
650 bool operator<(const LineSegment& rhs) const
651 {
652 if (begin != rhs.begin)
653 {
654 return begin < rhs.begin;
655 }
656 if (pos != rhs.pos)
657 {
658 return pos < rhs.pos;
659 }
660 if (finish != rhs.finish)
661 {
662 return finish < rhs.finish;
663 }
664 COLA_ASSERT(shapeSide == rhs.shapeSide);
665 return false;
666 }
668 bool overlaps(const LineSegment& rhs) const
669 {
670 if ((begin == rhs.begin) && (pos == rhs.pos) &&
671 (finish == rhs.finish))
672 {
673 // Lines are exactly equal.
674 return true;
675 }
677 if (pos == rhs.pos)
678 {
679 if (((begin >= rhs.begin) && (begin <= rhs.finish)) ||
680 ((rhs.begin >= begin) && (rhs.begin <= finish)) )
681 {
682 // They are colinear and overlap by some amount.
683 return true;
684 }
685 }
686 return false;
687 }
689 void mergeVertInfs(const LineSegment& segment)
690 {
691 begin = std::min(begin, segment.begin);
692 finish = std::max(finish, segment.finish);
693 vertInfs.insert(segment.vertInfs.begin(), segment.vertInfs.end());
694 }
696 VertInf *beginVertInf(void) const
697 {
698 if (vertInfs.empty())
699 {
700 return NULL;
701 }
702 return *vertInfs.begin();
703 }
704 VertInf *finishVertInf(void) const
705 {
706 if (vertInfs.empty())
707 {
708 return NULL;
709 }
710 return *vertInfs.rbegin();
711 }
713 VertInf *commitPositionX(Router *router, double posX)
714 {
715 VertInf *found = NULL;
716 for (VertSet::iterator v = vertInfs.begin();
717 v != vertInfs.end(); ++v)
718 {
719 if ((*v)->point.x == posX)
720 {
721 found = *v;
722 break;
723 }
724 }
725 if (!found)
726 {
727 found = new VertInf(router, dummyOrthogID, Point(posX, pos));
728 vertInfs.insert(found);
729 }
730 return found;
731 }
732 // Set begin endpoint vertex if none has been assigned.
733 void commitBegin(Router *router, VertInf *vert = NULL)
734 {
735 if (vert)
736 {
737 vertInfs.insert(vert);
738 }
740 if (vertInfs.empty() ||
741 ((*vertInfs.begin())->point.x != begin))
742 {
743 vertInfs.insert(new
744 VertInf(router, dummyOrthogID, Point(begin, pos)));
745 }
746 }
748 // Set begin endpoint vertex if none has been assigned.
749 void commitFinish(Router *router, VertInf *vert = NULL)
750 {
751 if (vert)
752 {
753 vertInfs.insert(vert);
754 }
756 if (vertInfs.empty() ||
757 ((*vertInfs.rbegin())->point.x != finish))
758 {
759 vertInfs.insert(new
760 VertInf(router, dummyOrthogID, Point(finish, pos)));
761 }
762 }
764 // Converts a section of the points list to a set of breakPoints.
765 // Returns the first of the intersection points occuring at finishPos.
766 VertSet::iterator addSegmentsUpTo(Router */*router*/, double finishPos)
767 {
768 VertSet::iterator firstIntersectionPt = vertInfs.end();
769 for (VertSet::iterator vert = vertInfs.begin();
770 vert != vertInfs.end(); ++vert)
771 {
772 if ((*vert)->point.x > finishPos)
773 {
774 // We're done.
775 break;
776 }
778 breakPoints.insert(PosVertInf((*vert)->point.x, (*vert),
779 getPosVertInfDirection(*vert, XDIM)));
781 if ((firstIntersectionPt == vertInfs.end()) &&
782 ((*vert)->point.x == finishPos))
783 {
784 firstIntersectionPt = vert;
785 }
786 }
787 // Returns the first of the intersection points at finishPos.
788 return firstIntersectionPt;
789 }
791 // Add visibility edge(s) for this segment. There may be multiple if
792 // one of the endpoints is shared by multiple connector endpoints.
793 void addEdgeHorizontal(Router *router)
794 {
795 commitBegin(router);
796 commitFinish(router);
798 addSegmentsUpTo(router, finish);
799 }
801 // Add visibility edge(s) for this segment up until an intersection.
802 // Then, move the segment beginning to the intersection point, so we
803 // later only consider the remainder of the segment.
804 // There may be multiple segments added to the graph if the beginning
805 // endpoint of the segment is shared by multiple connector endpoints.
806 VertSet addEdgeHorizontalTillIntersection(Router *router,
807 LineSegment& vertLine)
808 {
809 VertSet intersectionSet;
811 commitBegin(router);
813 // Does a vertex already exist for this point.
814 commitPositionX(router, vertLine.pos);
816 // Generate segments and set end iterator to the first point
817 // at the intersection position.
818 VertSet::iterator restBegin = addSegmentsUpTo(router, vertLine.pos);
820 // Add the intersections points to intersectionSet.
821 VertSet::iterator restEnd = restBegin;
822 while ((restEnd != vertInfs.end()) &&
823 (*restEnd)->point.x == vertLine.pos)
824 {
825 ++restEnd;
826 }
827 intersectionSet.insert(restBegin, restEnd);
829 // Adjust segment to remove processed portion.
830 begin = vertLine.pos;
831 vertInfs.erase(vertInfs.begin(), restBegin);
833 return intersectionSet;
834 }
836 // Insert vertical breakpoints.
837 void insertBreakpointsBegin(Router *router, LineSegment& vertLine)
838 {
839 VertInf *vert = NULL;
840 if (pos == vertLine.begin && vertLine.beginVertInf())
841 {
842 vert = vertLine.beginVertInf();
843 }
844 else if (pos == vertLine.finish && vertLine.finishVertInf())
845 {
846 vert = vertLine.finishVertInf();
847 }
848 commitBegin(router, vert);
850 for (VertSet::iterator v = vertInfs.begin();
851 v != vertInfs.end(); ++v)
852 {
853 if ((*v)->point.x == begin)
854 {
855 vertLine.breakPoints.insert(PosVertInf(pos, *v,
856 getPosVertInfDirection(*v, YDIM)));
857 }
858 }
859 }
861 // Insert vertical breakpoints.
862 void insertBreakpointsFinish(Router *router, LineSegment& vertLine)
863 {
864 VertInf *vert = NULL;
865 if (pos == vertLine.begin && vertLine.beginVertInf())
866 {
867 vert = vertLine.beginVertInf();
868 }
869 else if (pos == vertLine.finish && vertLine.finishVertInf())
870 {
871 vert = vertLine.finishVertInf();
872 }
873 commitFinish(router, vert);
875 for (VertSet::iterator v = vertInfs.begin();
876 v != vertInfs.end(); ++v)
877 {
878 if ((*v)->point.x == finish)
879 {
880 vertLine.breakPoints.insert(PosVertInf(pos, *v,
881 getPosVertInfDirection(*v, YDIM)));
882 }
883 }
884 }
885 void generateVisibilityEdgesFromBreakpointSet(Router *router, size_t dim)
886 {
887 if ((breakPoints.begin())->pos != begin)
888 {
889 if (!beginVertInf())
890 {
891 Point point(pos, pos);
892 point[dim] = begin;
893 // Add begin point if it didn't intersect another line.
894 VertInf *vert = new VertInf(router, dummyOrthogID, point);
895 breakPoints.insert(PosVertInf(begin, vert));
896 }
897 }
898 if ((breakPoints.rbegin())->pos != finish)
899 {
900 if (!finishVertInf())
901 {
902 Point point(pos, pos);
903 point[dim] = finish;
904 // Add finish point if it didn't intersect another line.
905 VertInf *vert = new VertInf(router, dummyOrthogID, point);
906 breakPoints.insert(PosVertInf(finish, vert));
907 }
908 }
910 const bool orthogonal = true;
911 BreakpointSet::iterator vert, last;
912 for (vert = last = breakPoints.begin(); vert != breakPoints.end();)
913 {
914 BreakpointSet::iterator firstPrev = last;
915 while (last->vert->point[dim] != vert->vert->point[dim])
916 {
917 COLA_ASSERT(vert != last);
918 // Assert points are not at the same position.
919 COLA_ASSERT(vert->vert->point != last->vert->point);
921 if ( !(vert->vert->id.isShape || last->vert->id.isShape))
922 {
923 // Here we have a pair of two endpoints that are both
924 // connector endpoints and both are inside a shape.
926 // Give vert visibility back to the first non-connector
927 // endpoint vertex (i.e., the side of the shape).
928 BreakpointSet::iterator side = last;
929 while (!side->vert->id.isShape)
930 {
931 if (side == breakPoints.begin())
932 {
933 break;
934 }
935 --side;
936 }
937 bool canSeeDown = (vert->dir & ConnDirDown);
938 if (canSeeDown && side->vert->id.isShape)
939 {
940 EdgeInf *edge = new
941 EdgeInf(side->vert, vert->vert, orthogonal);
942 edge->setDist(vert->vert->point[dim] -
943 side->vert->point[dim]);
944 }
946 // Give last visibility back to the first non-connector
947 // endpoint vertex (i.e., the side of the shape).
948 side = vert;
949 while ((side != breakPoints.end()) &&
950 !side->vert->id.isShape)
951 {
952 ++side;
953 }
954 bool canSeeUp = (last->dir & ConnDirUp);
955 if (canSeeUp && (side != breakPoints.end()))
956 {
957 EdgeInf *edge = new
958 EdgeInf(last->vert, side->vert, orthogonal);
959 edge->setDist(side->vert->point[dim] -
960 last->vert->point[dim]);
961 }
962 }
964 // The normal case.
965 //
966 // Note: It's okay to give two connector endpoints visbility
967 // here since we only consider the partner endpoint as a
968 // candidate while searching if it is the other endpoint of
969 // the connector in question.
970 //
971 bool generateEdge = true;
972 if (!last->vert->id.isShape && !(last->dir & ConnDirUp))
973 {
974 generateEdge = false;
975 }
976 else if (!vert->vert->id.isShape && !(vert->dir & ConnDirDown))
977 {
978 generateEdge = false;
979 }
980 if (generateEdge)
981 {
982 EdgeInf *edge =
983 new EdgeInf(last->vert, vert->vert, orthogonal);
984 edge->setDist(vert->vert->point[dim] -
985 last->vert->point[dim]);
986 }
988 ++last;
989 }
991 ++vert;
993 if ((vert != breakPoints.end()) &&
994 (last->vert->point[dim] == vert->vert->point[dim]))
995 {
996 // Still looking at same pair, just reset prev number pointer.
997 last = firstPrev;
998 }
999 else
1000 {
1001 // vert has moved to the beginning of a number number group.
1002 // Last is now in the right place, so do nothing.
1003 }
1004 }
1005 }
1007 double begin;
1008 double finish;
1009 double pos;
1010 bool shapeSide;
1012 VertSet vertInfs;
1013 BreakpointSet breakPoints;
1014 private:
1015 // MSVC wants to generate the assignment operator and the default
1016 // constructor, but fails. Therefore we declare them private and
1017 // don't implement them.
1018 LineSegment & operator=(LineSegment const &);
1019 LineSegment();
1020 };
1022 typedef std::list<LineSegment> SegmentList;
1024 class SegmentListWrapper
1025 {
1026 public:
1027 LineSegment *insert(LineSegment segment)
1028 {
1029 SegmentList::iterator found = _list.end();
1030 for (SegmentList::iterator curr = _list.begin();
1031 curr != _list.end(); ++curr)
1032 {
1033 if (curr->overlaps(segment))
1034 {
1035 if (found != _list.end())
1036 {
1037 // This is not the first segment that overlaps,
1038 // so we need to merge and then delete an existing
1039 // segment.
1040 curr->mergeVertInfs(*found);
1041 _list.erase(found);
1042 found = curr;
1043 }
1044 else
1045 {
1046 // This is the first overlapping segment, so just
1047 // merge the new segment with this one.
1048 curr->mergeVertInfs(segment);
1049 found = curr;
1050 }
1051 }
1052 }
1054 if (found == _list.end())
1055 {
1056 // Add this line.
1057 _list.push_back(segment);
1058 return &(_list.back());
1059 }
1061 return &(*found);
1062 }
1063 SegmentList& list(void)
1064 {
1065 return _list;
1066 }
1067 private:
1068 SegmentList _list;
1069 };
1072 // Given a router instance and a set of possible horizontal segments, and a
1073 // possible vertical visibility segment, compute and add edges to the
1074 // orthogonal visibility graph for all the visibility edges.
1075 static void intersectSegments(Router *router, SegmentList& segments,
1076 LineSegment& vertLine)
1077 {
1078 COLA_ASSERT(vertLine.beginVertInf() == NULL);
1079 COLA_ASSERT(vertLine.finishVertInf() == NULL);
1080 for (SegmentList::iterator it = segments.begin(); it != segments.end(); )
1081 {
1082 LineSegment& horiLine = *it;
1084 bool inVertSegRegion = ((vertLine.begin <= horiLine.pos) &&
1085 (vertLine.finish >= horiLine.pos));
1087 if (horiLine.finish < vertLine.pos)
1088 {
1089 // Add horizontal visibility segment.
1090 horiLine.addEdgeHorizontal(router);
1092 size_t dim = XDIM; // x-dimension
1093 horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim);
1095 // We've now swept past this horizontal segment, so delete.
1096 it = segments.erase(it);
1097 continue;
1098 }
1099 else if (horiLine.begin > vertLine.pos)
1100 {
1101 // We've yet to reach this segment in the sweep, so ignore.
1102 ++it;
1103 continue;
1104 }
1105 else if (horiLine.begin == vertLine.pos)
1106 {
1107 if (inVertSegRegion)
1108 {
1109 horiLine.insertBreakpointsBegin(router, vertLine);
1110 }
1111 }
1112 else if (horiLine.finish == vertLine.pos)
1113 {
1114 if (inVertSegRegion)
1115 {
1116 // Add horizontal visibility segment.
1117 horiLine.addEdgeHorizontal(router);
1119 horiLine.insertBreakpointsFinish(router, vertLine);
1121 size_t dim = XDIM; // x-dimension
1122 horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim);
1124 // And we've now finished with the segment, so delete.
1125 it = segments.erase(it);
1126 continue;
1127 }
1128 }
1129 else
1130 {
1131 COLA_ASSERT(horiLine.begin < vertLine.pos);
1132 COLA_ASSERT(horiLine.finish > vertLine.pos);
1134 if (inVertSegRegion)
1135 {
1136 // Add horizontal visibility segment.
1137 VertSet intersectionVerts =
1138 horiLine.addEdgeHorizontalTillIntersection(
1139 router, vertLine);
1141 for (VertSet::iterator v = intersectionVerts.begin();
1142 v != intersectionVerts.end(); ++v)
1143 {
1144 vertLine.breakPoints.insert(PosVertInf(horiLine.pos, *v,
1145 getPosVertInfDirection(*v, YDIM)));
1146 }
1147 }
1148 }
1149 ++it;
1150 }
1152 // Split breakPoints set into visibility segments.
1153 size_t dimension = YDIM; // y-dimension
1154 vertLine.generateVisibilityEdgesFromBreakpointSet(router, dimension);
1155 }
1158 // Processes an event for the vertical sweep used for computing the static
1159 // orthogonal visibility graph. This adds possible visibility sgments to
1160 // the segments list.
1161 // The first pass is adding the event to the scanline, the second is for
1162 // processing the event and the third for removing it from the scanline.
1163 static void processEventVert(Router *router, NodeSet& scanline,
1164 SegmentListWrapper& segments, Event *e, unsigned int pass)
1165 {
1166 Node *v = e->v;
1168 if ( ((pass == 1) && (e->type == Open)) ||
1169 ((pass == 2) && (e->type == ConnPoint)) )
1170 {
1171 std::pair<NodeSet::iterator, bool> result = scanline.insert(v);
1172 v->iter = result.first;
1173 COLA_ASSERT(result.second);
1175 NodeSet::iterator it = v->iter;
1176 // Work out neighbours
1177 if (it != scanline.begin())
1178 {
1179 Node *u = *(--it);
1180 v->firstAbove = u;
1181 u->firstBelow = v;
1182 }
1183 it = v->iter;
1184 if (++it != scanline.end())
1185 {
1186 Node *u = *it;
1187 v->firstBelow = u;
1188 u->firstAbove = v;
1189 }
1190 }
1192 if (pass == 2)
1193 {
1194 if ((e->type == Open) || (e->type == Close))
1195 {
1196 // Shape edge positions.
1197 double minShape = v->min[0];
1198 double maxShape = v->max[0];
1199 // As far as we can see.
1200 double minLimit, maxLimit;
1201 double minLimitMax, maxLimitMin;
1202 v->findFirstPointAboveAndBelow(0, minLimit, maxLimit,
1203 minLimitMax, maxLimitMin);
1205 // Only difference between Open and Close is whether the line
1206 // segments are at the top or bottom of the shape. Decide here.
1207 double lineY = (e->type == Open) ? v->min[1] : v->max[1];
1209 if (minLimitMax >= maxLimitMin)
1210 {
1211 // Insert possible visibility segments.
1212 VertInf *vI1 = new VertInf(router, dummyOrthogID,
1213 Point(minShape, lineY));
1214 VertInf *vI2 = new VertInf(router, dummyOrthogID,
1215 Point(maxShape, lineY));
1217 // There are no overlapping shapes, so give full visibility.
1218 if (minLimit < minShape)
1219 {
1220 segments.insert(LineSegment(minLimit, minShape, lineY,
1221 true, NULL, vI1));
1222 }
1223 segments.insert(LineSegment(minShape, maxShape, lineY,
1224 true, vI1, vI2));
1225 if (maxShape < maxLimit)
1226 {
1227 segments.insert(LineSegment(maxShape, maxLimit, lineY,
1228 true, vI2, NULL));
1229 }
1230 }
1231 else
1232 {
1233 if ((minLimitMax > minLimit) && (minLimitMax >= minShape))
1234 {
1235 segments.insert(LineSegment(minLimit, minLimitMax, lineY,
1236 true, NULL, NULL));
1237 }
1238 if ((maxLimitMin < maxLimit) && (maxLimitMin <= maxShape))
1239 {
1240 segments.insert(LineSegment(maxLimitMin, maxLimit, lineY,
1241 true, NULL, NULL));
1242 }
1243 }
1244 }
1245 else if (e->type == ConnPoint)
1246 {
1247 // Connection point.
1248 VertInf *centreVert = e->v->c;
1249 Point& cp = centreVert->point;
1251 // As far as we can see.
1252 double minLimit = v->firstPointAbove(0);
1253 double maxLimit = v->firstPointBelow(0);
1254 bool inShape = v->isInsideShape(0);
1256 LineSegment *line1 = NULL, *line2 = NULL;
1257 if (!inShape || (centreVert->visDirections & ConnDirLeft))
1258 {
1259 line1 = segments.insert(LineSegment(minLimit, cp.x, e->pos,
1260 true, NULL, centreVert));
1261 }
1262 if (!inShape || (centreVert->visDirections & ConnDirRight))
1263 {
1264 line2 = segments.insert(LineSegment(cp.x, maxLimit, e->pos,
1265 true, centreVert, NULL));
1266 }
1267 if (!line1 && !line2)
1268 {
1269 // Add a point segment for the centre point.
1270 segments.insert(LineSegment(cp.x, e->pos, centreVert));
1271 }
1273 if (!inShape)
1274 {
1275 // This is not contained within a shape so add a normal
1276 // visibility graph point here too (since paths won't route
1277 // *through* connector endpoint vertices).
1278 if (line1 || line2)
1279 {
1280 VertInf *cent = new VertInf(router, dummyOrthogID, cp);
1281 if (line1)
1282 {
1283 line1->vertInfs.insert(cent);
1284 }
1285 if (line2)
1286 {
1287 line2->vertInfs.insert(cent);
1288 }
1289 }
1290 }
1291 }
1292 }
1294 if ( ((pass == 3) && (e->type == Close)) ||
1295 ((pass == 2) && (e->type == ConnPoint)) )
1296 {
1297 // Clean up neighbour pointers.
1298 Node *l = v->firstAbove, *r = v->firstBelow;
1299 if (l != NULL)
1300 {
1301 l->firstBelow = v->firstBelow;
1302 }
1303 if (r != NULL)
1304 {
1305 r->firstAbove = v->firstAbove;
1306 }
1308 if (e->type == ConnPoint)
1309 {
1310 scanline.erase(v->iter);
1311 delete v;
1312 }
1313 else // if (e->type == Close)
1314 {
1315 size_t result;
1316 result = scanline.erase(v);
1317 COLA_ASSERT(result == 1);
1318 delete v;
1319 }
1320 }
1321 }
1324 // Processes an event for the vertical sweep used for computing the static
1325 // orthogonal visibility graph. This adds possible visibility sgments to
1326 // the segments list.
1327 // The first pass is adding the event to the scanline, the second is for
1328 // processing the event and the third for removing it from the scanline.
1329 static void processEventHori(Router */*router*/, NodeSet& scanline,
1330 SegmentListWrapper& segments, Event *e, unsigned int pass)
1331 {
1332 Node *v = e->v;
1334 if ( ((pass == 1) && (e->type == Open)) ||
1335 ((pass == 2) && (e->type == ConnPoint)) )
1336 {
1337 std::pair<NodeSet::iterator, bool> result = scanline.insert(v);
1338 v->iter = result.first;
1339 COLA_ASSERT(result.second);
1341 NodeSet::iterator it = v->iter;
1342 // Work out neighbours
1343 if (it != scanline.begin())
1344 {
1345 Node *u = *(--it);
1346 v->firstAbove = u;
1347 u->firstBelow = v;
1348 }
1349 it = v->iter;
1350 if (++it != scanline.end())
1351 {
1352 Node *u = *it;
1353 v->firstBelow = u;
1354 u->firstAbove = v;
1355 }
1356 }
1358 if (pass == 2)
1359 {
1360 if ((e->type == Open) || (e->type == Close))
1361 {
1362 // Shape edge positions.
1363 double minShape = v->min[1];
1364 double maxShape = v->max[1];
1365 // As far as we can see.
1366 double minLimit, maxLimit;
1367 double minLimitMax, maxLimitMin;
1368 v->findFirstPointAboveAndBelow(1, minLimit, maxLimit,
1369 minLimitMax, maxLimitMin);
1371 // Only difference between Open and Close is whether the line
1372 // segments are at the left or right of the shape. Decide here.
1373 double lineX = (e->type == Open) ? v->min[0] : v->max[0];
1375 if (minLimitMax >= maxLimitMin)
1376 {
1377 LineSegment vertSeg = LineSegment(minLimit, maxLimit, lineX);
1378 segments.insert(vertSeg);
1379 }
1380 else
1381 {
1382 if ((minLimitMax > minLimit) && (minLimitMax >= minShape))
1383 {
1384 LineSegment vertSeg =
1385 LineSegment(minLimit, minLimitMax, lineX);
1386 segments.insert(vertSeg);
1387 }
1388 if ((maxLimitMin < maxLimit) && (maxLimitMin <= maxShape))
1389 {
1390 LineSegment vertSeg =
1391 LineSegment(maxLimitMin, maxLimit, lineX);
1392 segments.insert(vertSeg);
1393 }
1394 }
1395 }
1396 else if (e->type == ConnPoint)
1397 {
1398 // Connection point.
1399 VertInf *centreVert = e->v->c;
1400 Point& cp = centreVert->point;
1402 // As far as we can see.
1403 double minLimit = v->firstPointAbove(1);
1404 double maxLimit = v->firstPointBelow(1);
1405 bool inShape = v->isInsideShape(1);
1407 if (!inShape || (centreVert->visDirections & ConnDirUp))
1408 {
1409 segments.insert(LineSegment(minLimit, cp.y, e->pos));
1410 }
1411 if (!inShape || (centreVert->visDirections & ConnDirDown))
1412 {
1413 segments.insert(LineSegment(cp.y, maxLimit, e->pos));
1414 }
1415 }
1416 }
1418 if ( ((pass == 3) && (e->type == Close)) ||
1419 ((pass == 2) && (e->type == ConnPoint)) )
1420 {
1421 // Clean up neighbour pointers.
1422 Node *l = v->firstAbove, *r = v->firstBelow;
1423 if (l != NULL)
1424 {
1425 l->firstBelow = v->firstBelow;
1426 }
1427 if (r != NULL)
1428 {
1429 r->firstAbove = v->firstAbove;
1430 }
1432 if (e->type == ConnPoint)
1433 {
1434 scanline.erase(v->iter);
1435 delete v;
1436 }
1437 else // if (e->type == Close)
1438 {
1439 size_t result;
1440 result = scanline.erase(v);
1441 COLA_ASSERT(result == 1);
1442 delete v;
1443 }
1444 }
1445 }
1448 extern void generateStaticOrthogonalVisGraph(Router *router)
1449 {
1450 const size_t n = router->shapeRefs.size();
1451 const unsigned cpn = router->vertices.connsSize();
1452 // Set up the events for the vertical sweep.
1453 size_t totalEvents = (2 * n) + cpn;
1454 events = new Event*[totalEvents];
1455 unsigned ctr = 0;
1456 ShapeRefList::iterator shRefIt = router->shapeRefs.begin();
1457 for (unsigned i = 0; i < n; i++)
1458 {
1459 ShapeRef *shRef = *shRefIt;
1460 double minX, minY, maxX, maxY;
1461 shRef->polygon().getBoundingRect(&minX, &minY, &maxX, &maxY);
1462 double midX = minX + ((maxX - minX) / 2);
1463 Node *v = new Node(shRef, midX);
1464 events[ctr++] = new Event(Open, v, minY);
1465 events[ctr++] = new Event(Close, v, maxY);
1467 ++shRefIt;
1468 }
1469 for (VertInf *curr = router->vertices.connsBegin();
1470 curr && (curr != router->vertices.shapesBegin());
1471 curr = curr->lstNext)
1472 {
1473 Point& point = curr->point;
1475 Node *v = new Node(curr, point.x);
1476 events[ctr++] = new Event(ConnPoint, v, point.y);
1477 }
1478 qsort((Event*)events, (size_t) totalEvents, sizeof(Event*), compare_events);
1480 // Process the vertical sweep.
1481 // We do multiple passes over sections of the list so we can add relevant
1482 // entries to the scanline that might follow, before process them.
1483 SegmentListWrapper segments;
1484 NodeSet scanline;
1485 double thisPos = (totalEvents > 0) ? events[0]->pos : 0;
1486 unsigned int posStartIndex = 0;
1487 unsigned int posFinishIndex = 0;
1488 for (unsigned i = 0; i <= totalEvents; ++i)
1489 {
1490 // If we have finished the current scanline or all events, then we
1491 // process the events on the current scanline in a couple of passes.
1492 if ((i == totalEvents) || (events[i]->pos != thisPos))
1493 {
1494 posFinishIndex = i;
1495 for (int pass = 2; pass <= 3; ++pass)
1496 {
1497 for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
1498 {
1499 processEventVert(router, scanline, segments,
1500 events[j], pass);
1501 }
1502 }
1504 if (i == totalEvents)
1505 {
1506 // We have cleaned up, so we can now break out of loop.
1507 break;
1508 }
1510 thisPos = events[i]->pos;
1511 posStartIndex = i;
1512 }
1514 // Do the first sweep event handling -- building the correct
1515 // structure of the scanline.
1516 const int pass = 1;
1517 processEventVert(router, scanline, segments, events[i], pass);
1518 }
1519 COLA_ASSERT(scanline.size() == 0);
1520 for (unsigned i = 0; i < totalEvents; ++i)
1521 {
1522 delete events[i];
1523 }
1525 segments.list().sort();
1527 // Set up the events for the horizontal sweep.
1528 SegmentListWrapper vertSegments;
1529 ctr = 0;
1530 shRefIt = router->shapeRefs.begin();
1531 for (unsigned i = 0; i < n; i++)
1532 {
1533 ShapeRef *shRef = *shRefIt;
1534 double minX, minY, maxX, maxY;
1535 shRef->polygon().getBoundingRect(&minX, &minY, &maxX, &maxY);
1536 double midY = minY + ((maxY - minY) / 2);
1537 Node *v = new Node(shRef, midY);
1538 events[ctr++] = new Event(Open, v, minX);
1539 events[ctr++] = new Event(Close, v, maxX);
1541 ++shRefIt;
1542 }
1543 for (VertInf *curr = router->vertices.connsBegin();
1544 curr && (curr != router->vertices.shapesBegin());
1545 curr = curr->lstNext)
1546 {
1547 Point& point = curr->point;
1549 Node *v = new Node(curr, point.y);
1550 events[ctr++] = new Event(ConnPoint, v, point.x);
1551 }
1552 qsort((Event*)events, (size_t) totalEvents, sizeof(Event*), compare_events);
1554 // Process the horizontal sweep
1555 thisPos = (totalEvents > 0) ? events[0]->pos : 0;
1556 posStartIndex = 0;
1557 posFinishIndex = 0;
1558 for (unsigned i = 0; i <= totalEvents; ++i)
1559 {
1560 // If we have finished the current scanline or all events, then we
1561 // process the events on the current scanline in a couple of passes.
1562 if ((i == totalEvents) || (events[i]->pos != thisPos))
1563 {
1564 posFinishIndex = i;
1565 for (int pass = 2; pass <= 3; ++pass)
1566 {
1567 for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
1568 {
1569 processEventHori(router, scanline, vertSegments,
1570 events[j], pass);
1571 }
1572 }
1574 // Process the merged line segments.
1575 vertSegments.list().sort();
1576 for (SegmentList::iterator curr = vertSegments.list().begin();
1577 curr != vertSegments.list().end(); ++curr)
1578 {
1579 intersectSegments(router, segments.list(), *curr);
1580 }
1581 vertSegments.list().clear();
1583 if (i == totalEvents)
1584 {
1585 // We have cleaned up, so we can now break out of loop.
1586 break;
1587 }
1589 thisPos = events[i]->pos;
1590 posStartIndex = i;
1591 }
1593 // Do the first sweep event handling -- building the correct
1594 // structure of the scanline.
1595 const int pass = 1;
1596 processEventHori(router, scanline, vertSegments, events[i], pass);
1597 }
1598 COLA_ASSERT(scanline.size() == 0);
1599 for (unsigned i = 0; i < totalEvents; ++i)
1600 {
1601 delete events[i];
1602 }
1603 delete [] events;
1605 // Add portions of the horizontal line that are after the final vertical
1606 // position we considered.
1607 for (SegmentList::iterator it = segments.list().begin();
1608 it != segments.list().end(); )
1609 {
1610 LineSegment& horiLine = *it;
1612 horiLine.addEdgeHorizontal(router);
1614 size_t dim = XDIM; // x-dimension
1615 horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim);
1617 it = segments.list().erase(it);
1618 }
1619 }
1622 //============================================================================
1623 // Path Adjustment code
1624 //============================================================================
1629 // Processes sweep events used to determine each horizontal and vertical
1630 // line segment in a connector's channel of visibility.
1631 // Four calls to this function are made at each position by the scanline:
1632 // 1) Handle all Close event processing.
1633 // 2) Remove Close event objects from the scanline.
1634 // 3) Add Open event objects to the scanline.
1635 // 4) Handle all Open event processing.
1636 //
1637 static void processShiftEvent(Router */*router*/, NodeSet& scanline,
1638 ShiftSegmentList& /*segments*/, Event *e, size_t dim,
1639 unsigned int pass)
1640 {
1641 Node *v = e->v;
1643 if ( ((pass == 3) && (e->type == Open)) ||
1644 ((pass == 3) && (e->type == SegOpen)) )
1645 {
1646 std::pair<NodeSet::iterator, bool> result = scanline.insert(v);
1647 v->iter = result.first;
1648 COLA_ASSERT(result.second);
1650 NodeSet::iterator it = v->iter;
1651 // Work out neighbours
1652 if (it != scanline.begin())
1653 {
1654 Node *u = *(--it);
1655 v->firstAbove = u;
1656 u->firstBelow = v;
1657 }
1658 it = v->iter;
1659 if (++it != scanline.end())
1660 {
1661 Node *u = *it;
1662 v->firstBelow = u;
1663 u->firstAbove = v;
1664 }
1665 }
1667 if ( ((pass == 4) && (e->type == Open)) ||
1668 ((pass == 4) && (e->type == SegOpen)) ||
1669 ((pass == 1) && (e->type == SegClose)) ||
1670 ((pass == 1) && (e->type == Close)) )
1671 {
1672 if (v->ss)
1673 {
1674 // As far as we can see.
1675 double minLimit = v->firstObstacleAbove(dim);
1676 double maxLimit = v->firstObstacleBelow(dim);
1678 v->ss->minSpaceLimit =
1679 std::max(minLimit, v->ss->minSpaceLimit);
1680 v->ss->maxSpaceLimit =
1681 std::min(maxLimit, v->ss->maxSpaceLimit);
1682 }
1683 else
1684 {
1685 v->markShiftSegmentsAbove(dim);
1686 v->markShiftSegmentsBelow(dim);
1687 }
1688 }
1690 if ( ((pass == 2) && (e->type == SegClose)) ||
1691 ((pass == 2) && (e->type == Close)) )
1692 {
1693 // Clean up neighbour pointers.
1694 Node *l = v->firstAbove, *r = v->firstBelow;
1695 if (l != NULL)
1696 {
1697 l->firstBelow = v->firstBelow;
1698 }
1699 if (r != NULL)
1700 {
1701 r->firstAbove = v->firstAbove;
1702 }
1704 size_t result;
1705 result = scanline.erase(v);
1706 COLA_ASSERT(result == 1);
1707 delete v;
1708 }
1709 }
1712 static void buildOrthogonalChannelInfo(Router *router,
1713 const size_t dim, ShiftSegmentList& segmentList)
1714 {
1715 if (router->routingPenalty(segmentPenalty) == 0)
1716 {
1717 // This code assumes the routes are pretty optimal, so we don't
1718 // do this adjustment if the routes have no segment penalty.
1719 return;
1720 }
1722 size_t altDim = (dim + 1) % 2;
1723 // For each connector.
1724 for (ConnRefList::const_iterator curr = router->connRefs.begin();
1725 curr != router->connRefs.end(); ++curr)
1726 {
1727 if ((*curr)->routingType() != ConnType_Orthogonal)
1728 {
1729 continue;
1730 }
1731 Polygon& displayRoute = (*curr)->displayRoute();
1732 // Determine all line segments that we are interested in shifting.
1733 // We don't consider the first or last segment of a path.
1734 for (size_t i = 1; i < displayRoute.size(); ++i)
1735 {
1736 if (displayRoute.ps[i - 1][dim] == displayRoute.ps[i][dim])
1737 {
1738 // It's a segment in the dimension we are processing,
1739 size_t indexLow = i - 1;
1740 size_t indexHigh = i;
1741 if (displayRoute.ps[i - 1][altDim] > displayRoute.ps[i][altDim])
1742 {
1743 indexLow = i;
1744 indexHigh = i - 1;
1745 }
1746 COLA_ASSERT(displayRoute.at(indexLow)[altDim] <
1747 displayRoute.at(indexHigh)[altDim]);
1749 if ((i == 1) || ((i + 1) == displayRoute.size()))
1750 {
1751 // The first and last segment of a connector can't be
1752 // shifted. We call them fixed segments. Note: this
1753 // will change if we later allow connection channels.
1754 segmentList.push_back(
1755 ShiftSegment(*curr, indexLow, indexHigh, dim));
1756 continue;
1757 }
1759 // The segment probably has space to be shifted.
1760 double minLim = -CHANNEL_MAX;
1761 double maxLim = CHANNEL_MAX;
1762 bool isSBend = false;
1764 double prevPos = displayRoute.ps[i - 2][dim];
1765 double nextPos = displayRoute.ps[i + 1][dim];
1766 if (((prevPos < displayRoute.ps[i][dim]) &&
1767 (nextPos > displayRoute.ps[i][dim]))
1768 ||
1769 ((prevPos > displayRoute.ps[i][dim]) &&
1770 (nextPos < displayRoute.ps[i][dim])) )
1771 {
1772 isSBend = true;
1774 // Determine limits if the s-bend is not due to an
1775 // obstacle. In this case we need to limit the channel
1776 // to the span of the adjoining segments to this one.
1777 if ((prevPos < displayRoute.ps[i][dim]) &&
1778 (nextPos > displayRoute.ps[i][dim]))
1779 {
1780 minLim = std::max(minLim, prevPos);
1781 maxLim = std::min(maxLim, nextPos);
1782 }
1783 else
1784 {
1785 minLim = std::max(minLim, nextPos);
1786 maxLim = std::min(maxLim, prevPos);
1787 }
1788 }
1789 else
1790 {
1791 // isCBend: Both adjoining segments are in the same
1792 // direction. We indicate this for later by setting
1793 // the maxLim or minLim to the segment position.
1794 if (prevPos < displayRoute.ps[i][dim])
1795 {
1796 minLim = displayRoute.ps[i][dim];
1797 }
1798 else
1799 {
1800 maxLim = displayRoute.ps[i][dim];
1801 }
1802 }
1804 segmentList.push_back(ShiftSegment(*curr, indexLow,
1805 indexHigh, isSBend, dim, minLim, maxLim));
1806 }
1807 }
1808 }
1809 if (segmentList.empty())
1810 {
1811 // There are no segments, so we can just return now.
1812 return;
1813 }
1815 // Do a sweep and shift these segments.
1816 const size_t n = router->shapeRefs.size();
1817 const size_t cpn = segmentList.size();
1818 // Set up the events for the sweep.
1819 size_t totalEvents = 2 * (n + cpn);
1820 events = new Event*[totalEvents];
1821 unsigned ctr = 0;
1822 ShapeRefList::iterator shRefIt = router->shapeRefs.begin();
1823 for (unsigned i = 0; i < n; i++)
1824 {
1825 ShapeRef *shRef = *shRefIt;
1826 Point min, max;
1827 shRef->polygon().getBoundingRect(&min.x, &min.y, &max.x, &max.y);
1828 double mid = min[dim] + ((max[dim] - min[dim]) / 2);
1829 Node *v = new Node(shRef, mid);
1830 events[ctr++] = new Event(Open, v, min[altDim]);
1831 events[ctr++] = new Event(Close, v, max[altDim]);
1833 ++shRefIt;
1834 }
1835 for (ShiftSegmentList::iterator curr = segmentList.begin();
1836 curr != segmentList.end(); ++curr)
1837 {
1838 const Point& lowPt = curr->lowPoint();
1839 const Point& highPt = curr->highPoint();
1841 COLA_ASSERT(lowPt[dim] == highPt[dim]);
1842 COLA_ASSERT(lowPt[altDim] < highPt[altDim]);
1843 Node *v = new Node(&(*curr), lowPt[dim]);
1844 events[ctr++] = new Event(SegOpen, v, lowPt[altDim]);
1845 events[ctr++] = new Event(SegClose, v, highPt[altDim]);
1846 }
1847 qsort((Event*)events, (size_t) totalEvents, sizeof(Event*), compare_events);
1849 // Process the sweep.
1850 // We do multiple passes over sections of the list so we can add relevant
1851 // entries to the scanline that might follow, before process them.
1852 NodeSet scanline;
1853 double thisPos = (totalEvents > 0) ? events[0]->pos : 0;
1854 unsigned int posStartIndex = 0;
1855 unsigned int posFinishIndex = 0;
1856 for (unsigned i = 0; i <= totalEvents; ++i)
1857 {
1858 // If we have finished the current scanline or all events, then we
1859 // process the events on the current scanline in a couple of passes.
1860 if ((i == totalEvents) || (events[i]->pos != thisPos))
1861 {
1862 posFinishIndex = i;
1863 for (int pass = 2; pass <= 4; ++pass)
1864 {
1865 for (unsigned j = posStartIndex; j < posFinishIndex; ++j)
1866 {
1867 processShiftEvent(router, scanline, segmentList, events[j],
1868 dim, pass);
1869 }
1870 }
1872 if (i == totalEvents)
1873 {
1874 // We have cleaned up, so we can now break out of loop.
1875 break;
1876 }
1878 thisPos = events[i]->pos;
1879 posStartIndex = i;
1880 }
1882 // Do the first sweep event handling -- building the correct
1883 // structure of the scanline.
1884 const int pass = 1;
1885 processShiftEvent(router, scanline, segmentList, events[i],
1886 dim, pass);
1887 }
1888 COLA_ASSERT(scanline.size() == 0);
1889 for (unsigned i = 0; i < totalEvents; ++i)
1890 {
1891 delete events[i];
1892 }
1893 delete [] events;
1894 }
1897 static void simplifyOrthogonalRoutes(Router *router)
1898 {
1899 // Simplify routes.
1900 for (ConnRefList::const_iterator curr = router->connRefs.begin();
1901 curr != router->connRefs.end(); ++curr)
1902 {
1903 if ((*curr)->routingType() != ConnType_Orthogonal)
1904 {
1905 continue;
1906 }
1907 (*curr)->set_route((*curr)->displayRoute().simplify());
1908 }
1909 }
1912 static void buildOrthogonalNudgingOrderInfo(Router *router,
1913 PtOrderMap& pointOrders)
1914 {
1915 // Simplify routes.
1916 simplifyOrthogonalRoutes(router);
1918 int crossingsN = 0;
1920 // Do segment splitting.
1921 for (ConnRefList::const_iterator curr = router->connRefs.begin();
1922 curr != router->connRefs.end(); ++curr)
1923 {
1924 if ((*curr)->routingType() != ConnType_Orthogonal)
1925 {
1926 continue;
1927 }
1928 ConnRef *conn = *curr;
1930 for (ConnRefList::const_iterator curr2 = router->connRefs.begin();
1931 curr2 != router->connRefs.end(); ++curr2)
1932 {
1933 if ((*curr2)->routingType() != ConnType_Orthogonal)
1934 {
1935 continue;
1936 }
1937 ConnRef *conn2 = *curr2;
1939 if (conn == conn2)
1940 {
1941 continue;
1942 }
1944 Avoid::Polygon& route = conn->displayRoute();
1945 Avoid::Polygon& route2 = conn2->displayRoute();
1946 splitBranchingSegments(route2, true, route);
1947 }
1948 }
1950 for (ConnRefList::const_iterator curr = router->connRefs.begin();
1951 curr != router->connRefs.end(); ++curr)
1952 {
1953 if ((*curr)->routingType() != ConnType_Orthogonal)
1954 {
1955 continue;
1956 }
1957 ConnRef *conn = *curr;
1959 for (ConnRefList::const_iterator curr2 = curr;
1960 curr2 != router->connRefs.end(); ++curr2)
1961 {
1962 if ((*curr2)->routingType() != ConnType_Orthogonal)
1963 {
1964 continue;
1965 }
1966 ConnRef *conn2 = *curr2;
1968 if (conn == conn2)
1969 {
1970 continue;
1971 }
1973 Avoid::Polygon& route = conn->displayRoute();
1974 Avoid::Polygon& route2 = conn2->displayRoute();
1975 bool checkForBranchingSegments = false;
1976 int crossings = 0;
1977 for (size_t i = 1; i < route.size(); ++i)
1978 {
1979 const bool finalSegment = ((i + 1) == route.size());
1980 crossings += countRealCrossings(route2, true, route, i,
1981 checkForBranchingSegments, finalSegment, NULL,
1982 &pointOrders, conn2, conn).first;
1983 }
1984 if (crossings > 0)
1985 {
1986 crossingsN += crossings;
1987 }
1988 }
1989 }
1991 // Sort the point orders.
1992 PtOrderMap::iterator finish = pointOrders.end();
1993 for (PtOrderMap::iterator it = pointOrders.begin(); it != finish; ++it)
1994 {
1995 //const VertID& ptID = it->first;
1996 PtOrder& order = it->second;
1998 for (size_t dim = XDIM; dim <= YDIM; ++dim)
1999 {
2000 order.sort(dim);
2001 }
2002 }
2003 }
2006 class CmpLineOrder
2007 {
2008 public:
2009 CmpLineOrder(PtOrderMap& ord, const size_t dim)
2010 : orders(ord),
2011 dimension(dim)
2012 {
2013 }
2014 bool operator()(const ShiftSegment& lhs, const ShiftSegment& rhs,
2015 bool *comparable = NULL) const
2016 {
2017 if (comparable)
2018 {
2019 *comparable = true;
2020 }
2021 Point lhsLow = lhs.lowPoint();
2022 Point rhsLow = rhs.lowPoint();
2023 #ifndef NDEBUG
2024 const Point& lhsHigh = lhs.highPoint();
2025 const Point& rhsHigh = rhs.highPoint();
2026 #endif
2027 size_t altDim = (dimension + 1) % 2;
2029 COLA_ASSERT(lhsLow[dimension] == lhsHigh[dimension]);
2030 COLA_ASSERT(rhsLow[dimension] == rhsHigh[dimension]);
2032 if (lhsLow[dimension] != rhsLow[dimension])
2033 {
2034 return lhsLow[dimension] < rhsLow[dimension];
2035 }
2037 // If one of these is fixed, then determine order based on
2038 // fixed segment, that is, order so the fixed segment doesn't
2039 // block movement.
2040 bool oneIsFixed = false;
2041 const int lhsFixedOrder = lhs.fixedOrder(oneIsFixed);
2042 const int rhsFixedOrder = rhs.fixedOrder(oneIsFixed);
2043 if (oneIsFixed && (lhsFixedOrder != rhsFixedOrder))
2044 {
2045 return lhsFixedOrder < rhsFixedOrder;
2046 }
2048 // C-bends that did not have a clear order with s-bends might
2049 // not have a good ordering here, so compare their order in
2050 // terms of C-bend direction and S-bends and use that if it
2051 // differs for the two segments.
2052 const int lhsOrder = lhs.order();
2053 const int rhsOrder = rhs.order();
2054 if (lhsOrder != rhsOrder)
2055 {
2056 return lhsOrder < rhsOrder;
2057 }
2059 // Need to index using the original point into the map, so find it.
2060 Point& unchanged = (lhsLow[altDim] > rhsLow[altDim]) ?
2061 lhsLow : rhsLow;
2063 PtOrder& lowOrder = orders[unchanged];
2064 int lhsPos = lowOrder.positionFor(lhs.connRef, dimension);
2065 int rhsPos = lowOrder.positionFor(rhs.connRef, dimension);
2066 if ((lhsPos == -1) || (rhsPos == -1))
2067 {
2068 // A value for rhsPos or lhsPos mean the points are not directly
2069 // comparable, meaning they are at the same position but cannot
2070 // overlap (they are just collinear. The relative order for
2071 // these segments is not important since we do not constrain
2072 // them against each other.
2073 //COLA_ASSERT(lhs.overlapsWith(rhs, dimension) == false);
2074 // We do need to be consistent though.
2075 if (comparable)
2076 {
2077 *comparable = false;
2078 }
2079 return lhsLow[altDim] < rhsLow[altDim];
2080 }
2082 return lhsPos < rhsPos;
2083 }
2085 PtOrderMap& orders;
2086 const size_t dimension;
2087 };
2090 // We can use the normaal sort algorithm for lists since it is not possible
2091 // to comapre all elements, but there will be an ordering defined between
2092 // most of the elements. Hence we order these, using insertion sort, and
2093 // the case of them not being able to be compared is handled by not setting
2094 // up any constraints between such segments when doing the nudging.
2095 //
2096 static ShiftSegmentList linesort(ShiftSegmentList origList,
2097 CmpLineOrder& comparison)
2098 {
2099 ShiftSegmentList resultList;
2101 while (!origList.empty())
2102 {
2103 // Get and remove the first element from the origList.
2104 ShiftSegment segment = origList.front();
2105 origList.pop_front();
2107 // Find the insertion point in the resultList.
2108 ShiftSegmentList::iterator curr;
2109 for (curr = resultList.begin(); curr != resultList.end(); ++curr)
2110 {
2111 bool comparable = false;
2112 bool lessThan = comparison(segment, *curr, &comparable);
2114 if (comparable && lessThan)
2115 {
2116 // If it is comparable and lessThan, then we have found the
2117 // insertion point.
2118 break;
2119 }
2120 }
2122 // Insert the element into the reultList at the required point.
2123 resultList.insert(curr, segment);
2124 }
2126 return resultList;
2127 }
2130 typedef std::list<ShiftSegment *> ShiftSegmentPtrList;
2133 static void nudgeOrthogonalRoutes(Router *router, size_t dimension,
2134 PtOrderMap& pointOrders, ShiftSegmentList& segmentList)
2135 {
2136 // Do the actual nudging.
2137 ShiftSegmentList currentRegion;
2138 while (!segmentList.empty())
2139 {
2140 // Take a reference segment
2141 ShiftSegment& currentSegment = segmentList.front();
2142 // Then, find the segments that overlap this one.
2143 currentRegion.clear();
2144 currentRegion.push_back(currentSegment);
2145 segmentList.erase(segmentList.begin());
2146 for (ShiftSegmentList::iterator curr = segmentList.begin();
2147 curr != segmentList.end(); )
2148 {
2149 bool overlaps = false;
2150 for (ShiftSegmentList::iterator curr2 = currentRegion.begin();
2151 curr2 != currentRegion.end(); ++curr2)
2152 {
2153 if (curr->overlapsWith(*curr2, dimension))
2154 {
2155 overlaps = true;
2156 break;
2157 }
2158 }
2159 if (overlaps)
2160 {
2161 currentRegion.push_back(*curr);
2162 segmentList.erase(curr);
2163 // Consider segments from the beginning, since we mave have
2164 // since passed segments that overlap with the new set.
2165 curr = segmentList.begin();
2166 }
2167 else
2168 {
2169 ++curr;
2170 }
2171 }
2172 CmpLineOrder lineSortComp(pointOrders, dimension);
2173 currentRegion = linesort(currentRegion, lineSortComp);
2175 if (currentRegion.size() == 1)
2176 {
2177 // Save creating the solver instance if there is just one
2178 // immovable segment.
2179 if (!currentRegion.front().sBend)
2180 {
2181 continue;
2182 }
2183 }
2185 // Process these segments.
2186 Variables vs;
2187 Constraints cs;
2188 ShiftSegmentPtrList prevVars;
2189 // IDs:
2190 const int freeID = 0;
2191 const int fixedID = 1;
2192 // Weights:
2193 double freeWeight = 0.00001;
2194 double strongWeight = 0.001;
2195 double fixedWeight = 100000;
2196 //printf("-------------------------------------------------------\n");
2197 //printf("Nudge -- size: %d\n", (int) currentRegion.size());
2198 for (ShiftSegmentList::iterator currSegment = currentRegion.begin();
2199 currSegment != currentRegion.end(); ++currSegment)
2200 {
2201 Point& lowPt = currSegment->lowPoint();
2203 // Create a solver variable for the position of this segment.
2204 int varID = freeID;
2205 double idealPos = lowPt[dimension];
2206 double weight = freeWeight;
2207 if (currSegment->sBend)
2208 {
2209 COLA_ASSERT(currSegment->minSpaceLimit > -CHANNEL_MAX);
2210 COLA_ASSERT(currSegment->maxSpaceLimit < CHANNEL_MAX);
2212 // For s-bends, take the middle as ideal.
2213 idealPos = currSegment->minSpaceLimit +
2214 ((currSegment->maxSpaceLimit -
2215 currSegment->minSpaceLimit) / 2);
2216 }
2217 else if (currSegment->fixed)
2218 {
2219 // Fixed segments shouldn't get moved.
2220 weight = fixedWeight;
2221 varID = fixedID;
2222 }
2223 else
2224 {
2225 // Set a higher weight for c-bends to stop them sometimes
2226 // getting pushed out into channels by more-free connectors
2227 // to the "inner" side of them.
2228 weight = strongWeight;
2229 }
2230 currSegment->variable = new Variable(varID, idealPos, weight);
2231 vs.push_back(currSegment->variable);
2232 size_t index = vs.size() - 1;
2233 //printf("line %.15f pos: %g min: %g max: %g\n",
2234 // lowPt[dimension], idealPos, currSegment->minSpaceLimit,
2235 // currSegment->maxSpaceLimit);
2237 // Constrain position in relation to previously seen segments,
2238 // if necessary (i.e. when they could overlap).
2239 for (ShiftSegmentPtrList::iterator prevVarIt = prevVars.begin();
2240 prevVarIt != prevVars.end(); )
2241 {
2242 ShiftSegment *prevSeg = *prevVarIt;
2243 Variable *prevVar = prevSeg->variable;
2245 if (currSegment->overlapsWith(*prevSeg, dimension) &&
2246 (!(currSegment->fixed) || !(prevSeg->fixed)))
2247 {
2248 // If there is a previous segment to the left that
2249 // could overlap this in the shift direction, then
2250 // constrain the two segments to be separated.
2251 // Though don't add the constraint if both the
2252 // segments are fixed in place.
2253 cs.push_back(new Constraint(prevVar, vs[index],
2254 router->orthogonalNudgeDistance()));
2255 prevVarIt = prevVars.erase(prevVarIt);
2256 }
2257 else
2258 {
2259 ++prevVarIt;
2260 }
2261 }
2263 if (!currSegment->fixed)
2264 {
2265 // If this segment sees a channel boundary to its left,
2266 // then constrain its placement as such.
2267 if (currSegment->minSpaceLimit > -CHANNEL_MAX)
2268 {
2269 vs.push_back(new Variable(fixedID,
2270 currSegment->minSpaceLimit, fixedWeight));
2271 cs.push_back(new Constraint(vs[vs.size() - 1], vs[index],
2272 0.0));
2273 }
2275 // If this segment sees a channel boundary to its right,
2276 // then constrain its placement as such.
2277 if (currSegment->maxSpaceLimit < CHANNEL_MAX)
2278 {
2279 vs.push_back(new Variable(fixedID,
2280 currSegment->maxSpaceLimit, fixedWeight));
2281 cs.push_back(new Constraint(vs[index], vs[vs.size() - 1],
2282 0.0));
2283 }
2284 }
2285 prevVars.push_back(&(*currSegment));
2286 }
2287 #if 0
2288 for(unsigned i=0;i<vs.size();i++) {
2289 printf("-vs[%d]=%f\n",i,vs[i]->desiredPosition);
2290 }
2291 #endif
2292 IncSolver f(vs,cs);
2293 f.solve();
2294 bool satisfied = true;
2295 for (size_t i = 0; i < vs.size(); ++i)
2296 {
2297 if (vs[i]->id == fixedID)
2298 {
2299 if (fabs(vs[i]->finalPosition - vs[i]->desiredPosition) > 0.01)
2300 {
2301 satisfied = false;
2302 break;
2303 }
2304 }
2305 }
2306 if (satisfied)
2307 {
2308 for (ShiftSegmentList::iterator currSegment = currentRegion.begin();
2309 currSegment != currentRegion.end(); ++currSegment)
2310 {
2311 Point& lowPt = currSegment->lowPoint();
2312 Point& highPt = currSegment->highPoint();
2313 double newPos = currSegment->variable->finalPosition;
2314 //printf("Pos: %X, %g\n", (int) currSegment->connRef, newPos);
2315 lowPt[dimension] = newPos;
2316 highPt[dimension] = newPos;
2317 }
2318 }
2319 #if 0
2320 for(unsigned i=0;i<vs.size();i++) {
2321 printf("+vs[%d]=%f\n",i,vs[i]->finalPosition);
2322 }
2323 #endif
2324 for_each(vs.begin(),vs.end(),delete_object());
2325 for_each(cs.begin(),cs.end(),delete_object());
2326 }
2327 }
2330 extern void improveOrthogonalRoutes(Router *router)
2331 {
2332 router->timers.Register(tmOrthogNudge, timerStart);
2333 for (size_t dimension = 0; dimension < 2; ++dimension)
2334 {
2335 // Build nudging info.
2336 // XXX: We need to build the point orders separately in each
2337 // dimension since things move. There is probably a more
2338 // efficient way to do this.
2339 PtOrderMap pointOrders;
2340 buildOrthogonalNudgingOrderInfo(router, pointOrders);
2342 // Simplify routes.
2343 simplifyOrthogonalRoutes(router);
2345 // Do the centring and nudging.
2346 ShiftSegmentList segLists;
2347 buildOrthogonalChannelInfo(router, dimension, segLists);
2348 nudgeOrthogonalRoutes(router, dimension, pointOrders, segLists);
2349 }
2350 router->timers.Stop();
2351 }
2354 }