Research on algorithm of collision detection and response to optimize forest simulation

doi:10.12302/j.issn.1000-2006.202208020

JOURNAL OF NANJING FORESTRY UNIVERSITY ›› 2023, Vol. 47 ›› Issue (5): 19-27.doi: 10.12302/j.issn.1000-2006.202208020

Research on algorithm of collision detection and response to optimize forest simulation

WANG Linlong¹^,²^,³(), ZHANG Huaiqing¹^,³^,^*(), YANG Tingdong¹, ZHANG Jing¹, LEI Kexin¹, CHEN Chuansong⁴, ZHANG Huacong¹, LIU Yang¹, CUI Zeyu¹, ZUO Yuanqing¹

1. Research Institute of Forest Resource Information Techniques, CAF, Beijing 100091, China
2. Research Institute of Forestry Policy and Information, CAF, Beijing 100091, China
3. Key Laboratory of Forestry Remote Sensing and Information Technology, National Forestry and Grassland Administration, CAF, Beijing 100091, China
4. Experimental Center of Subtropical Forestry,CAF, Fenyi 336600, China

Received:2022-08-09 Revised:2022-10-04 Online:2023-09-30 Published:2023-10-10

Abstract

Abstract:

【Objective】 Research into virtual forest collision is hampered by redundant detection objects and simple collision response modes. Our study addresses the technical bottlenecks of high time-cost collision-detection algorithms (aiming to achieve a rapid detection of collisions) and a lack of interaction between the response mode and environmental factors (in favor of real response in virtual forest scenes). 【Method】 We studied a pure-planted Chinese fir (Cunninghamia lanceolata) forest on Shanxia Farm, based at the Experimental Center of Subtropical Forestry in the Chinese Academy of Forestry. Our study compared the efficiency of three methods for the collision detection: an axis-aligned bounding box (AABB) algorithm;a mixed bounding volume hierarchy tree (MBVT) algorithm and a MBVT algorithm optimized using a ‘Finding-the-Four-Closest-Trees’ method, to understand the effect of population size and plant density on collision-detection efficiency and to explore the feasibility of collision response under the strategy proposed in our study.【Result】The total consumption time, t₁ for our optimized ‘Finding the Four Closest Trees’ method was approximately 29% that of the MBVT algorithm: 13.75 ms shorter. Compared with the BVH, the cross-test time consumption, t₂ was effectively reduced, as was the construction time consumption(t₃) and updating time(t₄). Both the MBVT and optimized MBVT algorithms reduced the total consumption time, t₁ was approximately 73% and 81% that of a single BVH tree AABB by 124.93 and 138.68 ms, respectively. Population was positively correlated with t₁, t₂ and t₃ of the BVH tree: total consumption time, intersection-test time, and construction time. There was a negative correlation between the density of different plants and the total consumption time(t₁) and intersection-test time(t₂) and no significant correlation with construction time(t₃). Conversely, an increase in population and decrease in plant density saw an increase in the total consumption time(t₁) and intersection-test time(t₂), while there was no significant difference in construction time(t₃). Compared with traditional collision response models, the proposed collision response algorithm took into account phototaxis and more realistically simulated a virtual scene of Chinese fir. The virtual scene had a frame rate of 8.6 frames per second and an accuracy of 100%. 【Conclusion】 Improving a MBVT algorithm using our ‘Finding the Four Closest Trees’ can optimize the number of collision detection objects in mixed bounding box hierarchy trees, reducing the consumption time of BVH cross tests and construction to improve collision detection efficiency in a virtual forest of Chinese fir. A collision response strategy for adjacent trees, which accounts for phototaxis, can solve the problem of collision response without interacting with environmental factors in virtual forest scenes, improving the realism of a Chinese fir virtual forest with the Lambert model and collision response function.

Key words: forest simulation, collision detection, collision response, mixed bounding volume hierarchy trees, Chinese fir (Cunninghamia lanceolata) forest

CLC Number:

S750

