Cut holes in mesh

[mariuszhermansdorfer]

First of all, a huge thanks for creating this fantastic library!

I've been experimenting with GC inside of Rhino to work with modelling terrains. One thing I'm struggling with is cutting holes in the mesh. Consider this basic example:

Initial mesh:

Faces to remove:

Resulting mesh with a hole inside:

I tried several approaches:

1. Omit the interior faces while constructing a new mesh:
   

   geometry-central/src/surface/manifold_surface_mesh.cpp

   Line 48 in ebe4029

   ManifoldSurfaceMesh::ManifoldSurfaceMesh(const std::vector<std::vector<size_t>>& polygons) : SurfaceMesh(true) {

This fails here:

geometry-central/src/surface/manifold_surface_mesh.cpp

Lines 154 to 161 in ebe4029

	std::vector<char> vertexOnBoundary(nVerticesCount, false);
	for (size_t iHe = 0; iHe < nHalfedgesCount; iHe++) {
	if (heNextArr[iHe] == INVALID_IND) {
	size_t v = heVertexArr[iHe];
	GC_SAFETY_ASSERT(!vertexOnBoundary[v],
	"vertex " + std::to_string(v) + " appears in more than one boundary loop");
	vertexOnBoundary[v] = true;
	}

2. Pass the edges defining the interior boundary to the SeparateEdge function
   

   geometry-central/src/surface/manifold_surface_mesh.cpp

   Line 671 in ebe4029

   std::tuple<Halfedge, Halfedge> ManifoldSurfaceMesh::separateEdge(Edge e) {

Which fails here;

geometry-central/src/surface/manifold_surface_mesh.cpp

Lines 808 to 814 in ebe4029

	// === Case 4: both vertices are same boundaries
	// need to split off disconnected compoent of surface
	// TODO implement
	if (vAIsBoundary && vBIsBoundary && boundaryLoopA == boundaryLoopB) {
	throw std::runtime_error("not implemented: separateEdge() creating disconnected components");
	return std::tuple<Halfedge, Halfedge>{Halfedge(), Halfedge()};
	}

Is there a straight-forward way to define an edge loop as a boundary?
@nmwsharp, @MarkGillespie, @keenancrane

[mariuszhermansdorfer]

Progress update:

It is stated in the comments that input polygons need to be dense. This means that naively omitting selected faces will obviously not work.

geometry-central/src/surface/manifold_surface_mesh.cpp

Lines 48 to 50 in ebe4029

	ManifoldSurfaceMesh::ManifoldSurfaceMesh(const std::vector<std::vector<size_t>>& polygons) : SurfaceMesh(true) {
	// Assumes that the input index set is dense. This sometimes isn't true of (eg) obj files floating around the
	// internet, so consider removing unused vertices first when reading from foreign sources.

A workaround I found is to first construct a SimplePolygonMesh, compress it and then create a ManifoldSurfaceMesh

  SimplePolygonMesh simpleMesh(meshFaces, vertexPositions);
  simpleMesh.stripUnusedVertices();
  auto lvals = makeManifoldSurfaceMeshAndGeometry(simpleMesh.polygons, simpleMesh.vertexCoordinates);

This works, but is relatively slow for larger meshes and recreating all connectivity from scratch on each mutation definitely feels heavy-handed.

I'd still like to understand how to correctly delete faces from an existing mesh. I found the following description in the docs:

Deleted halfedges and their edges are implicitly encoded by heNext[he] == INVALID_IND, while deleted edges and vertices are encoded by vHalfedge[v] == INVALID_IND and fHalfedge[f] == INVALID_IND.

Does deleting a face mean setting all the core arrays to INVALID_IND for all halfedges describing this face?

  std::vector<size_t> heNextArr;    // he.next(), forms a circular singly-linked list in each face
  std::vector<size_t> heVertexArr;  // he.vertex()
  std::vector<size_t> heFaceArr;    // he.face()
  std::vector<size_t> vHalfedgeArr; // v.halfedge()
  std::vector<size_t> fHalfedgeArr; // f.halfedge()

[HarryRos]

+1 for a feature request.