[ Cloth Simulation & Collision ] 07. K-D tree를 활용한 SDF 생성 최적화

coding-l7 2025. 5. 16. 15:38

📌 K-D tree를 활용한 SDF 생성 최적화

✅ 앞서 다룬 SDF 생성은 각 면을 순회하면서 주변 복셀에 대한 최단 거리를 모두 계산하기 때문에 중복 계산이 발생한다.

➡️ 이를 해결하기 위해 K-D Tree를 사용하여, 각 복셀에 대해 가장 가까운 삼각형 메시를 찾아 최단 거리를 계산할 수 있다.

K-D tree는 k차원 공간의 점들을 구조화하는 공간 분할 자료 구조이다.

K-D tree의 내용은 다음 두 가지로 나눌 수 있다:

1. K-D tree 구성

2. K-D tree 순회

먼저, tree 구조에 맞게 root 노드 생성을 진행한다.

➡️ 이때 다음 그림과 같이 전체 메시를 포함하는 Boundary와 polygon을 초기화 한다.

자식 노드의 생성 과정은 다음과 같다.

부모 노드의 포함된 polygon 수가 특정 개수 이상이라면, 아래의 과정을 반복한다.
해당 노드 boundary의 가장 긴 축을 기준으로 boundary에 포함된 정점들을 투영 및 정렬한다.
중간 값을 기준으로 2개의 boundary로 구분한다.
자식 노드를 생성하고, 나눈 boundary를 각 자식 노드의 boundary로 설정한다.
부모 노드에 포함된 polygon들을 순회하며, 각 자식 노드의 boundary와 충돌 검사를 통해 자식 노드의 polygon으로 push 한다.

이를 다음과 같이 그림으로 표현할 수 있다:

위의 5번 단계에서 AABB와 삼각형 메시의 정확한 충돌 검사를 진행한다.

이때, 충돌 검사를 최대한 적게 하기 위해 아래와 같이 간단한 min/maxPrimitive를 활용한 충돌 검사를 진행한다:

✅ 앞선 과정에서, 충돌 됐다고 판단된 삼각형 메시에 대해 정확한 충돌 처리를 SAT(Separating Axis Threorem)을 활용해 진행한다.

➡️ 이는 두 다면체의 법선 벡터와 edge의 외적을 이용하여, 축을 기준으로 다면체들을 투영하는 과정을 거친다.

이때, 겹치지 않는 1개의 분리된 축(Seperating Axis)가 존재한다면, 두 다면체는 충돌하지 않는 것으로 판단한다.

아래와 같은 AABB와 삼각형 메시를 기준으로 {AABB의 edge(=3) * 삼각형 메시의 edge(=3)} + {AABB의 법선 벡터(=3) + 삼각형 메시의 법선 벡터(=1)} = 13으로 총 13번의 계산(투영)이 필요하다.

투영 과정은 다음과 같다:

K-D tree의 순회를 통해 임의의 점과 가장 가까운 삼각형 메시를 찾을 수 있다.

tree 순회 과정은 다음과 같다:

각 노드에 저장된 분리된 축과 중간 값을 이용해 현재 정점의 위치가 어느 leaf 노드에 속하는지 탐색$(O(\log{n}) \sim O(n))$
해당 노드에 포함된 정점 중 가장 가까운 것과의 거리를 range로 설정
처음부터 트리 순회를 수행하여, 해당 노드 boundary와의 거리가 range보다 작은 노드들을 탐색한다.
탐색된 노드에 포함된 polygon들이 가장 가까운 삼각형 메시 후보군이다.

각 과정을 다음 그림을 통해 살펴볼 수 있다: