JP3724006B2 - High speed rendering method and apparatus - Google Patents

Description

【０００５】
（３） 視線の向きによる面のグルーピングを行い、グループごとに視点から見えるか否かの判定を行い、見えると判定されたグループのみを描画対象とすることにより、該当する３次元モデルの描画を高速化する方法（「リアルタイム景観シミュレータのための形状のグルーピングと多重表現に基づく描画時間の短縮」、北嶋克寛、遊佐洋子、電子情報通信学会論文誌Ｄ−ＩＩ Ｖｏｌ．Ｊ７７−Ｄ−ＩＩ Ｎｏ．２ ｐｐ．３１１−３２０ １９９４年２月）
【０００６】
【発明が解決しようとする課題】
しかし、上記従来の方法は、全て視点と描画物体との位置関係により描画するポリゴンを選出する方法であり、しかも立方体領域、オクトトリーなどの多面体表現を用いて位置関係を計算するのであるから、計算コストがかかるという不都合がある。そして、計算コストがかかることに起因して、描画ポリゴンの選出の所要時間が長くなり、ひいては描画所要時間が長くなってしまう。
【０００７】
【発明の目的】
この発明は上記の問題点に鑑みてなされたものであり、描画ポリゴンの選出所要時間を大幅に短縮することができる高速レンダリング方法およびその装置を提供することを目的としている。
【０００８】
【課題を解決するための手段】
請求項１の高速レンダリング方法は、階層球体モデル保持部（１）に保持されている階層球体モデルの、所定の半径以下の球体のうち、最も上位の階層の球体をレンダリング球として指定するとともに、各レンダリング球に対応してレンダリングモデルを割り当てておき、レンダリング球がクリップ領域の内部か外部かを判定して、レンダリング球がクリップ領域の外部である場合に該当するレンダリングモデルをクリップする方法である。
【０００９】
請求項２の高速レンダリング方法は、モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定し、メッシュ分割により発生し、メッシュデータ保持部（４４）により保持した各節点を中心として最下位階層の球体を生成し、次いで、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とし、その後、最上位階層の球体の中心を通る平面で全節点を２分割し、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とし、その後、全節点の２分割処理および各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して次の球体とする処理を、分割後の節点数が１になるまで反復することにより階層球体モデルを作成する方法である。
【００１０】
請求項３の高速レンダリング方法は、視点位置保持部（１１）に保持されている視点位置を基準として、視線方向ベクトル保持部（１２）に保持されている視線方向ベクトルおよび視野角保持部（１３）に保持されている視野角により視野が規定されている状態において、視点から、レンダリング球中心保持部（１３ａ）に保持されているレンダリング球の中心に向かうベクトルと、このベクトルを中心としてレンダリング球の広がりを規定する角度とを算出し、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいことを条件として該当するレンダリング球を除去する方法である。
【００１１】
請求項４の高速レンダリング方法は、視野内に少なくとも一部が含まれるレンダリング球について、このレンダリング球に含まれるポリゴンをそれぞれの法線ベクトルの向きに基づいて複数のグループに区分し、各区分に属するポリゴンの法線の集合体を円錐で近似し、視点から、レンダリング球中心保持部（２１）に保持されているレンダリング球の中心に向かうベクトルを中心としてレンダリング球の広がりを規定する第１広がり角度を算出するとともに、ポリゴンの法線の集合体を近似する円錐の中心軸を規定する中心軸ベクトルおよびこの円錐の第２広がり角度を算出し、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であることを条件として、該当する区分に属するポリゴンを描画の対象として選択する方法である。
【００１２】
請求項５の高速レンダリング方法は、各レンダリングモデルに対応するポリゴンについて、視点からレンダリング球の中心に向かうベクトルの大きさに対応させて、予め描画精度が異なる複数のポリゴンを生成してＬＯＤモデル保持部（３１）に保持しておき、上記ベクトルの実際の大きさに基づいて該当する描画精度のポリゴンを描画する方法である。
請求項６の高速レンダリング装置は、階層球体モデルの、所定の半径以下の球体のうち、最も上位の階層の球体をレンダリング球として指定するレンダリング球指定手段と、各レンダリング球に対応してレンダリングモデルを割り当てるレンダリングモデル割り当て手段と、レンダリング球がクリップ領域の内部か外部かを判定する内外判定手段と、レンダリング球がクリップ領域の外部であることを示す内外判定手段の判定結果に応答して該当するレンダリングモデルをクリップするクリップ手段とを有している。
【００１３】
請求項７の高速レンダリング装置は、モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定するメッシュ分割手段と、メッシュ分割により発生した各節点を中心として最下位階層の球体を生成する最下位階層球体生成手段と、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とする最上位階層球体生成手段と、処理時点での最上位階層の球体の中心を通る平面で全節点を２分割する分割手段と、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とする中間階層球体生成手段と、分割手段による処理および中間階層球体生成手段による処理を、分割後の節点数が１になるまで反復させる反復制御手段とをさらに有している。
【００１４】
請求項８の高速レンダリング装置は、視野を規定すべく、視点位置を基準として設定された視線方向ベクトルおよび視野角を保持する保持手段と、視点からレンダリング球の中心に向かうベクトルと、このベクトルを中心としてレンダリング球の広がりを規定する角度とを算出する算出手段と、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいか否かを判定する第１大小判定手段と、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいことを示す第１大小判定手段の判定結果に応答して該当するレンダリング球を除去するレンダリング球除去手段とをさらに有している。
【００１５】
請求項９の高速レンダリング装置は、視野内に少なくとも一部が含まれるレンダリング球について、このレンダリング球に含まれるポリゴンをそれぞれの法線ベクトルの向きに基づいて複数のグループに区分する区分手段と、各区分に属するポリゴンの法線の集合体を円錐で近似する近似手段と、視点からレンダリング球の中心に向かうベクトルを中心としてレンダリング球の広がりを規定する第１広がり角度を算出する第１算出手段と、ポリゴンの法線の集合体を近似する円錐の中心軸を規定する中心軸ベクトルおよびこの円錐の第２広がり角度を算出する第２算出手段と、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であるか否かを判定する第２大小判定手段と、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であることを示す第２大小判定手段の判定結果に応答して該当する区分に属するポリゴンを描画の対象として選択する選択手段とをさらに有している。
【００１６】
請求項１０の高速レンダリング装置は、各レンダリングモデルに対応するポリゴンについて、視点からレンダリング球の中心に向かうベクトルの大きさに対応させて、予め描画精度が異なる複数のポリゴンを生成しておくポリゴン生成手段と、上記ベクトルの実際の大きさに基づいて該当する描画精度のポリゴンを描画する描画手段とをさらに有している。
【００１７】
【作用】
請求項１の高速レンダリング方法であれば、階層球体モデル保持部（１）に保持されている階層球体モデルの、所定の半径以下の球体のうち、最も上位の階層の球体をレンダリング球として指定するとともに、各レンダリング球に対応してレンダリングモデルを割り当てておき、レンダリング球がクリップ領域の内部か外部かを判定して、レンダリング球がクリップ領域の外部である場合に該当するレンダリングモデルをクリップするのであるから、多面性表現を用いた位置関係の計算が不要になり、レンダリング球を用いた干渉計算を行うことによりレンダリングモデルのクリップを高速に達成でき、ひいてはレンダリングを高速化することができる。
【００１８】
請求項２の高速レンダリング方法であれば、モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定し、メッシュ分割により発生し、メッシュデータ保持部（４４）により保持した各節点を中心として最下位階層の球体を生成し、次いで、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とし、その後、直前の階層の球体の中心を通る平面で全節点を２分割し、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とし、その後、全節点の２分割処理および各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して次の階層の球体とする処理を、分割後の節点数が１になるまで反復することにより階層球体モデルを作成するのであるから、物体に内包される球体はもともと生成されず、処理の複雑化を伴なうことなく、生成される球体の数を減少させることができ、このように生成された階層球体モデルに基づいて請求項１と同様の作用を達成することができる。
【００１９】
請求項３の高速レンダリング方法であれば、視点位置保持部（１１）に保持されている視点位置を基準として、視線方向ベクトル保持部（１２）に保持されている視線方向ベクトルおよび視野角保持部（１３）に保持されている視野角により視野が規定されている状態において、視点から、レンダリング球中心保持部（１３ａ）に保持されているレンダリング球の中心に向かうベクトルと、このベクトルを中心としてレンダリング球の広がりを規定する角度とを算出し、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいことを条件として該当するレンダリング球を除去するのであるから、多面性表現を用いた位置関係の計算が不要になり、描画に不要なレンダリング球の除去を円錐対円錐の高速な干渉チェックにより簡単にすることができ、ひいては描画ポリゴンの検出を高速に達成することができる。
【００２０】
請求項４の高速レンダリング方法であれば、視野内に少なくとも一部が含まれるレンダリング球について、このレンダリング球に含まれるポリゴンをそれぞれの法線ベクトルの向きに基づいて複数のグループに区分し、各区分に属するポリゴンの法線の集合体を円錐で近似し、視点から、レンダリング球中心保持部（２１）に保持されているレンダリング球の中心に向かうベクトルを中心としてレンダリング球の広がりを規定する第１広がり角度を算出するとともに、ポリゴンの法線の集合体を近似する円錐の中心軸を規定する中心軸ベクトルおよびこの円錐の第２広がり角度を算出し、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であることを条件として、該当する区分に属するポリゴンを描画の対象として選択するのであるから、多面体表現を用いた位置関係の計算が不要になり、レンダリング球内のポリゴンのうち、描画の対象となるポリゴンの選択を高速に達成でき、ひいてはレンダリングを高速化することができる。
【００２１】
請求項５の高速レンダリング方法であれば、各レンダリングモデルに対応するポリゴンについて、視点からレンダリング球の中心に向かうベクトルの大きさに対応させて、予め描画精度が異なる複数のポリゴンを生成してＬＯＤモデル保持部（３１）に保持しておき、上記ベクトルの実際の大きさに基づいて該当する描画精度のポリゴンを描画するのであるから、一部のポリゴンについて描画精度が低いポリゴンを採用することにより描画を高速化でき、ひいてはレンダリングを高速化することができる。
【００２２】
請求項６の高速レンダリング装置であれば、階層球体モデルの、所定の半径以下の球体のうち、最も上位の階層の球体をレンダリング球指定手段によりレンダリング球として指定し、レンダリングモデル割り当て手段により、各レンダリング球に対応してレンダリングモデルを割り当てる。そして、内外判定手段により、レンダリング球がクリップ領域の内部か外部かを判定し、レンダリング球がクリップ領域の外部であることを示す内外判定手段の判定結果に応答してクリップ手段により該当するレンダリングモデルをクリップする。したがって、多面体表現を用いた位置関係の計算が不要になり、レンダリング球を用いた干渉計算を行うことによりレンダレングモデルのクリップを高速に達成でき、ひいてはレンダリングを高速化することができる。
【００２３】
請求項７の高速レンダリング装置であれば、モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定するメッシュ分割手段と、メッシュ分割により発生した各節点を中心として最下位階層の球体を生成する最下位階層球体生成手段と、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とする最上位階層球体生成手段と、処理時点での最上位階層の球体の中心を通る平面で全節点を２分割する分割手段と、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とする中間階層球体生成手段と、分割手段による処理および中間階層球体生成手段による処理を、分割後の節点数が１になるまで反復させる反復制御手段とをさらに有しているのであるから、物体に内包される球体はもともと生成されず、処理の複雑化を伴うことなく、生成される球体の数を減少させることができ、このように生成された階層球体モデルに基づいて請求項６と同様の作用を達成することができる。
【００２４】
請求項８の高速レンダリング装置であれば、視野を規定すべく、視点位置を基準として設定された視線方向ベクトルおよび視野角を保持する保持手段と、視点からレンダリング球の中心に向かうベクトルと、このベクトルを中心としてレンダリング球の広がりを規定する角度とを算出する算出手段と、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいか否かを判定する第１大小判定手段と、両ベクトルのなす角が視野角とレンダリング球の広がりを規定する角度との和よりも大きいことを示す第１大小判定手段の判定結果に応答して該当するレンダリング球を除去するレンダリング球除去手段とをさらに有しているのであるから、多面体表現を用いた位置関係の計算が不要になり、描画に不要なレンダリング球の除去を円錐対円錐の高速な干渉チェックにより簡単にすることができ、ひいては描画ポリゴンの検出を高速に達成することができる。
【００２５】
請求項９の高速レンダリング装置であれば、視野内に少なくとも一部が含まれるレンダリング球について、このレンダリング球に含まれるポリゴンをそれぞれの法線ベクトルの向きに基づいて複数のグループに区分する区分手段と、各区分に属するポリゴンの法線の集合体を円錐で近似する近似手段と、視点からレンダリング球の中心に向かうベクトルを中心としてレンダリング球の広がりを規定する第１広がり角度を算出する第１算出手段と、ポリゴンの法線の集合体を近似する円錐の中心軸を規定する中心軸ベクトルおよびこの円錐の第２広がり角度を算出する第２算出手段と、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であるか否かを判定する第２大小判定手段と、視点からレンダリング球の中心に向かうベクトルと中心軸ベクトルとのなす角が両広がり角度の和以下であることを示す第２大小判定手段の判定結果に応答して該当する区分に属するポリゴンを描画の対象として選択する選択手段とをさらに有しているのであるから、多面体表現を用いた位置関係の計算が不要になり、レンダリング球内のポリゴンのうち、描画の対象となるポリゴンの選択を高速に達成でき、ひいてはレンダリングを高速化することができる。
【００２６】
請求項１０の高速レンダリング装置であれば、各レンダリングモデルに対応するポリゴンについて、視点からレンダリング球の中心に向かうベクトルの大きさに対応させて、予め描画精度が異なる複数のポリゴンを生成しておくポリゴン生成手段と、上記ベクトルの実際の大きさに基づいて該当する描画精度のポリゴンを描画する描画手段とをさらに有しているのであるから、一部のポリゴンについて描画精度が低いポリゴンを採用することにより描画を高速化でき、ひいてはレンダリングを高速化することができる。
【００２７】
【実施例】
以下、実施例を示す添付図面によってこの発明を詳細に説明する。
図１は階層球体モデルとレンダリングモデルとの関係を示す概略図である。
図において、階層球体モデルを構成する各階層の球体をサイズが異なる楕円で示している。また、この階層球体モデルは、最上位階層の球体から順に分割処理を行うことにより作成されるのであるが、この場合に、予め指定した値以下の半径の球体Ｓ１，Ｓ２，Ｓ３が生成された場合に、この球体Ｓ１，Ｓ２，Ｓ３をレンダリング球に設定し、それぞれレンダリングモデルＬ１，Ｌ２，Ｌ３と対応付ける。ただし、予め指定した値以下の半径の球体のうち、最も上位階層の球体のみをレンダリング球に設定する。したがって、レンダリング球よりも下位の階層の球体はレンダリング球ではない。また、レンダリング球の半径が最下位階層の球体の半径よりも十分に大きくなるように、上記値を指定する。さらに、レンダリングモデルＬ１，Ｌ２，Ｌ３は、対応するレンダリング球に包含されるポリゴンなどの形状情報を含むモデルである。
【００２８】
上述のようにレンダリング球とレンダリングモデルとの対応付けを行った場合に、レンダリング球とレンダリングモデルとが１対１で対応しない場合がある。このような場合は、図２に示すように、レンダリングモデルを１対１対応部分Ｌ１´，Ｌ２´と多対１対応部分Ｌ１２´とに分離し、新たなレンダリングモデルを生成する。図２の場合に対応する元のレンダリングモデルＬ１，Ｌ２と新たなレンダリングモデルＬ１´，Ｌ２´，Ｌ１２´との関係は、図３に示すとおりである。
【００２９】
したがって、このようにレンダリング球を設定するとともに、各レンダリング球に対してレンダリングモデルを対応付けておけば、各レンダリング球がクリップ領域の内部か外部かの判定を行い、クリップ領域の外部であると判定されたレンダリング球のみをクリップすることにより、レンダリングモデルのクリップ処理を簡単に達成することができる。
【００３０】
上記レンダリングモデルのクリップ処理は、例えば、図４のフローチャートに示すように、ステップＳＰ１においてレンダリング球を設定し、ステップＳＰ２において各レンダリング球にレンダリングモデルを対応付けし、ステップＳＰ３において、各レンダリング球について、設定されたクリップ領域の内部か外部かの判定を行い、レンダリング球がクリップ領域の外部であると判定された場合には、ステップＳＰ４において、該当するレンダリング球をクリップし、ステップＳＰ５において全てのレンダリング球に対する処理が行われたか否かを判定し、処理が行われていないレンダリング球が存在している場合には、再びステップＳＰ３の処理を行う。逆に、ステップＳＰ５において全てのレンダリング球に対する処理が行われたと判定された場合には、そのまま一連の処理を終了する。また、ステップＳＰ３においてレンダリング球がクリップ領域の内部であると判定された場合には、再びステップＳＰ３の処理を行う。
【００３１】
したがって、階層球体モデルのうち、レンダリング球として設定された球体のみに基づいてクリップ領域に対する内外判定を行い、クリップ領域の外部であると判定されたレンダリング球に対応するレンダリングモデルのクリップ処理を行うことができ、レンダリングモデルをクリップするための処理を著しく簡単化できる。この結果、レンダリングを高速化することができる。
【００３２】
ただし、クリップされなかったレンダリング球であっても、レンダリングモデルを構成する全てのポリゴンなどがクリップ領域の内部であるとは限らない。したがって、この場合には、例えば、クリップされなかったレンダリング球に対応するレンダリングモデルを構成するポリゴンなどについてクリップ処理を行うことが可能であるが、後述する、法線ベクトルによるグルーピング方法を採用することが好ましい。
【００３３】
図５は円錐で近似された視野とレンダリング球との関係を示す概略図である。
図において、視点位置がＯ＝（Ｘ０，Ｙ０，Ｚ０）、視線方向ベクトルがＶ１＝（Ｘ１，Ｙ１，Ｚ１）、視野角がθ１、レンダリング球の中心がＣ＝（Ｘｃ，Ｙｃ，Ｚｃ）、レンダリング球の半径がｒ、視点を始点としレンダリング球の中心を終点とするレンダリング球ベクトルがＶ２＝（Ｘ２，Ｙ２，Ｚ２）、両ベクトルのなす角がφにそれぞれ設定されている。
【００３４】
この場合には、レンダリング球の広がりを示す角度が数１になる。また、上記角φは数２になる。
【００３５】
【数１】

