AhmedSaleh said:
I did it with bsp, now I wanna do it using octree for practices.
Ha, ok. : ) Notice, BSP has volume cells with a boundary defined from planes, and so has all the exact inside / outside or solid / empty information i've talked about before. But octree usually has no such information and only contains surface polygons.
I remember this paper about doing CSG with octree: https://www.graphics.rwth-aachen.de/media/papers/boolean_021.pdf
Personally i use octrees for CSG too, but i do this only on the volume data which is easy. Then i remesh the result for good edge flow. Maybe a bit similar to this: https://www.graphics.rwth-aachen.de/media/papers/feature1.pdf
You see this two examples are completely different things, with different applications and limitations. Thus i can not tell you any general ‘CSG by using octrees’ algorithm, because the question is too broad.
AhmedSaleh said:
Would you elaborate more about the efficacy code ?
Yeah, i assume you have one octree per mesh, and the octree contains faces but has no inside / outside information. I also assume you want to use this to speedup finding potential intersection pairs. So, in my context this is unrelated to the problem of doing CSG, it only is about optimization. (Contrary to the examples above or what you might have in mind.)
So we can talk about this in a general context. With spatial trees, we mostly do 3 things: Point queries, range queries and ray tracing. In this case we want a range query, precisely our range is a bounding box. Pseudo code, recursive for simplicity:
QueryBox (const TreeNode &node, const AABox &queryBox, const MyData &queryInfo)
{
if (node.boundingBox.Intersects(queryBox)
{
ProcessContent(node, queryInfo); // e.g. add pairs of interecting triangles to a list
for (int i=0; i<node.childCount; i++)
if (node.child[i]) QueryBox (node.child[i]);
}
}
This code would work for both octree, BVH, etc. My point is: The recursive child calls only happen if boxes overlap. If they don't, their children won't overlap either. Because the bound of a parent also bounds all bounds of all its descendants. So we can skip processing the whole sub branch of the tree, which usually is the primary reason to use spatial acceleration structures.
You have missed this here:
std::stack < cg::Octant*> stack;
for (size_t i = 0; i < ilist.count; i ++)
{
stack.push(root);
while (!stack.empty())
{
cg::Octant* node = stack.top();
stack.pop();
// ...
for (auto& n : node->octants) // <- no condition - you always process the whole tree
{
if (n == nullptr)
continue;
stack.push(n);
}
}
}