Correspondance between mesh before clipping and after splitting

[stla]

Hello,

I have a mesh mesh that I clip to a mesh clipper. Let's call cmesh the clipped mesh. My mesh has a colour associated to each of its faces, and I want to retrieve these colors in cmesh. If I correctly understand the splitting, each face of cmesh is either an unchanged face of mesh or a subface of a face of mesh, so what I want to do make sense.

Actually I managed to do it using an inefficient solution: for each face of cmesh, I take its centroid and I iterate over the faces of mesh to see in which original face this face belongs.

But then I discovered the corefinement visitors and this looks promising. For example, I tried to use these two visitor functions:

 void before_subface_creations(face_descriptor fsplit, const EMesh3 & tm) {
    *i = fsplit;
 }
 void after_subface_created(face_descriptor fnew, const EMesh3 & tm) {
    (*vmap).insert(std::make_pair(*i, fnew));  
 }

With these two visitor functions, I create a map from the splitted face descriptors to the new face descriptors. This didn't help me to solve my problem. The splitted face descriptors obtained in this way belong to mesh, so ok I have their color. In view of the large values of the new face descriptors, I guess that these are some face descriptors of the corefined mesh. That doesn't help.

The goal is to obtain what I was able to obtain with my inefficient method: for each face of cmesh, I want to know its original face in mesh. Is it possible with the refinement visitors?

[stla]

I found!!

There are two steps:

• with the visitors as above, I get a map from the indices of the new faces in the corefined mesh to the original indices in mesh
• with the optional parameter face_index_map of the PMP::clip function, I get a map from the face indices of the clipped mesh cmesh to the indices of the corefined mesh

Then it's easy to finish: for each face of cmesh, take its index in the corefined mesh given by the second map; if it is lower than the number of indices in the original mesh, then it has the color of the original face given by this index; if it is higher than the number of faces in the original mesh, that means it is a subface and you can get the index of its parent face in mesh by using the first map.

[stla]

After doing PMP::clip, there are some duplicated vertices on the border of the mesh. How to get rid of them? I tried PMP::merge_duplicated_vertices_in_boundary_cycles(mesh); but this had no effect.

[stla]

This is much more complicated when clipVolume = true. Here is the code to retrieve the original faces.

typedef std::map<face_descriptor, face_descriptor> MapBetweenFaces;

struct ClipVisitor : 
  public PMP::Corefinement::Default_visitor<EMesh3>
{
  void before_subface_creations(face_descriptor fsplit, const EMesh3 & tm) {
    *ofaceindex = fsplit;
    if(*is_tm) {
      size_t nf = tm.number_of_faces();
      if((*nfaces).size() >= 1 && nf < (*nfaces).back()) {
        *is_tm = false;
      } else {
        (*nfaces).push_back(nf);
      }
    }
  }
  void after_subface_created(face_descriptor fnew, const EMesh3 & tm) {
    if(*is_tm) {
      (*fmap_tm).insert(std::make_pair(fnew, *ofaceindex));
    } else {
      (*fmap_clipper).insert(std::make_pair(fnew, *ofaceindex));
    }
  }
  void after_face_copy(
    face_descriptor fsrc, const EMesh3 & tmsrc, 
    face_descriptor ftgt, const EMesh3 & tmtgt
  ) {
    (*ftargets).insert(std::make_pair(ftgt, fsrc));
  }
  
  ClipVisitor()
    : fmap_tm(new MapBetweenFaces()),
      fmap_clipper(new MapBetweenFaces()),
      ofaceindex(new face_descriptor()),
      nfaces(new std::vector<size_t>()),
      ftargets(new MapBetweenFaces()),
      is_tm(new bool(true))
  {}
  
  std::shared_ptr<MapBetweenFaces> fmap_tm;
  std::shared_ptr<MapBetweenFaces> fmap_clipper;
  std::shared_ptr<MapBetweenFaces> ftargets;
  std::shared_ptr<face_descriptor> ofaceindex;
  std::shared_ptr<std::vector<size_t>> nfaces;
  std::shared_ptr<bool> is_tm;
};

ClipVisitor vis;
std::size_t undetermined = 9999999;
Face_index_map fimap = 
  tm.add_property_map<face_descriptor, std::size_t>("f:i", undetermined).first;
