From cca66b9ec4e494c1d919bff0f71a820d8afab1fa Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 20:24:48 +0200 Subject: Adding upstream version 1.2.2. Signed-off-by: Daniel Baumann --- src/3rdparty/adaptagrams/libavoid/scanline.cpp | 562 +++++++++++++++++++++++++ 1 file changed, 562 insertions(+) create mode 100644 src/3rdparty/adaptagrams/libavoid/scanline.cpp (limited to 'src/3rdparty/adaptagrams/libavoid/scanline.cpp') 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 +#include + +#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 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 >(); + + 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 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 (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; +} + + +} + -- cgit v1.2.3