KR101405460B1 - System and method for rapid wave propagation analysis using 3d spatial indexing and 3d culling techniques - Google Patents

Abstract

3D propagation analysis system based on 3D spatial index and 3D curling technique receives input data for radio wave analysis using ray tube method. The propagation analysis speedup system divides the analysis area of the input data to generate a quadtree, divides the object, and creates a BSP tree based on the correlation between the objects. When the generation of the BSP tree is completed, the propagation analysis speedup system determines the effective reflection plane based on the 3D curling technique and generates a ray tube tree to search the effective propagation path.

Description

TECHNICAL FIELD [0001] The present invention relates to a system and method for accelerating radio wave analysis based on a 3D spatial index and a 3D curling technique,

The present invention relates to a system and method for spread spectrum analysis based on a 3D spatial index and a 3D curling technique. More particularly, the present invention relates to an efficient 3D spatial index and 3D curling method, And more particularly, to a system and method for spread spectrum analysis.

The present invention is derived from research carried out by the Ministry of Knowledge and Economy as a part of the IT original technology development project [Project Number: 2007-F-042-03, Project Name: Development of advanced technology for analysis of radio waves based on 3D GIS].

It is possible to analyze various propagation characteristics such as electric field intensity, path loss, and delay spread by tracking the process of a radio wave emitted from a transmitting antenna reaching a receiving antenna using a ray tracing based radio wave analysis technique. This ray tracing based radio wave analysis technique is useful for analyzing the propagation environment considering the reflection / diffraction from the terrain and building walls mainly for narrow areas such as micro cells or picocells.

Various models such as Ray Launching Method, Image Method and Deterministic Ray Tube Method have been developed according to the ray tracing method. Among these models, electric imaging or deterministic ray tube method is generally used more than photoreceiving method in terms of accuracy and speed of analysis.

What is important in the development of wave analysis based radio wave analysis technology is how to reflect the radio waves emitted from the transmitting antenna from the arbitrary wall surface to the peripheral wall surface, and to reflect / reflect from the arbitrary wall edge to the peripheral wall or the wall edge, Or diffraction of a building. Actually, when a ray tracing-based radio wave analysis technique is used, a long search time is required to analyze reflection and diffraction characteristics of each building wall and ground. In other words, even if it is a narrow area, in case of searching using a ray tracing based radio wave analysis technique, unnecessary searching process or duplicate search for the same area may occur in a state in which there is no prior information about all the faces and edges in the area So that a long search time is required. In addition, it is necessary to accurately search the effective reflection surface / effective diffraction point involved in actual reflection or diffraction on a 3D (Three Dimensions) object, and the accuracy of the analysis result can be improved through this.

Therefore, in order to commercialize the ray tracing-based radio wave analysis technology, it is required to develop various high-speed techniques for increasing the analysis speed and radio wave analysis technology considering the 3D curling technique for improving the accuracy.

SUMMARY OF THE INVENTION The present invention is directed to a system and method for spread spectrum analysis based on a 3D spatial index and a 3D curling technique capable of speeding up the propagation analysis technique based on ray tracing and improving accuracy.

According to an aspect of the present invention, there is provided a system for accelerating a radio wave analysis based on a 3D spatial index and a 3D curling technique,

A method for generating a BSP tree based on a correlation between objects, the method comprising: receiving input data for radio wave analysis using a ray tube technique, generating a quad tree by dividing an analysis area of the input data, And an electric field strength prediction / visualization unit for generating a ray tube tree and determining an effective propagation path by determining an effective reflection plane based on the 3D curling technique when the generation of the BSP tree is completed.

According to another aspect of the present invention, there is provided a method of performing radio wave analysis at a high speed based on a 3D spatial index and a 3D curling technique,

Receiving an input data for the radio wave analysis, dividing an analysis region of the input data to generate a quadtree, dividing an object, generating a BSP tree based on a correlation between the objects, Determining an effective reflection plane based on the 3D curling technique to generate a ray tube tree; searching for an effective propagation path by locating a reception point at a point where electric field intensity is to be predicted in the ray tube tree; .

