CGAL - SourceCode - Surface_ intersection_ visitor_ for_ Core definition source code reading

CGAL - SourceCode - Surface_ intersection_ visitor_ for_ Core definition source code reading

stay CGAL - SourceCode - box_intersection_d source code reading This paper introduces how to use box intersection to quickly find intersection pairs.

And in PaperImpl- Fast Software for Box Intersections This paper introduces how to use c + + to realize box intersection.

stay CGAL - SourceCode - Intersection_of_triangle_meshes source code reading This paper has introduced the specific calculation and implementation of the intersection line between two triangular meshes. However, there is no further expansion on how to reconstruct the mesh after the intersection lines are calculated. The text is surface_ intersection_ visitor_ for_ Record of core definition code reading.

Code location: CGAL\Polygon_mesh_processing\internal\Corefinement\Visitor.h

The implemented code entry function is: finalize, as follows:

  void finalize(Intersection_nodes<TriangleMesh,
                 VertexPointMap, Predicates_on_constructions_needed>& nodes,
                 const TriangleMesh& tm1,
                 const TriangleMesh& tm2,
                 const VertexPointMap& vpm1,
                 const VertexPointMap& vpm2)

    TriangleMesh* tm1_ptr = const_cast<TriangleMesh*>(&tm1);
    TriangleMesh* tm2_ptr = const_cast<TriangleMesh*>(&tm2);

    std::map<TriangleMesh*, VertexPointMap> vpms;
    vpms[tm1_ptr] = vpm1;
    vpms[tm2_ptr] = vpm2;

    vertex_descriptor null_vertex = Graph_traits::null_vertex();
    const Node_id nb_nodes = nodes.size();
    // we reserve nb_nodes+3 because we use the last three entries for the
    // face triangulation
    mesh_to_node_id_to_vertex[tm1_ptr].resize(nb_nodes+3, null_vertex);
    mesh_to_node_id_to_vertex[tm2_ptr].resize(nb_nodes+3, null_vertex);

    //store for each triangle face which boundary is intersected by the other surface,
    //original vertices (and halfedges in the refined mesh pointing on these vertices)
    typedef boost::unordered_map<face_descriptor,Face_boundary> Face_boundaries;
    std::map<TriangleMesh*,Face_boundaries> mesh_to_face_boundaries;

    //0) For each triangle mesh, collect original vertices that belongs to the intersection.
    //   From the graph of constraints, extract intersection edges that are incident to such vertices. In case
    //   there exists another original vertex adjacent to the first one found, this halfedge must be
    //   marked on the boundary (and possibly update an_edge_per_polyline).
    //   This is done first to avoid halfedges stored to be modified in the steps following.
    for (typename Mesh_to_vertices_on_intersection_map::iterator
      // ......

    //1) First split halfedges cut by the intersection polyline(s)
    for (typename std::map<TriangleMesh*,On_edge_map>::iterator
      it=on_edge.begin(); it!=on_edge.end(); ++it)
      // ......

    //2)triangulation of the triangle faces containing intersection point in their interior
    //  and also those with intersection points only on the boundary.
    for (typename std::map<TriangleMesh*,On_face_map>::iterator
      it=on_face.begin(); it!=on_face.end(); ++it)
      // ...


    // additional operations

It is found from the code comments that there are three main steps to realize this:

  1. For each triangular mesh, collect which points in the original vertices belong to intersections. From the constraint graph, find the intersecting edges related to these vertices. If two adjacent original vertices form an intersecting edge, the half edge must be marked as a boundary (and an_edge_per_polyline may be updated). By performing this step first, you can avoid modifying the half of the storage in the following steps.
  2. Cut the half edge according to the intersection line;
  3. Triangulate the triangular surface with intersection inside and the triangular surface with intersection only on the boundary;

If you only need a simple understanding of the principle, you can end here.

1. Original vertex intersection judgment

The first data structure to understand is Mesh_to_vertices_on_intersection_map.

   typedef std::vector<Node_id>                                        Node_ids;      // An array that stores the node id
   typedef boost::unordered_map<face_descriptor,Node_ids>           On_face_map;      // Relationship between triangular patch and corresponding nodes
   typedef boost::unordered_map<edge_descriptor,Node_ids>           On_edge_map;      // Relationship between triangle edge and corresponding nodes
   //to keep the correspondance between node_id and vertex_handle in each mesh
   typedef std::vector<vertex_descriptor>                     Node_id_to_vertex;      // Correspondence between nodeid and vertex
   typedef std::map<TriangleMesh*, Node_id_to_vertex >         Mesh_to_map_node;
   //to handle coplanar halfedge of polyhedra that are full in the intersection
   typedef std::multimap<Node_id,halfedge_descriptor>    Node_to_target_of_hedge_map; // Relationship between nodeid and half edge
   typedef std::map<TriangleMesh*,Node_to_target_of_hedge_map>
                                           Mesh_to_vertices_on_intersection_map;      // On each mesh, the mapping relationship between intersection and half edge

Then take a look at the implementation of the first step:

for (typename Mesh_to_vertices_on_intersection_map::iterator
     ++it)  // Traverse each mesh
    TriangleMesh& tm=*it->first;
    //   Face_boundaries& face_boundaries=mesh_to_face_boundaries[&tm];

    Node_to_target_of_hedge_map& nodes_to_hedge=it->second;
    for(typename Node_to_target_of_hedge_map::iterator
        ++it_node_2_hedge) // Traverse node
        Node_id node_id_of_first=it_node_2_hedge->first;
        // Gets the neighborhood node of the node. If the neighborhood node is empty, it is an outlier
        std::vector<Node_id>& neighbors=graph_of_constraints[node_id_of_first];
        if ( !neighbors.empty() )
            // Traverse neighborhood points
            BOOST_FOREACH(Node_id node_id, neighbors)
                //if already done for the opposite
                if (node_id >= node_id_of_first) continue;

                typename Node_to_target_of_hedge_map::iterator
                    it_node_2_hedge_two = nodes_to_hedge.find(node_id);
                // The adjacent points are also on the half
                if ( it_node_2_hedge_two!=nodes_to_hedge.end() ) //a full edge is on intersection
                    //get the corresponding halfedge with vertex corresponding to node_id_of_first
                    halfedge_descriptor hedge=it_node_2_hedge->second;
                    halfedge_descriptor start=hedge;
                    bool did_break=false;
                    while ( source(hedge,tm) !=
                           target(it_node_2_hedge_two->second,tm) )
                        if (tm1_ptr==tm2_ptr && hedge==start)
                            // ...  Special case handling
                    if (did_break) continue;
                    // Build associated edges and place them in marks_on_edges´╝îoutput_ Inside the builder.
                    std::pair<Node_id,Node_id> edge_pair(node_id,node_id_of_first);
                    // output_builder is used to build the grid for Boolean relation
            std::cout << "X1: Found an isolated point" << std::endl;

2. Half cutting

// on_ The type of edge is: STD:: Map < trianglemesh *, on_edge_ map> on_edge;
// Represents the relationship between each mesh and the corresponding edge and intersection
for (typename std::map<TriangleMesh*,On_edge_map>::iterator
     it=on_edge.begin(); it!=on_edge.end(); ++it)
    TriangleMesh& tm=*it->first;
    const VertexPointMap& vpm=vpms[&tm];
    On_edge_map& on_edge_map=it->second;
    On_face_map& on_face_map=on_face[&tm];
    Face_boundaries& face_boundaries=mesh_to_face_boundaries[&tm];

    for(typename On_edge_map::iterator it2=on_edge_map.begin();
        //Gets the split half
        halfedge_descriptor hedge=halfedge(it2->first,tm);
        //indices of the nodes to be inserted
        Node_ids& node_ids=it2->second;
        CGAL_assertion( std::set<Node_id>(node_ids.begin(), node_ids.end())
                       .size()==node_ids.size() );
        //Sort intersections on edges

        //save original face and nodes for face of hedge (1)
        // Save the original faces and nodes of the edge (1)
        if ( !is_border(hedge,tm) ){
            face_descriptor f=face(hedge,tm);
            typename Face_boundaries::iterator it_face = face_boundaries.find(f);
            if (it_face==face_boundaries.end())

        //save original face and nodes for face of hedge->opposite (2)
        // Save the original faces and nodes of the faces opposite the edge of the hedge
        typename Face_boundaries::iterator opposite_original_info=face_boundaries.end();
        halfedge_descriptor hedge_opp = opposite(hedge,tm);
        if ( !is_border(hedge_opp,tm) ){
            face_descriptor f=face(hedge_opp,tm);
            if (opposite_original_info==face_boundaries.end())

        /// ......
        //do split the edges
        //The key codes of split are as follows:
        CGAL_assertion_code(vertex_descriptor expected_src=source(hedge,tm));
        BOOST_FOREACH(std::size_t node_id, node_ids)
            // Split new hedge
            halfedge_descriptor hnew = Euler::split_edge(hedge, tm);
            /// New vertex
            vertex_descriptor vnew=target(hnew,tm);
            //          user_visitor.new_vertex_added(node_id, vnew, tm); // NODE_VISITOR_TAG
            nodes.call_put(vpm, vnew, node_id, tm);
            // register the new vertex in the output builder
            // Register the new vertex to output_ In Builder
            output_builder.set_vertex_id(vnew, node_id, tm);
            // Establish the relationship between the newly created vertex and node
            if (first){

            //update marker tags. If the edge was marked, then the resulting edges in the split must be marked
            if ( hedge_is_marked )


        /// ......

3. Triangulation

TODO: this part of the code is very complex. For the time being, we can only understand that it is used for triangulation. How to do it specifically needs to understand how to realize simple triangulation. In subsequent articles, we will learn this part and supplement this part.

Added by anjanesh on Wed, 05 Jan 2022 09:43:45 +0200