c++ - 从 3D 线框(线和点)创建网格

Question

我有一个程序可以生成点云以及边缘信息，即点之间的连接。我希望能够从这些数据中创建面孔。目前，我使用的是一个简单的算法，如下所示:

int CMesher::Poligonize(){
  unsigned int i0 = 0;
  unsigned int i1 = 0;
  int num = this->_nodenum;
  int facenum = 0;

  for (i0 = 0; i0 < num; i0++)
    for (i1 = 0; i1 < num; i1++){
        if (i1 <= i0)
          continue;
        if (this->IsEdge(i0, i1))
          facenum += this->PoligonizeEdge(i0, i1);
    }

  return facenum;
}

int CMesher::PoligonizeEdge(unsigned int i0, unsigned int i1){
   int facenum = 0;
   unsigned int* Ci01 = <unsigned int*>d_malloc(
          sizeof(unsigned int)*this->_nodenum);
   int Ci01_num = 0;
   //get the list of common neighbours between i0 and i1, 
        //Ci01=n0,...,ni,.., nK
   this->GetShared(i0, i1, Ci01, this->_nodenum, &Ci01_num);
   unsigned int ni = 0;
   unsigned int n0, n1;
   int it0 = 0;
   //For each common neighbour ni in Ci01
   while (it0 < Ci01_num){
     ni = Ci01[it0];
     //create a face f {ni, i0, i1}
     facenum += this->CreateFace(ni, i0, i1);
     it0++;
   //If i0 and i1 have NO common neighbours
   unsigned int* NB0 = <unsigned int*>d_malloc(
          sizeof(unsigned int)*this->_nodenum)
   int NB0_num = 0;
   int NB0_mem = this->_nodenum;
   unsigned int* NB1 = <unsigned int*>d_malloc(
          sizeof(unsigned int)*this->_nodenum);
   int NB1_num = 0;
   int NB1_mem = this->_nodenum;

   unsigned int it1 = 0;
   unsigned int it2 = 0;

   unsigned int* Cn01 = <unsigned int*>d_malloc(
          sizeof(unsigned int)*this->_nodenum);
   int Cn01_num = 0;
   int Cn01_mem = this->_nodenum;

   unsigned int n2 = 0;

   if (Ci01_num == 0){
      //Get the lists of neighbours of i0, NB0, and of i1, NB1
      this->GetNeighbours(i0, NB0, NB0_mem, &NB0_num);
      this->GetNeighbours(i1, NB1, NB1_mem, &NB1_num);

      //For each neighbour n0 in NB0, and n1 in NB1
      it0 = 0;
      while (it0 < NB0_num){
         n0 = NB0[it0];
         if (n0 == i1){
            //i0 is al. a neighbour of i1, and vice versa
            it0 += 1;
            continue;
         }
         it1 = 0
         while (it1 < NB1_num){
            n1 = NB1[it1];
            if (n1 == i0){
              //i0 is al. a neighbour of i1, and vice versa
              it1 += 1;
              continue;
            }
            isE = this->IsEdge(n0, n1);
            //if n0 and n1 are connected
            if (isE > 0){
              //Create two faces {i0, i1, n0} and {i1, n0, n1}
              facenum += this->CreateFace(i0, i1, n0);
              facenum +=  this->CreateFace(i1, n0, n1);
            }else{
              //get the list of common neighbours between n0 and n1, Cn01
              this->GetShared(n0, n1, Cn01, Cn01_mem, &Cn01_num);
              it2 = 0;
              //for each n2 in Cn01
              while (it2 < Cn01_num){
                n2 = Cn01[it2];
                //Create 3 faces {i0, i1, n2}, 
                //{i1, n1, n2}, {i1, n0, n2}
                if (n2 == i0 or n2 == i1){
                  //n2 cannot be n0 or n1, only i0 or i1
                  it2 += 1;
                  continue;
                }
                facenum +=  this->CreateFace(i0, i1, n2);
                facenum +=  this->CreateFace(i1, n1, n2);
                facenum +=  this->CreateFace(i1, n0, n2);
                it2 += 1;
              }
           }
           it1 += 1;
        }
        it0 += 1;
     }
  }
  //delete the lists
  free(Ci01);
  free(Cn01;
  free(NB0);
  free(NB1);
  return facenum;
}

//Not described here, but obvious
int CMesher::IsEdge(unsigned int n1, unsigned int n2);
int CMesher::DeleteEdge(unsigned int n1, unsigned int n2);
int CMesher::CreateFace(unsigned int n1, unsigned int n2
       unsigned int n3);

//Return a vector of nodes(vertice)
// linked to both n1 and n2
//@param shared: the input vector containing the vertice
//@param sharedmem: the size in memory of the input array
//@param sharednum: the actual number of shared vertice //found
int CMesher::GetShared(unsigned int n1, unsigned int n2,
   unsigned int* shared, int sharedmem, int* sharednum);

//Returns a vector of nodes(vertice)
// linked to both n1
//@param neighbours: the input vector containing the //vertice
//@param neighmem: the size in memory of the input array
//@param neighnum: the actual number of neighbours vertice //found
int CMesher::GetNeighbours(unsigned int n1,
   unsigned int* neighbours, int neighmem, int* neighnum);

我试过上面的代码，但我没有得到很好的三角剖分。重叠太多。换句话说，最终的网格不是流形。

问题:有没有更好的算法？或者我怎样才能改进我的算法？顺便说一下，我没有使用 Marching cubes 或 Delaunay triangulation，因为 90% 的工作已经完成，即我有地形(点之间的互连)。 MC 和 Delaunay 仅适用于没有地形的点云。ADEMDUM 1:Blender 3D 完全按照我想以编程方式执行的操作。这是它所做的帽子的捕获:

Answer 1

我想你可以用 qhull 得到凸包。