JPH05266213A - High-speed display system for three-dimensional space data - Google Patents

Abstract

PURPOSE:To display a large quantity of space data at a high speed while keeping a good outward appearance by generating space data having plural definitions for one three-dimensional object and selecting and displaying data in accordance with the distance from a visual point. CONSTITUTION:Desired three-dimensional space data read out from a disk 4 through a disk controller 3 is loaded to a main storage device 2. The display processing of the three-dimensional scene from a given visual point is executed in accordance with preliminarily determined procedures by the access of a processing processor 1. A memory controller 5 describes the result of three- dimensional scene display processing in a picture memory 6. Contents of the picture memory 6 are displayed on a CRT 8 through a CRT controller 7 by the instruction of the processing processor 1. A mouse interface 9 gives input data of indication of three-dimensional space data, indication of the visual point on the three-dimensional scene display, or the like to the processing processor 1 by the operation of a mouse 10.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for displaying a large amount of three-dimensional spatial data over a wide area at high speed and effectively.

[0002]

2. Description of the Related Art In recent years, CG has been capable of high-speed display with the development of hardware. But,
There is a limit to the amount that can be displayed in real time, and in order to solve this problem, conventionally, the following four methods have been proposed.

First, in order to reduce the display load, (1) wire frame display, and to limit the amount of data to be displayed, (2) display surface sorting (3) area management (Shoshodo Image Database・ Masao Sakauchi and Hiroshi Osawa) (4) Data management using an occluding surface (Visibility Preprocessing for Interactive Walkthr
ough, Seth J. Teller, Carlo H. Sequin, Univ. of Ca
lifornia at Berkeley, Computer Graphics, Volume 2
5, Number 4, July 1991).

Of these, the method (1) has a drawback that it is difficult to understand when the object is a complicated three-dimensional object or when the objects are dense.

In the method (2), when there are many faces, the amount of faces to be sorted is huge, the sorting process takes time, and high-speed display cannot be performed.

The method (3) is insufficient because the speed cannot be sufficiently increased when the individual shapes are complicated.

The method (4) uses a method in which the space is divided into two-dimensional areas, the space is managed for each area partitioned by the shielding surface, and the visible area from a certain area is calculated in advance. .. Then, when the line of sight is determined, only polygons within the visible region are drawn. However, this method is effective in that it is divided into rooms indoors, but has the drawback that it is not very effective outdoors or in a normal three-dimensional space.

Further, in the computer graphics display device of Japanese Patent Publication No. 1-20527, since an object distant from the viewpoint is generally small in size on the surface image, the shape of such an object is reduced. A method of reducing the total number of displayed polygons (triangular or quadrangular patches) forming the surface of an object by using the simplified model of is proposed. However, this method has the following drawbacks.

(I) When a large number of objects exist,
In order to decide whether to use the original model or the simplified model, the distance from the viewpoint has to be calculated for all objects, and the display time increases as the number increases.

(Ii) A desired simplification cannot be automatically performed on a three-dimensional object having a complicated shape.

(Iii) It was not possible to control the display speed to be constant during continuous viewpoint movement. That is, dynamic control of model selection could not be performed.

[0012]

As described above, in the past, displaying a large amount of data at a high speed and maintaining a good appearance to some extent were contradictory, and it was difficult to achieve both at the same time.

Further, there is a drawback in the related art that it is not possible to efficiently and effectively perform three-dimensional display on a large number of three-dimensional objects having complicated shapes by simplifying the shapes.

The present invention has been made in order to solve such a conventional problem, and its first object is to provide a three-dimensional spatial image high-speed display system for displaying a large amount of spatial data at high speed while maintaining a good appearance. Is to provide.

A second object is to provide a three-dimensional spatial image high-speed display system for displaying a large amount of spatial data at high speed by optimizing the total amount of display data while suppressing deterioration of the generated image as much as possible. ..

[0016]

In order to achieve the above object, the inventions according to claims 1 to 3 of the present invention devise a management method of spatial data, and when a viewpoint is given, the minimum required data is dynamically set. Is to be selected. Spatial data is managed as follows.

(1) Spatial data having a plurality of levels of detail are created for one three-dimensional object. Data with an appropriate level of detail is selected and displayed according to the distance from the viewpoint. In the calculation of the distance from the viewpoint used for the determination, the distance between the viewpoint and each object may be calculated strictly, but it is also possible to approximate the distance with the local region including the object.

