JP2000082155A - Pre-processing method for three-dimensional high speed plotting processing - Google Patents

Abstract

PROBLEM TO BE SOLVED: To optimize a detail level table to be used in a three-dimensional plotting system. SOLUTION: A detail level table held by a current table 50 represents a corresponding relation between the set of the size of an object and the distance from a point of view and the detail level of a model to be used for plotting the object. A simulation part 42 calculates the size and distance of each object in the view field based on an object DB(data base) 10. Then, the detail level corresponding to the size and distance is obtained from a current table 50, and the number of polygons of the model of the detail level is obtained from the object DB10, and the number of polygons is added for all the objects in the view field. A table adjusting part 44 compares the added result with the number of polygons to be plotted in a real time by a three-dimensional plotting system, and when the added result is larger, the table adjusting part 44 adjusts the setting of the current table 50 by judging that real time plotting is impossible. This process is repeated continuously the prescribed number of times until it is judged that the real time plotting is possible.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for preprocessing in a three-dimensional drawing system for changing the level of detail of a model used for drawing an object according to the distance from the viewpoint of the object and its size. The present invention relates to a method of adjusting the correspondence between the distance from the viewpoint and the object size and the degree of detail of the model in accordance with the distribution of objects in a region to be drawn.

[0002]

2. Description of the Related Art In the CG (computer graphics) world, when a viewpoint is constantly changing in a predetermined space, a process of drawing an image viewed from the viewpoint in real time is often performed. For example, a walk-through animation in a factory is one example. The walk-through animation in the factory is created based on polygon data of equipment and devices installed in the factory. In the walk-through animation, an image viewed from the viewpoint position at each time is created and displayed in real time according to the movement of the viewpoint. For this reason, at each time, from the information on the position of the viewpoint and the direction of the line of sight at that time, a region (called a visible region) that can be seen from the viewpoint within the space inside the factory is specified, and the facilities and equipment included in the visible region The polygon data of the object is read, and a drawing process for the visible region is performed based on the polygon data.

[0003] With CG, it is possible to express various spaces in detail, and users' expectations for CG are further increased. On the other hand, there is a constant need to draw more objects faster and more precisely. Although the performance of computers has increased rapidly in recent years, it is not easy to satisfy all of these demands.

[0004] One of the techniques for performing accurate drawing with a moderate speed is a management technique called LOD (Level-Of-Detail). The LOD is also called the level of detail at the time of drawing, and a plurality of models having different levels of detail are prepared in advance for each object. When the space to be drawn is determined, an object closer to the viewpoint has a higher level of detail (LOD), that is, an elaborate model, and an object farther from the viewpoint is drawn with a lower level of detail, that is, a simplified model. . This method is based on the fact that objects closer to the viewpoint have a greater effect on the subjective quality of the image.Near objects are precisely drawn to ensure the subjective quality of the image, and objects far away are roughly roughened. The speed of the drawing process is increased by drawing. This LOD method is described in, for example, “Flight Simulation” (edited
by JMRolfe and KJStaples, Cambridge University
Press), Chapter 7.4.3.

[0005] However, in the case of the conventional LOD management method, there is not a very clear criterion as to which level of detail model is to be applied to which object in which scene.

On the other hand, the applicant of the present invention has disclosed Japanese Patent Application No. 9-23 / 1990.
No. 6191 proposed an LOD management method for determining the degree of detail when drawing an object according to the size of the object. In an embodiment of the method, the object is divided into a plurality of groups in terms of size, and the distance from the viewpoint to the object is also divided into a plurality of ranges. Then, for each combination of the size group and the distance range, the degree of detail at the time of drawing the object corresponding to the combination is determined, and the relationship is tabulated.
This table is set such that the larger the object is, the higher the detail is, and the closer the distance from the viewpoint is, the higher the detail is. When drawing an object, the size of the object and the distance from the viewpoint are obtained, the level of detail corresponding to the combination is obtained from the table, and the object is drawn using the model of the level of detail.

[0007]

The time required to draw an image of one frame varies depending on the machine power of a three-dimensional drawing system that performs a drawing process, and how complicated an object is in a space to be drawn. Also depends on how many exist. Therefore, the aforementioned LOD
In order to ensure real-time performance when the management method is applied to individual cases, it is necessary to perform appropriate LOD management in consideration of the power of the drawing system to be used and the complexity of the space to be drawn.

The above-mentioned LOD management method proposed by the present applicant does not sufficiently deal with this point, and adjusts the table used for determining the level of detail according to the power of the drawing system and the complexity of the drawing target space in the individual case. The challenge was to develop a method to make it properly.

SUMMARY OF THE INVENTION The present invention has been made in view of such a problem, and draws each object by using a detail level table indicating the relationship between the size of the object, the distance from the viewpoint and the corresponding level of detail. An object of the present invention is to provide a method of adjusting a detail level table according to the power of the system and the complexity of the target space in a three-dimensional drawing system that determines the level of detail at the time.

[0010]

