Efficiency issues about CGAL::Face_filtered_graph classes.

[fynkxo]

Issue Details

Efficiency issues about CGAL::Face_filtered_graph classes.

The code is as follows. The time statistics results are attached in the figure. From the results, we can see that the Face_filtered_graph construction took a huge amount of time.The same seems to be true in the class CGAL::copy face graph.

Source Code

for (decltype(NumberComponents)i = 0; i < NumberComponents; i++)
    {
        std::shared_ptr<boost::timer::auto_cpu_timer> t{new boost::timer::auto_cpu_timer()};
        std::cout << "Construct: \n";
        CGAL::Face_filtered_graph<Mesh> subMesh{mesh,i,fccmap};
                t.reset(new boost::timer::auto_cpu_timer);
                std::cout << "Calculate:\n";
        double volumeOrigin = PMP::volume(subMesh);
        double volume = std::abs(volumeOrigin);

            double x1 = INFINITY, x2 = -INFINITY;
            double y1 = INFINITY, y2 = -INFINITY;
            double z1 = INFINITY, z2 = -INFINITY;
            auto iter = CGAL::vertices(subMesh);
            while (iter.first != iter.second)
            {
                ++iter.first;
                K::Point_3 v = mesh.point(*iter.first);
                double x = v.x();
                double y = v.y();
                double z = v.z();
                x1 = std::min(x1, x);
                x2 = std::max(x2, x);
                y1 = std::min(y1, y);
                y2 = std::max(y2, y);
                z1 = std::min(z1, z);
                z2 = std::max(z2, z);
            }

            volumes.push_back(volume);
            volumesOrigin.push_back(volumeOrigin);
            bboxes.push_back(CGAL::Bbox_3(x1, y1, z1, x2, y2, z2));
    }

Environment

• Operating system (Windows64 bits):
• Compiler: Visual Studio 2022
• Release or debug mode: Release
• Specific flags used (if any):
• CGAL version: 5.6.1
• Boost version: 1.84
• Other libraries versions if used (Eigen, TBB, etc.):

Refer to drawing:

[sloriot]

The time alone are not really meaningful. Indeed if the mesh is made of several millions of vertices, the timing would be perfectly fine I guess. Could you please share a complete example we can compile and run to reproduce the runtime that seem too long to you?

[fynkxo]

• The Face_filtered_graph class provides the set_selected_faces member function as follows:

  /// changes the set of selected faces using a range of patch ids
  template<class FacePatchIDRange, class FacePatchIDMap>
  void set_selected_faces(const FacePatchIDRange& selected_face_patch_ids,
                        FacePatchIDMap face_patch_id_map
  #ifndef DOXYGEN_RUNNING
                        , std::enable_if_t<
                            boost::has_range_const_iterator<FacePatchIDRange>::value
                          >* = 0
  #endif
                        )
  {
  selected_faces.resize(num_faces(_graph));
  selected_vertices.resize(num_vertices(_graph));
  selected_halfedges.resize(num_halfedges(_graph));
  
  selected_faces.reset();
  selected_vertices.reset();
  selected_halfedges.reset();
  
  typedef typename boost::property_traits<FacePatchIDMap>::value_type Patch_ID;
  std::unordered_set<Patch_ID> pids(std::begin(selected_face_patch_ids),
                                    std::end(selected_face_patch_ids));
  
  for(face_descriptor fd : faces(_graph))
  {
    if(pids.count(get(face_patch_id_map, fd)) != 0)
    {
      selected_faces.set(get(fimap, fd));
      for(halfedge_descriptor hd : halfedges_around_face(halfedge(fd, _graph), _graph))
      {
        selected_halfedges.set(get(himap, hd));
        selected_halfedges.set(get(himap, opposite(hd, _graph)));
        selected_vertices.set(get(vimap, target(hd, _graph)));
      }
    }
  }
  
  reset_indices();
  }

  We can see that each Face_filtered_graph construction requires a complete traversal of all the faces once, which is unfavorable for the huge number of faces to be built multiple times. Whether to consider a method to support the construction of multiple Face_filtered_graph classes in a single traversal.

• The class Face filtered graph is as follows:

  private:
  Graph& _graph;
  FIM fimap;
  VIM vimap;
  HIM himap;
  boost::dynamic_bitset<> selected_faces;
  boost::dynamic_bitset<> selected_vertices;
  boost::dynamic_bitset<> selected_halfedges;
  
  mutable std::vector<face_index_type> face_indices;
  mutable std::vector<vertex_index_type> vertex_indices;
  mutable std::vector<halfedge_index_type> halfedge_indices;
  mutable std::bitset<3> is_imap_in_use; // one per descriptor type (face, vertex, halfedge)
  };

  We can see that the indices of the faces, points, and half-edges are stored in the dense array, and we do a simple calculation: Suppose there are 8 million faces (assuming the same number of half-edges and vertices)，100 Face_filtered_graph objects are build at the same time.$4byte 3 8000000 * 100 ≈ 8.94Gb$ Whether to consider providing a version of the sparse array or a configurable array by template parameter.