HUANG Minjie, ZHOU Yaoming,*, WANG Yongchao, and LIU Zhongtie

1.School of Aeronautic Science and Engineering, Beihang University, Beijing 100191, China;

2.Key Laboratory of Complex Aviation System Simulation, Beijing 100076, China

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.

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

1.Introduction

Space partitioning is a process of dividing the space occupied by models or targets into a union of subspaces according to a certain rule and, in an orderly way, organizing the models’ or the targets’ information by their positional relationships with the subspaces.

Space partitioning techniques not only play an important role in computer modeling and display technology [1,2]but also are applied to many physical process simulation fields, such as image processing [3], high-frequency electromagnetic field calculations [4−6], acoustics analysis[7], thermal radiation simulation [8], and some basic fields such as multi-object optimization [9,10].These types of methods, which decompose the traversal operation of the whole model into a series of traversal operations of the subspaces and model parts, can obviously reduce the computational complexity and thus accelerate the speed of processing.

The binary space partitioning (BSP) algorithm and its derivative methods, which are known for their simplicity,high efficiency and recursive properties, have become the most popular space partitioning methods since they were proposed by Fuchs, Kedem, and Naylor at Bell Laboratory in 1980 [11].The BSP method is highly efficient and accurate in solving the space partitioning problems of particle swarm models and performs well in some 3D or quasi-3D applications that have low thresholds or requirements for accuracy.Space partitioning methods based on BSP have been widely used in solving some quasi-3D problems such as scene rendering and collision detection in computer game development, telecommunication base station planning, and noise prediction and control[11−14].This BSP based method is usually referred to as the octree method when dealing with 3D models.In these applications, the targets can be easily simplified to particles or 2−3 groups of parallel surface elements.For those targets that are composed of 2−3 groups of parallel surface elements, the BSP works with high efficiency by taking the planes parallel to those surface elements as partition base planes [12−15].

However, the cost would increase rapidly if the BSP technique is applied to solving the problems of precise space partitioning for more complex 3-D targets.Fig.1 gives a partition example for a 2-D triangle surface element.When the BSP technique is used, first, one selectsx=1 as the partitioning line which results in triangle ΔPQRcrossing the linex=1.Then, taking liney=1 as the second partitioning line, the triangle ΔPQRcan be mapped across four subareas: (0, 0), (0, 1), (1, 0), and (1,1) (the subarea is marked with the coordinate of its bottom-left vertex).Only when the precise shape of the triangle ΔPQRon the left side of linex=1 has been obtained can the subarea (0, 0), which is not crossed, be excluded.It is an enormous task to complete a large number of arbitrary polygon-division calculations, which makes the BSP technique inefficient for solving arbitrarily complex targets [16,17].

Fig.1 BSP method used to solve the space partitioning problem of a 2D triangle

Most existing space partitioning methods are based on the BSP algorithm or belong to the uniform space partitioning technique.Almost all of these methods are too inefficient to be used for real-time computing, so sometimes we have to use hardware acceleration to deal with some problems with high real-time requirements [18−20].Liu et al.[18] presented a rapid uniform space partitioning method that has the potential to transform into a realtime algorithm.This paper will improve the method and establish an adaptive space partitioning algorithm based on the method.

2.Improvement of the rapid uniform space partitioning method in [18]

The space partitioning method presented in [18] is proved to be efficient in solving the space partitioning problems of models that consist of triangular facets, but it is not rigorous in addressing the endpoints of the reference lines and has the possibility of improvement.

2.1 Fundamentals of the rapid uniform space partitioning method in [18]

Liu et al.[18] simplified the judgment of the position relationship between straight line segments and unit cube regions into the problems of real number rounding and memory addressing.As shown in Fig.2, the problem of the positional relationship between a straight-line segment and unit cubes is the prerequisite of discussing a more complex situation.Liu et al.[18] simplified this problem to the recognition of the parallelepiped subspaces a line passes through.

Fig.2 Uniform space partitioning of a straight-line segment

If normalized, the boundaries of unit-cube subspaces can be assumed to be planes parallel to the coordinate planes:

wherel,m,n=0,±1,±2,···.

Thus, if a straight-line segment intersects with a unit cube, at least one coordinate component of the intersection should be an integer.Considering this fact, we can search the intersected unit cubes by detecting the vertices that have an integer coordinate component in the given line.