SUMMARY OF THE INVENTION The present invention has been made to achieve the above object, and has a plurality of models having different degrees of detail for each object in a predetermined space. A three-dimensional rendering system that has a detail level table indicating the relationship between the distance from the object and the corresponding level of detail, and renders each object using a model of the detail level specified by the detail level table. A preprocessing method for adjusting a degree table according to an object distribution in the predetermined space, wherein (a) temporarily setting the detail level table; and (b) the predetermined level based on a given viewpoint and viewing direction. (C) obtaining information on the size of each object included in the visible area and the distance from the viewpoint; And (d) specifying the level of detail of the model when drawing each object in the visible region with reference to the level of detail table based on the acquired information on the size of each object and the distance from the viewpoint. Determining whether the total drawing data amount when each of these objects is drawn using the model of the detail level exceeds the real-time processable data amount of the three-dimensional drawing system; and (e) the step ( If it is determined in d) that the total drawing data amount does not exceed the real-time processable data amount, at least one of the viewpoint and the line-of-sight direction is changed, and the process returns to step (b). If it is determined that the total drawing data amount exceeds the real-time processable data amount, the setting of the detail level table is changed to the total drawing data amount. (F) changing according to a predetermined rule for gradually reducing the data amount and returning to the step (b); Outputting a detail level table as an adjustment result when it is determined that the data amount does not exceed the possible data amount.

Here, the drawing data amount refers to the data amount of the drawing target, and is a value corresponding to the time required for the drawing processing of the drawing target. For example, the number of polygons to be rendered is an example of the rendering data amount. The three-dimensional drawing system
When rendering an object, a detail level corresponding to a combination of the distance and the size of the object from the viewpoint is obtained from a detail level table, and rendering processing is performed using the model of the detail level. Therefore, if the distance from the viewpoint changes even for the same object, the degree of detail changes and the drawing data amount also changes. The total drawing data amount is a total sum of the drawing data amounts when each object included in the visible area is drawn by the model of the detail level obtained from the detail level table. The visible region is a region that is “visible” in a predetermined space, and is specified by determining a viewpoint and a viewing direction.

According to the present invention, a visual region at that time is obtained while changing a viewpoint and a line-of-sight direction in a predetermined space in various ways, and whether the total drawing data amount of the visible region exceeds the real-time processing capability of the three-dimensional drawing system is determined. Determine whether or not.
If it is determined that the amount of data to be drawn is exceeded, the setting of the detail level table is adjusted stepwise according to a predetermined rule so that the amount of drawing data is reduced as a whole. And after this adjustment,
The above simulation is repeated again. In this repetition, by changing the viewpoint and the line of sight in various ways, it is checked whether real-time drawing is possible from various positions in the predetermined space.

When it is determined that real-time drawing is possible for a predetermined number of times in succession, it is determined that real-time drawing is possible for the entire predetermined space, and the detail level table at this time is employed for drawing processing in the predetermined space. In addition,
The number of consecutive times as a criterion for determination may be determined from the viewpoint of statistics. By using the detail level table adjusted in this way, drawing processing can be performed in real time with a high probability in terms of statistics, regardless of where the visible area is set in the predetermined space.

According to the above-mentioned method, if the condition (f) is satisfied in the detail level table temporarily set, the performance of the three-dimensional drawing system is fully utilized in the table in the temporarily set state. There is a possibility that it could not be done. Therefore, in a preferred embodiment of the present invention, in such a case, the detail level table is adjusted in a direction in which the total drawing data amount is increased stepwise. This is called an increase adjustment mode. In the increase adjustment mode, when it is determined that the total drawing data amount when the visible area is changed does not exceed the data amount that can be processed in real time for a predetermined number of consecutive times, the detail level table is displayed in a direction in which the total drawing data amount increases. Adjust to By repeating this, the detail level table immediately before the total drawing data amount first exceeds the real-time processable data amount is adopted as the adjusted table for the final drawing process.
According to this method, it is possible to maximize the performance of the three-dimensional drawing system and provide a high-quality image within a range in which real-time performance can be guaranteed.

In a preferred aspect of the present invention, the representative length of the object is used as the size of the object as a parameter for determining the level of detail, and the distance from the viewpoint and the size of the object at the point where the level of detail switches by one step are determined. Temporary setting and setting change of the detail level table are performed so that the ratio becomes substantially constant. According to this aspect, when all the objects have substantially the same viewing angle, the degree of detail is switched, and a natural degree of detail switching can be realized.

Further, in a preferred aspect of the present invention, it is possible to limit the generation range of the viewpoint position when switching the visible region.

[0017]

Embodiments of the present invention (hereinafter referred to as embodiments) will be described below with reference to the drawings.

[Three-dimensional drawing system] First, the configuration of a three-dimensional drawing system to which the method of the present embodiment is applied will be described with reference to FIG.

In the system shown in FIG.
The B (database) 10 is a database in which information of each object in the drawing target space is registered. Here, for each object in the drawing target space, (m + 1)
Model M0-M of the level of detail of the stage (m is a predetermined positive integer)
m has been created, and the definition information of the model of each level of detail is registered in the object DB 10. In the following, M0 is assumed to be the most detailed model.
It is assumed that the detail decreases as the number increases as 2, M3.

FIG. 2 is a diagram showing the contents of registration data of individual objects stored in the object DB 10. The object data includes an identification number (ID) 100 of the object and size information 10 of the object.
2. Includes object position information 104 and data 106 of models M0 to Mm in (m + 1) stages with different levels of detail. As the object size information 102, the volume, surface area, representative length, and the like of the object can be used, and any information may be used as long as the objects are unified. The size information 102 does not necessarily have to be strict. For example, as the volume of an object, the volume of a circumscribed cuboid (also called a bounding box) of the object may be used. The representative length of the object may be determined according to a certain rule, such as the distance between the vertices of the object at the widest interval. Also, the position information 104 of the object can be variously defined. As an example, the center of gravity of the object, the center of gravity of the circumscribed cuboid of the object, and the like can be considered.