std::size_t nfaces = tm.number_of_faces();

const bool clipping = PMP::clip(
  tm, clipper,
  PMP::parameters::clip_volume(true).visitor(vis).face_index_map(fimap),
  PMP::parameters::clip_volume(true).do_not_modify(false)
);

tm.collect_garbage();

MapBetweenFaces fmap_tm = *(vis.fmap_tm);
MapBetweenFaces fmap_clipper = *(vis.fmap_clipper);
MapBetweenFaces ftargets = *(vis.ftargets);
MapBetweenFaces zeros;
{
  int fdi = 0;
  for(auto it = ftargets.rbegin(); it != ftargets.rend(); ++it) {
    while(fimap[CGAL::SM_Face_index(fdi)] != undetermined) {
      fdi++;
    }
    zeros[CGAL::SM_Face_index(fdi++)] = it->first;
  }
}

std::map<face_descriptor, int> originalMesh;
MapBetweenFaces originalFace;

for(EMesh3::Face_index fi : tm.faces()) {
  std::size_t ifi = fimap[fi];
  face_descriptor fd = CGAL::SM_Face_index(ifi);
  if(fi != fd && ifi != undetermined) {
    originalMesh[fi] = 1;
    originalFace[fi] = fmap_tm[fd];
  } else if(ifi != undetermined) {
    originalMesh[fi] = 1;
    originalFace[fi] = ifi < nfaces ? fd : fmap_tm[fd];
  } else if(ifi == undetermined) {
    originalMesh[fi] = 2;
    originalFace[fi] = zeros[fi];
  } 
}

[stla]

there's something wrong here; I'm working on it

[stla]

Totally lost... I'm unable to retrieve the colors of the clipper. Help wanted!

[stla]

And here is an application: the intersection of three cylinders with different colors.

[stla]

I unmark the answer I accepted because it is wrong. I partially fixed it: I'm able to retrieve the original face of any face of the corefined clipped mesh, but I'm unable to retrieve the original face of a face of the corefined clipping mesh.

[sloriot]

I guess it has to do with the is_tm that looks fishy to me.

[stla]

Ah yes, but this is my old visitor, I changed that.

[stla]

Here is my new visitor. To identify the mesh with is_tm, I assign a property map "f:i" to the mesh to be clipped.

struct ClipVisitor : 
  public PMP::Corefinement::Default_visitor<EMesh3>
{
  void before_subface_creations(face_descriptor fsplit, const EMesh3 & tm) {
    *ofaceindex = fsplit;
  }

  void after_subface_created(face_descriptor fnew, const EMesh3 & tm) {
    if(*is_tm) {
      if(tm.property_map<face_descriptor, std::size_t>("f:i").second) {
        (*fmap_tm).insert(std::make_pair(fnew, *ofaceindex));
      } else {
        *is_tm = false;
        (*fmap_clipper).insert(std::make_pair(fnew, *ofaceindex));
      }
    } else {
      (*fmap_clipper).insert(std::make_pair(fnew, *ofaceindex));
    }
  }

  void after_face_copy(
    face_descriptor fsrc, const EMesh3 & tmsrc, 
    face_descriptor ftgt, const EMesh3 & tmtgt
  ) {
    (*ftargets).insert(std::make_pair(ftgt, fsrc));
  }
  
  ClipVisitor()
    : ofaceindex(new face_descriptor()),
      fmap_tm(new MapBetweenFaces()),
      fmap_clipper(new MapBetweenFaces()),
      ftargets(new MapBetweenFaces()),
      is_tm(new bool(true))
  {}
  
  std::shared_ptr<face_descriptor> ofaceindex;
  std::shared_ptr<MapBetweenFaces> fmap_tm;
  std::shared_ptr<MapBetweenFaces> fmap_clipper;
  std::shared_ptr<MapBetweenFaces> ftargets;
  std::shared_ptr<bool> is_tm;
};

[stla]

Then I do:

ClipVisitor vis;
std::size_t undetermined = 9999999;
Face_index_map fimap = 
  tm.add_property_map<face_descriptor, std::size_t>("f:i", undetermined).first;
std::size_t nfaces = tm.number_of_faces();

