Serialize AABB Tree data

[hucancode]

Hello, i am working with AABB Tree. Thanks to CGAL we can handle the intersection very easy. But we had some difficult building the tree. There are about > 1M tris on our (static) scene. Build process usually take several minutes to finish. I am thinking of building AABB Tree once, then serialize them into file. From then i load the file instead of build the whole tree. I wonder if it would be supported in the future or not? Here is my serialize/deserialize naive implementation. It didn't work. If you had interest, drop me some hint, i would appreciate it much.

void CollisionDetector::SerializeTree()
{
    typedef char byte;
    {
        unsigned int mem;
        byte* raw_data;
        {
            mem = mTree.size() * sizeof(Primitive);
            raw_data = reinterpret_cast<byte*>(mTree.m_primitives.data());
        }
        {
            std::ofstream fout("aabb_prim_data.txt", std::ios::binary);
            byte* mem_b = reinterpret_cast<byte*>(&mem);
            fout.write(mem_b, 4);
            fout.write(raw_data, mem);
            fout.close();
        }
    }
    {
        unsigned int mem;
        byte* raw_data;
        {
            mem = mTree.size() * sizeof(AABBNode);
            AABBNode* root = mTree.m_p_root_node;
            raw_data = reinterpret_cast<byte*>(root);
        }
        {
            std::ofstream fout("aabb_tree_node_data.txt", std::ios::binary);
            fout.write(reinterpret_cast<byte*>(&mem), 4);
            fout.write(raw_data, mem);
            fout.close();
        }
    }
}
void CollisionDetector::DeserializeTree()
{   
    typedef char byte;
    {
        unsigned int mem;
        unsigned int size;
        byte* raw_data;
        {//load data
            std::ifstream fin("aabb_prim_data.txt", std::ios::binary);
            byte* mem_b = reinterpret_cast<byte*>(&mem);
            fin.read(mem_b, 4);
            size = mem / sizeof(Primitive);
            raw_data = new byte[mem];
            fin.read(raw_data, mem);
            fin.close();
        }
        {//apply
            Primitive* data = reinterpret_cast<Primitive*>(raw_data);
            mTree.m_primitives.reserve(size);
            mTree.m_primitives.assign(data, data + size);
        }
    }
    {
        unsigned int mem;
        unsigned int size;
        byte* raw_data;
        {//load data
            std::ifstream fin("aabb_tree_node_data.txt", std::ios::binary);
            fin.read(reinterpret_cast<byte*>(&mem), 4);
            size = mem / sizeof(AABBNode);
            raw_data = new byte[mem];
            fin.read(raw_data, mem);
            fin.close();
        }
        {//apply
            AABBNode* root = new AABBNode[size];
            mTree.m_p_root_node = root;
            byte* data = reinterpret_cast<byte*>(root);
            std::copy(raw_data, raw_data + mem, data);
        }
        ExpandNode(mTree.m_p_root_node,
            mTree.m_primitives.begin(), mTree.m_primitives.end(), mTree.m_primitives.size());
        mTree.m_need_build = false;
    }
}
void CollisionDetector::ExpandNode(AABBNode* root,
    std::vector<Primitive>::iterator first,
    std::vector<Primitive>::iterator beyond,
    const std::size_t range)
{
    //root->m_bbox = mTree.m_traits.compute_bbox_object()(first, beyond);
    //mTree.m_traits.sort_primitives_object()(first, beyond, root->m_bbox);
    switch (range)
    {
    case 2:
        root->m_p_left_child = &(*first);
        root->m_p_right_child = &(*(++first));
        break;
    case 3:
        root->m_p_left_child = &(*first);
        root->m_p_right_child = static_cast<AABBNode*>(root) + 1;
        ExpandNode(static_cast<AABBNode*>(root->m_p_right_child),
            first + 1, beyond, 2);
        break;
    default:
        const std::size_t new_range = range / 2;
        root->m_p_left_child = static_cast<AABBNode*>(root) + 1;
        root->m_p_right_child = static_cast<AABBNode*>(root) + new_range;
        ExpandNode(static_cast<AABBNode*>(root->m_p_left_child),
            first, first + new_range, new_range);
        ExpandNode(static_cast<AABBNode*>(root->m_p_right_child),
            first + new_range, beyond, range - new_range);
    }
}

[lrineau]

AABB tree are quite difficult to serialize in general.

Most of the issues in serialization are pointers. Depending on the type of primitives, the primitives can contains their own data, or be just a pointer to something. In the later case, you need to serialize/deserialize also the external data.

But let's assume, for the moment, that the primitives do not refer to external data...

For the serialization of nodes, I would first substract tree.root_node() to all m_p_left_child and m_p_right_child, and, after the read in the deserialization, add tree.root_node() to all of them. That would avoid the part ExpandNode of your code after the deserialization.

In your code, there is another error, about the memory allocation in the deserialization: raw_data is allocated but never deallocated.

[lrineau]

@sloriot The problem is quite interesting, and could be reused in CGAL.

[afabri]

Without being familiar with this topic, we should maybe also have a look at what boost.org offers for serialization.

[lrineau]

Boost Serialization seems a good library. Should we try to make CGAL objects compatible with it?

For all CGAL objects of the kernel, in the C3/H3 versions, we should add a new method template:

template<class Archive>
void serialize(Archive & ar, const unsigned int version) {
  ar & base;
}

and then in the global objects like: CGAL::Point_3:

template<class Archive>
void serialize(Archive & ar, const unsigned int version) {
  ar & boost::serialization::base_object<Rep>(*this);
}

http://www.boost.org/doc/libs/1_60_0/libs/serialization/doc/

[hucancode]

Thank Irineau for your suggestion. I'm glad you concern this matter. However, let alone these silly error (memory allocation, unoptimized save/load), can you please point out which data/field did i miss in the code above. m_primitives or m_p_nodes? I assume that:

• m_p_nodes refer to m_primitives.
• m_primitives contain data themself.
• m_primitives and m_p_nodes are everything AABB tree needs. (I did see some search tree or so in the code but i think it is redundant in my case).

Is it right?

[sgiraudot]

@lrineau any idea on the latest question?

[lrineau]

@hucancode Without seeing the type the Primitive (and more generally the full type of the AABB tree), I cannot tell. As I said earlier, in https://github.com/CGAL/cgal/issues/993#issuecomment-207445545, most of our Primitive types are not self-contained, and contain pointers to memory in the heap. If that was the case, just writing-reading the raw data will just lead to invalid pointers, pointing to random memory, whereas a proper serialization code would also serialize the pointed objects, and convert pointers to indices.

[sloriot]

The AABB-tree being now movable (internal pointers are now gone), this feature should be easier to address if someone is interested in it.

[Gu4ty]

Hello. Has there been any progress or workaround on this? I have a similar problem.