[💬] 2d 물리엔진 구현을 위한 글

[푸롤로로롤(june0812)]

물리 엔진 만드는 방법 혼자서 찾아보며 했는데, 다른 사람한테도 말해주고 싶어서 글 씀

근데 게임 엔진 사용하면 알 필요 없는 내용인가? 게임 엔진 써 보질 않아서 모르겠는데 자체적으로 물리엔진 있겠지?

그래도 일단 써 봄. 간단한 2d 물리엔진 구현에 대해 글을 써 보겠음.

먼저 내가 참고한 링크들

How to create custom physics engine : 링크

-> 설명이 잘 되어 있긴 한데 드문드문 틀린 곳이 있고, warmstarting 설명이 없고 accumulated impulse 설명도 없음

Box 2d : 링크

-> box 2d 물리엔진 라이브러리의 ppt 모음 링크임. 직접 소스 코드 볼 수 있어서 좋고 ppt 설명도 잘 되어 있음

Allen Chou game physics series : 링크

-> 여기도 설명 자세하게 나와 있는 거 같긴 한데 거의 완성 단계에서 발견한 거라서 자세하게 보진 않았음.

사실 이 글 볼 필요 없이 위 링크만 봐도 됨

========================================================

일단 먼저 간단하게 물리 법칙 부터 시작하면

아마 다들 알고 있겠지만 그래도 써 봄. 순서가 중요함

힘으로 가속도 구하고, 그 가속도로 속도 구하고, 그 속도로 위치 구해야 됨,

이걸 semi-implicit euler method 라고 하는 거 같음.

이거보다 정확한 RK4 라는 방식도 있지만, 복잡하고 semi-implicit euler method 로도 충분히 정확해서 안 쓰는 것 같음.

물체의 회전도 물체의 이동이랑 똑같이 생각하면 됨,

물체의 위치 x자리에 물체가 회전한 각도 θ를 넣고, 물체의 속도 v대신 물체의 각속도 ω넣고, 물체의 가속도 a 대신 각가속도 α넣고, 물체의 질량 m 대신에 물체의 회전관성 I 넣으면 됨.

즉, v=v0+a*t 대신 ω=ω0+α*t 하고

x=x0+v*t 대신 θ=θ0+ω*t 하면 됨.

문제는 F대신 뭘 넣냐는 건데, 마찬가지로 알고 있겠지만 토크 t 값을 넣으면 됨. t는 물체를 회전시키는 힘인데.

위 사진에서

회전 중심을 빨간 점이라 하고, r만큼 떨어진 곳에서 F로 힘을 주면, 위와 같이 되는데

토크 t 값의 크기는 r 에 F⊥ 값을 곱하면 됨. 사실 당연하다고 볼 수 있는게, F|| 방향으로 아무리 잡아 당겨도 빨간 점을 기준으로 회전 할 수가 없음

기호로 표기하면 t=r×F 가 됨.

다들 알고 있겠지만 벡터를 외적하면

위와 같은 방향이 됨.

따라서 초록색 r벡터와 보라색 F벡터를 외적해서 나온 ????는 화면에서 튀어나오는 방향이 된다.

참고로 a=<a1,a2,a3> 이고 b=<b1,b2,b3> 일 때,

a×b=<a2*b3-b2*a3,-a1*b3+a3*b1,a1*b2-a2*b1> 이 되는 공식이 있다.

벡터의 내적도 알고 있어야 하는데, 다들 알다시피

위의 사진에서 r과 F를 내적한다는 것은 r·F 로 표현하고

그 값의 크기는 r * F|| 이다.

a=<a1,a2,a3> 이고 b=<b1,b2,b3> 일 때,

a·b=<a1*b1,a2*b2,a3*b3> 이 되는 공식이 있다. 그리고 두 벡터 a와 b가 같은 방향이면 내적값은 양수이고 다른 방향이면 내적값이 음수가 된다.

========================================================

먼저 물체부터 정의하자. 물체를 어떻게 정의하냐는 코딩 하는 사람 마음이겠지만 나의 경우에는

object 구조체에 질량 중심에 대한 속도, 가속도, 힘, 각가속도, 각속도, 각도, 질량 등을 넣었음. 계산 할 때 질량의 역수가 많이 이용되니까 보통 질량의 역수로 저장함.

shape와 material 구조체는 위와 같이 했음

shape 구조체에 질량 중심에 대한 각 꼭지점의 좌표, 물체의 변에 대해 수직인 벡터(법선벡터) 등을 넣었음

질량 중심에 대한 꼭지점의 좌표(빨간색)과 물체의 변에 대해 수직인 벡터(보라색)

보라색 벡터는 편의상 크기를 1로 하는게 좋음

========================================================

