1

我找不到一种有效的方法来生成给定边缘的对边。我的想法只是进行迭代：

//construct the opposite half edges
for(int j=0;j<edge_num;j++)
        for(int m=0;m<edge_num;m++)
if(edge[j].vert_end->v_index==edge[m].vert_start->v_index  && 
   edge[j].vert_start->v_index==edge[m].vert_end->v_index )
                {
                    edge[j].pair = &edge[m];
                    edge[m].pair = &edge[j];
                }

关于半边的其他信息是从加载 .M 文件的过程中生成的。我的结构是：

class HE_vert{
public:
    GLfloat x, y, z;
    int v_index;
    HE_edge *edge;
};

class HE_face{
public:
    int v1, v2, v3;
    int f_index;
    HE_edge* edge;
};

class HE_edge{
public:
    HE_edge(){ pair = NULL; }
public:
    HE_vert* vert_start;   // vertex at the start of the half-edge
    HE_vert* vert_end;   // vertex at the end of the half-edge
    HE_edge* pair;   // oppositely oriented adjacent half-edge
     HE_face* face;   // face the half-edge borders
    HE_edge* next;   // next half-edge around the face
    int e_index;
};

我检查了所有的输出信息，它是正确的，但是计算时间很长，尤其是在加载 bunny.M 时。我怎样才能以更有效的方式做到这一点？你能给我一些提示吗？

4

1 回答 1

0 
// grid[i + vert_num*j] = edge from i to j
int grid[vert_num*vert_num]; // malloc()?

// memset()?
for (int i = vert_num*vert_num - 1; i >= 0; i--)
{
    grid[i] = -1;
}

for (int i = 0; i < edge_num; i++)
{
    int i_from = edge[i]->vert_start->v_index;
    int i_to = edge[i]->vert_end->v_index;
    int pair_index = grid[i_to + vert_num*i_from];

    if (pair_index >= 0)
    {
        edge[i]->pair = edge[pair_index];
        edge[pair_index]->pair = edge[i];
        grid[i_to + vert_num*i_from] = -1;
    }
    else
    {
        grid[i_from + vert_num*i_to] = i;
    }
}

可能的优化：使用链表而不是巨大的数组。每行/列只有大约 1-4 个条目。

于 2012-09-22T09:44:10.843 回答