WANG Linlong, ZHANG Huaiqing, YANG Tingdong, ZHANG Jing, LEI Kexin, CHEN Chuansong, ZHANG Huacong, LIU Yang, CUI Zeyu, ZUO Yuanqing. Research on algorithm of collision detection and response to optimize forest simulation[J]. JOURNAL OF NANJING FORESTRY UNIVERSITY, 2023, 47(5): 19-27.

Figures/Tables 5

Fig. 1

Table 1

Fig. 2

Fig. 3

Fig.4

References 27

[1]	WANG M N, CAO J Q. A review of collision detection for deformable objects[J]. Comput Animat Virtual Worlds, 2021, 32(5):e1987.DOI: 10.1002/cav.1987.
[2]	CHOI A R, SUNG M Y. Performance improvement of haptic collision detection using subdivision surface and sphere clustering[J]. PLoS One, 2017, 12(9):e0184334.DOI: 10.1371/journal.pone.0184334.
[3]	MOORE M, WILHELMS J. Collision detection and response for computer animationr3[C]// Proceedings of the 15th annual conference on computer graphics and interactive techniques-SIGGRAPH’88.Not Known. New York: ACM Press, 1988:289-298.DOI: 10.1145/54852.378528.
[4]	LIN M C, GOTTSCHALK S. Collision detection between geometric models: a survey visual computer, 1998, 11(10):542-561.DOI:10.1007/BF02434040.
[5]	JIMÉNEZ P, THOMAS F, TORRAS C. 3D collision detection:a survey[J]. Comput Graph, 2001, 25(2):269-285.DOI: 10.1016/S0097-8493(00)00130-8.
[6]	WALD I. On fast construction of SAH-based bounding volume hierarchies[C]// 2007 IEEE Symposium on Interactive Ray Tracing.September 10-12,2007.Ulm:IEEE, 2007:33-40.DOI: 10.1109/rt.2007.4342588.
[7]	MADERA F A, DAY A M, LAYCOCK S D. A hybrid bounding volume algorithm to detect collisions between deformable objects[C]// 2009 Second International Conferences on Advances in Computer-Human Interactions. February 1-7,2009,Cancun,Mexico:IEEE, 2009:136-141.DOI: 10.1109/ACHI.2009.13.
[8]	郑萍, 赵春江, 张继成. 基于关键点存取的虚拟植物碰撞检测方法的研究[J]. 东北农业大学学报, 2011, 42(8):78-82.
	ZHENG P, ZHAO C J, ZHANG J C. Study on virtual plant collision detection method based on save and access of key point[J]. J Northeast Agric Univ, 2011, 42(8):78-82.DOI: 10.3969/j.issn.1005-9369.2011.08.015.
[9]	李长锋, 郭新宇, 赵春江, 等. 基于空间散列法的虚拟植物碰撞检测算法[J]. 计算机应用与软件, 2009, 26(4):242-245.
	LI C F, GUO X Y, ZHAO C J, et al. Spatial hashing based collision detection algorithm for virtual plants[J]. Comput Appl Softw, 2009, 26(4):242-245.DOI: 10.3969/j.issn.1000-386X.2009.04.082.
[10]	秦铨, 赵春江, 肖伯祥, 等. 基于AABB-OBB盒的玉米叶片碰撞检测[J]. 农机化研究, 2012, 34(1):177-180.
	QIN Q, ZHAO C J, XIAO B X, et al. Collision detection for maize leaves based on AABB-OBB bounding volumes[J]. J Agric Mech Res, 2012, 34(1):177-180.DOI: 10.3969/j.issn.1003-188X.2012.01.043.
[11]	伍艳莲, 汤亮, 曹卫星, 等. 作物可视化中的碰撞检测及响应研究[J]. 计算机科学与探索, 2011, 38(10):263-266,284.
	WU Y L, TANG L, CAO W X, et al. Collision detection and response in crop visualization[J]. J Front Comput Sci Technol, 2011, 38(10):263-266,284.DOI: 10.3969/j.issn.1004-731X.2007.07.023.
