(57)【特許請求の範囲】
【請求項１】
複数の図形要素のベクトルデータである入力データをランレングスデータである出力データに変換するデータ変換方法であって、
ａ）入力データに含まれる複数の図形要素のベクトルデータに基づいて、一の図形要素を、代表的な形状を有する代表図形要素の集合である代表図形要素群と比較し、前記代表図形要素群に前記一の図形要素の形状と同じ形状の代表図形要素が含まれる場合に、前記代表図形要素を示す代表図形識別子を前記一の図形要素に関連付け、前記代表図形要素群に前記一の図形要素の形状と同じ形状の代表図形要素が含まれない場合に、前記一の図形要素の形状と同じ形状を有する新たな代表図形要素を前記代表図形要素群に追加するとともに前記新たな代表図形要素を示す代表図形識別子を前記一の図形要素に関連付ける工程と、
ｂ）前記入力データに含まれる前記複数の図形要素に対して前記ａ）工程を順次繰り返す工程と、
ｃ）前記代表図形要素群に含まれる各代表図形要素を第１の方向を向く直線にて所定幅毎に分割し、分割された領域のランレングスの実質的な集合として前記各代表図形要素を表す部分ランレングスデータを生成する工程と、
ｄ）前記複数の図形要素が配置される配置領域を前記第１の方向を向く複数の直線にて前記所定幅毎に分割することにより前記第１の方向に垂直な第２の方向に配列された前記所定幅の複数の単位領域を設定し、前記複数の単位領域のそれぞれと重なる一または複数の図形要素のランレングスを示す単位ランレングスデータを生成して前記入力データに含まれる前記複数の図形要素のランレングスデータである出力データを生成する工程と、
を備え、
前記複数の図形要素に含まれる各図形要素が、前記第１の方向を向く前記複数の直線のいずれかの上に設定されるとともに前記各図形要素の前記配置領域における位置を示す固有原点を有し、前記各代表図形要素が予め定められた固有原点を有し、前記ａ）工程において、前記一の図形要素の固有原点と前記各代表図形要素の固有原点とを一致させた際に前記一の図形要素の形状と前記各代表図形要素の形状とが一致する場合にのみ前記一の図形要素の形状と前記各代表図形要素の形状とが同じと判断され、
前記ｄ）工程が、
ｄ１）前記複数の単位領域のうち一の単位領域を注目単位領域として決定する工程と、
ｄ２）前記注目単位領域と重なる一または複数の図形要素を前記入力データに基づいて注目図形要素として抽出する工程と、
ｄ３）各注目図形要素の前記配置領域における位置、および、前記各注目図形要素に関連付けられた代表図形識別子が示す代表図形要素の部分ランレングスデータに基づいて、前記各注目図形要素の前記注目単位領域と重なるランレングスである注目ランレングスを取得し、前記各注目図形要素の前記注目ランレングスに基づいて前記注目単位領域の単位ランレングスデータを生成する工程と、
ｄ４）前記複数の単位領域に対して前記ｄ１）工程ないし前記ｄ３）工程を順次繰り返す工程と、
を備えることを特徴とするデータ変換方法。
【請求項２】
請求項１に記載のデータ変換方法であって、
前記ｃ）工程が、
ｃ１）前記各代表図形要素に、前記第１の方向に平行な１対の第１の辺を有するとともに前記第２の方向に平行であって前記各代表図形要素のエッジ上に位置する１対の第２の辺を有する長方形領域が含まれている場合に、前記長方形領域を前記各代表図形要素から抽出する工程と、
ｃ２）前記長方形領域を前記第１の方向を向く前記直線にて前記所定幅毎に複数の領域に分割した場合に前記複数の領域のうち前記第２の方向の一方の端に位置する一の領域のランレングスを取得する工程と、
ｃ３）前記一の領域の前記ランレングス、および、前記第２の方向における前記一方から他方へと向かう前記長方形領域の第２の辺の長さを、前記長方形領域を実質的にランレングスの集合として表すデータとして前記部分ランレングスデータに含める工程と、
を備え、
前記ｄ３）工程において、前記第２の辺の前記長さに基づいて、前記各注目図形要素の前記長方形領域に対応する領域が前記注目単位領域と重なるか否かが判断され、前記長方形領域に対応する前記領域が前記注目単位領域と重なる場合に、前記長方形領域の前記一の領域の前記ランレングスが前記注目ランレングスとされることを特徴とするデータ変換方法。
【請求項３】
請求項２に記載のデータ変換方法であって、
前記ｃ）工程が、
ｃ４）前記各代表図形要素に、前記第１の方向に平行な１対の第１の辺を有するとともに前記第２の方向に非平行であって前記各代表図形要素のエッジ上に位置する１対の平行な第２の辺を有する平行四辺形領域が含まれている場合に、前記平行四辺形領域を前記各代表図形要素から抽出する工程と、
ｃ５）前記平行四辺形領域を前記第１の方向を向く前記直線にて前記所定幅毎に複数の領域に分割した場合に前記複数の領域のうち前記第２の方向の一方の端に位置する一の領域のランレングスを取得する工程と、
ｃ６）前記一の領域の前記ランレングス、前記第２の方向の前記一方から他方へと向かう前記平行四辺形領域の第２の辺の前記第２の方向における長さ、および、前記第２の辺の前記第２の方向に対する傾きを、前記平行四辺形領域を実質的にランレングスの集合として表すデータとして前記部分ランレングスデータに含める工程と、
をさらに備え、
前記ｄ３）工程において、前記第２の辺の前記第２の方向における前記長さに基づいて、前記各注目図形要素の前記平行四辺形領域に対応する領域が前記注目単位領域と重なるか否かが判断され、前記平行四辺形領域に対応する前記領域が前記注目単位領域と重なる場合に、前記平行四辺形領域の前記一の領域の前記ランレングス、および、前記第２の辺の前記傾きに基づいて前記注目ランレングスが取得されることを特徴とするデータ変換方法。
【請求項４】
請求項１に記載のデータ変換方法であって、
前記ｃ）工程が、
ｃ７）前記各代表図形要素に、前記第１の方向に平行な１対の第１の辺を有するとともに前記各代表図形要素のエッジ上に位置する１対の平行な第２の辺を有する平行四辺形領域が含まれている場合に、前記平行四辺形領域を前記各代表図形要素から抽出する工程と、
ｃ８）前記平行四辺形領域を前記第１の方向を向く前記直線にて前記所定幅毎に複数の領域に分割した場合に前記複数の領域のうち前記第２の方向の一方の端に位置する一の領域のランレングスを取得する工程と、
ｃ９）前記一の領域の前記ランレングス、前記第２の方向の前記一方から他方へと向かう前記平行四辺形領域の第２の辺の前記第２の方向における長さ、および、前記第２の辺の前記第２の方向に対する傾きを、前記平行四辺形領域を実質的にランレングスの集合として表すデータとして前記部分ランレングスデータに含める工程と、
を備え、
前記ｄ３）工程において、前記第２の辺の前記第２の方向における前記長さに基づいて、前記各注目図形要素の前記平行四辺形領域に対応する領域が前記注目単位領域と重なるか否かが判断され、前記平行四辺形領域に対応する前記領域が前記注目単位領域と重なる場合に、前記平行四辺形領域の前記一の領域の前記ランレングス、および、前記第２の辺の前記傾きに基づいて前記注目ランレングスが取得されることを特徴とするデータ変換方法。
【請求項５】
複数の図形要素のベクトルデータである入力データをランレングスデータである出力データに変換するデータ変換方法であって、
ａ）入力データに含まれる複数の図形要素のベクトルデータに基づいて、一の図形要素を第１の方向を向く複数の直線にて所定幅毎に分割し、分割された領域のランレングスの実質的な集合として前記一の図形要素を表す部分ランレングスデータを生成する工程と、
ｂ）前記入力データに含まれる前記複数の図形要素に対して前記ａ）工程を順次繰り返す工程と、
ｃ）前記複数の図形要素が配置される配置領域を前記第１の方向を向く前記複数の直線にて前記所定幅毎に分割することにより前記第１の方向に垂直な第２の方向に配列された前記所定幅の複数の単位領域を設定し、前記複数の単位領域のそれぞれと重なる一または複数の図形要素のランレングスを示す単位ランレングスデータを生成して前記入力データに含まれる前記複数の図形要素のランレングスデータである出力データを生成する工程と、
を備え、
前記複数の図形要素に含まれる各図形要素が、前記第１の方向を向く前記複数の直線のいずれかの上に設定されるとともに前記各図形要素の前記配置領域における位置を示す固有原点を有し、前記各代表図形要素が予め定められた固有原点を有し、前記ａ）工程において、前記一の図形要素の固有原点と前記各代表図形要素の固有原点とを一致させた際に前記一の図形要素の形状と前記各代表図形要素の形状とが一致する場合にのみ前記一の図形要素の形状と前記各代表図形要素の形状とが同じと判断され、
前記ａ）工程が、
ａ１）前記一の図形要素に、前記第１の方向に平行な１対の第１の辺を有するとともに前記第２の方向に平行であって前記一の図形要素のエッジ上に位置する１対の第２の辺を有する長方形領域が含まれている場合に、前記長方形領域を前記一の図形要素から抽出する工程と、
ａ２）前記長方形領域を前記第１の方向を向く前記複数の直線にて前記所定幅毎に複数の領域に分割した場合に前記複数の領域のうち前記第２の方向の一方の端に位置する一の領域のランレングスを取得する工程と、
ａ３）前記一の領域の前記ランレングス、および、前記第２の方向における前記一方から他方へと向かう前記長方形領域の第２の辺の長さを、前記長方形領域を実質的にランレングスの集合として表すデータとして前記部分ランレングスデータに含める工程と、
を備え、
前記ｃ）工程が、
ｃ１）前記複数の単位領域のうち一の単位領域を注目単位領域として決定する工程と、
ｃ２）前記注目単位領域と重なる一または複数の図形要素を注目図形要素として抽出する工程と、
ｃ３）各注目図形要素の前記注目単位領域と重なるランレングスである注目ランレングスを取得し、前記各注目図形要素の前記注目ランレングスに基づいて前記注目単位領域の単位ランレングスデータを生成する工程と、
ｃ４）前記複数の単位領域に対して前記ｃ１）工程ないし前記ｃ３）工程を順次繰り返す工程と、
を備え、
前記ｃ３）工程において、前記第２の辺の前記長さに基づいて、前記各注目図形要素の前記長方形領域に対応する領域が前記注目単位領域と重なるか否かが判断され、前記長方形領域に対応する前記領域が前記注目単位領域と重なる場合に、前記長方形領域の前記一の領域の前記ランレングスが前記注目ランレングスとされることを特徴とするデータ変換方法。
【請求項６】
基板上にパターンを描画する描画システムであって、
請求項１ないし５のいずれかに記載のデータ変換方法により入力データを出力データに変換するデータ変換装置と、
前記データ変換装置により生成された前記出力データに基づいて基板上にパターンを描画する描画装置と、
を備え、
前記描画装置が、
前記基板を保持する基板保持部と、
前記基板に光を照射する光変調素子と、
前記光変調素子から導かれた光の前記基板上における照射位置を、前記基板上における前記第１の方向に対応する方向に前記基板に対して相対的に移動する照射位置移動機構と、
前記出力データに基づいて前記光変調素子からの光の変調を制御する光変調素子制御部と、
を備えることを特徴とする描画システム。
【請求項７】
複数の図形要素のベクトルデータである入力データをランレングスデータである出力データに変換するプログラムであって、前記プログラムのコンピュータによる実行は、前記コンピュータに、
ａ）入力データに含まれる複数の図形要素のベクトルデータに基づいて、一の図形要素を、代表的な形状を有する代表図形要素の集合である代表図形要素群と比較し、前記代表図形要素群に前記一の図形要素の形状と同じ形状の代表図形要素が含まれる場合に、前記代表図形要素を示す代表図形識別子を前記一の図形要素に関連付け、前記代表図形要素群に前記一の図形要素の形状と同じ形状の代表図形要素が含まれない場合に、前記一の図形要素の形状と同じ形状を有する新たな代表図形要素を前記代表図形要素群に追加するとともに前記新たな代表図形要素を示す代表図形識別子を前記一の図形要素に関連付ける工程と、
ｂ）前記入力データに含まれる前記複数の図形要素に対して前記ａ）工程を順次繰り返す工程と、
ｃ）前記代表図形要素群に含まれる各代表図形要素を第１の方向を向く直線にて所定幅毎に分割し、分割された領域のランレングスの実質的な集合として前記各代表図形要素を表す部分ランレングスデータを生成する工程と、
ｄ）前記複数の図形要素が配置される配置領域を前記第１の方向を向く複数の直線にて前記所定幅毎に分割することにより前記第１の方向に垂直な第２の方向に配列された前記所定幅の複数の単位領域を設定し、前記複数の単位領域のそれぞれと重なる一または複数の図形要素のランレングスを示す単位ランレングスデータを生成して前記入力データに含まれる前記複数の図形要素のランレングスデータである出力データを生成する工程と、
を実行させ、
前記複数の図形要素に含まれる各図形要素が、前記第１の方向を向く前記複数の直線のいずれかの上に設定されるとともに前記各図形要素の前記配置領域における位置を示す固有原点を有し、前記各代表図形要素が予め定められた固有原点を有し、前記ａ）工程において、前記一の図形要素の固有原点と前記各代表図形要素の固有原点とを一致させた際に前記一の図形要素の形状と前記各代表図形要素の形状とが一致する場合にのみ前記一の図形要素の形状と前記各代表図形要素の形状とが同じと判断され、
前記ｄ）工程が、
ｄ１）前記複数の単位領域のうち一の単位領域を注目単位領域として決定する工程と、
ｄ２）前記注目単位領域と重なる一または複数の図形要素を前記入力データに基づいて注目図形要素として抽出する工程と、
ｄ３）各注目図形要素の前記配置領域における位置、および、前記各注目図形要素に関連付けられた代表図形識別子が示す代表図形要素の部分ランレングスデータに基づいて、前記各注目図形要素の前記注目単位領域と重なるランレングスである注目ランレングスを取得し、前記各注目図形要素の前記注目ランレングスに基づいて前記注目単位領域の単位ランレングスデータを生成する工程と、
ｄ４）前記複数の単位領域に対して前記ｄ１）工程ないし前記ｄ３）工程を順次繰り返す工程と、
を備えることを特徴とするプログラム。
【請求項８】
複数の図形要素のベクトルデータである入力データをランレングスデータである出力データに変換するプログラムであって、前記プログラムのコンピュータによる実行は、前記コンピュータに、
ａ）入力データに含まれる複数の図形要素のベクトルデータに基づいて、一の図形要素を第１の方向を向く複数の直線にて所定幅毎に分割し、分割された領域のランレングスの実質的な集合として前記一の図形要素を表す部分ランレングスデータを生成する工程と、
ｂ）前記入力データに含まれる前記複数の図形要素に対して前記ａ）工程を順次繰り返す工程と、
ｃ）前記複数の図形要素が配置される配置領域を前記第１の方向を向く前記複数の直線にて前記所定幅毎に分割することにより前記第１の方向に垂直な第２の方向に配列された前記所定幅の複数の単位領域を設定し、前記複数の単位領域のそれぞれと重なる一または複数の図形要素のランレングスを示す単位ランレングスデータを生成して前記入力データに含まれる前記複数の図形要素のランレングスデータである出力データを生成する工程と、
を実行させ、
前記複数の図形要素に含まれる各図形要素が、前記第１の方向を向く前記複数の直線のいずれかの上に設定されるとともに前記各図形要素の前記配置領域における位置を示す固有原点を有し、前記各代表図形要素が予め定められた固有原点を有し、前記ａ）工程において、前記一の図形要素の固有原点と前記各代表図形要素の固有原点とを一致させた際に前記一の図形要素の形状と前記各代表図形要素の形状とが一致する場合にのみ前記一の図形要素の形状と前記各代表図形要素の形状とが同じと判断され、
前記ａ）工程が、
ａ１）前記一の図形要素に、前記第１の方向に平行な１対の第１の辺を有するとともに前記第２の方向に平行であって前記一の図形要素のエッジ上に位置する１対の第２の辺を有する長方形領域が含まれている場合に、前記長方形領域を前記一の図形要素から抽出する工程と、
ａ２）前記長方形領域を前記第１の方向を向く前記複数の直線にて前記所定幅毎に複数の領域に分割した場合に前記複数の領域のうち前記第２の方向の一方の端に位置する一の領域のランレングスを取得する工程と、
ａ３）前記一の領域の前記ランレングス、および、前記第２の方向における前記一方から他方へと向かう前記長方形領域の第２の辺の長さを、前記長方形領域を実質的にランレングスの集合として表すデータとして前記部分ランレングスデータに含める工程と、
を備え、
前記ｃ）工程が、
ｃ１）前記複数の単位領域のうち一の単位領域を注目単位領域として決定する工程と、
ｃ２）前記注目単位領域と重なる一または複数の図形要素を注目図形要素として抽出する工程と、
ｃ３）各注目図形要素の前記注目単位領域と重なるランレングスである注目ランレングスを取得し、前記各注目図形要素の前記注目ランレングスに基づいて前記注目単位領域の単位ランレングスデータを生成する工程と、
ｃ４）前記複数の単位領域に対して前記ｃ１）工程ないし前記ｃ３）工程を順次繰り返す工程と、
を備え、
前記ｃ３）工程において、前記第２の辺の前記長さに基づいて、前記各注目図形要素の前記長方形領域に対応する領域が前記注目単位領域と重なるか否かが判断され、前記長方形領域に対応する前記領域が前記注目単位領域と重なる場合に、前記長方形領域の前記一の領域の前記ランレングスが前記注目ランレングスとされることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の図形要素のベクトルデータである入力データをランレングスデータである出力データに変換する技術に関する。
【背景技術】
【０００２】
従来より、半導体基板やプリント基板、あるいは、プラズマ表示装置や液晶表示装置用のガラス基板等（以下、「基板」という。）に形成された感光材料に光を照射することによりパターンの描画が行われており、パターンの高精細化に伴い、感光材料上にて光ビームを走査してパターンを直接描画するパターン描画装置が利用されている。
【０００３】
このようなパターンは、設計段階では通常、ＣＡＤデータ等のベクトルデータにより表現されており、パターン描画装置によるパターンの描画に際して、例えば特許文献１に示されるように、当該ベクトルデータを、パターン描画装置が利用可能なランレングスデータ等のラスタデータに変換する処理（ＲＩＰ：Raster Image Processing）が行われる。
【０００４】
特許文献１では、複数の回路パターンのパターン情報を含むＣＡＤデータをランレングスデータに変換する際に、一の回路パターンと同一形状の回路パターンのパターン情報が既にランレングスデータに変換されている場合、当該一の回路パターンのパターン情報をランレングスデータに変換することなく、変換済みの同形状の回路パターンのランレングスデータを、描画領域の当該一の回路パターンに対応する位置に配置することにより、ランレングスデータへの変換処理に要する処理時間を短縮する技術が提案されている。
【０００５】
特許文献１のデータ変換方法では、全ての回路パターンに対応するパターンランレングスデータを描画領域に配置した後、副走査方向に配列された複数の走査ラインのそれぞれについて全パターンランレングスデータとの重なりが判断され、各走査ラインと重なる一または複数のパターンランレングスデータから当該各走査ライン上に位置するランレングスデータを抽出して各走査ラインと対応する位置に割り付けることにより、描画領域全体のランレングスデータが取得される。
【特許文献１】特開２００３−９９７７１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ところで、特許文献１のデータ変換方法では、描画領域全体のランレングスデータの取得の際に、全ての回路パターンに対応するパターンランレングスデータが描画領域に配置されたデータ（以下、「全ランレングス配置データ」という。）を利用するため、パターンの更なる高精細化に伴い、全ランレングス配置データの容量が増大してしまう。このため、データ変換処理が全ランレングス配置データをメモリ上に保持した状態で行われる場合、全ランレングス配置データにより使用されるメモリ容量が大きくなってしまい、データ変換の処理速度が低下してしまうおそれがある。
【０００７】
また、全ランレングス配置データの容量が使用可能なメモリ容量に対して過大となる場合には、全ランレングス配置データをメモリ上に保持するのではなく、中間ファイルとして保持することが必要になる。これにより、全ランレングス配置データへのアクセスに要する時間が、全ランレングス配置データがメモリ上に保持される場合に比べて増大し、その結果、データ変換処理による出力データの生成に要する時間がさらに増大してしまう。
【０００８】
本発明は、上記課題に鑑みなされたものであり、複数の図形要素のベクトルデータである入力データからランレングスデータである出力データへの変換に要する時間を短縮して出力データの生成を高速化することを目的としている。
【課題を解決するための手段】
【０００９】
請求項１に記載の発明は、複数の図形要素のベクトルデータである入力データをランレングスデータである出力データに変換するデータ変換方法であって、ａ）入力データに含まれる複数の図形要素のベクトルデータに基づいて、一の図形要素を、代表的な形状を有する代表図形要素の集合である代表図形要素群と比較し、前記代表図形要素群に前記一の図形要素の形状と同じ形状の代表図形要素が含まれる場合に、前記代表図形要素を示す代表図形識別子を前記一の図形要素に関連付け、前記代表図形要素群に前記一の図形要素の形状と同じ形状の代表図形要素が含まれない場合に、前記一の図形要素の形状と同じ形状を有する新たな代表図形要素を前記代表図形要素群に追加するとともに前記新たな代表図形要素を示す代表図形識別子を前記一の図形要素に関連付ける工程と、ｂ）前記入力データに含まれる前記複数の図形要素に対して前記ａ）工程を順次繰り返す工程と、ｃ）前記代表図形要素群に含まれる各代表図形要素を第１の方向を向く直線にて所定幅毎に分割し、分割された領域のランレングスの実質的な集合として前記各代表図形要素を表す部分ランレングスデータを生成する工程と、ｄ）前記複数の図形要素が配置される配置領域を前記第１の方向を向く複数の直線にて前記所定幅毎に分割することにより前記第１の方向に垂直な第２の方向に配列された前記所定幅の複数の単位領域を設定し、前記複数の単位領域のそれぞれと重なる一または複数の図形要素のランレングスを示す単位ランレングスデータを生成して前記入力データに含まれる前記複数の図形要素のランレングスデータである出力データを生成する工程とを備え、前記複数の図形要素に含まれる各図形要素が、前記第１の方向を向く前記複数の直線のいずれかの上に設定されるとともに前記各図形要素の前記配置領域における位置を示す固有原点を有し、前記各代表図形要素が予め定められた固有原点を有し、前記ａ）工程において、前記一の図形要素の固有原点と前記各代表図形要素の固有原点とを一致させた際に前記一の図形要素の形状と前記各代表図形要素の形状とが一致する場合にのみ前記一の図形要素の形状と前記各代表図形要素の形状とが同じと判断され、前記ｄ）工程が、ｄ１）前記複数の単位領域のうち一の単位領域を注目単位領域として決定する工程と、ｄ２）前記注目単位領域と重なる一または複数の図形要素を前記入力データに基づいて注目図形要素として抽出する工程と、ｄ３）各注目図形要素の前記配置領域における位置、および、前記各注目図形要素に関連付けられた代表図形識別子が示す代表図形要素の部分ランレングスデータに基づいて、前記各注目図形要素の前記注目単位領域と重なるランレングスである注目ランレングスを取得し、前記各注目図形要素の前記注目ランレングスに基づいて前記注目単位領域の単位ランレングスデータを生成する工程と、ｄ４）前記複数の単位領域に対して前記ｄ１）工程ないし前記ｄ３）工程を順次繰り返す工程とを備える。
【００１１】
請求項２に記載の発明は、請求項１に記載のデータ変換方法であって、前記ｃ）工程が、ｃ１）前記各代表図形要素に、前記第１の方向に平行な１対の第１の辺を有するとともに前記第２の方向に平行であって前記各代表図形要素のエッジ上に位置する１対の第２の辺を有する長方形領域が含まれている場合に、前記長方形領域を前記各代表図形要素から抽出する工程と、ｃ２）前記長方形領域を前記第１の方向を向く前記直線にて前記所定幅毎に複数の領域に分割した場合に前記複数の領域のうち前記第２の方向の一方の端に位置する一の領域のランレングスを取得する工程と、ｃ３）前記一の領域の前記ランレングス、および、前記第２の方向における前記一方から他方へと向かう前記長方形領域の第２の辺の長さを、前記長方形領域を実質的にランレングスの集合として表すデータとして前記部分ランレングスデータに含める工程とを備え、前記ｄ３）工程において、前記第２の辺の前記長さに基づいて、前記各注目図形要素の前記長方形領域に対応する領域が前記注目単位領域と重なるか否かが判断され、前記長方形領域に対応する前記領域が前記注目単位領域と重なる場合に、前記長方形領域の前記一の領域の前記ランレングスが前記注目ランレングスとされる。
【００１２】
請求項３に記載の発明は、請求項２に記載のデータ変換方法であって、前記ｃ）工程が、ｃ４）前記各代表図形要素に、前記第１の方向に平行な１対の第１の辺を有するとともに前記第２の方向に非平行であって前記各代表図形要素のエッジ上に位置する１対の平行な第２の辺を有する平行四辺形領域が含まれている場合に、前記平行四辺形領域を前記各代表図形要素から抽出する工程と、ｃ５）前記平行四辺形領域を前記第１の方向を向く前記直線にて前記所定幅毎に複数の領域に分割した場合に前記複数の領域のうち前記第２の方向の一方の端に位置する一の領域のランレングスを取得する工程と、ｃ６）前記一の領域の前記ランレングス、前記第２の方向の前記一方から他方へと向かう前記平行四辺形領域の第２の辺の前記第２の方向における長さ、および、前記第２の辺の前記第２の方向に対する傾きを、前記平行四辺形領域を実質的にランレングスの集合として表すデータとして前記部分ランレングスデータに含める工程とをさらに備え、前記ｄ３）工程において、前記第２の辺の前記第２の方向における前記長さに基づいて、前記各注目図形要素の前記平行四辺形領域に対応する領域が前記注目単位領域と重なるか否かが判断され、前記平行四辺形領域に対応する前記領域が前記注目単位領域と重なる場合に、前記平行四辺形領域の前記一の領域の前記ランレングス、および、前記第２の辺の前記傾きに基づいて前記注目ランレングスが取得される。
【００１３】
請求項４に記載の発明は、請求項１に記載のデータ変換方法であって、前記ｃ）工程が、ｃ７）前記各代表図形要素に、前記第１の方向に平行な１対の第１の辺を有するとともに前記各代表図形要素のエッジ上に位置する１対の平行な第２の辺を有する平行四辺形領域が含まれている場合に、前記平行四辺形領域を前記各代表図形要素から抽出する工程と、ｃ８）前記平行四辺形領域を前記第１の方向を向く前記直線にて前記所定幅毎に複数の領域に分割した場合に前記複数の領域のうち前記第２の方向の一方の端に位置する一の領域のランレングスを取得する工程と、ｃ９）前記一の領域の前記ランレングス、前記第２の方向の前記一方から他方へと向かう前記平行四辺形領域の第２の辺の前記第２の方向における長さ、および、前記第２の辺の前記第２の方向に対する傾きを、前記平行四辺形領域を実質的にランレングスの集合として表すデータとして前記部分ランレングスデータに含める工程とを備え、前記ｄ３）工程において、前記第２の辺の前記第２の方向における前記長さに基づいて、前記各注目図形要素の前記平行四辺形領域に対応する領域が前記注目単位領域と重なるか否かが判断され、前記平行四辺形領域に対応する前記領域が前記注目単位領域と重なる場合に、前記平行四辺形領域の前記一の領域の前記ランレングス、および、前記第２の辺の前記傾きに基づいて前記注目ランレングスが取得される。
【００１４】
請求項５に記載の発明は、複数の図形要素のベクトルデータである入力データをランレングスデータである出力データに変換するデータ変換方法であって、ａ）入力データに含まれる複数の図形要素のベクトルデータに基づいて、一の図形要素を第１の方向を向く複数の直線にて所定幅毎に分割し、分割された領域のランレングスの実質的な集合として前記一の図形要素を表す部分ランレングスデータを生成する工程と、ｂ）前記入力データに含まれる前記複数の図形要素に対して前記ａ）工程を順次繰り返す工程と、ｃ）前記複数の図形要素が配置される配置領域を前記第１の方向を向く前記複数の直線にて前記所定幅毎に分割することにより前記第１の方向に垂直な第２の方向に配列された前記所定幅の複数の単位領域を設定し、前記複数の単位領域のそれぞれと重なる一または複数の図形要素のランレングスを示す単位ランレングスデータを生成して前記入力データに含まれる前記複数の図形要素のランレングスデータである出力データを生成する工程とを備え、前記複数の図形要素に含まれる各図形要素が、前記第１の方向を向く前記複数の直線のいずれかの上に設定されるとともに前記各図形要素の前記配置領域における位置を示す固有原点を有し、前記各代表図形要素が予め定められた固有原点を有し、前記ａ）工程において、前記一の図形要素の固有原点と前記各代表図形要素の固有原点とを一致させた際に前記一の図形要素の形状と前記各代表図形要素の形状とが一致する場合にのみ前記一の図形要素の形状と前記各代表図形要素の形状とが同じと判断され、前記ａ）工程が、ａ１）前記一の図形要素に、前記第１の方向に平行な１対の第１の辺を有するとともに前記第２の方向に平行であって前記一の図形要素のエッジ上に位置する１対の第２の辺を有する長方形領域が含まれている場合に、前記長方形領域を前記一の図形要素から抽出する工程と、ａ２）前記長方形領域を前記第１の方向を向く前記複数の直線にて前記所定幅毎に複数の領域に分割した場合に前記複数の領域のうち前記第２の方向の一方の端に位置する一の領域のランレングスを取得する工程と、ａ３）前記一の領域の前記ランレングス、および、前記第２の方向における前記一方から他方へと向かう前記長方形領域の第２の辺の長さを、前記長方形領域を実質的にランレングスの集合として表すデータとして前記部分ランレングスデータに含める工程とを備え、前記ｃ）工程が、ｃ１）前記複数の単位領域のうち一の単位領域を注目単位領域として決定する工程と、ｃ２）前記注目単位領域と重なる一または複数の図形要素を注目図形要素として抽出する工程と、ｃ３）各注目図形要素の前記注目単位領域と重なるランレングスである注目ランレングスを取得し、前記各注目図形要素の前記注目ランレングスに基づいて前記注目単位領域の単位ランレングスデータを生成する工程と、ｃ４）前記複数の単位領域に対して前記ｃ１）工程ないし前記ｃ３）工程を順次繰り返す工程とを備え、前記ｃ３）工程において、前記第２の辺の前記長さに基づいて、前記各注目図形要素の前記長方形領域に対応する領域が前記注目単位領域と重なるか否かが判断され、前記長方形領域に対応する前記領域が前記注目単位領域と重なる場合に、前記長方形領域の前記一の領域の前記ランレングスが前記注目ランレングスとされる。
【００１５】
請求項６に記載の発明は、基板上にパターンを描画する描画システムであって、請求項１ないし５のいずれかに記載のデータ変換方法により入力データを出力データに変換するデータ変換装置と、前記データ変換装置により生成された前記出力データに基づいて基板上にパターンを描画する描画装置とを備え、前記描画装置が、前記基板を保持する基板保持部と、前記基板に光を照射する光変調素子と、前記光変調素子から導かれた光の前記基板上における照射位置を、前記基板上における前記第１の方向に対応する方向に前記基板に対して相対的に移動する照射位置移動機構と、前記出力データに基づいて前記光変調素子からの光の変調を制御する光変調素子制御部とを備える。
【００１６】
請求項７に記載の発明は、複数の図形要素のベクトルデータである入力データをランレングスデータである出力データに変換するプログラムであって、前記プログラムのコンピュータによる実行は、前記コンピュータに、ａ）入力データに含まれる複数の図形要素のベクトルデータに基づいて、一の図形要素を、代表的な形状を有する代表図形要素の集合である代表図形要素群と比較し、前記代表図形要素群に前記一の図形要素の形状と同じ形状の代表図形要素が含まれる場合に、前記代表図形要素を示す代表図形識別子を前記一の図形要素に関連付け、前記代表図形要素群に前記一の図形要素の形状と同じ形状の代表図形要素が含まれない場合に、前記一の図形要素の形状と同じ形状を有する新たな代表図形要素を前記代表図形要素群に追加するとともに前記新たな代表図形要素を示す代表図形識別子を前記一の図形要素に関連付ける工程と、ｂ）前記入力データに含まれる前記複数の図形要素に対して前記ａ）工程を順次繰り返す工程と、ｃ）前記代表図形要素群に含まれる各代表図形要素を第１の方向を向く直線にて所定幅毎に分割し、分割された領域のランレングスの実質的な集合として前記各代表図形要素を表す部分ランレングスデータを生成する工程と、ｄ）前記複数の図形要素が配置される配置領域を前記第１の方向を向く複数の直線にて前記所定幅毎に分割することにより前記第１の方向に垂直な第２の方向に配列された前記所定幅の複数の単位領域を設定し、前記複数の単位領域のそれぞれと重なる一または複数の図形要素のランレングスを示す単位ランレングスデータを生成して前記入力データに含まれる前記複数の図形要素のランレングスデータである出力データを生成する工程とを実行させ、前記複数の図形要素に含まれる各図形要素が、前記第１の方向を向く前記複数の直線のいずれかの上に設定されるとともに前記各図形要素の前記配置領域における位置を示す固有原点を有し、前記各代表図形要素が予め定められた固有原点を有し、前記ａ）工程において、前記一の図形要素の固有原点と前記各代表図形要素の固有原点とを一致させた際に前記一の図形要素の形状と前記各代表図形要素の形状とが一致する場合にのみ前記一の図形要素の形状と前記各代表図形要素の形状とが同じと判断され、前記ｄ）工程が、ｄ１）前記複数の単位領域のうち一の単位領域を注目単位領域として決定する工程と、ｄ２）前記注目単位領域と重なる一または複数の図形要素を前記入力データに基づいて注目図形要素として抽出する工程と、ｄ３）各注目図形要素の前記配置領域における位置、および、前記各注目図形要素に関連付けられた代表図形識別子が示す代表図形要素の部分ランレングスデータに基づいて、前記各注目図形要素の前記注目単位領域と重なるランレングスである注目ランレングスを取得し、前記各注目図形要素の前記注目ランレングスに基づいて前記注目単位領域の単位ランレングスデータを生成する工程と、ｄ４）前記複数の単位領域に対して前記ｄ１）工程ないし前記ｄ３）工程を順次繰り返す工程とを備える。
【００１７】
請求項８に記載の発明は、複数の図形要素のベクトルデータである入力データをランレングスデータである出力データに変換するプログラムであって、前記プログラムのコンピュータによる実行は、前記コンピュータに、ａ）入力データに含まれる複数の図形要素のベクトルデータに基づいて、一の図形要素を第１の方向を向く複数の直線にて所定幅毎に分割し、分割された領域のランレングスの実質的な集合として前記一の図形要素を表す部分ランレングスデータを生成する工程と、ｂ）前記入力データに含まれる前記複数の図形要素に対して前記ａ）工程を順次繰り返す工程と、ｃ）前記複数の図形要素が配置される配置領域を前記第１の方向を向く前記複数の直線にて前記所定幅毎に分割することにより前記第１の方向に垂直な第２の方向に配列された前記所定幅の複数の単位領域を設定し、前記複数の単位領域のそれぞれと重なる一または複数の図形要素のランレングスを示す単位ランレングスデータを生成して前記入力データに含まれる前記複数の図形要素のランレングスデータである出力データを生成する工程とを実行させ、前記複数の図形要素に含まれる各図形要素が、前記第１の方向を向く前記複数の直線のいずれかの上に設定されるとともに前記各図形要素の前記配置領域における位置を示す固有原点を有し、前記各代表図形要素が予め定められた固有原点を有し、前記ａ）工程において、前記一の図形要素の固有原点と前記各代表図形要素の固有原点とを一致させた際に前記一の図形要素の形状と前記各代表図形要素の形状とが一致する場合にのみ前記一の図形要素の形状と前記各代表図形要素の形状とが同じと判断され、前記ａ）工程が、ａ１）前記一の図形要素に、前記第１の方向に平行な１対の第１の辺を有するとともに前記第２の方向に平行であって前記一の図形要素のエッジ上に位置する１対の第２の辺を有する長方形領域が含まれている場合に、前記長方形領域を前記一の図形要素から抽出する工程と、ａ２）前記長方形領域を前記第１の方向を向く前記複数の直線にて前記所定幅毎に複数の領域に分割した場合に前記複数の領域のうち前記第２の方向の一方の端に位置する一の領域のランレングスを取得する工程と、ａ３）前記一の領域の前記ランレングス、および、前記第２の方向における前記一方から他方へと向かう前記長方形領域の第２の辺の長さを、前記長方形領域を実質的にランレングスの集合として表すデータとして前記部分ランレングスデータに含める工程とを備え、前記ｃ）工程が、ｃ１）前記複数の単位領域のうち一の単位領域を注目単位領域として決定する工程と、ｃ２）前記注目単位領域と重なる一または複数の図形要素を注目図形要素として抽出する工程と、ｃ３）各注目図形要素の前記注目単位領域と重なるランレングスである注目ランレングスを取得し、前記各注目図形要素の前記注目ランレングスに基づいて前記注目単位領域の単位ランレングスデータを生成する工程と、ｃ４）前記複数の単位領域に対して前記ｃ１）工程ないし前記ｃ３）工程を順次繰り返す工程とを備え、前記ｃ３）工程において、前記第２の辺の前記長さに基づいて、前記各注目図形要素の前記長方形領域に対応する領域が前記注目単位領域と重なるか否かが判断され、前記長方形領域に対応する前記領域が前記注目単位領域と重なる場合に、前記長方形領域の前記一の領域の前記ランレングスが前記注目ランレングスとされる。
【発明の効果】
【００１８】
本発明では、出力データの生成を高速化することができる。また、請求項２ないし４の発明では、出力データの生成をより高速化することができる。
【発明を実施するための最良の形態】
【００１９】
図１は、本発明の第１の実施の形態に係る描画システム１００の構成を示す図である。描画システム１００は、液晶表示装置用のガラス基板（以下、単に「基板」という。）上の感光材料に光を利用してパターンを描画するシステムである。図１に示すように、描画システム１００は、パターンを示すベクトルデータである入力データをランレングスデータである出力データに変換する（すなわち、ラスタライズを行う）データ変換装置７、および、データ変換装置７により生成された出力データに基づいて基板上にパターンを描画する描画装置１を備える。図１では、データ変換装置７の各機能も併せて示している（図１２、図１５、図１８および図２０においても同様）。以下では、描画装置１について説明した後、データ変換装置７およびデータ変換装置７にて取り扱われるデータについて説明する。
【００２０】
図２および図３はそれぞれ、描画装置１の側面図および平面図である。図２および図３に示すように、描画装置１は、（＋Ｚ）側の主面９１（以下、「上面９１」という。）上に感光材料の層が形成された基板９を保持する基板保持部３、基台１１上に設けられて基板保持部３をＺ方向に垂直なＸ方向およびＹ方向に移動する保持部移動機構２、基板保持部３および保持部移動機構２を跨ぐように基台１１に固定されるフレーム１２、並びに、フレーム１２に取り付けられて基板９上の感光材料に変調された光を照射する光照射部４を備える。また、描画装置１は、図２に示すように、保持部移動機構２や光照射部４等の各構成を制御する制御部６を備える。
【００２１】
図２および図３に示すように、基板保持部３は、基板９が載置されるステージ３１、ステージ３１を回転可能に支持する支持プレート３３、および、支持プレート３３上において、基板９の上面９１に垂直な回転軸３２１を中心としてステージ３１を回転するステージ回転機構３２を備える。
【００２２】
保持部移動機構２は、基板保持部３を図２および図３中のＸ方向（以下、「副走査方向」という。）に移動する副走査機構２３、副走査機構２３を介して支持プレート３３を支持するベースプレート２４、並びに、基板保持部３をベースプレート２４と共にＸ方向に垂直なＹ方向（以下、「主走査方向」という。）に移動する主走査機構２５を備える。描画装置１では、保持部移動機構２により、基板９の上面９１に平行な主走査方向および副走査方向に基板保持部３が移動される。
【００２３】
図２および図３に示すように、副走査機構２３は、支持プレート３３の下側（すなわち、（−Ｚ）側）において、ステージ３１の主面に平行、かつ、主走査方向に垂直な副走査方向に伸びるリニアモータ２３１、並びに、リニアモータ２３１の（＋Ｙ）側および（−Ｙ）側において副走査方向に伸びる１対のリニアガイド２３２を備える。主走査機構２５は、ベースプレート２４の下側において、ステージ３１の主面に平行な主走査方向に伸びるリニアモータ２５１、並びに、リニアモータ２５１の（＋Ｘ）側および（−Ｘ）側において主走査方向に伸びる１対のエアスライダ２５２を備える。
【００２４】
図３に示すように、光照射部４は、副走査方向に沿って等ピッチにて配列されてフレーム１２に取り付けられる複数（本実施の形態では、８つ）の光学ヘッド４１を備える。また、光照射部４は、図２に示すように、各光学ヘッド４１に接続される光源光学系４２、並びに、紫外光を出射するＵＶ光源４３および光源駆動部４４を備える。ＵＶ光源４３は固体レーザであり、光源駆動部４４が駆動されることにより、ＵＶ光源４３から波長３５５ｎｍの紫外光が出射され、光源光学系４２を介して光学ヘッド４１へと導かれる。
【００２５】
各光学ヘッド４１は、ＵＶ光源４３からの光を下方に向けて出射する出射部４５、出射部４５からの光を反射して空間光変調器４６へと導く光学系４５１、光学系４５１を介して照射された出射部４５からの光を変調しつつ反射する空間光変調器４６、および、空間光変調器４６からの変調された光を基板９の上面９１に設けられた感光材料上へと導く光学系４７を備える。
【００２６】
図４は、空間光変調器４６を拡大して示す図である。図４に示すように、空間光変調器４６は、出射部４５を介して照射されたＵＶ光源４３（図２参照）からの光を基板９の上面９１へと導く回折格子型の複数の光変調素子４６１を備える。光変調素子４６１は半導体装置製造技術を利用して製造され、格子の深さを変更することができる回折格子となっている。光変調素子４６１には複数の可撓リボン４６１ａおよび複数の固定リボン４６１ｂが交互に平行に配列形成され、複数の可撓リボン４６１ａは背後の基準面に対して個別に昇降移動可能とされ、複数の固定リボン４６１ｂは基準面に対して固定される。回折格子型の光変調素子としては、例えば、ＧＬＶ（Grating Light Valve：グレーチング・ライト・バルブ）（シリコン・ライト・マシーンズ（サニーベール、カリフォルニア）の登録商標）が知られている。
【００２７】
図５．Ａおよび図５．Ｂは、可撓リボン４６１ａおよび固定リボン４６１ｂに対して垂直な面における光変調素子４６１の断面を示す図である。図５．Ａに示すように可撓リボン４６１ａおよび固定リボン４６１ｂが基準面４６１ｃに対して同じ高さに位置する（すなわち、可撓リボン４６１ａが撓まない）場合には、光変調素子４６１の表面は面一となり、入射光Ｌ１の反射光が０次光Ｌ２として導出される。一方、図５．Ｂに示すように可撓リボン４６１ａが固定リボン４６１ｂよりも基準面４６１ｃ側に撓む場合には、可撓リボン４６１ａが回折格子の溝の底面となり、入射光Ｌ１が入射した光変調素子４６１から１次回折光Ｌ３（さらには、高次回折光）が導出され、０次光は消滅する。このように、光変調素子４６１は回折格子を利用した光変調を行う。
【００２８】
図２に示す光照射部４では、ＵＶ光源４３からの光が光源光学系４２により線状光（光束断面が線状の光）とされ、出射部４５を介して空間光変調器４６のライン状に配列された複数の可撓リボン４６１ａおよび固定リボン４６１ｂ（図５．Ａおよび図５．Ｂ参照）上に照射される。光変調素子４６１では、隣接する各１本の可撓リボン４６１ａおよび固定リボン４６１ｂを１つのリボン対とすると、３つ以上のリボン対が描画されるパターンの１つの画素に対応する。光変調素子４６１では、各空間光変調器４６に接続される光変調素子制御部６１からの信号に基づいてパターンの各画素に対応するリボン対の可撓リボン４６１ａがそれぞれ制御され、各画素に対応するリボン対が０次光（正反射光）を出射する状態と、非０次回折光（主として１次回折光（（＋１）次回折光および（−１）次回折光））を出射する状態との間で遷移可能とされる。光変調素子４６１から出射される０次光は光学系４７へと導かれ、１次回折光は光学系４７とは異なる方向へと導かれる。なお、迷光となることを防止するために１次回折光は図示を省略する遮光部により遮光される。
【００２９】
光変調素子４６１からの０次光は、光学系４７を介して基板９の上面９１へと導かれ、これにより、基板９の上面９１上においてＸ方向（すなわち、副走査方向）に並ぶ複数の照射位置のそれぞれに変調された光が照射される。すなわち、光変調素子４６１の各画素に対応するリボン対は０次光を出射する状態がＯＮ状態であり、１次回折光を出射する状態がＯＦＦ状態とされる。
【００３０】
図２および図３に示す描画装置１では、保持部移動機構２の主走査機構２５により主走査方向に移動される基板９に対し、光照射部４の光変調素子４６１から変調された光が照射される。換言すれば、主走査機構２５は、光変調素子４６１から基板９へと導かれた光の基板９上における照射位置を、基板９に対して主走査方向に相対的に移動する照射位置移動機構となっている。なお、描画装置１では、例えば、基板９を移動することなく、光変調素子４６１が主走査方向に移動することにより基板９上の照射位置が主走査方向に移動されてもよい。描画装置１では、基板９を主走査方向に移動しつつ、図２に示す制御部６の光変調素子制御部６１により、光変調素子４６１からの光の変調がデータ変換装置７から描画装置１へと出力された出力データに基づいて制御されることにより、データ変換装置７に入力された入力データが示すパターンが基板９上に描画される。
【００３１】
次に、データ変換装置７について説明する。図６は、データ変換装置７の構成を示す図である。データ変換装置７は、通常のコンピュータと同様に、各種演算処理を行うＣＰＵ７０１、実行されるプログラムを記憶したり演算処理の作業領域となるＲＡＭ７０２、基本プログラムを記憶するＲＯＭ７０３、各種情報を記憶する固定ディスク７０４、作業者に各種情報を表示するディスプレイ７０５、および、キーボードやマウス等の入力部７０６等を接続した構成となっている。固定ディスク７０４内には、データ変換装置７により実行されるプログラム７０４１が記憶される。プログラム７０４１は、基板上に描画される予定のパターンを示すベクトルデータである入力データを、ランレングスデータである出力データに変換する（すなわち、ラスタライズを行う）プログラムである。
【００３２】
図１では、データ変換装置７のＣＰＵ７０１（図６参照）等がプログラム７０４１に従って演算処理等を行うことにより（すなわち、プログラム７０４１がデータ変換装置７により実行されることにより）実現される機能をブロックにて示しており、図１中のデータ受付部７１、図形要素比較部７２、代表図形要素記憶部７３、部分ランレングスデータ生成部７４、単位領域設定部７５、単位ランレングスデータ生成部７６、ランレングス記憶部７７、フォーマット変換部７８およびデータ出力部７９が、ＣＰＵ７０１等により実現される機能に相当する。なお、これらの機能は複数台のコンピュータにより実現されてもよい。
【００３３】
次に、データ変換装置７による入力データから出力データへのデータ変換について説明する。図７．Ａおよび図７．Ｂは、データ変換装置７によるデータ変換の流れを示す図である。データ変換装置７では、まず、図１に示すデータ受付部７１によりベクトルデータである入力データが受け付けられる（ステップＳ１１）。
【００３４】
図８．Ａは、入力データにより表されるパターンを示す図である。図８．Ａに示すように、入力データでは、所定の配置領域８０に描画されるパターンを複数の図形要素として捉えた上で、複数の図形要素のそれぞれが、各図形要素の形状や基板９（図２および図３参照）上における位置等を示すベクトルデータの集合であるデータ要素として表現される。
【００３５】
図８．Ａに示す複数の図形要素８１〜８８が配置される配置領域８０では、配置領域８０における図形要素８１〜８８の位置は、図形要素８１〜８８をそれぞれ内側に含む矩形領域８１０〜８８０の左下の頂点８１１〜８８１（以下、「固有原点」という。）の座標にて示される。図形要素８１は台形であり、図形要素８２と図形要素８３とは同じ大きさの平行四辺形である。また、図形要素８４と図形要素８５とは同じ大きさの長方形であり、図形要素８６〜８８は互いに同じ大きさの六角形である。なお、図８．Ａでは、図の理解を容易にするために、図形要素８１〜８８にそれぞれ平行斜線を付している。
【００３６】
図８．Ａでは、図中の上側から下側へと向かう方向（以下、「第１の方向」という。）が、図２および図３に示す描画装置１における（＋Ｙ）側から（−Ｙ）側へと向かう主走査方向に対応し、図中の左側から右側に向かう方向（すなわち、第１の方向に垂直な方向であり、以下、「第２の方向」という。）が、描画装置１における（＋Ｘ）側から（−Ｘ）側へと向かう副走査方向に対応する。
【００３７】
後述するように、配置領域８０は、図８．Ｂに示すように、第１の方向を向く複数の直線８０１（すなわち、描画装置１における主走査方向に平行な直線であり、以下、「走査線８０１」という。）にて所定幅毎に分割され、これにより、第２の方向に配列された上記所定幅（図１に示す描画装置１の描画の分解能に基づいて決定される幅であり、以下、「単位幅」という。）の複数の領域８００が設定され、図形要素８１〜８８の固有原点８１１〜８８１は、これらの複数の走査線８０１のいずれかの上に設定される。したがって、図形要素８８のように、図８．Ｂ中の最も左側の部位が走査線８０１上に位置しない場合、図形要素８８の固有原点８８１は図形要素８８から左側に離れた位置に位置し、固有原点８８１を一の頂点として有する矩形領域８８０の輪郭は、図形要素８８の左側において図形要素８８に外接しない。なお、本実施の形態では、図形要素８８以外の各図形要素は、各図形要素の最も左側の部位が走査線８０１上に位置しており、各図形要素を含む矩形領域の左側のエッジに接する。
【００３８】
実際のデータ変換装置７では、後述する処理が、入力データに含まれる複数の図形要素８１〜８８に対応するデータ要素に対して行われるが、以下の説明では、理解を容易とするために、図形要素８１〜８８を処理の取扱対象として説明する。なお、実際の入力データは通常、図８．Ａに示すものよりも多種類かつ多様な形状の多数の図形要素を示すデータ要素を含む。
【００３９】
図１に示すデータ受付部７１により入力データが受け付けられると、図形要素比較部７２により、入力データに含まれる複数の図形要素のベクトルデータから図８．Ａに示す一の図形要素８１が選択され（ステップＳ１２）、選択された図形要素８１（以下、「選択図形要素８１」と呼ぶ。）と代表図形要素記憶部７３（図１参照）に格納される代表図形要素群とが比較される。代表図形要素群とは、代表的な形状を有する図形要素である代表図形要素の集合であり、最初の選択図形要素８１が選択された段階では、代表図形要素群は１つの代表図形要素も含んでいない。
【００４０】
したがって、代表図形要素群には選択図形要素８１の形状と同じ形状の代表図形要素は含まれていないと判断され（ステップＳ１３）、選択図形要素８１と同じ形状を有する新たな代表図形要素８９ａ（を示すデータ要素）が生成されて代表図形要素記憶部７３へと送られ、図９．Ａに示すように、代表図形要素群８９０に追加される（ステップＳ１４）。また、選択図形要素８１には、代表図形要素８９ａを示す識別子である代表図形識別子が図形要素比較部７２により関連付けられる（ステップＳ１５）。図９．Ａでは、図の理解を容易にするために、代表図形要素を囲む二点鎖線の矩形にて代表図形要素群８９０を描いている（図９．Ｂないし図９．Ｅ、並びに、図１０においても同様）。
【００４１】
代表図形要素８９ａと代表図形要素８９ａの固有原点８９１ａとの位置関係は、選択図形要素８１と選択図形要素８１の固有原点８１１（図８．Ａ参照）との位置関係と同様とされるが、代表図形要素８９ａの固有原点８９１ａの位置は、選択図形要素８１の固有原点８１１の位置とは無関係に、予め定められた座標とされる。また、代表図形要素８９ａを内側に含む矩形領域８９０ａは、選択図形要素８１を内側に含む矩形領域８１０（図８．Ａ参照）に対応している。なお、本段落の代表図形要素８９ａに関する記述は、後述する他の代表図形要素においても同様である。
【００４２】
図形要素８１に代表図形識別子が関連付けられると、次の図形要素が存在するため（ステップＳ１６）、ステップＳ１２に戻り、図８．Ａに示す図形要素８２が次の選択図形要素として選択される（ステップＳ１２）。本実施の形態では、図形要素の選択は各図形要素に付された符号の順に行われるが、当該選択の順序は適宜変更されてよい。図形要素８２が選択されると、図形要素比較部７２（図１参照）により、選択図形要素８２と代表図形要素記憶部７３（図１参照）に格納されている代表図形要素群８９０（図９．Ａ参照）とが比較される。代表図形要素群８９０との比較では、選択図形要素８２の固有原点８２１と代表図形要素群８９０に含まれる各代表図形要素（現段階では、代表図形要素８９ａのみ）の固有原点とを一致させた際に、選択図形要素８２の形状と各代表図形要素の形状とが一致するか否かが確認され、一致する場合にのみ選択図形要素８２の形状と各代表図形要素の形状とが同じと判断される。
【００４３】
この場合、選択図形要素８２の固有原点８２１と代表図形要素８９ａの固有原点８９１ａ（図９．Ａ参照）とを一致させた際に選択図形要素８２の形状と代表図形要素８９ａの形状とは一致しないため、選択図形要素８２の形状は代表図形要素８９ａの形状と異なると判断され、選択図形要素８２の形状と同じ形状の代表図形要素は代表図形要素群８９０に含まれていないと判断される（ステップＳ１３）。そして、選択図形要素８２と同じ形状を有する新たな代表図形要素８９ｂが生成され、図９．Ｂに示すように、代表図形要素群８９０に追加される（ステップＳ１４）。また、選択図形要素８２には、代表図形要素８９ｂを示す代表図形識別子が図形要素比較部７２により関連付けられる（ステップＳ１５）。
【００４４】
代表図形要素８９ｂと代表図形要素８９ｂの固有原点８９１ｂとの位置関係は、選択図形要素８２と選択図形要素８２の固有原点８２１（図８．Ａ参照）との位置関係と同様とされるが、代表図形要素８９ｂの固有原点８９１ｂの位置は、選択図形要素８２の固有原点８２１の位置とは無関係に、予め定められた座標とされる。なお、図９．Ｂでは、図の理解を容易にするために、代表図形要素８９ａの固有原点８９１ａと代表図形要素８９ｂの固有原点８９１ｂとが異なる位置に位置するものとして描いているが、固有原点８９１ａと固有原点８９１ｂとは同じ位置に位置していてもよい（以下、他の代表図形要素においても同様）。
【００４５】
図形要素８２に代表図形識別子が関連付けられると、次の図形要素が存在するため（ステップＳ１６）、再度ステップＳ１２に戻り、図８．Ａに示す図形要素８３が次の選択図形要素として選択され（ステップＳ１２）、選択図形要素８３と図９．Ｂに示す代表図形要素群８９０とが比較される。具体的には、まず、選択図形要素８３と代表図形要素８９ａとの比較が行われ、選択図形要素８３の形状と代表図形要素８９ａの形状とが一致しないと判断される。次に、選択図形要素８３と代表図形要素８９ｂとの比較が行われ、選択図形要素８３の固有原点８３１と代表図形要素８９ｂの固有原点８９１ｂとを一致させた際に選択図形要素８３の形状と代表図形要素８９ｂの形状とが一致する（すなわち選択図形要素８３の形状と同じ形状の代表図形要素が代表図形要素群８９０に含まれる）と判断され、選択図形要素８３に代表図形要素８９ｂを示す代表図形識別子が関連付けられる（ステップＳ１３，Ｓ１５）。本実施の形態では、図形要素８３に、図形要素８２に関連付けられた代表図形識別子と同じ代表図形識別子が関連付けられる。
【００４６】
図形要素８３に代表図形識別子が関連付けられると、図８．Ａに示す図形要素８４が選択され（ステップＳ１６，Ｓ１２）、図９．Ｂに示す代表図形要素群８９０と比較される。選択図形要素８４は、代表図形要素群８９０に含まれる代表図形要素８９ａおよび代表図形要素８９ｂと形状が異なるため、選択図形要素８４の形状と同じ形状の代表図形要素は代表図形要素群８９０に含まれていないと判断される（ステップＳ１３）。そこで、選択図形要素８４と同じ形状を有する新たな代表図形要素８９ｃが生成され、図９．Ｃに示すように、代表図形要素群８９０に追加される（ステップＳ１４）。また、選択図形要素８４には、代表図形要素８９ｃを示す代表図形識別子が関連付けられる（ステップＳ１５）。
【００４７】
図形要素８４に代表図形識別子が関連付けられると、図８．Ａに示す図形要素８５が選択されて図９．Ｃに示す代表図形要素群８９０と比較され、選択図形要素８５の形状と同じ形状の代表図形要素８９ｃが代表図形要素群８９０に含まれると判断されることにより、選択図形要素８５に代表図形要素８９ｃを示す代表図形識別子が関連付けられる（ステップＳ１６，Ｓ１２，Ｓ１３，Ｓ１５）。
【００４８】
図形要素８５に代表図形識別子が関連付けられると、図８．Ａに示す図形要素８６が選択され、選択図形要素８６の形状と同じ形状の代表図形要素が代表図形要素群８９０に含まれていないと判断されることにより、図９．Ｄに示すように、選択図形要素８６と同じ形状を有する新たな代表図形要素８９ｄが代表図形要素群８９０に追加され、選択図形要素８６に代表図形要素８９ｄを示す代表図形識別子が関連付けられる（ステップＳ１６，Ｓ１２〜Ｓ１５）。続いて、図８．Ａに示す図形要素８７が選択されて図９．Ｄに示す代表図形要素群８９０と比較され、選択図形要素８７の形状と同じ形状の代表図形要素８９ｄが代表図形要素群８９０に含まれると判断されることにより、選択図形要素８７に代表図形要素８９ｄを示す代表図形識別子が関連付けられる（ステップＳ１６，Ｓ１２，Ｓ１３，Ｓ１５）。
【００４９】
次に、図８．Ａに示す図形要素８８が選択され（ステップＳ１６，Ｓ１２）、図９．Ｄに示す代表図形要素群８９０と比較され、まず、代表図形要素８９ａ〜８９ｃとは異なる形状を有すると判断される。上述のように、図形要素８８は図形要素８６，８７と同じ大きさの六角形であるが、図８．Ｂに示すように、図形要素８８と図形要素８８の固有原点８８１との位置関係は、図形要素８６，８７とそれぞれの固有原点８６１，８７１との位置関係と異なるため、図形要素８６，８７と同じ形状である代表図形要素８９ｄと代表図形要素８９ｄの固有原点８９１ｄとの位置関係とも異なる。
【００５０】
したがって、選択図形要素８８の固有原点８８１と代表図形要素８９ｄの固有原点８９１ｄとを一致させた際に選択図形要素８８の形状と代表図形要素８９ｄの形状とは一致せず、選択図形要素８８の形状と同じ形状の代表図形要素が代表図形要素群８９０に含まれていないと判断される（ステップＳ１３）。そして、図９．Ｅに示すように、選択図形要素８８と同じ形状を有する新たな代表図形要素８９ｅ（すなわち、代表図形要素８９ｄと同じ大きさの六角形ではあるが、それぞれの固有原点との位置関係が異なる代表図形要素）が代表図形要素群８９０に追加され、選択図形要素８８に代表図形要素８９ｅを示す代表図形識別子が関連付けられる（ステップＳ１４，Ｓ１５）。
【００５１】
このように、データ変換装置７では、入力データに含まれる複数の図形要素８１〜８８のベクトルデータに基づいて、上述のステップＳ１２〜Ｓ１６が図形要素８１〜８８に対して順次繰り返され、各図形要素が代表図形識別子と関連付けられる。本実施の形態では、全図形要素８１〜８８に対してステップＳ１２〜Ｓ１６が行われることにより、図９．Ｅに示すように、代表図形要素群８９０が５つの代表図形要素８９ａ〜８９ｅを有することとなる。
【００５２】
全図形要素８１〜８８に代表図形識別子が関連付けられると、部分ランレングスデータ生成部７４（図１参照）により、代表図形要素群８９０に含まれる各代表図形要素（具体的には、代表図形要素８９ａ〜８９ｅをそれぞれ内側に含む矩形領域８９０ａ〜８９０ｅ）が、図１０に示すように、第１の方向を向く直線８０２にて上述の単位幅毎に分割され、第２の方向に配列された単位幅の複数の領域８９２が設定される。本実施の形態では、代表図形要素８９ａ〜８９ｄはそれぞれ、６つの領域８９２（以下、「代表図形分割領域８９２」という。）に分割されており、代表図形要素８９ｅは７つの代表図形分割領域８９２に分割される。
【００５３】
そして、各代表図形要素の分割された代表図形分割領域８９２において、代表図形要素の各代表図形分割領域８９２と重なる部分の情報が各代表図形分割領域８９２のランレングスとして取得され、代表図形分割領域８９２のランレングスの集合として各代表図形要素を表す部分ランレングスデータが生成される（ステップＳ１７）。
【００５４】
本実施の形態では、代表図形分割領域８９２のランレングスは、代表図形要素の代表図形分割領域８９２と重なる部分の第１の方向における始点および長さにより表される。なお、代表図形分割領域８９２のランレングスは、例えば、代表図形要素の代表図形分割領域８９２と重なる部分の第１の方向における始点および終点により表されてもよい。また、図１０では、代表図形要素８９ａ〜８９ｅの全ての固有原点８９１ａ〜８９１ｅが１本の直線８０２上に位置しているが、各代表図形要素の固有原点は、いずれかの直線８０２上に位置していればよい。
【００５５】
続いて、単位領域設定部７５（図１参照）により、複数の図形要素８１〜８８が配置される配置領域８０が、図８．Ｂに示すように、第１の方向を向く複数の走査線８０１にて単位幅に分割されることにより、第２の方向に配列された単位幅の複数の領域８００（以下、「単位領域８００」という。）が設定される（ステップＳ１８）。なお、ステップＳ１８における単位領域８００の設定は、ステップＳ１７における部分ランレングスデータの生成よりも前に行われてもよく、ステップＳ１７と並行して行われてもよい。
【００５６】
単位領域８００が設定されると、単位ランレングスデータ生成部７６（図１参照）により、複数の単位領域８００のうち一の単位領域８００が注目単位領域として決定される。本実施の形態では、図１１．Ａにおいて太実線にて囲んで示すように、図中の最も左側の単位領域８００が最初の注目単位領域８００ａとして決定され（ステップＳ１９）、配置領域８０における注目単位領域８００ａの位置と入力データが示す図形要素の位置とに基づいて、注目単位領域８００ａと重なる一または複数の図形要素が注目図形要素として抽出される（ステップＳ２０）。注目図形要素の抽出は、各図形要素の形状を示すベクトルデータ、および、配置領域８０における各図形要素の位置を示すデータに基づいて行われ、この場合、図形要素８１が注目図形要素として抽出される。
【００５７】
１つ以上の注目図形要素が抽出されると、各注目図形要素の配置領域８０における位置、および、各注目図形要素に関連付けられた代表図形識別子が示す代表図形要素の部分ランレングスデータに基づいて、各注目図形要素の注目単位領域８００ａと重なるランレングスである注目ランレングスが取得される。具体的には、図形要素８１に関連付けられた代表図形識別子が示す代表図形要素８９ａ（図１０参照）の部分ランレングスデータから、図形要素８１の配置領域８０における位置を示す固有原点８１１と注目単位領域８００ａとの位置関係に基づいて、最も左側の代表図形分割領域８９２（図１０参照）のランレングスが注目ランレングスとして取得される。そして、当該注目ランレングスに基づいて注目単位領域８００ａの単位ランレングスデータが生成され、ランレングス記憶部７７（図１参照）に記憶される（ステップＳ２１）。
【００５８】
最初の注目単位領域８００ａの単位ランレングスデータが生成されると、次の単位領域８００（すなわち、単位ランレングスデータの生成が未了の単位領域８００）があるためステップＳ１９に戻り、図１１．Ｂに示すように、図中の左側から２番目の単位領域８００が次の注目単位領域８００ａとして決定される（ステップＳ２２，Ｓ１９）。そして、注目単位領域８００ａと重なる図形要素８１，８２，８４が注目図形要素として抽出され（ステップＳ２０）、各注目図形要素の配置領域８０における位置、および、各注目図形要素に関連付けられた代表図形識別子が示す代表図形要素の部分ランレングスデータに基づいて、各注目図形要素の注目単位領域８００ａと重なるランレングスである注目ランレングスが取得される。
【００５９】
具体的には、図形要素８１に関連付けられた代表図形要素８９ａの図１０中の左側から２番目の代表図形分割領域８９２のランレングス、図形要素８２に関連付けられた代表図形要素８９ｂの最も左側の代表図形分割領域８９２のランレングス、および、図形要素８４に関連付けられた代表図形要素８９ｃの最も左側の代表図形分割領域８９２のランレングスが注目ランレングスとして取得され、これらの注目ランレングスに基づいて図１１．Ｂに示す注目単位領域８００ａの単位ランレングスデータが生成されてランレングス記憶部７７（図１参照）に記憶される（ステップＳ２１）。
【００６０】
データ変換装置７では、ステップＳ１８において設定された複数の単位領域８００に対して、上述のステップＳ１９〜Ｓ２２が順次繰り返される。例えば、図１１．Ｃに示すように、左側から１５番目の単位領域８００が注目単位領域８００ａとなる状態では、注目単位領域８００ａと重なる図形要素８６，８８が注目図形要素として抽出され、図形要素８６に関連付けられた代表図形要素８９ｄの図１０中の最も左側の代表図形分割領域８９２のランレングス、および、図形要素８８に関連付けられた代表図形要素８９ｅの最も左側の代表図形分割領域８９２のランレングスが注目ランレングスとして取得され、これらの注目ランレングスに基づいて図１１．Ｃに示す注目単位領域８００ａの単位ランレングスデータが生成される。
【００６１】
また、図１１．Ｄに示すように、左側から２６番目の単位領域８００が注目単位領域８００ａとなる状態では、図１１．Ｃと同様に、注目単位領域８００ａと重なる図形要素８６，８８が注目図形要素として抽出され、図形要素８６に関連付けられた代表図形要素８９ｄの図１０中の最も右側の代表図形分割領域８９２のランレングス、および、図形要素８８に関連付けられた代表図形要素８９ｅの右側から２番目の代表図形分割領域８９２のランレングスが注目ランレングスとして取得され、これらの注目ランレングスに基づいて図１１．Ｄに示す注目単位領域８００ａの単位ランレングスデータが生成される。
【００６２】
さらには、図１１．Ｅに示すように、左側から２７番目の単位領域８００が注目単位領域８００ａとなる状態では、注目単位領域８００ａと重なる図形要素８８のみが注目図形要素として抽出され、図形要素８８に関連付けられた代表図形要素８９ｅの図１０中の最も右側の代表図形分割領域８９２のランレングスが注目ランレングスとして取得され、当該注目ランレングスに基づいて図１１．Ｅに示す注目単位領域８００ａの単位ランレングスデータが生成される。
【００６３】
このように、データ変換装置７では、次の単位領域８００が存在しなくなるまで、配置領域８０の複数の単位領域８００のそれぞれと重なる一または複数の図形要素のランレングスを示す単位ランレングスデータが、第２の方向に向かって順次生成されてランレングス記憶部７７に記憶され、ランレングス記憶部７７にてこれらの単位ランレングスデータが、対応する単位領域８００の位置を示すデータと関連付けられることにより、入力データに含まれる複数の図形要素８１〜８８のランレングスデータである出力データが生成される。
【００６４】
なお、上述のステップＳ２０における注目図形要素の抽出では、配置領域８０中の全ての図形要素について注目単位領域との重なりの判定が行われてもよいが、右側のエッジが注目単位領域よりも左側に位置する図形要素については、注目単位領域との重なりの判定が行われることなく、注目図形要素の候補から除外されることが好ましい。これにより、注目図形要素の抽出に要する時間が短縮される。
【００６５】
図１に示す描画システム１００では、データ変換装置７において生成された出力データが、フォーマット変換部７８により描画装置１における処理に適合するフォーマットにフォーマット変換された後、データ出力部７９により描画装置１へと出力される。そして、当該フォーマット変換後のデータに基づいて図２に示す制御部６の光変調素子制御部６１から各空間光変調器４６へと信号が送られるとともに、主走査機構２５により基板９が主走査方向（すなわち、基板９上における上記第１の方向に対応する方向）に移動することにより、データ変換装置７に入力された入力データが示すパターンが基板９上の感光材料に描画される。描画システム１００では、データ変換装置７において出力データがフォーマット変換されることなく描画装置１へと出力され、描画装置１においてフォーマット変換が行われてもよい。
【００６６】
以上に説明したように、データ変換装置７では、ベクトルデータである入力データからランレングスデータである出力データへの変換において、入力データに含まれる複数の図形要素がそれぞれ同じ形状を有する代表図形要素に関連付けられ、各代表図形要素を表す部分ランレングスデータが生成される。続いて、注目単位領域８００ａ上の図形要素の注目単位領域８００ａに重なるランレングスが、当該図形要素に関連付けられた代表図形要素の部分ランレングスデータから取得されることにより、注目単位領域８００ａの単位ランレングスデータが生成される。そして、各単位領域８００の単位ランレングスデータを取得することにより出力データが生成される。
【００６７】
ここで、仮に、入力データに含まれる全ての図形要素についてベクトルデータからランレングスデータへの変換を行い、変換結果に基づいて出力データを生成するデータ変換装置を想定すると、このようなデータ変換装置では、入力データに同じ形状の図形要素が複数含まれる場合であっても、これら同形状の複数の図形要素のランレングスデータを個々に生成することとなり、その結果、出力データの生成に長時間を要することとなる。
【００６８】
この場合、同形状の複数の図形要素について、一の図形要素のランレングスデータのみを生成し、当該ランレングスデータを配置領域の同形状の他の図形要素の位置へと配置したデータ（以下、「全ランレングス配置データ」という。）に基づいて出力データを生成することにより、出力データの生成に要する時間を短縮することは可能である。しかしながら、全ランレングス配置データの容量は、入力データにより示されるパターンの高精細化に伴って増大するため、データ変換処理が全ランレングス配置データをメモリ上に保持した状態で行われる場合、全ランレングス配置データにより使用されるメモリ容量が大きくなってしまい、データ変換の処理速度が低下してしまうおそれがある。
【００６９】
また、全ランレングス配置データの容量が使用可能なメモリ容量に対して過大となる場合には、全ランレングス配置データをメモリ上でに保持するのではなく、中間ファイルとして保持することが必要になる。これにより、全ランレングス配置データへのアクセスに要する時間が、全ランレングス配置データがメモリ上に保持される場合に比べて増大し、その結果、データ変換処理による出力データの生成に要する時間がさらに増大してしまう。
【００７０】
これに対し、本実施の形態に係るデータ変換装置７では、入力データに含まれる全ての図形要素をランレングスデータに変換して配置領域に配置したデータを使用することなく、ベクトルデータである入力データと代表図形要素群を示すデータ（すなわち、各代表図形要素の部分ランレングスデータ）とに基づいて出力データが生成されるため、入力データおよび代表図形要素群のデータをメモリ上に保持した状態でデータ変換処理が行われる場合、入力データおよび代表図形要素群のデータにより使用されるメモリ容量を小さくすることができる。これにより、データ変換の処理速度を向上し、入力データから出力データへの変換に要する時間を短縮して出力データの生成を高速化することができる。また、入力データおよび代表図形要素群のデータをメモリ上に保持するのではなく、中間ファイルとして保持した状態でデータ変換処理が行われる場合には、中間ファイルのデータ容量を小さくすることができる。その結果、中間ファイルへのアクセス速度が向上され、出力データの生成を高速化することができる。
【００７１】
データ変換装置７では、図形要素８６および図形要素８８のように、同じ大きさであっても図形要素と固有原点との位置関係が互いに異なるものを、異なる代表図形要素に関連付けることにより、入力データにおける図形要素の走査線８０１からの第２の方向（すなわち、描画装置１における副走査方向）のずれが出力データに反映され、入力データが示すパターンと出力データが示すパターンとの相違を小さくすることができる。
【００７２】
次に、本発明の第２の実施の形態に係る描画システムについて説明する。図１２は、第２の実施の形態に係る描画システム１００ａの構成を示す図であり、描画システム１００ａは、データ変換装置７ａおよび描画装置１を備える。データ変換装置７ａの構成は、図６に示すデータ変換装置７と同様であり、以下の説明では対応する構成に同符号を付す。また、描画装置１の構成は第１の実施の形態（図２および図３参照）と同様である。
【００７３】
データ変換装置７ａは、ＣＰＵ７０１（図６参照）等がプログラムに従って演算処理等を行うことにより実現される機能として、図１に示すデータ変換装置７と同様に、データ受付部７１、図形要素比較部７２、代表図形要素記憶部７３、部分ランレングスデータ生成部７４、単位領域設定部７５、単位ランレングスデータ生成部７６、ランレングス記憶部７７、フォーマット変換部７８およびデータ出力部７９を備える。データ変換装置７ａでは、部分ランレングスデータ生成部７４が長方形領域抽出部７４１を備える。
【００７４】
データ変換装置７ａによる入力データから出力データへのデータ変換の流れは、第１の実施の形態（図７．Ａおよび図７．Ｂ参照）とほぼ同様であり、図７．Ｂ中のステップＳ１７における部分ランレングスデータの生成方法、および、ステップＳ２１における単位ランレングスデータの生成方法が第１の実施の形態と異なる。以下、データ変換装置７ａによるデータ変換処理について、図７．Ａおよび図７．Ｂを参照しつつ説明を行う。
【００７５】
図１２に示すデータ変換装置７ａでは、まず、第１の実施の形態と同様に、データ受付部７１により、図８．Ａに示す複数の図形要素８１〜８８を含む入力データが受け付けられる（ステップＳ１１）。続いて、図形要素比較部７２（図１２参照）により、入力データに含まれる複数の図形要素８１〜８８が順次選択図形要素とされて代表図形要素群と比較され、選択図形要素の形状と同じ形状の代表図形要素が代表図形要素群に含まれていない場合には、選択図形要素の形状と同じ形状を有する新たな代表図形要素が代表図形要素群に追加されるとともに当該新たな代表図形要素を示す代表図形識別子が選択図形要素に関連付けられ、選択図形要素の形状と同じ形状の代表図形要素が代表図形要素群に含まれる場合には、同じ形状の代表図形要素を示す代表図形識別子が選択図形要素に関連付けられる（ステップＳ１３〜Ｓ１６）。
【００７６】
入力データに含まれる全ての図形要素に対して代表図形識別子が関連付けられると、図１２に示す部分ランレングスデータ生成部７４により、代表図形要素記憶部７３に記憶されている代表図形要素群８９０の５つの代表図形要素８９ａ〜８９ｅ（図９．Ｅ参照）をそれぞれ表す部分ランレングスデータが生成される（ステップＳ１７）。
【００７７】
図１３．Ａおよび図１３．Ｂは、データ変換装置７ａによる部分ランレングスデータの生成の詳細な流れ（すなわち、ステップＳ１７の詳細な流れ）を示す図である。データ変換装置７ａでは、まず、図９．Ｅに示す代表図形要素群８９０に含まれる一の代表図形要素８９ａが選択され（ステップＳ１７１）、長方形領域抽出部７４１により、第１の方向に平行な１対の辺（以下、「第１の辺」という。）を有するとともに第２の方向に平行であって代表図形要素８９ａのエッジ上に位置する１対の辺（以下、「第２の辺」）を有する長方形領域が代表図形要素８９ａに含まれるか否かが確認される（ステップＳ１７２）。
【００７８】
代表図形要素８９ａには上述の長方形領域は含まれていないため、図１０に示すように、代表図形要素８９ａを内側に含む矩形領域８９０ａが直線８０２にて単位幅毎に分割されて複数の代表図形分割領域８９２が設定される（ステップＳ１７３）。そして、代表図形要素８９ａの各代表図形分割領域８９２と重なる部分の情報が各代表図形分割領域８９２のランレングスとして取得され、代表図形分割領域８９２のランレングスの集合として代表図形要素８９ａを表す部分ランレングスデータが生成される（ステップＳ１７４）。
【００７９】
代表図形要素８９ａの部分ランレングスデータが生成されると、次の代表図形要素である代表図形要素８９ｂが選択され（ステップＳ１７５，Ｓ１７１）、代表図形要素８９ａの場合と同様に、代表図形要素８９ｂに上述の長方形領域（すなわち、１対の第１の辺と１対の第２の辺とを有する長方形領域）が含まれていないと判断される（ステップＳ１７２）。そして、代表図形要素８９ｂを内側に含む矩形領域８９０ｂが直線８０２により単位幅毎に分割されて複数の代表図形分割領域８９２が設定され、代表図形分割領域８９２のランレングスの集合として代表図形要素８９ｂを表す部分ランレングスデータが生成される（ステップＳ１７３，Ｓ１７４）。
【００８０】
代表図形要素８９ｂの部分ランレングスデータが生成されると、図９．Ｅに示す代表図形要素８９ｃが次の代表図形要素として選択され、代表図形要素８９ｃが上述の長方形領域を含む（この場合、代表図形要素８９ｃ全体が一の長方形領域となる。）と判断される（ステップＳ１７５，Ｓ１７１，Ｓ１７２）。図１４．Ａは、代表図形要素８９ｃを拡大して示す図である。続いて、長方形領域抽出部７４１により、図１４．Ａにおいて太実線にて囲んで示すように、代表図形要素８９ｃから上記長方形領域８９３ａが抽出される（ステップＳ１７２１）。本実施の形態では、代表図形要素８９ｃ全体が、長方形領域８９３ａとして抽出される。
【００８１】
次に、長方形領域８９３ａを直線８０２にて単位幅毎に複数の代表図形分割領域８９２に分割した場合に複数の代表図形分割領域８９２のうち第２の方向の一方の端に位置する一の代表図形分割領域８９２（本実施の形態では、最も左側の代表図形分割領域８９２）のランレングスが取得される（ステップＳ１７２２）。そして、ステップＳ１７２２にて取得されたランレングス（以下、「代表ランレングス」という。）、および、左側から右側へと向かう（すなわち、第２の方向における一方から他方へと向かう）長方形領域８９３ａの第２の辺の長さが、長方形領域８９３ａを実質的にランレングスの集合として表すデータとして代表図形要素８９ｃの部分ランレングスデータに含められる（ステップＳ１７２３）。この場合、代表図形要素８９ｃと長方形領域８９３ａとが一致しているため、ステップＳ１７２３にて取得されたデータが、代表図形要素８９ｃの部分ランレングスデータとされる。
【００８２】
長方形領域８９３ａを表すデータが部分ランレングスデータに含められると、代表図形要素８９ｃにおいて長方形領域として抽出されなかった領域（以下、「未抽出領域」という。）が存在するか否かが確認され（ステップＳ１７２４）、未抽出領域がないと判断された後、ステップＳ１７５にて次の代表図形要素の有無が確認される。
【００８３】
そして、代表図形要素８９ｄが次の代表図形要素として選択され、図１４．Ｂに示すように、代表図形要素８９ｄが長方形領域８９３ｂおよび長方形領域８９３ｃを含むと判断されて長方形領域８９３ｂおよび長方形領域８９３ｃが代表図形要素８９ｄから抽出される（ステップＳ１７５，Ｓ１７１，Ｓ１７２，Ｓ１７２１）。
【００８４】
代表図形要素８９ｄでは、長方形領域８９３ｂ，８９３ｃのそれぞれにおいて、代表ランレングスと第２の辺の長さが各長方形領域を実質的にランレングスの集合として表すデータとして代表図形要素８９ｄの部分ランレングスデータに含められる（ステップＳ１７２３）。代表図形要素８９ｄには未抽出領域がないため、代表図形要素８９ｅが次の代表図形要素として選択され（ステップＳ１７２４，Ｓ１７５，Ｓ１７１）、代表図形要素８９ｄと同様に、２つの長方形領域が抽出され、各長方形領域の代表ランレングスおよび第２の辺の長さが、代表図形要素８９ｅの部分ランレングスデータに含められて代表図形要素８９ｅの部分ランレングスデータの生成が終了する（ステップＳ１７２，Ｓ１７２１〜Ｓ１７２４）。
【００８５】
このように、データ変換装置７ａでは、代表図形要素８９ａ〜８９ｅのそれぞれの部分ランレングスデータが、代表図形分割領域８９２のランレングスの集合、または、長方形領域の代表ランレングスおよび第２の辺の長さを示すデータとして生成される。換言すれば、各代表図形要素の部分ランレングスデータが、各代表図形要素の代表図形分割領域８９２のランレングスの実質的な集合として生成される。
【００８６】
データ変換装置７ａでは、例えば、図１４．Ｃに示すように、五角形の代表図形要素８９ｆが代表図形要素群に含まれているとすると、代表図形要素８９ｆから長方形領域８９３ｄが抽出され、長方形領域８９３ｄの代表ランレングスおよび第２の辺の長さが、代表図形要素８９ｆの部分ランレングスデータに含められる（ステップＳ１７１，Ｓ１７２，Ｓ１７２１〜Ｓ１７２３）。
【００８７】
続いて、長方形領域８９３ｄの右側の三角形の領域が未抽出領域８９４ａとして抽出され（ステップＳ１７２４，Ｓ１７２５）、代表図形要素８９ｆを内側に含む矩形領域８９０ｆが直線８０２により単位幅毎に分割されて設定された複数の代表図形分割領域８９２において、未抽出領域８９４ａの各代表図形分割領域８９２と重なる部分の情報が未抽出領域８９４ａのランレングスとして取得されて代表図形要素８９ｆの部分ランレングスデータに含められる（ステップＳ１７２６）。
【００８８】
全ての代表図形要素の部分ランレングスデータが生成されると（ステップＳ１７５）、第１の実施の形態と同様に、配置領域８０が直線８０１（図８．Ｂ参照）により分割されて複数の単位領域８００が設定された後（ステップＳ１８）、一の単位領域８００を注目単位領域８００ａとし、注目単位領域８００ａと重なる各注目図形要素の注目ランレングスに基づいて注目単位領域８００ａの単位ランレングスデータが生成される（ステップＳ１９〜Ｓ２２）。そして、全ての単位領域８００に対して、ステップＳ１９〜Ｓ２２が順次繰り返されることにより、出力データが生成される。
【００８９】
上述のステップＳ２１における単位ランレングスデータの生成では、注目単位領域８００ａと重なる注目図形要素が、例えば、長方形領域８９３ｂ，８９３ｃを含む代表図形要素８９ｄと同じ形状を有する図形要素８６である場合、図形要素８６の固有原点８６１、並びに、代表図形要素８９ｄの長方形領域８９３ｂ，８９３ｃのそれぞれの第２の辺の長さ、および、それぞれの固有原点８９１ｄに対する相対位置に基づいて、図形要素８６の長方形領域８９３ｂ，８９３ｃにそれぞれ対応する領域が、注目単位領域８００ａと重なるか否かが判断される。
【００９０】
そして、図形要素８６の長方形領域８９３ｂと対応する領域が注目単位領域８００ａと重なる場合には、長方形領域８９３ｂの代表ランレングスが、図形要素８６の注目単位領域８００ａと重なる注目ランレングスとされる。また、図形要素の長方形領域８９３ｃと対応する領域が注目単位領域８００ａと重なる場合には、長方形領域８９３ｃの代表ランレングスが、図形要素８６の注目ランレングスとされる。
【００９１】
図１２に示す描画システム１００ａでは、第１の実施の形態と同様に、データ変換装置７ａにおいて生成された出力データが、フォーマット変換部７８により描画装置１における処理に適合するフォーマットにフォーマット変換された後、データ出力部７９により描画装置１へと出力される。
【００９２】
以上に説明したように、データ変換装置７ａでは、第１の実施の形態と同様に、ベクトルデータである入力データと代表図形要素群を示すデータとに基づいて出力データが生成されるため、入力データおよび代表図形要素群のデータをメモリ上に保持した状態でデータ変換処理が行われる場合、および、入力データおよび代表図形要素群のデータを中間ファイルとして保持した状態でデータ変換処理が行われる場合の双方において、出力データの生成を高速化することができる。
【００９３】
また、第２の実施の形態に係るデータ変換装置７ａでは、代表図形要素の部分ランレングスデータを生成する際に、代表図形要素から長方形領域が抽出され、長方形領域の左側の端の代表図形分割領域８９２のランレングスと長方形領域の第２の辺の長さとが、長方形領域を実質的にランレングスの集合として表すデータとして部分ランレングスデータに含められる。そして、単位ランレングスデータの生成において、代表図形要素の代表ランレングスおよび第２の辺の長さに基づいて、当該代表図形要素に関連付けられた注目図形要素の長方形領域に対応する領域と注目単位領域８００ａとの重なりが判断され、重なる場合に、長方形領域の代表ランレングスが注目図形要素の注目ランレングスとされる。このように、長方形領域を含む代表図形要素の部分ランレングスデータの生成を簡素化することにより、出力データの生成をより高速化することができる。さらに、代表図形要素群８９０に含まれる複数の代表図形要素の部分ランレングスデータの容量を小さくすることができる。
【００９４】
次に、本発明の第３の実施の形態に係る描画システムについて説明する。図１５は、第３の実施の形態に係る描画システム１００ｂの構成を示す図であり、描画システム１００ｂは、データ変換装置７ｂおよび描画装置１を備える。データ変換装置７ｂの構成は、図６に示すデータ変換装置７と同様であり、以下の説明では対応する構成に同符号を付す。また、描画装置１の構成は第１の実施の形態（図２および図３参照）と同様である。
【００９５】
データ変換装置７ｂは、ＣＰＵ７０１（図６参照）等がプログラムに従って演算処理等を行うことにより実現される機能として、図１２に示すデータ変換装置７ａと同様に、データ受付部７１、図形要素比較部７２、代表図形要素記憶部７３、部分ランレングスデータ生成部７４、単位領域設定部７５、単位ランレングスデータ生成部７６、ランレングス記憶部７７、フォーマット変換部７８およびデータ出力部７９を備える。データ変換装置７ｂでは、部分ランレングスデータ生成部７４が長方形領域抽出部７４１に加えて平行四辺形領域抽出部７４２を備える。
【００９６】
図１６．Ａないし図１６．Ｃは、データ変換装置７ｂによる入力データから出力データへのデータ変換の流れの一部を示す図である。データ変換装置７ｂによるデータ変換の流れは、第２の実施の形態（図７．Ａおよび図７．Ｂ、並びに、図１３．Ａおよび図１３．Ｂ参照）とほぼ同様であり、代表図形要素の部分ランレングスデータが生成される際に各代表図形要素から長方形領域のみならず平行四辺形領域も抽出される点、および、各単位領域の単位ランレングスデータの生成の際に代表図形要素から抽出された平行四辺形領域が利用される点で異なる。
【００９７】
データ変換装置７ｂにおいて部分ランレングスデータが生成される際には、一の代表図形要素が選択され、当該代表図形要素に上述の長方形領域（すなわち、第１の方向に平行な１対の第１の辺を有するとともに第２の方向に平行であって代表図形要素のエッジ上に位置する１対の第２の辺を有する長方形領域）が含まれるか否かが確認される（ステップＳ２７１，Ｓ２７２）。選択された代表図形要素に長方形領域が含まれている場合には、当該代表図形要素から長方形領域が抽出され、長方形領域の代表ランレングスと第２の辺の長さが、当該長方形領域を実質的にランレングスの集合として表すデータとして代表図形要素の部分ランレングスデータに含められる（ステップＳ２７２１〜Ｓ２７２３）。
【００９８】
長方形領域を表すデータが部分ランレングスデータに含められると、あるいは、選択された代表図形要素に長方形領域が含まれていない場合、第１の方向に平行な１対の第１の辺を有するとともに第２の方向に非平行であって代表図形要素のエッジ上に位置する１対の平行な第２の辺を有する平行四辺形領域が、代表図形要素に含まれるか否かが確認される（ステップＳ２７３）。例えば、ステップＳ２７１にて代表図形要素８９ｂ（図９．Ｅ参照）が選択された場合、ステップＳ２７３にて代表図形要素８９ｂに平行四辺形領域が含まれると判断され、代表図形要素８９ｂから図１７．Ａにおいて太実線にて囲んで示すように平行四辺形領域８９５ａが抽出される（ステップＳ２７３１）。本実施の形態では、代表図形要素８９ｂ全体が、平行四辺形領域８９５ａとして抽出される。
【００９９】
次に、平行四辺形領域８９５ａを直線８０２にて単位幅毎に複数の代表図形分割領域８９２に分割した場合に複数の代表図形分割領域８９２のうち第２の方向の一方の端に位置する一の代表図形分割領域８９２（本実施の形態では、最も左側の代表図形分割領域８９２）のランレングスが代表ランレングスとして取得される（ステップＳ２７３２）。そして、当該代表ランレングス、並びに、左側から右側へと向かう（すなわち、第２の方向における一方から他方へと向かう）平行四辺形領域８９５ａの第２の辺の第２の方向における長さ、および、第２の辺の第２の方向に対する傾きが、平行四辺形領域８９５ａを実質的にランレングスの集合として表すデータとして代表図形要素８９ｂの部分ランレングスデータに含められる（ステップＳ２７３３）。この場合、代表図形要素８９ｂと平行四辺形領域８９５ａとが一致しているため、ステップＳ２７３３にて取得されたデータが、代表図形要素８９ｂの部分ランレングスデータとされる。
【０１００】
平行四辺形領域８９５ａを表すデータが部分ランレングスデータに含められると、代表図形要素８９ｂにおいて平行四辺形領域として抽出されなかった未抽出領域が存在するか否かが確認され（ステップＳ２７３４）、未抽出領域がないと判断された後、ステップＳ２７６にて次の代表図形要素の有無が確認される。
【０１０１】
ここで、例えば、図１７．Ｂに示すように、五角形の代表図形要素８９ｇが代表図形要素群に含まれているとすると、代表図形要素８９ｇから平行四辺形領域８９５ｂが抽出され、平行四辺形領域８９５ｂの代表ランレングス、第２の辺の第２の方向における長さ（すなわち、第２の方向における第２の辺の両端間の距離）、および、第２の辺の第２の方向に対する傾きが、代表図形要素８９ｇの部分ランレングスデータに含められる（ステップＳ２７３１〜Ｓ２７３３）。
【０１０２】
続いて、平行四辺形領域８９５ａの右側の三角形の領域が未抽出領域８９４ｂとして抽出され（ステップＳ２７３４，Ｓ２７３５）、代表図形要素８９ｇを内側に含む矩形領域８９０ｇが直線８０２により単位幅毎に分割されて設定された複数の代表図形分割領域８９２において、未抽出領域８９４ｂの各代表図形分割領域８９２と重なる部分の情報が未抽出領域８９４ｂのランレングスとして取得されて代表図形要素８９ｇの部分ランレングスデータに含められ（ステップＳ２７３６）、その後、ステップＳ２７６にて次の代表図形要素の有無が確認される。
【０１０３】
一方、選択された代表図形要素に平行四辺形領域が含まれていない場合（ステップＳ２７３）、代表図形要素を内側に含む上述の矩形領域（図１０中の矩形領域８９０ａ参照）が直線８０２にて単位幅毎に分割されて複数の代表図形分割領域８９２が設定される（ステップＳ２７４）。そして、代表図形要素の各代表図形分割領域８９２と重なる部分の情報が各代表図形分割領域８９２のランレングスとして取得され、代表図形分割領域８９２のランレングスの集合として代表図形要素を表す部分ランレングスデータが生成される（ステップＳ２７５）。
【０１０４】
全ての代表図形要素の部分ランレングスデータが生成されると、第１および第２の実施の形態と同様に、配置領域８０が直線８０１（図８．Ｂ参照）により分割されて複数の単位領域８００が設定された後（図７．Ａ：ステップＳ１８）、一の単位領域８００を注目単位領域８００ａとし、注目単位領域８００ａと重なる各注目図形要素の注目ランレングスに基づいて注目単位領域８００ａの単位ランレングスデータが生成される（ステップＳ１９〜Ｓ２２）。そして、全ての単位領域８００に対して、ステップＳ１９〜Ｓ２２が順次繰り返されることにより、出力データが生成される。
【０１０５】
上述のステップＳ２１における単位ランレングスデータの生成では、注目単位領域８００ａと重なる注目図形要素が、平行四辺形領域８９５ａを含む代表図形要素８９ｂと同じ形状を有する図形要素８２である場合、図形要素８２の固有原点８２１、並びに、代表図形要素８９ｂの平行四辺形領域８９５ａの第２の辺の第２の方向における長さ、および、平行四辺形領域８９５ａの固有原点８９１ｂに対する相対位置に基づいて、図形要素８２の平行四辺形領域８９５ａに対応する領域（この場合は、図形要素８２全体）が、注目単位領域８００ａと重なるか否かが判断される。
【０１０６】
そして、図形要素８２の平行四辺形領域８９５ａと対応する領域が注目単位領域８００ａと重なる場合には、平行四辺形領域８９５ａの代表ランレングス、および、平行四辺形領域８９５ａの第２の辺の第２の方向に対する傾きに基づいて、図形要素８２の注目単位領域８００ａと重なる注目ランレングスが取得される。具体的には、図形要素８２の平行四辺形領域８９５ａと対応する領域における左端の代表図形分割領域８９２と注目単位領域８００ａとの間の距離に、平行四辺形領域８９５ａの第２の辺の傾きを乗算した値だけ代表ランレングスの第１の方向における位置をずらすことにより、図形要素８２の注目ランレングスが取得される。
【０１０７】
図１５に示す描画システム１００ｂでは、第１および第２の実施の形態と同様に、データ変換装置７ｂにおいて生成された出力データが、フォーマット変換部７８により描画装置１における処理に適合するフォーマットにフォーマット変換された後、データ出力部７９により描画装置１へと出力される。
【０１０８】
以上に説明したように、データ変換装置７ｂでは、第１の実施の形態と同様に、ベクトルデータである入力データと代表図形要素群を示すデータとに基づいて出力データが生成されるため、入力データおよび代表図形要素群のデータをメモリ上に保持した状態でデータ変換処理が行われる場合、および、入力データおよび代表図形要素群のデータを中間ファイルとして保持した状態でデータ変換処理が行われる場合の双方において、出力データの生成を高速化することができる。
【０１０９】
第３の実施の形態に係るデータ変換装置７ｂでは、第２の実施の形態と同様に、長方形領域を含む代表図形要素の部分ランレングスデータの生成を簡素化し、さらに、平行四辺形領域を含む代表図形要素の部分ランレングスデータの生成をも簡素化することにより、出力データの生成をさらに高速化することができる。また、代表図形要素群８９０に含まれる複数の代表図形要素の部分ランレングスデータの容量をさらに小さくすることができる。
【０１１０】
次に、本発明の第４の実施の形態に係る描画システムについて説明する。図１８は、第４の実施の形態に係る描画システム１００ｃの構成を示す図であり、描画システム１００ｃは、データ変換装置７ｃおよび描画装置１を備える。データ変換装置７ｃの構成は、図６に示すデータ変換装置７と同様であり、以下の説明では対応する構成に同符号を付す。また、描画装置１の構成は第１の実施の形態（図２および図３参照）と同様である。
【０１１１】
データ変換装置７ｃは、ＣＰＵ７０１（図６参照）等がプログラムに従って演算処理等を行うことにより実現される機能として、図１６に示すデータ変換装置７ｂと同様に、データ受付部７１、図形要素比較部７２、代表図形要素記憶部７３、部分ランレングスデータ生成部７４、単位領域設定部７５、単位ランレングスデータ生成部７６、ランレングス記憶部７７、フォーマット変換部７８およびデータ出力部７９を備える。データ変換装置７ｃでは、部分ランレングスデータ生成部７４が平行四辺形領域抽出部７４２を備え、図１６に示す長方形領域抽出部７４１は部分ランレングスデータ生成部７４から省略される。
【０１１２】
図１９．Ａおよび図１９．Ｂは、データ変換装置７ｃによる入力データから出力データへのデータ変換の流れの一部を示す図である。データ変換装置７ｃによるデータ変換の流れは、第２の実施の形態（図７．Ａおよび図７．Ｂ、並びに、図１３．Ａおよび図１３．Ｂ参照）とほぼ同様であり、代表図形要素の部分ランレングスデータが生成される際に各代表図形要素から平行四辺形領域が抽出される点、および、各単位領域の単位ランレングスデータの生成の際に代表図形要素から抽出された平行四辺形領域が利用される点で異なる。
【０１１３】
データ変換装置７ｃにおいて部分ランレングスデータが生成される際には、一の代表図形要素が選択され、当該代表図形要素に、第１の方向に平行な１対の第１の辺を有するとともに代表図形要素のエッジ上に位置する１対の平行な第２の辺を有する平行四辺形領域が含まれるか否かが確認される（ステップＳ３７１，Ｓ３７２）。選択された代表図形要素に平行四辺形領域が含まれている場合には、第３の実施の形態と同様に、当該代表図形要素から平行四辺形領域が抽出され、平行四辺形領域の代表ランレングス、第２の辺の第２の方向における長さ、および、第２の辺の第２の方向に対する傾きが、当該平行四辺形領域を実質的にランレングスの集合として表すデータとして代表図形要素の部分ランレングスデータに含められる（ステップＳ３７２１〜Ｓ３７２３）。
【０１１４】
データ変換装置７ｃにおいて代表図形要素から抽出される平行四辺形領域では、１対の第２の辺は、第２の方向に平行であっても平行でなくてもよい。したがって、第１の方向に平行な１対の第１の辺を有するとともに第２の方向に平行であって代表図形要素のエッジ上に位置する１対の第２の辺を有する長方形領域も、上記平行四辺形領域として抽出される。代表図形要素の部分ランレングスデータに含められる長方形領域を表すデータでは、第２の辺の第２の方向における長さは第２の辺の長さに等しく、第２の辺の第２の方向に対する傾きは０とされる。
【０１１５】
平行四辺形領域を表すデータが部分ランレングスデータに含められると、代表図形要素において平行四辺形領域として抽出されなかった未抽出領域が存在するか否かが確認され（ステップＳ３７２４）、未抽出領域がないと判断された場合、ステップＳ３７５にて次の代表図形要素の有無が確認される。逆に、未抽出領域が存在すると判断された場合は、未抽出領域のランレングスが取得されて部分ランレングスデータに含められた後（ステップＳ３７２５，Ｓ３７２６）、ステップＳ３７５にて次の代表図形要素の有無が確認される。
【０１１６】
一方、選択された代表図形要素に平行四辺形領域が含まれていない場合（ステップＳ３７２）、代表図形要素を内側に含む上述の矩形領域（図１０中の矩形領域８９０ａ参照）が単位幅毎に分割されて複数の代表図形分割領域が設定され、代表図形要素の各代表図形分割領域と重なる部分の情報が各代表図形分割領域のランレングスとして取得され、代表図形分割領域のランレングスの集合として代表図形要素を表す部分ランレングスデータが生成される（ステップＳ３７３，Ｓ３７４）。
【０１１７】
全ての代表図形要素の部分ランレングスデータが生成されると、第１ないし第３の実施の形態と同様に、配置領域８０が直線８０１（図８．Ｂ参照）により分割されて複数の単位領域８００が設定された後（図７．Ａ：ステップＳ１８）、一の単位領域８００を注目単位領域８００ａとし、注目単位領域８００ａと重なる各注目図形要素の注目ランレングスに基づいて注目単位領域８００ａの単位ランレングスデータが生成される（ステップＳ１９〜Ｓ２２）。そして、全ての単位領域８００に対して、ステップＳ１９〜Ｓ２２が順次繰り返されることにより、出力データが生成される。
【０１１８】
上述のステップＳ２１における単位ランレングスデータの生成では、注目単位領域８００ａと重なる注目図形要素が、平行四辺形領域を含む代表図形要素と同じ形状を有する図形要素である場合、第３の実施の形態と同様に、図形要素の固有原点、並びに、対応する代表図形要素の平行四辺形領域の第２の辺の第２の方向における長さ、および、代表図形要素の固有原点に対する平行四辺形領域の相対位置に基づいて、図形要素の平行四辺形領域に対応する領域が注目単位領域８００ａと重なるか否かが判断される。そして、図形要素の平行四辺形領域と対応する領域が注目単位領域と重なる場合には、平行四辺形領域の代表ランレングス、および、平行四辺形領域の第２の辺の第２の方向に対する傾きに基づいて、図形要素の注目単位領域８００ａと重なる注目ランレングスが取得される。
【０１１９】
図１８に示す描画システム１００ｃでは、第１ないし第３の実施の形態と同様に、データ変換装置７ｃにおいて生成された出力データが、フォーマット変換部７８により描画装置１における処理に適合するフォーマットにフォーマット変換された後、データ出力部７９により描画装置１へと出力される。
【０１２０】
以上に説明したように、データ変換装置７ｃでは、第１の実施の形態と同様に、ベクトルデータである入力データと代表図形要素群を示すデータとに基づいて出力データが生成されるため、出力データの生成を高速化することができる。また、第３の実施の形態と同様に、平行四辺形領域を含む代表図形要素の部分ランレングスデータの生成を簡素化することにより、出力データの生成をさらに高速化することができる。さらには、代表図形要素群に含まれる複数の代表図形要素の部分ランレングスデータの容量を小さくすることができる。
【０１２１】
次に、本発明の第５の実施の形態に係る描画システムについて説明する。図２０は、第５の実施の形態に係る描画システム１００ｄの構成を示す図であり、描画システム１００ｄは、データ変換装置７ｄおよび描画装置１を備える。データ変換装置７ｄの構成は、図６に示すデータ変換装置７と同様であり、以下の説明では対応する構成に同符号を付す。また、描画装置１の構成は第１の実施の形態（図２および図３参照）と同様である。
【０１２２】
データ変換装置７ｄは、ＣＰＵ７０１（図６参照）等がプログラムに従って演算処理等を行うことにより実現される機能として、データ受付部７１、部分ランレングスデータ生成部７４、単位領域設定部７５、単位ランレングスデータ生成部７６、ランレングス記憶部７７、フォーマット変換部７８およびデータ出力部７９を備え、部分ランレングスデータ生成部７４は、長方形領域抽出部７４１を備える。
【０１２３】
図２１．Ａないし図２１．Ｃは、データ変換装置７ｄによる入力データから出力データへのデータ変換の流れを示す図である。データ変換装置７ｄでは、入力データから出力データへのデータ変換において、上述の代表図形要素群を利用することなく、入力データに含まれる複数の図形要素のそれぞれに対して、長方形領域の抽出や部分ランレングスデータの生成が行われる。
【０１２４】
データ変換装置７ｄによりデータ変換が行われる際には、まず、図２０に示すデータ受付部７１によりベクトルデータである入力データが受け付けられ、部分ランレングスデータ生成部７４により、入力データに含まれる複数の図形要素から一の図形要素が選択される（ステップＳ４１，Ｓ４２）。続いて、選択された図形要素（すなわち、選択図形要素）に、第１の方向に平行な１対の第１の辺を有するとともに第２の方向に平行であって図形要素のエッジ上に位置する１対の第２の辺を有する長方形領域が含まれているか否かが確認される（ステップＳ４３）。
【０１２５】
選択図形要素に長方形領域が含まれている場合、第２の実施の形態に係るデータ変換装置７ａにおいて代表図形要素に対して行われるステップＳ１７２１〜Ｓ１７２６（図１３．Ｂ参照）と同様に、当該選択図形要素から長方形領域が抽出され、長方形領域の代表ランレングス、および、第２の辺の長さが、当該長方形領域を実質的にランレングスの集合として表すデータとして選択図形要素の部分ランレングスデータに含められる（ステップＳ４３１〜Ｓ４３３）。
【０１２６】
長方形領域を表すデータが部分ランレングスデータに含められると、選択図形要素において長方形領域として抽出されなかった未抽出領域が存在するか否かが確認され（ステップＳ４３４）、未抽出領域がないと判断された場合、ステップＳ４６にて次の図形要素の有無が確認される。逆に、未抽出領域が存在すると判断された場合は、未抽出領域のランレングスが取得されて部分ランレングスデータに含められた後（ステップＳ４３５，Ｓ４３６）、ステップＳ４６にて次の図形要素の有無が確認される。
【０１２７】
一方、選択図形要素に長方形領域が含まれていない場合（ステップＳ４３）、図形要素を内側に含む上述の矩形領域（図８．Ｂ中の矩形領域８１０，８２０，８３０参照）が複数の走査線８０１により単位幅毎に分割されて第２の方向に配列された複数の領域（以下、「図形分割領域」という。）が設定され、選択図形要素の各図形分割領域と重なる部分の情報が各図形分割領域のランレングスとして取得される。そして、図形分割領域のランレングスの集合として図形要素を表す部分ランレングスデータが生成された後（ステップＳ４４，Ｓ４５）、ステップＳ４６にて次の図形要素の有無が確認され、入力データに含まれる複数の図形要素に対して上述の部分ランレングスデータの生成が行われる。
【０１２８】
全ての図形要素に対して、分割図形領域のランレングスの実質的な集合として各図形要素を表す部分ランレングスデータが生成されると、第１ないし第４の実施の形態と同様に、配置領域８０が直線８０１（図８．Ｂ参照）により分割されて複数の単位領域８００が設定された後（ステップＳ４７）、一の単位領域８００を注目単位領域８００ａとし、注目単位領域８００ａと重なる一または複数の図形要素が注目図形要素として抽出される（ステップＳ４８，Ｓ４９）。続いて、各注目図形要素の部分ランレングスデータに基づいて、各注目図形要素の注目単位領域８００ａと重なるランレングスである注目ランレングスが取得され、各注目図形要素の注目ランレングスに基づいて注目単位領域８００ａの単位ランレングスデータが生成される（ステップＳ５０，Ｓ５１）。その後、全ての単位領域８００に対して、ステップＳ４８〜Ｓ５１が順次繰り返されることにより、出力データが生成される。
【０１２９】
上述のステップＳ５０における単位ランレングスデータの生成では、注目単位領域８００ａと重なる注目図形要素が上述の長方形領域を含んでいる場合、第２の実施の形態とほぼ同様に、図形要素の固有原点、並びに、長方形領域の第２の辺の長さおよび固有原点に対する相対位置に基づいて、長方形領域が注目単位領域８００ａと重なるか否かが判断される。そして、図形要素の長方形領域が注目単位領域と重なる場合には、長方形領域の代表ランレングスが、図形要素の注目単位領域８００ａと重なる注目ランレングスとされる。
【０１３０】
図２０に示す描画システム１００ｄでは、第１ないし第４の実施の形態と同様に、データ変換装置７ｄにおいて生成された出力データが、フォーマット変換部７８により描画装置１における処理に適合するフォーマットにフォーマット変換された後、データ出力部７９により描画装置１へと出力される。
【０１３１】
以上に説明したように、データ変換装置７ｄでは、長方形領域を含む図形要素の部分ランレングスデータの生成を簡素化することにより、出力データの生成を高速化することができる。また、複数の図形要素の部分ランレングスデータの容量を小さくすることができる。
【０１３２】
以上、本発明の実施の形態について説明してきたが、本発明は上記実施の形態に限定されるものではなく、様々な変更が可能である。
【０１３４】
第１ないし第４の実施の形態に係るデータ変換装置では、最初の選択図形要素と同じ形状の代表図形要素が追加されるまでは、代表図形要素群は代表図形要素を有していないが、代表図形要素群は、最初の選択図形要素が選択されるよりも前の段階で、例えば、汎用される代表的な図形要素の形状と同じ形状を有する一または複数の代表図形要素を予め有していてもよい。
【０１３５】
上記実施の形態に係るデータ変換装置では、入力データに含まれる図形要素は、複数のサブ図形要素を含むサブ図形要素群であってもよい。また、入力データは、一の図形要素が他の図形要素を参照する階層構造とされてもよい。
【０１３６】
データ変換装置により出力データに変換される入力データは、必ずしも液晶表示装置用のガラス基板上に描画されるパターンを示すデータには限定されず、例えば、プラズマ表示装置等の他のフラットパネル表示装置またはフォトマスク用のガラス基板上に描画されるパターンを示すデータであってもよく、ＬＳＩ用のパターンデータであってもよい。また、他の様々な目的に利用される入力データがデータ変換装置により出力データに変換されてもよい。
【０１３７】
描画装置１は、上述の構造を備えるものには限定されず、ランレングスデータである出力データに基づいて描画を行う装置であればよい。例えば、描画装置１の光照射部４は、ＧＬＶ以外の他の光変調素子を備える空間光変調器を備えてもよい。
【図面の簡単な説明】
【０１３８】
【図１】第１の実施の形態に係る描画システムの構成を示す図である。
【図２】描画装置の側面図である。
【図３】描画装置の平面図である。
【図４】空間光変調器を拡大して示す図である。
【図５．Ａ】光変調素子の断面を示す図である。
【図５．Ｂ】光変調素子の断面を示す図である。
【図６】データ変換装置の構成を示す図である。
【図７．Ａ】データ変換の流れを示す図である。
【図７．Ｂ】データ変換の流れを示す図である。
【図８．Ａ】入力データにより表されるパターンを示す図である。
【図８．Ｂ】入力データにより表されるパターンを示す図である。
【図９．Ａ】代表図形要素群を示す図である。
【図９．Ｂ】代表図形要素群を示す図である。
【図９．Ｃ】代表図形要素群を示す図である。
【図９．Ｄ】代表図形要素群を示す図である。
【図９．Ｅ】代表図形要素群を示す図である。
【図１０】代表図形要素群を示す図である。
【図１１．Ａ】入力データにより表されるパターンを示す図である。
【図１１．Ｂ】入力データにより表されるパターンを示す図である。
【図１１．Ｃ】入力データにより表されるパターンを示す図である。
【図１１．Ｄ】入力データにより表されるパターンを示す図である。
【図１１．Ｅ】入力データにより表されるパターンを示す図である。
【図１２】第２の実施の形態に係る描画システムの構成を示す図である。
【図１３．Ａ】データ変換の流れの一部を示す図である。
【図１３．Ｂ】データ変換の流れの一部を示す図である。
【図１４．Ａ】代表図形要素を示す図である。
【図１４．Ｂ】代表図形要素を示す図である。
【図１４．Ｃ】代表図形要素を示す図である。
【図１５】第３の実施の形態に係る描画システムの構成を示す図である。
【図１６．Ａ】データ変換の流れの一部を示す図である。
【図１６．Ｂ】データ変換の流れの一部を示す図である。
【図１６．Ｃ】データ変換の流れの一部を示す図である。
【図１７．Ａ】代表図形要素を示す図である。
【図１７．Ｂ】代表図形要素を示す図である。
【図１８】第４の実施の形態に係る描画システムの構成を示す図である。
【図１９．Ａ】データ変換の流れの一部を示す図である。
【図１９．Ｂ】データ変換の流れの一部を示す図である。
【図２０】第４の実施の形態に係る描画システムの構成を示す図である。
【図２１．Ａ】データ変換の流れを示す図である。
【図２１．Ｂ】データ変換の流れを示す図である。
【図２１．Ｃ】データ変換の流れを示す図である。
【符号の説明】
【０１３９】
１    描画装置
３    基板保持部
７，７ａ〜７ｄ    データ変換装置
９    基板
２５    主走査機構
６１    光変調素子制御部
８０    配置領域
８１〜８８    図形要素
８９ａ〜８９ｇ    代表図形要素
１００，１００ａ〜１００ｄ    描画システム
４６１    光変調素子
８００    単位領域
８００ａ    注目単位領域
８０１    走査線
８０２    直線
８１１〜８８１    固有原点
８９０    代表図形要素群
８９１ａ〜８９１ｅ    固有原点
８９２    代表図形分割領域
８９３ａ〜８９３ｄ    長方形領域
８９５ａ，８９５ｂ    平行四辺形領域
７０４１  プログラム
Ｓ１１〜Ｓ２２，Ｓ４１〜Ｓ５１，Ｓ１７１〜Ｓ１７５，Ｓ２７１〜Ｓ２７６，Ｓ３７１〜Ｓ３７５，Ｓ４３１〜Ｓ４３６，Ｓ１７２１〜Ｓ１７２６，Ｓ２７２１〜Ｓ２７２３，Ｓ２７３１〜Ｓ２７３６，Ｓ３７２１〜Ｓ３７２６    ステップ
【図１】
0005215016.tif 000002
【図２】
0005215016.tif 000003
【図３】
0005215016.tif 000004
【図４】
0005215016.tif 000005
【図５．Ａ】
0005215016.tif 000006
【図５．Ｂ】
0005215016.tif 000007
【図６】
0005215016.tif 000008
【図７．Ａ】
0005215016.tif 000009
【図７．Ｂ】
0005215016.tif 000010
【図８．Ａ】
0005215016.tif 000011
【図８．Ｂ】
0005215016.tif 000012
【図９．Ａ】
0005215016.tif 000013
【図９．Ｂ】
0005215016.tif 000014
【図９．Ｃ】
0005215016.tif 000015
【図９．Ｄ】
0005215016.tif 000016
【図９．Ｅ】
0005215016.tif 000017
【図１０】
0005215016.tif 000018
【図１１．Ａ】
0005215016.tif 000019
【図１１．Ｂ】
0005215016.tif 000020
【図１１．Ｃ】
0005215016.tif 000021
【図１１．Ｄ】
0005215016.tif 000022
【図１１．Ｅ】
0005215016.tif 000023
【図１２】
0005215016.tif 000024
【図１３．Ａ】
0005215016.tif 000025
【図１３．Ｂ】
0005215016.tif 000026
【図１４．Ａ】
0005215016.tif 000027
【図１４．Ｂ】
0005215016.tif 000028
【図１４．Ｃ】
0005215016.tif 000029
【図１５】
0005215016.tif 000030
【図１６．Ａ】
0005215016.tif 000031
【図１６．Ｂ】
0005215016.tif 000032
【図１６．Ｃ】
0005215016.tif 000033
【図１７．Ａ】
0005215016.tif 000034
【図１７．Ｂ】
0005215016.tif 000035
【図１８】
0005215016.tif 000036
【図１９．Ａ】
0005215016.tif 000037
【図１９．Ｂ】
0005215016.tif 000038
【図２０】
0005215016.tif 000039
【図２１．Ａ】
0005215016.tif 000040
【図２１．Ｂ】
0005215016.tif 000041
【図２１．Ｃ】
0005215016.tif 000042