Ray to Octree Intersection for boolean geometry

Question

I'm trying to do boolean geometry that I have two meshes and would like to compute the intersection between them.

So I construct an octree from mesh A, and I check the vertices from mesh B against the octants, if there is an intersection, check the octant triangles for intersection, then I add the triangles, construct a mesh.

auto intersected_octant_faces = mn::buf_new<musa::Triangle>();
    std::stack < cg::Octant *> stack;
    stack.push(octree_sphere.root);
    for (size_t i = 0; i < tri_mesh_cube.vertices.count; i++)
    {
        while (!stack.empty())
        {
            cg::Octant* node = stack.top();
            if (!node)
                break;
            stack.pop();

            musa::Ray ray;
            ray.origin = { tri_mesh_cube.vertices[i] };
            ray.dir = { 1,0,0 };

            musa::Intersection_Points pts = {};
            pts = musa::ray_box_intersection(ray, node->region);
            if (pts.count >= 1)
            {
                musa::Intersection_Points t = {};
                auto vertices = node->faces;
                for (size_t j = 0; j < vertices.count; j += 3)
                {
                    musa::Triangle tri{ vertices[j], vertices[j + 1], vertices[j + 2] };
                    t = musa::ray_triangle_intersection(ray, tri);
                    if (t.count == 1)
                    {
                        mn::buf_push(intersected_octant_faces, tri);
                    }
                }

            }
            for (auto& n : node->octants)
            {
                stack.push(n);
            }
        }
    }

Right now I get just two faces as shown in the figure and not sure where is the problem.

Update:

I have followed the algorithm that Spektre says, and that's the result:

auto tri_mesh_a = cg::trimesh_from_indexed_mesh(sphere_indexed_mesh);
    auto tri_mesh_b = cg::trimesh_from_indexed_mesh(cube_indexed_mesh);
    auto octree_a = cg::octree_from_mesh(tri_mesh_a);
    
        std::stack < cg::Octant*> stack;

        for (size_t i = 0; i < tri_mesh_b.vertices.count; i += 3)
        {
            musa::Triangle triB{ tri_mesh_b.vertices[i], tri_mesh_b.vertices[i + 1], tri_mesh_b.vertices[i + 2] };
            stack.push(octree_a.root);

            while (!stack.empty())
            {
                cg::Octant* node = stack.top();
                stack.pop();

                if (box_box_intersect(musa::triangle_bounding_box(triB), node->region))
                {
                    auto vertices = node->faces;

                    for (size_t a = 0; a < vertices.count; a += 3)
                    {
                        musa::Triangle triA{ vertices[a], vertices[a + 1], vertices[a + 2] };

                        if (triangle_triangle_intersection_check(triB, triA))
                        {
                            vec3 v1 = { vertices[a] };
                            vec3 v2 = { vertices[a + 1] };
                            vec3 v3 = { vertices[a + 2] };

                            mn::buf_push(self->modelIntersection.points, v1);
                            mn::buf_push(self->modelIntersection.points, v2);
                            mn::buf_push(self->modelIntersection.points, v3);


                        }



                    }

                    for (auto& n : node->octants)
                    {
                        if (n == nullptr)
                            continue;
                        stack.push(n);
                    }
                }
            }
        }

 
    for (int i = 0; i < self->modelIntersection.points.count; i++)
    {
        mn::buf_push(self->modelIntersection.indices, i);
    }

Answer 1

Let assume: sphere is object A and the Octree o is populated with it. The cube is object B and both objects are constructed from only triangles.

1. for each triangle of B

   so loop through all triangles of B and test one at a time let call it tb. Let call the triangle points: tb.p0, tb.p1, t.p2

2. obtain all o nodes intersecting tb triangle

   In case your Octree does not have triangle testing you can simplify by testing lines:

   line(tb.p0,tb.p1)
   line(tb.p1,tb.p2)
   line(tb.p2,tb.p0)
   

   Its not complete test but in most cases its enough. You can also test few inside lines to cover some interior if needed:

   pp = (tb.p0 + tb.p1 + tb.p2) / 3
   line(tb.pp,tb.p0)
   line(tb.pp,tb.p1)
   line(tb.pp,tb.p2)
   

   However if you need full test you would most likely need to implement it the hard way (triangle vs cube intersection).

3. for each found intersecting node test all its triangles against tb

   So now you do triangle from A versus triangle tb test and store all triangles from A that intersects.

   Here example of the full test: line closest(triangle t0,triangle t1)

   There will be probably many duplicate triangles in the result so you might add a duplicity test before adding new triangle to the result.