【００３６】
【数２】

【００３７】
したがって、角φと、角度θ１，θ２の和との大小を判定し、φ≦θ１＋θ２の場合にレンダリング球が視野内であり、φ＞θ１＋θ２の場合にレンダリング球が視野外であると判定する。
この判定は、レンダリング球の全てについて行ってもよいが、好ましくは、最上位階層の球体から順にレンダリング球まで上記の判定を行い、視野外であると判定された上位球体から発生したレンダリング球について上記の判定を省略することが好ましい。そして、以上の判定の結果、視野外にあると判定されたレンダリング球を除去し、視野内にあると判定されたレンダリング球に対応するレンダリングモデルのポリゴンのみを描画の対象とすることにより、レンダリングの高速化を達成することができる。
【００３８】
以上には、視野を円錐で近似した場合について説明したが、視野（ビューボリューム）を表示管面に合せて四角錐台領域として規定した状態において、四角錐台領域の４つの側面のそれぞれと球体の中心との距離を計算し、距離と球体の半径との大小を判定することにより視野の内部か外部かを判定するようにしてもよい。
【００３９】
上記の処理において視野内であると判定されたレンダリングモデルのポリゴンなどを表示するに当って、以下の方法を適用することにより、表示の高速化を達成することができる。
この方法は、視野内のレンダリングモデルのポリゴンなどを法線ベクトルに応じて切り代えるため、予めレンダリング球内のポリゴンなどを法線ベクトルに基づいていくつかのグループに分割し、各グループの法線ベクトルを円錐で近似しておく（図６、図７参照）。
【００４０】
図６は描画されないポリゴンなどの法線ベクトルの範囲を円錐で近似した状態を示す概略図である。なお、ここでＶ２，θ２は図５のそれらと同じである。
この場合に、上記円錐の広がり角度θ３は、θ３＝（π／２）−θ２である。
図７は２つの円錐（１つは図６の円錐と同じ円錐）を示している。図において、新たに付加された円錐の中心ベクトル（円錐の頂点を始点とし、円錐の底面の中心に向かうベクトル）をＶ３＝（Ｘ３，Ｙ３，Ｚ３）、この円錐の広がり角度をα、両ベクトルＶ２，Ｖ３のなす角をβでそれぞれ示している。
【００４１】
この場合には、角βが、数３になる。
【００４２】
【数３】

