マニュアルを読むときに突然出てくるかもしれないプログラミング用語（ハッシュについてのおまけつき）

2014/9/9

Tag: maya,ハッシュ,用語

こんにちは。TD室の田村です。

CGソフトを使うのはデザイナーですが作っているのはプログラマーなのでマニュアルを読んでいるとたまにプログラミング用語が出てきたりします。今回はマニュアルにいきなり出てくると戸惑いそうな用語を挙げてみたいと思います。あくまでマニュアルを読む時に困らないための解説なので厳密性、正確性はあまり重視していません。

評価：
　　　計算実行し、結果を出すことです。例：ノードを評価する

コンテキスト：
　　　これは非常に紛らわしい用語です。いくつかの意味で使われています。
　　　　　　1 最も基本的な意味である「文脈、話の流れ」。
　　　　　　2 実行時の環境、状態。「状態」と読み替えると大抵は意味が通ります。
　　　　　　　　　例：このノードはレンダリングコンテキストでしか評価されません。
　　　　　　　　　意味：このノードはレンダリング中以外では計算されません（なので間違った結果を返します）。
　　　　　　3 Maya用語。APIではSelectツールなど「ツール」のことを「コンテキスト」と呼んでいます。

ネームスペース（名前空間）：
　　　同じ名称が異なる２つ以上の意味で使われ、名前がかぶらないようにそれぞれの名前をグループ化し、別のグループでは同じ名前を使っても良いようにするものです。

オーダー：
　　　意味的には「桁」。精度だったり計算量だったりします。

ガベージコレクション：
　　　残しておいても意味のない不要なものを削除する作業です。

DAG：
　　　Directed acyclic graphの略です。ノードとエッジからなるグラフで、循環がないものです。イメージを持つにはDirected acyclic graphで画像検索するのが一番いいでしょう。MayaのDAG階層の語源です。MayaのDAG階層では、親が複数の子供を持ったり、子供が複数の親を持ったりしますが、あるノードの子供を辿っていっても自分自身のノードに出くわすことは決してありません。親ノードから子ノードにエッジが存在すると考えるとDAGのイメージになります。

スコープ：
　　　あるもの（プログラムでは変数など）が存在する範囲を意味します。あるスコープ内に存在するものはスコープの外では使うことができません。

シリアライズ：
　　　キャッシュなどの目的のためにデータを変形すること（かなり不正確な表現ですが）。

同期：
　　　通信などの処理終了待ちをすること、「非同期」だと一つの処理を待たないで次に進みます。処理待ちで停止している状態をブロックされた状態と言います。

パース(Parse)：
　　　言葉を解析すること。

トラバース：
　　　データ構造の全てに渡って辿っていくこと。

参照：
　　　参照は実データを指すタグのようなもの。「ポインタ」も同じような意味で使われることがあります。例：Mayaのインスタンスはそれぞれにジオメトリデータのコピーを持たず、ジオメトリへの参照を保持します。

遅延(deferred, lazy)：
　　　遅延処理、遅延評価、遅延実行など。どれも「必要になったときに初めて行う」ということです。Mayaのノードは必要になったときに初めて計算を行います。

ハッシュ：
　　　あるデータを変換し、そのデータを表すサイズの小さい数値や文字のこと。ハッシュは様々な用途で用いられますがデータが変更されたかどうか確認するために用いられることが多いです。例えばNukeでは自分のノードのknob、及び全ての上流ノードの状態を表すハッシュを作成、利用します。ハッシュ値が変わらなければ自ノード、上流ノードの状態が変わっていないことを表すので以前に作成したキャッシュを使うことができます。ハッシュ値が変わっていればそのキャッシュを使うことができません。またキーを与えると値を返すデータ構造（2つの列からなる表を考え、最初の列のある項目を渡すと対応する２つ目の列の項目が返ってくるのを想像するといいでしょう。最初の列がキー、２つ目の列が値です）はハッシュを用いて作られることが多いのでこの構造自体をハッシュと呼んでしまっている場合もあります。

