Fast Convexhull Computation Parallel Design And Implementation Based On CUDA

Physical simulation of collision detection has a profound influence on operation response time.The bounding box method is not efficient for fits into the entire model in three dimensionality at present,which extra space determine an object intersection precision is reduced.It is difficult to obtain satisfactory results.The convex hull can cover the entire model and reduce the number of intersecting calculations.With the refinement and complexity of models,the scale and the partial number of convex packaging points of three-dimensional objects are increasing.The high density data processing of the convex hull results in a consumable time more than reasonable range.Therefore,how to construct convex hull quickly becomes the subject of extensive research.In this paper,the original serial mode is designed in parallel mode by using the universal computing power of GPU graphics processor to deal with large scale data processing.Firstly,the paper introduces the algorithm of the main structure convex hull of three-dimensional space.This paper focuses on the Quickhull algorithm developed by random increment method.Meanwhile,it expounds the principle of convex hull and the complexity of time and space in the analysis from two-dimensional space to three-dimensional space.The parallel principle of graphics processor is map data to hardware architecture which different data performing the same operation.Based on convex hull algorithm function complexity structure,initialize the tetrahedron and calculating extreme value point,and the judgment of point with plane in independent operation,and easy to deal with some assigned to GPU end to make it complete large-scale data calculation.Complex logical decisions are delivered to the CPU.Such reasonable task division reduces processing of idle and increases the utilization of equipment.Secondly,the algorithm is optimized to improve the efficiency of parallel computation by access memory technology.In this paper,we use the model data of different sets scale to realize the construction of convex hull in serial and parallel conditions,and display the final result of convex hull with OpenGL graphical interface.We use acceleration ratio as measure to evaluation time performance.The data shows that the overall speed time performance of the algorithm can be improved greatly when the data size is huge.