JPH04502368A - イメージ・ジェネレータ - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 本発明はイメージ・ジェネレータの中でも、特にリアルタイムに情報を作り出し 、そこから画像をディスプレイ上に呼び出せる、例えばフライト・シミュレータ のようなコンピュータ・イメージ・ジェネレータに関するものである。フライト ・シミュレータ用イメージ・ジェネレータは、航空機のコックピットをシミュレ ートした部屋のパイロットに伝える画像を作り出すために使用される。初期のシ ステムにおいては、視界は、移動をシミュレートすべき地形の模型上方でサーボ 駆動型カメラを操縦することにより得られるフィルム画像や、ビデオ画像から作 られていた。この方法は広範に使用されていたが、広い視点からみたリアルな情 景を作り出すことは不可能であることがわかってきた。この制限を克服するため に、コンピュータにより画像作成を行うイメージ・ジェネレータが導入された。

商業的成功を納めた最初のシステムは１９７０年代初期に登場した。

この種のシステムは、現在では、フライト・シミュレータ分野でほぼ独占的に使 用されており、通常ＣＩＧ（Ｃｏｍｐｕｔｅｒ　Ｉｍａｇｅ　Ｇｅｎｅｒａｔｉ ｏｎ）システムと呼ばれる。ＣＩＧシステムでは、システムにより作られた画像 のオブザーバ、即ち、シミュレータのパイロットは、仮想上のウィンドウから幾 何学的データや特性属性データなどとして格納された情報により定義される３次 元（３−Ｄ）の世界を覗く。視点から窓を洒して引かれる線は３次元世界の中の ある点と交差する。その点の色と強度は、その線のウィンドウと窓の交点で”着 色”されねばならない。表示されるイメージは、個々が均一の色と強度を持つ画 素（ビクセル）の連続から成る。各ビクセルの色と強度は、格納されたデータに より表現される３次元の世界に対する視点位置の関数である。イメージの飛びを 避けるため何十万個ものビクセルが十分な速度でアップデートされねばならない リアルタイム表示では、イメージの迫真性を維持するため、毎秒何百万もの計算 を行わねばならない。広角表示を生成することができる多くのシミュレータ・シ ステムにおいては、そのイメージは３つの並列するイメージからなり、その各々 のイメージは共通のデータベースを持ちながら、別々の処理チャネルで生成され ている。このように、計算負荷は３つのチャネルに分散される。ここでは単一の チャネル内での処理についてのみ取扱っているので、関連するチャネル間の相関 関係については言及しない。

リアルタイムＣＩＧシステムにおいて直面する諸問題の概説と、その問題解決へ の様々なアプローチが、ブルース　Ｊ、シャクター（Ｂｒｕｃｅ　Ｊ、　５ｃｈ ａｃｈｔｅｒ）！ｉ集、ジョン・ワイリー々アンドψサンズ社（Ｊｏｈｎ　Ｖｉ ｌｅｙ　＆　５ｏｎｓ　Ｉｎｃ、　）の１９８３年の出版にかかる、′コンピュ ータ・イメージ・ジェネレーション（Ｃｏｍｐｕｔｅｒ　Ｉｍａｇｅ　Ｇｅｎｅ ｒａｔｉｏｎ）、　（ＩＳＢＮ　０−４７１−８７２８７−３）の中で述べられ ている。しかし、本願において記述する技術の文脈を与えるために、既知のＣＩ Ｇシステムにおいて採用されている共通のアプローチの詳細を以下に概説する。

一般に、シミュレータは、例えば、特定の飛行場への進入など既知の地形のある 特定の領域上を飛行する航空機の航路をシミュレートするように設計されている 。ある公知のシステムでは、その地形の３次元モデルである主データベースを作 り、地形内の各点は、既定の原点に対する当該手点の相対的位置を定義するワー ルド空間座標を備えている。３次元の全表面は、例えば多角形のように、定義さ れた頂点、定義された色、そして定義された垂線面法線（頂点から多角形の面に 垂直に引かれた線）を有する特徴の連続により定義される。更に、例えば（水、 草木などの）表面性状の様な他の特徴も特定することができ、幾何学的並びに他 の特徴は特徴の属性と称される。

主データベース（以後利用可能データベースと称される）は、例えば２００平方 海里と言った、ある１点の視点がとらえられる範囲よりもはるかに広範囲の地球 表面の領域を含むことができる。一般に、通常の視野範囲は４０海里未満である と考えられている。このため、主データベース内のデータの全てが即時的に利用 可能である必要はないので、視点を中心とする所定の半径（例えば、４０海里） の円内にある地域に関するデータが、アクティブな、すなわちオンラインのデー タベースにダウンロードされる。

利用可能データベースに対する視点位置は、シミュレートされる航空機のフライ ト・コントロール操作に応じて常に変化する。この変化は既存の方法で計算され るが、以下に説明される技術に直接関連しない。どの瞬間にも、シミュレータは ワールド空間座標に於ける視点位置を指示する出力と、視線の方向即ちパイロッ トの視点から視野ウィンドウの中心に引かれたベクトルを指示する出力を行うと 言うに止める。

アクティブなデータベースの内容は、シミュレータパイロットの前面に置かれた スクリーン上に表示されるイメージの各画素（ピクセル）の色とその強度情報を 引き出すのに使われる。各画素は、視点からスクリーンに延び、概念的にはスク リーンを通してアクティブなデータベース内のデータにより定義されるモデルの 表面上に延びている予め定めた唯一の仮想視線上にある。これは、データベース のワールド空間座標系を、視点座標を使用して、スクリーン空間座標系に変換し なければならないことを意味する。これにより、（スクリーン空間座標が明らか である）各画素の色と強度を決定するモデルの表面領域を決定することが可能に なる。この表面領域が一旦決定されると、当該ピクセルに寄与する色、強度、そ の他のあらゆる特徴属性が得られ、ピクセルの均一な色と輝度を決定するための 、適切な計算が行われる。

モデルとなる面が平面である場合、各特徴は　その平面内に１つの面を定義する ため、通常は各特徴が他の特徴によって隠されることはない。しかし、許容しう る現実性を得るためには、ビルディングの様な３次元物体を含めたイメージを表 示できなければならない。

このことは、視点によっては、幾つかの特徴はビルディングによって覆い隠され るであろうし、したがって、ビルディングが投映されるピクセルの色と強度に寄 与してはならないことを意味する。この問題は、例えば第１優先順位を地表面に 、第２優先順位をビルディングに、そして第２優先順位の特徴は同一視線上にあ る第１優先順位の特徴の前面に常にあると考えるといったように、異なった特徴 に異なった優先順位を割り当てることで解決される。

それ故、従来のリアルタイムＣＧシステムでは、正しい相対的隠蔽優先順位が、 利用可能データベース内に含まれる特徴に割り当てられることか必要不可欠とな る。この所定の優先順位の序列は、所定の視点範囲に対してのみ有効であるのは 明らかであろう。例えば、パイロットがある側からビルディングを見るとすると 、ビルディングの反対側の壁は、見る側の壁に隠される。しかし、パイロットの 位置がビルの反対側に移れば、その逆が真となる。そのため、イメージのリアリ ズムを維持するためには、特徴の優先順位はパイロットがデータベースを動き回 るにつれて連続的に変わってい（と考えられる。

従来のＣＩＧシステムによって使用されるデータベースを構築するとき、特徴に はあらかじめ定められた優先順位と、この既定の優先順位の修正に必要な追加情 報が、あらゆる視点位置や方向に対して瞬時的な優先順位序列を作り出すために 割り当てられる。従って、データベースの作成は複雑、かつ時間のかかる作業で ある。特により高いリアリズムをめてデータベースの複雑度が増す場合にはそれ は更に複雑なものとなる。

瞬時的な特徴序列は、オンラインのソータにより計算される。このソータには、 平行処理技術では呼び出せない古典的アルゴリズムが組み込まれているため、デ ータベースの複雑度が増すにつれ、システムのスループットを最終的に制限する 。更に、このアプローチは、動的物体の複雑な相互作用を解決できない。従って 、従来のＣＩＧシステムのスクリーン上では、ビルディングの後ろにあるにもか かわらず、ビルディングを通して見える自動車のような可視的人工物（ｖｉｓｕ ａｌ　ａｒｔｉｆａｃｔｓ）が見られることが多い。

上述した、特徴に対する既定の優先順位を用いる従来のアプローチ固有の不利益 を克服するため、Ｚ−バッファリングとして知られる代替技術の実行が提案され 、それにより複雑なＣ■Ｇシーンを正しく表現することが可能になった。Ｚ−バ ッファリング技術は、既定の優先順位を要しない。この新しいＣＩＧシステムは 、成るピクセルに衝突する個々の特徴について、Ｚ−深度（祝事面に対し垂直方 向に測られる、ある特徴の３−Ｄシーンにおける視点からの距離）を計算するこ とにより、特徴の優先度の問題をピクセルレベルで解決する。個々の特徴の色と 強度は処理の際、そのＺ−深度と共にフレーム・メモリにロードされる。同一の ピクセルに衝突する後続の特徴が処理される時、新しい特徴のＺ〜深深度それぞ れ、フレーム・メモリに元より保存されている特徴の２−深度と比較される。新 しい特徴が元の特徴よりもオブザーバに近い位置にあるために元の特徴を隠す場 合、元の特徴は無視され、新しい特徴に置き換えられる。

この過程は、シーンのすべての特徴が処理されるまで繰り返され、その結果、最 終的に個々のピクセルのフレーム・メモリに納められるのは、人間が見ることが できる、最も近い距離にある特徴に対する色と強度のデータである。従来のアプ ローチに対するＺ−バッファリング技術の主な利点は、特徴の優先順位の並べ替 え作業が不必要になり、そのためにより複雑なシーンを作り出すことが可能にな ったことである。更に、特徴記述のために優先順位の情報を加える必要がなくな ったため、データベースの構築がかなり簡素化された。

その結果、特徴の隠蔽優先順位は、ピクセル（またはサブピクセル）の解像度ま で分解され、複雑で、動的な物体の相互作用が、シミュレート可能になった。

Ｚ−バッファリング技術の使用は明らかに利益をもたらす反面、その実用には多 くの新しい問題を提起する。第１に、特徴はでたらめな深度順に処理されるため 、その大部分がＺ−深度の比較が行われるフレーム・メモリで破棄されるにもか かわらず、テクスチャ、なめらかな陰影づけ、霧などの、あらゆる特徴パラメー タを計算しなければならない。これは膨大な計算負荷をもたらすため、リアルタ イム・システムでのＺ−バッファリングの実行を非常に困難にしている。ある既 知のＺ−バッファリングシステムでは、ソータが、上下順、つまり最も近い距離 の特徴が最初というように、システム内における特徴の順番を定める。

そのため、あるピクセル領域が満たされると、システムは、より遠方にある特徴 がそれ以上処理されないようにし、次のピクセルに移る。全ての特徴は、不幸に も、ピクセル処理の開始前に並び替えられねば成らないため、このソータ自体が 、システムのスルーブツトを制限するボトルネックとなっている。第２に、可視 的な別像のない、満足できるシーン品質を作るには、各特徴のＺ−深度計算を、 サブピクセルレベルで行う必要がある。従って、１００万ピクセルの最終的シー ン解像度を生成するシステムは、ピクセルあたり、８個の標本点（ｓａｍｐｌｉ ｎｇ　ｐｏｉｎｔ）、すなわち、８個のサブピクセルを持つため、８００万標本 点についてＺ−深度を計算し、比較しなければならない。これが莫大な計算負荷 を課す。第３に、従来のＺ−バッファリング・システムの主な不利益の１つは、 シーン内に透明な特徴を表現できないことである。それはＣＩＧシーンにおける 透明性の表現は、不透明の面上に透明の面をかぶせることにより作り出されるた めである。従って、あるピクセルに対し、Ｚ−深度が異なる、透明と不透明の２ つの特徴が、フレームメモリ内の同じ場所を争うこともある。そのため、より近 （にある半透明な特徴のために、より遠くにある不透明な特徴が捨てられる結果 となり、可視の不自然な物体を作り出す。

Ｚ−バッファ技術は良く理解され、非リアルタイムＣＩＧシステムに広（使われ る一方、高性能リアルタイムＣＩＧシステムで必要とされるアルゴリズムや技術 の全てを完全に実行するためには、今日まで利用されなかった。いくつかのリア ルタイムのＺ−バッファＣＩＧシステムが開発されたが、上述の本質的な不利益 は克服されなかったために、イメージの質やリアリズムを欠いている。

多くの出版物で、様々なＺ−バッファ技術と導入法が述べられている。例えば、 様々なＺ−バッファ技術の導入について述べたロバートーＦ、スブラウル（Ｒｏ ｂｅｒｔ　Ｆ、　５ｐｒｏｕｌｌによる論文、′フレーム・バッファ’ディスプ レイ・アーキテクチャ”　（Ｆｒａｍｅ　ｂｕｆｆｅｒ　ｄｉｓｐｌａｙ　ａｒ ｃｈｉｔｅｃｔｕｒｅｓ　：　Ａｎｎ、Ｒｅｖ、Ｃｏｍｐｕｔ、　Ｓｃｉ、　１ ９ｇ６．１：１９−４６　（０２７２−１７１６／８６／１１００−００３１） ）、Ｚ−バッファの導入におけるアンチ・アリアシング（ａｎｔｉ−ａｌｉａｓ ｉｎｇ）を行う際の問題を言及するケロッグ・Ｓ。

ブース（Ｋｅｌｌｏｇｇ　Ｓ、　Ｂｏｏｔｈ）他による論文”Ｚ−バッファ有視 面アルゴリズムを援助するハードウェア”　（ｔｌａｒｄｗａｒｅ　ａｓｓｉｓ ｔａｎｃｅ　ｆｏｒ　Ｚ−ｂｕｆｆｅｒ　ｖｉｓｉｂｌｅ　５ｕｒｆａｃｅ　ａ ｌｇｏｒｉｓｍｓ、　ｒＥＥＥ　ｐｕｂｌｉｃａｔｉｏｎ　０２７２−１７１６ ／８６／１１００−００３１）、深度バッファ数学（ｄｅｐｔｈ　ｂｕｆｆｅｒ 　ｍａｔｈｅｍａｔｉｃｓ）と線方程式（ｌｉｎｅ　ｅｑｕａｔｉｏｎ）を参照 した特徴衝突評価（ｆｅａｔｕｒｅ　ｉｍｐａｃｔａｓｓｅｓｓｍｅｎｔ）を述 たアラン・フォーニア（＾１ａｉｎ　Ｆｏｕｒｎｉｅｒ）他による、”フレーム ・バッファの力に関して”（Ｏｎ　ｔｈｅ　ｐｏｗｅｒ　ｏｆ　ｔｈｅ　ｆｒａ ｍｅｂｕｆｆｅｒ）と題する論文、ピクセルにおける適用範囲を格納するための Ａ−チャネルについて説明した、トーマス・ポーター（Ｔｈｏｍａｓ　Ｐ。

ｒｔｅｒ）他による”デジタル・イメージの計算”と題する論文（Ｃｏｍｐｕｔ ｉｎｇ　Ｄｉｇｉｔａｌ　Ｉｃｒａｇｅｓ、　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉ ｃｓ　ｖｏｌ、　１ｇ、　Ｎｏ、　３　（０−８９７９１−１３８−５／８４１ ００７１０２５３））、イヴアン・Ｅ　サザーランド（Ｉｖａｎ　Ｅ、　５ｕｔ ｈｅｒｌａｎｄ）他による、”１０の隠面アルゴリズムの特徴”と題する論文（ ＾ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎ　ｏｆ　ｔｅｎ　ｈｉｄｄｅｎ　５ｕｒｆ ａｃｅ　ａｌｇｏｒｉｓｍｓ、　Ｃｏｗｐｕｔｉｎｇ　５ｕｒｖｅｙｓ、　ｖｏ ｌ、　６．　Ｎｏ、　１．　ｒｎａｒｃｈ　１９７４．　ｐｐ、　３８７−４４ １）、モしてＰ、Ｊ、　ライリス（Ｐ、　Ｊ、Ｖｉｌｌｉｓ）による“現代陰面 除去技術の検討”と題する論文（＾ｒｅｖｉｅｗ　ｏｆ　ｒｅｃｅｎｔ　ｈｉｄ ｄｅｎ　５ｕｒｆａｃｅ　ｒｅｍｏｖａｌｔｅｃｈｎｉｑｕｅｓ、　Ｄｉｓｐｌ ａｙｓ、　Ｊａｎｕａｒｙ　１９８５　ｐｐ、　ｌｌ−２０）がある。どの論文 も、上記の問題点を、リアルタイムで現実的に解決できる技術を説明するのに、 特別に用意したモデルを使用している。

本発明の目的は、以上に述べた問題を解決、または軽減することである。

ＣＩＧシステムにおいて遭遇する更なる問題は、イメージの歪みの問題である。

イメージ投映装置（Ｉｍａｇｅ　ｐｒｏｊｅｃｔｉｏｎ　ｄｅｖｉｃｅ）、特に フライト・シミュレータで使用されるような大規模な装置では、歪みが生じる。

このため、通常は方形をしているディスプレイの個々のピクセルは、投映時には 歪んで見え、通常は直線であるピクセルの行は投映時には曲線に見える。これら の問題を解決するため、たとえは、米国特許ＵＳ−Ａ４　７１４　４２８に説明 されているような、様々な技術が提案されてきた。この文書は、特徴が優先順位 の降順に並べられたシステムについて記述し、特徴のサブエリア、すなわち、ス クリーン空間スパンへの衝突を、スクリーン空間における特徴辺の位置を定義す る線方程式を用いて、分析している。スパンの角は、歪んだイメージ空間にマツ プ（ｍａｐ）され、その結果、イメージ系の歪みは表示用のイメージ・データ作 成に取り入れられる。不幸にも、範囲が歪む時、各スパンにおける特徴のエツジ は再計算されなければならない。これにより、２つのスパンの境界と交差する各 エツジの連続性が維持されるが、表示される各辺は連続した曲線より、むしろ相 互に傾いた直線状エツジの連続となってしまう。更に、計算面では、各スパンの 境界にある特徴のエツジを再計算する必要性が大いにある。

本発明の更なる目的は、以上に述べた問題を解決、または軽減することである。

従来のＣＩＧシステムにおいて遭遇する更なる問題は、光点（ｌｉｇｈｔ　ｐｏ ｉｎｔ）の正確な模シミュレートである。高い輝度を持つ光点は、事実上、その 後ろに位置するあらゆる面を覆い隠す。しかし、低い輝度を持つ光点は、その後 ろに位置する、面の色などにより影響されて見える。従来のリアルタイムシステ ムでは、光点は、一般に、スクリーン空間の方形の領域を占める不透明の特徴に よってシミュレートされる。光点の輝度を、例えば、光が無い場合をシミュレー トするために０にすると、光点が位置する場所はイメージに開けられた「穴」よ うに見える。

本発明の更なる目的は、以上に述べた低い輝度の光点の問題を解決、または軽減 することである。

光点をシミュレートする場合の更なる問題は、”ビルドアップ（ｂｕｉｌｄ−ｕ ｐ）”と”ポツピング（ｐｏｐｐｉｎｇ）である。ビルドアップは、スクリーン 空間に重なり合う光点の輝度が合計された結果、不自然に高い輝度になるときに 起こる。ポツピングは、ワールド空間において、０点領域として定義された光点 が、ある特徴の背後から突然出現するときに起こる。これらの問題は、光点のモ デルを、ワールド空間の幾何学的点に存在すると定義する、従来のシステムでは 処理することはできない。

本発明の更なる目的は、上述の”ビルドアップ”や”ポツピング”の問題を解決 、または軽減することである。

既存のリアルタイムＣＩＧシステムが遭遇する更なる問題は、負荷バランスを保 つことである。個々の装置が最終イメージを完成させるためには、必要とする特 徴データの一部を処理する、並列したパラレル・プロセッサ（ｐａｒａｌｌｅｌ 　ｐｒｏｃｅｓｓｏｒ）群を使用することが知られている。特徴は、通常、（ス パン、またはセル）のような規則的なサイズと形をもつ小片に分割され、各プロ セッサが特定のセル集合に、例えば、あるプロセッサは偶数行のセルを、次のプ ロセッサは奇数行のセルを処理するというように割り当てられる。不幸にも、３ 次元ワールド空間のシーンにおける詳細な量は、スクリーン空間では均等に配布 されない。特に、透視効果は、特徴の密度を水平方向に増加させる。従って、各 プロセッサをスクリーンの特定エリアに割り当てられる場合、非常に重い負荷を 課されるプロセッサもあれば、軽い負荷で済むプロセッサもあるということが起 こる。

その結果、システムは、最も処理の遅いプロセッサのスピードまで、速度低下を 余儀なくされる。

本発明の更なる目的は、以上に述べたパラレル・プロセッサ間の負荷の不均衡の 問題を解決、または軽減することである。

従来のリアルタイムＣＩＧシステムにおいて遭遇する更なる問題は、能率的なス キャン変換（ｓｃａｎ　ｃｏｎｖｅｒｓｉｏｎ）である。

スキャン変換は、多角形データをフレーム・ストア内にラスター化（ｒａｓｔｅ ｒｉｚｅ）する処理で、グラフィック・ワークステーションやコンピュータ・イ メージ・ジェネレータには必要不可欠なものである。スキャン変換のアルゴリズ ムの概説を、アディソン・ウニスリー（Ａｄｄｉｓｏｎ　Ｗｅｓｌｅｙ）出版、 フォリーとヴアン・ダム（Ｆｏｌｅｙ　＆　Ｖａｎ　Ｄａｍ）著”会話型コンピ ュータグラフィックスの基礎”（Ｆｕｎｄａｍｅｎｔａｌｓｏｆ　Ｉｎｔｅｒａ ｃｔｉｖｅ　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ）に見つけることができる。

既知のスキャン変換技術の更に詳しい実例が、シュアン・ピネダ（Ｊｕａｎ　Ｐ ｉｎｅｄａ）による”多角形ラスタリゼーションのための平行アルゴリズム”と 題する論文（Ａ　ｐａｒａｌｌｅｌ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｐｏｌｙｇ ｏｎ　ｒａｓｔｅｒｉｚａｔｉｏｎ、　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ、 　Ｖｏｌｕｍｅ　２２．　Ｎｏ、　４．　Ａｕｇｕｓｔ　１９８ｇ　（０−８９ ７９１−２７５−６／８８１００８１００１７））に述べられている。ピネダが 説明した既知の技術は、スクリーン空間にある特徴のエツジを定義するエツジ関 数（ｅｄｇｅ　ｆｕｎｃｔｉｏｎ）と、そのエツジ関数に対するピクセルの位置 、すなわちエツジ関数の左、または右として表現される位置、を決定するアルゴ リズムに基づいている。特徴はその大きさを決定するために論理的に測量される 。その測量は、エツジ関数のある側から他方への変化を検知することにより制御 される。しかし、スクリーン空間エリアがかなり大きなものであれば、そのエリ アが特定の特徴によって衝突されるかどうかを効率よく評価することはできない 。

従って、本発明の更なる目的は、以上に述べたスキャン変換の問題を解決、また は軽減するものである。

