JPH0634239B2 - ３次元画像表示装置 - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、多面体の色彩陰影付画像をラスター走査型Ｃ
ＲＴ上に生成表示する３次元画像表示装置に関するもの
である。

（従来の技術） ３次元の色彩陰影付画像をラスター走査型ＣＲＴ上に生
成表示する方式として、多面体モデルのｚバッファ法を
用いた表示処理方法がある。その表示処理手順を以下に
述べる。

（Ｉ）形状モデリング……物体形状を３次元世界座標系
内に定義する。多面体モデルでは、物体形状を頂点、稜
線、面の座標値やその隣接関係により表現する。物体表
面が曲面を含む場合は、曲面を多角形に分割して近似す
る。多面体モデルの作成法は後に述べる。

（II）投影変換……世界座標系内に投影面、視点、投影
方法（平行投影か中心投影か）を指定し、投影面上に設
定した画面枠を基準とした３次元の画面座標系に投影変
換する。

世界座標系から画面座標系への投影変換は、座標軸の回
転、平行移動、画面座標へのスケーリング、及び透視変
換の合成されたもので、後に述べるように４×４の行列
乗算と透視除算からなる。視点から画面枠を通して見た
投影面の背後の空間部分は画面座標系の直方体の内部に
写像される。画面座標系のｚ値を深度と呼び、隠面消去
に用いる。多面体モデルでは、多面体のすべての頂点を
投影変換すればよい。投影変換では直線は直線に変換さ
れ、内分比を変えないという性質をもつので画面座標系
内部での線形内挿計算により、もとの多面体の稜線や面
を描画でき、深度も１点１点正しく求められる。座標変
換の結果、クリッピングや裏面除去を行うことがある。
クリッピングは投影面上に矩形の窓を設定し、投影図の
窓枠内部のみを表示するために、多面体を囲む各々の多
角形について窓枠の外部にはみ出した多角形の全体また
は一部を除去する処理である。裏面除去は、視点から見
て明らかに不可視となる裏面の多角形を検出し除去する
処理である。

（III）走査変換……画面座標系で頂点の系列として表
現された多角形を塗りつぶして表示するために、該多角
形を画素の系列に変換する。それには、多角形の頂点座
標からその稜線上の画素を補間して生成し、さらに多角
形の内部の画素を補間して生成する。隠面消去のために
は、画素毎に投影面から当該多角形に至る深度ｚも計算
する。

（IV）隠面消去を伴う画像表示……複数個の多角形が表
示画面上で重なる場合には視点に最も近い多角形を優先
的に表示する必要がある。この隠面消去を画素単位に行
うのがｚバッファ法である。ｚバッファ法では、２次元
の画素アドレス（ｘ，ｙ）に対して、三原色強度R,G,B
を記憶する画像メモリ（フレームバッファとも呼ぶ）の
他に、深度ｚを記憶するｚバッファメモリ（デプスバッ
ファとも呼ぶ）を使用し、予め画像メモリを背景色で、
ｚバッファメモリを深度の最大値ｚ_maxで満たしてお
く。多角形を走査変換して三原色及び深度をもつ一連の
画素（X_i,y_i,z_i,R_i,G_i,B_i）ｉ＝1,2,3,…に展開した
時、画像メモリの（x_i,y_i）番地に三原色強度R_i,G_i,B_i
を書き込む前に、ｚバッファメモリの（x_i,y_i）番地の
深度ｚ_Ｍ（x_i,y_i）を読み出してｚ_ｉと比較し、ｚ_ｉ＜
ｚ_Ｍのときに限り前記R_i,G_i,B_iの書き込みを行うと共
に、z_M（x_i,y_i）の値をｚ_ｉで更新する。従ってｚバッ
ファメモリは画素毎に現在までに描画された値も視点に
近い多角形の深度を記憶し、以後これより深度の大きい
多角形の画素が来てもその書き込みを禁止する機能を有
する。すべての多角形の走査変換されたすべての画素に
ついて以上の処理を順次実行すれば、最終的に正しく隠
面消去され、可視画素の深度が付与された３次元画像が
R_M,G_M,B_M,z_Mで得られる。（R,G,B）の値の付与の仕方と
しては、多角形毎に異なる値を予め与えられる方法、光
源が指定された時点で多角形毎に反射強度を計算し陰影
を付けて表示する方法、頂点毎に反射強度を計算し多角
形内部で補間して滑らかな陰影を付ける方法等がある。

以上の表示方式はハードウェアによる高速処理に向いて
おり、画像メモリの他に座標変換器、走査変換器、ｚバ
ッファメモリを備えた３次元画像表示装置が提案されて
いる。第１８図にこの種の従来の３次元画像表示装置の
構成を示す。同図において、ホストプロセッサ２１は後
述するように表現変換の処理における多大な計算を実行
し、その結果をホストインタフェース２２を介して表示
装置側に送出する。制御プロセッサ２３は装置各部を制
御して前述した一連の表示処理を実行させる。図形メモ
リ２４は多面体データを記憶し、座標変換器２５は頂点
の投影変換を行い、走査変換器２６は多角形の走査変換
を行い、メモリ更新器２７はｚバッファメモリ２９を使
って隠面消去を行いながら画像メモリ２８に３次元画像
を作り、ＣＲＴ３０に表示させる。画像メモリ２８及び
ｚバッファメモリ２９の役割は既述したとおりである。

