JPH1173526A - Converter for virtual spatial data using tree structure - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a converter for virtual spatial data in which a hierarchy structure and independence of a shape are not ruined by a combination operation and information except for video information is not destructed. SOLUTION: A scene tree structure decomposition part 101 decomposes a given tree structure into a group of tree structure in which each tree structure holds part of information on original tree structure so that incorporated information is not destructed, with regard to decomposed group of tree structures, a tree structure storage table generation part 102 stores information on one of the tree structures as a pair in a tree structure storage table 103, a reference tree structure generation part 104 generates a reference tree structure specialized for a spatial detection and a tree structure connection part 105 connects the reference tree structure and the group of tree structures stored in the tree structure storage table 103.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an apparatus for converting virtual space data using a tree structure, and more particularly to improving the drawing speed of a browser.

[0002]

2. Description of the Related Art Each intermediate node has at least one of modeling transformation matrix and bounding box information, and each leaf node has at least one of shape (polygon), texture, event handling, lighting, and color information. VRML (Virtual Reality Mo) as an example of virtual space data represented by a rooted ordered tree structure having
deling Language, literature: for example, Kenjiro Miura, published by Asakura Shoten, VRML 2.0: 3D cyberspace construction language).

[0003] VRML is a language developed for realizing an environment for publishing and sharing a virtual space on the Internet. The above environment is realized by exchanging a VRML file via the Internet, and drawing software (browser) dedicated to the data to draw a video at an arbitrary viewpoint while scanning a given tree structure by a depth-first search. You.

There are countless expression methods for creating VRML data corresponding to a certain virtual space. In general, the smaller the number of nodes scanned by a browser and the number of switching of textures (drawing attributes) during drawing, the smaller the number. The more the polygon is represented by a mesh (a geometric figure composed of adjacent triangles), the higher the drawing speed of the browser. Therefore, VRML corresponding to a certain virtual space
If there is data, if the VRML data can be converted to satisfy the above conditions without destroying various information related to the virtual space embedded in the data, the same virtual space is drawn at higher speed. VRML data can be created.

As a conventional method for automatically performing the above conversion, i
There is software called vfix (manufactured by Silicon Graphics). The ivfix converts virtual space data represented by a rooted ordered tree structure described in the Open Inventor file format based on VRML so as to improve the drawing speed of the browser.

FIG. 20 is a block diagram showing an apparatus for converting virtual space data according to the prior art.
Is stored in the shape-related information table 7 as one set of shape information and related information group (camera, light source model, texture, material, coordinate transformation, etc.) as one set. A shape-related information table creating unit 2 that sorts sets in the shape-related information table using drawing attributes as keys, and 3 a group of shape-related information tables with the same drawing attribute information Is a tree structure generating unit that generates one tree structure from the shape relevant information table 7, 5 is a mesh shape generating unit that meshes shape information, 6 is a tree This is a redundant information deletion unit that removes redundant nodes of the structure.

Next, the operation will be described with reference to FIGS. FIG. 21 is a flowchart showing a processing procedure in the related art. First, in step ST1, the shape-related information table creating unit 1 analyzes the tree structure of the input data, and sets the shape-related information table 7 as a set of the shape information defined in the tree structure and the related information group. Create

Next, in step ST2, the shape-related information table sorting section 2 rearranges each set of the shape-related information table 7 using the drawing attribute as a key. Next, in step ST3, the shape-related information table merging unit 3
An attribute called a difference level is added to the sorted shape related information table 7, and the difference level between the n-th set and the (n-1) -th set is set to 6
What is determined in the steps (0, 1, 2, 3, 4, 5) is the n-th
Attribute value of the difference level of the set. However, the attribute value of the first set of difference levels is 1.

[0009] Here, in the step ST3, the shape-related information table merging unit 3, the shape-related information in the table 7 of the n sets c _n and the n-1 set c _n-1 as compared to rendering attributes c _n Details of the processing procedure for obtaining the difference level l _n will be described with reference to the flowchart shown in FIG. First,
In step ST31, it is determined whether or not the cameras are the same in the drawing attributes of c _n and c _n−1 , and in the case of NO, l _n = 1 in step ST32 and the process ends.

If YES is determined in step ST31, it is determined in step ST33 whether the light source, the atmospheric effect, and the light source model are the same in the drawing attributes of c _n and c _n-1. In this case, in step ST34, l _n = 2 and the process ends.

If YES is determined in step ST33, it is determined in step ST35 whether or not the texture is the same in the drawing attributes of c _n and c _n-1. If NO, step ST36 is performed. In l
_The process ends with _n = 3.

