Рис. 4. Пример применения метода отбрасывания тени
Метод отбрасывания тени [5] базируется на построении лучей от
некоторого геометрического объекта по координате, для которой стро-
ится граф ограничений. В случае если луч упирается в другой элемент,
этот элемент добавляется в список препятствий. На рис. 4 приведен
пример построения лучей и нахождения препятствий. На основе этого
списка проводятся ребра графа между вершинами, соответствующи-
ми исходному геометрическому объекту и объекту-препятствию. Ме-
тод отбрасывания тени требует большого объема вычислений в связи с
необходимостью перебора точек на некотором пространстве. С учетом
этого для построения графа ограничений целесообразно использовать
метод сканирующей линии.
Алгоритм построения графа противоречий.
Для автоматиза-
ции проектирования топологии для технологии двойного фотоша-
блона, помимо графа ограничений, необходимо построить граф про-
тиворечий. Для этого необходимо выделить фрагменты топологии,
расположенные на расстоянии менее заданного значения параметра
d
dp
(
GeO
i
, GeO
j
)
.
Для определения параметра
d
dp
(
GeO
i
, GeO
j
)
могут быть исполь-
зованы различные подходы. Более точный подход базируется на ком-
пьютерном моделировании оптических эффектов и должен учитывать
сложные модели литографии. Другой подход базируется на использо-
вании некоторых эвристических правил. Он отличается меньшей точ-
ностью по сравнению с методом компьютерного моделирования про-
цесса литографии, однако требует меньших вычислительных затрат.
К сожалению, первый подход оказывается неэффективным при реше-
нии задачи трансформации топологии сложнофункциональных блоков
в связи с очень большими временными затратами на моделирование
оптических эффектов. В связи с этим в настоящей работе использу-
ется второй подход, базирующийся на использовании эвристических
правил. Полагается, что параметр
d
dp
(
GeO
i
, GeO
j
)
задан эвристиче-
ски после выполнения различных компьютерных экспериментов по
моделированию процесса фотолитографии или экспериментов на со-
ответствующем литографическом оборудовании.
Граф противоречий является обычным (невзвешенным) графом
G
2
= (
X
2
, U
2
)
,
(6)
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2011. № 1 83
