260219 통합보고서 파트1 GJK SAT

🧠 3D 간섭 해결 핵심 기술 통합 보고서 (파트 1): GJK, SAT 알고리즘

📝 작성일: 2026-02-19
📝 목적: GJK 및 SAT 알고리즘 관련 내용을 4개 원본 문서에서 수집하여 보고서 형식으로 재구성
📝 원본 문서:
💡 1. 260219_1200_3D알고리즘_심화_GJK_SAT_BVH_유전_LLM.md
💡 2. 260219_1945_3D충돌리서치_보강_GJK_SAT_Lib_LLM.md
💡 3. 260219_1910_additional_research_3D_GJK_SAT_LLM.md
💡 4. 260216_0220_3D_간섭해결_재배치_AI_휴리스틱_종합.md

📚 목차

• 파트 1: GJK 알고리즘
  • 1.1 핵심 아이디어, 쉬운 설명
  • 1.2 Minkowski Difference 개념
  • 1.3 Support 함수
  • 1.4 Simplex 개념 및 진화 과정
  • 1.5 동작 원리 단계별 설명
  • 1.6 의사코드, Python 코드 예제
  • 1.7 시각적 다이어그램 (ASCII)
  • 1.8 EPA (Expanding Polytope Algorithm)
  • 1.9 GJK 복잡도 및 특성
  • 1.10 BIM/MEP 활용 사례
  • 1.11 참고 자료 URL
• 파트 2: SAT 알고리즘
  • 2.1 핵심 아이디어, 쉬운 설명
  • 2.2 투영(Projection) 개념
  • 2.3 후보축 생성 방법
  • 2.4 2D vs 3D 차이 (후보축 4개 vs 15개, 그 이유)
  • 2.5 MTV(Minimum Translation Vector) 산출 방법
  • 2.6 의사코드, Python 코드 예제
  • 2.7 시각적 다이어그램 (ASCII)
  • 2.8 BIM/MEP 활용 사례
  • 2.9 참고 자료 URL
• 부록: GJK/SAT 알고리즘 종합 비교

🧠 파트 1: GJK 알고리즘

🔹 1.1 핵심 아이디어, 쉬운 설명

GJK(Gilbert-Johnson-Keerthi) 알고리즘은 두 볼록 도형이 서로 겹치는지 판별하는 알고리즘입니다. 1988년에 발표된 이 방법은 게임 엔진, 로보틱스, BIM 분야에서 가장 널리 사용되는 충돌 감지 기법 중 하나입니다.

직관적 비유: 두 손을 쥐어 서로 가까이 대보세요. 손과 손이 겹치는지 알려면 어떻게 하면 될까요? GJK는 아주 영리한 방법을 씁니다. 두 도형의 “차이(Difference)”를 계산한 뒤, 그 차이가 원점(0,0,0)을 포함하는지 확인합니다. 원점을 포함한다면 두 도형은 교차(충돌)하고 있는 것입니다.

아주 쉬운 설명:

• 두 볼록 물체 A, B가 겹치는지 보려면,
• “A-B 공간(민코프스키 차)”에서 원점(0,0,0)을 포함하는지만 보면 됩니다.
• GJK는 민코프스키 도형 전체를 만들지 않고,
• support 함수로 “필요한 극점”만 뽑아 simplex를 키워가며 원점을 포위하는지 봅니다.

핵심 직관:

• GJK의 성능 핵심은 “도형 전체”가 아니라 “극점 질의”(support)입니다.
• 볼록체 + support 구현만 있으면 다양한 형상을 같은 루프로 처리할 수 있습니다.

두 볼록 형상 간의 최소 거리/교차 여부를 판정하는 반복 알고리즘. 민코프스키 차(Minkowski Difference)가 원점을 포함하면 충돌이다.

🔹 1.2 Minkowski Difference 개념

Minkowski Difference(민코프스키 차집합)는 GJK의 핵심 수학 도구입니다.

도형 A의 점: {a1, a2, a3, ...}
도형 B의 점: {b1, b2, b3, ...}

Minkowski Difference = { a - b | a ∈ A, b ∈ B }

• A와 B가 겹치면 → Minkowski Difference가 원점(0,0,0)을 포함
• A와 B가 떨어지면 → Minkowski Difference가 원점을 포함하지 않음

Minkowski Sum: 두 점 집합 A와 B의 합 A (+) B = { a + b : a in A, b in B }. 장애물 공간에서의 C-obstacle 계산에 활용된다.

