JPH0348554B2

JPH0348554B2 -

Info

Publication number: JPH0348554B2
Application number: JP60015902A
Authority: JP
Inventors: Koichi Akatsuka; Shuichi Nakajima
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1985-01-30
Filing date: 1985-01-30
Publication date: 1991-07-24
Also published as: JPS61175782A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明はコンピユータグラフイツクス等におけ
る図形処理に用いられる図形表示処理方式の改良
に関する。

図形処理は取扱データ量が大であるため、多角
形等の平面図形を処理する際の処理効率の向上が
求められるている。

〔従来の技術〕

従来例を図によつて説明する。第１３図は従来
例の説明図である。例えば第１３図ａに示す中空
部を持つ多角形を表示する際、これを三角形や四
角形などの基本的な図形の集合に分割して表示す
る処理手法が、コンピユータグラフイツクス、３
次元CAD（Computer Aided Design）等に、広
く用いられている。

分割を行う際には、１３図ｂのように表示対象
の多角形を含む（メツシユ）を設定し、多角形を
格子単位に分割する。そして格子内に入つた図形
が三角形や四角形になつた場合は、その図形を表
示するしかし斜線を施した部分のように、格子内
の図形が四角形より複雑な図形である場合は、そ
の格子内に、より細かい格子を設定し、細分化さ
れた格子内の図形が三角形や四角形になるまで分
割を続ける。１３図ｃは１３図ｂの斜線部分を取
り出し細分した結果である。

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

上記の如く、従来の図形処理方式では単一の穴
空き多角形が複数の穴無し多角形に変換されるた
め、図形データ量が急増する。従つて処理装置か
ら表示装置へのデータ転送に要する時間が増大
し、表示処理に要する時間が大となる問題点があ
つた。

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

上記の問題点は、面データ、稜線データ等から
なる３次元情報が格納されたメモリと表示装置と
を有し、メモリから取出された３次元情報を用
い、表示装置の画面に立体形状画像を表示するシ
ステムにおいて、前記３次元情報を２次元情報に
変換する第１の変換処理手段と、該２次元情報内
の弧及び自由曲線データを複数の稜線データに分
割する分割処理手段と、該分割された稜線データ
を含む穴空き多角形２次元情報を穴無しの多角形
２次元情報に変換する変換処理手段と、該穴無し
多角形２次元情報を３次元情報に変換する第２の
変換処理手段とを備えた本願発明の図形表示処理
方式によつて解決される。

〔作用〕

以上のように本願発明は、穴空き多角形２次元
情報を、穴無し多角形２次元情報に変換する手段
を有するので、図形データ量が増加することがな
い。従つてデータ転送、データ処理に要する時間
が短縮され、図形表示の高速化が可能となり、図
形処理効率を著しく向上する。

〔実施例〕

以下、本発明を図面によつて説明する。第１図
は本発明の一実施例を説明するブロツク図、第２
図〜第４図及び第６図〜第１１図は本発明の図形
処理の一実施例を説明する図形、第５図及び第１
２図は従来例の説明図である。

第１図において、フアイル１には、ソリツドモ
デルデータSDが格納されている。このデータSD
に含まれる面データ或は境界線を構成する稜線デ
ータは、すべて３次元データである。なお立体形
状を表現する数学モデルをソリツドモデルと呼
び、このソリツドモデルの情報変更などを含むメ
ンテナンスは、ソリツドモデリング部３によつて
行われる。

表示制御装置４のキーボード５又はライトペン
６により図形処理（立体形状の変更など）を行う
ときには、処理部７によつてソリツドデータハン
ドラ２が起動される。

ソリツドデータハンドラ２は、フアイル１から
取出したソリツドモデルデータSDを、バス８を
経てDAデータ変換部９へ送出する。

DAデータ変換部９は、ソリツドモデルデータ
SDの面（ポリゴン）への分割処理を行うが、ま
ず３次元データを、２次元変換部１０により２次
元データに変換する。既述の如くソリツドモデル
データSDに含まれている面データや稜線データ
は、すべて３次元であり、これを２次元データに
変換する。以下２次元変換部１０の変換処理につ
いて説明する。

