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