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)
{
nodes.all_nodes_created();
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
it=mesh_to_vertices_on_inter.begin();
it!=mesh_to_vertices_on_inter.end();
++it)
{
// ......
}
//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)
{
// ...
}
nodes.finalize();
// additional operations
output_builder(nodes,
input_with_coplanar_faces,
is_node_of_degree_one,
mesh_to_node_id_to_vertex);
}
It is found from the code comments that there are three main steps to realize this:
- 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.
- Cut the half edge according to the intersection line;
- 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=mesh_to_vertices_on_inter.begin();
it!=mesh_to_vertices_on_inter.end();
++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=nodes_to_hedge.begin();
it_node_2_hedge!=nodes_to_hedge.end();
++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) )
{
hedge=opposite(next(hedge,tm),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);
call_put(marks_on_edges,tm,edge(hedge,tm),true);
// output_builder is used to build the grid for Boolean relation
output_builder.set_edge_per_polyline(tm,edge_pair,hedge);
}
}
}
#ifdef CGAL_COREFINEMENT_DEBUG
else
{
std::cout << "X1: Found an isolated point" << std::endl;
}
#endif
}
}
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();
it2!=on_edge_map.end();
++it2)
{
//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
sort_vertices_along_hedge(node_ids,hedge,tm,vpm,nodes);
//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())
it_face=face_boundaries.insert(std::make_pair(f,Face_boundary(hedge,tm))).first;
it_face->second.copy_node_ids(hedge,node_ids.begin(),node_ids.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);
opposite_original_info=face_boundaries.find(f);
if (opposite_original_info==face_boundaries.end())
opposite_original_info=face_boundaries.insert(std::make_pair(f,Face_boundary(hedge_opp,tm))).first;
opposite_original_info->second.copy_node_ids(hedge_opp,node_ids.rbegin(),node_ids.rend());
}
/// ......
//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);
CGAL_assertion(expected_src==source(hnew,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
node_id_to_vertex[node_id]=vnew;
if (first){
first=false;
hedge_incident_to_src=next(opposite(hedge,tm),tm);
}
//update marker tags. If the edge was marked, then the resulting edges in the split must be marked
if ( hedge_is_marked )
call_put(marks_on_edges,tm,edge(hnew,tm),true);
CGAL_assertion_code(expected_src=vnew);
}
/// ......
}
}
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.