【００４３】
したがって、角θ３と、角度α，βの和との大小を判定し、θ３≦α＋βの場合に、該当する円錐の範囲に対応する法線ベクトルを有するポリゴンなどを描画の対象とし、θ３＞α＋βの場合に、該当する円錐の範囲に対応する法線ベクトルを有するポリゴンなどを描画の対象としない。この処理を採用することにより、視野内にあるレンダリング球内のポリゴンなどのうち、描画の対象とすべきポリゴンなどの抽出を高速に達成することができる。
【００４４】
さらに、表示対象となるポリゴンなどをレベル・オブ・ディテイル（以下、ＬＯＤと略称する）表示（“Ａｄａｐｔｉｖｅ Ｄｉｓｐｌａｙ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｉｎｔｅｒａｃｔｉｖｅ Ｆｒｍｅ Ｒａｔｅｓ ＤｕｒｉｎｇＶｉｓｕａｌｉｚａｔｉｏｎ ｏｆ Ｃｏｍｐｌｅｘ Ｖｉｒｔｕａｌ Ｅｎｖｉｒｏｎｍｅｎｔｓ”，Ｔｈｏｍａｓ Ａ． Ｆｕｎｋｈｏｕｓｅｒ ａｎｄＣａｒｌｏ Ｈ． 外１， ＣＯＭＰＵＴＥＲ ＧＲＡＰＨＩＣＳ Ｐｒｏｃｅｅｄｉｎｇｓ， Ａｎｎｕａｌ Ｃｏｎｆｅｒｅｎｃｅ Ｓｅｒｉｅｓ， １９９３参照）することにより、表示対象となる全てのポリゴンなどの描画および表示の所要時間を短縮することができる。
【００４５】
具体的には、図８に示すように、各レンダリングモデルに対応するポリゴンなどの複数ＬＯＤモデル（ＬＯＤ階層が異なる複数のＬＯＤモデルであり、ＬＤ０，ＬＤ１，ＬＤ２がＬＯＤ階層を示している）を予め作成しておき、図９に示すように、レンダリング球ベクトルＶ２の長さからレンダリング球の半径ｒを減算した値（原点からレンダリング球までの最小距離）の大小に応じて何れかのＬＯＤ階層を選択し、または表示を省略するようにしている。なお、何れのＬＯＤ階層を選択するかを示す閾値は、経験則などに基づいて予め設定しておく。
【００４６】
したがって、この場合には、始点から離れたポリゴンなどを簡略化して表示することができ、レンダリングモデルのより一層の高速表示を達成することができる。
図１０、図１１は階層球体モデル作成方法の一例を説明するフローチャートである。
【００４７】
図１０のフローチャートにおいては、ステップＳＰ１において最下位階層の球体の直径を設定し、ステップＳＰ２においてＤｅｌａｕｎａｙ三角分割法など、従来公知の方法により処理対象となる物体の表面をメッシュ分割し、メッシュ分割により発生した節点群を記憶し、ステップＳＰ３において図１１のフローチャートの処理（球体モデル作成処理）を行い、そのまま一連の処理を終了する。なお、ステップＳＰ２におけるメッシュ分割は、各メッシュの各辺の長さが最下位階層の球体の半径以下になるように設定される。
【００４８】
図１１のフローチャートにおいては、ステップＳＰ１において複数個の節点が存在しているか否かを判定する。そして、節点の数が複数であると判定された場合には、ステップＳＰ２において、該当する全ての節点を基に立方体領域（全節点を含む直方体または立方体）を発生し、立方体領域を内包する最小半径の球体を生成し（図１２中（Ａ）参照）、ステップＳＰ３において、分割により節点群が発生したか否か（即ち、該当する節点群が後述する分割処理により発生させられたものであるか否か）を判定する。そして、節点群が分割により発生したのではないと判定された場合には、ステップＳＰ４において、ステップＳＰ２で生成された最小球を最上位階層の球体として保存する。逆に、節点群が分割により発生したと判定された場合には、ステップＳＰ５において、ステップＳＰ２で生成された最小球を、先に行われた図１１のフローチャートの処理のステップＳＰ４またはステップＳＰ５において保存された最小球の下位の階層の球体として保存する。
【００４９】
ステップＳＰ４またはステップＳＰ５の処理が行われた後は、ステップＳＰ６において、直前に保存された最小球の中心を通り、かつ立方体領域の長手方向を法線とする平面で全節点を２分割し（図１２中（Ｂ）参照）、ステップＳＰ７において、分割された一方の節点群に対して図１１のフローチャートの処理を行い、ステップＳＰ８において、分割された残余の節点群に対して図１１のフローチャートの処理を行い、そのまま元の処理に戻る。
【００５０】
上記ステップＳＰ１において節点の数が１つであると判定された場合には、ステップＳＰ９において、分割により節点群が発生したか否か（即ち、該当する節点群が後述する分割処理により発生させられたものであるか否か）を判定する。そして、節点群が分割により発生したのではないと判定された場合には、ステップＳＰ１０において、最下位階層の球体を、その中心を節点と一致させた状態で保存する。逆に、節点群が分割により発生したと判定された場合には、ステップＳＰ１１において、最下位階層の球体を、その中心を節点と一致させた状態で、かつ先に行われた図１１のフローチャートの処理のステップＳＰ４またはステップＳＰ５において保存された最小球の下位の階層の球体として保存する。ステップＳＰ１０またはステップＳＰ１１の処理が行なわれた後は、そのまま元の処理に戻る。
【００５１】
したがって、最下位階層の球体は、図１３中（Ａ）に示すように物体の表面のメッシュ分割が行われた場合において、例えば、物体の表面の１辺に対して図１３中（Ｂ）に示すように配置される。したがって、最下位階層の球体により表現される物体形状の誤差は最下位階層の球体の半径以下になる。
また、最下位階層以外の階層の球体は、その上位の階層の球体の中心を通り、かつ立方体領域の長手方向を法線とする平面で節点群を２分割し、各区分に属する全ての節点に基づいて定まる立方体領域を含む最小半径の球体として生成されるのであるから、球体の生成処理を簡単化できる。
さらに、物体表面のみを対象として球体を生成するのであるから、物体に内包される球体はもともと生成されない。したがって、無駄な球体を削除する処理が不要であり、しかも無駄な球体が生成されないので、球体の数を少なくすることができる。
【００５２】
なお、階層の数は、最下位階層の球体の直径および対象となる物体のサイズ、形状により自動的に定まる。
ただし、図１１のフローチャートにおいて、全ての節点に基づいて定まる立方体領域を含む最小半径の球体を生成する処理に代えて、全ての節点を含む最小半径の球体を生成する処理を採用することが好ましく、球体内における物体占有率を高めることができる。
【００５３】
また、図１１のフローチャートにおいて、立方体領域の長手方向を法線とする平面に代えて、全節点の最大分散方向を法線とする平面を採用することが好ましく、分割された各節点群を含む球体内における物体占有率が大なる確率を大きくすることができる。
【００５４】
【実施例２】
図１４はこの発明の高速レンダリング装置の一実施例を示すブロック図である。ただし、このブロック図には、レンダリングモデルのクリップ処理を行う部分のみを示している。したがって、他の処理を行う部分については、従来公知の装置または以下に説明する装置を採用することになる。
【００５５】
この装置は、階層球体モデル（階層ごとの球の中心座標値、半径など）を保持する階層球体モデル保持部１と、階層球体モデルを構成する全ての階層の球体の中から、所定の値以下の半径を有する球体であって、かつ最も上位の階層の球体を抽出してレンダリング球に設定するレンダリング球設定部２（レンダリング球指定手段）と、設定された各レンダリング球に対してレンダリングモデルを対応付けるレンダリングモデル対応付け部３（レンダリングモデル割り当て手段）と、クリップ領域を規定するデータを保持するクリップ領域保持部４と、各レンダリング球がクリップ領域の内部か外部かを判定する内外判定部５と、クリップ領域の外部であると判定されたレンダリング球に対応するレンダリングモデルをクリップするクリップ処理部６とを有している。なお、構成各部の動作は図４のフローチャートの該当するステップの処理と同様であるから詳細な説明は省略してある。もちろん、これら構成各部は、ハードウェアで構成されてもよいが、図４に示す処理を行うプログラムが組み込まれたコンピュータで構成することが好ましい。
【００５６】
したがって、階層球体モデルのうち、レンダリング球として設定された球体のみに基づいてクリップ領域に対する内外判定を行い、クリップ領域の外部であると判定されたレンダリング球に対応するレンダリングモデルのクリップ処理を行うことができ、レンダリングモデルをクリップするための処理を著しく簡単化できる。この結果、レンダリングを高速化することができる。
【００５７】
ただし、レンダリングモデル対応付け部３としては、レンダリング球とレンダリングモデルとが１対１に対応しない場合に、オペレータの指示などに基づいてレンダリングモデルを１対１対応部分と多対１対応部分とに分離して新たなレンダリングモデルを作成し、新たなレンダリングモデルに基づいて対応付けを行うものであることが好ましい。
【００５８】
図１５は、視野が円錐で近似されている場合に、レンダリング球が視野の内部か外部かを判定する処理を行なう装置の構成を示すブロック図である。
この装置は、視点位置Ｏ＝（Ｘ０，Ｙ０，Ｚ０）を保持する視点位置保持部１１と、視線方向ベクトルＶ１＝（Ｘ１，Ｙ１，Ｚ１）を保持する視線方向ベクトル保持部１２と、視野角θ１を保持する視野角保持部１３と、レンダリング球の中心Ｃ＝（Ｘｃ，Ｙｃ，Ｚｃ）を保持するレンダリング球中心保持部１３ａと、レンダリング球の半径ｒを保持する半径保持部１４と、視点を始点としレンダリング球の中心を終点とするレンダリング球ベクトルＶ２＝（Ｘ２，Ｙ２，Ｚ２）を算出するレンダリング球ベクトル算出部１５と、数１に基づいてレンダリング球の広がり角度θ２を算出する広がり角度算出部１６と、数２に基づいて両ベクトルのなす角φを算出するベクトル角度算出部１７と、角度φと、角度θ１，θ２の和との大小を判定する大小判定部１８と、φ≦θ１＋θ２の場合にレンダリング球が視野内であり、φ＞θ１＋θ２の場合にレンダリング球が視野外であると判定して該当するレンダリング球を除去する内外判定部１９とを有している。なお、以上の各構成部分による処理は、全てのレンダリング球について反復的に行われる。
【００５９】
したがって、全てのレンダリング球について角度φ、θ２の算出処理、角度φと角度θ１，θ２の和との大小判定を行うことにより、レンダリング球が視野内であるか視野外であるかの判定を行うことができる。ただし、最上位階層の球体から順にレンダリング球まで内外判定を行い、視野外であると判定された上位球体から発生したレンダリング球について上記の判定を省略することが好ましい。この場合には、レンダリング球についての各保持部、各算出部、各判定部による処理を、レンダリング球よりも上位の階層の球体に対して行うようにすればよい。そして、以上の判定の結果、視野外にあると判定されたレンダリング球を除去し、視野内にあると判定されたレンダリング球に対応するレンダリングモデルのポリゴンのみを描画の対象とすることにより、レンダリングの高速化を達成することができる。
【００６０】
図１６はレンダリング球に包含されるポリゴンなどを法線ベクトルに基づいてグルーピングした場合に、各グループのポリゴンなどが描画対象であるか否かを判定するための装置の構成を示すブロック図である。なお、このブロック図においては、グルーピングを行うための処理部、グルーピングされた各区分に属する法線ベクトルの集合体を円錐で近似する処理部を図示していない。これらの処理部は、例えば、オペレータの設定入力値に基づいて必要な処理を行うものであってもよく、この場合には、例えば、設定入力値に円錐の広がり角度、円錐の中心軸を規定する中心軸ベクトルなどが含まれることになる。
【００６１】
この装置は、レンダリング球の中心Ｃ＝（Ｘｃ，Ｙｃ，Ｚｃ）を保持するレンダリング球中心保持部２１と、レンダリング球の半径ｒを保持する半径保持部２２と、視点を始点としレンダリング球の中心を終点とするレンダリング球ベクトルＶ２＝（Ｘ２，Ｙ２，Ｚ２）を算出するレンダリング球ベクトル算出部２３と、数１に基づいてレンダリング球の広がり角度θ２を算出する第１広がり角度算出部２４と、（π／２−θ２）の演算を行って描画されないポリゴンなどの法線ベクトルの範囲を近似する円錐の広がり角度θ３を算出する第２広がり角度算出部２５と、何れかのグループのポリゴンなどの法線ベクトルの範囲を規定する円錐の中心ベクトルＶ３＝（Ｘ３，Ｙ３，Ｚ３）を保持する中心ベクトル保持部２６と、この円錐の広がり角度αを保持する第３広がり角度保持部２７と、数３に基づいて両ベクトルのなす角βを算出するベクトル角度算出部２８と、角度θ３と、角度α，βの和との大小を判定する大小判定部２９と、θ３≦α＋βの場合に対応するポリゴンなどが描画対象であり、θ３＞α＋βの場合に対応するポリゴンなどが描画対象でないと判定する描画判定部３０とを有している。なお、以上の各構成部分による処理は、全ての円錐について反復的に行われる。
【００６２】
したがって、グルーピングされた各グループのポリゴンなどが描画対象であるか否かを簡単かつ高速に判定することができ、ひいてはレンダリングを高速化することができる。
図１７はレンダリングモデルを構成するポリゴンなどをＬＯＤ表示するための装置を示すブロック図である。この装置には、複数のＬＯＤモデルを作成する処理部が示されていないが、この処理部としては、従来公知の装置を採用することができる。
【００６３】
この装置は、各レンダリングモデルごとに、対応するポリゴンについて予め作成されている複数のＬＯＤモデルを保持するＬＯＤモデル保持部３１と、レンダリング球ベクトルＶ２の長さからレンダリング球の半径を減算した値を得る距離算出部３２と、算出された距離と予め設定されている１または２以上の閾値との大小を判定する大小判定部３３と、大小判定部３３による大小判定結果に応答してＬＯＤモデル保持部から該当するＬＯＤ階層のＬＯＤモデルを選択するＬＯＤモデル選択部３４と、選択されたＬＯＤモデルに基づく表示を行う表示部３５とを有している。
【００６４】
したがって、ポリゴンなどの表示に当って、簡略化されたＬＯＤモデルを選択することにより、レンダリングモデルの表示を高速化することができる。レンダリングモデルでは、遠景に多数のポリゴンなどが含まれており、これらを簡略化表示できるのであるから、著しい高速化を達成することができる。
図１８は階層構造球体モデル作成装置の一例を示すブロック図である。
【００６５】
この階層構造球体モデル作成装置は、対象物体の形状データを保持する形状データ保持部４１と、最下位階層の球体の直径の設定値を保持する直径保持部４２と、対象物体の形状データおよび最下位階層の球体の直径を入力として、従来公知の方法により対象物体の表面をメッシュ分割し、各メッシュの各辺の長さを上記直径以下に設定するメッシュ分割部４３と、メッシュ分割により得られた節点群を保持する（例えば、各節点の座標値などを保持する）メッシュデータ保持部４４と、全ての節点に基づいて定まる立方体領域を含む最小の球体を生成し、最上位階層の球体として割当てる最上位階層球体生成部４５と、最も新たに生成され、かつ未処理の球体に含まれる節点の数が複数であることを条件として、この節点群を、この球体の中心を通り、かつ立方体領域の長手方向を法線とする平面で２分割する分割部４６と、分割部４６により分割された各区分に属する節点の数が複数か否かを判定する節点数判定部４７と、節点数が複数であることを条件として、分割部４６により分割された各区分に属する全ての節点に基づいて定まる立方体領域を含む最小の球体を生成し、次の階層の球体として割当てる中間階層球体生成部４８と、節点数が１であることを条件として、該当する節点と中心とを一致させた状態で最下位階層球体を配置する最下位階層球体配置部４９とを有している。
【００６６】
なお、構成各部の作用は図１０、図１１のフローチャートの該当するステップの処理と同様であるから、詳細な説明を省略する。もちろん、これら構成各部は、ハードウェアで構成されてもよいが、図１０、図１１に示す処理を行うプログラムが組み込まれたコンピュータで構成することが好ましい。また、節点数が１になるまで分割部４６による分割処理、中間階層球体生成部４８の処理を反復させる制御部は図示を省略してある。また、２分割された各節点群を保持する保持部も図示を省略してある。
【００６７】
【発明の効果】
請求項１の発明は、多面体表現を用いた位置関係の計算が不要になり、レンダリング球を用いた干渉計算を行うことによりレンダレングモデルのクリップを高速に達成でき、ひいてはレンダリングを高速化することができるという特有の効果を奏する。
【００６８】
請求項２の発明は、物体に内包される球体はもともと生成されず、処理の複雑化を伴なうことなく、生成される球体の数を減少させることができ、このように生成された階層球体モデルに基づいて請求項１と同様の効果を奏する。
請求項３の発明は、多面体表現を用いた位置関係の計算が不要になり、描画に不要なレンダリング球の除去を円錐対円錐の高速な干渉チェックにより簡単にすることができ、ひいては描画ポリゴンの検出を高速に達成することができるという特有の効果を奏する。
【００６９】
請求項４の発明は、多面体表現を用いた位置関係の計算が不要になり、レンダリング球内のポリゴンのうち、描画の対象となるポリゴンの選択を高速に達成でき、ひいてはレンダリングを高速化することができるという特有の効果を奏する。
請求項５の発明は、一部のポリゴンについて描画精度が低いポリゴンを採用することにより描画を高速化でき、ひいてはレンダリングを高速化することができるという特有の効果を奏する。
【００７０】
請求項６の発明は、多面体表現を用いた位置関係の計算が不要になり、レンダリング球を用いた干渉計算を行うことによりレンダリングモデルのクリップを高速に達成でき、ひいてはレンダリングを高速化することができるという特有の効果を奏する。
請求項７の発明は、物体に内包される球体はもともと生成されず、処理の複雑化を伴うことなく、生成される球体の数を減少させることができ、このように生成された階層球体モデルに基づいて請求項６と同様の効果を奏する。
【００７１】
請求項８の発明は、多面体表現を用いた位置関係の計算が不要になり、描画に不要なレンダリング球の除去を円錐対円錐の高速な干渉チェックにより簡単にすることができ、ひいては描画ポリゴンの検出を高速に達成することができるという特有の効果を奏する。
請求項９の発明は、多面体表現を用いた位置関係の計算が不要になり、レンダリング球内のポリゴンのうち、描画の対象となるポリゴンの選択を高速に達成でき、ひいてはレンダリングを高速化することができるという特有の効果を奏する。
【００７２】
請求項１０の発明は、一部のポリゴンについて描画精度が低いポリゴンを採用することにより描画を高速化でき、ひいてはレンダリングを高速化することができるという特有の効果を奏する。
【図面の簡単な説明】
【図１】階層球体モデルとレンダリングモデルとの関係を示す概略図である。
【図２】レンダリング球とレンダリングモデルとが１対１で対応しない場合に、レンダリングモデルを１対１対応部分と多対１対応部分とに分離した状態を説明する概略図である。
【図３】１対１対応部分と多対１対応部分とに分離した状態におけるレンダリングモデルを示す概略図である。
【図４】高速レンダリング方法のうち、レンダリングモデルのクリップ処理を説明するフローチャートである。
【図５】円錐で近似された視野とレンダリング球との関係を示す概略図である。
【図６】描画されないポリゴンなどの法線ベクトルの範囲を円錐で近似した状態を示す概略図である。
【図７】ポリゴンなどの法線ベクトルの範囲を近似する２つの円錐の関係を示す概略図である。
【図８】各レンダリングモデルに対応するポリゴンなどの複数ＬＯＤモデルを示す概略図である。
【図９】ＬＯＤ階層と、レンダリング球ベクトルの長さからレンダリング球の半径を減算した値との関係を示す図である。
【図１０】階層球体モデル作成方法の一例の一部を説明するフローチャートである。
【図１１】階層球体モデル作成方法の一例の残部を説明するフローチャートである。
【図１２】立方体領域を含む最小半径の球体の生成処理、および全節点の２分割処理を説明する概略図である。
【図１３】物体表面のメッシュ分割、および最下位階層の球体の配置を説明する概略図である。
【図１４】この発明の高速レンダリング装置の一実施例を示すブロック図である。
【図１５】レンダリング球が円錐で近似された視野の内部か外部かを判定する装置の構成を示すブロック図である。
【図１６】レンダリング球に包含されるポリゴンなどを法線ベクトルに基づいてグルーピングした場合に、各グループのポリゴンなどが描画対象であるか否かを判定するための装置の構成を示すブロック図である。
【図１７】レンダリングモデルを構成するポリゴンなどをＬＯＤ表示するための装置を示すブロック図である。
【図１８】階層球体モデル作成装置の一例を示すブロック図である。
【符号の説明】
２ レンダリング球設定部 ３ レンダリングモデル対応付け部
５ 内外判定部 ６ クリップ処理部
１２ 視線方向ベクトル保持部 １３ 視野角保持部
１５ レンダリング球ベクトル算出部 １６ 広がり角度算出部
１８ 大小判定部 １９ 内外判定部
２４ 第１広がり角度算出部 ２５ 第２広がり角度算出部
２６ 中心ベクトル保持部 ２７ 第３広がり角度保持部
２９ 大小判定部 ３０ 描画判定部
３１ ＬＯＤモデル保持部 ３２ 距離算出部
３３ 大小判定部 ３４ ＬＯＤモデル選択部
３５ 表示部 ４３ メッシュ分割部
４５ 最上位階層球体生成部 ４６ 分割部
４８ 中間階層球体生成部 ４９ 最下位階層球体生成部[0001]
[Industrial application fields]
The present invention relates to a high-speed rendering method and apparatus, and more particularly, to a high-speed rendering method and apparatus for reducing the drawing time of a three-dimensional model without reducing visual effects. This method and its apparatus can be suitably applied to fields such as landscape simulation and artificial reality.
[0002]
[Prior art]
In recent years, research on landscape simulation and scientific visualization using computer graphics (hereinafter abbreviated as CG) technology has been actively conducted, as well as research on artificial reality such as walkthroughs and flight simulators. It is actively done. Here, the former mainly targets still images, while the latter targets moving images. Accordingly, in general, high-speed drawing is strongly required as a CG technique applied to the latter. However, even in the former case, there is a case where there is a huge amount of data especially like a landscape simulation, so that high-speed drawing is still required. In any case, it is required to achieve high speed without reducing the visual effect.
[0003]
Conventionally, the following three methods have been proposed as methods for achieving this requirement.
(1) Three-dimensional solids are grouped by space division, inside / outside determination for the field of view is performed for each group, and only the group determined to be within the field of view is drawn, so that the corresponding 3D model can be drawn at high speed. ("Wide area 3D object management system", Takashi Tamada, Yasuaki Nakamura, TECHNICAL REPORT OF IEICE HC93-11 (1993-05), The Institute of Electronics, Information and Communication Engineers)
(2) A method for performing a stepwise simplified representation of a shape, for example, displaying a shape as it is when the distance from the viewpoint is small, and displaying a simplified shape when the distance from the viewpoint is large, how to speed up rendering of the entire relevant 3-dimensional model ( "Adaptive Display Algorithm for Interactive Frme Rates During Visualization of Complex Virtual Environments", Thomas A. Funkhouser and Carlo H. out 1, COMPUTER GRAPHICS Proceedings, Annual Conference Series, 1993), and
[0004]
[Outside 1]

