Skip to main content

볼록꼴 분해 개선에 대한 연구

9월

02, 2020

by Khanovich


테크

Roblox는 2014년 구조적 입체 지오메트리(CSG)를 도입했습니다. 당시 Tim Loduha가 이끄는 시뮬레이션 팀에 소속되어 있던 저에게 주어진 가장 큰 임무는 이 프로젝트에서 물리 시뮬레이션을 돕는 것이었습니다. 그 당시 Roblox는 매우 작은 규모였고, 물리 팀에는 개발 이외의 업무를 담당하는 두 사람만이 근무하고 있을 뿐이었습니다. 따라서 빠른 결과를 내고자 불렛 피직스(Bullet Physics)라는 인기 있는 라이브러리의 도움을 얻기로 했습니다. 불렛 피직스는 Roblox의 니즈에 잘 부합하는 것으로, 접근이 쉽고 다양한 장점을 가진 데다가 오픈 소스라는 특성 및 탁월한 확장성을 지니고 있기 때문에 오늘날 많은 게임에서 사용하고 있습니다.

Roblox는 물리 엔진을 자체 제작했지만, PartOperations를 시뮬레이션하기 위한 용도로 다음 두 개의 중요한 요소는 불렛 피직스에서 도입해 사용하였습니다.

    1. 복합적 지오메트리의 충돌 검출
    2. 임의의 3D 지오메트리의 충돌을 검출하기 위한 볼록한 물체 집단을 생성하는 볼록꼴 분해(솔루션 공간과 성능 제한으로 인한 업계 표준)

프로젝트 중 볼록꼴 분해에 대한 작업을 할 때, 불렛 피직스에서 가지고 온 다음 두 개의 알고리즘으로 실험을 실시했습니다.

  • 계층적 근사 볼록꼴 분해(HACD)
  • 근사 볼록꼴 분해(ACD)

HACD의 결과는 만족스러웠지만 ACD가 그 견고성 및 일관성으로 인해 첫 상품 출시에서 우위를 차지했습니다.

정밀 피드백

이 기능을 출시한 후, 충돌 검출을 통해 더 나은 지오메트리 작업을 원하던 사용자들이 엄청나게 많은 피드백을 보내 주었습니다. 덮여 있는 출입구나 창틀의 중요한 표면과 같이, 거칠게 복셀화된 것에 ACD를 사용하면 다양한 형상을 만들게 됩니다.

이 복잡한 형태가 복셀라이저를 통해서 어떻게 보일지 생각해보면 오목한 형태가 어떻게 감추어져 있는지 상상할 수 있습니다(아래).

우리에게는 뭔가 더 나은 것, 즉 원래의 지오메트리를 보여주는 것이 필요했습니다. 복셀화는 표면이 복셀 그리드에서 ‘끊어지는’ 경향이 있기 때문에 더 이상 고려 대상이 되지 않았습니다. 엄청나게 많은 형태를 입력해도 매번 수정할 필요 없이 자동으로 실행되는 것이 필요했습니다.

계층적 근사 볼록꼴 분해

결국 다음과 같은 특성으로 인하여 HACD로 돌아오게 됩니다.

  • 알고리즘의 초기 상태로 입력 메시 사용
  • 원래의 입력 지오메트리에 대한 오차 확인
  • 비 다양체 처리 (ACD도 마찬가지임)
  • 복셀화하지 않음

위에 링크된 연구에 따르면, HACD에는 3가지의 기본 요소가 있습니다.

  • 이중 그래프 삭제
  • 볼록꼴 외피 생성
  • 오목꼴 오차 계산

알고리즘 개요:

1. 입력된 메시는 그래프로 변환되는데, 이 그래프에서 각 삼각형은 노드(점), 두 삼각형이 만나는 모서리는 이 됩니다. 이것이 이중 그래프의 시작이고, 여기서 각 삼각형은 첫 볼록꼴 외피가 됩니다.

