WO2011062305A1 - Method for representing a three-dimensional object, method for processing topological queries on a three-dimensional object, and apparatus employing same - Google Patents

Abstract

Disclosed are a method for representing a three-dimensional object, a method for processing topological queries on a three-dimensional object, and an apparatus employing same. The method for representing a three-dimensional object comprises the steps of: extracting top and bottom surface footprints of a three-dimensional object; and, when the top and bottom surface footprints of the three-dimensional object are the same, specifying the three-dimensional object using information on the top and bottom surface footprints. Thus, not only can a three-dimensional object be represented using a smaller amount of data, but processing topological queries on a three-dimensional object can be rendered easy.

Description

3D object representation method, 3D object topology query processing method and apparatus using the same

The present invention relates to an object expression method, a three-dimensional object topology query processing method, and an apparatus using the same, and more particularly, to a method for representing a three-dimensional object, processing a phase query of a three-dimensional object, and an apparatus using the same.

The three-dimensional topology between objects is an essential component of the information used to analyze spatial characteristics. The topology of three-dimensional objects is much more difficult than the analysis of two-dimensional topologies because of the complexity of three-dimensional geometry. Thus, performing a phase query operation in a database management system in which information about a 3D object is stored is much more difficult and inefficient than that in a database management system in which information about a 3D object is stored. However, since the object is mostly composed of three dimensions, the three-dimensional phase is inevitable in analyzing the object.

The present invention provides a method for efficiently representing a three-dimensional object, and a method and apparatus for identifying the phase of the three-dimensional object with a smaller data amount to solve the above problems.

According to the present invention for achieving the above object, a three-dimensional object representation method, comprising: extracting the footprint of the top and bottom surfaces of the three-dimensional object; And specifying the three-dimensional object based on the information of the upper and lower surfaces if the footprints of the upper and lower surfaces of the three-dimensional object are the same.

The specifying of the 3D object may include: determining whether the top and bottom surfaces of the 3D object are flat; And when one of the top and bottom surfaces of the 3D object is not a plane, the top and bottom surfaces of the 3D object are correspondingly divided so that the top and bottom surfaces of the 3D object are flat, and the divided top and bottom surfaces It is preferable to include; specifying the three-dimensional object with information.

On the other hand, the three-dimensional object query processing method according to the present invention for achieving the above object, in the three-dimensional object topological query processing method of the same footprint of the top and bottom surface, the footprint phase of the query object and the surrounding objects Determining; Determining a height phase of the query object and the surrounding object; And determining a phase of the query object and the surrounding object from a footprint phase and the height phase.

The determining of the phase of the query object and the neighboring object may be performed by using a plurality of layers, and each of the plurality of layers may be configured using an object topology determination diagram composed of topological elements with no possibility of coexistence.

Further, after selecting a phase element corresponding to the footprint phase in the object phase determination diagram and a phase element corresponding to the height phase in the object phase determination diagram, the phase of the lowest layer that can coexist with the selected phase elements It is preferable to determine an element as the phase of the query object and the surrounding object.

The determining of the height phase may include a height phase with respect to the upper and lower points of the query object and the peripheral object corresponding to a point in a duplicate footprint of the query object and the surrounding object. Determining a point height phase; And determining the height phase from the point height phase.

Further, the height phase determination step is preferably made of a height phase determination diagram composed of a plurality of hierarchies, each of which consists of a height phase element that is not coexistable.

The point height phase is two or more, the height phase element corresponding to one of the point height phases is selected in the height phase determination diagram, and the height phase element corresponding to the other one of the point height phases is the height phase. After selection in the decision diagram, it is desirable to determine the height phase element of the lowest layer that can coexist with the selected height phase elements.

The invention may also be a computer readable recording medium having recorded thereon a program for executing the method on a computer.

On the other hand, according to the present invention for achieving the above object, the three-dimensional object representation apparatus, the extraction unit for extracting the footprints of the upper and lower surfaces of the three-dimensional object; And a specifying unit specifying the three-dimensional object based on the information of the upper and lower surfaces if the footprints of the upper and lower surfaces of the three-dimensional object are the same.

