JPH0724074B2

JPH0724074B2 - 画像シェーディング方法及び記憶装置ローディング方法

Info

Publication number: JPH0724074B2
Application number: JP1279605A
Authority: JP
Inventors: ジョン・シー・ダルリンプル; ブイ・ビー・スレシュクマー
Original assignee: テクトロニックス・インコーポレイテッド
Priority date: 1988-10-27
Filing date: 1989-10-26
Publication date: 1995-03-15
Anticipated expiration: 2010-03-15
Also published as: EP0366463A3; US5142617A; EP0366463B1; DE68927471D1; DE68927471T2; EP0366463A2; JPH02171877A

Description

【発明の詳細な説明】［産業上の利用分野］本発明は、コンピュータ・グラフィックス・システムに
於ける画像のシェーディング（陰影付け）方法及び記憶
装置ローディング方法に関する。

［従来技術及び発明が解決しようとする課題］コンピュータ・グラフィック・システムにおいて、陰極
線管（CRT）や他の表示装置のスクリーン上に画像を表
示する。一般に、CRTの電子ビームは、Ｘ（水平）成分
及びＹ（垂直）成分から成るデジタル信号の制御に基づ
いて偏向され、スクリーン上の長方形の格子点配列のピ
クセル（画素）がラスタ・パターンに従って１行ずつ走
査される。画像プロセッサが発生した画像データは、フ
レーム・バッファ・メモリにロード（記憶）される。フ
レーム・バッファは、CRTのスクリーン上の格子点（ピ
クセル）に１対１に対応する記憶位置を有している。以
下の説明では、フレーム・バッファの記憶位置は、便宜
上、スクリーン上の格子点配列に対応した長方形配列状
に物理的に配置されているものとして扱う。

CRTの電子ビームの偏向制御に用いられるデジタル信号
は、フレーム・バッファのアドレス制御にも用いられ
る。格子点のピクセルに表示される色は、フレーム・バ
ッファの対応する記憶位置の内容によって決まる。従っ
て、フレーム・バッファは、CRTスクリーン上の表示の
仮想的な画像データを含んでいる。画像プロセッサから
フレーム・バッファに送られるデータは、色塗り領域で
構成された画像を表すものでも良い。色塗り領域を表す
データ値をフレーム・バッファ・メモリにロードする過
程をタイリングと呼んでいる。以下の説明では、タイリ
ング動作に関連して特定の格子点のタイリング及び三角
形のタイリングについて説明する。しかし、これは、特
定の格子点に対応する記憶位置のタイリング、及び三角
形の中に含まれている格子点に対応する記憶位置のタイ
リングを簡単に説明する為の便宜的な意図に基づいてい
るに過ぎない。

コンピュータ・グラフィックス・システムを用いて３次
元曲面を描くことも出来る。この場合、曲面を三角形の
微小面に分解し、これらの三角形の投影図を２次元表示
面上に表示する。各三角形の微小面は、２次元表示面に
投影されると、三角形又は直線要素となる。投影により
三角形が直線要素となった場合は、ここでは考えない。
３次元空間で三角形の微小面を定義している情報は、画
像プロセッサによって決められる。画像プリセッサは、
この情報を用いて対応する表示面の三角形を定義する情
報を発生する。画像プロセッサが発生したこの情報は、
レンダリング・エンジンに供給される。レンダリング・
エンジンは、シェーディング処理した輝度値Ｉをフレー
ム・バッファにロードするのに用いられる。画像プロセ
ッサは、一般に三角形の微小面の情報を順次処理する。

正確な表示画像を得る為に、次の事実を考慮する必要が
ある。即ち、３次元の物体を調べる場合、観測者から見
てこの物体の反対側にある表面は見えないので、これら
見えない表面（隠面）を表すデータをフレーム・バッフ
ァにロードすべきではないという問題がある。コンピュ
ータ・グラフィックス・システムでは、これは隠面消去
法により処理される。隠面消去法に関しては、ニューマ
ン（Newman）及びスプロール（Sproull）による「対話
型コンピュータ・グラフィックスの原理（Principle of
Interactive Computer Graphics）」の第２版（マグロ
ウヒル社1979年刊）に説明されている。

所定の格子点のタイリングの為にフレーム・バッファ・
メモリにロードされたデータは、表示される曲面上の対
応する点から観測者に向かって反射される光の色及び強
度を表している。ここの説明では、このデータは、輝度
値Ｉを表すが、実際には、例えば赤、緑及び青の輝度の
ような別々の色成分の輝度を表す複数の値でも良い。あ
る格子点の輝度値Ｉが、その格子点の表す表面要素の位
置及び方向を考慮に入れたものであれば、一般に表面の
３次元表現は、極めて写実的に表示されよう。この表示
を行う為には、表面要素の表面法線ベクトルを計算し、
光源モデルを適用することにより、その表面要素を表す
格子点の輝度値Ｉを求めることが出来る。光源及び表面
反射率を考慮するには複雑な計算が必要になるので、格
子点の輝度値を計算する為に光源モデルを使用すると、
計算量が過大となるという点に留意されたい。

