浏览全部资源
扫码关注微信
Received：14 August 2023，
Revised：2024-01-07，
Published：16 October 2024
移动端阅览
目的
2
为了解决柔性体布料与复杂刚体模型的碰撞检测速率低与真实性差的问题，本文提出混合结构的层次包围盒法（bounding volume hierarchies， BVH）和快速构造OBB（oriented bounding box）包围盒法以及对被检测物体构造空间网格法来提高碰撞检测的时效性。
方法
2
首先构建适合柔性体布料的混合结构的层次包围盒树，顶层和底层分别使用结构简单的球形包围盒和AABB（aixe align bounding box）包围盒，中间层使用球形—AABB混合结构对碰撞对进行快速高效剔除。其次对复杂刚体模型使用三角形折叠法进行表面简化，用简化模型代替原复杂模型进行包围盒快速构建。最后构建空间网格，进行更精确的碰撞检测以及碰撞响应。
结果
2
实验结果表明，在相同场景情况下，本文方法与其他方法相比包围盒构建速度缩短了10%～18%，对复杂刚体模型构建的OBB包围盒紧密程度提升了8%～15%。包围盒剔除率在相同模型情况下比传统方法提升了8%～13%，整体碰撞检测耗时缩短了6%～13%。本文方法在速率和剔除率提升的情况下模拟的真实性也得到了保证。
结论
2
本文方法在检测速率和碰撞剔除率上都有所提升，能够在保证模拟真实的情况下缩短整体碰撞检测耗时，更适用于柔性体和刚体之间的碰撞检测。
Objective
2
Collision detection and collision processing are challenging problems and active research fields in computer graphics and virtual reality. The collision detection algorithm is a technical difficulty and the most important link in the entire simulation process. The quality of collision detection algorithms directly affects the authenticity of simulation situations. For collision detection between fabric and complex rigid body models， the softness and nonfixity of fabric pose great challenges to collision detection. When numerous particles that make up the fabric move， collisions inevitably occur. If collisions cannot be detected in a timely manner and the collision location cannot be repaired， penetration and distortion occur， considerably affecting subsequent simulations. Therefore， during the collision detection of fabric， higher requirements are placed on the authenticity and real-time performance of the system. To solve the problem of low detection rate and poor simulation authenticity when collision detection occurs between flexible fabric and complex rigid body models during interaction， this study analyzes the characteristics of flexible fabric and complex rigid body models and selects different suitable bounding boxes for collision detection of different detection objects. This study proposes a hybrid hierarchical bounding box method， a fast directed bounding box method， and a spatial grid method for detecting objects to improve the timeliness of collision detection.
Method
2
In response to the characteristics of flexible fabric that is soft and prone to deformation， a bounding box with fast construction speed and simple structure is selected for flexible fabric. The bounding box with a simple structure can be quickly updated to better cope with the deformation of flexible fabric during movement， making the bounding box better surrounded in the simulation of the fabric model and more rapid for subsequent collision detection. First， a hierarchical bounding box tree with a hybrid structure suitable for flexible fabric is constructed. The hierarchical bounding box tree structure is divided into three layers， with the upper， middle， and lower layers playing different roles in eliminating each other. The three layers of bounding boxes overlap with each other. The top layer uses a simple and fast spherical bounding box， the middle layer uses a spherical aixe align bounding box（AABB） mixed structure bounding box， and the bottom layer uses an AABB bounding box. A quickly constructed bounding box is used to eliminate irrelevant collision pairs quickly and efficiently， facilitating subsequent detection. The main reason for the slow speed and poor authenticity of collision detection for complex rigid body models is due to numerous points and surfaces contained in the complex surface， which leads to low detection efficiency and high system overhead. Moreover， the more complex the number of points and surfaces， the easier it is to cause penetration and distortion during simulation. In this situation， we use the method of triangle folding to simplify the complex rigid body model and combine it with quadratic error measurement to simplify and evaluate the model. This method enables the complex rigid body model to reduce the number of points and surfaces without losing the details of the model’s cause and allows the simplified model to replace the original complex model for rapid construction of the directed bounding box. This method accelerates the construction speed of bounding boxes and reduces system overhead， accelerating the process of collision detection. After collision detection of the bounding box structure， the collision pair information is obtained. The spatial grid method is used on the surface of the collision model to connect sequentially the model surface vertices between the detected models to construct a spatial grid. The area or volume of the spatial grid changes with the movement of the detected object. By detecting changes in the area or volume of the spatial grid， whether a collision has occurred is determined. The elements that make up the spatial grid must be constrained so that the area or volume of the spatial grid is within an acceptable range and is not zero. This process ensures that the simulation effect is not affected and prevents the collision simulation between the fabric and the rigid body model from penetrating.
Result
2
Compared with traditional methods and other literature methods， this study conducted experiments to record collision detection data in multiple scenarios. The experimental results showed that in the same scenario， compared with other methods， the construction speed of the bounding box in this study was shortened by 10%～18%， and the tightness of the bounding box on the model was improved by 8%～15%. For the same collision model， the removal rate of irrelevant collision pairs by bounding boxes is improved by 8%～13% compared with traditional methods， and the overall collision detection time is reduced by 6%～13%. This method ensures the authenticity of the simulation while improving the collision detection rate and rejection rate.
Conclusion
2
The improved bounding box method in this study has improved the detection speed in the rough detection stage and enhanced the rejection rate of incoherent collision pairs. In the precise detection stage， the use of spatial mesh methods can not only detect collisions but also prevent collision penetration between the fabric and the rigid body by imposing constraints on the model vertices. The algorithm in this study not only ensures the overall simulation authenticity but also improves the detection speed， reduces system overhead， and is more suitable for collision detection with flexible fabric and complex rigid body models.
Chang J W ， Wang W P and Kim M S . 2010 . Efficient collision detection using a dual OBB-sphere bounding volume hierarchy . Computer-Aided Design ， 42 （ 1 ）： 50 - 57 ［ DOI： 10.1016/j.cad.2009.04.010 http://dx.doi.org/10.1016/j.cad.2009.04.010 ］
Gan B Q and Dong Q P . 2022 . An improved optimal algorithm for collision detection of hybrid hierarchical bounding box . Evolutionary Intelligence ， 15 （ 4 ）： 2515 - 2527 ［ DOI： 10.1007/s12065-020-00559-6 http://dx.doi.org/10.1007/s12065-020-00559-6 ］
Garland M and Heckbert P S . 1997 . Surface simplification using quadric error metrics // Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques . New York， USA ： ACM： 209 - 216 ［ DOI： 10.1145/258734.258849 http://dx.doi.org/10.1145/258734.258849 ］
Jin Y X ， Cheng Q F ， Zhang J R ， Qi X ， Ma B and Jia Y . 2020 . Self-collision detection algorithm based on fused DNN and AABB-circular bounding box . Journal of Image and Graphics ， 25 （ 8 ）： 1674 - 1683
靳雁霞 ， 程琦甫 ， 张晋瑞 ， 齐欣 ， 马博 ， 贾瑶 . 2020 . 融合DNN与AABB—圆形包围盒自碰撞检测 . 中国图象图形学报 ， 25 （ 8 ）： 1674 - 1683 ［ DOI： 10.11834/jig.190548 http://dx.doi.org/10.11834/jig.190548 ］
Jin Y X ， Ma B ， Jia Y ， Chen Z X and Lu Y . 2022 . Neural network fusion based cloth collision detection algorithm . Journal of Image and Graphics ， 27 （ 7 ）： 2251 - 2262
靳雁霞 ， 马博 ， 贾瑶 ， 陈治旭 ， 芦烨 . 2022 . 融合神经网络的布料碰撞检测算法 . 中国图象图形学报 ， 27 （ 7 ）： 2251 - 2262 ［ DOI： 10.11834/jig. 210018 http://dx.doi.org/10.11834/jig.210018 ］
Jin Y X ， Shi Z R ， Yang J ， Liu Y B ， Qiao X Y and Zhang L . 2023 . Research on collision detection algorithm between cloth and finely modeled object . Computer Engineering ， 49 （ 7 ）： 269 - 277
靳雁霞 ， 史志儒 ， 杨晶 ， 刘亚变 ， 乔星宇 ， 张翎 . 2023 . 布料与精细建模物体间的碰撞检测算法研究 . 计算机工程 ， 49 （ 7 ）： 269 - 277 ［ DOI： 10.19678/j.issn.1000-3428.0064921 http://dx.doi.org/10.19678/j.issn.1000-3428.0064921 ］
Kim M ， Sung N J ， Kim S J ， Choi Y J and Hong M . 2019 . Parallel cloth simulation with effective collision detection for interactive AR application . Multimedia Tools and Applications ， 78 （ 4 ）： 4851 - 4868 ［ DOI： 10.1007/s11042-018-6063-9 http://dx.doi.org/10.1007/s11042-018-6063-9 ］
Li X X ， Song S B ， Yao J F ， Zhang H Y ， Zhou R Z and Hong Q Q . 2023 . Efficient collision detection using hybrid medial axis transform and BVH for rigid body simulation . Graphical Models ， 128 ： # 101180 ［ DOI： 10.1016/J.GMOD.2023.101180 http://dx.doi.org/10.1016/J.GMOD.2023.101180 ］
Li Y H and Wang Z Y . 2019 . Improvement of collision algorithm based on mixed level bounding box . Journal of East China Jiaotong University ， 36 （ 6 ）： 112 - 118
李玉虎 ， 王宗彦 . 2019 . 基于混合层次包围盒碰撞算法的改进 . 华东交通大学学报 ， 36 （ 6 ）： 112 - 118 ［ DOI： 10.16749/j.cnki.jecjtu.2019.06.017 http://dx.doi.org/10.16749/j.cnki.jecjtu.2019.06.017 ］
Liu C . 2018 . Research and Implementation of Collision Detection Algorithm in Virtual Environment . Nanjing， China ： Nanjing University of Aeronautics and Astronautics， （刘超 . 2018. 虚拟环境中碰撞检测算法的研究和实现 . 南京： 南京航空航天大学）
Liu S J ， Wang C C L ， Hui K C ， Jin X G and Zhao H L . 2007 . Ellipsoid-tree construction for solid objects // Proceedings of 2007 ACM Symposium on Solid and Physical Modeling . Beijing， China ： ACM： 303 - 308 ［ DOI： 10.1145/1236246.1236289 http://dx.doi.org/10.1145/1236246.1236289 ］
Mei H W ， Fan C Y ， Zhang R H and Liu Y G . 2022 . A collision detection and cloth simulation method based on parallel BVH . Forest Chemicals Review， 631 - 647 . ［J/OL］. ［ 2023-10-07 ］. http://www.forestchemicalsreview.com/index.php/JFCR/article/view/745 http://www.forestchemicalsreview.com/index.php/JFCR/article/view/745
Qin Q F and Hu Z G . 2018 . Exact algorithm for finding minimum oriented bounding boxes based on convex hull . Journal of Chinese Computer Systems ， 39 （ 11 ）： 2518 - 2522
秦启飞 ， 胡志刚 . 2018 . 基于凸包的最小有向包围盒生成算法 . 小型微型计算机系统 ， 39 （ 11 ）： 2518 - 2522 ［ DOI： 10.3969/j.issn.1000-1220.2018.11.031 http://dx.doi.org/10.3969/j.issn.1000-1220.2018.11.031 ］
Qu H Y . 2021 . Research on parallel algorithm based on AABB bounding box coordinate chain method . Journal of Physics： Conference Series ， 1732 （ 1 ）： # 012067 ［ DOI： 10.1088/1742-6596/1732/1/012067 http://dx.doi.org/10.1088/1742-6596/1732/1/012067 ］
Sun J R and Lu X M . 2018 . Optimized collision detection algorithm based on hybrid bounding box and intersection of triangles . Computer Engineering and Applications ， 54 （ 19 ）： 198 - 203
孙敬荣 ， 卢新明 . 2018 . 基于混合包围盒与三角形相交的碰撞检测优化算法 . 计算机工程与应用 ， 54 （ 19 ）： 198 - 203 ［ DOI： 10.3778/j.issn.1002-8331.1803-0262 http://dx.doi.org/10.3778/j.issn.1002-8331.1803-0262 ］
Sung M . 2023 . Visibility-based fast collision detection of a large number of moving objects on GPU . IEEE Access ， 11 ： 49456 - 49463 ［ DOI： 10.1109/ACCESS.2023.3277198 http://dx.doi.org/10.1109/ACCESS.2023.3277198 ］
Tang Y ， Yang S S ， Lü M Y ， Zhang M M and Pan Z G . 2013 . Collision detection for cloth based on adaptive enclosing ellipsoids . Journal of Computer-Aided Design and Computer Graphics ， 25 （ 10 ）： 1589 - 1596
唐勇 ， 杨偲偲 ， 吕梦雅 ， 张明敏 ， 潘志庚 . 2013 . 自适应椭球包围盒改进织物碰撞检测方法 . 计算机辅助设计与图形学学报 ， 25 （ 10 ）： 1589 - 1596 ［ DOI： 10.3969/j.issn.1003-9775.2013.10.021 http://dx.doi.org/10.3969/j.issn.1003-9775.2013.10.021 ］
Wang C ， Zhang Z L ， Long Y and Wang S D . 2018 . Improved hybrid bounding box collision detection algorithm . Journal of System Simulation ， 30 （ 11 ）： 4236 - 4243 ［ DOI： 10.16182/j.issn1004731x.joss.201811023 http://dx.doi.org/10.16182/j.issn1004731x.joss.201811023 ］
Wang R ， Hua W ， Xu G F ， Huo Y C and Bao H J . Variational hierarchical directed bounding box construction for solid mesh models ［EB/OL］. ［ 2023-10-07 ］. https://arxiv.org/pdf/2203.10521.pdf https://arxiv.org/pdf/2203.10521.pdf
Xu P and Sun Q Y . 2023 . Virtual reality collision detection based on improved ant colony algorithm . Applied Sciences ， 13 （ 11 ）： # 6366 ［ DOI： 10.3390/app13116366 http://dx.doi.org/10.3390/app13116366 ］
Ye J T ， Ma G H ， Jiang L G ， Chen L ， Li J T ， Xiong G ， Zhang X P and Tang M . 2017 . A unified cloth untangling framework through discrete collision detection . Computer Graphics Forum ， 36 （ 7 ）： 217 - 228 ［ DOI： 10.1111/cgf.13287 http://dx.doi.org/10.1111/cgf.13287 ］
Zhou G Y ， Yuan S D and Luo S M . 2020 . Mesh simplification algorithm based on the quadratic error metric and triangle collapse . IEEE Access ， 8 ： 196341 - 196350 ［ DOI： 10.1109/access.2020.3034075 http://dx.doi.org/10.1109/access.2020.3034075 ］
Zhu Y F ， Meng J ， Xie G H and Ma W J . 2008 . Research on real-time collision detection based on hybrid hierarchical bounding volume . Journal of System Simulation ， 20 （ 2 ）： 372 - 377
朱元峰 ， 孟军 ， 谢光华 ， 马文娟 . 2008 . 基于复合层次包围盒的实时碰撞检测研究 . 系统仿真学报 ， 20 （ 2 ）： 372 - 377
相关文章
相关作者
相关机构
京公网安备11010802024621
