치킨 날다

컨디션이 좋지 않아 문제 해석 후 풀다가 멈췄습니다.

내일 더 풀어보고 어느정도 정리해서 올려보겠습니다.

컨디션이 좋지 않아 오늘과 내일은 일단 휴식을 취하겠습니다.

따로 공부는 할 수도 있지만 보장을 못하니 비개발일지를 적습니다.

https://www.acmicpc.net/problem/2258

백준 사이트에서 풀 수 있는 정육점 문제입니다.

카테고리는 Greedy입니다.

19일 전에 처음 시도했던 이 문제를 중간에 과제 기간이라 하여 일주일 쉬긴 했지만 3주만에 드디어 풀었습니다.

풀면서 제가 막히거나 신경 쓴 부분은 다음과 같습니다.

1. 가격이 더 싼 고기를 무료로 얻을 수 있으므로 가격을 오른차순으롱 먼저 정렬하고,
무게를 빠르게 채워야 하므로 가격이 동일 한 경우 무게를 내림차순으로 정렬한다.

2. 가격이 더 싼 고기를 무료로 얻는다고 했지 가격이 같은 고기를 무료로 얻는다고는 안했다.

동일한 가격에 대해 누적된 가격을 계산해야 한다.

3. 2의 과정이 무게가 목표치보다 낮을 경우와 높을 경우에 필요한 연산이 다르다.

목표치보다 낮으면 항상 가격이 누적되고, 변동된 가격이 들어오더라도 이전 가격을 무시하면 된다.

반대로 목표치보다 높으면 가격을 더이상 누적하지 않고, 현재 최소 가격과 현재 가격만을 비교한다.

4. 모든 고기의 무게와 가격의 각 합인 unsigned int의 최대 값보다 작거나 같다.

때문에 조건에 부합하지 못해 -1을 출력해야 할 때 단순한 삼항연산자 등을 이용하면 <2^32 - 1>이 출력된다.
번거롭더라도 if문을 사용하거나, 출력 전에 string으로 형변환을 하는 등의 작업을 선행하자.

매우 간단하고, 처음에도 간단하다고 생각 했는데 3번 부분을 항상 놓치거나 잘못 작성하여 정답을 맞추지 못했다.

그리고 여태까지 문제를 풀면서 몇몇 문제는 정답 코드를 참조하기도 했는데,
이 문제는 정답률이 낮아서인지 마땅한 코드가 거의 없다.

아니, 그냥 검색 결과가 2개 정도 밖에 없다.

그래서 일부로 글 앞에 검색에 걸릴만한 내용을 추가하고, 하단에 코드를 작성했다.

이 문제에 막혀 참고를 하고자 하시는 분들은 다음 코드를 참고하시면 될 것 같다.

#include <iostream>
#include <vector>
#include <algorithm>

struct chunk {
	unsigned int weight;
	unsigned int price;
};

using namespace std;

int main()
{
	unsigned int length = 0, needs = 0, weight = 0, price = 0, before = -1;
	vector<struct chunk> meatlist;

	cin >> length >> needs;
	for (int i = 0; i < length; ++i)
	{
		cin >> weight >> price;
		meatlist.push_back(chunk{ weight, price });
	}

	sort(meatlist.begin(), meatlist.end(), [](const auto& a, const auto& b) { return ((a.price < b.price) || (a.price == b.price) && (a.weight > b.weight)); });

	weight = price = 0;

	for (const auto& iter : meatlist)
	{
		if (weight < needs)
		{
			if (before == iter.price)
			{
				price += iter.price;
			}
			else
			{
				before = price = iter.price;
			}
		}
		else
		{
			if ((before != iter.price) && (price >= iter.price))
			{
				before = price = iter.price;
			}
		}
		weight += iter.weight;
	}

	if (weight < needs)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << price << endl;
	}

	return 0;
}

혹 몇가지 testcase가 필요하신 분들은 아래 파일에 있는 것을 참고하시길.

유의미 하지는 않지만 그래도 없는 것 보다는 나을 것이다.

Puzzle을 기능 기준으로 수정 하려다가 수 많은 에러에 맞고 쓰러졌습니다.

Puzzle의 코어한 부분들이 모두 Blueprint로 구현되어 있었기에 기능 구현이고 뭐고
일단 C++ 스크립트로의 수정 과정이 선행 되어야 했습니다.

그래서 안타깝게도 하루만에 순서를 바꾸어 Interface 적용을 앞땡겼습니다.

Interface를 적용하고자 하는 부분을 탐색해보자 정말 수 많은 선택지가 펼쳐졌습니다.

그 중에서 단순 생성과 관련된 함수나, 외부에서 접근할 필요가 없는 트리거에 대한 변경 함수를 제외하고 
나머지 상태 확인이나 트리거 변경, 선언 함수들을 Interface로 엮었습니다.

그 결과는 다음과 같습니다.

이들을 하나씩 적용하고, 이미 기능이 적용 되어 있다면 이를 수정 할 예정입니다.

이 외에 변경점이라면 이전에 Climb 기능 구현을 하면서 터득한
Animation Notify를 이용해 Melee Attack 기능을 개선하고자 합니다.

우선 Hit 이벤트가 여러번 발생하는 것을 막아주는 Lock을 Semaphore로 변경하고자 합니다.

이를 통해 한 Character에게는 한번의 이벤트만 발생하지만, 한번에 여러 Character에게 이벤트가 발생할 수 있습니다.

그리고 데미지 계산이나 Semaphore 연산을 RPC 함수를 이용하고자 합니다.

그리고 Wall을 분할하고자 합니다.

현재의 Wall은 Character의 이동 경로를 막는 방해물과 등반 가능한 등반 Object가 동시에 혼용되고 있습니다.

이를 두개로 나누어 기존의 Wall은 후자의 것으로 사용하고, 

전자의 것에 어울리는 새로운 Object를 생성하고자 합니다.

