表面の導出

今下のような配列に立方体のデータが入っているとすると

a(n,8)：立方体を構成する頂点の番号[nは立方体の数]
x(m),y(m),z(m)：頂点の座標[mは頂点の数]

表面を構成する頂点の番号を検索するにはどのようにしたらよいでしょうか？

b(r,4)：表面を構成する頂点の番号[rは面の数]

No.6 ベストアンサー 回答者： tgb 回答日時： 2002/05/10 09:29

　ANo.#5で説明したのはANo.#4と同じく、見える面を抽出する方法です。

６面体のこちらから見える面を画面にどのように描画するかについては、ANo.#4で「立方体同士の干渉による見え隠れについては別途考慮されているものとします」としている通り、考慮していません。ANo.#4、ANo.#５の方法を利用して画面に描画するとしたら、一般に行われている方法だと思いますが１つ１つの立方体を視点から遠い順に描くことになると思います。従って各々の６面体の６面の内こちらを向いていないいくつかの面について描画処理を省略できるというもので、手前にある６面体によって隠される部分を考慮して新たに画面上に描かれる面を生成する（或いは完全に隠された部分は削除してしまう）と言う処理は考えていません。
　ANo.#5の補足にあるように、「画面上に見える部分のみを取り出す」と言うことになると、直方体や６面体の面と言うよりはそれらの干渉によってできる（上の「生成」）画面上の面になるので、これまでとは別の処理が必要になります。ANo.#5の補足からijiriさんの取り出したいと望んでいたのはこの面のことだったことが分かりましたが、立方体の表面と言う言葉からはこのことには全く思い至りませんでした。
・「立方体のデータaが集まってさらに大きい立方体を作っています．」
・「ａの中の頂点の番号が共有しているものがある」
と言うのはこの辺のことと関係あるのでしょうか？

　そこで画面上に描く面のみを取り出す方法ですが、だいぶ難しくなりそうです。うまく説明しているサイトがあるようなので、隠線処理・隠面処理、ｚバッファ法、スキャンライン法などをキーワードにして探して見られたらいかがでしょうか。
http://nis-lab.is.s.u-tokyo.ac.jp/~nis/CG/cgtxt/ …

（上のような処理を考えておられるなら関係ないかも知れませんが）
　ANo.#4、#5の方法で、描画するたびに処理を行うのかと言うことで計算量を心配されているようですが、６面体の方向・配置が変わって描画し直すときは当然必要となり、避けることはできないと思います。（全体の処理内容を理解した上で何らかの工夫により処理を軽減することの可能性はあり得るでしょうが）

参考URL：http://nis-lab.is.s.u-tokyo.ac.jp/~nis/CG/cgtxt/ …

No.5 回答者： tgb 回答日時： 2002/05/09 11:45

　「回転を何度も行う場合でもこの方法で描画するのが良いのでしょうか．」と言う質問ですが、

直方体が時間的に動いている場合、指定した時間によって直方体の方向が変わりますが、時々刻々変わる方向に対して表（おもて）の面を求めるのにANo.#4の方法が使えるかという意味と考えます。
・先ず、＃４の方法は取りあえずは描画には関係なく見える面を抽出する方法です。
・直方体の位置・方向が時々刻々変わる場合はその時点で求まる直方体の新しい頂点座標から＃４の方法を使って見える面を抽出し直し、この面を再描画することになると思います。
・良いかどうかと言うのがどういう観点で質問されているのかよく分かりませんが、心配されている点がある場合はもっと具体的に説明していただけたら、お役に立てるかも知れません。

　一般の６面体（平行６面体もこれに含める）の場合の方法ですが、そのまえに訂正させていただきたいと思います。ANo.#4で立方体の頂点番号の付番が一定の規則になっているかどうか聞いたのですが、面データがありますので直接そちらの方を使用することにしたいと思います。その面データでの頂点番号の付番順ですが、１２３４と振っていくときの方向について、右手で親指を伸ばして他の４本指を軽く握り、４本指の付け根から指先に向かって１２３４としたとき、この方向を６面体の１つの面の１２３４に合わせた場合に親指が常に外側（或いは常に内側）を向くようになっているか確認してください。そうなっていれば既存の面データがそのまま使えます。そうでない場合はコメントください（最後の方の＃２の部分参照）。以下では外側を向くようになっているものとして話を進めます。

