JPH07501162A - ３ｄコンピュータグラフィック用可視性計算の改善 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ３Ｄコンピユータグラフイツク用可視性計算の改善発明の分野 本発明はコンピュータグラフィックに関するものであり、特に、一般に３Ｄシス テムにおいて、改善された隠面消去を好適に行うための可視及び／又は不可視表 面の効率的な決定に関するものである。

発明の背景 可視表面検出は、３Ｄグラフイつて最も基本的な操作のうちの−っである。可視 表面検出は、観察者が直接見ることができる表面の像を発生させるのに利用され る。近年、可視表面検出は、表面間のエネルギ相互作用を計算するために、ラジ オシティ（ｒａｄｉｏｓｉｔｙ　（相互反射）の計算にも採用されている。

可視表面検出の基準ストラテジは、可視表面をパッチエレメントに分割し、これ らのエレメントの空間的な関係を比較することである。このストラテジを用いる に当たり、表面の可視性を、表面が詳細に解析されるまで決定することができな い。多くの技術が、この問題に取り組むために開発されているが、精密な表面解 析を要求するか、又は場面に種々の制限を課するものとして理想的なものは現代 まで存在しない。

現在の技術の限界は、可視表面の計算速度に重大な影響を及はしつる。場面が複 雑な場合、多くの表面か見えなくなるおそれかある。しかしなから、像の発生は 通常、各表面エレメントを詳細に解析する必要かあるため減速される。

同様な限界は、ラジオシティの計算の効率に重大な影響を及ぼす。近年、ラジオ シティの計算は、各表面エレメント対間の可視性を精密に計算する必要があるた め、非常に低速である。

また、ラジオシティの計算を、互いに明らかに可視又は不可視の表面エレメント をより簡単に計算できる場合には、大幅に軽減されることかできる。

初期の可視表面技術は主に、閉塞する表面原素を発見するために、種々の分類方 式に適用していた。しかしながら、ハードウェア技術か進歩するにしたがって、 現在では通常多数の高速メモリを使用することにより、分類及び比較の必要か減 少している。このメモリは、ＢＳＰツリーのような対象データを記憶するのに用 いることができる。このメモリを、Ｚバッファのように、深さ及び表面投影デー タを記憶するのにも用いることができる。Ｚバッファ法は簡単であり、かつ、非 常に低速の成長速度を有する。しかしなから、Ｚバッファ法には、すへてのパッ チを各画素に投影することによる各画素における深さ評価及び比較かなお要求さ れ、この理由はこれらの可視性か未知だからである。

ＢＳＰツリー法は、場面か静的な場合、ＢＳＰツリーの整列走査により深さ整列 を行うのには一般に十分である、という利点を有する。しかしなから、ＢＳＰツ リー法にも、各経路の走査変換が要求される。さらに、この方法には、走査中の 対象か移動するごとに、ＢＳＰツリーを再計算する必要がある。

全体的に不可視なエンティティの詳細な深さ解析を回避するだめの主なストラテ ンか二つある。一方のス１〜ラテジは、可視性の変化が表面の輪郭のエツジにの み発生しうるような特性に利用される。内在するエツジすなわちパッチの可視性 の計算を、最初にこれらの表面の輪郭のエツジとこれらの内在するエツジとを比 較することにより軽減することができる。

他方のストラテンは、場面の不可視の一致に用いることができる。これらの技術 を、エツジが最後の走査線において不可視の場合、エツジか走査線上で不可視の 状態でありそうな特性に利用する。したがってこのようなエツジを、不要な深さ 比較を回避するために、特別にみなすことができる。

上述したストラテンが可視性の計算を幾分軽減させることができるとしても、こ れらのストラテンには限界がある。輪郭指向技術（ｃｏｕｎｔｅｒ−ｏｒｉｅｎ ｔｅｄ　ｔｅｃｈｎｉｑｕｅ）によれば、専ら凸状又は非突出表面からなる状況 においてのみ走査することができる。

輪郭向き付けの近似及び走査線の近似も、可視性の計算を軽減させる能力に限界 かある。輪郭向き付けの近似では、エツジを、不可視の場合でさえも輪郭のエツ ジに対してテストする必要がある。走査線の近似では、走査線ごとのすべての不 可視エツジのセグメントを記憶させる必要がある。これらのセグメントも、セグ メントが存在する画素と深さ比較する必要がある。遂には、これらすべての技術 には、何らかの分類又は検索か必要本発明の目的は、可視性の計算を行うに当た り改善された方法を用いることにより、従来技術に関連する問題をほとんど克服 又は改善することである。

本発明の好適例は、イメージを発生させる多次元コンピュータの生産に要求され る、すなわち多次元データを、少なくとも１次元少ない多次元データに減少させ るのに要求される可視性計算の複雑度を減少させるのに当たり、以下の工程を有 することを特徴とする可撓性姿勢計算の複雑度減少方法。

（１）（それ自体既知の）閉塞すなわち不可視性関係計算を、計算されるべき選 択された視点から複数の表面で実行する前に、これらの視点を群に分割する。

（２）前記表面の選択されたものの幾つかに対して、前記選択された表面が、 （ａ）常に閉塞されていない表面、常に隠された表面、又はそれ以外の表面であ るか、 （ｂ）常に閉塞されていない表面又はそれ以外の表面であるか、 又は、 （Ｃ）常に隠された表面又はそれ以外の表面であるか、どうかを決定する。前記 それ以外の表面を、閉塞されていない又は隠されていないかどうかを確実に決定 できない表面とする。

（３）常に閉塞されていない又は常に隠された前記閉塞すなわち不可視性関係計 算を免除する。

（４）前記それ以外の表面の記録を保持する。

（５）前記閉塞すなわち不可視性関係計算を前記それ以外の表面で行うことであ る。

本発明の他の好適例は、３次元的な抽象又は物理的表面からなる環境における計 算に関連する可視性を減少させるに当たり、以下の工程を有することを特徴とす る可視性減少方法。

（１）（それ自体既知の）可視性計算を行う前に、幾つか又はすへての視点すな わち存在しうる視点の発生を、視点群に分類する。

（２）一つ又はそれ以上の（それ自体既知の）表面を、この表面すなわち視点群 に関連する表面エレメントの同時的な投射を発生させるために、規定する。

（３）選択された表面に対して、及び各視点群に対して、これらの選択された表 面すなわちこれらの表面エレメントが、これらの投射写像すなわち前記投射表面 への同時的な投射を計算かつ比較することにより、前記視点群に対して常に不可 視であるかどうかを決定する。

（４）前記視点群に対して常に不可視である幾つかの又はすべての表面すなわち 表面エレメントを、実際の可視性すなわち前記群中の幾つかの又はすへての視点 に対する計算に関連する可視性中で無視又は特別に取り扱うことである。

本発明の他の好適例は、可視性、ラジオシティ又は３次元的な抽象又は物理表面 からなる環境における計算に関連する可視性を減少させるに当たり、以下の工程 を有することを特徴とする可視性減少方法。

（１）（それ自体既知の）可視性計算を行う前に、幾つか又はすべての視点すな わち存在しつる視点の発生を、視点群に分類する。

（２）一つ又はそれ以上の（それ自体既知の）表面を、この表面すなわち視点群 に関連する表面エレメントの同時的な投射を発生させるために規定する。

（３）前記投射表面のそれぞれを規則的又は不規則的な格子に分割する。

（４）前記格子に投射を記憶するために、コンピュータのメモリを組織するデー タ構造を規定する。

（５）選択された表面すなわち表面エレメントそれぞれに対して、及び各視点群 に対して、前記表面すなわち前記表面エレメントを前記投射表面に投射し、投射 下にある格子セルを計算する。前記群の視点間の取りうる最長距離及び前記コン ピュータを分類する。

（６）前記表面の各バッチエレメントに対して、前記パッチエレメントが投射す ることができる前記格子セルを決定し、前記格子セルに記憶された深さと、前記 パッチエレメントと前記視点群との間の取りつる最長距離を比較し、前記パッチ エレメントが常に他の表面によって閉塞されているかどうかを決定するようにし てことである。

図面の簡単な説明 本発明の好適例を図面を参照して詳細に説明する。

図ＩＡ及び図ＩＢは、二つの視点階層を示す。

図２は、任意の視点における投影を示す。

図３は、投影ボックスとファジィ投影ボックスとの間の関係を示す。

図４は、ファジィ領域及び非ファジィ領域の形成を示す。

図５Ａ、図５Ｂ及び図５Ｃは、フロント対向（ｆｒｏｎｔ−ｆａｃｉｎｇ）表面 及びこれに相当するファジィ領域及び非ファジィ領域を示す。

図５Ｄは、視点境界ボックスに対して完全に隠れていない点を示す。

図５Ｅは、視点境界ボックスに対して完全に隠れた点を示す。

図６Ａ〜６Ｄは、完全に不可視なパッチの検出を示す。

図７Ａ及び７Ｂは、完全に可視／隠れていないパッチの検出を示す。

図８Ａ〜８Ｄは、非ファジィ領域の走査変換を示す。

図９Ａ〜９Ｄは、ファジィ領域の走査変換を示す。

図１Ｏは、シャッセとファジィアレイとの間の写像を示す。

図１１Ａ及び図１１Ｂは、フロント対向表面領域の視野を示す。

図１２Ａ、図１２Ｂ及び図１２Ｃは、表面領域の投影の切り口平面の視野を示す 。

図１３Ａ、図１３Ｂ及び図１３Ｃはそれぞれ、好適実施例をテストするのに用い られる１個、２個及び４個のルームモデルを示す。

図１４は、エツジのファジィ領域の直接計算を示す。

図１５は、生立方体のピラミッド構造を示す。

補遺ｌは、視点境界ボックスに対してフロントに対向するパッチの検出を記載す る。

補遺２は、境界エツジ及びパッチのファジィ範囲の計算を記載する。

補遺３は、非ファジィ領域の計算を記載する。

補遺４は、ファジィ領域の走査変換を記載する。

補遺５は、アクセスを高速にするためのシャッセの使用及びパッチのファジィ範 囲内でのファジィエレメントの書込みを記載する。

補遺６は、エツジのファジィ領域の直接計算を記載する。

補遺７は、半立方ピラミッドのパッチの走査変換を記載する。

補遺８は、参考文献のリストを記載する。

本発明を実行する最良及び他の方法 好適実施例は３次元コンピュータグラフィック像を計算する種々の方法に関する ものであり、一般に「ファジィ投影法」と総称される。

本実施例では、平面方向の一つ又はそれ以」二の視点に対するエンティティの投 影を写像するようにする。本実施例では、すべてのエンティティの投影を含む領 域及びそれぞれ並びにすべての投影内の領域を計算するようにもする。本実施例 で説明する空間位置、時間及び光学的特性を、置換がグラフィック像のエンティ ティの数学的な関係に影響を及ぼさない場合には、他の物理的又は抽象的な変数 に置き換えることができる。

これらの実施例を議論する前に、３Ｄグラフイツクにおいて用いられる種々の用 語を紹介するとともに、変数を規定するのが有効である。

最初に、図ＩＡ、ＩＢ及び２を参照して、図面において眼球で示される観察者を 、周囲の物体の可視性が得られる場合には、抽象的かつ無次元の観察者とする。

観察者がら投影される光か不透明な物体に遮られない場合、点は観察者にとって 可視となる。−Å以上の観察者がいっても存在することができ、各観察者はその 時間にわたって移動又は回転してもよい。視点ＶＰを空間的な点とし、かつ、瞬 時における観察者の方位とする。視界ベクトルｖｖを、視点ｖＰから観察される 点ＰＯへのベクトルとする（図２参照）。

数個の視点ＶＰを、これらの視点■Ｐか共有するある特性により、互いに分類す ることができる。視点の関連する群は、より高いレベルの群を順に形成すること ができる。このような合併を置き換えて、視点の階層を形成することができる。

現時点の群を、現時点て考察される視点■Ｐの群とする。図ＩＡにおいて、視点 ＶＰ、、　ＶＰ２．　ｖｐａ及びＶＰ４はそれぞれバスＰＡ、上に存在するとと もに、時刻１．２．３及び４における視点を表し、これらを一群と考えることか できる。視点ＶＰ５〜■Ｐ、に対しても同様である。

視点の各群を、群座標系Ｃ８と呼ばれる座標系に関連させる。

視点ｖＰの群の視点境界ボックスＢＢは、これらの視点を包囲する最小の正四角 柱であり、この四角柱の境界は群座標系の軸に平行である。視点の群の位置すな わち発生を正確に規定しない場合、関連の視点境界ボックスを、これらの視点に よって占領されるような空間を包囲する四角柱としなければならない。視点の群 を、平面又は点上に置く。このような場合、視点境界ボックスを平面又は点に低 下させてもよい。視点境界ボックスＢＢ中のすへてのありうる視点ｖＰから常に 可視である場合、点ＰＯは視点境界ボックスＢＢから完全に可視である。逆に、 視点境界ボックスＢＢ中のすへてのありうる視点ｖＰの視野から隠れている場合 、点ＰＯは視点境界ボックスＢＢから完全に不可視である。図ＩＡにおいて、視 点■Ｐ１〜ＶＰ４は視点境界ボックスＢＢ、中に存在し、かつ、視点ＶＰ５〜Ｖ Ｐｔは視点境界ボックスＢＢ、中に存在する。視点境界ボックスＢＢ、及びＢＢ ２を第ルベルの境界ボックスと見なすことができる。視点境界ボックスＢＢ、及 びＢＢ、を結合する場合、第２レベルの境界ボックスＢＢ２を形成する。視点境 界ボックスを直方体又は立方体とするだけでなく、楕円面、球又は任意の容量と することもできる。

視点群を低下させるとともに、単一の視点を含むようにしてもよい。このように して、通常の視点群に適用しうるすへての方法を、単一の視点にも適用しうる。

この場合、視点境界ボックスＢＢを、視点■Ｐに一致する点に低下させる。

図ＩＢにおいて、異なる時刻における複数の観察者を示す。

ある群の一人の観察者の経路ＰＡ、を、ある時刻における２点の位置の間で延在 させて示す。ＶＰ、は時刻ＮＪにおける視点を、ｖｐ、は時刻「２」における視 点をそれぞれ表し、Ｖｈは時刻「ｌ」における視点境界ボックスＢＢ、を有し、 ＶＰ０は視点■Ｐ。

及びＶＰＩの結合した視点境界ボックスＢＢ、を有する。

図２には、視点ＶＰ上に中心があり、現在の群座標系Ｃ８の主軸に平行なエツジ 面を有する直方体プリズムである投影ボックスＢＰを示す。投影ボックスＢＰの ６面を、投影面ＰＦと総称する。各投影面ＰＦは、投影平面ＰＰと総称される平 面上にある。投影平面ＰＰに直交する方向への点ＰＯ，の投影ＰＲは、投影平面 ＰＰと視点■Ｐから点ＰＯ８への視野ベクトル■ｖとの間で交差する。逆に、視 点ＶＰから出る直線を、投影平面ＰＰ上の投影点ＰＲのみに対して直交させるこ とかできるので、この投影平面ＰＰ上の位置も視点■Ｐからの独自の視野方向て 示すことがてきる。

