JPH06150015A - フィルポリゴンの作成方法 - Google Patents

Abstract

(57)【要約】 【目的】 ポリゴンの形状の如何によらず高速な塗りつ
ぶしを可能とする。 【構成】 任意形状ポリゴンの塗描方法であって、
（１）前記ポリゴンを含む塗描処理領域を定めるステッ
プ、（２）前記ポリゴンを構成する各線分と、前記線分
の両端から特定方向に引き出した二直線と、上記塗描処
理領域の外縁と、に挟まれる領域の塗描データをメモリ
内に作成するステップ、（３）前記各線分についての各
塗描データについて、排他的論理和を演算するステッ
プ、とからなることを特徴とする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、コンピュータ図形処理
におけるフィルポリゴン（塗りつぶしたポリゴン）の作
成方法に関し、ポリゴンの形状の如何によらず高速な塗
りつぶし（塗描）が可能なフィルポリゴンの作成方法に
関する。

【０００２】

【技術背景】従来、任意形状のフィルポリゴンを作成す
る場合、水平方向にスキャンして塗描領域を求め、これ
を垂直方向に画素単位で順次ずらして、ポリゴン全体を
塗描する方法が採用されている。この方法では、描かれ
たポリゴンを、所定領域内で水平スキャンを画素単位で
垂直方向にずらして行い、スキャンラインをポリゴンと
交差させ、Ｘ座標が小さい方から数えて奇数番目の交差
点と偶数番目の交差点に存在する画素を、スキャンライ
ンに沿って塗描している。

【０００３】例えば、図７に示すように、任意形状のポ
リゴン（同図では、Ｐｎ１〜Ｐｎ５の頂点を持つ、５つ
の三角形と１つの五角形とから成る星形ポリゴン６）
を、Ｙ座標がＹｎである水平ラインによりスキャンする
と、スキャンラインＬは星形ポリゴン６とＰｎ１，Ｐｎ
２，Ｐｎ３，Ｐｎ４で交差するので、Ｐｎ１からＰｎ
２、およびＰｎ３からＰｎ４までを塗描する。そして、
この水平ラインについてのスキャンを画素単位で垂直方
向にずらして行うことで、星形ポリゴン６を構成する３
角形の内部が塗描される。なお、図７では、上方から下
方にスキャンしつつＹｎの高さまで塗描されている状態
を示している。このような塗描方法は、各種のソフトウ
ェアに利用されており、ハードウェア化（グラフッィク
用のプロセッサに上記塗描機能を組み込むこと）も比較
的容易である。

【０００４】しかし、上記塗描方法は、次に述べるよう
な欠点を有している。 （１）スキャンラインＬとポリゴン６との交点を記憶す
るメモリ領域（テーブル）が必要となる。このため、あ
るＹ座標のスキャンラインＬと、これに交差するポリゴ
ン６を構成する線分（Ｐ１−Ｐ２，Ｐ４−Ｐ５，Ｐ２−
Ｐ３，Ｐ５−Ｐ１）との交点のＸ座標（Ｘｎ１，Ｘｎ
２，Ｘｎ３，Ｘｎ４）を求めてテーブルに登録しなくて
はならないため、テーブルの大きさによっては、扱える
ポリゴンの線の数に制限を設けざるを得ない。 （２）計算回数が多いため、前記ポリゴンを構成する各
線分と、前記線分の両端から特定方向に引き出した二直
線と、上記塗描処理領域の外縁と、に挟まれる領域の塗
描データをメモリ内に作成するスピードが遅い。すなわ
ち、あるＹ座標にポリゴン６を構成する線分が含まれて
いるか否かを判断する計算、交差点のＸ座標の計算、交
差点をＸ座標の小さい順または大きい順にソートする計
算等を、塗描処理領域内においてＹ方向に並んだ画素の
数と同回数行う必要がある。

【０００５】このような方法に対して、任意形状のポリ
ゴンを多数の三角形に分解し、各三角形の内部を塗描す
るといった方法も従来知られているが、この方法はアル
ゴリズムが複雑となる等ため、塗描プログラムにバグが
生じる可能性が多い。

【０００６】

【発明の目的】本発明は、ポリゴンの形状の如何によら
ず高速な塗りつぶし（塗描）が可能なフィルポリゴンの
作成方法を提供することを目的とする。

【０００７】

