如何检测和保存边缘顶点中的循环连通性（孔检测）？ [英] How to detect and save cyclic connectivity in edge vertices (hole detection)?

问题描述

感谢您抽出宝贵的时间阅读我的问题。

我正在研究检测三角形网格中的孔，并用新的三角形填充它们。我已经完成了一些部分，以获取边缘顶点的列表等。以下是产生孔的顶点/边缘，请看一下图像。

 （9，62）=>顶点＃9和62使边缘（左洞）
（66，9）=>顶点＃66和9使得边（左洞）
（70，66）=>顶点＃70和66使边缘（左洞）
（62，70）=>顶点＃62和70形成边缘（左洞）
 
（147，63）=>顶点147和63形成边缘（右孔）
（55，148）
（63，149）
（149，55）
（148，147）
  

我要做的第一件事是检查哪些顶点构成了一个循环（意味着检测到一个洞）

问题是要编写一种算法，检查给定图（顶点/边）是否包含多少个循环？然后保存到单独的集合中。

请给我写一些简单且优化的算法来解决此问题。

谢谢。

解决方案

1. 网格

   
   
   

   假设您的 STL 网格得到您需要将n 个三角形转换为索引格式。因此，提取所有三角形点并转换为两个单独的表。一个持有所有点，第二个持有每个三角形3个点的索引。假设您获得了 m 点和 n 三角形。

   
   
   

   您应该对点表（索引）进行排序，并使用二进制搜索将其从 O（nm）加快到 O（m.log（ n））。




2. _edge 结构 >

   
   
   

   创建一个结构，该结构保留网格的所有边缘。

     struct _edge 
    {
    int p0，p1; //使用的顶点索引
    int cnt; //边缘使用情况的计数
   }; 
     

   其中 p0< p1 。




3. 创建 _edge edge [] 表 O（n）

   
   
   

   应该是一个包含所有边的列表（ 3n ），以便循环穿过所有三角形，每个三角形增加3条边。设置为 cnt = 1 的计数，这是 O（n）。

   
   
   

   现在按 p0，p1 对列表进行排序，即 O（n.log（n）） 。之后，只需将其所有 cnt 相加并删除其中之一，即可将所有具有相同 p0，p1 的边合并在一起。如果编码正确，则为 O（n）。




4. 检测孔 >

   
   
   

   在常规 STL 中，每个边必须具有 cnt = 2 。如果 cnt = 1 ，则三角形不存在，您找到了孔。如果 cnt> 2 网格中出现几何错误。

   
   
   

   因此，删除所有带有 cnt> = 2 从您的 edge [] 表中，该表为 O（n） 。




5. 检测循环

   
   
   

   假设我们得到了<$ c edge [] 表中的$ c> k 条边。现在，为每个共享点的2条边创建一个三角形。

    对于（i = 0; i  for（j = i + 1 ; j< k; j ++）
    {
    if（（edge [i] .p0 == edge [j] .p0）||（edge [i] .p1 == edge [j]。 p0））add_triangle（edge [i] .p0，edge [i] .p1，edge [j] .p1）; 
    if（（edge [i] .p0 == edge [j] .p1）||（edge [i] .p1 == edge [j] .p1））add_triangle（edge [i] .p0， edge [i] .p1，edge [j] .p0）; 
   } 
     

   如果对内部循环使用二进制搜索，则将为 O（k.log（k））。另外，您应该避免添加重复的三角形并纠正它们的缠绕，因此，首先将三角形添加到单独的表中（或记住起始索引），然后删除重复的三角形（或者您可以直接在 add_triangle ）。

   
   
   

   要处理更大的孔，请不要忘记在 edge [] 表中添加新的边。您可以在处理完当前边缘后更新边缘，然后重复＃4 或在运行中合并更改。




[Edit1] C ++示例

最近我正在为此QA做一些STL编码：

