(57)【特許請求の範囲】
【請求項１】
３次元レーザスキャンデータの画像をレンダリングする方法であって、
所定のスキャンのレーザスキャンデータのセットを球状変位マップとしてグラフィック処理ユニットに提供する段階と、
前記グラフィック処理ユニットにより、前記球状変位マップをサンプリングすることによってテッセレーションパターンを生成する段階と、を備える、方法。
【請求項２】
前記所定のスキャンの前記レーザスキャンデータのセットを前記球状変位マップとして提供する段階は、
所定の位置でレーザスキャナによって生成されたレーザスキャンデータのセットを受信する段階と、
所定の方位角および所定の仰角における所定のレーザスキャンポイントについてのレンジの値を、前記レーザスキャンデータから、レーザスキャンの方位角及び迎角により定義されるテクスチャにおける前記所定の方位角および前記所定の仰角に対応するテクセル位置のテクセルにコピーする段階と、
を備える、請求項１に記載の方法。
【請求項３】
前記球状変位マップにおける複数の隣接ポイントの間における複数の不連続を識別する段階と、
前記複数の隣接ポイントをマーク付けする段階とをさらに備える、請求項１または２に記載の方法。
【請求項４】
前記球状変位マップに基づいて法線マップを生成する段階をさらに備える、請求項１から３のいずれか一項に記載の方法。
【請求項５】
前記法線マップを生成する段階は、前記球状変位マップにおけるそれぞれのポイントについて法線を算出する段階と、前記法線を法線マップに格納する段階とを備える、請求項４に記載の方法。
【請求項６】
前記球状変位マップに基づいて混合テクスチャを生成する段階をさらに備える、請求項１から５のいずれか一項に記載の方法。
【請求項７】
所定のスキャンについて、複数のパッチを有するパッチマップを生成する段階をさらに備える、請求項１から６のいずれか一項に記載の方法。
【請求項８】
前記パッチマップは、それぞれのパッチにつき相対テッセレーションレベルを含む、請求項７に記載の方法。
【請求項９】
前記テッセレーションパターンにおける三角形の頂点の形成部分は、不連続上にあるか、または不連続に隣接するとしてマーク付けされているかを判断する段階と、前記頂点が無効であると判断することに基づいて、前記三角形をカリングする段階と、をさらに備える、請求項１から８のいずれか一項に記載の方法。
【請求項１０】
前記スキャンに対して画素のセットを生成する段階と、深度テストを実行する段階と、を備える、請求項１から９のいずれか一項に記載の方法。
【請求項１１】
請求項１から１０のいずれか一項に記載の方法を実行するための複数の命令を備える、コンピュータプログラム。
【請求項１２】
請求項１１に記載のコンピュータプログラムを格納している、コンピュータ可読媒体。
【請求項１３】
メモリと、
少なくとも１つのグラフィック処理ユニットを有する少なくとも１つの処理装置と、を備え、
前記メモリは、所定のスキャンについてレーザスキャンデータのセットを球状変位マップとして格納し、前記少なくとも１つのグラフィック処理ユニットは、前記球状変位マップをサンプリングすることによってテッセレーションパターンを生成する、
コンピュータシステム。
【請求項１４】
前記少なくとも１つの処理装置は、マイクロソフト（登録商標）ＤｉｒｅｃｔＸ（登録商標）１１アプリケーション・プログラミング・インタフェースを使用して構成される、請求項１３に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、レーザスキャンデータの画像をレンダリングする方法およびシステムに関する。
【背景技術】
【０００２】
３次元レーザスキャナは、プロセスプラント、船舶または他の施設等の環境を調査するために使用され得る。典型的なスキャナは、スキャナとビュー内にある表面上のポイントとの間の距離を測定し得るレーザ距離計を含む。視野全体（通常、水平方向に３６０度、鉛直方向にほぼ１８０度）を一斉にスイープすることによって、スキャナは、周囲環境についての一式のレンジ（本明細書において「レーザスキャンデータ」と称される）をキャプチャし得る。これらは、３次元空間において、「ポイントクラウド」としばしば称されるポイントのセットを生成するために使用され得る。ポイントクラウドの例は、ＥＰ１  １７６  ３９３  Ａ２に記載されている。
【０００３】
複数のスキャンは、環境における複数の異なる位置で実行され得、複数の異なるスキャンからの複数のポイントクラウドが、より広いエリアをカバーする複合（または「統合」）ポイントクラウドを生成するべく、組み合わされ得る。ポイントクラウドデータを組み合わせることの例は、ＷＯ２００４／００３８４４  Ａ１において見つけことができる。
【０００４】
レンジデータを取得することに加え、スキャナは、また、反射したレーザ光の強度を測定するか、またはカメラを使用することによっても周囲環境の複数の画像をキャプチャし得る。
【０００５】
１または複数のポイントクラウドおよび複数の画像は、ポイントクラウド・ビューアー・アプリケーションまたは３次元コンピュータ支援設計（ＣＡＤ）アプリケーションを使用して環境を可視化および／または解析するために使用され得る。通常、これらのアプリケーションは、２つのカテゴリ、すなわち、複数の個々のスキャンからの複数のポイントで機能するものと、複数のスキャンから組み合わされた複数のポイントで機能するものとに該当する。
【０００６】
レーザスキャンの複数の最も単純な応用の１つは、個々のスキャンによってキャプチャされた画像を表示することである。レーザスキャンからの画像は球状であり、レーザスキャナの周囲のエリアを対象に含めることから、ソフトウェアアプリケーションは画像を球体内へとマッピングし得る。アプリケーションは、球体の一部をコンピュータスクリーンに表示し得る。
【０００７】
ユーザは、全体画像の異なる複数の部分を見るべく、ビューを回転させ得る。この表示は、「バブルビュー」と呼ばれる。
【０００８】
バブルビューにおいて、ユーザは、画像上においてスポットを選択し得、そのレーザスキャンのポイントクラウドデータを使用してその位置の３次元座標を取得し得る。２つのポイントを選択することによって、ユーザは、複数の距離を測定し得る。
【０００９】
１つのタイプのアプリケーションは、バブルビューにおいて３次元ＣＡＤモデルを重ねることができる。アプリケーションは、バブルビューにおける複数のポイントの３次元位置を知っていることから、それは、バブルビューの背後のＣＡＤモデルの適切な複数の部分を不明瞭にし得る。この組み合わせられた画像は、施設の新しい複数のエリアを設計する場合に有用であり得る。
【００１０】
バブルビューの魅力的な特徴は、それがリアルに見えることである。リアリズムは、スキャナ位置でキャプチャされた画像によってもたらされる。しかしながら、複数のバブルビューの制限は、それらが、レーザスキャナが配置された複数の位置に対してのみ生成され得ることである。ユーザは、バブルビューを選択し、左右に、または上下に回転させ得るが、彼／彼女は、異なる視点から環境を見るべく、前方向、後方向、水平方向または鉛直方向には移動できない。
【００１１】
フリーローミングを可能にするべく、いくつかのソフトウェアアプリケーションは、複数のスキャンから組み合わされたポイントクラウドと連携する。そのようなアプリケーションを使用し、ユーザは、施設内の位置および見る方向を選択する。アプリケーションは、次に、ユーザの視点からその位置の周囲の組み合わされたポイントクラウドにおける各ポイントを表示する。ユーザは、複数の異なる視点から複数のポイントを見るべく、見る位置および方向を移動させ得る。
【００１２】
いくつかのアプリケーションは、組み合わされたポイントクラウドと同じ３次元空間におけるＣＡＤモデルとして表示し得る。ユーザは、次に、ＣＡＤモデルにおける複数の位置とポイントクラウドにおける複数のポイントとの間の複数の距離を測定し得る。ユーザは、また、ポイントクラウドの複数の部分がＣＡＤモデルの複数の部分と交差するかどうかも判断し得る。
【００１３】
組み合わされたポイントクラウドを表示することにより、ユーザは１より多くの視点から複数のポイントを見ることが可能になるものの、このアプローチは、１または複数の欠点を有し得る。
【００１４】
複数の個々のポイントの表示は、計算的に費用が高くなる傾向がある。複数の近い距離でスキャンされた表面の描写において複数の空隙が生じ得ることから、複数の表面を判別することは困難になり得る。
【発明の概要】
【００１５】
本発明の第１の態様に従って、３次元レーザスキャンデータの画像をレンダリングする方法が提供される。方法は、所定のスキャンについてのレーザスキャンデータのセットを球状変位マップとして提供する段階と、球状変位マップをサンプリングすることによってテッセレーションパターンを生成する段階とを備える。方法は、テッセレーションパターンを使用して画像をレンダリングする段階を備える。
【００１６】
所定のスキャンのためのレーザスキャンデータを（複数のスキャンのためのレーザスキャンデータを統合することとは対照的に）ポイントのセットとして保つことによって、およびレーザスキャンデータがグラフィックスシステムによって直接処理され得る変位マップの形で提供され得るという事実をうまく利用することによって、レーザスキャンデータの画像は、効率的におよび／または素早くレンダリングされ得る。これは、複数のスキャンからの複数の画像を組み合わせる場合に特に有用であり得る。なぜならば、各スキャンは独立して処理され得、複数の異なるスキャンからの複数の画像は、共通のバッファにおいて容易に組み合わされ得るからである。これにより、複数の静止画像のみならず、例えばユーザが環境を「通って歩く」ことから、複数の動画の効率的／迅速なレンダリングもまた可能になる。
【００１７】
所定のスキャンのためのレーザスキャンデータのセットを、球状変位マップとして提供する段階は、所定の位置でレーザスキャナによって生成されるレーザスキャンデータのセットを受信する段階と、レーザスキャンデータから所定の方位角および所定の仰角における所定のレーザスキャンポイントについてのレンジの値を、所定の方位角および所定の仰角に対応するテクセル位置における２次元テクスチャ（またはより高い次元のテクスチャ）のそれぞれのテクセルにコピーする段階とを備えてよい。
【００１８】
方法は、テッセレーションパターンを生成するグラフィック処理ユニット（ＧＰＵ）を備えてよい。しかしながら、方法は、テッセレーションパターンを生成する中央演算処理装置（ＣＰＵ）を備えてもよい。
【００１９】
処理装置は、マイクロソフト（登録商標）ＤｉｒｅｃｔＸ（登録商標）１１（またはより最新）またはＯｐｅｎＧＬ４．４（またはより最新の）アプリケーション・プログラミング・インタフェース（ＡＰＩ）を使用して構成されてよい。
【００２０】
方法は、さらに、球状変位マップにおける複数の隣接するポイント間における複数の不連続性を識別する段階と、複数の隣接するポイントをマーク付けする段階とを備えてよい。複数の隣接するポイントをマーク付けする段階は、変位値を、０または−１等、予め定められた数に設定する段階を備えてよい。
【００２１】
方法は、さらに、上記球状変位マップに基づいて法線マップを生成する段階を備えてよい。変位マップおよび法線マップは、１つのテクスチャに組み合わされてよい。１つのテクスチャは、少なくとも４個のチャネルを備えてよい。
【００２２】
法線マップを生成する段階は、球状変位マップにおける各ポイントについての法線を算出する段階と、法線マップに法線を格納する段階とを備えてよい。法線は、第１、第２および第３のベクトル成分値を備えてよい。
【００２３】
方法は、さらに、球状変位マップに基づいて混合テクスチャを生成する段階を備えてよい。混合テクスチャは、複数の混合テクセルのアレイを備えてよく、各混合テクセルは、不連続からの距離に依存する値を有する。
【００２４】
方法は、所定のスキャンについて複数のパッチを有するパッチマップを生成する段階をさらに備えてよい。
【００２５】
パッチマップは、複数の多角形のパッチを備えてよく、各パッチは、３またはそれより多くの頂点を有する。複数のパッチは、同じ形状であってよい。複数のパッチは、同じサイズであってよい。複数のパッチは、長方形であってよい。複数のパッチは長方形である場合、パッチマップは、複数の向かい合った頂点の位置を有してよい。
【００２６】
複数のパッチの位置、形状および／またはサイズは、球状変位マップの複数の不連続に依存してよい。
【００２７】
パッチマップは、各パッチについての相対テッセレーションレベルを含んでよい。方法は、複数の不連続性に基づいて所定のパッチの相対テッセレーションレベルを設定する段階を備えてよい。方法は、所定のパッチの全域にわたる正常変動量に基づいて所定のパッチの相対テッセレーションレベルを設定する段階を備えてよい。
【００２８】
方法は、所定のパッチのビュー位置および／または可視性に基づいて所定のパッチについて絶対テッセレーションレベルを算出する段階を備えてよい。
【００２９】
方法は、さらに、テッセレーションパターンにおける三角形の頂点形成部分が、不連続に隣接しているとしてマーク付けされているかどうかを判断する段階、および頂点が無効であると判断する段階に基づいて、三角形をカリング（ｃｕｌｌｉｎｇ）（または「破棄」）する段階を備えてよい。
【００３０】
方法は、さらに、スキャンについて画素のセットを生成する段階、および深度テストを実行する段階を備えてよい。
【００３１】
方法は、画素の法線に基づいて画素を着色する段階を備えてよい。方法は、画像の対応する部分における強度および／または色に基づいて画素を着色する段階を備えてよい。
【００３２】
方法は、１より多くのレーザスキャンデータのセットを提供する段階を備えてよく、レーザスキャンデータのセットの各々は、それぞれのスキャンに対応する。レーザスキャンデータのセットの各々は、それぞれの球状変位マップとして提供される。方法は、複数の異なるスキャンからレンダリングされた複数の画像を組み合わせる段階を備えてよい。複数の異なるスキャンからの複数のレンダリングされた画像を組み合わせる段階は、深度バッファを使用する段階を備えてよい。
【００３３】
本発明の第２態様に従って、方法を実行するための複数の命令を備えるコンピュータプログラムが提供される。
【００３４】
本発明の第３態様に従って、コンピュータプログラムを格納しているコンピュータ可読媒体または非一時的コンピュータ可読媒体が提供される。
【００３５】
本発明の第４態様に従って、メモリおよび少なくとも１つの処理装置を有するコンピュータシステムが提供される。メモリは、所定のスキャンのためのレーザスキャンデータのセットを球状変位マップとして格納し、少なくとも１つの処理装置は、球状変位マップをサンプリングすることによってテッセレーションパターンを生成するように構成されている。
【００３６】
少なくとも１つの処理装置は、少なくとも１つの図形処理装置を備えてよい。少なくとも１つの処理装置は、少なくとも１つの中央演算処理装置を備えてよい。少なくとも１つの処理装置は、１つの処理装置、例えば１つのグラフィック処理ユニットを備えてよい。
【００３７】
少なくとも１つの処理装置は、マイクロソフト（登録商標）ＤｉｒｅｃｔＸ（登録商標）１１（またはより最新の）アプリケーション・プログラミング・インタフェースを使用して構成可能であってよい。少なくとも１つの処理装置は、ＯｐｅｎＧＬアプリケーション・プログラミング・インタフェースを使用して構成可能であってよい。
【図面の簡単な説明】
【００３８】
本発明の複数の特定の実施形態が、ここで、複数の添付の図面を参照して例を手段として記載されるであろう。
【図１】レーザスキャンデータを取得し処理し、且つ画像をレンダリングするためのシステムの概略ブロック図である。
【図２】レーザスキャンデータを処理し、画像をレンダリングするために使用され得るコンピュータシステムの概略ブロック図である。
【図３】レーザスキャンデータを処理する方法の処理フロー図である。
【図４】球状変位マップの生成を示す。
【図５】２つの表面の間における不連続を示す。
【図６】不連続をマーク付けするための球状変位マップを更新する段階を示す。
【図７】法線マップの生成を示す。
【図８】混合マップの生成を示す。
【図９】複数の規則的な、長方形のパッチの配置を示す。
【図１０】複数の不規則な長方形のパッチの配置を示す。
【図１１】複数の不規則な非長方形のパッチの配置を示す。
【図１２】パッチマップを示す。
【図１３】パッチマップに対する相対テッセレーションデータを追加する段階を示す。
【図１４】グラフィックパイプラインおよびグラフィックメモリの概略ブロック図である。
【図１５】ハルシェーダの出力を示す。
【図１６】パッチについてのテッセレーションレベルを示す。
【図１７】テッセレーションシェーダの出力およびドメインシェーダの入力を示す。
【図１８】変位マップおよび法線マップを含むテクスチャを使用してドメインシェーダの動作を示す。
【図１９】ドメインシェーダからの頂点リストの出力を示す。
【図２０】複数の無効な三角形を選抜除去するジオメトリシェーダの動作を示す。
【図２１】ラスタライザーの動作を示す。
【図２２】画素シェーダの動作を示す。
【図２３】深度テストの処理フロー図である。
【図２４】複数のスキャンの並列処理を示す。
【図２５】複数のスキャンから生成された組み合わされたポイントクラウドを示す。
【図２５ａ】図２５に示されるポイントクラウドの一部の拡大図である。
【図２６】図２５に示されるポイントクラウドの複数の個々のスキャンから生成された、組み合わされテッセレーションされた画像を示す。
【図２６ａ】図２６に示されるテッセレーションされた画像の一部の拡大図である。
【図２６ｂ】図２６に示されるテッセレーションされた画像の他の部分の拡大図である。
【図２７】図２６に示されるテッセレーションを使用して生成された、組み合わされレンダリングされた画像を示す。
【図２８】異なる視点から図２５に示されるポイントクラウドの複数の個々のスキャンから生成された、組み合わされレンダリングされた画像を示す。
【発明を実施するための形態】
【００３９】
システム概要  図１を参照すると、レーザスキャンデータを生成し処理し、画像をレンダリングするためのシステム１が示される。
【００４０】
システム１は、多数の標的表面４を含む環境３を調査するための１または複数の３次元レーザスキャナ２を含む。その、またはそれぞれのレーザスキャナ２は、レーザスキャンデータ６を生成する（本明細書において、単に「スキャンデータ」と称される）レーザスキャニングユニット５、画像データ８を、例えばＪＰＥＧファイルの形式で生成するために使用され得るオプションのカメラ７、およびデータ６、８を格納するための内蔵（ｏｎ−ｂｏａｒｄ）記憶装置９を含む。その、またはそれぞれのレーザスキャナ２は、例えばデータをフォーマットするべく、レーザスキャンデータ６を処理するために使用され得る１または複数のプロセッサ１０およびメモリ１１を含む。別々のコンピュータシステム（図示せず）が、データを処理するために使用され得る。
【００４１】
レーザスキャニングユニット５は、所定の方向（すなわち、所定の水平方向の角度および所定の鉛直方向の角度）においてパルス状のレーザビーム１２を放射することによってポイントのスキャンデータ６の要素を生成し、標的表面４から反射され、レーザスキャナ２へ戻る反射ビーム１３を感知し、レーザビーム１２、１３の飛行時間に基づいて標的表面４へのレンジを決定する。スキャンデータ６のセットは、スキャナ２の周囲にポイントのセットを構築するように、レーザビーム１２を水平方向および鉛直方向にスキャンすることによって取得され得る。スキャンデータ６におけるそれぞれのポイントは、デカルト座標のセット、すなわちそれぞれのポイント（ｘ，ｙ，ｚ）において表現される形で提供される。データ６のセットにおける複数のポイントは、方位角および仰角によって順序付けられる。
【００４２】
スキャンデータ６、およびオプションとして画像データ８は、テクスチャ１８、１９、２０、２１のセット１７、単一のテクスチャ２２へと組み合わされるいくつかのテクスチャ、およびそれぞれのスキャンのためのパッチマップ２３を生成するスキャンデータ処理モジュール１６を含むコンピュータシステム１５に供給される。コンピュータシステム１５は、また、データを格納するための１または複数のハードドライブの形で記憶装置２４を含む。１または複数のハードドライブは、複数のハードディスクドライブ、ソリッドステートドライブ、光学ドライブまたは他の形式の適した記憶装置であってよい。
【００４３】
後により詳細に説明されるように、テクスチャ１７のセットは、（本明細書において、深度マップともまた称される）球状変位マップ１８およびスキャンデータ６から得られた法線マップ１９を含む。後により詳細にまた説明されるように、変位マップ１８および法線マップ１９は、単一の、４チャネルテクスチャ２２（本明細書において「組み合わされたテクスチャ」と称される）で組み合わされる。
【００４４】
テクスチャ１７のセットは、混合マップ２０を含み得る。テクスチャ１７のセットは、画像データ８から取得されたカラーマップ２１を含み得る。
【００４５】
コンピュータシステム１５は、ユーザ入力デバイス２５（マウスおよび／またはキーボード等）、レンダリングシステム２６およびユーザ入力デバイス２５を介してユーザによって供給される視点２９からの画像２８を表示するためのディスプレイ２７を含む。レンダリングシステム２６は、テクスチャ１７のセットおよび１または複数の異なるスキャンから取得されたパッチマップ２３を使用して複数の三角形に分割された３次元表面を生成し、任意の視点から複数の表面をリアルタイムで１または複数のスキャンから取得された複数の表面を画像２８において組み合わせてレンダリングする。
【００４６】
スキャンデータ処理モジュール１６およびレンダリングシステム２６は、複数の異なるコンピュータシステムで実装されてよい。例えば、スキャンデータ処理モジュール１６は、レーザスキャナ２によって全体または部分的に実装されてよい。代替的に、レーザスキャナ２は、変位マップ１８を生成してよく、第１のコンピュータシステムは、１または複数の他のテクスチャ１９、２０、２１およびパッチマップ２３、あるいはパッチマップ２３のみを生成してよく、１または複数のテクスチャ１８、１９、２０、２１およびパッチマップ２３を、レンダリングシステム２６を実装する第２のコンピュータシステムに供給してよい。
【００４７】
また、図２も参照すると、コンピュータシステム１５は、より詳細に示される。 
【００４８】
コンピュータシステム１５は、それぞれのメモリキャッシュ（図示せず）を有する１または複数の中央演算処理装置（ＣＰＵ）３１、システムメモリ３２、グラフィック処理ユニット（ＧＰＵ）３４および（「ビデオＲＡＭ」と称されてよい）グラフィックメモリ３５を含む、例えばグラフィックカードの形でグラフィックモジュール３３、およびバス３７によって動作可能に接続された入出力（Ｉ／Ｏ）インタフェース３６を含む。適しているグラフィックモジュール３３の例は、１ＧＢのビデオＲＡＭを持つＮＶＩＤＩＡ（登録商標）ＧｅＦｏｒｃｅ４６０ＧＰＵである。
【００４９】
Ｉ／Ｏインタフェース３６は、その、またはそれぞれのスキャナ２からスキャンデータ６を受信するためのバスおよび／または１または複数のネットワークインタフェース３８（ＵＳＢインタフェースまたはＷＬＡＮインタフェース等）に動作可能に接続されている。Ｉ／Ｏインタフェース３６は、また、ユーザ入力デバイス２５および記憶装置２４に、例えば１または複数のハードディスクドライブおよび／またはソリッドステートドライブの形で動作可能なように接続されている。着脱可能記憶装置等のいくつかの周辺機器および他の複数のコンピュータ構成要素は図示されていない。コンピュータシステム１５は、図２に示されるものとは異なる構成を有してよい。
【００５０】
スキャンデータ処理モジュール１６は、ソフトウェアにおいて実装される。スキャンデータ処理モジュール１６を実施するためのコンピュータコード３９は、記憶装置２４において保持され、１または複数のＣＰＵ３１による実行のためのメモリ３２へとロードされる。
【００５１】
レンダリングシステム２６は、好ましくは、ＧＰＵの複数の向上されたグラフィック処理能力、特にテッセレーションをうまく利用するようにＧＰＵを使用して実装される。しかしながら、レンダリングシステム２６は、１または複数のＣＰＵを使用して実装され得る。
【００５２】
後により詳細に説明されるように、レンダリングシステム２６は、プログラマブルであり、一定の機能のシェーダ６１、６２、６３、６４、６５、６７、６８およびラスタライザー６６を含む複数のモジュール６１、６２、６３、６４、６５、６６、６７、６８（図１４）を含むグラフィックパイプライン６０（図１４）を実装する。
【００５３】
スキャン処理  図１、図２および図３を参照し、スキャンデータ処理モジュール１６の動作が、ここでより詳細に記載されるであろう。
【００５４】
モジュール１６は、バスまたはネットワーク（図示せず）、またはポータブル記憶装置（図示せず）を介してスキャナ２から、および／または記憶装置２４から、スキャンについてのスキャンデータ６のセットをロードする（段階Ｓ１）。スキャンデータ６は、デカルト座標にあることから、モジュール１６は、スキャンデータ６を球状変位マップ１８として変換し、格納する（段階Ｓ２）。
【００５５】
また、図４も参照すると、球座標系４１が示されている。球座標系４１は、原点４２（すなわち、スキャナ２における基準点）および水平および鉛直方向の基準軸４３、４４を含む。図４に示されるように、スキャナ２は、原点４２と標的表面４上（図１）のポイント４５との間の距離（または「レンジ」）ｄｉ，ｊをキャプチャする。
【００５６】
スキャンについてのスキャンデータ６は、テクスチャ２２にコピーされる。テクスチャ２２は、複数のテクスチャ要素（または「テクセル」）４６の２次元アレイを含む（ｕ，ｖ）マップの形を取る。それぞれのテクセル４６は、第１、第２、第３および第４の要素４６１、４６２、４６３、４６４を有する。
【００５７】
先に説明されたように、テクスチャ２２は、４個のチャネルを有する。第１のチャネルは、変位マップ１８を格納し、第２、第３および第４チャネルは、法線マップ１９を格納する。
【００５８】
テクスチャ２２の水平軸ｕは、レーザスキャナ２の水平方向の角度（または「方位角」）に比例する。テクスチャの鉛直軸ｖは、レーザスキャナ２の鉛直方向の角度（「仰角」）に比例する。それぞれのテクセル４６は、スキャンにおけるポイントのレンジの値をその（ｕ，ｖ）位置に対応する方位角および仰角で深度、ｄｉ，ｊとして格納する。よって、レンジの複数の値は、テクスチャ２２に格納される場合、レーザスキャンの球状変位マップ１８を提供する。
【００５９】
ＲＧＢ成分値の形としての画像データ８は、同様のやり方でカラーマップ２１にコピーされ得る。
【００６０】
図１、図２、図３、図５および図６を参照すると、スキャンデータ処理モジュール１６は、特定された閾値ΔｄＴＨを超える深度の差Δｄを持つ複数の隣接するテクセル４６を探すことによって変位マップ１８において何らかの不連続があるかどうかを判断するべく複数のテクセル４６を検査し、もし不連続がある場合、その位置がテッセレーションされないように不連続をマーク付けする（段階Ｓ３）。不連続は、０または−１等、予め定められた数を使用してマーク付けされる。
【００６１】
変位マップ１８は、球状であって、レーザスキャナ２の視点から取られる。よって、球状変位マップ１８における複数の隣接するテクセル４６間の不連続は、レーザスキャナ２が１つの表面４８１から他の表面４８２まで移動した領域または線４７を表す。従って、このエリアでは表面は描かれるべきでない。
【００６２】
例えば、図５に示されるように、２つの隣接するスキャンポイントが、縁４７の何れかの側に収まる。図６に示されるように、対応するテクセル４６は、例えば、それぞれ深度値８５５および２２を有する。閾値ΔｄＴＨは、例えば３００であってよい。よって、深度の差Δｄ＝８５５‐２２＝８３３およびΔｄ>ΔｄＴＨであるから、モジュール１６は両方の値をゼロに等しく設定することによって不連続をマーク付けする。
【００６３】
ｕ方向および／またはｖ方向における複数の隣接するテクセル４６が比較され得る。
【００６４】
図１、図２、図３および図７を参照すると、スキャンデータ処理モジュール１６は、変位マップ１８から法線マップ１９を生成し、法線マップ１９を格納する（段階Ｓ４）。
【００６５】
変位マップ１８における各テクセル４６について、モジュール１６は、テクセル４６によって表される球座標からデカルト座標を算出する。モジュールは、デカルト座標において、テクセル４６に隣接している、複数の水平方向の隣接するテクセル４６間の第１ベクトルと複数の鉛直方向の隣接するテクセル４６間の第２ベクトルとの外積を取ることによって、所定のテクセル４６の法線４９（図７で網掛けされて示される）を算出する。モジュール１６は、不連続にわたって法線４９を算出しない。
【００６６】
モジュール１６は、法線４９のｘ、ｙおよびｚ成分（ｎｘ，ｎｙ，ｎｚ）を第２、第３および第４の要素４６２、４６３、４６４におけるテクセル４６に格納する。
【００６７】
図１、図２、図３および図８を参照すると、スキャンデータ処理モジュール１６は、オプションとして、不連続の近くの表面の縁を滑らかにするために使用される情報を含む混合テクスチャ２０を生成し得る（段階Ｓ５）。
【００６８】
混合テクスチャ２０における各テクセル５０は、０と１との間の範囲に存在する混合値ｓを含む。
【００６９】
スキャンデータ処理モジュール１６は、不連続に沿った複数のポイントに対応する変位マップ１８において複数のテクセル４６を識別し、混合テクスチャ２０における複数の対応するテクセル５０が０の混合値を有する（すなわち、ｕおよびｖと同じ値を有する）ように設定する。スキャンデータ処理モジュール１６は、混合テクスチャ２０、すなわち徐々に増える複数の値を通って徐々に伝播する複数の混合値をさらに生成する。例えば、図８に示されるように、０．５という値が、不連続に最も近い隣りのテクセル５０に与えられ、０．８という値が、２番目に最も近い隣りのテクセル５０に与えられ、１という値が３番目に最も近い隣りのテクセル５０に与えられる。
【００７０】
図１、図２、図３および図９を参照すると、スキャンデータ処理モジュール１６は、スキャンを複数のパッチ５１へと分け、パッチマップ２３を格納する（段階Ｓ６）。
【００７１】
各パッチ５１は、（ｕ，ｖ）座標において複数のテクスチャのスキャンの領域を定義する。各パッチは、頂点５２のセットを有する。
【００７２】
複数のパッチ５１は、任意の形状であり得、スキャンにおいて規則的または不規則に分配され得る。複数のパッチ５１の形状および位置は、予め定められているか、または複数の不連続の複数の位置または複数の法線の変動量等、スキャンの任意の態様に基づいてよい。
【００７３】
例えば、図９は、全てが同じ形状およびサイズである複数の長方形のパッチ５１の配置を示す。
【００７４】
他の例において、図１０は、複数の不連続４７の位置を考慮する異なるサイズの複数の長方形のパッチ５１の配置を示す。例えば、図１０に示されるように、複数の一定サイズのパッチ５１を使用する代わりに、スキャンデータ処理モジュール１６は、不連続がパッチ５１内に見つかるかどうかに従って、より大きいパッチ５１をより小さいパッチ５１１、５１２、５１３、５１４、５１５に分けてよい。
【００７５】
さらに他の例において、図１１は、スキャンデータ処理モジュール１６が、分岐する不連続４７を考慮する複数の縁を有する（例えば、それと一直線になっている）非長方形のパッチ５１６、５１７、５１８、５１９を生成する配置を示す。明確にするため、パッチ５１６、５１７、５１８、５１９の複数の外側の縁が、先を切断されて示され、それにより、それらは直線で鉛直のまたは水平の複数の縁として見える。しかしながら、複数のパッチは、先を切断される必要はなく、例えば図１１のパッチ５１６の鎖で示されるような不規則な輪郭を有し得ることは理解されるであろう。
【００７６】
図１２をまた参照すると、パッチ５１のそれぞれについて、要素５４のセットは、各パッチ５１のパッチマップ２３に格納され、各要素５４は、パッチ頂点５２の位置を有する。長方形のパッチ５１（図９に示されるもの等）の場合、パッチ５１は、２つの頂点５２のみ、例えば左上および右下の頂点５２を使用して特定され得る。しかしながら、特に複数の不規則な形状のパッチについては、２より多くの要素５４があってよい。
【００７７】
図１、図２、図３および図１３を参照すると、モジュール１６は、各パッチ５１の相対テッセレーションレベル５５を算出する（段階Ｓ７）。
【００７８】
相対テッセレーションレベル５５は、パッチ５１が他の複数のパッチ５１に対してどの程度テッセレーションされるかを表す。絶対テッセレーションレベルは、ビューに依存するファクタまたは他の複数のファクタが適用された後、後に算出される。相対テッセレーションレベル５５は、予め定められているか、または複数の不連続の位置もしくは複数の法線の変動量等、パッチの任意の態様に基づいてよい。
【００７９】
変位マップ１８、法線マップ１９、混合テクスチャ２０およびパッチマップ２３は、各スキャンにつき一回生成され得、後の使用のために格納され得る。
【００８０】
レンダリング  図１、図２および図１４を参照すると、スキャンデータ処理モジュール１６は、各スキャンのためのテクスチャ１８、１９、２０およびパッチマップ２３をレンダリングシステム２６にロードする。
【００８１】
レンダリングシステム２６は、パッチマップ２３における情報を使用して、スキャンの１または複数のテッセレーションされた表面を生成するために使用される。テッセレーションをサポートするレンダリングシステムが使用され得る。好ましくは、毎秒１億個の三角形またはそれより速い速度で処理するレンダリングシステムが使用される。レンダリングシステムは、ＣＰＵまたはＧＰＵにおいて実行され得る。
【００８２】
レンダリングシステム２６は、ＧＰＵ３４で実行されるマイクロソフト（登録商標）ＤｉｒｅｃｔＸ１１（登録商標）を利用する。しかしながら、ＯｐｅｎＧＬ４．ｘ等の他の複数のグラフィックスシステムが使用され得る。
【００８３】
テクスチャ１８、１９、２０およびパッチマップ２３は、レンダリングシステム２６によって効率的に処理され得る形で格納される。
【００８４】
テクスチャ１８、１９、２０は、複数の２次元テクスチャ資源として格納され、パッチマップ２３は、一制御ポイントのパッチリストのトポロジーを持つ頂点バッファとして格納される。先に説明されたように、変位および法線マップ１８、１９は、４個のチャネルを持つ組み合わされたテクスチャ２２に組み合わされる。
【００８５】
テクスチャ１８、１９、２０および頂点バッファ２３、すなわちパッチマップ２３は、ＧＰＵ３４に送信される。
【００８６】
図１４を参照すると、グラフィックスシステム用のグラフィックパイプライン６０が示されている。グラフィックパイプライン６０は、頂点シェーダ６１、ハルシェーダ６２、テッセレーションシェーダ６３（本明細書においては、また、単に「テッセレータ」とも称される）、ドメインシェーダ６４、ジオメトリシェーダ６５、ラスタライザー６６、画素シェーダ６７および出力合併ステージ６８を含み、出力合併ステージ６８は、数ある中で、深度バッファ６９（また、「ｚバッファ」とも称される）と併せて深度テストを実行する。
【００８７】
ＯｐｅｎＧＬにおいて、ハルシェーダは、「テッセレーション制御シェーダ」と称され、テッセレーションシェーダは「プリミティブジェネレータ」と称され、ドメインシェーダは「テッセレーション評価シェーダ」と称され、画素シェーダは、「断片シェーダ」と称される。
【００８８】
図１４および図１５を参照すると、頂点バッファ２３における各パッチ５１は、ハルシェーダ６２によって処理される。ハルシェーダ６２は、各パッチ５１の絶対テッセレーションレベル７０を算出する。テッセレーションレベル７０は、予め定められているか、または視点２９からのパッチ５１の距離またはその可視性等、１または複数のファクタに基づいてよい。パッチ５１の相対テッセレーションレベル５５が、考慮されてよい。
【００８９】
この例において、各パッチ５１の絶対テッセレーションレベル７０は、視点２８および相対テッセレーションレベル５５に基づいて算出される。ハルシェーダ６２は、また、隣の複数のパッチ５１のテッセレーションレベルに一致するように、パッチ５１の縁の周囲でテッセレーションレベルを調節する。これは、複数のパッチ５１にわたって連続的なテッセレーションを生成する。
【００９０】
図１６および図１７もまた参照すると、テッセレーションシェーダ６３は、各パッチ５１のそれぞれのテッセレーションパターン７１を生成する一定の機能のモジュールである。
【００９１】
テッセレーションシェーダ６３は、ハルシェーダ６２によって算出される絶対テッセレーションレベル７０に基づいてテッセレーションパターン７１（本明細書においては「テッセレーションされたパッチ」と称される）を生成する。テッセレーションパターン７１は、複数の三角形７２から成る。テッセレーションパターン７１における複数のポイント７３は、組み合わされたテクスチャ２２内にそれらの（ｕ，ｖ）座標を含む。
【００９２】
図１７に示されるように、テッセレーションシェーダ６３は、各パッチ５１を構成する複数の三角形７２の複数のポイント７３の座標を載せるポイントリストの形でテッセレーションパターン７１を出力する。それぞれの（ｕ，ｖ）ポイント７３は、一度に一個ずつドメインシェーダ６４に送信される。
【００９３】
図１８および図１９をまた参照すると、それぞれのパッチ５１におけるそれぞれのポイント７３は、ドメインシェーダ６４によって処理される。
【００９４】
ドメインシェーダ６４は、組み合わされた深度／法線テクスチャ２２をサンプリングし、複数のテッセレーションされたポイントを３次元空間へと投影する。
【００９５】
ドメインシェーダ６４は、パッチ５１においてテッセレーションパターン７１における各ポイント７３の位置を算出する。
【００９６】
ドメインシェーダ６４は、深度および法線の値を取り出すべく、ポイント７３の（ｕ，ｖ）座標における組み合わされた深度／法線テクスチャ２２をサンプリングする。サンプルが不連続の隣にあるテクセル４６を含む場合、そのポイントは無効とマーク付けされる。
【００９７】
ドメインシェーダ６４は、パッチ５１における情報を使用して（ｕ，ｖ）座標から方位角および仰角を算出する。ドメインシェーダ６４は、次に、球座標（すなわち方位角、仰角、深度）を、直接または（図１８に示されるように）段階的の何れかでビュー座標７４へと変換する。すなわち、それは、球座標を、スキャンの座標系におけるデカルト位置７５へと変換し、次に、その位置および法線を、世界座標へと転換し、そして次にビュー座標７４へと転換する。座標７４は、頂点リスト７６の形で出力される。
【００９８】
ドメインシェーダ６４は、（球状）変位マップ１９で特定された深度によって球状表面上の複数のポイントを効果的にずらす。
【００９９】
図２０を参照すると、テッセレーションされたパッチ７１におけるそれぞれの三角形７２は、次に、ジオメトリシェーダ６５によって処理される。ジオメトリシェーダ６５は、複数の不連続において複数の三角形７２をカリングする。ジオメトリシェーダ６５は、三角形７２が任意の無効の頂点７７を含むかどうかを判断する。頂点７４は、不連続の隣にある場合、無効である。無効な頂点７７が存在する場合、ジオメトリシェーダ６５は、三角形７２を破棄、すなわち無効な三角形７８を破棄する。ジオメトリシェーダ６５は、また、三角形７２がレーザスキャナ位置に対して過度に傾斜した角度にあるかどうかを判断する。そうである場合、三角形７２もまた破棄される。ジオメトリシェーダ６５は、更新された頂点リスト７９を出力する。
【０１００】
図２１を参照すると、ラスタライザー６６は、更新された頂点リスト７９におけるそれぞれの三角形７２を、複数の画素８１を有するラスタデータ８０へと変換する。各画素８１は、深度８２の値を含む。
【０１０１】
それぞれのラスタライズされた三角形７２は、次に、画素シェーダ６７によって処理される。
【０１０２】
図２２を参照すると、画素シェーダ６７は、画素８１が不連続４７（図５）に過度に近いかどうかを判断するべく、混合テクスチャ２０をサンプリングする。画素８１が不連続に過度に近い場合、それは破棄される。画素シェーダ６７は、画素８１で法線４９（図７）を取り出すべく、組み合わされた深度／法線テクスチャ２２をサンプリングする。画素シェーダ６７は、世界空間において、法線４９
（図７）をベクトル（図示せず）へと転換する。画素シェーダ６７は、画素８１の色８３を算出し、各画素８１の深度８２および色８３を含むためのラスタデータ８４を出力する。
【０１０３】
図１４および図２３を参照すると、複数のスキャンが１つの画像へとレンダリングされる場合、スキャンデータが深度バッファ６９を使用して組み合わされ得る。
【０１０４】
画素シェーダ６７は、所定の位置およびオフセットで深度８２をサンプリングすることによって深度の品質を測定し得る。画素シェーダ６７は、同じスクリーン座標ではより高い品質の複数のサンプルを支持（ｆａｖｏｒ）し得る。画素シェーダ６７は、サンプルの品質を判断するべく、混合テクスチャ２０および／または組み合わされた深度／法線テクスチャ２２における情報を使用し得る。
【０１０５】
出力合併ステージ６８は、数ある中でも深度テストを実行する。
【０１０６】
また、図２４も参照すると、各画素８１は、深度バッファ６９における対応する画素に比較される（段階Ｓ１１,Ｓ１２およびＳ１３）。入ってくる画素８１が、深度バッファ６９に格納されている対応する画素より小さい値の深度を有する場合、その入ってくる画素８１は、バッファ６９に書き込まれる（段階Ｓ１４）。入ってくる画素８１が、深度バッファ６９に格納されている対応する画素より大きい値の深度を有する場合、その入ってくる画素８１は破棄される（段階Ｓ１５）。
【０１０７】
数回のスキャンから生成された画素データは、同じ深度バッファ６９に書き込まれ得、よって、数回のスキャンからのデータを有する画像が形成され得る。
【０１０８】
図２５から図２８を参照すると、レーザスキャンデータを処理し、画像をレンダリングする方法が、処理中の複数の異なるステージにおける一式のスキャンについて示される。
【０１０９】
図２５は、複数のスキャンから生成されたポイントクラウドの画像９１である。図２５ａは、図２５において示される画像９１の部分９１ａの拡大されたビューである。
【０１１０】
画像９１は、数ある中で、フロア９２、天井９３、貯蔵タンク９４、３つの反応容器の列９５、様々なパイプ９６、４つの制御パネル９７の列、天井９３から吊り下がっているケーブルトレイ９８、ライティングユニット９９（または「照明」）および４つのパレット型液体貯蔵容器の列１００を含むプロセスプラントの内側を示す。
【０１１１】
図２５ａは、中央反応容器９５、パイプ９６および対応する制御パネル９７のより詳細な図である。画像９１、９１ａは、ポイントクラウドの複数のポイント４５から形成される。この場合、各ポイント４５は、スキャンの時にキャプチャされたそれぞれの色を有する。
【０１１２】
図２５ａに示されるように、制御パネル９７等の複数の比較的遠くの物体は、反応容器９５等、複数の比較的近い物体がそれの前にあり、遠くの物体を不明瞭にするはずであるにもかかわらず、可視である。この効果は、画像が拡大される場合、より顕著になる。
【０１１３】
図２６は、図２５に示されるポイントクラウドの複数の個々のスキャンから生成された、組み合わされテッセレーションされた画像１０１を示す。図２６ａおよび図２６ｂは、図２６に示される画像１１１の部分１１１ａ、１１１ｂの拡大図である。
【０１１４】
図２５ａおよび図２６ｂを参照すると、ポイントクラウドからの複数のポイント４５は、複数の三角形７２から成るテッセレーションパターン７１を形成するために使用される。
【０１１５】
図２６ｂは、複数の異なるサイズを有する、言い換えれば複数の異なるテッセレーションレベルを有する複数の三角形７２を示す。
【０１１６】
反応容器９５等、隠されるべきである複数の物体は、複数の三角形７２がラスタライズされておらず、よって塗りつぶされなかったことから、未だに透明である。
【０１１７】
図２７は、テッセレーションを使用して生成された、組み合わされレンダリングされた画像２８、１１１を示す。
【０１１８】
図２７に示されるように、複数の制御パネル９７等、複数の比較的遠くの物体は、ここで、複数の反応容器９５等、複数の比較的近い物体によってはっきり見えなくなる。
【０１１９】
先に説明されたように、レンダリングシステム２６（図１）は、複数のスキャンを使用してリアルタイムで複数の画像をレンダリングし得る。さらに、システム２６（図１）により、位置は変更されることが可能になり、複数の異なる位置から見られる複数のテッセレーションされた画像を生成する。位置は、増加的または連続的に変更され得、ユーザが調査された環境を介して「歩く」または「飛ぶ」のを可能にする。
【０１２０】
図２８は、図２５に示される同じポイントクラウドからではあるが、異なる視点から生成された、別の組み合わされレンダリングされた画像２８、１１１'を示す。
【０１２１】
図２８に示されるように、画像１１１'は、複数の制御パネル９７および複数の反応容器９５等の複数の同じ物体を示すが、別の視点から示す。図２７に示される画像１１１は、図２８に示される複数のドア１１２の前の視点から取られている。
【０１２２】
図２８は、スキャンを実行する場合のスキャナ２（図１）の複数の位置を示す。それぞれの暗い円形領域１１３は、スキャナ２が複数のポイントを記録しない、スキャナ２の下のエリアに対応する。
【０１２３】
ポイントクラウド画像９１（図２５）およびレンダリングされた画像１１１'（図２８）の比較は、複数のスキャンから生成されたポイントクラウドの画像９１を表示することに関連する視覚アーティファクトを示す。レンダリングされた画像１１１'は、複数の制御パネル９７の前面を示す。それぞれの前面は、製造業者ラベル１１３および警告サイン１１４を持つ。しかしながら、これらのラベル１１３およびサイン１１４は、それらが実世界においておそらく可視でない場合、ポイントクラウド画像９１において可視である。
【０１２４】
複数の個々のスキャンについてのスキャンデータを１つの、スキャンデータのより大きいセットに統合しないことによって、システムは、スキャンデータが収集される順番をうまく利用し得る。それぞれのスキャンデータのセットは、球状変位マップとして取り扱われ得、複数の計算的に効率的な技術を使用してテッセレーションパターンを生成するべくサンプリングされ得る。ラスタライズ等、さらなる複数のグラフィック処理が実行され得、そのときになって初めて複数の異なるスキャンからの複数の画像が組み合わされる。よって、システムにより、スキャンデータの画像は、特にＧＰＵの複数のグラフィック能力が使用される場合に、効率的および／または素早くレンダリングされることが可能になる。
【０１２５】
様々な変更が以上に記載された複数の実施形態に対して作成されてもよいことは理解されるであろう。そのような複数の変更は、複数のレーザスキャンシステムおよび／またはグラフィック処理システムおよびこれらの構成要素部分の設計、製造、および使用において既に公知であり、本明細書において既に記載された複数の特徴の代わりに、またはそれらに加えて使用されてよい複数の同等な他の特徴を伴ってよい。１つの実施形態の複数の特徴は、他の実施形態の複数の特徴によって置き換えられるか、または補足されてよい。
【０１２６】
特許請求の範囲は、本出願において特定の複数の特徴の組み合わせに対して明確に述べられたが、本発明の開示の範囲は、また、本明細書で開示された任意の新規の特徴または任意の新規の特徴の組み合わせを明示的または暗黙的の何れかのやり方で含み、またはそれらの任意の一般化を、それが任意の請求項において現時点で請求されているものと同じ発明に関するか否かを問わず、および本発明がするようにそれが同じ技術的課題のいずれかまたは全てを軽減するか否かを問わず、含むことは理解されるべきである。これにより出願人らは、新しい特許請求の範囲が、本出願またはそこから導出される任意のさらなる出願の遂行中に、複数のそのような特徴および／またはそのような特徴の複数の組み合わせに対して明確に述べられてよいことを告示する。
【図１】
0006260924.tif 000002
【図２】
0006260924.tif 000003
【図３】
0006260924.tif 000004
【図４】
0006260924.tif 000005
【図５】
0006260924.tif 000006
【図６】
0006260924.tif 000007
【図７】
0006260924.tif 000008
【図８】
0006260924.tif 000009
【図９】
0006260924.tif 000010
【図１０】
0006260924.tif 000011
【図１１】
0006260924.tif 000012
【図１２】
0006260924.tif 000013
【図１３】
0006260924.tif 000014
【図１４】
0006260924.tif 000015
【図１５】
0006260924.tif 000016
【図１６】
0006260924.tif 000017
【図１７】
0006260924.tif 000018
【図１８】
0006260924.tif 000019
【図１９】
0006260924.tif 000020
【図２０】
0006260924.tif 000021
【図２１】
0006260924.tif 000022
【図２２】
0006260924.tif 000023
【図２３】
0006260924.tif 000024
【図２４】
0006260924.tif 000025
【図２５】
0006260924.tif 000026
【図２５ａ】
0006260924.tif 000027
【図２６】
0006260924.tif 000028
【図２６ａ】
0006260924.tif 000029
【図２６ｂ】
0006260924.tif 000030
【図２７】
0006260924.tif 000031
【図２８】
0006260924.tif 000032