JPH03238559A - Setting processing method for bounding volume - Google Patents

Abstract

PURPOSE:To reduce the number of cross judgement times by deciding the propriety of BV (Bounding Volume) setting from the number of slave nodes and the projecting area of BV of a master node with the projecting area of BV of a noticing node on a screen as the basis. CONSTITUTION:The projecting area of the bounding volume on the screen is calculated and the bounding volume is set in the node if it is S<(n-1)Sp/n and it is not set if not when the projecting area of the bounding volume of the node is set to be S, the projecting area of the bounding volume of the master node to be Sp and the number of the slave nodes to be (n) as against respective nodes of a constructive solid geometry tree. Thus, the number of cross judgement times is reduced and the generation time of a picture is shortened.

Description

[Detailed description of the invention] [Technical field to which the invention pertains] The present invention relates to a technique for generating one image.

Constructive solid geometry is an object definition method used in ray tracing, etc.
uctlve 5 solid Geotaetry (
Bounding Volume (hereinafter abbreviated as BV) used for
(abbreviated as ))).

[Prior Art] FIG. 8 shows an example of defining object data using a C3G model. In the C3G model, objects are defined in a tree structure as shown in FIG. The ray tracing method is a method of calculating whether a ray intersects with an object, and if the ray intersects with the object, determining the brightness of the object at that point to generate an image. In order to efficiently determine the intersection between an object and a ray, the CSC model:
Bounding Volume for each node of CSC tree
A solid with a simple shape such as a rectangular parallelepiped or a sphere called (B V ) is set.

The BV set for a node is set as a solid with the minimum volume that includes all primitives under it.

When the BV is set in this way, the intersection between the '#yJ body and the ray is determined by determining the intersection with the BV set at the root node of the CSC tree, and if it intersects, the intersection is determined with the BV of the child node. It can be executed by proceeding with the calculation as follows, and finally determining the intersection of leaf nodes with primitives. If it does not intersect with a BV on the way, the BV under that node
Cross determination with can be omitted. By doing so, the number of intersection determinations can be significantly reduced.

[Problems to be Solved by the Invention] In the conventional method, a BV is set for each node of the CSC tree to reduce the number of intersection determinations. However, from the viewpoint of reducing the number of cross determinations, setting a BV for each node is not necessarily the best. In some cases, the number of cross-judgments may be reduced if no BV is set for a certain type of node.

SUMMARY OF THE INVENTION In order to solve the above-mentioned problems, the present invention provides a means for determining whether or not a BV stage can be set, and aims to further reduce the number of intersection determinations.

[Means to solve the problem]

The present invention executes a first process, a second process, a third process, and a fourth process as shown in the process flow of the embodiment illustrated in FIG.
Based on the projected area of the BV of the node of interest on the screen, determine whether or not a BV should be set for the node based on the number of children of the node and the projected area of the BV of the parent node of the node and the Kii node. In this way, it is decided whether or not to set the BV stage.

In conventional technology, a method was used to set a BV that minimized the projected area by utilizing only the fact that the smaller the projected area of the BV on the screen, the greater the calculation time reduction effect (( 1) HJegh
orst, G., Hooper, D., P., Greenbe.
rg:'Io+proved Computation
alMethods for Ray Tracing
, ACM Trans,onGraphics,
Vol, 3. NO, 1, l) p, 52-69. J
an, 1984 (2) T.L., Kay, J.T.
Kajiya:”Ray Tracing Complete
x 5cenes”, Compute, Graphi
cs, Vol, 20+No, 4. pp, 269-2
78.1986).

〔Example〕

The present invention will be explained in detail below. To simplify the explanation, the following assumptions are made.

■ The structure of the given C3G tree is not changed.

■ Each node of the C3G tree is usually ANDed or ORed.
However, here it is assumed that the CSC tree is composed only of OR connections.

■ A C3G tree is a primitive (C
3C: BV of the same type of shape is set for each node.

■ The BV projection area is included in the screen surface.

The BV set for a node in the C3G tree does not need to completely include the BV of a child node as long as it includes all of its descendant leaf nodes. An example is shown in FIG. Figure 2 shows a two-dimensional example, where BV is a circle,
The 9-leaf node is also a circle. Note that FIG. 2(a) shows a tree structure, and FIG. 2(b) shows an inclusion situation.

Now, let's focus on the root node of the CSC tree. Assume that the parent-child relationship of the node is as shown in FIG. 3(a). Set BV for each node (nL n2. n3).

Considering their projection onto the screen surface, see Figure 3).
The 0 problem as follows is to determine whether or not to set a BV to node n1.

If the number of calculation steps for determining the intersection between one ray and one BV- is Cr, the projected area of BV is St, and the area of the screen is SO, then the number of calculation steps C1 when placing BV in nl is C1
-3O-Cr+S1.2Cr 2) The number of calculation steps C2 when BV is not placed in nl is C2=2.5o-Cr.

Therefore, when C1<C2, it is advantageous to place BV at nl. Namely.

