DOPの描画(1)

3d

相変わらずReal-Time Collision Detection (The Morgan Kaufmann Series In Inteacive 3-D Technolagy)を読み進めています。k-DOPの実装をしていたのですが、そこで問題にぶち当たりました。k-DOPの生成や衝突テストはものすごくシンプルです。AABBのように、その軸と各頂点の内積をとりminとmaxを決定してやるだけ。本にもそのまんまのコードが載っているのでこれは問題ありませんでした。……が、問題はその表示。作ったk-DOPをどうやって描画すればいいのだろう？というところで全てがストップしてしまいました。
6-DOPならばAABBと全く同じでいいのですが、8-DOPとなると八面体（って言っていいのかな？）でややこしくなります。6-DOPのように頂点の数や面の数が決まっているわけではなく、形によって、頂点は6個〜12個。面は三角形、四角形、五角形、六角形のいずれかになります（下図参照）。立方体を覆う8-DOPの場合は、正8面体（クリスタル形）になるようです。

三角形のみ 四角形を含む 五角形を含む 六角形を含む

はじめは

全ての平面同士の交線を求め、そこから交線同士の交点を求め、それをもとに形を作ろうと考えていたのですが、いちいち条件を決めるのが面倒で挫折しました。

次に

全ての面が三角形だと仮定し、その三角形の頂点を、隣接する3つの面の交点として求めて描画してみました。正8面体のときはうまくいくのですが、そうでないときは三角形同士が交差していたりしてかっこ悪いです（下図参照）。しかも、このあと14-DOPや18-DOPを作るときに応用もできない……。



そんなわけで

今は別の方法を考えています。全ての組み合わせの3つの面の交点を列挙し、各平面の外側にある点は削除する。そうすれば、余分な点は削除され、頂点となる点だけが残るはずです。全ての組み合わせといっても、面8つのなかから3つの組み合わせなので、{}_{8}C_{3} = 56程度（平行な面を含む場合は交点が存在しないので実際はもっと減るはず）です。よくはないけど、これならk-DOPのkの数が増えてもコードを流用できます。ただ、問題は求まった頂点からどうやって8面体を作るかってことです。3次元の凸包とか使えばポリゴナイズできるのかなぁ。。。

Vector3d plane[8]={...}; // 8-DOPを構成する8つの平面を定義しておく
std::vector<Vertex3d> verts; // 求めた8-DOPの頂点を格納する
for ( int i=0; i<8; ++i )
{
  for ( int j=i+1; j<8; ++j )
  {
    for ( int k=j+1; k<8; ++k )
    {
      Vector3d point;
      bool res = IntersectPlanes( plane[i], plane[j], plane[k], point );
      for ( int l=0; l<8 && res; ++l )
      {
          if ( DistPointPlane( point, plane[l]) > EPSILON )
            res = false;
      }
      if ( res )
        verts.push_back(point);
    }
  }
}


とりあえず、明日あたり実装してみよう。