JPS60243772A - 表示装置における閉曲線内塗りつぶし方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〈産業上の利用分野〉 本発明は、画像の輪郭線を表わす閉曲線データが表示メ
モリに書込まれたラスクスキャン型表示装置において、
前記閉曲線領域内の塗りつぶしを簡単なハードウェア構
成で効率良く行うことが出来る塗りつぶし方式に関する
。

〈従来技術〉 ラスクスキャン型表示装置において、例えば、第１図で
示すような、境界をＯで表わされた閉曲線の領域内にＳ
で表わされる塗りつぶし要求が与えられた場合、これを
開始点として前記閉曲線領域内の点を第２図の・で示す
ように塗りつぶされる。

この塗りつぶし方式として、例えば、１９８２年度にＡ
ｄｄｉｓｏｎ−Ｗｅｓｌｅｙ　ｐｕｂ。

Ｇｏ、より出版された、Ｊ、Ｄ、Ｆｏ　Ｉ　ｅｙ。

Ａ、Ｄ、Ｄａｍ共箸”Ｆｕｎｄａｍｅｎｔａ　ｌ　ｓｏ
ｆ　Ｉｎｔｅｒａｃｔｉｖｅ　Ｃｏｍｐｕｔ　−ｅｒ　
Ｇｒａｐｈｉｃｓ”Ｐ、４４８〜４５１に記載されてい
るような方式が知られている。

この文献に示されている第１の方式は、閉曲線によって
囲まれた領域内の任意の点に塗りつぶし要求が与えられ
た場合、要求された画素を中心にこれに４方（左、右、
上、下隣り）、或は８方（左、右、上、下、斜め隣り）
より隣接する画素を一定のルールに従ってチェックし、
塗りつぶすべき画素を順次特定していくものである。

第３図は、このような方式によって塗りつぶしが行われ
て行く状態を示す説明図である。０で表わされる閉曲線
の領域内にＳで表わされる塗りつぶし要求が与えられた
場合、８点を開始点として、回帰的定義に従った処理が
繰り返し行われ、塗りつぶすべき画素が順次特定されて
行く。本具体例の場合、開始点Ｓより下側に１，２と移
動し、下側の境界点に当って左方に折れ、上側に３．４
・・・７と折り返し、上側の境界点に当って左方に折れ
、更に、下側に８．９．Ａ、Ｂ・・・というように、一
定の順序で塗りつぶしが行われる。

この文献に示された第２の方式は、前記閉曲線で囲まれ
た領域内に塗りつぶし要求が与えられた場合、これに隣
接する水平方向の画素を順次塗りつぶして行く方法であ
る。この場合、塗りつぶしが終了したあと、次に塗りつ
ぶしを行う部分を探し出すべく、塗りつぶしが行なわれ
た水平線に隣接する上側及び下側の水平線が走査される
。これによって得られたデータはスタックに蓄積され、
これらデータの中から次に塗りつぶすべき部分が選択さ
れて、これを塗りつぶすようようにしている。

第４図乃至第６図は、このような方式によって塗りつぶ
しが行われて行（状態を示す説明図である。、第５４図
において、Ｓで表された塗りつぶし要求が与えられた場
合、これに隣接する水平方向の画素が、・で示すように
、順次塗りつぶされて行く。この後、塗りつぶされた水
平線に隣接する上側及び下側の水平線が走査され、これ
らに関するデータがスタックに蓄積される。第４図中、
１゜２はこれらデータのスタックＷＩ丹を代表的に表し
たものである。本具体例の場合、画素グループ２が次に
塗りつぶされるべき水平部分として選択され、Ｆｉ５図
に示すようにこの部分が塗りつぶされる。

この後、第４図における場合と同様、塗りつぶしが完了
した水平線に隣接するＬ側及び下側の水平線が走査され
、次に塗りつぶしを行う部分が特定され、第６図に示す
ように、第５図における画素グループ２が塗りつぶされ
る。

しかしながら、これら従来方式において、第１の方式の
場合、夫々の手続は簡単であるが、画素一つ一つについ
て、回帰的定義に従った処理を繰り返し実行する必要が
あり、時間が掛る欠点があった。更に、メモリスペース
が限られているような場合、スタックがオーバフローし
てしまう欠点があった。

