[GPG 3 글 3.7] gem 3권 3.7 네비게이션 메시에 대한 한 가지 빠른 접근 방식에

GPG 시리즈 관련 질답, 논의 공간.

Moderator: 류광

jinny3d
Posts: 20
Joined: 2004-07-29 17:44

gem 3권 3.7 네비게이션 메시에 대한 한 가지 빠른 접근 방식에

Post by jinny3d »

책의 내용을 보면서 잘 이해가 가지 않는 부분이 있어서 질문 드립니다.
388쪽 테이블 만들기에서 이웃한 삼각형을 찾는데 외심과 홍수 채우기를 사용한다고 되어
있는데, 외심으로 어떻게 삼각형이 옆에 있는지 알수 있을까요?

첫번째 생각할 수 있는게
모든 삼각형의 외심을 구하고, 외심과의 거리로 측정하는 방법인데,
인접한 삼각형의 모양에 따라서 바로 인접해 있지만, 외심과의 거리는
상당히 멀어집니다.
그리고 모든 삼각형이 3개의 인접 삼각형을 가지고 있다는 보장도 없습니다.
2개일수도 있고, 3개일 수도 있고
작도를 해 본 결과 정확하게 나오지 않는다고 판단했구요.

2번째 방법은 외심을 구하고 모든 삼각형의 버텍스로 거리 계산을 하는 겁니다.
2개의 버텍스에서 외심과의 거리가 같다면 인접해 있다고 판단하고..
이 방법을 쓰면 꽤 정확하게 인접 삼각형을 알 수가 있습니다만,
이 방법 역시 예외적인 경우가 생길 소지가 충분히 있다고 생각합니다.
저 멀리 있는 삼각형의 한 변의 수직 이등분선이 우연하게 외심을 지나갈 수 있을 거 같습니다.

홍수 채우기 알고리즘을 쓴다는 것은 외심만으로 인접한지 안한지 다 찾을 수 있다는 건데,
위 2가지 방법외에 어떤 방법이 있을까요?

그리고 개인적인 생각으로는 외심 구하는 연산도 만만치 않고, 그냥 버텍스 비교로 인접
삼각형을 찾는게 확실하고 더 좋을거란 생각도 해봅니다.
버텍스 비교도 만만치 않은 연산이 들어 가긴 마찬가지겠지만요;;
류광
Posts: 3805
Joined: 2001-07-25 09:00
Location: GPGstudy
Contact:

Post by 류광 »

그 부분이 삼각형들사이의 연결 관계를 생성하는 것은 아닙니다. 인접한 삼각형들에 대한 정보가 이미 존재한다는 가정 하에서, 삼각형 안의 한 점들을 잇는 그래프에 대해 실시간 길찾기 계산을 피하기 위한 참조표를 만드는 것일 뿐입니다.

외심은 그냥 삼각형 안의 한 점을 택하는 수단 중 하나이구요..(외심 대신 무게중심을 택할 수도 있겠죠.)
jinny3d
Posts: 20
Joined: 2004-07-29 17:44

Post by jinny3d »

외심이 항상 삼각형 안에 존재 할 수 없구요
내심이라면 가능하겠지만.

책 내용을 보면 외심과 홍수 채우기로 테이블를 만든다고 되어 있습니다.
테이블은 어떤 삼각형에서 다른 삼각형으로 갈때 포탈(변)들을 지정한 2차원 배열입니다.
이 테이블을 만든다는 것은 인접한 삼각형을 구한다는 의미라 생각합니다

이미 인접한 삼각형의 대한 테이블 만들어져 있다면
다시 다른 참조표가 필요 하진 않다고 생각됩니다.
그 테이블과 현 위치, 목표 위치로 나온 삼각형들을 따라 가기만 하면
되니까요,
그리고 무게중심이나 내심같은 삼각형 안에 중심이 되는 점이 알고리즘 상
필요하지 않습니다.
386쪽과 387쪽에 보면 메시를 무시한 이동 방향 벡터에서 가장 가까운 포탈의 점을
찾기 때문에 굳이 중심이 되는 점을 정해놓을 필요가 없을거 같습니다.
Last edited by jinny3d on 2005-02-28 17:44, edited 2 times in total.
류광
Posts: 3805
Joined: 2001-07-25 09:00
Location: GPGstudy
Contact:

Post by 류광 »

예 외심이 삼각형 바깥일 수도 있습니다. 그 부분은 그냥 저자의 팀이 그런 방법을 선택했다는 것일 뿐입니다... 메시 생성 시 삼각형이 둔각을 가지지 않도록 한다던가 하는 제한 조건이 있다면 외심도 문제가 없겠죠. 그런 제한을 두지 않는다면 무게중심(세 조각들의 면적이 같아지는 점)이 더 적합하겠구요.

마찬가지로 홍수채우기 역시 주어진 그래프에서 모든 노드들을 빼먹지 않고 방문하기 위한 수단으로 선택된 것일 뿐이구요.

어쨌거나 그 둘이 삼각형들 사이의 연결 정보를 생성하기 위한 것은 아닙니다. 연결 정보는 메시 자체에 이미 존재한다는 가정 (사실 메시라는 말 자체에 그런 가정이 포함되어 있습니다)이 깔려 있어야 그 글 전체가 말이 됩니다. 임의의 삼각형 "수프"에서 삼각형들의 연결 정보를 생성하는 것은 다른 차원의 알고리즘입니다.(기본적으로는 정점들의 공유 관계를 점검해야죠...)

(제가 답글을 다는 동안 글을 좀 수정하셨네요.)
jinny3d wrote: ...
이미 인접한 삼각형의 대한 테이블 만들어져 있다면
다시 다른 참조표가 필요 하진 않다고 생각됩니다.
그 테이블과 현 위치, 목표 위치로 나온 삼각형들을 따라 가기만 하면
되니까요,
...
홍수채우기로 만드는 테이블은 http://occam.n4gate.com/move2.html 의 세 번째 아스키 그림(테이블 형태)에 해당하는 것입니다. 두 번째 아스키 그림이 삼각형 연결 관계에 해당하는 것이구요.
jinny3d wrote: 그리고 무게중심이나 내심같은 삼각형 안에 중심이 되는 점이 알고리즘 상
필요하지 않습니다.
386쪽과 387쪽에 보면 메시를 무시한 이동 방향 벡터에서 가장 가까운 포탈의 점을
찾기 때문에 굳이 중심이 되는 점을 정해놓을 필요가 없을거 같습니다.
하나의 삼각형을 대표하는 점, 또는 연결 그래프의 노드가 될 점을 택하는 것이라고 생각하시면 될 것 같습니다.
jinny3d
Posts: 20
Joined: 2004-07-29 17:44

Post by jinny3d »

홍수채우기로 각 노드들을 탐색하기 위한 거라 하셨는데
이미 인접한 삼각형들이 구해지면
굳이 홍수채우기를 사용할 필요가 없습니다.
그냥 인접한 삼각형들을 따라가서 가장 가까운 패스를 찾으면 되니까요
Last edited by jinny3d on 2005-02-28 17:58, edited 1 time in total.
류광
Posts: 3805
Joined: 2001-07-25 09:00
Location: GPGstudy
Contact:

Post by 류광 »

그냥 인접한 삼각형들을 따라가서 가장 가까운 경로를 찾기 위해서는 A* 같은 실시간 길찾기 검색 알고리즘이 필요하겠죠.

그 글의 핵심은 "모든 가능한 경로들"을 담을 테이블을 만들어 두고 단순한 테이블 참조만으로 길을 찾는다는 것이고요. 모든 가능한 경로들을 만들기 위해 홍수 채우기라는 모든 노드들을 방문하는 알고리즘을 사용하는 것입니다.
Last edited by 류광 on 2005-02-28 18:00, edited 1 time in total.
jinny3d
Posts: 20
Joined: 2004-07-29 17:44

Post by jinny3d »

아뇨 실시간 타임에서 하는게 아니라 처음 시작할 때 한번 해주는 겁니다.
그렇게 해 주면, 테이블은 간단히 완성됩니다.
테이블만 있다면, 포탈을 찾기만 하면되죠
jinny3d
Posts: 20
Joined: 2004-07-29 17:44

