An Adaptive and Highly Accurate FDTD Mesh Generation Technique for Objects with Complex Edge Structures

Chunhui Mou $^{1}$ and Juan Chen $^{1, 2}$

¹School of Information and Communications Engineering
Xi’an Jiaotong University, Xi’an 710049, China
mouchunhui@163.com

²Shenzhen Research School
Xi’an Jiaotong University, Shenzhen 518057, China
chen.juan.0201@mail.xjtu.edu.cn

Submitted On: October 14, 2021; Accepted On: February 14, 2022

Abstract

In this paper, a triangular facets based, highly accurate, and adaptive finite-difference time-domain (FDTD) mesh generation technique is presented. There are two innovations in the implementation of this technique. One is adaptive mesh lines placement method. The mesh lines are automatically set to be dense where the object has fine structure and sparse where the object has rough structure based on the incremental placement of the triangular mesh vertices. The other is ray column tracing method. Ray columns in the normal direction of the coordinate plane are employed to intersect the surface facets to make the mesh generation results highly accurate. The generating FDTD results of the numerical examples show that the proposed technique can well-restore objects with complex edge structures. The simulation results are in good agreement with the theoretical results.

Keywords: Adaptive, FDTD, mesh generation, ray column tracing.

I. INTRODUCTION

The finite-difference time-domain (FDTD) algorithm is implemented by calculating the electric and magnetic fields on each Yee cell [1-3]. The Yee cells, whose sizes and related material parameters are simultaneously employed in the iterative formulas of the FDTD algorithm, must be established before FDTD simulation. Unlike unstructured meshes [4, 5], which can be easily obtained by computer-aided design (CAD) or some open source programs, there are relatively few ways to obtain the structured cuboid meshes. Therefore, the transformation from unstructured meshes to structured meshes has attracted much attention [6-13].

Since the ray tracing method (RTM) was proposed by Sun in 1993 [6], it has been widely used in mesh generation for FDTD simulation. The RTMs proposed before mainly casted single ray to intersect the surface facets for each two-dimensional (2D) grid on the projection plane. This kind of processing may lead to missing mapping at the edge of the target. In practice, edge structure of a target may have a great influence on its overall electromagnetic performance [14-16]. For example, slot design at the edge of patch antennas can not only realize miniaturization but also reduce antenna radar cross section (RCS). In addition, the biologically inspired antennas usually have complex edge structures. Therefore, the precision of edge mesh conversion needs to beconsidered.

For complex objects, if a uniform mesh generation method (UMGM) is employed, there will be a problem of large number of mesh cells, compared with employing a non-uniform mesh generation method (NUMGM). The increase in the number of mesh cells caused by using the UMGM than the NUMGM then can result in problems such as high memory consumption and long simulation time. Therefore, in contrast to the UMGM, the NUMGM is more suitable for complex objects mesh generation. A key step in NUMGM is to place proper mesh lines [[12], 17-20]. In reference [12], a non-uniform mesh lines placement method is presented for multi-objectscenarios. An NUMGM for overlapping objects wasproposed by Kanai in reference [17]. The NUMGMs proposed before were implemented based on the condition that the bounding box of each object was known. In other words, they solved a complex problem by breaking it down into a group of individual objects. The non-uniform mesh lines were placed by setting reasonable grid sizes in the overlapping part and the adjacent part of the objects. However, in the field of electromagnetism, some electromagnetic devices, such as multi-frequency antenna, broad band frequency selective surface (FSS), are too complex to be easily and quickly separated into several independent objects. Therefore, an adaptive mesh lines placement method based on the incremental placement of the triangular mesh vertices is proposed in this paper. Obviously, the choice of triangulation in the preparation of the triangulated mesh is critical to the performance of the proposed NUMGM. We choose Altair FEKO v2019.1 [21] to get the triangular meshes. Since FEKO is a mature commercial electromagnetic simulation software and has been globally used in high-frequency electromagnetic simulation for over 20 years, the triangular mesh generation results of it arereliable.