마지막으로 Puzzle을 새로 개발하고자 합니다.

BP 기반에 이전 Trap에 너무 의존적이었기에 완전히 삭제하고, 새로운 Puzzle을 개발하고자 합니다.

이번에는 UI 등 편의성을 개선할 계획도 있습니다.

새로운 Puzzle은 기존의 Break, Select를 우선 구현하고, 새로운 것을 구현할지 그때 가서 고민하려 합니다.

진행 순서는

1. Character 자체 기능 개선

2. Wall 분할

3. Climb 기능 개선

4. Trap 기능 개선

5. Puzzle 생성

입니다.

#include <iostream>
#include <vector>
#include <algorithm>

struct chunk {
	unsigned int weight;
	unsigned int price;
};

using namespace std;

int main()
{
	unsigned int length = 0, needs = 0, weight = 0, price = 0, before = -1;
	vector<struct chunk> meatlist;

	cin >> length >> needs;
	for (int i = 0; i < length; ++i)
	{
		cin >> weight >> price;
		meatlist.push_back(chunk{ weight, price });
	}

	sort(meatlist.begin(), meatlist.end(), [](const auto& a, const auto& b) { return ((a.price < b.price) || (a.price == b.price) && (a.weight > b.weight)); });
	weight = price = 0;

	for (const auto& iter : meatlist)
	{
		if (weight < needs)
		{
			if (price > iter.price)
			{
				before = price = iter.price;
			}
			else
			{
				if (before == iter.price)
				{
					price += iter.price;
				}
				else
				{
					before = price = iter.price;
				}
			}
		}
		else
		{
			if ((price > iter.price) && (before != iter.price))
			{
				before = price = iter.price;
			}
		}
		weight += iter.weight;
	}

	if (weight < needs)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << price << endl;
	}

	return 0;
}

구상한 코드가 틀려 몇일 정도 다시 예외 상황이나 문제점을 고민해보도록 하겠습니다.

오늘은 Spawn Object의 Collision과 Hidden을 어떻게 처리할지 고민을 좀 하였습니다.

처음에는 Interface를 사용하지 않고 한번 구현해 보려 했으나,
Character와 Object를 모두 Spawn하려면 결국 Interface를 쓰거나, 
Spawn Trap을 Object Spawn고 Character Spawn으로 다시 나누거나, 

Object의 근간인 THObject의 내용을 Interface로 따로 빼내거나 해야 합니다.

결국 Interface를 쓰거나 구조를 바꾸거나 둘 중 하나입니다.

여기서 고민이 생기기 시작합니다.

Interface를 쓰지 않는다면 지금 당장 가장 빠르게 구현을 할 수 있겠지만, 
앞으로도 이런 문제를 직면 하면 SubClass를 쪼개줘야 할 것입니다.

어쩌면 동시에 두 가지 기준을 잡는다면 Class를 4개 이상으로 쪼개야 할 것입니다.

Interface를 쓴다면 지금과 같은 문제를 효과적이고 가장 좋은 방법으로 해결할 것입니다.

하지만 현재 Interface를 생성하는 방식을 정확히 파악하지 못하고 있고, 
또 Document에서 제시된 것으로 보아 여태까지 개발해온 많은 상호작용들을
Interface로 엮어서 다시 구현해야 할 것 같습니다.

다른 작업이 덩쿨에 엮이듯이 줄줄이 딸려 오는 것이죠.

VS 업데이트 2시간 동안 상당히 고민을 하다가 잠들고, 다시 일어나 고민 한 끝에
Interface를 적용하기로 결정했습니다.

단, 우선순위는 뒤로 미룰 것입니다.

일이 어느정도 마무리가 되고 나서 Interface를 전반적으로 적용을 하고자 합니다.

그래서 빠르면 이번주. 혹은 다음주부터 Puzzle쪽 기능을 우선 구현하고자 합니다.

Puzzle의 Multiplay상 기능 구현이 완료가 되면, Project 전반적으로 Interface 분리 작업을 진행 할 것입니다.

그 뒤에는 Level에 특정 스크립트를 C++로 적용할 수 있는지 조사할 계획입니다.

이는 Teleport나 Brush등의 기능들에 필요하다고 판단이 되며,
후에 구조와 기능에 따라 다른 Trap들도 다시 한번 수정을 할 수도 있을 것입니다.

DirectX 공부가 너무 늦게 끝나 미처 알고리즘을 하지 못했습니다.

매일매일 하는 것은 어떻게 보면 남는 시간을 투자하고자 하는 것이기에 이런 문제가 생기네요.

아무래도 일시적이지만 투자 시간이 늘어나기도 했고,

이론에서 프로그래밍 입문으로 넘어가는 단계라 시간과 체력 소모가 큽니다.

정육점 문제 더럽게 안풀리던데 시간이 얼마가 걸리든 정답은 보고 다음 문제 넘어가렵니다.

Input Assembler

• Input Assembler 단계는 메모리에서 기하 자료를 읽어 기하학적 기본 도형을 조립한다.

Vertex

• 원래 Vertex는 두 변이 만나는 점이다. 때문에 "기하학적 기본 도형의 꼭짓점"이라는 인상을 받을 것이다.
  • 그러나 Direct3D의 정점은 그보다 훨씬 일반적이다.
• Direct3D의 Vertex는 본질적으로 공간적 위치 이외의 정보도 담을 수 있다.
  • 그리고 이를 이용해 더 복잡한 Redering 효과를 낼 수 있다.
    • 예를 들어 조명을 구현하기 위해 Vertex에 Normal Vector를 추가할 수 있다.
    • 또는 Texture를 적용하기 위해 Vertex에 Texture 좌표를 추가할 수도 있다.
• Direct3D에서는 Application이 자신만의 Vertex type을 정의할 수 있는 유연성을 제공한다.

기본도형 위상구조(Primitive Topology)