(2) The space is defined by the distribution of the constructs
The area is divided into one, two or three dimensions and managed. The hierarchy of the selected area is selected according to the position of the viewpoint, and the visible area is selected according to the visual field range. Specifically, when the viewpoint is located at a place where the user can see far away, the area is selected with a coarse size, and when only the vicinity is visible, the area is selected with a fine size.

(3) If there is a large occluding surface, the space is divided by this occluding surface, and the three-dimensional data is managed in this space. When the viewpoint is specified, the space occluded by the occluding surface is excluded from the drawing target in advance.

(4) With respect to a distance farther than a certain threshold from the viewpoint, even if the shape is accurately displayed, it is meaningless for the human to discriminate on the display screen, so that a fixed pattern created in advance is displayed. ..

On the other hand, in the invention of claim 4 of the present application, the method of expressing the shape of the three-dimensional object and the method of managing the whole data are devised so that the minimum necessary data is dynamically selected when the viewpoint is given. I have to. The basic idea is as follows.

First, the given raw data is displayed as the most detailed data, and the nearby objects are displayed in more detail, and the far objects are displayed more coarsely by hierarchically simplifying the raw data according to the distance.

As parameters for hierarchical simplification, (i) the number of divisions of the distance (equal to the number of simplification levels), (ii) the boundary value in the distance division, and (iii) the value for controlling the degree of simplification of the shape. There is.

Generally, (i) depends on the size of the data set to be displayed and the memory capacity for holding, and (ii)
Depending on the value of (i) and the statistical properties related to the size of the object in the display data set and the size of the three-dimensional space occupied by the data, the value of (ii) and the object of (iii) are displayed on the display screen. It is determined based on the size determined by the display resolution at that time, and simplification is automatically performed by approximating the three-dimensional shape of the object with the specified accuracy.

The specific procedure is (i) creation of hierarchical simplified data and area division management, (ii) dynamic data selection using area division management when a viewpoint is given, and (iii) necessary data It is composed of three parts: display.

[0026]

According to the inventions of claims 1 to 3 configured as described above, the number of faces to be drawn without changing the appearance by changing the detail level of the data according to the distance from the viewpoint. Can be effectively reduced, so that a high-speed three-dimensional image can be displayed.

Further, when the visual field range is determined, necessary spatial data can be efficiently extracted by the hierarchical divided area management, so that the optimum image corresponding to the position of the viewpoint is displayed at high speed. ..

Furthermore, by managing the space using the occluding surface, it is possible to eliminate the load of drawing a three-dimensional object which is clearly invisible.

According to the fourth aspect of the present invention, the optimum three-dimensional image can be displayed in the trade-off relationship between the degree of deterioration of the generated image and the speed of the display speed. Also,
Effective simplification is possible for a three-dimensional object having a complicated shape.

[0030]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 shows a schematic configuration of a system to which a high-speed display method for three-dimensional spatial data according to the present invention is applied. In the figure, reference numeral 1 is a processor, and this processor 1 controls the entire system through a system bus 1a. In this case, the system bus 1a
A main storage device 2, a disk controller 3, a memory controller 5, a CRT controller 7, and a mouse interface 9 are connected to the.

The main memory 2 is a disk controller 3
The desired three-dimensional spatial data read from the disk 4 via the. Then, from this state, by the access by the processing processor 1, the display processing of the three-dimensional scene from the given viewpoint is executed in accordance with a predetermined procedure.

The memory controller 5 is for drawing the result of the three-dimensional scene display processing in the image memory 6. Then, the contents of the image memory 6 are transferred to the CRT via the CRT controller 7 by the instruction of the processor 1.
It is supposed to be displayed on 8.

The mouse interface 9 is adapted to give input data to the processor 1 such as an instruction of the three-dimensional space data to be retrieved and displayed by operating the mouse 10 during the three-dimensional scene display processing and an instruction of the viewpoint in the three-dimensional scene display. ing.

Next, a high-speed display process of three-dimensional space data will be described by taking a cityscape display based on a city database, which is a database of three-dimensional information about a city.