また、第２の方式では、前記閉曲線の領域内の全ての画
素を２度走査する必要があり、時間が掛る欠点がある他
、次に塗りつぶしを行う部分を探し出す為、塗りつぶし
が完了した水平線に隣接する水平線の走査を行わなけれ
ばならず、この走査によるデータのｍは前記閉曲線によ
って作られる図形の形態によって著しく変化するので、
複雑な形態の図形にも正しく対処出来るようにする為に
は充分大きなメモリを用意する必要があった。

く目的〉 本発明の目的は、画像の輪郭線を表ゎ′！Ｊ１１１曲線
データが予め表示メモリに書込まれたラスクスキャン型
表示装置において、前記閉曲線の領域内の塗りつ４−シ
を簡単なハードウェア構成で効率良く行える塗りつぶし
方式を実現ｊることにある。

〈発明の構成〉 本発明の構成は、画像の輪郭線を表わす閉曲線データが
書込まれたラスクスキャン型表示装置において、前記閉
曲線領域内の任意の点に塗りつぶし要求が与えられたと
き、この点を水平方向に移動させて前記閉曲線と交わる
点をめ、これを開始点としてこの点に隣接する画素を時
計回り、或は反時計回りに走査して前記閉曲線との交点
をめ、これを新たな境界点として先の場合と同様な走査
を行い更に新たな境界点を検出する動作を、前記閉曲線
上を辿って前記開始点まで繰り返し行うと共に、前記境
界点の検出毎に、この境界点の垂直方向の変化傾向が特
定の方向にある場合、この境界点から水平に前記閉曲線
と交わる点まで塗りつぶし、前記閉曲線で囲まれる領域
を塗りつぶすようにしたことことにある。

〈実施例〉 先ず、本発明による塗りつぶし方式の原理について第７
図及び第８図に従い説明を行う。水平、垂直方向の座標
位置をＸｎ、Ｙｎで表わす。第７図で示すような、閉曲
１１ＬＩによって囲まれた領域内の任意の点（Ｘ、ｂ、
Ｙａ）に塗りつぶし要求が与えられた場合、この点を通
る水平線と閉曲線Ｌ１との交点（ｘａ、Ｙａ）を先ず見
付け、この点を開始点とする。この点から、閉曲線Ｌ１
を例えば時１回り方向Ａｒ１に移動しながら、水平線を
Ｘで順次塗りつぶして行く。−周して開始点（Ｘａ、Ｙ
Ｆ３）に戻ったところで閉曲線Ｌ１の領域内の塗りつぶ
しは完了する。

閉曲線Ｌ１上をを時計回り方向Ａｒ１に進んで行く過程
を第８図に従し）説明づる。第８図は第７図に示す閉曲
線Ｌ１の部分を拡大して示したもので、黒点で表わされ
た開始点（Ｘａ、Ｙａ）を中心にこれに８方より隣接す
る画素が示されている。

これらのうち、斜線の点は、閉曲線Ｌ１を構成する画素
で、この閉曲線は予め表示メモリに書込まれている。

開始点（Ｘａ、Ｙａ）が決ると、この点を中心に反時計
回り方向Ａｒ２に隣接する８つの画素のアドレスをチェ
ックする。閉曲線Ｌ１と最初に交わる点、即ち、（Ｘａ
−１’、Ｙａ＋１）の点が新たな境界点として特定され
る。次にこれを新たな開始点として先の場合と同様な走
査を行い史に新たな境界点を検出して行く。このような
動作を繰り返し行うことによって、開始点（＞（ａ、Ｙ
ａ）まで閉曲線し１上を辿って行くことが出来る。

更に、前記境界点が検出される毎にその前の境界点から
水平に閉曲線１−１と交わる点まで塗りつぶしが行われ
る。尚、この場合、同じ水平線が２度塗りつぶしが行わ
れないようにする為、前記境界点の垂直方向の変化傾向
が特定の方向にある場合、例えば、新たな境界点のＹｎ
の値が前回の境界点のものと比べ増加しているときだ１
ノ水平線の塗りつぶしを行う。

ところで、閉曲線Ｌ１の形状は第７図に示寸ような簡単
な形状ばかりとは限らない。複雑な閉曲線の場合も有り
得る。以下、このような場合の本発明の実施例について
説明を行う。第９図は複雑な閉曲線Ｌ２の部分を拡大し
て示したもので、黒並びに斜線の点はこの閉曲線を構成
づる画素を表わす。尚、以下の説明では、閉曲線Ｌ２上
の開始点を見付番プる行程、即ち、閉曲線Ｌ２内の任意
の点に塗りつぶし要求が出され、この点を通る水平線と
閉曲線Ｌ２との交点をめ、開始点とする行程についての
説明は省略されている。今、黒点の位置から矢印Ａｒ３
方向に閉曲線Ｌ２上を進んで行くものとする。

