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

다음 그림과 같이 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 에 의해..

선형대수학에서, 크래머 공식은 유일한 해를 가지며 변수와 방정식의 수가 같은 연립 일차 방정식의 해를 구하는 공식이다. 2개의 연립 일차 방정식의 경우 연립 일차 방정식 이 유일한 해를 갖는다면, 그 해는 다음과 같다. 행렬 표현법으로 다시 써보면, 이다. 3개의 연립 일차 방정식의 경우 연립 일차 방정식 이 유일한 해를 갖는다면, 그 해는 다음과 같다. 행렬 표현법으로 다시 써보면, 크래머 공식은 이렇게 계수 행렬과 그 한 열을 상수항으로 대신하여 얻는 행렬들의 행렬식의 비를 통해 해를 구한다. 2~3개 이상의 연립 방정식의 경우 크래머 공식에 의한 알고리즘은 가우스 소거법보다 비효율적이다.

3차원 공간에서 두 직선사이의 교차점을 구해보자. 두 직선의 방정식을 다음과 같이 정의한다. 벡터 자기 자신과 외적을 하면 0벡터가 나온다는 사실을 이용하여 직선의 교점을 다음과 같이 구한다. 위에서 구한 s와 t 가 교차점에서 두 직선의 파라미터이다. 만약에 분모가 0이라면 두 직선은 평행하므로 만나지 않는다. 또한 두 직선이 서로 꼬인(skew) 위치에 있다면 즉, 공통 평면위에 있지 않으면 만나지 않으며 이때 s와 t는 두 직선의 가장 가까운 점을 나타낸다. 두 직선이 유한한 길이의 선분 (line segment)라면 s 와 t 가 0과 1 사이에 있는지도 확인해봐야한다. 이 범위를 벗어나면 선분 밖에서 만난다. [참고] Real-time rendering. Akenine-Moller, Tomas,..