[12]	KIM Y J, WOO J H, KIM M S, et al. Interactive tree modeling and deformation with collision detection and avoidance[J]. Comput Animat Virtual Worlds, 2015, 26(3/4):423-432.DOI: 10.1002/cav.1661.
[13]	XIAO B, GUO X, WANG C, et al. Collision detection based on biomimetic pattern recognition for virtual plant[J]. Icic Express Letters, 2015, 9(5): 1413-1418.
[14]	TANG L, SONG W G, HOU T C, et al. Collision detection of virtual plant based on bounding volume hierarchy:a case study on virtual wheat[J]. J Integr Agric, 2018, 17(2):306-314.DOI: 10.1016/S2095-3119(17)61769-6.
[15]	惠刚盈, 胡艳波. 混交林树种空间隔离程度表达方式的研究[J]. 林业科学研究, 2001, 14(1):23-27.
	HUI G Y, HU Y B. Measuring species spatial isolation in mixed forests[J]. For Pesearch, 2001, 14(1):23-27.DOI: 10.3321/j.issn:1001-1498.2001.01.004
[16]	DING W L, WAN Z X, XU Y, et al. New collision detection method for simulating virtual plant populations[J]. Int J Agric Biol Eng, 2019, 12(6):156-161.DOI: 10.25165/j.ijabe.20191206.4888.
[17]	COMMONER B, LIPKIN D. The application of the beer-lambert law to optically anisotropic systems[J]. Science, 1949, 110(2845):41-43.DOI: 10.1126/science.110.2845.41-a. pmid: 17735370
[18]	XIE K, YAN F L, SHARF A, et al. Tree modeling with real tree-parts examples[J]. IEEE Trans Vis Comput Graph, 2016, 22(12):2608-2618.DOI: 10.1109/TVCG.2015.2513409. pmid: 26731769
[19]	白静, 张怀清, 刘闽. 合轴分枝树木形态结构三维可视化模拟方法[J]. 林业科学, 2014, 50(12):73-78.
	BAI J, ZHANG H Q, LIU M. Three-dimensional visual simulation of sympodial branching trees morphological architecture[J]. Sci Silvae Sin, 2014, 50(12):73-78.DOI: 10.11707/j.1001-7488.20141210.
[20]	高士增, 张怀清, 刘闽, 等. 基于点云的树木枝干形态参数提取技术[J]. 东北林业大学学报, 2014, 42(4):109-114.
	GAO S Z, ZHANG H Q, LIU M, et al. Morphological parameters extraction of tree branches based on point cloud[J]. J Northeast For Univ, 2014, 42(4):109-114.DOI: 10.3969/j.issn.1000-5382.2014.04.025.
[21]	吴谦, 张怀清, 陈永富, 等. 杉木形态三维可视化模拟技术研究[J]. 林业科学研究, 2010, 23(1):59-64.
	WU Q, ZHANG H Q, CHEN Y F, et al. Study on visual simulation technology of Cunninghamia lanceolata morphological characters[J]. For Res, 2010, 23(1):59-64.DOI: 10.3969/j.issn.1004-731X.2007.21.027.
[22]	朱念福, 张怀清, 崔泽宇, 等. 基于空间结构的杉木枝下高可视化模拟研究[J]. 南京林业大学学报(自然科学版), 2022, 46(1):51-57.
	ZHU N F, ZHANG H Q, CUI Z Y, et al. Visual simulation of Chinese fir under branch height in consideration of spatial structure[J]. J Nanjing For Univ (Nat Sci Ed), 2022, 46(1):51-57.DOI: 10.12302/j.issn.1000-2006.202010037.
[23]	崔泽宇, 张怀清, 左袁青, 等. 杉木三维模型各方向枝下高分布研究[J]. 南京林业大学学报(自然科学版), 2022, 46(1):81-87.
	CUI Z Y, ZHANG H Q, ZUO Y Q, et al. The distribution of under branch heights in various directions of the three-dimensional Chinese fir model[J]. J Nanjing For Univ (Nat Sci Ed), 2022, 46(1):81-87.DOI: 10.12302/j.issn.1000-2006.202110017.
