JPH03238559A - バウンディング・ボリュームの設定処理方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔発明の属する技術分野〕 本発明は１画像生成手法に関する技術であって。

光線追跡法等で使用される物体定義法の−っであるコン
ストラクチイブ・ソリッド・ジオメトリ（Ｃｏｎｓｔｒ
ｕｃｔｌｖｅ　５ｏｌｉｄ　Ｇｅｏｔａｅｔｒｙ　　（
以下Ｃ３Ｇと略す））に用いるバウンディング・ボリュ
ーム（Ｂｏｕｎｄｉｎｇ　Ｖｏｌｕｍｅ　　（以下ＢＶ
と略す））の設定処理方法に関する。

〔従来の技術］ 第８図はＣ３Ｇモデルで物体データを定義する例を示す
。Ｃ３Ｇモデルでは、第８図図示のように木構造で物体
が定義される。光線追跡法は、光線が物体と交差するか
否かを計算し、物体と交差すれば、その点における物体
の輝度を求めて画像を生成する手法である。物体と光線
の交差判定を効率良く行うために、ＣＳＣモデルでは、
ＣＳＣ木の各ノードにＢｏｕｎｄｉｎｇ　Ｖｏｌｕｍｅ
　（Ｂ　Ｖ　）と呼ぶ直方体や球などの単純な形状の立
体を設定する。

ノードに設定するＢＶは配下のプリミティブをすべて包
含する最小の体積をもつ立体が設定される。

このようにＢＶを設定すると、′＃ｙＪ体と光線との交
差判定は、ＣＳＣ木のルートノードに設定されたＢＶと
交差判定を行い、交差すれば、子供のノードのＢＶと交
差判定を行うというように計算を進め、最終的に葉ノー
ドのプリミティブとの交差判定を行うことにより実行で
きる。途中ＢＶと交差しなければそのノード配下のＢＶ
との交差判定は省くことができる。このようにすること
により交差判定の回数を大幅に削減できる。

〔発明が解決しようとする課題］ 従来の手法では、ＣＳＣ木の各ノードにＢＶを設定し交
差判定回数の削減を図ってきた。しかしながら、交差判
定回数削減の観点からは、各ノードにＢＶを設定するこ
とが必ずしも最良とは言えない。場合によっては、ある
種のノードにはＢＶを設定しない方が交差判定回数が少
なくなることがある。

本発明は、上記の問題を解決するため、ＢＶ段設定可否
判定手段を提供し、交差判定回数の一層の削減を図るこ
とを目的としている。

〔課題を解決するための手段〕

本発明は、第１図図示実施例処理フローの如く第１の処
理、第２の処理、第３の処理、第４の処理を実行して１
着目ノードのＢＶのスクリーン上への投影面積を基礎と
して、該ノードの子供の数と該ノードおよび喜亥ノード
の親ノードのＢＶの投影面積とから該ノードにＢＶを設
定すべきか否かを判定するようにして、ＢＶ段設定可否
を決定するとした形で。

従来の技術では、ＢＶのスクリーンへの投影面積を小さ
くするほど計算時間短縮効果は大きい事実のみを利用し
て、投影面積ができるだけ小さくなるＢＶを設定する手
法が用いられていたものである（　（１）　ＨＪｅｇｈ
ｏｒｓｔ、　Ｇ、ＨｏｏｐｅｒＤ、Ｐ、Ｇｒｅｅｎｂｅ
ｒｇ：’Ｉｏ＋ｐｒｏｖｅｄ　Ｃｏｍｐｕｔａｔｉｏｎ
ａｌＭｅｔｈｏｄｓ　ｆｏｒ　Ｒａｙ　Ｔｒａｃｉｎｇ
　、　ＡＣＭ　Ｔｒａｎｓ、　ｏｎＧｒａｐｈｉｃｓ、
　Ｖｏｌ、３．　ＮＯ，１，ｌ）ｐ、５２−６９．　Ｊ
ａｎ、　１９８４（２）　Ｔ、Ｌ、Ｋａｙ、　Ｊ、Ｔ、
Ｋａｊｉｙａ：”Ｒａｙ　ＴｒａｃｉｎｇＣｏｍｐｌｅ
ｘ　５ｃｅｎｅｓ”、　Ｃｏｍｐｕｔ、　Ｇｒａｐｈｉ
ｃｓ、　Ｖｏｌ、２０＋Ｎｏ、４．　ｐｐ、２６９−２
７８．１９８６参照）。