2. 그래프의 모든 선을 조사하고, 이 선들을 연결해 산출한 컨벡스 헐(주어진 도형을 포함하는 최소의 철체)을 결합해 예상 볼록 외피를 계산합니다.

3. 그 다음 이 예상 볼록 외피를 사용하여 원래 지오메트리에 의하여 발생하는 오목 오차를 계산합니다. 이 오차를 사용하여 오차가 가장 적은 모서리에서 가장 많은 모서리를 정렬합니다.

4. 마지막으로 오차가 가장 작은 모서리를 선택합니다.

a. 오차가 정해 놓은 최대 허용 오목꼴 오차보다 작으면 모서리를 버리고(모서리 병합, Edge-collapse), 두 점을 모서리의 예상 볼록 외피로 교체합니다.

b. 오차가 정해 놓은 최대 허용 오목꼴 오차보다 크면 끝냅니다.

5. 모서리 병합으로 모서리가 없어질 때마다, 이웃하는 모서리에 대한 이전 오목꼴 오차 결과를 무효화합니다. 그리고 이웃하는 모서리에 대하여 2단계와 3단계를 반복합니다.

6. 새 오목 오차를 바탕으로 다시 계산된 모서리를 모서리 정렬 리스트에 업데이트합니다.

7. 남은 모서리의 오차값이 국제 허용 오차보다 커질 때까지 4단계에서 6단계까지를 반복합니다(이것은 알고리즘을 시작하기 전에 사용자가 지정합니다).

우리는 오픈 소스 HACD 코드의 가장 최신 버전을 얻어 몇 개의 메시에 테스트했습니다. 자동차와 같은 형태의 경우, 전보다 훨씬 나아진 충돌 지오메트리를 만들어 냈지만 다른 형태의 입력 메시에 대한 결과는 좋지 않았습니다. 알고리즘은 이론상 문제가 없는 것으로 보여 다음 단계에서는 무엇이 이러한 이상한 결과를 만들어내는지 알아보기로 했습니다.

비주얼 디버깅

내부에서 실행이 잘 되는지 알 수 없었기 때문에, 우리는 조사의 속도를 높이기 위해 비주얼 디버거를 사용해 이중 그래프 모서리를 제거하는 모든 과정을 기록하고, 원래 지오메트리에 생기는 모든 변화를 한번에 한 단계씩 파악했습니다.

이 툴을 이용하여 오목 오차 계산볼록 외피 생성 모두에 문제가 있다는 것을 발견했습니다. 제대로 형성된 볼록 외피가 중요한 큰 오목 형태를 막아버리는 경우가 있으나 오목 오차 계산에서는 이 외피를 형성하는 모서리 병합에 오차가 없는 것으로 표시합니다. 볼록 외피 생성에 있어서는, 모서리 충돌이 때때로 꼭지점을 만들어 면을 잃게 됩니다. 이로 인하여 표면의 극히 일부나 전체가 손실되기도 합니다.

따라서 철저히 분석하고 각 요소에 대한 로직을 스스로 만들어야 한다는 것을 깨닫게 되었습니다.

오목 오차 계산(알고리즘 개요의 3단계)

오목 오차 계산의 목적은 원래의 지오메트리에 생긴 ‘손상’을 정량화하는 것입니다. 모서리를 제거하는 것은 모서리가 연결하는 외피를 결합함으로써 새 볼록 외피를 만들면서 발생합니다. 원래 연구에서는 이 오차를 여러 방법으로 추적할 수 있다고 하였고, 실행에는 새로 만들어진 예상 볼록 외피 내부에서 원래의 표면부터 새롭게 형성된 표면까지의 거리 중 가장 먼 거리를 사용했습니다. 우리도 같은 논리를 사용할 것입니다.

수량을 구하기 위해서는 다음과 같은 두 가지 정보가 필요합니다.

  • 소스 지오메트리 중 정량화할 수 있는 항목
  • 이 모서리를 제거하고 만들어지는 예상 볼록 외피(개요의 2단계)