例えば直方体は、３次元実空間（ｘ，ｙ，ｚ）
内のデータとしてしか表現できないが、この直方
体の上面だけに限定すれば第２次元パラメータ空
間（ｕ，ｖ）で考えるこどができる。この３次元
データから２次元データへの変換は、数学的手法
を用いて処理できる。一例として平面の変換の場
合、法線ベクトルｎ→を、ｎ→＝（n_x，n_y，n_z）とし、また各成分中で絶対値最大のものを、 n_nax＝Max｛｜n_x｜，｜n_y｜，｜n_z｜｝とすれば、 n_nax＝｜n_x｜ならば（ｕ，ｖ）＝（ｙ，ｚ） n_nax＝｜n_y｜ならば（ｕ，ｖ）＝（ｚ，ｘ） n_nax＝｜n_z｜ならば（ｕ，ｖ）＝（ｘ，ｙ）の如く３次元実空間（ｘ，ｙ，ｚ）から２次元パ
ラメータ空間（ｕ，ｖ）への変換が行われる。

例えば第２図に示す如く、直方体、全体は３次
元実空間（ｘ，ｙ，ｚ）内のデータとしてしか表
現できない。しかし上面だけに限定すれば、２次
元パラメータ空間（ｕ，ｖ）で考えることが可能
である。

更に、任意の多面体を構成する一表面をとら
え、これが２次元空間内の平面上に構成する多角
形は、穴空き多角形も含めて、次のように表せ
る。

第１４図においてｐ→₁，ｐ→₂，…，ｐ→_Nは同一平
面に存在する多角形の各頂点の３次元位置ベクト
ルであつて、ｐ→_i＝（X_i，y_i，Z_i），ｉ＝１〜Ｎまた、ｎ→は多角形がのつている無限平面上の法
線ベクトルであつてｎ→＝（n_x，n_y，n_z）また、ｏ→は多角形がのつている無限平面上の任
意の一点の３次元位置ベクトルであつてｏ→＝（o_x，o_y，o_z）とする。

第１図の２次元変換部１０では、３次元実空間
（ｘ，ｙ，ｚ）に存在する多角形を構成する頂点
列ｐ→_i（ｉ＝１〜Ｎ）の情報を、以下の手順で２
次元パラメタ空間（ｕ，ｖ）へ変換する。

先ず、n_x，n_y，n_zの中でその絶対値が最も大き
いものをみつけだす。

次に、n_xの絶対値が最大である場合は、ｐ→_i＝（x_i，y_i，z_i）の中から、y_iとz_iをｕ，ｖと
して採用する。

つまり頂点ｐ→_iに対応する２次元パラメタ空間
（ｕ，ｖ）での頂点ｐ→_iの座標値は、ｐ→_i＝（u_i，v_i）＝（y_i，z_i）である。

同様に、n_yの絶対値が最大である場合は、ｐ→_i＝（u_i，v_i）＝（z_i，x_i）であり、n_zの絶対値
が
最大である場合は、ｐ→_i＝（u_i，v_i）＝（x_i，y_i）である。

以上の処理は第１５図に示すように、３次元空
間（ｘ，ｙ，ｚ）内の多角形を、座標平面の一つ
に投影し、その座標平面内の２次元図形とするこ
とに相当する。

更に以上の処理により、３次元空間内の多角形ｐ→_i＝（x_i，y_i，z_i），ｉ＝１〜Ｎを２次元空間内
の多角形ｐ→_i＝（u_i，v_i），ｉ＝１〜Ｎに変換する。

ここで以上の２次元変換に使われた『多角形が
のつている無限平面上の法線ベクトル』ｎ→ および『多角形がのつている無限平面上の任意の
一点の３次元位置ベクトル』ｏ→の情報は保存さ
れ、３次元変換部１３が行う変換処理の中で使わ
れる。

本発明では第２図に示す穴空き多角形の穴無し
多角形への変換において、図形データを一旦２次
元（ｕ，ｖ）空間データに変換し、（ｕ，ｖ）空
間内で穴無し多角形への変換を行つた後に、その
データを（ｘ，ｙ，ｚ）空間に逆変換する。

ソリツドモデルデータSDから抽出される稜線
データは、 ●各辺の始点と終点の座標値 ●円弧については中心の座標値と半径 ●自由曲線については制御点情報などから成る３次元データである。各辺の始点と
終点の座標値は２次元変換部によつて（ｕ，ｖ）
空間での座標値に変換される。

次に稜線分割部１１による稜線分割処理を第３
図によつて説明する。第３図ａに示す辺Ａ、自由
曲線（Bezier曲線）Ｂ及び円弧Ｃで構成される
３次元図形は同図ｂに示す如く、分割して近似処
理を行うことができる。即ち自由曲線Ｂ及び弧Ｃ
については第３図ｂに示す如く各辺上に点列を発
生させて分割し、折線で近似する。従つて第３図
ａに示す図形データ（ソリツドモデルデータSD）
から抽出されるデータは、 (1) 各辺Ａの始点と終点の座標値 (2) 自由曲線（Bezier曲線）Ｂについては制御
情報即ちパラメータｔ（０〜１）で表現される
情報、 (3) 円弧Ｃについては角度θ によつて表現される。このような稜線分割処理に
より、「３次元空間内の曲線で囲まれた穴空き有
限平面」は、「２次元空間内の穴空き多角形」に
変換することができる。

