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

Г.С. Петросян,

О.Б. Полубасов,

Ю.И. Попов,
С.И. Попов, luzin@eremex.com,

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

Топологическая трассировка в САПР TopoR выполняется в два этапа. На первом этапе производится поиск топологических путей проводников, на втором этапе – вычисление по ним геометрической формы проводников. Топологический путь не дает информации о реальных расстояниях между проводником и остальными элементами печатного монтажа (другими проводниками, контактными площадками, переходными отверстиями). Предложенный алгоритм, исходя из топологического пути проводника, вычисляет его геометрическую форму, соблюдая заданные зазоры и минимизируя длину.

In Cad TopoR the topological routing is performed in two stages. First, TopoR is searching for topological paths of the wires, then their geometric shape is calculated. Topological path doesn’t give information about the actual distances between the wire and the rest of the PCB elements (other wires, pads, vias). The proposed algorithm based on the topological path of a wire calculates the geometric shape, following the specified clearance and minimizing the length.

Введение

Трассировка в САПР TopoR выполняется в два этапа – топологический и геометрический. На топологическом этапе модель печатного монтажа представляет собой триангуляцию Делоне. Вершинами триангуляции являются некоторые точки расположенных на плате объектов. Используя данное представление, алгоритм поиска находит топологические пути проводников. Топологический путь после расстановки переходных отверстий представляется исходной и конечной вершинами, а также последовательностью ребер, которые он пересекает, либо ребром, вдоль которого он идет.

Затем происходит переход на второй, геометрический этап, на котором моделью печатного монтажа является квазитриангуляция [1]. Квазитриангуляция представляет собой разбиение монтажного пространства на треугольные грани и квазиребра. Каждое квазиребро разделяет две грани и соединяет две квазивершины. Квазивершина представляется точкой или отрезком. Квазиребро, в связи с появлением двумерных вершин, уже может быть не только отрезком, как в триангуляции, но и треугольником или четырехугольником. Каждому квазиребру соответствует по две квазидуги. Грани квазитриангуляции, как и в триангуляции, треугольные (рис. 1).

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

c – треугольное, d – вырожденное, a и e – параллельные, f – квазиребро содержит часть отрезка

На геометрическом этапе объекты печатного монтажа представляются набором примитивов – квазивершин с определенными радиусами (ширинами). Например, переходное отверстие – примитив с центром в вершине квазитриангуляции и заданным радиусом. Некруглые контактные площадки представляются одним или несколькими примитивами.

При переходе с первого на второй этап топологический путь проводника преобразуется в путь, идущий от квазивершины и до квазивершины. Обеим квазивершинам соответствуют свои примитивы, поэтому в дальнейшем изложении будем говорить, что топологический путь проводника соединяет два примитива. Далее будем опускать приставку «квази-». Топологический путь проводника может идти вдоль ребра, либо пересекать одно и более ребер (рис. 2).

1. Основные понятия

Алгоритм вычисляет геометрическую форму проводника по заданному топологическому пути. Удобнее ассоциировать топологический путь проводника не с ребрами, а с дугами триангуляции, поэтому входными данными алгоритма являются начальный и конечный примитивы, а также дуга, вдоль которой идет проводник, либо последовательность дуг, которые он пересекает.

Исток – примитив, с которого начинается топологический путь проводника.

Сток – примитив, на котором заканчивается топологический путь проводника.

Проводник, геометрическая форма которого вычисляется, называется текущим.

Текущий проводник должен огибать препятствия, которые нельзя пересекать. Препятствиями являются объекты печатного монтажа (контактные площадки, переходные отверстия…). Все они, кроме проводников, представлены примитивами и поэтому для алгоритма идентичны. Для правильного вычисления геометрической формы проводника следует учесть препятствия, а также допустимые расстояния до них (зазоры).

