Research On Optimization Of Convex Hull Construction And Collision Detection

Collision detection,as a basic issue of physical simulation,path programming,virtual assembly,haptic rendering and many other aspects in computer science field,has been addressed by many related algorithms so far.However,these algorithms have their own advantages and disadvantages.Some of them,such as V-Clip algorithm,Lin-Canny algorithm and GJK algorithm,treated polyhedron as a convex geometry,and therefore the concave polyhedron needs to be converted to convex geometry by structuring a convex hull.When applying these algorithms to practical application,they will also encounter some other challenges.For instance,haptic rendering requires extremely high refresh rate;virtual assembly for precision parts requests not only high real-time performance,but also extremely high accuracy of detection results.Therefore,how to optimize and improve existing convex hull construction algorithms and collision detection algorithms according to the actual application environment,which is a field worthy of study,has strong theoretical and realistic significance.By using rigid part model of mechanical watch as research subjects which based on triangle primitive,we discuss the related issues of convex hull construction and two stages of collision detection in this paper.The main research works and contributions are as follows:1.First we study the nature of convex hull and then present the basic idea and computational complexity of Gift-Wrapping algorithm and QuickHull algorithm in three-dimensional space.The advantages and disadvantages of QuickHull construction algorithm are discussed emphatically,and thus a improved convex hull construction algorithm using three-dimensional point set as input is proposed.By giving priority to other vertices that are coplanar with a given vertex on the convex hull,this algorithm avoids the generation of the middle face,and reduces the number of primitives which constitute the final convex hull.The convex hull of parts model,which could speed up the construction of the bounding volume and be used for the realization of fast collision detection between mechanical parts and tools as well as environment,is constructed by using the improved algorithm.2.We investigate in global stage the N-body prune methods of collision detection,such as bounding volume tree,space subdivision and topological method,and discuss the applicable scenarios for these methods.In topological methods,we emphatically analyze advantages,disadvantages and the operational efficiency of the sweep and prune algorithm as well as several variants of it,then an sweep and prune algorithm which is optimized and based on sample estimation is proposed.With this algorithm,we can select the best discrete sorting axis dynamically through the sample estimation,therefore the negative effect on the real-time performance caused by the gathering of models and the change of model density in a large scene can be decreased.The experimental results show that the performance of the new algorithm is superior to that of other similar algorithms and hence it has wider practicality than others.3.We look into exact intersecting detection method for collision detection in local stage.In order to address the lacking of the real-time performance of the existing bounding volume tree algorithm and the poor applicability to mechanical watch assembly scenarios,we proposed an improved hybrid bounding volume tree algorithm which uses multiple related bounding volumes to create the tree nodes and amends the way the tree is constructed.By using this algorithm,it is more accurate and efficient to detect the intersection between parts model.Also,the optimization of the memory footprint is discussed.4.By using the Unity3D engine,a mechanical watch virtual assembly system,in which its scene was used as a template to construct the experimental environment,is developed.Then in the experimental environment,two experiments are designed for comparison of the running time,accuracy and comprehensive performance among several collision detection algorithms.By analyzing the comparative experimental results with the traditional algorithms,it shows that the performance of hybrid bounding volume tree algorithm proposed in this paper is superior to that of traditional algorithms.