원래의 HACD 실행에는 삼각형마다 몇 개의 샘플 포인트를 원래 표면의(정량화할 수 있는) 항목으로 사용하였습니다(개요의 1단계를 진행하는 동안). 그때 이 점들은 페이스 노멀(Face normal)을 따라 오목꼴을 방해하는 볼록 외피의 뒷면을 찾기 위하여 레이캐스팅하는데 사용됩니다. 원래 표면에서 뒷면까지의 가장 긴 거리는 오차로 간주됩니다. 이것은 논리적인 접근이지만, 각 삼각형마다 작동하는 샘플링 밀도 때문에 큰 삼각형 면이 있는 단순한 형태일 경우 오목을 가로막는 물체를 스캔할 때 엄청나게 많은 블라인드 스팟(숨겨진 지점)이 생기는 문제가 발생했습니다.

이상적인 시스템이라면 실험대상인 볼록 외피에 있는 원래 삼각형 면으로부터 표면을 뽑아내지만(Extrusion), 이것을 해결하고 최적화하는 데 너무 많은 비용이 들기 때문에 대신 조금 더 일정하게 분포되어 있는 원래의 삼각형 표면을 샘플링하기로 했습니다.

배열을 이룬 그리드 거리에 따라 모든 삼각형에 대한 표면 샘플 포인트를 균일하게 생성합니다(왼쪽 참조). 이것으로 많은 점들이 만들어지기 때문에 오목 오차 계산 과정 중 새롭게 형성되는 볼록 외피 대비 확인하여야 하는 포인트를 빠르게 걸러내는 방법이 필요합니다. 이를 위하여 표면 샘플 포인트 그룹을 빠르게 선택하는 시험 대상인 외피의 바운딩 박스(Bunding box)를 사용하여, 모든 샘플 포인트를 충돌 검출에 사용했던 것과 유사한 (3차원의) 공간 그리드로 보냅니다.

바운딩 박스 안에서 찾은 포인트를 잡으면 새롭게 만들어진 볼록 외피의 ‘내부’에 있는 포인트를 더 걸러냅니다. 이는 현재의 볼록 외피가 덮고 있는 오목꼴을 잡아내기 위한 것입니다. 그 다음 외피의 삼각형에 대응하는 샘플 포인트로부터 레이캐스팅합니다. 더 이상 오차가 나오지 않으면 모두 거리 0값을 돌려보내지만, 위의 다이어그램과 같이 문제가 되는 볼록 외피는 원 표면에서의 레이캐스팅이 예상 볼록 외피의 삼각형 중 하나의 뒷면에 영향을 끼치게 만듭니다.

요약하면, 오차가 생성되는 과정을 다음과 같이 설명할 수 있습니다.

  • (알고리즘 개요의 1단계 과정 중) 각 삼각형에서 균일하게 포인트를 샘플링하여 공간 그리드로 보냅니다.
  • 테스트를 하려는 볼록 외피의 바운딩 박스를 잡아서 모든 포인트를 이 바운딩 박스 안에 있는 그리드에 모읍니다.
  • 볼록 외피의 ‘내부’에 있는 모든 샘플 포인트에 대하여, 원래 표면 노멀(Surface normal)에 따라 모은 포인트로부터 레이캐스팅하고 그것이 볼록 외피 뒷면에 닿는지 봅니다.
  • 뒷면에 닿는 가장 멀리 있는 레이가 오목 오차로 되는 것입니다.
  • 볼록 외피가 원 표면 밖으로 튀어나오지 않으면 결과는 0이 됩니다.
  • 이것은 모서리가 병합하는 것을 중지시킬 수 있기 때문에, 첫 샘플 레이캐스팅이 최대 허용 글로벌 오차를 초과하자마자 빠져나감으로써 최적화될 수 있습니다.

