计算机技术与发展
計算機技術與髮展
계산궤기술여발전
COMPUTER TECHNOLOGY AND DEVELOPMENT
2014年
1期
57-60
,共4页
宋城虎%闵林%朱琳%郭拯危
宋城虎%閔林%硃琳%郭拯危
송성호%민림%주림%곽증위
碰撞检测%空间分解%AABB%哈希表
踫撞檢測%空間分解%AABB%哈希錶
팽당검측%공간분해%AABB%합희표
collision detection%spatial subdivision%AABB%hash table
文中提出一种基于包围盒和空间分解的碰撞检测算法,用以解决软体的碰撞检测。算法使用AABB包围盒做初步检测,确定可能发生碰撞的物体。再根据包围盒的重叠情况缩小可能发生碰撞的区域,利用哈希表作为数据储存结构进行空间分解,将物体包围盒重叠区域的基本几何元素的空间网格映射到哈希表中,将碰撞区域缩小到基本几何元素,最后用基元碰撞检测找出具体碰撞点。由于前期AABB包围盒的处理减少了空间分解阶段需要映射的基本几何元素数量,该算法具有较高的运算速度。
文中提齣一種基于包圍盒和空間分解的踫撞檢測算法,用以解決軟體的踫撞檢測。算法使用AABB包圍盒做初步檢測,確定可能髮生踫撞的物體。再根據包圍盒的重疊情況縮小可能髮生踫撞的區域,利用哈希錶作為數據儲存結構進行空間分解,將物體包圍盒重疊區域的基本幾何元素的空間網格映射到哈希錶中,將踫撞區域縮小到基本幾何元素,最後用基元踫撞檢測找齣具體踫撞點。由于前期AABB包圍盒的處理減少瞭空間分解階段需要映射的基本幾何元素數量,該算法具有較高的運算速度。
문중제출일충기우포위합화공간분해적팽당검측산법,용이해결연체적팽당검측。산법사용AABB포위합주초보검측,학정가능발생팽당적물체。재근거포위합적중첩정황축소가능발생팽당적구역,이용합희표작위수거저존결구진행공간분해,장물체포위합중첩구역적기본궤하원소적공간망격영사도합희표중,장팽당구역축소도기본궤하원소,최후용기원팽당검측조출구체팽당점。유우전기AABB포위합적처리감소료공간분해계단수요영사적기본궤하원소수량,해산법구유교고적운산속도。
A collision detection algorithm based on the bounding volume and spatial subdivision for the collision detection of deformable objects is proposed. The algorithm does preliminary detection with AABB bounding volume boxes to find the objects which may be colli-ded. Then according to the area of overlap of the bounding box reduce the possible collision,use hash table as a data storage structure for spatial decomposition,the spatial grid of basic geometric elements in the object bounding box overlap area is mapped to a hash table,re-ducing the collision area to basic geometric elements,with primitive collision detection to find out specific collision point finally. Owing to the detection of AABB to reduce the number of object primitives,so this algorithm has a better performance.