1

私は、ツリー ノードが次元の長さ (2 のべき乗) でテンプレート化されている octree の実装に取り​​組んでいます。

template<long N>
struct node_t {
    enum { DIM = 1 << N };
    node_t<N+1> * parent;
    node_t<N-1> * children[8];
    long count;
}

また、データを指すように N = 0 (葉) に特化しています。

struct node_t<0> {
    enum { DIM = 1 };
    node_t<1> * parent;
    data_t data;
    long count;
}

(余談ですが、親ポインターを除外する N_MAX の特殊化もおそらく必要だと思います。そうしないと、C++ は無限に増加する N の型を生成しますか?しかし、それは私の質問にはあまり関係ありません。)

オクツリーが占有する 3D 空間で光線に沿って進む関数を作成したいので、表向きはルート ノード (既知の型を持つ) へのポインターを保持し、ルートからオクツリーを毎回トラバースすることができます。ステップ。ただし、現在のノードを追跡できる、より「ローカル」なオプションを希望します。これにより、可能であればツリーの下位から開始できるため、octree の上位ノードを不必要にトラバースすることを回避できます。

しかし、スライスを経験しないように、その型ポインターが何であるか (またはこれを実装する他の方法) がわからない。

ディメンションは単純に として実装できるため、テンプレートに縛られていませんlong const。しかし、葉がinodeとは異なる子タイプを持つようにする方法がわかりません。

ご協力いただきありがとうございます！

アップデート

これに似た方法ではなく、このようにしたい理由は、各ノードの変数のためですcount。カウントが 0 の場合、キューブ全体をジャンプしたいので、葉を通過する時間を無駄にします。私は空であることを知っています。(これはレイトレーシング ボクセル エンジン用です。)

4

1 に答える 1

0

私はテンプレートが大好きですが、コードは実際には次のように単純化できます。

class node {
  node* parent; // NULL for root node
  long dim;
  long count;
  virtual rayTrace(Ray) = 0;
};
class leafNode : node {
  data_t data;
  virtual rayTrace(Ray);
};
class nonLeafNode : node {
  vector<node*> children;
  virtual rayTrace(Ray);
};

これには、一部のサブツリーが他のサブツリーよりも深くなる可能性があることを含め、ツリーを任意の深さにすることができるという利点があります。実行時に dim を計算する必要があるという欠点がありますが、それでも、ツリーが非常に大きくなった場合に double にすることができるという銀の裏地があります。

于 2013-01-25T22:52:38.520 に答える