リアルタイムのイメージ・ジェネレータにおいて遭遇する更なる問題は、アクテ ィブなデータベースから効率よくデータを呼び出し、変換することである。はと んどのリアルタイム・３−Ｄ・グラフィック・システムは、入力データを３（ワ ールド空間）次元から、２（スクリーン空間）次元に変換するパラレル・プロセ ッサを含む。この変換は、少な（とも、平行移動（ｔｒａｎｓｌａｔｉｏｎ）、 回転（ｒｏｔａｔｉｏｎ）、透視計算（ｐｅｒｓｐｅｃｔｉｖｅ　ｃａｌｃｕｌ ａｔｉｏｎ）を含み、その他の計算を含むこともある。この作業を担当するサブ システムは、データ・スルーブツト向上のためにパラレル・プロセッサ単位に分 けられる。不幸にも、現在のシステムはまだ十分に能率的ではない。あるシステ ムでは、各プロセッサは異なった作業を行い、最初のプロセッサは平行移動、２ 番目のプロセッサは回転、３番目のプロセッサが透視計算を行う。これは３つの プロセッサのみが使用されるという点において、非常に融通の利かない配置であ り、例えば、平行移動は回転に比べ相対的に単純な作業であるため、平行移動担 当のプロセッサは非常に負荷が少ない。また他のあるシステムでは、アクティブ なデータベースを、利用可能なプロセッサ間で均等に分割可能である。

このアプローチも、たいていのデータベースが実際には視野フィールドの外部に あり、その結果、いくつかのプロセッサの負荷は、データベースの全部、または いくらかの部分が視野フィールドの外部にあるため、軽減され過ぎる傾向がある ので長所は少ない。

従って、本発明の更なる目的は、以上に述べたデータベースから読み出したデー タの変換に関する問題を解決、または軽減することである。

本発明によれば、イメージが、所定の視点からのモデルの景観を表わすよう意図 され、ラスター走査過程により表示されるスクリーン空間ピクセルの配列によっ て構成され、個々のピクセルは均一の色と輝度からなり、ピクセル全体ではイメ ージ領域を定義することを特徴とする、複数個の不透明、半透明の特徴を含むモ デルを定義するデータから、スクリーン上に表示するイメージを生成するため、 以下の手段からなる装置が提供される。

ａ、上記イメージ領域を、１サブエリアが少なくとも１個のピクセルを包含する サブエリアの配列に分割する手段、ｂ、視点から見える可能性があるモデル内の 各特徴に対して、少なくともその特徴により部分的に包含されるサブエリアを決 定するための手段、 Ｃ０各サブエリアに関する特徴識別子リストを作成するための手段で、上記いず れか１つのサブエリアに関するリストは、少なくとも部分的にそのサブエリアを 包含する特徴を識別する、ｄ、各サブエリア内の少なくとも１個の標本点のスク リーン空間における位置を決定するための手段、 ｅ、各サブエリアについて順に、かつ上記各標本点について、標本点を包含する 上記サブエリアリスト内の特徴を決定するための手段、ｆ、標本点を包含する各 特徴について、視点から特徴までの標本点における距離の関数を決定する手段、 ｇ、サブエリア内の各標本点について、特徴を記述するデータを格納するための 手段で、上記格納データは、少なくとも、標本点を包含し１、最も視点近（にあ る不透明な特徴の距離と、標本点を包含する少なくとも１個のより近くにある半 透明の特徴の距離と半透明度を表す、 ｈ、サブエリア内の各標本点について出力を生成するための手段で、上記標本点 出力は、上記デー多格納手段に格納されているデータにより識別される特徴を組 み合わせた効果に相当する、ｉ、サブエリア内の各ピクセルについて、出力を生 成するための手段で、上記ピクセル出力は、ピクセルに貢献する全ての標本点に 対する上記標本点出力を組み合わせた効果に相当する、ｊ、上記ピクセル出力を 表示するための手段。

各サブエリアは、複数個のピクセルを覆うことがあり、各サブエリア内に、１個 以上の標本点がある場合がある。

それぞれが１個の上記標本点包含特徴決定手段、１個の上記距離決定手段、１ｍ の上記格納手段、そして１個の上記標本点出力生成手段を含むパラレル・サンプ リング・ポイント・プロセッサ（ｐａｒａｌｌｅｌ　ｓａｍｐｌｉｎｇ　ｐｏｉ ｎｔ　ｐｒｏｃｅｓｓｏｒ）配列を与えることが望ましい。

サブエリア内の各標本点につき１個のサンプリング・ポイント・プロセッサを与 えることができる。

それぞれが１個の上記ピクセル生成出力手段台み、サブエリア内の各ピクセルに つき１個のピクセル・プロセッサを与えるパラレル・ピクセル・プロセッサ（ｐ ａｒａｌｌｅｌ　ｐｉｘｅｌ　ｐｒｏｃｅｓｓｏｒ）の配列を与えることが望ま しい。１ピクセルにつき１個以上の標本点が与えられることが望ましく、上記ピ クセル出力生成手段は、各ピクセル内にある各標本点、及びピクセル周囲に拡が る所定の領域内にある各標本点から入力を受けることが望ましい。

本発明は、また、それぞれが対応する表示ピクセル行からなる連続する複数のラ スター走査線としてイメージが表示面上に投映され、所定の視点から、所定の領 域を持つ仮想の視野面を通し、表示面が見えるイメージ・プロジェクション・シ ステム（ｉｍａｇｅ　ｐｒｏｊｅｃｔｉｏｎｓｙｓｔｅｍ）と併用するイメージ ・ジェネレータを与えるものであって、上記イメージ・ジェネレータは、ワール ド空間に関連して特徴を定義する幾何学的属性データと特徴の特性を定義する非 幾何学的属性データによりモデルの特徴を記述するモデル・データベース、モデ ルが視覚されるべきワールド空間における視点位置を定義するための手段、幾何 学的属性データを、ワールド空間から視点空間へ変換するための手段、そして変 換した幾何学的属性データと非幾何学的属性データからディスプレイ表面上に表 示するイメージ・データを計算するための手段からなり、上記イメージ・データ は、視点からみたモデルの外観と一致しており、上記イメージ・データ計算手段 は、以下の手段を有する； ａ、祝事面領域をサブエリアの配列へ分割するための手段で、各サブエリアは、 視点から表示面上へのサブエリア投映像が形と面積において所定の各ピクセル群 が投映される表示面の部分に対応するように配置された４個のコーナ座標により 定義される、ｂ、各サブエリア内の１個以上の標本点の位置を定義するための手 段で、各標本点位置は、各サブエリアの４つのコーナに関連づけて定義されてい る、 Ｃ０変換された幾何学的特徴属性と各標本点の位置から、各特徴に包含される標 本点を決定するための手段、ｄ、各標本点について、その標本点を含む少なくと も１個の特徴に対する非幾何学的属性データを格納するための手段、ｅ、上記の 格納属性データから、イメージ・プロジェクション・システム（ｉｍａｇｅ　ｐ ｒｏｊｅｃｔｉｏｎ　ｓｙｓｔｅｍ）への出力を、ピクセル単位に生成するため の手段。

各サブエリアは、線形のエツジを持ち、各サブエリアの面積は、複数行と複数列 のピクセルを含む方形のピクセル配列の面積に一致しつる。

本発明は、更に、ワールド空間において定義される複数個の特徴からなり、光点 特徴と非光点特徴を含み、ワールド空間において定義された支店から見ることが できるワールド空間モデルの表示スクリーン上でのイメージを生成する装置を提 供するものであって、この装置は以下の手段を有する。

ａ、各光点特徴により占有される、スクリーン空間における有限エリアを計算す るための手段、 ｂ、光点特徴の輝度を計算するための手段、Ｃ０視点から見える各光点の特徴に ついて半透明度を計算するための手段で、計算された半透明度は計算された輝度 の関数である、ｄ、最終的に計算された光点特徴の輝度に対応する表示装置への 出力を生成するための手段。

本発明は、また、それぞれがワールド空間における光点の位置を決定する、ワー ルド空間座標により定義される光点特徴を含み、ワールド空間座標により定義さ れる複数個の特徴からなり、ワールド空間において定義される視点から見えるワ ールド空間モデルの表示スクリーン上でのイメージを生成するための装置を与え る、この装置は以下の手段よりなる。

ａ、各光点のスクリーン空間座標を計算するための手段、ｂ、各光点に対するス クリーン空間領域を、少なくともワールド空間における光点から視点の距離の関 数として計算するための手段、Ｃ３各光点について、輝度を計算するための手段 、ｄ０表表示スクリーン上に分布する複数個の標本点のスクリーン空間位置を定 義するための手段、 ｅ、各光点について、上記光点の計算された領域内に含まれる標本点を決定する ための手段。

ｆ、各光点について、上記計算された光点輝度と上記計算された光点領域内にあ る特定の標本点に相応した表示装置への出力を生成するための手段。

上記輝度は、少なくとも視点から光点までの距離の関数として計算することがで きる。少なくとも１個の光点特徴がランダムスキャン方式でカリガラフィックに 表示されねばならない場合、装置は、更に、各標本点が位置する領域内のカリガ ラフィック光点の減衰度を計算するための手段であって、上記減衰度は、標本点 を包含し、かつ、カリガラフィック光点より視点に近いあらゆる特徴の存在を考 慮して計算されるものと、カリガラフィック光点における表示輝度を計算する手 段であって、この表示輝度は、カリガラフィック光点の領域内に位置する全ての 標本点におけるカリガラフィック光点の減衰度の総和とカリガラフィック光点の 内在輝度の関数である。

本発明は、更に、イメージ・ジェネレータが、スクリーン表示用イメージ・デー タを生成するよう意図されており、イメージ・ジェネレータのサブシステムの計 算負荷を、複数のプロセッサ間に分配するための装置を提供するものであって、 その装置は以下の手段からなる。

ａ、スクリーンをサブエリアに分割するための手段で、各サブエリアは少なくと も１個の表示ピクセルを含み、各プロセッサは１度に１サブエリアに関するデー タを処理するよう改良されている、ｂ、すぐ隣合ったサブエリアに関するデータ が、異なったプロセッサにより処理されるよう、処理タスクをプロセッサに分配 するための手段。

好ましくは、表示されるイメージに寄与する可能性がある連続する各特徴を記述 するデータを読み出すための手段が提供され、各特徴を記述するデータは各プロ セッサによって並列に読み出され、各プロセッサは処理を行うサブエリアのスク リーン空間座標を選択するための手段、その特徴が選択されたサブエリアに寄与 するか否かを決定するために読み込まれる特徴データを分析するための手段、及 び、選択されたサブエリアに寄与する特徴を識別するデータを出力するための手 段からなる。

本発明は、更に、各特徴が複数個のまっすぐなエツジにより定義される境界を有 し、各エツジがスクリーン空間座標において線方程式により定義され、スクリー ンを複数個のサブエリアに分割するための手段と、いずれか１個の特徴によるサ ブエリアの包含範囲を分析するための手段とからなり、特徴により定義されるワ ールド空間モデルのイメージの表示を可能にするための複数個の特徴を記述する データを走査変換するための装置を提供する。上記装置において、上記範囲分析 手段は以下の手段からなる。

ａ、上記１サブエリア内の基準点から上記１特徴各辺までの垂直距離を計算する ための手段、 ｂ、基準点からの制限距離（ｌｉｍｉｔｉｎｇ　ｄｉｓｔａｎｃｅ）を計算する ための手段、ある特徴の辺と基準点との垂直距離が制限距離を超えると、その辺 はサブエリアと交差できない； Ｃ１上記計算された垂直距離を上記制限距離と比較するための手段、ｄ、上記計 算した距離と上記制限距離とを比較した結果の論理的組み合せに基づき、ある特 徴によるサブエリア領域の包含範囲を評価するための手段。

各サブエリアは好ましくは方形であり、サブエリアの各コーナに関する特徴のエ ツジについて制限距離を計算するための手段が提供されることが望ましく、上記 制限距離は、サブエリアの中心から各サブエリアのエツジに平行で、各サブエリ アのコーナを通過する線までの垂直距離である。

本発明は、更に、スクリーン上にイメージが表示されるモデルを記述するデータ を処理するための装置を提供する。モデルが、複数個の特徴からなり、各特徴は 、特徴の位置と方向を定義する幾何学的属性と特徴の特性を定義する非幾何学的 属性との関係において記述され、上記イメージは、ワールド空間における視点か らのモデルの外観を表すよう意図されている。上記装置は以下の手段からなる。

Ｃ９ツリーの基部に相当するルート・ノード（ｒｏｏｔ　ｎｏｄｅ）とツリーの 分枝点に相当するブランチ・ノード（ｂｒａｎｃｈ　ｎｏｄｅ）とツリーの各校 の末端に相当するリーフ・ノード（ｌｅａｆ　ｎｏｄｅ）をもつ階層的ツリー構 造において、モデルのデータを格納するデータベース、ツリーの各ノードは各々 の物体を記述するデータを格納し、リーフ・ノードは各々の物体に寄与する少な くとも１個の特徴を格納し、ルート・ノードとブランチ・ノードは少なくとも１ 個の他の物体に対するポインタ（ｐｏｉｎｔｅｒ）と、ポインタで指示された物 体に関連した指示した物体の相対位置と方向を定義する変換データとを格納する ことにより、ツリー構造において連続する個所が、モデルの連続的なより細部に 関するデータを格納する： ｂ、平行に配列されたオブジェクト・プロセッサ（ｏｂｊｅｃｔ　ｐｒｏｃｅｓ ｓ。

ｒ）を有する変換プロセッサ（ｔｒａｎｓｆｏｒｍａｔｉｏｎ　ｐｒｏｃｅｓｓ ｏｒ）、並びに仁　１ノードから読み出されたデータが１データ・プロセッサに 読み出されるよう、データベースからオブジェクト・プロセッサにデータを読み 出すためのコントローラ。

上記装置において、各データ・プロセッサは、ツリーのあらゆるノードから読み 出されるデータでも受け入れるよう改良され、オブジェクト・プロセッサは、ポ インタ・データが読み出されると、各変換データを共通の座標空間へと変換し、 ポインタと変換済みデータをコントローラに返し、オブジェクト・プロセッサは 、特徴が読み出されると、その幾何学的属性を変換し、変換済み属性を更なる処 理のために出力し、コントローラは、ツリーの基部に相当するノードに格納され たデータを読み出し、オブジェクト・プロセッサからそれに返されたポインタに より識別されるツリーのノードに保存されるデータを読み出すよう改良されてい る。

コントローラは、各オブジェクト・プロセッサが連結されたバス（ｂｕｓ）にオ ブジェクト・データを読み出すよう調整することができ、オブジェクト・プロセ ッサが使用されていないかどうか、処理のためにオブジェクト・データを受け入 れられるかどうかを示すための手段を与え、１個の使用されていないオブジェク ト・プロセッサが、バス上で利用可能になったオブジェクト・データを受け入れ ることを可能にする手段を与え、上記オブジェクト・プロセッサは、同一のオブ ジェクト・データの他のオブジェクト・プロセッサによる受け取り防止のために 、オブジェクト・データが処理のために受け取られたことを示すオブジェクト・ データを受け入れる。

本発明の更なる特長は、この明細書の一部を構成する説明と補足的請求の範囲よ り明らかにされる。本発明を、今、さし絵を参照し、実例を挙げて具体的に説明 する。挿絵中、図面の簡単な説明 図１は、本発明に基づいたＣＩＧシステムの基本構成の略図である。

図２は、図１において概説した同型のシステムでの使用に適したシステム拳マネ ージ＋　（ｓｙｓｔｅｍ　ｍａｎａｇｅｒ）と変換エンジン（ｔｒａｎｓｆｏｒ ｍａｔｉｏｎ　ｅｎｇｉｎｅ）の略図である。

図３は、゛データベースのツリー構造の略図である。

図４は、図３で説明された型のツリー構造において、ある特定の物体の集合の相 関関係を説明する。

図５は、図２の変換エンジンに組み込まれたオブジェクト・プロセッサのブロッ ク図である。

図６は、図５で説明されたオブジェクト・プロセッサの機能を説明する。

図７と図８は、本発明の体系化の中でスクリーン空間の特徴位置を評価するため に使用される線方程式の導出を図示する。

図９は、本発明の体系化の中で、スクリーン空間の様々なサブエリアの間の相互 関係を図示する。

図１０は、図２に関連し、一般的に説明された形のスキャン・コンバータとスト ア配置を説明する。

図１１は、図１０で説明されたストアの機能構造を図示する。

図１２は、ある特徴のための境界ボックス（ｂｏｕｎｄｉｎｇ　ｂｏｘ）に対応 するスクリーン空間のサブエリアの境界の相対配置図である。

図１３は、スキャン・コンバータにおける辺方程式の処理を説明する。

図１４は、図１に関連して概説されたレンダリング・エンジン（ｒｅｎｄｅｒｉ ｎｇ　ｅｎｇｉｎｅ）の基本部品の略図である。

図１５と図１８は、レンダリング・エンジンの構成部分であるプリソータ（ｐｒ ｅｓｏｒｔｅｒ）におけるエツジ方程式の処理を説明する。

図１９は、プリソータにおけるエツジ方程式の処理を説明するフローチャートで ある。

図２０は、隠される特徴を決定するブリソータの機能を図示する。

図２１はブリソータ・プロセッサ（ｐｒｅｓｏｒｔｅｒ　ｐｒｏｃｅｓｓｏｒ） の構造を説明する略図である。

図２２は、プリソータにおける処理の分配を図示する。

図２３は、最終表示の１個のピクセルに対応する標本点の分布を説明する。

図２４は、図１４の特別効果モジュール（ｓｐｅｃｉａｌ　ｅｆｆｅｃｔ　ｍｏ ｄｕｌｅ）の構造を説明する。

図２５は、図１４のカラー・ミキサ（ｃｏｌｏｒ　ｍ１ｘｅｒ）の構造の簡略図 である。

図２６は、上記ブリソータからの出力を受け入れるポストソータ（ｐｏｓｔ　５ ｏｒｔｅｒ）のブロック図である。

図２７は、ポストソータの機能を説明するフローチャートである。

図２８は、標本点上の多角形の衝突がアドレスされる方法を説明する。

図２９は、視点から光点の距離、光点の大きさ、輝度の関係を示す。

図３０は、標本点上の光点の衝突の評価を図示する。

図３１は、多角形状の特徴の上の点の、視点からの距離の計算を示す。

図３２は、図１４に関連して簡単に説明された光点ストアの構造を示す。そして 、 図３３は、表示装置における歪み効果を克服するために使用される技術を説明す る。

図１は、フライト・ンミュレータでの使用のために改良した、本発明を具体化し たものの基本機能構成部品である。このンミュレータには、地球表面のワールド 空間モデルに相対する、シミュレートされる航空機の位置と姿勢に対応する出力 を与えるホストコンピュータ１が組み込まれている。イメージは、シミュレート された航空機内のオブザーバ（ｏｂｓｅｒｖｅｒ）に、モデルとなった地表面の 外観を表すものとして表示される。上記具体例において、イメージはバック・プ ロジェクション・スクリーン上に射映される。オブザーバは、大きな回転楕円状 の鏡に映るバック・プロジェクション・スクリーンの反射を見る。しかし、それ に代わる表示システムを使用しても構わなイ。システム−ｖネージャ（ｓｙｓｔ ｅｍ　ｍａｎａｇｅｒ）　（ＳＭ）　２は航空機の位置と姿勢を記述したホスト ・コンピュータ１の出力を受け、シミュレートされた航空機の位置と姿勢から、 オブザーバの視点より見える可能性があるモデルの位置に対応するモデル記述デ ータをデータベースからダウンロードする。そのイメージは、各ラスター走査の 末端のイメージ・ラスター上に複数個のラスター走査線と複数個のカリガラフィ ック光点として射映される。カリガラフィック光点を表示する機能を持たないシ ステムを使用しても構わない。モデルを記述するデータはモデル生成時にあらか じめ決められているが、例えば、滑走路、ビルディング、原野などのモデルシー ンが、所定の原点と１組のワールド空間座標に関する表現で加えられる。

後に更に詳しく説明するが、特徴は直線的な辺を持つ多角形と（スクリーン空間 においては）楕円または円形の面を含む。ラスター光点は通常のラスター走査過 程の一部では、スクリーン空間に楕円または円とし、て表示され、カリガラフィ ック光点はスクリーン空間においては円で表される。モデル記述データは階層的 な順序を持ち、モデルの各特徴は、その特徴を部分的に含む物体に関連づけて定 義され、その対象はモデル内の他の対象に関連づけられ、順に定義される。

抽出されたモデル記述データは、２つの主要な機能をはだす変換エンジン（ＴＥ ）３へと送られる。それは、モデル特徴データを、データベース、すなわちワー ルド座標系、からオブザーバ、すなわち、視点座標系へ幾何学的に変換し、３次 元の視点座標系を２次元のスクリーン空間座標系へ透視変換することである。こ のような変換を可能にするために用いられる技術はよく知られているのでここで は詳しく説明しない。ＴＥ３は、スクリーン座標のモデル記述データの流れをレ ンダリング（再現）・エンジン（ＲＥ）４に供給する。ＲＥ４は、ＴＥ３より受 け入れたモデル特徴幾何学的属性データ（サイズ、位置など）とモデル特徴非幾 何学的属性データ（色、半透明度など）を使用して多（の機能を実行し、表示イ メージの各ビクセルの最終色を生成する。非幾何学属性情報を表すデータは、Ｒ ＥＪ内のフレーム・ストアにロードされる。上記フレーム・ストアは、最終表示 の各ビクセルに対応するメモリ・アドレスを持つ。

フレーム・ストアの内容は最終イメージを出力する表示装置５にダウンロードさ れる。１フレーム・メモリは、ノン・インターレース表示装置（ｎｏｎ−ｉｎｔ ｅｒｌａｃｅｄ　ｄｉｓｐｌａｙ　ｄｅｖｉｃｅ）に対しては完全な１フレーム 、インターレース表示装置（ｉｎｔｅｒｌａｃｅｄ　ｄｉｓｐｌａｙ　ｄｅｖｉ ｃｅ）に対しては完全な１フイールドを含むことが出来ることは理解を要する。

システムは、パイプライン化された４つのステージを持ち、１イメージフレーム の表示中、ＲＥ４では次の表示フレームが再現され（ｒｅｎｄｅｒ）、Ｔ　Ｅ　 ３ではその次の表示フレームが処理され、８Ｍ２ではその次のフレームが処理さ れている。各段階は、ダブル・バッファ・ストア（ｄｏｕｂｌｅ　ｂｕｆｆｅｒ ｅｄ　５ｔｏｒｅ）により隣接する段階と分離される。

２フレーム・スワップ”信号が、全ダブル・バッファ・ストアの内容を一斉に交 換するために生成される。このように、フレーム・スワップ信号は、バイブライ ンを通じ、１フレームに関するデータを効果的に”クロック”する。

図２は、図１の８Ｍ２とＴＥ３を更に詳細に示している。８Ｍ２は本質的には従 来のもので、このサブシステム内に含まれる様々なモジュールをリンクするＶＭ Ｅデータ・バスからなる。このモジュールには、利用可能データベース７、ホス ト・コンピュータと双方向通信を可能にするホスト・インターフェイス８、コマ ンドとステータス行によりＴ、Ｅ、ＲＥとの双方向通信をもたらし、変換エンジ ンにデータベースの情報の放送を可能にする汎用インターフェイス９、必要な全 てのシステム・マネージャの計算タスクを実行する配列されたＣＰＵｌ０１並び に、オブザーバの瞬時の視点を中心とし、適度な視野であるオブザーバの視点の 周囲３６０°に広がる範囲を包含する利用可能データベースの補助集合を保存す るアクティブ・データベース−メモリ（ａｃｔｉｖｅ　ｄａｔａｂａｓｅ　ｍｅ ｍｏｒｙ）　１１　（Ａ　Ｄ　Ｈ）が含まれる。８Ｍ２は後述されるものを含む 多くの従来的機能を果たす。

