Research And Application Of GPU Oriented Parallel Space Indexing Scheme

Three-dimensional Model Processing is an important research topic of Computer Graphics, Reverse Engineering and so on. With the advancing of the computer software and hardware, especially the adventure of the Many-core GPU, Three-dimensional Model Processing usher in a new phase of development. That GPUs’excellent performance of the computing capacity makes that dealing with Large-scale Three-dimensional data and high Computational Complexity of Three-dimensional Model become possible. But at the same time, processing the Large-scale Three-dimension data with GPU also has a lot of problems to solve. How to design a sparse fast index structure on GPU is one of the important.This paper is subject to sparse index problem in the Three-dimensional Model processing, On the basis of deep analysis the storage difference between CPU and GPU, find a appropriate sparse index method of the parallel accessing on GPU, which can get excellent performance both in efficiency and memory’s usage because of the limited resource of the graphics card.This paper has attained this following achievement:(?) Introduced us GPUs’General-purpose computing architecture and Unified programming framework--CUDA. Then it introduced us CUDA’s thread architecture and memory hierarchy, and analyzed the GPU division of tasks and the layers of the memory performance.(?) Proposed a parallel method of storage and indexing on GPU. To the data characteristics of Three-dimension models, designed the methods of establish and accessing against the data type of single-key single value, single-key multi-value and multi-key multi-value in the three-dimension model processing respectively.(?) Proposed Point cloud smoothing parallel indexing CUDA algorithm based on the above parallel indexing, improving the scale of processing data, and according to the characteristics of the algorithm, provide the data a pretreatment for some purpose, thereby reducing the speed bottleneck access storage. The algorithm has been proved by experiments to be effective.(?) By analyzing the procedure of the CPU algorithm, Proposed and Realized a Mesh intersection CUDA algorithm on GPU and parallel index structure. Mining algorithm in parallel, proposed a parallel method. This algorithm also used Collision Detection based on GPUs’ accelerating to reduce the dimension of the calculation, it achieved a good performance.