(57)【要約】コーン階層および境界（たとえば外皮）階層の二重検索に基づいて可視オブジェクト判定を実行するためのシステムおよび方法。ホスト・プロセッサ上で稼動するビジュアライゼーション・ソフトウェアが、再帰細分化によって構成されるコーンの階層を有する空間を表現し、オブジェクトのクラスタを再帰的にグループ化することによって、オブジェクトの所与の集合から境界外皮の階層を生成する。外皮階層の外皮ノードは、クラスタのメンバシップを反映する。各外皮ノードには、対応するクラスタまたはオブジェクトの境界外皮の特徴を表すパラメータが格納される。ビジュアライゼーション・ソフトウェアは、ルートコーンおよびルート外皮から始めて、コーン階層および外皮階層を検索する。各リーフ・コーンには、それに最も近い既知のオブジェクトへの距離を表す可視性距離値が割り当てられる。非リーフ・コーンの可視性距離値には、その子の可視性距離値の最大値がセットされる。所与のコーン／外皮対を探索する前に、コーンと外皮の間のコーンによって制限された最小距離を測定し、コーンの可視性距離値と比較する。前者が後者より小さい時に限って、外皮に対してコーンを検索する。検索条件が満足されると仮定すると、所与の外皮のサブ外皮が、コーン（またはそのサブコーン）からのそのコーン−外皮の距離の昇順で、所与のコーン（またはそのサブコーン）に対してもう一度条件的に探索される。２つの木の再帰検索が完了した時に、可視オブジェクトが、各リーフ・コーンに割り当てられている。
2004513403.tif 000002
【特許請求の範囲】
【請求項１】
担体媒体上で実施されたコンピュータ・ソフトウェア・プログラムであって、上記プログラムが、表示装置上に可視オブジェクトを表示する方法を実行するように構成された複数の命令を含み、上記方法が、
オブジェクトの集合にアクセスするステップと、
上記オブジェクトの集合から境界階層を構成するステップと、
コーン階層を構成するステップと、
上記コーン階層のコーンのサブセットの最も近いオブジェクトを判定するために、上記コーン階層および上記境界階層を検索するステップと、
上記コーン階層のコーンの上記サブセットの上記最も近いオブジェクトを表示するステップと
を含む、コンピュータ・ソフトウェア・プログラム。
【請求項２】
上記担体媒体が、伝送媒体である請求項１に記載のコンピュータ・ソフトウェア・プログラム
【請求項３】
上記担体媒体が、コンピュータ可読媒体である請求項１に記載のコンピュータ・ソフトウェア・プログラム
【請求項４】
表示装置上に可視オブジェクトを表示する方法であって、
オブジェクトの集合にアクセスするステップと、
上記オブジェクトの集合から境界階層を構成するステップと、
コーン階層を構成するステップと、
上記コーン階層のコーンのサブセットの最も近いオブジェクトを判定するために、上記コーン階層および上記境界階層を検索するステップと、
上記コーン階層のコーンの上記サブセットの上記最も近いオブジェクトを表示するステップと
を含む方法。
【請求項５】
前記コーンのサブセットが、上記コーン階層のリーフ・コーンを含む請求項２、請求項３、または請求項４に記載の方法。
【請求項６】
上記コーン階層の第１コーンおよび上記境界階層の第１境界について、前記検索するステップが、
上記第１コーンと上記第１境界との間の離隔の第１測定値を判定するステップと、
上記第１測定値が、上記第１コーンに関連する測定値に関して不等式条件を満足するかどうかを判定するステップと、
上記第１測定値が上記第１コーンに関連する上記測定値に関して上記不等式条件を満足することの肯定の判定に応答して、上記第１コーンに関して上記第１境界を検索するステップと
を含む請求項２、請求項３、または請求項４に記載の方法。
【請求項７】
前記境界階層を構成するステップが、
クラスタを形成するために前記オブジェクトをクラスタ化するステップと、
対応する境界を用いて各オブジェクトおよび各クラスタの境界を定めるステップと、
各オブジェクトおよび各クラスタについて、上記境界階層内でノードを割り振るステップと、
各ノードにパラメータを関連付けるステップであって、上記ノードに関連する上記パラメータが、上記対応する境界を記述する、関連付けるステップと
ノード関係がクラスタ・メンバシップを表すように上記ノードを編成するステップと
を含む請求項６に記載の方法。
【請求項８】
上記第１コーンと上記第１境界との間の離隔の上記第１測定の前記判定が、上記第１コーンの頂点と上記第１コーンおよび上記第１境界の共通部分の点との間の離隔距離の増加関数を最小化する計算を実行するステップを含み、上記第１測定値が上記不等式条件を満足するかどうかの前記判定が、上記第１測定値が上記第１コーンに関連する測定値より小さいかどうかを判定するステップを含む請求項６に記載の方法。
【請求項９】
上記第１コーンと上記第１境界との間の離隔の第１測定の前記判定が、上記第１コーンの頂点と上記第１コーンおよび上記第１境界の共通部分の点との間の離隔距離の減少関数を最大化する計算を実行するステップを含み、上記第１測定値が上記不等式条件を満足するかどうかの前記判定が、上記第１測定値が上記第１コーンに関連する測定値より大きいかどうかを判定するステップを含む請求項６に記載の方法。
【請求項１０】
上記第１コーンと上記第１境界との間の離隔の上記第１測定値の前記判定が、上記第１コーンの頂点と上記第１コーンおよび上記第１境界の共通部分の点との間の極大距離を判定するために、上記第１コーンを定義する制約の第１組と上記第１境界を定義する制約の第２組とを使用して非線形計画問題を解くステップを含む請求項６に記載の方法。
【請求項１１】
前記コーン階層が、初期コーンを細分するステップによって生成される請求項６に記載の方法。
【請求項１２】
上記第１コーンに関する上記第１境界の前記検索するステップが、
前記第１コーンが上記コーン階層のリーフであり、前記第１境界が上記境界階層のリーフであるか否かを判定するステップと、
上記第１コーンに関連する上記測定値に、上記第１境界と上記第１コーンとの間の離隔の上記第１測定値をセットするステップと、
上記第１コーンに関連する可視オブジェクト属性に、上記第１境界をセットするステップと
を含み、上記第１コーンに関連する上記測定値の前記セットおよび上記第１コーンに関連する上記可視オブジェクト属性の前記セットが、上記第１コーンが上記コーン階層のリーフであり、上記第１境界が上記外皮階層のリーフであることの肯定の判定に応答して実行される請求項６に記載の方法。
【請求項１３】
上記第１コーンに関する上記第１境界の前記検索するステップが、
前記第１コーンが上記コーン階層のリーフであり、前記第１境界が上記境界階層のリーフでないかどうかを判定するステップと、
前記第１コーンが上記コーン階層のリーフであり、前記第１境界が上記境界階層のリーフでないことの肯定の判定に応答して、前記第１コーンに関して前記第１境界のサブ境界を条件的に探索するステップと
を含む請求項６に記載の方法。
【請求項１４】
前記第１境界のサブ境界の前記条件的探索が、
前記第１コーンに関する上記第１境界の上記サブ境界のそれぞれのコーン−境界の離隔値を計算するステップと、
上記第１コーンからの離隔の昇順で、前記第１コーンに関して前記第１境界の前記サブ境界を条件的に検索するステップと
を含む請求項１３に記載の方法。
【請求項１５】
前記第１境界の前記サブ境界の前記条件的検索が、
前記サブ境界のうちの第１サブ境界の上記コーン−境界の離隔値が、上記第１コーンに関連する上記測定値に関して上記不等式条件を満足するかどうかを判定するステップと、
上記第１サブ境界の上記コーン−境界の離隔値が、上記第１コーンに関連する上記測定値に関して上記不等式条件を満足することの肯定の判定に応答して、前記第１コーンに関して前記第１サブ境界を検索するステップと
を含む請求項１４に記載の方法。
【請求項１６】
上記第１コーンに関する上記第１境界の前記検索するステップが、
上記第１境界が上記境界階層のリーフであり、上記第１コーンが上記コーン階層のリーフでないかどうかを判定するステップと、
前記第１境界が上記境界階層のリーフであり、前記第１コーンが上記コーン階層のリーフでないことの肯定の判定に応答して、上記第１境界に関して上記第１コーンのサブコーンを条件的に検索するステップと
を含む請求項６に記載の方法。
【請求項１７】
上記第１境界に関する上記第１コーンのサブコーンの前記条件的検索が、
上記第１コーンの第１サブコーンに関する上記第１境界のコーン−境界の離隔値を計算するステップと、
上記コーン−境界の離隔値が上記第１サブコーンに関連する測定値に関して上記不等式条件を満足するかどうかを判定するステップと、
前記コーン−境界の離隔値が上記第１サブコーンに関連する上記測定値に関して上記不等式条件を満足することの肯定の判定に応答して、前記第１境界に関して前記第１サブコーンを検索するステップと
を含み、上記第１コーンに関する上記第１境界の前記検索するステップが、さらに、上記第１コーンに関連する上記測定値に、上記第１境界に関する前記サブコーンの前記条件的検索の後の前記サブコーンに関連する上記測定値の極値をセットするステップとを含む請求項１６に記載の方法。
【請求項１８】
上記第１コーンに関する上記第１境界の前記検索するステップが、
上記第１コーンの第１サブコーンに関する上記第１境界の第１コーン−境界の離隔値を計算するステップと、
上記第１コーン−境界の離隔値が、前記第１サブコーンに関連する測定値に関して上記不等式条件を満足するかどうかを判定するステップと、
前記第１コーン−境界の離隔値が、前記第１サブコーンに関連する上記測定値に関して上記不等式条件を満足することの肯定の判定に応答して、前記第１サブコーンに関して前記第１境界のサブ境界を条件的に探索するステップと
を含む請求項６に記載の方法。
【請求項１９】
前記第１サブコーンに関する前記第１境界のサブ境界の前記条件的探索が、
前記第１サブコーンに関して前記サブ境界のそれぞれの第２コーン−境界の離隔値を計算するステップと、
上記第１サブコーンからの離隔の昇順で、前記第１サブコーンに関して前記第１境界の前記サブ境界を条件的に検索するステップと
を含む請求項１８に記載の方法。
【請求項２０】
前記第１サブコーンに関する前記第１境界の前記サブ境界の前記条件的検索が、
前記サブ境界のうちの第１サブ境界の上記第２コーン−外皮の離隔値が、上記第１サブコーンに関連する上記測定値に関して上記不等式条件を満足するかどうかを判定するステップと、
上記第１サブ境界の上記第２コーン−外皮の離隔値が上記第１サブコーンに関連する上記測定値に関して上記不等式条件を満足することの肯定の判定に応答して、前記第１サブコーンに関して前記第１サブ境界を検索するステップと
を含み、上記第１コーンに関する上記第１境界の前記検索するステップが、さらに、上記第１コーンに関連する上記測定値に、前記第１サブコーンを含む上記第１コーンのサブコーンに関連する上記測定値の極値をセットすることを含む請求項１９に記載の方法。
【請求項２１】
可視オブジェクトを表示するコンピュータ・システムであって、
表示装置と、
オブジェクトの集合を記憶するためのメモリであって、可視性検索プログラムも格納する、メモリと、
上記可視性検索プログラムを実行する、上記メモリに結合されたプロセッサであって、上記可視性検索プログラムの制御下で、
オブジェクトの集合にアクセスし、
上記オブジェクトの集合から境界階層を構成し、
コーン階層を構成し、
上記コーン階層のコーンのサブセットの最も近いオブジェクトを判定するために、上記コーン階層および上記境界階層を検索する
ように構成されたプロセッサと
を含み、上記表示装置が、上記コーン階層内の上記コーンのサブセットの上記最も近いオブジェクトを表示するように動作可能である
コンピュータ・システム
【請求項２２】
上記コーンのサブセットが、上記コーン階層のリーフ・コーンを含む請求項２１に記載のコンピュータ・システム
【請求項２３】
上記コーン階層および上記境界階層の前記検索を実行する際に、前記プロセッサが、
上記コーン階層の第１コーンと上記境界階層の第１境界との間の離隔の第１測定値を判定し、
上記第１測定値が、上記第１コーンに関連する測定値に関して不等式条件を満足するかどうかを判定し、
上記第１測定値が上記第１コーンに関連する上記測定値に関して上記不等式条件を満足することの肯定の判定に応答して、上記第１コーンに関して上記第１境界を検索する
ように構成される請求項２１に記載のコンピュータ・システム。
【請求項２４】
さらに、上記プロセッサに結合されたグラフィックス・アクセラレータを含み、前記プロセッサが、上記コーン階層の各リーフ・コーンの上記最も近いオブジェクトの指定を含む可視性情報を上記グラフィックス・アクセラレータに送るように構成され、上記グラフィックス・アクセラレータが、上記コーン階層の各リーフ・コーンの上記最も近いオブジェクトに基づいて表示画面上に画像をレンダリングするように構成される請求項２３に記載のコンピュータ・システム。
【請求項２５】
上記境界階層を構成するために、上記プロセッサが、
クラスタを形成するために前記オブジェクトをクラスタ化し、
対応する境界を用いて各オブジェクトおよび各クラスタの境界を定め、
各オブジェクトおよび各クラスタについて、上記境界階層内でノードを割り振り、
各ノードに関連するパラメータが、上記対応する境界を記述する、上記パラメータを各ノードに関連付け、
ノード関係がクラスタ・メンバシップを表すように上記ノードを編成する
ように動作可能である請求項２３に記載のコンピュータ・システム。
【請求項２６】
上記第１コーンと上記第１境界との間の離隔の上記第１測定を判定するために、上記プロセッサが、上記第１コーンの頂点と上記第１コーンおよび上記第１境界の共通部分の点との間の離隔距離の増加関数を最小化する計算を実行し、上記第１測定値が上記不等式条件を満足するかどうかを判定する際に、上記プロセッサが、上記第１測定値が上記第１コーンに関連する上記測定値より小さいかどうかを判定する請求項２３に記載のコンピュータ・システム。
【請求項２７】
上記第１コーンと上記第１境界との間の離隔の上記第１測定を判定する際に、上記プロセッサが、上記第１コーンの頂点と上記第１コーンおよび上記第１境界の共通部分の点との間の離隔距離の減少関数を最大化する計算を実行し、上記第１測定値が上記不等式条件を満足するかどうかを判定する際に、上記プロセッサが、上記第１測定値が上記第１コーンに関連する上記測定値より大きいかどうかを判定する請求項２３に記載のコンピュータ・システム。
【請求項２８】
上記第１コーンと上記第１境界との間の離隔の上記第１測定値を判定する際に、上記プロセッサが、上記第１コーンの頂点と上記第１コーンおよび上記第１境界の共通部分の点との間の極大距離を判定するために、上記第１コーンを定義する制約の第１組と上記第１境界を定義する制約の第２組とを使用して非線形計画問題を解く請求項２３に記載のコンピュータ・システム。
【請求項２９】
上記プロセッサが、初期コーンを細分することによって上記コーン階層を構成する請求項２３に記載のコンピュータ・システム。
【請求項３０】
上記第１コーンに関して上記第１境界を検索する際に、上記プロセッサが、
前記第１コーンが上記コーン階層のリーフであり、前記第１境界が上記境界階層のリーフであるか否かを判定し、
上記第１コーンに関連する上記測定値に、上記第１境界と上記第１コーンとの間の離隔の上記第１測定値をセットし、
上記第１コーンに関連する可視オブジェクト属性に、上記第１境界をセットする
ように構成され、上記第１コーンに関連する上記測定値の前記セットおよび上記第１コーンに関連する上記可視オブジェクト属性の前記セットが、上記第１コーンが上記コーン階層のリーフであり、上記第１境界が上記外皮階層のリーフであることの肯定の判定に応答して実行される請求項２３に記載のコンピュータ・システム。
【請求項３１】
上記第１コーンに関して上記第１境界を検索する際に、上記プロセッサが
前記第１コーンが上記コーン階層のリーフであり、前記第１境界が上記境界階層のリーフでないかどうかを判定し、
前記第１コーンが上記コーン階層のリーフであり、前記第１境界が上記境界階層のリーフでないことの肯定の判定に応答して、前記第１コーンに関して前記第１境界のサブ境界を条件的に探索する
ように構成される請求項２３に記載のコンピュータ・システム。
【請求項３２】
前記第１境界のサブ境界を条件的に探索する際に、前記プロセッサが、
前記第１コーンに関する上記第１境界の上記サブ境界のそれぞれのコーン−境界の離隔値を計算し、
上記第１コーンからの離隔の昇順で、前記第１コーンに関して前記第１境界の前記サブ境界を条件的に検索する
ように構成される請求項３１に記載のコンピュータ・システム。
【請求項３３】
前記第１境界の前記サブ境界を条件的に検索する際に、上記プロセッサが、
前記サブ境界のうちの第１サブ境界の上記コーン−境界の離隔値が、上記第１コーンに関連する上記測定値に関して上記不等式条件を満足するかどうかを判定し、
上記第１サブ境界の上記コーン−境界の離隔値が、上記第１コーンに関連する上記測定値に関して上記不等式条件を満足することの肯定の判定に応答して、前記第１コーンに関して前記第１サブ境界を検索する
ように構成される請求項３２に記載のコンピュータ・システム。
【請求項３４】
上記第１コーンに関して上記第１境界を検索する際に、上記プロセッサが、
上記第１境界が上記境界階層のリーフであり、上記第１コーンが上記コーン階層のリーフでないかどうかを判定し、
前記第１境界が上記境界階層のリーフであり、前記第１コーンが上記コーン階層のリーフでないことの肯定の判定に応答して、上記第１境界に関して上記第１コーンのサブコーンを条件的に検索する
ように構成される請求項２３に記載のコンピュータ・システム。
【請求項３５】
上記第１境界に関して上記第１コーンのサブコーンを条件的に検索する際に、上記プロセッサが、
上記第１コーンの第１サブコーンに関する上記第１境界のコーン−境界の離隔値を計算し、
上記コーン−境界の離隔値が上記第１サブコーンに関連する測定値に関して上記不等式条件を満足するかどうかを判定し、
前記コーン−境界の離隔値が上記第１サブコーンに関連する上記測定値に関して上記不等式条件を満足することの肯定の判定に応答して、前記第１境界に関して前記第１サブコーンを検索する
ように構成され、上記第１コーンに関して上記第１境界を検索する際に、上記プロセッサが、上記第１コーンに関連する上記測定値に、上記第１境界に関する前記サブコーンの前記条件的検索の後の前記サブコーンに関連する上記測定値の極値をセットする請求項３４に記載のコンピュータ・システム。
【請求項３６】
上記第１コーンに関して上記第１境界を検索する際に、上記プロセッサが、
上記第１コーンの第１サブコーンに関する上記第１境界の第１コーン−境界の離隔値を計算し、
上記第１コーン−境界の離隔値が、前記第１サブコーンに関連する測定値に関して上記不等式条件を満足するかどうかを判定し、
前記第１コーン−境界の離隔値が、前記第１サブコーンに関連する上記測定値に関して上記不等式条件を満足することの肯定の判定に応答して、前記第１サブコーンに関して前記第１境界のサブ境界を条件的に探索する
ように構成される請求項２３に記載のコンピュータ・システム。
【請求項３７】
前記第１サブコーンに関して前記第１境界のサブ境界を条件的に探索する際に、上記プロセッサが、
前記第１サブコーンに関して前記サブ境界のそれぞれの第２コーン−境界の離隔値を計算し、
上記第１サブコーンからの離隔の昇順で、前記第１サブコーンに関して前記第１境界の前記サブ境界を条件的に検索する
ように構成される請求項３６に記載のコンピュータ・システム。
【請求項３８】
前記第１サブコーンに関して前記第１境界の前記サブ境界を条件的に検索する際に、上記プロセッサが、
前記サブ境界のうちの第１サブ境界の上記第２コーン−外皮の離隔値が、上記第１サブコーンに関連する上記測定値に関して上記不等式条件を満足するかどうかを判定し、
上記第１サブ境界の上記第２コーン−外皮の離隔値が上記第１サブコーンに関連する上記測定値に関して上記不等式条件を満足することの肯定の判定に応答して、前記第１サブコーンに関して前記第１サブ境界を検索する
ように構成され、上記第１コーンに関して上記第１境界を検索するために、上記プロセッサが、上記第１コーンに関連する上記測定値に、前記第１サブコーンを含む上記第１コーンのサブコーンに関連する上記測定値の極値をセットする請求項３７に記載のコンピュータ・システム。
【発明の詳細な説明】
【０００１】
（１．技術分野）
本発明は、全般的にはコンピュータ・グラフィックスの分野に関し、具体的には、グラフィックス環境で定義された視点から可視のオブジェクト／表面の組を判定するという問題に関する。
【０００２】
（２．背景技術）
ビジュアライゼーション・ソフトウェアは、３次元設計を物理的に実現するよりかなり前から、３次元設計を評価するのに非常に有用であることがわかっている。さらに、ビジュアライゼーション・ソフトウェアは、エンジニアリング会社が設計サイクルの早期に設計の問題を見つけることができので、かなりの金額を節約でき、コスト効率を与えていた。残念ながら、ますます複雑なシーンを見る必要性が、適度なフレーム・レートでそれを表示するグラフィックス・ハードウェア・システムの能力を追い越している。シーンの複雑さが高まるにつれて、ビジュアライゼーション・ソフトウェア設計者は、グラフィック・ハードウェア・パイプラインによって提供されるレンダリング・リソースを注意深く使用する必要が生じる。
【０００３】
ハードウェア・パイプラインは、三角形作業を破棄する時にレンダリング帯域幅を浪費する。レンダリング帯域幅の浪費は、破棄する三角形を描画しないようにパイプラインに要求することによって減らすことができる。パイプライン浪費を減らすためのさまざまなソフトウェア方法が、これまでに発展してきた。各技法が、パイプライン内の異なる点で浪費を減らす。例として、ソフトウェア切頭体のカリング（ｃｕｌｌｉｎｇ）は、パイプラインのクリッピング計算での破棄を大幅に減らすことができ、ソフトウェア裏面カリングは、パイプラインのライティング計算での破棄を減らすことができる。
【０００４】
ｚバッファは、グラフィックス・パイプラインのうちで作業を破棄する最後の部分である。本質的に、ｚバッファは、可視の表面を保持し、可視でない表面を破棄する。シーンの複雑さが高まるにつれて、特にウォーク・スルー環境およびＣＡＤ環境で、遮られる表面の数が急激に増え、その結果として、ｚバッファが破棄する表面の数も増える。フレームの平均デプス複雑性によって、ｚバッファがどれだけの作業（したがってレンダリング帯域幅）を破棄するかが大まかに決定される。画素あたりのデプス複雑性がｄのフレームでは、パイプラインの効率が１／ｄになる。したがって、デプス複雑性が高まるにつれて、ハードウェア・パイプラインはそれに比例してますます非効率的になる。
【０００５】
ソフトウェア・オクルージョン・カリング（ｏｃｃｌｕｓｉｏｎ ｃｕｌｌｉｎｇ）が、レンダリング効率を改善するための追加のツールとして提案された。オクルージョン・カリングを実行するビジュアライゼーション・プログラムは、遮られるオブジェクトの描画をハードウェア・パイプラインに要求しないことによって、グラフィック・ハードウェアの総合レンダリング帯域幅を効果的に高める。シーンの可視オブジェクトの計算は、オクルージョン・カリングの計算に対する相補的な問題である。遮られる（オクルードされる）オブジェクトをシーン内または切頭体カリングされたシーン内のオブジェクトの組から除去するのではなく、プログラムがどのオブジェクトが可視であるかを計算し、可視オブジェクトだけを描画する。単純なビジュアライゼーション・プログラムは、可視オブジェクトの組を計算し、現在の視点から可視オブジェクトを描画し、パイプラインに裏向きのポリゴンを除去させ、ｚバッファに不可視の表面を除去させる。
【０００６】
可視オブジェクトの組を計算する技法の１つでは、レイ・キャスティングを使用する。レイ・キャスティング技法を実施したシステム、ＲｅａｌＥｙｅｓ［Ｓｏｗｉｚｒａｌ，Ｈ．Ａ．，Ｚｉｋａｎ，Ｋ．，Ｅｓｐｏｓｉｔｏ，Ｃ．，Ｊａｎｉｎ，Ａ．，Ｍｉｚｅｌｌ，Ｄ．”ＲｅａｌＥｙｅｓ：　Ａ　Ｓｙｓｔｅｍ　ｆｏｒ　Ｖｉｓｕａｌｉｚｉｎｇ　Ｖｅｒｙ　Ｌａｒｇｅ　Ｐｈｙｓｉｃａｌ　Ｓｔｒｕｃｔｕｒｅｓ”，ＳＩＧＧＲＡＰＨ　’９４，Ｖｉｓｕａｌ　Ｐｒｏｃｅｅｄｉｎｇｓ，１９９４，ｐ．２２８］が、ＳＩＧＧＲＡＰＨ　１９９４年のＢＯＯＭルームでデモンストレーションされた。インタラクティブな速度で、訪問者がボーイング７４７の内部を「歩き回る」か、宇宙ステーションＦｒｅｅｄｏｍの研究室モジュールを含む構造を探検することができた。
【０００７】
可視性判定での光線（レイ）の使用に対する直観は、光の特性に頼るものである。光線に沿って最初に出会うオブジェクトは、それだけが見る人の目に入る光線を反射することができるので、可視である。また、そのオブジェクトは、見る人と、光線に沿った後続のすべてのオブジェクトの間に入り、後続オブジェクトを可視でなくする。コンピュータ・グラフィックの離散世界では、連続体の光線を伝播させることが困難である。したがって、光線の離散サブセットが必ず使用される。もちろん、これは、光線サンプルの解像度より小さい可視オブジェクトまたはオブジェクトのセグメントが見逃され、発見されない可能性があることを意味する。これは、光線が、光線サンプルの密度までしか可視オブジェクトの正しい判定を保証しないからである。図１に、光線ベースの可視オブジェクト検出の方法を示す。１つまたは複数のオブジェクトと相互作用する光線は、オブジェクトとの最初の接触の点に丸印を記されている。画面の画素の光線に対応する値を決定するのは、この最初の接触の点である。また、Ａと記されたオブジェクトは、所与の光線サンプルによって完全に見逃されるのに十分に小さいことを観察されたい。
【０００８】
可視オブジェクト判定は、可視表面判定にその基礎を有する。Ｆｏｌｅｙ他［Ｆｏｌｅｙ，Ｊ．，ｖａｎ　Ｄａｍ，Ａ．，Ｆｅｉｎｅｒ，Ｓ．ａｎｄ　Ｈｕｇｈｅｓ，Ｊ．Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ；　Ｐｒｉｎｃｉｐｌｅｓ　ａｎｄ　Ｐｒａｃｔｉｃｅ，２ｎｄ　ｅｄ，，Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ，Ｃｈａｐｔｅｒ　１５，ｐｐ．６４９−７１８，１９９６］は、可視表面判定手法を２つの大まかなグループすなわち、画像精度アルゴリズムとオブジェクト精度アルゴリズムに分類した。画像精度アルゴリズムは、通常は、表示装置の解像度で動作し、計算的に優れた性能を有する傾向がある。オブジェクト精度手法は、オブジェクト空間で動作し、通常は、オブジェクト対オブジェクトの比較を実行する。
【０００９】
基本型の画像精度可視表面判定アルゴリズムでは、視点から各表示画素の中央を通る光線を投影して、各光線に沿った最も近い可視表面を判定する。可視表面レイ・キャスティング（またはレイ・トレーシング）の応用例のリストは、長く、有名である。Ａｐｐｅｌ［”Ｓｏｍｅ　Ｔｅｃｈｎｉｑｕｅｓ　ｆｏｒ　Ｓｈａｄｉｎｇ　Ｍａｃｈｉｎｅ　Ｒｅｎｄｅｒｉｎｇ　ｏｆ　Ｓｏｌｉｄｓ”，ＳＪＣＣ’６８，ｐｐ．３７−４５，１９６８］は、シェーディングにレイ・キャスティングを使用する。ＧｏｌｄｓｔｅｉｎおよびＮａｇｅｌ［Ｍａｔｈｅｍａｔｉｃａｌ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｇｒｏｕｐ，Ｉｎｃ．，”３−Ｄ　Ｓｉｍｕｌａｔｅｄ　Ｇｒａｐｈｉｃｓ　Ｏｆｆｅｒｅｄ　ｂｙ　Ｓｅｒｖｉｃｅ　Ｂｕｒｅａｕ，”　Ｄａｔａｍａｔｉｏｎ，１３（１），Ｆｅｂｒｕａｒｙ　１９６８，ｐ．６９．；Ｇｏｌｄｓｔｅｉｎ，Ｒ．Ａ．ａｎｄ　Ｎａｇｅｌ，Ｒ．”３−Ｄ　Ｖｉｓｕａｌ　Ｓｉｍｕｌａｔｉｏｎ”，Ｓｉｍｕｌａｔｉｏｎ，１６（１），ｐｐ．２５−３１，１９７１も参照されたい］は、論理集合演算にレイ・キャスティングを使用する。Ｋａｙ他［Ｋａｙ，Ｄ．Ｓ．ａｎｄ　Ｇｒｅｅｎｂｅｒｇ，Ｄ．，”Ｔｒａｎｓｐａｒｅｎｃｙ　ｆｏｒ　Ｃｏｍｐｕｔｅｒ　Ｓｙｎｔｈｅｓｉｚｅｄ　Ｉｍａｇｅｓ，”　ＳＩＧＧＲＡＰＨ’７９，ｐｐ．１５８−１６４］およびＷｈｉｔｔｅｄ［”Ａｎ　Ｉｍｐｒｏｖｅｄ　Ｉｌｌｕｍｉｎａｔｉｏｎ　Ｍｏｄｅｌ　ｆｏｒ　Ｓｈａｄｅｄ　Ｄｉｓｐｌａｙ”，ＣＡＣＭ，２３（６）．ｐｐ．３４３−３４９，１９８０］は、屈折計算およびスペキュラ反射計算にレイ・トレーシングを使用する。Ａｉｒｅｙ他［Ａｉｒｅｙ，Ｊ．Ｍ．，Ｒｏｈｌｆ，Ｊ．Ｈ，．ａｎｄ　Ｂｒｏｏｋｓ，Ｊｒ．Ｆ．Ｐ．Ｔｏｗａｒｄｓ　Ｉｍａｇｅ　Ｒｅａｌｉｓｍ　ｗｉｔｈ　Ｉｎｔｅｒａｃｔｉｖｅ　Ｕｐｄａｔｅ　Ｒａｔｅｓ　ｉｎ　Ｃｏｍｐｌｅｘ　Ｖｉｒｔｕａｌ　Ｂｕｉｌｄｉｎｇ　Ｅｎｖｉｒｏｎｍｅｎｔｓ．ＡＣＭ　ＳＩＧＧＲＡＰＨ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｉｎｔｅｒａｃｔｉｖｅ　３Ｄ　Ｇｒａｐｈｉｃｓ，２４，２（１９９０），ｐｐ．４１−５０］は、所与のセルから可視のモデルの部分を計算するのにレイ・キャスティングを使用する。
【００１０】
可視表面判定のもう１つの手法では、表面のデータベースにビームまたはコーンを送ることに頼る［Ｄａｄｏｕｎ　ｅｔ　ａｌ．，”Ｈｉｅｒａｒｃｈｉｃａｌ　ａｐｐｒｏａｃｈｓ　ｔｏ　ｈｉｄｄｅｎ　ｓｕｒｆａｃｅ　ｉｎｔｅｒｓｅｃｔｉｏｎ　ｔｅｓｔｉｎｇ．”　Ｐｒｏｃｅｅｅｄｉｎｇｓ　ｏｆ　Ｇｒａｐｈｉｃｓ　Ｉｎｔｅｒｆａｃｅ　’８２，Ｔｏｒｏｎｔｏ，Ｍａｙ　１９８２，４９−５６；およびＤａｄｏｕｎ　ｅｔ　ａｌ．，”Ｔｈｅ　ｇｅｏｍｅｔｒｙ　ｏｆ　ｂｅａｍ　ｔｒａｃｉｎｇ．”　Ｉｎ　Ｊｏｓｅｐｈ　Ｏ’Ｒｏｕｒｋｅ，ｅｄ．，Ｐｒｏｃｅｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｇｅｏｍｅｔｒｙ，ｐｐ．５５−６１，ＡＣＭ　Ｐｒｅｓｓ，Ｎｅｗ　Ｙｏｒｋ，１９８５を参照されたい］。基本的に、ビームは、光線の置換物になる。この手法では、通常は、オブジェクトとの相互作用の後におそらくはコンパクトなビームを接触しないコーンの組へ分解する。
【００１１】
さまざまな空間副分割方式が、シーン内のオブジェクトに空間的構造を与えるのに使用されてきた［以下の４つの参考文献は、空間副分割方式に関係する：（ａ）Ｇｌａｓｓｎｅｒ，”Ｓｐａｃｅ　ｓｕｂｄｉｖｉｓｉｏｎ　ｆｏｒ　ｆａｓｔ　ｒａｙ　ｔｒａｃｉｎｇ，”　ＩＥＥＥ　ＣＧ＆Ａ，４（１０）：１５−２２，Ｏｃｔ．１９８４；（ｂ）Ｊｅｖａｎｓ　ｅｔ　ａｌ．，”Ａｄａｐｔｉｖｅ　ｖｏｘｅｌ　ｓｕｂｄｉｖｉｓｉｏｎ　ｆｏｒ　ｒａｙ　ｔｒａｃｉｎｇ，”　Ｐｒｏｃｅｅｄｉｎｇｓ　Ｇｒａｐｈｉｃｓ　Ｉｎｔｅｒｆａｃｅ　’８９，１６４−１７２，Ｊｕｎｅ　１９８９；（ｃ）Ｋａｐｌａｎ，Ｍ．”Ｔｈｅ　ｕｓｅ　ｏｆ　ｓｐａｔｉａｌ　ｃｏｈｅｒｅｎｃｅ　ｉｎ　ｒａｙ　ｔｒａｃｉｎｇ，”　ｉｎ　Ｔｅｃｈｎｉｑｕｅｓ　ｆｏｒ　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ．．．，Ｒｏｇｅｒｓ，Ｄ．ａｎｄ　Ｅａｒｎｓｈａｗ　Ｒ．Ａ．（ｅｄｓ），Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，Ｎｅｗ　Ｙｏｒｋ，１９８７；および（ｄ）Ｒｕｂｉｎ，Ｓ．Ｍ．ａｎｄ　Ｗｈｉｔｔｅｄ，Ｔ．”Ａ　３−ｄｉｍｅｎｓｉｏｎａｌ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ　ｆｏｒ　ｆａｓｔ　ｒｅｎｄｅｒｉｎｇ　ｏｆ　ｃｏｍｐｌｅｘ　ｓｃｅｎｅｓ，”　Ｃｏｍｐｕｔｅｒ　Ｇｒａｐｈｉｃｓ，１４（３）；１１０−１１６，Ｊｕｌｙ　１９８０］。
【００１２】
Ｋａｙ他［Ｋａｙ，Ｔ．Ｌ．ａｎｄ　Ｋａｊｉｙａ，Ｊ．Ｔ．”Ｒａｙ　Ｔｒａｃｉｎｇ　Ｃｏｍｐｌｅｘ　Ｓｃｅｎｅｓ”，ＳＩＧＧＲＡＰＨ　１９８６，ｐｐ．２６９　−　２７８，１９８６］は、レイ・キャスティングの計算的態様に集中して、光線と共に空間境界ボリュームの階層を使用して、各光線に沿った可視オブジェクトを判定した。もちろん、空間階層は、事前に計算する必要がある。しかし、使える状態になったならば、そのような階層は、オブジェクトを発見するための再帰計算を容易にする。環境が静止している場合、同一のデータ構造によって、任意の起点からの光線に沿った可視オブジェクトの発見が容易になる。
【００１３】
Ｔｅｌｌｅｒ他［Ｔｅｌｌｅｒ，Ｓ．ａｎｄ　Ｓｅｑｕｉｎ．Ｃ．Ｈ．”Ｖｉｓｉｂｉｌｉｔｙ　Ｐｒｅｐｒｏｃｅｓｓｉｎｇ　ｆｏｒ　Ｉｎｔｅｒａｃｔｉｖｅ　Ｗａｌｋｔｈｒｏｕｇｈｓ，”　ＳＩＧＧＲＡＰＨ　’９１，ｐｐ．６１−６９］は、セルからセルへの可視性を事前に計算することによって、可視オブジェクト計算で利益を得るために前処理を使用する。彼らの手法は、基本的に、オブジェクト精度手法であり、彼らは、５０ＭＩＰの計算機で２５００００ポリゴンのモデルに関する５８Ｍバイトの可視性情報の計算に６時間以上の前処理時間を要すると報告している［Ｔｅｌｌｅｒ，Ｓ．ａｎｄ　Ｓｅｑｕｉｎ．Ｃ．Ｈ．”Ｖｉｓｉｂｉｌｉｔｙ　ｃｏｍｐｕｔａｔｉｏｎｓ　ｉｎ　ｐｏｌｙｈｅｄｒａｌ　ｔｈｒｅｅ−ｄｉｍｅｎｓｉｏｎａｌ　ｅｎｖｉｒｏｎｍｅｎｔｓ，”　Ｕ．Ｃ．Ｂｅｒｋｅｌｅｙ　Ｒｅｐｏｒｔ　Ｎｏ．ＵＣＢ／ＣＳＤ　９２／６８０，Ａｐｒｉｌ　１９９２］。
【００１４】
可視性計算に対する異なる手法で、Ｇｒｅｅｎｅ他［Ｇｒｅｅｎｅ，Ｎ．，Ｋａｓｓ，Ｍ．，ａｎｄ　Ｍｉｌｌｅｒ，Ｇ．”Ｈｉｅｒａｒｃｈｉｃａｌ　ｚ−Ｂｕｆｆｅｒ　Ｖｉｓｉｂｉｌｉｔｙ，”　ＳＩＧＧＲＡＰＨ　’９３，ｐｐ．２３１−２３８］は、さまざまな階層データ構造を使用して、オブジェクト空間に固有の空間的構造（オブジェクトのオクトリ）、画素に固有の画像構造（Ｚピラミッド）、およびフレームごとのレンダリングに固有の時間的構造（前に可視であったオクトリ・ノードのリスト）を活用するのを助ける。Ｚピラミッドは、オクトリ内の立方体の高速スキャン変換を使用して可視性に関するテストを行うことによって、モデルの大きい部分の高速カリングを可能にする。
【００１５】
グラフィカル環境のデプス複雑性は、リアリズムおよび性能に関する消費者の需要に応答して増大を続ける。したがって、可視オブジェクト判定のためのアルゴリズムの効率は、ビジュアライゼーション・システムの市場性に直接的な影響を有する。可視オブジェクト判定アルゴリズムが必要とする計算帯域幅によって、ビジュアライゼーション・システムに必要なプロセッサのクラスが決定され、それによって、総合的なシステム・コストに影響する。したがって、可視オブジェクト判定の効率を改善するシステムまたは方法が、非常に望まれる。
【００１６】
（発明の開示）
本発明は、グラフィックス環境で可視オブジェクトを表示するシステムおよび方法を含む。具体的に言うと、コーン階層および境界階層の二重検索に基づく可視オブジェクト判定を実行するシステムおよび方法を本明細書で開示する。このシステムには、プロセッサ、表示装置、システム・メモリ、および任意選択のグラフィックス・アクセラレータが含まれる。プロセッサは、ビジュアライゼーション・ソフトウェアを実行し、このビジュアライゼーション・ソフトウェアは、３次元オブジェクトの集合の表示装置でのビジュアライゼーションを提供する。オブジェクトは、３次元空間に存在し、したがって、お互いを遮る可能性がある。
【００１７】
ビジュアライゼーション・ソフトウェアは、視点から発するコーンの階層として空間を表現する。１実施態様では、階層のリーフ・コーンすなわち、細分化の最高レベルにあるコーンが、シーン領域の画素の一部に対応する領域と相対する。たとえば、２つのコーンが、好都合なことに１画素の領域を満たすことができる。その代わりに、リーフ・コーンが、１つまたは複数の画素を含む領域と相対することができる。
【００１８】
初期ビュー切頭体またはビュー切頭体の近傍を、再帰的にテセレート（すなわち細分）して（ｔｅｓｓｅｌｌａｔｅｄ）、コーン階層を生成する。代替案では、視点周囲の空間全体を、再帰的にテセレートして、コーン階層を生成する。この場合、コーン階層は、視点および視線方向の変化に対して再計算する必要がなくなる。
【００１９】
ビジュアライゼーション・ソフトウェアは、オブジェクトの集合から境界の階層も生成する。具体的に言うと、境界階層は、（ａ）０次クラスタとしてオブジェクト自体から始めて、クラスタを再帰的にグループ化し、（ｂ）各オブジェクトおよびクラスタ（すべての次数の）を、対応する境界、たとえば多面体の外皮を用いて境界を定め、（ｃ）オブジェクトおよびクラスタごとに境界階層内にノードを割り振り、（ｄ）クラスタのメンバシップを反映するように境界階層内のノードを編成することによって、生成される。たとえば、ノードＡがノードＢの親である場合には、ノードＡに対応するクラスタに、ノードＢに対応するサブクラスタ（またはオブジェクト）が含まれる。各ノードには、対応するクラスタまたはオブジェクトの境界の特徴を表すパラメータが格納される。
【００２０】
ビジュアライゼーション・ソフトウェアは、ルート・コーンおよびルート境界から始めて、コーン階層および境界階層の検索を実行する。各リーフ・コーンには、そのリーフ・コーン内から認められる最も近い既知のオブジェクトまでの距離をあらわす可視性距離値が割り当てられる。各リーフ・コーンには、そのリーフ・コーンの視野内の最も近い既知のオブジェクトを指定するオブジェクト属性も割り当てられる。同様に、各非リーフ・コーンには、可視性距離値が割り当てられる。しかし、非リーフ・コーンの可視性距離値には、そのサブコーンの子の可視性距離値の最大値がセットされる。これは、各非リーフ・コーンの可視性距離値が、そのリーフ・コーンの子孫の可視性距離の最大値に等しいことを意味する。
【００２１】
可視性ソフトウェアは、コーン−境界対に対して動作する。所与のコーン−境界対を探索する前に、コーンと境界の間の距離を測定する。これには、コーンの頂点から境界とコーンの両方に存在する点までの最小の距離の判定が含まれる。このコーン−境界距離を、コーンの可視性距離値と比較する。コーン−境界距離が、コーンの可視性距離値より大きい場合には、所与のコーンのすべてのリーフ・コーン子孫が、可視性距離値の定義によって所与の境界より近い既知の可視性オブジェクトを有する。したがって、このコーン−境界対を探索することによって利益を得ることはできない。逆に、コーン−境界距離が、コーンの可視性距離値より小さい場合には、その境界に、所与のコーンの１つまたは複数のリーフ・コーン子孫の可視性距離値に影響するオブジェクトが含まれる可能性がある。このコーン−境界対は検索しなければならない。本発明によれば、コーン−境界対は、有利なことに、所与の境界がコーンの子孫の可視性に影響する可能性がある時に限って検索される。したがって、本発明の検索アルゴリズムでは、不要なコーン−境界探索がなくなり、それによって、かなりの計算帯域幅が節約される。
【００２２】
検索条件が満足されると仮定すると、境界は、所与のコーンに関して探索される。コーンと境界の両方が、それぞれの階層のリーフである場合には、その境界は、リーフ・コーンの既知の最も近いオブジェクトより近いオブジェクトを指定する。したがって、リーフ・コーンの可視性距離値は、そのコーンと境界のコーン−境界距離を用いて更新される。また、コーンのオブジェクト属性は、所与の境界を指すように更新される。
【００２３】
コーンがリーフ・コーンであり、境界が非リーフ境界である場合には、検索アルゴリズムは、所与の境界のサブ境界を検査し、所与のコーンからのコーン−境界距離の昇順でこれらのサブ境界を条件的に探索する。やはり、サブ境界の探索は、コーンの可視性距離値より小さい、所与のコーンへのコーン−境界距離になるサブ境界を条件とする。
【００２４】
コーンが非リーフ・コーンであり、境界がリーフ境界（すなわち、単一のオブジェクトの境界になる境界）である場合には、検索アルゴリズムは、所与の境界に対して所与のコーンのサブコーンを条件的に探索する。サブコーンの探索は、サブコーンの可視性距離値より小さい、所与の境界へのコーン−境界距離になるサブコーンを条件とする。
【００２５】
コーンが非リーフ・コーンであり、境界が非リーフ境界である場合には、検索アルゴリズムは、所与のコーンのサブコーンに対して所与の境界のサブ境界を条件的に探索する。議論のために、所与のコーンの特定のサブコーンを考慮されたい。所与の境界のサブ境界は、サブコーンに対して、サブコーンからのコーン−境界距離の昇順で条件的に探索される。最も近いサブ境界が最初に検索され、潜在的に所与のサブコーンの可視性距離値が減少するので、後続の（より遠くの）サブ境界は、検索条件に合格するのがより困難すなわち、サブコーンの可視性距離値より小さい、所与のサブコーンへのコーン−境界距離を有することがより困難になる。したがって、条件探索をコーン−境界距離に従って順序付けることによって、最小の数のサブ境界を探索する必要が生じる可能性が最大になる。
【００２６】
２つの木の検索が完了した時に、各リーフ・コーンのオブジェクト属性は、そのリーフ・コーンから可視のオブジェクトを指し、リーフ・コーンの可視性距離値は、その可視のオブジェクトまで距離を指定する。この可視性情報は、グラフィックス・アクセラレータに供給され、その結果、グラフィックス・アクセラレータが、表示装置上に可視オブジェクト（または可視オブジェクトの可視部分）をレンダリングすることができるようになる。
【００２７】
１実施態様では、ビジュアライゼーション・ソフトウェアが、ユーザ入力を読み取って、グラフィックス環境内の現在の視点および視線方向を制御することによって、インタラクティブ・ビジュアライゼーションを提供する。追加のソフトウェアによって、注意深い状態管理および並列性の使用を介する効率的な計算が保証される。
【００２８】
１代替実施態様では、コーン階層と境界階層が反復的に検索される。第２の代替実施態様では、コーン階層と境界階層に対するレベル順の検索が実行される。
【００２９】
本発明では、境界とコーンの間の離隔または近接の程度を測定するさまざまな技法が企図されている。実施態様の１組では、コーンの頂点とコーンおよび境界の共通部分の点との間の離隔距離の増加関数の最小化に焦点を合わせている。もう１組の実施態様には、コーンの頂点とコーンおよび境界の共通部分の点の間の離隔距離の減少関数の最大化が含まれる。一般に、ゆるやかな「星型」条件に従う境界を有する波面が、境界とコーンの間の離隔の測定のための基礎を提供することができる。
【００３０】
（発明を実施するモード）
図２Ａは、本発明の好ましい実施形態によるグラフィカル計算システム８０を表す。グラフィカル計算システム８０には、システム・ユニット８２、およびシステム・ユニット８２に結合された表示装置８４が含まれる。表示装置８４は、さまざまな種類のビデオ・モニタまたはグラフィカル・ディスプレイのいずれかによって実現することができる。グラフィカル計算システム８０には、キーボード８６および、好ましくは、マウス８８も含まれる。
【００３１】
図２Ｂは、グラフィカル計算システム８０の１実施形態を示すブロック図である。図からわかるように、グラフィカル計算システム８０には、高速バスまたはシステム・バス１０４に結合されたホスト中央処理装置（ＣＰＵ）１０２が含まれる。システム・メモリ１０６も、システム・バス１０４に結合されることが好ましい。システム・メモリ１０６には、ランダム・アクセス・メモリ、読取専用メモリ、または大容量記憶装置を含む、さまざまな種類のメモリ・サブシステムのいずれをも含めることができる。ホスト・プロセッサ１０２は、シーン内の可視オブジェクトの組を判定するビジュアライゼーション・ソフトウェア・プログラムを実行する。ビジュアライゼーション・ソフトウェア・プログラムは、システム・メモリ１０６に記憶されている。代替実施形態では、ビジュアライゼーション・ソフトウェア・プログラムは、グラフィックス・アクセラレータ１１２内に含まれるプロセッサ上で実行される。
【００３２】
任意選択の３Ｄグラフィックス・アクセラレータ１１２をシステム・バス１０４に結合することができる。３Ｄアクセラレータ１１２がグラフィカル計算システム８０に含まれない場合には、表示装置８４を、システム・バス１０４に直接に結合することができる。さまざまな他の周辺装置または他のバスを、当技術分野で周知のようにシステム・バス１０４に接続することができることが仮定されている。表示装置８４は、３Ｄグラフィックス・アクセラレータ１１２に結合されている。ＣＰＵ１０２は、システム・バス１０４を介して、プログラム式入出力（Ｉ／Ｏ）プロトコルに従って、グラフィックス・アクセラレータ１１２との間で情報を転送することができる。さらに、グラフィックス・アクセラレータ１１２は、直接メモリ・アクセス（ＤＭＡ）プロトコルに従って、またはインテリジェント・バス・マスタリングを介して、システム・メモリ１０６にアクセスすることができる。
【００３３】
３Ｄグラフィックス・アクセラレータ１１２は、３Ｄレンダリング機能をホスト・プロセッサからオフロードし、したがって、改善されたシステム性能を提供する専用のグラフィックス・レンダリング・サブシステムである。３Ｄグラフィックス・アクセラレータを有するシステムでは、ホスト・プロセッサ１０２上で実行中のグラフィックス・アプリケーション・プログラムが、表示装置８４での出力のための３次元グラフィックス要素を定義する３次元ジオメトリ・データを生成する。アプリケーション・プログラムは、このジオメトリ・データをグラフィックス・アクセラレータ１１２に転送する。グラフィックス・アクセラレータ１１２は、ジオメトリ・データを受け取り、対応するグラフィックス要素を表示装置上にレンダリングする。コンピュータ・グラフィックスの基本的な目標は、ユーザにとって現実的なオブジェクトをレンダリングすることである。しかし、視覚的なリアリズムという問題は、非常に複雑である。「実世界」のオブジェクトには、色の微妙な変動、反射、表面の不規則性を含む、信じられない量の詳細が含まれる。３次元グラフィックスを表示するアプリケーションは、膨大な量の処理帯域幅を必要とする。たとえば、コンピュータ・システムが滑らかな３Ｄモーション・ビデオを生成するためには、コンピュータ・システムは、毎秒２０フレームから３０フレームの間のフレーム・レートまたは更新速度を維持する必要がある。これは、通常は、毎秒１００万個を超える三角形を処理できる３Ｄグラフィックス・アクセラレータを必要とする。
【００３４】
コンピュータ・システム８０には、本発明によるビジュアライゼーション・ソフトウェアが含まれる。このビジュアライゼーション・ソフトウェアは、ホスト・プロセッサ１０２によって実行されることが好ましいが、代替案として、グラフィックス・アクセラレータ１１２上に含まれるプロセッサによって実行されてもよい。
【００３５】
ビジュアライゼーション・ソフトウェアのアーキテクチャ
図３に示されているように、本発明のビジュアライゼーション・ソフトウェアには、３つの主な相が含まれる。最初のステップ２１０で、ビジュアライゼーション・ソフトウェアは、シーンをロードする。シーンには、複数のオブジェクトが含まれる。オブジェクト階層がまだ構成されていない場合には、シーンのロードにオブジェクト階層の構成が含まれる。ステップ２２０で、ビジュアライゼーション・ソフトウェアは、現在の視点に関してシーン内の可視オブジェクトの組を発見する。好ましい実施形態では、ビジュアライゼーション・ソフトウェアは、３次元座標空間内の視点からの３次元オブジェクトの可視性を計算するように設計される。しかし、本明細書に記載の方法論は、任意の次元の空間に自然に一般化される。
【００３６】
ビジュアライゼーション・ソフトウェアの１実施形態では、グラフィカル環境内の視点を、ユーザ入力によって変更することができる。たとえば、マウス８８の操作またはキーボード８６のキーの押下げもしくはその両方によって、ユーザが、視点と視線の向きを変えることができる。したがって、ビジュアライゼーション・ソフトウェアは、視点または視線の向きが変化した時に、必ず可視オブジェクトの組を再計算することが好ましい。
【００３７】
ステップ２３０で、ビジュアライゼーション・ソフトウェアは、グラフィックス・アクセラレータ１１２と共に、可視オブジェクトを表示する、すなわち、グラフィックス・アクセラレータ１１２に、これらのオブジェクトを表示画面内にレンダリングするように指令する。ホスト・コンピュータ上のソフトウェアで可視オブジェクト判定を実行することによって、グラフィックス・アクセラレータ１１２が、はるかに高い効率で動作することができるようになる。それによって、グラフィックス・システム８０の総合処理能力が改善される。可視オブジェクトの組の発見および表示は、視点または視線方向（すなわち方位）が変化する時に繰り返して行われる。発見ステップおよび表示ステップは、並列処理として実行されることが好ましい。しかし、代替実施形態では、順次実行される。
【００３８】
特に記述がない限り、モデル内のすべてのオブジェクトが、不透明の凸多面体であると仮定する。３次元立体が凸であると言われるのは、立体内（または立体の表面）の任意の２つの点を、完全に立体内に含まれる直線で連結できる場合である。したがって、立方体は凸であるが、ドーナツ型は凸ではない。多面体は、平面の側面を有するオブジェクト（たとえば立方体、四面体など）である。不透明オブジェクトに対する本明細書に記載される方法論は、透明または半透明のオブジェクトがコーン計算を終了させないようにすることによって、自然に透明または半透明のオブジェクトに拡張される。凸の仮定は、より多くの問題を示す。しかし、あらゆるオブジェクトは、凸多面体の合併として近似することができる。可視オブジェクトの組の計算が、正確な計算ではなくコンザバティブな（ｃｏｎｓｅｒｖａｔｉｖｅ）計算を必要とすることに留意することが役に立つ。言い換えると、可視オブジェクトの組を多めに見積もることが許容される。
【００３９】
オブジェクト階層の構成
当初、シーン内のオブジェクトは、オブジェクトを空間的にグループ化する階層に編成される。オクトリ（ｏｃｔｒｅｅ）は、オブジェクト階層を生成する可能性の１つである。しかし、好ましい実施形態では、近くのオブジェクトをグループ化し、再帰的にグループの対をより大きい包含空間にクラスタ化するクラスタ化アルゴリズムを使用する。クラスタ化アルゴリズムでは、単純な距離測定および閾値化演算を使用して、オブジェクトのクラスタ化を達成する。図４Ａないし４Ｄに、４つのオブジェクトＪ００ないしＪ１１の集合に関するクラスタ化処理を示す。オブジェクトには、オブジェクト・グループの２進木での最終的な位置を予想する形でインデックスを与えてある。オブジェクトは、平面内に配置された多角形として図示されている（図４Ａ参照）。しかし、読者は、これらのオブジェクトを、任意の３次元オブジェクトとして想像されたい。１実施形態では、オブジェクトは、３次元多面体である。
【００４０】
各オブジェクトは、本明細書で境界と称する、対応して囲んでいる表面によって境界を定められる、すなわち、囲まれる。好ましい実施形態では、各オブジェクトの境界は、図４Ｂに示されているように、多面体外皮（すなわち、平面の面を有する外皮）である。外皮Ｈ００ないしＨ１１には、それが境界を定めるオブジェクトとの一貫性を有するラベルが与えられている。たとえば、外皮Ｈ００は、オブジェクトＪ００の境界を定める。外皮は、座標軸の対に平行な辺を有する長方形として図示されている。これらの外皮は、固定された座標軸の組に垂直な面を有する、３次元の長方形の箱（直方体）を表す目的のものである。外皮ごとに、対応するノード・データ構造を生成する。ノードには、対応する外皮の特徴を表すパラメータが格納される。
【００４１】
外皮は、有限の個数の平面構成要素からなる表面を有するので、外皮の記述は、３次元空間での平面の記述に緊密に関係する。図５Ａに、任意の平面の式を生成する２次元の例を示す。単位ベクトルｎ［どのようなベクトルでもよいが、長さ１のベクトルが、議論のために好都合である］によって、２次元空間の原点を通る直線Ｌが定義される。ベクトルｖと単位ベクトルｎの内積（ｖ・ｎと表記する）をとることによって、単位ベクトルｎによって定義される方向へのベクトルｖの射影の長さが得られる。したがって、実定数ｃを与えられた場合に、ｘがベクトル変数であるものとして、式ｘ・ｎ＝ｃによって、直線Ｌに垂直で、原点から直線Ｌに沿って距離ｃにある直線Ｍが定義されることになる。３次元空間に関しては、これと同一の式によって、直線Ｌに垂直な、やはり原点から直線Ｌに沿ってｃの距離にある平面が定義される。定数ｃを負にすることができ、その場合に、直線（または平面）Ｍが、原点から単位ベクトルｎと反対の向きに直線Ｌに沿って｜ｃ｜の距離にあることを観察されたい。
【００４２】
直線ｘ・ｎ＝ｃは、平面を２つの半平面に分割する。上の式の等号を不等号に置換することによって、これらの半平面の一方の記述を得ることができる。不等式ｘ・ｎ＜ｃによって、直線Ｌの負の無限大の端を含む半平面が定義される［単位ベクトルｎは、直線Ｌの正方向を定義する］。３次元では、平面ｘ・ｎ＝ｃが、３次元空間を２つの半空間に分割する。不等式ｘ・ｎ＜ｃによって、直線Ｌの負の無限大の端を含む半空間が定義される。
【００４３】
図５Ｂに、４つの半平面の共通部分として長方形領域を定義する方法を示す。４つの法線ベクトルｎ１ないしｎ４と、４つの対応する定数ｃ１ないしｃ４を与えられた場合に、長方形領域は、１から４までの範囲のｉについて不等式ｘ・ｎｉ＜ｃｉの組を同時に満足する点の組として定義される。この連立不等式を、行列ベクトル式Ｎ・ｘ＜ｃによって要約することができる。ここで、行列Ｎの行は、法線ベクトルｎ１ないしｎ４であり、ベクトルｃの成分は、対応する定数ｃ１ないしｃ４である。法線ベクトルが、正負の軸の向きに重なるように（図５Ｂのように）選択される場合、結果の長方形領域は、軸に平行な辺を有する。図４Ｂに示された長方形の外皮Ｈ００ないしＨ１１のすべてが、共通の組の法線ベクトルを使用することに留意されたい。したがって、各外皮は、その独自のｃベクトルの特徴を有する。
【００４４】
３次元空間では、長方形の箱を、６つの半空間の共通部分として、同様の形で定義することができる。３つの正の軸方向および３つの負の軸方向のそれぞれに向けられた６つの法線ベクトルｎ１ないしｎ６と、６つの対応する定数ｃ１ないしｃ６を与えられた場合に、１から６までのｉについて不等式ｘ・ｎｉ＜ｃｉを同時に満足する解によって、座標平面に平行な面を有する長方形の箱が定義される。したがって、長方形の箱は、同一の行列ベクトル式Ｎ・ｘ＜ｃを用いてコンパクトに表現することができ、ここで、行列Ｎは、６つの法線ベクトルの６つの行を有し、ベクトルｃは、６つの対応する定数の６つの要素を有する。
【００４５】
オブジェクト階層を構成するために、オブジェクト外皮Ｈ００ないしＨ１１が、図４Ｃに示されているように対にされる。オブジェクト外皮の各対は、包含外皮によって境界を定められる。たとえば、外皮Ｈ００およびＨ０１は、互いに対にされ、包含外皮Ｈ０によって境界を定められる。包含外皮Ｈ０には、効果的に、２つの構成要素外皮Ｈ００およびＨ０１が含まれる。同様に、オブジェクト外皮Ｈ１０およびＨ１１は、互いに対にされ、包含外皮Ｈ１によって境界を定められる。さらに、包含外皮Ｈ０およびＨ１のそれぞれについて１つの、２つの親ノードが、オブジェクト階層内で生成される。説明を簡単にするために、親ノードには、対応する包含外皮と共通のラベルをつける。したがって、親ノードＨ０は、その子ノードＨ００およびＨ０１を指し、親ノードＨ１は、その子ノードＨ１０およびＨ１１を指す。各親ノードには、対応する包含外皮の特徴を表すｃベクトルが含まれる。
【００４６】
包含外皮Ｈ０およびＨ１を、第１次包含外皮と称する場合がある。というのは、これらが、元のオブジェクト外皮に対する最初のペアリング動作の結果だからである。第２のペアリング動作を、第１次包含外皮に適用して、第２次包含外皮を得る。各第２次包含外皮には、効果的に、２つの第１次外皮が含まれる。第２次包含外皮のそれぞれについて、オブジェクト階層内で親ノードを生成する。この親ノードは、対応する第２次包含外皮と同一の親子関係を反映する。たとえば、図４Ｄで、第２次包含外皮Ｈには、効果的に、第１次包含外皮Ｈ０およびＨ１が含まれる。したがって、オブジェクト階層の親ノードＨは、子ノードＨ０およびＨ１を指す。親ノードＨには、包含外皮Ｈの特徴を表すベクトルｃが格納される。図４Ａないし４Ｄに示した例では、元のオブジェクト集合に４つのオブジェクトだけが含まれるので、２つのペアリング動作の後にオブジェクト階層が完成する。
【００４７】
一般に、一連のペアリング動作が実行される。各段階では、包含外皮およびオブジェクト階層の対応するノードの高次の組が生成される。各ノードには、対応する包含外皮を記述するベクトルｃが含まれる。この処理の終りに、オブジェクト階層には、単一のルート・ノードを有する２進木が含まれる。ルート・ノードは、すべてのオリジナル・オブジェクト外皮を含むすべての次数のすべてのサブ外皮を含む総包含外皮に対応する。オブジェクト階層は、境界を定める外皮の階層を含むので、外皮階層とも呼ばれる。好ましい実施形態では、ペアリング動作は、近接に基づく、すなわち、オブジェクト（および同一次の外皮）は近接に基づいて対にされる。近接に基づくペアリングは、より効率的な可視オブジェクト判定アルゴリズムをもたらす。この包含外皮の木は、シーン全体の、計算的に効率的な階層表現をもたらす。たとえば、コーンが、あるノードの包含外皮から完全に外れる時には、そのノードの子孫のどれも検査する必要がない。
【００４８】
境界を定める外皮（すなわち包含外皮）は、オブジェクトを簡略化し、近似するという目的のために働く。包含外皮のどの階層も、原則として機能する。しかし、共通の法線ベクトルの組に基づく外皮の階層が、計算的に特に効率的である。共通の法線ベクトルの組に基づく外皮の集合を、本明細書では、固定方向集合または共通生成された集合と称する。上で述べたように、多面体の外皮は、境界を定める連立線形不等式｛ｘ：Ｎｘ≦ｃ｝によって記述され、ここで、行列Ｎの行は、法線ベクトルの組であり、ベクトルｃの要素は、多面体の対応する面を得るために法線ベクトルのそれぞれに沿って移動する距離を定義する。外皮の固定方向集合では、法線行列Ｎが、集合内のすべての外皮に共通であり、ベクトルｃは、集合内の外皮のそれぞれに一意である。サブ外皮の集合を与えられて包含外皮の係数ベクトルｃを計算するという問題は、共通の法線ベクトルの組が使用される時には非常に単純になる。さらに、外皮階層のノードは、有利なことに、法線行列Ｎをノード内に格納する必要がないので、消費するメモリ空間を減らすことができる。本発明の好ましい実施形態では、外皮階層に、外皮の固定方向集合が含まれる。
【００４９】
第１の実施形態では、３つの正の軸方向および３つの負の軸方向に向けられた６つの法線ベクトルを使用して、座標平面に平行な面を有する長方形の箱に類似した形状の外皮の固定方向階層を生成する。これらの軸に整列された境界を定める外皮は、優れたローカル計算特性を有する単純な表現をもたらす。軸に整列された２つの外皮の平行移動または比較は簡単である。しかし、軸に整列された外皮によってもたらされる近似は、粗くなる傾向があり、しばしば、よりグローバルなレベルでコストが高いことがわかっている。
【００５０】
第２の実施形態では、立方体の頂点に向けられた８つの法線ベクトルを使用して、８つの面を有する外皮の階層を生成する。たとえば、８つのベクトル（±１、±１、±１）を使用して、８つの面を有する外皮を生成することができる。８面体は、この外皮ファミリの特殊な例である。
【００５１】
第３の実施形態では、１４個の法線ベクトルすなわち、長方形の箱を生成する６つの法線と、８面の箱を生成する８つの法線を使用して、１４面を有する外皮の外皮階層を生成する。これらの１４面を有する外皮は、頂点を切り落とされた長方形の箱として記述することができる。法線ベクトルの数、したがって面の数が増えるにつれて、基礎となるオブジェクトに対する外皮の近似の精度が高まることに留意されたい。
【００５２】
第４の実施形態では、上で説明した１４個の法線にさらに１２個の法線を追加して、２６個の法線ベクトルの組を得る。１２個の追加の法線は、すでに切り落とされた頂点に加えて、長方形の箱の１２個の辺を切り落とすように働く。これは、２６面を有する外皮をもたらす。たとえば、１２個の法線（±１、±１、０）、（±１、０、±１）、および（０、±１、±１）を、追加のベクトルとして使用することができる。
【００５３】
上で示した例では、外皮は、２進木を生成するために再帰的に対にグループ化される。しかし、他の実施形態では、外皮を、２より大きいサイズＧのグループに一緒にグループ化する。１実施形態では、グループのサイズが、グループによって異なる。これは、不均一なオブジェクト密度を有するシーンに特に有利である。たとえば、大量の小さいオブジェクトが１シーンに密集している場合、これらを単一のグループに含める、すなわち、単一の包含外皮を用いてこれらの境界を定めることが有利になる可能性がある。大きいオブジェクトは、要素数の少ないグループに集めることができる。
【００５４】
上の説明では、オブジェクトおよびクラスタの境界としての多面体外皮の使用に焦点を合わせたが、任意の種類の境界表面を使用することができ、それによって、本明細書で境界階層と称する境界の階層を生成することができることに留意されたい。境界階層の各ノードは、オブジェクトまたはクラスタに対応し、そのオブジェクトまたはクラスタの対応する境界の特徴を表すパラメータが格納される。たとえば、正方形表面などの多項式表面を使用して、オブジェクトまたはクラスタの境界を生成することができる。球および楕円体が、多項式表面の例である。
【００５５】
可視オブジェクト判定でのコーン
上で述べた境界階層（たとえば外皮階層）に加えて、本発明は、空間的コーンの階層を利用する。ビュー切頭体を表す初期コーンを、再帰的に副分割してサブコーンの階層にする。その後、木の対（オブジェクト木とコーン木）を介する同時二重再帰を実行して、可視オブジェクトの組をすばやく判定する。このコーンに基づく方法は、レイキャスティングに基づく従来技術の方法に対する実質的な計算上の利得をもたらす。これは、部分的には、レイキャスティング方法が、コーンと同等の領域をカバーするために複数の関連しない可視性照会を必要とするという事実に起因する。
【００５６】
コーンによって、光線とは異なる形で空間的連続体が離散化される。１点からの可能なすべての光線の同時伝播と、その結果として続く球形の波面を考慮されたい。各光線が最初に出会うオブジェクトは可視である。考慮が、コーンを形成する光線だけに制限される場合、同一の観察がやはりあてはまる。コーンの波面が最初に出会うオブジェクトは可視である。次に、ビュー切頭体がある個数のコーンに区分される場合、視点から可視のオブジェクトは、コーンの解像度まで判定することができる。
【００５７】
図６に、２次元環境での２次元コーンＣを示す。コーンＣは、光線Ｒ１およびＲ２の内側（およびこれらの光線を含む）領域によって定義される。コーンＣは、複数のサブコーンに区分される。この環境空間に、２次元オブジェクトの集合を持ち込む。波面は、サブコーンのそれぞれの中を伝播する。各波面は、オブジェクトとの最初の相互作用の際に終了する。サブコーンのうちの３つすなわちサブコーンＣ１、Ｃ２、およびＣ３が特に強調されている。サブコーンＣ１は、２つのオブジェクトすなわち、楕円形のオブジェクトおよび星型のオブジェクトと相互作用する。しかし、サブコーンＣ１内を伝播する波面は、定義によって、オブジェクトとの最初の相互作用の際に終了する。波面は、最初に楕円形と相互作用するので、この波面は、楕円形で終了し、星型のオブジェクトは、このサブコーンに関して不可視と定義される。より高い解像度が望まれる場合、サブコーンＣ１を、より小さいコーンの組にさらに区分することができる。これらのより小さいコーンのうちのいくつかは、楕円で終了するが、それ以外のコーンは、星型のオブジェクトで終了するはずである。サブコーンＣ２は、１つのオブジェクトすなわちオブジェクトＢのみと相互作用する。サブコーンＣ２を伝播する波面は、オブジェクトＢとの最初の接触の点で終了する。
【００５８】
コーンに基づくオブジェクト可視性照会（波面伝播の概念に基づいてモデル化される）は、本来、空間的計算であることに留意されたい。したがって、サブコーンＣ３に関するオブジェクト可視性照会では、サブコーンＣ３の内部に完全におさまる場合であっても、小さいオブジェクトＡが検出される。この可視性照会計算は、後で詳細に説明する。
【００５９】
多面コーン
好ましい実施形態で使用される空間的コーンは、多面コーンである。一般的な多面コーンは、多角形の横断面を有する。図７に、多面コーンの２つの例を示す。第１の多面コーンＰＣ１は、長方形の横断面を有し、第２の多面コーンＰＣ２は、三角形の横断面を有する。ビュー切頭体は、コーンＰＣ１のように長方形断面を有するコーンである。多面コーンは、同次線形不等式によって定義される。法線ベクトルｎに対して、ベクトル引数ｘを伴う式ｎ・ｘ＝０によって、原点を通り、法線ベクトルｎに垂直な平面が定義される。この平面は、空間を２つの半空間に分割する。線形不等式ｎ・ｘ＜０によって、法線ベクトルが外を指す方向の半空間が定義される。図８Ａに、２次元の例を示す。図からわかるように、式ｎ・ｘ＝０によって、法線ｎに垂直な点の組（ベクトルと解釈される）が指定される。この垂直な直線Ｌが、平面を２つの半平面に分割する。不等式ｎ・ｘ＜０によって定義される半平面を、斜線部分によって示す。法線ベクトルｎが、この半平面の外を指していることを観察されたい。
【００６０】
多面コーンは、複数の半空間の共通部分によって構成される。たとえば、図７の中実のコーンＰＣ２は、３つの半空間の共通部分である。同様に、中実のコーンＰＣ１は、４つの半空間の共通部分である。図８Ｂに、コーン区域を生成するための交わる半平面の２次元の例を示す。２つの法線ベクトルｎ１およびｎ２によって、それぞれ垂直の直線Ｌ１およびＬ２が定義される。不等式ｎ１・ｘ＜０によって、直線Ｌ１の南西（すなわち左下）の半平面が指定される。不等式ｎ２・ｘ＜０によって、直線Ｌ２の右の半平面が定義される。同時連立不等式ｎ１・ｘ＜０およびｎ２・ｘ＜０の解が、斜線で示された共通領域である。この連立不等式は、行列式Ｓｘ≦０によって要約することができ、ここで、行列Ｓの行は、法線ベクトルである。この議論から、図７の中実のコーンＰＣ１が、４つの法線ベクトルによって決定されることが観察される。法線行列Ｓは、４行（４つの法線ベクトルの）と、環境空間の次元に対応する３つの列を有するはずである。
【００６１】
したがって、原点から発する多面コーンは、連立線形不等式Ｓｘ≦０を満足する点の組として定義される［原点を視点と仮定することによって一般性は失われない］。この定義によれば、半空間、平面、光線、および原点自体を、多面コーンとみることができる。さらに、空間全体を多面コーンとみなす、すなわち、空の行列Ｓによって定義されるコーンとみることができる。
【００６２】
距離の測定
波伝播に関する議論に鑑みて、特定の視点からの、オブジェクト、外皮、または境界の距離は、視点からオブジェクト、外皮、または境界までの最小距離と定義される。したがって、視点が原点にあると仮定すると、視点からのオブジェクト、外皮、または境界Ｘの距離は、次式によって定義される。
【数１】
2004513403.tif 000003
【００６３】
ここで、‖ｘ‖は、ベクトルｘのノルムである。オブジェクト、外皮、または境界Ｘが空の時には、距離は正の無限大であるものとする。
【００６４】
どのベクトルのノルムでも、距離の測定のために選択することができる。１実施形態では、ユークリッド・ノルムが、距離測定のために選択される。ユークリッド・ノルムは、球形の波面をもたらす。どのような波面形状でも、ゆるやかな「星型」判断基準すなわち、波面の境界全体が、原点から見られる時に遮られてはならないという条件を満足する限り、使用することができる。すべての凸波面が、この条件を満たし、多数の非凸波面もこの条件を満足する。一般に、ノルムの等位曲線が波面形状として推奨される。計算の観点からは、Ｌ２ノルムによって与えられる球の波面形状、Ｌ１によって与えられる区分的線形波面形状、およびＬ∞ノルムが、可視性検出のよい選択を提供する。驚くべきことではないが、このようなノルムの区分的線形近似、たとえばＬ２ノルムに対する近似も、良好に動作する。このような近似を、図６に示す。
【００６５】
コーンと可視性
オブジェクトの大きい組の中に配置された視点からは、その視点に最も近い点（あるオブジェクト上の）が少なくとも１つ存在する。その点（または点の組）は、視点に最も近いので、その点（または点の組）のビューを遮るものはない。これは、最も近い点（１つまたは複数）を含むオブジェクト（１つまたは複数）が、少なくとも部分的に可視であることを暗示する。
【００６６】
ここで、視点としての原点から発する任意のコーンＫを考慮されたい。遮られない可視性の議論は、すべての距離測定がコーン内に含まれる点に制限される場合であっても成り立つ。オブジェクト、外皮、または境界ＸのコーンＫへの相対距離を、次式によって定義する。
【数２】
2004513403.tif 000004
【００６７】
距離ｆＫを、シーン内のオブジェクトごとに計算する場合、最も近いオブジェクトすなわち、最小の距離値になるオブジェクトが、コーンＫに関して可視である。実際、オブジェクトＸが可視になるのは、（ａ）ｆＫ（Ｘ）が有限であり、（ｂ）オブジェクトの組のすべてのオブジェクトＹに対してｆＫ（Ｘ）≦ｆＫ（Ｙ）が成り立つコーンＫが存在する場合に限られる。
【００６８】
光線は、視点から発し、各画素の中央を通過する退化円コーン曲線とみることができることに留意されたい。各光線に沿った最も近いオブジェクトが、可視であり、したがって、対応する画素の値を決定する。同様に、視点から発し、各画素を含むコーンを構成することが可能である。たとえば、三角形の横断面を有する複数のコーンは、画素の面積をきれいにカバーすることができる。各コーン内の最も近いオブジェクトが、可視であり、対応する画素の値を生成する。
【００６９】
上で述べたように、従来技術の光線に基づく方法は、光線サンプルの解像度までのオブジェクトだけを検出することができる。小さい可視オブジェクトまたは大きいオブジェクトの小さい部分は、不十分な光線密度に起因して完全に見逃される可能性がある。対照的に、コーンは、完全に空間を満たすことができる。したがって、本発明のコーンに基づく方法は、有利なことに、等しい角度分解能を有する光線に基づく方法が見逃すはずの小さい可視オブジェクトまたはオブジェクトの部分を検出することができる。
【００７０】
一般化された離隔測定
可視性探索手順を実行するためには、オブジェクト、境界、または外皮の、コーンに関する離隔（または近接）の程度を測定する方法を有する必要がある。上で定義したベクトル・ノルムの最小化に基づく方法のほかに、さまざまなそのような方法が存在する。上でほのめかしたように、組ＸとコーンＫの間の離隔の程度を示す測定値は、波面をコーンの内部でコーンの頂点から伝播させ、組Ｘとの内部波面の最初の相互作用の半径を観察することによって得ることができる。上で述べたように、波面は、ゆるやかな「星型」条件を満足しなければならない、すなわち、波面の境界全体がコーンの頂点から可視でなければならない
【００７１】
１実施形態では、測定値は、組ＸとコーンＫの間の離隔のペナルティを計算することによって得られる。離隔のペナルティは、コーンＫの頂点と、コーンＫおよび組Ｘの共通部分内の点との間の離隔距離の増加関数を最小化することによって評価される。たとえば、ベクトル・ノルムの正のべきが、そのような増加関数を与える。
【００７２】
もう１つの実施形態では、測定値は、組ＸとコーンＫの間の近接の価値を計算することによって得られる。離隔の価値は、コーンＫの頂点と、コーンＫおよび組Ｘの共通部分内の点との間の離隔距離の減少関数を最大化することによって評価される。たとえば、ベクトル・ノルムの負のべきが、そのような減少関数を与える。
【００７３】
コーン階層
本発明の可視性判定方法は、上で説明した外皮の階層に加えて、コーンの階層の使用に頼っている。多面コーンのクラスは、コーン階層の生成に特によく適している。多面コーンは、１つまたは複数の分離平面を挿入することによって、自然に多面サブコーンに分解される。コーンを階層構造に入れ子にする能力によって、オブジェクト可視性の非常にすばやい検査が可能になる。１例として、共通の面を共有する２つの隣接するコーンを検討されたい。この２つのコーンの合併をとることによって、新しい合成コーンが生成される。この合成コーンは、その子をきれいに含み、したがって、その２つの子と正確に同一の空間を照会するのに使用することができる。言い換えると、子コーンは、互いに内部の点を共有せず、空の空間を残さずに親を完全に満たす。
【００７４】
通常の表示およびそれに関連するビュー切頭体は、長方形の横断面を有する。この長方形の横断面をテセレートしてサブコーンの系を生成する可能性は膨大な数が存在する。たとえば、長方形は、自然に４つの長方形の横断面、または２つの三角形の横断面に分解される。この例では、規則的な構成要素を使用する分解を示したが、不規則な構成要素も使用することができる。
【００７５】
図９Ａないし９Ｃに、初期ビュー切頭体Ｃの階層的分解を示す。図９Ａに、ビュー切頭体の長方形の横断面と、三角形の横断面を有する２つのコーンすなわち、コーンＣ０およびＣ１への二分割を示す。ビュー切頭体Ｃは、コーン木のルート・ノードに対応する。コーンおよびそれに対応するコーン木内のノードには、説明を簡単にするために同一のラベルを付す。コーン木の各ノードには、対応するコーンを生成する法線ベクトルの行列Ｓが格納される。ルート・ノードは、コーンＣ０およびＣ１に対応する２つの子ノードを指す。図９Ｂに、第２の分解段階を示す。コーンＣ０およびＣ１のそれぞれが、２つのサブコーン（やはり三角形の横断面）に二分割される。コーンＣ０は、２つのサブコーンＣ００およびＣ０１に分解される。同様に、コーンＣ１は、２つのサブコーンＣ１０およびＣ１１に二分割される。コーン木にノードを追加して、この分解の構造を反映する。コーン木内のノードの親子関係は、空間内のめいめいのコーンのスーパセット／サブセット関係を反映する。図９Ｃに、１実施形態による連続するコーンの二分割のパターンを示す。階層内の各コーンは、平面を二分割することによって２つのサブコーンに分解することができる。図９Ｃは、コーンＣ０、Ｃ１０、Ｃ１１０、およびＣ１１１０などを生成する、複数の連続する下ってゆく二分割を示す。初期コーンＣ（すなわちビュー切頭体）を、任意の所望の解像度まで分解することができる。１実施形態では、ニ分割は、結果のコーンが画素のある分数、たとえば１／２画素をさえぎる時に終了する。コーン木の対応する終端ノードを、リーフと呼ぶ。結果のリーフ・コーンが、（ａ）Ｎが正の整数であるものとして画素の１／Ｎなどの部分か、（ｂ）１つまたは複数の画素を含む面積に相対する面積を遮る時にニ分割が終了する代替実施形態が企図されている。
【００７６】
図９Ａないし９Ｃに示した三角形階層分解は、多数の有用な特性を有する。元の三角コーンを再帰的なニ分割に基づいて分解することによって、任意のデプスのコーンの２進木が生成される。三ピラミッドは、最小の数の面を有するので、計算的に魅力的である。最後に、三ピラミッドは、単位立方体（または単位球）をテセレートすることもできる。したがって、視点を囲む全空間の階層コーン表現を作成することが可能である。
【００７７】
コーン階層を生成するために、どのようなコーン分解戦略でも使用することができることに留意されたい。第２の実施形態では、ビュー切頭体が、４つの類似する四角コーンに分解され、サブコーンのそれぞれが、４つの四角サブコーンに分解され、以下同様である。これは、４分岐の枝を有するコーン木をもたらす。
【００７８】
可視オブジェクトの組の発見
外皮階層およびコーン階層を構成した後に、可視オブジェクトの組を、現在の視点から計算する。１実施形態では、可視オブジェクトの組は、一連の視点および視線方向について繰り返し再計算される。連続する視点および視線方向は、ユーザによって、マウス、ジョイスティック、キーボード、トラックボール、またはこれらの組合せなどの入力装置を介して指定される可能性がある。本発明の可視オブジェクト判定方法は、外皮木とコーン木の同時検索として編成される。この探索処理には、コーン−外皮照会の再帰的実行が含まれる。コーン・ノードＫおよび外皮ノードＨを与えられた場合、コーンＫおよび外皮Ｈに対するコーン−外皮照会では、コーンＫおよびその子孫コーンに関する外皮Ｈおよびその子孫外皮の可視性を調査する。この検索処理は、オーダーｌｏｇ　Ｍの計算的複雑さを有し、このＭは、コーン・ノードの個数に外皮ノードの個数を乗じた値に等しい。さらに、多数のコーン−外皮照会を、並列に行うことができ、可視オブジェクトの組の構成に複数のプロセッサを積極的に使用することができる。
【００７９】
シーンの表示
独立にまたはやはり並列に、現在の視点からの可視オブジェクトの組を、１つまたは複数のディスプレイにレンダリングすることができる。レンダリングを並列に行えるのは、可視オブジェクトの組が、ウォークスルー環境でのフレームの間でかなり一定になるからである。したがって、前の可視オブジェクトの組が、現在の可視オブジェクトの組のよい近似になる。
【００８０】
可視オブジェクトの組の管理
ビジュアライゼーション・ソフトウェアは、可視オブジェクトの組を管理しなければならない。時と共に、エンドユーザがモデルを通ってナビゲーションするにつれて、可視オブジェクトの組にオブジェクトを挿入するだけでは、可視オブジェクトの組に含まれるオブジェクトが多すぎる結果になるはずである。したがって、よいレンダリング性能を保証するために、ビジュアライゼーション処理では、オブジェクトがもはや組に属さなくなった時またはその後すぐに、可視オブジェクトの組からオブジェクトを除去しなければならない。オブジェクト除去に対するさまざまな解決策が可能である。１つの解決策は、オブジェクトのエージングに基づく。システムは、指定された再描画サイクル数の間にコーン照会によって再発見されなかったオブジェクトを、可視オブジェクトの組から除去する。
【００８１】
コーンを使用する可視性の計算
かなりの計算の活用が、外皮の階層木と共にコーンの階層木を再帰的に検索することによってもたらされる。コーンのグループ全体を、単一の照会で外皮のグループ全体に対してテストすることができる。たとえば、親コーンが親外皮と交差しない場合、親コーンのすべての子が、親外皮のどの子とも交差できないことは明白である。そのような状況では、親外皮とその子孫のすべてを、その親コーンに関するその後の可視性検討から除去することができる。
【００８２】
可視性検索アルゴリズム
好ましい実施形態では、本発明の可視性探索アルゴリズムは、メモリ１０６に記憶された可視性検索プログラムで実現される。したがって、以下では、可視性検索プログラムと可視性検索アルゴリズムの用語を交換可能な形で使用する。可視性検索プログラムは、２つの木（オブジェクト木とコーン木）の再帰検索を実行して、コーン木のリーフ・コーンのそれぞれに可視オブジェクトを割り当てる。ホスト・プロセッサ１０２が可視性検索プログラムを実行する。代替実施形態では、可視性検索プログラムは、グラフィックス・アクセラレータ１１２内に含まれるプロセッサ上で実行される。
【００８３】
２つの木の再帰検索は、検索空間の積極的な枝刈りの複数の機会を提供する。検索の中心にあるのが、上で定義したオブジェクト−コーン距離測定である、すなわち、コーンＫおよびオブジェクト（または外皮）Ｘに対して、オブジェクト−コーン距離は、次式によって定義される。
【数３】
2004513403.tif 000005
【００８４】
コーンとオブジェクト外皮が、制約式すなわち３次元空間内の平面によって定義されるので、この最小化は一般的な非線形計画法問題であることに留意されたい。ベクトル・ノルム‖ｘ‖がＬ１ノルム（すなわち、ベクトルｘの成分の絶対値の和として定義されるノルム）である場合には、非線形計画法問題が線形計画法問題になる。ベクトル・ノルム‖ｘ‖が、ユークリッド・ノルムである場合には、非線形計画法問題が、二次計画法問題になる。オブジェクトの集合に対して、最小の距離ｆＫ（Ｘ）となったオブジェクトＸが、コーンの視点に最も近く、したがって、少なくとも部分的に可視でなければならない。
【００８５】
再帰検索は、外皮木のルートＨおよびコーン木のルートＣから始まる（図４および図９を参照）。外皮木の各ノードは、その子孫ノードのすべての外皮を含む境界外皮を指定することを想起されたい。当初は、ルートコーンとルート外皮の間の距離を計算する。その距離が無限大の場合には、コーン階層のすべてのコーンが、外皮階層のどの外皮とも交差せず、可視オブジェクトは存在しない。距離が有限の場合には、さらに検索する必要がある。どちらかの木を、この時点で細分することができる。好ましい実施形態では、両方の木を、事前に定義された順序で細分する。
【００８６】
枝刈り機構は、複数の基本要素の上に構築される。距離測定関数は、コーンＫの視点からの外皮Ｘの距離ｆＫ（Ｘ）を計算する。言い換えると、この関数は、外皮Ｘへのコーンに制限された距離を決定する。好ましい実施形態では、距離測定関数の評価に関連する最小化が、関連する線形計画法問題を解くことによって実施される。
【００８７】
検索処理を簡単にするために、各リーフ・コーンすなわち、コーン木の各終端ノードに、最も近い既知のオブジェクト−外皮の距離を表す長さ値を割り当てる。したがって、この長さ値を可視性距離と称する場合がある。リーフ・コーンの可視性距離は、非増加的すなわち、より近いオブジェクト（すなわちオブジェクト外皮）が検索処理で発見される際に減少する。すべてのリーフ・コーンの可視性距離は、正の無限大に初期化される［オブジェクト−外皮は、１つのオブジェクトの境界を直接に定める外皮である。したがって、オブジェクト−外皮は、外皮木の終端ノードである］。可視性距離値のほかに、各リーフ・コーン・ノードには、現在可視のオブジェクトに関する記憶域が割り当てられる。このオブジェクト属性は、シーン・コンテキストに応じてＮＯ＿ＯＢＪＥＣＴ（オブジェクトなし）またはＢＡＣＫＧＲＯＵＮＤ（背景）に初期化される。
【００８８】
さらに、各非リーフ・コーンすなわち、最終細分化レベル以外のレベルにあるコーンのそれぞれに、そのサブコーンの最大値に等しい長さ値を割り当てる。または、これと同等であるが、非リーフ・コーンの長さ値は、そのリーフ・コーンの子孫の最大値に等しい。これらの長さ値を可視性距離値とも称する。すべての非リーフ・コーンの可視性距離値も、正の無限大に初期化される（リーフ・コーンの初期化との一貫性を有する）。所与の非リーフ・コーンＫおよび外皮Ｈが、コーン−オブジェクト距離ｆＫ（Ｘ）となると仮定する。この距離ｆＫ（Ｘ）が、コーンＫの可視性距離値より大きい場合には、コーンＫのリーフ・コーン子孫のすべてが、すでに、外皮Ｈより近い既知のオブジェクトを有する。したがって、コーンＫおよびその子孫に対して外皮Ｈを検索することによって得られる利益はない。逆に、外皮Ｈが、コーンＫの可視性距離値より小さい、コーンＫからの距離ｆＫ（Ｘ）になる場合には、外皮Ｈに、コーンＫのいくつかのリーフ・コーン子孫の可視性距離を厳密に減少させるオブジェクトが含まれる可能性がある。したがって、外皮Ｈとその子孫を、コーンＫおよびその子孫に対して検索しなければならない。
【００８９】
次のコード辺は、検索処理の始めを示す。変数ｈｕｌｌＴｒｅｅおよびｃｏｎｅＴｒｅｅは、それぞれ外皮木のルート・ノードおよびコーン木のルート・ノードを指す。
2004513403.tif 000006
ＤＩＳＴ関数は、ルート外皮とルートコーンの間の距離を評価する。この距離が正の無限大より小さい場合には、引数としてルート外皮、ルートコーン、およびそれらの外皮−コーン距離を用いて、関数ｆｉｎｄＶｉｓｉｂｌｅを呼び出す。関数ｆｉｎｄＶｉｓｉｂｌｅは、２つの木の再帰検索を実行する。
【００９０】
図１０Ａないし１０Ｃに、ｆｉｎｄＶｉｓｉｂｌｅ関数（短縮形ＦＶによっても参照される）の１実施形態を示す。ｆｉｎｄＶｉｓｉｂｌｅ関数のソース・コード実施形態については、付録を参照されたい。ｆｉｎｄＶｉｓｉｂｌｅ関数は、次の関数プロトタイプによって示されるように、呼出し側ルーチンから複数の入力変数を受け取る。
ｆｉｎｄＶｉｓｉｂｌｅ（Ｈ，Ｃ，ｄ）
ここで、Ｈは、コーン・ノードＣに対して探索する外皮ノードである。値ｄは、コーンＣと外皮Ｈの間のコーン−外皮の距離を表す。ステップ３００で、ｆｉｎｄＶｉｓｉｂｌｅ関数は、コーンＣと外皮Ｈが、両方ともリーフ・ノードである、すなわち、それぞれの木の終端ノードであるかどうかを判定する。そうである場合には、リーフ・コーンＣの可視性距離値ｄｃに、オブジェクト外皮Ｈまでの現在の距離をセットする。さらに、リーフ・コーンＣのオブジェクト属性に、外皮Ｈの値を割り当てる。その後、制御を呼出し側ルーチンに返す。
【００９１】
外皮ＨとコーンＣの両方がリーフではない場合には、ステップ３０２を実行する。ステップ３０２では、ｆｉｎｄＶｉｓｉｂｌｅ関数がコーンＣ自体がコーン木のリーフ・ノードであるかどうかを判定する。そうである場合には、ステップ３０４ないし３１０を実行する。ステップ３０４では、外皮Ｈの子を調査する、すなわち、サブ外皮Ｈ０およびＨ１へのコーンＣの距離を比較する［外皮Ｈの子を総称的にＨ０およびＨ１と呼称する］。サブ外皮Ｈ０への距離がサブ外皮Ｈ１への距離より小さい場合には、ステップ３０６および３０８を実行する。そうでない場合には、ステップ３１０を実行する。ステップ３０４は、どちらのサブ外皮が最初にコーンＣと相互作用する機会を与えられるかを判定するために実行される。本発明の好ましい実施形態では、最も近いサブ外皮を最初に検索する。
【００９２】
ステップ３０６で、ｆｉｎｄＶｉｓｉｂｌｅ関数は、コーンＣからのサブ外皮Ｈ０のコーン−外皮の距離が、コーンＣの可視性距離値ｄＣより小さいかどうかを判定する。そうである場合には、コーンＣに対してサブ外皮Ｈ０を検索するために、ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数をもう一度呼び出す。コーンＣとサブ外皮Ｈ０の間のコーン−外皮の距離は、関数呼び出しの距離引数として供給される。サブ外皮Ｈ０への距離が、現在の可視性距離より小さくない場合には、ステップ３０８を実行する。
【００９３】
ステップ３０８では、ｆｉｎｄＶｉｓｉｂｌｅ関数は、コーンＣからのサブ外皮Ｈ１のコーン−外皮の距離が、コーンＣの可視性距離値より小さいかどうかを判定する。小さい場合には、コーンＣに対してサブ外皮Ｈ１を検索するために、ｆｉｎｄＶｉｓｉｂｌｅ関数をもう一度呼び出す。コーンＣとサブ外皮Ｈ１の間のコーン−外皮の距離は、関数呼び出しの距離引数として供給される。サブ外皮Ｈ１への距離が、現在の可視性距離より小さくない場合には、プログラムの制御が、呼出し側プログラムに返される。
【００９４】
ステップ３０６の関数ｆｉｎｄＶｉｓｉｂｌｅの呼び出しが、コーンＣの可視性距離値の減少を引き起こす可能性があることに留意されたい。したがって、コーンＣの可視性距離値は、実際には、ステップ３０８でテストされる時に、ステップ３０６でテストされた時よりも小さくなっている場合がある。これによって、コーンＣにより近いサブ外皮を判定するためにステップ３０４で実行されるテストの重要性が強調される。より近い外皮が、まず検索され、より遠いサブ外皮の先に立つことを許可される。言い換えると、より近いサブ外皮を検索した後には、より遠いサブ外皮を検索する必要がない可能性がある。したがって、サブ外皮に関する距離を条件とする検索順序によって、可視性検索アルゴリズムの効率が改善される。
【００９５】
ステップ３１０では、サブ外皮Ｈ０が、サブ外皮Ｈ１の対応する距離より小さくない、コーンＣからのコーン−外皮の距離となることのステップ３０４での判定に応答して、逆の順序でサブ外皮を検索する。やはり、より近いサブ外皮Ｈ１が、先に検索され、より遠いサブ外皮Ｈ０の検索の先に立つことを許可される。
【００９６】
ステップ３０２で、コーンＣがリーフではないと判定された場合には、ステップ３２０を実行する（図１０Ｂ参照）。ステップ３２０で、ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数は、外皮ノードＨが、外皮階層のリーフ・ノードすなわちオブジェクト外皮であるかどうかを判定する。そうである場合には、ステップ３２２ないし３２６で、オブジェクト外皮Ｈに関してコーンＣの子を探索する。ステップ３２２で、ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数は、外皮Ｈと子サブコーンＣ０の間のコーン−外皮の距離が、子サブコーンＣ０の可視性距離より小さいかどうかを判定する。そうである場合には、サブコーンＣ０に関して外皮Ｈを探索するために、ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数をもう一度呼び出す。したがって、外皮Ｈ、サブコーンＣ０、およびこれら２つの間のコーン−外皮の距離が、引数としてｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数に供給される。ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数からリターンした時に、制御がステップ３２４に渡される。ステップ３２２の不等式テストが失敗の場合にも、制御がステップ３２４に渡される。
【００９７】
ステップ３２４では、ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数は、サブコーンＣ１からの外皮Ｈのコーン−外皮の距離が、サブコーンＣ１の可視性距離値より小さいかどうかを判定する。そうである場合には、サブコーンＣ１に関して外皮Ｈを探索するために、ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数をもう一度呼び出す。したがって、外皮Ｈ、サブコーンＣ１、およびこれら２つの間のコーン−外皮の距離が、引数としてｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数に供給される。ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数からリターンした時に、制御がステップ３２６に渡される。ステップ３２４の不等式テストが失敗の場合にも、制御がステップ３２６に渡される。
【００９８】
サブコーンＣ０およびＣ１の可視性距離値は、それぞれステップ３２２またはステップ３２４で外皮Ｈとの相互作用によって減らされている可能性があるので、コーンＣの可視性距離値を更新しなければならない。したがって、ステップ３２６で、コーンＣの可視性距離値に、サブコーンＣ０およびＣ１の可視性距離値の最大値をセットする。ステップ３２６の後に、プログラムの制御は、呼出し側ルーチンに戻る。
【００９９】
ステップ３２０で、外皮ノードＨがリーフ・ノードではないと判定された場合、ステップ３３０を実行する（図１０Ｃ参照）。したがって、ステップ３３０および後続ステップでは、外皮ＨもコーンＣも、めいめいの階層内のリーフ・ノードではないと仮定することができる。ステップ３３２、３３４、３３５、および３３６では、テスト・ステップ３３０の結果を条件として、コーンＣ０に関して外皮Ｈの子を探索する。同様に、ステップ３４０では、テスト・ステップ３３８の結果を条件として、サブコーンＣ１に関して外皮Ｈの子を探索する。
【０１００】
ステップ３３０では、ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数は、外皮ＨとサブコーンＣ０の間のコーン−外皮の距離が、サブコーンＣ０の現在の可視性距離値より小さいかどうかを判定する。そうである場合には、ステップ３３２を実行する。ステップ３３２では、サブ外皮Ｈ０およびＨ１の、サブコーンＣ０からのコーン−外皮の距離を比較する。より近いサブ外皮に、サブコーンＣ０との最初の相互作用の機会が与えられる。したがって、サブコーンＣ０からのサブ外皮Ｈ０のコーン−外皮の距離がサブコーンＣ０からのサブ外皮Ｈ１のコーン−外皮の距離より小さい場合には、ステップ３３４を実行する。そうでない場合には、ステップ３３６を実行する。
【０１０１】
ステップ３３４では、ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数は、サブコーンＣ０からのサブ外皮Ｈ０のコーン−外皮の距離が、サブコーンＣ０の現在の可視性距離値より小さいかどうかを判定する。そうである場合には、サブコーンＣ０に対してサブ外皮Ｈ０を探索するためにｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数をもう一度呼び出す。したがって、サブ外皮Ｈ０、サブコーンＣ０、およびこれら２つの間のコーン−外皮の距離が、引数としてｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数に供給される。このｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数への呼び出しからリターンした時に、ステップ３３５を実行する。
【０１０２】
ステップ３３４で、サブコーンＣ０からのサブ外皮Ｈ０のコーン−外皮の距離が、サブコーンＣ０の可視性距離値より小さくないと判定された場合には、ステップ３３５を実行する。ステップ３３５では、ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数は、サブコーンＣ０からのサブ外皮Ｈ１のコーン−外皮の距離がサブコーンＣ０の可視性距離値より小さいかどうかを判定する。そうである場合には、サブコーンＣ０に関してサブ外皮Ｈ１を探索するために、ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数をもう一度呼び出す。したがって、サブ外皮Ｈ１、サブコーンＣ０、およびこれら２つの間のコーン−外皮の距離が、引数としてｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数に供給される。このｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数への呼び出しからリターンした時に、プログラムの制御が、ステップ３３８に渡される。さらに、ステップ３３５の不等式のテストが失敗した場合に、ステップ３３８が実行される。
【０１０３】
より近いサブ外皮Ｈ０が、コーンＣ０との最初の相互作用を許可されるので、これによって、サブコーンＣ０の可視性距離値が変更（すなわち減少）される可能性がある。したがって、より遠いサブ外皮Ｈ１は、サブ外皮Ｈ０の前の相互作用に起因して、ステップ３３５の不等式テストに合格することがより困難になる可能性がある。言い換えると、より近いサブ外皮Ｈ０との前の相互作用に鑑みて、サブコーンＣ０に関するサブ外皮Ｈ１の探索を実行する必要がない可能性があり、有利なことにスキップすることができる。したがって、可視性判定方法の検索効率が、不要なサブ外皮探索を避けることによって改善される。
【０１０４】
ステップ３３６は、サブコーンＣ０からのサブ外皮Ｈ０のコーン−外皮の距離がサブコーンＣ０からのサブ外皮Ｈ１のコーン−外皮の距離より少なくないというステップ３３２での判定に応答して実行される。言い換えると、ステップ３３６は、サブ外皮Ｈ０よりもサブ外皮Ｈ１がサブコーンＣ０に近い時に実行される。ステップ３３６には、ステップ３３４および３３５で実行されるものに類似する動作が含まれる。しかし、サブ外皮Ｈ１の条件検索は、サブ外皮Ｈ０の条件検索の前に実行される、すなわち、より近いサブ外皮が最初に検索される。ステップ３３６の後に、制御はステップ３３８に渡される。
【０１０５】
ステップ３３０で、コーンＣ０からの外皮Ｈのコーン−外皮の距離が、サブコーンＣ０の可視性距離より小さくないと判定される場合には、制御はステップ３３８に渡される。ステップ３３８では、ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数は、サブコーンＣ１からの外皮Ｈのコーン−外皮の距離が、サブコーンＣ１の可視性距離値より小さいかどうかを判定する。そうである場合には、ステップ３４０を実行する。ステップ３４０では、サブコーンＣ１に関するサブ外皮Ｈ０およびＨ１の条件探索を実行する。したがって、ステップ３４０には、サブコーンＣ０およびサブコーンＣ１の役割を交換した、ステップ３３２、３３４、３３５、および３３６で説明したものに類似する動作が含まれる。ステップ３４０の後に、ステップ３４２を実行する。さらに、ステップ３３８の不等式テストが失敗した場合に、ステップ３４２を実行する。
【０１０６】
ステップ３４２では、コーンＣの可視性距離値に、サブコーンＣ０およびＣ１の可視性距離値の最大値をセットする。ステップ３４２の後に、プログラムの制御は、呼出し側ルーチンに戻る。
【０１０７】
上で説明したように、コーン木の各コーンに割り当てられる可視性距離値は、そのサブコーンの子に割り当てられた可視性距離値の最大値に等しい。したがって、所与の外皮ノードが、コーンの現在の可視性距離値より大きいコーンへの距離となる場合には、外皮子孫のどれもが、コーンの子孫のいずれにとっても重要でないことが即座に明らかになる。所与の外皮ノードは、このコーンに関する限り、スキップすることができる。
【０１０８】
コーンの可視性距離値は、再帰でますます多くのオブジェクト／コーンのリーフ対をテストするにつれて減少する。近いオブジェクトが発見される際に、コーンの可視性距離値が減少し、見込みのない外皮ノードをスキップする確率が増加する。外皮木のリーフは、関連するオブジェクトの塊の境界を定め、また、そのオブジェクトの内容を近似する。したがって、再帰中にセットされるコーンの可視性距離値は、通常は、オブジェクトへの実際の距離ではないが、この距離のコンザバティブな近似である。コンザバティブな近似がアプリケーションでの使用に不適切な場合には、そのアプリケーションは、可視性距離値の正確な計算を用いることができる。
【０１０９】
可視性検索アルゴリズムの上の議論全体を通じて、コーン−外皮の離隔距離の計算に使用されるＤＩＳＴ関数が、所与のコーンの頂点と所与のコーンおよび所与の境界／外皮の共通部分の点の間の離隔距離の増加関数の最小化に基づくと仮定した。しかし、ＤＩＳＴ関数は、所与のコーンと所与の境界／外皮の間の近接の価値を計算するようにプログラミングすることができることに留意されたい。結果の価値の値は、距離関数の通常の振る舞いとは逆に、近接の増加に伴って増加し、離隔の増加に伴って減少する。この場合、可視性検索アルゴリズムは、コーンＫと境界／外皮Ｈの間の離隔の価値値が、コーンＫに関連する現在の価値値より大きい場合に限って、コーンＫに対して境界／外皮Ｈの検索を実行する。さらに、コーンＫのサブコーンの検索が完了した後に、コーンＫに関連する価値値をそのサブコーン子の価値値の最小値に等しくなるように更新する。
【０１１０】
一般に、ＤＩＳＴ関数は、コーンＫの頂点とコーンＫおよび境界／外皮Ｈの共通部分の点との間の離隔の単調（増加または減少）関数の極値（すなわち最大値または最小値）を計算することによって、離隔のコーン−外皮の測定値を決定する。境界／外皮Ｈに対するコーンＫの検索は、コーンＫに割り当てられた測定値に関する不等式条件を満足する、コーンＫに関するコーン−外皮測定値を達成する境界／外皮Ｈを条件とする。不等式の意味すなわち未満または超は、ＤＩＳＴ関数で離隔の増分関数と減少関数のどちらを使用するかに依存する。
【０１１１】
上で説明した外皮階層およびコーン階層の検索は、再帰形式を前提とするが、どのような検索戦略でも使用することができることに留意されたい。１代替実施形態では、外皮階層またはコーン階層もしくはその両方を反復して検索する。このような力任せの解決策は、反復検索の実施に大量のプロセッサのアレイを使用可能である時に有利になるであろう。もう１つの実施形態では、外皮階層またはコーン階層もしくはその両方に対して、レベル順の探索を実行する。
【０１１２】
可視オブジェクトを表示する方法
グラフィックス環境で可視オブジェクトを表示する方法を、図１１の流れ図で説明する。ＣＰＵ１０２または任意選択としてグラフィックス・アクセラレータ１１２上で実行される可視性検索アルゴリズムは、表示画面８４での表示用の可視オブジェクトの組の判定を制御する。ステップ５０１で、メモリ１０６のオブジェクトの集合にアクセスする。ステップ５０２で、オブジェクトの集合から境界階層を構成する。境界階層の構成は、下で図１２に関連して詳細に説明する。ステップ５０３で、初期コーンを細分することによってコーン階層を構成する。コーン階層の構成の詳細については、図６ないし９に関する上の議論を参照されたい。１実施形態では、初期コーンは、空間全体である。第２の実施形態では、初期コーンは、ビュー切頭体およびビュー切頭体の回りの近傍を含む近傍に対応する。したがって、ビュー方位（すなわち向き）が変化し、その結果、新しいビュー切頭体が初期コーンの近傍内にとどまる場合には、コーン階層を再構成する必要がなくなる可能性があり、それによって計算帯域幅が節約される。コーン階層内の各コーンは、全く遮られない可視性に対応する測定値を割り振られる。
【０１１３】
ステップ５０４で、コーン階層および境界階層の検索を実行する。検索手順によって、コーン階層のリーフ・コーンのそれぞれの最も近いオブジェクトが判定される。いくつかのリーフ・コーンは、所与の集合内のどのオブジェクトとも相互作用しない場合があることに留意されたい。この場合、最も近いオブジェクトが、背景であると解釈することができる。
【０１１４】
検索手順で、コーン階層のルートコーンおよび境界階層のルート境界から始めて、コーン／境界対の条件探索を実行する。コーン階層の第１コーンおよび境界階層の第１境界を与えられた探索アルゴリズムは、ステップ５０４Ａで、第１コーンと第１境界の間の離隔の程度を示す第１測定値を判定する。
【０１１５】
ステップ５０４Ｂで、第１測定値を第１コーンに関連する測定値と比較する。第１測定値が、第１コーンに関連する測定値に関する不等式条件を満足する場合には、ステップ５０４Ｃに示されているように、第１コーンに関して第１境界を検索する。一般に、非リーフ・コーンに関連する測定値は、そのリーフ・コーンの子孫の測定値の最大値を反映し、リーフ・コーンに関連する測定値は、そのリーフ・コーンと最も近い既知のオブジェクトとの間の離隔の程度を示す。したがって、ステップ５０４Ｂの比較から、第１境界が、第１コーンのリーフ・コーン子孫のそれぞれの最も近い既知のオブジェクトより遠いことが示される場合には、第１コーンに関して第１境界を検索することによって利益を得ることはできない。ステップ５０４Ｂおよび５０４Ｃを一緒にして、条件検索と称する。したがって、第１境界と第１コーンが探索されるのは、第１境界が、第１コーンの少なくとも１つのリーフ子孫の最も近い既知のオブジェクトより近いという証拠がある場合に限られる。
【０１１６】
ステップ５０６で、コーン階層のコーンのサブセットに関する最も近いオブジェクトが、表示装置８４に表示される。好ましい実施形態では、コーンのサブセットに、コーン階層のリーフ・コーンが含まれる、すなわち、コーン階層の各リーフ・コーンの最も近いオブジェクトが、表示装置８４に表示される。可視のオブジェクトだけについてレンダリング計算を要求することによって、大量の処理帯域幅が節約される。リーフ・コーンに最も近いオブジェクトが、そのコーンの可視オブジェクトである。ステップ５０４で実行される可視性検索は、異なる視点または視線方向について繰り返し実行することができることに留意されたい。したがって、表示ステップ５０６は、有利なことに、ステップ５０４と並列に実行することができる。可視性検索５０４は、現在の視点／視線方向について実行されているが、これと同時に、前の可視性検査からの結果をステップ５０６で表示装置に表示することができる。
【０１１７】
１実施形態では、第１測定値に、第１コーンと第１境界の間の離隔のペナルティが含まれ、このペナルティは、第１コーンの頂点と、第１コーンと第１境界の共通部分の点との間の離隔距離の増加関数を最小化することによって決定される。この場合、ステップ５０４Ｂでは、小さい測定値がより近い近接を示すので、第１測定値が第１コーンに関連する測定値より小さいかどうかを判定する。言い換えると、ステップ５０４Ｂの不等式条件は、第１測定値が第１コーンに関連する測定値より小さい時に満足される。離隔距離の増加関数は、ベクトル・ノルムによって指定することができる。たとえば、式‖ｓ‖によって、離隔距離の増加関数が定義される。ここで、ｓは、第１コーンの頂点と、第１コーンおよび第１境界の共通部分の任意の点との間のベクトル差を表し、‖・‖は、ベクトル・ノルムを表す。ベクトル・ノルムの例には、Ｌ１ノルム、Ｌ２ノルム、Ｌ∞ノルムが含まれ、一般に、ｐが１から無限大までの両端を含む範囲の任意の実数であるものとして、Ｌｐノルムのすべてが含まれる。ベクトルのＬ１ノルムは、その成分の絶対値の和として定義される。ベクトルのＬ２ノルムは、ベクトル成分の自乗和の平方根として定義される。ベクトルのＬ∞ノルムは、ベクトル成分の絶対値の最大値として定義される。
【０１１８】
好ましい実施形態では、第１境界と第１コーンの間の離隔の第１測定値は、第１コーンの法線行列Ｓによって与えられる線形制約と、第１境界の法線行列Ｎおよびベクトルｃによって与えられる線形制約とを使用して線形計画法問題を解くことによって計算される。図９Ａないし９Ｃに関連する議論を想起されたい。
【０１１９】
代替実施形態では、第１測定値に、第１コーンと第１境界の間の近接（すなわち近さ）の価値が含まれ、この価値は、第１コーンの頂点と、第１コーンおよび第１境界の共通部分の点との間の離隔距離の減少関数を最大化することによって決定される。この場合、ステップ５０４Ｂでは、大きい測定値がより近い近接を示すので、第１測定値が第１コーンに関連する測定値より大きいかどうかを判定する。言い換えると、ステップ５０４Ｂの不等式条件は、第１測定値が第１コーンに関連する測定値より大きい時に満足される。
【０１２０】
図１２に、ステップ５０２すなわち、オブジェクトの集合からの境界階層の構成を示す。ステップ６０２で、グラフィックス・シーン内のオブジェクトを、再帰的にクラスタ化する。オブジェクトは、好ましくは近接に基づいてクラスタに組み込まれる。これらの１次クラスタは、それ自体が２次クラスタに組み込まれる。後続の高次のクラスタは、すべてのオブジェクトが１つのユニバーサル・クラスタに含まれるまで形成される。オブジェクトは、０次クラスタとみなすことができる。ステップ６０４で、すべての次数の各クラスタの境界を、対応する境界を用いて定める。境界は、図４および５に関連して上で説明した多面体外皮であることが好ましい。しかし、たとえば２次曲面、一般化された多項式境界など、他の種類の境界が企図されている。
【０１２１】
ステップ６０６で、オブジェクトおよびクラスタのそれぞれについてノードを割り振ることによって、境界の階層木を生成する。ステップ６０８で、各ノードに、対応する境界を記述する（特性を表す）パラメータを割り当てる。１実施形態では、このパラメータ割当に、図５Ａおよび５Ｂに関連して説明した、多面体外皮面を配置するベクトルｃの記憶が含まれる。ステップ６１０で、ノードを編成し、その結果、ノードの関係がクラスタのメンバシップに対応するようにする。たとえば、ノードＡが境界階層内でノードＢの親である場合には、ノードＡに対応するクラスタに、ノードＢに対応するサブクラスタが含まれ、ノードＡの境界に、ノードＢの境界が含まれる。
【０１２２】
上のコーン階層の構成は、再帰的クラスタ化に関して説明したが、反復クラスタ化などの他の形のクラスタ化を使用する代替実施形態が企図されていることに留意されたい。
【０１２３】
終端コーン−境界対
図１３に、ステップ５０４Ｃの最初の部分すなわち、第１境界と第１コーンの両方がそれぞれの階層のリーフである時に、第１コーンに関して第１境界を検索するステップを示す。ステップ７０２で、可視性検索アルゴリズムが、第１コーンと第１境界が、めいめいの階層のリーフであるかどうかを判定する。この両方がリーフである場合に、可視性検索アルゴリズムは、（ａ）ステップ７０４に示されているように、第１コーンに関連する測定値に、第１境界と第１コーンの間の離隔の第１測定値をセットし、（ｂ）ステップ７０６に示されているように、第１コーンに関連する可視オブジェクト属性に、第１境界をセットする。ステップ７０４および７０６は、任意の順序でまたは並列に実行できることに留意されたい。
【０１２４】
非終端境界を有する終端コーン
図１４に、ステップ５０４Ｃの第２の部分すなわち、第１コーンがコーン階層のリーフであり、第１境界が境界階層のリーフでない時に、第１コーンに関して第１境界を検索するステップを示す。ステップ７１０で、可視性検索アルゴリズムは、第１コーンがコーン階層のリーフ・コーンであり、第１境界が境界階層の非リーフ境界すなわち非終端境界であるかどうかを判定する。第１コーンがリーフ・コーンであり、第１境界がリーフ境界でないことの肯定の判定に応答して、第１境界のサブ境界を第１コーンに関して条件的に探索する。
【０１２５】
図１５に、ステップ７１２すなわち、第１コーンに関して第１境界のサブ境界を条件的に探索するステップを示す。ステップ７２０で、可視性検索アルゴリズムは、第１コーンに関して第１境界のサブ境界のそれぞれについてコーン−境界の離隔値を計算する。１実施形態では、コーン−境界の離隔値を、第１測定値と同じ形で計算する。ステップ７２２で、可視性検索アルゴリズムは、第１コーンからの離隔の昇順で、第１コーンに関して第１境界のサブ境界を条件的に検索する。コーン−境界の離隔値が、昇順の判定に使用される。言い換えると、サブ境界Ａがサブ境界Ｂよりも第１コーンに近い場合に、サブ境界Ａが、サブ境界Ｂの前に条件的に検索される。
【０１２６】
図１６に、ステップ７２２すなわち、第１境界の包括的第１サブ境界による、第１コーンに関する第１境界のサブ境界の条件検索を示す。ステップ７３０で、可視性検索アルゴリズムは、第１サブ境界のコーン−境界の離隔値が、第１コーンに関連する測定値に関して不等式条件を満足するかどうかを判定する。ステップ７３０でテストされる不等式の意味は、ステップ５０４Ｂでテストされる不等式の意味と同一とすることができる。
【０１２７】
ステップ７３２で、可視性検索アルゴリズムは、第１サブ境界のコーン−境界の離隔値が第１コーンの測定値に関して不等式条件を満足することの肯定の判定に応答して、第１コーンに関して第１サブ境界を検索する。
【０１２８】
非終端コーンを有する終端外皮
図１７に、ステップ５０４Ｃの第３の部分すなわち、第１境界が境界階層のリーフ境界であり、第１コーンがコーン階層の非リーフ・コーンである時に、第１コーンに関して第１境界を検索するステップを示す。ステップ７４０で、可視性検索アルゴリズムは、第１境界が境界階層のリーフ境界であり、第１コーンがコーン階層の非リーフ・コーンであるかどうかを判定する。ステップ７４２で、可視性検索アルゴリズムは、第１境界がリーフ境界であり、第１コーンが非リーフ・コーンであることの肯定の判定に応答して、第１境界に関して第１コーンのサブコーンを条件的に検索する。
【０１２９】
図１８に、ステップ７４２すなわち、包括的第１サブコーンによって、第１境界に関して第１コーンのサブコーンを条件的に検索するステップを示す。包括的代表は、第１コーンのサブコーンのすべてを条件的に検索する処理を代表することが目的である。ステップ７４９で、可視性検索アルゴリズムは、第１サブコーンに関する第１境界のコーン−境界の離隔値を計算する。ステップ７５０で、可視性検索アルゴリズムは、そのコーン−境界の離隔値が、第１サブコーンに関連する測定値に関して不等式条件を満足するかどうかを判定する。１実施形態では、コーン−境界の離隔値は、ステップ５０４Ａで第１測定値の計算に使用されたものと同一の方法を使用して計算される。この場合、ステップ７５０でテストされる不等式の意味は、ステップ５０４Ｂでテストされる不等式の意味との一貫性を有するものとすることができる。
【０１３０】
ステップ７５２で、可視性検索アルゴリズムは、コーン−境界の離隔値が第１サブコーンに関連する測定値に関して不等式条件を満足することの肯定の判定に応答して、第１境界に関して第１サブコーンを検索する。
【０１３１】
第１コーンのサブコーンを第１境界に対して検索した後に、第１コーンに関連する測定値を更新する。すなわち、第１コーンに関連する測定値に、第１コーンのサブコーンに関連する測定値の極値（すなわち最大値または最小値）をセットすることができる。極値としての最大値の選択は、離隔の増加関数に基づいてコーン−境界の離隔を計算する実施形態に関連する。極値としての最小値の選択は離隔の減少関数に基づいてコーン−境界の離隔を計算する実施形態に関連する。
【０１３２】
非終端境界を有する非終端コーン
図１９に、ステップ５０４Ｃの第４の部分すなわち、第１コーンおよび第１境界の両方がそれぞれの階層のリーフ・ノードでない時に、第１コーンに関して第１境界を検索するステップを示す。ステップ７５９で、可視性検索アルゴリズムは、第１コーンの第１サブコーンに関して第１境界の第１コーン−境界の離隔値を計算する。ステップ７６０で、可視性検索アルゴリズムは、第１コーン−境界の離隔値が、第１サブコーンに関連する測定値に関して不等式条件を満足するかどうかを判定する。１実施形態では、第１コーン−境界の離隔値は、ステップ５０４Ａで第１測定値の計算に使用されたものと同一の方法を使用して計算される。この場合、ステップ７６０でテストされる不等式の意味は、ステップ５０４Ｂでテストされる不等式の意味との一貫性を有するものとすることができる。ステップ７６２で、可視性検索アルゴリズムは、第１コーン−境界の離隔値が第１サブコーンに関連する測定値に関して不等式条件を満足することの肯定の判定に応答して、第１サブコーンに関して第１境界のサブ境界を条件的に探索する。
【０１３３】
図２０に、ステップ７６２すなわち、第１サブコーンに関して第１外皮のサブ外皮を条件的に探索するステップを示す。ステップ７７０で、可視性検索アルゴリズムは、第１サブコーンに関する第１境界のサブ境界のそれぞれの第２コーン−境界の離隔値を計算する。第２コーン−境界の離隔値は、ステップ５０４Ａで第１測定値の計算に使用されたものと同一の方法を使用して計算することができる。ステップ７７２で、可視性検索アルゴリズムは、第１サブコーンからの離隔の昇順で第１サブコーンに関して第１境界のサブ境界を条件的に検索する、すなわち、第１サブコーンに近いサブ境界が最初に検索される。この検索の順序付けによって、有利なことに、より近いサブ境界が、より遠いサブ境界の検索の先に立つことができ、したがって、不要な検索が回避される。
【０１３４】
図２１に、ステップ７７２すなわち、第１サブコーンに関して第１境界のサブ境界を条件的に検索するステップを示す。第１外皮の包括的サブ外皮を使用してこの条件的検索を示す。ステップ７８０で、可視性検索アルゴリズムは、第１境界のサブ境界のうちの第１サブ境界の第２コーン−外皮の離隔値が、第１サブコーンに関連する測定値に関して不等式条件を満足するかどうかを判定する。ステップ７８０でテストされる不等式の意味は、特に第２コーン−外皮の離隔値の計算に使用される方法が第１測定値の計算に使用される方法と同一である場合に、ステップ５０４Ｂでテストされる不等式の意味に類似するものとすることができることに留意されたい。
【０１３５】
ステップ７８２で、可視性探索アルゴリズムは、第１サブ境界の第２コーン−外皮の離隔値が第１サブコーンに関連する測定値に関して不等式条件を満足することの肯定の判定に応答して、第１サブコーンに関して第１サブ境界を検索する。
【０１３６】
第１境界のサブ境界を第１サブコーンに対して検索した後に、第１コーンの第２サブコーンをテストする。具体的に言うと、可視性検索アルゴリズムは、第２サブコーンからの第１境界の離隔の測定を計算する。この離隔の測定が、第２サブコーンに関連する測定値に関して不等式条件を満足する場合には、第１境界のサブ境界を、第２サブコーンに関して条件的に探索することができる。第２サブコーンの条件探索は、図２０および２１に関連して説明した第１サブコーンの条件探索に類似する。
【０１３７】
上で説明したように、第１コーンのすべてのサブコーンをテストし、条件的に検索した後に、第１コーンに関連する測定値に、サブコーンに関連する測定値の極値をセットする。上で注記したように、コーン−境界の離隔値の計算に離隔の増加関数を使用する実施形態では、極値として最大値が選択され、コーン−境界の離隔値の計算に離隔の減少関数を使用する実施形態では、極値として最小値が選択される。
【０１３８】
１代替実施形態では、リーフ・コーンが、１画素より大きい角度のセクタに相対する。したがって、上で説明した可視性検索アルゴリズムの終了の後に、光線に基づく探索方法によってリーフ・コーンをさらに処理して、リーフ・コーン内の個々の画素の値を決定することができる。
【０１３９】
上で説明した境界階層およびコーン階層の検索では、再帰形式を仮定したが、レベル順検索または反復検索が、境界階層およびコーン階層の一方または両方に対して実行される代替実施形態が企図されている。
【０１４０】
コーンによって制限される距離関数の計算
コーンＣからの外皮Ｈのコーン−外皮の距離ｆＣ（Ｈ）の評価が、外皮制約Ａｘ≦ｂおよびコーン制約Ｓｘ≦０の対象となる‖ｘ‖の最小化を必要とすることを想起されたい。行列Ａの行には、外皮表面の法線が含まれる。行列Ｓの行には、コーン表面の法線が含まれる。この最小化は、非線形計画法問題として定式化することができる。たとえば、非線形計画法問題は、ユークリッド・ノルムを使用する時には二次計画法問題になり、Ｌ１ノルムを使用する時には線形計画法問題になる。コーン−外皮の距離計算を本明細書では幾何照会と称する。
【０１４１】
コーン−外皮の離隔は、境界／外皮制約およびコーン制約を満足する点ｘについて‖ｘ‖−１などの増加関数離隔を最大化することによって測定できることにも留意されたい。したがって、一般に、コーン−外皮の離隔値は、コーン制約および境界／外皮制約の対象になる離隔関数の極値（すなわち最大値または最小値）を判定することによって計算することができる。
【０１４２】
光線の集合の代わりにコーンの階層を使用する動機は、計算効率の所望である。前に示した二重再帰から生じる早期の候補枝刈りのおかげで、より少ない幾何照会が実行される。しかし、これらの照会は、レイ・キャスティング方法で使用される照会よりはるかに高価である。したがって、コーン照会計算は、非常に注意深く設計しなければならない。ずさんなアルゴリズムは、二重木検索での改善によってもたらされる計算上の利益の大半を浪費することになりかねない。線形計画法の場合について、計算的に厳しい照会を達成する方法の概要を示す。
【０１４３】
距離ｆＣの区分的線形定式化によって、次の線形計画が得られる。
ｍｉｎ（ｖＴｘ）
ただし、Ａｘ≦ｂ、Ｓｘ≦０
ベクトルｖは、コーンＣに対する極線のコーンの要素である。たとえば、ｅが全要素が１のベクトルであるものとすると、ｖ＝−ＳＴｅである［コーンの法線Ｓの行列Ｓが、コーン表面に対する外向きの法線であることに留意されたい。したがって、法線ベクトルの和の符号を反転すると、極線ベクトルになる］。条件Ａｘ≦ｂは、点ｘが境界外皮の中にあることを意味する。条件Ｓｘ≦０は、点ｘがコーンＣの中にあることを意味する。効率的な解法のために、線形計画問題を、その双対の項で書き直す。
ｍａｘ（ｂＴｙ）
ただし、ＡＴｙ＋ＳＴｚ＝ｖ、０≦ｙ、０≦ｚ
双対目標値ｂＴは、コーンと境界外皮が交わらない時に無限大になる（変数ｙおよびｚは、前の問題の制約のラグランジェの乗数である）。
【０１４４】
好ましい実施形態では、境界外皮が、法線ベクトルの固定された組に垂直な面を有する。したがって、行列ＡＴは、すべての外皮について同一になる。所与のコーンについて、行列ＳＴおよびベクトルｖも固定値である。この観察から、多次元多面体
｛（ｙ，ｚ）：ＡＴｙ＋ＳＴｚ＝ｖ，０≦ｙ，０≦ｚ｝
が、コーンに関連することは明白である（１実施形態では、この多面体が１７次元を有する。これらの次元のうちの１４次元は、固定方向境界外皮の種類に由来し、３つの追加の次元はコーンに由来する）。この多面体は、コーン行列Ｓだけに依存するので、コーン階層内のすべてのコーンについて多角形の極値構造を事前に完全に計算することは、実行可能である。相補的な緩さによって、多面体の頂点は、多くとも３つの要素を有する。辺と極値の光線は、多くとも４つの非ゼロ要素を有する。宿約されたシンプレックス・ベースのヒル・クライム技法を使用して、この設定の照会をすばやく解くことができる。
【０１４５】
設定を確立するためには、コーン階層の方位を固定する必要がある。これは、ビュー切頭体の方位の変化に伴ってコーン階層の方位が変化する場合には、実行できない。したがって、全空間をコーンによってテセレートし、可視オブジェクトを全空間内で検出する。この全空間計算の後に限って、オブジェクトの可視の組が、現在のビュー切頭体に合わせてカリングされる。
【０１４６】
代替実施形態では、より積極的でない手法を行うことができる。すなわち、コーンのどのサブセットがビュー切頭体の現在の方位に対応するかを記録することによって、このサブセットだけを、可視オブジェクトの組の計算に含めることができる。
【０１４７】
記憶媒体
前に述べたように、本発明の可視性ソフトウェアおよび可視性検索プログラムは、プロセッサ１０２によるアクセスのためにメモリ１０６に記憶されることが好ましい。さらに、可視性ソフトウェアおよび可視性検索プログラムは、インストール媒体（たとえばＣＤ−ＲＯＭ、フロッピ・ディスクなど）、不揮発性メモリ（たとえばハード・ディスク、光学記憶装置、磁気テープ、ｚｉｐドライブ記憶装置、ＲＯＭなど）、ＲＡＭなどのさまざまな種類の揮発性メモリ、またはこれらの組合せなど、所望の記憶媒体に記憶することができる。本発明は、エンド・ユーザまたは顧客への配布のための記憶媒体への可視性ソフトウェアおよび可視性検索プログラムの寄託および記憶を企図している。
【０１４８】
コーンあたり複数のオブジェクト
可視性検索ソフトウェアによれば、リーフ・コーン（すなわち終端コーン）のそれぞれについて、単一の最も近いオブジェクトが識別される。リーフ・コーンのそれぞれが、究極の解像度すなわち１画素の解像度を有する場合には、各リーフ・コーンで最も近いオブジェクトを識別するという戦略が、すべての可視オブジェクトを検出することが保証される。しかし、完全に解像されたコーン階層の可視性検索は、計算的に高価である。この計算コストは、コーン階層の細分化のレベルを減らすことによって減らすことができる。しかし、細分化のレベルを減らすことは、リーフ・コーンのサイズが大きくなることを意味する。リーフ・コーンのサイズが大きくなるにつれて、複数のオブジェクトが単一のリーフ・コーンに対して可視になるすなわち、最も近いオブジェクトだけがコーンに可視のオブジェクトではなくなる確率が高まる。したがって、リーフ・コーンのサイズが大きくなるか、これと同等であるが、コーン階層で使用されるコーン細分化のレベルが減る時に、可視オブジェクトの完全な組より少ない数のオブジェクトが報告される可能性が高まる。
【０１４９】
可視オブジェクトの完全な組を捉える確率を高めるために、可視性検索アルゴリズムを変更して、リーフ・コーンごとに最初のＫ個の最も近いオブジェクトを識別するようにすることができる。ここで、Ｋは２以上の整数である。有利なことに、整数Ｋは、コーンサイズの関数とすることができる。したがって、コーン階層が究極の解像度に近い場合には、Ｋを１に近い値にすることができる。逆に、コーン階層が、低い解像度を有する、すなわち、少数の細分化のレベルだけが含まれる場合には、整数Ｋを大きくすることができる。
【０１５０】
本発明は、一方では高コーン解像度／低Ｋ値の軸に沿い、もう一方では低コーン解像度／高Ｋ値の軸に沿った計算効率の最大化を企図している。
【０１５１】
コーン階層の適応細分化
前述の議論では、コーン階層が、可視性検索アルゴリズムによる可視オブジェクトの検索の開始の前に構成され、検索中に静的なままであるものとして説明した。もう１つの代替案が、検索手順中にコーン階層を適応式に細分することである。この形では、コーン階層は、どのオブジェクトとも絶対に交わらないコーンのために記憶域を浪費しなくなる可能性がある。コーン階層は、ユーザ入力に応答して細分することができる。たとえば、ユーザが現在見つめている方向に対応するコーンは、追加の細分化を正当化することができる。所与のコーンは、その所与のコーンと相互作用する境界が検索手順で発見されるまで細分されないままにすることができ、それが発見された時点で、そのコーンを細分することができる。所与のコーンの細分化は、追加の相互作用するオブジェクト／境界が発見された時に、そのオブジェクトをより適切に区別するためにさらに細分することができる。オブジェクトが移動している情況では、所与のコーンの視界内へのオブジェクトの移動が、所与のコーンの細分化の向上を引き起こすことができる。仮想環境内のユーザが、立ち止まって所与のオブジェクトを見つめる場合には、そのオブジェクトを定義するコーンをさらに細分することができる。
【０１５２】
コーン階層の細分化は、計算サイクルの可用性の対象とすることができる。連続的ウォーミング（ｓｕｃｃｅｓｓｉｖｅ ｗａｒｍｉｎｇ）のパラダイムによれば、初期のコーン木は、１つまたは少数のコーンだけを有することができ、即座に表示される可視オブジェクトの組の粗い初期推定が可能になる。計算サイクルが使用可能になるにつれて、ますます正確になる可視オブジェクトの組の表示をもたらすために、コーン階層を連続的に細分し、検索することができる。
【０１５３】
一般に、コーン階層のコーンは、細分化の異なるレベルにある可能性がある。コーン細分化は、コーンがオブジェクトまたは境界（たとえば外皮）と相互作用する場合に限って許可される。コーンの適応細分化は、コーンの解像度が画素と等しくなった時か、コーンの中にオブジェクトがなくなった時に終了する。
【０１５４】
コーン階層の固定細分化と適応細分化の組み合わせを使用できることに留意されたい。
【０１５５】
本発明は、コーン階層を適応式に細分し、コーンごとにＫ個の最も近いオブジェクト／境界を識別し、Ｋによって細分化レベル変化が変更されることも企図している。
【０１５６】
ノンオクルーディング（ｎｏｎ−ｏｃｃｌｕｄｉｎｇ）・オブジェクト
ノンオクルーディング・オブジェクトとは、他のオブジェクトを完全には遮らない（すなわち可視性を完全にはブロックしない）オブジェクトである。たとえば、透明オブジェクト、半透明オブジェクト、またはトランスルーセント（ｔｒａｎｓｌｕｃｅｎｔ）オブジェクトが、ノンオクルーディング・オブジェクトである。網戸、着色ガラス、よろい板付きの窓をノンオクルーディングとして分類することができる。ノンオクルーディングなものの背後にあるオブジェクトは、部分的に可視になる可能性がある。本発明は、検索されるオブジェクトの集合にノンオクルーディング・オブジェクト（ＮＯＯ）が存在することを許容するための可視性検索アルゴリズムの変更を企図している。具体的に言うと、可視性検索アルゴリズムは、各リーフ・コーンで、最初のＫ個の最も近いオクルーディング（遮る）・オブジェクトと、Ｋ番目のオクルーディング・オブジェクトより近いＮＯＯを検索するように構成することができる。ここで、Ｋは、リーフ・コーンサイズの関数とすることができる。
【０１５７】
（産業上の利用可能性）
本発明は、コンピュータ・グラフィックス、コンピュータ・ビジュアライゼーション、コンピュータ支援設計およびエンジニアリング、ディジタル画像処理、仮想現実感モデリング、および並列処理を含むが、これらに制限されない、多数の異なる分野に適用可能である。
【０１５８】
上の開示を完全に理解した後に、多数の変形形態および修正形態が、当業者には明白になるであろう。請求の範囲は、そのような変形形態および修正形態のすべてを含むものとして解釈されることを目的とする。
【０１５９】
付録：ｆｉｎｄＶｉｓｉｂｉｌｉｔｙ関数のソース・コード
以下のソース・コードに、各リーフ・コーンの可視オブジェクトを識別するための外皮木およびコーン木の再帰検索の１実施形態を示す。
2004513403.tif 000007
2004513403.tif 000008
2004513403.tif 000009
【図面の簡単な説明】
【図１】
従来技術による可視オブジェクト検出の光線ベースの方法を示す図である。
【図２Ａ】
本発明によるグラフィカル計算システムを示す図である。
【図２Ｂ】
本発明のグラフィカル計算システムの１実施形態を示すブロック図である。
【図３】
本発明によるビジュアライゼーション・ソフトウェアの複数の主な相を示す図である。
【図４】
グラフィックス環境内のオブジェクトの集合を示す図（Ａ）、外皮階層の最初の形成の第１ステップすなわち、包含外皮を用いてオブジェクトの境界を定め、包含外皮の外皮ノードを割り振るステップを示す図（Ｂ）、高次外皮を形成するために外皮を一緒にグループ化し、高次外皮に対応する外皮階層内のノードを割り振る処理を示す図（Ｃ）、すべてのオブジェクトが、外皮階層のルート・ノードに対応するユニバーサル包含外皮に含まれる、再帰的グループ化処理の最高部を示す図（Ｄ）である。
【図５Ａ】
２次元空間内の直線と半平面を記述する数学的表現を示す図である。
【図５Ｂ】
２次元空間内の４つの半平面の共通部分としての長方形領域の記述を示す図である。
【図６】
サブコーンのそれぞれの中で伝播する波面によってオブジェクトの集合と相互作用する複数のサブコーンに区分された２次元コーンを示す図である。
【図７】
原点から発する長方形および三角形の横断面を有する多面コーンを示す図である。
【図８Ａ】
２次元空間内の、原点を通る直線と、法線ベクトルを与えられた場合の対応する半平面を記述する数学的表現を示す図である。
【図８Ｂ】
２つの半平面の共通部分としての２次元コーン領域の指定を示す図である。
【図９】
長方形の横断面による当初のコーンの副分割の繰り返しに基づくコーン階層の形成を示す図（Ａ）、長方形の横断面による当初のコーンの副分割の繰り返しに基づくコーン階層の形成を示す図（Ｂ）、長方形の横断面による当初のコーンの副分割の繰り返しに基づくコーン階層の形成を示す図（Ｃ）である。
【図１０Ａ】
本発明による可視性検索アルゴリズムを示す図である。
【図１０Ｂ】
本発明による可視性検索アルゴリズムを示す図である。
【図１０Ｃ】
本発明による可視性検索アルゴリズムを示す図である。
【図１１】
グラフィックス環境内で可視オブジェクトを表示する方法を示す図である。
【図１２】
境界階層を形成するためにオブジェクトの集合を再帰的にクラスタ化する処理を示す図である。
【図１３】
可視性検索が終端コーンおよび終端境界に達した時に実行される処理ステップを示す図である。
【図１４】
可視性検索が終端コーンおよび非終端境界に達した時に実行される処理ステップを示す図である。
【図１５】
図１４のステップ７１２すなわち、第１コーンに関して第１境界のサブ境界を条件的に探索するステップをさらに詳細に示す図である。
【図１６】
図１５のステップ７２２すなわち、１例として包括的サブ境界によって、第１コーンに関して第１境界のサブ境界を条件的に検索するステップをさらに詳細に示す図である。
【図１７】
可視性検索が終端境界および非終端コーンに達した時に実行される処理ステップを示す図である。
【図１８】
図１７のステップ７４２すなわち、包括的サブコーンの例によって、第１境界に関して第１コーンのサブコーンを条件的に検索するステップをさらに詳細に示す図である。
【図１９】
可視性検索が非終端境界および非終端コーンに達した時に実行される処理ステップを示す図である。
【図２０】
図１９のステップ７６２すなわち、第１サブコーンに関して第１境界のサブ境界を条件的に探索するステップをさらに詳細に示す図である。
【図２１】
図２０のステップ７７２すなわち、包括的サブ外皮の例によって、第１サブコーンに関して第１境界のサブ境界を条件的に検索するステップをさらに詳細に示す図である。
【図２Ｂ】
2004513403.tif 000010
【図３】
2004513403.tif 000011
【図１０Ａ】
2004513403.tif 000012
【図１０Ｂ】
2004513403.tif 000013
【図１０Ｃ】
2004513403.tif 000014
【図１１】
2004513403.tif 000015
【図１２】
2004513403.tif 000016
【図１３】
2004513403.tif 000017
【図１４】
2004513403.tif 000018
【図１５】
2004513403.tif 000019
【図１６】
2004513403.tif 000020
【図１７】
2004513403.tif 000021
【図１８】
2004513403.tif 000022
【図１９】
2004513403.tif 000023
【図２０】
2004513403.tif 000024
【図２１】
2004513403.tif 000025
【国際公開パンフレット】
2004513403.tif 000026
2004513403.tif 000027
2004513403.tif 000028
2004513403.tif 000029
2004513403.tif 000030
2004513403.tif 000031
2004513403.tif 000032
2004513403.tif 000033
2004513403.tif 000034
2004513403.tif 000035
2004513403.tif 000036
2004513403.tif 000037
2004513403.tif 000038
2004513403.tif 000039
2004513403.tif 000040
2004513403.tif 000041
2004513403.tif 000042
2004513403.tif 000043
2004513403.tif 000044
2004513403.tif 000045
2004513403.tif 000046
2004513403.tif 000047
2004513403.tif 000048
2004513403.tif 000049
2004513403.tif 000050
2004513403.tif 000051
2004513403.tif 000052
2004513403.tif 000053
2004513403.tif 000054
2004513403.tif 000055
2004513403.tif 000056
2004513403.tif 000057
2004513403.tif 000058
2004513403.tif 000059
2004513403.tif 000060
2004513403.tif 000061
2004513403.tif 000062
2004513403.tif 000063
2004513403.tif 000064
2004513403.tif 000065
2004513403.tif 000066
2004513403.tif 000067
2004513403.tif 000068
2004513403.tif 000069
2004513403.tif 000070
2004513403.tif 000071
2004513403.tif 000072
2004513403.tif 000073
2004513403.tif 000074
2004513403.tif 000075
2004513403.tif 000076
2004513403.tif 000077
2004513403.tif 000078
2004513403.tif 000079
2004513403.tif 000080
2004513403.tif 000081
2004513403.tif 000082
2004513403.tif 000083
2004513403.tif 000084
【国際調査報告】
2004513403.tif 000085