An efficient adaptive space partitioning algorithm for electromagnetic scattering calculation of complex 3D models

doi:10.23919/JSEE.2021.000092

Journal of Systems Engineering and Electronics ›› 2021, Vol. 32 ›› Issue (5): 1071-1082.doi: 10.23919/JSEE.2021.000092

• ELECTRONICS TECHNOLOGY • Previous Articles Next Articles

An efficient adaptive space partitioning algorithm for electromagnetic scattering calculation of complex 3D models

Minjie HUANG¹(), Yaoming ZHOU^1,*(), Yongchao WANG¹(), Zhongtie LIU²()

¹ School of Aeronautic Science and Engineering, Beihang University, Beijing 100191, China
² Key Laboratory of Complex Aviation System Simulation, Beijing 100076, China

Received:2019-11-12 Online:2021-10-18 Published:2021-11-04
Contact: Yaoming ZHOU E-mail:huangminjie@buaa.edu.cn;zhouyaoming@buaa.edu.cn;wangyongchao@buaa.edu.cn;liuzhongtie@ase.buaa.edu.cn
About author:|HUANG Minjie was born in 1982. He received his Ph.D. degree from Beihang University, Beijing, China, in 2008. He is a lecturer in Beihang University. His research interests include design of microwave filters and computational electromagnetics. E-mail: huangminjie@buaa.edu.cn||ZHOU Yaoming was born in 1987. He received his Ph.D. degree from Beihang University, Beijing, China, in 2013. He is now a researcher in Beihang University. His research interests include aircraft design, and helicopter flight control. E-mail: zhouyaoming@buaa.edu.cn||WANG Yongchao was born in 1992. He received his B.S. degree from Beihang University, Beijing, China, in 2018, where he is currently working towards his Ph.D. degree. His research interests include avionics and wireless communication. E-mail: wangyongchao@buaa.edu.cn||LIU Zhongtie was born in 1980. He received his Ph.D. degree from Beihang University, Beijing, China, in 2011. He is now working as a senior engineer in Key Laboratory of Complex Aviation System Simulation. His research interests include aircraft design and computational electromagnetics. E-mail: liuzhongtie@ase.buaa.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (61601015; 91538204)

Abstract

Abstract:

The space partitioning algorithm based on the rounding and addressing operations has been proved to be an efficient space partitioning algorithm with the potential for real-time calculation. An improvement on this kind of space partitioning algorithms for solving complex 3D models is presented. Numerical examples show that the efficiency of the improved algorithm is better than that of the original method. When the size of most target elements is smaller than the size of spatial grids, the efficiency of the improved method can be more than four times of that of the original method. An adaptive method of space partitioning based on the improved algorithm is developed by taking the surface element density or the curvature as the threshold for deep partitioning and conducting the deep partitioning using the octree method. A computer program implementation for applying the method in some typical applications is discussed, and the performance in terms of the efficiency, reliability, and resource use is evaluated. Application testing shows that the results of the adaptive spacing partitioning are more convenient for the follow-up use than that of the basic uniform space partitioning. Furthermore, when it is used to calculate the electromagnetic scattering of complex targets by the ray tracing (RT) method, the adaptive space partitioning algorithm can reduce the calculation time of the RT process by more than 40% compared with the uniform space segmentation algorithm.

Key words: adaptive space partitioning, computer graphics, binary space partitioning, ray tracing (RT) method, stealth technology

Minjie HUANG, Yaoming ZHOU, Yongchao WANG, Zhongtie LIU. An efficient adaptive space partitioning algorithm for electromagnetic scattering calculation of complex 3D models[J]. Journal of Systems Engineering and Electronics, 2021, 32(5): 1071-1082.

Figures/Tables 20

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Table 1

Fig 7

Fig 8

Fig 9

Fig 10

Fig 11

Table 2

Fig 12

Fig 13

Fig 14

Table 3

Fig 15

Fig 16

Table 4

References 23

