JP2000227966A

JP2000227966A - ３ｄコンピュ―タ・グラフィックス処理装置及び方法

Info

Publication number: JP2000227966A
Application number: JP2000027708A
Authority: JP
Inventors: Graham John Dunnett; ジョンダンネットグラハム; Holger Heinrichh Gruen; ハインリッヒグリューンホルガー
Original assignee: Canon Inc
Current assignee: Canon Inc
Priority date: 1999-02-04
Filing date: 2000-02-04
Publication date: 2000-08-15
Also published as: US7027050B1; EP1026639A2; US7034823B2; US20040075655A1; EP1026639A3

Abstract

(57)【要約】（修正有）【課題】多数の表現でモデル化されるオブジェクトに
対して、計算量を少くし、またポリゴンの一層の細分割
法を提供する。【解決手段】３次元オブジェクトがオブジェクト面に
近似する三角形のメッシュを使用してモデル化される。
画像表示のために、各三角形は、この元の三角形と同じ
平面にある必要のない、より小さい三角形に細分割さ
れ、オブジェクト面の湾曲度はより正確にモデル化でき
る。バーンスタイン−ベジエ三角形パッチ又はヘロン・
パッチのようなパラメータ的パッチが、各三角形をより
小さい非平面三角形に分割するか決定するのに使用され
る。加えて非平面三角形の数が、画像データの現在又は
前回フレーム中の元の三角形のサイズを使用して決定さ
れる。非平面三角形は、非平面三角形の同数を必要とす
る次のフレーム中で使用するために記憶され、各新しい
非平面三角形の頂点の明度値が計算され、次の新しい三
角形のための明度値の決定に使用される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は３次元（３Ｄ）コン
ピュータ・グラフィックス、より詳しくはオブジェクト
面をレンダリングすること、オブジェクト面のシェーデ
ィング（又はライティング）すること、及び／又はレン
ダリングするためにオブジェクト面の表現の細分割（サ
ブディビジョン）を多角形（ポリゴン）にすることに関
する。

【０００２】

【従来の技術】３Ｄコンピュータ・グラフィックスにお
いて、３次元オブジェクトは普通、オブジェクトの面に
接近している多角形のメッシュを用いて表わされる。オ
ブジェクト面がより複雑になればなるほど、多角形はま
すますそれを正確にモデルにすることが必要になる。し
かし、多角形の数が増加するにつれて、オブジェクトの
画像表示を実行しなければならない処理操作が増える。
これは各多角形が処理されなければならず、また、多角
形の全てを記憶するのに必要とする記憶容量も増えるか
らである。従って、多くの３Ｄグラフィックス・システ
ムはできるだけ少ない多角形を使用することが試みられ
ている。それゆえに、この種のシステムの一つの問題
は、低い多角形表現のために面の曲率が失われることで
ある。これがモデルの画像をして滑らかさの代わりに切
り子面を生ぜしめることになる。

【０００３】D.E.Breen による１９８６年フォール・ジ
ョイント・コンピュータ会議議事録、９３１−９４０ペ
ージ、ＩＥＥＥカタログ番号86CH2345-7、「ステイナー
・パッチ・モザイク細工の成形及びスムーズ−シェイデ
ィング(Creation and Smooth-Shading of Steiner Patc
h Tessellations)」には、その面がバイパラメータ状パ
ッチの特定タイプ、すなわち、超長楕円面として本来モ
デル化される３次元面をシェーディングする方法が開示
されており、すなわち、この超長楕円面は三角形に均一
に細分割され、また、各三角形はステイナー・パッチに
近似し、ステイナー・パッチの連続メッシュを生成す
る。得られたメッシュをレンダリングするために、ステ
イナー・パッチはレイ・トレーシングされ、またパッチ
が光線によって交差されたときは、座標と交点における
ノーマル（法線）が決定される。得られる結果から、高
品質ーレイ・トレーシング・コンピュータ・アニメーシ
ョンを生成するコンピュータ操作費用と時間の軽減の可
能性を提供する方法と言われる。しかし、この方法は一
般目的として、特にリアル・タイムのコンピュータ・グ
ラフィックスにおいては多くの問題を含んでいる。例え
ば、この方法は超長楕円面から出発し、次いでステイナ
・パッチに近似する均一な三角形ができるように細分割
(sub-divided)される。この均一な細分割は、単一のノ
ーマルが一つより多い三角形によって分割された頂点で
規定され、これによって得られた−ステイナー・パッチ
・モザイクの滑らかなシェーディングが許容されること
を保証するのに欠くことができない。しかし、これらの
必要条件は不当に限定的であり、不正確また非能率なモ
デリングにつながる。さらに、レンダリングに使用され
るレイ−トレーシング技術は、コンピュータ処理の必要
条件をさらに増加させる。

【０００４】３Ｄコンピュータ・グラフィックスにおい
て、オブジェクトのモデルの画像を表示するために、オ
ブジェクト面による画像中に生成する光度値(light int
ensity values)を計算する必要がある。

【０００５】これを実行するためのある技術、例えばレ
イ−トレーシング法は、画像の各画素のための明度値
（ライト・バリュー：light value）を計算する。しか
し、これらの方法はコンピュータ処理上高価であり、か
つ、リアルタイム・アプリケーションに対してはしばし
ば不適当である。

【０００６】他の技術は画像中のある画素のみの明度値
を計算し、また、残りの画素については補間によって計
算される。この方法はグロー・シェイディングとして知
られており、表示されるべきオブジェクトのモデルを形
成する多角形の頂点における光度を計算し、次いでこれ
らの頂点の値間を補間することによって実行される。し
かし、この方法においてさえも、明度値はモデル中の各
多角形の各頂点に対して計算しなければならず、従っ
て、多角形の数が増える（例えば、オブジェクトをより
正確にモデルする）につれて、実行しなければならない
光度計算の回数も増えることになる。さらに、この方法
は上述したように各多角形の内側のポイントに対する明
度値が直接計算ではなく補間によって決定されるので、
画像中に不正確さが生じる。これらの不正確さは多角形
によってモデル化されたオブジェクト面の曲率の増大に
つれて増大する。これは真の光度値が、多角形によって
モデル化されたオブジェクト面の曲率の増大につれて多
角形を、より横切って変化するからである（また、より
小さい多角形が多数使用されると、頂点の数、従って明
度計算の回数が増える）。

【０００７】３Ｄコンピュータ・グラフィックスにおい
て、また特に対話型リアル・タイム・コンピュータ・グ
ラフィックスにおいて、オブジェクトのコンピュータ・
モデルは多数回処理され、それが異なる３Ｄ座標系（例
えば、モデルが記憶された３Ｄ「オブジェクト・スペー
ス」及び全てのオブジェクト及び光源等のための「ワー
ルド・スペース」）間で変換される。各変換を実行する
ために、モデルを規定する全てのポイントが変換されな
ければならず、計算（コンピュータ処理）上高くつく。

【０００８】従って、多くのコンピュータ・モデルは、
オブジェクトをモデルにするのに少ないポイント数を使
用して、変換を実行するのに必要とされる計算回数を減
じ、次いで変換後、処理を実行してレンダリングのため
の多数のポイントによって規定されたモデルを形成し画
像を表示することが試行されている。

【０００９】例えば、一つのアプローチにおいて、ベジ
エ・パッチないしＢ−スプライン・パッチのようなパラ
メータ状面パッチがオブジェクト面の一部（パーツ）を
表現するのに使用される。変換後、オブジェクトの画像
をレンダリングするために、面パッチがフラットな多角
形に細分割され、これが従来の方法でレンダリングされ
る。

【００１０】面部分の表現を処理してレンダリングする
ために多角形を規定する多数の方法が知られている。

【００１１】例えば、アディソン−ウエスリ・パブリッ
シング・カンパニ(Addison-WesleyPublishing Company)
刊、フォリ、ヴァン・ダム、フェイナとヒューズ(Fole
y,van Dam, Feiner and Hughes) による「コンピュータ
・グラフィックスの原理及び方法」第２版、ISBN0-201-
12110-7、523-528頁により、効果的により多くのポイン
トを発生する再帰（リカーシブ）ないし反復細分割ベジ
エ・パッチとして知られており、実際のオブジェクト面
と接近させる近似方法がある。それからレンダリングは
ポイントを使用して、フラット・エッジ多角形、普通、
四辺形又は好ましくは三角形を規定して実行され、その
後、それぞれの画素が走査変換として知られる処理によ
って多角形内の域に割り当てられる。各反復後、十分な
分割が実行されたかどうか決定する必要があり、従っ
て、フラットネス・テストが各細分割の実行された後に
行なわれる。

【００１２】上述の「コンピュータ・グラフィックスの
原理及び方法」には、各細分割が固定深さまで再帰細分
割を実行した後、フラットネス・テストを実行し、これ
によって、ある余分な細分割の費用のかかるフラットネ
ス・テストを回避する別の方法も開示されている。

【００１３】ＥＰ−Ａ−０３６６４６３はグラフィクス
画像をシェディングする方法を開示しており、ここでは
３次元のカーブ面の三角形一面形成部分が、副三角形が
グロー・シェディングのために十分フラットになるま
で、反復して細分割される。反復の深さの各反復のゼロ
を含む各レベルにおいてテストを実行し、三角形又は副
三角形の各頂点における単位長さ面ノーマル・ベクトル
を計算すること、及びこれをそのドット・プロダクツの
計算によって比較してどれだけ単一性に接近しているか
を決定することによって決定される。三つのドット・プ
ロダクツの各々が所定値を超えておれば、三角形／副三
角形の近傍する面がプラナー（平面）であると想定され
る。加うるに、反復は副三角形のサイズの関数となり、
また、各三角形の４回の反復コールにおける反覆の深さ
を固定することは（これによってこれが２５６個の副三
角形に分割される）、満足のいく結果をもたらすことが
分る。

【００１４】ＥＰ−Ａ−０５９６６６７には、ベジエ・
パスを細分割する方法が開示されており、細分割のレベ
ルを決定するために細分割を実行する前に、そのパッチ
の極率がテストされる。

【００１５】３Ｄコンピュータ・グラフィックスにおい
て、また特に対話型リアル・タイム・コンピュータ・グ
ラフィックスにおいて、オブジェクトのコンピュータ・
モデルは多数回処理され、それが異なる３Ｄ座標系（例
えば、モデルが記憶された３Ｄ「オブジェクト・スペー
ス」及び全てのオブジェクト及び光源等のための「ワー
ルド・スペース」）間で変換される。各変換を実行する
ために、そのモデルを規定する全てのポイントが変換さ
れなければならず、コンピュータ処理上高つく。

【００１６】従って、多くのコンピュータ・モデルは、
オブジェクトをモデルにするのに少ないポイント数を使
用して、変換を実行するのに必要とされる計算回数を減
じ、次いで変換後、処理を実行してレンダリングの多数
のポイント数によって規定されたモデルを形成し画像を
表示することが試行されている。

【００１７】例えば、一つのアプローチにおいて、ベジ
エ・パッチないしＢ−スプライン・パッチのようなパラ
メータ状面パッチがオブジェクト面の一部（パーツ）を
表現するのに使用される。変換後、オブジェクトの画像
をレンダリングするために、面パッチがフラットな多角
形に細分割され、これが従来の方法でレンダリングされ
る。

【００１８】

【発明が解決しようとする課題】しかし、従来の方法は
多数の問題がある。例えば、レンダリングのために表現
を多角形に変換するのに必要とされる処理は、特に多数
の表現でモデル化されるオブジェクトに対して、また画
像データの一連のフレームが、各フレーム中の各表現の
ために実行された処理によって発生される場合におい
て、計算量が多く、時間がかかる。

【００１９】本発明は上記問題点に鑑みてなされたもの
であり、一つの態様において、本発明は多角形（ポリゴ
ン）のさらなる細分割方法を提供することを目的として
いる。

【００２０】

【課題を解決するための手段】本発明によれば、多角形
からなる面の第１モデルが、複数の面パッチを介してこ
れも多角形からなる面の第２モデルに変換される３次元
オブジェクト面の画像をレンダリングするのに使用する
処理装置又は方法を提供する。

【００２１】本発明はさらに、そのパラメータ状面パッ
チが曲面のモデルを形成する多角形の少なくともいくつ
かのために規定され、その面に近似する多数のより小さ
い多角形が面パッチを用いて生成される処理方法又は装
置を備える。より小さい多角形は、元の多角形と同じ平
面に置く必要はなく、従って、曲面をより優れたモデル
にできる。

【００２２】本発明は更に、３次元内の曲面の少なくと
も一部をモデル化する多角形が、各多角形のための各曲
面パッチを規定するように処理され、この処理が各元の
多角形を、対応する面パッチに依存する頂点を有する別
の多角形と置換するように実行される。

【００２３】本発明の実施の形態は、多くの３Ｄコンピ
ュータ・グラフィックス・アプリケーションに広く使用
される従来の多角形モデルを、より正確な多角形モデル
に置換させることができる。次いで、この置換モデルは
従来環境、分散及び／又は鏡面光度式(diffuse and/or
specular lighting equations)によって評価することが
でき、レイートレース(ray-traced)を必要としない。

【００２４】本発明によれば、３次元オブジェクトのモ
デルの一部を形成する多角形が、多角形のための明度値
を規定する面パッチを計算する工程と；面パッチを使用
する複数のポイントにおける明度値を計算する工程と；
計算された明度値間を補間する工程と；によってシェー
ドされる処理装置又は方法が提供される。

【００２５】面パッチを使用して計算される明度値にお
けるポイントは、元の多角形がさらに分割される多角形
の頂点に対応するか、又は明度値が利用可能な多数のポ
イントが増えるように使用された多角形内の付加的なポ
イントとなり、これによって続く補間の精度が高まる。

【００２６】本発明はまた３次元面のモデルをレンダリ
ングするのに使用するための明度値を規定する面パッチ
を計算する装置又は方法を提供する。

【００２７】本発明はさらに多角形のための明度値を計
算する装置又は方法を提供し、その明度値が多角形の複
数の第１ポイントのために計算され、計算された明度値
が面パッチを規定するのに使用され、面パッチが複数の
第２ポイントのための計算に使用される。複数の第２ポ
イントは複数の第１ポイントの数よりも大きい。

【００２８】本発明によれば、３次元曲面の少なくとも
一部の表現が、その表現のサイズに基づいて細分割され
る装置又は方法が提供される。

【００２９】表現は多角形か、あるいは面パッチであ
る。

【００３０】サイズは表現の面積（エリア）である。

【００３１】このサイズは画像データの前回のフレーム
中又は現在のフレーム中のサイズである。

【００３２】本発明はまた、レンダリングするための多
角形を発生するための装置又は方法を提供し、その多角
形の数は最初の表現のサイズ・パラメータに依存して決
定される。

【００３３】本発明によれば、複数のフレームのための
画像データを発生する複数の表現のモデルをレンダリン
グする方法又は装置を提供し、その各表現は所与のフレ
ームのための同数の多角形に分割され、多角形を規定す
るデータが次の使用のために、同じ範囲に分割されるべ
き表現を必要とするフレーム内に記憶される。

【００３４】この方法において、試験が各フレームにつ
き実行され、モデル内の表現の全てに対する細分割深さ
を規定するとともに、この深さに対する多角形を規定す
るデータが既に記憶されておれば、多角形を再計算する
よりも、この記憶データが使用される。そうでなければ
多角形が計算され、データが次の使用のために記憶され
る。

【００３５】本発明は、また３次元オブジェクトの画像
をレンダリングするのに使用する多角形を発生する装置
又は方法を提供し、発生されるべき多角形の数が決定さ
れ、多角形のこの数のデータが既に記憶されておれば、
この記憶データが使用され、一方、データが未だ記憶さ
れていなければ、多角形を規定するデータが発生され
る。

【００３６】本発明はまた、３次元オブジェクトのモデ
ルを形成する表現を処理する装置又は方法を提供し、各
表現がレンダリングのために同数の多角形に変換され
る。多角形を規定するデータが、所与の数の多角形に変
換されるべき表現を必要とする画像内で使用するために
記憶される。

【００３７】

【発明の実施の形態】ここで本発明の実施の形態を添付
図面を参照して例としのみ説明し、同様の参照数字は同
じか、又は類似のものを示す。

【００３８】図１を参照して、一実施の形態における３
Ｄグラフィックス処理装置の機能要素のブロック図を示
す。

【００３９】図１の装置において、メモリ６に接続され
た中央処理装置（ＣＰＵ）４を含むプログラム可能コン
ピュータ２が設けられ、ＣＰＵ４によって実行されるべ
き動作を規定するプログラムと、ＣＰＵ４にって処理さ
れるべきデータと、ＣＰＵよって処理されたデータを記
憶するように動作可能である。

【００４０】メモリ６にはディスク・ドライブ８が接続
されており、このディスクドライブ８は、ディスク１０
のような取り外し可能なデータ記憶媒体を許容するよう
に動作可能であり、かつ、これに記憶されたデータをメ
モリ６に伝送することができる。

【００４１】ＣＰＵ４の入力ポートには、例えばキーボ
ード及び／又はマウス、トラックボール等のような位置
検出入力デバイスを含むユーザ命令入力デバイス１４が
接続されている。

【００４２】さらに、ＣＰＵ４には、従来の方法で配置
されたメモリ・ユニットを含み、ＣＰＵ４によって発生
された少なくとも一つの画像に関する画像データを記憶
するフレーム・バッファ１６が接続されている。一つ
（又は数個）のメモリ位置が画像の画素のために設けら
れ、また各画素のためのフレーム・バッファに記憶され
た値が画像中のその画素の色又は輝度を規定する。

【００４３】フレーム・バッファ１６には、従来の方法
でフレーム・バッファ１６内に記憶された画像データを
使用する画像を表示するための表示ユニット１８が接続
されている。さらに、フレーム・バッファ１６にはビデ
オ・テープ・レコーダ（ＶＴＲ）２０又は他の画像デー
タ記録デバイスが接続されている。

【００４４】高データ記憶容量を有するハード・ディス
ク・ドライブのような大容量記憶デバイス２２が、メモ
リ６（一般的にＣＰＵ４を介して）に、さらにフレーム
・バッファ１６にも接続されている。この大容量記憶デ
バイス２２はメモリ６からＣＰＵ４によって処理された
データ、又はディスプレイ装置１８に表示されるべきフ
レーム・バッファ１６からのデータを受信する。

【００４５】コンピュータ２をして本発明の実施の形態
に係る処理を実行する作動命令が、ディスク１０に記憶
されたプログラムの形態で商業的に供給でき、又は他の
データ記憶媒体（及びディスク・ドライブ８を介しての
コンピュータへの入力）が、信号として例えばインター
ネットのようなデータリンク（図示省略）を介してコン
ピュータ２に伝送され、又は入力デバイス１４を介して
ユーザによって入力することができ、これによって受信
コンピュータ２が本実施の形態の装置に変更される。

【００４６】ＣＰＵ４によって処理されるべきデータ
は、ディスク・ドライブ８を使用して取り外し可能デー
タ記憶媒体からコンピュータ２に入力できる。別の方法
として、あるいは付加的に、処理されるべきデータがこ
のデータを記憶しているローカルないしリモート・デー
タベースから接続部（図示省略）を介してメモリ６にダ
ウンロードすることができる。加うるに、処理されるべ
きデータは、例えば放送信号としてコンピュータ２に伝
送できる。従って、コンピュータ２は「セットトップ・
ボックス」の形態をとり、テレビ１８と併用される構成
とすることができ、放送データを受信し、このデータを
処理して処理画像をテレビ１８上に表示することができ
る。

【００４７】図２Ａ及び図２Ｂは図１の装置によってこ
の実施の形態で実行される処理操作を示すフローチャー
トである。

【００４８】図２Ａ，２Ｂを参照して、処理が各々３次
元オブジェクト・スペース内にある一つ又はそれ以上を
規定する３次元モデリング・データでステップＳ２で開
始される。このデータは各オブジェクトの多角形メッシ
ュ・モデルを含み、このオブジェクトは３Ｄオブジェク
ト・スペース内のモデルを構成する各多角形の頂点の位
置と、頂点を結ぶ線となると考えることのできる連結情
報とを含んでいる。これらの線はモデル内の多角形の境
界線である。３Ｄモデリング・データは、また各多角形
の光特性（すなわち、多角形の環境、分散及び鏡面反射
係数）を規定する情報を含んでいる。

【００４９】ステップＳ２における３Ｄモデリング・デ
ータは、ディスク・ドライブ８を介してディスク１０の
ような記憶媒体上のコンピュータ２に入力され、インタ
ーネットのような通信回線を介してコンピュータ２へ、
例えば他のコンピュータ又はデータベースから伝送さ
れ、又は例えば放送信号のような信号としてコンピュー
タ２によって受信される。別の方法として、３Ｄモデリ
ング・データは市場で入手可能なモデリング・パッケー
ジ及びユーザ入力デバイス１４を介してユーザからの情
報を使用してコンピュータ２内に発生することができ
る。

【００５０】ステップＳ４において、ＣＰＵ４が、ステ
ップＳ２で受信した３Ｄモデリング・データが必要とさ
れるフォーマットであるかどうかを決定し、もしそうで
なければ、このデータを必要なフォーマットに変換す
る。

【００５１】図３はステップＳ４においてＣＰＵ４によ
って実行される処理操作を示すフローチャートである。

【００５２】図３を参照して、ステップＳ５０におい
て、ＣＰＵ４が次のオブジェクトのモデルを規定する３
Ｄモデリング・データを考慮する（これが最初のオブジ
ェクトとなり、最初にこのステップが実行される）。

【００５３】ステップＳ５２において、ＣＰＵ４はモデ
ルが三角形状の多角形からなるかどうかを決定する。ス
テップＳ５２において、考慮されたオブジェクトのモデ
ルが三角形状の多角形で構成されていないと決定されれ
ば、次いでステップＳ５４において、ＣＰＵ４が各多角
形を、各多角形の頂点を連結することで三角形に変換し
て、従来方法による三角形を形成する。

【００５４】ステップＳ５４において三角形への変換に
続き、あるいはモデルが既に三角形状多角形で形成され
ていることがステップＳ５２で決定されれば、ステップ
Ｓ５６において、ＣＰＵ４が、考慮されたオブジェクト
のモデルが各三角形状の多角形の各頂点としてノーマル
（正常）であると規定されたかどうかを決定する。

【００５５】ステップＳ５６において、モデルが各頂点
でノーマル（法線）を規定しないと決定されれば、次い
でステップＳ５８において、ＣＰＵ４が従来方法で各三
角形状の多角形の各頂点でノーマルを計算する。従来方
法としては、例えば、デビッド・エフ・ロジャーズによ
る「コンピュータ・グラフィックスのための手順上の基
準(Procedural Elements for Computer Graphics)」、
マックグローヒル社刊、１９８８、ISBN 0-07-Y66503-
6、３１７−３１９頁（セクション５．３及び例５−
２）に記述された技術が使用される。

【００５６】ステップＳ５８でユニット・ノーマルの計
算に続いて、又は、ステップＳ５６において３Ｄモデリ
ング・データが既に各三角形状の多角形の各頂点でノー
マルが規定されたことが決定されれば、ステップＳ６０
において、ＣＰＵ４が他のオブジェクト・モデルを考慮
すべきかどうかを決定する。ステップＳ６０においてさ
らなるモデルが処理されることがないと決定されるま
で、ステップＳ５０からＳ６０が反復され上述した方法
で各オブジェクトの各モデルが処理される。

