Potree 논문 번역 및 정리

작성일 | In |
WebGL 기반으로 수백억의 Cloud Point를 다른 응용프로그램 없이 웹에서 렌더링할 수 있는 성과를 보여준 Potree 논문에 대한 번역과 정리를 해봤다.

완벽하게 번역을 하지는 않았고, 중복되는 내용이 많아 꼭 필요한 내용과 추가로 논문을 읽으면서 필요했던 지식들을 잘 정리한 블로그들을 링크로 연결해 놓았다.

아직 작성중 ..

목차

  1. 소개 1.1 동기 1.2 문제정의 1.3

1.1 Motivation 동기

Point Cloud는 3D 모델로 자주 사용되는 “삼각형 모델?” 보다는 점들의 구성으로 이루어져있다. 주로 현실세계를 레이저 스캐닝이나 혹은 사진측량법과 같은 다양한 스캐닝 방법을 통해 만들어진 데이터 들이다. Potree는 3D 지도 또는 지구본 생성, 도시의 건축 프로세스 또는 변화 추척, 숲 또는 다른 형태의 지형, 3D 게임/영화 에셋 생성, 움직임과 포즈(POS) 추척 등의 다양한 사례로 사용되어지고 있다. 많은 사례에서, Point Cloud는 row data로 다뤄지며, “삼각형 모델?” 또는 2D 이미지로 변환하여 보정된다.

클라이언트 혹은 유저에게 이러한 모델을 보여주기 위해 거대한 데이터를 다룰 수 있는 어플리케이션의 설치가 필요했으며, 메모리를 너무 많이 차지했기에 하드디스크 자체를 보내주는 일도 가끔 있었다.

WebGL이 출시 되면서 3D 컨텐츠가 웹 브라우저를 통해 표현되는게 유행하기 시작하며, 주요 브라우저와 데스크탑 뿐만아니라 모바일에서도 기본적으로 지원하는 표준으로 진화했다. WebGL은 개발자, 예술가, 회사, 연구소 등 많은 곳에서 다른 소프트웨어의 설치 없이 고객에게 그들의 컨텐츠를 보여주는 용도로 사용하고 있다. Sketchfab과 같은 서비스는 WebGL에 대한 기본지식이 없는 상태로도 사용가능하다.

대부분의 경우 컨텐츠의 용량이 작기에 다운받거나 로드하는데 문제가 생기지 않는다. 하지만 이와 반대로 메모리를 초과하거나 다운로드를 받는데 몇 시간씩 걸리는 데이터도 존재한다. 이 논문의 목표는 수십억개의 점으로 구성된 Point Cloud 데이터를 다른 어플리케이션 없이 실시간으로 볼 수 있도록 만드는 것이다.

1.2 Problem Definition 문제정의

레이저 스캐너 또는 사진측량법과 같은 3D 스캐닝 기술은 수억 또는 수십억개를 초과하는 점들을 추출해낸다. 포인트 데이터의 특성상 단순한 모델이라도 정확하게 표현하기 위해 많은 수의 포인트가 필요하다. 평평한 벽을 예로 들면 1개의 사각 단면 텍스쳐로 표현될 수 있지만 비슷한 디테일을 구현하기 위해 수천 또는 수백만개의 색칠된 점들이 필요할지도 모른다. 많은 사례로 cloud point 보다는 더 작은 triangle mesh를 사용한 것들이 있지만, 항상 대체될 수 있는 것은 아니다. 낮은 해상도의 triangle mesh는 적은 정보를 제공하기 떄문에, 복잡한 물체나 표면에 대한 낮은 스캔 밀도로 인해 변환이 불가능할 수 있으며, 매우 많은 시간과 비용이 소요될 수 있다. 가장 큰 문제는 데이터의 크기이며 이를 해결하기 위해 Out-of-core 알고리즘을 사용한다. Out-of-core 알고리즘은 큰 데이터를 작은 chunk로 나눠서 실행하고, 더이상 사용하지 않는 chunk는 메모리에서 삭제함으로써 다음 chunk가 실행될 수 있게 공간을 확보한다. (딥러닝에서는 이를 외부 메모리 학습이라고 한다) 이 논문에서 사용한 데이터는 약 27조개의 점으로 이뤄진 540 테라바이트 규모의 미국 전체를 스캐닝한 데이터를 사용하였으며, 최대한 많은 사람들이 웹으로 쉽게 접근할 수 있도록 하는 것이 목표이다. Scheiblauer에서 소개된 modifiable nested octree(MNO)의 구조를 기반으로 만들어졌으며, 이 구조는 시야 밖의 점을 도려낼 수 있고, 먼 지역을 낮은 수준으로 렌더링할 수 있다.

2.1 Rendering Massive Point Clouds