const bool clipping = PMP::clip(
  tm, clipper,
  PMP::parameters::clip_volume(true).visitor(vis).face_index_map(fimap),
  PMP::parameters::clip_volume(true).do_not_modify(false)
);

tm.collect_garbage();

Then in fimap I get the faces information for the clipped mesh. If the face comes from the clipping mesh, I get "undetermined" (9999999), which does not allow to retrieve the original face.

I tried to put another face_index_map parameter for the clipping mesh, but it doesn' provide any information, it is just 1, 2, 3, 4, ..... I don't understand the role of this parameter.

[sloriot]

I don't understand your code. Did you have a look at this example: https://github.com/CGAL/cgal/blob/master/Polygon_mesh_processing/examples/Polygon_mesh_processing/corefinement_mesh_union_with_attributes.cpp ? As far as I understand it should work also for what you want to achieve.

[stla]

Thanks for looking into this. I will more carefully look at this example.

My visitor creates three maps between face descriptors:

• fmap_tm: it maps a face of the corefined mesh (mesh) to be clipped to its original face before corefinement
• fmap_clipper: idem for the clipping mesh (clipper)
• ftargets: I don't remember :-(

Then I do (I don't put all the code, not sure this is more understandable :-/):

    MaybeFcolorMap fcolorMap_ = 
      copy_prop<face_descriptor, std::string>(mesh, "f:color");
    MaybeFcolorMap fcolorMap2_ = 
      copy_prop<face_descriptor, std::string>(clipper, "f:color");

    std::size_t nfaces = mesh.number_of_faces();
    std::size_t nfaces_clipper = clipper.number_of_faces();
    
    std::size_t undetermined = 9999999;

    ClipVisitor vis; 
    Face_index_map fimap = 
      mesh.add_property_map<face_descriptor, std::size_t>(
        "f:i", undetermined
      ).first;
    const bool doNotModify = !clipVolume;
    const bool clipping = PMP::clip(
      mesh, clipper,
      PMP::parameters::clip_volume(clipVolume)
        .visitor(vis).face_index_map(fimap),
      PMP::parameters::clip_volume(clipVolume).do_not_modify(doNotModify)
    );
    if(!clipping) {
      Rcpp::stop("Clipping has failed.");
    }

    mesh.collect_garbage();


    MapBetweenFaces fmap_tm      = *(vis.fmap_tm);
    MapBetweenFaces fmap_clipper = *(vis.fmap_clipper);
    MapBetweenFaces ftargets     = *(vis.ftargets);
    MapBetweenFaces zeros;
    std::map<face_descriptor, std::string> fcolorMap;
    std::map<face_descriptor, std::string> fcolorMap2;
    std::map<face_descriptor, std::string> fcolorMap_clipper;
    
    fcolorMap = fcolorMap_.first;
    fcolorMap2 = fcolorMap2_.first;

    {
      int fdi = 0;
      for(auto it = ftargets.begin(); it != ftargets.end(); ++it) {
        face_descriptor fd = it->second;
        if(std::size_t(fd) >= nfaces_clipper) {
          fd = fmap_clipper[fd];
        }
        fcolorMap_clipper[it->first] = fcolorMap2[fd];
        while(fimap[CGAL::SM_Face_index(fdi)] != undetermined) {
          fdi++;
        }
        zeros[CGAL::SM_Face_index(fdi++)] = it->first;
      }
    }

    Face_index_map whichPart = 
      mesh.add_property_map<face_descriptor, std::size_t>("f:which").first;

    Fcolors_map newfcolor;
    newfcolor = mesh.add_property_map<face_descriptor, std::string>(
      "f:color", ""
    ).first;

    for(EMesh3::Face_index fi : mesh.faces()) {
      std::size_t ifi = fimap[fi];
      face_descriptor fd = CGAL::SM_Face_index(ifi);
      if(ifi != undetermined) {
        whichPart[fi] = 0;
        newfcolor[fi] = ifi < nfaces ? fcolorMap[fd] : fcolorMap[fmap_tm[fd]]; 
      } else {
        whichPart[fi] = 1;
        newfcolor[fi] = fcolorMap_clipper[zeros[fi]];
      } 
    }

    mesh.remove_property_map(fimap);

    EMesh3 tmesh;
    {
      Filtered_graph ffg(mesh, 0, whichPart);
      MapBetweenFaceDescriptors f2fmap_;
      boost::associative_property_map<MapBetweenFaceDescriptors> f2fmap(f2fmap_);
      CGAL::copy_face_graph(
        ffg, tmesh, CGAL::parameters::face_to_face_map(f2fmap)
      );
      copy_property<ffg_face_descriptor, face_descriptor, std::string>(
        mesh, tmesh, f2fmap_, "f:color"
      );
    }

    EMesh3 tmesh2;
    {
      Filtered_graph ffg(mesh, 1, whichPart);
      MapBetweenFaceDescriptors f2fmap_;
      boost::associative_property_map<MapBetweenFaceDescriptors> f2fmap(f2fmap_);
      CGAL::copy_face_graph(
        ffg, tmesh2, CGAL::parameters::face_to_face_map(f2fmap)
      );
      copy_property<ffg_face_descriptor, face_descriptor, std::string>(
        mesh, tmesh2, f2fmap_, "f:color"
      );
    }

With this code, I obtain the mesh tmesh whose faces inherit the colors of the input mesh. But the tmesh2 faces are supposed to inherit the colors of the clipping mesh and that does not work.

[stla]

Well, I try to adapt the example. Now I do:

struct ClipVisitor : 
  public PMP::Corefinement::Default_visitor<EMesh3>
{
  void before_subface_creations(face_descriptor fsplit, EMesh3 & tm) {
    *color = properties[&tm][fsplit];
  }

  void after_subface_created(face_descriptor fnew, EMesh3 & tm) {
    properties[&tm][fnew] = *color;
    (*(fmap_mesh))[fnew] = *color;
  }

  void after_face_copy(
    face_descriptor fsrc, EMesh3 & tmsrc, 
    face_descriptor ftgt, EMesh3 & tmtgt
  ) {
    (*(fmap_mesh))[ftgt] = properties[&tmsrc][fsrc];
  }
  
  ClipVisitor()
    : color(new std::string("black")),
      fmap_mesh(new std::map<face_descriptor, std::string>())
  {
    properties.reserve(2);
  }
  
  boost::container::flat_map<const EMesh3*, std::map<face_descriptor, std::string>> properties;
  std::shared_ptr<std::string> color;
  std::shared_ptr<std::map<face_descriptor, std::string>> fmap_mesh;
};

    std::map<face_descriptor, std::string> fcolorMap = fcolorMap_.first; // mesh color map
    std::map<face_descriptor, std::string> fcolorMap2 = fcolorMap2_.first; // clipper color map
    ClipVisitor vis; 
    vis.properties[&mesh] = fcolorMap;
    vis.properties[&clipper] = fcolorMap2;

    size_t undetermined = 9999999;    
    Face_index_map fimap = 
      mesh.add_property_map<face_descriptor, std::size_t>(
        "f:i", undetermined
      ).first;

    const bool clipping = PMP::clip(
      mesh, clipper,
      PMP::parameters::clip_volume(true).visitor(vis).face_index_map(fimap),
      PMP::parameters::clip_volume(true).do_not_modify(false)
    );
    if(!clipping) {
      Rcpp::stop("Clipping has failed.");
    }

    mesh.collect_garbage();

    Fcolors_map newfcolor = mesh.add_property_map<face_descriptor, std::string>(
      "f:color", ""
    ).first;
    
    for(EMesh3::Face_index fi : mesh.faces()) {
      std::string col = (*(vis.fmap_mesh))[fi];
      if(col == "") {
        std::size_t ifi = fimap[fi];
        if(ifi == undetermined) {
          col = fcolorMap2[fi];
        } else {
          col = fcolorMap[fi];
        }
      }
      newfcolor[fi] = col;
    }

Then, when I clip two unicolor meshes, I get a perfect bicolor mesh. But when I clip two meshes with multiple colors, the colors are completely messy.

[stla]

Well, still spent two days on this problem and I now believe it's impossible.

The face_index_map parameter allows to retrieve the parent faces of the clipped mesh. But it takes a unique value for the clipper faces: the default value of this property map. And then it does not allow to retrieve the parent faces of the clipper faces.