このようにして、 Ｆ＝ｃｏｓ　Ａ”　ｃｏｓ　Ｂ”　Ａ／　（πｒ”　ｒ）となる。

可視空間点ＰＯ，の周囲の領域を可視パッチＰＴとすると、視野ベクトル■■は 可視空間点Ｐ０１を通過して不可視空間点ＩＰに到達し、パッチＰＴによって閉 塞される。

各平面上の投影計算は、この平面に対して直交する方向の文体の像領域の発見と 同一である。投影平面ＰＰに対する物体の投影はしたがって、投影平面ＰＰＯ法 線Ｎに平行な方向の対象の像領域を示す。

視点■Ｐは無指向性でなく、制限された視野領域を存してもよい。したかって、 ある投影面は、部分的に又は全体的に視点ＶＰから観察できないかもしれない。

投影面ＰＦから隠れた領域を、投影面ＰＦと視点ＶＰの視野範囲とを交差させる ことにより得ることかできる。

投影平面ＰＰ上の位置を、投影座標と総称される座標系Ｃ３によって表すことが できる。この座標系Ｃ８の原点は、投影面ＰＦの中心に存在する。この座標系Ｃ ８のｙ軸及びｙ軸はエツジ面に平行であり、Ｚ軸は投影面ＰＦの法線に垂直であ る。

ｙ軸、ｙ軸及びＺ軸はすべて平行であるので、現在の視点ｖＰの群の投影座標系 は同一の目盛係数を存し、したがって投影座標系から同一の視野方向を有する点 は、常に同一の投影座標を存する。

二つの面の上の点を同一位置、例えば投影面ＰＰ上のＰＲに投影する場合、閉塞 が発生する。視点■Ｐよりさらに先の表面上の点は、視点ＶＰにより近い表面が 透明でない限り、視点ｖＰにより近い表面上の点に隠される。このことは、投影 面ＰＰ上の点ＰＲと視点ＶＰとの間の距離によって決まる。

ある群の投影ボックスＰＢの各エツジ面は、各群の座標系Ｃ８の主軸（ｘ、　ｙ 又はＺ）のうちの一つに平行である。主軸に平行なベクトルはせいぜい６方向し か有さないので、これらの面を垂直方向によって６セツトに分類する。

このことを図３に示す。この場合、境界ボックスＢＢ、内に存在する各投影ボッ クスＰＢ、、ＰＢ２及びＰＢ、をそれぞれ有する視点ＶＰ　１．　ＶＰ　２及び ＶＰ３を示す。

投影ボックスＰＢ、〜ＰＢ、上の投影を、エツジか現在の座標系Ｃ３の軸にも平 行である他のボックスに関連させることができる。このようなボックスをファジ ィ投影ボックスＦＢと総称する。

このようなボックスを「ファジィ」と総称している理由は、このようなボックス は、すべての視点からの単一表面（すなわち物体、エンティティ等）の結合され た投影だからであり、この結合された投影は、表面のファジィ像を形成する。投 影ボックスの各面をファジィ投影面ＦＦと総称する。ファジィ投影面ＦＦは、フ ァジィ投影平面ＦＰと総称される平面に存在する。投影座標系を、ファジィ投影 平面ＦＰ及びその上にあるファジィ投影面ＰＦに対して定義することができる。

投影平面ＦＰの投影座標系Ｃ８と同様に、この座標系の原点はファジィ投影面Ｆ Ｆの中心に存在し、軸はそれぞれこれのエツジ面及びファジィ投影面ＦＦの法線 に平行である。

各ファジィ投影平面の投影座標系の目盛係数を、ファジィ投影平面に関連する投 影平面ＰＰの目盛係数と同一に設定することにより、投影平面／面の各組は、同 一方向に対向するファジィ投影平面／面とともに１対ｌの写像を有する。投影平 面／面上の点をしたがって、関連するファジィ投影平面／面に直線的に写像する ことがてきる。

同一の投影座標を有し、したがって同一の視野方向を表す投影平面の組上の点は 、同一の座標を有する関連のファジィ投影平面上の点に写像する。したかって、 投影平面ＰＰと同様に、ファジィ投影平面ＰＰ上の点も唯一の視野方向を表す。

しかしなから、この点は特定の視点に関連しない。

視点ＶＰは視野の制限された領域を有するので、射影平面のある領域を観察する ことかできないおそれかある。ファジィ投影面ＦＦの隠された領域は、すへての 関連する投影面上の対応する領域が隠されている領域である。ファジィ投影面Ｆ Ｆは、すべての関連する投影面上の対応する領域か隠されている場合アクティブ でない。ファジィ投影ボックスＦＢ上の投影を簡単にするために、各ファジィ投 影平面ＦＰを、ファジィアレイＦＡを形成する平行かつ幾分能れた２組の格子線 によって基盤目状にする。ファジィ投影面のエツジ上に格子線か常に存在するよ うにすることにより、これらのファジィ投影面を同一の長方形又は正方形の区画 に分割する。各区画をファジィエレメントＦＢと総称する。各ファジィエレメン トＦＢは、ファジィエレメントＰＨの中心に関連する視野方向を表すとともに、 図２に示すように視野方向の全周によって表された唯一の視野方向の立体角Ａを 表す。

４個に再分割するような他の表現方法を適用することもできる。Ｚバッファの指 向されたすべての操作はしたがって、このような方法の下で操作が変更されるが 、面の規則的な再分割は、本発明の最も好適な実施例と考えられる。

観察環境中の表面を、パッチＰＴのメツシュ（ｍｅｓｈ）によって近似すること ができる。表面をパッチの階層によっても表すことかできる。異なるレベルの階 層を、異なる詳細におけるパッチのメツツユとする。各パッチＰＴを平坦とみな すとともに、多角形によって近似する。視点■Ｐへの表面ＳＵの投影は、パッチ ＰＴのすへての投影領域を結合する領域である。この領域を表面ＳＵの投影領域 ＰＥと総称する。パッチＰＴの投影領域ＰＨがパッチＰＴのイメージ領域を表す ので、表面ＳＬＩの投影領域ＰＨも表面ＳＯのイメージ領域を表す。

パッチを適切に包囲するとともに、エツジか現在の群の座標系の軸に平行である 最小の立方体を、パッチの境界容積と総称する。パッチの最短深さ及び最長深さ を、現在の視点とノ々・フチ上の点との間の最短深さ及び最長深さとする。この 深さは、全考察している投影平面に垂直なＺ座標方向の大きさに相当する。これ らの深さを発見するのは通常困難であるので、視点境界ボックスとパッチの境界 容積との間の最短深さ及び最長深さによって近似する。これらの最短深さ及び最 長深さを、視点境界ボックスの平面による空間を分割し、かつ、どの分割がパッ チの境界容量に存在するかを決定することにより決定することかできる。

このことは図４に示すように、表面のパッチＰＴを、境界ボックスＢＢ、中の点 ｖｐ、、ｖｐ２及びＶＰ、から観察する。各視点ＶＰ、〜ｖＰコを、各視点ｖＰ １〜ｖＰ、に対して異なる方法で、対応する投影面ＰＰＩ〜ＰＦ２に交差するよ うに見える投影領域ＰＥ＋〜ＰＩＥＩに関連させる。

投影面ＰＦ、〜ＰＦｚの同−組へのパッチの投影を、関連するファジィ投影面Ｆ Ｆに写像することができる。すべての写像を含むファジィ投影ボックスＦＢ、の 領域を、パッチのファジィ（結合）領域ＦＲと総称する。その理由は、必然的に この領域ＰＲがファジィだからである。領域ＰＲは、パッチＰＴ、が実際に各投 影ボックスＰＢＩ〜ＰＢ２の対応する領域に投影しているかどうか区別できない 。

パッチの場合と同様に、表面ＳＵのファジィ領域ＰＲを、多数のパッチに対する 表面投影の写像を結合することにより発生させる。したかって、表面ＳＵの各フ ァジィ領域ＰＲはパッチのすべての投影の論理ＯＲであり、かつ、各パッチのフ ァジィ投影はパッチの投影領域の論理ＯＲである。したがって、表面ＳＵのファ ジィ領域ＰＲも、多数のパッチのファジィ投影の論理ＯＲである。ファジィ領域 ＰＲは、現在の視点から見える表面のすべての像の重畳に相当する。

ファジィ投影ボックスＦＢＩには、現在の視点群から表面の投影領域によって常 に写像された領域が存在しうる。これらの領域では、表面ＳＵの投影領域ＰＥ、 〜ＰＨ，の論理ＡＮＤは真である。

論理ＡＮＤ操作の結果は常に論理ＯＲ操作の結果の部分集合であるので、これら の領域は常に表面ＳＵのファジィ領域ＰＲ内に存在する。

論理的にこれらの領域は、現在の投影ボックスの対応する領域の投影状態が常に 真であるときは、非ファジィである。したがってこれらの領域を非ファジィ領域 ＮＦと総称する。換言すれば影領域である。

表面ＳＵの非ファジィ領域ＮＦを、ファジィ投影ボックスＦＢの現在のすべての 視点の群における表面の投影を写像するとともに、すべての投影内の領域を発見 することにより得ることができる。しかしながら、この方法は多数の視点が存在 する場合コスト高になる。計算を減らすために、慎重すぎる一連の近似を適用す る。

各表面に対して複数の非ファジィ領域が存在しうることは当業者には明白である 。

図５Ａによれば、第１の近似は、視点が現在の視点境界ボックスＢＢ、のあらゆ る場所で存在しうり、かつ、各視点は現在の視点群のすべてのあり得る視野領域 を含む領域を有すると仮定する。これらすべての視点に対向するパッチＰＴ、を 決定する。

これらのパッチＰＴ、、をフロント対向バッチと総称する。これらのパッチＰＴ 、を発見する方法を、補遺ｌで詳細に説明する。

相互接続したフロント対向パッチＰＴ、を、フロント対向副表面５ＬＬａと総称 される表面領域に分類する。これらの表面領域の境界におけるエツジを、境界エ ツジＢＥと総称する。

前面バッチＰＴ、及びこれらの境界エツジＢＥは、視点境界ボックスＢＢ中のあ り得る視点ｖＰに対向しているので、前面副表面ＳＵ２は決して湾曲することな く、かつ、常にこれらの視点ｖＰに対向する。フロント対向副表面ＳＵｔの境界 エツジＢＥＥの投影はしたかって、常に投影領域ＰＲを包囲する。

図５Ｂに示すパッチと同様に、各境界エツジＢＨの投影をファジィ投影ボックス ＦＢ、に写像することができる。エツジＢＥ＋のファジィ領域ＰＲ，はファジィ 投影ボックスＦＢ、の領域であり、この領域は、現在の視点境界ボックスＢＢ、 のすへてのあり得る視点におけるエツジのすへての投影写像を含む。

フロント対向副表面に属するすべての境界エツジのファジィ領域を、ファジィ境 界領域ＢＰと総称される領域に結合することができる。点がファジィ境界領域Ｂ Ｐに存在しない場合、境界エツジＢＥは投影ボックスのすへての関連する点に投 影しない。投影状態のあらゆる変化は境界エツジにおける投影である必要がある ので、点は前面副表面ＳＵの投影領域のすべての写像内に存在する必要がある。

ファジィ領域は前面副表面の結合された投影であるので、ファジィ領域内のあら ゆる区域を、フロント対向副表面の少なくとも一つの投影領域によって写像する 必要がある。したがって、投影領域の内側であるがファジィ境界領域ＢＰの外側 に存在する区域は常に、フロント対向副表面の投影領域の写像を含む。

定義されたこれらの区域を、フロント対向副表面の非ファジィ領域ＮＦ、とする 。

視点はあらゆる指向を有し、かつ、視点境界ボックスＢＢのあらゆる場所に存在 するので、エツジのファジィ領域ＰＲを計算するのは困難である。しかしながら 、ファジィ面上のこの領域の範囲をより簡単に得ることかできる。この範囲の計 算を補遺２に記載する。この範囲を完全に包囲し、かつ、ファジィ投影平面の格 子線に境界を有する最小の長方形を、ファジィ投影平面のエツジのファジィ範囲 ＥＦと総称する。

このことを、図５Ｂと同一のファジィ投影面が示された図５Ｃに示す。この場合 ファジィ境界領域ＢＦ＋を、境界エツジＢＢ。

等のファジィ範囲ＥＦによって置換する。

境界エツジのすへてのファジィ範囲ＢＰを含む領域は常に、フロント対向副表面 のファジィ境界領域を包囲する。したがって、ファジィ領域ＰＲからファジィ境 界領域を減算することにより、常に非ファジィ領域内に存在する区域を発生させ る。この区域を、非ファジィ領域ＮＦを近似するのに用いる。

表面が広いパッチしたがって広い境界エツジを含む場合、表面のファジィ境界領 域を近似するためにファジィ範囲を用いるのは有効でないおそれかある。表面の 境界エツジのファジィ領域を、補遺６に記載された方法を用いて直接評価するこ とができる。各エツジを副エツジに分割することもできる。各エツジのファジィ 領域をこの場合、副エツジのファジィ範囲によって置換することもてきる。

全体か不可視のパッチを検出するための不可視ファジィ投影法 本実施例では、視点■Ｐの群に関連するファジィ投影面ＦＦのエンティティの写 像を比較するようにする。この操作により、これらすべての視点に対して不可視 とみなすことができるエンティティを検出することができる。

図６Ａによれば、視点境界ボックスＢＢ、を、メツシュ表面５ｔＪ８を介して三 つのパッチＰＴＡ、　ＰＴ、及びＰＴｃが観察できるように示す。図６ａ、図６ ｂ、図６０及び図６ｄはそれぞれ、各ファジィ投影面ＦＦ、、のパッチＰＴＡ、 　ｐ’ｒａ及びＰＴｃに対するファジィ範囲ＥＦＡ、εＦ８及びＥＦｃをそれぞ れ示す。メツシュ表面ＳＵ８の非ファジィ領域ＮＦ、も示す。

全体か不可視の表面の決定は、非ファジィ領域の特性に基づく。図５Ｄにおいて 、点ＰＯ７は、現在の視点境界ボックスＢＢ６の視点ＶＰ、１から表面ＳＵ＋に よって隠される。点ＰＯ２が視点境界ボックスＢＢ、に存在する他の視点■Ｐ、 。から可視である場合、表面ＳＵ＋は湾曲して点ＰＯ７の背後に到達している必 要がある。しかしながらこのような状況では、点ＳＰに隣接する表面ＳＵ１の一 部は、視点境界ボックスＢＢａの視点ｖＰｌｔに対してバック対向（ｂａｃｋ− ｆａｃｉｎｇ）となる。この場合表面ＳＯ，の非ファジィ領域は、ＰＯｌの周辺 の射影写像を被覆しない。

