用於將連接三角形分組到組中的C++算法

Question

我有一個三角形網格，它具有不同的三角形組，例如一組15個連接的三角形，後面跟着25個三角形的另一個組（不連接到第一個）。連接三角形的組的數量是任意的，並且組本身可以是任何大小（1到任何值）。我需要爲每個三角形頂點分配一個索引，以指示它屬於哪個連接的三角形組。因此，在上面的例子中，我將給出構成15個三角形組的頂點的索引爲0，並且組成25個三角形的組的頂點的索引爲1（依此類推）。

下面的代碼是非常慢，當我餵它一個70,000 +三角形的數組，但工程。有沒有人有一些洞察代碼的領域，我可以找到最有效的優化？

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    //test array of vertex indices - each triple is a discrete triangle 
    int vv[21] = {0,1,2, 2,3,4, 4,5,6, 7,8,9, 9,10,11, 0,99,80, 400, 401, 402}; 

    //setup the initial arrays prior to the while loop 
    std::vector<int> active_points; 
    std::vector<vector<int>> groups; 
    std::vector<int> active_triplets(&vv[0], &vv[0]+21); 

    //put the first three triangle points into active points 
    active_points.push_back(active_triplets[0]); 
    active_points.push_back(active_triplets[1]); 
    active_points.push_back(active_triplets[2]); 

    int group_index = 0; 

    //put these initial points in the first group 
    std::vector<int> v; 
    v.push_back(active_points[0]); 
    v.push_back(active_points[1]); 
    v.push_back(active_points[2]); 
    groups.push_back(v); 

    //remove the first triangle points from the triplets array 
    std::vector<int>::iterator it = active_triplets.begin(); 
    active_triplets.erase(it, it+3); 

    while (active_triplets.size() > 0) 
    { 
     //once we've exhausted the first group of connections 
     //we move on the next connected set of triangles 
     if (active_points.size() == 0) 
     { 
      group_index++; 
      active_points.push_back(active_triplets[0]); 
      active_points.push_back(active_triplets[1]); 
      active_points.push_back(active_triplets[2]); 

      std::vector<int> v; 
      for (std::vector<int>::iterator it = active_points.begin(); it != active_points.end(); ++it) 
      { 
       v.push_back(*it); 
      } 
      groups.push_back(v); 

      std::vector<int>::iterator it = active_triplets.begin(); 
      active_triplets.erase(it,it+3); 
     } 

     //create a vector to store the 'connected' points of the current active points 
     //I don't think I can modify any of the existing vectors as I iterate over them 
     std::vector<int> temp_active_points; 
     //start check this group of three vertices 
     for (std::vector<int>::iterator it = active_points.begin(); it != active_points.end(); ++it) 
     { 
      std::vector<int> polys_to_delete; 
      for (std::vector<int>::iterator it_a = active_triplets.begin(); it_a != active_triplets.end();++it_a) 
      { 
       if (*it == *it_a) 
       { 
        //which triangle do we hit? put all points in temp_active_points. 
        //Once a vertex matches with another vertex we work out the other 
        //connected points in that triangle from that single connection 

        int offset = it_a - active_triplets.begin(); 
        int mod = (it_a - active_triplets.begin()) % 3; 
        polys_to_delete.push_back(offset - mod); 
        if (mod == 1) 
        { 
         temp_active_points.push_back(active_triplets.at((offset - 1))); 
         temp_active_points.push_back(active_triplets.at((offset + 1))); 
        } 
        else if (mod == 2) 
        { 
         temp_active_points.push_back(active_triplets.at((offset - 2))); 
         temp_active_points.push_back(active_triplets.at((offset - 1))); 
        } 
        else 
        { 
         temp_active_points.push_back(active_triplets.at((offset + 1))); 
         temp_active_points.push_back(active_triplets.at((offset + 2))); 
        } 
       } 
      } 
      int offset_subtraction = 0; 
      for (std::vector<int>::iterator it = polys_to_delete.begin(); it != polys_to_delete.end(); ++it) 
      { 
       std::vector<int>::iterator it_a = active_triplets.begin(); 
       active_triplets.erase(it_a + (*it - offset_subtraction), it_a + (*it - offset_subtraction) + 3); 
       offset_subtraction += 3; 
      } 
     } 
     for (std::vector<int>::iterator it = temp_active_points.begin(); it != temp_active_points.end(); ++it) 
     { 
      groups[group_index].push_back(*it); 
     } 
     //remove duplicates 
     std::sort(temp_active_points.begin(), temp_active_points.end()); 
     temp_active_points.erase(std::unique(temp_active_points.begin(), temp_active_points.end()), temp_active_points.end()); 
     active_points = temp_active_points; 
     temp_active_points.clear(); 
    } 
    for (std::vector<vector<int>>::iterator it = groups.begin(); it != groups.end(); ++it) 
    { 
     for (std::vector<int>::iterator it_sub = (*it).begin(); it_sub != (*it).end(); ++it_sub) 
     { 
      std::cout << it - groups.begin() << ' ' << *it_sub << '\n'; 
     } 
    } 
} 