[0005]
(3) Perform grouping of surfaces according to the direction of the line of sight, determine whether each group can be seen from the viewpoint, and draw only the group that is determined to be visible, and draw the corresponding 3D model. Speeding up method ("Shaping grouping for real-time landscape simulator and reduction of drawing time based on multiple representations", Katsuhiro Kitajima, Yoko Yusa, IEICE Transactions D-II Vol. J77-D-II No. 2 pp. 311-320 February 1994)
[0006]
[Problems to be solved by the invention]
However, the above conventional methods are all methods for selecting polygons to be drawn based on the positional relationship between the viewpoint and the drawn object, and the positional relationship is calculated using a polyhedral representation such as a cubic region and octree. There is an inconvenience of cost. Then, due to the calculation cost, the time required for selecting the drawing polygon becomes long, and the time required for drawing becomes long.
[0007]
OBJECT OF THE INVENTION
The present invention has been made in view of the above problems, and an object of the present invention is to provide a high-speed rendering method and apparatus capable of significantly reducing the time required for selecting drawn polygons.
[0008]
[Means for Solving the Problems]
The high speed rendering method of claim 1 comprises: Floors held in the hierarchical sphere model holding unit (1) Among the spheres of the layered sphere model, the sphere of the highest hierarchy among the spheres with a predetermined radius or less is designated as the rendering sphere, and a rendering model is assigned to each rendering sphere, and whether the rendering sphere is inside the clip area. In this method, it is determined whether the rendering model is external, and the rendering model is clipped when the rendering sphere is outside the clipping region.
[0009]
The high-speed rendering method according to claim 2, wherein the surface of the object to be modeled is divided into meshes, and the lengths of all sides of each mesh-divided mesh are equal to or less than a diameter of a sphere in the lowest hierarchy. Set to And is held by the mesh data holding unit (44) The lowest sphere is generated around each node, and then the smallest sphere including the cubic region determined based on all nodes is generated as the highest sphere, and then the top sphere is centered. All nodes are divided into two on the plane passing through, and the smallest sphere including the cubic region determined based on all the nodes belonging to each divided section is generated to be the sphere of the next hierarchy of the hierarchy before the division, and then By repeating the process of dividing all nodes into two and generating the smallest sphere including the cubic region determined based on all the nodes belonging to each section and making it the next sphere until the number of nodes after division becomes 1 This is a method of creating a hierarchical sphere model.
[0010]
The fast rendering method according to claim 3 is: View held in the viewpoint position holding unit (11) Based on point position The visual direction held by the line-of-sight vector holding unit (12) Line direction vector and And viewing angle held by the viewing angle holding part (13) If the field of view is defined by the field angle, The label held in the rendering sphere center holding portion (13a) Calculate the vector that goes to the center of the dulling sphere and the angle that defines the spread of the rendering sphere around this vector, and the angle between both vectors is greater than the sum of the viewing angle and the angle that defines the spread of the rendering sphere This is a method of removing the corresponding rendering sphere on the condition.
[0011]
The high-speed rendering method according to claim 4, with respect to a rendering sphere at least partially included in the field of view, the polygons included in the rendering sphere are divided into a plurality of groups based on the directions of the respective normal vectors. Approximate a collection of polygon normals to which it belongs with a cone, The label held in the rendering sphere center holding part (21). A first spread angle that defines the spread of the rendering sphere centered on a vector directed to the center of the dulling sphere, and a central axis vector that defines a central axis of a cone that approximates a collection of polygon normals, and the cone The second divergence angle is calculated, and polygons belonging to the corresponding category are drawn on condition that the angle formed by the vector from the viewpoint toward the center of the rendering sphere and the central axis vector is less than or equal to the sum of both divergence angles. How to choose.
[0012]
The high-speed rendering method according to claim 5 generates, in advance, a plurality of polygons having different drawing accuracy in correspondence with the magnitude of a vector from the viewpoint toward the center of the rendering sphere for the polygon corresponding to each rendering model. Held in the LOD model holding unit (31) In this method, a polygon having a corresponding drawing accuracy is drawn based on the actual size of the vector.
The high-speed rendering device according to claim 6 includes: a rendering sphere designating unit that designates a sphere of the highest hierarchy as a rendering sphere among spheres having a predetermined radius or less of the hierarchical sphere model; and a rendering model corresponding to each rendering sphere. Applicable in response to the determination results of the rendering model assigning means for assigning, the inside / outside judging means for judging whether the rendering sphere is inside or outside the clip area, and the inside / outside judging means showing that the rendering sphere is outside the clip area Clip means for clipping the rendering model.
[0013]
The high-speed rendering apparatus according to claim 7, wherein the surface of the object to be modeled is mesh-divided, and the length of all sides of each mesh-divided mesh is equal to or less than a diameter of a sphere in the lowest hierarchy. The mesh division means to set to, the lowest hierarchy sphere generation means for generating the lowest layer sphere around each node generated by the mesh division, and the smallest sphere including the cubic region determined based on all the nodes A top-level sphere generating means to be a top-level sphere, Top level at the time of processing A dividing means for dividing all nodes into two on a plane passing through the center of the sphere, and a minimum sphere including a cubic region determined based on all the nodes belonging to each divided section, It further has an intermediate layer sphere generating means for forming a sphere of a hierarchy, and an iterative control means for repeating the processing by the dividing means and the processing by the intermediate layer sphere generating means until the number of nodes after division becomes 1.
[0014]
The high-speed rendering apparatus according to claim 8 includes a holding unit that holds a line-of-sight direction vector and a viewing angle set with respect to a viewpoint position in order to define a field of view, a vector from the viewpoint toward the center of the rendering sphere, and the vector First calculating unit for calculating an angle defining the spread of the rendering sphere as a center, and determining whether an angle formed by both vectors is larger than a sum of a viewing angle and an angle defining the spread of the rendering sphere Rendering that removes the rendering sphere in response to a determination result of the first size determination means indicating that the angle between the determination means and the angle formed by both vectors is larger than the sum of the viewing angle and the angle that defines the spread of the rendering sphere And a ball removing means.
[0015]
The high-speed rendering apparatus according to claim 9, with respect to a rendering sphere that includes at least a part in the field of view, a partitioning unit that divides the polygons included in the rendering sphere into a plurality of groups based on directions of the respective normal vectors; Approximating means for approximating a collection of polygon normals belonging to each section with a cone, and first calculating means for calculating a first spread angle that defines the spread of the rendering sphere with a vector from the viewpoint toward the center of the rendering sphere as a center. A center axis vector that defines a center axis of a cone that approximates a collection of polygon normals, a second calculation means that calculates a second spread angle of the cone, and a vector and center from the viewpoint toward the center of the rendering sphere Second magnitude determining means for determining whether or not the angle formed by the axis vector is equal to or less than the sum of both spread angles, and rendering from the viewpoint In response to the determination result of the second size determining means indicating that the angle formed between the vector directed to the center of the ring sphere and the center axis vector is equal to or less than the sum of both spread angles, polygons belonging to the corresponding category are drawn. And selecting means for selecting.
[0016]
The high-speed rendering apparatus according to claim 10, wherein polygon generation corresponding to each rendering model is generated in advance by generating a plurality of polygons having different drawing accuracy in correspondence with the magnitude of a vector from the viewpoint toward the center of the rendering sphere. And drawing means for drawing a polygon having a drawing accuracy corresponding to the actual size of the vector.
[0017]
[Action]
If it is the high-speed rendering method of claim 1, Floors held in the hierarchical sphere model holding unit (1) Among the spheres of the layered sphere model, the sphere of the highest hierarchy among the spheres with a predetermined radius or less is designated as the rendering sphere, and a rendering model is assigned to each rendering sphere, and whether the rendering sphere is inside the clip area. If the rendering sphere is outside the clipping area, the corresponding rendering model is clipped by determining whether it is external, so there is no need to calculate the positional relationship using multi-faceted expressions, and interference using the rendering sphere By performing the calculation, the clip of the rendering model can be achieved at high speed, and as a result, the rendering can be speeded up.
[0018]
According to the high-speed rendering method of claim 2, the surface of the object to be modeled is divided into meshes, and the spheres in the lowest hierarchy in which the lengths of all sides of each mesh divided are set in advance. Set below the diameter and generate by mesh division. And is held by the mesh data holding unit (44) The sphere of the lowest hierarchy is generated around each node, and then the smallest sphere including the cubic region determined based on all the nodes is generated as the sphere of the highest hierarchy, and then the center of the sphere of the previous hierarchy All nodes are divided into two on the plane passing through, and the smallest sphere including the cubic region determined based on all the nodes belonging to each divided section is generated to be the sphere of the next hierarchy of the hierarchy before the division, and then The process of dividing all nodes into two and the process of generating the smallest sphere including a cubic region determined based on all the nodes belonging to each section and making it the sphere of the next hierarchy is repeated until the number of divided nodes becomes 1. Therefore, the sphere contained in the object is not generated originally, and the number of generated spheres can be reduced without complicating the processing. Generated hierarchy It can achieve the effect similar to those of claim 1 on the basis of body model.
[0019]
If it is the high-speed rendering method of claim 3, View held in the viewpoint position holding unit (11) Based on point position The visual direction held by the line-of-sight vector holding unit (12) Line direction vector and And viewing angle held by the viewing angle holding part (13) If the field of view is defined by the field angle, The label held in the rendering sphere center holding portion (13a) Calculate the vector that goes to the center of the dulling sphere and the angle that defines the spread of the rendering sphere around this vector, and the angle between both vectors is greater than the sum of the viewing angle and the angle that defines the spread of the rendering sphere Since the corresponding rendering sphere is removed on the condition, it is not necessary to calculate the positional relationship using multi-faceted expressions, and it is easy to remove the rendering sphere unnecessary for drawing by the high-speed cone-to-cone interference check. As a result, detection of a drawing polygon can be achieved at high speed.
[0020]
According to the high-speed rendering method of claim 4, with respect to the rendering sphere including at least a part in the field of view, the polygons included in the rendering sphere are divided into a plurality of groups based on the directions of the respective normal vectors. Approximate a collection of polygon normals belonging to a section with a cone The label held in the rendering sphere center holding part (21). A first spread angle that defines the spread of the rendering sphere centered on a vector directed to the center of the dulling sphere, and a central axis vector that defines a central axis of a cone that approximates a collection of polygon normals, and the cone The second divergence angle is calculated, and polygons belonging to the corresponding category are drawn on condition that the angle formed by the vector from the viewpoint toward the center of the rendering sphere and the central axis vector is less than or equal to the sum of both divergence angles. Since it is selected, it is not necessary to calculate the positional relationship using the polyhedron expression, and among the polygons in the rendering sphere, the polygon to be drawn can be selected at a high speed, and as a result, the rendering can be speeded up. it can.
[0021]
In the high-speed rendering method according to claim 5, a plurality of polygons having different drawing accuracy are generated in advance for each polygon corresponding to each rendering model in correspondence with the magnitude of a vector from the viewpoint toward the center of the rendering sphere. Held in the LOD model holding unit (31) Since the polygons with the corresponding drawing accuracy are drawn based on the actual size of the above vector, drawing can be speeded up by adopting polygons with low drawing accuracy for some of the polygons, and as a result, the rendering speed is increased. Can be
[0022]
In the high-speed rendering device according to claim 6, among the spheres having a predetermined radius or less in the hierarchical sphere model, the sphere of the highest hierarchy is specified as a rendering sphere by the rendering sphere specifying means, and each rendering model assigning means Assign a rendering model corresponding to the rendering sphere. Then, the internal / external determination means determines whether the rendering sphere is inside or outside the clip area, and the corresponding rendering model is output by the clip means in response to the determination result of the internal / external determination means indicating that the rendering sphere is outside the clip area. Clip. Therefore, the calculation of the positional relationship using the polyhedron representation becomes unnecessary, and the rendering model clip can be achieved at high speed by performing the interference calculation using the rendering sphere, and thus rendering can be speeded up.
[0023]
In the high-speed rendering device according to claim 7, the surface of the object to be modeled is divided into meshes, and the spheres in the lowest hierarchy in which the lengths of all sides of each mesh divided are set in advance. A mesh dividing means for setting the diameter below the diameter, a lowest hierarchy sphere generating means for generating a sphere of the lowest hierarchy around each node generated by the mesh division, and a minimum sphere including a cubic region determined based on all the nodes. A top layer sphere generating means for generating a top layer sphere; Top level at the time of processing A dividing means for dividing all nodes into two on a plane passing through the center of the sphere, and a minimum sphere including a cubic region determined based on all the nodes belonging to each divided section, It further has an intermediate hierarchy sphere generating means for forming a sphere of a hierarchy, and an iterative control means for repeating the process by the dividing means and the process by the intermediate hierarchy sphere generating means until the number of nodes after division becomes 1. From the above, the sphere contained in the object is not originally generated, and the number of generated spheres can be reduced without complicating the processing, and the claim is based on the hierarchical sphere model thus generated. The same effect as 6 can be achieved.
[0024]
In the high-speed rendering device according to claim 8, in order to define the field of view, holding means for holding a line-of-sight direction vector and a field angle set with reference to the viewpoint position, a vector from the viewpoint toward the center of the rendering sphere, Calculating means for calculating an angle defining the spread of the rendering sphere centered on the vector; and determining whether the angle formed by both vectors is greater than the sum of the viewing angle and the angle defining the spread of the rendering sphere. The corresponding rendering sphere is removed in response to the determination result of the first size determination means indicating that the angle formed by the one size determination means and the angle between both vectors is larger than the sum of the viewing angle and the angle defining the spread of the rendering sphere. And a rendering sphere removing means that does not need to calculate the positional relationship using the polyhedral representation. The removal of the ring ball can be simplified by a high-speed interference checking cone pair cone can thus achieve the detection of the drawing polygons at high speed.
[0025]
10. The high-speed rendering apparatus according to claim 9, wherein the rendering sphere including at least a part in the field of view is configured to classify the polygons included in the rendering sphere into a plurality of groups based on the directions of the respective normal vectors. And an approximation means for approximating a collection of normal lines of polygons belonging to each section with a cone, and a first spread angle that defines a spread of the rendering sphere centered on a vector from the viewpoint toward the center of the rendering sphere. A calculation means; a central axis vector that defines a central axis of a cone approximating an aggregate of polygon normals; a second calculation means that calculates a second spread angle of the cone; and a vector from the viewpoint toward the center of the rendering sphere A second magnitude judging means for judging whether or not an angle formed by the center axis vector is equal to or less than a sum of both spread angles, and from a viewpoint In response to the determination result of the second size determining means indicating that the angle formed by the vector directed to the center of the dundling sphere and the center axis vector is equal to or less than the sum of the two spread angles, polygons belonging to the corresponding category are drawn. Since there is a selection means to select, it is not necessary to calculate the positional relationship using polyhedral representation, and among the polygons in the rendering sphere, the polygon to be drawn can be selected at high speed. As a result, rendering can be speeded up.
[0026]
In the high-speed rendering apparatus according to claim 10, a plurality of polygons having different drawing accuracy are generated in advance for each polygon corresponding to each rendering model in correspondence with the magnitude of a vector from the viewpoint toward the center of the rendering sphere. Since it further includes a polygon generating means and a drawing means for drawing a polygon having a drawing accuracy corresponding to the actual size of the vector, a polygon having a low drawing accuracy is adopted for some polygons. Thus, drawing can be speeded up, and in turn rendering can be speeded up.
[0027]
【Example】
Hereinafter, the present invention will be described in detail with reference to the accompanying drawings showing embodiments.
FIG. 1 is a schematic diagram showing the relationship between a hierarchical sphere model and a rendering model.
In the figure, the spheres of each layer constituting the hierarchical sphere model are indicated by ellipses having different sizes. In addition, this hierarchical sphere model is created by performing division processing in order from the sphere of the highest hierarchy. In this case, spheres S1, S2, and S3 having radii equal to or less than a predetermined value are generated. In this case, the spheres S1, S2, and S3 are set as rendering spheres, and are associated with the rendering models L1, L2, and L3, respectively. However, among the spheres having a radius equal to or smaller than a predetermined value, only the sphere at the highest level is set as the rendering sphere. Therefore, a sphere in a lower hierarchy than the rendering sphere is not a rendering sphere. Further, the above value is specified so that the radius of the rendering sphere is sufficiently larger than the radius of the sphere at the lowest hierarchy. Furthermore, the rendering models L1, L2, and L3 are models including shape information such as polygons included in the corresponding rendering sphere.
[0028]
When the rendering sphere and the rendering model are associated as described above, the rendering sphere and the rendering model may not correspond one-to-one. In such a case, as shown in FIG. 2, the rendering model is separated into one-to-one corresponding portions L1 ′ and L2 ′ and a many-to-one corresponding portion L12 ′, and a new rendering model is generated. The relationship between the original rendering models L1, L2 corresponding to the case of FIG. 2 and the new rendering models L1 ′, L2 ′, L12 ′ is as shown in FIG.
[0029]
Therefore, if the rendering sphere is set in this way and a rendering model is associated with each rendering sphere, it is determined whether each rendering sphere is inside or outside the clip area, and is outside the clip area. By clipping only the determined rendering sphere, the rendering model can be easily clipped.
[0030]
In the rendering model clipping process, for example, as shown in the flowchart of FIG. 4, a rendering sphere is set in step SP1, a rendering model is associated with each rendering sphere in step SP2, and for each rendering sphere in step SP3. Then, it is determined whether the set clip area is inside or outside, and if it is determined that the rendering sphere is outside the clip area, in step SP4, the corresponding rendering sphere is clipped, and in step SP5, all the rendering spheres are clipped. It is determined whether or not processing has been performed on the rendering sphere. If there is a rendering sphere that has not been processed, the processing in step SP3 is performed again. Conversely, if it is determined in step SP5 that the processing has been performed for all the rendering spheres, the series of processing ends. If it is determined in step SP3 that the rendering sphere is inside the clip area, the processing in step SP3 is performed again.
[0031]
Therefore, the inside / outside determination for the clip area is performed based only on the sphere set as the rendering sphere among the hierarchical sphere models, and the rendering model corresponding to the rendering sphere determined to be outside the clip area is clipped. Can greatly simplify the process of clipping the rendering model. As a result, rendering can be speeded up.
[0032]
However, even if the rendering sphere has not been clipped, not all polygons constituting the rendering model are necessarily inside the clip area. Therefore, in this case, for example, it is possible to perform clipping processing on polygons constituting a rendering model corresponding to a rendering sphere that has not been clipped, but a grouping method based on normal vectors, which will be described later, should be adopted. Is preferred.
[0033]
FIG. 5 is a schematic diagram showing the relationship between the field of view approximated by a cone and the rendering sphere.
In the figure, the viewpoint position is O = (X0, Y0, Z0), the line-of-sight direction vector is V1 = (X1, Y1, Z1), the viewing angle is θ1, the center of the rendering sphere is C = (Xc, Yc, Zc), The rendering sphere radius is set to r, the rendering sphere vector starting from the viewpoint and the center of the rendering sphere is set to V2 = (X2, Y2, Z2), and the angle formed by both vectors is set to φ.
[0034]
In this case, the angle indicating the spread of the rendering sphere is expressed by Equation 1. Further, the angle φ is expressed by Formula 2.
[0035]
[Expression 1]

