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 に答える