s 1 < s O/ 2 ---------1 (1
) is advantageous. Generally, when the number of children is n, S 1 < (n-1) S O/ n ------
(It is advantageous if you are 21.

The same can be said for intermediate nodes.

In this case, the projected area of the BV of the node of interest is determined by considering the common portion of the projected areas of the BVs of its ancestor nodes. In other words, if the projected area of the first node of interest is Si, the number of children of the second node of interest is n, and the area of the common part of the projected areas of ancestor nodes is 5(i), then 5(i) ns i< (n −
1) 5(i) /n - (3). Here, when a relationship is established in which the BV of each node is completely included in the BV of its parent node, 5(i) becomes the projected area of the BV of the parent node, and the left side of equation (3) becomes Si.

From these formulas.

■ You can determine whether to set a BV based on the projected area ■ If the number of children is large, even if the projected area of the node you are looking at is much larger than the area of the common part of the projected areas of its ancestor nodes (i.e. It is more advantageous to set the BV (even if it is about (nl)/n) (2) It can be seen that the projected area of the child's BV is not related to the BV step setting determination condition.

FIG. 4 shows an example of calculation time reduction by setting the BV stage. Fourth
Figure (a) shows the case without BV setting.

FIG. 4(0)) shows the case where BV setting is applied to the root node, and FIG. 4(C) shows the case when BV setting is applied to each node. Setting V as shown in FIG. 4 (0) may seem wasteful at first glance, but in reality, the calculation time can be reduced by nearly 40% by setting the BV stage. Figure 4 (
Setting the BV as in C) (surrounding it with a frame) will further improve the effect. Note that in FIG. 4 (dl represents the relationship between nodes.

Next, when the projected area of the BV increases due to a change in the BV helical shape or simplification of calculation of the included BV, an increase in the number of intersection determinations due to this increase will be considered.

Now, suppose the number of children of node i (>O) is ni, the projected area of BV is Si, and the screen area is SO.

The number of cross determinations T is T=SO+Σni*(S (i) n S i)
-1---(4) where S (i) is the above-mentioned common part for node i.

Now, suppose that 5(i)nS i increases by ΔSt.

The number of intersection determinations T' at that time is.

T'=so+Σni*(S(i)ns++Δ5t)-3
O+Σni rate (S (i) n S i)*(1+Δ
St/(S(i) n5i)). Here MAX (ΔS i/ (S(i) r″1si))
= p, the above formula becomes 7 T'=SO+(1+I))Σni*(S (i) n
S i)<(1+p)T −・−・・−・
-(5). 5(i)ns i=S i, then p is B
It represents the rate of increase in the projected area of V.

If the number of calculation steps for the intersection point calculation for a given BV spiral shape is Cr, then the total number of steps for the intersection point calculation is Cr-T. Here, depending on the shape of BV. The value of Cr varies depending on the architecture of the computer. Generally, the number of calculation steps for calculating the intersection of BY having a complicated shape is large.

This is because the total number of calculation steps for intersection point calculation is determined by the product of Cr and T.

It is important to minimize the product. Even if the projected area is somewhat large, it may be advantageous to use a BV with a simple shape that requires a small number of calculation steps for calculating the intersection point.

Furthermore, Equation 1 (5) shows that when S (i) 100 St uniformly increases by q%, the number of intersection determinations can be suppressed by an increase of q% at most. Therefore, when finding the inclusive BV, it is not necessarily necessary to find the minimum solution, but it is practically sufficient to find the approximate minimum solution.

A BV setting algorithm can be constructed using equations (1) to (3).

Bvi algorithm FIG. 6 shows the BV setting algorithm, and FIG. 7 shows the called "rBV setting determination" routine. Note that the current node in the figure corresponds to the current node.

(1): For each node in the C3G tree, set the minimum BV that includes all the BVs of its own descendant leaf nodes (for convenience, BV is also set for two-leaf nodes).

(2): Depth First from root node
Find out the following using 5search.

(2,1): Calculate equation 1), (2) or (3) for the current node.

(2, 2) Set if n2 is satisfied. Execute the above process (2) for the next node.

(2, 3): If not satisfied, the node with the largest area BV among the child nodes is expanded into the form of a child node as shown in FIG. Considering the expanded tree as a new tree, perform the above process (2) on the current node.

I would like to add a few points to the assumptions assumed at the beginning of the example.

■ The BV set for an AND connection node is generally smaller than the BV of its child nodes. Therefore, the BV setting problem can be considered as if the node were a leaf node. Therefore, the initial assumption is valid. The BV to be set in the AND node can be found by considering this node as the root and applying it.

(2) Case in which catadioptric light is included 1. For example, 2. The number of calculation steps for determining the intersection between the BV of an object and the light ray that can be seen by the reflected light can also be evaluated by the area on the projection plane. In this case, - Membrane perspective transformation ((3) M, 5hinyaT, Takahash
i, S, Na1to:”Pr1nciples an
dApplications of Pencil T
racing IComputerGraphics+
Vol, 21+ No, 4+ pp, 45-5
4JLIL, 1987) to calculate the area of the BV on the projection plane.

[Effects of the Invention] As explained above, according to the two aspects of the present invention, it is possible to reduce the number of times of negative layer intersection determination and to shorten the time required to generate one image, compared to the conventional method.

[Brief explanation of drawings]

Fig. 1 is a processing flow of an embodiment of the present invention, Fig. 2 is an example of BV setting, Fig. 3 is a diagram of projection of BV onto the screen surface, Fig. 4 is a diagram showing the BV stage setting effect, and Fig. 5 is a diagram showing an example of BV setting. Diagram showing the expansion of nodes. FIG. 6 shows a BV setting algorithm, FIG. 7 shows a BV setting determination routine, and FIG. 8 shows an example of a C3G model.

Claims (1)

[Claims] An object is defined by a constructive solid geometry model, and bounding is applied to the constructive solid geometry model for the purpose of reducing the amount of calculation.
A method for generating an image by setting a volume and using the constructive solid geometry model in which the bounding volume is set, including: (1) calculating the projected area of the bounding volume on the screen; (2) ) For each node of the constructive solid geometry tree, the projected area of the bounding volume of the node (S), the projected area of the bounding volume of the parent node of the node (Sp), and the number of children of the node. (n), if S<(n-1)Sp/n, a bounding volume is set for the node; otherwise, it is not set. How to set up a bounding volume.