上述した特性により、現在の視点境界ボックスの任意の点から点の投影写像を、 表面の非ファジィ領域内で行う場合、また、この点が視点から表面の背後に存在 する場合、この点は常に視点境界ボックスのすべての視点から表面によって隠さ れる。

このことを図５Ｅに示す。この場合、不可視性検出を、単一の視点（ＶＰ、２． 　ＶＰ、４又は視点境界ボックスＢＢ、のいずれか）を用いて行う。

上述した観察を、全体か不可視性のパッチを検出するために用いることができ、 可視が決定されるへき各パッチを選択する。視点境界ボックスの視点から、パッ チの投影を写像する範囲のファジィエレメントをアクセスする。各ファジィエレ メントに記憶された距離が、ファジィエレメントに関連する方向の視点からのパ ッチの深さより小さい場合、パッチは、今上述した非ファジィ領域の特性から常 に非可視パッチとなる。

上述した計算を軽減させるために、パッチの投影写像を、投影写像の範囲すなわ ちパッチのファジィ範囲に置換することかできる。視点からのパッチの深さを、 パッチ境界ボックスと視点すなわち視点境界ボックスとの間の可能な最長の深さ に置換することもできる。このような近似は常に慎重すぎて、隠れた表面の計算 の正確さに影響を及はさない。

各アクティブファジィ投影面ＦＦＡ−ｃに、ファジィエレメントＥＦのような多 数の記憶エレメントを有する２ＤフアジイアレイＰＡ、　、　ＦＡ、及びＦＡｃ を、アクティブファジィ投影面に写像情報を記憶するために割り当てる。すべて のファジィアレイＦＡＡ−ｃをひとまとめにファジィバッファと総称し、２次元 的にアドレス可能なメモリとする。

各ファジィエレメントＦＥは深さ領域を含む。深さ領域は、ファジィ範囲ＥＦが ファジィエレメントＦＢを包囲するパッチＰＴの深さを記憶する。

ファジィバッファ計算周期を各視点群に適用する。まず深さ領域を、表面がまだ 投影ボックスＰＢに投影されていないことを示すために、無限に初期化する。

境界エツジＢεのファジィ範囲ＥＦ及び選択された不透明表面のフロント対向副 表面のパッチＰＴのファジィ範囲ＥＦを、（補遺２に記載するように）計算する 。通常、広い表面が選択される。

これらの範囲に基づいて、フロント対向副表面の非ファジィ領域ＮＦを、補遺３ に記載するように走査線法によって計算する。

さらに、境界エツジＢＢのファジィ範囲ＥＦを、補遺６に記載するように直接計 算することにより見つけることもできる。

上述した方法を用いることにより、すべての非ファジィ領域の各水平セグメント 中のファジィエレメントの最長深さを得る。ファジィアレイＦＡＡ−Ｃの各ファ ジィエレメントに記憶された距離を、ファジィバッファ中の対応するエレメント に記憶された深さと比較する。対応するエレメントに記憶された深さの方か長い 場合、これをファジィアレイＦＡＡ−，の各ファジィエレメントに記憶された距 離に置換する。

不透明なフロント対向副表面のすべての非ファジィ領域をファジィエレメントに 更新した後、ファジィバッファ中の各エレメントは最も隣接した表面の最長深さ を含み、最も隣接した表面を、ファジィエレメントと関連する方向の現在の視点 境界ボックスの選択された視点から見つけることができる。この場合、ファジィ バッファを、現在の視点境界ボックスから全体が不可視のパッチを計算するのに 用いる。これらのツク・ソチを全体か不可視のパッチとみなす。

全体が不可視のパッチを検出するために、各パッチのファジィ範囲内のファジィ エレメント、投影写像、又は写像の範囲をアクセスする。各エレメントに記憶さ れた深さがパッチの最小深さより小さい場合、パッチをエレメントによって示さ れた方向で常に隠される。非ファジィ領域の特性から、すなわちファジィ範囲か すべてのあり得るパッチの視野方向を覆う特性から、ファジィ範囲内のすべての ファジィエレメントにおいて隠されていることを見つける場合、パッチは全体的 に不可視である図６Ｂに示すように、パッチＰＴＡのファジィ範囲ＥＦＡは完全 に非ファジィ領域ＮＦ３内に存在する。したかつて、ノく・ソチＰＴＡは、境界 ボックスＢＢ３中の視点から隠される。

図６０では、パッチＰＴｖゎのファジィ範囲ＥＦｅは、非ファジィ領域ＮＦ２の 内側及び外側に存在する。したがって、外側のこれら四つのエレメントを可視と しても隠してもよく、内側の四つのエレメントの場合、これらのエレメントを介 するすべての視野方向に対して、パッチＰＴ８は隠される。

図６Ｄにおいて、パッチＰＴｃのファジィ範囲ＥＰ、は、ノクツチＰＴｃか存在 するすへてのファジィバッファエレメントに対する深さテストをバスする。パッ チＰＴｃは常に、境界ボックスＢＢ３から不可視である。

隣接するパッチのファジィ範囲間は常にほぼ重畳しているので、高速シャッセを 、各パッチのファジィ範囲内のファジィエレメントの読取り及び書込み速度を上 げるのに用いることができる。シャッセを、次の段落で議論する可視ファジィ投 影法に用いることもできる。補遺５は、シャツセメモリの使用について更に詳し く記載している。

全体か可視のパッチの検出に対する可視ファジィ投影方法本実施例では、視点群 に関連するファジィ投影面のエンティティの写像を比較している。この操作によ り、これらすべての視点に対して可視で、他のエンティティを隠さないものとみ なすことができるエンティティを検出する。

簡単及び高速のために、この方法は、すべての表面が、視野方向に面しない部分 を除いて、現在の視点境界ボックスからあらゆる視野方向において自身を隠さな いと仮定する。このことは、現在の視点境界ボックスの視点に面する同一表面の 二つの部分か互いに隠れないことを意味する。全ての平坦及び二次曲線平面はこ の特性を存する。他の表面を、この基準を満たすより小さい表面に再分割できる 。

図７八に示すように、視点境界ボックスＢＢ４は、メツシュ表面ＳＵＮの回りに 配置した三つのパッチＰＴＤ、　ＰＴ、及びＰＴ、を観察する。

全体が不可視のパッチを検出する方法と同様に、数個のアレイからなるファジィ バッファを、ファジィエレメントの投影結果を記憶するのに用いる。

ファジィバッファのすへてのエレメントは、同次インディケータと総称される領 域を含む。この領域は、ファジィ投影ボックスの関連する格子セルに投影が存在 するかどうか、及び、一つ又はそれ以上の表面を網目格子に投影するかどうかを 示す３値の領域である。投影がファジィ領域に包囲されていない場合、インディ ケータを０とする。投影が一つの表面のファジィ領域内に存在する場合、インデ ィケータを１とする。投影が１より多い表面のファジィ領域内に存在する場合、 インディケータを２とする。

最初に、同次インディケータを０に初期化する。このことは、表面がまだファジ ィバッファに投影されていないことを示す補遺４に記載した走査変換法を用いて 、各表面のファジィ領域の水平セグメントを得る。同次インディケータを、各セ グメントの下で試験する。各インディケータを、インディケータが０又は１の場 合ｌを加える。

パッチのファジィ範囲内にある同次インディケータがすべてｌの場合、一つの面 のみが、現在の視点境界ボックスから、パッチのファジィ範囲内の全ての視野方 向に見える。この表面はパッチ上に存在する必要がある。パッチはしたがって、 他の表面を隠さない。表面のフロント対向部は互いに隠れないので、パッチは、 表面がバック対向とならない限り常に可視である。

このパッチを、全体的に可視／隠されていないパッチと総称する。

パッチのファジィ範囲内に存在する同次インディケータのいずれかが１でない場 合、パッチは被覆、すなわち現在の視点境界ボックスのある視点の他の表面のパ ッチによって閉塞される。

このことを図７Ｂに示す。図７Ｂにおいて、各エレメントか値０．　１又は２の うちのいずれかを有するファジィ投影面ＦＦ４を示す。パッチＰＴ、及びＰＴＦ と、これらに対応するファジィエレメントＦＢＩ、及びＦＢ、に対して示したよ うに、これらは、各ファジィ範囲内のファジィエレメントの幾つかを二つ以上の 表面に写像する場合、全体が可視でなく、かつ、他のパッチを隠さない。パッチ ＰＴ、は、ファジィ範囲内のすべてのファジィエレメントＰＨ，を一つの表面（ すなわちＳＵ、　＞にのみ写像する場合、全体的入力可視／隠されていないパッ チである。

修正された可視ファジィ投影法 上述した方法により、各表面のファジィ領域を２度走査変換する。その理由は、 各ファジィエレメントを、同一表面の数個のパッチのファジィ領域により重畳す ることができるからである。このことを、各ファジィエレメントに対して重畳さ れたパッチを記憶する投影パッチリストと総称される結合リストを用いることに より、回避できる。アレイのような他のデータ構造も、結合リストの位置で用い ることができる。修正された方法は、以下の工程からなる。

１、上述した方法と同様に、各ファジィエレメントは同次インディケータ及び表 面［Ｄ領域を有する。各ファジィエレメントは投影バッチリストも有する。同次 インディケータ及び表面１０領域を、表面がファジィエレメントに投影されない インディケータに対してそれぞれ０に初期化する。ファジィエレメントに関連す る投影バッチリストを０のリストに初期化する。

２、各パッチは、全体が可視のインディケータを有する。このインディケータを ＯＮに初期化する。この状態の各パッチをアクセスする。各パッチのファジィ領 域を計算するとともに、ファジィ領域内の各ファジィエレメントをアクセスする 。

３、アクセスされた各ファジィエレメントの同次インディケータをＯにする場合 、ファジィエレメントは、あらゆる表面のファジィ領域により、投影されない。

現在のパッチの表面ｒＤを表面■Ｄ領領域書き込む。同次インディケータを１に 設定する。

現在のパッチの全体が可視のインディケータをＯＮにする場合、表面ＩＤに現在 のファジィエレメントの投影バッチリストを加える。そうでない場合、これらの 操作は必要なく、その理由は投影パッチ領域を、パッチの全体か可視のインディ ケータをリセットするために用いるからである。

４、同次インディケータが１の場合、現在のパッチの表面１０を、現在のファジ ィエレメントの表面ｔＤ領領域記憶された表面ｔＤと比較する。これらの表面【 Ｄが同一で、全体的に可視のパッチのインディケータがＯＮの場合、このパッチ の１Ｄに、現在のファジィエレメントに関連する投影バッチリストを加える。

二つの表面のＩＤが異なる場合、同次インディケータを、現在のファジィエレメ ントに投影している二つ以上の表面か存在していることを示すために、２に設定 する。現在のパッチ及び現在のエレメントの投影バッチリストに記憶された］Ｄ を存するすべてのパッチは、全体か可視でないおそれがある。したがって、これ らの全体が可視のインディケータをＯＦＦに設定する。投影パッチリスト中の記 録を、これらすべての全体か可視のインディケータを更新した後、移転すること かできる。

５、同次インディケータか２の場合、現在のファジィエレメントは既に、二つ以 上の表面により投影されているへきである。現在のパッチはしたかって、全体が 可視てないおそれかある。投影パッチリスト中の全体が可視のインディケータを ＯＦＦに設定する。

６、すへてのパッチを処理した後、全体か可視のインディケータがＯＦＦに設定 されていない場合、パッチを全体が可視であると決定する。

上述した処理の疑似コードを以下に示す。

表　１ １ｎｌｔｌａｌｌｚｅ　ｔｈｅ　ｔｏｔａｌｌｙ　１ｎｖｌｓｌｂｌｅ　Ｉｎｄ ｉｃａｔｏｒｓ　ｏｆ　ａｌｌ　ｐａｔｃｉｅｓ　ｔｏ　Ｏm； １ｎｌｔｌａｌｌｚｅ　ｔｈｅ　ｈｏｍｏｇｅｎｅｏｕｓ　Ｉｎｄｉｃａｔｏｒ 　ｏｆ　ａｌｌ　ｆｕｚｚｙ　ｅｌｅｍｅｎｔｓ　ｔ。

ｃｌｅａｒ　ａｌｌ　ｐｒｏｊｅｃｔｅｄ　ｐａｔｃｈ　ｌ１ｓｔｓ　ｏｆ　ｔ ｈｅ　ｆｕｚｚｙ　ｅｌｅｍｅｎｔｓ；ｆｏｒ　（ｅａｃｈ　ｐａｔｃｈ　ｏｆ 　ｔｈｅ　ｃｕｒｒｅｎｔ　５ｕｒｆａｃｅ）ｄ。

