Screened Poisson Surface Reconstruction Misha Kazhdan Hugues Hoppe Johns Hopkins University Microsoft Research Motivation 3D scanners are everywhere: Time of flight Structured light Stereo images
Shape from shading Etc. http://graphics.stanford.edu/projects/mich/ Motivation Surface reconstruction Geometry processing tio a z ri
n ete m ra Pa ation Decim Filte rin etc.
g Implicit Function Fitting Given point samples: Define a function with value zero at the points. Extract the zero isosurface. >0 F(q) =0 F(q)<0 0 F(q)>0
Sample points F(q) <0 Related work [Hoppe et al. 1992] [Curless and Levoy 1996] [Carr et al. 2001] [Kazhdan et al. 2006]
[Alliez et al. 2007] [Calakli and Taubin 2011] and many more Poisson Surface Reconstruction [2006] Oriented points samples of indicator gradient. Fit a scalar field to the gradients. 2 =min =
(q)=0.5 (q)=-0.5 ( ) ( ) Poisson Surface Reconstruction [2006] 1. Compute the divergence 2. Solve the Poisson equation
( ) ( ) 1 Poisson Surface Reconstruction [2006] 1. Compute the divergence 2. Solve the Poisson equation fine Discretize over an octree
Update coarse fine + + ( ) ( ) + 1 +
coarse Solution Correction Poisson Surface Reconstruction [2006] Properties: Supports noisy, non-uniform data Over-smoothes Solver time is super-linear Screened Poisson Reconstruction Higher fidelity at same triangle count Faster solver time is linear
Poisson Screened Poisson Outline Introduction Better / faster reconstruction Evaluation Conclusion Better Reconstruction Add discrete interpolation to the energy: 2
+ ( ) 0 2 ( )= ( ) ( ) Gradient fitting Sample interpolation [Carr et al.,,Calakli and Taubin] encouraged to be zero at samples Adds a bilinear SPD term to the energy Introduces inhomogeneity into the system Better Reconstruction Discretization:
Choose basis to represent : 1 ( ) ( ) +1 ( ) +2 ( ) 1 +2
+1 ( ) = ( ) =1 Better Reconstruction Discretization: For an octree, use B-splines: centered on each node scaled to the node size Better Reconstruction
Screened Poisson reconstruction: ^ To compute , solve: = with coefficients given by: = ( ) , ( ) ( ) = , ( ) + ( ) ( )
Bi Bj Better Reconstruction Screened Poisson reconstruction: ^ Sparsity is unchanged Entries are data-dependent
Bj Bi Bi = ( ) , ( ) ( ) = , ( ) + ( ) ( ) Bj
Faster Screened Reconstruction Observation: At coarse resolutions, no need to screen as precisely. Use average position, weighted by point count. Bj Bi Bi Bj B Bi j
Faster Reconstruction Solver inefficiency: fine Before updating, subtract constraints met at all coarser levels of the octree. complexity + ( ) +
+ Solution coarse Correction Faster Reconstruction Regular multigrid: Function spaces nest can upsample coarser solutions to finer levels Faster Reconstruction Adaptive multigrid:
Function spaces do not nest coarser solutions need to be stored explicitly Faster Reconstruction Naive enrichment: Complete octree Faster Reconstruction Observation: Only upsample the part of the solution visible to the finer basis. Faster Reconstruction
Enrichment: Iterate fine coarse Identify support of next-finer level Add visible functions Faster Reconstruction Original Enriched Faster Reconstruction Adaptive Poisson solver:
+ Update coarse fine + Get supported solution Adjust constraints + + + ( )
Solve residual + + + + + Solution + Correction
Visible Solution Outline Introduction Better / faster reconstruction Evaluation Conclusion Accuracy Poisson Screened Poisson
SSD [Calakli & Taubin] z z Accuracy Poisson
SSD [Calakli & Taubin] Screened Poisson
Performance Solver Time Poisson 89 sec Poisson (optimized) 36 sec Space
422 MB 604 MB Screened Poisson SSD [Calakli & Taubin] Input: 2x106 points 44 sec 3302 sec 1247 MB Performance Solver Time
Space Poisson 412 sec 1498 MB Poisson (optimized) 149 sec 2194 MB Screened Poisson 172 sec
Input: 5x106 points SSD [Calakli & Taubin] 19,158 sec 4895 MB Limitations Assumes clean data Poisson Screened Poisson Summary Screened Poisson reconstruction: Sharper reconstructions
Optimal-complexity solver Future Work Robust handling of noise (Non-watertight reconstruction) Extension to full multigrid Data: Thank You! [email protected], Digne et al., EPFL, Stanford Shape Repository Code:
Berger et al., Calakli et al., Manson et al. Funding: NSF Career Grant (#6801727) http://www.cs.jhu.edu/~misha/Code/PoissonRecon