【発明の概要】上記の目的を達成するために、本発明の
フィルポリゴンの作成方法では、まず、第１のステップ
で、ポリゴンを含む塗描処理領域を定める。この塗描処
理領域の形状は、通常、画素の並び方向（一般には水
平，垂直方向）を辺の方向とする長方形（正方形を含
む）とするが、必ずしもこれに限らない。例えば、円形
であったとしても、フィルポリゴンの作成は可能であ
る。この塗描処理領域の位置や大きさは、ポリゴンの描
画の終了と同時に決定されることもあるし、例えば、予
め作成されたポリゴンの形状データがメモリ内に存在す
るような場合において該ポリゴンを塗描するようなとき
には、ポリゴンの指定により決定される。

【０００８】第２のステップでは、前記ポリゴンを構成
する各線分と、該線分の両端から特定方向に引き出した
二直線と、上記処理領域の外縁とに挟まれる領域の塗描
データをメモリ内に作成する。

【０００９】ここで、特定方向とは、処理のし易さか
ら、通常画素の並び方向（水平または垂直方向）が選ば
れる。塗描処理領域が、水平，垂直方向の辺を持つ長方
形である場合には、ポリゴンを構成する各線分と長方形
の一辺とが構成する領域（塗描領域）は、該線分を斜辺
とし、該線分の両端から水平に引き出された二直線を上
底，下底とする直角台形（一方の底角が直角である台
形）となる。なお、塗描処理領域の外縁が、ポリゴンを
構成する線分と接している場合には、塗描領域は、該線
分を斜辺とし該線分の一端から引き出された直線を底辺
とする直角三角形となる。台形の塗描領域は三角形と四
角形の組合せであることから、この場合には塗描領域
を、三角形と四角形のみで構成することができる。三角
形と四角形については、塗描専用のプロセッサも提供さ
れているので、より高速に塗描処理を行うこともでき
る。

【００１０】第３のステップでは、前記各線分について
の各塗描データについて、排他的論理和を演算する。こ
の演算は、どの線分について先に塗描データを作成する
かは任意であり、例えば、ポリゴンが３つの線分Ａ，
Ｂ，Ｃにより構成される場合、最初にＣについて、次に
Ｂについての塗描データを作成し、これらの排他的論理
和をとってもよいし、最初にＢについて、次にＡについ
ての塗描データを作成し、これらの排他的論理和をとっ
てもよい。

【００１１】ポリゴンは、直線により構成されるが、ス
プライン曲線等も微視的に見ると直線の集合とすること
ができる。したがって、本発明には、広く曲線により構
成された図形を含んでいる。また、ポリゴンは通常の四
角形、五角形等、それを構成する線分同士が交差してい
ない図形であってもよいし、数字の「８」のように線分
同士が交差する図形であってもよい。ポリゴンは、通常
は３以上の線分が必要とされるが、２つの線分により構
成される図形（Ｌ字形）も本発明のポリゴンに含まれ
る。この場合には、開いた線分の先端同士を結ぶ仮想線
を、ポリゴンを構成する線分とみなすことで本発明が適
用される。さらに、３以上の線分から構成されていて
も、完全には閉じていない図形（例えば、コ字形等）に
ついても、本発明は適用できる。このような、閉じてい
ない図形についても、何れの線分とも接続されていない
線分の先端同士を結ぶ仮想線を、ポリゴンを構成する線
分とみなすことで本発明が適用される。

【００１１】本発明では、必要とするメモリ領域は作成
したいポリゴンのサイズに依存するが、扱えるポリゴン
の線分の数に制限はない。したがって、スプライン曲線
が複雑に入り組んだポリゴンの作成も容易にできる。ま
た、本発明では、スキャンラインとポリゴンを構成する
線分との交点を求める等の複雑な計算の必要はないの
で、高速なフィルポリゴンの作成がなされる。

【００１２】