[0036]
[Expression 2]

[0037]
Therefore, the magnitude of the angle φ and the sum of the angles θ1 and θ2 is determined. When φ ≦ θ1 + θ2, the rendering sphere is in the field of view, and when φ> θ1 + θ2, the rendering sphere is determined to be out of the field of view.
This determination may be performed for all of the rendering spheres. Preferably, the above determination is performed in order from the sphere of the highest hierarchy to the rendering sphere, and the rendering sphere generated from the upper sphere determined to be out of the field of view. It is preferable to omit the above determination. As a result of the above determination, the rendering sphere determined to be out of the field of view is removed, and only the rendering model polygon corresponding to the rendering sphere determined to be within the field of view is rendered. High speed can be achieved.
[0038]
The case where the field of view is approximated by a cone has been described above. However, in the state where the field of view (view volume) is defined as a quadrangular frustum region in accordance with the display tube surface, each of the four side surfaces of the quadrangular frustum region and the sphere It is also possible to determine whether the distance is inside or outside the field of view by calculating the distance from the center of the eye and determining the magnitude of the distance and the radius of the sphere.
[0039]
In displaying the rendering model polygon or the like determined to be within the field of view in the above processing, the display speed can be increased by applying the following method.
This method switches polygons in the rendering model in the field of view according to the normal vector, so the polygons in the rendering sphere are divided into several groups based on the normal vector in advance, and the normals of each group The vector is approximated by a cone (see FIGS. 6 and 7).
[0040]
FIG. 6 is a schematic diagram showing a state in which a normal vector range such as a polygon not drawn is approximated by a cone. Here, V2 and θ2 are the same as those in FIG.
In this case, the cone spreading angle θ3 is θ3 = (π / 2) −θ2.
FIG. 7 shows two cones (one is the same cone as in FIG. 6). In the figure, V3 = (X3, Y3, Z3) is the newly added cone center vector (vector starting from the cone vertex and going to the center of the cone bottom), α is the spread angle of this cone, both vectors The angle formed by V2 and V3 is indicated by β.
[0041]
In this case, the angle β is expressed by Equation 3.
[0042]
[Equation 3]

