GJK 알고리듬: 단순한 일을 기묘하고 아름답게 해결하는 방법

 (computerwebsite.net)
2P by GN⁺ | ★ favorite | 댓글 1개
  • GJK 알고리듬은 두 도형이 겹치는지 확인하는 방법
  • 도형 A와 도형 B가 겹치는지 확인하려면, 두 도형의 점 중 하나라도 겹치는지 확인하면 됨

Minkowski 차집합

  • 두 도형의 모든 점을 빼서 새로운 집합을 만듦.
  • 이 새로운 집합에 원점이 포함되면 두 도형이 겹친다는 의미임.
  • 이를 Minkowski 차집합이라 부름.

알고리듬의 기본 아이디어

  • A와 B의 Minkowski 차집합이 원점을 포함하는지 확인함.
  • 차집합이 원점을 포함하면 두 도형이 겹침.

알고리듬 단계

  1. 초기화: 임의의 방향 벡터 d를 설정하고, 첫 번째 점 p를 찾음.
  2. 점 찾기: d와 p의 내적을 계산하여 양수이면 계속 진행, 음수이면 종료.
  3. 새 점 추가: p에서 원점 방향으로 새로운 점을 찾음.
  4. 단순화: 첫 번째 두 점을 기준으로 새로운 점을 추가하여 단순화함.
  5. 원점 포함 여부 확인: 단순화된 도형이 원점을 포함하는지 확인함.
  6. 반복: 원점을 포함할 때까지 또는 포함하지 않는다는 증거를 찾을 때까지 반복함.

