Research On Fast Collision Detection Technology In Complex Virtual Environment

Collision detection in virtual reality has become a hot issue in the fields of computational geometry,computer animation,simulation robot,CAD/CAM,3D game development,physical simulation,etc.,and increasingly complex virtual environment puts forward higher requirements on the sense of reality and real-time of collision.This paper presents a crossover and exclusive operator based SIMD parallel collision detection algorithm,crossover and exclusive operator is introduced,and the search space is limited to local minimum area of the nonuniform,reduced the search time of ant colony,and the good point set genetic operator is introduced into the solution of the optimization,proposed a restructuring line was proposed,using the GPU in order to improve the tracking performance of light collision detection methods.It can integrate different ray tracing algorithms to deal with objects of different properties effectively in the detailedly detection stage.Through the detailed test phase is divided into three steps,to be able to keep the whole assembly line intensive input,in order to efficiently use of GPU,this paper proposes a iterative light use of space and time correlation tracking algorithm,the proposed iterative ray-tracing algorithm can speed up any existing light tracing algorithm,effectively improve the existing algorithm of ray tracing,puts forward a fabrics on the GPU,object tracking and light cloth cloth simulation of collision detection and response algorithm,this paper proposes a cloth by ray tracing method of collision detection.The proposed method can detect the collision between volumetric objects(rigid or deformable)and fabrics,as well as the collision between fabrics(including automatic collision).The main research results are as follows:1.A high quality geometric partition method of BVH structure is proposed.At the same time,an efficient and fully parallel accelerated structure construction process was proposed to develop 8-bit unit vector and advanced vector extension in x86 CPU architecture.In addition,a clustering algorithm which can calculate the complexity in linear time is proposed.2.A partition method for establishing high-performance BVH is provided.An efficient parallel construction process is also proposed,which implements the sequential allocation of primitives based on the projection center of the longestbounding box,and a fast parallel piecewise radix sort algorithm is proposed for the primitives.The advantage of this partitioning method is to optimize the parallel scanning of data and quickly determine the coordinates of the longest intersecting surface of the AABB bounding box.And get a good parallel construction time.We use a position tracking traversal method to speed up ray tracing and increase the frame rate.The comparison with SAH-BVH algorithm is given.In addition,the process of memory occupation and average intersecting test is presented and compared with sah-bvh algorithm.3.A SIMD parallel collision detection algorithm based on crossover and exclusion operators is proposedThe crossover and repulsion operators are introduced to limit the search space to the non-uniform local minimal region,which reduces the searching time of the ant colony,and the genetic operator of the best point set is introduced to the optimization of the solution.A parallel collision detection algorithm CROCDA based on cross rejection operator is proposed.The crossover and repulsion operators are introduced to limit the search space to the non-uniform local minimal region,which reduces the searching time of ant colony.In the solving process of multi-ant colony,the fine-grained decomposition of parallel tasks is adopted,and the sub-tasks are distributed to the processing cores of multi-core processors to execute in parallel using the load balancing strategy.The main advantages are described in the following aspects:(1)use the structural advantages of simd-dop encased box to construct a task tree.Subtasks are executed under multiple threads,making the parallelization process of the program more efficient;(2)introduce the concept of cross exclusion operator.The stack technology is adopted to mark traversal nodes,which reduces the number of intersection detection,improves the speed of collision detection,and displays the virtual scene in real time.(3)the program is processed in parallel in the computer cluster,and sub-tasks are executed in parallel to shorten the collision detection time;(4)adopt crossover exclusion operator to optimize ant colony,so that the algorithm is not easy to fall into local extremum,and can be quickly executed under SIMD.4.A collision detection method is proposed to improve ray tracing performance by using GPU in reconfigured pipeline.In the detailed detection stage,ray tracing algorithm is used to deal with different types of objects effectively.By partitioning the detailed detection stage,the whole pipeline is maintained dense input,and the efficiency of GPU is improved.The experimental results show that the proposed method speeds up on average.5.A collision detection algorithm based on spatial and temporal correlation iteration ray tracing is proposed.The iterative ray tracing algorithm proposed in this chapter can accelerate any existing ray tracing algorithm,starting from the last affected triangle until the current triangle is found,instead of recalculating the ray at each step,and introducing predicted light to avoid unnecessary penetration.A collision detection method between fabric and fabric using ray tracing technology is proposed.It is an object-space-based algorithm implemented in CUDA and NVIDIA OptiX ray tracing engine.Several rays are projected from the moving vertex of the cloth to find the location relationship with other objects in the scene.The high performance parallel computing performance of GPU is utilized to accelerate the collision detection and solving process.6.A new algorithm for ray tracing and collision detection and response of deformable model on GPU is proposed.For the motion model,the ray is projected along the direction of each vertex of the deformation model,and the collision is judged by ray tracing.If collision is found,the collision point is found.If collision is not found,another ray is projected by normal vector,and the error caused by discrete simulation is corrected by inverse processing.Compared with collision detection based on image space,it has high efficiency and can be applied to dynamic simulation of deformation model.