In order to improve the drawing speed and other processing speeds, the size information 102 and the position information 104 are stored in M0 in advance.
It is preferable to calculate from the model data 106 and the like and register it in the object DB 10.

Each model is represented by a polygon. For example, a model can be represented as a set of three-dimensional coordinates in the rendering target space of each vertex that constitutes the model (polygon model). In this case, information on the position of the model in the drawing target space can be obtained from the coordinates of each vertex of the model.

For example, when a drawing target space including an object group is constructed by a CAD (computer-aided design) system, polygon data of an object output by the CAD system can be adopted as the most detailed model M0. . The low-detailed model can be created step by step from the most detailed model M0. For example, a model with a reduced number of polygons can be created by combining a plurality of adjacent polygons in M0 into one polygon according to a predetermined rule. Further, a primitive (basic solid) such as a sphere, a polygonal prism, or a polygonal pyramid close to the shape of M0 can be obtained, and the primitive can be used as a low-detailed model. Alternatively, “not display” may be adopted as a low-detailed model. In this case, the “not displayed” model will be the model Mm with the lowest level of detail.

It should be noted here that the three-dimensional drawing system (and the detail level table adjusting device in the present embodiment).
"Object" is the system that created the original of the "Object" (eg, CAD system)
Is not necessarily the same as the object defined in. For example, even if a device composed of several parts is treated as one object in a CAD system, individual parts of the device can be regarded as objects in a three-dimensional drawing system. Which level is regarded as an "object" depends on the design concept of the three-dimensional drawing system. As an example, an object in CAD can be decomposed into simple shape elements according to a predetermined rule, and the elements can be treated as “objects” in a three-dimensional drawing system. As a method for automatically decomposing polygon data of an object in CAD into simpler shape elements, for example, Japanese Patent Application No. 9-3410 filed by the present applicant etc.
No. 09 can be used.

On the other hand, the detail level table 30 is, for example, as shown in FIG.
As shown in FIG. 3, the matrix is configured as a matrix of the distance D from the viewpoint of the object and the size G of the object. For each combination of the distance D and the size G, the degree of detail of the model corresponding to the combination (in this example, M0 to M0) M3) are registered. In the table of FIG. 3, the distance D from the viewpoint is
Are divided into eight ranges of distances d0, d1,..., D7 in order from the viewpoint closest to the viewpoint, and the size G is G0,
G1,..., G5. Distance D
The user of the system may freely decide how to classify the size and the size G.

The detail level table 30 is constructed based on the following two basic rules. The first rule is to use a more detailed model closer to the viewpoint, and the second rule is to use a more detailed model as the size is larger. From these two rules, as shown in FIG.
The table setting is such that the degree of detail is higher at the lower left (that is, nearer and larger) of the table, and is lower at the upper right.

The three-dimensional drawing system uses the object DB 10 and the detail level table 30 to execute a drawing process in the following procedure. First, information on the position of the viewpoint and the direction of the line of sight is acquired by the viewpoint / sight line acquiring unit 20. For example, when producing a walk-through animation, information on the viewpoint position and the line-of-sight direction is sequentially extracted from the previously input viewpoint movement path and the line-of-sight direction setting information at each point on the path. Next, the drawing processing unit 22 specifies a view volume based on the acquired information on the gaze position and the gaze direction. The view volume is a region that is “visible” from a viewpoint in space, and can also be called a viewing space or a visible region. The view volume can be specified by a well-known method based on information of a predetermined viewing angle and depth of the viewing field, and a viewpoint position and a viewing direction that change from time to time. Next, the drawing processing unit 22 selects an object group included in the view volume from among the object group registered in the object DB 10 (that is, “visible”).
Stuff). This process is called culling or clipping.

Then, the drawing processing section 22 draws each of the extracted objects. In the drawing processing, the drawing processing unit 22 first obtains, for each object, the distance and size of the object from the viewpoint, and searches the detailed level table 30 for a model detail corresponding to the distance and size. Then, the polygon data of the model of the obtained degree of detail is read from the object DB 10, and drawing is performed based on the polygon data.

[Detail Level Table Adjustment] In the three-dimensional rendering system described above, in order to render the image of the view volume when the viewpoint and the line of sight are changed every moment, the detail level table 30 must be The settings need to be adjusted appropriately. Hereinafter, the table adjustment will be described.

In the present embodiment, when the view volume is variously changed in the drawing target space, it is determined whether or not the current view volume can be processed in real time by the processing capability of the three-dimensional drawing system. This determination is made, for example, based on whether or not the number of polygons included in the view volume falls within the number of polygons that can be processed in real time by the three-dimensional rendering system. If it is determined that real-time processing is not possible, the setting of the detail level table is adjusted. Such processing is repeated, and the detail level table when the real-time processing is determined to be statistically determined to be possible regardless of how the view volume is selected in the drawing target space is output as an adjustment result. .

Hereinafter, an apparatus configuration and a processing procedure for realizing such processing will be sequentially described.

(1) Apparatus Configuration Referring to FIG. 4, an apparatus configuration for adjusting the detail level table according to the present embodiment will be described. This device can be constructed as software based on, for example, a general-purpose computer system. This device may be constructed as a part of the three-dimensional drawing system, or may be configured as a device independent of the three-dimensional drawing system.

