Substract closed mesh from surface (CGAL?)

Question

I have the following problem, best described with the picture below.

I have a surface in 3D, so it can have vertical overlap and is a non-closed mesh. And I have an object which I want to subtract from it. The green+yellow area is the original surface, the red lines outline a sphere (as triangulated mesh, not a primitive). The yellow area is the part of the surface intersecting the sphere that needs to be removed from the original surface. The green area is the result of the subtraction: the surface that is needed.

I am already using the CGAL library, but still new to it, so a solution using CGAL would be the most preferred. However if somebody has a solution without CGAL that would be welcome as well.

The best way I can see would be to give the surface a slight thickness (keeping the current surface as the bottom). And then use Nef_polyhedron_3 to substract the other object, then convert to Polyhedron_3 and only keep the bottom faces. But this seems like a bit of a hack.

EDIT: Using the proposed solution I get very close, but I am unable to clip to the correct side using the reversed normals as proposed, using the following code. I also tried to see if face vertex ordering (clockwise / counter clockwise) has any effect, but it seems not to have any.

typedef CGAL::Simple_cartesian<double>                  SC;
typedef CGAL::Surface_mesh<SC::Point_3>                 SurfaceMesh;
typedef SurfaceMesh::Property_map<SM_fid, SC::Vector_3> SM_fnormals;
typedef SurfaceMesh::Vertex_index                       SM_vid;
typedef SurfaceMesh::Face_index                         SM_fid;

namespace PMP = CGAL::Polygon_mesh_processing;
namespace params = PMP::parameters;

void clip(SurfaceMesh P&, SurfaceMesh& Q) {        
    SM_fnormals fnormals = CGALobstacle->add_property_map<SM_fid, SC::Vector_3>
        ("f:normals", CGAL::NULL_VECTOR).first;

    PMP::compute_face_normals(Q, fnormals);

    PMP::clip(P, Q, false, params::all_default(), params::face_normal_map(fnormals));
}

sloriot sloriot · Accepted Answer · 2017-08-02T18:45:37

There is an undocumented function starting from CGAL 4.10 in Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/internal/clip.h. The function signature is :

/// requires face_index_map, vertex_index_map for np_tm
/// requires face_index_map for np_c
/// if edge_is_constrained_map is not provided in np_tm a default one is
/// provided using boost::unordered_set<edge_descriptor>
template <class TriangleMesh,
          class NamedParameters1,
          class NamedParameters2>
bool
clip(      TriangleMesh& tm,
 /*const*/ TriangleMesh& clipper,
           bool close,
     const NamedParameters1& np_tm,
     const NamedParameters2& np_c)

The second parameter would be your sphere and the first your surface. The third indicates if you want the output surface to be closed (so false in your case). Note that the function is clipping so if you want the outside part of the sphere you need to reverse the orientation of your sphere (inward normals).

There is a usage example here.

I recommend using Surface_mesh rather than Polyhedron_3.

Note that the function is not documented and the header might disappear in an upcoming release (if it does it means that it got officially documented).

EDIT: The officially documented function since CGAL 4.13 is here.

Substract closed mesh from surface (CGAL?)

1 Answers