A System for Reconstruction of Solid Models from Large Point Clouds

• Autorzy: Hussein A. S.
• Języki publikacji: EN

Abstrakty

EN

This paper presents an integrated system for reconstructing solid models capable of handling large-scale point clouds. The present system is based on new approaches to implicit surface fitting and polygonization. The surface fitting approach uses the Partition of Unity (POU) method associated with the Radial Basis Functions (RBFs) on a distributed computing environment to facilitate and speed up the surface fitting process from large-scale point clouds without any data reduction to preserve all of the surface details. Moreover, the implicit surface polygonization approach uses an innovative Adaptive Mesh Refinement (AMR) based method to adapt the polygonization process to geometric details of the surface. This method steers the volume sampling via a series of predefined optimization criteria. Then, the reconstructed surface is extracted from the adaptively sampled volume. The experimental results have demonstrated accurate reconstruction with scalable performance. In addition, the proposed system reaches more than 80% savings in the total reconstruction time for large datasets of Ο (10⁷) points.

Słowa kluczowe

EN

solid modeling; computational geometry; surface reconstruction; parallel implementation; radial basis functions; CAD; point clouds

• Wydawca: Institute of Information Technology of the Warsaw University of Life Sciences – SGGW
• Czasopismo: Machine Graphics and Vision
• Rocznik: 2009
• Tom: Vol. 18, No. 3
• Strony: 321--344
• Opis fizyczny: Bibliogr. 41 poz., il., wykr.

Twórcy

autor

Hussein A. S.

• Faculty of Computer and Information Sciences, Ain Shams University, Cairo, 11566, Egypt,

Bibliografia