С этой целью создаются шкивы. Каждой пересеченной дуге квазитриангуляции соответствуют ровно два шкива, расположенные на ее концах. Если две дуги на концах имеют общую точку, то создается общий шкив для этих дуг. Шкив имеет несколько атрибутов, например:

1. Центр шкива – точка того конца дуги, которому он соответствует.

2. Радиус шкива – величина, определяемая по радиусу примитива, сумме ширин проводников, расположенных между текущим проводником и примитивом, ширине текущего проводника, а также зазорам между ними.

3. Принадлежность к левой или правой стенке коридора.

Шкивы можно представить кругами (секторами кругов), расположенными с двух сторон (слева и справа) от топологического пути проводника (рис. 2). Между шкивами расположены проемы. Проем может быть ребром, соединяющим примитивы, либо частью примитива между дугами. Шкивы и проемы образуют коридор.

рис. 2 Топологический путь проводника вдоль ребра (а) и пересекающий ребра (б). Путь идет слева направо, наверху дугами изображены левые шкивы,

внизу – правые. Примитивы с ненулевыми радиусами выделены серым цветом

При вычислении геометрической формы понадобятся понятия круга и окружности шкива. Круг шкива – круг, центр которого расположен в центре шкива, а радиус равен радиусу шкива. Окружность шкива – окружность, центр которой расположен в центре шкива, а радиус равен радиусу шкива.

Топологический путь проводника проходит из истока в сток, разделяя пересекаемое пространство на левую и правую части. Шкивы и проемы, расположенные слева от топологического пути, образуют левую стенку коридора, а расположенные справа – правую стенку коридора.

2. Создание коридора

2.1. Создание коридора из истока и стока

Сначала особо рассматриваются исток и сток. Независимо от вытянутости соответствующих примитивов создаются по два шкива для них:

1. Левый исток.

2. Правый исток.

3. Левый сток.

4. Правый сток.

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

Между шкивами одной стенки вводится отношение линейного порядка – предыдущий (следующий). Для стенки коридора исток является первым и вначале является предыдущим для стока, который, в свою очередь, является следующим для истока. Каждому шкиву соответствует ровно один проем, расположенный слева от него, то есть после предыдущего шкива. Для левого и правого истоков проемами являются примитивы, независимо от вытянутости соответствующего примитива.

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

2.2. Вычисление вспомогательных радиусов

Минимальная и номинальная ширина проводников, а также минимальный и номинальный зазоры между цепями, задаются правилами разводки. Текущая ширина проводников может отличаться от номинальной. По этим данным формируются два значения ширины (width) (минимальная (wMin), текущая (wCur)) и два значения зазора (clearance) (минимальный (cm), номинальный (cd)).

Для каждого шкива, расположенного на концах дуги, вычисляются по три базовых радиуса:

1. rd – радиус с нормальным зазором и нормальной шириной проводника.

2. rc – радиус с уменьшенным зазором и нормальной шириной проводника.

3. rb – радиус с уменьшенным зазором и подрезкой проводника.

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

1. Инициализация нулями.

2. Прибавить к каждому по половине ширины текущего проводника, формулы 1, 2, 3.

(1)

(2)

(3)

3. Перебрать все проводники между текущим и примитивом, прибавить ширину проводников и зазоры между ними, зазор от текущего проводника до них и зазор от ближайшего проводника к примитиву до примитива: rd += cd, rc += cm, rb += cm, rd += wCur, rc += wCur, rb += wMin.

2.3. Обработка пересеченного ребра

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

1. Дуга начинается в новой точке примитива, в которой не заканчивалась предыдущая дуга. Следует создать два новых шкива на концах дуги. Точки концов дуги являются центрами создаваемых шкивов (рис. 3 (а, в)).

2. Дуга начинается в точке примитива, в которой закончилась предыдущая дуга, а заканчивается не в точке начала предыдущей дуги. Следует создать лишь один новый шкив, центром его является точка конца дуги (рис. 3 (б)). Шкив с центром в точке начала дуги уже создан при обработке в первом состоянии, но его необходимо рассмотреть для возможного уменьшения радиуса.