ホスト・コミュニケーション イメージ・ジェネレータはイーサネット・リンク（Ｅｔｈｅｒｎｅｔ　１ｉｎｋ ）を通じてホスト・シミュレータ・コンピュータに接続される。これにより、複 数のシミュレータと、または、複数のイメージ・ジェネレータをネットワークで 連結することが可能になる。ホスト・シミュレータとイメージ・ジェネレータ間 の通信は双方向である。ホストは、ホストが制御する全ての移動物体（その１つ は、シミュレートされた航空機、つまり、ホストである乗り物）の位置と方向を 定義するデータと、例えば、離着陸場の照明の状態、天候などを定義するデータ を送る。イメージ・ジェネレータは、上空の高度、衝突などシーンの様々な物体 （動的物体など）のステータスを送り返す。

データベースの選択 常にデータベース・メモリ（アクティブ・データベース、ＡＤＢ）に存在する実 際のデータは、視点がモデルとなった世界を動き回る時、ディスクから新しいデ ータをダウンロードし、必要がなくなったデータを捨てることにより継続的に更 新される。その結果、モデルとなった世界と相対して動き、そのためいかなる視 点においてもアクセス可能でなければならない°ライブラリ（ｌｉｂｒａｒｙ） ”物体と共に、ＡＤＢは、常に視野内にある全てのデータベース物体を含む。

タイミングとロードの制御 システム・マネージャはイメージ・ジェネレータの全体的なタイミングを制御し 、規則的で、最適なフレーム率を維持する役割をもつ。システム・マネージャは 、ＴＥとＲＥの様々な部分がら、この役割を補助するタイミング信号を受信し、 （以下に要約される詳細スイッチ・レベルで）瞬時的なシーン内容を制御し、フ レーム・タイムが最適値を越えるときに適切な処置をとるため（過負荷制御）収 集し、異なった状態（例えば、異なったモデル、異なったＴＥ構成など）でのシ ステムの性能を評価するためにユーザに開放する。

データベースは異なった詳細レベルを含む異なったバージョンの対象を保存する ことができる。すなわち、ＴＥは対象物体が視点からどれぐらい遠（にあるかに よって、その対象物体の正しい詳細描写レベルを決定する。現在表示されている 詳細レベルが間違いであっても、１゛Ｅはその詳細レベルを変更せず、ＳＭに詳 細レベルの変更が必要であることだけを知らせる。その結果、ＳＭは詳細レベル を別のレベルにフェードする。

過負荷調整は、対象物体のモデル化された特徴の全体内容を減らすことにより、 フレーム・タイムの短縮を試みる。その方法は、先ず、遠方にある物体の細部（ 装飾物など）を除去し、望ましいフレーム時間を得るために更なる処置が必要な 場合には、次に、対象物体の描写レベルを低い細部レベルに、作意的に切り替え る。過負荷調整は、処理データの量が膨大で、作業が既定の最大受は入れ可能フ レーム・タイム以内に完了できない場合に限り実行される。細部レベル制御は、 フライト・シミュレータ分野では、よく知られた手法であるので、ここでは詳細 には触れない。

特殊効果 ホスト・シミュレータ・コンピュータから、または、環境を記述するローカル端 末から受け取ったデータは、天候効果、着陸光ローブ（ｌａｎｄｉｎｇ　ｌｉｇ ｈｔ　１ｏｂｅ）などの生成に対する適切な情報をＴＥとＲＥに送るために処理 される。このデータは、雲の高さ、可視度、霧の深さ、着陸光の状態と光線の方 向、時間（周辺光レベル制御）、落下の中心点、並びに、天候レーダとの相関用 成長／減衰率を含む。

物体の相互作用 システム・マネージャはアクティブ・データベース内の対物体間の相互作用を記 述し、ＴＥから送り返されるデータを照合する責務をもつ。このデータはフィル ターにかけられ、必要なときに、ホスト・コンピュータに送り返される。上記デ ータは上空の高度計算、衝突検出、範囲検知などに使用される。

一般的には、イメージ・ジェネレータが駆動するチャネルは３経路あり、各々が 専用のＴＥ、ＲＥと表示装置を有する。しかしながら、単一チャネルのシステム 、または、例えば、３つのサブ・チャネルを１個のイメージ・ジェネレータが駆 動するシステムなど他の構成も可能である。しかし、そのような構成の多様性は 、本発明とは密接なつながりはないので、１チヤネルについてのみ説明する。

今、ＴＥ３を更に詳細に見ると、８Ｍ２がＡＤＢにおいて必要なデータを組み立 てる時、ＴＥ３は、８Ｍ２からチャネル・アクティブ・データベース（ＣＡＤＢ ）１２に前もって読み出したデータを処理する。ＣＡＤＢ１２は、メモリ１３と 制御論理１４からなり、制御論理１４は、メモリからオブジェクト・プロセッサ １５の配列へのデータ読み出しを制御する。その代わりに、オブジェクト・プロ セッサ１５は、制御論理１４に対し制御入力を与える。メモリ１３はアクティブ ・データベース全体を保持し、制御論理１４はチャネル特定のオブジェクト・デ ータを選択し、処理する。オブジェクト・プロセッサ・アレイ１５は、各ボード １７上にグループ単位に配列された個々のオブジェクト・プロセッサ１６よりな る。これらのプロセッサは、ＴＥ３の主要な計算要素を形成する。システムに要 求される能力に見合った数のオブジェクト・プロセッサを供給する方が望ましい 。

オブジェクト・プロセッサ・アレイ１５の共通出力１８は、スキャン・コンバー タ・ストア２１に対し出力を与える論理ユニット２０を組み込んだスキャン・コ ンバータ１９に送られる。属性ストア２２は、スキャン・コンバータ１９を介し て入力を受ける。ストア２２への入力されるデータには、オブジェクト・プロセ ッサでの変換を要しないものがある。テクスチャー・マツプ（ｔｅｘｔｕｒｅ　 ｍａｐｓ）は、そのようなデータの例である。その種のデータは、オブジェクト ・プロセッサとスキャン・コンバータを通過するだけである。

図３は、簡単なデータベースの”ツリー”構造を示す。ツリー構造とは、特定の フレームに関連するデータの検索を可能にするために、モデルの特徴データを保 存する方法を表す。ワールド空間モデルは１つの連続する”物体”から構成され ると考えられる。特徴はツリー構造により結合され、各物体はツリーのそれぞれ のノードに存在する。ツリー構造は、ルート・ノード（図３の０１）ブランチ・ ノード（図３の物体０２から０６）とリーフ・ノード（図３の物体０７から０９ ）からなる。ルート・ノードと各ブランチ・ノードは連結するノードへのポイン タを１個以上含む。図３で示す簡単な例では、物体０２は物体０４と０５へのポ インタを所持し、物体０４は物体０６から０８を指すポインタを所持する。多角 形や光点の様な個々の特徴は、ツリー構造全体に配布される。例えば、各リーフ ・ノードは１個以上の特徴を含み、基部と枝分かれするノードは、それぞれ１個 以上の特徴を含む。このように、ツリー内にある連続する物体は、連続する、更 に詳細なワールド空間モデルの細部に関するデータを所持する。例えば、図３に おいて、物体０１はある特定の地図上の地域を、物体０２と０３はそれぞれその 地域の一部、物体０４は例えば物体０２の地域内の飛行場を表すデータ等を表す こともできる。

各物体は、１個のオブジェクト・プロセッサが１サイクル内に処理可能な量のデ ータを保存できる。ある導入では、各物体に最高４０個の特徴（多角形、光点、 等）を保存できる。ルート・ノードとブランチ・ノードもまた、他の物体へのポ インタを保持する。特徴とポインタの組み合せ数は、どの１個のオブジェクト・ プロセッサも過負荷の状態にさせない程度に制限される。各物体内の特徴とポイ ンタは、′オブジェクト空間″に関連づけて定義される。オブジェクト空間は平 行移動や回転によりワールド空間座標系から変換された座標系である。従って、 各ポインタは、指示された物体を識別するのみならず、指示された物体のオブジ ェクト空間から指示する物体のオブジェクト空間に変換するために必要な適切な 平行移動と回転を与えるデータも含む。ルート・ノードの物体はワールド空間に 直接関連づけられ、他の物体は、物体のツリーを通し、移動と回転によりルート ・ノードに結び付けられ、間接的にワールド空間へ関連づけられる。このように 、各物体内では、特徴とポインタはその物体のオブジェクト空間空間に関連づけ て定義されるが、各物体は共通の座標系であるワールド空間に関連づけて定義さ れると考えられる。

図４は、飛行場を表す物体のツリーの例である。このような物体ツリーはモデル 全体のごく一部を構成するだけなので、簡単な図４のモデルは単に説明のための ものに過ぎない。

図４では、１０個の物体が以下のように表されている。

１、地表多角形（ｇｒｏｕｎｄ　ｐｏｌｙｇｏｎ）、地表多角形上に位置する光 点と他の物体へのポインタ等の特徴を保持する′飛行場”物体２、飛行場と相対 的に移動する可能性がある自動車を定義する特徴を保持する”自動車”物体 ３、滑走路面、滑走路置場のマーキング、光点を定義する多角形の特徴を保持す る”滑走路”物体 ４、滑走路の誘導路を定義する多角形と光点の特徴を保持する”誘導路′物体 ５、特徴は保存しないが、他のポインタへのポインタを保持する”ターミナル・ エリア”物体 ６．２個の１ビルディング物体（ビルディング１とビルディング２）。ビルディ ング１は多角形の特徴と他の物体へのポインタを保持する。ビルディング２は、 ターミナル・エリア物体からビルディング２へ向けた２個のポインタにより定義 される位置に現れるビルディングと同一の１個のビルディングを記述する特徴を 保持する７、ビルディング１物体を構成する各特徴群を保持する３個の物体（Ａ 、Ｂ％Ｃ）。

図４の”ツリー”は、図２で説明したＴＥにより検討される。制御論理１４は、 最初の関連物体（飛行場）を読み出し、その情報は最初のオブジェクト・プロセ ッサに受け取られる。そのオブジェクト・プロセッサは、その後、制御論理１４ に対し、ツリーにある次レベルの物体（自動車、滑走路、等）を使用されていな いオブジェクト・プロセッサ内に読み込むよう指示する。このサイクルは、全て の関連するデータがプロセッサに読み込まれるまで、ツリー中に拡がりながら繰 り返される。従って、処理はツリーの各校に沿って同時に進行し、その結果、処 理時間は最低限に抑えられる。

図５はオブジェクト・プロセッサを更に詳細に説明し、図６は、図４で説明した 簡単な例における処理タスクの分配を示す。図５では、グループ１７中のｎ個の オブジェクト・プロセッサ１６は、ＯＰｉ、ＯＦ２．、、ＯＰｎとして識別され る。このプロセッサは、次にＣＡＤＢ１２やスキャン・コンバータ１９へと接続 される３ｍのＦＩＦＯ回路に並列に接続される（図２）。ローカル・コントロー ラ２６はこのｎ個のプロセッサの処理を制御し、制御論理１４はＣＡＤＢからこ のプロセッサへのデータの配布を制御する。このデータは、ＦＩＦＯ２３を通し て、オブジェクト・コントローラに送られる。ＦＩＦＯ２４は入力を制御論理１ ４に返し、ＦＩＦＯ２５は処理済みの特徴データをスキャン・コンバータ１９へ 渡す。

プロセッサ群１７は平行バスを通じＣＡＤＢ１２に接続される。

データはメモリ１３からパス上に読み出される。プロセッサ群７に使用されてい ないプロセッサが少なくとも１個ある場合、そのグループは処理のために物体に 関するデータを受け取ることができる。

１度に１つのプロセッサ群がアドレスされ、各プロセッサ群はそれぞれの時間ス ロット（ｔｉｍｅ　５ｌｏｔ）の間でアドレスされる。もし、あるプロセッサ群 のアドレス時、そのプロセッサ群のＦＩＦＯ２３が空であり、プロセッサ群の１ 個のプロセッサが使用されていなければ、物体データはバスを通じＦＩＦＯ２３ に読み出される。あるバス上の信号は、物体データが処理のために受け取られた ことを意味する。この信号は、他のプロセッサが同一の物体データに割り当てら れることを防止し、別の物体データ・パケットをバスに読み出すことを可能にす る。

各グループ１７内では、物体データは、物体データの分配と同様の手法で、ＣＡ ＤＢからプロセッサ群へ分配される。すなわち、各オブジェクト・プロセッサは １個づつアドレスされ、アドレス時にオブジェクト・プロセッサが使用されてい ない場合には、そのプロセッサはその時点で入手可能の物体データ・パケットを 受け取る。

このように、物体データは効率的な方法で分配される。全体が使用されていない オブジェクト・プロセッサ群に、物体データ受は入れが最優先される場合には、 その効率は更に高くなる。

各オブジェクト・プロセッサは、１個のマイクロプロセッサ、１２８にバイトＲ ＡＭと１個のＤＭＡコントローラからなる。ＲＡＭは、物体データと、関連デー タを識別するために実行し、ツリーを検索（ｗａｌｋ）するツリー”検素”プロ グラム、及び、特徴変換プログラムを保持するよう構成される。プロセッサは、 先ずツリー検索モード、次に変換モードで動作する。

ツリー検索モードでは、各オブジェクト・プロセッサは作業対象の物体のポイン タ・データを見る。そのデータは、各ポインタに対する、指示されるの物体の” 大きさ”　（すなわち、物体の中心を中心とし、物体全体を包含する領域の半径 ）、指示された物体の”位置”　（すなわち、指示された物体を、その物体自身 のオブジェクト空間から、指示した物体の空間に変換するのに必要な平行移動と 回転）を含む。オブジェクト・プロセッサは、ポインタ・データと現在の視点位 置、視野の方向を参照することにより、範囲内、かつ、視野内にある指示された 物体を決定する。視野外にある物体はそれ以上処理されない。視野内の物体を指 示するポインタはＣＡＤＢ１２に返され、指示された物体は、その後、制御論理 １４によって、使用されていないプロセッサに読み出される。使用されていない 各プロセッサはそれぞれの物体を受け取る。

変換モードでは、各オブジェクト・プロセッサは、作業対象の物体に保持された （ポインタではな（）特徴に対して処理を行う。プロセッサは、各特徴について 必要な幾何学的変換を行い、その結果、ＦＩＦＯ２５への出力が、スクリーンに 基づく座標により、後続処理に適する連続する特徴（多角形、光点など）データ となる。このように、オブジェクト・プロセッサはアクティブ・データベースの 内容を、各モデルが自身の座標フレームにあるツリー構造のモデル集合から、各 モデル内の全ての基本要素（ｐｒｉｍｉｔｉｖｅｓ）がスクリーン空間に変換さ れる方式で変換する。使用されるアルゴリズムは従来のものであるので、ここで は詳細には説明しないが、スキャン・コンバータの機能に特に関係する特徴属性 の計算については以下に説明する。

図６は、図４で示した簡単な例に適当な”ツリー検索”シーケンスを説明してい る。フレームの開始において、飛行場の全てが範囲内かつ視野内にある視点位置 を仮定し、ルート・ノード（飛行場）の特徴とポインタ・データは、プロセッサ ＯＰＩに出力される。０Ｐｌはその物体からポインタを選択し、必要な変換を行 い、その選択したポインタを制御論理１４に返す。その４個の指示された物体は 、その後、ＯＦ２からＯＦ２のプロセッサに出力される。ＯＰＩは、次に、飛行 場物体の特徴をスクリーン空間に変換し、変換された特徴属性をスキャン・コン バータ１９に出力する。その後、ＯＰｌは別の処理タスクのために使用できる。

ＯＦ２からＯＦ２の各プロセッサは、ポインタをもたない物体を受け取るため、 物体の特徴に必要な変換を施し、変換された特徴属性をスキャン・コンバータ１ ９へ出力する。ＯＦ２に送られた物体は特徴は保持していないが、他の２つの物 体への３つのポインタを保持している。これらのポインタは、処理後、制御論理 １４に返される。その２つの物体は、飛行場全体が視野内にあるならば、視野内 にあるはずなので、対応する物体データがＯＦ２、ＯＦ２、Ｏ２０のプロセッサ に読み出される。処理は、この方法で、ＯＦ２から０Ｐ１１のプロセッサを使い 、全ての物体が処理されるまで続けられる。注意を要するのは、”ビルディング ２“物体が２度処理されることである。これは”ピルディング２′物体が２度指 示されるからであり、それはこの物体がワールド空間の２つの異なった位置に現 れることを意味する。

このように、プロセッサは、非常に効率的な方法で分配されるデータを平行処理 する。プロセッサは、特徴データが１個のプロセッサに渡されると同時に、変換 タスクを開始する。ルート・ノードがポインタ・データと共に特徴データを保持 する場合、この処理はほとんど瞬間的に行われる。以前のアート・オブジェクト ・プロセッサは、一般に４ミリ秒を要して特徴データを並び替えた後、変換作業 を開始できた。典型的なフレーム周期が１６ミリ秒であることを考えると、フレ ーム周期の１／４をデッド・タイムに要した以前のアート・オブジェクト・プロ セッサと比較し、本発明の場合は、フレーム周期中にデッド・タイムはほとんど 無いことを意味する。

図６は、全ての処理タスクには同じ時間がかかり、タスクはＯＰｌ、ＯＦ２．Ｏ Ｆ２の順にプロセッサに分配されることを意味する。

実際には、常にそうである必要はな（、もしそうでなければ、他のプロセッサ群 が使用されていないにも拘わらず、最初のプロセッサ群の通信バスの仲裁機能が 処理スピードを低下させてしまう。この事実から、タスクの分配は、上述のよう に、ツリーから読み出された最初の物体がグループ３の０Ｐ１４に進み、次の対 象はグループ７のＯＦ２に進むというように管理される。このように、データの 処理は、無秩序に、グループ間に均等に分配される。

上述したように、実際のシステムでは、物体のツリーは図４に示したよりもずっ と複雑ではあるが、複雑の度合はつながった物体の基本的関係に影響を与えない 。従って、複雑な物体ツリーにおいても、ワールド空間モデルを非常に柔軟に構 成することができ、そのためにデータベースの作成を比較的簡単にしている。ワ ールド空間モデルの作成は、どのシミュレータのコストに対してもかなりの割合 を占めるため、この事実は根本的な重要性をもつ。

オブジェクト空間から視点空間への物体変換を共同で可能にする回転行列と平行 移動ベクトルに加え、物体もまた以下のデータから構成される。

Ａ、物体に適用される細部のフェード・レベル（ＦＬＯＤ）因数。

ＦＬＯＤ因数は、システム・マネージャ２（図２）によって、ＣＡＤＢ１２から ＳＭ２に返されるデータに答えて決定される。このデータの流れは、図２に示し たＣＡＤＢ１２と８Ｍ２間のリターン・パスにより示される。

Ｂ、オブジェクト・プロセッサが、結び付けられる環境データにアクセスするた めに使用する（多チヤネルシステムを想定した場合の）チャネル同一性（ｃｈａ ｎｎｅｌ　１ｄｅｎｔｉｔｙ）。

Ｃ１物体内の全てのランダムスキャン光点をドロー優先度番号と結び付けるのに 使用される光点ドロー・オーダー・タスク番号（ｌｉｇｈｔｐｏｉｎｔ　ｄｒａ ｗ　ｏｒｄｅｒ　ｔａｓｋ　ｎｕｍｂｅｒ）。これにより、カリグラフィック光 点の投映を制御するために効率的なドロー順位が保持される。

物体は、このように、空間における方向、位置、他の物体への任意のポインタと 共に、多角形や光点等の特徴によって定義されるデータ・ブロックである。各物 体は独立し、他の物体とはいかなるデータも共有しない。しかし、物体内では、 最も多く使用されるのは、共有データである。例えば、多角形は、実際には頂点 座標データを含まず、単に頂点のブロック内の登録データへのポインタを有する だけである。これにより、２つの利益がもたらされる。ＣＡＤＢやプロセッサに 必要なメモリが減り、データは格納することが出来るので、特徴属性の大部分は １度処理するだけで済む。これは、２つの特徴が頂点を共有する場合には、重要 である。

従って、各オブジェクト・プロセッサは、物体を構成する個々の特徴というより も物体そのものを処理する間、先ず、指示された物体が範囲内にあるか否かを決 定し、次に、範囲内にある物体が視野内にあるか否かを決定する。この２つのテ ストをパスした物体を構成する個々の特徴は、次に、変換され、更なる処理のた めにスキャン・コンバータへと渡される。

物体範囲淘汰 視点から見るには遠すぎる物体は除外される。すなわち、その物体を処理する命 令は出されない。範囲淘汰は、物体を含む制限半球に最も近い点の（視点空間で の）Ｚ成分と、その物体に関する最大可視範囲を比較することにより行われる。

上述のように、物体は自身のオブジェクト空間に形成され、その空間では、物体 の原点が物体の座標系の原点であり、物体の中心がその物体を含む制限半球の中 心である。オブジェクト空間原点から物体中心の移動結果もまた格納される。次 に、以下の手続きが行われる。

ａ、移動のＺ成分は視点空間に変換され、物体（原点）移動のＺ成分に加算され る。

ｂ、物体制限半球半径はＺ成分から減算され、視点から制限半球の最短点までの 距離がめられる。

ｃ、ＳＭは、物体が選択される最大範囲を与える。上によりめられたＺが最大範 囲より大きい場合、物体は除外される。次に処理されるフレームに関する限り、 その物体とその物体のみにより指示されたあらゆる物体は自動的に除外される。

視点から物体への斜線内の範囲（ｓｌａｎｔ　ｒａｎｇｅ）ではなく、斜線Ｚ成 分（視点から表示スクリーンの中心に引かれた線）のみを利用する結果、出現す る場合があるスクリーンの辺に位置する物体は除外されない。それにも拘らず、 そのような物体は、視点から物体への斜線内の範囲を利用する細部選択機構（こ こでは詳しくは述べない）のレベルの結果除外される。

視野淘汰 視野淘汰は、表示スクリーンの境界内に指示された物体が見られるか否かを決定 する確認である。高すぎる物体、低すぎる物体、極端に右寄りの物体、極端に左 寄りの物体は全て除外される。すなわち、その物体処理の命令は行われない。物 体をスクリーン空間に透視し、物体がスクリーン上に存在するか否かを確認する のではなく、スクリーン境界で逆透視変換（ｉｎｖｅｒｓｅ　ｐｅｒｓｐｅｃｔ ｉｖｅ　ｔｒａｎｓｆｏｒｍａｔｉ。

ｎ）を行い、視点空間において視野淘汰が行われる。実際には、物体の最大値Ｚ （中心と制限半球の半径）について、（視点空間における）視野のためのＸとｙ の最大値がめられる。物体は、視野の上下よりも、側方に存在する傾向がある。

従って、先ず、側方視野淘汰が行われる。物体制限半球の範囲を定義するＸとｙ の値は、範囲淘汰に対しめられたＺと同様にしてめられる。計算値はスクリーン の境界の値と比較される。スクリーンから完全に外れた物体は、全て除外される 。

