[논문리뷰] Local Optimization for Robust Signed Distance Field Collision
PACMCGIT 2020. [Paper]
Miles Macklin, Kenny Erleben, Matthias Müller, Nuttapong Chentanez, Stefan Jeschke, Zach Corse
NVIDIA | University of Copenhagen
14 May 2020
Introduction
SDF 기반의 point-based contact을 삼각형 메쉬와 같은 연속적인 표면을 처리하도록 확장하는 방법은 명확하지 않다. 기존 방법들은 표면에서 discrete point들을 오프라인으로 샘플링한 다음, 런타임에 각 점의 겹침 여부를 point-based contact으로 확인했다. 이 방식은 개념적으로는 간단하지만, 특히 날카로운 부분에서는 겹침을 감지하기에 불충분할 수 있다는 문제가 있다. 또한, 점 샘플링은 물체 간의 edge-edge contact을 포착하지 못한다. 샘플링 밀도를 높일 수는 있지만, contact 위치는 표면의 discrete point들에 고정되어 있어 contact이 한 지점에서 다른 지점으로 이동할 때 불연속적인 현상이 발생할 수 있다. 또한 샘플 수가 증가함에 따라 생성되는 contact 수도 증가한다. 이로 인해 contact solver의 계산 부담이 커진다.
본 논문에서는 삼각형 메쉬의 면과 모서리 사이의 contact을 연속적으로 생성하는 방법을 제안하였다. 제안하는 방법은 constrained convex optimization을 사용하는 메쉬 모서리 또는 면에 대한 로컬 최적화를 기반으로 한다. 고정된 discrete point와 달리, 이 방식은 메쉬 element 전체에 걸쳐 contact이 부드럽게 변화하도록 하여 point-face contact과 edge-edge contact을 명확하게 포착한다.
Face Contact
먼저, SDF $\phi$로 표현된 물체와 하나의 삼각형이 충돌하는 경우를 생각해보자. 접촉점을 생성하기 위해 closest point 방법을 사용하는데, 이는 면과 SDF isosurface에서 가장 가까운 점을 찾는 것을 요구한다. 꼭짓점이 $\textbf{p}, \textbf{q}, \textbf{r} \in \mathbb{R}^3$인 삼각형의 경우, 물체에 가장 가까운 삼각형 위의 점은 무게중심 좌표 $u, v, w$에 대한 다음 최소화 문제의 해로 주어진다.
\[\begin{aligned} \underset{u, v, w}{\textrm{argmin}} \quad & \phi (u \textbf{p} + v \textbf{q} + w \textbf{r}) \\ \textrm{s.t.} \quad & u, v, w \ge 0, \; u + v + w = 1 \end{aligned}\]이러한 제약 조건은 문제의 해가 삼각형 내부 또는 경계에 있음을 보장한다.
1. Projected Gradient Descent
SDF는 임의의 shape을 나타낼 수 있으므로 최소화 문제의 objective는 일반적으로 비선형적이고 비볼록 함수이다. 이러한 함수의 글로벌 최적화는 어렵고 정교한 방법이 필요할 수 있다. Local minimum을 찾는 데 효과적인 방법은 projected gradient descent (PGD)이다. PGD를 적용하려면 무게중심 좌표에 대한 SDF의 gradient $\textbf{d}$가 필요하다.
\[\begin{equation} \textbf{d} = \begin{bmatrix} \frac{\partial \phi}{\partial u} & \frac{\partial \phi}{\partial v} & \frac{\partial \phi}{\partial w} \end{bmatrix}^\top = \begin{bmatrix} \nabla \phi (\textbf{x}) \textbf{p} \\ \nabla \phi (\textbf{x}) \textbf{q} \\ \nabla \phi (\textbf{x}) \textbf{r} \end{bmatrix} \\ \textrm{where} \quad \textbf{x}(u, v, w) = u \textbf{p} + v \textbf{q} + w \textbf{r} \end{equation}\]SDF gradient \(\nabla \phi (\textbf{x})\)는 그때그때 계산하거나, 미리 계산하여 그리드에 저장할 수 있다. $\textbf{d}$를 계산한 후, 고정된 step size $\alpha$에 따라 후보 해 $\textbf{c}$를 반복적으로 업데이트하고, fixed-point iteration을 사용하여 constraint manifold에 projection한다.
\[\begin{equation} \textbf{c}_{i+1} \leftarrow \mathbb{P}(\textbf{c}_i - \alpha \textbf{d}) \quad \textrm{where} \quad \textbf{c} = [u, v, w]^\top \end{equation}\]($\mathbb{P}$는 projection 연산자)
기하학적으로 제약 조건들은 3D에서 원점을 중심으로 하는 꼭짓점 $[1,0,0]$, $[0,1,0]$, $[0,0,1]$을 갖는 삼각형을 나타낸다. 따라서 projection은 현재 iteration에서 이 삼각형 상의 가장 가까운 점을 찾는 것으로, 이를 위한 효율적인 코드가 존재한다. 또한 $w$를 $u$와 $v$로 표현하여 문제를 단순화하면 projection을 3D 대신 2D에서 수행할 수 있다.
2. Frank-Wolfe
Frank-Wolfe는 constrained convex optimization 문제를 해결하기 위한 반복 알고리즘이다. Frank-Wolfe는 PGD와 마찬가지로 1차 미분값을 필요로 하지만, constraint manifold에 대한 projection 단계가 필요하지 않다. Frank-Wolfe 알고리즘은 점 \(\textbf{s}_i \in \mathbb{R}^3\)에 대해 다음 최소화 문제를 반복적으로 해결함으로써 진행된다.
\[\begin{equation} \underset{\textbf{s}_i}{\textrm{argmin}} \; \textbf{s}_i^\top \nabla \phi (\textbf{x}_i) \quad \textrm{s.t.} \quad \textbf{s}_i \in \mathcal{D} \\ \textbf{x}_{i+1} \leftarrow \textbf{x}_i + \alpha (\textbf{s}_i - \textbf{x}_i) \end{equation}\]$\mathcal{D}$는 최적화 대상 영역으로, 본 논문에서는 삼각형 자체이다. 삼각형의 볼록성 때문에 해 \(\textbf{s}_i\)는 꼭짓점 $\textbf{p}$, $\textbf{q}$, $\textbf{r}$ 중 하나여야 한다. 이 극점 \(\textbf{s}_i\)가 식별되면 Frank-Wolfe 방법은 수렴을 보장하기 위해 step size $\alpha = \frac{2}{i+2}$로 \(\textbf{x}_i\)를 업데이트 한다.
3. Culling and Starting Iterate
삼각형을 처리에서 빠르게 제외하기 위해 삼각형의 중심 \(\textbf{x}_c\)에서의 SDF \(\phi (\textbf{x}_c)\)를 계산하고, 이 값이 $r$보다 작은지 확인한다. 이 방법은 rigid body contact의 경우 매우 효과적인 조기 제외 방법이지만, 물체와 밀접하게 접촉하는 천 같은 경우에는 효과가 떨어진다.
반복 방법들의 수렴에는 초기 반복점 선택이 중요하다. 효과적이고 간단한 휴리스틱은 각 삼각형 꼭짓점에서 SDF를 평가하고 가장 작은 값을 갖는 꼭짓점을 선택하는 것이다. 이는 local minima를 피하는 데에도 도움이 되지만, 글로벌 해를 보장하는 데는 충분하지 않다.
4. Termination Conditions
각 element에 대한 거리의 하한값을 사전에 알 수 없으므로 $\phi (\textbf{x})$에 대한 절대 허용 오차를 정의할 수 없다. 그러나 PGD의 경우, gradient $\textbf{d}$의 크기를 기준으로 종료 기준을 정의할 수 있다. Frank-Wolfe의 경우, \(\textbf{s}_i^\top \nabla \phi (\textbf{x}_i)\)가 오차의 상한값이므로 이를 사용할 수 있다. 종료 후, 최소 거리가 특정 threshold $\delta$ 내에 있으면 contact으로 간주한다. 그렇지 않으면 element가 충돌하지 않는 것으로 간주한다.
Edge Contact
면 기반 최적화는 자연스럽게 edge에 있는 contact point를 찾는다. 그러나 머리카락이나 밧줄과 같은 1차원 물체를 시뮬레이션할 때는 edge를 직접 최적화해야 한다. 두 점 $\textbf{p}, \textbf{q} \in \mathbb{R}^3$ 사이에 정의된 edge를 고려할 때, SDF isosurface에 가장 가까운 점을 단일 변수 최적화 문제의 해로 정의할 수 있다.
PGD와 Frank-Wolfe를 이 문제에 직접 적용할 수 있지만, 차원이 낮기 때문에 탐색 기반 방법이 더 효과적이다. 구간 제약 조건이 있는 최적화 문제를 해결하는 간단하고 robust한 방법은 golden-section search이다. Golden-section search는 최소값 중 하나 또는 구간의 경계에서 종료된다. Golden-section search는 gradient를 필요로 하지 않아 특히 효율적이다.
Models
1. Cloth Collision
삼각형 메쉬로 표현된 천과 SDF로 표현된 shape 간의 충돌을 처리하기 위해, 각 삼각형에 대한 로컬 면 최적화를 수행한다. 이 방식은 삼각형당 하나의 contact point를 생성한다. 연결된 면들 사이에 중복된 contact point가 생성되는 것을 방지하기 위해, greedy한 전처리로서 메쉬의 feature (vertex, edge, face)를 각 element에 고유하게 할당한다. 최적화 후, contact point가 해당 element에 할당되지 않은 feature에 위치하는 경우 해당 contact은 제거될 수 있다.
2. Rigid Body Collision
테셀레이션이 잘된 rigid body 간의 충돌의 경우, 면에 대한 최적화만으로도 양호한 contact manifold를 생성하기에 충분하다. 그러나 테셀레이션이 잘 되지 않는 경우, 특히 곡률이 높은 edge-edge contact에서 descent 기반 방법이 수렴 속도가 느리다. 이러한 문제를 피하기 위해 두 메쉬의 vertex를 직접 테스트한 다음, 각 edge에 대해 golden-section search를 수행할 수 있다.
3. Soft Body Collision
SDF는 deformable cage 내부에 SDF를 포함시켜 deformable shape과의 충돌을 처리하는 데 사용할 수 있다. World space 좌표계의 한 점 \(\textbf{x}_s\)가 주어졌을 때, material space의 점 \(\textbf{x}_m = \textbf{g}(\textbf{x}_s)\)를 연결한다. 이러한 매핑을 통해 변형된 SDF를 정의할 수 있다.
변형된 SDF는 더 이상 \(\| \nabla \phi_d \| = 1\)을 만족하지 않을 수 있지만, 이 변환으로 인해 isosurface는 변경되지 않으므로 local minimum을 찾고 제약 조건을 정의하는 것으로 충분하다.
변형된 사면체 메쉬가 주어지면 먼저 world space 점을 둘러싸는 사면체를 찾은 다음, 해당 점에 대한 material space 점을 계산한다. 꼭짓점이 \(\textbf{v}_0\), \(\textbf{v}_1\), \(\textbf{v}_2\), \(\textbf{v}_3\)인 사면체는 BVH 또는 다른 데이터 구조를 사용하여 효율적으로 찾을 수 있다. Material space로의 projection은 다음과 같다.
\[\begin{equation} \textbf{x}_m = \textbf{g} (\textbf{x}_s) = \textbf{MD}^{-1} (\textbf{x}_s - \textbf{v}_{0s}) + \textbf{v}_{0m} \end{equation}\]$\textbf{D} \in \mathbb{R}^{3 \times 3}$은 world space에서 변형된 사면체를 둘러싸는 basis이고, $\textbf{M} \in \mathbb{R}^{3 \times 3}$은 material space에서 변형되지 않은 사면체의 basis이다.
\[\begin{aligned} \textbf{M} &= \begin{bmatrix} \textbf{v}_{1m} - \textbf{v}_{0m} & \textbf{v}_{2m} - \textbf{v}_{0m} & \textbf{v}_{3m} - \textbf{v}_{0m} \end{bmatrix} \\ \textbf{D} &= \begin{bmatrix} \textbf{v}_{1s} - \textbf{v}_{0s} & \textbf{v}_{2s} - \textbf{v}_{0s} & \textbf{v}_{3s} - \textbf{v}_{0s} \end{bmatrix} \end{aligned}\]매핑 함수 $g$와 다음과 같이 정의된 삼각형 위의 world space 점 \(\textbf{x}_s\)가 주어졌을 때, 무게중심 좌표에 대한 \(\phi_d (\textbf{x}_s)\)의 gradient는 다음과 같다.
\[\begin{equation} \textbf{d} = \begin{bmatrix} \frac{\partial \phi_d}{\partial u} & \frac{\partial \phi_d}{\partial v} & \frac{\partial \phi_d}{\partial w} \end{bmatrix}^\top = \begin{bmatrix} \nabla \phi_m (\textbf{x}_m) \textbf{G} (\textbf{x}_s) \textbf{p} \\ \nabla \phi_m (\textbf{x}_m) \textbf{G} (\textbf{x}_s) \textbf{q} \\ \nabla \phi_m (\textbf{x}_m) \textbf{G} (\textbf{x}_s) \textbf{r} \end{bmatrix} \\ \textrm{where} \quad \textbf{x}_s (u, v, w) = u \textbf{p} + v \textbf{q} + w \textbf{r}, \quad \textbf{G} = \nabla \textbf{g} = \textbf{MD}^{-1} \end{equation}\]$\textbf{D}$는 변형된 사면체의 basis이므로, element의 조건이 극도로 불량한 경우 역행렬 계산이 불가능할 수 있다. 이러한 경우를 감지하고 해당 element를 무시하도록 선택할 수 있다.
$\textbf{G}$는 월드 공간 점 \(\textbf{x}_s\)의 함수이며, 일반적으로 BVH를 순회하여 둘러싸는 사면체를 결정하는 과정을 포함한다. 최적화 단계마다 이 작업을 반복하지 않기 위해, 삼각형의 중심에서 $\textbf{G}$를 계산하고 최적화 과정 전체에 걸쳐 상수로 간주한다. 이후, \(\phi_d\)의 최소값을 찾으면 최소점을 material space에 다시 projection하고, 변형 매핑을 world space에 적용하여 contact point를 정의한다.
Discrete Distance Fields
SDF는 종종 regular grid나 sparse grid에 discrete한 샘플로 저장되며, 이를 통해 복잡한 비선형 함수를 표현할 수 있다. 그러나 유한 범위 discretization을 사용하는 경우 contact 생성 과정에서 특별한 처리가 필요하다. 최적화는 유효한 SDF 데이터가 있는 경우에만 진행될 수 있으므로, shape의 표면과 SDF 볼륨 데이터의 범위 사이에 충분한 마진이 없을 때 문제가 발생한다.
이에 대한 가능한 해결책은 SDF 볼륨의 bounding box 외부에 있는 샘플을 bounding box 표면의 가장 가까운 점으로 projection하는 것이다. 그러나 저자들은 shape의 isosurface 주변에 보수적인 샘플링 마진을 사용하는 것으로 충분함을 확인했다.
Analytic Discrete Fields
종종 단순한 shape에 대한 closed-form SDF를 찾을 수 있으며, 이러한 함수들을 효율적으로 조합하여 복잡한 shape을 모델링할 수 있다. 본 방법은 SDF 표현 방식에 구애받지 않으므로 analytic field 정의를 자연스럽게 지원한다. 이를 통해 메쉬를 임의로 매끄러운 표면과 충돌시킬 수 있다. 또한, analytic field로 정의된 shape을 시간에 따라 변하게 하여 충돌시킬 수 있다.
Results
1. Convergence
다음은 PGD, Frank-Wolfe, golden-section search의 수렴 속도를 비교한 그래프이다.
2. Performance
다음은 계산에 걸리는 시간을 비교한 결과이다.
다음은 sphere culling 효율성을 나타낸 그래프이다.
3. Comparison To Surface Approaches
다음은 (a) 서로 겹치는 초기 상태가 주어졌을 때, (b) 삼각형 기반 충돌과 (c) SDF 기반 충돌 시뮬레이션 결과이다.