In this paper, an adaptive FDTD mesh generation technique is proposed. This technique presents high accuracy in FDTD mesh generation, especially at the edge part of the target. Two key methods are employed to achieve this capability. One is ray column tracing method (RCTM), and the other is adaptive mesh lines placement method. Numerical examples are given and discretized. The simulation and theoretical results show that the proposed mesh generation technique can properly restore the target with fine structure, especially at the edge part.

II. RAY COLUMN TRACING METHOD

For RTM, generally, a single ray perpendicular to a grid on the coordinate plane is employed to intersect the plane where the triangular facet is located [6]. The triangular facets mentioned in this section are obtained by .STL files exported from CAD software. The specific operation is to build a model in CAD and save it as. STL format. As shown in Figure 1, the shaded part without slash lines are the Yee cells transformed by RTM, while the shaded part with slash lines are the Yee cells of missing marks.

Figure 1: The transformed Yee cells of the 2D triangle by RTM.

In this paper, RCTM is proposed. For each grid on the coordinate plane, multiple rays in the normal direction are selected to intersect the facets in one tracing process. Taking one triangular facet as an example, the RCTM is described in detail as follows.

First, project the triangular facet ABC. onto XOY plane and denote its projection as DEF, as shown in Figure 2.

Figure 2: Triangular facet ABC and its projection DEF.

Second, find out the maximum and minimum values of triangle DEF in the x-direction and confirm the starting and ending mesh numbers in the x-direction accordingly. Denote the starting number as $x_{s}$ and the ending number as $x_{e}$ . Taking the grids numbered i in the x-direction as examples, calculate the intersection points of their two adjacent grid lines and the three sides of triangle DEF. Determine the maximum and minimum y values of these intersection points and mark the grids between them as shown in Figure 3(a). In this way, the triangle DEF is discretized as shown in Figure 3(b).

Figure 3: 2D ray column tracing method. (a) The discretization result of grids numbered i in the x-direction and (b) the discretization result of the triangle DEF.

Third, for the grids inside triangle DEF, obtain the intersections of the rays perpendicular to the four nodes of each grid and triangle ABC, respectively. For the grids at the edge of triangle DEF, figure out the intersection points of their adjacent grid lines and the three sides of triangle DEF first and then obtain the intersections of the rays perpendicular to these points and triangle ABC severally. The three-dimensional (3D) RCTM is shown in Figure 4.

Figure 4: 3D ray column tracing method: (a) grids inside DEF and (b) grids at the edge of DEF.

Take a hexagonal star ring as an example to illustrate the validity of the proposed RCTM in edge mesh generation. The hexagonal star ring is shown in Figure 5(a), and its triangulation is shown in Figure 5(b).

Figure 5: The structure and triangulation of the hexagonal star ring: (a) the structure and (b) the triangulation.

Figures 6 and 7 show the resulting Yee cells of the hexagonal star ring obtained by RTM and RCTM, respectively. The mesh size in Figure 6 is 5 mm, and the mesh size in Figure 7 is 2 mm.

Figure 6: The discretization results of the hexagonal star ring when the grid size is 5 mm: (a) by RCTM and (b) by RTM.

Figure 7: The discretization results of the hexagonal star ring when the grid size is 2 mm: (a) by RCTM and (b) by RTM.

It can be seen from Figure 6 that, when the mesh size is 5 mm, there are obvious missing marks in the discretization result obtained by RTM. Although the Yee cells transformed by RCTM are not completely appropriate to the original structure, the accuracy of RCTM is obviously improved compared with that of RTM. When the mesh size is 2 mm, as shown in Figure 7, both RCTM and RTM perform better. However, the transformation result of RCTM is closer to the original shape and size of the target than that of RTM.

III. ADAPTIVE MESH LINES PLACEMENT METHOD