[0012] If it is determined as YES in the step ST35, in step ST37, c _n and c _n-1
It is determined whether or not the definition order of the drawing style, the material, and the vertex is the same in the drawing attribute. If the determination is NO, the process ends with l _n = 4 in step ST38.

[0013] If it is determined as YES in the step ST37, in step ST39, c _n and c _n-1
It is determined whether or not both shapes are defined in the same file in the drawing attribute of, and in the case of NO, in step ST40, the processing is terminated by setting l _n = 5, and Y
In the case of ES, in step ST41, l _n = 0 and the process ends.

Next, in step ST4 of FIG. 21, in the set of the shape-related information table 7 obtained in step ST3, the set having the difference level of 0 (the n-th set) is the upper set (the n-th set).
If the drawing attribute information is the same as the (-1) set, the shape-related information table merging unit sequentially executes an operation of combining the n-th set and the (n-1) -th set.

Here, the details of the processing procedure of the set combining operation in step ST4 will be described with reference to FIG. Here, the n-th set c _n of the shape-related information table 7
The attribute value of the difference level of 0 is n-th set c _n and n-1-th set c
It is assumed that _n-1 drawing attribute information RA is the same. At this time,
c _n-1 of the shape information s _n-1 in the modification information t _n-1 s which is reacted with the _'n-1, c _n of shape information s _n in which is reacted with the modification information t _n s' _{If n} , the shape information is s' _n-1 +
A set having s' _n , deformation information of NULL, drawing attribute information of RA, and a difference level of l _n-1 (attribute value of a difference level of c _n-1 ) is generated, and is generated as c _{n- 1} and c _n And the result of the combination.

Next, in step ST5 of FIG. 21, the tree structure generation unit 4 executes the shape-related information table 7 after the joining operation.
Then, one tree structure T is generated according to the flowchart shown in FIG. First, in step ST51 of FIG. 24, a linear rooted ordered tree structure T including only intermediate nodes having a depth of 5 as shown in FIG. 25 is generated. In this root ordered tree structure T, the information about whether the information related to the camera in what file on are stored in the R _1,
Hereinafter, a light source, atmospheric effects, lighting model in R _2, in R ₃ the texture, definition order of drawing style, material, vertices in R _4, and so the shape information in R _5, each information which file on Is stored.

Next, in step ST52, a variable N indicating a set number is initialized to N = 1. And step S
At T53, it is determined whether N is larger than the number of sets in the shape-related information table 7, and if it is larger, the process is terminated. If N is equal to or less than the number of sets in the shape-related information table 7, in step ST54, a linear rooted ordered tree structure T _N having a depth d is generated. Here, the value of the depth d is given by the following equation using the difference level 1 _N. d = 0 if l _N = 0 d = 6-1 l _N otherwise

Next, in step ST55, the tree structure T
It will insert the first N sets of information shape related information table 7 to _N. Each node s depth i in the T _N T _N
(I, T _N) information to be inserted into is determined by the depth i in depth and T _N of T _N. Next, in step ST56, as shown in FIG. 26, the root of T _N is the depth d of T
(T _N ), that is, in FIG. 26, T _{N is set} to T so that it is the rightmost child of the rightmost node (the node of depth d (T _N ) with the highest priority in depth priority). Insert Here, the value of the depth d (T _N ) is given by the following equation using the difference level 1 _N. d (T _N ) = 5 if l _N = 0 d (T _N ) = l _N -1 otherwise Then, in step ST57, N = N + 1 is incremented, and the process returns to step ST53.

Next, in step ST6 of FIG. 21, the mesh shape generation unit 5 meshes the shape information in the rooted ordered tree structure T obtained in step ST5. Finally, in step ST7, the redundant information deleting unit 6 detects and removes redundant nodes by scanning the rooted ordered tree structure T by a depth-first search in the same manner as a browser.

As described above, the conventional virtual space data conversion apparatus converts the virtual space data expressed by the rooted ordered tree structure, thereby reducing the number of texture (drawing attribute) switchings during drawing. However, in most cases, the number of nodes in the tree structure is reduced as compared to before conversion, and the meshing of the shape improves the polygon drawing speed.

[0021]

However, the conventional virtual space data conversion apparatus uses a hierarchical structure of a shape by a joining operation.
There is a problem that independence is lost and information other than video information is destroyed. Therefore, if this method is applied to virtual space data in which some action is defined in response to user interaction (such as clicking a certain object with a mouse), it will not operate properly after conversion.

