Convex decomposition

• 다른 이름: approximate convex decomposition, ACD
• 카테고리: Software & tooling › Simulation & twins
• 태그: collision-detection, simulation, geometry-processing, meshes, contact

볼록하지 않은 형상, 보통 삼각형 메시를 그 합집합이 원래 형상을 근사하는 볼록 조각들의 집합으로 나누어, 빠른 볼록 충돌 알고리즘을 쓸 수 있게 하는 것.

정의

볼록 분해(convex decomposition)는 볼록하지 않은 형상을, 그 합집합이 원래 형상을 재현하거나 근사하는 볼록한 부분들의 모음으로 나눈다. 로보틱스에서 입력은 보통 물체, 그리퍼 또는 로봇 링크의 삼각형 메시이고, 출력은 그 충돌 형상으로 쓰이는 볼록 껍질들의 집합이다. 이유는 알고리즘에 있다. GJK와 EPA 같은 표준적인 세부 단계(narrow-phase) 충돌 및 거리 계산 루틴은 볼록 형상에서 작동하며, 많은 물리 엔진은 움직이는 물체에 볼록 형상을 요구하거나, 메시를 아무 알림 없이 하나의 볼록 껍질로 대체한다. 껍질 하나로 표현한 머그잔에는 입구도 손잡이 구멍도 없다. 분해는 그런 특징들을 여러 볼록 조각으로 되살린다.

다면체의 정확한 분해에는 매우 많은 부분이 필요할 수 있고 최소 개수를 찾는 것은 계산적으로 어려우므로, 실용적인 도구들은 근사 볼록 분해를 계산한다. 이 도구들은 조각과 그 조각 자신의 볼록 껍질 사이의 거리 같은 오목도 지표로 측정하여, 모든 조각이 선택한 허용 오차 안에서 볼록해질 때까지 형상을 나눈다. V-HACD는 오랫동안 시뮬레이션 파이프라인에서 흔히 쓰는 선택이었고, CoACD는 메시를 직접 자르며 얇은 벽이나 입구처럼 접촉에 중요한 특징을 보존하려는 더 새로운 충돌 인지 방법이다. 둘 다 오목도 임계값과 최대 부분 개수에 대한 파라미터를 제공한다.

결과는 충실도와 비용 사이의 절충이다. 조각이 많을수록 실제 표면을 더 가깝게 따르지만 충돌 검사가 느려지고 조각들이 만나는 곳에서 접촉 생성에 잡음이 많아진다. 조각이 적으면 빠르지만, 그리퍼 손가락이나 페그가 들어가야 할 수도 있는 오목한 영역이 메워진다. 분해는 입력 메시의 품질도 물려받는다. 구멍, 자기 교차, 비다양체 모서리가 있는 스캔 메시는 흔히 먼저 수리가 필요하다. 볼록 분해는 부호 거리 필드, 삼각형의 경계 볼륨 계층, 구 근사 같은 충돌 표현과 관련이 있지만 이들과는 다르며, 이들은 속도와 정확도 사이에서 다른 절충을 한다.

중요한 이유

시뮬레이션한 파지, 삽입, 밀기 작업이 실제처럼 동작하는지는 충돌 형상에 크게 좌우된다. 볼록 분해는 시각용 메시를, 접촉이 많은 작업이 의존하는 오목한 특징을 유지하면서 물리 엔진이 빠르게 시뮬레이션할 수 있는 형상으로 바꾸는 일반적인 단계다.

주요 응용

• 물리 시뮬레이터에서 물체와 로봇 링크의 충돌 메시
• 시뮬레이션에서 생성하는 대규모 파지 및 조작 데이터셋
• 샘플링 기반 모션 플래너의 빠른 충돌 검사
• 오목한 특징을 보존해야 하는 삽입 같은 접촉이 많은 작업
• CAD 메시나 스캔 메시를 URDF 또는 MJCF 충돌 형상으로 변환

실제 사례

시뮬레이션에서 파지 데이터셋을 구축하는 팀이 수천 개의 스캔한 가정용 물체 메시에서 시작한다. 각 메시는 먼저 수밀하게 수리하고 스케일을 정규화한 다음, 오목도 임계값과 부분 개수 상한을 두고 CoACD에 넣는다. 그 결과로 나온 볼록 조각들은 물체의 URDF나 MJCF 파일에 별도의 충돌 메시로 기록하고, 원래 메시는 렌더링용으로 남겨 둔다. 파지를 생성하기 전에 팀은 물체 일부를 표본으로 눈으로 확인한다. 안쪽 공간이 메워진 그릇이나 몸체와 합쳐진 손잡이는 더 엄격한 임계값을 받는다. 수십 개의 조각으로 분해되는 물체는 대규모 병렬 환경을 느리게 하므로 시뮬레이션 속도도 지켜본다.

흔한 오해

• 물리 엔진은 그려진 그대로의 메시와 충돌을 계산한다 — 많은 엔진은 각 충돌 메시의 볼록 껍질을 쓰므로, 메시를 분해하지 않으면 오목한 영역이 사라진다
• 볼록 조각이 많을수록 언제나 시뮬레이션이 좋아진다 — 조각이 늘면 충돌 검사가 느려지고 조각 사이의 이음매에서 가짜 접촉이 생길 수 있다
• 볼록 분해는 정확하다 — 실용적인 도구들은 근사적이며 선택한 허용 오차보다 작은 오목부를 메우므로, 작은 구멍이나 좁은 틈이 막힐 수 있다

알아야 할 사람

• 로봇과 물체 에셋을 준비하는 시뮬레이션 엔지니어
• 시뮬레이션에서 데이터셋을 구축하는 파지 및 조작 연구자
• 충돌 검사를 다루는 모션 플래닝 엔지니어
• CAD 모델을 URDF나 MJCF 파일로 변환하는 메이커

관련 기술

• V-HACD
• CoACD
• GJK 알고리즘
• 볼록 껍질(Convex Hull)
• MuJoCo
• PhysX

관련 용어

• Penalty-Based Contact Model
• Signed Distance Field
• Axis-Aligned Bounding Box
• Graph of Convex Sets
• URDF
• Grasp Quality Metric

관련 프로젝트

• GENESIS: World's fastest physics engine: 43M FPS for embodied AI learning
• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• PyBullet: Python physics simulator for robotics and RL research with fast CPU-based simulation
• RLinf: Scalable infrastructure for post-training foundation models via RL
• Webots: Cross-platform robot simulator with built-in models, sensors, and development environment
• NVIDIA Isaac Sim: NVIDIA Omniverse app for AI-driven robot simulation and testing