[그래픽스] 삼각형과 광선의 충돌

이전까지는 구의 방정식을 이용해 구를 그렸다.

컴퓨터는 삼각형 여려개를 모아서 삼각형 메시(Triangle Mesh)로 물체를 그려낼 수 있다.

그래픽카드의 성능은 이 삼각형을 얼마나 빠르게 처리할 수 있느냐가 하나의 성능의 기준이 된다.

 

[주의]

레이 트레이싱에서 삼각형을 그리는 방법과 리얼타임 렌더링 파이프라인에서 삼각형을 그리는 방법은 다르다.

이번에 다룰것은 레이 트레이싱에서 삼각형을 다루는 방법이다.

 

삼각형

• 삼각형은 세개의 점이 주어지면 반드시 한 평면으로 정의된다.
• 사각형의 경우에는 임의의 4개의 점으로 반드시 한 평면으로 정의된다고 할 수 없다.
• 한 점, 즉 한 정점을 Vertex라고 부른다.

 

어떻게 그리냐?

1. 시점(눈)위치에서 ray를 쏜다.
2. 3개의 점으로 정의되는 평면과 충돌하는 지점을 찾는다.(삼각형 평면이 아니라, 3개의 점으로 정의되는 평면 전체, 즉, 그냥 무한히 넓은 평면 전체)
3. 그 충돌지점이 삼각형 안인지, 밖인지 판단한다.

삼각형을 그리는 기본 원리

삼각형과 광선의 충돌

1. 정점 세 개 (v0, v1, v2)로 삼각형 하나를 정의할 수 있다.
2. 광선 하나가 시작점 o에서 d(유닛벡터)라는 방향으로 간다.
3. 이 광선이 삼각형이 있는 평면에 부딪힌다면 그 충돌 위치(p)가 어디겠는가를 알아내는 것이 목표
4. p = o + td (t만 찾으면 p를 찾을 수 있다.)
5. 그럴려면 삼각형의 face normal vector n를 구해야 한다.
6. cross product의 성질을 이용하면 삼각형에서 수직으로 나오는 벡터를 쉽게 구할 수 있고
7. 이 벡터를 normalize 만 하면 된다.
8. directX 는 왼손좌표계를 사용한다. (corss product 할때는 곱하는 순서가 중요하다)
9. (p-v0) dot n = 0 (수직이니까) 같은이유로 v1, v2와 p와의 벡터도 마찬가지
10. (o + td - v0) dot n = 0 (4번식의 p부분에 9번식 대입) 
11. t = ((v0 dot n) - (o dot n)) / (d dot n)
12. 이제 삼각형 안인지 밖인지를 파악해서 삼각형 안이면 그려주고, 밖이면 안그려주면 된다.
13. 어떻게 판단하느냐, 삼각형은 p를 기준으로 3개의 삼각형으로 쪼갠다.
14. 각 3개의 삼각형에 대한 face normal vector를 구한다. n0, n1, n2
15. 만약 p가 삼각형 안에 들어있다면 n0, n1, n2가 n과 같은 방향일것이다.
16. 즉, v0를 구하고 n0 dot n == 1이면 같은 방향일것이다.
17. 그런데, float로 연산을 하다보면 오차가 발생하고 반드시 1로 같을것이라는 보장이 전혀 없다. (이것땜에 고민을 많이 했다.)
18. (n0 dot n > 0) && (n1 dot n > 0) && (n2 dot n > 0) 조건만 만족하면 삼각형 안이라고 할 수 있다.
    • 왜냐하면, 이미 p는 한 평면안에 있는 점이기 때문이다.
    • 만약 삼각형 밖의 점 p로 같은 계산을 해 보면 n012의 방향이 완전히 반대 방향으로 나온다.

1~11 번 설명

12 ~18 설명

