四边形网格处理——沿Edge遍历 矩形域顶点提取
记录最近遇到的一个问题和解决方案。
最近遇到的问题：将一个五边形划分为四边形网格。
参考文献《Closed -form Quadrangulation of n-Sided Patches》，划分方式如下图所示，实际上是在五边形中间添加了一个顶点，顶点分别向五边形的5条边各引出一条分割线，将五边形划分成了5个四边形区域，再将5个四边形区域分成更细小的四边形网格。
假如划分后的整体四边形网格已得到，如何得到分割的5块四边形区域网格，并将其顶点按照矩形域的形式（形如N行M列）排好呢？此问题可整理为：
输入： quadMesh -- 四边形网格；
corners -- 五边形5个角点的vid；
sides -- 各条边（side）的vid集合；
mpoint -- 中间的分界点；上图中的红点；
输出：
patchMesh -- mpoint分割出来的5个四边形区域的顶点，顶点整理成N*M的形式
大致思路：
1. 遍历mpoint邻接的所有四边形；
2. 对每一个四边形，找到与mpoint邻接的两个Edge；
3. 分别沿这两条Edge向边的方向遍历，直到抵达五边形边界；
四边形网格沿Edge遍历的大致思路，Edge首尾点分别为a,b，首先分别找到a，b邻接的所有面，取b邻接面的所有与b邻接的顶点，从这些顶点中再筛选出不属于a的邻接面的顶点，即沿Edge遍历的下一个顶点。
4. 固定一条EdgeA为矩形域首行点，另一条EdgeB为矩形域首列点；那么矩形域顶点的行数为EdgeB的顶点数，矩形域顶点的列数为EdgeA的顶点数。
5. 从第2行开始，根据前一行顶点位置，和当前行第一个顶点的位置，查找并填充当前行的所有顶点，直到所有行顶点填充完毕。
这里需要实现已知面的三个顶点ID，搜索该面ID及余下一顶点的ID。搜索面ID的时候，从三个顶点的邻接面中搜索即可。
代码使用C++\vcglib实现。
代码基于quadwild-bimdf项目修改（GitHub - cgg-bern/quadwild-bimdf: QuadWild extended with BiMDF solver）。五边形mpoint的编号固定为3。
//Get polymesh
PolyMeshType quadrangulatedChartMesh;
QuadRetopology::internal::eigenToVCG(quadrangulationV, quadrangulationF, quadrangulatedChartMesh, 4);
vcg::tri::UpdateTopology<PolyMeshType>::FaceFace(quadrangulatedChartMesh);
vcg::tri::UpdateTopology<PolyMeshType>::VertexFace(quadrangulatedChartMesh);
vcg::tri::UpdateFlags<PolyMeshType>::VertexBorderFromFaceAdj(quadrangulatedChartMesh);
auto getSideId = [&](int vid) {
for (int i = 0; i < patchSides.size(); i++)
{
for (int j = 0; j < patchSides[i].size(); j++)
{
if (patchSides[i][j] == vid)
return i;
}
}
return -1;
};
auto getCornerId = [&](int vid) {
for (int i = 0; i < patchCorners.size(); i++)
{
if (patchCorners[i] == vid)
return i;
}
return -1;
};
auto isEdgeInFace = [&](int vid1, int vid2, int fid) {
auto* f = &quadrangulatedChartMesh.face[fid];
for (int i = 0; i < f->VN(); i++)
{
auto a = vcg::tri::Index(quadrangulatedChartMesh, f->V(i));
auto b = vcg::tri::Index(quadrangulatedChartMesh, f->V((i + 1) % f->VN()));
if (a == vid1 && b == vid2)
return true;
if (a == vid2 && b == vid1)
return true;
}
return false;
};
// 在fid所在面中找到vid的两个相邻顶点
auto findNeighborVertex = [&](int vid, int fid) {
auto* f = &quadrangulatedChartMesh.face[fid];
for (int i = 0; i < f->VN(); i++)
{
auto iv = vcg::tri::Index(quadrangulatedChartMesh, f->V(i));
if (iv == vid)
{
auto a = vcg::tri::Index(quadrangulatedChartMesh, f->V((i - 1 + f->VN()) % f->VN()));
auto b = vcg::tri::Index(quadrangulatedChartMesh, f->V((i + 1) % f->VN()));
return std::make_pair(a, b);
}
}
};
auto rf = quadrangulatedChartMesh.face[0];
auto findNextVF = [&](int last_vid, int cur_vid, int last_fid) {
auto v_cur = &quadrangulatedChartMesh.vert[cur_vid];
auto v_last = &quadrangulatedChartMesh.vert[last_vid];
std::vector<decltype(rf)*> faceVec_cur;
std::vector<int> index_cur;
vcg::face::VFStarVF(v_cur, faceVec_cur, index_cur); // 获取所有与顶点相邻的面
std::vector<decltype(rf)*> faceVec_last;
std::vector<int> index_last;
vcg::face::VFStarVF(v_last, faceVec_last, index_last); // 获取所有与顶点相邻的面
int curr_dir = 0;
for (unsigned int i = 0; i < faceVec_cur.size(); i++)
{
decltype(rf)* curr_f = faceVec_cur[i]; // 当前面
auto curr_f_id = vcg::tri::Index(quadrangulatedChartMesh, curr_f);
if (curr_f_id == last_fid)
{
continue;
}
auto pairv = findNeighborVertex(cur_vid, curr_f_id);
bool findAdjFace = false;
for (unsigned int j = 0; j < faceVec_last.size(); j++)
{
decltype(rf)* tmpf = faceVec_last[j]; // 当前面
auto tmpf_id = vcg::tri::Index(quadrangulatedChartMesh, tmpf);
if (isEdgeInFace(pairv.first, cur_vid, tmpf_id))
{
findAdjFace = true;
break;
}
}
if (!findAdjFace)
return std::make_pair((int)pairv.first, (int)curr_f_id);
findAdjFace = false;
for (unsigned int j = 0; j < faceVec_last.size(); j++)
{
decltype(rf)* tmpf = faceVec_last[j]; // 当前面
auto tmpf_id = vcg::tri::Index(quadrangulatedChartMesh, tmpf);
if (isEdgeInFace(pairv.second, cur_vid, tmpf_id))
{
findAdjFace = true;
break;
}
}
if (!findAdjFace)
return std::make_pair((int)pairv.second, (int)curr_f_id);
}
return std::make_pair(-1, -1);
};
// 3个点的顺序要与实际一致，中间不能有断开的点
auto findFaceAndLastV = [&](int v[3])
{
for (int i = 0; i < 3; i++)
{
std::vector<decltype(rf)*> faceVec;
std::vector<int> index;
vcg::face::VFStarVF(&quadrangulatedChartMesh.vert[v[i]], faceVec, index); // 获取所有与顶点相邻的面
for (int j = 0; j < faceVec.size(); j++)
{
auto f = faceVec[j];
for (int k = 0; k < 4; k++)
{
auto v1 = vcg::tri::Index(quadrangulatedChartMesh, f->V(k));
auto v2 = vcg::tri::Index(quadrangulatedChartMesh, f->V((k + 1) % 4));
auto v3 = vcg::tri::Index(quadrangulatedChartMesh, f->V((k + 2) % 4));
if ((v1 == v[0] && v2 == v[1] && v3 == v[2]) || (v1 == v[2] && v2 == v[1] && v3 == v[0]))
return std::make_pair(index[j], (int)vcg::tri::Index(quadrangulatedChartMesh, f->V((k + 3) % 4)));
}
}
}
return std::make_pair(-1, -1);
};
auto findPathToSide = [&](int mpoint_vid, int next_vid, int fid, int& sideId)
{
std::vector<int> subPatchV;
subPatchV.push_back(mpoint_vid);
subPatchV.push_back(next_vid);
auto lastVid = mpoint_vid;
sideId = -1;
bool mpoint_on_board = (getSideId(mpoint_vid) >= 0);
if (mpoint_on_board)
{
sideId = getSideId(mpoint_vid);
}
do {
auto ret = findNextVF(lastVid, next_vid, fid);
if (ret.first == -1)
break;
lastVid = next_vid;
fid = ret.second;
next_vid = ret.first;
subPatchV.push_back(next_vid);
sideId = getSideId(next_vid);
} while ((sideId < 0 && (!mpoint_on_board)) || (mpoint_on_board && getCornerId(next_vid) < 0));
return subPatchV;
};
//vcg::tri::UpdateEdges<PolyMeshType>::UpdateEdge(quadrangulatedChartMesh);
if (chart.chartSides.size() == 5)
{
auto* mpoint = &quadrangulatedChartMesh.vert[3];
std::vector<decltype(rf)*> faceVec;
std::vector<int> index;
vcg::face::VFStarVF(mpoint, faceVec, index); // 获取所有与顶点相邻的面
for (unsigned int i = 0; i < faceVec.size(); i++)
{
auto lastVid = vcg::tri::Index(quadrangulatedChartMesh, mpoint);
decltype(rf)* f = faceVec[i];
auto curFid = vcg::tri::Index(quadrangulatedChartMesh, f);
auto neighborV = findNeighborVertex(lastVid, curFid);
int side_U = -1, side_V;
std::vector<int> u_verts = findPathToSide(lastVid, neighborV.first, curFid, side_U);
std::vector<int> v_verts = findPathToSide(lastVid, neighborV.second, curFid, side_V);
std::vector<std::vector<int>> subPatchsV;
subPatchsV.resize(v_verts.size());
subPatchsV[0] = u_verts;
for (int j = 1; j < v_verts.size(); j++)
{
subPatchsV[j] = u_verts;
int vids[3] = { v_verts[j], subPatchsV[j - 1][0], subPatchsV[j - 1][1] };
auto f_v = findFaceAndLastV(vids);
int side = -1;
subPatchsV[j] = findPathToSide(v_verts[j], f_v.second, f_v.first, side);
}
}
}