データ構造を模索 - 三次元日誌

UniformGridににいろんな種類の形状を突っ込む方法を模索中。
インターフェースとしてはこんなのがあって、

Shape
{
  result intersect(const Ray &ray);
};

具体的には、TriangleとSphereを格納したい。
ゆくゆくは無限平面とか曲面とかintersect関数が定義できるものを
なんでもかんでも格納したい。

案１すべての形状をひとつのclassから継承してポインタを格納する

templateのダックタイピングな感じに慣れるとやってられない
仮想関数のオーバーヘッド

むしろ普通すぎるので却下ｗ

案2 boost::anyかboost::variantに対象のポインタを格納する

空間のオーバーヘッド
取り出した後型ごとにディスパッチするオーバーヘッド

boost::variantのvisitorで交差判定するものを途中まで作ったが中止。

案3 MPLで型のリストを作ってそれぞれの処理を自動生成させる

今、この方向で試作中。
果たして実用的なものになるかはまだわからない。

以下はBoost本を参考に習作。
boost::mpl::foldで再帰的に継承して型毎にメンバを定義する。
usingがポイント。
http://d.hatena.ne.jp/minekoa/20080222/1203696120
Effective C++にも書いてあるらしい。
まったく覚えていない。

#include <iostream>
#include <sstream>
#include <vector>
#include <typeinfo>
#include <boost/shared_ptr.hpp>
#include <boost/mpl/list.hpp>
#include <boost/mpl/fold.hpp>
#include <boost/mpl/for_each.hpp>

//------------------------------------------------------------//
// 適当な定義
//------------------------------------------------------------//
struct Vector2 { float x; float y; };
struct Vector3 { float x; float y; float z; };
struct Sphere { Vector3 center; float radius; };
struct Plane { Vector3 normal; float d; };

struct VertexAttribute { Vector2 uv; Vector3 normal; };
struct FaceAttribute { Vector3 normal; int materialIndex; };
template<typename VERTEX_ATTRIBUTE, typename FACE_ATTRIBUTE>
struct TriangleMesh
{
  struct Triangle{
    VERTEX_ATTRIBUTE v0;
    VERTEX_ATTRIBUTE v1;
    VERTEX_ATTRIBUTE v2;
    FACE_ATTRIBUTE face;
  };

  std::vector<Vector3> vertices;
  std::vector<Triangle> faces;
};
typedef TriangleMesh<VertexAttribute, FaceAttribute> MESH;

//------------------------------------------------------------//
// MPL
// タイプリストの型をそれぞれ別のvectorで保持するStoreの定義
//------------------------------------------------------------//
// foldの初回用
struct Store_Dummy
{
  void add();
  void summary_();
};

template<class BASE, typename SHAPE>
struct Store_Build
{
  typedef boost::shared_ptr<SHAPE> shapePtr;
  typedef struct _ : BASE {
    // 継承したクラスのメンバ関数を見えるようにする
    using BASE::add;
    using BASE::summary_;

    std::vector<shapePtr> shapes_;
    
    void
    add(shapePtr pShape)
    {
      shapes_.push_back(pShape);
    }

    void
    summary_(std::ostream &os, const SHAPE& shape)
    {
      os 
        << typeid(shape).name() << ": " << shapes_.size() << std::endl
        ;
    }
  } type;
};

// boost::mpl::for_each用のファンクタ
template<class STORE>
struct Summary
{
  STORE *pStore_;
  std::ostream &os_;

  Summary(STORE *pStore, std::ostream &os)
  : pStore_(pStore), os_(os)
  {}

  template<typename T>
  void operator()(const T& tag)const
  {
    pStore_->summary_(os_, tag);
  }
};

// いれものとなるtemplate
template<class TYPE_LIST>
class Store
: public boost::mpl::fold<
  TYPE_LIST, Store_Dummy, Store_Build<boost::mpl::_, boost::mpl::_>
>::type
{
public:
  std::string summary()
  {
    std::stringstream ss;

    ss << "[summary]" << std::endl;

    boost::mpl::for_each< TYPE_LIST >( Summary<Store>(this, ss) );

    return ss.str();
  }
};

//------------------------------------------------------------//
// 使う
//------------------------------------------------------------//
typedef boost::mpl::list<
  Sphere, MESH, Plane
> StorableTypeList;

int main(int argc, char **argv)
{
  Store<StorableTypeList> store;

  store.add(boost::shared_ptr<Sphere>(new Sphere));
  store.add(boost::shared_ptr<Sphere>(new Sphere));
  store.add(boost::shared_ptr<Sphere>(new Sphere));
  store.add(boost::shared_ptr<MESH>(new MESH));
  store.add(boost::shared_ptr<MESH>(new MESH));
  store.add(boost::shared_ptr<Plane>(new Plane));

  std::cout << store.summary() << std::endl;
}

なんかバッドノウハウのような気がする。
だが、そこがいい。
ますますバッドだな・・・

実行結果

[summary]
6Sphere: 3
12TriangleMeshI15VertexAttribute13FaceAttributeE: 2
5Plane: 1

シーンにあわせて必要なテンプレートを実行時にコンパイルような仕組みを妄想してみる。
オフラインレンダラで重いシーンをレンダリングする場合はコンパイル時間くらいは元がとれるんではないかと。