구현 화면

	class Triangle : public Object
	{
	public:
		vec3 v0, v1, v2;
		// vec2 uv0, uv1, uv2; // 뒤에서 텍스춰 좌표계로 사용

	public:
		Triangle()
			: v0(vec3(0.0f)), v1(vec3(0.0f)), v2(vec3(0.0f))
		{
		}

		Triangle(vec3 v0, vec3 v1, vec3 v2)
			: v0(v0), v1(v1), v2(v2)
		{
		}

		virtual Hit CheckRayCollision(Ray &ray)
		{
			Hit hit = Hit{-1.0, vec3(0.0), vec3(0.0)};

			vec3 point, faceNormal;
			float t, u, v;
			if (IntersectRayTriangle(ray.start, ray.dir, this->v0, this->v1,
									 this->v2, point, faceNormal, t, u, v))
			{
				hit.d = t;
				hit.point = point; // ray.start + ray.dir * t;
				hit.normal = faceNormal;

				// 텍스춰링(texturing)에서 사용
				// hit.uv = uv0 * u + uv1 * v + uv2 * (1.0f - u - v);
			}

			return hit;
		}

		// 수학 프로그래밍을 좋아하시는 분들은 직접 구현해보시면 좋고,
		// 대부분은 개념만 이해해두시고 활용하는 방향으로 접근하셔도 충분합니다.
		// 잘 이해가 가지 않는다면 여러 자료로 교차 검증하면서 공부하시는 방법도
		// 좋습니다. 참고:
		// https://www.scratchapixel.com/lessons/3d-basic-rendering/ray-tracing-rendering-a-triangle/ray-triangle-intersection-geometric-solution
		bool IntersectRayTriangle(const vec3& orig, const vec3& dir,
			const vec3& v0, const vec3& v1,
			const vec3& v2, vec3& point, vec3& faceNormal,
			float& t, float& u, float& v)
		{
			/*
			 * 기본 전략
			 * - 삼각형이 놓여있는 평면과 광선의 교점을 찾고,
			 * - 그 교점이 삼각형 안에 있는지 밖에 있는지를 판단한다.
			 */

			 /* 1. 삼각형이 놓여 있는 평면의 수직 벡터 계산 */
			 // faceNormal = ...;
			 //주의: 삼각형의 넓이가 0일 경우에는 계산할 수 없음
			const vec3 Va = v1 - v0;
			const vec3 Vb = v2 - v0;
			faceNormal = glm::normalize(cross(Va, Vb)); // 왼손 좌표계 사용

			// 삼각형 뒷면을 그리고 싶지 않은 경우 (Backface culling)
			// if (... < 0.0f) return false;
			if (dot(-dir, faceNormal) < 0.0f) // 충돌지점으로부터 광선으로의 방향과 faceNormal 의 코사인 세타 값이 음수이면 뒷면 (90도 넘어가니까)
			{
				return false;
			}

			// 평면과 광선이 수평에 매우 가깝다면 충돌하지 못하는 것으로 판단
			// if (... < 1e-2f) return false; // t 계산시 0으로 나누기 방지
			if (glm::abs(dot(dir, faceNormal)) < 1e-2f)
			{
				return false;
			}
			/* 2. 광선과 평면의 충돌 위치 계산 */
			// t = ...
			t = (dot(v0, faceNormal) - dot(orig, faceNormal)) / dot(dir, faceNormal);

			// 광선의 시작점 이전에 충돌한다면 렌더링할 필요 없음
			// if (...) return false;
			if (t < 0.0f)
			{
				return false;
			}

			point = orig + t * dir; // 충돌점

			/* 3. 그 충돌 위치가 삼각형 안에 들어 있는 지 확인 */

			// 작은 삼각형들 3개의 normal 계산
			// cross product 순서 주의
			const vec3 normal0 = glm::cross(v1 - point, v2 - point);
			const vec3 normal1 = glm::cross(v2 - point, v0 - point);
			const vec3 normal2 = glm::cross(v0 - point, v1 - point);
			
			// 방향만 확인하면 되기 때문에 normalize() 생략 가능
			// 아래에서 cross product의 절대값으로 작은 삼각형들의 넓이 계산

			if (dot(normal0, faceNormal) < 0.0f) return false;
			if (dot(normal1, faceNormal) < 0.0f) return false;
			if (dot(normal2, faceNormal) < 0.0f) return false;

			// Barycentric coordinates 계산
			// 텍스춰링(texturing)에서 사용
			// u = ...
			// v = ...

			return true;
		}
	};