API tools faq
paste
Advertisement
Mysakure

Untitled

Mysakure
Oct 20th, 2021
1,141
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.63 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!