ｆｏｒ　（ｅａｃｈ　ｆｕｚｚｙ　ｅｌｅｍｅｎｔ　ｕｎｄｅｒ　ｔｈｅ　ｆｕ ｚｚｙ　ｒｅｇｌｏｎ　ｏｆ　ｔｈｅ　ｐａｔｃｈ）Ｏ Ｉｆ　Ｃｔｈｅ　ｈｏｍｏｇｅｎｅｏｕｓ　１ｎｄｌｃａｔｏｒ　Ｉｓ　ｚｅｒ ｏ）ｈｅｎ ｗｒｉｔｅ　ｔｈｅ　５ｕｒｆａｃｅ　１０　ｏｆ　ｔｈｅ　ｃｕｒｒｅｎｔ　 ｐａｔｃｈ　ｔｏ　ｔｈｅ　５ｕｒｆａｃｅ　ＩＤｆｌｅｌｄ； ｓｅｔ　ｔｈｅ　ｈｏｍｏｇｅｎｅｏｕｓ　Ｉｎｄｉｃａｔｏｒ　ｔｏ　ｏｎｅ ；１ｆ　（ｔｈｅ　ｔｏｔａｌｌｙ　１ｎｖｌｓｌｂｌｅ　Ｉｎｄｉｃａｔｏｒ 　ｏｆ　ｔｈｅ　ｃｕｒｒｅｎｔ　ｐａｔｃｈ　１ｓｎｏｔ　０ＦＦ） ａｄｄ　ｔｈｅ　ｐａｔｃｈ　ＩＱ　ｔｏ　ｔｈｅ　ｐｒｏｊｅｃｔｅｄ　ｐａ ｔｃｈ　＋１ｓｔ　ｏｆ　ｔｈｅｆｕｚｚｙ　ｅｌｅｍｅｎｔ； ｎｄｌＦ ｅｌｓｅ　Ｉｆ　（ｔｈｅ　ｈｏ＋ｎｏｇｅｎｅｏｕｓ　１ｎｄｌｃａｔｏｒ　 Ｉｓ　ｏｎｅ）ｌｆ　（ｔｈｅ　５ｕｒｆａｃｅ　ＩＤ　ｏｆ　ｔｈｅ　ｃｕｒ ｒｅｎｔ　ｐａｔｃｈ　ｌｓ　ｔｈｅ　ｓａｍｅａｓ　ｔｈｅ　５ｕｒｆａｃｅ 　１０５ｔｏｒｅｄ　Ｉｎ　ｔｈｅ　ｆｕｚｚｙ　ｅｌｅｍｅｎｔ）ｈｅｎ Ｉｆ　（ｔｈｅ　ｔｏｔａｌｌｙ　１ｎｖｌｓｌｂｌｅ　Ｉｎｄｉｃａｔｏｒ　 ｏｆ　ｔｈｅ　ｃｕｒｒｅｎｔｐａｔｃｈ　Ｉｓ　ｎｏｔ　０ＦＦ） ａｄｄ　ｔｈｅ　ｐａｔｃｈ　１０　ｔｏ　ｔｈｅ　ｐｒｏｊｅｃｔｅｄ　ｐａ ｔｃｈ　１ｉｓｔ　ｏｆｔｈｅ　ｆｕｚｚｙ　ｅｌｅｍｅｎｔ；ｎｄｌｆ １ｓｅ ｓｅｔ　ｈｏｍｏｇｅｎｅｏｕｓ　Ｉｎｄｌｃａｔｏｒ　ｔｏ　ｔｗｏ；　’ｓ ｅｔ　ｔｈｅ　ｔｏｔａｌｌｙ　１ｎｖｌｓｌｂｌｅ　１ｎｄｌｃａｔｏｒ　ｏ ｆ　ｔｈｅｃｕｒｒｅｎｔ　ｐａｔｃｈ　ａｎｄ　ｅａｃｈ　ｐａｔｃｈ　Ｉｎ ｄｅｘｅｄ　ｂｙ　ｔｈｅｐｒｏｊｅｃｔｅｄ　ｐａｔｃｈ　１１ｓｔ　ｏｆ　 ｔｈｅ　ｆｕｚｚｙ　ｅｌｅｍｅｎｔ　ｔ。

ＯＦＦ； ｎｄｌｆ １ｓｅ ｓｅｔ　ｔｈｅ　ｔｏｔａｌｌｙ　１ｎｖｌｓｌｂｌｅ　Ｉｎｄｉｃａｔｏｒ　 ｏｆ　ｔｈｅ　ｃｕｒｒｅｎｔｐａｔｃｈ　ｔｏ　ＯＦＦ； ｎｄｌｆ ストラテジイ法に対する可視法及び不可視法の使用上記方法を適用することによ り、全体が不可視のパッチ及び全体が可視／隠されていないパッチのリストを、 視点群に対して得ることができる。これらのパッチの可視性は、すべての副群及 び副群の下の視点に対して同一のままである。したがって、これらのパッチは、 これらの副群及び視点中の複雑な可視性の計算を行う必要がない。

群中の各視点に対して、全体が不可視のパッチを無視することができる。全体が 可視／隠れていないパッチを、これらの可視性及び形状係数を決定するために、 他のパッチと比較する必要がない。これらのパッチの形状係数を、表面間の放射 転送を表す数式を用いたこれらのパッチの指向、位置及び形状から直接計算する ことができる。

パッチが明るく、すなわち現在の視点群に隣接している場合、直接の形状係数の 計算をより正確に行う必要がない。パッチをより小さいパッチに再分割すること ができ、この場合形状係数の計算をこれらの副バッチに対して代わりに行う。メ ツセルアナログ法（Ｎｕｓｓｅｌ　ａｎａｌｏｇ　ｔｅｃｈｎｉｑｕｅ）のよう に正確な放射転送の式を用いることもできる。この方法により、パッチを表面、 この場合には中心が視点上にある半球の低部に投影した後、パッチの断片区域を 見つける。

正確な形状係数の計算が必要とされない場合、視点の現在の群に対するパッチの 形状係数を、形状係数がバッチ中で一定であると仮定することにより得ることが できる。通常の形状係数の式を ｃｏｓ　Ａ　＝Ｎ、（ＰＯ−ＶＰ）　”　ｋ＝ｋ（Ｎｘ　（ｘ’　−ｘ）　＋Ｎ ｙ（ｙ’　−Ｙ）＋Ｎｚ（ｚ’　−ｚ））＝ｋ（Ｎｘ　ｘ’　＋Ｎｙ　ｙ’　十 Ｎｚ　ｚ’　−Ｎｘ　ｘ−Ｎｙ　ｙ−Ｎｚ　ｚ）によって簡単にすることかてき る。ここで、Ａ及びＢはそれぞれ、視野ベクトルと観察されるパッチの法線との 間の角度及び視野ベクトルと視点か存在するパッチの法線との間の角度であり、 ｒは視点と観察されるパッチの中心との間の距離である。

ファジィ投影法には、視点の階層に基づいた視点の規則正してトップ−ダウン操 作か要求される。しかしながら、順次詳細化法（ｐｒｏｇｒｅｓｓｉｖｅ　ｒｅ ｆｉｎｅｍｅｎｔ　ｍｅｔｈｏｄ）のような方法ては、受信バッチは通常、明る さの減少する順序でアクセスされる。したがって、これらの方法をファジィ投影 法と共同して用いる場合、群中の幾つかの視点の形状係数の計算を行なわなくて もよい場合があり、その理由は群中のすへての視点が一度に処理されないからで ある。どれが全体的に可視／隠れていないパッチであるか、及び、とれが部分的 に完全な群の全体的に不可視のパッチであるかについての情報を、メモリに記憶 させる必要がある。この場合群中の離れた視点を、処理されるべき視点の順序に くる際に、この情報を用いることができる。この情報を、群中のすへての視点か 処理された場合に除去することができる。

（それ自体既知の）順次詳細化法のような方法において、バッチ間の形状係数を 繰り返して計算しなければならない。したかって、メモリか許容するならば、ど れが全体的に可視／隠れていないパッチであるか、及び、どれか部分的に完全な 群の全体的に不可視のパッチであるかについての情報を除去することができ、か つ、有効に用いることかできる。

−巡目の計算では、すべての受信パッチに対するすべてのファジィ投影の計算及 び通常の半玉六面体の計算を、必要に応じて行う。これらの計算中、各ｎ／視点 における放射バッチを三群、すなわち可視／隠れていない群、全体的に不可視の 群及びその他の群に分類する。このような分類情報を、アレイすなわち結合リス トのようなデータ構造を用いて記憶する。

二巡目の計算では、パッチ間の形状係数を再評価する必要がある場合、ファジィ 投影の計算を繰り返さない。各視点の全体的に可視／隠れていないパッチ及び全 体的に不可視のパッチを、記憶された情報から検索するだけでよい。

視点の各群に対するパッチの分類を記憶するためのメモリを、幾つかの方法によ って減少させることができる。最初に、群から全体的に可視／隠れていない又は 全体的に不可視であると判るパッチは、すべての副群に対して同一の状態に維持 するので、これらのパッチを繰り返して記憶させる必要がない。

次に、パッチの三つのリストの組合せは、各視点群に対して分類される必要のな いすべてのパッチの組であるので、二つのリストのみが群に対して記憶される必 要かある。さらに記憶を減らすために、三つのリストの最初の対を保持すること ができる。

パッチの記録を通常は順番に編成及びアクセスするので、リスト中のパッチ【Ｄ は通常ある順序を有する。リスト中の連続するパッチのＩＤ間の差は通常、これ らのＩＤの大きさより小さい。

このようなことが生じる度に、これらの差をパッチＩＤの代わりに記憶させるこ とができる。符号ビットを、パッチｒＤと差の値との間で区別するために用いる ことができる。リストを、リストのアレイを更に効率的に用いるために、［Ｄに よって分類することができる。

最後に、パッチの可視状蓼は通常、視点のある群から視点の隣接する群で大きく 変化しない。したかって、開始点として視点群のパッチリストを用いる場合、一 連の隣接群を視点群のバッチリストに更に記憶させることができる。最初の群か ら開始し、各隣接する群は、削除される必要があるバッチリストを記憶し、現在 のリストを形成するために前の群のバッチリストを追加するだけでよい。また、 特定の領域を、このアレイに使用するのと区別するために用いることができる。

形状係数計算の精度の増大 ファジィ投影法を、形状係数の計算の最適精度を得るために用いることもできる 。不可視性技術により全体的に不可視のパッチをフィルタした後、可視性技術に より全体的に可視かつ隠れていないパッチを検出する。上述したように、これら のパッチの形状係数の計算において、異なる精度を算出する種々の方法を利用す ることかできる。

残りのパッチは全体的に不可視でない。これらの残りのパッチは全体的に可視／ 隠れていないのでもない。これらの残りのパッチの形状係数計算の精度を以下の 工程により決定する。

ａ、最初に、数個のレベルを、これらのレベルのそれぞれがパッチの形状係数の 計算により到達すべき精度のレベルに相当するように規定する。各精度レベルに より、半穴面体バッファの解像度、パッチの詳細のレベル、半穴面体バッファの 代わりにレイ・トレーシングを用いるかどうか、又は標本点ごとに追跡された光 の本数のような形状係数の計算のストラテジを決定する。

ｂ、全体的に不可視か全体的に可視かわからないすへてのパッチを、これらのパ ッチの輝度、重要性、現在の視点群からの距離及び他の特性に基づいた精度レベ ルにより分類する。各パッチ記録は、パッチの精度レベルを記憶する領域を有す る。精度レベル領域を、ファジィバッファ中の各ファジィエレメントに対しても 割り当てる。各領域を最低の精度レベルに初期化する。

ｃ９バッチを、より高い精度レベルを有するパッチが最初に走査変換されるよう にアクセスする。

アクセスされた各パッチに対して、可視ファジィ投影の計算に用いられたパッチ のファジィ範囲の同一の走査変換を行う。

しかしながら、同次変換器の代わりに、各ファジィエレメントアクセス中の精度 レベル領域をテストする。領域中の値がパッチの精度レベルより大きい場合、パ ッチは隠れ又はより高い精度レベルのパッチにより隠されるおそれがある。パッ チの精度レベルをこの領域中の値に設定する。この値が元の精度レベルより小さ い場合、元の精度レベルをこの値に書き込む。

ｄ、すべてのパッチを処理した後、各パッチの最新の精度レベルは、パッチの形 状係数の計算が現在の視点群に対して行われる必要のある精度の最大レベルを示 す。この精度レベルは、パッチか付与しうる精度より高い場合、パッチを後方に 湾曲し　゛て再分割し、精度がこの精度レベルと同等の副パッチに置換する。

パッチの実表面を湾曲させる場合、副パッチの投影をパッチの投影の外側にする ことかできる。したかって、効率的であるへき副分割ストラテジに対して、各エ ンティティのファジィ範囲は、すべてのファジィ投影中に副エンティティのファ ジィ範囲を存するべきである。各エンティティのファジィ範囲を、これらすべて の副エンティティを有する軸に整列した境界ボックスのファジィ範囲によって近 似することができる。

ｅ、ファジィエレメントの精度レベル領域は、現在の視点群からの対応する視野 方向すなわちこれらの視点の半穴面体の対応する領域で行われる必要がある計算 の精度を表す。パッチの形状係数を、パッチに覆われた種々のファジィエレメン トの精度要件に一致する可変解像度で計算できる。このことを、レイ・トレーシ ング又は形状係数の計算の半立法方式で行うことができる。

ｆ、レイ・トレーシング方式では、視点におけるパッチの形状係数を、すべての 観察できる方向で光を追跡することにより計算する。現在の視点群のそれぞれに 対して、ファジィエレメントに関連する立体角内に発射させるべき光の本数は、 ファジィエレメントの精度レベルに依存する。精度レベルか高い場合、２本以上 の光をトレースする。反対に、数個の隣接するファジィエレメントの精度レベル か低い場合、１本の光のみをファジィエレメントに関連する方向にトレースして もよい。

ｇ、半立法方式では、半立法体の異なる領域は、これらの領域に関連するファジ ィエレメントの精度の要求に一致する異なる標本解像度を存する必要かある。こ のことは、生立法ピラミッドと総称されるピラミッド形状を用いることにより得 られる。半穴面体ピラミッドのパッチの走査変換を補遺７に記載する。

隠面計算に対する可視性及び不可視性法の使用本例では、隠面計算における可視 性及び非可視性ファジィ投影法の計算結果に利用している。

影計算では、コンピュータアニメーション、フライトシュミレーション又は動的 グラフィックのように取り除かれるべき一連のイメージで利用するに当たり、隠 面消去操作を数回繰り返す必要かある。周囲の像を取り除く場合、観察者の位置 を視点とみなすことができる。この視点を、視点群の階層に結合することもてき る。

現在の視点群の視野の結合された領域が狭い場合、投影ボックス及びファジィ投 影ボックスを、ファジィ投影平面及びこれに関連する投影平面が現在の視点群に 対してアクティブとなるように平坦にすることができる。

不可視性ファジィ投影法を用いることにより、視点群に対して全体的に不可視で あるとわかるパッチは、副群及び群中のそれぞれの視点を考慮する必要がない。

可視ファジィ投影法を用いることにより、走査変換中の深さ計算及び全体が可視 のパッチの比較が必要でなくなる。

レイ・トレーシング計算に対する可視性及び不可視性法の使用 本実施例では、レイ・トレーシング法における可視性及び不可視性投影法の計算 結果を利用する。

レイ・トレーシングを利用する場合、周囲の物体及び表面を通常、階層幾何学的 モデルとして編成する。幾何学的モデルの節点からトレースされた光の本数か、 ファジィバッファ法の使用に適する場合、視点群を、光が観察者として放射され る節点の表面のすべての点を処理することにより形成する。あらゆる瞬時の観察 者の位置を視点とする。視点を視点群の階層に分類できる。

ファジィバッファ計算から、どのパッチが各節点に対応する視点群に対して全体 的に可視／隠れていないか、及び、どのパッチかこの視点群に対して全体的に不 可視かを決定する。

光を接点からトレースする場合、すべての全体的に不可視のパッチを考慮する必 要がない。また、光を最初に全体が可視／隠れていないパッチに対してテストす る。光かこれらのパッチの一つに当たると、当てられたパッチが光路に最も隣接 したパッチであるので、他のパッチに対する別のテストを行う必要がない。

ラジオシティ法とレイ・トレーシング法の双方を用いる場合、ファジィバッファ 計算の結果を双方の方法に対して用いることかできる。

コンピュータビジョンにおける可視及び不可視ファジィ投影法の使用 可視性及び不可視性ファジィ投影法を、コンピュータビジョンに用いることかで きる。物体の閉塞解析は、コンピュータビジョンの必須操作である。この解析に 基づいて、仮説を３Ｄモデルに対して立てる。この場合３Ｄモデルを、視覚デー タすなわち存在するモデルに調和させる。３Ｄモデルを、このモデルが適正なも のになるまで、繰り返し調和及び詳細化させる。通常、視覚データ及び仮説には 、多くの不明確さ及びあいまいさがある。このような不正確さを、以下に示す現 在の技術によって調整することができる。

１、モデル構築段階中、視点境界ボックスを、視点の存在しつるすべての位置を 含むように定義できる。

２、モデル構築段階中、３Ｄモデルを視覚データに基づいて発生させる。しかし ながら、エツジやパッチのようなエンティティの正確な位置や形状が不正確な場 合、エンティティを、すべてのありうるエツジやパッチの位置を有する境界ボッ クスによって近似する。

３、仮説を立てたモデルに基づいて、不可視性及び可視性技術を、全体か可視の 表面、全体か不可視の表面及び可視性を決定できない表面を計算するために実行 する。

４、全体的に可視の表面は、情報が比較的明示された視覚データに相当する。こ のようなデータを、連続的に解析されたすなわちより急速に検査されたデータと みなすことができる。可視性を決定できない表面によって、投影されるファジィ 投影ボックスの区域は、より不明確な視覚データに相当する。これらの区域に相 当する像平面の区域を更に解析する。

５、次の解析順序で、仮説はさらに正確になる。したがって、視点境界ホックス 及びエンティティの境界ボックスを縮小させることかてきる。

好適実施例を、Ｃ言語のプログラムに適合し７た通常の目的のコンピュータで実 行するとともに、深さの複雑さの異なる１組のモデルを用いてテストンた。三つ のモデルを図１３Ａ１図１３Ｂ及び図１３Ｃに示す。可視表面計算を、隣接する ５個の視点に対して行った。異なる画素及びパッチ解像度の下での隠面計算の時 間を測定したものを、以下示す。

例１ 粗パッチ、粗スクリーン画素（４００Ｘ　４００画素）、ファジィバッファの解 像度：　４００　Ｘ４００画素表２ 例２ 粗バッチ、精スクリーン画素（１０００ｘ１０００画素）、ファジィバッファの 解像度：　４００　Ｘ４００画素表３ 例３ 精パッチ、粗スクリーン画素（４００Ｘ　４００画素）、ファジィバッファの解 像度：　４００　Ｘ４００画素表４ 例４ 精パッチ、精スクリーン画素（１０００ｘｌｏ００画素）、ファジィバッファの 解像度：４００Ｘ４００画素表５ 上記の結果は、好適実施例のオーバヘッドが低いことを示している。また、モデ ルの深さ方向複雑度が高いときにかなりの計算の節約が達成される。

上述した種々の実施例のストラデジイを適用することにより、多数の利点が得ら れる。第１に、上述のストラデジイは、これまでの隠面アルゴリズムで遭遇する 節約がない。例えば、これらストラデジイは、環境内の交差する表面又はパッチ の存在を除外しない。さらに、表面パッチを曲面にすることができ、かつ、場面 を静止場面にする必要がない。さらに、本発明による方法は、極めてわずかな計 算オーバヘッドとなる。本発明による方法では、Ｚ−バッファで演算するため、 容易にハードウェアで実行することがてきる。

好適実施例は、ヒユーリスティックを用いてさらに向上させることかできる。ビ ルディングのインテリアのインラクティブウ十−クスルーのような用途では、お そらく大きな鮮明（非ファジィ、本撮）領域を形成する表面か、壁、床、天井を 表すものとなる。したかって、これら表面の鮮明領域のみをファジィバッファに 走査変換するだけでよい。

隠面除去計算等の低減に加えて、本発明の好適方法はラジオシティ法に使用する こともてきる。現在のところ、ラジオシティ法は極めて低速であり、これは主と して形状ファクタを決定するのに多数の表面点について表面の可視度を計算する 必要があるためである。しかし、これらの点を分類し、視点群として処理するこ とにより、この好適方法はこれら視点の１＃に対して全体的に可視の表面を決定 するのに使用することかできる。

ボックスを限界する各視点における視点の密度は極めて高くなりうる。したかっ て、本発明による方法の利点は、通常の隠面消去法に使用する場合よりラジオシ ティ法に使用する場合の方か大きくなる。

上述した本発明による方法は、抽象データを用いるバーチャルリアリティ及びそ の他の用途に使用することもできる。将来、このような用途ではラジオシティ法 を用いて複雑かつ動的な環境をリアルタイムで表示することが必要になる。時間 次元を追加することにより、ボックスを閉塞する各視点における視点密度をラジ オシティ法の視点密度より著しく高くすることができる。したがって、上述した 方法は、これらの用途における計算等を著しく高速化することができる。他の用 途ととしては、エネルギースペクトルデータのような科学データの発生、処理及 び表示のような物理的データの処理がある。

以上、本発明を幾つかの実施例について説明したが、本発明はこれらの実施例に のみ限定されるものではなく、幾多の変形及び変更か可能である。

補遺ｌ 視点境界ボックスとフロント対向するパッチの検出図２を参照するに、パッチＰ Ｔが視点ＶＰと対向するか否かは、パッチＰＴの法線Ｎと視野ベクトルｖｖとの 間の角度Ａにより決定することかできる。視野ベクトルは視点ＶＰからパッチＰ Ｔの中心に向くベクトルであり、この角度Ａのコサインは以下の通りである。

ｃｏｓＡ　＝Ｎｘ　（ＰＯ−ＶＰ）　Ｘｋ＝ｋ（Ｎ□　（ｘ’−ｘ）＋Ｎｙ　（ ｙ’　−ｙ）十Ｎ、（ｚ’−ｚ）） ＝ｋ　（Ｎ、・ｘ’　＋Ｎ、・ｙ’　＋Ｎｔ　−ｚ’　−Ｎ、・ｘ−Ｎ、・ｙ− Ｎ、・Ｚ） ここで、ＶＰ＝　（ｘ、ｙ、ｚ）は、視点の位置であり、Ｎ＝　（Ｎ、、Ｎア、 Ｎ、）はパッチの単位法線であり、ＰＯ＝（ｘ’、ｙ’、ｚ’）はパッチ中心の 位置である。ｋは視線ベクトル（ＶＶ＝ＰＯ−ＶＰ）を単位ベクトルに変換する 正の係数である。

パッチＰＴが視点境界ボックスＢＢと対向する場合、角度Ａは鈍角になるべきで ある。従って、ｃｏｓＡはボックス中の各取り得る視点ＶＰに対して負になるべ きである。これをチェックするため、角度Ａのコサインの最大値を見つける。最 大値が正の場合、パッチは境界ボックス中のある視点に対してバック対向となる 。

ＰＯ及びＮは、定数ベクトルであるから、ｃｏｓ　Ａか最大値となるには、Ｎア 　・ｘ、　Ｎ、　・ｙ及びＮ、・Ｚが最小になる必要がある。Ｎの成分の符号に 応じて、ｘ、ｙ及びＺの最大値又は最小値のいずれかを用いる。これらの座標は 現在の視点境界ボックスのコーナーの位置に対応する。

パッチか時間に対して移動又は回転し、視点境界ボックスが時間に対して異なる 視点を含む場合、各時間瞬時における最小のｃｏｓＡを計算し、最小のｃｏｓ　 Ａを選択することができる。

視点境界ボックスの内部に位置し又は交差する境界容積を有するパッチは常時フ ロント対向しないものとして処理する。これらのパッチは初期境界容積チェック により検出することができる。

図１１Ａは一組の視点ＶＰ、、ＶＰ、、ＶＰ、とフロント対向する領域ＳＵ、ｌ の切断面視野を示し、図１１Ｂは視点境界ボックスＢＢＲとフロント対向する同 一の表面領域を示す。フロント対向するパッチは、ボックスＢＢＲ中の全ての取 り得る視点と対向するので、領域ＳＵ、は後方湾曲せずこれらの視点と常時対向 する。従って、領域ＳＵ、の限界の視野投影は常時その投影を包含することにな る。この特性をその後のファジー投影計算に利用することができる。

図１２Ａ〜図１２Ｃは視点群及びそれらの境界ボックスとフロント対向する表面 領域の投影の切断面視野を示す。

図１２Ａにおいて、表面領域の全てのパッチＰＴＡがフロント対向する場合、こ の表面領域の境界エツジの投影ＢＰＡはその領域の投影ＰＥＡを常時包囲する。

図１２Ｂにおいて、表面領域の一部の表面パッチＰＴ、がフロント対向しない場 合、この表面領域は後方に湾曲している。この表面領域の境界エツジの投影ＢＰ 、はこの領域の投影Ｐ　Ｅ　ｍの内側に位置する。

図１２Ｃにおいて、巻き込んだ表面の各フロント対向領域の境界の投影ＢＰｃは この領域の投影ＰＥｃを包囲する。

補遺２ 境界エツジおよびパッチのファジィ範囲の計算図２に示すように正のＺ方向に対 向する射影平面ＰＰの視点ＶＰ　（ｘ、ｙ、ｚ）に対する点ＰＯ（ｘ’　、ｙ’ 　、ｚ’　）の射影座標ＰＲ（Ｘ、　Ｙ）は次式で表わすことができる。

Ｘ＝　（ｘ’　−ｘ）　・ｄ／　（ｚ’　−ｚ）　（１）Ｙ＝　（ｙ’　−ｙ） 　・ｄ／　（ｚ’　−ｚ）　（２）ここにｄはＺ方向に対向する投影面に対する 視点からの最短距離である。

ＸおよびＹを最大とするために、Ｘおよびｙの最小値を用いる。ＸおよびＹを最 小とする必要かある場合にはＸおよびｙの最大値を用いる。Ｚが除数の一部分で あるため、その最大値または最小値を用いるかどうかはＸおよびｙの極値を選定 した後の（ｘ’−ｘ）および（ｙ’−ｙ）の符号に依存する。視点境界ボックス のエツジが軸に平行である場合にはこれら極値Ｘ。

ｙおよびＺを存する視点はボックスの隅部にある。

式（１）および（２）によれば、極値ｘ’、ｙ’およびＺ′を有する点は最大お よび最小の投影を生ずる。しかし、これらの点は境界エツジおよびパッチとし得 る現在の投影エンティティには存在しない。

この問題を解決するために、エンティティの境界容量を用いてこのエンティティ を近似する。その投影を評価に用いることができる。その理由はこれら投影がこ のエンティティの投影を含むからである。

往々にして１つのエンティティをサブエンティティに再分割することができる。

その位置および形状は全時間に亘り静的でなく、しかも確かてない。従って、エ ンティティの境界容量は占有すべきスペースの全部および考慮すべきサブエンテ ィティの境界容量全部を含む容量とする。

従って、エンティティの境界容量は、計算を考慮する必要のあるサブエンティテ ィの全部を含む。

上述した導関数について、ｙ′およびｙ′の最大値およびＸおよびｙの最小値を 用いて投影を最大にする。最大とするかまたは最小とするか（ｚ’−ｚ）は（ｘ ’−ｘ）および（ｙ′−ｙ）の符号に依存する。これらの項が正である場合には この項を最小とする必要かある。従って、最小値Ｚ′および最大値Ｚを用いる。

そうでない場合には最大値Ｚ′および最小値Ｚを選定する。最小投影の検出は最 大化の逆である。従って、個別の項を最小化または最大化することはこれに従っ て変化させるようにする。

最大値Ｘおよび最小値Ｙを与える投影を得ることにより、これら投影を法線がＺ 方向に向かうファジィ投影面ＦＰに写像する。

隅部のこれら投影を有し、且つ関連するファジィ投影面ＦＦのエツジに平行なエ ツジを有する面に長方形を画成することができる。これら投影は切上げまたは切 捨てを行って元の長方形およびその下側の画素全部を含む他の領域を形成する。

これがファジィ投影面ＦＰにおけるパッチのファジィ度ＥＦである。

軸を回転することにより、式（１）および（２）の項をこれに従って変更する場 合には、同一の式（１）および（２）を他の方向に対向する投影面に用いること ができる。従って、これらの面に相当するファジィ範囲を同様に得ることができ る。

パッチが視点境界ボックス内にある場合には、ある視点Ｚ′は式（１）および（ ２）のＺよりも小さいかまたはこれに等しい。従ってファジ一度はこれら式の分 母および分子の符号によって決まり得る方向に無限となるようにする。

補遺３ 非ファジィ領域の計算 非ファジィ領域を計算するために、まず最初、ファジィ境界領域と、投影領域の １つとの関係を得る必要がある。

現在の視点境界ボックスの２つの視点およびファジィ投影面の点を考察する。こ の点の１つの視点写像および他の視点のフロント対向サブ面の投影はこの点に写 像しない。

投影状態の変化は境界エツジの投影時にのみ発生し得るため、２つの点に隣接す る曲面で、これからの境界エツジの投影はファジィ投影面同一の点に写像される ようになる。この曲面は現在の視点境界ボックスの内側に全体的に位置するため 、この点はこの境界ボックスの境界エツジのファジィ領域内に位置するようにす る必要がある。

ファジィ投影面の点がフロント対向サブ面の投影領域の写像内にあるとともにこ れが境界エツジのファジィ領域の外側にある場合には、かかる点は現在の視点境 界ボックスの視点全部に対しサブ面の投影領域内に常時位置するようになる。こ の点を非ファジィ領域の内側に規定する。ファジィ境界領域が境界エツジのファ ジィ度を含む区域内に常時位置するため、この点も前者か後者により近似される 際に非ファジィ領域の内側に位置する。

上述した所を基とし、現在の視点境界ボックスの視点からフロント対向サブ面の 投影領域を見いだし、これをファジィ領域に投影し、境界エツジのファジィ度と 交差する区域全部を減算することによって近似非ファジィ領域を得ることができ る。この目的のために、変形走査線アルゴリズムを用いることができる。

まず最初、現在の視点境界ボックスの任意の視点を選択する。

通常境界ボックスの中心を選択する。この視点は選択された視点と称される。こ の視点からのフロント対向サブ面のエツジの投影座標を見いだす。投影座標系お よびファジィ投影座標系はｌ対ｌの写像であるため、前者から後者への写像は通 常のようになる。

これに次いて補遺２で記載したパッチのファジィ度の計算を行う。

２つのパッチＡおよびＢか走査線ＳＬと交差し、且つこれら境界エツジの各ファ ジィ度ＥＦＡおよびＥＦ、を有するがかるアレイの例を図８Ａに示す。

２つのアクティブエツジリストは、走査線の処理中保持される。第１エツジリス トはパッチのアクティブエツジを含む。第２エツジリストは境界エツジのファジ ィ度のアクティブ垂直エツジ対を含む。

