diff options
Diffstat (limited to 'src/libavoid/orthogonal.cpp')
| -rw-r--r-- | src/libavoid/orthogonal.cpp | 2970 |
1 files changed, 1941 insertions, 1029 deletions
diff --git a/src/libavoid/orthogonal.cpp b/src/libavoid/orthogonal.cpp index 466d1dd58..2558e0d73 100644 --- a/src/libavoid/orthogonal.cpp +++ b/src/libavoid/orthogonal.cpp @@ -3,7 +3,7 @@ * * libavoid - Fast, Incremental, Object-avoiding Line Router * - * Copyright (C) 2009 Monash University + * Copyright (C) 2009-2014 Monash University * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -12,14 +12,14 @@ * See the file LICENSE.LGPL distributed with the library. * * Licensees holding a valid commercial license may use this file in - * accordance with the commercial license agreement provided with the + * accordance with the commercial license agreement provided with the * library. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * - * Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net> + * Author(s): Michael Wybrow */ @@ -34,96 +34,257 @@ #include "libavoid/geomtypes.h" #include "libavoid/shape.h" #include "libavoid/orthogonal.h" +#include "libavoid/connend.h" #include "libavoid/connector.h" +#include "libavoid/junction.h" #include "libavoid/vpsc.h" #include "libavoid/assertions.h" +#include "libavoid/scanline.h" +#include "libavoid/debughandler.h" -#ifdef LIBAVOID_SDL - #include <SDL_gfxPrimitives.h> -#endif +// For debugging: +//#define NUDGE_DEBUG +//#define DEBUG_JUST_UNIFY namespace Avoid { -static const double CHANNEL_MAX = 100000000; +// IDs: +static const int freeSegmentID = 0; +static const int fixedSegmentID = 1; +static const int channelLeftID = 2; +static const int channelRightID = 3; +// Weights: +static const double freeWeight = 0.00001; +static const double strongWeight = 0.001; +static const double strongerWeight = 1.0; +static const double fixedWeight = 100000; -static const size_t XDIM = 0; -static const size_t YDIM = 1; +// A pair of unsigned values that can be compared and used as the keys +// for sets and maps. +class UnsignedPair +{ + public: + UnsignedPair(unsigned ind1, unsigned ind2) + { + COLA_ASSERT(ind1 != ind2); + // Assign the lesser value to m_index1. + m_index1 = (ind1 < ind2) ? ind1 : ind2; + // Assign the greater value to m_index2. + m_index2 = (ind1 > ind2) ? ind1 : ind2; + } -class ShiftSegment + bool operator<(const UnsignedPair& rhs) const + { + if (m_index1 != rhs.m_index1) + { + return m_index1 < rhs.m_index1; + } + return m_index2 < rhs.m_index2; + } + private: + unsigned short m_index1; + unsigned short m_index2; +}; +typedef std::set<UnsignedPair> UnsignedPairSet; + + +// Used to sort points when merging NudgingShiftSegments. +// Sorts the indexes, by point position in one dimension. +class CmpIndexes { public: - // For shiftable segments. - ShiftSegment(ConnRef *conn, const size_t low, const size_t high, - bool isSBend, const size_t dim, double minLim, double maxLim) + CmpIndexes(ConnRef *conn, size_t dim) : connRef(conn), - indexLow(low), - indexHigh(high), - sBend(isSBend), - fixed(false), - dimension(dim), - variable(NULL), - minSpaceLimit(minLim), - maxSpaceLimit(maxLim) + dimension(dim) { } + bool operator()(size_t lhs, size_t rhs) + { + return connRef->displayRoute().ps[lhs][dimension] < + connRef->displayRoute().ps[rhs][dimension]; + } + private: + ConnRef *connRef; + size_t dimension; +}; + +class NudgingShiftSegment : public ShiftSegment +{ + public: + // For shiftable segments. + NudgingShiftSegment(ConnRef *conn, const size_t low, const size_t high, + bool isSBend, bool isZBend, const size_t dim, double minLim, + double maxLim) + : ShiftSegment(dim), + connRef(conn), + variable(NULL), + fixed(false), + finalSegment(false), + endsInShape(false), + singleConnectedSegment(false), + sBend(isSBend), + zBend(isZBend) + { + indexes.push_back(low); + indexes.push_back(high); + minSpaceLimit = minLim; + maxSpaceLimit = maxLim; + } // For fixed segments. - ShiftSegment(ConnRef *conn, const size_t low, const size_t high, + NudgingShiftSegment(ConnRef *conn, const size_t low, const size_t high, const size_t dim) - : connRef(conn), - indexLow(low), - indexHigh(high), - sBend(false), + : ShiftSegment(dim), + connRef(conn), + variable(NULL), fixed(true), - dimension(dim), - variable(NULL) + finalSegment(false), + endsInShape(false), + singleConnectedSegment(false), + sBend(false), + zBend(false) { + indexes.push_back(low); + indexes.push_back(high); // This has no space to shift. minSpaceLimit = lowPoint()[dim]; maxSpaceLimit = lowPoint()[dim]; } - + virtual ~NudgingShiftSegment() + { + } Point& lowPoint(void) { - return connRef->displayRoute().ps[indexLow]; + return connRef->displayRoute().ps[indexes.front()]; } - Point& highPoint(void) { - return connRef->displayRoute().ps[indexHigh]; + return connRef->displayRoute().ps[indexes.back()]; } - const Point& lowPoint(void) const { - return connRef->displayRoute().ps[indexLow]; + return connRef->displayRoute().ps[indexes.front()]; } - - const Point& highPoint(void) const + const Point& highPoint(void) const { - return connRef->displayRoute().ps[indexHigh]; + return connRef->displayRoute().ps[indexes.back()]; + } + double nudgeDistance(void) const + { + return connRef->router()->routingParameter(idealNudgingDistance); + } + bool immovable(void) const + { + return ! zigzag(); + } + void createSolverVariable(const bool justUnifying) + { + bool nudgeFinalSegments = connRef->router()->routingOption( + nudgeOrthogonalSegmentsConnectedToShapes); + int varID = freeSegmentID; + double varPos = lowPoint()[dimension]; + double weight = freeWeight; + if (nudgeFinalSegments && finalSegment) + { + weight = strongWeight; + + if (singleConnectedSegment && !justUnifying) + { + // This is a single segment connector bridging + // two shapes. So, we want to try to keep it + // centred rather than shift it. + // Don't do this during Unifying stage, or else + // these connectors could end up at slightly + // different positions and get the wrong ordering + // for nudging. + weight = strongerWeight; + } + } + else if (checkpoints.size() > 0) + { + weight = strongWeight; + } + else if (zigzag()) + { + COLA_ASSERT(minSpaceLimit > -CHANNEL_MAX); + COLA_ASSERT(maxSpaceLimit < CHANNEL_MAX); + + // For zigzag bends, take the middle as ideal. + varPos = minSpaceLimit + ((maxSpaceLimit - minSpaceLimit) / 2); + } + else if (fixed) + { + // Fixed segments shouldn't get moved. + weight = fixedWeight; + varID = fixedSegmentID; + } + else if ( ! finalSegment ) + { + // Set a higher weight for c-bends to stop them sometimes + // getting pushed out into channels by more-free connectors + // to the "inner" side of them. + weight = strongWeight; + } + + variable = new Variable(varID, varPos, weight); } - int fixedOrder(bool& isFixed) const + void updatePositionsFromSolver(const bool justUnifying) { if (fixed) { + return; + } + double newPos = variable->finalPosition; + + // The solver can sometimes cause variables to be outside their + // limits by a tiny amount, since all variables are held by + // weights. Thus, just make sure they stay in their limits. + newPos = std::max(newPos, minSpaceLimit); + newPos = std::min(newPos, maxSpaceLimit); + +#ifdef NUDGE_DEBUG + printf("Pos: %lX, %.16f\n", (long) connRef, newPos); +#endif + for (size_t it = 0; it < indexes.size(); ++it) + { + size_t index = indexes[it]; + connRef->displayRoute().ps[index][dimension] = newPos; + } + +#ifdef DEBUGHANDLER + if (!justUnifying && connRef->router()->debugHandler()) + { + connRef->router()->debugHandler()->updateConnectorRoute( + connRef, indexes[0], indexes[indexes.size() - 1]); + } +#endif + } + int fixedOrder(bool& isFixed) const + { + double nudgeDist = nudgeDistance(); + double pos = lowPoint()[dimension]; + bool minLimited = ((pos - minSpaceLimit) < nudgeDist); + bool maxLimited = ((maxSpaceLimit - pos) < nudgeDist); + + if (fixed || (minLimited && maxLimited)) + { isFixed = true; return 0; } - if (lowC()) + else if (minLimited) { return 1; } - else if (highC()) + else if (maxLimited) { return -1; } return 0; } - int order(void) const { if (lowC()) @@ -136,389 +297,264 @@ class ShiftSegment } return 0; } - - bool operator<(const ShiftSegment& rhs) const + bool zigzag(void) const { - const Point& lowPt = lowPoint(); - const Point& rhsLowPt = rhs.lowPoint(); - - if (lowPt[dimension] != rhsLowPt[dimension]) - { - return lowPt[dimension] < rhsLowPt[dimension]; - } - return this < &rhs; + return sBend || zBend; } - - // This counts segments that are colliear and share an endpoint as + // This counts segments that are collinear and share an endpoint as // overlapping. This allows them to be nudged apart where possible. - bool overlapsWith(const ShiftSegment& rhs, const size_t dim) const + bool overlapsWith(const ShiftSegment *rhsSuper, const size_t dim) const { + const NudgingShiftSegment *rhs = + static_cast<const NudgingShiftSegment *> (rhsSuper); size_t altDim = (dim + 1) % 2; const Point& lowPt = lowPoint(); const Point& highPt = highPoint(); - const Point& rhsLowPt = rhs.lowPoint(); - const Point& rhsHighPt = rhs.highPoint(); - if ( (lowPt[altDim] <= rhsHighPt[altDim]) && - (rhsLowPt[altDim] <= highPt[altDim])) - { - if ( (minSpaceLimit <= rhs.maxSpaceLimit) && - (rhs.minSpaceLimit <= maxSpaceLimit)) + const Point& rhsLowPt = rhs->lowPoint(); + const Point& rhsHighPt = rhs->highPoint(); + if ( (lowPt[altDim] < rhsHighPt[altDim]) && + (rhsLowPt[altDim] < highPt[altDim])) + { + // The segments overlap. + if ( (minSpaceLimit <= rhs->maxSpaceLimit) && + (rhs->minSpaceLimit <= maxSpaceLimit) ) { return true; } } - return false; - } - - ConnRef *connRef; - size_t indexLow; - size_t indexHigh; - bool sBend; - bool fixed; - size_t dimension; - Variable *variable; - double minSpaceLimit; - double maxSpaceLimit; - private: - bool lowC(void) const - { - // This is true if this is a cBend and its adjoining points - // are at lower positions. - if (!sBend && !fixed && (minSpaceLimit == lowPoint()[dimension])) + else if ( (lowPt[altDim] == rhsHighPt[altDim]) || + (rhsLowPt[altDim] == highPt[altDim]) ) { - return true; - } - return false; - } + bool nudgeColinearSegments = connRef->router()->routingOption( + nudgeOrthogonalTouchingColinearSegments); - bool highC(void) const - { - // This is true if this is a cBend and its adjoining points - // are at higher positions. - if (!sBend && !fixed && (maxSpaceLimit == lowPoint()[dimension])) - { - return true; + if ( (minSpaceLimit <= rhs->maxSpaceLimit) && + (rhs->minSpaceLimit <= maxSpaceLimit) ) + { + // The segments could touch at one end. + if (connRef->router()->routingParameter( + fixedSharedPathPenalty) > 0) + { + // If we are routing with a fixedSharedPathPenalty + // then we don't want these segments to ever touch + // or slide past each other, so they are always + // considered to be overlapping. + return true; + } + else if ((rhs->sBend && sBend) || (rhs->zBend && zBend)) + { + // Count them as overlapping for nudging if they + // are both s-bends or both z-bends, i.e., when + // the ordering would matter. + return nudgeColinearSegments; + } + else if ((rhs->finalSegment && finalSegment) && + (rhs->connRef == connRef)) + { + return nudgeColinearSegments; + } + } } return false; } -}; -typedef std::list<ShiftSegment> ShiftSegmentList; - -struct Node; -struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; }; - -typedef std::set<Node*,CmpNodePos> NodeSet; -struct Node -{ - ShapeRef *v; - VertInf *c; - ShiftSegment *ss; - double pos; - double min[2], max[2]; - Node *firstAbove, *firstBelow; - NodeSet::iterator iter; - - Node(ShapeRef *v, const double p) - : v(v), - c(NULL), - ss(NULL), - pos(p), - firstAbove(NULL), - firstBelow(NULL) - { - //COLA_ASSERT(r->width()<1e40); - v->polygon().getBoundingRect(&min[0], &min[1], &max[0], &max[1]); - } - Node(VertInf *c, const double p) - : v(NULL), - c(c), - ss(NULL), - pos(p), - firstAbove(NULL), - firstBelow(NULL) - { - min[0] = max[0] = c->point.x; - min[1] = max[1] = c->point.y; - } - Node(ShiftSegment *ss, const double p) - : v(NULL), - c(NULL), - ss(ss), - pos(p), - firstAbove(NULL), - firstBelow(NULL) - { - // These values shouldn't ever be used, so they don't matter. - min[0] = max[0] = min[1] = max[1] = 0; - } - ~Node() - { - } - // Find the first Node above in the scanline that is a shape edge, - // and does not have an open or close event at this position (meaning - // it is just about to be removed). - double firstObstacleAbove(size_t dim) - { - Node *curr = firstAbove; - while (curr && (curr->ss || (curr->max[dim] > pos))) - { - curr = curr->firstAbove; - } - - if (curr) - { - return curr->max[dim]; - } - return -DBL_MAX; - } - // Find the first Node below in the scanline that is a shape edge, - // and does not have an open or close event at this position (meaning - // it is just about to be removed). - double firstObstacleBelow(size_t dim) - { - Node *curr = firstBelow; - while (curr && (curr->ss || (curr->min[dim] < pos))) + // These segments are allowed to drift into alignment but don't have to. + bool canAlignWith(const NudgingShiftSegment *rhs, + const size_t dim) const { - curr = curr->firstBelow; - } + COLA_UNUSED(dim); - if (curr) - { - return curr->min[dim]; - } - return DBL_MAX; - } - // Mark all connector segments above in the scanline as being able - // to see to this shape edge. - void markShiftSegmentsAbove(size_t dim) - { - Node *curr = firstAbove; - while (curr && (curr->ss || (curr->pos > min[dim]))) - { - if (curr->ss && (curr->pos <= min[dim])) + if (connRef != rhs->connRef) { - curr->ss->maxSpaceLimit = - std::min(min[dim], curr->ss->maxSpaceLimit); + return false; } - curr = curr->firstAbove; - } - } - // Mark all connector segments below in the scanline as being able - // to see to this shape edge. - void markShiftSegmentsBelow(size_t dim) - { - Node *curr = firstBelow; - while (curr && (curr->ss || (curr->pos < max[dim]))) - { - if (curr->ss && (curr->pos >= max[dim])) + + // Don't allow segments of the same connector to drift together + // where one of them goes via a checkpoint. We want the path + // through the checkpoint to be maintained. + bool hasCheckpoints = checkpoints.size() > 0; + bool rhsHasCheckpoints = rhs->checkpoints.size() > 0; + if (hasCheckpoints || rhsHasCheckpoints) { - curr->ss->minSpaceLimit = - std::max(max[dim], curr->ss->minSpaceLimit); + return false; } - curr = curr->firstBelow; + return true; } - } - bool findFirstPointAboveAndBelow(const size_t dim, double& firstAbovePos, - double& firstBelowPos, double& lastAbovePos, double& lastBelowPos) - { - bool clearVisibility = true; - firstAbovePos = -DBL_MAX; - firstBelowPos = DBL_MAX; - // We start looking left from the right side of the shape, - // and vice versa. - lastAbovePos = max[dim]; - lastBelowPos = min[dim]; - - // Find the first blocking edge above this point. Don't count the - // edges as we are travelling out of shapes we are inside, but then - // mark clearVisibility as false. - Node *curr = firstAbove; - while (curr && (curr->max[dim] > min[dim])) - { - lastAbovePos = std::min(curr->min[dim], lastAbovePos); - if ((curr->max[dim] >= min[dim]) && (curr->max[dim] <= max[dim])) - { - lastAbovePos = std::min(curr->max[dim], lastAbovePos); + // These segments should align with each other. + bool shouldAlignWith(const ShiftSegment *rhsSuper, + const size_t dim) const + { + const NudgingShiftSegment *rhs = + static_cast<const NudgingShiftSegment *> (rhsSuper); + if ((connRef == rhs->connRef) && finalSegment && + rhs->finalSegment && overlapsWith(rhs, dim)) + { + // If both the segments are in shapes then we know limits + // and can align. Otherwise we do this just for segments + // that are very close together, since these will often + // prevent nudging, or force it to have a tiny separation + // value. + if ((endsInShape && rhs->endsInShape) || + (fabs(lowPoint()[dim] - rhs->lowPoint()[dim]) < 10)) + { + return true; + } } - lastBelowPos = std::max(curr->max[dim], lastBelowPos); - clearVisibility = false; - curr = curr->firstAbove; - } - if (curr) - { - firstAbovePos = curr->max[dim]; - } - while (curr) - { - // There might be a larger shape after this one in the ordering. - if (curr->max[dim] < min[dim]) + else if ((connRef == rhs->connRef) && + // Not both final + ((finalSegment & rhs->finalSegment) != true)) { - firstAbovePos = std::max(curr->max[dim], firstAbovePos); + bool hasCheckpoints = checkpoints.size() > 0; + bool rhsHasCheckpoints = rhs->checkpoints.size() > 0; + + if (hasCheckpoints != rhsHasCheckpoints) + { + // At least one segment has checkpoints, but not both. + + size_t altDim = (dim + 1) % 2; + double space = fabs(lowPoint()[dim] - rhs->lowPoint()[dim]); + double touchPos; + bool couldTouch = false; + if (lowPoint()[altDim] == rhs->highPoint()[altDim]) + { + couldTouch = true; + touchPos = lowPoint()[altDim]; + } + else if (highPoint()[altDim] == rhs->lowPoint()[altDim]) + { + couldTouch = true; + touchPos = highPoint()[altDim]; + } + + // We should align these so long as they are close + // together (<= 10) and there isn't a checkpoint at the + // touch point, i.e., we'd be altering the edges leading + // into the checkpoint. We want to keep these in place + // and opportunistically move other edges to align with + // them. + return couldTouch && (space <= 10) && + !hasCheckpointAtPosition(touchPos, altDim) && + !rhs->hasCheckpointAtPosition(touchPos, altDim); + } } - curr = curr->firstAbove; + return false; } - - // Find the first blocking edge below this point. Don't count the - // edges as we are travelling out of shapes we are inside, but then - // mark clearVisibility as false. - curr = firstBelow; - while (curr && (curr->min[dim] < max[dim])) + // Used for merging segments with end segments that should appear as + // a single segment. + void mergeWith(const ShiftSegment *rhsSuper, const size_t dim) { - lastBelowPos = std::max(curr->max[dim], lastBelowPos); - if ((curr->min[dim] >= min[dim]) && (curr->min[dim] <= max[dim])) + // Adjust limits. + minSpaceLimit = std::max(minSpaceLimit, rhsSuper->minSpaceLimit); + maxSpaceLimit = std::min(maxSpaceLimit, rhsSuper->maxSpaceLimit); + + // Find a new position for the segment, taking into account + // the two original positions and the combined limits. + double segmentPos = lowPoint()[dimension]; + double segment2Pos = rhsSuper->lowPoint()[dimension]; + if (segment2Pos < segmentPos) { - lastBelowPos = std::max(curr->min[dim], lastBelowPos); + segmentPos -= ((segmentPos - segment2Pos) / 2.0); } - lastAbovePos = std::min(curr->min[dim], lastAbovePos); - clearVisibility = false; - curr = curr->firstBelow; - } - if (curr) - { - firstBelowPos = curr->min[dim]; - } - while (curr) - { - // There might be a larger shape after this one in the ordering. - if (curr->min[dim] > max[dim]) + else if (segment2Pos > segmentPos) { - firstBelowPos = std::min(curr->min[dim], firstBelowPos); + segmentPos += ((segment2Pos - segmentPos) / 2.0); } - curr = curr->firstBelow; - } + segmentPos = std::max(minSpaceLimit, segmentPos); + segmentPos = std::min(maxSpaceLimit, segmentPos); - return clearVisibility; - } - double firstPointAbove(size_t dim) - { - Node *curr = firstAbove; - while (curr && (curr->max[dim] >= pos)) - { - curr = curr->firstAbove; - } + // Merge the index lists and sort the new list. + const NudgingShiftSegment *rhs = + static_cast<const NudgingShiftSegment *> (rhsSuper); + indexes.insert(indexes.end(), rhs->indexes.begin(), rhs->indexes.end()); + size_t altDim = (dim + 1) % 2; + CmpIndexes compare(connRef, altDim); + sort(indexes.begin(), indexes.end(), compare); - if (curr) - { - return curr->max[dim]; + // Apply the new positon to all points to keep them constant. + for (size_t it = 0; it < indexes.size(); ++it) + { + size_t index = indexes[it]; + connRef->displayRoute().ps[index][dimension] = segmentPos; + } } - return -DBL_MAX; - } - double firstPointBelow(size_t dim) - { - Node *curr = firstBelow; - while (curr && (curr->min[dim] <= pos)) + bool hasCheckpointAtPosition(const double position, + const size_t dim) const { - curr = curr->firstBelow; + for (size_t cp = 0; cp < checkpoints.size(); ++cp) + { + if (checkpoints[cp][dim] == position) + { + return true; + } + } + return false; } - if (curr) - { - return curr->min[dim]; - } - return DBL_MAX; - } - // This is a bit inefficient, but we won't need to do it once we have - // connection points. - bool isInsideShape(size_t dimension) - { - for (Node *curr = firstBelow; curr; curr = curr->firstBelow) + ConnRef *connRef; + Variable *variable; + std::vector<size_t> indexes; + bool fixed; + bool finalSegment; + bool endsInShape; + bool singleConnectedSegment; + std::vector<Point> checkpoints; + private: + bool sBend; + bool zBend; + bool lowC(void) const { - if ((curr->min[dimension] < pos) && (pos < curr->max[dimension])) + // This is true if this is a cBend and its adjoining points + // are at lower positions. + if (!finalSegment && !zigzag() && !fixed && + (minSpaceLimit == lowPoint()[dimension])) { return true; } + return false; } - for (Node *curr = firstAbove; curr; curr = curr->firstAbove) + bool highC(void) const { - if ((curr->min[dimension] < pos) && (pos < curr->max[dimension])) + // This is true if this is a cBend and its adjoining points + // are at higher positions. + if (!finalSegment && !zigzag() && !fixed && + (maxSpaceLimit == lowPoint()[dimension])) { return true; } + return false; } - return false; - } }; -bool CmpNodePos::operator() (const Node* u, const Node* v) const -{ - if (u->pos != v->pos) - { - return u->pos < v->pos; - } - - // Use the pointers to the base objects to differentiate them. - void *up = (u->v) ? (void *) u->v : - ((u->c) ? (void *) u->c : (void *) u->ss); - void *vp = (v->v) ? (void *) v->v : - ((v->c) ? (void *) v->c : (void *) v->ss); - return up < vp; -} - - -// Note: Open must come first. -typedef enum { - Open = 1, - SegOpen = 2, - ConnPoint = 3, - SegClose = 4, - Close = 5 -} EventType; - -struct Event -{ - Event(EventType t, Node *v, double p) - : type(t), - v(v), - pos(p) - {}; - EventType type; - Node *v; - double pos; +enum ScanVisDirFlag { + VisDirNone = 0, + VisDirUp = 1, + VisDirDown = 2 }; +typedef unsigned int ScanVisDirFlags; -Event **events; - -// Used for quicksort. Must return <0, 0, or >0. -static int compare_events(const void *a, const void *b) -{ - Event *ea = *(Event**) a; - Event *eb = *(Event**) b; - if (ea->pos != eb->pos) - { - return (ea->pos < eb->pos) ? -1 : 1; - } - if (ea->type != eb->type) - { - return ea->type - eb->type; - } - COLA_ASSERT(ea->v != eb->v); - return ea->v - eb->v; -} - - -// Returns a bitfield of the direction of visibility (in this dimension) -// made up of ConnDirDown (for visibility towards lower position values) -// and ConnDirUp (for visibility towards higher position values). +// Returns a bitfield of the directions of visibility in terms of the scanline +// in a particular dimension dimension. It will return either ConnDirDown +// (meaning visibility to lower position values) or ConnDirUp (for visibility +// towards higher position values). // -static ConnDirFlags getPosVertInfDirection(VertInf *v, size_t dim) +static ScanVisDirFlags getPosVertInfDirections(VertInf *v, size_t dim) { if (dim == XDIM) // X-dimension { unsigned int dirs = v->visDirections & (ConnDirLeft | ConnDirRight); if (dirs == (ConnDirLeft | ConnDirRight)) { - return (ConnDirDown | ConnDirUp); + return (VisDirDown | VisDirUp); } else if (dirs == ConnDirLeft) { - return ConnDirDown; + return VisDirDown; } else if (dirs == ConnDirRight) { - return ConnDirUp; + return VisDirUp; } } else if (dim == YDIM) // Y-dimension @@ -526,58 +562,72 @@ static ConnDirFlags getPosVertInfDirection(VertInf *v, size_t dim) unsigned int dirs = v->visDirections & (ConnDirDown | ConnDirUp); if (dirs == (ConnDirDown | ConnDirUp)) { - return (ConnDirDown | ConnDirUp); + return (VisDirDown | VisDirUp); } else if (dirs == ConnDirDown) { - // For libavoid the Y-axis points downwards, so in terms of - // smaller or larger position values, Down is Up and vice versa. - return ConnDirUp; + // libavoid's Y-axis points downwards, so where the user has + // specified visibility downwards, this results in visibility to + // higher scanline positition values. + return VisDirUp; } else if (dirs == ConnDirUp) { - // For libavoid the Y-axis points downwards, so in terms of - // smaller or larger position values, Down is Up and vice versa. - return ConnDirDown; + // libavoid's Y-axis points downwards, so where the user has + // specified visibility upwards, this results in visibility to + // lower scanline positition values. + return VisDirDown; } } // Can occur for ConnDirNone visibility. - return ConnDirNone; + return VisDirNone; } struct PosVertInf { - PosVertInf(double p, VertInf *vI, ConnDirFlags d = ConnDirNone) + PosVertInf(double p, VertInf *vI, ScanVisDirFlags d = VisDirNone) : pos(p), vert(vI), - dir(d) + dirs(d) { } - - bool operator<(const PosVertInf& rhs) const + + bool operator<(const PosVertInf& rhs) const { if (pos != rhs.pos) { return pos < rhs.pos; } - return vert < rhs.vert; + if ((vert->id == rhs.vert->id) && (vert->id == dummyOrthogID)) + { + // Multiple dummy nodes can get placed at the same point for + // multiple ShapeConnectionPins on junctions (outside of shapes). + // We only need one at each position, so multiples can be seen + // as equal here. + return false; + } + if (vert->id != rhs.vert->id) + { + return vert->id < rhs.vert->id; + } + return dirs < rhs.dirs; } double pos; VertInf *vert; // A bitfield marking the direction of visibility (in this dimension) - // made up of ConnDirDown (for visibility towards lower position values) - // and ConnDirUp (for visibility towards higher position values). + // made up of VisDirDown (for visibility towards lower position values) + // and VisDirUp (for visibility towards higher position values). // - ConnDirFlags dir; + ScanVisDirFlags dirs; }; struct CmpVertInf -{ +{ bool operator()(const VertInf* u, const VertInf* v) const { // Comparator for VertSet, an ordered set of VertInf pointers. @@ -600,21 +650,21 @@ struct CmpVertInf typedef std::set<VertInf *, CmpVertInf> VertSet; -// A set of points to break the line segment, +// A set of points to break the line segment, // along with vertices for these points. typedef std::set<PosVertInf> BreakpointSet; -// Temporary structure used to store the possible horizontal visibility +// Temporary structure used to store the possible horizontal visibility // lines arising from the vertical sweep. -class LineSegment +class LineSegment { public: - LineSegment(const double& b, const double& f, const double& p, - bool /*ss*/ = false, VertInf *bvi = NULL, VertInf *fvi = NULL) + LineSegment(const double& b, const double& f, const double& p, + bool ss = false, VertInf *bvi = NULL, VertInf *fvi = NULL) : begin(b), finish(f), pos(p), - shapeSide(false) + shapeSide(ss) { COLA_ASSERT(begin < finish); @@ -627,7 +677,6 @@ public: vertInfs.insert(fvi); } } - LineSegment(const double& bf, const double& p, VertInf *bfvi = NULL) : begin(bf), finish(bf), @@ -639,9 +688,9 @@ public: vertInfs.insert(bfvi); } } - + // Order by begin, pos, finish. - bool operator<(const LineSegment& rhs) const + bool operator<(const LineSegment& rhs) const { if (begin != rhs.begin) { @@ -667,7 +716,7 @@ public: // Lines are exactly equal. return true; } - + if (pos == rhs.pos) { if (((begin >= rhs.begin) && (begin <= rhs.finish)) || @@ -686,14 +735,21 @@ public: finish = std::max(finish, segment.finish); vertInfs.insert(segment.vertInfs.begin(), segment.vertInfs.end()); } - + VertInf *beginVertInf(void) const { if (vertInfs.empty()) { return NULL; } - return *vertInfs.begin(); + VertInf *inf = *vertInfs.begin(); + if ( ((inf->point.y == begin) && (inf->point.x == pos)) || + ((inf->point.x == begin) && (inf->point.y == pos)) ) + { + // Only return the point if it is actually at the begin pos. + return inf; + } + return NULL; } VertInf *finishVertInf(void) const { @@ -701,7 +757,14 @@ public: { return NULL; } - return *vertInfs.rbegin(); + VertInf *inf = *vertInfs.rbegin(); + if ( ((inf->point.y == finish) && (inf->point.x == pos)) || + ((inf->point.x == finish) && (inf->point.y == pos)) ) + { + // Only return the point if it is actually at the finish pos. + return inf; + } + return NULL; } VertInf *commitPositionX(Router *router, double posX) @@ -724,7 +787,7 @@ public: return found; } // Set begin endpoint vertex if none has been assigned. - void commitBegin(Router *router, VertInf *vert = NULL) + void horiCommitBegin(Router *router, VertInf *vert = NULL) { if (vert) { @@ -734,13 +797,16 @@ public: if (vertInfs.empty() || ((*vertInfs.begin())->point.x != begin)) { - vertInfs.insert(new - VertInf(router, dummyOrthogID, Point(begin, pos))); + if (begin != -DBL_MAX) + { + vertInfs.insert(new + VertInf(router, dummyOrthogID, Point(begin, pos))); + } } } // Set begin endpoint vertex if none has been assigned. - void commitFinish(Router *router, VertInf *vert = NULL) + void horiCommitFinish(Router *router, VertInf *vert = NULL) { if (vert) { @@ -750,17 +816,20 @@ public: if (vertInfs.empty() || ((*vertInfs.rbegin())->point.x != finish)) { - vertInfs.insert(new - VertInf(router, dummyOrthogID, Point(finish, pos))); + if (finish != DBL_MAX) + { + vertInfs.insert(new + VertInf(router, dummyOrthogID, Point(finish, pos))); + } } } - // Converts a section of the points list to a set of breakPoints. - // Returns the first of the intersection points occuring at finishPos. - VertSet::iterator addSegmentsUpTo(Router */*router*/, double finishPos) + // Converts a section of the points list to a set of breakPoints. + // Returns the first of the intersection points occurring at finishPos. + VertSet::iterator addSegmentsUpTo(double finishPos) { VertSet::iterator firstIntersectionPt = vertInfs.end(); - for (VertSet::iterator vert = vertInfs.begin(); + for (VertSet::iterator vert = vertInfs.begin(); vert != vertInfs.end(); ++vert) { if ((*vert)->point.x > finishPos) @@ -768,11 +837,11 @@ public: // We're done. break; } - + breakPoints.insert(PosVertInf((*vert)->point.x, (*vert), - getPosVertInfDirection(*vert, XDIM))); + getPosVertInfDirections(*vert, XDIM))); - if ((firstIntersectionPt == vertInfs.end()) && + if ((firstIntersectionPt == vertInfs.end()) && ((*vert)->point.x == finishPos)) { firstIntersectionPt = vert; @@ -782,38 +851,125 @@ public: return firstIntersectionPt; } - // Add visibility edge(s) for this segment. There may be multiple if + // Add visibility edge(s) for this segment. There may be multiple if // one of the endpoints is shared by multiple connector endpoints. void addEdgeHorizontal(Router *router) { - commitBegin(router); - commitFinish(router); + horiCommitBegin(router); + horiCommitFinish(router); + + addSegmentsUpTo(finish); + } + + // Set flags to show what can be passed on this visibility line. + // This can be used later to disregard some edges in the visibility + // graph when routing particular connectors. + void setLongRangeVisibilityFlags(size_t dim) + { + // First, travel in one direction + bool seenConnPt = false; + bool seenShapeEdge = false; + for (BreakpointSet::iterator nvert = breakPoints.begin(); + nvert != breakPoints.end(); ++nvert) + { + VertIDProps mask = 0; + if (dim == XDIM) + { + if (seenConnPt) + { + mask |= XL_CONN; + } + if (seenShapeEdge) + { + mask |= XL_EDGE; + } + } + else // if (dim == YDIM) + { + if (seenConnPt) + { + mask |= YL_CONN; + } + if (seenShapeEdge) + { + mask |= YL_EDGE; + } + } + nvert->vert->orthogVisPropFlags |= mask; + + if (nvert->vert->id.isConnPt()) + { + seenConnPt = true; + } + if (nvert->vert->id.isOrthShapeEdge()) + { + seenShapeEdge = true; + } + } + // Then in the other direction + seenConnPt = false; + seenShapeEdge = false; + for (BreakpointSet::reverse_iterator rvert = breakPoints.rbegin(); + rvert != breakPoints.rend(); ++rvert) + { + VertIDProps mask = 0; + if (dim == XDIM) + { + if (seenConnPt) + { + mask |= XH_CONN; + } + if (seenShapeEdge) + { + mask |= XH_EDGE; + } + } + else // if (dim == YDIM) + { + if (seenConnPt) + { + mask |= YH_CONN; + } + if (seenShapeEdge) + { + mask |= YH_EDGE; + } + } + rvert->vert->orthogVisPropFlags |= mask; - addSegmentsUpTo(router, finish); + if (rvert->vert->id.isConnPt()) + { + seenConnPt = true; + } + if (rvert->vert->id.isOrthShapeEdge()) + { + seenShapeEdge = true; + } + } } // Add visibility edge(s) for this segment up until an intersection. // Then, move the segment beginning to the intersection point, so we // later only consider the remainder of the segment. - // There may be multiple segments added to the graph if the beginning + // There may be multiple segments added to the graph if the beginning // endpoint of the segment is shared by multiple connector endpoints. - VertSet addEdgeHorizontalTillIntersection(Router *router, + VertSet addEdgeHorizontalTillIntersection(Router *router, LineSegment& vertLine) { VertSet intersectionSet; - commitBegin(router); + horiCommitBegin(router); // Does a vertex already exist for this point. commitPositionX(router, vertLine.pos); - - // Generate segments and set end iterator to the first point + + // Generate segments and set end iterator to the first point // at the intersection position. - VertSet::iterator restBegin = addSegmentsUpTo(router, vertLine.pos); + VertSet::iterator restBegin = addSegmentsUpTo(vertLine.pos); // Add the intersections points to intersectionSet. VertSet::iterator restEnd = restBegin; - while ((restEnd != vertInfs.end()) && + while ((restEnd != vertInfs.end()) && (*restEnd)->point.x == vertLine.pos) { ++restEnd; @@ -826,7 +982,7 @@ public: return intersectionSet; } - + // Insert vertical breakpoints. void insertBreakpointsBegin(Router *router, LineSegment& vertLine) { @@ -839,15 +995,15 @@ public: { vert = vertLine.finishVertInf(); } - commitBegin(router, vert); + horiCommitBegin(router, vert); for (VertSet::iterator v = vertInfs.begin(); v != vertInfs.end(); ++v) { if ((*v)->point.x == begin) { - vertLine.breakPoints.insert(PosVertInf(pos, *v, - getPosVertInfDirection(*v, YDIM))); + vertLine.breakPoints.insert(PosVertInf(pos, *v, + getPosVertInfDirections(*v, YDIM))); } } } @@ -864,7 +1020,7 @@ public: { vert = vertLine.finishVertInf(); } - commitFinish(router, vert); + horiCommitFinish(router, vert); for (VertSet::iterator v = vertInfs.begin(); v != vertInfs.end(); ++v) @@ -872,37 +1028,82 @@ public: if ((*v)->point.x == finish) { vertLine.breakPoints.insert(PosVertInf(pos, *v, - getPosVertInfDirection(*v, YDIM))); + getPosVertInfDirections(*v, YDIM))); } } } void generateVisibilityEdgesFromBreakpointSet(Router *router, size_t dim) { - if ((breakPoints.begin())->pos != begin) + if (breakPoints.empty() || ((breakPoints.begin())->pos > begin)) { - if (!beginVertInf()) + // Add a begin point if there was not already an intersection + // found at that point. Though, don't do this if the line + // segment goes off to infinity -- we can't reach anything + // by going in that direction! + if (begin == -DBL_MAX) { + // Shorten line to first intersection point. + COLA_ASSERT(!breakPoints.empty()); + begin = breakPoints.begin()->pos; + } + else + { + // Add begin point. Point point(pos, pos); point[dim] = begin; - // Add begin point if it didn't intersect another line. VertInf *vert = new VertInf(router, dummyOrthogID, point); breakPoints.insert(PosVertInf(begin, vert)); } } - if ((breakPoints.rbegin())->pos != finish) + if (breakPoints.empty() || ((breakPoints.rbegin())->pos < finish)) { - if (!finishVertInf()) + // Add a finish point if there was not already an intersection + // found at that point. Though, don't do this if the line + // segment goes off to infinity -- we can't reach anything + // by going in that direction! + if (finish == DBL_MAX) + { + // Shorten line to last intersection point. + finish = breakPoints.rbegin()->pos; + } + else { + // Add finish point. Point point(pos, pos); point[dim] = finish; - // Add finish point if it didn't intersect another line. VertInf *vert = new VertInf(router, dummyOrthogID, point); breakPoints.insert(PosVertInf(finish, vert)); } } + // Set flags for orthogonal routing optimisation. + setLongRangeVisibilityFlags(dim); + const bool orthogonal = true; BreakpointSet::iterator vert, last; +#if 0 + last = breakPoints.end(); + for (vert = breakPoints.begin(); vert != breakPoints.end();) + { + if (vert->vert->id == dummyOrthogID) + { + if (last == breakPoints.end() || + (last->vert->point != vert->vert->point)) + { + last = vert; + } + else + { + // Already seen a dummy orthogonal point at this + // position, delete it. + + } + else + { + ++vert; + } + } +#endif for (vert = last = breakPoints.begin(); vert != breakPoints.end();) { BreakpointSet::iterator firstPrev = last; @@ -912,15 +1113,15 @@ public: // Assert points are not at the same position. COLA_ASSERT(vert->vert->point != last->vert->point); - if ( !(vert->vert->id.isShape || last->vert->id.isShape)) + if (vert->vert->id.isConnPt() && last->vert->id.isConnPt()) { // Here we have a pair of two endpoints that are both // connector endpoints and both are inside a shape. - + // Give vert visibility back to the first non-connector // endpoint vertex (i.e., the side of the shape). BreakpointSet::iterator side = last; - while (!side->vert->id.isShape) + while (side->vert->id.isConnPt()) { if (side == breakPoints.begin()) { @@ -928,54 +1129,58 @@ public: } --side; } - bool canSeeDown = (vert->dir & ConnDirDown); - if (canSeeDown && side->vert->id.isShape) + bool canSeeDown = (vert->dirs & VisDirDown); + if (canSeeDown && !(side->vert->id.isConnPt())) { - EdgeInf *edge = new + EdgeInf *edge = new EdgeInf(side->vert, vert->vert, orthogonal); - edge->setDist(vert->vert->point[dim] - + edge->setDist(vert->vert->point[dim] - side->vert->point[dim]); } // Give last visibility back to the first non-connector // endpoint vertex (i.e., the side of the shape). side = vert; - while ((side != breakPoints.end()) && - !side->vert->id.isShape) + while ((side != breakPoints.end()) && + side->vert->id.isConnPt()) { ++side; } - bool canSeeUp = (last->dir & ConnDirUp); + bool canSeeUp = (last->dirs & VisDirUp); if (canSeeUp && (side != breakPoints.end())) { - EdgeInf *edge = new + EdgeInf *edge = new EdgeInf(last->vert, side->vert, orthogonal); - edge->setDist(side->vert->point[dim] - + edge->setDist(side->vert->point[dim] - last->vert->point[dim]); } } - + // The normal case. // - // Note: It's okay to give two connector endpoints visbility - // here since we only consider the partner endpoint as a + // Note: It's okay to give two connector endpoints visibility + // here since we only consider the partner endpoint as a // candidate while searching if it is the other endpoint of // the connector in question. // bool generateEdge = true; - if (!last->vert->id.isShape && !(last->dir & ConnDirUp)) + if (last->vert->id.isConnPt() && !(last->dirs & VisDirUp)) { + // Don't generate the visibility segment if the ConnEnd + // doesn't have visibility in that direction. generateEdge = false; } - else if (!vert->vert->id.isShape && !(vert->dir & ConnDirDown)) + else if (vert->vert->id.isConnPt() && !(vert->dirs & VisDirDown)) { + // Don't generate the visibility segment if the ConnEnd + // doesn't have visibility in that direction. generateEdge = false; } if (generateEdge) { - EdgeInf *edge = + EdgeInf *edge = new EdgeInf(last->vert, vert->vert, orthogonal); - edge->setDist(vert->vert->point[dim] - + edge->setDist(vert->vert->point[dim] - last->vert->point[dim]); } @@ -992,8 +1197,8 @@ public: } else { - // vert has moved to the beginning of a number number group. - // Last is now in the right place, so do nothing. + // vert has moved to the beginning of a group at a new + // position. Last is now in the right place, so do nothing. } } } @@ -1001,14 +1206,16 @@ public: double begin; double finish; double pos; - bool shapeSide; + // XXX shapeSide is unused and could possibly be removed? + bool shapeSide; + VertSet vertInfs; BreakpointSet breakPoints; private: - // MSVC wants to generate the assignment operator and the default - // constructor, but fails. Therefore we declare them private and - // don't implement them. + // MSVC wants to generate the assignment operator and the default + // constructor, but fails. Therefore we declare them private and + // don't implement them. LineSegment & operator=(LineSegment const &); LineSegment(); }; @@ -1037,7 +1244,7 @@ class SegmentListWrapper } else { - // This is the first overlapping segment, so just + // This is the first overlapping segment, so just // merge the new segment with this one. curr->mergeVertInfs(segment); found = curr; @@ -1066,11 +1273,15 @@ class SegmentListWrapper // Given a router instance and a set of possible horizontal segments, and a // possible vertical visibility segment, compute and add edges to the // orthogonal visibility graph for all the visibility edges. -static void intersectSegments(Router *router, SegmentList& segments, +static void intersectSegments(Router *router, SegmentList& segments, LineSegment& vertLine) { - COLA_ASSERT(vertLine.beginVertInf() == NULL); - COLA_ASSERT(vertLine.finishVertInf() == NULL); + // XXX: It seems that this case can sometimes occur... maybe when + // there are many overlapping rectangles. + //COLA_ASSERT(vertLine.beginVertInf() == NULL); + //COLA_ASSERT(vertLine.finishVertInf() == NULL); + + COLA_ASSERT(!segments.empty()); for (SegmentList::iterator it = segments.begin(); it != segments.end(); ) { LineSegment& horiLine = *it; @@ -1078,40 +1289,28 @@ static void intersectSegments(Router *router, SegmentList& segments, bool inVertSegRegion = ((vertLine.begin <= horiLine.pos) && (vertLine.finish >= horiLine.pos)); - if (horiLine.finish < vertLine.pos) - { - // Add horizontal visibility segment. - horiLine.addEdgeHorizontal(router); - - size_t dim = XDIM; // x-dimension - horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim); - - // We've now swept past this horizontal segment, so delete. - it = segments.erase(it); - continue; - } - else if (horiLine.begin > vertLine.pos) + if (vertLine.pos < horiLine.begin) { // We've yet to reach this segment in the sweep, so ignore. ++it; continue; } - else if (horiLine.begin == vertLine.pos) + else if (vertLine.pos == horiLine.begin) { if (inVertSegRegion) { horiLine.insertBreakpointsBegin(router, vertLine); } } - else if (horiLine.finish == vertLine.pos) + else if (vertLine.pos == horiLine.finish) { if (inVertSegRegion) { // Add horizontal visibility segment. horiLine.addEdgeHorizontal(router); - + horiLine.insertBreakpointsFinish(router, vertLine); - + size_t dim = XDIM; // x-dimension horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim); @@ -1120,15 +1319,27 @@ static void intersectSegments(Router *router, SegmentList& segments, continue; } } + else if (vertLine.pos > horiLine.finish) + { + // Add horizontal visibility segment. + horiLine.addEdgeHorizontal(router); + + size_t dim = XDIM; // x-dimension + horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim); + + // We've now swept past this horizontal segment, so delete. + it = segments.erase(it); + continue; + } else { - COLA_ASSERT(horiLine.begin < vertLine.pos); - COLA_ASSERT(horiLine.finish > vertLine.pos); + COLA_ASSERT(vertLine.pos > horiLine.begin); + COLA_ASSERT(vertLine.pos < horiLine.finish); if (inVertSegRegion) { // Add horizontal visibility segment. - VertSet intersectionVerts = + VertSet intersectionVerts = horiLine.addEdgeHorizontalTillIntersection( router, vertLine); @@ -1136,7 +1347,7 @@ static void intersectSegments(Router *router, SegmentList& segments, v != intersectionVerts.end(); ++v) { vertLine.breakPoints.insert(PosVertInf(horiLine.pos, *v, - getPosVertInfDirection(*v, YDIM))); + getPosVertInfDirections(*v, YDIM))); } } } @@ -1149,16 +1360,16 @@ static void intersectSegments(Router *router, SegmentList& segments, } -// Processes an event for the vertical sweep used for computing the static -// orthogonal visibility graph. This adds possible visibility sgments to -// the segments list. +// Processes an event for the vertical sweep used for computing the static +// orthogonal visibility graph. This adds possible horizontal visibility +// segments to the segments list. // The first pass is adding the event to the scanline, the second is for // processing the event and the third for removing it from the scanline. -static void processEventVert(Router *router, NodeSet& scanline, +static void processEventVert(Router *router, NodeSet& scanline, SegmentListWrapper& segments, Event *e, unsigned int pass) { Node *v = e->v; - + if ( ((pass == 1) && (e->type == Open)) || ((pass == 2) && (e->type == ConnPoint)) ) { @@ -1168,53 +1379,54 @@ static void processEventVert(Router *router, NodeSet& scanline, NodeSet::iterator it = v->iter; // Work out neighbours - if (it != scanline.begin()) + if (it != scanline.begin()) { Node *u = *(--it); v->firstAbove = u; u->firstBelow = v; } it = v->iter; - if (++it != scanline.end()) + if (++it != scanline.end()) { Node *u = *it; v->firstBelow = u; u->firstAbove = v; } } - + if (pass == 2) { if ((e->type == Open) || (e->type == Close)) { + // Only difference between Open and Close is whether the line + // segments are at the top or bottom of the shape. Decide here. + double lineY = (e->type == Open) ? v->min[YDIM] : v->max[YDIM]; + // Shape edge positions. - double minShape = v->min[0]; - double maxShape = v->max[0]; + double minShape = v->min[XDIM]; + double maxShape = v->max[XDIM]; // As far as we can see. double minLimit, maxLimit; double minLimitMax, maxLimitMin; - v->findFirstPointAboveAndBelow(0, minLimit, maxLimit, + v->findFirstPointAboveAndBelow(XDIM, lineY, minLimit, maxLimit, minLimitMax, maxLimitMin); - // Only difference between Open and Close is whether the line - // segments are at the top or bottom of the shape. Decide here. - double lineY = (e->type == Open) ? v->min[1] : v->max[1]; - + // Insert possible visibility segments. if (minLimitMax >= maxLimitMin) { - // Insert possible visibility segments. - VertInf *vI1 = new VertInf(router, dummyOrthogID, + // These vertices represent the shape corners. + VertInf *vI1 = new VertInf(router, dummyOrthogShapeID, Point(minShape, lineY)); - VertInf *vI2 = new VertInf(router, dummyOrthogID, + VertInf *vI2 = new VertInf(router, dummyOrthogShapeID, Point(maxShape, lineY)); - + // There are no overlapping shapes, so give full visibility. if (minLimit < minShape) { segments.insert(LineSegment(minLimit, minShape, lineY, true, NULL, vI1)); } - segments.insert(LineSegment(minShape, maxShape, lineY, + segments.insert(LineSegment(minShape, maxShape, lineY, true, vI1, vI2)); if (maxShape < maxLimit) { @@ -1224,15 +1436,25 @@ static void processEventVert(Router *router, NodeSet& scanline, } else { + // There are overlapping shapes along this shape edge. + if ((minLimitMax > minLimit) && (minLimitMax >= minShape)) { - segments.insert(LineSegment(minLimit, minLimitMax, lineY, - true, NULL, NULL)); + LineSegment *line = segments.insert( + LineSegment(minLimit, minLimitMax, lineY, true)); + // Shape corner: + VertInf *vI1 = new VertInf(router, dummyOrthogShapeID, + Point(minShape, lineY)); + line->vertInfs.insert(vI1); } if ((maxLimitMin < maxLimit) && (maxLimitMin <= maxShape)) { - segments.insert(LineSegment(maxLimitMin, maxLimit, lineY, - true, NULL, NULL)); + LineSegment *line = segments.insert( + LineSegment(maxLimitMin, maxLimit, lineY, true)); + // Shape corner: + VertInf *vI2 = new VertInf(router, dummyOrthogShapeID, + Point(maxShape, lineY)); + line->vertInfs.insert(vI2); } } } @@ -1243,27 +1465,32 @@ static void processEventVert(Router *router, NodeSet& scanline, Point& cp = centreVert->point; // As far as we can see. - double minLimit = v->firstPointAbove(0); - double maxLimit = v->firstPointBelow(0); - bool inShape = v->isInsideShape(0); - + double minLimit = v->firstPointAbove(XDIM); + double maxLimit = v->firstPointBelow(XDIM); + bool inShape = v->isInsideShape(XDIM); + + // Insert if we have visibility in that direction and the segment + // length is greater than zero. LineSegment *line1 = NULL, *line2 = NULL; - if (!inShape || (centreVert->visDirections & ConnDirLeft)) + if ((centreVert->visDirections & ConnDirLeft) && (minLimit < cp.x)) { - line1 = segments.insert(LineSegment(minLimit, cp.x, e->pos, + line1 = segments.insert(LineSegment(minLimit, cp.x, e->pos, true, NULL, centreVert)); } - if (!inShape || (centreVert->visDirections & ConnDirRight)) + if ((centreVert->visDirections & ConnDirRight) && (cp.x < maxLimit)) { - line2 = segments.insert(LineSegment(cp.x, maxLimit, e->pos, + line2 = segments.insert(LineSegment(cp.x, maxLimit, e->pos, true, centreVert, NULL)); + // If there was a line1, then we just merged with it, so + // that pointer will be invalid (and now unnecessary). + line1 = NULL; } if (!line1 && !line2) { // Add a point segment for the centre point. segments.insert(LineSegment(cp.x, e->pos, centreVert)); } - + if (!inShape) { // This is not contained within a shape so add a normal @@ -1284,13 +1511,13 @@ static void processEventVert(Router *router, NodeSet& scanline, } } } - + if ( ((pass == 3) && (e->type == Close)) || ((pass == 2) && (e->type == ConnPoint)) ) { // Clean up neighbour pointers. Node *l = v->firstAbove, *r = v->firstBelow; - if (l != NULL) + if (l != NULL) { l->firstBelow = v->firstBelow; } @@ -1309,22 +1536,23 @@ static void processEventVert(Router *router, NodeSet& scanline, size_t result; result = scanline.erase(v); COLA_ASSERT(result == 1); + COLA_UNUSED(result); // Avoid warning. delete v; } } } -// Processes an event for the vertical sweep used for computing the static -// orthogonal visibility graph. This adds possible visibility sgments to -// the segments list. +// Processes an event for the vertical sweep used for computing the static +// orthogonal visibility graph. This adds possible vertical visibility +// segments to the segments list. // The first pass is adding the event to the scanline, the second is for // processing the event and the third for removing it from the scanline. -static void processEventHori(Router */*router*/, NodeSet& scanline, +static void processEventHori(Router *router, NodeSet& scanline, SegmentListWrapper& segments, Event *e, unsigned int pass) { Node *v = e->v; - + if ( ((pass == 1) && (e->type == Open)) || ((pass == 2) && (e->type == ConnPoint)) ) { @@ -1334,56 +1562,72 @@ static void processEventHori(Router */*router*/, NodeSet& scanline, NodeSet::iterator it = v->iter; // Work out neighbours - if (it != scanline.begin()) + if (it != scanline.begin()) { Node *u = *(--it); v->firstAbove = u; u->firstBelow = v; } it = v->iter; - if (++it != scanline.end()) + if (++it != scanline.end()) { Node *u = *it; v->firstBelow = u; u->firstAbove = v; } } - + if (pass == 2) { if ((e->type == Open) || (e->type == Close)) { + // Only difference between Open and Close is whether the line + // segments are at the left or right of the shape. Decide here. + double lineX = (e->type == Open) ? v->min[XDIM] : v->max[XDIM]; + // Shape edge positions. - double minShape = v->min[1]; - double maxShape = v->max[1]; + double minShape = v->min[YDIM]; + double maxShape = v->max[YDIM]; // As far as we can see. double minLimit, maxLimit; double minLimitMax, maxLimitMin; - v->findFirstPointAboveAndBelow(1, minLimit, maxLimit, + v->findFirstPointAboveAndBelow(YDIM, lineX, minLimit, maxLimit, minLimitMax, maxLimitMin); - // Only difference between Open and Close is whether the line - // segments are at the left or right of the shape. Decide here. - double lineX = (e->type == Open) ? v->min[0] : v->max[0]; - if (minLimitMax >= maxLimitMin) { - LineSegment vertSeg = LineSegment(minLimit, maxLimit, lineX); - segments.insert(vertSeg); + LineSegment *line = segments.insert( + LineSegment(minLimit, maxLimit, lineX)); + + // Shape corners: + VertInf *vI1 = new VertInf(router, dummyOrthogShapeID, + Point(lineX, minShape)); + VertInf *vI2 = new VertInf(router, dummyOrthogShapeID, + Point(lineX, maxShape)); + line->vertInfs.insert(vI1); + line->vertInfs.insert(vI2); } else { if ((minLimitMax > minLimit) && (minLimitMax >= minShape)) { - LineSegment vertSeg = - LineSegment(minLimit, minLimitMax, lineX); - segments.insert(vertSeg); + LineSegment *line = segments.insert( + LineSegment(minLimit, minLimitMax, lineX)); + + // Shape corner: + VertInf *vI1 = new VertInf(router, dummyOrthogShapeID, + Point(lineX, minShape)); + line->vertInfs.insert(vI1); } if ((maxLimitMin < maxLimit) && (maxLimitMin <= maxShape)) { - LineSegment vertSeg = - LineSegment(maxLimitMin, maxLimit, lineX); - segments.insert(vertSeg); + LineSegment *line = segments.insert( + LineSegment(maxLimitMin, maxLimit, lineX)); + + // Shape corner: + VertInf *vI2 = new VertInf(router, dummyOrthogShapeID, + Point(lineX, maxShape)); + line->vertInfs.insert(vI2); } } } @@ -1394,27 +1638,29 @@ static void processEventHori(Router */*router*/, NodeSet& scanline, Point& cp = centreVert->point; // As far as we can see. - double minLimit = v->firstPointAbove(1); - double maxLimit = v->firstPointBelow(1); - bool inShape = v->isInsideShape(1); - - if (!inShape || (centreVert->visDirections & ConnDirUp)) + double minLimit = v->firstPointAbove(YDIM); + double maxLimit = v->firstPointBelow(YDIM); + + // Insert if we have visibility in that direction and the segment + // length is greater than zero. + if ((centreVert->visDirections & ConnDirUp) && (minLimit < cp.y)) { segments.insert(LineSegment(minLimit, cp.y, e->pos)); } - if (!inShape || (centreVert->visDirections & ConnDirDown)) + + if ((centreVert->visDirections & ConnDirDown) && (cp.y < maxLimit)) { segments.insert(LineSegment(cp.y, maxLimit, e->pos)); } } } - + if ( ((pass == 3) && (e->type == Close)) || ((pass == 2) && (e->type == ConnPoint)) ) { // Clean up neighbour pointers. Node *l = v->firstAbove, *r = v->firstBelow; - if (l != NULL) + if (l != NULL) { l->firstBelow = v->firstBelow; } @@ -1433,47 +1679,138 @@ static void processEventHori(Router */*router*/, NodeSet& scanline, size_t result; result = scanline.erase(v); COLA_ASSERT(result == 1); + COLA_UNUSED(result); // Avoid warning. delete v; } } } +// Correct visibility for pins or connector endpoints on the leading or +// trailing edge of the visibility graph which may only have visibility in +// the outward direction where there will not be a possible path. +void fixConnectionPointVisibilityOnOutsideOfVisibilityGraph(Event **events, + size_t totalEvents, ConnDirFlags addedVisibility) +{ + if (totalEvents > 0) + { + double firstPos = events[0]->pos; + size_t index = 0; + while (index < totalEvents) + { + if (events[index]->pos > firstPos) + { + break; + } + + if (events[index]->v->c) + { + events[index]->v->c->visDirections |= addedVisibility; + } + ++index; + } + index = 0; + double lastPos = events[totalEvents - 1]->pos; + while (index < totalEvents) + { + size_t revIndex = totalEvents - 1 - index; + if (events[revIndex]->pos < lastPos) + { + break; + } + + if (events[revIndex]->v->c) + { + events[revIndex]->v->c->visDirections |= addedVisibility; + } + ++index; + } + } +} extern void generateStaticOrthogonalVisGraph(Router *router) { - const size_t n = router->shapeRefs.size(); + const size_t n = router->m_obstacles.size(); const unsigned cpn = router->vertices.connsSize(); // Set up the events for the vertical sweep. size_t totalEvents = (2 * n) + cpn; - events = new Event*[totalEvents]; + Event **events = new Event*[totalEvents]; unsigned ctr = 0; - ShapeRefList::iterator shRefIt = router->shapeRefs.begin(); + ObstacleList::iterator obstacleIt = router->m_obstacles.begin(); for (unsigned i = 0; i < n; i++) { - ShapeRef *shRef = *shRefIt; - double minX, minY, maxX, maxY; - shRef->polygon().getBoundingRect(&minX, &minY, &maxX, &maxY); - double midX = minX + ((maxX - minX) / 2); - Node *v = new Node(shRef, midX); - events[ctr++] = new Event(Open, v, minY); - events[ctr++] = new Event(Close, v, maxY); - - ++shRefIt; + Obstacle *obstacle = *obstacleIt; +#ifndef PAPER + JunctionRef *junction = dynamic_cast<JunctionRef *> (obstacle); + if (junction && ! junction->positionFixed()) + { + // Junctions that are free to move are not treated as obstacles. + ++obstacleIt; + totalEvents -= 2; + continue; + } +#endif + + Box bbox = obstacle->routingBox(); + double midX = bbox.min.x + ((bbox.max.x - bbox.min.x) / 2); + Node *v = new Node(obstacle, midX); + events[ctr++] = new Event(Open, v, bbox.min.y); + events[ctr++] = new Event(Close, v, bbox.max.y); + + ++obstacleIt; + } + +#ifdef DEBUGHANDLER + if (router->debugHandler()) + { + std::vector<Box> obstacleBoxes; + ObstacleList::iterator obstacleIt = router->m_obstacles.begin(); + for (unsigned i = 0; i < n; i++) + { + Obstacle *obstacle = *obstacleIt; + JunctionRef *junction = dynamic_cast<JunctionRef *> (obstacle); + if (junction && ! junction->positionFixed()) + { + // Junctions that are free to move are not treated as obstacles. + ++obstacleIt; + continue; + } + Box bbox = obstacle->routingBox(); + obstacleBoxes.push_back(bbox); + ++obstacleIt; + } + router->debugHandler()->updateObstacleBoxes(obstacleBoxes); } - for (VertInf *curr = router->vertices.connsBegin(); - curr && (curr != router->vertices.shapesBegin()); +#endif + + for (VertInf *curr = router->vertices.connsBegin(); + curr && (curr != router->vertices.shapesBegin()); curr = curr->lstNext) { + if (curr->visDirections == ConnDirNone) + { + // This is a connector endpoint that is attached to a connection + // pin on a shape, so it doesn't need to be given visibility. + // Thus, skip it and record that there is one less total event. + --totalEvents; + continue; + } Point& point = curr->point; Node *v = new Node(curr, point.x); events[ctr++] = new Event(ConnPoint, v, point.y); } qsort((Event*)events, (size_t) totalEvents, sizeof(Event*), compare_events); - - // Process the vertical sweep. + + // Correct visibility for pins or connector endpoints on the leading or + // trailing edge of the visibility graph which may only have visibility in + // the outward direction where there will not be a possible path. We + // fix this by giving them visibility left and right. + fixConnectionPointVisibilityOnOutsideOfVisibilityGraph(events, totalEvents, + (ConnDirLeft | ConnDirRight)); + + // Process the vertical sweep -- creating cadidate horizontal edges. // We do multiple passes over sections of the list so we can add relevant - // entries to the scanline that might follow, before process them. + // entries to the scanline that might follow, before processing them. SegmentListWrapper segments; NodeSet scanline; double thisPos = (totalEvents > 0) ? events[0]->pos : 0; @@ -1481,6 +1818,11 @@ extern void generateStaticOrthogonalVisGraph(Router *router) unsigned int posFinishIndex = 0; for (unsigned i = 0; i <= totalEvents; ++i) { + // Progress reporting and continuation check. + router->performContinuationCheck( + TransactionPhaseOrthogonalVisibilityGraphScanX, + i, totalEvents); + // If we have finished the current scanline or all events, then we // process the events on the current scanline in a couple of passes. if ((i == totalEvents) || (events[i]->pos != thisPos)) @@ -1490,7 +1832,7 @@ extern void generateStaticOrthogonalVisGraph(Router *router) { for (unsigned j = posStartIndex; j < posFinishIndex; ++j) { - processEventVert(router, scanline, segments, + processEventVert(router, scanline, segments, events[j], pass); } } @@ -1505,12 +1847,12 @@ extern void generateStaticOrthogonalVisGraph(Router *router) posStartIndex = i; } - // Do the first sweep event handling -- building the correct + // Do the first sweep event handling -- building the correct // structure of the scanline. const int pass = 1; processEventVert(router, scanline, segments, events[i], pass); } - COLA_ASSERT(scanline.empty()); + COLA_ASSERT(scanline.size() == 0); for (unsigned i = 0; i < totalEvents; ++i) { delete events[i]; @@ -1521,23 +1863,38 @@ extern void generateStaticOrthogonalVisGraph(Router *router) // Set up the events for the horizontal sweep. SegmentListWrapper vertSegments; ctr = 0; - shRefIt = router->shapeRefs.begin(); + obstacleIt = router->m_obstacles.begin(); for (unsigned i = 0; i < n; i++) { - ShapeRef *shRef = *shRefIt; - double minX, minY, maxX, maxY; - shRef->polygon().getBoundingRect(&minX, &minY, &maxX, &maxY); - double midY = minY + ((maxY - minY) / 2); - Node *v = new Node(shRef, midY); - events[ctr++] = new Event(Open, v, minX); - events[ctr++] = new Event(Close, v, maxX); - - ++shRefIt; + Obstacle *obstacle = *obstacleIt; +#ifndef PAPER + JunctionRef *junction = dynamic_cast<JunctionRef *> (obstacle); + if (junction && ! junction->positionFixed()) + { + // Junctions that are free to move are not treated as obstacles. + ++obstacleIt; + continue; + } +#endif + Box bbox = obstacle->routingBox(); + double midY = bbox.min.y + ((bbox.max.y - bbox.min.y) / 2); + Node *v = new Node(obstacle, midY); + events[ctr++] = new Event(Open, v, bbox.min.x); + events[ctr++] = new Event(Close, v, bbox.max.x); + + ++obstacleIt; } - for (VertInf *curr = router->vertices.connsBegin(); - curr && (curr != router->vertices.shapesBegin()); + for (VertInf *curr = router->vertices.connsBegin(); + curr && (curr != router->vertices.shapesBegin()); curr = curr->lstNext) { + if (curr->visDirections == ConnDirNone) + { + // This is a connector endpoint that is attached to a connection + // pin on a shape, so it doesn't need to be given visibility. + // Thus, skip it. + continue; + } Point& point = curr->point; Node *v = new Node(curr, point.y); @@ -1545,11 +1902,23 @@ extern void generateStaticOrthogonalVisGraph(Router *router) } qsort((Event*)events, (size_t) totalEvents, sizeof(Event*), compare_events); - // Process the horizontal sweep + // Correct visibility for pins or connector endpoints on the leading or + // trailing edge of the visibility graph which may only have visibility in + // the outward direction where there will not be a possible path. We + // fix this by giving them visibility up and down. + fixConnectionPointVisibilityOnOutsideOfVisibilityGraph(events, totalEvents, + (ConnDirUp | ConnDirDown)); + + // Process the horizontal sweep -- creating vertical visibility edges. thisPos = (totalEvents > 0) ? events[0]->pos : 0; posStartIndex = 0; for (unsigned i = 0; i <= totalEvents; ++i) { + // Progress reporting and continuation check. + router->performContinuationCheck( + TransactionPhaseOrthogonalVisibilityGraphScanY, + i, totalEvents); + // If we have finished the current scanline or all events, then we // process the events on the current scanline in a couple of passes. if ((i == totalEvents) || (events[i]->pos != thisPos)) @@ -1559,11 +1928,11 @@ extern void generateStaticOrthogonalVisGraph(Router *router) { for (unsigned j = posStartIndex; j < posFinishIndex; ++j) { - processEventHori(router, scanline, vertSegments, + processEventHori(router, scanline, vertSegments, events[j], pass); } } - + // Process the merged line segments. vertSegments.list().sort(); for (SegmentList::iterator curr = vertSegments.list().begin(); @@ -1583,27 +1952,27 @@ extern void generateStaticOrthogonalVisGraph(Router *router) posStartIndex = i; } - // Do the first sweep event handling -- building the correct + // Do the first sweep event handling -- building the correct // structure of the scanline. const int pass = 1; processEventHori(router, scanline, vertSegments, events[i], pass); } - COLA_ASSERT(scanline.empty()); + COLA_ASSERT(scanline.size() == 0); for (unsigned i = 0; i < totalEvents; ++i) { delete events[i]; } - delete [] events; + delete [] events; - // Add portions of the horizontal line that are after the final vertical + // Add portions of horizontal lines that are after the final vertical // position we considered. - for (SegmentList::iterator it = segments.list().begin(); + for (SegmentList::iterator it = segments.list().begin(); it != segments.list().end(); ) { LineSegment& horiLine = *it; horiLine.addEdgeHorizontal(router); - + size_t dim = XDIM; // x-dimension horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim); @@ -1617,386 +1986,300 @@ extern void generateStaticOrthogonalVisGraph(Router *router) //============================================================================ +typedef std::pair<Point, Point> RectBounds; - -// Processes sweep events used to determine each horizontal and vertical -// line segment in a connector's channel of visibility. -// Four calls to this function are made at each position by the scanline: -// 1) Handle all Close event processing. -// 2) Remove Close event objects from the scanline. -// 3) Add Open event objects to the scanline. -// 4) Handle all Open event processing. -// -static void processShiftEvent(Router */*router*/, NodeSet& scanline, - ShiftSegmentList& /*segments*/, Event *e, size_t dim, - unsigned int pass) +static bool insideRectBounds(const Point& point, const RectBounds& rectBounds) { - Node *v = e->v; - - if ( ((pass == 3) && (e->type == Open)) || - ((pass == 3) && (e->type == SegOpen)) ) + Point zero(0, 0); + if ((rectBounds.first == zero) && (rectBounds.second == zero)) { - std::pair<NodeSet::iterator, bool> result = scanline.insert(v); - v->iter = result.first; - COLA_ASSERT(result.second); - - NodeSet::iterator it = v->iter; - // Work out neighbours - if (it != scanline.begin()) - { - Node *u = *(--it); - v->firstAbove = u; - u->firstBelow = v; - } - it = v->iter; - if (++it != scanline.end()) - { - Node *u = *it; - v->firstBelow = u; - u->firstAbove = v; - } - } - - if ( ((pass == 4) && (e->type == Open)) || - ((pass == 4) && (e->type == SegOpen)) || - ((pass == 1) && (e->type == SegClose)) || - ((pass == 1) && (e->type == Close)) ) - { - if (v->ss) - { - // As far as we can see. - double minLimit = v->firstObstacleAbove(dim); - double maxLimit = v->firstObstacleBelow(dim); - - v->ss->minSpaceLimit = - std::max(minLimit, v->ss->minSpaceLimit); - v->ss->maxSpaceLimit = - std::min(maxLimit, v->ss->maxSpaceLimit); - } - else - { - v->markShiftSegmentsAbove(dim); - v->markShiftSegmentsBelow(dim); - } + // We can't be inside the invalid rectangle. + return false; } - if ( ((pass == 2) && (e->type == SegClose)) || - ((pass == 2) && (e->type == Close)) ) + for (size_t i = 0; i < 2; ++i) { - // Clean up neighbour pointers. - Node *l = v->firstAbove, *r = v->firstBelow; - if (l != NULL) + if (point[i] < rectBounds.first[i]) { - l->firstBelow = v->firstBelow; + return false; } - if (r != NULL) + if (point[i] > rectBounds.second[i]) { - r->firstAbove = v->firstAbove; + return false; } - - size_t result; - result = scanline.erase(v); - COLA_ASSERT(result == 1); - delete v; } + return true; } -static void buildOrthogonalChannelInfo(Router *router, +static void buildOrthogonalNudgingSegments(Router *router, const size_t dim, ShiftSegmentList& segmentList) { - if (router->routingPenalty(segmentPenalty) == 0) + if (router->routingParameter(segmentPenalty) == 0) { - // This code assumes the routes are pretty optimal, so we don't - // do this adjustment if the routes have no segment penalty. + // The nudging code assumes the routes are pretty optimal. This will + // only be true if a segment penalty is set, so just return if this + // is not the case. return; } + bool nudgeFinalSegments = + router->routingOption(nudgeOrthogonalSegmentsConnectedToShapes); + std::vector<RectBounds> shapeLimits; + if (nudgeFinalSegments) + { + // If we're going to nudge final segments, then cache the shape + // rectangles to save us rebuilding them multiple times. + const size_t n = router->m_obstacles.size(); + shapeLimits = std::vector<RectBounds>(n); + + double zeroBufferDist = 0.0; + + ObstacleList::iterator obstacleIt = router->m_obstacles.begin(); + for (unsigned i = 0; i < n; i++) + { + ShapeRef *shape = dynamic_cast<ShapeRef *> (*obstacleIt); + JunctionRef *junction = dynamic_cast<JunctionRef *> (*obstacleIt); + if (shape) + { + // Take the real bounds of the shape + Box bBox = shape->polygon().offsetBoundingBox(zeroBufferDist); + shapeLimits[i] = std::make_pair(bBox.min, bBox.max); + } + else if (junction) + { + // Don't nudge segments attached to junctions, + // so just use the junction position here. + Point pos = junction->position(); + shapeLimits[i] = std::make_pair(pos, pos); + } + ++obstacleIt; + } + } size_t altDim = (dim + 1) % 2; // For each connector. - for (ConnRefList::const_iterator curr = router->connRefs.begin(); - curr != router->connRefs.end(); ++curr) + for (ConnRefList::const_iterator curr = router->connRefs.begin(); + curr != router->connRefs.end(); ++curr) { if ((*curr)->routingType() != ConnType_Orthogonal) { continue; } Polygon& displayRoute = (*curr)->displayRoute(); - // Determine all line segments that we are interested in shifting. + // Determine all line segments that we are interested in shifting. // We don't consider the first or last segment of a path. - for (size_t i = 1; i < displayRoute.size()-1; ++i) + for (size_t i = 1; i < displayRoute.size(); ++i) { if (displayRoute.ps[i - 1][dim] == displayRoute.ps[i][dim]) { // It's a segment in the dimension we are processing, size_t indexLow = i - 1; size_t indexHigh = i; - if (displayRoute.ps[i - 1][altDim] > displayRoute.ps[i][altDim]) + if (displayRoute.ps[i - 1][altDim] == + displayRoute.ps[i][altDim]) + { + // This is a zero length segment, so ignore it. + continue; + } + else if (displayRoute.ps[i - 1][altDim] > + displayRoute.ps[i][altDim]) { indexLow = i; indexHigh = i - 1; } - COLA_ASSERT(displayRoute.at(indexLow)[altDim] < - displayRoute.at(indexHigh)[altDim]); + // Find the checkpoints on the current segment and the + // checkpoints on the adjoining segments that aren't on + // the corner (hence the +1 and -1 modifiers). + std::vector<Point> checkpoints = + displayRoute.checkpointsOnSegment(i - 1); + std::vector<Point> prevCheckpoints = + displayRoute.checkpointsOnSegment(i - 2, -1); + std::vector<Point> nextCheckpoints = + displayRoute.checkpointsOnSegment(i, +1); + bool hasCheckpoints = (checkpoints.size() > 0); + if (hasCheckpoints && !nudgeFinalSegments) + { + // This segment includes one of the routing + // checkpoints so we shouldn't shift it. + segmentList.push_back(new NudgingShiftSegment( + *curr, indexLow, indexHigh, dim)); + continue; + } + + double thisPos = displayRoute.ps[i][dim]; + if ((i == 1) || ((i + 1) == displayRoute.size())) { - // The first and last segment of a connector can't be - // shifted. We call them fixed segments. Note: this - // will change if we later allow connection channels. - segmentList.push_back( - ShiftSegment(*curr, indexLow, indexHigh, dim)); + // Is first or last segment of route. + + if (nudgeFinalSegments) + { + // Determine available space for nudging these + // final segments. + double minLim = -CHANNEL_MAX; + double maxLim = CHANNEL_MAX; + + // If the position of the opposite end of the + // attached segment is within the shape boundaries + // then we want to use this as an ideal position + // for the segment. + + // Bitflags indicating whether this segment starts + // and/or ends in a shape. + unsigned int endsInShapes = 0; + // Also limit their movement to the edges of the + // shapes they begin or end within. + for (size_t k = 0; k < shapeLimits.size(); ++k) + { + double shapeMin = shapeLimits[k].first[dim]; + double shapeMax = shapeLimits[k].second[dim]; + if (insideRectBounds(displayRoute.ps[i - 1], + shapeLimits[k])) + { + minLim = std::max(minLim, shapeMin); + maxLim = std::min(maxLim, shapeMax); + endsInShapes |= 0x01; + } + if (insideRectBounds(displayRoute.ps[i], + shapeLimits[k])) + { + minLim = std::max(minLim, shapeMin); + maxLim = std::min(maxLim, shapeMax); + endsInShapes |= 0x10; + } + } + + if ( endsInShapes == 0 ) + { + // If the segment is not within a shape, then we + // should limit it's nudging buffer so we don't + // combine many unnecessary regions. + double pos = displayRoute.ps[i - 1][dim]; + double freeConnBuffer = 15; + minLim = std::max(minLim, pos - freeConnBuffer); + maxLim = std::min(maxLim, pos + freeConnBuffer); + } + + if ((minLim == maxLim) || (*curr)->hasFixedRoute()) + { + // Fixed. + segmentList.push_back(new NudgingShiftSegment(*curr, + indexLow, indexHigh, dim)); + } + else + { + // Shiftable. + NudgingShiftSegment *segment = new NudgingShiftSegment( + *curr, indexLow, indexHigh, false, false, dim, + minLim, maxLim); + segment->finalSegment = true; + segment->endsInShape = (endsInShapes > 0); + if ((displayRoute.size() == 2) && + (endsInShapes = 0x11)) + { + // This is a single segment connector bridging + // two shapes. So, we want to try to keep the + // segment centred rather than shift it. + segment->singleConnectedSegment = true; + } + segmentList.push_back(segment); + } + } + else + { + // The first and last segment of a connector can't be + // shifted. We call them fixed segments. + segmentList.push_back(new NudgingShiftSegment(*curr, + indexLow, indexHigh, dim)); + } continue; } + // The segment probably has space to be shifted. double minLim = -CHANNEL_MAX; double maxLim = CHANNEL_MAX; - bool isSBend = false; - double prevPos = displayRoute.ps[i - 2][dim]; - double nextPos = displayRoute.ps[i + 1][dim]; - if (((prevPos < displayRoute.ps[i][dim]) && - (nextPos > displayRoute.ps[i][dim])) - || - ((prevPos > displayRoute.ps[i][dim]) && - (nextPos < displayRoute.ps[i][dim])) ) + // Constrain these segments by checkpoints along the + // adjoining segments. Ignore checkpoints at ends of + // those segments. XXX Perhaps this should not + // affect the ideal centre position in the channel. + for (size_t cp = 0; cp < nextCheckpoints.size(); ++cp) { - isSBend = true; - - // Determine limits if the s-bend is not due to an - // obstacle. In this case we need to limit the channel - // to the span of the adjoining segments to this one. - if ((prevPos < displayRoute.ps[i][dim]) && - (nextPos > displayRoute.ps[i][dim])) + if (nextCheckpoints[cp][dim] < thisPos) { - minLim = std::max(minLim, prevPos); - maxLim = std::min(maxLim, nextPos); + // Not at thisPoint, so constrain. + minLim = std::max(minLim, nextCheckpoints[cp][dim]); } - else + else if (nextCheckpoints[cp][dim] > thisPos) { - minLim = std::max(minLim, nextPos); - maxLim = std::min(maxLim, prevPos); + // Not at thisPoint, so constrain. + maxLim = std::min(maxLim, nextCheckpoints[cp][dim]); } } - else + for (size_t cp = 0; cp < prevCheckpoints.size(); ++cp) { - // isCBend: Both adjoining segments are in the same - // direction. We indicate this for later by setting - // the maxLim or minLim to the segment position. - if (prevPos < displayRoute.ps[i][dim]) + if (prevCheckpoints[cp][dim] < thisPos) { - minLim = displayRoute.ps[i][dim]; + // Not at thisPoint, so constrain. + minLim = std::max(minLim, prevCheckpoints[cp][dim]); } - else + else if (prevCheckpoints[cp][dim] > thisPos) { - maxLim = displayRoute.ps[i][dim]; + // Not at thisPoint, so constrain. + maxLim = std::min(maxLim, prevCheckpoints[cp][dim]); } } - segmentList.push_back(ShiftSegment(*curr, indexLow, - indexHigh, isSBend, dim, minLim, maxLim)); - } - } - } - if (segmentList.empty()) - { - // There are no segments, so we can just return now. - return; - } - - // Do a sweep and shift these segments. - const size_t n = router->shapeRefs.size(); - const size_t cpn = segmentList.size(); - // Set up the events for the sweep. - size_t totalEvents = 2 * (n + cpn); - events = new Event*[totalEvents]; - unsigned ctr = 0; - ShapeRefList::iterator shRefIt = router->shapeRefs.begin(); - for (unsigned i = 0; i < n; i++) - { - ShapeRef *shRef = *shRefIt; - Point min, max; - shRef->polygon().getBoundingRect(&min.x, &min.y, &max.x, &max.y); - double mid = min[dim] + ((max[dim] - min[dim]) / 2); - Node *v = new Node(shRef, mid); - events[ctr++] = new Event(Open, v, min[altDim]); - events[ctr++] = new Event(Close, v, max[altDim]); - - ++shRefIt; - } - for (ShiftSegmentList::iterator curr = segmentList.begin(); - curr != segmentList.end(); ++curr) - { - const Point& lowPt = curr->lowPoint(); - const Point& highPt = curr->highPoint(); - - COLA_ASSERT(lowPt[dim] == highPt[dim]); - COLA_ASSERT(lowPt[altDim] < highPt[altDim]); - Node *v = new Node(&(*curr), lowPt[dim]); - events[ctr++] = new Event(SegOpen, v, lowPt[altDim]); - events[ctr++] = new Event(SegClose, v, highPt[altDim]); - } - qsort((Event*)events, (size_t) totalEvents, sizeof(Event*), compare_events); + bool isSBend = false; + bool isZBend = false; - // Process the sweep. - // We do multiple passes over sections of the list so we can add relevant - // entries to the scanline that might follow, before process them. - NodeSet scanline; - double thisPos = (totalEvents > 0) ? events[0]->pos : 0; - unsigned int posStartIndex = 0; - unsigned int posFinishIndex = 0; - for (unsigned i = 0; i <= totalEvents; ++i) - { - // If we have finished the current scanline or all events, then we - // process the events on the current scanline in a couple of passes. - if ((i == totalEvents) || (events[i]->pos != thisPos)) - { - posFinishIndex = i; - for (int pass = 2; pass <= 4; ++pass) - { - for (unsigned j = posStartIndex; j < posFinishIndex; ++j) + if (checkpoints.empty()) { - processShiftEvent(router, scanline, segmentList, events[j], - dim, pass); + // Segments with checkpoints are held in place, but for + // other segments, we should limit their movement based + // on the limits of the segments at either end. + + double prevPos = displayRoute.ps[i - 2][dim]; + double nextPos = displayRoute.ps[i + 1][dim]; + if ( ((prevPos < thisPos) && (nextPos > thisPos)) || + ((prevPos > thisPos) && (nextPos < thisPos)) ) + { + // Determine limits if the s-bend is not due to an + // obstacle. In this case we need to limit the channel + // to the span of the adjoining segments to this one. + if ((prevPos < thisPos) && (nextPos > thisPos)) + { + minLim = std::max(minLim, prevPos); + maxLim = std::min(maxLim, nextPos); + isZBend = true; + } + else // if ((prevPos > thisPos) && (nextPos < thisPos)) + { + minLim = std::max(minLim, nextPos); + maxLim = std::min(maxLim, prevPos); + isSBend = true; + } + } } - } - if (i == totalEvents) - { - // We have cleaned up, so we can now break out of loop. - break; + NudgingShiftSegment *nss = new NudgingShiftSegment(*curr, + indexLow, indexHigh, isSBend, isZBend, dim, + minLim, maxLim); + nss->checkpoints = checkpoints; + segmentList.push_back(nss); } - - thisPos = events[i]->pos; - posStartIndex = i; } - - // Do the first sweep event handling -- building the correct - // structure of the scanline. - const int pass = 1; - processShiftEvent(router, scanline, segmentList, events[i], - dim, pass); } - COLA_ASSERT(scanline.empty()); - for (unsigned i = 0; i < totalEvents; ++i) - { - delete events[i]; - } - delete [] events; } -static void simplifyOrthogonalRoutes(Router *router) -{ - // Simplify routes. - for (ConnRefList::const_iterator curr = router->connRefs.begin(); - curr != router->connRefs.end(); ++curr) - { - if ((*curr)->routingType() != ConnType_Orthogonal) - { - continue; - } - (*curr)->set_route((*curr)->displayRoute().simplify()); - } -} - - -static void buildOrthogonalNudgingOrderInfo(Router *router, - PtOrderMap& pointOrders) -{ - // Simplify routes. - simplifyOrthogonalRoutes(router); - - int crossingsN = 0; - - // Do segment splitting. - for (ConnRefList::const_iterator curr = router->connRefs.begin(); - curr != router->connRefs.end(); ++curr) - { - if ((*curr)->routingType() != ConnType_Orthogonal) - { - continue; - } - ConnRef *conn = *curr; - - for (ConnRefList::const_iterator curr2 = router->connRefs.begin(); - curr2 != router->connRefs.end(); ++curr2) - { - if ((*curr2)->routingType() != ConnType_Orthogonal) - { - continue; - } - ConnRef *conn2 = *curr2; - - if (conn == conn2) - { - continue; - } - - Avoid::Polygon& route = conn->displayRoute(); - Avoid::Polygon& route2 = conn2->displayRoute(); - splitBranchingSegments(route2, true, route); - } - } - - for (ConnRefList::const_iterator curr = router->connRefs.begin(); - curr != router->connRefs.end(); ++curr) - { - if ((*curr)->routingType() != ConnType_Orthogonal) - { - continue; - } - ConnRef *conn = *curr; - - for (ConnRefList::const_iterator curr2 = curr; - curr2 != router->connRefs.end(); ++curr2) - { - if ((*curr2)->routingType() != ConnType_Orthogonal) - { - continue; - } - ConnRef *conn2 = *curr2; - - if (conn == conn2) - { - continue; - } +typedef std::vector<ConnRef *> ConnRefVector; +typedef std::vector<Polygon> RouteVector; - Avoid::Polygon& route = conn->displayRoute(); - Avoid::Polygon& route2 = conn2->displayRoute(); - bool checkForBranchingSegments = false; - int crossings = 0; - for (size_t i = 1; i < route.size(); ++i) - { - const bool finalSegment = ((i + 1) == route.size()); - crossings += countRealCrossings(route2, true, route, i, - checkForBranchingSegments, finalSegment, NULL, - &pointOrders, conn2, conn).first; - } - if (crossings > 0) - { - crossingsN += crossings; - } - } - } - - // Sort the point orders. - PtOrderMap::iterator finish = pointOrders.end(); - for (PtOrderMap::iterator it = pointOrders.begin(); it != finish; ++it) - { - //const VertID& ptID = it->first; - PtOrder& order = it->second; - - for (size_t dim = XDIM; dim <= YDIM; ++dim) - { - order.sort(dim); - } - } -} - -class CmpLineOrder +class CmpLineOrder { public: CmpLineOrder(PtOrderMap& ord, const size_t dim) @@ -2004,66 +2287,73 @@ class CmpLineOrder dimension(dim) { } - bool operator()(const ShiftSegment& lhs, const ShiftSegment& rhs, + bool operator()(const ShiftSegment *lhsSuper, + const ShiftSegment *rhsSuper, bool *comparable = NULL) const { + const NudgingShiftSegment *lhs = + static_cast<const NudgingShiftSegment *> (lhsSuper); + const NudgingShiftSegment *rhs = + static_cast<const NudgingShiftSegment *> (rhsSuper); if (comparable) { *comparable = true; } - Point lhsLow = lhs.lowPoint(); - Point rhsLow = rhs.lowPoint(); -#ifndef NDEBUG - const Point& lhsHigh = lhs.highPoint(); - const Point& rhsHigh = rhs.highPoint(); -#endif + Point lhsLow = lhs->lowPoint(); + Point rhsLow = rhs->lowPoint(); size_t altDim = (dimension + 1) % 2; - +#ifndef NDEBUG + const Point& lhsHigh = lhs->highPoint(); + const Point& rhsHigh = rhs->highPoint(); COLA_ASSERT(lhsLow[dimension] == lhsHigh[dimension]); COLA_ASSERT(rhsLow[dimension] == rhsHigh[dimension]); +#endif + // We consider things at effectively the same position to + // be ordered based on their order and fixedOrder, so only + // compare segments further apart than the nudgeDistance. if (lhsLow[dimension] != rhsLow[dimension]) { return lhsLow[dimension] < rhsLow[dimension]; } // If one of these is fixed, then determine order based on - // fixed segment, that is, order so the fixed segment doesn't + // fixed segment, that is, order so the fixed segment doesn't // block movement. bool oneIsFixed = false; - const int lhsFixedOrder = lhs.fixedOrder(oneIsFixed); - const int rhsFixedOrder = rhs.fixedOrder(oneIsFixed); + const int lhsFixedOrder = lhs->fixedOrder(oneIsFixed); + const int rhsFixedOrder = rhs->fixedOrder(oneIsFixed); if (oneIsFixed && (lhsFixedOrder != rhsFixedOrder)) { return lhsFixedOrder < rhsFixedOrder; } - // C-bends that did not have a clear order with s-bends might - // not have a good ordering here, so compare their order in + // C-bends that did not have a clear order with s-bends might + // not have a good ordering here, so compare their order in // terms of C-bend direction and S-bends and use that if it // differs for the two segments. - const int lhsOrder = lhs.order(); - const int rhsOrder = rhs.order(); + const int lhsOrder = lhs->order(); + const int rhsOrder = rhs->order(); if (lhsOrder != rhsOrder) { return lhsOrder < rhsOrder; } - + // Need to index using the original point into the map, so find it. Point& unchanged = (lhsLow[altDim] > rhsLow[altDim]) ? lhsLow : rhsLow; PtOrder& lowOrder = orders[unchanged]; - int lhsPos = lowOrder.positionFor(lhs.connRef, dimension); - int rhsPos = lowOrder.positionFor(rhs.connRef, dimension); + int lhsPos = lowOrder.positionFor(dimension, lhs->connRef); + int rhsPos = lowOrder.positionFor(dimension, rhs->connRef); if ((lhsPos == -1) || (rhsPos == -1)) { // A value for rhsPos or lhsPos mean the points are not directly // comparable, meaning they are at the same position but cannot - // overlap (they are just collinear. The relative order for + // overlap (they are just collinear. The relative order for // these segments is not important since we do not constrain // them against each other. - //COLA_ASSERT(lhs.overlapsWith(rhs, dimension) == false); + //COLA_ASSERT(lhs->overlapsWith(rhs, dimension) == false); // We do need to be consistent though. if (comparable) { @@ -2071,7 +2361,6 @@ class CmpLineOrder } return lhsLow[altDim] < rhsLow[altDim]; } - return lhsPos < rhsPos; } @@ -2080,29 +2369,63 @@ class CmpLineOrder }; -// We can use the normaal sort algorithm for lists since it is not possible -// to comapre all elements, but there will be an ordering defined between -// most of the elements. Hence we order these, using insertion sort, and -// the case of them not being able to be compared is handled by not setting +// We can't use the normal sort algorithm for lists since it is not possible +// to compare all elements, but there will be an ordering defined between +// most of the elements. Hence we order these, using insertion sort, and +// the case of them not being able to be compared is handled by not setting // up any constraints between such segments when doing the nudging. // -static ShiftSegmentList linesort(ShiftSegmentList origList, - CmpLineOrder& comparison) +static ShiftSegmentList linesort(bool nudgeFinalSegments, + ShiftSegmentList origList, CmpLineOrder& comparison) { + // Cope with end segments that are getting moved and will line up with + // other segments of the same connector. We do this by merging them into + // a single NudgingShiftSegment. + if (nudgeFinalSegments) + { + for (ShiftSegmentList::iterator currSegIt = origList.begin(); + currSegIt != origList.end(); ++currSegIt) + { + for (ShiftSegmentList::iterator otherSegIt = currSegIt; + otherSegIt != origList.end(); ) + { + NudgingShiftSegment *currSeg = + static_cast<NudgingShiftSegment *> (*currSegIt); + NudgingShiftSegment *otherSeg = + static_cast<NudgingShiftSegment *> (*otherSegIt); + if ((currSegIt != otherSegIt) && currSeg && otherSeg && + currSeg->shouldAlignWith(otherSeg, comparison.dimension)) + { + currSeg->mergeWith(otherSeg, comparison.dimension); + delete otherSeg; + otherSegIt = origList.erase(otherSegIt); + } + else + { + ++otherSegIt; + } + } + } + } + ShiftSegmentList resultList; + size_t origListSize = origList.size(); + size_t deferredN = 0; while (!origList.empty()) { // Get and remove the first element from the origList. - ShiftSegment segment = origList.front(); + ShiftSegment *segment = origList.front(); origList.pop_front(); // Find the insertion point in the resultList. + bool allComparable = true; ShiftSegmentList::iterator curr; for (curr = resultList.begin(); curr != resultList.end(); ++curr) { bool comparable = false; bool lessThan = comparison(segment, *curr, &comparable); + allComparable &= comparable; if (comparable && lessThan) { @@ -2111,9 +2434,22 @@ static ShiftSegmentList linesort(ShiftSegmentList origList, break; } } - - // Insert the element into the reultList at the required point. - resultList.insert(curr, segment); + + if (resultList.empty() || allComparable || (deferredN >= origListSize)) + { + // Insert the element into the resultList at the required point. + resultList.insert(curr, segment); + // Reset the origListSize and deferred counter. + deferredN = 0; + origListSize = origList.size(); + } + else + { + // This wasn't comparable to anything in the sorted list, + // so defer addition of the segment till later. + origList.push_back(segment); + deferredN++; + } } return resultList; @@ -2122,28 +2458,182 @@ static ShiftSegmentList linesort(ShiftSegmentList origList, typedef std::list<ShiftSegment *> ShiftSegmentPtrList; +class PotentialSegmentConstraint +{ + public: + PotentialSegmentConstraint(size_t index1, size_t index2, + const Variables& vs) + : index1(index1), + index2(index2), + vs(vs) + { + } + + bool operator<(const PotentialSegmentConstraint rhs) const + { + return sepDistance() < rhs.sepDistance(); + } + double sepDistance(void) const + { + if (!stillValid()) + { + return 0; + } + return fabs(vs[index1]->finalPosition - vs[index2]->finalPosition); + } + bool stillValid(void) const + { + return (index1 != index2); + } + void rewriteIndex(size_t oldIndex, size_t newIndex) + { + if (index1 == oldIndex) + { + index1 = newIndex; + } + + if (index2 == oldIndex) + { + index2 = newIndex; + } + } + + size_t index1; + size_t index2; + + private: + const Variables& vs; +}; + -static void nudgeOrthogonalRoutes(Router *router, size_t dimension, - PtOrderMap& pointOrders, ShiftSegmentList& segmentList) +class ImproveOrthogonalRoutes { +public: + ImproveOrthogonalRoutes(Router *router); + void execute(void); + +private: + void simplifyOrthogonalRoutes(void); + void buildOrthogonalNudgingOrderInfo(void); + void nudgeOrthogonalRoutes(size_t dimension, + bool justUnifying = false); + + Router *m_router; + PtOrderMap m_point_orders; + UnsignedPairSet m_shared_path_connectors_with_common_endpoints; + ShiftSegmentList m_segment_list; +}; + + +ImproveOrthogonalRoutes::ImproveOrthogonalRoutes(Router *router) + : m_router(router) +{ +} + +void ImproveOrthogonalRoutes::execute(void) +{ + TIMER_START(m_router, tmOrthogNudge); + + m_shared_path_connectors_with_common_endpoints.clear(); + + // Simplify routes. + simplifyOrthogonalRoutes(); + + // Build a cache that denotes whether a certain segment of a connector + // contains a checkpoint. We can't just compare positions, since routes + // can be moved away from their original positions during nudging. + buildConnectorRouteCheckpointCache(m_router); + + // Do Unifying first, by itself. This greedily tries to position free + // segments in overlapping channels at the same position. This way they + // have correct nudging orders determined for them since they will form + // shared paths, rather than segments just positioned as an results of + // the routing process. Of course, don't do this when rerouting with + // a fixedSharedPathPenalty since these routes include extra segments + // we want to keep apart which prevent some shared paths. + if (m_router->routingOption(performUnifyingNudgingPreprocessingStep) && + (m_router->routingParameter(fixedSharedPathPenalty) == 0)) + { + for (size_t dimension = 0; dimension < 2; ++dimension) + { + // Just perform Unifying operation. + bool justUnifying = true; + m_segment_list.clear(); + buildOrthogonalNudgingSegments(m_router, dimension, m_segment_list); + buildOrthogonalChannelInfo(m_router, dimension, m_segment_list); + nudgeOrthogonalRoutes(dimension, justUnifying); + } + } + +#ifndef DEBUG_JUST_UNIFY + // Do the Nudging and centring. + for (size_t dimension = 0; dimension < 2; ++dimension) + { + m_point_orders.clear(); + // Build nudging info. + // XXX Needs to be rebuilt for each dimension, cause of shifting + // points. Maybe we could modify the point orders. + buildOrthogonalNudgingOrderInfo(); + + // Do the centring and nudging. + m_segment_list.clear(); + buildOrthogonalNudgingSegments(m_router, dimension, m_segment_list); + buildOrthogonalChannelInfo(m_router, dimension, m_segment_list); + nudgeOrthogonalRoutes(dimension); + } +#endif // DEBUG_JUST_UNIFY + + // Resimplify all the display routes that may have been split. + simplifyOrthogonalRoutes(); + + m_router->improveOrthogonalTopology(); + + // Clear the segment-checkpoint cache for connectors. + clearConnectorRouteCheckpointCache(m_router); + + TIMER_STOP(m_router); +} + +void ImproveOrthogonalRoutes::nudgeOrthogonalRoutes(size_t dimension, + bool justUnifying) +{ + bool nudgeFinalSegments = m_router->routingOption( + nudgeOrthogonalSegmentsConnectedToShapes); + bool nudgeSharedPathsWithCommonEnd = m_router->routingOption( + nudgeSharedPathsWithCommonEndPoint); + double baseSepDist = m_router->routingParameter(idealNudgingDistance); + COLA_ASSERT(baseSepDist >= 0); + // If we can fit things with the desired separation distance, then + // we try 10 times, reducing each time by a 10th of the original amount. + double reductionSteps = 10.0; + + size_t totalSegmentsToShift = m_segment_list.size(); + size_t numOfSegmentsShifted = 0; // Do the actual nudging. ShiftSegmentList currentRegion; - while (!segmentList.empty()) + while (!m_segment_list.empty()) { + // Progress reporting and continuation check. + numOfSegmentsShifted = totalSegmentsToShift - m_segment_list.size(); + m_router->performContinuationCheck( + (dimension == XDIM) ? TransactionPhaseOrthogonalNudgingX : + TransactionPhaseOrthogonalNudgingY, numOfSegmentsShifted, + totalSegmentsToShift); + // Take a reference segment - ShiftSegment& currentSegment = segmentList.front(); + ShiftSegment *currentSegment = m_segment_list.front(); // Then, find the segments that overlap this one. currentRegion.clear(); currentRegion.push_back(currentSegment); - segmentList.erase(segmentList.begin()); - for (ShiftSegmentList::iterator curr = segmentList.begin(); - curr != segmentList.end(); ) + m_segment_list.erase(m_segment_list.begin()); + for (ShiftSegmentList::iterator curr = m_segment_list.begin(); + curr != m_segment_list.end(); ) { bool overlaps = false; for (ShiftSegmentList::iterator curr2 = currentRegion.begin(); curr2 != currentRegion.end(); ++curr2) { - if (curr->overlapsWith(*curr2, dimension)) + if ((*curr)->overlapsWith(*curr2, dimension)) { overlaps = true; break; @@ -2152,90 +2642,131 @@ static void nudgeOrthogonalRoutes(Router *router, size_t dimension, if (overlaps) { currentRegion.push_back(*curr); - segmentList.erase(curr); - // Consider segments from the beginning, since we mave have + m_segment_list.erase(curr); + // Consider segments from the beginning, since we may have // since passed segments that overlap with the new set. - curr = segmentList.begin(); + curr = m_segment_list.begin(); } else { ++curr; } } - CmpLineOrder lineSortComp(pointOrders, dimension); - currentRegion = linesort(currentRegion, lineSortComp); + + if (! justUnifying) + { + CmpLineOrder lineSortComp(m_point_orders, dimension); + currentRegion = linesort(nudgeFinalSegments, currentRegion, + lineSortComp); + } if (currentRegion.size() == 1) { // Save creating the solver instance if there is just one - // immovable segment. - if (!currentRegion.front().sBend) + // immovable segment, or if we are in the unifying stage. + if (currentRegion.front()->immovable() || justUnifying) { + delete currentRegion.front(); continue; } } // Process these segments. + std::list<size_t> freeIndexes; Variables vs; Constraints cs; + Constraints gapcs; ShiftSegmentPtrList prevVars; - // IDs: - const int freeID = 0; - const int fixedID = 1; - // Weights: - double freeWeight = 0.00001; - double strongWeight = 0.001; - double fixedWeight = 100000; - //printf("-------------------------------------------------------\n"); - //printf("Nudge -- size: %d\n", (int) currentRegion.size()); - for (ShiftSegmentList::iterator currSegment = currentRegion.begin(); - currSegment != currentRegion.end(); ++currSegment) + double sepDist = baseSepDist; +#ifdef NUDGE_DEBUG + fprintf(stderr, "-------------------------------------------------------\n"); + fprintf(stderr, "%s -- size: %d\n", (justUnifying) ? "Unifying" : "Nudging", + (int) currentRegion.size()); +#endif +#ifdef NUDGE_DEBUG_SVG + printf("\n\n"); +#endif + for (ShiftSegmentList::iterator currSegmentIt = currentRegion.begin(); + currSegmentIt != currentRegion.end(); ++currSegmentIt ) { - Point& lowPt = currSegment->lowPoint(); + NudgingShiftSegment *currSegment = static_cast<NudgingShiftSegment *> (*currSegmentIt); // Create a solver variable for the position of this segment. - int varID = freeID; - double idealPos = lowPt[dimension]; - double weight = freeWeight; - if (currSegment->sBend) - { - COLA_ASSERT(currSegment->minSpaceLimit > -CHANNEL_MAX); - COLA_ASSERT(currSegment->maxSpaceLimit < CHANNEL_MAX); + currSegment->createSolverVariable(justUnifying); - // For s-bends, take the middle as ideal. - idealPos = currSegment->minSpaceLimit + - ((currSegment->maxSpaceLimit - - currSegment->minSpaceLimit) / 2); - } - else if (currSegment->fixed) + vs.push_back(currSegment->variable); + size_t index = vs.size() - 1; +#ifdef NUDGE_DEBUG + fprintf(stderr,"line(%d) %.15f dim: %d pos: %.16f\n" + "min: %.16f max: %.16f\n" + "minEndPt: %.16f maxEndPt: %.16f weight: %g cc: %d\n", + currSegment->connRef->id(), + currSegment->lowPoint()[dimension], (int) dimension, + currSegment->variable->desiredPosition, + currSegment->minSpaceLimit, currSegment->maxSpaceLimit, + currSegment->lowPoint()[!dimension], currSegment->highPoint()[!dimension], + currSegment->variable->weight, + (int) currSegment->checkpoints.size()); +#endif +#ifdef NUDGE_DEBUG_SVG + // Debugging info: + double minP = std::max(currSegment->minSpaceLimit, -5000.0); + double maxP = std::min(currSegment->maxSpaceLimit, 5000.0); + fprintf(stdout, "<rect style=\"fill: #f00; opacity: 0.2;\" " + "x=\"%g\" y=\"%g\" width=\"%g\" height=\"%g\" />\n", + currSegment->lowPoint()[XDIM], minP, + currSegment->highPoint()[XDIM] - currSegment->lowPoint()[XDIM], + maxP - minP); + fprintf(stdout, "<line style=\"stroke: #000;\" x1=\"%g\" " + "y1=\"%g\" x2=\"%g\" y2=\"%g\" />\n", + currSegment->lowPoint()[XDIM], currSegment->lowPoint()[YDIM], + currSegment->highPoint()[XDIM], currSegment->highPoint()[YDIM]); +#endif + + if (justUnifying) { - // Fixed segments shouldn't get moved. - weight = fixedWeight; - varID = fixedID; + // Just doing centring, not nudging. + // Record the index of the variable so we can use it as + // a segment to potentially constrain to other segments. + if (currSegment->variable->weight == freeWeight) + { + freeIndexes.push_back(index); + } + // Thus, we don't need to constrain position against other + // segments. + prevVars.push_back(&(*currSegment)); + continue; } - else + + // The constraints generated here must be in order of + // leftBoundary-segment ... segment-segment ... segment-rightBoundary + // since this order is leveraged later for rewriting the + // separations of unsatisfable channel groups. + + // Constrain to channel boundary. + if (!currSegment->fixed) { - // Set a higher weight for c-bends to stop them sometimes - // getting pushed out into channels by more-free connectors - // to the "inner" side of them. - weight = strongWeight; + // If this segment sees a channel boundary to its left, + // then constrain its placement as such. + if (currSegment->minSpaceLimit > -CHANNEL_MAX) + { + vs.push_back(new Variable(channelLeftID, + currSegment->minSpaceLimit, fixedWeight)); + cs.push_back(new Constraint(vs[vs.size() - 1], vs[index], + 0.0)); + } } - currSegment->variable = new Variable(varID, idealPos, weight); - vs.push_back(currSegment->variable); - size_t index = vs.size() - 1; - //printf("line %.15f pos: %g min: %g max: %g\n", - // lowPt[dimension], idealPos, currSegment->minSpaceLimit, - // currSegment->maxSpaceLimit); // Constrain position in relation to previously seen segments, // if necessary (i.e. when they could overlap). for (ShiftSegmentPtrList::iterator prevVarIt = prevVars.begin(); - prevVarIt != prevVars.end(); ) + prevVarIt != prevVars.end(); ++prevVarIt) { - ShiftSegment *prevSeg = *prevVarIt; + NudgingShiftSegment *prevSeg = + static_cast<NudgingShiftSegment *> (*prevVarIt); Variable *prevVar = prevSeg->variable; - if (currSegment->overlapsWith(*prevSeg, dimension) && + if (currSegment->overlapsWith(prevSeg, dimension) && (!(currSegment->fixed) || !(prevSeg->fixed))) { // If there is a previous segment to the left that @@ -2243,104 +2774,485 @@ static void nudgeOrthogonalRoutes(Router *router, size_t dimension, // constrain the two segments to be separated. // Though don't add the constraint if both the // segments are fixed in place. - cs.push_back(new Constraint(prevVar, vs[index], - router->orthogonalNudgeDistance())); - prevVarIt = prevVars.erase(prevVarIt); - } - else - { - ++prevVarIt; + double thisSepDist = sepDist; + bool equality = false; + if (currSegment->shouldAlignWith(prevSeg, dimension)) + { + // Handles the case where the two end segments can + // be brought together to make a single segment. This + // can help in situations where having the small kink + // can restrict other kinds of nudging. + thisSepDist = 0; + equality = true; + } + else if (currSegment->canAlignWith(prevSeg, dimension)) + { + // We need to address the problem of two neighbouring + // segments of the same connector being kept separated + // due only to a kink created in the other dimension. + // Here, we let such segments drift back together. + thisSepDist = 0; + } + else if (!nudgeSharedPathsWithCommonEnd && + (m_shared_path_connectors_with_common_endpoints.count( + UnsignedPair(currSegment->connRef->id(), prevSeg->connRef->id())) > 0)) + { + // We don't want to nudge apart these two segments + // since they are from a shared path with a common + // endpoint. There might be multiple chains of + // segments that don't all have the same endpoints + // so we need to make this an equality to prevent + // some of them possibly getting nudged apart. + thisSepDist = 0; + equality = true; + } + + Constraint *constraint = new Constraint(prevVar, + vs[index], thisSepDist, equality); + cs.push_back(constraint); + if (thisSepDist) + { + // Add to the list of gap constraints so we can + // rewrite the separation distance later. + gapcs.push_back(constraint); + } } } if (!currSegment->fixed) { - // If this segment sees a channel boundary to its left, - // then constrain its placement as such. - if (currSegment->minSpaceLimit > -CHANNEL_MAX) - { - vs.push_back(new Variable(fixedID, - currSegment->minSpaceLimit, fixedWeight)); - cs.push_back(new Constraint(vs[vs.size() - 1], vs[index], - 0.0)); - } - // If this segment sees a channel boundary to its right, // then constrain its placement as such. if (currSegment->maxSpaceLimit < CHANNEL_MAX) { - vs.push_back(new Variable(fixedID, + vs.push_back(new Variable(channelRightID, currSegment->maxSpaceLimit, fixedWeight)); cs.push_back(new Constraint(vs[index], vs[vs.size() - 1], 0.0)); } } + prevVars.push_back(&(*currSegment)); } -#if 0 - for(unsigned i=0;i<vs.size();i++) { - printf("-vs[%d]=%f\n",i,vs[i]->desiredPosition); + + std::list<PotentialSegmentConstraint> potentialConstraints; + if (justUnifying) + { + for (std::list<size_t>::iterator curr = freeIndexes.begin(); + curr != freeIndexes.end(); ++curr) + { + for (std::list<size_t>::iterator curr2 = curr; + curr2 != freeIndexes.end(); ++curr2) + { + if (curr == curr2) + { + continue; + } + potentialConstraints.push_back( + PotentialSegmentConstraint(*curr, *curr2, vs)); + } + } } -#endif - IncSolver f(vs,cs); - f.solve(); - bool satisfied = true; - for (size_t i = 0; i < vs.size(); ++i) +#ifdef NUDGE_DEBUG + for (unsigned i = 0;i < vs.size(); ++i) { - if (vs[i]->id == fixedID) + fprintf(stderr, "-vs[%d]=%f\n", i, vs[i]->desiredPosition); + } +#endif + // Repeatedly try solving this. There are two cases: + // - When Unifying, we greedily place as many free segments as + // possible at the same positions, that way they have more + // accurate nudging orders determined for them in the Nudging + // stage. + // - When Nudging, if we can't fit all the segments with the + // default nudging distance we try smaller separation + // distances till we find a solution that is satisfied. + bool justAddedConstraint = false; + bool satisfied; + + typedef std::pair<size_t, size_t> UnsatisfiedRange; + std::list<UnsatisfiedRange> unsatisfiedRanges; + do + { + IncSolver f(vs, cs); + f.solve(); + + // Determine if the problem was satisfied. + satisfied = true; + for (size_t i = 0; i < vs.size(); ++i) + { + // For each variable... + if (vs[i]->id != freeSegmentID) + { + // If it is a fixed segment (should stay still)... + if (fabs(vs[i]->finalPosition - + vs[i]->desiredPosition) > 0.0001) + { + // and it is not at it's desired position, then + // we consider the problem to be unsatisfied. + satisfied = false; + + // We record ranges of unsatisfied variables based on + // the channel edges. + if (vs[i]->id == channelLeftID) + { + // This is the left-hand-side of a channel. + if (unsatisfiedRanges.empty() || + (unsatisfiedRanges.back().first != + unsatisfiedRanges.back().second)) + { + // There are no existing unsatisfied ranges, + // or there are but they are a valid range + // (we've encountered the right-hand channel + // edges already). + // So, start a new unsatisfied range. + unsatisfiedRanges.push_back( + std::make_pair(i, i + 1)); + } + } + else if (vs[i]->id == channelRightID) + { + // This is the right-hand-side of a channel. + if (unsatisfiedRanges.empty()) + { + // There are no existing unsatisfied ranges, + // so start a new unsatisfied range. + // We are looking at a unsatisfied right side + // where the left side was satisfied, so the + // range begins at the previous variable + // which should be a left channel side. + COLA_ASSERT(i > 0); + COLA_ASSERT(vs[i - 1]->id == channelLeftID); + unsatisfiedRanges.push_back( + std::make_pair(i - 1, i)); + } + else + { + // Expand the existing range to include index. + unsatisfiedRanges.back().second = i; + } + } + else if (vs[i]->id == fixedSegmentID) + { + // Fixed connector segments can also start and + // extend unsatisfied variable ranges. + if (unsatisfiedRanges.empty()) + { + // There are no existing unsatisfied ranges, + // so start a new unsatisfied range. + unsatisfiedRanges.push_back( + std::make_pair(i, i)); + } + else + { + // Expand the existing range to include index. + unsatisfiedRanges.back().second = i; + } + } + } + } + } + +#ifdef NUDGE_DEBUG + if (!satisfied) + { + fprintf(stderr,"unsatisfied\n"); + } +#endif + + if (justUnifying) { - if (fabs(vs[i]->finalPosition - vs[i]->desiredPosition) > 0.01) + // When we're centring, we'd like to greedily place as many + // segments as possible at the same positions, that way they + // have more accurate nudging orders determined for them. + // + // We do this by taking pairs of adjoining free segments and + // attempting to constrain them to have the same position, + // starting from the closest up to the furthest. + + if (justAddedConstraint) { + COLA_ASSERT(potentialConstraints.size() > 0); + if (!satisfied) + { + // We couldn't satisfy the problem with the added + // potential constraint, so we can't position these + // segments together. Roll back. + potentialConstraints.pop_front(); + delete cs.back(); + cs.pop_back(); + } + else + { + // We could position these two segments together. + PotentialSegmentConstraint& pc = + potentialConstraints.front(); + + // Rewrite the indexes of these two variables to + // one, so we need not worry about redundant + // equality constraints. + for (std::list<PotentialSegmentConstraint>::iterator + it = potentialConstraints.begin(); + it != potentialConstraints.end(); ++it) + { + it->rewriteIndex(pc.index1, pc.index2); + } + potentialConstraints.pop_front(); + } + } + potentialConstraints.sort(); + justAddedConstraint = false; + + // Remove now invalid potential segment constraints. + // This could have been caused by the variable rewriting. + while (!potentialConstraints.empty() && + !potentialConstraints.front().stillValid()) + { + potentialConstraints.pop_front(); + } + + if (!potentialConstraints.empty()) + { + // We still have more possibilities to consider. + // Create a constraint for this, add it, and mark as + // unsatisfied, so the problem gets re-solved. + PotentialSegmentConstraint& pc = + potentialConstraints.front(); + COLA_ASSERT(pc.index1 != pc.index2); + cs.push_back(new Constraint(vs[pc.index1], vs[pc.index2], + 0, true)); satisfied = false; - break; + justAddedConstraint = true; + } + } + else + { + if (!satisfied) + { + COLA_ASSERT(unsatisfiedRanges.size() > 0); + // Reduce the separation distance. + sepDist -= (baseSepDist / reductionSteps); +#ifndef NDEBUG + for (std::list<UnsatisfiedRange>::iterator it = + unsatisfiedRanges.begin(); + it != unsatisfiedRanges.end(); ++it) + { + COLA_ASSERT(vs[it->first]->id != freeSegmentID); + COLA_ASSERT(vs[it->second]->id != freeSegmentID); + } +#endif +#ifdef NUDGE_DEBUG + for (std::list<UnsatisfiedRange>::iterator it = + unsatisfiedRanges.begin(); + it != unsatisfiedRanges.end(); ++it) + { + fprintf(stderr, "unsatisfiedVarRange(%ld, %ld)\n", + it->first, it->second); + } + fprintf(stderr, "unsatisfied, trying %g\n", sepDist); +#endif + // And rewrite all the gap constraints to have the new + // reduced separation distance. + bool withinUnsatisfiedGroup = false; + for (Constraints::iterator cIt = cs.begin(); + cIt != cs.end(); ++cIt) + { + UnsatisfiedRange& range = unsatisfiedRanges.front(); + Constraint *constraint = *cIt; + + if (constraint->left == vs[range.first]) + { + // Entered an unsatisfied range of variables. + withinUnsatisfiedGroup = true; + } + + if (withinUnsatisfiedGroup && (constraint->gap > 0)) + { + // Rewrite constraints in unsatisfied ranges + // that have a non-zero gap. + constraint->gap = sepDist; + } + + if (constraint->right == vs[range.second]) + { + // Left an unsatisfied range of variables. + withinUnsatisfiedGroup = false; + unsatisfiedRanges.pop_front(); + if (unsatisfiedRanges.empty()) + { + // And there are no more unsatisfied variables. + break; + } + } + } } } } + while (!satisfied && (sepDist > 0.0001)); + if (satisfied) { +#ifdef NUDGE_DEBUG + fprintf(stderr,"satisfied at nudgeDist = %g\n", sepDist); +#endif for (ShiftSegmentList::iterator currSegment = currentRegion.begin(); currSegment != currentRegion.end(); ++currSegment) { - Point& lowPt = currSegment->lowPoint(); - Point& highPt = currSegment->highPoint(); - double newPos = currSegment->variable->finalPosition; - //printf("Pos: %X, %g\n", (int) currSegment->connRef, newPos); - lowPt[dimension] = newPos; - highPt[dimension] = newPos; + NudgingShiftSegment *segment = + static_cast<NudgingShiftSegment *> (*currSegment); + + segment->updatePositionsFromSolver(justUnifying); } } -#if 0 +#ifdef NUDGE_DEBUG for(unsigned i=0;i<vs.size();i++) { - printf("+vs[%d]=%f\n",i,vs[i]->finalPosition); + fprintf(stderr, "+vs[%d]=%f\n",i,vs[i]->finalPosition); } #endif - for_each(vs.begin(),vs.end(),delete_object()); - for_each(cs.begin(),cs.end(),delete_object()); +#ifdef NUDGE_DEBUG_SVG + for (ShiftSegmentList::iterator currSegment = currentRegion.begin(); + currSegment != currentRegion.end(); ++currSegment) + { + NudgingShiftSegment *segment = + static_cast<NudgingShiftSegment *> (*currSegment); + + fprintf(stdout, "<line style=\"stroke: #00F;\" x1=\"%g\" " + "y1=\"%g\" x2=\"%g\" y2=\"%g\" />\n", + segment->lowPoint()[XDIM], segment->variable->finalPosition, + segment->highPoint()[XDIM], segment->variable->finalPosition); + } +#endif + for_each(currentRegion.begin(), currentRegion.end(), delete_object()); + for_each(vs.begin(), vs.end(), delete_object()); + for_each(cs.begin(), cs.end(), delete_object()); } } -extern void improveOrthogonalRoutes(Router *router) +void ImproveOrthogonalRoutes::simplifyOrthogonalRoutes(void) { - router->timers.Register(tmOrthogNudge, timerStart); - for (size_t dimension = 0; dimension < 2; ++dimension) + // Simplify routes. + for (ConnRefList::const_iterator curr = m_router->connRefs.begin(); + curr != m_router->connRefs.end(); ++curr) { - // Build nudging info. - // XXX: We need to build the point orders separately in each - // dimension since things move. There is probably a more - // efficient way to do this. - PtOrderMap pointOrders; - buildOrthogonalNudgingOrderInfo(router, pointOrders); + if ((*curr)->routingType() != ConnType_Orthogonal) + { + continue; + } + (*curr)->set_route((*curr)->displayRoute().simplify()); + } +} - // Simplify routes. - simplifyOrthogonalRoutes(router); - // Do the centring and nudging. - ShiftSegmentList segLists; - buildOrthogonalChannelInfo(router, dimension, segLists); - nudgeOrthogonalRoutes(router, dimension, pointOrders, segLists); +// Populates m_point_orders and m_shared_path_connectors_with_common_endpoints. +void ImproveOrthogonalRoutes::buildOrthogonalNudgingOrderInfo(void) +{ + // Simplify routes. + simplifyOrthogonalRoutes(); + + int crossingsN = 0; + + bool buildSharedPathInfo = false; + if (!m_router->routingOption(Avoid::nudgeSharedPathsWithCommonEndPoint) && + m_shared_path_connectors_with_common_endpoints.empty()) + { + // We're not going to nudge apart shared paths with common ends so we + // will need to store information about this during the crossing + // detection. + buildSharedPathInfo = true; + } + + + // Make a vector of the ConnRefList, for convenience. + ConnRefVector connRefs(m_router->connRefs.begin(), m_router->connRefs.end()); + + // Make a temporary copy of all the connector displayRoutes. + RouteVector connRoutes(connRefs.size()); + for (size_t ind = 0; ind < connRefs.size(); ++ind) + { + connRoutes[ind] = connRefs[ind]->displayRoute(); } - router->timers.Stop(); + + // Do segment splitting. + for (size_t ind1 = 0; ind1 < connRefs.size(); ++ind1) + { + ConnRef *conn = connRefs[ind1]; + if (conn->routingType() != ConnType_Orthogonal) + { + continue; + } + + for (size_t ind2 = 0; ind2 < connRefs.size(); ++ind2) + { + if (ind1 == ind2) + { + continue; + } + + ConnRef *conn2 = connRefs[ind2]; + if (conn2->routingType() != ConnType_Orthogonal) + { + continue; + } + + Avoid::Polygon& route = connRoutes[ind1]; + Avoid::Polygon& route2 = connRoutes[ind2]; + splitBranchingSegments(route2, true, route); + } + } + + for (size_t ind1 = 0; ind1 < connRefs.size(); ++ind1) + { + ConnRef *conn = connRefs[ind1]; + if (conn->routingType() != ConnType_Orthogonal) + { + continue; + } + + for (size_t ind2 = ind1 + 1; ind2 < connRefs.size(); ++ind2) + { + ConnRef *conn2 = connRefs[ind2]; + if (conn2->routingType() != ConnType_Orthogonal) + { + continue; + } + + Avoid::Polygon& route = connRoutes[ind1]; + Avoid::Polygon& route2 = connRoutes[ind2]; + int crossings = 0; + unsigned int crossingFlags = 0; + ConnectorCrossings cross(route2, true, route, conn2, conn); + cross.pointOrders = &m_point_orders; + for (size_t i = 1; i < route.size(); ++i) + { + const bool finalSegment = ((i + 1) == route.size()); + cross.countForSegment(i, finalSegment); + + crossings += cross.crossingCount; + crossingFlags |= cross.crossingFlags; + } + if (crossings > 0) + { + crossingsN += crossings; + } + + if (buildSharedPathInfo && + (crossingFlags & CROSSING_SHARES_PATH_AT_END)) + { + // Record if these two connectors have a shared path with a + // common end point. + m_shared_path_connectors_with_common_endpoints.insert( + UnsignedPair(conn->id(), conn2->id())); + } + } + } +} + + +extern void improveOrthogonalRoutes(Router *router) +{ + ImproveOrthogonalRoutes improver(router); + improver.execute(); } |