In FIG. 2, the object DB 10 is
It is the same as that used by the three-dimensional drawing system, and is typically constructed on a large-capacity storage medium. The current table 50 and the previous table 52 are tables corresponding to the detail level table 30 of the three-dimensional drawing system. In the present embodiment, the setting of the detail level table is adjusted little by little to find the optimum setting. The current table 50 holds the current setting of the detail level table in this adjustment process, and the previous table 52 holds the previous setting.

The viewpoint / line-of-sight generator 40 randomly generates a viewpoint position and a line-of-sight direction. Simulation unit 42
Specifies a view volume based on the viewpoint position and the line of sight in the same manner as in the case of the drawing system, and simulates a drawing process of an object group in the view volume. In this simulation, it is sufficient to determine whether or not the view volume can be drawn in real time by the three-dimensional drawing system, and it is not necessary to actually perform the drawing processing. As a simulation, for example, a process of adding the number of polygons of an object in a view volume is sufficient. At the time of this simulation, the simulation unit 42 determines the level of detail of each object with reference to the setting of the current level of detail table held in the current table 50, and stores a model of the level of detail in the object DB.
Search from 10 and simulate.

The table adjustment section 44 controls the entire apparatus and adjusts the settings of the current table 50 based on the simulation result of the simulation section 42. At this time, the table adjustment unit 44 copies the setting contents of the current table 50 up to that time to the previous table 52 and holds the contents, if necessary.

(2) Processing Procedure Next, with reference to FIGS. 5 and 6, an example of a procedure for adjusting the detail level table in the present embodiment will be described.

In the present embodiment, the detail level table is provisionally set first, and the table is adjusted little by little to determine the detail level table setting suitable for the drawing target space. That is, a drawing simulation is performed using the table, and it is determined whether or not real-time drawing processing is possible based on the simulation result, and the table is adjusted based on the determination. The table adjustment includes a decrease direction adjustment and an increase direction adjustment.

The adjustment in the decreasing direction is a table adjustment for reducing the total number of polygons in the view volume (ie, reducing the time required for the drawing process), and is an adjustment in a direction for reducing the set value of the model detail level in the table. .

Conversely, the increase direction adjustment is a table adjustment for increasing the total number of polygons in the view volume, and is an adjustment in the direction of increasing the set value of the model detail level in the table. In the present embodiment, first, it is determined whether or not real-time drawing is possible based on the temporarily set detail level table. If it is determined that the real-time drawing is not possible, the table is adjusted little by little in the decreasing direction adjustment, and conversely, it is determined that it is possible. In this case, adjust the table little by little by adjusting the direction of increase.

Hereinafter, the adjustment procedure will be described in more detail with reference to a flowchart. FIG. 5 is a flowchart showing the flow of the overall processing procedure. In the procedure shown in FIG. 5, the decrease direction adjustment is considered as a basic mode, and the increase direction adjustment is treated as a special mode called “increase adjustment mode”. That is, a typical flow is considered in which the detail level table is gradually adjusted in the decreasing direction from the temporarily set state, and finally an appropriate table setting is obtained. However, this treatment is relative, and those skilled in the art can easily understand that the processing procedure when the increase direction adjustment is set to the basic mode is essentially the same.

In the procedure of FIG. 5, first, the table adjustment unit 4
4 is for temporarily setting the current table 50 and 3
The number of polygons that can be processed in real time by the dimensional drawing system is set as a threshold (S10). Here, the number of polygons that can be processed in real time is determined in advance by the administrator of the drawing system based on catalog values, experience, and the like. Here, "real-time processing is possible" means that drawing processing of a view volume is completed within a frame interval of moving image display. The temporary setting of the current table 50 may be performed by interactively receiving an input from the user, or may be performed by simply copying the setting contents created in advance to the current table 50. Also,
At this time, the table adjustment mode is set in a decreasing direction (referred to as a decreasing adjustment mode).

Next, the value of the counter representing the number of simulations is initialized to 1 (S12). Then, a drawing simulation is performed (S14). In the drawing simulation (S14), as shown in FIG. 6, first, the viewpoint / sight line generating unit 40 randomly generates a viewpoint position and a viewpoint direction (S142). Next, the simulation unit 42 specifies a view volume from the viewpoint position and the line-of-sight direction (S144), and performs a culling process (S146). Then, the simulation unit 42 acquires the number of polygons at the time of drawing for each object in the view volume extracted by the culling process (S148). S
At 148, the distance from the viewpoint is calculated for each object (S150). The distance from the viewpoint is obtained from information on the position of the viewpoint and the position of the object stored in the object DB 10. Object D
Obtain object size information from B10 (S15
2). Any of S150 and S152 may be executed first. Next, referring to the current table 50, the degree of detail of the object is determined from the combination of the distance from the viewpoint and the size. And the object DB 10
Then, the number of polygons of the model of the object of the detail level is obtained (S156). Then, the simulation unit 42 calculates the total number of polygons of all objects in the view volume thus obtained, and passes the result (ie, the total number of polygons) to the table adjustment unit 44 (S158).

Referring back to FIG. 5, the table adjusting unit 44
Compares the total number of polygons received from the simulation unit 42 with the threshold value set in S10 (S1
6). In this comparison, if the total number of polygons is equal to or smaller than the threshold value (determination result No), it is determined that all objects in the view volume can be drawn in real time. In this case, the value of the counter indicating the number of simulations is incremented by 1 (S18), and the result is compared with a preset upper limit number of simulations (S20). If the value of the counter is equal to or less than the upper limit, the process returns to S14, and the above-described simulation is repeated again by changing the viewpoint position or the line of sight. In this way, simulation is performed while sequentially changing the view volume, and if the determination that real-time drawing processing is possible (S16 is No) continues for the upper limit number of times (S20 is No), the view volume is set anywhere in the drawing target space. Even if it is set, it is statistically determined that real-time drawing processing is possible. Therefore, the upper limit number needs to be determined statistically from such a viewpoint.