[24]	COTÉ J F, WIDLOWSKI J L, FOURNIER R A, et al. The structural and radiative consistency of three-dimensional tree reconstructions from terrestrial lidar[J]. Remote Sens Environ, 2009, 113(5):1067-1081.DOI: 10.1016/j.rse.2009.01.017.
[25]	黄洪宇, 陈崇成, 邹杰, 等. 基于地面激光雷达点云数据的单木三维建模综述[J]. 林业科学, 2013, 49(4):123-130.
	HUANG H Y, CHEN C C, ZOU J, et al. Tree geometrical 3D modeling from terrestrial laser scanned point clouds:a review[J]. Sci Silvae Sin, 2013, 49(4):123-130.DOI: 10.11707/j.1001-7488.20130418.
[26]	刘清旺, 李世明, 李增元, 等. 无人机激光雷达与摄影测量林业应用研究进展[J]. 林业科学, 2017, 53(7):134-148.
	LIU Q W, LI S M, LI Z Y, et al. Review on the applications of UAV-based LiDAR and photogrammetry in forestry[J]. Sci Silvae Sin, 2017, 53(7):134-148.DOI: 10.11707/j.1001-7488.20170714.
[27]	张兴邦, 胡滨, 汤亮, 等. 基于改进包围盒树和 GPU 的水稻群体叶片间快速碰撞检测[J]. 农业工程学报, 2018, 34(1):171-177.
	ZHANG X B, HU B, TANG L, et al. Fast collision detection for rice leaf population based on improved bounded box tree and GPU[J]. Transactions of the Chinese Society of Agricultural Engineering, 2018, 34(1): 171-177.

Metrics

Comments

www.nldxb.njfu.edu.cn

Edited ＆ Published by Editorial Department of Nanjing Forestry University(Natural Sciences Edition)
Address： No.159 Longpan Road,Nanjing 210037 Jiangsu,P.R.China
E-mail ：xuebao@njfu.edu.cn , xuebao@njfu.com.cn
Telephone +86-25-85428247,85427076
Distributed by China International Book Trading Corporation P.O. Box 399, Beijing ,P.R. China

方法 method	t₁	t₂	t₃	t₄
单一包围盒树算法 (AABB) single axis-aligned bounding tree	172.27	9.33	79.73	83.21
混合包围盒树算法(MBVT) mixed bounding volume hierarchy tree	47.34	27.03	15.94	4.37
引入最近4株树法的MBVT优化算法 MBVT optimized by introducing Find- Closest-Four-Trees algorithm	33.59	19.66	10.32	3.61

Research on algorithm of collision detection and response to optimize forest simulation

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 27

Related Articles 5

Recommended Articles

Metrics

Comments

Author

Reader

Reviewer

[1]	HU Wenjie, CUI Hongxia, WANG Xiaorong, LEI Jingpin, PAN Lei, TANG Wanpeng, PANG Hongdong, YUAN Xiujin. Structure characteristics of Pinus massoniana secondary forest in the Three Gorges Reservoir area [J]. JOURNAL OF NANJING FORESTRY UNIVERSITY, 2019, 62(03): 67-76.
[2]	PENG Hui, ZHOU Hongmin, HUI Gangying. Bivariate distribution of spatial structure of a Cunninghamia lanceolate coppice forest [J]. JOURNAL OF NANJING FORESTRY UNIVERSITY, 2017, 60(04): 136-140.
[3]	OU Jiande, WU Zhizhuang. Early judgment and disposal technology for stem form abnormity of Taxus chinensis var. mairei plantation [J]. JOURNAL OF NANJING FORESTRY UNIVERSITY, 2017, 60(03): 95-99.
[4]	XU Da，LIU Anxing，WENG Weisong，WEN Xiaorong，TAN Ying. Study on optimal goal programming of the countylevel forest comprehensive benefit based on AHP [J]. JOURNAL OF NANJING FORESTRY UNIVERSITY, 2013, 56(05): 70-74.
[5]	ZHANG Xi. Effects on Slope Cropland Site and Site Classification of Guizhou Karst Upland [J]. JOURNAL OF NANJING FORESTRY UNIVERSITY, 2003, 46(06): 98-102.