JPH0750508B2 - 描画処理装置 - Google Patents
描画処理装置Info
- Publication number
- JPH0750508B2 JPH0750508B2 JP60072610A JP7261085A JPH0750508B2 JP H0750508 B2 JPH0750508 B2 JP H0750508B2 JP 60072610 A JP60072610 A JP 60072610A JP 7261085 A JP7261085 A JP 7261085A JP H0750508 B2 JPH0750508 B2 JP H0750508B2
- Authority
- JP
- Japan
- Prior art keywords
- segment
- horizontal
- area
- vertical
- calculation result
- 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 - Fee Related
Links
Classifications
-
- 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/36—Control arrangements or circuits for visual indicators common to cathode-ray tube indicators and other visual indicators characterised by the display of a graphic pattern, e.g. using an all-points-addressable [APA] memory
- G09G5/39—Control of the bit-mapped memory
- G09G5/393—Arrangements for updating the contents of the bit-mapped memory
-
- 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
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computer Hardware Design (AREA)
- Image Generation (AREA)
- Digital Computer Display Output (AREA)
Description
【発明の詳細な説明】 〔発明の利用分野〕 本発明は描画処置装置に係り、特に水平あるいは垂直線
分の高速クリッピング処理に好適な描画機能を有する描
画処理装置に関する。
分の高速クリッピング処理に好適な描画機能を有する描
画処理装置に関する。
従来の描画処理装置は特開昭58−203550号公報に開示さ
れるように、例えば直線の描画を例にとると、第１図に
示した直線発生のBresenhamのアルゴリズム（文献Algor
ithm for computer control of a digital plotter:Bre
senham,J.E,IBM System Joarnal,Vol.4,No.1,pp.25〜30
（1965））を用いて、描画すべき線分を▲▼とし、
この線分の傾きを０゜〜45゜の範囲とするＡ点の次のプ
ロットすべき点は右横か右上のいずれかとなることに注
目した▲▼に至る各ベット点列の座標を順次発生さ
せている。
れるように、例えば直線の描画を例にとると、第１図に
示した直線発生のBresenhamのアルゴリズム（文献Algor
ithm for computer control of a digital plotter:Bre
senham,J.E,IBM System Joarnal,Vol.4,No.1,pp.25〜30
（1965））を用いて、描画すべき線分を▲▼とし、
この線分の傾きを０゜〜45゜の範囲とするＡ点の次のプ
ロットすべき点は右横か右上のいずれかとなることに注
目した▲▼に至る各ベット点列の座標を順次発生さ
せている。
このようにして発生した座標点列を全てプロットするこ
とにより描画処理が終了する処理装置は特に問題はない
が、一般には、第２図の斜線部で示すようにあらかじめ
描画してよい任意サイズの矩形領域が定められ、この領
域内に入る座標点列のみをプロットし、発生した座標が
領域外の場合にはプロットを禁止する処理、すなわちク
リッピング処理が要求される。このクリッピング処理を
行なう手法としては、例えば特開昭58−203550号公報で
示されるように、発生した座標点Ｐの２次元座標（xi,y
i）と描画可矩形領域の位置情報LX,TY,RX,BYより４ビッ
トの領域コードを生成し、４ビットのすべてが０であれ
ば座標点Ｐをプロットし、それ以外の時はプロットを禁
止する方法が行われている。この方法を実現する回路
は、例えば第３図に示す構成をしており、４ビットの領
域コードの意味は、TCは座標点,xi,yiが領域の上にある
ことを、BCは領域の下にあることを、LCは領域の左にあ
ることを、RCは領域の右にあることを示すフラグであ
る。
とにより描画処理が終了する処理装置は特に問題はない
が、一般には、第２図の斜線部で示すようにあらかじめ
描画してよい任意サイズの矩形領域が定められ、この領
域内に入る座標点列のみをプロットし、発生した座標が
領域外の場合にはプロットを禁止する処理、すなわちク
リッピング処理が要求される。このクリッピング処理を
行なう手法としては、例えば特開昭58−203550号公報で
示されるように、発生した座標点Ｐの２次元座標（xi,y
i）と描画可矩形領域の位置情報LX,TY,RX,BYより４ビッ
トの領域コードを生成し、４ビットのすべてが０であれ
ば座標点Ｐをプロットし、それ以外の時はプロットを禁
止する方法が行われている。この方法を実現する回路
は、例えば第３図に示す構成をしており、４ビットの領
域コードの意味は、TCは座標点,xi,yiが領域の上にある
ことを、BCは領域の下にあることを、LCは領域の左にあ
ることを、RCは領域の右にあることを示すフラグであ
る。
一方、図形発生のアルゴリズムで第１図に示したBresen
ham法よりも高速処理の可能なアルゴリズムとして、第
４図に示した水平方向（あるいは垂直方向）に連続する
座標点列を水平セグメント（あるいは垂直セグメント）
としてとらえて、そのセグメントが開始する座標とセグ
メント長（これをラン数と呼ぶ）を与えることで図形を
描画する方法がある。このアルゴリズムは、第４図のよ
うに傾きが45゜よりも小さい場合には、ｙ座標の変化Δ
Ｙがｘ座標の変化ΔＸよりも小さいため、ｙ座標１格子
ピッチあたりのｘ座標の変化量をセグメントのラン数と
することでｘ座標の変化量ΔＸをｙ座標の各格子ピッチ
に分配する方法である。１格子ピッチあたりの変化量
は、一般には、整数とならないため、整数部をＲ、小数
部をΔＲとすると、第４図に示すような式になる。直線
の両端では変化量を半分に分けるためΔX2ΔＹで割った
値を用いている。ラン数は整数でなければならないた
め、ΔＲが０でない場合にＲをラン数とすると誤差がで
る。この誤差の積み重ねが１を越えた時にラン数をＲ＋
１とし、それ以外ではラン数をＲとすることで、第４図
に示す斜線の描画が実現する。
ham法よりも高速処理の可能なアルゴリズムとして、第
４図に示した水平方向（あるいは垂直方向）に連続する
座標点列を水平セグメント（あるいは垂直セグメント）
としてとらえて、そのセグメントが開始する座標とセグ
メント長（これをラン数と呼ぶ）を与えることで図形を
描画する方法がある。このアルゴリズムは、第４図のよ
うに傾きが45゜よりも小さい場合には、ｙ座標の変化Δ
Ｙがｘ座標の変化ΔＸよりも小さいため、ｙ座標１格子
ピッチあたりのｘ座標の変化量をセグメントのラン数と
することでｘ座標の変化量ΔＸをｙ座標の各格子ピッチ
に分配する方法である。１格子ピッチあたりの変化量
は、一般には、整数とならないため、整数部をＲ、小数
部をΔＲとすると、第４図に示すような式になる。直線
の両端では変化量を半分に分けるためΔX2ΔＹで割った
値を用いている。ラン数は整数でなければならないた
め、ΔＲが０でない場合にＲをラン数とすると誤差がで
る。この誤差の積み重ねが１を越えた時にラン数をＲ＋
１とし、それ以外ではラン数をＲとすることで、第４図
に示す斜線の描画が実現する。
アルゴリズムの理解を助けるため、第４図の例を具体的
に説明すると、ΔＸ＝22,ΔＹ＝５であるため、Ｒは
４、ΔＲは0.4と求められる。端ではさらに２で割った
値を用いるためｒは２、Δｒは0.2となる。この結果、
最初のセグメントのラン数は２であるが、開始点は含め
ていないため、この場合だけ特別に１の加えラン数は３
となる。この時の誤差はΔｒすなわち0.2となる。次の
セグメントのラン数は、誤差がΔｒ＋ΔＲで0.6となり
これは１より小さいためＲすなわち４となる。３番目の
セグメントは、誤差が0.6＋ΔＲで１となるので、ラン
数はＲ＋１すなわち５となる。ここで誤差は、１を越え
た分はラン数に反映するため、小数部すなわち０を誤差
とする。以下同様の手順で、終了点までくり返すことで
第４図に示す結果が得られる。以上の手順に示したよう
に、このアルゴリズムでは、個々の座標を求めるBresen
hamのアルゴリズムと異なり、セグメントを単位として
算出するため、座標算出の効率が良くなっている。
に説明すると、ΔＸ＝22,ΔＹ＝５であるため、Ｒは
４、ΔＲは0.4と求められる。端ではさらに２で割った
値を用いるためｒは２、Δｒは0.2となる。この結果、
最初のセグメントのラン数は２であるが、開始点は含め
ていないため、この場合だけ特別に１の加えラン数は３
となる。この時の誤差はΔｒすなわち0.2となる。次の
セグメントのラン数は、誤差がΔｒ＋ΔＲで0.6となり
これは１より小さいためＲすなわち４となる。３番目の
セグメントは、誤差が0.6＋ΔＲで１となるので、ラン
数はＲ＋１すなわち５となる。ここで誤差は、１を越え
た分はラン数に反映するため、小数部すなわち０を誤差
とする。以下同様の手順で、終了点までくり返すことで
第４図に示す結果が得られる。以上の手順に示したよう
に、このアルゴリズムでは、個々の座標を求めるBresen
hamのアルゴリズムと異なり、セグメントを単位として
算出するため、座標算出の効率が良くなっている。
従って、このような水平または垂直セグメントを単位と
して座標を算出する方法を図形発生アルゴリズムとして
採用した場合の出力データは座標点Ｐ（xi,yi）、ラン
数Ｒ、及び方向係数Ｄ（水平セグメントor垂直セグメン
トかの区別）となる。この結果、第４図の例では、Bres
enhamのアルゴリズムが22回座標計算を必要とするのが
６回で済み、描画処理も水平線または垂直線のみを描画
すればよいため、高速化が図れる。しかしながら、第２
図に示したように、画面の一部のみが描画できる場合
は、第３図に示した座標点毎のクリップ判定を行うと、
描画処理で、水平セグメントまたは垂直セグメントを点
列の描画へ変換し、一点ずつクリップ判定をすることと
なり、結果として、一点ずつの描画を行うBresenhamの
アルゴリズムと同じく22回の座標点の描画処理となり描
画処理性能は向上しないという欠点を有している。
して座標を算出する方法を図形発生アルゴリズムとして
採用した場合の出力データは座標点Ｐ（xi,yi）、ラン
数Ｒ、及び方向係数Ｄ（水平セグメントor垂直セグメン
トかの区別）となる。この結果、第４図の例では、Bres
enhamのアルゴリズムが22回座標計算を必要とするのが
６回で済み、描画処理も水平線または垂直線のみを描画
すればよいため、高速化が図れる。しかしながら、第２
図に示したように、画面の一部のみが描画できる場合
は、第３図に示した座標点毎のクリップ判定を行うと、
描画処理で、水平セグメントまたは垂直セグメントを点
列の描画へ変換し、一点ずつクリップ判定をすることと
なり、結果として、一点ずつの描画を行うBresenhamの
アルゴリズムと同じく22回の座標点の描画処理となり描
画処理性能は向上しないという欠点を有している。
本発明の目的は、上記欠点を解決するもので、図明描
画、任意サイズのパターンをあらかじめ定められた描画
可領域内にかかる部分のみを高速に描画するクリッピン
グ処理を高速に実現する描画処理装置を提供することに
ある。
画、任意サイズのパターンをあらかじめ定められた描画
可領域内にかかる部分のみを高速に描画するクリッピン
グ処理を高速に実現する描画処理装置を提供することに
ある。
上記目的を達成するために、本発明は描画処理装置の描
画点列は必ず水平線分あるいは垂直線分の集合としてと
らえることができることに着目し、描画処理を描画点の
プロットから、始点座標Ｐ（x,y）、ランレングス長
Ｒ、方向DiR（水平又は垂直）という線分要素に分解
し、これにクリッピング処理を施して高速に描画する。
画点列は必ず水平線分あるいは垂直線分の集合としてと
らえることができることに着目し、描画処理を描画点の
プロットから、始点座標Ｐ（x,y）、ランレングス長
Ｒ、方向DiR（水平又は垂直）という線分要素に分解
し、これにクリッピング処理を施して高速に描画する。
即ち、文字、図形、画像等を描画する描画処理装置にお
いて、被描画データを水平方向に連続する長さriピクセ
ルの水平セグメント要素あるいは、垂直方向に連続する
長さri′ピクセルの垂直セグメント要素、各水平あるい
は垂直セグメント要素の始点となる座標値Ｐ（xi,yi）
及び各セグメントの方向係数（右→左、左→右、上→
下、下→上）を算出する第１の手段と、被描画データを
描画する領域の位置と領域サイズに基づいて描画可領域
の境界座標値を算出する第２の手段と、第２の手段の算
出結果に基づいて、第１の算出結果である各セグメント
の長さ、各セグメント要素の始点となる座標値Ｐ、各セ
グメントの方向係数により各セグメント要素毎にセグメ
ントの有効となる部分と無効となる部分を算出する第３
の手段と、第１の手段の算出結果と第３の手段の算出結
果に基づいて、有効となった水平あるいは垂直セグメン
トの部分を描画する第４の手段とを備えたことを特徴と
する。
いて、被描画データを水平方向に連続する長さriピクセ
ルの水平セグメント要素あるいは、垂直方向に連続する
長さri′ピクセルの垂直セグメント要素、各水平あるい
は垂直セグメント要素の始点となる座標値Ｐ（xi,yi）
及び各セグメントの方向係数（右→左、左→右、上→
下、下→上）を算出する第１の手段と、被描画データを
描画する領域の位置と領域サイズに基づいて描画可領域
の境界座標値を算出する第２の手段と、第２の手段の算
出結果に基づいて、第１の算出結果である各セグメント
の長さ、各セグメント要素の始点となる座標値Ｐ、各セ
グメントの方向係数により各セグメント要素毎にセグメ
ントの有効となる部分と無効となる部分を算出する第３
の手段と、第１の手段の算出結果と第３の手段の算出結
果に基づいて、有効となった水平あるいは垂直セグメン
トの部分を描画する第４の手段とを備えたことを特徴と
する。
以下、本発明の一実施例を図面を用いて詳細に説明す
る。
る。
まず、第５図により本発明の基本原理を説明する。
例えば点Ｐ（xi,yi）から水平方向にラン長riをもつ水
平セグメントと描画可領域（すなわち、クリッピング領
域）との関係は第５図に示した如く５種類に分類され
る。すなわち、 与えられた水平セグメントは全て描画不要となるも
の。（Ｐ（x1,y1）,r1） 与えられた水平セグメントの後半の部分が描画可領域
に存在し、さらに後半の部分セグメント全てを描画して
良いもの。（Ｐ（x2,y2）,r2） 与えられた水平セグメントの後半の部分が描画可領域
に存在し、さらに後半の部分セグメントの中の前半の部
分のみが描画対象となるもの。（Ｐ（x3,y3）,r3） 与えられた水平セグメントは全て描画対象となるも
の。（Ｐ（x4,y4）,r4） 与えられた水平セグメントの前半の部分のみ描画対象
となるもの（Ｐ（x5,y5）,r5） 以上の〜の５種類の関係を利用することにより、例
えば第４図に示したアルゴリズムで算出したセグメント
の位置Ｐ（xi,yi）及びラン数riと描画可領域の位置と
サイズ情報をもとに、ラン数riのうちの描画しないでス
キップするラン数si、描画するラン数Ri（ただし、ここ
でSiとRiの間にはSi＋Ri≦riの関係がある）を算出す
る。
平セグメントと描画可領域（すなわち、クリッピング領
域）との関係は第５図に示した如く５種類に分類され
る。すなわち、 与えられた水平セグメントは全て描画不要となるも
の。（Ｐ（x1,y1）,r1） 与えられた水平セグメントの後半の部分が描画可領域
に存在し、さらに後半の部分セグメント全てを描画して
良いもの。（Ｐ（x2,y2）,r2） 与えられた水平セグメントの後半の部分が描画可領域
に存在し、さらに後半の部分セグメントの中の前半の部
分のみが描画対象となるもの。（Ｐ（x3,y3）,r3） 与えられた水平セグメントは全て描画対象となるも
の。（Ｐ（x4,y4）,r4） 与えられた水平セグメントの前半の部分のみ描画対象
となるもの（Ｐ（x5,y5）,r5） 以上の〜の５種類の関係を利用することにより、例
えば第４図に示したアルゴリズムで算出したセグメント
の位置Ｐ（xi,yi）及びラン数riと描画可領域の位置と
サイズ情報をもとに、ラン数riのうちの描画しないでス
キップするラン数si、描画するラン数Ri（ただし、ここ
でSiとRiの間にはSi＋Ri≦riの関係がある）を算出す
る。
第６図は本発明の一実施例を実現する描画処理装置の構
成を示すブロック図である。第６図において、１は描画
可領域設定部、２は水平セグメントあるいは垂直セグメ
ントに対する要素算出部、３は水平セグメントあるいは
垂直セグメントに対するクリップ判定部、４は描画処理
部、５は例えばCRTのビデオメモリを示す。
成を示すブロック図である。第６図において、１は描画
可領域設定部、２は水平セグメントあるいは垂直セグメ
ントに対する要素算出部、３は水平セグメントあるいは
垂直セグメントに対するクリップ判定部、４は描画処理
部、５は例えばCRTのビデオメモリを示す。
次に、第６図に示した描画処理装置の動作例を説明す
る。描画可領域設定部１は与えられた描画可領域の位置
情報（例えば矩形領域の左上コーナーの座標）とサイズ
情報から第５図に示したＸ軸上の座標値LX,RX及びＹ軸
上の座標値TY,BYを生成し、クリップ判定部３へ出力す
る。要素算出部２は例えばベクトル描画の場合には、第
４図に示したアルゴリズムにより線分の構成要素となる
水平セグメントあるいは垂直セグメント成分及び線パタ
ーンデータを生成するセグメントデータの算出部であ
る。また要素算出部２は例えば文字フォント描画時には
各ラスタの位置及び文字フォントの横幅、フォントのパ
ターンデータをとり出す部分となる。要素算出部２によ
って算出されたセグメント要素の始点座標値Ｐ（xi,
yi）、ラン数ri、セグメントの方法係数DiRi（これはラ
ンが水平で右→左、左→右かあるいは垂直で上→下なの
か下→上なのかの区分を与える）とラン数に対応するパ
ターンデータDATAiを生成しクリップ判定部３へ出力す
る。クリップ判定部３は描画可領域設定部１及び要素算
出部２から与えられた各入力データをもとに与えられた
セグメント要素Ｐ（xi,yi）,riの始点位置Ｐ（xi,yi）
から描画対象とならないラン数の値Si及び描画対象とな
るラン数の値Riを第５図に示す５種類の分類に従って算
出し、これらの出力を描画処理部４へ印加する。描画処
理部４は、要素算出部２及びクリップ判定部３の出力で
あるＰ（xi,yi）DiRi,Si,Ri及びDATAiをもとに例えばビ
デオメモリ５の指定座標値に対応するメモリ上の物理ア
ドレスを生成してRiで与えられた部分に対応するパター
ンデータの描画を行なう。
る。描画可領域設定部１は与えられた描画可領域の位置
情報（例えば矩形領域の左上コーナーの座標）とサイズ
情報から第５図に示したＸ軸上の座標値LX,RX及びＹ軸
上の座標値TY,BYを生成し、クリップ判定部３へ出力す
る。要素算出部２は例えばベクトル描画の場合には、第
４図に示したアルゴリズムにより線分の構成要素となる
水平セグメントあるいは垂直セグメント成分及び線パタ
ーンデータを生成するセグメントデータの算出部であ
る。また要素算出部２は例えば文字フォント描画時には
各ラスタの位置及び文字フォントの横幅、フォントのパ
ターンデータをとり出す部分となる。要素算出部２によ
って算出されたセグメント要素の始点座標値Ｐ（xi,
yi）、ラン数ri、セグメントの方法係数DiRi（これはラ
ンが水平で右→左、左→右かあるいは垂直で上→下なの
か下→上なのかの区分を与える）とラン数に対応するパ
ターンデータDATAiを生成しクリップ判定部３へ出力す
る。クリップ判定部３は描画可領域設定部１及び要素算
出部２から与えられた各入力データをもとに与えられた
セグメント要素Ｐ（xi,yi）,riの始点位置Ｐ（xi,yi）
から描画対象とならないラン数の値Si及び描画対象とな
るラン数の値Riを第５図に示す５種類の分類に従って算
出し、これらの出力を描画処理部４へ印加する。描画処
理部４は、要素算出部２及びクリップ判定部３の出力で
あるＰ（xi,yi）DiRi,Si,Ri及びDATAiをもとに例えばビ
デオメモリ５の指定座標値に対応するメモリ上の物理ア
ドレスを生成してRiで与えられた部分に対応するパター
ンデータの描画を行なう。
第７図は、描画処理装置におけるセグメント要素のクリ
ップ判定部３の動作例について、水平セグメント（但
し、方向係数DiRiは左→右の場合）を例にとった場合の
詳細な判定処理動作を示すフローチャートである。
ップ判定部３の動作例について、水平セグメント（但
し、方向係数DiRiは左→右の場合）を例にとった場合の
詳細な判定処理動作を示すフローチャートである。
第７図において、クリップ判定部３の動作はまず、与え
られたセグメントの始点Ｐ（xi,yi）のＹ軸座標値yiがT
Y≦yi≦BYかの判別の行ない（702,704）、もしこの条件
に違反していれば描画処理不要（760）、すなわち、Si
＝０、Ri＝０を出力する。次にTY≦yi≦BYを満足してい
れば、与えられた水平セグメントriの前半が描画対象と
なるか後半が描画対象となるのかの判別を行なうため、
セグメントの始点xiと描画可領域の左側を境界座標LXと
の大小比較を行ない（705,706）、LX≧xiならばセグメ
ントの後半が描画対象の部分セグメントになる可能性が
あると判定し、さらに、描画対象とならないラン数とセ
グメントのラン数との大小関係の比較を行い（729、73
0）描画するかしないかを判定する。LX＜xiならばセグ
メント全体が描画対象になる可能性がある、あるいは前
半が描画対象の部分セグメントになる可能性があると判
定し、描画するラン数が正であるか比較することで（72
7）描画するかしないかを判定する。同様にしてセグメ
ントの終点となるＸ座標（xi＋ri）と描画可領域の右側
の境界座標RXとの大小関係の比較を行ない（715,74
0）、描画すべきセグメントのランの開始位置Si、描画
するラン数Riの算出を行なう（710,720,725,735,745,75
0）。
られたセグメントの始点Ｐ（xi,yi）のＹ軸座標値yiがT
Y≦yi≦BYかの判別の行ない（702,704）、もしこの条件
に違反していれば描画処理不要（760）、すなわち、Si
＝０、Ri＝０を出力する。次にTY≦yi≦BYを満足してい
れば、与えられた水平セグメントriの前半が描画対象と
なるか後半が描画対象となるのかの判別を行なうため、
セグメントの始点xiと描画可領域の左側を境界座標LXと
の大小比較を行ない（705,706）、LX≧xiならばセグメ
ントの後半が描画対象の部分セグメントになる可能性が
あると判定し、さらに、描画対象とならないラン数とセ
グメントのラン数との大小関係の比較を行い（729、73
0）描画するかしないかを判定する。LX＜xiならばセグ
メント全体が描画対象になる可能性がある、あるいは前
半が描画対象の部分セグメントになる可能性があると判
定し、描画するラン数が正であるか比較することで（72
7）描画するかしないかを判定する。同様にしてセグメ
ントの終点となるＸ座標（xi＋ri）と描画可領域の右側
の境界座標RXとの大小関係の比較を行ない（715,74
0）、描画すべきセグメントのランの開始位置Si、描画
するラン数Riの算出を行なう（710,720,725,735,745,75
0）。
第７図のフローチャートによれば、描画処理不要（76
0）へ分岐する処理が第５図に示す５種類の分類のうち
のとして分類される場合であり、725の処理へ行くの
がとして分類される場合であり、720のうち727の判定
で790の描画処理へ行くのがとして分類される場合で
あり、750の処理へ行くのがとして分類される場合で
あり、745の処理へ行くのがとして分類される場合で
ある。
0）へ分岐する処理が第５図に示す５種類の分類のうち
のとして分類される場合であり、725の処理へ行くの
がとして分類される場合であり、720のうち727の判定
で790の描画処理へ行くのがとして分類される場合で
あり、750の処理へ行くのがとして分類される場合で
あり、745の処理へ行くのがとして分類される場合で
ある。
本実施例では、水平セグメントの場合について詳しく説
明したが、垂直セグメントの処理も同様であり、ｘ座標
の処理とｙ座標の処理を入れかえればよい。すなわち、
第７図でTYをLXに、BYをRXに、yiをxiに置きかえ、LXを
TYに、RXをBYに、xiをyiに置きかえれば、垂直セグメン
トの処理を示すフローチャートとなる。
明したが、垂直セグメントの処理も同様であり、ｘ座標
の処理とｙ座標の処理を入れかえればよい。すなわち、
第７図でTYをLXに、BYをRXに、yiをxiに置きかえ、LXを
TYに、RXをBYに、xiをyiに置きかえれば、垂直セグメン
トの処理を示すフローチャートとなる。
次に描画処理装置全体の動作例について説明する。描画
処理装置は、あらかじめ外部から描画領域データが与え
られており、このデータをもとに描画可領域設定部１は
座標データTY,BY,LX,RXを出力する。しかるのちに、描
画要求を要素算出部２に与えることで、要素算出部２は
例えば直線描画であれば、第４図に示したアルゴリズム
により、１番目の座標xi,yi、ラン長ri、方向係数DiRi
で示される水平セグメントまたは垂直セグメントのデー
タをクリップ判定部３及び描画処理部４に出力する。ク
リップ判定部３は、第７図のフローチャートで示したク
リップ判定処理を実行し、描画不要の場合は直ちに要素
算出部２にセグメントの描画終了を知らせる。描画不要
でない場合は、スキップラン長Si及びラン長Riを描画処
理部４に出力し、描画の起動をかける。描画処理部４は
与えられた各データをもとに、描画すべきラン長Riの部
分をビデオメモリ５に書き、しかるのちに要素算出部２
に描画終了を知らせる。要素算出部２は描画終了の報告
により次のセグメントの座標xi,yi、ラン長ri、方向係
数DiRiを算出し、前述の場合と同様にクリップ判定部３
及び描画処理部４にデータを出力する。この動作を要求
された全てのセグメントの描画が終了するまでくり返
し、全セグメントの描画が終了すると、要素算出部２の
上位に描画終了を知らせ、次の描画要求を待つ。
処理装置は、あらかじめ外部から描画領域データが与え
られており、このデータをもとに描画可領域設定部１は
座標データTY,BY,LX,RXを出力する。しかるのちに、描
画要求を要素算出部２に与えることで、要素算出部２は
例えば直線描画であれば、第４図に示したアルゴリズム
により、１番目の座標xi,yi、ラン長ri、方向係数DiRi
で示される水平セグメントまたは垂直セグメントのデー
タをクリップ判定部３及び描画処理部４に出力する。ク
リップ判定部３は、第７図のフローチャートで示したク
リップ判定処理を実行し、描画不要の場合は直ちに要素
算出部２にセグメントの描画終了を知らせる。描画不要
でない場合は、スキップラン長Si及びラン長Riを描画処
理部４に出力し、描画の起動をかける。描画処理部４は
与えられた各データをもとに、描画すべきラン長Riの部
分をビデオメモリ５に書き、しかるのちに要素算出部２
に描画終了を知らせる。要素算出部２は描画終了の報告
により次のセグメントの座標xi,yi、ラン長ri、方向係
数DiRiを算出し、前述の場合と同様にクリップ判定部３
及び描画処理部４にデータを出力する。この動作を要求
された全てのセグメントの描画が終了するまでくり返
し、全セグメントの描画が終了すると、要素算出部２の
上位に描画終了を知らせ、次の描画要求を待つ。
なお、本実施例の図形描画は直線について説明したが、
曲線についても同様に扱える。すなわち、曲線も部分部
分については直線と考えられ、水平セグメントと垂直セ
グメントの集合で表現できるため、曲線座標発生アルゴ
リズムで水平あるいは垂直セグメントを単位として描画
することで、同じクリップ判定が適用できる。即ち、図
形、文字、画像はセグメントの集合として考えられるの
でセグメントの分解の仕方を定義すれば、分解されたセ
グメントに対しては全く同じ手法を用いることできる。
例えばビットマップフォントは矩形（ｎドット幅、ｍ
列）で表現されるが、ｎドットの水平セグメントをｍ個
持つと考えて分解すれば良い。方向係数は左→右、座標
値Ｙ座標を１ずらせばよい。画像データも同様に矩形と
して扱えるので、同様の処理で行える。図形は、基本的
に線分の集合なので、同様に水平／垂直に分解すること
で扱える。
曲線についても同様に扱える。すなわち、曲線も部分部
分については直線と考えられ、水平セグメントと垂直セ
グメントの集合で表現できるため、曲線座標発生アルゴ
リズムで水平あるいは垂直セグメントを単位として描画
することで、同じクリップ判定が適用できる。即ち、図
形、文字、画像はセグメントの集合として考えられるの
でセグメントの分解の仕方を定義すれば、分解されたセ
グメントに対しては全く同じ手法を用いることできる。
例えばビットマップフォントは矩形（ｎドット幅、ｍ
列）で表現されるが、ｎドットの水平セグメントをｍ個
持つと考えて分解すれば良い。方向係数は左→右、座標
値Ｙ座標を１ずらせばよい。画像データも同様に矩形と
して扱えるので、同様の処理で行える。図形は、基本的
に線分の集合なので、同様に水平／垂直に分解すること
で扱える。
本実施例によれば、１回のクリッピング判別により、ラ
ン数ri個の座標点列全てについてのクリッピング処理が
可能となり、かつ、従来方式と比較し内部で大小比較判
別する回数はほぼ同一となるため、従来方式の約ri倍の
高速処理が可能となる。
ン数ri個の座標点列全てについてのクリッピング処理が
可能となり、かつ、従来方式と比較し内部で大小比較判
別する回数はほぼ同一となるため、従来方式の約ri倍の
高速処理が可能となる。
また、描画処理部に対する出力は、１点毎のプロット出
力要求ではなく、ラン数Ri個分について同時に描画する
出力要求となるために、描画処理部の処理効率も向上す
る。
力要求ではなく、ラン数Ri個分について同時に描画する
出力要求となるために、描画処理部の処理効率も向上す
る。
さらに、従来方式と比較し、ハードウェアの規模もほぼ
同等でよいため、コスト／パフォーマンスが著しく向上
する。
同等でよいため、コスト／パフォーマンスが著しく向上
する。
以上の説明から明らかなように、本発明によれば、水平
あるいは垂直に連続するラン数の単位でクリッピング判
別ができるため、従来の各座標毎にクリッピング判別を
する方式に比較してラン数ri倍の高速処理が可能とな
り、また、描画処理部の起動回数は従来方式では描画す
る座標点毎であったが、セグメントの個数分でよいため
に、描画速度が大幅に向上するという効果が得られる。
あるいは垂直に連続するラン数の単位でクリッピング判
別ができるため、従来の各座標毎にクリッピング判別を
する方式に比較してラン数ri倍の高速処理が可能とな
り、また、描画処理部の起動回数は従来方式では描画す
る座標点毎であったが、セグメントの個数分でよいため
に、描画速度が大幅に向上するという効果が得られる。
第１図は直線発生におけるBresenhamのアルゴリズムを
説明するための図、第２図は従来のクリッピング判別処
理を説明するための図、第３図は従来のクリッピング用
の論理演算回路の処理を説明するための図、第４図は直
線の発生を水平あるいいは垂直セグメント成分としてと
らえて発生するアルゴリズムの説明図、第５図は本発明
のクリッピング判別の基本原理を説明するための図、第
６図は本発明の一実施例の構成を示すブロック図、第７
図は本発明におけるクリップ判定部の詳細動作を示すフ
ローチャートである。 １……描画可領域設定部 ２……要素算出部、３……クリップ判定部 ４……描画処理部、５……ビデオメモリ
説明するための図、第２図は従来のクリッピング判別処
理を説明するための図、第３図は従来のクリッピング用
の論理演算回路の処理を説明するための図、第４図は直
線の発生を水平あるいいは垂直セグメント成分としてと
らえて発生するアルゴリズムの説明図、第５図は本発明
のクリッピング判別の基本原理を説明するための図、第
６図は本発明の一実施例の構成を示すブロック図、第７
図は本発明におけるクリップ判定部の詳細動作を示すフ
ローチャートである。 １……描画可領域設定部 ２……要素算出部、３……クリップ判定部 ４……描画処理部、５……ビデオメモリ
───────────────────────────────────────────────────── フロントページの続き (72)発明者 木村 光一 神奈川県横浜市戸塚区吉田町292番地 株 式会社日立製作所マイクロエレクトロニク ス機器開発研究所内 (72)発明者 桑原 禎司 神奈川県横浜市戸塚区吉田町292番地 株 式会社日立製作所マイクロエレクトロニク ス機器開発研究所内 (72)発明者 真茅 裕一 神奈川県秦野市堀山下１番地 株式会社日 立製作所神奈川工場内
Claims (2)
- 【請求項１】文字、図形、画像等を描画する描画処理装
置において、被描画データを水平方向に連続する長さri
ピクセルの水平セグメント要素、あるいは垂直方向に連
続する長さri′ピクセルの垂直セグメント要素の、該各
セグメントの長さ、該各セグメント要素の始点となる座
標値Ｐ（xi,yi）及び該各セグメントの方向係数（右→
左、左→右、上→下、下→上）を算出する第１の手段
と、前記被描画データを描画する領域の位置と領域サイ
ズに基づいて描画可領域の境界座標値を算出する第２の
手段と、前記第２の手段の算出結果に基づいて、前記第
１の手段の算出結果である各セグメントの長さ、各セグ
メント要素の始点となる座標値Ｐ、各セグメントの方向
係数により、各セグメント要素毎に描画対象となる部分
と描画対象とならない部分を算出する第３の手段と、前
記第１の手段の算出結果と前記第３の手段の算出結果に
基づいて、描画対象となった水平あるいは垂直セグメン
ト要素の部分を描画する第４の手段とを備えたことを特
徴とする描画処理装置。 - 【請求項２】前記第３の手段は、前記第１の手段の算出
結果であるセグメントの方向係数が水平（右→左あるい
は左→右）成分かあるいは垂直（上→下あるいは下→
上）成分かの区別と、前記第２の手段の算出結果である
Ｘ軸方向の境界座標値あるいはＹ軸方向の境界座標値に
基づいて、当該セグメントが描画可領域に全く関与しな
い成分であるか否かを判別するセグメント領域判定部
と、前記セグメント領域判定部により抽出されたセグメ
ントに対し、前記描画可領域に入る部分の判別、すなわ
ち局所判別を行い、有効となるセグメントの始点座標か
らの位置情報Si（水平方向の変位量Δxiあるいは、垂直
方向の変位量Δyi）及び該位置情報Siの位置から有効と
なるセグメント長Riの算出部とから成ること特徴とする
特許請求の範囲第１項の描画処理装置。
Priority Applications (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60072610A JPH0750508B2 (ja) | 1985-04-08 | 1985-04-08 | 描画処理装置 |
| KR1019860002122A KR940001880B1 (ko) | 1985-04-08 | 1986-03-21 | 묘화처리(描畵處理)의 방법 및 장치 |
| US06/848,459 US4849907A (en) | 1985-04-08 | 1986-04-07 | Draw processing method and apparatus |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60072610A JPH0750508B2 (ja) | 1985-04-08 | 1985-04-08 | 描画処理装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS61231677A JPS61231677A (ja) | 1986-10-15 |
| JPH0750508B2 true JPH0750508B2 (ja) | 1995-05-31 |
Family
ID=13494332
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP60072610A Expired - Fee Related JPH0750508B2 (ja) | 1985-04-08 | 1985-04-08 | 描画処理装置 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US4849907A (ja) |
| JP (1) | JPH0750508B2 (ja) |
| KR (1) | KR940001880B1 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9065286B2 (en) | 2005-07-12 | 2015-06-23 | Massachusetts Institute Of Technology | Wireless non-radiative energy transfer |
Families Citing this family (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS63245576A (ja) * | 1987-03-31 | 1988-10-12 | Toshiba Corp | 面図形クリツプ回路 |
| US5333263A (en) * | 1987-09-25 | 1994-07-26 | Minolta Camera Kabushiki Kaisha | Digital image processing apparatus |
| JPH01181173A (ja) * | 1988-01-14 | 1989-07-19 | Toshiba Corp | ベクトルフォント輪郭描画方式 |
| JP2634851B2 (ja) * | 1988-04-28 | 1997-07-30 | シャープ株式会社 | 画像処理装置 |
| US5202671A (en) * | 1989-10-24 | 1993-04-13 | International Business Machines Corporation | Pick function implementation in a parallel processing system |
| JPH0796311B2 (ja) * | 1990-01-30 | 1995-10-18 | キヤノン株式会社 | 罫線パターン生成装置及び罫線パターン出力方法 |
| US5542052A (en) * | 1991-03-04 | 1996-07-30 | Adobe Systems Incorporated | Applying traps to a printed page specified in a page description language format |
| JPH05292331A (ja) * | 1992-03-30 | 1993-11-05 | Internatl Business Mach Corp <Ibm> | ラン・レングス・コードのデコード方法、ビデオ・コントローラ、及びデータ処理システム |
| US5819278A (en) * | 1996-08-23 | 1998-10-06 | Adobe Systems Incorporated | Maintaining invalidation information in tiled image representations |
| JPH10143134A (ja) * | 1996-11-11 | 1998-05-29 | Hewlett Packard Co <Hp> | 文字の生成と記憶のための方法と装置 |
| JP4547906B2 (ja) * | 2003-12-19 | 2010-09-22 | ソニー株式会社 | 描画装置および描画方法、プログラム、並びに記録媒体 |
| DE102005023356A1 (de) * | 2005-05-20 | 2006-11-23 | Robert Bosch Gmbh | Verfahren zur Darstellung eines Objekts |
| JP4621617B2 (ja) * | 2006-03-28 | 2011-01-26 | 株式会社東芝 | 図形描画装置、図形描画方法、及びプログラム |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3639736A (en) * | 1969-11-19 | 1972-02-01 | Ivan E Sutherland | Display windowing by clipping |
| US4146925A (en) * | 1977-08-04 | 1979-03-27 | Smiths Industries, Inc. | Graphics generator |
| US4209832A (en) * | 1978-06-13 | 1980-06-24 | Chrysler Corporation | Computer-generated display for a fire control combat simulator |
| US4291380A (en) * | 1979-05-14 | 1981-09-22 | The Singer Company | Resolvability test and projection size clipping for polygon face display |
| US4412296A (en) * | 1981-06-10 | 1983-10-25 | Smiths Industries, Inc. | Graphics clipping circuit |
| US4586036A (en) * | 1983-02-28 | 1986-04-29 | Advanced Computer Concepts, Inc. | Graphics display systems |
-
1985
- 1985-04-08 JP JP60072610A patent/JPH0750508B2/ja not_active Expired - Fee Related
-
1986
- 1986-03-21 KR KR1019860002122A patent/KR940001880B1/ko not_active Expired - Fee Related
- 1986-04-07 US US06/848,459 patent/US4849907A/en not_active Expired - Lifetime
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9065286B2 (en) | 2005-07-12 | 2015-06-23 | Massachusetts Institute Of Technology | Wireless non-radiative energy transfer |
Also Published As
| Publication number | Publication date |
|---|---|
| JPS61231677A (ja) | 1986-10-15 |
| US4849907A (en) | 1989-07-18 |
| KR940001880B1 (ko) | 1994-03-10 |
| KR860008512A (ko) | 1986-11-15 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7945114B2 (en) | Image transform method for obtaining expanded image data, image processing apparatus and image display device therefore | |
| KR920001801B1 (ko) | 화상확대방법 및 장치 | |
| EP0360155B1 (en) | Image transformation method and device | |
| US5966136A (en) | Efficient method for clipping numerous objects against an arbitrary clipping path | |
| US4849907A (en) | Draw processing method and apparatus | |
| EP0592770B1 (en) | Method for filling of interior pixels within a polygon | |
| US5489920A (en) | Method for determining the optimum angle for displaying a line on raster output devices | |
| EP0344686A2 (en) | Clipping process and processor | |
| JP3037854B2 (ja) | 文字生成方法及びその装置 | |
| JP2828592B2 (ja) | カーニング処理方法 | |
| JPH01296389A (ja) | 図形処理方法及びその装置 | |
| JP3026706B2 (ja) | 画像処理装置 | |
| JP2634851B2 (ja) | 画像処理装置 | |
| JP2770582B2 (ja) | 図形塗潰し装置 | |
| JP3266905B2 (ja) | 図形処理装置 | |
| JPS63305478A (ja) | パタ−ン情報復元装置 | |
| JPH0769968B2 (ja) | クリップ領域内における直線描画方法 | |
| JP2562458B2 (ja) | コンピュータシステム用文字発生方法 | |
| JP4098870B2 (ja) | 文字拡大方法 | |
| JP2630843B2 (ja) | 直線描画方法及び装置 | |
| Šrámek | Fast ray-tracing of rectilinear volume data | |
| JP3196291B2 (ja) | 文字認識方法および装置 | |
| JP2962525B2 (ja) | テキストブロック認識方法 | |
| KR900009182B1 (ko) | 표시방법 및 표시장치 | |
| JPH09305160A (ja) | 文字生成装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |