(57)【特許請求の範囲】
【請求項１】
セントラル・プロセッシング・ユニットと、
グラフィカル・プロセッシング・ユニットと、
データと実行可能命令を格納するメモリに接続するプロセッシング・ユニットと、
を備え、
前記メモリが、
各レベルがさまざまな詳細レベルで地形を表現する複数レベルの正規グリッドの描写データと、
前記複数レベルの正規グリッドに対応する、少なくとも１つの遷移領域の描写データと、
前記複数のレベルの部分を、視点からの距離の関数として詳細レベルを下げるネストされた正規グリッドの集合にネストするための実行可能命令とを備えるレンダリング・コンポーネントと、
を備え、
前記正規グリッドの複数の頂点が、ｘ，ｙ，ｚ及びｚＣ座標を含み、当該ｚ座標が、詳細なレベルに対する地形標高値を表し、ｚＣ座標が、次の詳細なレベルに対するｘ，ｙ座標におけるｚ座標を表し、
前記遷移領域が、前記正規グリッドの少なくとも１つの外側の境界の近くに存在し、
ｚＣ値及びｚ値が、融合値αと共に用いられ、当該融合値αが、前記遷移領域における対応するｘ，ｙ座標における地形標高を表すｚとｚＣの間のｚ’値を決定するために、前記遷移領域における遷移モーフィングにおける０から１の評価を表し、
前記ｚ’値が、式：
ｚ’＝（１−α）ｚ＋αｚＣ
によって決定され、
前記複数レベルの正規グリッドが、頂点の２次元配列であり、各次元が、サイズｎのレベル内であり、
前記レベル内の前記少なくとも１つの遷移領域が、式：
ｗ＝min（ｎ/10，min＿width）
によって決定される幅ｗで表現され、
min＿width＞＝２であり、
遷移モーフィングｚ’の計算が、前記グラフィカル・プロセッシング・ユニットで行われる、
ことを特徴とするコンピュータ・システム。
【請求項２】
前記複数レベルの正規グリッドは、テクスチャ・イメージをさらに備えることを特徴とする請求項１に記載のコンピュータ・システム。
【請求項３】
前記レンダリング・コンポーネントが、更に、複数レベルのネストされた正規グリッドの集合間で融合するための、実行可能な命令を備える、
請求項１に記載のコンピュータ・システム。
【請求項４】
前記レンダリング・コンポーネントは、前記地形に対して前記視点が移動するに連れて、前記ネストされた正規グリッドの集合を徐々に入れ替えるための実行可能命令をさらに備えることを特徴とする請求項３に記載のコンピュータ・システム。
【請求項５】
前記レンダリング・コンポーネントは、前記ネストされた正規グリッドの集合を徐々に入れ替える際に、地形シェーディングの法線マップを作成するための実行可能命令をさらに備えることを特徴とする請求項４に記載のコンピュータ・システム。
【請求項６】
地形についてのさまざまな詳細レベルを備える複数の正規グリッドからなる描写データを提供すること、
前記地形に対する視点を決定すること、および
前記視点からの距離が増大するにつれて前記ネストされた正規グリッド・レベルの詳細レベルが低下するように、複数の正規グリッドから選択された、ネストされた正規グリッドの集合を作成すること、
を備える方法を実行するためのコンピュータ実行可能命令を備え、
前記正規グリッドが、２次元であり、各次元が等しいサイズであり、
ネストされた正規グリッドの集合の中で遷移領域を生成し、当該遷移領域が、前記正規グリッドの外側の境界に近く、
所定の正規グリッドの少なくとも１つの遷移領域が、幅ｗを持ち、当該ｗが式：
ｗ＝min（ｎ/10，min＿width）
によって決定され、
min＿width＞＝２であり、
ｎ＝前記領域の次元のサイズ、
であり、
少なくとも１つの正規グリッドの頂点が、ｘ，ｙ，ｚ及びｚＣ座標を含み、当該ｚ座標が、レベルに対する標高値を表し、ｚＣ座標が、論理的に隣接するレベルの地形標高値を表し、
前記少なくとも１つの正規グリッドに対応する前記遷移領域内の遷移モーフィングにおいて、ｚＣ値がｚ値及び融合値αと共に用いられて、ｚ’座標が用いられて、前記遷移領域での各ｘ，ｙ座標における前記地形標高を表現するようにされ、
前記ｚ’座標が、式：
ｚ’＝（１−α）ｚ＋αｚＣ
によって決定される、
ことを特徴とするコンピュータ可読媒体。
【請求項７】
前記方法は、前記ネストされた正規グリッドの集合の各レベル間で地形の標高値を、レベルの境界でより細かい詳細レベルの標高値がより粗い詳細レベルに近付くように、融合する（blending）こと、をさらに備えることを特徴とする請求項６に記載のコンピュータ可読媒体。
【請求項８】
前記方法は、前記地形に対して前記視点が移動するに連れて、前記ネストされた正規グリッドの集合を徐々に入れ替えることをさらに備える、ことを特徴とする請求項６に記載のコンピュータ可読媒体。
【請求項９】
前記ネストされた正規グリッドの集合に含まれる各レベルは、２次元正規グリッドであり、各次元が、ｎのサイズであり、各レベルが、連続的な２のべき乗の解像度で低下する
ことを特徴とする請求項８に記載のコンピュータ可読媒体。
【請求項１０】
前記論理的に隣接するレベルが、次の、より粗いレベルである、請求項６に記載のコンピュータ可読媒体。
【請求項１１】
前記遷移モーフィングが、次の、より粗い、論理的に隣接するレベルのダウンサンプルされた値に遷移する、前記複数の頂点の部分を含む、請求項６に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にさまざまな詳細レベル（level of detail）による地形レンダリングの分野に関する。
【背景技術】
【０００２】
既存の地形の詳細レベル（ＬＯＤ：level-of-detail）アルゴリズムでは、メッシュ詳細化操作（mesh refinement operations）の階層を使用してサーフェス・テッセレーション（surface tessellation）を適用する。こうしたアルゴリズムは、このような階層構造によって分類できる。
【０００３】
【非特許文献１】Cohen-Or, Daniel, et al., Temporal Continuity of Levels of Detail in Delaunay Triangulated Terrain, IEEE Visualization 1996, 37-42
【非特許文献２】Cignoni, P. et al. Representation and Visualization of Terrain Surfaces at Variable Resolution, The Visual Computer 13(5), 199-217, 1997
【非特許文献３】Rabinovich, Boris, et al, Visualization of Large Terrains in Resource-Limited Computing Environments, IEEE Visualization 1997
【非特許文献４】De Floriana E. et al., Building and Traversing a Surface at Variable Resolution, IEEE Visualization 1997, 103-110
【非特許文献５】Hoppe, Hugues, Optimization of Mesh Locality for Transparent Vertex Caching, ACM SIG-GRAPH , 1999, 269-276
【非特許文献６】El-Sans, Jihad, et al., Generalized View-Dependent Simplification, Proceedings of Eurographics, 1999, 83-94
【非特許文献７】Lindstrom, Peter, et al., Real-Time, Continuous Level of Detail Rendering of Height Fields, ACM SIGGRAPH 1996, 109-118
【非特許文献８】Duchaineau, Mark, et al., Roaming Terrain: Real-time Optimally Adapting Meshes, IEEE Visualization 1997, 81-88
【非特許文献９】Pajarola, Renato, Large Scale Terrain Visualization Using the Restricted Quadtree Triangulation, IEEE Visualization 1998, 19-26
【非特許文献１０】Rottger, Stefan, et al., Real-time Generation of Continuous Levels of Detail for Height Fields, Central Europe Conf. on Computer Graphics and Vis., 315-322
【非特許文献１１】Blow, Jonathan, Terrain Rendering at High Levels of Detail, Game Developers Conference 2000
【非特許文献１２】Levenberg, Joshua, et al., Fast View-dependent Level-of-Detail Rendering Using Cached Geometry, IEEE Visualization 2002, 259-266
【非特許文献１３】Cignoni, P. et al., BDAM -- Batched Dynamic Adaptive Meshes for High Performance Terrain Visualization, Computer Graphics Forum 22(3) 2003
【非特許文献１４】Cignoni, Paulo, et al., Planet-sized Batched Dynamic Adaptive Meshes (P-BDAM), IEEE Visualization 2003
【非特許文献１５】Bishop, Lars, et al., Designing a PC Game Engine, IEEE CG&A 18(1), 46-53 1998
【非特許文献１６】De Boer, Willem, Fast Terrain Rendering Using Geometrical Mipmapping, http://www.flipcode.com/tutorials/geomipmaps.pdf, dated October 2000
【非特許文献１７】Wagner, Daniel, 2004, Terrain Geomorphing in the Vertex Shader, In ShaderX2: Shader Programming Tips & Tricks with DirectX 9, Wordware Publishing 2004
【非特許文献１８】Gumhold, Stefan, et al., Multiresolution Rendering with Displacement Mapping, Graphics Hardware Workshop 1999
【非特許文献１９】Dogget, Michael, et al., Adaptive View-dependent Tessellation of Displacement Maps, Graphics Hardware Workshop, 2000
【非特許文献２０】Moule, Kevin, et al., Efficient Bounded Adaptive Tessellation of Displacement Maps, Graphics Interface, 2002
【非特許文献２１】Dollner, Jergen, et al., Texturing Techniques for Terrain visualization, IEEE Visualization 2000, 227-234
【非特許文献２２】Tanner, Christopher C, et al., The Clipmap: A Virtual Mipmap, ACM SIG-GRAPH 1998, 151-158 ("Tanner 1998")
【非特許文献２３】Williams, Lance., Pyramidal Parametrics, ACM SIGGRAPH 1983, 1-11
【非特許文献２４】Kobbelt, Leif, Interpolatory Subdivision on Open Quadrilateral Nets with Arbitrary Topology, Eurographics 1996, 409-420
【非特許文献２５】Dyn, Nira, A 4-point Interpolatory Subdivision Scheme for Curve Design, CAGD 4, 257-268 1987
【非特許文献２６】Malvar, Henrique., Fast Progressive Image Coding without Wavelets, Data Compression Conference 2000, 243-252
【非特許文献２７】Fournier, Alain, et al., Computer Rendering of Stochastic Models, Comm. of the ACM 25(6), 371-384, 1982
【非特許文献２８】Lewis, J.P, Generalized Stochastic Subdivision, ACM Transactions on Graphics 6(3), 167-190, 1987
【非特許文献２９】Wei, Li-Yi. et al., Fast Texture Synthesis Using Tree-structured Vector Quantization, ACM SIGGRAPH 2000, 479-488
【非特許文献３０】Miller, Gavin, The Definition and Rendering of Terrain Maps, Vol. 20, No. 4, ACM SIGGRAPH 1986, 39-48
【非特許文献３１】Gu, Xianfeng, et al., Geometry Images, ACM SIGGRAPH 2002, 355-361
【非特許文献３２】Hoppe, Hughes; Smooth View-Dependent Level-of-Detail Control and its Application to Terrain Rendering; undated; 9 pages.
【非特許文献３３】lindstrom, Peter, et al.; Terrain Simplification Simplified: A General Framework for View-Dependent Out-of-Core Visualization; IEEE Transactions on Visualization and Computer Graphics, Vol. 8, No. 3, July-September 2002; pages 239-254.
【非特許文献３４】Vlachos, Alex, et al.; Curved PN Triangles; undated; 8 pages.
【非特許文献３５】Lefebvre, Sylvain, et al.; Pattern Based Procedural Textures; undated; 11 pages.
【非特許文献３６】Losasso, F., et al.; Smooth Geometry Images; Eurographics Symposium on Geometry Processing (2003); 8 pages.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
たとえば、不規則三角形網（triangulated irregular networks）などの不規則メッシュ（irregular meshes）は、特定の数の三角形面としては地形の適切な近似を提供する、しかし、隣接するメッシュを追跡したり、詳細化依存状態（refinement dependencies）を追跡したりする必要がある。一部の階層では、Ｄｅｌａｕｎａｙ（ドローネー）三角形分割法（Delaunay triangulations）（たとえば、非特許文献１、非特許文献２、非特許文献３を参照）、あるいは他の任意の接続性（arbitrary connectivities）（たとえば、非特許文献４、非特許文献５、非特許文献６を参照）を使用している。
【０００５】
最長エッジ２分割（longest-edge bisection）、限定された四分木（restricted quadtrees）、直角三角形の階層などのビンツリー階層（Bin-tree hierarchies；２分木階層）では、直角三角形の再帰的２分割（recursive bisection）を使用してメモリ・レイアウトとトラバース（traversal）アルゴリズムを簡素化する。しかしながら、こうした半正規メッシュ（semi-regular meshes）では、依然としてポインタ・ベースのデータ構造と直接モードのレンダリング（immediate-mode rendering）を必要とする（たとえば、非特許文献７、非特許文献８、非特許文献９、非特許文献１０、非特許文献１１を参照）。
さらに、ビンツリー領域はビンツリー構造に関連付けられた領域に対する比較的粗いリファイン操作を定義し、あらかじめ計算した三角形領域が、ビデオ・メモリにキャッシングされたバッファにアップロードされるので、レンダリング・スループットが向上する。しかしながら、キャッシングは時間コヒーレンシのために、地形モーフィング（geomorphs）の使用を妨げる。たとえば、非特許文献１２、非特許文献１３、非特許文献１４を参照されたい。他に、ビュー依存のマッピング（view dependent mapping）についても多くの方法が提供されている。たとえば、非特許文献１５、非特許文献１６、非特許文献１７、非特許文献１８、非特許文献１９、非特許文献２０を参照されたい。他に、テクスチャ・マップ（texture maps）についての方法も提供されている。たとえば、非特許文献２１、非特許文献２２を参照されたい。
【課題を解決するための手段】
【０００６】
ここで説明する技術により、コンピュータによる地形レンダリングにおけるさまざまな詳細レベルについての製品、方法、システムが提供される。１つの例において、地形レンダリングはここで説明するジオメトリ・クリップマップ（geometry clipmaps）という技術を使用して行われる。ジオメトリ・クリップマップは、いくつかの点で従来の方法とは異なっている。詳細化階層（refinement hierarchy）は、地形モーフィングがレベル間の連続性を提供する状態で、ネストされた、ビューア中心の、正規グリッドの集合で構成される。詳細化基準では、他にビューアの距離も考慮されるが、局所的なサーフェス・ジオメトリ（surface geometry）は無視される。ジオメトリ・クリップマップは、速度と時間の両方においてレベル間の連続性を単純かする、ビューアを中心とした階層を定義する。
【０００７】
１つの例において、地形の複数の詳細レベルはメモリ内に正規グリッドとして格納される。こうした１つの例では、ビューポイントからの距離の関数として、複数のレベルからの得られた、ネストされた正規グリッドの集合の形で地形がキャッシングされる。地形に対して視点が移動する場合、ネストされた正規グリッドは、地形内の視点の移動に伴って徐々に入れ替えられる。こうした例の１つでは、遷移領域（transition region）を導入してグリッド・レベル間の融合（blending）を支援する。１つの例において、正規グリッドは頂点バッファとしてビデオ・メモリに格納される。こうした例の１つでは、頂点データ・セットに別のグリッド・レベルの標高（elevation）値を提供して効率的に境界を融合する。
【０００８】
別の例では、コンピュータ・システムはさまざまなレベルで地形を表現する複数レベルの正規グリッドを提供する。こうした例では、レンダリング・コンポーネントは、正規グリッドの一部を、視点からの距離に基づいて、詳細さに関して低減する、ネストされた正規グリッドに、構成する。複数の詳細レベルを有する地形レンダリングのその他の多くの例とバリエーションについて説明する。
【０００９】
その他の機能や利点については、以下の発明を実施するための最良の形態と添付の図面を関連付けることで明らかになるであろう。
【発明を実施するための最良の形態】
【００１０】
（概観）
地形ジオメトリ（Terrain geometry）は、アウト・ドア・グラフィック環境の重要なコンポーネントであり、たとえば、映画、バーチャル環境、地図作成（cartography）、ゲームで使用される。特に、リアルタイムのアウト・ドア・ゲームには、フライト・シミュレータ、運転シミュレータ、大規模なマルチ・プレーヤー・ゲームが含まれる。この技術は、地形のハイト・フィールド（terrain height-fields）のリアルタイム・レンダリングに照準を合わせており、地形イメージ・レンダリングの効果的な働きを提供する。
【００１１】
ネストされた正規グリッドの形のジオメトリ・クリップマップを使用した地形レンダリングの例を示すために、実際の地形の正規グリッドが使用される。ただし、仮想的な地形の正規グリッドも全く同様に動作する。たとえば、１つの例示的なデータ・セットは正規グリッド内に３０ｍごとの標高サンプルを格納する米国のハイト・フィールドマップである。
【００１２】
図１は、クリップマップのレベルを表す図である。この例では、レベル１０２は地形の最も細かい詳細レベルであり、地形のより粗い詳細レベルが中間のレベルとして１０４に作成されている。最後に最も粗いレベル１０６に達する。地形レベルのコーナーの矢印は、任意の地形のサイズが非常に大きいことを示している。たとえば、米国のデータ・セットには２１６，０００×９３，６００の標高サンプルが含まれる。地形内の標高は、特定の地形レベルの頂点１０８、１１０で表される。より粗い地形レベル１０４、１０６は、ビューアから離れているが見える地形の標高がビューアから近い場所の地形の標高と同じ詳細レベルである必要はないため、効率が向上する。地形図（terrain maps）の頂点は、地形内のサーフェスを作成するのに使用される。たとえば、正方形のサーフェスは、頂点ａ、ｂ、ｃ、ｄで定義される標高のサンプルで定義される。より細かい詳細レベルでより多くの標高のサンプル（すなわち頂点）を提供することで、地形をより詳細に表現する、より精密なサーフェスを作成できる。たとえば、三角形サーフェス（三角形メッシュとも呼ばれる）は頂点ａ、ｂ、ｄで表現される。テクスチャ・イメージがこうしたサーフェスに適用され、メッシュサーフェスにテクスチャを提供する。
【００１３】
地形内で視点が移動すると、視点に最も近い地形の標高とテクスチャが地形のより細かい詳細レベルでレンダリングされ、視点からの距離が増すにつれて地形の標高とテクスチャの詳細はより粗いレベルで得られる。
【００１４】
１つの例では、ジオメトリ・クリップマップのレベルの部分は頂点バッファとして高速のビデオ・メモリに格納され、視点が移動するにつれて徐々に入れ替えられる。このことは、視覚的な連続性、一定のフレームレート（frame rate）、複雑性の抑制（throttling）、および適切なデグラデーション（degradation）を提供する。
【００１５】
大規模な地形ハイトマップ（terrain height maps）には、多くの場合、対話方式でリアルタイムにレンダリングするには非常に多くの標高サンプルが含まれる。さらに、密集した三角形を均一にレンダリングすると、サンプルからピクセルへのフィルタを適用しない多対一のマップによって、ミップマップ（mipmaps）のないテクスチャに見られるような、エイリアシング・アーティファクト（aliasing artifacts）が発生する可能性がある。従って、詳細レベル（ＬＯＤ）の制御は、ビュー・パラメータの関数として地形のテッセレーションを調整するために提供される。
【００１６】
従来のスキーマでは、ビューだけでなく局所的な地形ジオメトリにも基づく詳細化を適用している。こうした従来のスキーマでは、平面の領域が、より大きな三角形に割り当てられ、レンダリングする三角形の数が少ない不規則なメッシュを結果として生ずる。しかし、こうしたフレームワークにはいくつかの欠点がある。詳細化基準および／または詳細化操作を事前に計算する必要があり、余分なメモリを消費する。そのデータ構造には、キャッシュ・コヒーレンシ（cache-coherence）のないランダム・アクセス・トラバース（traversals）が必要である。さらに、テッセレーションの変更により、低速の直接モードのレンダリングが必要であるが、静的領域のキャッシングによって時間的な連続性が阻害される。さらに、一定のフレームレートを維持するために、表示される地形の凹凸（bumpiness）によって詳細化しきい値を変更する必要がある。最後に、サーフェス・シェーディング（surface shading）はテクスチャ・イメージを必要とし、これは、個別に格納され、全く異なるＬＯＤ構造を使用する。
【００１７】
本ＧＰＵのレンダリング速度は、ピクセル・サイズの三角形を有するフレーム・バッファをビデオ速度で完全に処理できる十分なスループットを提供する。さらに、頂点処理速度は、それがピクセル速度に遅れないように、増加し続ける。したがって、ここで説明する技術には精密なＬＯＤ（fine-grain LOD）が必要であるという前提がなくなり、代わりに、すべての三角形が粗いピクセル・サイズの地形についてスクリーン上で均一なテッセレーションが要求される。この技術は、グラフィック・パイプラインにフィードする最適なＬＯＤフレームワークを作り上げる。
【００１８】
図２は、ネストされたジオメトリ・クリップマップの例を示す図である。ジオメトリ・クリップマップは、ビューアを中心とするネストされた正規グリッドの集合の形で地形をキャッシングする。これらのグリッドは、２のべき乗の解像度（resolutions）でフィルタされた複数の地形のバージョンを表現し、頂点バッファとしてビデオ・メモリに格納される。視点が移動するにつれて、クリップマップのレベルが移動し、データが徐々に入れ替えられる。
【００１９】
ジオメトリ・クリップマップとテクスチャ・クリップマップとの間には、いくつかの大きな相違がある。たとえば、非特許文献２２、非特許文献２３を参照されたい。
【００２０】
テクスチャ・クリップマップでは、スクリーン空間のジオメトリが投影されてから、ピクセルあたりのＬＯＤを計算する。しかし、地形に関しては、地形のＬＯＤを選択するまで、スクリーン空間のジオメトリは存在しない（循環依存性（circular dependency））。さらに重要なのは、ピクセルあたりのＬＯＤの選択は、メッシュの機密性（watertight）と時間的ななだらかさを維持するのを難しくする。
【００２１】
代わりに、視点を中心とするネストされた長方形領域（rectangular region）の集合を使用して、領域全体のＬＯＤがビューアの距離に基づいて選択される。レベル間をスムーズに融合し、ゼロ領域三角形（zero-area triangles）を使用してレベルの境界をステッチすることでＴジャンクション（T-junctions）、遷移領域が作成される。ここで説明するＬＯＤ遷移スキーマは、クリップマップ・レベルの独立した移動（translation）を可能とし、非特許文献２２で説明するようにレベルが自動的にクロッピングされるのではなく、無効化される。さらに、ネストされた正規グリッドはテクスチャ・イメージをサポートするので、ジオメトリとイメージに関する統一されたＬＯＤのフレームが得られる。テクスチャ・クリップマップとは異なり、説明する技術は専用のハードウェアを必要としない。
【００２２】
地形全体が正規グリッドとしてメイン・メモリ内に存在する必要はない。地形が圧縮された形で格納されている場合は、地形のピラミッド全体の圧縮された描写データをメイン・メモリに格納してもよい。こうした１つの例では、連続するレベル間の圧縮された残差（residuals）の形でレベルが格納される。地形が合成される際、クリップマップがキャッシングされている場合は、この合成のためにメイン・メモリに何も格納する必要はない。こうした１つの例では、合成手順は、ビューが移動するとクリップマップのレベルを満たす。
【００２３】
ジオメトリ・クリップマップの概要
ジオメトリ・クリップマップは、ｍ個のレベルの集合を使用して地形ピラミッドをキャッシングし、ネストされた範囲を連続する２のべき乗の解像度で表現する（たとえば図２）。１つの例において、各レベルにはｎ×ｎ個の頂点の配列が含まれており、頂点バッファとしてビデオ・メモリに格納される。徐々に効率よく更新できるように、この配列は、トロイド式に（toroidally）（すなわち、ｘとｙに関する剰余（ｍｏｄ）演算を使用した２次元のラップアラウンド・アドレシング（wraparound addressing）を使用して）アクセスされる。近い将来、グラフィック・ハードウェアはこの頂点の２次元配列をイメージとして格納できるようになる見込みである。特に、３つのチャネル（赤、緑、青）の３チャネル・イメージには、頂点の位置（Ｘ，Ｙ，Ｚ）が格納される。こうした例の１つにおいて、各頂点には（ｘ，ｙ，ｚ，ｚｃ）座標、ただし、ｚはこのレベルの標高の値、ｚｃは次に粗いレベルでの（ｘ，ｙ）の標高の値であり、後述する遷移モーフィング（transition morphing）に使用する。
【００２４】
クリップマップの各レベルｌについて、長方形領域の集合３００は図３に示すように定義される。ｃｌｉｐ＿ｒｅｇｉｏｎ（ｌ）３０２は、そのレベルのｎ×ｎのグリッドで表される範囲全体である。ａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ）３０４は、レンダリングするサブセットの範囲である。後述するように、ここで説明するアクティブ領域はビューアが中心であるが、クリップ領域は遅れる可能性があるので、アクティブ領域がクロッピングされることになる。次に細かいレベルのｃｌｉｐ＿ｒｅｇｉｏｎ（ｌ＋１）３０６にもａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ＋１）３０８がある。最終的に、このレベルのｒｅｎｄｅｒ＿ｒｅｇｉｏｎ（ｌ）３１０が、ｒｅｎｄｅｒ＿ｒｅｇｉｏｎ（ｌ）＝ａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ）−ａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ＋１）と定義される。最も細かいレベルｍでは、ａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｍ＋１）は空（empty）であると定義される。「アクティブ領域の計算」と「ジオメトリ・クリップマップの更新」で後述のするように、ビューが変わるとアクティブ領域とクリップ領域が更新される。
【００２５】
図３に関して、次の所見が得られる。
【００２６】
（１）  ｃｌｉｐ＿ｒｅｇｉｏｎ（ｌ＋１）⊆ｃｌｉｐ＿ｒｅｇｉｏｎ（ｌ）
【００２７】
【数１】
0004694256.tif 000002
【００２８】
１、ただし
【００２９】
【数２】
0004694256.tif 000003
【００３０】
はスカラーの距離によるｅｒｏｓｉｏｎ（縮小、腐食）を表す。より細かいレベルの値は、解凍（decompression）中または合成（synthesis）中に粗いレベルの値から予測されるので、クリップ領域はネストされる。この予測は、すべての辺上で１グリッド単位を保持している必要がある。
【００３１】
（２）  ａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ）⊆ｃｌｉｐ＿ｒｅｇｉｏｎ（ｌ）、これはレンダリングデータがクリップマップ内のデータのサブセットとなるためである。
【００３２】
（３）  ａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ）の外周は、「偶数」の頂点上にあり（図６で説明するとおり）、より粗いレベルｌ−１との密な境界を有効化する。
【００３３】
（４）  ａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ＋１）⊆ａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ）
【００３４】
【数３】
0004694256.tif 000004
【００３５】
２、これはレンダリング領域が少なくとも２つのグリッド単位の幅にあり、レベル間の連続的な遷移を可能にするためである。
【００３６】
１つの例では、個々のクリップマップ・レベルには関連のテクスチャイメージ（１つ以上）も含まれる。チャネルあたり８ビットの法線マップ（normal map）がサーフェス・シェーディング用として格納される。これは、頂点あたりの法線を格納するより効率的なためである。正確なシェーディングを行うために、法線マップはジオメトリの２倍の解像度である。頂点あたり１法線では非常にぼやけている。１つの例では、クリップマップが更新されるときにジオメトリから法線マップが計算される。カラーフィールドや地形属性などの付加的なイメージは、さまざまな解像度で格納される。頂点の配列やテクスチャは、トロイド式にアクセスされ、効率的に更新される。１つの例では、後述のビュー・フラスタム（view-frustum）カリング（culling）で使用する標高の上限（ｚｍａｘ）と下限（ｚｍｉｎ）はクリップマップ・レベル内の局所的な地形に対して保持される。
【００３７】
図４は、フレームをレンダリングするための例示的な方法４００を表す流れ図である。１つの例では、フレームごとに次の方法が実行される。１つの例では、４０２で本方法はクリップマップのレベルのアクティブ領域を決定する。一般に、視点に最も近い地形については、クリップマップのより細かいレベルが選択される。たとえば、図２に示すように、視点２０２は特定のレベルのクリップマップの地形に最も近いことが決定される。したがって、より細かいレベルのクリップマップの地形２０４を使用して、ビューアに最も近い地形を表示する。ビューア２０２からの距離２１０が大きくなるにつれて、より粗いレベルのクリップマップ２０６、２０８を使用する。アクティブ領域を決定する別の例について以下（すなわち「アクティブ領域の決定」）に説明する。
【００３８】
４０４で、クリップマップに対して視点が移動するにつれてクリップマップ・ジオメトリが更新される。視点が地形に対して相対的に移動すると、視点の周囲のレベルが一般的に図２に示す関係を維持するように、すなわち、より細かいクリップマップ・レベルのデータを視点に最も近いビューに配置するように、クリップマップの境界レベルを調整する。こうして、カンザス（Kansas）からノースカロライナ（North Carolina）に移動するときに、視点の前に広がる地形は、徐々に変化す正面を有することになる。図２に示すように、視点が２１０だけ移動すると、そのクリップマップの各レベルからの地形が展開されるので、その結果、視点は、そのクリップマップの中心近くに引き続き、存在する。図示されるように視点を中心に維持することは、ビューアが回転して後ろを見る場合に特に有効である。クリップマップを更新する別の例については、以下（すなわち「ジオメトリ・クリップマップの更新」）で考察する。
【００３９】
４０６で、アクティブ領域はクリップ領域に合わせてクロッピングされ（cropped）、クリップマップがレンダリングされる。このステップの別の例については、以下（すなわち「レンダリング・アルゴリズム」）で説明する。
【００４０】
アクティブ領域の決定
ビューに依存する詳細化は、クリップマップのレベルごとにアクティブ領域を選択することで決定する。１つの例では、各レベルｌについて、領域全体でグリッド２１２が間隔ｇｌ＝２−ｌである場合、望ましいアクティブ領域は中心を視点２０２の位置（ｘ，ｙ）とするサイズｎｇｌ×ｎｇｌの正方形２１４である。換言すれば、クリップマップでは中心をビューアの位置に変更し、各レベルの範囲全体をレンダリングすることが望ましい。ここで、選択したクリップマップ・サイズｎによってスクリーン空間の三角形のサイズがどう変化するかについて考察する。ここで、その地形は勾配が小さいことが仮定されているとすると、個々の三角形は辺の長さｇｌの正三角形に近くなる。より一般的なエラー分析については、以下（すなわち「結果と考察」）で説明する。
【００４１】
領域内に見える任意のポイントについて、スクリーン空間サイズは、スクリーン空間内の深度（ｄｅｐｔｈ）に反比例する。ビューの方向が水平の場合、スクリーン空間の深度はＸＹ平面で測定される。ビューアはｒｅｎｄｅｒ＿ｒｅｇｉｏｎ（ｌ）の中心に位置し、外側の辺のサイズはｎｇｌ、内側の辺のサイズはｎｇｌ／２である。視野φ＝９０°、スクリーン空間の平均深度は（すべての表示方向で）約（０．４）ｎｇｌである。したがって、スクリーン空間の三角形のピクセル単位によるおよそのサイズｓは次の式で求められる。
【００４２】
【数４】
0004694256.tif 000005
【００４３】
ただし、Ｗはウィンドウサイズ、φは視野で（field of view）ある。デフォルトではＷ＝６４０ピクセル、φ＝９０°、クリップマップ・サイズｎ＝２５５の場合に適切な結果が得られる。これは、スクリーン空間の３ピクセルからなる三角形のサイズに対応する。法線マップは２倍の解像度で格納されるので、テクスチャサンプルあたり約１．５ピクセルになり、これは、テクスチャ・サンプリングとして妥当な設定である。
【００４４】
ビューの方向が水平でない場合、ｒｅｎｄｅｒ＿ｒｅｇｉｏｎ（ｌ）のスクリーン空間深度は、上で抽出した（０．４）ｎｇｌより大きく、したがってスクリーン空間の三角形のサイズはｓより小さくなる。地形の上方から地形を見下ろすビューの場合は、三角形はとても小さなり、エイリアシングが目立つようになる。これを解決する方法は、不要な細かいレベルを無効にすることである。具体的には、ビューアの高さは、クリップマップの最も細かな妥当なレベルにアクセスすることによって、その地形全体で計算される。各レベルｌについて、ビューアの標高が（０．４）ｎｇｌを超える場合は、アクティブ領域を空（empty）に設定する。
【００４５】
単純にビューアを中心とする領域の欠点は、視野φが狭くなるにつれてクリップマップ・サイズｎを大きくしなければならないことである。対応策は、ビュー・フラスタムにクリップマップ領域の位置とサイズを適応させることである。代わりに、ビューア中心の領域は、ビューを現在の視点を中心として瞬時に回転させる場合に、使用される。これは、ユーザがジョイスティックの「ハットスイッチ」（joystick “hat switch”）を使用してすべての方向を見るフライト・シミュレータなどの多くのアプリケーションに求められる要件である。後述の「ビュー・フラスタム・カリング（View Frustum Culling）」では、視点の外部にある地形のレンダリングを回避する方法について説明する。
【００４６】
ジオメトリ・クリップマップの更新
要求されるアクティブ領域がビューアの動きに伴って移動すると、これに応じてクリップ領域も移動することになる。１つの例では、トロイド方式でアクセスするので、レベルが変わっても古いデータをコピーする必要がない。クリップ領域が移動すると、新しく視界内に入るＬ形の領域にデータが満たされる。このデータは、後述の「地形の圧縮」と「地形の合成」で説明するように、明示的な地形の解凍または手続き的地形の合成（synthesis of procedural terrain）のいずれかによってもたらされる。１つの例において、粗いレベル３１４には解凍された地形から満たされ、より細かいレベルは合成されている３１２となる。
【００４７】
１つのバリエーションは、更新の頻度を低くするために、クリップ領域を移動するときに今後のビューアの動きを予測することである。小規模な領域の解凍と合成はいずれも効率的に実行できるので、更新の細かさ（granularity）は現在のところ重要な要因ではない。
【００４８】
ビューアが高速で移動すると、すべてのレベルの更新に必要なプロセスは、負荷が重くなる可能性がある。したがって、レベルは粗いものから細かいものへという順序で更新され、特定の処理バジェット（budget）に達すると更新が停止する。１つの例では、更新されたサンプルの数がｎ２を超えると停止することが効率的であると決定される。更新されない（より細かい）レベルのクリップ領域は取り残されるので、空（empty）になるまで関連のアクティブ領域をクロッピングする。このことは、高速に移動する（ビューアに近い）地形では、高い周波数の詳細が失われ、適切に機能する、という効果がある。興味深い結果は、ビューアが高速で移動するとレンダリングの負荷は実際には軽減されることである。
【００４９】
圧縮または合成のいずれかを使用してクリップマップを更新する場合に、より細かいレベルは補間再分割（interpolatory subdivision）スキーマを使用して粗いレベルから予測されたレベルである。こうした例の１つでは、マスクの重み（−１／１６、９／１６、９／１６、−１／１６）を有する４ポイントの再分割曲線補間のテンソル積バージョンが選択される。たとえば、非特許文献２４、および非特許文献２５を参照されたい。
【００５０】
レンダリング・アルゴリズム
望ましいアクティブ領域が決定すると、地形は表１のアルゴリズムを使用してレンダリングされる。
【００５１】
【表１】
0004694256.tif 000006
【００５２】
このアルゴリズムに従って、前述の「ジオメトリ・クリップマップの概要」で説明した条件に従って、クリップ領域とより粗いアクティブ領域に、アクティブ領域がクロッピングされることになる。ａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｋ）が空の場合は、構造上、ｌ＞ｋとすると、より細かいａｃｔｉｖｅ  ｒｅｇｉｏｎ（ｌ）もすべて空である。より細かいレベルに空（empty）のアクティブ領域があるのはきわめて一般的である。これは、クリップ領域がまだ更新されていないか（ビューアが高速に移動）、またはより細かいテッセレーションが保証されない（つまり、ビューアが地形より十分に高い）ためである。
【００５３】
より細かいレベルはビューアにより近いので、細かいレベルから粗いレベルという順序でレンダリングされ、任意のハードウェアのオクルージョン・カリング（occlusion culling）を利用する。
【００５４】
図５は、最適な頂点キャッシングによってレンダリングする例示的なレンダリング領域を示す図である。
【００５５】
１つの例において、ｒｅｎｄｅｒ＿ｒｅｇｉｏｎ（ｌ）は４つの長方形パーティションの領域５０２〜５０８に分割される。こうした領域は、図５に示すように三角形ストリップを使用してレンダリングされる。最適な頂点キャッシングの最大ストリップ長が選択され、ストリップをグループ化して大規模なバッチ・プリミティブ（batch primitives）を構成する。実際に、ストリップは最大２０個の三角形の長さである。グリッド・シーケンシャル・メモリ・アクセスは、ビデオ・メモリ階層のすべてのレベルで適切に機能する。
【００５６】
視覚的連続性のための遷移領域
これまで説明してきたアルゴリズムでは、境界での２のべき乗の不整合による異なるレベルのレンダリング領域間のギャップを考慮していない。
【００５７】
図６は、ネストされたクリップマップのレベル間の例示的な境界を示す図である。たとえば、ネストされたクリップマップには、より細かいレベルのクリップマップとより粗いレベルが接する境界６０８がある。前述のように、より細かいレベル６０４は通常は視点により近く、三角形メッシュはより複雑になっている。図示されるように、より粗いグリッド６０２には２つの三角形ＡとＢを定義する４つの頂点がある。これを隣接するより細かいグリッド６０４と比較すると、６０４には８個の三角形ａ〜ｈを定義する９個の頂点がある。予測されるように、このより細かいメッシュと粗いメッシュとの境界は、ユーザから見える視覚的なギャップを提供する。
【００５８】
例えば、より詳細なレベルはより粗いレベル方向に移行し、より細かいメッシュはレベルの境界６０８に近づく。このレベル間の移行は、粗いレベルに到達するときに、ビューアに遷移がわかりにくいように、より細かいレベルの頂点に対して実行される。この概念を示すために、レベルの境界６０８はｘ＝０、ｙ＝０、頂点（０，０）６１０を中心として縦ｙ軸と横ｘ軸を表記する。より粗いレベルの頂点は、すべて偶数ｘと偶数ｙの頂点の値になる（すなわち（０，０）、（０，２）、（２，０）、（２，２）など）ことに留意されたい。より細かいレベルの頂点は、奇数と偶数の両方の頂点ｘおよびｙの値になることにも留意されたい（すなわち、偶数：（０，０）、（−２，０）、（０，２）、（−２，２）、奇数：（０，−１）、（０，１）、（−１，１）、（−２，１）、（−１，２））。したがって、遷移の幅がグリッド３つ分（６１２）に等しい場合は、より細かいレベルの奇数の頂点は、下位の粗いグリッドのダウン・サンプリングされた値に遷移する。境界６０８に到達すると同時に、ダウン・サンプリング値への遷移が完了し、より粗いレベル上の奇数のポイント（０，１）の地形の高さの値は、隣接するより細かいレベルの三角形の中間点（すなわち（０，０）と（０，２）の中間点）に等しい。
【００５９】
図７は、遷移領域を含むネストされたクリップマップの例を示す図である。ｔｒａｎｓｉｔｉｏｎ＿ｒｅｇｉｏｎ（ｌ）７０２を図７に示す。ギャップを除去すると同時に時間的な連続性を提供するには、各ｒｅｎｄｅｒ＿ｒｅｇｉｏｎ（ｌ）７１４の外側の境界近くでジオメトリをモーフィングし、より粗いレベルのジオメトリにスムーズに遷移する。モーフィングは、視点（ｖｘ，ｖｙ）７０６の地形頂点の座標を基準とする空間的（ｘ，ｙ）７０８グリッド座標の関数である。したがって、遷移は時間ベースではなく、ビューアの連続的な位置７０６を追跡することに基づく。
【００６０】
実験により、ｍｉｎ＿ｗｉｄｔｈ（ｌ）７１０、ｎ／１０グリッド単位の遷移幅ｗは適切に機能することが確認された。ｗが小さすぎると、レベルの境界が明瞭になる。ｗが大きすぎると、必要以上に細かい詳細が失われる。より細かいａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ＋１）７１２がより粗い領域に非常に近い場合は、ｗ＝ｍｉｎ（ｎ／１０，ｍｉｎ＿ｗｉｄｔｈ（ｌ））に設定すると有効である。ただし、ｍｉｎ＿ｗｉｄｔｈ（ｌ）は少なくとも２であることが知られている。
【００６１】
頂点ごとに（ｘ，ｙ，ｚ，ｚｃ）が格納されることを想起されたい。ただし、ｚcは次に粗いレベルｌ−１における地形の標高である。遷移領域において、モーフィングされた頂点の値の標高は次のように決定する。
【００６２】
ｚ’＝（１−α）ｚ＋αｚｃ
融合（blend）パラメータα＝ｍａｘ（αｘ，αｙ）として次の式で計算される。
【００６３】
【数５】
0004694256.tif 000007
【００６４】
同様にしてαｙが計算される。ここで、
【００６５】
【数６】
0004694256.tif 000008
【００６６】
はｃｌｉｐ＿ｒｅｇｉｏｎ（ｌ）のグリッド内の視点の連続的な座標を表し、ｘｍｉｎとｘｍａｘはａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ）７０４の範囲を表す整数値である。望ましいプロパティは、αが遷移領域以外では０に評価され、遷移領域では線形に増加し、外周で１に到達するものである。こうした計算（evaluations）はＧＰＵ頂点シェーダーで１０命令程度によって実行されるので、レンダリング・コストにはほとんど影響を及ぼさない。こうして、外周に近い遷移領域は、細かいレベルｌから次に粗いレベルｌ−１にスムーズに融合する。
【００６７】
ジオメトリ遷移によってギャップは除去されるが、一部の例では依然として境界に沿ったＴ接合（Ｔ−ｊｕｎｃｔｉｏｎｓ）は、ラスタライズ時にピクセルが脱落する結果をもたらす。隣接するレベルを密なメッシュにステッチするために、幅ゼロの三角形をレンダリング領域の境界に沿ってレンダリングする。
【００６８】
テクスチャ・マッピング
前述のように、クリップマップ・レベルごとにラスタライズ（たとえば法線マップ）に使用するテクスチャ・イメージを格納する。テクスチャ・マッピングの１つのオプションは、ハードウェア・ミップマッピング（mipmapping）でテクスチャＬＯＤを制御することである。クリップマップ・レベルのテクスチャにはそれぞれに固有のミップマップ・ピラミッドを有するので、３３％を超えるメモリを必要とする。ただし、このピラミッドのより粗いミップマップ・レベルはより粗いクリップマップ・レベルに正確に対応するので、テクスチャ・クリップマップ内に共有するのが理想的であるが（たとえば非特許文献２２を参照）、本ハードウェアではこの機能をサポートしない。さらに重要なのは、ハードウェアでミップマップ・レベルを制御する上で実際的な問題があることである。格納されたテクスチャの解像度があまり高くない場合は、一部の例では、レンダリング領域の境界におけるテクスチャ解像度の急激な遷移が表面化する。これは、ミップマップ・レベルが次に粗いレベルに到達していないためである。こうした急激な遷移は、ビューアが地形表面上を「前進」する間に可視可能になる。
【００６９】
代わりに、ミップマッピングを完全に無効化し、ジオメトリに適用された同じ空間的遷移領域を使用し、テクスチャ上でＬＯＤが実行される。このように、テクスチャＬＯＤは、ハードウェア・ミップマッピングのようなスクリーン空間デリバティブ（derivatives）にではなく、ビューアの距離に基づいている。この近似で失われる主な要素は、テクスチャＬＯＤの表面配向（surface orientation）に対する依存性である。サーフェスが斜めに向いている場合は、エイリアシングを回避するために、より粗いミップマップ・レベルにアクセスできなくなる。ただし、グラフィックス・ハードウェアは一般に異方性の（anisotropic）フィルタリングをサポートしており、これにより、多くのサンプルは、本来の最も細かいレベルから組み合わせられる。結果として、ミップマップがないことは表面配向の依存性にとって実際的な問題ではない。
【００７０】
空間ベースのテクスチャＬＯＤスキーマは、ＧＰＵフラグメント・シェーダー（fragment shader）に容易に実装される。レンダリング・レベルｌの場合は、シェーダーにレベルｌとレベルｌ−１のテクスチャが提供され、これらは、頂点シェーダーでジオメトリ遷移用にすでに計算されたものと同じパラメータを使用して融合される。
【００７１】
ビュー・フラスタム・カリング
図８は、上方から見たビュー・フラスタム・ピラミッドの例を示す図である。各レンダリング領域は４つの長方形領域に分割されること、また、クリップマップの各レベルごとに、下限ｚｍｉｎと上限ｚｍａｘが局所的な地形に対して保持されること、を図５から思い出されたい。２次元の長方形の範囲は、地形の限界［ｚｍｉｎ，ｚｍａｘ］に向けて広がり、ａｘｉｓ−ａｌｉｇｎｅｄ  ｂｏｕｎｄｉｎｇ  ｂｏｘを構成する。このボックスは、ビュー・フラスタムの４面を有するピラミッドと交差し、結果の凸状の集合がＸＹ平面に投影される。たとえば、スクリーン端末座標表ａ−ｄで表されるスクリーン表示８０２について、このスクリーン位置から交差する対応する範囲は、同じスクリーン座標ａ〜ｄで表される例示的なネストされたグリッド８０４内に示される。この集合の境界となる軸に平行な長方形（axis-aligned rectangle）を使用して、特定の長方形領域をクロッピングする。ビュー・フラスタム・カリングにより、９０°の視野のレンダリング負荷を約１／３に軽減する。
【００７２】
地形の圧縮
標高地図（Height maps）は、実際面では、際だってコヒーレンシであり、通常のカラー・イメージに比べると、コヒーレンシが著しく高いので、圧縮の可能性は非常に大きい。ジオメトリ・クリップマップ構造と効率的に対話するために、解凍アルゴリズムは「関心領域」（ＲＯＩ：region-of-interest）クエリーを２のべき乗の解像度でサポートしなければならない。
【００７３】
以下でピラミッド圧縮スキームについて説明する。地形ピラミッドＴ１．．Ｔｍは、まず細かい地形Ｔｍからより粗いレベルへと、線形のフィルタＴｌ−１＝Ｄ（Ｔｌ）を使用して、連続的にダウン・サンプリングすることによって作成される。その後、各ピラミッドレベルＴｌは次に粗いレベルＴｌ−１から補間細分割Ｕ（Ｔｌ−１）（たとえば「ジオメトリ・クリップマップの更新」で説明）によって予測され、残差Ｒｌ＝Ｔｌ−Ｕ（Ｔｌ−１）はイメージ・コーダによって圧縮される。最適なフィルタＤ（サイズ１１×１１）は、特定の地形のサブセットに関する線形系を解くことで、Ｕ（Ｄ（Ｔｌ）からＴの最適なＬ２近似が得られるように、あらかじめ計算される。圧縮は、ロッシー（lossy）であり、Ｒｌは
【００７４】
【数７】
0004694256.tif 000009
【００７５】
で近似される。したがって、粗いレベルから細かいレベルへ順序付けされる各レベルが
【００７６】
【数８】
0004694256.tif 000010
【００７７】
として再構成され、残差が圧縮され、
【００７８】
【数９】
0004694256.tif 000011
【００７９】
として再定義される。
【００８０】
粗いレベルは遠方から見られるので、最初のアプローチは、絶対精度（absolute accuracy）の低い近似
【００８１】
【数１０】
0004694256.tif 000012
【００８２】
をそれらに与えることであった。具体的に、残差Ｒは量子化に先立って２ｌ−ｍでスケーリングされる。これは幾何学的なフィディリティ（fidelity）では正しい議論であるが、これは、不十分な視覚的なフィディリティをもたらす。その理由は、法線マップとｚベースのカラーリングはいずれも量子化のアーティファクトを示すためである（これらは解凍されるジオメトリから推定される）。これを解決する方法は、同じ絶対精度ですべての残差を圧縮することである。
【００８３】
量子化された残差は、いくつかの優れたプロパティを備えるＰＴＣイメージ・コーダー（たとえば、非特許文献２６）を使用して圧縮される。重複する基本の関数（overlapping basis functions）を定義することでブロッキングのアーティファクトを回避するが、そのベースは空間的に局所化され、効率的な領域の圧縮が可能になる。また、このイメージ・コーダは、コード化が２ＧＢ以内に収まる場合に任意のサイズのイメージをサポートする。１つの例では、解凍はビデオ・メモリに徐々にアップロードしながら行われるので、十分に高速である。
【００８４】
圧縮の前処理は、すべてのステップをストリーミング演算として実行することで、３２ビット・アドレス空間内に実装される。４０ＧＢ  Ｕ．Ｓ．データでは、初めの地形Ｔｍから圧縮された残差
【００８５】
【数１１】
0004694256.tif 000013
【００８６】
までの手順を完了するのに約５時間を要し、そのほとんどはディスクＩ／Ｏである。圧縮エラー
【００８７】
【数１２】
0004694256.tif 000014
【００８８】
のｒｍｓについては、後述の「結果と考察」で説明する。圧縮された地形は、海岸線に関連付けられる急激な色の遷移を、多分、除いて、元のデータと視覚的に区別できない。
【００８９】
地形の合成
ジオメトリ・クリップマップは自然構造（natural structure）を提供し、確率的細分割（stochastic subdivision）（たとえば、非特許文献２７、非特許文献２８）、またはマルチ解像度テクスチャ合成（たとえば、非特許文献２９を参照）を使用して新しい詳細データを生成する。１つの制約は、合成プロセスは、常に同じ地形が作成されるように空間的に１つに決定できなければならない（spatially deterministic）ことである。
【００９０】
フラクタル・ノイズの置き換えは、アップ・サンプリングされたより粗い地形に無相関のガウスのノイズを追加することで実行される。ノイズの変動は、実際の地形の変動（すなわち、「地形の圧縮」で計算した残差Ｒｌの変動）と等しくなるように各レベルｌでスケーリングされる。補間細分割の滑らかさＣｌは、サーフェスのしわ（crease）のアーティファクト（たとえば、非特許文献３０を参照）を回避するために重要である。効率的に評価するために、あらかじめ計算したガウスのノイズ値がテーブルに格納され、頂点の座標に関する剰余（modulo）演算でインデックス付けされる。テーブル・サイズ５０×５０は、任意の反復パターンまたは認識可能なバンディング（banding）を除去するのに十分である。
【００９１】
ジオメトリ・データ全体がビデオ・メモリに残るように、ＧＰＵフラグメント・シェーダーを使用する合成プロセスを実行するのが望ましい。ＧＰＵは、必要な「頂点レンダリング（render-to-vertex）」機能をすでに備えている。この機能について簡単に説明する。現在のところ、ＣＰＵは表３のような計算時間を示している。
【００９２】
手続き的合成は、無限の範囲と解像度を有する地形の生成を可能とし、その結果、大きな可能性を与える。さらに、フラクタル・ノイズは合成された地形（landscapes）を提供する。
【００９３】
結果と考察
実験には、２つの米国政府のサンプルが使用された。小さい方は、ｌｍの垂直解像度で１６ビットの標高値を備えた、ピュジェット湾（Puget Sound）地域の１０ｍ間隔による１６，３８５２グリッドである。最大解像度のグリッドはレベルｌ＝９に割り当てられており、最も粗いレベルｌ＝１での範囲は６５２である。データは５３７ＭＢから８．７ＭＢに圧縮され、ｒｍｓエラーは１．２ｍ（ＰＳＮＲ＝２０ｌｏｇ１０（ｚｍａｘ／ｒｍｓ）＝７１．４ｄＢ）である。
【００９４】
大きい方のデータ・セットは、隣接する（conterminous）米国の３０ｍ（正確には、経度と緯度の両方で１秒）間隔の標高マップである。その範囲は１２６°Ｗ，６６°Ｗ］×［２４°Ｎ，５０°Ｎ］であり、２１６，０００×９３，６００グリッドを構成する。レベル数ｍ＝１１のクリップマップでは、最も粗いレベルで２１２×９３の長方形になる（極座標でパラメータ化されているが、平面にレンダリングされる）。４０．４ＧＢから３５３ＭＢに圧縮され、ｒｍｓエラーは２．６ｍ（ＰＳＮＲ＝６４．９ｄＢ）である。３．０  ＧＨｚ  Ｐｅｎｔｉｕｍ（登録商標）Ｐｅｎｔｉｕｍ（登録商標）４  ＣＰＵ、１ＧＢのシステム・メモリ、２５６ＭＢのビデオ・メモリを伴うＡＴＩ  Ｒａｄｅｏｎ  ９８００ＸＴ  ＧＰＵを備えたＰＣを使用した。
【００９５】
エラーの原因は圧縮エラーとＬＯＤエラーの２つがあり、別々に分析している。この米国のデータ・セットは、４０．４ＧＢから３５３ＭＢに圧縮され、ｒｍｓエラーは２．６ｍ  （ＰＳＮＲ＝６４．９ｄＢ）である。ピュジェット湾のデータ・セットは５３７ＭＢから８．７ＭＢに圧縮され、ｒｍｓエラーは１．２ｍ（ＰＳＮＲ＝２０ｌｏｇ１０（ｚｍａｘ／ｒｍｓ）＝７１．４ｄＢ）である。こうしたｒｍｓエラーは非常に小さく、サンプリング間隔の１０％程度にすぎない。
【００９６】
この米国のデータ・セットでは、レベル数ｍ＝１１であり、圧縮された地形はシステム・メモリ３５３ＭＢを占有する。デフォルトのクリップマップ・サイズ、ｎ＝２５５に対して、頂点ジオメトリ用のジオメトリ・クリップマップは、ビデオ・メモリ内に１６ｍｎ２＝１１ＭＢを要する。レベルの予測はＧＰＵではまだ使用できないので、ｚの標高のデータはシステム・メモリ内で複製され、４ｍｎ２＝３ＭＢが必要になる。この法線マップは、解像度の２倍であるが、３バイト／サンプルにすぎないので、さらに１２ｍｎ２＝９ＭＢが必要になる。したがって、全体のメモリ使用量は３７６ＭＢ、すなわち０．０１９バイト／サンプルにすぎない。表２に示すように、必要な領域はこれまでに報告された結果に比べてはるかに少ない。このデータは標準的なＰＣのメモリに収まるので、実行時のディスク・アクセスは回避される。
【００９７】
サイズ２５５２のレベル数ｍ＝１１では、１２０フレーム／秒が、フラスタムカリングを使用し、レンダリング速度５９  ＭΔ／秒で、得られる（４×フレーム・バッファのマルチ・サンプリングでは、９５フレーム／秒に低下する）。この結果は、従来のＬＯＤの方法では最適なレンダリング・スループットを実現できていなかったことを示唆している。
【００９８】
１つの例において、クリップマップ更新の処理バジェットのしきい値（threshold processing budget）は、完全なｎ×ｎのレベルであった。表３は、この最悪のケースの更新ステップの実行時間を示している。これらの時間はＧＰＵの処理と重複する可能性がある。ビューアが移動する間に、システムは、ほとんど均一の速度６０フレーム／秒を維持している。近い将来、正規グリッド・データ構造により、ＧＰＵを使用してすべてのステップ（解凍を除く）を実行できるようになることに留意されたい。
【００９９】
サイズ２５５２のレベル数ｍ＝１１では、フラスタムカリングを使用し、レンダリング速度５９  ＭΔ／秒で１２０フレーム／秒を実現する。（４×フレーム・バッファのマルチ・サンプリングでは、９５フレーム／秒に低下する）。クリップマップ更新の処理バジェットのしきい値は詳細なｎ×ｎのレベルであった。表３は、この最悪のケースの更新ステップの実行時間を示している。これらの時間はＧＰＵの処理と重複すると思われる。ビューアが移動する間に、システムはほとんど均一の速度６０フレーム／秒を維持している。近い将来、この正規グリッド・データ構造により、すべてのステップ（解凍を除く）を、ＧＰＵを使用して実行できるようになることに留意されたい。
【０１００】
【表２】
0004694256.tif 000015
【０１０１】
表２では、従来の各方法における実行時に必要な領域と比較している。従来の方法では、サーフェス・シェーディング用の法線マップを格納する領域も必要である（ここには、含んでいない）。ジオメトリ・クリップマップでは、法線マップは解凍されたジオメトリから必要に応じて計算される。
【０１０２】
【表３】
0004694256.tif 000016
【０１０３】
表３では、ｎ×ｎレベル（ｎ＝２５５）の全体の更新にかかる時間を比較している。この値は更新処理バジェットの例である。
【０１０４】
レベル数ｍ＝１１の場合、浮動小数点の精度はまだ問題にはならない。任意のレベル数に対応するために、シンプルなソリューションは、視点とビュー・マトリックスを各クリップマップ・レベルの倍精度を使用した局所座標系に変換することである（たとえば、非特許文献１４を参照）。
【０１０５】
これまで、スクリーン空間の三角形のサイズｓは、特定のクリップマップ・サイズｎに対して評価された。この分析は、地形の傾斜が小さいことが想定される場合に地形の三角形はコンパクトな形状をとるという事実に基づいている。一方、そうではなく、地形が急傾斜の場合は、三角形を自由に伸張でき、スクリーン空間の範囲には制限されなくなり、このことは、若干不十分に思われる。
【０１０６】
しかし、より適切な基準は、スクリーン空間のジオメトリ・エラー、すなわちレンダリングしたメッシュと元の地形との間のスクリーン投影による相違、である。このエラーは、地形ジオメトリのスペクトル特性（spectral properties）に関する情報が提供された場合に分析できる。
【０１０７】
各地形レベルＴｌについて、エラー関数ｅｌ＝ＰＬ（Ｔｌ）−ＰＬ（Ｔｍ）は興味深い。ただし、ＰＬは区間（ｘ，ｙ）に対する区分的に線形のメッシュ補間（piecewise linear mesh interpolant）を表す。この関数は、地形信号の（連続的な）スペクトル密度に関連する。レベルｌのグリッド間隔ｇｌはスクリーン空間におきてのｓ個のピクセルに投影されるので、位置（ｘ，ｙ）におけるスクリーンエラーｅｌ（ｘ，ｙ）のスクリーン空間投影は、最大で次のようになる。
【０１０８】
【数１３】
0004694256.tif 000017
【０１０９】
（ビューの方向が水平でない場合はエラーが小さい。）こうして、地形データ・セットが与えられると、
【０１１０】
【数１４】
0004694256.tif 000018
【０１１１】
のノルムが計算され、表４に示すように、レンダリング・レベルごとにスクリーン空間エラーが評価される。
【０１１２】
結果は、ｒｍｓスクリーン空間エラーが１ピクセルより小さいことを示している。ｓは３ピクセルにすぎず、こうした平面の三角形同士の相違とより細かい細部は通常はさらに小さいので、この結果は予想外ではない。大きな
【０１１３】
【数１５】
0004694256.tif 000019
【０１１４】
の（最大）エラーの値は、取得した地形データにはアーティファクトの崖を作成するモザイクの位置ずれ（misregistration）のアーティファクトがあり、それは、統計を歪ませる１つの誤った標高の値をとるのみであるという理由で、誤解させる可能性がある。代わりに、９９．９パーセンタイルのエラーを調査し、依然として１ピクセルより小さいかどうかを確認するのが好ましい。
【０１１５】
【表４】
0004694256.tif 000020
【０１１６】
表４は、スクリーン空間のジオメトリ・エラーの分析をピクセル単位で示している。各カラムは、ｒｍｓ，９９．９パーセンタイル、最大エラーを示している（ｎ＝２５５、Ｗ＝６４０、φ＝９０°、ｓ＝３の場合）。
【０１１７】
エラーの分析により、クリップマップ・サイズは許容可能な幾何学的フィディリティを維持する限り、小さくしてもよいことが示されている。しかし、真の限定的要因は視覚的なフィディリティである。これは、サーフェス・シェーディングに強く依存しており、法線マップの基本前提である。したがって、より粗いジオメトリを使用しても、依然として高解像度の法線マップを維持する必要がある。本システムでは、こうした法線マップがジオメトリ・クリップマップ自体から生成される。実際に、圧縮されたミップマップ・ピラミッドは、法線マップをコード化する有効なスキーマと見なすことができ、第２の利点としてキャリア・ジオメトリ（carrier geometry）を提供する。
【０１１８】
レベルを横切るスクリーン空間エラー
【０１１９】
【数１６】
0004694256.tif 000021
【０１２０】
の不均一性は、個々のクリップマップ・レベルのサイズに合わせることで利用することができる。たとえば、遠くの山のシルエットよりも近くのなだらかな地形上のなだらかな山は、（スクリーン空間において）テッセレーションが少なくてよい。このように、サーフェス・シェーディングが悪影響を及ぼさないことを確認する必要がある。ピュジェット湾と米国のいずれの地形データ・セットも、スペクトル密度はほぼ均一に見える。米国のデータでは、粗いレベルでこのエラーは減少するようになり、地面が粗いスケールでなだらかであるという事実を表している。
【０１２１】
圧縮された地形ピラミッドの残差
【０１２２】
【数１７】
0004694256.tif 000022
【０１２３】
は、サーバー上に格納することができ、小型のクライアント（lightweight client）に（ユーザの動きに基づいて）徐々にストリーミングされる。必要な帯域幅は、圧縮比が５０〜１００のオーダーなので、僅かである。
【０１２４】
あらかじめフィルタを適用したミップマップ・ピラミッドは、地形データの自然な描写データである。ジオメトリ・クリップマップはピラミッドのネストされた長方形の範囲をキャッシングし、ビューに依存する近似を作成する。本フレームワークに固有の態様は、ＬＯＤがデータの内容に依存しないことである。したがって、地形データの詳細化基準をあらかじめ計算しておく必要はない。シンプルなグリッド構造に加えて、地形をその場で、ゆっくりと（lazily）作成でき、圧縮率の高い形式で格納できる。こうした機能はいずれもこれまでは利用できなかった。
【０１２５】
１つの例において、米国の２０ビリオンのサンプル・グリッドに渡る対話型のフライトが表示され、これは、メモリ内にちょうど４００ＭＢで格納され、その場で６０フレーム／秒で解凍される。解凍されたデータのｒｍｓエラーは２．６ｍである。スクリーン空間ＬＯＤエラーは９９．９パーセンタイルが１ピクセルより小さいので、レンダリングはスムーズである。
【０１２６】
正規グリッドを使用したジオメトリからなる表現は、近々予定されている頂点バッファとイメージバッファの統一によってさらに興味深いものになるはずである。頂点バッファは、２次元トロイド座標からアクセスされるジオメトリ・イメージになる（たとえば、非特許文献３１を参照）。これは、ジオメトリ・クリップマップによる大幅な簡素化の実現である。より一般的に言えば、この統一は、並列度の高いＧＰＵラスタライザがイメージに加えてジオメトリを処理することを可能にする。
【０１２７】
ジオメトリ・クリップマップは、地形ジオメトリとそれに関連するテクスチャ信号のＬＯＤ管理を統一する。空間ベースのＬＯＤ構造では、レベルの境界の視覚的不連続性を生じさせずに、低解像度テクスチャが適用されるようにしている。法線マップの実行時の作成に加えて、イメージされる（envisioned）シャドウマップのような非局所的な関数は、同様にレイジー方式（lazy fashion）で計算できる。
【０１２８】
ジオメトリ・クリップマップには、従来の地形ＬＯＤスキーマに比べて次のように多くの利点を得る可能性がある。
【０１２９】
・  シンプルさ（Simplicity）。不規則メッシュの三角形分割で実行されるように、ポインタ／インデックス・ベースのデータ構造を考慮せず、詳細化の依存性を追跡しない。
【０１３０】
・  最適なレンダリング・スループット（Optimal rendering throughput）。クリップマップの頂点は、ビデオ・メモリに常駐し、そのグリッド構造によって、最適な頂点キャッシュ再利用による三角形ストリップ（strip）レンダリングが可能になる。
【０１３１】
・  視覚的連続性（Visual continuity）。レベル間の遷移領域によって、頂点プログラムと断片プログラム（fragment programs）のそれぞれにおいて僅かな命令を使用して、ジオメトリとテクスチャの両方について空間的かつ時間的な連続性が提供される。
【０１３２】
・  安定したレンダリング（Steady rendering）。テッセレーションの複雑性は局所的な地形の起伏に関係ないので、レンダリング速度はほぼ一定である。
【０１３３】
・  直接的な複雑性の抑制（Immediate complexity throttling）。クリップマップ・サイズが修正（fix）されたも、レンダリング領域を修正（fix）してレンダリング負荷を軽減することができる。
【０１３４】
・  適切なデグラデーション（Graceful degradation）。ビューアが迅速に移動すると、更新帯域幅（クリップマップを入れ替えるための）がボトルネックなる恐れがある。テクスチャ・クリップマップと同様に、所定のバジェット内でできるだけ多くのレベルが更新される。その効果は、高速で移動する地形は、低い周波数の詳細を使って可能なことである。
【０１３５】
・  サーフェス・シェーディング（Surface shading）。法線マップは、必要に応じてジオメトリから迅速に計算でき、ジオメトリと同じＬＯＤ構造を使用する。また、ジオメトリ・クリップマップでは２つの新しい実行時の機能を有効にする。
【０１３６】
・  圧縮（Compression）。クリップマップのみを頂点データに展開すればよいので、地形ピラミッドのその他の部分は圧縮形式で格納できる。ピラミッドレベルの残差は、２次元イメージ・コーダを使用して計算される。データのコヒーレンシが高いので、圧縮比５０〜１００を実現できる。地形全体をメモリに格納することで、ページングによる一時的中断（paging hiccups）が回避される。
【０１３７】
・  合成（Synthesis）。シンプルなグリッド構造によって迅速な地形の合成が可能になるので、粗く指定したジオメトリは、手続き的に生成された詳細レベルによって拡張される。
【０１３８】
・  制限（Limitations）。一部の事例では、レンダリングされたメッシュの詳細レベルは、従来のＬＯＤスキーマより複雑である。本質的に、ジオメトリ・クリップマップの詳細レベルは均一なので（あらゆる場所かつあらゆる周波数で）、局所的な適応性による効果はない。他方では、メッシュは規則的であり、ビデオ・メモリに格納されているので、最悪のケースであっても最適なレンダリングパフォーマンスを提供する。別の制限では、地形のスペクトル密度が有界であることが仮定される。たとえば、高い針のようなフィーチャ（地物）は若干遅いビューにモーフィングされる。幸い、実際的な地形の動作は適切であり、こうした問題は発生しない。この環境に存在する建物、植物、その他の物体は他のＬＯＤ技術を使用して別々にレンダリングされる。
【０１３９】
コンピューティング環境
図９と以下の説明は、実装のための適切なコンピューティング環境の簡単で一般的な説明を目的とするものである。本発明について、コンピュータ上および／またはネットワーク・デバイス上で実行するコンピュータ・プログラムのコンピュータ実行可能命令の一般的なコンテキストで説明してきたが、本発明を他のプログラム・モジュールと組み合わせても実装できることは当業者には明らかである。一般に、プログラム・モジュールには、ルーチン、プログラム、コンポーネント、データ構造などがあり、特定のタスクを実行するものや、特定の抽象データ型を実装するものもある。さらに、本発明が、マルチ・プロセッサ・システム、マイクロ・プロセッサ・ベースまたはネットワーク・アプライアンス、無線デバイス、ミニ・コンピュータ、メインフレーム・コンピュータなどを含むその他のコンピュータ・システム構成で実施できることは言うまでもない。こうした拡張は、ネットワークに接続されたコンピューティング環境でも、スタンドアロンのコンピュータでも実施できる。
【０１４０】
図９を参照すると、実装のための例示的なシステムには、プロセッシング・ユニット９２１、システム・メモリ９２２、およびシステム・メモリ９２２からプロセッシング・ユニット９２１までのさまざまなシステム・コンポーネントを接続するシステム・バス９２３を備える従来のコンピュータ９２０（パーソナル・コンピュータ、ラップトップ、サーバー、メインフレーム、などのさまざまなコンピュータ）が含まれる。プロセッシング・ユニットは、Ｉｎｔｅｌ  ｘ８６，Ｐｅｎｔｉｕｍ（登録商標）および互換可能なＩｎｔｅｌおよび他社製のマイクロ・プロセッサ（Ｃｙｒｉｘ、ＡＭＤ  Ｎｅｘｇｅｎ、ＤｉｇｉｔａｌのＡｌｐｈａ、ＭＩＰＳ  Ｔｅｃｈｎｏｌｏｇｙ、ＮＥＣ、ＩＤＴ、ＳｉｅｍｅｎｓなどのＭＩＰＳ、ＩＢＭおよびＭｏｔｏｒｏｌａのＰｏｗｅｒＰＣなど）を含む市販のさまざまなプロセッサのいずれでもよい。デュアル・マイクロ・プロセッサやその他のマルチ・プロセッサ・アーキテクチャもプロセッシング・ユニット９２１として利用できる。
【０１４１】
システム・バスは、たとえば、ＰＣＩ、ＶＥＳＡ、ＡＧＰ、Ｍｉｃｒｏｃｈａｎｎｅｌ、ＩＳＡ、ＥＩＳＡなど市販のさまざまなバス・アーキテクチャの任意の１つを使用したメモリ・バスまたはメモリ・コントローラ、周辺バス、ローカル・バスを含む各種バス構造のいずれでもよい。システム・メモリには、読み取り専用メモリ（ＲＯＭ：read only memory）９２４とランダム・アクセス・メモリ（ＲＡＭ：random access memory）９２５が含まれる。起動時などにコンピュータ９２０内のエレメント間の情報転送を支援する基本ルーチンを含む基本入出力システム（ＢＩＯＳ：basic input/output system）は、ＲＯＭ９２４に格納される。
【０１４２】
コンピュータ９２０には、さらにハードディスク・ドライブ９２７、取り外し可能なディスク９２９に対する読み出しまたは書き込みを行う磁気ディスク・ドライブ９２８、ＣＤ−ＲＯＭディスク９３１の読み出し、または他の光媒体に対する読み出しまたは書き込みを行う光ディスク・ドライブ９３０が含まれる。ハードディスク・ドライブ９２７、磁気ディスク・ドライブ９２８、および光ディスク・ドライブ９３０は、それぞれハードディスク・ドライブ・インターフェース９３２、磁気ディスク・ドライブ・インターフェース９３３、および光ディスク・ドライブ・インターフェース９３４を介してシステム・バス９２３に接続する。ドライブとこれに関連付けられたコンピュータ可読媒体は、データ、データ構造、コンピュータ９２０のコンピュータ実行可能命令を格納する不揮発性ストレージとして利用できる。前述のコンピュータ可読媒体の説明は、ハードディスク、取り外し可能な磁気ディスク、およびＣＤを表しているが、例示的な動作環境では、磁気カセット、フラッシュ・メモリ・カード、デジタル・ビデオ・ディスク（ＤＶＤ：digital video disk）、Ｂｅｒｎｏｕｌｌｉ（ベルヌーイ）カートリッジなど、その他のコンピュータ可読媒体も利用できることを当業者は理解されたい。
【０１４３】
説明した技術９５６を実装する以外に、オペレーティング・システム９３５、１つまたは複数のアプリケーション・プログラム９３６、その他のプログラム・モジュール９３７、およびプログラム・データ９３８を含む多くのプログラム・モジュールは、ドライブおよびＲＡＭ９２５に格納できる。
【０１４４】
ユーザは、キーボード９４０やポインティング・デバイス（たとえばマウス９４２）を使用してコンピュータ９２０にコマンドや情報を入力できる。これらの入力装置および他の入力装置は、多くの場合、システム・バスに接続するシリアル・ポート・インターフェース９４６を介してプロセッシング・ユニット９２１に接続するが、パラレル・ポート、ゲームポート、ＵＳＢ（universal serial bus）のような他のインターフェースで接続してもよい。モニター９４７または他のタイプの表示装置も、ビデオ・アダプタ９４８のようなインターフェースを介してシステム・バス９２３に接続される。コンピュータには、一般にモニター以外にもスピーカーやプリンタなどの周辺出力装置（図示せず）が接続されている。
【０１４５】
コンピュータ９２０は、リモート・コンピュータ９４９のような１台または複数台のリモート・コンピュータへの論理接続を使用してネットワーク環境で動作する。リモート・コンピュータ９４９は、ワークステーション、サーバー、ルーター、ネットワークＰＣ、ピア・デバイス、または他の一般的なネットワーク・ノードのいずれでもよい。通常は、コンピュータ９２０に関連して上で説明したエレメントの多くまたはすべてが含まれるが、メモリ記憶装置９５０のみが図１０示されている。図示された論理接続には、ローカル・エリア・ネットワーク（ＬＡＮ：local area network）９５１とワイド・エリア・ネットワーク（ＷＡＮ：wide area network）９５２を含めてもよい。このようなネットワーキング環境は、職場、企業規模のコンピュータ・ネットワーク、イントラネット、およびインターネットではごく一般的である。
【０１４６】
ＬＡＮネットワーキング環境で使用する場合、コンピュータ９２０はローカル・ネットワーク９５１にネットワーク・インターフェースまたはアダプタ９５３を介して接続する。ＷＡＮネットワーキング環境で使用する場合、コンピュータ９２０は一般にインターネットなどのＷＡＮ９５２を介して通信を確立する（たとえば、ＬＡＮ９５１およびゲートウェイまたはプロキシ・サーバー９５５）ためのモデム９５４またはその他の手段を備えている。モデム９５４（内蔵または外付け）は、シリアル・ポート・インターフェース９４６を介してシステム・バス９２３に接続できる。ネットワーク環境では、コンピュータ９２０またはその一部に関連して説明したプログラム・モジュールをリモート・メモリ記憶装置に格納できる。図示されたネットワーク接続が例示的なものであり、無線またはそれ以外のコンピュータ間の通信リンクを確立する他の手段を使用してもよいことは言うまでもない。
【０１４７】
代替手段
本発明の原理について、提示された例に関連して説明し、図示してきたが、こうした例は前述の原理を逸脱することなく配置および細部を変更できることは言うまでもない。さらに、通常のコンピュータ科学者には明らかなように、こうした例の一部または全体を他の例の他の部分と全体的または部分的に組み合わせることもできる。ここで説明するプログラム、プロセス、あるいは方法は、特に他の指定がない限り、特定のコンピュータ機器に関連または限定するものでないことを理解されたい。さまざまなタイプの汎用または専用コンピュータ機器を使用して、ここで説明する指針による動作を実行できる。ソフトウェアで示す提示された実施形態のエレメントは、ハードウェアでも実装できる。また、ハードウェアで示すエレメントは、ソフトウェアでも実装できる。１つの例の中で示された技術は、他の任意の例に組み込むことができる。
【０１４８】
本発明の原理を適用できる多くの実施形態について考察する上で、詳細は説明のためのみに示されており、本発明の範囲を限定するものと解釈してはならないことを理解されたい。むしろ、本発明はこうしたすべての実施形態を、以下の請求項およびそれと同等のものの範囲と精神を逸脱しないものとして請求する。
【図面の簡単な説明】
【０１４９】
【図１】クリップマップのレベルを示す図である。
【図２】ネストされたジオメトリ・クリップマップの例を示す図である。
【図３】ネストされた正規グリッドの集合のレベル間の関係を表す例示的なレンダリング領域を示す図である。
【図４】フレームをレンダリングするための例示的な方法を示す流れ図である。
【図５】最適な頂点キャッシングによってレンダリングする例示的なレンダリング領域を示す図である。
【図６】ネストされたクリップマップのレベル間の例示的な境界を示す図である。
【図７】遷移領域を含むネストされたクリップマップの例を示す図である。
【図８】以上によって表示されるビュー・フラスタム・ピラミッド（view frustum pyramid）の例を示す図である。
【図９】前述の技術を実装する分散コンピュータ・システムを示すブロック図である。
【符号の説明】
【０１５０】
１０２    レベル
１０４    中間のレベル
１０６    最も粗いレベル
１０８、１１０    地形レベルの頂点
２００    ネストされたジオメトリ・クリップマップの例
２０２    視点
２０４    より細かいレベルのクリップマップの地形
２０６、２０８    より粗いレベルのクリップマップ
２１０    視点の移動
２１２    領域全体のグリッド
２１４    アクティブ領域の辺の長さ
３００    長方形領域の集合
３０２    ｃｌｉｐ＿ｒｅｇｉｏｎ（ｌ）
３０４    ａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ）
３０６    ｃｌｉｐ＿ｒｅｇｉｏｎ（ｌ＋１）
３０８    ａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ＋１）
３１０    ｒｅｎｄｅｒ＿ｒｅｇｉｏｎ（ｌ）
５００    レンダリング領域
５０２〜５０８    長方形パーティション
６００    ネストされたクリップマップのレベル間の例示的な境界を示す図
６０２    粗いグリッド
６０４    より細かいレベル
６０８    レベルの境界
６１０    頂点
６１２    ３グリッド
７００    遷移領域を含むネストされたクリップマップ
７０２    ｔｒａｎｓｉｔｉｏｎ＿ｒｅｇｉｏｎ（ｌ）
７０４    ａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ）
７０６    視点
７０８    空間座標
７１０    ｍｉｎ＿ｗｉｄｔｈ（ｌ）
７１２    より細かいａｃｔｉｖｅ＿ｒｅｇｉｏｎ（ｌ＋１）
７１４    ｒｅｎｄｅｒ＿ｒｅｇｉｏｎ（ｌ）
８０２    画面表示（スクリーン・ビュー）
８０４    ネストされたグリッド
９２０    コンピュータ
９２１    プロセッシング・ユニット
９２２    システム・メモリ
９２７    ハード・ドライブ
９２８    フロッピー（登録商標）ドライブ
９２９    ディスク
９３０    ＣＤ−ＲＯＭドライブ
９３１    ディスク
９３２    インターフェース
９３３    インターフェース
９３４    インターフェース
９３５    オペレーティング・システム
９３６    アプリケーション
９３７    モジュール
９３８    データ
９４０    キーボード
９４２    マウス
９４６    シリアル・ポート・インターフェース
９４７    モニター
９４８    ビデオ・アダプタ
９４９    リモート・コンピュータ
９５０    メモリ記憶装置
９５３    ネットワーク・アダプタ
９５４    モデム
９５５    ゲートウェイ
９５６    技術
【図１】
0004694256.tif 000023
【図２】
0004694256.tif 000024
【図３】
0004694256.tif 000025
【図４】
0004694256.tif 000026
【図５】
0004694256.tif 000027
【図６】
0004694256.tif 000028
【図７】
0004694256.tif 000029
【図８】
0004694256.tif 000030
【図９】
0004694256.tif 000031