図８Ａにおいて、第１アクテイブエツジリストはＡＩ　Ａ２　ＢＩ　Ｂ２であり 、第２アクテイブエツジリストはＥＩ　Ｂ２　Ｂ３　Ｂ４である。

順次の走査線の処理中これらリストのエントリは、これらが現在の走査線でアク ティブとなる際に重畳されるようになる。

これらエントリはアクティブ状態にある最後の走査線が処理される際にリストか ら除去する。

現在のファジィアレーｒの水平エレメントの数と同程度の多数のエレメントを有 する走査線アレイを保持する。このアレイの各エレメントは深さフィールドおよ びオーバーラツプインディケータと称されるプールフィールドを含む。深さフィ ールドを用いてファジィ度がファジィエレメントを囲むパッチの深さを記憶する 。オーバーラツプインディケータによってエレメントが非ファジィ領域の下にあ るかどうかを示す。深さフィールドは負の無限に初期化する。オーバーラツプイ ンディケータは零に設定する。

次いで第１アクテイブエツジリストのエツジ対を処理する。

これらエツジの各層のスパンによって現在の走査線のパッチのセグメントを表わ す。スパン内のエレメントのオーバーラツプインディケータを１に設定する。こ れらエレメントの各々の深さフィールドに蓄積された値を、選択された視点に対 してパッチの深さと比較する。この値は視点からパッチまたはパッチ境界ボック スまての最大深さによって近似する。前者が小さい場合にはこれを後者により置 換する。

パッチのセグメントの計算を行うことによって現在の走査線およびアクティブエ ツジの交点を見いだす必要がある。この計算は、エツジかスパンの左側にあるか または右側にあるかに応じて各エツジの最も左側の位置または最も右側の位置を 用いることにより回避することかできる。この不正確さか許容される理由は、こ れが境界エツジのファジィ度により常時オフセットされるからである。

次いて第２アクテイブエツジリストのアクティブエツジ対をアクセスする。各層 のスパンは現在の走査線の境界エツジのファジィ度のセグメントを表わす。スパ ン内のエレメントのオーバーラツプインジケータ全部を零にリセットする。

アクティブエツジリストの記録の全部が処理された後、オーバーラツプインジケ ータが１である走査線アレイのエレメントは現在の走査線の非ファジィ領域のセ グメント内に位置する。

深さフィールドはこれらエレメントにより表わされる視点方向において領域の最 大可能な深さを含む。

アレイの各エレメントに蓄積された深さをファジィバッファの対応するエレメン トの深さフィールドと比較する。後者が大きい場合にはこれを前者と置換する。

図８Ｂはパッチへのアクティブエツジの走査変換後の走査線アレイを示す。図８ ０はパッチＢのアクティブエツジの走査変換を示す。図８Ｄは境界エツジのファ ジィ度ＥＦＡおよびＥＦ８内のエレメントかりストされた後ラインアレイを示す 。

補遺４ ファジィ領域の走査変換 ファジィ領域を得るには、補遺３のアルゴリズムに対し変更した走査線アルゴリ ズムを用いる。

走査線の処理中はアクティブエツジリストを維持しておく。

このリストには、現在の走査線中でアクティブとなるパッチのファジィ範囲の垂 直エツジの対を含む。順次の走査線の処理中、現在の走査線中でアクティブとな るリスト中のエントリが加えられる。アクティブである最後の走査線が処理され ると、エントリはリストから削除される。

（図８八に類似するもファジィ領域に対する）図９Ａの配置に対しては、アクテ ィブエツジリストはＥＩ　Ｂ２　Ｂ３　Ｂ４である。

現在のファジィアレイにおける水平エレメントの個数と同じ個数のエレメントを 有する走査線アレイが維持される。このアレイの各エレメントは当該エレメント がファジィ領域の下にあるかどうかを示すオーバーラツプインディケータと称さ れるプールフィールドである。

各走査ラインに対しては、アクティブエツジリスト中のエントリがアクセスされ る。各対間のスパンは現在の走査線中のパッチのファジィ範囲のセグメントを表 す。スパン内のエレメントのオーバーラツプインディケータはすへて１にセット されるアクティブエツジリスト中のエントリの処理後、オーバーランプインディ ケータ力月であるアレイエレメントは現在の走査線中のファジィ領域のセグメン トを含む。

図９Ｂは、パッチへのファジィ範囲ＥＦＡ内のエレメントが更新された後の走査 線アレイの状態を示す。

図９Ｃは、バッチＢのファジィ範囲ＥＦ、内のエレメントが更新された後の走査 線アレイの状態を示す。

補遺５ パッチのファジィ範囲内のファジィエレメントのアクセス及び書き込みを速める ためにキャッシュを用いることここに述へるファジィバッファ法では、各バッチ のファジィ範囲内のファジィエレメントを読み出したり書き込んだりする必要が ある。隣接するパッチのファジィ範囲間には通常かなりのオーバーラツプがある 為、これらエレメントのアクセス及び更新は、高速のキャッシュ内にこれらの情 報を記憶することにより減少させることができる。

キュッシュは種々の形態にすることができる。図１Ｏに示す一例では、キャッシ ュバッファＣＢと２０の相互参照表ＣＲ＋及びＣＲ２とを用いる。キャッシュバ ッファＣＢは、読み出す又は書き込む必要のあるファジィバッファエレメント上 のフィールドの鏡映（ミラー）であるフィールドを各エレメントが含んでいる２ Ｄアレイである。相互参照表ＣＲ，及びＣＲｘはそれぞれ、２Ｄアレイにおける 行及び列の個数と同じ個数のエレメントを含んでいる。表中の各エレメントは、 これを含むアレイに応じて現在のファジィアレイＦＡの行及び列と２Ｄアレイの 行及び列とを相互参照するのに用いられる行（ＣＲ，）又は（ＣＲ２）のいずれ かを含んでいる。キャッシュ中の各エレメントに対しては、相互参照表ＣＲ＋及 びＣＲ２はリセットスイッチを含んでおり、これかりセットされたかどうかを表 すようになっている。

最初はすべてのリセットスイッチが１に初期化される。キャッシュバッファＣＢ の中心は読み出すべき第１バツチのファジィ範囲の中心に写像される。第１バツ チのファジィ範囲内のファジィエレメントが読み出された後、これらエレメント における情報は写像に応じてキャッシュバッファＣＢのエレメント内に記憶され る。キャッシュ内の行及び列の写像はそれぞれ相互参照表ＣＲ，及びＣＲ１内に 更新される。これらの表中で更新されたエレメント中のリセットスイッチ及びキ ャシュバッファＣＢは零にリセットされる。

第２バツチのファジィ範囲内のファジィエレメントを読出す前に、キャッシュバ ッファＣＢ内のデータが最初に読み出される。エレメントが既にキャッシュバッ ファＣＢ内に記憶されている場合には、キャッシュバッファＣＢはその情報を得 るためにアクセスされる必要はない。

キャッシュの効率を最大にするために、いずれかの隣接のバッチを最初にアクセ スする。一連のパッチの処理後、写像がキャッシュの境界を被覆するパッチが存 在する。影響を受けた行又は列は包み込まれる。対抗するエツジにおける行はバ ッチに対する次の行又は列となる。

バッチデータをキャッシュバッファＣＢに書き込む前に、現在のパッチ写像の行 又は列内の相互参照表ＣＲ＋及びＣＲｔ内の各エレメントを検査する。リセット スイッチがオンであるか又は写像値が現在の写像に適合している場合には、キャ ッシュエレメントの行又は列全体が用いられず、それらの使用に問題かない。そ れ以外の場合、行又は列を回収する必要がある。キャッシュエレメントの行又は 列全体における原データがファジィバッファに書き込まれ、次に初期化される。

相互参照表における影響を受けたエレメントは新たな写像により更新される。

その後、パッチデータをこれらの新たに回収されたキャッシュエレメント内に書 き込みつる。

キャッシュバッファＣＢからファジィバッファ内への書き込みはバーストモード で行いつる。従って、このようなタスクが生じると、キャッシュエレメントの幾 つかを回収する必要がない場合でも、キャッシュエレメントの数個の隣接行又は 列をファジィバッファに書き込み、再初期化することができる。

補遺６ エツジのファジィ領域の直接計算 １、エツジの式は次式（１）及び（２）で表されるものとする。

ｘ＝ａｚ十ｂ　（１） ｙ　＝　ｃ　ｚ　十ｄ　（２） ２、現在の視点境界ボックス甲の視点Ｐのすべての座標が（ｘＯ、ｙＯ，ｚＯ） であるものとする。

３、Ｐに対するエツジ上の点Ｔ　（ｘ、ｙ、ｚ）のイメージ投影が４、（ｘ、ｙ 、ｚ）及び（ｘ　Ｏ，ｙ　Ｏ，ｚ　Ｏ）は不確実である為、（ｘ、ｙ）のすべて の可能な値 を有する領域かエツジのファジィ領域となる。

５、式（２）を式（４）中に導入し、並へ替えると、次式（５）が得られる。

Ｄｄ−ＤｙＯ＋ＹＺ０ Ｙが分かって、いると、ｙＯ及びＺＯの適切な極値を上記の式中に代入すること により２の極値が得られる。これら極値内のＺを有するエツジ上のすべての点は 現在の視点境界ボックス内の視点からＹに投影しうる。

６、式（１）を式（３）内に代入すると、次式（６）が得られる。

式（６）には、Ｚを変化させるためのＸの局部的な極値がないことに注目すべき である。従って、上記のセクション５から見出したＺの極値とＸＯ及びＺＯの適 切な極値とを式（６）に割り当てることによりＸの２つの極値を見出しつる。こ れらの値はＹの特定値に対する可能な最大及び最小値Ｘに一致する。

７、エツジのファジィ領域を近似させるのに走査線近似を用いつる。式（２）を 式（４）に代入してこれを並べ替えることにより次式（７）が得られる。

ｚ、ｙＯ及びＺＯの適切な極値を式（７）に割り当てることにより、その最大及 び最小値が得られる。これらの値を切り捨てや切り上げ処理して、エツジを投影 しうるすへての走査線をカバーする。上述したセクション５及び６からＸの最大 値及び最小値を見出すことができる。これらの値内の領域がエツジのファジィ領 域の走査線セグメントとなる。このエツジの拡張ファジィ領域の対応するセグメ ントはすべての格子セルを完全にカバーするセグメントを更に丸め処理したもの である。

上述した方法は、Ｘ走査線上の領域のセグメントを走査変換することにより拡張 ファジィ領域を計算する。垂直よりもむしろ水平なエツジの場合、Ｘ走査線上の 領域のセグメントを走査変換することにより拡張ファジィ領域を一層正確に計算 しうるこのことを図１４に示してあり、この図１４では、ファジィ領域がエツジ のファジィ領域を中心とする走査線形状をとる。

これはエツジのファジィ範囲よりも相当小さい。

補遺７ 半立方ピラミッドにおけるパッチの走査変換この補遺７ては、分解能か異なるセ ルを含む平面上のパッチを走査変換するのに有効な技法につき説明する。この技 法は、ラジオシティ法でパッチの形状係数をファジィ投影法を用いたり、又は使 用しないで計算するのに用いることができる。

上記走査変換法は半立方ピラミッドと称するデータ構造を使用する。ピラミッド の各レベルは２Ｄ個を一組とするアレイを包含する。各アレイはピラミッドの各 レベル及び投影面に対応する。アレイの各エレメントは投影面上の画素に対応す る。なお、半立方ピラミッドは立方体状でなく、プリズム状とするのがよく、そ の平面は必ずしもアクティブとする必要はない。

アレイのエレメントをピラミッドエレメントと称する。このエレメントは元の半 立方エレメントに必要とされる情報以外に細分インジケータ及びポインタを含ん でいる。細分インジケータは最初オフ状態にセットしておく。このインジケータ は、そのレベルがエレメントに投影されるパッチの必要な精度レベル以下となる 場合にアクティブとなる。

ポインタは１つのピラミッドエレメントをその領域内における他のピラミッドエ レメントの１つに高精度でリンクさせるのに用いられる。より一層正確なサンプ リングを可能ならしめるために、リンクさせるへきエレメントは、精度レベルが 低いエレメントからのポインタによってアクセスされるエレメントができるだけ 精度レベルが低いエレメントの中心に近づくように選定するのが普通である。

生立方面に相当する半立方ピラミッドの編成法を図１５に示す。

半立方ピラミッドの初期化後にはパッチを精度が低下する順にアクセスして、パ ッチを半立方ピラミッドに走査変換する。

このような順序でパッチをアクセスすることにより、パッチはそれら固有の最適 投影解像度及びパッチがすき間をふさぐことになるパッチの最適投影解像度に等 しいか、又はそれよりも細かく走査変換される。

各投影バッチに対して、その精度レベルに対応する生立方体投影解像度を見つけ る。この解像度に属し、しかもそのパッチを投影した各半立方ピラミッドをアク セスする。

アクセスしたエレメントの精度レベルが既に最高である場合、又はその細分イン ジケータがオン状態にない場合には、現行バッチが、通常の生立方体走査変換に おけるように、エレメントにこれまで記憶された最も近いパッチよりももつと近 い場合に現行パッチのＩＤを現行エレメントに書き込むようにする。

こうした変更が起こる場合には、細分インジケータが既にオン状態にセットされ ているエレメントがアクセスされるまで現行エレメントの先祖を全てアクセスす る。この際、アクセスされた各エレメントの細分インジケータはオン状態にセッ トする。

なお、先祖エレメントの巡回アクセスは、これらのエレメントが見つかった直後 にパッチ投影により全てのエレメントに対して行なうこともてきる。しかし、パ ッチか不可視となる可能性か高い場合には、パッチが接近していることを確かめ た後に循環アクセスを行なう方が有効であり、その理由はパッチが隠れている場 合にはエレメントを巡回アクセスする必要がないからである。

現行エレメントの細分インジケータがオン状態にある場合には、もっと正確な形 状係数評価を必要とするパッチがエレメントに投影されている。従って、現行パ ッチの投影下にある前記エレメントの各娘エレメントをアクセスして、前記計算 を繰り返す。

全ての投影パッチを走査変換した後に全レベルにおけるエレメントを走査する。

これらのエレメントに記憶される投影情報からパッチの各形状係数を計算する。

精度の高い形状係数の計算値、従って半立方の分解能を極めて高くする必要があ る場合には、半立方アレイに相対的に多量のメモリを持たせる必要がある。形状 係数を累算するためのこれらアレイの初期化及び走査処理も費用がかかる。

極めて微細な投影を必要とするパッチは相対的にごく僅かであるから、上述した ような問題点は、高い解像度レベルに相当するアクティブ（細分）エレメントを 記憶するのに空間マトリックスを用いることにより克服することができる。各マ トリックスは一次元アレイとする。アクティブエレメントは、このアレイにおけ る画素位置によりパラメータ化されるハツシング関数により決められる位置に記 憶される。