According to the embodiment of the present invention, the accuracy of the propagation path search can be improved by searching the accurate reflection surface and the effective diffraction point from the wall of the building through the propagation analysis technique based on the ray tube technique using the 3D curling technique, The tree technique can shorten the search time required to find the effective propagation path.

1 is a diagram schematically showing a radio wave analysis and acceleration system according to an embodiment of the present invention.
FIG. 2 is a view schematically showing the space division / indexing unit shown in FIG. 1. FIG.
3 is a diagram illustrating an example of a quadtree according to an embodiment of the present invention.
4 is a diagram illustrating an example of an object division scheme according to an embodiment of the present invention.
5 is a diagram illustrating an exemplary BSP tree generation scheme according to an embodiment of the present invention.
FIG. 6 is a view schematically showing the electric field intensity predicting / visualizing unit shown in FIG. 1. FIG.
7 is a view showing an example of searching only the effective reflection surface from the entire wall surface by using the 3D curling technique according to the embodiment of the present invention.
FIG. 8 is a diagram illustrating an example of an effective radio wave search process using a ray tube technique according to an embodiment of the present invention.
9 is a view showing an example of a visualized screen of a real-time radio wave analysis result according to an embodiment of the present invention.
10 is a diagram illustrating a procedure for performing radio wave analysis at a high speed based on a ray tube technique in a radio wave analysis and acceleration system according to an embodiment of the present invention.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings so that those skilled in the art can easily carry out the present invention. The present invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. In order to clearly illustrate the present invention, parts not related to the description are omitted, and similar parts are denoted by like reference characters throughout the specification.

Throughout the specification, when an element is referred to as "comprising ", it means that it can include other elements as well, without excluding other elements unless specifically stated otherwise.

1 is a diagram schematically showing a radio wave analysis and acceleration system according to an embodiment of the present invention.

1, a radio wave analysis and acceleration system 10 according to an embodiment of the present invention includes a data processing unit 100, a space division / index unit 200, and a field strength prediction / visualization unit 300 .

The data processing unit 100 receives input data required for a radio wave analysis using a ray tube technique from a user using a radio wave analysis and acceleration system. The data processing unit (100) transfers the input data to the space partitioning / indexing unit (200). Here, the data and the input data include a 3D terrain model, a 3D building model and an orthoimage image. The 3D terrain model is a numerical value of various geospatial information such as the terrain and the ground within the analysis area and is mainly generated from the digital photogrammetry or LiDAR data. Direction, position, and wall texture information, and is generated mainly by fusion between image data and LiDAR images. Orthographic images are used mainly to provide accurate location information and real images similar to real terrain in visualizing the results of radio waves while containing various features of the terrain or objects, and are mainly produced by digital photogrammetry. Since the technique of generating input data according to the embodiment of the present invention is a known technique, a detailed description will be omitted.

The spatial division / indexing unit 200 divides the input data analysis region into quad trees, divides the faces of the corresponding objects into objects, generates a BSP (Binary Space Partitioning) tree according to the relative positions and directions of the divided faces do. Then, the spatial division / indexing unit 200 generates a BSP tree and transmits it to the electric field strength prediction / visualization unit 300.

The field intensity prediction / visualization unit 300 generates a ray tube tree for finding an effective reflection plane from a transmission point using a BSP tree, and determines an effective propagation path to a reception point based on the generated ray tube tree. Then, the electric field strength predicting / visualizing unit 300 visualizes the effective propagation path on the input data to complete the electric wave analysis.

FIG. 2 is a view schematically showing the space division / indexing unit shown in FIG. 1. FIG. 3 is a diagram illustrating an example of a quadtree according to an embodiment of the present invention. 4 is a diagram illustrating an example of an object division scheme according to an embodiment of the present invention. 5 is a diagram illustrating an exemplary BSP tree generation scheme according to an embodiment of the present invention.

2, the spatial partitioning / indexing unit 200 according to the embodiment of the present invention includes a quadtree partitioning unit 210, an object partitioning unit 220, and a BSP tree generating unit 230.

