JPH08227431A - マスクパターンのリサイジング方法 - Google Patents

Abstract

(57)【要約】 【目的】ＣＡＤシステムによって、マスクパターンの入
力図形を、高速で拡大演算または縮小演算処理する。 【構成】入力図形が斜辺を有するかどうかを判定し、斜
辺を有している場合には、その入力図形の頂点毎に、そ
の頂点が斜辺の影響を受けるかどうかを判定する。頂点
が斜辺の影響を受ける場合には、その頂点を挟む入力図
形の一対の辺を、図形の内部または外部に平行移動した
際のその頂点に対応するそれぞれの端点を、その頂点と
ともに仮図形の頂点とする。頂点が斜辺の影響を受けな
い場合には、その頂点を挟む入力図形の一対の辺を図形
の外部または内部にそれぞれ平行移動した際の各辺の交
点、または平行移動した各辺の延長線の交点を、入力図
形の頂点に対する仮図形の頂点とする。その後、得られ
た仮図形の各頂点を結んで仮図形を生成し、生成された
仮図形をＯＲ演算する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ＣＡＤ（Computer Aid
ed Design ）システムを利用して実施されるマスクパタ
ーンを拡大演算処理および縮小演算処理するリサイジン
グ方法に関する。

【０００２】

【従来の技術】ＬＳＩの大規模高集積化に伴って、現在
では、ＣＡＤシステムにより、ＬＳＩが設計されてい
る。特に、マスクパターンを対象としたアートワークシ
ステムにおいて、図形演算機能はなくてはならないもの
になっている。

【０００３】図形演算の一つとして、マスクパターンの
拡大および縮小を行うリサイジング（resizing）は、マ
スクパターンの最小間隔や最小幅に関する設計規則検
証、配線可能領域の抽出、ノッチや突起の除去等に利用
されている。この場合のリサイジングは、マスクパター
ンを入力図形として、その各辺を、図形の外部あるいは
内部へ指定された変更幅だけ平行移動して、拡大図形ま
たは縮小図形を得る操作のことであり、相似図形を得る
操作ではない。

【０００４】例えば、図１８（ａ）に示すようなマスク
パターンを入力図形３０として、その入力図形３０の各
辺を、図１８（ｂ）に示すように、指定幅ｄだけそれぞ
れ外部に平行移動させて拡大図形３１を得る操作がリサ
イジング（拡大演算）であり、図１８（ｃ）に示すよう
に、入力図形３０の各辺をそれぞれ拡大させて相似図形
３２を得る操作とは異なる。

【０００５】リサイジングにおける拡大演算（expandin
g)では、図１９（ａ）に示すように、入力図形３０の各
辺から指定幅ｄの範囲にある外部領域３３も、図形の内
部として扱うことを基本概念としており、縮小演算（sh
rinking)では、図１９（ｂ）に示すように、入力図形の
各辺から指定幅ｄの範囲にある内部領域３４も図形の外
部として扱うことを基本概念としている。拡大演算の場
合には、入力図形３０における頂点の内角が凸角（πよ
り小）になっていると、その頂点は、指定幅ｄだけ拡大
されることにより円弧状になる。

【０００６】例えば、拡大演算の場合には、図１９
（ｃ）に示すように、入力図形３０における内角が凸角
になった頂点３０ａは、その頂点を構成する各辺３０ｂ
および３０ｃがそれぞれ平行移動することにより消滅す
るが、扇形補間図形３５によって補間されることによ
り、円弧状になる。しかし、マスクパターンでは、円弧
状の扇形補間図形３５が存在すると、取扱が困難になる
ことから、図１９（ｄ）に示すように、扇形補間図形３
５における円弧部分の両端の各接線と円弧部分とによっ
て囲まれた追加図形３６を扇形補間図形３５に加えて、
図１９（ｅ）に示すように、扇形補間図形３５を四角形
補間図形３７に変えている。これにより、図１９（ｆ）
に示す拡大図形（リサイジング図形）３１が得られる。

【０００７】縮小演算の場合も、同様に、扇形補間図形
における円弧部分の両端の各接線と円弧部分とによって
囲まれた追加図形を扇形補間図形に加えて構成された四
角形補間図形を図形の外部として扱うことにより、図１
９（ｇ）に示す縮小図形（リサイジング図形）３８が得
られる。

【０００８】このようにして得られたリサイジング図形
は、ＩＣのマスクパターンの最小間隔や最小幅に関する
規則検証、配線可能領域の抽出、ノッチや突起の除去等
に利用される。

【０００９】最小間隔の設計規則検証は、複数のマスク
パターンが指定された最小間隔ｄだけ相互に離れている
かどうかを判定するとともに、最小間隔ｄを満たしてい
ない場合にはその部分を特定する処理である。例えば、
図２０（ａ）に示すように、相互に平行になった一対の
マスクパターンに相当する入力図形４１および４２が、
最小間隔ｄを満足しているか否かを検証する場合には、
図２０（ｂ）に示すように、各入力図形４１および４２
を、最小間隔ｄの１／２の幅で拡大演算し、図２０
（ｃ）に示すように、拡大演算されたリサイジング図形
４３および４４が相互に重なっている場合には、その重
なり部分４５にて、各入力図形４１および４２は最小間
隔ｄを満足していないものとして特定する。

【００１０】最小幅検証は、例えば、図２１（ａ）に示
すような形状のマスクパターンに相当する図形４６が、
最小幅寸法を満足しているか否かを検証する処理であ
り、マスクパターンに相当する入力図形４６を最小幅寸
法ｄの１／２の幅で縮小演算し、図２１（ｂ）に示すよ
うに、縮小演算されたリサイジング図形４７が、複数の
図形４７ａおよび４７ｂに分離されたら、図２１（ｃ）
に示すように、その分離された部分４８が最小幅寸法ｄ
を満足していないものとして特定する。

【００１１】配線可能領域の抽出は、例えば、図２２
（ａ）に示すように、すでに配線されている領域等のよ
うに、配線ができない領域を示す３つの入力図形５１、
５２、５３を、図２２（ｂ）に示すように、配線幅の１
／２と配線最小間隔との和に等しい寸法ｄだけそれぞれ
拡大演算し、図２２（ｃ）に示すように、拡大演算され
た各リサイジング図形５４、５５、５６以外の領域５７
を、配線可能領域として抽出する。

【００１２】ノッチまたは突起の除去とは、マスクパタ
ーンにおけるノッチの幅寸法（切り欠き部分の間隔）、
または、突起の幅が、最低寸法を満足していない場合
に、そのノッチ部分または突起部分を除去するものであ
り、例えば、図２３（ａ）に示すように、ノッチ６１ａ
を有する入力図形６１の場合には、ノッチ６１ａの最小
幅寸法ｄの１／２の寸法で、図形６１を拡大演算し、図
２３（ｂ）に示すように、拡大演算されたリサイジグ図
形６２を得る。その後、図２３（ｃ）に示すように、拡
大演算されたリサイジング図形６２を同じ寸法（ｄ／
２）だけ縮小演算する。ノッチ６１ａの幅寸法が、最小
幅寸法ｄを満足していない場合には、縮小演算によって
得られたリサイジング図形６３は、ノッチ６１ａが除去
された状態になる。

【００１３】ＩＣのマスクパターンを構成する図形群を
処理する図形演算は、ＩＣの大規模集積化による図形数
の増大に伴って、人手処理が困難となり、ＣＡＤシステ
ムで処理されるようになっている。例えば、特開平３−
９４７４号公報には、コンピューターを援用した隣接パ
ターン間のオーバーラップを自動的に作成する方法が開
示されており、また、特開平６−１９１１０号公報に
は、ＣＡＤデーターを使用して半導体製造用マスクデー
ターを作成する方法が開示されている。

【００１４】また、膨大な数の図形を処理する必要性か
ら、図形演算には高速なアルゴリズムが各種提案されて
いる。

【００１５】例えば、「A Concurrent pattern Operati
on Algorithm for VLSI Mask Data(Proc. 18th Design
Automation Conference, 1981) 」には、図形演算のひ
とつであるＯＲ演算について報告されている（以下、こ
の報告を従来法１とする）。ＯＲ演算は、図形が１つ以
上重なっている領域と、図形が１つもない領域とを隔て
る境界線を抽出する演算であり、この報告では、ＯＲ演
算実行前の入力図形群の総頂点数をｎとすると、O(n lo
g n)の計算複雑度でＯＲ演算後の図形群を得ることがで
きる。