形状係数の計算はレイ・トレーシングを半立方計算と一緒に用いることにより高 精度に行なうこともできる。それでも全てのパッチは半立方ピラミッド又は通常 の生立方体形状に走査変換される。しかし、形状係数の計算に高精度を必要とす るパッチの走査変換は、これらのパッチにより他のパッチがどれだけブロックさ れるのかを決定するのに用いられるだけである。他のパッチの形状係数は、これ らのパッチからの光線を追跡することにより決定される。

半立方ピラミッドの内容はレイ・トレーシングスピードアップさせるのに用いる ことができる。レイ・トレーシングされるパッチの走査変換中には、バッファに 記憶されている前記パッチに近いパッチがめられる。これをレイ・トレーシング すれば、こうしたパッチかもっと光線を阻止するようになるので、これらのパッ チを先ず光線でテストすることができる。

補遺８ 参考文献 １、　Ａｇｇａｒｗａｌ　Ｊ、に、、　Ｄｙｎａｍｉｃ　５ｃｅｎｅ　Ａｎａｌ ｙｓＩｓ、”　ｉｎ　”Ｉｍａｇｅ　ＳｅｑｕｅｎｃｅＰｒｏｃｅｓｓｌｎｇ　 ａｎｄ　Ｄｙｎａｍｉｃ　５ｃｅｎｅ　Ａｎａｌｙｓｔｓ、”　）Ｉｕａｎｇ、 　Ｔ、　Ｓ、　（Ｅｄｓ、＞　１９W１゜ ５ｏｌｕｔｉｏｎｓ　ｔｈｒｏｕｇｈ　ｔｈｅ　ｕｓｅ　ｏｆ　Ａｎａｌｙｔｌ ｃａｌｌｙ　Ｄｅｔｅｒｍｌｎｅｄ　Ｆｏｒｍ−ｆａｃｔｏ窒刀h。

Ｐｒｏｇｒｅｓｓｉｖｅ　Ｒｅｆｉｎｅｍｅｎｔ　Ａｐｐｒｏａｃｈ　ｔｏ　Ｆ ａｓｔ　Ｒａｄｌｏｓｌｔｙ　Ｉｍａｇｅ１５、Ｈｕｂｓｃｈｍａｎ、　Ｈ，、 Ｚｕｃｋｅｒ、　Ｓ、Ｈ，、”Ｆｒａｍｅ−ｔｏ−Ｆｒａｍｅ　Ｃｏｈｅｒｅｎ ｃｅ　ａｎｄ　ｔｈｅＨｌｄｄｅｎ　５ｕｒｆａｃｅ　Ｃｏｍｐｕｔａｔｉｏｎ ：　Ｃｏｎ５ｔｒａｉｎｔｓ　ｆｏｒ　ａ　Ｃｏｎｖｅｘ　Ｗｏｒｌｄ、”５Ｉ ＧＧＲＡＰ）ｌ　８１．４５−５４゜１６、Ｉｍｍｅｌ、　Ｄ、　Ｓ、、　Ｃｏ ｈｅｎ、　Ｍ、　Ｆ、、　”Ａ　Ｒａｄｊｏｓｌｔｙ　Ｍｅｔｈｏｄ　ｆｏｒ　 Ｎｏｎ−Ｄｉｆｆ浮唐■ Ｅｎｖｊｒｏｎｍ＆ｎｔｓ、”、　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｌｃｓ、　Ｖ ｏｌ、　４．１９８６．　ｐｐ、　＋３３−１４２゜＋７．　ｊａｌｎ、　Ｒ， 、Ｈａｙｎｅｓ　Ｓ、、　”Ｉｍｐｒｅｃｌｓｌｏｎ　Ｉｎ　Ｃｏｍｐｕｔｅｒ 　Ｖｉｓｉｏｎ、”　Ｉｎ　”Ａр魔≠獅モ■■ Ｉｎ　Ｆｕｚｚｙ　５ｅｔｓ、　Ｐｏ５ｓｉｂｉｌｉｔｙ　ａｎｄ　Ａｐｐｌｉ ｃａｔｉｏｎｓ、”　Ｈａｎｇ、　Ｐ、　（Ｅｄ）、　Ｐｌ■獅浮■ Ｐｒｅｓｓ、　１９８３．　ｐｐ、　２１７−２３６゜１８、にａｎａｔａｎｌ 　、に、、　”Ｇｒｏｕｐ−Ｔｈｅｏｒｅｔｌｃａｌ　Ｍｅｔｈｏｄｓ　Ｉｎ　 Ｉｍａｇｅ　Ｕｎｄｅｒｓｔａｎｄhｎｇ、” Ｓｐｒｌｎｇｅｒ　Ｖｅｒｌａｇ、　＋９９０゜１９、にａｕｆｍａｎｎ、　Ａ 、、　”Ｔｈｅｏｒｙ　ｏｆ　Ｆｕｚｚｙ　５ｕｂｓｅｔｓ、　Ｖｏｌ、　ｌ　 、　ＦｕｎｄａｍｅｎｔａｌＴｈｅｏｒｅｔｉｃａｌ　Ｅｌｅｍｅｎｔｓ”、　 Ａｃａｄｅｍｉｃ　Ｐｒｅｓｓ、　＋９７５゜２０、Ｌｌｇｏｍｅｎｌｄｅｓ、 　Ｐ、　Ａ、、　”Ｍｏｄｅｌｌｎｇ　Ｕｎｃｅｒｔａｌｎｔｙ　Ｉｎ　ｌ（ｕ ｍａｎ　Ｐｅｒｃｅｐｔｌ盾氏A”　１ｎ ｌｌＵｎｃｅｒｔａｉｎｔｙ　Ｉｎ　Ｋｎｏｗｌｅｄｇｅ−Ｂａｓｅｄ　Ｓｙｓ ｔｅｍｓ、”　Ｂｏｕｃｈｏｎ、　Ｂ、、　Ｙａｇｅｒ、　q。

（Ｅｄｓ）、　Ｓｐｒｌｎｇｅｒ　Ｖｅｒｌａｇ、　１９８６．　ｐｐ、　３３ ７−３４６゜２１、　Ｌｌｍ、Ｈ，Ｌ、、”Ｆａｓｔ　Ｈｌｄｄｅｎ　５ｕｒｆ ａｃｅ　Ｒｅｍｏｖａｌ　Ｔｈｒｏｕｇｈ　５ｔｒｕｃｔｕｒａ＋Ａｎａｌｙｓ ｉｓ　ａｎｄ　Ｒｅｐｒｅｓｅｎｔａｔｌｏｎ　ｏｆ　０ｂｊｅｃｔｓ　ａｎｄ 　Ｔｈｅｉｒ　Ｃｏｎｔｏｕｒｓ、”　ＣＧＩf８７゜ Ｊａｐａｎ、　＋９８７．　ｐｐ、　７５−８８゜２２、Ｍａｒｋｓ、　ｊ、、 　Ｈａｌｓｈ、　Ｒ，、Ｃｈｒｌｓｔｅｎｓｅｎ、　３．、　Ｆｒ１ｅｄｅｌｌ 、　Ｍ、、　”Ｉｍａｇｅ　ａ獅■ Ｉｎｔｅｒｖｌｓｊｂｌｌｌｔｙ　Ｃｏｈｅｒｅｎｃｅ　ｌｎ　Ｒｅｎｄｅｒｌ ｎｇ”、　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｇｒａｐｈｉｃ■ ＩｎｔＬ！ｒｆｉｃｅ’９０．　Ｔｏｒｏｎｔｏ、　０ｎｔａｒｌｏ、　Ｍａｙ 　１９９０．　ｐｐ、　＋７−３０゜２３、Ｒｅｃｋｅｒ、　Ｒ，Ｊ、、　Ｇｅ ｏｒｇｅ　Ｄ、　Ｈ，、Ｇｒｅｅｎｂｅｒｇ　Ｄ、　Ｐ、、　”Ａｃｃｅｌｅｒ ａｔｌｏｎＴｅｃｈｎｉｑｕｅｓ　ｆｏｒ　Ｐｒｏｇｒｅｓｓｌｖｅ　Ｒｅｆｉ ｎｅｍｅｎｔ　Ｒａｄｊｏｓｌｔｙ、”　Ｐｒｏｃｅｅｄｌｎｇｓ、　P９９０ Ｓｙｍｐｏｓｌｕｍ　ｏｎ　ｆｎｔｅｒａｃｔｌｖｅ　３０　Ｇｒａｐｈｉｃｓ 、　Ｓｎｏｗｂｉｒｄ、　Ｕｔａｈ、　ＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ、　 ｐｇ、　５９−６６゜２４、Ｒｕ５ｐｌｎｊ、　Ｅ、　Ｈ，、”Ａ　Ｎｅｗ　Ａ ｐｐｒｏａｃｈ　ｔｏ　Ｃｌｕｓｔｅｒｉｎｇ、”　？ｎｆｏｒｍａｔｊｏｎＣ ｏｎｔｒｏｌ、　Ｖｏｌ、　ＩＳ、　ｐｐ、　２２−３２゜２５、　５ｌｅｄｌ ｅｃｋｌ、　Ｈ，、５ｌｅｃｌｌｅｃｋａ、　Ｋ、、　５ｋｌａｎｓｋｙ、　Ｊ 、、　”Ｈａｐｐｌｎｇ　Ｔｅｃｈｎｌ曹浮■刀@ｆｏｒ Ｅｘｐｌｏｒａｔｏｒｙ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｔｓ、’Ｉｎ　１ｌＰ ａｔｔｅｒｎ　Ｒｅｃｏｇｎｌｔｌｏｎ　ａｎｄＡｒｔｌｆｊｃｌａｌ　Ｉｎｔ ｅｌｌｉｇｅｎｃｅ、”　Ｇｅｌｓｅｍａ、　Ｅ、　Ｓ、、　Ｋａｎａ＋　Ｌ、 　Ｎ、、　（Ｅｄｓ）。

Ｅｌｓｅｖｌｅｒ　５ｃｉｅｎｃｅ、　１９８Ｂ、　ｐｐ、　２７７−２９９゜ ２６、　５ｌｌｌｌｏｎ、　Ｆ、、　Ｐｕｅｃｈ、　Ｃ，、Ａ　Ｇｅｎｅｒａｌ 　Ｔｗｏ−Ｐａｓｓ　Ｍｅｔｈｏｄ　Ｉｎｔｅｇｒａｔｌｎ■ Ｓｐｅｃｕｌａｒ　ａｎｄ　Ｄｌｆｆｕｓｅ　Ｒｅｆｌｅｃｔｌｏｎ、”　５Ｉ ＧＧＲＡＰ）ｌ　１９８９．　ｐｇ、　３３５−３４４゜２７、　５ｕｂｂａｒ ａｏ、　Ｍ、、　”Ｉｎｔｅｒｐｒｅｔａｔｉｏｎ　ｏｆ　Ｖｌｓｕａｌ　Ｍｏ ｔｌｏｎ：　Ａ　Ｃｏｍｐｕｔａｔｉ盾獅≠■ Ｓｔｕｄｙ、”　Ｐｌｔｍａｎ、　Ｌｏｎｄｏｎ、　１９８８゜ＩＰ ＦＩＧ、　２ １ゞζ ７　ｊＪ　・・ １）　Ｚ ・　：Ｉ り Ｌ宜線了しイ ＡＡ八へ　ＦＩＧ、８Ｂ Ｆｉｇ、　１５ 国際調査報告　−一□Ｎ６ ■ゴ／ＡＩＪ！２／ｌ）１３１１２ ＦａｒｍＰＣＴｌＩＳＡ／２１０ｆｅａｎ＋ａ＋ｕｕ＋ｉｏ＋＋ｏｆ６１１ｔｈ ｅｍイ２１１ｆｌｕｌｙ１９９２１ｃｏすす・ｃ国際調査報告　１−−ａ□Ｎ。

ＰＣＴＩＡＩｌｊシ１東■２ ＦＯｒｍＫＴＩ１５Ａ／２蔦０＋ｅｏｎｕ＋ｉｕｍｏｎｏｒ＋ｅｔｂｍＩ−にＪ ｕｌｙ１９９２１ｗ＠ｔｅａ国際調査報告　□°ＰＰ″″′″″０゜ＰＣｒｌＡ υｔｚｍｍ Ｔｈｉｓ　Ａｎｎｅｘ　ｈｓｔｓ　ｔｈｅ　ｋｎｏｗｎ　”Ａ”　ｐｕｂｌｉｃ ａｔｉｏｎ　１ｅｖｅｌ　ｐａｍｌ　ｆｍｉｌｙ　ｍｅｍｂ■窒刀@ｒｅｌａｔ ｉｎｇ　Ｉｏ出ｅ、ｐａｌｅｎｌ　ｄｏｃｕｍｅｎｔｓｃｉｔｅｄ　ｉｎ　ｔｈ ｅ　ａｂｏｖｅ−ｍｅｎｕｏｎｃｄ　ｔｎｐｍａｔｉｏｔｉｍ　ｓｍｒｃｈ　ｒ ｅｐｏｒｔ、　Ｔｈｅ＾ｕｓｔｒｓiｓａｎ　Ｐａｍｔ　０ｆｆｉｃｅ　ｒｓ　 ＋ｎ　ｎｏ　ｗａｙ　１ｉａｂｌｅｆｏｒ　ｔｈｅｓｅ　Ｐｒ１１ｃｕｌａｎ　 ｗｈｉｃｈ　ｕｅ　ｍｅｒｅｌｙ　ｇｉｖｅｎ　ｆｏｒ　ｔｈｅ　ｐｕｒｐｏｓ ｅ　ｏｆ　ｉｎ■盾窒獅浮浮盾■ Ｆａｒｍ　Ｐσ閏５Ａ７２ＨＸｐａ＋ａ＊　ｌｍ１ｌｙ　ａｎｎａｘ×ｊｕ１７ １９９２１　ｅｏｐ４ｍ

Claims (1)