上記の方法で除外されない全ての物体に保存される特徴は、その後、オブジェク ト・プロセッサ内で処理されねばならない。この処理は、５つの基本手続きから なる。裏面除去（視点と反対の向きであるため、視点からは見ることができない 全ての特徴の除外）平面方程式係数計算（見える可能性がある各特徴の視点空間 にある平面の係数計算）、視野淘汰（スクリーンから完全に外れた全ての特徴の 除外）、境界ボックス計算（各特徴の最大及び最小スクリーン空間のＸとｙの範 囲）、そして線方程式計算（スクリーン空間における、処理される特徴の基本幾 何構造を定義する線を記述する方程式の計算）である。これらの処理を説明する にあたり、処理される様々な特徴に割り当てられる基本的幾何学属性を解説する のが適切でワールド空間では、３つの異なった特徴が必要不可欠である。それは 、４辺からなる多角形（以後、ポリコツト（ｐｏｌｙｑｕａｄ）と呼ぶ）、ラス ター光点（以後ＲＬＰ）　、カリグラフィック光点（。ａｌｌｉｇｒａｐｈｉｃ 　ｌｉｇｈｔ　ｐｏｉｎｔ）　（以後ＣＬＰ）である。現在の説明に関連するこ れらの特徴の幾何学属性について、以下に詳述する。

１、ポリコツト−４つの頂点と１つの面に対する法線ベクトル（Ｓｕｒｆａｃｅ 　ｎｏｒｍａｌ）で表現される多角形である。３辺からなるポリコツトは１つの ヌル頂点をもつにすぎない。

２、　ＲＬＰ−１つの位置、非対称の方向性に対する２つの方向ベクトル、１つ の基準ベクトルにより表現される。

３、　ＣＬＰ−ＲＬＰとまったく同じ意味で定義されるが、他のあらゆる種類の 特徴を通常のラスター走査手続きで表示後、高い輝度の点としてＣＬＰを投映す るため、ＲＬＰと区別するためのフラグが立てられる。

多くの場合、ＲＬＰとＣＬＰは、例えば、ビルディングの壁を表すポリコツトの ような、別の特徴の上に置かれる。その場合、光点に対する法線は、光点が置か れる特徴の面法線と同じである。例えば、どの方向からでも見られる自由位置光 （ｆｒｅｅ　ｓｔａｎｄｉｎｇ　ｌｉｇｈｔ）をシミュレートする、別の特徴の 上に置かれない光点について、視点から光点への視線に平行であるデフォルトの 基準ベクトルが定義される。

このように、全ての特徴は（オブジェクト空間からワールド空間に参照される） ワールド空間における定義された位置と、ワールド空間において定義される基準 ベクトルを持つ。

オブジェクト・プロセッサは、あらゆる種類の特徴について、裏面除去と平面方 程式属性計算と同じ手続きを行う必要があるが、それに続けてポリコツトや光点 （ＲＬＰ、ＣＬＰ両方）に対し異なった手続きを行う。

オブジェクト・プロセッサは、物体データの処理に加えて環境データの処理も行 う。

環境データは各フィールド毎に処理され、次の４つに分類される。

（ａ）他の全てのオブジェクト・プロセッサに一斉に届けられるデータ（例、シ ステム負荷係数） （ｂ）他の全てのオブジェクト・プロセッサに一斉に届けられ、１つのプロセッ サで処理され、ＲＥに送られるデータ（例、スクリーンの寸法） （Ｃ）処理のためにオブジェクト・プロセッサに送られ、その後ＲＥに伝送され るデータ（例、太陽ベクトル）（ｄ）処理されずにＲＥに直送されるデータ（例 、テクスチャー・マツプ） 環境データの処理は本発明に直接の関わりを持たないので、ここではこれ以上の 説明はしない。

裏面除去 オブジェクト・プロセッサは、裏面除去から特徴の処理を開始する。各特徴につ いて、面に対する法線ベクトルを視点空間に回転し、特徴上の制御頂点を視点空 間に回転、平行移動する。これにより、平面方程式係数（Ａ、Ｂ、Ｃ）と制御頂 点係数（Ｘ、、Ｙｃ、Ｚｃ）が発生する。これらは、平面方程式 ％式％ に代入され、”−Ｄ”を得る。（視点空間の原点に正対しない）裏面平面は”− Ｄ”として正の値を持つので除外される。これにより、全ての裏面の特徴が効果 的に除外される。

平面方程式属性計算 残った全ての特徴に対し、”−Ｄ′は −２，３＞ｐ＞＝−１，０ に正規化され、以下の属性を得るために使用される。

Ｃ／Ｄ ｋｘとｋｙは定数で、イメージを表示するスクリーンの大きさとアスペクト比（ ａｓｐｅｃｔ　ｒａｔｉｏ）を属性と関連づける。スクリーンが正方形の場合は 、ｋｘ＝ｋｙである。

平面方程式属性はスキャン・コンバータに渡され、各フィールドに対する定数と なる。

ポリコツト ポリコツトの辺の線方程式係数は、オブジェクト・プロセッサにより、図７を参 照し説明したポリコツトのスクリーン空間頂点から簡単に計算される。図７は、 ポリコツトの１辺を構成する線２７を計算する線方程式 ％式％ を示す。このポリコツトはスクリーン空間座標（Ｘｏ、ｙｏ）　、（ｘ１＋　ｙ ＋）　＋　（ＸＬ　ｙ２）及び（Ｘ　＄＋　ｙ　ｓ）をもつ頂点０．１．２、及 び３の間に定義される。表示（スクリーン）の境界は、スクリーン座標の原点（ ０，０）をスクリーンの中心とする線２８によって示されている。

正規化された線方程式で得たｅは以下からめられる。

ｅ＝　（ｙ＋　ｙｏ）／ｓｑｒ　ｔ　［（ｙ＋　ｙｏ）”＋　（ｘｌ−ｘｏ）　 ２］正規化された線方程式で得たｆは以下からめられる。

ｆ＝　（ｘｏ　Ｘ＋）　／ｓｑｒ　ｔ　［（ｙ＋　ｙｏ）　”＋　（ｘ、−ｘｏ ）　”コこのように、ｅとｆは簡単にめられ、ｇはめたｅ、ｆの値と頂点のいず れかの座標をこの線方程式に代入することにより簡単にめられる。

ＲＬＰとＣＬＰ 光点に対しては、辺方程式は計算されない。

ポリコツトの線方程式により、簡単なスクリーン視野のテストが可能になる。ス クリーンが長方形であると仮定すれば、ポリコツトのスクリーン空間で最も近く にある辺とスクリーンの中心との垂直距離がそのポリコツトの角とスクリーンの 中心とのそれより長いポリコツトは、必ず視野外に存在する。従って、スクリー ンの中心と各スクリーンの角との距離をｇｃｒｉｔ、ある特徴への距離をｇと仮 定した時、各特徴の辺に対し、 ｆ＜−ｇｃｒｉｔ であれば、その特徴は除外される（それ以上の処理は行われない）。

ポリコツト辺方程式係数の符合は、ポリコツトの辺１組が時計方向の、閉じた結 合ベクトル列を構成するよう公式化されている。更に、各辺への距離ｇは、スク リーンの中心が辺の線方程式の左側にある場合、負であるように計算される。こ れらの符合の取り決めに従い、多角形のいずれか一つのエツジに対してでもｇが −ｇｃｒｉｔより小さい場合、その特徴は除外される。これにより、ポリコツト が除外されるか否かの決定に必要な論理は簡略化される。

上述の多角形スクリーン淘汰は、スクリーンが長方形であるとの仮定で行われる 。しかし、この方法は、ポリコツトが長方形でない表示範囲にに衝突するか否か を決めるために用いることもできる。

この方法には、基準点（例においては、スクリーンの中心）、制限距離（例にお いては、スクリーンの中心からスクリーンの角までの距離）、そして基準点とポ リコツトの辺との距離と、制限距離を比較するための配列が必要である。遠くに ある全ての辺が表示範囲外にある様な制限距離を選択すれば、除外する多角形を 識別するために距離比較を利用できる。

境界ボックス計算 ポリコツト もう１度、図７を見ると、境界ボックスは破線２９により示されるスクリーンの 領域であり、ポリコツトの特徴上にあるかも知れないスクリーン空間の最大範囲 ｘＳｙの値で表される。例においては、境界ボックスの辺は次の通りである。

従って、境界ボックスは４つの線方程式で定義される。

または、一般に Ｔ−ｙ＝０ ｙ−Ｂ＝０ 但し、Ｌ、　Ｒ，Ｔ、Ｂは、それぞれ境界ボックスの左、右、上、下の範囲を表 す。

ＲＬＰとＣＬＰ 光点は、境界ボックスを直接導く頂点を持たないが、光点の中心が置かれる（ワ ールド空間における）１点を持つ。ＲＬＰはスクリーン空間では円形であり、範 囲によって大きさが変えられる。従って、境界ボックスは、スクリーン空間にお ける光点の大きさの関数として計算される。ＣＬＰもまた、スクリーン空間にお いては円形で、範囲の関数として計算される大きさと境界ボックスを持つが、そ の境界ボックスは、カリグラフィック光点が投映される方法を考慮すれば、その 大きさは、例えば、最大２ｘ２ピクセルに制限される。図８は、ある光点の境界 ボックスを表している。

多角形と境界ボックス辺方程式係数の符合は、多角形形の辺１組と境界ボックス の辺１組が、それぞれ時計方向の、閉じた結合ベクトル列を作るよう公式化され ている。

オブジェクト・プロセッサが特徴の処理を完了すると、（通係数の境界ボックス を含めた）属性がスキャン・コンバータに出力される。スキャン・コンバータの 機能は、オブジェクト・プロセッサから受け入れた各特徴のスクリーン座標幾何 学データを再検討し、その特徴がスクリーン領域を分割してできた複数の連続領 域に関連する可能性があるか否かを決定することである。スキャン・コンバータ の動作を説明するにあたり、レンダリング・エンジンでの処理のために、スクリ ーンがサブエリアに分割される方法を、図９に関連して解説する。

表示スクリーンのサブエリア 表示されるイメージは、重ならずに全体でスクリーンを覆°うピクセルの規則的 配列から構成される。後述のように、各ピクセルは、カリグラフィック光点によ る上書きが行われない場合、ラスター走査表示装置により、均一の色と輝度を持 つ領域として投映される。

図９は、スクリーンの様々なサブエリアを示す４つの図からなる。

１番左の図は、他の３つの１／４のスケールで示されている。

図９では、番号３０で表される各斜線部が１個のピクセルに対応している。スク リーンは、サブエリア、すなわちセルに分割され、各々が長方形のピクセル配列 、図の場合は４／４配列、を包含している。図９の番号３１は、１個のセルの境 界を指している。隣合うセルは重ならない。各セル上には、そのセルと周囲１／ ２ピクセル幅の範囲を包含する疑似セルが重ねられる。図９の破線３２は疑似セ ルの境界を表している。隣合う疑似セルは、互いに重なり合っている。各疑似セ ルは、例えば、４ｘ４に配列された疑似ピクセルのように、規則的に配列された 、隣合う疑似ピクセルに分割される。

図９の斜線部３３は、疑似ピクセルを表している。疑似ピクセル上には、各々が 長方形配列された疑似セル、図では４ｘ４に配列された疑似セルを包含するスー パーセルが重ねられる。このように、隣合ったスーパーセルは互いに重なり合う 。破線３４はスーパーセルの境界を、斜線部３５はそのスーパーセル内にある１ 個の疑似セルを示している。各スーパーセルは１６個の疑似セルを包含し、その １６個の疑似セルは全体で、１６個のセルとその外周１／２ピクセル幅の境界を 覆っている。

後述のアンチ・エリアシング（ａｎｔｉ−ａｌｉａｓｉｎｇ）を可能にするため には、隣合うスーパーセル、隣合う疑似セル、隣合う疑似ピクセルが重なり合わ なければならない。

ルスーパーセルの場合、１０２４ｘ１０２４ピクセルの表示範囲を想定すれば、 そこには６４ｘ６４のスーパーセルと２５６ｘ２５６の疑似セルがある。

スキャン會コンバータ オブジェクト・プロセッサによりスキャン・コンバータに送られる各特徴に対し 、スキャン・コンバータは、その特徴に部分的に少しでも重なる全てのスーパー セルを識別する。スキャン・コンバータはポリコツトとその他の特徴を判別する 。ポリコツトの場合、ポリコツトの辺を定義する線方程式と、境界ボックスを定 義する線方程式の両方が処理される。その他の特徴（光点）の場合には、境界ボ ックスの辺のみ処理される。

スキャン・コンバータは、各特徴に識別子（ＩＤ）を割り当て、その特徴により 衝突されるスーパーセルを識別し、スキャン・コンバータ・ストア２１（以降ス ーパーセル・ストアと呼ぶ）にそのポリコツトＩＤを送る。

図１０は、スキャン・コンバータ１９と、図２のスーパーセル・ストア２１の構 成を示す図である。スキャン・コンバータ・ストア２１は、個々のスーパーセル に関連するデータを格納する。属性は、ＴＥから入力１８に１特徴ずつ受け取ら れる。そして、属性インク−フェイス・モジニール３６は、特徴ＩＤを各特徴を 表すデータの流れに挿入し、スキャン・コンバータ・インプット・バッファ３７ と、属性ストア２２（図２）に連絡する属性バス３９に供給する役割を持つ属性 伝送モジュール３８に分配する。

インターフェイス・モジュールは、走査変換処理に必要な幾何学属性データだけ をバッファ３７に送る。このバッファ３７により、ＴＥからの属性データの流れ を遅らせる必要なく、受は入れデータを最適な速度で保存できる。そのバッファ 出力は、属性データを７個の線方程式プロセッサからなる配列４０に供給する。

この配列４０は、代わって、その線方程式プロセッサを制御するステート・マシ ンに出力を与える。４０と４１は図２における論理ユニット２０に対応する。書 き込み座標参照テーブル４２は、ダブルバッファをもつスーパーセルの書き込み 部の適切な場所に特徴ＩＤを振り向ける。読み込み制御ユニット４３は、次のフ レームの先頭でスーパーセル・ストアからデータを読み取り、座標テーブル４２ の読み取り部を制御する。

各線方程式プロセッサは、ステート・マシン４１により制御可能な、全く同一の 用途特定集積回路（ＡＳＩＣ）の形をとる。これ以後Ｄｉｅｔと呼ばれるＡＳＩ Ｃは、選択されたモードによって様々に機能する。各Ｄｉｅｔの詳細な構造は、 本発明の理解には重要でないので、ここでは説明しない。もちろん、単純な算術 演算を行うのに必要となる回路の構成要素は以下に説明する。

配列４０の３つのＤｉｅｔは、特徴の境界ボックスがスーパーセルに衝突するか 否かを決定するタスクを分担する。他の４角Ｄｉｅｔは、ポリコツトの辺方程式 から、そのポリコツトはがスーパーセルに衝突するか否かを決定するタスクを分 担する。衝突する特徴のＩＤは、それぞれのスーパーセル・ストアに格納されて いる。スーパーセル・ストアは、図１１に示されるように、各スーパーセルにつ き１個の格納スタックからなることが分かる。１個のスタックは最大２５６個の 特徴ＩＤを格納できる。従って、上記の例では、６４Ｘ６４個のスタックがあり 、各々のスタックは対応するスーパーセルに衝突する特徴の単純な記録（ＩＤの み）を格納する。

境界ボックス処理 あらゆる特徴の境界ボックスの走査変換は、ボックスの底辺から開始され、ボッ クス内をＸ軸方向に、ボックスの左右の辺の間にあるか、または左右のボックス 端に重なる全てのスーパーセルが確認されるまで行われる。その後、スーパーセ ルは、１行づつ、ボックス内を上の方向に処理される。処理されるスーパーセル は、唯一のスクリーン空間座標を持ち、その座標は、スーパーセルの中心（Ｘｓ ｅ＋　７ｉＪから境界ボックスの左、右、上端までの距離ｄＬ、ｄＲ。

及びｄＴをめるのに使用される。ｄＬ＝ｘ、ｅ−Ｌｄ　Ｒ＝　Ｒｘ　、ｃ ｄＴ＝　Ｔ−ｙｍｃ 走査変換は底辺から始まり、常に上方向に進行するので、ボックスの底辺までの 距離を計算する必要はない。

上述の方法でめられた３つの距離は、それぞれ、スーパーセルの中心（Ｘｔｃ、 ｙｍ、）からスーパーセルの辺までの距離と比較される。上の例では、スーパー セルは正方形であるため、スーパーセルは２ａ平方の大きさであると想像できる 。次に、境界ボックスの左の辺について考えると、 ｄＬ＜−ａの場合、スーパーセルは境界ボックスの左の辺より左側にある。これ は、アウトコード０１　（ｏｕｔｃｏｄｅ）の生成により表される。

−ａ＜＝ｄＬ＜＝＋ａの場合、そのスーパーセルは、境界ボックスにより衝突さ れる行で１番左のスーパーセルである。これは、アウトコード１０で表現できる 。

＋ａ＜ｄＬの場合、スーパーセルは、境界ボックスの１番左の辺の右側にある。

これは、アウトコード１１で表現できる。

コード０１１０，１１は、境界ボックスの左、右、上の辺に対し、この方法で得 ることができる。１つのコード０１は、スーパーセルが境界ボックスの外にある ことを意味する。１つのコード１０は、スーパーセルが境界ボックスの辺の１つ と交わっていることを示す。これは境界ボックスの走査方向を効率的に制御する ために使用される。例えば、ある特徴は、図１２中の線４４により示されるよう な境界ボックスを持つかもしれない。図１２内に描かれている格子は、境界ボッ クス４４に対するスーパーセルの境界の相対的配列を示す。スーパーセルは、も ちろん、わずかに重なり合っているが、それは図１２中では示されていない。ス キャン・コンバータは、境界ボックスの左下角を含むスーパーセルに行き、境界 ボックス内をｙ軸の正方向に横切って境界ボックスの右の辺に重なるスーパーセ ルが処理される結果としてアウトコード１０が生成されるまで進み、そして、ｙ 軸の正方向に１段階だけ進み、次にｙ軸の負方向に境界ボックスの左の辺に対し アウトコード１０を生成するまで進む、等の設定が可能である。従って、図１２ の場合には、スキャン・コンバータは、境界ボックス４４と重なるスーパーセル 中を１から２０の番号で示された順に進む。

光点の場合、スーパーセル衝突の確認のために、境界ボックステストだけが行わ れる。しかし、ポリコツトの場合、境界ボックステストと多角形造方程式テスト の両方が行われ、この２つのテスト結果の組合せにより、スーパーセルの検索路 が決められる。

ポリコツト辺方程式処理 ポリコツトの走査変換は、内部にポリコツトの底辺の頂点が特定されたスーパー セルから始まる。（同一のｙ座標をもつ２つの頂点がある場合、最も左のものが 選択される。）底辺上の頂点は変換エンジンによって決定され、図７の場合は、 頂点（Ｘｓ、ｙｓ）に相当する。

図１３において、正方形４５はスーパーセルを表し、四辺形４６は、ポリコツト を示す。ポリコツト４６の各辺について、スーパーセルの中心からの垂直距離ｄ が計算され、スーパーセルの中心からそのスーパーセルに接し、ポリコツトの辺 に平行な線までの垂直距離ｄｃｒｉｔが計算される。そしてその２つの距離の差 が計算される。

ｄｃｒｉｔ＝ｌｅ、ａｌ＋ｌｆ、ｂｌ 但し、ｅとｆは線方程式の係数であり、ａとｂはそれぞれスーパーセルの幅と高 さの１／２である。

垂直距離ｄは以下より得る。

ｄ＝ｅｘ＋ｆｙ＋ｇ 但し、ｅ、ｆ、ｇ、は、ポリコツトの辺についての線方程式係数ｄの符合は、ス ーパーセルの中心が線の左側か、右側かによって決まる。ｄｃｒｉｔの符合は不 変である。従って、以下を表すためにアウトコード０１．１０．１１を得ること ができる。

ｄ＜−ｄｃｒｉｔ（アウトコード０１）−ｄｃｒｉ　ｔ＝＝＜ｄ＝＜ｄｃｒｉｔ 　（アウトコード１０）ｄｃｒｉｔ＜ｄ　（アウトコード１１）アウトコード０ １は、スーパーセルがポリコツトの辺の完全に左側にあることを意味する。アウ トコード１１は、スーパーセルがポリコツトの辺の完全に右側にあることを示す 。アウトコード１０は、スーパーセルがポリコツトの辺（または、その辺の延長 ）にまたがっていることを意味する。４つのアウトコード１１は、スーパーセル がポリコツトに完全に包含されていることを示す。しかし、この４つのアウトコ ードを単に組合せることより、ポリコツト衝突を完全に決定できる。各アウトコ ードの第１ビツトを１つのゲート、第２ビツトを他のＡＮＤゲートとし、この４ つのアウトコードをＡＮＤゲートに応用すれば、結果として、以下のような２次 アウトコードを表現可能な２ビツトの出力を得る。

００−ポリコツトの完全に外側にあるスーパーセル０１−ポリコツトの完全に外 側にあるスーパーセル１０−ポリコツトに部分的に覆われるスーパーセル１１− ポリコツトに完全に覆われるスーパーセル後の２つは、処理中のスーパーセルが 処理中のポリコツトにより衝突されていることを暗示している。ポリコツトＩＤ は、このようにして、適切なスーパーセル・ストア・スタックに送られる。

ポリコツトの場合には、あらゆるスーパーセルに曖昧な出力を与えることにより 、スーパーセルがポリコツトにより少なくとも部分的に包含されているか否かを 表すことができるが、上述の境界ボックステストは、ポリコツトの検索を能率的 に制御し、完全にスーパーセル内に存在する境界ボックスの様な特別な場合の処 理の更なる情報を与える。

簡単な境界ボックステストを行うよりポリコツトを能率的に検索するために使用 できるな方法の１つは、最下部の頂点をもつスーパーセルから検索を開始し、明 らかにそのポリコツトの外側にある、または境界ボックスの最も左の辺を含むス ーパーセルに達するまで左に進み、その後開始点に戻り、明らかにそのポリコツ トの外側にあるか、その境界ボックスの右側の辺を含むスーパーセルに達するま で右に進み、そして１つ高い行のスーパーセルに進む過程を繰り返すことであろ う。スーパーセルの各行の開始点として、すぐ下の行で、ポリコツトにより衝突 されたと思われるスーパーセルのほぼ中間に相当する点を選択できる。再び図１ ０を参照すると、書き込み座標参照テーブル４２は、ダブルバッファをもつスー パーセル・ストアの書き込み部の適当な位置に各特徴ＩＤを向ける。読み出し制 御ユニット４３は、次の″フレーム交換″信号を受けると、スーパーセル・スト アよりデータを読み出す。このデータは、各スーパーセル・ストア・スタックか ら順に読み出される。データの読み出し速度もまた、イメージ・ジェネレータ・ パイプラインの次の構成要素であるブリソータから受ける”停止”入力により制 御される。

従って、評価に値することは、スキャン・コンバータにより行われる全過程が、 簡単に実行できることである。リアルタイム表示に十分なスルーブツトを得るに は、高速処理が必要であることは言うまでもないが、そのような速度は適当なＡ ＳＩＣにより達成される。

説明中のシステムは、計７個のＤｉｅｔ　ＡＳＩＣが与えられ、その中の４個は ポリコツトの辺方程式処理用に、３個は境界ボックス処理用に使用されている。

しかし、スルーブツトを上げるために、更に平行処理バスを与えることができる 。従って、スキャン・コンバータは最大スルーブツトにボトルネック的な制限を 加えない。また、そのアルゴリズムは凸状の多角形ならば、辺の数に関係なく取 り扱える。

