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

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

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

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

---

🎄 K-D tree

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

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

1. K-D tree 구성

2. K-D tree 순회

---

⚙️ K-D tree 구성

🔻 root 노드 생성

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

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

 

---

🧒 child 노드 생성

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

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

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

 

---

📈 충돌 검사 최적화

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

 

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

---

💥 SAT 충돌 검사

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

 

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

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

 

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

 

투영 과정은 다음과 같다:

 

---

✈️ K-D tree 순회

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

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

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

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

임의의 점 pos에서, 트리 순회를 통해 B1-2라는 노드에 속한 것을 확인한다.

이후, 가장 가까운 정점과의 거리를 range로 설정한다.

 

range 범위 내에 있는 boundary를 가진 모든 노드를 순회하며 가장 가까운 삼각형 메시를 탐색한다.

 

➡️ 위의 과정을 통해 가장 가까운 삼각형 메시를 찾고, 이전 글에서 다룬 삼각형-정점 최단 거리 계산 방법을 통해 최소 거리를 계산할  수 있다.

---

💻 결과

이전 글과 동일하게 SDF를 생성하고, OpenCV를 통해 2차원 이미지를 출력할 결과이다.

➡️ 이전 기법과는 다르게, 하이폴리곤 모델(dragon 등),에 대해서도 출력할 수 있을 정도의 속도를 확인할 수 있었다.

다음으로, 생성된 SDF를 기준으로 regular 그리드에 대해 모델 내부에 포함된 점들을 시각화한 결과이다:

 

마지막으로, 생성된 SDF를 가지고 충돌처리를 하는 결과이다:

 

 

 

➡️ 위 결과의 빨간색 점은 충돌 지점을 의미한다.

---

참고 자료:

SDF:

https://mshgrid.com/2021/02/07/computing-the-sign-of-discrete-distance-fields/

---

AABB tree:

https://mshgrid.com/2021/01/17/aabb-tree/

---

K-D tree:

https://www.baeldung.com/cs/k-d trees#:~:text=A%20K%2DD%20Tree%20is%20a,one%20of%20the%20K%20dimensions.

---

깃허브:

https://github.com/qkrdmstn/pbd-sdf-collision.git

GitHub - qkrdmstn/pbd-sdf-collision