openmesh - impl - Remove Duplicated Vertices
关于openmesh元素删除实现的介绍参见：openmesh - src - trimesh delete and add elements - grassofsky - 博客园 (cnblogs.com)
重复点删除的主要步骤如下：
- 找到所有的重复顶点，并设定每组重复顶点中需要保留的顶点；
- 记录这些重复顶点对应的三角形；（因为下一步在顶点删除的时候，会将顶点周围关联的三角形都删除，并将顶点的状态设置为deleted）；
- 删除所有的重复的顶点；（此时会删除关联的三角形和半边）；
- 可能出现孤立点，删除孤立点；（此步骤可选）；
- 回收，边和面的资源；（此步骤为了后续添加关联面做准备）；
- 遍历所有的重复顶点关联的三角形，如果这个三角形中仅含有一个重复点，那么添加该三角形，并将重复点替换为对应的保留的点；
- 恢复重新添加的保留的顶点的删除状态；
- 资源回收；
具体实现代码如下：
#include <iostream>
#include <OpenMesh/Core/Mesh/TriMesh_ArrayKernelT.hh>
#include <OpenMesh/Tools/Utils/Timer.hh>
#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "doctest.h"
using namespace OpenMesh;
struct MyTraits : public OpenMesh::DefaultTraits
{
#if 1
typedef OpenMesh::Vec3f Point;
typedef OpenMesh::Vec3f Normal;
#else
typedef OpenMesh::Vec3d Point;
typedef OpenMesh::Vec3d Normal;
#endif
};
typedef OpenMesh::TriMesh_ArrayKernelT<MyTraits> TriMesh;
//-----------------------------------------------------------------------------
bool HasDuplicatedVertex(const TriMesh& mesh)
{
std::map<TriMesh::Point, int> mapPoints;
for (auto iter = mesh.vertices_begin(); iter != mesh.vertices_end(); ++iter)
{
auto iterPt = mapPoints.find(mesh.point(*iter));
if (iterPt == mapPoints.end())
{
mapPoints.insert_or_assign(mesh.point(*iter), 1);
}
else
{
return true;
}
}
return false;
}
int RemoveDuplicatedVertex(TriMesh& mesh)
{
// Find all duplicated vertices
int iOriginalNumVertices = static_cast<int>(mesh.n_vertices());
std::map<TriMesh::Point, TriMesh::VertexHandle> mapPoints;
std::map<TriMesh::VertexHandle, std::set<TriMesh::VertexHandle>> mapDuplicatedVertices;
for (auto iter = mesh.vertices_begin(); iter != mesh.vertices_end(); ++iter)
{
auto& pt = mesh.point(*iter);
if (mapPoints.find(pt) != mapPoints.end())
{
auto& vh = mapPoints[pt];
auto iterDuplicatedVertices = mapDuplicatedVertices.find(vh);
if (iterDuplicatedVertices == mapDuplicatedVertices.end())
{
mapDuplicatedVertices.insert(std::make_pair(vh, std::set<TriMesh::VertexHandle>{ vh, *iter }));
}
else
{
iterDuplicatedVertices->second.insert(*iter);
}
}
else
{
mapPoints.insert(std::make_pair(pt, *iter));
}
}
// Record the duplicated vertices related faces
std::map<TriMesh::VertexHandle, std::set<std::array<TriMesh::VertexHandle, 3>>> mapVertexFaces;
for (auto iter = mapDuplicatedVertices.begin(); iter != mapDuplicatedVertices.end(); ++iter)
{
auto pair = mapVertexFaces.insert(std::make_pair(iter->first, std::set<std::array<TriMesh::VertexHandle, 3>>{}));
auto& vecFaces = pair.first->second;
for (auto v_it = iter->second.begin(); v_it != iter->second.end(); ++v_it)
{
for (auto vf_it = mesh.vf_iter(*v_it); vf_it.is_valid(); ++vf_it)
{
std::array<TriMesh::VertexHandle, 3> face;
int i = 0;
auto fv_it = mesh.fv_begin(*vf_it);
face[i++] = *(fv_it++);
face[i++] = *(fv_it++);
face[i++] = *(fv_it++);
vecFaces.insert(face);
}
}
}
if (!mesh.has_vertex_status()) mesh.request_vertex_status();
if (!mesh.has_face_status()) mesh.request_face_status();
if (!mesh.has_edge_status()) mesh.request_edge_status();
// remove all duplicated vertices
for (auto iter = mapDuplicatedVertices.begin(); iter != mapDuplicatedVertices.end(); ++iter)
{
for (auto v_it = iter->second.begin(); v_it != iter->second.end(); ++v_it)
{
mesh.delete_vertex(*v_it);
}
}
mesh.delete_isolated_vertices();
// garbage_collection edge and face
mesh.garbage_collection(false, true, true);
// add not degenereated faces
std::set<TriMesh::VertexHandle> setRemainVertices;
for (auto iter = mapVertexFaces.begin(); iter != mapVertexFaces.end(); ++iter)
{
for (auto f_it = iter->second.begin(); f_it != iter->second.end(); ++f_it)
{
std::array<TriMesh::VertexHandle, 3> face = *f_it;
unsigned short result = 0;
for (auto iter = mapDuplicatedVertices.begin(); iter != mapDuplicatedVertices.end(); ++iter)
{
// bit pos records if the vertex is duplicated vertex or not
result = 0;
result |= (iter->second.count(face[0]) == 0 ? 0 : 1);
result |= (iter->second.count(face[1]) == 0 ? 0 : 2);
result |= (iter->second.count(face[2]) == 0 ? 0 : 4);
if (result == 1 || result == 2 || result == 4)
{
// replace the duplicated vertex as remaining vertex
face[result / 2] = iter->first;
mesh.add_face(face[0], face[1], face[2]);
setRemainVertices.insert(face[0]);
setRemainVertices.insert(face[1]);
setRemainVertices.insert(face[2]);
break;
}
}
}
}
// recover status of remain vertex
for (auto v_it = setRemainVertices.begin(); v_it != setRemainVertices.end(); ++v_it)
{
mesh.status(*v_it).set_deleted(false);
}
// garbage_collection vertex
mesh.garbage_collection();
if (!mesh.has_vertex_status()) mesh.release_vertex_status();
if (!mesh.has_face_status()) mesh.release_vertex_status();
if (!mesh.has_edge_status()) mesh.release_vertex_status();
return iOriginalNumVertices - static_cast<int>(mesh.n_vertices());
}
//-----------------------------------------------------------------------------
TEST_CASE("testing delete duplicated vertex")
{
TriMesh mesh;
// Add some vertices
TriMesh::VertexHandle vhandle[7];
vhandle[0] = mesh.add_vertex(TriMesh::Point(0, 0, 0));
vhandle[1] = mesh.add_vertex(TriMesh::Point(0, 2, 0));
vhandle[2] = mesh.add_vertex(TriMesh::Point(2, 2, 0));
vhandle[3] = mesh.add_vertex(TriMesh::Point(2, 0, 0));
vhandle[4] = mesh.add_vertex(TriMesh::Point(1, 1, 0));
vhandle[5] = mesh.add_vertex(TriMesh::Point(1, 1, 0));
vhandle[6] = mesh.add_vertex(TriMesh::Point(1, 1, 0));
// Add faces
mesh.add_face(vhandle[0], vhandle[1], vhandle[4]);
mesh.add_face(vhandle[0], vhandle[4], vhandle[6]);
mesh.add_face(vhandle[0], vhandle[6], vhandle[3]);
mesh.add_face(vhandle[1], vhandle[5], vhandle[4]);
mesh.add_face(vhandle[1], vhandle[2], vhandle[5]);
mesh.add_face(vhandle[2], vhandle[6], vhandle[5]);
mesh.add_face(vhandle[2], vhandle[3], vhandle[6]);
mesh.add_face(vhandle[4], vhandle[5], vhandle[6]);
auto iNDeleted = RemoveDuplicatedVertex(mesh);
CHECK(iNDeleted == 2);
CHECK(mesh.n_faces() == 4);
CHECK(mesh.n_vertices() == 5);
CHECK_FALSE(HasDuplicatedVertex(mesh));
}