• Vertex들은 Vertex Buffer라는 특별한 Direct3D Data Structure 안에 담겨서 Rendering Pipeline에 묶인다.
  • 이는 그저 Vertex들을 연속적인 Memory에 저장하는 Data Structure일 뿐이다.
• Vertex Buffer 그 자체는 Vertex들이 어떤 식으로 조합해서 기본도형을 형성할 것인지 알려주지 않는다.
  • 이를 알려주는 것은 Primitive Topology가 맡는다.
• 다음은 Primitive Topology를 지정하는 Method와 이를 정의한 Enumeration이다.

virtual void STDMETHODCALLTYPE IASetPrimitiveTopology( 
            _In_  D3D12_PRIMITIVE_TOPOLOGY PrimitiveTopology) = 0;
            
typedef 
enum D3D12_PRIMITIVE_TOPOLOGY_TYPE
    {
        D3D12_PRIMITIVE_TOPOLOGY_TYPE_UNDEFINED	= 0,
        D3D12_PRIMITIVE_TOPOLOGY_TYPE_POINT	= 1,
        D3D12_PRIMITIVE_TOPOLOGY_TYPE_LINE	= 2,
        D3D12_PRIMITIVE_TOPOLOGY_TYPE_TRIANGLE	= 3,
        D3D12_PRIMITIVE_TOPOLOGY_TYPE_PATCH	= 4
    } 	D3D12_PRIMITIVE_TOPOLOGY_TYPE;

• 한번 Method를 호출해서 Primitive Topology를 설정하면, 다음 호출이 있기 전까지 모든 그리기 호출에서 이 Primitive Topology가 적용된다.
• 각 Primitive Topology의 방식은 아래 링크로 대체한다.

https://docs.microsoft.com/ko-kr/windows/uwp/graphics-concepts/primitive-topologies

색인(Index)

• 앞서 이야기 했듯이, 3차원 Solid Object의 기본 구축 요소는 삼각형이다.
• 다른 다각형을 표현할 때에도 여러 개의 삼각형으로 나누어서 표현을 한다.
  • 때문에 다각형을 여러 개의 삼각형으로 표현하기 위해서는 다음과 같이 Vertex Array를 사용한다.

Vertex quad[6] = {
	v0, v1, v2, 	// 삼각형 0
    	v0, v2, v3	// 삼각형 1
};

Vertex octagon[24] = {
	v0, v1, v2, 	// 삼각형 0
	v0, v2, v3, 	// 삼각형 1
	v0, v3, v4, 	// 삼각형 2
	v0, v4, v5, 	// 삼각형 3
	v0, v5, v6, 	// 삼각형 4
	v0, v6, v7, 	// 삼각형 5
	v0, v7, v8, 	// 삼각형 6
	v0, v8, v1 	// 삼각형 7
};

• 예시에서 보이듯이, 각 삼각형들은 다 수의 Vertex들을 공유한다.
  • 한 두개라면 상관이 없지만, 팔각형처럼 공유하는 Vertex가 많아지면 문제가 심각해진다.
    • 같은 Vertex를 여러번 저장하면서 Memory 요구량이 증가한다.
    • 마찬가지로 같은 Vertex를 여러번 처리하면서 Graphic Hardware의 처리량이 증가한다.
• 물론 다른 방식의 Primitive Topology를 사용하는 방법도 있지만, 삼각형 방식만큼 유연성이 높은 방식이 없다.
• 때문에 우리는 삼각형 목록에서 중복 Vertex를 제거하기 위해 Index를 사용한다.
  • 예를 들어 사각형의 Vertex Array는 다음과 같이 표현한다.

Vertex v[4] = { v0, v1, v2, v3 };
UING indexList[6] = { 0, 1, 2, 	// 삼각형 0
		      0, 2, 3};	// 삼각형 1

• Graphic Hardware는 Vertex Array의 고유한 Vertex들을 처리한 후, Index를 이용해 Vertex들을 조합한다.
• Vertex의 중복이 없어지는 대신 Index의 중복이 발생하지만, 이는 큰 문제가 없다.
  • Index는 그냥 정수이므로 Vertex Structure보다 메모리 점유양이 적다.
  • Vertex Cache 순서가 좋은 경우 Graphic Hardware가 중복된 Vertex를 처리하지 않아도 된다.

Vertex Shader

• Input Assembler에서 기본 도형들을 조립 한 후, Vertex들이 Vertex Shader(VS)로 입력된다.
  • 이는 Vertex 하나를 입력 받아 Vertex 출력하는 함수로 간주해도 될 것이다.
  • 화면에 그려질 모든 Vertex는 이 Vertex Shader를 거쳐간다.
• Vertex Shader Function의 구체적인 내용은 Programmer가 구현해서 GPU에 제출한다.
  • 이 Function은 각 Vertex에 대해 GPU에서 실행되기 때문에 아주 빠르다.
• Transform, Illuminate, Conversion Mapping 등 수 많은 특수효과를 GS에서 수행할 수 있다.
  • Vertex Shader에서 Vertex data는 물론 Texture, Transform Matrix등 GPU Memory에 담긴 다른 자료에도 접근할 수 있기 때문이다.

Local Space와 World Space

• 3D 물체를 만들 때에는 장면 전역의 좌표계가 아니라 물체 자신의 국소 좌표계를 기준으로 구축한다.
  • 전자의 좌표계를 World Space라고 부른다.
  • 후자의 좌표게는 Local Space라고 부른다.
• Local Space에서 3차원 물체의 Vetex들을 정의 했다면, 이를 World Space에 적절히 배치해야 한다.
• 이를 위해서는 Local Space와 World Space의 관계를 정의할 수 있어야한다.
  • 정확히는 World Coordinate를 기준으로 한 Local Coordinate의 원점과 Axis의 위치, 방향을 지정.
  • 그리고 이에 해당하는 Coordinate Transformation을 수행해야 한다.
