summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/adaptagrams/libavoid/scanline.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/3rdparty/adaptagrams/libavoid/scanline.cpp')
-rw-r--r--src/3rdparty/adaptagrams/libavoid/scanline.cpp562
1 files changed, 562 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libavoid/scanline.cpp b/src/3rdparty/adaptagrams/libavoid/scanline.cpp
new file mode 100644
index 0000000..9351c36
--- /dev/null
+++ b/src/3rdparty/adaptagrams/libavoid/scanline.cpp
@@ -0,0 +1,562 @@
+/*
+ * vim: ts=4 sw=4 et tw=0 wm=0
+ *
+ * libavoid - Fast, Incremental, Object-avoiding Line Router
+ *
+ * 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
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ * 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
+ * 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.
+ *
+ * Author(s): Michael Wybrow
+*/
+
+#include <cfloat>
+#include <algorithm>
+
+#include "libavoid/scanline.h"
+#include "libavoid/obstacle.h"
+#include "libavoid/vertices.h"
+#include "libavoid/connector.h"
+#include "libavoid/junction.h"
+#include "libavoid/router.h"
+
+namespace Avoid {
+
+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;
+}
+
+
+Node::Node(Obstacle *v, const double p)
+ : v(v),
+ c(nullptr),
+ ss(nullptr),
+ pos(p),
+ firstAbove(nullptr),
+ firstBelow(nullptr)
+{
+ Box bBox = v->routingBox();
+ min[XDIM] = bBox.min.x;
+ min[YDIM] = bBox.min.y;
+ max[XDIM] = bBox.max.x;
+ max[YDIM] = bBox.max.y;
+ //COLA_ASSERT(r->width()<1e40);
+}
+
+Node::Node(VertInf *c, const double p)
+ : v(nullptr),
+ c(c),
+ ss(nullptr),
+ pos(p),
+ firstAbove(nullptr),
+ firstBelow(nullptr)
+{
+ min[XDIM] = max[XDIM] = c->point.x;
+ min[YDIM] = max[YDIM] = c->point.y;
+}
+
+Node::Node(ShiftSegment *ss, const double p)
+ : v(nullptr),
+ c(nullptr),
+ ss(ss),
+ pos(p),
+ firstAbove(nullptr),
+ firstBelow(nullptr)
+{
+ // These values shouldn't ever be used, so they don't matter.
+ min[XDIM] = max[XDIM] = min[YDIM] = max[YDIM] = 0;
+}
+
+Node::~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 Node::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 Node::firstObstacleBelow(size_t dim)
+{
+ Node *curr = firstBelow;
+ while (curr && (curr->ss || (curr->min[dim] < pos)))
+ {
+ curr = curr->firstBelow;
+ }
+
+ 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 Node::markShiftSegmentsAbove(size_t dim)
+{
+ Node *curr = firstAbove;
+ while (curr && (curr->ss || (curr->pos > min[dim])))
+ {
+ if (curr->ss && (curr->pos <= min[dim]))
+ {
+ curr->ss->maxSpaceLimit =
+ std::min(min[dim], curr->ss->maxSpaceLimit);
+ }
+ curr = curr->firstAbove;
+ }
+}
+
+// Mark all connector segments below in the scanline as being able
+// to see to this shape edge.
+void Node::markShiftSegmentsBelow(size_t dim)
+{
+ Node *curr = firstBelow;
+ while (curr && (curr->ss || (curr->pos < max[dim])))
+ {
+ if (curr->ss && (curr->pos >= max[dim]))
+ {
+ curr->ss->minSpaceLimit =
+ std::max(max[dim], curr->ss->minSpaceLimit);
+ }
+ curr = curr->firstBelow;
+ }
+}
+
+void Node::findFirstPointAboveAndBelow(const size_t dim, const double linePos,
+ double& firstAbovePos, double& firstBelowPos,
+ double& lastAbovePos, double& lastBelowPos)
+{
+ 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];
+
+ Node *curr = nullptr;
+ bool eventsAtSamePos = false;
+ for (int direction = 0; direction < 2; ++direction)
+ {
+ // Look for obstacles in one direction, then the other.
+ curr = (direction == 0) ? firstAbove: firstBelow;
+
+ while (curr)
+ {
+ // The events are at a shared beginning or end of a shape or
+ // connection point. Note, connection points have the same
+ // min and max value in the !dim dimension.
+ eventsAtSamePos =
+ (((linePos == max[!dim]) &&
+ (linePos == curr->max[!dim])) ||
+ ((linePos == min[!dim]) &&
+ (linePos == curr->min[!dim])));
+
+ if (curr->max[dim] <= min[dim])
+ {
+ // Curr shape is completely to the left,
+ // so add it's right side as a limit
+ firstAbovePos = std::max(curr->max[dim], firstAbovePos);
+ }
+ else if (curr->min[dim] >= max[dim])
+ {
+ // Curr shape is completely to the right,
+ // so add it's left side as a limit
+ firstBelowPos = std::min(curr->min[dim], firstBelowPos);
+ }
+ else if (!eventsAtSamePos)
+ {
+ // Shapes that open or close at the same position do not
+ // block visibility, so if they are not at same position
+ // determine where they overlap.
+ lastAbovePos = std::min(curr->min[dim], lastAbovePos);
+ lastBelowPos = std::max(curr->max[dim], lastBelowPos);
+ }
+ curr = (direction == 0) ? curr->firstAbove : curr->firstBelow;
+ }
+ }
+}
+
+double Node::firstPointAbove(size_t dim)
+{
+ // We are looking for the first obstacle above this position,
+ // though we ignore shape edges if this point is inline with
+ // the edge of the obstacle. That is, points have visibility
+ // along the edge of shapes.
+ size_t altDim = (dim + 1) % 2;
+ double result = -DBL_MAX;
+ Node *curr = firstAbove;
+ while (curr)
+ {
+ bool inLineWithEdge = (min[altDim] == curr->min[altDim]) ||
+ (min[altDim] == curr->max[altDim]);
+ if ( ! inLineWithEdge && (curr->max[dim] <= pos) )
+ {
+ result = std::max(curr->max[dim], result);
+ }
+ curr = curr->firstAbove;
+ }
+ return result;
+}
+
+double Node::firstPointBelow(size_t dim)
+{
+ // We are looking for the first obstacle below this position,
+ // though we ignore shape edges if this point is inline with
+ // the edge of the obstacle. That is, points have visibility
+ // along the edge of shapes.
+ size_t altDim = (dim + 1) % 2;
+ double result = DBL_MAX;
+ Node *curr = firstBelow;
+ while (curr)
+ {
+ bool inLineWithEdge = (min[altDim] == curr->min[altDim]) ||
+ (min[altDim] == curr->max[altDim]);
+ if ( ! inLineWithEdge && (curr->min[dim] >= pos) )
+ {
+ result = std::min(curr->min[dim], result);
+ }
+ curr = curr->firstBelow;
+ }
+ return result;
+}
+
+// This is a bit inefficient, but we won't need to do it once we have
+// connection points.
+bool Node::isInsideShape(size_t dimension)
+{
+ for (Node *curr = firstBelow; curr; curr = curr->firstBelow)
+ {
+ if ((curr->min[dimension] < pos) && (pos < curr->max[dimension]))
+ {
+ return true;
+ }
+ }
+ for (Node *curr = firstAbove; curr; curr = curr->firstAbove)
+ {
+ if ((curr->min[dimension] < pos) && (pos < curr->max[dimension]))
+ {
+ return true;
+ }
+ }
+ return false;
+}
+
+
+Event::Event(EventType t, Node *v, double p)
+ : type(t),
+ v(v),
+ pos(p)
+{
+}
+
+
+// Used for quicksort. Must return <0, 0, or >0.
+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 (int)(ea->v - eb->v);
+}
+
+
+void buildConnectorRouteCheckpointCache(Router *router)
+{
+ for (ConnRefList::const_iterator curr = router->connRefs.begin();
+ curr != router->connRefs.end(); ++curr)
+ {
+ ConnRef *conn = *curr;
+ if (conn->routingType() != ConnType_Orthogonal)
+ {
+ continue;
+ }
+
+ PolyLine& displayRoute = conn->displayRoute();
+ std::vector<Checkpoint> checkpoints = conn->routingCheckpoints();
+
+ // Initialise checkpoint vector and set to false. There will be
+ // one entry for each *segment* in the path, and the value indicates
+ // whether the segment is affected by a checkpoint.
+ displayRoute.checkpointsOnRoute =
+ std::vector<std::pair<size_t, Point> >();
+
+ for (size_t ind = 0; ind < displayRoute.size(); ++ind)
+ {
+ if (ind > 0)
+ {
+ for (size_t cpi = 0; cpi < checkpoints.size(); ++cpi)
+ {
+ if (pointOnLine(displayRoute.ps[ind - 1],
+ displayRoute.ps[ind], checkpoints[cpi].point) )
+ {
+ // The checkpoint is on a segment.
+ displayRoute.checkpointsOnRoute.push_back(
+ std::make_pair((ind * 2) - 1,
+ checkpoints[cpi].point));
+ }
+ }
+ }
+
+ for (size_t cpi = 0; cpi < checkpoints.size(); ++cpi)
+ {
+ if (displayRoute.ps[ind].equals(checkpoints[cpi].point))
+ {
+ // The checkpoint is at a bendpoint.
+ displayRoute.checkpointsOnRoute.push_back(
+ std::make_pair(ind * 2, checkpoints[cpi].point));
+ }
+ }
+ }
+ }
+}
+
+
+void clearConnectorRouteCheckpointCache(Router *router)
+{
+ for (ConnRefList::const_iterator curr = router->connRefs.begin();
+ curr != router->connRefs.end(); ++curr)
+ {
+ ConnRef *conn = *curr;
+ if (conn->routingType() != ConnType_Orthogonal)
+ {
+ continue;
+ }
+
+ // Clear the cache.
+ PolyLine& displayRoute = conn->displayRoute();
+ displayRoute.checkpointsOnRoute.clear();
+ }
+}
+
+
+// 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(NodeSet& scanline, Event *e, size_t dim,
+ unsigned int pass)
+{
+ Node *v = e->v;
+
+ if ( ((pass == 3) && (e->type == Open)) ||
+ ((pass == 3) && (e->type == SegOpen)) )
+ {
+ 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);
+ }
+ }
+
+ if ( ((pass == 2) && (e->type == SegClose)) ||
+ ((pass == 2) && (e->type == Close)) )
+ {
+ // Clean up neighbour pointers.
+ Node *l = v->firstAbove, *r = v->firstBelow;
+ if (l != nullptr)
+ {
+ l->firstBelow = v->firstBelow;
+ }
+ if (r != nullptr)
+ {
+ r->firstAbove = v->firstAbove;
+ }
+
+ size_t result;
+ result = scanline.erase(v);
+ COLA_ASSERT(result == 1);
+ COLA_UNUSED(result); // Avoid warning.
+ delete v;
+ }
+}
+
+void buildOrthogonalChannelInfo(Router *router,
+ const size_t dim, ShiftSegmentList& segmentList)
+{
+ if (segmentList.empty())
+ {
+ // There are no segments, so we can just return now.
+ return;
+ }
+
+ // Do a sweep to determine space for shifting segments.
+ size_t altDim = (dim + 1) % 2;
+ const size_t n = router->m_obstacles.size();
+ const size_t cpn = segmentList.size();
+ // Set up the events for the sweep.
+ size_t totalEvents = 2 * (n + cpn);
+ Event **events = new Event*[totalEvents];
+ unsigned ctr = 0;
+ 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;
+ totalEvents -= 2;
+ continue;
+ }
+ Box bBox = obstacle->routingBox();
+ Point min = bBox.min;
+ Point max = bBox.max;
+ double mid = min[dim] + ((max[dim] - min[dim]) / 2);
+ Node *v = new Node(obstacle, mid);
+ events[ctr++] = new Event(Open, v, min[altDim]);
+ events[ctr++] = new Event(Close, v, max[altDim]);
+
+ ++obstacleIt;
+ }
+ 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);
+
+ // 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)
+ {
+ processShiftEvent(scanline, events[j], dim, pass);
+ }
+ }
+
+ if (i == totalEvents)
+ {
+ // We have cleaned up, so we can now break out of loop.
+ break;
+ }
+
+ thisPos = events[i]->pos;
+ posStartIndex = i;
+ }
+
+ // Do the first sweep event handling -- building the correct
+ // structure of the scanline.
+ const int pass = 1;
+ processShiftEvent(scanline, events[i], dim, pass);
+ }
+ COLA_ASSERT(scanline.size() == 0);
+ for (unsigned i = 0; i < totalEvents; ++i)
+ {
+ delete events[i];
+ }
+ delete [] events;
+}
+
+
+}
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-15 13:56:22 +0000