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

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

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

bool equal(const ZGVECTOR3& a, const ZGVECTOR3& b, zgF32 eps)
{ 
  //eps:許容誤差 差がこの値以下なら同じ位置とみなす
  zgF32 sub = b.x - a.x;
  if(sub > eps)return false;//大きい
  if(sub < -eps)return false;//小さい
	
  sub = b.y - a.y;
  if(sub > eps)return false;
  if(sub < -eps)return false;

  sub = b.z - a.z;
  if(sub > eps)return false;
  if(sub < -eps)return false;
  return true;
}

//総当たりアルゴリズムで頂点のマージ
zgU32 MergeVertex_Bubble(
    const std::vector<ZGVECTOR3>& vertex,
    std::vector<zgU32>& merge_map,//マージ後のindex値
    zgF32 EPS)
{
  merge_map.resize(vertex.size(), 0);
  zgU32 new_idx = 0;	
  for(zgU32 iv=0;iv<vertex.size();++iv){
    const ZGVECTOR3& v = vertex[iv];
    //同じ位置の頂点を探す
    zgU32 jv=0;
    for(jv=0;jv<iv;++jv){
      const ZGVECTOR3& w = vertex[jv];
      if( equal(v,w,EPS) ){
        break;
      }
    }
    if(jv==iv){
      merge_map[iv] = new_idx++;
    }else{
      merge_map[iv] = merge_map[jv];
    }
  }
  return new_idx;//マージ後の頂点数
}

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

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

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

頂点のソート

ソートする頂点構造体
typedef float zgF32;
struct ZGVECTOR3
{
  zgF32 x,y,z;
};
まず思いつくソート方法
// ソート用の関数オブジェクト
struct  SortZGVECTOR3
{
  bool operator()(const ZGVECTOR3* a, const ZGVECTOR3* b) const {
    if( a->x < b->x)return true;
    if( a->y < b->y)return true;
    if( a->z < b->z)return true;
    return false;
  }
};

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

頂点のソート
// ソート用の関数オブジェクト
struct  SortZGVECTOR3
{
  bool operator()(const ZGVECTOR3* a, const ZGVECTOR3* b) const {
    return (a->x + a->y + a->z) < (b->x + b->y + b->z);
  }
};

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

頂点のマージ処理

//ソート用関数オブジェクト
struct  SortZGVECTOR3
{
  bool operator()(const ZGVECTOR3* a, const ZGVECTOR3* b) const {
    return (a->x+a->y+a->z) < (b->x+b->y+b->z);
  }
};

// 頂点のマージ
zgU32 MergeVertex(
        const std::vector<ZGVECTOR3>& vertex,
        std::vector<zgU32>& merge_map,//マージ後のindex値
        zgF32 EPS)//許容誤差 差がこの値以下なら同じ位置とみなす
{
    zgU32 new_idx = 0;	
    zgU32 vnum = vertex.size();

    // ベクトル要素を足した値でソート 
    std::vector<const ZGVECTOR3*> sort_vertex;
    sort_vertex.reserve(vertex.size());
    for(auto& v : vertex){
      sort_vertex.push_back(&v);
    }
    std::sort(sort_vertex.begin(), sort_vertex.end(), SortZGVECTOR3());

    merge_map.resize(vertex.size(), vnum);//共有化済みフラグも兼ねる

    // 配列の先頭から順に位置の近い頂点を1つにまとめる
    for(zgU32 iv=0;iv<vnum;++iv){
      zgU32 a_idx = sort_vertex[iv] - vertex.data();
      const ZGVECTOR3& a = *sort_vertex[iv];

      if( merge_map[a_idx] < vnum )continue;//すでにマージ済み
      merge_map[a_idx] = new_idx;

      zgU32 next = vnum;
      for(zgU32 jv=iv+1;jv<vnum;++jv){
        zgU32 b_idx = sort_vertex[jv] - vertex.data();
        const ZGVECTOR3& b = *sort_vertex[jv];
        if( merge_map[b_idx] < vnum )continue;//すでにマージ済み

        zgF32 sort_dist = fabs(a.x+a.y+a.z - (b.x+b.y+b.z)); 
        if(sort_dist > 3.0f*EPS){
          break;//これ以上先に近い頂点はない
          //3.0f*EPS:数式から求めた値 テキトーな値ではない 
          //float誤差を考えて3.01fとしたほうがいいかも
        }

        if( equal(a, b, EPS) ){
          merge_map[b_idx] = new_idx;
        }else{
          if( next == vnum){
            //次の検索開始位置
            next = jv-1;
          }
        }
      }
      ++new_idx;
      if( next < vnum ){
        iv = next;
      }
    }
    return new_idx;//マージ後の頂点数
}

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

3.0f*EPSの導出

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

頂点V0={x0,y0,z0} V1={x1,y1,z1}
ソート値 s0=x0+y0+z0  s1=x1+y1+z1
ソート値の差分
e = s0 - s1
e = (x0-x1)+(y0-y1)+(z0-z1)
  = ex + ey + ez  -------------- (1)
ex,ey,ezの絶対値が最大のものをemとすると
|e| > 3*EPS  EPS>0 のとき
|em| > EPS が成立する

証明
ex,ey,ezのうち
2番目に大きいものを a*em
最小のものを       b*em ( |a|=|b|も含む )
(1)式に代入
e = (1+a+b)em ----------(2)

|em| > |a*em| ≧ |b*em|より
-1 3*EPS に(2)を代入
|(1+a+b)em| > 3*EPS
|1+a+b||em| > 3*EPS ----(4)
|em| > (3/|1+a+b|)*EPS
(3)より 3/|1+a+b| > 1
∴|em| > EPS 

|ex| = |ey| = |ez| = |em|のとき
a=b=1なら(4)より
3|em| > 3*EPS
a=1,b=-1 a=-1,b=1 a=b=-1なら(4)より
|em| > 3*EPS
∴|em| > EPS

証明終了

あとがき

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

コメントを残す

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

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