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);
				}
			}
		}

Try this:

				if(box_box_intersect(musa::triangle_bounding_box(tri), node->region)) 
// parent box ovelaps current triangle
				{
					auto vertices = node->faces;

					cg::CG_Polygon poly;
					poly.vertices = mn::buf_new<CG_Vertex>();
					for (size_t a = 0; a < vertices.count; a += 3)
					{
						// ...
					}					


// this else is wrong - it visits children only if the parent has NO overlap, which is the opposite of what we want.
				//}
				//else 
				//{

// now we visit children only if parent overlaps, as intended
					for (auto& n : node->octants)
					{
						if (n == nullptr)
							continue;
						stack.push(n);
					}
				}

After this change it should process all potential intersections (like before, just faster).

But i don't think it will work, because you make assumptions about front or back sides. This works with BSP, but not for Octree:

Here i have blue and black models, and near a intersection we can tell front or back from the normal. But if there is no intersection (orange) we don't know if it's inside or outside. We could propagate this information from known faces near intersection if we had adjacency information in the mesh, but even then we would get failures if the meshes are not closed and watertight.

Similar case to show things can become complicated:

Every face can have multiple intersections and so different front and back sides.

Thus my proposal is to add intersection edges in a first step, but not delete anything yet. We can delete faces only after all intersections are known. We also need to link new polygons which has been split to the original face in the octree, so we can still refer octree cells to those newly added faces.

So after this first step, we have a combined polygon soup with no intersecting faces (drawn some of them in green):

After this you could use my inside / outside test, e.g. to find all green faces which are inside the original grey model, or at the surface of black model but inside the blue model, and remove them.

Likely the result won't be as perfect as with the BSP method, but it could process high detail geometry where BSP fails due to precision and performance.

AhmedSaleh said:
So you mean the triangle to triangle intersection should get intersection segments and add them to a list ?

Yeah, but while the intersection of two meshes is a path of new edges, i'd hope we get away with only handling faces. One original face will be cut apart multiple times:

Blue triangle cuts black triangle into 3 sub triangles. So the black triangle no longer exists, but the octree still refers to it, so we need to link sub triangles to the original face. After some time we may need to cut further with another blue triangle:

I think that's where the complexity is. We need to do the same on the blue triangles as well of course, and we don't know yet which triangles could be deleted.

So, some code looks like this:

struct Triangle
{
	vec3 vertices[3];
	bool active = true; // we need this only for splitTriangles, but i put it here for simplicity
};

struct CutableTriangle
{
	Triangle initialTriangle;
	AABox boundingBox;
	std::vector<Triangle> splitTriangles;
};

void PrepareMeshForCSG (
	std::vector<CutableTriangle> &preparedTriangles,
	const std::vector<Triangle> &meshTriangles)
{
	for (auto &tri : meshTriangles)
	{
		CutableTriangle n;
		n.initialTriangle = tri;
		n.splitTriangles.push_back(tri); // we start with a copy
		n.boundingBox = CalcBBoxFromTriangle(tri);
		preparedTriangles.push_back(n);
	}
}

bool SplitTrianlges (
	std::vector<Triangle> &addSplittedTrianglesToThisList,
	const Triangle &triangleToSplit,
	const Triangle &cuttingTriangle)
{
	// todo:
	// cut triangleToSplit into new (active) sub triangles, so the intersction with cuttingTriangle becomes a new edge
	// return true if triangleToSplit has been split up, false if nothing happened
	return true;
}
	

// we could now make a octree from preparedTriangles, but to keep it simple i'll do it with brute force

void IntersectMeshes (
	std::vector<CutableTriangle> &meshA, 
	std::vector<CutableTriangle> &meshB)
{
	for (auto &triA : meshA) // todo: use octree
	for (auto &triB : meshB)
	{
		if (!triA.boundingBox.Overlaps(triB.boundingBox))
			continue;
			
		// split intersecting stuff to new split triangles, deactivate triangles whaich has been splitted
			
		for (auto &splitTriA : triA.splitTriangles) if (splitTriA.active)
		for (auto &splitTriB : triB.splitTriangles) if (splitTriB.active)
		{
			splitTriB.active = !SplitTrianlges (
					triB.splitTriangles,
					splitTriB,
					splitTriB);
		}
		
		// do the same vice versa. todo: avoid redundant work here
		
		for (auto &splitTriA : triB.splitTriangles) if (splitTriA.active)
		for (auto &splitTriB : triA.splitTriangles) if (splitTriB.active)
		{
			splitTriB.active = !SplitTrianlges (
					triB.splitTriangles,
					splitTriB,
					splitTriB);
		}
	}
}

If this works as expected (which i'm not sure of!), you could then make a new mesh from all split triangles which are still active.

Then use the inside outside test routine to implement CSG ops.

Looks good : ) It finds all polygons that need splitting on one mesh.

AhmedSaleh said:
now I'm getting into the problem of inside or outside I think…

No, no. There is a long way to go. First you need to do all the poly clipping, so the intersection path exists in both meshes.

You know, result should look like this then, pretty messy:

I left this as todo in my function ‘SplitTrianlges’.

I think it's the hardest part. You already have poly clipping functions, but maybe still a full day of work to get it right.

Only after all this is done, and all final triangles are known, you can remove triangles using inside outside test.