JPS6231481A - ベクトルクリツピング方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はグラフィックディスプレイ装置等の図形情報処
理装置において、線分の始終点データに基づき、この線
分のウィンドウとの境界点の座標値を得るためのベクト
ルクリッピング方式に関する。

（従来の技術〕 従来の図形情報処理装置では、２次元あるいは３次元空
間におけるスクリーン上の直線のクリッピング方式とし
て中点分割法が公知である。該中点分割法においては、
第６図に示す、ウィンドウ２と直線４との交点ＰＢの座
標値ｘｂ、ｙｂを次のような方法で求めている。

この場合、直線４の始点ｐ１と終点Ｐ２のＸ。

ｙ座標値は既知で、且つ、点ＰＢのＸかＹ座標のどちら
かが既知である。第６図の場合は、Ｘ座標値ｘｂが既知
であるため、図７のフローチャートでは点ＰＢのＸ座標
ｘｂが既知であるとしている。

まず、コンピュータは、直線４の中点ＰＣのｘｙ座標値
ｘＯ，ｙＯを次の（１）（２）式で演算する。

ｘｏ＝（ｘｌ＋ｘ２）÷２・・・・・・（１）式％式％
（２） 更に上記ｘＯから前記中点ＰＣと点ＰＢとの間のＸ座標
軸上の距離ＢＢを演算する。

ＢＢ　＝ｘＯ−ｘｂ 次に、Ｘｉ＞Ｘ２を判断し、ＹＥＳであればＢＢにマイ
ナス１をかける。第６図の場合は。

ｘ　１　＜　ｘ　２なので、ｇＢはその正負の付帯が反
転されない。ＢＢが図示するようにプラスであれば ｘ２＝ｘ。

ｙ　２　＝　ｙ　Ｏ として、このｘ２．ｙ２を、上記（１）（２）式に代入
して、線分ＰＬ、ＰＣの中点ｐｃ’を求め、この中点Ｐ
Ｃ’とクリップ点ＰＢとのＸ座標軸上の距１ｉＢＢを求
める。これは、前に求めた中点をクリップ点を含む線分
の端部とすることであり、この端部とクリップ点を含む
線分の他端とを結ぶ線分の中点を次に求める。また、Ｂ
Ｂがマイナスであれば、ｘｌ＝ｘｏ、ｙｌ＝ｙｏとして
、このｘｌ。

ｙｌを上記（１）（２）式に代入して、前に求めた。中
点をクリップ点を含む線分の端部として、該端部とクリ
ップ点を含む線分の他端とを結ぶ線分の中点を求める。

上記の計算をくり返し行うことによりＢＢ＝０となった
ときのｘｏ、ｙＯが求めるクリップ点のｘｙ座標値であ
る。

〔発明が解決しようとする問題点〕

整数計算によって前記中点分割法を用いてクリップ点を
求める場合、第３図のようにｄｙ　／　ｄ　ｘ　＞　１
のような直線に対しては、ｄｘが小さいため中点をくり
返し求めてゆくと、精度が悪くなってしまう。本発明は
、このような欠点を除去することを目的とするものであ
る。

〔問題点を解決する手段〕

上記目的を達成するため本発明は線分図形の面端のＸ’
ｌ＄標値及び該線分の、ウィンドウとの境界であるクリ
ップ点の、一方の座標軸上における値が既知である場合
において。

上記線分の両端間の一方の座標軸上における距離を拡大
して前記線分の前記他の座標軸に対する傾きを所定の値
に設定した後、該拡大した線分の中点を求め、該中点の
前記一方の座標軸上における値と前記線分拡大後におけ
る前記クリップ点の一方の座標軸上における値とを比較
し、両者が不一致のときは、前記中点と前記クリップ点
を含む側の線分の端部との中点を求めるとともに該中点
を前記拡大線分の他方の端部と成し、この動作を、求め
た中点の前記一方の座標軸上の値と前記クリップ点の前
記一方の座標軸上の値とが一致するまで行うことにより
、前記クリップ点の他の座標軸上の値を得るようにした
ものである。

