LoginSignup
5
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@subrutm

[3D Animation] DirectX8の時代にゼロから創ったMeshのロードから3Dアニメーションエンジンのエンジン開発した際のノウハウやTips まとめ Part2

Last updated at Posted at 2016-06-30

今回は、MeshFile(X File)のロードをメインの内容とします。
構成図の中で言う、緑色のブロックです。

2回目の話.png

私のエンジンは、マップエディターや3Dアニメーションの入ったアクションゲームの作成を一人で1年という期間の制約の中で作ったので、DirectXのAPIを利用してロードしています。

この話は、今の時代には無用の産物なので話しません。
もう少し汎用性のある話をしましょう。

そこで今回は、ファイルのパーサーアルゴリズムについて解説します。
HTMLやXMLなど、Fileにデータを保存する際に必要なるパーサーアルゴリズム。
これらは、AIなどの応用やパース系のアルゴリズムにも応用でき活用範囲が広いと考えています。
パースアルゴリズムの考え方を身に着けて、スキルアップに繋げてください。

パースアルゴリズムの考え方について

パースアルゴリズムの基本は、区切り文字(キー文字とする)を使った構文ルールを決めて、そのルールに従って順番に解析することです。
X Fileのロードがテーマなので、X Fileの構文を基にパースアルゴリズムを簡単に試作してみましょう。

まず、文字列解析するには一定のルールで作った構文を区切り文字などで分解できる仕組みが必要です。
どんな構文でも共通で必要になる部分なのでこちらの実装を考えましょう。

以下の、構文を例に考えてみましょう。
区切り文字.png
①は、大枠のグループカテゴリを表しています。
②は、大枠のグループ名を表しています。
区切り文字は、半角スペースで区切り、括弧は文字の範囲として扱うものとする。

まず、関数の外枠を考えます。
関数と入力・アウトプットの関係性は、以下のようなイメージになります。

関数のイメージ.png

すなわち、c言語の構文で表現すると、
void parseLine(const char* pBuffer, unsigned int nBufferLength, char keyBuff, std::vector<char*>& result)
std::vectorは、複数の文字列を動的変動する個数で格納したいので、動的配列アルゴリズムのvectorを選択しました。

区切る時に、まず『どこ』から『どこ』までを切り取るか考えますよね？
それが、最初のステップです。

『半角スペース』を区切り文字として2つの文字列を分離してみましょう。
シーク移動.png
矢印は、シーク(参照位置)を表現しています。
ロジックをコードにすると以下のイメージになります。

ParseTest.cpp
	int StartPos = -1;
	unsigned int count = 0;
	for (unsigned int i = 0; i < nBufferLength && (pBuffer[i] != '\n'); i++) {
		if (pBuffer[i] == keyBuff) {
			if (count) {
				// 何らかの文字があるのでバッファを動的に確保してコピーする

				char* newData = new char[count + 1]; // +1は、null文字分
				memset(newData, 0, count + 1);
				strncpy(newData, pBuffer + StartPos, count);

				result.push_back(newData);

				StartPos += count + 1;
				count = 0;

			} else {
				// 有効な文字ではないので初期化する
				StartPos = -1;
				count = 0;
			}
		} else {
			// 最初の有効な文字にシークが行ったので、最初の位置の登録と
                        // カウントを開始する
			if (StartPos < 0)
				StartPos = i;

			count++;
		}
	}

※'\n': 改行文字です。
※ あとは、関数を抜ける前に、最後の1括りをコピーして追加することを忘れないことが大事です。
※ コピーする部分は共通なのでinline関数にするなどして冗長性を省くと良いと思います。

グループ別にパースアルゴリズムを作る

以下のようなデータ構造を考えます。

test.x
FRAME [Guild]
{
  MESH
  {
    3,
    5.1236, 4.62514, -1.947634,
    0.5826, 4.14551, -14785456,
    5.1236, 4.62514, -1.947634,
  }

  MATERIAL
  {
    3,
    5.1236, 4.62514, 1.947634,
    0.5826, 4.14551, 14785456,
    5.1236, 4.62514, 1.947634,
  }
}