대용량의 Point Cloud를 랜더링하기 위해 kd-tree, octree 또는 quadtree와 같이 multiresolution structures로도 알려진 space-partitioning structures의 알고리즘을 사용해 다른 해상도에서 나타낸 기존 모델의 데이터를 사용해서 모든 노드를 채우는 방법을 주로 사용하였다. 알고리즘에 대한 자세한 내용은 여기를 참고하자.

위의 일부 알고리즘은 기존 Point Data를 계층 구조에 맞춰 재분배 하는 방법을 사용한 반면, 나머지들은 마지막 노드에 데이터를 저장하여 노드의 평균을 하향 샘플링하는 방법을 사용하였다.

QSplat의 랜더링 시스템은 수억개의 Point를 랜더링 가능하게한 최초의 시스템이다.

총정리

MNO 알고리즘을 사용했음, node 간의 간격은 boundingCubeWidth/128 로 잡았으며, Scanopy에서 사용하는 MNO 알고리즘과 동일함.

동일한 간격으로 점들과의 최소한의 거리를 유지 하도록 설계된 서브샘플링 알고리즘 Poisson-Disk Subampling 방법을 사용해서 샘플링 진행. 기존 MNO에서는 그리드를 사용해서 샘플링함. Poisson-Disk는 그리드 방식으로 샘플링된 패턴보다 시각적으로 더 좋은 결과물을 보여주고, 적은 수의 점으로 뛰어난 커버력을 보여준다.

Poisson-Disk 샘플은 dart throwing? 알고리즘을 통해 생성 할 수 있다.

1개 이상의 Point Cloud를 빌드업 하는 과정은 Octree를 통해 분할한 다음 결과값은 아래 순서대로 저장합니다.

  1. Octree로 리프 노드로 전달되는 점을 1개의 노드로 결합한다.
  2. 리프 노드에 점들이 하나씩 더해진다.
  3. 만약 최소의 거리를 가진 다른 점이 없을 경우 내부의 노드들은 점을 유지하고 그렇지 않을 경우 자식 노드에게 전달한다.
  4. 각 레벨에서 공간이 반으로 줄어든다.
  5. 리프 노드는 모든 점들을 처음으로 유지한다.
  6. 포인트의 특정 임계값에 도달하면 리프 노드가 확장된다. 내부 노드가 되어 저장된 모든 포인트를 자신에게 추가하지만, 이번에는 내부 노드 규칙을 따른다.최소 거리에 위치한 점은 리프 노드 전에 남아있으며 다른 점들은 새로 생성된 자식 노드에 전달된다.
  7. 데이터들은 정기적으로 디스크에 저장된다. 예를들면 한번에 천만개씩의 점을 처리했다.
  8. 만약 노드가 저장된 이후 영향을 받지않았다면, 다음 저장시점까지 해당 데이터는 메모리에서 삭제된다.
  9. 만일 포인트가 메모리에서 제거된 노드에 추가되려고 한다면, 데이터는 먼저 디스크에서 메모리로 다시 읽혀질 것이다.

3,4번 - 낮은 레벨에 있는 낮은 해상도에서 부터 높은 레벨에 높은 해상도까지 점차적으로 샘플링하는 과정을 보여준다. 낮은 레벨의 노드들은 넓은 간격을 유지하고 있다. 이 간격은 각 레벨이 올라가면서 쪼개지게 되며 해상도를 증가시킨다.

5,6번 - 필요시 octree hierarchy로 확장할 수 있도록 허용한다. hierarchy는 처음에는 얕고 점이 추가됨에 따라 깊이가 깊어진다. 내부 노드에 있는 점은 일정한 간격을 갖고 있다. 다른 한편으로 리프 노드는 남은 모든 점이 저장되는 버킷이다.

7번 - 유저들이 Potree에서 데이터를 저장한 다음, 변환이 끝나기 전에 바로 변화상태를 확인할 수 있게 해준다. 브라우저는 데이터를 캐시하는 경향이 있기 때문에 단순히 URL을 통해 재방문하는 대신 캐싱을 비활성화하거나 페이지를 새로 고칠 필요가 있을 수 있다. 그렇지 않으면 기존에 저장된 데이터가 보여질 수 있다.

8,9번 - 한동안 사용되지 않은 데이터를 지움으로써 메모리 사용량을 낮게 유지하는 것에 대해 설명한다. 이는 이후의 프로세싱될 점들이 특정한 지역성을 가질 경우 가장 잘 작동한다. 그것들은 상대적으로 가깝게 위치해 있기에 같은 octree 노드에 속해있다.

이슈

이 구현은 각 노드 내에 Poisson-Disk로 샘플링된 하위 노드들을 생성하지만, 결합된 노드에서는 그렇지 않다. 랜더링하는 동안, 여러 노드들이 결합되지만 인접 또는 교차 노드에 대해 Poisson-Disk가 실행되지 않았다.