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.