Patch Decomposition for Efficient Mesh Contours Extraction

3줄 요약

1. Panagiotis Tsiapkolis와 Pierre Bénard의 2024년 논문은 삼각형 메쉬에서 윤곽선 모서리를 빠르게 찾는 방법을 제안한다.
2. 모서리를 패치로 구성하고 각 패치의 면 방향과 공간 정보를 검사해, 윤곽선이 생길 수 없는 패치는 한꺼번에 제외한다.
3. 윤곽선 추출 속도는 전수 검사의 최대 5.3배였다. 실제 Vulkan 데모에서는 컴퓨트 셰이더 방식이 태스크와 메쉬 셰이더 방식보다 효율적이었다.¹

어떤 선을 찾는가

삼각형 메쉬의 모서리 중, 카메라를 향한 면과 반대 방향의 면이 공유하는 모서리가 이 논문의 추출 대상이다. 카메라가 이동하거나 메쉬가 변형되면 그 모서리도 달라진다. 물체의 외곽과 표면이 겹쳐 보이는 부분을 표현하는 이 선은 선화 렌더링, 그림자 볼륨, 미분 렌더링 등에 쓰인다.

가장 단순한 방법은 모든 모서리에 인접한 두 면의 방향을 검사하는 것이다. 그러나 전체 모서리 가운데 윤곽선에 해당하는 모서리는 적다. 화면의 깊이 정보나 법선 정보로 선을 검출하는 방법도 있지만, 메쉬에 속한 선분이 필요한 작업에서는 3차원 모서리를 직접 구하는 방법이 유용하다.²

기존 연구는 트리 같은 계층 구조로 검사할 모서리를 줄이거나, GPU에서 모든 모서리를 병렬로 검사했다. 저자들은 계층을 탐색하는 작업이 GPU의 병렬 처리에 잘 맞지 않는다는 문제에 주목했다. 이 논문이 만든 결과물은 서로 독립적으로 검사할 수 있는 패치 목록이다.

패치마다 무엇을 저장하는가

패치는 모서리 여러 개를 포함한다. 패치마다 모서리 목록과 함께 두 종류의 정보를 저장한다.

• 법선 원뿔은 모서리에 인접한 면들의 법선 방향을 포함한다. 원뿔의 중심 방향과 반각으로 면 방향의 분포를 표현한다.
• 구의 중심과 반지름은 카메라에서 검사 지점들을 바라보는 방향을 제한하는 데 쓰인다.

실행할 때는 카메라에서 구를 바라보는 시선 원뿔과 법선 원뿔을 비교한다. 두 원뿔에 속한 방향들이 서로 직교할 가능성이 없으면, 해당 패치에는 윤곽선 모서리가 없으므로 검사를 생략한다. 가능성이 있으면 패치의 모서리를 개별 검사한다.

검사할 모서리가 적다는 이유만으로 처리 시간이 짧아지는 것은 아니다. 패치를 검사하는 데도 시간이 든다. 저자들은 특정 거리에서 카메라 방향을 고르게 바꿨을 때 패치를 개별 검사 대상으로 선택할 확률을 추정하고, 하드웨어에서 측정한 처리 시간을 반영했다. 패치 하나의 기대 비용은 다음과 같다.

$$E(\mathcal{P}) = t_{\mathcal{P}} + H(\mathcal{P})\,t_e\,\xi$$

여기서 패치 검사 시간은 $t_{\mathcal{P}}$, 모서리 하나의 검사 시간은 $t_e$, 패치의 모서리 수는 $\xi$다. $H(\mathcal{P})$는 패치를 검사한 뒤 개별 모서리도 검사해야 할 확률이다. 법선 방향이 비슷하고 시선 원뿔이 좁은 패치일수록 이 확률이 낮다.³

구를 더 작게 만드는 방법

보통 바운딩 구는 모서리의 양 끝점을 모두 포함한다. 이 논문은 윤곽선 검사에 필요한 조건을 다시 검토했다. 면의 앞뒤 방향은 모서리를 연장한 직선의 어느 점을 기준으로 계산해도 같다. 따라서 구가 모든 모서리를 감쌀 필요는 없고, 각 모서리를 연장한 직선과 한 번씩 교차하면 된다.

출처: Tsiapkolis와 Bénard, HAL 공개 원고, Figure 3.

모서리 중점들의 좌표를 평균하면 Reduced Sphere에 사용할 구의 중심이 정해진다. 반지름은 그 중심에서 각 모서리의 연장 직선까지 잰 수직 거리 중 최댓값이다. 평균 반지름은 Mean Sphere를 쓸 때보다 약 20% 작아졌다. 두 방법의 전처리 시간은 비슷했다.⁴

나는 이 조건의 차이가 인상적이었다. 구가 포함해야 하는 대상을 모서리 전체로 정하면 필요 이상으로 큰 구가 된다. 저자들은 면 방향을 판정하는 데 필요한 점만 포함해도 된다는 성질을 이용해 검사량을 줄였다.

패치를 어떻게 구성하는가

처음에는 모서리 하나당 패치 하나를 만든다. 이후 두 패치를 합쳤을 때 기대 비용이 얼마나 감소하는지 계산하고, 감소량이 가장 큰 쌍을 반복해서 합친다. 더 합쳐도 비용이 줄지 않으면 중단한다. 마지막에는 패치 검사 비용이 개별 모서리 전수 검사 비용보다 저렴한지도 확인한다.

