Автоматизация устранения клинчей в топологии печатного монтажа

Автоматизация устранения клинчей в топологии печатного монтажа[1]

С.Ю. Лузин,

д.т.н., luzin@eremex.com,

С.И. Попов,

инж.,

Ю.И. Попов,

инж.,

ООО ЭРЕМЕКС, г. Санкт-Петербург

В статье предложено решение часто встречающейся проблемы клинчей при автоматической разводке печатных плат. Рассмотрен способ представления топологии печатного монтажа. Приведены несколько способов автоматического распознавания клинчей, несколько алгоритмов их устранения. Описаны результаты использования алгоритмов в САПР TopoR.

This article suggests a solution to the problem of clinches that occur during the autorouting of printed circuit boards. Article overviews the ways of presentation of the printed circuit topology, and gives several methods of the clinches automatic recognition, as well as several algorithms for their elimination. The results of using the mentioned algorithms in CAD TopoR are described.

Введение

Одним из вариантов представления топологического пространства печатного монтажа является квазитриангуляция [1]. В квазитриангуляции (рис. 1) квазивершины представлены отрезками, а квазирёбра четырёхугольниками. Грани же квазитриангуляции представлены, как и в обычной триангуляции, – треугольниками. При этом в вырожденном случае отрезок квазивершины может быть точкой, а четырёхугольник квазиребра «сузиться» до отрезка. В таком, частном, случае квазитриангуляция является триангуляцией в обычном смысле. Благодаря «двумерности» рёбер не сложно соблюсти условие Делоне [2] для граней, не добавляя в триангуляцию новых вершин. Просто, при необходимости, увеличивается или уменьшается размер квазирёбер и квазивершин.

Квазитриангуляция описывается списком дуг (arc). Для каждой дуги следующей в списке (массив ArcNext) идёт дуга против часовой стрелки.

В пространстве печатной платы круглые контакты и переходы представлены точечными примитивами (bar) с необходимым радиусом запрета (для того, чтобы учитывать размер контакта). Контакты более сложной формы, например, прямоугольные, представлены набором примитивов. На рис. 2 левый контакт (Obj1) образован девятью примитивами (b1 – b9), правый, круглый, контакт – одним примитивом b10. Каждому ребру (edge) квазитриангуляции соответствуют две направленные дуги (arc). Противоположную дуге arc дугу можно получить через массив ArcOver.

рис. 1. Квазитриангуляция. Квазирёбра: a – выпуклое четырёхугольное, b – невыпуклое четырёхугольное, c – треугольное, d – вырожденное, a и e – параллельные, f – квазиребро содержит часть отрезка

рис. 2. Представление объектов. Левый, прямоугольный, объект (Obj1) состоит из девяти примитивов (b1 – в центре, b2, b4, b6, b8 –по сторонам, b3, b5, b7, b9 – по углам); правый, круглый, объект – из одного примитива (b10); e – ребро, a1 и a2 – дуги, соответствующие ребру e

Каждый проводник (span) логически представлен двумя противоположно идущими по плате проводниками (wire и через массив WireOver). Проводник (span) состоит из последовательности крестов – пересечений проводника с квазирёбрами. Каждый крест имеет четыре хвоста (tail) – два сонаправленные каждой из дуг пересекаемого ребра и два для каждого из противоположных направлений проводника (wire и WireOver(wire)). У проводника есть два начала: одно для wire, второе для проводника, противоположного wire. Проводник, если он короткий, может не иметь крестов (пересечений с рёбрами). При этом, если его направление совпадает с ребром, а начала являются двумя вершинами (примитивами), инцидентными ребру, то проводник «прокладывается» вдоль ребра (рис. 3). По хвостам проводника wire можно передвигаться. Для этого необходимо получить первый хвост проводника (массив TailWire), затем по имеющемуся хвосту можно получить следующий с помощью массива TailWNext. Если TailWNext(tail) меньше нуля, то достигнут конец проводника.

Неприятной особенностью методов локальной оптимизации топологии печатного монтажа является «застревание» в локальных минимумах, когда качество разводки ещё далеко от совершенства, но в то же время никакой шаг локальной оптимизации не может привести к его улучшению. Например, на рис. 4 слева показан типичный «клинч» двух проводников. Перекладка ни одного из двух проводников не может перевести топологию в ситуацию, показанную на том же рисунке справа.

рис. 3. Представление проводников. Проводник w1 идёт от ветвления b1, проводник w3 идёт от ветвления вниз, проводник w2 – проложен вдоль ребра от ветвления между примитивами b1 и b2; t1, t3 – хвосты проводников w1 и WireOver(w1) при пересечении ребра, t2, t4 – хвосты дуг ребра при пересечении проводником ребра