Also, since polygons having the same drawing attribute are combined as one piece of shape information regardless of the position and size of the shape information, polygons having the same drawing attribute information as polygons outside the viewing area are also combined. If it exists, the drawing process is performed. Therefore, in the case of a tree structure expressing a wide virtual space in which most of the polygons are outside the visual field region, there is a problem that useless drawing processing frequently occurs and the drawing speed is reduced.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-mentioned problem, and the drawing speed of a browser can be improved even for data expressing a wide virtual space without causing loss of information other than video information. It is an object to obtain a virtual space data conversion device using a tree structure as described below.

[0024]

A virtual space data conversion apparatus using a tree structure according to the present invention inputs virtual space data using a tree structure, and incorporates a given tree structure into the tree structure itself. Scene tree structure decomposing means for decomposing each tree structure into a tree structure group holding a part of the information of the original tree structure without destroying the extracted information, A tree structure storage table generating means for generating a tree structure storage table for storing information regarding one tree structure as one set, and adding bounding box information as area information of the shape of each set; A reference tree structure generating means for generating a reference tree structure specialized for spatial search, and a reference tree structure generated by the reference tree structure generating means and stored in the tree structure storage table Those having a tree structure coupling means for coupling the tree structure group is.

A virtual space data conversion device using a tree structure according to the present invention inputs virtual space data using a tree structure and destroys a given tree structure with information incorporated in the tree structure itself. A scene tree structure decomposing means for decomposing each tree structure into a tree structure group holding a part of the information of the original tree structure, and information on one tree structure for the decomposed tree structure group And a tree structure storage table generating means for adding bounding box information as area information of the shape of each group, and each group holding the tree structure storage table. Tree structure storage table dividing means for dividing into a plurality of tables such that a set holding at least one type of the same texture is present in the same table in accordance with the given texture information , For each of the divided tree structure storage table, on the basis of the bounding box information,
A reference tree structure generating means for generating a reference tree structure specialized for spatial search; a reference tree structure generated by the reference tree structure generating means; and a tree structure group stored in the divided tree structure storage table. And a tree structure coupling means for coupling.

An apparatus for converting virtual space data using a tree structure according to the present invention comprises mesh shape generation means for meshing shape information in a tree structure generated by the tree structure connection means.

A virtual space data conversion apparatus using a tree structure according to the present invention stores a method of generating a reference tree structure specialized for a plurality of spatial searches, and selects one of a plurality of stored methods. A reference tree structure generation method selection unit that selects a predetermined method according to a user's instruction, wherein the reference tree structure generation unit uses the reference tree structure generation unit based on the bounding box information of the shape managed by each set of the tree structure storage table. A method of generating a reference tree structure specialized for spatial search using the method of generating a reference tree structure specialized for the predetermined space search selected by the tree structure generation method selecting means.

A virtual space data conversion apparatus using a tree structure according to the present invention stores a method of generating a reference tree structure specialized for a plurality of spatial searches, and selects one of a plurality of stored methods. A reference tree structure generation method selection unit that selects a predetermined method according to a user's instruction, wherein the reference tree structure generation unit selects, for each divided tree structure storage table, a shape managed by each set of the tree structure storage tables. Based on the bounding box information of the above, using a method of generating a reference tree structure specialized for the predetermined space search selected by the reference tree structure generation method selecting means, a reference tree structure specialized for the spatial search To generate.

A virtual space data conversion apparatus using a tree structure according to the present invention has a tree structure specialized for spatial search.
It uses a tree structure that divides a two-dimensional space into a plurality of small spaces and manages the data in the small spaces.

The virtual space data conversion apparatus using a tree structure according to the present invention has a tree structure specialized for spatial search.
It uses a tree structure that divides a three-dimensional space into a plurality of small spaces and manages the data in the small spaces.

A virtual space data conversion apparatus using a tree structure according to the present invention has a tree structure specialized for spatial search.
It uses a tree structure that divides a two-dimensional space into regions according to the distribution state of data.

The virtual space data conversion apparatus using a tree structure according to the present invention has a tree structure specialized for spatial search.
It uses a tree structure that divides a three-dimensional space into regions according to the distribution state of data.

[0033]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention will be described below. Embodiment 1 FIG. FIG. 1 is a block diagram showing an apparatus for converting virtual space data using a tree structure according to Embodiment 1 of the present invention. In FIG. A scene tree structure decomposition unit (scene tree structure decomposition unit) 102, which decomposes each tree structure into a group of tree structures holding a part of information of the original tree structure, so that each tree structure 102 A tree structure storage table generation unit (tree structure storage table generation means) that generates the tree structure storage table 103 by storing information on one tree structure as one set for the decomposed tree structure group.