Assuming that the coordinate components of the two endpoints (A(xA,yA,zA) andB(xB,yB,zB)) of the straightline segmentare real numbers, the number of intersection vertices of the straight-line segmentABand the grid lines can be obtained by the following equations:

where [[x]] means the largest integer not greater thanx,and

where min(p1,p2,···)(m ax(p1,p2,···)) gives the minimum(maximum) value of the real number series{p1,p2,···}.

Each grid that the straight-line segment passes through has two intersection vertices with the straight-line segment, except for the grids in which the endpointsAandBare located.On the other hand, two adjacent grids share the same intersection.Therefore, the number of grids crossed by the straight-line segmentcan be calculated as follows:

The coordinate of the vertex on the straight-line segmentcan be expressed with the parametric equations

where λ ∈[0,1].

As the parameter λ changes from 0 to 1, pointE(x,y,z)moves from vertexAto vertexB.In this process, the coordinates of the intersection vertices of the straight-line segmentand the grid lines can be expressed with the following parametric equations:

sign(x) means the sign of real numberx.

If we use the coordinate of the bottom-left corner vertex to mark the grid, for example, Grid(1,2,3) represents that the coordinate of the bottom-left corner vertex of the grid is (1,2,3), and then the grids thatABpasses through can be expressed as

If the coordinate of vertexBis a non-integer, thenin which vertexBis located will not be counted.If all grid related information is stored in 3-D arrays, the obtaining of (x,y,z) means that the storage address of the related information of Grid(x,y,z) is found.

Among all the discrete elements used to discretise 3D surface models, the triangular element is the most fundamental form.Any complex model or other discrete elements can be approximated by triangles.Therefore, the position relationship between the triangles and space partition grids is a key to solve the space partitioning problem of complex 3D models.

The grids on the boundaries of the triangular patch can be first determined using the method proposed earlier.Next the question is how to quickly determine which grids are surrounded by the boundary grids.

As in the 2D case shown in Fig.3, if thex-coordinate of vertexEsatisfies the following condition as they-coordinate varies fromyAtoyC:

Fig.3 Positional relation between planar triangle and unit squares

We can then draw the conclusion that vertexEis located inside the triangle, and a method can be designed to seek the grids surrounded by the boundaries of the triangular patch according to this conclusion.

For an arbitrary surface element ΔPQR, assuming that ΔABCis identical to ΔPQRand we are only making an adjustment on the sequence of nodes, we have

If vertexBis on the right side of sideAC, then

As they-coordinate of vertexEon the triangular varies fromyAtoyC, the parametersxminandxmaxcan be expressed as follows:

The question is simplified to determine the grids that the lines pass through (14), which are represented by the dotted red lines shown in Fig.3.

2.2 Improvement on definition of reference lines

Liu et al.[18] selected (14) as the basis for detecting the unit cubes that a triangle passes through.This method can be repeated with the count of the edges of the triangle,which makes the algorithm inefficient especially when the triangles are small.Actually, the lengths of the lines(14) can be further reduced to lines (15), and the search range is shrunk to the solid red lines shown in Fig.3.

In fact, redundancy always exists when the straightline segments given by (15) are used to detect the grids surrounded by the boundaries.As is shown in Fig.3, the grids in which the blue points are located have been identified by the boundary detection in the previous step.The solution is to further reduce the lengths of the segments given in (15) to (16), and thus, the detection ranges are shrunk to the line segments between the red endpoints.

The difference betweenxMIN(n) andxmin(n) is thatxMIN(n) is an integer that depends on the larger one ofxmin(n) andxmin(n+1) .Thus, the straight-line segmentLnpasses through the following grids:

The grids are finally determined, as in the shaded area shown in Fig.3.

If vertexBis on the left side of sideAC, then

By just exchanging the mathematical expressions of the parametersxmin(y) andxmax(y), the following steps basically remain the same.

For the 2D case, the detection of the grids that overlap with a triangular surface element can be regarded as the process of using they-direction as the key search direction, and then, we search the possiblex-coordinate of the vertex whosey-coordinate falls in the interval between two adjacent integers.