In this embodiment, real-time drawing is not possible in the provisionally set state of the detail level table (Yes in S16).
Is determined, the table adjustment is subsequently performed in the decrease adjustment mode, and conversely, if it is determined that real-time drawing is possible in the temporary setting state (No in S20), the table adjustment is performed in the increase adjustment mode thereafter. Hereinafter, each case will be described in order.

(A) Procedure in Decrease Adjustment Mode Drawing simulation while changing the viewpoint and line of sight (S1)
In the process of repeating 4), if the determination result of S16 becomes Yes before the number of repetitions reaches the upper limit number,
It means that it is impossible to draw the view volume in real time by setting the detail level table at that time. The processing in this case differs depending on whether the table adjustment mode is in the decreasing direction or the increasing direction. For this reason, it is determined whether the mode is set to the increase adjustment mode (S34). When the detail level table is in the temporary setting state, the mode is the decrease adjustment mode, so the determination result in S34 is No, and the setting of the current table 50 is adjusted in a direction in which the number of polygons decreases according to a predetermined rule.

When the detail level table of FIG. 3 is adjusted in the decreasing direction, a table setting as shown in FIG. 7, for example, is obtained. That is, in the decreasing direction adjustment, the boundary between M0 and M1 and M
The boundary between 1 and M2 is lowered overall (i.e., the boundary is moved in the direction of "larger" and "closer"), and the range to which a model with high detail is assigned is reduced. At this time, the manner and degree of movement of the boundary line are determined in advance. For example, a method of moving the boundary of the degree of detail downward one frame at a time from the lower right corner of the table at a time, and sequentially moving the boundary toward the upper left corner can be considered. It is also conceivable to change the inclination of the boundary line at predetermined intervals. When the adjustment of the current table 50 is completed in this way,
The counter of the number of simulations is initialized to 1, and S1
The processing after 4 is repeated.

As described above, when the determination result of S20 is No in the process of adjusting the decreasing direction of the table (S36) and the simulation (S14 to S20),
This means that the detail table (current table 50) has been adjusted to the point where it is statistically determined that the whole drawing target space can be processed in real time. Therefore, by using the settings of the current table 50 at this time, it is possible to draw an image when the visual field changes every moment in the drawing target space in real time. Moreover, since this setting is obtained by repeating fine adjustment for gradually reducing the number of polygons, the drawing performance of the three-dimensional drawing system is effectively used.

As an actual processing procedure, when S20 is No, it is next determined at S22 whether the adjustment mode of the table is the increase adjustment mode. Since this example is the decrease adjustment mode, the determination result in S22 is No. Then, next, it is determined whether or not the current table 50 remains in the temporary setting state (S28). In the flow of this example, since the current table 50 has undergone the decreasing direction adjustment (S36), the current table 50 does not remain in the temporarily set state, and the determination result in S28 is N
It becomes o. As a result, the setting of the current table 50 becomes
The final adjustment result is output (S32).

(B) Procedure in the increase adjustment mode The table adjustment mode is set to the increase adjustment mode when the result of determination in S20 is No when the detail level table (current table 50) is in the temporary setting state. That is, it is only when it is determined that the entire drawing target space can be processed in real time.

The table setting at this time is sufficient only for the purpose of real-time processing, but it is not yet known whether it is sufficient from the viewpoint of effective use of the drawing processing capability of the three-dimensional drawing system. In the setting state of the tentative setting, a rough model is adopted too much, and the drawing processing capability of the three-dimensional drawing system may be lost. Therefore, in the present embodiment, an increase adjustment mode is provided in order to effectively use the capability of the three-dimensional drawing system.

In a specific processing procedure, if the determination result in S20 is No, it is checked whether the table adjustment mode is set to the increase adjustment mode (S2).
2). When the current table is in the tentative setting state, the mode is set to the decrease adjustment mode, and the determination result in S22 is No. Then, it is next determined whether or not the detail level table is in the temporary setting state (S28). In this example, since the determination result is Yes, the table adjustment mode is set to the increase adjustment mode (S30). Then, the setting state of the current table 50 is changed to the previous table 5
2 (S24), and then copy the current table 50
Is adjusted in the increasing direction according to a predetermined rule (S
26). The method of adjusting the increasing direction may be the reverse of the case of adjusting the decreasing direction described above. That is, the boundary of the range of each level of detail in the table may be moved in the opposite direction by the same movement and degree as in the decrease direction adjustment. When the increase direction adjustment is completed, the simulation counter is initialized (S12), and the simulation process from S14 is repeated.

In this repetition, if the determination result of S20 is No again, it is determined that the adjustment of the table in the increasing direction is insufficient, and the adjusting of the increasing direction is further performed. That is, the determination result of S22 is Yes, the setting of the previous table 52 is updated by the setting of the current table 50 (S24), and then the current table 50 is adjusted in the increasing direction.

