(57)【特許請求の範囲】
【請求項１】
地形シーンに関連付けられた標高データのアレイの複数の標高グリッド点に基づき、前記地形シーンの照射を表すシャドウマスクを形成するための、コンピュータによって実現される方法であって、前記方法は、
ａ．標高値が複数の空間座標のそれぞれに関連付けられている標高点データを受信するステップと、
ｂ．特定のアンカー点に対して、各標高グリッド点での放射照度値によって特徴づけられる光源への方向を求めるステップと、
ｃ．前記光源を方位円の１つの象限に関連付けるステップと、
ｄ．前記光源に関連付けられた前記象限に基づき、１つのシャドウフロントラインプロパゲーションモードを選択するステップと、
ｅ．標高データの次のラインへの投影により、標高データの前記アレイに沿ってシャドウホライズンのプロパゲーションを行うステップと、
ｆ．コンピュータメモリのフロントラインバッファに記憶された前記シャドウホライズンを再帰的に更新するステップと、
ｇ．特定の標高点が前記シャドウホライズンの上方にあるかまたは下方にあるかに基づき、バイナリのシャドウマスクを形成するステップと、
を含む、コンピュータによって実現される方法。
【請求項２】
前記方法はさらに、前記バイナリのシャドウマスクによって変調された、前記標高グリッド点での前記光源の放射照度に基づき、特定のグリッド点への全日射入射に対する放射照度寄与分を計算するステップを含む、
請求項１記載のコンピュータによって実現される方法。
【請求項３】
前記光源は、太陽である、
請求項１記載のコンピュータによって実現される方法。
【請求項４】
前記シャドウホライズンのプロパゲーションを行うステップは、さらに、前記地形シーンの基礎表面の曲率が反映されるよう、前記光源の方向に変換を適用するステップを含む、
請求項１記載のコンピュータによって実現される方法。
【請求項５】
前記地形シーンの前記基礎表面は、実質的に球面状である、
請求項４記載のコンピュータによって実現される方法。
【請求項６】
前記地形シーンの前記基礎表面は、地球である、
請求項４記載のコンピュータによって実現される方法。
【請求項７】
単一のシャドウホライズンが前記フロントラインバッファに記憶される、
請求項１記載のコンピュータによって実現される方法。
【請求項８】
地形シーンに関連付けられた標高データのアレイの複数の標高グリッド点に基づき、前記地形シーンの照射を表すシャドウマスクを形成するためにコンピュータシステムを使用する非一時性のコンピュータ可読媒体であって、前記非一時性のコンピュータ可読媒体は、プロセッサによって実行される際に、前記プロセッサに、
ａ．標高値が複数の空間座標のそれぞれに関連付けられている標高点データを受信させ、
ｂ．特定のアンカー点に対して、方向および各標高グリッド点での放射照度値によって特徴づけられる光源への方向を求めさせ、
ｃ．前記光源を方位円の１つの象限に関連付けさせ、
ｄ．前記光源に関連付けられた前記象限に基づき、１つのシャドウフロントラインプロパゲーションモードを選択させ、
ｅ．標高データの次のラインへの投影により、標高データの前記アレイに沿ってシャドウホライズンのプロパゲーションを行わせ、
ｆ．フロントラインバッファに記憶された前記シャドウホライズンを再帰的に更新させ、
ｇ．特定の標高点が前記シャドウホライズンの上方にあるかまたは下方にあるかに基づき、バイナリのシャドウマスクを形成させる、
ようにするコンピュータの命令を記憶している、
非一時性のコンピュータ可読媒体。
【請求項９】
前記命令はさらに、前記プロセッサに、前記バイナリのシャドウマスクによって変調された、前記標高グリッド点での前記光源の放射照度に基づき、特定のグリッド点への全日射入射に対する放射照度寄与分を計算させる、
請求項８記載の非一時性のコンピュータ可読媒体。
【請求項１０】
前記命令はさらに、前記プロセッサに、前記地形シーンの基礎表面の曲率が反映されるよう、前記光源の方向に変換を適用させる、
請求項８記載の非一時性のコンピュータ可読媒体。
【請求項１１】
単一のシャドウホライズンが前記フロントラインバッファに記憶される、
請求項８記載の非一時性のコンピュータ可読媒体。
【請求項１２】
地形シーンに関連付けられた標高データのアレイの複数の標高グリッド点に基づき、前記地形シーンの照射を表すシャドウマスクを形成するためにコンピュータシステムを使用するコンピュータプログラムであって、前記コンピュータプログラムは、プロセッサによって実行される際に、前記プロセッサに、
ａ．標高値が複数の空間座標のそれぞれに関連付けられている標高点データを受信させ、
ｂ．特定のアンカー点に対して、方向および各標高グリッド点での放射照度値によって特徴づけられる光源への方向を求めさせ、
ｃ．前記光源を方位円の１つの象限に関連付けさせ、
ｄ．前記光源に関連付けられた前記象限に基づき、１つのシャドウフロントラインプロパゲーションモードを選択させ、
ｅ．標高データの次のラインへの投影により、標高データの前記アレイに沿ってシャドウホライズンのプロパゲーションを行わせ、
ｆ．フロントラインバッファに記憶された前記シャドウホライズンを再帰的に更新させ、
ｇ．特定の標高点が前記シャドウホライズンの上方にあるかまたは下方にあるかに基づき、バイナリのシャドウマスクを形成させる、
ようにするコンピュータの命令を含む、
コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、２０１７年３月３日提出の米国仮特許出願第６２／４６６５３１号（US Provisional Patent Application Serial No.62/466,531）の優先権を主張し、この出願は引用により本願に組み込まれるものとする。
【０００２】
本発明は、画像中のシャドウの形成に関しており、より具体的には、きわめて大きな２．５次元（２．５Ｄ）標高データセットに基づいてシャドウイングを行う方法および装置に関する。
【背景技術】
【０００３】
照明された地形に関するシャドウマッピングは、地形の起伏に陰影を付ける技術の本来的な部分である。光源が遮蔽されていないかぎり、表面上の所与のグリッド点は、この所与のグリッド点での表面に対する局所法線と、局所勾配と、アスペクト角とによって定義される直接ビーム放射輝度を受ける。これは、所与のグリッド点を中心とした３×３ピクセルカーネルの小さな局所面積を用いて予測可能である。
【０００４】
予備的定義：ここでのならびに添付の任意の請求項における使用の通り、以下の語句は、文脈において別のことを述べていないかぎり、指示された意味を有するものとする。
・「シャドウイング」または類義の「シャドウマッピング」「シャドウキャスティング」もしくは「シャドウプロジェクション」なる語は、ここでの使用の通り、シーンの３次元画像に陰影を加えることを記述しているものとする。特定の例には、全日射エネルギ束のうち直接ビーム放射照度成分を表す、遮蔽マスク（語は後に定義する）としての入射光エネルギもしくは反射光エネルギの放射照度マップ（後に定義する）の形成が含まれる。ただし、本発明の範囲には遮蔽マスクが形成されるか否かにかかわらずシャドウイングが含まれることを理解されたい。
・「マップ」は、あるドメイン内の各点に値を割り当てる関数（有限であるが、必ずしも連続的でない）である。
・「放射照度マップ」なる語は、特定の源からの光が当該点へ達するか否かに関連して、地域の各点に値（単位を有するものであってもなくてもよい）を割り当てるマップを記述するものとする。
・「遮蔽マスク」は、特定の源からの光が地域の各点に達するか否かを表す２つのバイナリ値のうち一方を仮定する放射照度マップである。
・「日射エネルギ束」なる語は、直接のまたは散乱もしくは反射によるとを問わず、特定の源、典型的には太陽による照射に起因する、特定の地点での特定の時間範囲にわたるワット時毎平方メートルの入射または瞬時ワット毎平方メートル（すなわち日射パワー束）の入射をいう。日射エネルギ束のうち１点での直接照明に起因する成分は、「全日射エネルギ束のうち直接ビーム放射照度成分」と称される。
・「勾配」なる語は、局所点で撮影された標高の勾配の規模（モジュラス）をいうものとする。
・「アスペクト角」なる語は、局所点での標高の勾配が最大となる方向であって、特定の基準方向、典型的には北に関して定義された方向をいうものとする。
・「スカイビュー」なる語は、特定の点から特定の方向での有効無限までの射線に沿った視線を意味するものとする。
・「ビューシェッド」なる語は、特定の点に関する全方向でのスカイビューであって、いわば当該特定の点を含む視線（ＬＯＳ）内の全ての周囲点を意味するものとする。
・「光ベクトル」なる語は、所与の点から照明源の位置への空間内方向を記述しており、照明源の輝度分布の中心軌跡によって定義される。「輝度」および他の測光用語は、Lang, Astrophysical Formulae (1980)に定義されている。照明源は、アンカー点からの有効無限距離にあり、いわば照明源から発せられた光の波面は、照明源から発した全ての射線およびアンカー点（後に定義する）への入射に対する有効法線である。光ベクトルに関連付けられた方向は、方位‐標高（ＡＺ‐ＥＬ）座標においてまたは他の座標系にしたがって特定可能である。なお、同語「光ベクトル」は、同一線ではあるが反対方向のライン、すなわち照明源から特定のアンカー点へのラインに沿った向きの射線に等しい度量で適用されることを理解されたい。
・「太陽ベクトル」なる語は、太陽に関連付けられた光ベクトルを記述する。当該語は、説明の利便性のためにここで帰納的に使用可能であり、当該分野の通常の知識を有する読者であれば、月または他の自然もしくは人工の照明源を包含することまで容易に一般化可能なはずである。
・方向（例えば上述の「光ベクトル」または「太陽ベクトル」）を求める際の基準となる所与の点は、ここでは「アンカー点」と称する。
【０００５】
複雑な地形学の分野では、幾何学は、所与の太陽ベクトル（例えば（方位、標高）の座標において特定されており、ここでは（ＡＺ，ＥＬ）とも称する）が当該点からのビュー内にあるか否かが判定されるよう、１つの点に対して全方向のスカイビューを既知としなければならないことを要求する。標高のラジアル座標および方位のタンジェント座標の極のプロットとしての地形点に対するビューシェッドを計算する技術は、論文J.Tovar-Pescador et al., “On the use of the digital elevation model to estimate the solar radiation in areas of complex topography”, Meteorol.Appl., vol.13 (2006)の第279頁−第287頁において設計されている。著者らが設計した点ベースのビューシェッドマップを形成する概略的なプロセスが図１のＡ−Ｃに示されている。図１のＡには、特定のグリッド点１０１を中心としたシーンのディジタル標高モデル（ＤＥＭ）が示されている。図１のＢは、グリッド点１０１に対するスカイビューの標高断面図であり、図１のＣは、グリッド点１０１に関するビューシェッドの方位‐標高（ＡＺ‐ＥＬ）表現である。
【０００６】
フル３Ｄ幾何データが存在しないことに加え、ＧＩＳデータセットの別の重大な特徴は、しばしば近似的なリアルタイムモードで処理しなければならないデータがきわめて大量であることである。各点に対するビューシェッドを形成する初期プロセスは、計算上きわめて高コストであるが、任意の所与の時間帯（または時間インターバル）に対する以下のシャドウマップ形成は、きわめて高速である。当該方法の精度の制限は、極座標におけるビューシェッド分布の形成のために選択された方位方向の離散数によって定義され、正確に１２の方向の間の補間がいわば３６０度未満の低い忠実度を有することが明らかである。
【発明の概要】
【課題を解決するための手段】
【０００７】
本発明の各実施形態によれば、地形シーンに関連付けられた標高データのアレイの複数の標高グリッド点に基づき、地形シーンの照射を表すシャドウマスクを形成するための、コンピュータによって実現される方法が提供される。当該方法は、標高値が複数の空間座標のそれぞれに関連付けられている標高点データを受信するステップ、特定のアンカー点に対して、各標高グリッド点での放射照度値によって特徴づけられる光源への方向を求めるステップ、光源を方位円の１つの象限に関連付けるステップ、光源に関連付けられた象限に基づき、１つのシャドウフロントラインプロパゲーションモードを選択するステップ、標高データの次のラインへの投影により、標高データのアレイに沿ってシャドウホライズンのプロパゲーションを行うステップ、コンピュータメモリのフロントラインバッファに記憶されたシャドウホライズンを再帰的に更新するステップ、および特定の標高点がシャドウホライズンの上方にあるかまたは下方にあるかに基づき、バイナリのシャドウマスクを形成すステップを含む。
【０００８】
本発明の他の実施形態によれば、バイナリのシャドウマスクによって変調された、標高グリッド点での光源の放射照度に基づき、特定のグリッド点への全日射入射に対する放射照度寄与分を計算する付加ステップを設けることができる。
【０００９】
本発明の別の実施形態では、光源は太陽であってよい。
【００１０】
本発明のさらに別の実施形態では、シャドウホライズンのプロパゲーションを行うことはさらに、地形シーンの基礎表面の曲率が反映されるよう、光源の方向に変換を適用する別のステップを含むことができる。地形シーンの基礎表面は、実質的には球面状であってよく、より具体的には地球であってよい。
【００１１】
本発明の別の態様によれば、地形シーンに関連付けられた標高データのアレイの複数の標高グリッド点に基づき、地形シーンの照射を表すシャドウマスクを形成するためにコンピュータシステムを使用するコンピュータプログラム製品が提供される。当該コンピュータプログラム製品は、プロセッサによって実行される際に、当該プロセッサに、標高値が複数の空間座標のそれぞれに関連付けられている標高点データを受信させ、特定のアンカー点に対して、各標高グリッド点での放射照度値によって特徴づけられる光源への方向を求めさせ、光源を方位円の１つの象限に関連付けさせ、光源に関連付けられた象限に基づき、１つのシャドウフロントラインプロパゲーションモードを選択させ、標高データの次のラインへの投影により、標高データのアレイに沿ってシャドウホライズンのプロパゲーションを行わせ、さらに特定の標高点がシャドウホライズンの上方にあるかまたは下方にあるかに基づき、バイナリのシャドウマスクを形成させるようにするコンピュータ命令を記憶した非一時性のコンピュータ可読媒体を含む。
【００１２】
他の実施形態では、命令はさらに、プロセッサに、バイナリのシャドウマスクによって変調された、標高グリッド点での光源の放射照度に基づき、特定のグリッド点への全日射入射に対する放射照度寄与分を計算させることができる。命令はさらに、プロセッサに、地形シーンの基礎表面の曲率が反映されるよう、光源の方向に変換を適用させることもできる。
【００１３】
本発明は、図面に関連して、以下の特定の実施形態の詳細な説明を参照することにより、より完全に理解されるであろう。
【図面の簡単な説明】
【００１４】
【図１】Ａは、特定のグリッド点を中心としたシーンのディジタル標高モデル（ＤＥＭ）を示す図であり、Ｂは、当該点に対するスカイビューの標高断面図であり、Ｃは、同じ点に対するビューシェッドの従来技術の方位‐標高（ＡＺ‐ＥＬ）表現である。
【図２】本発明の一実施形態による、２．５Ｄデータのシャドウ予測の概略的な表現である。
【図３】本発明の一実施形態による、シャドウマップ画像の形成の各ステップを示すフローチャートである。
【図４】本発明の一実施形態によるシャドウキャスティングを示す、２．５Ｄ標高データから形成された画像である。
【図５】中緯度アンカー点において、例えば北緯４９°線に沿って、緯１０°および経１５°にわたって広がる、アレイ規則空間のグリッド点の水平方向の全体形状を示す図である。
【図６】図５で使用されている中緯度アンカー点において、緯１０°および経１５°にわたって広がる、アレイ規則空間のグリッド点の垂直方向の全体形状を示す図である。
【図７】Ａは、図５のグリッド点のアレイに関する入射光ベクトルを示す図であり、Ｂは、原光ベクトル方向を示す図であり、Ｃは、本発明の一実施形態により変換された方向を示す図である。
【図８】本発明の態様の実現に使用可能なシステムの一実施形態を概略的に示す図である。
【発明を実施するための形態】
【００１５】
さらなる定義：ここでのならびに添付の任意の請求項における使用の通り、以下の語句は、文脈において別のことを述べていないかぎり、指示された意味を有するものとする。
・「画像」なる語は、有形の形式であるかまたはそうでなく認知上の形式もしくはその他であるかを問わず、あらゆる多次元表現をいうものとし、ここでは、幾つかの特性の値（振幅、位相など）が地形空間内の物体の次元座標に対応するものの必ずしも１対１でマッピングされない複数の位置（またはユークリッド空間内のベクトル、典型的にはＲ２）のそれぞれに関連付けられている。つまり、例えば、あるフィールドの空間分布のグラフィック表示は、スカラーまたはベクトル、例えば輝度もしくは色もしくは強度のいずれであっても、１つの画像を構成する。よって、数値のアレイ、例えばコンピュータメモリ内またはホログラム媒体内の３Ｄホログラムデータセットについても同様である。同様に「イメージング」とは、１つもしくは複数の画像として上述した地形特性をレンダリングすることをいう。
・「シャドウマップ」なる語は、ここでは「遮蔽マップ」または「シャドウマスク」なる語と同義に用い、「観察者位置」と記述される空間内位置から見て、ピクセルが可視であるか否かをタグによって示したバイナリマップをいう。シャドウマップは、任意の特定の標高グリッド点が特定の照明源からの放射照度に曝されるか否かを表す標高データセットの３Ｄレンダリング上にオーバレイ可能である。
・「照明点」なる語は、例えばシーンの照明のために、光が発せられたと仮定される（必須ではないが典型的には平行な射線での）厳密に数学的な意味においてコンパクトな、厳密に幾何学的な意味における１点、または３次元空間内に定義された領域をいう「パッチ」のいずれかをいうことができる。
・「遠隔の光源方向」とは、照明源から発せられた光がプレーナの位相フロントで伝播すると仮定可能な、すなわち全ての射線が照明されるシーンへ向かって平行に走行すると仮定可能な方向をいう。
・「時間」なる語は、ここでは最も一般的に可能な意味で用いられており、日時および天文学的時期、または所望の参照フレームにおける時間を示すために使用される何らかの他のパラメータを含む。
・「標高データ」または等価の「２．５Ｄデータ」なる語は、例えば、特定の点または座標または表面、例えば地表面に対応する標高を提供するデータである。標高データは、これも単なる例示に過ぎないが、リモートセンシング法、例えばＬＩＤＡＲまたは他の航空測量法を含む任意の数の方式において、または陸上測量によって、収集可能である。
【００１６】
３つの要素、すなわち直接ビーム放射照度、拡散放射（天空光）および地表アルベド（近傍地勢が任意の非水平の表面を照明する）が、各標高グリッド点での照明に寄与する。
【００１７】
本発明の実施形態によれば、各方法は、メモリ効率良くかつ計算が高速であるという２つの点で有利でありうる方式でシャドウマスクを形成するために提供される。従来技術によれば、シャドウマップを形成する多数の手法を実施することができる。本発明には、ここに説明しかつ特許請求する種々の新規な方法が属する。
【００１８】
図２を参照しながら、以下、本発明の一実施形態によるシャドウ予測の方法を説明し、シャドウ予測の方法は、全体的に番号２００によって指定されている。本発明の範囲においては、当該方法による各ステップは必ずしも図示した、説明したまたは特許請求した順序で実行されなくてもよいことを理解されたい。例えば、第１のステップとは、番号付けの問題であって、必ずしも時間的に最初でなくてよい。
【００１９】
標高点データは航空機または衛星または他の手段を用いて取得されるが、ここでは、帰納的簡便性のために、データが（図８に示されている）コンピュータシステム６００によって受信され、（図３に示されている）全体的に番号３０１で指定された、東‐西方向（方位９０°および２７０°）に対応する行と北‐南方向（方位０°および１８０°）に対応する列とを有するアレイとしてメモリデバイス６０４に記憶されるものと仮定する。データアレイへの方向の任意の割り当ては帰納的簡便性のためのものであり、アンカー点を中心としたアレイの回転とここで説明する相応のアルゴリズムの修正とは、通常の知識を有する読者の能力内で行われることを理解されたい。アレイ３０１はここでは「グリッド点３０１」または「グリッド３０１」とも称されることがあり、本発明の範囲において、種々の点がアレイ３０１から消失しうるが、ここで説明し特許請求する方法は依然として実行可能であることを理解されたい。
【００２０】
全体的に番号２００で指定されているシャドウマスク形成のプロセスを開始するため、標高データがマトリクスフォーマットで取得、受信および記憶され（２０１）、いわば、データは、直交する基本方向、すなわち帰納的目的のためのみであるが北‐南方向および東‐西方向として記述される方向を示す２つのインデクスによって特徴づけられる。同じ方向条件を用いて、特定の光のベクトル方位を含む象限が識別される（２０３）。他の場合には「セクタ」とも称される「象限」は、方位円の４つの部分への分割をいい、ここで、方位は、従来のごとく基準北方向での０°に対して時計回りで定義される。方位円は特定のアンカー点を取り巻く３６０°の円である。「光ベクトル方位」とは、上で定義したように、光ベクトルの方位成分の値である。それぞれ４つの基本方向を中心とした４象限（または４セクタ）は、
・ＮＷ‐ＮＥ：３１５°から４５°、
・ＮＥ‐ＳＥ：４５°から１３５°、
・ＳＥ‐ＳＷ：１３５°から２２５°、
・ＳＷ‐ＮＷ：２２５°から３１５°、
である。
【００２１】
光ベクトル方位のセクタに基づいて、４つのシャドウフロントラインプロパゲーションモードのうち１つが選択される（２０５）。すなわち、
・ＮＷ‐ＮＥ：行に沿って上方から下方へ、
・ＮＥ‐ＳＥ：列に沿って右方から左方へ、
・ＳＥ‐ＳＷ：行に沿って下方から上方へ、
・ＳＷ‐ＮＷ：列に沿って左方から右方へ、
である。
【００２２】
ここでのならびに添付の任意の請求項における使用の通り、「シャドウフロントライン」なる語は、所与の点が特定の照明源から特定のアンカー点への光ベクトルを遮蔽するか否かについて現在計算評価を受けている行（または状況により列）をいうものとする。
【００２３】
「第１のライン」とは、照明源へ向かう標高データのアレイ３０１の極値行または（状況により）極値列に相当する。つまり、照明源がＮＷ‐ＮＥ象限にある場合、第１のラインは、アレイ３０１の最初の行３０５（以下、帰納的簡便性のために第１のラインと称する）である。シャドウフロントラインは、初期的には、当該第１のラインである。（図２に示されている）ステップ２０７では、第１のラインの各点３０３は、「照明されている」または「光を受けた」とのフラグを付され、各点３０３に関連付けられた標高がシャドウフロントラインにおける「光遮蔽高さ」としてマークされる。
【００２４】
シャドウフロントラインの点３０３は、光ベクトル３０７に沿って、アレイ３０１の次のライン３０９に投影され（ステップ２０９）、記録される。「投影される」とは、ここでの語の使用の通り、点３０３の標高を、光ベクトル３０７に対して平行なラインにより、次のライン３０９内の１点３１３の標高に接続することを意味する。次のライン３０９では、光遮蔽高さが、標高データの各グリッド点の標高のうち大きなものとして、または前のライン３０５内の１点の標高の投影として記録される（２０９）。グリッド点は、スプラインフィット、例えばエルミートスプラインによって接続可能であり、ここで（上で定義した）「シャドウフロントライン」と称される、照明源の方向に向かって見て暗所と明所とを分離する（図４に示された）曲線４０５が得られる。シャドウフロントラインは、コンピュータメモリのフロントラインバッファ内に記憶され（２１１）、次のライン（行または列）において再帰的に更新される。次のライン（照明源が現れる象限に依存して、状況により、行または列）へのシャドウプロパゲーションは、シャドウフロントラインを生じさせるが、このことについては図４を参照して後に詳述する。次のラインでの最大高さの記録は、「新たなシャドウフロントラインの収集」と称されることがある。その後、遮蔽高さのプロパゲーションが、アレイ３０１の最終ライン３１５に達するまで、次のラインに対して反復される。よって、各グリッド点は、照明源からの光が遮蔽される下方の標高によってマークされる。
【００２５】
フロントラインプロパゲーションは、これまで説明したように、有利には、メモリ効率良くかつ計算が高速なシャドウマスクの形成のために設けることができる。なぜなら、入力画像は、ラインごとに（行ごとまたは列ごとに）読まれればよく、出力マスク画像は、エリアキャッシュを要求せずにラインごとに書き込まれるからである。いったん所与の行または列が処理されると、入力ラインおよび出力ラインは作動中のメモリから除去可能であり、再びアクセスされることはなく、単一のシャドウフロントライン４０５のみがフロントラインバッファに記憶されるべきものとして保持される。
【００２６】
図４を参照しながら、以下シャドウフロントライン４０５の等高線を説明する。ここでは、黒丸点４１０が、第２の列３０９での太陽光を受けた点を表し、青丸点（灰色）４１２がシャドウ点を表し、太線円４１５が現在のステップでシャドウフロントライン４０５内に収集された光遮蔽高さを表す。細線円４１７は、（図３に示されている）光ベクトル３０７の方向、すなわちこの例では水平および垂直の勾配の（−２５°，−４５°）方向に沿って現在のラインへ投影された、先行のシャドウフロントラインを表す。スプライン曲線４０５は、西（図３の左方）に向かって見て、現在の列での暗所と明所とを分離する「ホライズンライン」を表す。「ホライズンライン」および「シャドウホライズン」なる語は、上で定義した「シャドウフロントライン」なる語と完全に同義である。ホライズンラインより上方にいる全ての観察者が照明源の光を見るのに対して、図４の位置５，６，７にいる観察者は、彼らの標高がシャドウフロントラインより下方にあることから、シャドウ内にある。
【００２７】
本発明の他の態様によれば、シャドウキャスティングは、測地座標（緯度、経度、高さ）もしくはマップ投影された標高グリッド（東向き、北向き、高さ）とアンカーされた測心カルテシアングリッドとの間の厳密な３Ｄ変換の多項式モデルによる近似を使用しているが、シーン全体への変換の適用に代えて、変換が光ベクトル３０７に適用される。
【００２８】
測地データもしくはマップ投影データを測心データに関連付ける厳密な３Ｄ変換が多数の非線形の変換項を要求するのに対し、多項式近似は、連続的であるかまたは部分ごとに平滑であるかを問わず本発明の範囲において使用可能であり、３次元の多数の点から成るデータのＸＹＺ変換の速度向上のためにきわめてよく知られており、通常使用されている。当該アプローチは、本発明の実施形態によれば、局所光ベクトル３０７の方向に対する角度補正をモデリングするために使用される。
【００２９】
一例として、（図３に示されている）点３０１のグリッドが、ある中緯度のアンカー点（例えば中央ヨーロッパまたは例えば米加国境を成す北緯４９°線に沿って）緯１０°および経１５°にわたって広がっている場合、測心カルテシアンフレームにおけるアレイ３０１の全体形状は、水平方向５０１では図５に示されているようになり、垂直方向６０１では図６に示されているようになる。
【００３０】
行および列の双方がまったく直線ではなく、行のほうが列よりも湾曲している。にもかかわらず、直接に隣接する２つのグリッドノード間の線分は直線にほかならないと仮定でき、光線が次の行または次の列と交差する際の両側の２つの点を接続する線分の水平方向および垂直方向に関して、前の行または前の列のグリッドノードから発した光方向（すなわち図３に示されている光ベクトル３０７の方向）を補正するだけでよい。
【００３１】
単一のセル長方形に関するかぎり、１つの角から発して所与の比で対辺を２分割する光線の処理は、当該比に対して単一の補正しか要さない。局所的な形状変形、例えば差分スケーリング、回転、せん断などの全てが、対辺を２分割する比の単一の変更、すなわち水平比に対する１回の補正と地球の湾曲度に起因する垂直仰角に対する１回の補正とに累積的に寄与する。
【００３２】
マトリクス内のグリッドノード（ｉ，ｊ）位置の関数としてのこうした補正は、補正形態に大きく寄与する項のみを保持する特別な２変量多項式によってモデリング可能である。使用される特別な多項式およびＬ１ノルム最小化または他の手法に基づくそのパラメタライズは、当該分野においてよく知られており、その使用についての厳密な説明は、ここで述べる必要なく、通常の知識を有する読者に設計選択が委ねられ、http://www.dtic.mil/dtic/tr/fulltext/u2/a307127.pdfで入手可能な“Handbook for Transformation of Datums, Projections, Grids”(1996)に見出すことができるので、引用により本願に組み込まれるものとする。多くの特定の多項式関数のうち任意の関数が、連続的であるかまたは部分ごとに平滑であるかを問わず、所与の標高グリッドに対する垂直／水平データに依存した設計選択の問題として選択可能であり、その全てが本発明の範囲内に該当する。測地グリッドがマップ投影されたグリッドとは異なる補正式を有すること、横メルカトル投影がランベルト円錐投影とは異なる形状を有しうることなどは明らかであるが、これらのことも全て特許請求される本発明の範囲内に該当する。本発明の実施形態によれば、座標フレームに適用される変形は、上述したシャドウキャスティングプロセスが実行される際に、入射光ベクトル３０７に適用される。
【００３３】
光ベクトル３０７の方向を補正する方法の一例を以下に説明する。（フロントラインプロパゲーションが行ごとに進行すると仮定して）各行につき（また必要な変更を加えて各列につき）、単一の多項式が、基準アンカー点（Ｘ，Ｙ，Ｚ）に対する全ての点（ｘ，ｙ，ｚ）に使用される。不一致が補正され、
（ｄｘ，ｄｙ）＝（Ｆｘ（Ｘ，Ｙ，Ｚ）−ｘ，Ｆｙ（Ｘ，Ｙ，Ｚ）−ｙ）
となり、ここで（Ｆｘ，Ｆｙ）は、測地座標系（またはユニバーサル横メルカトル（ＵＴＭ）など）から局所測心カルテシアン座標系への投影であり、それ以外の場合にはここでは「マッピング軸」と称される。
【００３４】
単一の多項式が、各横方向次元をモデリングするために用いられ、例えば、
ｄｘ＝ｃ０ｙ＋ｃ１ｘｙ＋ｃ２ｘ２＋ｃ３ｙ２＋ｃ４ｘｚ＋ｃ５ｙｚ＋ｃ６ｘｙ２＋ｃ７ｘ３＋ｃ８ｘ２ｙ＋ｃ９ｙ３
となる。上記の１０項の３次多項式は例として掲げたものであり、本発明の範囲においては任意のモデル関数を使用可能である。使用される多項式は、モデルフィッティングに使用される立方グリッドの外側では近似の精度が低下するが、３次元ＵＴＭ空間内（グリッド３０１内、グリッドノード上、ならびに外側）の任意の点でのｘｔоｐо＝ｘＵＴＭ＋ｄｘのモデリングに用いられる。他の多項式の項は、設計選択の問題として、ソースデータ、すなわち測地、ＵＴＭ、投影ランベルト円錐などに基づいて、保持可能である。
【００３５】
係数ｐｘ＝［ｃ０，…ｃ１０］のパラメータベクトルは、標準数値技術を用いて｛Ｂ＊ｐｘ−Ｆｘ（Ｘ，Ｙ，Ｚ）−ｘ｝を最小化する最小二乗の最小化問題への解として定義される。つまり、原ラスタ標高グリッド３０１における各ピクセルに対して、２分割比に対する補正が、上述したフロントラインプロパゲーションにおける次のラインに対して見出される。
【００３６】
図７のＢ，Ｃを参照すると、コンフォーマルマッピング（局所的に角度を保存する正則マッピング、例えば測地座標から測心座標へのマッピング）のための「２分割比」が次のように定義されている。すなわち、未変換の座標系（すなわち、コンフォーマルマッピングのドメイン）における対辺線分
【数１】
0006899915.tif 000002
を２分割する角度φに対して、２分割比は、変換フレームにおける線分
【数２】
0006899915.tif 000003
の長さに対する、線分
【数３】
0006899915.tif 000004
の長さの比であり、ここで、当該比は、図７のＣに示されているように、αによって記述されている。
【００３７】
原長方形グリッド、すなわち所与のいわばＵＴＭ座標において、任意の列上の隣接する任意の２点につき、２分割比（α：（１−α）である）は一定であるが、変換されたグリッドでは、四辺形のメッシュとなり、２分割比はピクセル位置に応じて変化する。
【００３８】
光ベクトル３０７の標高ＥＬに関するかぎり、これは、アンカー点に対する測地座標と測心カルテシアン座標との間の不一致の残留分を最小化することにより、係数が求められ、アンカー点からの距離における第２度の多項式補正の適用によって補正される。
【００３９】
また、本発明の種々の態様は、図８に示されているような汎用コンピュータシステム６００で実行される特別のソフトウェアとしても実現可能である。代替的に、本発明の態様は、有利には、モバイルフォン上、タブレット上および他のデバイス上に実現される。コンピュータシステム６００は、１つもしくは複数のメモリデバイス６０４、例えばディスクドライブ、メモリまたはデータを記憶する他のデバイスに接続されたデータベースサーバ６０３を含むことができる。データベースサーバ６０３は、複数の点での標高を含む点標高データ、または本発明を適用可能な他のデータを記憶している。プロセッサ６０７（ここでは中央処理ユニットとも称される）または処理サーバ６０６は、上述の説明における教示のごとくシャドウキャスティングを行うように構成されたコンピュータ実行可能ソフトウェアを含む。代替的に、コンピュータプログラム製品は、プロセッサ６０７によって実行される際に、上述の説明における教示のごとくプロセッサにシャドウキャスティングを行わせるためのコンピュータ命令を記憶した非一時性のコンピュータ可読媒体を有することができる。メモリ６０４は、典型的には、コンピュータシステム６００の動作中、プログラムおよびデータを記憶するために用いられる。コンピュータシステム６００の各コンポーネントは、（例えば同じマシン内に組み込まれたコンポーネント間の）１つもしくは複数のバスおよび／または（例えば別個の離散的なマシン上にあるコンポーネント間の）ネットワークを含むことができる相互接続機構６０５によって結合可能である。相互接続機構６０５により、システム６００のシステムコンポーネント間で交換すべき通信（例えばデータ、命令）が可能となる。また、コンピュータシステム６００は、１つもしくは複数の入力デバイス６０２、例えばキーボード、マウス、トラックボール、マイクロフォン、タッチスクリーン、および１つもしくは複数の出力デバイス６０１、例えば印刷デバイス、ディスプレイスクリーン、スピーカを含む。加えて、コンピュータシステム６００は、自身を通信ネットワークへ（付加的にもしくは代替的には相互接続機構へ）接続する１つもしくは複数のインタフェース（図示しない）を含むことができる。
【００４０】
コンピュータシステムは、特別にプログラミングされた専用目的のためのハードウェア、例えば特定用途向け集積回路（ＡＳＩＣ）を含むことができる。本発明の態様は、ソフトウェア、ハードウェアもしくはファームウェア、またはこれらの任意の組み合わせにおいて実現可能である。さらに、こうした方法、動作、システム、システムエレメントおよびそのコンポーネントは、上述したコンピュータシステムの一部として、または独立したコンポーネントとして実現可能である。
【００４１】
コンピュータシステム６００は、本発明の種々の態様を実施可能なコンピュータシステムの１つのタイプの例として示されているが、本発明の態様は図８に示したコンピュータシステム上に実現されるものに限定されないことを理解されたい。本発明の種々の態様は、図８に示したものとは異なるアーキテクチャまたはコンポーネントを有する１つもしくは複数のコンピュータ上で実施可能である。
【００４２】
サーバ６０３，６０６に関連して使用されるプロセッサ６０７およびオペレーティングシステムは、アプリケーションプログラムを高級プログラミング言語で記述するコンピュータプラットフォームを定義する。ただし、本発明は特定のコンピュータシステムプラットフォーム、プロセッサ、オペレーティングシステムまたはネットワークに限定されないことを理解されたい。また、本発明が特定のプログラミング言語またはコンピュータシステムに限定されないことは当該分野の技術者には明らかなはずである。さらに、他の適切なプログラミング言語および他の適切なコンピュータシステムを使用可能であることも理解されたい。
【００４３】
コンピュータシステムの１つもしくは複数の部分は、通信ネットワークに結合された１つもしくは複数のコンピュータシステム（図示しない）に分散可能である。なお、こうしたコンピュータシステムは、汎用コンピュータシステムであってよい。例えば、本発明の種々の態様は、１つもしくは複数のクライアントコンピュータにサービス（例えばサーバ）を提供するように構成された、または分散システムの一部としてタスク全体を実行するように構成された、１つもしくは複数のコンピュータシステムに分散可能である。例えば、本発明の種々の態様は、本発明の種々の態様による種々の機能を実行する１つもしくは複数のサーバシステムに分散されたコンポーネントを含むクライアントサーバシステム上で実行可能である。こうしたコンポーネントは、ｈ通信プロトコル（例えばＴＣＰ／ＩＰ）を用いて通信ネットワーク（例えばインタネット）を介して通信する中間コードまたは解釈コードを実行可能である。
【００４４】
本発明は、任意の特定のシステム上またはシステム群上での実行に限定されないことを理解されたい。また、本発明は、任意の特定の分散アーキテクチャ、ネットワークまたは通信プロトコルに限定されないことも理解されたい。
【００４５】
本発明の幾つかの説明的な実施形態を説明したが、上述した事柄は、単に説明のために非限定的に、例示として提示したに過ぎないことは、当該分野の技術者には明らかなはずである。多数の修正および他の説明的な実施形態も当該分野の通常の知識を有する者の視野に捉えられており、本発明の範囲内に該当するものと企図されている。特に、シャドウキャスティングの概念において説明を行ったが、本発明は当該の文脈に限定されない。プロシージャは多様な照明レンダリングの分野に適用可能である。
【００４６】
さらに、提示した例は方法動作またはシステムエレメントの特定の組み合わせを含むが、これらの動作およびエレメントが、シャドウマッピングの同じ課題を達成するため、他の方式で組み合わせ可能であることも理解されたい。１つの実施形態のみに関連して検討した動作、エレメントおよびフィーチャが他の実施形態において類似の役割を果たすことの排除は意図していない。
【００４７】
特許請求の範囲における、各請求項要素を修飾する「第１の」「第２の」「第３の」などの通常語の使用は、それ自体では、１つの請求項要素が他要素に対して有する優先性、上位性もしくは序列、または方法動作を実行する時間順序を表すものでなく、これらは単に、ある名称を有する１つの請求項要素を、（通常語を使用した）同じ名称を有する別の要素から区別するための標識として用いているものであり、これにより請求項要素が区別される。付加的に、単一のデバイスフィーチャは、１つの請求項で個々に言及される要素の要求を満足することができる。
【００４８】
本発明を上述した例示的実施形態によって説明したが、ここに開示した本発明のコンセプトから離れることなく、説明した実施形態への修正および変更を行いうることは当該分野の通常の知識を有する者には理解されるであろう。例えば、フローチャートを参照しながらシャドウ予測法の幾つかの態様を説明したが、当該分野の技術者であれば、フローチャートの各ブロックの全てもしくは一部の機能、動作、判定またはフローチャートのブロックの組み合わせが組み合わせ可能であること、個々の動作へ分割可能であることまたは他の順序で実行可能であることは容易に理解されるはずである。また、各実施形態を、種々の説明的なデータ構造に関連して説明したが、当該分野の技術者であれば、種々のデータ構造を用いてシステムを実現可能であることも理解されるであろう。さらに、開示した各態様またはこれらの態様の一部は、上で列挙しなかった手法で組み合わせることもできる。よって、本発明は開示した各実施形態に限定されると見なされてはならない。
【図１】
0006899915.tif 000005
【図２】
0006899915.tif 000006
【図３】
0006899915.tif 000007
【図４】
0006899915.tif 000008
【図５】
0006899915.tif 000009
【図６】
0006899915.tif 000010
【図７】
0006899915.tif 000011
【図８】
0006899915.tif 000012