【実施例】図１の流れ図、図３の塗描過程図により図２
に示すポリゴン１を塗描する場合を詳細に説明する。図
６に本発明のフィルポリゴンの作成方法の実施に使用す
るハードウェアの一例を示す。同図では、バス５１には
ＣＰＵ５２、ＲＯＭ５３、ＲＡＭ５４、入力装置５５、
出力装置５６が接続された様子が示されている。ＣＰＵ
５２はＲＯＭ５３や図示しない補助記憶装置等からＲＡ
Ｍ５４に読み込まれたプログラムによって動作する。こ
のプログラムは、マウス，タブレット，キーボード等の
入力装置５５からのデータを受け取ったり、計算を行っ
たりするほか、表示装置，プリンタ等の出力装置５６に
データを転送したり、ＲＡＭ５４や前記補助記憶装置等
に計算結果の書き込みを行ったりする。本実施例では、
以下に述べる処理や判断は、ＣＰＵ５２がＲＯＭ５３ま
たはＲＡＭ５４に書き込まれたプログラムにより行われ
る。また、ポリゴンの各頂点の座標は、予め入力されて
ＲＡＭ５４に記憶されているものとする。なお、以下に
述べるＳ１〜Ｓ６は図１に示すように、本発明における
処理の流れを示している。

【００１３】（１）Ｓ１では、最初に塗描処理領域を定
める。この処理領域の決定は、上記ＲＡＭ５４に記憶さ
れているポリゴンの各頂点座標により決定することがで
きる。図２では、説明の便宜上、塗描処理領域１０はポ
リゴン１のＸ，Ｙ方向最大値よりやや大きく、Ｘ，Ｙ方
向最小値よりもやや小さく設定してあるが、塗描処理領
域１０の大きさを、Ｘ，Ｙ方向最大値，最小値に合わせ
て定めることもできることは勿論である。なお、ここで
は塗描処理領域１０のＸ，Ｙ方向の最大値をそれぞれＸ
ｍａｘ，Ｙｍａｘとし、Ｘ，Ｙ方向の最小値をそれぞれ
Ｘｍｉｎ，Ｙｍｉｎとしてある。

【００１４】（２）Ｓ２では「次に処理するべきベクタ
が存在するか」否かが判断され、該ベクタが存在すれ
ば、処理対象となっているベクタ〔（Ｘα，Ｙα），
（Ｘβ，Ｙβ）〕（α，β＝１，２，・・・、α≠β）
についての処理が行われる。ここで、ベクタ〔（Ｘα，
Ｙα），（Ｘβ，Ｙβ）〕とは、塗描処理対象となる線
分を座標表示したものであり、本実施例では表１で表さ
れる。

【００１５】

【表１】 線 分 ベ ク タ Ｐ１−Ｐ２：〔（Ｘ１，Ｙ１），（Ｘ２，Ｙ２）〕 Ｐ２−Ｐ３：〔（Ｘ２，Ｙ２），（Ｘ３，Ｙ３）〕 ・ ・ ・ ・ ・ ・ Ｐ５−Ｐ１：〔（Ｘ５，Ｙ５），（Ｘ１，Ｙ１）〕

【００１６】ここでは、処理が開始されたばかりである
ので、「次に処理すべきベクタ」が存在している。現在
処理するべきベクタは、当初から分かっているものとす
る。なお、処理の順番には特別な規則があるわけではな
いが、ここでは上記表１に掲げられた順にその後の処理
が進められるものとする。したがって、まず〔（Ｘ１，
Ｙ１），（Ｘ２，Ｙ２）〕が処理対象となる。

【００１７】（３）Ｓ３では、処理対象となるベクタの
各Ｙ座標が等しいか否か判断される。これらの座標が等
しい場合には、後述するように処理が中断され、Ｓ１に
戻り、等しくない場合には次の処理（Ｓ４）に移行す
る。ここでは、Ｙ１≠Ｙ２であるので、処理はＳ４に移
行する。

【００１８】（４）Ｓ４では、処理対象となるベクタ
〔（Ｘα，Ｙα），（Ｘβ，Ｙβ）〕と、その両端座
標（Ｘα，Ｙα），（Ｘβ，Ｙβ）からＸ軸に平行に正
の方向に向けて引いた２本の線と、塗描処理領域１０
のＹ軸に平行な右側の辺、とに挟まれる領域に形成され
る塗描データがメモリ（ＲＡＭ４）に格納される。この
場合には、塗描対象となるベクタは〔（Ｘ１，Ｙ１），
（Ｘ２，Ｙ２）〕であるので、その塗描データは図３
（Ａ）下段で示すようになる（該塗描データ領域を
「１」で、非塗描データ領域を「０」で示す）。そし
て、この塗描処理領域１０についての塗描データと、そ
の際に塗描処理領域についてのすでに作成されている塗
描データ（前回作成の塗描データ）とのＸＯＲが演算さ
れる。ここでは、「すでに作成されているデータ」は、
存在していないことから、塗描処理領域１０全体につい
て「０」（図３（Ａ）の上段参照）である。したがっ
て、この場合演算後の塗描データは、図３（Ｂ）上段に
示すように、同図（Ａ）下段と同一である。