以下に本発明の構成を添付図面に示す実施例を参照して
説明する。

第３図に示す線分り上の任意の一点（クリップ点ＰＢ）
のＹ座標値ｙｂを求める場合について説明する。

マイクロコンピュータのＣＰＵ６には被計算値として線
分名の始点座１１１ＰＩ　　（ｘｉ、ｙｌ）、終点座標
Ｐ２　（ｘ２．ｙ２）及びクリップ点のＸ座標ｘｂを、
記憶回路８，１０，１２゜１４．１６に入力する。求め
るのはクリップ点ＰＢのＹ座標ｙｂである。

記憶回路８，１０から比較回路１・８にｘｌ。

Ｘ２が入力され、ここで、ＸｌとＸ２が比較される（ス
テップ１）、ｘｌ＜ｘ２の場合は、Ｘｌのデータは、デ
ータ選択回路２０を経て。

ｘ１１記憶路２２に入力され、ｘ２は、データ選択回路
２４を経てＸ２記憶回路２６に入力される。一方、ｙｌ
は、記憶回路１２からデータ選択回路２８を経てｙＩ記
憶回路３０に入力され、ｙ２は、記憶回路１４からデー
タ選択回路３２を経てｙ２記憶回路３４に入力される。

一方、ｘ　ｌ　＞　ｘ　２の場合は、ｘｌはｘｌに、ｙ
ｌはｙ２に、ｘｌはｘｌに、ｙ２はｙｌにそれぞれ変換
される。即ち、計算の便宜上、線分名の始点と終点を入
れかえる。

具体的には、データ選択回路２０，２４，２８．３２の
制御により、ｘｌはｘ２記憶回路２６に入力されてｘｌ
として処理され、ｘｌは、〜ｘ１記憶回路２２に入力さ
れてＸｌとして処理される。更に、ｙｌはｙ２記憶回路
３４に入力されてｙ２として処理され、ｙ２はｙ１記憶
回路３０に入力されてｙｌとして処理される（ステップ
２）。

次に、演算回路３６は、ｄｘ＝ｘ２−ｘｉを演算し、演
算回路３８はｄｘｂ＝ｘｂ−ｘｉを演算し、演算回路４
０は、ａｙ＝７２−７１を演算する（以上ステップ３）
。ｄｘ、ｄは、ライン４８にＨｉｇｈの信号を出力し。

はライン５２にＨｉｇｈの信号を出力する。

制御回路５４は、ライン４８がＨｉｇｈのとき、データ
選択回路５６．５８を制御して。

演算回路６０．６２のデータ（ｄｘＸ２）。

（ｄｘｂＸ２）を記憶回路６４．６６にｄｘ。

ｄｘｂとして入力する。記憶回路６４に入力されたｄ　
ｘ　＝　２　ｄ　ｘは補数回路４２によって絶対値化さ
れ、比較回路４６シ；再び入力される。一方記憶回路３
４のデータｄｙは記憶回路６８及び補数回路４４を経て
比較回路４６に入力される。比較回路４６は、再び補数
同号を出力するにのようにして、ｄｘとｄｙｘ、ｄｘｂ
を２のｎ乗倍する。ここでｎはくあれば、ｄｘ＝２ｄｘ
、ｄｘｂ＝２ｄｘｂと＝　４　ｄ　ｘ　、　ｄ　ｘ　ｂ
　＝　４　ｄ　ｘ　ｂとする。更にｄｘ、ｄｘｂ＝＝　
（２のｎ乗）ｄｘｂとする。