The quad tree partitioning unit 210 recursively divides the analysis region into four child nodes as shown in FIG. The quad tree partitioning unit 210 determines a space division criterion according to the number of the floor surface of the building and the bottom surface of the building to generate a quadtree. Then, a quad with small size is generated in a region having a large number of faces such as a point P1, and a relatively large quad is generated in a region having a small number of faces such as a point P2. The most important reason for using quad tree partitioning in the embodiment of the present invention is that the BSP tree generating unit 230 maintains a proper number of tree nodes to generate a BSP tree so that the generated BSP tree can have a tree structure .

The object division unit 220 separates the faces of the spatial objects in each quad node when the quadtree division is completed in the quadtree division unit 210. [ For example, the object division unit 220 divides the virtual building 400 into one roof surface 410 and four wall surfaces 420, 430, 440 and 450 as shown in FIG. At this time, the object division unit 220 does not consider the bottom surface because it is covered by the ground, and treats each surface as a single surface with respect to the ground point formed in a lattice form. This is a process of separating the wall surfaces of each building and the bottom surface of the terrain so that each side can be recognized as one object. The faces of the divided spatial objects are compared with the relative positions and orientations of the objects, In order to enable the BSP tree to be generated in the generating unit 230, the effective reflection surface is determined on the 3D coordinate space through 3D culling in the radio wave analysis process in the future.

The BSP tree generation unit 230 generates a BSP tree by designating a relative correlation between all the objects existing in the analysis region as a spatial division tree structure based on a binary method and determining an order between the objects based on the relation. That is, the BSP tree generating unit 230 determines a relationship between a preceding plane and a trailing plane, based on the relative position and direction between the object-divided planes in the object division unit 220. The BSP tree generating unit 230 determines a parent node in the lowermost node of the quadtree generated by the quadtree partitioning unit 210 and determines a child node according to the correlation with the parent node to generate a BSP tree. In this case, the BSP tree has almost the same tree height, and the child nodes on the BSP tree are evenly distributed from the parent node in the right and left directions. This keeps the same search time in most areas for searching the BSP tree.

For example, as shown in FIG. 5, the BSP tree generating unit 230 determines that the C plane 500 is the lowest most preceding node based on the relative positions and orientations between the object-divided planes, ) As the parent node. The BSP tree generation unit 230 determines the B plane 510 and the D plane 520 as child nodes of the C plane 500 according to the correlation with the C plane 500. [ The BSP tree generation unit 230 determines the A side 530 and the E side 540 as child nodes of the B side 510 according to the correlation with the B side 510 to generate a BSP tree.

FIG. 6 is a view schematically showing the electric field intensity predicting / visualizing unit shown in FIG. 1. FIG. 7 is a view showing an example of searching only the effective reflection surface from the entire wall surface by using the 3D curling technique according to the embodiment of the present invention. FIG. 8 is a diagram illustrating an example of an effective radio wave search process using a ray tube technique according to an embodiment of the present invention. 9 is a view showing an example of a visualized screen of a real-time radio wave analysis result according to an embodiment of the present invention.

6, the electric field strength prediction / visualization unit 300 according to the embodiment of the present invention includes a ray tube tree generation unit 310, a propagation path search unit 320, and a result display unit 330 .

When the generation of the BSP tree is completed, the ray tube tree generating unit 310 determines effective reflection planes and effective diffraction points based on the 3D curling technique from the BSP tree, and calculates effective reflection planes and effective diffraction points Create a ray tube tree based on position and orientation. Specifically, when the initial position of the transmission point is determined, the ray tube tree generating unit 310 finds a wall surface from which the radio wave can be firstly reached from the transmission point, and then, based on the reflection and diffraction characteristics, The effective reflection surface and the effective diffraction point are determined through the relationship with the other wall surface in which the ray tube tree is formed.

For example, when a wall surface 600 of a building is covered by an obstacle 700 as shown in FIG. 7, a ray tube tree generating unit 310 generates a ray tube tree based on 3D curling to find an effective reflecting surface The effective reflection surface 800 is determined by removing only the area 900 which is actually blocked between the wall surface 600 and the obstacle 700. In the ray tube tree generating unit 310, since it is computationally complex to directly recognize the non-uniform geometric shape of the effective reflecting surface 800, the surface of the effective reflecting surface 800 is divided into two rectangular shaped regions 810 and 820 ), And stores each rectangular area on the ray tube tree.