Reference numeral 104 denotes a tree structure storage table 103
The reference tree structure generation unit (which generates a reference tree structure specialized for spatial search based on the bounding box (minimum rectangular parallelepiped including the shape held by each set) of the shape managed by each set Reference tree structure generating means) 105 generates one tree structure expressing a virtual space equivalent to a given tree structure by combining the reference tree structure and a tree structure group stored in the tree structure storage table. It is a tree structure connection part (tree structure connection means).

Next, the operation will be described. FIG. 2 is a flowchart showing a processing procedure of the virtual space data conversion device using the tree structure in the first embodiment. First, in step ST101, the scene tree structure decomposition unit 101
Given a tree structure representing a certain virtual space, each tree structure has a tree structure that holds a part of the information of the original tree structure so as not to destroy the information embedded in the tree structure itself. Decompose.

Here, the details of the processing procedure of step ST101 by the scene tree structure decomposition section 101 will be described with reference to the flowchart of FIG. First, step S
At T1101, a variable TP indicating a tree structure to be processed is set to the tree structure T to be converted, and a value of a variable Q indicating the depth of the decomposition process is initialized to zero.

Next, in step ST1102, it is determined whether or not the variable TP can be further decomposed. The reason for determining NO in this step ST1102 is as follows. No shape information exists in TP. An operation mechanism for an input from a user common to all shapes in the TP is defined (for example, an animation function using a Touch Sensor in VRML). C. The case where the depth of the TP is 1 or less is satisfied.

If it is determined as YES in step ST1102, Q = Q in step ST1103.
Q + 1. Then, in step ST1104,
Non-leaf children of the root of TP are assigned to intermediate nodes v _i (i =
1, 2,..., N: n = the number of non-leaf root children of TP, and as shown in FIG.
Tree structure T consisting of only the roots of TP and their offspring
P (Q, 0) [only when leaves are present in the root], (b) T
Tree structure T, which consists of P of the roots and the intermediate node v _i and its descendants
P (Q, i) [i = 1, 2,..., N].

Next, in step ST1105, each T
For P (Q, i) [1 ≦ i ≦ n], as shown in FIG. 5, a node (R _i (i = 0, 1,
.., R)), the modeling transformation matrix information held by R _i is represented by M _i , and the modeling transformation matrix information obtained by multiplying each M _i is represented by M (M = M _r × M _r−1 × ···).・ × M ₀ ), R
_When the bounding box of the shape managed by the descendant node of ₀ is B, by replacing it with a node R having M as the modeling transformation matrix information and B as the bounding box information, R _i (i = 0, 1,
.., r) are combined into one node R so that there is no information loss.

Next, in step ST1106, the number of tree structures NN [Q] generated by the decomposition processing at the depth Q
Is set to NN [Q] = n + 1, and the index NI [Q] of the decomposition processing at the depth Q is set to NI [Q] = 0.
Then, in step ST1107, NI [Q]> N
It is determined whether or not N [Q]. This step ST1
If NO is determined in step 107, the process proceeds to step ST11.
08, TP = TP (Q, NI [Q]), and step S
It returns to T1102. If it is determined as YES, Q = Q-1 is set in step ST1109, and step ST11 is performed.
At 10, it is determined whether or not Q ≦ 0.

If the determination in step ST1110 is NO, NI [Q] = N in step ST1111.
I [Q] +1, the process returns to step ST1107, and YE
If it is determined to be S, the process ends. If NO is determined in step ST1102, the process proceeds to step S1102.
TP is output in T1112, and N is output in step ST1113.
Step ST1107: I [Q] = NI [Q] +1
Jump to

Next, in step ST102 of FIG.
The tree structure storage table generation unit 102 determines in step ST10
1, the tree structure group TP _(i) (i = 0, 1,...)
·, N: n + 1 = to step ST101 number of the generated tree structure), stores information on a tree structure TP _(i) in one set c _i of the tree structure storage table 103. Next, in step ST103, the tree structure storage table generation unit 102 adds an attribute called area information to the tree structure storage table 103, and sets a bounding box (a minimum rectangular parallelepiped that includes the shape held by each set) as the data. This is the attribute value of the set of area information. However, if there is no shape information, the area information is NULL.

Next, in step ST104, as shown in FIG. 6, in the tree structure storage table 103 obtained in step ST103, if the area information is not NULL, the area information is c _j , and the area information of c _j is r _j (bounding). box), XZ plane (X-axis of r _j: width direction, Z-axis: a projected figure of the depth direction) is taken as p _j, the reference tree structure generating unit 104, p _j a (1 ≦ j ≦ n) A tree structure _Tb is generated by sequentially inputting into a packet type tree structure that manages two-dimensional figures efficiently (one that manages information on a plurality of graphic data in one leaf), and The reference tree structure is used.

