Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

octree with stxxl

2008-09-03
2013-04-25
  • Hey,

    I try to build an out-of-core octree with stxxl for my diploma thesis. My octree is a combination of a btree and a pointer tree. The btree is for fast searching, deleting and adding of octree nodes. The pointer structure is for fast traversing the octree.

    Therefor I used the stxxl::btree for storing the octree nodes and there indices. This works fine. But for my combi octree the inner nodes have to consist of pointers to there child nodes just like in a normal octree. In the documentation is mentioned that pointers aren't supported for the offered containers. So I took the stxxl::btree::btree::iterator as recommended. The problem is now that I have a recursive class definition in octree_node: the octree_node needs the octree_iterator, the octree_iterator needs the btree_type, and the btree_type needs the value_type which is the octree_node. But the octree_node isn't defined at this time. So the cycle is closed and it won't compile.

    So I ask, is there a solution or workaround for this problem? Maybe there is a even better way to build an octree with stxxl? Any advice is appreciated.

    Here's the code:

    #include "stxxl.h"
    #include "stxxl\bits\containers\btree\btree.h"

    using namespace stxxl;

    template <typename Tp, unsigned Dim=3>
    class octree
    {
    public:
        enum { dim = Dim };

        typedef unsigned __int64 octree_tick;
       
        class octree_node;
       
        typedef Tp type;
        typedef octree_node value_type;
        typedef octree_tick key_type;
       
        struct comp_type : public std::less<key_type>
        {
            static key_type max_value()
            {
                return (std::numeric_limits<key_type>::max)();
            }
        };

        typedef btree::btree<key_type, value_type, comp_type, 4096, 4096, SR> btree_type;
        typedef typename btree_type::iterator octree_iterator;
       
        class octree_node
        {
        public:
            octree_node() {}
            ~octree_node() {}

            type value;
            octree_iterator children[8]; // error c2146: the octree_node isn't yet defined
            int level;
        };

        octree()
        {
            bp = new btree_type(25 * 1024 * 1024, 25 * 1024 * 1024);
        }

        ~octree()
        {
            delete bp;
        }

    private:
        btree_type* bp;
    };

    int main()
    {
        octree<int> o;
            return 0;

     
    • First of all, this is not a STXXL problem, but a generic C++ problem.
      One thing you can always do is to declare a void pointer and to cast to the right type when enough information is there for the compiler. And I don't see a better solution here, but I might be wrong.

      void* children[8];

      later in some non-inline routine

      static_cast<octree_iterator*>(children[i])

      and so on.

      -- Johannes