〔実施例〕

以下１本発明の詳細な説明する。説明を簡単にするため
、以下の仮定を置く。

■　与えられたＣ３Ｇ木の構造は変更しない。

■　Ｃ３Ｇ木の各ノードは通常ＡＮＤ結合あるいはＯＲ
結合されているが、ここでは、ＣＳＣ木はＯＲ結合だけ
で構成されているとする。

■　Ｃ３Ｇ木は反射・屈折属性を持つプリミティブ（Ｃ
３Ｃ；木の葉ノードの置く形状）を含まない ■　各ノードには同種の形状のＢＶを設定する。

■　ＢＶの投影領域はスクリーン面に含まれる。

Ｃ３Ｇ木のノードに設定するＢＶは、その子孫である葉
ノードをすべて含むものであればよく子ノードのＢＶを
完全に含むものである必要はない。第２図にその例を示
す。第２図では、２次元の例を示しており、ＢＶは円、
また９葉ノードも円としている。なお、第２図（ａ）は
木構造を表し第２図（ｂ）は包含状況を表している。

今、ＣＳＣ木のルートノードに着目する。そのノードの
親子関係が第３図（ａ）のようになっていたとする。各
ノード（ｎＬ　ｎ２．　ｎ３）にＢＶを設定し。

それらのスクリーン面への投影を考えると、第３図い）
のようになる０問題はノードｎ１にＢＶを設定するか否
かの判定を与えることである。

１本の光線と１個のＢＶ−との交差判定のための演算ス
テップ数をＣｒ、ＢＶの投影面積をＳｔスクリーンの面
積をＳＯとすると ■）ｎｌにＢＶを置く場合の演算ステップ数Ｃ１はＣ１
−３Ｏ−Ｃｒ＋Ｓ１・２Ｃｒ ２）ｎｌにＢＶを置かない場合の演算ステップ数Ｃ２は Ｃ２＝２　・５ｏ−Ｃｒ となる。

従って、Ｃ１＜Ｃ２のときｎｌにＢＶを置くのが有利と
なる。すなわち。

ｓ　１＜　ｓ　Ｏ／　２　　　　　−−−−−−一（１
）のとき有利となる。一般に子供の数がｎのときは Ｓ　１　＜　（ｎ−１）　　Ｓ　Ｏ／　ｎ　−−−−−
（２１のとき有利となる。

中間ノードに対しても同様のことがいえるが。

この場合には着目ノードのＢＶの投影面積は、その先祖
ノードのＢＶの投影領域の共通部分を考えることになる
。すなわち１着目ノードの投影面積をＳｉ２着目ノード
の子供の数をｎ、先祖ノードの投影領域の共通部分の面
積を５（ｉ）とすると５（ｉ）　ｎｓ　ｉ＜　（ｎ　−
１）　５（ｉ）　／ｎ　−（３）となる。ここで、各ノ
ードのＢＶがその親ノードのＢＶに完全に含まれるとい
う関係が成立するときには、　　５（ｉ）は親ノードの
ＢＶの投影面積となり、（３）式の左辺はＳｉとなる。

これらの式から。

■　投影面積でＢＶを設定するか否かを判定できる ■　子供の数が多いと着目しているノードの投影面積が
その先祖ノードの投影領域の共通部分の面積に比べかな
り大きくても（すなわち、　　（ｎｌ）／ｎ程度であっ
ても）ＢＶを設定したほうが有利である ■　ＢＶ段設定判定条件に子供のＢＶの投影面積は関係
しない ということがわかる。

