[ Cloth Simulation & Collision ] 04. 천 자가 충돌 (Cloth Self-Collision)

👕 Cloth Self-Collision

하나의 천에서 서로 겹치거나, 부딪힐 때 면을 통과하지 않도록 하는 충돌 처리 방법이다.

❗ Self Collision이 적용되지 않은 천에서는 서로 부딪혔을 때 통과하는 등의 현상이 발생할 수 있다.

➡️ 따라서, 사실적인 천을 시뮬레이션 하기 위해서는 이러한 SelfCollision이 필요하다.

 

이러한 Self Collision은 다음과 같이 다섯 가지 방법을 통해 구현된다.

1. hash를 이용한 각 정점 접근

2. 떨림 현상을 피하기 위한 rest distance 사용

3. Iterator Solver와 CCD가 아닌 Sub-Stepping 사용

4. 최대 속도 제한

5. 안정적인 천-천 마찰 사용

---

🔴 Particle Hash

무작위로 배치된 정점들 사이에서, 일정 거리 내에 있는 정점(이웃한 정점)을 찾기 위해 Hashing을 사용한다.

➡️ 만약, 아래와 같이 이중 반복문을 이용해 모든 정점을 순회한다면 시간 복잡도가 $O(n^2)$ 이 된다. 이는 비효율적이다.

 

아래와 같이 그리드를 이용해 각 정점을 cell에 포함시키고, 인접한 cell에 포함된 정점만을 조사한다면 일정 거리 내에 있는 정점들을 찾을 수 있다.

➡️ 2차원 공간이라면 9칸, 3차원 공간이라면 27칸을 순회한다.

 

그리드 배열 형태로 각 파티클들을 저장하는 방법은 다음과 같다:

그리드 한 칸의 길이를 spacing이라 하면, 각 정점 위치를 이용하여 배열의 index를 계산할 수 있다. 이를 이용해 각 배열 index에 해당 정점의 index를 대입한다.

---

🔎 Dense Grid Representation

더 밀도 있는 배열을 만들기 위해 다음과 같이 각 cell에 포함된 정점의 수를 누적하여 배열을 만들고 정점이 모여 있는 파티클 배열을 추가한다.

➡️ 이때, 그리드 배열의 원소는 해당 cell의 첫 번째 입자가 파티클 배열의 어느 위치에 있는지를 나타낸다.

---

🔎 Handle Unbounded Grid With Hashing

✅ 시뮬레이션에 경계 그리드가 포함되지 않은 경우에는 Spatial Hashing 기법을 사용한다. 이는 정점의 위치 값을 정보로 hash 함수를 통해 index를 얻은 뒤, 이를 배열에 할당하는 방식이다.

 

➡️ 이때, 아래의 보라색과 파란색 cell처럼 다른 위치(cell)가 같은 index 값을 반환하는 Hash Collision이 발생할 수 있다. 하지만, Cloth Simulation에서는 cell에 포함된 입자들의 최소 거리 값을 계산하는 과정을 거치기 때문에 Hash Collision을 무시해도 무관하다.

 

❗ 그럼에도 거리 계산을 최소화하기 위해 hash function은 최대한 cell을 균등하게 분포시키도록 값을 반환해야 한다.

 

최종적인 Hash Table을 구성하는 과정은 다음과 같다.

---

📏 Rest Distance

아래의 그림과 같이 충돌 처리를 위한 거리(2r)와 거리 제약 조건의 거리가 중첩되면 떨림 현상이 발생한다.

➡️ 이를 방지하기 위해 충돌 거리를 설정한 충돌 거리와 거리 제약 조건의 잔여 거리 중 더 작은 것으로 선택한다.

---

🚶 Sub-Step

정점 간의 충돌을 놓치지 않기 위해 CCD(Continuous Collision Detection)나 Iterator Solver에 의한 반복 연산이 아닌, Sub-Step 방식을 사용한다.

 

알고리즘은 다음과 같다:

➡️ 이는 다음에 설명할 최대 속도를 제한하는 것과 관련이 있으며, 앞서 설명한 hash를 Sub-Step 과정 전에 한 번만 생성한다.

 

추가적으로, Iterator Solver에 의한 투영과 Sub-step 방식의 차이를 간단하게 살펴보면 다음과 같다:

---

⛔ Enforce Maximal Velocity