물체의 형태에 관해 저장을 했으니 이제 물체의 충돌을 검출해야 함. 이 글에서는 GDC 2013 ppt에 있던 SAT 방식을 설명하려고 함. Box2d ppt 사이트에 있음

이 부분이 계산 시간이 좀 걸리니 보통은 광역 검사를 한 번 하고 그 다음에 제대로 충돌 검사를 함.

광역 검사를 시각적으로 표현해 보면

위의 오각형과 육각형의 충돌을 제대로 검사하기 이전에, 계산하기 쉬운 영역(하늘색 테두리)를 미리 잡은 후에 그 영역으로 충돌 검사를 하는 거임

위에 보면 하늘색 사각형이 겹치지 않으니 굳이 검은색 도형이 충돌 하는 지 안 하는지 확인할 필요가 없음.

Box2d 의 경우에는 위처럼 사각형으로 영역을 잡았고, 난 걍 귀찮아서 도형의 최대 길이를 max_distance에 저장한 후에 두 도형 사이의 거리와 max_distance의 합을 비교했음.

만일 광역 검사에서 걸리면 이제 충돌 검사를 해야 되는데,

뭔가 이것 저것 많아서 복잡해 보이지만 잘 보도록 하자.

직사각형과 평행사변형이 보이는 것 처럼 충돌하고 있음

이 때, 평행사변형의 3번 꼭지점이 직사각형 내부로 들어와 있음. 이걸 어떻게 알 수 있는지 보도록 하자.

나는 핑크색 벡터와 갈색 벡터를 object 구조체에 저장했었음. 그리고 주황색과 빨간색과 보라색 벡터는 shape 구조체에 저장 했었음.

그러면 초록색 벡터 = (갈색 + 빨간색) - (핑크색 + 주황색) 인 것을 쉽게 알 수 있음

그리고 초록색 벡터와 보라색 벡터를 내적 했을 때, 그 값이 음수가 나오면 그 꼭지점은 변의 내부에 있다는 것을 알 수 있다.

이 것과 동일하게 직사각형의 2번 3번 4번 꼭지점도 똑같이 계산해서 전부 음수가 나오면 충돌했다는 것을 알 수 있음.

계산하다가 하나라도 양수 나오면 break나 return 해서 걍 빨리 빠져나오셈

그리고 초록색 벡터와 보라색 벡터를 내적하면 (보라색 벡터의 크기라 1이라는 가정하에)

위의 사진에서 빨간색 선분의 길이가 나올 거임.(정확히 말하자면 내적 값이 음수이므로 선분 길이의 음수값)

그리고 2번 꼭지점에서는 주황색이 나오고

3번 꼭지점에서는 초록색, 4번 꼭지점에서는 하늘색 선분이 나올거임.

만약 두 도형이 충돌했을 경우, 이 4개 선분 중에서 길이가 가장 짧은 놈이 빨간색이니까, 이 빨간 선분의 길이를 저장하고 1번 꼭지점에서 그 선분이 발생했다는 거도 저장해놔야됨

이렇게 가장 짧은 선분의 길이를 minimum penetration depth 라고 함.

========================================================

그 다음으로 필요한 게 충격량과 운동량이라는 개념인데,

두 물체가 충돌 할 때, 힘의 방향은 충돌면에 수직 방향임.

직사각형과 평행사변형의 예시를 들자면.

먼저 penetration depth 가 가장 짧았던 하늘색 변이 충돌면이 되는 거임.

그리고 빨간색 화살표가 평행사변형이 받는 힘의 방향이고, 녹색이 직사각형이 받는 힘의 방향이 됨.

빨간색/녹색 화살표의 방향은 우리가 이미 직사각형의 변에 수직한 벡터를 shape 에 저장해 놓았으니 쉽게 얻을 수 있음.

운동량, 충격량, 반발계수에 대한 대략적 설명은 위와 같음.

그렇다면 우리는, 두 물체의 충돌 전 속도를 알고 있고, 반발계수도 알고 있을 때, 충돌 후 두 물체가 주고 받는 충격량의 크기만 알면 됨,

기존의 운동량 + 충격량을 하면 충돌 후 물체의 속도를 알 수 있으니까 그거만 하면 물리엔진 대략적 구현은 끝났다고 봐도 되지.

그 충격량 값은 위와 같음.

마음 같아서는 나도 증명 쓰고 싶은데, 이거 계산 복잡해 뒤짐

한 번 해 봤는데 벡터방정식 풀어야 되더라, 이거 어떻게 벡터 형태로 그대로 풀 수 있을까 고민 하다가 성분 별로 그냥 방정식 세워서 풀었음. 일단 답이 나오긴 나옴

그냥 원본 링크 걸어드림 (링크)

일단 이 값이 나오긴 나온다는 걸 알았으면 좋겠음 

========================================================