For the spatial triangle ΔPQR, we can extend the detection algorithm of the 2D case to 3D space.Specifically,we only detect the unit cubes that the triangle ΔPQRpasses through along a three-level searching direction determined by a certain sequence ofx,y, andz.If the coordinate componentszA,zB, andzCare not completely the same, then the sequence of the three pointsA,B, andCcould be adjusted to meet the following condition in accordance with thez-coordinates of the three vertices:

The coordinate of vertexEon spatial triangle ΔPQRmeets the following relation:

Rewriting the relation in detail, we have

where α=0 represents that vertexEis on the sideBC,β=0 represents thatEis on the sideAC, and 1−α−β=0 represents thatEis on the sideAB.

If thez-coordinates of the three vertices meet the relations ofzA≠zB,zB≠zC,zC≠zA, andzA≤z0≤zC, the possible endpoints at which the triangular element intersects with the planez=z0can be determined.

As shown in Fig.4, if triangle ΔABCintersects with the planez=z0, the intersection (xβ,yβ,z0) at which the sideACintersects with the planez=z0must be one of the endpoints of the intersecting line.IfzA≤z0≤zB, the line segmentABintersects with the planez=z0at vertex (xαβ,yαβ) .IfzB≤z0≤zC, the line segmentBCintersects with the planez=z0at vertex (xα,yα).Therefore,the intersecting line can be expressed as follows:

Fig.4 Projection of the triangular patch and spatial grids on the coordinate planes

Similar to the 2D algorithm, we must determine the unit cubes passed through byLn, which is the intersecting line of the surface element and planez=[[zA]]+n, as the parameterz0varies fromzAtozC:

wheren=1,2,···,[[zC]]−[[zA]]−1.

Similarly, the parametersEnandFncan be modified to avoid the unit cubes passed through by the boundaries of the surface element being double counted.If we make the judgment based on thex-coordinate, then we have

If we make the judgment based on they-coordinate,then we have

where

Additionally, the parametersx=x(y,z),y=y(z,x) can be determined by the relational expression of the three coordinates of the vertex on ΔABC.

Obviously, verticesEnx,Fnx,Eny, andFnyare on the intersecting line of the triangular element and the planez=[[zA]]+n.We modifyEnandFnto the vertices which makes the length ofreach the minimum:

whereu,v=x,y;n=1,2,···,[[zC]]−[[zA]]−1.

Next, the question can be simplified to detecting the unit-square grids passed through by straight-line segments on the 2D plane, and the method presented earlier can be used to settle the problem.

The coordinate componentzcould be replaced byxandyin a sequence to perform similar operations, and the unit cubes that intersect with the triangular patch would finally be determined accurately.If each vertex in the triangle has the same coordinate component, then this coordinate component can be directly skipped.

The coordinates of the three vertices of ΔABCshown in Fig.4 are as follows:

The number of unit cubes that intersect with ΔABCdetected by the above method is 181, and the positional relationship between these unit cubes and ΔABCis shown in Fig.5.

Fig.5 Unit cubes that intersect with ΔABC

2.3 Actual effects

Both the BSP and the algorithm proposed in this paper are used to solve two 3D models separately on a personal computer configured with an i7 6500U 2.5 GHz CPU and 8 GB RAM.Programs are built with VS2010 under the Windows 7 32-bit operating system.Model 1 and model 2 have 238641 and 260489 triangular surface elements, respectively.Different scales of isometric orthogonal spatial grids, including 20×20×10 and 40×40×20, are used to divide model 1, and 20×20×5 and 40×40×10 are used to divide model 2 (see Fig.6).A comparison of the time consumption is shown in Table 1.Accurate calculation of the shapes of the deep-divided patches mentioned in Section 1 is not conducted in the BSP method, and thus, redundancy is inevitable in the result.

Fig.6 Space partitioning images for two typical models

Table 1 Comparison of the efficiency among the BSP algorithm,algorithm in [18] and the proposed algorithm

In Table 1,*means the calculation time of converting the main frequency of the computer to the same hardware platform as [18].According to Table 1, the algorithm presented in this paper has nearly 4−6 times higher computational efficiency than [18].Even if it is converted to the same hardware platform, the method proposed in this paper is still six times faster than the method of [18] for the space partitioning of 20×8×8 orthogonal spatial grids.The reason may be that when the size of most of the surface elements is smaller than the size of the spatial grids, the positional relation judgment between triangle and unit cubes of this method degenerates to the judgment of unit cubes where the vertexes of triangle lie, but method in [18] still needs to judge at least three edges passing through the unit cubes.This efficiency makes it feasible for real-time or quasi real-time space partitioning of large dynamic models.