• 이 Coordinate Transformation을 세계 변환(World Transform)이라 부른다.
  • 이때 Transform 되는 Matrix를 세계 행렬(World Matrix)라고 부른다.
• World Matrix를 만들기 위해서는 World Space를 기준으로 한 Local Space의 원점과 Axis의 좌표가 필요하다.
• 더 흔한 접근 방식은 World Transform W를 SRT 형태로 정의하는 것이다.
  • S는 Scaling Matrix
  • R은 Rotation Matrix
  • T는 Translate Matrix
• 이와 같이 Local Space에서 물체를 정의하는 방식을 사용하는 이유는 다음과 같다.
  • 더 쉽다. 
    • 보통 Local Space에서 원점과 물체의 중심이 일치하고, Axis 중 하나와 대칭한다.
  • 더 합리적이다.
    • World Space에서 모양은 같으니 크기나 방향이 다른 물체를 여러번 만드는 것은 비합리적이다.
    • 이를 Local Space에서 생성하여 다양한 크기와 방향에 맞춰 배치하는 것이 더 합리적이다.
  • 같은 물체를 반복적으로 배치해야 할 경우, Vertex나 Index으로 인한 낭비를 막아준다.

• 이런 방식을 Instancing이라고 부른다.

시야 공간(View Space)

• 최종적으로 화면에 표시 될 2차원 이미지를 만들기 위해서는 가상의 카메라를 배치해야 한다.
  • 이느 World에 2차원 이미지를 생성해야 하는 영역을 결정하는 것이다.
• 이 때 카메라에 Local Coordinate를 부여했을 때, 이 Coordinate를 View Space라 한다.
  • View Space는 시점 공간(Eye Space) 또는 카메라 공간(Camera Space)라고 부르기도 한다.
• 카메라는 View Space에서 +Z축을 바라보고, 카메라의 오른쪽이 +X축, 위쪽이 +y축이다.
  • 이 때 World Space에서 Local Space로의 Transform 하는 것을 시야 변환(View Transform)라 한다.
  • Transform 되는 Matrix는 시야 행렬(View Matrix)라고 부른다.
• 이는 World Space에서 카메라의 좌표에 대한 World Matrix W의 반대되는 역할을 한다.
  • 즉 W의 역행렬이 View Matrix이다.
• 이에 대해 DirectXMath.h는 다음과 같은 함수들을 제공하고 있다.

XMMATRIX    XM_CALLCONV     XMMatrixLookAtLH(FXMVECTOR EyePosition, FXMVECTOR FocusPosition, FXMVECTOR UpDirection);
XMMATRIX    XM_CALLCONV     XMMatrixLookAtRH(FXMVECTOR EyePosition, FXMVECTOR FocusPosition, FXMVECTOR UpDirection);
XMMATRIX    XM_CALLCONV     XMMatrixLookToLH(FXMVECTOR EyePosition, FXMVECTOR EyeDirection, FXMVECTOR UpDirection);
XMMATRIX    XM_CALLCONV     XMMatrixLookToRH(FXMVECTOR EyePosition, FXMVECTOR EyeDirection, FXMVECTOR UpDirection);

투영과 동차 절단 공간

• 카메라를 서술하는 요소가 하나 더 있다.
  • 카메라가 바라보는 절두체(Frustum)의 공간 영역이다.
• 이제 할 일은 이 절두체 안의 3차원 기하 구조를 2차원 투영 창으로 Projection하는 것이다.
  • 이를 위해서는 반드시 평행선들이 하나의 소실점으로 수렴하는 방식으로 이루어져야 한다.
  • 그래야 3차원 Dpeth가 증가함에 따라 Project 된 결과가 줄어드는 현상이 나타나다.
  • 즉 이는 원근투영(Perspective Projection)을 따른다는 것이다.
  • 정점에서 시점으로의 직선을 정점의 투영선(line of projection)이라 부른다.
• 원근투영 변환(Perspective Projection Transform)은 하나의 3차원 Vertex v를 Line of Projection이 2차원 투영 평면과 만나는 점 v'로 변환하는 Transform이다.
  • 이 v'를 v의 Projection이라 부른다.

Frustum의 정의

• View Space에서 Center of Projection을 원점에 두고 +Z축을 바라보는 Frustum을 4가지 수량으로 정의할 수 있다.
  • 원점과 가까운 평면 사이의 거리 n
  • 원점과 먼 평면 사이의 거리 f
  • 수직 시야각 a
  • 종횡비(Aspect Ratio) r
• 여기서 평면이 XY 평면과 평행임을 주목하자.
  • 이로 인해 평면과 원점사이의 거리는 Z축 상의 거리가 된다.
• Aspect Ratio r = w / h로 정의 된다.
  • w: Projection 창의 너비
  • h: Projection 창의 높이
• Projection 창은 본질적으로 View Space 안 장면의 2차원 이미지이고, 이는 결국 Back Buffer에 사상된다.
  
  • 때문에 Projection Window의 Aspect Ratio는 Back Buffer의 Aspect Ratio와 같게 만드는 것이 바람직하다.
• 그래서 일반적으로 Back Buffer에 맞춰서 설정한다.

정규화된 장치 좌표(Normalized Device Coordinates)

• Vertex를 Aspect Ratio을 이용해 Projection하면 Aspect Ratio에 의존한다는 문제가 발생한다.
  • 이는 Hardware가 Projection 창의 크기가 관여하는 연산을 수행할 수 있으려면
    Hardware에 Asprect Ratio를 알려줘야 한다는 것이다.
• 이 문제를 해결하기 위해 우리는 X 좌표 성분을 [-r, r]에서 [-1, 1]로 비례시킨다.
  • 이러한 작업이 수행된 후의 좌표를 Normalized Device Coordinates(NDC)라 부른다.