【００１９】なお、上記塗描データを作成は、メモリ上
での台形（図３（Ａ）下段等参照）の塗描処理を意味し
ている。この場合、台形の塗描はどのような方法でもよ
く、水平ラインについてのスキャンを画素単位で垂直方
向にずらして行う方法でもよいし、前述したように台形
を直角三角形と長方形に分解して塗描する方法でもよ
い。

【００２０】（５）次に、塗描されている台形状のデー
タ領域の上底または下底から、画素１列（線１本）を消
去または付加する（Ｓ６）。本実施例では、ＸＹ座標
を、画素を基準に（画素の中心を基準に）に定めている
ため、上記消去を実行しておかないと、ポリゴン１につ
いての塗描の全処理が終了した後、非塗描領域に不要な
水平塗描線が現れたり、塗描領域に不要な水平非塗描線
が現れたりする場合がある。本実施例では、Ｓ５におい
て、Ｙα＞Ｙβの判断を行い、台形の上底から上記画素
１列の消去または付加を行うような場合分けを行ってい
る。この場合分けに応じ、上記関係が成立するときに
は、現在の塗描データと、線分（Ｘα，Ｙα）−（Ｘｍ
ａｘ，Ｙα）が塗描された処理領域とのＸＯＲが演算さ
れ（Ｓ６ａ）、上記関係が成立しないときは、現在の塗
描データと、線分（Ｘβ，Ｙβ）−（Ｘｍａｘ，Ｙβ）
が塗描された処理領域とのＸＯＲが演算される（Ｓ６
ｂ）。この後、処理はＳ２に移行する。今の場合、Ｙ１
＜Ｙ２であるので、Ｓ６ｂに処理が移行し、図３（Ｂ）
上段に示した塗描データと、同図（Ｂ）下段に示す線分
とのＸＯＲが演算され、図３（Ｃ）上段に示す塗描デー
タが作成される。

【００２１】（６）次に、Ｐ２−Ｐ３、すなわちベクタ
〔（Ｘ２，Ｙ２），（Ｘ３，Ｙ３）〕について、上記と
同様の処理が行われる。すなわち、Ｓ２において、図３
（Ｃ）に示すように、〔（Ｘ２，Ｙ２），（Ｘ３，Ｙ
３）〕について塗描データが作成され（下段参照）、こ
れと上段に示した塗描データとのＸＯＲが演算される。
この結果、塗描データは、図３（Ｄ）上段に示すよう
に、上記２つの塗描データ間に「０」の線が形成された
データに書き換えられる。Ｓ５での判断により、処理は
Ｓ６ａに移行し、図３（Ｄ）下段に示す塗描データと、
上記図３（Ｄ）上段に示す塗描データとのＸＯＲが演算
される。この結果、図３（Ｅ）上段に示すように、上記
塗描データ間の「０」の線は消去される。

【００２２】（７）ついで、Ｐ３−Ｐ４すなわち、ベク
タ〔（Ｘ３，Ｙ３），（Ｘ４，Ｙ４）〕についてＳ２，
Ｓ３の処理が行われる。ここでは、Ｙ３＝Ｙ４であるこ
とから、Ｓ３の判断により、ベクタ〔（Ｘ３，Ｙ３），
（Ｘ４，Ｙ４）〕についてのその後の処理はなされず、
Ｐ４−Ｐ５、すなわちベクタ〔（Ｘ４，Ｙ４），（Ｘ
５，Ｙ５）〕についてのＳ２，Ｓ３，Ｓ４の処理が行わ
れる。Ｓ４では、図３（Ｅ）に示すように、下段に示す
ベクタ〔（Ｘ４，Ｙ４），（Ｘ５，Ｙ５）〕についての
塗描データと、上段に示したすでに作成されている塗描
データとのＸＯＲが演算され、図３（Ｆ）上段に示す塗
描データが作成される。

