오다기리 박의 알고리즘 노트

아래 그림과 같이 3차원 공간에서 평관과 박스의 교차 여부를 검사해보자. 박스의 모든 점들을 평면의 방정식에 대입하여 모든 sigend distance값이 같은 부호라면 교차하지 않고, 부호가 다른값이 나왔다면 정점들이 평면의 양쪽에 존재하므로 둘은 교차하게 된다. 여기서는 AABB와 OBB 각각 다른 방식을 소개한다. 두 방식 모두 박스의 두 점만 평면의 방정식에 대입해보면 된다. 여기서 박스의 두 점은 박스의 중심을 지나는 4개의 대각선들 중 평면의 법선과의 내적값이 가장 큰 대각선의 두 점을 말한다. 우선 박스 B에서 양 끝점, 대각선의 half 벡터, 중심점을 다음과 같이 나타낸다. half 벡터 h는 박스에서 양 끝점을 어떻게 잡느냐에 따라 총 8개를 구할 수 있다. 이제 다음 그림처럼 3차원 ..

3차원 공간에서 직선과 평면의 교점을 구해보자. 아래 그림과 같이 3차원 공간에 직선과 평면이 존재한다고 하자. x는 평면위의 임의의 점이다. 교점을 찾기 위해서는 직선의 방정식의 파라미터 t*를 구해야 한다. 우선 예외처리를 위해 다음과 같이 직선의 방향벡터와 평면의 법선의 내적이 0인지 조사한다. 두 벡터의 내적이 0이라면 서로 수직하므로 직선이 평면과 평행하거나 평면에 완전히 포함되어 있는 경우다. 이 때는 교점이 존재하지 않는다. 그 외의 경우에는 직선 위의 점 r(t*)을 평면의 방정식에 대입하여 t* 를 구한다.

다음 그림과 같이 3차원 공간의 삼각형 pqr내부에 점 a가 있을 때 이 점의 무게중심 좌표 (α, β, γ)를 구해보자. 삼각형 pqr과 점 a는 같은 평면 위에 존재한다고 가정한다. 이 말은 α, β, γ의 합이 1이라는 것을 뜻한다. 점 a의 위치가 첫번째 정점 p와 같다면 (α, β, γ) = (1, 0, 0), 점 a의 위치가 두번째 정점 q와 같다면 (α, β, γ) = (0, 1, 0), 점 a의 위치가 세번째 정점 r와 같다면 (α, β, γ) = (0, 0, 1) 이다. 그 외 일반적인 경우에는 우선 세번째 정점 r을 기준으로 벡터를 만들어보자. 그러면 (α, β, γ) 에 대하여 다음 식이 성립한다. 그리고 다음과 같이 선형 시스템으로 다시 표현할 수 있다. 그런데 이 식은 방정식이 3..

4개의 3차원 벡터 a, b, c, d 로 이루어진 4x4 행렬을 생각해보자. 연산 [a, b, c, d] 에 대해서 다음이 성립한다. 위 식을 직관적으로 살펴보면, (b - a) X (c - a)는 삼각형 abc의 법선으로 볼 수 있다. 이 법선과 a에서 d로 향하는 벡터를 서로 내적하면 점 d가 삼각형 abc에 위쪽에 있는지 아래쪽에 있는지 알 수 있다. 결론적으로, 4개의 3차원 벡터로 이루어진 행렬의 행렬식을 계산해서 마이너스 부호를 붙여보면 네 번째 점 d가 삼각형 abc의 위쪽방향에 위치하는지, 아래쪽 방향에 위치하는지를 판별할 수 있다.

삼각형과 삼각형의 교차점을 구하기 위해 interval overlap 방식과 ERIT 방식을 사용한다. 다음과 같이 두 평면 π1, π2 에 존재하는 삼각형 T1, T2 가 있다고 할 때 이들이 서로 교차하는지 검사해보자. 일반적으로 두 평면이 만나는 경우 교차선은 L 에 해당되는데, 삼각형이 서로 만난다면 직선 위의 빨간 구간이 서로 겹치게 될 것이다. 우선 삼각형 T1 의 각각의 정점과 평면 π2 사이의 부호 거리(signed distance) du0, du1, du2 및 삼각형 T2 의 각각의 정점과 평면 π1사이의 부호 거리 dv0, dv1, dv2 를 계산해본다. (1) 만약 du0, du1, du2 이 모두 0이 아니면서 같은 부호라면 즉, T1 의 세 점이 모두 π2 의 한쪽에만 있으므로 만..

일반적으로 직선과 삼각형의 교차점을 구할 때 가장 먼저 직선과 삼각형이 포함된 평면과의 교차점을 먼저 계산한다. 그 다음에 교차점과 삼각형 정점들을 좌표 평면들(xy, yz, xz) 중 하나에 투영시킨다. 이 때 투영면은 삼각형의 면적을 최대화하도록 한다. 이렇게 2차원 문제로 축소시켜서 2차원 점이 2차원 삼각형 내부에 있는 판단하면 된다. 다음과 같이 3차원 공간에서 직선과 삼각형이 정의된다고 하자. 여기서 α, β는 α >= 0, β >= 0, α + β

스칼라 삼중곱은 벡터 3개를 곱하는 방법을 말한다. 우선 두 벡터를 외적하면 벡터가 나오고 거기에 다른 벡터를 내적하면 결과가 스칼라가 나온다. 결과값이 스칼라라서 스칼라 삼중곱이라는 이름이 붙었다. 계산법과 간단한 기하학적 의미를 알아보자. 정의 스칼라 삼중곱은 두 벡터의 외적을 나머지 벡터와 내적한 것으로 정의된다. 기하학적 의미 스칼라 삼중곱의 절댓값은 세 벡터로 정의되는 평행 육면체의 부피로 정의된다. 행렬의 관점에서 보면, 세 벡터로 정의되는 평행 육면체의 부피는 세 벡터로 이루어진 행렬의 행렬식의 절댓값과도 같다. 성질 스칼라 삼중곱은 다음과 같이 벡터의 순서를 바꿀 수 있다. 만약, 스칼라 삼중곱이 0이면 세 벡터는 모두 동일한 평면 위에 있다.

선형대수학에서 말하는 행렬식은 기하학적으로 어떤 의미가 있을까? 2x2로 이루어진 2차 행렬식과 3x3으로 이루어진 3차 행렬식의 기하학적인 의미에 대해서 알아보자. 2차 행렬식의 기하학적 의미 다음과 같이 좌표평면 위의 두 점 P, Q 와 원점 O가 만드는 삼각형 OPQ가 있다고 하자. 삼각형 OPQ의 넓이는 다음과 같이 계산될 수 있다. 행렬 A를 다음과 같이 정의하면 결론적으로 삼각형 OPQ의 넓이는 A의 행렬식(determinant)의 절반이 된다. 3차 행렬식의 기하학적 의미 이제 3차원 공간에의 행렬식의 기하학적 의미를 살펴보자. 다음과 같이 3차원 공간의 세 벡터 로 이루어지는 평행사변형을 생각하자. 세 벡터 x, y, z 에 의해 만들어지는 평행육면체의 부피는 다음과 같이 x, y 에 의해..