[ Cloth Simulation & Collision ] 06. SDF 생성

🔳 SDF 생성

✅ 그동안 다뤘던 충돌처리는 방정식으로 표현 가능한 SDF에 대한 방식이었다.

❗ 하지만, 방정식으로 표현 가능한 SDF는 매우 한정적이기 때문에 임의의 삼각형 메시에 대해 SDF를 생성하는 것의 필요하다.

 

이는 크게 세 가지 단계를 거쳐 진행한다:

1. 삼각형-정점 부호 계산 과정

2. 삼각형-정점 거리 계산 과정

3. SDF 생성

---

➕ 삼각형-정점 부호 계산 과정

SDF는 부호화된 거리 영역이기 때문에, 주어진 정점이 임의의 메시에 대해 내부인지 외부인지 부호로 판단할 수 있어야 한다.

 

➡️ 이는 다음과 같이 삼각형이 면 위의 점 $q$ 와 법선 벡터 $n$ 을 가질 때, 내적을 통해 부호를 판단 가능하다:

그러나, 가장 가까운 점 $q$ 가 정점(Vertex)이나 가장자리(Edge)에 위치하면 법선 벡터가 여러 삼각형에 의해 각기 다른 값을 가지게 된다는 문제가 있다.

 

➡️ 이를 해결하기 위해 아래와 같이 angle weighted normal을 사용한다. 이는 각도에 따라 각 면에 대한 법선 벡터에 가중치 법선 벡터를 의미한다.

모든 면의 가중치를 동일하게 하여 법선 벡터의 평균을 사용할 수도 있다.

---

📏 삼각형-정점 거리 계산 과정

거리 계산에는 Barycentric Coordinates라는 개념을 활용해 삼각형의 구성 요소(Face, Edge,Vertex) 중 어디가 정점과 가까운지를 계산한 뒤, 요소와의 거리를 계산하는 과정을 거친다.

---

🛠️ Barycentric Coordinates

어떤 점 $P$ 가 선분 $\overline{AB}$ 에 대해 barycentric 좌표 $(u, v)$ 를 갖는다고 하면 다음과 같이 표현된다:

 

$ \large P = A + t(B-A) = (1-t)A + tB \rightarrow p = uA + vB, where \ \ u+v = 1, \ \ 0 \le u,v \le 1 $

 

➡️ 이때 $u, v$ 는 점 $P$ 가 정점 $A$ 와 $B$ 에서 얼마나 '기여받았는지'를 나타내는 가중치이다.

 

이를 삼각형에 적용 시켜, 임의의 점 $P$ 를 삼각형 메시 위로 투영시킨 뒤, 다음과 같은 식을 통해 각 정점에 대한 영향력 가중치를 설정할 수 있다:

 

$ \large P =  uA + vB + wC, where \ \ u+v+w = 1, \ \ 0 \le u,v,w \le 1 $

 

➡️ 이때, $u,v,w$ 의 부호를 통해 아래와 같이 투영된 정점 즉, closest point가 어느 영역에 위치하는지 알 수 있다:

아래와 같이 각 영역이 의미하는 바는 다음과 같다:

$\text{R1}$: 정점 $p$ 와 가장 가까운 삼각형 위의 점 $q$ 가 면(face) 위에 존재

$\text{R2, R3, R4}$: $q$ 가 가장자리(edge) 위에 존재

$\text{R5, R6, R7}$: $q$ 가 정점(vertex) 위에 존재

---

📐 거리 계산

이때 각 요소에 대해 거리를 계산하는 방법은 다음과 같다:

 

🔻 면(Face)

삼각형의 중점 $c$와 점 $p$ 사이의 거리를 통해 최단 거리를 계산할 수 있다. 

이때, 면의 법선 벡터와 내적하여 부호 및 최단 거리를 구할 수 있다.

---

📏 가장자리(Edge)

삼각형이 가진 세 개의 edge에 대해 점-직선 사이의 거리를 계산하여 최단 거리를 구할 수 있다.

이때, 부호는 edge의 법선 벡터를 사용하여 mesh의 내부/외부를 판단한다.

edge의 법선 벡터는 앞서 설명한 것처럼, 이웃한 면의 법선 벡터 평균을 사용할 수 있다.

---

🔴 정점(Vertex)

삼각형을 이루는 세 정점과의 거리를 계산하고, 최단 거리를 설정한다.

마찬가지로 부호는 인접한 면들의 법선 벡터 평균으로 결정할 수 있다.

---

⚙️ SDF 생성

최종적인 알고리즘은 다음과 같다:

정리

1. 각 정점과 가장자리에 대해 법선 벡터를 계산한다.

2. 모든 면을 순회하며 일정 거리 내의 복셀로부터 거리를 계산하여 최단 거리를 업데이트 한다.

 

이는 전처리 과정으로 수행되며, 시뮬레이션 도중 요구되는 임의의 정점과 삼각형 메시 사이의 거리는 이미 계산된 복셀의 최단 거리로부터 3차원 보간을 통해 계산한다.

---

💻 결과

각각 Sphere와 stanford bunny 오브젝트에 대해 SDF를 계산하고, OpenCV를 활용해 2차원 이미지로 표현한 결과이다.

이를 통해 경계면을 따라 결과가 잘 출력됨을 확인했다.

---

참고 자료:

https://www2.imm.dtu.dk/pubdb/edoc/imm1289.pdf

---

깃허브:

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

GitHub - qkrdmstn/pbd-sdf-collision