• 
  
  

  黑线是线框和红色这些只是 edge []，pnt [] 数组的调试图以进行调试...

  
  
  

  甚至可以看到它甚至适用于比单个三角形大的孔：) ...

  
  

  thanks for taking the time to read my question.

  I am working on detecting holes in a triangular mesh and fill them with new triangles. I have done some of the parts that are, to get a list of edge vertices, etc. Following are the vertices/edges that make holes, please have a look at the image.

  (9, 62)         => vertex # 9  and 62 makes an edge (left hole)
  (66, 9)         => vertex # 66 and 9  makes an edge (left hole)
  (70, 66)        => vertex # 70 and 66 makes an edge (left hole)
  (62, 70)        => vertex # 62 and 70 makes an edge (left hole)
  
  (147, 63)       => vertex # 147 and 63 makes an edge (right hole)
  (55, 148)
  (63, 149)
  (149, 55)
  (148, 147)
  

  The first thing that I need to do is to check which vertices make a cycle (means a hole is detected), and then save in a separate set of cyclic vertices.

  The issue is to write such an algorithm that checks whether the given graph(vertices/edges) contains how many cycles? and then save into separate sets.

  Please write me some simple and optimized algorithm to solve this problem.

  Thank you.

  解决方案

  1. mesh

     Let assume your STL mesh got n triangles you need to convert it into indexed format. So extract all triangle points and convert to two separate tables. one holding all the points and second holding 3 indexes of points per each triangle. Let assume you got m points and n triangles.

     You should have the point table (index) sorted and using binary search to speed this up from O(n.m) to O(m.log(n)).

  2. _edge structure

     create structure that holds all the edges of your mesh. Something like:

     struct _edge
      {
      int p0,p1; // used vertexes index
      int cnt;   // count of edge usage
      };
     

     where p0<p1.

  3. create _edge edge[] table O(n)

     It should be a list holding all the edges (3n) so loop through all the triangles and add 3 edges per each. The count set to cnt=1 This is O(n).

     Now sort the list by p0,p1 which is O(n.log(n)). After that just join all the edges with the same p0,p1 by summing their cnt and deleting one of them. If coded right then this is O(n).

  4. detect hole

     In regular STL each edge must have cnt=2. If cnt=1 then triangle is missing and you found your hole. if cnt>2 you got geometric error in your mesh.

     So delete all edges with cnt>=2 from your edge[] table which is O(n).

  5. detect loops

     let assume we got k edges left in our edge[] table. Now for each 2 edges that are sharing a point create triangle. Something like:

     for (i=0;i<k;i++)
      for (j=i+1;j<k;j++)
       {
       if ((edge[i].p0==edge[j].p0)||(edge[i].p1==edge[j].p0)) add_triangle(edge[i].p0,edge[i].p1,edge[j].p1);
       if ((edge[i].p0==edge[j].p1)||(edge[i].p1==edge[j].p1)) add_triangle(edge[i].p0,edge[i].p1,edge[j].p0);
       }
     

     If you use binary search for the inner loop then this will be O(k.log(k)). Also you should avoid to add duplicate triangles and correct the winding of them so first add the triangles to separate table (or remember starting index) and then remove duplicates (or you can do it directly in add_triangle).

     Also to handle bigger holes do not forget to add new edges to your edge[] table. You can either update the edges after current edges are processed and repeat #4 or incorporate the changes on the run.

  [Edit1] C++ example

  recently I was doing some coding for STL for this QA:

  • Generating outside supporters into mesh for 3D printing

  So as I got all the infrastructure already coded I chose to give this a shot and here the result:

  struct STL3D_edge
      {
      int p0,p1,cnt,dir;
      STL3D_edge()    {}
      STL3D_edge(STL3D_edge& a) { *this=a; }
      ~STL3D_edge()   {}
      STL3D_edge* operator = (const STL3D_edge *a) { *this=*a; return this; }
      //STL3D_edge* operator = (const STL3D_edge &a) { ...copy... return this; }
      int operator == (const STL3D_edge &a) { return ((p0==a.p0)&&(p1==a.p1)); }
      int operator != (const STL3D_edge &a) { return ((p0!=a.p0)||(p1!=a.p1)); }
      void ld(int a,int b) { cnt=1; if (a<=b) { dir=0; p0=a; p1=b; } else { dir=1; p0=b; p1=a; }}
      };
  List<STL3D_edge> edge;
  List<float> pnt;
  void edge_draw()
      {
      int i; STL3D_edge *e;
      glBegin(GL_LINES);
      for (e=edge.dat,i=0;i<edge.num;i++,e++)
          {
          glVertex3fv(pnt.dat+e->p0);
          glVertex3fv(pnt.dat+e->p1);
          }
      glEnd();
      }
  void STL3D::holes()
      {
      //  https://stackoverflow.com/a/45541861/2521214
      int i,j,i0,i1,i2,j0,j1,j2;
      float q[3];
      _fac        *f,ff;
      STL3D_edge  *e,ee,*e0,*e1,*e2;
      ff.attr=31<<5;                          // patched triangles color/id
  
      // create some holes for testing
      if (fac.num<100) return;
      for (i=0;i<10;i++) fac.del(Random(fac.num));
  
      // compute edge table
      edge.allocate(fac.num*3); edge.num=0;
      for (f=fac.dat,i=0;i<fac.num;i++,f++)
          {
          // add/find points to/in pnt[]
          for (i0=-1,j=0;j<pnt.num;j+=3){ vectorf_sub(q,pnt.dat+j,f->p[0]); if (vectorf_len2(q)<1e-6) { i0=j; break; }} if (i0<0) { i0=pnt.num; for (j=0;j<3;j++) pnt.add(f->p[0][j]); }
          for (i1=-1,j=0;j<pnt.num;j+=3){ vectorf_sub(q,pnt.dat+j,f->p[1]); if (vectorf_len2(q)<1e-6) { i1=j; break; }} if (i1<0) { i1=pnt.num; for (j=0;j<3;j++) pnt.add(f->p[1][j]); }
          for (i2=-1,j=0;j<pnt.num;j+=3){ vectorf_sub(q,pnt.dat+j,f->p[2]); if (vectorf_len2(q)<1e-6) { i2=j; break; }} if (i2<0) { i2=pnt.num; for (j=0;j<3;j++) pnt.add(f->p[2][j]); }
          // add edges
          ee.ld(i0,i1); for (e=edge.dat,j=0;j<edge.num;j++,e++) if (*e==ee) { e->cnt++; j=-1; break; } if (j>=0) edge.add(ee);
          ee.ld(i1,i2); for (e=edge.dat,j=0;j<edge.num;j++,e++) if (*e==ee) { e->cnt++; j=-1; break; } if (j>=0) edge.add(ee);
          ee.ld(i2,i0); for (e=edge.dat,j=0;j<edge.num;j++,e++) if (*e==ee) { e->cnt++; j=-1; break; } if (j>=0) edge.add(ee);
          }
  
      // delete even times used edges (to speed up the loops finding)
      for (i0=i1=0,e0=e1=edge.dat;i0<edge.num;i0++,e0++)
       if (int(e0->cnt&1)==1) { *e1=*e0; i1++; e1++; } edge.num=i1;
      // find 2 edges with one comon point (j1)
      for (e0=edge.dat,i0=0;i0<edge.num;i0++,e0++) if (int(e0->cnt&1)==1)
       for (e1=e0+1,i1=i0+1;i1<edge.num;i1++,e1++) if (int(e1->cnt&1)==1)
          {
          // decide which points to use
          j0=-1; j1=-1; j2=-1;
          if (e0->p0==e1->p0) { j0=e0->p1; j1=e0->p0; j2=e1->p1; }
          if (e0->p0==e1->p1) { j0=e0->p1; j1=e0->p0; j2=e1->p0; }
          if (e0->p1==e1->p0) { j0=e0->p0; j1=e0->p1; j2=e1->p1; }
          if (e0->p1==e1->p1) { j0=e0->p0; j1=e0->p1; j2=e1->p0; }
          if (j2<0) continue;
          // add missin triangle
          if (e0->dir)
              {
              vectorf_copy(ff.p[0],pnt.dat+j1);
              vectorf_copy(ff.p[1],pnt.dat+j0);
              vectorf_copy(ff.p[2],pnt.dat+j2);
              }
          else{
              vectorf_copy(ff.p[0],pnt.dat+j0);
              vectorf_copy(ff.p[1],pnt.dat+j1);
              vectorf_copy(ff.p[2],pnt.dat+j2);
              }
          ff.compute();
          fac.add(ff);
          // update edges
          e0->cnt++;
          e1->cnt++;
          ee.ld(j0,j2); for (e=edge.dat,j=0;j<edge.num;j++,e++) if (*e==ee) { e->cnt++; j=-1; break; } if (j>=0) edge.add(ee);
          break;
          }
      }
  

  The full C++ code and description for the STL3D class is in the link above. I used some sphere STL mesh I found in my archive and color the hole patching triangles in green to recognize them. Here the result:

  The black lines are wireframe and red ones are just debug draw of the edge[],pnt[] arrays for debug ...

  As you can see it works even for holes bigger than just single triangle :) ...

  这篇关于如何检测和保存边缘顶点中的循环连通性（孔检测）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！