フレーム・バッファにロードされる所定の格子点の輝度
値は、表示面に適用されるシェーディング・モデルによ
って決まる。３つの主なシェーディング・モデルがジェ
ー・ディー・フォレイ（J.D.Foley）及びエイ・バン・
ダム（A.Van Dam）による「対話型コンピュータ・グラ
フィックスの基礎（Fundamentals of Interactive Comp
uter Graphics）」（1984年刊）の580〜584頁に記載さ
れている。これら３つのシェーディング・モデルとは、
一定シェーディングと、輝度補間シェーディング（即
ち、ゴーラード・シェーディング）と、法線ベクトル補
間シェーディング（即ち、フォング・シェーディング）
である。一定シェーディング・モデルは、所定の表示領
域に対して一定の輝度値を与えるので、曲面を表現する
際には、ゴーラード（Gouraud）やフォング（Phong）の
シェーディング・モデルの場合ほど満足出来る画像は得
られない。

三角形の微小面を表す表示面三角形を使用するゴーラー
ド・シェーディングでは、微小面の各頂点について頂点
面法線が与えられ、選択された光源モデルを対応する頂
点法線に適用し、各対応する表示面の頂点について頂点
輝度が求められる。この計算された輝度値を基本とし
て、三角形の各辺の輝度及び各走査線上の辺の間の輝度
を直線補間することにより、表示面三角形に陰影付けを
する。従って、ゴーラードの方法によって三角形に陰影
付けするには、選択された光源モデルを一旦各頂点に接
近させる。フォングによる三角形の陰影付け方法では、
頂点面法線が与えられる。走査線と交差する三角形の辺
の両端の頂点法線を補間することにより、三角形の辺と
各走査線との交点に対して端点法線が計算される。走査
線上の各ピクセルについて、その走査線の端点ベクトル
を補間することにより、表面法線ベクトルが計算され
る。表面法線ベクトルは、ピクセル毎に存在し、各ピク
セル毎の表面法線ベクトルに選択された光源モデルが適
用され、陰影付けされた輝度値が計算される。光源モデ
ルは、三角形の総ての格子点について計算されるので、
フォング・シェーディングは、ゴーラード・シェーディ
ングより長い実行時間を必要とする。しかし、フォング
・シェーディングでは、各格子点に対応する各表面要素
の位置及び方向を考慮しているので、物体をより写実的
に表現することが出来る。

従って、本発明の目的は、計算量を余り過大にすること
なく、写実性の良好な商品位の陰影付けを可能にする画
像シェーディング方法及び記憶装置ローディング方法を
提供することである。

［課題を解決する為の手段及び作用］本発明の好適実施例によれば、複数の記憶位置を含む記
憶装置へデータをロードする方法を開示している。この
記憶装置の各記憶位置は、長方形配列の格子点に夫々対
応するＸ成分及びＹ成分を有するアドレスで唯１つ定義
可能であり、少なくとも３つの頂点（X0,Y0）、（X1,Y
1）、（X2,Y2）及びこれらの頂点に関連する表面法線ベ
クトルによって決まる表示領域内の記憶位置にデータを
ロード（即ち、タイリング）することが必要である。本
発明のロード方法では、点（X0,Y0）と点（X1,Y1）及び
点（X2,Y2）を夫々結ぶ線上に夫々点（X3,Y3）及び点
（X4,Y4）を定義する。これにより、点（X0,Y0）、（X
3,Y3）及び（X4,Y4）によってサブ領域が定義される。
点（X3,Y3）及び（X4,Y4）の表面法線ベクトルは、点
（X0,Y0）、（X1,Y1）及び（X2,Y2）に関する表面法線
ベクトルを補間することにより導かれる。点（X0,Y
0）、（X3,Y3）及び（X4,Y4）の輝度値I0、I3及びI4
は、これらに関連する表面法線ベクトルに光源モデルを
適用することにより計算される。上記サブ領域に対応す
る記憶位置に、これらI0、I3及びI4から導かれた輝度値
がロードされる。

好適実施例によれば、タイリングの為の「親」三角形が
曲面をモデル化しており、この親三角形は、３つの頂点
及び曲面の法線方向の頂点に対応する３つの表面法線ベ
クトルによって定義される。互いに合同なサブ三角形
は、親三角形の各辺を二等分して定められ、また、親三
角形の表面法線ベクトルを補間することにより、各サブ
三角形の表面法線ベクトルが導かれる。各サブ三角形を
テストして、ゴーラード・シェーディングが好適か否か
を判断する。ゴーラード・シェーディングが適切でない
と判断されたサブ三角形は、更に分割され、これら分割
された新たなサブ三角形がテストされ、ゴーラード・シ
ェーディングに好適か否かが判断される。ゴーラード・
シェーディングに好適と判断されたサブ三角形は、頂点
表面法線ベクトルを最初に光源モデルに適用し、頂点の
輝度値を求め、サブ三角形の内部の両端の輝度値を補間
することによりタイリングされる。

以上の構成により、実質的に必要とされる画像の写実性
に応じて、計算量を過大にすることなく、必要且つ十分
な品質のシェーディング処理方法を実現することが出来
る。