FRAMEの中にMESHとMATERIALのグループがあるケースを考えます。
FRAMEのグループは、区切り文字がスペースですが、MESHとMATERIALのグループは、『句点』が区切り文字になっておりデータの型も違います。

”アルゴリズムは同じだけど部分的に違う。”

こういうケースで役に立つのが、『継承』です。
今回は、 CParseBeseという基底クラスを中心にグループ別のクラスを用意してみました。
クラス構成.png

ParseTest.h
class CParseBase {
protected:
	// 派生クラス識別用のID
	enum {
		PARSE_BASE = 0,
		PARSE_FRAME = 1,
		PARSE_MESH = 2
	};

public:
	CParseBase();
	virtual ~CParseBase();

public:
	// 純粋仮想関数としてパース関数を用意する
	virtual void parse(const FILE* fp, std::vector<char*>& result) = 0;

protected:
	unsigned int m_ParseId;
};

// フレーム情報のパース用
class CFrameP : public CParseBase {
public:
	CFrameP();
	virtual ~CFrameP();

public:
	// フレームグループを分解するための専用関数
    // フレームの構成に合わせてパースロジックを書く
	void parse(const FILE* fp, std::vector<char*>& result);

public:
	// フレーム名の取得
	char* getFrameName();

private:
	// フレームグループ内でMeshやMaterialに分かれるため、
    // サブグループ用の分岐処理
	void junctionCommand(const FILE* fp, std::vector<char*>& result);

	// 動的に確保したバッファ領域の解放処理
	void releaseName();

protected:
	char* m_pFrameName;  // フレーム名の格納用バッファ
};

こうすることで、管理がしやすくパース処理の改編もしやすくなります。

実際に動くサンプルコード

急ぎでササッと創ったコードなので、スマートではない部分もあるかと思います。
あくまでも、実装の参考としてご利用ください。
※コピペでは、自分の力にはなりませんよ！

ParseTest.cpp

// ParseTest.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//

# include "stdafx.h"

# include "Parse.h"

// Visual Studio系Buildツール
# ifdef _MSC_VER
	#define _CRT_SECURE_NO_WARNINGS	// CRT SECURE系IFを無効化する
# endif // _MSC_VER

void loadFile(char* pFileName);

int main(int argc, char* argv[])
{
	loadFile("C:\\Users\\tmatsuoka\\Desktop\\ParseTest\\Data\\test.dat");
	return 0;
}

//***********************************************************:
// loadFile(char* pFileName)
//
//	メンバ変数:
//		pFileName: ファイルを開くファイルの名称
//
//	ファイルを開いてデータを解析する
//
//***********************************************************:
void loadFile(char* pFileName) {
	FILE* fp = NULL;

	fp = fopen(pFileName, "r");
	if (fp) {
		PARSE_UTIL::startParse(fp);
		fclose(fp);
	}
}
Parse.h
# pragma once

# include <vector>

namespace PARSE_UTIL {
	void startParse(const FILE* fp);

	void parseLine(const char* pBuffer, unsigned int nBufferLength, char keyBuff, std::vector<char*>& result);

	bool isMatchWord(const char* pWord, unsigned int nWordLen, const char* pKey, unsigned int nKeyLen);
}

typedef struct stMesh {
	double m_x;
	double m_y;
	double m_z;
} MESH;

// パース系ベースクラス
class CParseBase {
protected:
	enum {
		PARSE_BASE = 0,
		PARSE_FRAME = 1,
		PARSE_MESH = 2
	};

public:
	CParseBase();
	virtual ~CParseBase();

public:
	virtual void parse(const FILE* fp, std::vector<char*>& result) = 0;

protected:
	unsigned int m_ParseId;
};

// フレーム情報のパース用
class CFrameP : public CParseBase {
public:
	CFrameP();
	virtual ~CFrameP();

public:
	void parse(const FILE* fp, std::vector<char*>& result);
	void junctionCommand(const FILE* fp, std::vector<char*>& result);

public:
	char* getFrameName();

private:
	void releaseName();

protected:
	char* m_pFrameName;
};