The specifying unit may include: a determiner configured to determine whether upper and lower surfaces of the 3D object are flat; If any one of the top and bottom surfaces of the three-dimensional object is not a plane, the upper and lower portions of the three-dimensional object to divide the upper and lower surfaces of the three-dimensional object correspondingly; includes; Do.

On the other hand, the three-dimensional object query processing apparatus according to the present invention for achieving the above object, in the apparatus for processing a phase query of the three-dimensional object of the same footprint of the top and bottom, the footprint of the query object and the surrounding objects A first determining unit determining a phase; A second determiner configured to determine a height phase of the query object and the surrounding object; And a third determiner configured to determine a phase of the query object and the neighboring object from the footprint phase and the height phase.

The third determiner is configured to determine a phase of the query object and the neighboring object by using an object topology determination diagram, which is composed of a plurality of hierarchies, and each of the hierarchical hierarchies is composed of topological elements that are not likely to coexist. It is preferable.

Further, after selecting a phase element corresponding to the footprint phase in the object phase determination diagram and a phase element corresponding to the height phase in the object phase determination diagram, the phase of the lowest layer that can coexist with the selected phase elements It is preferable to determine an element as the phase of the query object and the surrounding object.

The second determiner may further include a point height phase that is a height phase with respect to the upper and lower points of the query object and the peripheral object corresponding to a point in the overlapped footprint among the footprints of the query object and the surrounding object. Point height phase determination unit for determining the; And a height upper determination unit determining the height phase from the point height phase.

In addition, the height phase determination unit is composed of a plurality of hierarchies, it is preferable to determine the height phase by using a height phase determination diagram composed of a height phase element that each of the plurality of hierarchies are not coexist.

The point height phase is two or more, and the height height phase determining unit selects a height phase element corresponding to one of the point height phases from the height phase determination diagram and corresponds to the other of the point height phases. After selecting the height phase element in the height phase determination diagram, it is preferable to determine the height phase element of the lowest layer that can coexist with the selected height phase elements.

1 is a view showing an example of a three-dimensional object according to an embodiment of the present invention,

2 is a diagram illustrating an example of a three-dimensional object to which a prism model is applicable according to an embodiment of the present invention;

3 illustrates a phase of a three-dimensional object having a phase of the same two-dimensional footprint according to an embodiment of the present invention;

4 is a view showing the height phase of the three-dimensional object according to an embodiment of the present invention,

FIG. 5 illustrates a superimposed footprint and height phase in accordance with one embodiment of the present invention; FIG.

6 illustrates a point phase at a pair of points according to an embodiment of the present invention;

7 is a height phase determination diagram according to an embodiment of the present invention;

8 is an object phase determination diagram according to an embodiment of the present invention;

9 is a diagram illustrating a phase of an object for validating an object phase determination diagram according to an embodiment of the present invention;

10 is a block diagram of an apparatus for storing a 3D object as a prism model according to an embodiment of the present invention;

11 illustrates a method in which the apparatus of FIG. 10 stores a 3D object as a prism model.

12 is a block diagram of an apparatus for processing a topology query of an object specified by a prism model according to an embodiment of the present invention;

FIG. 13 is a flowchart for describing a method of processing a topology query of an object by the apparatus of FIG. 12.

Explanation of symbols on the main parts of the drawings

1010: extraction unit 1020: footprint determination unit

1030: plane determination unit 1040: plane divider

1220: footprint extractor 1230: footprint phase determiner

1240: overlapped footprint determiner 1250: point height phase determiner

1260: height phase determination unit 1270: object phase determination unit

EXAMPLE

Hereinafter, with reference to the drawings will be described the present invention in more detail.

The terms or words used in this specification and claims are not to be construed as being limited to their ordinary or dictionary meanings, and the inventors may appropriately define the concept of terms in order to best describe their invention. It should be interpreted as meaning and concept corresponding to the technical idea of the present invention based on the principle that the present invention.

Therefore, the embodiments described in the specification and the drawings shown in the drawings are only one of the most preferred embodiments of the present invention and do not represent all of the technical idea of the present invention, various modifications that can be replaced at the time of the present application It should be understood that there may be equivalents and variations.