【００２３】この結果、処理はＳ５を経てＳ６に移行
し、図３（Ｆ）下段に示す塗描データ（図３（Ｅ）下段
の台形の上底に相当する線）と、前述の同（Ｆ）上段に
示す塗描データとのＸＯＲが演算され、図３（Ｇ）に示
す塗描データが作成される。 （８）さらに、Ｐ４−Ｐ５、すなわちベクタ〔（Ｘ４，
Ｙ４），（Ｘ５，Ｙ５）〕についてＳ２の処理が行われ
る。Ｓ２では、〔（Ｘ４，Ｙ４），（Ｘ５，Ｙ５）〕
が、「次に処理するべきベクタベクタ」を有していない
ことから、処理は終了する。

【００２４】図４は、上記（１）〜（８）に述べた処理
を、五角形と５つの三角形により構成された星形ポリゴ
ン２（頂点をＰ１〜Ｐ５で示す）に適用して、フィルポ
リゴン２′を作成する場合の説明図である。同図に示す
ように、塗描処理領域２０内に作成された星形ポリゴン
２は、各線分により形成される塗描データ２１〜２５と
の間で順次ＸＯＲが演算され、フィルポリゴン２′が作
成される。

【００２５】図５は、同じく上記（１）〜（８）に述べ
た処理を、白抜きの星形ポリゴン３に適用して、フィル
ポリゴン３′を作成する場合の説明図である。同図で
は、塗描処理領域３０内に作成された星形ポリゴン３
（頂点をＰ１〜Ｐ１０で示す）は、各線分により形成さ
れる塗描データ３１〜４０との間でトーナメント方式で
順次ＸＯＲが演算され、フィルポリゴン３′が作成され
ている。

【００２６】以上のようにして作成されるフィルポリゴ
ンの塗描の面種は、いわゆるベタ塗りに限らず、縞模様
や梨地等のハッチングが含まれることは言うまでもな
い。

【００２７】

【発明の効果】

（１）スキャンラインとポリゴンを構成する線分との交
点を求める等の複雑な計算の必要はなく、線の描画と同
等の計算量のみで、高速にフィルポリゴンの作成をする
ことができる。 （２）扱えるポリゴンの線分の数に制限はない。したが
って、スプライン曲線が複雑に入り組んだポリゴンの作
成が可能となる。 （３）グラフィックプロセッサを用いたり、専用のハー
ドウェア化も容易であり、ＣＡＤ等の図形処理装置に有
効であるばかりでなく、アウトラインフォントの作成を
行うレーザプリンタ等の図形出力装置にも有効である。

【図面の簡単な説明】

【図１】本発明の処理の流れの一例を示す図である。

【図２】本発明の実施例を説明するために例示されたポ
リゴンを示す図である。

【図３】図２のポリゴンを用いた本発明の実施例の説明
図である。

【図４】本発明の他の実施例の説明図である。

【図５】本発明のさらに他の実施例の説明図である。

【図６】本発明において使用するハードウェア構成を示
す図である。

【図７】従来のポリゴンの塗描方法を示す図である。

【手続補正書】

【提出日】平成４年１２月６日

【手続補正１】

【補正対象書類名】図面

【補正対象項目名】図１

【補正方法】変更

【補正内容】

【図１】

Claims (2)

【特許請求の範囲】
1. 【請求項１】 任意形状ポリゴンの塗描方法であって、
   （１）前記ポリゴンを含む塗描処理領域を定めるステッ
   プ、（２）前記ポリゴンを構成する各線分と、前記線分
   の両端から特定方向に引き出した二直線と、上記塗描処
   理領域の外縁と、に挟まれる領域の塗描データをメモリ
   内に作成するステップ、（３）前記各線分についての各
   塗描データについて、排他的論理和を演算するステッ
   プ、とからなることを特徴とするフィルポリゴンの作成
   方法。
2. 【請求項２】 任意形状ポリゴンの塗描方法であって、
   （１）前記ポリゴンを含む長方形の塗描処理領域を定め
   るステップ、（２）前記ポリゴンを構成する各線分と、
   上記線分の両端から前記長方形の特定の一辺と、上記線
   分の両端から前記一辺に引き出した二直線と、に挟まれ
   る台形または三角形領域の塗描データをメモリ内に作成
   するステップ、（３）前記各線分についての各塗描デー
   タについて、排他的論理和を演算するステップ、とから
   なることを特徴とするフィルポリゴンの作成方法。