[개념 정리] Poisson Surface Reconstruction (2006) : Point-to-Mesh

Poisson Surface Reconstruction, Michael Kazhdan, 2006 

 

3D Point Clouds를 3D Mesh로 바꾸는 고전적인 방법중에 하나인,  Poisson Surface Reconstruction 기법을 소개합니다.

논문에 언급된 가장 퀄리티가 좋은 결과입니다. 약 2억개의 points를 입력을 받아, 5.2GB RAM으로 (2006년 CPU기준) 1.9시간이면, 약1600만개정도 Triangle로 구성된 Mesh를 만들어 냅니다.

 

최신 논문을 읽다가 언급된 옛날 논문입니다. 때문에 어떤 내용인지 정도만 파악해보았습니다.

 

아래 강의 자료을 기반으로 작성하였습니다.

https://www.hao-li.com/cs599-ss2015/slides/Lecture06.2.pdf

 

 

 

해결하고자 하는 문제

Lidar센서 RGB-D센서로 물체에 신호를 보내서 돌아오는 시간정보로 Point마다 3D값을 획득하여 3D Point 집합인 Point Cloud를 만들 수 있습니다. SfM알고리즘 바탕으로 여러장의 RGB이미지로 Point Cloud를 획득 할수도 있습니다. 일반적으로 불규칙적(irregular)이고 듬성듬성(sparse)하게 획득하게 됩니다.

이 Point Cloud를 입력으로 Points를 Approximation하는 3D Mesh를 만들고자 합니다.

 

 

 

 

해결 방법

Object Mesh(M) 내부에 Point(p)가 있으면 1, 외부이면 0인 함수를 Indicator function으로 정의합니다.

입력 Point Cloud의 좌표들은 Object 표면에 수직인 방향(Oriented)을 가진 points의 형태가 되며, Point들로부터 Indicator Function를 만들고자 합니다.

스칼라 함수인 Indicator Function에 Gradient(▽)를 취하면 Vector함수가 되므로(참조: ▽ 설명), 이 Vector함수와 Oriented Points가 Relationship(관계성)을 갖게 된다는 점을 활용합니다. Oriented Points를 Approximation하는 Indicator Gradient를 찾는 문제가 됩니다.

 

이것을 풀기 위해, 2차 편미분 방정식 중에 하나인 Poisson Equation(푸아송 방정식)이 사용됩니다. 이해없이 Implementation단계 보셔도 됩니다. (출처 : link) 

위 공식을 통해, 함수 f가 주어지면 함수φ를 찾을 수 있습니다. 둘 다 Vector Field이므로, Divergence(▽)를 취할 수 있으며, 양변은 Scalar Field가 됩니다. (참조: ▽ 설명)

논문에서는 위 방정식을 풀면 Indicator function을 만들 수 있다라는 것을 수식적으로 증명 후에, 구현방법을 소개하고 있습니다.

 

 

 

 

Implementation

방향(Oriented)이 주어진 Point Cloud(왼쪽 이미지)가 주어지면, 모든 Point가 포함된 큰 육면체를 만들고, Octree를 사용해서 분할합니다. Octree는 3차원에서 6면체인 사각형을 8등분(x,y,z축으로 1/2지점 분할)하는 Tree입니다. Point가 있으면 8개의 자식 node로 분할하는 형태입니다. 실제 3차원이지만 아래 이미지는 2차원으로 간단하게 표현한 형태입니다.

입력 Point Cloud의 Point Vector V(하단 빨간색)을 주변 Octree들의 합이 되도록 설계합니다(하단 왼쪽 이미지). Octree Node의 Depth가 Gaussian의 variance로 설계(2^-Depth)하여, V가 있는 주변 Octree들을 Gaussian으로 표현하면 오른쪽 그림과 같아집니다. 이 과정을 Splatting이라고 표현하고 있습니다. (2006년에 나온 논문인데, 2023년에 각광받고 있는 Gaussian Splatting과 이름이 같네요)

 

다시 앞으로 돌아가서, 방향이 주어진 Point Cloud(위위이미지 왼쪽)는 Vector Field였습니다. 각 차원을 편미분(▽ : Divergence)하면 아래 그림과 같이 Scalar Field로 만들어집니다. 이는 빨간색으로 표시한 부분입니다. 

하늘색 박스는 Poisson Equation(푸아송 방정식)이며, 푸아송 방정식에 의해, 우항의 f가 주어지면 좌항의 φ을 계산 할 수 있다고 했습니다. 좌항의 φ는 Indicator Function X에 해당하며, 이를 다시 보면 아래 왼쪽이미지는 1과 0으로 구성된 Scalar함수인 X, 아래 오른쪽 이미지는 Vector함수인 ▽X이며, 목표로하는 ▽▽X는 Object내부일수록 큰값을 갖게되는 이미지가 되게 됩니다.

이를 모델링하기 위해 Octree 깊이 별로 각 Node마다 input point가 중심이 되는 가우시안을 그리도록 function space F。를 설계합니다.

이 부분부터는 정확히 이해가 되지 않는 부분인데, Octree의 깊이별로 각 Node의 ▽V값( =Scalar값 =위위그림)과 ▽▽X(=Scalar값=아래그림)의 차이를 최소화함으로써, Indicator Function X를 만들게됩니다. 

그럼 최종적으로 Indicator Function X는 아래 왼쪽이미지와 같이 만들어집니다. Indicator Function X는 Octree자료구조에서 각 node의 중심이 Gaussian의 중심이 되는 Gaussian의 집합으로 생성되어지는 것 처럼 보입니다.

그 후에 mesh화를 진행하는데, input point clouds의 point의 좌표값을 Indicator Function X의 입력으로 넣어서 나온 결과값들을 평균내고 이 값과 같은 값(=isovalue)을 출력하는 좌표들을 surface(=isosurface)로 간주(위 오른쪽 그림)합니다.

 

Octree에 Marching Cube알고리즘(이전글)을 사용해서 Mesh를 생성하게 됩니다. Octree의 Node마다 Marching Cube의 Polygon을 만들면 되는 것 처럼 보입니다. 이렇게 할 경우에 fine한 여러 node가 coarse한 node를 공유하게 될 때 문제가 되어 fine한 node의 면의 부분을 coarse한 면으로 projection하는 방법을 사용했다고 합니다.

 

 

 

 

Experiments

왼쪽은 octree의 깊이에 따른 결과입니다. 오른쪽은 다른 연구와 비교한 결과입니다.

다른 연구와 비교할 때 Octree의 depth는 9로 썼다고 합니다.

 

아래는 Tree의 깊이에 따른 연산시간(초)와 메모리 사용량(Mb), triangle mesh갯수입니다.

 

 

 

 

Closing..

매번 신뢰있는 정확한 글을 쓰려고 노력하지만, 이번 글은 참조 논문을 빠르게 이해하고 넘어가면서 정리한터라, 글의 정확도를 약간 보장하기 어렵습니다. (하지만 생각보다 많은 시간을 썼네요..) 어떤 논문인지 느낌 정도만 파악하시길 바라며, 위에 글에 많은 오류가 있다면 댓글 부탁드립니다.

 

 

참고한 자료

https://www.hao-li.com/cs599-ss2015/slides/Lecture06.2.pdf

https://3d.bk.tudelft.nl/courses/geo1016/slides/Lecture_07_SurfaceReconstruction.pdf

https://www.youtube.com/watch?v=PWlo7PvtQVw

https://www.slideserve.com/colton/fourier-based-and-poisson-surface-reconstruction