рис. 4. Клинч слева и желаемая топология справа

В нижеприведённых алгоритмах будет использоваться понятие «длинного» пути – это путь в клинче, который необходимо сократить за счёт перекладки «мешающих» проводников.

1. Устранение полупетель

В процессе перекладки проводников при устранении клинчей возникает ситуация, при которой топологически проводнику ничего не мешает идти более коротким путём без лишних поворотов.

Далее под удалением полупетли будет пониматься ситуация, изображённая на рис. 5, а под удалением петли в начале проводника ситуация, изображённая на рис. 6.

рис. 5. Полупетля слева и желаемая топология справа. a1 – дуга, на которой обнаружена полупетля, a2 – первая дуга, которую проводник пересекает не дважды, a3 – дуга, вдоль ребра которой будет проложен проводник, w1 – проводник, b1, b2 – примитивы концов проводника

рис. 6. Полупетля в начале проводника слева и желаемая топология справа. b1 – примитив начала проводника, w1 – проводник

2. Устранение клинчей с распознаванием при помощи пересечения ребра проводником

Если проводник w1 пересекает дугу a1, инцидентную тому же объекту Obj1, с которого начинается проводник, то его путь, вероятно, можно сократить, оттянув мешающие этому проводники за Obj1 (рис. 8).

2.2. Определение, состоит ли длинный путь в клинче из нескольких проводников

Алгоритм IsClinchWithWireSequence. Входные данные: wire – проводник, пересекающий дугу, bar – примитив, из которого начинается пересекаемая проводником дуга.

В нормальной ситуации в топологии нет циклов, поэтому для поиска длинного пути в клинче можно использовать поиск в ширину в графе [3]. Проводники в таком случае являются дугами, точки ветвления – промежуточными узлами дерева поиска в ширину, другие объекты – листьями. При этом в дерево необходимо добавлять только те дуги, веса которых (ширина соответствующих проводников), не меньше ширины wire.

Выходные данные: проводник, начинающийся на том же объекте, что и пересекаемая дуга. Он отделён от wire проводниками и ветвлениями.

2.3. Оттягивание проводников за объект

Алгоритм ProcessInnerWiresMoving. Входные данные: arc – дуга, на которой обнаружен клинч, wire – длинный проводник, wireCount – число мешающих проводников. A. Для каждого из wireCount первых проводников wire на дуге.

1. Если хвост был ранее запомнен и ещё не обработан (см. шаг 4.1.):

1.1. Выполнить шаги, начиная с 2., для ещё не обработанного запомненного проводника.

2. Удалить проводник с инцидентных объекту Obj (из которого выходит дуга arc) рёбер. При этом запомнить дугу firstArcDelFrom, инцидентную Obj, которую проводник пересекал первой, запомнить хвосты tailPrev и tailNext, между которыми был удалён проводник с инцидентных объекту Obj рёбер.

3. Если перекладывается первый проводник:

3.1. Если есть хвост проводника wire до пересечения им дуг объекта Obj, то по его дуге и дуге firstArcDelFrom определить по часовой или против часовой (clockWise) проводники будут огибать Obj (обе дуги – стороны одной грани в триангуляции).

3.2. Иначе (хвост < 0 => перед пересечением дуг Obj проводник wire только начинается): по примитиву и firstArcDelFrom определить по часовой или против часовой (clockWise) проводники будут огибать Obj (начальный примитив проводника wire и дуга firstArcDelFrom – вершина и сторона одной грани).

4. Если два хвоста tailPrev и tailNext находятся на одном ребре и при этом соседние, то, значит, есть полупетля.

4.1. Если одним из концов проводника является примитив b2, из которого выходит ArcOver(arc), то удалить полупетлю с запретом на прокладку вдоль ребра:

4.1.1. Если wire ещё раз пересекает arc, запомнить хвост на дуге, идущий после хвоста его креста на дуге. Запомнить хвост проводника перед b2 после удаления полупетли. Запомнить wire для дальнейшей перекладки.

4.1.2. Если wire после удаления полупетли почти проложен вдоль ребра, запомнить это.

4.2. Иначе удалить полупетлю.

4.3. Перейти к шагу A. (следующему проводнику).

5. Иначе необходимо обогнуть проводником wire объект Obj.

5.1. Если хвост tail перед обрабатываемой вершиной или после неё меньше нуля и его ребро инцидентно началу или концу проводника, то