// フレーム情報のパース用
class CMeshP : public CParseBase {
public:
	CMeshP();
	virtual ~CMeshP();

public:
	void parse(const FILE* fp, std::vector<char*>& result);

private:
	void releaseMesh();

protected:
	MESH* m_pMesh;
	unsigned int m_nVertex;
};
Parse.cpp
# include "stdafx.h"

# include <string.h>
# include "Parse.h"

namespace PARSE_UTIL {
	#define BUFFER_LENGTH 1000	// 1ラインのサイズ

	// 構造名称定義
# define Frame "FRAME"
# define	Mesh "MESH"

	//**********************************************************
	//						外部非公開関数
	//**********************************************************

	void junctionCommand(const FILE* fp, std::vector<char*>& result) {
		if (isMatchWord(result[0], strlen(result[0]), Frame, strlen(Frame))) {
			// Frame情報をパースする
			CFrameP frameParse;
			frameParse.parse(fp, result);
		}
	}

	//**********************************************************
	//						外部公開関数
	//**********************************************************

	void startParse(const FILE* fp) {
		// ゼロ初期化
		char pBuffer[BUFFER_LENGTH];
		memset(pBuffer, 0, BUFFER_LENGTH);

		// ラインサーチ
		std::vector<char*> tagList;
		while (fgets(pBuffer, BUFFER_LENGTH, const_cast<FILE*>(fp)) != NULL) {
			// 1行分を分割する
			parseLine(pBuffer, BUFFER_LENGTH, ' ', tagList);

			// 構造分岐処理
			junctionCommand(fp, tagList);
			tagList.clear();
			break;
		}

		for (unsigned int i = 0; i < tagList.size(); i++) {
			delete [] tagList[i];
			tagList[i] = NULL;
		}
		tagList.clear();
	}

	void parseLine(const char* pBuffer, unsigned int nBufferLength, char keyBuff, std::vector<char*>& result) {
		int sIndex = -1;
		unsigned int count = 0;
		for (unsigned int i = 0; i < nBufferLength && (pBuffer[i] != '\n'); i++) {
			if (pBuffer[i] == keyBuff || pBuffer[i] == ' ') {
				if (count) {
					// 何らかの文字がある
					char* newData = new char[count+1];
					memset(newData, 0, count + 1);
					strncpy(newData, pBuffer + sIndex, count);
					printf("newData: %s\n", newData);

					result.push_back(newData);

					sIndex += count + 1;
					count = 0;

				} else {
					sIndex = -1;
					count = 0;
				}
			}
			else {
				if (sIndex < 0)
					sIndex = i;

				count++;
			}
		}

		if (count > 0) {
			char isNewline = 0;
			if (pBuffer[sIndex + count] == '\n'){
				isNewline = 1;
			}

			// 何らかの文字がある
			char* newData = new char[count + 1];
			memset(newData, 0, count + 1);
			strncpy(newData, pBuffer + sIndex, count + 1 - isNewline);
			printf("newData: %s\n", newData);

			result.push_back(newData);
		}
	}

	// 完全一致のみ検出
	bool isMatchWord(const char* pWord, unsigned int nWordLen, const char* pKey, unsigned int nKeyLen) {
		if (nWordLen != nKeyLen)
			return false;

		bool bCheck = false;
		for (unsigned int i = 0; i < nWordLen; i++) {
			if (pWord[i] != pKey[i]) {
				return false;
			}
		}

		return true;
	}
}

//**************************************************************
//							解析クラス
//**************************************************************

//******************************************************************
//							CParseBase
//******************************************************************
CParseBase::CParseBase() {
	m_ParseId = PARSE_BASE;
}

CParseBase::~CParseBase() {
	m_ParseId = PARSE_BASE;
}


//******************************************************************
//							CFrameP
//******************************************************************
CFrameP::CFrameP() : CParseBase() {
	m_pFrameName = NULL;
	m_ParseId = CParseBase::PARSE_FRAME;
}

CFrameP::~CFrameP() {
	releaseName();
}