• Space Area에서 NDC Space로의 변환은 일종의 단위 변환(unit conversion)으로 볼 수 있다.
• x 축에서 NDC의 한 단위는 View Area의 r 단위와 같다.
  • 1 ndc = r vs
  • 즉, NDC 좌표에서는 Projection 창의 너비도, 높이도 2이다.
• 위와 같이 Projection 창의 크기가 조정되었으므로, Hardware는 Aspect Ratio를 몰라도 된다.
  • 뒤집어 말하면, Graphic Hardware는 Project된 Coordinate들이 NDC Space라고 가정하므로,
    프로그래머는 항상 실제로 NDC Space를 기준으로 한 Projection Coordinate를 공급하는 것에
    신경을 써야 한다.

Projection Transform을 Matrix로 표현

• 일관성을 위해서는 Projection Trnasform을 하나의 Matrix로 표현하는 것이 좋다.
  • 그러나 식이 비선형적이라 Matrix Expression이 존재하지 않는다.
• 그래서 우리는 한가지 요령으로 이 문제를 피해간다.
  • 바로 선형 부분과 비선형 부분을 분리하는 것이다.
• Projection Transform에서 비선형적인 연산은 z로 나누는 연산이다.
  • 임의의 Vertex V = ( x, y, z, w )에 대한 Transform 연산을 하면 w = z가 되기 때문이다.
• 그렇기에 Transform 연산을 한 후에 z로 나누어 w = 1로 만들어준다.
  • z = 0인 경우를 걱정 할 수 있으나, 아무리 평면과 가까워도 z는 0보다 크다.
• 이와 같이 w로 나누는 것을 원근 나누기(Perspective Divide), 또는 동차 나누기(Homogeneous Divide)라 부른다.

Normalized Depth

• Projection이 끝났다면 3차원의 z 성분은 이제 버려도 되지 않을까 하는 생각이 들 수 있다.
  • 하지만 Depth Buffering을 위해 여전히 Depth 정보가 필요하다.
• 앞서 보았듯이, Direct3D는 투영된 x, y 좌표가 Normalized 되어 있기를 요구한다.
  • Depth 역시 마찬가지로 [0, 1] 구간으로 Normalized 되기를 요구한다.
• 이를 위해 구간 [n, f]를 [0, 1]로 사상하는 순서 보존 함수 g(z)를 구축할 필요가 있다.
  • 이는 Depth 값들이 Transform 되어도 상대적 관계는 유지 시키는 함수이다.
• Depth Buffering에는 Dpth의 값이 아니라 상대적 관계가 필요한 것임을 기억하자.
• Depth를 Normalize 하기 위해서는 한번의 Scaling과 한번의 Translate 연산이 필요하다.
  • 하지만 실제로 적용을 해본다면, 잘 먹히지 않을 것이다.

• 이제 여기서 두 가지 구속조건을 만족하는 A와 B를 선택해야 한다.
  • 조건 1) g(n) = A + B/n = 0 (가까운 평면이 0으로 사상됨)
  • 조건 2) g(f) = A + B/f = 1 (먼 평면이 1로 사상됨)
• 여기서 조건 1을 풀고, 조건 2를 푼다면 함수 g의 그래프가 순증가(strictly increasing)이고, 비선형임을 알 수 있다.
  • 또한 치역의 대부분을 가까운 평면에 가까운 Depth이 차지하고 있음도 알 수 있다.
    • Depth들이 치역의 작은 부분에 몰려 있는 것이다.
  • 때문에 Depth Buffer에서 정밀도 문제가 발생 할 수 있다.
• 이를 해결하기 위한 일반적인 조언은, "가까운 평면과 먼 평면을 최대한 가깝게 하라"는 것이다.
  • 값이 작으면 작을수록 기울기가 늘어나면서 치역이 분포가 더 퍼지게 된다.
• 이 Proejction Matrix를 곱하고, Perspective Divide를 하기 전의 기하 구조를
  동차 절단 공간(Homogeneous Clip Space) 또는 투영 공간(Projection Area)에 있다고 한다.
• Perspective Divide를 수행한 후의 기하 구조를 가리켜 Normalized Device Coordinate Area에 있다고 말한다.

XMMatrixPerspectiveFovLH

• DirectXMath.h에는 이에 대해 다음 함수를 제공한다.

XMMATRIX    XM_CALLCONV     XMMatrixPerspectiveFovLH(float FovAngleY, float AspectRatio, float NearZ, float FarZ);
XMMATRIX    XM_CALLCONV     XMMatrixPerspectiveFovRH(float FovAngleY, float AspectRatio, float NearZ, float FarZ);

Hull Shader

• Hull Shader에 대한 자세한 설명은 따로 찾을 수 없었다. 우선은 관련 링크로 대체를 한다.

https://docs.microsoft.com/ko-kr/windows/uwp/graphics-concepts/hull-shader-stage--hs-

Tessellator

• Tessellation은 한 mesh의 삼각형들을 더 잘게 쪼개서 새로운 삼각형들을 만드는 과정을 나타낸다.
  • 이렇게 생성된 새로운 삼각형들을 새로운 위치로 이동함으로써 좀 더 세밀한 메시를 만들어낼 수 있다.
• Tessellation의 장점은 다음과 같다.
  • 계산 리소스를 더 중요한 곳에 투자할 수 있다.
    • 카메라에 가까운 삼각형들에는 세부도를 높이고,
      먼 삼각형들에는 Tessellation을 적용하지 않으면서 세부도를 낮춘다.
    • 이러한 방식의 세부수준(LOD) 메커니즘은 눈에 띄는 부분에 삼각형을 더 투자할 수 있게 한다.
  • 메모리 소모를 줄일 수 있다.
    • 메모리에는 삼각형이 적은 Mesh를 담아두고 즉석에서 삼각형을 추가함으로써 메모리를 적용할 수 있다.
  • 계산량을 줄일 수 있다.
    • Animation이나 물리 처리 같은 연산들을 저다각형 Mesh로 수행하고,
      Tessellation된 고다각형 Mesh는 Rendering에만 사용한다.