If the total number of polygons exceeds the threshold value in S16 during such repetition, this means that real-time drawing processing is determined to be impossible for the first time in the flow of adjustment in the increasing direction. is there. In other words, it can be determined that the table has been adjusted to the limit in the flow of adjustment in the increasing direction, and as a result, it has reached a point where real-time drawing is impossible. The setting of the detail level table at this time cannot be adopted because real-time processing is not possible, but the setting immediately before that makes real-time drawing processing possible and 3
The processing capability of the three-dimensional drawing system is often used effectively. Since the previous setting state is held in the table 50 last time, this may be output as the final adjustment result of the detail level table. That is, in the present embodiment, if it is determined that the mode is the increase adjustment mode after the determination result of S16 is Yes (S34), the previous table 5
0 is output as a final adjustment result (S3
8).

(3) Preferred Example of Table Adjustment A preferred example of fine adjustment of the table in the above processing procedure will be described. As an example of the detail level table, for example, FIG.
Please refer to.

In this example, the detail level table is set so that the detail level of the model is switched where the appearance of each object becomes substantially the same, and the setting is adjusted so as to satisfy the condition. .

The size of the appearance of an object is proportional to the viewing angle (ie, the angle at which the object is viewed from the viewpoint). Strictly speaking, the viewing angle is determined by the ratio of the length of the projection of the object onto the plane perpendicular to the line of sight and the distance from the viewpoint to the object.However, since strictness is not required here, priority is given to processing speed, and The representative length of the object itself is used instead of the length. That is, the inclination of the object with respect to the line of sight is not considered. As the representative length, for example, a distance between two farthest vertices of the object can be used.

That is, in this example, the representative length of the object is used as the size G in the detail level table.
The boundary line of the model detail level in the detail level table is determined so that the ratio between the representative length of the object and the distance is substantially constant. Then, when adjusting the setting of the table, the boundary line is moved so as to satisfy the condition. In other words, if the distance and size in the table are constant, the boundary line comes near a straight line passing through the origin (distance = 0, size = 0). The boundary line itself is step-shaped, but the overall tendency is to be a straight line passing through the origin. The adjustment of the table is performed by changing the inclination of the boundary line.

According to this example, when the objects have substantially the same viewing angle, the detail level of the model is switched, and a natural detail level switching can be realized.

(4) Effect As described above, according to the embodiment, the detail level table used in the three-dimensional drawing system can be used in a state where the drawing capability of the system can be effectively used while real-time performance of the drawing process is guaranteed. Can be adjusted up to.

(5) Modification Next, a modification of the embodiment will be described. In this modification, together with the adjustment of the boundary of the detail level in the detail level table, the step of the range of the distance from the viewpoint in the table is adjusted.

In this modification, it is possible to adjust the distance which is the boundary of the range of the distance from the viewpoint (d0 to d7 in FIG. 3) in the detail level table. Instead, a fixed upper limit number of polygons is assigned to each distance range. Then, when adjusting the table, the boundary distance is determined so as to satisfy the upper limit polygon number of each distance range. The number of distance ranges in the detail level table is arbitrarily set by the user. The total number of upper polygons assigned to each distance range is 3
The dimension rendering processing system decides to be substantially equal to the number of polygons that can be rendered in real time.

The processing procedure of the present modification will be described below with reference to FIGS. 8 and 9 focusing on differences from the above-described embodiment. 8 and 9, steps indicating the same processing contents as the steps in FIGS. 5 and 6 are denoted by the same reference numerals, and the description is simplified.

As can be seen from the overall processing procedure shown in FIG. 8, in this modification, the entire framework of the processing is the same as that of the above embodiment, except for the contents of the simulation. In this modification, the boundary distance determination simulation (S50) and the accompanying boundary distance determination processing (S50)
54 and S56) are only different from the above embodiment,
Hereinafter, only the differences will be described.

Boundary distance determination simulation (S50)
Is shown in FIG. The procedure from the switching of the viewpoint and the line of sight (S142) to the culling (S146) is the same as the procedure in FIG. Hereinafter, the boundary distance is determined by the simulation unit 42 in the following procedure in the order from the viewpoint closer to the viewpoint.

That is, first, the distance from the viewpoint of each object in the view volume obtained by culling is calculated, and the objects are sorted in the order of the distance from the viewpoint (S200). The result of the sorting is an array in which the object information is arranged in the order closer to the viewpoint. The information of each object includes three data items: an identification number of the object, size information of the object, and a distance from the viewpoint of the object.

Next, a counter n indicating the number of the boundary distance is initialized to 1 (S202). The distance of the point closest to the viewpoint of the view volume is set as the 0th boundary distance.
FIG. 10 shows the correspondence between the distance range and the boundary distance. As is clear from the figure, the distance at the boundary between the distance range d (n-1) and dn is the n-th boundary distance. It is assumed that the number of distance ranges in the detail level table is set to N (that is, d0 to d
(N of (N-1)) and the boundary of the last distance range in the detail level table are the boundaries between d (N-2) and d (N-1), and (N
-1) The first boundary.

Next, the integrated value of the number of polygons is initialized to 0 (S204). Next, it is checked whether an unprocessed object remains in the array of the object sorting result (S206). If there is an unprocessed object, information on the object closest to the viewpoint (including data on identification information, size, and distance from the viewpoint) is obtained (S2).
08), the object is set to “processed”. Then, with reference to the current table 50, a model detail level corresponding to the size of the object in the distance range d0 is obtained (S210). And the object DB1
From 0, the data of the model of the object of the detail level is extracted, and the number of polygons is obtained (S212).