［実施例］第３図は、本発明を適用するのに好適なコンピュータ・
グラフィックス・システムのブロック図である。画像プ
ロセッサ（１）は、表示リストを受け、三角形を表す情
報を作成し、これらの三角形を定義する情報を順次XYア
ドレス発生器（２）及びＩ（輝度値）発生器（６）に送
る。XYアドレス発生器（２）に関しては、米国特許出願
第113031号（特開平1-147682号公報参照）及び米国特許
出願第113045号（特開平1-134579号公報参照）に記載さ
れている。Ｉ発生器（６）に関しても、米国特許出願第
113045号（特開平1-134579号公報参照）に記載されてい
る。XYアドレス発生器（２）は、改良型のブレセンハム
（Bresenham）のアルゴリズムを実行し、表示面三角形
の中の格子点を選択し、フレーム・バッファ・メモリ
（５）をアドレスする為にＸアドレス・レジスタ（３）
及びＹアドレス・レジスタ（４）に夫々Ｘ及びＹアドレ
スを供給する。Ｉ発生器は、ゴーラード・シェーディン
グを実行し、上記アドレス発生器（２）によって選択さ
れた格子点の各々の輝度値をフレーム・バッファ・メモ
リ（５）に供給する。

第２図は、表示面三角形及び網目状の格子点の一部分を
表す図で、中央の三角形は３つの頂点V0、V1及びV2を有
する。第２図の格子点は、縦座標値Ｙ及び横座標値Ｘで
表される。三角形V0V1V2は、コンピュータ・グラフィッ
クス・システムが画像表現の便宜の為に、曲面の一部分
を多数の微小三角形に分割し、曲面をモデル化している
これらの三角形を表示面上に投影したものである。画像
プロセッサ（１）が受ける表示リストは、各微小三角形
の頂点のワールド座標（X,Y,Z）と、各頂点に対応し
（X,Y,Z）成分を有する表面法線ベクトルを含んでお
り、表面法線ベクトルは、対応する頂点の付近の微小三
角形でモデル化された曲面の法線を表す。画像プロセッ
サ（１）は、対応する表面法線ベクトルに適当な光源モ
デルを適用し、その頂点の輝度値Ｉを計算する。

本発明の説明の便宜上、先ず、３つの頂点の座標値及び
対応する表面法線ベクトルによって定義される三角形の
ゴーラード・シェーディングに関して説明する。輝度値
Ｉ（即ち、I0、I1及びI2）は、夫々の頂点に適当な光源
モデルを適用することにより、各頂点について計算され
る。三角形をタイリングする為に、先ず、XYアドレス発
生器（２）及びＩ発生器（６）は初期状態に設定され、
XYアドレス発生器（２）のレジスタには、タイリング領
域を定義するデータがロードされ、Ｉ発生器のレジスタ
には、初期輝度値及び輝度値の増分（インクリメント）
値がロードされる。その後、XYアドレス発生器（２）及
びＩ発生器（６）は、動作状態に設定され、これらの動
作は、マスタ・クロックの連続サイクルに従って順次所
定の状態に進んで行くステート・マシンによって制御さ
れる。

ゴーラード・シェーディングは、下から上に１行ずつ実
行される。従って、画像プロセッサ（１）は、三角形の
頂点をＹの値が増加する順序で並べ替え（ソーティン
グ）をする。第２図の三角形ではY0＜Y1＜Y2なので、こ
の微小三角形は、頂点V0を含む行から頂点V2を含む行に
向かってタイリングされる。各行は、左から右へ、又は
右から左へ何れの方向でタイリングしても良い。

三角形は、縦座標の最小値から最大値まで延びる２本の
「側線（siding）」を有すると考えられる。第２図の三
角形V0V1V2は、側線V0V2及びV0V1V2を有する。これら側
線の一方を「主側線」として選択すると、他方が「副側
線」と考えられる。各行のタイリングは、主側線から反
対側の副側線へ実行される。一般に、主側線は、辺の数
がより少ない側が選択される。主側線を左又は右の何れ
にするかは、頂点V0から延びる２本の辺のクロス積（外
積）を評価することにより決定される。従って、第１図
の場合、側線V0V2が主側線として選択され、タイリング
は左から右へ実行される。

改良型ブレセンハム・アルゴリズムを実行するには、三
角形の各辺について１組のブレセンハムパラメータが必
要である。これらのパラメータは、DX（Ｘの変化量）、
DY（Ｙの変化量）、ｓ｛floor（DX/DY）で計算された整
数値で表された直線の傾き｝、PInc（DX-sDY-DYで計算
された正の増分）、NInc（DX-sDYで計算された負の増
分）、AErr（初期エラー）、X₀（種格子点のＸ座標）及
びY₀（種格子点のＹ座標）である。（尚、floorは、フ
ロア演算子で、floorXは、Ｘの値を超えない最大の整数
を表す。）三角形の２辺間を結ぶ一連の格子線をタイリ
ングするには、これらの辺のブレセンハム・パラメータ
をXYアドレス発生器（２）にロードしなければならな
い。