C_obs = O (+) (-R)   (O: 장애물, R: 로봇/객체)

모든 점의 쌍을 계산하는 대신, Support 함수를 사용하여 특정 방향으로 가장 멀리 있는 점만 효율적으로 계산합니다.

🔹 1.3 Support 함수

Support(A, d) = 도형 A에서 방향 d로 가장 멀리 있는 점
Support_diff(d) = Support(A, d) - Support(B, -d)

Support 함수는 도형의 꼭짓점 중에서 주어진 방향 벡터 d와의 내적이 최대인 점을 반환합니다.

import numpy as np

def support(shapeA, shapeB, d):
    # shapeA/shapeB: 꼭짓점 리스트라고 가정
    a = max(shapeA, key=lambda v: np.dot(v, d))
    b = max(shapeB, key=lambda v: np.dot(v, -d))
    return a - b

🔹 1.4 Simplex 개념 및 진화 과정

Simplex(심플렉스)는 n차원 공간에서 가장 단순한 형태입니다.

0-simplex : 점 (point)
1-simplex : 선분 (line segment)
2-simplex : 삼각형 (triangle)      ← 2D GJK
3-simplex : 사면체 (tetrahedron)   ← 3D GJK

GJK는 Minkowski Difference 공간 내에서 이 Simplex를 반복적으로 개선하여, 원점이 Simplex 안에 있는지 판별합니다.

좀 더 자세한 설명:
1) 두 도형의 지지점(support point)을 이용해 Minkowski Difference 위의 점을 찾습니다.
2) 그 점들로 simplex(점/선/삼각형/사면체)를 확장합니다.
3) simplex가 원점을 포함하는지 검사합니다.
4) 포함하면 충돌, 포함하지 않으면 원점을 더 잘 감싸도록 방향을 갱신합니다.

🔹 1.5 동작 원리 단계별 설명

단계 1: 초기 방향 d 설정 (임의 방향, 예: (1,0,0))
단계 2: Support 함수로 Minkowski Difference의 점 A 계산
단계 3: A가 원점 방향으로 전진하지 못하면 → 교차 없음(종료)
단계 4: Simplex에 A 추가
단계 5: 현재 Simplex에서 원점에 가장 가까운 점/선/면 찾기
단계 6: 새로운 탐색 방향 d = 원점 방향으로 갱신
단계 7: Simplex가 원점을 포함하면 → 교차 있음(종료)
단계 8: 포함하지 않으면 단계 2로 반복

요약:

1. 임의 방향 d 선택
2. support(A,d) - support(B,-d)로 점 하나 획득
3. simplex(점/선/삼각형/사면체)를 갱신
4. “원점 쪽으로 더 나아갈 수 있는지” 검사
5. 더 못 가면 비충돌, 원점 포위하면 충돌

🧪 1.6 의사코드, Python 코드 예제

🧪 의사코드 (원본 문서 4)

function GJK(shapeA, shapeB):
    d = initial_direction
    simplex = [Support(A-B, d)]
    d = -simplex[0]
    loop:
        point = Support(A-B, d)
        if Dot(point, d) < 0: return NO_COLLISION
        simplex.add(point)
        if DoSimplex(simplex, d): return COLLISION

🧪 Python 코드 예제 1 (원본 문서 1)

def GJK(shapeA, shapeB):
    d = (1, 0, 0)  # 초기 탐색 방향
    simplex = []

    # 첫 번째 점 계산
    point = support(shapeA, d) - support(shapeB, -d)
    simplex.append(point)
    d = -point  # 원점을 향하는 방향

    while True:
        # 새로운 지지 점 계산
        A = support(shapeA, d) - support(shapeB, -d)

        # 원점 방향으로 전진 불가 → 교차 없음
        if dot(A, d) < 0:
            return False  # No intersection

        simplex.append(A)

        # Simplex가 원점을 포함하는지 확인 + 새 방향 갱신
        contains_origin, d = do_simplex(simplex)

        if contains_origin:
            return True  # Intersection!

🧪 Python 코드 예제 2 (원본 문서 2)

def gjk_intersect(shape_a, shape_b) -> bool:
    d = (1.0, 0.0, 0.0)
    simplex = []

    p = support(shape_a, d) - support(shape_b, neg(d))
    simplex.append(p)
    d = neg(p)

    while True:
        a = support(shape_a, d) - support(shape_b, neg(d))
        if dot(a, d) <= 0:
            return False

        simplex.append(a)
        contains, d = do_simplex(simplex)  # line/triangle/tetrahedron 케이스 처리
        if contains:
            return True