【００１６】ＯＲ演算の一例を、図２４に示す。図２４
（ａ）に示すように、小さな正方形の入力図形６５と、
大きな正方形の入力図形６６と、この大きな正方形の入
力図形６６に一部が重なった長方形の入力図形６７と、
さらに、小さな長方形の開口部を示す入力図形６８とを
ＯＲ演算する場合には、各入力図形６５〜６８の全ての
辺をベクトル化する。本例では、便宜的に図形の内部が
右側になるように各辺をベクトル化しており、従って、
開口部の入力図形６８の各辺は、開口部の内部が左側に
なるようにベクトル化される。そして、ベクトルの向き
から入力図形６５〜６８の重なり数を得て、重なり数が
１以上の部分が取り出される。通常、開口部でない１つ
の入力図形の重なり数は１であり、図形の外側は０であ
る。また、２つの入力図形が重なっている部分では、重
なり数は２であり、開口部は重なり数が−１になる。Ｏ
Ｒ演算の結果、図２４（ｂ）に示す図形が得られ、負に
なった開口部の入力図形６８は消滅する。

【００１７】また、図形の拡大および縮小演算に関して
は、「An O(n log n)algorithm forLSI layout resizin
g problems (ISCAS '85,1985) 」に報告されている（以
下、この報告を従来法２とする）。この報告では、Ｘ方
向の拡大または縮小とＹ方向の拡大または縮小とを別個
に行うことにより、リサイジング図形を得るようになっ
ている。

【００１８】このために、入力図形群の総頂点数をｎと
すると、理論的には、O(n log n)の計算複雑度にて処理
できるが、Ｘ方向とＹ方向との拡大または縮小が別個に
実施されるために、処理時間の高速化が困難であるとい
う問題がある。

【００１９】しかも、基本的にはＸ方向およびＹ方向に
平行な水平辺および垂直辺のみからなる図形を対象とし
ているために、Ｘ軸に対して４５°または１３５°の角
度の斜辺を有する入力図形でもリサイジング処理は可能
であるが、斜辺の処理が複雑になる。例えば、図２５
（ａ）に示すように、一対の斜辺７１および７２の間に
短い水平辺７３を有するような入力図形７０や、図２５
（ｂ）に示すように、斜辺７４と水平辺７５との間に短
い垂直辺７６を有するような入力図形７７を、水平辺７
３および垂直辺７６の長さよりも大きな変更幅で拡大演
算する場合には、正確なリサイジング図形が得られな
い。各図形の正確な拡大演算処理図形は、図２５（ａ）
および（ｂ）に一点鎖線で示すように、水平辺７３およ
び垂直辺７６に対応する辺がそれぞれ消滅した状態にな
る。このような正確な拡大演算処理図形を得るために
は、各辺のＸ方向およびＹ方向の拡大処理に、さらに、
水平辺７３を挟む一対の斜辺７１および７２の交点計
算、垂直辺７６を挟む斜辺７４および垂直辺７５の交点
計算が、それぞれ必要になる。従って、このような複雑
な処理を追加しなければ正確なリサイジング図形を得る
ことができず、処理時間を高速化することは容易ではな
い。

【００２０】さらに、「任意角度辺を含むＬＳＩパター
ンの拡大・縮小手法（情報処理学会研究報告DA43-4, 19
88-7）」には、任意角度辺からなる入力図形を対象とし
て、リサイジング図形を得るために、中間的な仮図形を
生成し、生成された仮図形をＯＲ演算することにより、
リサイジング図形を得る方法が開示されている（以下、
これを従来法３とする）。

【００２１】この従来法３のフローチャートを図２６に
示す。この従来法３では、まず、変更幅ｄを読み込むと
（図２６（ａ）のステップ２６−１、以下同様）、複数
の入力図形からなる入力図形群Ｓを読み込む（ステップ
２６−２）。そして、読み込まれた入力図形群ＳをＯＲ
演算する（ステップ２６−３）。

【００２２】マスクパターンが複数の図形によって構成
された図形群として入力される場合には、マスクパター
ンを拡大演算処理または縮小演算処理する前に、ＯＲ演
算が必要になる。例えば、図２７（ａ）に示すマスクパ
ターン８０を、図２７（ｂ）に示すように３つの矩形の
入力図形８１、８２、８３として入力された場合に、Ｏ
Ｒ演算処理することなく拡大演算処理すると、図２７
（ｃ）に示すように、全ての入力図形８１、８２、８３
が拡大演算処理されるために、各入力図形８１、８２、
８３に対する拡大図形８１’、８２’、８３’が得ら
れ、これらの拡大図形８１’、８２’、８３’をＯＲ演
算処理しても、正確なリサイジング図形が得られない。
このために、マスクパターンが複数の図形にて構成され
た図形群にて入力される場合には、その入力図形群に対
してＯＲ演算が必要になる。

【００２３】その後、入力図形群のＯＲ演算処理後の図
形数をＮとして（ステップ２６−４）、Ｎ個の入力図形
の全てに対して仮図形を生成する（ステップ２６−５〜
２６−１８）。

【００２４】仮図形の生成に際して、ｎ番目の入力図形
をＦとして（ステップ２６−６）、その入力図形Ｆの頂
点数をＭとし（ステップ２６−７）、全ての頂点を頂点
列として方向付けて、各辺をベクトル化する（ステップ
２６−８）。そして、全ての頂点に対して仮図形の頂点
を生成する（ステップ２６−９〜２６−１６）。

【００２５】仮図形の頂点は、入力図形Ｆにおける頂点
列のｍ番目の頂点をＶ、その頂点Ｖのベクトルの方向と
は反対側に隣接する頂点をＵ、頂点Ｖのベクトル方向に
隣接する頂点をＷとし（ステップ２６−１０）、リサイ
ジングが拡大演算か縮小演算かを判断する（ステップ２
６−１１）。そして、リサイジングが拡大演算の場合に
は、頂点Ｖの内角が凸角（πよりも小）か、凹角（πよ
りも大）かを判定する（ステップ２６−１２）。頂点Ｖ
の内角が凸角の場合には、頂点Ｖを挟む一対の辺ＵＶお
よびＶＷをそれぞれ変更幅ｄだけＯＲ演算図形の外部に
平行移動して得られる各ベクトルまたはそれらの延長線
の交点を仮図形の頂点とする（ステップ２６−１４）。
このような仮図形の頂点の生成方法をプロセスＡとす
る。

【００２６】また、リサイジングが拡大演算であって、
頂点Ｖの内角が凹角の場合には、頂点Ｖを挟む一対の辺
ＵＶおよびＶＷをそれぞれ変更幅ｄだけＯＲ演算図形の
外部に平行移動して得られる各ベクトルＵ’Ｖ’および
Ｖ”Ｗ’の頂点Ｖに対応するそれぞれの端点Ｖ’および
Ｖ”と、入力図形の頂点Ｖとを、Ｖ’、Ｖ、Ｖ”の順
に、それぞれ、仮図形の頂点として登録する（ステップ
２６−１５）。このような仮図形の頂点の生成方法をプ
ロセスＢとする。

【００２７】リサイジングが縮小演算の場合にも、頂点
Ｖの内角が凸角（πよりも小）か、凹角（πよりも大）
かを判定し（ステップ２６−１３）、拡大演算の場合と
は逆に、頂点Ｖの内角が凹角の場合には、プロセスＡに
よって、頂点Ｖを挟む一対の辺ＵＶおよびＶＷをそれぞ
れ変更幅ｄだけＯＲ演算図形の内部に平行移動して得ら
れるベクトルまたはそれらの延長線の交点を仮図形の頂
点とする（ステップ２６−１４）。リサイジングが縮小
演算であって、頂点Ｖの内角が凸角の場合には、プロセ
スＢによって、頂点Ｖを挟む一対の辺ＵＶおよびＶＷを
それぞれ変更幅ｄだけＯＲ演算図形の内部に平行移動し
て得られる各ベクトルＵ’Ｖ’およびＶ”Ｗ’の頂点Ｖ
に対応する端点Ｖ’およびＶ”と、ＯＲ演算図形の頂点
Ｖとを、Ｖ’、Ｖ、Ｖ”の順に、それぞれ、仮図形の頂
点として登録する（ステップ２６−１５）。

【００２８】このような仮図形の頂点の生成を、ＯＲ演
算によって生じた全ての図形に対して実施し（ステップ
２６−１７）、仮図形の登録された頂点を順番に結ぶこ
とにより、仮図形が生成される（ステップ２６−１
８）。そして、生成された仮図形をＯＲ演算して（ステ
ップ２６−１９）、ＯＲ演算された図形がリサイジング
図形Ｓとして出力される（ステップ２６−２０）。仮図
形は、辺が交差した状態になっているが、ＯＲ演算によ
り、正確なリサイジング図形とされる。

【００２９】この従来法３では、例えば、図２８（ａ）
に示すように、頂点数が１８の入力図形８４の場合に
は、図２８（ｂ）に示すように、頂点数が３２の仮図形
８５とされる。

【００３０】このような演算処理方法では、Ｘ方向また
はＹ方向のいずれか一方向の処理によって、斜辺を含ん
でいても、誤りのない正確なリサイジング図形を得るこ
とができる。また、ＯＲ演算図形の各頂点を辺に沿って
順番に処理し、ＯＲ演算図形を一周することにより終了
するために、O(n)の手数で簡単に処理することができ
る。さらに、辺の交差処理のために実施されるＯＲ演算
に、従来法１を採用することにより、従来法２のＯＲ演
算の場合と同様に、O(n log n)の計算複雑度を実現でき
る。しかも、内部のデーター構造が線形リストになるた
めに、従来法２のように、内部データーが線形リストに
なっていない場合よりも高速で処理することが可能にな
る。

【００３１】

【発明が解決しようとする課題】従来法３では、仮図形
は、O(n log n)の計算複雑度で生成されるために、処理
全体の計算時間は、仮図形のＯＲ演算に要する時間がほ
とんどである。しかしながら、仮図形の頂点の生成に際
して、入力図形の頂点が凸角か凹角かだけを判定して、
仮図形の頂点を１つだけ生成するプロセスＡとするか、
頂点を３つ生成するプロセスＢとするようになっている
ために、拡大演算（または縮小演算）時に入力図形の頂
点が凹角（または凸角）になっていると、その頂点に対
応する仮図形の頂点として３つが生成されることにな
る。その結果、仮図形の頂点数が多くなり、仮図形のＯ
Ｒ演算に長時間を要するという問題がある。

【００３２】仮図形の総頂点数を削減する方法として、
仮図形の頂点の生成を、従来法３のプロセスＡだけを適
用することにより、入力図形の各頂点に対して１つの仮
図形の頂点を生成することも考えられる。以下、これを
従来法４とし、そのフローチャートを図２９に示す。図
２９のフローチャートでは、仮図形の全ての頂点を、前
述のプロセスＡによって生成するようになっており（ス
テップ２９−１１）、他のステップは、図２６に示す従
来法３のフローチャートと同様である。

【００３３】この従来法４での仮図形の各頂点の生成方
法は、頂点を挟む２辺を指定幅ｄだけ平行移動して、平
行移動された各辺の交点、または、平行移動された各辺
の延長線の交点を仮図形の頂点とするものである。従っ
て、入力図形の１つの頂点に対して仮図形の１つの頂点
が生成される。そして、仮図形の頂点を順番に結ぶこと
により、仮図形が生成される。従って、入力図形に斜辺
が含まれており、しかも、拡大演算時に凹角（または縮
小演算時に凸角）になった入力図形の頂点数が多い場合
にも、仮図形の総頂点数は、従来法３に比べて少なくす
ることができ、ＯＲ演算に要する時間も短縮される。

【００３４】しかし、図３０（ａ）に示すように、複数
の四角形からなる入力図形８６が斜辺を有する場合に
は、一点鎖線で示す拡大演算図形８７が得られ、本来、
図形の内部として扱われるべき部分８７ａが、図形の外
部として認識されるために、誤った仮図形が生成され
る。同様に、図３０（ｂ）に示すように斜辺を有する入
力図形８８の場合にも、拡大演算図形８９は、図形の内
部として扱われるべき部分８９ａが図形の外部として認
識された誤った仮図形が生成される。

【００３５】本発明は、このような問題を解決するもの
であり、その目的は、ＩＣのマスクパターンを構成する
図形が斜辺を含んでいる場合にも、正確なリサイジング
図形を、高速で得ることができるマスクパターンのリサ
イジング方法を提供することにある。

【００３６】

【課題を解決するための手段】本発明のマスクパターン
のリサイジング方法は、ＣＡＤシステムによって、マス
クパターンに対応する入力図形の各辺を、その入力図形
の外部または内部に平行移動させて拡大図形または縮小
図形を得るマスクパターンのリサイジング方法であっ
て、前記入力図形が斜辺を含むかどうかを判定する工程
と、その入力図形が斜辺を含んでいる場合には、その入
力図形の頂点毎に、その頂点が斜辺の影響を受けるかど
うかを判定する工程と、入力図形の頂点が斜辺の影響を
受ける場合に、その頂点を挟む入力図形の一対の辺を、
図形の内部または外部に平行移動した際のその頂点に対
応するそれぞれの端点を、その頂点とともに仮図形の頂
点とする工程と、入力図形の頂点が斜辺の影響を受けな
い場合には、その頂点を挟む入力図形の一対の辺を図形
の外部または内部にそれぞれ平行移動し、平行移動され
た各辺の交点または平行移動された各辺の延長線の交点
を、入力図形の頂点に対する仮図形の頂点とする工程
と、得られた仮図形の各頂点を結んで仮図形を生成する
工程と、生成された仮図形をＯＲ演算する工程と、を包
含することを特徴とするものであり、そのことにより上
記目的が達成される。

【００３７】なお、入力図形の各頂点が、斜辺の影響を
受けるかどうかを、その頂点に隣接する各頂点を挟む一
対の辺に斜辺が含まれているかどうかによって、あるい
は、その頂点に隣接する各頂点の角度に基づいて、ある
いは、その頂点の角度と、その頂点に隣接する各頂点の
角度と、その頂点の角度と隣接する各頂点それぞれの角
度との和とに基づいて、判定することが好ましい。

【００３８】

【作用】本発明のマスクパターンのリサイジング方法で
は、まず、マスクパターンに相当する入力図形の各辺
に、斜辺が含まれているかどうかを判定し、斜辺が含ま
れている場合には、入力図形の各頂点が、斜辺の影響を
うけるかどうかを判定する。そして、斜辺の影響を受け
ない頂点の場合には、その頂点を挟む一対の辺を、拡大
演算の場合には図形の外部、縮小演算の場合には図形の
内部に、それぞれ平行移動し、平行移動された各辺の交
点、または、各辺の延長線の交点を、仮図形の頂点とす
る。従って、この場合には、１つの頂点に対して仮図形
の頂点は、１つ生成される。頂点が斜辺の影響を受ける
場合には、その頂点を挟む一対の辺を、拡大演算の場合
には図形の外部、縮小演算の場合には図形の内部に、そ
れぞれ平行移動し、平行移動された各辺における頂点に
対応する各端点それぞれと、もとの入力図形の頂点との
３つを、仮図形の頂点として設定する。

【００３９】仮図形の頂点が設定されると、各頂点を結
んで仮図形を生成し、ＯＲ演算することにより、リサイ
ジング図形が得られる。

【００４０】入力図形における各頂点は、その頂点に隣
接する各頂点を挟むそれぞれ一対の辺のいずれかが斜辺
であれば、斜辺の影響を受けるものとされるが、ＩＣの
マスクパターンでは、通常、斜辺は図形の一部にしか利
用されないために、３つの仮図形の頂点を生成するプロ
セスが採用されることは稀であり、仮図形の総頂点数を
削減することができる。その後のＯＲ演算に要する時間
を短縮できて、処理の高速性が高められる。

【００４１】また、入力図形の頂点が斜辺の影響を受け
るかどうかを、その頂点に隣接する各頂点の角度に基づ
いて判定することにより、３つの仮図形の頂点を生成す
るプロセスが採用されることが減少し、図形処理の高速
性が高められる。さらに、入力図形の頂点が斜辺の影響
を受けるかどうかを、その頂点の角度と、その頂点に隣
接する各頂点の角度と、その頂点の角度と隣接する各頂
点それぞれの角度との和とに基づいて判定することによ
り、３つの仮図形の頂点を生成するプロセスの適用範囲
がさらに限定されて、図形処理は一層、高速化される。

【００４２】

【実施例】以下、本発明の実施例を図面に基づいて詳細
に説明する。

【００４３】本発明のマスクパターンのリサイジング方
法は、ＬＳＩのマスクパターンの検証等のために、ＣＡ
Ｄ（Computer Aided Design ) システムにより、マスク
パターンを入力図形として、その入力図形の各辺を図形
の外部あるいは内部へ指定された変更幅だけ平行移動す
ることにより拡大図形または縮小図形を得る方法であ
る。