第４図はＢＶ段設定よる計算時間削減の例を示す。第４
図（ａ）はＢＶセツティングをしない場合。

第４図０））はルートノードにＢＶセツティングをした
場合、第４図（Ｃ）は各ノードにＢＶセツティングをし
た場合を表している。第４図０）のようなりＶを設定す
ることは一見無駄が多いように思えるが実際にはＢＶ段
設定よって４割近くも計算時間が削減できる。第４図（
Ｃ）のようにＢＶを設定する（枠で囲う）と、さらに効
果があがる。なお第４図（ｄｌはノードの関係を表す。

次に、ＢＶ旋形状変更や包含ＢＶの計算の簡略化によっ
てＢＶの投影面積が増加した場合、その増加に伴う交差
判定回数の増加について検討する。

今、ノードｉ　　（＞Ｏ）の子供の数をｎｉ、ＢＶの投
影面積をＳｉ、スクリーン面積をＳＯとすると。

交差判定の回数Ｔは Ｔ＝ＳＯ＋Σｎｉ＊（Ｓ　（ｉ）　ｎ　Ｓ　ｉ）　　　
−一−−−−（４）となる　ここで　Ｓ　（ｉ）はノー
ドｉに対する上述の共通部分である。

今、５（ｉ）ｎＳ　ｉがΔＳｔ増加したとすると。

そのときの交差判定の回数Ｔ′は。

Ｔ’＝ｓｏ＋Σｎｉ＊（Ｓ（ｉ）ｎｓ＋＋Δ５ｔ）−３
Ｏ＋Σｎｉ率（Ｓ　（ｉ）　　ｎ　Ｓ　ｉ）＊（１＋Δ
Ｓｔ　　／　　（Ｓ（ｉ）　　ｎ５ｉ））となる。ここ
で ＭＡＸ　（ΔＳ　ｉ／　（Ｓ（ｉ）　ｒ″１ｓｉ））　
＝ｐと置くと、上式は７ Ｔ’＝ＳＯ＋（１＋Ｉ））Σｎｉ＊（Ｓ　（ｉ）　　ｎ
　Ｓ　ｉ）＜（１＋ｐ）Ｔ　　　　　　−・−・・−・
−（５）となる。５（ｉ）ｎｓ　ｉ＝Ｓ　ｉならｐはＢ
Ｖの投影面積の増加率を表す。

与えられたＢＶ旋形状対する交点計算の演算ステップ数
をＣｒとすると、交点計算の総ステツプ数はＣｒ−Ｔと
なる。ここで、ＢＶの形状によりまた。計算機のアーキ
テクチャにより、Ｃｒの値は異なる。一般に複雑な形状
をしたＢＹの交点計算の演算ステップ数は大きくなる。

交点計算の総演算ステップ数はＣｒとＴとの積で決まる
から。

その積を最小にすることが重要である。投影面積が多少
大きくても交点計算の演算ステップ数が小さい単純な形
状のＢＶを用いた場合が有利なことがある。

また１式（５）はＳ　（ｉ）百Ｓｔが一様にｑ％増加す
ると交差判定の回数は高々ｑ％の増加で押さえられるこ
とを示している。従って、包含ＢＶを求める場合、必ず
しも最小解は必要ではなく、近似的に最小の解を求めれ
ば実用上は十分である。

式（１）〜（３）を用いて、ＢＶ設定アルゴリズムを構
築できる。

Ｂｖｉ　　アルボ１ズム 第６図はＢＶ設定アルゴリズムを表し、第７図は呼び出
されるｒＢＶ設定可否の判定」ルーチンを表す。なお図
中ｃｕｒｒｅｎｔ　ｎｏｄｅとしているのは現ノードに
対応している。