이 시스템은 볼록 외피가 원래 형태에 얼마나 많은 오차를 만들어낼지를 확인할 수 있는 확실한 방법입니다. 그러나 아직 해결하지 못한 한가지가 있습니다. 이 방식은 3D 볼록 외피일 경우에만 잘 작동합니다. 볼록 외피가 편평할 경우, 2D 볼록 외피가 형성되는 동안 샘플 포인트들이 테스트할 방향으로 정렬할 수 없습니다. 오른쪽 형태를 예로 들면, 파란 삼각형과 초록색 삼각형이 볼록 외피를 형성하여 빨간색 삼각형과 결합하려고 하는 경우, 이 볼록 외피 내부의 샘플 포인트는 거리가 0인 경우 외에는 볼록 외피의 뒷면에 영향을 주지 않을 것입니다. 이 문제를 제대로 해결하려면 완전히 다른 2D 오차 계산 과정을 생각해 내야 하고, 그 과정은 앞에서 설명한 것만큼 복잡한 것입니다.

대신 약간 수정을 할 수 있습니다. 원래의 두 볼록 외피 면적의 합을 결과물의 면적과 비교할 수 있는데, 결과물의 외피 면적이 두 소스 외피의 합보다 크면 하나의 오목을 닫을 수 있고, 이 때 남은 것의 면적 제곱근이 오목 오차로 계산될 수 있습니다. 마지막으로, 입력 볼록 외피가 제대로 형성된다면, 이것이 잠재적인 볼록 외피 후보들에 존재하는 오차를 검출할 방법이 되는 것입니다.

볼록 외피 생성: 퀵헐(Quickhull) (알고리즘 개요 중 2단계)

오목 오차 계산을 수정한 다음, 여전히 존재하는 문제들을 해결하기 위하여 비주얼 디버거를 사용하였습니다.

  1. 큰 오목꼴을 막아버리는 볼록 외피들은 여전히 결과값을 0으로 내며 오목 오차 테스트를 통과합니다.
  2. 두 개의 볼록 외피를 결합할 때 원래 형태에 있는 구멍을 빠져나가면서 가끔 꼭지점을 사라지게 합니다.

원래 HACD 실행에서는 다양한 퀵헐 알고리즘을 사용하였는데 이 선택은 알고리즘이 현재의 볼록 외피에 새로운 포인트를 빠르게 더해주기 때문에 완벽했습니다. 모서리가 병합될 때마다 새로운 포인트를 더해줍니다. 비주얼 디버거를 통하여 모은 데이터를 처음 검토한 결과, 결과물로 만들어진 외피에 때때로 뒤집어진 삼각형이 있다는 것을 알게 되었는데 이는 앞서 설명한 오목 오차 계산 방법의 버그였습니다.

이 알고리즘이 작동하는 방식은 기존의 외피에 추가할 새 포인트를 고를 때 점이 바깥에 존재하는 평면의 삼각형을 발견하는 것입니다. 이 삼각형들은 삭제되도록 표시되고 다른 삼각형에 면하는 변들이 볼록 외피를 덮으면서 생긴 점들과 함께 새로운 그룹의 삼각형을 만드는데 사용됩니다. Valve 소프트웨어가 사용하는 퀵헐 알고리즘에서 배울 수 있는 점은 그 알고리즘이 부동소수점 오차에 매우 민감한데 특히 외피에서 삼각형들이 동일 평면상에 있을 때 매우 민감합니다. 오른쪽의 예시는 단순한 경우의 단면으로서 밸브가 설명하는 문제를 보이지 않습니다.

이 문제를 이해하려면 왼쪽에 있는 형태와 같은 단면을 생각해 보아야 합니다. 삼각형 E와 F가 같은 평면상에서 바깥에 있는 점을 인지하는지 안쪽에 있는 점을 인지하는지 알 수 없는 퀵헐 상황을 보도록 하겠습니다. 사실 최악의 상황은 F는 내부의 점을 인지하는데 E가 외부의 점을 인지하는 경우입니다. 퀵헐에서는 삼각형의 방향이 이웃하는 삼각형에 의하여 정해지기 때문에 이러한 서로 다른 위상(토폴로지)는 잘못된 방향의 삼각형을 만들거나 완전 실패의 결과를 냅니다.