画像プロセッサ（１）は、三角形の各頂点について頂点
データ構造を作成する。各頂点データ構造は、頂点の位
置についての座標値Ｘ、Ｙ及びＺと、頂点表面法線ベク
トル成分値（X,Y,Z）を含んでいる。カラー成分、例え
ば赤、緑及び青の輝度値を各頂点データ構造の中に入れ
ても良い。この頂点データ構造は、装置（デバイス）又
は選択された変換関数によって得られた各頂点のピクセ
ル座標値も含んでも良い。各頂点データ構造は、三角形
の１辺に対応する１組のブレセンハム・パラメータを記
憶する。頂点V0に対応する頂点データ構造辺V0V1に関す
るブレセンハム・パラメータを記憶し、頂点V1に対応す
る頂点データ構造は、辺V1V2に関するパラメータを記憶
し、頂点V2に対応する頂点データ構造は、辺V2V0に関す
るパラメータを記憶する。

頂点データ構造に含まれる情報により画像プロセッサ
（１）がXYアドレス発生器（２）及びＩ発生器（６）を
起動し、ゴーラード・シェーディング技法に関して改良
型ブレセンハム・アルゴリズムを実行し、表示領域のタ
イリングを行える。特に、一方が主側線を構成し、他方
が副側線を構成している三角形の２本の辺は、各走査
線、即ち格子行がタイリングされる際に「アクティブ」
と考えられ、頂点データ構造の情報は、両方のアクティ
ブな辺に交差する一連の走査線をタイリングする前に、
XYアドレス発生器（２）及びＩ発生器（６）を初期化す
るのに用いられる。従って、XYアドレス発生器（２）の
初期化の際に、頂点データ構造が参照され、次の値がXY
アドレス発生器のレジスタにロードされる。即ち、これ
らのパラメータは、AErrM、AErrm、PIncM、PIncm、NInc
M、NIncm、DYM、DYm、sM、sm、XM、Xm及び右から左又は
左から右のタイリング方向を示す論理値である。尚、最
後に「Ｍ」を付したパラメータは、主側線に関するもの
を意味し、最後に「ｍ」を付したパラメータは、副側線
に関するものを意味している。

Ｉ発生器（６）は、XYアドレス発生器（２）が発生した
各座標値（X,Y）についての輝度値Ｉを発生する。ゴー
ラード・シェーディングでは、Ｉの値は、垂直方向及び
水平方向の何れに対しても線形的に変化すると仮定され
ている。従って、頂点V0、V1及びV2の輝度値I0、I1及び
I2は、Ｘ及びＹの面方程式を満たし、これらＸ及びＹか
ら水平輝度増分及び垂直輝度増分が計算される。最初
に、画像プロセッサ（１）は、水平及び垂直の増分値を
Ｉ発生器（６）にロードし、輝度値Ｉの初期値を計算し
てタイリングする最初の格子点を決定する。この初期値
もＩ発生器（６）にロードされる。

初期化後、XYアドレス発生器（２）及びＩ発生器（６）
は、動作状態となる。この状態では、アドレス発生器
（２）及びＩ発生器（６）は同期して動作し、改良型ブ
レセンハム・アルゴリズム及びゴーラード・シェーディ
ング・モデルに従って三角形のタイリングを実行する。
XYアドレス発生器（２）は、各行の最初にタイリングす
るピクセルのＸ座標を計算し、各行のタイリングされる
ピクセルの数Hrzを計算し、タイリングの方向（右から
左又は左から右）も決定する。Ｉ発生器（６）は、XYア
ドレス発生器（２）によってアドレスされた各格子点の
輝度値Ｉを供給する。上記米国特許出願第113031号（特
開平1-147682号公報）から判るように、Hrzの値は、三
角形の最下行では計算されないので、最下行はタイリン
グされないことに留意されたい。しかし、三角形の最上
行はタイリングされる。同様に、右側線（第２図では側
線V0V1V2）と格子行との厳密な交点のフロア値の格子
点、左側線と格子行との厳密な交点のフロア値に１を加
算した格子点、及び上記２つの格子点の間の総ての格子
点がタイリングされる。従って、三角形がモザイク状に
隣接している場合、隣接する三角形の境界の格子点は、
１つの格子点として扱われ、２つの隣接する三角形は１
つの三角形と同様となる。これにより、三角形の間に隙
間が出来たり、三角形が重なったりするのを確実に防止
出来る。

この方法による三角形V0V1V2のゴーラード・シェーディ
ングは、三角形の表す曲面部分が略平面であれば、満足
出来る結果が得られる。しかし、これは確実な仮定では
ないので、この方法によるゴーラード・シェーディング
の結果は、フォング・シェーディングの結果と比較して
常に満足出来るものとは限らない。他方、フォング・シ
ェーディングは、計算量が多く、曲面を略正確に表現す
る際に必ずしも必要でない場合もある。

