// Copyright (c) 2017 GeometryFactory (France). // All rights reserved. // // This file is part of CGAL (www.cgal.org). // // $URL: https://github.com/CGAL/cgal/blob/v5.2/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/detect_features.h $ // $Id: detect_features.h c253679 2020-04-18T16:27:58+02:00 Sébastien Loriot // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial // // // Author(s) : Laurent Rineau, Stephane Tayeb, Maxime Gimeno // #ifndef CGAL_POLYGON_MESH_PROCESSING_DETECT_FEATURES_IN_POLYGON_MESH_H #define CGAL_POLYGON_MESH_PROCESSING_DETECT_FEATURES_IN_POLYGON_MESH_H #include #include #include #include #include #include #include #include namespace CGAL { namespace Polygon_mesh_processing { namespace internal { template Int generate_patch_id(Int, int i) { return Int(i); } template std::pair generate_patch_id(std::pair, int i) { return std::pair(i, 0); } template bool is_sharp(PolygonMesh& polygonMesh, const typename boost::graph_traits::halfedge_descriptor& he, const typename GT::FT& cos_angle) { typedef typename boost::graph_traits::face_descriptor face_descriptor; if(is_border(edge(he,polygonMesh),polygonMesh)){ return false; } face_descriptor f1 = face(he,polygonMesh); face_descriptor f2 = face(opposite(he,polygonMesh),polygonMesh); const typename GT::Vector_3& n1 = Polygon_mesh_processing::compute_face_normal(f1,polygonMesh); const typename GT::Vector_3& n2 = Polygon_mesh_processing::compute_face_normal(f2,polygonMesh); if ( n1 * n2 <= cos_angle ) return true; else return false; } //wrapper for patchid map. template::value_type> struct PatchIdMapWrapper { typedef typename boost::property_traits::category category; typedef ValueType value_type; typedef typename boost::property_traits::reference reference; typedef typename boost::property_traits::key_type key_type; PatchIdMap map; int offset; PatchIdMapWrapper(PatchIdMap map, int offset) : map(map), offset(offset){} }; template typename PatchIdMapWrapper::value_type get(PatchIdMapWrapper& map, Handle_type h) { typedef typename PatchIdMapWrapper::value_type value_type; return value_type(get(map.map, h) - map.offset); } template void put(PatchIdMapWrapper& map, Handle_type h, typename PatchIdMapWrapper::value_type pid) { typedef typename PatchIdMapWrapper::value_type value_type; put(map.map, h, value_type(pid + map.offset)); } //specialization for std::pair template struct PatchIdMapWrapper > { typedef typename boost::property_traits::category category; typedef Int value_type; typedef typename boost::property_traits::reference reference; typedef typename boost::property_traits::key_type key_type; PatchIdMap map; int offset; PatchIdMapWrapper(PatchIdMap map, int offset) : map(map), offset(offset){} }; template typename PatchIdMapWrapper >::value_type get(PatchIdMapWrapper >& map, Handle_type h) { return Int(get(map.map, h).first - map.offset); } template void put(PatchIdMapWrapper >& map, Handle_type h, typename PatchIdMapWrapper >::value_type pid) { put(map.map, h, std::pair(Int(pid+map.offset), 0)); } template typename boost::graph_traits::faces_size_type detect_surface_patches(PolygonMesh& p, PatchIdMap patch_id_map, EdgeIsFeatureMap eif, const NamedParameters& np) { int offset = static_cast( parameters::choose_parameter(parameters::get_parameter(np, internal_np::first_index), 1)); internal::PatchIdMapWrapper::value_type> wrapmap(patch_id_map, offset); return connected_components(p, wrapmap, parameters::edge_is_constrained_map(eif) .face_index_map(CGAL::get_initialized_face_index_map(p, np))); } template typename boost::graph_traits::faces_size_type detect_surface_patches(PolygonMesh& p, PatchIdMap patch_id_map, EdgeIsFeatureMap eif) { return detect_surface_patches(p, patch_id_map, eif, parameters::all_default()); } template void sharp_call(PolygonMesh& pmesh, FT angle_in_deg, EIFMap edge_is_feature_map, VNFEMap vnfe) { // Initialize vertices for(typename boost::graph_traits::vertex_descriptor vd : vertices(pmesh)) { put(vnfe, vd, 0); } FT cos_angle ( std::cos(CGAL::to_double(angle_in_deg) * CGAL_PI / 180.) ); // Detect sharp edges for(typename boost::graph_traits::edge_descriptor ed : edges(pmesh)) { typename boost::graph_traits::halfedge_descriptor he = halfedge(ed,pmesh); if(is_border_edge(he,pmesh) || angle_in_deg == FT() || (angle_in_deg != FT(180) && internal::is_sharp(pmesh,he,cos_angle)) ) { put(edge_is_feature_map, edge(he, pmesh), true); put(vnfe, target(he,pmesh), get(vnfe, target(he,pmesh))+1); put(vnfe, source(he,pmesh), get(vnfe, source(he,pmesh))+1); } } } template void sharp_call(PolygonMesh& pmesh, FT& angle_in_deg, EIFMap edge_is_feature_map, const internal_np::Param_not_found&) { typedef typename boost::graph_traits::edge_descriptor edge_descriptor; typedef typename boost::graph_traits::halfedge_descriptor halfedge_descriptor; FT cos_angle ( std::cos(CGAL::to_double(angle_in_deg) * CGAL_PI / 180.) ); // Detect sharp edges for(edge_descriptor ed : edges(pmesh)) { halfedge_descriptor he = halfedge(ed,pmesh); if(is_border_edge(he,pmesh) || angle_in_deg == FT() || (angle_in_deg != FT(180) && internal::is_sharp(pmesh,he,cos_angle)) ) { put(edge_is_feature_map, edge(he, pmesh), true); } } } } //end internal /*! * \ingroup PMP_detect_features_grp * * detects and marks the edges that are considered to be sharp with respect to the given angle bound. * `angle_in_deg` gives the maximum angle (in degrees) between the two normal vectors of adjacent triangles. * For an edge of the input polygon mesh, if the angle between the two normal vectors of its incident facets is bigger * than the given bound, then the edge is marked as being a feature edge. * * Also computes the number of sharp edges incident to each vertex, if `vertex_feature_degree_map` is provided. * * \tparam PolygonMesh a model of `HalfedgeListGraph` * \tparam FT a number type. It is * either deduced from the `geom_traits` \ref bgl_namedparameters "Named Parameters" if provided, * or from the geometric traits class deduced from the point property map * of `PolygonMesh`. * \tparam EdgeIsFeatureMap a model of `ReadWritePropertyMap` with `boost::graph_traits::%edge_descriptor` * as key type and `bool` as value type. It must be default constructible. * \tparam NamedParameters a sequence of \ref bgl_namedparameters "Named Parameters" * * \param pmesh the polygon mesh * \param angle_in_deg the dihedral angle bound * \param edge_is_feature_map the property map that will contain the sharp-or-not status of each edge of `pmesh` * \param np an optional sequence of \ref bgl_namedparameters "Named Parameters" among the ones listed below * * \cgalNamedParamsBegin * \cgalParamNBegin{vertex_feature_degree_map} * \cgalParamDescription{a property map that will associate to each vertex of `pmesh` the number of incident feature edges} * \cgalParamType{a class model of `ReadWritePropertyMap` with `boost::graph_traits::%vertex_descriptor` as key type and `int` as value type} * \cgalParamDefault{`boost::get(CGAL::vertex_feature_degree_t(), pmesh)`} * \cgalParamNEnd * * \cgalParamNBegin{geom_traits} * \cgalParamDescription{an instance of a geometric traits class} * \cgalParamType{a class model of `Kernel`} * \cgalParamDefault{a \cgal Kernel deduced from the point type, using `CGAL::Kernel_traits`} * \cgalParamExtra{The geometric traits class must be compatible with the vertex point type.} * \cgalParamNEnd * \cgalNamedParamsEnd * */ #ifdef DOXYGEN_RUNNING template #else template #endif void detect_sharp_edges(PolygonMesh& pmesh, #ifdef DOXYGEN_RUNNING FT angle_in_deg, #else typename GetGeomTraits::type::FT angle_in_deg, #endif EdgeIsFeatureMap edge_is_feature_map, const NamedParameters& np) { //extract types from NPs typedef typename GetGeomTraits::type GT; typedef typename GT::FT FT; internal::sharp_call(pmesh, angle_in_deg, edge_is_feature_map, parameters::get_parameter(np, internal_np::vertex_feature_degree)); } /*! * \ingroup PMP_detect_features_grp * * collects the surface patches of the faces incident to each vertex of the input polygon mesh. * * \tparam PolygonMesh a model of `HalfedgeListGraph` * \tparam PatchIdMap a model of `ReadablePropertyMap` with `boost::graph_traits::%face_descriptor` as key type and the desired patch id, model of `CopyConstructible` as value type. * \tparam VertexIncidentPatchesMap a model of mutable `LvaluePropertyMap` with `boost::graph_traits::%vertex_descriptor` as key type. Its value type must be a container of `boost::property_traits::%value_type` and have a function `insert()`. A `std::set` or a `boost::unordered_set` are recommended, as a patch index may be inserted several times. * \tparam EdgeIsFeatureMap a model of `ReadablePropertyMap` with `boost::graph_traits::%edge_descriptor` * as key type and `bool` as value type. * * \param pmesh the polygon mesh * \param patch_id_map the property map containing the surface patch ids for the faces of `pmesh`. It must be already filled. * \param vertex_incident_patches_map a property map that will contain the patch ids of all the faces incident to each vertex of `pmesh`. * \param edge_is_feature_map a filled property map that will contain the sharp-or-not status of each edge of `pmesh` * * @see `CGAL::Polygon_mesh_processing::sharp_edges_segmentation()` */ template void detect_vertex_incident_patches(PolygonMesh& pmesh, const PatchIdMap patch_id_map, VertexIncidentPatchesMap vertex_incident_patches_map, const EdgeIsFeatureMap edge_is_feature_map) { typedef typename boost::graph_traits::vertex_descriptor vertex_descriptor; typedef typename boost::graph_traits::halfedge_descriptor halfedge_descriptor; for(vertex_descriptor vit :vertices(pmesh)) { // Look only at feature vertices if( ! get(edge_is_feature_map, edge(halfedge(vit, pmesh), pmesh) )) { continue; } // Loop on incident facets of vit typename VertexIncidentPatchesMap::value_type& id_set = vertex_incident_patches_map[vit]; for(halfedge_descriptor he : halfedges_around_target(vit,pmesh)) { if( ! is_border(he,pmesh) ) { id_set.insert(get(patch_id_map, face(he, pmesh))); } else if( ! is_border(opposite(he,pmesh),pmesh) ) { id_set.insert(get(patch_id_map, face(opposite(he, pmesh), pmesh))); } } } } namespace internal { template void vip_call(PolygonMesh& mesh, PIDMap pid, VIPMap vip, EIFMap eif ) { CGAL::Polygon_mesh_processing::detect_vertex_incident_patches(mesh, pid, vip, eif); } template void vip_call(PolygonMesh&, PIDMap, const internal_np::Param_not_found&, EIFMap) { //do nothing when the parameter is not given } }//end internal /*! * \ingroup PMP_detect_features_grp * * This function calls successively `CGAL::Polygon_mesh_processing::detect_sharp_edges()`, * `CGAL::Polygon_mesh_processing::connected_components()` and * `CGAL::Polygon_mesh_processing::detect_vertex_incident_patches()` * * It detects and marks the sharp edges of `pmesh` according to `angle_in_deg`. * The sharp edges define a segmentation of `pmesh`, that is done by * computing a * surface patch id for each face. * * \tparam PolygonMesh a model of `FaceGraph` * \tparam FT a number type. It is * either deduced from the `geom_traits` \ref bgl_namedparameters "Named Parameters" if provided, * or from the geometric traits class deduced from the point property map * of `PolygonMesh`. * \tparam EdgeIsFeatureMap a model of `ReadWritePropertyMap` with `boost::graph_traits::%edge_descriptor` * \tparam PatchIdMap a model of `ReadWritePropertyMap` with `boost::graph_traits::%face_descriptor` as key type and the desired patch id, model of `CopyConstructible` as value type. * \tparam NamedParameters a sequence of \ref bgl_namedparameters "Named Parameters" * * \param pmesh the polygon mesh * \param angle_in_deg the dihedral angle bound * \param edge_is_feature_map the property map that will contain the sharp-or-not status of each edge of `pmesh` * \param patch_id_map the property map that will contain the surface patch ids for the faces of `pmesh`. * \param np an optional sequence of \ref bgl_namedparameters "Named Parameters" among the ones listed below * * \cgalNamedParamsBegin * \cgalParamNBegin{vertex_feature_degree_map} * \cgalParamDescription{a property map that will associate to each vertex of `pmesh` the number of incident feature edges} * \cgalParamType{a class model of `ReadWritePropertyMap` with `boost::graph_traits::%vertex_descriptor` * as key type and `int` as value type} * \cgalParamDefault{`boost::get(CGAL::vertex_feature_degree_t(), pmesh)`} * \cgalParamNEnd * * \cgalParamNBegin{first_index} * \cgalParamDescription{the index of the first surface patch of `pmesh`} * \cgalParamType{`std::size_t`} * \cgalParamExtra{The patches will be numbered on `[first_index; first_index + num_patches]`, * where `num_patches` is the number of surface patches.} * \cgalParamNEnd * * \cgalParamNBegin{face_index_map} * \cgalParamDescription{a property map associating to each face of `pmesh` a unique index between `0` and `num_faces(pmesh) - 1`} * \cgalParamType{a class model of `ReadablePropertyMap` with `boost::graph_traits::%face_descriptor` * as key type and `std::size_t` as value type} * \cgalParamDefault{an automatically indexed internal map} * \cgalParamNEnd * * \cgalParamNBegin{vertex_incident_patches_map} * \cgalParamDescription{a property map that will contain the patch ids of all the faces incident to each vertex of `pmesh`} * \cgalParamType{a model of mutable `LvaluePropertyMap` with * `boost::graph_traits::%vertex_descriptor` as key type. Its value type * must be a container of `boost::property_traits::%value_type` and have a function `insert()`.} * \cgalParamExtra{A `std::set` or a `boost::unordered_set` are recommended, as a patch index may be inserted several times.} * \cgalParamNEnd * * \cgalParamNBegin{geom_traits} * \cgalParamDescription{an instance of a geometric traits class} * \cgalParamType{a class model of `Kernel`} * \cgalParamDefault{a \cgal Kernel deduced from the point type, using `CGAL::Kernel_traits`} * \cgalParamExtra{The geometric traits class must be compatible with the vertex point type.} * \cgalParamNEnd * \cgalNamedParamsEnd * \returns the number of surface patches. * * @see `CGAL::Polygon_mesh_processing::detect_sharp_edges()` * @see `CGAL::Polygon_mesh_processing::connected_components()` * @see `CGAL::Polygon_mesh_processing::detect_vertex_incident_patches()` */ #ifdef DOXYGEN_RUNNING template #else template #endif typename boost::graph_traits::faces_size_type sharp_edges_segmentation(PolygonMesh& pmesh, #ifdef DOXYGEN_RUNNING FT angle_in_deg, #else typename GetGeomTraits::type::FT angle_in_deg, #endif EdgeIsFeatureMap edge_is_feature_map, PatchIdMap patch_id_map, const NamedParameters& np) { detect_sharp_edges(pmesh, angle_in_deg, edge_is_feature_map, np); typename boost::graph_traits::faces_size_type result = internal::detect_surface_patches(pmesh, patch_id_map, edge_is_feature_map, np); internal::vip_call(pmesh, patch_id_map, parameters::get_parameter(np, internal_np::vertex_incident_patches), edge_is_feature_map); return result; } //Convenient overrides template void detect_sharp_edges(PolygonMesh& p, FT angle_in_deg, EdgeIsFeatureMap edge_is_feature_map) { detect_sharp_edges(p, angle_in_deg, edge_is_feature_map, parameters::all_default()); } template typename boost::graph_traits::faces_size_type sharp_edges_segmentation(PolygonMesh& p, FT angle_in_deg, EdgeIsFeatureMap edge_is_feature_map, PatchIdMap patch_id_map) { return sharp_edges_segmentation(p, angle_in_deg, edge_is_feature_map, patch_id_map, parameters::all_default()); } } // end namespace PMP } // end namespace CGAL #include #endif // CGAL_POLYGON_MESH_PROCESSING_DETECT_FEATURES_IN_POLYGON_MESH_H