Valve의 Dirk Gregorius는 한 평면에 있는 삼각형들을 한 개의 면을 가진 개체로 결합시킴으로써 이러한 부합이 일어나지 않도록 하는 방법으로 문제를 해결합니다. 그러나 우리의 경우는 각각의 삼각형들 사이의 거리가 중요하기 때문에 이 방법을 사용할 수 없습니다. 대신 우리는, 동일 평면상에 있는 다수의 삼각형들이 두꺼운 평면을 만듦으로써 모든 삼각형이 연결되어 확실하게 한 평면 안에 들어오도록 했습니다. 이것이 점이 내부에 있는지 외부에 있는지를 계산할 수 있는 유일한 방법입니다. 특히 이것은 Dirk의 면-결합(Face-merge) 방법과 비슷한 방법으로 문제를 해결하는 것이며 동시에 각 삼각형에 대한 직접 참조값을 유지할 수 있는 방법입니다.

앞에서의 오목 오차 계산과 같이, 2D의 경우도 생각해 보아야 합니다. 다양한 입력 데이터로부터 볼록꼴 분해 코드를 보호하려면, 3D 퀵헐뿐만 아니라 2D 퀵헐도 반드시 실행하여 동일 평면상 삼각형을 결합시켜야 합니다. 동일 평면상 삼각형에 같은 프로세스를 사용해 보면 이는 작동하지 않고 입력 꼭지점을 종종 지우거나 오류가 날 것입니다.

일관된 부동 소수점 처리

우리는 확신하고 이해했던 오목 오차볼록 외피 생성에 대한 해결책을 찾은 후에도 여전히 문제에 직면해 있었지만, 비주얼 디버깅은 항상 반 변질된 표면의 경우에 해당한다는 것을 발견했습니다.

이것은 3D 지오메트리에서 가장 중요한 문제 중 하나입니다. 부동점을 일관되게 처리하는 것은 반드시 필요합니다. 이 알고리즘이 안정되게 작동하려면 엡실론 개념과 양자화된 정보가 통합되어야 합니다.

전체 알고리즘 과정에서 엡실론 개념은 여러 곳에서 사용되었습니다.

  • 입력 지오메트리에서 이중 그래프를 만들 때, 미분화된 꼭지점들은 하나의 꼭지점에 결합됩니다.
  • 볼록 외피 생성 과정에서 볼록 외피들이 동일 평면상에 있는지를 테스트해야 하고, 2D 모드와 3D 모드 중 어느 것을 사용해야 하는지를 결정해야 합니다.
  • 오목 오차 계산 과정 중, 현재 외피의 평편도를 테스트해야 하고 볼록 외피 내부에 부딪히는 레이캐스트의 엡실론이 일정해야 합니다.

양자화 거리(s)가 알고리즘의 형태로 결정되면 s를 엡실론 및 편평한 정도에 따른 값으로 처리해야 합니다. 이것은 단일 평면의 가로길이 s 안에 들어가는 모든 포인트가 동일 평면에 있는 것으로 처리됨을 의미합니다. 단일 평면의 가로길이 s 안에 들어가는 모든 포인트 그룹에서 생성되는 볼록 외피는 2D 작업으로만 이루어져야 합니다. 또한 우리가 찾으려는 엡실론 관련 모든 정보는 단일 디멘션에서 이루어져야 하는데 이것은 개체의 볼륨이나 면적에 대한 정보를 평면에서 가장 멀리 있는 거리와 비교해야 함을 의미합니다.

결론