In order to represent a three-dimensional object with the same top and bottom footprints, a new model is proposed in the present invention, a prism model.

The prismatic model is the same footprint of the top and bottom planes, which are not parallel to the axis representing the height values of the objects on the top and bottom surfaces, and the height for any point on the top surface for any point on the bottom surface. It is a method of expressing a 3D object using the same or higher height.

As described above, the prism model has the following effects.

First, the prism model is simpler than other techniques for specifying three-dimensional objects, and has a smaller geometrical configuration. Therefore, the prism model requires a smaller amount of data when storing, transmitting, and calculating geometric information about three-dimensional objects. It works.

For example, FIG. 1 is a diagram illustrating an example of a 3D object according to an embodiment of the present invention. As shown in FIG. 1, in order to specify a cube, a general geography markup language (GML) method requires eight corner information, twelve line information, and six face information. However, the prism model defined herein requires eight corner information, eight line information, and two plane information.

By using the prism model as described above, the 3D object may be defined as one or more prism models. When a 3D object is specified by a plurality of prismatic models, the 3D object may be defined using a phase regarding a footprint and a phase regarding a height.

2 is a diagram illustrating an example of a three-dimensional object to which a prism model according to an embodiment of the present invention is applicable.

The three-dimensional object illustrated in FIG. 2 has the same two-dimensional footprint. Accordingly, the 3D object illustrated in FIG. 2 may be represented by a prism model. Since the entire top surface of the 3D object illustrated in FIG. 2 is not a plane, the top surface is divided to be a plane, and the bottom surface corresponds to the divided top surface. Also divide.

Then, the three-dimensional object illustrated in FIG. 2 has a first prism model having a first bottom surface F1 = (P1, P2, P8, P9) and a first top surface F4 = (P10, P11, P19, P20). A second prism model (EP1 = (F1, F4)), a second bottom surface (F2 = (P2, P3, P7, P8)) and a second top surface (F5 = (P11, P12, P17, P19)) Third prism model (EP3) having EP2 = (F2, F5)) and third bottom surface (F5 = (P11, P12, P17, P19)) and third top surface (F6 = (P13, P14, P15, P16)) = (F3, F6)).

In the prism model, the upper and lower surfaces for specifying an object are extruded surfaces, and each edge of the upper and lower surfaces is an extrusive curve. It is defined as.

Second, since the prismatic model includes the concept of footprint, the phase between a plurality of three-dimensional objects can be primarily inferred as the phase of the footprint. Thus, query processing of three-dimensional objects becomes easier.

Specifically, the phase between the plurality of three-dimensional objects and the phase between the footprint is 'disjoint' 'cover', 'covered by', 'contain', 'inside' ',' Meet ',' overlap 'and' equal '.

Since the phase of the 3D object is related to the phase of the 2D footprint, the phase of the 3D object may be inferred from the phase between the 2D footprints. It goes without saying that each three-dimensional object is specified by a prism model.

For convenience of explanation, two three-dimensional objects are described as an example, and it is assumed that the three-dimensional objects are each specified by one prism model.

3 is a diagram illustrating a phase of a three-dimensional object having a phase of the same two-dimensional footprint according to an embodiment of the present invention.

As shown in FIG. 3, if the phase of the two-dimensional footprint is in an 'overlapping' relationship, the phase of the three-dimensional object may be one of 'overlapping', 'contacting' and 'separation'.

In this way, the phase of the two-dimensional footprint and the phase of the three-dimensional object are shown in Table 1 below.

Table 1

As shown in Table 1, if the footprint phase is 'separated', then the object's phase is 'separated'. Therefore, the phase of the object can be determined only by the footprint phase. Thus, the process of processing the topology query of the object can be simplified.

In addition, even if the footprint phase is 'contact', the object's phase is one of 'contact' and 'separation', so it is only necessary to determine whether the object's phase is 'contact' or 'separation' during the phase query.

Thus, the footprint phase functions to filter out candidates that can be the phase of the object when determining the phase of the object.

