Mysakure

Untitled

Oct 20th, 2021
848
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<Eigen\Dense>
  3. #include<vector>
  4. #include"model.hpp"
  5. #include<set>
  6. #include<ctime>
  7. #include<map>
  8. #include"cross.hpp"
  9. using namespace std;
  10.  
  11. const int maxn = 1e5 + 10;
  12. int in[maxn];
  13. bool checkColision() {
  14.  
  15.     return false;
  16. }
  17.  
  18. auto cmpVector2i = [](const Eigen::Vector2i a, const Eigen::Vector2i b) {
  19.     return a.x() < b.x();
  20. };
  21. map<Eigen::Vector2i, int, decltype(cmpVector2i)>edgeId(cmpVector2i);
  22. int ID = 0;
  23. vector<set<int>>edge2faces;
  24.  
  25. bool judge(double a, double b, double c, double d) {
  26.     if (a > b)swap(a, b);
  27.     if (c > d)swap(c, d);
  28.  
  29.     if (a <= c && b >= c)return true;
  30.     if (a <= d && b >= d)return true;
  31.     if (a >= c && b <= d)return true;
  32.     return false;
  33. }
  34. template<class cmp1,class cmp2>
  35. bool CrossCheckY(Eigen::Vector2i v,set<Eigen::Vector2i,cmp1>& SortedEdgeYbyFirstVert, set<Eigen::Vector2i,cmp2>& SortedEdgeYbyEndVert,const vector<Eigen::Vector3d>& verts, const vector<Eigen::Vector3i>&faces) {
  36.     int stVert = v.x(), edVert = v.y();
  37.     auto stY = SortedEdgeYbyFirstVert.lower_bound(Eigen::Vector2i(edVert, edVert));
  38.  
  39.     //cerr << "check st" << '\n';
  40.     if (stY != SortedEdgeYbyFirstVert.begin()) {
  41.         --stY;
  42.         while (stY != SortedEdgeYbyFirstVert.begin() && verts[stY->x()].y() >= verts[stVert].y()) {
  43.             //crossCheck(Eigen::Vector2i(vert,nxtVert),*stY);
  44.             int ida = edgeId[Eigen::Vector2i(min(stVert, edVert), max(stVert, edVert))];
  45.             int idb = edgeId[Eigen::Vector2i(min(stY->x(), stY->y()), max(stY->x(), stY->y()))];
  46.             /*if (judge(verts[stVert].z(), verts[edVert].z(), verts[stY->x()].z(), verts[stY->y()].z()) == 0)
  47.             {
  48.                 cerr << "cross " << '\n';
  49.                 cout << verts[stVert].z() << " " << verts[edVert].z() << '\n';
  50.                 cout << verts[stY->x()].z() << " " << verts[stY->y()].z() << '\n';
  51.             }*/
  52.             //for (int i = 0; i < edge2faces[ida].size(); ++i) {
  53.             //  for (int j = 0; j < edge2faces[idb].size(); ++j) {
  54.             //      if (ida != idb) {
  55.             //          /*float va[3][3] = { {verts[faces[ida].x()].x(),verts[faces[ida].x()].y(),verts[faces[ida].x()].y()},\
  56.             //              {verts[faces[ida].y()].x(), verts[faces[ida].y()].y(), verts[faces[ida].y()].y()},
  57.             //              { verts[faces[ida].z()].x(),verts[faces[ida].z()].y(),verts[faces[ida].z()].y() } };
  58.             //          float vb[3][3] = { {verts[faces[idb].x()].x(),verts[faces[idb].x()].y(),verts[faces[idb].x()].y()},\
  59.             //              {verts[faces[idb].y()].x(), verts[faces[idb].y()].y(), verts[faces[idb].y()].y()},
  60.             //              { verts[faces[idb].z()].x(),verts[faces[idb].z()].y(),verts[faces[idb].z()].y() } };
  61.             //          Triangle a(va), b(vb);*/
  62.             //          //if (judge_triangle_topologicalStructure(&a, &b)== INTERSECT) {
  63.             //          //  /*cerr << " cross " << '\n';
  64.             //          //  cerr << verts[stVert].z() << '\n';
  65.             //          //  cerr << verts[edVert].z() << '\n';
  66.  
  67.             //          //  cerr << verts[stY->x()].z() << '\n';
  68.             //          //  cerr << verts[stY->y()].z() << '\n';*/
  69.             //          //  /*cerr << faces[ida].x() + 1 << " " << faces[ida].y() + 1 << " " << faces[ida].z() + 1 << '\n';
  70.             //          //  cerr << faces[idb].x() + 1 << " " << faces[idb].y() + 1 << " " << faces[idb].z() + 1 << '\n';*/
  71.             //          //}
  72.             //      }
  73.             //  }
  74.             //}
  75.            
  76.             --stY;
  77.         }
  78.     }
  79.  
  80.     auto edY = SortedEdgeYbyFirstVert.lower_bound(Eigen::Vector2i(stVert, stVert));
  81.     while (edY != SortedEdgeYbyFirstVert.end() && verts[stY->y()].y() <= verts[edVert].y()) {
  82.         //crossCheck(Eigen::Vector2i(vert, nxtVert), *edY);
  83.         int ida = edgeId[Eigen::Vector2i(min(stVert, edVert), max(stVert, edVert))];
  84.         int idb = edgeId[Eigen::Vector2i(min(edY->x(), edY->y()), max(edY->x(), edY->y()))];
  85.         /*if (judge(verts[stVert].z(), verts[edVert].z(), verts[edY->x()].z(), verts[edY->y()].z()) == 0)
  86.         {
  87.             cerr << "cross " << '\n';
  88.             cout << verts[stVert].z() << " " << verts[edVert].z() << '\n';
  89.             cout << verts[edY->x()].z() << " " << verts[edY->y()].z() << '\n';
  90.         }*/
  91.         //for (int i = 0; i < edge2faces[ida].size(); ++i) {
  92.         //  for (int j = 0; j < edge2faces[idb].size(); ++j) {
  93.         //      if (ida != idb) {
  94.         //          /*float va[3][3] = { {verts[faces[ida].x()].x(),verts[faces[ida].x()].y(),verts[faces[ida].x()].y()},\
  95.         //              {verts[faces[ida].y()].x(), verts[faces[ida].y()].y(), verts[faces[ida].y()].y()},
  96.         //              { verts[faces[ida].z()].x(),verts[faces[ida].z()].y(),verts[faces[ida].z()].y() } };
  97.         //          float vb[3][3] = { {verts[faces[idb].x()].x(),verts[faces[idb].x()].y(),verts[faces[idb].x()].y()},\
  98.         //              {verts[faces[idb].y()].x(), verts[faces[idb].y()].y(), verts[faces[idb].y()].y()},
  99.         //              { verts[faces[idb].z()].x(),verts[faces[idb].z()].y(),verts[faces[idb].z()].y() } };
  100.         //          Triangle a(va), b(vb);*/
  101.         //          //if (judge_triangle_topologicalStructure(&a, &b) == INTERSECT) {
  102.         //          //  /*cerr << " cross " << '\n';
  103.         //          //  cerr << verts[stVert].z() << '\n';
  104.         //          //  cerr << verts[edVert].z() << '\n';
  105.  
  106.         //          //  cerr << verts[edY->x()].z() << '\n';
  107.         //          //  cerr << verts[edY->y()].z() << '\n';*/
  108.         //          //  /*cerr << faces[ida].x()+1<<" "<< faces[ida].y()+1<<" "<< faces[ida].z()+1 << '\n';
  109.         //          //  cerr << faces[idb].x()+1 << " " << faces[idb].y()+1 << " " << faces[idb].z()+1 << '\n';*/
  110.         //          // 
  111.         //          //}
  112.         //      }
  113.         //  }
  114.         //}
  115.         ++edY;
  116.     }
  117.     //cerr << "check end" << '\n';
  118.     return false;
  119. }
  120. int main() {
  121.     Model model;
  122.     time_t begin, end;
  123.  
  124.     model.ReadObjFile("C:\\Users\\admin\\Desktop\\model\\trumpet2.obj");
  125.     vector<Eigen::Vector3d> verts = model.GetVertices();
  126.     vector<Eigen::Vector3i> faces = model.GetFaces();
  127.    
  128.     vector<set<int>>nxtVerts(verts.size(), set<int>());
  129.     vector<set<int>>preVerts(verts.size(), set<int>());
  130.  
  131.     begin = clock();
  132.  
  133.     for (int pos = 0;pos<faces.size();++pos) {
  134.         auto face = faces[pos];
  135.         if (verts[face.x()].z() > verts[face.y()].z()||(verts[face.x()].z() == verts[face.y()].z())&&face.x()<face.y())
  136.         {
  137.             nxtVerts[face.x()].insert(face.y());
  138.             preVerts[face.y()].insert(face.x());
  139.             in[face.y()] = 1;
  140.         }
  141.         else {
  142.             nxtVerts[face.y()].insert(face.x());
  143.             preVerts[face.x()].insert(face.y());
  144.             in[face.x()] = 1;
  145.         }
  146.         if (edgeId.count(Eigen::Vector2i(min(face.x(), face.y()), max(face.x(), face.y())))) {
  147.             edge2faces[edgeId[Eigen::Vector2i(min(face.x(), face.y()), max(face.x(), face.y()))]].insert(pos);
  148.         }
  149.         else {
  150.             edgeId[Eigen::Vector2i(min(face.x(), face.y()), max(face.x(), face.y()))] = ID;
  151.             edge2faces.push_back(set<int>());
  152.             edge2faces[ID].insert(pos);
  153.             ++ID;
  154.         }
  155.  
  156.         if (verts[face.x()].z() > verts[face.z()].z() || (verts[face.x()].z() == verts[face.z()].z()) && face.x() < face.z())
  157.         {
  158.             nxtVerts[face.x()].insert(face.z());
  159.             preVerts[face.z()].insert(face.x());
  160.             in[face.z()] = 1;
  161.         }
  162.         else {
  163.             nxtVerts[face.z()].insert(face.x());
  164.             preVerts[face.x()].insert(face.z());
  165.             in[face.x()] = 1;
  166.         }
  167.         if (edgeId.count(Eigen::Vector2i(min(face.x(), face.z()), max(face.x(), face.z())))) {
  168.             edge2faces[edgeId[Eigen::Vector2i(min(face.x(), face.z()), max(face.x(), face.z()))]].insert(pos);
  169.         }
  170.         else {
  171.             edgeId[Eigen::Vector2i(min(face.x(), face.z()), max(face.x(), face.z()))] = ID;
  172.             edge2faces.push_back(set<int>());
  173.             edge2faces[ID].insert(pos);
  174.             ++ID;
  175.         }
  176.  
  177.         if (verts[face.z()].z() > verts[face.y()].z() || (verts[face.z()].z() == verts[face.y()].z()) && face.z() < face.y())
  178.         {
  179.             nxtVerts[face.z()].insert(face.y());
  180.             preVerts[face.y()].insert(face.z());
  181.             in[face.y()] = 1;
  182.         }
  183.         else {
  184.             nxtVerts[face.y()].insert(face.z());
  185.             preVerts[face.z()].insert(face.y());
  186.             in[face.z()] = 1;
  187.         }
  188.         if (edgeId.count(Eigen::Vector2i(min(face.z(), face.y()), max(face.z(), face.y())))) {
  189.             edge2faces[edgeId[Eigen::Vector2i(min(face.z(), face.y()), max(face.z(), face.y()))]].insert(pos);
  190.         }
  191.         else {
  192.             edgeId[Eigen::Vector2i(min(face.z(), face.y()), max(face.z(), face.y()))] = ID;
  193.             edge2faces.push_back(set<int>());
  194.             edge2faces[ID].insert(pos);
  195.             ++ID;
  196.         }
  197.     }
  198.     cerr << "size " << verts.size() << " " << faces.size() << '\n';
  199.  
  200.     //利用x和y交叉进行检查
  201.     //存储当前准备扫描的边,将每条边的起点和终点的坐标记录下来,做比较函数,利用y值进行比较
  202.     auto cmpEdgeYbyFirstVert = [&verts](const Eigen::Vector2i edgea, const Eigen::Vector2i edgeb) {
  203.         return verts[edgea.x()].y() < verts[edgeb.x()].y();
  204.     };
  205.     //正在扫描的边和所有的点,将所有正在扫描的边组合在一起产生的数据结构
  206.     set<Eigen::Vector2i,decltype(cmpEdgeYbyFirstVert)>SortedEdgeYbyFirstVert(cmpEdgeYbyFirstVert);
  207.  
  208.     auto cmpEdgeYbyEndVert = [&verts](const Eigen::Vector2i edgea, const Eigen::Vector2i edgeb) {
  209.         return verts[edgea.y()].y() < verts[edgeb.y()].y();
  210.     };
  211.     set<Eigen::Vector2i, decltype(cmpEdgeYbyEndVert)>SortedEdgeYbyEndVert(cmpEdgeYbyEndVert);
  212.  
  213.     set<Eigen::Vector2i, decltype(cmpEdgeYbyEndVert)>allEdge(cmpEdgeYbyEndVert);
  214.     /*auto cmpEdgeX = [&verts](const Eigen::Vector2i edgea, const Eigen::Vector2i edgeb) {
  215.         return min(verts[edgea.x()].x(), verts[edgea.y()].x()) < \
  216.             min(verts[edgeb.x()].x(), verts[edgeb.y()].x());
  217.     };
  218.     set<Eigen::Vector2i, decltype(cmpEdgeX)>SortedEdgeX(cmpEdgeX);*/
  219.  
  220.    
  221.     //如果存在离散的点或者多个分开的数据结构的时候,所以需要单独建立一个点的数据结构,在不能利用边含入进来的时候
  222.     //利用点的高度继续构建
  223.     auto cmpVertZ = [&verts](const int verta, const int vertb) {
  224.         return verts[verta].z() > verts[vertb].z();
  225.     };
  226.     set<int,decltype(cmpVertZ)>RemainVerts(cmpVertZ);
  227.     //当前正在扫描中的点
  228.     set<int,decltype(cmpVertZ)>CurVerts(cmpVertZ);
  229.     for (int i = 0; i<int(verts.size()); ++i) {
  230.         RemainVerts.insert(i);
  231.     }
  232.     int out = 0;
  233.     while (!RemainVerts.empty() || !CurVerts.empty()) {
  234.         //删除掉旧的边会产生新的边
  235.         //在插入新的边的时候再判断这条边有没有和已有的边产生交叉
  236.         //如果CurVerts是空的
  237.         if (CurVerts.empty()||(!RemainVerts.empty()&&verts[*CurVerts.begin()].z()<verts[*RemainVerts.begin()].z())) {
  238.             int vert = *RemainVerts.begin();
  239.             //CurVerts.insert(vert);
  240.             RemainVerts.erase(vert);
  241.             for (auto nxtVert : nxtVerts[vert]) {
  242.                
  243.                 CurVerts.insert(nxtVert);
  244.                 RemainVerts.erase(nxtVert);
  245.  
  246.                 int stVert = (verts[nxtVert].y() < verts[vert].y() ? nxtVert : vert);
  247.                 int edVert = (stVert == vert ? nxtVert : vert);
  248.                 CrossCheckY(Eigen::Vector2i(stVert, edVert), SortedEdgeYbyFirstVert, SortedEdgeYbyEndVert, verts,faces);
  249.                
  250.                 SortedEdgeYbyFirstVert.insert(Eigen::Vector2i(stVert, edVert));
  251.                 SortedEdgeYbyEndVert.insert(Eigen::Vector2i(stVert, edVert));
  252.                 allEdge.insert(Eigen::Vector2i(stVert, edVert));
  253.                 //cerr << "end 1 "<<nxtVert << '\n';
  254.             }
  255.             //cerr << "end 2" << '\n';
  256.         }
  257.         else {
  258.             //cerr << "start 2" << '\n';
  259.             cerr << ++out << '\n';
  260.  
  261.             int vert = *CurVerts.begin();
  262.             //cerr << vert<< '\n';
  263.             CurVerts.erase(vert);
  264.  
  265.             for (auto preVert : preVerts[vert]) {
  266.                 int stVert = (verts[vert].y() < verts[preVert].y() ? vert : preVert);
  267.                 int edVert = (vert == stVert ? preVert : vert);
  268.                 if (!allEdge.count(Eigen::Vector2i(stVert, edVert))) {
  269.                     cerr << "error " << endl;
  270.                 }
  271.                 SortedEdgeYbyFirstVert.erase(Eigen::Vector2i(stVert, edVert));
  272.                 SortedEdgeYbyEndVert.erase(Eigen::Vector2i(stVert, edVert));
  273.             }
  274.  
  275.             for (auto nxtVert : nxtVerts[vert]) {
  276.                 //cerr << "nxt " << nxtVerts[vert].size() << endl;
  277.                 CurVerts.insert(nxtVert);
  278.                 RemainVerts.erase(nxtVert);
  279.                 int stVert = verts[nxtVert].y() < verts[vert].y() ? nxtVert : vert;
  280.                 int edVert = (stVert == vert ? nxtVert : vert);
  281.                 //CrossCheckY(Eigen::Vector2i(stVert, edVert), SortedEdgeYbyFirstVert, SortedEdgeYbyEndVert, verts,faces);
  282.                
  283.                 SortedEdgeYbyFirstVert.insert(Eigen::Vector2i(stVert, edVert));
  284.                 SortedEdgeYbyEndVert.insert(Eigen::Vector2i(stVert, edVert));
  285.                 allEdge.insert(Eigen::Vector2i(stVert, edVert));
  286.             }
  287.         }
  288.     }
  289.     end = clock();
  290.     std::cout << "runtime:   " << double(end - begin) / CLOCKS_PER_SEC << endl;
  291.     return 0;
  292. }
RAW Paste Data