3.Design of the adaptive space partitioning algorithm

To save computing resources, the subspace density of the space partitioning should be determined by the local complexity of the target or local surface-element density.In other words, the subspace density should be almost proportional to the local complexity of the target.Applying computing resources to the most needful areas is the basic idea of the adaptive space partitioning algorithm.

If the isometric planes in the three orthogonal directions are used to divide a 3D model, then two possible adaptive algorithms for space partitioning can be adopted.One of them is to replace the isometric planes with nonisometric planes; the other is to subdivide the unit-cube subspaces that comprise more discrete models by a uniform space partitioning algorithm.The former method is easy to implement.However, the increase in the partition density in the areas that have high local complexity or surface-element density could simultaneously result in an increase in the partition density in the areas that contain few surface elements, which partially offsets the benefits.The latter approach has no similar defect.Instead, it can be programmed by nested structures.This paper will select the latter adaptive algorithm as the research direction and design nested structures based on a uniform space partitioning algorithm to achieve the intention of an adaptive space partition.

3.1 Principle of the adaptive space partitioning algorithm

To achieve the nestification of a space partition, we can detect the result of the first uniform space partition and subdivide the subspaces that must be further partitioned.Normally, the number of surface elements in the subspaces or other characteristics is taken as the evaluation parameter.If the evaluation parameter is greater than a certain threshold (such as the number of surface elements being greater than a certain value), the subspaces and the part of the model in these subspaces would be taken as the target of the space partitioning to be further partitioned.We define the target and its bounding box to be partitioned as the parent space, the hexahedral spatial regions obtained by space partitioning as sub-grids, and the union of the sub-grid and the surface elements within it as the subspace.Then, the subspace to be partitioned can also serve as the parent space for the next level subspaces.

Fig.7 is a schematic diagram of the adaptive space partition, which is based on the algorithm of uniform space partition mentioned above.The basic steps are as follows:

Fig.7 Schematic diagram of the adaptive space partitioning algorithm

Step 1Determine the parameters of the parent space that must be partitioned according to the models.

Step 2Conduct the first space partition on the parent space by using the rapid space partitioning algorithm proposed in Section 2 according to the initial requirements.Then, the first layer of the sub-grids and the corresponding model partition information will be generated.

Step 3Determine the setting parameters of the subgrids serving as the spaces to be partitioned from their geometrical features, and organize this information as the parent space.

Step 4Make a judgment on whether the layer level of the sub-grid is less than the target level.If true, execute Step 5; otherwise, no operation is needed.

Step 5Make a judgment on the characteristics of the part of the model located in the sub-grid.If the condition required for further space partitioning is satisfied, then the sub-grid would be subdivided again; otherwise, no operation is needed.

Step 6For the newly formed sub-grids, repeat Steps 3 to 6 until no further space partitioning is required for any sub-grid.

For the discrete surface element models, the number of surface elements contained in the sub-grid can serve as the condition required for further space partitioning in Step 5.For the surface models, the maximum radian of the curved surface in the sub-grid could serve as the condition.

The reason why a restriction has been set in Step 4 is that in some cases, regardless of how the sub-grids are subdivided, the characteristics of the sub-grids always meet the further space partition condition in Step 5.For the symmetric target with a steeple shown in Fig.8, if the initial grid lines go through the conic node, then the number of surface elements contained in some sub-grids will remain constant regardless of how the sub-grids are divided by using the isometric partition algorithm.Then,the level restriction in Step 4 can help to jump out from the endless loop.

Fig.8 An extreme situation in which an endless loop of subdivisions can appear

The program structure of the adaptive space partitioning algorithm is shown in Fig.9.Compared with the rapid space partitioning algorithm, the kernel of this algorithm is that every generated sub-grid and its contained surface elements can be taken as a new space to be subdivided to achieve the nestification.In addition, two judging conditions are required to break out of the nested loop.On the other hand, the information of each subspace contains not only the necessary geometric information and the code set of elements located in the subspace, but also its parentspace code and child-space codes.In order to directly find out the subspace where elements belong to by rounding operation and avoid the judgment of geometric position relationship, the codes of child spaces are also stored as a three-dimensional array.In this way, with the standard subspace module as the basic unit, the whole adaptive space partitioning result information can be stored according to the tree structure (Fig.9(b)).Then, the adaptive space partitioning algorithm can be easily conducted based on the rapid space partitioning algorithm.