2 and 3 show the procedure flow of the processing executed by the processing processor 1. In step 1, the XX section is designated with the mouse from the index displayed on the screen, and the spatial data to be displayed in the city database is loaded from the disk to the memory. Now, the city database includes three-dimensional object data such as building data, land use data, and underground piping data. In addition, for each building, attribute data describing the number of floors of the building, usage, barycentric coordinates, etc., coordinate data of points forming the building, coordinate ID list forming the surface, normal vector data of each surface, building When a given ID is given, a reference table is provided to refer to them.

For each land, attribute data indicating the use of the land and coordinate data of points composing the land are given. Regarding the underground piping data, the thickness of the pipe, the attribute data indicating the type, and the coordinate values of the start point and the end point of each pipe are given.

Then, in step 2, the space is divided and managed with respect to the closed surface. Here, the ground is used as a clear shielding surface. Since the ground is an almost horizontal area now, the shielding surface is a plane of Z = 0. Therefore, Z <0. And Z ≧ 0. Manage the data by dividing it into spaces. Z <0. Included in the space are underground piping data and Z ≧ 0. Buildings and land use data included in the space are managed separately.

In step 3, since the city has a two-dimensional spread, two-dimensional mesh division is performed on the XY plane to manage the data of the building, land use, and underground piping.
The mesh division has a hierarchical structure.
Divide by b and repeat division of each mesh into c × c n times. At this time, the number of layers of the mesh and the degree of detail of the data can be arbitrarily set, but here, in order to simplify the explanation, each is set to three stages.

For example, when there is a city of 5 km × 10 km, the whole is divided into 5 × 10 meshes, each mesh is divided into 2 × 2, and each mesh is further divided into 2 × 2. As a result, the actual data is the finest 250m ×
It is managed by a 250m mesh.

As shown in FIG. 4, the ID of each mesh has the lower two digits as the mesh number of the lowermost layer, the next two digits as the mesh number of the second layer, and the upper four digits as the uppermost mesh. It is represented by an 8-digit number. When referring to the highest mesh, the last 4 digits of the ID are designated as 0. For example, in FIG.
When the inner mesh 02020000 is specified, all the lowermost layer meshes whose upper four digits of the ID are 0202 are targeted.

In step 4, the building data is hierarchized according to the detail level of the building as shown in FIG. Here, since the shape of most buildings is composed of polygonal columns, the method of polygonal column approximation will be improved. When there is a building with n prisms, the degree of detail 3 is the original data, which is the most detailed data.

FIG. 6 shows a flow of processing for obtaining the data of the detail levels 2 and 1. When the top surface of the polygonal prism is an n-sided polygon, the vertices are sequentially designated as P ₀ to P _n . In addition, the vertices of the bottom surface are defined as P _{n + 1} to P _2n . However, P _n and P ₀ , P _2n and P _{n + 1}
Are the same point. Then, the point P ₀ is registered as a polygonal point having a level of detail of 2. Further, at a certain point P _i (1 ≦ i ≦ n−
1), P _j (j = i + 1), the side faces P _i , P _j ,
If the area of P _{i + n + 1} and P _{j + n + 1} is greater than or equal to the threshold value α,
Register the point P _j . Otherwise, P _j is incremented and the same judgment is made. Then, this process is repeated, and when there are m points in total, a face list and normal vector data are newly constructed as an m prism having a cross section of this m polygon. If m ≦ 1, the building is invisible at the current level of detail.

In FIG. 5, the original object is a hexagonal prism, so that n = 16, the top surface is P ₀ to P ₁₆ , and the bottom surface is P.
_{From 17} to P ₃₃ . Register P ₀ in the polygon list of detail level 2. As a result of calculating the areas of the side surfaces P ₀ , P ₁ , P ₁₇ , and P ₁₈ , this is smaller than the threshold value α, so this is not registered and the judgment is repeated by incrementing j. P ₀ ,
Since the areas of P ₅ , P ₁₇ , and P ₂₂ were larger than α, P ₅
To the list. In this way, the data of detail level 2 was created.

Further, the area threshold value α at the detail level 2 is obtained as follows. When the viewpoint is set at the distance L2 from the surface in the normal vector direction of the surface with the reference point as the center of the surface and the surface is projected on the display screen, the surface forms at least 1 pixel on the screen. Let α be the area of. Similarly, the distance L
The viewpoint is set to 1 and the data of the detail level 1 is created. However, the distances L1 and L2 are arbitrarily set, and here, L2 = 250 m and L1 = 500 m. In this way, the data construction on the main memory is completed. The data structure of each mesh at this time is shown in FIG.