In the process of structured cuboid mesh generation, the first step is to create efficient structured mesh lines, which must satisfy the numerical dispersion requirement of the FDTD method and can be adapted to geometric models. These mesh lines can provide spatial coordinate information for subsequent material mapping. Taking an object with fine structure into account, if it is discretized by uniform mesh, there will be a problem of huge mesh quantity. This problem can be solved by using non-uniform meshes. In this paper, an adaptive mesh lines placement method is proposed, which can set mesh lines automatically according to the mechanical structure and the electromagnetic characteristics of thetarget.

In the implementation of the adaptive mesh lines placement method, the object is modeled and meshed by FEKO software. The mesh generation results are saved as .STL file. Since FEKO is a powerful 3D full wave electromagnetic simulation software, we can use its triangulation results as the basis of the NUMGM proposed in this paper. The adaptive mesh lines placement method is illustrated as follows.

Determine the minimum wavelength, denoted as $λ_{\min}$ , in terms of frequency and material property. Constrained by the typical rule of FDTD spatial discretization, the maximum mesh size, $d_{\max}$ , of the entire computing space should satisfy $d_{\max} = \leq λ_{\min} / 10$ .
Calculate the side lengths of each triangular facet and find out the minimum side length $l_{\min}$ . Set the minimum interval of the entire computing space to be $d_{\min} = l_{\min} / 2$ .
Project each triangular facet onto three principal coordinate planes, respectively. Find out the maximum and minimum coordinates along three axes and calculate the differences between them severally, as shown in Figure 8. Denote these differences as $Δ x, Δ y$ , and $Δ z$ .

Figure 8: The projections of the facet on three coordinate planes.
Sort all the $Δ x, Δ 𝑦$ , and $Δ z$ from the smallest one to largest one and insert the starting and ending coordinates of them on the corresponding axes, respectively. Let us take the x-axis treatment as an example. If $Δ x$ is equal to zero, this means that the triangular facet is perpendicular to the XOZ plane. At this point, the $Δ 𝑥$ needs to be adjusted to a suitable value to represent the thickness of the vertical plane. If $Δ x$ is greater than zero and less than $d_{\min}$ , change the value of $Δ x$ to $d_{\min}$ to ensure that the minimum mesh size of the entire space is $d_{\min}$ . Take a cylinder as an example to explain how we decide where to put the mesh lines when $Δ x$ is less than $d_{\min}$ . The cylinder and its triangulation are shown in Figure 9. When we project the triangular facets onto the XOY plane, we will find that the intervals determined by the vertices of the triangular facets are smaller than $d_{\min}$ . At this point, we should change $Δ x$ to $d_{\min}$ .

Figure 9: The cylinder and its triangulation.
Finally, for the intervals greater than $d_{\max}$ on the coordinate axes, divide them equally with the value of d. Taking an internal whose length is $L$ as an example, let the integer $N = ceil (L / d_{\max}$ ), then $d = L / N$ .

Figures 10(a) and (b) show the overall and local structures of a parabolic antenna. The parabolic antenna is fed by a horn antenna and it works at the center frequency of 2.45 GHz. As shown in Figures 10(a) and (b), the maximum size of the antenna is the diameter of the parabola, which is 600 mm, and the minimum size of the antenna is the diameter of the coaxial probe inner conductor, which is 2 mm. The ratio of the maximum size to the minimum sizeis 300.

Figure 10: The structure of the parabolic antenna: (a) the overall structure and (b) the structure of the horn antenna.

Figure 11 shows the triangulation of the parabolic antenna obtained from FEKO 2019.1. FEKO software has its own mesh function. When we build a model in FEKO and set it to the working frequency, the software will automatically generate the appropriate triangular meshes.

Figure 11: The triangulation of the parabolic antenna.

Figure 12 shows the discretization results of the parabolic antenna, the horn antenna, and the coaxial probe. The maximum mesh size is 6.1 mm, and the minimum mesh size is 0.5 mm. It can be seen from Figure 12 that the adaptive mesh lines placement method proposed in this paper can set dense meshes in the fine part and sparse meshes in the other part. The discretization results are in good agreement with the antenna model.

