Abstract
We introduce a GPU grid-based data structure for massively parallel nearest neighbor searches for dynamic point clouds. The implementation provides real-time performance and it is executed on GPU, both grid construction and nearest neighbors (approximate or exact) searches. This minimizes the memory transfer between device and system memories, improving overall performance. The proposed algorithm may be used across different applications with static and dynamic scenarios. Moreover, our data structure supports three-dimensional point clouds and given its dynamic nature, the user can change the data structure’s parameters at runtime. The same applies to the number of neighbors to be found. Performance comparisons were made against previous works, endorsing the benefits of our solution. Finally, we were able to develop a real-time Point-Based Rendering application for validation of the data structure. Its drawbacks and data distribution’s impact on performance were analysed and some directions for further investigation are given.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Pharr M., Humphreys G.: Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann Publishers Inc., San Francisco (2004)
Jensen H.W.: Realistic Image Synthesis Using Photon Mapping. A. K. Peters, Natick (2001)
Alexa, M., Gross, M., Pauly, M., Pfister, H.: Stamminger, Marc., Zwicker, Matthias.: Point-based computer graphics. In: SIGGRAPH ’04: ACM SIGGRAPH 2004 Course Notes, p. 7. ACM, New York (2004)
Losasso, F., Gibou, F., Fedkiw, R.: Simulating water and smoke with an octree data structure. In: SIGGRAPH ’04: ACM SIGGRAPH 2004 Papers, pp. 457–462. ACM, New York (2004)
Lacoste, J., Boubekeur, T., Jobard, B., Schlick, C.: Appearance preserving octree-textures. In: GRAPHITE ’07: Proceedings of the 5th International Conference on Computer Graphics and Interactive Techniques in Australia and Southeast Asia, pp. 87–93. ACM, New York (2007)
Teschner M., Heidelberger B., Müller, M., Pomeranets, Danat., Gross M.: Optimized spatial hashing for collision detection of deformable objects. In: Vision, Modeling, Visualization (VMV), pp. 47–54 (2003)
Curtis, S., Tamstorf, R., Manocha, D.: Fast collision detection for deformable models using representative-triangles. In: I3D ’08: Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games, pp. 61–69. ACM, New York (2008)
Pantazopoulos I., Tzafestas S.: Occlusion culling algorithms: a comprehensive survey. J. Intell. Robot. Syst. 35(2), 123–156 (2002)
Knuth D.: Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, Massachusetts (1998)
Cover T., Hart P.: Nearest neighbor pattern classification. Inf. Theory IEEE Trans. 13(1), 21–27 (1967)
Safar M.: K nearest neighbor search in navigation systems. Mob. Inf. Syst. 1(3), 207–224 (2005)
Alexa, M., Behr, J., Cohen-Or, D., Fleishman, S., Levin, D., Silva, C.T.: Point set surfaces. In: Visualization Conference, pp. 21–28. IEEE (2001)
Levin, D.: Mesh-independent surface interpolation. In: Brunnett, G., Hamann, B., Müller, H. (eds.) Geometric Modeling for Scientific Visualization, pp. 37–49. Springer (2003)
Pauly, M., Gross, M., Kobbelt, L.P.: Efficient simplification of point-sampled surfaces. In: VIS ’02: Proceedings of the Conference on Visualization ’02, pp. 163–170. IEEE Computer Society, Washington (2002)
Adams, B., Pauly, M., Keiser, R., Guibas, L.J.: Adaptively sampled particle fluids. In: ACM Transactions on Graphics (SIGGRAPH ’07 papers), San Diego, CA, vol. 26, issue 3, art. no. 48. ACM Press, New York (2007)
Mitra, N.J., Nguyen, A.: Estimating surface normals in noisy point cloud data. In: SCG ’03: Proceedings of the Nineteenth Annual Symposium on Computational Geometry, pp. 322–328. ACM, New York (2003)
Clarenz, U., Rumpf, M., Telea, A.: Finite elements on point based surfaces. In: Symposium of Point Based Graphics 2004 (2004)
Sankaranarayanan J., Samet H., Varshney A.: A fast all nearest neighbor algorithm for applications involving large point-clouds. Comput. Graph. 31(2), 157–174 (2007)
Samet H.: Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling). Morgan Kaufmann, San Francisco (2005)
Connor, M., Kumar, P.: Parallel construction of k-nearest neighbor graphs for point clouds. In: Proceedings of Volume and Point-Based Graphics, pp. 25–32. IEEE VGTC (2008)
Lin, K.-I., Yang, C.: The ANN-tree: an index for efficient approximate nearest neighbor search. In: DASFAA ’01: Proceedings of the 7th International Conference on Database Systems for Advanced Applications, pp. 174–181. IEEE Computer Society, Washington (2001)
Arya S., Mount D.M., Netanyahu N.S., Silverman R., Angela Y.W.: An optimal algorithm for approximate nearest neighbor searching fixed dimensions. J. ACM 45(6), 891–923 (1998)
Garcia, V., Debreuve, E., Barlaud, M.: Fast k nearest neighbor search using gpu. In: CVPR Workshop on Computer Vision on GPU, Anchorage (2008)
Guennebaud G., Germann M., Gross M.: Dynamic sampling and rendering of algebraic point set surfaces. Comput. Graph. Forum 27(2), 653–662 (2008)
Zhou, K., Hou, Q., Wang, R., Guo, B.: Real-time KD-tree construction on graphics hardware. In: SIGGRAPH Asia ’08: ACM SIGGRAPH Asia 2008 papers, pp. 1–11. ACM, New York (2008)
Leite, P.J.S., Teixeira, J.M.X.N., de Farias, T.S.M.C., Teichrieb, V., Kelner, J.: Massively parallel nearest neighbor queries for dynamic point clouds on the GPU. In: Proceedings of the 2009 21st International Symposium on Computer Architecture and High Performance Computing, SBAC- PAD ’09, pp. 19–25. IEEE Computer Society, Washington (2009)
Mark H.: Optimizing parallel reduction in CUDA. http://www.nvidia.com/content/cudazone/cuda_sdk/Data-Parallel_Algorithms.html (2009)
NVIDIA.: Compute unified device architecture programming guide. http://www.nvidia.com/cuda (2009)
Farias T.S.M.C., TeixeiraJoao Marcelo N.X., Leite Pedro J.S., Almeida G.F., Almeida Mozart W.S., Teichrieb V., Kelner J.: High performance computing: cuda as a supporting technology for next generation augmented reality applications. RITA 16(1), 26 (2009)
Shubhabrata S., Mark H., Zhang, Y., Owens, J.D.: Scan primitives for GPU computing. In: GH ’07: Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware, pp. 97–106. Eurographics Association, Aire-la-Ville (2007)
Eng J.: Sample size estimation: how many individuals should be studied?. Radiology 227(2), 309–313 (2003)
Anderson J.A., Lorenz C.D., Travesset A.: General purpose molecular dynamics simulations fully implemented on graphics processing units. J. Comput. Phys. 227(10), 5342–5359 (2008)
Levoy, M., Whitted, T.: The use of points as a display primitive. Technical Report 85-022, University of North Carolina at Chapel Hill (1985)
Botsch, M., Hornung, A., Zwicker, M., Kobbelt, L.: High-quality surface splatting on today’s GPUs. In: Proceedings of the Eurographics Symposium on Point-Based Graphics, pp. 17–24 (2005)
Botsch, M., Kobbelt, L.: High-quality point-based rendering on modern gpus. In: Pac. Conf. Comput. Graph. Appl., pp. 335–343 (2003)
Guennebaud, G., Paulin, M.: Efficient screen space approach for hardware accelerated surfel rendering. In: Vision, Modeling and Visualization, pp. 485–495. IEEE Signal Processing Society (2003)
Botsch, M., Spernat, M., Kobbelt, L.: Phong splatting. In: Proceedings of Symposium on Point-based Graphics, pp. 25–32 (2004)
de Farias, T.S.M.C., Almeida, M.W.S., Teixeira Joao, M.X.N., Teichrieb, V., Kelner, J.: A high performance massively parallel approach for real time deformable body physics simulation. In: Comput. Archit. High Perform. Comput. Symp., pp. 45–52 (2008)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Leite, P., Teixeira, J.M., Farias, T. et al. Nearest Neighbor Searches on the GPU. Int J Parallel Prog 40, 313–330 (2012). https://doi.org/10.1007/s10766-011-0184-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10766-011-0184-3