[3D CV] Poisson Surface Reconstruction
3D points๋ ๊ฐ 3D point๋ง๋ค normal์ด ์์ผ๋ฉด surface๋ฅผ ๋ง๋ค ์ ์๊ณ , ์ด๋ ์ฌ์ฉํ๋ ๊ฒ์ด poisson reconstruction์ ๋๋ค.
ํฌ์ธํธ(Points)๊ฐ ๋ฒ์ (normals)์ ๊ฐ์ง๊ณ ์์ผ๋ฉด ์ด๋ฅผ โoriented point setโ์ด๋ผ๊ณ ๋ถ๋ฆ ๋๋ค. โOrientedโ๋ผ๋ ์ฉ์ด๋ ๊ฐ ํฌ์ธํธ๊ฐ ํน์ ๋ฐฉํฅ์ผ๋ก ์ ๋ ฌ๋์ด ์๋ค๋ ์๋ฏธ๋ฅผ ๋ดํฌํ๋ฉฐ, ์ด ๋ฐฉํฅ ์ ๋ณด๋ ๋ฒ์ ๋ฒกํฐ๋ก ์ ๊ณต๋ฉ๋๋ค
Poisson surface reconstruction is more sensitive to estimated positions of the points than their normal estimates, thus further smoothing and regularizing the Gaussian scene representation would result in smoother reconstructions. DN-Splatter: Depth and Normal Priors for Gaussian Splatting and Meshing
Poisson Reconstruction ๋น ๋ฅธ ์ฌ์ฉ ๋ฐฉ๋ฒ
Poisson detph
Poisson ์ฌ๊ตฌ์ฑ์ ํฌ์ธํธ ํด๋ผ์ฐ๋(point cloud) ๋ฐ์ดํฐ๋ก๋ถํฐ ๋งค๋๋ฌ์ด ํ๋ฉด์ ์์ฑํ๋ ๋ฐฉ๋ฒ ์ค ํ๋์ ๋๋ค. ์ด ์๊ณ ๋ฆฌ์ฆ์ ํฌ์ธํธ ํด๋ผ์ฐ๋์์ ์ถ์ถํ normal ๋ฒกํฐ๋ฅผ ์ฌ์ฉํ์ฌ ์ต์ ์ ํ๋ฉด์ ๊ณ์ฐํฉ๋๋ค.
Poisson Depth = Depth of Octree
โpoisson_depthโ๋ ์ฅํธ๋ฆฌ์ ์ต๋ ๊น์ด๋ฅผ ์๋ฏธํฉ๋๋ค. ๊น์ด๊ฐ ๊น์์๋ก ๊ณต๊ฐ์ ๋ ์ธ๋ฐํ๊ฒ ๋ถํ ํ์ฌ ์์ ์ธ๋ถ ์ฌํญ๊น์ง ํํํ ์ ์์ต๋๋ค.
- ๋์ ๊น์ด: ๋ ์์ ์ ๋ก ๊ณต๊ฐ์ ๋ถํ ํ๋ฏ๋ก, ๋ ๋ง์ ์ธ๋ถ ์ฌํญ์ ์บก์ฒํ ์ ์์ง๋ง, ๋ ธ์ด์ฆ์ ์์ ๊ฒฐํจ๋ ๋ ๋ง์ด ๋ํ๋ ์ ์์ต๋๋ค.
- ๋ฎ์ ๊น์ด: ๋ ํฐ ์ ๋ก ๊ณต๊ฐ์ ๋ถํ ํ๋ฏ๋ก, ํฐ ๊ตฌ์กฐ๋ฅผ ๋งค๋๋ฝ๊ฒ ํํํ ์ ์์ง๋ง, ์์ ์ธ๋ถ ์ฌํญ์ ๋์น ์ ์์ต๋๋ค.
- Octree์ ๊น์ด๋ฅผ ์ฆ๊ฐ์ํค๋ฉด ๋ ๋์ ํด์๋์ ํจ์๋ฅผ ์ฌ์ฉํ์ฌ indicator function์ ๋ง์ถ ์ ์๊ฒ ๋์ด, ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด์ด ๋ ์ธ๋ฐํ ๋ํ ์ผ์ ํฌ์ฐฉํ ์ ์์ต๋๋ค.
Practical Usage of Poisson depth value
- ๊น์ด ๊ฐ์: ์ฅํธ๋ฆฌ ๊น์ด๋ฅผ ์ค์ด๋ฉด, ํ๋ฉด์ ๋ ์ธ๋ฐํ๊ฒ ๋ถํ ํ๊ฒ ๋์ด, ์์ ๊ฒฐํจ์ด ๋ ๋๋ฌ๋๊ฒ ๋ฉ๋๋ค.
- ๋ฉ์ฌ ํ๋ฉด์ ์ง์ ๋ถํ ํ์ํ ๋๊ธฐ๊ฐ ๋ํ๋๋ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ฅํธ๋ฆฌ ๊น์ด๋ฅผ ์ค์ด๋ ๊ฒ์ด ๊ถ์ฅ๋ฉ๋๋ค.
poisson_depth = 7
Poisson Surface Reconstruction
๋ง์ ์ด์ ์ฐ๊ตฌ๋ค์ฒ๋ผ, Poisson Surface Reconstruction์ ํ๋ฉด ์ฌ๊ตฌ์ฑ ๋ฌธ์ ์ ๋ํด implicit function ํ๋ ์์ํฌ๋ฅผ ์ฌ์ฉํ์ฌ ์ ๊ทผํฉ๋๋ค. ๊ตฌ์ฒด์ ์ผ๋ก, [Kaz05]์ ๊ฐ์ด, ์ฐ๋ฆฌ๋ 3D indicator function ฯ๋ฅผ ๊ณ์ฐํฉ๋๋ค (๋ชจ๋ธ ๋ด๋ถ์ ์ ์์๋ 1๋ก ์ ์๋๊ณ , ์ธ๋ถ์ ์ ์์๋ 0์ผ๋ก ์ ์๋ฉ๋๋ค). ๊ทธ๋ฐ ๋ค์ ์ ์ ํ isosurface๋ฅผ ์ถ์ถํ์ฌ ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด์ ์ป์ต๋๋ค. ์ฐ๋ฆฌ์ ์ฃผ์ ํต์ฐฐ๋ ฅ์ ๋ชจ๋ธ ํ๋ฉด์์ ์ํ๋ง๋ oriented points์ ๋ชจ๋ธ์ indicator function ์ฌ์ด์ ์ ๋ถ์ ๊ด๊ณ๊ฐ ์๋ค๋ ๊ฒ์ ๋๋ค. ๊ตฌ์ฒด์ ์ผ๋ก, indicator function์ gradient๋ ๊ฑฐ์ ๋ชจ๋ ๊ณณ์์ 0์ธ ๋ฒกํฐ ํ๋์ ๋๋ค(์ด๋ indicator function์ด ๊ฑฐ์ ๋ชจ๋ ๊ณณ์์ ์์์ด๊ธฐ ๋๋ฌธ์ ๋๋ค). ๊ทธ๋ฌ๋ ํ๋ฉด ๊ทผ์ฒ์ ์ ์์๋ gradient๊ฐ ๋ด๋ถ ํ๋ฉด normal๊ณผ ๊ฐ์ต๋๋ค. ๋ฐ๋ผ์ oriented point ์ํ์ ๋ชจ๋ธ์ indicator function gradient์ ์ํ๋ก ๋ณผ ์ ์์ต๋๋ค(๊ทธ๋ฆผ 1 ์ฐธ์กฐ).
- Poisson Surface Reconstruction: ๋ง์ ์ด์ ์ฐ๊ตฌ๋ค์ฒ๋ผ, Poisson Surface Reconstruction์ ํ๋ฉด ์ฌ๊ตฌ์ฑ ๋ฌธ์ ์ ๋ํด implicit function ํ๋ ์์ํฌ๋ฅผ ์ฌ์ฉํ์ฌ ์ ๊ทผํฉ๋๋ค.
- 3D Indicator Function ฯ:
- ๋ชจ๋ธ ๋ด๋ถ์ ์ ์์๋ 1๋ก ์ ์๋๊ณ , ์ธ๋ถ์ ์ ์์๋ 0์ผ๋ก ์ ์๋๋ 3D indicator function ฯ๋ฅผ ๊ณ์ฐํฉ๋๋ค.
- Isosurface ์ถ์ถ:
- ๊ณ์ฐ๋ indicator function์ ์ฌ์ฉํ์ฌ ์ ์ ํ isosurface๋ฅผ ์ถ์ถํจ์ผ๋ก์จ ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด์ ์ป์ต๋๋ค.
- ์ฃผ์ ํต์ฐฐ๋ ฅ:
- ๋ชจ๋ธ ํ๋ฉด์์ ์ํ๋ง๋ oriented points์ ๋ชจ๋ธ์ indicator function ์ฌ์ด์๋ ์ ๋ถ์ ๊ด๊ณ๊ฐ ์์ต๋๋ค.
- Gradient์ ํน์ฑ:
- Indicator function์ gradient๋ ๊ฑฐ์ ๋ชจ๋ ๊ณณ์์ 0์ธ ๋ฒกํฐ ํ๋์ ๋๋ค.
- ์ด๋ indicator function์ด ๋ชจ๋ธ ๋ด๋ถ์์๋ 1, ์ธ๋ถ์์๋ 0์ผ๋ก ์์์ด๊ธฐ ๋๋ฌธ์, ๊ทธ ์ ๋ค์์์ gradient๋ 0์ด ๋ฉ๋๋ค.
- ํ๋ฉด ๊ทผ์ฒ์ ์ ์์๋ indicator function์ด 0์์ 1๋ก ๊ธ๊ฒฉํ ๋ณํฉ๋๋ค. ์ด ๋ณํ๋ ํ๋ฉด normal ๋ฐฉํฅ์ผ๋ก ์ผ์ด๋๋ฏ๋ก, ์ด ์ง์ ์์์ gradient๋ ๋ด๋ถ ํ๋ฉด normal๊ณผ ๊ฐ์ต๋๋ค.
- ํ๋ฉด ๊ทผ์ฒ์ ์ ์์๋:
- ํ๋ฉด ๊ทผ์ฒ์ ์ ์์ indicator function์ gradient๊ฐ non-zero์ ๋๋ค. ์ด๋ ํ๋ฉด์์์ ๋ณํ(๊ฒฝ๊ณ ์กฐ๊ฑด) ๋๋ฌธ์ ๋๋ค. ์ด ๋ณํ๋ ํ๋ฉด normal ๋ฐฉํฅ์ผ๋ก ์ผ์ด๋๋ฏ๋ก, ์ด ์ง์ ์์์ gradient๋ ํ๋ฉด normal์ ๋ฐฉํฅ๊ณผ ํฌ๊ธฐ๋ฅผ ๋ฐ์ํฉ๋๋ค.
- Oriented Point ์ํ:
- Oriented point ์ํ์ ๋ชจ๋ธ์ ํ๋ฉด์์ ๊ฐ์ ธ์จ ์ ๋ค๊ณผ ๊ทธ ์ ๋ค์ ์์ง์ธ normal๋ค์ ํฌํจํฉ๋๋ค.
- ์ด ์ํ๋ค์ ๋ชจ๋ธ์ indicator function gradient์ ์ํ๋ก ๋ณผ ์ ์์ต๋๋ค. ์ด๋ ํ๋ฉด ๊ทผ์ฒ์ gradient๊ฐ ํ๋ฉด normal๊ณผ ์ผ์นํ๊ธฐ ๋๋ฌธ์ ๋๋ค.
- ๋ฐ๋ผ์, oriented points๋ ํ๋ฉด์ ๊ธฐํํ์ ํน์ฑ์ ์ ๋ฐ์ํ๋ฉฐ, ์ด๋ฅผ ํตํด ํ๋ฉด์ ์ฌ๊ตฌ์ฑํ ์ ์์ต๋๋ค.
โฆ
4.1. Problem Discretization
๋จผ์ , ๋ฌธ์ ๋ฅผ discretizeํ ํจ์ ๊ณต๊ฐ์ ์ ํํด์ผ ํฉ๋๋ค. ๊ฐ์ฅ ๋จ์ํ ์ ๊ทผ ๋ฐฉ์์ regular 3D grid๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ด์ง๋ง, ์ด๋ ๊ณ ํด์๋ ์ธ๋ถ ์ฌ๊ตฌ์ฑ์ ๋น์ค์ฉ์ ์ ๋๋ค. ํด์๋๊ฐ ๋์์ง์๋ก ๊ณต๊ฐ์ ์ฐจ์์ด ๊ธ๊ฒฉํ ์ฆ๊ฐํ์ฌ ๊ณ์ฐ ๋ณต์ก๋๊ฐ ์ปค์ง๊ธฐ ๋๋ฌธ์ ๋๋ค.
๋คํํ๋, implicit function์ ์ ํํ ํํ์ ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด ๊ทผ์ฒ์์๋ง ํ์ํฉ๋๋ค. ์ด๋ implicit function์ ํํํ๊ณ Poisson ์์คํ ์ ํด๊ฒฐํ๊ธฐ ์ํด adaptive octree๋ฅผ ์ฌ์ฉํ๋ ๋๊ธฐ๋ฅผ ์ ๊ณตํฉ๋๋ค. Poisson์์ Octree๋ฅผ ์ฌ์ฉํ๋ ์ด์ ๋ computational cost๋ฅผ ์ค์ด๊ธฐ ์ํด์์ ๋๋ค.
- Problem Discretization:
- ๋ฌธ์ ๋ฅผ discretizeํ ํจ์ ๊ณต๊ฐ ์ ํ์ด ํ์ํฉ๋๋ค.
- ๊ธฐ๋ณธ ์ ๊ทผ ๋ฐฉ์:
- Regular 3D grid๋ก ์์ํ๋ ๊ฒ์ด ๊ฐ์ฅ ๋จ์ํ ์ ๊ทผ ๋ฐฉ์์ ๋๋ค.
- ๊ท ์ผํ ๊ตฌ์กฐ์ ๋ฌธ์ ์ :
- ๊ท ์ผํ ๊ตฌ์กฐ๋ ๊ณ ํด์๋ ์ธ๋ถ ์ฌ๊ตฌ์ฑ์ ๋น์ค์ฉ์ ์ ๋๋ค.
- ํด์๋์ ๋ฐ๋ผ ๊ณต๊ฐ์ ์ฐจ์์ด ์ธ์ ๊ณฑ์ผ๋ก ์ฆ๊ฐํฉ๋๋ค.
- surface triangle์ ์๋ ์ด์ฐจ์ ์ผ๋ก ์ฆ๊ฐํฉ๋๋ค.
- Implicit Function์ ์ ํํ ํํ:
- Implicit function์ ์ ํํ ํํ์ ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด ๊ทผ์ฒ์์๋ง ํ์ํฉ๋๋ค.
- Adaptive Octree ์ฌ์ฉ ๋๊ธฐ:
- Implicit function์ ํํํ๊ณ Poisson ์์คํ ์ ํด๊ฒฐํ๊ธฐ ์ํด adaptive octree๋ฅผ ์ฌ์ฉํฉ๋๋ค.
- Poisson์์ Octree๋ฅผ ์ฌ์ฉํ๋ ์ด์ ๋ computational cost๋ฅผ ์ค์ด๊ธฐ ์ํด์์ ๋๋ค.
4.4. Isosurface Extraction
Poisson reconstruction์์๋ implicit function์ ์ฌ์ฉํ์ฌ ํ๋ฉด์ ์ฌ๊ตฌ์ฑํ๊ณ , isosurface extraction์ ํตํด ์ต์ข ํ๋ฉด์ ์ป์ต๋๋ค. ์ด๋ level set ๋ฐฉ๋ฒ์ ๊ฐ๋ ๊ณผ ์ ์ฌํ์ง๋ง, Poisson reconstruction ์์ฒด๋ ํน์ ํ ๋ฐฉ๋ฒ๋ก ์ด๊ณ , isosurface extraction์ ์ด ๋ฐฉ๋ฒ๋ก ์ ํ ๋ถ๋ถ์ ๋๋ค.
- Implicit Function:
- Poisson reconstruction์ ๊ธฐ๋ณธ ๊ฐ๋ ์ implicit function์ ์ฌ์ฉํ๋ ๊ฒ์ ๋๋ค. ์ด ํจ์๋ ์ฃผ๋ก indicator function์ผ๋ก ์ ์๋ฉ๋๋ค.
- Indicator Function:
- Indicator function์ ๋ชจ๋ธ์ ๋ด๋ถ์ ์ธ๋ถ๋ฅผ ๊ตฌ๋ถํฉ๋๋ค. ๋ชจ๋ธ ๋ด๋ถ์ ์ ์์๋ 1๋ก ์ ์๋๊ณ , ์ธ๋ถ์ ์ ์์๋ 0์ผ๋ก ์ ์๋ฉ๋๋ค.
- Poisson Reconstruction:
- Implicit function์ ๊ณ์ฐํ๋ ๋ฐฉ๋ฒ๋ก ์ผ๋ก, ์ฃผ์ด์ง ๋ฐ์ดํฐ์์ ํ๋ฉด์ ์ฌ๊ตฌ์ฑํฉ๋๋ค.
- ๊ณ์ฐ๋ implicit function์ผ๋ก๋ถํฐ ์ ์ ํ isovalue๋ฅผ ์ ํํฉ๋๋ค.
- Isovalue:
- Isovalue๋ isosurface๋ฅผ ์ถ์ถํ๊ธฐ ์ํด ์ ํ๋๋ ๊ฐ์ ๋๋ค. ์ด ๊ฐ์ ์ฃผ๋ก ์ ๋ ฅ ์ํ์ ์์น๋ฅผ ๊ฐ๊น๊ฒ ๊ทผ์ฌํ๋๋ก ์ ํ๋ฉ๋๋ค.
- Isosurface Extraction:
- Poisson reconstruction์์ ๊ณ์ฐ๋ implicit function๊ณผ ์ ํ๋ isovalue๋ฅผ ์ฌ์ฉํ์ฌ isosurface๋ฅผ ์ถ์ถํ๋ ๋จ๊ณ์ ๋๋ค.
- ์ถ์ถ๋ isosurface๋ ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด์ ๋ํ๋ ๋๋ค.
- Level Set ๋ฐฉ๋ฒ:
- Level set ๋ฐฉ๋ฒ์ implicit function์ ์ฌ์ฉํ์ฌ ํ๋ฉด์ ์ถ์ ํ๋ ๋ฐฉ๋ฒ๋ก ์ ๋๋ค.
- Poisson reconstruction์์ ์ฌ์ฉ๋ ์ ์์ผ๋ฉฐ, isosurface extraction๊ณผ ๊ฐ๋ ์ ์ผ๋ก ์ ์ฌํฉ๋๋ค.
Poisson Reconstruction, Level Set ๋ฐฉ๋ฒ ๋ฐ Isosurface Extraction์ ๊ด๋ จ์ฑ
- Poisson Reconstruction:
- Implicit function์ ์ฌ์ฉํ์ฌ ํ๋ฉด์ ์ฌ๊ตฌ์ฑํ๋ ํฌ๊ด์ ์ธ ๋ฐฉ๋ฒ๋ก ์ ๋๋ค.
- ๊ณ์ฐ๋ implicit function์ผ๋ก๋ถํฐ isosurface๋ฅผ ์ถ์ถํ์ฌ ์ต์ข ํ๋ฉด์ ์ป์ต๋๋ค.
- Level Set ๋ฐฉ๋ฒ:
- Implicit function์ ์ฌ์ฉํ๋ ๋ฐฉ๋ฒ๋ก ์ค ํ๋๋ก, Poisson reconstruction์ ์ผ๋ถ๋ก ๊ฐ์ฃผ๋ ์ ์์ต๋๋ค.
- Isosurface extraction๊ณผ ์ ์ฌํ๊ฒ implicit function์ ํน์ ๊ฐ์ ๊ธฐ์ค์ผ๋ก ํ๋ฉด์ ์ถ์ถํ๋ ๊ณผ์ ์ ๋๋ค.
- Isosurface Extraction:
- Poisson reconstruction์ ํ ๋จ๊ณ๋ก, ๊ณ์ฐ๋ implicit function์์ isosurface๋ฅผ ์ถ์ถํฉ๋๋ค.
- Level set ๋ฐฉ๋ฒ๊ณผ ์ ์ฌํ๊ฒ, isosurface extraction์ implicit function์ ํน์ ๊ฐ์ ๊ธฐ์ค์ผ๋ก ํ๋ฉด์ ์ ์ํฉ๋๋ค.
๋ฐ๋ผ์, Poisson reconstruction์์ isosurface extraction๊ณผ level set ๋ฐฉ๋ฒ์ ๋์ผํ ์๋ฆฌ๋ฅผ ๊ณต์ ํฉ๋๋ค. ๋ ๋ฐฉ๋ฒ ๋ชจ๋ implicit function์ ์ฌ์ฉํ์ฌ ํ๋ฉด์ ์ ์ํ๊ณ , ์ด๋ฅผ ํตํด ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด์ ์ป๋ ๊ณผ์ ์ ๋๋ค.
โฆ
5.1. Resolution
์ต๋ octree ๊น์ด๊ฐ ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด์ ๋ฏธ์น๋ ์ํฅ์ ๊ณ ๋ คํด๋ด ์๋ค.
- Resolution:
- ์ต๋ octree ๊น์ด๊ฐ ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด์ ๋ฏธ์น๋ ์ํฅ์ ๊ณ ๋ คํฉ๋๋ค.
- Octree ๊น์ด 6, 8, 10์์ โdragonโ ๋ชจ๋ธ์ ์ฌ๊ตฌ์ฑ ๊ฒฐ๊ณผ๋ฅผ ๋ณด์ฌ์ค๋๋ค.
- ์ ๊ท ๊ทธ๋ฆฌ๋์์ ์ด๋ ๊ฐ๊ฐ 64ยณ, 256ยณ, 1024ยณ ํด์๋์ ํด๋นํฉ๋๋ค.
- ํธ๋ฆฌ ๊น์ด ์ฆ๊ฐ์ ํจ๊ณผ:
- ํธ๋ฆฌ ๊น์ด๊ฐ ์ฆ๊ฐํจ์ ๋ฐ๋ผ ๋ ๋์ ํด์๋์ ํจ์๊ฐ indicator function์ ๋ง์ถ๋ ๋ฐ ์ฌ์ฉ๋ฉ๋๋ค.
- ๊ทธ ๊ฒฐ๊ณผ, ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด์ด ๋ ์ธ๋ฐํ ๋ํ ์ผ์ ํฌ์ฐฉํฉ๋๋ค.
- ์ธ๋ฐํ ๋ํ
์ผ ํฌ์ฐฉ ์์:
- ๊ฐ์ฅ ๋ฎ์ ํด์๋์์๋ ํฌ์ฐฉํ๊ธฐ ์ด๋ ค์ด ์ฉ์ ๋น๋์ด ํธ๋ฆฌ ๊น์ด๊ฐ ์ฆ๊ฐํจ์ ๋ฐ๋ผ ๋ํ๋๊ธฐ ์์ํฉ๋๋ค.
- ๋ ๋์ ํด์๋์์๋ ์ฉ์ ๋น๋์ด ๋ ์ ๋ช ํ๊ฒ ํํ๋ฉ๋๋ค.
์ฆ, octree์ ๊น์ด๋ฅผ ์ฆ๊ฐ์ํค๋ฉด ๋ ๋์ ํด์๋์ ํจ์๋ฅผ ์ฌ์ฉํ์ฌ indicator function์ ๋ง์ถ ์ ์๊ฒ ๋์ด, ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด์ด ๋ ์ธ๋ฐํ ๋ํ ์ผ์ ํฌ์ฐฉํ ์ ์์ต๋๋ค.
Poisson Surface Reconstruction User Guide
3 Poisson
Poisson Surface Reconstruction ๋ฐฉ๋ฒ์ 3D ์ ๊ณผ ๊ทธ์ ๋ํ ๋ ธ๋ง ์ ๋ณด๋ฅผ ํ์ฉํ์ฌ ์ถ๋ก ๋ ๊ณ ์ฒด์ ํ๋ฉด์ ์ ํํ๊ฒ ์ฌ๊ตฌ์ฑํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. ์ด ์๊ณ ๋ฆฌ์ฆ์ ์ฃผ์ด์ง ๋ ธ๋ง ๋ฒกํฐ์ ์ ๋ง๋ gradient๋ฅผ ๊ฐ์ง indicator function์ ๊ณ์ฐํจ์ผ๋ก์จ ํ๋ฉด์ ํํ๋ฅผ ์ถ์ ํฉ๋๋ค.
Given a set of 3D points with oriented normals (denoted oriented points in the sequel) sampled on the boundary of a 3D solid, the Poisson Surface Reconstruction method [2] solves for an approximate indicator function of the inferred solid, whose gradient best matches the input normals. The output scalar function, represented in an adaptive octree, is then iso-contoured using an adaptive marching cubes.
CGAL implements a variant of this algorithm which solves for a piecewise linear function on a 3D Delaunay triangulation instead of an adaptive octree. The algorithm takes as input a set of 3D oriented points. It builds a 3D Delaunay triangulation from these points and refines it by Delaunay refinement so as to remove all badly shaped (non-isotropic) tetrahedra and to tessellate a loose bounding box of the input oriented points. The normal of each Steiner point added during refinement is set to zero. It then solves for a scalar indicator function $f$ represented as a piecewise linear function over the refined triangulation. More specifically, it solves for the Poisson equation
\[\Delta f = \text{div}(n)\]at each vertex of the triangulation using a sparse linear solver. Eventually, the CGAL surface mesh generator extracts an isosurface with function value set by default to be the median value of $f$ at all input points.
4 Reconstruction Function
A global function poisson_surface_reconstruction_delaunay() is provided. It takes points with normals as input and handles the whole reconstruction pipeline :
- it computes the implicit function
- it reconstructs the surface with a given precision using the CGAL surface mesh generator based on Delaunay refinement [4] [1]
- it outputs the result in a polygon mesh.
This function aims at providing a quick and user-friendly API for Poisson reconstruction. Advanced users may be interested in using the class (see Reconstruction Class) which allows them, for example, to use another surface mesher or a different output structure.
โฆ
6 Case Studies
The surface reconstruction problem being inherently ill-posed, the proposed algorithm does not pretend to reconstruct all kinds of surfaces with arbitrary sampling conditions. This section provides the user with some hints about the ideal sampling and contouring conditions, and depicts some failure cases when these conditions are not matched.
6.1 Ideal Conditions
The user must keep in mind that the Poisson surface reconstruction algorithm comprises two phases (computing the implicit function from the input point set and contouring an iso-surface of this function). Both require some care in terms of sampling conditions and parameter tuning.
6.2 Point Set
Ideally the current implementation of the Poisson surface reconstruction method expects a dense 3D oriented point set (typically matching the epsilon-sampling condition [1]) and sampled over a closed, smooth surface. Oriented herein means that all 3D points must come with consistently oriented normals to the inferred surface. Figure 63.3 and Figure 63.4 illustrate cases where these ideal conditions are met.
Figure 63.3 Poisson reconstruction. Left: 120K points sampled on a statue (Minolta laser scanner). Right: reconstructed surface mesh.
Figure 63.4 Left: 120K points sampled on a statue (Minolta laser scanner). Right: reconstructed surface mesh.
The algorithm is fairly robust to anisotropic sampling and to noise. It is also robust to missing data through filling the corresponding holes as the algorithm is designed to reconstruct the indicator function of an inferred solid (see Figure 63.5).
Figure 63.5 Top left: 65K points sampled on a hand (Kreon laser scanner). Bottom left: the point set is highly anisotropic due to the scanning technology. Right: reconstructed surface mesh and closeup. The holes are properly closed.
The algorithm is in general not robust to outliers, although a few outliers do not always create a failure, see Figure 63.6.
Figure 63.6 Left: 70K points sampled on an elephant with few outliers emphasized with disks. Right: reconstructed surface mesh.
The algorithm works well even when the inferred surface is composed of several connected components, provided that both all normals are properly estimated and oriented (the current CGAL normal orienter algorithm may fail in some cases, see mst_orient_normals()), and that the final contouring algorithm is properly seeded for each component. When the inferred surface is composed of several nested connected components care should be taken to orient the normals of each component in alternation (inward/outward) so that the final contouring stage picks a proper contouring value.
6.3 Contouring Parameters
Our implementation of the Poisson surface reconstruction algorithm computes an implicit function represented as a piecewise linear function over the tetrahedra of a 3D Delaunay triangulation constructed from the input points then refined through Delaunay refinement. For this reason, any iso-surface is also piecewise linear and hence may contain sharp creases. As the contouring algorithm make_surface_mesh() expects a smooth implicit function these sharp creases may create spurious clusters of vertices in the final reconstructed surface mesh when setting a small mesh sizing or surface approximation error parameter (see Figure 63.7).
One way to avoid these spurious clusters consists of adjusting the mesh sizing and surface approximation parameters large enough compared to the average sampling density (obtained through compute_average_spacing()) so that the contouring algorithm perceives a smooth iso-surface. We recommend to use the following contouring parameters:
- Max triangle radius: at least 100 times the average spacing.
- Approximation distance: at least 0.25 times the average spacing.
6.3 ํ๊ตญ์ด ํด์
Poisson ํ๋ฉด ์ฌ๊ตฌ์ฑ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ ๋๋ ํ๋ฉด์ ๋ถ๋๋ฌ์์ ์ ์งํ๊ณ ๋ฉ์ฌ์ ํ์ง์ ๋ณด์ฅํ๊ธฐ ์ํด ํ๋ผ๋ฏธํฐ ์ค์ ์ ์ฃผ์ํด์ผ ํฉ๋๋ค.
- Implicit Function์ ํน์ฑ: Poisson ํ๋ฉด ์ฌ๊ตฌ์ฑ ์๊ณ ๋ฆฌ์ฆ์ 3D Delaunay triangulation์ tetrahedra ์์ piecewise linear function์ผ๋ก ํํ๋ implicit function์ ๊ณ์ฐํฉ๋๋ค. ์ด๋ฌํ ํน์ฑ ๋๋ฌธ์ ๋ชจ๋ iso-surface๋ piecewise linear์ด๋ฉฐ, ๋ฐ๋ผ์ ๋ ์นด๋ก์ด ์ฃผ๋ฆ์ ํฌํจํ ์ ์์ต๋๋ค. ์ด๋ก ์ธํด ํ๋ฉด์ด ๋งค๋๋ฝ์ง ์๊ฒ ๋ณด์ผ ์ ์์ต๋๋ค.
- Contouring ์๊ณ ๋ฆฌ์ฆ์ ๊ธฐ๋: Contouring ์๊ณ ๋ฆฌ์ฆ์ธ make_surface_mesh()๋ ๋ถ๋๋ฌ์ด implicit function์ ๊ธฐ๋ํฉ๋๋ค. ๊ทธ๋ฌ๋ ์ ๋ ฅ๋ iso-surface๊ฐ ๋ ์นด๋ก์ด ์ฃผ๋ฆ์ ํฌํจํ๊ณ ์์ ๊ฒฝ์ฐ, contouring ์๊ณ ๋ฆฌ์ฆ์ ์ด๋ฅผ ์ ๋๋ก ์ฒ๋ฆฌํ์ง ๋ชปํด ์ต์ข ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด ๋ฉ์ฌ์ spuriousํ ํด๋ฌ์คํฐ๊ฐ ์์ฑ๋ ์ ์์ต๋๋ค. ์ด๋ ํนํ ์์ mesh ํฌ๊ธฐ ๋๋ ํ๋ฉด ๊ทผ์ฌ ์ค๋ฅ ํ๋ผ๋ฏธํฐ๋ฅผ ์ฌ์ฉํ ๋ ๋ฐ์ํ ๊ฐ๋ฅ์ฑ์ด ๋์ต๋๋ค.
- ํ๋ผ๋ฏธํฐ ์ค์ ์ ์ค์์ฑ: ์ด๋ฌํ ๋ฌธ์ ๋ฅผ ํผํ๊ธฐ ์ํด์๋ ํ๋ผ๋ฏธํฐ ์ค์ ์ ์ฃผ์ํด์ผ ํฉ๋๋ค. ํ๋ผ๋ฏธํฐ๋ฅผ ์ ์ ํ ์ค์ ํ๋ฉด contouring ์๊ณ ๋ฆฌ์ฆ์ด ๋ถ๋๋ฌ์ด iso-surface๋ฅผ ์ธ์ํ ์ ์๊ฒ ๋์ด, ๊ฒฐ๊ณผ์ ์ผ๋ก ๋ถ๋๋ฌ์ด ํ๋ฉด๊ณผ ๋์ ํ์ง์ mesh๋ฅผ ์ป์ ์ ์์ต๋๋ค. ์๋ฅผ ๋ค์ด, Max triangle radius์ Approximation distance๋ฅผ ํ๊ท ์ํ๋ง ๋ฐ๋์ ๋นํด ์ถฉ๋ถํ ํฌ๊ฒ ์ค์ ํจ์ผ๋ก์จ, contouring ์๊ณ ๋ฆฌ์ฆ์ด ๋ถ๋๋ฌ์ด iso-surface๋ฅผ ์ธ์ํ ์ ์์ต๋๋ค.
Figure 63.7 Left: surface reconstructed with approximation distance = 0.25 * average spacing. Right: surface reconstructed with approximation distance = 0.15 * average spacing. Notice the spurious cluster on the cheek.
6.4 Degraded Conditions
The conditions listed above are rather restrictive and in practice not all of them are met in the applications. We now illustrates the behavior of the algorithm when the conditions are not met in terms of sampling, wrongly oriented normals, noise and sharp creases.
6.5 Sparse Sampling
The reconstruction algorithm expects a sufficiently dense point set. Although there is no formal proof of correctness of the algorithm under certain density conditions due to its variational nature, our experiments show that the algorithm reconstructs well all thin features when the local spacing is at most one tenth of the local feature size (the distance to the medial axis, which captures altogether curvature, thickness and separation). When this condition is not met the reconstruction does not reconstruct the thin undersampled features (see Figure 63.8).
Figure 63.8 Left: 50K points sampled on the Neptune trident. The reconstruction (not shown) is successful in this case. Right: point set simplified to 1K points then reconstructed (all input points are depicted with normals). The thin feature is not reconstructed.
6.6 Large Holes
The reconstruction is devised to solve for an implicit function which is an approximate indicator function of an inferred solid. For this reason the contouring algorithm always extracts a closed surface mesh and hence is able to fill the small holes where data are missing due, e.g., to occlusions during acquisition (see Figure 63.9).
6.6 ํ๊ตญ์ด ํด์
Poisson reconstruction์ ์ถ๋ก ๋ solid์ ๊ทผ์ฌ indicator function์ธ implicit function์ ํ๊ธฐ ์ํด ๊ณ ์๋์์ต๋๋ค. ์ด๋ฌํ ์ด์ ๋ก, contouring ์๊ณ ๋ฆฌ์ฆ์ ํญ์ closed surface mesh๋ฅผ ์ถ์ถํ์ฌ, ์๋ฅผ ๋ค์ด ๋ฐ์ดํฐ ์ทจ๋ ์ค occlusions๋ก ์ธํด ๋ฐ์ํ ์์ ๊ตฌ๋ฉ์ ๋ฉ์ธ ์ ์์ต๋๋ค (๊ทธ๋ฆผ 63.9 ์ฐธ์กฐ).
- Implicit function ๊ณ์ฐ: Poisson reconstruction์ ์ถ๋ก ๋ solid์ ๊ทผ์ฌ indicator function์ธ implicit function์ ๊ณ์ฐํฉ๋๋ค. ์ด๋ ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด์ด ๊ณ ์ฒด์ ๊ตฌ์กฐ๋ฅผ ์ ๋ฐ์ํ๋๋ก ํฉ๋๋ค.
- Closed surface mesh ์ถ์ถ: Contouring ์๊ณ ๋ฆฌ์ฆ์ ํญ์ closed surface mesh๋ฅผ ์ถ์ถํฉ๋๋ค. Closed surface mesh๋ ๋ชจ๋ ๊ตฌ๋ฉ์ด ๋ฉ์์ง ์์ ํ ํ๋ฉด์ ์๋ฏธํฉ๋๋ค.
- ์์ ๊ตฌ๋ฉ ๋ฉ์ฐ๊ธฐ: Closed surface mesh๋ฅผ ์์ฑํจ์ผ๋ก์จ, ๋ฐ์ดํฐ ์ทจ๋ ์ค ๋ฐ์ํ ์์ ๊ตฌ๋ฉ์ ๋ฉ์ธ ์ ์์ต๋๋ค. ์๋ฅผ ๋ค์ด, ๋ฐ์ดํฐ ์ทจ๋ ์ occlusions๋ก ์ธํด ๋ฐ์ดํฐ๊ฐ ๋๋ฝ๋ ๋ถ๋ถ์ ์ฑ์ธ ์ ์์ต๋๋ค.
- ๊ฒฐ๋ก ์ ์ผ๋ก, Poisson reconstruction ์๊ณ ๋ฆฌ์ฆ์ ๋ฐ์ดํฐ ์ทจ๋ ๊ณผ์ ์์ ๋ฐ์ํ ์ ์๋ ๊ฒฐํจ์ ๋ณด์ํ์ฌ ๋ณด๋ค ์์ ํ๊ณ ์ ๋ขฐํ ์ ์๋ ํ๋ฉด ์ฌ๊ตฌ์ฑ์ ์ ๊ณตํฉ๋๋ค.
Figure 63.9 Left: 65K points sampled on a hand with no data captured at the wrist base. Right: reconstructed surface mesh. The surface is properly closed on the fingers and also closed at the wrist but in a less plausible manner.
In case of large holes the algorithm still closes them all but the resulting piecewise linear implicit function may exhibit large triangle patches and sharp creases as the 3D Delaunay triangulation used for solving is very coarse where the holes are filled. This can be avoided by a two pass approach. The first pass for a subset of the points serves to get an approximation of the surface at the holes. This surface then serves to compute a smoother 3D Delaunay triangulation for the second pass with the full set of points.
Figure 63.10 Left: The wrist. Middle: one pass. Right: two passes.
6.7 Wrongly Oriented Normals
The Poisson surface reconstruction approaches solves for an implicit function whose gradient best matches a set of input normals. Because it solves this problem in the least squares sense, it is robust to few isolated wrongly oriented (flipped) normals. Nevertheless a cluster of wrongly oriented normals leads to an incorrect implicit function and hence to spurious geometric or even topological distortion (see Figure 63.11).
6.7 ํ๊ตญ์ด ํด์
Poisson surface reconstruction ๋ฐฉ๋ฒ์ ์ ๋ ฅ๋ normal ์ธํธ์ ๊ฐ์ฅ ์ ๋ง๋ gradient๋ฅผ ๊ฐ์ง๋ implicit function์ ํ๋๋ค. ์ด ๋ฌธ์ ๋ฅผ ์ต์ ์ ๊ณฑ ๋ฐฉ์์ผ๋ก ํ๊ธฐ ๋๋ฌธ์, ์ผ๋ถ ๊ณ ๋ฆฝ๋ ์๋ชป๋ ๋ฐฉํฅ(๋ค์งํ) normals์ ๋ํด์๋ ๊ฒฌ๊ณ ํฉ๋๋ค. ๊ทธ๋ฌ๋ ์๋ชป๋ ๋ฐฉํฅ์ normals๊ฐ ํด๋ฌ์คํฐ๋ก ์กด์ฌํ ๊ฒฝ์ฐ, ์๋ชป๋ implicit function์ด ์์ฑ๋์ด ๊ธฐํํ์ ์๊ณก์ด๋ ์ฌ์ง์ด ์์์ ์๊ณก์ด ๋ฐ์ํ ์ ์์ต๋๋ค (๊ทธ๋ฆผ 63.11 ์ฐธ์กฐ).
- Implicit function ๊ณ์ฐ: Poisson surface reconstruction ๋ฐฉ๋ฒ์ a set of input normals๊ณผ ๊ฐ์ฅ ์ ์ผ์นํ๋ gradient๋ฅผ ๊ฐ์ง๋ implicit function์ ๊ณ์ฐํฉ๋๋ค. ์ด๋ ํ๋ฉด์ ๋ชจ์์ ์ ๋ฐ์ํ๋๋ก ํฉ๋๋ค.
- ์ต์ ์ ๊ณฑ ๋ฐฉ์์ ์ฅ์ : ์ด ์๊ณ ๋ฆฌ์ฆ์ ์ต์ ์ ๊ณฑ ๋ฐฉ์์ ์ฌ์ฉํ๊ธฐ ๋๋ฌธ์, ์ผ๋ถ ๊ณ ๋ฆฝ๋ ์๋ชป๋ ๋ฐฉํฅ์ normals์ ๋ํด์๋ ๊ฒฌ๊ณ ํฉ๋๋ค. ์ฆ, ๋ช ๊ฐ์ ์๋ชป๋ normals๊ฐ ์์ด๋ ์ ์ฒด ๊ฒฐ๊ณผ์ ํฐ ์ํฅ์ ๋ฏธ์น์ง ์์ต๋๋ค.
- ํด๋ฌ์คํฐ๋ก ์กด์ฌํ๋ ์๋ชป๋ ๋ฐฉํฅ์ normals์ ๋ฌธ์ ์ : ๊ทธ๋ฌ๋ ์๋ชป๋ ๋ฐฉํฅ์ normals๊ฐ ํด๋ฌ์คํฐ๋ก ์กด์ฌํ๋ฉด ๋ฌธ์ ๊ฐ ๋ฐ์ํฉ๋๋ค. ์ด๋ฌํ ํด๋ฌ์คํฐ๋ ์๋ชป๋ implicit function์ ์์ฑํ๊ฒ ๋์ด, ๊ฒฐ๊ณผ์ ์ผ๋ก ๊ธฐํํ์ ์๊ณก์ด๋ ์์์ ์๊ณก์ ์ด๋ํ ์ ์์ต๋๋ค. ์ด๋ ์ฌ๊ตฌ์ฑ๋ ํ๋ฉด์ด ์ค์ ํ๋ฉด๊ณผ ํฌ๊ฒ ๋ค๋ฅผ ์ ์์์ ์๋ฏธํฉ๋๋ค.
- ๊ฒฐ๋ก ์ ์ผ๋ก, Poisson surface reconstruction ์๊ณ ๋ฆฌ์ฆ์ ์ผ๋ถ ๊ณ ๋ฆฝ๋ ์๋ชป๋ normals์ ๋ํด ๊ฒฌ๊ณ ํ์ง๋ง, ํด๋ฌ์คํฐ ํํ์ ์๋ชป๋ normals์ ๋ํด์๋ ์ทจ์ฝํฉ๋๋ค.
Figure 63.11 Left: points sampled on a sphere with a cluster of wrongly oriented normals. Right: reconstructed surface mesh with a spurious bump.
6.8 Noise and Outliers
A large amount of noise inevitably impacts on the reconstruction (see Figure 63.12, top) and the current implementation does not provide any mean to trade data fitting for smoothness. Nevertheless if the signal-to-noise ratio is sufficiently high and/or the surface approximation and sizing parameters set for contouring the iso-surface is large with respect to the noise level the output surface mesh will appear smooth (not shown). If the user wants to produce a smooth and detailed output surface mesh, we recommend to apply smoothing through jet_smooth_point_set() (see Figure 63.12, bottom).
Figure 63.12 Top-left: points sampled on a sphere and corrupted with a lot of noise. Top-right: reconstructed surface mesh. Bottom-left: smoothed point set. Bottom-right: reconstructed surface mesh.
6.9 Sharp Creases
The current reconstruction algorithm is not able to recover the sharp creases and corners present in the inferred surface. This translates into smoothed sharp creases.
6.9 ํ๊ตญ์ด ํด์
ํ์ฌ์ Poisson Reconsrcution ์๊ณ ๋ฆฌ์ฆ์ ์ถ๋ก ๋ ํ๋ฉด์ ์กด์ฌํ๋ sharp creases(์ฃผ๋ฆ)์ corners(๋ชจ์๋ฆฌ)๋ฅผ ๋ณต์ํ ์ ์์ต๋๋ค. ์ด๋ ๊ฒฐ๊ณผ์ ์ผ๋ก ๋งค๋๋ฝ๊ฒ ์ฒ๋ฆฌ๋ sharp creases(์ฃผ๋ฆ)๋ก ๋ํ๋ฉ๋๋ค.
- Sharp creases(์ฃผ๋ฆ)์ corners(๋ชจ์๋ฆฌ)์ ๋ณต์ ๋ถ๊ฐ๋ฅ: ํ์ฌ ์ฌ์ฉ ์ค์ธ ์ฌ๊ตฌ์ฑ ์๊ณ ๋ฆฌ์ฆ์ ์ถ๋ก ๋ ํ๋ฉด์ ์กด์ฌํ๋ sharp creases(์ฃผ๋ฆ)์ corners(๋ชจ์๋ฆฌ)๋ฅผ ์ ํํ๊ฒ ๋ณต์ํ ์ ์์ต๋๋ค. ์ด๋ ์๊ณ ๋ฆฌ์ฆ์ด ๋ ์นด๋ก์ด ๋ชจ์๋ฆฌ๋ ์ฃผ๋ฆ์ ์ธ์ํ๊ณ ์ด๋ฅผ ๊ทธ๋๋ก ์ ์งํ๋ ๋ฐ ์ด๋ ค์์ ๊ฒช๋๋ค๋ ๊ฒ์ ์๋ฏธํฉ๋๋ค.
- ๋งค๋๋ฝ๊ฒ ์ฒ๋ฆฌ๋ sharp creases(์ฃผ๋ฆ): ์ด๋ฌํ ํ๊ณ๋ก ์ธํด, sharp creases(์ฃผ๋ฆ)๋ ๋งค๋๋ฝ๊ฒ ์ฒ๋ฆฌ๋์ด ๋ ์นด๋ก์ด ๋ชจ์์ด ์ฌ๋ผ์ง๊ณ ๋ฅ๊ทผ ํํ๋ก ๋ณํ๋ฉ๋๋ค. ์ด๋ ๋ณต์๋ ํ๋ฉด์ด ์๋์ ๋ ์นด๋ก์ด ํน์ง์ ์๊ฒ ๋ง๋๋ ๊ฒฐ๊ณผ๋ฅผ ์ด๋ํฉ๋๋ค.
- ๊ฒฐ๋ก ์ ์ผ๋ก, ํ์ฌ์ Poisson reconstruction ์๊ณ ๋ฆฌ์ฆ์ ๋ ์นด๋ก์ด ์ฃผ๋ฆ๊ณผ ๋ชจ์๋ฆฌ๋ฅผ ์ ํํ ๋ณต์ํ์ง ๋ชปํด, ๊ฒฐ๊ณผ ํ๋ฉด์ด ๋ถ๋๋ฝ๊ฒ ์ฒ๋ฆฌ๋๋ ํ๊ณ๊ฐ ์์ต๋๋ค.
Figure 63.13 Left: 5K points sampled on a mechanical piece with sharp features (creases, darts and corners). Right: reconstructed surface mesh with smoothed creases.
Leave a comment