(57)【要約】階層イメージデータがメモリを有するグラフィックエンジンで受信され、パターンの繰返されるフィーチャまたはフィーチャのセットを決める少なくとも一つのセルがメモリにストアされ、及びビーム制御データがイメージデータに応答して生成されるパターン生成方法及びシステムである。イメージデータは、メモリにストアされた各セルのための少なくとも２つのサブルーチン呼び出しコマンドを含む残りのデータを有する。各サブマリン呼び出しコマンドに応答して、グラフィックエンジンはメモリからセル（コマンドによって識別される）を抽出し、コマンドによって識別されたターゲット上の場所で（または場所で始まる）イメージされるべきセルによって決められたフィーチャまたはフィーチャのセットを決めるビーム制御データをアサートする。サブルーチン呼び出しコマンドは、キャッシュせれるべき少なくとも一つのセルばかりでなく残りのデータも含むイメージデータ全体にわたって分布される。好ましくは、グラフィックエンジンは、メモリにイメージデータの各セルをキャッシュし、メモリからキャッシュされたセルを抽出し、抽出されたセルに応答してビーム制御データを生成することによって含む各サブルーチン呼び出しコマンドに応答してビーム制御データのセットを生成する。代わりに、グラフィックエンジンは、イメージデータの各セルに応答してビーム制御データのセルを生成し、メモリにこの各々のビーム制御データセルをキャッシュし、及びメモリからキャッシュされたビーム制御データを抽出し、ターゲット上にイメージされるべきフィーチャまたはフィーチャセット（抽出されたセルによって決められる）を決めるビーム制御データのセットの一部として抽出されたサブルーチン制御データセルをアサートすることによって、イメージデータの各サブルーチン呼び出しコマンドに応答する。本発明の他の特徴は、生の階層イメージデータを解析し、この生のイメージデータを、セルを含む最適化された階層イメージデータに変換することによって、階層イメージデータ（グラフィックエンジンへ転送されるべき）のセルを決めるための方法及び装置である。
2005521071.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも一つのビームがターゲット上にパターンをイメージ化するためのビーム制御データを生成するパターン生成システムであって、
少なくとも３つの階層を有する階層イメージデータのセットを生成し、アサートするように構成されたデータ生成サブシステム、及び
メモリを有するグラフィックエンジン、
を備え、
前記階層イメージデータは、残りのデータ及びセルのセットを含み、前記セルの各々は、パターンのフィーチャセットを決め、残りのデータは少なくとも２つのサブルーチン呼び出しコマンドを含み、且つ前記サブルーチン呼び出しコマンドの各々は、セルのセットのセル及び前記セルによって決められたフィーチャセットがイメージ化されるべきターゲットの一部を識別し、
前記グラフィックエンジンは、前記階層イメージデータを受信し、前記階層イメージデータを受信すると前記セルのセットをストアし、且つ前記残りのデータ及びメモリの内容に応答して前記ビーム制御データを生成するように接続され、且つ構成されており、更に、前記グラフッィエンジンは、前記メモリからセルの１つを抽出し、及び前記サブルーチン呼び出しコマンドの少なくとも２つの各々によって識別されたターゲットの前記一部に前記セルの１つによって決められたフィーチャセットのイメージ化を制御する前記ビーム制御データの一部を生成することによって、前記サブルーチン呼び出しコマンドの少なくとも２つの各々に応答するように構成され、
前記セルのセットは、少なくとも１つの一次セルと少なくとも１つの二次セルを有し、前記サブルーチン呼び出しコマンドは、少なくとも２つの一次呼び出しコマンドと少なくとも２つの二次呼び出しコマンドを有し、前記一次セルは、前記少なくとも２つの二次呼び出しコマンドを有し、前記グラフィックエンジンは、前記メモリから前記一次セルを抽出し、前記一次呼び出しコマンドの少なくとも２つの各々によって識別される前記ターゲットの一部に前記一次セルによって決められるフィーチャセットのイメージ化を制御する前記ビーム制御データの一部を生成することによって、前記一次呼び出しコマンドの少なくとも２つの各々に応答するように構成され、且つ、グラフィックエンジンは、前記メモリから前記二次セルを抽出し、前記二次呼び出しコマンドの少なくとも２つの各々によって識別される前記ターゲットの一部に前記二次セルによって決められるフィーチャセットのイメージ化を制御する前記ビーム制御データの一部を生成することによって、前記二次呼び出しコマンドの少なくとも２つの各々に応答するように構成されることを特徴とするパターン生成システム。
【請求項２】
前記ビーム制御データは、ピクセル形式であることを特徴とする請求項１に記載のパターン形成システム。
【請求項３】
また、前記グラフィックエンジンから前記ビーム制御データを受け取るために結合され、前記ビーム制御データに応答して前記ターゲット上にパターンをイメージ化するように構成されるビームシステムを有し、前記ビームシステムは、少なくとも１つのビームがターゲット上にパターンをイメージ化する構成のシーケンスにおいて動作することによってビーム制御データに応答するように構成されることを特徴とする請求項１に記載のパターン形成システム。
【請求項４】
前記グラフィックエンジンは、ラスターエンジンであり、且つ前記ビームシステムは、前記ターゲットに対して少なくとも１つのビームのラスター走査を行なうことによって前記制御データに応答するように構成されていることを特徴とする請求項３に記載のパターン形成システム。
【請求項５】
前記データ生成システムは、生の階層イメージデータのセットに応答して階層イメージデータのセットを生成するようにプログラムされたプロセッサを有し、
前記プロセッサは：
生のイメージデータのための階層グラフを決め、前記階層グラフを前記階層イメージデータの仮のバージョンの仮の階層グラフとして識別し、フィギュア・オブ・メリットにより前記仮の階層グラフのセルをソートし、且つ第１のセルのセットにおける各セルは、前記第１のセルのセットの各セルのフィギュア・オブ・メリットがスレッショルド値と所定の関係を有し、第２のセルのセットは前記第１のセルのセットにないセルの各々から成っていると言う基準を含む少なくとも１つの所定の基準を満足するように、前記仮の階層グラフのセルを第１のセルのセット及び第２のセルのセットにクラス分けするための；及び
前記階層イメージデータの前記階層グラフは、前記第１のセルのセットを含むが、前記第２のセルのセットを含まず、且つ前記階層イメージデータの残りのデータは置き換えの残りのデータを含むように、前記第２のセルのセット及び前記第２のセルのセットにおける各々のセルへの前記サブルーチン呼び出しを置き換えの残りのデータで置きかえることによって、生の階層イメージデータから前記階層イメージデータを決めるための、
ソフトウェアでプログラムされることを特徴とする請求項１に記載のパターン形成システム。
【請求項６】
前記データ生成システムは、生の階層イメージデータのセットに応答して階層イメージデータのセットを生成するためにプログラムされたプロセッサを有し、
前記プロセッサは：
前記生のイメージデータのための階層グラフを決め、前記階層イメージデータの仮のバージョンの仮の階層グラフとして前記階層グラフを識別し、且つ前記生のイメージデータのセットの全大きさに対するそれらの個々の大きさによる仮の階層グラフのセルをソートし；
前記階層イメージデータの仮のバージョンの全大きさに対して大きさが最も大きい仮の階層グラフのセルの１つを識別し、そしてもし、前記セルの１つの大きさがキャッシュ可能な大きさを越えないならば、階層イメージデータのセルとしてセルの１つの含有によって前記階層イメージデータの残りの部分の大きさが所定の最大の大きさを越えるか否かを決め；
もし、前記階層イメージデータのセルとしてセルの１つの含有によって前記階層イメージデータの残りの部分の大きさが前記所定の最大の大きさを越えるならば、前記セルの一つの多数のインスタンティエーションを含み、且つキャッシュ可能な大きさを越えない大きさを有する新しいセルを識別し、前記セルの１つの多数のインスタンティエーションを前記新しいセルで置き換えることによって、前記階層グラフ及び前記階層イメージデータの前記仮のバージョンを更新し、それによって、前記階層イメージデータの更新された階層グラフ及び更新されたバージョンを決め、もし、更新された階層イメージデータの残りの部分の大きさが前記所定の最大の大きさを越えないならば、前記更新された階層イメージデータを前記階層イメージデータとして識別するためのソフトウェアでプログラムされることを特徴とする請求項１に記載のパターン形成システム。
【請求項７】
少なくとも１つのビームがターゲット上にパターンをイメージ化するためのビーム制御データを生成するグラフィックエンジンであって、
少なくとも３−レベルの階層を有する階層イメージデータのセットを受信するために結合されたメモリと前記メモリに結合されたビーム制御データ生成器を備え、
前記階層イメージデータは、残りのデータとセルのセットを含み、前記セルの各々は、前記パターンのフィーチャセットを決め、前記残りのデータは、少なくとも２つのサブルーチン呼び出しコマンドを有し、且つ前記サブルーチン呼び出しコマンドの各々は、セルのセットのセル及びセルによって決められるフィーチャセットがイメージ化されるべきターゲットの一部を識別し、前記エンジンは、前記階層イメージデータを受信するとメモリにセルのセットをストアするように構成され；及び
前記ビーム制御データ生成器は、前記階層イメージデータの少なくとも残りのデータを受信するために結合され、前記残りのデータと前記メモリの内容に応答して前記ビーム制御データを生成するように構成され、且つ、前記ビーム制御データ生成器は、メモリから前記セルの１つを抽出し、前記サブルーチン呼び出しコマンドの少なくとも２つの各々によって識別された前記ターゲットの一部に前記セルの１つによって識別されたフィーチャセットのイメージ化を制御する前記ビーム制御データの一部を生成することによって、前記サブルーチン呼び出しコマンドの少なくとも２つの各々に応答するように構成されており、
前記セルのセットは、少なくとも１つの一次セルと少なくとも１つの二次セルを有し、前記サブルーチン呼び出しコマンドは、少なくとも２つの一次呼び出しコマンドと少なくとも２つの二次呼び出しコマンドを有し、前記一次セルは、前記少なくとも２つの二次呼び出しコマンドを有し、前記ビーム制御データ生成器は、メモリから前記一次セルを抽出し、前記一次呼び出しコマンドの各々によって識別された前記ターゲットの一部に前記一次セルよって識別されたフィーチャセットのイメージ化を制御する前記ビーム制御データの一部を生成することによって、前記一次呼び出しコマンドの少なくとも２つの各々に応答するように構成されており、且つ、前記ビーム制御データ生成器は、前記メモリから前記二次セルを抽出し、前記二次呼び出しコマンドの少なくとも２つの各々によって識別された前記ターゲットの一部に前記二次セルよって識別されたフィーチャセットのイメージ化を制御する前記ビーム制御データの一部を生成することによって、前記二次呼び出しコマンドの少なくとも２つの各々に応答するように構成されることを特徴とするグラフィックエンジン。
【請求項８】
前記ビーム制御データは、ピクセル形式であることを特徴とする請求項７に記載のグラフィックエンジン。
【請求項９】
少なくとも１つのビームがターゲット上にパターンをイメージ化するためのビーム制御データを生成するパターン生成システムであって、
少なくとも３-レベルの階層を有する階層イメージデータを生成し、アサートするように構成されたデータ生成サブシステム及びメモリを有するグラフィックエンジンを備え、
前記階層イメージデータは、残りのデータとセルを有し、前記セルは、パターンのフィーチャセットを決める少なくとも１つの一次セルとパターンのフィーチャセットを決める少なくとも１つの二次セルを有し、前記残りのデータは、前記セルの各々に対して少なくとも２つのサブルーチン呼び出しコマンドを有し、且つ、前記サブルーチン呼び出しコマンドの各々は、前記セルの１つ及び前記セルの１つによって決められたフィーチャセットがイメージされるべきターゲットの一部を識別し；及び
前記グラフィックエンジンは、前記階層イメージデータを受信し、前記階層イメージデータの前記セルの各々に応答してビーム制御データのセル生成し、前記をビーム制御データのセル前記メモリにストアし、且つ前記残りのデータ及び前記メモリの内容に応答して前記ビーム制御データを生成するように接続、構成され、更に、前記グラフィックエンジンは、前記メモリから１つの前記ビーム制御データのセルを抽出することによって前記サブルーチン呼び出しコマンドの各々に応答するように構成されていることを特徴とするパターン生成システム。
【請求項１０】
前記ビーム制御データは、ピクセル形式であることとを特徴とする請求項９に記載のパターン生成システム。
【請求項１１】
前記グラフィックエンジンから前記制御データを受信するように接続され、且つ、前記ビーム制御データに応答して前記ターゲット上にパターンをイメージ化するように構成されたビームシステムを備え、前記ビームシステムは、前記少なくとも１つのビームが前記ターゲット上にパターンをイメージ化する構成のシーケンスにおいて動作することによって前記ビーム制御データに応答するように構成されていることを特徴とする請求項９に記載のパターン生成システム。
【請求項１２】
前記グラフィックエンジンはラスターエンジンであり、且つ前記ビームシステムは前記ターゲットに対して前記少なくとも１つのビームのラスター走査を行なうことによって前記ビーム制御データに応答するように構成されていることを特徴とする請求項１１に記載のパターン生成システム。
【請求項１３】
少なくとも１つのビームがターゲット上にパターンをイメージ化するためのビーム制御データを生成するグラフィックエンジンであって、
メモリと、
前記メモリに接続され、少なくとも３−レベルの階層を有する階層イメージデータのセットを受信するビーム制御データ生成器と、
を備え、
前記階層イメージデータは、残りのデータとセルを含み、前記セルは、パターンのフィーチャセットを決める少なくとも１つの一次セルとパターンのフィーチャセットを決める少なくとも１つの二次セルを有し、前記残りのデータは、前記セルの各々に対して少なくとも２つのサブルーチン呼び出しコマンドを有し、且つ、前記サブルーチン呼び出しコマンドの各々は、前記セルの１つ及び前記セルの１つによって決められたフィーチャセットがイメージされるべきターゲットの一部を識別し；及び
前記ビーム制御データ生成器は、前記セルの各々に応答してビーム制御データセルを生成して前記メモリにストアし、且つ、前記残りのデータ及び前記メモリのないように応答して前記ビーム制御データを生成するように構成され、更に、前記ビーム制御データ生成器は、メモリから一つの前記ビーム制御データセルを抽出することによって前記サブルーチン呼び出しコマンドの少なくとも２つの各々に応答するように構成されていることを特徴とするグラフィックエンジン。
【請求項１４】
前記ビーム制御データは、ピクセル形式であることを特徴とする請求項１３に記載のグラフィックエンジン。
【請求項１５】
生の階層イメージデータのセットに応答して少なくとも２−レベルの階層を有する階層イメージデータのセットを生成するようにプログラムされたプロセッサであって、
その結果前記階層イメージデータは、残りのデータと少なくとも一つのセルを有し、前記セルの各々は、パターンフィーチャセットを定め、前記残りのデータは、少なくとも２つのサブルーチン呼び出しコマンドを有し、且つ前記サブルーチン呼び出しコマンドは、前記少なくとも一つのセルのセルと前記セルによって決められる前記フィーチャセットがイメージ化されるべきであるターゲットの一部を識別し、
前記プロセッサは、
（ａ）前記生のイメージデータのための階層グラフを決め、前記階層グラフを前記階層イメージデータの仮のバージョンの仮の階層グラフとして識別し、フィギュア・オブ・メリットにより前記仮の階層グラフのセルをソートし、且つ第１のセルのセットにおける各セルが、前記第１のセルのセットにおける各セルのフィギュア・オブ・メリットがスレッショルドに対して所定の関係を有し、及び第２のセルのセットが前記第１のセルのセットにないセルの各々から成っているという基準を含む少なくとも１つの所定の基準を満足するように、前記仮の階層グラフのセルを前記第１のセルのセット及び第２のセルのセットにクラス分けし；及び
（ｂ）前記第２のセルのセットと前記第２のセルのセットにおける各々のセルへのサブルーチン呼び出しを残りの置換データで置き換えることによって、前記生の階層イメージデータから前記階層イメージデータを決め、その結果、前記階層イメージデータの前記階層グラフは、前記第１のセルのセットを有するが、前記第２のセルのセットを有せず、且つ前記階層イメージデータの残りのデータは、残りの置換データを有するためのソフトウェアでプログラムされることを特徴とするプロセッサ。
【請求項１６】
前記プロセッサは、前記第１のセルのセットの各セルのフィギュア・オブ・メリットが前記スレッショルド値を越え、且つ前記第２のセルのセットの各セルのフィギュア・オブ・メリットが前記スレッショルド値を越えないように、前記仮の階層グラフのセルを前記第１のセルのセットと前記第２のセルのセットにクラス分けするためのソフトウェアでプログラムされることを特徴とする請求項１５に記載のプロセッサ。
【請求項１７】
前記階層イメージデータのセルは、グラフィックエンジンのメモリにキャッシュされ、各セルに対する前記フィギュア・オブ・メリットは、もし、前記セルが前記メモリにキャッシュされたならば、前記セルによって占有されるメモリのその部分の大きさであることとを特徴とする請求項１６に記載のプロセッサ。
【請求項１８】
前記階層イメージデータは、前記グラフィックエンジンに転送され、前記階層イメージデータのセルは、前記グラフィックエンジンのメモリにキャッシュされ、且つ各セルのためのフィギュア・オブ・メリットは、SAV（節約）/SIZE（大きさ）である：ただし、もし、前記セルが前記メモリにキャッシュされたならば、SIZEは前記セルによって占有されるメモリのその部分の大きさであり、且つSAVは、前記階層イメージデータの全体の量が前記セルに対応する残りのデータに代えて前記セルがメモリにキャッシュされた後に前期セルを繰り返し呼び出すサブルーチン呼び出しコマンドと共に、前記階層イメージデータに前記セルを含むことによって減少されるデータ量であることを特徴とする請求項１６に記載のプロセッサ。
【請求項１９】
生の階層イメージデータのセットに応答して少なくとも２−レベルの階層を有する階層イメージデータのセットを生成するようにプログラムされたプロセッサであって、前記階層イメージデータは、残りのデータとセルのセットを含み、前記セルの各々は、パターンのフィーチャセットを定め、前記残りのデータは、少なくとも２つのサブルーチン呼び出しコマンドを含み、且つ前記サブルーチン呼び出しコマンドの各々は、前記セルのセットのセル及び前記セルによって決められた前記フィーチャのセットがイメージ化されるターゲットの一部を識別し、
前記プロセッサは、
（ａ）前記生のイメージデータのための階層グラフを定め、前記階層グラフを前記階層イメージデータの仮のバージョンの仮の階層グラフとして認識し、且つ前記生のイメージデータのセットの全大きさに対して個々の大きさにより仮の階層グラフのセルをソートし、
（ｂ）前記階層イメージデータの仮のバージョンの全大きさに対して大きさが最も大きい仮の階層グラフのセルの１つを識別し、且つもし、前記セルの１つの大きさがキャッシュ可能な大きさを越えないならば、前記階層イメージデータのセルとして前記セルの１つの含有によって、前記階層イメージデータの残りの部分の大きさが所定の最大の大きさを越えるか否かを判断し、且つ
（ｃ）もし、前記階層イメージデータのセルとして前記セルの一つの含有によって、前記階層イメージデータの残りの部分の大きさが所定の最大の大きさを越えるならば、前記セルの１つの多重インスタンティエーションを含み、キャッシュ可能な大きさを越えない大きさを有する新しいセルを識別し、前記セルの１つの多重インスタンティエーションを前記新しいセルで置き換えることによって仮の階層グラフ及び前記階層イメージデータの仮のバージョンを更新し、それによって更新された階層グラフ及び前記階層イメージデータの更新されたバージョンを決め、且つもし、更新された階層イメージデータの残りの部分の大きさが前記所定の最大の大きさを越えないならば、前記更新された階層イメージデータを前記階層イメージデータとして識別するためのソフトウェアでプログラムされることを特徴とするプロセッサ。
【請求項２０】
生の階層イメージデータのセットに応答して少なくとも２−レベルの階層を有する階層イメージデータのセットを生成する方法であって、前記階層イメージデータは、残りのデータとセルのセットを含み、前記セルの各々は、パターンのフィーチャセットを定め、前記残りのデータは、少なくとも２つのサブルーチン呼び出しコマンドを含み、且つ前記サブルーチン呼び出しコマンドの各々は、前記セルのセットのセル及び前記セルによって定められた前記フィーチャのセットがイメージ化されるターゲットの一部を識別し、
前記方法は、
（ａ）前記生のイメージデータのための階層グラフを定め、前記階層グラフを前記階層イメージデータの仮のバージョンの仮の階層グラフとして認識し、且つ前記生のイメージデータのセットの全大きさに対して個々の大きさにより仮の階層グラフのセルをソートするステップと、
（ｂ）前記階層イメージデータの仮のバージョンの全大きさに対して大きさが最も大きい仮の階層グラフのセルの１つを識別し、且つもし、前記セルの１つの大きさがキャッシュ可能な大きさを越えないならば、前記階層イメージデータのセルとして前記セルの１つの含有によって、前記階層イメージデータの残りの部分の大きさが所定の最大の大きさを越えるか否かを判断するステップと、且つ
（ｃ）もし、前記階層イメージデータのセルとして前記セルの一つの含有によって、前記階層イメージデータの残りの部分の大きさが所定の最大の大きさを越えるならば、前記セルの１つの多重インスタンティエーションを含み、キャッシュ可能な大きさを越えない大きさを有する新しいセルを識別し、前記セルの１つの多重インスタンティエーションを前記新しいセルで置換えることによって、仮の階層グラフ及び前記階層イメージデータの仮のバージョンを更新し、それによって更新された階層グラフ及び前記階層イメージデータの更新されたバージョンを決め、且つもし、更新された階層イメージデータの残りの部分の大きさが前記所定の最大の大きさを越えないならば、前記更新された階層イメージデータを前記階層イメージデータとして識別するステップと、
を有することを特徴とする方法。
【請求項２１】
生の階層イメージデータのセットに応答してグラフィックエンジンに転送されるべき階層イメージデータのセットを生成する方法であって、前記階層イメージデータは、少なくとも２−レベルの階層を有し、且つ残りのデータとセルのセットを含み、前記セルの各々は、パターンのフィーチャセットを決め、前記残りのデータは、少なくとも２つのサブルーチン呼び出しコマンドを含み、且つ、前記サブルーチン呼び出しコマンドの各々は、前記セルのセットのセル及び前記セルによって決められた前記フィーチャセットがイメージ化されるべきであるターゲットの一部を識別し、
前記方法は、
前記生のイメージデータのための階層グラフを定め、及び前記階層グラフを有する前記階層イメージデータの仮のバージョンを決めるステップと、
前記生のイメージデータのデータ量に対して減少されたデータ量と前記グラフィックエンジンにおける生のイメージデータから前記ビーム制御データの生成のために必要な時間に対して前記グラフィックエンジンにおける前記最適な階層イメージデータからのビーム制御データの生成のために必要な減少された時間との最適な組み合わせを達成する階層イメージデータの最適バージョンを決めるために前記階層イメージデータの仮のバージョンを変更するするステップと、
を有することを特徴とする方法。
【請求項２２】
生の階層イメージデータのセットに応答して少なくとも２−レベルの階層を有する階層イメージデータのセットを生成する方法であって、前記階層イメージデータは、残りのデータと少なくとも一つのセルを含み、前記セルの各々は、パターンのフィーチャセットを決め、前記残りのデータは、少なくとも２つのサブルーチン呼び出しコマンドを含み、且つ前記サブルーチン呼び出しコマンドの各々は、前記セルのセットのセル及び前記セルによって決められた前記フィーチャのセットがイメージ化されるターゲットの一部を識別し、
前記方法は、
（ａ）前記生のイメージデータのための階層グラフを決め、前記階層イメージデータの仮のバージョンの仮の階層グラフとして前記階層グラフを識別し、フィギュア・オブ・メリットによる前記仮の階層グラフのセルをソートし、且つ前記仮の階層グラフのセルを第１のセルのセットと第２のセルのセットにクラス分けするステップを有し、前記第１のセルのセットにおける各々のセルは、前記第１のセルのセットの各々のセルのフィギュア・オブ・メリットがスレッショルド値と所定の関係を有する基準を有する少なくとも一つの所定の基準を満足し、且つ第２のセルのセットは、前記第１のセルのセットにないセルの各々から成り、且つ
（ｂ）前記第２のセルのセットおよび前記第２のセルのセットにおける各々のセルへのサブルーチン呼び出しを残りの置換データで置き換えることによって、前記生の階層イメージデータからの階層イメージデータを定めるステップを有し、前記階層イメージデータの階層グラフは、前記第１のセルのセットを含むが、前記第２のセルのセットを含まず、且つ前記階層イメージデータの残りのデータは、前記残りの置換データを含むことを特徴とする方法。
【請求項２３】
少なくとも一つのビームがターゲット上にパターンをイメージ化するようにするためのビーム制御データを生成する方法であって、前記方法は、
（ａ）少なくとも３-レベルの階層を有する階層イメージデータのセットを生成するステップ、前記階層イメージデータは、残りのデータ、及び前記パターンのフィーチャセットを決める少なくとも１つの一次セルと前記パターンのフィーチャセットを決める少なくとも１つの二次セルを有し、前記残りのデータは、一次のサブルーチン呼び出しコマンドを含み、前記一次セルは、少なくとも２つの二次サブルーチン呼び出しコマンドを含み、前記サブルーチン呼び出しコマンドの各々は、前記セルのセット及び前記セルによって定められるフィーチャセットがイメージ化されるべきであるターゲットの一部を識別し、
（ｂ）前記セルの各々をメモリにストアするステップ、及び
（ｃ）前記一次セルを前記メモリから抽出し、前記一次呼び出しコマンドの少なくとも２つの各々によって識別された前記ターゲットの一部に前記一次セルによって定められたフィーチャセットのイメージ化を制御する前記ビーム制御データの一部を生成することによって、前記一次の呼び出しコマンドの少なくとも２つの各々に応答することによって、且つ前記二次セルを前記メモリから抽出し、前記二次呼び出しコマンドの少なくとも２つの各々によって識別された前記ターゲットの一部に前記二次セルによって定められたフィーチャセットのイメージ化を制御する前記ビーム制御データの一部を生成することによって、前記二次の呼び出しコマンドの少なくとも２つの各々に応答することによって含む前記残りのデータと前記メモリの内容に応答して前記ビーム制御データを生成するステップ、
を有することを特徴とする方法。
【請求項２４】
前記ステップ（ｃ）は、ビーム制御データがピクセル形式であるように実行されることを特徴とする請求項２３に記載の方法。
【請求項２５】
（ｄ）前記ビーム制御データに応答して少なくとも一つのビームが前記ターゲット上に前記パターンをイメージ化する構成のシーケンスにおいてビームシステムを動作するステップを含むことを特徴とする請求項２３に記載の方法。
【請求項２６】
前記ビームシステムは、前記ステップ（ｄ）中に、前記ターゲットに対して少なくとも１つのビームのラスター走査を行なうことを特徴とする請求項２５に記載の方法。
【請求項２７】
少なくとも１つのビームがターゲット上にパターンをイメージ化するようにするためのビーム制御データを生成する方法であって、前記方法は、
（ａ）少なくとも３-レベルの階層を有し、前記パターンのフィーチャセットを決める少なくとも１つの一次セル及び前記パターンのフィーチャセットを決める少なくとも１つの二次セルを含むセルのセットを有する階層イメージデータのセット及び残りのデータを受信するため、及びメモリ内に前記一次セル及び二次セルをストアするためにグラフィックエンジンを動作するステップ、前記残りのデータは、一次のサブルーチン呼び出しコマンドを含み、前記一次セルは、二次のサブルーチン呼び出しコマンドを含み、前記サブルーチン呼び出しコマンドの各々は、セルの１つ及び前記セルの１つによって決められるフィーチャセットがイメージされるべきターゲットの一部を識別し、及び
（ｂ）前記一次セルを前記メモリから抽出し、前記一次呼び出しコマンドの少なくとも２つの各々によって識別された前記ターゲットの一部に前記一次セルによって定められたフィーチャセットのイメージ化を制御する前記ビーム制御データの一部を生成することによって、前記一次の呼び出しコマンドの少なくとも２つの各々に応答することによって、且つ前記二次セルを前記メモリから抽出し、前記二次呼び出しコマンドの少なくとも２つの各々によって識別された前記ターゲットの一部に前記二次セルによって定められたフィーチャセットのイメージ化を制御する前記ビーム制御データの一部を生成することによって、前記二次の呼び出しコマンドの少なくとも２つの各々に応答することによって含む前記残りのデータと前記メモリの内容に応答して前記ビーム制御データを生成するために前記グラフィックエンジンを動作するステップ、
を有することを特徴とする方法。
【請求項２８】
前記ステップ（ｂ）は、前記ビーム制御データがピクセル形式であるように行なわれることを特徴とする請求項２７に記載の方法。
【請求項２９】
前記ビーム制御データに応答して前記少なくとも一つのビームが前記ターゲット上にパターンをイメージ化するようにする構成のシーケンスにおいてビームシステムを動作するステップを有することを特徴とする請求項２７に記載の方法。
【請求項３０】
前記ビームシステムは、前記ステップ（ｃ）中に前記ターゲットに対して少なくとも１つのビームのラスター走査を行なうことを特徴とする請求項２９に記載の方法。
【請求項３１】
少なくとも一つのビームがターゲット上にパターンをイメージ化するようにするためのビーム制御データを生成する方法であって、前記方法は、
（ａ）少なくとも３−レベルの階層及び少なくとも１つの一次セルと少なくとも１つの二次セルを含むセルを有する階層イメージデータのセットを受信し、前記階層イメージデータの前記一次セルの各々及び前記二次セルの各々に応答して前記制御データを生成し、メモリにストアするためにグラフィックエンジンを動作するステップ、前記階層イメージデータは、サブルーチン呼び出しコマンドを含む残りのデータを含み、且つ前記サブルーチン呼び出しコマンドの各々は、１つの前記ビーム制御データセルと前記ビーム制御データセルによって決められたフィーチャセットがイメージされるべき前記ターゲットの一部を識別し、及び
（ｂ）１つの前記ビーム制御データセルを前記メモリから抽出することによって前記サブルーチン呼び出しコマンドの少なくとも２つの各々に応答することによって含む、前記残りのデータと前記メモリの内容に応答して前記ビーム制御データを生成するために前記グラフィックエンジンを動作するステップ、
を有することを特徴とする方法。
【請求項３２】
前記ステップ（ｂ）は、前記ビーム制御データがピクセル形式であるように行なわれることを特徴とする請求項３１に記載の方法。
【請求項３３】
前記ビーム制御データに応答して、前記少なくとも１つのビームが前記ターゲット上にパターンをイメージ化するようにする構成のシーケンスにおいてビームシステムを動作するステップを有することを特徴とする請求項３２に記載の方法。
【請求項３４】
前記ビームシステムは、前記ステップ（ｃ）中に前記ターゲットに対して少なくとも１つのビームのラスター走査を行なうことを特徴とする請求項３３に記載の方法。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
（技術分野）
本発明は、少なくとも一つのビーム（例えば、少なくとも一つのレーザビームまたは少なくとも一つの電子ビーム）がターゲット上にパターンを生成するために制御されるパターンの生成方法及び装置に関する。代表的な実施例において、本発明は、階層的イメージデータのセットの少なくとも一つのセルがキャッシュされ、その後、ビームがパターン化されたマスクを生成するのに適したビーム制御データ（ピクセルまたはベクトル形式を有する）へのイメージデータの変換中に、抽出されるマイクロリソグラフィ方法及び装置である。
【０００２】
（背景技術）
パターン生成装置は、例えば、集積回路を製造するために使用されるマスクの製造のようなマイクロリソグラフィへの適用ばかりでなく、他の応用にも使用される。
【０００３】
あるパターンの生成システムは、ターゲット上のパターンを定めるピクセルを書き込むために、ビームの強さが変化されるにしたがって、レーザまたは電子ビームがラスター走査パスに沿ってターゲット上でスイープされる。このようなシステムの実現化において、ターゲットは移動可能なステージ上に取り付けられ、ビームは第１の軸（ターゲット面の）に沿って前後に移動し、一方このステージは、第１の軸に垂直な軸に沿ってビームを移動させる。ラスター書込み手段を用いるパターン生成の動作において、生のイメージデータのセットが受信され、ラスターエンジンが生のイメージデータの各セットをラスター化するために用いられ、ラスター化されたデータのセットを発生する。ラスター化されたデータは、それが一つのラスター走査中にシーケンシャルに書き込まれるようにピクセルのシーケンスを有するという意味で"ピクセル形式"である。このシーケンスにおける各ピクセルは、バイナリーの値（０または１）か、グレースケール値であることができる。
【０００４】
1996年7月2日にR.L. Teitzel他に付与されたUSP5,533,170は、パターン生成装置用のラスターエンジンを開示し、階層構造が呼び出されたサブルーチンによって構成されることができるように、ラスターエンジンによって処理されたデータはサブルーチンのように呼び出されるデータオブジェクトを含むことができる。
【０００５】
他のパターン生成システムは、生のイメージデータをピクセル形式にラスター化しないが、しかし、代わりに、生のイメージデータを“ベクトル形式”のデータに変換する。このベクトル形式のデータは、ベクトルのシーケンスを有し、その各々は（走査を始める）位置及び走査の長さ（または間隔）を示す大きさを決める。一般に、その位置は基準点からのずれ（オフセット）として表わされる。ベクトル形式のデータのセットに応答して、ビームは、走査のシーケンスを行ない、その走査において、ビームは、ターゲット上の第１の位置に向けられ、第１の位置で開始し、示された長さまたは間隔を有する走査（例えば、小さな領域上のラスター走査）を実行し、その後、ターゲット上の第２の位置にジャンプし、第２の位置に対応する長さまたは間隔を有する他の走査を実行し、以下同様である。
【０００６】
パターン生成システム（時々、“整形スポットシステム(shaped spot system)”と呼ばれる。）の他の形式において、ターゲットは可変整形ビームのショットのシーケンスによって露光される。各々のショットを行なうために、ターゲットの選ばれた領域が選ばれた時間の間可変整形ビームに露光されるように、ビームが（例えば、ビームの経路において開口を操作することによって）制御される。この形式のシステムは、生のイメージデータをベクトルのシーケンスを有するベクトル形式のデータに変換し、各々のベクトルは、（ショットのシーケンスにおける）一つのショットに対して（ターゲット上の）位置を定め及びビーム制御素子の構成を示す大きさがこのショット（及び任意にショット間隔）に対して選択され、投射されたビームの形状を定める。
【０００７】
マイクロリソグラフィのために用いられる他のパターン生成システムは、“セルプロジェクション(cell projection)”システムとして知られている。セルプロジェクションシステムは、ターゲットをショットのシーケンスに露光するために用いられる。各々のショットを行うために、ビームがウエハによって決められた孔のパターンを通してターゲットに投射される。ウエハは、孔の一つのパターンか、或いは孔の２つ以上のパターンかのいずれかを決めることができる。各々のショットを行うために、ビームが選ばれた時間の間、ウエハの孔の選ばれたパターンを通ってターゲットの選ばれた領域へ通過するように、ビームが制御される。この形式のシステムは、生のイメージデータをベクトルのシーケンスを有するベクトル形式のデータに変換し、各ベクトルが一つのショットに対してターゲット上の位置を決め、そして制御ビットが（ウエハの）孔のどのパターンを通ってビームがショットに対して通過するかを決める。
【０００８】
特許請求の範囲を含むこの開示の全体を通して、“ビーム制御データ”という表現は、パターンがイメージデータのセットに応答してパターン生成システムによってターゲット上にイメージされるものを決めるビーム制御ハードウェアの構成（または構成のシーケンス）を直接決めるデータ（ベクトル形式であるか、或いはピクセル形式であるか）を示す。本発明のパターン生成システムは、一般に、生の階層データから最適な階層イメージデータを生成し、この最適な階層イメージデータに応答してビーム制御データを生成する中間ステップを伴って、生のイメージデータを受け取り、それに応答してビーム制御データを発生する。“最適な”という用語は、“改善された”（例えば、グラフィックエンジンへ転送される減少されたデータ量や、受け入れ可能に低い処理時間を有するビーム制御データに変換される能力のような特性の改善された組み合わせを実施する）ばかりでなく、“最大程度まで改善された”（たとえば、関連した特性の最良の可能な組み合わせを実施する）をあらわす広い意味に用いられる。一つの例において、本発明のパターン生成システムは、階層イメージデータ（２次元ビットマップを示す）のセットを受け取り、ラスター化して、ラスター走査の間、ターゲットへ書き込まれるピクセルのシーケンスを決めるビーム制御データ（ピクセル形式）を生成する。
【０００９】
本方法の一つの特徴は、階層イメージデータに応答してビーム制御データを生成するための方法である。好適な実施例において、本発明は、階層ＣＡＤ設計、例えば従来のＧＤＳ-IIフォーマットにおける設計を示す階層イメージデータをラスター化する。階層設計は、レイアウト上（例えば、レイアウト上の異なる位置を示す適切なオフセットを有するセル上で繰返すことによって）の異なる位置にそれぞれ配置されるべき形状（または形状のセット）を示すデータと一緒に（“セル”として知られた実体において）グループ化する。階層設計のセルは、それが繰返されたフィーチャまたはフィーチャのセットを決めるデータから成っているという意味で“簡単”でり、または他のセル（他のセルは複雑なセル内に含まれることができるが、必ずしも含まれる必要はない）の参照を含み、繰返されたフィーチャまたはフィーチャのセット（他のセルを含んだり、或いは参照することなく）を決めるデータを任意に含むという意味で“複雑”である。
【００１０】
階層イメージデータのセットは、１つまたはそれ以上の“一次”セル（各セルはレイアウト上で繰返されるフィーチャまたはフィーチャのセットを決める）及び追加データも含む。追加データは、レイアウトの繰返のないフィーチャを示すデータ及び一次セルを参照するデータを含む。各々の一次セルは、それ自体１つまたはそれ以上のセル（ここでは、二次セルとして示される）の参照（レファレンス）を含む。同様に、各々の二次セルは、１つまたはそれ以上のセル（ここでは三次セルとして示される）の参照を含み、及び階層の高いレベルに対して同様である。もし、一次セルが二次セルの参照を含んでいないならば、我々は、“２−レベル”の階層データ（２−レベルの階層を有するレイアウトを決める）としての階層データの全体セットを参照しなければならない。もし、少なくとも一つの一次セルが二次セルの参照を含むならば、我々は、“Ｎ-レベル”（Ｎは２より大きい）の階層データを有するレイアウトを決める“Ｎ-レベル”の階層データとして階層データの全体セットを参照しなければならない。階層イメージデータとは対照的に、“平坦な”形式のイメージデータ（“平坦な”レイアウトを定める）は一次セルを含まない。
【００１１】
用語“セルのインスタンティエーション(instantiation)”は、ここでは、セルがレイアウト上の特定の位置へコピーされることを示すセルの参照を指示するために用いられる。
【００１２】
一般的なＩＣレイアウトにおける増大するフィーチャの数、一般的なフィーチャの臨界寸法の縮尺サイズ（例えば、ゲートサイズ）、及びセリフ（serifs)やスキャッタバー(scatter bars)を加えることによって、臨界寸法の物理的減少を容易にするように試みるプロセスの修正管理スキームへの必要性によって、階層は避けることができなくなる。階層設計は、レイアウトの繰返しビルディングブロック（構成要素）の一致した構造に影響を及ぼす。ＤＲＡＭまたはＦＰＧＡ(field-programmable gate array）デバイスは、例えば、１０9のフィーチャより大きな平坦なフォーマット数を規定することができる。形状（ジオメトリ）あたり８〜１０バイトの場合、平坦なレイアウトで実現されるとき、この設計は、設計を示す生のイメージデータが記憶装置からラスタエンジンへ送られる場合困難な帯域幅の問題を抱える。発明者たちは、それが平坦な設計以外の階層設計（一般的にＮレベルの階層、ここで、Ｎは２より大きい）として、このような設計を実現することが望ましいことを認識した。何故ならば、セルのインスタンティエーションあたりの情報の唯一の新しいピース(piece)がレイアウト上のセルのオフセットであり、その結果このオフセットを送ることが十分であるからである。階層設計の圧縮係数は、セルのインスタンティエーションの数に比例して決まる。従って、セルのみを一旦グラフィックエンジン（インスタンティエーションあたりの関連したオフセットと共に）へ送ることは、必要な通信の帯域幅を劇的に減少する。
【００１３】
1994年12月6日に付与されたUSP5,371,373は、セルプロジェクションシステム（図３のマスク２１として識別される、図６のマスク２４-２８の選択された１つを含む）及び図６のマスク２９（図３のマスク２１として識別される）と図３のマスク１９及びメカニズム１８を含む整形スポットシステムを有する電子ビームリソグラフィ装置を教示する。この装置は、２−レベル階層イメージデータに応答してオブジェクト１５上にパターンを生成する。マスク２４-２８の各々は、階層イメージデータの異なる一次セルに応答して製造される。マスク２４-２８の製造に加えて、リソグラフィデータ（ベクトル形式）は、階層イメージデータを処理することによって生成される。データ制御システム８は、以下のようなリソグラフィデータの流れに応答する：一次セルの１つを指定するリソグラフィデータの連続して受信された各ユニットに応答して、オブジェクト１５上にセルを投影するために、ビームが対応するマスク２４，２５，２６，２７、または２８を通過する単一の“セルプロジェクション”スポットが得られ、及び一次セルの１つを指定しないリソグラフィデータの連続して受信された各ユニットに応答して、オブジェクト１５上に選択されたビーム形状を投影するために、ビームが適切に制御された一対のマスク１９と２９を通過する単一の“整形されたビーム”スポットが得られる。しかし、USP5,371,373は、Ｎ−レベルの階層イメージデータ（Ｎは２より大きい）に応答して、オブジェクト１５上にパターンを生成するための方法を何ら教示していない。
【００１４】
リソグラフィデータ用のファイルサイズを大きくする傾向は、リソグラフィのために使用されるパターン生成システムにおけるデータ転送速度の増加より速いようである。速い転送速度に頼るよりむしろ充分な処理パワー及び大きな利用可能なメモリに頼ることが効果的で、実行可能なパラダイム(paradigm: 体系）を提供する。従って、発明者たちは、大量の繰り返しデータがグラフィックエンジンへ一回だけ転送され、各大量のデータが繰り返し参照される限りグラフィックエンジンのメモリに保持されるようにして、パターン生成システムのグラフィックエンジンへ転送されなければならないデータ量を減少することが望ましいことを認識した。代表的な実施例において、本発明は、ターゲット上にイメージ化されるパターンを決める形状データ(geometry data)を含むイメージデータ（ＧＤＳ IIフォーマットにあることができる）の階層データ構造を探索し、イメージデータの最も著しく繰返されるセルを識別する。その後、このイメージデータは、その最も著しく繰返されるセルの各々がグラフィックエンジンへ一回だけ転送される（グラフィックエンジンのメモリにキャッシュするために）という意味で圧縮される。グラフィックエンジンは１回以上（適当なときに）メモリから各々のキャッシュされたセルを抽出するためにサブルーチン呼び出しコマンドを処理することができるように、サブルーチンの呼び出しコマンドもグラフィックエンジンへ転送される。従って、このグラフィックエンジンは、キャッシュされたセルのインスタンティエーションの一般的に高い数によって大きな伸張率で、本発明に従ってグラフィックエンジンへ転送された圧縮データを伸張する。このデータを一回だけ転送すること、グラフィックエンジンに転送されたデータのサブセットをキャッシュすること、及びキャッシュされたデータを繰り返し呼び出すことは、ダウンロードの障害を取り除く。
【００１５】
より詳細には、本発明は、Ｎ−レベル階層イメージデータ（Ｎは１より大きい、好ましくは２より大きい）のセットを定め、階層イメージデータをグラフィックエンジン（“ＧＥ”）へ転送し、且つＧＥのメモリに階層イメージデータのセルをキャッシュすることによって、グラフィックエンジン（例えば、ラスターエンジン）に転送されなければならないイメージデータの量を減少する。ＧＥは、キャッシュされたセルの部分または階層イメージデータのキャッシュされないエレメントの何れかであることができる階層イメージデータのエレメントに応答して、サブルーチン呼び出しコマンドを実行する。各サブルーチン呼び出しコマンドは、（ＧＥのメモリから）キャッシュされたセルを抽出し、抽出され、キャッシュされたセル及びオフセットを示すデータに応答して、（オフセットによって示されたターゲット上のある位置にあるセルによって決められたパターンをイメージ化するための）ビーム制御データを生成する。好適な実施例においては、ビーム制御データは、ピクセル形式であるが、代わりにベクトル形式であっても良い。
【００１６】
（本発明の概要）
本発明のパターン生成方法及びシステムの好適な実施例において、メモリを有するグラフィックエンジン（“ＧＥ”）は、メモリにストアされる少なくとも一つのセル（繰返されたフィーチャのセットを決める）に階層イメージデータのセット（ターゲット上にイメージ化されるべきパターンを決める）を受信し、ビーム制御データがそのイメージデータに応答して生成される。用語“フィーチャのセット”は、ここではパターンに生じるフィーチャまたはフィーチャのセットを示し、用語“繰返されるフィーチャのセット”は、パターンに繰り返し生じるフィーチャまたはフィーチャのセットを示すために用いられる。階層イメージデータは、残りのデータを含み、この残りのデータは、メモリにストアされた各セルに対する少なくとも２つのサブルーチン呼び出しコマンドを含み、また各サブルーチン呼び出しコマンドは、ターゲット上の位置及びメモリから抽出されるべきセルを示している。各サブルーチン呼び出しコマンドに応答して、ＧＥはメモリからセルを抽出し、及びサブルーチン呼び出しコマンドによって識別される位置で（また位置で始まる）ターゲット上にイメージされるべきフィーチャのセット（セルによって決められる）を決めるビーム制御データをアサートする。サブルーチン呼び出しコマンドは、キャッシュされるべき少なくとも一つのセル（例えば、一次セルに、そして一次セルの場合にそれは二次セルを識別する）ばかりでなく残りのデータに含んでいる、ＧＥへ転送されるイメージデータ全体に分布されることができる。
【００１７】
好適な実施例において、ＧＥは、メモリに階層イメージデータの各セルをキャッシュし、メモリからキャッシュされたセルを抽出し、抽出されたセルに応答してビーム制御データを生成することによって、各サブルーチン呼び出しコマンドに応答してビーム制御データのセットを生成する。他の実施例において、ＧＥは、階層イメージデータの各セルに応答してビーム制御データのセルを生成し、メモリにある各々のこのビーム制御データセル（ビーム制御データセルに相当するイメージデータセル以外）をキャッシュし、及びメモリからビーム制御データのキャッシュされたセルを抽出し、コマンドによって識別される位置（またはその位置で始まる）ターゲット上にイメージされるべきフィーチャのセット（抽出されたセルによって決められる）を決めるビーム制御データのセットの一部として抽出されたビーム制御データのセルをアサートすることによって、転送されたイメージデータの各サブルーチン呼び出しコマンドに応答する。最後の実施例において、各キャッシュされたビーム制御データのセルは、プリントジョブの全ライフタイムを通してＧＥのメモリに静的に残っている。
【００１８】
本発明の幾つかの実施例は、生のイメージデータのセットからＧＥへ転送されるべき階層イメージデータを生成する方法及び装置を含む。
【００１９】
本発明の好適な実施例にしたがって生成されたビーム制御データは、ピクセル形式であるけれども、本発明の他の実施例によるベクトル形式のビーム制御データが生成される。本発明によって生成されたビーム制御データは、ＧＥによってビームシステムへアサートされることができ、ビームシステムによって制御されるビームがターゲット上に所望のパターン（転送された階層イメージデータによって特定される）をイメージ化する構成（または構成のシーケンス）にビームシステムを配置する。
【００２０】
幾つかの実施例において、本発明のシステのＧＥはラスターエンジンである。これらの実施例において、ＧＥに転送される階層イメージデータのセットの少なくとも一つのセルは、一旦このラスターエンジンのメモリに（好ましくは、ビットマップとして）キャッシュされる。そしてこのラスターエンジンは、ラスター走査されたビームがセルによって決められたピクセルをイメージ化するターゲット上の各々の位置（またはそこから始まるターゲット上の位置）を示すサブルーチン呼出コマンド（転送されたイメージデータに含まれる）に応答して、ストアされたセルを繰り返し呼び出す。
【００２１】
本発明の他の特徴は、キャッシュされるべきセルを含む最適化された階層イメージデータのセットへ生のイメージデータを転送するために、生の階層イメージデータのセットの階層を解析し、生のイメージデータの階層構造を最適化することによって、ＧＥのメモリにキャッシュされるべき階層イメージデータのセルを決める方法及び装置である。これは、解析ソフトウエアでプログラムされたプロセッサによって達成される。最適化された階層イメージデータは、好ましくは、以下のファクタの最適な組み合わせを達成する：Ｇｅへ転送されるべきデータ量の減少及び転送されたイメージデータからビーム制御データを生成し、ラスター化を行なうのに必要な時間を最少化する（または受け入れ可能な制限内に保持する）。最適化された階層イメージデータは２つのクラスのデータ、すなわち、キャッシュされるべき（またはキャッシュされるべきビーム制御データへ変換される）１つまたはそれ以上のセル、及び残りのデータを有する。残りのデータは、レイアウトの非繰り返しフィーチャを示すデータ、及びサブルーチン呼出コマンドを含む。最適化された階層イメージデータは、シーケンシャルに送られるそれらの残りのデータと一緒に、一旦ＧＥへ送られる（例えば、ラスター化とほぼ同じ）。
【００２２】
グラフッィクエンジンが階層データ構造のセルをキャッシュせず、代わりに、イメージデータの流れにそれらに存在するフィーチャ上にシーケンシャルに動作するグラフィックエンジン（例えば、ラスターエンジン）を含む従来のパターン生成システムと比較して、本発明を実施するシステムは、階層イメージデータをグラフッィクエンジンに送るのに必要な帯域幅を大きく減少して（例えば、２０分の１まで）実現される。
【００２３】
（好適な実施例の詳細な説明）
図１を参照して、本発明の好適な実施例を説明する。図１のシステムは、生の階層イメージデータのセットに応答して、ターゲット８上にパターンをイメージ化するプリントジョブを行うためにプログラムされ、構成されている。ターゲット８は、それがこのようなプリントジョブの結果としてパターン化された後に、集積回路を形成するために用いられるマスク（例えば、クロムがコーティングされたクォーツガラス片）である。図１のシステムは、ビーム装置６、及びイメージデータ生成装置２とグラフィックエンジン４を含むパターン生成装置を有する。ビーム装置６は、ターゲット８上にビーム（電子ビームまたはレーザビーム）を投射し、ターゲット上のスポットをイメージ化し、且つターゲット上に一連のピクセルをイメージ化するために、ターゲット８に対してラスター走査路に沿ってビームをスイープする。ターゲット８は移動可能なステージ（図示せず）上に取り付けられており、ステージ及びビームの双方の移動がターゲットの基準フレーム内のラスター走査路に沿ってビームをスイープさせるように制御される。
【００２４】
イメージデータ生成装置２は、ターゲット８上にイメージされるべきパターンを示す生の階層イメージデータのセットに応答して、最適化された階層イメージデータのセットを発生するように構成される。装置２は、一般に、プログラムされたプロセッサとして実現され、以下、時々“プロセッサ”２と呼ばれる。好適な実施例において、グラフィックエンジン４は、プロセッサ２から最適化された階層イメージデータを受信するために接続されたラスターエンジン（メモリ１０、１１及びプロセッサ１２を含む）であり、メモリ１０に最適化された階層イメージデータの少なくとも一つのセルをストアし、最適化された階層イメージデータ（メモリ１０からストアされたデータを抽出することによって）に応答して、ビーム制御データ（またはそこへのプリカーサ）を発生し、メモリ１１にビーム制御データ（またはビーム制御データへのプリカーサ）をストアし、且つメモリ１１からビーム制御データを抽出し（またはメモリ１１からプリカーサデータを抽出し、それに応答してビーム制御データを発生し）、そしてビーム制御データをビーム装置６へ送って（またはビーム制御データを発生し、それをまたはそれのプリカーサをメモリ１１にストアすることなくシステム６へ直接送って）、装置６がターゲットに対してビームのラスター走査を実行させる。図１のパターン生成システムによって装置６へアサートされるビーム制御データは、ピクセル形式である。しかし、本発明の他の実施例はベクトルフォーマットを有するビーム制御データを発生することが意図される。
【００２５】
ラスターエンジン４のプロセッサ１２は、識別されたセルがメモリ１０から抽出されるべきであることを示し、そしてこのセルによって決められたパターンがイメージ化されるターゲット上の位置（または位置で始まる）を識別する階層イメージデータ（サブルーチン呼び出しコマンドと呼ばれる）の各々のエレメントに応答して、サブルーチンの呼び出しを実行するようにプログラムされる。このサブルーチン呼び出しコマンドは、一般にイメージ化されるべきパターンの位置を決めるオフセット値を識別することによってターゲット上の位置を識別し、後者の位置はターゲット上の位置に対応する。各サブルーチン呼び出しコマンドは、メモリ１０から抽出され、キャッシュされたセルの一部である（例えば、抽出された一次メモリが、一次セルの残りが抽出される前に、二次のセルが抽出されるべきであることを示すサブルーチン呼出コマンドを含む場合）か、または、それは最適化された階層イメージデータのキャッシュされない一部である。代表的な実施例において、各サブルーチン呼び出しコマンドは、オフセット（ターゲット８上にイメージ化されるべき全パターンの単一の識別された位置からの）を示すデータを含み、プロセッサ１２がメモリ１０からキャッシュされたセルを抽出するようにし、抽出されたセルに応答して、（セルによって決められたパターンをイメージ化するため、またはオフセットによって示された位置で始めるための）ビーム制御データを生成する。
【００２６】
図１のシステムの代替実施例において、プロセッサ１２は、プロセッサ２からラスターエンジン４へ転送される最適化された階層イメージデータの各々のセルに応答してビーム制御データのセルを生成し、ラスターエンジン４は、プロセッサ２から抽出されたイメージデータの対応するセルではなく、ビーム制御データのセルをメモリ１０または１１にキャッシュする。各々のキャッシュされたビーム制御データは、プリントジョブの全ライフタイムにわたってメモリに静的に残っている。ビーム制御データの各キャッシュされたセルに対するサブルーチン呼び出しコマンドは、プロセッサ２から受信された最適化された階層イメージデータの各セットにわたって分布されている。一つのこのコマンドに応答してラスターエンジン４によって実行される各サブルーチンの呼び出しは、メモリ１０（または１１）からのビーム制御データのセルを抽出して、コマンドによって決められる位置（すなわち、コマンドに含まれるオフセットによって決められる位置）で始まるターゲット８上の抽出されたセルによって決められたパターンをイメージ化する。
【００２７】
図１のシステムの実施例において、プロセッサ２は、２−レベルの生の階層イメージデータに応答して最適化された２−レベルの階層イメージデータを生成するためのソフトウェアでプログラムされ、このソフトウェアは以下に規定された変数と定数を参照する。
【００２８】
イメージデータの全セットによって規定された形状(geometries)の全数：ＴＧＣ；
セルの境界のあるボックスの大きさ：ＣＥＸ；
セルのインスタンティエーションの数（イメージデータの全セット内）：ＣＮＩ；
アレー化されたプリミティブス(primitives)を含むセルのローカルフィギュアの数(local figure count)：ＣＦＣ；
イメージデータがインスタンティエーションされるイメージデータの全セットの全サイズ（量）のセルの割合：ＣＰＯ＝(ＣＮＩ)(ＣＦＣ)/ＴＧＣ；
イメージデータの全セットに対する残りの平面出力：ＲＦＯ＝［１−ΣＣＰＯ］ＴＧＣ、ここで、Σは全体の解析されたセル；
セルの等価メモリ：ＣＥＭ＝ａ×ＣＦＣ（ここで、ａは定数、一つの実施例では、ａ＝８）；
その復号されたインスタンティエーションによるセルの出力（すなわち、キャッシュされたセルの全インスタンティエーションを実現するためにセルを（セルがＧＥにキャッシュされた後に）繰り返し呼び出す必要がある、最適化された階層イメージデータに含まれるべきデータ量）：ＣＩＯ＝ｂ×ＣＮＩ（ここで、ｂは定数、一つの実施例では、ｂ＝１２）；
利用可能なＧＥのメモリ（すなわち、キャッシュするために利用可能なラスターエンジン４のメモリ１０のその部分の大きさ）：ＧＥＭ；
ライブラリーの出力（すなわち、最適化された階層イメージデータの各キャッシュされたセルの全呼び出しを実現するために用いられる最適化された階層イメージデータの全セットのキャッシュされない“呼び出しデータ”部分の量。呼び出しデータは、キャッシュされたセルを参照する全てのサブルーチン呼び出しコマンドを含む。）：ＬＯ＝ΣＣＩＯ（全体の解析されたセルをまとめる）；
キャッシュされるべき階層イメージデータのセルを含む最適化された階層イメージデータの全セットの投射された大きさ：ＰＦＳ=ＬＯ＋ＲＦＯ；及び
ＧＥに転送されるべき最適化されたイメージデータのセットの最大の大きさ（キャッシュされるべきそれらのセルを含まない）：ＦＳＬ（例えば、ＦＳＬは１３ギガバイトである。）
【００２９】
プロセッサ２は、有名なソフトウェアでプログラムされる場合、２−レベルの生の階層イメージデータのセットに応答して、最適化された２−レベルの階層イメージデータのセットを生成するために、指示されたシーケンスで以下の動作を行なう。
【００３０】
１．開始：生の階層イメージデータによって決められる階層グラフを識別し、及び各キャッシュＣＰＯに関する生のイメージデータのセルをソートするインデックス構造を形成する。
２．前に解析されなかった最も高いＣＰＯを有するセルでスタートする。もし、ＣＥＭ≦ＧＥＭならば、ステップ３へ行き、もし、ＣＥＭ＞ＧＥＭならば、終了へ行く（すなわち、最適化されたイメージデータの（キャッシュされるべき）セルとして生のイメージデータの如何なるセルも含まない。）。
３．ＣＥＭ≦ＧＥＭである各セルに対して、ＣＩＯを計算する。その後、もし、ＬＯ＋ＣＩＯ＜ＦＳＬならば、ステップ５に行き、その他はステップ４へ進む。
４．ＣＩＯを減少するために、できるだけ現在のセルの多くのインスタンティエーションを含む新しいセルを作る。
５．セルのためのＣＥＭがＣＥＭ≦ＧＥＭを満足することをチェックすることによって復号するライブラリーのためセルの大きさをチェックする（もし、ステップ５がステップ３に続くなら、古いセルの大きさ、またはステップ５がステップ４に続くなら、新しいセルの大きさ）、及び必要に応じて（すなわち、セルのためのＣＥＭがＧＥＭより大きいなら）、セルを多数のセルにする。
６．ＧＥＭ（利用可能なＧＥメモリの量）、及びＬＯ（ライブラリーの出力）を更新する。
７．最適化されたイメージデータの全セットの投射サイズ（“ＰＥＳ”）を計算し、もし、ＰＦＳ＞ＦＳＬならば、ステップ２へ行き、その他はステップ８へ進む。
８．終了。
【００３１】
例えば、ステップ４において、現在のセルのインスタンティエーションの４０×４０のリストが新しいセルにグループ化されることができる。これは、インスタンティエーションの近似に頼る方法で具現化される。多くの、小さなセルの、大きなセルへのこのようなグループ化は、大きな係数によって（例えば、元の４.４７×１０9のインスタンティエーションから２.８×１０6のインスタンティエーションへ１６００の係数によって）最適化されたイメージデータの最終バージョンにおいてセルのインスタンティエーションの数を減少する。従って、最適化された階層のイメージデータの残りの（キャッシュされない）部分のその結果のセットのサイズは、管理することができるサイズに減少することができる。
【００３２】
図１のシステムの好適な実施例において、プロセッサ２は、Ｍ−レベルの生の階層イメージデータ（ここで、Ｍは１より大きい任意の整数）に応答して、最適化されたＮ−レベルの階層イメージデータ（ここで、Ｎは１より大きい任意の整数）を生成するためのソフトウェアでプログラムされる。これらの実施例において、プロセッサ２は、最も大きなセル割合の出力（上記定義されたＣＰＯ）を有する生のイメージデータの４つのセルを２−レベルの階層にグループ化するように試みる。一般に、生のイメージデータのセットから生成された最適化されたＮ−レベルの階層イメージデータ（ＧＥのメモリにキャッシュされるべきセルを含む）の階層レベルの数を増加することによって、ＧＥに転送されるべき最適化された階層イメージデータの量が減少される。
【００３３】
好ましくは、プロセッサ２は、プロセッサが生成する最適化された階層イメージデータのセットの平坦化を遅らせるようにプログラムされる。ここで、このコンテクストにおける“平坦化”は、最適化されたデータのセットのセル（またはサブセル）の各々（データは最適化されたデータのセットの残りの部分を含む）がラスターエンジン４へ送られるシーケンスの決定を示す。
【００３４】
また、好ましくは、プロセッサ２は、最も低い階層レベル（“トランク”）から最も高い階層レベル（プリミティブ）へ進められる“アレー化するオペレータ”に対してアレーをマップ化するようにプログラムされる。（生のイメージデータに応答して、最適化された階層イメージデータの発生中）ブラウジングのいずれかの点にあるセルは、それらの埋め込まれたサブツリー(sub-tree)を完全に含む。プロセッサ２がセルを扱うとき、これは、セルに含まれる全サブツリーを扱うことと等価である。これは、最適化された階層イメージデータへ階層の１より多いレベルの本来の復号を容易にする。
【００３５】
次に、階層イメージデータに応答して最適化された階層イメージデータを生成するために、プロセッサ２をプログラムするためのソフトウェアの好適な実施例を説明する。この例のために、Ｎ_ｇ形状及びＮ_セルを参照するセル（“セル_Ａ”）を考え、最適化された階層イメージデータは、これらのセルの“ｃ”（ここで、ｃは整数）のセット（“ＨＩ”）を含むと仮定する：ＨＩ＝｛セル_Ａ_１-セル_Ａ_Ｎ_ｃ｝。また、ＨＩにおける各セルは、少なくとも一つの形状（すなわち、Ｎ_ｇはセットにおける各セルに対してゼロより大きい）及びセットＨＩにおける各セルは、最適化された階層イメージデータの全セットにおいて少なくとも２倍生じることを仮定する。
【００３６】
２−レベルの階層を有する最適化された階層イメージデータを特徴づけるために、ソフトウェアは、（各セル_Ａ_ｉに対して）セルのＮ_ｇ形状を多くのフレームに集める。そしてそれらの各々は、ターゲット上の特定の領域（例えば、大きさ４０×４０ミクロンの領域）をカバーするようにされ、ソフトウェアは残りのデータのセットと共にセルのセットＨＩ（各セルはフレームのシーケンスを有する）として最適化された階層イメージデータを生成する。残りのデータは、セットＨＩのセルのいずれにも含まれない非繰り返しデータ（フレームに集められることもできる）、及び最適化されたイメージデータの全セットの座標系 (coordinate system)における各セルの各インスタンティエーションを決める“呼び出しデータ”を有する。この呼び出しデータは、最適化された階層イメージデータの全セットの座標系における各セルの各インスタンティエーションに対するオフセット、及び呼び出される各セルへの絶対アドレス（セルを有する形状のリストのためのアドレス）を含む、セルの各インスタンティエーションのためのサブルーチン呼び出しコマンドを含むのが好ましい。
【００３７】
３−レベル階層を有する生のイメージデータに応答して３−レベルの最適化された階層イメージデータを生成するために、ソフトウェアは、（各セル_Ａ_ｉに対して）少なくとも一つのサブセル（“サブセル”のセットは少なくとも一つのサブセルを有する）を識別する。ここで、サブセルのセットにおける各サブセルは、セル内に繰り返し生じる。ソフトウェアは、以下のデータによってセルを特徴づける：サブセット；及びセルの非繰り返しデータ（非繰り返しデータはフレームに集められることができる）を有する残りのセルデータのセット及びセル内の各サブセルの各インスタンティエーションを決める呼び出しデータ。ソフトウェハは全てのサブセル（セットＨＩの全てのセルの）を決める（キャッシュされるべき）データ、キャッシュされるべき残りのセルデータ（“第１のセルデータ”）及び追加の残りのデータのセットとして最適化された階層イメージデータの全セット生成する。
【００３８】
第１の残りのセルデータは、セルのセット（ＨＩ）を決め、これらのセルの各々は、サブルーチン呼び出しコマンドのシーケンス及びセルの残りのデータを有し、サブルーチン呼び出しコマンドの各々は、キャッシュされたサブセルの一つのインスタンティエーションのためであり、セルのための残りのセルデータは、セルの非繰り返しデータを有する。一般に、第１の残りのセルデータは、セルの中の一つの「セルの残りのデータ」で点在されたサブルーチン呼び出しコマンドのシーケンス（キャッシュされたサブセルをインスタンティエーションするための）を有し、セルの中の他の一つの「セルの残りのデータ」で点在された多くのサブルーチン呼び出しコマンド（キャッシュされたサブセルをインスタンティエーションするための）が続く、等々である。一般に、第１の残りのデータのサブルーチン呼び出しコマンドの各々は、セットＨＩのセルの１つ（“呼び出しセル”）のコーディネートシステムにおけるサブセルのインスタンティエーションに対するオフセット、及び呼び出される各サブセルに対する絶対アドレス（サブセルを含む形状のリストがキャッシュされるアドレス）を有する。追加の残りのデータのセット（キャッシュされるべきでない）は、セットＨＩ（非繰り返しデータはフレームに集められることができる）のセルの一部でないイメージデータの最適化された階層セットの非繰り返しデータ、及び最適なされた階層イメージデータの全セットにおける各セルの各インスタンティエーションを決める呼び出しデータを含む。
【００３９】
呼び出しデータは、最適化された階層イメージデータの全セットの座標系における各インスタンティエーションのためのセット、及び呼び出されるべき各セルへの絶対アドレス（セルを有する形状及びサブルーチン呼び出しコマンドのリストのためのアドレス）を含むのが好ましい。呼び出しデータの各サブルーチン呼び出しコマンドに応答して、ＧＥはキャッシュされたセルを抽出し、続いて抽出されたセルのサブルーチン呼び出しコマンドを実行し、抽出されたセルのサブルーチン呼び出しコマンドの１つに応答して抽出された各サブセルのデータを抽出されたセルの「セルの残りのデータ」で点在させる。
【００４０】
代わりに、３−レベル階層を有する生のイメージデータに応答して２−レベルの最適化された階層イメージデータを生成するために、ソフトウェアは（各セル_Ａ_ｉに対して）、サブセルセットにおける各サブセルがセル内に繰り返し生じ、少なくとも一つのサブセル（すなわち、少なくとも一つのサブセルの“サブセル”セット）を識別し、ソフトウェアは以下のデータ：サブセルのセット；及び残りのセルデータのセットによってセルを特徴づける。残りのセルデータは、セルの非繰り返しデータ（非繰り返しデータがフレームに集められる）、及びセル内の各サブセルの各インスタンティエーションを決める呼び出しデータを有する。残りのデータのセットが、セットＨＩの各セルに対する残りのセルデータ（この残りのセルデータはフレームに集められることができる）、セットＨＩのいずれのセルの一部でない非繰り返しデータ（非繰り返しデータもフレームに集められることができる）、及び修正された呼び出しデータ（各セルの呼び出しデータ及び生のイメージデータの呼び出しデータから得られる）を有する場合、ソフトウェアは、全てのサブセル（セットＨＩの全てのセルの）を決めるデータ（キャッシュされるべき）；及び残りのデータのセットとして最適化された階層イメージデータの全セットを生成する。修正された呼び出しデータは、最適化されたイメージデータの全セットにおける各サブセルの各インスタンティエーションを決める。修正されたデータは、好ましくは、最適化された階層イメージデータの全セットの座標系における各サブセルの各インスタンティエーションに対するオフセット、及び呼び出されるべき各サブセルへの絶対アドレス（サブセルを有する形状のリストに対するアドレス）を含んで、サブセルの各インスタンティエーションに対するサブルーチン呼び出しコマンドを含む。
【００４１】
３−レベル階層を有する生のイメージデータに応答して３−レベル（または２−レベル）の最適化された階層イメージデータを生成するための前述の方法は、本発明による帰納法でＭ−レベル階層を有する生のイメージデータに応答してＮ−レベルの最適化された階層イメージデータを生成するように容易に一般化される。これは、与えられたブランチにおける終端セルから参照しているセルまで（例えば、セットＨＩからセル_Ａまで）動作することによって行なわれる。同様のことがセルのアレーに対しても真であることに留意されたい。階層の追加のレベルを使用することの利点は、最適化された階層イメージデータを決める（グラフィックエンジンへ転送されるべき）ファイルの大きさをさらに減少することである。
【００４２】
より一般的には、実施例のクラスにおいて、本発明は、生の階層イメージデータのセットに応答して階層の少なくとも２−レベルを有する階層イメージデータを生成するようにプログラムされたプロセッサ（例えば、図１のプロセッサ２）であり、その結果、階層イメージデータは、残りのデータ及びすくなくとも１つのセルを含み、各セルは、パターンのフィーチャセットを決定し、残りのデータは少なくとも２つのサブルーチン呼び出しコマンドを含み、且つサブルーチン呼び出しコマンドの各々は、プロセッサが以下の（ａ）〜（ｃ）に対してソフトウェアでプログラムされている場合、少なくと１つのセルのセル及びセルによって決められたフィーチャセットがイメージされるべきターゲットの一部を識別する。
【００４３】
（ａ）生のイメージデータのための階層グラフを決め、この階層イメージデータの仮のバージョンの一次階層グラフとして階層グラフを識別し、且つ生のイメージデータのセットの全大きさに対するそれらの個々の大きさによる仮の階層グラフのセルをソートする（例えば、ソートするインデックス構造を決める）；
【００４４】
（ｂ）サイズが階層イメージデータの仮のバージョンの全大きさに対して最も大きい仮の階層グラフのセルの１つを識別し、そして、もし、セルの一つの大きさがキャッシュ可能な大きさを越えないならば、階層イメージデータのセルとしてセルの一つの包含によって、階層イメージデータの残り部分の大きさが所定の最大の大きさを越えるか否かを決める；
【００４５】
（ｃ）もし、階層イメージデータのセルとしてセルの一つの含有によって、階層イメージデータの残り部分の大きさが所定の最大の大きさを越えるならば、セルの一つの多重インスタンティエーションを含み、キャッシュ可能な大きさを越えない大きさを有する新しいセルを識別し、セルの一つの多重インスタンティエーションをこの新しいセルで置き換えることによって、階層イメージデータの仮の階層グラフ及び仮のバージョンを更新し、それによって、階層イメージデータの更新された階層グラフ及び更新されたバージョンを決定する。そして、もし、更新された階層イメージデータの残り部分の大きさが所定の最大の大きさを越えないならば、更新された階層イメージデータを階層イメージデータとして識別する。
【００４６】
また、生の階層イメージデータのセットに応答して階層の少なくとも２−レベルを有する階層イメージデータのセットを生成するための方法は、本発明の範囲内である。その結果、階層イメージデータは、残りのデータ及び少なくとも１つのセルを含み、各セルは、パターンのフィーチャのセットを決定し、残りのデータは、少なくとも２つのサブルーチン呼び出しコマンドを含み、且つ、サブルーチン呼び出しコマンドの各々は、少なくとも一つのセルのセル及びセルによって決められたフィーチャのセットがイメージされるべきターゲットの一部を識別する。前記方法は、以下ステップを有している：
【００４７】
（ａ）生のイメージデータのための階層グラフを決め、この階層イメージデータの仮のバージョンの仮の階層グラフとして階層グラフを識別し、且つ生のイメージデータのセットの全大きさに対するそれらの個々の大きさによる仮の階層グラフのセルをソートする（例えば、ソートするインデックス構造を決める）；
【００４８】
（ｂ）サイズが階層イメージデータの仮のバージョンの全大きさに対して最も大きい仮の階層グラフのセルの１つを識別し、そして、もし、セルの一つの大きさがキャッシュ可能な大きさを越えないならば、階層イメージデータのセルとしてセルの一つの包含によって、階層イメージデータの残り部分の大きさが所定の最大の大きさを越えるか否かを決める；
【００４９】
（ｃ）もし、階層イメージデータのセルとしてセルの一つの含有によって、階層イメージデータの残り部分の大きさが所定の最大の大きさを越えるならば、セルの一つの多重インスタンティエーションを含み、キャッシュ可能な大きさを越えない大きさを有する新しいセルを識別し、セルの一つの多重インスタンティエーションをこの新しいセルで置き換えることによって、階層イメージデータの仮の階層グラフ及び仮のバージョンを更新し、それによって、階層イメージデータの更新された階層グラフ及び更新されたバージョンを決定する。そして、もし、更新された階層イメージデータの残り部分の大きさが所定の最大の大きさを越えないならば、更新された階層イメージデータを階層イメージデータとして識別する。
【００５０】
生の階層イメージデータのセットに応答して、グラフィックエンジンへ転送されるべき階層イメージデータのセットを生成するための方法は、本発明の範囲内である。その結果回動イメージデータは、階層の少なくとも２−レベルを有し、残りのデータ及び少なくとも一つのセルを含み、各々のセルはパターンのフィーチャセットを決め、残りのデータは、少なくとも２つのサブルーチン呼び出しコマンドを含み、サブルーチン呼び出しコマンドの各々は、少なくとも一つのセルのセル、及びセルによって決められるフィーチャセットがイメージされるべきであるターゲットの一部を識別し、前記方法は、
生のイメージデータのための階層グラフを決め、前記階層グラフを有する階層イメージデータの仮のバージョンを決めるステップと、
階層イメージデータの仮のバージョンを変更して、生のイメージデータのデータ量に対する減少されたデータ量、及びグラフィックエンジンにおける生のイメージデータからビーム制御データの生成に必要な時間に対してグラフィックエンジンにおける最適化された階層イメージデータからビーム制御データの生成に必要な減少された時間の最適的な組み合わせを達成する階層イメージデータの最適化されたバージョンを決めるステップとを有する。
【００５１】
例えば、図１のシステムの実施例において、プロセッサ２は、フィギュア・オブ・メリットを各候補セル(candidate cell)に割当てることによって生の階層イメージデータに応答して最適化された階層イメージデータを生成するため、及び最適化された階層イメージデータのセルを決めるために割当てられたフィギュア・オブ・メリットを用いるためのソフトウェアでプログラムされる。このフィギュア・オブ・メリット（“ＦＯＭ”）は、ある意味で、以下に多くの利点が候補セルをキャッシュし、それを少なくとも２回（サブルーチン呼び出しコマンドに応答するそれぞれのとき）抽出することによって得られるかを示している。ＦＯＭｓは、ＦＯＭの減少（または増加）順にストアされ、ＦＯＭが最小の値を越える（または最大値より小さい）セルのみが最適化された階層イメージデータのセル（キャッシュされるべき）として包含のための適格性がある。ＦＯＭが最小値を越え（または最大値より小さい）、そしてプログラマによって課せられた如何なる他の基準を満足するセルは、最適化された階層イメージデータのキャッシュされるべきセルとして実際に含まれる。ＦＯＭが最小値を越えない（または最大値を越える）各々のセル、またはプログラマによって課せられた他の基準（もしあるなら）の１つも満足しない各々のセルは、最適化された階層イメージデータの残りの（キャッシュされない）部分に含まれる平坦なイメージデータによって置き換えられる。
【００５２】
例えば、そのＦＯＭは、節約(savings)と大きさ(size)の比（節約/大きさ)である。ここで、“節約”とは全てのイメージデータファイル（ＧＥへ転送されるべき）が、最適化された階層イメージデータにおいてキャッシュされたセルを呼び出すためのキャッシュされないサブルーチン呼び出しコマンド共に、セル（キャッシュされるべきセルとして）を含むことによって減少されるバイトの数である。及び
“大きさ”とは、セルがＧＥメモリ（もし、セルがそこにキャッシュされたなら）において占有するバイトの数である。
代わりに、ＦＯＭは、上記定義された“節約”の値のみであっても良い（先の例における“節約と大きさ”の比ではなく）。
【００５３】
プロセッサが処理されたイメージデータをグラフィックエンジンへ転送する前にプロセッサが受け取る生のイメージデータについていろいろな動作を行わせるソフトウェアでプロセッサ（例えば、図１のプロセッサ２）をプログラムすることは通常のことである。このような動作の例は、生のイメージデータの分解及び継ぎ合わせであり、また生のイメージデータの形状を他の形式、例えばEtec System, Inc.によって市販されているパターン生成装置に採用されているアルタ・バイナリー・フォーマット（Alta Binary Format：ABF)へ変換することである。本発明の幾つかの実施例において、プロセッサ２をプログラムするソフトウェアは、従来のソフトウェアの機能ばかりでなく本発明を実現するのに必要な機能を達成する従来のソフトウェアの変形バージョンである。
【００５４】
階層イメージデータのセルが本発明によりキャッシュされるＧＥメモリは、ＧＥの特定目的のキャッシュメモリ（これらのセルをキャッシュする目的のためのみに用いられる）であっても良く、またはそれがＧＥの多目的メモリ（多目的メモリは、これらセルのキャッシュ以外の少なくとも１つの目的のためＧＥによって用いられる）の一部であっても良いことを理解すべきである。
【００５５】
また、本発明の幾つかの形態はここに説明されたけれども、本発明は、上述した及び示された特定の実施例及び説明された特定の方法に限定されるべきでないことを理解すべきである。
【図面の簡単な説明】
【００５６】
【図１】本発明を実施するシステムのブロック図である。
【図１】
2005521071.tif 000003
【国際調査報告】
2005521071.tif 000004
2005521071.tif 000005
2005521071.tif 000006