Next, the number of polygons obtained in S212 is added to the integrated value (S214), and it is checked whether the integrated value exceeds the upper limit polygon number in the distance range d0 (S216).
If not, the process returns to S206 to extract an unprocessed object closest to the next viewpoint from the sorting result, and then proceeds to S20.
8 to S216 are repeated. In such a repetition, if the integrated value exceeds the upper limit polygon number of d0 in S216, the distance from the viewpoint of the object in the immediately preceding loop (that is, the distance from the viewpoint of the object immediately before exceeding the upper limit polygon number) is set. The distance is determined as the first boundary distance (S218), and this distance is stored. Then, the value of the counter n is incremented by 1 (S220), the process returns to S204, the integrated value of the number of polygons is initialized to 0, and the processes of S206 to S216 are repeated to calculate the next boundary distance.

When the (n-1) th boundary distance is determined in this way, the distance range d (n
The model detail level corresponding to the size of the unprocessed object is obtained from the column of (-1) (S210), and the number of polygons of the model of the detail level is sequentially accumulated (S212, S21).
4) If the integrated value exceeds the upper limit polygon number of the distance range d (n-1) (S216), the distance from the viewpoint of the immediately preceding object is determined as the n-th boundary distance (S21).
8). Then, the value n of the counter indicating the number of the boundary distance is incremented by 1 (S222), and it is determined whether or not this value n has exceeded the last boundary number (N-1) (S22).
2).

If n> N−1 is satisfied in S222, it indicates that the integrated value of the number of polygons of the object in the view volume exceeds the number of polygons that can be processed in real time by the three-dimensional processing system. Each distance range d0
This is because the sum of the upper limit number of polygons of d (N-1) is set substantially equal to the number of polygons that can be processed in real time by the three-dimensional drawing processing system. In this case, error termination (S
224), the process is passed to the table adjustment unit 44, and the routine shifts to S52 in the main routine in FIG.

If n> N−1 is not satisfied in S222,
Returning to S204, the processing described above is repeated. Then, in this repetition, if the processing is completed up to the last object of the sort result before the result of S222 becomes Yes (that is, the determination result of S206 is No), this means that all the objects in the view volume are drawn in real time. Indicates that it can be processed. In this case, each boundary distance obtained so far is stored as a simulation result (S
226). As a result, the boundary distance determination simulation ends normally (S228), and the processing is performed by the table adjustment unit 44.
To S52 of the main routine in FIG.

The procedure of the boundary distance simulation described above is described in Japanese Patent Application No.
This is an application of the idea of the method disclosed in Japanese Patent No. 56929.

When the boundary distance determination simulation is completed (S224 or S228), the table adjustment unit 4
No. 4 determines whether or not it is an error end (S224) (S52). If this result is No (normal end), it indicates that real-time drawing is possible, and the same processing as when the determination result of S16 is No in the procedure of FIG. If the determination result of S20 is No,
Since the simulation results using the current table 50 (that is, the 0th to N−1th boundary distances) have been accumulated for the simulation upper limit number of times, they are stored as total data. At this time, if the total data of the simulation result obtained by using the previous setting of the current table 50 already exists, it is discarded.

On the other hand, if the determination result in S52 is Yes, it means that real-time drawing is not possible, and the same processing as in the case where the determination result in S16 is Yes in the procedure of FIG.

When the above processing is repeated and the determination result in S28 is No, it means that the detail level table has been appropriately adjusted in the reduction adjustment mode. Here, the boundary distance of each distance range in the detail level table is statistically determined based on the total data of the simulation results stored (S56). For example, a method of adopting the shortest distance among the results of each simulation is conceivable. The method of this determination is disclosed in Japanese Patent Application No. 10-56929. Then, the respective boundary distances determined in this way are reflected on the boundary distances of the respective distance ranges of the current table 50, and the results are output as adjustment results of the detail level table (S
32).

If the determination result in S34 is Yes, it means that an appropriate detail level table has been obtained in the increase adjustment mode. Also in this case, the boundary distance of each distance range in the detail level table is statistically determined based on the totaled data of the stored simulation results (S5).
4). The tabulation data used here corresponds to the previous table setting, which matches the contents of the previous table 52 output in S38. The respective boundary distances determined in this way are reflected on the boundary distances of the respective distance ranges in the previous table 52, and the results are output as adjustment results of the detail level table (S38).

As described above, according to this modification, the setting of the model detail level in the detail level table can be adjusted, and the distance value at the boundary of each distance range in the table can also be adjusted.

The method described above can be realized by causing a computer to execute a program describing the processing content of each step described above. In this case, the program is supplied to the user via a communication medium in the form of a recording medium such as a floppy disk or a CD-ROM. This program can be executed by installing it from a recording medium into, for example, a fixed disk device attached to a computer.

The preferred embodiment of the present invention and its modifications have been described above. In each of the above examples, the generation range of the viewpoint position in the simulation is the entire drawing target space. However, when the range of the viewpoint is limited to a certain range in the drawing target space, such as in a walk-through animation in which the moving path of the viewpoint is predetermined, by limiting the generation range of the viewpoint to that range, The processing time of the simulation can be reduced.

[Brief description of the drawings]

FIG. 1 is a functional block diagram showing a configuration of a device for adjusting a detail level table.

FIG. 2 is a diagram showing a data configuration of individual objects registered in an object DB (database).

FIG. 3 is a diagram illustrating an example of a detail level table.

FIG. 4 is a diagram showing an apparatus configuration for adjusting a detail level table.

FIG. 5 is a flowchart illustrating a processing procedure according to the embodiment.

FIG. 6 is a flowchart showing a detailed procedure of a drawing simulation.