Figure 12: The discretization results of the parabolic antenna: (a) the overall discretization result, (b) the discretization result of the horn antenna, and (c) the discretization result of the coaxial probe.

Table 1 shows the total mesh numbers of the parabolic antenna obtained by UMGM and NUMGM. The mesh size of the UMGM is 0.5 mm. The maximum and minimum mesh sizes of the NUMGM are 6.1 and 0.5 mm. We can see from Table 1 that the number of mesh cells of the target using NUMGM is about 1/5 of that using UMGM.

Table 1: The total mesh numbers of the parabolic antenna generated by UMGM and NUMGM

	UMGM	NUMGM
Mesh number	529205	102776

IV. NUMERICAL EXAMPLES AND SIMULATION RESULTS

Numerical examples are given to illustrate the efficiency of the adaptive mesh generation technique proposed in this paper. The first example is a metal sphere, and the second example is a band-stop FSS. The structures and the generating FDTD grids of the numerical examples are represented, respectively. We also give some simulation results of the numerical examples by performing the novel mesh generation technique.

A. Metal sphere

Figure 13 shows the structure and the resulting FDTD meshes of a metal sphere. The radius of the sphere is 1 m, and the mesh size is 0.025 m. The RCS of the metal sphere simulated by the FDTD method is shown in Figure 14. As comparison, we also give the Mie series result of the sphere’s RCS [22]. It can be seen from Figure 14 that the simulated result is in good agreement with the theoretical result.

Figure 13: The structure and Yee cells of the sphere: (a) the structure and triangulation of the sphere and (b) the Yee cells distribution of the sphere.

Figure 14: The RCS of the metal sphere.

B. Band-stop FSS

A band-stop FSS is shown in Figure 15(a), and its triangulation is shown in Figure 15(b). In order to realize the miniaturization and broad band-stop characteristics, a relatively complex structure was employed in the design of this FSS, especially in the design of the edge part.

Figure 15: The structure and triangulation of the FSS. (a) The structure. (b) The triangulation.

As shown in Figure 15(a), the parameters of the patch is $n = 19$ mm, $w = 1.5$ mm, and $l = 1$ mm. The radii of the four rings are $r_{1} = 2.5$ mm, $r_{2} = 2$ mm, $r_{3} = 1.5$ mm, and $r_{4} = 1$ mm, respectively. The width of each ring is 0.2 mm. The length of the substrate is $P = 20$ mm and the thickness of the substrate is $h = 3.2$ mm.

The FDTD meshes of the band-stop FSS generated by RCTM are shown in Figure 16. The mesh size is 0.2 mm. It can be seen from Figure 16 that the FSS is well-restored in the FDTD grid.

Figure 16: The discretization result of the FSS.

The transient E $_{x}$ values at a point which is 1 mm backward of the FSS is shown in Figure 17. We can see that the FDTD result is in good agreement with the result obtained by CST Studio Suite 2020 [23]. CST Studio Suite is a high-performance 3D EM analysis software package for designing, analyzing, and optimizing electromagnetic components and systems.

Figure 17: The $E_{x}$ of the point which is 1-mm backward of the FSS.

Figure 18 shows the S $_{21}$ curves of the FSS obtained by FDTD method and CST Studio Suite, respectively. The calculated S $_{21}$ shows reasonable agreement with the CST Studio Suite one, which represents that the mesh generation technique proposed in this paper has the ability to deal with the target with complex edgestructure.

Figure 18: The $S_{21}$ of the FSS obtained by FDTD method and CST Studio Suite simulation.

V. CONCLUSION

Based on the triangular facets obtained by the .STL file of the object, an adaptive mesh generation technique is proposed for 3D FDTD simulation in this paper. First, RCTM is introduced. As opposed to RTM, for each grid on the coordinate plane, the RCTM employs multiple rays in the normal direction to intersect the triangular facets. The implementation of RCTM makes the mesh generation technique have high accuracy in edge structure mesh transformation. Second, according to the vertex coordinates of the triangular facets, adaptive mesh lines placement method is illustrated. For an object with fine structure, the mesh lines placement method can automatically set dense meshes in fine structure and sparse meshes in rough structure. A metal sphere and a band-stop FSS are given as numerical examples. Simulated and theoretical results show that the proposed mesh generation technique is flexible andaccurate.