このゴーラード・シェーディングの使用効果の制限を回
避し、フォング・シェーディングによる計算量の増加を
回避する為に、フォング及びゴーラードのシェーディン
グ技法を組み合わせて使用する。第１図に示すように、
三角形V0V1V2は、各辺を二等分し、各二等分点を結ぶこ
とにより、４つの合同なサブ三角形に分割し得る。各サ
ブ三角形の３つの頂点データ構造は、親三角形の頂点デ
ータ構造と同じパラメータを含むデータ構造として構成
される。新しい頂点位置の座標値及び表面法線ベクトル
成分は、補間によって得られる。例えば、辺V0V1、V1V2
及びV0V2の二等分点は夫々V01、V12及びV02と表され、
頂点V0、V1及びV2の座標値から補間により得られた座標
値となる。各二等分点の表面法線ベクトル成分も点V0、
V1及びV2の表面法線ベクトル成分から補間により得られ
る。ゴーラード・シェーディングが好適ではないと判断
された場合には、サブ三角形は、同様の方法により更に
細かく分割しても良いし、好適であれば、ゴーラード・
シェーディングで処理される。従って、表面法線ベクト
ル補間、即ちフォング・シェーディング技法の使用は制
限される。サブ三角形がゴーラード・シェーディングに
好適な場合、輝度値は各頂点毎に計算され、サブ三角形
は、輝度値の線形補間、即ち、ゴーラード・シェーディ
ング技法によってタイリングされる。

三角形の再分割は、ワールド空間か又はピクセル空間で
実行し得る。ワールド空間で実行された場合、ゴーラー
ド・シェーディングのステップは、ワールド座標をピク
セル座標に変化する変換関数を含んでいなければならな
い。ピクセル空間で実行された場合、三角形の再分割の
前に三角形の頂点の座標はピクセル座標に変換され、ゴ
ーラード・シェーディングのステップは上述のように実
行される。以下の説明では、再分割は、ピクセル空間で
実行されたものと仮定している。

サブ三角形は二等分点で形成されているので、サブ三角
形の各辺は、親三角形の対応する辺に平行である。従っ
て、サブ三角形の各辺のDX/DY、ｓ、PInc及びNIncの値
は、親三角形の対応する辺のDX/DY、ｓ、PInc及びNInc
の値に夫々等しい。これらのパラメータの値は、親三角
形より直接求められるので、サブ三角形の頂点は、ピク
セル座標に変換してブレセンハムのパラメータを計算す
る必要はなく、そのような座標変換に於ける丸め誤差を
避けることが出来る。

再分割アルゴリズムは、再帰的手順として特に役立ち、
それによって親三角形は、最初の入力パラメータとな
り、この親三角形を分割したサブ三角形が、ゴーラード
・シェーディングに好適か否かによって後で実行される
再分割処理の対象となる。従って、親三角形を繰り返し
再分割し、曲面のより微小で平面的な部分に対応する多
くのサブ三角形を作成し、親三角形よりも更にゴーラー
ド・シェーディングの処理に適合させても良い。実際
に、各サブ三角形はゴーラード・シェーディングに適合
すると考えられ、ゴーラード・シェーディングを実行す
る為には、各サブ三角形の辺のAErr値（初期エラー値）
及び種格子点（X0,Y0）を計算することにより、各サブ
三角形の頂点の頂点データ構造を作成しなければならな
い。この種格子点（X0,Y0）は、対象となる辺に基づい
てタイリングを開始する点を示し、AErr値は、点（X0,Y
0）から対象となる辺までのＸ方向の距離を示してい
る。

親三角形の再帰的な再分割を説明する為に、親三角形と
して三角形V0V1V2を考える。この三角形V0V1V2の各頂点
は、タイリングの為に位置座標及び表面法線ベクトルに
よって定義されている。以下の説明では、位置座標は、
接頭文字ｘ、ｙ及びｚで表し、表面法線ベクトル成分
は、接頭文字ａ、ｂ及びｃで表す。従って、親三角形の
頂点は、以下に示す位置パラメータ及び表面法線ベクト
ル・パラメータに関連している。即ち、頂点V0:（x0,y0,z0）及び（a0,b0,c0）頂点V1:（x1,y1,z1）及び（a1,b1,c1）頂点V2:（x2,y2,z2）及び（a2,b2,c2）である。

再帰的手順を呼び出す前に、親三角形の頂点V0、V1及び
V2をデバイス（ピクセル）座標に変換し、これら変換さ
れた頂点は、Ｙ成分の上昇方向順に並べ替えられる。こ
の例では、V0のＹ成分が最も小さく、V2のＹ成分が最も
大きい。親三角形の各辺のブレセンハムの増分パラメー
タが、各頂点のデバイス座標（ピクセル座標）を用いて
計算され、適当な頂点データ構造に記憶される。

辺V1V0に対して、 DY10 ＝y1−y0 DX10 ＝x1−x0 slope10＝DX10/DY10 s10 ＝floor（slope10） PInc10 ＝DX10−s10＊DY10−DY10 NInc10 ＝DX10−s10＊DY10 辺V2V1に対して、 DY21 ＝y2−y1 DX21 ＝x2−x1 slope21＝DX21/DY21 s21 ＝floor（slope21） PInc21 ＝DX21−s21＊DY21−DY21 NInc21 ＝DX21−s21＊DY21 辺V2V0に対して、 DY20 ＝y2−y0 DX20 ＝x2−x0 slope20＝DX20/DY20 s20 ＝floor（slope20） PInc20 ＝DX20−s20＊DY20−DY20 NIic20 ＝DX20−s20＊DY20 これらのブレセンハム・パラメータは、親三角形を分割
したどのサブ三角形にも適用可能であり、各サブ三角形
の頂点は、自動的にＹ成分値に従って並べ替えられる。
何故なら、サブ三角形は親三角形と同様であり、親三角
形の頂点は既にＹ成分値に従って並べ替え済みだからで
ある。