Post by jinny3d »

이미 인접한 삼각형을 알고 테이블을 구성하기 위해 홍수채우기를 사용한다.
초점이 좀 빗나간거 같네요.
이 쪽으로 좀 더 생각을 해 보고 결과를 올리겠습니다.
류광
Posts: 3805
Joined: 2001-07-25 09:00
Location: GPGstudy
Contact:

Post by 류광 »

참고로, 홍수 채우기라는 말은 일단 잊어버리시고 그냥 "모든 가능한 (시작, 목표) 쌍들에 대해 최단 경로를 찾고 그 결과를 테이블에 채운다"라는 접근방식으로 고민하시는 게 좋을 지도 모르겠습니다....
jinny3d
Posts: 20
Joined: 2004-07-29 17:44

Post by jinny3d »

외심으로 인접 삼각형 구하는 걸 알아 냈습니다.
생각을 조금만 더 하면 될걸을 ;;

처음에 말한 두번째 방법에서, 외심과 거리가 같은 걸 구하면 되고,
멀리 있는 삼각형중 변의 이등분선이 외심을 지날때, 두 버텍스가 외심과의 거리가 같아 지는데
이는 외심과 현재 인접 삼각형들을 구하고자 하는 삼각형의 버텍스의 거리와 서로 틀리게 때문에
외심으로 정확하게 인접한 삼각형을 구할 수 있습니다.

아래의 네비게이션 메쉬가 있을 때
____________
|....... /|......../
|..A../..|..C../
|..../....|..../
|../......|../
|/...B...|/
ㅡㅡㅡㅡ

외심으로 인접 삼각형의 정보를 구하고
A - B
B - A, C
C - B

이 정보를 홍수 채우기 알고리즘을 사용 하여

....A...B...C
+-----------
A| .....B...B
..|
B| A........C
..|
C| B...B.....

이런 테이블을 만들 수 있습니다

참고로 그래프 자료구조는 사용 하지 않구요
좀더 복잡한 도형을 그림으로 올리고 싶은데,
url 링크 걸데가 없어서 아스키로 대신합니다
Last edited by jinny3d on 2005-03-03 10:17, edited 3 times in total.
jinny3d
Posts: 20
Joined: 2004-07-29 17:44

Post by jinny3d »

헉 도형과 표에서 빈칸이 없어 지네요 ;;
왜 그런지....
jinny3d
Posts: 20
Joined: 2004-07-29 17:44

Post by jinny3d »

아.. 외심으로 인접 삼각형 구할 수 없군요 ㅠ.ㅠ;;
구현해 보니 예외적인 경우가 많이 생깁니다.
구현이 끝나면 정리해서 올릴게요..
류광
Posts: 3805
Joined: 2001-07-25 09:00
Location: GPGstudy
Contact:

Post by 류광 »

인접한 삼각형은 그냥 정점들을 비교하면 됩니다. 한 변(꼭지점 두 개)을 공유하는 삼각형이 인접한 삼각형이니까요...
jinny3d
Posts: 20
Joined: 2004-07-29 17:44

Post by jinny3d »

휴.. 이제 구현이 끝이 났네요.
한 120개짜리 메쉬에서 테스트 했는데 잘 돌아 가는군요;

제가 외심과 홍수 채우기에 너무 연연해 쓸데 없이 시간을 너무 많이 빼긴거 같네요
결론은 내부의 적당한 점으로 옆 삼각형으로 가는 포탈을 구하는 거고
홍수 채우기 알고리즘은 재귀 함수로 주위를 계속 채워 나가는 알고리즘인데.
테이블 만들때 최소 뎁쓰의 테이블로 구성할 수 없더군요
큐를 이용한 넓이 우선 탐색으로 테이블을 만드니 정확한 테이블이 구성되었습니다.

<네비게이션 메쉬>

1. 인접 삼각형 구하기
T접합부를 가진 삼각형이 없기 때문에 두개의 버텍스가 같다면 인접 삼각형이라고 판단한다.

