CAJ | 학술논문

为实现虚拟环境中可变形物体与刚体间实时的碰撞检测，提出了一种快速的基于混合包围盒层次结构的并行碰撞检测算法。算法充分利用包围盒在检测速度和精度上的不同侧重，对可变形物体建立Sphere和AABB混合包围盒层次树，对刚体建立Sphere和OBB混合包围盒层次树；每个物体的混合包围盒层次树又分成上层、中层和下层，每层使用不同的包围盒；在碰撞检测遍历时，上层使用Sphere和Sphere相交检测快速排除不相交物体，在中层使用Sphere和OBB的相交检测进一步排除物体相交的可能性，在下层使用AABB和OBB的相交检测较精确地确定物体是否相交；采用多线程技术，在多核设备上实现并行碰撞检测算法。实验结果表明，与经典的AABB算法相比较，该算法在效率方面具有明显优势，能够满足可变形物体与刚体的碰撞检测要求。
위실현허의배경중가변형물체여강체간실시적팽당검측，제출료일충쾌속적기우혼합포위합층차결구적병행팽당검측산법。산법충분이용포위합재검측속도화정도상적불동측중，대가변형물체건립Sphere화AABB혼합포위합층차수，대강체건립Sphere화OBB혼합포위합층차수；매개물체적혼합포위합층차수우분성상층、중층화하층，매층사용불동적포위합；재팽당검측편력시，상층사용Sphere화Sphere상교검측쾌속배제불상교물체，재중층사용Sphere화OBB적상교검측진일보배제물체상교적가능성，재하층사용AABB화OBB적상교검측교정학지학정물체시부상교；채용다선정기술，재다핵설비상실현병행팽당검측산법。실험결과표명，여경전적AABB산법상비교，해산법재효솔방면구유명현우세，능구만족가변형물체여강체적팽당검측요구。
In order to achieve a real-time collision detection between deformable objects and rigid body in the virtual envi-ronment, a fast parallel collision detection algorithm based on hybrid bounding box hierarchy is proposed. Taking into account the different characteristics of the bounding box in the detection speed and accuracy, this algorithm builds a sphere-AABB hybrid bounding box hierarchy tree for deformable object, and establishes a sphere-OBB hybrid bounding box hierarchy tree for rigid body;in addition, every hybrid bounding box hierarchy tree is divided into upper layer, middle layer and lower layer, and each layer uses a different bounding box;when traversing the trees, this algorithm uses sphere-sphere test in the upper layer, sphere-OBB test in the middle layer and AABB-OBB test in the lower layer to detect collision. This paper uses multi-threading technology to achieve parallel collision detection algorithm on multi-core devices. Experi-mental results show that this algorithm has obvious advantages compared with the classic AABB algorithm in the aspect of efficiency, and can meet the requirement of collision detection between deformable objects and rigid body.