Abstract: To increase the running speed of the collision detection algorithm, a new approach is proposed, which uses convex Bounding Volume Hierarchies (BVHs) to express convex polyhedron. Thus the distance problem of two convex polyhedrons is come down to a nonlinear programming problem with constraints. The nonlinear programming problem can be solved by simulated annealing genetic algorithm. Applying the acceptance criterion of the simulated annealing genetic algorithm, intersection and variation are carried out to optimize the time complexity. Results show that the efficiency of the simulated annealing genetic algorithm is high and the computing speed is faster.

Key words: computer software, collision detection, convex polyhedron, nonlinear programming, anneal genetic algorithms