（１）：Ｃ３Ｇ木の各ノードに対し、自分の子孫の葉ノ
ードのＢＶをすべて含む最小のＢＶを設定する（便宜上
２葉ノードに対してもＢＶを設定する）。

（２）：　　ルートノードからＤｅｐｔｈ　Ｆｉｒｓｔ
　５ｅａｒｃｈで以下を調べる。

（２，１）　　：現ノードに対しく１）、　（２）ある
いは（３）式を計算。

（２，２）　　ｎ弐を満たせば設定。次のノードに対し
て上記処理（２）を実行。

（２，３）　　：満たさないときは子ノードの中で面積
最大のＢＶを持つノードを第５図図示のように子ノード
の形に展開する。展開した木を新たな木と考えて、現ノ
ードに対し上記処理（２）を実行。

実施例の冒頭で仮定した前提について二、三補足する。

■　ＡＮＤ結合ノードに設定するＢＶはその子供のノー
ドのＢＶよりも一般に小さい。よって該ノードをあたか
も葉ノードと考えてＢＶ設定問題を考えることができる
。それ故、冒頭の仮定は妥当である。ＡＮＤノードに設
定すべきＢＶは該ノードをルートと考えて適用すれば求
められる。

■　反射屈折光を含む場合１例えば２反射光により見え
る物体のＢＶと光線との交差判定の演算ステ・ンプ数も
投影面上の面積で評価できる。この場合は、−膜化透視
変換（（３）　Ｍ、５ｈｉｎｙａＴ、Ｔａｋａｈａｓｈ
ｉ、　Ｓ、Ｎａ１ｔｏ：”Ｐｒ１ｎｃｉｐｌｅｓ　ａｎ
ｄＡｐｐｌｉｃａｔｉｏｎｓ　ｏｆ　Ｐｅｎｃｉｌ　Ｔ
ｒａｃｉｎｇ　ＩＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ＋
　　Ｖｏｌ、２１＋　　Ｎｏ、４＋　　ｐｐ、４５−５
４ＪＬＩＬ、１９８７参照）を用いてＢＶの投影面上の
面積を計算することとなる。

〔発明の効果］ 以上説明したように２本発明によれば、従来の手法に比
べて、−層の交差判定回数の削減が可能となり１画像生
成時間の短縮が可能となる。

【図面の簡単な説明】

第１図は本発明の実施例処理フロー、第２図はＢＶの設
定例、第３図はＢＶのスクリーン面への投影図、第４図
はＢＶ段設定効果を示す図、第５図はノードの展開を示
す図。第６図はＢＶ設定アルゴリズム、第７図はＢＶ設
定可否の判定ルーチン、第８図はＣ３Ｇモデルの例を示
す。

Claims (1)

1. 【特許請求の範囲】 コンストラクティブ・ソリッド・ジオメトリモデルで物
   体を定義し、該コンストラクティブ・ソリッド・ジオメ
   トリモデルに計算量を削減する目的でバウンディング・
   ボリュームを設定し、該バウンディング・ボリュームを
   設定した該コンストラクティブ・ソリッド・ジオメトリ
   モデルを利用して画像を生成する方法において、 （１）該バウンディング・ボリュームのスクリーン上の
   投影面積を計算する、 （２）コンストラクティブ・ソリッド・ジオメトリ木の
   各ノードに対して、該ノードのバウンディング・ボリュ
   ームの投影面積（Ｓ）、該ノードの親ノードのバウンデ
   ィング・ボリュームの投影面積（Ｓｐ）、該ノードの子
   供の数（ｎ）のとき、 Ｓ＜（ｎ−１）Ｓｐ／ｎなら該ノードにバウンディング
   ・ボリュームを設定し、そうでなければ設定しない、 とした形でバウンディング・ボリューム設定の可否を判
   定する ことを特徴とするバウンディング・ボリュームの設定処
   理方法。