ACKNOWLEDGMENT

This work was supported by the National Key Research and Development Program of China under Grant 2020YFA0709800, by the Technology Program of Shenzhen under Grant JCYJ20180508 152233431, and by the National Natural Science Foundations of China under Grant 61971340.

REFERENCES

[1] K. S. Yee, “Numerical solution of initial boundary value problems involving Maxwell’s equations in isotropic media,” IEEE Trans. Antennas Propagat., vol. AP-14, pp. 302–307, 1966.

[2] A. Taflove and S. C. Hagness, Computational Electrodynamics: The Finite-Difference Time-Domain Method, Artech House, Boston, MA,2005.

[3] A. G. Taflove, A. Oskooi, and S. G. Johnson, Advances in FDTD Computational Electrodynamics: Photonics and Nanotechnology, Artech House, Boston, MA, 2013.

[4] P. Li, J. J. Li, M. Tang, Y. J. Zhang, S. Xu, and H. Bagci, “A novel subdomain 2D/Q-2D finite element method for power/ground plate-pair analysis,” IEEE Trans. Electromagnetic Compatibility, vol. 62, no. 5, pp. 2217–2226, Oct.2020.

[5] P. Li, J. J. Li, Y. J. Zhang, S. Xu, and H. Bagci, “An efficient mode based domain decomposition hybrid 2D/Q-2D finite-element time-domain method for power/ground plate-pair analysis,” IEEE Trans. Microwave Theory and Techniques, vol. 66, no. 10, pp. 4357–4366, Oct. 2018.

[6] W. Sun, C. A. Balanis, M. P. Purchine, and G. Barber, “Three dimensional automatic FDTD mesh generation on a PC,” Proceedings of IEEE Antennas and Propagation Society International Symposium, Ann Arbor, MI, pp. 30–33, 1993.

[7] Y. Srisukh, J. Nehrbass, F. L. Teixeira, J. F. Lee, and R. Lee, “An approach for automatic grid generation in three-dimensional FDTD simulations of complex geometries,” IEEE Antennas Propag. Mag., vol. 44, no. 4, pp. 75–80, Aug. 2002.

[8] J. T. MacGillivray, “Trillion cell CAD-based cartesian mesh generator for the finite-difference time-domain method on a single-processor 4-GB workstation,” IEEE Trans. Antennas Propagat., vol. 56, no. 8, pp. 2187–2190, Aug. 2008.

[9] T. Ishida, S. Takahashi, and K. Nakahashi, “Efficient and robust cartesian mesh generation for building-cube method,” Journal of Computational Science and Technology, vol. 2, no. 4, pp. 435-446, 2008.

[10] G. Waldschmidt, A. Taflove, “Three-dimensional CAD-based mesh generator for the Dey-Mittra conformal FDTD algorithm,” IEEE Trans. Antennas Propagat., vol. 52, no. 7, pp. 1658–1664, July 2004.

[11] L. X. Yang, D. B. Ge, J. Bai, and S. T. Zhang, “A novel FDTD modeling technique based on triangle mesh-units of an object,” Journal of Xidian University, vol. 34, no. 2, pp. 298–302, Apr. 2007.

[12] M. K. Berens, I. D. Flintoft, and J. F. Dawson, “Structured mesh generation: Open-source automatic nonuniform mesh generation for FDTD simulation,” IEEE Antennas and Propagation Magazine, vol. 58, iss. 3, pp. 45–55, June 2016.

[13] X. C. Bo, X. B. Jin, J. F. Zhang, and T. J. Cui, “Study of corner singularity in conformal structured mesh generation for the finite-difference time-domain method based on ray tracing,” IEEE Transactions on Microwave Theory and Techniques, vol. 67, no. 1, pp. 57–69, Jan. 2019.