모든 패치 쌍을 계속 비교하면 전처리에 너무 오래 걸린다. 저자들의 구현에서는 패치마다 유리한 병합 후보 50개를 캐시한다. 공간적으로 가까운 모서리로 최대 4,096개 규모의 그룹을 구성하고, 그룹별로 패치를 병합한다. 후보를 캐시해도 최선의 병합을 선택하는 결과는 같으며, 계산량은 줄어든다. 공간 분할은 비교할 후보를 제한하므로 최종 패치 구성에도 영향을 준다.

전처리는 런타임 성능과 별도로 고려해야 한다. 논문의 단일 스레드 C++ 구현에서 패치 생성 시간은 Bunny가 2분 48초, Dragon이 29분 28초였다. 필터링된 모서리가 약 758만 개인 Thai Statue는 5시간 9분 38초가 걸렸다. 같은 표에서 meshoptimizer의 생성 시간은 각각 1초 미만, 5초, 1분 2초였다. 이 방법은 패치 생성에 더 많은 시간을 들여 이후 윤곽선 추출을 빠르게 한다.

GPU에서는 얼마나 빨라졌는가

저자들은 정적 물체, 환경, 리깅된 캐릭터를 비교했다. 카메라 조건은 모델 주위에 고르게 분포한 42개 시점과 6개 거리였다. GPU 실험에서는 이 252개 조건을 모델 인스턴스로 만들어 한 번에 평가했다. 아래는 GeForce GTX 1080에서 측정한 평균 GPU 계산 시간이다.⁵

모델	전수 검사	Reduced Sphere	전수 검사 대비 속도
Bunny	21.0μs	3.9μs	5.3배
Armadillo	88.5μs	28.55μs	3.1배
Dragon	155.9μs	56.55μs	2.8배
Thai Statue	1,579μs	604μs	2.6배
Roman Bath	8.3μs	4.6μs	1.8배
Spaceship	17.9μs	9.8μs	1.8배
Space Station	18.7μs	8.9μs	2.1배
Pigman	20.8μs	10.8μs	1.9배
Tuba Gunner	18.4μs	11.5μs	1.6배
Gawain	91.4μs	66.3μs	1.4배

범용 메쉬렛 생성 라이브러리인 meshoptimizer와도 비교했다. Bunny에서 meshoptimizer의 윤곽선 추출 시간은 9.4μs였고, 이 논문의 방법은 3.9μs였다. 법선 원뿔의 폭은 윤곽선 추출에 맞춰 구성한 패치에서 더 좁았다. 저자들은 이 차이 덕분에 더 많은 패치를 제외할 수 있었다고 설명했다.

애니메이션에서는 같은 본에 속해 강체로 변환되는 모서리들을 본별로 처리한다. 여러 본의 영향을 받아 변형되는 모서리들은 패치 제외를 적용하지 않고 개별 검사한다. 모델과 리깅 방식에 따라 적용 가능한 비율이 달라지며, 실험 모델의 강체 모서리 비율은 Pigman과 Gawain에서 45%, Tuba Gunner에서 98%였다.

실제로 선을 그렸을 때

Vulkan 데모는 두 방식을 구현했다. 첫 번째는 컴퓨트 셰이더로 패치를 검사하고 윤곽선 모서리 인덱스를 기록한 뒤 선분을 그린다. 두 번째는 태스크와 메쉬 셰이더로 추출과 그리기를 한 패스로 처리한다.

GeForce RTX 2080 SUPER, 1920×1080 해상도에서 컴퓨트 방식이 더 빨랐다. Bunny 121개를 표시한 장면은 패치 제외를 끄면 1.3ms, 켜면 0.48ms였다. 태스크와 메쉬 셰이더 방식은 각각 121ms와 32ms였다. 저자들은 출력할 선분이 없는 메쉬 셰이더 호출이 많아 두 번째 방식의 성능이 저조했을 가능성을 제시했다. 컴퓨트 방식은 대신 모든 인스턴스의 모서리 인덱스를 기록할 버퍼를 확보해야 한다.

이 결과에서 나는 패치 구성을 평가하는 기준과 실행 방식이 함께 중요하다는 점을 기억하게 됐다. 계층이 없어도 윤곽선이 없는 패치를 충분히 제외할 수 있었고, 한 패스로 처리하는 방식보다 두 번의 컴퓨트 처리 후 선분을 그리는 방식이 더 빨랐다. 저자들은 비강체 변형에서도 패치 제외가 가능하도록 개선하는 일을 후속 과제로 제시했다.

출처

Panagiotis Tsiapkolis와 Pierre Bénard, Patch Decomposition for Efficient Mesh Contours Extraction. Computer Graphics Forum 43(4), e15154, 2024. Eurographics Symposium on Rendering 2024 발표 논문이다.

• 원문: HAL
• 공개 원고: Mesh_Contours.pdf
• 정식 출판본: DOI 10.1111/cgf.15154
• 저자 동영상: Pierre Bénard의 부연 영상

커버는 공개 원고의 Figure 1, 본문 그림은 Figure 3을 인용했다.