上述の走査変換手続きは、システム効率を向上させるいくつかの特徴を持つ。そ の特徴は、以下のように要約できる。

ａ）各辺間数（Ｅ　（ｘ、ｙ）＝ｅｘ十ｅｙ＋ｇ）が辺から点（ｘ。

ｙ）までの距離と等しくなるような辺方程式の正規化ｂ）疑似セルが、ポリコツ トの辺の内側か、外側か、或は辺に掛かっているかを評価するためのｄｃｒｉｔ の使用Ｃ）完全な特徴評価に関する疑似セルのステータス決定のためのアウトコ ードの使用 ｄ）効果的な２つの平行な線方程式の使用ｅ）平行処理が可能なハードウェアの 導入正規化 線方程式係数ｅ、ｆ、ｇは、正規化因数ｎにより除算される。但し、 ｎ＝ｓ　ｑ　ｒ　ｔ　［（Ｘ２−ｘ＋）　２＋　（ｙｚ−３’＋）　２コ実際に は、ｎは頂点（Ｘ＋、Ｖ＋）から頂点（ｘ　！＋　’／　２）への辺上の距離で ある。

次に、辺間数ｅｘ＋ｆｙ十ｇは、点（ｘ、　ｙ）　を含む線からの直呼法（ｄｉ ｒｅｃｔ　ｍｅａｓｕｒｅ）である。

これは、スーパーセルの中心からの臨界距離であり、それに対しスーパーセルの 中心から特徴の辺までの距離ｄ　（＝ｅｘ十ｆｙ＋ｇ）が比較される。ｄｃｒｉ ｔは、スーパーセルの中心と特徴の辺の垂線上にある最も遠いスーパーセルの角 との間の変位を表している。

ｄｃｒｉｔの計算方法は上述されている。

アウトコード アウトコードは簡単に得られ、曖昧でないスーパーセルの衝突の評価を与える最 終アウトコードを生み出すために、単純なＡＮＤゲートを用い、簡単に組み合わ せられる。

２つの平行な線方程式 スーパーセルが、そのスーパーセルの辺の内側か、外側か、辺にまたがっている かを知るため、辺（エツジ）関数の値は以下のようにｄＣｒｉｔと比較される。

Ｅ　（ｘ、ｙ）　＝ｄ＜−ｄｃ　ｒ　ｉ　ｔ　ならば、スーパーセルは外側にあ る （アウトコード０１） Ｅ　（ｘ、ｙ）＝ｄ＞ｄｃｒｉｔ　ならば、スーパーセルは内側にある （アウトコード１１） さもなければ、スーパーセルはまたがっている（アウトコード１０） ［すなわち、−ｄ　ｃ　ｒ　ｉ　ｔ　＜＝Ｅ（ｘ、　ｙ）＝ｄ＜＝ｄ　ｃ　ｒ　 ｉ　ｔコもし２つの辺関数が Ｆ　（ｘ、ｙ）　＝Ｅ　（ｘ、ｙ）　＋ｄｃ　ｒ　ｉ　ｔＧ　（ｘ、ｙ）＝Ｅ　 （ｘ、ｙ）−ｄｃｒｉｔに初期化されるならば、ｄｃｒｉｔとの２つの連続して 行われる比較の要件は回避される。そのアウトコードは簡単な並列する符合テス トにより決定される。

Ｆ　（ｘ、ｙ）　＜Ｏならば、アウトコードＯＩＧ　（ｘ、ｙ）　＞Ｏならば、 アウトコード１１さもなければ、アウトコード１０ この２つの辺関数は、それぞれ垂直距離ｄｃｒｉｔと−ｄＣｒｉｔにより、問題 の辺からオフセットされた２つの線を効果的に定義する。

ハードウェアの導入 上述した距離計算のために、Ｄｉｅｔ　ＡＳＩＣの平行配列を利用したハードウ ェアの導入すれば、システムのスルーブツトは向上する。

レンダリング・エンジン 図１４に関連し、今、図４のＲＥ４の要点を説明する。図１４は、図２のスーパ ーセル・ストア１９と属性ストア２２を示している。

上述のように、スーパーセル・ストアと属性ストアは両方ともダブル・バッファ を持ち、フレーム信号の開始受信に続いてストアの内容が読み出される。スーパ ーセル・ストアの内容は、属性ストア２２からの幾何学的属性データも同様に受 け入れるブリソータ４７に、スーパーセル単位で読み出される。ブリソータと属 性ストアは、出力４８と４９をそれぞれ特殊効果モジュール５０、カラー・ミキ サ５１、ポストソータ５２、光点ストア５４に供給する。ポストソータは、フレ ーム・ストア５４にラスタ・イメージ・データを送り、光点ストアとフレーム・ ストアからの出力５５と５６は、表示装置（図１の表示装置５）に送られる。出 力５５はカリグラフィ、ツク光点の投映を制御する。

ブリソータ４７の機能は、各スーパーセルを連続する疑似セルに細別し、各疑似 セルの角で各特徴の有効深度（視点からの距離）を計算し、疑似セルを完全に覆 う不透明な全ての特徴を検出し、そのような特徴が、その疑似セルを完全に覆う 不透明な特徴の後ろに存在するかどうかを各疑似セルについて考慮し、廃棄する ことである。

このようにして、４ｘ４の表示ピクセルと１／２ビクセル幅の境界からなる疑似 セルの大きさが得られ、各スーツく−セルＩＤリストが、１６個の疑似セルの各 々について、順に、考慮される。

スーパーセル・ストア１９に蓄積されるＩＤは、スタ・ツク単位で、ブリソータ ４７にダウンロードされる。同時に、属性ストア２２からブリソータに、対応す る属性がダウンロードされる。このように、次のスタックがダウンロードされる までに、ブリソータは１個のスーパーセルに対応する１スタツクの内容を受け取 り、そのスタ・ソクの内容により識別される特徴を処理する。

ある特徴が、処理中の疑似セルに衝突する（その疑似セルを、少なくとも部分的 に覆う）場合、”フラグメント”データ・パケットが生成され、フラグメント輸 送出力バス４８に送られる。このデータ・パケットは、関連する疑似セルの４つ の角のスクリーン空間座標と衝突する特徴のＩＤだけで構成される。このように して識別された特徴のフラグメントは、次に、特殊効果モジュール５０、カラー ・ミキサ５Ｌボストンータ５２、光点ストア５３において処理される。

５０から５３の装置は、疑似ピクセルに応じて働く。図の場合には、１６個の疑 似ピクセルが各々の疑似セルを完全に覆っている（が、越えては広がらない）。

疑似ピクセルの角は、フラグメント・バスにより運ばれるそれぞれの疑似セルの 角に補間される。特殊効果モジュール５０は、処理中の疑似セルの各疑似ピクセ ルについて、処理されている特徴の属性が要求する、例えば、テクスチャー効果 、霧効果、着陸灯効果等の、あらゆる特殊効果に対し、適切な出力を生成する。

この出力は、周辺光等の更なる効果が処理されるカラー・ミキサ５１に送られる 。カラー・ミキサは、各疑似ピクセルについて、ＲＧＢＴ　（赤、緑、青、透明 ）出力をポストソータ５２に渡す。

光点ストア５３は、以下に詳しく説明されるように、カラー・ミキサ、ポストソ ータと共同で光点を処理する。光点ストア５３は出力５５を与え、ポストソータ はフレーム・ストア５４への出力を与える。フレーム・ストアは、ラスク表示装 置５（図１）に出力５６を与える。

ポストソータ５２の機能は、他の表面を完全に隠しているか、部分的に隠してい る面の効果を決定することである。その方法は、標本点配列への特徴の衝突を評 価し、その衝突の与える効果を累算、加重し、各表示ピクセルについての最終Ｒ ＧＢ出力をフレーム・ストアに与えることである。ポストソータが受け取る各疑 似ピクセルのフラグメントは、各疑似ピクセルに対応するピクセル配列中に分布 する各標本点配列を覆う。一般的には、２００カ所の標本点、す例の中で、各疑 似ピクセルは、４ｘ４個のピクセル配列と１ｘ２ビクセル幅の境界を覆うことが 思い出される。）各疑似セルに対し定義される４ｘ４個からなる疑似ピクセル配 列に関する各標本点の位置は既に分かっているため、特徴がその点に衝突してい るかどうかを各標本点について決定し、衝突が確認された場合には、対応する疑 似ピクセルからポストソータにＲＧＢ入力を蓄積することが必要とされる。

各標本点は、多数の特徴により覆われるかも知れないので、それらの特徴を深度 順にソートし、各の標本点で、より（視点の）近くにある不透明な特徴により完 全に隠される特徴を廃棄する必要がある。この目的のため、各標本点における、 各特徴の（視点からの）距離が計算される。標本点に衝突する最初の特徴のＲＧ ＢＴと深度は、各ストアにロードされる。それに続く特徴は、最初に保存された 特徴と深度比較され、最も近くにあった不透明な特徴より近いところにある、現 在量も近くにある不透明の特徴と半透明の特徴を除いて、ストアから廃棄される （またはストアに入れられない）。セルに関連する可能性がある全ての特徴に一 旦この処理が行われると、各スタックで識別される全ての累積効果が計算され、 最終ＲＧＢ出力が各抽出について生成される。各ピクセルは、自身の境界内にあ る８つの標本点と、近くの１ｘ２ビクセル幅の境界内の標本点、すなわち、全部 で３２標本点（１ｘ８＋４ｘ４＋４ｘ２）からの貢献に応じる。この合計３２の 標本点を包含する領域は、２ｘ２ビクセルからなる配列の領域と同じであるが、 １表示ピクセルの中心上に中心を持つ。

パイプライン化されたシステム内のステージ間の境界を定義するために、属性ス トア２２、スーパーセル・ストア１９、光点ストア５３、及びフレーム・ストア ５４は全てダブルバッファを持つ。

図１４のシステム働きを詳述する前に、このシステムの一般構造に固有の利点を 概説するのが適切であろう。第１に、真の隠面の排除が例外なく行われる。すな わち、各標本点についての、イメージに貢献するモデル特徴の相対的優先度は、 各標本点における（視点からの）特徴の距離間の直接比較に基づいて決定される 。このことは、例えば、滑走路上のマーキングのような共通の平面を共有してい る特徴を除いて、モデラは、相対的優先度を考慮する必要がないことを意味する 。このような共通平面優先度は、適当なフラグにより簡単に表すことができる。

第２に、処理のためにデータを組み立てる間のシステムのデッド・タイムが最短 になり、スルーブツトが向上する。第３に、システムは、計算が集中するタスク を平行プロセッサにより行う構造になっている。例えば、幾何学変換は、オブジ ェクト・プロセッサ内の平行プロセッサ間に分配され、ブリソータ・タスクは、 それぞれが１つの疑似セル、または疑似セル群を担当する複数の平行プロセッサ 間に分配され、ポストソータ・タスクは、それぞれが１個のの標本点を担当する 平行プロセッサに配布することができる。システム・スルーブツトは、システム の大規模な再設計を必要とせず、基本”基礎単位”を加えるか、減らすことだけ で調整できる。４番目に、特殊効果モジュールとカラー・ミキサ機能は、システ ムの基本構造に影響を与えず、必要なだけ複雑にできる。第５に、以下の説明で 更に明らかになるが、本来、システムは表示装置の非線形性を補正することがで きる。６番目に、半透明物のエリアシング（ａｌｉａｓｉｎｇ）と陰面の排除が 正確に行われる。以下に、上述のレンダリング・エンジンを、更に詳しく説明す る。

ブリソータ 今、図１４のブリソータ４７に目を移しと、ブリソータは、スーパーセルから特 徴ＩＤを１つづつ受け取り、識別された特徴に衝突される、各スーパーセル内の 疑似セルを決定する。ブリソータは、識別された特徴に対する辺と境界ボックス 方程式を受け取り、ポリコツトと光点を区別する。ポリコツトには、辺と境界ボ ックスの両方を使用し、ポリコツトと疑似セルの重複を決定する。光点は、ＣＬ ＰとＲＬＰのどちらに対しても、境界ボックスの辺だけが使用され、重複を決定 する。

各特徴ＩＤと各疑似セルを構成する１６の疑似セルそれぞれについて、ブリソー タは、特徴がその疑似セルに衝突しているか否か、特徴が完全に疑似セルを覆っ ているか否か、もし完全に覆っているならば、特徴が不透明か否かを決定する。

特徴の平面上に射映される疑似セルの角の深度（視点からの距離）も、各特徴に ついて計算される。その後、特徴ＩＤが、最も近くにある完全に包含する不透明 な特徴、近くにある部分的に包含する特徴、または部分的か完全に包含している 半透明の特徴を識別するリストとして保存される。

ブリソータは、ポリコツトのために、各疑似セルの角からポリコツトの各辺まで のスクリーン空間での垂直距離を計算する。ブリソータは、各特徴の境界ボック スの各辺までのスクリーン空間での距離も計算する。光点は、ある特定の疑似セ ルが衝突されたかどうかに関する決定を補助する辺を持たないため、光点につい ては、境界ボックスの辺までの光点距離のみが計算される。境界ボックス辺距離 と、ポリコツト辺距離は同時に計算され、疑似セルの衝突が決定される。

各距離は、スキャン・コンバータの場合に似た方法で、ＤｉｅｔＡＳＩＣにより 計算される。

図１５から１８に、辺の距離からのポリコツトの衝突を評価する方法が説明され ている。図１５では、疑似セルは１から４の角を持ち、ポリコツトはＡからＤの 辺を持つ。辺方程式を参照すれば、以下の距離（ｄの値）が得られる。

ｄｌＡ、ｄ２Ａ、ｄ３Ａ、ｄ４Ａ ｄｌＢ、ｄ２Ｂ、ｄ３Ｂ、ｄ４Ｂ ｄｌｃ、ｄ２Ｃ，ｄ３Ｃ，ｄ４Ｃ ｄｌＤ、ｄ２Ｄ、ｄ３Ｄ、ｄ４Ｄ 図１５．１６．１７は、距離ｄｌＢ、ｄ２Ｂ、ｄ３Ｂ、ｄ４Ｂを、例をあげて示 している。図１５と１６においては、ｄの値すべてが正である。図１７において は、６２Ｂは負であるが、ｄｌＢ、ｄ３Ｂ、ｄ４Ｂは正である。全ての特徴につ いて、１６の距離からなる同じ集合が、境界ボックスの辺を参照して計算される 。すなわち、それは、各疑似セルの角から各境界ボックスまでの距離である。従 って、図１８に示される例では、疑似セルの角２について要求されるｄ値は、そ の角から境界ボックスを定義する４本の破線のそれぞれへの垂直距離に対応する 。

１つのポリコツトに関する４つのｄ値、すなわちその辺から疑似セルの４つの角 までの距離について考える時、条件は以下のように分けられ、関連するアウトコ ードにより表される。

４個のｄ値がそれぞれ正、またはゼロ アウトコード１１ ４個のｄ値の全てが負、または、あるものは負、またあるものはゼロ アウトコード０１ さもなければ、他のあらゆる組合せ アウトコード１０ ４つの辺についてのアウトコードは、次に、ＡＮＤゲートにより組み合わされ、 以下の総アウトコード（ｔｏｔａｌ　ｏｕｔｃｏｄｅ）を生む。

総アウトコード　意義 １１　疑似セルを完全に包含する特徴 １０　疑似セルにまたがった（部分的に覆う）特徴０１　特徴は疑似セルの外側 にある ００　特徴は疑似セルの外側にある 境界ボックスの辺から疑似セルの角までのｄの値は、ポリコツトの辺に対するｄ 値と同じ方法で処理され、各境界ボックスの辺に対しては、アウトコード１１． ０１、または１０、組み合わされた境界ボックスの辺については総アウトコード １１．１０．０１、または００を与える。このように、多角形用（ＯＣｔｏｔ） と境界ボックス用（ＯＣＸｔＯｔ）の２つのアウトコードが生み出さる。光点に ついては、境界ボックスの辺以外の”辺”はない。従って、光点については、ポ リコツトの辺に対応する絶対アウトコードとして、デフォルト値である１０が設 定される。

その２つの絶対アウトコードは組み合わされ、”包含（ｉｎｃｌｕｄｅ）”　（ 更なる処理に引き渡される特徴）、または”全体遮蔽（ｔｏｔａｌｃｏｖｅｒ） ”　（更なる処理に引き渡され、かつ特徴は不透明であり、疑似セルの全てを覆 う）のいずれかに断定される。

包含は、 ０ＣＸｔｏｔ＝１７ かつ ０Ｃｔｏｔ＝１７ 但し？は、１、または０ である場合のみ、断定される。

全体遮蔽は、 フラグメントが”包含“であり、 かつ ０Ｃｔｏｔ＝７１ かつ ０ＣＸｔｏｔ＝７１ かつ フラグメントは、透明でも光点でもない但し、ここでも？は１、または０である 。

図１９は、ブリソータの働きを示すフローチャートである。上記のように、ブリ ソータは、疑似セルの衝突の分析に加えて、特徴のフラグメントを最初に除外す る（すなわち、完全に不透明の特徴の、完全に後ろにあるフラグメントを廃棄す る）。ブリソータは、各疑似セルの角について、処理中の特徴の深度を計算する 。これには、後述のように、標準ＡＳＩＣにより実行可能の逆透視変換が必要と される。逆透視変換には、システムを通じて同じＡＳＩＣが使用される。特徴属 性の一部として、ブリソータは、ＴＥにおいて上述の方法で計算された、多角形 平面方程式係数を受け取る。これらは、各疑似セルの角において、逆Ｚ（視点か ら関連する疑似セルの角へ引かれた線と交差する特徴平面上の点についての、視 点平面座標Ｚの逆座標）を計算するのに使用される。

このようにして、各特徴について、各疑似セルに１つの２深度が計算される。そ の後、この４つの各Ｚ深度は、最も（視点に）近い場所にある、以前に処理され た、完全に覆う特徴の４つの各Ｚ深度と同時に比較される。処理中の特徴のＺ深 度全てが、比較対象の、最も近い場所にある、完全に覆う、不透明の特徴のＺ深 度より大きい場合、その処理中の特徴は除外される。処理中の特徴のＺ深度全て が、比較対象の、最も近い場所にある、完全に覆う特徴より小さく、その処理中 の特徴が不透明である場合、その処理中の特徴は、以前に処理された完全に覆う 不透明の特徴と入れ替えられる。

図２０は、プリソータにおける、特徴の深度のソートを示している。視野の方向 は、矢印５７で示されている。破線５８と５９は、疑似セルの上下の境界を示し ている。６０から６６の線は、この図に対し垂直な平面にある特徴を示している 。特徴６０は不透明ではないが、６１から６６の特徴は不透明である。特徴６２ は、最も近い場所にある、完全に覆う、不透明の特徴であるが、線５８上のその Ｚ値は、特徴６４の線５８に射映されたＺ値より大きいため、特徴６４は除外さ れない。特徴６２の線５９上のＺ値は、特徴６５の投映のＺ値より大きいため、 特徴６５は除外されない。特徴６３と６６は除外される。

図２１は、プリソータ・プロセッサを図式化したものである。図２１を見れば、 プリソータは、入力６７上で連続する衝突する特徴のリストを受け取る。各リス トは、それぞれのスーパーセルに対応する。属性ストアからの属性データも、入 力６８上で受け取られる。

各疑似セルのスクリーン空間における）４つの角は、セレクタ６９により決定さ れる。上述のように、各疑似セルは、１６ピクセルと１／２ピクセル幅の境界に 相当する広さを持つ。理想的な状態では、基本セルは正方形または長方形である が、多くの表示システムに固有の歪効果のため、セルがその効果を打ち消す様、 非標準な形のセルの形成が非常に望ましい。従って、選択された疑似セルは、そ の４つの角に対し、４つの異なったＸ座標と４つの異なったＸ座標を持つ可能性 がある。表示システムの非直線性を克服するための疑似セルの角の選択について 、以下に更に詳しく説明する。

セレクタ６９の出力は、上述の種類のＤ］ｅｔ７０と、疑似セルの角に対応する 各特徴の平面上の４点の逆距離（ｉｎｖｅｒｓｅ　ｄｉｓｔａｎｃｅ）（１／Ｚ ）を計算する距離カルキュレータ７１に送られる。この計算では、特徴の平面は 疑似セルの全てを覆うと仮定される。上述のように、Ｄｌｅｔはポリコツトの特 徴を得るため、３２の計算を行う。すなわち、疑似セルの各角について、角から 特徴の辺までの垂直距離と、角から特徴の境界ボックスの各辺までの垂直距離を 計算する。光点については、１６の（境界ボックスへの）距離のみが計算される 。

アナライザ７２は、上述のように特徴がそれぞれの疑似セルに衝突しているか否 かを決定する。特徴が疑似セルに衝突する場合、各疑似セルの角において、その 特徴のＩＤは、その視点からの距離と共にストア７３にロードされる。コンパレ ータ７４は、その距離と以前に保存した特徴の距離を比較し、隠された特徴をス トア７３から除外する。

各疑似セルが処理されると、選択されたＩＤはフラグメント・バス４８（図１４ ）上に出力される。フラグメント・バスは、疑似セルの角の（スクリーン空間） 座標と、その疑似セルに関連する特徴ＩＤをを運ぶ。疑似セルの角座標から、疑 似セルを構成する１６個の疑似ピクセルの角が、双１次補間（ｂｉｌｉｎｅａｒ 　１ｎｔｒｐｏｌａｔｉｏｎ）によって得られる。

負荷バランス 図２１に示した種類のプロセッサが与えられる場合のみ、１６個の疑似セルは、 １つずつ単純に処理される。しかし、システムのスルーブツトを高めるために、 複数の（例えば、４つの）疑似セル・プロセッサを与えることは有効である。も し、４つの疑似セル・プロセッサが与えられた場合、各疑似セル・プロセッサは 、それぞれ４個からなる疑似セル群を担当し、プリソータの４サイクルでスーパ ーセルが完全に処理される。

疑似ピクセルのあらゆる行や列も、例えば地平線の様な、特徴の密度がスクリー ンの他の領域よりも高いことが多いシーンの”凝った”部分を覆う可能性がある 。例えば、４つのプリソータ・プロセッサが与えられたと仮定する。各プロセッ サが４個の疑似ピクセルからなる１行を割り当てられ、あるプロセッサが他のプ ロセッサよりもイメージの凝ワた部分を処理するならば、そのプロセッサは他に 比べて過負荷となる。しかし、もし各ブリソータ・プロセッサに、それぞれのス ーパーセル中に配布された疑似セルが割り当てられるとすれば、この問題は解決 できる。図２２は、そのような配布を図示している。４ｘ４の格子は、１つのス ーパーセルを表し、格子内の１６の各サブエリアは、それぞれの疑似セルを表し ている。負荷のバランスは、最初のプロセッサに１番のラベルの付いた疑似セル を割り当て、次のプロセッサに２番のラベルの付いた疑似セルを割り当てる、と いう単純な方法で保つことができる。このように、単にブリソータ処理タスクを 配布することで、１つのプロセッサに過負荷がかかる可能性を大幅に減らすこと ができるため、簡単に実行できる方法で、ブリソータ内の負荷バランスを保つこ とができる。

２つのプロセッサしか与えられない場合、どの疑似セル行、列においても、すぐ 隣りの疑似セルの処理を他のプロセッサで行うことで負荷のバランスが保たれる 。