A tree structure for efficiently managing a two-dimensional figure (one in which the range search is 0 (logN): N = the number of data) is described in, for example, "A multi-dimensional data balanced tree by Yasuaki Nakamura et al. Management-Proposal of MD Tree-"(Transactions of the Institute of Electronics, Information and Communication Engineers, Vol. J71-D, No. 9, 1988)
).

Finally, in step ST 105, the tree structure combining unit 105 combines the reference tree structure _Tb and the tree structure group stored in the tree structure storage table 103 to create a virtual space equivalent to the given tree structure. _Is generated and output, and the process ends.

In this step ST105, T _opt
The details of the processing procedure for generating the data will be described with reference to FIG. First, the leaves of the reference tree structure _{T b l k (1 ≦ k} ≦ L, L =
The two-dimensional figure in which the number of leaves of T _b) holds p (k
_{m) (m = 1,2, ···} , M: M = Leaf l _k when is the number) of the two-dimensional figure being managed, l _k the step S
The tree structure generated in _{T101 Tp (k m) (m} = 1,2,
..., M). Next, a node that is not a leaf of T _b is replaced with a node having the bounding box information of the shape information held by all of its descendant nodes (for example,
Group node in VRML). Finally, add a having no shape information in a tree structure generated in step ST101 to the root of T _b.

As shown in FIG. 8, the browser scans the rooted ordered tree structure by the depth-first search, and when the node arrives, the node holds whether or not a descendant node of the node exists in the view area. Judgment is made based on the bounding box information that exists, and if it does not exist, the search for descendant nodes is not performed. For example, in FIG. 9, the search for the descendant node of the node A is not performed because it is outside the visual field area, but the search for the descendant node of the node B is performed because it is within the visual field area.

As described above, according to the first embodiment, a given tree structure is decomposed into a plurality of tree structures so as to prevent loss of information, and the decomposed tree structure group has a scan node number (O (LogN): N is the number of decomposed tree structures shown in FIG. 4), so that the number of nodes operated at the time of drawing without losing information other than video information is significantly reduced. As a result, the effect that the drawing speed of the browser is improved can be obtained.

Based on this embodiment, about one of the actual cities
After converting the kml square VRML file (version 2.0), the browser (Silicon Graphics:
Cosmop 1 layer) drawing speed was improved 3 to 4 times.

Embodiment 2 FIG. 10 is a block diagram showing an apparatus for converting virtual space data using a tree structure according to a second embodiment of the present invention.
The same reference numerals are given and the description is omitted. In FIG. 10, reference numeral 106 denotes a plurality of tree structure storage tables 103 according to the texture information held by each set so that a set holding at least one type of the same texture exists in the same table. It is a tree structure storage table division unit (tree structure storage table division means) for dividing into tables.

Next, the operation will be described. FIG. 11 is a flowchart showing a processing procedure of the virtual space data conversion device using the tree structure according to the second embodiment. First, the processes in steps ST101 and ST102 are performed in steps ST101 and ST102 in FIG.
Is the same as the processing of Then, in step ST201, the tree structure storage table partitioning unit 106
The tree structure storage table 103 generated in 102 is divided into a plurality of tables according to the texture information used by each set.

Here, in this step ST201,
Details of the processing procedure in which the tree structure storage table dividing unit 106 divides the tree structure storage table 103 will be described with reference to the flowchart in FIG. First, step ST21
01, tex ₁ , tex ₂ ,..., Tex _q obtained by sorting the textures used in the tree structure storage table 103 in descending order of the texture size.
And Next, in step ST2102, the texture number I is initialized to I = 1, and step ST2103 is performed.
, An attribute called a selection flag is added to each set of the tree structure storage table 103, and the selection flags of all the sets are set to FAL.
Set to SE.

[0053] Then, in step ST2104, we use texture tex _I a set of the tree structure storage table 103, creates a table TBL _I consisting of those selected flag is FALSE. And step ST21
In 05, the selection flag of the set selected in step ST2104 is set to TRUE. Next, step ST21
At 06, it is determined whether or not I = q. If YES, the selection flag is set to FA in step ST2107.
Set is the LSE (that is, a set that does not use the texture) to finish creating and processing the table TBL ₀ consisting. If NO is determined in step ST2106, I = I + 1 is incremented in step ST2108, and the process returns to step ST2104.