１）１つの６面体について視点を向いた面を抽出することを考えます。複数の６面体の場合は以下の処理を繰り返します。
２）６面体の各面をi=1,6とします。各面の頂点をpj(j=1,4)とします。視点をｖとします。
３）i=1～6まで各面iについて処理４）５）を繰り返し、６面体の各面の表・裏を決めます。
４）p1からp2へ向かうベクトルをａ、p1からp4へ向かうベクトルをｂとし、c=a×b（外積・ベクトル積）とします。p1からｖへ向かうベクトルをdとします。ｒ=c・d(内積)とします。
　　視点が無限遠にある場合はp1の位置に拘わらずdは視点の方向ベクトル（固定の値）を視点に向かうように取ってください。大きさは任意ですが、計算の精度の観点からは平均的なcの大きさ即ち６面体の平均的な寸法のオーダーがよいと思います。
５）ｒが＋ならその面は表を向いています（こちらから見えます）。－なら裏を向いています。r=0ならちょうど面が１つの線に見えるような位置になっています。

＃１　この方法は立方体・直方体の場合にも適用可能ですが、計算量はANo.#4の方法より多くなるかも知れません。

＃２　上に述べたチェックで親指が
・内側を向いていた場合：
　　処理４）でp2とp4を入れ替えて計算します。
・バラバラの場合：
　　面倒ですが新たに面データをつくることになります。applicationとして作成中でデータはこれから作成するという場合は一定の規則にして面データb(r,4)を作成すべきだと思います。システムの他の部分との関係でb(r,4)のデータはそのままにして処理したい場合はコメントしてください。

この回答への補足

#5の方法は視点から遠い面の順に描画していくということで良いのでしょうか．
できれば，値を用いて色を塗る際の計算量を減らすため，画面上に見える部分のみを取り出したいと考えています．
立方体数(30000個以上の場合もある)×6の処理を描画するたびに行うと計算量が多くなるのではないかということを心配しています．

補足日時：2002/05/09 15:59

No.4 回答者： tgb 回答日時： 2002/05/08 22:22

　何をしようとしているかについての具体的な話をお伺いしたのでだいぶ分かってきたようです。

ANo.#3に対する補足から私が理解したことを確認したいと思います。
　「表面」と言うのは小立方体（または直方体）を囲む大立方体の６つの表面と言うことではなく、１つの立方体がある角度で置かれている場合に画面を通してこちら側から見える面ということになると理解しました。従って、大立方体、小立方体と言う考えは不要で、１つ１つの立方体に対して６つの面の中からこちら側から見える３面（角度によっては２面、或いは１面）を選び出すと言うことになります。（この場合、立方体同士の干渉にによる見え隠れについては別途考慮されているものとします。）

　以上のような前提で以下のように考えることができると思います。方法の適用の条件ですが、視点は無限遠、形状は直方体としています。平行６面体や一般の６面体についても考えたい場合、或いは有限位置での視点で表示する場合について必要なら、コメントしてください。計算量が多くなるかも知れませんが、別の方法を考えます。その際、頂点の番号を振る順が全ての６面体で一定していないと困りますので確認をお願いします。（例えば６面体の下側の４角形に対し、辺の周りに１、２、３、４と振ったあと１の点に戻り、そこから上側に移って下の場合と同じ方向に５、６、７、８と振っていて、ねじに見立てて１２３４の方向に回すとねじが１から５の方向に進むようになっていると言ったような関係です。全ての６面体について順序が一定していれば、読み替えが可能ですのでこの通りでなくとも構いません。）