Fig.9 Data storage and program structure of the adaptive space partitioning algorithm

3.2 Combination of the adaptive space partitioning algorithm and its applications

The adaptive space partitioning algorithm presented in Section 3.1 can be easily combined with several applications.Fig.10(b) is a flow chart of the application part since the adaptive space partitioning algorithm has been introduced.A judgment as to whether there are sub-grids or not and a loop are added to the fundamental application processes, as seen in Fig.10(b), such that they have little effect on the program’s implementation.

Fig.10 Combination of the adaptive space partitioning algorithm and application algorithms

4.Numerical experiments and application in electromagnetic scattering calculation

4.1 Effects of the adaptive space partitioning algorithm

The authors programmed the algorithm of adaptive space partitioning in the language C++, and analyzed the results of the space partitioning of the models as shown in Fig.6.The hardware is the same as the platform mentioned in Section 2.3.The space partition results of the uniform space partitioning algorithm and the adaptive space partitioning algorithm are shown in Fig.11 and Table 2.Model 1 has been divided into seven layers and the maximum allowable quantity of surface elements in each subspace is 16 (Fig.11(a)).Model 2 has been divided into eight layers, and the maximum allowable quantity of surface element in each subspace is 24 (Fig.11(b)).From the distribution effect of the sub-grids, the goal of the adaptive space partitioning has been completely achieved.The bounding box of Model 1 has been divided into 54264 seventh-layer sub-grids, in which the average quantity of triangles is 8.64 and the maximum quantity is 299.The bounding box of Model 2 has been divided into 44728 eighth-layer sub-grids.The average quantity of triangles in the bottom layer sub-grids is 8.36, and the maximum quantity of triangles is 313.The time consumption of the adaptive space partitioning is no more than 13 times longer than that of the uniform space partitioning, while the memory occupancy is about 3.8−4.6 times of the uniform space partitioning (Table 2).Considering that the space partitioning process only needs to be carried out once for static model or quasi-static model, the time consumption of adaptive space partitioning is an acceptable cost and can be reduced by controlling the count of layers.The memory occupancy of space partitioning information is still less than that of the geometry information of the model, so the worry about memory occupancy is unnecessary.

Fig.11 Effects of adaptive space partitioning on typical targets

Table 2 Statistical result of space partitioning on typical targets

The space partitioning result of Model 1 is shown in the statistical graph in Fig.12.

Fig.12 Statistical result of Model 1 obtained using the adaptive space partitioning algorithm

The quantity of the subspaces at space partitioning level 1 is 2×2×2.Fig.12 indicates that the quantity of the bottom level subspaces reduced with the increase in the partitioning level when the partitioning level is more than 7.On the other hand, as the partitioning level increased,the maximum quantity of the surface patches in the bottom level subspace is tightened to 299.This arrangement means that the extreme case shown in Fig.8 occurs, and no significant improvement will be achieved if we continue the space partitioning when the partitioning level is more than 7.This result is helpful for designing an adaptive space partition process.

(i) Attempt to avoid symmetry space partitioning for a symmetry model.

(ii) There is no need to pursue a meticulous partition.Usually, there is a best space partitioning depth for a given model.

As shown in Fig.11, the space partitioning operation is executed entirely in accordance with the local complexity of the target, and a trend that the spatial grids are gradually presenting the outline of the target has been formed,which directly confirms the adaptive feature of space partitioning.

4.2 Application in electromagnetic scattering calculation for the adaptive space partitioning algorithm

The ray tracing (RT) method which is also called as“shooting and bouncing ray (SBR) method”, is widely used for electromagnetic field calculation, 3D rendering and other applications [19−23].RT calculation involves a lot of calculation of intersections between rays and the target surface.If the surface elements are organized according to their space position, the efficiency of the RT method can be significantly improved by solving the intersection of ray and spatial grids first, and then the intersection of ray and the surface elements in the spatial grids.The calculation of the intersection points of ray and spatial grids is very similar to the basic calculation process involved in the space partition method in this paper.Therefore, the algorithm proposed in this paper may greatly improve the efficiency of RT calculation.