이제 accumulated impulse 에 대해서 설명을 할 거임.

위와 같이 바닥에 10kg 물체가 3개 쌓여있다고 하자.

중력의 크기는 F=m*g 임 (편의상 g값을 10이라고 하자)

따라서 10kg 물체에 작용하는 중력의 크기는 각 각 100 N일 거임

물체가 정지한 채 있다면 위와 같이 힘이 작용할 거임.

근데 우리는 두 물체 사이의 충격량만 구할 수 있음.

물체 a, b, c가 있는데, a하고 b 사이의 충격량을 구해놓고 b하고 c의 충격량을 다시 구해놓으면 기존에 해놨던 a하고 b사이의 상대속도가 달라져서 또 다시 a하고 b사이의 충격량을 구해야 됨.

이 과정을 무수히 많이 반복하면 결국 안정적인 global solution 으로 수렴하게 됨.

이 반복 횟수는 많을 수록 정확해지지만 당연히 횟수가 많아지면 계산 시간이 늘어남.

보통은 10번~15번으로 하는 거 같은데.

말로 하긴 힘드니 그림으로 표현하면 아래와 같음

위와 같이 충돌을 여러번 반복 해서 global solution으로 도달하게 하는 방법임.

이 식에서 

두 물체 a, b가 가까워질 경우에는 그냥 값들을 대입해서 충격량 j를 구하면 끝임. 그리고 그 충격량으로 서로에게 멀어지도록 운동량을 변화시키면 됨.

그런데 만약 두 물체가 멀어지는 경우는 어떻게 해야 될까.

두 물체가 멀어지므로 그냥 생각해서는 굳이 충격량 j를 구하지 않아도 될 것 같지만.

어쩌다가 물체에 큰 충격량이 작용하면 그걸 수정할 수가 없게됨.

위와 같이 바닥에 물체가 올려져 있으면, 충돌 점이 두 개가 생기게 됨.

그런데 어쩌다 빨간색이 크게 작용하면 이걸 다시 줄일 방법이 없게 되고, 빨간색이 커지면 파란색도 덩달아 커지고, 그럼 다시 빨간색이 다시 커지게 되며 덜덜 떨리게 됨

이런 현상을 jittering 이라고 부르더라

우리의 해결책은 두 물체가 멀어지더라도 그냥 공식에 때려 박아서 충격량 j를 구하는 거임. 물론 충격량의 방향은 가까워질때의 충격량이랑 반대방향이 될 거임.

그런데 반복해서 충격량을 구할 때, 만약 충격량의 총 합이 가까워지는 방향이면 그냥 0으로 취급할 거임. 충격량을 누적시켜서 더한다는 의미에서 accumulated impulse임.

쉽게 예를 들어보자.

두 물체 a와 b가 충돌했다고 치자.

반복의 첫 번째에서 a가 받은 충격량이 +5라고 하자. 이때 +는 서로 멀어지는 방향으로 받은 충격량을 의미한다고 하자. a의 질량이 2이면, a의 속도는 +2.5 만큼 바뀔거임.

두 번째 반복에서 a가 받은 충격량이 -2라 하자. 즉 서로 가까워지는 방향으로 충격량을 받은거임. 그러면 a의 속도는 다시 -1.0 만큼 바뀔거임

첫 번째 반복에서 변한량이랑 더하면, 총 속도는 +1.5만큼 변한거임. +1.5값은 (+5-2)/2.0=1.5 로도 구할 수 있음.

이 시점에서 accumulated impulse 값은 +5-2=+3임.

세 번째 반복에서 a가 -10의 충격량을 받았다고 하자. 그러면 accumulated impulse가 -7이 되는데, 이렇게 음수가 되면 accumulated impulse을 0으로 바꿔버린 후에, a의 속도의 변화량도 0으로 해버리는 거임. 즉 a의 총 속도 변화량은 (+5-2-7)/2.0=-2.0 이 아니라 그냥 0인거임. 그리고 accumulated impulse 값도 그냥 0이 됨.

왜 이렇게 하냐면 어쨌든 두 물체가 충돌할 때 서로 가까워질 수는 없기 때문임.

========================================================

이제 position correction 을 해보자.

지금까지 한 거로만 물리엔진을 만들면 두 도형이 박혀버린다거나, 바닥으로 점점 가라앉는다거나 할 거임.

바닥으로 가라앉는건 부동소수점 오류때문에 생긴다는데 어쨌든 이걸 보정해야됨.

보정 방법 자체는 간단함.

충돌 검사에서 minimum penetration depth를 구하면 그 방향으로 양 물체를 이동시키면 됨.

충돌 검사를 해서 penetration depth값을 저장해 놨으면, 서로의 질량에 따라서 그 값을 나눠가지면 됨.