　３面の選び出しですが、このためには視点の方向が分かっている必要があります。（３次元データを画面に表示しているので当然そのデータは既知だと思います）　これを使って以下のようにします。
１）適当に１点Ｐ（例えば原点）を選びます。
２）点Ｐから視点に向かうベクトルをＶとします。ベクトルＶの大きさ（絶対値）は任意です。平均的な直方体の寸法と同じオーダーにしておけばよいと思います。ベクトルは必ず視点へ向かう方向にとってください。
３）直方体の８つの点について順に（ｉ＝１～８）点Ｐを通るＶ方向ベクトルへの正射影（ｊ＝１～８）をつくります。即ち、点Ｐを通り、ベクトルＶの方向を持つ直線（ｍ）と点ｉから直線ｍへ垂線を引いてできる交点ｊ（＝点ｉのｍへの正射影）を求めます。点Ｐからこの点ｊまでの距離ｓｊを求めます（ベクトルＶの向きに正として）。ｓｊは視線上で測った各頂点の位置（大きい方が手前、即ち視点に近い）を示しています。
４）ｊ＝１～８でｓｊが最大となる点（視点に近い点）を選びます。
　・４つの点についてｓｊが等しくなり、これが最大になる場合
　　これはその４点からなる面が視線・ベクトルＶに直交（或いは画面に平行）の場合です。
　・２つの点についてｓｊが等しくなり、これが最大になる場合
　　これは２点を結ぶ辺が画面に平行の場合です。
　・１つの点で最大になる場合
　　直方体が完全に斜めになっている場合です。
　以上の３通りのいずれかになる筈です。
５）処理４）のｓｊ最大点の数に応じて、着目した立方体の頂点・面に対して以下のようにします。
　・４つの場合
　　その４点を頂点とする面が表の面（こちら側を向いた面）として１つ選び出せます。
　・２つの場合
　　その２点を頂点とする面が２つ選び出せます。
　・１つの場合
　　その１点を頂点とする面が３つ選び出せます。
　以上のように面の選び出しができると思います。


　１つだけ気になる点があります。ANo.#1で「立方体のデータaが集まってさらに大きい立方体を作っています．」と言われていますが、この「大きな立方体」はANo.#3の補足説明からは理解しがたいのですがもしこの点に関して問題があれば補足していただけないでしょうか。（今回の説明ではこの点は無視しています。）

この回答への補足

ありがとうございます．
質問の内容はこれで合っています．
もしよろしければ一般の六面体についてもご教授いただけないでしょうか？
(番号を振る順は全ての６面体で一定になっています)
さらに質問なのですが，回転を何度も行う場合でもこの方法で描画するのが良いのでしょうか．

「立方体のデータaが集まってさらに大きい立方体を作っています．」というのは，ａの中の頂点の番号が共有しているものがあるという意味で書きました．

補足日時：2002/05/09 09:07

No.3 回答者： tgb 回答日時： 2002/05/07 13:53

　申し訳ないのですが、まだ問題の輪郭が掴めないようです。

　私の理解する範囲で、ANo.#2の補足に基づいて、本問題の簡単な実例：
　　　　方向、大きさの異なる小立方体がお互いに離れた位置に
　　　　３個あるとするとして、これから、本問題で要求する
　　　　大立方体を求める
を考えてみます。この例からすぐに分かるように、
・大立方体をいくつにしたらよいか決まらない
・そのサイズをいくらにしたらよいか決まらない
と言うことになります。
　このような問題を考えているとは思えないので、更に補足が必要なように思います。

この回答への補足

　説明が下手なために何度も申し訳ありません．
　現在上記に示すような配列を使って画面上に形状を書くという作業を行っています．
六面体の各頂点には値が与えられておりそれを元に色を塗る作業を行おうとしています．
しかしながら，すべての面(ｎ×６)について描画を行うと処理に時間がかかってしまいます．
そこで，表面を選び出して描画の処理を少なくしようと思っています．
また，現在の描画方法は配列ａからｒを取り出して，ｒに入っている頂点の座標番号からＸ，Ｙ，Ｚそれぞれの座標を取り出しているといった単純なものです．

補足日時：2002/05/08 09:00

No.2 回答者： tgb 回答日時： 2002/05/04 21:39

　補足説明を考慮して処理方法を考えようとするとだいぶ煩雑になると思います。

