Parallel Implementation Of The Smallest Directed Rectangle Algorithm On CUDA Platform

With the rapid development of computer technology, GPU general computing has become a major trend of heterogeneous computing in the field of high performance computing. CUDA (Compute Unified Device Architecture) launched by Nvidia Company, has become an important tool and development environment for high-performance computing, using GPU general computing to do image processing has become a trend. The oriented bounding rectangle and the smallest directed rectangle as one of image processing technology, is widely used in fast rendering scenes, fast interference detection, collision detection and other scenes.Based on CUDA and the actual project background, this paper focus on the convex hull, the oriented bounding rectangle and the smallest directed rectangle, propose parallelization strategies and optimization strategies to make the algorithm for optimal performance under certain conditions, while for different scenarios, different proposals put forward:when the demand is fast approximate detection and the distribution of the set of points is uniform, using the oriented bounding rectangle (OBB) to compute the smallest bounding rectangle; when it requires accurate detection of the object, using the classic smallest bounding rectangle algorithm which first compute the convex hull then use the Rotating Calipers method to get the smallest enclosing rectangle.This paper introduces and discusses the scan algorithm, the convex hull algorithm, the oriented bounding rectangle algorithm and the smallest directed rectangle algorithm and their research status, the author proposes parallel implementation strategy and optimization strategy of these algorithms. Finally, by experiments and analysis, the paper concludes the optimization strategy allows the algorithm for optimal performance under certain conditions.