ブリツジ生成部１２は、稜線分割部で生成され
た「２次元空間内の穴空き多角形」の内部ループ
と外部ループの間に２本の稜線（doublebridge）
を生成することで、穴空き多角形を単一の穴無し
多角形に変換する処理を行うが、ブリツジ生成の
概要を第４図によつて説明する。

第４図ａは、入力データとなる穴空き多角形で
あり、外部ループＬの中に、斜線で示される内部
ループ１₁及び１₂を有する。本発明では第４図ｂ
に示す如く、外部ループの頂点Ｅと内部ループの
１₁頂点Ｆとを２本の稜線R₁及びR₂（double
bridge）で結び、同様に外部ループＬの頂点Ｈ
と、内部ループ１₂の頂点Ｇとを、２つの稜線R₃
及びR₄で結ぶことで穴の無い多角形への変換を
行う。

また第４図ｃに示す如く、外部ループＬに直接
結ぶことができない内部ループ１₃が存在すると
きには、内部ループ１₃の頂点Ｑと、内部ループ
１₄の頂点Ｐとの間にダブルブリツジ（double
bridge）を形成せしめると共に、内部ループ１₄
の頂点Ｍと、外部ループＬの頂点Ｋとの間にダブ
ルブリツジを形成させて、穴の無い多角形への変
換を行う。即ち内部ループＬにつなぎ、穴の無い
多角形への変換を行う。

第１図におけるブリツジ生成部１２の処理を第
５図のフローチヤートの処理順に、第６図〜第１
１図を用いて説明する。

内部ループ１₁の選択内部ループが複数在るときは、まず１つの内部
ループｉを指定する。

ブリツジ候補の選択内部ループｉ上の１頂点と外部ループＬ上の１
頂点を取り出し、ブリツジ候補線とする。

第６図において、破線で示す例はブリツジとし
て不適の例である。

端点チエツク処理ブリツジの両端点でブリツジが多角形の内側へ
向かつて出ているかどうかチエツクする。第７図
において、斜線を施した部分（多角形外部）へ出
ている３本のブリツジ候補線はいずれも不当なも
のである。第６図のブリツジ候補線ａはこのチエ
ツクによつて除外される。

交差チエツク処理ブリツジ候補線と他の全稜線について交差チエ
ツクを行い、１本でも交差する稜線があれば、そ
のブリリツジ候補線を除外する。従つて第６図は
第８図に示す如くなる。また処理高速化のため、
交差チエツクは次の２つの段階に分けて行う (1) ラフチエツクブリツジ候補線または稜線を対角線とし、
ｕ，ｖ各座標軸に平行な辺を持つ長方形を生成
し、長方形間で重なりの有無を調べる。

第９図において、ブリツジ候補線を含む長方
形のｕ，ｖ軸方向最小値と最大値を、それぞれ u_nio，u_nax，v_nio，v_nax とする。

同様に稜線を含む長方形について、 u′_nio u′_nax v′_nio v′_nax を定義する。

このとき、以下の条件の少なくとも１つが満た
されたとき、ブリツジ候補線とその稜線の間に
交差は無い。

u′_nio＞u_nax u′_nax＜u_nio v′_nio＞v_nax v′_nax＜v_nio 例えば第１０図ａに示す稜線Ｃはブリツジ候
補線ｂについて「交差無し」と判定される。

(2) 詳細チエツク (1)項のラフチエツクで「交差が無い」と判定
できなかつた稜線について、ブリツジ候補線と
交点計算を行い交差の有無をチエツクする。

第１０図ｂにおける稜線ｄは、(1)項のラフチ
エツクでは判定できないが、(2)項の詳細なチエ
ツクにおいて、交点計算を行うことによりブリ
ツジ候補線ｂについて「交差無し」と判定でき
る。

ブリツジ生成処理以上のチエツク処理理で全稜線と交差が無いと
判定されたブリツジ候補線にそつてブリツジを生
成する。これにより第１１図ａに示す穴空き多角
形は、同図ｂに示す穴無し多角形に変換される。

なお第１１図ａにおけるｅはブリツジ候補線を
示し、また第１１図ｂにおけるｆ及びｇは新規生
成点である。

ブリツジ生成の終了判定を行う。

処理の正常終了の判定を行う。

次ぎに第１図における３次元変換部１３は、２
次元（ｕ，ｖ）空間で生成された穴無し多角形デ
ータを３次元（ｘ，ｙ，ｚ）実空間に逆変換す
る。

