FBX解読③ 配列型〜配列展開まで

http://qiita.com/gshirato/items/3d3041b8abbca13b769c
の続き

#やりたいこと

- FBXデータのバイナリデータからUnity上で描画するために必要な情報を抽出し、再現。

#扱うデータ

Blender上でワンクリックでCubeを作ってFBX形式でエクスポート。

##基本情報(常識等)
頂点:８個
描画に使う頂点:２４個(四角形→4×６(面))
頂点法線:２４個




#配列型

##構造

>DataLength:圧縮前の配列の長さ
Encoding:圧縮の有無(0:無,1:有)
CompresseLength:圧縮後の配列の長さ(Dataの大きさ)
Type:配列型
Data:実際の配列
**CompressLengthは圧縮されていない場合、[配列長さ×データ要素の大きさ]になる。*

##例

###頂点(Vertices)

>DataLength: 24
Encoding: 1
CompressedLength: 84
Type: d
Data: 詳細は後述

```
[0] (1.0,1.0,-1.0)
... 
[7] (-1.0,1.0,1.0)
```

###(ポリゴンごとの)PolygonVertexIndex


>DataLength: 24
Encoding: 0
CompressedLength: 96
Type: i
Data: それぞれ上のVerticesのインデックスを指している

```
 0, 1, 2, 3,
 4, 7, 6, 5,
 0, 4, 5, 1,
 1, 5, 6, 2,
 2, 6, 7, 3,
 4, 0, 3, 7
```

#ポリゴンをどう構成するか

ここで、メッシュの多角形の種類について考える。

- 三角形の場合：     

 
```
 __
|／| //頂点数→(3*2)*6 =36
 ￣
```

- 四角形の場合：
頂点数→4*6=24

ここから、四角ポリゴンから成っている立方体だとわかる。
しかし、これでは応用が効かない。

じつは`PolygonVertexIndex`を4byte×配列数でみると

```
00 00 00 00  01 00 00 00  02 00 00 00  fc ff ff ff // 0 1 2 ?
04 00 00 00  07 00 00 00  06 00 00 00  fa ff ff ff // 4 7 6 ?
... 
```

というように決まった周期で未知の数字を発見できる。(数字はリトルエンディアンで読むことに注意)

https://stackoverflow.com/questions/7736845/can-anyone-explain-the-fbx-format-for-me を見ると

>
The one with the negative value represents the last vertex indeed.

>To find out witch vertex this is, you have to negate it and subtract 1 from that value.

>For example, -4 represents 3 ((-4)*(-1) - 1)

とあり、各ポリゴンの最終要素であることがわかり、実際の数字はその`数字×(−1)-1`もしくは16進数の補数ほ取ることで求められる。
つまり 
`fc ff ff ff → 03 00 00 00 //3`
や
`fa ff ff ff → -7 * (-1) -1 = 7 - 1 = 6`
で求められる。

###Edges


>DataLength: 12
Encoding: 0
CompressedLength: 48
Type: i
Data: それぞれ**PolygonVertexIndex**のインデックスを指している(略)

###頂点法線・Normals
>DataLength: 72
Encoding: 1
CompressedLength: 96
Type: d
Data: ポリゴンごとの頂点法線なのであとで計算必要(略)

##Encodingされている場合
Doubleの配列型`d`は圧縮され、比較的小さいIntの配列型`i`はそのまま表示されている。

FBX SDKで使われる圧縮はzlibを使って行われる。(https://wiki.rogiken.org/specifications/file-format/fbx/7400/syntax/binary/ table 6.より)


#zlib形式圧縮

参考：https://tools.ietf.org/html/rfc1950

この圧縮方式は可逆的なためデータと方法さえしっかりしていれば理論上は圧縮前の元データを得ることができるはずである。

##メタデータ
zlib形式の圧縮では必ず最初に2バイトのメタデータがつく。

Verticesの配列Dataを2進数表示で見てみると

`0111 1000 0000 0001'
ちなみにここの2バイト分は素直に上から読んで良い。

ここのメタデータはCMF(圧縮方法) とFLG(フラグ)の二種類に分けることができる。

```
   0   1  (byte)
 +---------+---------+
 |   CMF   |   FLG   | 
 +---------+---------+
 |CM |CINFO|CHCK|D|Lv| 
 +---------+---------+
 |7654 3210|7654 3210| 
 +---------+---------+
 |0111 1000|0000 0001| 
 +---------+---------+
```
(byteは左から0,1,2,...と読むがbitは右から読んでいくことに注意）

###CMF
- 0−3バイト→CM:圧縮方式
基本8で、Deflate形式の圧縮を示す

- 4-7バイト→CINFO:圧縮情報
CMが8のときのみ定義され、基本7。圧縮時のスライド窓とやらの大きさを示すらしいが解凍時には特に意味のない情報。とんでもない数字に成っていないことだけ確認できれば良い。

###FLG

- 0-4バイト→FCHECK:検算用データ
このデータ自体には意味がないが`CMF*256+FLG`が31の倍数に成るように調整されている。
- 5バイト目→FDICT:プリセット辞書
圧縮時に使う符号の対応表が入るが殆どの場合用意されておらずここでも使わない。
- 6-7バイト→FLEVEL:圧縮レベル

>   0 - compressor used fastest algorithm
1 - compressor used fast algorithm
2 - compressor used default algorithm
3 - compressor used maximum compression, slowest algorithm

らしいです。ここでは0、一番速いやつ。

CMF * 256 + 1 = 30721 → 30721 % 31 = 0となり正常なデータであることがわかる。

###プリセット辞書
FDICTが1の場合はプリセット辞書が入るが今回は無し。

##実データ読み込み

こちらのサイトに大きくお世話になりました。


>http://darkcrowcorvus.hatenablog.jp/entry/2016/09/23/195644

>https://www.slideshare.net/7shi/deflate

zlibで使うDeflate圧縮とはハフマン符号化とLZ77データ圧縮アルゴリズムを組み合わせたもの。

###ハフマン符号化
出現する文字パターンのうち出現頻度の高いものを文字数の少ない符号で表現する　
プレフェックス符号化が採用されており、上から順にバイナリを読んでいけば正しく符号を読むことができる（基本的に）
###LZ77

文字列のパターンを記憶し、同じパターンを発見すると一致する文字長と現在の位置からどれくらい離れているかを表示する。

圧縮データは1つ又は複数の*ブロック*から構成されていて、各ブロックは3bitのヘッダを持つ。

中のデータの読む順番は間違えやすい。
http://darkcrowcorvus.hatenablog.jp/entry/2016/09/27/222117
を参考。

ブロックタイプは、
- 無圧縮
- 固定ハフマン
- カスタムハフマン

の3つである。

今回使ったfbxデータからは固定ハフマンしか発見できなかった。
固定ハフマンは出現頻度を無視して予め値と符号の対応値がきまっており、出現した文字に合わせて対応表を書かなくて良いためシンプルだが裏を返せば出現パターンが決まっていたり大きな配列が圧縮されている場合は圧縮効率としては低くなる可能性がある。

#次回

次回は固定ハフマンによる展開。
http://qiita.com/gshirato/items/4aa85fe31e8d48574d8c