In other words, knowing the topology between their 2D footprints (TP-F), candidates for the topology between the 3D objects (TP-3D) can be obtained from Table 1. .

Then, in order to know the exact phase of the three-dimensional object, it is possible to use the height phase of the top and bottom of the two objects.

4 is a diagram illustrating the height phase of a three-dimensional object according to an embodiment of the present invention.

As shown in FIG. 4, the topology of elevation (TP-ER) of a three-dimensional object is also referred to as 'disjoint', 'meet', 'equal', and 'overlapping'. (overlap), 'contain', 'inside', 'cover' and 'covered by'.

The height phase of the three-dimensional object as described above may be obtained by using a duplicated footprint among the footprints of the two objects.

FIG. 5 illustrates a superimposed footprint and height phase in accordance with one embodiment of the present invention. FIG.

As shown in FIG. 5, only some of the footprints of the first object p and the second object q overlap.

The height phase of the object can be inferred from the Topology of Elevation at Point (TP-EP) because the top and bottom surfaces of the object are planar.

And, the point height phase refers to the height phase of the points on the top and bottom of the objects corresponding to the overlapped footprint. More specifically, the point height phase may be referred to as a height phase for points on the top and bottom surfaces of objects corresponding to points in the overlapping footprint.

Preferably, the points are points of the upper and lower surfaces of the objects corresponding to the pair of points on the lines of the overlapping footprint, and the pair of points are preferably on different lines.

In particular, where the overlapped footprint includes four lines, it is desirable that a pair of points are each on the facing line.

6 is a diagram illustrating point phases at a pair of points according to an embodiment of the present invention.

As shown in FIG. 6, the point phases at the pair of points v1 and v2 are 'overlap' and 'overlap', respectively. The height phase of the object having the point phase described above is 'overlapping'.

In this way, the height phase can be determined from the point height phase.

7 is a height phase determination diagram according to an embodiment of the present invention.

As shown in FIG. 7, the height phase determination diagram is composed of a plurality of layers, each layer including one or more height phases. The height phase in each layer is called the height phase element.

Height phase elements in the same hierarchy cannot coexist with each other, and height phase elements in different hierarchies may or may not coexist. Height phase elements of different layers connected by lines of FIG. 7 indicate that the height phase elements can coexist.

The height phase determination diagram of FIG. 7 makes it easier to obtain the height phase. Specifically, the height phase element corresponding to the point height phase may be selected in the height phase determination diagram, and the height phase element of the lowest layer that can coexist with the plurality of height phase elements may be determined as the height phase of the object.

For example, the point height phases shown in FIG. 6 are 'overlap' and 'overlap', respectively. In the height phase determination diagram, the height phase element of the lowest layer that can coexist with the 'overlap' height phase element and the 'overlap' height phase element is 'overlap'. Thus, 'overlap' is the height phase of the object, which is the same as described above, so the height phase determination diagram shown in FIG. 7 is valid.

Knowing the footprint phase of the object and the height phase of the object can determine the phase of the object.

8 is an object phase determination diagram according to an embodiment of the present invention.

As shown in FIG. 8, the object topology determination diagram is also composed of a plurality of layers, each layer comprising one or more object topologies. The object topology in each layer is called the phase element. The phase element may be a footprint phase or a height phase.

Phase elements in the same layer may not coexist, but phase elements in different layers may or may not coexist. The phase elements of different layers connected by the lines of FIG. 8 indicate that the phase elements can coexist.

By using the object topology determination diagram of FIG. 8, it is easier to obtain the object topology. Specifically, when the phase element corresponding to the footprint phase is selected in the object phase determination diagram and the phase element corresponding to the height phase is selected in the object phase determination diagram, the lowest hierarchical phase element that can coexist with the selected phase elements is an object. It is determined by phase.

Hereinafter, the validity of the object topology determination diagram is verified.

9 is a diagram illustrating a phase of an object for validating an object phase determination diagram according to an embodiment of the present invention.

The phases of the footprints of the first object p and the second object q in FIG. 9 are "contained," and the height phases of the first object p and the second object q are "same." In addition, the phase of the first object and the second object is 'shield'.