Then, in step 5 shown in FIG. 2, the view field range is determined from the view point, the reference point, and the view angle. By clicking the map and altimeter displayed on the display screen with the mouse, the viewpoint (vx, vy, vz) and the reference point (rx, r
y, rz) is specified. The viewing angle is given a default value. The visual field range forms, for example, a quadrangular pyramid, but in order to determine the inside and outside of the visual field range, (vx, vy) is centered,
A sector shape on the XY plane whose radius is L0, a straight line passing through the viewpoint and the reference point is the center line, and the center angle is θ is set as the visual field range (FIG. 8).

In step 6, the spatial relationship between the closed surface and the viewpoint is obtained, and the spatial area is selected. vz <0. If it is, the following processing is performed on the underground piping data. Here, as shown in FIG. 9, vz> 0. Therefore, the description will be continued assuming that the spatial area including the building data and the land use data is selected.

In step 7, a mesh included in the mesh hierarchy and the visual field range is selected. First, as shown in FIG. 10, a mesh hierarchy is selected according to the altitude (vz) of the viewpoint. For example, the selection criterion is set by vz as follows.

(1) When vz is 500 m or more, the highest mesh is used.

(2) When vz is 10 m to 500 m, the mesh of the second layer is used.

(3) When vz is 10 m or less, the mesh of the lowest layer having the smallest size is used. Then, in the designated mesh hierarchy, a mesh included in the visual field range is selected. First, the mesh including the viewpoint is specified, and then the line-of-sight direction is quantized. Next, set the line of sight to 8
Quantize in the direction (FIG. 11) and along this direction select the meshes included in the field of view. An example for the bottom mesh is shown in FIG. Especially when vz is 5 m or less, only meshes in the immediate vicinity of the visible meshes are selected. In the example of FIG. 12, only the four meshes in the vicinity are selected. This is because the buildings are densely packed, and in a place where the viewpoint is low, only the buildings very close to the viewpoint can be seen.

In step 8, the level of detail of the building inside the selected area is determined. Basically, the degree of detail of the building is changed depending on the distance as shown in FIG. 13, but here, the distance between the viewpoint and the building is replaced by the distance between the viewpoint and the center of the mesh including the building. Then, the distance between the viewpoint and the center of the selected mesh is calculated. As a result, if the distance from the viewpoint is within L2, the detail level is 3, L2 to L1.
Is set to level of detail 2, and L1 to L0 are set to level of detail 1. However,
L2 = 250 m, L1 = 500 m, L0 = 1 km.
When a certain viewpoint is determined as shown in FIG. 12, the detail level is determined for each mesh.

In step 9, the building in the selected mesh is drawn in accordance with each detail level.

In step 10, if each building is sufficiently distant and it is difficult to identify each building, it is created in advance,
A distant view from a distance from the center of the area is used as a background according to the direction of the line of sight. An example of this distant view is shown in FIG.

Steps 5 to 10 are repeated each time a new viewpoint and reference point are designated. In step 6, vz <0. If it is, only underground piping data is displayed. Underground piping data can be hierarchized according to the level of detail. Underground piping data has radius r and length L
Since it is a circular cylinder, it is represented by a polygonal prism at the time of display. Therefore, for example, the degree of detail 3 approximates to a 12-sided prism, the degree of detail 2 approximates to a hexagonal column, and the degree of detail 1 approximates to a triangular prism.

The description is not limited to the above embodiment,
The invention can be appropriately modified and implemented without changing the gist.

For example, when the building has internal data, the wall surface of the building may be used as the shielding surface. This internal data is managed separately by using the plane figure of the building that has the internal data as an enclosed area. Minimum value in the X and Y directions of a plane figure,
The maximum value is registered as a dangerous area, and whether or not the viewpoint is in this dangerous area is checked by comparing vx and vy. If it is in the hazardous area, inspect it for inclusion in the enclosed area. If it is included in the closed area, it is determined that the building is inside the building, and only the internal data is drawn. Further, when the scenery outside the window is designated, only the data included in the window frame is displayed. By performing this processing, the inside of the building can be drawn at high speed. When it is not included in these, the internal data is not targeted for drawing.