次に多面体モデルの作成方法について従来採られていた
方法を説明する。第１９図は２つの直方体ＡとＢの空間
的な論理演算によって合成される多面体の形状を示す図
で、同図(a)はＡとＢの位置関係を示し、同図(b)は論理
和Ａ∨Ｂ、同図(c)は論理積Ａ∧Ｂ、同図(d)は論理差Ａ
−Ｂによる結果である。通常は、システムの利用者が
Ａ，Ｂのような基本立体の形状と寸法、移動と回転の
両、論理演算記号を入力すると、多面体モデリングシス
テムは両多面体を座標変換して位置関係を設定し、両多
面体の交差稜線をすべて求め、目的とする合成体を囲む
多角形をすべて求めることにより多面体モデルを作成す
る。出来上がった多面体にさらに第３，第４の基本立体
や別の合成体を逐次合成して次第に複雑な形状の多面体
を形成して行く。第２０図は４つの基本立体A₁,A₂,A₃,A
₄の合成方法の一例を示す図で、ＣＳＧ（Constructive
Solid Geometory）表現またはＣＳＧトリーと呼ばれる
立体表現法である。これに対し、多面体を囲む多角形の
集合による表現は境界表現（Boundary Representatio
n）と呼ばれる。ＣＳＧ表現から境界表現への変換を行
う処理には多大の計算量が必要であるから、通常はこの
処理を第１８図のホストプロセッサ２１において実行
し、境界表現による多面体データとしてホストインタフ
ェース２２から図形メモリ２４に転送し、表示装置側で
投影変換以後の表示処理を行っている。

（発明が解決しようとする問題点） しかしながら、以上述べたような処理方式では２つの多
面体の交差稜線を求めるために両多面体を囲む多角形の
すべての組合わせについて３次元的な交差を調べる必要
があるので、利用者が多面体のＣＳＧ表現を入力してか
らその３次元画像を得るまでに多大の時間を費やすこと
になり、この応答性の悪さが対話型の多面体モデリング
システムの１つの大きな問題点であった。

本発明はこのような従来技術の問題点を解決するために
なされたものであって、応答性の優れた多面体モデリン
グシステムを構築できるように、ＣＳＧ表現多面体を直
接表示できる３次元画像表示装置を提供することを目的
とする。

（問題点を解決するための手段） 本発明の２次元画像表示装置は、前記従来技術の問題点
を解決するため、多面体のＣＳＧ表現データとその構成
要素である基本立体データとを記憶する第１の図形メモ
リと、基本立体データに対し、当該ＣＳＧ表現及び視点
情報にしたがって座標変換及び投影変換を施す座標変換
器と、変換された基本立体データを記憶する第２の図形
メモリと、基本立体を囲む多角形を走査変換して三原色
強度及び深度をもつ画素データに分解する走査変換器
と、画面上の画素毎に３次元画像の三原色強度を記憶す
る画像メモリと、画素毎に深度を一時記憶する第１のｚ
バッファメモリと、ＣＳＧ表現における基本立体のうち
の１つだけの前方面または後方面を走査変換したときの
構成画素の深度のみを一時記憶する第２のｚバッファメ
モリと、可視となる画素をＣＳＧ表現の論理式にしたが
って検出するために、その基本立体の前方面または後方
面の構成画素の各々につきそれが他の基本立体の内部か
外部かを判定してその結果を記憶する論理演算メモリ
と、深度の付与された画素データを隠面消去しつつ画像
メモリ及び第１のｚバッファメモリに書き込む操作、及
びＣＳＧ論理演算のために第２のｚバッファメモリ及び
論理演算メモリの制御を行うメモリ更新器とを設け、可
視とされた基本立体の構成画素に対し三原色強度及び深
度を求め、該データを隠面消去しつつ画像メモリ及び第
１のｚバッファメモリに書き込むことにより、ＣＳＧ表
現による多面体の３次元画像を表示するようにしたもの
である。

（作用） 本発明によれば以上のように３次元画像表示装置を構成
したので、各技術手段は次のように作用する。

第１の図形メモリは基本立体データ及び多面体のＣＳＧ
表現データを記憶する。座標変換器は第１の図形メモリ
から基本立体データを読み出し、それに座標変換及び投
影変換を施す。変換された基本立体データは第２の図形
メモリに記憶される。走査変換器は基本立体を囲む多角
形を走査変換して三原色強度及び深度の画素データを得
る。この画素データは、メモリ更新器の働きにより、画
像メモリ及び第１のｚバッファメモリに隠面消去しなが
ら書き込まれる。すなわち画像メモリは画面上の画素毎
に３次元画像の３原色強度を記憶し、第１のｚバッファ
メモリは画素毎に深度を記憶する。ところで本発明では
第２の図形メモリに記憶されている変換された基本立体
データより多面体を合成するわけであるが、この合成の
ため、第２のｚバッファメモリは基本立体のうちの１つ
だけの前方面または後方面を走査変換した画素の深度の
みを記憶し、一方論理演算メモリは１の基本立体の各画
素につきそれが他の基本立体の内部か外部かを判定した
結果を保持する。そしてメモリ更新器の働きにより、こ
れらの情報を参照しつつ可視となる画素がＣＳＧ論理演
算にしたがって求められる。そしてメモリ更新器の操作
により、可視と判定された基本立体の三原色強度及び深
度のデータが隠面消去を行いながら画像メモリ及び第１
のｚバッファメモリに正しく書き込まれる。したがっ
て、ＣＳＧ表現から境界表現への変換をせずに多面体画
像を直接表示できるようになり、前記従来技術の問題点
が解決される。

（実施例） 以下本発明の一実施例について詳細に説明する。