In the object phase determination diagram, the object phase determination diagram is valid because the phase elements of the lowest hierarchy that can coexist with the phase elements 'contains' and 'identical' are 'shield'.

As such, the phase of the three-dimensional object can be easily obtained with a smaller data amount by using the prism model of the present invention.

Hereinafter, an apparatus and a method for representing a 3D object as a prism model and expressing the object using the prism model will be described with reference to the accompanying drawings.

FIG. 10 is a block diagram of an apparatus for storing a 3D object as a prism model, and FIG. 11 is a flowchart illustrating a method for storing the 3D object as a prism model according to an embodiment of the present invention. .

10 and 11, when information about a 3D object is input (S1110-Y), the extractor 1010 extracts an upper surface and a lower surface using a footprint from the 3D object (S1120). The information about the three-dimensional object is information in which the top, bottom and side surfaces are combined into one. The extractor extracts only the information of the top and bottom surfaces of the 3D object except for the side surface. In addition, in extracting the top and bottom surfaces of the extractor 1010, a simple feature geometry (SFG) method may be used. Since the SFG method is a conventional technique, a detailed description thereof will be omitted.

The footprint determination unit 1020 generates a footprint for the top and bottom surfaces extracted by the extraction unit, and determines whether the generated footprint is the same (S1130). This is because a three-dimensional object can be expressed as a prism model only when the top and bottom footprints are the same.

If the top and bottom footprints are the same (S1130-Y), the plane determination unit 1030 determines whether the top and bottom surfaces of the object are flat (S1140). There may be several ways to determine whether the top and bottom surfaces are flat. As an example, the plane determination unit 1030 may determine that the top surface and the bottom surface are flat when each of the top surface and the bottom surface is represented by one plane equation.

If it is determined that the top and bottom surfaces are flat (S1140-Y), the plane determination unit 1030 stores the information of the top and bottom surfaces in the storage unit 1050 (S1150). As such, if the top and bottom surfaces are each one plane, the object is stored as one prism model.

However, if it is determined that at least one of the top and bottom surfaces is not flat (S1140-N), the information of the top and bottom surfaces is applied to the plane divider 1040, and the plane divider 1040 divides the top and bottom surfaces ( S1160). When the plane divider 1040 divides the top and bottom surfaces, it is preferable to divide the top and bottom surfaces so that the footprints of the top and bottom surfaces remain the same.

It is also preferable to divide the upper and lower surfaces so that the degree of division is minimal. For example, if an object has a top surface consisting of two planes and a bottom surface consisting of one plane, the plane divider 1040 may have a footprint of the top and bottom surfaces around a boundary line between the two planes with respect to the top surface. The top and bottom are divided so that they remain the same. The divided objects are stored as two prism models.

Meanwhile, the plane determiner 1030, the plane divider 1040, and the storage 1050 of FIG. 10 will be described in more detail with reference to the accompanying drawings.

The terms or words used in this specification and claims are not to be construed as being limited to their ordinary or dictionary meanings, and the inventors may appropriately define the concept of terms in order to best describe their invention. It should be interpreted as meaning and concept corresponding to the technical idea of the present invention based on the principle that the present invention.

Therefore, the embodiments described in the specification and the drawings shown in the drawings are only one of the most preferred embodiments of the present invention and do not represent all of the technical idea of the present invention, various modifications that can be replaced at the time of the present application It should be understood that there may be equivalents and variations.

According to the present invention, if a three-dimensional object having the same footprint on the upper and lower surfaces is identified using a prism model, not only can the three-dimensional object be represented with a smaller amount of data, but also in processing the phase query of the three-dimensional object. It is easy.

Claims (17)

