じぇのサイト

点群モデルから，点群の内側にあるスケルトンを計算してみました．
この昔は気付かなかったことが今では気付けるようになっているので，今後が楽しみです．

ボクセルは内外を定義するだけで，任意の形状を定義することができます．
この性質を利用して，ボリュームデータの形状の操作を行ってみようと思います．

まずは前回の肉のついた螺旋を真ん中でばっすり切ってみます．
ボリュームデータなので中身が詰まっています．



これは，任意のボクセルを内側と定義した後に，手前半分を外とすることでものを切っています．
内外だけで，もの形状を定義しているので，内外だけで操作できることがわかります．
この形状操作を利用して，任意の形状から，別の任意の形状を削りとるような操作もできます．



上の図は，でっかい立方体から，螺旋状に削り取るような操作を行った結果です．
削り取る操作は，一般的にCSG(Constructive Solid Geometry)やブール演算（boolean）と呼ばれる操作のひとつです．
CSGやブール演算と呼ばれる操作は3つあり，それぞれ「和(union)」「差(difference)」「積(intersection)」と呼ばれています．それぞれ二つの形状を足し合わせた形状，一方からもう一方を差し引いた形状，二つの重なった部分の形状を意味します．
今回の図は差を表現しています．
内側のボクセルの集合Aから内側のボクセルの集合Bを引くという処理を行います．
差を式で表せば，A - B です．
同様に，和と積は，内側の集合Aと内側の集合Bを足す処理，集合Aと集合Bがどちらもが内側の部分を取り出す処理を行います．
和を式で表せば，A ∪ B，積はA ∩ Bとなります．
まぁ，簡単にこのような操作が行えるのがボリュームデータの魅力のひとつですかね．

ボクセル(Voxel)とは三次元のボリュームデータを扱うための最小単位で，画像でいうところのピクセル(Pixel，画素)にあたるものです．

大概どんなにものでも表面の内側に中身が詰まっている．
かわいいあの娘にも，ちゃんと中身がある．
ペラペラの面で構成されているわけではない，ちゃんと脳も筋肉も臓器もあるはず．
別に女だけじゃなくて，身の周りの家の壁や，板なんでも中身がある．
CGで体積があるもの，中身が詰まっているものを扱う時に，面しか定義されていなかったら，不自由極まりない．というか，面しか定義されていないのに，中身を扱えるわけがない．
たとえば，表面だけの大根を切っても，切り口はペラペラの面だけで，中身がないわけだ．これは現実離れしている．
たぶん，そういうのを問題に思った輩が，ボリュームデータを考えたんだと思う．
そういうボリュームデータを扱う方法の一つがボクセルです．

3次元空間内に，ボクセルと呼ばれる空間の要素が敷き詰まっていて，その要素で「もの」を定義します．
ボクセルの表現として，小さな立方体を格子状に敷き詰める方法があります．
他にも8面体や12面体などを敷き詰める方法もあるようですが，考えるのが面倒なのと実装が面倒なので，ボクは立方体を格子状に並べればいいんじゃないのって思っています．

ですから，立方体を格子状に並べて，ものを定義してみます．
xyzの三次元にボクセルを敷き詰めて，内側/外側の2値で形を定義してみようと思います．
内側というは中身，外側というはその「もの」の内側ではないということです．

何の形が表現に好ましいのかわからないので，とりあえず螺旋を作ってみました．
螺旋の媒介変数tを用いた関数は以下です．
x = a cos(t)
y = a sin(t)
z = b t
aとbはそれぞれ係数です．
螺旋の関数で，螺旋上のボクセルを内側とします．


うん，格子状のボクセルで，螺旋が表現されている．
せっかくだから，この螺旋を太らせてみよう．
螺旋に該当したボクセルからある距離内もボクセルを内側と定義してみよう．



太った．もう少し太らすと．



太った太った．
しかし，古い論文に出てそうなライティングしているなぁ．
まぁこういう古典的な色が好きなんですよ．

とにかく，格子状のボクセルを内外を定義するだけで形を作れるというです．
こうやって，形状を定義すると，切っても中身があるように見えるのだ．（次回，やってみるわ）
ただ見ての通り，立方体の格子だと，見た目がひどい．
まぁこれは立方体が大きいというのが問題のひとつかもしれないが，小さくしようとすると，それに依存してデータ量が膨大になるので，私のようなヘッポコなコンピュータしか使わない人には，難しい問題ですね．