Если точки начала и конца дуги совпадают с точками конца и начала предыдущей дуги, то это выход из простого ребра, дуга не обрабатывается.

рис. 3 Число шкивов зависит от формы ребра: (а) – невытянутое ребро и два шкива, (б) – треугольное ребро и три шкива, (в) – четырехугольное ребро и четыре шкива

Созданные шкивы добавляются в соответствующие им стенки коридора, корректируются отношения предыдущий/следующий. Шкив добавляется перед последним шкивом соответствующей стенки.

После создания двух шкивов при обработке дуги следует задать радиусы новых шкивов. Если создался лишь один шкив, то ему следует задать радиус, и, при необходимости, уменьшить радиус шкива противоположного конца дуги.

2.4. Вычисление радиуса шкива

Определить расстояние между примитивами дуги, на конце которой находится шкив. Расстоянием (dist) в общем случае является не длина дуги, а расстояние между точкой конца дуги и ее проекцией на примитив противоположного конца дуги (рис. 4).

рис. 4 Примеры расстояний между примитивами, вычисленными по проекциям (горизонтально расположены примитивы)

Радиус определяется по ранее вычисленным базовым радиусам. Данные шкива, радиус которого вычисляется, имеют индекс 1, данные шкива противоположного конца дуги – индекс 2. Введем обозначения: capD = rd₁ + rd₂, capC = rc₁ + rc₂, capB = rb₁ + rb₂.

1. Если dist >= capD, то между шкивами достаточно места для проводника без уменьшения зазоров и подрезки.

2. Иначе следует попробовать уменьшить зазоры и при необходимости подрезать проводники.

2.1. В этом случае вычисляется вспомогательная величина a.

2.1.1. Если dist >= capC, то a вычисляется по формуле 4.

(4)

2.1.2. Иначе если dist >= capB, то a вычисляется по формуле 5.

(5)

2.1.3. Иначе a вычисляется по формуле 6.

(6)

2.2. Если rd₁ <= a, то R = rd₁.

2.3. Если rd₂ <= dist - a, то R = dist - rd₂.

2.4. Иначе R = a.

2.5. Создание перегородок

С каждым шкивом связан список перегородок. Перегородка идет от шкива к шкиву, имеющим общую дугу. Каждая стенка коридора также имеет свой список перегородок. При создании шкива по дуге к обоим ее шкивам в список перегородок добавляется новая последняя перегородка (если списки пусты, то добавляется первая перегородка, она же пока последняя). Перегородки также добавляются в соответствующие списки левой и правой стенки коридора.

2.6. Корректировка координат центров шкивов истока и стока

В случае проводника, пересекающего ребра, после создания всех шкивов необходимо скорректировать координаты центров шкивов истока и стока, если эти шкивы расположены на вытянутых примитивах. Для этого строится проекция центра соседнего в стенке шкива на примитив. Точка проекции становится центром соответствующего шкива.

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

2.7. Определение лучей шкивов

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

2.8. Пересечение шкивов

Геометрическая форма проводника вычисляется так, чтобы проводник проходил между шкивами левой и правой стенки. Пересечение шкивов одной стенки не мешает этому, но между шкивами противоположных стенок проводник должен поместиться. Таким образом, следует обеспечить непересекаемость шкивов разных стенок. Это достигается уменьшением радиусов (подрезкой) пересекающихся шкивов.

Стенки коридора рассматриваются по очереди. Возьмем следующий шкив после левого истока. При добавлении шкивов учитывался радиус всех шкивов, имеющих общую перегородку с новым, поэтому рассматриваемый шкив не пересекается с соседями по перегородкам. В его списке перегородок возьмем последнюю, по ней узнаем противоположный (имеющий ту же перегородку) шкив pivOp. Левый шкив проверяется на пересечение с правыми, начиная со следующего шкива после pivOp и до правого стока (не включая его). Перебор может закончится раньше, например, в случаях резкого поворота коридора. Точно так же обрабатываются остальные шкивы левой стенки. В случае пересечения шкивов вычисляются их уменьшенные радиусы, которые запоминаются отдельно.