2. 인접 삼각형으로 가는 포탈 구하기
* 각 삼각형 마다 미리 내부의 적당한 점을 구한다
(전 밑의 중점과 나머지 버텍스와의 선의 중간점을 내부의 점으로 사용했습니다. 그냥 적당한 내부의 점이면 충분합니다)
* 자신의 내부의 점과 인접 삼각형의 내부의 점을 지나는 벡터를 구한다
* 위에 구한 벡터를 각 변(포탈)과 dot 연산으로 걸치는지 안 걸치는지를 판별할 수 있다.
걸치는 변이 그 삼각형으로 가는 포탈이 된다.

여기 까지 하면 아래와 같은 정보가 구해집니다.
A -> 0(B) // A 옆 B삼각형은 0번 포탈로 인접해 있다.
B -> 1(A), 2(C) // B 옆에 A삼각형은 1번 포탈로 인접해 있다. B 옆에 C삼각형은 2번 포탈로 인접해 있다.
C -> 1(B), 0(D)
D -> 1(C)

3. 테이블 만들기
테이블은 "포탈 인덱스 = 테이블[시작삼각형인덱스][목표삼각형인덱스]"로 이루어 진다.
위의 인접 정보로 그래프가 만들어 집니다.
이 그래프를 넓이 우선 탐색으로 탐색하면서 테이블 내용을 채웁니다.
A 시작점을 기준으로 해서 각 포탈별로 전체 그래프를 넓이 우선 탐색하고,
B 시작점을 기준으로 해서 각 포탈별로 넓이 우선 탐색....
테이블에 포탈인덱스외에 뎁쓰 정보를 추가해서 저장된 뎁쓰보다 낮으면 저장시키고
아니면 탐색하고.
그리면 아래 표가 나옵니다. (뎁쓰 정보는 표시하지 않았음)
...A B C D
A....0..0.0
B.1.....2.2
C.1.1.....0
D.1.1..1...

4. 이동
시작 점의 위치를 테이블에서 찾는다.
목표점의 위치를 테이블에서 찾는다.
그럼 포탈이 튀어 나오죠.
그 포탈과 시작 -> 목표 방향 벡터와 걸치는 지 안 걸치는 지를 판단한다.
BSP에 알고리즘을 보면 선이 앞에 있냐 뒤에 있냐 판단하는 게 있죠
전 그걸 사용했습니다. 기본적으로 Dot 연산으로 구할 수 있습니다.
내부의 점에서 포탈 구하는 거 보다 좀 더 연산이 더 필요합니다.
교차 하면 두개의 직선의 방정식을 풀면 되고,
교차 하지 않으면, 포탈의 양 끝 점 중 가장 가까운 점을 찾으면 되는데.
단순히 포탈의 양 끝점이 목적지랑 가까운 걸 찾으면 바보처럼 움직이는 경우가
발생합니다. 여기서 "현재 위치에서 포탈의 끝 점으로 이동하는 거리+끝점에서 목적지의 거리"로
계산을 해주면, 대부분 해결이 됩니다.
몬스터에게 적용을 했구요
처음 몬스터 위치가 할당될 때만 어느 삼각형인지 메쉬 삼각형을 다 돌아서 찾고
포탈 점에 도착하면 포탈에 연결된 옆 삼각형 인덱스를 할당하는 식으로 이동했습니다.
한 버텍스에 많은 삼각형이 몰려 있을때, 살짝 떨리는 문제가 있는데, (코너같은 경우)
위치를 계산해서 계속 이동시키지 않고, 그 위치에서 정지 하게 하는 방식으로 해결했습니다.
보통 많이 몰려 있는 경우가 4개정도 되는데요, 4틱정도 멈춰 있게 되는 거죠
코너에서 회전 하는 루틴을 넣으면 삼각형 갯수 이상의 틱(시간)을 벌수 있기 때문에 상관없을 듯합니다
지금은 코너돌 때 휙휙 돕니다. ;;;
그리고 메쉬를 처음 잘 만들어야 합니다.
쓸데 없는 버텍스가 많으면 바보처럼 움직입니다.

외심과 홍수채우기에 연연해서 좀 삽질을 했는데.
조언해 주신 류광님게 감사드립니다.
그리고 좋은 알고리즘을 공개해준 NaughtyDog 개발진에게도 감사의 말을..
Post Reply