第１０図は本発明の塗りつぶし方式を実行する為の制御
回路を、第１１図はその動作を説明する為のフローヂャ
ートを示す。これらに従い、第９図における塗りつぶし
の状態を説明する。

第１０図において、ＡＬＬＩは演算装置、ＡＢ及びＤＢ
はデータバス、０１３は出力バスである。ＸはＸ値がＲ
ＥＡＤ、ＷＲＩＴＥされるレジスタ、ＹはＹ値がＲＥＡ
Ｄ、ＷＲＩＴＥされるレジスタ、Ｐｒｘ　Ｉは閉曲線Ｌ
２上において、現在位置より一つ前の境界（閉曲線Ｌ２
＞の左端のＸ４７１ｉがＲＥＡＤ、ＷＲＩＴＥされるレ
ジスタ、ｐｒｘ　ｒは現在位置より一つ前の境界の右端
のＸ値がＲＥＡＤ。

ＷＲＩＴＥされるレジスタ、ＣＸ　ｌは現在位置の境界
の左端のＸ値がＲＥＡＤ、ＷＲＩ　Ｔｌ：されるレジス
タ、Ｃｘｒ４．ｔｍ在位置の境界の右端のＸ値がＲｊＥ
ＡＤ、ＷＲＩ　ＴＥされるレジスタ、Ｐｒｙは現在位置
より一つ前の境界のｙ値がＲＥＡＤ。

ＷＲＩＴＥされるレジスタ、Ｃｙは現在位置の境界のｙ
値がＲＥＡＤ、ＷＲＩＴＥされるレジスタ、ＣＮＴＲは
カウンタである。ＭＥＭは閉曲１１Ｌ２に関するグラフ
ィック情報が記憶されたメモリ、ＣＬＯＧは第１１図に
お（ブる各種の論理演算を実行する為のコントロール・
ロジックである。

今、黒点の位置において、左端のｘｉ　（Ｃｘ　ｌ　）
をα、右端のＸ値（ＣＸｒ）をβ、ｙｌ（Ｇｙ）をγと
する。尚、第９図より明らかな通り、現在位置よ−リ一
つ前の境界の左端のＸ値（ｐｒｘ　ｌ　）並びに右端の
Ｘ値（ｐｒｘｒ）はβであり、一つ前の境界のｙｉｌｉ
（Ｐｒｙ）はγ−１である。

二つの黒点の回りを反時計回りに隣接する画素のアドレ
スをチェックし、閉曲ＩＩＬ２との交点を検出し、塗り
つぶしを行う行程について第１１図のフローチャートに
従い説明を行う。ステップ（１）において、ｐｒｘｒ＋
１　＜＝β＋１）がめられ、レジスタＸに書込まれる。

ステップ（２）において、Ｃｙ−，１＜＝ｒ−１＞がめ
られ、レジスタＹに書込まれる。これらステップによっ
て、走査される画素の開始点が決まる。

ステップ（３）において、Ｃｘｒ−ｐｒｘｒ（−〇）が
められ、カウンタＣＮＴＲに記憶される。ステップ（４
）において、カウンタＣＮ　１’　Ｒの値がＯＪＸ−１
ｍか判断される。この例では、０であるから、ステップ
（５）に進んで、ここで、×（−β＋１＞、Ｙ（＝γ−
１）が境界にあるか判断される。Ｘ、Ｙは境界にないか
ら、ステップ（６）に移り、カウンタＣＮ　Ｔ　Ｒの値
から１を引いたものが新たなカウンタ値として記憶され
、ステップ（７）でＸ＋１が新たな値としてレジスタＸ
に書込まれる。

この後、ステップ（４）に戻るが、本例の場合、カウン
タＣＮＴＲの値は−１となって、ループを抜は出て、ス
テップ（８）に移る。尚、ステップ（５）において、Ｘ
、Ｙが境界にある場合には、Ｂ以下の塗りつぶし、並び
に初期化のステップに移る。