1. 【特許請求の範囲】 １．イメージを発生させる多次元コンピュータの生産に要求される、すなわち多 次元データを、少なくとも１次元少ない多次元データに減少させるのに要求され る可視性計算の複雑度の減少させるのに当たり、以下の工程を有することを特徴 とする可視性計算の複雑度減少方法。 （１）（それ自体既知の）閉塞すなわち不可視性関係計算を、計算されるべき選 択された視点から複数の表面で実行する前に、これらの視点を群に分割する。 （２）前記表面の選択されたものの幾つかに対して、前記選択された表面が、 （ａ）常に閉塞されていない表面、常に隠された表面、又はそれ以外の表面であ るか、 （ｂ）常に閉塞されていない表面又はそれ以外の表面であるか、又は （ｃ）常に隠された表面又はそれ以外の表面であるか、どうか前記群それぞれに 対して決定する。前記それ以外の表面を、閉塞されていない又は隠されていない かどうかを確実に決定できない表面とする。 （３）常に閉塞されていない又は常に隠された表面の前記閉塞、すなわち不可視 性関係計算を免除する。 （４）前記それ以外の表面の記録を保持する。 （５）前記閉塞、すなわち不可視性関係計算を前記それ以外の表面で行う。 ２．前記工程（４）において、前の記録を更新することを特徴とする請求の範囲 １記載の可視性計算の複雑度減少方法。 ３．前記工程（４）において、新しい記録を形成することを特徴とする請求の範 囲１記載の可視性計算の複雑度減少方法。 ４．前記イメージを、グラフィックイメージ、コンピュータ視覚データ、抽象デ ータ及び物理データからなる群から選択することを特徴とする請求の範囲１記載 の可視性計算の複雑度減少方法。 ５．複雑度の減少が、可視性計算の回数及び／又は継続時間の減少を伴うことを 特徴とする請求の範囲１記載の可視性計算の複雑度減少方法。 ６．前記可視性計算が、一連のラジオシティ計算の一部を形成することを特徴と する請求の範囲１記載の可視性計算の複雑度減少方法。 ７．前記工程（３）が、前記閉塞されていない表面の直接計算を伴うことを特徴 とする請求の範囲６記載の可視性計算の複雑度減少方法。 ８．前記表面の一つ又はそれ以上を、最初の表面の部分集合とすることを特徴と する請求の範囲１記載の可視性計算の複雑度減少方法。 ９．請求の範囲１の工程に加えて、以下の工程を有することを特徴とする可視性 計算の複雑度減少方法。 （６）前記表面の選択されたものの各境界に対して、前記境界のエッジを見るこ とができる視野方向を表す境界区域を規定する前記境界の範囲を決定する。 （７）前記表面の選択されたものの結合された投射を決定するとともに、前記選 択された表面それぞれの境界エッジの結合された投射を決定する。 （８）前記結合された表面投射から前記結合された境界エッジ投射を除去し、前 記選択された表面それぞれの影領域を形成する。 （９）前記選択された表面それぞれの前記影領域及び前記結合された投射の前記 閉塞すなわち不可視性関係計算を行う。 １０．前記境界区域を、前記選択された表面のいずれかの走査線表示に一致させ ることを特徴とする請求の範囲９記載の可視性計算の複雑度減少方法。 １１．前記結合された表面投射を、前記群の視点から見えるように、対応する表 面の投射区域よって置換することを特徴とする請求の範囲９又は１０記載の可視 性計算の複雑度減少方法。 １２．前記可視性計算を、閉塞すなわち不可視関係計算を行わずに、前記現在の 視点群、及び前記現在の視点群から観察される際のより浅い深さで隣接する表面 が存在することからの深さの結果、全体的に隠された表面区域を検出することに より、さらに簡単にし、前記全体的に隠された表面区域の検出が以下の工程を有 することを特徴とする請求の範囲１１記載の可視性計算の複雑度減少方法。 （１０）視野方向の対応する表面の投射表面に深さ平面を割り当てる前記視点群 に関連する視野方向の範囲それぞれに対して、前記投射表面の各エレメントが、 対応する前記表面区域を観察する群中の視点に関連する複数の深さ値を有するよ うにする。 （１１）前記表面区域それぞれに対して、前記各エレメントの深さ値を選択かつ 記憶して、前記投射表面の深さ値を規定し、その結果前記影領域の深さ値を表示 する。 （１２）前記結合された表面投射の深さ値を同様に決定する。 （１３）前記影領域の深さ値と、前記結合された表面投射の深さ値とを比較し、 前記影領域の深さ値が小さい場合、前記結合された表面投射を形成する表面が全 体的に隠れていると考える。 １３．前記工程（１１）において、前記エレメントそれぞれに投射された表面の 近似された最大深さ値の最小値を選択することを特徴とする請求の範囲１２記載 の可視性計算の複雑度減少方法。 １４．前記工程（１２）において、前記エレメントそれぞれの最小の取りうる深 さ値を選択することを特徴とする請求の範囲１２記載の可視性計算の複雑度減少 方法。 １５．前記可視性計算を、閉塞すなわち不可視性関係計算を行わずに、全体的に 閉塞された表面区域を検出することにより、さらに簡単にし、前記全体的に閉塞 された表面区域の検出が以下の工程を有することを特徴とする請求の範囲１記載 の可視性計算の複雑度減少方法。 （１４）工程（５）を行う前に、前記表面の選択されたもののそれぞれすなわち 表面エレメントに対して結合された投射を形成及び記憶し、記憶された前記結合 された投射の各エレメントに対して、前記エレメントが以下のいずれかであるこ とを示す。 （ａ）前記選択された表面のいずれかの前記結合された投射内に存在する。 （ｂ）前記選択された表面の一つのみの前記結合された投射内に存在する。 （ｃ）前記選択された表面の二つ以上の前記結合された投射内に存在する。 （１５）前記選択された表面それぞれの前記結合された投射を走査し、前記工程 （１４（ｂ））によって示された一投射に対するすべてのエレメントにおいて、 このように投射された前記表面を全体的に閉塞すると考える。 １６．前記表面を、詳細のレベルの変化によって表された階層に配置することを 特徴とする請求の範囲１記載の可視性計算の複雑度減少方法。 １７．３次元的な抽象又は物理的表面からなる環境における演算に関連する可視 性を減少させるのに当たり、以下の工程を有することを特徴とする可視性減少方 法。 （１）（それ自体既知の）可視性計算を行う前に、幾つか又はすべての視点すな わち存在しうる視点の発生を、視点群に分類する。 （２）一つ又はそれ以上の（それ自体既知の）表面を、この表面すなわち視点群 に関連する表面エレメントの同時的な投射を発生させるために、規定する。 （３）選択された表面に対して、及び各視点群に対して、これらの選択された表 面すなわちこれらの表面エレメントが、これらの投射写像すなわち前記投射表面 への同時的な投射を計算かつ比較することにより、前記視点群に対して常に不可 視であるかどうかを決定する。 （４）前記視点群に対して常に不可視である幾つかの又はすべての表面すなわち 表面エレメントを、実際の可視性すなわち前記群中の幾つかの又は全ての視点に 対する計算に関連する可視性中に無視又は特別に取り扱う。 １８．可視性、ラジオシティ又は３次元的な抽象又は物理表面からなる環境にお ける計算に関連する可視性を減少させるに当たり、以下の工程を有する可視性減 少方法。 （１）（それ自体既知の）可視性計算を行う前に、幾つか又はすべての視点すな わち存在しうる視点の発生を、視点群に分類する。 （２）一つ又はそれ以上の（それ自体既知の）表面を、この表面すなわち視点群 に関連する表面エレメントの同時的な投射を発生させるために規定する。 （３）前記投射表面のそれぞれを規則的又は不規則的な格子に分割する。 （４）前記格子に投射を記憶するためにコンピュータのメモリを組織するデータ 構造を規定する。 （５）選択された表面すなわち表面エレメントそれぞれに対して、及び各視点群 に対して、前記表面すなわち前記表面エレメントを前記投射表面に同時に投射し 、投射下にある格子セルを計算する。 （６）前記視点群に対して常に不可視である表面エレメントを、実際の可視性す なわち前記群中の幾つかの又は全ての視点に対する計算に関連する可視性中に無 視又は特別に取り扱う。 １９．イメージデータを発生させるコンピュータに記憶させるに当たり、以下の 工程を有することを特徴とするコンピュータ記憶方法。 （１）選択された視点群に対して可視である複数のイメージ部分を特定する。 （２）予め設定されたイメージの特性を有する前記イメージ部分を選択し、組織 化された記憶構造に前記イメージ部分を記憶する。 （３）前記選択されたイメージ部分の最初の一つに対して、部分識別子を割り当 て、これを最初の一つの前記イメージデータとともに記憶する。 （４）残りの前記選択されたイメージ部分に対して、異なる値の識別子を計算し 、この識別子を前記選択された部分の対応するイメージデータとともに記憶する 。この場合、あらゆる前記選択された部分は、前記部分識別子及び１個又はそれ 以上の異なる値の識別子によってアドレス可能である。 ２０．計算された前記異なる値の識別子が、前記残りの選択された部分と前記最 初の選択された部分との間のアドレスの異なる値を表すことを特徴とする請求の 範囲１９記載のコンピュータ記憶方法。 ２１．前記計算された異なる値の識別子が、前記残りの選択された部分及び他の 前記残りの選択された部分との間のアドレスの異なる値を表し、前記残りの選択 された部分の一つが、前記残りの選択された部分と前記最初の選択された部分と の間のアドレスの異なる値を表す計算された異なる値の識別子を有することを特 徴とする請求の範囲１９記載のコンピュータ記憶方法。 ２２．前記記憶構造を隣接させないことを特徴とする請求の範囲１９記載のコン ピュータ記憶方法。 ２３．前記記憶構造を結合されたリストとすることを特徴とする請求の範囲２２ 記載のコンピュータ記憶方法。 ２４．前記記憶構造を隣接させることを特徴とする請求の範囲１９記載のコンピ ュータ記憶方法。 ２５．前記記憶構造をアレイとすることを特徴とする請求の範囲２２記載のコン ピュータ記憶方法。 ２６．前記イメージ部分を、イメージデータの複数の組を付与するために、複数 の前記予め設定されたイメージ特性に基づいて記憶し、あらゆる組のあらゆるエ レメントを、他の視点群からの視野に基づいて処理することができることを特徴 とする請求の範囲１９記載のコンピュータ記憶方法。 ２７．前記処理が、組へのエレメントの追加、組からのエレメントの削除、又は ２若しくはそれ以上の間でのエレメントの複写を伴うことを特徴とする請求の範 囲２６記載の記憶方法。 ２８．複数の前記予め設定されたイメージ特性を利用可能とし、最小の前記複数 の一つ少ない対応する組を保持し、残りのものを重複させることを特徴とする請 求の範囲２７記載の記憶方法。 ２９．イメージを発生させる多次元コンピュータの生産に要求されるすなわち多 次元データを少なくとも１次元少ない多次元データに減少させるのに要求される 計算の複雑度を減少させるに当たり、以下の工程を有することを特徴とする計算 の複雑度減少方法。 （１）複数の視点を有する物体表面を観察し、前記視点それぞれに対する投射表 面を規定する。 （２）作業表面を形成し、前記投射表面のそれぞれをこの作業表面に写像する。 （３）結合された領域を、少なくとも投射表面の一つを有する前記作業表面で計 算する。 ３０．前記工程（３）を行う前に、 （４）前記視点のすべてを有する容積を計算することにより、前記視点を近似し 、 前記工程（３）において、この容積をすべての前記視点を近似するために用いる ことを特徴とする請求の範囲２９記載の計算の複雑度減少方法。 ３１．イメージを発生させる多次元コンピュータの生産に要求されるすなわち多 次元データを少なくとも１次元少ない多次元データに減少させるのに要求される 計算の複雑性を減少させるに当たり、以下の工程を有することを特徴とする計算 の複雑度減少方法。 （１）複数の視点を有する物体表面を観察し、前記視点それぞれに対する投射表 面を規定する。 （２）作業表面を形成し、前記投射表面のそれぞれをこの作業表面に写像する。 （３）すべての写像を有する領域を計算する。 ３２．前記工程（３）を行う前に、 （４）前記視点のすべてを有する容積を計算することにより、前記視点を近似し 、 前記工程（３）において、この容積をすべての前記視点を近似するために用いる ことを特徴とする請求の範囲３１記載の計算の複雑度減少方法。 ３３．前記残りの表面に対する前記計算を、以下の工程によって更に減少させる ことを特徴とする請求の範囲１２記載の計算の複雑度減少方法。 （１６）前記残りの表面の形状係数の計算によって到達されるように要求される 複数の精度レベルを設定する。 （１７）前記精度レベルの一つを前記常に閉塞された表面のそれぞれ、前記常に 隠された表面のそれぞれ、及び前記結合された投射のエレメントのそれぞれに割 り当てる。 （１８）前記結合された投射の対応するエレメントの精度レベルが、前記表面そ れぞれの精度レベルより大きい場合、前記表面それぞれの精度レベルを前記結合 された投射の対応するエレメントの精度レベルに更新し、次に、前記表面のそれ ぞれを、最高の精度レベルを有するものから開始して、最低の精度レベルを有す るもので終了する順序で走査変換する。更新された精度レベルは、前記表面それ ぞれに対する形状係数の計算に対する精度の最大レベルを表す。 （１９）前記表面それぞれに対する前記更新された精度レベルが、前記表面に付 与されうる精度レベルより高いかどうかを決定し、高い場合には、対応する前記 表面を複数の副表面に再分割し、この再分割を、前記副表面の対応する精度レベ ルが前記表面の精度レベルと一致するまで行う。 ３４．前記形状係数計算を、レイ・トレーシング法又は半立法法（それら自体は 既知）を用いて行うことを特徴とする請求項３３記載の計算の複雑度減少方法。 ３５．イメージを発生させる多次元コンピュータの複数の表面を走査変換するに 当たり、以下の工程を有することを特徴とする表面走査変換方法。 （１）複数の２次元アレイを具えるデータ構造を形成する。この場合、前記アレ イそれぞれは、視点から観察されるような前記表面の投射に対する対応する精度 レベルに関連するものである。また、前記配列それぞれのエレメントを投射平面 上の画素とする。 （２）前記エレメントそれぞれに対して、関連する細分インディケータを設け、 この細分インディケータが、対応する前記エレメントのアクティブ細分を示すよ うに適合させる。 （３）前記細分インディケータそれぞれをＯＦＦに初期化する。 （４）前記表面それぞれの各パッチに対して、同様に所望の精度を規定するとと もに、精度の減少する順序で前記パッチを含む投射を、前記データ構造の対応す るエレメントに走査変換し、最高の精度レベルの前記エレメントそれぞれに対す る細分インディケータを、前記エレメントが前記パッチの一つに相当する場合、 ＯＮに設定する。 （５）前記表面のエレメントそれぞれに対して、前記細分インディケータがＯＮ の場合、投射下の前記エレメントのサブエレメントをアクセスする。前記細分イ ンディケータがＯＮでない場合、前記パッチの深さが前記サブエレメントに記憶 された深さより小さいときには、前記パッチを前記エレメントの形態で更新する 。 （６）前記エレメントそれぞれをアクセスし、形状係数の寄与を、前記パッチの 記録の形状係数に加える。なお、前記パッチ自身の識別子は前記パッチに記憶さ れている。 ３６．上述した請求の範囲のいずれか一つに記載された請求の範囲の方法を行う ためのプログラム制御によって適合される際のコンピュータシステム。