🧪 Python 코드 예제 3 (원본 문서 3)

import numpy as np

def support(shapeA, shapeB, d):
    # shapeA/shapeB: 꼭짓점 리스트라고 가정
    a = max(shapeA, key=lambda v: np.dot(v, d))
    b = max(shapeB, key=lambda v: np.dot(v, -d))
    return a - b

def gjk_intersect(shapeA, shapeB):
    d = np.array([1.0, 0.0, 0.0])
    simplex = [support(shapeA, shapeB, d)]
    d = -simplex[0]

    while True:
        a = support(shapeA, shapeB, d)
        if np.dot(a, d) < 0:
            return False
        simplex.append(a)
        contains, d = do_simplex(simplex)  # 방향 갱신
        if contains:
            return True

🔹 1.7 시각적 다이어그램 (ASCII)

[2D GJK 예시 - 삼각형 Simplex]

     Minkowski Difference 공간

     ┌─────────────────────────┐
     │      점C                │
     │     /  \                │
     │    /    \               │
     │   /  O←─ \─── 원점이   │
     │  / (원점)  \    Simplex │
     │ /────────────\  안에!  │
     │ 점A          점B        │
     └─────────────────────────┘

     → 교차 판정: True (충돌)

[비충돌 케이스]

     ┌─────────────────────────┐
     │ 점A──점B                │
     │        \                │
     │         점C             │
     │                         │
     │              O (원점)   │
     │                         │
     └─────────────────────────┘

     → 원점이 Simplex 밖에 있음 → 충돌 없음

🔹 1.8 EPA (Expanding Polytope Algorithm)

GJK가 “충돌함”으로 판정한 후, 정확한 관통 깊이와 관통 방향(접촉 법선) 을 계산하는 알고리즘이다.

GJK의 단점: 오목(concave) 형상 직접 불가, 관통 깊이 미제공 (EPA 필요)

🧪 EPA 의사코드

function EPA(simplex, shapeA, shapeB):
    polytope = InitPolytope(simplex)
    loop:
        closestFace = FindClosestFace(polytope)
        support = Support(A-B, closestFace.normal)
        newDist = Dot(support, closestFace.normal)
        if (newDist - closestFace.distance) < TOLERANCE:
            return (closestFace.normal, closestFace.distance)
        RemoveFacingFaces(polytope, support)
        FillHole(polytope, support)

EPA의 출력인 관통 깊이와 방향은 MTV(최소 이동 벡터) 기반 분리에 직접 활용됩니다.

🏢 MTV 기반 분리 (EPA 결과 활용)

function ResolvePenetration(objA, objB, mtv):
    // 방법 1: 한쪽만 이동
    objA.position += mtv
    // 방법 2: 질량 비례 분배
    totalMass = objA.mass + objB.mass
    objA.position += mtv * (objB.mass / totalMass)
    objB.position -= mtv * (objA.mass / totalMass)
    // 방법 3: 우선순위 기반 (BIM)
    if objA.priority < objB.priority:
        objA.position += mtv
    else:
        objB.position -= mtv

🚀 Push-out vs 최적화 기반 재배치

🧠 1.9 GJK 복잡도 및 특성

• 장점: 형상 종류에 무관(볼록이면), 메모리 극소, 빠른 수렴
• 단점: 오목(concave) 형상 직접 불가, 관통 깊이 미제공 (EPA 필요)

🏢 1.10 BIM/MEP 활용 사례

• MEP 배관 간섭 감지: 배관(볼록 원통)과 빔(볼록 직육면체) 간 교차 여부를 GJK로 빠르게 판별
• 정밀 간섭 거리 계산: 두 부재 간 최소 이격 거리를 mm 단위로 계산하여 BIM 모델 검토에 활용
• 실시간 충돌 감지: 설계 변경 시 즉각적인 간섭 재검사 가능 (near-constant time 복잡도)
• 볼록 분해와 결합: 비볼록 형상(파이프 벤드 등)을 볼록 조각으로 분해한 뒤 GJK 적용

🏗️ 실무 파이프라인에서의 GJK 위치

매 물리 프레임:
1. Broad Phase (SAP / BVH) -> 잠재적 충돌 쌍
2. Narrow Phase (GJK + EPA / SAT) -> 접촉 매니폴드
3. Constraint Solver (Sequential Impulse / TGS) -> 접촉+조인트 동시 해결
4. Integration -> 속도/위치 갱신

