Research on dynamic voxelization-based collision detection in construction scenarios

doi:10.11996/JG.j.2095-302X.2026010204

Abstract

Abstract:

Among all safety accidents in construction scenarios, collision accidents are regarded as one of the most common types of injury. To effectively prevent and monitor the occurrence of collision accidents, the computer graphics analysis technology has been used to assist collision detection and analysis; however, limitations remain in balancing the real-time performance with high precision of detection. To address this, a collision-detection method based on dynamic voxelization was proposed. This method integrated the generation of dynamic spatial voxel tree with the dynamic spherical voxelization calculation of resources to construct a collision detection and analysis mechanism. The core ideas are as follows: ① Based on the crowding-degree threshold, the space was recursively divided to generate a dynamic voxel tree, effectively filtering out non-collision risk areas. ② The side length of voxel units were dynamically calculated according to the relative distance between resources and resource volume, realizing the adaptive adjustment of voxel granularity. ③ Spherical voxels were used instead of traditional cubic voxels to avoid the computational burden of non-axis-aligned detection. ④ A hollowing-out procedure was introduced to eliminate internal invalid voxels, further optimizing detection efficiency. This method can accurately capture resource interactions in complex dynamic construction environments, significantly improving detection accuracy and optimizing computational efficiency. Experimental results showed that compared with traditional methods, the proposed method significantly improved the detection accuracy, with precision and accuracy reaching 94.64% and 96.67%, respectively. In terms of collision detection time, it was more efficient than most existing methods, with a calculation speed increase of at least about 11.36%. At the same time, the study analyzed the impact of key parameters such as voxel-tree depth, root-node size, and voxel side length on performance, and analyzed the consumption of CPU resources and memory resources by the method in scenarios of different scales. The consumption was within an acceptable range, verifying the applicability of the method in construction scenarios. The method provided an effective new idea of information processing for enhancing the intelligent level of construction safety management.

Key words: construction scenarios, computer graphics analysis, dynamic spatial voxel tree, dynamic spherical voxelization, adaptive adjustment, collision detection

CLC Number:

TU712.4

LIN Hao, WU Zhiming, JIN Jilan. Research on dynamic voxelization-based collision detection in construction scenarios[J]. Journal of Graphics, 2026, 47(1): 204-215.

Figures/Tables 21

Fig. 1 Flow chart of collision detection based on dynamic voxelization

Fig. 2 Voxel tree structure and segmentation conditions

Fig. 3 Examples of crowdedness in architectural scenarios ((a) Small quantity of resources, high overall crowding ratio; (b) Small quantity of resources, high local crowding ratio; (c) Extremely large quantity of resources, low crowding ratio; (d) Relatively small quantity of resources, relatively high crowding ratio)

Fig. 4 Dynamic spatial voxel tree example

Fig. 5 Component axis-aligned bounding box

Fig. 6 Schematic diagram of voxel unit collision

Fig. 7 Hollowing example ((a) Special resources with a double-layer structure; (b) Horizontal cross-sectional view after sphere voxelization)

Fig. 8 Simulate the test scenario ((a) Conventional view;(b) South elevation; (c) East elevation; (d) Top view)

Table 1 Resource parameter

资源	长×宽×高/m	资源体积V/m³
挖掘机	6.26×2.56×3.58	7.900
工人	1.71×0.37×1.78	0.090
静态堆料	2.2×2×2.8	6.920
拟建建筑	22×19×18	5 643
拟建建筑(梁构件)	4.2×0.6×0.6	1.512
拟建建筑(柱构件)	0.75×0.75×4.5	2.530
拟建建筑(板构件)	5.5×4.75×0.12	3.140
挖掘机移动速度	0.5 m/s
挖掘机机身回转速度	10 °/s
工人移动速度	1.7 m/s

Table 2 Comparison of volume errors

资源	(1)	(2)	(3)	(4)	(5)	(6)
拟建建筑(梁构件)	0~6.13	0	28.56	0	0	0.91~2.01
静态堆料	3.97~8.82	3.97	31.49	3.97	0.02	0.87~1.95
挖掘机(水平状态)	6.01~13.16	6.01	21.55	6.01	0.06	0.81~1.79
挖掘机(倾斜状态)	11.22~23.11	6.01	21.55	11.22	0.06	0.81~1.79
工人(臂展状态)	12.26~44.29	12.26	39.33	12.26	0.09	1.12~2.93

Fig. 9 The fitting effects of different methods in terms of shape ((a) AABB; (b) OBB; (c) Sphere; (d) VERTICAL-OBB; (e) Triangular mesh; (f) Spherical voxelization)

Fig. 10 Comparison of detection accuracy

Fig. 11 Examples of missed detection and false detection ((a) Missed detection situation; (b) False detection situation)

Table 3 Comparison of detection times/ms