標本点分配 図２３は、最終的に描かれたイメージの１ピクセルに関する３２の標本点の分布 を示している。図２３において、破線７５で表された正方形の輪郭は、１つの疑 似セルの境界を境界を表している。破線７６で示された正方形は、３２の標本点 を囲む領域の境界を表している。この３２の標本点から取られた標本は、破線７ ６により囲まれた範囲内の中心に位置するピクセルに割り当てられた最終ＲＧＢ 値と関連を持つ。そのピクセルの辺の１つが数字７７で示されている。破線７６ で囲まれた範囲内の点は、個々の標本点を表す。疑似セルの境界に対する標本点 の位置は、フレーム毎に固定されるが、推計学的な標本が要求される場合には、 フレーム毎に変更（ディザ−（ｄｉｔｈｅｒｅｄ））可能である。問題のピクセ ルの境界内には、８つの標本点があることが分かる。隣り合う１／２ピクセルの 範囲内にそれぞれ４標本点、隣合う１ｘ４標本点にそれぞれ２標本点がある。

１ピクセル当りの標本点の数は、もちろん、システムが必要とされる能力に適し た数が選択される。標本点の数を増やせば、最終イメージの質が向上する。

特殊効果モジュール 特殊効果モジュール５０（図１４）は、図２４に図解されている。

特殊効果モジュールは、ブリソータ４７からフラグメント・データ、属性ストア から属性データを受け取る。モジュールは、７８から８１の連続するサブシステ ム構成され、それぞれのサブシステムが、１つの特殊効果を処理する。図では、 サブシステム７８は、テクスチャー、サブシステム７９は霧、サブシステム８０ は着陸灯、サブシステム８１は陰影づけの特殊効果を処理する。もちろん、他の 特殊効果用にサブシステムを供給することもできる。各サブシステムが、処理中 の疑似セルを構成する各疑似ピクセルについて、それぞれの出力（Ｔ、　Ｆ、　 ＬＬ、Ｓ）を生成する。疑似セルは、ブリソータからフラグメント・バスに送ら れるときに、１つずつ処理される。

テクスチャー・サブシステムを例にすれば、各疑似ピクセルに関するテクスチャ ー出力を生み出すために、従来のテクスチャー技術を使用することもできる。そ のような技術に不可欠の要素は、適用される各モデルの特徴に対しテクスチャー を定義した”テクスチャー”空間に疑似ピクセルを投映し、投映された各疑似ピ クセルについてテクスチャー空間座標を計算し、テクスチャー・マツプから計算 されたテクスチャー空間座標に対応するテクスチャーを読み取り、その結果を出 力することである。しかし、テクスチャー出力Ｔやその他の特殊効果を計算する のに採られたアプローチの詳細は、本発明に密接な関係を持たないので、ここで はこれ以上はふれない。ただ、出力Ｔ、Ｆ、ＬＬ、Ｓは、特殊効果が適用される 各疑似ピクセルについて生成されることを認識することが必要である。

カラー・ミキサ カラー・ミキサ（図１４）は、図２５に示されている。カラー・ミキサは、ブリ ソータ４８からフラグメント・データ、属性ストア２２から属性データ、特殊効 果モジュールの出力Ｔ、Ｆ、ＬＬ、Ｓを受け取る。カラー・ミキサ内には、必要 な効果を生むための様々な入力を組み合わせるサブシステムがある。これらのサ ブシステムは、配列された８２から８７のプロセッサから構成され、各プロセツ サには、固有のタスクが割り当てられる。様々なサブシステムとカラー・ミキサ への入力の間の詳しい関係は、本発明と深い関わりを持たない。ただ、カラー・ ミキサは、処理中の疑似セルを構成する疑似ピクセルに対するＲＧＢの値を含む 出力８８をもたらすことを認識することが必要である。出力８８は、ポストソー タ５２に送られる。

ポストソータ 今、図２６を参照する。図２６は、ポストソータの構造を図解している。各標本 点（疑似セルにつき２００）に１つのポストソータ・プロセッサが与えられる。

各ポストソータは、標本点・インパクト・ディテクタ８９、逆Ｚ深度カルキュレ ータ９０、半透明スタック９１、及びアキュムレータ９２から構成される。ポス トソータ・プロセッサの出力は、回路９３により加重され、累算される。ピクセ ル毎に１つ、すなわち１疑似セル当り１６の回路が与えられる。ポストソータの 働きは、図２７に示されている。

各ポストソータ・プロセッサは、それぞれの疑似セルに衝突していると確認され た各特徴の幾何学属性と、配置された標本点を含む疑似ピクセル用に、カラー・ ミキサにより生成されたＲＧＢＴ値を受け入れる。その疑似セルに関係する標本 点を位置を参照し、各標本点のために適切な疑似ピクセル・データが選択される 。不透明体のスタックを乱さないように、完全に透明な標本は廃棄される。

各疑似セルについて、その疑似セルを覆う１６の疑似ピクセルのためのＲＧＢＴ 値が、カラー・ミキサからポストソータに入力される。各ポストソータ・プロセ ッサは、標本点を含むクオドラント（ｑｕａｄｒａｎｔ）が４つの疑似ピクセル 値を受け入れるよう調整される。１つのクオドラントは疑似セルの１／４、すな わち２／２個の疑似ピクセルである。しかし、各プロセッサは、そのプロセッサ の標本点を含む疑似セルのための単一のＲＧＢＴ値以外は無視するようにプログ ラムされる。各疑似ピクセル領域は１２個、または１３個の標本点、各クオドラ ント領域は５０個の標本点、そして、隣ある２つの疑似ピクセル１組は、２５個 の標本点を含む。

標本点の衝突評価 ポリコツトの場合、インパクト・ディテクタによる標本点が衝突されたかどうか の決定は、処理中の特徴の線方程式に依存する。図２８は、ポリコツト９４と、 それぞれ、ポリコツト９４により衝突される９５と、衝突されない９６の２つの 標本点を示している。ここでもまた、疑似セルの角から各辺までの垂直距離を決 定するために、Ｄ］ｅｔ　ＡＳＩＣによって、多角形の辺を定義する線方程式が 使用される。プロセッサは、次に、双１次補間を用いて、その４つの辺から自身 の標本点までの距離を計算する。各標本点について、４つの距離が出力される。

４つ全てが正、またはゼロの場合は、衝突が起こっている。１つでも負である場 合には、衝突はない。

２つの特徴辺の間の境界が、ちょうど標本点を通過する（距離がゼロの）場合は 、覆い隠しが発生する可能性がある。もし、特徴の双方が標本点に衝突している と判断されるならば、その結果、オーバーラツプが起こる。どちらの特徴も標本 点に衝突していないと判断されるならば、その結果、”ホール”が起こる。この 問題は、もし、２つの内１つの特徴がその特徴が共通の辺を”所有している”こ と、すなわち、その特徴だけが標本点に衝突していることを意味するフラグを立 てることで解決できる。そのようなフラグを作る１つの方法は、ちょうど標本点 を通過する（垂直距離がゼロの）全ての辺を識別することであり、その標本点の ために、同一基準を満たす更なる特徴の全てをを阻止することである。同様の問 題は、標本点に衝突している特徴の座標についても発生する。この問題もまた、 標本点に衝突する２つ目以降の多角形を阻止することで解決される。

光点 ＲＬＰとＣＬＰの双方の光点の場合には、衝突の評価は、比較的単純である。以 下に、スクリーン空間における円形の光点について説明する。光点の円の中心の スクリーン空間座標と光点の半径は、ＴＥ（図１）において計算される。光点半 径と内在輝度の計算については、図２９を引用して説明する。図２９では、実線 ９７は、半径の振動を視点座標におけるＺを使って表している。最初の制限距離 ＬＩＮより小さいＺについて、光点半径は最大の半径に強制される。カリグラフ ィック光点の最大半径は、カリグラフィック光点プロジェクタ−が処理できる最 大サイズを超えないように制限されなければならず、ラスター光点の最大半径は 、スクリーン空間の非現実的に大きな領域を占めないように制限されなければな らない。２つめのあらかじめ決定された制限距離Ｚ　ＬＩＭより大きいＺについ て、光点が小さくなりすぎた場合に起きるフレーム間の制御不可能な”きらめき “、すなわち、シンチレーションを防ぐため、半径は最小の半径にに強制される 。もちろん、必要ならば、故意にシンチレーションを起こすこともできる。それ は、連続するフレーム間の光点の内在輝度を変えることで行われる。ＺＭＩＮと Ｚ　ＬＩＭ間の距離の光点については、例えば、Ｚの２乗というような関数とし てＺを使って、半径を小さくする。

内在輝度もまた、線９８により表されるＺに基づき、調整される。

従って、Ｚ　ＬＩＭより小さいＺについては、輝度は一定に保たれ、ＺがＺ　ｔ ＋ｔ＋を超えて増加するにつれて減少する。このように、半径と輝度両方の適切 な調整によって、現実的な領域効果がシミュレートされる。２１半径、内在輝度 間の正確な関係は、基本的に重要ではないが、図２９に示された例は、現実的な 効果を提供する。

図３０は、光点の衝突の評価を示している。図３０において、光点の境界は円９ ９で表されている。それぞれスクリーンのＸ軸とｙ軸に平行である線１００と１ ０１について、平凡に計算される。その方程式は、 である。但し、（ｘｃ、ｙ、）は、光点中心の座標である。標本点１０２と１０ ３は、例中で示される。各標本点について、線１００と１０１に対する垂直距離 ｄ１とｄ２が計算される。もし、（ｄｉ）”十（ｄ２）”＜＝Ｒ２ であれば、標本点は衝突される。

こうして、全種類の特徴に対する衝突の評価が説明される。

各特徴に対する標本点に衝突する特徴の深さの逆数（１／Ｚ）は、Ｚ深度カルキ ュレータ９０により計算される。図３１は、基本的幾何学的図形配列を表してい る。特徴１０４は、視点１０６からの祝事面（ｖｉｅｗｉｎｇ　ｐｌａｎｅ）　 １０５を通して観察される。その特徴の平面方程式が、受は取られる属性から確 認され、特徴上の任意の点Ｐの視点空間の座標（ｘ、ｙ、ｚ）が、次の方程式に より計算される。

ｚ＝−Ｄ／　（Ａｘ、／ｄ、＋Ｂｙ、／ｄ、＋Ｃ）但し、Ａ、Ｂ、Ｃ，Ｄは、特 徴の平面方程式係数、ｄ、、ｄ、は、表示角度の１／２の関数、 Ｘｌ、ｙ、は、視点からＰ点に引かれた線のスクリーン空間座標、そして Ｘｏとｙｏは、スクリーン空間の原点の座標である。視点空間のｘｌｙの座標も また、 ｘ＝ｚｘ、／ｄｚ　ｙ＝ｚｙ、／ｄｙ から、簡単にめられる。

注目すべきことは、逆透視変換は、適当な場所でシステムを通じて使われる、例 えば、Ｚ深度特徴のソートのため、プリソータで行われる変換や、おそらく、専 用ＡＳＩＣによって行われる変換と同じである。

衝突しているフラグメントの深さの逆数は、ＲＧＢＴ値と共に、半透明スタック に渡される。そのスタックは、例えば、８エントリーを記憶でき、各エントリー は、１個の特徴のフラグメントに対するＲＧＢＴと１／Ｚを含む。（特定の標本 点において）半透明の特徴のフラグメントがスタックに与えられると、その１／ Ｚが、スタック内に存在する全てのエントリーと比較される。それまでエントリ ーがないと仮定すると、最初の半透明の特徴は、８の位置を指す”トップ・オブ ・スタック”ポインタによって示されるスタックの８の位置に保存される。次の （２番目の）半透明であるフラグメントは、８の位置にあるフラグメントの深度 と比較される。その２個のフラグメントは、近い方のフラグメントを７の位置と し、７と８の位置に保存される。スタック・ポインタは、次に、７の位置を指す 。

標本点において受け取られたフラグメントが不透明である場合、そのフラグメン トは、深度順に、スタックの正確な位置に置かれ、次に、（まだ、８の位置にな い時は）スタックの８の位置まで下がる。

スタック内の、その下の全てのエントリーは廃棄され、その上の全てのエントリ ーは、深度の順番が保たれるよう、そのフラグメントにつれて下がる。スタック ・ポインタは、一番近い（スタックの最上部の）フラグメントの動きを追ってい る。

ＲＬＰの場合にも同じ手続きが使用されるが、常駐できるＲＬＰＯ数が、例えば １個に、制限される。従って、スタック中で現在一番近い不透明の特徴より近く にある最初のＲＬＰは、スタックの適当な位置に挿入される。２つ目のＲＬＰが 受け取られると、最初のＲＬＰは廃棄される（それが常駐するＲＬＰよりも視界 から遠い場合）か、スタックの適当な深度でソートされた位置へ挿入（それが常 駐するＲＬＰより視点に近い場合）される。２つ目のＲＬＰがスタックに挿入さ れる場合には、それまで常駐していたＲＬＰは廃棄される。一般に、現実的な最 終イメージを得るには１つのＲＬＰで十分であるが、１つ以上のＲＬＰがスタッ クに受け入れられる装置では、そのＲＬＰの最大輝度は、ピクセルのラスター投 映により可能な比較的低いレベルに制限される。

ＣＬＰの場合、これらはスタックには入らず、半透明スタックにロードされた特 徴を更に処理するかどうかを検討後、後述のように処理される。このように、各 ポストソータプロセッサは、深度順に並べられ、それぞれが結び付いた、ＲＧＢ とＴの値を持つフラグメントリストを生成する。そして、各標本点の最終的な色 分布が、アキュムレータ９２で計算される。Ｔｏ、ＴＩ、、、、Ｔ６の半透明度 を持つ７つの半透明なフラグメントがあり、７つの半透明フラグメントと１つの 不透明フラグメントが、ＲＩＧＩＢＩ−−−Ｒ７Ｇ７Ｂ７の色を持つと仮定すれ ば、ｎ番目の半透明フラグメントの前に蓄積する半透明度は、 ｃＴｎ＝ＴＯｘ　Ｔ、ｘ　、、、ｘ　Ｔ、。

各最終色成分（Ｒ，Ｇ、Ｂ）は、次のように計算される。

Ｒ＝ｃＴＯｘ　ＲＯ＋　ｃＴｌ　ｘ　Ｒ１＋　、、、　ｃＴ７　ｘ　Ｒ７ Ｇ＝ｃＴＯｘ　ＧＯ＋　ｃＴｌ　ｘ　Ｇｌ　＋　、、、　ｃＴ７　ｘ　Ｇ７ Ｂ＝ｃＴＱ　ｘ　ＢＯ＋　ｃＴｌ　、ｘ　Ｂｌ　＋　、、、　ｃＴ７　ｘ　Ｂ７ 従って、各標本点プロセッサは、１個のＲＧＢ値を生成し、最終的に作り出され るピクセルのＲＧＢは、この値を合計し、加重したものから得られる。

最終イメージの各ピクセルについて、３２の標本点、つまり、そのピクセル内の ８標本点と、そのピクセルを囲む１／２ピクセル幅の境界内の２４標本点が関連 する。ピクセルの中心近くの標本点は、ピクセル境界の辺近くの標本点より、多 くの効果を持たねばならないため、標本点には異なった重さが割り当てられる。

各標本点は、４つの異なったピクセルに貢献し、貢献するピクセルに対し、異な った重さを持つ。その重さは、標本点と関連するピクセルの中心の距離の関数で ある。

各ウェイティング／アキュムレータ装置９３は、３２個のポストソータ・プロセ ッサから出力を得て、適当な重さを適用し、結果を合計し、その合計をフレーム ・ストア内のそれぞれのピクセル・アドレスに出力する。セル内の全１６個のピ クセルは、１６個のウェイティング／アキュムレータ装置により同時に処理され 、１６ピクセルからなる次のセルに関連するデータは、ポストソータに開放され る。その過程は、全てのスーパーセルの全てのセルが処理されるまで繰り返され る。そして、完成したフレームは表示用にダウンロ光点ストアは、ＲＬＰ半透明 度計算と、ＣＬＰ半透明度計算以降の処理の２つの機能を行う。

光点の半透明度は、光点の輝度の関数として計算される。ＲＬＰとＣＬＰの輝度 は、当初は干渉する特徴はないとの仮定で、光点ストアで計算される。計算され た輝度は範囲、方向性、大気密度等の関数でなければならない。半透明度は、高 輝度の光点では低く、低輝度の光点では高くなるに計算される。正確な光度と透 明度の関係は特に重要であるが、例えば、その関係は、ある最初に与えられた輝 度レベル以下について最下限の半透明値があらかじめ決められると、次に与えら れる輝度レベル以上の光点は不透明であると判断される。半透明度は、その２つ の与えられたレベル間で、非線形的に異なる。輝度は、光点ストアに供給される 属性から計算され、ＲＬＰの輝度は、図１４の光点ストアとカラー・ミキサ間で 表されるバスを通してカラー・ミキサに戻される。

カリグラフィック光点 ＣＬＰは、フレーム・ストアの内容がラスター走査により投映された後に投映さ れる。ＣＬＰは、ラスター・イメージ上に重ねられる。ＣＬＰの輝度は、そのＣ ＬＰと視点の間の特徴を説明するものでなければならないため、ＣＬＰは、特徴 の全てが適当な半透明スタックに入れられた後、処理される。ＣＬＰは、他の特 徴の全ての処理が終わるまでに戻される必要がある。更に、最終イメージの品質 にとって重要なことは、オーバーラツプしたＣＬＰがビルドアップ（蓄積）して はならないことである。対ビルドアップ機構が与えられない場合、例えば、地表 近くの滑走路の端から観察される滑走路灯は輝度がその範囲とともに増大するよ うに見える。このため、滑走路のもう一方の端は、丘を登っているように見える 。

あらゆる標本点について、そのサンプリング点に衝突する各ＣＬＰのＺ深度は、 それぞれのスタックにある特徴のＺ深度と比較される。

カリグラフィック光点は、各列が１個のオブジェクト・プロセッサにより処理さ れる１列の光点として組み立てられ、そのオブジェクト・プロセッサから、視点 に近い列から遠い列の順に出力される。

従って、各標本点は、最初の列の最も近くの衝突するＣＬＰを受け入れる。

各標本点について、その標本点に衝突するＣＬＰの減衰が、半透明スタックで識 別される特徴の半透明度の関数として、ＣＬＰより視点近くにあるように計算さ れる。ＣＬＰの′アパーチャ”も計算される。”１”は、標本点に衝突している ことを示し、”０”は、衝突していないことを示す。各標本点の”アパーチャ” と”減衰率”は、ウェイティング／アキュムレーション装置（図２６の９３）に 組み込まれ、それぞれのセル内にある各ピクセルの比較された減衰率とアパーチ ャが、光点ストアに出力される。

標本点で受け取られる最初のＣＬＰの半透明率は、その１個が各ボストソータ・ プロセッサの半透明スタックと結合しているベール・ストアに保存される。２つ めのＣＬＰが同じ標本点に衝突する場合、その減衰率は最初のＣＬＰと同様に計 算されるが、既に保存されているＣＬＰも加味される。計算済みの減衰率とアパ ーチャは、衝突された他のＣＬＰのものと結合され、元のように光点ストアに出 力される（ベール・ストアに保存される）。最初のＣＬＰの半透明率は、その後 、２つめのＣＬＰの半透明率と乗算され、組み合わせた半透明率が得られる。こ れは、やがて、新規の値としてそれぞれのベール・ストアに書き込まれる。この ように、ベール・ストアは、それぞれの標本点に衝突する全てのＣＬＰを累算し た半透明率を保存する。このことは、より遠くのＣＬＰを事実上覆い隠す１個の ＣＬＰの効果を説明する。そのためには、ビルドアップ対策が必要な全てのＣＬ Ｐは、近いものから遠いものの順に、ポストソータに渡されることが必要条件と なる。例えば、非常に高い輝度の光源をシミュレートするようない（つかの効果 については、ＣＬＰのビルドアップが望ましいこともある。これは、問題となる ＣＬＰに対する対ビルドアップ機構を単に無効にすることにより行われる。

ＣＬＰの投映技術は、全てのＣＬＰが、ガウスの輝度分布を使い、円形のスポッ トとして投映されることを意味する。１つのＣＬＰ内の輝度を調節することはで きない。そのため、ＣＬＰの輝度はそのＣＬＰの累算されたアパーチャと減衰率 の関数として計算される。

累積したアパーチャの数は、ＣＬＰと衝突する可能性がある、それぞれのセル内 の標本点の数である。累積した減衰率は、（より近くにある不透明の特徴による ）覆い隠しと（より近くにある半透明の特徴による）減衰が加味された後の、セ ル内のＣＬＰの可視部分の基準である減衰因数を表す。例えば、あるＣＬＰが１ セル内に完全に含まれると計算され、その大きさはそのセル内の２０の標本点を 覆うと計算される場合、そのアパーチャは２０となる。もし、より近くに１つの 不透明の特徴があり、それによりその内１０の標本点が覆い隠されるならば、そ の減衰因数は１０と計算される。もう１つの例として、より近（に１つの半透明 の特徴があり、それによりその２０の標本点の内１０が覆われ、その半透明率の 値が０５である場合、減衰因数は１５と計算される。最初の場合には、ＣＬＰの 最終輝度は、０．５（減衰因数（１０）をアパーチャ（２０）で割った数）に修 正される。２つ目の場合は、ＣＬＰの最終輝度は、因数０．７５（減衰因数（１ ５）をアパーチャ（２０）で割った数）により修正される。

ＣＬＰは複数の隣合うセルに重なることが出来るため、そのＣＬＰにより覆われ る全てのセルがボストンータにより処理されるまで、最終輝度計算は遅らされる 。最終輝度は、全ての重なったセルからのアパーチャを合計し、全ての重なった セルからの減衰率を合計し、その２つの合計値の比をめることで得られる。

図３２は、光点ストアの図解である。光点属性データは、オブジェクト・プロセ ッサから受け取られ、属性ストア１０７に保存される。

各ＣＬＰ列のためのＣＬＰ・ドロー・オーダー・リストも同様に、オブジェクト ・プロセッサより受け取られ、ドロー・オーダー・リスト・ストア１０８に保存 される。ドロー・オーダー・コントローラ１０９は保存されたリストを使用し、 ＣＬＰディスプレイ・インターフェイス１１１による、適切な順序のＣＬＰ表示 データを受け取りが可能であるようＣＬＰ・ストア１１０にアドレスする。

方向性プロセッサ１１２は、眼方向ベクトル（ｅｙｅ　ｄｉｒｅｃｔｉｏｎ　ｖ ｅｃｔｏｒ）をオブジェクト・プロセッサより出力１１３上で受け入れる。

方向性プロセッサは、−（ンテンシティ。アンド・サイズ・プロセッサへの入力 に適当な輝度を出力する。プロセッサ１１５は、光点（ＲＬＰまたはＣＬＰ）に 対する不透明度の値を出力１１６上に生成し、その値はカラー・ミキサに返され る。プロセッサ１１５は、また、ＣＬＰの大きさと輝度を示す出力１１７を生成 する。

ストア１１０は、位置と色属性を属性ストアから入力１１８上で受け取り、また 人力１１７を受け取る。アパーチャ／減衰率アキュムレータ１１９は、アパーチ ャと減衰率データを、入力１２０上で受け取り、累算されたアパーチャと減衰率 の出力をストア１１０に与える。ストア１１０は、同一のＣＬＰにより覆われた 隣合ったセルより得たアパーチャと減衰率の累算を可能にするため、アキュムレ ータ１１９に入力を与える。このように、ストアは、最終ＣＬＰ表示データを累 算し、ドロー・オーダー・コントローラの制御の下でディスプレイ・インターフ ェイス１１１に出力する。

