• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:

    公开号:WO1987004546A1
    申请号:PCT/JP1987/000029
    申请日:1987-01-19
    公开日:1987-07-30
    发明作者:Mikio Yonekura
    申请人:Fanuc Ltd；
    IPC主号:G06T15-00
    专利说明:
    [0001] 明 柳 図形抽出方式 技 術 分 野
    [0002] 本発明は画面中の任意の図形を抽出する方式に孫り、 特に
    [0003] 3次元図形処理装置において画面上において指定された図形を 迅速に抽出するこ とができ る図形抽出方式に関するものである《 背 景 技 術
    [0004] 第 5図は 3次元図形処理装置を示したものであって、 1 は中 央処理装置 （ C P U ) 、 2 は C P U 1 と周辺回路とを接铙する バス、 3 は画面上に指定点を設定するためのボイ ンティ ングデ バイ スであって、 力 一ソル、 ジョ イ スティ ック ， ラ イ ト ペン等 からなる。 4 は 3次元画像デ一タを蓄えるセグメ ン トバッファ. 5 はセグメ ン トバッファ 4の画像デ一タを与えられた視点から 見たときの図形を表わすように座標変換する座標変換部、 6は 図形データを、 視点を中心として所定の視角を張る四角錐 （ビ ユーボリ ューム） に含まれるものに制限 （ク リ ッ ピング） する ク リ ッビング部、 7 はビューボリ ューム内の図形が表示器の酉 面に対応する定義面上に投影されるとおりの形状に図形データ を変形する投影処理部、 8は表示器上の図形の面を直線で埋め て面として表示するためのぬりつぶし部、 9 はぬりつぶし処理 のための直線を発生する直線発生部、 10は処理が終った図形デ ータを 1 フ レーム分保持するフ レームバッファ、 11は図形の奥 行き （ Z軸） 方向のデータを格鈉するデブスバッファ、 12は直 線発生部 9で発生した直線のデブス値と、 デブスバッファ 11に 設定されているデブス値とを比較する比較器、 13は直線データ のフ レームバッファ 10への書き込みを禁止するスィ ツチ、 14は 各図形の識別用データを記億するビックバッファ、 15はデブス バッファ 11の書き替えを禁止するスィ ツチである。
    [0005] 第 5図において、 C P U 1 はバス 2を介してセグメ ン トバッ ファ 4に蓄えられている 3次元の酉像データを読み出して、 座 標変換部 5に供給する。 座標変換部 5では設定された視点に対 応してその視点から所定の視角を張る四角錐 （ビューボリュ一 ム） を設定し、 この四角錐の高さ方向を Z铀方向として座標系 の変換を行う。
    [0006] ク リ ッピング部 6 においては、 図形がビューボリ ューム内に 入っているか否かを判断し、 ビューボリュ一ムの境界外または 境界上に存在する図形については、 境界外の部分を削除してビ ユーボリューム内の図形データのみを抽出するク リ ッビング処 を ί亍ラ ο
    [0007] 投影処理部 Ίにおいては、 ビューボリユーム内の図形か図示 されない表示器 （ C R T ) の画面に対応して定義された Z軸に 垂直な面 （定義面） 上に投影される形状になるように、 図形デ 一タを変形する投影変換処理を行う。 ぬりつぶし部 8では、 以上の処理を終った図形の面を平行す る多数の直線で埋めて、 面として表現するぬりつぶし処理を行 う。 ぬりつぶし部 8では、 このような直線の始点と終点を定め て 直線の発生を直線発生部 9に指示する。
    [0008] 直線発生部 9では、 直線発生の指示に応じてそれぞれの直線 を構成する連続的な点の集合からなるデータとして直線を発生 する。
    [0009] デプスバッファ 11には、 各図形データ中視点から見て最も手 前にある（ 最小の Z座標値を有する） 面の Z座標値がデブス値 として設定されている。 比較器 12は直線発生部 9 において発生 した直線のデブス値 （ Z座標値） とデブスバッファ 1 1のデプス 値とを比較して、 一致したとき発生した直線をフ レームバッフ ァ 10に書き込む。 フ レームバッファ 10のデータは、 図示されな い表示'器 （ C R T ) の走査に応じて読み出されて画面上に表示 される。
    [0010] 3次元図形データにおいて、 視点から見て複数の図形が重な り合って存在するとき、 直線発生部 9において発生した直線が デブスバッファ 1 1に格納されている値より大きい Z座標値を有 するときは、 その直線は視点から見て手前にある図形によって 陰蔽されて見えない図形の面に属するものであるから、 このデ —タを捨てて一致するもののみをフ レームバッファ 10に書き込 むことによって、 視点から見えない図形が酉面上に重複して表 示されないようにする陰面処理が行われる。 第 5図に示された装置において、 特定の図形について何らか の操作 （移動, 拡大等） を行おう とするときは、 オペレータは ボイ ンティ ングデバイ ス 3を使用レて、 C P U 1 に対し表示器 画面上の一点を指示する。 これによつて C P U 1 は指定された 点のまわりに一定の大きさのウイ ン ドウを設定し、 ク リ ッビ ン グ部 6 に設定されたウイ ン ドウに相当するビュ一ボリ ユ ームを 設定する。 これとともにスィ ッチ 13， 15をオフにして、 フ レー ムバッファ 10およびデプスバッファ 11への書き込みを禁止する , 次に通常の表示処理と同様にセグメ ン トバッファ 4内の図形 データを座標変換部 5へ入力し、 座標交換， ク リ ッピング、 投 影処理， ぬりつぶし処理， 直線の処理を順次行わせる。 ただし この際、 図形データの識別のためのデータ （ I D No . )をそれぞ れの図形データに付加する。 データ I D No . は図形データ と一 しょに各処理部を通過するが、 途中で内容に変化を生じること はない。
    [0011] ク リ ッビング部 6 においてク リ ッビング処理を行う際、 ビュ 一ボリューム外にある図形データが除去されるとともに、 除去 された図形データの i D No . も消滅する。 ぬりつぶし部 8の出 力において図形データ と I D No . とは分解され、 図形データが 直線発生部 9 に入力されるとともに、 I D No . はビックバッフ ァ 14に入力される。
    [0012] 直線発生部 9 においては、 入力された図形データの面に対応 して直線を発生する。 発生された直線は、 比較器 12においてそ のデブス値 （ z座標値） をデブスバッファ 1 1のデブス値と比較 される。 デブスバッファ 1 1には、 視点から見て最も手前にある 図形の Z座標値がデブス値と して設定されている。 比較器 12に おける比較結果、 発生された直線のデブス値がデブスバッファ 1 1のデブス値より大きい値を持つときは、 その図形は手前にあ る他の図形によって陰蔽されて見えないものであるから、 ピッ クバッファ 14における対応する I D N o . は消去される。
    [0013] 一方、 発生された直線のデブス値がデブスバッファ 1 1の内容 と一致したとき、 C P U 1 に対して割込みが発生するとともに、 ぴックバッファ 14の現在値がラッチされる。
    [0014] C P U 1 は割込みの発生に応答して、 ピックバッファ 14内の I D N o . を読み取り、 この I D N o . からセグメ ン トノ、'ッファ 4 内の対応する図形データをサーチするこ とによって、 図形抽出 行う。
    [0015] このよう にして、 視点から見て最も手前にある図形のみが抽 出される。 図形抽出が行われたとき、 スィ ッチ 13を閉じてその 図形データをフ レームバッファ 10に書き込むこ とによって、 抽 出された図形を図示されない表示器 （ C R T ) 上に表示させる こ とができる。
    [0016] 図形抽出は、 抽出した図形を例えば画面上で移動させたりま たは拡大したりする等、 オペレータが何らかの意図をもって図 形を操作するために行う ものであり、 従って指定領域にある図 形を抽出して次の図形操作につなげてゆく ためには、 できるだ け短時間に抽出を完了できることが要求される。
    [0017] しかしながら第 5図に示された図形抽出方式では、 通常の描 画処理とほぼ同様の動作を行って図形抽出を行うため、 処理完 了までにある程度の時間を必要とし、 必ずしも十分迅速である とは言えないという問題があった。 発明の開示
    [0018] このような従来技術の問題点を解決するため本発明の図形抽 出方式においては、 設定されたウイ ン ドウに相当するビューボ リューム内に舍まれる図形の面をぬりつぶす直線を発生してデ ブス値の比較を行う際に、 発生する直線を面をぬりつぶす直線 の N本ごとに 1本発生させ、 直線上の画素を直線を埋める画素 の M個ごとに 1倔発生させるようにする。
    [0019] 本発明の方式ではデブス値の比較を行うために発生する直線 の数を 1 Z Nとし、 直線上の画素の数を 1 ノ Mとするので直線 発生とデブス値の比較のための時間が短縮され、 従って図形抽 出の速度が向上する。 図面の簡単な説明
    [0020] 第 1図は本発明の一実施例を示す図、
    [0021] 第 2図はぬりつぶし処理を説明する図、
    [0022] 第 3図は直線発生を説明する図、
    [0023] 第 4図は図形描酉時と図形抽出時の酉素抽出を示す図、 第 5図は 3次元図形処理装置の構成を示す図である。
    [0024] 発明を実施するための最良の形態 本発明の図形抽出方式は、 第 5図に示された図形処理装置に おいてぬりつぶしおよび直線発生の処理を行う際に、 それぞれ 分解能を低下させることによって図形抽出の処理に必要な時間 を短縮するようにしたものである。
    [0025] 第 1図は本発明方式の一実施例を示し、 ）はぬりつぶし処理 を示すフローチヤ— ト、 （b)は直線発生を示すフローチヤ一 ト、 である。
    [0026] ぬりつぶし処理は図形を単位の三角形に分割し、 各三角形に ついてこれを被うように底辺に平行な多数の線分を発生するこ とによって行われる。 いま頂点 （X y , ) と底辺 （xz , y 2 ) (x3 ，y 3 ) によって定まる第 2図に示される三角形について、 図示のようにこれを被うように底辺に平行な多数の線分を発生 させるものとする。
    [0027] まず、 三角形の頂点 （x, ,y，）を挟む 2辺の傾斜 k, ,k2 を次の 関係によって求める（ ステップ S 1 ) 。 y 2
    [0028] k ,
    [0029] 2
    [0030] y l y 3
    [0031] k
    [0032] x X 3 次に A y = l > h = 0 , x = x t , y = y t として次の演算 によって、 頂点の次に発生する直線を求めて出力する（ ステツ ブ S 2 ) 。
    [0033] ( X - k ,h, y - h ) , ( x - k 2h , y - h ) ここで hは頂点 （ x , , y ,)からの高さを示している。
    [0034] 最初の直線が発生したとき、 次の直線は h— h + A y とする ことによって求められる （ステップ S 3 ) 。 ここで A y は y方 向の直線間隔である。
    [0035] 以下このような処理を繰り返し、 頂点からの距離 hが頂点と 底辺との y座標の差 （ y i — y 2 ) 以上になったとき処理を終 了する （ステップ S 4 ) 。
    [0036] 以上の方式では、 例えば A y = 2 とするこ とによって、 ぬり つぶし処理に要する時間を第 5図に示された場合の約 1 2に することができる。
    [0037] また直線発生はぬりつぶし処理において発生した直線に対応 して画素を書き込むことによって行われる。 いま第 3図に示す ように、 線分の始点 （ X , > y . ) から距離△ Xごとに画素を書 き込むものとする。
    [0038] 第 1図 ( )において、 まず Δ χ = 1 , = X 1 , = y , とし て点 （ X , y ) を出力し （ステップ S 6 ) 、 次に X— χ + Δ χ として同じ処理を繰り返し、 X軸の値が χ 2 を越えたとき処理 を完了する （ステップ S 7 ) 。 距離 Δ χは画素の間隔に対応し て定められるが、 Δ χ = 2 としたときは、 直線発生に必要な時 間を、 第 5図に示された場合のほぼ 1 / 1 とすることができる。 第 4図は本発明方式による図形描酉時と図形抽出時とにおい て抽出される画素を示し、 )に示す図形描酉時と比較して (b)に 示す図形抽出時には抽出される画素数が大幅に少く なることが 示されている。
    [0039] このように本発明の方式では、 図形抽出時に図形の面をぬり つぶす直線を発生してデブス値の比較を行う酉面の書直し動作 において、 面をぬりつぶす直線の数を間引いて酉面の走査線 N 本につき 1 本の直線を発生させるようにし、 また発生させる直 線はそれを表わす画素の数を間引いて 1 Z Mとし、 従って座標 の分解能を 1 に低下させるようにしている。 従って図形抽 出時デプス値の比較を行うべき酉素の数は 1 ノ N となるの で、 直線発生とデブス値の比較のため必要な時問が大幅に短縮 され、 図形抽出の速度を向上させることが可能になる。
    [0040] 以上説明したように本発明の方式によれば、 図形抽出時に行 われる画面の書直し動作において、 多角形のぬりつぶし処理に おける直線の発生数を 1 Z Nとし、 直線発生処理における座標 の分解能を 1 Z Mにするので、 図形抽出処理に要する時間が大 幅に短縮される。
    权利要求:
    Claims
    ο) 請 求 の 範 囲
    3次元図形処理装置において、 画面上の指定点を中心として ウィ ン ドゥを設定して 3次元図形データを該ゥイ ン ドウに対応 してク リ ツビングして、 該ウイ ン ドウに相当するビューボリ ュ —ム内に含まれる図形とその識別用データとを抽出して該抽出 された識別用データをピックバッファに格納し、 該抽出された 図形の面に対応して発生された直線のデブス値を予め設定され ているデブス値と比較して一致したとき該直線の属する図形の 識別用データに対応する図形データを読み岀すことによって指 定点に対応する図形を抽出する図形抽出方式において、
    前記ぬりつぶし処理時デブス値の比較のため発生する直線を 面をぬりつぶす直線の Ν ( Νは任意の整数） 本ごとに 1本発生 させるとともに、
    前記直線発生時デブス値の比較のため発生する画素を直線を 埋める画素の Μ ( Μは任意の整数） 個ごとに 1個発生させるよ うにしたことを特徴とする図形抽出方式。
    类似技术:
    公开号 | 公开日 | 专利标题
    US8487954B2|2013-07-16|Automatic 3D modeling
    US8144158B2|2012-03-27|Display system having floating point rasterization and floating point framebuffering
    KR900006042B1|1990-08-20|복합문서 처리 장치용 표시 제어장치
    CA1213085A|1986-10-21|Method and apparatus for image compression andmanipulation
    US4967392A|1990-10-30|Drawing processor for computer graphic system using a plurality of parallel processors which each handle a group of display screen scanlines
    US4953107A|1990-08-28|Video signal processing
    US4914607A|1990-04-03|Multi-screen display control system and its method
    US7643683B2|2010-01-05|Generation of image database for multifeatured objects
    KR100411534B1|2004-04-28|영상데이터생성방법,생성장치및생성회로,및게임재생장치
    US4763119A|1988-08-09|Image processing system for area filling of graphics
    JP2725062B2|1998-03-09|画像処理装置
    US6222551B1|2001-04-24|Methods and apparatus for providing 3D viewpoint selection in a server/client arrangement
    US4648045A|1987-03-03|High speed memory and processor system for raster display
    JP3184327B2|2001-07-09|３次元グラフィックス処理方法及びその装置
    US5473740A|1995-12-05|Method and apparatus for interactively indicating image boundaries in digital image cropping
    EP0433373B1|1996-05-29|Efficient method for updating pipelined, single port z-buffer
    CA2015518C|2000-06-20|Method and apparatus for moving control points in displaying digital typeface on raster output devices
    US4975976A|1990-12-04|Image transformation method and device
    CN100399358C|2008-07-02|图像处理装置及其方法
    US4570181A|1986-02-11|Characteristic extracting apparatus
    JP3189870B2|2001-07-16|画像処理装置
    KR960016886B1|1996-12-26|다수의 3차원 객체로부터 가시 객체를 픽크하는 장치 및 방법과 그를 이용한 비디오 디스플레이 시스템
    US6016148A|2000-01-18|Automated mapping of facial images to animation wireframes topologies
    US4935879A|1990-06-19|Texture mapping apparatus and method
    JP5463866B2|2014-04-09|画像処理装置および画像処理方法、並びにプログラム
    同族专利:
    公开号 | 公开日
    EP0255545A1|1988-02-10|
    JPS62168281A|1987-07-24|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    1987-07-30| AK| Designated states|Kind code of ref document: A1 Designated state(s): US |
    1987-07-30| AL| Designated countries for regional patents|Kind code of ref document: A1 Designated state(s): DE FR GB |
    1987-09-18| WWE| Wipo information: entry into national phase|Ref document number: 1987900877 Country of ref document: EP |
    1988-02-10| WWP| Wipo information: published in national office|Ref document number: 1987900877 Country of ref document: EP |
    1989-04-12| WWW| Wipo information: withdrawn in national office|Ref document number: 1987900877 Country of ref document: EP |
    优先权:
    申请号 | 申请日 | 专利标题
    [返回顶部]