[입력: BIM 모델 + 규칙 세트]
    -> [1. Spatial Indexing] Octree/BVH
    -> [2. Broad Phase] AABB + Sweep-and-Prune
    -> [3. Narrow Phase] GJK + EPA
    -> [4. 간섭 분류 및 우선순위화] Hard/Soft 분류, 클러스터링
    -> [5. 해결 전략 선택] 규칙 1차 -> 실패 시 최적화
    -> [6-A. 이동 기반] MTV + 우선순위 + 제약 전파
       [6-B. 경로 재탐색] A* 3D Grid
    -> [7. 검증] 새 간섭 발생? Yes -> 5단계 복귀
    -> [8. 출력: 수정된 BIM 모델]

🧠 시나리오별 알고리즘 선택

🔗 1.11 참고 자료 URL

• GJK 상세 설명 - dyn4j.org
• GJK 시각적 인터랙티브 설명 - CSE442
• Wikipedia - GJK Algorithm
• GJK 200줄 C 구현 - GitHub
• GJK 알고리즘 심층 분석 - winter.dev
• dyn4j - GJK Distance/Closest Points
• dyn4j - EPA

🧪 데모 비디오 URL

• Reducible GJK: https://www.youtube.com/watch?v=ajv46BSqcK4
• Casey Muratori GJK(심화 구현): https://www.youtube.com/watch?v=Qupqu1xe7Io

🧠 파트 2: SAT 알고리즘

🔹 2.1 핵심 아이디어, 쉬운 설명

SAT(분리 축 정리)는 놀라울 정도로 직관적인 아이디어에 기반합니다.

비유: 두 물체 사이에 얇은 종이를 집어넣을 수 있다면, 두 물체는 충돌하지 않습니다. SAT는 이 “종이”를 수학적 축(Axis)으로 표현합니다. 모든 후보 축에 두 도형을 투영했을 때, 하나라도 투영이 겹치지 않는 축이 있으면 두 도형은 충돌하지 않습니다.

반대로, 모든 축에서 투영이 겹친다면 두 도형은 충돌 중입니다.

모든 후보 축에 투영하여, 하나라도 겹치지 않으면 비충돌. MTV(최소 이동 벡터) 를 직접 산출 가능하다.

🔹 2.2 투영(Projection) 개념

▫️ 쉬운 설명

• 투영은 “그림자 만들기”입니다.
• 어떤 축(axis) 방향에서 물체를 비추면, 물체의 모든 점이 1차원 선 위 값으로 바뀝니다.
• SAT에서는 이 1차원 구간끼리 겹치는지 비교합니다.

투영은 “벡터가 어떤 축에 얼마나 길게 걸려 있는지”를 숫자로 바꾸는 과정입니다. 도형의 모든 꼭짓점을 특정 축 방향으로 눕혀서 1차원 값(스칼라)로 만든 다음, 그 구간이 겹치는지 확인합니다.

▫️ 핵심 수식

• 점 v를 축 a로 투영한 스칼라 값:
• proj(v, a) = dot(v, a)
• 도형 전체 투영 구간:
• min_i dot(v_i, a), max_i dot(v_i, a)

🎯 왜 dot인가?

• dot은 “해당 축 방향 성분”을 뽑아내는 연산이기 때문입니다.
• 축이 단위벡터일 때 직관이 가장 좋고, 값 해석도 쉽습니다.

▫️ Python 예시 1

from typing import Iterable, Tuple

Vec3 = Tuple[float, float, float]

def dot(a: Vec3, b: Vec3) -> float:
    return a[0]*b[0] + a[1]*b[1] + a[2]*b[2]

def project_interval(vertices: Iterable[Vec3], axis: Vec3) -> Tuple[float, float]:
    vals = [dot(v, axis) for v in vertices]
    return min(vals), max(vals)

def overlap_1d(i1: Tuple[float, float], i2: Tuple[float, float]) -> bool:
    return not (i1[1] < i2[0] or i2[1] < i1[0])

▫️ Python 예시 2

import numpy as np

def project(vertices, axis):
    axis = axis / np.linalg.norm(axis)  # 정규화 필수
    dots = [np.dot(v, axis) for v in vertices]
    return min(dots), max(dots)

🔗 투영 관련 참고 자료 URL

• 3Blue1Brown (dot의 기하 직관): https://www.3blue1brown.com/lessons/dot-products
• Math Insight (dot=projection 인터랙티브): https://mathinsight.org/applet/dot_product_projection
• dyn4j SAT(투영 설명): https://dyn4j.org/2010/01/sat/
• 3Blue1Brown 영상: https://www.youtube.com/watch?v=LyGKycYT2v0