第１図は本実施例の３次元画像表示装置の構成を示すブ
ロック図である。図中１はホストプロセッサ、２はホス
トインタフェース、３は制御プロセッサ、４は第１の図
形メモリ、５は第２の図形メモリ、６は座標変換器、７
は走査変換器、８はメモリ更新器、９は画像メモリ、１
０は第１のｚバッファメモリ、１１は第２のｚバッファ
メモリ、１２は論理演算メモリである。この装置を第１
８図の従来の装置と比較すると、第２の図形メモリ５、
第２のｚバッファメモリ１１及び論理演算メモリ１２を
追加した点が主として相違している。第１図の３次元画
像表示装置を使用すれば境界表現の多面体モデルの他、
ＣＳＧ表現の多面体モデルの画像も生成できる。以下、
ＣＳＧ表現された多面体を本装置を使用して表示処理す
る手順を詳細に説明する。

第１図の第１の図形メモリ４には表示すべきすべての３
次元図形データが記憶されている。これらの図形データ
は通常は３次元世界座標系で既述されており、順次読み
出されて座標変換器６による投影変換と走査変換器７に
よる走査変換を施され、メモリ更新器８の働きにより画
像メモリ９及び第１のｚバッファメモリ１０に深度の付
与された３次元画像として合成されて行く。ＣＳＧ表現
の多面体はこれらの図形の１表現形態として発生するも
ので、このときＣＳＧ多面体を画像メモリ９に正しく合
成表示する必要がある。

ＣＳＧ表現の多面体は第２０図に例示されるような木
（トリー）構造をもつ。ＣＳＧトリーの葉に位置する
「基本立体」は第３図のように定義される。第３図(a)
のように基本立体に固定した座標系Ｏ−ＸＹＺにおい
て、基本立体の各頂点Ｖ_１〜Ｖ_８の座標を第３図(b)の
ように定義し、基本立体を囲む各面Ｓ_１〜Ｓ_６を第３図
(c)のように頂点の系列として定義する。各面は多角形
であって基本立体の外部から見て反時計回りになるよう
に頂点を順に並べたものとする。第２０図のＣＳＧトリ
ーの枝に位置する「変換」は基本立体または合成途中の
立体（以下これらを単に立体と呼ぶ）の座標変換を指定
するもので、拡大，縮小，平行移動，回転の組合せが許
される。この変換は次式のようなベクトルとマトリクス
の乗算である。

第２０図のＣＳＧトリーの節に位置する「合成」は座標
変換を受けた２つの立体に和，積，差のいずれかの２項
論理演算を施すものである。第２０図では基本立体A₁,A
₂に「合成１」が施され、基本立体A₃,A₄に「合成２」が
施され、これらの合成体にさらに「合成３」が施されて
最終的な合成体が得られる。「変換７」はこの合成体を
世界座標系内のしかるべき位置に置き、または運動させ
る機能をもつ。この合成体はさらに「投影変換」を受け
て画面上に表示される。ところが、この合成体の表面は
基本立体A₁,A₂,A₃,A₄のいずれかの表面であるから、第
２図に示すように基本立体A₁,A₂,A₃,A₄を個別に画面座
標系まで変換した立体をそれぞれA_1S,A_2S,A_3S,A_4Sと
し、これらの変換された基本立体を第２０図と同じ合成
手続きにより合成すればよい。

画面座標系に変換された基本立体データA_1S,A_2S,A_3S,A
_4Sは第２の図形メモリ５に記憶される。画面座標系os-x
syszsにおける基本立体データの１つ（例えばＡ_1S）を
選び第４図に例示する。第４図(a)は同座標系における
Ａ_1Sの空間位置を示す図である。第４図(b)の頂点座標
は次式により求められる。

〔x_siy_siz_siw_si〕＝〔X_iY_iZ_i1〕・Ｍ_１・Ｍ_５・Ｍ_７・Ｍ_ｐ 但し、ｉ＝1,2,…，８ … ここにM₁,M₅,M₇,M_pはそれぞれ「変換１」，「変換
５」，「変換７」，「投影変換」を表わす４×４の行列
であって、M₁,M₅,M₇は式における行列と同じ形をも
つ。Ｍ_ｐは平行投影の場合は式における行列と同じ形
をもつが、中心投影の場合は第４列が〔0,0,0,1〕では
ない。基本立体Ａ_１の座標変換を行うにはまず行列同志
の乗算を行って Ｍ_1S＝Ｍ_１・Ｍ_５・Ｍ_７・Ｍ_ｐ … を求めておき、行列Ｍ_1Sを乗算する。Ｍ_1Sは平行投影の
場合は式の行列と同じ形をもつから式の結果はｗ_si
＝１となるが、中心投影の場合はｗ_si＝１が成立せず、
次式による除算 を行い、これらの商の値を改めてx_si,y_si,z_siとする必
要がある。