Further, for example, when the ground is an obstructing surface, and if there is a particular designation, the ground can be made semitransparent and the building and underground piping data can be superimposed and displayed. By this processing, it is possible to perform flexible display according to the user's request.

Several other methods are conceivable as a method of layering the buildings with different degrees of detail. As a method for approximating a polygonal column, two methods for approximating a polygonal cross section will be described below.

When the cross section of a polygonal column is approximated by a polygon, the bisection method can be used. As shown in FIG. 15, a line is drawn from one point P1 on the periphery of the original polygon to the farthest point P2 on the periphery. From this straight line, P3 and P4 having the largest distances to other points on the periphery are obtained, and if these distances are larger than d, this point is adopted. This is repeated for each of the two divided regions. In this two-division method, different approximation data can be obtained by setting various values of d. The larger the value of d, the rougher the approximation.

As another method of polygonal approximation, there is a method of utilizing the error of linear approximation. A straight line is approximated to a part of each point forming the polygon by the method of least squares, and if the error at this time is less than a certain value ε, the part is a straight line. By changing the value of ε, approximate data of different layers can be obtained. Also in this case, the larger ε, the rougher the approximation, and the smaller the degree of detail.

It is possible to save the data under the hierarchical mesh management and the approximated data having different degrees of detail in the designated hierarchy on the disk and reuse it. in this case,
The load at initial load is light.

When considering an indoor walkthrough or the like, the shield is used quite effectively. If it is partitioned by a partition, etc.
The view area is three-dimensionally determined based on the position of the viewpoint by dividing the view area.

When the inside of a plant has complicated three-dimensional data, the space is divided into three-dimensional grids for management. The visual field range is a quadrangular pyramid, and the data inside the grid included in this range is drawn. Hierarchizing each structure data according to the level of detail is the same as in the case of a city.

In this embodiment, only the shape of the three-dimensional object is hierarchized by the degree of detail, but the surface material can be hierarchized by the degree of detail. For example, texture mapping is performed at detail level 3, a simple pattern is used at detail level 2, and only representative colors are used at detail level 1.

Next, another embodiment of the present invention will be described. The hardware configuration is the same as in FIG.

16 to 18 are flowcharts showing the processing procedure executed by the processing processor 1 in this embodiment. In FIG. 16, step 31 is a process of reading the three-dimensional spatial data of the designated area from the city database. Here, it is assumed that the building plane shape figure divided for each 300 m square map mesh and its height value are read from the secondary storage (disk).

Step 32 is a hierarchical simplification process, the output of which is an n-level simplified model. The processing here is shown in detail in FIG. That is, first, at step 41, the number of simplification levels n is determined.

The simplification level number n is [M / D], where D is the total amount of data read from the database and M is the amount of memory available for the system to hold display data.
([A] is the maximum integer that does not exceed A). For example, when the value of [M / D] is 5, the number of simplification levels n = 5, and five kinds of simplification models from level 0 to level 4 are obtained. The method of obtaining the number of simplification levels n is one guide, and if it is determined that, for example, five kinds of simplification levels are not necessary in the above example, this should be changed empirically.

When the number of simplification levels is determined, the relationship between the simplification level and the distance value from the viewpoint is determined in step 42 of FIG. If the simplification level number n is obtained, the values of the distances corresponding to level 0, level 1, ..., Level n−1 are determined as follows.

First, the circumscribed rectangular parallelepiped is obtained for each building data read from the database, and the average H _av of the side lengths of the circumscribed rectangular parallelepiped is calculated. This may be represented by the average length of the bottom side. Also. It can also be specified interactively. The distance value d _n from the viewpoint corresponding to the maximum display distance (no more objects are displayed)
Is a value where the side of length H _av + α becomes k (usually 1) pixels on the display screen. For example, P · (H _av + α) / 2ksi
It can be roughly estimated by n (θ / 2). Here, P is the total number of horizontal display pixels, and θ is the horizontal viewing angle. Further, d _n may be directly designated (for example, the maximum distance on the horizontal plane occupied by a given data set). In addition, for each distance value from the viewpoint from level 1 to level n-1, the distance value d _n is
Determine based on the equally divided values. Instead of dividing into n equal parts, it is also possible to divide into a predetermined ratio.

