Создание сетки из каркаса (линий и точек) в 3D - PullRequest
Новая
       62

Создание сетки из каркаса (линий и точек) в 3D

0 голосов
/ 20 сентября 2018

У меня есть программа, которая создает облако точек вместе с информацией о ребрах, то есть связь между точками.Я хотел бы иметь возможность создавать лица из этих данных.В настоящее время я использую простой алгоритм, который выглядит следующим образом: 

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 делает именно то, что я пытаюсь сделать программно.Вот захват шляпы: enter image description here

1 Ответ

0 голосов
/ 23 сентября 2018

Я думаю, вы можете получить выпуклый корпус с помощью qhull.

...