次のステップは、親三角形がゴーラード・シェーディン
グに好適か否かを判断することである。後で詳細に説明
するように、ゴーラード・シェーディングへの適合性を
判断するにはいくつかの方法が用いられる。

親三角形がゴーラード・シェーディングに好適であると
判断されると、上述のシェーディング手順により親三角
形の陰影付けが実行される。好適でないと判断される
と、親三角形の頂点データ構造は、次の再帰的手順「PS
EUDO_PHONG（擬似フォング処理）」に渡される。ローカ
ル変数V01、V02及びV12は、夫々辺V0V1、V0V2及びV1V2
の二等分点に対応する頂点データ構造である。以下に擬
似フォング処理の手順をパスカル（PASCAL）言語で書い
た例を示す。尚、／＊及び＊／で挟まれた部分は注釈で
ある。

PSEUDO_PHONG（V0,V1,V2） vertex V01,V02,V12 begin pseudo_phong ／＊辺V0V2の二等分点V02を求める＊／ V02.x:＝（V0.x＋V2.x）/2 V02.y:＝（V0.y＋V2.y）/2 V02.z:＝（V0.z＋V2.z）/2 ／＊二等分点V02の表面法線ベクトルを求める＊／ V02.a:＝（V0.a＋V2.a） V02.b:＝（V0.b＋V2.b） V02.c:＝（V0.c＋V2.c） L:＝NORM（V02.a,V02.b,V02.c） V02.a:＝V02.a/L V02.b:＝V02.b/L V02.c:＝V02.c/L ／＊辺V0V1の二等分点V01を求める＊／ V01.x:＝（V0.x＋V1.x）/2 V01.y:＝（V0.y＋V1.y）/2 V01.z:＝（V0.z＋V1.z）/2 ／＊二等分点V01の表面法線ベクトルを求める＊／ V01.a:＝（V0.a＋V1.a） V01.b:＝（V0.b＋V1.b） V01.c:＝（V0.c＋V1.c） L:＝NORM（V01.a,V01.b,V01.c） V01.a:＝V01.a/L V01.b:＝V01.b/L V01.c:＝V01.c/L ／＊辺V1V2の二等分点V12を求める＊／ V12.x:＝（V1.x＋V2.x）/2 V12.y:＝（V1.y＋V2.y）/2 V12.z:＝（V1.z＋V2.z）/2 ／＊二等分点V12の表面法線ベクトルを求める＊／ V12.a:＝（V1.a＋V2.a） V12.b:＝（V1.b＋V2.b） V12.c:＝（V1.c＋V2.c） L:＝NORM（V12.a,V12.b,V12.c） V12.a:＝V12.a/L V12.b:＝V12.b/L V12.c:＝V12.c/L ／＊各サブ三角形をテストし、ゴーラード・シェーディ
ングが好適であるか、又は更に再分割が必要であるかを
判断する＊／／＊三角形V01V12V02に対して＊／ if（RECURSE_CONDITION（V01,V12,V02）） then PSEUDO_PHONG（V01,V12,V02） else GOURAUD_SHADE（V01,V12,V02）／＊三角形V0V01V02に対して＊／ if（RECURSE_CONDITION（V0,V01,V02）） then PSEUDO_PHONG（V0,V01,V02） else GOURAUD_SHADE（V0,V01,V02）／＊三角形V01V1V12に対して＊／ if（RECURSE_CONDITION（V01,V1,V12）） then PSEUDO_PHONG（V01,V1,V12） else GOURAUD_SHADE（V01,V1,V12）／＊三角形V02V12V2に対して＊／ if（RECURSE_CONDITION（V02,V12,V2）） then PSEUDO_PHONG（V02,V12,V2） else GOURAUD_SHADE（V02,V12,V2） end pseudo_phong 繰り返しの深さは、ブール関数RECURSE_CONDITIONによ
って判断されるので、三角形の付近の表面の曲率の近似
値を調べることにより、その値に適応するように決めて
も良い。ゼロ番目を含む繰り返しの各レベルで、単位長
の表面法線ベクトルが三角形又はサブ三角形の各頂点に
ついて計算される。これは、単位長の法線ベクトルが光
源モデルの計算に必要となるからである。三角形（又は
サブ三角形）の３つの頂点表面法線は比較され、それら
のドット積（内積）を計算し、それらがどの程度１に近
いかを判断する。尚、２つの単位ベクトルのドット積
は、両ベクトル間の角度のコサインに等しい。これら３
つのドット積が、所望の写実性の程度によって決まる所
定の値を超えると、三角形（又はサブ三角形）の付近の
表面が平坦であると仮定する。上述の操作の代わりに、
２つのベクトルのクロス積（外積）を計算し、その値を
ゼロと比較しても良い。このクロス積の値が十分ゼロに
近ければ、三角形又はサブ三角形は十分に平坦であると
考えて良く、その三角形（又はサブ三角形）のゴーラー
ド・シェーディングは、無限遠の点光源を用いた拡散光
源モデルに対して満足出来る結果が得られよう。