FIG. 7 is a diagram illustrating another example of a detail level table.

FIG. 8 is a flowchart illustrating a processing procedure according to a modification.

FIG. 9 is a flowchart showing a detailed procedure of a boundary distance determination simulation.

FIG. 10 is a diagram illustrating a relationship between a distance range and a boundary distance.

[Explanation of symbols]

10 Object DB (database), 40 viewpoint / gaze generation unit, 42 simulation unit, 44 table adjustment unit, 50 current table, 52 previous table.

────────────────────────────────────────────────── ───

[Procedure amendment]

[Submission date] July 27, 1999 (July 7, 1999
7)

[Procedure amendment 1]

[Document name to be amended] Statement

[Correction target item name] Claims

[Correction method] Change

[Correction contents]

[Claims]

[Procedure amendment 2]

[Document name to be amended] Statement

[Correction target item name] 0010

[Correction method] Change

[Correction contents]

[0010]

SUMMARY OF THE INVENTION The present invention has been made to achieve the above object, and has a plurality of models having different degrees of detail for each object in a predetermined space. A three-dimensional rendering system that has a detail level table indicating the relationship between the distance from the object and the corresponding level of detail, and renders each object using a model of the detail level specified by the detail level table. A preprocessing method for adjusting a degree table according to an object distribution in the predetermined space, wherein (a) temporarily setting the detail level table; and (b) the predetermined level based on a given viewpoint and viewing direction. (C) obtaining information on the size of each object included in the visible area and the distance from the viewpoint; And (d) specifying the level of detail of the model when drawing each object in the visible region with reference to the level of detail table based on the acquired information on the size of each object and the distance from the viewpoint. Determining whether the total drawing data amount when each of those objects is drawn using the model of the detail level exceeds the real-time processable data amount of the three-dimensional drawing system; and (e) the step (e). If it is determined in d) that the total drawing data amount does not exceed the real-time processable data amount, at least one of the viewpoint and the line-of-sight direction is changed, and the process returns to step (b). If it is determined that the total drawing data amount exceeds the real-time processable data amount, the setting of the detail level table is changed to the total drawing data amount. And (f) changing the total drawing data amount in the step (d) continuously for a predetermined number of times in the real-time processing. If it is determined not to exceed the data amount, viewed including the steps of outputting the level of detail of the table at that time as an adjustment result, and the parameters of the verbosity decision
As the size of the object, the representative length of the object
From the viewpoint at the point where the level of detail switches by one level
The ratio between distance and object size is almost constant
Tentative setting and setting change of the detail level table .

[Procedure amendment 3]

[Document name to be amended] Statement

[Correction target item name] 0015

[Correction method] Change

[Correction contents]

[0015] In this onset bright, as the size of the object that is the parameters of the verbosity determining, using a characteristic length of the object, the ratio of the size of the distance and the object from the viewpoint in that the degree of detail is switched one step so that substantially constant, by performing temporary setting and configuration changes detail level table, any object granularity is switched when it is substantially the same viewing angle, it is possible to achieve a natural level of detail switching.

Claims (4)

[Claims] An object has a plurality of models having different degrees of detail for each object in a predetermined space, and has a detail level table indicating a relationship between an object size and a distance from a viewpoint and a corresponding level of detail. A three-dimensional rendering system for rendering each object using a model of the detail level specified by the detail level table, wherein the detail level table is adjusted in accordance with the object distribution in the predetermined space; (A) temporarily setting the detail level table; (b) specifying a visible area in the predetermined space based on a given viewpoint and line-of-sight direction; (c) being included in the visible area Obtaining information on the size of each object and the distance from the viewpoint; (d) from the obtained size and viewpoint of each object Based on the information on the distance, the level of detail of the model when drawing each object in the visible region is specified by referring to the level of detail table, and when each of those objects is drawn using the model of the level of detail, The total drawing data amount is 3
(E) determining whether the total drawing data amount does not exceed the real-time processable data amount in step (d). If at least one of the viewpoint and the line-of-sight direction is changed and the process returns to the step (b), and it is determined in the step (d) that the total drawing data amount exceeds the real-time processable data amount, Changing the setting of the table in accordance with a predetermined rule for gradually reducing the total drawing data amount and returning to the step (b); and (f) repeating the step (d) a predetermined number of times. When it is determined that the total drawing data amount does not exceed the real-time processable data amount, a detail level table at that time is output as an adjustment result. The method comprising the step, the. 2. The method according to claim 1, wherein the total drawing data amount is changed to the real-time processable data in the step (d) continuously for a predetermined number of times using the detail level table provisionally set in the step (a). If it is determined that the amount does not exceed the amount, the process proceeds to the increase adjustment mode. In the increase adjustment mode, it is determined that the total drawing data amount does not exceed the real-time processable data amount in step (d) for a predetermined number of consecutive times. In this case, the setting of the detail level table is changed according to a predetermined rule for gradually increasing the total drawing data amount, and the process returns to the step (b). When it is determined that the data amount exceeds the real-time processable data amount, the setting of the immediately preceding detail level table is output as an adjustment result. How to with. 3. The method according to claim 1, wherein a representative length of the object is used as the size of the object, and the provisional setting and the setting change of the detail level table switch the detail level by one step. The method is performed so as to satisfy a condition that a ratio between a distance from a viewpoint and an object size is substantially constant. 4. The method according to claim 1, wherein in the step (b), the position of the viewpoint is limited to a predetermined area in the predetermined space. And how.