ステップ（８）でＣｘｒ＋１（＝β＋１）がめられ、こ
れがレジスタＸに書込まれ、ステップ（９）でＣＶ＋１
　（＝γ＋１）がめられ、これがレジスタＹに書込まれ
、また、ステップ（１０）テｃｘ　ｒ−Ｃｘ　Ｉ　＋２
　（＝３）がめられ、これがカウンタＣＮ　Ｔ’　Ｒに
記憶される。これらステップと、これら以降のステップ
（１１）〜（１４）とは、右端の黒点（β、γ）のも斜
め上の画素（β＋１．γ＋１）から左方に走査する過程
に相当する。

尚、黒点（β、γ）の右隣りの画素が飛ばされて前記右
斜め上の画素に移っているが、前記右隣りの画素は、一
つ前の境界点を検出する走査で、予め境界にないことが
確認されている（後出のＢ以下の初期化のステップを参
照）為、スキップされている。

ステップ（１１）において、カウンタＣＮＴＲの値が０
以上か判断される。この例では、３であるから、次のス
テップ（１２）に進んで、ここで、×（−β＋１＞　、
　Ｙ　（−γ＋１）が境界にあるか判断される。このと
きのＸ、Ｙは境界にないから、ステップ（１３）に移り
、カウンタＣＮ　Ｔ　Ｒの値から１を引いたものが新た
なカウンタ値として記憶され、ステップ（１４）でＸ−
１が新たな値としてレジスタＸに書込まれる。

この後、ステップ（１１）に戻るが、本例の場合、この
ループを３回まわって、４回目に１３以下のステップに
移って行く。

Ａ以下のステツ、プは、右端の黒点の右斜め上の画素（
β＋１．γ＋１）からノ１端の黒点の左斜め上ノ画素（
α−１，γ＋１）までの走査で境界が見付Ｇノられない
ときのステップを示ず。

第９図において点線で示した位置に境界があるような場
合、走査は左端の黒点から更に反時計回りに行う必要が
ある。ステップ＜１５）、（１６）は走査の開始点（α
−１，γ−１）を定める為のものである。尚、開始点が
、左端の黒点の左隣りの画素を飛ばし、前記黒点の左斜
め下の画素（α−１，γ−１）からとなっているが、こ
れは、前記左隣りの画素は、一つ前の境界点を検出する
走査の過程で境界にないことがＭｔ　Ａｌされている為
である。

ステップ（１７）で、ｐｒＸｌ−ＱＸ＋が記憶され、ス
テップ（１８）で、カウンタＣＮ　Ｔ　Ｒの値が０以上
か判断される。次のステップ（１９）で、Ｘ、Ｙが境界
にあるか判断され、境界にない場合にはステップ（２０
）に移り、カウンタＣＮＴＲの値から１を引いたものが
新たなカウンタ値として記憶され、ステップ（２１）に
おいて、Ｘ＋１を新たな値として、レジスタＸｋ、書込
まれる。

この後、ステップ（１８）に戻るが、本例のように点線
の画素の位置が境界にある場合には、−回目でこのルー
プを抜は出てＢ以下のステップに移る。尚、ステップ（
１８）でＮＯとなった場合は、閉曲線Ｌ２が不連続であ
ることになる。

Ｂ以下のステップにおいて、ステップ（２２）は塗りつ
ぶしのサブルーチンで、現在の境界（黒点の位置）のｙ
ｌａ（Ｃｙ）、一つ前の境界のｙ値（Ｐｒｙ）、今回の
走査によって検出された境界のｙ（直（Ｙ）が比較され
、 Ｐ　ｒ　ｙ＜　ＣＶ　＜　Ｙのとき、即ち、現在の境界
点の変化傾向が増加傾向にあるときに、右端の黒点の隣
りの位置（Ｃｘ　ｒ＋　１　、　Ｃｙ、）から右へ反対
側の境界まで塗りつぶしが行われる。

ステップ（２３）〜（３２）は次の境界点を検出する走
査に先立ち行う初期化ステップである。

ステップ（２３）、（２４）において、新たな境界の右
端のＸ値がめられる。右端がめられた場合、ステップ（
２５）において、現在の境界の右端のＸ値（ＣＸｒ）を
一つ前の境界の右端のＸ値に関するレジスタｐｒＸｒに
書込み、ステップ（２６）において、Ｘ−１（ステップ
（２３）において、Ｘ＋１→Ｘとされている。）をレジ
スタＱｘｒに書込む。