【００４４】図１は、本発明のマスクパターンのリサイ
ジング方法の一例を示すフローチャートである。本実施
例では、まず、図１（ａ）に示すように、ＣＡＤシステ
ムに入力されるマスクパターンを拡大演算処理または縮
小演算処理（リサイジング処理）する際の各辺の変更幅
ｄが入力される（図１のステップ１−１参照、以下同
様）。この場合、入力図形を拡大するときの変更幅を
正、縮小するときの変更幅を負とする。

【００４５】次に、リサイジングの対象となるＬＳＩの
マスクパターンのデーターが、Ｘ−Ｙ座標で入力される
（ステップ１−２）。

【００４６】図２（ａ）は、入力されるマスクパターン
の一例を示している。このマスクパターン１０は、中央
部に４５度に傾斜する斜辺部１１を有しており、その斜
辺部１１の上側の端部から横長の長方形状の水平部１２
が水平方向に延出している。この水平部１２の先端部に
は、一辺の長さが水平部１２の幅寸法よりも大きな正方
形状の矩形部１３が連続している。また、斜辺部１１の
下側の端部には、短い縦長の長方形状の垂直部１４が垂
直に延出しており、その垂直部の下端部に横長の長方形
状の水平部１５が水平に延出している。そして、水平部
１５の先端部に、一辺の長さが水平部１５の幅寸法より
も大きな正方形状の矩形部１６が連続している。