方法	最大值	最小值	绝对差值	平均值
AABB	103.27	99.01	4.26	99.850
OBB	1 347.57	1 283.18	64.39	1 310.600
Sphere	1 295.34	1 192.79	102.55	1 238.170
VERTICAL-OBB	1 245.87	1 123.11	122.76	1 179.900
莫顿码八叉树与VERTICAL-OBB结合的方法^[20]	693.12	604.52	88.60	662.500
八叉树分割与包围盒结合三角网格的方法^[22]	7 635.98	7 682.33	46.35	7 647.820
传统八叉树与动态球状体素结合方法	4 128.39	3 945.67	179.72	4 076.820
本方法	639.13	567.88	71.25	587.230

Fig. 12 The calculation time of the proposed method at different depths

Table 4 The detection time of the proposed method under different root node sizes

根节点尺寸/m	粗碰撞检测时间/ms	精碰撞检测时间/ms	总碰撞检测时间/ms
50	553.20	127.38	680.58
55	475.23	112.00	587.23
60	381.72	182.43	564.15
65	287.88	201.98	489.86
70	247.21	702.35	949.56
75	196.23	927.73	1 123.96

Table 5 The detection time of the proposed method under different side lengths of voxel units

序号	体素单元边长/m		检测时间/ms
序号	挖掘机	工人	检测时间/ms
1	1.2	1.2	212.98
2	0.9	0.9	373.59
3	0.6	0.6	909.87
4	0.3	0.3	8 532.30
5	0.3	1.2	6 169.54
6	0.6	0.9	397.23
7	0.9	0.6	454.79
8	1.2	0.3	2 713.62

Fig. 13 Examples of the proposed method under different side lengths of voxel units ((a) Original view; (b) N=1.2 m, Nx·Ny·Nz=29; (c) N=0.9 m, Nx·Ny·Nz=48; (d) N=0.6 m, Nx·Ny·Nz=135; (e) N=0.3 m, Nx·Ny·Nz=663)

Fig. 14 Accuracy of the proposed method under different voxel unit edge lengths

Fig. 15 Detection time of the proposed method in scenarios with different scales

Fig. 16 Memory usage of the proposed method in scenarios with different scales

References 30

[1]	DAGAN D, ISAAC S. Planning safe distances between workers on construction sites[J]. Automation in Construction, 2015, 50: 64-71. DOI URL
[2]	VAN DEN BERGEN G. Collision detection in interactive 3D environments[M]. London: CRC Press, 2003: 1-277.
[3]	DINAS S, BAÑÓN J M. A literature review of bounding volumes hierarchy focused on collision detection[J]. Ingeniería y Competitividad, 2015, 17(1): 49-62. DOI URL
[4]	李占利, 付敬鼎, 李洪安, 等. 虚拟正畸治疗中的错位牙齿自动排列方法[J]. 图学学报, 2019, 40(2): 225-234. DOI
	LI Z L, FU J D, LI H A, et al. Automatic alignment method for malocclusion in virtual orthodontics treatment[J]. Journal of Graphics, 2019, 40(2): 225-234 (in Chinese).
[5]	CHI S, CALDAS C H. Image-based safety assessment: automated spatial safety risk identification of earthmoving and surface mining activities[J]. Journal of Construction Engineering and Management, 2012, 138(3): 341-351. DOI URL
[6]	KIM K, KIM M. RFID-based location-sensing system for safety management[J]. Personal and Ubiquitous Computing, 2012, 16(3): 235-243. DOI URL
[7]	LUO X C, LI H, HUANG T, et al. A field experiment of workers’ responses to proximity warnings of static safety hazards on construction sites[J]. Safety Science, 2016, 84: 216-224. DOI URL
[8]	YANG B, ZHANG H R, SHEN Z R. Minimum distance calculation method for collision issues in lifting construction scenarios[J]. Journal of Computing in Civil Engineering, 2024, 38(6): 04024041. DOI URL
[9]	HU S B, FANG Y H, GUO H L. A practicality and safety-oriented approach for path planning in crane lifts[J]. Automation in Construction, 2021, 127: 103695. DOI URL
[10]	ZHU A M, ZHANG Z Q, PAN W. Crane-lift path planning for high-rise modular integrated construction through metaheuristic optimization and virtual prototyping[J]. Automation in Construction, 2022, 144: 104434.
[11]	李世林, 李红军. 改进的最小包围球随机增量算法[J]. 图学学报, 2016, 37(2): 166-171. DOI
	LI S L, LI H J. An improved randomized incremental algorithm for generating minimum enclosing ball of discrete point set[J]. Journal of Graphics, 2016, 37(2): 166-171 (in Chinese).
[12]	王佳, 苏鼎丁, 周小平, 等. BIM模型相似度计算方法[J]. 图学学报, 2020, 41(4): 624-631. DOI
	WANG J, SU D D, ZHOU X P, et al. Similarity calculation method of BIM model[J]. Journal of Graphics, 2020, 41(4): 624-631 (in Chinese). DOI
[13]	柳有权, 李婉, 王愿超, 等. 基于碰撞检测强化的实时爆炸视图自动生成算法研究[J]. 图学学报, 2019, 40(2): 235-239. DOI
	LIU Y Q, LI W, WANG Y C, et al. Real-time automatic generation algorithm of exploded view with collision detection enhancement[J]. Journal of Graphics, 2019, 40(2): 235-239 (in Chinese).
[14]	ZHOU Y, ZHANG E D, GUO H L, et al. Lifting path planning of mobile cranes based on an improved RRT algorithm[J]. Advanced Engineering Informatics, 2021, 50: 101376. DOI URL
[15]	LI Y, SHEN X K. A real-time collision detection between virtual and real objects based on three-dimensional tracking of hand[C]// 2010 International Conference on Audio. New York: IEEE Press, 2010: 1346-1351.
[16]	TU C Q, YUAN L Z. Study on collision detection algorithm of hybrid bounding box[C]// 2009 International Forum on Information Technology and Applications. New York: IEEE Press, 2009: 190-192.
[17]	GAN B Q, DONG Q P. An improved optimal algorithm for collision detection of hybrid hierarchical bounding box[J]. Evolutionary Intelligence, 2022, 15(4): 2515-2527. DOI
[18]	程琦甫. 融合深度神经网络的自碰撞检测算法研究[D]. 太原: 中北大学, 2020.
	CHENG Q F. Research on self-collision detection algorithm combined with deep neural network[D]. Taiyuan: North University of China, 2020 (in Chinese).
[19]	马晓萌, 孙红岩, 孙晓鹏. 层次八叉的三维模型并行碰撞检测[J]. 计算机工程与设计, 2019, 40(4): 1077-1084.
	MA X M, SUN H Y, SUN X P. Parallel collision detection of 3D mesh using hierarchical octree[J]. Computer Engineering and Design, 2019, 40(4): 1077-1084 (in Chinese).
[20]	ZHU A M, ZHANG Z Q, PAN W. Developing a fast and accurate collision detection strategy for crane-lift path planning in high-rise modular integrated construction[J]. Advanced Engineering Informatics, 2024, 61: 102509. DOI URL
[21]	胡振中, 张建平, 张新. 基于四维时空模型的施工现场物理碰撞检测[J]. 清华大学学报(自然科学版), 2010, 50(6): 820-825.
	HU Z Z, ZHANG J P, ZHANG X. Construction collision detection for site entities based on 4-D space-time model[J]. Journal of Tsinghua University (Science & Technology), 2010, 50(6): 820-825 (in Chinese).
[22]	张建平, 李丁, 胡振中. 一种集成空间分解与占用的精确碰撞检测算法及其在建筑工程中的应用[J]. 工程力学, 2014, 31(5): 79-85.
	ZHANG J P, LI D, HU Z Z. An accurate collision detection algorithm integrating spatial decomposition and spatial occupancy and its applications in constructions[J]. Engineering Mechanics, 2014, 31(5): 79-85 (in Chinese).
[23]	LI P, WANG Q K, GUO Z, et al. Identifying falling-from-height hazards in building information models: a voxelization-based method[J]. Journal of Construction Engineering and Management, 2022, 148(2): 04021203. DOI URL
[24]	谢震鹏. 基于深度学习和视觉SLAM的语义地图构建及碰撞检测研究[D]. 南宁: 广西大学, 2023.
	XIE Z P. Research on semantic map construction and collision detection based on deep learning and visual slam[D]. Nanning: Guangxi University, 2023 (in Chinese).
[25]	徐进, 柳宁, 李德平, 等. 一种基于抓取簇和碰撞体素的工业零件抓取姿态检测算法[J]. 机器人, 2022, 44(2): 153-166. DOI
	XU J, LIU N, LI D P, et al. A grasping poses detection algorithm for industrial workpieces based on grasping cluster and collision voxels[J]. Robot, 2022, 44(2): 153-166 (in Chinese).
[26]	LIN X, HAN Y, GUO H L, et al. Lift path planning for tower cranes based on environmental point clouds[J]. Automation in Construction, 2023, 155: 105046. DOI URL
[27]	于瑞云, 赵金龙, 余龙, 等. 结合轴对齐包围盒和空间划分的碰撞检测算法[J]. 中国图象图形学报, 2018, 23(12): 1925-1937.
	YU R Y, ZHAO J L, YU L, et al. Collision detection algorithm based on AABB bounding box and space division[J]. Journal of Image and Graphics, 2018, 23(12): 1925-1937 (in Chinese).
[28]	QU H Y. Research on parallel algorithm based on AABB bounding box coordinate chain method[J]. Journal of Physics: Conference Series, 2021, 1732: 012067. DOI
[29]	HU A L, HE Y Y. Research on hybrid collision detection algorithm based on separation distance[J]. Journal of Physics: Conference Series, 2022, 2258: 012011. DOI
[30]	LU S N, XU Z D, WANG B R. Human-robot collision detection based on the improved camshift algorithm and bounding box[J]. International Journal of Control, Automation and Systems, 2022, 20(10): 3347-3360. DOI