マーチング・キューブズ法の「14通り」の謎を解く

Isosurfaces: Geometry, Topology, and Algorithms

マーチング・キューブズ法(Marching Cubes)は、３次元格子の頂点位置において定義された値（値そのものの意味は任意：温度、密度、存在確率、、などなど）をもとに、「等値面」を作成するためのよく知られた手法である。私もこれまでに何度か実装したことがあり、未熟な実装であったとはいえ、閾値を変えるにつれて等値面が変形する様を見ては楽しんだものである。

等値面を作成する上で、ある種自明と考えられなくもない手法であるにもかかわらず、特許化されたということもあり、ソフトウェア特許の功罪や難しさを語る際の代表的な事例とされてきたという見方もあるようだ。これを避けるために、マーチングテトラヒドロンズという苦し紛れの別手法というものも考案されたりしたらしい。同じ内容を紹介しているのにマーチングキューブズという言葉が最後まで出てこない陰関数曲面の入門書があったり、日本の国立研究機関でも殆ど同一と思われる手法を使っているにも関わらず、いくつかの優位性が付与され、あえて別の名前が付けられて紹介されていたりする事例があったりするのだが、もしかしたらそれもこの特許の問題があったからなのかも知れない。とにかく、この手法に関しては、そういう不思議な思いをよくしたことを覚えている。
しかししかし、85年に取得されたこの特許から20年以上が経過した今、もはやマーチングキューブは米国内にあっても誰でも利用できる技術となったようだ。

３次元格子の中で、任意の隣り合う８つの頂点から構成される箱状セル（箱、直方体）を考えるとき、８隅に位置する頂点の値を、それが閾値以上か否かで２値化しておく。一つのセルの中だけで見れば、８隅にある８つの頂点のとる２値パターンは、２の８乗＝256通りあることになり、このたかだか256通りについて、それに対応する等値面のテセレーション雛形を用意しておけばよいというものだが、さらに対称性を考慮すると、14通りのケースのみについて、テセレーションを用意しておけばよいという内容が、マーチング・キューブズ法の述べるところである。

ところが以上を知ったところで、実際に実装するのはなかなか容易ではないことに気付く。たかだか14通りしかないよ、よかったねなどと言われても。実際には256通りあるのだ。

• どうやって14通りとわかったのか、256通りあるパターンをどうグループ分けして14通りに帰着したものか。
• 14通りのなかのいずれかのテセレーションを行った後、それをもとの向きに、どう戻したらいいものか。

勿論、最終的にはテセレーションの表を、256通り作れればよいわけだが、即ちその表をどう作るかが問題なのである。
以下ではこの問題を真正面から考え、自力解決していこう。

勿論巷に落ちてるソースコード
http://paulbourke.net/geometry/polygonise/
などをそのまま利用するのも実用上は有効だがここでは他力に頼らないアプローチを模索したいのである）

対称性と聞くと、「群論」という数学の一分野が思い浮かぶが、数学者ではない手前、群論というものをこれだけのために紐解く気にもならない。しかしながらその14通りのグルーピング出しを体系的に行い、マーチングキューブズ法の実装をスマートに完全自作する方法を考えたい。

８つの頂点の２値化された値を、並べて、８ビットの変数として扱うことを考えよう。図のように、頂点にIDを振り、対応するビットにその頂点の２値化結果をセットする。
このようにして、セルの８隅の頂点がとり得る全ての２値パターンを、0から255の値をとる8ビット数値として考える。この8ビット数値を、コンフィギュレーションと呼ぶことにしよう。（図の例はコンフィギュレーション#29の場合である）
そうすると例えば、コンフィギュレーション#1,#2,#4,#8,#16,#32,#64,#128 の８つは、どれも赤い頂点を一つだけ持つわけで、然るべき回転・対称・ビット反転操作を行うことにより、コンフィギュレーション#１と重ね合わせられることがわかる。
このように回転・対称・ビット反転操作を組み合わせて互いに完全に一致させることのできる二つのコンフィギュレーションは、同一の「グループ」に属するものとする。同一グループのコンフィギュレーションは、テセレーション構成を共有することができる。（#1の場合のテセレーション構成は、赤い点を囲むような三角が一つあるだけの簡単なものとなる。）
そのグループに含まれる最小のコンフィギュレーション番号（＝プライマリコンフィギュレーション）を以って、グループ名とする。上記の場合は、皆、グループ＃1に属する、という言い方が出来る。

（☆ビット反転とは、赤い頂点を赤でなくし、赤でない頂点を赤にする、という操作である。上記の例で実はビット反転まで考えると、#254、その他さらに７つの数値がやはり同じコンフィギュレーション#1のグループに属するはずであることがわかるだろう）

すると、上記でも述べたように、マーチングキューブズ法によれば、全部で１４グループ存在する、というのである。本当にそうなのかを、実際に確かめてみよう。グループの定義はもう確立しているので、以下のようなアルゴリズムで、簡単なクラスタリング処理をやってみよう。

1. 256個の各コンフィギュレーションについて、グループを作成する。（全部で256グループできる）
2. あるグループの任意の要素（コンフィギュレーションのこと）が、回転・対称・ビット反転の組み合わせ操作によって、別のグループの要素と一致したならば、両グループを同一グループとして融合。
3. グループ間融合が全く起こらなくなるまで、２を繰り返す。

いかがだろうか。以上のアルゴリズムによって、始め256あったグループ数は、果たしてちゃんと14個のグループに統合されるだろうか。私はC++しか使えないので、敢えてC++でこのクラスタリング計算を実装してみた。その実装と詳細説明および更なる考察は、後日にまわすとして、ここでは結果のみを示そう。たしかに、14グループになることが確認できた。それぞれのグループに含まれるコンフィギュレーションを、出力させてみた。

study on MarchingCubes algorithm:
configurations of 14 groups.
group #0: 0 255
group #1: 1 2 4 8 16 32 64 127 128 191
          223 239 247 251 253 254
group #3: 3 5 10 12 17 34 48 63 68 80
          95 119 136 160 175 187 192 207 221 238
          243 245 250 252
group #6: 6 9 18 20 33 40 65 72 96 111
          123 125 130 132 144 159 183 190 215 222
          235 237 246 249
group #7: 7 11 13 14 19 21 31 35 42 47
          49 50 55 59 69 76 79 81 84 87
          93 112 115 117 138 140 143 162 168 171
          174 176 179 186 196 200 205 206 208 213
          220 224 234 236 241 242 244 248
group #15: 15 51 85 170 204 240
group #22: 22 41 73 97 104 107 109 121 134 146
          148 151 158 182 214 233
group #23: 23 43 77 113 142 178 212 232
group #24: 24 36 66 126 129 189 219 231
group #25: 25 26 28 37 38 44 52 56 61 62
          67 70 74 82 88 91 94 98 100 103
          110 118 122 124 131 133 137 145 152 155
          157 161 164 167 173 181 185 188 193 194
          199 203 211 217 218 227 229 230
group #27: 27 29 39 46 53 58 71 78 83 92
          114 116 139 141 163 172 177 184 197 202
          209 216 226 228
group #30: 30 45 54 57 75 86 89 99 101 106
          108 120 135 147 149 154 156 166 169 180
          198 201 210 225
group #60: 60 90 102 153 165 195
group #105: 105 150

次は、各グループに分類された各コンフィギュレーションが、どのような操作によって、グループのプライマリコンフィギュレーションと一致するのかを調べたり、各グループのテセレーションをどうするかということについて、考えて行かなくてはならない。→次の日記はこちら。

Visualization in Medicine and Life Sciences (Mathematics and Visualization)