【００４７】このようなマスクパターン１０は、ＣＡＤ
システムに図形入力される際に、複数の図形の集合体と
される。すなわち、図２（ａ）に示すマスクパターン１
０は、図２（ｂ）に示すように、傾斜状態になった長方
形状の傾斜入力図形１１’と、この傾斜入力図形１１’
の上側の端部に、一方の端部が重なった横長の長方形状
の水平入力図形１２’と、この水平入力図形１２’の他
方の端部に重なった正方形状の矩形入力図形１３’と、
この斜辺入力図形１１’の他方の端部に上端部が重なっ
た縦長の垂直入力図形１４’と、この垂直入力図形１
４’の下部に、一方の端部が重なった横長の長方形状の
水平入力図形１５’と、この水平入力図形１５’の他方
の端部に重なった正方形状の矩形入力図形１６’とし
て、ＣＡＤシステムに入力される。各入力図形１１’〜
１６’は、水平方向をＸ方向、垂直方向をＹ方向とし
て、また、各入力図形１１’〜１６’のそれぞれの辺
が、ベクトル化されて読み込まれる。

【００４８】入力図形１１’〜１６’の各辺のベクトル
は、本実施例では、便宜的に、図形の内側が右側になる
ように方向付けされている。ＣＡＤシステムに読み込ま
れた６個の入力図形１１’〜１６’は、入力図形群Ｓと
される。

【００４９】６個の入力図形１１’〜１６’が読み込ま
れると、読み込まれた入力図形群Ｓが、図形演算の一つ
であるＯＲ演算される（ステップ１−３）。ＯＲ演算と
は、各入力図形１１’〜１６’のそれぞれの辺をベクト
ル表示した際に、ベクトルの向きから図形の内側と外側
を判断することにより、入力図形１１’〜１６’が複数
の図形の重なりであるかどうかを検出し、重なり数が１
以上の図形部分を取り出すパターン論理演算である。

【００５０】図２（ｂ）に示す入力図形群ＳをＯＲ演算
すると、図２（ｃ）に示すように、マスクパターン１０
の輪郭に沿ったＯＲ演算図形Ｆが得られることになる。
このようにして得られるＯＲ演算図形Ｆの全ての辺は、
図形の内部が右側となるようにベクトル化されている。
そして、ベクトルが閉鎖されて生成されるＯＲ演算図形
Ｆの数が「Ｎ」として登録される（ステップ１−４）。
本実施例では、ＯＲ演算によって生成されたＯＲ演算図
形Ｆの数Ｎは１である。

【００５１】次に、ＯＲ演算によって生成されたＯＲ演
算図形Ｆ毎に番号ｎ（１〜Ｎ）が付されて、各ＯＲ演算
図形Ｆ毎に、正確なリサイジング図形を得るための中間
的な仮図形が生成される（ステップ１−５〜ステップ１
−２３）。

【００５２】仮図形の生成は以下のようにして実施され
る。すなわち、ＯＲ演算によって生成された各ＯＲ演算
図形Ｆ毎に、頂点の数Ｍを計数して（ステップ１−６お
よびステップ１−７）、仮図形の頂点列の集合を空集合
に初期化する（ステップ１−８）。

【００５３】次に、処理の対象とされている各ＯＲ演算
図形Ｆの全ての頂点について、それぞれの角度を算出し
て、角度の種別を判定することにより、処理対象のＯＲ
演算図形Ｆに斜辺が含まれているかどうかを判定する
（ステップ１−９）。

【００５４】処理対象になっているＯＲ演算図形Ｆの全
ての頂点の角度の種別の判定は、図３のフローチャート
に詳細に示されている。すなわち、まず、ＣＡＤシステ
ムは、ＯＲ演算図形Ｆが斜辺を含むかどうかを示すフラ
グＤを、斜辺を含んでいない「ＮＯ」の初期状態に設定
して（ステップ３−１）、ＯＲ演算図形ＦにおけるＭ個
の頂点に対して、それぞれ順番に、角度の種別が判定さ
れる（ステップ３−２〜ステップ３−２０）。

【００５５】ＯＲ演算図形Ｆの全ての頂点は、登録され
た頂点列の順番に判別され、例えば、ｍ番目の頂点をＶ
とすると（ステップ３−３）、その頂点Ｖの角度の種別
を判定する際に、まず、リサイジング処理が拡大演算で
あるか縮小演算であるかを判別する（ステップ３−
４）。リサイジング処理が拡大演算の場合には、その頂
点Ｖの内角がθとして算出され（ステップ３−５）、縮
小演算の場合には、頂点Ｖの外角がθとして算出される
（ステップ３−６）。これは、入力図形に対して拡大演
算処理した図形の輪郭と、入力図形の内部と外部とを入
れ換えて縮小演算処理した図形の輪郭とが同じであると
いう事実に基づき、拡大演算における頂点Ｖの内角が、
縮小演算における頂点Ｖの外角と同じ性質を有している
ことに着目している。従って、拡大演算の場合における
頂点Ｖの外角、および縮小演算の場合における頂点Ｖの
内角を、それぞれθとして演算してもよい。

【００５６】このようにして頂点Ｖの内角または外角θ
が演算されると、演算されたθの値に基づいて、頂点Ｖ
は、例えば以下の６つの種別Ｔ１〜Ｔ６に分類される
（ステップ３−７）。すなわち、拡大演算処理の場合に
おいて、図４（ａ）に示すように、頂点Ｖの内角θが、
０＜θ＜π／２の場合には、頂点Ｖは種別Ｔ１とされる
（ステップ３−８）。以下同様に、図４（ｂ）に示すよ
うに、θ＝π／２の場合には頂点Ｖは種別Ｔ２（ステッ
プ３−９）、図４（ｃ）に示すように、π／２＜θ＜π
の場合には頂点Ｖは種別Ｔ３（ステップ３−１０）、図
４（ｄ）に示すように、π＜θ＜３π／２の場合には頂
点Ｖは種別Ｔ４（ステップ３−１１）、図４（ｅ）に示
すように、θ＝３π／２の場合には頂点Ｖは種別Ｔ５
（ステップ３−１２）、図４（ｆ）に示すように、３π
／２＜θ＜２πの場合には種別Ｔ６（ステップ３−１
３）とそれぞれされる。

【００５７】頂点Ｖの内角θがπ／２および３π／２で
なく、従って、頂点Ｖは種別Ｔ２およびＴ５でない場
合、すなわち、頂点Ｖが種別Ｔ１、Ｔ３、Ｔ４、Ｔ６の
いずれかの場合には、ＯＲ演算図形Ｆに斜辺が含まれて
いるものとして、フラグＤがセット状態にされる（ステ
ップ３−１４〜ステップ３−１７）。

【００５８】このようにして、得られた頂点Ｖの内角
（あるいは外角）θの演算結果と、頂点Ｖの設定された
種別Ｔ１〜Ｔ６とが、それぞれ登録される（ステップ３
−１８および３−１９）。そして、全ての頂点の種別が
登録されたＯＲ演算図形Ｆが斜辺を含んでいるかどうか
が登録される（ステップ３−２０）。

【００５９】なお、ＯＲ演算図形における全ての頂点Ｖ
の種別がＴ２およびＴ５の場合（θ＝π／２およびθ＝
３π／２の場合）であって、しかも、全ての辺が斜辺で
構成されているような場合には、そのＯＲ演算図形は実
際には斜辺を含んでいるにもかかわらず、斜辺を含まな
い図形と判定される。しかし、このようなＯＲ演算図形
は、斜辺を含まない垂直辺および水平辺だけによって構
成された図形を回転させて傾斜状態になっているものと
して、斜辺を含まない図形として処理しても特に不都合
はない。

【００６０】このようにして、ＯＲ演算図形Ｆにおける
全ての頂点の種別が判定されて、斜辺の有無が設定され
ると、図１のステップ１−１０に示すように、ＯＲ演算
図形Ｆが斜辺を含んでいるかどうかを、フラグＤのセッ
ト状態およびリセット状態で判定される。そして、ＯＲ
演算図形Ｆが斜辺を含んでいない場合には、図１のステ
ップ１−１１〜１−１４により、また、斜辺を含んでい
る場合には、図１のステップ１−１５〜１−２１によ
り、それぞれ、ＯＲ演算図形Ｆの各頂点に対して仮図形
の頂点が生成される。

【００６１】ＯＲ演算図形Ｆが斜辺を含んでいない場合
には、ステップ１−１２に示すように、例えば頂点列の
ｍ番目の頂点をＶとするとともに、この頂点Ｖに隣接す
る各頂点を、それぞれＵおよびＷとして、頂点Ｖに対す
る仮図形の頂点を、図５のフローチャートに示すプロセ
スＡに基づいて生成する（ステップ１−１３）。

【００６２】図６（ａ）および（ｂ）は、ＯＲ演算図形
Ｆが斜辺を含んでいない場合に、頂点Ｖに対する仮図形
の頂点を生成するために実施されるプロセスＡの説明図
である。プロセスＡでは、拡大演算処理の場合には、図
６（ａ）に示すように、頂点Ｖを挟む２辺ＵＶおよびＶ
Ｗを、各辺ＵＶおよびＶＷの垂直方向に変更幅ｄだけそ
れぞれ図形の外部に平行移動される（ステップ５−
２）。縮小演算の場合には、図６（ｂ）に示すように、
図形の内部に平行移動される。

【００６３】この場合の詳細を、図７のフローチャート
に示す。すなわち、頂点Ｖを挟む２辺（ベクトル）ＵＶ
およびＶＷの一方の辺ＵＶを、変更幅（垂直距離）ｄだ
け、拡大演算の場合には図形の外部（縮小演算の場合に
は図形の内部）に平行移動させて、ベクトルＵ’Ｖ’と
する（図７のステップ７−１）。この場合の端点Ｕ’
は、辺ＵＶを平行移動した際のベクトルＵ’Ｖ’におけ
る頂点Ｕに対応する端点であり、端点Ｖ’は、辺ＵＶを
平行移動した際のベクトルＵ’Ｖ’における頂点Ｖに対
応する端点である。頂点Ｖを挟む２辺ＵＶおよびＶＷ
は、前述したように、それぞれベクトル化されているた
めに、図形の外部方向および内部方向は容易に識別され
る。

【００６４】次に、ＯＲ演算図形Ｆにおける頂点Ｖを挟
んだ他方の辺（ベクトル）ＶＷが、変更幅（垂直距離）
ｄだけ、図形の外部（または内部）に平行移動されて、
辺Ｖ" Ｗ’とされる（図７のステップ７−２）。この場
合の端点Ｖ" は、辺ＶＷを平行移動した際のベクトル
Ｖ’Ｗ’における頂点Ｖに対応する端点である。端点
Ｗ’は、辺ＶＷを平行移動した際のベクトルＶ”Ｗ’に
おける頂点Ｗに対応する端点である。

【００６５】このようにして、各辺（ベクトル）ＵＶお
よびＶＷが平行移動されると、平行移動後の各ベクトル
Ｕ’Ｖ’およびＶ" Ｗ’が、図６（ｂ）に示すように、
交差する場合には、その交点が、頂点Ｖに対する仮図形
の頂点Ｖ^"'として登録される。平行移動された各ベクト
ルＵ’Ｖ’およびＶ" Ｗ’が、図６（ａ）に示すよう
に、交差しない場合には、各ベクトルＵ’Ｖ’および
Ｖ" Ｗ’をそれぞれ延長した際の交点が、頂点Ｖに対す
る仮図形の頂点Ｖ^"'として登録される（図５のステップ
５−２）。

【００６６】ＯＲ演算図形Ｆにおける全ての頂点に対し
て、ベクトルの方向に沿った頂点列の順番に、このよう
な処理をすることにより、ＯＲ演算図形Ｆに対する全て
の頂点に対応した仮図形の頂点が順次設定される。そし
て、設定された仮図形の頂点は、ベクトルの方向に沿っ
て順番に登録されて、仮図形の頂点列とされる（ステッ
プ５−３）。

【００６７】これに対して、ＯＲ演算図形Ｆが斜辺を含
んでいる場合には、図１のステップ１−１５に進み、例
えば、頂点列のｍ番目の頂点をＶとし、この頂点Ｖに隣
接する各頂点を、それぞれＵおよびＷとする（ステップ
１−１６）。そして、ＯＲ演算図形Ｆの各頂点が、斜辺
の影響を受けるものかどうかの属性が判定される（ステ
ップ１−１７）。

【００６８】頂点Ｖが斜辺の影響を受けるものであるか
どうかの属性の判定は、図８に示すフローチャートに基
づいて実施される。すなわち、すでに登録された頂点Ｖ
の角度θがπよりも小さい種別Ｔ１またはＴ３のいずれ
かであれば（ステップ８−１）、拡大演算の場合におけ
る内角θが凸角（πより小）、あるいは、縮小演算の場
合における外角θが凹角（πより大）であるために、頂
点Ｖは、特に斜辺の影響を受けるものではなく、前述し
たプロセスＡ（ＯＲ演算図形Ｆが斜辺を含まない場合の
仮図形の頂点生成プロセス）によって仮図形の頂点を生
成するように、その頂点Ｖに対して「Ｐ−Ａ」の属性が
付与される（ステップ８−４）。

【００６９】これに対して、すでに登録された頂点Ｖの
角度θがπよりも大きい種別であり、しかも、頂点Ｕお
よびＷをそれぞれ挟む一対の辺のいずれかが斜辺である
場合には（ステップ８−２および８−３）、頂点Ｖは斜
辺の影響を受けるものとして、プロセスＡによる仮図形
の頂点の生成方法とは異なるプロセスＢによって仮図形
の頂点を生成すべきものとして、その頂点Ｖに「Ｐ−
Ｂ」の属性が付与される（ステップ８−５）。

【００７０】これは、例えば、図９に示すように、内角
θがπより大きい凹角になった頂点Ｖに隣接する各頂点
をＵおよびＷとすると、頂点Ｖを挟む一方の辺ＶＷが斜
辺であり、他の各頂点ＵおよびＷを挟む各辺ＸＵ、Ｕ
Ｖ、ＷＹがそれぞれ斜辺でない場合（水平辺または垂直
辺の場合）には、その斜辺ＶＷを構成する各頂点Ｖおよ
びＷは、斜辺の各端点として斜辺の影響を受けることに
なる。また、頂点Ｖに隣接する頂点Ｕは、斜辺ＶＷの端
点Ｖと辺ＵＶを共有することになるために斜辺の影響を
受けることになる。同様に、頂点Ｗに隣接する頂点Ｙ
も、斜辺ＶＷの端点Ｗと辺ＷＹを共有することになるた
めに、斜辺ＶＷの影響を受ける。従って、斜辺ＶＷの影
響を受けない頂点は、頂点ＵおよびＹに隣接する頂点Ｘ
およびＺになる。

【００７１】このように、斜辺ＶＷの一方の端点Ｖに対
して、その斜辺の影響は、頂点Ｖに隣接する頂点Ｕおよ
びＷをそれぞれ挟む各一対の辺ＸＵ、ＵＶ、ＶＷ、ＷＹ
にまで及ぶために、処理対象になっている頂点Ｖに隣接
する各頂点ＵおよびＷを挟む各一対の辺に斜辺があるか
どうかを判定して、斜辺がある場合には、頂点Ｖは斜辺
の影響を受けるものとして、プロセスＢによって、仮図
形の頂点を生成するように、属性「Ｐ−Ｂ」が付与され
る。プロセスＢは、図１１のフローチャートに示されて
おり、後述する。

【００７２】「Ｐ−Ａ」の属性が付与された頂点Ｖは、
拡大演算の場合には、図１０（ａ）に示すように、頂点
Ｖを挟む２つの辺（ベクトル）ＵＶおよびＶＷを、変更
幅（垂直距離）ｄだけ、外部に平行移動させて、ベクト
ルＵ’Ｖ’およびＶ’Ｗ’とし、それらのベクトルＵ’
Ｖ’およびＶ”Ｗ’の延長線の交点Ｖ^"'を頂点Ｖに対す
る仮図形の頂点とする。縮小演算の場合には、図１０
（ｂ）に示すように、頂点Ｖを挟む２辺ＵＶおよびＶＷ
を、変更幅（垂直距離）ｄだけ、内部に平行移動させ
て、ベクトルＵ’Ｖ’およびＶ”Ｗ’とし、それらの交
点Ｖ^"'を頂点Ｖに対する仮図形の頂点とする。

【００７３】これに対して、登録された頂角Ｖの種別
が、Ｔ４またはＴ６のいずれかになっている場合には、
拡大演算の場合における内角θが凹角（πより大）、あ
るいは縮小演算の場合における外角θが凸角（πより
小）になっており、さらに、その頂点Ｖが斜辺の影響を
受けるかどうかを、頂点Ｖに隣接する各頂点ＵおよびＷ
をそれぞれ挟む各一対の辺のいずれかが斜辺であるかど
うかによって判定する（ステップ８−２）。そして、頂
点ＵおよびＷをそれぞれ挟む各一対の辺がそれぞれ斜辺
でない場合には、頂点Ｖは斜辺の影響を受けないものと
して、「Ｐ−Ａ」の属性が付与され（ステップ８−
３）、頂点Ｖは、プロセスＡによって仮図形の頂点が生
成される。

【００７４】このようにして「Ｐ−Ａ」の属性が付与さ
れた頂点Ｖも、拡大演算の場合には、図１０（ａ）に示
すように、また、縮小演算の場合には、図１０（ｂ）に
示すように、頂点Ｖを挟む２辺ＵＶおよびＶＷを、変更
幅（垂直距離）ｄだけ、外部または内部に平行移動させ
て、ベクトルＵ’Ｖ’およびＶ”Ｗ’とし、それらの交
点Ｖ^"'または各ベクトルＵ’Ｖ’およびＶ”Ｗ’の延長
線の交点Ｖ^"'を頂点Ｖに対する仮図形の頂点とする。