【００５７】図２Ａ、２Ｂを再度参照して、ステップＳ
６において、ＣＰＵ４が各オブジェクトの各モデルのた
めのトポロジー・データベースを構築し、記憶する。次
に説明するように、このデータベースは、レンダリング
中、次の使用のために、各モデル内の各三角形、特に各
三角形のエッジ及び頂点に関する上方を記憶する。

【００５８】図４Ａ，４Ｂは、前述のステップＳ６にお
けるＣＰＵ４によって処理される処理操作を示すフロー
チャートである。

【００５９】図４Ａ、４Ｂを参照して、ステップＳ８０
において、ＣＰＵ４が次のオブジェクトのモデル中の次
の三角形を考慮する（これはステップＳ８０が実行され
る最初の第１オブジェクトのモデルである）。

【００６０】ステップＳ８２において、ＣＰＵ４がユニ
ークＩＤを三角形に割り当て、ステップＳ８４におい
て、インデックスを三角形中の各エッジに割り当てる。

【００６１】ステップＳ８６において、ＣＰＵ４が別の
三角形がモデル中にあるか決定する。ステップＳ８６に
おいて、さらなる三角形がモデル中にないことが決定さ
れるまで、ステップＳ８０からＳ８６が反復される。上
述した方法で各三角形が処理される。

【００６２】ステップＳ８８において、ＣＰＵ４が特定
番号によるＩＤをモデル中の各特定頂点に割り当てる。
（頂点は複数の三角形の一部を形成するが、この場合、
ステップＳ８８において、単一のＩＤのみが頂点に割り
当てられる）。このＩＤは、各特定頂点が考慮されてス
テップＳ８８において番号順に割り当てられる。本実施
の形態において、ユーザはモデル中の各頂点の位置に関
する不確実性メジャを規定することができ、これによっ
て頂点はそれらの座標を有する同じ頂点としてユーザに
よって規定された量とは異ならないように処理される。
例えば、ユーザは各座標につき０．０２の不明確域を規
定し、これで頂点（１．００、０．００、０．００）が
同じ頂点（０．９８、０．００、０．００）として処理
される。

【００６３】ステップＳ９０において、ＣＰＵ４が目下
考慮中のオブジェクトのモデル内で次の三角形を考慮
し、また、ステップＳ９２において、三角形内で次のエ
ッジを考慮する（これが最初のエッジとすると、第１回
のステップＳ９２が実行される）。

【００６４】ステップＳ９３において、ＣＰＵ４がエッ
ジの各端で頂点におけるノーマル・ベクトルのドット−
プロダクトを計算する。この計算された値は、これら二
つのノーマル・ベクトル間の角度を表わし、従って、下
にあるオブジェクト面の曲率が三角形を表わす。ドット
・プロダクト値は、ノーマル・ベクトルが平行で、頂点
間のエッジの曲率を指示していないときの＋１から、反
対方向の（すなわち、両者間の角度が１８０°）にある
ノーマル・ベクトルで、エッジの最大曲率を指示してい
るときの−１までの範囲である。

【００６５】ステップＳ９４において、ＣＰＵ４はステ
ップＳ９２で考慮されたエッジの頂点を規定する特定Ｉ
Ｄ（これらのＩＤはステップＳ８８で割り当てられる）
からの２次元データ構造を作成する。本実施の形態にお
いて、２次元データ構造はフォーム（ＩＤ０、ＩＤ１）
を有しており、ここにＩＤ０は二つのＩＤの小さい方
で、ＩＤ１は二つのＩＤの大きい方である。各対の内の
小さい方のＩＤを最初に、大きい方のＩＤを二番目し
て、二つの寸法データ構造を構成することによって、こ
れが例えば頂点Ｍを頂点Ｎに連結するエッジを、頂点Ｎ
を頂点Ｍに連結するエッジと同じであると考えることが
保証される。

【００６６】ステップＳ９６において、ＣＰＵ４がステ
ップＳ９４で形成された２次元データ構造に依存してＩ
Ｄをエッジに割り当てる。各特定エッジが特定ＩＤを受
ける（一つのより多い三角形のエッジとするエッジが単
一の特定ＩＤを受ける）ように、ＣＰＵ４がステップＳ
９６でＩＤを割り当てる。

【００６７】ステップＳ９８において、ＣＰＵ４が考慮
中の三角形内に他のエッジがあるかどうか決定する。処
理されるべき三角形内にさらなるエッジがないことがス
テップＳ９８で決定されるまで、ステップＳ９２からＳ
９８が反復され、上述した方法で各エッジが処理され
る。

【００６８】ステップＳ９９において、ＣＰＵ４がステ
ップＳ９３において各対のノーマルのために前回計算さ
れたドット・プロダクトが読み取りされ、次の使用のた
めの最少ドット・プロダクトを決定し、記憶する。これ
については後述する。この最少ドット・プロダクツ値
が、全体として三角形のオブジェクト面の一部の最大曲
率値を表わす代表値である。

【００６９】ステップＳ１００において、ＣＰＵ４が考
慮されているオブジェクトのモデル内で処理されるべき
他の三角形があるかどうかを決定する。ステップＳ１０
０において処理されるべきさらなる三角形がないと決定
されるまで、ステップＳ９０からＳ１００が上述した方
法で各三角形を処理するのに反復される。

【００７０】ステップＳ１０２において、ＣＰＵ４が考
慮中のオブジェクトのモデル内で次の特定エッジを考慮
する（各特定エッジがステップＳ９６において前回割り
当てられた特定ＩＤによって識別される）。

【００７１】ステップＳ１０４において、ＣＰＵ４がエ
ッジを共用しているオブジェクトのモデル内の三角形の
数を決定し、かつ、エッジのためのエッジ・フラグを記
憶するために各三角形用のメモリ・スペースを予約す
る。

【００７２】ステップＳ１０６において、ＣＰＵ４が考
慮されているオブジェクトの特定エッジであるかどうか
を決定する。ステップＳ１０６において全てのエッジが
処理されたことが決定されるまで、ステップＳ１０２か
らＳ１０６が上述した方法で各特定エッジを処理するの
に反復される。

【００７３】ステップＳ１０８において、ＣＰＵ４が従
来の方法でモデル内の各三角形のために、ノーマル化さ
れたノーマル（すなわち、三角形の平面と垂直であるベ
クトル）を計算する。

【００７４】ステップＳ１１０において、ＣＰＵ４が考
慮されているオブジェクトのモデル内のエッジのために
各フラグをセットする。

【００７５】図５Ａ，５ＢはＣＰＵ４によってステップ
Ｓ１１０において各フラグをセットするように実行され
る処理操作を示すフローチャートである。

【００７６】図５Ａ，５Ｂを参照して、ステップＳ１３
０において、ＣＰＵ４が目下考慮中のオブジェクトのモ
デル内の次のエッジを考慮する。

【００７７】ステップＳ１３２において、ＣＰＵ４がエ
ッジを共用している三角形の数を決定し、また、ステッ
プＳ１３４において、エッジがただ一つの三角形の一部
であるかどうかを決定する。

【００７８】ステップＳ１３４において、エッジがただ
一つの三角形の一部であると決定されれば、ステップＳ
１３６において、ＣＰＵ４がエッジのために「境界エッ
ジ」フラグをセットする。後述するように、「境界エッ
ジ」フラグがエッジのためにセットされると、エッジは
オブジェクトのモデルのどの次のリファインメントにお
いて変更されない（なぜなら、モデルは例えばこのエッ
ジに沿って他のモデルと連結する必要があるからであ
る）。

【００７９】一方、エッジがただ一つの三角形の一部で
ないとステップＳ１３４において決定されれば、ステッ
プＳ１３８において、ＣＰＵ４はエッジが二つ以上の三
角形によって共用されているかどうかを決定する。

【００８０】図６（ａ）は、エッジが二つ以上の三角形
によって共用されている一例の状況を示す図である。図
６（ａ）を参照すると、エッジ３０は三角形３２、３４
及び３６によって共用されている。

【００８１】エッジが二つ以上の三角形によって共用さ
れているとステップＳ１３８で決定されれば、次に、ス
テップＳ１４０において、ＣＰＵ４がエッジを共用する
各三角形のためのエッジ用に「無効エッジ共用」フラグ
をセットする。図６（ａ）に示した例を再度参照して、
「無効エッジ共用」フラグが三角形３２、三角形３４及
び三角形３６用にエッジ３０がセットされる。後述する
ように、「無効エッジ共用」フラグが一つのエッジのた
めにセットされると、そのエッジはオブジェクトのモデ
ルのいかなるレファインメント中でも変わることがない
（これはモデルのトポロジー中のエラーを指示するのが
普通だからである）。実際には、「無効エッジ共用」フ
ラグは、どのようなエッジ共用もただ二つの三角形間に
生じるようにオブジェクトのモデルが通常作成されるの
で、そう頻繁にセットされない。

【００８２】一方、エッジが二つ以上の三角形によって
共用されないことがステップＳ１３８において決定され
れば、エッジは二つに、ただ二つの三角形によって共用
されなければならない（これはエッジがただ一つの三角
形の一部ではないことがステップＳ１３４で決定され、
かつ、エッジが二つ以上の三角形によって共用されてい
ないことがステップＳ１３８で決定されるからであ
る）。

【００８３】図６（ｂ）は、エッジが二つの三角形によ
って共用された状態の二つの形態を例として示す。図６
（ｂ）の例において、エッジ３０は三角形３２と３８に
よって共用されている。

【００８４】エッジが二つ以上の三角形によって共用さ
れていないことがステップＳ１３８で決定されると、次
いでステップＳ１４２において、ＣＰＵ４がエッジを共
用している最初の三角形を考慮し、また、ステップＳ１
４４において、第１三角形用のエッジの両端を規定する
各頂点におけるノーマルが三角形ノーマルと平行である
かどうかが決定される。

【００８５】図６（ｃ）は、エッジの各頂点ノーマルが
三角形ノーマルと平行である一例を示す。図６（ｃ）を
参照して、図示した例において、エッジ３０の一端を規
定する頂点におけるノーマル４２は、エッジの他端を規
定する頂点のノーマルと平行であり、両ノーマルは三角
形ノーマルに平行である。

【００８６】エッジの両端を規定する各頂点におけるノ
ーマルが三角形のノーマルと平行であるとステップＳ１
４４において決定されれば、次に、ステップＳ１４６に
おいて、ＣＰＵ４が第１三角形に対するエッジのための
「キープ・エッジ」フラグをセットする。このフラグの
効果については後述する。一方、各頂点におけるノーマ
ルと三角形ノーマルが平行でないことがステップＳ１４
４において決定されれば、次に「キープ・エッジ」フラ
グが三角形のためにセットされないとして、ステップＳ
１４６は省略される。

【００８７】ステップＳ１４８、Ｓ１５０及びＳ１５２
において、ＣＰＵ４が、第１三角形に対してステップＳ
１４２、Ｓ１４４及びＳ１４６において前回実行された
エッジを共用する第２三角形に同じ処理操作を実行す
る。これらの処理操作は既に説明したので、ここでは再
度説明しない。

【００８８】ステップＳ１５４において、ＣＰＵ４がエ
ッジの第１端で頂点におけるノーマルが二つの共用三角
形用であるかどうかが決定される。

【００８９】図６（ｄ）はエッジの端を規定する頂点に
おけるノーマルが、二つの共用三角形用と異なる一例を
示す。図６（ｄ）に示された例によれば、三角形３２用
のノーマル５０は頂点５４における三角形３８のノーマ
ル５２と異なる。

【００９０】頂点におけるノーマルが共用三角形用と異
なることがステップＳ１５４において決定されれば、次
に処理がステップＳ１５８に進行し、ここでＣＰＵ４が
両共用三角形のためのエッジに対して「エッジ・ノーマ
ル不明瞭」フラグをセットする。従って、図６（ｄ）に
示した例を参照して、「エッジ・ノーマル不明瞭」フラ
グが、三角形３２と三角形３８両方のエッジ３０のため
にセットされることになる。

【００９１】一方、ステップＳ１５４において、エッジ
の第１端の頂点におけるノーマルが共用三角形用と同じ
であることが決定されれば、次に処理がステップＳ１５
６に進行する。ステップＳ１５６において、ＣＰＵ４
が、エッジの他端の頂点におけるノーマルが共用三角形
用と異なるかどうかを決定する。図６（ｄ）の例を再度
参照して、三角形３２のノーマル５６が頂点６０におけ
る三角形３８のためのノーマル５８と異なる。

【００９２】エッジの第２端の頂点におけるノーマルが
二つの共用三角形用と異なることがステップＳ１５６で
決定されれば、次にステップＳ１５８において、ＣＰＵ
４が両共用三角形に対するエッジのために「エッジ・ノ
ーマル不明瞭」フラグをセットする。従って、図６
（ｄ）に示した例を参照して、「エッジ・ノーマル不明
瞭」フラグは三角形３２と三角形３８両方のエッジ３０
のためにセットされる。一方、エッジの第２端を規定す
る頂点におけるノーマルが共用三角形用と異なることが
ステップＳ１５６において決定されれば、次に「エッジ
・ノーマル不明瞭」フラグがエッジのためにセットされ
ないようにステップＳ１５８が省略される。

【００９３】従って、ステップＳ１５４、ステップＳ１
５６及びステップＳ１５８において実行された処理の結
果、「エッジ・ノーマル不明瞭」フラグは、エッジのい
ずれの端における頂点のノーマルも共用三角形用と異な
れば、エッジを共用する両三角形のためにセットされ
る。

【００９４】ステップＳ１６０において、ＣＰＵ４が、
未だに考慮されていないモデル内に他のエッジがあるか
どうかを決定する。ステップＳ１３０からＳ１６０が反
復され上述した方法でモデルのエッジの全てを処理す
る。

【００９５】図４Ａ，４Ｂを再度参照して、ステップＳ
１１２において、ＣＰＵ４がステップＳ１１０において
前回セットされたエッジ・フラグを修正する。ステップ
Ｓ１１２において実行された処理の目的は、「エッジ・
ノーマル不明瞭」フラグがセットされたエッジを識別す
ることである（各共用三角形のノーマルが、エッジの両
端を規定する少なくとも一つの頂点において異なること
を指示している）、さらに「キープ・エッジ」フラグ
が、エッジを共用する一対の内の一つの三角形（この三
角形のために、各頂点におけるノーマルが三角形ノーマ
ルと平行であることを示している）のためにセットさ
れ、また、レンダリングリング中、次の使用のためにこ
れを指示するフラグをセットする。

【００９６】図７Ａ，７ＢはＣＰＵ４によってステップ
Ｓ１１２において実行されエッジ・フラグを修正する処
理操作を示すフローチャートである。

【００９７】図７Ａ，７Ｂを参照して、ステップＳ１９
０において、ＣＰＵ４は目下考慮中のモデル内の二つの
三角形によって共用された次のエッジを考慮する。

【００９８】ステップＳ１９２において、ＣＰＵ４が、
「エッジ・ノーマル不明瞭」フラグがエッジを共用する
三角形用にセットされれているかどうかを決定する。
「エッジ・ノーマル不明瞭」フラグがセットされている
と決定されれば、次にステップＳ１９４において、ＣＰ
Ｕ４が、エッジを共用する第２三角形ではなく、第１三
角形のためのエッジ用にセットされたかどうかを決定す
る。

【００９９】後ほど詳細に説明するが、「キープ・エッ
ジ」フラグが第１三角形のためにセットされるが、第２
三角形のためにセットされなければ、これはエッジがレ
ンダリングの間オブジェクトのモデルのリファインメン
ト中、第２三角形のために変形されるような状況に対応
するが、第１三角形のために変更されることはない。こ
の状況の例を図８（ａ）に示す。

【０１００】図８（ａ）を参照して、エッジ３０は三角
形３２のためにリファインされていない。しかし、この
エッジはカーブ７０に近似するように三角形３８のため
にリファインされることになる。

【０１０１】再度図７Ａ，７Ｂを参照して、ステップＳ
１９６において、ＣＰＵ４が、エッジを共用する第１及
び第２三角形のエッジのための「エッジ・ノーマル不明
瞭」フラグを削除する。ステップＳ１９８において、Ｃ
ＰＵ４がエッジを共用している第１三角形のエッジのた
めの「キープ・エッジ」フラグを削除する。ステップＳ
２００において、ＣＰＵ４がエッジを共用する第１三角
形のエッジのための「エッジの付けられた(is attached
edge)」フラグをセットし、ステップＳ２０２におい
て、エッジを共用する第２三角形のエッジのための「エ
ッジの付けられている(has attached edge)」フラグを
セットする。

【０１０２】一方、ステップ１９４において「キープ・
エッジ」フラグが、エッジを共用するのに第１三角形の
エッジのためにセットされ、第２三角形のためにセット
されていないことが決定されれば、次に処理がステップ
Ｓ２０４に進行し、「キープ・エッジ」フラグがエッジ
を共用するのが第２三角形のエッジのためにセットさ
れ、第１三角形のためにセットされていないかどうかを
ＣＰＵ４が決定する。「キープ・エッジ」フラグが第１
三角形のためではなく、第２三角形のためにセットされ
たことがステップＳ２０４で決定されれば、次にエッジ
が第１三角形のために修正されることになり、レンダリ
ング中オブジェクトのモデルの続く工程のリファイメン
ト中、第２三角形のために修正されることはない状況が
発生する。この状況の一例を図８（ｂ）に示す。

【０１０３】図８（ｂ）に示す例を参照して、エッジ３
０が三角形３２のカーブ７２に近似するように修正され
るが、三角形３８のために修正されることはない。

【０１０４】ステップＳ２０６において、ＣＰＵ４が、
エッジを共用する両三角形のエッジのための「エッジ・
ノーマル不明瞭」フラグを削除し、また、ステップＳ２
０８において、ＣＰＵ４が、エッジを共用する第２三角
形のための「キープ・エッジ」フラグを削除する。

【０１０５】ステップＳ２１０において、ＣＰＵ４が第
２三角形のエッジのために「エッジの付けられた」フラ
グをセットし、またステップＳ２１２において、ＣＰＵ
４が第１三角形のエッジのために「エッジの付けられて
いる」フラグをセットする。

【０１０６】ステップＳ１９２からＳ２１２で実行され
た処理操作の結果、二つの三角形によって共用されたエ
ッジが一つの三角形のためであって、他の三角形のため
にではなくリファインされるケースを識別するように、
ＣＰＵ４がフラグをセットする。「エッジの付けられ
た」フラグは、フラグがセットされた三角形のために変
更されず、一方「エッジの付けられている」フラグが、
フラグのセットされた三角形のために変更されることを
示す。

【０１０７】ステップＳ２０４において、「キープ・エ
ッジ」フラグが第２三角形のためでなく、第１三角形の
ためにセットされたことがＣＰＵ４によって決定されれ
ば、次に各三角形のエッジのめにセットされたフラグ
は、「エッジ・ノーマル不明瞭」フラグと「キープ・エ
ッジ」フラグを一緒にしたものか、又は「エッジ・ノー
マル不明瞭」フラグ単独でなければならない。

【０１０８】後ほど詳細に説明するが、「エッジ・ノー
マル不明瞭」フラグと「キープ・エッジ」フラグ両方が
各エッジのためにセットされれば、次にエッジは、オブ
ジェクトのモデルがレンダリング中リファインされると
きに、二つの三角形のいずれかのために変更されること
はない。この状況の一例を図８（ｃ）に示し、ここでそ
のエッジ３０は、三角形３２又は三角形３８のいずれの
ためにもリファインされない。

【０１０９】「エッジ・ノーマル不明瞭」フラグのみが
両三角形のエッジのためにセットされれば、次にエッジ
がモデルの次のリファインメント中に両三角形のために
変更される。この状況の一例を図８（ｄ）に示し、三角
形３２と三角形３８によって前回共用されたエッジがリ
ファインされ、三角形３２のためにカーブ７６が近似さ
れ、また三角形３８のためにカーブ７８が近似される。

【０１１０】図７Ａ，７Ｂを再度参照して、ステップＳ
２１４において、二つの、ただ二つの三角形によって共
用されているモデル中に他のエッジがあるかどうかをＣ
ＰＵ４が決定する。モデル中の二つの三角形によって共
用された全てのエッジが前述の方法で処理されるまで、
ステップＳ１９０からＳ２１４が反復される。

【０１１１】図４Ａ，４Ｂを再度参照して、ステップＳ
１１４において、未だ処理されていない他のオブジェク
トのモデルがあるかどうかをＣＰＵ４が決定する。各モ
デルが上述した方法で処理されるまで、ステップＳ８０
からＳ１１４までが反復される。

【０１１２】図２Ａ，２Ｂを再度参照して、ステップＳ
８において、各オブジェクトのモデルのリファインメン
トのためのパラメータをＣＰＵ４が計算する。

【０１１３】本実施の形態において、パラメータが、３
次バーンスタイン−ベジエ三角形パッチに基づいてモデ
ルをリファインするように計算される。

【０１１４】図９は、ステップＳ８において、ＣＰＵ４
によって実行されリファインメント・パラメータを計算
する処理操作を示すフローチャートである。

【０１１５】図９を参照して、ステップＳ２３０におい
て、ＣＰＵ４が次のオブジェクトのモデルを考慮してお
り、また、ステップＳ２３２において、モデル中の次の
三角形を考慮している。ステップＳ２３４とＳ２３６に
おいて、ＣＰＵ４が、考慮されている三角形の各「制御
ポイント」のための「縦座標」を計算する。これらの縦
座標は三角形のための３次バーンスタイン−ベジエ三角
形パッチを規定する。

【０１１６】図１０は、例示した三角形のための制御ポ
イント９０、９２、９４、９６、９８、１００、１０
２、１０４、１０６、１０８を示す。図１０中の各制御
ポイントのためのかっこ内に示された座標は、制御ポイ
ントの重心座標である。従来の方法において、１０個の
制御ポイントが３次バーンスタイン−ベジエ三角形パッ
チを規定する座標を計算するのに使用される。制御ポイ
ント９０、９６及び１０２が三角形頂点に配置される。
二つの制御ポイントが各三角形エッジに沿って等距離に
隔置される（これらの制御ポイントは図１０において、
９２、９４、９８、１００及び１０６である）。さらな
る制御ポイントが三角形の重心座標に配置される（これ
は図１０の制御ポイント１０８である）。

【０１１７】図９を再度参照して、ステップＳ２３４に
おいて、ＣＰＵ４が各頂点制御ポイント（図１０におい
て９０、９６及び１０２）と各エッジ制御ポイント（図
１０において９２、９４、９８、１００、１０４及び１
０６）のための縦座標を計算する。

【０１１８】図１１は、ＣＰＵ４がステップＳ２３４に
おいて縦座標の計算を実行する処理操作を示すフローチ
ャートである。

【０１１９】図１１を参照して、ステップＳ２５０にお
いて、ＣＰＵ４が各頂点制御ポイントのための縦座標を
ゼロにセットする。これは縦座標によって規定された３
次ベルンスタイン−ベジエ三角形パッチが三角形の各頂
点を通過することを保証する。これが、所与の頂点を共
用する各三角形のためのパッチが頂点において一致を保
証することになり、これによって頂点における三角形の
合致（メッシィング）の連続性が保証される。

【０１２０】ステップＳ２５２からＳ２６４において、
ＣＰＵ４が各制御ポイント（図１０の例において、９
２、９４、９８、１００、１０４及び１０６）における
縦座標を計算する。