上記線分えをＰＢ点を中心として第４図に示す如くＸ座
標方向に２のｎ乗倍拡大してもこの拡大によって求める
クリップ点ＰＢのＹ座標値ｙｂは、第４図から明らかな
ようにＹ座標軸上を移動しない６尚、第４図において、
ＰＢ点を不動点としたのは説明の便宜のためであり、実
際は、ｔ３ｘを、第３図上の２１点を基準として拡大す
れば、ＰＢ点も、その拡大倍数に応じてＸ座標軸上を移
動するが、この移動によって求めるクリップ点ＰＢ点の
ｙ座標値ｙｂが変化することはない。（２）ｎなったと
ころで、ライン５０．５２はＨｉ　ｇｈを出力し、制御
回路５４．７０の制御にょってデータ選択回路７２．７
４が作動され、記憶回路６４のデータｄｘが線分Ｌ′の
終点Ｘ２′として、記憶回路７６に入力されるとともに
（ステップ５）、記憶回路７８に線分え′の始点ｘｌ’
としてゼロ８ｏが入力されて、上記拡大線分え′のクリ
ップ点のＹ座標値を求める演算即ち中点分割法による計
算ロジックが作動される。

上記ｘ２’＝ｄｘ、ｘｌ’＝０の線分Ｌ′の図形は第５
図に図示される。第５図は、線分名・を中点分割する前
の、座標原点変換を表し、これにより、Ｌ′の初期状態
において、第５　　　　　　　　図から明らかなように
、 線分え″の始点のＸ座標値ｘ　１’＝ｘ　１−ｘ　１；
０ 線分え′の始点のＹ座標値ｙ１＝ｙｌ 線分し′の終点のＸ座標値ｘ２’＝２　　ｄＸ線分え′
の終点のＹ座標値ｙ　２＝Ｙ　２クリップ点ＰＢと線分
Ｌ′の始端ｘ１′との間のＸ座標値ｄｘｂ＝２　　ｄｘ
ｂ となる。

ここで、線分Ｌ′の中点ＰＣのｘ−ｙ座標値（ｘｏ、ｙ
ｏ）は、以下の式により求めることが ＸＯ＝　（Ｘ１’＋Ｘ２’）÷２＝　（０＋２　　ｄＸ
）÷２＝２　　ｄｘ÷２ ＹＯ＝　ＣＹＬ十Ｙ２）÷２ ＸＯは、第１図において、演算回路８０，８２により演
算され、記憶回路８４に記憶される。

一方、記憶回路８６．８８のデータ７１＋）’２に基づ
き、演算回路９０は、ｙｔ＋ｙ２＝＝Ｗを演算し、この
演算値を記憶回路９４に記憶させ、この記憶回路９４の
データＷに基づいて演算回路９４はＷ÷２を演算し、該
演算値ｙＯを記憶回路９６にセットする（ステップ６）
。次に、比較回路９８は、データｘＯとｄｘｂとを比較
する（ステップ７）。

ｘＯ＞ｄｘｂの場合、第５図中、Ｐｌを線分の始端ＰＣ
を線分の終端として、線分Ｐ１ｐｃの中点ｐｃ’を求め
る。即ち 記憶回路７８には、ｘｌ’＝０ 記憶回路８６にはｙ　ｔ−ｙ　を 記憶回路７６にはｘ２’＝２　　ｄｘ÷２記憶回路８８
にはｙ２＝　（ｙ　Ｉ−ｙ２）÷２が入力され（ステッ
プ８）。

ｘＯ＝　（ｘｌ’＋ｘ２’）÷２＝　（０＋２　　ｄＸ
÷２）÷２＝：２　　ｄｘ÷４ ｙＯ＝　（ｙｌ＋ｙ２）÷２ ＝　（ｙ　１＋　　（ｙ　１＋ｙ２）÷２〕÷２＝３ｙ
ｌ＋７２÷４ が演算回路８２．９４によって演算される（ステップ６
）。

ｘｏ＝ｄｘｂ即ち、ｘＯ−ｄｘｂ＝２　　ｄｘ÷４−ｄ
ｘｂがゼロとなったときのｘＯとｙＯの値がクリップ点
ＰＢのＸＹ座標値となる。

以上の動作を要約すると、線分の中点を求め、この中点
のＸ座標値がクリップ点のＸ座標値ｄｘｂより大である
ときは、求めた中点を線分の終端とし、クリップ点を含
む側の線分の一端を始端とする線分の中点を求め、この
中点のＸ座標値がｄｘｂと一致するまでこの作業をくり
返して、線分を細分割してゆくことである。

ｘ　Ｏ＜　ｄ　ｘ　ｂの場合には（ステップ９）、記憶
回路７８には、ｘＬ’＝２　　ｄｘ÷２記憶回路８６に
はｙ　１＝　（ｙ　１＋ｙ２）÷２記憶回路７６にはｘ
２’＝２　　ｄｘ 記憶回路８８にはＹ　２＝７２ が入力され。

ｘｏ＝＝　（Ｘ１’十Ｘ２’）÷２ ＝＝（２ｒｌ　ｄｘ÷２＋２”ｄｘ）÷２ｙｏ＝　（ｙ
ｌ＋ｙ２）÷２ ＝　　（Ｙ１＋７２）÷２＋ｙ２　÷２が演算回路８２
．９４によって演算される。

ｘｏ−’ｄｘｂがゼロとなったところで、記憶回路８４
．９６の記憶データｘＯ，ｙＯの値は、線分尤のクリッ
プ点ＰＢのＸＹ座標値（ｘｂ、ｙｂ）としてＣＰＵ６に
入力される。

上記ｙｏのコンピュータによる整数計算において、ｙｔ
＋７２を１７２にすると端数の切り捨てがおこるので、
端数（最下位の１ビツトがオン）が２回でると次にｙＯ
を求めるとき、１／２する前に１を加えて補正する（ス
テップ６）。これを以下に説明する。

記憶回路９２の最終桁が奇数の場合（第１回目）、論理
積回路１０２は１７１　ＩＩを出力する。

演算回路１０４によるｉ　ｃ＝　ｉ　ｃ＋　（Ｗ　ａｎ
ｄｌ）の式により、記憶回路１０６は１を記憶する。記
憶回路９２の最終桁が２回目の奇数の状態になると、演
算回路１０４は２を出力し、記憶回路１０６に２が入力
される。これにより演算回路１０８は１を演算し、これ
を記憶回路１１０に入力するとともに、演算回路９０に
ｉ　ｄ＝１が供給される。このとき、演算回路１１４は
（ｉｃ−２ｉｄ）の式から、ゼロを記憶回路１０Ｇに入
力して、ｉ　ｃ　＝　０となる。このようにして、記憶
回路９２に端数が２回出ると１次にｙＯを求めるとき、
ｙ１＋ｙ２を１／２する前に演算回路９０に１ｄ＝１が
供給される。

〔効果〕

本発明は上述の如く構成したので従来の中点分割法に比
し、計算速度をあまり損うことなく計算精度を向上させ
ることができ、しかも、論理と構造が簡単なため、他の
手法よりも高速でローコストを実現することができる効
果が存する。

【図面の簡単な説明】

第１図はブロック回路図であり、コンピュータの一般的
制御線を省略したもの、第２図はフローチャート、第３
図は説明図、第４図は説明図、第５図は説明図、第６図
は従来技術の説明図、第７図は同、フローチャートであ
る。 第３図 Ｙ 第５図 第６図 Ｙ 第７図

Claims (1)

【特許請求の範囲】
1. （１）線分図形の両端のＸＹ座標値及び該 線分の、ウィンドウとの境界であるクリップ点の、一方
   の座標軸上における値が既知である場合において、上記
   線分の両端間の一方の座標軸上における距離を拡大して
   前記線分の前記他の座標軸に対する傾きを所定の値に設
   定した後、該拡大した線分の中点を求め、該中点の前記
   一方の座標軸上における値と前記線分拡大後における前
   記クリップ点の一方の座標軸上における値とを比較し、
   両者が不一致のときは、前記中点と前記クリップ点を含
   む側の線分の端部との中点を求めるとともに該中点を前
   記拡大線分の他方の端部と成し、この動作を、求めた中
   点の前記一方の座標軸上の値と前記クリップ点の前記一
   方の座標軸上の値とが一致するまで行うことにより、前
   記クリップ点の他の座標軸上の値を得るようにしたこと
   を特徴とするベクトルクリッピング方式。