ブリツジを追加して穴無し多角形に変換された
多角形ｐ→_i＝（u_i，v_i），ｉ＝１〜Ｎを再び３次元実空間内の多角形ｐ→_i＝（X_i，y_i，Z_i），ｉ＝１〜Ｎに戻すために、
第１図の２次元変換部１０で使つたｎ→およびデｏ→
を再度利用して、以下の処理を行う。

この場合、第１図の２次元変換部１０での判定
結果を保存し、それを利用することも可能であ
る。

次に、n_xの絶対値が最大である場合、u_iはy_iと
して、v_iはz_iとしてそのまま使える。

補うべき座標値はx_iであり、以下のように求め
られる。

第１６図に示すように、３次元空間内の多角形
の頂点ｐ→_i＝（x_i，y_i，z_i）とその多角形がのつている無
限平面上の一点ｏ→との間のベクトルｐ→_i−ｏ→は、その無限平面の法線ベクトルｎ→と
垂直である。ここで、互いに垂直な２つのベクト
ルの各成分の積の総和は０となるので、（ｐ→−ｏ→・ｎ→＝（x_i−o_x）n_x ＋（y_i−o_y）n_y ＋（z_i−o_z）n_z ＝０となる。

従つて、 x_i＝o_x−〔（y_i−o_y）n_y ＋（z_i−o_z）n_z〕／n_x ＝o_x−〔（u_i−o_y）n_y ＋（v_i−o_z）n_z〕／n_x となる。

従つて、ｐ→_i＝（o_x−〔（u_i−o_y）n_y ＋（v_i−o_z）n_z〕／n_x，u_i，v_i）＝（x_i，y_i，z_i）となる。

同様にn_yの絶対値が最大である場合は、ｐ→_i＝（v_i，o_y−〔（u_i−o_z）n_z ＋（v_i−o_x）n_x〕／n_y，u_i）＝（x_i，y_i，z_i）となる。

また、n_zの最大値が最大である場合は、ｐ→_i＝（u_i，v_i），o_z−〔（u_i−o_x）n_x ＋（v_i−o_y）n_y〕／n_z）＝（x_i，y_i，z_i）となる。

２次元パラメタ空間（ｕ，ｖ）内でブリツジ作
成を終えた穴無し多角形は、以上の処理によつ
て、３次元実空間（ｘ，ｙ，ｚ）内の多角形に変
換される。

以上の処理によつて、多面体を構成する一面の
処理が完了するので、他の面についても必要によ
り同様な処理をすればよい。

第１２図は、以上に述べた一連の処理即ち第１
図におけるDAデータ変換部９の処理概要を示す
フローチヤートである。また第１図における１４
は表示データハンドラ、１５は表示データフアイ
ル、１６は表示部、１７は処理装置である。

〔発明の効果〕

以上のように本発明は、穴空き多角形の図形情
報を１つの穴無し多角形の図形情報に変換しうる
ので、図形データ量が増加しないため、データ転
送及びデータ処理に関する処理効率を著しく向上
する効果をもたらす利点を有する。

【図面の簡単な説明】

第１図は本発明の一実施例を説明するブロツク
図、第２図〜第４図は本発明の一実施例を説明す
る図形、第５図及び第１２図は本発明の一実施例
を説明するフローチヤート図、第６図〜第１１図
は本発明の一実施例を説明する図形、第１３図は
従来例の説明図、第１４図〜第１６図は本発明の
一実施例を説明する図形、図において、１はフアイル、２はソリツドデー
タハンドラ、３はソリツドモデリング部、４は表
示制御装置、５はキーボード、６はライトペン、
７は処理部、８はバス、９はDAデータ変換部、
１０は２次元変換部、１１は稜線分割部、１２は
ブリツジ生成部、１３は３次元変換部、１４は表
示データハンドラ、１５は表示データフアイル、
１６は表示部、１７は処理装置を示す。

Claims

【特許請求の範囲】

１面データ、稜線データ等からなる３次元情報
が格納されたメモリと表示装置とを有し、メモリ
から取出された３次元情報を用い、表示装置の画
面に立体形状画像を表示するシステムにおいて、
前記３次元情報を２次元に変換する第１の変換処
理手段と、該第２次元情報の内の弧及び自由曲線
データを複数の稜線データに分割する分割処理手
段と、該分割された稜線データを含む穴空き多角
形２次元情報を穴無しの多角形２次元情報に変換
する変換処理手段と、該穴無し多角形２次元情報
を３次元情報に変換する第２の変換処理手段とを
備えたことを特徴とする図形表示処理方式。