[0043]
Therefore, the magnitude of the angle θ3 and the sum of the angles α and β is determined, and when θ3 ≦ α + β, a polygon having a normal vector corresponding to the corresponding cone range is drawn, and θ3> α + β In this case, polygons having normal vectors corresponding to the corresponding cone range are not drawn. By adopting this processing, it is possible to rapidly extract polygons to be drawn among polygons in the rendering sphere in the field of view.
[0044]
Furthermore, polygons and the like to be displayed are displayed in a level of detail (hereinafter abbreviated as LOD) display (“Adaptive Display Algorithm for Interactive Frames and Compensation of Complementary Complex. By referring to GRAPHICS Proceedings, Annual Conference Series, 1993), it is possible to reduce the time required for drawing and displaying all polygons to be displayed.
[0045]
Specifically, as shown in FIG. 8, a plurality of LOD models such as polygons corresponding to each rendering model (a plurality of LOD models having different LOD layers, and LD0, LD1, and LD2 indicate LOD layers). As shown in FIG. 9, any LOD hierarchy is created according to the magnitude of the value obtained by subtracting the radius r of the rendering sphere from the length of the rendering sphere vector V2 (minimum distance from the origin to the rendering sphere). Is selected or the display is omitted. Note that a threshold indicating which LOD layer to select is set in advance based on an empirical rule or the like.
[0046]
Therefore, in this case, a polygon or the like away from the starting point can be displayed in a simplified manner, and a higher speed display of the rendering model can be achieved.
10 and 11 are flowcharts for explaining an example of a hierarchical sphere model creation method.
[0047]
In the flowchart of FIG. 10, the diameter of the sphere of the lowest hierarchy is set in step SP1, and the surface of the object to be processed is mesh-divided by a conventionally known method such as the Delaunay triangulation method in step SP2. The generated node group is stored, the process of the flowchart of FIG. 11 (spherical model creation process) is performed in step SP3, and the series of processes is finished as it is. Note that the mesh division in step SP2 is set so that the length of each side of each mesh is equal to or less than the radius of the sphere in the lowest hierarchy.
[0048]
In the flowchart of FIG. 11, it is determined in step SP1 whether or not there are a plurality of nodes. If it is determined that the number of nodes is plural, in step SP2, a cubic region (a rectangular parallelepiped or a cube including all the nodes) is generated based on all the corresponding nodes, and the minimum that includes the cubic region. A sphere having a radius is generated (see (A) in FIG. 12), and whether or not a node group is generated by the division in step SP3 (that is, the corresponding node group is generated by a division process described later). Whether or not). If it is determined that the node group is not generated by the division, in step SP4, the smallest sphere generated in step SP2 is stored as a sphere of the highest hierarchy. Conversely, if it is determined that the node group has been generated by the division, the minimum sphere generated in step SP2 is determined in step SP5 in step SP4 or step SP5 of the process in the flowchart of FIG. Save as a sphere below the saved minimum sphere.
[0049]
After the processing of step SP4 or step SP5 is performed, in step SP6, all the nodes are divided into two on a plane that passes through the center of the smallest sphere stored immediately before and is normal to the longitudinal direction of the cubic region ( In step SP7, the process of the flowchart of FIG. 11 is performed on one of the divided node groups, and in step SP8, the flowchart of FIG. 11 is applied to the remaining node group that has been divided. And return to the original process.
[0050]
If it is determined in step SP1 that the number of nodes is one, in step SP9, whether or not a node group is generated by the division (that is, the corresponding node group is generated by a division process described later). Or not). If it is determined that the node group is not generated by the division, the sphere of the lowest hierarchy is stored in a state where the center thereof coincides with the node in step SP10. On the other hand, if it is determined that the node group has been generated by the division, the flow chart of FIG. 11 is performed in a state where the center of the sphere of the lowest hierarchy is matched with the node in step SP11. This is stored as a sphere in the lower hierarchy of the minimum sphere stored in step SP4 or step SP5 of the process. After the process of step SP10 or step SP11 is performed, the process returns to the original process.
[0051]
Therefore, when the sphere of the lowest hierarchy is subjected to mesh division of the surface of the object as shown in FIG. 13A, for example, in FIG. Arranged as shown. Therefore, the error of the object shape expressed by the sphere in the lowest hierarchy is less than the radius of the sphere in the lowest hierarchy.
In addition, a sphere of a hierarchy other than the lowest hierarchy passes through the center of the sphere of the higher hierarchy and divides the node group into two on a plane whose normal is the longitudinal direction of the cube area, and all the nodes belonging to each division Since it is generated as a sphere with the minimum radius including a cubic region determined based on the sphere, the sphere generation process can be simplified.
Furthermore, since the sphere is generated only for the object surface, the sphere included in the object is not generated originally. Therefore, the process of deleting useless spheres is unnecessary, and no useless spheres are generated, so the number of spheres can be reduced.
[0052]
The number of layers is automatically determined by the diameter of the sphere at the lowest layer and the size and shape of the target object.
However, in the flowchart of FIG. 11, it is preferable to employ a process for generating a sphere with a minimum radius including all nodes instead of a process for generating a sphere with a minimum radius including a cubic region determined based on all the nodes. The object occupancy rate in the sphere can be increased.
[0053]
In addition, in the flowchart of FIG. 11, it is preferable to adopt a plane whose normal is the maximum dispersion direction of all nodes instead of the plane whose normal is the longitudinal direction of the cubic region, and includes each divided node group. It is possible to increase the probability that the object occupancy rate in the sphere is large.
[0054]
[Example 2]
FIG. 14 is a block diagram showing an embodiment of the high speed rendering apparatus of the present invention. However, this block diagram shows only the portion of the rendering model that performs clip processing. Therefore, a conventionally known device or a device described below is adopted for a portion that performs other processing.
[0055]
This apparatus includes a hierarchical sphere model holding unit 1 that holds a hierarchical sphere model (the center coordinate value, radius, etc. of each sphere), and a predetermined value or less from spheres of all hierarchies constituting the hierarchical sphere model. A rendering sphere setting unit 2 (rendering sphere designating means) that extracts a sphere having a radius of and having the highest hierarchy and sets it as a rendering sphere, and a rendering model for each of the set rendering spheres. A rendering model associating unit 3 (rendering model allocating means) to be associated; a clip region retaining unit 4 that retains data defining a clip region; an inside / outside determining unit 5 that determines whether each rendering sphere is inside or outside the clip region; Clip processing that clips the rendering model corresponding to the rendering sphere determined to be outside the clip area And a part 6. Note that the operation of each component is the same as that of the corresponding step in the flowchart of FIG. Of course, each of these components may be configured by hardware, but is preferably configured by a computer in which a program for performing the processing shown in FIG. 4 is incorporated.
[0056]
Therefore, the inside / outside determination for the clip area is performed based only on the sphere set as the rendering sphere among the hierarchical sphere models, and the rendering model corresponding to the rendering sphere determined to be outside the clip area is clipped. Can greatly simplify the process of clipping the rendering model. As a result, rendering can be speeded up.
[0057]
However, when the rendering sphere and the rendering model do not correspond one-to-one, the rendering model associating unit 3 converts the rendering model into a one-to-one corresponding part and a many-to-one corresponding part based on an operator's instruction or the like. It is preferable that a new rendering model is created by separation and the association is performed based on the new rendering model.
[0058]
FIG. 15 is a block diagram illustrating a configuration of an apparatus that performs processing for determining whether the rendering sphere is inside or outside the field of view when the field of view is approximated by a cone.
This apparatus includes a viewpoint position holding unit 11 that holds a viewpoint position O = (X0, Y0, Z0), a line-of-sight direction vector holding unit 12 that holds a line-of-sight direction vector V1 = (X1, Y1, Z1), and a viewing angle. A viewing angle holding unit 13 that holds θ1, a rendering sphere center holding unit 13a that holds the center C = (Xc, Yc, Zc) of the rendering sphere, a radius holding unit 14 that holds the radius r of the rendering sphere, and a viewpoint A rendering sphere vector calculation unit 15 that calculates a rendering sphere vector V2 = (X2, Y2, Z2) starting from the center of the rendering sphere, and a spread angle that calculates the spread angle θ2 of the rendering sphere based on Equation 1 The calculation unit 16, the vector angle calculation unit 17 that calculates the angle φ formed by both vectors based on Equation 2, and the magnitude of the angle φ and the sum of the angles θ 1 and θ 2 are determined. A small determination unit 18 and an internal / external determination unit 19 that determines that the rendering sphere is in the field of view when φ ≦ θ1 + θ2 and that the rendering sphere is out of the field of view when φ> θ1 + θ2, and removes the corresponding rendering sphere. Have. Note that the processing by each component described above is repeatedly performed for all rendering spheres.
[0059]
Therefore, it is determined whether or not the rendering sphere is in the field of view or out of the field of view by calculating the angles φ and θ2 and determining the size of the angle φ and the sum of the angles θ1 and θ2 for all the rendering spheres. be able to. However, it is preferable that the inside / outside determination is performed in order from the top-level sphere to the rendering sphere, and the above determination is omitted for the rendering sphere generated from the top sphere determined to be out of the field of view. In this case, the processing by each holding unit, each calculation unit, and each determination unit for the rendering sphere may be performed on a sphere in a higher hierarchy than the rendering sphere. As a result of the above determination, the rendering sphere determined to be out of the field of view is removed, and only the rendering model polygon corresponding to the rendering sphere determined to be within the field of view is rendered. High speed can be achieved.
[0060]
FIG. 16 is a block diagram showing a configuration of an apparatus for determining whether or not a polygon in each group is a drawing target when the polygons included in the rendering sphere are grouped based on a normal vector. . In this block diagram, a processing unit for performing grouping and a processing unit for approximating a collection of normal vectors belonging to each grouped group by a cone are not illustrated. These processing units may perform necessary processing based on, for example, an operator set input value. In this case, for example, the cone input angle and the center axis of the cone are defined in the set input value. The center axis vector to be included is included.
[0061]
This apparatus includes a rendering sphere center holding unit 21 that holds the center C of the rendering sphere C = (Xc, Yc, Zc), a radius holding unit 22 that holds the radius r of the rendering sphere, and the center of the rendering sphere starting from the viewpoint. A rendering sphere vector V2 = (X2, Y2, Z2), and a first divergence angle calculation unit 24 that calculates a sphere spread angle θ2 based on Equation 1. A second spread angle calculation unit 25 for calculating a cone spread angle θ3 that approximates a range of a normal vector such as a polygon that is not drawn by performing a calculation of (π / 2−θ2), and a polygon of any group A center vector holding unit 26 that holds the center vector V3 = (X3, Y3, Z3) of the cone that defines the range of the normal vector, and the extent of this cone The third spread angle holding unit 27 that holds the degree α, the vector angle calculation unit 28 that calculates the angle β formed by both vectors based on Equation 3, the angle θ3 and the sum of the angles α and β are determined. And a drawing determination unit 30 that determines that a polygon corresponding to θ3 ≦ α + β is a drawing target and determines that a polygon corresponding to θ3> α + β is not a drawing target. . In addition, the process by the above each component is repeatedly performed about all the cones.
[0062]
Therefore, it can be determined easily and at high speed whether or not the grouped polygons and the like are to be rendered, and as a result, rendering can be speeded up.
FIG. 17 is a block diagram showing an apparatus for LOD display of polygons constituting a rendering model. Although this apparatus does not show a processing section for creating a plurality of LOD models, a conventionally known apparatus can be adopted as this processing section.
[0063]
This apparatus includes, for each rendering model, an LOD model holding unit 31 that holds a plurality of LOD models created in advance for the corresponding polygon, and a value obtained by subtracting the radius of the rendering sphere from the length of the rendering sphere vector V2. LOD model holding in response to the magnitude determination result obtained by the magnitude calculation unit 32, the magnitude judgment unit 33 for judging the magnitude of the calculated distance and one or more preset thresholds, and the magnitude judgment unit 33 An LOD model selection unit 34 that selects an LOD model of the corresponding LOD hierarchy from the unit, and a display unit 35 that performs display based on the selected LOD model.
[0064]
Therefore, the display of the rendering model can be speeded up by selecting a simplified LOD model when displaying a polygon or the like. In the rendering model, a large number of polygons are included in a distant view, and these can be displayed in a simplified manner, so that significant speedup can be achieved.
FIG. 18 is a block diagram illustrating an example of a hierarchical sphere model creation device.
[0065]
This hierarchical structure sphere model creation device includes a shape data holding unit 41 that holds shape data of a target object, a diameter holding unit 42 that holds a set value of the diameter of a sphere in the lowest hierarchy, shape data of the target object, By inputting the diameter of the lower layer sphere as an input, the surface of the target object is mesh-divided by a conventionally known method, and the mesh division unit 43 that sets the length of each side of each mesh to be equal to or smaller than the above-mentioned diameter is obtained by mesh division A mesh data holding unit 44 that holds a group of nodes (for example, a coordinate value of each node) and a minimum sphere including a cubic region determined based on all the nodes, and generates a sphere of the highest hierarchy. On the condition that there are a plurality of nodes included in the highest-level sphere generation unit 45 to be assigned and the most newly generated and unprocessed sphere, A division unit 46 that divides into two by a plane that passes through the center and has the longitudinal direction of the cubic region as a normal line, and determines whether or not there are a plurality of nodes belonging to each section divided by the division unit 46 On the condition that there are a plurality of nodes 47 and the number of nodes, a minimum sphere including a cubic region determined based on all the nodes belonging to each section divided by the dividing unit 46 is generated, and the sphere of the next hierarchy is generated. An intermediate hierarchy sphere generation unit 48 to be allocated, and a lowest hierarchy sphere arrangement unit 49 that arranges the lowest hierarchy sphere in a state where the corresponding node and the center are matched, on condition that the number of nodes is 1. ing.
[0066]
Since the operation of each component is the same as the corresponding step in the flowcharts of FIGS. 10 and 11, detailed description thereof will be omitted. Of course, each of these components may be configured by hardware, but is preferably configured by a computer in which a program for performing the processes shown in FIGS. 10 and 11 is incorporated. Further, the control unit that repeats the division process by the division unit 46 and the process of the intermediate layer sphere generation unit 48 until the number of nodes becomes 1 is not shown. Also, a holding unit that holds each of the two divided node groups is not shown.
[0067]
【The invention's effect】
According to the first aspect of the present invention, it is not necessary to calculate the positional relationship using the polyhedron representation, and the clip of the rendering model can be achieved at a high speed by performing the interference calculation using the rendering sphere, thereby speeding up the rendering. There is a unique effect of being able to.
[0068]
In the invention of claim 2, the sphere included in the object is not originally generated, and the number of generated spheres can be reduced without complicating the processing. Based on the spherical model, the same effect as in the first aspect can be obtained.
According to the third aspect of the present invention, calculation of the positional relationship using the polyhedron expression is unnecessary, and the removal of the rendering sphere unnecessary for drawing can be simplified by the high-speed cone-to-cone interference check. There is a specific effect that detection can be achieved at high speed.
[0069]
The invention according to claim 4 eliminates the need for calculating the positional relationship using the polyhedron representation, and can quickly select a polygon to be drawn from among the polygons in the rendering sphere, thereby speeding up rendering. There is a unique effect of being able to.
The invention of claim 5 has a specific effect that drawing can be speeded up by adopting polygons with low drawing accuracy for some of the polygons, and thus rendering can be speeded up.
[0070]
According to the sixth aspect of the present invention, it is not necessary to calculate the positional relationship using the polyhedron representation, and the clip of the rendering model can be achieved at a high speed by performing the interference calculation using the rendering sphere, and thus rendering can be speeded up. There is a unique effect that you can.
According to the seventh aspect of the present invention, the sphere included in the object is not originally generated, and the number of generated spheres can be reduced without complicating the processing. The hierarchical sphere model generated in this way On the basis of the Claim 6 Has the same effect as.
[0071]
The invention of claim 8 eliminates the need for calculating the positional relationship using the polyhedron representation, and makes it possible to easily remove the rendering sphere unnecessary for drawing by the high-speed cone-to-cone interference check. There is a specific effect that detection can be achieved at high speed.
The invention of claim 9 eliminates the need for calculating the positional relationship using the polyhedron representation, and can quickly select a polygon to be drawn from among the polygons in the rendering sphere, thereby speeding up rendering. There is a unique effect of being able to.
[0072]
The invention of claim 10 has a specific effect that drawing can be speeded up by adopting polygons with low drawing accuracy for some of the polygons, and therefore rendering can be speeded up.
[Brief description of the drawings]
FIG. 1 is a schematic diagram showing a relationship between a hierarchical sphere model and a rendering model.
FIG. 2 is a schematic diagram illustrating a state in which a rendering model is separated into a one-to-one correspondence part and a many-to-one correspondence part when the rendering sphere and the rendering model do not correspond one-to-one;
FIG. 3 is a schematic diagram showing a rendering model in a state where a one-to-one correspondence portion and a many-to-one correspondence portion are separated.
FIG. 4 is a flowchart illustrating a rendering model clip process in a high-speed rendering method;
FIG. 5 is a schematic diagram showing the relationship between a field of view approximated by a cone and a rendering sphere.
FIG. 6 is a schematic diagram showing a state in which a range of normal vectors such as polygons not drawn is approximated by a cone.
FIG. 7 is a schematic diagram showing the relationship between two cones approximating the range of a normal vector such as a polygon.
FIG. 8 is a schematic diagram showing a plurality of LOD models such as polygons corresponding to each rendering model.
FIG. 9 is a diagram showing the relationship between the LOD hierarchy and a value obtained by subtracting the radius of the rendering sphere from the length of the rendering sphere vector.
FIG. 10 is a flowchart for explaining a part of an example of a hierarchical sphere model creation method;
FIG. 11 is a flowchart illustrating a remaining part of an example of a hierarchical sphere model creation method;
FIG. 12 is a schematic diagram for explaining a process for generating a sphere with a minimum radius including a cubic region and a process for dividing all nodes into two parts.
FIG. 13 is a schematic diagram for explaining mesh division of an object surface and arrangement of spheres in the lowest hierarchy.
FIG. 14 is a block diagram showing an embodiment of the high-speed rendering apparatus of the present invention.
FIG. 15 is a block diagram showing a configuration of an apparatus for determining whether a rendering sphere is inside or outside a field of view approximated by a cone.
FIG. 16 is a block diagram illustrating a configuration of an apparatus for determining whether or not a polygon in each group is a drawing target when polygons included in a rendering sphere are grouped based on a normal vector; is there.
FIG. 17 is a block diagram showing an apparatus for LOD display of polygons constituting a rendering model.
FIG. 18 is a block diagram illustrating an example of a hierarchical sphere model creation device.
[Explanation of symbols]
2 Rendering sphere setting unit 3 Rendering model association unit
5 Inside / outside determination unit 6 Clip processing unit
12 Gaze direction vector holding unit 13 Viewing angle holding unit
15 Rendering Sphere Vector Calculation Unit 16 Spreading Angle Calculation Unit
18 Large / small judgment part 19 Inside / outside judgment part
24 1st spread angle calculation part 25 2nd spread angle calculation part
26 Center vector holding part 27 Third spread angle holding part
29 Size determination unit 30 Drawing determination unit
31 LOD model holding unit 32 Distance calculation unit
33 Large / small judgment part 34 LOD model selection part
35 Display unit 43 Mesh division unit
45 Top layer sphere generator 46 Divider
48 Middle layer sphere generator 49 Lower layer sphere generator