非線形マツピング イメージ・ジェネレータがしばしば遭遇する問題の１つに、非線形マツピング（ ｎｏｎ−１ｉｎｅａｒ　ｍａｐｐｉｎｇ）がある。イメージを、例えば、スフエ ロイド・ミラー越しに見たバック・プロジェクション式表示スクリーンのような 非平面的表示スクリーン上にイメージを映写する場合、プロジェクタ−が軸から それていれば、非線形の状態が起きる。その結果、表示されるビクセルは、長方 形でない上に、形も大きさも均一ではない。表示されるイメージを歪曲させたく ない場合には、修正が必要である。

上述のシステムにおいて、表示スクリーンは正方形の疑似セルに分割され、個々 の疑似セルは、全て同一サイズの正方形をした整然としたピクセルの配列からな る。疑似セル上の特徴の衝突は、疑似セルの角を参照して決定され、標本点上の 特徴の衝突は、疑似セルの境界に対する標本点の相対位置を参照して決定される 。この一般的構造が、視覚システムの不完全さから生じる歪んだラスク走査に対 応する疑似セルの境界を設定することで、非線形マツピングの修正を可能にして いる。

更に詳細には、ブリソータにおいては、特徴の衝突は、疑似セルの各角とその特 徴の辺の距離を計算することにより決定される。図３３を参照すると、正方形の 疑似セル１２１は多角形１２２と衝突しないため、多角形１２２は疑似セル１２ １の対象から除外される。

しかし、疑似セル１２１に対応する情報を表示するために光学系を使用し、疑似 セルの領域を歪曲させ、その歪曲した角を１２３から１２６の数字で示すと、角 １２４は多角形１２２内にまで延びるだろう。従って、多角形１２２は、その疑 似セルと結び付く特徴リストに含まれねばならない。

これは、疑似セルの角が射映された時の位置に対応する、歪曲した疑似セルを利 用することにより簡単に行われる。従って、１個のセルは４つの角（Ｘｏｙｏ） 、（ｘ＋ｙυ、（Ｘ２Ｙ２）、（ＸｓＹｓ）を持つと仮定すると、正方形のセル の場合は、ＸＯ：Ｘ２、Ｖｏ＝Ｖｒ、Ｖ　２＝　Ｖ　ｓ、ｘｌ＝ｘ、である。一 方、歪曲したセルでは、その２つの座標の値は同じである必要はない。従って、 通常、表示装置は歪曲しない（ｒｅｃｔｉｌｉｎｅａｒ）疑似セルの配列からな るが、疑似セルの角は、光学射映系での歪曲のために歪んでいる。ブリソータ内 の計算は全て有効であり、歪曲修正された疑似セルに関するものでも、歪曲した 疑似セルに関するものも含む。疑似ピクセルの境界は、例えば、補間によって、 角の座標から簡単に推論出来る。説明した例においては、歪曲した疑似ピクセル の４つの辺は直線である。図３３の場合は、疑似セルの角１２４は多角形１２２ の内部にあると見なされ、多角形１２２のＩＤは、その疑似セルに関係するもの として次の処る方程式と同じものに基づいている。特別効果モジュール内では、 疑似セルの角は上述のように、疑似ピクセルの角は疑似セルの角から補間により 得られるという方法で処理される。従って、歪曲されない疑似セルの場合と同様 に、ポストソータへの入力は、連続する特徴ＩＤであり、各特徴ＩＤは１６個の 疑似ピクセルＲＧＢＴを伴う。

標本点とピクセル境界は、補間により、疑似セルの角に相対する位置、すなわち 、疑似ピクセルの座標系と同じ座標系に相対する位置に固定される。

従って、１ピクセルに関係する３２標本点からなる各標本点群が分かる。図３３ は、１２８により示された１／２ピクセル幅の境界を持つ、斜線部２７により表 された１ピクセルと示している。疑似ピクセルとピクセルの境界が、疑似セルの 角から補間されるとき、ピクセル自体は正方形ではないことがわかる。標本点の 分布は、結び付いたピクセルの歪曲と一致する。従って、映写時に斜線部１２７ を覆うピクセルに関連してフレーム・ストアにロードされるＲＧＢは、１２２の 領域に対する適切なイメージの情報に一致する。

上述のシステムにおいて、スキャン・コンバータは初期特徴ソート過程を経て、 スーパーセルに関する特徴のリストを定義する。映写装置の歪曲を処理するため に疑似セルが歪められる場合、それぞれの疑似セル群に関する全ての特徴が、ス ーパーセル・スタックにより確実に識別されるように、対策を講じなければなら ない。これは、例えば、スキャン・コンバータが歪曲した空間内で機能するよう 設計するか、歪曲した疑似セルのスーパーセルの組合せへの重なりを疑似セルの 位置により表示するようスーパーセル・リストを組み合わせる等の方法で行われ る。

上に要約した非線形マツピングの方法により、表示が幾何学的には解決できない ことが確信される。直線状のな多角形の辺は、セルの境界で、切れ目なく、緩や かに歪曲する。セルの境界においては、部分的な推測は出来ない。更に、多角影 線方程式を再計算することも、歪曲したピクセルに”適合する”ために特徴を分 解する必要もない。テクスチャや霧などの効果は、同様に歪曲する。従って、モ デルのデータベースからダウンロードした特徴データを処理するために、システ ムの全能力が利用できる。最後に、表示スクリーンや視点に対して、プロジェク タの射出瞳（ｐｒｏｊｅｃｔｏｒ　ｅｘｉｔ　ｐｕｐｉｌ）が動く時、非線形マ ツピングは動的になる（疑似セルの角を変化させる）かもしれない。これは、あ る映写システムで、例えば、”興味のある領域”　（ａｒｅａ　ｏｆ　１ｎｔｅ ｒｅｓｔ）として、パイロットが見ている方向に表示装置が向けられた場所が表 示される場合に起きる。

ＦＩｏ、２６ 国際調査報告 １ｍｌ’ｌＪＩＩａＭｌ＾ｍ−ｌ−１１−ＰＣＴ／ＧＢ８９１０１４５１国際調 査報告

Claims (1)