Next, in step 43, the relationship between the simplification level and the degree of simplification is determined. The simplification is done by approximating the shape with a specified precision. Therefore, the degree of simplification can be controlled by the maximum value of the allowable error (simplification parameter) in the approximation. Where level 1
To the level n-1 simplified parameter values are determined using the distance values d ₁ to d _n-1 as described above. That is, the simplification parameter value of level i is the length of the side having k (usually 1) pixels on the display screen at the distance d _i from the viewpoint.

Using the above (H _av + α),
It is estimated by {(H _av + α) / n} · i. Also, these values may be specified by dialogue.

In step 44, a simplified model is created. This is done using the values of the simplification parameters above. FIG. 15 is an explanatory diagram of polygonal approximation by the two-division method. For example, a heptagon composed of P1 to P7 is simplified by replacing a point whose angle is close to 180 ° with a straight line. That is, the original data (level 0) is a heptagon as shown in FIG. 9A, the simplification level 1 is a pentagon as shown in FIG. 7B, and the simplification level 2 is shown in FIG. It becomes a square like this.

This will be described with reference to the object shown in FIG. 5. As shown in FIG. 5A, the polygonal prism has no fine protrusions at the simplification level 1 and its cross section is shown in FIG. The figure becomes (), and at simplification level 2 the figure (c)
It becomes a simple rectangular parallelepiped as shown in. The polygonal approximation is not limited to the bisection method.

In this way, the hierarchy is simplified in step 32 shown in FIG.

Then, step 33 is a process for managing the data area division including the simplified model, and the map mesh size of step 31 is finely divided. Here, the area is divided into a mesh of 100 m square, which is one-third.

Next, in step 34, the viewpoint and reference point information are read. This is reading of information on the viewpoint and reference point shown in FIG. 8, and is designated by mouse click. Further, the viewing angle θ is defined in advance, and here, in order to simplify the processing, quantization is performed by setting the directions to eight directions as shown in FIG.

Then, in step 35, the data included in the visual field range is displayed in a simplified manner. The processing here will be described in detail with reference to the flowchart shown in FIG.

First, in step 51, a divided area included in the visual field range is calculated, and in step 52, a simplified model is selected. FIG. 13 shows a method of calculating divided areas included in the visual field range and a method of selecting a simplified model. As shown in the figure, the region up to the distance value d ₁ from the viewpoint is the simplification level 0, the region up to the distance value d ₂ is the simplification level 1, and the region up to the distance value d ₃ is the simplification level 2. Can be decided

Further, the simplification region can be extracted by only calculating the representative point (here, the center of gravity) of each region and the viewpoint. Here, since the directions are quantized into eight directions as shown in FIG. 11, the area extraction can be further speeded up by storing eight patterns.

Further, when performing dynamic display control such that the display speed becomes constant, as shown in FIG. 12, adaptively,
It is sufficient to change the simplification level assignment of the distance segment without changing the distance threshold. That is, when the display speed is specified to a certain value, when the viewpoint is moved, the display data may be slower than the specified value due to fluctuations (when the display data amount is increased). In this case, in the next movement, level 0 is automatically controlled to level 1, level 1 to level 2, and level 2 is omitted automatically to enhance the degree of simplification and reduce the amount of display data. suppress. The opposite is true when it gets faster.

Thus, the visual field range is displayed. Then, in step 36 of FIG. 16, steps 34 and 35 are repeated until a display end command is given. Note that steps 33 'and 3 stored in FIG.
5'is a process performed to increase the naturalness in interactive continuous display (walkthrough, etc.). Here, "naturalness" means the smoothness of transition of the display screen.
At this time, control is performed so that the display speed is constant.

Although the example of the outdoor landscape in the city database has been described above, it can be applied to the indoor landscape. In the room, the shapes of objects such as desks and chairs are more complicated than in buildings. Hereinafter, a simplification method when a simplification parameter is specified for an object having a general shape will be described.

