일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- shader
- 핵심 API로 배우는 윈도우프로그래밍
- MFC
- 컴퓨터 구조
- 오픈지엘
- Mesh Processing
- win32
- modeling
- 윈도우 프로그래밍
- Graphics
- 그래픽스
- MFC 윈도우 프로그래밍
- 윈도우
- denoising
- 셰이더
- 윈도우 구조
- 윈도우프로그래밍
- 렌더링
- 베지에 곡선
- window programming
- c4d
- OpenGL
- bezier curve
- 운영체제
- Geometry Modeling
- 셰이더프로그래밍
- Win32 API
- 컴퓨터 아키텍쳐
- 그래픽스기초
- shader programming
Archives
- Today
- Total
오다기리 박의 알고리즘 노트
삼각형과 삼각형의 교차점 구하기 본문
삼각형과 삼각형의 교차점을 구하기 위해 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 의 한쪽에만 있으므로 만나지 않는다.
- (1) 만약 dv0, dv1, dv2 이 모두 0이 아니면서 같은 부호라면, 즉, T2 의 세 점이 모두 π1 의 한쪽에만 있으므로 만나지 않는다.
- (2) 만약 du0, du1, du2 이 모두 0이라면 두 삼각형이 같은 평면상에 존재하므로
- 두 삼각형의 외접원이 교차하지 않으면 (두 외심사이의 거리가 두 외접원의 반지름의 합보다 크다면) 만나지 않는다.
- T1 의 모든 에지에 대하여 T2 의 에지와 하나라도 교차한다면(직선과 직선의 교차점 계산을 총 9번 수행) 만난다.
- T1의 정점이 T2에 하나라도 포함되거나 T2의 정점이 T1에 하나라도 포함된다면 (무게 중심 좌표가 모두 양수인지 총 6번 조사) 만난다.
- 그 외의 경우에는 만나지 않는다.
- (3) 만약 du0, du1, du2 이 모두 0이 아니라면 즉, T1 어느 한 점도 π2에 놓여있지 않다면
- T1의 두 에지와 π2 의 교차점 p, q를 구하여(에지와 평면의 교차점 계산을 이용)
- p, q 모두 T2 의 내부에 있다면 만난다.
- p가 T2 내부에 있다면 만난다. (이 때 q 위치를 수정해야 한다.)
- q가 T2 내부에 있다면 만난다. (이 때 p 위치를 수정해야 한다.)
- p, q 모두 T2 외부에 있다면 만난다. (이 때, p, q 위치를 수정해야 한다.)
- (4) 만약 du0, du1, du2 중 두 값만 0이라면 즉, T1의 두 점이 π2 에 포함된다면
- 교차점 p, q (삼각형의 두 정점에 해당됨)를 구하고
- p, q 모두 T2 의 내부에 있다면 만난다.
- p가 T2 내부에 있다면 만난다. (이 때 q 위치를 수정해야 한다.)
- q가 T2 내부에 있다면 만난다. (이 때 p 위치를 수정해야 한다.)
- p, q 모두 T2 외부에 있다면 만난다. (이 때, p, q 위치를 수정해야 한다.)
- (5) 만약 du0, du1, du2 중 한 값만 0이라면 즉, T1의 한 점만 π2 에 포함된다면
- 나머지 두 값이 부호가 같다면 한 점 p를 구하고
- T2 내부에 있다면 만난다.
- T2 외부에 있다면 만나지 않는다.
- 나머지 두 값이 부호가 다르다면 두 교차점 p(삼각형의 한 정점에 해당됨), q(에지와 평면의 교차점 계산 이용)를 구하고
- p, q 모두 T2 의 내부에 있다면 만난다.
- p가 T2 내부에 있다면 만난다. (이 때 q 위치를 수정해야 한다.)
- q가 T2 내부에 있다면 만난다. (이 때 p 위치를 수정해야 한다.)
- p, q 모두 T2 외부에 있다면 만난다. (이 때, p, q 위치를 수정해야 한다.)
- 나머지 두 값이 부호가 같다면 한 점 p를 구하고
각 경우을 아래 그림과 같이 나타냈다.
[참고] Real-time rendering. Akenine-Moller, Tomas, Eric Haines, and Naty Hoffman.
'컴퓨터 그래픽스 > 메쉬 기하학' 카테고리의 다른 글
삼각형 내부점의 무게중심 좌표(barycentric coordinate) 구하기 (3) | 2022.01.26 |
---|---|
네개의 3차원 벡터로 이루어진 행렬 (0) | 2022.01.26 |
직선과 삼각형의 교차점 구하기 (0) | 2022.01.25 |
스칼라 삼중곱 (scalar triple product) (0) | 2022.01.25 |
행렬식(determinant)의 기하학적 의미 (0) | 2022.01.25 |