更に、再分割の繰り返しをデバイス（ピクセル）座標に
おけるサブ三角形の大きさの関数にしても良い。この繰
り返しのあるレベルで、総てのサブ三角形は合同で同じ
大きさなので、再分割の繰り返しにおいて大きさの制限
を設けることにより、同じ回数だけ各サブ三角形に分割
する結果となる。しかし、隣接する表示面又は親三角形
は、大きさが異なることもあるので、その場合には、同
じ回数だけ分割されるとは限らない。再分割がワールド
空間で実行される場合、この方法では隣接する三角形の
境界に新しい頂点が導入されるので、親三角形間に隙間
や重複が発生する可能性が生じるが、実際には問題にな
らない。本発明の一実施例では、繰り返しの深さは、各
表示面三角形に対して４回の繰り返しに限定されてお
り、これにより、各表示面三角形を256個のサブ三角形
に分割し、そして満足出来る結果を得ている。

この繰り返しの深さは、記憶出来るパラメータの数によ
って制限される。従って、各サブ三角形毎にパラメータ
が追加され、これらのパラメータを次の再分割の為に記
憶しなければならない。そして、これら記憶可能なパラ
メータの総数が制限されていると、実行可能な再分割処
理の数も制限される。

関数NORMは、ベクトルの長さ、即ち値を返す関数で、種
々の方法で実現出来る。極めて正確であるが、計算負荷
が大きいNORM関数の例は次のようなものである。

NORM（a,b,c）＝square_root（ａ＊ａ＋ｂ＊ｂ＋ｃ＊
ｃ）少し精度は劣るがより高速な関数の例として、 NORM（a,b,c）＝MAX（ABS（ａ）,ABS（ｂ）,ABS
（ｃ））がある。ここで、関数ABSは、引数の絶対値を返すもの
である。ベクトルの長さＬが与えられると、単位表面法
線ベクトルは、補間された表面法線ベクトルから各成分
をＬで割算することにより得られる。

三角形の再分割処理がワールド空間で実行されると、手
順GOURAUD_SHADEにより、三角形の頂点はピクセル空間
に変換される。ピクセル空間で再分割処理が実行される
と、手順GOURAUD_SHADEは、上述のゴーラード・シェー
ディングの処理に従って動作する。

三角形又はサブ三角形がゴーラード・シェーディングに
好適であると一旦判断されると、各辺についてAErr値及
び種格子点（X0,Y0）を計算して、３つの頂点の頂点デ
ータ構造を作成しなければならない。サブ三角形の頂点
は格子点に一致する必要はないので、格子点に頂点を有
する親三角形の場合とサブ三角形のパラメータの計算は
少し異なっている。ブレセンハムのアルゴリズムを変数
の増分計算に用い、走査線の所定の格子点の位置を求め
る。特定のサブ三角形をタイリングする際には、あたか
もブレセンハムのアルゴリズムにより親三角形をタイリ
ングし、丁度そのサブ三角形に処理が及んだかのよう
に、AErr、X0及びY0の値を求める必要がある。サブ三角
形の領域にタイリング処理が達した瞬間にこれらの値を
求める為に、擬似的に親三角形をタイリングしているか
のようにブレセンハムのアルゴリズムを実行することが
出来る。しかし、以下に述べる計算によれば、この作業
をもっと効率的に実行することが出来る。今、三角形V0
1V012V02の辺V01V12を考える。親三角形の頂点データ構
造、即ち、親三角形V0V1V2の辺V0V2の値から、このサブ
三角形の辺V01V12のPInc、NInc及びｓの値が求められ
る。従って、 slope＝DX20/DY20 ｓ＝floor（slope）となる。

サブ三角形V01V12V02をタイリングする為に、辺V01V12
のAErr及び種格子点（X0,Y0）の値を計算するには、 Y₀ ＝floor（V01.y） X₀real＝V01.x−slope＊（V01.y−Y0） X₀ ＝floor（X₀real） AERR＝floor（（（X₀real＋slope）−（X₀＋ｓ）−１）
＊DY20）のようになる。辺V01V12が左側にあるならば、この辺の
開始Ｘ値は、X₀＋１となり、右側にあるならば、X₀とな
る。

このように、辺V01V12についての必要なブレセンハム・
パラメータが総て求められた。即ち、ｓ、PInc、及びNI
ncは、親三角形から得られ、AErr、X₀及びY₀は、上述の
ように計算される。同様の計算を実行することにより、
他の辺V12V02及びV02V01のブレセンハム・パラメータも
得られる。頂点V01、V12及びV02の輝度値の計算は、選
択された光源モデルを夫々の頂点表面法線ベクトルに適
用することにより導かれる。そして、サブ三角形V01V12
V02は、XYアドレス発生器（２）及びＩ発生器（６）を
用いて上述のようにゴーラード・シェーディング技法に
より陰影処理される。