また、無駄な処理をすることのないよう、もう少し補足をしていただく必要があると思います。
・最終的に大きな立方体は１つなのか？
　それともいくつかのグループがあるのか？（当然こちらの方がより煩雑になります）
・大きな立方体の表面は必ず小さな立方体で構成されているのか？
　それとも表面が間欠的になっていて不完全な立方体なのか？
・上と関連して、大きな立方体の内部の間欠性はどうなのか？
・全ての立方体は同一の方向を向いているのか？（大立方体が１つなら一致しているものと考えますが）
　また、１つの頂点に集まる３つの辺は座標軸の方向に一致しているのかいないのか？
　更に、小立方体の大きさは一定しているのかバラバラなのか？　一定している場合、位置は格子状（格子間隔が小立方体のサイズ？）なのか任意の位置か？
・ｒ＝６＊ｎとしていますが、２つの小さな立方体が１つの面を共有して接しているとき、ｂ（ｒ，４）のデータとしてはこのような同一の面に対して立方体毎に別の番号が割り当てられているということなのか？それとも他に意味があるのか？
・最終的に欲しいデータの形はどのようなものなのか配列などで具体的に示せないでしょうか？

この回答への補足

ありがとうございます．
・最終的に大きな立方体は１つなのか？
　それともいくつかのグループがあるのか？（当然こちらの方がより煩雑になります）
＞１つの場合といくつかのグループで構成されている場合があります．
・大きな立方体の表面は必ず小さな立方体で構成されているのか？
　それとも表面が間欠的になっていて不完全な立方体なのか？
＞これも間欠的になっている場合もあります．
・上と関連して、大きな立方体の内部の間欠性はどうなのか？
＞内部に間欠性はあります．
・全ての立方体は同一の方向を向いているのか？（大立方体が１つなら一致していないものと考えますが）
＞同一方向を向いていません．
　また、１つの頂点に集まる３つの辺は座標軸の方向に一致しているのかいないのか？
＞一致していません．
　更に、小立方体の大きさは一定しているのかバラバラなのか？　一定している場合、位置は格子状（格子間隔が小立方体のサイズ？）なのか任意の位置か？
＞立方体の大きさは一定ではありません．
・ｒ＝６＊ｎとしていますが、２つの小さな立方体が１つの面を共有して接しているとき、ｂ（ｒ，４）のデータとしてはこのような同一の面に対して立方体毎に別の番号が割り当てられているということなのか？それとも他に意味があるのか？
＞ｂ（ｒ，４）はａ（ｎ，８）から取り出したものでありますので，同一の面に対して立方体毎に別の番号がふられています．
・最終的に欲しいデータの形はどのようなものなのか配列などで具体的に示せないでしょうか？
＞最終的には表面となる面の数ｍと表面を構成する頂点の番号ｓ（ｍ，４）を取り出したいと考えています．

補足日時：2002/05/07 09:40

No.1 回答者： tgb 回答日時： 2002/05/02 15:43

　立方体のデータａ（ｎ，８）と面のデータｂ（ｒ，４）が与えられていて、立方体の番号ｉ（＝１～ｎ）が与えられたとき、立方体の面として全体の面データからどの面番号ｊ（＝１～ｒ）を６個取り出すかと言う問題と解釈します。

　もっと効率的な方法があるかも知れませんが、虱潰しに指定の立方体の点番号と合致するような面をｂの中から探していけばよいと思います。この場合、ｘ、ｙ、ｚ座標は不要です。
　以下のようになります。
１．立方体番号ｉと面番号ｊとを与えて、与えられた面番号についてこの面の４つの点の点番号全てが、与えられた立方体の８つの点の点番号いずれかと一致するかどうかチェックできるようにします。...f１(i,j)
２．立方体ｉが与えられたとき、f2を使って面１から順にｒまでチェックを繰り返します。面が見つかる度にデータｃ（ｎ，６）に格納します。一致する点が全て見つかるような面の数が６になったら途中で終了します...f2(ｉ)
３．立方体ｉ＝１～ｎについて、f2を使った処理を繰り返します。
以上でｃ（ｎ，６）が出来上がります。ｃ（ｎ，６）をつくらずに必要な度に処理２を行って６つの面を取り出すと言うことも可能です。

この回答への補足

ご回答ありがとうございます．

すいません．説明不足でした．
立方体のデータaが集まってさらに大きい立方体を作っています．
このような場合立方体の表面を取り出す方法を知りたいです．
ちなみにr=n*6となっています．

補足日時：2002/05/02 17:30