Extracting footprints of the top and bottom surfaces of the three-dimensional object; And And specifying the three-dimensional object with the information of the upper and lower surfaces when the upper and lower surfaces of the three-dimensional object are the same. The method of claim 1, Specifying the three-dimensional object, Determining whether the top and bottom surfaces of the 3D object are planar; And If any one of the top and bottom surfaces of the 3D object is not a plane, the top and bottom surfaces of the 3D object are correspondingly divided and divided so that the top and bottom surfaces of the 3D object are flat, and the divided top and bottom information are divided. Specifying the three-dimensional object with a; three-dimensional object representation method comprising a. In the phase query processing method of a three-dimensional object of the same top and bottom footprint, Determining a footprint topology of the query object and surrounding objects; Determining a height phase of the query object and the surrounding object; And And determining the phases of the query object and the surrounding object from a footprint phase and the height phase. The method of claim 3, Determining the phase of the query object and the surrounding object 3. The method of claim 3, wherein each of the plurality of hierarchies uses an object topology determination diagram composed of topological elements with no possibility of coexistence. The method of claim 4, wherein After selecting a phase element corresponding to the footprint phase in the object phase determination diagram and a phase element corresponding to the height phase in the object phase determination diagram, a phase element of the lowest layer that can coexist with the selected phase elements is selected. 3D object topology query processing method, characterized in that determined by the phase of the query object and the surrounding object. The method of claim 4, wherein Determining the height phase, Determining a point height phase that is a height phase with respect to a point on the top and bottom surfaces of the query object and the surrounding object corresponding to a point in a duplicate footprint of the query object and the surrounding object; And And determining the height phase from the point height phase. The method of claim 6, The height phase determination step, 3. The method of claim 3, wherein the plurality of hierarchies use a height phase determination diagram, wherein each hierarchical layer is composed of non-coexistable height phase elements. The method of claim 7, wherein The point height phase is two or more, Selecting a height phase element corresponding to one of the point height phases in the height phase determination diagram and selecting a height phase element corresponding to the other one of the point height phases in the height phase determination diagram, And determining a height phase element of the lowest layer that can coexist as the height phase. A computer-readable recording medium having recorded thereon a program for executing the method according to any one of claims 1 to 8. An extraction unit for extracting a footprint of the top and bottom surfaces of the three-dimensional object; And And a specifying unit specifying the three-dimensional object based on the information of the upper and lower surfaces if the upper and lower surfaces of the three-dimensional object are the same. The method of claim 10, The specific unit, A determination unit to determine whether the top and bottom surfaces of the 3D object are flat; And If the one of the upper surface and the lower surface of the three-dimensional object is not a plane, the partition unit for correspondingly dividing the upper and lower surfaces of the three-dimensional object correspondingly so that the upper and lower surfaces of the three-dimensional object; 3-D object representation apparatus. The top and bottom footprints are on devices that handle topological queries of the same three-dimensional object, A first determiner configured to determine a footprint phase of the query object and a neighboring object; A second determiner configured to determine a height phase of the query object and the surrounding object; And And a third determiner configured to determine the phases of the query object and the neighboring object from the footprint phase and the height phase. The method of claim 12, The third determination unit, A three-dimensional object comprising a plurality of layers, wherein each of the plurality of layers determines a phase of the query object and the surrounding object by using an object topology determination diagram that is composed of a phase element with no possibility of coexistence. Topology Query Processing Unit. The method of claim 13, Selecting a phase element corresponding to the footprint phase from the object phase determination diagram and a phase element corresponding to the height phase from the object phase determination diagram, and then selecting a phase element of the lowest layer that can coexist with the selected phase elements. 3D object topology query processing apparatus, characterized in that determined by the phase of the query object and the surrounding object. The method of claim 12, The second determination unit, A point height phase determination unit for determining a point height phase, which is a height phase with respect to a point on the top and bottom surfaces of the query object and the surrounding object corresponding to a point in a duplicate footprint of the query object and the surrounding object. ; And And a height determiner configured to determine the height phase from the point height phase. The method of claim 15, The height phase determination unit, 3. The apparatus of claim 3, wherein the height phase is determined using a height phase determination diagram that is configured of a plurality of hierarchical layers, each of the plurality of hierarchical layers. The method of claim 16, The point height phase is two or more, The height phase determination unit, Selecting a height phase element corresponding to one of the point height phases in the height phase determination diagram and selecting a height phase element corresponding to the other one of the point height phases in the height phase determination diagram, And determining the height phase element of the lowest layer that can coexist as the height phase.

Images