문제에서 주어진 의사코드를 3차원배열을 선언해주고 조건에 해당하는 값이라면 재귀함수를 통해 이 3차원배열을 초기화해주고 만약 이미 있는 값이라면 그 값을 반환해주는 방식으로 DP를 활용하는 방식이다.
정답코드
#include <iostream>
using namespace std;
int dp[51][51][51];
int w(int a, int b, int c)
{
if (a <= 0 || b <= 0 || c <= 0)
return 1;
if (a > 20 || b > 20 || c > 20)
return w(20, 20, 20);
// 이미 저장된 값이 있다면 재활용 : DP
if (dp[a][b][c] != 0) {
return dp[a][b][c];
}
if (a < b && b < c)
{
dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
}
else
{
dp[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}
return dp[a][b][c];
}
int main()
{
int a, b, c;
while (true)
{
cin >> a >> b >> c;
if (a == -1 && b == -1 && c == -1) break;
cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << endl;
}
return 0;
}
우선 위처럼 하나의 정육면체 큐브를 만든다고 했을 때 이 큐브가 어떻게 만들어지는 지 생각해보자.
이 큐브도 렌더링파이프라인을 모두 거쳐서 나오게 될 것이다.
우선 IA 단계에서 정점과 인덱스 정보를 묘사하는 아이인 Input Layout을 통해 넘겨주고 이를 VS단계에서 카메라에 어떻게 보이게 되는지 행렬곱 연산을 적용시켜 줄 것이다. 그리고 RS단계에서 색상을 보간해줘서 위와 같이 보이게 해야할 것 이다. 그렇게 해주려면 정점과 색상에 대한 정보가 있어야 할 것이다.
코드를 살펴보자면 우선 vertexBuffer와 indexBuffer에 정보를 채워서 GPU쪽에 보내줘야한다.
그 다음에는 렌더타켓뷰와 깊이 스텐실뷰를 클리어해주는 것으로 그림 그릴 도화지를 밀어주고 IA단계의 인풋레이아웃을 묘사한 부분을 실제 DeviceContext와 연결시켜주고 물체를 어떤 기본 물체로 그려줄지 세팅하는 토폴로지 단계를 하는 것을 볼 수 있다. 정점버퍼와 인덱스버퍼도 연결시켜준다.
이제 여러물체를 만들고 이 모든 물체가 나를 바라보도록 만들어보자. 물체를 많이 만들어줄 때 인스턴싱을 우리가 사용했었는데 이 방법을 빌보드로 적용시키려면 정점을 우선 넘겨주고 쉐이더에서 각 정점의 위치를 고정시켜주거나 기본 정점을 가지고 이 정점을 여러개로 늘려주는 작업을 Geometry 쉐이더에서 해줄 수도 있다.
지금은 물체를 여러개 만들어주는 것이 아니라 정점을 여러개로 늘려서 쉐이더에 건네주고 첫 위치를 일단은 건네준 다음에 그 자체를 일단 하나의 통 매쉬로 만들어서 건네주고 세부적인 메쉬둘 간의 좌표 계산을 쉐이더에서 해주도록 하자.
매쉬를 늘리는 것처럼 정점을 늘리는 방식으로 만들고 이 정점을 묶어서 한번만 건네주면 된다. 이때 위치는 고정되어있고 바뀌지않는다. 이렇게 해주기 위해 Geometry클래스처럼 정점과 인덱스 정보를 넘겨줄 수 있게 만들어주자. 이때 위치와 스케일을 동일하게 해서 쉐이더쪽에 전달해주게 되는데 이렇게 하는 이유는 좌표와 스케일 연산을 쉐이더쪽에서 해주기 위해서 이다.
BillBoard.h
#pragma once
#include "Component.h"
struct VertexBillboard
{
Vec3 position;
Vec2 uv;
Vec2 scale;
};
//정점 최대개수
#define MAX_BILLBOARD_COUNT 500
class Billboard : public Component
{
using Super = Component;
public:
Billboard();
~Billboard();
void Update();
//만들어줄 위치
void Add(Vec3 position, Vec2 scale);
void SetMaterial(shared_ptr<Material> material) { _material = material; }
void SetPass(uint8 pass) { _pass = pass; }
private:
vector<VertexBillboard> _vertices;
vector<uint32> _indices;
shared_ptr<VertexBuffer> _vertexBuffer;
shared_ptr<IndexBuffer> _indexBuffer;
//그려줄 애들의 수
int32 _drawCount = 0;
//그려준 애들의 수 - 바뀔때만 갱신
int32 _prevCount = 0;
shared_ptr<Material> _material;
uint8 _pass = 0;
};
조합을 통해 풀 수 있는 문제이다. mCn을 통해 다리를 지을 수 있는 경우의 수를 출력해주면 된다.
정답코드
#include <iostream>
using namespace std;
int combination(int n, int k) {
if (k > n - k) k = n - k; // 계산량을 줄이기 위해 k를 더 작은 값으로 설정
long long result = 1;
for (int i = 0; i < k; i++) {
result *= (n - i);
result /= (i + 1);
}
return result;
}
int main()
{
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
int n, m;
cin >> n >> m;
cout << combination(m, n) << endl;
}
}
3D 그래픽스에서 가장 기본적인 구성 단위 중 하나인 Triangle의 Point Test와 Intersection, Raycast에 대해 알아보자 이 삼각형을 통해 우리는 네비게이션 매쉬(갈 수 있는 범위를 정해준다.)와 같은 요소를 만들어 줄 수 있다.
1. Point Test
만약 삼각형을 클릭했을 때 그것을 판별해야한다고 할 때 Point Test를 하게 될 것이다. 이때 삼각형을 구성하는 벡터들을 사용해서 교차 벡터를 계산하고 이들의 내적을 검사해준다.
// 점이 삼각형 내부에 있는지 판단하는 함수
bool MathUtils::PointInTriangle(const Point3D& p, const Triangle3D& t)
{
Vec3 a = t.a - p; // 점 p에서 삼각형의 꼭짓점 a로의 벡터
Vec3 b = t.b - p; // 점 p에서 삼각형의 꼭짓점 b로의 벡터
Vec3 c = t.c - p; // 점 p에서 삼각형의 꼭짓점 c로의 벡터
// 삼각형의 각 변에 대해 점 p를 포함하는 평면의 법선 벡터 계산
Vec3 normPBC = b.Cross(c); // PBC의 법선 벡터 (u)
Vec3 normPCA = c.Cross(a); // PCA의 법선 벡터 (v)
Vec3 normPAB = a.Cross(b); // PAB의 법선 벡터 (w)
// 법선 벡터들의 방향이 모두 같은지 확인하여 점이 삼각형 내부에 있는지 판단
if (normPBC.Dot(normPCA) < 0.0f)
return false; // PBC와 PCA 법선 벡터가 서로 반대 방향이면 점은 삼각형 내부에 없음
else if (normPBC.Dot(normPAB) < 0.0f)
return false; // PBC와 PAB 법선 벡터가 서로 반대 방향이면 점은 삼각형 내부에 없음
return true; // 그 외의 경우 점은 삼각형 내부에 있음
}
※벡터 투영
투영은 벡터에서 다른 벡터의 선분을 구하기 위한 함수로 정사영이해서 비율을 알 수 있다.
// 벡터 a를 벡터 b에 투영하는 함수
Vec3 MathUtils::ProjectVecOnVec(Vec3 a, Vec3 b)
{
b.Normalize(); // 벡터 b를 정규화
float dist = a.Dot(b); // 벡터 a와 정규화된 벡터 b의 내적 계산
return b * dist; // 투영된 벡터 반환
}
2. Intersection
충돌 검사는 삼각형을 구성하는 점으로 평면 방정식을 생성하고 이를 통해 충돌과 물리 계산을해주면 된다.
// 삼각형으로부터 평면을 생성하는 함수
Plane3D MathUtils::FromTriangle(const Triangle3D& t)
{
Plane3D result;
// 삼각형의 두 변의 벡터를 외적하여 평면의 법선 벡터를 계산
result.normal = (t.b - t.a).Cross(t.c - t.a);
result.normal.Normalize(); // 법선 벡터를 정규화
// 평면의 거리 계산 (법선 벡터와 삼각형의 한 꼭짓점의 내적으로 계산)
result.distance = result.normal.Dot(t.a);
return result;
}
3. Raycast
삼각형과 레이케스팅의 충돌 검사는 위의 코드로 만들어준 평면을 통해 교차점을 찾아주면 된다.
//삼각형 내의 점에 대한 바리센트릭 좌표를 계산
Vec3 MathUtils::Barycentric(const Point3D& p, const Triangle3D& t)
{
return Vec3();
}
// 레이와 삼각형의 충돌 검사
bool MathUtils::Raycast(const Triangle3D& triangle, const Ray3D& ray, OUT float& distance)
{
Plane3D plane = FromTriangle(triangle); // 삼각형으로부터 평면 생성
float t = 0;
// 레이와 평면의 충돌 검사
if (!Raycast(plane, ray, OUT t))
return false; // 충돌하지 않으면 false 반환
// 충돌 지점 계산
Point3D result = ray.origin + ray.direction * t;
// 충돌 지점에 대한 바리센트릭 좌표 계산
Vec3 barycentric = Barycentric(result, triangle);
// 바리센트릭 좌표를 사용하여 충돌 지점이 삼각형 내부에 있는지 확인
if (barycentric.x >= 0.0f && barycentric.x <= 1.0f &&
barycentric.y >= 0.0f && barycentric.y <= 1.0f &&
barycentric.z >= 0.0f && barycentric.z <= 1.0f)
{
distance = t;
return true;
}
return false; // 충돌하지 않음
}
