じぇのサイト

ボロノイ図(Voronoi diagram)は，母点(site)からボロノイ領域(Voronoi region)を計算し，その堺をボロノイ境界(Voronoi edge，2次元上ではボロノイ辺)として構成した図です．
ある母点が最も近くにある領域をある母点のボロノイ領域として定義しています．
また，ボロノイ境界の頂点をボロノイ頂点(Voronoi vertex)としています．

ボロノイ図は，ドロネー図同様，2次元以上ならば任意の次元で定義できます．
しかし，2次元平面上に分布された母点から3次元のボロノイ図は計算することは難しいです．
2次元上に母点がある場合，すべてのボロノイ領域が3次元方向に無限になるため，ボロノイ図をボロノイ頂点として構成できません．
頂点の座標が定義できないため，コンピュータでは2次元の母点からは3次元のボロノイ図は計算できません．

とにかく，ボロノイ図を見てましょう．
このうさぎの頂点を母点とし，ボロノイ図を計算してみます．
色は表裏がわかりやすいように，6方向から別の色の光が当たるように光源を設定しています．


これが母点となるモデルです．



これがうさぎのボロノイ図です． 3次元の母点だとこのようになります．
ボロノイ境界が面ですから，描画したとき，奥が見えなくなり，何がなんだかわかりません．
ということで面の辺のみを描画してみました．

/*画像が重すぎるため削除しました*/
/*意味がなさすぎるので，もう少し意味ありげなときにスタンフォードバニーを使います*/

まぁ結局同じようなものです．

不満が残るかもしれませんが，これがボロノイ図です．

www.qhull.org/

qhullのqdelaunay.exeという実行ファイルに点群データ入力すると，その点群からドロネー図を構成して出力することができます．
しかし，このときオプションで設定する必要があります．
このオプションに関しては，qhullサイトのqdelaunayの項目に適度に書いてあります．
http://www.qhull.org/html/qdelaun.htm

今回は思い切って簡単にいきましょう．
点群の座標をqdelaunayに入力し，その点群のドロネー図を頂点のインデックスで出力させましょう．

qhullの仕様だと，点群の定義は「次元」「点の個数」「座標」が必要で，入力するときもその順である必要があります．
座標は頂点を一行に一頂点とし，各次元の値はスペース区切りで記述します．
2次元で4点，(1,0)(0,0)(0,2),(1,1)という点群だと

2
4
1 0
0 0
0 2
1 1

となります．これを「test.pts」という名前でファイルに保存します．
このときの拡張子はなんでもいいです．

三角化したドロネー図を返してほしい場合のオプションは「Qt」で，ドロネー図のドロネー領域の数とその頂点のインデックスだけを返してほしい場合のオプションは「i」です．
それに，結果を表示させるために「s」のオプションをつけます．
これら「Qt i s」によって，入力に対して，領域数とそのインデックスを表示させることができます．
表示されるものをリダイレクトでファイルにそのまま保存すれば，インデックスデータが入ったファイルが作れます．
入力に関してはパイプを使ってもよいと思いますが，ファイルに保存してあるので，入力のリダイレクトを用いると便利だと思います．
今は実験的に出力されたデータを「test.dln」という名前を付けます．
コマンドは次のようになります．

qdelaunay Qt s i < test.pts > test.dln

リダイレクトでtest.ptsを入力し，表示される内容をリダイレクトでtest.dlnに保存しています．
これを行った結果test.dlnは次のようになります．

2
0 3 1
3 2 1

これがtest.ptsのドロネー図です．
実際に描画してみましょう．



赤い線がドロネー図のエッジです．
これは2次元ですが，3次元にも同様の方法で適用できます．その証拠が前回の記事の図にまります．

私がドロネー図に出会ったのは学部2年のころで，その当時はさっぱり利用用途がわからなかった．
ドロネー図は与えられた母点から三角形を計算するために使われることが多いような気がします．確かに図の構成要素は三角形のみなのですが，ただ単に三角形を作っていくわけではありません．
2次元上の場合だと，与えられた点群のうち3点を結んで三角形にしたとき，その三角形の外接円の内側に頂点以外の点が入らないように三角形を計算していきます．そのように構築した図が2次元上のドロネー図となります．
3次元上だと四面体の外接球の中に四面体の頂点以外の点がないように，四面体を構築した図がドロネー図となります．
うさぎで見てみましょう．


これが入力となります．
そして，ドロネー図にした結果が次のこれです．

みごとに梱包されたようになっています．
面で区切られているため，当然のように面しか見えません．
この中にはぎっしりと四面体が敷き詰められています．

四面体の辺のみを描画したのこれです．



中は見えるようになったけど，数が多すぎてわけわからん状態です．
しかし，これがドロネー図です．

