(57)【要約】【課題】隣接図形間の境界部分で両図形に共に属するピクセルを生じないスキャン変換方法で描画する際に、一定の輪郭線条件時に発生する、輪郭線内部領域の不連続化現象を抑制し、美しい描画結果を提供することを目的とする。【解決手段】隣接図形間の境界部分で両図形に共に属するピクセルを生じないスキャン変換による描画方法において、左右輪郭線の傾きの差分の絶対値の逆数から不連続化する副走査範囲を調べ、当該範囲において生成するスキャン成分の長さを調べ、有効なスキャン成分を発生しなかったスキャンラインに対してスキャン成分を発生させるよう構成したもの。【選択図】　　　　図１
2004030385.tif 000002
【特許請求の範囲】
【請求項１】
幾何座標空間における左右輪郭線をスキャン変換によりピクセル座標上に描画する描画方法であって、さらに輪郭線を共有する隣接図形をスキャン変換した場合に、共有される輪郭線部分において左右の図形にともに属するピクセルを生じない描画方法であって、さらにスキャン変換の結果、左輪郭に対するスキャン成分の左端ピクセルよりも、右輪郭に対するスキャン成分の右端ピクセルが左側にある場合はスキャン成分を発生しない描画方法において、
輪郭線の交点を求める交点演算手段と、
輪郭線の傾きの差分を演算する傾き差分演算手段と、
傾き差分から不連続領域化範囲を求める不連続領域化範囲演算手段と、
左右輪郭線を、隣接図形の境界部分で左右図形にともに含まれるピクセルを生じない方法でスキャン変換するスキャン変換手段と、
スキャン成分長を判定するスキャン成分長判定手段と、
スキャン成分を強制的に発生させるスキャン成分発生手段とを備えたことを特徴とする描画方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は輪郭線情報をラスタ空間にマッピングしつつ描画する、描画方法に関する。
【０００２】
【従来の技術】
輪郭線で囲まれた領域を塗り潰し図形としてラスタ空間に表現する処理には、一般的にはスキャン変換と呼ばれる方法が用いられる。
【０００３】
ラスタ空間は仮想的には直行する水平垂直の格子からなり、格子線で囲まれた正方形領域を、画像を形成する最小単位と考えることができる。本発明では以下この最小単位をピクセルと称する。
【０００４】
スキャン変換とは輪郭線を一定方向（主走査方向）に走査（スキャン）し、走査線と輪郭線の交点座標から、輪郭線の内部となる部分を特定する処理を、走査方向と直行方向（副走査方向）に、一定間隔で繰り返す処理と位置付けることができる。
【０００５】
図２は格子線とピクセルの位置関係の一例を説明する図である。図２において２０１から２０４は水平方向の格子線である。この方向を本発明における主走査方向とし、便宜的にｘ方向とする。また、格子線２０２のｙ座標値を２００とする。
【０００６】
２１１から２１４は垂直方向の格子線である。この方向を本発明における副走査方向とし、便宜的にｙ方向とする。また、格子線２１２のｘ座標値を１００とする。
【０００７】
２２１は格子線２０２と格子線２１２の交点で、幾何的に表現すればこの点の座標は（ｘ，ｙ）＝（１００，２００）となる。本発明において、幾何的に表現する座標位置は前記の書式を取るものとする。
【０００８】
２３１は格子線２０２、２０３、２１２、２１３で囲まれるピクセルで、幾何的座標（ｘ，ｙ）＝（１００，２００）のポイントに対応するものとする。本発明において、ラスタ空間内のピクセルの位置は［Ｘ，Ｙ］＝［１００，２００］の書式にて表現するものとする。
【０００９】
つまり、本発明においては図２における幾何的座標位置（ｘ，ｙ）＝（１００，２００）とラスタ的座標位置［Ｘ，Ｙ］＝［１００，２００］が対応しているものとする。ただし前述のような対応関係を前提にしなければ本発明が効果を発揮しないということではない。
【００１０】
続いて輪郭線をスキャン変換する処理の一例について、図３を参照して説明する。図３において３０１から３０４は主走査方向格子線で、対応するｙ座標値は２００から２０３である。
【００１１】
３１１から３１８は副走査方向格子線で、対応するｘ座標値は２９９から３０６である。
【００１２】
３２１は左輪郭線である。３３１から３３３は左輪郭線３２１と主走査方向格子線との交点にマークしたものである。このマークを始点として描かれている短い矢印は、交点に対して着色される左端ピクセルの対応の一例を模式的に表現したものである。この対応関係については後述する。
【００１３】
３２２は右輪郭線である。３３４から３３６は右輪郭線３２２と主走査方向格子線との交点にマークしたものである。このマークを支点として描かれている短い矢印は、交点に対して着色される右端ピクセルの対応の一例を模式的に表現したものである。この対応関係については後述する。
【００１４】
図３においてグレーに着色された各ピクセルは、左輪郭線３２１と右輪郭線３２２を、本発明におけるスキャン変換規則に従ってスキャン変換した結果、前記２輪郭線の内部とされるピクセルである。これらピクセルの主走査方向の一並びを、本発明では便宜的にスキャン成分と称する。たとえば［Ｘ，Ｙ］＝［２００，３００］のピクセルから［Ｘ，Ｙ］＝［２００，３０３］のピクセルを、本発明では「Ｙ＝２００」におけるスキャン成分と称する。
【００１５】
続いて任意のＹ座標におけるスキャン成分の左右端の決定方法について説明する。はじめに左端の決定方法を説明する。本発明において、任意のＹ座標における左端のピクセルは、左輪郭線とｙ＝ｙ＋１の格子線との交点のｘ座標の小数部分を切り捨てたｘ値に該当するＸ座標をもつピクセルとする。これを図３に当てはめて、Ｙ＝２００のスキャン成分の左端ピクセル座標を求めてみる。左輪郭線３２１とｙ＝２００＋１の格子線の交点が図３において３３１で指示した点となる。このｘ座標値は３００と３０１の間の値となる。この小数部を切り捨てるとｘ＝３００となるので、Ｘ＝３００のピクセルがＹ＝２００のスキャン成分の左端ピクセル座標となる。この対応を図示したのが、左輪郭線３２１とｙ方向格子線３０２，３０３，３０４の交点３３１，３３２，３３３を始点とする短い矢印である。
【００１６】
続いて右端の決定方法を説明する。本発明において、任意のＹ座標における右端のピクセルは、右輪郭線とｙ＝ｙ＋１の格子線との交点のｘ座標の小数部分を切り捨てたｘ値から１を減じ、そのｘ値に該当するＸ座標をもつピクセルとする。これを図３に当てはめて、Ｙ＝２００のスキャン成分の右端ピクセル座標を求めてみる。右輪郭線３２２とｙ＝２００＋１の格子線の交点が図３において３３４で指示した点となる。このｘ座標値は３０４と３０５の間の値となる。この小数部を切り捨てて１を減じるとｘ＝３０３となるので、Ｘ＝３０３のピクセルがＹ＝２００のスキャン成分の右端ピクセル座標となる。この対応を図示したのが、右輪郭線３２２とｙ方向格子線３０２，３０３，３０４の交点３３４，３３５，３３６を始点とする短い矢印である。
【００１７】
以上説明した、スキャン成分の左右端部ピクセル座標を任意のｙ座標において求める処理を実施した結果、左端Ｘ座標が右端Ｘ座標よりも大きくなった場合、そのＹ座標におけるスキャン成分は無しとなる。
【００１８】
ここで任意のスキャンラインにおける左右端ピクセルのＸ座標を求める処理を比較してみると、右輪郭のみ輪郭線と水平方向格子線の交点座標の小数部を切り捨てた後に１を減じる処理が追加されているが、これは幾何的座標空間において輪郭線を共有しつつ隣接する図形をスキャン変換した際に、左右の図形に同時に含まれるピクセルを生じさせないための処理である。このようにしないと幾何的座標空間において隣接する図形がピクセル座標空間において重なるという不自然さが生じるので、スキャン変換処理において左右端の決定方法を上記のようにすることが行われている。
【００１９】
図４はこの処理の合理性を説明する図である。図４において４０１、４０２、４０３は輪郭線で、４０１と４０２をそれぞれ左右輪郭線とする図形と、４０２と４０３をそれぞれ左右輪郭線とする図形が、輪郭線４０２を共有しつつ隣接している。また、輪郭線４０１と４０２によって構成される図形を、前記の方法でスキャン変換した結果が濃いグレーの矩形で描かれ、輪郭線４０２と４０３によって構成される図形を、前記の方法でスキャン変換した結果が、やや薄いグレーの矩形で描かれている。輪郭線４０２に注目してみると、各スキャンラインにおいて、左側図形の右輪郭として変換される、濃いグレーのピクセルと、右側図形の左輪郭として変換される、やや薄いグレーのピクセルは、各スキャンラインにおいて互いに隣接しており、境界部分において左右の図形に共に含まれるピクセルが生じていないことがわかる。
【００２０】
以上説明したように、右側の輪郭線に対する右端のピクセルの決定方法を、左側の輪郭線に対する左端ピクセルの決定方法よりも１少なくすることで、幾何的座標空間において共有される輪郭線に対するピクセルが隣接する図形に共に含まれる不自然さを回避することが可能となる。
【００２１】
以上説明した例では、右端ピクセル位置を求める際に１を減じているが、左端で行っても同様の効果を発揮することは言うまでもない。
【００２２】
【発明が解決しようとする課題】
しかしながら、前記手法によって輪郭線をスキャン変換すると、左右輪郭線の傾きが近い値を取る場合、本来連続領域であるべき図形が不連続領域となる場合があった。
【００２３】
図５は本来連続領域であるべき図形が不連続領域となるケースである。図５において５０１、５０２はそれぞれ左右輪郭線である。図５から明らかなように、左右輪郭線５０１と５０２に挟まれる領域は本来連続領域であるべきなのにもかかわらず、前記のスキャン変換方法に沿って処理すると、図５の５１１から５１８で指示するＹ座標のスキャンラインにおいて有効なスキャン成分が生成されず、不連続領域化が発生する。
【００２４】
本発明は以上のような不連続領域化を解決するためになされたものである。
【００２５】
【課題を解決するための手段】
本発明の描画方法は、幾何座標空間における左右輪郭線をスキャン変換によりピクセル座標上に描画する描画方法であって、さらに輪郭線を共有する隣接図形をスキャン変換した場合に、共有される輪郭線部分において左右の図形にともに属するピクセルを生じない描画方法であって、さらにスキャン変換の結果、左輪郭に対するスキャン成分の左端ピクセルよりも、右輪郭に対するスキャン成分の右端ピクセルが左側にある場合はスキャン成分を発生しない描画方法において、
輪郭線の交点を求める交点演算手段と、
輪郭線の傾きの差分を演算する傾き差分演算手段と、
傾き差分から不連続領域化範囲を求める不連続領域化範囲演算手段と、
左右輪郭線を、隣接図形の境界部分で左右図形にともに含まれるピクセルを生じない方法でスキャン変換するスキャン変換手段と、
スキャン成分長を判定するスキャン成分長判定手段と、
スキャン成分を強制的に発生させるスキャン成分発生手段とを備え、
スキャン変換すべき左右輪郭線が決定すると、これらに対して交点演算手段が左右輪郭線の交点座標を演算する。
【００２６】
続いて傾き差分演算手段が左右輪郭線の傾きの差分を演算する。
【００２７】
続いて不連続領域化範囲演算手段が、前記傾き差分演算手段が算出した傾き差分の絶対値を求め、さらにその逆数を求めることで、左右輪郭線をスキャン変換した場合に不連続領域化が発生し得る範囲を求める。
【００２８】
続いてスキャン変換手段が左右輪郭線をスキャン変換する。
【００２９】
続いてスキャン成分長判定手段がスキャン成分長が１以上か、すなわち有効なスキャン成分が発生したかどうかを判定する。
【００３０】
続いてスキャン成分発生手段が、前記スキャン成分長判定手段が、有効なスキャン成分が発生しなかったと判定した場合に、スキャン成分を発生させるよう構成したものである。
【００３１】
【発明の実施の形態】
（第１実施例）
以下に本発明の実施例を説明する。本実施例では、図５に示したような、＋ｙ方向に尖った輪郭線のスキャン変換処理中に、従来の方法では不連続領域化が発生するのを抑制し、更にスキャン変換しようとする輪郭線の交点座標までピクセルを描画する方法に関して説明する。
【００３２】
図１は本実施例で説明する描画方法の処理手順を説明するフローチャートである。図１のフローチャートには、スキャン変換しようとする、＋ｙ方向に尖った左右の輪郭線が確定した後の処理手順についてのみ記述してある。幾何学的座標空間上で、スキャン変換しようとする、＋ｙ方向に尖った左右の輪郭線が確定すると、左輪郭の傾きと右輪郭の傾きの差分値の絶対値の逆数を求める（Ｓ１０１）。便宜上この量をｙｒとする。
【００３３】
ｙｒが１より小さければ（Ｓ１０２）、本発明で改善しようとする不連続領域化現象が発生しないと判断し（Ｓ１０３）、処理を終了する。
【００３４】
一方ステップＳ１０２においてｙｒが１以上であったら、不連続領域化が起こり得る、ラスタ座標空間におけるＹ座標範囲であるＹＦＲＯＭとＹＴＯを次のように求める。
ＹＦＲＯＭ＝ｉｎｔ（ｙｘ−ｙｒ）
ＹＴＯ＝ｉｎｔ（ｙｘ）
【００３５】
ただし上記の式においてｙｘは左右輪郭線の交点のｙ座標とする。またｉｎｔ（）は（）内の数値の小数部分を切り捨てて整数化する処理関数とする（Ｓ１０４）。
【００３６】
続いて不連続領域化が起こり得るラスタ座標空間におけるＹ座標範囲をカウントするカウンタをＹＦＲＯＭに初期化する（Ｓ１０５）。
【００３７】
続いてカウンタの指示するＹ座標について、所定の方法でスキャン変換処理を行ってスキャン成分を生成し（Ｓ１０６）、当該スキャンラインにおけるスキャン成分の長さを調べる（Ｓ１０７）。
【００３８】
スキャン成分の長さが０であったら（Ｓ１０７）、スキャン変換の結果有効なスキャン成分を生成しなかったことになるので、たとえば長さ１のスキャン成分を当該Ｙ座標のスキャン成分として発生させる（Ｓ１０８）。
【００３９】
続いてカウンタをインクリメントし（Ｓ１０９）、不連続領域化現象が発生し得るＹ座標の最大値であるＹＴＯまで処理したかどうかを評価し（Ｓ１１０）、ＹＴＯまで処理していなかったらステップＳ１０６を実行する。
【００４０】
一方ステップＳ１０７においてスキャン成分の長さが１以上であったら、ステップＳ１０９に行く。
【００４１】
本実施例では、有効なスキャン成分を生成しなかったスキャンラインに対して、長さ１のスキャン成分を発生させる処理について説明したが、例えば大小関係が逆転した左右端のＸ座標を入れ替えて右端Ｘ座標から左端Ｘ座標まで（ただし右端Ｘ座標＜左端Ｘ座標）の、長さ２のスキャン成分を発生させてもよい。
【００４２】
（第２実施例）
本発明の第２実施例として、図５における不連続領域化現象が発生したスキャンライン成分のうち、従来の描画方法でスキャン成分が発生した、最もＹ座標が大きなピクセルよりも小さなＹ座標であるスキャンラインのみに、不連続領域化を回避するスキャン成分を発生させる描画方法について説明する。すなわち図５における５１１から５１８のスキャンラインのみに、不連続領域化を回避するスキャン成分を発生させる描画方法について説明する。
【００４３】
図７は本実施例で説明する描画方法の処理手順を説明するフローチャートである。図７のフローチャートには、スキャン変換しようとする、＋ｙ方向に尖った左右の輪郭線が確定した後の処理手順についてのみ記述してある。幾何学的座標空間上で、スキャン変換しようとする、＋ｙ方向に尖った左右の輪郭線が確定すると、左輪郭の傾きと右輪郭の傾きの差分値の絶対値の逆数を求める（Ｓ７０１）。便宜上この量をｙｒとする。
【００４４】
ｙｒが１より小さければ（Ｓ７０２）、本発明で改善しようとする不連続領域化現象が発生しないと判断し（Ｓ７０３）、処理を終了する。
【００４５】
一方ステップＳ７０２においてｙｒが１以上であったら、不連続領域化が起こり得る、ラスタ座標空間におけるＹ座標範囲であるＹＦＲＯＭとＹＴＯを次のように求める。
ＹＦＲＯＭ＝ｉｎｔ（ｙｘ−ｙｒ）
ＹＴＯ＝ｉｎｔ（ｙｘ）
【００４６】
ただし上記の式においてｙｘは左右輪郭線の交点のｙ座標とする。またｉｎｔ（）は（）内の数値の小数部分を切り捨てて整数化する処理関数とする（Ｓ７０４）。
【００４７】
続いて不連続領域化が起こり得るラスタ座標空間におけるＹ座標範囲をカウントするカウンタをＹＦＲＯＭに初期化する（Ｓ７０５）。
【００４８】
続いてカウンタの指示するＹ座標について、所定の方法でスキャン変換処理を行ってスキャン成分を生成し（Ｓ７０６）、当該スキャンラインにおけるスキャン成分の長さを調べる（Ｓ７０７）。
【００４９】
スキャン成分の長さが１以上であったら（Ｓ７０７）、当該Ｙ座標値をＹＴＭＰに記憶する（Ｓ７０８）。このようにすることで、ＹＴＭＰには従来の描画方法によって有効なスキャン成分を発生したＹ座標のうちの最大値が記憶される。
【００５０】
続いてカウンタをインクリメントし（Ｓ７０９）、不連続領域化現象が発生し得るＹ座標の最大値であるＹＴＯまで処理したかどうかを評価し（Ｓ７１０）、ＹＴＯまで処理していなかったらステップＳ７０６を実行する。
【００５１】
一方ステップＳ７０７においてスキャン成分の長さが０であったらステップＳ７０９を実行する。
【００５２】
ステップＳ７１０においてＹＴＯまで処理したと判断したら、再びカウンタＹをＹＦＲＯＭで初期化する（Ｓ７１１）。
【００５３】
続いてカウンタの指示するＹ座標について、所定の方法でスキャン変換処理を行ってスキャン成分を生成し（Ｓ７１２）、当該スキャンラインにおけるスキャン成分の長さを調べる（Ｓ７１３）。
【００５４】
スキャン成分の長さが０であったら（Ｓ７１３）、スキャン変換の結果有効なスキャン成分を生成しなかったことになるので、たとえば長さ１のスキャン成分を当該Ｙ座標のスキャン成分として発生させる（Ｓ７１４）。
【００５５】
続いてカウンタをインクリメントし（Ｓ７１５）、ＹがＹＴＭＰまで処理したかどうかを評価し（Ｓ７１６）、ＹＴＭＰまで処理していなかったらステップＳ７１２を実行する。
【００５６】
一方ステップＳ７１３においてスキャン成分の長さが１以上であったら、ステップＳ７１５に行く。
【００５７】
本実施例では、有効なスキャン成分を生成しなかったスキャンラインに対して、長さ１のスキャン成分を発生させる処理について説明したが、例えば大小関係が逆転した左右端のＸ座標を入れ替えて右端Ｘ座標から左端Ｘ座標まで（ただし右端Ｘ座標＜左端Ｘ座標）の、長さ２のスキャン成分を発生させてもよい。
【００５８】
【発明の効果】
第１実施例にて説明した処理を、図５に記した不連続領域化現象が発生する例に対して適用した結果を図６に示す。図６において、図５にも描かれている左右輪郭線および、従来の描画方法において不連続領域化現象が発生していたスキャンラインを指示する符合については、図５と共通の符合を記述してある。また、図６において濃いグレーで描画されているのは従来の描画方法にて生成されるスキャン成分のピクセルであり、それよりもやや薄いグレーで描画されているのは、本発明の第１実施例にて説明した描画方法により描画されるスキャン成分（６１１から６１８）である。
【００５９】
図６を参照すると、従来の描画方法においては５１１から５１８のスキャンラインにおいて不連続領域化現象が発生していたが、本発明を適用した場合、これらのスキャンラインに長さ１のスキャン成分を強制的に発生させるので、不連続領域化現象が発生しなくなる。また、６０１から６０４のスキャンラインにも長さ１のスキャン成分（６１９から６２２）が発生させられるので、本来の輪郭線交点に近い位置のピクセルまでが輪郭線内部として描画されるようになる。
【００６０】
第２実施例にて説明した処理を、図５に記した不連続領域化現象が発生する例に対して適用すると、図５において符合５１１から５１８で指示した、不連続領域化現象が発生したスキャンラインに、長さ１のスキャン成分（６１１から６１８）を発生させるので不連続領域化現象が発生しなくなる。さらに第１実施例にて説明した描画方法に対しては、通常の描画方法にてスキャン成分が生成される最大のＹ座標よりも大きなＹ座標にスキャン成分を生成しなくなる、すなわち図６において符合６１９から６２２のスキャン成分を発生しないので、従来の描画方法における不連続領域化現象だけを補完する描画処理を実現できるようになる。
【図面の簡単な説明】
【図１】本発明の不連続領域化を防止する描画方法の処理手順を示すフローチャート
【図２】本発明における格子線とピクセルの位置関係を説明する図
【図３】左右輪郭線をスキャン変換する処理を説明する図
【図４】隣接する図形のスキャン変換を説明する図
【図５】不連続領域化現象の発生例を説明する図
【図６】本発明を適用して不連続領域化が回避された例を説明する図
【図７】本発明の不連続領域化を防止する、別の描画方法の処理手順を示すフローチャート
【符号の説明】
６１１から６１８　本発明の第１、第２実施例に記述した描画方法により、不連続領域化を防止するために生成されたスキャン成分
６１９から６２２　本発明の第１実施例に記述した描画方法により、不連続領域化を防止するために生成されたスキャン成分
【図１】
2004030385.tif 000003
【図２】
2004030385.tif 000004
【図３】
2004030385.tif 000005
【図４】
2004030385.tif 000006
【図５】
2004030385.tif 000007
【図６】
2004030385.tif 000008
【図７】
2004030385.tif 000009