记录最近遇到的一个问题和解决方案。

        最近遇到的问题：将一个五边形划分为四边形网格。

        参考文献《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 polymeshPolyMeshType 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);}}}