5.1.1. Удалить полупетлю в начале проводника.

5.1.2. Перейти к шагу A (следующему проводнику).

5.2. Иначе

5.2.1. Если хвост проводника перед огибаемой вершиной меньше нуля, то пропустить общие рёбра примитива-начала проводника и огибаемого объекта (если они есть).

5.2.2. Проложить проводник по рёбрам (ближайшим к Obj) по clockWise вокруг Obj, пока не будет ребра, с которого проводник был до этого удалён или общего ребра у объекта и конца проводника (если TailWNext < 0).

5.2.3. Если необходимо (tailPrev < 0, tailNext < 0, и проводник не был добавлен ни на одно ребро), проложить проводник вдоль ребра.

Выходные данные: переложенные проводники. По часовой или против перекладывались проводники (clockWise).

2.4. Основной алгоритм устранения клинчей с распознаванием с помощью пересечения ребра проводником

Алгоритм Clinches_1. Входные данные: триангуляция, возможно, с клинчами данного типа.

A. Идти по всем рёбрам триангуляции. B. Для обеих дуг каждого ребра.

1. Если ребро внутри объекта или его не пересекают проводники, идти к шагу A. (следующему ребру).

2. Если объекту Obj, от которого отходит дуга, инцидентно более одного проводника, перейти к шагу B. (следующей дуге).

3. Идти по хвостам пересекающих дугу проводников (проверять wire и WireOver(wire)).

3.1. Если проводник пересекает дугу больше двух раз, то перейти к шагу A. (следующему ребру).

3.2. Для обоих проводников (wire и WireOver):

3.2.1. Если проводник начинается с того же объекта, то и рассматриваемая дуга и примитив, из которого начинается дуга имеет цепь меньше нуля (он – барьер), то запомнить, что такой проводник был.

3.2.2. Если длинный путь в клинче состоит из одного проводника (рис. 7).

3.2.2.1. Если на ребре всего один проводник, перейти к шагу A. (следующему ребру).

3.2.2.2. Запомнить, что длинный путь состоит из одного проводника.

3.2.3. Иначе определить, состоит ли длинный путь из нескольких проводников, выполнив IsClinchWithWireSequence (рис. 8).

рис. 7. Клинч, длинный путь в котором состоит из одного проводника. a1 – дуга, на которой обнаружен клинч, b1 – примитив, от которого отходит дуга a1, w1 – «длинный» проводник в клинче, w2 – «мешающий» проводник в клинче

рис. 8. Клинч, длинный путь в котором состоит из нескольких проводников. a1 – дуга, на которой обнаружен клинч, b1 – примитив, от которого отходит дуга a1, w1, w3, w5 – проводники, составляющие «длинный» путь в клинче, w6 – «мешающий» проводник в клинче. w2, w4 – проводники, b2 – примитив добавленного ветвления

3.2.3.1. Если длинный путь найден, то проверить, не пересекает ли первый проводник firstWire (w5 на рис. 9), отходящий от Obj, в длинном пути рассматриваемую дугу. Если это так, то перейти к следующему проводнику, так как этот клинч будет устранён позже, когда будет рассматриваться найденный проводник.

3.2.3.2. Запомнить, что длинный путь состоит из нескольких проводников.

3.2.4. Если клинч найден:

3.2.4.1. Проверить, поместятся ли мешающие проводники на тех рёбрах, которые они ещё не пересекают:

3.2.4.1.1. Запомнить мешающие проводники wires (кроме wire).

3.2.4.1.2. Для каждой дуги arc в новом пути для wires с другой стороны от объекта (обойти объект по периметру), на дуге из которого обнаружен клинч, проверить, помещаются ли на неё мешающие проводники.

3.2.4.1.3. Если не помещаются, перейти к шагу A. (следующему ребру).

3.2.4.2. Если длинный путь в клинче состоит из одного проводника longWire:

3.2.4.2.1. Идти по хвостам в обе стороны от рассматриваемой дуги и, начиная с неё, удалить кресты с рёбер, инцидентных объекту.

3.2.4.2.2. Удалить остаток проводника до Obj.

3.2.4.3. Если длинный путь в клинче состоит из нескольких проводников:

3.2.4.3.1. Удалить firstWire.

3.2.4.4. Оттянуть все пройденные до wire проводники за объект, из которого начинается рассматриваемая дуга. Если проводник wire не первый на ребре и ранее он его уже пересекал (шаг 3.2.1.), то уменьшить число пройденных проводников wireCount на один. ProcessInnerWiresMoving(arc, firstClWire, wireCount).