[14] W. Jiang, Y. Liu, S.-X. Gong, and T. Hong, “Application of bionics in antenna radar cross section reduction,” IEEE Antennas and Wireless Propagation Letters, vol. 8, pp. 275–1278,2009.

[15] B. Biswas, R. Ghatak, and D. R. Poddar, “A fern fractal leaf inspired wideband antipodal vivaldi antenna for microwave imaging system,” IEEE Trans. Antennas Propagat., vol. 65, no. 11, pp. 6126–6129, Nov. 2017.

[16] G. N. Zhou, B. H. Sun, and Q. Y. Liang, “Triband dual-polarized shared-aperture antenna for 2G/3G/ 4G/5G base station applications,” IEEE Trans. Antennas Propagat., vol. 69, no. 1, pp. 97–108, Jan. 2021.

[17] Y. Kanai and K. Sato, “Automatic mesh generation for 3D electromagnetic field analysis by FDTD method,” IEEE Trans. Magn., vol. 34, no. 5, pp. 3383–3386, Sept. 1998.

[18] M. W. Yang, and Y. C. Chen, “AutoMesh: an automatically adjustable, non-uniform, orthogonal FDTD mesh generator,” IEEE Antennas and Propagation Magazine, vol. 41, no. 2, pp. 13–19, April 1999.

[19] H. S. Kim, I. S. Ihm, and K. Choi, “Generation of non-uniform meshes for finite-difference time-domain simulations,” Journal of Electrical Engineering and Technology, vol. 6, no. 1, pp. 128–132, Jan. 2011.

[20] H. A. Fernanades, “Development of software for antenna analysis and design using FDTD,” M.S. dissertation, Instituto Superior T $\overset{´}{e}$ cnico, University of Lisbon, LIS, Portugal, 2007.

[21] Altair Feko. (2019). [Online]. Available: https://www.altair.com/feko.

[22] J. M. Jin, Theory and Computation of Electromagnetic Fields, John Wiley & Sons Inc., Hoboken, NJ, 2010.

[23] CST STUDIO SUITE. (2020). [Online]. Available: https://www.3ds.com/products-services/simulia/products/cst-studio-suite/.

[24] Javier Moreno, Mar $\overset{´}{i}$ a J. Algar, Iv $\overset{´}{a}$ n Gonz $\overset{´}{a}$ lez, and Felipe C $\overset{´}{a}$ tedra, “Design and evaluation of the multilevel mesh generation mode for computational electromagnetics,” Applied Computational Electromagnetic Society (ACES) Journal, vol. 30, no. 6, pp. 578–588, June 2015.

[25] M. Bai, B. Liang, and H. Ma, “An efficient FDTD algorithm to analyze skewed periodic structures impinged by obliquely incident wave,” Applied Computational Electromagnetic Society (ACES) Journal, vol. 30, no. 10, pp. 1068–1073, Oct. 2015.

BIOGRAPHIES

Chunhui Moubio1was born in Yantai, China, in 1988. She received the B.S. and M.S. degrees in electromagnetics from Xidian University, Xi’an, China, in 2012 and 2015, respectively. She is currently working toward the Ph.D. degree with Xi’an Jiaotong University, Xi’an, China. Her research interests include the fast FDTD method, multi-physical field calculation, and FDTD mesh generation method.

Juan Chenbio was born in Chongqing, China, in 1981. She received the Ph.D. degree in electromagnetic field and microwave techniques from Xi’an Jiaotong University, Xi’an, China, in 2008. From April 2016 to March 2017, she was a Visiting Researcher with the Department of Electrical and Computer Engineering, Duke University, Durham, NC, USA, under the financial support from the China Scholarship Council. She currently serves as a Professor with Xi’an Jiaotong University. Her research interests include the numerical electromagnetic methods, advanced antenna designs, and graphene theory and application.