FIG. 19 is a flow chart showing the simplification processing by the slice method, and FIG. 20 is an explanatory view showing this processing. Now, as shown in FIG. 20, when there is an object 65 to be simplified, each intersecting figure with the object surface for which horizontal slicing is performed at a specified interval is obtained (FIG. 19, step 61). Then, in step 62, polygonal approximation by the two-division method is performed on each intersecting figure with the specified accuracy. That is, in FIG. 20, the slice plane surrounded by the curved line is approximated by a polygon to be a slice plane surrounded by a plurality of straight lines.

Next, in step 63, surface patches are performed by connecting the vertices of vertically adjacent polygons whose horizontal plane coordinates are close to each other with straight lines so as not to intersect each other. This makes the object 6 covered with curves
5 can be approximated by a plurality of planes, and the accuracy of the approximation can be arbitrarily changed by changing the size of the slice interval and the number of points in the polygonal approximation. In addition,
The slice direction is not limited to the horizontal direction, and the polygon approximation is not limited to the bisection method.

Regarding this, for example, the literature: Fuchs H., et.
al "Optinal surface reconstruction from planar co
ntours "commun. Assoc. Comput Mach Vol.20, NO.10 pp
The method shown in 693-702 (1977) can be used.

Further, FIG. 21 is a flow chart of simplification processing by the voxel method, and FIGS. 22 and 23 are explanatory diagrams thereof. First, in step 71, a three-dimensional lattice is generated at a specified interval in the three-dimensional space. Then, the surface of the object is quantized by a three-dimensional lattice to convert the object into a three-dimensional binary image (step 72). Then, in step 73, a surface patch is applied to the three-dimensional binary image. As a result, the object is simplified as shown in FIGS. The method described in the literature (Computer Graphics, Vol. 21, No. 4, July, 1987) can be used for the processing here. Further, as shown by B1 in FIG. 22, when the object screen is included in the unit cube, the voxel value is 1, and the other values are 0.

FIG. 24 is a flow chart showing the simplification process by the clustering method, and FIGS. 25 and 26 are explanatory diagrams thereof. First, at step 81, it is determined whether or not the object of the node is equal to or larger than the designated size (threshold value) by performing a top-down search for the hierarchically expressed object.

As a result, when the object of the child node is smaller than the threshold value and more than the threshold value, the circumscribed rectangular parallelepiped is made the shape of the own node object (step 82). It may be that a certain ratio or more is smaller than the threshold value.

Then, in step 83, the entire object consisting of only partial objects equal to or larger than the threshold is used as a simplified model. The representative shape of the cluster is not limited to the circumscribed rectangular parallelepiped, but may be approximated by a polygonal column, a cylinder, a sphere, a convex polyhedron, or the like.

In this way, a simplified model of the indoor landscape can be created by the above three methods. In this way, in the present embodiment, a plurality of simplified models are created by changing the approximation accuracy for each object existing in the three-dimensional space data, and the simplified model of the approximation accuracy according to the distance from the viewpoint. Is displayed. Also, when the viewpoint moves, a simplified model of each object is determined according to the moving speed. Therefore, it is possible to prevent the generated three-dimensional image from deteriorating, effectively reduce the number of strokes to be drawn, and perform high-speed three-dimensional image display.

Further, instead of selecting the simplified model according to the distance from the viewpoint, the model may be selected with a uniform visual field range by the user's designation (mode selection). Further, the simplified model may be fixed for each object by the user's designation. Further, a simplified model may be assigned not for the viewpoint distance but for each section of the display screen, such as near and around the center of the display screen.

[0093]

As described above, according to the present invention, when the visual field range is determined, necessary spatial data can be efficiently extracted by the hierarchical divided area management.
Moreover, by changing the detail level of the data according to the distance from the viewpoint, it is possible to reduce the drawing load while maintaining the appearance. As a result, it is possible to rapidly display an arbitrarily designated portion of a large amount of data over a wide area.

Further, when the view field range is determined, necessary spatial data can be efficiently extracted by a combination of data layer simplification and area division management, and the data simplification level can be changed according to the distance from the viewpoint. By changing, the deterioration of the generated image can be minimized and the drawing load can be reduced. As a result, it is possible to rapidly display an arbitrarily designated portion of a large amount of data over a wide area.

[Brief description of drawings]

FIG. 1 is a block diagram showing the configuration of an embodiment of a system to which the method of the present invention is applied.

FIG. 2 is a first partial diagram of a flowchart showing the operation of the present embodiment.