void CFrameP::parse(const FILE* fp, std::vector<char*>& result) {
	// FRAME行に複数の定義があり、かつ2番目の1文字目が『[』だった場合
	if (result.size() >= 2 && result[1][0] == '[') {
		int numNameLen = strlen(result[1]) - 2; // 2 = '[' + ']'
		releaseName();

		m_pFrameName = new char[numNameLen + 1];
		memset(m_pFrameName, 0, numNameLen + 1);
		strncpy(m_pFrameName, result[1] + 1, numNameLen);
		printf("FrameName: %s\n", m_pFrameName);
	}

	// ゼロ初期化
	char pBuffer[BUFFER_LENGTH];
	memset(pBuffer, 0, BUFFER_LENGTH);

	// Frame内のラインサーチ
	std::vector<char*> tag;
	while (fgets(pBuffer, BUFFER_LENGTH, const_cast<FILE*>(fp)) != NULL) {
		printf("%s\n", pBuffer);

		if (pBuffer[0] != '{') {
			PARSE_UTIL::parseLine(pBuffer, strlen(pBuffer), ' ', tag);
			junctionCommand(fp, tag);
		}

		for (int i = 0; i < tag.size(); i++) {
			delete[] tag[i];
			tag[i] = NULL;
		}
		tag.clear();
		memset(pBuffer, 0, BUFFER_LENGTH);
	}
}

void CFrameP::junctionCommand(const FILE* fp, std::vector<char*>& result) {
	if (PARSE_UTIL::isMatchWord(result[0], strlen(result[0]), Mesh, strlen(Mesh))) {
		// Mesh情報をパースする
		CMeshP meshParse;
		meshParse.parse(fp, result);
	}
}

char* CFrameP::getFrameName() {
	return m_pFrameName;
}

void CFrameP::releaseName() {
	if (m_pFrameName) {
		delete[] m_pFrameName;
		m_pFrameName = NULL;
	}
}



//******************************************************************
//							CMeshP
//******************************************************************
CMeshP::CMeshP() : CParseBase() {
	m_nVertex = 0;
	m_pMesh = NULL;
	m_ParseId = CParseBase::PARSE_MESH;
}

CMeshP::~CMeshP() {
	releaseMesh();
}

void CMeshP::parse(const FILE* fp, std::vector<char*>& result) {
	// ゼロ初期化
	char pBuffer[BUFFER_LENGTH];
	memset(pBuffer, 0, BUFFER_LENGTH);

	// Frame内のラインサーチ
	std::vector<char*> tag;
	int nVertex = 0;
	while (fgets(pBuffer, BUFFER_LENGTH, const_cast<FILE*>(fp)) != NULL) {
		printf("%s\n", pBuffer);

		if (pBuffer[0] != '{') {
			PARSE_UTIL::parseLine(pBuffer, strlen(pBuffer), ',', tag);

			if (!m_pMesh && tag.size() == 1) {
				// 頂点の数
				m_nVertex = atoi(tag[0]);
				if (m_nVertex > 0) {
					m_pMesh = new MESH[m_nVertex];
				}
				nVertex = 0;
			} else if (m_pMesh && tag.size() == 3 && nVertex < m_nVertex) {
				// 頂点情報を格納する
				m_pMesh[nVertex].m_x = atof(tag[0]);
				m_pMesh[nVertex].m_y = atof(tag[1]);
				m_pMesh[nVertex].m_z = atof(tag[2]);

				printf("Vertex[%d]: %f, %f, %f\n", nVertex, m_pMesh[nVertex].m_x, m_pMesh[nVertex].m_y, m_pMesh[nVertex].m_z);
				nVertex++;
			}
		}

		for (int i = 0; i < tag.size(); i++) {
			delete[] tag[i];
			tag[i] = NULL;
		}
		tag.clear();

		memset(pBuffer, 0, BUFFER_LENGTH);
	}
}

void CMeshP::releaseMesh() {
	if (m_pMesh) {
		delete[] m_pMesh;
		m_pMesh = NULL;
	}
}
test.x
FRAME [Guild]
{
  MESH
  {
    3,
    5.1236, 4.62514, -1.947634,
    0.5826, 4.14551, -14785456,
    5.1236, 4.62514, -1.947634,
  }
}

今回は、X Fileを分析してデータに落とすための手法について説明しました。
次回は、X Fileから得た情報を基にMeshオブジェクトを3D空間で配置するための計算手法を説明します。
※次回は、数学も含まれます。

5
6
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?