탐구 수행 후 한 발자국 물러나 ‘우리가 배운 것은 무엇인가?’라는 질문을 하는 것은 의미 있는 일입니다. HACD에 있어서는, 일정한 수준의 결과를 얻기 위해 다음과 같은 전체적인 개념에 대한 중요성을 꼭 강조하고 싶습니다.

  • 균일한 표면 샘플링 – 알고리즘이 얼마나 잘 처리하고 있는지를 알려주는 원래 지오메트리의 게이지를 잘 이해해야 합니다.
  • 오목 오차 계산 과정에서 2D와 3D간의 구분, 그리고 볼록 외피 생성 – 입력 지오메트리가 동일한 평면상의 면이 없는 개체를 매끈하게 만들지 않는 경우 알고리즘은 2D 작업을 하느라 엄청난 시간을 보내게 됩니다. 알고리즘의 2D 단계는 매우 중요합니다.
  • 양자화와 부동소수점 처리를 위한 일관된 시스템 – 동일 평면 문제를 퀵헐로 해결하면서 입력 삼각형의 연결성을 계산하고 2D 및 3D 작업을 분리하는데 중요합니다.

이 세 개념은 HDCA 라이브러리에 있는 엄청난 양의 내부 리팩터를 이끄는 핵심 근간이며, 이로 인해 HACD 라이브러리를 Roblox의 삼각형 메시와 CGS 개체용 일반 자동 충돌 지오메트리 생성기로 출시할 수 있게 되었습니다. 하지만 향후 시스템 향상을 위해 지속적으로 상당한 작업이 필요합니다.

이 방식에 따라 할 수 있는 연구는 다양합니다.

  • 병행성, 성능 개선.
  • 체적 보존: 현재의 알고리즘은 체적(볼륨)을 유지하지 않습니다. 이는 VHACD가 해결해야 할 문제입니다.
  • 2D 오목 오차 개선: 현재의 2D 오목 오차 계산은 닫혀 있는 볼록형에 반대되는 영역에 있는 변화를 확인하기 때문에 긍정 오류를 냅니다. 이것은 차단된 모서리 병합으로 인하여 수렴된 알고리즘에서 제거되지 않아야 하는 잠재적으로 옳은 결과를 제거하기 때문에 문제가 될 수 있습니다.
  • 미세조정의 결과를 낼 수 있도록 고급 사용자가 알고리즘 조정하는 것을 보여주는 것.

Roblox는 항상 디폴트로 작업하는 기능을 중요하게 여깁니다. 또한 충돌 지오메트리를 수동으로 조절하지 않고 양질의 충돌을 만들어낼 수 있도록 하기 위해 계속해서 노력하고 있습니다. 아직 완벽한 픽셀 충돌은 구현하지 못하고 있지만, 복잡한 CSG 작동 결과를 자동으로 시뮬레이션할 수 있게 되어 몹시 기쁩니다. 이는 Roblox에서 어떠한 형태의 지오메트리에 대해서도 충돌 생성을 할 수 있도록 하는, 흥미롭고 새로운 국면으로 가는 첫 단계입니다. 앞으로 우리의 연구와 사용자 피드백이 우리를 어디로 이끌지 매우 기대가 됩니다.

결과

모든 결과는 원래의 HACD와 Roblox HACD에 일정한 설정을 하여 계산된 것입니다. 각 색상은 다른 볼록 외피를 표현합니다.

SetNClusters 1
ScaleFactor 1000 // 모든 사물 개체의 크기는 작업을 위하여 1000 x 1000 x 1000 크기의 정육면체로 조정되었습니다.
ConnectDist 0.1 // 양자화 거리입니다.
Concavity 10 // 이것은 모서리-제거용 허용 오목 오차입니다.
CompacityWeight 0 // 이 설정은 둘레 기반 모서리 충돌 순서를 따릅니다. 우리는 사용하지 않습니다.
VolumeWeight 0 // 이 설정은 볼륨(체적)기반 모서리 충돌 순서를 따릅니다. 우리는 사용하지 않습니다.

 

왼쪽: RoHACD 중앙: 입력 지오메트리 오른쪽: HACD


Roblox Corporation이나 이 블로그는 특정 회사나 서비스를 홍보하지 않습니다. 또한 블로그에 포함된 정보의 정확성, 신뢰성, 완전성에 대하여 어떠한 보장이나 약속도 하지 않습니다.

이 블로그 게시물은 Roblox 테크 블로그에 수록된 글입니다.