🔹 2.3 후보축 생성 방법

▫️ 동작 원리 단계별 설명

단계 1: 후보 축 목록 생성
   - AABB: x, y, z 축 (3개)
   - OBB: 각 도형의 로컬 축 (최대 15개 = 3+3+9)
   - 폴리곤: 각 면의 법선 벡터

단계 2: 각 축에 두 도형의 모든 꼭짓점을 투영
   proj(vertex, axis) = dot(vertex, axis)

단계 3: 각 도형의 투영 범위 [min, max] 계산

단계 4: 두 범위가 겹치는지 확인
   겹침 없음: minA > maxB 또는 minB > maxA

단계 5: 하나라도 겹치지 않는 축 발견 → 충돌 없음 (종료)

단계 6: 모든 축에서 겹침 확인 → 충돌 있음
   → 최소 겹침(overlap) 축 = MTV 방향

🧪 OBB 교차 검사 의사코드 (원본 문서 4)

function OBB_Intersect(A, B):
    axes = [A.axisX, A.axisY, A.axisZ, B.axisX, B.axisY, B.axisZ]
    for i in A.axes:
        for j in B.axes:
            axes.append(Normalize(CrossProduct(i, j)))
    for axis in axes:
        if not Overlap(ProjectOBB(A, axis), ProjectOBB(B, axis)):
            return false   // 분리축 발견
    return true

객체의 주축 방향에 맞춰 회전된 직육면체. 분리축 정리(SAT) 로 교차 검사한다. 3D OBB-OBB 검사 시 테스트할 분리축: 3 + 3 + 9 = 15축.

⚖️ 2.4 2D vs 3D 차이 (후보축 4개 vs 15개, 그 이유)

▫️ 요약 결론

• 2D(두 볼록 다각형): 보통 “각 도형의 edge 법선”만 검사 -> 예시로 사각형-사각형이면 4개 축
• 3D OBB-OBB: 최대 15개 축
  • A의 면 법선 3개
  • B의 면 법선 3개
  • A edge x B edge 크로스곱 9개

🎯 왜 3D에서 9개(edge x edge)가 추가되는가?

• 3D에서는 “면-면 분리”뿐 아니라 “edge-edge 분리” 방향이 존재하기 때문입니다.
• 이 edge-edge 분리 방향이 바로 크로스곱 축입니다.
• 이 축을 빼면 false positive(겹친다고 오검출) 가능성이 생깁니다.

▫️ 엄밀 근거 (OBBTree 1996)

• 두 볼록 다면체가 떨어져 있으면, 분리축은
  • 어떤 면의 법선에 수직이거나
  • 양쪽 도형의 각 edge 쌍에 동시에 수직인 축 중 하나에 존재합니다.
• OBB는 고유 face orientation 3개, edge direction 3개를 가져서 총 15축이 충분조건입니다.

⚖️ 2D vs 3D 차이표

▫️ Python 형태 (OBB-OBB 축 생성 스켈레톤)

def candidate_axes_obb(A_axes, B_axes):
    axes = []
    axes.extend(A_axes)  # 3
    axes.extend(B_axes)  # 3
    for a in A_axes:
        for b in B_axes:
            c = cross(a, b)
            if norm(c) > 1e-9:  # 평행/퇴화 축 제거
                axes.append(normalize(c))
    return axes  # 최대 15

🔹 2.5 MTV(Minimum Translation Vector) 산출 방법

MTV(Minimum Translation Vector)는 두 물체를 분리하기 위해 필요한 최소 이동 벡터입니다.

모든 축에서 겹친다면, 겹침량이 가장 작은 축이 최소 이동 벡터(MTV) 방향입니다. MTV = (최소 겹침 축) x (겹침량).

MTV를 적용하면 두 물체가 정확히 분리됩니다. BIM에서는 이 벡터만큼 MEP 요소를 이동시켜 간섭을 해소합니다.

🧪 2.6 의사코드, Python 코드 예제

🧪 의사코드 (원본 문서 4)

function SAT_with_MTV(A, B):
    min_overlap = INFINITY
    for axis in CandidateAxes(A, B):
        overlap = ComputeOverlap(Project(A, axis), Project(B, axis))
        if overlap <= 0: return NO_COLLISION, null
        if overlap < min_overlap:
            min_overlap = overlap
            mtv_axis = axis
    return COLLISION, mtv_axis * min_overlap