[0054] Next, in step ST202 of FIG. 11, the reference tree structure generating unit 104, each TBL tree representing the virtual space corresponding to the TBL _j according to the procedure of the first embodiment for each _j structure T _opt (j) Generate. Then, in step ST203, as shown in FIG. 13, the tree structure combining unit 105 determines that T _opt (0), T _opt (1) _,.
(Q) ends bound a single tree structure T _{o pt} by generate and output processing.

As described above, according to the second embodiment, since the tables having the same texture are sorted, the number of times of switching of the texture (drawing attribute) at the time of drawing is reduced as compared with the first embodiment. And the drawing speed of the browser can be improved.

Embodiment 3 FIG. 14 is a block diagram showing an apparatus for converting virtual space data using a tree structure according to a third embodiment of the present invention. Parts corresponding to those in FIG. 10 are denoted by the same reference numerals as in FIG. I do. In FIG. 14, reference numeral 107 denotes a mesh shape generation unit (mesh shape generation means) for converting the shape information in the tree structure generated by the tree structure connection unit 105 into a mesh.

Next, the operation will be described. FIG. 15 is a flowchart showing a processing procedure of the virtual space data conversion device using the tree structure according to the third embodiment. In this embodiment, in the second embodiment, each shape information in the tree structure T _opt generated in step ST 203,
In step ST301, the mesh shape generation unit 10
7 is a mesh.

As described above, according to the third embodiment, a tree structure expressing a virtual space equivalent to a given tree structure so as to reduce the drawing cost of the graphics engine by meshing the shape. Can be generated,
The effect that the drawing speed of the browser can be improved can be obtained.

In the third embodiment, the mesh shape generator 107 is added to the second embodiment. However, the same effect can be obtained by adding the mesh shape generator 107 to the first embodiment.

Embodiment 4 FIG. 16 is a block diagram showing an apparatus for converting virtual space data using a tree structure according to a fourth embodiment of the present invention.
The same reference numerals are given and the description is omitted. In FIG. 16, reference numeral 108 stores a plurality of methods for generating a tree structure specialized for spatial search, and a tree structure for generating a tree structure specialized for spatial search in the reference tree structure generation unit 104. A reference tree structure generation method selection unit (reference tree structure generation method selection means) selected by a user's instruction.

Next, the operation will be described. FIG. 17 is a flowchart showing a processing procedure of the virtual space data conversion device using the tree structure according to the fourth embodiment. Steps ST101 to ST103 in this embodiment
The processing up to is the same as the processing from step ST101 to ST103 in FIG. 2 of the first embodiment.
In step ST401, the reference tree structure generation method selection unit 108 selects a tree structure according to a user's instruction from a tree structure specialized for spatial search prepared in advance. Then, in step ST104, the reference tree structure generation unit 104 generates a reference tree structure using the selected tree structure. The processing in step ST105 is the same as in the first embodiment.

As a tree structure specialized for space search, in addition to the tree structure for efficiently managing two-dimensional figures used in the first embodiment, a tree structure for efficiently managing three-dimensional space (for example, octree , Literature: CL Jackins and
S. L. Tanimono, "Oct-Trees
and Their Use in Represen
ting Three-Dimensional Ob
jets ", Computer Graphics
and Image Processing, Nov.
1980, pp. 249-270). When the virtual space data to be converted is in the plane direction (X
If the space has a very small spread in the height direction (Z axis) compared to the spread in the Y plane, it is more efficient to manage the space two-dimensionally.

On the other hand, virtual space data that has the same extent in the height direction as the plane direction, such as a large-scale molecular model or three-dimensional visualization data of a scientific simulation result, is managed three-dimensionally. It is more efficient to select a tree structure to be used when the user generates the reference tree structure according to the spatial characteristics of the virtual space data to be converted. A tree structure with an improved drawing speed can be generated.

In the fourth embodiment, the reference tree structure generation method selection unit 108 is added to the first embodiment, but the same applies to the case where the reference tree structure generation method selection unit 108 is added to the second embodiment. The effect of is obtained.

Embodiment 5 In a fifth embodiment of the present invention, a two-dimensional space is divided into a plurality of small spaces as a tree structure specialized for space search in the first to fourth embodiments, and data in the small space is divided into a plurality of small spaces. By using a tree structure to be managed, virtual space is managed as shown in FIG.

In this embodiment, the tree structure is easy to mount, and if the three-dimensional shape is evenly distributed in the virtual space and the spread of the virtual space in the height direction is very small, the embodiment will be described. 1 is a tree structure that efficiently manages the two-dimensional figure used in (1) range search, that is, if the number of scanning nodes is 0 (l
ogN)) can be obtained.