——————————————————————————————-
ハッシュについてのおまけ

今回はハッシュを用いて遊んでみましょう。お題は「2つのMayaメッシュが同一かどうかをハッシュを用いて高速判定する」です。

通常の方法では

a) 2つのMayaメッシュのデータを取り出す。
b) それぞれについて、一つずつ値を比較する

という方法がとられるかと思います。それでも構わないのですが、それぞれのメッシュが別ファイルにあった場合、例えばバージョンの異なるキャラモデルの入ったシーンファイルが2つあり、両方を開けないといけない場合などはシーンを2つ開けると遅くなってしまいます。予めシーンの中に入っているメッシュのハッシュ値を計算、別ファイルとして記録しておけば、もう一方のファイルのみを開いてキャッシュ値が変わっていないか比較、判定することができます。まとめると

古いバージョンのシーンファイルについて

a) 各メッシュのキャッシュ値を計算
b) シーンファイルの保存時にキャッシュ値を別ファイルとして保存

新しいバージョンのシーンファイルと比較したいとき

c) 新しいバージョンのシーンファイルを開く
d) 各メッシュのキャッシュ値を計算
e) b)で保存したキャッシュ値と比較
　　　e-1) 異なっていればメッシュは変更されている
　　　e-2) 同一ならば恐らくメッシュは変更されていない（後述）

となります。プログラミングの手順は

– メッシュのデータ（頂点位置、三角ポリゴン情報、ノーマル情報）を取り出す
– データをバイト列としてハッシュ化
– 文字列化してコマンドプラグインの結果として出力