• Direct3D 11에서 추가된 Tessellation Step은 GPU에서 기하구조를 그 수단을 제공한다.
  • 이전에는 CPU에서 새로운 기하구조를 만들고, 이를 GPU에 올려 Rendering해야 했다.
    • 하지만 CPU 메모리에서 GPU 메모리로 올리는 것은 매우 느린 연산이다.
    • 게다가 CPU에서 Tessellation 하는 것도 큰 부담이 된다.
• 그래서 Direct3D 11 이전에는 실시간 그래픽에서 Tessellation이 별로 인기가 없었다.
• 하지만 Direct3D 11에서는 이를 전적으로 Hardware에서 수행하는 API를 제공한다.
  • 이 덕분에 Tessellation은 매우 매력적인 기법이 되었다.
• Tessellation 단계는 생략이 가능한 단계이다.
• Tessellation에 대한 자세한 이론은 나중에 뒤에서 좀 더 자세히 다루겠다.

Domain Shader

• 역시 자세한 설명을 찾지 못해 링크로 대체한다.

https://docs.microsoft.com/ko-kr/windows/uwp/graphics-concepts/domain-shader-stage--ds-

Geometry Shader

• Geometry Shader(GS) 단계는 생략 가능한 단계이며, 한참 뒤에 사용할 것이기에 간단히 설명만 하겠다.
• Geometry Shader는 하나의 온전한 기본도형을 입력받아 임의로 변경한다.
  • 예를 들어 삼각형 목록을 그리는 경우, Geometry Shader에는 삼각형을 정의하는 Vertex 3개가 입력된다.
    • 이 Vertex들은 이미 Vertex Shader 처리를 거친 것들이다.
• Geometry Shader가장 큰 장점은 기하구조를 생성하거나 파괴 할 수 있다는 것이다.
  • 예를 들어 Geometry Shader는 입력 기본도형을 다른 여러 기본 도형으로 확장할 수 있다.
  • 또 특정 조건에 따라서는 출력하지 않고 폐기할 수도 있다.
• 이는 Vertex Shader와 대조되는 특징이다.
  • Vertex Shader는 항상 Vertex 하나를 받아 Vertex 하나를 출력한다.
  • 하지만 Geometry Shader의 흔한 용도는 하나의 점이나 선분을 하나의 사각형으로 확장하는 것이다.
• Rendering Pipeline 사진에서 Geometry Shader로부터 Stream Output으로 화살표가 이어지는 점도 주목하자.
  • GS의 Output Vertex Data는 Stream Output 단계를 통해
    Memory의 Buffer에 저장해두고 나중에 활용하는 것이 가능하다.
    • 이는 고급 기법이므로 뒤에서 자세히 설명하겠다.

Clipping

• Frustum을 벗어난 기하 구조를 폐기하고, 교차한 것은 Frustum 내부에 있는 것만 남도록 잘라내는 연산이다.
• 이 연산은 Hardware가 수행해주므로 이 이상 설명은 생략한다.
  • 관심이 있다면 Sutherland-Hodgeman Clipping Algorith을 살펴보기 바란다.

Rasterizer

• Rasterization Stage라고도 하며, 주 임무는 투영된 3차원 삼각형으로부터 Pixel 색상들을 계산하는 것이다.

Viewport Transform

• Clipping을 마치고 나면 Hardware는 Prespective Divide를 수행해서 Homogeneous Clip Space Coordinate를
  Normalized Device Coordinate로 변환한다.
• Vertex들이 NDC Space에 들어왔다면, 2차원 이미지를 형성하는 x, y 성분들을
  Back Buffer의 한 직사각형 영역으로 변환한다. 
  • 이 직사각형 영역이 Viewport이다.
• 이 Transform을 마치면 x, y 성분은 Pixel 단위의 값이 된다.
  • 일반적으로 Viewport Transform은 z성분은 변경하지 않는다.
    • 이 성분을 Depth Buffering에 사용해야하기 때문이다.
  • 하지만 D3D12_VIEWPORT의 MinDepth와 MaxDepth의 값은 변경할 수 있다.
    • 단, 반드시 [0, 1] 범위 안에 들어와야 한다.

Backface Culling

• 하나의 삼각형에는 두 개의 면이 있는데, 이를 구분하기 위해서는 다음 관례를 사용한다.
  • 삼각형의 한 Vertex를 기준으로, 다른 Vertex로 향하는 Vector e1, e2를 생성한다.
  • e1과 e2를 Cross Product 한 후 Normalize 한 결과를 n이라 하자.
  • Vector n과 같은 방향인 면을 Front Side, 반대 쪽을 Back Side라 한다.
• 관찰자가 삼각형의 앞면을 보고 있는 경우, 그 삼각형을 Front-Facing 삼각형이라 한다.
  • 반대로 뒷면을 보고 있으면 Back-Facing 삼각형이라 한다.
• 또한 DirectX의 관례를 통해 Vertex가 시계방향으로 나열된 삼각형을 Front-Facing 삼각형으로 판단 가능하다.
• 3차원 장면에서 대부분의 물체는 Closed Solid Object이다.
• 각 물체의 삼각형들을 항상 Normal Vector가 물체 바깥쪽으로 향하도록 구성한다고 하자.
  • 그럼 카메라에는 Solid Object의 Back-Facing 삼각형이 보이지 않는다.
    • Back-Facing 삼각형은 모두 Front-Facing 삼각형에 가려지기 때문이다.
  • 때문에 Back-Facing 삼각형은 화면에 그릴 필요가 전혀 없어진다.
