DDT Picking (Bresenham's algorithm)

브레젠험 알고리즘을 이용한 DDT Picking

 

 

 

Bresenham 직선 알고리즘을 이용한 DDT Picking을 구현해 보았습니다.

Bresenham 직선 알고리즘은 주어진 시작점과 끝점을 두고 직선을 만들어 내기위한 알고리즘 입니다.

 

(두점을 안다면 방향을알 수 있으며, 기울기 많큼 증가량으로 직선위의 정점들을 모을 수 있습니다. 이 정점들은 터레인의 유효한 점이 되고,

이 정점들을 포함하는 삼각형 메쉬에 Lay와 삼각형의 교차 판정을 통해 교차하는 유효한 삼각형들을 모을 수 있습니다.

이중 카메라와 거리가 제일 가까운 것이 지금 픽킹된 점이 됩니다.)

1. 카메라의 Ray의 위치와 방향을 지형의 로컬스페이스로 보낸다. 

2. 지형의 로컬스페이스 상의 Ray를 XZ 평면으로 정사영을 내려줍니다.

3. Terrain을 통과하는 유효한 직선인지를 판단합니다.

4. 유효한 직선이 지나는 Triangle patch들을 잡아줍니다.

5. Triangle patch와의 최단거리 * 정사영을 내리지 않은 지형의 로컬스페이스 상의 Ray뱡항 + 위치
가 픽킹된 좌표가 됩니다. 

Terrain을 모두 순회 하면서 Picking된 좌표를 찾은 경우 : O(n^2)

DDT픽킹을 통해 좌표를 찾는 경우 : O(n) + α