FIG. 3 is a second partial diagram of the flowchart showing the operation of the present embodiment.

FIG. 4 is an explanatory diagram showing construction of a hierarchical mesh.

FIG. 5 is an explanatory diagram showing layering of a three-dimensional object according to the degree of detail.

FIG. 6 is a flowchart showing a procedure of a polygonal column approximation method.

FIG. 7 is an explanatory diagram showing a structure of three-dimensional object data.

FIG. 8 is an explanatory diagram showing a visual field range used for determination.

FIG. 9 is a region selection diagram when an occluding surface exists.

FIG. 10 is a mesh hierarchy selection diagram according to the position of a viewpoint.

FIG. 11 is a line-of-sight quantization diagram.

FIG. 12 is a mesh selection diagram within the visual field range.

FIG. 13 is a hierarchy selection diagram of data according to a distance from a viewpoint.

FIG. 14 is an explanatory diagram showing an example of a fixed pattern.

FIG. 15 is a hierarchical polygon approximation diagram using the two-division method.

FIG. 16 is a flowchart showing an operation according to another embodiment of the present invention.

FIG. 17 is a flowchart showing a procedure for creating a simplified model.

FIG. 18 is a flowchart showing a procedure for three-dimensional display.

FIG. 19 is a flowchart showing the procedure of simplification processing by the horizontal slice method.

FIG. 20 is an explanatory diagram of a horizontal slice method.

FIG. 21 is a flowchart showing a procedure of simplification processing by the voxel method.

FIG. 22 is an explanatory diagram of a voxel method.

FIG. 23 is an explanatory diagram of a voxel method.

FIG. 24 is a flowchart showing a procedure of simplification processing by the clustering method.

FIG. 25 is an explanatory diagram of a clustering method.

FIG. 26 is an explanatory diagram of a clustering method.

[Explanation of symbols]

1 Processor 2 Main memory 3 Disk controller 4 Disk 5 Memory controller
6 image memory 7 CRT controller 8 CRT
9 mouse interface 10 mouse

Claims (4)

[Claims] 1. A high-speed display method for three-dimensional space data, which displays on a screen a three-dimensional scene in a field of view arbitrarily designated in the three-dimensional space data, in which a shadow existing in the three-dimensional space data is included. First management means for extracting a closed surface and managing a three-dimensional object existing in the three-dimensional spatial data for each area divided by the closed surface, and the three-dimensional spatial data is hierarchically divided. However, it has a second management means for managing the three-dimensional object for each of the divided areas, and a third management means for managing the three-dimensional object data in a hierarchy for each degree of detail, and has an arbitrary visual field range. When is specified, means for limiting the space area to be displayed based on the first management means based on the positional relationship between the viewpoint and the shielding surface, and a hierarchy for the space area is selected from the viewpoint position. An area included in the visual field range based on the second management means A means for extracting, a means for determining the detail level of the three-dimensional object inside the extracted area according to the distance from the viewpoint, and displaying based on the third management means. High-speed display method for 3D spatial data. 2. The high-speed three-dimensional spatial data according to claim 1, wherein the third managing means approximates a three-dimensional shape with a specified accuracy to hierarchically form the original data into rougher approximation data. Display method. 3. A device for displaying a fixed pattern in advance, wherein the fixed pattern is not displayed when the distance from the viewpoint of the object to be displayed is equal to or more than a threshold value, and means for using the fixed pattern as display data is provided. A high-speed display method for three-dimensional spatial data according to item 1. 4. A high-speed display method of three-dimensional space data for displaying on a screen a three-dimensional scene of a field of view arbitrarily designated in the three-dimensional space data, each of which is present in the three-dimensional space data. Means for simplifying the original model of the object with one or more approximation precisions, means for determining the number of simplification levels based on the number of models that can be possessed for the simplified object, and each simplification level A means for determining the degree of simplification,
A means for obtaining one or a plurality of simplified models for each of the objects based on the determination result; a means for dividing and managing the original model and the simplified model for each predetermined divided area;
Means for selecting a divided area to be displayed when a viewpoint is given in a three-dimensional space and determining which level of the simplified model to use in the selected divided area; and three-dimensional based on the determination result A high-speed display method of three-dimensional spatial data, characterized by comprising: means for displaying spatial data.