Research On The Key Technology Of Interference Detection For Virtual Assembly

Interference detection is an important technology of computer graphics, which is extensively used in the fields such as virtual assembly, virtual surgery, flight navigation, path planning of robots and animation. For above applications of computer graphics, both information of distance and detection of intersection are required to adjust the route/trajectory timely and avoid the possible interference. So, it is vital that determine the position between objects and provide distance information (separation, penetration depth and the witness vector) efficiently and accurately to fit the need of such applications. The research work, which is not limited to a special problem, involves many subjects such as computer science, dynamics, machine engineering and mathematics. Because of the great value in theory and practice, various new theories and algorithms have emerged in endlessly. However, so far many difficulties remain unresolved, especially in some applications that require an accurate measure. The objective of this research is to present new approaches for improving the performance of distance algorithm by use of some existing technologies such as sweeping line, bounding volume hiberarchy, branch limit strategy, heuristic searching and nonlinear programming theory. The research of the dissertation consists of the interference detection and distance computation for some typical models such as planar polygon, convex polyhedron and smooth surface, and some efficient algorithms are presented in the paper.The principal research work and novelties are listed as follows:1.A quasi QuickHull algorithm (QQH algorithm) computing the distance between planar convex polygons is presented in the dissertation. QQH algorithm, which is based on the QuickHull algorithm, solves the problem of minimum translational distance (MTD) between planar convex polygons by constructing the translational C-space obstacle (TCSO) M of both objects implicitly with computing directed area. Firstly, two different vertices are obtained by calling GJK (Gilbert-Johnson-Kerrthi) algorithm two times; secondly, the initial inner polygon P is calculated via (triangle) area computation; thirdly, the nearest edge on P distance to origin is determined and then the opposite vertex on M corresponds to the nearest edge is searched using area computation; finally, the boundary of P is updated by adding the new opposite vertex and carries out the above procedure repeatedly until the nearest edge or vertex on the border of M is found.QQH algorithm provides a fast terminate condition based on judging the area and avoids the special process for the exception, as well as determines whether interference occurs or not by region test.2.A sweep line method to determine the position between two planar simple polygons is purposed in this paper. Based on intersection detection algorithm of bounding volume hierarchy tree (BVT), the method resolves the problem of relation determining for planar simple polygons by testing the position between monotone chains with sweep line technology. Firstly, the border of polygon is decomposed into a collection of monotone chains; secondly, the BVH of monotone chains are constructed respectively and the monotone chain-pairs whose bounding volume overlap are obtained using interference detection technology based on BVT; thirdly, the relation of a monotone chain-pair is decided through sweep line approach; finally, the accurate relation between polygons are achieved by the further test accord to the results from chain-pair test. The new method can distinguish just boundary touching from inner intersection, and the stability of ray shooting for checking whether one object contain the other is enhanced.3.A new approach based on coupling monotone chains pairwse for computing the separation between planar simple polygons is put forward in the article. On the basis of BVT distance algorithm, the approach settles the separation problem between two separable simple polygons by coupling the monotone chains selectively to determine the possible sub-boundary where the nearest point lies with. Firstly, both the interested boundary...