2次元のボロノイ図では，ボロノイ境界は線分によってで表現でき，3次元では閉じた面で表現できます．
線分は2点を指定することによって定義できますが，面というのはややこしく，頂点の数が定まらず，三角形や四角形，などの多角形によって定義します．
これはCGで描画するときに結構な面倒なことだと感じています．
ですが，多角形を分割していくと最終的に三角形にすることができますから，多角形を三角形にうまく分割できれば，その問題はなくなります．
しかし，次はどのように三角形に分割するかという問題が出てきます．
一般的な手法はどのようなものなのでしょうか．ボクは知りません．

三角化の手法としては，ドロネー図などが応用できます．
あるボロノイ境界の点群（ボロノイ頂点）から三角形のみの図を作って，ボロノイ境界に乗っている三角形のみを取り出します．
その処理を全ボロノイ領域に行うと，ボロノイ境界上の三角化されたメッシュを得ることができます．
その三角形を描画すれば，3次元のボロノイ図をボロノイ境界によって表示させることができます．
例としてはこの画像です．

赤い点がボロノイ図の母点，青い点がボロノイ頂点，面がボロノイ境界で，中が見えるように透過してレンダリングしています．
しかし，この絵ではうまくいっているのかわかりにくい．
どうすれば見やすい絵作りができるか，模索中であります．

ボロノイ図の計算のためにqhullを用います．
www.qhull.org/

自分でコードを書いても良いかもしれませんが，高速化も面倒なことですし，ここは優秀なツールを使いましょう．
qhullのqhull.exeを用いていてボロノイ図を計算する際，次元と頂点数，頂点が定義された母点が必要です．
今回も思い切って簡単な母点で実験してみましょう．
ドロネー図の実験同様，2次元で4点，(1,0)(0,0)(0,2),(1,1)という点群で実験してみます．

2
4
1 0
0 0
0 2
1 1

これをtest.ptsという名前のテキストファイルとします．実際は，拡張子はなんでもいいです．
これからボロノイ図を計算します．
ボロノイ図のファイルは「test.vrn」という名前で保存することにします．
qhullでボロノイ図を計算するとき，オプションを指定してやる必要があります．
そのオプションはボロノイ図の「v」とOFF(オブジェクトファイルフォーマット)のための「o」，そしてファイル出力の「TO ファイル名」です．
この「o」のアウトプットは
・次元
・ボロノイ頂点数とボロノイ領域数，尾根の数
・ボロノイ頂点
・ボロノイ領域
となります．
最初の次元は入力が2次元なら2次元ですし，3次元なら3次元です．
2番目のボロノイ頂点数とボロノイ領域数，尾根の数がスペース区切りで並んでいます．
ボロノイ図の頂点とボロノイ領域の数はそのままです．
最後の尾根の数というのがわかりにくいのですが，ボロノイ図の場合，qhull側が定義した無限遠としている点の数です．
ボロノイ図には必ず無限遠の頂点が必要であり，その無限を指すために仮に定義しています．
この値が1の場合，ボロノイ頂点のうち，1番目の点が無限遠と定義されているようです．
3番目の項目のボロノイ頂点というのは，座標が並んでおり，一行につき，一つの頂点が定義されています．
4番目の項目のボロノイ領域は3番目の項目で定義されたボロノイ頂点を指すインデックスで定義されています．
ボロノイ領域が定義されている列の1番目の要素は，ボロノイ領域の頂点の数が記されています．
それ以降は，ボロノイ頂点のインデックスになります．
実際に先ほど定義したtest.ptsで計算させます．
そのときのコマンドはこのようになります．

qhull v o TO test.vrn < test.pts

このコマンドによってtest.vrnが作成されます．

2
3 4 1
-10.101 -10.101
   0.5    0.5
     0      1
2 0 1
3 2 0 1
2 0 2
3 0 1 2

最初の列が2次元を指し，次に3頂点，4領域，無限遠1，頂点3つの座標，領域4つのインデックスとなっています．
ちなみに領域の数と入力の母点の数は必ず同じになります．
その上，入力の頂点に対応したボロノイ領域が同じインデックスとして計算されています．
つまりは，最初の母点に対応したボロノイ領域はボロノイ領域の最初に定義されているということです．

無限遠を抜いて描画するとこのようになります．
母点を黒，ボロノイ頂点を赤，ボロノイ辺を緑としています．



これは見ての通り，ほとんどが無限遠のため描画しても1本しか表せません．
もっと多くの点を描画すると，このようになります．