【０１２１】より詳しく説明すると、ステップＳ２５２
において、「境界エッジ」フラグが三角形中のどのエッ
ジに対してもセットされるかどうかをＣＰＵ４が決定す
る。このフラグがセットされれば、次にステップＳ２５
４において、「境界エッジ」フラグがセットされた各エ
ッジに沿った全てのエッジ制御ポイントのための縦座標
に対してゼロの値をＣＰＵ４がセットする。これが、三
角形のための３次バーンスタイン−ベジエ三角形パッチ
が、「境界エッジ」フラグのセットされた三角形中の各
エッジと一致することを保証する。後述するように、こ
れがオブジェクトのモデルが次に続く処理中にリファイ
ンされるときに、このエッジが変更されるのを回避させ
る。「境界エッジ」フラグが三角形中のどのエッジ対し
てもセットされなければ、ステップＳ２５４は省略され
る。

【０１２２】ステップＳ２５６において、「無効エッジ
共用」フラグが三角形中のどのエッジについてもセット
されているかどうか、ＣＰＵ４が決定する。このフラグ
がどのエッジについてもセットされておれば、次にステ
ップＳ２５８において、ＣＰＵ４が、「無効エッジ共
用」フラグがセットされた各エッジに沿った各エッジ制
御ポイントの縦座標のためにゼロの値をセットする。ス
テップＳ２５８における処理が、三角形のべルンスタイ
ン−ベジエ三角形パッチが、「無効エッジ共用」フラグ
がセットされた各三角形のエッジと一致することを保証
し、これによって、オブジェクトのモデルが次の処理中
（これについては後述する）リファインされるときに、
このエッジの修正されるのを回避する。「無効エッジ共
用」フラグが三角形のどのエッジについてもセットされ
なければ、ステップＳ２５８が省略される。

【０１２３】ステップＳ２６０において、ＣＰＵ４が、
縦座標の値がステップＳ２５４又はステップＳ２５８に
おいてセットされないような次の残りのエッジ制御ポイ
ントを考慮する。

【０１２４】ステップＳ２６２において、ＣＰＵ４が直
近の頂点を通過するタンジェント平面の制御ポイントか
らの距離を計算することによって、制御ポイントの縦座
標の値を計算する。この距離は直近の頂点のノーマルと
平行な方向で測定される。

【０１２５】図１２は、ステップＳ２６２においてＣＰ
Ｕ４によって計算された距離を示す図である。図１２を
参照すると、制御ポイント９８への直近の三角形頂点は
頂点９６である。頂点９６を通過するタンジェント平面
１２０は頂点９６におけるノーマル１２２に対して垂直
な平面である。ステップＳ２６２においてＣＰＵ４によ
って計算された距離は、制御ポイント９８から頂点ノー
マル１２２と平行な方向１２４にある平面１２０までの
高さ「ｈ」である。

【０１２６】図１３は、ステップＳ２６２（図１１）に
おいて、ＣＰＵ４によって実行され、縦座標の値を計算
する処理操作を示すフローチャートである。

【０１２７】図１３を参照して、ステップＳ２８０にお
いて、ＣＰＵ４がエッジのエッジ方向ベクトルを計算
し、このエッジ上の制御ポイントは直近頂点から制御ポ
イントまでの方向にある。

【０１２８】ステップＳ２８２において、ＣＰＵ４が制
御ポイントに対する直近頂点におけるユニット・ノーマ
ル・ベクトルの値を読み取り、またステップＳ２８４に
おいて、ステップＳ２８０で計算されたエッジ・べクト
ルと、ステップＳ２８２で読み取られたユニット・ノー
マル・ベクトルとのスカラー積を計算する。

【０１２９】ステップＳ２８６において、ＣＰＵ４が、
ステップＳ２８４で得られたスカラー積にマイナス１／
３を乗算し、得られた値が縦座標のための値を規定する
（これが図１２の例で示す高さ「ｈ」である）。

【０１３０】ＣＰＵ４で計算された縦座標の値は、制御
ポイントに対する直近頂点においてノーマルの方向に依
存して負か正のいずれかになることがわかる。

【０１３１】図１１を再度参照して、ステップＳ２６４
において、縦座標が計算されていない他のエッジ制御ポ
イントがあるかどうか、ＣＰＵ４が決定する。縦座標値
がステップＳ２５４又はステップＳ２５８において、前
回ゼロにセットされていない縦座標が各エッジ制御ポイ
ントのために計算されるまで、ステップＳ２６０からＳ
２６４が反復される。

【０１３２】図９を再度参照して、ステップＳ２３６に
おいて、ＣＰＵ４が中央制御ポイント（すなわち、三角
形の共通重心における制御ポイント − 図１０の例で
ポイント１０８）の縦座標のための値を計算する。本実
施の形態において、ＣＰＵ４がエッジ制御ポイント（図
１０で９２、９４、９８、１０４及び１０６）の縦座標
の和の１／４として中央制御ポイントのための縦座標を
計算する。

【０１３３】ステップＳ２３８において、縦座標が計算
されていないモデル中に別の三角形があるがどうかＣＰ
Ｕ４が決定する。縦座標がモデル中の各三角形のために
計算されるまで、ステップＳ２３２からＳ２３８が反復
される。

【０１３４】ステップＳ２４０において、ＣＰＵ４が、
考慮されるべき別のオブジェクトのモデルがあるかどう
かを決定する。縦座標が各モデル中の各三角形のために
計算されるまでステップＳ２３０からＳ２４０が反復さ
れる。

