前回に引き続き、あまり語られてこなかったマーチングキューブズ法の謎を追う旅の途中だが、ここでは前回示した、14グループとそのコンフィギュレーションの探索を行った際の、実装上の詳細とノウハウをメモしておく。
格子内の８つの頂点について、IDを振るやり方についてのメモ。
箱（キューブ）の８隅にある８つの頂点。
どの頂点にどのID値をどう割り振るか、一見とるにたらないこの決め事はともすれば実装者の自由に任された至極トリビアルな事柄にも思えるのだが、案外そうでもなかったりする。少しだけ気の利いたIDの振り方をすることにより、ID値そのものに情報を持たせることができ、その後の処理の簡潔な記述にも役立つのである。
そのやり方とは、X軸に第０ビット、Y軸に第１ビット、Z軸に第２ビット、をとるやり方だ。各軸は0か1の値をとるので、勿論8つの頂点に割り振れば0〜7という8つのID値が消費される。こうしておくと、ID値とその頂点の位置とが自ずと対応し、どのIDがどの頂点だったっけかと迷う必要がなくなるし、ID値の90度回転や対称操作が非常に楽に記述できるようになる。
たとえば、XY面内反時計回転で考えると、任意の頂点のID値に対し、
- Yビット値の否定値をXビット値にし、
- Xビット値をYビット値に
するだけで、90度回転したときのID値が得られたり、
（図で言えば、上記操作で０⇒１⇒３⇒２⇒０と回転する）
X方向反転なら、
- Xビット値のみを反転するだけ、
で、、X方向に反転したID値が得られる。
（図で言えば、上記操作で０⇔１、２⇔３、と反転を繰り返す）
などなど。いかがだろうか。
あとはこれを利用して、グルーピングを実装すればよいだけだ。以下のようなC++コードとなった。私のマシンでは一瞬で14グループが計算され出力された。
#include <iostream> #include <set> #include <vector> #include < algorithm > using namespace std; // x: 0->001 // y: 0->010 // z: 0->100 class tr { public: enum Axis{ X=0, Y, Z }; public: static void rotValX( int& val ){ trval_sub( val, &tr::rotIdX ); } static void rotValY( int& val ){ trval_sub( val, &tr::rotIdY ); } static void rotValZ( int& val ){ trval_sub( val, &tr::rotIdZ ); } static void symValX( int& val ){ trval_sub( val, &tr::symIdX ); } static void symValY( int& val ){ trval_sub( val, &tr::symIdY ); } static void symValZ( int& val ){ trval_sub( val, &tr::symIdZ ); } static void complement( int& val ){ val = (~val)&0xff; } private: static void rotIdX( int& id ){ rotid_sub( id, Y, Z ); } static void rotIdY( int& id ){ rotid_sub( id, X, Z ); } static void rotIdZ( int& id ){ rotid_sub( id, X, Y ); } static void symIdX( int& id ){ sym_planar( id, X ); } static void symIdY( int& id ){ sym_planar( id, Y ); } static void symIdZ( int& id ){ sym_planar( id, Z ); } // static void bit_mod( int& val, int bitid, bool s ){ val &= ~(1<<bitid); val |= s<<bitid; } static void rotid_sub( int& id, Axis a, Axis b ) { bool u = !(id&(1<<b)); bool v = id&(1<<a); bit_mod( id, a, u ); bit_mod( id, b, v ); return; } static void sym_planar( int& id, Axis a) { bool v = !( id&(1<<a) ); bit_mod( id, a, v ); return; } template< class TrIdFunc > static void trval_sub( int& val, TrIdFunc fn ){ int ids[8]; for( int i=0; i<8; ++i ){ int id=i; fn( id ); ids[i] = id; } subst( val, ids ); return; } static void subst( int& val, int ids[8] ){ int tmp = val; val = 0; for( int i=0; i<8; ++i ) val |= ( (tmp&(1<<i))!=0 ) << ids[i]; return; } }; template< class Op > bool check_fusion( int cfg, set< int >& svi, set< int >& svj, Op op ) { op( cfg ); set< int >::iterator it = svj.find( cfg ); if( it!=svj.end() ){ svi.insert( svj.begin(), svj.end() ); svj.clear(); return !0; } return 0; } class is_empty { public: template< class T > bool operator()( T& t ){ return t.empty(); } }; int main( int argc, char* argv[] ) { // 256グループを作成 vector< set< int > > sv; for( int i=0; i<256; ++i ){ set< int > st; st.insert( i ); sv.push_back( st ); }// i // グループ間融合処理 bool fused = 0; do{ fused = 0; for( int i=0; i<sv.size() && !fused; ++i ){ for( int j=0; j<i && !fused; ++j ){ set< int >& svi = sv[i]; set< int >& svj = sv[j]; set< int >::iterator it; for( it =svi.begin(); it!=svi.end(); ++it ){ if( fused = check_fusion( *it, svi, svj, &tr::rotValX ) ) break; if( fused = check_fusion( *it, svi, svj, &tr::rotValY ) ) break; if( fused = check_fusion( *it, svi, svj, &tr::rotValZ ) ) break; if( fused = check_fusion( *it, svi, svj, &tr::symValX ) ) break; if( fused = check_fusion( *it, svi, svj, &tr::symValY ) ) break; if( fused = check_fusion( *it, svi, svj, &tr::symValZ ) ) break; if( fused = check_fusion( *it, svi, svj, &tr::complement ) ) break; }// it }// j }// i sv.erase( remove_if( sv.begin(), sv.end(), is_empty() ), sv.end() ); }while( fused ); // 結果の出力 cout<< "configurations of " << sv.size() <<" groups." <<endl; reverse( sv.begin(), sv.end() ); for( int i=0; i<sv.size(); ++i ){ cout << "group #"<< *sv[i].begin() <<":"; set< int >::iterator it; int cnt=1; for( it=sv[i].begin(); it!=sv[i].end(); ++it, ++cnt ){ cout << " " << *it; if( cnt%10==0 ) cout<< endl<<" "; }// it cout << endl; }// i return 0; }
