[ Cloth Simulation & Collision ] 05. Local Optimization for SDF

⚙️ Loal Optimization for SDF(Signed Distance Field)

✅ NVIDIA의 Local Optimization for Robust Signed Distance Field Collision 논문은 SDF를 이용한 충돌처리에서 삼각형 Cloth에 대해 Face와 Edge 사이의 접촉을 연속적인 방식으로 생성하는 방법을 다룬다.

➡️ 이는 이산화된 위치에서 접촉을 생성하던 이전 접근법과는 다르게, 실제 정점이 존재하지 않는 Face와 Edge 내부에 접촉을 생성하기 때문에, 면에 대한 충돌처리가 가능해진다.

🎯 이때, Projected Gradient Descent와 Frank-Wolfe 방법과 같은 로컬 최적화를 위한 수치 해석적 방법을 사용한다.

 

---

📏 Projected Gradient Descent

투영과 미분 값의 하강을 통해 로컬 최적화를 수행하는 방법이다.

이를 간편하게 설명하기 위해 2차원 공간에 다음과 같은 원과 선분이 있다고 가정한다:

위와 같은 상황에서 Projected Gradient Descent의 다음 식을 이용해 로컬 최적화를 진행한다.

이때, P는 Barycentric coordinate를 이용한 Face 내부로의 투영이다. 계산 과정은 다음과 같다.

1. 법선 벡터($\nabla \phi$) 계산

2. $-\nabla \phi$ 방향으로 하강

3. 선분에 투영

SDF의 Gradient는 물체로부터 멀어지는 충돌 법선 방향을 의미한다. 따라서, Gradient의 하강 및 투영을 계산하면 선분 위에서 SDF 물체와 가까워진다.

 

이를 반복하여 다음과 같이 물체와 가장 가까운 선분 위의 점으로 수렴하게 한다:

 

위 그림처럼 closest point를 찾은 경우, 해당 점에 대해 충돌처리를 진행한다.

---

📏 Frank-Wolfe Method

Projected Gradient Descent 방법과 유사하게 1차 미분 값이 요구되지만, 투영 과정이 생략된다.

 

마찬가지로 설명의 편의를 위해 다음과 같은 원과 선분을 가정한다:

 

 Frank-Wolfe 방법은 다음과 같은 식을 이용해 로컬 최적화를 진행한다.

이때, $\alpha$ 는 가중치로 $(0, 1)$ 값을 가진다. 

 

Frank-Wolfe 방법의 전체적인 진행 과정은 다음과 같다:

1. $\nabla \phi_{p0}$ 계산

2. 끝점의 A와 B를 $\nabla \phi_{p0}= N$에 투영

3. 값이 더 작은 정점을 $s_i$로 두고, 위의 식을 계산

4. 반복

이를 통해 다음과 같이 선분(mesh) 위의 closest point로 수렴하게 된다:

 

---

📏 Golden-Section Search

황금 비율을 이용한 구간 탐색 방법으로, 2차원 직선에서 사용되는 로컬 최적화 기법이다.

이는 Gradient가 요구되지 않으며, 과정은 다음과 같다:

1. 양 끝점의 61.8%(황금비)에 해당하는 지점에 $x_a, x_b$ 설정

2. $\phi(x_a), \phi(x_b)$ 값을 계산하여 더 큰 값을 가진 지점을 경계로 설정

3. 위 과정을 SDF 값이 일정 크기보다 작아질 때까지 반복

---

💻 Implement

전체적인 알고리즘 진행은 다음과 같다:

모든 triangle에 대해 반복
	Bounding Sphere를 이용한 Culling
    Start Point 지정(중간 값)
    While(수렴)
    	로컬 최적화
    sdf를 이용한 접촉 생성

 

이때 Bounding Sphere의 관한 내용은 다음과 같다:

---

📈 Result

위 내용을 토대로 Projected Gradient Descent 방법과 Frank-Wolfe 방법을 이용해 구현하였고, 다음과 같은 결과를 확인할 수 있었다.

 

Projected Gradient Descent

Frank-Wolfe

 

충돌 처리는 앞서 다뤘던 Self Collision에서 사용한 제약 조건 투영을 사용하였으며, Face의 각 정점에 대해 Barycentric Coordinate를 이용해 가중치를 두어 투영을 진행하였다. 현재는 방정식으로 표현되는 SDF만을 다룰 수 있다보니, 모서리에서의 충돌 감지 및 처리를 확인할 수 없었다. 

---

참고 자료 : 

Local Optimization for Robust Signed Distance Field Collision (MILESMACKLIN, KENNYERLEBEN, MATTHIASMÜLLER, NUTTAPONGCHENTANEZ, STEFANJESCHKE, ZACHCORSE)

---

깃허브:

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

GitHub - qkrdmstn/pbd-sdf-collision