【００７５】このようにして、ＯＲ演算図形Ｆの頂点Ｖ
の属性が付与されると、図１におけるフローチャートの
ステップ１−１８に示すように、頂点Ｖの属性が判定さ
れ、頂点Ｖの属性が「Ｐ−Ａ」の場合には、図５に示す
フローチャートに基づくプロセスＡによって、頂点Ｖに
対応する仮図形の頂点Ｖ^"'が生成される（ステップ１−
１９）。

【００７６】これに対して、ＯＲ演算図形Ｆの頂点Ｖの
属性が「Ｐ−Ｂ」の場合には、プロセスＡとは異なり、
斜辺の影響を受けるものとして、プロセスＢによって、
頂点Ｖに対する仮図形の３つの頂点が生成される（ステ
ップ１−２０）。

【００７７】図１１は、ＯＲ演算図形Ｆの頂点Ｖに対す
る仮図形の頂点を、プロセスＢによって生成する方法を
示すフローチャート、図１２はそのプロセスＢによる仮
図形の頂点の生成方法の説明図である。プロセスＢで
は、拡大演算する場合には、図１２（ａ）に示すよう
に、頂点Ｖを挟む２辺ＵＶおよびＶＷを、変更幅（垂直
距離）ｄだけ、ＯＲ演算図形Ｆの外部に平行移動して、
それぞれベクトルＵ’Ｖ’とベクトルＶ”Ｗ’とする
（図１１のステップ１１−１）。縮小演算する場合に
は、図１２（ｂ）に示すように、頂点Ｖを挟む２辺ＵＶ
およびＶＷを、それぞれ、変更幅（垂直距離）ｄだけ、
図形の内部に平行移動して、ベクトルＵ’Ｖ’およびベ
クトルＶ”Ｗ’とする。図形の全ての辺は、図形の内部
が右側になるようにベクトル化されているために、図形
の外部方向および内部方向は容易に識別することができ
る。

【００７８】このようにして、頂点Ｖに対して２つの端
点Ｖ’およびＶ”が得られるが、これらの端点Ｖ’およ
びＶ”が、仮図形の頂点としてそれぞれ登録される。こ
の場合、ＯＲ演算図形Ｆの頂点Ｖも仮図形の頂点として
登録される。仮図形の３つの頂点Ｖ、Ｖ’、Ｖ”は次の
ように順番に登録される。すなわち、仮図形の頂点の生
成が、ＯＲ演算図形におけるベクトル化された各辺のベ
クトルの方向に沿って順番に実施されているために、頂
点Ｕ−Ｖ−Ｗの順に処理され、頂点Ｕが、頂点Ｖの処理
に先立って処理されるとともに、頂点Ｗが、頂点Ｖの処
理後に処理されるようになっている。このために、辺Ｕ
Ｖを平行移動した際の頂点Ｖに対応する端点Ｖ’は、頂
点Ｕに対応する端点Ｕ’と頂点Ｖとの間に登録される。
辺ＶＷを平行移動した際の頂点Ｖに対応する端点Ｖ”
は、頂点Ｗに対応する端点Ｗ’と頂点Ｖとの間に登録さ
れる。従って、仮図形の頂点列としては、頂点Ｕ’の次
に頂点Ｖ’が登録され（ステップ１１−２）、次に頂点
Ｖが登録され（ステップ１１−３）、さらにその後に頂
点Ｖ”が登録される（ステップ１１−４）。従って、仮
図形の頂点としては、Ｕ’−Ｖ’−Ｖ−Ｖ”−Ｗ’の順
に登録される。

【００７９】このような仮図形の頂点列の登録は、入力
図形群ＳをＯＲ演算した際に得られるＯＲ演算図形Ｆが
複数の場合には、各ＯＲ演算図形Ｆ毎に仮図形が得られ
るように、それぞれのＯＲ演算図形Ｆに対して仮図形の
頂点列が生成される（図１（ｂ）のステップ１−２
２）。そして、全ての仮図形の頂点列を設定登録された
順に結ぶことにより、仮図形が生成される（ステップ１
−２３）。ＯＲ演算図形Ｆの数がＮ個の場合には、生成
される仮図形もＮ個になる。

【００８０】全ての仮図形が生成されると、全仮図形に
対してＯＲ演算される（ステップ１−２４）。そして、
ＯＲ演算されて得られた図形群が、リサイジング図形の
データーＳとして出力される（ステップ１−２５）。

【００８１】ＯＲ演算は、辺が交差も含むＮ個の仮図形
に対して、総頂点数をｎとすると、Ｏ（ｎｌｏｇｎ）の
計算速度で実施される。

【００８２】図２（ｃ）に示すＯＲ演算図形Ｆに対して
は、全ての頂点に対して、図１のフローチャートに基づ
いて仮図形の頂点が登録されると、図１３（ａ）に示す
１つの仮図形２１が生成される。この場合、ＯＲ演算図
形Ｆの頂点数は１８であったが、仮図形２１の頂点数は
２８になる。そして、図１３（ａ）に示す仮図形２１を
ＯＲ演算することにより、図１３（ｂ）に示すリサイジ
ング（拡大）図形２２が得られ、この図形が出力される
ことになる。

【００８３】本実施例では、頂点Ｖが斜辺に影響される
かどうかの属性を判定することにより、頂点Ｖに対応す
る仮図形の頂点を１つだけ生成するプロセスＡを実施す
べき「Ｐ−Ａ」と、対応する仮図形の頂点を３つ生成す
るプロセスＢを実施すべき「Ｐ−Ｂ」とに分類される
が、この属性の分類の条件判定は、各頂点毎に実施され
るだけであり、その後に実施されるＯＲ演算に要する計
算時間に比して高速で処理することができる。

【００８４】しかも、斜辺を含まない図形に対しては、
その頂点のいずれもが、１つの頂点に対して仮図形の頂
点が１つしか生成されない「Ｐ−Ａ」の属性に分類され
るために、仮図形の総頂点数が削減されて、その後のＯ
Ｒ演算処理も高速で実施することができる。

【００８５】なお、上記実施例では、ＯＲ演算図形Ｆが
斜辺を有している場合において、頂点Ｖの角度θがπよ
りも大きいときには（頂点の角度の種別がＴ４〜Ｔ
６）、頂点の属性の判定、すなわち、頂点Ｖが斜辺の影
響を受けるかどうかの判定を、図８に示すように、頂点
Ｖに隣接する各頂点ＵおよびＷを、それぞれ挟む一対の
辺のいずれかが斜辺であるかどうかによって実施するよ
うにしたが、例えば、その頂点Ｖに隣接する頂点Ｕおよ
びＷの角度（頂点ＵおよびＷの種別Ｔ１〜Ｔ６）に基づ
いて、頂点Ｖの属性を判断するようにしてもよい。

【００８６】図１４は、その場合のフローチャートを示
している。この場合には、頂点Ｖの属性を調べる際に、
頂点Ｖの種別がＴ１〜Ｔ３のいずれかであるか、Ｔ４〜
Ｔ６のいずれかであるかを調べ（ステップ１４−１）、
頂点Ｖの種別がＴ１〜Ｔ３の場合（頂点の角度θ＜π）
には、図８に示す例と同様に、頂点Ｖは、斜辺の影響を
受けないものとして、プロセスＡにより処理すべきであ
る「Ｐ−Ａ」の属性とされる（ステップ１４−４）。す
なわち、拡大演算の場合における頂点Ｖの内角θがπよ
りも小さな凸角、または、縮小演算の場合における頂点
Ｖの外角θがπよりも大きな凹角であれば、「Ｐ−Ａ」
の属性とされて、頂点Ｖに対して、仮図形の１つの頂点
が生成される。

【００８７】これに対して、頂点Ｖの種別がＴ４〜Ｔ６
の場合（頂点Ｖの角度θ＞π）には、頂点Ｖに隣接する
頂点ＵおよびＷの種別がＴ１〜Ｔ３であるか、Ｔ４〜Ｔ
６であるかをそれぞれ調べる（ステップ１４−２および
１４−３）。そして、頂点Ｖに隣接する頂点ＵおよびＷ
のいずれもが、種別Ｔ１〜Ｔ３になっている場合、すな
わち、頂点ＵおよびＷの角度が、いずれもπよりも小さ
い場合にのみ、頂点Ｖは、斜辺に影響されるものとし
て、プロセスＢにより処理すべき「Ｐ−Ｂ」の属性が付
与される（ステップ１４−５）。頂点Ｖに隣接する頂点
ＵおよびＷのいずれかの種別がＴ４〜Ｔ６の場合、すな
わち、頂点ＵおよびＷの角度θがπよりも大きい場合に
は、頂点Ｖは、斜辺の影響を受けないものとして、プロ
セスＡによって処理すべき「Ｐ−Ａ」の属性が付与され
る（ステップ１４−４）。