penetration depth값이 10이고 물체 a가 질량이 1, 물체 b가 질량이 4이면

물체 a는 4*10/(1+4)=8만큼 뒤로 물러나고, 물체 b는 1*10/(1+4)=2 만큼 뒤로 물러나면 됨

그런데 약간의 여백을 두는게 좋음. 말 들어보면 0.1에서 0.01정도는 여유 두는거 같더라.

여백을 안 두면 물체가 충돌 했다 안 했다 할 수 있어서 불안정해짐.

========================================================

이제 마지막으로 warmstarting 에 대해 설명할 거임.

왈도체로 따듯한 시작 정도 되는데 말 그대로 물리엔진 계산을 하기 전에 미리 충격량을 어림해서 예열하는 거임.

두 물체 a와 b가 충돌해서 15번의 반복 끝에 a가 받은 accumulated impulse 값이 +7이라면

그 다음 반복이 시작될 때 미리 +7 의 impulse를 가하고 시작하는 거임. 값이 너무 튀는 거 같다 싶으면 +7그대로 넣지 말고 일부만 넣던가

이렇게 되면 시간이 지날수록 더 정확해 지게 된다는 걸 알 수 있지.

========================================================

이렇게 나도 물리엔진 만들어 봤는데 뭐 재밌었음

근데 문제점이 도형들이 예각일 때는 제대로 충돌검사가 작동을 못 하더라

위 사진처럼 서로 도형이 통과되면서 아주 개판이 됨.

이거 dirk gregorius 한테 이거 뭐 어캐 했냐 하니까 자기도 모르겠다고 함.

이거 때문에 문제 생기면 SAT 말고 걍 gjk 알고리즘 쓰자...

[地鬼(dczlatan)]

충돌 검출할 때, 3번 꼭지점에 대해서 내적 계산하면 양수 나오는거 아님? 3번 벡터 (a, b), 보라색 노멀 벡터 (0, n) 일 때, 내적 = a*0 + b*n = b*n 인데, a, b, n 전부 양수니까 내적도 양수 아님? 생긴것도 3번 꼭지점에 대한 벡터랑 보라색 노멀벡터의 내적은 그 사이 각이 90도가 안되게 생겨서 내적은 0보다 크게 나오겠던데. 꼭지점마다 쓰는 노멀벡터가 다른건가?

[푸롤로로롤(june0812)]

3번 꼭지점에 대한 노말 벡터는 (0,-1) 임. 설명을 너무 대충했나.... 1번 꼭지점의 노말 벡터는 (0,1) 이고 2번 꼭지점에 대한 노말 벡터는 (-1,0)이고 4번은 (1,0) 임. 각 꼭지점의 왼편에 존재하는 변에 수직임 벡터임

[地鬼(dczlatan)]

아 ㅇㅋ. 와 진짜 대단하네 ㅋㅋㅋ 내적으로 점 내부에 들어와있는걸 계산하는건 생각도 못해봄. 신기하다 ..

[地鬼(dczlatan)]

재밌게 잘봤음!

[地鬼(dczlatan)]

그리고 또 하나 질문 있음. 도형 구조체에서 1번점과 2번점의 연결성에 대한 정보는 어디에 담겨져있는 것임? vertex 배열에 있는건감?

[라멛(121.125)]

어 얼마전에 내적으로 충돌체크하는거 책에서 봤는데 다시보니 반갑다 정성추!

[새우맨(222.120)]

와 강의를 써주셨네...ㅊㅊ

[푸롤로로롤(june0812)]

점을 저장할 때 한쪽 방향으로만 저장하면 연결성에 대한 정보가 담겨 있다고 할 수 있음. 임의의 점을 vertex[0]에 먼저 저장 하고 그 다음 점은 시계방향으로 한 칸씩 vertex[1]에 저장하고 그 다음 점은 vertex[2]에 저장하는 식으로 하면 됨

[익명(121.125)]

다른것들도 좋은 내용을 다루는데 그것들 보다도 에린카토 GDC 강의들은 전부 다 강추함. 제약조건이라던지, 볼만한 내용들이 엄청 많음.

[익명(118.40)]

너무 유익한 글

[dd(61.72)]

위치 보정은 물체를 이동만 시키면 안되고 회전도 적용시켜야 댈텐데... 존나 길고 얇은 막대기끼리 끄뜨머리에서 직각으로 충돌이러면 위치만 옮기는 거로는 충분치 않지. 속도 대신 위치넣어서 충격량 계산하듯 하면 댐. 그리고 충돌검출도 걍 gjk 쓰는 게 나을 걸. 예각만 문제가 아니라 아까 예로 든 존나 길고 얇은 막대기는 어쩔?

[ㅇㅅㅇ(14.33)]

개쩐다 인디겜갤의 보배