• 이러한 Backface Culling은 Pipeline에서 이러한 삼각형을 골라서 폐기하는 공정이다.
• 이 과정을 통해 처리해야 할 삼각형의 수가 거의 절반으로 줄어들 수 있다.
• Direct3D는 일반적으로 시계방향으로 감긴 삼각형을 Front-Facing 삼각형으로 간주한다.
  • 하지만 Render State의 설정에 따라 그 반대도 가능하다.

Vertex 특성 Interpolation

• 이전에 한번 삼각형은 Vertex들로 정의된다고 말한 적이 있을 것이다.
  • 또한 Vertex Data에는 위치 정보뿐만 아니라 색상, Normal Vector, Texture Coordinates 같은 
    추가적인 특성을 붙일 수 있다는 점도 언급했을 것이다.
• Viewport Transformation을 거친 후에는 Vertex의 그러한 특성들을 Pixel들에게 Interpolation 해야한다.
  • Vertex 뿐만 아니라 Depth value도 Interpolation 해야 한다.
• 그럼 각 Pixel마다 Depth Buffering Algorithm을 위한 값이 생성된다.
• 이러한 Vertex 특성들은 View Space에서 Interpolation되는데, 
  3차원 공간에서는 삼각형의 면을 따라 Linear하게 Interpolation 된다.
  • 이를 위해서는 원근 보정 보간(Perspective Correct Interpolation)이 필요하다.
• Perspective Correct Interpolation은 Hardware가 수행하므로 수학적 세부사항을 굳이 알 필요는 없다.

Pixel Shader

• Pixel Shader(PS)는 프로그래머가 작성해서 GPU에서 실행하는 프로그램으로, 각 Pixel Fragment마다 실행된다.
• PS는 기본적으로 Interpolation 된 Vertex 특성들을 입력받아 하나의 색상을 출력한다.
  
  • 이는 고정된 상수 색을 돌려주는 간단한 형태서부터
    Pixel별 조명, 반사, 그림자 효과를 수행하는 복잡한 형태까지 다양하다.

Output Merger

• Pixel Shder가 생성한 Pixel Fragment들은 Output Merger(OM)단계로 입력된다.
• Output Merger에서는 일부 Pixel Fragment들이 폐기된다.
  • Depth나 Stencil 판정으로 인해
• 기각되지 않은 Pixel Fragment는 Back Buffer에 기록된다.
• Blending도 이 단계에서 일어난다.

Blending

• Blending은 새 Pixel이 Back Buffer의 기존 Pixel을 덮어쓰는 것이 아니라
  두 Pixel을 일정한 공식에 따라 혼합된 결과를 기록하는 것을 말한다.
• Blending은 주로 반투명과 같은 특수효과를 내는데 쓰인다.
• 이에 대해서는 뒤에서 더 자세히 다룰 예정이다.

• 이번 챕터에서는 총 두가지 이론을 다룰 것이다.
  • 평평한 2차원 모니터 화면을 통해서 3차원 세상을 보고 있다는 환상의 주요 요소
  • 색상을 수학적으로, 그리고 Direct3D 코드 안에서 표현하고 다루는 방법

3차원의 환상

• 3차원 세계의 깊이와 부피를 2차원 평면으로 나타내는 방법은 이미 충분히 연구되어 왔다.
  • 소실점(Vanishing Point)
    • 시각 평행선들이 수렴하는 점.
  • 물체 겹침(Object Overlay)
    • 불투명한 물체가 그 뒤에 있는 물체의 일부 또는 전체를 가리는 현상.
  • 조명, 셰이딩
    • 광원으로 인한 밝기 변화를 적용함으로써 부피를 표현
  • 그림자
    • 그림자는 장면에서 광원이 있는 위치를 말해준다.
    • 또한 물체의 위치를 대략적으로 제시하기도 한다.

모형의 표현

• Direct3D Application에서는 일반적으로 Solid의 3차원 물체를 삼각형 Mesh로 Approximation한다.
• 실제 세상의 그 어떤 3차원 물체라도 삼각형 mesh로 표현이 가능하다.
• 일반적으로, 근사하는데 사용한 삼각형이 많을수록 요구되는 처리 능력이 높아진다.
  • 따라서 사용자의 Hardware 성능에 근거하여 적절한 균형점을 찾아야 한다.
• 삼각형 외에 섬이나 점도 물체를 근사하는데 유용하다.
  • 예를 들어 곡선은 한 Pixel 굵기의 짧은 선분들로 근사가 가능하다.
• 모든 3차원 물체를 삼각형 mesh로 표현이 가능하지만, 이를 일일이 나열하는 작업은 매우 성가시다.
  • 그래서 간단한 모형이 아닌 이상 모형을 생성, 조작할 때에는 3D Modeler를 사용한다.
  • 3D Studio Max, LightWave 3D, Maya, Softimage, Blender 등

색상 표현의 기초

• 컴퓨터 모니터는 Pixel마다 Red, Green, Blue 색의 빛을 섞어서 방출한다.
• 모니터가 방출하는 RGB의 세기에는 상한과 하한이 존재한다.
  • 보통 [0, 1]의 정규화된 값을 사용한다.
  • 0은 빛이 전혀 ㅇ벗는 것이고, 1은 세기가 최대인 것이다.
  • 예를 들어 (0.25, 0.67, 1.0)은 25%의 Red, 67%의 Green, 100%의 Blue가 혼합되었다는 의미이다.
• 이는 하나의 색상을 하나의 3차원 색상 Vector (r, g, b)로 나타낼 수 있음을 의미한다.

색상 연산

• Vector 연산 중 몇가지 연산은 색상 Vector에도 그대로 적용이 가능하다.
  • 덧셈, 뺄셈, 스칼라 곱 등은 그대로 적용이 된다.
• 반면 Dot Product, Cross Product와 같은 연산은 의미를 퇴색한다.
• 색상 Vector만의 연산도 존재한다.
  • 변조(Modulation) 혹은 성분별 곱셈(Componentwise multiplication)이라고도 한다.

