Research On Collision Detection Between Non-convex Objects Based On GPU Stream Computing Model

Collision detection is one of vital problems in the fields of robotics, virtualreality and CAD/CAM, etc. Its fundamental task is to detect whether there arecontacts and penetrations between two or among multiple objects.Based on the intensive analyses and summarizations of various algorithms aboutcollision detection, taking advantage of the high stream computing power of graphicshardware, the dissertation converts non-convex objects into triangle strips, maps thegeometry computation of collision detection between two triangles into shaders of theprogrammable graphics processing unit (GPU) to match the parallel architecture ofgraphics hardware, and produces fast accurate results via real time rendering.Analyses and applications for the tessellation of trimmed NURBS surfaces arepresented, which do good for the further relative research.This subject is a part of the abnormal-workpiece measuring project in Mianyang,Sichuan province. Aiming at the collision detection problems in realistic simulation ofnon-convex workpieces, such as holes, grooves, cavities or turbines, we have done thefollowing work:1. Design the framework of analysising various file formats, and implement the3DS file parser to read scene data.2. Through introducing GPU graphics hardware and its development language,realize the migration of SAT (separating axis theorem) algorithm intoprogrammable GPU's fragment shader, implement the collision detectionalgorithm between non-convex workpieces based on the stream computingmodel.3. Compare three solutions for the tessellation of the trimmed NURBS surfaces.Modify and expand the tNURBS library to basically implement the demandof the subject.