GN⁺의 의견

  • 흥미로운 점: GJK 알고리듬은 복잡한 문제를 간단한 수학적 변환으로 해결하는 좋은 예시임.
  • 도움이 되는 이유: 충돌 감지와 같은 실시간 그래픽스에서 매우 유용하게 사용됨.
  • 비판적 시각: 알고리듬의 구현이 복잡할 수 있으며, 정확한 이해가 필요함.
  • 관련 기술: 다른 충돌 감지 알고리듬으로는 SAT(Separating Axis Theorem) 등이 있음.
  • 고려 사항: GJK 알고리듬을 사용할 때는 도형의 복잡성과 계산 비용을 고려해야 함.

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 1990년대에 GJK 때문에 거의 1년을 고생했음
    3D 충돌 감지에 유용하고, 최근접점 알고리즘으로도 쓸 수 있음. 기본 아이디어는 이해하기 쉬움. 두 개의 볼록 입체가 있을 때 각 입체에서 임의의 점을 하나씩 잡고 두 점 사이 거리를 구한 뒤, 현재 점에서 각 모서리를 따라 이동해 거리를 개선해 보고 새 최근접점을 고르는 과정을 반복함
    하지만 최근접점이 더 이상 꼭짓점이 아니면 이 방식이 깨지고, 이때 단체(simplex) 개념이 필요해짐. 최근접점 조합은 꼭짓점-꼭짓점, 꼭짓점-모서리, 꼭짓점-면, 모서리-모서리, 모서리-면(유일해가 없음), 면-면(유일해가 없음)으로 나뉘며, 단체 처리는 사실상 이 경우들을 분석하는 일에 가까움
    실제로는 문제가 많이 생김. 물리 엔진에서는 물체가 면-면 접촉 상태로 안정되는 일이 많고, 단일 점 충돌 모델은 진동이나 잘못된 움직임을 만들 수 있음. 또한 위치가 면-면 접촉으로 수렴할 때 GJK는 큰 값들 사이의 작은 차이를 다루게 되어 부동소수점 유효 자릿수를 완전히 잃을 수 있음. 종료 조건도 무한 루프를 일으킬 수 있음
    이론적으로는 우아하지만, 실제로는 어려운 수치해석 문제임. 그래도 아마 이 문제에 대한 가장 빠른 접근일 가능성이 큼. 일반적인 경우 O(log N)이고, 이전 위치와 가장 가까운 상황에서 마지막 해를 시작점으로 쓰면 O(1)에 가까움
    Oxford의 고 Steven Cameron 교수가 GJK를 제대로 동작시키는 데 많은 작업을 했고, 1990년대 후반 첫 상용 3D 래그돌 시스템인 "Falling Bodies"에서 GJK를 사용했음

    • 접촉을 찾고 나면 거의 반드시 그걸로 뭔가 해야 하고, 대부분 유용한 처리를 하려면 실제 겹침 정보를 알아야 함
      이걸 구하는 쪽이 수치적으로는 더 나쁨. GJK가 만든 단체에서 시작해 바깥으로 확장하고, 그 과정에서 삼각형 분할을 해야 함. 성능 좋게 구현하기는 완전 악몽에 가까움
    • https://www.youtube.com/watch?v=5lHqEwk7YHs
      특허는 이제 만료됐는지, 코드를 공개할 생각이 있는지 궁금함. 역사적으로 의미 있고 Doom 소스 읽기 같은 흥미로운 자료가 될 것 같음

  • GJK 충돌 감지 알고리즘을 직관적으로 설명한 글을 찾지 못해서, 오후 시간을 들여 직접 정리했음
    더 명확하고 효율적으로 만들 방법이 있으면 알려주면 좋겠음. 물론 고등학교 2학년이 수학 관련 내용을 설명한 글이라는 점은 적당히 감안해 줬으면 함

    • 글이 아주 명확함. 계속 이런 작업을 하면 언젠가 훌륭한 교과서를 쓸 수도 있을 만큼 재능이 보임
      이미 좋지만 더 완벽하게 만들려면 몇 가지를 추가할 수 있을 듯함. 최악의 경우 시간 복잡도에 대한 짧은 설명, 종료 조건을 다루는 별도 섹션, 그리고 설명 중간중간 의사코드가 있으면 좋겠음
      지금처럼 수학적 관점에서 설명하는 방식은 잘 맞고 유지할 가치가 있음. 다만 각 단계 뒤에 S(•) 같은 보조 함수를 정의하면서 알고리즘이 어디까지 진행됐는지를 담는 짧은 의사코드를 덧붙이면 더 좋을 듯함
      OpenAI의 숨겨진 모델에 대한 글도 좋았음. 인상적인 결과물을 만든 사람이 또 뭘 했는지 찾아보는 데 들이는 시간은 거의 항상 보람 있음
    • 수학자로서 말하자면, 수학 독자를 대상으로 쓴다면 몇몇 표현을 아주 약간 다르게 했을 것 같다는 정도가 최악의 비판임
      제목은 "as simply as possible"이어야 함. GJK 알고리즘은 몰랐지만 지금 Calculus III를 가르치고 있었다면 이 내용을 수업에 넣을 방법을 찾아봤을 것 같음. 그만큼 설명이 좋음
    • 이 알고리즘은 종료가 보장되는지 궁금함
      글 끝의 부드럽게 둥근 직사각형 예시에서 답에 점점 가까워지기만 하고 실제로 도달하지 못하는 걸 막는 장치가 무엇인지 모르겠음. 물론 실제 컴퓨팅에서는 실용적인 정밀도 한계 이후로 계속할 이유가 없다는 건 알고 있음
    • 두 번째 그림의 세 집합 A, B, A-B가 헷갈림
      처음에는 A와 B에 어떤 변환을 적용해서 A-B 모양이 나온다는 뜻으로 받아들였음. 몇 번 다시 읽고 나니 A-B는 왼쪽에 있는 두 집합이 아니라 다른 A와 B의 교집합을 나타내는 것 같고, 그 교집합이 원점 또는 0,0과 겹친다는 점이 중요하다는 뜻으로 보임. 맞는지 궁금함

  • 같은 알고리즘을 다룬 영상 발표: https://www.youtube.com/watch?v=ajv46BSqcK4

  • 글이 매우 명확하고 흥미로움
    두 볼록 집합의 교차 여부를 확인하는 다른 방법으로는, 첫 번째 볼록 집합에 속한 점과 두 번째 볼록 집합에 속한 점의 차이의 노름을 최소화하는 볼록 최적화 문제를 푸는 방식이 있음. 최적값이 0이면 두 집합은 교차함
    GJK 알고리즘과 볼록 최적화를 비교해 보면 흥미로울 것 같음. 어느 쪽이 더 유리한지는 잘 모르겠음

    • 흥미로운 질문임. 겹침이 충분히 크면 내점법이 빨리 종료될 수도 있어 보임. 영리한 조기 종료 조건도 추가할 수 있을 것 같음

  • 첫 이미지가 비볼록 도형의 교차를 보여주는데, 알고리즘이 볼록 도형에서만 동작한다는 사실은 훨씬 뒤에야 나와서 약간 오해를 부를 수 있음

    • 비볼록 도형은 볼록 도형들로 나눠서 처리한다고 설명되어 있음

  • openSCAD에서 Minkowski 함수를 한동안 써 왔는데, 그게 실제로 무엇인지 알게 되어 좋음

  • 예상보다 관심을 많이 받게 되었으니, 개인 웹사이트가 사실상 정교한 내부 농담 모음이라는 점은 말해둬야 할 듯함
    연락하고 싶거나 할 일이 있으면 답글로 알려주면 됨

    • 연구 프로젝트 멘토링에 관심이 있다면 메일 보내도 됨: bersub@cmu.edu
    • 사이트가 좋고 멋진 사람 같음. 계속 멋진 걸 만들면 좋겠음

  • 거의 10년 전에 Casey의 훌륭한 설명을 바탕으로 GJK를 구현했음: https://www.youtube.com/watch?v=Qupqu1xe7Io

  • 민코프스키 기하와 관련된 글을 쓴 적이 있음: https://nickp.svbtle.com/asteroid-intersections

답변달기