3.2.4.5. Если длинный путь состоит из одного проводника:

3.2.4.5.1. Если его хвост перед Obj >= 0 (то есть перед Obj есть крест проводника):

3.2.4.5.1.1. Если противоположный хвосту примитив – не барьер объекта, то соединить проводник с примитивом.

3.2.4.5.1.2. Иначе, проложить проводник по !clockWise до ближайшего подходящего примитива (всегда есть хотя бы тот, к которому проводник был присоединён до этого) (AddToNewEdges).

3.2.4.5.2. Иначе проложить проводник вдоль ребра.

3.2.4.6. Иначе (длинный путь состоит из нескольких проводников).

Выходные данные: триангуляция с устранёнными, где возможно, клинчами данного типа.

3. Устранение неявных клинчей

Пусть проводник w1 огибает объект arObj, пройти с другой стороны от объекта ему мешает проводник w2, и проводник w2 пересекает дугу, инцидентную тому же объекту clObj, с которого начинается w1. Тогда, вероятно, можно проложить w2 с другой стороны от clObj, а w1 проложить с другой стороны от arObj (рис. 10).

3.1. Вспомогательный алгоритм определения есть ли огибание объекта

Алгоритм IsRoundObject. Входные данные: wire – обрабатываемый проводник, tail – хвост проводника, prevD1 – координата предыдущего хвоста или начала проводника (если предыдущего хвоста нет).

1. Запомнить: arcBegin – дуга по часовой стрелке от хвоста, arcBegin2 – дуга против часовой стрелки от хвоста, Obj1 – объект, из которого выходит arcBegin1, Obj2 – объект, из которого выходит arcBegin2.

2. Идти по хвостам проводника пока не закончатся дуги, инцидентные Obj1 или Obj2.

3. Если дуге текущего хвоста не инцидентен ни один из объектов, то огибания нет, вернуть false.

4. Пусть Obj – объект, мимо которого проводник идёт дольше, чем мимо второго объекта-претендента. arcBegin – первая дуга Obj, через которую проходит wire, arcEnd – последняя дуга Obj, через которую проходит wire. prevD2 – координата начала arcBegin. curD1 – координата хвоста проводника wire после Obj или конца wire, если он после Obj заканчивается.

5. Если векторы (prevD1 - prevD2) и (curD1 - curD2) расходятся, и синус угла между ними меньше нуля, то:

5.1. Есть огибание проводником wire объекта Obj. Вернуть true.

6. Иначе вернуть false.

Выходные данные: огибаемый объект, дуга объекта, с которой начинается огибание, дуга объекта, на которой заканчивается огибание; по часовой или против необходимо переложить проводник (clockWise).

3.2. Вспомогательный алгоритм перекладки проводников при устранении неявного клинча

Алгоритм RelineWire. Входные данные: arWire – огибающий проводник, clWire – мешающий проводник, tBeg – первый хвост мешающего проводника на дуге, не инцидентной огибаемому объекту, tEnd – хвост после огибания объекта огибающим проводником или -1, arcBeg – первая дуга, на которую будет переложен мешающий проводник, arcEnd – дуга, до которой будет переложен мешающий проводник, tEnd2 – хвост, до которого необходимо удалить мешающий проводник, tBeg2 – хвост, с которого начинается мешающий проводник, clockWise – по часовой или против необходимо проложить мешающий проводник.

1. Удалить проводник clWire от tBeg2 до tBeg (не включая последнего).

2. Проложить clWire с другой стороны от arObj (от arcBeg до arcEnd), соединить с tEnd или концом проводника, если tEnd < 0.

3. Проложить arWire по пути clWire от arcBeg до первой дуги, инцидентной arObj, примитива-начало которой имеет ту же цепь, что и проводник.

4. Если такой нет, то обязательно есть дуга с другой цепью. Тогда, начиная с неё, проложить проводник по clockWise по инцидентным объекту дугам до дуги с нужной цепью.

5. Удалить ставшую ненужной часть clWire, которая огибала clObj от первой дуги, инцидентной clObj до tEnd2.

6. Удалить, возможно, появившиеся полупетли в начале и в конце arWire.

7. Если необходимо, проложить arWire вдоль ребра.

8. Если tEnd >= 0 и он находится на одной дуге с предыдущим хвостом – удалить образовавшуюся полупетлю.

Выходные данные: проложенный по нужному пути arWire.

3.3. Алгоритм устранения неявного клинча без точки ветвления