.objファイルから読み込んだデータをどのように持とうが構わないと思いますが，ボクの場合は前回お話した通りに持っています．
今回はどのようにファイルから読みだしていくかを話していこうと思います．
ボクのプログラムの書き方はゲッターとセッターをしっかり書いてしまうタイプなので，まともな方だとは思っているのですが，このような記事を書くときは不便でして，関数の説明を一からしなければなりません．しかし，そんな説明をするほど元気ではないので，簡単にどのような手続きをとればよいのかを記述します．
前回の記事で記述しているように.objファイルは一行に一頂点，一面を定義しているので，ファイルの読み込み時に一行ずつ読み込んでいけばよいのです．
これには，ファイルの入力処理がわかっていればよいので，本か他のサイトで調べてください．
ちなみにボクはVC++でコードを書いており，ファイル周りに関してはc++よりcの関数のほうが使いやすいと思っています．fopen_s関数でファイルポインターを掴んで，fgets関数で300文字くらいを指定して，一行読み込んでいます．
次に，一行を読み込んでスペース区切りで切りだされた文字を見ます．その文字が「v」「vt」「vn」「f」なら気にすることにしましょう．それ以外は「#」か「g」か「mtllib」ですので，今は無視しておきましょう．とくに「#」から始まる行はコメント行なので永年無視です．
vの場合は，頂点座標として格納する．
vtならば，テクスチャ座標として格納する．
vnならば，法線として格納する．
fならば，面として格納する．
と言った感じに場合わけの処理になります．
このとき，前回の説明で用意してあるフラグを立ててやれば，描画処理の時にテクスチャ座標がないのか，法線がないのかわかりやすいので，楽です．
「v」「vt」「vn」ならば一行読み取った文字列を全てスペース区切りにして行末まで送っていきます．これでこの行の読み込みは完了するはずです．

「f」の行はちょろっとひねりが必要になります．
スペース区切りで参照している頂点の数はわかるのですが，問題は切り出したあとで，スラッシュ区切りの部分です．
cで用意されているstrtok_sを区切り文字を用いて「a//c」のようにスラッシュが二重に続いたものを処理した場合，スラッシュが一度で２つ飛ばされて処理されてしまいます．
ですので，文字を一文字見ていってスラッシュ区切りを実装するしかありません．
ボクはトークンの切り出し関数mystrtokを作って，スラッシュを一文字ずつ抜き出していました．

char *mystrtok(char *s, char *t)
{
    static char buf[50];
    static char *headp;
    char *tailp;
    char *p;
   
    if (s != NULL) {
        strcpy_s(buf, s);
        headp = buf; /* headpは先頭を指す */
    }
    //sがNULLでかつheadpがNULLの場合，これは終点に達しているということ
    if(headp==NULL){
        return NULL;
    }
    //headp文字列からtを検索
    // tailpは区切り文字を指す
    tailp = strstr(headp, t);
   
    //区切りがない場合，最後という判定でこのときのheadpを返す
    if (tailp == NULL){
        p = headp;
        headp = NULL;
        return p;
    }

    //このときtailpがheadpと同じ場合，区切り文字が連続に続いているということでNULLを返す
    if(tailp==headp){
        headp = tailp + strlen(t); /* 次の頭 */
        return NULL;
    }

    *tailp = '\0';
    p = headp;
    headp = tailp + strlen(t); /* 次の頭 */
    return p;
}

この関数my_strtok()は引数に，区切りたい文字列sと，区切り文字列tとします．簡単に言うと，標準ライブラリのstrtok()と同じ使い方です．
最初に引数に入れた区切りたい文字列sは，先頭から区切り文字列tまでを切り出して返り値として返します．
区切りたい文字列sから次のトークンを得たいときは，NULLをsに入れ，区切り文字tを入力します．すると次のトークンが返ってきます．
今の場合，スラッシュ区切りにしたいので，面のスペース区切りしたあとの文字列と"/"を引数として指定します．
区切りたい文字列sが「200/201/202」の場合，mystrtok(s,"/")とします．この返り値は200となります．
次に，次のトークンがほしいので，mystrtok(NULL,"/")とします．すると，201が返ってきます．
最後のトークンがほしいので再度mystrtok(NULL,"/")とします．もちろん，202が返ってきます．

仮に，区切りたい文字列sが「200//202」だったら，標準ライブラリのstrtok()では，二重のスラッシュ//を1区切りとしてみなします．しかし，mystrtok()では，/毎に区切っていきます．
ですから，mystrtok(s,"/")，mystrtok(NULL,"/")，mystrtok(NULL,"/")とした場合，200,NULL,202と返します．
区切りたい文字列が最後まで行くと，それからは常にNULLしか返さなくなります．

これで取り出して，メモリに格納していけば，面情報を得ることができるので読み込み終了となります．

前回の話でなんとなく.objファイルを読み込むモチベーションを感じてもらえたことでしょう．
さて，じゃ読み込みましょうかね．
先に言っておきますが，ここではcもしくはc++で開発します．ボクみたいな面倒くさがりさんは，開発言語はcもしくはc++くらいしか使う気がありません．型を定義しないような言語はデバッグが面倒なことが多いので使いません．

読み込む前に，まず.objファイルがどのような構造なのかを知らなければなりません．
ということで調べましょう．
「cg objファイル フォーマット」とかで検索すれば，なんか出てきます．
で，だいたいそれで正解です．検索ワードにcgを入れないと，cのコンパイルした時にできるようなobjファイルのことについて出てきちゃいます．今はそんなのを知ってもしょうがないですからね．

