그람-슈미트(Gram-Schmidt) 공정을 이용한 정규 직교화

안녕하세요!!

게임개발 입문서에서 그람-슈미트 공정과 관련해서 연습문제가 있길래, 직접 풀어보았습니다.

우선 답지가 어디있는지 안보여서 그냥 감으로 (코딩)풀었습니다.

답이 맞는지 확인하기 위해서 그람-슈미트 계산기를 열고 값을 비교해보니, 대충 실수점오차제외하면 일치하는것같네요.

 

그람-슈미트 공정은 벡터 집합이 주어졌을때 직교기저를 구하는 과정입니다.

그러면은 실제 어떤식으로 구해지는지 알아보겠습니다.

 

그람-슈미트(Gram-Schmidt) 정규 직교화

그람-슈미트 정규 직교화에서는 크게 3번의 과정으로 이루어집니다.

 

1. w의 첫번째원소는 v의 첫번째원소이다.

 

2. 식은 다음과 같다.

 

3. w를 일반화한다.

 

와우!! 간단합니다.

혹시 proj <-- 이 기호를 모르시는 분들께 알려드리자면 다음과 같습니다.

 

이제 실제로 c++기반의 코드를 짜보면서 알아보겠습니다.

 

소스코드

우선 SIMD의 기능을 적극적으로 사용하기위해, 관련함수가 포함된 DirectXMath 헤더파일을 포함시켜주셔야 합니다.

#include <iostream>
#include <vector>

#include <Windows.h>
#include <DirectXMath.h>
#include <DirectXPackedVector.h>
#include <conio.h>

using namespace DirectX;
using namespace DirectX::PackedVector;

 

<<연산자 오버로딩을 합니다.

SIMD의 기능을 사용하려면 함수파라미터의 XMVECTOR는 주석과 같은순서로 배치해주셔야합니다.

1~3은 FXMVECTOR, 4는 GXMVECTOR 5~6은 HXMVECTOR 그후로는 CXMVECTOR

// F - F - F - G - H - H - C...
std::ostream& XM_CALLCONV operator<<(std::ostream& os, DirectX::FXMVECTOR vec) {
	DirectX::XMFLOAT3 float3;
	DirectX::XMStoreFloat3(&float3, vec);

	os << "\tx: " << float3.x << "\ty: " << float3.y << "\tz: " << float3.z;

	return os;
}

 

저가 구현한 그람-슈미트 함수는 다음과 같은 순서로 작동합니다.

1. 벡터 집합 v의 내용이 비어있다면 바로 종료.

2. 벡터 집합 v의 크기가 1이라면, 바로 w0 = v0([과정 1])하고 일반화한뒤 바로 종료.

3. 이제 2중for문은 그람-슈미트 공정 [과정 2]의 내용을 담고있습니다.

4. 그다음 마지막 1중for문은 그람-슈미트 공정 [과정 3]의 내용을 담고있습니다.

std::vector<XMVECTOR> Gram_Schmidt(std::vector<XMVECTOR> v) {
	std::vector<XMVECTOR> w;

	if (v.empty()) {
		return {};
	}

	XMVECTOR w0 = v[0];
	w.push_back(XMVector3Normalize(w0));

	if (v.size() == 1) {
		return w;
	}

	for (std::size_t i = 1; i < v.size(); ++i) {
		XMVECTOR vi, wi, proj_sigma;

		vi = v[i];
		proj_sigma = XMVectorZero();

		for (std::size_t j = 0; j < i - 1; ++j) {
			XMVECTOR proj, perp;

			XMVector3ComponentsFromNormal(&proj, &perp, vi, w[j]);
			proj_sigma += proj;
			// wi = vi - Sigma{proj_wj(vi)}
		}

		wi = vi - proj_sigma;
		w.push_back(wi);
	}

	for (std::size_t i = 1; i < w.size(); ++i) {
		w[i] = XMVector3Normalize(w[i]);
	}

	return w;
}

 

이제 메인 함수에서는 이런식으로 구동시킬 겁니다.

int main(int argc, char** argv) {
	std::cout.precision(8);
	std::cout << std::fixed;
    
	std::vector<XMVECTOR> w;
	w.push_back(XMVectorSet(1.0f, 0.0f, 0.0f, 0.0f));
	w.push_back(XMVectorSet(1.0f, 5.0f, 0.0f, 0.0f));
	w.push_back(XMVectorSet(2.0f, 1.0f, -4.0f, 0.0f));

	std::vector<XMVECTOR> output = Gram_Schmidt(w);
	for (std::size_t i = 0; i < output.size(); ++i) {
		std::cout << output[i] << std::endl;
	}

	_getch();
	return 0;
}

 

실제 실행을 시켜보면, 다음과 같이 실수점오차를 제외하면 값은 일치합니다.

 

굿! 재밌다!

그럼 안녕~~!!@

 

---