【００８８】本実施例の場合には、図２（ｃ）に示すＯ
Ｒ演算図形Ｆに対して、図１５に示すリサイジング（拡
大）仮図形２３が生成される。この場合には、仮図形２
３の頂点数は３０になる。そして、この仮図形２３をＯ
Ｒ演算することにより、図１３（ｂ）に示すリサイジン
グ（拡大）図形２２が得られる。

【００８９】図１６は、頂点Ｖの属性を調べる方法のさ
らに他の実施例を示すフローチャートである。本実施例
では、頂点Ｖが斜辺の影響を受けるかどうかの属性を、
頂点Ｖの角度θと、頂点Ｖに隣接する各頂点ＵおよびＷ
の角度と、さらに、頂点Ｖと隣接する各頂点ＵおよびＷ
の角度それぞれとの和とに基づいて判定するようになっ
ている。

【００９０】すなわち、頂点Ｖの角度の種別がＴ１〜Ｔ
３の場合（頂点の角度θ＜π）には（ステップ１６−
１）、頂点Ｖは斜辺の影響を受けないものとして、前記
各実施例と同様に、斜辺の影響を受けないものとして、
「Ｐ−Ａ」の属性とされる（ステップ１６−６）。

【００９１】これに対して、頂点Ｖの角度θの種別がＴ
４（π＜θ＜３π／２）の場合には、頂点Ｖに隣接する
各頂点ＵおよびＷのいずれもが種別Ｔ３（π／２＜θ＜
π）でなければ（ステップ１６−２および１６−４）、
頂点Ｖの斜辺の影響を受けないものとして「Ｐ−Ａ」の
属性とされる（ステップ１６−６）。

【００９２】しかしながら、頂点Ｖの角度θの種別がＴ
４（π＜θ＜３π／２）であって、頂点Ｖに隣接する各
頂点ＵおよびＷのいずれかが種別Ｔ３（π／２＜θ＜
π）である場合には、種別Ｔ３の頂点ＵまたはＷの角度
と頂点Ｖの角度との和が２πよりも大きいときにのみ、
頂点Ｖは斜辺の影響を受けるものとして、「Ｐ−Ｂ」の
属性とされる（ステップ１６−７）。頂点Ｖの角度の種
別がＴ４の場合には、このような条件以外では、頂点Ｖ
の属性は「Ｐ−Ａ」とされる。

【００９３】これにより、ＯＲ演算図形を拡大演算する
場合には、頂点Ｖの内角θが、π＜θ＜３π／２の凹角
であり、しかも、隣接する頂点ＵまたはＷのいずれかの
内角θ’が、π／２＜θ’＜πの凸角であって、さら
に、（θ＋θ’）＞２πであるときに限り、頂点Ｖの属
性として「Ｐ−Ｂ」が付与される。従って、ＯＲ演算図
形に４５°または１３５°の斜辺だけが含まれている場
合には、この条件を満足する頂点Ｖと頂点ＵまたはＷと
の組み合わせは存在せず、この場合には、ＯＲ演算図形
の各頂点は、Ｐ−Ａの属性が付与されて、各頂点に対し
て仮図形の頂点が１つずつ生成される。

【００９４】頂点Ｖの角度の種別がＴ５（θ＝３π／
２）の場合には、図１６（ｂ）に示すように、頂点Ｖに
隣接する各頂点ＵおよびＷのいずれかが種別Ｔ３（π／
２＜θ＜π）であれば（ステップ１６−８および１６−
９）、頂点Ｖの属性は、「Ｐ−Ｂ」とされる（ステップ
１６−７）。頂点Ｖの角度の種別がＴ５（θ＝３π／
２）の場合では、このような条件になければ、頂点Ｖの
属性は「Ｐ−Ａ」とされる（ステップ１６−６）。

【００９５】これにより、ＯＲ演算図形を拡大演算する
場合には、頂点Ｖの内角θが、θ＝３π／２の凹角であ
り、隣接する頂点ＵまたはＷのいずれかの内角θ’が、
π／２＜θ’＜πの凸角であるときに限り、頂点Ｖは、
斜辺の影響を受けるものとして、「Ｐ−Ｂ」の属性とさ
れる。従って、ＯＲ演算図形に４５°または１３５°の
斜辺だけが含まれている場合には、頂点Ｖの角度θが２
７０°であって、頂点ＵまたはＷの角度θ’が１３５°
の場合にのみ、その頂点Ｖは斜辺の影響をうけるものと
して、プロセスＢにより、仮図形の３つの頂点が生成さ
れる。

【００９６】頂点Ｖの角度の種別がＴ６（３π／２＜θ
＜２π）の場合には、図１６（ｃ）に示すように、頂点
Ｖに隣接する各頂点ＵおよびＷのいずれかが種別Ｔ２
（θ＝π／２）またはＴ３（π／２＜θ＜π）であれば
（ステップ１６−１０および１６−１２）、頂点Ｖの属
性は、「Ｐ−Ｂ」とされる（ステップ１６−７）。ま
た、頂点Ｖに隣接する各頂点ＵおよびＷのいずれかが種
別Ｔ１（０＜θ＜π／２）であれば、種別Ｔ１の頂点Ｕ
またはＷの角度と頂点Ｖの角度との和が２πよりも大き
いと（ステップ１６−１１および１６−１３）、頂点Ｖ
の属性は、「Ｐ−Ｂ」とされる（ステップ１６−７）。
頂点Ｖの角度の種別がＴ６の場合（３π／２＜θ＜２
π）では、このような条件になっていないと、頂点Ｖ
は、斜辺の影響を受けないものとして、「Ｐ−Ａ」の属
性とされる（ステップ１６−６）。

【００９７】これにより、ＯＲ演算図形を拡大演算する
場合には、頂点Ｖの内角θが、３π／２＜θ＜２πの凹
角であり、しかも、隣接する頂点ＵまたはＷのいずれか
の内角θ’が、π／２≦θ’＜πの凸角であるか、もし
くは、０２＜θ’＜π／２の凸角で（θ＋θ’）＞２π
であるときに限り、頂点Ｖは斜辺の影響を受けるものと
して「Ｐ−Ｂ」の属性が付与される。従って、ＯＲ演算
図形に４５°または１３５°の斜辺だけが含まれている
場合には、頂点Ｖの角度θ＝３１５°、頂点ＵまたはＷ
の角度θ’＝９０°のとき、または、頂点Ｖの角度θ＝
３１５°、頂点ＵまたはＷの角度θ’＝１３５°のとき
にのみ、斜辺の影響を受けるものとして、プロセスＢに
よって３つの仮図形の頂点が生成される。

【００９８】本実施例では、頂点Ｖの属性は、対応する
仮図形の頂点を１つだけ生成するプロセスＡを実施すべ
き「Ｐ−Ａ」と、対応する仮図形の頂点を３つ生成する
プロセスＢを実施すべき「Ｐ−Ｂ」とに分類されるが、
この属性の分類の条件判定は、各頂点毎に実施されるだ
けであり、その後に実施されるＯＲ演算に要する計算時
間に比して高速で処理することができる。

【００９９】しかも、斜辺を含まない図形の場合には、
その頂点のいずれもが、１つの頂点に対して仮図形の頂
点が１つしか生成されない「Ｐ−Ａ」の属性に分類され
る。また、垂直辺および水平辺以外に、水平辺に対して
４５°および１３５°の斜辺しか含まない図形に対して
も、連続する２つの頂点の角度（拡大演算の場合には内
角の角度、縮小演算の場合には外角の角度）θおよび
θ’の組み合わせは、θ＝２７０°およびθ’＝１３５
°と、θ＝３１５°およびθ’＝９０°と、θ＝３１５
°およびθ’＝１３５°の３通りの場合に限られ、角度
θとなった頂点のみが、仮図形の頂点として３つが生成
されるように「Ｐ−Ｂ」に分類され、他の頂点は「Ｐ−
Ａ」に分類される。

【０１００】従って、本実施例では、仮図形の頂点数
が、ＯＲ演算図形の頂点に対して３つの仮図形の頂点が
生成されるプロセスＢが適用される属性「Ｐ−Ｂ」にな
ることはごくまれである。その結果、仮図形の頂点数を
著しく削減することができ、仮図形のＯＲ演算処理に要
する時間を著しく短縮することが可能になる。

【０１０１】本実施例の場合には、図２（ｃ）に示すＯ
Ｒ演算図形Ｆに対して、図１７に示すリサイジング（拡
大）仮図形２４が生成される。この場合には、入力図形
Ｆの総頂点数１８に対して、仮図形２４の頂点数は２２
になり、４つの頂点が増加しているにすぎない。そし
て、この仮図形２４をＯＲ演算することにより、図１３
（ｂ）に示すリサイジング（拡大）図形２２が得られ
る。