第４図(c)は画面座標系に変換された基本立体の各面Ｓ
_ｉに関するデータで、各面Ｓ_ｉにつき、頂点系列の他、
三原色強度R_i,G_i,B_i及び外向き法線ベクトルのｚ_ｓ方向
成分ｎ′_ziをもっている。（R,G,B）の値として陰影を
付ける場合には、多面体全体に一定の色相（r,g,b）を
指定し、多面体が世界座標系内に置かれた時、ある光源
から照射した光の反射強度Ｉ_ｉを多面体の各面Ｓ_ｉに対
して計算し、 Ｒ_ｉ＝ｒ×Ｉ_ｉ，Ｇ_ｉ＝ｇ×Ｉ_ｉ，Ｂ_ｉ＝ｂ×Ｉ_ｉ
… をもって（R_i,G_i,B_i）とする。この処理は以下の手順で
行われる。まず、 〔x_wiy_wiz_wi1〕＝〔X_iY_iZ_i1〕・Ｍ_１・Ｍ_５・Ｍ_７
… により、基本立体データを世界座標系まで座標変換す
る。その結果を第５図に示す。多面体の各面Ｓ_ｉの反射
強度Ｉ_ｉはその面に立てた法線と光の入射方向との傾角
（入射角）θ_ｉの余弦によって決まるから、各面Ｓ_ｉの
単位法線ベクトルｎ_ｉ＝（n_xi,n_yi,n_zi）を求め、これ
と光源方向への単位ベクトルｌ＝（l_x,l_y,l_z）から Ｉ_ｉ＝Ｉ_ｏｃｏｓθ_ｉ＝I_o(l_xn_xi+l_yn_yi+l_zn_zi） …
を求める。ここにＩ_ｏは光源の強度、θ_ｉは入射角を示
す。面の法線ベクトルはその上の３点の座標値から計算
される。例えば第５図(a)に示すように面Ｓ_１の外向き
単位法線ベクトルｎ_１＝（n_x1,n_y1,n_z1）を求めるに
は、反時計回りの３つの頂点Ｖ_１，Ｖ_２，Ｖ_３を用いて
次のように計算する。

Ｎ_X1＝（y_w2-y_w1）（Z_w3-z_w1）−（y_w3-y_w1）（Z_w2-
z_w1） … Ｎ_y1＝（z_w2-z_w1）（x_w3-x_w1）−（z_w3-z_w1）（x_w2-
x_w1） … Ｎ_z1＝（x_w2-x_w1）（y_w3-y_w1）−（x_w3-x_w1）（y_w2-
y_w1） … 各面Ｓ_ｉの外向き法線ベクトルと反射強度の結果を第５
図(c)に示す。θ_ｉ＞180°の場合、式による反射強度
Ｉ_ｉが負の値をとり、その面は光源に対して裏となる
が、符号を反転した非負値−Ｉ_ｉはその面の内面を照射
する場合の反射強度を示している。こうして求められた
符号付の反射強度Ｉ_ｉに式により（r,g,b）を乗じた
ものが第４図(c)における（R_i,G_i,B_i）である。また、
平行投影の場合には、法線ベクトルを次式により画面座
標系に投影変換し、 〔ｎ′xi ｎ′yi ｎ′zi １〕 ＝〔nxi nyi nzi 1〕・Ｍ_ｐ … によって、中心投影の場合には画面座標系に投影変換さ
れた頂点座標を用いて式〜によって、ｎ′_ziのみを
求めて第４図(c)に示すように記憶すれば、ｎ′_ziの符
号は基本立体の外面が視点に対して表か裏かを示してい
る。ｎ′_zi＜０のときこの面は視点側を向いている表面
であるから前方面と呼び、ｎ′_zi＞０のときこの面は視
点と反対側を向いている裏面であるから後方面と呼ぶ。
単一の多面体では前方面のみを表示すればよいが、ＣＳ
Ｇ表現多面体では第１９図(d)における立体Ｂのように
基本立体の後方面が合成体の表面になり得るから、この
ような基本立体については後方面を表示する必要があ
る。

次に画面座標系に変換された基本立体データA_1S,A_2S,A
_3S,A_4Sを使って合成体の画像を構成する方法を説明す
る。以後の説明では、A_1S,A_2S,A_3S,A_4Sを改めてA₁,A₂,A
₃,A₄と書き、画面座標系においてA₁,A₂,A₃,A₄はいずれ
も凸多面体であると仮定する。また、画面座標系はｏ−
ｘｙｚと記す。

まず最も簡単な場合として、２つの凸多面体A₁,A₂の
和，差，積の表示方法を順に述べる。第６図は和Ａ_１∨
Ａ_２の、ｙ座標が一定の走査線を含む水平面（走査平
面）による断面図である。多面体A₁,A₂の断面は凸多角
形であって、斜線を施した領域が多面体Ａ_１∨Ａ_２の内
部である。この図の白丸印及び黒丸印・は多面体Ａ_１
及びＡ_２の前方面のみを走査変換した１行分の深度の付
与された画素を示している。視点はｚ軸上負の無限遠点
にあるから・印の画素が可視、印が不可視となる。ま
たA₁,A₂の後方面が不可視となることは第６図から明ら
かである。従ってＡ_１∨Ａ_２を表示するには、まずＡ_１
の前方面を順次走査変換して画像メモリ９及び第１のｚ
バッファメモリ１０に隠面消去を伴う書き込みを行い、
次にＡ_２の前方面について同じ処理を行えばよい。

第７図は２つの凸多面体A₁,A₂の積Ａ_１∧Ａ_２の走査平
面による断面図を示している。第７図(a)はＡ_１の前方
面の画素を印及び・印で示し、このうちＡ_２の内部に
ある・印の画素がＡ_１∧Ａ_２の前方面上にあることを示
している。第７図(b)はＡ_２の前方面のうち・印の画素
がＡ_１∧Ａ_２の前方面上にあることを示している。従っ
て合成体Ａ_１∧Ａ_２を表示するには、Ａ_１とＡ_２の前方
面を走査変換し、第７図(a)，(b)における・印の画素を
検出し、第１図の画像メモリ９及び第１のｚバッファメ
モリ１０に隠面消去を伴う書き込みを行えばよい。・印
の画素を選び出すためには、第２のｚバッファメモリ１
１、及び論理演算メモリ１２を使用する。

Ａ_１の前方面のうち、Ａ_２の内部を検出し表示する手順
を第８図に示す。最初にステップ１０１で第２のｚバッ
ファメモリ１１全体をｚ座標の最大値ｚ_maxで満たす。
次にステップ１０２でＡ_１の前方面を走査変換し、画素
列（X_i,y_i,z_i）ｉ＝1,2,…を得たとき、第２のｚバッフ
ァメモリ１１の（x_i,y_i）番地にｚ_ｉを書き込む。すな
わちｚ_ｉ→ｚ_ｓ（x_i,y_i）とする。次にステップ１０３
で論理演算メモリ１２全体を０で満たす。そして、ステ
ップ１０４でＡ_２の前方面を走査変換し、画素列（x_i,y
_i,z_i）ｉ＝1,2,…を得たとき、第２のｚバッファメモリ
１１の（x_i,y_i）番地の内容ｚ_ｓ（x_i,y_i）とｚ_ｉを比較
し、ｚ_ｉｚ_ｓ（x_i,y_i）が成立すれば論理演算メモリ
１２の（x_i,y_i）番地の値Ｃ_ｓ（x_i,y_i）を１だけ増加さ
せる。次にステップ１０５でＡ_２の後方面を走査変換
し、画素列（x_i,y_i,z_i）ｉ＝1,2,…を得たとき、ｚ_ｉ
ｚ_ｓ（x_i,y_i）が成立すればＣ_ｓ（x_i,y_i）を１だけ減少
させる。その結果、Ａ_１の前方面の画素のうち、Ａ_２の
前方面の背後にあり、かつＡ_２の後方面の手前にあるも
ののみがＣ_ｓ＝１の値を有し、その他の画素はＣ_ｓ＝０
となる。すなわち第７図の・印の画素はＣ_ｓ＝１とな
る。そこでステップ１０６で多面体Ａ_１の前方面を再び
走査変換し、三原色強度と深度を含む画素列（x_i,y_i,
z_i,R_i,G_i,B_i）ｉ＝1,2,…を得たとき、Ｃ_ｓ（x_i,y_i）＝
１かつｚ_ｉ＜ｚ_Ｍ（x_i,y_i）ならばｚ_ｉ→ｚ_Ｍ（x_i,
y_i），Ｒ_ｉ→Ｒ_Ｍ（x_i,y_i），Ｇ_ｉ→Ｇ_Ｍ（x_i,y_i），Ｂ
_ｉ→Ｂ_Ｍ（x_i,y_i）の書き込みを行う。その結果、Ａ_１
の前方面のうちＡ_２の内部及び境界の部分が隠面消去を
伴って画像メモリ９及び第１のｚバッファメモリ１０に
書き込まれる。以後、このような隠面消去を伴うメモリ
書き込みを単に「表示する」と記す。

次に、Ａ_２の前方面のうち、Ａ_１の内部を検出し表示す
る。その手順は第８図においてＡ_１とＡ_２を交換したも
のである。以上により多面体Ａ_１∧Ａ_２が表示される。

第９図は２つの凸面体A₁,A₂の差Ａ_１−Ａ_２の走査平面
上の断面を示している。同図(a)はＡ_１の前方面のうち
Ａ_２の外部にある画素・印がＡ_１−Ａ_２の前方面である
ことを示し、同図(b)はＡ_２の後方面のうちＡ_１の内部
にある画素・印がＡ_１−Ａ_２の前方面であることを示し
ている。Ａ_１の前方面のうちＡ_２の外部を表示する手順
は第８図のステップ１０６において、Ｃ_ｓ＝０かつｚ_ｉ
＜ｚ_Ｍのとき、z_i,R_i,G_i,B_iの書き込みを行えばよい。
Ａ_２の後方面のＡ_１の内部を表示する方法も同様であ
る。この場合、Ａ_２の内面はＡ_１−Ａ_２の外面になって
いる。

合成体の表面の三原色強度R_i,G_i,B_iの値を決定するには
以下の注意が必要である。第４図(c)に記載されている
（R_i,G_i,B_i）の値は基本立体の外面に対する三原色強度
を符号付きで示しているので、その基本立体の外面を表
示する場合には、（R_i,G_i,B_i）の値が非負であればその
まま、（R_i,G_i,B_i）が負であれば（0,0,0）に設定す
る。また、Ａ_１−Ａ_２におけるＡ_２のようにその基本立
体の内面を表示する場合には、（R_i,G_i,B_i）の符号を反
転して（-R_i,-G_i,-B_i）とし、これらの値が非負であれ
ばそのまま、負であれば（0,0,0）に設定する。しかし
この方法では光源に対して裏向きの面は黒レベルで表示
されることになるので、これを次のような方法で避け
る。光源からの直射光Ｉ_ｏによる散乱反射強度Ｉ_ｏ co
sθ_ｉに一定の周囲光強度Ｉ′_ｏを加え、式の代わり
に Ｉ_１＝Ｉ_ｏ cosθ_ｉ＋Ｉ′_ｏ … を反射強度とする。多面体の色相（r,g,b）にＩ′_ｏを
乗じた Ｒ′_ｏ＝ｒ×Ｉ′_ｏ，Ｇ′_ｏ＝ｇ×Ｉ′_ｏ，Ｂ′_ｏ＝ｂ
×Ｉ′_ｏ … を前記のように得られた非負の強度（R_i,G_i,B_i）に加算
した（Ｒ_ｉ＋Ｒ′_ｏ，Ｇ_ｉ＋Ｇ′_ｏ，Ｂ_ｉ＋Ｂ′_ｏ）を
周囲光の加味された三原色強度として画像メモリ９に書
き込む。一般に合成体の構成要素である各基本立体の外
面を表示すべきか内面を表示すべきかは、後述するよう
にCSGトリーを座標系に変換したとき、基本立体に反転
記号が付いているか否かより決定できるから、上記の各
面の三原色強度の計算は座標変換直後に実行し、その結
果を第４図(c)の（R_i,G_i,B_i）として第２の図形メモリ
５に記憶すればよい。

次に３つの凸多面体A₁,A₂,A₃の合成体の表示方法を種々
の合成式について説明する。第１０図(a)はＡ_１∨Ａ_２
∨Ａ_３の走査平面による断面を示しており、これを表示
するにはA₁,A₂,A₃の外面を順次走査変換して表示すれば
よい。第１０図(b)はＡ_１∧Ａ_２∧Ａ_３の断面を示して
おり、これを表示するには、Ａ_１の外面のＡ_２∧Ａ_３内
部、Ａ_２の外面のＡ_３∧Ａ_１内部、Ａ_３の外面のＡ_１∧
Ａ_２内部を順に表示すればよい。この操作を次式のよう
に表わす。

Ａ_１∧Ａ_２∧Ａ_３＝Ａ_１⊆（Ａ_２∧Ａ_３）＋Ａ_２⊆（Ａ_１∧Ａ_３）＋Ａ_３⊆（Ａ
_１∧Ａ_２） … ここにＡ_１⊆（Ａ_２∧Ａ_３）はＡ_１の外面のうちＡ_２∧
Ａ_３の内部を示しており、＋記号はこれによって結合さ
れた各項を順次表示すべきことを示している。Ａ_１⊆
（Ａ_２∧Ａ_３）を第２のｚバッファメモリ１１及び論理
演算メモリ１２を使って求める手順を第１１図に示す。
以下の説明では、論理演算メモリ１２の１画素に対する
１語を１６ビットとして第１２図に示すようにC_s,C_s1,C
_s2,…，Ｃ_s8に区分したものを使用する。まずステージ
２０１で多面体Ａ_１の前方面を描き、その深度をｚ_ｓに
書き込む。ステージ２０２でＡ_２の前方面及び後方面を
描き、Ａ_１の各画素がＡ_２の内部にあるか外部にあるか
を判定し、その結果をＣ_s1に書き込む。ステージ２０３
でＡ_３の前方面及び後方面を描き、Ａ_１の各画素がＡ_３
の内部にあるか外部にあるかを判定し、その結果をＣ_s2
に書き込む。ステージ２０４でＣ_s1∧Ｃ_s2→Ｃ_ｓなる論
理演算を画素毎に実行し、Ａ_２∧Ａ_３の内部にある画素
を検出する。ステージ２０５でＡ_１の前方面のR,G,B,z
を求め、Ｃ_ｓ＝１の画素のみを表示する。A₂,A₃につい
ても同様の方法で表示する。

第１０図(c)は（Ａ_１∧Ａ_２）−Ａ_３の断面を示す。こ
れを表示するにはＡ_１の外面のＡ_２∧_３内部、Ａ_２の
外面のＡ_１∧_３内部、Ａ_３の内面のＡ_１∧Ａ_２内部を
順に表示すればよい。この操作は次式のように表わされ
る。

（Ａ_１∧Ａ_２）−Ａ_３＝Ａ_１⊆（Ａ_２∧_３）＋Ａ_２⊆（Ａ_１∧_３）＋_３⊆
（Ａ_１∧Ａ_２） … ここにＡ_１⊆（Ａ_２∧_３）における_３は多面体Ａ_３
の外部領域を示しており、_３⊆（Ａ_１∧Ａ_２）におけ
る_３は多面体Ａ_３の内面を示している。内面を表示す
るにはその後方面のみを表示すればよい。Ａ_１⊆（Ａ_２
∧_３）をｚ_ｓ及びＣ_ｓを使って求める手順は第１１図
におけるステージ２０４をＣ_s1∧_s2→Ｃ_ｓと変更した
ものである。

第１０図(d)，(e)，(f)，(g)，(h)の合成体はそれぞれ
以下の操作で表示される。

Ａ_１−Ａ_２）−Ａ_３＝Ａ_１∧_２∧_３＝Ａ_１⊆（_２∧_３）＋_２⊆（Ａ_１
∧_３）＋_３⊆（Ａ_１∧_３） …… Ａ_１∨Ａ_２）∧Ａ_３＝Ａ_１⊆Ａ_３＋Ａ_２⊆Ａ_３＋Ａ_３⊆
（Ａ_１∨Ａ_２） …… （Ａ_１∧Ａ_２）∨Ａ_３＝Ａ_１⊆Ａ_２＋Ａ_２⊆Ａ_１＋Ａ_３
…… （Ａ_１∨Ａ_２）−Ａ_３＝Ａ_１⊆_３＋Ａ_２⊆_３＋_３
⊆（Ａ_１∨Ａ_２） …… Ａ_１−（Ａ_２−Ａ_３）＝Ａ_１∧_２∨Ａ_３）＝Ａ_１⊆（_２∨Ａ_３）＋_２⊆Ａ
_１＋Ａ_３⊆Ａ_１ …… 第１０図(b)〜(h)の太線は式〜によって表示すべき
基本立体の境界面を示したもので前方面，後方面の区別
はしていない。

次に、４個の多面体のＣＳＧトリーの表示方法を一例を
あげて説明する。第１３図(a)は４個の凸多面体Ａ_１，
Ａ_２，Ａ_３，Ａ_４の論理式 Ｆ＝（Ａ_１∨Ａ_２）−（Ａ_３∧Ａ_４） … による合成体ＦのＣＳＧトリーを示す。表示処理は次の
３ステップから成る。

(1)ＣＳＧトリーの標準形への変換 (2)反転表，関数表，干渉表の作成 (3)基本立体の順次表示処理 この中で(1)，(2)の処理は、基本立体毎の座標変換以前
に実行してもよい。

第１３図(a)のＣＳＧトリーを標準形に変換した結果を
第１３図(b)に示す。これは式の論理式を次式のよう
に差演算を含まない形に変換したもののＣＳＧトリーで
ある。

Ｆ＝（Ａ_１∨Ａ_２）∧（_３∨_４） … 標準形への変換方法を第１４図に示す。まずＣＳＧトリ
ー中のすべての差演算を第１４図(a)のように積演算と
反転演算に分解する。次にこれによって生じた反転演算
記号をトリーに沿って基本立体まで移動する。第１４図
(b)，(c)に示すようにトリーの節で和や積に出合った
ら、ドモルガンの法則に従って和を積に、積を和に変え
ることにより、分岐しながら移動できる。第１４図(d)
に示すようにトリーの枝で別の反転演算に出合ったなら
ば相殺消去する。最後に第１４図(e)に示すように反転
演算子の付いている基本立体Ａ_ｉを反転記号_ｉを使っ
て表現する。

第１３図(b)の標準形ＣＳＧトリーを使って、反転表，
関数表，干渉表を作成した結果を第１５図に示す。第１
５図(a)の反転表は基本立体毎に、反転＝１，非反転＝
０の区別を示す。第１５図(b)の関数表は式または式
を真理値表として展開したものである。第１６図はこ
の関数表を図示したものであり、Ａ_１〜Ａ_４の包含関係
とそれにより区分された各領域にA₄A₃A₂A₁の４ビットの
符号を記入し、Ｆが真となる領域に斜線を施したもので
ある。この図から合成体Ｆを表示する操作は次式で表わ
される。

Ｆ＝Ａ_１⊆（_３∨_４）＋Ａ_２⊆（_３∨_４）＋_３⊆（Ａ_１∨Ａ_２）＋
_４⊆（Ａ_１∨Ａ_２） …… すなわちＡ_１の外面の_３∨_４内部，Ａ_２の外面の
_３∨_４内部、Ａ_３の内面のＡ_１∨Ａ_２内部、Ａ_４の内
面のＡ_１∨Ａ_２内部を順次表示すればよい。第１６図の
太線は式に従って表示すべき基本立体の境界部分を示
している。式でＡ_１とＡ_２が相互干渉を不要としてい
るのは第１３図(b)でＡ_１とＡ_２が和演算∨で結ばれて
いるためであり、Ａ_３とＡ_４との関係も同様である。こ
のような基本立体間の相互干渉を示す表が干渉表であ
り、結果を第１５図(c)に示す。これを作成するには、
対角要素が０，非対角要素が１の行列を作り、第１３図
(b)のＣＳＧトリーにおいてＡ_１からＦに向かって進
み、和演算ノードに出合ったらその和の相手側に属する
すべてのＡ_ｉとの関係を不干渉とすべく行列の対応要素
に０を書き込む。これをA₂,A₃,A₄についても行う。

第１５図の３つの表を用いて基本立体の順次表示を行う
手順を第１７図に示す。これは３つの多面体のＣＳＧト
リーの表示手順を４個の多面体の場合に拡張したもので
ある。ステップ３０３及び３１７では第１５図(a)の反
転表を参照し、Ａ_ｉの前方面または後方面のいずれかを
走査変換する。ステップ３０９では第１５図(c)の干渉
表を参照し、値が０ならばＡ_ｉとＡ_ｊの干渉処理を省略
する。ステップ３１６では式の合成規則に従ってC_s1,
C_s2,C_s3,C_s4の論理演算を行っているがそれには第１５
図(b)の関数表をメモリ更新器８内に記憶しておき、Ａ
_１＝Ｃ_s1，Ａ_２＝Ｃ_s2，Ａ_３＝Ｃ_s3，Ａ_４＝Ｃ_s4として
この表を索引し、Ｆの値を求め、Ｃ_ｓに書き込めばよ
い。第１２図のＣ_s1〜Ｃ_s8を使用すれば、最大８個まで
の基本立体から合成された合成体を以上述べた処理手順
で表示することができる。例えば、８個の基本立体から
なる合成体であれば、ＣＳＧトリーの標準形への変換、
反転表、関数表、干渉表の作成の後、第１７図におい
て、ステップ３０５に記載の「Ｃ_s1〜Ｃ_s4を１で満た
す」を「Ｃ_s1〜Ｃ_s8を１で満たす」と変更し、ステップ
３０７に記載の「Ｃ_s1〜Ｃ_s4を０で満たす」を「Ｃ_s1〜
Ｃ_s8を０で満たす」と変更し、ステップ３１４に記載の
「ｊ＝４」を「ｊ＝８」と変更し、ステップ３１８に記
載の「ｊ＝４」を「ｊ＝８」と変更し、ステップ３１６
は、Ｃ_s1〜Ｃ_s8を用いて与えられた合成体の論理式の値
を求めて結果をＣｓとするように変更すればよい。

（発明の効果） 以上、詳細に説明したように本発明による３次元画像表
示装置を用いれば、ＣＳＧ表現から境界表現への変換を
せずに直接表示することが可能となり、多面体間の交差
を陽に求めるための大量で複雑な処理が不要となる。本
発明の装置によるＣＳＧ多面体の表示処理は、座標変換
器、多角形の走査変換器のような従来のハードウェアで
装備されている高速な演算装置やメモリの増設手段を用
いて実現できるので、高速化が可能である。従って本発
明はソリッドモデリングシステムの利用者が試行錯誤的
に繰り返し設定するＣＳＧ表現モデルをディスプレイを
介して対話的に検証するのに適している。また、本発明
によれば、所望の形状が得られた時点で改めてホストプ
ロセッサ等が時間をかけて境界表現に変換すればよく、
境界表現の多面体も従来の処理手順により高速に表示す
ることができる。

【図面の簡単な説明】

第１図は本発明に係る３次元画像表示装置の構成を示す
ブロック図、第２図は変形したＣＳＧトリーを示す図、
第３図は基本立体の定義法の説明図、第４図は画面座標
系に変換された基本立体データの説明図、第５図は世界
座標系に変換された基本立体データの説明図、第６図は
多面体の和の断面図、第７図は多面体の積の断面図、第
８図は多面体の積の表示処理手順を示すフローチャー
ト、第９図は多面体の差の断面図、第１０図は３個の多
面体のＣＳＧ演算を示す断面図、第１１図は３個の多面
体のＣＳＧトリーの表示処理手順を示すフローチャー
ト、第１２図は論理演算メモリの区分を示す図、第１３
図は４個の多面体のＣＳＧトリー例を示す図、第１４図
はＣＳＧトリーの標準形への変換法の説明図、第１５図
はＣＳＧトリーの表示に用いられる表を示す図、第１６
図は基本立体の包含関係を示す図、第１７図は４個の基
本立体のＣＳＧトリーの表示処理手順を示すフローチャ
ート、第１８図は従来の３次元画像表示装置の構成を示
すブロック図、第１９図は従来の多面体モデル作成方法
の説明図、第２０図は基本立体の合成方法の説明図であ
る。 １……ホストプロセッサ、 ２……ホストインタフェース、 ３……制御プロセッサ、４……第１の図形メモリ、 ５……第２の図形メモリ、６……座標変換器、 ７……走査変換器、８……メモリ更新器、 ９……画像メモリ、 １０……第１のｚバッファメモリ、 １１……第２のｚバッファメモリ、 １２……論理演算メモリ。

Claims (1)

【特許請求の範囲】
1. 【請求項１】多面体のＣＳＧ表現データとその構成要素
   である基本立体データとを記憶する第１の図形メモリ
   と、 基本立体データに対し、該ＣＳＧ表現及び視点情報にし
   たがって座標変換及び投影変換を施す座標変換器と、 変換された基本立体データを記憶する第２の図形メモリ
   と、 基本立体を囲む多角形を走査変換して三原色強度及び深
   度をもつ画素データに分解する走査変換器と、 画面上の画素毎に３次元画像の三原色強度を記憶する画
   像メモリと、画素毎に深度を一時記憶する第１のｚバッ
   ファメモリと、 ＣＳＧ表現における基本立体のうちの１つだけの前方面
   または後方面を走査変換したときの構成画素の深度のみ
   を一時記憶する第２のｚバッファメモリと、 該基本立体の前方面または後方面の構成画素の各々につ
   きそれが他の基本立体の内部か外部かを判定してその結
   果を記憶する論理演算メモリと、 深度の付与された画素データを隠面消去しつつ画像メモ
   リ及び第１のｚバッファメモリに書き込む操作、第２の
   ｚバッファメモリ及び論理演算メモリの制御を行なうメ
   モリ更新器とを設け、 メモリ更新器は、 （ａ）前記多面体のＣＳＧ表現を変換して作成される基
   本立体毎の反転表、基本立体間の干渉表、ＣＳＧ論理式
   の関数表をもち、 （ｂ）予め前記画像メモリを背景色で、第１のｚバッフ
   ァメモリを深度の最大値で満たし、 （ｃ）ＣＳＧ表現を構成する１つの特定の基本立体を前
   記反転表の値に従って、前方面または後方面のいずれか
   を走査変換し、深度分布を第２のｚバッファメモリに作
   成し、 （ｄ）前記（ｃ）の処理で前方面を走査変換した場合は
   論理演算メモリの内外判定結果部分を１で満たし、前記
   （ｃ）の処理で後方面を走査変換した場合は論理演算メ
   モリの内外判定結果部分を０で満たし、 （ｅ）前記干渉表の値に従って該基本立体と干渉する他
   の基本立体の各々について前方面と後方面を走査変換
   し、 （ｆ）前記第２のｚバッファメモリに記憶された深度
   が、該前方面及び後方面の間にあるか否かを論理演算メ
   モリの判定用カウンタを用いて画素毎に判定し、判定結
   果を論理演算メモリの内外判定結果部分に書き込み、 （ｇ）該内外判定結果の組合せの値を用いて前記関数表
   の関数値を画素毎に求め、関数値が１である可視画素と
   ０である不可視画素とに判別し、 （ｈ）前記特定の基本立体の前方面または後方面を再び
   走査変換して三原色強度及び深度を求め、前記関数値が
   １である可視画素について、深度が第１のｚバッファメ
   モリの対応する画素の深度より小さい場合に第１のｚバ
   ッファメモリ及び画像メモリの値を更新することによ
   り、前記特定の基本立体の表面の一部を表示し、 （ｉ）前記（ｃ）〜（ｈ）の処理を、ＣＳＧ表現の全基
   本立体について順次行なうことにより、 ＣＳＧ表現による多面体の３次元画像を表示することを
   特徴とする３次元画像表示装置。