在彼得的評論我重做的代碼與同事的幫助。使用如此之快的地圖：

#include "stdafx.h" 
#include <iostream>  // std::cout 
#include <algorithm> // std::set_difference, std::sort 
#include <vector>  // std::vector 
#include <set>  // std::vector 
#include <cmath> 
#include <map> 

using namespace std; 

// the global vertex indices 
int numIndices; 
int* indices; 

class Triangle 
{ 
public: 
    explicit Triangle(int positionIndex_) : added(false), positionIndex(positionIndex_) {} 

    int positionIndex; // positinon of the first index of this triangle in the global vert array (which is in 3's) 

    // only valid with 0, 1, 2 
    int getIndex(int i) { return indices[positionIndex + i];} 

    bool isNeighbour(Triangle* other) 
    { 
     for (int i = 0; i < 3; ++i) 
      for (int j = 0; j < 3; ++j) 
       if (getIndex(i) == other->getIndex(j)) 
        return true; 
     return false; 
    } 

    bool isAdded() const{return added;} 
    void setAdded(){ added = true;} 

    int getNeighbourCount() const{ return neighbours.size(); } 
    Triangle* getNeighbour(int i) const{ return neighbours[i];} 
    void AddNeighbour(Triangle* neighbour) 
    { 
     neighbours.push_back(neighbour);//changed to set 
    } 

private: 
    std::vector<Triangle*> neighbours;//changed to set 
    bool added; 
}; 

std::vector<Triangle*> triangles; 

void createAllTriangles() 
{ 
    for (int i = 0; i < numIndices; i += 3) 
     triangles.push_back(new Triangle(i)); 

    //must delete all these pointers created with new 
} 

void setupAllNeighboursA() 
{ 
    std::map<int,std::set<int>> vertex_to_tris; 
    for (int i = 0; i < numIndices; i += 3) 
    { 
     vertex_to_tris[indices[i]].insert(i); 
     vertex_to_tris[indices[i+1]].insert(i); 
     vertex_to_tris[indices[i+2]].insert(i); 
    } 

    int n = triangles.size(); 
    for (int i = 0; i < n; ++i) 
    { 
     Triangle* t = triangles[i]; 
     std::set<int> temp_neighbours; 
     for (int j = 0; j < 3; ++j) 
     { 
      int test_index = t->getIndex(j); 
      for (std::set<int>::iterator it = vertex_to_tris[test_index].begin(); it != vertex_to_tris[test_index].end(); ++it) 
      { 
       if (*it != i) temp_neighbours.insert(*it/3);//divide by 3 to get the 'actual' tri index 
      } 
     } 

     for (std::set<int>::iterator it = temp_neighbours.begin(); it != temp_neighbours.end(); ++it) 
     { 
      Triangle* other = triangles[*it]; 
      t->AddNeighbour(other); 
     } 
    } 
} 

class Island 
{ 
public: 
    void recursiveAdd(Triangle* t) 
    { 
     AddAndSetAdded(t); 
     for(int i = 0; i < t->getNeighbourCount(); i++) 
      if (! t->getNeighbour(i)->isAdded()) 
       recursiveAdd(t->getNeighbour(i)); 
    } 
    std::set<Triangle*> children; 
private: 
    void AddAndSetAdded(Triangle* t) 
    { 
     t->setAdded(); 
     children.insert(t); 
    } 
}; 

std::vector<Island*> island_list; 

void createIslands() 
{ 
    for (int i = 0; i < int(triangles.size()); ++i) 
    { 
     Triangle* t = triangles[i]; 
     if(! t->isAdded()) 
     { 
      Island* island = new Island; 
      island->recursiveAdd(t); 
      island_list.push_back(island); 
     } 
    } 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    indices = vv; 
    numIndices = 73728; 
    createAllTriangles(); 
    setupAllNeighboursA(); 
    createIslands(); 

    for (int x = 0; x < int(island_list.size()); x++) 
    { 
     std::cout << "Island Index: " << x << endl; 
     std::cout << island_list[x]->children.size() << endl; 
    } 
} 

Answer 1

我想大部分的時間會在這些線路中度過：

for (std::vector<int>::iterator it = active_points.begin(); it != active_points.end(); ++it) 
    { 
     std::vector<int> polys_to_delete; 
     for (std::vector<int>::iterator it_a = active_triplets.begin(); it_a != active_triplets.end();++it_a) 
     { 
      if (*it == *it_a) 

我的理解是，這是測試每個活動點對每一個活動的三角形，所以這可能會循環數千次，每個活動點。

我認爲如果您準備了從頂點到使用相應頂點的三角形列表的映射，速度會快很多。然後您會立即發現所有連接的三角形，而不必搜索它們。