以上説明した表示領域のシェーディング方法は、従来の
フォング・シェーディング技法に比較して計算量は少な
いにもかかわらず、視覚的に略同等の表示結果を得るこ
とが出来る。三角形の辺を二等分して形成したサブ三角
形のシェーディングの為にブレセンハムのアルゴリズム
を使用した場合、親三角形の領域について計算したブレ
センハムの増分パラメータは、再分割したサブ三角形に
ついても適用することが出来る。

以上本発明の好適実施例について説明したが、本発明は
ここに説明した実施例のみに限定されるものではなく、
本発明の要旨を逸脱することなく必要に応じて種々の変
形及び変更を実施し得ることは当業者には明らかであ
る。例えば、比較的程度の低い写実性で構わなければ、
一定シェーディングを実行することが出来るので、サブ
三角形に対して必ずしもゴーラード・シェーディングを
実行する必要はない。更に再分割するか否かを判断する
為にドット積を計算する場合、三角形（又はサブ三角
形）の３つの単位頂点法線ベクトルの内、２つのベクト
ルのドット積が略１であれば、３つ目のベクトルも１に
近い値になるので、３つの総てのベクトルについて計算
する必要はない。

本発明の方法は、三角形の辺の二等分により４つの合同
なサブ三角形に分割するという方法に限定して適用され
るものではない。サブ三角形は、別の方法により形成し
ても良い。例えば、親三角形を再分割する際に、１辺の
二等分点を求め、この点に対向する頂点とを結んで親三
角形を２つのサブ三角形に分割しても良い。この場合、
位置座標の値及び表面法線ベクトル成分は、二等分され
た辺の両端から補間により求められる。

［発明の効果］本発明の画像シェーディング方法及び記憶装置ローディ
ング方法によれば、三角形の微小面に関して、例えばゴ
ーラード・シェーディングや一定シェーディングのよう
に計算負荷の軽い技法を適用しても所望の写実性を表現
できるまでサブ三角形に再分割し、フォング・シェーデ
ィングのように計算負荷の大きな技法を使用する格子点
（ピクセル）の数を減少させるようにしたので、従来の
ように、フォング技法等を総ての格子点に適用する場合
に比べ計算負荷を軽くすることが出来る上に、実質的に
必要十分な写実性を有する画像を表現することが出来
る。

【図面の簡単な説明】

第１図は、本発明に係る方法を説明する為の画像をモデ
ル化した三角形微小面の再分割図、第２図は、曲面を複
数の三角形微小面によりモデル化した際の概略図、第３
図は、本発明の方法を適用するのに好適なコンピュータ
・グラフィックス・システムの基本的な構成を示すブロ
ック図である。 V0V1V2:三角形微小面（親三角形） V0V01V02:サブ三角形 V01V1V12:サブ三角形 V02V12V2:サブ三角形 V01V12V02:サブ三角形（１）：画像プロセッサ（２）:XYアドレス発生器（５）：フレーム・バッファ・メモリ（６）:I発生器

Claims

【特許請求の範囲】

【請求項１】各頂点に法線ベクトルが関連付けられた三
角形表面の画像に陰影付けする画像シェーディング方法
であって、上記三角形の各辺上に１つずつ合計３つの点を定義し、
該３つの点を相互接続することにより、４つのサブ三角
形を形成し、上記三角形表面の頂点の法線ベクトルを計
算し、上記三角形の３つの頂点の法線ベクトルを線形補間する
ことにより、上記３つの点の法線ベクトルを計算し、上記サブ三角形の３つの頂点の法線ベクトルに基づいて
上記サブ三角形表面の平坦性を判断し、上記サブ三角形
の平坦性が十分である場合に、これら３つの頂点の輝度
値を計算し、これら計算された輝度値を線形補間するこ
とにより上記サブ三角形の内部の点の輝度値を求めるこ
とを特徴とする画像シェーディング方法。
【請求項２】長方形の格子点配列の格子点に夫々対応す
るＸ成分及びＹ成分を含むアドレスにより一意的に指定
可能な複数の記憶位置を有する記憶装置に対して、上記
格子点配列の中で、夫々法線ベクトルN0,N1及びN2が与
えられた３つの格子点（X0,Y0）、（X1,Y1）及び（X2,Y
2）により定義される三角形の領域内の格子点に対応す
る記憶位置に輝度データをロードする記憶装置ローディ
ング方法であって、上記格子点（X0,Y0）と、上記格子点（X1,Y1）及び（X
2,Y2）とを夫々結ぶ直線上に格子点（X3,Y3）及び（X4,
Y4）を求めることにより、上記格子点（X0,Y0）、（X3,
Y3）及び（X4,Y4）によりサブ三角形を定義し、上記法線ベクトルN0,N1及びN2を線形補間することによ
り、上記格子点（X3,Y3）及び（X4,Y4）についての法線
ベクトルN3及びN4を夫々求め、上記法線ベクトルN0,N3及びN4に基づいて上記サブ三角
形表面の平坦性を判断し、上記サブ三角形の平坦性が十分である場合に、これら３
つの頂点の輝度値I0,I3及びI4を計算し、該輝度値I0,I3及びI4を線形補間することにより、上記
サブ三角形内部の格子点に対応する輝度値を求め、該輝
度値データを対応する記憶位置にロードすることを特徴
とする記憶装置ローディング方法。