🧪 Python 코드 예제 1 (원본 문서 1)

def compute_MTV(shapeA, shapeB):
    min_overlap = float('inf')
    mtv_axis = None

    for axis in get_all_candidate_axes(shapeA, shapeB):
        # 각 축으로 투영
        projA = project(shapeA, axis)
        projB = project(shapeB, axis)

        # 겹침 계산
        overlap = min(projA.max, projB.max) - max(projA.min, projB.min)

        if overlap <= 0:
            return None  # 분리 축 존재 → 충돌 없음

        # 최소 겹침 축 갱신
        if overlap < min_overlap:
            min_overlap = overlap
            mtv_axis = axis

    # MTV = 가장 겹침이 작은 축 방향 × 겹침 크기
    return mtv_axis * min_overlap

🧪 Python 코드 예제 2 (원본 문서 3)

def sat_mtv(shapeA, shapeB, axes):
    min_overlap = float('inf')
    mtv_axis = None

    for axis in axes:
        minA, maxA = project(shapeA, axis)
        minB, maxB = project(shapeB, axis)
        overlap = min(maxA, maxB) - max(minA, minB)
        if overlap <= 0:
            return None  # 분리 축 발견
        if overlap < min_overlap:
            min_overlap = overlap
            mtv_axis = axis

    return mtv_axis / np.linalg.norm(mtv_axis) * min_overlap

🔹 2.7 시각적 다이어그램 (ASCII)

[2D SAT - 두 직사각형]

  y축 투영:
  ┌────┐     ┌────┐
  │  A │     │  B │
  └────┘     └────┘
  ←───→     ←───→   ← 겹침 없음! → 분리 축 발견

  x축 투영:
  ┌────┬────┐
  │ A  │ B  │
  └────┴────┘
  ←─────────→       ← 겹침 있음

  결론: y축에서 분리 → 충돌 없음


[3D OBB - 후보 축 목록]

  OBB A의 로컬 축: Ax, Ay, Az           (3개)
  OBB B의 로컬 축: Bx, By, Bz           (3개)
  엣지 쌍 크로스 곱: Ax×Bx, Ax×By ...  (9개)

  총 15개 축을 모두 검사해야 함

🏢 2.8 BIM/MEP 활용 사례

• AABB 사전 필터링: BVH 트리에서 빠른 AABB 충돌 검사 (3축만 필요)
• OBB 정밀 검사: 회전된 배관, 사선 빔에 대한 정확한 간섭 판별
• MTV 기반 자동 이격: 충돌한 MEP 요소를 MTV 방향으로 최소 이동시켜 간섭 해소
• 피팅/조인트 검사: 복잡한 형상은 볼록 다각형으로 근사 후 SAT 적용

🔗 2.9 참고 자료 URL

• SAT 상세 설명 - dyn4j.org
• 비디오 게임 물리 충돌 감지 - Toptal
• 충돌 감지 강의 자료 - Johns Hopkins
• OBBTree 원문(PDF)
• SAT 간단 개요(라이브러리 문서)

🧪 데모 비디오 URL

• SAT Explanation: https://www.youtube.com/watch?v=Ap5eBYKlGDo
• 시각 데모(SAT + OBB): https://www.youtube.com/watch?v=EB6NY5sGd08
• SAT 구현 예시: https://www.youtube.com/watch?v=7Ik2vowGcU0

⚖️ 부록: GJK/SAT 알고리즘 종합 비교

⚖️ 알고리즘 비교표

⚡ 알고리즘 성능 특성

알고리즘    시간복잡도        공간복잡도    특징
─────────────────────────────────────────────────────
GJK         O(k) 반복        O(1)          볼록 형상 필수
SAT         O(n×m) 축 수    O(n+m)        MTV 직접 산출

🧠 상황별 최적 알고리즘 선택

┌──────────────────────────────────┬──────────────────────────────┐
│ 상황                             │ 권장 알고리즘                │
├──────────────────────────────────┼──────────────────────────────┤
│ 두 볼록 형상 간 정밀 충돌 판별  │ GJK                          │
│ 다각형 메쉬 간 빠른 충돌 판별   │ SAT (AABB 먼저, OBB 정밀)    │
│ 수천 개 부재 간 충돌 검색       │ BVH + GJK/SAT                │
└──────────────────────────────────┴──────────────────────────────┘

🎮 GPU 병렬화 적합도

본 문서의 검색 자료 출처 요약