3D길찾기를 시도하면서 큰 목표중 하나가 복셀맵에서 길찾기를 하는것이었다.
marching cube알고리즘으로 일단 voxel지형에서 삼각형을 생성할 수 있다. 이걸 네비게이션 매시로 사용해서 길찾기를 하면 되기는 하는데…..문제가 있다.
- 복셀 매시로부터 삼각형 매시를 생성.
- 삼각형이 미친듯이 많이 나온다.
- 복셀 매시로부터 생성한 삼각형을 최적화.
- 인접한 삼각형간에 엣지를 공유할 수 없게 된다.
- 엣지를 공유하지 않으므로 네비게이션 매시로 사용할 수 없게 된다.
- 두 삼각형이 위치상으로 인접해있고 자료구조상으로는 엣지를 공유하지 않는 경우 양쪽 삼각형의 엣지가 겹치는 영역을 계산하여 부분엣지를 만들어주고 이 부분엣지 기준으로 삼각형을 연결한다.
- 삼각형 베이스 맵에서도 충돌매시를 네비게이션 매시로 사용할 경우에도 두 삼각형이 인접해있으나 엣지는 공유하지 않는 경우가 많이 발생한다. 이 경우도 이 방법으로 해결이 된다.
아직 문제가 좀 있긴 한데 의도대로 작동은 한다. 삼각형 베이스 맵과 복셀 맵 각각 어떻게 적용할지 정책을 맞춰가야겠다.
yuchi's development 