• Modulation은 주로 조명 공식에 쓰인다.
• 색상 연산은 성분이 [0, 1] 범위 바깥으로 나갈 수 있다.
  • 하지만 1.0이 최대 세기이므로 이보다 큰 성분은 1.0으로 clamping 해야 한다.
  • 마찬가지로 음의 세기도 0.0으로 clamping 해야 한다.

128비트 색상

• 보통 RGB 외에 A(Alpha)라는 성분을 색상 Vector에 추가하는 경우가 많다.
• Alpha는 색상의 불투명도를 나타내는데, 이는 색상 혼합에 유용하다.
• Alpha를 색상 Vector에 추가함으로서 하나의 색상은 각 성분 별 32bit float형으로 총 128bit로 표현된다.
  • 수학적으로는 하나의 4차원 Vector이므로, 코드상에서도 그냥 XMVector를 이용한다.
  • 그러면 XNA Math 라이브러리의 Vector 함수들로 연산 할 때 SIMD의 이득을 취할 수 있다
• 색상 Vector의 Modulate에 대해서는 XNA Math 라이브러리의 다음 함수를 사용한다.

XMVECTOR    XM_CALLCONV     XMColorModulate(FXMVECTOR C1, FXMVECTOR C2);

32비트 색상

• 각 성분당 1Byte를 할당해서 32bit로 하나의 색상을 표현할 수도 있다.
  • 성분 당 0에서 255로 16,777,216가지의 색을 표현하는 것이 가능하다.
• XNA Math 라이브러리는 이를 위해 다음 구조체를 제공한다.

struct XMCOLOR {
  union {
    struct {
      uint8_t b;
      uint8_t g;
      uint8_t r;
      uint8_t a;
    };
    uint32_t c;
  };
  void         XMCOLOR();
  void         XMCOLOR(
    const XMCOLOR & 
  );
  XMCOLOR &    operator=(
    const XMCOLOR & 
  );
  void         XMCOLOR(
    XMCOLOR && 
  );
  XMCOLOR &    operator=(
    XMCOLOR && 
  );
  XM_CONSTEXPR XMCOLOR(
    uint32_t Color
  );
  void         XMCOLOR(
    float _r,
    float _g,
    float _b,
    float _a
  );
  void         XMCOLOR(
    const float *pArray
  );
  void         operator uint32_t();
  XMCOLOR &    operator=(
    const uint32_t Color
  );
};

https://docs.microsoft.com/en-us/windows/win32/api/directxpackedvector/ns-directxpackedvector-xmcolor

• 32bit 색상을 128bit 색상으로 바꿀 때는 각 성분을 255로 나누면 된다.
• 반대로 128bit 색상을 32bit 색상으로 바꿀 때는 각 성분을 255를 곱하면 된다.
  • 단, 32bit 색상은 4개의 8bit 색상 성분을 하나의 32bit 정수형 자료형(ex. unsigned int)에 넣은 형태이다.
  • 때문에 추가적인 비트 연산이 필요하다. 이는 XMCOLOR도 해당된다.
• 이에 대해서 XNA Math 라이브러리는 다음 함수를 제공한다.

XMVECTOR XM_CALLCONV XMLoadColor(
  const XMCOLOR *pSource
);

• 반대로 XMVECTOR 색상을 XMCOLOR로 변환하는 함수도 제공한다.

void XM_CALLCONV XMStoreColor(
  XMCOLOR   *pDestination,
  FXMVECTOR V
);

• 하지만 이 함수들과 XMColor는 DirectX11이나 DirectXPackedVector.h에 존재한다.
• DirectX12 예시에서는 XNA Math가 아니라 DirectXMath.h를 사용하는데, 이 안에 흔적을 찾을 수 없었다.
  • 아무래도 DirectX12에 와서는 일반 XMUInt4를 사용하는 것 같다.

struct XMUINT4
{
    uint32_t x;
    uint32_t y;
    uint32_t z;
    uint32_t w;

    XMUINT4() = default;

    XMUINT4(const XMUINT4&) = default;
    XMUINT4& operator=(const XMUINT4&) = default;

    XMUINT4(XMUINT4&&) = default;
    XMUINT4& operator=(XMUINT4&&) = default;

    XM_CONSTEXPR XMUINT4(uint32_t _x, uint32_t _y, uint32_t _z, uint32_t _w) : x(_x), y(_y), z(_z), w(_w) {}
    explicit XMUINT4(_In_reads_(4) const uint32_t *pArray) : x(pArray[0]), y(pArray[1]), z(pArray[2]), w(pArray[3]) {}
};

XMVECTOR    XM_CALLCONV     XMLoadUInt4(_In_ const XMUINT4* pSource);
void        XM_CALLCONV     XMStoreUInt4(_Out_ XMUINT4* pDestination, _In_ FXMVECTOR V);

• 다시 돌아와, 128bit 색상은 Pixel Shader와 같이 다수의 색상 연산이 진행되는 곳에 쓰인다.
  • 정밀도를 위한 비트가 많으므로 산술 오차가 과도하게 누적되는 일이 없기 때문이다.
• 하지만 최종적인 Pixel 색상은 일반적으로 Back Buffer에 32bit로 저장된다.
• 현재의 물리적 디스플레이 장치들은 고해상도 색상의 장점을 취하지 못한다.

몇일 휴식기를 가지다 보니 집중력과 체력이 부족해 코드를 짜지는 못했습니다.

대신 간단한 수도 코드를 짜놓았고, 내일 이를 구현하고자 합니다.

#sort ascendent price, descendent weight
if weight < need
	if price > iter.price
    	before = price = iter.price
    else 
    	if before == iter.price
        	price += iter.price
        else 
        #price is always same or bigger than before.
        	before = price = iter.price
else
	if price > iter.price && before != iter.price
    	before = price = iter.price
weight += iter.price