7

これは、3D アプリケーション用のエクスポーター プラグイン用です。私の現在のソリューションは正常に機能していますが、非常に遅いです (複雑さ O(n^2 * log n ) )。

これは、入力がオブジェクトの頂点の配列であり、重複とインデックス リストのない頂点のリストとして出力される関数である必要があります。

また、2 つの頂点が互いに非常に非常に近い場合 (たとえば、約 0.001 の差)、アルゴリズムは重複としてマークします。

私の質問は、線形時間でそれを行う方法はありますか、または少なくとも私のソリューションよりも高速ですか? どうもありがとうございました。

4

1 に答える 1

4

STL の set containerを使用して O(n log n) で実行できます。基本的に行うことは次のとおりです。

  1. ペア (頂点、整数) の空のセット、インデックスの空の配列、インデックス = 0 から開始します。
  2. 各頂点について、それがセット内にあるかどうかを確認します。そうでない場合は、ペア (頂点、インデックス) をセットに追加し、インデックスをインクリメントします。それ以外の場合は、セットから頂点のインデックスを取得します。どちらの場合も、頂点のインデックスをインデックス バッファーに追加します。
  3. 最後に、インデックス バッファーを取得し、セット内の頂点が頂点バッファーになります。

C++ での実装:

#include<set>
#include<vector>
#include<cmath>
using namespace std;

struct Vertex
{
    float x, y, z;
};

typedef pair<Vertex, int> VPair;

float eps = 0.001;

struct CmpClass // class comparing vertices in the set
{
    bool operator() (const VPair& p1, const VPair& p2) const
    {
        if (fabs(p1.first.x-p2.first.x) > eps) return p1.first.x < p2.first.x;
        if (fabs(p1.first.y-p2.first.y) > eps) return p1.first.y < p2.first.y;
        if (fabs(p1.first.z-p2.first.z) > eps) return p1.first.z < p2.first.z;
        return false;
    }
};

vector<Vertex> input, vbuffer;
set<VPair, CmpClass> vertices;
vector<int> indices;
int index = 0;

void ComputeBuffers()
{
    for (int i=0; i<input.size(); i++)
    {
        set<VPair>::iterator it = vertices.find(make_pair(input[i], 0/*this value doesn't matter*/));
        if (it!=vertices.end()) indices.push_back(it->second);
        else
        {
            vertices.insert(make_pair(input[i], index));
            indices.push_back(index++);
        }
    }

    // Notice that the vertices in the set are not sorted by the index
    // so you'll have to rearrange them like this:
    vbuffer.resize(vertices.size());
    for (set<VPair>::iterator it=vertices.begin(); it!=vertices.end(); it++)
        vbuffer[it->second] = it->first;
}
于 2013-01-19T18:08:08.790 に答える