Embodiment 6 FIG. In the sixth embodiment of the present invention, a three-dimensional space is divided into a plurality of small spaces as a tree structure specialized for space search in the first to fourth embodiments, and data in the small space is divided into a plurality of small spaces. By using a tree structure to be managed, a virtual space is managed as shown in FIG.

Also in this embodiment, the tree structure can be easily mounted, and when the three-dimensional shapes are evenly distributed in the virtual space, the tree for efficiently managing the three-dimensional figures used in the fourth embodiment is used. The effect is obtained that a search efficiency equivalent to the structure (range search, that is, the number of scan nodes is 0 (logN)) can be realized.

Embodiment 7 In the seventh embodiment of the present invention, a two-dimensional space is divided into regions according to the distribution state of data as a tree structure specialized for spatial search in the fourth embodiment, so that dynamic data can be obtained. A plurality of tree structures for realizing good area division are prepared for static data. As these tree structures, besides the tree structure used in Embodiment 1, for example, Osawa, Sakauchi:
"A Proposal of Multidimensional Data Management Structure with Good Dynamic Characteristics"
(Transactions of the Institute of Electronics, Information and Communication Engineers, Vol. J66-D, N
o. 10, 1983), etc., and these tree structures have characteristics in terms of ease of implementation, search efficiency, tree generation time, and the like. Therefore, by preparing a plurality of trees, an optimal tree structure is selected according to the purpose. can do.

Embodiment 8 FIG. In the eighth embodiment of the present invention, a three-dimensional space is divided into regions according to the distribution state of data as a tree structure specialized for space search in the fourth embodiment, so that dynamic data can be obtained. A plurality of tree structures for realizing good area division are prepared for static data. As these tree structures, in addition to the tree structure used in the fourth embodiment, “Jansen, F.,
Data Structures for Ray T
racing, Data Structures fo
r Raster Graphics, p57-73,
1986 "etc., and these tree structures have characteristics in terms of ease of implementation, search efficiency, tree generation time, and the like. Can be.

[0071]

As described above, according to the present invention, the number of nodes to be operated at the time of drawing can be greatly reduced without causing information loss, so that the drawing speed of the browser can be improved.

Further, according to the present invention, since the tables having the same texture are sorted, the number of switching of the texture (drawing attribute) at the time of drawing can be reduced, and the drawing speed of the browser can be improved. There is an effect that can be.

[Brief description of the drawings]

FIG. 1 is a block diagram showing an apparatus for converting virtual space data using a tree structure according to a first embodiment of the present invention.

FIG. 2 is a flowchart showing a processing procedure according to the first embodiment of the present invention.

FIG. 3 is a flowchart illustrating a processing procedure of tree structure decomposition.

FIG. 4 is an explanatory diagram of a tree structure decomposition.

FIG. 5 is an explanatory diagram of node connection.

FIG. 6 is an explanatory diagram of a relationship between a three-dimensional shape and area information / projected figure.

FIG. 7 is an explanatory diagram of conversion from a reference tree structure to a scene tree structure.

FIG. 8 is an explanatory diagram of a browser node scanning procedure at the time of drawing.

FIG. 9 is an explanatory diagram of a relationship between node scanning and a bounding box.

FIG. 10 is a block diagram showing an apparatus for converting virtual space data using a tree structure according to a second embodiment of the present invention.

FIG. 11 is a flowchart showing a processing procedure according to the second embodiment of the present invention.

FIG. 12 is a flowchart illustrating a processing procedure of tree structure storage table division.

FIG. 13 shows T _opt (0), T _opt (1) _,.
It is explanatory drawing of T _opt generation from _opt (q).

FIG. 14 is a block diagram showing a virtual space data conversion device using a tree structure according to a third embodiment of the present invention.

FIG. 15 is a flowchart showing a processing procedure according to the third embodiment of the present invention.

FIG. 16 is a block diagram showing an apparatus for converting virtual space data using a tree structure according to a fourth embodiment of the present invention.

FIG. 17 is a flowchart showing a processing procedure according to the fourth embodiment of the present invention.

FIG. 18 is an explanatory diagram of virtual space management using a tree structure that divides a two-dimensional space into a plurality of small spaces and manages the data in the small spaces.

FIG. 19 is an explanatory diagram of a virtual space management using a tree structure that divides a three-dimensional space into a plurality of small spaces and manages the data in the small spaces by preserving them.

FIG. 20 is a block diagram showing a conventional virtual space data conversion device using a tree structure.

FIG. 21 is a flowchart showing a conventional processing procedure.

