물리 엔진에서의 충돌 처리 충돌처리

물리 엔진에서의 충돌 처리는 3 가지 정보를 필요로 합니다. 

1. Contact point : 충돌점입니다.
2. Contact normal : 충돌해서 튕겨나올 방향을 결정합니다.
3. Penetration depth : 얼마나 침투했는지를 나타냅니다.

제가 생각하는 간단하고, brute force 한 방법은 SAT (Separating Axis Theorem) 로 충돌여부를 판정하고, 최소 분리 edge (3d 에선 plane) 를 구해서 penetration vector 를 구하고, 폴리곤과 상대 폴리곤의 각각의 정점 포함여부를 검사해서 contact point 를 계산하는 방식입니다. 실제로 제가 만든 2D 물리엔진인 physicsRus (http://juhlnet.egloos.com/3820233) 는 이렇게 구현했습니다.


좀 더 효율적인 방법은 GJK (Gilbert–Johnson–Keerthi) 로 충돌여부를 검사하고, 충돌했을 경우 EPA (Expanding Polytope Algorithm) 로 penetration vector 를 구하고, edge clipping 으로 contact point 와 penetration depth 를 구하는 방식입니다. 대다수의 물리엔진들이 SAT 보다는 GJK/EPA 같은 효율적인 알고리즘들을 사용합니다. GJK 알고리즘은 빠르게 충돌여부를 판단할 때도 쓸 수 있을 뿐만 아니라 두 convex 폴리곤의 가장 가까운 거리를 구할때에도 사용할 수 있습니다.


GJK/EPA 알고리즘을 바탕으로 데모를 만들어 봤습니다.

참고: 
GDC 2010: Computing Distance with GJK by Erin Catto



덧글

  • 레인보우 2012/06/28 20:47 # 삭제 답글

    좋은정보 감사합니다~!
  • 개발자 2013/07/15 12:24 # 삭제 답글

    와우! 우리나라에도 이런 분이 계시다니! 웹코딩으로도 이런게 가능하군요~ 물리엔진에 검색중에 좋은 사이트 발견했네요.
    한가지 질문이 있는데, 오래된 글이라 답변이 달리지 모르지만, 의문점이 있어 적어 놓고 갑니다.

    올려주신 소스를 분석했는데 polygon shape의 충돌점 검출 부분에 의문이 있습니다.
    올려주신 글을 보면 SAT로 충돌 여부 검출후 MSA를 검출 한다고 나왔는데, 소스상에는

    //Space.prototype.genTemporalContactSolvers 함수 내에서

    body1.isCollidable(body2) 로 동적인지만 검사하고

    body1.bounds.intersectsBounds(body2.bounds)에서 단순이 AABB 교차 방식으로만 충돌 여부를 체크하내요.

    그리고 바로

    collision.collide를 호출해서 shape 별로 충돌점 검출 하는 알고리즘으로 넘어가던데.

    폴리곤 충돌 모델에서도 poly2Poly() 함수를 보면

    findMSA()에서 단지 A 폴리곤의 각 점을 돌면서 B폴리곤 모서리 평면 법선 벡터를을 이용해서
    내부에 있으면서 가까운 점을 찾을 뿐이고,

    findVerts()에서도 해당 점이 B폴리곤에 있는데 AABB를 사용해서 검사만 하고, 바로
    contactArr로 넣던데..

    이후에 살펴봐도 더 이상 충돌점 검출연산을 하지 않던데...
    그러면 A폴리곤의 점을 충돌점으로 바로 사용 하는 건가요?

    소스를 보닌 SAT구현 부분이 없고, MSA도 간단하게 구현 되있어서 이렇게 질문드립니다.
    Box2d와 병행해서 분석하고 있는데, 구현 로직이 다르내요..
    Box2d 보다 간단하게 구현되었는데 웹상에서 돌아가는거 보면, 잘 돌아가서 신기하고..
    혹 제가 못 본 부분이 있나요?
    box2dlite 돌려봐도 충돌번이 각 꼭지점에만 있지 않고 모소리 위에나 내부에도 빨간 점으로 표시 되서요.

    p.s. 근데 정말 대단하시내요!! 09년도에 고퀄러티 3d 엔진도 만드시고,
    3d그래픽관련해서도 상당하시던데. 지금쯤 엄청난 스킬을 계시겠죠.ㅠㅠ
    트위터에 보니 대학도 휴학하고 독학으로 하셨다고 하는데, 예비군도 다녀 오신거 보면
    저와 비슷하거나 한두살 정도 많으실거 같은데, 비교되서 한숨만 나오내요...
    전 아직도 학생때부터 가지고 있던 3d엔진과 그래픽쪽으로 목표를 아직도 다가가지 못했는데...

  • juhlnet 2013/07/16 11:46 #

    반갑습니다. ^^
    이렇게 장문의 댓글은 처음이네요.

    그럼 우선 답변을 하자면..

    SAT 를 정식으로 하려면 각 edge plane 별로 투영해서 거리 비교를 해야하는데, 일반적인 2D poly 일 경우, SAT 를 생략해도
    상대 poly 의 edge 를 기준으로 거리 비교를 하는 코드가 간단하다고 생각이되어서 하지 않았습니다. (box vs box 의 경우라면, 하는게 더 효율적이긴 하지만요)

    그리고, 충돌점은.. findVerts() 에서 poly 끼리 겹쳐진 vertex 를 찾아서 충돌점으로 사용합니다.
    위 그림의 빨간점을 보시면 이해가 빠르실 것 같습니다.

    사실 충돌 normal 과 길이가 같다면 두개의 충돌 점을 평균내서 사용해도 무방하다고 봅니다. 제 추측이 지만 box2dlite 가 그런 경우가 아닌가 싶네요.

    ps. 도움이 되실 거 같아서 몇 마디 적자면..
    저도 비슷한 경험이 있습니다. 자극을 많게 받게 되더군요. 벽에 부딪힌 느낌도 들구요.
    그때 제 수학실력으로는 부족하다는 걸 깨닫고, 몇 개월 동안 코딩없이 수학관련 지식만 쌓았습니다.
    물론 지금도 원하는 만큼은 아니지만, 그게 모멘텀이 되었던거 같아요.
    나중에 관련 포스팅을 하는게 어떨까 싶네요.
  • 개발자 2013/07/16 15:30 # 삭제 답글

    오래된 글인데 하루만에 답글이 올라와서 감사합니다. 최근 글이 작년 9월이라... 반은 포기했었는데...
    덕분에 고민이 해결 됐습니다.
    역시 따로 SAT 구현 로직은 없었군요.

    그리고 자세히 보니 findVerts()에서 A,B 두 폴리곤을 다 검사해서 내부 점을 찾고 없으면 findVertsFallback()으로 넘어 가네요.
    결국은 A, B 폴리곤의 각 점만이 충돌점으로 선택되어지는 거였내요.

    ps. 이런 멋진 걸 구현 해주시고 소스도 공개 해주셔서 감사합니다. 물리 엔진쪽 공부하고 있었는데 엄청 도움이 되었습니다.
    (opengl로 구현선 3d 엔진이라니...탐이나는 소스내요. ^^;;; 저도 빨리 구현 해봐야 할텐데..)
    인터넷을 돌아 다닐때마다 저보다 한참이나 높은 능력을 가진 분들을 발견하는데,
    그때마다 제 자신이 작아지는 거 같아 한 숨만 나오내요.
    대학때부터 가지고 있었던 목표를 아직도 못 이루었는데, 다른 분들은 더 높은 곳에 계시니...
    근데 혹시 jc에서 근무 하셨나요? 09년도 경향 기사에 동일이름을 가진 분이 인터뷰 하셔서..
    대학에 관해서 비슷한 관점으로 인터뷰하셔서.. 아카데미 언급한걸 보면 독학하셨다고 하는 아닌것 같기도 하고. 더욱이 그분은 안경을 안 썼는데..
    혹여나 해서 질문 드려 봅니다. ^^
  • juhlnet 2013/07/16 16:07 #

    동명이인인가보네요
댓글 입력 영역