ステップ（２７＞、（２８＞において、新たな境界の左
端のＸ値がめられる。左端がめられた場合、ステップ（
２９）において、現在の境界の左端のＸ値＜ＣＸ　＋　
＞を−゛〕前の境界の左端のＸ値に関するレジスタＰｒ
ｘ　ｌに書込み、ステップ（３０）において、Ｘ＋１（
ステップ（２７）において、Ｘ−１→×とされている。

）をレジスタＣｘｌに書込む。

ステップ（３１）、（３２）において、ｙ値の更新が行
われる。即ち、ステップ（３１）において、現在の境界
のｙ値（ｃｙ＞が一つ前の境界のｙｌＩｆｉに関するレ
ジスタＰｒｙに書込まれ、ステップ（３２）において、
新たな境界のｙ値が現在の境界のｙ値に８Ｑするレジス
タＣｙに書込まれる。

この後、ステップ（１）に戻って、新たな境界点の検出
の為の走査が行われる。

このような動作を繰り返し行うことによって、黒点で示
′ｇ′開始点まで閉曲線Ｌ２上を辿って行くことによっ
て、この閉曲線で囲まれる部分が塗りつぶされる。尚、
前記本発明の実施例では、境界点の回りを反時計回りに
走査して、新たな境界点を検出するようにしているが、
これに限らず、時５１回りに走査して境界点を検出する
ようにしても良い。

く効果〉 本発明の塗りつぶし方式によれば、境界点の回りを走査
する為の記憶内容は、前記境界点の直前、現在、直後の
座標データであり、従来方式と比較して少なく、メモリ
スケールをその分、縮小することが出来る。更に、本発
明の方式によれば、境界点に隣接する小数の画素を走査
し、新たな境界点を見付け、直線を引（ものである為、
第１の従来方式で示したような、閉曲線内の全画素につ
いて回帰的定義に従った塗りつぶら処理を繰返し行うも
の、或は、第２の従来方式のように、塗りつぶしは水平
線単位で行うものの、次の塗りつぶしの準備の為に隣接
する水平線を一々走査しな【プれはならないものと比較
し、塗りつぶしに必要な時間を大幅に短縮することが出
来る。加えて、本発明の方式では、新たな境界点が検出
される毎に、境界点の垂直方向の変化傾向がチェックさ
れ、例えば、現在の境界点の変化傾向が増加傾向にある
ときにだけ、水平線の塗りつぶしを行うようにして、同
じ水平線が２ｒ！１塗りつぶされないようにした為、時
間が更に節約出来る。

【図面の簡単な説明】

第１図乃至第６図は、従来の塗り−）ぶし方式の路のブ
ロック線図、第１１図は本発明方式の動作を説明する為
の７１コーチヤードで゛ある。 し１．Ｌ２・・・閉曲線、△ｌ−ＬＪ・・・演算装置、
Ｘ。 Ｙ、Ｐｒｘ　ｌ、Ｐｒｘｒ、Ｃｘ　ｌ、Ｃｘｒ、Ｃ’／
。 Ｐｒｙ・・・レジスタ、ＭＥＭ・・・グラフィック情報
を記憶す−るメモリ、ＣＬＯＧ・・・コントロール・ロ
ジック。 帛１図 第３図 ０００００００００００００００００００００００００ ０　０ ０ ｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏ。 ｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏ。 諮５囚 ｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏｏ。 第７図 第８図 隼９図

Claims (1)

1. 【特許請求の範囲】 画像の輪郭線を表わす閉曲線データが書込まれたラスメ
   タスキャン型表示装置において、（ａ）前記閉曲線領域
   内の任意の点に塗りつぶし要求が与えられたとき、この
   点を水平方向に移動させて前記閉曲線と交わる点をめる
   行程と、 （ｂ）これを開始点としてこの点に隣接する画素を時開
   回り、或は反時計回りに走査して前記閉曲線との交点を
   め、これを新たな境界点として先の場合と同様な走査を
   行い更に新たな境界点を検出する動作を、前記閉曲線上
   を辿って前記開始点まで繰り返し行う行程と、 （Ｃ）！記境界点の検出毎に、この境界点の垂直方向の
   変化傾向を検出する行程と、 （ｄ）前記境界点の変化傾向が特定の方向にある場合、
   この境界点から水平に前記閉曲線と交わる点まで塗りつ
   ぶしを行う行程 とよりなる表示装置における閉曲線内塗りつぶし方式。