PDF(4010 KB)
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
JOURNAL OF NANJING FORESTRY UNIVERSITY ›› 2023, Vol. 47 ›› Issue (5) : 19-27.
PDF(4010 KB)
PDF(4010 KB)
Research on algorithm of collision detection and response to optimize forest simulation
【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, t1 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, t2 was effectively reduced, as was the construction time consumption(t3) and updating time(t4). Both the MBVT and optimized MBVT algorithms reduced the total consumption time, t1 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 t1, t2 and t3 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(t1) and intersection-test time(t2) and no significant correlation with construction time(t3). Conversely, an increase in population and decrease in plant density saw an increase in the total consumption time(t1) and intersection-test time(t2), while there was no significant difference in construction time(t3). 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.
forest simulation / collision detection / collision response / mixed bounding volume hierarchy trees / Chinese fir (Cunninghamia lanceolata) forest
| [1] |
|
| [2] |
|
| [3] |
|
| [4] |
|
| [5] |
|
| [6] |
|
| [7] |
|
| [8] |
郑萍, 赵春江, 张继成. 基于关键点存取的虚拟植物碰撞检测方法的研究[J]. 东北农业大学学报, 2011, 42(8):78-82.
|
| [9] |
李长锋, 郭新宇, 赵春江, 等. 基于空间散列法的虚拟植物碰撞检测算法[J]. 计算机应用与软件, 2009, 26(4):242-245.
|
| [10] |
秦铨, 赵春江, 肖伯祥, 等. 基于AABB-OBB盒的玉米叶片碰撞检测[J]. 农机化研究, 2012, 34(1):177-180.
|
| [11] |
伍艳莲, 汤亮, 曹卫星, 等. 作物可视化中的碰撞检测及响应研究[J]. 计算机科学与探索, 2011, 38(10):263-266,284.
|
| [12] |
We present an interactive tree modeling and deformation system that supports an efficient collision detection and avoidance using a bounding volume hierarchy of sweep surfaces. Starting with conventional tree models (given as meshes), we convert them into sweep surfaces and deform their branches interactively while detecting and avoiding collisions with many other branches. Multiple tree models (sharing the same topology) can be generated with great ease using this sweep‐based approach, and they can serve as a basis for the generation of a multiparameter family of trees. We demonstrate the effectiveness of our approach in an automatic generation of similar trees, the colonization of trees to form a forest, and the tree growth, aging, and withering simulations. Copyright © 2015 John Wiley & Sons, Ltd.
|
| [13] |
|
| [14] |
|
| [15] |
惠刚盈, 胡艳波. 混交林树种空间隔离程度表达方式的研究[J]. 林业科学研究, 2001, 14(1):23-27.
|
| [16] |
|
| [17] |
|
| [18] |
We introduce a 3D tree modeling technique that utilizes examples of real trees to enhance tree creation with realistic structures and fine-level details. In contrast to previous works that use smooth generalized cylinders to represent tree branches, our method generates realistic looking tree models with complex branching geometry by employing an exemplar database consisting of real-life trees reconstructed from scanned data. These trees are sliced into representative parts (denoted as tree-cuts), representing trunk logs and branching structures. In the modeling process, tree-cuts are positioned in space in an intuitive manner, serving as efficient proxies that guide the creation of the complete tree. Allometry rules are taken into account to ensure reasonable relations between adjacent branches. Realism is further enhanced by automatically transferring geometric textures from our database onto tree branches as well as by guided growing of foliage. Our results demonstrate the complexity and variety of trees that can be generated with our method within few minutes. We carry a user study to test the effectiveness of our modeling technique.
|
| [19] |
白静, 张怀清, 刘闽. 合轴分枝树木形态结构三维可视化模拟方法[J]. 林业科学, 2014, 50(12):73-78.
|
| [20] |
高士增, 张怀清, 刘闽, 等. 基于点云的树木枝干形态参数提取技术[J]. 东北林业大学学报, 2014, 42(4):109-114.
|
| [21] |
吴谦, 张怀清, 陈永富, 等. 杉木形态三维可视化模拟技术研究[J]. 林业科学研究, 2010, 23(1):59-64.
|
| [22] |
朱念福, 张怀清, 崔泽宇, 等. 基于空间结构的杉木枝下高可视化模拟研究[J]. 南京林业大学学报(自然科学版), 2022, 46(1):51-57.
|
| [23] |
崔泽宇, 张怀清, 左袁青, 等. 杉木三维模型各方向枝下高分布研究[J]. 南京林业大学学报(自然科学版), 2022, 46(1):81-87.
|
| [24] |
|
| [25] |
黄洪宇, 陈崇成, 邹杰, 等. 基于地面激光雷达点云数据的单木三维建模综述[J]. 林业科学, 2013, 49(4):123-130.
|
| [26] |
刘清旺, 李世明, 李增元, 等. 无人机激光雷达与摄影测量林业应用研究进展[J]. 林业科学, 2017, 53(7):134-148.
|
| [27] |
张兴邦, 胡滨, 汤亮, 等. 基于改进包围盒树和 GPU 的水稻群体叶片间快速碰撞检测[J]. 农业工程学报, 2018, 34(1):171-177.
|
/
| 〈 |
|
〉 |