• [1] Franke R.: Scattered data interpolation: tests of some method. Mathematics of Computation, JS-TOR, 38(157), 181-200, 1982. [doi:10.2307/2007474]
• [2] Berger M. J., Oliger J. E.: Adaptive mesh refinement for hyperbolic partial differential equations. Journal of Computational Physics, 53, 484-512, 1984.
• [3] Lorensen W. E., Cline H. E.: Marching cubes: a high resolution 3D surface construction algorithm. ACM SIGGRAPH Computer Graphics, 21(4), 163-169, 1987.
• [4] Berger M. J., Colella P.: Local adaptive mesh refinement for shock hydrodynamics. Journal of Computational Physics, 82(1), 64-84, 1989.
• [5] Beatson R. K., Newsam G. N.: Fast evaluation of Radial Basis Functions: I. Computers & Mathematics with Applications, Pergamon Press, 24 (12), 7-19, 1992.
• [6] Bloomenthal J.: An implicit surface polygonizer. Academic Press Graphics Gems Series, Graphics Gems IV, Academic Press Professional, New York, 1, 324-349, 1994.
• [7] Savchenko V. V., Pasko A. A., Okunev O. G., Kunii T. L.: Function representation of solids reconstructed from scattered surface points and contours. Computer Graphics Forum, Blackwell Synergy, 14(4), 181-188, 1995. [doi: 10.1111/1467-8659.1440181]
• [8] Wendland H.: Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree. Advances in Computational Mathematics, Springer-Verlag, 4, 389-396, 1995.
• [9] Turk G., O'Brien J. F.: Variational implicit surfaces. Technical Report GIT-GVU-99-15, Graphics, Visualization, and Useability Center. Georgia Institute of Technology. 9p, 1999.
• [10] Beatson R. K., Light W. A., Billings S.: Fast solution of the Radial Basis Functions interpolation equations: domain decomposition methods. SIAM Journal on Scientific Computing, 22(5), 1717-1740, 2000.
• [11] Blane M. M., Lei Z., Cooper D. B.: The 3L algorithm for fitting implicit polynomial curves and surfaces to data. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22, 298-313, 2000.
• [12] Akkouche S., Galin E.: Adaptive implicit surface polygonization using marching triangles. Computer Graphics Forum, Blackwell Synergy, 20(2), 67-80, 2001. [doi:10.1111/1467-8659.00479]
• [13] Alexa M., Behr J., Cohen-Or D., Fleishman S., Levin D., Silva C. T.: Point set surface. In: Proc. Of the Conference on Visualization, Visualization'01, IEEE Computer Society Washington, DC, USA, 21-28, 2001.
• [14] Carr J. C., Beatson R. K., Cherrie J. B., Mitchell T. J., Fright W. R., McCallum B. C., Evans T. R.: Reconstruction and representation of 3D objects with Radial Basis Functions. In: Proc. of the 28th Annual Conference on Computer Graphics and Interactive Techniques, ACM Press New York, NY, USA, 67-76, 2001.
• [15] Karkanis T., Stewart A. J.: Curvature-dependent triangulation of implicit surfaces. IEEE Computer Graphics and Applications, 22(2), 60-69, 2001.
• [16] Morse B. S., Yoo T. S., Chen D. T., Rheingans P., Subramanian K. R.: Interpolating implicit surfaces from scattered surface data using compactly supported Radial Basis Functions. In: Proc. of the International Conference on Shape Modeling &: Applications, 89-98, 2001.
• [17] Iske A.: Scattered data modelling using Radial Basis Functions. In: Iske A., Quak E., Floater M. (Ed.), Tutorials on Multiresolution in Geometric Modelling, Springer-Verlag, Heidelberg, Germany, 205-242, 2002.
• [18] Randrianarivony M., Brunett G.: Parallel implementation of surface reconstruction from noisy samples. Preprint-Reihe des Chemnitzer SFB 393, Preprint SFB 393/02-16, ISSN 1619-7178, 2002.
• [19] Alexa M., Behr J., Cohen-Or D., Fleishman S., Levin D., Silva C. T.: Computing and rendering point set surfaces. IEEE Transaction on Visualization and Computer Graphics, 9(1), 3-15, 2003.
• [20] Carr J. C., Beatson R. K., McCallum B. C., Fright W. R., McLennan T. J., Mitchell T. J.: Smooth surface reconstruction from noisy range data. In: Proc. of the 1st International Conference on Computer Graphics and Interactive Techniques in Australia and South East Asia, 119-126, 2003.
• [21] Cermak M.: Methods for implicit surfaces polygonization, DCSE/TR-2003-01, University of West Bohemia in Pilsen, 2003.
• [22] Ohtake Y., Belyaev A., Alexa M., Turk G., Seide H. P.: Multi-level Partition of Unity implicits. ACM Transactions on Graphics (TOG), 22(3), 463-470, 2003.
• [23] Ohtake Y., Belyaev A., Seidel H. P.: A multi-scale approach to 3D scattered data inter polation with compactly supported basis functions. Shape Modeling International, 153-161, 2003. [doi:10.1109/SMI.2003.1199611]
• [24] Ralf K., Hans-Christian H.: visualization of time-dependent adaptive mesh refinement data. ZIB-Report 03-16, Zuse-Institut, Berlin, 2003.
• [25] Weber G. H., Kreylos O., Ligocki T. J., Shalf J. M., Hagen H., Hamann B., Joy K. I.: Extraction of crack-free isosurfaces from adaptive mesh refinement data. In: Farin, G., Hagen, H., Hamann, B. (Ed.) Approximation and Geometrical Methods for Scientific Visualization, Springer-Verlag, Heidelberg, Germany, 19-40, 2003.
• [26] Cuno A., Esperanga C., Oliveira A., Cavalcanti P. R.: Fast polygonization of variational implicit surfaces. In: Proc. of the Computer Graphics and Image Processing, XVII Brazilian Symposium (SIBGRAPI'04), 258-265, 2004.
• [27] Fang, D. C.: Extracting geometrically continuous isosurfaces from adaptive mesh refinement data. In: Proc. of 2004 Hawaii International Conference on Computer Sciences, 216-224, 2004.
• [28] Khattab D. R., Abdel Aziz A. H., Hussein A. S.: An enhanced WWW-based scientific data visualization service using VRML. In: Proc. of the 2004 ACM SIGGRAPH International Conference on Virtual Reality Continuum and its Applications in Industry, 134-140, 2004.
• [29] Tobor I., Reuter P., Schlick C.: Efficient reconstruction of large scattered geometric datasets using the Partition of Unity and Radial Basis Functions. Journal of WSCG 2004, 12, 467-474,
• [30] Tobor I., Reuter P., Schlick C.: Multi-scale reconstruction of implicit surfaces with attributes from large unorganized point sets. In: Proc. of the Shape Modeling International, 19-30, 2004.
• [31] Jing W., Yunde J., Luping A.: Parallel computation of 3D shape reconstruction under PCs cluster. Journal of Computer-Aided Design and Computer Graphics, 17(5), 895-901, 2005.
• [32] Kazhdan M.: Reconstruction of solid models from oriented point sets. In: Proc. of the 3rd Eurographics Symposium on Geometry Processing, (SGP 2005), 73-82, 2005.
• [33] Kazhdan M., Bolitho M., Hoppe H.: Poisson surface reconstruction. In: Proc. of the 4th Eurographics Symposium on Geometry Processing, ACM International Conference Proceeding Series, 256, 61-70, 2006.
• [34] Kohout J., Varnuka M., Kolingerov I.: Surface reconstruction from large point clouds using virtual shared memory manager. In: Proc. of the International Conference on Computer Science and Its Applications (ICCSA 2006), 71-80, 2006.
• [35] Bolitho M., Kazhdan M., Burns R., Hoppe H.: Multilevel streaming for out-of-core surface recon struction. In: Proc. of the 5th Eurographics Symposium on Geometry Processing, ACM International Conference Proceeding Series, 257, 69-78, 2007.
• [36] Wang Q., Pan Z., Bu J., Chen C.: Parallel RBF-based reconstruction from contour dataset. In: Proc. of the 10th IEEE International Conference on Computer-Aided Design and Computer Graphics, 82- 85, 2007.
• [37] Cyberware Incorporated, 2008. [Online] http://www.cyberware.com/.
• [38] Georgia Institute of Technology: Large geometric models archive, 2008. [Online] http://www.cc.gatech.edu/projects/large_models/.
• [39] Schroeder W., Martin K., Lorensen B.: The visualization toolkit: an object-oriented approach to 3D graphics, 3rd Edition, Kitware, Inc. publishers. NY, USA, 2008. [ISBN-13: 978-1930934078]
• [40] Stanford University: Stanford 3D Scanning Repository, 2008. [Online] http://graphics.stanford.edu/data/3Dscanrep/.
• [41] University of Chicago - Argonne National Laboratory: MPICH home page, 2008. [Online] http://www-unix.mcs.anl.gov/mpi/mpich/index.htm.