将连接的三角形分类为组的 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';
        }
    }
}

在 Peter 的评论之后，我在一位同事的帮助下重做了代码。使用 map 要快得多:

#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)

我的理解是，这是针对每个事件三角形测试每个事件点，因此这可能会针对每个事件点循环数千次。

我认为如果您准备一个从顶点到使用相应顶点的三角形列表的映射，这会更快。然后您会立即发现所有连接的三角形，而不必搜索它们。