JPH0366675B2 - - Google Patents
Info
- Publication number
- JPH0366675B2 JPH0366675B2 JP60089088A JP8908885A JPH0366675B2 JP H0366675 B2 JPH0366675 B2 JP H0366675B2 JP 60089088 A JP60089088 A JP 60089088A JP 8908885 A JP8908885 A JP 8908885A JP H0366675 B2 JPH0366675 B2 JP H0366675B2
- Authority
- JP
- Japan
- Prior art keywords
- pixels
- circle
- point
- partial
- ellipse
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06K—GRAPHICAL DATA READING; PRESENTATION OF DATA; RECORD CARRIERS; HANDLING RECORD CARRIERS
- G06K15/00—Arrangements for producing a permanent visual presentation of the output data, e.g. computer output printers
- G06K15/22—Arrangements for producing a permanent visual presentation of the output data, e.g. computer output printers using plotters
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06K—GRAPHICAL DATA READING; PRESENTATION OF DATA; RECORD CARRIERS; HANDLING RECORD CARRIERS
- G06K15/00—Arrangements for producing a permanent visual presentation of the output data, e.g. computer output printers
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T11/00—Two-dimensional [2D] image generation
- G06T11/20—Drawing from basic elements
- G06T11/23—Drawing from basic elements using straight lines or curves
-
- G—PHYSICS
- G09—EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
- G09G—ARRANGEMENTS OR CIRCUITS FOR CONTROL OF INDICATING DEVICES USING STATIC MEANS TO PRESENT VARIABLE INFORMATION
- G09G5/00—Control arrangements or circuits for visual indicators common to cathode-ray tube indicators and other visual indicators
- G09G5/20—Function-generator circuits, e.g. circle generators line or curve smoothing circuits
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06K—GRAPHICAL DATA READING; PRESENTATION OF DATA; RECORD CARRIERS; HANDLING RECORD CARRIERS
- G06K2215/00—Arrangements for producing a permanent visual presentation of the output data
- G06K2215/0002—Handling the output data
- G06K2215/004—Generic data transformation
- G06K2215/0042—Rasterisation
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Image Generation (AREA)
- Digital Computer Display Output (AREA)
- Controls And Circuits For Display Device (AREA)
Description
【発明の詳細な説明】
Ａ 産業上の利用分野
この発明はCRT（陰極線管）、デジタル・プロ
ツタ、マトリクス・プリンタ等デジタル表示装置
上に円、楕円またはこれらの部分図形（たとえば
パイ・チヤート）の輪郭を描き、かつこの内部を
塗りつぶす図形塗りつぶし方法に関する。
ツタ、マトリクス・プリンタ等デジタル表示装置
上に円、楕円またはこれらの部分図形（たとえば
パイ・チヤート）の輪郭を描き、かつこの内部を
塗りつぶす図形塗りつぶし方法に関する。
Ｂ 開示の概要
走査変換塗りつぶし方法に適した円弧または楕
円曲線の発生方法が開示される。変形DDA法が
導き出され、この変形DDA法により、走査線と
曲線との交点が単一の点で表わされる。
円曲線の発生方法が開示される。変形DDA法が
導き出され、この変形DDA法により、走査線と
曲線との交点が単一の点で表わされる。
Ｃ 従来技術
ラスタ型表示装置を例に考える。従来、塗りつ
ぶされた図形をラスタ型表示装置で表示する場合
には、まず対象となる図形の輪郭線を描き、画面
表示用のメモリの内容を読み出しながら、図形の
内部（塗られるべき領域）と外部（塗られない領
域）とを判別し、塗りつぶすという方法がよく行
なわれてきた。このような手法はたとえば特開昭
56−142585号に記載されている。この方法では遂
一メモリの内容を読み出す必要があることから、
処理に時間がかかる。またすでに画面上に書き込
まれている内容に大きく依存するため、他の図形
に邪魔されて、思うように塗りつぶしが行えない
といつたことが起こる。
ぶされた図形をラスタ型表示装置で表示する場合
には、まず対象となる図形の輪郭線を描き、画面
表示用のメモリの内容を読み出しながら、図形の
内部（塗られるべき領域）と外部（塗られない領
域）とを判別し、塗りつぶすという方法がよく行
なわれてきた。このような手法はたとえば特開昭
56−142585号に記載されている。この方法では遂
一メモリの内容を読み出す必要があることから、
処理に時間がかかる。またすでに画面上に書き込
まれている内容に大きく依存するため、他の図形
に邪魔されて、思うように塗りつぶしが行えない
といつたことが起こる。
また別の手法としては「走査変換」（Scan
Conversion）と呼ばれるものが知られている。
走査変換については「対話式コンピユータ・グラ
フイツクスの原理」（Principles of Interactive
Computer Graphics」第２版、ダブリユー・エ
ム・ニユーマン（W.M.Newman）著、マグロー
ヒル社、1979年、pp232〜243に記載がある。こ
の手法では、対象となる図形と画面を構成する走
査線との交点をすべて求め、得られた交点の奇偶
ペアの間を塗りつぶすものである。第２図はこれ
を模式的に示す。この手法では対象となる図形の
幾何学的性質を積極的に利用することにより、画
面表示用メモリの内容とは無関係に塗りつぶしを
行うことができ、処理速度も向上する。走査変換
方法では精度を保ちつつ、いかに効率よく交点計
算を行うかが大きな鍵となる。
Conversion）と呼ばれるものが知られている。
走査変換については「対話式コンピユータ・グラ
フイツクスの原理」（Principles of Interactive
Computer Graphics」第２版、ダブリユー・エ
ム・ニユーマン（W.M.Newman）著、マグロー
ヒル社、1979年、pp232〜243に記載がある。こ
の手法では、対象となる図形と画面を構成する走
査線との交点をすべて求め、得られた交点の奇偶
ペアの間を塗りつぶすものである。第２図はこれ
を模式的に示す。この手法では対象となる図形の
幾何学的性質を積極的に利用することにより、画
面表示用メモリの内容とは無関係に塗りつぶしを
行うことができ、処理速度も向上する。走査変換
方法では精度を保ちつつ、いかに効率よく交点計
算を行うかが大きな鍵となる。
この発明は、円および楕円の走査変換に関する
もので、円弧の発生手法に新しい考え方を導入
し、従来存在した精度上の問題を解消したもので
ある。
もので、円弧の発生手法に新しい考え方を導入
し、従来存在した精度上の問題を解消したもので
ある。
さて指定された中心および半径をもつ円（楕円
であれば中心と長径、短径が指定される）を正確
に描くために、これまで三角関数等の関数計算を
必要としない、効率的な方法がいくつか提案され
ている。
であれば中心と長径、短径が指定される）を正確
に描くために、これまで三角関数等の関数計算を
必要としない、効率的な方法がいくつか提案され
ている。
その１つは始点から終点まで増分的に点を移動
させていき、所望の線分を得るものである。増分
的な点の移動とは、、たとえば１つの画素から、
これに隣接する画素のうち０度、90度、180度お
よび270度の角度位置にあるものの任意の１つに
移動することをいう。これは４画素連結という。
０度、45度、90度、……315度の角度位置にある
隣接画素に移行させてもよい。これを８画素連結
という。次回に移行すべき画素を選定する際には
何らかのテストを行つて２つまたは３つの隣接画
素を候補として絞り込む。そして候補点の各々と
実際の線分との間の距離を求め、これが一番小さ
くなる候補点を最終的に選定する。このような手
法はジエー・イー・プレゼンハム（J.E.
Bresenham）の「円弧の増分デジタル表示用線
形アルゴリズム」、コミユニケーシヨンズ・オ
ブ・エイ・シ−・エム（Communications of
ACM）20（２）、1977年２月pp100〜106に記載さ
れている。円および楕円を走査変換により塗りつ
ぶす際にも、このような方法の基本的な考え方を
適用できるけれども、ただ単にそれを流用しただ
けでは、以下に述べるような精度上の問題が生じ
る。
させていき、所望の線分を得るものである。増分
的な点の移動とは、、たとえば１つの画素から、
これに隣接する画素のうち０度、90度、180度お
よび270度の角度位置にあるものの任意の１つに
移動することをいう。これは４画素連結という。
０度、45度、90度、……315度の角度位置にある
隣接画素に移行させてもよい。これを８画素連結
という。次回に移行すべき画素を選定する際には
何らかのテストを行つて２つまたは３つの隣接画
素を候補として絞り込む。そして候補点の各々と
実際の線分との間の距離を求め、これが一番小さ
くなる候補点を最終的に選定する。このような手
法はジエー・イー・プレゼンハム（J.E.
Bresenham）の「円弧の増分デジタル表示用線
形アルゴリズム」、コミユニケーシヨンズ・オ
ブ・エイ・シ−・エム（Communications of
ACM）20（２）、1977年２月pp100〜106に記載さ
れている。円および楕円を走査変換により塗りつ
ぶす際にも、このような方法の基本的な考え方を
適用できるけれども、ただ単にそれを流用しただ
けでは、以下に述べるような精度上の問題が生じ
る。
たとえば四画素連結で円を発生した場合、第３
図のような点列を得る。いまｘ軸上の点ｘ＝ｒか
ら反時計回りに点列を発生し、それらを利用しな
がら塗りつぶしを行うことを考える。走査変換の
場合は第２図からも分るとおり、各走査線につい
てただ一つの点が順次発生されれば十分であるか
ら、一走査線上に連なる複数の点が発生した際
に、どの１点を選びだすかが問題となる。例えば
ｙ座標値が変化した時の点を選ぶと、第４図にあ
るような黒い点が選ばれ（二重丸の点は、一走査
線上の点の数をつねに偶数に保つためのもので、
ｙ方向の変分の符号を見ながら、別途付け加えて
やる必要がある）、最終的に同図のような真円か
らは程遠い、いびつな円が得られる。もし対象と
なる図形が、縦方向につぶれた楕円であればある
ほど、その影響はさらに顕著なものとなる（第６
図）。
図のような点列を得る。いまｘ軸上の点ｘ＝ｒか
ら反時計回りに点列を発生し、それらを利用しな
がら塗りつぶしを行うことを考える。走査変換の
場合は第２図からも分るとおり、各走査線につい
てただ一つの点が順次発生されれば十分であるか
ら、一走査線上に連なる複数の点が発生した際
に、どの１点を選びだすかが問題となる。例えば
ｙ座標値が変化した時の点を選ぶと、第４図にあ
るような黒い点が選ばれ（二重丸の点は、一走査
線上の点の数をつねに偶数に保つためのもので、
ｙ方向の変分の符号を見ながら、別途付け加えて
やる必要がある）、最終的に同図のような真円か
らは程遠い、いびつな円が得られる。もし対象と
なる図形が、縦方向につぶれた楕円であればある
ほど、その影響はさらに顕著なものとなる（第６
図）。
ここで円のもつ対称性に着目し、実際に発生す
る点列は例えば第１象限（四分円）に属するもの
だけとし、他の象限での値は、単に第一象限の値
の符号を反転することで得るものとすれば（点列
を発生するすぐそばから点のペアが得られ、これ
らの間を塗りつぶすことができるので、処理時間
の短縮にもつながる）、図形の対称性はひとまず
保たれるものの、上端および下端が平な円となつ
てしまう（第５図）。
る点列は例えば第１象限（四分円）に属するもの
だけとし、他の象限での値は、単に第一象限の値
の符号を反転することで得るものとすれば（点列
を発生するすぐそばから点のペアが得られ、これ
らの間を塗りつぶすことができるので、処理時間
の短縮にもつながる）、図形の対称性はひとまず
保たれるものの、上端および下端が平な円となつ
てしまう（第５図）。
いずれにしても、上記の方法では問題の根本的
な解決手段にはなり得ず、精度の高い円および楕
円の走査変換を行うには、新たな工夫が必要であ
る。結果として円と走査線との交点に最も近い点
が、順次一つずつ求められるような方法が最適で
あるが、円の方程式ｙ＝√2−2からこれを直接
的に求めようとすると、平方根の計算が必要にな
る。円を簡便に発生させる他の手法としては
DDA（デジタル・デイフアレンシヤル・アナライ
ザ）法が知られている。前掲「対話式コンピユー
タ・グラフイツクスの原理」、pp27〜28に記載が
ある。ここではDDAについて簡単に触れておく
ことにする。
な解決手段にはなり得ず、精度の高い円および楕
円の走査変換を行うには、新たな工夫が必要であ
る。結果として円と走査線との交点に最も近い点
が、順次一つずつ求められるような方法が最適で
あるが、円の方程式ｙ＝√2−2からこれを直接
的に求めようとすると、平方根の計算が必要にな
る。円を簡便に発生させる他の手法としては
DDA（デジタル・デイフアレンシヤル・アナライ
ザ）法が知られている。前掲「対話式コンピユー
タ・グラフイツクスの原理」、pp27〜28に記載が
ある。ここではDDAについて簡単に触れておく
ことにする。
第７図において、半径ｒの円周上の１点pk
（xK，yK）が求まつているとする。この点pkから
Δθだけ反時計廻り方向に進んだ円周上の点 pK+1（xK+1，yK+1）は xK+1＝ｒ cos （θ＋Δθ） ＝ｒ cos θ cosΔθ−ｒ sinθsinΔθ ＝xKcosΔθ−yKsinΔθ ……(1) yK+1＝ｒ sin（θ＋Δθ） ＝ｒ sinθ cosΔθ＋ｒ cosθsinΔθ ＝yKcosΔθ＋xKsinΔθ ……(2) となる。
（xK，yK）が求まつているとする。この点pkから
Δθだけ反時計廻り方向に進んだ円周上の点 pK+1（xK+1，yK+1）は xK+1＝ｒ cos （θ＋Δθ） ＝ｒ cos θ cosΔθ−ｒ sinθsinΔθ ＝xKcosΔθ−yKsinΔθ ……(1) yK+1＝ｒ sin（θ＋Δθ） ＝ｒ sinθ cosΔθ＋ｒ cosθsinΔθ ＝yKcosΔθ＋xKsinΔθ ……(2) となる。
ここでΔθを微小角度とすると、cosΔθ≒１、
sinΔθ≒Δθとなる。さらに、Δθ＝ｅ＝2-m（ｍは
正の整数）とおけば式(1)および(2)は xK+1＝xK−eyK ……(3) yK+1＝yK＋exK ……(4) ただし2m-1＜ｒ＜2m となる。しかしこれらの式をそのまま用いると発
散してしまうので式(4)のxKをxK+1に置き換え xK+1＝xK−eyK ……(5) yK+1＝yK＋exK+1 ……(6) を得る。式(5)および(6)から真円の値が得られるこ
とが確かめられている。
sinΔθ≒Δθとなる。さらに、Δθ＝ｅ＝2-m（ｍは
正の整数）とおけば式(1)および(2)は xK+1＝xK−eyK ……(3) yK+1＝yK＋exK ……(4) ただし2m-1＜ｒ＜2m となる。しかしこれらの式をそのまま用いると発
散してしまうので式(4)のxKをxK+1に置き換え xK+1＝xK−eyK ……(5) yK+1＝yK＋exK+1 ……(6) を得る。式(5)および(6)から真円の値が得られるこ
とが確かめられている。
ところでこのDDAの手法を走査変換に適用す
ることについてもすでに提案がなされている（特
開昭59−206884号公報）。しかしこの場合にも１
本の走査線と曲線との交点に一連の点が発生して
しまうので、上述の増分的デジタル表示と同様の
問題が生じる。特開昭59−206884号にはこの点に
ついて何ら記載がない。
ることについてもすでに提案がなされている（特
開昭59−206884号公報）。しかしこの場合にも１
本の走査線と曲線との交点に一連の点が発生して
しまうので、上述の増分的デジタル表示と同様の
問題が生じる。特開昭59−206884号にはこの点に
ついて何ら記載がない。
Ｄ 発明が解決しようとする問題点
この発明は以上の事情を考慮してなされたもの
であり、走査変換に最適で、しかも三角関数や平
方根の計算を必要とすることなく円弧または楕円
曲線を発生することができる曲線発生方法を提出
することを目的としている。
であり、走査変換に最適で、しかも三角関数や平
方根の計算を必要とすることなく円弧または楕円
曲線を発生することができる曲線発生方法を提出
することを目的としている。
Ｅ 問題点を解決するための手段
この発明では以上の目的を達成するために、
DDAの漸化式を変更して同一走査線上に連続し
た点列が発生するのを防ぐようにしている。
DDAの漸化式を変更して同一走査線上に連続し
た点列が発生するのを防ぐようにしている。
具体的にはつぎの漸化式(7)および(8)または(9)お
よび(10)に基づいて円についての点列を得るように
している。
よび(10)に基づいて円についての点列を得るように
している。
yK+1＝yK＋１ ……(7)
xK+1＝xK−yK+1／xK ……(8)
yK+1＝yK−１ ……(9)
xK+1＝xK＋yK+1／xK ……(10)
ただしｋ＝０，１，２……，xK≠０
なお走査変換により直線的に塗りつぶしを行う
方向をｘ軸とし、これと直交する方向をｙ軸とし
た。
方向をｘ軸とし、これと直交する方向をｙ軸とし
た。
Ｆ 作用
ここでは上述の漸化式(7)および(8)の意味につい
て考えよう。
て考えよう。
先に触れた従前のDDAの漸化式(3)，(4)，(5)お
よび(6)をもう一度考える。
よび(6)をもう一度考える。
xK+1＝xK−eyK ……(3)
yK+1＝yK＋exK ……(4)
xK+1＝xK−eyK ……(5)
yK+1＝yK＋exK+1 ……(6)
式(3)，(4)から明らかなようにベクトル（xK+1，
yK+1）はベクトル（xK，yK）に微小ベクトル（−
eyK，exK）を加えたものである。そして微小ベ
クトル（−eyK，exK）はベクトル（xK，yK）と
直角である。したがつて式(3)および(4)で得られる
点列は発散してしまう。式(5)および(6)はこの発散
を解消したものである。すなわち、式(5)および(6)
を行列で表わすとつぎのようになる。
yK+1）はベクトル（xK，yK）に微小ベクトル（−
eyK，exK）を加えたものである。そして微小ベ
クトル（−eyK，exK）はベクトル（xK，yK）と
直角である。したがつて式(3)および(4)で得られる
点列は発散してしまう。式(5)および(6)はこの発散
を解消したものである。すなわち、式(5)および(6)
を行列で表わすとつぎのようになる。
〔xK+1，yK+1〕＝〔xKyK〕 １ ｅ
−ｅ １−e2
……(11) この式(11)でdet １ ｅ −ｅ １−e2は １となるのでこの式(11)により生成される点列は真
円を描くことが明らかである。このことについて
はたとえばデイー・コーエン（Cohen，Ｄ）氏の
「線型差分曲線」（ハーバード大学、1969年）を参
照されたい。
……(11) この式(11)でdet １ ｅ −ｅ １−e2は １となるのでこの式(11)により生成される点列は真
円を描くことが明らかである。このことについて
はたとえばデイー・コーエン（Cohen，Ｄ）氏の
「線型差分曲線」（ハーバード大学、1969年）を参
照されたい。
ところで式(6)でｙ軸方向の増分を１とした場
合、すなわち走査線１本につき１つ点を発生させ
たい場合、問題がある。すなわち増分を１とする
ためにexK+1＝１とすると式(5)が xK+1＝xK−yK／xK+1 となり、xK+1を得るのにxK+1が必要となり不合理
であるからである。
合、すなわち走査線１本につき１つ点を発生させ
たい場合、問題がある。すなわち増分を１とする
ためにexK+1＝１とすると式(5)が xK+1＝xK−yK／xK+1 となり、xK+1を得るのにxK+1が必要となり不合理
であるからである。
この発明では式(3)のyKをyK+1で置きかえたつぎ
の式に基礎を置いている。
の式に基礎を置いている。
xK+1＝xK−eyK+1 ……(12)
yK+1＝yK＋exK ……（13）
この式を行列で表わすと
〔xK+1，yK+1〕＝〔xK，yK〕１−e2 ｅ
−ｅ １
……(14) となる。
……(14) となる。
この式(14)でもdet１−e2 ｅ
−ｅ １＝１
であるから真円が描かれることはもちろんであ
る。そしてこれらの式(12)および（13）だｙ軸方向
の増分を１とするためexK＝１とすれば、式(7)，
(8)を得る。
る。そしてこれらの式(12)および（13）だｙ軸方向
の増分を１とするためexK＝１とすれば、式(7)，
(8)を得る。
以上から明らかなように式(7)，(8)は走査線との
交点に１つづつ点をプロツトしながら真円を描く
ことができるものであることがわかる。
交点に１つづつ点をプロツトしながら真円を描く
ことができるものであることがわかる。
なお、式(8)，(9)は反時計廻り方向に円をプロツ
トする式であり、式(9)，(10)は時計廻り方向に円を
プロツトするものである。このことについては説
明を要しないであろう。
トする式であり、式(9)，(10)は時計廻り方向に円を
プロツトするものである。このことについては説
明を要しないであろう。
なお、実際に円ゆ描く場合にはその中心が原点
にあるとはかぎらないので平行移動を行う必要が
ある。また楕円の場合には長径および短径に応じ
てスケール変換を別途行う必要がある。
にあるとはかぎらないので平行移動を行う必要が
ある。また楕円の場合には長径および短径に応じ
てスケール変換を別途行う必要がある。
Ｇ 実施例
以下この発明を円の塗りつぶしに適用した一実
施例について第１図、第８図〜第１２図を参照し
ながら説明しよう。この実施例では第９図に示す
ように円の中心（xc，yc）を通る走査線上の画
素を点psからpeにいたるまで塗りつぶし、以降
上方向および下方向に隣接する走査線上の画素を
順次塗りつぶしていくようにしている。これを第
１０図に示す。具体的には第１１図に示すように
所望の円上の点psを決定したのち、円の対称性を
利用して点pe，ps′，pe′を求める。そしてps〜pe
間およびps′〜pe′間の画素を塗りつぶすのであ
る。なお、この実施例の説明のうえで用いる記号
は第１１図に示されている。
施例について第１図、第８図〜第１２図を参照し
ながら説明しよう。この実施例では第９図に示す
ように円の中心（xc，yc）を通る走査線上の画
素を点psからpeにいたるまで塗りつぶし、以降
上方向および下方向に隣接する走査線上の画素を
順次塗りつぶしていくようにしている。これを第
１０図に示す。具体的には第１１図に示すように
所望の円上の点psを決定したのち、円の対称性を
利用して点pe，ps′，pe′を求める。そしてps〜pe
間およびps′〜pe′間の画素を塗りつぶすのであ
る。なお、この実施例の説明のうえで用いる記号
は第１１図に示されている。
さて第８図はこの実施例で用いるパーソナル・
コンピユータ・システムの概要を示す。このシス
テムは日本IBM（株）のIBM5550とすることがで
きる。第８図においてデータバス１にはCPU２、
キーボード３、フロツピ・デイスク４、CRTデ
イスプレイ５、主ストレージ６、リフレツシユ・
バツフア７等が接続されている。キーボード３、
フロツプ・デイスク４、CRTデイスプレイ５の
それぞれとデータバス１との間にはインターフエ
ースとしてキーボード・インターフエース８、フ
ロツピ・デイスク・コントローラ９、CRTデイ
スプレイ・コントローラ１０が設けられている。
この図においてはアドレスバス、コントロールバ
ス、ROS等は省略されている。
コンピユータ・システムの概要を示す。このシス
テムは日本IBM（株）のIBM5550とすることがで
きる。第８図においてデータバス１にはCPU２、
キーボード３、フロツピ・デイスク４、CRTデ
イスプレイ５、主ストレージ６、リフレツシユ・
バツフア７等が接続されている。キーボード３、
フロツプ・デイスク４、CRTデイスプレイ５の
それぞれとデータバス１との間にはインターフエ
ースとしてキーボード・インターフエース８、フ
ロツピ・デイスク・コントローラ９、CRTデイ
スプレイ・コントローラ１０が設けられている。
この図においてはアドレスバス、コントロールバ
ス、ROS等は省略されている。
CRTデイスプレイ５はたとえば15インチ・モ
ノクローム型のものであり、1024×768ドツトを
約0.22mmのスポツトで表示することができる。リ
フレツシユ・バツフア７は1024×768ドツトの全
点アドレス可能グラフイツク・モードをサポート
する容量を有している。このリフレツシユ・バツ
フア７はCPU２およびCRTデイスプレイ・コン
トローラ１０によりアドレス可能であり、CPU
アドレスによりグラフイツク・データをリフレツ
シユ・バツフア７に書き込み、またリフレツシ
ユ・バツフア７の内容を読み出すことができる。
CRTデイスプレイ・コントローラ１０はCRTデ
イスプレイ５用の垂直同期信号および水平同期信
号に応じてリフレツシユ・バツフア７をアクセス
し、その内容をCRTデイスプレイ５に表示する。
ノクローム型のものであり、1024×768ドツトを
約0.22mmのスポツトで表示することができる。リ
フレツシユ・バツフア７は1024×768ドツトの全
点アドレス可能グラフイツク・モードをサポート
する容量を有している。このリフレツシユ・バツ
フア７はCPU２およびCRTデイスプレイ・コン
トローラ１０によりアドレス可能であり、CPU
アドレスによりグラフイツク・データをリフレツ
シユ・バツフア７に書き込み、またリフレツシ
ユ・バツフア７の内容を読み出すことができる。
CRTデイスプレイ・コントローラ１０はCRTデ
イスプレイ５用の垂直同期信号および水平同期信
号に応じてリフレツシユ・バツフア７をアクセス
し、その内容をCRTデイスプレイ５に表示する。
この実施例の方法はたとえばアプリケーシヨ
ン・プログラムのパツケージ・デイスクとして提
供される。デイスク・オペレーテイング・システ
ムの管理のもとにこのパツケージ・デイスクをフ
ロツピ・デイスク４にロードすると、このプログ
ラムが主ストレージ６に転送され、そののち実行
される。この実施例の方法は第１図に詳細に示さ
れている。
ン・プログラムのパツケージ・デイスクとして提
供される。デイスク・オペレーテイング・システ
ムの管理のもとにこのパツケージ・デイスクをフ
ロツピ・デイスク４にロードすると、このプログ
ラムが主ストレージ６に転送され、そののち実行
される。この実施例の方法は第１図に詳細に示さ
れている。
なお、この例では所望の円Ｏに沿う点psを求め
るに際し、半径ｒを同一とし、かつ中心を原点
（Ｏ，Ｏ）とする円O′に沿う点（ｘ，ｙ）を変形
DDAで求め、こののち平行移動を行つてpsを得
るようにしている。psにしたがつてさらにpe，
ps′およびpe′を求めることができることはもちろ
んである。
るに際し、半径ｒを同一とし、かつ中心を原点
（Ｏ，Ｏ）とする円O′に沿う点（ｘ，ｙ）を変形
DDAで求め、こののち平行移動を行つてpsを得
るようにしている。psにしたがつてさらにpe，
ps′およびpe′を求めることができることはもちろ
んである。
第１図においてキーボード３を用い、塗りつぶ
しを行う円の中心（xc，yc）および半径ｒをキ
ーボード３を介して入力する。そうするとこのデ
ータxc＋ycおよびｒが主ストレージ６に転送さ
れる（ステツプ11）。こののち円O′上の点（ｘ，
ｙ）およびカウンタＣがそれぞれ（ｒ，Ｏ）およ
びＯに初期化される（ステツプ12）。増分開始点
をｘ軸上の点（ｒ，Ｏ）としているので半径デー
タをそのまま初期値データに用いることができ
る。ｘ軸またｙ軸上にない円O′の点を増分開始
点とすると、その初期値データを得るのに平方根
の計算が必要となり、煩雑である。
しを行う円の中心（xc，yc）および半径ｒをキ
ーボード３を介して入力する。そうするとこのデ
ータxc＋ycおよびｒが主ストレージ６に転送さ
れる（ステツプ11）。こののち円O′上の点（ｘ，
ｙ）およびカウンタＣがそれぞれ（ｒ，Ｏ）およ
びＯに初期化される（ステツプ12）。増分開始点
をｘ軸上の点（ｒ，Ｏ）としているので半径デー
タをそのまま初期値データに用いることができ
る。ｘ軸またｙ軸上にない円O′の点を増分開始
点とすると、その初期値データを得るのに平方根
の計算が必要となり、煩雑である。
こののちステツプ13で中心（xc，yc）を通る
走査線と円Ｏとの交点psおよびpe（第９図）につ
いてのデータyc，xc−ｒおよびｒ＋xcをそれぞ
れyy，xsおよびxeに代入する。つぎにステツプ
14で点（xs，yc）〜（xe，yc）の間の画素に対
応するリフレツシユ・バツフア７のロケーシヨン
に塗りつぶしデータを書き込む。以上で第９図の
一走査線上の塗りつぶし動作が終了する。以降、
この走査線の上または下方向に隣接する走査線に
ついて走査変換を行つていく。
走査線と円Ｏとの交点psおよびpe（第９図）につ
いてのデータyc，xc−ｒおよびｒ＋xcをそれぞ
れyy，xsおよびxeに代入する。つぎにステツプ
14で点（xs，yc）〜（xe，yc）の間の画素に対
応するリフレツシユ・バツフア７のロケーシヨン
に塗りつぶしデータを書き込む。以上で第９図の
一走査線上の塗りつぶし動作が終了する。以降、
この走査線の上または下方向に隣接する走査線に
ついて走査変換を行つていく。
すなわち、ステツプ15においてカウンタＣおよ
び円O′上の点のｙ座標ｙをそれぞれ＋１増分し、
さらに円O′上の点のｘ座標ｘをｘ−ｙ／ｘで代
入する。こののちステツプ16でyy，xsおよびxe
にそれぞれｙ＋yc，xc−〔ｘ〕および〔ｘ〕＋xc
を代入する。なお〔ｘ〕はｘの整数部を示す。こ
の操作が＋１増分後の走査線と円Ｏとの交点psお
よびpeを求めるためのものであることは明らか
である。つぎにステツプ17で増分後の走査線につ
いての塗つぶしを行う。すなわち点ps（xs，yy）
〜点pe（xe，yy）の間の画素に対応するリフレツ
シユ・バツフア７のロケーシヨンに塗りつぶしデ
ータを書き込む。
び円O′上の点のｙ座標ｙをそれぞれ＋１増分し、
さらに円O′上の点のｘ座標ｘをｘ−ｙ／ｘで代
入する。こののちステツプ16でyy，xsおよびxe
にそれぞれｙ＋yc，xc−〔ｘ〕および〔ｘ〕＋xc
を代入する。なお〔ｘ〕はｘの整数部を示す。こ
の操作が＋１増分後の走査線と円Ｏとの交点psお
よびpeを求めるためのものであることは明らか
である。つぎにステツプ17で増分後の走査線につ
いての塗つぶしを行う。すなわち点ps（xs，yy）
〜点pe（xe，yy）の間の画素に対応するリフレツ
シユ・バツフア７のロケーシヨンに塗りつぶしデ
ータを書き込む。
こののちステツプ18および19で点ps′〜点pe′の
間の塗りつぶしを行う。すなわち線分は線
分ps′pe′とｘ軸について軸対称であるから、yyに
yc−ｙを代入すればよい（ステツプ18）。このの
ちステツプ19でステツプ17と同様の塗りつぶしを
行う。
間の塗りつぶしを行う。すなわち線分は線
分ps′pe′とｘ軸について軸対称であるから、yyに
yc−ｙを代入すればよい（ステツプ18）。このの
ちステツプ19でステツプ17と同様の塗りつぶしを
行う。
以上のステツプ15〜19はカウンタＣがｒ−１と
等しくなるまで繰り返される（ステツプ20）。カ
ウンタＣがｒ−１に等しくなると、ステツプ21お
よび22が実行され、そののち動作が終了する。ス
テツプ21および22ではそれぞれ（ｒ＋yc，xc）
および（yc−ｒ，xc）に対応するリフレツシ
ユ・バツフア７のロケーシヨンに塗りつぶしデー
タが書き込まれる。こうして第１２図に丸印で示
すような円Ｏに沿う点のプロツトが行われるとと
もに、同一走査線上で対をなすプロツトの間の塗
りつぶしが行われる。この塗りつぶした円の表示
がCRTデイスプレイ５で行われることはもちろ
んである。
等しくなるまで繰り返される（ステツプ20）。カ
ウンタＣがｒ−１に等しくなると、ステツプ21お
よび22が実行され、そののち動作が終了する。ス
テツプ21および22ではそれぞれ（ｒ＋yc，xc）
および（yc−ｒ，xc）に対応するリフレツシ
ユ・バツフア７のロケーシヨンに塗りつぶしデー
タが書き込まれる。こうして第１２図に丸印で示
すような円Ｏに沿う点のプロツトが行われるとと
もに、同一走査線上で対をなすプロツトの間の塗
りつぶしが行われる。この塗りつぶした円の表示
がCRTデイスプレイ５で行われることはもちろ
んである。
つぎに第１３図〜第１５図を参照してこの発明
を楕円の塗りつぶしに適用した実施例について説
明しよう。この実施例で塗りつぶすものは第１４
図に示すような楕円である。尚第１３図において
第１図と対応する箇所には第１図の参照数字に
100を加えた数字を付し、以下では第１図と異な
る部分についてのみ説明を加えることとする。
を楕円の塗りつぶしに適用した実施例について説
明しよう。この実施例で塗りつぶすものは第１４
図に示すような楕円である。尚第１３図において
第１図と対応する箇所には第１図の参照数字に
100を加えた数字を付し、以下では第１図と異な
る部分についてのみ説明を加えることとする。
第１３図においてキーボード３を介して入力さ
れたデータすなわち中心（xc，yc）および長径
ａ、短径ｂが読み込まれる（ステツプ111）。ステ
ツプ113ではこれに応じてyy，xsおよびxeにそれ
ぞれyc，xc−ａおよびａ＋xcが代入される。
れたデータすなわち中心（xc，yc）および長径
ａ、短径ｂが読み込まれる（ステツプ111）。ステ
ツプ113ではこれに応じてyy，xsおよびxeにそれ
ぞれyc，xc−ａおよびａ＋xcが代入される。
またステツプ116ではxc−〔ａ＊×1b〕および
〔ａ＊×1b〕＋xcがそれぞれxs及びxeに代入され
る。
〔ａ＊×1b〕＋xcがそれぞれxs及びxeに代入され
る。
さらにステツプ121および122では点（ｂ＋yc，
xc）および（yc−ｂ，xc）に対応するリフレツ
シユ・バツフア７のロケーシヨンに塗りつぶしデ
ータが書き込まれる。
xc）および（yc−ｂ，xc）に対応するリフレツ
シユ・バツフア７のロケーシヨンに塗りつぶしデ
ータが書き込まれる。
第１３図に示すシーケンスにより第１５図に示
すような楕円が得られ、この内部が塗りつぶされ
る。
すような楕円が得られ、この内部が塗りつぶされ
る。
なお以上の実施例においては単に円および楕円
を全体的に塗りつぶすことについて説明したが、
第１６図に示すようなパイ・チヤートを塗りつぶ
すこともできる。この場合にはその間を塗りつぶ
す走査線上の奇偶ペアについてテーブルをつく
り、このテーブルに基づいて塗りつぶしデータを
リフレツシユ・バツフアに書き込んでいけばよ
い。たとえば走査線LSと円Ｏとの交点をこの発
明の方法で得、また直線LLと走査線LSとの交点
を任意の手法たとえばブレゼンハム法で得、この
データをテーブルにストアしておけばよい。外観
形状を楕円とするパイ・チヤートも同様にして得
ることができることはもちろんである。
を全体的に塗りつぶすことについて説明したが、
第１６図に示すようなパイ・チヤートを塗りつぶ
すこともできる。この場合にはその間を塗りつぶ
す走査線上の奇偶ペアについてテーブルをつく
り、このテーブルに基づいて塗りつぶしデータを
リフレツシユ・バツフアに書き込んでいけばよ
い。たとえば走査線LSと円Ｏとの交点をこの発
明の方法で得、また直線LLと走査線LSとの交点
を任意の手法たとえばブレゼンハム法で得、この
データをテーブルにストアしておけばよい。外観
形状を楕円とするパイ・チヤートも同様にして得
ることができることはもちろんである。
Ｈ 発明の効果
以上説明したようにこの発明によれば極めて精
度の高い円および楕円を発生させることができ、
しかも走査線と曲線との交点は１つの点として決
定されるので、すなわち交点が一連の点列として
表わされることがないので、走査変換に最適であ
る。さらに平方根や三角関数の演算を必要とせ
ず、短時間で円および楕円の発生を行える。
度の高い円および楕円を発生させることができ、
しかも走査線と曲線との交点は１つの点として決
定されるので、すなわち交点が一連の点列として
表わされることがないので、走査変換に最適であ
る。さらに平方根や三角関数の演算を必要とせ
ず、短時間で円および楕円の発生を行える。
第１図はこの発明を円の塗りつぶしに適用した
一実施例を示すフローチヤート、第２図〜第７図
は従来例を説明するための図、第８図は第１図例
を実行するのに用いるシステムの概略を示すブロ
ツク図、第９図〜第１２図は第１図例を説明する
ための図、第１３図はこの発明を楕円の塗りつぶ
しに適用した他の実施例を示すフローチヤート、
第１４図および第１５図は第１３図例を説明する
ための図、第１６図は第１図例の変形例を説明す
るための図である。 １……データバス、２……CPU、５……CRT
デイスプレイ、６……主ストレージ、７……リフ
レツシユ・バツフア、１０……CRTデイスプレ
イ・コントローラ。
一実施例を示すフローチヤート、第２図〜第７図
は従来例を説明するための図、第８図は第１図例
を実行するのに用いるシステムの概略を示すブロ
ツク図、第９図〜第１２図は第１図例を説明する
ための図、第１３図はこの発明を楕円の塗りつぶ
しに適用した他の実施例を示すフローチヤート、
第１４図および第１５図は第１３図例を説明する
ための図、第１６図は第１図例の変形例を説明す
るための図である。 １……データバス、２……CPU、５……CRT
デイスプレイ、６……主ストレージ、７……リフ
レツシユ・バツフア、１０……CRTデイスプレ
イ・コントローラ。
Claims (1)
- 【特許請求の範囲】 １ 入力装置、ラスタ走査表示装置およびデータ
処理装置を含む表示装置であつて、上記入力装置
が塗りつぶしを行う円、楕円またはこれらの部分
的な図形の輪郭に関する情報を入力でき、、上記
ラスタ走査表示装置が二次元座標に対応する複数
の画素を表示でき、さらに上記データ処理装置が
上記輪郭と上記ラスタ表示装置の各走査線との交
点の各々について近傍の唯一の画素を決定し、各
走査線について決定された画素が一対あるときに
は決定された画素のみでなくその一対の画素の間
にある画素も塗りつぶしの画素とする処理を行う
ように構成されたものに用いられる、円、楕円ま
たはこれらの部分的な図形の塗りつぶしを行う方
法において、 つぎのステツプａ〜ｄを有することを特徴とす
る図形塗りつぶし方法。 (a) 所望の円または部分円の中心点の二次元座標
および径をそれぞれ表すデータを入力するステ
ツプ。 (b) 始点（x0，y0）から始まる一連の点（xK，
yK）（ただしｋ＝０，１，２，……、xK≠０）
であつて、原点を中心とする円弧に沿うものを yK+1＝yK＋１ xK+1＝xK−yK+1／xK または yK+1＝yK−１ xK+1＝xK＋yK+1／xK の漸化式に基づいて順次生成するステツプ。 (c) 上記ステツプで生成した一連の点の座標を変
換して上記入力二次元座標を中心点とする円、
楕円またはこれらの部分的な図形の輪郭を表す
一連の画素を生成するステツプ。 (d) 上記生成された円、楕円またはこれらの部分
的な図形の輪郭を表す画素と、各走査線上で対
をなすこれらの画素の間の画素とを塗りつぶす
ステツプ。
Priority Applications (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60089088A JPS61249088A (ja) | 1985-04-26 | 1985-04-26 | 図形塗りつぶし方法 |
| CA000501113A CA1247246A (en) | 1985-04-26 | 1986-02-05 | Method for generating a circular or elliptic arc |
| DE8686104603T DE3687077T2 (de) | 1985-04-26 | 1986-04-04 | Verfahren zum generieren eines kreisfoermigen oder elliptischen bogens. |
| EP86104603A EP0199160B1 (en) | 1985-04-26 | 1986-04-04 | Method for generating a circular or elliptic arc |
| US06/853,572 US5146551A (en) | 1985-04-26 | 1986-04-18 | System for generating a circular or elliptic arc on a digital display |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60089088A JPS61249088A (ja) | 1985-04-26 | 1985-04-26 | 図形塗りつぶし方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS61249088A JPS61249088A (ja) | 1986-11-06 |
| JPH0366675B2 true JPH0366675B2 (ja) | 1991-10-18 |
Family
ID=13961116
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP60089088A Granted JPS61249088A (ja) | 1985-04-26 | 1985-04-26 | 図形塗りつぶし方法 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US5146551A (ja) |
| EP (1) | EP0199160B1 (ja) |
| JP (1) | JPS61249088A (ja) |
| CA (1) | CA1247246A (ja) |
| DE (1) | DE3687077T2 (ja) |
Families Citing this family (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB9009127D0 (en) * | 1990-04-24 | 1990-06-20 | Rediffusion Simulation Ltd | Image generator |
| US5420970A (en) * | 1991-03-13 | 1995-05-30 | Martin Marietta Corporation | Method for determining computer image generation display pixels occupied by a circular feature |
| GB9312447D0 (en) * | 1992-10-28 | 1993-07-28 | Int Technical Illustration Co | Method of tracing a drawing and apparatus for embodying the method |
| JP3210141B2 (ja) * | 1993-06-24 | 2001-09-17 | 松下電器産業株式会社 | 直線描画装置 |
| WO2003071452A2 (en) * | 2002-02-15 | 2003-08-28 | Computer Associates Think, Inc. | System and method for drawing an elliptical arc |
| JP2005031369A (ja) * | 2003-07-11 | 2005-02-03 | Toshiba Corp | 映像表示装置及び映像表示方法 |
| CN102646281B (zh) * | 2011-02-16 | 2015-02-11 | 富士通株式会社 | 用于对椭圆弧进行栅格化的方法和系统 |
Family Cites Families (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4283765A (en) * | 1978-04-14 | 1981-08-11 | Tektronix, Inc. | Graphics matrix multiplier |
| US4631750A (en) * | 1980-04-11 | 1986-12-23 | Ampex Corporation | Method and system for spacially transforming images |
| JPS578584A (en) * | 1980-06-18 | 1982-01-16 | Nippon Electric Co | Video controller |
| AU542593B2 (en) * | 1981-01-21 | 1985-02-28 | Tokyo Shibaura Denki Kabushiki Kaisha | Straight line co-ordinates generator |
| JPS59137942A (ja) * | 1983-01-28 | 1984-08-08 | Hitachi Ltd | 画像位置合わせ方式 |
| JPS59206884A (ja) * | 1983-05-10 | 1984-11-22 | カシオ計算機株式会社 | 円または楕円の塗りつぶし方式 |
| US4692887A (en) * | 1983-05-10 | 1987-09-08 | Casio Computer Co., Ltd. | Circle and circular arc generator |
| US4602346A (en) * | 1983-05-19 | 1986-07-22 | Matsushita Electric Industrial Co., Ltd. | Method and apparatus for processing image data using sum and subtract operations |
| US4593406A (en) * | 1984-01-16 | 1986-06-03 | The United States Of America As Represented By The United States Department Of Energy | Automatic image acquisition processor and method |
| GB8415602D0 (en) * | 1984-06-19 | 1984-07-25 | Secr Defence | Raster image manipulator |
-
1985
- 1985-04-26 JP JP60089088A patent/JPS61249088A/ja active Granted
-
1986
- 1986-02-05 CA CA000501113A patent/CA1247246A/en not_active Expired
- 1986-04-04 EP EP86104603A patent/EP0199160B1/en not_active Expired
- 1986-04-04 DE DE8686104603T patent/DE3687077T2/de not_active Expired - Fee Related
- 1986-04-18 US US06/853,572 patent/US5146551A/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| EP0199160A2 (en) | 1986-10-29 |
| US5146551A (en) | 1992-09-08 |
| DE3687077T2 (de) | 1993-04-15 |
| JPS61249088A (ja) | 1986-11-06 |
| EP0199160B1 (en) | 1992-11-11 |
| CA1247246A (en) | 1988-12-20 |
| DE3687077D1 (de) | 1992-12-17 |
| EP0199160A3 (en) | 1990-06-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0360155B1 (en) | Image transformation method and device | |
| EP0356103B1 (en) | Scan-conversion process and processor | |
| US4529978A (en) | Method and apparatus for generating graphic and textual images on a raster scan display | |
| JPH0126072B2 (ja) | ||
| US20220366621A1 (en) | Systems for Generating Anti-Aliased Vector Objects | |
| EP0344686B1 (en) | Clipping process and processor | |
| JPH0366675B2 (ja) | ||
| JPH03119387A (ja) | デジタル活字面の輪郭を形成する方法およびその装置 | |
| CA1200025A (en) | Graphic and textual image generator for a raster scan display | |
| JP2770582B2 (ja) | 図形塗潰し装置 | |
| JPS60173676A (ja) | 図形塗りつぶし方式 | |
| JPH07120427B2 (ja) | グラフイツクス処理システム | |
| US5077681A (en) | System for source image transformation | |
| JP3129717B2 (ja) | 画像処理装置および画像処理方法 | |
| JPS61286895A (ja) | グラフイツク装置における直線描画方式 | |
| US5305431A (en) | Method and system for rendering polygons on a raster display | |
| JPS6274164A (ja) | 走査型ディスプレイ装置における多角形ぬりつぶし装置 | |
| JPS6326773A (ja) | 図形情報の表示処理方法 | |
| JPS61212895A (ja) | 多角形内部の領域を塗りつぶし処理する方法 | |
| JP2634906B2 (ja) | 画像処理方法 | |
| JP2794446B2 (ja) | エレメント別に文字を構成したアウトラインフォントの塗りつぶし方法および装置 | |
| JPS5836350B2 (ja) | パタ−ン表示方式 | |
| JPS61159690A (ja) | Ｃｒｔディスプレイ装置における半透明図形描画回路 | |
| Alavala | Computer Graphics | |
| JPS623295A (ja) | 表示画像補償方法 |