【０１３５】これまでに言及したように、ステップＳ８
（図２Ａ）において計算された縦座標が、モデル中の各
三角形のための３次バースタイン・ベジエ三角形パッチ
を規定する。算術的に、度「ｎ」のバーンスタイン−ベ
ジエ三角形パッチ、ｂⁿ(τ）は次式によって与えられ
る：

【０１３６】

【数１】ここで、λは制御ポイントλの位置を識別する重心座標
のトリプレット（λ₁，λ₂，λ₃）である；ｂ_λは制御
ポイントλのための縦座標の値である；Ｂ_λ ⁿ（τ）
は、制御ポイントλのためのバーンスタイン整数であ
り、また次式によって与えられる：

【０１３７】

【数２】ここで、（λ₁，λ₂，λ₃）は、元の三角形上のポイン
トの重心座標を規定する。

【０１３８】式（１）及び（２）において、ｂⁿ（τ）
は三角形上のポイントτの上方パッチ高さを表わす。次
の制限はτに適用される：

【０１３９】

【数３】 λは次式によってτに関連付けられる：

【０１４０】

【数４】３次バーンスタイン−ベジエ三角形パッチに対し、
「ｎ」は３であり、また、従って、パッチの式は、

【０１４１】

【数５】で与えられ、全ての制御ポイント９０、９２、９４、９
６、９８、１００、１０２、１０４、１０６及び１０８
のための｜λ｜＝３を図１０に示す。従って、３次バー
ンスタイン−ベジエ三角形パッチは次のように書くこと
ができる：

【０１４２】

【数６】式６において、b₀₀₃, b₀₃₀, b₃₀₀, b₁₀₂, b₂₀₁, b₀₁₂,
b₀₂₁, b₁₂₀, b₂₁₀及びb₁₁₁ がステップＳ８において、
それぞれ重心座標（０，０，３），（０，３，０），
（３，０，０），（１，０，２），（２，０，１），
（０，１，２），（０，２，１），（１，２，０），
（２，１，０）及び（１，１，１）を有する制御ポイン
トのために計算された縦座標の値である。

【０１４３】図１４は、ステップＳ８において計算され
た縦座標によって規定された三角形のためのバーンスタ
イン−ベジエ三角形パッチの例を示す図である。ＣＰＵ
４はいかなるパッチも引くことはないが、ただ次の使用
のために各三角形のパッチを規定する縦座標を単に記憶
するだけである。これについては後述する。

【０１４４】図１４（ａ）を参照して、一例のバーンス
タイン−ベジエ三角形パッチ１４０を三角形３２で示
す。このパッチ１４０は各頂点で三角形と接触している
が、この例において、どのほかのポイントにおいても三
角形と接触していない。その代わりに、三角形頂点以外
の全てのポイントに対し、パッチ１４０が三角形３２の
面の上方のある高さにある。

【０１４５】図１４（ｂ）は、三角形３２のためのバー
ンスタイン−ベジエ三角形パッチの第２例を示す。図１
４（ｂ）を参照して、パッチ１４４は三角形の各頂点で
三角形３２と一致している。さらに、パッチ１４４はエ
ッジ３０に沿って各ポイントにおいて三角形３２と一致
している。エッジに沿った各縦座標の値がゼロのとき
に、パッチがエッジの各ポイントに沿った三角形と一致
している。これは、「境界エッジ」フラグ、「無効エッ
ジ共用」フラグ又は「キープ・エッジ」フラグが、エッ
ジのためにセットされたときに、発生する。「境界エッ
ジ」フラグがセットされた場合において、エッジに沿っ
た縦座標が、ステップＳ２５４（図１１）においてＣＰ
Ｕ４によってゼロにセットされ、強制的にパッチがゼロ
に一致させられる。同様にして、「無効エッジ共用」フ
ラグがエッジのためにセットされると、ＣＰＵ４がステ
ップＳ２５８においてエッジのために縦座標をゼロにセ
ットし、強制的にパッチをエッジに一致させる。「キー
プ・エッジ」フラグがエッジにセットされると、次にエ
ッジの両端を規定する各頂点におけるノーマルが三角形
ノーマルと平行になる（これは、「キープ・エッジ」フ
ラグが図５Ａ，５ＢにおけるステップＳ１４４とＳ１４
６又はＳ１５０とＳ１５２においてセットされる条件下
にある。この場合に、エッジに沿った各制御ポイントの
縦座標の値が、ステップＳ２６２（図１１）においてＣ
ＰＵ４によってゼロとなるように計算される。なぜな
ら、直近頂点におけるタンジェント平面がエッジに沿っ
て通過することになる（すなわち、図１２に示したタン
ジェント平面の高さ「ｈ」がエッジの全体に沿ってゼロ
となる）からである。

【０１４６】図１４（ｃ）は、バースタイン−ベジエ三
角形パッチが二つの近接する三角形３２と３８の例で示
し、その三角形によって共用された共通エッジ３０が、
三角形３２のためにセットされた「エッジの付けられ
た」フラグを有し、「エッジの付けられている」フラグ
が三角形３８のためにセットされる。三角形３２のため
のパッチ１４４がエッジ３０に沿って各ポイントで三角
形と一致している。一方、三角形３８のためのパッチ１
４８は、三角形頂点以外のエッジ３０と接触していな
い。

【０１４７】図１４（ｄ）は、二つの近接する三角形３
２と３８のためのバーンスタイン−ベジエ三角形パッチ
の一例を示し、その三角形によって共用された共通エッ
ジ３０が各三角形のエッジのためにセットされた「エッ
ジ・ノーマル不明瞭」フラグを有しているが、「キープ
・エッジ」フラグはセットされていない。この場合、三
角形３２のためのパッチ１５２も三角形３８のためのパ
ッチ１４８のいずれも、三角形頂点における以外にエッ
ジ３０と接触していない。

【０１４８】図２Ａ，２Ｂを再度参照して、ステップＳ
９からＳ３４において、ＣＰＵ４が各オブジェクトのモ
デルをレンダリングすることによって画像データのフレ
ームを発生させる処理を実行する。ステップＳ９からＳ
３４は、これらのステップ中の処理が１フレームの時間
周期内で発生するように、画像データの各フレームにつ
き反復される。一般的に、フレームは１秒当り３０フレ
ームのようなビデオ・レートで発生され、ステップＳ９
からＳ３４の処理操作中のフレーム周期の場合、１／３
０秒である。

【０１４９】ステップＳ９において、ＣＰＵ４がオブジ
ェクトの位置を決定する。すなわち、画像データの前回
フレームが発生されている間、オブジェクトの位置が指
令入力に基づいて変更されたかどうかをＣＰＵ４が決定
する。

【０１５０】ステップＳ１０において、ライトニング
（照明）パラメータがオブジェクトのモデルを照明する
のに使用されたことをＣＰＵ４が決定する。これらのパ
ラメータは従来のライトニング・パラメータで、例えば
周囲光の量と、一つ又はそれ以上の各光源の位置、方向
及び光度を含んでいる。照明パラメータは、ステップＳ
２において受信された３Ｄモデリング・データ内に規定
される。これに加えて、又はこれに代えて、これらはＣ
ＰＵ４に入力されるか、又はユーザによる入力デバイス
１４によって変更される。ステップＳ１０において、Ｃ
ＰＵ４は、前回フレーム周期中になされた全ての変更を
含む照明パラメータの値を読み取る。

【０１５１】ステップＳ１２において、ＣＰＵ４が、オ
ブジェクトの画像が発生されるであろうビューイング位
置とビューイング方向を規定するデータを読み取る。ビ
ューイング・パラメータは、３Ｄワールド・スペースか
ら３Ｄビューイング（又はカメラ）スペースへ多角形を
変換するビューイング変換を規定する。ビューイング・
パラメータはユーザによって、例えば入力デバイス１４
を介して入力される。ステップＳ１２において、ＣＰＵ
４は、前回フレーム周期中になされた全ての変更を含む
ビューイング・パラメータの値を読み取る。

【０１５２】ステップＳ１４において、ＣＰＵ４が、ス
テップＳ１２において決定されたビューイング・パラメ
ータによって規定されたビューイングのフィールド内に
入っていないオブジェクトを抜粋して、これらのオブジ
ェクトがそれ以上処理されないようにし、これによって
実行しなければならない処理量を削減する。

【０１５３】より詳しく説明すると、本実施の形態にお
いて、境界ボックスがオブジェクトのオブジェクト・ス
ペース内に従来方法で各オブジェクトのために規定され
る。オブジェクト・スペースから共用３Ｄワールド・ス
ペースまでのポイントを変換するローカル変換及び３Ｄ
ワールド・スペースから３Ｄビューイング・スペースま
でのポイントを変換するビューイング変換は、ローカル
変換とビューイング変換を規定するマトリックスを連結
することによって境界ボックスでの共通操作として実行
される。これがビューイングスペース内にオブジェクト
境界ボックスを配置する。その後、変換境界ボックスの
位置は、ビューイング可能スペース内に完全にあるか、
ビューイング可能スペースの完全に外にあるか、又はビ
ューイング可能スペースと交差しているかどうかの決定
が考慮される。

【０１５４】境界ボックスが完全にビューイング可能ス
ペース外にある場合、さらなる処理は境界ボックス内の
オブジェクトを規定する多角形に対して実行されること
はない。境界ボックスが部分的ないし完全にビューイン
グ可能スペース内にある場合、境界ボックス内のオブジ
ェクトを規定する多角形は処理され画像データを発生す
る。しかし、付加的に、境界ボックスが一部ビューイン
グ可能スペース内にあり、また一部ビューイング可能ス
ペース外にある場合、境界ボックスと観察可能スペース
の交差する平面を規定するデータがオブジェクトを規定
する多角形のクリッピングで続く使用のために記憶され
る。これについては後述する。

【０１５５】ステップＳ１６において、ステップＳ１４
における抜粋がステップＳ８において前回計算されたリ
ファイメント・パラメータを使用してＣＰＵ４によって
リファインされた後、各オブジェクトのモデルが残留さ
れる。

【０１５６】ステップＳ１６においてＣＰＵ４にって実
行される処理の目的は、オブジェクトのモデル内の各三
角形状多角形を、オブジェクト面をより正確に表わす多
数の小さい三角形にリファインすることである。以下に
説明するように、より小さい三角形は元の三角形として
同じ平面にある必要性はなく、また下に敷かれたオブジ
ェクト面がより忠実にモデル化できる。従って、ステッ
プＳ１６における処理を実行することによって、オブジ
ェクト面の曲率を表わすことができ、またビューアに対
してより正確に表示することができる。

【０１５７】図１５Ａ，１５Ｂは、ＣＰＵ４によって実
行され、本実施の形態でステップＳ１６（図２Ａ）にお
いてリファイメントが実行される処理操作を示すフロー
チャートである。

【０１５８】図１５Ａ，１５Ｂを参照して、ステップＳ
２９８において、実行されるべき処理が実行され、画像
データの第１フレームが発生させるかどうかＣＰＵ４が
決定する。処理が第１フレームを発生されることが決定
されれば、どのモデルのリファインメントも実行され
ず、従って、各モデルが第１フレームのために、リファ
インされていない形態に処理される。

【０１５９】一方、処理が画像データの第２又は次のフ
レームのために処理されれば、次に、ステップＳ３００
において、ＣＰＵ４が処理されるべき次のオブジェクト
を考慮している（これは第１のオブジェクトであり、最
初にステップＳ３００が実行される）。ステップＳ３０
２において、ＣＰＵ４がオブジェクトのモデル中で次の
三角形を考慮する。

【０１６０】ステップＳ３０４において、三角形の各エ
ッジが、「キープ・エッジ」フラグ、「エッジの付けら
れた」フラグ、「境界エッジ」フラグ、又は「無効エッ
ジ共用」フラグでセットされているかどうかをＣＰＵ４
が決定する。これらのフラグの一つが三角形中のどのエ
ッジもセットされていなければ、三角形の少なくとも一
つのエッジ（又は、より詳しく説明すると、フラグの一
つがセットされていないエッジ）が変更されることにな
る。これはバーンスタイン−ベジエ三角形パッチがこの
三角形エッジと一致しないからである。

【０１６１】従って、三角形の少なくとも一つのエッジ
がこれらのフラグの一つをセットしていないことをＣＰ
Ｕ４が決定すれば、次にステップＳ３０６において、Ｃ
ＰＵ４がこの三角形に必要とされているモザイクの深さ
を決定する。（ステップＳ３０６は、これらのフラグの
一つが三角形中のどのエッジのためにもセットされれ
ば、省略される。）図１６は、ステップＳ３０６においてＣＰＵ４によって
実行され、三角形のためのモザイクの深さを決定するた
めの処理操作を示すフローチャートである。

【０１６２】図１６を参照して、ステップＳ３４２にお
いて、ＣＰＵ４がビューアに対して表示された画像デー
タの前回フレームから三つの三角形頂点のスクリーン座
標を読み取る。

【０１６３】ステップＳ３４４において、ＣＰＵ４がス
テップＳ３４２で読み取った頂点座標を使用して前回フ
レーム中の三角形のエリア（面積）を決定する。

【０１６４】本実施の形態において、発生中の現データ
のための画像フレーム中の三角形のエリアが、前回フレ
ーム中の三角形のエリアとほぼ同じであると仮定する。
これはオブジェクトが一つのフレーム周期で大きく移動
しないからである。従って、ステップＳ３４６におい
て、ＣＰＵ４が入力としてステップＳ３４４において決
定された三角形のエリアを第１ルックアップ・テーブル
に対して使用し、この入力値に対するルックアップ・テ
ーブル中に規定された深さの値を読み取る。

【０１６５】図１７（ａ）は、本実施の形態中の第１ル
ックアップ・テーブル内に記憶された情報を示す図であ
る。

【０１６６】図１７（ａ）を参照して、本実施の形態に
おいて、このルックアップ・テーブルは１０個の異なる
深さ値の一つを具体的に挙げている。第１深さ値、すな
わち、深さ１は三角形のモザイクはまったく発生してい
ないことを指示している。後述するように、深さ２から
９は、モザイクの発生されたことを示しており、深さが
増すにつれて、三角形がより小さい三角形の数に分割さ
れる。前回フレーム中の三角形のエリアが増大するにつ
れて、深さ値が増す（これは、ユーザが三角形をもっと
詳しく見ることができ、従って、多数のより小さい三角
形が必要とされる詳細を表示することが望ましい）。

【０１６７】図１６を再度参照して、ステップＳ３４８
において、ＣＰＵ４がトポロジー的データベースから、
ステップＳ９９（図４Ｂ）において前回記憶されたベク
トル・ノーマルのドット−プロダクトの最少値を読み取
る。上述したように、この値は三角形を表示するオブジ
ェクト面の一部の曲率を表わす。

【０１６８】ステップＳ３５０において、ＣＰＵ４がス
テップＳ３４８において、第２ルックアップ・テーブル
への入力として読み取りした最少ドット・プロダクツ値
を使用し、この入力値のためのルックアップ・テーブル
中に規定された深さ値を読み取る。

【０１６９】図１７（ｂ）は、本実施の形態中の第２ル
ックアップ・テーブル内に記憶された情報を示す図であ
る。

【０１７０】図１７Ｂを参照して、深さ値が頂点ノーマ
ル・ドット・プロダクツ値の減少に伴って増大する（す
なわち、三角形を表わしているオブジェクト面の曲率が
増大するにつれて、多数の小さい三角形が、曲率を表わ
すのに必要となる）ことが分る。第１ルックアップ・テ
ーブルと比較すると、第２ルックアップ・テーブルから
の出力は１０の異なる深さ値の一つである。

【０１７１】ステップＳ３５２において、ＣＰＵ４がス
テップＳ３４６における三角形面積と依存する第１ルッ
クアップ・テーブルから読み取られた深さ値と、ステッ
プＳ３５０において読み取られた最少頂点ノーマル・ド
ット・プロダクツに依存する第２ルックアップ・テーブ
ルからの読み取られた深さ値とを組み合わせる。本実施
の形態において、二つの深さ値が加算され、一方が合計
から減算され、モザイクのための最終深さ値を提供す
る。例えば、三角形が１０００ピクセル（画素）のエリ
アを有しておれば、ステップＳ３４６において第１ルッ
クアップ・テーブルから読み取られた深さ値は５であ
り、三角形の最少頂点ドット・プロダクツが０．８０で
あれば、ステップＳ３５０において第２ルックアップ・
テーブルから読み取られた深さ値は２である。従って、
ステップＳ３５２において、モザイクの深さは５＋２−
１＝６と決定される。

【０１７２】図１５Ａ，１５Ｂを再度参照して、ステッ
プＳ３０８において、オブジェクトのモデル内で別の三
角形が考慮されているかどうか、ＣＰＵ４が決定する。
モデル内の三角形の全てが上述した方法で処理されるま
で、ステップＳ３０２からＳ３０８が反復される。

【０１７３】ステップＳ３１０において、ステップＳ３
０６においてモデル内の三角形のために決定されたモザ
イクの最も大きい深さを選択することによって全体のモ
デルのためのモザイクの深さをＣＰＵ４が決定する。こ
のモザイクがモデルの全ての三角形のために使用され
る。

【０１７４】ステップＳ３１２において、ステップＳ３
１０において決定された深さでモザイクされたモデルを
規定するデータが既にメモリに記憶されているどうか、
ＣＰＵ４が決定する。この決定が後述する理由で、オブ
ジェクトのモデルが新しい深さにモザイクされたとき
に、モザイクを規定するデータが次の使用のために記憶
されるように実行される。

【０１７５】要求されたモザイクを規定するデータが、
メモリに記憶されたことがステップＳ３１２において決
定されれば、次にステップＳ３１４において、データが
メモリから読み取りされる。一方、必要とされるモザイ
クを規定するデータが記憶されていないことがステップ
Ｓ３１２で決定されれば、次にステップＳ３１６におい
て、ＣＰＵ４がモデルの三角形全てに対してモザイクを
ステップＳ３１０において規定された深さに処理するよ
うに実行する。

【０１７６】図１８は、ＣＰＵ４によって、ステップＳ
３１６（図１５Ｂ）でモザイクを実行するように実行さ
れた処理操作を示すフローチャートである。

【０１７７】図１８を参照して、ステップＳ３６０にお
いて、ＣＰＵ４がモデル内の次の三角形を考慮してい
る。

【０１７８】ステップＳ３６２において、ＣＰＵ４が次
の新しい頂点が形成されるための三角形上のポイントの
重心座標を計算する（これは第１の新しい頂点であり、
最初にステップＳ３６２が実行される）。

【０１７９】図１９は、新しい頂点が本実施の形態で深
さ２、３及び４につき形成されるための三角形上のポイ
ントを示す（図１７（ａ）及び１７（ｂ）に関して前に
説明したように、深さ１ではモザイクが生じない）。

【０１８０】図１９（ａ）を参照して、三角形が深さ２
までモザイクされたときに、新しい三角形頂点がポイン
ト１７０、１７２及び１７４に対して計算され、各々三
角形の各サイドに沿って半分のところに位置する。新し
い頂点は実際にはポイント１７０、１７２及び１７４に
配置されているのではなく、新しい頂点の位置はこれら
の端に関するバーンスタイン−ベジエ三角形パッチの高
さに依存してポイント１７０、１７２及び１７４のそれ
ぞれにつき計算される。これについては後述する。

【０１８１】図１９（ｂ）を参照して、三角形が深さ３
までモザイクされると、新しい頂点がポイント１７６、
１７８、１８０、１８２、１８４及び１８６のそれぞれ
に対して計算され、三角形の各エッジが１／３に分割さ
れる。新しい頂点もポイント１８８のために計算され、
その三角形上の位置が図１９（ｂ）に示されたようにポ
イント１７６、１７８、１８０、１８２、１８４及び１
８６を連結することによって決定される。

【０１８２】図１９（ｃ）を参照して、三角形が深さ４
までモザイクされると、新しい頂点がそれぞれのポイン
ト１９０、１９２、１９４、１９６、１９８、２００、
２０２、２０４及び２０６のために形成され、各ポイン
トは三角形のエッジに沿って等しく隔置され、各エッジ
は１／４に分割される。新しい頂点が三角形の内側でポ
イント２０８、２１０及び２１２のために計算され、そ
の位置は図１９（ｃ）に示したようにポイント１９０、
１９２、１９４、１９６、１９８、２００、２０４及び
２０６を連結することによって決定される。

【０１８３】他の深さレベルのために計算される新しい
頂点のポイントは、同様の方法で決定される。三角形の
各エッジに沿って生じた新しい頂点の数は、深さの数マ
イナス１に等しく、また元の三角形の分割される新しい
三角形の数は、深さの数の２乗に等しい。例えば、三角
形が深さ１０までモザイクされると、新しい頂点は、エ
ッジが１０個に分割される三角形の各エッジに沿って９
個のポイントにつき計算され、また、三角形の内側のポ
イントについてはエッジに沿ったポイント同士が相互連
結されることによって決定される。従って、生じた三角
形の数は１００である。

【０１８４】新しい頂点が形成されることになる三角形
内のポイントの重心座標が、各深さレベルのために前も
って計算され、かつ、記憶できることが分る。このよう
にして、ステップＳ３６２において重心座標を決定する
ステップは、メモリから必要とされる座標を読み取るこ
とによって実行できる。

【０１８５】図１８を再度参照して、ステップＳ３６４
において、ＣＰＵ４がステップＳ８において三角形のた
めに前回計算された縦座標を使用して、その重心座標が
ステップＳ３６２において決定される三角形上方の上述
のポイントのバーンスタイン−ベジエ三角形パッチの高
さを計算する。これはテップＳ３６２において決定され
た重心座標を使用するバーンスタイン−ベジエ三角形パ
ッチ式を評価することによって実行される。より詳しく
説明すると、ＣＰＵ４が新しいポイントの重心座標（τ
₁,τ₂,τ₃）と、ステップＳ８において計算された縦座
標b₀₀₃, b₀₃₀, b ₃₀₀, b₁₀₂, b₂₀₁, b₀₁₂, b₀₂₁, b₁₂₀,
b₂₁₀, b₁₁₁を使用して上述の式６を評価して、上述のポ
イントのバーンスタイン−ベジエ三角形パッチの高さと
なるｂ³（τ）の値を提供する。

【０１８６】ステップＳ３６６において、ＣＰＵ４が、
その重心座標がステップＳ３６２において読み取られた
三角形上のポイントにおけるノーマルを計算する。本実
施の形態において、ＣＰＵ４が次式を用いてノーマル、
Ｎ_newを計算する：

【０１８７】

【数７】ここで、Ｎ１、Ｎ２及びＮ３は三角形の頂点におけるユ
ニット・ノーマル・ベクトルである。より詳しく説明す
ると、第１重心座標がノン−ゼロである頂点がノーマル
Ｎ１を有するように規定され、第２重心座標がノン−ゼ
ロである頂点がノーマルＮ２を有するように規定され、
また、第３重心座標がノン−ゼロである頂点がノーマル
Ｎ３を有するように規定される。

【０１８８】ステップＳ３６８において、ＣＰＵ４がス
テップＳ３６４において計算された高さと、ステップＳ
３６６において計算されたノーマルとを使用して、モザ
イクに使用されるべき新しい頂点の位置を計算する。よ
り詳しく説明すると、ＣＰＵ４は、その重心座標が、ス
テップＳ３６６で計算されたノーマルの方向に測定され
たステップＳ３６４において計算された高さに等しい、
ステップＳ３６２において読み取られる元の三角形上の
ポイントから測定された距離にあるポイントとして新し
い頂点の位置が計算される。

【０１８９】図２０は、図１８のステップＳ３６４、Ｓ
３６６及びＳ３６８において計算された例を示す図であ
る。

【０１９０】図２０を参照して、バーンスタイン−ベジ
エ三角形パッチ１４４を、図１４（ｂ）に関して前回説
明した三角形３２のために示す。前記ステップＳ３６４
で計算されたポイント１７０上方の（図１９（ａ）に関
して前回説明したように、三角形のサイドの中央点であ
る）バーンスタイン−ベジエ三角形パッチの高さは
「Ｈ」である。ポイント１７０におけるベクトル・ノー
マルはＮ_newである。モザイク中で使用されるべき新し
い頂点の位置は、ポイント１７０から距離「Ｈ」だけノ
ーマルＮ_newに沿ったポイント２２０である。図２０に
示した例から分るように、新しいポイントはステップＳ
８（図２Ａ）においてＣＰＵ４によって前回計算された
縦座標によって規定されたバーンスタイン−ベジエ三角
形パッチの面にある必要はない。

【０１９１】図１８を再度参照して、ステップＳ３７０
において、ＣＰＵ４がステップＳ３６８において計算さ
れた新しい頂点のためのベクトル・ノーマルを規定す
る。本実施の形態において、ＣＰＵ４がステップＳ３６
６で計算されたベクトル・ノーマルと同じとなるベクト
ル・ノーマルを規定する。

【０１９２】ステップＳ３７２において、ＣＰＵ４が、
計算されれるべきモザイク中に使用される新しい頂点の
ために元の三角形上に別の頂点があるかどうか決定す
る。新しい頂点が三角形上の各必要とするポイント（す
なわち、深さレベルによって規定された三角形上のポイ
ント；例えば、深さレベル２である図１９（ａ）に示さ
れたポイント１７０、１７２及び１７４と、深さレベル
が深さ３である図１９（ｂ）に示されたポイント１７
６、１７８、１８０、１８２、１８４、１８６及び１８
８）のために計算されるまで、ステップＳ３６２からＳ
３７２が反復される。

【０１９３】ステップＳ３７４において、ＣＰＵ４がス
テップＳ３６８において計算された新しい頂点間の連結
が規定される。これは元の三角形のための多数のモザイ
ク三角形を規定する。モザイク三角形は元の三角形の平
面にある必要はなく、従って、元の三角形がフラットに
表わされたオブジェクト面の曲率をより正確に表わされ
る。（モザイクされた三角形は、元の三角形の各エッジ
が「キープ・エッジ」フラグ、「エッジの付けられた」
フラグ、「境界エッジ」フラグ又は「「無効エッジ共
用」フラグ・セットを有しておれば、元の三角形として
同じ平面に全てあることになる）。

【０１９４】図２１は、図１４に示した三角形が、深さ
２にモザイクされたときの、モザイク三角形の例を示す
図である。

【０１９５】図２１（ａ）を参照して、新しい頂点２２
０、２２２及び２２４が発生され、接続される。いずれ
の新しい頂点も元の三角形の平面内の元の三角形のエッ
ジに沿って置かれていない。なぜなら、三角形３２のエ
ッジは「キープ・エッジ」フラグ、「エッジの付けられ
た」フラグ、「境界エッジ」フラグ又は「無効エッジ共
用」フラグ・セットをいずれも有していないからであ
る。

【０１９６】図２１（ｂ）を参照して、新しい頂点２３
０、２３２及び２３４が作成され、かつ、連結される。
新しい頂点２３２は、エッジ３０が「キープ・エッジ」
フラグ、「エッジの付けられた」フラグ又は「無効エッ
ジ共用」フラグ・セットを有しているので、エッジ３０
に沿った中央に位置する。

【０１９７】図２１（ｃ）を参照して、三角形３２のた
めの新しい頂点２３０、２３２及び２３４は、図２１
（ｂ）に示したものと同じである。しかし、図２１
（ｃ）は、エッジ３０が三角形３２と三角形３８の共通
であり、三角形３８のために修正されている一例であ
り、これはエッジ３０が三角形３８のための「キープ・
エッジ」フラグ、「エッジの付けられた」フラグ、「境
界エッジ」フラグ又は「無効エッジ共用」フラグ・セッ
トを有していないからである。より詳しく説明すると、
図２１（ｃ）に示した例は、エッジ３０が三角形３２の
ための「エッジの付けられた」フラグ・セットを有し、
また、三角形３８のための「エッジの付けられている」
フラグのセットを有している場合に対応する。従って、
三角形３８に対して、新しい頂点２４０が計算される。
三角形３８の他のエッジのための新しい頂点は、図２１
（ｃ）に示されていない。図２１（ｃ）から分るよう
に、三角形３２と三角形３８間のギャップ２４２（ドッ
ト域で示された）が、エッジ３０に沿って形成されるこ
とが分る。このエッジが処理される方法は後述する。

【０１９８】図２１（ｄ）を参照して、新しい頂点２５
０、２５２及び２５４が三角形３２のために形成され、
また、新しい頂点２５６が三角形３８の辺３０のために
形成される（三角形３８の他の辺のために形成された新
しい頂点は、図２１（ｄ）には示していない）。図２１
（ｄ）に示した例は、「エッジ・ノーマル不明瞭」フラ
グが三角形３２と三角形３８のエッジ３０のためにセッ
トされるケースに対応するが、「キープ・エッジ」フラ
グはいずれの三角形のエッジ３０のためにもセットされ
ない。図２１（ｄ）から分るように、ギャップ２５８
（ドット域で示された）は、三角形３２と三角形３８間
に形成される。

【０１９９】図１８を再度参照して、ステップＳ３７６
において、ＣＰＵ４がモデル内で処理されるべき別の三
角形があるかどうかを決定する。ステップＳ３６０から
Ｓ３７６が、各三角形が処理され上述した方法でモザイ
ク三角形を発生するまで、反復される。

【０２００】図１５Ａ，１５Ｂを再度参照して、ステッ
プＳ３１８において、ＣＰＵ４がステップＳ３１６にお
いて発生されたモザイク化モデルのトポロジーを修正す
るように処理を実行する。より詳しく説明すると、ＣＰ
Ｕ４は近接する三角形間で形成されたモデル内のどのギ
ャップも、図２１（ｃ）の例に示したギャップ２４２及
び図２１（ｄ）の例に示されたギャップ２５８のような
どのギャップも満たすように処理がなされる。

【０２０１】図２２Ａ，２２Ｂは、図１５Ｂのステップ
Ｓ３１８において、ＣＰＵ４によって実行され、トポロ
ジーを修正する処理操作を示す。

【０２０２】図２２Ａ，２２Ｂを参照して、ステップＳ
３９０からＳ４００において、ＣＰＵ４が「エッジの付
けられた」フラグが一つの三角形のエッジのためにセッ
トされ、また「エッジの付けられている」フラグが他の
三角形のためにセットされるエッジに沿って三角形間に
形成されたギャップを満たす処理を実行する。

【０２０３】より詳しく説明すると、ステップＳ３９０
において、ＣＰＵ４がモデル内の次の三角形を考慮し、
またステップＳ３９２において、ＣＰＵ４がトポロジー
的データベースから三角形のためのエッジ・フラグを読
み取る。

【０２０４】ステップＳ３９４において、ＣＰＵ４が、
「エッジの付けられた」フラグが三角形のいずれかのエ
ッジのためにセットされたか決定する。このフラグがセ
ットされなければ、処理はステップＳ４００に進行す
る。一方、「エッジの付けられた」フラグがセットされ
たことが決定されれば、次にステップＳ３９６におい
て、「エッジの付けられた」フラグがセットされる各エ
ッジのために、ＣＰＵ４がステップＳ３６８（図１８）
におけるモザイクによって発生されたエッジのための新
しい頂点を移動して、「エッジの付けられている」フラ
グがセットされた対応するエッジのための対応する新し
い頂点と一致させる。図２１（ｃ）を再度参照して、一
例として「エッジの付けられた」フラグが三角形３２の
エッジ３０のためにセットされ、また「エッジの付けら
れている」フラグが三角形３８のエッジ３０のためにセ
ットされる。従って、ステップＳ３９６において、ＣＰ
Ｕ４がモザイクによって発生されたエッジ３０のための
新しい頂点２３２の位置を、三角形３８のエッジ３０の
ために発生された対応する新しい頂点２４０の位置に移
動させる。

【０２０５】図２３（ａ）は、さらなる例として、三角
形３２と三角形３８が深さ４までモザイクされる場合を
示す。再度、「エッジの付けられた」フラグが三角形３
２のエッジ３０のためにセットされ、従って、ステップ
Ｓ３６８（図１８）におけるモザイクによって発生され
た三つの新しい頂点２７０、２７２、２７４はエッジ３
０上にくる。エッジ３０は三角形３８のための「エッジ
の付けられている」フラグを有している。従って、エッ
ジ３０と三角形３８のためにモザイクによって発生され
た新しい頂点２７６、２７８、２８０はエッジ３０に沿
ってはいない。ステップＳ３９６において、ＣＰＵ４が
頂点２７０の位置を頂点２７６の位置に移動させ、頂点
２７２の位置を頂点２７８の位置に移動させ、また、頂
点２７４の位置を頂点２８０の位置へ移動させる。

【０２０６】図２３（ｂ）は、ステップＳ３９６が実行
された後、図２３（ａ）の例から得られることになる三
角形３２のモザイクを示す。

【０２０７】図２３（ｂ）を参照して、移動する頂点２
７０、２７２及び２７４の結果は、その頂点の一つを包
含するモザイク三角形はそれぞれその形状（また、ほと
んどの場合、その頂点のある平面で）が変形される。図
２３（ａ）の例において、頂点２７０、２７２及び２７
４は元の三角形から移動して三角形３８の対応するリフ
ァインされた頂点と一致している。従って、図２３
（ｂ）に示したように、三角形３００、３０２、３０
４、３０６、３０８、３１０及び３１２は、残りのモザ
イク三角形よりも大きくなっている。

【０２０８】しかし、モザイク三角形はほぼ均一したサ
イズで、かつ、元の三角形上に均一に分布されるのが望
ましい。このようにして、三角形の平面が「エッジの付
けられた」フラグ・セットを有するエッジのための頂点
の移動によって変化される場合、その下にあるオブジェ
クト面の曲率がより均一にモデル化される。

【０２０９】従って、図２２Ａ，２２Ｂを再度参照し
て、ステップＳ３９８において、ＣＰＵ４が、元の三角
形の内側にあるモザイク三角形の頂点を再分配する。図
２３（ｂ）の例において、これらの頂点は頂点３２０、
３２２及び３２４である。このステップで再分配される
べき内側頂点の数はモザイクの深さに依存しており、深
さの増大につれて内側頂点の数が増加することが分る。
モザイクの深さが深さ２であるとき、再分配される内側
頂点がないことが図１９（ａ）から分る。

【０２１０】図２４はＣＰＵ４によって実行され、図２
２ＡのステップＳ３９８における内側頂点の再分布の処
理操作を示す。

【０２１１】図２４を参照して、ステップＳ４２０にお
いて、ＣＰＵ４が次の内側頂点を考慮している。ステッ
プＳ４２２において、ＣＰＵ４が目下考慮中の内側頂点
に連結された６個のエッジ頂点の各々の重心座標を決定
する。

【０２１２】図２５は、図２３（ａ）と図２３（ｂ）に
示された例から深さ４まで分割された三角形３２を示す
図である。

【０２１３】図２５を参照して、三角形３２は深さ４に
分割され、従って、３個の内側頂点３２０、３２２及び
３２４が再分配されている。各頂点の重心座標が図２５
に示されている。

【０２１４】内側頂点が連結された６個のエッジ頂点
が、一つのエッジ頂点が到達するまで、三角形エッジと
平行な六つの方向にある内側頂点から進行して頂点にな
る。従って、重心座標（２、１、１）を有する頂点３２
０が、重心座標（３、１、０）、（２、２、０）、
（３、０、１）、（２、０、２）、（０、３、１）及び
（０、１、３）を有する６個のエッジ頂点に連結され
る。

【０２１５】同様にして、内側頂点３２２が重心座標
（１、２、１）を有し、重心座標（１、３、０）、
（２、２、０）、（３、０、１）、（１、０、３）、
（０、３、１）及び（０、２、２）を有する６個のエッ
ジ頂点に連結される。内側頂点３２４が重心座標（１、
１、２）を有し、重心座標（１、３、０）、（３、１、
０）、（２、０、２）、（１、０、３）、（０、１、
３）及び（０、２、２）を有する６個のエッジ頂点に連
結される。

【０２１６】内側頂点から一つのエッジに進行すると、
頂点の重心座標の一つが減ることになる。例えば、内側
頂点３２４からエッジ頂点２７０へ進行するとき、３番
目の重心座標が頂点３２４における２から頂点３２２に
おける１へ、頂点２７０における０へ減る。さらに、内
側頂点からエッジに進行するとき、別の重心座標は一定
を維持することになる。例えば、内側頂点３２４からエ
ッジ頂点２７０へ進行するとき、最初の重心座標が一定
値１を有する。

【０２１７】ステップＳ４２２において、ＣＰＵ４が、
内側頂点に連結された各エッジ頂点が、０となる一つの
重心座標を有し、また、さらなる重心座標が内側頂点の
座標と同じであるという事実を使用して６個の連結され
たエッジ頂点の完全な重心座標を計算する。

【０２１８】ステップＳ４２４において、ＣＰＵ４が、
内側頂点に連結された６個のエッジ頂点のそれぞれに対
する重さを計算する。本実施の形態において、ＣＰＵ４
が目下考慮中の内側頂点の重心座標と、０であるエッジ
頂点の重心座標に基づいて各連結エッジ頂点のための重
さを決定する。より詳しく説明すると、エッジ頂点の第
１重心座標が０であれば、次にＣＰＵ４が内側頂点の第
１重心座標の逆数の重さをこの頂点に割り当てる。同様
にして、エッジ頂点の第２重心座標が０であれば、次に
ＣＰＵ４が内側頂点の第２重心座標の逆数の重さを割り
当てし、一方、エッジ頂点の第３重心座標が０であれ
ば、次にＣＰＵ４が内側頂点の第３重心座標の逆数の重
さを割り当てる。

【０２１９】図２５の例を再度参照して、内側頂点３２
２のために、エッジ頂点２７０とエッジ頂点２７２（そ
の第３重心座標が０である）に割り当てられた重さは１
／１で、エッジ頂点３３０と３３２（その第１重心座標
が０である）に割り当てられた重さは１／１で、エッジ
頂点３３４と３３６（その第２重心座標が０である）に
割り当てられた重さは１／２である。

【０２２０】ステップＳ４２６において、ＣＰＵ４が６
個の連結エッジ頂点の各々の３次元位置（すなわち、頂
点がステップＳ３９６で移動した後の位置）を読み取
り、ステップＳ４２４で計算された重さに基づく位置を
組み合わせて、目下考慮中の内側頂点のための新しい位
置を提供する。本実施の形態においてステップＳ４２６
におけるこの組み合わせは次式を使用して実行されベク
トル・センス内の位置を組み合わせる：

【０２２１】

【数８】ここで、Ｖ^newは内側頂点の新しい３次元位置である；
Ｗ_i（ｉ＝１．．６）はステップＳ４２４において計算
されたｉ番目のエッジ頂点である；Ｖ_i（ｉ＝１．．
６）はｉ番目のエッジ頂点の３次元位置である。

【０２２２】ステップＳ４２６において、内側頂点の位
置は元の三角形の平面と平行に移動するだけでなく、内
側頂点は元の三角形の上方へ異なる高さにも移動するこ
とが理解できる。

【０２２３】上述したように、ステップＳ４２０からＳ
４２６が実行されることにより、ＣＰＵ４が、６個の連
結エッジ頂点に依存して内側頂点を再位置付けする。内
側頂点に最も近いエッジ頂点が、内側頂点からさらに離
れたエッジ頂点よりも大きい重さを有しており、従っ
て、最も近いエッジ頂点の位置がさらに離れたエッジ頂
点の位置よりも内側頂点の位置に影響を与える。

【０２２４】ステップＳ４２８において、ＣＰＵ４が再
位置付けされるべき別の内側頂点があるかどうか決定す
る。ステップＳ４２０からＳ４２８が、すべての内側頂
点が上述したようにして再位置付けされるまで、反復さ
れる。

【０２２５】図２２Ａ，２２Ｂを再度参照して、ステッ
プＳ４００において、ＣＰＵ４が、未だ考慮されていな
いモデル内に別の三角形があるかどうか決定される。ス
テップＳ３９０からＳ４００が、モデル内の全ての三角
形が上述した方法で処理されるまで、反復される。

【０２２６】ステップＳ４０２からＳ４０８において、
ＣＰＵ４が、「エッジ・ノーマル不明瞭」フラグがエッ
ジのためにセットされるが、「キープ・エッジ」フラグ
がいずれのエッジ（これは、エッジが例えば図２１
（ｄ）の例で示したエッジを共用する両三角形のために
修正されたエッジ中の状況に対応している）のためにも
セットされないエッジに沿って三角形間に生じたギャッ
プを埋める処理を実行する。

【０２２７】より詳しく説明すると、ステップＳ４０２
において、ＣＰＵ４がトポロジー的データベースからエ
ッジ・フラグを読み取る。ステップＳ４０４において、
ＣＰＵ４が「エッジ・ノーマル不明瞭」フラグがセット
されるが、「キープ・エッジ」フラグがセットされない
次のエッジ対を考慮する。

【０２２８】ステップＳ４０６において、ＣＰＵ４が二
つの修正エッジ間のギャップを満たす。本実施の形態に
おいて、ＣＰＵ４が、モザイクによって発生された新し
い頂点を連結して「スティチング三角形」を形成するこ
とによってこれを実行する。

【０２２９】図２６は、どのようにしてスティチング三
角形がステップＳ４０６（図２２Ｂ）においてＣＰＵ４
により発生されるかという例を示す。

【０２３０】図２６（ａ）は、エッジを共用する三角形
が深さ２までモザイクされた例を示す。この場合におい
て、モザイクによって発生された新しい頂点３５０、３
５２が連結されてスティチング三角形３５４と３５６を
形成する。

【０２３１】図２６（ｂ）は、三角形３２と３８が深さ
３までモザイクされた例を示す。この場合において、三
角形３２の頂点３６０は三角形３８（すなわち、この頂
点はエッジ３０上の同じ元のポイントからなる）の対応
する頂点に連結され、これが頂点３６２になる。同様に
して、三角形３２の頂点３６４は三角形３８の対応する
頂点３６に連結される。付加的に、頂点３６０、３６
２、３６６及び３６４によって形成された四角形が、三
角形３２からの頂点３６０を、四辺形の対向コーナーに
おける三角形３８の頂点３６６と連結することによって
三角形に分割される。

【０２３２】図２６（ｃ）は、三角形３２と３８が深さ
４までモザイクされた例を示す。この状況において、三
角形３２の頂点３７０が三角形３８の対応する頂点３７
２に連結され、三角形３２の頂点３７４が三角形３８の
対応する頂点３７６に連結され、また三角形３２の頂点
３７８が三角形３８の対応する頂点３８０に連結され
る。連結された頂点３７０、３７２、３７６及び３７４
によって形成された四辺形を分割するために、ＣＰＵ４
が三角形３２の頂点３７０を三角形３８の頂点３７６に
四辺形の対向するコーナーに連結する。同様にして、連
結された頂点３７４、３７６、３８０及び３７８によっ
て形成された四辺形を三角形に分割するために、ＣＰＵ
４が三角形３２の頂点３７４を三角形３８の頂点３８０
に四辺形の対向するコーナーで連結する。

【０２３３】図２２Ａ，２２Ｂを再度参照して、ステッ
プＳ４０８において、ＣＰＵ４が、「エッジ・ノーマル
不明瞭」フラグがセットされているが、「キープ・エッ
ジ」フラグはセットされていない別の対のエッジがある
かどうか決定する。ステップＳ４０４からＳ４０８が、
「エッジ・ノーマル不明瞭」フラグがセットされ、「キ
ープ・エッジ」フラグがセットされない各対のエッジが
上述した方法で処理されるまで、反復される。

【０２３４】図１５Ａ，１５Ｂを再度参照して、ステッ
プＳ３２０において、ＣＰＵ４が、モザイクの同じ深さ
が必要なときに、別のフレームのための画像データの発
生において次の再使用のためにメモリ内にステップＳ３
１６とＳ３１８において発生されたデータを記憶する。

【０２３５】ステップＳ３２２において、ＣＰＵ４が処
理されるべき他のオブジェクトのモデルがあるかどうか
決定する。ステップＳ３００からＳ３２２が、各モデル
が上述した方法で処理されるまで、反復される。

【０２３６】図２Ａ，２Ｂを再度参照して、ステップＳ
１８において、ＣＰＵ４がステップＳ１６において発生
された三角形状多角形を照明する。

【０２３７】本実施の形態において、照明が各オブジェ
クトのオブジェクト・スペースで実行される。これはロ
ーカル変換（オブジェクトをそのオブジェクト・スペー
スから共通の３Ｄワールド・スペースに変換する）の逆
を計算し、各光源の位置に対して逆変換を実行し、これ
によって光源をオブジェクト・スペースに変換すること
によって実行される。

【０２３８】図２７Ａ，２７Ｂは、ＣＰＵ４によって実
行され、図２ＡのステップＳ１８において多角形を照明
する処理操作を示す。

【０２３９】図２７Ａ，２７Ｂを参照して、ステップＳ
４５０において、ＣＰＵ４が次のオブジェクトのモデル
を考慮している。

【０２４０】ステップＳ４５２において、ＣＰＵ４が、
表示されるべき画像データのフレームが第１フレームで
あるかどうかを決定する。このフレームが画像データの
第１フレームであることが決定されれば、次にステップ
Ｓ４５４において、ＣＰＵ４が従来方法でモデル内の各
三角形頂点における各色要素のための値を計算する。本
実施の形態において、各三角形頂点における各色要素の
ために、ＣＰＵ４が周囲光度値、分散光度値及び目下の
全ての光源を考慮した鏡面光度値を計算する。これは、
例えば、アディソン−ウエズリ・パブリッシング・カン
パニ刊、フォリ、ヴァン・ダム、フェイナとヒューズに
よる「コンピュータ・グラフィックスの原理及び方法」
第２版、ISBN-201-12110-7、セクション16.1及び16.2に
説明に説明したような従来の方法で実行される。

【０２４１】一方、表示されるべき画像データのフレー
ムは第１フレームでないことがステップＳ４５２で決定
されれば、次にステップＳ４５６において、ＣＰＵ４
が、ステップＳ１２において決定されたビューイング・
パラメータ（ビューされるべき画像から位置と方法が規
定される）が、前回フレーム以来変更されたかどうか決
定する。ビューイング・パラメータが変更されると、次
に処理がステップＳ４６２に進行する。

【０２４２】一方、ビューイング・パラメータが前回フ
レーム以来変更されていることが、ステップＳ４５６に
おいて決定されれば、次にステップＳ４５８において、
ＣＰＵ４が、照明パラメータ（ステップＳ１０において
決定された）が前回フレーム以来変更されないかどうか
決定する。照明パラメータが変更されていれば、次に処
理がステップＳ４６２に進行する。

【０２４３】一方、照明パラメータが前回フレーム以来
変更されていなければ、ステップＳ４５８において決定
されれば、次にステップＳ４６０において、ＣＰＵ４
が、オブジェクトが前回フレーム以来移動されたかどう
を決定する。オブジェクトが移動されていないことが決
定されれば、次にビューイング・パラメータ、照明パラ
メータ及びオブジェクト位置は、前回フレーム以来変更
されていないことになる。従って、ＣＰＵ４が目下のフ
レームのために前回フレームのために計算された明度値
を使用し、処理がステップＳ４８２に進行する。

【０２４４】一方、ビューイング・パラメータが変更さ
れたことがステップＳ４５６において決定されるか、又
はステップＳ４５８において、照明パラメータが変更さ
れたことが決定されるか、又はステップＳ４６０におい
て、オブジェクトが移動し、次に新しい明度値を計算す
る必要があり、処理がステップＳ４６２に進行する。

【０２４５】ステップＳ４６２において、ＣＰＵ４が、
モデルが所定深さより深くモザイクされるかどうか決定
される。本実施の形態において、所定の深さは深さ３
（図１９（ｂ）に示したように）である。このテストの
結果が、どのように明度値がモデルのために計算される
かを決定する。より詳しく説明すると、ステップＳ１６
におけるモデルのリファインメントは多数の新しい頂点
を発生し、各色要素のための値を発生し、各色要素のた
めの値が各頂点において計算されなければならない。従
って、実行されるべき計算の数は、頂点の数が増加する
につれて増加する。本実施の形態において、上述した従
来方法において各頂点における各色要素のための値を計
算するよりも、「照明パッチ」としての別の技術が使用
でき、コンピュータ処理的にはより有効である。この照
明パッチ技術は、計算されるべき明度値(lighting valu
es)のための頂点の数が所定値を超えたときに、従来技
術よりも有効である。本実施の形態で使用される照明パ
ッチ技術に基づいて、三角形が深さ３よりも大きい深さ
にモザイクされたときに、頂点の数の所定値に達する。
この理由で、ステップＳ４６２において実行されるテス
トが、モデルが深さ３より大きい深さにモザイクされる
かどうか決定する。

【０２４６】モデルが深さ３よりも大きい深さにモザイ
クされないことがステップＳ４６２で決定されれば、次
にステップＳ４６４、Ｓ４６６及びＳ４６８において、
ＣＰＵ４がモデル内の各頂点のために従来方法で明度値
を計算する。より詳しく説明すると、ステップＳ４６４
において、ＣＰＵ４がオブジェクトの元のモデル内で次
の三角形を考慮し、また、ステップＳ４６６において、
ＣＰＵ４が各元の頂点における各色要素の値と、ステッ
プＳ４５４に関する上述した従来方法によるモザイク三
角形の各新しい頂点を計算する。ステップＳ４６８にお
いて、ＣＰＵ４がオブジェクトのモデル内で処理される
べき別の三角形があるかどうか決定する。ステップＳ４
６４からＳ４６８が、モデル内の全ての三角形が上述し
た方法で処理されるまで、反復される。

【０２４７】一方、モデルが深さ３よりも大きい深さに
モザイクされたことがステップＳ４６２において決定さ
れれば、ステップＳ４７０からＳ４８０において、ＣＰ
Ｕ４が次に説明するように、「照明パッチ」を使用して
モデルのための明度値を計算する。

【０２４８】ステップＳ４７０において、ＣＰＵ４がオ
ブジェクトのモデル内の次の三角形を考慮し、また、ス
テップＳ４７２において次の色要素を考慮する。本実施
の形態において、色要素の赤、緑及び青が使用される
が、他の色要素計画も使用できることはもちろんであ
る。

【０２４９】ステップＳ４７４において、ＣＰＵ４が考
慮された三角形のための照明パッチを規定するパラメー
タと、考慮された色要素とを計算する。

【０２５０】図２８は、図２７ＢのステップＳ４７４に
おいてＣＰＵ４によって実行され、照明パッチを規定す
るパラメータを計算する処理操作を示すフローチャート
である。

【０２５１】図２８を参照して、ステップＳ５００にお
いて、ＣＰＵ４が三角形の各制御ポイントにおける色要
素のための値を計算する。三角形の制御ポイントは図１
０に示すとともに、これまでに説明したように１０ポイ
ントである。すなわち、三角形の頂点と、エッジを１／
３に分割する各エッジに沿った二つのポイントと三角形
の重心におけるポイントである。これらのポイントの各
々における色要素のための値が従来方法で計算される。
例えば、本実施の形態において、色要素のための周囲
値、色要素のための分散値及び色要素のための鏡面値が
考慮中の全ての光源に依存して計算され、これらの値が
総合されて所与の制御ポイントにおける色要素のための
全体値を提供する。

【０２５２】ステップＳ５０２において、ＣＰＵ４が、
その制御ポイントにおける色要素の計算値に対応する高
さで上述の各制御ポイントを規定する。

【０２５３】ステップＳ５０４において、ＣＰＵ４が三
角形の次のエッジを考慮する。

【０２５４】ステップＳ５０６において、ＣＰＵ４が、
パラメータ的パッチをしてエッジに沿った制御ポイント
を上述のステップＳ５０２において規定されたポイント
を補間せしめるエッジのための縦座標値を規定する。本
実施の形態において、座標が３次バーンスタイン−ベジ
エ三角形パッチのために計算される。

【０２５５】図２９は、図２８のステップＳ５０６にお
いて実行される処理操作の効果の一例を示す図である。

【０２５６】図２９（ａ）において、ポイント４００、
４０２、４０４及び４０６は三角形エッジ上に位置し、
三角形のこのエッジのための制御ポイントである（ポイ
ント４００と４０６は三角形の頂点であり、ポイント４
０２はポイント４００からエッジ長さの１／３のスペー
スがあり、また、ポイント４０４はポイント４０６から
エッジ長さの１／３のスペースがある）。ポイント４１
０、４１２、４１４及び４１６は、ステップＳ５００に
おいて計算された制御ポイントにおける色要素の値に対
応する制御ポイントの上方の高さでステップＳ５０２に
おいて規定されたポイントである。従って、本実施の形
態において、ステップＳ５００においてポイント４００
で計算された色要素の値はｈ０であるから、ポイント４
１０はポイント４００から上に高さｈ０にある。ポイン
ト４０２で計算された色要素の値はｈ１であるから、ポ
イント４１２はポイント４０２の上方に高さｈ１であ
る。ポイント４０２で計算された色要素の値はｈ１であ
るから、ポイント４１２はポイント４０２上方に高さｈ
１である。ポイント４０４で計算された色要素の値はｈ
２であるから、ポイント４１４はポイント４０４の上方
に高さｈ２である。ポイント４０６で計算された色要素
の値はｈ３であるから、ポイント４１６はポイント４０
６の上方に高さｈ３である。

【０２５７】ポイント４１０、４１２、４１４及び４１
６が縦座標として使用され３次バーンスタイン−ベジエ
三角形パッチを規定し、これでパッチのエッジがポイン
ト４１２と４１４を通過せず、代わりに図２９（ａ）の
破線４１８によって示した位置をとる。従って、ステッ
プＳ５０６において、ＣＰＵ４はバーンスタイン−ベジ
エ三角形パッチのエッジをしてポイント４１０、４１
２、４１４及び４１６の全てを通過せしめる縦座標値を
計算する。ステップＳ５０６において計算された縦座標
値を図２９（ｂ）に示し、ポイント４１０、４２０、４
２２及び４１６からなる。三角形頂点の縦座標は、バー
ンスタイン−ベジエ三角形パッチのエッジがこれらのエ
ンド・ポイントを補間するので、計算された色要素値と
同じ値を有する。従って、図示例において、ポイント４
００の縦座標は値ｈ０を有し、またポイント４０６の縦
座標は値ｈ３を有する。

【０２５８】三角形の頂点でないエッジに沿ったポイン
ト４０２と４０４における縦座標のための値を計算する
ために、ＣＰＵ４はポイント４０２上方のポイント４２
０の高さｈ１’の値を、また、ポイント４０４上方のポ
イント４２２の高さｈ２’の値を計算し、これで値ｈ
１’とｈ２’がバーンスタイン−ベジエ三角形パッチを
してポイント４１０、４１２、４１４及び４１６を補間
せしめる。

【０２５９】照明パッチの各エッジは３次ベジエ・ポリ
ノミナルによって規定される。パラメータｔ及び制御縦
座標ｈ０，ｈ１’，ｈ２’及びｈ３の３次ベジエ・ポリ
ノミナルのための式は：

【０２６０】

【数９】これを評価すると、ｔ＝１／３とｔ＝２／３（三角形エ
ッジに沿った制御ポイントの位置に対応する）における
ホリノミナルは次式で与えられる：

【０２６１】

【数１０】しかし、ステップＳ５００において計算された値を使用
すると：

【０２６２】

【数１１】従って、次のようにセットすると

【０２６３】

【数１２】式１０は次のようになり

【０２６４】

【数１３】これは次式に等価である

【０２６５】

【数１４】式１４が一次方程式であるから、クラメールの法則を使
用してｈ１’とｈ２’について解くと、次式が得られ
る：

【０２６６】

【数１５】また、結果として次式が得られ、ＣＰＵ４がこれをステ
ップＳ５０６で使用して各内側エッジ制御ポイント（図
２９Ａと２９Ｂの例のポイント４０２と４０４）のため
の縦座標値を計算する：

【０２６７】

【数１６】本実施の形態において、それが主観的により優れた照明
結果を提供することが分っているので、ゼロより小さく
なるようにステップＳ５０６において計算されたどの縦
座標値もゼロにセットされる。

【０２６８】図２８を再度参照して、ステップＳ５０８
において、ＣＰＵ４が処理されるべき三角形の別のエッ
ジがあるかどうかを決定する。ステップＳ５０４とＳ５
０８が、各エッジ制御ポイントのための縦座標が上述し
た方法で計算されるまで、反復される。

【０２６９】ステップＳ５１０において、ＣＰＵ４が三
角形の重心（すなわち、図１０に示した例においてポイ
ント１０８）における制御ポイントのための縦座標値を
計算する。

【０２７０】図３０はＣＰＵ４によって実行され、図２
８のステップＳ５１０において中央制御ポイントのため
の縦座標を計算する処理操作を示すフローチャートであ
る。

【０２７１】本実施の形態において、ＣＰＵ４が、頂点
間の三角形のエッジにある制御ポイントのためにステッ
プＳ５０６で前回計算された６個の縦座標と、これらの
制御ポイントのための６個の元の色要素値とを使用し
て、各制御値のためのファクターを計算し、色要素を掛
けたときに縦座標値を得る。６個のファクターが三角形
の重心における制御ポイントのための縦座標値を計算す
るのに使用される。この処理については後ほど詳しく説
明する。

【０２７２】図３０を参照して、ステップＳ５２０にお
いて、ＣＰＵ４が「総計（和）」とタイトルの付けられ
た可変値をゼロにセットする。

【０２７３】ステップＳ５２２において、ＣＰＵ４が考
慮されている三角形の頂点間のエッジ上にある次の制御
ポイントを考慮する（図１０に示した例を参照し、頂点
間のエッジ上にある制御ポイントは、ポイント９２、９
４、９８、１００、１０４及び１０６からなる）。

【０２７４】ステップＳ５２４において、ＣＰＵ４がス
テップＳ５００における制御ポイントのために計算され
た色要素の値を読み取り、値がゼロに等しいかどうかを
決定する。値がゼロに等しければ、次にステップＳ５２
６において、ＣＰＵ４が可変「和」の値に１を加算す
る。一方、制御ポイントにおける色要素の値がゼロに等
しくなければ、ステップＳ５２８において、ＣＰＵ４が
ステップＳ５０６において計算された制御ポイントにお
ける縦座標の値を、制御ポイントの色要素の値で分割し
（割り）、得られた値を可変「和」の値に加算する。

【０２７５】ステップＳ５３０において、ＣＰＵ４が三
角形の頂点間に別の制御ポイントがあるかどうか決定す
る。ステップＳ５２２からＳ５３０が、三角形の頂点間
で各制御ポイントが上述した方法で処理されるまで、反
復される。

【０２７６】ステップＳ５３２において、ＣＰＵ４が三
角形の重心における制御ポイントのための縦座標の値を
計算する。この値は（ｉ）重心における制御ポイントの
色要素の値（ステップＳ５００において前回計算され
た）と、(ii)可変「総計」の値と、(iii)１／６（これ
は可変「和」の値を導出するのに使用された頂点間の三
角形のエッジに沿ってある制御ポイントの数の逆数に対
応する）との積である。

【０２７７】上述した処理の結果、データが発生され、
三角形全体の制御ポイントにおいて計算された色要素の
値を補間（相補）する照明パッチを規定する。

【０２７８】図２７Ａ，２７Ｂを再度参照して、ステッ
プＳ４７６において、ＣＰＵ４が、ステップＳ４７４で
前回計算されたパラメータによって規定された照明パッ
チを使用して目下考慮されている元の三角形内で各モザ
イクされた三角形の各頂点における色要素のための値を
計算する。

【０２７９】図３１は、図２７ＢのステップＳ４７６に
おいてＣＰＵ４によって実行され、各頂点における色要
素のための値を計算する処理操作を示す。

【０２８０】図３１を参照して、ステップＳ５５０にお
いて、ＣＰＵ４が色要素の値が計算されるべき次の頂点
を考慮する。

【０２８１】ステップＳ５５２において、ＣＰＵ４が、
頂点が対応している元の三角形上のポイントの重心座標
を決定する。例によれば、図２３（ｂ）と図２５とを再
度参照して、頂点２７０に対応する元の三角形上のポイ
ントが重心座標（１、３、０）を有するポイントであ
る。同様にして、頂点２７４に対応する元の三角形上の
ポイントが、重心座標（３、１、０）を有するポイント
であり、また、頂点３２４に対応する元の三角形上のポ
イントが、重心座標（１、１、２）を有するポイントで
ある。

【０２８２】ステップＳ５５４において、ＣＰＵ４が元
の三角形上のポイント上方の３次バーンスタイン−ベジ
エ三角形照明パッチ（ステップＳ４７４で計算されたパ
ラメータによって規定される）の高さを計算する。これ
はステップＳ５５２で決定された重心座標を使用する照
明パッチ式を評価することによって実行される。この照
明パッチの式は、ステップＳ５５２によって決定され
る。照明パッチの式は式６によって与えられ、上述した
ように、縦座標b₀₀₃, b₀₃₀, b₃₀₀, b₁₀₂, b₂₀₁,b₀₁₂, b
₀₂₁, b₁₂₀及びb₂₁₀の値が、ステップＳ５０６で前回計
算された値であり、縦座標b₁₁₁の値がステップＳ５１０
で前回計算された値である。

【０２８３】ステップＳ５５６において、ＣＰＵ４が、
計算されるべき色要素のための値で別の頂点があるかど
うか決定する。ステップＳ５５０からＳ５５６が、色要
素のための値が上述した各頂点において計算されまで、
反復される。

【０２８４】図２７Ａ，２７Ｂを再度参照して、ステッ
プＳ４７８において、ＣＰＵ４が、三角形内の各頂点に
おけるその明度値が計算されるべき別の色要素があるか
どうか決定する。ステップＳ４７２からＳ４７８が、元
の三角形内の各頂点における各色要素のための値が上述
した方法で計算されるまで、反復される。

【０２８５】ステップＳ４８０において、ＣＰＵ４が、
モデル内に別の三角形があるかどうかを決定する。テッ
プＳ４７０からＳ４８０が、モデル内の各三角形が上述
した方法で処理されるまで、反復される。

【０２８６】ステップＳ４８２において、ＣＰＵ４が、
処理されるべき別のオブジェクトのモデルがあるかどう
かを決定する。テップＳ４５０からＳ４８２が、各モデ
ルが上述した方法で処理されるまで、反復される。

【０２８７】図２Ａ，２Ｂを再度参照して、ステップＳ
２０において、ＣＰＵ４がオブジェクトのモデリング・
スペースから各オブジェクトを形成している三角形を３
次元ビューイング・スペースに変換する。より詳しく説
明すると、ステップＳ１４で抜粋されるオブジェクトの
操作中に境界ボックスに変換するのに使用される連鎖マ
トリックスが再度使用され、オブジェクト・スペースか
らビューイング・スペースに実際のオブジェクト多角形
に変換される。これまでに説明したように、連鎖マトリ
ックスは、オブジェクトをそのオブジェクト・スペース
を共用３Ｄスペースに変換するローカル変換と、オブジ
ェクトを３Ｄワールド・スペースから３Ｄビューイング
・スペースに変換するビュー変換とを規定するマトリッ
クスからなる。

【０２８８】ステップＳ２２において、ＣＰＵ４がクリ
ッピング処理を実行して、ステップＳ１２において前回
決定されたビューイング・パラメータによって規定され
たビューの域の外側にある多角形又はそのパーツを除去
する。ステップＳ２２におけるクリッピング処理の実行
において、各オブジェクトが交差するビューイング・ス
ペースの平面を識別するステップＳ１４においてオブジ
ェクトが抜粋されたときに、ＣＰＵ４が前回発生された
情報を使用し、これによってステップＳ２２を実行する
コンピュータ処理上の必要条件が少なくなる。

【０２８９】ステップＳ２４において、各オブジェクト
の三角形が、ｚ（深さ）寸法を捨て、捨てたｚ寸法を考
慮してｘ及びｙ寸法を計測することによる従来方法で２
次元に投影し、これによって透視図を得る。

【０２９０】ステップＳ２６において、ＣＰＵ４が、多
角形面が前面（すなわち、ビューワに面している）にあ
ることと、多角形面が裏面であることを識別する。裏面
は前面によって不明瞭になっており、実際には見えない
ので除去される。本実施の形態において、コンピュータ
処理上のオーバーヘッドを減じるために、多角形ノーマ
ルがオブジェクト・スペース内でのみ使用され、ビュー
イング・スペースに伝送されない。従って、ステップＳ
２６において、ＣＰＵ４が多角形エッジを規定するベク
トルを処理し、多角形が前面であるか裏面であるかを決
定する。この処理は公開ヨーロッパ特許出願ＥＰ−Ａ−
０５９０９９５に開示された方法で実行される。

【０２９１】ステップＳ２８において、ＣＰＵ４が三角
形データを走査コンバートし、画素データを生成する。
このステップは従来方法で実行され、またこのステップ
中、色値が従来のグロー・シェィデイング技術を使用し
て各三角形の各頂点につき前記計算された値を考慮して
各画素につき計算される。

【０２９２】ステップＳ３２において、ＣＰＵ４が画素
データを多角形対多角形ベースでフレーム・バッファ１
６に書込み、これによって従来方法で完全な２次元画像
のための画像データを構築する。

【０２９３】ステップＳ３２において、ＣＰＵ４が、表
示デバイス１８のフレーム・バッファ１６に書き込まれ
た画像データを表示及び／又はビデオテープ・レコーダ
２０のような記録デバイス上に画像データを記録する。

【０２９４】ステップＳ３４において、ＣＰＵ４が、画
像データが別のフレームのために発生されるべきかどう
か決定する。ステップＳ９からＳ３４が反復され、画像
データの各フレームが発生される。注意しなければなら
ないのは、ステップ６でモデルのためのトポロジー・デ
ータベースが構成され、また、ステップＳ８で、各オブ
ジェクトのモデルのリファイメントのためのパラメータ
が計算され、オブジェクトがアニメ化されなければ（オ
ブジェクトを形成する三角形パッチが変更されない場合
に）、オブジェクト位置が変更されても（これはオブジ
ェクトを形成する三角形に影響しないので）、画像デー
タの各フレームのために反復される必要はない。しか
し、上述した技術はアニメーションには使用され、相補
を従来方法で「インビトウィーン・フレーム」のために
三角形頂点を計算するのに使用されて各「キー・フレー
ム」のための三角形頂点を規定することができる。

【０２９５】多数の変形が上述した実施の形態に可能で
ある。

【０２９６】ステップＳ１８において上述した（及び図
２７Ａ，２７Ｂに関して説明した）実施の形態を実行す
る処理による照明計算の実行は、ステップＳ６、Ｓ８及
び１６における処理とは独立して実行でき、モデルをリ
ファインする。例えば、照明パッチは、上述の実施の形
態で説明した一つに適用される異なるリファインメント
方法によって発生された多角形頂点における明度値を計
算するのに使用できる。さらに、照明パッチはどのリフ
ァインメントも実行していない元のモデル内の多角形に
対する明度値を計算するのに使用することもできる。こ
の場合、照明パッチは元の多角形内の複数のポイントに
おける明度値を発生するのに使用でき、また補間はこれ
らの値の間で実行され、従来方法による頂点のみにおけ
る明度値間の補間と比較して精度が改善される。

【０２９７】上述の実施の形態において、３次バーンス
タイン−ベジエ三角形パッチがモデルの各三角形をリフ
ァインするのに使用され、３次バーンスタイン−ベジエ
三角形パッチはモデルの各三角形の照明パッチを決定す
るのに使用される。しかし、より高いオーダーのバーン
スタイン−ベジエ三角形パッチは、三角形をリファイン
すること及び／又は三角形の照明パッチを規定すること
に使用することもできる。しかし、より高いオーダーの
パッチは、三角形をリファインするの使用するときは、
利用度が制限されている。これは、より高いオーダーの
式（図９のステップＳ２３４）によって要求されたエキ
ストラ制御ポイントのそれぞれにおける縦座標を計算す
るのに利用可能な情報が制限されるからである（なぜな
ら、元の三角形の各頂点におけるノーマルのみが既知だ
からである）。

【０２９８】バーンスタイン−ベジエ三角形パッチ以外
のタイプのパッチは、三角形をリファインすること及び
／又は三角形の照明パッチを規定するのに使用すること
もできる。このもう一つのタイプのパッチの一例は、ヘ
ロン・パッチであるが、他のタイプのパッチも使用でき
る。ヘロン・パッチの式において、ｈ（τ）は次の通り
である：

【０２９９】

【数１７】ここで、λは制御ポイントの位置を識別する重心座標の
トリプレット（λ₁, λ₂, λ₃）である；ｂ_λは制御ポ
イントλにおける縦座標の値である。

【０３００】上述の実施の形態において、三角形の頂点
における縦座標は、値０に割り当てられ、これによって
パッチがこれらの頂点を補間する。さらに、ヘロン多項
式は中央縦座標に対してゼロであり、従って、b₁₁₁の値
は決して必要でなない。

【０３０１】上述の実施の形態において、各オブジェク
トのモデルは三角形からなる。三角形のためのニュート
ラル重心座標系が上述した実施の形態で説明のコンピュ
ータ処理を補助する。しかし、各オブジェクトは多角形
の他の形状を使用してモデル化でき、また三角形以外の
パッチが各多角形をリファインすること及び／又は各多
角形のための照明パッチを決定するのに使用することも
できる。特に、各オブジェクトは四角形を使用してモデ
ル化できる。５個ないしそれ以上の辺を有する多角形が
使用される場合、必要とされるコンピュータ処理量が相
当増えるが、リアルタイム操作は可能ではない。

【０３０２】各オブジェクト（上述の実施の形態におけ
る図２ＡのステップＳ１６）のリファインメントは、図
２Ａ、２Ｂに示したレンダリング・パイプライン内の他
の場所で実行することができる。例えば、リファインメ
ントは、多角形がステップＳ１８で照明された後で実行
できる。

【０３０３】上述の実施の形態において、各モデル内の
全ての三角形は、続く処理がなされる前に、ステップＳ
１８でリファインされる。しかし、処理は、ステップＳ
１６からＳ３０が多角形対多角形ベースで実行されるよ
うに実行される。

【０３０４】上述の実施の形態において、ステップＳ６
において、各オブジェクトのモデルのためのトポロジー
的データベースが構築される。しかし、この情報は３Ｄ
モデリング・データで受信される。

【０３０５】上述の実施の形態のトポロジー的データベ
ース内に記憶された情報は、識別されるべき所与のエッ
ジを共用する三角形とすることができる。現在のビュー
イング・パラメータ（ステップＳ１２で決定された）を
検査し、エッジを共用する両三角形の三角形ノーマルを
考慮することにより、エッジがオブジェクトのシルエッ
トの一部であれば、決定することが可能である。より詳
しく説明すると、一つの三角形ノーマルは三角形をビュ
ーワに見える方向に向けさせ、また他のノーマルはビュ
ーワから離れるように向けさせれば、これでエッジがシ
ルエットの一部となる。この情報は、ステップＳ１６中
使用でき、シルエットの一部である三角形のための大き
い細分割に適用する。

【０３０６】上述の実施の形態において、ステップＳ１
８において、各オブジェクトのモデルを形成する三角形
がオブジェクト・スペース内で照明される。しかし、三
角形は実行されるべき照明計算のための３次元ワールド
・スペースに変換される。

【０３０７】上述の実施の形態において、各エッジ制御
ポイント（図９のステップＳ２３４）のための縦座標を
計算するために、制御ポイントから直近の頂点を通過す
るタンジェント面の距離が直近の頂点におけるノーマル
と平行な方向で計算される（図１１のステップＳ２６
２）。しかし、この距離は他の方向でも計算できる。例
えば、一つの方向が三角形の各頂点におけるノーマルの
重りつけ(weighting)に基づく各制御ポイントのために
計算できる（各頂点の重りつけはその制御ポイントから
のその距離によって決定される）。別の方法としては、
方向はエッジの両端の頂点におけるノーマルの平均に基
づいて計算でき、それらの座標が上述の実施の形態中の
直近頂点のノーマルと平行な方向を使用して計算されれ
ば（また、表面がより湾曲されることになるので）、縦
座標値が僅かに大きくなる。さらに、三角形ノーマルと
平行な方向が使用できる（これは近接する三角形間のギ
ャップが、例えば上述の実施の形態のステップＳ４０６
と同様に「ステッチング三角形」を生じることによって
埋めることができたとしてもである）。

【０３０８】上述の実施の形態のステップＳ２３４（図
９）において、ＣＰＵ４が各頂点における縦座標と各エ
ッジ制御ポイントの値を計算する。しかし、上述したよ
うに、「キープ・エッジ」フラグがエッジでセットされ
たときに、縦座標がゼロに計算される。従って、装置は
「キープ・エッジ」フラグがエッジのためにセットされ
るか、また縦座標値が計算を実行するよりもゼロにセッ
トされるかどうかテストするようにアレンジされる。

【０３０９】上述の実施の形態のステップＳ３０６（図
１５Ａ）おいて、三角形のモザイクの深さが、画像デー
タの前回フレーム中の三角形によって占められたエリア
と、三角形の湾曲度（三角形の頂点におけるノーマルの
角度内の差から決定される）の両方に依存して決定され
る。しかし、この深さは前回フレーム内の三角形のエリ
アだけか、又は三角形の曲率のみに依存するかで決定さ
れる。さらに、この深さはどの先行フレーム中の三角形
のエリアからも決定でき、直前のフレームである必要は
ない（使用された先行フレームが離れれば離れるほど、
ますますオブジェクトを移動させるのに時間がかかり、
従って、使用されたエリアが現在のフレームのためのエ
リアを表示させないチャンスがますます多くなる）。そ
の上、他の技術も使用できる。例えば、前回（又は先行
する）フレーム内でビューアからの三角形の深さを使用
できる。さらなる例によれば、境界球面がオブジェクト
・スペース内のオブジェクトのまわりで規定でき、境界
球体は２次元スクリーン・スペースに投射でき、投射球
体のエリアが計算され、また計算されたエリアの半分が
オブジェクトのモデル内で多角形の数で分割され、平均
多角形エリアが提供され、これが細分割の深さを決定す
るのに使用できる。この方法において、現在フレーム
（先行フレームではなくて）のための多角形エリアが細
分割深さを決定するのに使用される。もちろん、個々の
多角形が２次元スクリーン・スペースに投射でき、また
そのエリア及び細分割深さが現フレームのために決定さ
れる。さらに、エリア以外のサイズ・パラメータが細分
割深さを決定するのに使用できる。例えば、スクリーン
・スペース内の多角形の最長エッジの長さが使用でき、
これもユーザに対して表示される多角形のサイズを表わ
し、元の多角形を分割して必要とされる詳細を表示しな
ければならない多角形の数とする。

【０３１０】これまでに説明したように、ステップＳ３
０６において、多角形の細分割の深さは多角形のエリア
（画像データの前回のフレーム又は現在のフレームいず
れでも）及び／又は多角形の曲率とに依存して決定され
る。同じ原理がパラメータ的面パッチ（例えば、ベジエ
・パッチ及びＢ−スプライン・パッチ）を形成するオブ
ジェクトのモデルにも適用できる。

【０３１１】周知のように、パラメータ的面パッチを形
成するモデルをレンダリングしようとするときは、各面
パッチはフラット多角形に分割される（例えば、Addiso
n-Wesley Publishing Company 出版、ISBN 0-201-12110
-7、Foley,van Dam, Feinerand Hughesによる「コンピ
ュータ・グラフィックス・プリンシプルズ・アンド・プ
ラクティス(Computer Graphics Principles and Practi
ce)」第２版、セクション11.3.5参照）。所与のパッチ
のための細分割の深さの決定及び、従って、レンダーリ
ングのために生成しなければならない多角形の数の決定
には、パッチのエリアが使用できる。一例としてベジエ
・パッチを採用し、図３２を参照すると、ピッチは一般
的に１６個の制御ポイント、Ｐ１１、Ｐ１２、Ｐ１３、
Ｐ１４、Ｐ２１、Ｐ２２、Ｐ２３、Ｐ２４、Ｐ３１、Ｐ
３２、Ｐ３３、Ｐ３４、Ｐ４１、Ｐ４２、Ｐ４３及びＰ
４４によって規定される。これら１６個の制御ポイント
は、８個のベジエ・カーブ、Ｐ１１−Ｐ１２−Ｐ１３−
Ｐ１４、Ｐ２１−Ｐ２２−Ｐ２３−Ｐ２４、Ｐ３１−Ｐ
３２−Ｐ３３−Ｐ３４、Ｐ４１−Ｐ４２−Ｐ４３−Ｐ４
４、Ｐ１１−Ｐ２１−Ｐ３１−Ｐ４１、Ｐ１２−Ｐ２２
−Ｐ３２−Ｐ４２、Ｐ１３−Ｐ２３−Ｐ３３−Ｐ４３、
及びＰ１４−Ｐ２４−Ｐ３４−Ｐ４４を規定する。従っ
て、各制御ポイントは、二つのベジエ・カーブのための
制御ポイントになる。より詳しく説明すると、ポイント
Ｐ１１、Ｐ１４、Ｐ４４及びＰ４１は各々二つのカーブ
のエンド制御ポイントであり、ポイントＰ２２、Ｐ２
３、Ｐ３３、及びＰ３２は各々二つのカーブのための曲
率制御ポイントであり、また、ポイントＰ１２、Ｐ１
３、Ｐ２４、Ｐ３４、Ｐ４３、Ｐ４２、Ｐ３１及びＰ２
１は各々一つのカーブのためのエンド制御ポイントと、
一つのカーブのための曲率制御ポイントである。パッチ
のエリアを決定するために（レンダリングのためにパッ
チを分割しなければならない多角形の数を計算するため
に）、パッチ内のベジエ・カーブの二つに対してエンド
制御ポイントとなる四つのポイント（すなわち、図３２
の例においてポイントＰ１１、Ｐ１４、Ｐ４４及びＰ４
１）が連結され、得られた多角形のエリアが計算され
る。別の方法として、制御ポイントの他の組み合わせが
連結されて多角形を形成し、得られたエリアが計算、加
算されて全体のパッチのエリアが得られる。例えば、全
て１６個の制御ポイントが図３２に示すように連結で
き、得られた９個の多角形のエリアが計算され、全て合
計される。さらなる例において、二つのカーブに対する
エンド制御ポイントとなる四つのポイント（Ｐ１１、Ｐ
１４、Ｐ４４、Ｐ４１）と、二つのカーブに対する曲率
制御ポイントとなる四つのポイント（Ｐ２２、Ｐ２３、
Ｐ３３、Ｐ３２）が連結され、得られた５個の多角形の
エリアが計算され、全て合計される。

【０３１２】さらに、エリア以外のサイズ・パラメータ
がパラメータ的面パッチの細分割深さを決定するのに使
用できる。例えば、図３２に示したベジエ・パッチを参
照して、レンダリングのための多角形の数がポイントＰ
１１とＰ４４間の距離及び／又はポイントＰ１４とＰ４
１間の距離に依存して決定できる。

【０３１３】上述した実施の形態のように、レンダング
のためにパラメータ的面パッチに分割される多角形の数
が、エリアだけでなくパッチの曲率に依存して、又は曲
率のみに依存して決定できる。ＥＰ−Ａ−０５９６６６
７が、パッチの曲率に依存してパラメータ的面パッチに
分割される多角形の数を決定するのに使用できる方法を
開示している。

【０３１４】上述した実施の形態のように、モデルを形
成する各面パッチが同じ面パッチに細分割でき、また得
られた多角形を、画像データの将来のフレームのレンダ
リングの深さを同じにするように使用するために記憶さ
れる。

【０３１５】上述の実施の形態において、各三角形が図
１９に関してこれまでに説明したようにしてモザイクす
るために分割される。しかし、各三角形は他の方法でも
分割できる。

【０３１６】上述した実施の形態において、ステップＳ
３６６（図１８）において、三角形が分割されるとき
に、ノーマルが元の三角形の頂点からのノーマルの線形
内挿（補間）法を使用して各新しい頂点が計算される。
このノーマルは続いてステップＳ３６８において使用さ
れ、三角形のリファインされた代表中の頂点として使用
される元の三角形の表面から少し離れたポイントの位置
を決定する。しかし、ノーマルは、線形内挿法以外の技
術を使用してステップＳ３６６において計算できる。例
えば、角度内挿法が各頂点のノーマルに対して実行でき
る。この種の内挿法は、例えばコンピュータ・グラフィ
ックス・プロシーディングス、SIGGRAPH (1995)、J. Av
roによる「球体三角形の層化抽出法」、437-438頁に開
示されている技術に基づいている。

【０３１７】上述の実施の形態のステップＳ３６４（図
１８）において計算されたバーンスタイン−ベジエ・パ
ッチの高さは、定数に応じて決定され高さが増減する。
この定数の効果は、いかにして、リファインされた表面
を元のオブジェクトの形状に近接して合わせるか制御す
る。従って、例えば、オブジェクトを描くアーチスト
は、定数と、オブジェクト面が取らなければならない形
状を表わしているオブジェクトと関連付けることができ
る。例を挙げると、球体からなるオブジェクトは、三角
形によって大まかに近似させれば、立方体として現れ
る。これにアドレスするために、上述の実施の形態にお
いて、1.267927822449の定数が、オブジェクトと関連
し、ステップＳ３６４で計算された高さをリファインす
るのに使用され、モデルが本来意図していた球体により
近似するようにリファインされる。

【０３１８】上述の実施の形態において、ステップＳ４
０２からＳ４０８（図２２Ａ，２２Ｂ）において、「ス
テッチング」三角形が発生され、「エッジ・ノーマル不
明瞭」フラグがセットされているが、「キープ・エッ
ジ」フラグがセットされていない各対のエッジ間のギャ
ップを埋める。しかし、これらのステッチング三角形
は、走査変換が実行された後で発生される。さらに、別
の技術がステッチング角度のための必要条件を完全に阻
止するのに使用できる。より詳しく説明すると、「キー
プ・エッジ」フラグではなく、「エッジ・ノーマル不明
瞭」フラグがセットされた二つの三角形間のギャップ
（図２１（ｄ）に示したように）が、次の理由で生じて
くる：（ｉ）エッジに沿った少なくとも一つの内側制御ポイン
トの縦座標の値が、ステップＳ２６２（図１１）で計算
され、直近の頂点のノーマルが少なくとも一つの頂点に
対する二つの三角形につき異なるので、エッジを共用す
る各三角形では異なる；（ii）ステップＳ３６８（図１８）において、エッジ上
の少なくとも一つの内側制御ポイントのための新しい頂
点の位置は、エッジを共用する二つの三角形につき異な
るように計算されるが、これはステップＳ３６８で測定
された距離が、各三角形が少なくとも一つの頂点におい
て異なるノーマルを有しているので、ステップＳ３６６
における二つの三角形につき異なるように計算される。

【０３１９】従って、ステップＳ２６２において、エッ
ジを共用する二つの三角形間のギャップの生じるのを阻
止するために、直近頂点を通過するタンジェント平面の
制御ポイントからの距離が、第１三角形のノーマルと、
直近頂点における第２三角形のノーマルの平均に平行な
方向に測定される。この方法において、エッジのために
計算された縦座標が、各三角形につき同じである。従っ
て、ステップＳ３６４（図１８）において、バーンスタ
イン−ベジエ・パッチの高さは、各三角形につき同じに
なる。加うるに、ノーマルはステップＳ３６６におい
て、エッジの一端の頂点における二つの三角形のノーマ
ルの平均と、エッジの他端の頂点における二つの三角形
のノーマルの平均を内挿法によって計算でき、これによ
って新しい頂点の位置がステップＳ３６８において、エ
ッジを共用する三角形の各々が同じように計算される。
この方法において、ギャップはエッジに沿って現れな
い。このアプローチは、エッジを共用する三角形のリフ
ァインメントが互いに交差し合う面となる場合、上述の
実施の形態で生じた不必要な「ステッチング」三角形が
発生しないという利点がある（従って、ギャップは実際
に発生しない）。

【０３２０】上述の実施の形態において、照明パッチ
が、各三角形のための明度値を計算するのに使用される
か否かが、モデルのモザイクの深さに依存して決定され
る（図２７ＡのステップＳ４６２）。これの代わりに、
又はこれに加えて、照明パッチの使用はモデル内のそれ
ぞれの三角形の表面の曲率に依存して決定できる。

【０３２１】上述の実施の形態のステップＳ４６６にお
いて、照明パッチが明度値の計算に使用されないとき
は、（モデルが深さ３又はこれ以下でモザイクされるの
で）、各元の頂点及び各モザイク頂点における各色要素
の値が計算される。しかし、各モザイク頂点の値を計算
する代わりに、一つ又はそれ以上の元の頂点において計
算された値を内挿して、モザイク頂点における値を発生
させることが可能である。これは、エッジの各端におけ
る頂点の計算された値が内挿された場合に、フラット・
エッジ上の制御ポイントに対応するモザイク頂点に対し
て特にうまく作用する。

【０３２２】アプリケーションが低品質の照明を大目に
見ることができれば、照明パッチは明度値を計算するの
に使用する必要はなく、またその代わりにモザイクによ
って発生された各頂点における色が、元の頂点において
計算された色から線形内挿法によって計算できる。さら
に、これは増大するコンピュータ操作の実行を許容す
る。より詳しく説明すると、縦座標は上述の実施の形態
のようにオブジェクト・スペース三角形データから計算
できるが、むしろ各三角形をリファインするというより
は、上述の実施の形態のようにオブジェクト・スペース
内で新しい頂点を発生させる。この新しい頂点はビュー
イング・スペース（カメラ・スペース）内で発生させる
ことができる。この方法において、新しい頂点はオブジ
ェクト・スペースからビューイング・スペースに変換す
る必要はなく、性能上の増大をもたらす。

【０３２３】上述の実施の形態の説明では述べていない
が、テクスチャ・マッピングが実行できる。例えば、三
角形の頂点において規定されたテクスチャ座標が、重心
座標を使用して内挿でき、これと同時にモザイク形成
中、新しい頂点の生成されモザイク頂点におけるテクス
チャ座標が規定される。

【０３２４】上述の実施の形態において、新しい頂点の
位置が計算されるときに、ステップＳ３６４において、
バーンスタイン−ベジエ・パッチの高さが、高さの計算
された元の三角形上の各頂点に対する３次バーンスタイ
ン−ベジエ三角形パッチ式を評価することによって、計
算される。同様にして、照明パッチを使用する明度値が
計算されるときに、ステップＳ５５４において、元の三
角形上方のバーンスタイン−ベジエ照明パッチの高さ
が、高さの計算された元の三角形上の各頂点に対する３
次バーンスタイン−ベジエ照明パッチ式を評価すること
によって、計算される。しかし、ステップＳ３６４とス
テップＳ５５４両者において、バーンスタイン−ベジエ
三角形パッチの高さは、例えば、Addison-Wesley Publi
shing Company 出版、ISBN 0-201-12110-7、Foley,van
Dam, Feiner and Hughesによる「コンピュータ・グラフ
ィックス・プリンシプルズ・アンド・プラクティス」第
２版、５１１−５１３頁に開示された従来の前進差分法
を用いて元の三角形上の連続ポイントにつき計算するこ
とができる。この種の前進差分法で使用するためのパラ
メータを次に説明する。

【０３２５】ステップＳ３６４において使用するパラメ
ータについてまず説明する。

【０３２６】図２５に関して前述したように、三角形の
エッジと平行に移動するとき、三角形頂点の重心座標の
一つが、一定に保たれる。例えば、図２５において、重
心座標（４，０，０）と（０，０，４）を有する頂点に
よって規定されたエッジに沿ったポイント間を移動する
ときと、このエッジと平行な方向にあるポイント間を移
動するとき、第２重心座標が一定になる。すなわち、τ
₂が一定になる。τ₁＋τ₂＋τ₃＝１であるから、τ₂＝
ｃにセットすると、τ₁＝１−ｃ−τ₃が得られる。従っ
て、式（６）は次のようになる：

【０３２７】

【数１８】式（１８）を整理すると、次式を得る：

【０３２８】

【数１９】ここで、b₃₀₀＝b₀₃₀＝b₀₀₃＝０。従って、式（１９）は
次のように簡略化される：

【０３２９】

【数２０】式（２０）はフォームｆ（τ₃）＝Ａτ₃ ³＋Ｂτ₃ ²＋Ｃ
τ₃＋Ｄの３次多項式である。再度ｃをτ₂で置換する
と、ｆ（τ₃）の係数は次のようになる：

【０３３０】

【数２１】式（２０）がτ₃の３次多項式であるので、定数τ₂と定
数τ₃のために、次の開始値を用いて階段（ステップ）
δ₃に前進差分できる：

【０３３１】

【数２２】さらに、Ｂ、Ｃ及びＤも定数τ₂のために、次の開始値
を用いて階段（ステップ）δ₂に前進差分できる：

【０３３２】

【数２３】これがステップＳ３６４において前進差分を実行するた
めのパラメータの終了になる。

【０３３３】ステップＳ５５４において前進差分を実行
するのに使用するためのパラメータについて次に説明す
る。

【０３３４】照明（イルミネーション）パッチ・アルゴ
リズムに対して、b₃₀₀, b₀₃₀及びb₀ ₀₃は一般的に０では
ない。従って、照明パッチに対して前進差分を適用する
ために、式（１９）が使用される。式（１９）はフォー
ムｆ（τ₃）＝Ａτ₃ ³＋Ｂτ₃ ²＋Ｃτ₃＋Ｄの３次多項式
である。再度ｃをτ₂で置換すると、ｆ（τ₃）の係数は
次のようになる：

【０３３５】

【数２４】式（２４）がτ₃の３次多項式であるので、定数τ₂及び
τ₃のために、式（２２）を用いて階段（ステップ）δ₃
に前進差分できる。

【０３３６】同様に、Ｂ、Ｃ及びＤも定数τ₂のため
に、次の開始値を用いて階段（ステップ）δ₂に前進差
分できる：

【０３３７】

【数２５】上述の実施の形態において、処理がプログラム指令によ
って規定された処理ルーチンを使用してコンピュータに
よって実行される。しかし、処理の一部又は全部はハー
ドウエアを用いて実行される。

【０３３８】

【発明の効果】以上説明したように本発明によれば、多
角形からなる面の第１モデルが、複数の面パッチを介し
て、多角形からなる面の第２モデルに変換される３次元
オブジェクト面の画像をレンダリングするのに使用する
処理装置又は方法を提供することができる。

【０３３９】また本発明によれば、そのパラメータ状面
パッチが曲面のモデルを形成する多角形の少なくともい
くつかのために規定され、その面に近似する多数のより
小さい多角形が面パッチを用いて生成される処理方法又
は装置を提供することができる。

【０３４０】又本発明によれば、３次元の曲面をより優
れたモデルにできるという効果がある。

【０３４１】更に本発明によれば、３次元面のモデルを
レンダリングするのに使用するための明度値を規定する
面パッチを計算する装置又は方法を提供することができ
る。

【図面の簡単な説明】

【図１】本実施の形態の機能要素を示すブロック図であ
る。

【図２Ａ】本実施の形態において実行される全体の処理
動作を示すフローチャートである。

【図２Ｂ】本実施の形態において実行される全体の処理
動作を示すフローチャートである。

【図３】図２ＡのステップＳ４において実行される処理
動作を示すフローチャートである。

【図４Ａ】図２ＡのステップＳ６において実行される処
理動作を示すフローチャートである。

【図４Ｂ】図２のステップＳ６において実行される処理
動作を示すフローチャートである。

【図５Ａ】図４ＢのステップＳ１１０において実行され
る処理動作を示すフローチャートである。

【図５Ｂ】図４ＢのステップＳ１１０において実行され
る処理動作を示すフローチャートである。

【図６】図５において実行される、動作を示すエッジを
共用する三角形の例を示す図である。

【図７Ａ】図４ＢのステップＳ１１２において実行され
る処理動作を示すフローチャートである。

【図７Ｂ】図４ＢのステップＳ１１２において実行され
る処理動作を示すフローチャートである。

【図８】ステップＳ１１０とＳ１１２が実行された後、
フラグ・セットに依存して修正された三角形の例を示す
図である。

【図９】図２ＡのステップＳ８において実行される処理
動作を示すフローチャートである。

【図１０】三角形の３次バーンスタイン−ベジエ三角形
パッチを規定するのに使用される三角形の制御ポイント
とその重心座標を示す図である。

【図１１】図９のステップＳ２３４において実行される
処理動作を示すフローチャートである。

【図１２】図１１のステップＳ２６２において計算され
る距離を概略的に示す図である。

【図１３】図１１のステップＳ２６２において実行され
る処理動作を示すフローチャートである。

【図１４】三角形のためのエッジ・フラグ・セットに依
存して三角形のために規定された三角形及びバーンスタ
イン−ベジエ三角形パッチの例を示す図である。

【図１５Ａ】図２ＡのステップＳ１６において実行され
る処理動作を示すフローチャートである。

【図１５Ｂ】図２ＡのステップＳ１６において実行され
る処理動作を示すフローチャートである。

【図１６】図１５ＡのステップＳ３０６において実行さ
れる処理動作を示すフローチャートである。

【図１７】そ図１６のステップＳ３４６とＳ３５０にお
いて使用されるルックアップ・テーブルを示す図であ
る。

【図１８】図１５ＢのステップＳ３１６において実行さ
れる処理動作を示すフローチャートである。

【図１９】モザイクのために深さ２、深さ３及び深さ４
にそれぞれ分割された三角形の例を示す図である。

【図２０】新しい頂点の位置が図１８のステップＳ３６
８においてどのように計算されるかを示す図である。

【図２１】図１５ＢのステップＳ３１６において実行さ
れる動作によってより小さい三角形にリファインされた
三角形の例を示す図である。

【図２２Ａ】図１５ＢのステップＳ３１８において実行
される処理動作を示すフローチャートである。

【図２２Ｂ】図１５ＢのステップＳ３１８において実行
される処理動作を示すフローチャートである。

【図２３】三角形のモザイク例を説明する図である。

【図２４】図２２ＡのステップＳ３９８において実行さ
れる処理動作を示すフローチャートである。

【図２５】深さ４にモザイクされた三角形のための制御
ポイントと、各制御ポイントのための重心座標を示す図
である。

【図２６】図２２ＢのステップＳ４０６において実行さ
れる処理動作を説明する図である。

【図２７Ａ】図２ＡのステップＳ１８において実行され
る処理動作を示すフローチャートである。

【図２７Ｂ】図２ＡのステップＳ１８において実行され
る処理動作を示すフローチャートである。

【図２８】図２７ＢのステップＳ４７４において実行さ
れる処理動作を示すフローチャートである。

【図２９】図２８のステップＳ５０６において実行され
る処理操作の効果例を示す図である。

【図３０】図２８のステップＳ５１０において実行され
る処理動作を示すフローチャートである。

【図３１】図２７ＢのステップＳ４７６において実行さ
れる処理動作を示すフローチャートである。

【図３２】ベジエ・パッチを規定する制御ポイントを示
す図である。

───────────────────────────────────────────────────── フロントページの続き (31)優先権主張番号９９０２５１４．０ (32)優先日平成11年２月４日(1999．2．4) (33)優先権主張国イギリス（ＧＢ） (72)発明者ホルガーハインリッヒグリューンイギリス国ジーユー２５ワイジェイサリー，ギルドフォード，サリーリサーチパーク，オッカムロード，オッカムコート１キヤノンリサーチセンターヨーロッパリミテッド内

Claims

【特許請求の範囲】

【請求項１】３次元曲面の少なくとも一部に近似する
第１多角形を規定するデータを処理し、面の画像をレン
ダリングするのに使用するための第２多角形を生成する
方法であって、各第１多角形について、それぞれの面パッチを規定し、第１多角形によって表わ
されたオブジェクト面の一部に近似させる工程と；第１
多角形を複数の概念上の多角形に分割する工程と；各概
念上の多角形に対して、第１多角形の面パッチを使用し
てレンダリングするための前記第２多角形を規定し、第
２多角形の頂点の位置を３次元内に決定する工程と；を
有することを特徴とする方法。
【請求項２】３次元曲面に近似する第１多角形が三角
形であり、バーンスタイン−ベジエ三角形パッチが各第
１多角形のための面パッチとして規定されることを特徴
とする請求項１に記載の方法。
【請求項３】３次バーンスタイン−ベジエ三角形パッ
チが、各第１多角形のために規定されることを特徴とす
る請求項２に記載の方法。
【請求項４】第１多角形のための面パッチを規定する
工程が、前記第１多角形の制御ポイントにおける制御値
を計算して面パッチを規定する工程を含むことを特徴と
する請求項１乃至３のいずれか１項に記載の方法。
【請求項５】前記第１多角形の各頂点の制御値がゼロ
にセットされることを特徴とする請求項４に記載の方
法。
【請求項６】頂点以外のエッジに沿った制御ポイント
の制御値が、所定方向内の直近頂点におけるタンジェン
ト平面の制御ポイントからの距離を決定することによっ
て計算されることを特徴とする請求項４又は５に記載の
方法。
【請求項７】前記所定方向が直近頂点のみにおける法
線の方向に基づくことを特徴とする請求項６に記載の方
法。
【請求項８】前記所定方向が、制御ポイントが位置す
るエッジの両端を規定する各頂点の法線に基づくことを
特徴とする請求項６に記載の方法。
【請求項９】各面パッチがヘロン(Herron)パッチであ
ることを特徴とする請求項１に記載の方法。
【請求項１０】第１多角形を概念的多角形に分割する
工程において、当該分割が画像データの前回フレーム内
の前記第１多角形のサイズと、画像データの現フレーム
内の前記第１多角形のサイズと、前記第１多角形の曲率
と、画像データの前回フレーム内のビューイング位置か
らの前記第１多角形の距離と、画像データの現フレーム
内のビューイング位置からの前記第１多角形の距離の少
なくとも一つに依存して実行されることを特徴とする請
求項１乃至９のいずれか１項に記載の方法。
【請求項１１】各第１多角形が概念的多角形の同数に
分割されることを特徴とする請求項１乃至１０のいずれ
か１項に記載の方法。
【請求項１２】概念的多角形の数が、各第１多角形を
テストし、概念的多角形の数を規定するための数に分割
し、最高の分割数を選択することによって決定すること
を特徴とする請求項１１に記載の方法。
【請求項１３】処理が、発生されるべき画像データの
各フレームのために実行され、概念的多角形の数を規定
する細分割のレベルが決定され、この数に各第１多角形
が分割され；レンダリングのために生成された第２多角
形を規定するデータが、未だ記憶されていないデータの
ための細分割のレベルのためにそれが発生されたときの
将来の使用のために記憶され；画像データのフレーム
が、既に記憶されたデータのための細分割のレベルのた
めに発生されるべきときに使用されることを特徴とする
請求項１１又は１２に記載の方法。
【請求項１４】各前記第２多角形が三角形であること
を特徴とする請求項１乃至１３のいずれか１項に記載の
方法。
【請求項１５】概念的多角形のための第２多角形を規
定する工程において、前記第２多角形の頂点が、前記概
念的多角形の各頂点上方の面パッチの距離に依存して計
算されることを特徴とする請求項１乃至１４のいずれか
１項に記載の方法。
【請求項１６】概念的多角形のための第２多角形を規
定する工程において、前記第２多角形の頂点が、（ｉ）前記概念的多角形の各頂点上方の面パッチの距
離を計算する工程と；（ii）前記概念的多角形の各頂点における法線を計算
する工程と；（iii) 前記概念的多角形の各頂点に対して、工程
（ｉ）で計算された距離と、工程(ii)で計算された法線
の距離とに等しい概念的多角形の頂点からの距離にある
ポイントにおいて前記第２多角形のための頂点の位置を
セットする工程と；によって計算されることを特徴とす
る請求項１５に記載の方法。
【請求項１７】前進差分技術が各概念的多角形の上方
の面パッチの距離を計算するのに使用されることを特徴
とする請求項１６に記載の方法。
【請求項１８】レンダリングのために発生された前記
第２多角形間のギャップを満たす工程をさらに含むこと
を特徴とする請求項１乃至１７のいずれか１項に記載の
方法。
【請求項１９】前記ギャップがレンダリングのために
発生された前記第２多角形の頂点の移動によって満たさ
れることを特徴とする請求項１８に記載の方法。
【請求項２０】前記ギャップが前記第２多角形の頂点
を連結し、レンダリングのためのさらなる多角形を形成
することによって満たされることを特徴とする請求項１
８又は１９に記載の方法。
【請求項２１】満たされるべきギャップが、前記各第
１多角形の各頂点のために、エッジを共用する第１多角
形の各頂点における法線間の関係を規定するデータベー
スを使用して識別されることを特徴とする請求項１８乃
至２０のいずれか１項に記載の方法。
【請求項２２】面パッチを規定する工程がオブジェク
ト・スペース内のデータを処理することによって実行さ
れ、前記第２多角形を規定する工程がビューイング・ス
ペース内で実行されることを特徴とする請求項１乃至２
１のいずれか１項に記載の方法。
【請求項２３】周囲光、分散光及び鏡面光の少なくと
も一つのための多角形照明式を評価することによって前
記各第２多角形のための明度値を計算する工程をさらに
含むことを特徴とする請求項１乃至２２のいずれか１項
に記載の方法。
【請求項２４】多角形照明式を評価し、前記第１多角
形の少なくともいくつかのためのそれぞれ第２面パッチ
を規定し、また明度値が前記第２面パッチを使用して前
記第２多角形について計算されることを特徴とする請求
項２３に記載の方法。
【請求項２５】明度値を計算する工程において、各面
パッチに分割される概念上の多角形の数が決定され、ま
た：（ｉ）前記概念上の多角形の数が所定数より少なけれ
ば、前記明度値は各頂点につき照明式を評価することに
よって前記第２多角形の各頂点につき計算され；（ii）前記概念上の多角形の数が所定数より多けれ
ば、それぞれ第２面パッチは各頂点につき計算され、ま
た前記明度値は前記第２面パッチを使用して前記第２多
角形の各頂点につき計算されることを特徴とする請求項
２３又は２４に記載の方法。
【請求項２６】第１多角形のための第２面パッチを計
算する工程が：（ｉ）前記第１多角形のための複数の制御ポイントに
おける明度値を計算する照明式を評価する工程と；（ii）前記面パッチが、前記制御ポイントにおいて計
算された明度値を内挿するように前記第２面パッチを規
定する値を計算する工程と；を含むことを特徴とする請
求項２４又は２５に記載の方法。
【請求項２７】第２面パッチを使用して第２多角形の
頂点のための明度値を計算する工程において、前記明度
値は、その明度値の計算されるべき頂点に対応する概念
上の多角形の頂点における前記第１多角形の上方の前記
第２面パッチの高さを使用して計算されることを特徴と
する請求項２４乃至２６のいずれか１項に記載の方法。
【請求項２８】前進差分技術が各概念上の多角形の各
頂点上方の第２面パッチの高さを計算するのに使用され
ることを特徴とする請求項２７に記載の方法。
【請求項２９】前記第２多角形を変換する信号を発生
する工程をさらに含むことを特徴とする請求項１乃至２
８のいずれか１項に記載の方法。
【請求項３０】レンダリングされた画像データを生成
する工程をさらに含むことを特徴とする請求項１乃至２
９のいずれか１項に記載の方法。
【請求項３１】レンダリングされた画像データを変換
する信号を発生する工程をさらに含むことを特徴とする
請求項３０に記載の方法。
【請求項３２】信号を記録する工程をさらに含むこと
を特徴とする請求項３１に記載の方法。
【請求項３３】レンダリングされた画像データを使用
して画像を表示する工程をさらに含むことを特徴とする
請求項３０乃至３２のいずれか１項に記載の方法。
【請求項３４】画像データの記録を直接的又は間接的
に行なう工程をさらに含むことを特徴とする請求項３０
乃至３３のいずれか１項に記載の方法。
【請求項３５】オブジェクトの画像をレンダリングす
るのに使用する３次元オブジェクトの面の少なくとも一
つに近似する多角形を生成する方法において：面の初期
多角形モデルが、前記面を近似する面パッチのメッシュ
を生成するように処理され；前記面の更なる多角形モデ
ルが前記面パッチを使用して生成されることを特徴とす
る方法。
【請求項３６】３次元曲面の少なくとも一部に近似す
る第１多角形を規定するデータを処理し、面の画像をレ
ンダリングするのに使用するための第２多角形を生成す
る装置であって、それぞれの面パッチを規定し、前記第１多角形によって
表わされたオブジェクト面の一部に近似させるパッチ規
定手段と；前記第１多角形のそれぞれを複数の概念的多
角形に分割する分割手段と；前記概念的多角形のそれぞ
れに対して、対応する第１多角形の前記面パッチを使用
してレンダリングするための前記第２多角形を規定し、
当該第２多角形の頂点の位置を３次元内に決定する多角
形規定手段と；を有することを特徴とする装置。
【請求項３７】前記３次元曲面に近似する前記第１多
角形が三角形であり、前記パッチ規定手段が、各第１多
角形のための面パッチとしてバーンスタイン−ベジエ三
角形パッチを規定するように作動することを特徴とする
請求項３６に記載の装置。
【請求項３８】前記パッチ規定手段が、各第１多角形
のために３次バーンスタイン−ベジエ三角形パッチを規
定するように作動することを特徴とする請求項３７に記
載の装置。
【請求項３９】前記パッチ規定手段が、制御ポイント
において、前記第１多角形の制御ポイントにおける制御
値を計算して面パッチを規定する手段を含むことを特徴
とする請求項３６乃至３８のいずれか１項に記載の装
置。
【請求項４０】前記パッチ規定手段が、前記第１多角
形の各頂点の前記制御値をゼロにセットするように構成
されていることを特徴とする請求項３９に記載の装置。
【請求項４１】前記パッチ規定手段が、所定方向内の
直近頂点におけるタンジェント平面の制御ポイントから
の距離が決定される頂点以外のエッジに沿った制御ポイ
ントのための制御値を計算するように構成されることを
特徴とする請求項３９又は４０に記載の装置。
【請求項４２】前記所定方向が、直近頂点のみにおけ
る法線の方向に基づくことを特徴とする請求項４１に記
載の装置。
【請求項４３】前記所定方向が、制御ポイントが位置
するエッジの両端を規定する各頂点の法線に基づくこと
を特徴とする請求項４１に記載の装置。
【請求項４４】前記パッチ規定手段が、各第１多角形
のためのヘロン(Herron)パッチを規定するように作動可
能であることを特徴とする請求項３６に記載の装置。
【請求項４５】前記分割手段が、画像データの前回フレーム内の前記第１多角形のサイズ
と、画像データの現フレーム内の前記第１多角形のサイ
ズと、前記第１多角形の曲率と、画像データの前回フレ
ーム内のビューイング位置からの前記第１多角形の距離
と、画像データの現フレーム内のビューイング位置から
の前記第１多角形の距離の少なくとも一つに依存して実
行されるように構成されていることを特徴とする請求項
３６乃至４４のいずれか１項に記載の装置。
【請求項４６】前記各第１多角形が概念的多角形と同
じ数に分割されることを特徴とする請求項３６乃至４５
のいずれか１項に記載の装置。
【請求項４７】前記分割手段が、各第１多角形をテス
トし、概念的多角形の数を規定するための数に分割し、
最高の分割数を選択することによって決定するように構
成されていることを特徴とする請求項４６に記載の装
置。
【請求項４８】処理が、発生されるべき画像データの
各フレームのために実行され、概念的多角形の数を規定
する細分割のレベルが決定され、この数に各第１多角形
が分割され；レンダリングのために生成された前記第２
多角形を規定するデータが、未だ記憶されていないデー
タのための細分割のレベルのためにそれが発生されたと
きの将来の使用に記憶され；前記記憶データが、画像デ
ータのフレームが既に記憶されたデータを細分割のレベ
ルのために発生されるときに使用されるように作動可能
なことを特徴とする請求項４６又は４７に記載の装置。
【請求項４９】各前記第２多角形が三角形である請求
項３６乃至４８のいずれか１項に記載の装置。
【請求項５０】前記多角形規定手段が、前記概念的多
角形の頂点上方の面パッチの距離に依存して前記各第２
多角形のための頂点を計算するように構成されたことを
特徴とする請求項３６乃至４８のいずれか１項に記載の
装置。
【請求項５１】前記多角形規定手段が、（ｉ）前記概念的多角形の各頂点上方の面パッチの距離
を計算する手段と；（ii）前記概念的多角形の各頂点における法線を計算す
る手段と；（iii)前記概念的多角形の各頂点に対して、前記手段
（ｉ）で計算された距離と、前記手段(ii)で計算された
法線の距離とに等しい前記概念的多角形の頂点からの距
離にある点において前記第２多角形のための頂点の位置
をセットする手段と；を有することを特徴とする請求項
５０に記載の装置。
【請求項５２】前記各概念的多角形の各頂点上方の面
パッチの距離を計算するための手段が、前進差分技術を
使用して距離を計算するように構成されていることを特
徴とする請求項５１に記載の装置。
【請求項５３】レンダリングのために発生された前記
第２多角形間のギャップを満たすための手段をさらに含
むことを特徴とする請求項３６乃至５２のいずれか１項
に記載の装置。
【請求項５４】前記ギャップを満たす手段が、レンダ
リングのために発生された前記第２多角形の頂点の移動
によってギャップを満たすように構成されていることを
特徴とする請求項５３に記載の装置。
【請求項５５】前記ギャップを満たす手段が、前記第
２多角形の頂点を連結し、レンダリングのためのさらな
る多角形を形成することによってギャプを満たすように
構成されたことを特徴とする請求項５３又は５４に記載
の装置。
【請求項５６】前記ギャップを満たす手段が、各第１
多角形のために、エッジを共用する前記第１多角形の各
頂点における法線間の関係を規定するデータベースを使
用して識別される手段を含むことを特徴とする請求項５
３乃至５５のいずれか１項に記載の装置。
【請求項５７】前記パッチ規定手段が、オブジェクト
・スペース内のデータを処理することによって面パッチ
を規定するように構成され、前記多角形規定手段がビュ
ーイング・スペース内で処理を実行することによって前
記第２多角形を規定するように構成されていることを特
徴とする請求項３６乃至５６のいずれか１項に記載の装
置。
【請求項５８】周囲光、分散光及び鏡面光の少なくと
も一つのための多角形照明式を評価することによって前
記各第２多角形のための明度値を計算する手段を更に含
むことを特徴とする請求項３６乃至５７のいずれか１項
に記載の装置。
【請求項５９】前記明度値を計算するための手段が、
前記多角形照明式を評価して前記第１多角形の少なくと
もいくつかのためのそれぞれの第２面パッチを規定し、
また前記第２面パッチを使用して前記第２多角形の明度
値を計算するように構成されていることを特徴とする請
求項５８に記載の装置。
【請求項６０】前記明度値を計算する手段が、各面パ
ッチに分割される前記概念的多角形の数を決定するよう
に構成されており、また：（ｉ）前記概念的多角形の数が所定数より少なければ、
前記明度値を各頂点につき照明式を評価することによっ
て前記第２多角形の各頂点につき計算し；（ii）前記概念的多角形の数が所定数より多ければ、そ
れぞれ第２面パッチを各頂点につき計算し、また前記明
度値を前記第２面パッチを使用して前記第２多角形の各
頂点につき計算することを特徴とする請求項５８又は５
９に記載の装置。
【請求項６１】前記明度値を計算する手段は、（ｉ）第１多角形のための複数の制御ポイントにおける
明度値を計算する照明式を評価し；（ii）前記面パッチが前記制御ポイントにおいて計算さ
れた明度値を内挿するように前記第２面パッチを規定す
る値を計算することによって前記第１多角形のための前
記第２面パッチを計算するように構成されていることを
特徴とする請求項５９又は６０に記載の装置。
【請求項６２】前記明度値を計算する手段が、第２面パッチを使用して処理を実行し、明度値の計算さ
れるべき頂点に対応する概念的多角形の頂点における前
記第１多角形の上方の前記第２面パッチの高さを使用し
て前記明度値を計算するように構成されていることを特
徴とする請求項５９乃至６１のいずれか１項に記載の装
置。
【請求項６３】前記明度値を計算する手段が、前進差
分技術を使用して、各概念的多角形の各頂点上方の第２
面パッチの高さを計算するのに使用されるように構成さ
れていることを特徴とする請求項６２に記載の装置。
【請求項６４】レンダリングされた画像データを生成
する手段をさらに含むことを特徴とする請求項３６乃至
６３のいずれか１項に記載の装置。
【請求項６５】レンダリングされた画像データを使用
して画像を表示する手段をさらに含むことを特徴とする
請求項６４に記載の装置。
【請求項６６】オブジェクトの画像をレンダリングす
るのに使用する３次元オブジェクトの面の少なくとも一
つに近似する多角形を生成する装置において：面の初期
多角形モデルを処理し、前記面に近似する面パッチのメ
ッシュを生成する手段と；前記面のさらなる多角形モデ
ルを前記面パッチを使用して生成する手段と；を有する
ことを特徴とする装置。
【請求項６７】プログラムにより制御可能な処理装置
に、請求項１乃至３５のいずれか１項で説明された方法
を実行させるためのコンピュータ使用可能命令を記憶す
ることを特徴とする記憶デバイス。
【請求項６８】プログラムにより制御可能な処理装置
に、請求項１乃至３５のいずれか１項で説明された方法
を実行させることを特徴とする信号搬送コンピュータ使
用可能インストラクション。
【請求項６９】３次元オブジェクトのコンピュータ・
モデル内の多角形のための明度値を計算する方法であっ
て：（ａ）多角形のための複数の制御ポイントの各々におけ
る明度値を計算する工程と；（ｂ）前記制御ポイントにおいて計算された明度値を内
挿処理して面パッチを規定する工程と；（ｃ）前記面パッチを使用して複数のさらなるポイント
の各々のための明度値を計算する工程と；を有すること
を特徴とする方法。
【請求項７０】前記多角形が三角形であり、また、バ
ーンスタイン−ベジエ三角形パッチが多角形の面パッチ
として規定されることを特徴とする請求項６９に記載の
方法。
【請求項７１】３次バーンスタイン−ベジエ三角形パ
ッチが、前記多角形のための前記面パッチとして規定さ
れることを特徴とする請求項７０に記載の方法。
【請求項７２】ヘロン・パッチが、前記多角形のため
の前記面パッチとして規定されることを特徴とする請求
項６９に記載の方法。
【請求項７３】前記制御ポイントにおける明度値を計
算する工程において、明度値が、周囲光、分散光及び鏡
面光の少なくとも一つのために照明式を評価することに
よって計算されることを特徴とする請求項６９乃至７２
のいずれか１項に記載の方法。
【請求項７４】前記制御ポイントは前記多角形の頂点
を含んでいることを特徴とする請求項６９乃至７３のい
ずれか１項に記載の方法。
【請求項７５】前記面パッチを使用して計算される前
記明度値のためのさらなるポイントが、前記オブジェク
トの面と近似するさらなる多角形の頂点であることを特
徴とする請求項６９乃至７４のいずれか１項に記載の方
法。
【請求項７６】前記さらなるポイントの少なくともい
くつかが、前記多角形内にあることを特徴とする請求項
７５に記載の方法。
【請求項７７】前記面パッチを使用してさらなるポイ
ントにおける明度値を計算する工程において、前記明度値がさらなるポイントの上方の面パッチの高さ
に依存して計算されることを特徴とする請求項６９乃至
７６のいずれか１項に記載の方法。
【請求項７８】前記明度値がさらなるポイントの上方
で前記面パッチの高さとして計算されることを特徴とす
る請求項７７に記載の方法。
【請求項７９】前進差分技術が、さらなるポイントの
明度値を計算するのに使用されることを特徴とする請求
項６９乃至７８のいずれか１項に記載の方法。
【請求項８０】前記工程（ａ），（ｂ）及び（ｃ）
が、複数の色成分につき実行され、各色成分に対するそ
れぞれ明度値を計算することを特徴とする請求項６９乃
至７９のいずれか１項に記載の方法。
【請求項８１】前記計算された明度値を搬送する信号
を発生する工程をさらに含むことを特徴とする請求項６
９乃至８０のいずれか１項に記載の方法。
【請求項８２】レンダリングされた画像データを生成
する工程をさらに含むことを特徴とする請求項６９乃至
８１のいずれか１項に記載の方法。
【請求項８３】前記レンダリングされた画像データを
生成する工程において、前記さらなるポイントのために
計算された明度値が内挿処理されて他のポイントのため
の明度値を生成することを特徴とする請求項８２に記載
の方法。
【請求項８４】前記レンダリングされた画像データを
搬送する信号を発生する工程をさらに含むことを特徴と
する請求項８２又は８３に記載の方法。
【請求項８５】前記信号を記録する工程をさらに含む
ことを特徴とする請求項８４に記載の方法。
【請求項８６】前記レンダリングされた画像データを
使用して画像を表示する工程をさらに含むことを特徴と
する請求項８２乃至８５のいずれか１項に記載の方法。
【請求項８７】前記画像データを直接的又は間接的に
記録する工程をさらに含むことを特徴とする請求項８２
乃至８６のいずれか１項に記載の方法。
【請求項８８】３次元曲面のモデル内で多角形のため
の明度値を計算する方法であって、面パッチが多角形のための明度値を規定するように計算
され、また前記面パッチが内挿処理のための複数の明度
値を決定するのに使用されることを特徴とする方法。
【請求項８９】３次元オブジェクトのコンピュータ・
モデル内の多角形のための明度値を計算する装置であっ
て：（ａ）前記多角形のための複数の制御ポイントの各々に
おける明度値を計算する手段と；（ｂ）前記制御ポイントにおいて計算された明度値を内
挿処理して面パッチを規定する手段と；（ｃ）前記面パッチを使用して複数のさらなるポイント
の各々のための明度値を計算する手段と；を有すること
を特徴とする装置。
【請求項９０】前記多角形が三角形であり、また前記
面パッチを規定する手段が、前記多角形の前記面パッチ
として、バーンスタイン−ベジエ三角形パッチを規定す
るように動作可能であることを特徴とする請求項８９に
記載の装置。
【請求項９１】前記面パッチを規定する手段が、前記
多角形のための前記面パッチとして、３次バーンスタイ
ン−ベジエ三角形パッチを規定するように作動可能であ
ることを特徴とする請求項９０に記載の装置。
【請求項９２】前記面パッチを規定する手段が、前記
多角形のための前記面パッチとしてヘロンパッチを規定
するように作動することを特徴とする請求項８９に記載
の装置。
【請求項９３】前記制御ポイントにおける明度値を計
算する手段が、周囲光、分散光及び鏡面光の少なくとも
一つに対して照明式を評価することによって明度値を計
算するように作動可能なことを特徴とする請求項８９乃
至９２のいずれか１項に記載の方法。
【請求項９４】前記制御ポイントが前記多角形の頂点
を含んでいることを特徴とする請求項８９乃至９３のい
ずれか１項に記載の装置。
【請求項９５】前記面パッチを使用して計算される前
記明度値のためのさらなるポイントが、前記オブジェク
トの面と近似するさらなる多角形の頂点であることを特
徴とする請求項８９乃至９４のいずれか１項に記載の装
置。
【請求項９６】前記さらなるポイントの少なくともい
くつかが、前記多角形内にあることを特徴とする請求項
９５に記載の装置。
【請求項９７】前記面パッチを使用してさらなるポイ
ントにおける明度値を計算する手段が、前記さらなるポ
イントの上方の前記面パッチの高さに依存して明度値が
計算されるように動作可能であることを特徴とする請求
項８９乃至９６のいずれか１項に記載の装置。
【請求項９８】前記面パッチを使用してさらなるポイ
ントにおける明度値を計算する手段が、前記さらなるポ
イントの上方で前記面パッチの高さとして明度値を計算
するように動作することを特徴とする請求項９７に記載
の装置。
【請求項９９】前記面パッチを使用してさらなるポイ
ントの明度値を計算する手段が、前進差分技術を使用し
てさらなるポイントの明度値を計算するように動作可能
であることを特徴とする請求項８９乃至９８のいずれか
１項に記載の装置。
【請求項１００】前記手段（ａ），（ｂ）及び（ｃ）
が、複数の色成分のそれぞれについて作動し、各色成分
に対するそれぞれ明度値を計算するように構成されてい
ることを特徴とする請求項８９乃至９９のいずれか１項
に記載の装置。
【請求項１０１】レンダリングされた画像データを生
成する手段をさらに含むことを特徴とする請求項８９乃
至１００のいずれか１項に記載の装置。
【請求項１０２】前記レンダリングされた画像データ
を生成する手段が、前記さらなるポイントのために計算
された明度値を内挿して他のポイントのための明度値を
生成するように構成されていることを特徴とする請求項
１０１に記載の装置。
【請求項１０３】前記レンダリングされた画像データ
を使用して画像を表示する手段をさらに含むことを特徴
とする請求項１０１又は１０２に記載の装置。
【請求項１０４】３次元曲面のモデル内で多角形のた
めの明度値を計算する装置であって、前記多角形のための明度値を規定する面パッチを計算す
る手段と、前記面パッチを使用して内挿処理のための複数の明度値
を決定する手段と、を有することを特徴とする装置。
【請求項１０５】プログラムにより制御可能な処理装
置に、請求項６９乃至８８のいずれか１項で説明された
方法を実行させるためのコンピュータ使用可能命令を記
憶する記憶デバイス。
【請求項１０６】プログラムにより制御可能な処理装
置に、請求項６９乃至８８のいずれか１項で説明された
方法を実行させるための信号搬送コンピュータ使用可能
インストラクション。
【請求項１０７】３次元オブジェクト曲面の一部の表
現を規定するデータを処理し、その表現をレンダリング
するために複数の多角形に分割する方法であって、前記多角形の数が表現のエリアに依存して決定されるこ
とを特徴とする方法。
【請求項１０８】前記多角形の数が、画像データの前
回フレーム内の表現のエリアに依存して決定されること
を特徴とする請求項１０７に記載の方法。
【請求項１０９】前記多角形の数が、レンダリングの
ために発生された多角形のためのフレームより、直前の
フレーム内の表現のエリアに依存して決定されることを
特徴とする請求項１０８に記載の方法。
【請求項１１０】前記表現のエリアが画像データの前
回フレーム内でレンダリングされた多角形の頂点の座標
を使用して決定されることを特徴とする請求項１０８又
は請求項１０９に記載の方法。
【請求項１１１】前記多角形の数が、レンダリングの
ために発生された前記多角形のための画像データのフレ
ーム内の表現のエリアに依存して決定されることを特徴
とする請求項１０７に記載の方法。
【請求項１１２】前記表現のエリアが、この表現を規
定するポイントを２次元画像座標系に変換することによ
って決定されることを特徴とする請求項１１１に記載の
方法。
【請求項１１３】前記表現のエリアが、複数の表現を
制限するボリュームを２次元画像座標系に変換すること
によって決定されることを特徴とする請求項１１１に記
載の方法。
【請求項１１４】前記表現のエリアが、複数の表現の
平均エリアとして決定されることを特徴とする請求項１
０７乃至１１３のいずれか１項に記載の方法。
【請求項１１５】前記決定されたエリアが、ルックア
ップ・テーブルへの入力として使用され、レンダリング
のために前記多角形の数を表示する値を発生することを
特徴とする請求項１０７乃至１１４のいずれか１項に記
載の方法。
【請求項１１６】前記多角形の数が、前記表現のエリ
アと、前記表現の曲率とに依存して決定されることを特
徴とする請求項１０７乃至１１５のいずれか１項に記載
の方法。
【請求項１１７】前記表現が多角形であることを特徴
とする請求項１０７乃至１１６のいずれか１項に記載の
方法。
【請求項１１８】前記表現がパラメータ的面パッチで
あることを特徴とする請求項１０７乃至１１６のいずれ
か１項に記載の方法。
【請求項１１９】前記表現がベジエ・パッチであり、
また前記エリアがその角を規定する制御ポイントを使用
して決定されることを特徴とする請求項１１８に記載の
方法。
【請求項１２０】前記多角形をレンダリングしてレン
ダリングされた画像データを生成する工程をさらに含む
ことを特徴とする請求項１０７乃至１１９のいずれか１
項に記載の方法。
【請求項１２１】前記レンダリングされた画像データ
を搬送する信号を発生する工程をさらに含むことを特徴
とする請求項１２０に記載の方法。
【請求項１２２】前記信号を記憶する工程をさらに含
むことを特徴とする請求項１２１に記載の方法。
【請求項１２３】前記レンダリングされた画像データ
を使用して画像を表示する工程をさらに含むことを特徴
とする請求項１２０乃至１２２のいずれか１項に記載の
方法。
【請求項１２４】前記画像データの記録を直接的又は
間接的に行なう工程をさらに含むことを特徴とする請求
項１２０乃至１２３のいずれか１項に記載の方法。
【請求項１２５】オブジェクト面の表現をレンダリン
グする方法であって、前記表現のサイズに依存して細分割の深さを決定する工
程と；前記決定された深さに依存して複数の多角形を発
生する工程と；を含むことを特徴とする方法。
【請求項１２６】前記サイズが表現のエリアであるこ
とを特徴とする請求項１２５に記載の方法。
【請求項１２７】３次元オブジェクト曲面の一部の表
現を規定するデータを処理し、前記表現をレンダリング
するために複数の多角形に分割する装置であって、前記表現のエリアに依存してレンダリングするための多
角形の数を決定するための数決定手段を含むことを特徴
とする装置。
【請求項１２８】前記数決定手段が、画像データの前
回フレーム内の表現のエリアに依存して決定されるよう
に構成されていることを特徴とする請求項１２７に記載
の装置。
【請求項１２９】前記数決定手段が、レンダリングの
ために発生された前記多角形のためのフレームより、直
前のフレーム内の表現のエリアに依存して決定するよう
に構成されていることを特徴とする請求項１２８に記載
の装置。
【請求項１３０】前記数決定手段が、前記画像データ
の前回フレーム内でレンダリングされた前記多角形の頂
点の座標を使用して前記表現のエリアを決定するように
構成されていることを特徴とする請求項１２８又は請求
項１２９に記載の装置。
【請求項１３１】前記数決定手段が、レンダリングの
ために発生された前記多角形のための画像データのフレ
ーム内の前記表現のエリアに基づいて前記多角形の数を
決定するように構成されていることを特徴とする請求項
１２７に記載の装置。
【請求項１３２】前記数決定手段が、前記表現を規定
するポイントを２次元画像座標系に変換することによっ
て前記表現のエリアを決定するように構成されているこ
とを特徴とする請求項１３１に記載の装置。
【請求項１３３】前記数決定手段が、複数の表現を制
限するボリュームを、２次元画像座標系に変換すること
によって前記表現のエリアを決定するように構成されて
いることを特徴とする請求項１３１に記載の装置。
【請求項１３４】前記数決定手段が、複数の表現の平
均エリアとして前記表現のエリアを決定するように構成
されていることを特徴とする請求項１２７乃至１３３の
いずれか１項に記載の装置。
【請求項１３５】前記数決定手段が、ルックアップ・
テーブルへの入力として使用され、レンダリングのため
の前記多角形の数を表示する値を発生するように構成さ
れていることを特徴とする請求項１２７乃至１３４のい
ずれか１項に記載の装置。
【請求項１３６】前記数決定手段が、前記表現のエリ
アと、前記表現の曲率とに依存して前記多角形の数を決
定するように構成されていることを特徴とする請求項１
２７乃至１３５のいずれか１項に記載の装置。
【請求項１３７】前記表現が多角形であることを特徴
とする請求項１２７乃至１３６のいずれか１項に記載の
装置。
【請求項１３８】前記表現がパラメータ的面パッチで
あることを特徴とする請求項１２７乃至１３６のいずれ
か１項に記載の装置。
【請求項１３９】前記表現がベジエ・パッチであり、
また前記数決定手段がその角を規定する制御ポイントを
使用してエリアを決定するように構成されていることを
特徴とする請求項１３８に記載の装置。
【請求項１４０】前記多角形をレンダリングしてレン
ダリングされた画像データを生成する手段をさらに含む
ことを特徴とする請求項１２７乃至１３９のいずれか１
項に記載の装置。
【請求項１４１】前記レンダリングされた画像データ
を使用して画像を表示する手段をさらに含むことを特徴
とする請求項１４０に記載の装置。
【請求項１４２】オブジェクト面の表現をレンダリン
グする装置であって、表現のサイズに依存して細分割の
深さを決定する手段と、前記決定された深さに依存して
複数の多角形を発生する手段とを含むことを特徴とする
装置。
【請求項１４３】前記サイズが表現のエリアであるこ
とを特徴とする請求項１４２に記載の装置。
【請求項１４４】プログラムにより制御可能な処理装
置に、請求項１０７乃至１２６のいずれか１項で説明さ
れた方法を実行させるためのコンピュータ使用可能命令
を記憶する記憶デバイス。
【請求項１４５】プログラムにより制御可能な処理装
置に、請求項１０７乃至１２６のいずれか１項で説明さ
れた方法を実行させるための信号搬送コンピュータ使用
可能命令。
【請求項１４６】複数の表現を含む３次元曲面オブジ
ェクトのモデルを規定するデータを処理して、レンダリ
ングのための複数の多角形を規定する方法であって、レ
ンダリングされるべき画像データの各フレームに対し
て：変換されるべきモデル内の各表現中に多角形数を規
定する共通深さを決定する工程と；前記共通深さのため
の多角形を規定するデータが既に記憶されているかどう
かを判定する工程と；前記共通深さが既に記憶されてお
れば、次にレンダリングのために前記記憶されたデータ
を選択し；記憶されていなければ、前記共通深さのため
の多角形を規定するデータを発生し、レンダリングのた
めに発生されたデータを選択し、かつ、次の使用のため
に、発生データを記憶する工程と；を有することを特徴
とする方法。
【請求項１４７】前記共通深さを決定する工程におい
て、各表現がテストされその個々の深さを決定し、また
前記多角形の最も大きい数を規定する個々の深さが、全
ての表現のための共通深さとして使用されることを特徴
とする請求項１４６に記載の方法。
【請求項１４８】前記共通深さを決定する工程におい
て、全体としてのモデルへのテストが、前記共通深さを
決定するように実行されることを特徴とする請求項１４
６に記載の方法。
【請求項１４９】前記共通深さが、各表現のエリアに
依存して決定されることを特徴とする請求項１４６乃至
１４８のいずれか１項に記載の方法。
【請求項１５０】前記エリアが表現全ての平均エリア
であることを特徴とする請求項１４９に記載の方法。
【請求項１５１】前記共通深さが各表現の曲率に依存
して決定されることを特徴とする請求項１４６乃至１５
０のいずれか１項に記載の方法。
【請求項１５２】各表現が多角形であることを特徴と
する請求項１４６乃至１５１のいずれか１項に記載の方
法。
【請求項１５３】各表現がパラメータ的面パッチであ
ることを特徴とする請求項１４６乃至１５１のいずれか
１項に記載の方法。
【請求項１５４】前記多角形をレンダリングし、レン
ダリングされた画像データを生成する工程をさらに含む
ことを特徴とする請求項１４６乃至１５３のいずれか１
項に記載の方法。
【請求項１５５】前記レンダリングされた画像データ
を搬送する信号を発生する工程をさらに含むことを特徴
とする請求項１５４に記載の方法。
【請求項１５６】前記信号を記録する工程をさらに含
むことを特徴とする請求項１５５に記載の方法。
【請求項１５７】前記レンダリングされた画像データ
を使用して画像を表示する工程をさらに含むことを特徴
とする請求項１５４乃至１５６のいずれか１項に記載の
方法。
【請求項１５８】前記画像データの記録を直接的又は
間接的に行なう工程をさらに含むことを特徴とする請求
項１５４乃至１５７のいずれか１項に記載の方法。
【請求項１５９】オブジェクトの各部をモデル化する
複数の表現から構成された３次元オブジェクトのモデル
をレンダリングする方法であって、同数の多角形を使用して各表現をレンダリングし、異な
る深さの多角形を規定するデータを記憶し、多角形を計
算する前に使用することを特徴とする方法。
【請求項１６０】複数の表現からなる３次元オブジェ
クトのモデルを規定するデータを処理し、レンダリング
のために複数の多角形を規定するデータを生成する装置
であって、画像データの所与のフレームのために前記モデル内の各
表現に変換された多角形の数を規定する共通の深さを決
定する手段と；前記共通深さのために前記多角形を規定
するデータが既に記憶されているかどうか判定する手段
と；前記共通深さのためのデータが既に記憶されていれ
ば、記憶されたデータをレンダリングのために選択する
手段と；前記共通深さのためのデータが未だ記憶されて
いなければ、前記共通深さのために多角形を規定するデ
ータを生成し、生成されたデータをレンダリングのため
に選択し、次の使用のために前記生成データを記憶する
手段と；を有することを特徴とする装置。
【請求項１６１】前記共通深さを決定する手段は、各
表現をテストし、全ての表現のための共通深さとして多
角形の最大数を規定する個々の深さを使用するように作
動可能であることを特徴とする請求項１６０に記載の装
置。
【請求項１６２】前記共通深さを決定する手段が、全
体として前記モデルに対してテストを実行して共通深さ
を決定することを特徴とする請求項１６０に記載の装
置。
【請求項１６３】前記共通深さを決定する手段が、各
表現のエリアに依存して前記共通深さを決定することを
特徴とする請求項１６０乃至１６２のいずれか１項に記
載の装置。
【請求項１６４】前記エリアが全ての表現の平均エリ
アであることを特徴とする請求項１６３に記載の装置。
【請求項１６５】前記共通深さを決定する手段が、各
表現の曲率に依存して共通深さを決定することを特徴と
する請求項１６０乃至１６４のいずれか１項に記載の装
置。
【請求項１６６】各表現が多角形であることを特徴と
する請求項１６０乃至１６５のいずれか１項に記載の装
置。
【請求項１６７】各表現がパラメータ的面パッチであ
ることを特徴とする請求項１６０乃至１６５のいずれか
１項に記載の装置。
【請求項１６８】前記多角形をレンダリングしてレン
ダリングされた画像データを生成する手段をさらに含む
ことを特徴とする請求項１６０乃至１６７のいずれか１
項に記載の装置。
【請求項１６９】前記レンダリングされた画像データ
を使用して画像を表示する手段をさらに含むことを特徴
とする請求項１６８に記載の装置。
【請求項１７０】オブジェクトの各部を各々モデル化
する複数の表現から構成される３次元オブジェクトのモ
デルをレンダリングする装置であって、同数の多角形が各表現をレンダリングするのに使用され
ように動作可能であり、異なる深さのための多角形を規
定するデータが、多角形を計算する前に記憶され、使用
されることを特徴とする装置。
【請求項１７１】プログラムにより制御可能な処理装
置に、請求項１４６乃至１５９のいずれか１項で説明さ
れた方法を実行させるためのコンピュータ使用可能命令
を記憶する記憶デバイス。
【請求項１７２】プログラムにより制御可能な処理装
置に、請求項１４６乃至１５９のいずれか１項で説明さ
れた方法を実行させるための信号搬送コンピュータ使用
可能命令。