[Position Based Dynamics] 3.2. The Solver

Solver의 목적은 외력만 고려하여 움직인 position들에 추가로 constraint들을 만족하도록 하여 추가로 내력을 받은 것처럼 imitation하는 것이다.

 

Solver에는 M개의 constraint와 M_coll개의 collision constraint가 입력으로 들어오고, 외력을 받아 움직인 position들이 p1,...,pN이 입력으로 들어온다. Solver는 모든 constraint를 충족하도록 외력만 고려한 position들을 수정하려고 한다. 결과적인 이 constraint들의 방정식 시스템은 비선형적이다.

 

부등식(inequality)에 대한 constraint는 부등식을 만드는데, 이러한 부등식와 일반적인 방정식들을 해결하기 위해 Gauss-Seidel-type iteration의 아이디어를 살짝 빌려왔다. original Gauss-Seidel algorithm(GS)는 선형 시스템만 처리할 수 있다. GS에서 각 constraint를 독립적으로 차례대로 처리하는 아이디어(앞선 constraint에 대해 구한 해를 이용해 현재 constraint에 대해 독립적으로 풀고, 그 다음 값을 갱신하는 것)를 가져왔지만, GS와 달리 비선형 작업을 처리한다.

 

이 논문은 모든 constraint를 여러차례 반복하고, 주어진 constraint만으로 particle들을 유효한 위치로 projection한다. Jacobi-type iteration과 다르게, point 위치에 대한 수정은 즉시 process에 표시된다. 압력파가 단일 solver step에서는 물질을 통해 전파될 수 있기 때문에 수렴 속도가 크게 빨라지는데, 이는 constraint가 해결되는 순서에 따라 달라지는 효과이다. 과도하게 제약된 상태에서는 순서가 일정하게 유지되지 않으면 process가 진동으로 이어질 수 있다.