(57)【特許請求の範囲】
【請求項１】
フォトマスク上の歪みを補正するためにモデルベース・オプティカル・プロクシミティ・コレクション（モデルベースＯＰＣ）を実行する方法であって、
インタラクション・ディスタンスを有するリージョン・オブ・インタレスト（ＲＯＩ）を設けることと、
前記ＲＯＩ内で少なくとも１つの有限幾何形状を突き止めることと、
前記少なくとも１つの有限幾何形状の少なくとも１つの稜線にまたがる少なくとも１つのカット・ラインを生成することと、
オプティカル・プロクシミティを補正するために、前記少なくとも１つの有限幾何形状の前記少なくとも１つの側稜にまたがる前記少なくとも１つのカット・ラインの位置に基づいて、そのインタラクション・ディスタンスを超えて前記ＲＯＩを拡張することと、    オプティカル・プロクシミティを補正するために、前記ＲＯＩ内の畳み込みの合計の単一の畳み込み寄与検索ステップで前記少なくとも１つのカット・ラインにまたがる複数のサンプル点の事前に計算された畳み込み寄与を同時に検索することと、
前記補正されたオプティカル・プロクシミティを使用してフォトマスク上の歪みを補正することとを備え、
そのインタラクション・ディスタンスを超えて前記ＲＯＩを拡張する前記ステップが、さらに、元々は前記ＲＯＩの境界の外にある追加の有機幾何形状または元々は前記ＲＯＩの前記境界の中または上にあるすべての有機幾何形状の追加部分を取り込むことと、
を含むモデルベース・オプティカル・プロクシミティ・コレクションを実行する方法。
【請求項２】
前記有限幾何形状が、ポリゴンを含む、請求項１に記載の方法。
【請求項３】
前記ポリゴンが、規則的、不規則、凸、凹、規則的な凸、規則的な凹、不規則な凸、および不規則な凹からなる群から選択される、請求項２に記載の方法。
【請求項４】
前記少なくとも１つのカット・ラインが、前記ＲＯＩ内の頂点の組を表す複数のサンプル点を含む、請求項１に記載の方法。
【請求項５】
前記側稜の前記位置にまたがって存在する前記少なくとも１つのカット・ラインが、前記カット・ラインと前記側稜との間の交差の第１の側にある第１個数の前記複数のサンプル点、および前記交差の第２の側にある第２個数の前記複数のサンプル点を含む、請求項４に記載の方法。
【請求項６】
前記カット・ラインの前記複数のサンプル点の前記第１個数および第２個数が、同一である、請求項５に記載の方法。
【請求項７】
前記カット・ラインの前記複数のサンプル点の前記第１個数および第２個数が、異なる、請求項５に記載の方法。
【請求項８】
前記少なくとも１つのカット・ラインの前記位置に基づいてそのインタラクション・ディスタンスを超えて前記ＲＯＩを拡張する前記ステップが、前記少なくとも１つのカット・ラインが、水平カット・ライン、垂直カット・ライン、および４５°カット・ラインからなる群から選択されるかどうかを判定することを含む、請求項１に記載の方法。
【請求項９】
前記カット・ラインが、前記水平カット・ラインを含み、前記方法が、前記ＲＯＩを、水平に１次元方向で前記ＲＯＩの対向する水平側面で拡張するステップを含む、請求項８に記載の方法。
【請求項１０】
前記カット・ラインが、前記垂直カット・ラインを含み、前記方法が、前記ＲＯＩを、垂直に１次元方向で前記ＲＯＩの対向する垂直側面で拡張するステップを含む、請求項８に記載の方法。
【請求項１１】
前記カット・ラインが、前記４５°カット・ラインを含み、前記方法が、前記ＲＯＩを、２次元方向で前記ＲＯＩのすべての水平側面および垂直側面で拡張するステップを含む、請求項８に記載の方法。
【請求項１２】
前記少なくとも１つの有限幾何形状の前記少なくとも１つの側稜にまたがる複数のカット・ラインについて前記ステップを繰り返すことと、前記複数のカット・ラインの複数の位置に基づいて前記ＲＯＩをそのインタラクション・ディスタンスを超えて拡張することとをさらに含む、請求項１に記載の方法。
【請求項１３】
フォトマスク上の歪みを補正するためにモデルベースＯＰＣを実行する方法であって、
インタラクション・ディスタンスを有する第１リージョン・オブ・インタレスト（ＲＯＩ）を設けることと、
前記第１ＲＯＩ内で少なくとも１つのポリゴンを突き止めることと、
前記少なくとも１つのポリゴンの少なくとも１つの側稜にまたがる少なくとも１つのカット・ラインを突き止めることであって、前記少なくとも１つのカット・ラインが、前記第１ＲＯＩ内の頂点の組を表す複数のサンプル点を含む、突き止めることと、
前記少なくとも１つのポリゴンの前記少なくとも１つの側稜にまたがる前記少なくとも１つのカット・ラインの角度位置を判定することと、
前記少なくとも１つのカット・ラインと前記少なくとも１つの側稜との間の交差の対向する側にある前記少なくとも１つのカット・ラインの第１部分および第２部分を判定することと、
前記少なくとも１つのカット・ラインの前記角度位置ならびに前記交差の前記対向する側にある前記少なくとも１つのカット・ラインの前記第１部分および第２部分に基づいて、そのインタラクション・ディスタンスを超えて前記第１ＲＯＩを拡張することによって第２ＲＯＩを設けることであって、前記第２ＲＯＩが、オプティカル・プロクシミティの補正に使用される、設けることと、  
オプティカル・プロクシミティを補正するために、前記第１ＲＯＩ内の頂点の前記組の畳み込みの合計の単一の畳み込み寄与検索ステップで前記少なくとも１つのカット・ラインにまたがる複数のサンプル点の事前に計算された畳み込み寄与を同時に検索することと、
前記第２ＲＯＩを使用してオプティカル・プロクシミティの補正をすることと、及び、
前記補正されたオプティカル・プロクシミティを使用してフォトマスク上の歪みを補正することとを備え、
そのインタラクション・ディスタンスを超えて前記第１ＲＯＩを拡張する前記ステップが、さらに、元々は前記第１ＲＯＩの境界の外にある追加ポリゴンまたは元々は前記第１ＲＯＩの前記境界の中または上にあるすべてのポリゴンの追加部分を取り込むこと、
を含むモデルベース・オプティカル・プロクシミティ・コレクションを実行する方法。
【請求項１４】
前記少なくとも１つのポリゴンの前記少なくとも１つの側稜にまたがる複数のカット・ラインを前記第１ＲＯＩ内で突き止めることと、複数の新しいリージョン・オブ・インタレストを生成するために、前記複数のカット・ラインに基づいて、そのインタラクション・ディスタンスを超えて複数回前記第１ＲＯＩを拡張することによって前記第２ＲＯＩを設けることとをさらに含む、請求項１３に記載の方法。
【請求項１５】
前記交差の前記第１側にある前記少なくとも１つのカット・ラインの前記第１部分が、前記複数のサンプル点からの第１個数のサンプル点に対応し、前記交差の前記第２側にある前記少なくとも１つのカット・ラインの前記第２部分が、前記複数のサンプル点からの第２個数のサンプル点に対応する、請求項１３に記載の方法。
【請求項１６】
前記第２ＲＯＩが、前記第１ＲＯＩの少なくとも２つの対向する側面で等しい量だけ前記第１ＲＯＩを拡張することによって設けられるように、前記カット・ラインの前記複数のサンプル点の前記第１個数および第２個数が等しい、請求項１５に記載の方法。
【請求項１７】
前記第２ＲＯＩが、前記第１ＲＯＩの少なくとも２つの対向する側面で等しくない量だけ前記第１ＲＯＩを拡張することによって設けられるように、前記カット・ラインの前記複数のサンプル点の前記第１個数および第２個数が等しくない、請求項１５に記載の方法。
【請求項１８】
前記少なくとも１つのポリゴンの前記少なくとも１つの側稜にまたがる前記少なくとも１つのカット・ラインの前記角度位置が、水平カット・ライン、垂直カット・ライン、および４５°カット・ラインからなる群から選択される、請求項１３に記載の方法。
【請求項１９】
前記カット・ラインが、前記水平カット・ラインを含み、前記方法が、前記第１ＲＯＩを、水平に１次元方向で前記第１ＲＯＩの対向する水平側面で拡張することによって前記第２ＲＯＩを設けるステップを含む、請求項１８に記載の方法。
【請求項２０】
前記第１ＲＯＩが、前記第１ＲＯＩの前記対向する水平側面で等しい量または等しくない量だけ拡張される、請求項１９に記載の方法。
【請求項２１】
前記カット・ラインが、前記垂直カット・ラインを含み、前記方法が、前記第１ＲＯＩを、垂直に１次元方向で前記第１ＲＯＩの対向する垂直側面で拡張することによって前記第２ＲＯＩを設けるステップを含む、請求項１８に記載の方法。
【請求項２２】
前記第１ＲＯＩが、前記第１ＲＯＩの前記対向する垂直側面で等しい量または等しくない量だけ拡張される、請求項２１に記載の方法。
【請求項２３】
前記カット・ラインが、前記４５°カット・ラインを含み、前記方法が、前記第１ＲＯＩを、２次元方向で前記第１ＲＯＩのすべての水平側面および垂直側面で拡張することによって前記第２ＲＯＩを設けるステップを含む、請求項１８に記載の方法。
【請求項２４】
前記第１ＲＯＩが前記第１ＲＯＩのすべての側面で拡張されるように、前記第１ＲＯＩが、前記第１ＲＯＩの対向する辺の第１組で第１関数（ｄ１）（ｃｏｓ（π／４））だけ拡張され、前記第１ＲＯＩの対向する辺の第２組で第１関数（ｄ２）（ｃｏｓ（π／４））だけ拡張される、請求項２３に記載の方法。
【請求項２５】
前記第１ＲＯＩが、対向する辺の第２組と比較して、対向する辺の第１組で等しい量または等しくない量で拡張される、請求項２４に記載の方法。
【請求項２６】
フォトマスク上の歪みを補正するためにモデルベース・オプティカル・プロクシミティ・コレクション（モデルベースＯＰＣ）を実行する方法ステップを実行するためプログラムであって、
インタラクション・ディスタンスを有するリージョン・オブ・インタレスト（ＲＯＩ）を設けることと、
前記ＲＯＩ内で少なくとも１つの有限幾何形状を突き止めることと、
前記少なくとも１つの有限幾何形状の少なくとも１つの稜線にまたがる少なくとも１つのカット・ラインを生成することと、
オプティカル・プロクシミティを補正するために、前記少なくとも１つの有限幾何形状の前記少なくとも１つの側稜にまたがる前記少なくとも１つのカット・ラインの位置に基づいて、そのインタラクション・ディスタンスを超えて前記ＲＯＩを拡張することと、
オプティカル・プロクシミティを補正するために、前記ＲＯＩ内の畳み込みの合計の単一の畳み込み寄与検索ステップで前記少なくとも１つのカット・ラインにまたがる複数のサンプル点の事前に計算された畳み込み寄与を同時に検索することと、
前記補正されたオプティカル・プロクシミティを使用してフォトマスク上の歪みを補正することとを備え、
そのインタラクション・ディスタンスを超えて前記ＲＯＩを拡張する前記ステップが、さらに、元々は前記ＲＯＩの境界の外にある追加の有機幾何形状または元々は前記ＲＯＩの前記境界の中または上にあるすべての有機幾何形状の追加部分を取り込むことと、
をコンピュータに実行させるプログラム。
【請求項２７】
フォトマスク上の歪みを補正するためにモデルベース・オプティカル・プロクシミティ・コレクション（モデルベースＯＰＣ）を実行する方法ステップを実行するためプログラムであって、
インタラクション・ディスタンスを有する第１リージョン・オブ・インタレスト（ＲＯＩ）を設けることと、
前記第１ＲＯＩ内で少なくとも１つのポリゴンを突き止めることと、
前記少なくとも１つのポリゴンの少なくとも１つの側稜にまたがる少なくとも１つのカット・ラインを突き止めることであって、前記少なくとも１つのカット・ラインが、前記第１ＲＯＩ内の頂点の組を表す複数のサンプル点を含む、突き止めることと、
前記少なくとも１つのポリゴンの前記少なくとも１つの側稜にまたがる前記少なくとも１つのカット・ラインの角度位置を判定することと、
前記少なくとも１つのカット・ラインと前記少なくとも１つの側稜との間の交差の対向する側にある前記少なくとも１つのカット・ラインの第１部分および第２部分を判定することと、
前記少なくとも１つのカット・ラインの前記角度位置ならびに前記交差の前記対向する側にある前記少なくとも１つのカット・ラインの前記第１部分および第２部分に基づいて、そのインタラクション・ディスタンスを超えて前記第１ＲＯＩを拡張することによって第２ＲＯＩを設けることであって、前記第２ＲＯＩが、オプティカル・プロクシミティの補正に使用される、設けることと、
オプティカル・プロクシミティを補正するために、前記第１ＲＯＩ内の頂点の前記組の畳み込みの合計の単一の畳み込み寄与検索ステップで前記少なくとも１つのカット・ラインにまたがる複数のサンプル点の事前に計算された畳み込み寄与を同時に検索することと、
前記第２ＲＯＩを使用してオプティカル・プロクシミティの補正をすることと、及び、前記補正されたオプティカル・プロクシミティを使用してフォトマスク上の歪みの補正することとを備え、
そのインタラクション・ディスタンスを超えて前記第１ＲＯＩを拡張する前記ステップが、さらに、元々は前記第１ＲＯＩの境界の外にある追加ポリゴンまたは元々は前記第１ＲＯＩの前記境界の中または上にあるすべてのポリゴンの追加部分を取り込むこと、
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的には光リソグラフィの分野に関し、具体的には、インタラクション・ディスタンス（interaction distance、ＩＤ）を超えてリージョン・オブ・インタレスト（Region of Interest、ＲＯＩ）を拡張して、ＲＯＩ内のポリゴンの完全な畳み込みのためにそのようなポリゴンの頂点を突き止め、畳み込みを合計するのに必要な時間を減らす、モデルベース・オプティカル・プロクシミティ・コレクション（OpticalProximity Correction、ＯＰＣ）の方法に関する。
【背景技術】
【０００２】
半導体デバイスの製造では、光マイクロリソグラフィ処理が、一般に、所望の回路パターンを半導体ウェハ上で複製することを必要とする。この所望の回路パターンは、フォトマスクと称するテンプレート上の不透明領域および透明領域として表され、フォトマスクは、露光システムを介するオプティカル・イメージング（optical imaging）によって、フォトレジストをコーティングされたウェハに投影される。
【０００３】
半導体製造での光リソグラフィを分析し、訂正する貴重なツールが、エリアル・イメージ・シミュレータ（aerial image simulator）である。エリアル・イメージ・シミュレータは、光学投影系によって生成される画像を計算し、エリアル・イメージのモデリングは、半導体製造の非常に重要な構成要素である。しかし、現在のリソグラフィ・ツールでは、部分的にコヒーレントな照明が使用されるので、そのようなモデル化は、基本的なパターンを除くすべてについて計算集中型である。マスクによって作られるエリアル・イメージすなわち、光学投影系の結像面での光強度は、開発されたフォトレジスト構造が所望のマスク設計をどれほどよく複製するかを左右する、マイクロリソグラフィで非常に重要な品質である。
【０００４】
ＯＰＣソフトウェアでは、画像強度が、通常は、プロセスの物理的特性を記述する特定のカーネル関数を有する双一次変換によって計算される。これは、ホプキンの積分に対応する光カーネルまたはレジスト効果を含む複合カーネルによって達成することができる。たとえば、短距離効果に関して、双一次変換を、ＳＯＣＳ（Sum of Coherent Sources）法によって単純な線形畳み込みの和に最適に変形することができるが、中距離効果または他の非光学効果に関して、双一次変換を、マスク・パターンと強度カーネルの間の線形畳み込みに変形することができる。
【０００５】
超長距離効果に関して、問題をさらに変形して、粗いグリッドによってマスクを表すことができ、ここで、各画素は、そのグリッド正方形内の特徴の平均パターン密度である。粗いグリッドとインコヒーレントカーネルの間の畳み込みは、たとえば、高速フーリエ変換（ＦＦＴ）が同時にすべての画素の畳み込みを生成できるので、ＦＦＴを介して、または同一の効果をもたらすより新しくより高速の方法によって、非常にすばやく行うことができる。
【０００６】
しかし、短距離および中距離は、個々のポリゴンに対処する必要に起因して時間がかかる可能性があるクリティカルな部分である。短距離効果および中距離効果の計算の通常の実践に、有限で受入可能なサイズのテーブルに保管される基本構成要素セクタの畳み込みのテーブル・ルックアップを提供するある実用的な仮定によってカーネルを空間的に切り詰めることが含まれる。
【０００７】
上の従来技術の畳み込み技法は、一般に、セクタベース・アルゴリズムまたは辺ベース・アルゴリズムのいずれかを使用してポリゴン特徴に対して実行される。このセクタベース・アルゴリズムは、さまざまな角度でセクタを使用して計算することができるが、このセクタベース・アルゴリズムを用いると、セクタに対する畳み込みを、ベースイメージとして事前に計算し、テーブルまたは行列に保管できるようになる。たとえば、セクタ・ベースＯＰＣエンジンの普通の実践に、ポリゴンを、９０°角度（図１に図示）または４５°角度（図２および３に図示）のいずれかのセクタの集合に分解することを含めることができる。
【０００８】
たとえば、図１に、正方形ＲＯＩ１０の内部のさまざまな計算された点「Ｘ０」のさまざまな９０°セクタのルックアップ・テーブル値を示す。ＲＩＯ内部のすべての点「Ｘ０」で、テーブル値は、直線の輪郭線２０のいずれかに沿って一定である。しかし、正方形ＲＯＩ１０の外部にあるすべての点「Ｘ０」３０について、図示のように、輪郭線２０が、水平にまたは垂直にのいずれかでＲＯＩの外に拡張され、そのような点「Ｘ０」３０の畳み込み値は、同一の輪郭線に沿ったＲＯＩの境界の点「Ｘ０＊」３０’で取られる。
【０００９】
さらに図１に関して、ＲＯＩ内にある各点または頂点のすべての畳み込み寄与は、事前に計算され、行列に保管される。すなわち、ルックアップ・テーブルに、ＲＯＩ内にある各すべての点の計算が含まれる。ポリゴンに寄与しない、ＲＯＩの外部の他のすべての点、たとえば、ＲＯＩの左および下の境界の先にある点について、そのような点の畳み込み値は、０と等しい。カーネルを伴うポリゴンの畳み込みが、ＲＯＩ内にある、各すべての寄与する事前に計算され保管されたセクタの寄与を合計することによって計算される。しかし、それを行う際に、これらの寄与する事前に計算され保管されたセクタのそれぞれが、ＲＯＩルックアップ・テーブル内で突き止められることと、その畳み込み寄与が、ポリゴンの畳み込みの合計のために検索されることが必要である。このタスクは、時間がかかり、単調で退屈であるだけではなく、十分な量のメモリおよび記憶容量も必要とする。
【００１０】
普通のセクタ・ベースＯＰＣ計算のもう１つの例で、図２および３に、横に斜めにされ、それぞれが上側領域で４５°の傾斜を有し、輪郭線に沿って一定の値を有する４５°セクタのルックアップ・テーブル値を示す。したがって、点「Ｘ０」３０が、ＲＯＩ１０上にある時に、値は、ＲＯＩの境界にあり、同一の横に斜めにされた輪郭線に沿った点「Ｘ０＊」３０’で取られる。同様に、ＲＯＩ内のすべての点「Ｘ０」で、テーブル値は、横に斜めにされた４５°セクタのいずれかに沿って一定である。各４５°セクタ頂点すなわち点での畳み込みが、ポリゴンの畳み込みの後続の合計のために、計算され、行列に保管される。しかし、この手法も、時間がかかり単調で退屈である。というのは、ポリゴンの事前に計算され保管されるセクタ頂点のそれぞれを、ポリゴンのすべての頂点の畳み込みの合計のために検索しなければならないからである。
【００１１】
４５°セクタのもう１つの短所は、図３で矢印によって示されているように、斜めにされたＲＯＩ１０’の頂点に関する半径の外にあるすべての点が、事前に計算される行列の外にあり、したがって、ポリゴンの畳み込みに寄与を一切追加しないことである。したがって、普通の実践は、（（１−１／ｓｑｒｔ（２））×インタラクション・ディスタンス（ＩＤ））の距離だけ斜めにされたＲＯＩ１０’をテーブルの４つのすべての辺でこの量だけ延長して、新しいＲＯＩ１５を提供することである。それでも、それを行う際に、ルックアップ・テーブルを４つのすべての拡張された辺に拡張しなければならず、この４つの拡張される辺の中にある各すべての点または頂点の畳み込み寄与を、計算し、ルックアップ・テーブルに保管しなければならない。これによって、時間とメモリの両方の要件が追加される。というのは、これらの追加の事前に計算され保管される頂点を、すべての頂点の畳み込み総計について突き止めなければならないからである。
【００１２】
オプティカル・プロクシミティ・コレクションのポリゴン畳み込みの他の一般的な技法に、ポリゴン・ピニング（polygon pinning）手順およびポリゴン・クロッピング（polygon cropping）手順が含まれる。ポリゴン・クロッピング手順では、一般に、元のポリゴンの頂点の複数ポリゴン表現を生成することが含まれ、これによって、この新しい頂点が、ＲＯＩ境界内またはＲＯＩ境界上に存在する。インタセクション法（IntersectionMethod）と称する手順が、そのようなクロッピング技法である。インタセクション法では、一般に、アルゴリズムＣ＝Ａ∪Ｂ（ただし、形状Ａはポリゴン、形状ＢはＲＯＩ、インタセクションＣは複数の新しいより小さいポリゴン）を使用して、元のポリゴンの複数のクロッピングされたポリゴンを生成することが含まれる。クロッピングが完了したならば、各頂点を突き止め、ポリゴンの総畳み込み合計のために合計する。それを行う際に、この手法は、時間がかかり、単調で退屈であり、十分な量のメモリを必要とする。というのは、各頂点を突き止めなければならず、次に、その畳み込み寄与を、ポリゴンのすべての頂点の畳み込みの合計のために検索しなければならないからである。ポリゴン・ピニング手順では、一般に、ＲＯＩの外にある頂点を突き止めることと、その後、そのような頂点をＲＯＩの境界またはその中にピニングすることが含まれる。ピニング手順は、一般に、モデル・ベースのＯＰＣでクロッピング手順より効率的であるが、ＲＯＩ内のすべてのサンプル点の畳み込み計算のためにそのような手順が繰り返される場合に、大量のオーバーヘッドを必要とする。
【００１３】
その結果、当技術分野には、ＯＰＣエンジンで使用される、ポリゴンの頂点の畳み込み寄与を合計する、改善された高速で簡単な方法の必要が存在する。
【００１４】
したがって、本発明は、ポリゴンの畳み込み総計のために、ＲＩＯ内のポリゴンの畳み込まれる頂点を突き止め、合計するのに必要な時間を減らすために、インタラクション・ディスタンスＩＤを超える新しいＲＯＩを定義することによって、モデルベース・オプティカル・プロクシミティ・コレクションで使用される改善された方法を提供することによって、従来技術の上記の問題および不足を克服する。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
従来技術の問題および不足を念頭において、本発明の目的は、ポリゴンの畳み込み寄与総計に関するＲＯＩ内のポリゴンの畳み込まれる頂点を突き止め、合計するのに必要な時間の長さを減らす、インタラクション・ディスタンス（ＩＤ）を超える新しいＲＯＩを定義する方法およびその方法を実行するためのプログラム・ストレージ・デバイスを提供することである。
【００１６】
本発明のもう１つの目的は、ＲＯＩ内のポリゴンの頂点の畳み込みを簡単に、迅速に合計する、新しいＲＯＩを定義する改善された方法およびプログラム・ストレージ・デバイスを提供することである。
【００１７】
本発明のもう１つの目的は、モデルベース・オプティカル・プロクシミティ・コレクションをより効率的にする改善された方法およびプログラム・ストレージ・デバイスを提供することである。
【００１８】
本発明のもう１つの目的は、畳み込み寄与に関するルックアップ・テーブルの拡張を避けるモデルベースＯＰＣの改善された方法およびプログラム・ストレージ・デバイスを提供することである。
【００１９】
本発明のもう１つの目的は、部分的には明白であり、部分的には本明細書から明らかになる。
【課題を解決するための手段】
【００２０】
上記の目的および当業者に明白になる他の目的は、第１の態様で、インタラクション・ディスタンスを有するＲＯＩを設け、ＲＯＩ内の少なくとも１つの有限幾何形状を突き止めることによってモデルベース・オプティカル・プロクシミティ・コレクションを実行する方法を対象とする本発明で達成される。少なくとも１つのカット・ライン（cut line）を、そのような有限幾何形状の少なくとも１つの側稜にまたがって生成し、次に、ＲＯＩを、少なくとも１つのカット・ラインが有限幾何形状の側稜と交わる位置に基づいて、そのインタラクション・ディスタンスを超えて拡張して、オプティカル・プロクシミティを訂正する。
【００２１】
有限幾何形状が、規則的、不規則、凸、凹、規則的な通常の凸、規則的な凹、不規則な凸、不規則な凹などのポリゴンであることが好ましい。カット・ラインに、ＲＯＩ内の頂点の組を表す複数のサンプル点が含まれることが好ましく、これによって、カット・ラインに、カット・ラインと側稜の間の交点の第１側にある第１の個数のサンプル点と、交点の第２側にある第２の個数のサンプル点が含まれる。本発明のこの態様では、カット・ラインのこのサンプル点の第１個数および第２個数を、同一または異なるものとすることができる。
【００２２】
本発明のこの態様では、そのインタラクション・ディスタンスを超えるＲＯＩの拡張が、カット・ラインの位置と、それが水平カット・ライン、垂直カット・ライン、または４５°カット・ラインのどれであるかに基づく。カット・ラインが水平である場合に、ＲＯＩは、ＲＯＩの対抗する水平側面で１次元方向で水平に拡張される。カット・ラインが垂直である場合に、ＲＯＩは、ＲＯＩの対抗する垂直側面で１次元方向で垂直に拡張される。さらに、カット・ラインが４５°カット・ラインである場合に、ＲＯＩは、ＲＯＩのすべての側面で水平および垂直の両方で２次元に拡張される。
【００２３】
さらに、この態様では、有限幾何形状の側稜を横切っている複数のカット・ラインについて上の方法ステップを繰り返すことができ、これによって、ＲＯＩが、複数のカット・ラインの複数の位置に基づいてインタラクション・ディスタンスを超えて拡張される。ＲＯＩが拡張されたならば、すなわち、新しいＲＯＩが生成されたならば、この方法に、さらに、オプティカル・プロクシミティを訂正するためにＲＯＩ内の畳み込みを合計する単一の畳み込み寄与検索ステップで少なくとも１つのカット・ラインをまたぐ複数のサンプル点の事前に計算された畳み込み寄与を同時に検索するステップを含めることができる。
【００２４】
第２の態様で、本発明は、インタラクション・ディスタンスを有する第１ＲＯＩを提供することと、第１ＲＯＩ内で少なくとも１つのポリゴンを突き止めることによってモデルベース・オプティカル・プロクシミティ・コレクションを実行する方法を対象とする。ポリゴンの少なくとも１つの側稜にまたがる少なくとも１つのカット・ラインを突き止め、これによって、そのカット・ラインに、第１ＲＯＩ内の頂点の組を表す複数のサンプル点が含まれるようにする。ポリゴンの側稜にまたがるカット・ラインの角度位置を判定し、次に、カット・ラインとポリゴンの側稜の間の交点の両側にあるカット・ラインの第１部分および第２部分を判定する。角度位置に基づいて、インタラクション距離を超えて第１ＲＯＩを拡張することによって、新しいＲＯＩを設け、少なくとも１つのカット・ラインの第１部分および第２部分が、交差の両側にあるようにする。この第２ＲＯＩが、最終的に、オプティカル・プロクシミティを訂正するのに使用される。この方法に、さらに、第１ＲＯＩ内で、少なくとも１つのポリゴンの少なくとも１つの側稜にまたがる複数のカット・ラインを突き止めることと、問題の複数の新しい領域を生成するために、複数のカット・ラインに基づいて、インタラクション・ディスタンスを超えて第１ＲＯＩを複数回拡張することによって第２ＲＯＩを設けることを含めることができる。
【００２５】
この第２の態様では、カット・ラインの第１部分および第２部分が、それぞれ、複数のサンプル点からの第１個数のサンプル点および第２個数のサンプル点に対応し、この第１個数および第２個数は、第１ＲＯＩがその両側で等しい部分だけ拡張されるように、互いに同一とすることができ、あるいは、第１ＲＯＩがその両側で等しくない部分だけ拡張されるように、互いに異なるものとするとができる。
【００２６】
カット・ラインは、水平カット・ラインまたは垂直カット・ラインとすることができ、第１ＲＯＩは、水平に１次元方向で等しい量または等しくない量だけ、あるいは垂直に１次元方向で等しい量または等しくない量だけのいずれかで拡張することができる。代替案では、カット・ラインを、４５°カット・ラインとし、第１ＲＯＩが、第１ＲＯＩの対抗する辺の第１組に対する第１関数（ｄ１）（ｃｏｓ（π／４））および第１ＲＯＩの対抗する辺の第２組に対する第２関数（ｄ２）（ｃｏｓ（π／４））だけ、すべての側面で２次元に拡張される。
【００２７】
さらに、第２の態様では、インタラクション・ディスタンスを超えて第１ＲＯＩを拡張するステップに、元々は第１ＲＯＩの境界の外に存在した追加ポリゴン、または第１ＲＯＩの境界内または境界上に元々存在したポリゴンの追加部分を取り込むことが含まれる。この方法には、さらに、オプティカル・プロクシミティを訂正するための、第１ＲＯＩ内の頂点の組の畳み込みを合計する単一の畳み込み寄与検索ステップに、少なくとも１つのカット・ラインにまたがる複数のサンプル点の事前に計算された畳み込み寄与を同時に検索するステップを含めることができる。
【００２８】
本発明の第３および第４の態様では、本発明は、本発明の第１および第２の態様に関してモデルベース・オプティカル・プロクシミティ・コレクションを実行する上の方法ステップを実行するために機械によって実行可能な命令のプログラムを有形に実施する、機械によって可読のプログラム・ストレージ・デバイスを対象とする。
【００２９】
本発明の特徴は、新規であると思われ、本発明の特性を表す要素は、請求項に具体的に示されている。図面は、例示のみのものであり、原寸通りに描かれてはいない。しかし、本発明自体は、編成および動作の方法の両方に関して、添付図面と共に以下の詳細な説明を参照することによって最もよく理解することができる。
【発明を実施するための最良の形態】
【００３０】
本発明の実施形態の説明で、図面の図１から７を参照するが、図面では、類似する符号が本発明の類似する特徴を指す。
【００３１】
本発明は、計算時間およびメモリの両方を節約するためにリージョン・オブ・インタレスト（ＲＯＩ）を修正する、光リソグラフィに使用されるモデルベース・オプティカル・プロクシミティ・コレクション（ＯＰＣ）を対象とする。ＲＯＩは、少なくともインタラクション・ディスタンス（図面では「ＩＤ」と称する）と同程度に大きい、その中心を通る線にまたがる直径を有する凸区域であり、インタラクション・ディスタンスは、それを超えるすべての２つの点が互いに無視できるインタラクションを有する距離の２倍である。最終的に、本発明は、フォトレジストをコーティングされたウェハへの正確な投影のための、所望の回路パターンを有するフォトマスク上のひずみの訂正に使用される。
【００３２】
本発明が、すべての有限幾何形状と共に使用するのに適することを理解されたい。好ましい実施形態では、有限幾何形状が、ポリゴンである。設計におけるポリゴンは、通常、頂点、辺、直線、および類似物の集合によって定義され、対応するシーケンス、たとえば、規約によって順方向に動く辺の左側を、必ずポリゴンの内側とすることができる。本発明によれば、ポリゴンは、規則的または不規則、凸または凹、あるいはこの組合せとすることができる。さらに、ポリゴンに、三角形、四辺形（正方形、長方形、平行四辺形）、５角形、６角形、７角形、８角形、９角形、１０角形など含む任意の形状を含めることができる。
【００３３】
本発明は、ポリゴンの畳み込み総計に関して、ＲＯＩ内のポリゴンの畳み込まれる頂点を突き止め、合計するのに必要な時間の長さを減らすという長所を有する、インタラクション・ディスタンスを超えてＲＯＩを定義することによるモデルベース・オプティカル・プロクシミティ・コレクションで使用される効率的な方法を提供する。前述のモデルベース・シミュレーションは、元のＲＯＩ内のすべての点すなわち有限幾何形状（ポリゴンなど）の頂点またはセクタの畳み込みの事前計算および保管の後に行われることが好ましい。
【００３４】
従来、ＲＯＩ内のポリゴンの畳み込み寄与を合計するために、まず、ポリゴンの各すべての頂点を突き止め、次に、その事前に計算された畳み込み寄与を、システムのストレージ・コンポーネントから検索しなければならない。そのような頂点のすべてを突き止め、事前計算された畳み込み寄与を検索したならば、寄与する畳み込みを有するものを合計して、ポリゴンの畳み込み総計を得る。それを行う際に、この手法は、広範囲の計算およびメモリ容量を必要とするだけではなく、望ましくなく時間がかかり単調で退屈である。
【００３５】
有利なことに、前述の発明は、インタラクション・ディスタンスを超えてＲＯＩを拡張する量を同時に判定することに加えて、ＲＯＩ内のポリゴンの畳み込みの合計に関して複数のサンプル点を同時に計算することによって、モデルベースＯＰＣエンジンの改善された性能を提供する。本発明によれば、ＲＯＩを、ＲＯＩの１辺、２辺、３辺、または４つのすべての辺で、そのインタラクション・ディスタンスを超えて拡張することができる。
【００３６】
ＲＯＩを拡張する際に、ＲＯＩ内の少なくとも１つのポリゴンを、当初に突き止め、その後、そのポリゴンの側稜をまたぐ少なくとも１つのカット・ラインを突き止める。代替案では、複数のカット・ラインを、ＲＯＩ内で突き止めることができる。これらのカット・ラインのそれぞれに、ＲＯＩ内の頂点の単一の組に対応する複数のサンプル点が含まれる。本発明の本質的特徴は、単一のカット・ラインにまたがるこれらの複数のサンプル点が、ＲＯＩ内の単一ポリゴンの全ての頂点（一組の頂点）に対応し、これらの変化する点の畳み込み寄与が異なる場合であっても、これらのサンプル点のテーブル・ルックアップが、同時に実行されることである。
【００３７】
すなわち、本発明は、ＲＯＩ内の単一ポリゴンを表す複数のサンプル点に基づいてＲＯＩを拡張することを有利に提供し、ＲＯＩ内のそのような単一ポリゴンの畳み込みの合計に関して、そのようなサンプル点の畳み込み寄与を検索するのに、単一の畳み込み寄与検索だけを必要とする。本発明では、１つずつ各個々のサンプル点を突き止め、次にそのような突き止められたサンプル点ごとの多数の畳み込み寄与検索を実行し、その後、個々のサンプル点に関する多数の畳み込み合計アルゴリズムを実行する必要がなくなる。
【００３８】
本発明の利益は、ＲＯＩ内の各すべての頂点を繰り返して突き止め、頂点ごとにそのめいめいの畳み込み寄与を検索し、ＲＯＩ内のポリゴンの総畳み込みについて頂点のそのような寄与のすべてを合計する必要がなくなることである。
【００３９】
図面を参照すると、本発明の処理フローは、図４に示された流れ図の以下の説明によってよりよく理解される。
【００４０】
ステップ１０００  開始。処理を開始し、これによって、ＲＯＩ内のすべての有限幾何形状の問題のすべての点の畳み込み寄与を、事前に計算し、ルックアップ・テーブルなど、システムのストレージ・コンポーネントに保管する。
【００４１】
ステップ１００５  最初のカットラインを得る。ポリゴン・ピニング（polygon pinning）手順およびポリゴン・クロッピング（polygon cropping）手順により、ＲＯＩ内のポリゴンを突き止め、そのポリゴンの少なくとも１つの側稜にまたがる少なくとも１つのカット・ラインを生成する。ポリゴンは、少なくとも１つのカット・ラインがポリゴンの少なくともセグメントを横切って生成されるユーザ定義のルールの組によって定義される複数のセグメント・ライン（segment line）からなるものとすることができる。代替案では、ポリゴンの単一のセグメントまたは複数のセグメントにまたがる複数のカット・ラインを生成する。
【００４２】
ステップ１０１０  カット・ラインは水平か。突き止められたカット・ラインが、ＲＯＩの下の側稜に関して水平であるかどうかを判定する。カット・ラインが水平である場合には、ステップ１０１５に進む。カット・ラインが水平でない場合には、ステップ１０２０に進む。
【００４３】
ステップ１０１５  ＲＯＩの左の側稜でｄ１、右の側稜でｄ２だけＲＯＩを拡張する。基準ｄ１およびｄ２は、互いに同一とすることができ、そうでなくすることができる。ステップ１０５０に継続する。
【００４４】
ステップ１０２０  カット・ラインは垂直か。カット・ラインが水平でない場合に、突き止められたカット・ラインが、ＲＯＩの下の側稜に関して垂直であるかどうかを判定する。カット・ラインが垂直である場合には、ステップ１０２５に進む。カット・ラインが垂直でない場合には、ステップ１０３０に進む。
【００４５】
ステップ１０２５  ＲＯＩの上の側稜でｄ１、下の側稜でｄ２だけＲＯＩを拡張する。基準ｄ１およびｄ２は、互いに同一とするか、異なるものとすることができる。ステップ１０５０に継続する。
【００４６】
ステップ１０３０  カット・ラインは４５°か。カット・ラインが、水平でも垂直でもない場合に、突き止められたカット・ラインが４５°セクタであるかどうか、すなわち、４５°の角度を形成するかどうかを判定する。カット・ラインが４５°セクタである場合には、ステップ１０３５に進む。カット・ラインが４５°セクタでない場合には、ステップ１０４０に進む。
【００４７】
ステップ１０３５  ＲＯＩの２つの隣接する側稜で（ｄ１）（（ｃｏｓ）（π／４））、ＲＯＩの残りの２つの隣接する側稜で（ｄ２）（（ｃｏｓ）（π／４））だけＲＯＩを拡張する。ステップ１０５０に継続する。
【００４８】
ステップ１０４０  エラー。処理にエラーがある。ステップ１０７０に進み、処理を終了する。
【００４９】
ステップ１０５０  新しいＲＯＩの内部のポリゴンのすべての頂点を得る。ＲＯＩが拡張されており、新しいポリゴン（元のＲＯＩ内になかったポリゴン）が、この新しい拡張されたＲＯＩに含まれる。この新しいポリゴンは、追加の頂点を有し、これによって、これらの新しい頂点のそれぞれの畳み込み寄与を、事前に計算し、後の使用のために保管する。そのような新しい頂点のすべてを、新しい拡張されたＲＯＩ内で突き止める。ステップ１０５５に継続する。
【００５０】
ステップ１０５５  テーブル・ルックアップによって得られる各ポリゴンの寄与を入手する。新しい拡張されたＲＯＩ内のすべての新しい頂点を突き止めたならば、各新しい頂点のそれぞれの事前に計算され保管された畳み込み寄与を、ポリゴンの畳み込みの最終的な合計のために、改訂されたルックアップ・テーブルから検索し、処理はステップ１０６０に継続する。
【００５１】
ステップ１０６０  まだカット・ラインがあるか。新しい拡張されたＲＯＩ内（元のＲＯＩを含む）にまだカット・ラインがあるかどうかを判定する。そうである場合には、ステップ１０６５に進む。そうでない場合には、ステップ１０７０に進み、処理を終了する。
【００５２】
ステップ１０６５  次のカット・ラインを得る。新しい拡張されたＲＯＩ内にまだカット・ラインがある場合に、ステップ１０１０に継続する。
【００５３】
ステップ１０７０  終了。処理を終了する。
【００５４】
図５および６を参照すると、１つまたは複数のカット・ライン上の複数の点の同時計算の、本発明の処理フローおよび方法が、ＲＯＩ１０内のさまざまな点または頂点に関する９０°セクタについて示されている。図５からわかるように、複数の有限幾何形状２０、２２、２４、２６すなわちポリゴンＡ、Ｂ、Ｃ、およびＤが、ＲＯＩ１０の内部または外部に存在することができる。ＲＯＩ１０のオプティカル・ビューイング・ウィンドウ（optical viewing window）すなわち図５および６ではＩＤ×ＩＤ内の任意の点「Ｘ０」の畳み込みを計算する際に、少なくとも１つの頂点がＲＯＩ内にあるすべてのポリゴンを、当初に突き止める。それを行う際に、図５のポリゴンＢ、Ｃ、およびＤが突き止められる。ＲＯＩ内に頂点を有するポリゴンだけが、サンプル点「Ｘ０」での値に畳み込み寄与を追加する。
【００５５】
本発明によれば、前述の処理は、ＲＯＩの内部および外部のすべてのセクタが、突き止められ、そのようなセクタの各頂点の畳み込み寄与が、事前計算され、ルックアップ・テーブルに保管された後に開始されることが好ましい。クロッピングおよびピニング手順を、本発明の間にポリゴンに適用することができる。
【００５６】
ＲＯＩの内部および外部のセクタのすべての畳み込み寄与を事前計算し、保管したならば、ＲＯＩ内の少なくとも１つのポリゴンを突き止めることと、その後、突き止められたポリゴンの側稜にまたがる少なくとも１つのカット・ラインを突き止めることによって、前述のシステムおよび処理を開始する。図５および６に示されているように、ポリゴンＤ２６が、ＲＯＩ１０内で突き止められる。このポリゴンＤは、ＲＯＩ内の任意の位置にあるものとすることができ、その側稜にまたがる複数のセグメントからなるものとすることができる。
【００５７】
その後、少なくとも１つのカット・ライン３０を、ポリゴンＤ２６の少なくとも１つの側稜にまたがる所定の位置で生成する。カット・ラインは、既知の技法（ポリゴン・ピニング（polygon pinning）手順およびポリゴン・クロッピング（polygon cropping）手順が含まれる。）によって生成することができる。代替案では、複数のカット・ライン３０を、ポリゴンＤ２６の同一のまたは異なる側稜、あるいは同一のまたは異なるセグメント、あるいは、ＲＯＩ１０内にあるさまざまな異なるポリゴンの側稜または側稜のセグメントもしくはその両方にまたがって順次または同時に生成することができる。本発明によれば、カット・ライン３０に、ユーザ定義のルールの組に基づいて選択される所定の個数のサンプル点が含まれる。
【００５８】
第１カット・ラインを入手したならば、この処理は、カット・ラインが水平、垂直、またはその代わりに４５°セクタであるかどうかを判定することによって継続する。カット・ライン３０が、ＲＯＩの下の側稜に関して水平であると判定される場合に、ＲＯＩは、ＲＯＩの側面の辺で水平に拡張される。その代わりに、カット・ライン３０が、ＲＯＩの側稜の辺に関して垂直であると判定される場合に、ＲＯＩは、ＲＯＩの上下の側稜で垂直に拡張される。本発明でのＲＯＩの拡張は、ポリゴンの辺にまたがるカット・ライン３０の位置に基づく。すなわち、ＲＯＩは、カット・ラインとポリゴンの辺の間の交差に基づくカット・ラインの第１の側にあるカット・ラインの長さに基づいて第１の側で拡張され、そのような交差の反対側にあるカット・ラインの残りの量に基づいてＲＯＩの反対側で拡張される。
【００５９】
理解を簡単にするために、図５からわかるように、カット・ライン３０は、ＲＯＩ１０の底辺１１に関して水平のカット・ラインであり、ポリゴンＰの水平の側稜にまたがって存在する。カット・ライン３０が水平なので、ＲＯＩは、本発明に従って、ＲＯＩの第１の横の側稜１３で寸法「ｄ１」、ＲＯＩの対向する第２の横の側稜１４で寸法「ｄ２」だけ拡張される。その代わりに、カット・ライン３０が垂直カット・ラインであり、ポリゴンＰの上または下の側稜にまたがっている場合に、ＲＯＩは、ＲＯＩの上側稜１２で寸法「ｄ１」、下側稜１１で寸法「ｄ２」だけ拡張される。
【００６０】
寸法「ｄ１」および「ｄ２」は、ユーザが事前に定義するルールの組を使用して、ポリゴン辺にまたがるカット・ラインの交差点に関してカット・ライン３０にまたがるサンプル点を評価することによって判定される。本発明のクリティカルな態様は、カット・ライン３０に、複数のサンプル点「Ｘ０」が含まれ、これによって、単一のカット・ライン３０に沿ったこれらのサンプル点「Ｘ０」が、ＲＯＩ内の頂点の単一の組に対応することである。したがって、ＲＯＩ１０は、第１の個数のサンプル点「Ｘ０」に基づく、そのようなカット・ライン３０の部分によって、ＲＯＩの１つの側で１つの方向に拡張することができ、すなわち、「ｄ１」は、カット・ラインとポリゴン辺との間の交差の第１側にあり、ＲＯＩ１０は、残りの個数のサンプル点「Ｘ０」に基づく、カット・ライン３０の残りの部分によって、ＲＯＩの反対側で反対方向に拡張することができ、すなわち、「ｄ２」は、そのような交点の第２の側にある。ＲＯＩ１０の拡張は、ＲＯＩが、水平にまたは垂直にのいずれかで、反対方向に同時に拡張されるので、同時拡張である。
【００６１】
本発明によれば、この寸法「ｄ１」および「ｄ２」は、互いに同一とするか異なるものとすることができる。その結果、ＲＯＩ１０を、対向する横の側稜１３および１４または対向する上下の側稜１１および１２で、等しい部分だけまたは等しくない部分だけ、垂直または水平のいずれかで拡張して、図６に示された拡張されたＲＯＩ１０を形成することができる。本発明の本質的な特徴は、カット・ラインが、通常は垂直または水平のいずれかであることであり、本発明を用いると、ＲＯＩの１次元のすなわち、水平方向または垂直方向のいずれかの拡張または拡大が可能になることである。元のＲＯＩ１０を１次元で拡張する時に、この新しい拡張されたＲＯＩ１０は、実質的に長方形の形状を有する。本発明の拡張されたＲＯＩ１０によって、評価のための新しい拡張されたＲＯＩ１０内の追加ポリゴンならびに元のＲＯＩ１０内に既にあるポリゴンの増やされた部分の取り込みが有利に可能になる。
【００６２】
たとえば、図５および６からわかるように、ポリゴンＢおよびＣの部分Ｂ１およびＣ１だけが、元のＲＯＩ１０内にある。ポリゴンＡは、元のＲＯＩ１０の外部にあり、したがって、ポリゴンＡからの畳み込み寄与は、点Ｐだけに関する元のＲＯＩ１０に含まれない。しかし、本発明の新たに拡張されたＲＯＩ３０では、ポリゴンＢおよびＣの増やされた部分すなわち部分Ｂ２およびＣ２が、ＲＯＩ３０内にあり、ポリゴンＡの一部も、図６に示されているように拡張されたＲＯＩ３０内にあり、したがって、追加の畳み込み寄与が、これらの追加のポリゴンおよび先在するポリゴンの増やされた部分からもたらされる。
【００６３】
本発明のもう１つの本質的な特徴は、サンプル点の畳み込み寄与に関する複数のテーブル・ルックアップを、単一のカット・ラインまたは複数の異なるカットラインに沿ったすべてのサンプル点について、ＲＯＩ内の頂点の単一の組に対応する単一カット・ラインに沿ったサンプル点の結果として、同時に実行できることである。カット・ラインに沿ったすべてのサンプル点の畳み込み寄与の同時テーブル・ルックアップは、本発明に従って、サンプル点が同一の畳み込み寄与を有するかさまざまな異なる畳み込み寄与を有するかにかかわらずに達成可能である。複数テーブル・ルックアップ畳み込み寄与を検索したならば、本発明を用いて、単一のカット・ラインまたは複数のカット・ラインに沿った複数のサンプル点のそのような検索された畳み込みのすべての同時計算が、有利に可能になる。
【００６４】
それを行う際に、本発明は、ＲＯＩ内のサンプル点または頂点を検索し、そのような点ごとに１つずつ、畳み込み寄与テーブル・ルックアップ・ステップを実行するという時間がかかり単調で退屈な従来技術を避ける。本発明のクリティカルな特徴は、追加の頂点が本発明による新しい拡張されたＲＯＩによって取り込まれる場合であっても、モデルベースＯＰＣ計算の簡単さおよび速度が大幅に改善されることである。すなわち、１つまたは複数のカット・ライン内のサンプル点に関する畳み込みの同時計算の本発明の手法によって、計算速度が大幅に高められる。
【００６５】
普通の計算方法では、単一のカット・ラインに沿ったＮ個のサンプル点のすべての畳み込み寄与を計算するのに必要な時間が、（Ｎ）（ＩＤ２）（ｕ＋ｖ）に比例し、ここで、寄与するポリゴンの数がＩＤ２に比例すると仮定して、「ｕ」は、単一ポリゴンから畳み込み寄与を計算する時間を表し、「ｖ」は、単位面積を横切るポリゴンの数を数える時間である。
【００６６】
本発明では、単一カット・ラインに沿ったＮ個のサンプル点の畳み込み寄与を計算するのに必要な時間が、（Ｎ）（ｕ）（ＩＤ）（ＩＤ＋ｄ）＋（ｖ）（ＩＤ）（ＩＤ＋ｄ’）に比例し、したがって、普通の方法に必要な時間よりかなり短い。ここで、ｄおよびｄ’は、ｄ１およびｄ２とするか、任意のユーザ定義の数とすることができる。これは、拡張ｄ１またはｄ２あるいはその両方が、単独でまたは組み合わされてあるいはその両方で、元のＲＯＩ１０の寸法よりかなり小さいが、複数の新しいサンプル点または頂点、たとえばＮ≧２が取り込まれるからである。さらに、拡張ｄ１またはｄ２あるいはその両方は、ＲＯＩの比較的小さい拡張であるが０より大きいことが好ましいので、本発明の畳み込み計算の時間の節約は、（ｖ）（Ｎ−１）（ＩＤ２）の関数になる。本発明によれば、本発明の実行時間は、条件ｄ／ＩＤ＜（Ｎ−１）（ｖ）／（Ｎ）（ｕ＋ｖ）が満足される限り、より効率的であり、この条件は、「ｕ」を決定するテーブル・ルックアップ時間が速いことの結果として満足される。
【００６７】
図７からわかるように、カット・ラインが４５°カット・ラインである時に、本発明を使用してＲＯＩを拡張することができる。上の処理ステップの説明を続けると、突き止められたカット・ラインが、水平カット・ラインでも垂直カット・ラインでもないと判定される場合に、次に、カット・ラインが４５°カット・ラインであるかどうかを判定する。カット・ラインが、水平、垂直、４５°のどれでもないと判定される場合には、本発明の方法でエラーが発生しており、処理は停止する。
【００６８】
しかし、カット・ラインが実際に４５°カット・ラインである場合に、本発明は、元のＲＯＩ１０を４つのすべての側面ですなわち、両横の側稜ならびに上下の側稜で拡張することを可能にし、ＲＯＩが、実質的に正方形の形状を保つようにする。すなわち、４５°カット・ラインが、ポリゴンＤ２６’の側稜に沿った単一の４５°カット・ライン３０’に沿ってＮ個のサンプル点「Ｘ０」を有する場合に、本発明は、ＲＯＩ１０の回転図６０によって示されるように、元のＲＯＩ１０の２次元拡張をもたらす。この２次元拡張によって、上で説明した本発明の１次元拡張実施形態と比較して、元々元のＲＯＩ１０の外部にあった取り込まれる追加のポリゴンの数をさらに増やすことができ、元々元のＲＯＩ１０内にあったポリゴンの増やされた部分を取り込むことができる。
【００６９】
本発明によれば、単一の４５°カット・ラインにまたがる複数のサンプル点を含む４５°カット・ラインの場合に、ＲＯＩ１０が、４つの側面のすべてで拡張されて、新しい拡張されたＲＯＩ５０が形成される。新しいＲＯＩ５０の形成で、元のＲＯＩ１０は（およびその回転図６０に示されているように）、図７に示されているように、ＲＯＩ１０の各側面で、（ｄ／２）（ｃｏｓ（π／４））として表される関数によって２次元で拡張される。ＲＯＩ１０の４つのすべての側面での（ｃｏｓ（π／４））の関数であるＲＯＩ１０の２次元拡張の結果として、各側面でのＲＯＩ１０の拡張は、本発明の９０°カット・ライン実施形態の水平または垂直のいずれかのカット・ラインの１次元拡張より小さくなる。代替案では、新しい拡張されたＲＯＩ５０の左上角および右下角を切り詰めることによって、４５°カット・ラインの場合のさらなる縮小を行うことができる。
【００７０】
ＲＯＩ内のカット・ラインが、互いにかなり近い場合に、サイズＤ１×Ｄ２の長方形の内部の複数のカット・ライン上のサンプル点に対して複数の畳み込みを実行することができる。この形で、ＲＯＩ１０が、水平方向に寸法Ｄ１、垂直方向に寸法Ｄ２だけ拡張される。これは、狭いピッチのパターンを有する回路設計に特に有用である。
【００７１】
本発明の上記の実施形態のどれにおいても、元のＲＯＩ１０が、少なくとも２つの側面でまたはその代わりに４つのすべての側面で拡張されたならば、この処理フローは、元々はＲＯＩ１０内になかったすべての追加の取り込まれるポリゴンのすべてならびにＲＯＩ内にある元々のポリゴンの追加部分のすべてを突き止めることによって継続される。そのようなポリゴンを表す事前に計算された畳み込み寄与頂点が、カット・ラインに沿ったサンプル点の総畳み込み寄与についてルックアップ・テーブルから検索される。したがって、本発明のクリティカルな特徴は、本発明によるさらなる処理のための元のＲＯＩの拡張およびこの新しい拡張されたＲＯＩの使用ならびに普通のＯＰＣ処理ステップおよび技法と共にこの新しい拡張されたＲＯＩを使用することである。
【００７２】
本発明の方法は、ＲＯＩ内のすべてのカット・ライン、具体的には本発明の拡張されたＲＯＩ内にあるカット・ラインについて継続される。このモデルベースＯＰＣエンジンの畳み込み合計で使用されるカット・ラインがもうないと判定されたならば、この処理フローが終了する。
【００７３】
前述の説明に鑑みて、本発明は、元のＲＯＩの外部にあるポリゴンを突き止める前に、あるカット・ラインにまたがる複数のサンプル点に基づいて、少なくとも２つの側面、任意選択として４つのすべての側面で、ＲＯＩを同時に拡張し、そのような追加のポリゴンすなわちポリゴンＡを有利に取り込む。それを行う際に、本発明は、ＲＯＩ内の頂点を１つずつ突き止め、頂点ごとにめいめいのテーブル・ルックアップ畳み込み寄与を１つずつ実行するという面倒で時間のかかるタスクを避けることによって利益を提供する。本発明は、ポリゴンＡなどのＲＯＩの外にある追加ポリゴンを検索し、次にそのようなポリゴンをＲＯＩ内に含めるためにＲＯＩの１側面でＲＯＩを拡張し、次にこのポリゴンのすべての頂点を突き止め、そのめいめいの畳み込み寄与を１つずつ検索する必要がある従来の手法に関連する問題も克服する。さらに、前述の発明は、上で詳細に述べたように単一のカット・ラインにまたがる複数のサンプル点を同時に計算することによって、ＲＯＩで突き止められるすべてのポリゴンの畳み込み寄与を達成するための広範囲の記帳ステップを実行する必要をなくす。
【００７４】
この方法は、機械によって読取可能であり、方法ステップのそれぞれを実行するために機械によって実行可能な命令のプログラムを有形に実施するプログラム・ストレージ・デバイスに保管されたコンピュータ・プログラム製品を介して実施することができる。本発明のプログラム・ストレージ・デバイスは、光学特性、磁気特性、またはエレクトロニクスあるいはこれらの組合せを使用して本発明の方法ステップを実行する機械の構成要素として考案し、作り、使用することができる。プログラム・ストレージ・デバイスには、磁気ディスケット、磁気テープ、光ディスク、読取専用メモリ（ＲＯＭ）、フロッピ・ディスク、半導体チップ、および類似物が含まれるが、これに制限はされない。既知のソース・コード内のコンピュータ可読プログラム・コード手段を使用して、上で説明した方法をコンピュータでの使用のために変換することができる。
【００７５】
本発明を、特定の好ましい実施形態と共に詳細に説明したが、多数の代替形態、修正形態、および変形形態が、前述の説明に鑑みて当業者に明白であることは明らかである。したがって、添付請求項は、本発明の真の範囲および趣旨に含まれる、そのような代替形態、修正形態、および変形形態のすべてを含むことが企図されている。
【図面の簡単な説明】
【００７６】
【図１】セクタの畳み込みをテーブルに保管された基本画像として事前に計算できるようにするために、ポリゴンを９０°角度のセクタの集合に分解するセクタ・ベースのＯＰＣエンジンを示す、従来技術の概略図である。
【図２】セクタの畳み込みをテーブルに保管された基本画像として事前に計算できるようにするために、ポリゴンを４５°角度のセクタの集合に分解するセクタ・ベースのＯＰＣエンジンを示す、もう１つの従来技術の概略図である。
【図３】テーブル・ルックアップ区域を、あるｘ０値を含むようにリージョン・オブ・インタレストに類似する形で斜めにしなければならないことを示す。図２の従来技術を示す概略図である。
【図４】本発明を実践する際に使用される好ましいステップを示すブロック図流れ図である。
【図５】リージョン・オブ・インタレストが、９０°セクタについてＲＯＩ内のポリゴンの１つの測稜をまたぐカット・ラインに沿った複数の点を有する、図４の処理フローと共に使用される、リージョン・オブ・インタレストの内部および外部のポリゴンのグループを示す、本発明の概略図である。
【図６】図４の処理フローによる、１方向でカット・ライン・サイズの部分だけ、反対方向でカット・ライン・サイズの残りの部分だけの、９０°セクタに関する図５のリージョン・オブ・インタレストの領域の拡張を示す本発明の概略図である。
【図７】図４の処理フローによる、ＲＯＩの４辺全部でのカット・ライン・サイズの部分だけの４５°セクタに関するリージョン・オブ・インタレストの拡張を示す本発明の概略図である。
【符号の説明】
【００７７】
１０  正方形ＲＯＩ
１０’  ＲＯＩ
１１  下側稜
１２  上側稜
１３  第１の横の側稜
１４  第２の横の側稜
１５  ＲＯＩ
２０  輪郭線
２０  有限幾何形状
２２  有限幾何形状
２４  有限幾何形状
２６  有限幾何形状
３０  点Ｘ０
３０’  点Ｘ０＊
【図１】
0004791020.tif 000002
【図２】
0004791020.tif 000003
【図３】
0004791020.tif 000004
【図４】
0004791020.tif 000005
【図５】
0004791020.tif 000006
【図６】
0004791020.tif 000007
【図７】
0004791020.tif 000008