Claims (10)

The hierarchy spherical model stored in the hierarchical spherical model holding unit (1), of predetermined radius below the sphere, as well as specify the sphere of the most upper hierarchy as the rendering sphere, rendering corresponding to each rendering sphere A high-speed rendering method characterized by allocating a model, determining whether a rendering sphere is inside or outside a clip area, and clipping a corresponding rendering model when the rendering sphere is outside the clip area. The subject to the surface of the object modeling, as well as mesh division, mesh-divided set to less than or equal to the diameter of all the sides of the preset lowest layer lengths sphere of each mesh, occurs by meshing Then, a sphere of the lowest hierarchy is generated around each node held by the mesh data holding unit (44) , and then a minimum sphere including a cubic region determined based on all nodes is generated to generate a sphere of the highest hierarchy. A sphere is formed, and then all nodes are divided into two on a plane passing through the center of the sphere of the highest hierarchy, and the smallest sphere including a cubic region determined based on all the nodes belonging to each divided section is generated. After the division, the sphere of the next layer of the next layer is divided, and then the process of dividing all the nodes into two parts and generating the smallest sphere including the cubic region determined based on all the nodes belonging to each section and making it the next sphere Section of Fast Rendering Method according to claim 1 to create a hierarchical sphere model by several iterates until 1. Viewpoint position holding portion is viewed point position stored in the (11) as a reference, is held in the line-of-sight direction vector holding portion beauty viewing angle holder Oyo visual line direction vector is held in the (12) (13) in a state in which the field of view by are viewing field angle is defined, perspectives, et al., a vector directed to the center of the rendering sphere held in rendering sphere center support portion (13a), the spread of rendering sphere around the vector The specified angle is calculated, and the rendering sphere is removed on condition that the angle formed by both vectors is larger than the sum of the viewing angle and the angle defining the spread of the rendering sphere. The described fast rendering method. For rendering spheres that are at least partially included in the field of view, polygons contained in the rendering sphere are divided into a plurality of groups based on the direction of the respective normal vectors, and a set of polygon normals belonging to each division is obtained. approximating a conical, perspectives, et al., calculates the first spread angle for defining the extent of rendering sphere around a vector directed to the center of the rendering sphere held in rendering sphere center support portion (21), a polygon The center axis vector that defines the center axis of the cone that approximates the set of normals and the second divergence angle of this cone are calculated, and the angle formed between the vector from the viewpoint toward the center of the rendering sphere and the center axis vector is both 2. A polygon belonging to a corresponding section is selected as a drawing target on condition that the sum is not more than a sum of spread angles. Fast Rendering Method according to any one of al claims 3. For polygons corresponding to each rendering model, a plurality of polygons having different rendering accuracy are generated in advance corresponding to the size of the vector from the viewpoint toward the center of the rendering sphere, and stored in the LOD model holding unit (31). 5. The high-speed rendering method according to claim 1, wherein a polygon having a drawing accuracy corresponding to the vector is drawn based on an actual size of the vector. A rendering sphere designating means (2) for designating a sphere of the highest hierarchy as a rendering sphere among spheres having a predetermined radius or less of the hierarchical sphere model, and a rendering model assigning means for assigning a rendering model corresponding to each rendering sphere In response to the determination results of (3), the inside / outside determination means (5) for determining whether the rendering sphere is inside or outside the clip area, and the inside / outside determination means (5) indicating that the rendering sphere is outside the clip area. And a clip means (6) for clipping the corresponding rendering model. Mesh dividing means (43) for dividing the surface of the object to be modeled into meshes and setting the lengths of all the sides of each mesh divided to a diameter of a sphere of the lowest hierarchy set in advance And a lowest hierarchy sphere generation means (49) for generating a sphere of the lowest hierarchy around each node generated by mesh division, and a lowest sphere including a cubic region determined based on all the nodes, A top-level sphere generating means (45) as a sphere of the hierarchy , a dividing means (46) for dividing all the nodes into two on a plane passing through the center of the sphere of the top-level hierarchy at the time of processing , and for each divided section An intermediate layer sphere generating unit (48) that generates a minimum sphere including a cubic region determined based on all the nodes to which it belongs and forms a sphere of a layer next to the layer before the division, and a process by the dividing unit (46) The processing by the hierarchical spheres generating means (48), number of nodes after the division fast rendering apparatus of claim 6, further comprising a repetition control unit for repeating until 1. Holding means (12) and (13) for holding a line-of-sight vector and a viewing angle set with respect to the viewpoint position to define the field of view, a vector from the viewpoint toward the center of the rendering sphere, and rendering with this vector as the center The calculation means (15) (16) for calculating the angle defining the spread of the sphere, and determining whether the angle formed by both vectors is larger than the sum of the viewing angle and the angle defining the spread of the rendering sphere. Responding to the determination result of the first size determination means (18) and the first size determination means (18) indicating that the angle formed by both vectors is larger than the sum of the viewing angle and the angle defining the spread of the rendering sphere. The high-speed rendering apparatus according to claim 6 or 7, further comprising a rendering sphere removing means (19) for removing the corresponding rendering sphere. For rendering spheres that are at least partially included in the field of view, the dividing means for dividing the polygons included in the rendering sphere into a plurality of groups based on the direction of the respective normal vectors, and the normals of the polygons belonging to each division Approximating means for approximating the aggregate with a cone, first calculating means (24) for calculating a first spread angle that defines the spread of the rendering sphere around the vector from the viewpoint toward the center of the rendering sphere, and the normal of the polygon And a second calculation means (25) (26) (27) for calculating a central axis vector defining the central axis of the cone approximating the aggregate of the second and a second spread angle of the cone, and from the viewpoint toward the center of the rendering sphere A second magnitude judging means (29) for judging whether or not an angle formed by the vector and the central axis vector is equal to or less than a sum of both spread angles; In response to the determination result of the second size determining means indicating that the angle formed by the vector directed to the center of the dundling sphere and the center axis vector is equal to or less than the sum of the two spread angles, polygons belonging to the corresponding category are drawn. 9. The high-speed rendering apparatus according to claim 6, further comprising selection means (30) for selecting. Polygon generating means (31) for generating a plurality of polygons having different rendering accuracy in advance corresponding to the size of the vector from the viewpoint toward the center of the rendering sphere for the polygon corresponding to each rendering model; The drawing means (32) (33) (34) (35) for drawing a polygon having a drawing precision corresponding to the actual size, further comprising: High speed rendering device.

Images