Алгоритм UntangleAroundClinch (рис. 9). Входные данные: arcBegin (a1 на рис.) – дуга, с которой начинается огибание объекта проводником, arcEnd (a2 на рис.) – дуга, на которой заканчивается огибание объекта проводником, arWire (w1 на рис.) – проводник, на котором обнаружено огибание, clockWise – по часовой или против будет переложен arWire.

рис. 9. Неявный клинч без точки ветвления.arObj – огибаемый объект, clObj – объект начала огибающего проводника, a1 – дуга, с которой начинается огибание, a2 – дуга, на которой заканчивается огибание, w1 – огибающий проводник, w2 – мешающий проводник, a3 – дуга, с которой мешающий проводник будет проходить с другой стороны от clObj, a4 – дуга, до которой мешающий проводник будет проходить с другой стороны от clObj, a5 – дуга, начиная с которой огибающий проводник будет проходить с другой стороны от arObj, a6 – дуга, после которой мог бы закончится clWire, если бы примитив, из которого выходит a1 был бы не барьером

1. Если мешающий проводник clWire проходит через инцидентное ребро clObj, объекта-начала arWire, то клинч обнаружен.

2. Иначе, если мешающий проводник clWire проходит через инцидентное ребро clObj, объекта-начала WireOver(arWire), то клинч обнаружен. Поменять arcBegin c arcEnd местами, в качестве arWire рассматривать WireOver(arWire). Поменять значение clockWise на противоположное.

3. Пусть: arcFirst1 (a5 на рис.) – первая дуга, инцидентная огибаемому объекту arObj, через которую будет проходить arWire после устранения клинча, arcFirst2 (a3 на рис.) – первая дуга clObj, через которую будет проходить clWire после устранения клинча, возможно, огибая clObj, arcEnd1 (a2 на рис.) – дуга arObj, на которой заканчивается его огибание arWire и до которой проводник будет идти с другой стороны от arObj, arcEnd2 (a4 на рис.) – дуга clObj, на которой заканчивается прохождение мимо него или его огибание проводником clWire и до которой проводник будет идти с другой стороны от clObj, tArEnd1 – хвост arWire после arObj, или -1, если проводник кончается, tArEnd2 – хвост clWire после clObj, или -1, если проводник заканчивается.

4. Для каждой дуги arObj от arcFirst1 до arcEnd1, для каждой дуги clWire от первой не инцидентной arObj до первой инцидентной clObj (с примитивом начала с нужной цепью): проверить, поместиться ли на них arWire. Если нет, вернуть false.

5. Для каждой дуги clObj от arcFirst2 до arcEnd2, для каждой дуги arWire от первой не инцидентной clObj до первой инцидентной arObj (с примитивом начала с нужной цепью): проверить, поместиться ли на них arWire. Если нет, вернуть false.

6. Проверить, что при перекладке clWire с другой стороны от clObj не получится огибание большей длины и с большим углом. Огибание определяется так же как и в IsAroundObject (по координате хвоста arWire перед arcFirst2 (prevD1), по координате начала arcFirst2 (prevD2), по координате хвоста clWire после clObj (или конца clWire, если он заканчивается) (curD1) и по координате начала arcEnd2).

7. Если у переложенных проводников куски от первого хвоста clWire на дуге, не ицидентной arObj, до первого хвоста clWire на дуге, не инцидентной clObj будут пересекаться, то не устранять клинч, вернуть false.

8. Для clWire и arWire сложилась симметричная ситуация, поэтому выполнить RelineWire для каждого из них, меняя их роли местами. Вернуть true.

Выходные данные: устранённый, если возможно, неявный клинч.

4. Применение в САПР TopoR

Вышеприведённые алгоритмы были применены в САПР TopoR 5.2 и показали свою эффективность.

Выводы

Устранение клинчей приводит к увеличению свободного места для перекладки проводников, улучшению топологии, сокращению длины проводников.

Литература

1. Лузин С. Ю., Лячек Ю. Т., Петросян Г. С., Полубасов О. Б. Модели и алгоритмы автоматизированного проектирования радиоэлектронной и электронно-вычислительной аппаратуры. – СПб.: БХВ-Петербург, 2010. –224 с.

2. Скворцов А. В. Триангуляция Делоне и ее применение. – Томск: Изд-во Томского ун-та, 2002. –128 с.

3. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ — 2-е изд. — М.: Вильямс, 2006. –1296 с.

[1] Работа выполняется в рамках конкурса грантов для студентов, аспирантов вузов и академических институтов, расположенных на территории Санкт-Петербурга.