How to push faces?

[jirihon]

Hi, I'm trying to implement an algorithm for pushing a face of a manifold in the direction of its normal. I would like to kindly ask you for your opinion whether I'm heading in the right direction or for ideas how to make it more realiable.

Vocabulary:

• Face: set of connected coplanar triangles extracted using Manifold::GetMeshRelation.
• Border edge: edge that connects two different faces.

Input:

• Manifold polyhedron where each vertex connects exactly 3 border edges.
• Signed distances for all faces.

Output:

• Manifold polyhedron with the faces pushed by the corresponding distances

Algorithm:

1. Go through all faces and calculate displacement of vertexes. The vertex displacement vector has the direction of the border edge that comes from the vertex but is not a border edge of the face. The size of the displacement vector depends on the face normal and the signed distance: size = distance / cos(displ_to_normal_angle). Up to 3 faces might additively contribute to the displacement of a single vertex.
2. Using the displacement vectors, calculate new 3D polygons that define the moved faces.
3. Project the 3D polygons in 2D and use Triangulate.
4. Create a manifold from all triangles.

I'm aware that bad thing can happen. For example, if the border edge that drives the direction of the displacement is too short, the result will be useless. What I'm afraid of is that I might end up with extra faces (almost coplanar) due to rounding errors. That would make problems with additional face pushing later in the workflow.

What do you think? Is it good approach or should I go for another solution?

[elalish]

As long as you keep track of the parent face of each triangle (akin to what MeshRelation does), then you should be fine. As soon as you try to guess based on coplanarity (geometry), that's dangerous. Manifold already does this coplanarity check for you on input, so just use its result (as reported in MeshRelation) and don't check coplanarity again.

Considering you're already restricted on not collapsing edges, I'd avoid retriangulation entirely. You should be able to look up the 3 unique faces by checking the triangles involved. Going back and forth from triangles to polygons is also dangerous (and slow) and should be avoided when possible.

[jirihon]

Thank you very much for your advice. From my experiments I see I can't avoid retriangulation. There are cases where pushing the face will dramatically change the shape of the neighbouring face, so a retriangulation is needed. Especially when the neighbouring face is not convex polygon. I'll use the rounding-error-free axis-aligned projection (GetAxisAlignedProjection) for projecting 3D polygons for triangulation and will see if it works reliably.

[jirihon]

Could I please have another question related to this topic? As I'm working towards "push faces" functionality, I've implemented the following constructor which can make a manifold from a set of 3D polygons, which is great. However, it has one serious drawback. The vertex indices are changed in the output manifold and therefore I'm not able to track the relation between the input 3D polygons and the faces reported by getMeshRelation function called on the resulting manifold.

Is it somehow possible to get the information on how the vertices were reordered during manifold initialization without comparing the coordinates of input and output vertices?

Manifold Manifold::Polyhedron(
    const std::vector<glm::vec3> vertPos,
    const std::vector<std::vector<std::vector<int>>>& polygonsVec,
    const std::vector<glm::vec3> normals) {
  auto pImpl_ = std::make_shared<Impl>();
  auto& _vertPos = pImpl_->vertPos_;
  VecDH<glm::ivec3> triVertsDH;
  auto& triVerts = triVertsDH;

  for (auto& vert : vertPos) {
    _vertPos.push_back(vert);
  }
  for (int i = 0; i < polygonsVec.size(); i++) {
    auto& polygons = polygonsVec[i];
    auto& normal = normals[i];

    const glm::mat3x2 projection = GetAxisAlignedProjection(normal);
    auto polygons2d = To2DPolygon(polygons, projection, _vertPos);

    auto tris = Triangulate(polygons2d);
    for (auto& tri : tris) {
      triVerts.push_back({tri[0], tri[1], tri[2]});
    }
  }
  pImpl_->CreateHalfedges(triVertsDH);
  pImpl_->Finish();
  pImpl_->InitializeNewReference();
  return Manifold(pImpl_);
}

[jirihon]

I see BaryRef.tri and already using it to extract coplanar triangles, but I don't know how could I use it to match the input faces with the output faces. The set of triangles in the input might be quite different from the output. I'm first extracting face polygons from the input, then applying displacement vectors on the vertices to calculate new polygons that define the pushed faces. These polygons are then used as input for the Polyhedron function, which does retriangulation. I think I'm still missing something.

[elalish]

Definitely the whole point of the mesh relation is to match output triangles to input faces. Could you post the code you're trying to use for mapping? Maybe I can spot the problem there.

[jirihon]

I think my problem is, that the Polyhedron function constructs the manifold from scratch. Therefore there is no useful information in MeshRelation for me to map the input polygons to the output faces/triangles.

const new_vert_pos: Vec3[];
const face_normals: Vec3[];
const face_polygons: number[][][];

// Code that calculates the values of new_vert_pos, face_normals and face_polygons based on input manifold

const pushed_solid = manifold.polyhedron(new_vert_pos, face_polygons, face_normals); // call the Polyhedron C++ function
const mesh = pushed_solid.getMesh();

// Now, how to find out, which triangles from mesh.triVerts belongs to which polygons from face_polygons?

[elalish]

Oh, sure. This is why I said to make a function outside of the library. If we start from your Polyhedron function a few comments up, just also return a std::vector<int> tri2face and fill it with the i value in your loop for each tri. Then you'll get int face = tri2face[meshRelation.triBary[outputTri].tri];

[jirihon]

Oh, thank you very much! Now I think I get it. This is possible, because the input and output triangles have the same index. I wish I didn't waste much of your time.

Here is the code I'm using with the addition you suggested. Hopefully, it will also help other people using manifold.

std::vector<SimplePolygon> To2DPolygon(
    const std::vector<std::vector<int>>& polygons, const glm::mat3x2 projection,
    const std::vector<glm::vec3>& vertPos) {
  std::vector<SimplePolygon> simplePolygons(polygons.size());

  for (int i = 0; i < polygons.size(); i++) {
    std::vector<PolyVert> vertices(polygons[i].size());
    for (int j = 0; j < polygons[i].size(); j++) {
      const int vert_i = polygons[i][j];
      auto& vert = vertPos[vert_i];
      vertices[j] = {projection * vert, vert_i};
    }
    simplePolygons[i] = {vertices};
  }
  return simplePolygons;
}

struct PolyhedronOutput {
  Manifold manifold;
  std::vector<int> tri_face;
};

PolyhedronOutput Polyhedron(
    const std::vector<glm::vec3> vertPos,
    const std::vector<std::vector<std::vector<int>>>& polygonsVec,
    const std::vector<glm::vec3> normals) {
  Mesh mesh;
  mesh.vertPos = vertPos;
  std::vector<int> tri_face;

  for (int i = 0; i < polygonsVec.size(); i++) {
    auto& polygons = polygonsVec[i];
    auto& normal = normals[i];

    const glm::mat3x2 projection = GetAxisAlignedProjection(normal);
    auto polygons2d = To2DPolygon(polygons, projection, vertPos);

    auto tris = Triangulate(polygons2d);
    for (auto& tri : tris) {
      mesh.triVerts.push_back({tri[0], tri[1], tri[2]});
      tri_face.push_back(i);
    }
  }
  return {Manifold(mesh), tri_face};
}