Taking the application of computational electromagnetism as an example, the authors pretreated Model 2 using the adaptive space partitioning algorithm, and then computed the monostatic scattering fields of Model 2 illuminated by plane wave by the RT method.The frequency is 3 GHz, the pitching angle is −15°, and the azimuth angle is 45°, with HH polarization.The hardware is the same as the platform mentioned in Section 2.3.The RT method is used to calculate the primary scattering contribution and multiple scattering contribution of the target surface.In practice, the incident plane wave is divided to 7.7×105ray tubes with the same cross section of 0.01 m×0.01 m.The result shows that the time consumption for obtaining a scattering map as in Fig.13 using the RT method reduces from 12.1 s of the uniform space partition to 6.1 s.Considering that it is hard to reduce the computing cost of RT [19−22], this result means a significant improvement in the efficiency.This adequately demonstrates that the adaptive space partitioning algorithm can significantly improve the processing efficiency of certain engineering applications.It is usually hard to strictly prove the accuracy of the space-partitioning result of a complex target.However, Fig.14 shows that there is no difference between the RCS azimuth distribution maps between the traditional uniform space partition method and the adaptive space partition method (the frequency is 10 GHz and the pitching angle is 10°, with HH polarization).On the other hand, the total reflection times and the coordinates of the reflection points calculated by the two methods are exactly the same (Table 3), which proves the reliability of the adaptive space partitioning algorithm indirectly.

Fig.13 Scattering density distribution map of Model 2

Fig.14 RCS calculation results comparison of Model 2

Table 3 Comparison of ray tracing process conducted on adaptive space partition and uniform space partition

In another example, the adaptive space partitioning algorithm is used to improve the efficiency of the RCS integrated computing platform.The calculation method of electromagnetic scattering of the platform is PO + (ECM +PTD) + RT.In this method, RT is used to calculate the contribution of multiple scattering; the PO (physics optical) method is used to calculate the primary scattering contribution while ECM (equivalent current method) + PTD(physical theory of diffraction) is used to compute the contribution of discontinuous characters of the target.The efficiency bottleneck of the RCS computing platform is the RT computing part.Fig.15 shows a scattering density distribution map of Model 1 (frequency = 22.5 GHz,pitching angle = −15°, azimuth angle = 0°, VV polarization) and Fig.16 gives a typical monostatic RCS azimuth distribution map of Model 1 calculated by the RCS integrated computing platform (frequency = 30 GHz, pitching angle = −15°, VV polarization).The time consumption for obtaining an RCS azimuth distribution map shown in Fig.15 is given in Table 4.The hardware is the same as that mentioned in Section 2.3 and the cross section of the ray tubes is also 0.01 m×0.01 m.As can be seen from the table, compared with uniform space partitioning, the adaptive space partitioning algorithm can reduce the calculation time of the RCS integrated computing platform by about 40%.

Fig.15 Scattering density distribution map of Model 1

Fig.16 RCS calculation results comparison of Model 1

Table 4 Comparison of computing time consumption for integrated computing platform

5.Conclusions

In this paper, an improvement on the space partitioning of the complex 3D model in [18] 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 method in [18].Furthermore, an adaptive space partitioning algorithm is developed based on this improved algorithm.This adaptive space partitioning algorithm can be easily implemented and combined with the applied algorithms.The tests show that almost all the advantages of the original uniform space partitioning algorithm, such as its low time consumption and memory occupancy, reliability and usability, are retained in the adaptive algorithm.When it is used to calculate the electromagnetic scattering of complex targets by the 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.

The study finds that the layers of the space partition and the initial settings in different directions have a large impact on the efficiency of the engineering calculation.In view of consideration, the next step that the authors will focus on in the investigations is the action of the partitioning forms and the settings of the adaptive space partitioning algorithm on the calculation efficiency in some typical applications and searching for the optimal application mode of the adaptive space partitioning algorithm.On the other hand, in practical engineering applications,volume targets are more common and the volumetric SBR (VSBR) method is more widely used [23]; if the proposed adaptive spatial segmentation method can be combined with volumetric targets and the VSBR method,it can greatly broaden the application scope and play a role in many fields, which is also one of the research contents of the authors.