According to the embodiment of the present invention, a ray tube tree is generated in the above-described manner to precisely consider the actual reflection or diffraction surface through three-dimensional curling, thereby ensuring a sufficient number of effective propagation paths for predicting the electric field intensity And the accuracy of the analysis result can be improved.

When the generation of the ray tube tree is completed in the ray tube tree generating unit 310, the propagation path searching unit 320 positions the reception point at a point where the electric field intensity is to be predicted, and then the wave generated from the transmission point is reflected and diffracted And searches for all possible effective propagation paths reaching the reception point, one example of which is shown in FIG. The technology for searching for the effective propagation path according to the embodiment of the present invention is a known technology, and a detailed description thereof will be omitted.

After the search for the effective propagation path is completed in the propagation path searching unit 320, the result display unit 330 generates a virtual screen by using input data including a 3D terrain model, a 3D building model, and an orthoimage for realistic visualization . The result display unit 330 displays a visualized image of the real-time radio wave analysis result by positioning the transmission point and the reception point on the virtual screen and projecting the analyzed effective propagation path.

For example, the result display unit 330 displays a 3D terrain model at the bottom as shown in FIG. 9, projects an orthoimage image thereon to visualize a natural ground form, and displays a 3D building model To create a virtual screen. Then, the result display unit 330 displays the analyzed effective propagation path after locating the transmission point and the reception point on the virtual screen, and generates a visualized screen of the real-sensible radio wave analysis result, and displays it.

10 is a diagram illustrating a procedure for performing radio wave analysis at a high speed based on a ray tube technique in a radio wave analysis and acceleration system according to an embodiment of the present invention.

10, the data processing unit 100 of the radio wave analysis and acceleration system 10 according to the embodiment of the present invention receives input data requesting radio wave analysis from a user using the radio wave analysis and acceleration system (S900) .

The spatial division / indexing unit 200 of the radio wave analysis and acceleration system 10 recursively divides the input data analysis region into four child nodes to generate a quadtree (S910). The spatial partitioning / indexing unit 200 performs object partitioning on the corresponding surface of the spatial object in the node of the quadtree (S920). The spatial segmentation / indexing unit 200 specifies a relative correlation between all the objects existing in the analysis region, and determines a sequence between the objects based on the relation, thereby generating a BSP tree (S930).

When the generation of the BSP tree is completed and the initial position of the transmission point is determined, the field intensity prediction / visualization unit 300 of the radio wave analysis and acceleration system 10 determines an effective reflection plane from the BSP tree to generate a ray tube tree (S940 ). When the generation of the ray tube tree is completed, the electric field intensity predicting / visualizing unit 300 positions the reception point at a point where electric field strength is to be predicted, so that all the radio waves transmitted from the transmission point arrive at the reception point through reflection and diffraction The effective propagation path is searched (S950). The field strength prediction / visualization unit 300 generates a virtual screen using the input data, displays the visualized screen by projecting the effective propagation path after locating the transmission point and the reception point for the virtual screen (S960).

As described above, in the radio wave analysis and acceleration system 10 according to the embodiment of the present invention, a quadtree is generated and divided into objects, and a BSP tree is generated according to the relative correlation between the objects, As the time to create the tube tree is shortened, the search time for finding the effective propagation path can be shortened. The accuracy of the effective propagation path search can be improved by searching the accurate effective reflection surface and the effective diffraction point from the wall of the building through the radio wave analysis technique based on the ray tube technique through 3D curling.

The embodiments of the present invention described above are not implemented only by the apparatus and method, but may be implemented through a program for realizing the function corresponding to the configuration of the embodiment of the present invention or a recording medium on which the program is recorded.

While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it is to be understood that the invention is not limited to the disclosed exemplary embodiments, It belongs to the scope of right.

Claims (17)