FIG. 22 is a flowchart showing a conventional difference level determination procedure.

FIG. 23 is an explanatory diagram of a conventional joining operation procedure of a shape-related information table.

FIG. 24 is a flowchart showing a processing procedure for generating a tree structure from a conventional shape-related information table.

FIG. 25 is an explanatory diagram of a conventional tree structure on a straight line having a depth of 5;

FIG. 26 is an explanatory diagram of a conventional tree structure generation procedure.

[Explanation of symbols]

101 scene tree structure decomposition unit (scene tree structure decomposition means), 102 tree structure storage table generation unit (tree structure storage table generation means), 103 tree structure storage table, 1
04 reference tree structure generation unit (reference tree structure generation means), 10
5 tree structure coupling unit (tree structure coupling unit), 106 tree structure storage table division unit (tree structure storage table division unit),
107 mesh shape generation unit (mesh shape generation means), 108 reference tree structure generation method selection unit (reference tree structure generation method selection means).

Claims (9)

[Claims] 1. A virtual space data using a tree structure is inputted, and a given tree structure is converted into one of information of the original tree structure without destroying information embedded in the tree structure itself. Scene tree structure decomposing means for decomposing into a tree structure group holding a part, and a tree structure storage table for storing information on one tree structure as one set for the decomposed tree structure group, Tree structure storage table generating means for adding bounding box information as area information of each set of shapes, and reference tree structure generating means for generating a reference tree structure specialized for spatial search based on the bounding box information And a tree structure combining means for combining a reference tree structure generated by the reference tree structure generation means and a tree structure group stored in the tree structure storage table. An apparatus for converting virtual space data using a structure. 2. A virtual space data using a tree structure is input, and a given tree structure is converted into one of information of the original tree structure without destroying information embedded in the tree structure itself. Scene tree structure decomposing means for decomposing into a tree structure group holding a part, and a tree structure storage table for storing information on one tree structure as one set for the decomposed tree structure group, Tree structure storage table generating means for adding bounding box information as region information of each set of shapes, and holding at least one type of texture in accordance with the texture information held by each set of the tree structure storage table Tree-structured storage table dividing means for dividing the set into a plurality of tables so that the set exists in the same table; A reference tree structure generating means for generating a reference tree structure specialized for spatial search based on the loading box information; and a reference tree structure generated by the reference tree structure generating means and the divided tree structure storage table. A virtual space data conversion device using a tree structure, comprising: a tree structure combining means for combining the stored tree structure groups. 3. A virtual system using a tree structure according to claim 1, further comprising mesh shape generation means for meshing shape information in the tree structure generated by the tree structure connection means. Spatial data converter. 4. A reference tree structure generating method for storing a method of generating a reference tree structure specialized for a plurality of spatial searches, and selecting a predetermined method from a plurality of stored methods in accordance with a user's instruction. The reference tree structure generation unit includes a selection unit based on the bounding box information of the shape managed by each set of the tree structure storage table.
The method of generating a reference tree structure specialized in spatial search using a method of generating a reference tree structure specialized in the predetermined spatial search selected by the reference tree structure generation method selecting means. An apparatus for converting virtual space data using the tree structure according to 1. 5. A reference tree structure generating method for storing a method for generating a reference tree structure specialized for a plurality of spatial searches, and selecting a predetermined method from a plurality of stored methods in accordance with a user's instruction. Selecting means for each of the divided tree structure storage tables based on the bounding box information of the shape managed by each set of the tree structure storage tables; 3. The tree structure according to claim 2, wherein a method of generating the reference tree structure specialized for the predetermined space search selected by the selection means is used to generate the reference tree structure specialized for the space search. Conversion device for virtual space data used. 6. A tree structure specialized in spatial search, wherein a two-dimensional space is divided into a plurality of small spaces, and a tree structure for managing data in the small space is used. An apparatus for converting virtual space data using a tree structure according to any one of claims 1 to 5. 7. A tree structure specialized for spatial search, wherein a tree structure is used which divides a three-dimensional space into a plurality of small spaces and manages data in the small spaces. An apparatus for converting virtual space data using a tree structure according to any one of claims 1 to 5. 8. The tree structure according to claim 1, wherein a tree structure that divides a two-dimensional space into regions according to the distribution state of data is used as a tree structure specialized for spatial search. An apparatus for converting virtual space data using a tree structure according to claim 1. 9. The tree structure according to claim 1, wherein a tree structure that divides a three-dimensional space into regions according to the distribution state of data is used as a tree structure specialized for spatial search. An apparatus for converting virtual space data using a tree structure according to claim 1.