です。今回はUV等は考慮していませんが付け加えるのも難しくはないでしょう。
ハッシュ関数はSHA256を使っており、Crypto++ (http://www.cryptopp.com/)を用いました。ライセンスはBoost Software License 1.0と緩く、クロスプラットフォームなので使いやすいライブラリです。
ではコードを。

#include <vector>

#include <maya/MSimple.h>
#include <maya/MGlobal.h>
#include <maya/MDagPath.h>
#include <maya/MFnMesh.h>
#include <maya/MSelectionList.h>


#define CRYPTOPP_DEFAULT_NO_DLL
#include "dll.h"


DeclareSimpleCommand(genSHA256, "Digital Frontier", "1.0");

MStatus genSHA256::doIt(const MArgList& args)
{
	//対象とするメッシュのMFnMeshを得る。
	MStatus status;
	MString mstrObjectName = args.asString(0);
	MSelectionList selList;
	status = selList.add(mstrObjectName);
	if (!status)
	{
		MGlobal::displayError("Could not find the object");
		return status;
	}
	MDagPath dpath;
	selList.getDagPath(0, dpath);
	MFnMesh fnMesh(dpath);
	unsigned int numVertices = fnMesh.numVertices();

	//ハッシュ計算準備。
	byte digest[CryptoPP::SHA256::DIGESTSIZE];
	CryptoPP::SHA hash;

	//頂点位置データの取得（transformは反映されない）。
	const float* vertexData = fnMesh.getRawPoints(&status);
	hash.Update(reinterpret_cast < const byte* > (vertexData), numVertices * 12);

	//法線データの取得。
	const float* normalData = fnMesh.getRawNormals(&status);
	hash.Update(reinterpret_cast < const byte* > (normalData), numVertices * 12);

	//ポリゴンデータの取得。
	MIntArray triangleCounts;
	MIntArray triangleVertices;
	fnMesh.getTriangles(triangleCounts, triangleVertices);
	std::vector < int > polyVec(triangleVertices.length());
	int* polyData = polyVec.data();
	triangleCounts.get(polyData);
	hash.Update(reinterpret_cast < const byte* > (polyData), triangleCounts.length() * sizeof(int));
	triangleVertices.get(polyData);
	hash.Update(reinterpret_cast < const byte* > (polyData), triangleVertices.length() * sizeof(int));

	//ハッシュ値計算。
	hash.Final(digest);

	//文字列化してコマンドの結果にする。
	char hexRep[CryptoPP::SHA256::DIGESTSIZE + 1];
	sprintf(hexRep, "%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x",
		digest[0], digest[1], digest[2], digest[3],
		digest[4], digest[5], digest[6], digest[7],
		digest[8], digest[9], digest[10], digest[11],
		digest[12], digest[13], digest[14], digest[15]);
	setResult(hexRep);

	return MS::kSuccess;
}

使ってみましょう。プラグインをビルド、MayaでロードしてpPlane1を作ります。MELコマンドgenMd5 pPlane1;を実行すると

genMd5 pPlane1;
// a73d2c824d116f481318dd2553b1723a //

のように結果が出力されます。

複製してpPlane2を作り、同様にコマンド実行すると

genMd5 pPlane2;
// Result: a73d2c824d116f481318dd2553b1723a //

変わっていないことがわかります。

次にpPlane2の頂点を適当に移動させ、再度実行。
genMd5 pPlane2;
// Result: 56476ec1fa73057dc777c322b5b063ca //

変化していることがわかります（MFnMesh::getRawPoints()を用いているのでtransformには反応しません）。

同様にノーマルを編集しても値が変わります。

最後に3つほど注意点を。

– ハッシュのユニーク性について

ごく稀に異なる2つのデータ（この場合はMayaメッシュ）から同じハッシュ値ができることがあります。これをハッシュの衝突(collision)といいます。ハッシュのサイズが有限（SHA256では256ビット）なのでこれは仕方のないことです。ハッシュ関数にはMD5やMurmurHash3、CityHashなど様々ありますが、ZFSというファイルシステムでSHA256が使われていたためそれに習いこちらでもSHA256を使いました。ZFSにはdeduplicationといってファイルを保存するときに既に保存した別のファイルと一部重複しているデータがないか探し、もしあればその部分は新たに保存せずデータを共有するという機能が用意されています。やはり衝突の可能性があり、衝突した場合は（衝突した場合に全データ比較チェックするオプションをonにしない限り）データが破損するのですが、ハッシュ衝突の可能性がハードディスクの故障によるデータ破損の確率よりも低いという理由で採用されているようです。今回はZFSよりも更に安全な利用方法（詳細を知りたい方は「誕生日 パラドックス」で検索）なので大丈夫だと思いますがそれでも気になる方は稀に衝突しても構わない利用方法に限定するか、衝突した場合に本当に一致しているか全データ比較をするのが良いでしょう（利用用途が限られてしまいますが）。

– 誤差に注意

上のコードでは1ビットでも異なると全く異なったハッシュが作成されるため、僅かな誤差が入っていてもメッシュの変更が検出されてしまいます。実際頂点を移動させ、undoすると元とは異なったハッシュになってしまいました。undoではごく僅かな誤差が入るのでしょう。今回試した限りでは大丈夫でしたがセーブ、ロード時に誤差が入らないかも確認が必要でしょう。データを取り出してからハッシュを計算するまでに何らかの計算が入るときは要注意です。Maya内部で計算が入るものは何をしているかわからない（マルチスレッドでの並列処理に伴う誤差など）ので避けた方が無難です。またdoubleの値は同じコードでも環境によって実行する度に僅かに異なった結果になることがあります。例えばdouble値を無理にfloat化したりすると計算誤差が入りそうです。double値のデータは固定小数点化し誤差が入らないくらいまで丸めてハッシュ化するなどの工夫が必要になるでしょう。

※免責事項※
本記事内で公開している全ての手法・コードの有用性、安全性について、当方は一切の保証を与えるものではありません。
これらのコードを使用したことによって引き起こる直接的、間接的な損害に対し、当方は一切責任を負うものではありません。
自己責任でご使用ください。