(57)【特許請求の範囲】
【請求項１】
図形データに対して施す図形処理の数をＮ（２以上の自然数）とした場合に、ＦＩＦＯバッファメモリをＮ−１個設け、各図形処理のためのワークメモリをＮ個設け、
一のワークメモリにＸ−Ｙ座標平面内の図形データとして記憶された複数の図形データを一の走査線によって順次Ｙ軸方向へ走査しながら、該一の走査線と交差する図形データに対して一の図形処理を施し、
該一の図形処理が施された図形データを、図形データのＹ座標値で並び替えてＦＩＦＯバッファメモリに順番に入力し、
該ＦＩＦＯバッファメモリからＹ座標値で並び替えられた前記図形データを所定量ずつ取り出してＸ−Ｙ座標平面内の図形データとして他のワークメモリに記憶し、
該他のワークメモリに記憶された図形データを他の走査線によって順次Ｙ軸方向へ走査しながら他の図形処理を施すことにより、複数の図形処理を並列に行なうことを特徴とする図形処理方法。
【請求項２】
図形処理を施す図形データのデータ量に上限を設け、
前記一の走査線による走査によって前記一の図形処理が施された図形データの前記データ量が前記上限に達してから上限を超えるまでに、一の図形処理が施された図形データを前記ＦＩＦＯバッファメモリに入力すると共に、前記一の走査線により走査中の図形データがある場合には、該図形データを一の走査線の位置で分断して新たな複数の図形データとし、該新たな図形データの内の一の図形処理が施された図形データも併せてＦＩＦＯバッファメモリに入力することを特徴とする請求項１記載の図形処理方法。
【請求項３】
図形データに対して施す図形処理の数をＮ（２以上の自然数）とした場合に、ＦＩＦＯバッファメモリをＮ−１個設け、各図形処理のためのワークメモリをＮ個設けたコンピュータが読み取り可能なプログラムであって、
一のワークメモリにＸ−Ｙ座標平面内の図形データとして記憶された複数の図形データを一の走査線によって順次Ｙ軸方向へ走査しながら、該一の走査線と交差する図形データに対して一の図形処理を施し、
該一の図形処理が施された図形データを、図形データのＹ座標値で並び替えてＦＩＦＯバッファメモリに順番に入力し、
該ＦＩＦＯバッファメモリからＹ座標値で並び替えられた前記図形データを所定量ずつ取り出してＸ−Ｙ座標平面内の図形データとして他のワークメモリに記憶し、
該他のワークメモリに記憶された図形データを他の走査線によって順次Ｙ軸方向へ走査しながら他の図形処理を施すことにより、複数の図形処理を並列に行なうことを特徴とするコンピュータが読み取り可能なプログラムを格納した記憶媒体。
【請求項４】
図形処理を施す図形データのデータ量に上限を設け、
前記一の走査線による走査によって前記一の図形処理が施された図形データの前記データ量が前記上限に達してから上限を超えるまでに、一の図形処理が施された図形データを前記ＦＩＦＯバッファメモリに入力すると共に、前記一の走査線により走査中の図形データがある場合には、該図形データを一の走査線の位置で分断して新たな複数の図形データとし、該新たな図形データの内の一の図形処理が施された図形データも併せてＦＩＦＯバッファメモリに入力することを特徴とする請求項３記載のコンピュータが読み取り可能なプログラムを格納した記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、図形処理方法に関し、ＣＡＤ（Computer Aided Design ）を用いてＬＳＩを製造する際のマスクパターンに対してＯＲ処理等の論理処理や拡大処理や縮小処理（サイジング処理）の図形処理を複数適応する図形処理方法とコンピュータが読み取り可能なプログラムを格納した記憶媒体に関する。
【０００２】
【従来の技術】
通常、ＬＳＩを製造する際のマスクパターンのデータ変換システムでは、処理の複雑さを避けるために、多角形で構成されるマスクパターンＰを、図１０に示すように複数の水平台形（上辺と下辺がＸ軸と平行な台形Ａ、Ｂ）に分割して表現し、この水平台形を基本としてＳＩＺＩＮＧ（サイジング）処理を含む各種図形処理（サイジングの他、ＡＮＤ、ＯＲ、ＸＯＲ、ＮＯＴ、ＳＵＢ処理等がある）を行っている。なお、水平台形の概念には、その上辺若しくは下辺の長さが零となる図形、すなわち三角形も含まれるものとする。以下同様。
ここでサイジング処理とは、ＬＳＩのＣＡＤデータを露光（製造）用データに変換するマスクデータ変換システムにおいて、マスクパターン（マスク図形）図形Ｐの外周を一定幅だけ膨らませたり（拡大処理、プラスサイジング処理）、また細らせたり（縮小処理、マイナスサイジング処理）する処理のことである（図１１参照）。これは製造プロセス上起こる変形の補正、設計規則の変更に対応するための補正等の目的で行われる。
【０００３】
そして従来の図形処理方法においては、入力データメモリにＸ−Ｙ座標平面内の図形データとして記憶された複数の図形データに対して上記図形処理を行う場合には、例えば図９に示すようにコンピュータのワークメモリに格納できる程度の小さなブロック（各ブロックの大きさは同じ）に分割してファイルに格納しておき、ファイルから必要な個数だけ取り出してブロック単位で並列処理することでスピードアップを図っていた。
【０００４】
【発明が解決しようとする課題】
しかしながら、このような従来の図形処理方法では、各ブロックの境界にかかる図形データがこの境界線で分断されるため、処理しなければならない図形データの数が増える。このため、図形処理の時間が増加してしまうと共に、分割したブロックを記憶しておくためのファイルの容量も増加してしまうという課題がある。具体的には、ブロック分割しない場合の約２〜６倍程度にまで増加すると考えられる。
【０００５】
従って、本発明は上記課題を解決すべくなされ、その目的とするところは、処理時間を短縮できると共に、処理に必要とされるメモリ容量も少なくて済む図形処理方法を提供することにある。
【０００６】
【課題を解決するための手段】
上記課題を解決するため、本発明にかかる請求項１記載の図形処理方法は、図形データに対して施す図形処理の数をＮ（２以上の自然数）とした場合に、ＦＩＦＯバッファメモリをＮ−１個設け、各図形処理のためのワークメモリをＮ個設け、一のワークメモリにＸ−Ｙ座標平面内の図形データとして記憶された複数の図形データを一の走査線によって順次Ｙ軸方向へ走査しながら、該一の走査線と交差する図形データに対して一の図形処理を施し、該一の図形処理が施された図形データを、図形データのＹ座標値で並び替えてＦＩＦＯバッファメモリに順番に入力し、該ＦＩＦＯバッファメモリからＹ座標値で並び替えられた前記図形データを所定量ずつ取り出してＸ−Ｙ座標平面内の図形データとして他のワークメモリに記憶し、該他のワークメモリに記憶された図形データを他の走査線によって順次Ｙ軸方向へ走査しながら他の図形処理を施すことにより、複数の図形処理を並列に行なうことを特徴とする。
これにより、一の走査線による一の図形処理と他の走査線による他の図形処理とを並列して行えるため、複数の図形処理に要する時間を短縮できる。また、従来のように複数のブロックに分割する必要が無いため、処理する図形データの数が少なくてすみ、処理時間の短縮と共に図形処理のために必要となるメモリ容量が少なくてすむ。
【０００７】
また、図形処理を施す図形データのデータ量に上限を設け、前記一の走査線による走査によって前記一の図形処理が施された図形データの前記データ量が前記上限に達してから上限を超えるまでに、一の図形処理が施された図形データを前記ＦＩＦＯバッファメモリに入力すると共に、前記一の走査線により走査中の図形データがある場合には、該図形データを一の走査線の位置で分断して新たな複数の図形データとし、該新たな図形データの内の一の図形処理が施された図形データも併せてＦＩＦＯバッファメモリに入力することを特徴とする。
さらにこの構成によれば、走査線の走査方向に沿った長い図形データがある場合でも、強制的に一の走査線の位置でこの長い図形データを分断して新たな図形データとすることができるため、分断された図形データの内、既に図形処理が完了した部分の図形データを、既に一の図形処理が完了した他の図形データと共にバッファメモリに記憶でき、並列処理が行えるようになる。
【０００８】
図形データに対して施す図形処理の数をＮ（２以上の自然数）とした場合に、ＦＩＦＯバッファメモリをＮ−１個設け、各図形処理のためのワークメモリをＮ個設けたコンピュータが読み取り可能なプログラムであって、一のワークメモリにＸ−Ｙ座標平面内の図形データとして記憶された複数の図形データを一の走査線によって順次Ｙ軸方向へ走査しながら、該一の走査線と交差する図形データに対して一の図形処理を施し、該一の図形処理が施された図形データを、図形データのＹ座標値で並び替えてＦＩＦＯバッファメモリに順番に入力し、該ＦＩＦＯバッファメモリからＹ座標値で並び替えられた前記図形データを所定量ずつ取り出してＸ−Ｙ座標平面内の図形データとして他のワークメモリに記憶し、該他のワークメモリに記憶された図形データを他の走査線によって順次Ｙ軸方向へ走査しながら他の図形処理を施すことにより、複数の図形処理を並列に行なうことを特徴とする。
【０００９】
さらに、図形処理を施す図形データのデータ量に上限を設け、前記一の走査線による走査によって前記一の図形処理が施された図形データの前記データ量が前記上限に達してから上限を超えるまでに、一の図形処理が施された図形データを前記ＦＩＦＯバッファメモリに入力すると共に、前記一の走査線により走査中の図形データがある場合には、該図形データを一の走査線の位置で分断して新たな複数の図形データとし、該新たな図形データの内の一の図形処理が施された図形データも併せてＦＩＦＯバッファメモリに入力するプログラムを記憶したことを特徴とする。
【００１０】
【発明の実施の形態】
以下、本発明に係る図形処理方法の好適な実施の形態について添付図面と共に詳述する。なお、一例として図形処理を施す複数の図形データとしてはＬＳＩを製造する際のマスクパターンを用いて説明を行う。そして、マスクパターンに対する図形処理の場合には、処理の複雑化を避けるために、前述したように多角形で構成されるマスクパターンを複数の水平台形（上辺と下辺がＸ軸と平行な台形）に分割して表現し、この水平台形を基本として各種図形処理を行っている。従って、１つの水平台形のデータ（例えば各コーナー部分のＸ、Ｙ座標データ）が１つの図形データとなる。
【００１１】
（第１の実施の形態）
本実施の形態の図形処理方法の基本概念について図１〜図３を用いて説明する。
なお、図形処理の内容は、入力データメモリ１０に記憶された複数の図形データに対して、図形処理Ａ、図形処理Ｂ、・・、最終図形処理、という複数の図形処理を順番に施し、最終図形処理が施された図形データを最終データメモリ１２に記憶するというものであるとする。また、複数の図形処理が施されることになる複数の図形データは、図１に示す入力データメモリ１０内に、図２に示すようなＸ−Ｙ座標平面内（詳細には一例としてＸ−Ｙ座標平面の第１象限内）の図形データとして予め記憶されているとする。
【００１２】
そして、本実施の形態の図形処理方法の特徴点は、このような図形データに対して図形処理を施す場合に、従来のように入力データメモリ１０内を図９に示すようなブロックに分割してブロック単位でその中に含まれる図形データに対して図形処理を施すのではなく、ブロックに分けないで平面走査法によるアルゴリズムを使用し、入力データメモリ１０にＸ−Ｙ座標平面内の図形データとして記憶された複数の図形データを、Ｘ−Ｙ座標平面内の図形データとしてワークメモリに記憶して一の走査線Ａによって順次走査しながら、一の走査線Ａと交差する図形データに対して一の図形処理を施す。そして、この一の図形処理が施された図形データをＹ座標値（例えば下辺のＹ座標値）で並び替えてＦＩＦＯ（First In First Out）バッファメモリ（以下、単にバッファメモリとも言う）に入力する。そして、バッファメモリからこの図形データを所定量ずつＸ−Ｙ座標平面内の図形データとして他のワークメモリに記憶すると共に、図３に示すような他のワークメモリに記憶された図形データを他の走査線Ｂによって順次走査しながら他の図形処理を施すようにする点にある。
そして２番目以降のワークメモリのメモリ領域は、入力データメモリ１０と同様にＸ−Ｙ座標平面に形成されているが、相違する点は、そのメモリ容量が、前述の所定量の図形データが記憶できる程度に限定されている、つまり小さい点である。具体的には図３中の斜線部分のメモリ領域は存在しない構成である。
【００１３】
これにより、各図形処理を並列に、いわゆるパイプライン的に処理できるようになり、図形処理に要するトータル時間を短縮できると共に、従来のように図形データを細かなブロックに分割する必要がなくなるために、図形データの数の増加を最小限に抑えられ、分割したブロックを記憶しておくためのファイルの容量が少なくて済む。
なお、平面走査法とは、例えばＸ軸と平行な走査線を、例えばＸ軸上をスタート位置としてＹ軸の軸線方向に沿って順次Ｘ軸から離間させるようにＹ軸のプラス方向へ移動させ、この走査線と交差する図形データに対して所定の図形処理を行うという、アルゴリズムである。なお、走査線をＹ軸と平行なものとし、この走査線をＸ軸の軸線方向に沿って移動させるアルゴリズムも考えられる。この場合には、マスクパターンを複数の水平台形（上辺と下辺がＹ軸と平行な台形）に分割して表現することになる。つまり、走査線は、Ｘ軸若しくはＹ軸のいずれか一方と平行なものであって、走査方向はそれに対応してＹ軸方向若しくはＸ軸方向のいずれか一方の方向となるのである。
【００１４】
そして、必要となるワークメモリやバッファメモリの数は、図形データに対して施す図形処理の数（図形処理Ａ、図形処理Ｂ、・・、最終図形処理の合計数）をＮ（２以上の自然数）とすると、ＦＩＦＯバッファメモリは、Ｎ−１個必要となり、また各図形処理のためのワークメモリはＮ個必要となる。なお、元の図形データが記憶されている入力データメモリ１０を一つのワークメモリと考えた場合にはワークメモリの数はＮ−１個となる。
なお、入力データメモリ１０に記憶された図形データの量が非常に多い場合には、図８に示すように、予め入力データメモリ１０のＸ−Ｙ座標平面に形成されたメモリ空間をＹ軸と平行な直線で複数のセグメントに分割し、各セグメント毎に前述の平面走査法による並列図形処理を適用するようにしても良い。
【００１５】
続いて、図４と図５を用いて、より具体的に図形処理方法について説明する。
ここで、図形処理の数は一例としてＯＲ処理とサイジング（一例として縮小）処理の２つであるが、実際には縮小処理後、最終データメモリに図形データを記憶する際には最終データメモリに格納するための出力処理が必要となるから、合計３つとなる。よって、図１に当てはめて考えると、処理ＡがＯＲ処理に、処理Ｂが縮小処理に、最終処理が出力処理となる。
そして、ワークメモリとバッファメモリのメモリ構成は、ＯＲ処理を行う第１ワークメモリ１１と、縮小処理を行う第２ワークメモリ１４と、出力処理を行う第３ワークメモリ１６と、第１ワークメモリ１１と第２ワークメモリ１４との間に配置された第１バッファメモリ１８と、第２ワークメモリ１４と第３ワークメモリ１６との間に配置された第２バッファメモリ２０という構成となる。
なお、入力データメモリ１０をＯＲ処理する第１ワークメモリ１１として使用することも可能であり、これによりメモリ容量を削減することが可能となる。
【００１６】
また、説明を分かり易くするために、入力データメモリ１０に記憶された図形データは、図４（ａ）のように簡略化され、図形データの下辺のＹ座標値でグループ化すると、ｙ０を下辺のＹ座標値とする図形データ群ｙ０、ｙ１を下辺のＹ座標値とする図形データ群ｙ１、ｙ２を下辺のＹ座標値とする図形データ群ｙ２、ｙ３を下辺のＹ座標値とする図形データ群ｙ３、ｙ４を下辺のＹ座標値とする図形データ群ｙ４、ｙ５を下辺のＹ座標値とする図形データ群ｙ５、の６つのグループにまとめられる。そして図形データ群ｙ０と図形データ群ｙ１とがＹ軸方向に沿って重なるように配置され、図形データ群ｙ２と図形データ群ｙ３とがＹ軸方向に沿って重なるように配置され、図形データ群ｙ４と図形データ群ｙ５とがＹ軸方向に沿って重なるように配置されている。なお、図形データ群ｙ１と図形データ群ｙ２、図形データ群ｙ３と図形データ群ｙ４は、Ｙ軸方向に沿って重ならない配置となっている。
【００１７】
また、本実施の形態においては、各メモリ間で図形データを受け渡す際の最小単位は、図形データの下辺Ｙ座標値でソートする関係上、下辺Ｙ座標値が同じ一群の図形データ、すなわち図形データ群を一単位として行う。そして、図５で表現されたｙ０、ｙ１等は、前述のように下辺Ｙ座標値が同じｙ０、ｙ１等である図形データ群を示す識別子でもある。
【００１８】
まず最初に、入力データメモリ１０に記憶された図形データの内から、一処理単位分の図形データ（予め決めデータ量が決められていて、図形データの一部となる場合や全部となる場合もある）を取り出して第１ワークメモリ１１に記憶する。例えば、上述したように入力データメモリ１０に記憶された図形データを複数のセグメントに分割し、各セグメント毎に前述の平面走査法による並列図形処理を適用するような場合には、１セグメントに含まれる図形データを一処理単位分の図形データとすることが考えられる。
そして、第１ワークメモリ１１に記憶された図形データに対して、走査線（第１走査線とする）を使用した平面走査法によりＯＲ処理を、図形データ群ｙ０、図形データ群ｙ１、図形データ群ｙ２、・・、という順番で各図形データ群に含まれる全ての図形データに対して順次施していく。
そして、第１ワークメモリ１１に記憶された各図形データは、ＯＲ処理された結果、最終的には図４（ｂ）に示すような図形データに変換されるが、このように全ての図形データに対するＯＲ処理が完了してから縮小処理のための第２ワークメモリに一括して記憶されるのではない。
つまり、第１走査線Ａが通過してＯＲ処理が終了した図形データ群から順番に第１バッファメモリ１８に入力される。具体的には下辺のＹ座標値が小さい図形データ群から順番に（下辺のＹ座標値でソートされて）第１バッファメモリ１８に、図形データ群ｙ０、図形データ群ｙ１、図形データ群ｙ２、・・と入力される。そして、第１バッファメモリ１８から所定量ずつＯＲ処理後の図形データ群が取り出されて縮小処理のための第２ワークメモリ１４に記憶されるのである。この所定量とは、本実施の形態では、図形データ群の２個分であるが、これに限定されるものではない。
【００１９】
そして、図３のように構成された第２ワークメモリ１４において、取り込んだ図形データ群に対して第２走査線Ｂを用いた平面走査法により縮小処理を施し、ＯＲ処理の場合と同様に、第２ワークメモリ１４の後段の第２バッファメモリ２０に、第２走査線Ｂが通過して縮小処理が終了した図形データ群から順番に、下辺のＹ座標値でソートして小さい図形データ群から順次入力される。図４（ｃ）は、図４（ｂ）の各図形データに縮小処理を施した状態を示すものであるが、図４（ｃ）中の図形データ群ｙ０、図形データ群ｙ１、・・というように入力される。
なお、第２ワークメモリ１４には、第１バッファメモリ１８から所定量ずつの図形データ群しか取り込まれないから、メモリ容量はこの所定量を考慮した少ないメモリ容量で済み、メモリ領域は図３のような構成で済む。そして、第２ワークメモリ１４は、処理した図形データ群が第２バッファメモリに吐き出される毎に、クリアされる。なお、後から記憶される図形データの書き込みによりクリアされる構成も可能である。
そして、第２バッファメモリ１４に入力された図形データ群は、一旦出力処理のために第３ワークメモリ１６に記憶されて処理された後に最終データメモリ１２に順番に記憶される。
【００２０】
具体的に、図５で図形データの流れを説明する。
第１ワークメモリ１１においては、第１走査線Ａの走査にしたがって、ｙ０、ｙ１、ｙ２、・・、ｙ５という図形データ群に対してＯＲ処理が施され、ｙ０、ｙ１、ｙ２、・・、ｙ８というようにＯＲ処理された図形データ群が順次生成される。
そして、生成された図形データ群は、この順番に順次第１バッファメモリ１８に入力される。最初に、図形データ群ｙ０、ｙ１に対してＯＲ処理を施すと、新たな図形データ群ｙ０、ｙ１、ｙ２が生成されるため、このｙ０、ｙ１、ｙ２が第１バッファメモリ１８に入力される。
【００２１】
そして、第２ワークメモリ１４に第１バッファメモリ１８から所定量（本実施の形態では２個の図形データ群）ずつ取り込まれ、第２走査線Ｂによる走査で縮小処理が施され、新たな図形データ群ｙ０と図形データ群ｙ１が生成され、その後この新たな図形データ群ｙ０、ｙ１は第２バッファメモリ２０に入力される。また、第２ワークメモリ１４における縮小処理と並列に第１ワークメモリ１１においては、次の図形データ群ｙ２、ｙ３に対してＯＲ処理が施され、新たな図形データ群ｙ３、ｙ４、ｙ５が生成されて、第１バッファメモリ１８に入力されている。
次に、第２バッファメモリ２０から図形データ群ｙ０、ｙ１が取り出されて、第３ワークメモリ１６に記憶され、出力処理が施され、最後に最終データメモリ１２に順番に記憶される。そして、第３ワークメモリ１６における出力処理と並列に、第１バッファメモリ１８から第２ワークメモリ１４にｙ２〜ｙ５の内のｙ２とｙ３の２つの図形データ群が取り込まれ、第２走査線Ｂによる走査で縮小処理が施され、新たな図形データ群ｙ２とｙ３が生成されている。
以上、この動作を、最終の図形データ群ｙ８が最終データメモリ１２に記憶されるまで繰り返し、終了する。
【００２２】
（第２の実施の形態）
本実施の形態も、その基本的な考え方は第１の実施の形態と同じであり、従来のようにブロック化せず、平面走査法を用いながら複数の図形処理を並列で行うことによって、処理時間を短縮するものであるが、例えば図６（ａ）にあるように、図形データの一部にＹ軸方向に沿って長い図形データＣ（一例としてその下辺Ｙ座標がｙ０）がある場合には、第１バッファメモリ１８には下辺Ｙ座標値でソートして小さい図形データ群から順番に入力するようになっている関係上、この図形データＣの第１走査線Ａによる走査が完了しない限り、たとえ図形処理が完了した図形データが他にあっても第１バッファメモリ１８に図形データを入力できないという課題がある。
【００２３】
そこで本実施の形態では、第１ワークメモリ１１において図形処理を施す図形データのデータ量に上限を設け、一の走査線による走査によって一の図形処理が施された図形データのデータ量が上限に達してから上限を超えるまでに（詳細には上限に達してから上限を超えるまでのいずれかの時点において）、一の図形処理が施された図形データをＦＩＦＯバッファメモリ１８に入力すると共に、一の走査線により走査中の図形データがある場合には、図形データを一の走査線の位置で分断して新たな複数の図形データとし、新たな図形データの内の一の図形処理が施された図形データも併せてＦＩＦＯバッファメモリ１８に入力する構成としている。これにより、並列処理が行えるようになる。
【００２４】
図６と図７を用いて、図形データの流れを説明する。
なお、各ワークメモリ１１、１４において図形処理を施す図形データのデータ量の上限は、一例として図形データ群４個分としている。また、後段のバッファメモリへの図形処理済みの図形データの入力時期は、一例として図形データのデータ量がこの上限を超える直前としている。図６の（ａ）は、第１ワークメモリ１１に記憶された図形処理前の状態の図形データであり、（ｂ）はＯＲ処理後の図形データ、（ｃ）は縮小処理後の図形データである。
【００２５】
第１ワークメモリ１１においては、第１走査線Ａの走査により、元の図形データ群であるｙ０、ｙ１、ｙ２、・・、に対して順次ＯＲ処理されていく。そして、ＯＲ処理された図形データ群の数が４個に達し（図形データｙ０、ｙ１、ｙ２、ｙ３が図形処理済み）、５個になる直前において、つまり第１走査線Ａが図形データ群ｙ４の下辺に一致した時点で、そこまでにＯＲ処理により生成された図形データ群ｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５を第１バッファメモリ１８に入力する。
そして、第１走査線Ａが図形データ群ｙ４の下辺に一致した時点において、第１走査線Ａが走査中の図形データＣに対しては、この第１走査線Ａの位置で図形データＣを分断し、下辺のＹ座標値がｙ０の図形データＣ１と、下辺のＹ座標値がｙ６の図形データＣ２の２つの新たな図形データを生成する。そして、既に第１走査線Ａが走査されてＯＲ処理が終了した図形データＣ１は、下辺Ｙ座標値がｙ０の他の図形データと共に同じ図形データ群ｙ０に組み入れた状態で第１バッファメモリ１８に入力する。
【００２６】
その後の処理は第１の実施の形態の場合と同様であり、第２ワークメモリ１４に第１バッファメモリ１８から所定量（本実施の形態では２個の図形データ群）ずつ取り込まれ、第２走査線Ｂによる走査で縮小処理が施され、新たな図形データ群ｙ０、ｙ１が生成され、その後この新たな図形データ群ｙ０、ｙ１は第２バッファメモリ２０に入力される。また、第２ワークメモリ１４における縮小処理と並列して、第１ワークメモリ１１においては、図形データ群ｙ４（図形データＣ２を含む）と図形データ群ｙ５に対してＯＲ処理が施され、新たな図形データ群ｙ６、ｙ７、ｙ８が生成されて、第１バッファメモリ１８に入力される。
次に、第２バッファメモリ２０から図形データ群ｙ０、ｙ１が取り出されて、第３ワークメモリ１６に記憶され、出力処理が施され、最後に最終データメモリ１２に順番に記憶される。また、この出力処理と並列して第２ワークメモリ１４に第１バッファメモリ１８からｙ２〜ｙ８の内のｙ２、ｙ３の２つの図形データ群が取り込まれ、第２走査線Ｂによる走査で縮小処理が施され、新たな図形データ群ｙ２とｙ３が生成される。
以上、この動作を、最終の図形データ群ｙ８が最終データメモリ１２に記憶されるまで繰り返し、終了する。
【００２７】
なお、この第２の実施の形態では、ワークメモリ１４については第１の実施の形態と同様に、図形処理された図形データのデータ量が所定量に達したら（一例として２つの図形データ群の処理が終了したら）、後段の他のＦＩＦＯバッファメモリ２０に入力する構成としているが、このワークメモリ１４についてもワークメモリ１１と同様の考え方を適用するようにしても良い。
【００２８】
上述した図形処理方法を実行するプログラムは、図１２に示すように、記憶媒体（フロッピやＣＤ−ＲＯＭ等の外部記憶媒体）５０に格納されており、一例として下記の構成のコンピュータ５２にインストールされてＣＡＤ装置（図形処理装置）として動作する。
このコンピュータ（図形処理装置）５２の概要構成について図１３を用いて説明する。
５４はＣＰＵである。ＣＰＵ５４は、図形処理装置５２全体を制御する。
このＣＰＵ５４に、バス５６を介してＲＯＭ５８、ＲＡＭ６０、ＨＤ（ハードディスク装置）６２、マウスやキーボード等の入力装置６４、外部記憶媒体ドライブ装置６６およびＣＲＴ等の表示装置６８が接続されている。
【００２９】
ＣＰＵ５４の制御プログラムはＲＯＭ５８に格納されている。
図形処理方法を実行するプログラム（図形処理プログラムとも言う）は、記憶媒体５０からＨＤ６２にインストール（記憶）される。また、ＲＡＭ６０には、図形処理方法をＣＰＵ５４が実行する際の作業領域や、図形処理方法を実行するプログラムの一部が記憶される領域が確保されている。そして、各ワークメモリやバッファメモリはＲＡＭ６０の作業領域をさらに細分化した領域を用いて実現している。
また、ＨＤ６２には、入力データや最終データやＯＳ（オペレーティングシステム）等が予め記憶される。
【００３０】
まず、コンピュータ５２の電源を投入すると、ＣＰＵ５４がＲＯＭ５８から制御プログラムを読み出し、さらにＨＤ６２からＯＳを読み込んで、ＯＳを起動させる。これによりコンピュータ５２は図形処理プログラムを記憶媒体５０からインストール可能な状態となる。
次に、記憶媒体５０を外部記憶媒体ドライブ装置６６に装着し、入力装置６４から制御コマンドをＣＰＵ５４に入力し、記憶媒体５０に格納された図形処理プログラムを読み取ってＨＤ６２等に記憶する。つまり図形処理プログラムをコンピュータ５２にインストールする。
その後は、図形処理プログラムを起動させると、コンピュータ５２は図形処理装置として動作し、オペレータは図形処理プログラムがＣＲＴ６８に表示する作業内容と手順に従って入力装置６４を操作することで、上述した図形処理を行えるようになる。
【００３１】
以上、本発明の好適な実施例について種々述べてきたが、本発明は上述の実施例に限定されるのではなく、発明の精神を逸脱しない範囲で多くの改変を施し得るのはもちろんである。
【００３２】
【発明の効果】
本発明に係る図形処理方法やコンピュータが読み取り可能なプログラムを格納した記憶媒体によれば、一の走査線による一の図形処理と他の走査線による他の図形処理とを並列して行えるため、複数の図形処理に要する時間を短縮できる。また、従来のように複数のブロックに分割する必要が無いため、処理する図形データの数が少なくてすみ、処理時間の短縮と共に図形処理のために必要となるメモリ容量が少なくてすむという効果を奏する。
【図面の簡単な説明】
【図１】本発明に係る図形処理方法の基本概念を説明するための説明図である。
【図２】図１の第１ワークメモリ（入力データメモリ）のメモリ領域の構成を説明するための説明図である。
【図３】図１の第２ワークメモリのメモリ領域の構成を説明するための説明図である。
【図４】本発明に係る図形処理方法の第１の実施の形態を説明するための説明図であり、（ａ）は第１ワークメモリ内に記憶された図形データを示し、（ｂ）は（ａ）の図形データのＯＲ処理後の状態を示し、（ｃ）は（ｂ）の図形データの縮小処理後の状態を示す。
【図５】本発明に係る図形処理方法の第１の実施の形における図形データ群のパイプライン処理の様子を説明するための説明図である。
【図６】本発明に係る図形処理方法の第２の実施の形態を説明するための説明図であり、（ａ）は第１ワークメモリ内に記憶された図形データを示し、（ｂ）は（ａ）の図形データのＯＲ処理後の状態を示し、（ｃ）は（ｂ）の図形データの縮小処理後の状態を示す。
【図７】本発明に係る図形処理方法の第２の実施の形における図形データ群のパイプライン処理の様子を説明するための説明図である。
【図８】本発明に係る図形処理方法において、入力データメモリの図形データの量が多い場合に、Ｘ−Ｙ座標平面をＹ軸と平行な直線で複数のセグメントに分割して処理を行う様子を示す説明図である。
【図９】従来の図形処理方法の一例を説明するための説明図である。
【図１０】多角形で構成されるマスクパターンＰを、複数の水平台形（上辺と下辺がＸ軸と平行な台形Ａ、Ｂ）に分割して表現した様子を示す説明図である。
【図１１】多角図形のサイジング処理を説明するための説明図である。
【図１２】図形処理装置の外観、および図形処理方法を実施する図形処理プログラムが格納された記憶媒体の外観を示す説明図である。
【図１３】図１２の図形処理装置の構成を示すブロック図である。
【符号の説明】
１０  入力データメモリ
１１  第１ワークメモリ
１２  最終データメモリ
１４  第２ワークメモリ
１６  第３ワークメモリ
１８  第１バッファメモリ（ＦＩＦＯバッファメモリ）
２０  第２バッファメモリ（ＦＩＦＯバッファメモリ）
【図１】
0003697374.tif 000002
【図２】
0003697374.tif 000003
【図３】
0003697374.tif 000004
【図４】
0003697374.tif 000005
【図５】
0003697374.tif 000006
【図６】
0003697374.tif 000007
【図７】
0003697374.tif 000008
【図８】
0003697374.tif 000009
【図９】
0003697374.tif 000010
【図１０】
0003697374.tif 000011
【図１１】
0003697374.tif 000012
【図１２】
0003697374.tif 000013
【図１３】
0003697374.tif 000014