【０１０２】従って、折れ曲がりの多い配線パターンの
ような複雑な図形において、斜辺が局所的に使用されて
いるような場合には、本実施例によって、３つの仮図形
の頂点を生成するプロセスＢの適用範囲を限定すること
ができ、高速処理が可能になる。

【０１０３】

【発明の効果】本発明のマスクパターンのリサイジング
方法は、このように、入力図形に対して斜辺が含まれて
いるかどうかを判定し、さらに、斜辺が含まれている場
合には、入力図形の各頂点が斜辺の影響を受けるかどう
かを判定して、頂点が斜辺の影響を受ける場合にのみ、
その頂点に対して３つの仮図形の頂点を生成するように
している。従って、入力図形に斜辺が含まれていても、
斜辺の影響を受けない頂点に対しては、仮図形の頂点は
１つしか生成されず、仮図形の総頂点数を削減すること
ができて、その後のＯＲ演算処理を高速化することがで
きる。

【０１０４】頂点が斜辺の影響を受けるかどうかは、そ
の頂点に隣接する各頂点をそれぞれ挟む各一対の辺によ
って判定することができるが、その頂点の角度とその頂
点に隣接する各頂点の角度とに基づいて、さらに、その
頂点の角度とその頂点に隣接する各頂点の角度と、隣接
する頂点のいずれか一方ともとの頂点の角度との和に基
づいて判定することにより、３つの仮図形の頂点を生成
するプロセスが適用される範囲が制限され、仮図形の総
頂点数がより一層、削減されて、その後のＯＲ演算処理
を高速化することができる。

【図面の簡単な説明】

【図１】（ａ）および（ｂ）は、それぞれ、本発明のマ
スクパターンのリサイジング方法の手順の一例を示すフ
ローチャートである。

【図２】（ａ）は、ＬＳＩのマスクパターンの一例、
（ｂ）はそのマスクパターンのＣＡＤシステムに入力さ
れる入力図形、（ｃ）はその入力図形をＯＲ演算して得
られたＯＲ演算図形である。

【図３】ＯＲ演算図形の全ての頂点の角度の種別を判定
するため方法の手順の一例を示すフローチャートであ
る。

【図４】（ａ）〜（ｆ）は、それぞれ、ＯＲ演算図形の
頂点の角度の種別Ｔ１〜Ｔ６の説明図である。

【図５】ＯＲ演算図形が斜辺を含んでいない場合のその
ＯＲ演算図形の頂点に対する仮図形の頂点の生成方法で
あるプロセスＡの手順を示すフローチャートである。

【図６】（ａ）および（ｂ）は、それぞれ、プロセスＡ
による仮図形の頂点の生成方法の説明図である。

【図７】ＯＲ演算図形の各辺を平行移動する際の手順の
一例を示すフローチャートである。

【図８】ＯＲ演算図形の各頂点が、斜辺の影響を受ける
ものかどうかの属性を判定する手順の一例を示すフロー
チャートである。

【図９】ＯＲ演算図形における頂点が斜辺の影響を受け
る場合の説明図である。

【図１０】（ａ）および（ｄ）は、それぞれ、斜辺を含
むＯＲ演算図形における斜辺の影響を受けない頂点に対
する仮図形の頂点の生成方法の説明図、（ｂ）および
（ｃ）は、それぞれ、斜辺を含むＯＲ演算図形における
斜辺の影響を受ける頂点に対する仮図形の頂点の生成方
法の説明図である。

【図１１】ＯＲ演算図形の頂点に対する仮図形の頂点
を、プロセスＢによって生成する方法の手順の一例を示
すフローチャートである。

【図１２】（ａ）および（ｂ）は、それぞれ、そのプロ
セスＢによる仮図形の頂点の生成方法の説明図である。

【図１３】（ａ）は、図２（ｃ）に示すＯＲ演算図形を
図１のフローチャートに基づいて生成された仮図形、
（ｂ）はその仮図形をＯＲ演算して得られる拡大演算図
形である。

【図１４】ＯＲ演算図形の各頂点が、斜辺の影響を受け
るものかどうかの属性を判定する手順の他の例を示すフ
ローチャートである。

【図１５】図２（ｃ）に示すＯＲ演算図形に基づいて生
成された仮図形である。

【図１６】（ａ）〜（ｃ）は、それぞれ、ＯＲ演算図形
の各頂点が、斜辺の影響を受けるものかどうかの属性を
判定する手順の、さらに他の例を示すフローチャートで
ある。

【図１７】図２（ｃ）に示すＯＲ演算図形に基づいて生
成された仮図形である。

【図１８】（ａ）はマスクパターンの入力図形の一例、
（ｂ）はその拡大図形、（ｃ）はその相似図形である。

【図１９】（ａ）〜（ｇ）は、それぞれ、入力図形の拡
大演算処理または縮小演算処理の説明図である。

【図２０】（ａ）は、マスクパターンの最小間隔を検証
する際の入力図形の一例、（ｂ）は、その入力図形の拡
大図形、（ｃ）は、最小間隔を満足していない部分の説
明図である。

【図２１】（ａ）は、マスクパターンの最小幅を検証す
る際の入力図形の一例、（ｂ）は、その入力図形の縮小
図形、（ｃ）は、最小幅を満足していない部分の説明図
である。

【図２２】（ａ）は、配線可能領域を抽出する際の入力
図形の一例、（ｂ）は、その入力図形の拡大図形、
（ｃ）は、配線可能領域を満足する部分の説明図であ
る。

【図２３】（ａ）は、ノッチを除去する際の入力図形の
一例、（ｂ）は、その入力図形の拡大図形、（ｃ）は、
その拡大図形の縮小図形である。

【図２４】（ａ）および（ｂ）は、それぞれ、ＯＲ演算
の説明図である。

【図２５】（ａ）および（ｂ）は、それぞれ、従来法２
によっては正確な拡大図形が得られない入力図形であ
る。

【図２６】（ａ）および（ｂ）は、それぞれ、従来法３
の手順を示すフローチャートである。

【図２７】（ａ）〜（ｃ）は、それぞれ、ＯＲ演算が必
要であることの説明図である。

【図２８】（ａ）はマスクパターンの入力図形の一例、
（ｂ）は従来法３によりその入力図形の拡大演算におけ
る仮図形である。

【図２９】従来法４の手順を示すフローチャートであ
る。

【図３０】（ａ）および（ｂ）は、それぞれ、従来法４
によって生成された誤った拡大図形である。

【符号の説明】

１０ マスクパターン １１ 斜辺部 １２ 水平部 １３ 矩形部 １４ 垂直部 １５ 水平部 １６ 矩形部 １１’ 傾斜入力図形 １２’ 水平入力図形 １３’ 矩形入力図形 １４’ 垂直入力図形 １５’ 水平入力図形 １６’ 矩形入力図形 Ｆ ＯＲ演算図形

Claims (4)

【特許請求の範囲】
1. 【請求項１】 ＣＡＤシステムによって、マスクパター
   ンに対応する入力図形の各辺を、その入力図形の外部ま
   たは内部に平行移動させて拡大図形または縮小図形を得
   るマスクパターンのリサイジング方法であって、 前記入力図形が斜辺を含むかどうかを判定する工程と、 その入力図形が斜辺を含んでいる場合には、その入力図
   形の頂点毎に、その頂点が斜辺の影響を受けるかどうか
   を判定する工程と、 入力図形の頂点が斜辺の影響を受ける場合に、その頂点
   を挟む入力図形の一対の辺を、図形の内部または外部に
   平行移動した際のその頂点に対応するそれぞれの端点
   を、その頂点とともに仮図形の頂点とする工程と、 入力図形の頂点が斜辺の影響を受けない場合には、その
   頂点を挟む入力図形の一対の辺を図形の外部または内部
   にそれぞれ平行移動し、平行移動された各辺の交点また
   は平行移動された各辺の延長線の交点を、入力図形の頂
   点に対する仮図形の頂点とする工程と、 得られた仮図形の各頂点を結んで仮図形を生成する工程
   と、 生成された仮図形をＯＲ演算する工程と、 を包含することを特徴とするマスクパターンのリサイジ
   ング方法。
2. 【請求項２】 入力図形の各頂点が、斜辺の影響を受け
   るかどうかを、その頂点に隣接する各頂点を挟む一対の
   辺に斜辺が含まれているかどうかによって判定すること
   を特徴とする請求項１に記載のマスクパターンのリサイ
   ジング方法。
3. 【請求項３】 入力図形の各頂点が、斜辺の影響を受け
   るかどうかを、その頂点に隣接する各頂点の角度に基づ
   いて判定することを特徴とする請求項１に記載のマスク
   パターンのリサイジング方法。
4. 【請求項４】 入力図形の各頂点が、斜辺の影響を受け
   るかどうかを、その頂点の角度と、その頂点に隣接する
   各頂点の角度と、その頂点の角度と隣接する各頂点それ
   ぞれの角度との和とに基づいて判定することを特徴とす
   る請求項１に記載のマスクパターンのリサイジング方
   法。