In a radio wave analysis accelerating system based on a 3D spatial index and a 3D curling technique,
A method for generating a BSP tree based on a correlation between objects, the method comprising: receiving input data for radio wave analysis using a ray tube technique, generating a quad tree by dividing an analysis area of the input data, Index part, and
When the generation of the BSP tree is completed, an effective reflection plane is determined based on the 3D curling technique to generate a ray tube tree, and a field strength prediction /
/ RTI >
The space division /
An object division unit for dividing the faces of the spatial objects in each quad node and processing the faces of the spatial objects into one object when the creation of the quadtree is completed;
A BSP tree generating unit for generating the BSP tree by designating a relative correlation between all the objects existing in the analysis area when the object segmentation is completed;
And the radio wave analysis accelerating system. The method according to claim 1,
The space division /
And a quad tree partitioning unit for dividing the analysis region into predetermined child nodes to generate the quadtree. 3. The method of claim 2,
Wherein the quadtree partitioning unit generates a quadtree by determining a space division criterion according to the number of the floor surface of the building and the floor surface of the building,
Wherein a number of quads generated in an area having a relatively large number of wall surfaces of the building and a bottom surface of the terrain is greater than the number of quads generated in an area having a relatively small number of floor surfaces of the building and a wall surface of the building, . delete delete The method according to claim 1,
Wherein a parent node of the BSP tree is determined at a lowest node of the quadtree. The method according to claim 6,
The space division /
And determines a child node of the parent node by determining a relationship between a preceding face and a following face according to a relative correlation between all the objects. The method according to claim 1,
The field strength prediction /
When the building wall surface of the analysis area is covered by an obstacle,
Determining the effective reflection plane by removing the non-reflection surface blocked between the building wall surface and the obstacle based on the 3D curling technique when the creation of the BSP tree is completed and the location of the transmission point to transmit the radio waves is determined, And a ray tube tree generating unit for generating the ray tube tree by dividing the effective reflection plane by a predetermined portion. 9. The method of claim 8,
The field strength prediction /
And a radio wave path searching unit for searching for the effective propagation path in which a radio wave generated from the transmission point arrives after a reception point is located at a point where the electric field strength is predicted when generation of the ray tube tree is completed, . 10. The method of claim 9,
The field strength prediction /
And a result display unit for generating a virtual screen using the input data when the search for the effective propagation path is completed and displaying a visualized screen by projecting the effective propagation path after locating the transmission point and the reception point, Analytical Fastening System. 11. The method according to any one of claims 1 to 3 and 6 to 10,
Wherein the input data includes a 3D terrain model, a 3D building model, and an orthoimage. A method for performing radio wave analysis based on a 3D spatial index and a 3D curling technique at a high speed,
Receiving input data for the radio wave analysis,
Dividing an analysis region of the input data into a quad tree to divide an object,
Generating a BSP tree based on a correlation between the objects,
When the generation of the BSP tree is completed, generating a ray tube tree by determining an effective reflection plane based on the 3D curling technique,
Searching for an effective propagation path by locating a reception point at a point where electric field intensity is to be predicted in the ray tube tree
/ RTI >
Wherein the object splitting comprises:
Dividing the analysis region into predetermined child nodes to generate the quadtree, and
Dividing a face of the space object in the node of the quadtree into a single object,
Wherein the generating the BSP tree comprises:
Designating a relative correlation between all the objects existing in the analysis area when the object segmentation is completed;
Determining a parent node in the lowermost node of the quadtree based on the correlation, and
Determining a child node according to a correlation with the parent node
Wherein the radio wave analysis accelerating method comprises: delete delete 13. The method of claim 12,
Wherein generating the ray tube tree comprises:
Determining the effective reflecting surface by removing a non-reflecting surface blocked between the building wall surface and the obstacle when a building wall surface of the analysis area is covered with an obstacle and a position of a transmission point to transmit the radio wave is determined,
And generating the ray tube tree by dividing the effective reflection surface by a predetermined portion. 16. The method of claim 15,
Wherein the step of searching for the effective propagation path comprises:
Positioning the reception point at a point where the electric field strength is to be predicted when generation of the ray tube tree is completed, and
And searching the effective propagation path through which the radio wave generated from the transmission point arrives at the reception point. 17. The method according to any one of claims 12 to 16,
Wherein the input data includes a 3D terrain model, a 3D building model, and an orthoimage.

Images