まぁとにかく調べたらどのサイトも以下のようなことが書いてあると思います．
「v」は頂点x y z
「vt」はテクスチャ座標
「vn」は法線x y z
「f」は面
「g」はグループ
ほかにもマテリアルとか何とかってあるかもしれませんがその辺は無視で．

これらの記号を見ても，初見だと意味わからないですよね．
ボクもそうでした．
これはどういう意味かというと，行のはじめにvがついていた場合，その列は頂点のxyzを記してあるということです．
.objファイルの性質として，一行に１頂点，もしくは１面を定義します．

v 1 0 0

これは{x,y,z}={1,0,0}という頂点を指しているということです，スペース区切りでxyzを並べています．
つぎに，vtですがこれはテクスチャを貼り付けるための座標が記されます．

vt 1 1

これはテクスチャ座標の(1,1)を指します．
そして，vnは法線です．

vn 0 0 1

この場合，法線ベクトルが(0,0,1)だということです．
ここまでが座標に関することです．
なんとなくわかってきたでしょうか．
これらv,vt,vnは座標に関する情報の定義でしたが，これだけではポリゴンメッシュとして定義できません．
面の定義が必要です．
面はfで始まる行で定義されています．しかし，座標に関する定義とは大きく違う書き方をしています．

f a1/b1/c1 a2/b2/c2 a3/b3/c3 a4/b4/c4 ...

このような書き方になっています．
スペース区切りでa/b/cが並んでいます．
それぞれaは頂点座標のインデックス，bはテクスチャ座標のインデックス，cは法線のインデックスです．
a/b/cが3つ並んでいた場合，それは三角形を示します．
4つ並んでいると四角形，5つだと五角形ということになります．
インデックスは最初に定義されたvには1番がつけられ，それ以降は1ずつ増えた番号与えられていきます．
a/b/cはスラッシュ区切りになっており，場合によってはテクスチャ座標が抜かれたり法線が省略されたりします．
テクスチャ座標が参照されないような場合は，

f a1//c1 a2//c2 a3//c3 a4//c4 ...

となっています．
必ずしもスラッシュの数が2つあるわけではなく，

f a1 a2 a3 a4 ...

のように省略される場合もあります．

gのグループについてはgがついたあとの面はグループ化されるということです．
それだけです．

以上がフォーマットについてでしたが，比較的簡単に読み込めそうですよね．
頂点の座標などのv，vt，vnは簡単ですよね．
一行を読み込んで，一文字目を見て，それ以降を単純にスペース区切りで読み込めばよいだけですからね．
しかし，ちょっと厄介なのは面の読み込みです．
何個の頂点で面を構成しているかのかを示していないので，リスト構造や配列を用意してその中に入れてみて，数を数えなければなりません．
しかも，面の各頂点の情報は頂点，テクスチャ座標，法線ベクトルをそれぞれスラッシュ区切りで指しています．
考えるだけでも面倒ですよね．
面倒なのですが，書いてしまえば簡単なものです．

ボクはデータをまとめて持っておくのが好きなタイプですから，ファイルから抜き出したデータを一括して管理しておきます．
ですから，クラスを作って，その中に頂点座標やテクスチャ座標，法線ベクトル，面の情報を格納していきます．
また，面の情報は面の情報としてクラスとします．
それぞれをMeshDataクラスとFaceIndexクラスと名付けました．
この二つのクラスで400行くらいしかないので，短いのですが，この記事にべた張りするとあほみたいに長くなるので，何か別の方法で掲載します．いや，面倒になったらしないかも．
とにかく，これらのクラスは以下のようなメンバー変数を持ちます．
MeshDataクラスのメンバー変数は，

bool vertexF;
int verticesN;
double** vertices;

bool textureF;
int textureCoordN;
double **textureCoords;

bool normalF;
int normalsN;
double **normals;

bool faceF;
int facesN;
FaceIndex **faces;

としました．実は他にもいろいろ持たせてあるのですが，今は面倒なのでこれだけで．
vertexFやtextureF，normalF，faceFはそれぞれそのデータが有効なのかを示すために用意しました．
verticesNとverticesはそれぞれ頂点の数と頂点の座標，textureCoordNとtextureCoordはそれぞれテクスチャ座標の数とテクスチャ座標，normalsNとnormalsはそれぞれ法線ベクトルの数とベクトルです．
facesNとfacesはそれぞれ面の数と面の情報です．

FaceIndexには上で用意したvertices，textureCoordとnormalsのインデックスが格納されます．
FaceIndexクラスのメンバー変数は，

int faceN;
int *verIndex;
int *texIndex;
int *norIndex;

とし，faceNはこの面が何頂点で構成されているか，verIndexとtexIndex，norIndexはそれぞれvertices，textureCoordとnormalsのインデックスが格納されています．

用意したこれらに.objファイルから読みだしたものを格納していけば読み込み終了となります．
読み込みの関数はまた次回ということで．