1. 【特許請求の範囲】 １．複数の透明、並びに、半透明の特徴を含むモデルを定義するデータから、表 示スクリーン上に表示するイメージを生成するようにし、上記イメージは所定の 視点からの上記モデルの景観を表すよう意図されるとともにラスタ走査過程によ り表示されるスクリーン空間ピクセルの配列によって構成され、各ピクセルは均 −の色と輝度をもち、上記ピクセルが集まってイメージ・エリアを定義するよう にした装置であって、上記装置は、以下の手段から構成される；ａ．上記イメー ジ・エリアを分割し、それぞれのサブエリアが少なくとも１個のピクセルを−包 含するように分割するための手段、ｂ．視点から見える可能性のあるモデル内の 各特徴について、少なくとも部分的にその特徴に包含されるサブエリアを決定す るための手段、 ｃ．各サブエリアに関する特徴固定のリストを生成するための手段、そのいずれ か１つのサブエリアに関するリストは、少なくとも部分的にそのサブエリアを包 含する特徴を固定する；ｄ．各サブエリア内の少なくとも１個の標本点を包含す る、スクリーン空間の位置を決定するための手段、ｅ．各サブエリアについて順 に、かつ上記の各標本点について、その標本点を包含するサブエリアリスト内の 特徴を決定するための手段、 ｆ．標本点を包含する各特徴について、視点から特徴までの標本点における距離 の関数を決定するための手段、ｇ．サブエリア内の各特徴について、特徴を記述 するデータを格納するための手段、格納されたデータは、標本点を包含し、視点 に最も近い不透明な特徴の距離と標本点を包含する少なくとも１個のより近くに ある半透明の特徴の距離と半透明度を表す：ｈ．サブエリア内の各標本点に対す る出力を生成するための手段、その標本点出力は、上記データ格納手段に格納さ れたデータによって固定される特徴を組み合わせた効果に相当する；ｉ．サブエ リア内の各ピクセルに対する出力を生成するための手段。 そのピクセル出力は、そのピクセルに寄与する全ての標本点に対する標本点出力 の複合効果に対応する；並びにｊ．上記ピクセル出力を表示するための手段。 ２．請求項１に記載の装置において、 各サブエリアが榎数個のピクセルを包含するもの。 ３．請求項１、または２に記載の装置において、それぞれが上記の標本点包含決 定手段、上記の距離決定手段、上記の格納手段、並びに上記の標本点出力生成手 段を含む複数個の平列標本点プロセッサを含むもの。 ４．請求項３に記載の装置において、 サブエリア内の標本点或は各標本点のための１個の標本点プロセッサを含むもの 。 ５．請求項１から４のいずれか−に記載の装置において、それぞれが上記のピク セル生成出力手段を含む複数個の平列ピクセル・プロセッサを含むもの。 ６．請求項５に記載の装置において、サブエリア内の標本点或は各標本点のため の１個の標本点プロセッサを含むもの。 ７．請求項１から６のいずれか−に記載の装置において、上記ピクセル出力生成 手段が、ピクセル内にある標本点或は各標本点、及びピクセルの周囲に拡がる所 定の領域内にある標本点或は各標本点から、ピクセルに関する入力を受けるもの 。 ８．請求項７に記載の装置において、 上記の所定の領域が、ピクセルの周囲に拡がる１／２ピクセル幅の細長い領域で あるもの。 ９．請求項１から８のいずれか−に記載の装置において、各標本点に対し、上記 標本点包含決定手段が、その標本点と、それぞれのサブエリアを少なくとも部分 的に包含する全ての多角形特徴の辺との垂直距離を計算するための手段と、標本 点が多角形内にあるか否かを決定するための距離計算の結果を論理的に組み合わ せるための手段を含むもの。 １０．請求項９に記載の装置において、各多角形の辺が辺方程式により定義され 、その辺方程式の係数は、辺上を全て同−方向に走るつながったベクトル列から なる閉じた多角形を形成するように選択され、上記距離計算手段は、各辺方程式 に関して、標本点を含む辺のどちら側かを符合により示す出力を生成し、上記論 理組合せ手段は、標本点が多角形内にあるか否かを、多角形の辺との距離の符合 により表示するための手段から構成されるもの。 １１．請求項１０に記載の装置において、多角形は凸状で、その辺は、辺上を全 て時計方向に走るつながったベクトル列からなる閉じた多角形を構成し、上記距 離計算手段は、標本点が多角形の左側にある場合には、その多角形を表す辺方程 式について全て負の出力を生成し、上記論理組合せ手段は、上記距離計算手段の １つの出力でも負の場合には、標本点が包含されていないことを意味する出力を 生成するもの。 １２．請求項１から１１のいずれか−に記載の全てに該当する装置において、 標本点包含決定手段が、各標本点について、その標本点とそれぞれのサブエリア を少なくとも部分的に覆うスクリーン空間にある楕円の特徴の全ての主軸と従軸 の垂直距離を計算するための手段、標本点が楕円の特徴により覆われるか否かを 決定するために、スクリーン空間方程式に計算された楕円の距離を代入するため の手段から構成されるもの。 １３．請求項１から１２のいずれか−に記載の装置において、上記距離決定手段 が、それぞれの標本点のスクリーン空間座標から、視点から標本点に引かれた線 上にある特徴の上の点の１つ以上のの視点空間座標を計算するために、その標本 点の逆透視変換を行うための手段から構成されるもの。 １４．請求項１３に記載の装置において、上記視点空間座標は、視点から表示ス クリーンの中心に拡がる視点空間のＺ軸上の座標であるもの。 １５．請求項１から１４のいずれか−に記載の装置において、格納手段が、半透 明スタックメモリ、標本点から受け取った各特徴の視点への距離と、格納手段よ り以前に受け取った全ての特徴の視点への距離とを比較するための手段、更に、 スタックに受け入れた各特徴を、視点からの距離順となるスタック位置に格納す るための手段から構成されるもの。 １６．請求項１５に記載の装置において、完全に透明の特徴がスタックに格納さ れるのを抑止するための手段から構成されるもの。 １７．請求項１５と１６に記載の装置において、同−平面上の特徴の相対可視性 を定義する特徴属性データに基づき、スタック内の同−平面上の特徴の位置を決 めるための手段を含むもの。 １８．請求項１５、１６、１７に記載の装置において、スタックの最終位置にあ る最初に受け入れた不透明の特徴を固定するための手段、並びに、最初に受け入 れた不透明の特徴識別データを、スタックの最終位置にある以前に格納された特 徴より視点に近い後続して受け入れた不透明の特徴についてのみ、後続して受け 入れた不透明特徴を固定するデータと置き換えるための手段から構成されるもの 。 １９．請求項１８に記載の装置において、上記格納手段が、視点距離からの距離 順に格納されたスタック内の半透明の特徴、及び、廃棄されるスタック内の最終 位置に格納されたデータにより固定される不透明の特徴よりも視点より遠い不透 明の特徴を固定するデータを格納するための手段を含むもの。 ２０．請求項１５から１９のいずれか−に記載の装置において、イメージのラス ター・ピクセルを表すように意図された特徴には、他の特徴と区別するためにフ ラグを立てられるようになっており、格納手段は半透明スタックに格納されるか も知れないラスター光点の特徴の量大数を制限するための手段を含むもの。 ２１．請求項２０に記載の装置において、半透明スタック内のラスター光点特徴 の数を１に限定するよう上記制限手段が配列されたもの。 ２２．請求項１５から２１のいずれか−に記載の装置において、イメージに含ま れるカリグラフィック光点を、カリグラフィック的に投映される光点として表す よう意図された特徴には、他の特徴と区別するためのフラグを立てるようにし、 上記装置は、更に、全ての非カリグラフィック光点が読み出された後に、視点に 近いものから遠いものの順にカリグラフィック光点の特徴を上記格納手段に読み 出すための手段、各標本点を包含するカリグラフィック光点の減衰を計算するた めの手段、各カリグラフィック光点に包含される全ての標本点に対する計算され た減衰を累算するための手段、及び各カリグラフィック光点に関して、累算され た減衰の関数であるカリグラフィック光点の輝度出力を生成するための手段を含 み、上記減衰は、少なくとも、カリグラフィック光点より視点の近くにある半透 明スタックに格納された特徴の半透明度を説明するものであり、上記輝度出力は 、カリグラフィック光点の映写装置を制御するカリグラフィック光点に供給され るものである。 ２３．請求項２２に記載の装置で、カリグラフィック光点についてのアパーチャ を決定するための手段、カリグラフィック光点に対する減衰因数を決定するため の手段、及び光点の内在輝度に、アパーチャで減衰因数を割ることにより計算さ れた数を掛けることによりカリグラフィック光点に対する表示輝度を計算するた めの手段から構成されるもの。上記アパーチャは、能書光点により覆われる可能 性がある標本点数に等しいもので、上記減衰因数は、覆われた各標本点における カリグラフィック光点の減衰の合計であり、各標本点の減衰はモデルとなった世 界において、視点に達するカリグラフィック光点として表される特徴により発せ られる光の面積の関数であるもの。 ２４．請求項１から２３のいずれか−に記載の装置において、格納手段が、各標 本点を包含する特徴の赤色、緑色、青色の半透明属性を識別するデータを格納す るもの。 ２５．請求項２４に記載の装置において、標本点出力生成手段が、以下の方程式 から導かれる赤色、緑色、青色の出力を生成するための手段により構成されるも の。 Ｒ＝ｃＴＯ・ＲＯ＋ｃＴ１・Ｒ１＋．．．ｃＴＮ・ＲＮＧ＝ｃＴＯ・ＧＯ＋ｃＴ １・Ｇ１＋．．．ｃＴＮ・ＧＨＢ＝ｃＴＯ・ＢＯ十ｃＴ１・Ｂ１＋．．．ｃＴＮ ・ＢＮ但し、Ｒ，Ｇ，Ｂは、それぞれ赤色、緑色、青色の出力であり、ｃＴＮは 、上記格納手段により格納された視点からの距離順位Ｎ番目の特徴の累算された 半透明度であり、ＲＮは、上記格納手段により格納された視点からの距離順位Ｎ 番目の特徴の赤色の成分であり、 ＧＮは、上記格納手段により格納された視点からの距離順位Ｎ番目の特徴の緑色 の成分であり、 ＢＮは、上記格納手段により格納された視点からの距離順位Ｎ番目の特徴の青色 の成分である。 ２６．請求項１から２５のいずれか−に記載の装置において・上記ピクセル出力 生成手段が、各ピクセルに関係すると見なされる各標本点に対する標本点出力生 成手段から出力を受け取る加重累算回路を含み、上記加重累算回路は、上記ピク セルに関連する各標本点の位置に適当な標本点出力生成手段の受け入れ、各出力 に対し重みを割り当て、上記ピクセル出力を生成するために標本点生成手段の加 重された出力を累算するもの。 ２７．請求項１から２６のいずれか−に記載の装置において、上記標本点位置決 定手段が、各サブエリアに対するスクリーン空間角座標を決定するための手段と 、角座標からの補間により標本点座標を決定するための手段を含む。 ２８．請求項１から２７のいずれか−に記載の装置において、各サブエリアはサ ブエリアのスクリーン空間における境界が、視点空間から、それぞれのピクセル 、または複数個のピクセルにより覆われる表示スクリーン領域のスクリーン空間 へのマッピングを表すスクリーン空間領域の境界に対応するように形成されてい るもの。 ２９．請求項１から２８のいずれか−に記載の装置において、各サブエリアが、 上記の１個以上ののピクセルと、近くの所定の距離に延びる重なる境界領域を包 含するもの。 ３０．請求項２９に記載の装置において、境界領域の幅が、ピクセル幅の１／２ と同じであるもの。 ３１．請求項１から３０のいずれか−に記載の装置において、上記サブエリア包 含範囲決定手段が、サブエリアを完全に包含する不透明の特徴を検出するための 手段とその完全に包含する不透明の特徴より視点から遠くにある特徴を廃棄する ための手段を含むもの。 ３２．請求項３１に記載の装置において、各特徴により定着された平面のサブエ リアの各角と視点との距離を計算するための手段とその計算された距離を比較す るための手段とを含み、上記廃棄手段は、その特徴に対し計算された距離が、視 点に最短の不透明特徴に対し計算された距離よりも大きい場合のみ、特徴を廃棄 するもの。 ３３．請求項３２に記載の装置において、上記廃棄手段が、それぞれのサブエリ アを少なくとも部分的に包含する特徴を固定するデータが読み込まれるストアを 含み、上記比較手段は、最も近くにある不透明の特徴の背後にある特徴を固定す るデータをストアから取り消すため、ストアから出力を受け、ストアに入力を与 えるもの。 ３４．請求項１から３３のいずれか−に記載の装置において、上記サブエリア包 含決定手段が、全ての特徴を境界ボックス内に含むために、サブエリアの各角か ら、各特徴に対するスクリーン空間座標において定義される境界ボックスの辺へ の垂直距離を計算するための手段から構成されるもの。 ３５．請求項３４に記載の装置において、境界ボックスが、その辺上を全て同− 方向に走るつながった閉じたベクトル列を形成し、上記組み合せ手段が、各サブ エリアの角についてアウトコードを生成するようになっており、上記各コーナー についてのアウトコードは、境界ボックスの辺の距離が全て同じ符合か、ゼロの 場合、最初のアウトコードであり、境界ボックスの辺の距離が全て異なる符合か 、そのいくつかが異なりまたいくつかがゼロの場合、２番目のアウトコードとな り、他の境界ボックスの辺の距離の組合せが生成される場合、３番目のアウトコ ードとなり、上記各コーナーについてのアウトコードは、合計アウトコ−ド（ｔ ｏｔａｌｏｕｔｃｏｄｅ）を形成するため、ゲートにより組み合わされ、最初の 合計アウトコードは、境界ボックスがサブエリアを完全にを包含することを意味 し、２番目の合計アウトコードは、境界ボックスがサブエリアを部分的に包含す ることを意味し、そして残りの総アウトコードは、境界ボックスがサブエリアの 外側にあることを意味するようになっているもの。 ３６．請求項１から３５のいずれか−に記載の装置において、サブエリア包含決 定手段が、サブエリアの各角と多角形の特徴の辺との垂直距離を計算する手段と 、サブエリアの遮蔽を示すための出力を与えるために計算された垂直距離を論理 的に組み合わせるための手段とを含むもの。 ３７．請求項３６に記載の装置において、多角形の特徴は、辺上を全て同−方向 に走るつながったベクトル列からなる閉じた多角形を形成するように定義され、 上記組み合せ手段は各サブエリアの角についてアウトコードを生成するようにな っており、各コーナーについてのアウトコードは、多角形の辺の距離が全て同じ 符合か、ゼロの場合、最初のアウトコードであり、多角形の辺の距離が全て異な る符合か、そのいくつかが異なりまたいくつかがゼロの場合、２番目のアウトコ ードとなり、他の多角形の辺の距離の組合せが生成される場合、３番目のアウト コードとなり、上記各コーナーについてのアウトコードは、総アウトコード（ｔ ｏｔａｌｏｕｔｃｏｄｅ）を形成するため、ゲートにより組み合わされ、最初の 総アウトコードは、境界ボックスがサブエリアを完全に包含することを意味し、 ２番目の合計アウトコードは、境界ボックスがサブエリアを部分的に包含するこ とを意味し、そして残りの総アウトコードは、境界ボックスがサブエリアの外側 にあることを意味するもの。 ３８．請求項３５と３７の組み合せにかかる装置において、最終のアウトコード を生成するために、総アウトコードを組み合わせるための手段を含み、最初の最 終アウトコードは、境界ボックスと多角形の辺のアウトコードが、どちらも最初 または２番目の合計アウトコードの場合、サブエリアが少なくとも部分的に覆わ れることを表し、２番目の最終アウトコードは、境界ボックスと多角形の辺の最 終アウトコードがどちらも最初の合計アウトコードであり、特徴が不透明の場合 、サブエリアがその不透明の特徴に完全に覆われることを表すもの。 ３９．請求項１から３８のいずれか−に記載の装置において、イメージエリアを 、各々が複数個の上記サブエリアを覆うスーパーサブエリアの配列に分割するた めの手段、各スーパーサブエリアを少なくとも部分的に包含する特徴を固定する データを格納するための手段、上記格納手段から上記サブエリア包含決定手段に データを１スーパーサブエリア毎に読み込むための手段を含む。 ４０．請求項３９に記載の装置において、上記サブエリア包含決定手段が、スー パーサブエリアの各サブエリアを個別に処理するもの。 ４１．請求項４０に記載の装置において、上記サブエリア包含決定手段が、２つ 以上ののプロセッサから構成され、処理タスクを各プロセッサに配分するために 、隣合ったサブエリアが異なるプロセッサにより処理されるような手段が与えら れたもの。 ４２．請求項３９、または４０、または、４１に記載の装置において、 スーパーサブエリア内の基準点と特徴の各辺との垂直距離を計算するための手段 、上記の基準点からの制限距離を計算するための手段、計算された垂直距離と制 限距離を比較するための手段、及び計算された垂直距離と制限距離の比較結果論 理的組み合せに基づき、特徴によるスーパーサブエリアの包含度を評価するため の手段を含み、制限距離は、それが特徴の辺と基準点との距離より大きい場合、 辺がスーパーサブエリアに交差不可能であるとされるもの。 ４３．請求項４２に記載の装置において、各スーパーサブエリアが長方形であり 、スーパーサブエリアの各コーナーについて、特徴の各辺に対する制限距離を計 算するための手段が与えられ、制限距離は、スーパーサブエリアの中心と各々の 特徴の辺に平行に引かれ、各々のスーパーサブエリアのコーナーを通過する線と の距離を意味するもの。 ４４．請求項１から４３のいずれか−に記載の装置において、特徴が、特徴の位 置と方向を定義する幾何学属性に関して記述され、上記装置が、更にツリーの基 部に対応するルート・ノード、ツリーの枝分かれ点に対応するブランチ・ノード 、更に、ツリーの個々の技の末端に対応するリーフ・ノード階層的ツリー構造に よりデータを格納するデータベース、平行に配列したオブジェクト・プロセッサ を持つ１個の変換プロセッサ、並びに、データベースからオブジェクト・プロセ ッサにデータを読み出し、１ノードから１データ・プロセッサヘのデータ読み出 しを可能にするコントローラを含んでおり、上記ツリーの各ノードは、各々の物 体を記述するデータを格納し、リーフ・ノードは、各々の物体に貢献する１つ以 上の特徴を格納し、ルート・ノードとブランチ・ノードは、他の物体への１つ以 上のポインタと、ポインタで指す物体に対する指された物体の相対位置と方向を 定義する変換データを格納し、これにより、ツリー構造内の連続する位置は、モ デルの更に詳細な連続する部分に関するデータを格納する。上記データ・プロセ ッサにおいて、各々のデータ・プロセッサは、ツリーのどのノードから読み出さ れたデータをも受け入れるよう改良され、オブジェクト・プロセッサは、各々の 変換データを共通の座標空間に変換し、ポインタからのポインタデータ読み出し にはポインタと変換されたデータをコントローラに返し、オブジェクト・プロセ ッサは、特徴の幾何学属性を変換し、特徴からの読み出しには、変換した属性を 更なる処理のために出力し、コントローラは、ツリーの基部に対応するノードに 格納されたデータを読み出し、引続き、オブジェクト・プロセッサから返された ポインタにより固定されるツリーのノードに格納されたデータを読み出すように なっているもの。 ４５．表示面上にイメージを投映し、既定の視点から既定領域の想像上の視平面 を通して表示面を見るイメージ映写システムと共に使用されるイメージ・ジェネ レータであって、各イメージが対応する表示ピクセル列からなる−連のラスタ走 査線として投映され、イメージ・ジェネレータは、ワールド空間に関連づけて特 徴を定義する幾何学属性データと、特徴の特性を定義する非幾何学属性データに よりモデルを記述するモデル・データベース、ワールド空間におけるモデルの視 点位置を決定するための手段、ワールド空間の幾何学属性データを視点空間の幾 何学属性データに変換するための手段、及び、変換された幾何学属性データと非 幾何学属性データから表示面上に表示されるイメージデータを計算するための手 段を含み、上記イメージデータは、視点からのモデルの外見に矛盾しないように なっており、上記イメージデータ計算手段は、以下の手段から構成される； ａ．視平面領域をサブエリアの配列に分割するための手段。各サブエリアは、既 定のピクセル群か映写される部分の表示面と、形、面積において対応するサブエ リアが表示面へ映写されるように醒列された４つのコーナー座標により定義され るもの。 ｂ．各サブエリア内の１個以上の標本点の位置を定義するための手段、各標本点 の位置は、各々のサブエリアのコーナーを参照して定義されるもの； ｃ．各標本点の変換された幾何学特徴属性と位置から、各特徴により覆われる標 本点を決定するための手段、ｄ．各標本点について、その標本点を包含する１個 以上の特徴に対する非幾何学属性データを格納するための手段、ｅ．格納された 属性データから、各ピクセルについて、イメージ映写システムヘの出力を生成す るための手段。 ４６．請求項４５に記載のイメージ・ジェネレータにおいて、各サブエリアの辺 が線形であるもの。 ４７．請求項４５、または４６に記載のイメージ・ジェネレータにおいて、 各サブエリアの面積が、複数のピクセル行と複数のピクセル列からなる長方形の ピクセル配列に対応するもの。 ４８．請求項４５から４７のいずれか−に記載のイメージ・ジェネレータにおい て、 １ピクセル当り複数個の標本点からなるもの。 ４９．請求項４５から４９のいずれか−に記載のイメージ・ジェネレータにおい て、 属性格納手段が、各標本点を覆う１個の不透明特徴と１個以上の半透明の特徴に 対する属性データを格納するための手段を含むもの。 ５０．請求項４５から４９のいずれか−に記載のイメージ・ジェネレータにおい て、 イメージ映写システムヘの上記出力生成のため、ピクセル出力生成手段が、ピク セル近傍に分布する所定の標本点群からの格納属性データを累算、加重するため の手段を含むもの。 ５１．ワールド空間において定義される複数の特徴からなるワールド空間モデル の、表示スクリーン上へのイメージを生成するための装置であって、上記モデル は、光点と非光点の特徴を含み、ワールド空間において定義された視点から観察 されるようになっており、上記の装置は、以下の手段を備える； ａ．各校点特徴により占有されるスクリーン空間における有限領域を計算するた めの手段、 ｂ．光点特徴の輝度を計算するための手段、ｃ．視点から見える各光点に対する 半透明度を計算するための手段、上記計算された半透明度は計算された輝度の関 数であるもの；ｄ．光点特徴の最終的に計算された輝度に適切である、表示装置 に対する出力を生成するための手段。 ５２．請求項５１に記載の装置において、輝度計算手段は、視点から光点の距離 以上の距離の関数として、光点特徴の輝度を計算するもの。 ５３．請求項５１、または５２に記載の装置において、非光点特徴の半透明度を 決定するための手段、表示スクリーン全体に分布する複数の標本点のスクリーン 空間位置を定義するための手段、特徴のみが視点から槻察される場合に、その特 徴に占有される可能性があるスクリーン空間の領域を決定するための手段、各標 本点のスクリーン空間における位置占有する視点に最も近い不透明特徴とより近 くにある半透明の特徴含む属性を格納するための手段を含み上記出力生成手段は 、各標本点に格納された属性に適当な、表示装置への出力を生成するもの。 ５４．請求項５３に記載の装置において、上記格納手段が、半透明性スタックか ら構成され、複数個のピクセルからなるラスタで表示される光点を記述するデー タは、非光点特徴を記述するデータと共に、視点からの距離順に、半透明性スタ ックに格納され、出力生成手段は、以下の方程式に従い、各標本点に対し出力を 生成する； Ｒ＝ｃＴＯ・ＲＯ＋ｃＴ１・Ｒ１十．．．ｃＴＮ・ＲＮＧ＝ｃＴＯ・ＧＯ＋ｃＴ １・Ｇ１＋．．．ｃＴＮ・ＧＮＢ＝ｃＴＯ・ＢＯ＋ｃＴ１・Ｂ１＋．．．ｃＴＮ ・ＢＮ但し、Ｒ，Ｇ，Ｂは、それぞれ、赤色、緑色、青色の出力であり、ｃＴＮ は、格納手段により、視点からの距離順で格納されたＮ番目の特徴の累算半透明 率であり、 ＲＮは、格納手段により、視点からの距離順で格納されたＮ番目の特徴の赤色成 分であり、 ＧＮは、格納手段により、視点からの距離順で格納されたＮ番目の特徴の緑色成 分であり、 ＢＮは、格納手段により、視点からの距離順で格納されたＮ番目の特徴の青色成 分である。 ５５．請求項５４に記載の装置において、半透明スタックに格納可能なラスタで 表示される光点の最大数を制限するための手段から構成されるもの。 ５６．請求項５５に記載の装置において、半透明スタックの光点の最大数を１に 制限するための手段を含むもの。 ５７．請求項５３から５６のいずれか−に記載の装置において、カリグラフィッ ク的に投映される光点としてイメージ内に含まれるカリグラフィック光点を表す よう意図された特徴を、他の特徴と区別するためにフラグを立てるようにしてお り、上記装置は、更に、全ての非カリグラフィック光点が読み出された後、視点 から近いものから遠いものの順で、カリグラフィック的光点特徴を格納手段に読 み出すための手段、各カリグラフィック光点を覆うカリグラフィック光点の減衰 率を計算するための手段で、減衰率が、少なくとも、カリグラフィック的光点よ りも視点近くにある、格納手段に格納された特徴の半透明度を説明するために計 算されたものから構成されるもの、各カリグラフィック光点に覆われる全ての標 本点に対する減衰率を計算するための手段、累算された減衰率の関数であるカリ グラフィック光点輝度出力を、各カリグラフィック光点について生成するための 手段で、カリグラフィック光点投映装置を制御するカリグラフィック光点ストア に、輝度出力が与えられるものを含むもの。 ５８．請求項５７に記載の装置において、カリグラフィック光点に対するアパー チャを決定するための手段、カリグラフィック光点に対し減衰因数を決定するた めの手段、光点に対する内在輝度を、アパーチャの値で除算した減衰因数として 計算された数で割ることによって得られるカリグラフィック光点に対する表示毎 度を計算するための手段を含み、上記アパーチャの数は、カリグラフィック光点 により覆われる可能性がある標本点の数に等しく、上記減衰因数は、覆われた各 標本点にあるカリグラフィック光点の減衰率の合計であるもので、各標本点にお ける減衰率は、モデルの世界で視点に達するカリグラフィック光点として表され る特徴により発せられる光の計算された比率であるもの。 ５９．ワールド空間座標により定義され、ワールド空間において定義される視点 から観察される複数の特徴からなるワールド空間モデルのイメージを、表示スク リーン上に生成するものであって、上記モデルは、ワールド空間における光点の 位置を決定するワールド空間座標により定義される光点特徴を含む装置は、以下 の手段を備える； ａ．各光点のスクリーン空間座標を計算するための手段；ｂ．各光点に対するス クリーン空間領域を、ワールド空間における光点と視点の距離以上の距離の関数 として計算するための手段；ｃ．各光点の輝度を計算するための手段：ｄ．表示 スクリーン全体に分布する複数個の標本点のスクリーン空間での位置を定義する ための手段； ｅ．各光点について、計算された光点領域内に存在する標本点を決定するための 手段； ｆ．計算された光点輝度と計算された光点領域内に存在する特定の標本点に適切 な各光点に対し、表示装置への出力を生成するための手段。 ６０．請求項５９に記載の装置において、上記年度計算手段が、視点と光点の距 離以上の距離の関数として輝度を計算するもの。 ６１．請求項５９、または６０に記載の装置において、１個以上の光点特徴がカ リグラフィック的に表示される、装置は、更に、各標本点が位置する領域内のカ リグラフィック光点の減衰率を計算するための手段、及び、カリグラフィック光 点の領域内に位置する全ての標本点にあるカリグラフィック光点の減衰率の合計 に対する表示輝度と光点の内在輝度を計算するための手段を含み上記減衰率は、 標本点を覆い、カリグラフィック光点よりも視点近くにある他の全ての特徴の存 在を説明するために計算されるもの。 ６２．請求項６１に記載の装置において、上記輝度計算手段が、より視点近くに ある特徴による覆い隠しは無いものとの仮定で、各光点の内在輝度を計算するも のであり、装置は、更に、各カリグラフィック光点について、半透明度を計算す るための手段、及び、より視点近くにある、全ての不透明、または、半透明の特 徴により、減衰される内在輝度の関数であるカリグラフィック光点に対する表示 輝度を計算するための手段を含み、上記半透明度は、計算された内在輝度の関数 として計算されるもの。 ６３．請求項６２に記載の装置において、全ての非カリグラフィック光点処理後 に、カリグラフィック光点特徴を処理するための手段を備え、該カリグラフィッ ク光点処理手段は、各標本点を覆うカリグラフィック光点の減衰率を計算するた めの手段、各カリグラフィック光点により覆われる全ての標本点に対し計算され た減衰率を累算するための手段、及び、各カリグラフィック光点について、累算 した減衰率の関数である能書光点表示輝度出力を生成するための手段を含み、上 記減衰率は、少なくとも、カリグラフィック光点よりも視点近くにある特徴の半 透明度を説明するために計算され、上記光点表示輝度は、カリグラフィック光点 投映装置での使用のために格納されるもの。 ６４．請求項６３に記載の装置において、カリグラフィック光点に対するアパー チャを決定するための手段、カリグラフィック光点に対する減衰因数を決定する ための手段、及び、光点の内在輝度と、減衰因数をアパーチャで除算することで 算出される数を掛けることによって、カリグラフィック光点に対する表示輝度を 計算するための手段を含み、上記アパーチャの数は、カリグラフィック光点によ り覆われる可能性がある標本点の数に等しく、上記減衰因数は、覆われた各標本 点におけるカリグラフィック光点の減衰率の合計であり、各標本点における減衰 率は、モデルとなる世界において視点に達するであろうカリグラフィック光点と して表される特徴により、発せられる光の計算された比率であるもの。 ６５．請求項６３、または６４に記載の装置において、上記減衰率計算手段が、 各標本点に対する半透明スタック、各標本点を覆う最も近くにある不透明特徴、 より近くにある非カリグラフィック光点特徴を識別するデータを半透明スタック 内に格納するための手段、各標本点に対するベール・ストア、各カリグラフィッ ク光点の視点との距離と半透明性スタックに格納される特徴の視点との距離を比 較するための手段、及び、カリグラフィック光点に対して累算された半透明度を ベール・ストアに格納するための手段を備え、上記累算された半透明度は、半透 明性スタックに格納されるより視点近くの特徴により、カリグラフィック光点の 減衰率を表すものであるもの。 ６６．請求項６５に記載の装置において、各衝突される可能性のある標本点に対 し計算される減衰率とアパーチャが、その他の衝突される標本点のものと組み合 わされ、光点ストアに出力されるもの。 ６７．スクリーン上に表示するためのイメージ・データを生成するイメージ・ジ ェネレータのサブシステムの計算負荷を被数のプロセッサへ分配するための装置 であって、以下の手段を含むもの；ａ．スクリーンをサブエリアに分割するため の手段、各サブエリアは、１個以上の表示ピクセルを包含し、各プロセッサは、 １度に１サブエリアに関するデータを処理するよう改良されたもの；ｂ．プロセ ッサに処理タスクを分配し、その結果、すぐ隣合ったサブエリアに関するデータ を異なったプロセッサにより処理するための手段。 ６８．請求項６７に記載の装置において、表示されるイメージに部分的に寄与す る連続する各特徴を記述するデータを読み出すための手段を含み、各特徴を記述 するデータは、各プロセッサに平行に読み出される上記手段において、各プロセ ッサにより処理されるサブエリアのスクリーン空間座標を選択する手段、特徴が 選択されたサブエリアに寄与するか否かを決定するために、プロセッサに読み込 まれる特徴データを分析するための手段、及び、選択されたサブエリアに寄与す る特徴を識別するデータを出力するための手段を備えるもの。 ６９．請求項６８に記載の装置において、スクリーンをスーパーサブエリアに分 割するための手段、各スーパーサブエリアに寄与する特徴を固定するデータを格 納するための手段、及び、スーパーサブエリア格納手段からデータを１つづつ読 み出すための手段を含む、上記各スーパーサブエリアは、サブエリアの２次元的 な配列を包含するもので、上記選択手段は、既知の方法で、スーパーサブエリア の境界に照らし合わせてサブエリアのスクリーン空間座標を選択するもの。 ７０．請求項６７、６８、または６９のいづれかに記載の装置において、 ２つのプロセッサを含み、各サブエリア行、または列のすぐ隣合ったサブエリア は異なるプロセッサにより処理されるもの。 ７１．請求項６７、６８、または６９に記載の装置で、４個のプロセッサを含み 、各プロセッサは、どのサブエリア行、または列においても、４つの連続するサ ブエリアの内１サブエリアのみを処理するもの。 ７２．複数の特徴により定義されるワールド空間モデルイメージの表示を可能に するため、その複数の特徴を記述するデータをスキャン変換するための装置であ って、各特徴は複数のまっすぐな辺により定義される境界を持ち、各辺はスクリ ーン空間座標において線方程式により定義され、上記装置は、スクリーンを複数 個のサブエリアに分割するための手段と、１個の特徴に包含される１個のサブエ リアを分析するための手段を含み上記遮蔽分析手段が、以下の手段を備える。 ａ．上記の１サブエリア内の基準点と上記１特徴の各辺の垂直距離を計算するた めの手段、 ｂ．基準点からの制限距離を計算するための手段、制限距離とは、基準点からの 垂直距離にある特徴辺が制限距離よりも長い場合、その辺がサブエリアを横切る ことが不可能な距離として定義されている、 ｃ．計算された垂直距離と制限距離を比較するための手段；ｄ．計算された垂直 距離と制限距離の間の比較結果の論理的組み合せに基づき、特徴により、サブエ リアの包含を評価するための手段。 ７３．請求項７２に記載の装置において、各サブエリアが長方形であり、特徴の 各辺についての制限距離をサブエリアの各コーナーから計算するための手段が備 えられ、制限距離は、サブエリアの中心からの垂直距離と各特徴の辺に平行であ り、サブエリアの各コーナーを通過する直線との垂直距離として定義されている もの。 ７４．請求項７３に該当する装置において、特徴の各辺が、 ｄ＝ｅ・ｘ＋ｆ・ｙ＋ｇ の形式の線方程式により定義され、サブエリアの中心と特徴の辺との垂直距離を 、その線方程式にサブエリアの中心のスクリーン空間座標を代入することにより 計算するための手段が備えられるもの。 ７５．請求項７４に記載の装置において、特徴辺への制限距離が、 制限距離＝｜ｅ・ａ｜＋｜ｆ・ｂ｜ で導かれるもの； 但し、｜ｅ・ａ｜は、ｅ・ａの絶対値であり、ａとｂは、それぞれサブエリアの スクリーン空間における幅の１／２と高さの１／２である。 ７６．請求項７５に記載の装置において、特徴辺の線方程式の係数をｎで除算す ることにより、正規化するための手段を備えており、 但し、 ｎ＝ｓｑｒｔ［（Ｘ２−Ｘ１）２＋（ｙ２−ｙ１）２］で、（Ｘ１，ｙ１）と（ Ｘ２，ｙ２）は、上記線方程式により記述される辺上にある特徴のスクリーン空 間座標であり、装置は更に、サブエリアの中心から上記線方程式により記述され る特徴の辺を直接得るため、正規化された線方程式にサブエリアの中心座標を代 入するための手段を備えるもの。 ７７．請求項７６に記載の装置において、２つの線関数、 Ｆ（ｘ，ｙ）＝Ｅ（ｘ，ｙ）＋ｄｃｒｉｔＧ（ｘ，ｙ）＝Ｅ（ｘ，ｙ）−ｄｃｒ ｉｔを得るために、特徴の辺を記述する線方程式Ｅ（ｘ，ｙ）を初期化するため の手段（但し、ｄｃｒｉｔは、線方程式Ｅ（ｘ，ｙ）により記述される辺につい て計算される制限距離である）及び、線方程式が、サブエリアと交差するか否か を決定するために、上記の２つの初期化された辺関数の符合を算出するための手 段を含むもの。 ７８．請求項７４、７４、７６、または７７のいずれかに記載の装置において、 各特徴の辺について、算出された垂直距離が、マイナス制限距離より小さければ 第１のアウトコードを、マイナス制限距離と同じか、それより大きければ第２の アウトコードを、負符号を付した制限距離と同じか、それより小さければ第３の アウトコードを生成する手段、特徴の全ての辺に対しアウトコードを組み合わせ るための手段、その特徴がサブエリアに少なくとも部分的に含まれるか否かを決 定するために生成するための手段を含むもの。 ７９．請求項７８に記載の装置において、アウトコードが２ビットからなり、組 み合せ手段が、−方のＡＮＤゲートが各アウトコードの第１ビットを受け、他方 が第２ビットを受ける１対のＡＮＤゲートからなり、上記ＡＮＤゲートは、サブ エリアが、少なくとも部分的に特徴に覆われるか否かを示す２ビットの出力を生 成するもの。 ８０．イメージをスクリーン上に表示するモデルを記述するデータを処理するた めの装置であって、モデルは、各特徴が特徴の位置と方向を各特徴により定義さ れる幾何学属性と、特徴の特性を定義する非幾何学的属性において記述される複 数の特徴からなり、上記イメージは、ワールド空間における、視点からのモデル の景観を表すよう意図されている上記装置は、以下の装置から構成される；ａ． モデルのデータを、ツリーの基部に対応するルート・ノード、ツリーの分枝点に 対応するブランチ・ノード、ツリーの各枝の末端に対応するリーフ・ノードから なる階層的ツリー構造で格納するデータベース、ツリーの各ノードは、それぞれ の物体を記述するデータを、リーフ・ノードは、各物体に貢献する１つ以上の特 徴を、ルート・ノードとブランチ・ノードは、他の物体への１つ以上のポインタ と、ポインタで指す方の物体に対する指される物体の格対的な位置と方向を格納 する、これにより、ツリー構造内の連続する位置は、モデルの更に詳細な連続す る部分に関するデータを格納する。 ｂ．平行に配列されたオブジェクト・プロセッサを有する変換プロセッサ、 ｃ．データベースから、オブジェクト・プロセッサにデータを読み込む結果、１ つのノードから１つのデータ・プロセッサにデータを読み出すコントローラ、 各データ・プロセッサは、ツリーのあらゆるノードから読み出されたデータを受 け入れるよう改良されており、上記オブジェクト・プロセッサは、ポインタ・デ ータが読み出されると、各変換データを共通の座標空間に変換し、ポインタと変 換済データをコントローラに返し、上記オブジェクト・プロセッサは、特徴が読 み出されると、その特徴の幾何学的属性を変換し、変換済の属性を更なる処理へ 出力し、上記コントローラは、ツリーの基部に相当するノードにデータを読み出 し、続いて、上記オブジェクト・プロセッサから返されるポインタによって識別 されるツリーのノードに格納されるデータを読み出すよう改良されているもの。 ８１．請求項８０に記載の装置において、オブジェクト・プロセッサが群配列さ れ、各群がローカル・コントローラを通じてバスと連絡するようにしており、上 記ローカル・コントローラは、各オブジェクト・プロセッサ群の内、１個以上の オブジェクト・プロセッサが使用されていない場合のみ、バスから物体のデータ を受け入れ、上記ローカル・コントローラは、バスに送られる信号により、オブ ジェクト・プロセッサ群の１個のオブジェクト・プロセッサによる処理のために 物体データを受け付けた時を示すようにしたもの。 ８３．請求項８１、または８２に記載の装置において、物体のデータが、疑似ラ ンダム（ｐｓｅｕｄｏ−ｒａｎｄｏｍ）に、オブジェクト・プロセッサに分配さ れるもの。 ８４．請求項８１、８２、または８３に記載の装置において、各オブジェクト・ プロセッサにオブジェクト・データを読み出す処理の完了を示すための手段を備 えているもの。 ８５．請求項８０から８４のいずれかに記載の装置において、各オブジェクト・ プロセッサは、ポインタと物体を記述する特徴データを受け入れた後、先ず、ポ インタ・データを処理し、そのポインタをコントローラに返し、次に特徴データ を処理するように改良されたもの。 ８６．請求項８０から８５のいずれかに記載の装置において、各物体のオブジェ クト空間における境界天球を定義するための手段、表示スクリーンの境界をオブ ジェクト空間に投影するための手段、並びに、物体の境界天球がオブジェクト空 間の表示スクリーンの境界の外側にある場合、その物体を記述するデータを廃棄 するための手段を備えるもの。