位置を共有している頂点のマージアルゴリズム

3Dモデルデータの最適化のために、ほぼ同じ位置にある頂点データを1つにまとめる(マージする)処理を作成します。総当たりで近い位置にあるか比較していけば簡単に実装できると思っていました……
これまでの経験では数千頂点程度のマージ処理だったので、それほど実行速度を気にすることはありませんでした。が、今回約70000頂点のマージを総当たり比較で処理したところ、処理時間1分間以上。違う方法を考えなければ。

総当たりで比較(バブルソートと同じ方法)

万単位の頂点では、対応できません。

近い頂点の検索アルゴリズム

衝突判定などで使用される空間分割(オクトツリーなど)アルゴリズムで検索処理の高速化を行うことが一般的だと思います。しかし今回、ちょっと違った方法で検索処理を作成してみます。基本は頂点をソートすることで検索の効率を上げます。

頂点のソート

ソートする頂点構造体

まず思いつくソート方法

この方法での問題は、x平面上に頂点が偏った場合、検索効率が悪化することです。この現象が発生する可能性は低くありません。その場合、他の軸の判定を先に行うことで回避できますが、事前に頂点の分布を調べる必要があります。そんなことをするなら素直に空間分割アルゴリズムで検索します。
もっと単純なアルゴリズムがないか考えてみます。

頂点のソート

ベクトルの各要素を加算した値でソートします。軸毎のソートより複雑になるため、特定の位置に頂点分布が偏る可能性が低くなるはずです。なので事前に頂点分布を調べる必要もないはずです。

頂点のマージ処理

頂点をソートすることで、距離の近い頂点が配列上でも近くなり、比較の回数を大幅に減らせます。この方法で一番重要な処理は、 if(sort_dist > 3.0f*EPS)の部分です。これで比較する必要のない頂点を判定し、比較回数を減らします。マージ処理、検索アルゴリズムの詳細は、ソースコードを見てください(手抜き)。

3.0f*EPSの導出

if(sort_dist > 3.0f*EPS)で比較処理をスキップできることを証明します。

あとがき

ちょっと面白いアルゴリズムだと思ったので紹介してみました。計算式が単純で、それなりに実用性もあるアルゴリズムではないでしょうか。使ってみて特に問題はなさそうなので大丈夫だと思いますが、間違っていたらすみません。

広告

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

認証:数字を入力してください(必須) * Time limit is exhausted. Please reload CAPTCHA.