정점의 속도가 너무 빠를 경우, Sub-Step 과정에서 충돌을 놓칠 가능성이 있다.

➡️ 따라서, 다음 식을 통해 한 번의 서브 스텝 도중 최대 정점의 반지름 r만큼 즉, spatial hashing의 grid size 만큼만 이동할 수 있도록 속도를 제한한다:

---

👌 Stable Cloth-Cloth Friction

더욱 안정적인 천과 천 사이의 마찰을 계산하기 위해 다음과 같이 평균 속도를 사용하여 마찰력을 계산한다.

---

💻 Implement

Class Hash :

앞에서 설명한 Particle Hash를 구현한 Class로, 자세한 수치와 같은 코드는 생략했다.

class Hash
{
public:
	double spacing;
	int tableSize;
	int querySize;
	int numParticles;

	vector<int> cellStart; //cell Index 스타트 배열
	vector<int> cellEntries; //파티클 배열
	vector<int> queryIds; //인접 정점 배열
	vector<int> firstAdjId; //queryAll 함수의 스타트 배열 (Dense Grid Representation)
	vector<int> adjIds; //queryAll 함수의 인접 정점 배열
    
public:
	Hash();
	Hash(double _spacing, int _numParticles, int _numOfTri);
	~Hash();

public:
	int intCoord(double coord); //좌표 값을 int 값(내림)으로 반환
	int hashCoords(int xi, int yi, int zi); //hash function
	int hashPos(vec3 pos); //정점의 위치를 입력 받아 hash index로 변환
	void create(vector<vec3> _pos); // table 생성
	void query(vector<vec3> _pos, int index, double maxDist); //하나의 정점에 대해 주변 9칸 순회
	void queryAll(vector<vec3> _pos, double maxDist); //모든 정점에 대해 주변 9칸 순회
};

 

updatePPSelfCollision() :

void PBD_PlaneCloth::updatePPSelfCollision(double dt)
{
	double thickness2 = thickness * thickness;

	for (int i = 0; i < _res[0]; i++) { //width
		for (int j = 0; j < _res[1]; j++) { //height 모든 정점에 대하여 실행
			int index = j * _res[0] + i;

			int id0 = index;
			int first = _hash->firstAdjId[index];
			int last = _hash->firstAdjId[index + 1];
			
			for (int j = first; j < last; j++)
			{
				int id1 = _hash->adjIds[j];

				vec3 diffPos = (_pos1[id1] - _pos1[id0]);
				double dist2 = diffPos.lengthSquared();
				
				if (dist2 > thickness2 || dist2 == 0) //거리가 두께보다 멀면 처리 X
					continue;

				//rest distance
				double restDist2 = (_restPos[id1] - _restPos[id0]).lengthSquared();
				double minDist = thickness; //restDistance 와 thickness 중 작은 값을 minDist로 설정
				if (dist2 > restDist2)
					continue;
				if (restDist2 < thickness2)
					minDist = sqrt(restDist2);

				//position correction
				double dist = sqrt(dist2);
				diffPos = diffPos * ((minDist - dist) / dist);

				_pos1[id0] += diffPos * -0.5 ;
				_pos1[id1] += diffPos * 0.5 ;

				//friction
				vec3 v0 = (_pos1[id0] - _pos[id0]);
				vec3 v1 = (_pos1[id1] - _pos[id1]);

				vec3 Vavg = (v0 + v1) * 0.5;

				double damping = 0.3;
				_pos1[id0] = _pos1[id0] + (Vavg - v0) * damping ;
				_pos1[id1] = _pos1[id1] + (Vavg - v1) * damping;
			}
		}
	}	
}

앞서 설명한 과정을 그대로 모든 정점에 대해 실행하였다.

 

---

📈 Result

결과는 아래와 같이 Self-Collision을 적용한 것과 하지 않은 것을 비교해 보았다.

Self-Collision X

Self-Collision O

천이 겹치지 않고 잘 충돌하는 것을 확인할 수 있다.

---

참고 자료 : 

https://matthias-research.github.io/pages/tenMinutePhysics/index.html, (09 - Getting ready to simulate the world with XPBD, 11 - Finding overlaps among thousands of objects blazing fast, 15 - Self-collisions, solving the hardest problem in animation)

---

깃허브:

https://github.com/qkrdmstn/pbd-cloth-simulation.git

GitHub - qkrdmstn/pbd-cloth-simulation