(57)【特許請求の範囲】
【請求項１】
基板に描画を行う描画装置であって、
基板に向けて描画用のビームを出射するビーム出射部と、
前記ビームを偏向する偏向部と、
基板を保持するステージ部と、
基板上の複数の描画点の描画順序である経路を求める経路決定部と、
を備え、
前記経路決定部が、
含まれる描画点の密度が高いほど小さい分割領域となるように、２次元の描画領域を複数の分割領域へと分割する領域分割工程と、
求められる経路が前記複数の分割領域を経由する経由順序を決定する領域経由順序決定工程と、
前記経由順序に基づいて前記複数の分割領域のそれぞれにおいて第１描画点と第２描画点とを決定する描画端点決定工程と、
前記複数の分割領域のそれぞれにおいて所定の経路決定アルゴリズムを用いて前記第１描画点から前記第２描画点に至る分割領域内の点を経由する部分経路を求める部分経路決定工程と、
前記経由順序に従って各第２描画点を次の分割領域内の第１描画点と接続する部分経路接続工程と、
を実行し、
前記領域分割工程が、
前記描画領域を大きさがほぼ等しい所定数の分割領域へと分割する単純分割工程と、
前記複数の描画点の密度に基づいて前記所定数の分割領域から選択されたものに対して前記単純分割工程を繰り返す繰返工程と、
を有することを特徴とする描画装置。
【請求項２】
請求項１に記載の描画装置であって、
最初の前記単純分割工程により分割された分割領域間の経由順序が予め定められており、２回目以降の前記単純分割工程により分割された分割領域間の経由順序が、分割前の分割領域に対する経由態様に基づいて予め定められており、前記領域分割工程と前記領域経由順序決定工程とが実質的に同時に行われることを特徴とする描画装置。
【請求項３】
請求項２に記載の描画装置であって、
２回目以降の前記単純分割工程により分割された分割領域間の経由順序が、フラクタル曲線生成アルゴリズムを用いて予め決定されていることを特徴とする描画装置。
【請求項４】
請求項３に記載の描画装置であって、
前記複数の分割領域のそれぞれが矩形であり、前記フラクタル曲線生成アルゴリズムがヒルベルト曲線を生成するアルゴリズムであることを特徴とする描画装置。
【請求項５】
請求項２ないし４のいずれかに記載の描画装置であって、
最初の前記単純分割工程により分割された分割領域間の経由順序がループ状であることを特徴とする描画装置。
【請求項６】
請求項１ないし５のいずれかに記載の描画装置であって、
前記繰返工程が、前記単純分割工程による分割後の分割領域内に存在する描画点が所定数以下になるまで再帰的に実行されることを特徴とする描画装置。
【請求項７】
基板を撮像する撮像装置であって、
基板に照明光を照射する照明部と、
基板の画像データを取得する撮像部と、
基板を保持するステージ部と、
前記撮像部を前記ステージ部に対して相対的に移動させる移動機構と、
基板上の複数の撮像位置の撮像順序である経路を求める経路決定部と、
を備え、
前記経路決定部が、
含まれる撮像位置の密度が高いほど小さい分割領域となるように、基板上の所定領域を複数の分割領域へと分割する領域分割工程と、
求められる経路が前記複数の分割領域を経由する経由順序を決定する領域経由順序決定工程と、
前記経由順序に基づいて前記複数の分割領域のそれぞれにおいて第１撮像位置と第２撮像位置とを決定する撮像位置決定工程と、
前記複数の分割領域のそれぞれにおいて所定の経路決定アルゴリズムを用いて前記第１撮像位置から前記第２撮像位置に至る分割領域内の撮像位置を経由する部分経路を求める部分経路決定工程と、
前記経由順序に従って各第２撮像位置を次の分割領域内の第１撮像位置と接続する部分経路接続工程と、
を実行し、
前記領域分割工程が、
前記所定領域を大きさがほぼ等しい所定数の分割領域へと分割する単純分割工程と、
前記複数の撮像位置の密度に基づいて前記所定数の分割領域から選択されたものに対して前記単純分割工程を繰り返す繰返工程と、
を有することを特徴とする撮像装置。
【請求項８】
請求項７に記載の撮像装置であって、
最初の前記単純分割工程により分割された分割領域間の経由順序が予め定められており、２回目以降の前記単純分割工程により分割された分割領域間の経由順序が、分割前の分割領域に対する経由態様に基づいて予め定められており、前記領域分割工程と前記領域経由順序決定工程とが実質的に同時に行われることを特徴とする撮像装置。
【請求項９】
請求項８に記載の撮像装置であって、
２回目以降の前記単純分割工程により分割された分割領域間の経由順序が、フラクタル曲線生成アルゴリズムを用いて予め決定されていることを特徴とする撮像装置。
【請求項１０】
請求項９に記載の撮像装置であって、
前記複数の分割領域のそれぞれが矩形であり、前記フラクタル曲線生成アルゴリズムがヒルベルト曲線を生成するアルゴリズムであることを特徴とする撮像装置。
【請求項１１】
請求項８ないし１０のいずれかに記載の撮像装置であって、
最初の前記単純分割工程により分割された分割領域間の経由順序がループ状であることを特徴とする撮像装置。
【請求項１２】
請求項７ないし１１のいずれかに記載の撮像装置であって、
前記繰返工程が、前記単純分割工程による分割後の分割領域内に存在する撮像位置が所定数以下になるまで再帰的に実行されることを特徴とする撮像装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数の点の経由順序を求める技術に関し、特に、基板上の複数の描画点に描画を行う描画装置や基板上の複数の撮像位置における画像を取得する撮像装置に適する。
【０００２】
【従来の技術】
半導体基板（以下、「基板」という。）に回路パターンを描画する描画装置や、基板上に描画されたパターン等を検査のために撮像する撮像装置では、基板上の多数の描画点または撮像位置（以下、「対象点」と総称する。）にアクセスが行われる。例えば、描画装置では基板上の多数の対象点に順に電子ビームを照射することにより、基板上に多数の点（微小パターン）が描画される。このとき、描画に要する時間は、対象点を経由する経路の距離にほぼ比例して長くなる。
【０００３】
従来は、全ての対象点を経由する経路は、対象点のデータが入力された順序であったり、Ｘ座標軸およびＹ座標軸を定義しておいて対象点のＸ座標またはＹ座標の値の昇降順（いわゆる「ＸＹソート」）で決められることが多かった。
【０００４】
【発明が解決しようとする課題】
ところが、ＸＹソートはアルゴリズムが単純であるため、電算機等を用いて経路を速やかに求めることができるが、対象点が広範囲に散らばっている場合、求められる経路が非常に長くなるという問題を有している。
【０００５】
そこで、複雑な計算アルゴリズムを用いて可能な限り短い経路を求める方法も多く研究されているが、対象点が多くなると指数関数的に計算時間が長くなるとともに実用化するには高価な演算回路が必要となってしまう。
【０００６】
また、特開２００１−１９５１１２号公報のように対象点が存在する領域を等分割する処理を複数通りシミュレーションして分割後の１つの領域の大きさを予め決定しておき、分割された個々の領域において複雑なアルゴリズムを用いて経路を求めるという方法も提案されている。ところが、この方法では予めシミュレーションを行う分時間を要し、また、対象点が局所的に集中している場合には、対象点が集中している領域に基づいて全体が不必要に細かく分割され、好ましい経路が得られない場合がある。
【０００７】
本発明は上記課題に鑑みなされたものであり、好ましい経路を容易に求めることを主たる目的としている。
【０００８】
【課題を解決するための手段】
請求項１に記載の発明は、基板に描画を行う描画装置であって、基板に向けて描画用のビームを出射するビーム出射部と、前記ビームを偏向する偏向部と、基板を保持するステージ部と、基板上の複数の描画点の描画順序である経路を求める経路決定部とを備え、前記経路決定部が、含まれる描画点の密度が高いほど小さい分割領域となるように、２次元の描画領域を複数の分割領域へと分割する領域分割工程と、求められる経路が前記複数の分割領域を経由する経由順序を決定する領域経由順序決定工程と、前記経由順序に基づいて前記複数の分割領域のそれぞれにおいて第１描画点と第２描画点とを決定する描画端点決定工程と、前記複数の分割領域のそれぞれにおいて所定の経路決定アルゴリズムを用いて前記第１描画点から前記第２描画点に至る分割領域内の点を経由する部分経路を求める部分経路決定工程と、前記経由順序に従って各第２描画点を次の分割領域内の第１描画点と接続する部分経路接続工程とを実行し、前記領域分割工程が、前記描画領域を大きさがほぼ等しい所定数の分割領域へと分割する単純分割工程と、前記複数の描画点の密度に基づいて前記所定数の分割領域から選択されたものに対して前記単純分割工程を繰り返す繰返工程とを有する。
【０００９】
請求項２に記載の発明は、請求項１に記載の描画装置であって、最初の前記単純分割工程により分割された分割領域間の経由順序が予め定められており、２回目以降の前記単純分割工程により分割された分割領域間の経由順序が、分割前の分割領域に対する経由態様に基づいて予め定められており、前記領域分割工程と前記領域経由順序決定工程とが実質的に同時に行われる。
【００１０】
請求項３に記載の発明は、請求項２に記載の描画装置であって、２回目以降の前記単純分割工程により分割された分割領域間の経由順序が、フラクタル曲線生成アルゴリズムを用いて予め決定されている。
【００１１】
請求項４に記載の発明は、請求項３に記載の描画装置であって、前記複数の分割領域のそれぞれが矩形であり、前記フラクタル曲線生成アルゴリズムがヒルベルト曲線を生成するアルゴリズムである。
【００１２】
請求項５に記載の発明は、請求項２ないし４のいずれかに記載の描画装置であって、最初の前記単純分割工程により分割された分割領域間の経由順序がループ状である。
【００１３】
請求項６に記載の発明は、請求項１ないし５のいずれかに記載の描画装置であって、前記繰返工程が、前記単純分割工程による分割後の分割領域内に存在する描画点が所定数以下になるまで再帰的に実行される。
【００１４】
請求項７に記載の発明は、基板を撮像する撮像装置であって、基板に照明光を照射する照明部と、基板の画像データを取得する撮像部と、基板を保持するステージ部と、前記撮像部を前記ステージ部に対して相対的に移動させる移動機構と、基板上の複数の撮像位置の撮像順序である経路を求める経路決定部とを備え、前記経路決定部が、含まれる撮像位置の密度が高いほど小さい分割領域となるように、基板上の所定領域を複数の分割領域へと分割する領域分割工程と、求められる経路が前記複数の分割領域を経由する経由順序を決定する領域経由順序決定工程と、前記経由順序に基づいて前記複数の分割領域のそれぞれにおいて第１撮像位置と第２撮像位置とを決定する撮像位置決定工程と、前記複数の分割領域のそれぞれにおいて所定の経路決定アルゴリズムを用いて前記第１撮像位置から前記第２撮像位置に至る分割領域内の撮像位置を経由する部分経路を求める部分経路決定工程と、前記経由順序に従って各第２撮像位置を次の分割領域内の第１撮像位置と接続する部分経路接続工程とを実行し、前記領域分割工程が、前記所定領域を大きさがほぼ等しい所定数の分割領域へと分割する単純分割工程と、前記複数の撮像位置の密度に基づいて前記所定数の分割領域から選択されたものに対して前記単純分割工程を繰り返す繰返工程とを有する。
【００１５】
請求項８に記載の発明は、請求項７に記載の撮像装置であって、最初の前記単純分割工程により分割された分割領域間の経由順序が予め定められており、２回目以降の前記単純分割工程により分割された分割領域間の経由順序が、分割前の分割領域に対する経由態様に基づいて予め定められており、前記領域分割工程と前記領域経由順序決定工程とが実質的に同時に行われる。
【００１６】
請求項９に記載の発明は、請求項８に記載の撮像装置であって、２回目以降の前記単純分割工程により分割された分割領域間の経由順序が、フラクタル曲線生成アルゴリズムを用いて予め決定されている。
【００１７】
請求項１０に記載の発明は、請求項９に記載の撮像装置であって、前記複数の分割領域のそれぞれが矩形であり、前記フラクタル曲線生成アルゴリズムがヒルベルト曲線を生成するアルゴリズムである。
【００１８】
請求項１１に記載の発明は、請求項８ないし１０のいずれかに記載の撮像装置であって、最初の前記単純分割工程により分割された分割領域間の経由順序がループ状である。
【００１９】
請求項１２に記載の発明は、請求項７ないし１１のいずれかに記載の撮像装置であって、前記繰返工程が、前記単純分割工程による分割後の分割領域内に存在する撮像位置が所定数以下になるまで再帰的に実行される。
【００２０】
【発明の実施の形態】
図１は本発明の第１の実施の形態に係る描画装置１の全体構成を示す図である。描画装置１は基板９に描画用の電子ビームを出射するヘッド部２、基板９を保持するステージ３、ヘッド部２に対してステージ３を相対的に移動させるステージ駆動部３１、並びに、ヘッド部２およびステージ駆動部３１に接続されたコンピュータ４を有する。
【００２１】
ヘッド部２は電子ビームを発生するビーム出射部２１、および、電子ビームを適切に基板９へ導く光学ユニット２２を有し、光学ユニット２２は電子ビームの形状を成形するビーム成形部２２１、電子ビームを偏向する偏向部２２２、および、電子ビームを収束させつつ基板９に導く対物レンズ部２２３を有する。
【００２２】
ビーム出射部２１より出射された電子ビームは、ビーム成形部２２１において偏向されるとともに複数のアパーチャにより所望のビーム形状に成形され、偏向部２２２により主走査（基板９上の領域間の走査）および副走査（領域内の走査）の偏向を受ける。その後、電子ビームは対物レンズ部２２３により基板９上に収束され、基板９上に描画が行われる。なお、ビーム成形部２２１、偏向部２２２および対物レンズ部２２３の配置は上記例に限定されず、各構成の順序や各構成の一部分の配置が適宜変更されてよい。また、走査領域をさらに分割した副々走査が行われてもよい。
【００２３】
ステージ駆動部３１はステージ３を図１中のＸ方向に移動させるＸ方向移動機構３２、および、Ｙ方向に移動させるＹ方向移動機構３３を有する。Ｘ方向移動機構３２はモータ３２１にボールねじ（図示省略）が接続され、モータ３２１が回転することにより、Ｙ方向移動機構３３がガイドレール３２２に沿って図１中のＸ方向に移動する。Ｙ方向移動機構３３もＸ方向移動機構３２と同様の構成となっており、モータ３３１が回転するとボールねじ（図示省略）によりステージ３がガイドレール３３２に沿ってＹ方向に移動する。
【００２４】
コンピュータ４は、図２に示すように、各種演算処理を行うＣＰＵ４１、基本プログラムを記憶するＲＯＭ４２および各種情報を記憶するＲＡＭ４３をバスラインに接続した一般的なコンピュータシステムの構成となっている。バスラインにはさらに、情報記憶を行う固定ディスク４４、各種情報の表示を行うディスプレイ４５、操作者からの入力を受け付けるキーボード４６ａおよびマウス４６ｂ、光ディスク、磁気ディスク、光磁気ディスク等のコンピュータ読み取り可能な記録媒体８から情報の読み取りを行う読取装置４７、並びに、ヘッド部２やステージ駆動部３１に制御信号を送り出す通信部４８が、適宜、インターフェイス（Ｉ／Ｆ）を介する等して接続される。
【００２５】
コンピュータ４には、事前に読取装置４７を介して記録媒体８からプログラム４４１が読み出され、固定ディスク４４に記憶される。そして、プログラム４４１がＲＡＭ４３にコピーされるとともにＣＰＵ４１がＲＡＭ４３内のプログラムに従って演算処理を実行することにより（すなわち、コンピュータがプログラムを実行することにより）、コンピュータ４が各種構成を制御して描画を実行させる。
【００２６】
図３は、ＣＰＵ４１がプログラム４４１に従って動作することにより、ＣＰＵ４１、ＲＯＭ４２、ＲＡＭ４３、固定ディスク４４等が実現する機能構成を示すブロック図である。図３において制御部５１および経路決定部５２がＣＰＵ４１等により実現される機能を示す。なお、これらの機能は専用の電気的回路により実現されてもよく、部分的に電気的回路が用いられてもよい。
【００２７】
描画装置１による描画が行われる際には、予め複数の描画点の位置を示す描画点データ４０１、およびビームの大きさや形状等の描画条件を示す描画条件データ４０２がキーボード４６ａや読取装置４７等を介して作業者により固定ディスク４４に記録される。描画点データ４０１は図１中のＸおよびＹ方向の座標（所定の基準点に対する相対座標）をパラメータとする座標データとなっている。描画点データ４０１は固定ディスク４４から経路決定部５２に送信され、後述する経路決定部５２の各構成により処理されることで描画点の経由順序が求められ、制御部５１に送信される。
【００２８】
制御部５１はステージ駆動部３１を制御して基板９上の１つの半導体チップに相当する部分をヘッド部２の真下に移動させ、各描画点の経由順序および描画条件データ４０２に従ってヘッド部２を制御することにより、１つのチップ内の所定の領域内に描画を行う。
【００２９】
図４は、経路決定部５２が、基板９上の所定の領域内における描画点の経由順序（描画順序）である経路を決定する動作の流れを示す図である。以下、経路決定動作について図３を参照しながら図４に沿って説明を行う。
【００３０】
まず、経路決定部５２の分割領域生成部５２１が固定ディスク４４に記憶されている描画点データ４０１を受け取り、描画点を含む基板９上の所定領域を大きさがほぼ等しい所定数の分割領域へと単純な分割を行う（ステップＳ１１）。例えば、図５に示すようにＸおよびＹ座標により定義される２次元の領域６に描画点６０が散在する場合、領域６はＸおよびＹ方向に関してそれぞれを２等分した４つの分割領域へと分割される。図６は取得された分割領域６１を例示する図である。なお、図６では右下側（（＋Ｘ）側かつ（−Ｙ）側）の分割領域６１に符号６１ａを付しており、左下側（（−Ｘ）側かつ（−Ｙ）側）の分割領域６１に符号６１ｂを付している。
【００３１】
続いて、分割領域生成部５２１は、各分割領域内に存在する描画点６０の個数を数え、予め決められた上限点数を超える描画点６０を含む分割領域をさらにＸおよびＹ方向に関してそれぞれを２等分する（すなわち、４つの矩形の分割領域へと単純な分割を行う。）（ステップＳ１２，Ｓ１３）。図６において、上限点数を５とした場合、５個以上の描画点６０を有する分割領域６１ａおよび分割領域６１ｂのそれぞれが図７に示すようにさらに分割領域６２へと４等分される。なお、図７では、分割領域６１ａ（図６参照）から生じた分割領域６２のうち左上側（（−Ｘ）側かつ（＋Ｙ）側）のものに符号６２ａを付し、分割領域６２ａの左側および下側の分割領域６２にはそれぞれ、符号６２ｂ，６２ｃを付している。
【００３２】
ステップＳ１２およびＳ１３は分割により生成された各分割領域に対して実行されるため、実際の演算処理ではすべての分割領域内に存在する描画点６０の個数が上限点数以下となるまで分割が再帰的に繰り返される。図７の例においては、分割領域６２ａに上限点数より多い描画点６０が存在するため、図８に示すように分割領域６２ａがさらに４等分され、分割領域６３（左上側の分割領域から反時計回りに符号６３ａ，６３ｂ，６３ｃ，６３ｄを順に付している。）とされる。これにより、すべての分割領域内に存在する描画点６０の個数が上限点数以下となって分割が終了し（ステップＳ１２）、分割領域６１〜６３が確定する。
【００３３】
次に、分割領域生成部５２１は生成された分割領域６１〜６３に対して、電子ビームが経由する分割領域間の順序（すなわち、最終的に求められる描画点６０間の経路が分割領域を経由する順序）が決定される（ステップＳ１４）。分割領域間の順序は任意の手法により決定されてもよいが、本実施の形態では矩形の分割領域の経由順序決定に適したヒルベルト曲線生成アルゴリズムを利用（以下、「ヒルベルト曲線の利用」と適宜略す。）して決定される。
【００３４】
なお、ヒルベルト曲線が利用される場合には分割領域間の順序が分割の経緯に基づいて決定されるため、ステップＳ１４はステップＳ１２，Ｓ１３と同時に行われることが好ましい。図４に示す動作は説明の便宜上ステップＳ１４を独立して示しているが、本実施の形態に係る描画装置１ではステップＳ１４はステップＳ１２，Ｓ１３と実質的に同時に行われる。以下、ヒルベルト曲線を利用して分割と同時に分割領域間の経由順序が決定される様子について説明する。
【００３５】
まず、ステップＳ１１において最初に分割された分割領域６１に対して、図９（ａ）に示すように、全分割領域６１を一周するループ状の経由順序７０が定められる。ただし、ループ状の経由順序としては、経由順序において最初の分割領域６１をいずれのものとするかにより、図９（ａ）ないし（ｄ）に示すように４通りの経由順序が想定されるため、装置および基板の仕様に応じていずれの経由順序が採用されてもよい。
【００３６】
図１０（ａ）ないし（ｌ）は、１つの分割領域が４つの分割領域へとさらに分割される際に（すなわち、２回目以降の分割の際に）、ヒルベルト曲線を利用した変換パターンに従って分割領域間の経由順序が分割前の分割領域に対する経由態様に基づいて予め定められている様子を示す図である。すなわち、各図の左側に示すように隣接する領域との経由順序が存在する場合、分割後の経由順序は各図の右側に示す順序とされる。
【００３７】
例えば、分割領域６１ｂにおいて隣接する分割領域６１との経由順序の関係は図１０（ｅ）の左側に示すものとなり、分割領域６１ｂが図７に示すように４等分されると、生成される４つの分割領域６２に対する経由順序は図１０（ｅ）の右側に示す順序とされる。
【００３８】
同様に、図６中の分割領域６１ａにおいては、４分割された分割領域６２（図７参照）に図１０（ｋ）に示す変換が適用される。さらに、図７中の分割領域６２ａは、図１０（ｋ）の右側の４つの領域のうち左上のものに対応することから、分割領域６２ａにおいて隣接する分割領域との経由順序の関係は図１０（ｇ）の左側に示すものとなる。したがって、分割領域６２ａがさらに分割される際には、図１０（ｇ）に示す変換が適用される。
【００３９】
以上のように、描画装置１ではヒルベルト曲線を利用した図１０（ａ）ないし（ｌ）に示す変換を予め定めておくことにより、分割と実質的に同時に分割領域間の経由順序が決定される。図１１は、図５に例示する領域６において分割と実質的に同時に求められる分割領域間の経由順序７２を示す図である。図１１に示す分割領域間の経由順序では、分割領域６２ｂが最初となり、分割領域６３ａが最後となる。
【００４０】
分割領域間の経由順序が決定されると、分割領域６１〜６３、分割領域間の経由順序および描画点６０の位置を示すデータが分割領域内経路生成部５２２に送られる。分割領域内経路生成部５２２は分割領域間の経由順序に基づいて、各分割領域における第１描画点および第２描画点を決定する。第１描画点としては、経由順序に従って手前となる分割領域に接する辺に近接するものが決定され、第２描画点としては次の分割領域と接する辺に近接するものが決定される（ステップＳ１５）。第１描画点および第２描画点は、次のステップにて求められる分割領域内の経路の端点として利用される。
【００４１】
なお、経由順序が最初の分割領域では、経由順序が最後の分割領域に接する辺に近接する描画点６０が第１描画点として決定され、経由順序が最後の分割領域では、経由順序が最初の分割領域に接する辺に近接する描画点６０が第２描画点として決定される。
【００４２】
図１２は、図１１中の分割領域６３ａ〜６３ｄを例に第１描画点および第２描画点（端点）が決定される様子を示す図である。なお、図１２では、分割領域間の経由順序は６３ｂ，６３ｃ，６３ｄ，６３ａの順である（図８および図１１参照）。分割領域６３ｂでは、順序が前の分割領域６２ｃと接する辺６４ａに近接する描画点６０が第１描画点６０１として決定され、順序が次の分割領域６３ｃと接する辺６４ｂに近接する描画点６０が第２描画点６０２として決定される。
【００４３】
同様に、分割領域６３ｃにおいて、辺６４ｂに近接する第１描画点６０１、および、順序が次の分割領域６３ｄと接する辺６４ｃに近接する第２描画点６０２が決定され、分割領域６３ｄにおいて、辺６４ｃに近接する第１描画点６０１、および、順序が次の分割領域６３ａと接する辺６４ｄに近接する第２描画点６０２が決定される。
【００４４】
分割領域間の経由順序が最後である分割領域６３ａにおいては、辺６４ｄに近接する描画点６０が第１描画点６０１として決定され、経由順序が最初である分割領域６２ｂと接する辺６４ｅに近接する描画点６０が第２描画点６０２ａとして決定される。図１１における他の分割領域６１，６２においても同様にして第１描画点６０１および第２描画点６０２が決定され、経由順序が最初である分割領域６２ｂでは、経由順序が最後の分割領域６３ａと接する辺に近接する描画点６０が第１描画点６０１とされる。
【００４５】
なお、１つの分割領域において第１描画点６０１と第２描画点６０２とが同一の描画点６０になってしまう場合は、第２候補の第１描画点６０１と第２描画点６０２とを求め、第１描画点６０１および第２描画点６０２のいずれかが第２候補へと変更される。
【００４６】
続いて、分割領域内経路生成部５２２により、所定の経路決定アルゴリズムを用いて、各分割領域において第１描画点６０１から第２描画点６０２に至る各描画点６０を経由する経路が求められる（ステップＳ１６）。すなわち、第１描画点６０１および第２描画点６０２を端点とする分割領域内の経路（以下、「部分経路」という。）が求められる。部分経路を求めるアルゴリズムには、例えば、局所探索法等が用いられる。図１３に局所探索法により求められた分割領域６３ａ〜６３ｄにおける部分経路７３を示す。
【００４７】
なお、端点決定と経路決定とを繰り返して最適な経路を求めるアルゴリズムが採用される場合には、上述のステップＳ１５とステップＳ１６とは実質的に同時に行われる。この場合、第１描画点６０１および第２描画点６０２のいずれもが上述の対応する辺（前後の分割領域に接する辺）に最も近接する点とはならないこともある。
【００４８】
その後、経路接続部５２３により分割領域間の経由順序に従って、各分割領域の第２描画点６０２が次の分割領域の第１描画点６０１に接続され（ステップＳ１７）、領域６における全体の経路が決定される。ただし、経由順序が最初の分割領域６２ｂの第１描画点は全体の経路の始点となり、最後の分割領域６３ａの第２描画点は終点となるため、これらの描画点の接続は行われない。
【００４９】
図１４は以上のようにして求められた経路７４を例示する図であり、経路７４は、分割領域６２ｂの第１描画点６０１ａから分割領域６３ａの第２描画点６０２ａへと至る経路となる。生成された経路７４は、既述のように制御部５１へと出力されてヘッド部２の制御に利用される。
【００５０】
以上、描画装置１について説明してきたが、描画装置１では描画点６０の密度が高い分割領域を選択しつつ再帰的に小さな分割領域へと分割することで不必要に領域が分割されてしまうことを防止しつつ各分割領域に含まれる描画点６０の個数を少なくすることができる。そして、各分割領域を経由する順序をヒルベルト曲線生成アルゴリズムを利用して分割とほぼ同時に速やかに求めた上で分割領域６１〜６３ごとの部分経路を求め、これらの部分経路を接続することにより全体の経路７４が求められる。その結果、経路を迅速かつ容易に求めることができる。
【００５１】
すなわち、高度なアルゴリズムを用いて領域６全体の経路を求めようとした場合、描画点の数に対して指数関数的に演算量が増えるため、短時間で経路を求めることができない。しかしながら、描画装置１では存在する描画点６０の個数が上限点数以下である分割領域６１〜６３に対して経路の算出が行われるため、全体の演算量を減らすことが可能となる。また、上述の領域分割の手法では、事前に分割領域の大きさを決定するためのシミュレーションを行う必要がないため、多品種少量生産の場合に特に有効となる。
【００５２】
なお、領域分割を再帰的に行う（すなわち、プログラムにおいて関数の呼び出しやオブジェクトの生成を再帰的に行う）ことにより、演算速度が向上され、短時間で経路を求めることができる。
【００５３】
また、描画装置１では、最初に分割された分割領域６１に対してループ状の経由順序が与えられることにより、最終的に得られる分割領域群において、経由順序が最初の分割領域と最後の分割領域とが必ず隣接することとなる。つまり、最終的に得られる分割領域間の経由順序もおよそループ状となり、経路の始点と終点とを近づけることができる。
【００５４】
これにより、１つの領域６への描画が完了した後に電子ビームの主走査（複数の領域６間の走査）を行って次の同様の領域６への描画を開始する際に、副走査（領域６内の走査）を行うための偏向を小さくすることができる。その結果、主走査が行われる際に、主走査と副走査との制御が互いに影響を及ぼし合うことが抑制されるとともに高精度な位置決めが要求される副走査の制御を短時間に行うことができる。
【００５５】
通常、描画装置において電子ビームを大きく偏向させて照射位置を長い距離だけ移動させる（ジャンプさせる)と描画される画像の精度が低下する現象が見られる。そのため、このような場合にはダミーデータを挿入する等して精度を維持する対策がなされる。描画装置１では、領域分割により領域６内における大きなジャンプが低減され、かつ、領域６間のジャンプの際にも副走査の偏向が小さく抑えられるため、精度の高い描画を速やかに行うことが実現される。
【００５６】
なお、図６において右上（（＋Ｘ）側かつ（＋Ｙ）側）の分割領域６１に描画点６０が存在しないと仮定した場合は、左上の分割領域６１から右下の分割領域６１ａへの移動の際に大きな偏向が必要となる可能性がある。この場合は、最初の分割による分割領域６１間の経由順序を図９（ｂ）に示すように決定することにより、電子ビームの偏向量の抑制が図られる。
【００５７】
図１５は本発明の第２の実施の形態に係る撮像装置１ａの全体構成を示す図である。撮像装置１ａは基板９を撮像することにより２次元画像のデータを取得する撮像部２ａ、基板９を保持するステージ３、撮像部２ａに対してステージ３を相対的に移動させるステージ駆動部３１、並びに、撮像部２ａおよびステージ駆動部３１に接続されたコンピュータ４を有する。撮像装置１ａは、第１の実施の形態に係る描画装置１のヘッド部２を撮像部２ａに置き換えたという点を除いて描画装置１と同様の構成となっており、対応する構成には同符号を付している。コンピュータ４の機能構成も図３と同様である。
【００５８】
撮像部２ａは、照明光を出射する照明部２３、基板９に照明光を導くとともに基板９からの光が入射する光学系２４、および、光学系２４により結像された基板９の像を電気的信号に変換する撮像デバイス２５を有する。
【００５９】
撮像装置１ａでは、基板９上の撮像位置の座標を示す撮像位置データが、第１の実施の形態にて説明した描画点データ４０１（図３参照）に代えて入力される。そして、撮像位置データが経路決定部５２の各構成により処理された後、決定された複数の撮像位置の経由順序である経路が制御部５１に送信される。制御部５１は決定された経路に従って撮像部２ａの真下に複数の撮像位置が順番に位置するようにステージ駆動部３１を制御し、撮像部２ａが複数の撮像位置の画像を順次取得する。取得された画像データは固定ディスク４４に記録される。
【００６０】
ここで、経路決定部５２が複数の撮像位置を経由する経路を決定する動作は第１の実施の形態と同様である。すなわち、図４に関する説明における描画点が撮像位置に置き換えられた処理が行われる。これにより、各撮像位置を経由する好ましい（短い）経路が求められ、効率のよい撮像が行われる。
【００６１】
なお、描画装置１や撮像装置１ａでは、基板９がアクセス対象とされるが、一般に、半導体基板、プリント配線基板、マスク用基板等では、描画点や撮像位置が局所的に偏在していることが多い。したがって、局所的な領域のみが細かく分割された分割領域が生成されることにより、非常に効率よく経路を求めることが実現される。すなわち、描画装置１や撮像装置１ａは回路が形成される基板あるいは回路形成に用いられる基板に特に適した装置であるといえる。
【００６２】
以上、本発明の実施の形態について説明してきたが、本発明は上記実施の形態に限定されるものではなく様々な変形が可能である。
【００６３】
分割領域間を経由する順序を決定する工程は、既述のように領域分割から独立して行われてもよく、この場合、経由順序を決定するアルゴリズムとしては任意のものが利用されてよい。また、上記実施の形態では最も簡単な例としてヒルベルト曲線を生成するアルゴリズムが利用されるが、他の平面充填型のフラクタル曲線を生成するアルゴリズムも利用可能である。例えば、（狭義の）ペアノ曲線またはシェルピンスキー曲線等のフラクタル曲線生成アルゴリズムが利用されてもよい。
【００６４】
ステップＳ１１またはＳ１３における領域の分割は４分割に限定されず、９分割等であってもよい。また、分割領域の形状は必ずしも正方形には限定されない。すなわち、分割の際に等分割以外の分割が行われてもよいし、さらには、三角形に分割されてもよい。なお、分割領域が三角形等の他の形状に分割される場合であっても、分割領域の形状に合わせたフラクタル曲線生成アルゴリズムを利用することが可能である。
【００６５】
ステップＳ１２，Ｓ１３において、各分割領域内の描画点６０の個数が上限点数以下となるまで再帰的に分割領域の分割が繰り返されるが、実質的に分割領域内に含まれる描画点６０の密度が高いほど小さな領域に分割されるのであれば他の分割基準が採用されてもよい。
【００６６】
図４に示す動作の流れは、可能な範囲内で適宜変更されてよい。例えば、端点となる描画点が接続されてから端点間の部分経路が求められてもよい。
【００６７】
上記実施の形態では、最初の分割により生じた分割領域６１間の経由順序がループ状に決定されるが、描画装置１のような電子ビームの主走査および副走査という概念が存在しない場合はループ状でない経由順序が採用されてもよい。例えば、第２の実施の形態に係る撮像装置１ａにおいて、図６に示す領域６が検査すべき領域である場合、前に検査を行った領域が領域６の左側に隣接し、次に検査すべき領域が領域６の右側に存在する場合は、４つの分割領域６１に対して図１０（ａ）に示す変換アルゴリズムが採用されることが好ましい。これにより、領域間の移動の際の撮像装置１ａにおけるステージ３の移動距離を小さく抑えることが実現される。
【００６８】
【発明の効果】
請求項１ないし６の発明では、複数の描画点を経由する好ましい経路を容易に求めることができ、効率よく複数の描画点の描画を行うことができる。
【００６９】
請求項７ないし１２の発明では、複数の撮像位置を経由する好ましい経路を容易に求めることができ、効率よく複数の撮像位置に対する撮像を行うことができる。
【００７０】
また、請求項１ないし４並びに請求項７ないし１０の発明では、短時間で経路を求めることができる。
【００７１】
また、請求項５および１１の発明では、経路の始点と終点とを近づけることができる。
【００７２】
また、請求項６および１２の発明では、経路決定アルゴリズムによる演算時間を短くすることができる。
【図面の簡単な説明】
【図１】  描画装置の全体構成を示す図である。
【図２】  コンピュータの構成を示す図である。
【図３】  コンピュータの機能構成を示すブロック図である。
【図４】  複数の描画点を経由する経路を求める動作の流れを示す図である。
【図５】  描画点が散在する領域を例示する図である。
【図６】  領域が分割される様子を説明するための図である。
【図７】  領域が分割される様子を説明するための図である。
【図８】  領域が分割される様子を説明するための図である。
【図９】  最初に分割された分割領域間の経由順序を示す図である。
【図１０】  ２回目以降に分割された分割領域間の経由順序を求める様子を示す図である。
【図１１】  分割領域間の経由順序を示す図である。
【図１２】  経路が求められる様子を説明するための図である。
【図１３】  経路が求められる様子を説明するための図である。
【図１４】  求められた経路の一例を示す図である。
【図１５】  撮像装置の全体構成を示す図である。
【符号の説明】
１  描画装置
１ａ  撮像装置
２ａ  撮像部
３  ステージ部
４  コンピュータ
６  領域
９  基板
２１  ビーム出射部
２３  照明部
３１  ステージ駆動部
５２  経路決定部
６０  描画点
６１，６１ａ，６１ｂ，６２，６２ａ〜６２ｃ，６３ａ〜６３ｄ  分割領域
７２  経由順序
７３  部分経路
７４  経路
２２２  偏向部
５２１  分割領域生成部
５２２  分割領域内経路生成部
５２３  経路接続部
６０１，６０１ａ  第１描画点
６０２，６０２ａ  第２描画点
Ｓ１１〜Ｓ１７  ステップ
【図１】
0004201160.tif 000002
【図２】
0004201160.tif 000003
【図３】
0004201160.tif 000004
【図４】
0004201160.tif 000005
【図５】
0004201160.tif 000006
【図６】
0004201160.tif 000007
【図７】
0004201160.tif 000008
【図８】
0004201160.tif 000009
【図９】
0004201160.tif 000010
【図１０】
0004201160.tif 000011
【図１１】
0004201160.tif 000012
【図１２】
0004201160.tif 000013
【図１３】
0004201160.tif 000014
【図１４】
0004201160.tif 000015
【図１５】
0004201160.tif 000016