1	SHEN X L, WU Q Hybrid collision detection algorithm based on bounding box and spatial decomposition. Computer Engineering, 2012, 38 (6): 256- 258.
2	GE Y K, LI R, LI H L Study of point cloud data reduction algorithm integrating space partitioning and curvature. Application Research of Computers, 2012, 29 (5): 1998- 2000.
3	DONG F, CAI W L, SHI J Y Volume rendering of irregular data field based on space segmentation. Journal of Computer-Aided & Computer Graphics, 1997, 9 (3): 241- 248.
4	GAO R, CHENG L L, HU X Indoor positioning method based on space division using passive RFID. Application Research of Computers, 2012, 29 (1): 184- 188.
5	LIONEL M N, YUN H L, YIU C L LANDMARC: indoor location sensing using active RFID. Proc of the IEEE International Conference on Pervasion Computing and Communications, 2003, 407- 415.
6	FRANK W. Adaptive multi-level uniform space partitioning algorithm for high-frequency electromagnetics simulations based on ray tracing. Proc. of the International Conference on Numerical Electromagnetic Modeling and Optimization for RF, Microwave and Terahertz Applications, 2014. DOI: 10.1109/NEMO.2014.6995667.
7	LEE K S Position-dependent crosstalk cancellation using space partitioning. IEEE Trans. on Audio, Speech, and Language Processing, 2013, 21 (6): 1228- 1239. doi: 10.1109/TASL.2013.2248713
8	ZHOU S H, LIU H W Space-partition-based target detection for distributed MIMO radar. IEEE Trans. on Aerospace and Electronic Systems, 2013, 49 (4): 2717- 2729. doi: 10.1109/TAES.2013.6621848
9	REN C A, LI Z Y, CHEN Y W. Improved multi-objective evolutionary algorithm based on objective-space-divided. Application Research of Computers, 2010, 27(4): 1311−1314. (in Chinese)
10	TAMARA J, ARMIN R M, CHENTAN T. A novel space partitioning algorithm to improve current practices in facility placement. IEEE Trans. on Systems, Man, and Cybernetics-Part A: Systems and Humans 2012, 42(5): 1194−1205.
11	FUCHS H, KEDEM Z, NAYLOR B On visible surface generation by a priori tree structures. Computer Graphics, 1980, 14 (1): 124- 133.
12	VERONICA V, FERRAN M, PHILIPPE S Binary partition trees for object detection. IEEE Trans. on Image Processing, 2008, 17 (11): 2201- 2216. doi: 10.1109/TIP.2008.2002841
13	MICHEL S, KLAUS D Content adaptive mesh representation of images using binary space partitions. IEEE Trans. on Image Processing, 2009, 18 (5): 1069- 1079. doi: 10.1109/TIP.2009.2016148
14	HUANG M, ZHANG H C, LI C Algorithm for finding k-nearest neighbors based on octree segmentation in space. Journal of Computer Applications, 2008, 28 (8): 2047- 2051.
15	YANG J J, ZHOU J Z, FANG C X Multi-objective particle swarm optimization based on adaptive grid algorithms. Journal of System Simulation, 2008, 22 (21): 5843- 5847.
16	SHI F Z CAGD & NURBS. Beijing: Higher Education Press, 2001, 131- 135.
17	ERICKSON J. Local polyhedra and geometric graphs. Computational Geometry: Theory and Applications, 2005, 31(1/2): 101−125.
18	LIU Z T, MA D L Efficient arithmetic for space partitioning. Journal of Beijing University of Aeronautics and Astronautics, 2010, 36 (4): 434- 437.
19	LIU X Y, DENG Y D, NI Y F FastTree: a hardware KD-tree construction acceleration engine for real-time ray tracing. Proc. of the Design, Automation & Test in Europe Conference & Exhibition, 2015, 1595- 1598.
20	GAO Y Y, ZHOU L, CHEN Y H A hardware acceleration engine for ray tracing. Proc. of the IEEE 17th International Conference on Computational Science and Engineering, 2014, 505- 508.
21	MENG X, GUO L X, WEI Y W An accelerated ray tracing method based on the TSM for the RCS prediction of 3-D large-scale dielectric sea surface. IEEE Antennas and Wireless Propagation Letters, 2015, 14, 233- 236. doi: 10.1109/LAWP.2014.2360705
22	GHANBARABAD S J H, ASADI Z, MOHTASHAMI V Adaptive super-sampling of rays for accurate calculation of physical optics scattering from parametric surfaces. IEEE Antennas and Wireless Propagation Letters, 2018, 17 (6): 960- 963. doi: 10.1109/LAWP.2018.2827042
23	CONG Z, HE Z, CHEN R S An efficient volumetric SBR method for electromagnetic scattering from in-homogeneous plasma sheath. IEEE Access, 2019, 7, 90162- 90170. doi: 10.1109/ACCESS.2019.2927264

Model	Size/m	Number of triangles	Unit cube	Time consumption/s
Model	Size/m	Number of triangles	Unit cube	BSP	[18]	This paper
1	15.46×10.75×3.51	238 641	20×20×10	76.4	0.84	0.18
			40×40×20	150.3 s	1.15	0.19
			20×8×8	?	1.1*	0.18*
2	21.49×14.7× 4.8	260 489	20×20×5	75.5	0.91	0.18
			40×40×10	145.1	1.28	0.19
			20×8×8	?	1.2*	0.18*

Statistical item		Model 1	Model 2
Number of triangles		238641	260489
Statistical data of subspaces in the bottom layer	Quantity of grids in the bottom layer	54264	44728
	Average quantity of triangles	8.64	8.36
	Standard deviation	9.17	10.35
	Maximum quantity of triangles	299	313
Time consumption	Uniform space partition/s	0.19(40×40×20)	0.19(40×40×20)
Time consumption	Adaptive space partition/s	2.34	2.36
Memory occupancy	Uniform space partition/MB	1.79	1.67
	Adaptive space partition/MB	8.11	6.43
	Geometry information of model/MB	21.8	23.8

Comparison item	Uniform space partition	Adaptive space partition
Quantity of grids	40×40×20	44728 (in the bottom layer)
Time consumption of RT/s	12.1	6.1
Number of Ray tubes	7.7×10⁵	7.7×10⁵
Maximum bouncing times of the rays	12	12
Total reflection times	11845	11845

Comparison item	Uniform space partition	Adaptive space partition
Quantity of grids	30×30×10	13406 (in the bottom layer)
Time consumption/s	2 419	1 426

An efficient adaptive space partitioning algorithm for electromagnetic scattering calculation of complex 3D models

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 20

References 23

Related Articles 0

Recommended Articles

Metrics

Comments