Обработав на пересечение левую стенку, следует проверить пересечение шкивов правой стенки со шкивами левой.

Только после проверки на пересечение шкивам присваиваются новые вычисленные уменьшенные радиусы.

2.9. Определение поворотов коридора

Из каждой стенки по очереди берется по три шкива и определяется поворот. Три шкива:

1. Предыдущий (pivP), его центр P.

2. Текущий (pivC), его центр C.

3. Следующий (pivN), его центр N.

Итерации продолжаются, пока есть следующий шкив. Сначала рассматривается левая стенка, затем правая. Рассмотрим, например, левую. Предыдущим является левый исток, а текущий и следующий – это последовательно два следующих шкива в стенке. На следующей итерации идет сдвиг на один вперед, то есть текущий становится предыдущим, следующий – текущим, а следующий за ним – следующим. Поворот в каждой тройке определяется для текущего шкива.

1. Если центры P и N совпадают, то это поворот на 360 градусов (рис. 5 (а)).

2. Иначе узнать шкивы на концах первой и последней перегородок pivC (pivOpp1 и pivOpp2). Если точка центра pivOpp1 совпадает с точкой центра N и точка центра pivOpp2 совпадает с точкой центра P, то это поворот больше чем на 360 градусов. При этом лучи шкива pivC (в сторону предыдущего и следующего) меняются местами.

3. (Если стенка правая, то для дальнейшей проверки поменять местами центры P и N.)

4. Иначе если точки центров P, C, N расположены по часовой стрелке, то это поворот меньше 180 градусов (рис. 5 (б)).

5. Иначе если точки центров P, C, N расположены против часовой стрелки, то это поворот больше 180 градусов, но меньше 360 (рис. 5 (в)).

6. Иначе поворот на 180 градусов.

(а) (б) (в)

рис. 5 Углы поворота коридора (а) – угол поворот 360 градусов, (б) – угол поворота меньше 180 градусов, (в) – угол поворота больше 180 градусов

2.10. Отметка пропускаемых шкивов

Круги шкивов могут быть вложены друг в друга, либо пересекаться. При выполнении определенных условий часть таких шкивов не влияет на вычисление геометрической формы проводника. Условие определяется по кругам шкивов и повороту коридора, лучам шкива. Шкивы, не влияющие на вычисление геометрической формы проводника, отмечаются как пропускаемые.

2.11. Учет препятствий, расположенных за ребрами триангуляции

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

2.12. Расчёт точки split

Для всех непропускаемых шкивов кроме истоков и стоков рассчитывается точка split. Эта точка является вспомогательной для определения места, где проводник, огибая шкив, не может оказаться.

1. Если на шкиве коридор поворачивает на 360 градусов, то точка split расположена на пересечении окружности шкива и предыдущего луча.

2. Иначе вычисляются точки пересечения предыдущего (B) и следующего (E) лучей шкива с окружностью шкива. Точкой split становится середина дуги, расположенной между B и E, расположенными против часовой стрелки. Напомним, что для правой стенки лучи определялись не так, как для левой, поэтому точки независимо от стенки расположены против часовой стрелки.

3. Построение пути из шкивов

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

По шкивам обрабатываемого дека и другого дека, а также шкивам, добавленным в путь из шкивов, определяются места огибания проводником препятствий. Те шкивы, с окружностями которых геометрическая форма проводника непосредственно контактирует, добавляются в путь из шкивов.

Построенный путь из шкивов определяет геометрическую форму проводника. Геометрическая форма является последовательностью дуг окружностей шкивов из пути и их общих касательных.

Заключение

Алгоритм вычисления геометрической формы проводника успешно внедрен в САПР TopoR.

Литература

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