JP3241638B2 - Three-dimensional shape deformation method, information storage medium and manufacturing method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for deforming a three-dimensional shape and an image synthesizing system using the method. More specifically, the present invention relates to a three-dimensional shape effective as a modeling technique in computer graphics (CG). Method for deforming a shape, information storage medium storing a program for realizing the method, and 3 generated by the method
The present invention relates to an information storage medium that stores information on a dimensional shape.

[0002]

2. Description of the Related Art In CG (computer graphics), a three-dimensional shape to be expressed (hereinafter referred to as an object)
Various modeling techniques have been developed to obtain. One of such modeling techniques is to create a new object by combining or deforming a plurality of objects. FIGS. 1A and 1B use a Boolean modeling technique called Boolean. FIG. 5 is a diagram showing a state in which three objects 32, 34, and 36 are united to create one object 38. Here, the object 38 in FIG.
When it is desired to create a smooth object 38 'as in (C), there is no appropriate modeling technique.

The closest one is a technique called a metaball which combines a plurality of objects to obtain a smoothly shaped object.

[0004] The metaball is a modeling technique that considers a density distribution defined by a density distribution and spread around a point around a point in a three-dimensional space. Concentration is greatest at the center, decreasing with distance from the center,
It is assumed that the distance becomes 0 after a certain distance. FIG. 2 shows a density curve curve 10 in which the density distribution is graphed, and an object 16 obtained by a metaball.

The horizontal axis represents the distance from the center, and the vertical axis represents the density. The distance from the center point 12 to the point at which the density becomes 0 is called the effective radius r. This effective radius r is different from the actually visible radius. The actually visible radius is the radius of the portion where the concentration is 1 or more. The value 1 serving as the branch point is called a threshold, and the radius at that time is called a threshold radius s. This threshold radius s is the apparent radius, and what looks like an object is a sphere 16 of radius s. That is, the metaball object defined by the density curve 10 is a sphere 16 having a radius s.

FIG. 3 is a diagram showing a state where two metaballs are fused. In FIG. 3, the metaball 25 defined by the density curve curve 21 and the metaball 26 defined by the density curve curve 22 come close to each other, and the effective radii overlap. As described above, the density is simply added in the overlapping portion 23, and the portion draws a density distribution like a density curve curve 24. Therefore, the density increases, and the portion where the density was 1 or less becomes 1 or more (24-a,
24-b), the unseen part also becomes visible (2
5 ', 26'). This is the metaball deformation.

FIG. 4 shows the two meta balls (A) to (C).
The object after deformation is shown when the object is gradually approached in the order of (H). In FIG. 4A, the effective radii of the two objects 25-1 and 26-1 do not overlap, or the density of the overlapped portion is equal to or less than the threshold value. In such a case, the objects are not deformed. .

In FIG. 4B, two objects 25
In the portions where -2 and 26-2 face each other, the effective radius overlaps to form a portion where the density is equal to or higher than the threshold, and the portions where the objects face each other are deformed. FIG.
In (C), the facing portion is further deformed, and the two objects are fused after FIG. 4 (D). 4 (E) to FIG. 4 (G), the degree of fusion is increased. In FIG. 4 (H), the deformed object 28 in a state where the centers of the two objects 25 and 26 overlap each other.
Is represented.

[0009]

As described above, when modeling is performed using metaballs, a smooth shape can be formed. However, there are the following problems.

[0010] First, the shapes of all objects are smoothly rounded, and it is not possible to form an angular portion.

Second, since objects fuse only when they come close to each other, it is difficult to arrange objects closely without merging them.

Further, there is a problem that it is difficult to predict the final shape, and it is difficult to use it in combination with other primitives. Therefore, with the metaball, as shown by the object 38 'in FIG. 1 (C), it was not possible to create an object in which an angular shape and a smooth shape coexist in one object.

SUMMARY OF THE INVENTION The present invention has been made in view of the above problems, and a three-dimensional shape deformation method capable of easily controlling a shape and generating various shapes in which an angular shape and a smooth shape coexist. Another object of the present invention is to provide an information storage medium storing a program for realizing the method and an information storage medium storing information of a three-dimensional shape generated by the method.

[0014]

According to one aspect of the present invention, there is provided a method of deforming a three-dimensional shape.
A deformation condition setting step of setting surface tension and pressure acting on the surface of the three-dimensional shape as deformation conditions;
A constraint condition setting step of setting a constraint condition for deforming the three-dimensional shape based on the three-dimensional shape; a deformation condition set in the deformation condition setting step; and a constraint condition set in the constraint condition setting step. And a deformation calculating step of deforming the three-dimensional shape based on the above.

The three-dimensional shape deformation method of the present invention is a method in which surface tension and pressure are applied to a three-dimensional shape, and the three-dimensional shape is deformed based on the result of the action according to a dynamic model.

In the deformation condition setting step, the surface tension and pressure to be applied are set. Applying surface tension and pressure to a three-dimensional shape means that the three-dimensional shape is a model that can be deformed into a shape that is dynamically determined based on the surface tension and pressure, and a parameter for the deformation is used. Is to give surface tension and pressure. Perform 3 in the present invention
Unlike the natural world model, the deformation of the dimensional shape is performed based on the surface tension and pressure given by the parameters. Therefore, it is not necessary to specify the absolute values of the surface tension and the pressure as the parameters, and the ratio between the two may be used. .

However, if the deformation is performed without any constraint in accordance with the laws of mechanics, the ball will become a sphere, expand to infinity, or shrink infinitely and approach zero. Therefore, in the present invention, a constraint condition is provided based on the shape of the three-dimensional shape before deformation, and a certain restriction is imposed on the shape deformation. By providing such a constraint condition, it is possible to perform a deformation that is affected by the properties of the original three-dimensional shape.

In the deformation calculation step, the surface tension and the pressure given by the parameters are applied to the three-dimensional shape, and the shape is deformed under a constraint condition until a mechanical equilibrium state is reached.
As the mechanical model at this time, a model that keeps the surface tension and the pressure constant irrespective of changes in the surface area and volume values of the three-dimensional shape due to deformation, or either one of them,
Or a model in which both change.

In the case where the three-dimensional shape is deformed in accordance with the above-mentioned mechanical model, it is possible to control the deformation of the shape such as smoothing or expanding by specifying the surface tension and pressure to be applied by parameters. it can. Therefore, the final shape can be predicted based on an empirical rule, and since it is based on a mechanical model of the natural world, it is effective when it is desired to reproduce a complicated shape in the natural world.

According to a second aspect of the present invention, in the first aspect, the same deformation condition is set for the entire three-dimensional shape in the deformation condition setting step.

Therefore, it is effective when the entire three-dimensional shape is desired to be deformed under the same conditions.

According to a third aspect of the present invention, in the first aspect, in the deformation condition setting step, different deformation conditions are set for each part of the three-dimensional shape.

Therefore, it is effective when it is desired to deform each part of the entire three-dimensional shape under different conditions. Further, since partial control is possible, the range of deformation is widened, and control for obtaining a desired shape can be easily performed.

According to a fourth aspect of the present invention, in any one of the first to third aspects, in the constraint condition setting step, the constraint condition is set so as not to deform the inside or outside of the three-dimensional shape before deformation. And

According to the three-dimensional shape deformation method of the present invention, by applying appropriate surface tension and pressure as parameters and providing constraint conditions, a new shape that retains the characteristics or properties of the original three-dimensional shape is provided. Can be obtained. For example, it is possible to obtain a three-dimensional shape or the like in which the original three-dimensional shape is inflated while leaving an angular part, or a three-dimensional shape or the like in which the corner of the original three-dimensional shape is rounded. it can.

According to a fifth aspect of the present invention, in the first aspect of the present invention, in the deformation calculating step, the surface tension and the pressure set in the deformation condition setting step are applied to the three-dimensional shape to form the three-dimensional shape. A balance between the acting surface tension and the pressure force is calculated, and a deformation calculation is performed until the surface tension and the pressure are balanced within the range of the constraint condition.

According to the three-dimensional shape deformation method of the present invention, the calculation of the three-dimensional shape deformation by the applied surface tension and pressure is performed by calculating the force acting on each part of the object based on the applied surface tension and pressure. It can be performed by a dynamic calculation for obtaining a balanced three-dimensional shape by deformation. Therefore,
It is possible to provide a three-dimensional shape deformation method capable of performing an object deformation calculation by a calculation according to a dynamic model in the natural world.

According to a sixth aspect of the present invention, in any one of the first to fourth aspects, in the deformation calculating step, the surface tension and the pressure set in the deformation condition setting step are applied to the three-dimensional shape to form the three-dimensional shape. The potential energy of surface tension acting and the potential energy of pressure are calculated, and the deformation calculation is performed until the sum of the two potential energies is minimized within the range of the constraint condition.

According to the three-dimensional shape deformation method of the present invention, the calculation of the deformation of the three-dimensional shape by the applied surface tension and pressure is performed by calculating the sum of the potential energy of the surface tension and the potential energy of the pressure acting on the three-dimensional shape. Can be performed by a dynamic calculation for obtaining a three-dimensional shape when is in a minimum state. Therefore, it is possible to provide a three-dimensional shape deformation method capable of performing an object deformation calculation by a calculation according to a dynamic model of the natural world.

By performing image synthesis using the present system, a desired shape and a complicated shape can be obtained with easy control. Further, various shapes in which an angular shape and a smooth shape coexist can be obtained.

An information storage medium according to a seventh aspect of the present invention is an information storage medium for storing a program code for deforming a three-dimensional shape. And storing a program code for performing the program.

The information storage medium of the present invention stores a program code for executing the three-dimensional shape deformation method according to any one of claims 1 to 6. For this reason, the information storage medium is provided as an external storage medium of a given computer system, or by loading a program code stored in the information storage medium into an internal storage medium of a given computer system. The three-dimensional shape deformation method according to any one of claims 1 to 6 can be easily implemented by the computer system of (1).

[0033] The information storage medium according to the invention of claim 8 is an information storage medium for storing information of a three-dimensional shape.
3 deformed by any one of the three-dimensional shape deformation methods
At least one of dimensional shape information and image information generated based on the three-dimensional shape is stored.

In the information storage medium of the present invention, at least one of the information of the three-dimensional shape deformed by the three-dimensional shape deformation method according to any one of claims 1 to 6 and the image information generated based on the three-dimensional shape is stored. It is memorized including.

Therefore, by loading the information storage medium as an external storage medium of a given computer system, or by loading the information stored in the storage medium into an internal storage medium of a given computer system, An image is generated by using information of a three-dimensional shape deformed by the three-dimensional shape deformation method according to any one of claims 1 to 6 or image information generated based on the three-dimensional shape by a given computer system. Can be done.

Here, the information storage medium is R
It includes AM, ROM, magnetic tape, CD, floppy disk, and the like.

A method for generating image information of a three-dimensional shape, wherein the image information of the three-dimensional shape is generated based on the three-dimensional shape deformed by the three-dimensional shape deformation method according to any one of claims 1 to 6. May be configured.

A system for generating image information of a three-dimensional shape, wherein the image information of the three-dimensional shape is generated based on the three-dimensional shape deformed by the three-dimensional shape deformation method according to any one of claims 1 to 6. And means for storing the image information generated by the image information generating means in a given information storage medium.

With this configuration, it is possible to provide a method and a system for generating image information of a three-dimensional shape based on the three-dimensional shape deformed by the three-dimensional shape deformation method according to any one of claims 1 to 6. I can do it.

A system for generating an image of a three-dimensional shape, wherein the three-dimensional shape is generated based on information of the three-dimensional shape deformed by the three-dimensional shape deformation method according to any one of claims 1 to 6 and the three-dimensional shape. Reading out at least one of an information storage medium storing at least one of image information and three-dimensional shape information stored in the information storage medium and image information generated based on the three-dimensional shape; And a means for generating the image information.

A method of displaying an image of a three-dimensional shape, wherein the three-dimensional shape is generated based on information of the three-dimensional shape deformed by the three-dimensional shape deformation method according to any one of claims 1 to 6 and the three-dimensional shape. The information storage medium storing at least one of the image information and the image information may be used to display an image on a given image display device.

According to a ninth aspect of the present invention, there is provided a method for manufacturing a video master recording medium, wherein at least one still image is recorded using a three-dimensional shape. It is created using a three-dimensional shape deformed by the three-dimensional shape deformation method according to any one of claims 1 to 6.

According to a tenth aspect of the present invention, there is provided a method of manufacturing a video master recording medium for a moving image, in which a plurality of gradually changing still images are recorded using a three-dimensional shape. The still image is created using a three-dimensional shape deformed by the three-dimensional shape deformation method according to any one of claims 1 to 6.

In this way, it is possible to create a video master recording medium which records a still image created using the three-dimensional shape deformed by the three-dimensional shape deformation method according to any one of the first to sixth aspects.

[0045] A method of manufacturing a video recording medium according to the invention of claim 11 is to copy a video using the video of the video master recording medium manufactured by the manufacturing method of claim 9 or 10 as a source video, and to copy the copied video to a recording medium. To manufacture a copy recording medium.

Here, the video master recording medium and its copy recording medium are concepts including a video recording medium for moving images and a video recording medium for still images, and include movie films, video tapes, video disks, CDs, and the like. Shall be considered.

By doing so, it is possible to create a large number of video recording media on which videos created based on the three-dimensional shape created by the method of the present invention are recorded.

A video master recording medium is manufactured by the manufacturing method of claim 9 or 10, a video is copied using the video of the medium as a source video, and the copied video is recorded on a recording medium to manufacture a copy recording medium. You may make it.

[0049]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS A preferred embodiment of the present invention will be described by taking as an example a case where the shape of an object specified by three-dimensional shape data is deformed.

FIG. 5 is a diagram showing how the shape of an object is deformed using the method of the present invention. FIG.
The object 30-0 shown in FIG. 5A represents the shape before the change, and the object 30-0 shown in FIGS.
Reference numerals -1 and 30-2 are obtained by deforming the object 30-0 by applying surface tension and pressure by the method of the present invention. The object 30-1 in FIG.
The object 30-0 in (A) is deformed into a smooth shape, and the object 30-2 in FIG. 5 (C) is further deformed into a rounded shape.

As described above, the inventor of the present application applies the method of deforming a three-dimensional shape, which is the method of the present invention, to the method of CG modeling, and obtains an angular shape and a smooth shape in one object. We developed a modeling method that enables coexistence of shapes and easy control of shapes. The method of the present invention
This is a method of deforming the shape by applying surface tension and pressure to the surface of the object.

The effect of the action of the surface tension and pressure used in the present invention is inspired by the effect of the action of the surface tension and pressure of the liquid. Liquids tend to make all surfaces as small as possible. Surface tension is the force that acts in a direction that seeks to minimize the surface area of the liquid, and is quantitatively the force that acts perpendicular to the unit length line on the surface of the liquid.

The surface tension and pressure acting on the object will be described below by taking the surface tension and pressure acting on the soap bubble as an example.

FIG. 7A shows that when the surface tension acting on the soap bubble 100 is σ (kgf / cm), the bubble 1
Each side m1 of a square M having a side of 1 cm on the surface of 00,
surface tension σ acting on m2, m3, m4 (kgf / c
It is a figure showing the image of m). In the present embodiment, the surface tension when the surface tension is applied to the object is the aforementioned σ. Further, the force acting on the square M due to the surface tension is the resultant force α of the forces acting on each side.
(Kgf), the α (kgf) is the soap bubble 10
FIG. 7B shows a state of acting on 0. FIG. 3 is a sectional view taken along a line XX when the soap bubble 100 is cut along a plane including the center of gravity of the square M and the center of the soap bubble, and shows a force α (kg) acting on the square M by surface tension.
f).

FIG. 8A shows the pressure p acting on the soap bubble 100 when the external pressure is not considered (the external pressure is set to 0).
It is a figure showing (kgf / cm ² ). In the present embodiment, the pressure when applying pressure to an object is p. Here, the force acting on the square M of 1 cm per side on the surface of the soap bubble 100 is p (kg).
f).

The reason why the soap bubble 100 is kept in an equilibrium state is that, as shown in FIG. 8 (B), in each portion of the soap bubble 100, a force .alpha.
And the force β acting on each part by the pressure p is balanced.

In the present embodiment, the surface tension σ and the pressure p are applied to the three-dimensional shape by designating the surface tension σ and the pressure p described above as parameters.
Perform dimensional shape deformation. Unless considering the constraint conditions described later, this deformation means that the force α acting on each part due to the surface tension σ and the force β acting on each part due to the pressure p are balanced to form a shape when they are in an equilibrium state. It is to make it.

Even if the object is subjected to surface tension and pressure and is deformed without any constraint, if the internal pressure is too large compared to the surface tension, the object expands and becomes a sphere or infinity. If the surface tension is too large compared to the internal pressure, the object shrinks to zero. In this case, no matter what object is deformed, the shape becomes infinity, sphere, or 0, so that it has little meaning as modeling.

However, for example, surface tension and pressure are applied to the object 30-0 shown in FIG.
The object 30-1 having a smooth shape shown in FIG.
The object 3 having a further expanded shape shown in FIG.
If 0-2 can be obtained, effective modeling can be performed.

On the other hand, when an artist deforms an object, if the shape is deformed in some relation to the shape of the original object, the deformation can be controlled and the shape can be predicted, which is an effective modeling technique.

Therefore, in the method of the present invention, a constraint condition for deforming the object is set based on the shape of the object before deformation.

For example, in the modification shown in FIG. 5B, a constraint condition is set so as not to deform inside the original shape. By setting the constraint conditions in this way, a sphere or 0
5A in which the constricted portion of the original object 30-0 shown in FIG.
An object 30-1 shown in FIG. 5B and an object 30-2 having a further expanded shape shown in FIG. 5C can be obtained. It should be further noted that the corners of the original object shown in FIG.
3-0... Are the corners 31-1, 32-1, 33-1... Of the deformed object shown in FIG. 5B, and the corners 31- of the deformed object shown in FIG. 2, 32-2,
33-2...

FIGS. 9 (A) to 9 (E) show that the constraint condition is set so as not to be deformed inside the shape of the original object, and the value of the applied pressure p is changed (the surface tension σ is kept constant). ) The shape of the object before and after the deformation when the object is deformed.

Numeral 40 denotes the shape of the object before deformation, and g denotes a resultant force of forces acting on each part by the pressure p and the surface tension σ. If the value of the pressure p is changed while the surface tension σ is kept constant, the shape of the deformed object becomes like 41, 42, 43, 44, and 45 as the pressure p increases. Reference numeral 42 denotes a case where the pressure p is set to 0;
Is the case where the pressure p is negative (the pressure that pushes the object from the outside to the inside), and after 43, the pressure increases in the positive direction (the direction that pushes the object from the inside to the outside).

As shown in FIG. 9A, when a negative pressure p is applied, an inward force acts as a resultant force of the pressure p and the surface tension σ as shown at 40-1. , The deformed 41 remains in its original shape.

As shown in FIG. 9 (B), when 0 is applied as the pressure p, the resultant force g of the pressure p and the surface tension σ as shown in 40-2 is applied. , And is deformed only in the direction of the outward force, resulting in 42.

FIGS. 9C and 9D show deformations when the pressure p is slightly higher than in FIG. 9B and the object has a pulling force g outward.
(E) shows a deformation in a state where the pressure is higher than that of (C) and (D), and a pulling force g acts on all of the objects, and the object expands to infinity without reaching an equilibrium state. Will be.

As described above, in the deformation according to the method of the present invention, an effective deformation can be performed by setting appropriate surface tension σ, pressure p, and constraint conditions. Coexistence of a shape and a smooth shape is also possible.

By providing such a constraint, the convex portion of the object can be left in its original shape and the concave portion can be deformed into a smooth shape.

For example, a constraint condition is set so that the object 60 is not deformed inside the original shape.
Surface tension σ (the resultant of surface tension at each point is α) on the surface of object 60 having a cross section as shown in FIG.
When the pressure p is applied, it can be deformed as shown in FIG.

That is, since the object cannot be deformed inward, only the portion where the resultant g of the surface tension and the pressure is directed outward is deformed. Therefore, the convex portion 62 (A, H,
G, F, E, and D), when the surface tension σ and the pressure p are applied within a range in which the resultant force g acting on the outside does not act on the outside, the vicinity of the corners of B and C of the concave portion 64 is reduced by the surface tension σ and the pressure p. The resultant force g acts outward. Therefore, as shown in FIG.
2 retains the original shape, and the concave portion 64 is deformed into a smooth shape.

Further, by making the constraint condition deformable only inside the object, a deformation in which the corner of the object is rounded can be performed as shown in FIG.

That is, since the object can be deformed only inward, only the portion where the resultant g of the surface tension σ and the pressure p is directed inward is deformed. Therefore, when a surface tension σ and a pressure p are applied such that the resultant force is on the inside at the vertices and ridge lines of the cube, which is the object shown in FIG. ), The corners of the cube may be rounded.

When there is a closed object, the invisible part is usually called the inside if it is in the real world. Therefore, not deforming inside means literally not deforming inside and outside of the real world.

However, in the case of an object composed of polygons, for example, inside and outside of a polygon can be designated. In this case, inside and outside can be designated irrespective of actual inside and outside. Thus, the visible portion of a closed object, which is actually outside, can be designated as inside. In such a case,
[Inside] is opposite to the inside of the real world.

For example, when the cubic object shown in FIG. 6A is made up of polygons, the surface facing the outside of the cube is designated as the inside of the polygon, so that it can be deformed only outside the object. Under the constraint condition described above, the same result of FIG.

As described above, by setting the constraint condition so that the object is not deformed inside the original shape, or by setting the constraint condition so that it can be deformed only inside the original shape, the shape of the object before deformation can be obtained. You can get objects that are constrained in some way.

As described above, according to the method of the present invention, various shapes can be obtained by applying the surface tension σ and the pressure p to the object and deforming the object in accordance with an appropriate constraint condition.
The concept of the method of the present invention has been described above. Hereinafter, specific modes of use of the method of the present invention and calculation methods for realizing the method of the present invention will be described.

FIG. 11 is a flowchart showing a procedure for performing modeling using the method of the present invention in CG.

First, the artist prepares an object to be transformed (step 10), and designates a surface tension σ and a pressure p acting on the object as parameters (step 20).

Here, the object to be transformed may be one obtained by combining a plurality of objects. For example, as described above, an effective effect can be obtained by combining a plurality of separately created objects with a boolean or the like and performing deformation using the method of the present invention. As this parameter, a uniform value can be specified for the entire object, or a different value can be specified for each part.

If the value of pressure p / surface tension σ is the same (surface tension ≠ 0), the result is equal, so the ratio may be used, or one of the values may be fixed and the other may be used. It may be specified.

Then, a constraint condition for restricting the deformation of the object is designated (step 30). If the constraint condition is uniquely determined in advance, the artist need not be specified.

Thereafter, a deformation operation is performed on the target object based on the designated parameters and constraint conditions (step 40). The artist visually checks the object after the calculation is completed (step 50),
If OK, the data of the object is obtained.

If the shape is not the desired shape, a new parameter or constraint condition is set again, and the deformation according to the method of the present invention is performed again. The artist obtains data of a desired shape by trial and error in this way.

Next, a specific calculation method and algorithm for realizing the method of the present invention will be described. Since a specific realization method differs depending on how the target object is defined or configured, in the present embodiment, a method of the present invention targeting an object configured by a polygon will be described.

In deforming an object,
As described above, a model that always keeps the surface tension σ and the pressure p constant regardless of changes in the surface area and volume of the three-dimensional shape due to deformation is used.

It is assumed that the artist designates the ratio of the pressure p to the surface tension σ as a parameter defining the deformation.

Further, there is a method for calculating an equilibrium state between the surface tension σ and the pressure p to be applied, a method for calculating a balance between forces, and a method in which an object has potential energy based on the surface tension σ and the pressure p. Then, there is a method of calculating as the energy minimization problem. First, the calculation method and algorithm in the former case will be described.

1. Embodiment of First Deformation Calculation Since the object handled in this embodiment is made up of polygons, substantial deformation is performed by moving the coordinates of the vertices of the polygons. That is, the resultant force of the surface tension σ and the pressure p acting on each vertex is obtained, and each vertex is moved in the direction of the resultant force. Then, as a result of the movement, a loop process for repeating the above process is performed until the resultant vectors at all the vertices are 0 (or a sufficiently small value) or until the resultant does not move due to the constraint by the constraint condition.

First, a vector acting on a vertex is obtained by the following method.

[0092] As shown on the front surface tension force diagram 13 (A), for one polygon around the vertex, the unit on the edge (edge line of the polygon) vector U _0, make U _1, the U _0, U ₁ The angle formed is θ. In the present embodiment, the surface tension σ is fixed at 1.

As shown in FIG. 13B, utilizing the fact that the resultant force of the force perpendicular to the arc is equal to the resultant force of the force perpendicular to the chord, a fan having a radius of 1 Make a mold and find the force acting on the arc. N around the vertex
In the case where there are polygons, if the force vector acting on the arc portion of the i-th polygon is Fi, the following expression is obtained.

(Equation 1) Then, the force vector represented by the equation 1 is converted to n around the vertex.
The resultant vectors are obtained and summed to obtain the resultant force vector Ft.

That is, θ of the i-th polygon is θi
Assuming that (i = 0 to n−1), the corners around the vertices are summed up and expressed by Expression 2.

[0095]

(Equation 2) If Equation 2 is small, the force acting on the vertex becomes unnecessarily small. To correct this, when calculating the resultant vector Ft, multiply by Equation 3 expressed by the following equation.

[0096]

(Equation 3) In order to obtain a resultant force vector Ft in order to further increase the size in proportion to the object size, the following equation (4) is obtained.
Multiply.

[0097]

(Equation 4) However, the area of the i-th polygon is Ai.

As described above, the resultant vector Ft of the force acting on the apex due to the surface tension is expressed by the following equation (5).

[0099]

(Equation 5) Pressure Let p be the pressure acting inside the object. This p
Is a value specified as a parameter by the artist. The area of the i-th polygon among the n polygons around the vertex is Ai, the normal vector is Ni, and the number of vertices is ai. (| Ni | = 1) A force vector acting on the i-th polygon is represented by Expression 6.

[0100]

(Equation 6) Then, it is considered that this force vector is evenly distributed to the vertices belonging to the polygon. The resultant force vector acting on the vertex is the resultant vector of the above vectors obtained for the surrounding polygons. Therefore, the force vector Fp acting on the vertex due to the pressure is expressed by Expression 7.

[0101]

(Equation 7) In this example, since the force acting on the object is determined only by the surface tension σ and the pressure p, the force vector F acting on the vertex is expressed by the following equation (8), which is the sum of the force vector Ft due to the surface tension and the force vector Fp due to the pressure. expressed.

[0102]

(Equation 8) At each vertex, a force acting to move in the direction of each resultant force vector F acts. When this force is 0, the vertex has reached an equilibrium state, and a constraint condition is set that no deformation occurs inside this time. Therefore, when the force is inward, the vertex is moved. Absent.

Therefore, only when the force is directed outside the object, the vertex is moved in the direction of the resultant force vector.

The moving amount is obtained by the following method. FIG. 14 is a diagram illustrating the principle of linear extrapolation used in the processing of vertex movement.
The horizontal axis represents the movement amount of the vertex, and the vertical axis represents the magnitude of the resultant vector. The vertex is moved by a very small amount δ in the direction of the resultant force vector F, and the resultant resultant force vector F ′ is obtained. And
As shown in FIG. 14, when the relationship between the resultant vector and the movement of the vertex is approximated to change linearly, the relationship between the resultant vector and the movement of the vertex is represented by a straight line 200, and the inclination is represented by Expression 9.

[0105]

(Equation 9) Then, based on the relationship 200, a movement amount γ at which the resultant vector after the vertex movement becomes 0 is obtained.

Actually, the relationship between the resultant vector and the vertex movement does not always change linearly. Therefore, even if the resultant vector F 'is obtained by moving by γ, it does not become zero. Therefore, the resultant vector is converged to 0 by repeating such processing in a loop.

An algorithm for obtaining the transformed vertex coordinates by using such a loop process will be described below.

FIG. 12 is a PAD diagram showing an algorithm of a deformation operation according to the method of the present invention when a constraint condition that no deformation is performed inside the original object is set. In the transformation operation of the method of the present invention, a loop process of moving the vertices is performed for all vertices according to the present algorithm, and the transformation ends when the movement of all vertices is completed.

In FIG. 12, N is the number of vertices, k is a vertex counter for determining whether or not all vertices of the object have been processed, and 1 is for determining whether or not the convergence state has been reached. Is a counter of vertices whose vertex movement has not been performed.

This processing includes a process for setting the vertex coordinates of each vertex of the object before deformation (step 100) and a process for performing the deformation until the convergence state is reached (loop 110).

In the process of performing deformation until the convergence state is reached (loop 110), the following process is performed until 1 = N. First, processing for initializing the variables k and l (step 1)
20) is performed to calculate the area of each polygon required for calculating the resultant vector at the vertex (step 130). The processing of steps 120 and 130 is performed for the first time or when new vertex coordinates are set after the vertex movement has completed one cycle.

Then, a loop process (loop 140) for making a round of the movement of the vertices constituting the object is performed. In this loop processing, until the vertex movement makes one round (k =
1 to N) The following processing is performed.

[0113] First, calculates the resultant force vector at each vertex V _k (step 160). This calculation is performed by obtaining the resultant vector of the surface tension and the pressure as described above. That is, as a resultant vector of surface tension,
Equation 7 is obtained as the resultant vector of pressure, and Equation 8 is obtained as the resultant vector of both.

When the resultant vector is 0, the vertices do not move because the forces are balanced at the vertices.
Further, in the present embodiment, since the constraint condition is provided that no deformation occurs inside, the vertex does not move even when the resultant vector is inward.

Therefore, it is determined whether the resultant vector is 0 or inward (step 170). If yes, the counter 1 for the vertex whose vertex has not been moved is counted up (step 180). ). performs moving operation of the vertex V _k of interest when no, resetting the vertex coordinates (step 190). In this vertex movement calculation, the movement direction of the vertex is the direction of the resultant force vector, and the movement amount γ is obtained by the above-described linear extrapolation calculation process.

[0116] 2. Embodiment of Second Deformation Calculation Next, a method of calculating the energy minimization problem in consideration of the potential energy due to the surface tension σ and the pressure p will be described.

In order to make the deformation converge at high speed, it is effective to control not by local balance but by grasping the state of the entire object. Thus, potential energy due to surface tension σ and pressure p is considered. The stable state in which the surface tension σ and the pressure p are balanced corresponds to the minimum state of the potential energy. Therefore, instead of obtaining the deformation of the object as a state of balance between the force of the surface tension σ and the force of the pressure p, the deformation of the object can be obtained as the shape of the minimum state of the energy E.

The specific calculation method will be described below. First, the potential energy of the object is defined by the surface tension σ and the pressure p.

Definition of Potential Energy Based on Surface Tension Since the surface tension σ is a force for reducing the area, the potential energy monotonically increases as the area increases. This is called surface energy and is represented by Es.

Definition of Potential Energy Based on Pressure The state in which the pressure p is acting inside the object can be modeled as shown in FIG. Therefore, assuming that the volume of the object is V ₀ , the potential energy Ev due to the pressure p is expressed by the following equation.

Ev = −pV ₀ This energy will be referred to as volume energy.

In this way, the total potential energy E of the object is represented by E = Es + Ev.

Next, details of Es and Ev will be described.

Surface Energy Model The surface energy Es is determined as follows. The object handled in this embodiment is composed of polygons,
Hereinafter, a case where the shape of the polygon is a triangle will be described.

The surface energy Es is the sum of the surface energies S of the polygons constituting the object.

[0126]

(Equation 10) As shown in FIG. 15, the area of the polygon is A, the edge length l
Let L be the sum of squares of ₀ , l ₁ and l ₂ .

[0127]

[Equation 11] Also, S has the following properties.

A. S is proportional to the area A.

B. S is smaller as the shape of the polygon is closer to a regular triangle.

The following equation 12 is used as a parameter indicating how close the polygon shape is to a regular triangle.

[0131]

(Equation 12) Equation 13 is used as an equation that satisfies the properties of a and b.

[0132]

(Equation 13) The coordinates of the three vertices of the polygon are (x ₀ , y ₀ , z ₀ ),
When (x ₁ , y ₁ , z ₁ ) and (x ₂ , y ₂ , z ₂ ) are used to express S in Expression 13, the following equation is obtained.

[0133]

[Equation 14] The volume energy Ev of the volume energy model object is expressed as Ev = −pV ₀ as described above. Assuming that the volume of a tetrahedron composed of the coordinate origin (0, 0, 0) and one polygon (triangle) is V, the volume of the entire object is

(Equation 15) Becomes However, when the origin is on the front side with respect to the polygon, V takes a negative value. The coordinates of the vertices of the polygon are P ₀ (x ₀ , y ₀ , z ₀ ), P ₁ (x ₁ , y ₁ , z ₁ ), P ₂
(X ₂ , y ₂ , z ₂ ), the origin is the starting point, and P ₀ , P 2
_1, each vector whose end point _{P 2 P 0, P 1,} P 2
And V is represented by the following equation.

[0134]

(Equation 16) How to Solve Energy Equations If the number of vertices is M, each vertex has x, y, and z coordinate values as variables, so the total energy E of the object is represented as a function of 3M variables.

Assuming that N = 3M, p ₀ = V _x0 and p ₁ = V _{y0 for} the x, y, and z coordinates V _xj , V _yj , and V _{zj of} each vertex V _j (j = 0 to M−1). , P ₂ = V _z0 , ... p _3j = V _xj , p _{3j + 1} = V _yj , p _{3j + 2} = V _zj , ... p _N-3 = V _{x (M-1)} , p _N-2 = V _{y (M-1)} , p _N-1 = V _{z (M-1)}
..., N variables can be represented as p _i (i = 0 to N−1), and the energy E can be represented in the following form.

E = f (p ₀ , p ₁ ,..., P _N- 1) In order to obtain pi (i = _{0 to N−1} ) at which the value of E is minimal,

[Equation 17] Will be solved. The expression 17 means the following simultaneous equations.

[0137]

(Equation 18) Each equation becomes a non-linear equation by the energy model described above. Therefore, the problem is reduced to solving the simultaneous nonlinear equations of Expression 18.

Solution of the simultaneous nonlinear equations The simultaneous nonlinear equations (Equation 18) will be solved using the Newton method. At this time, calculation is performed by the following method.

Procedure 1. An initial value is given to pi (i = 0 to N−1). The vertex coordinates of the input object are used as the initial values.

Procedure 2. First and second order partial derivatives E of E
Find i and Eij.

[0141]

[Equation 19]

(Equation 20) Procedure 3. The value of Δpi (i = 0 to N−1) is obtained by solving the following equation.

[0142]

(Equation 21) Step 4. The pi in Equation 21 is replaced with pi + Δpi.

Procedure 5. Steps 2 to 4 are repeated until the value of | Δpi | becomes sufficiently small.

In the procedure 2, the first and second order partial derivatives of E are obtained from E = Es + Ev.

(Equation 22)

(Equation 23) Note that Es and Ev use those defined above.

Constraint Conditions Although the solution of the simultaneous nonlinear equations described above does not consider the constraint conditions, the method of the present invention sets the constraint conditions when moving the vertices and deforming the object. By doing so, effective deformation can be performed. Therefore, a case will be described below as an example in which a constraint condition is set that deformation is not performed inside the original shape.

In order to deform the object under the above constraint conditions, it is necessary to detect a vertex which is going to move inside the object and to correct the equation 21 so that the vertex is fixed.

Procedure 1. First, a vertex to be fixed is detected. Is the value on the right side of Equation 21

(Equation 24) Means a gradient vector in the downward direction of the potential energy. Therefore, the coordinate values of the vertices are represented by (p _i , p _j ,
p _k ), the following vector

(Equation 25) Find out which direction is inside or outside the object, and decide whether to fix or not fix the vertex. Here, since a constraint condition is set that no deformation occurs inside the original shape, the vertex is fixed when the direction of the vector represented by Expression 25 is inward. In addition, since each polygon constituting the object is set to the front and back, the vector is outward if the vector is facing the front of each polygon around the vertex, and inward if the vector is facing the back. Is determined.

Procedure 2. The above determination is made for all the vertices constituting the object, and when the vertices to be fixed are determined, the equation 21 is modified to fix the vertices. Here, a method of correcting the number 21 will be described by taking as an example a case where the vertices (p _x , p _y , p _z ) are fixed.

This correction is performed, for example, as follows. Of the simultaneous equations constituting Equation 21, three equations are

(Equation 26) Replaced, Delta] p _x from the remaining N-3 amino of formula, Δp _y, Δp
Remove the term in _z .

That is, the following correction is made on the right side of Expression 21.

E _x = E _y = E _z = 0 Further, the following modification is made to the matrix on the left side.

E _xx = E _yy = E _zz = 1 E _yz = E _zx = E _xy = E _zy = E _xz = E _yx = 0 E _xi = E _yi = E _zi = E _ix = E _iy = E _iz = 0 (i = 0 to N−1, i ≠ x, y, z) FIG. 16 illustrates this equation.

Since it is difficult to determine the constraint conditions in the final shape of the object at the initial stage, the constraint conditions must be reset by the above-described procedures 1 and 2 for each step of the Newton method. Do.

An algorithm for obtaining the vertex coordinates after deformation using the Newton's method will be described below.

FIG. 17 is a PAD diagram showing an algorithm of a deformation operation according to the method of the present invention when a constraint condition that no deformation is performed inside the original object is set. In the modified operation of the method of the present invention, all vertices V _k (k
= 1 to M) is fixed by the constraint conditions and cannot be moved, or the value of | Δpi | for pi (i = 1 to N, N = 3M) corresponding to all the x, y, and z coordinates constituting the vertex Until is sufficiently small, the loop processing of the movement of the vertices is performed according to the present algorithm, and the transformation ends when the movement of all the vertices is completed.

In FIG. 17, M is the number of vertices, and N is the total number of variables x, y, z representing the coordinates of the vertices. Also,
k is a counter of vertices for checking the moving direction for all vertices of the object, and 1 is a counter of vertices that could not move due to the constraint. I is pi (i = i = x) corresponding to the x, y, z coordinates of all vertices.
0 to N-1, N = 3M), and j is p
This counter counts the number of pi such that the movement amount | Δpi | of i is sufficiently small.

In this process, the process of setting the vertex coordinates of each vertex of the object before deformation (step 200)
The loop processing (loop 210) is performed until all | Δpi | values become sufficiently small (until j = N).

The loop processing (loop 210) is a processing for initializing the variables j and l (steps 220 and 225).
And a process of detecting fixed vertices from all the vertices constituting the object (loop 230), a process of determining whether all vertices are fixed (step 240), and setting constraints to each of them by Newton's method. The process includes a process of obtaining the moving amount of the vertex (step 250), and a process of determining whether or not each pi has converged as a result of the calculation and moving each vertex (loop 270).

From all vertices constituting the object,
In the process of detecting a fixed vertex (loop 230),
The following processing is performed on all vertices. First, in order to check the moving direction of each vertex V _k, the direction of the above-described equation 25 is checked (step 290). When the direction of the vector is inward (step 300), the vertex is fixed by the constraint condition, and 1 is counted up (step 31).
0).

When the vertices to be fixed have been determined for all the vertices constituting the object after the above-described processing, it is determined whether or not all the vertices are fixed (step 240). If the fixed number of vertices is equal to the total number of vertices of the object, the transformation ends (step 320).

In the process of setting the constraint conditions and calculating the movement amount of each vertex by the Newton method (step 250), the movement amount of the vertex is calculated by the Newton method based on the constraint condition of the vertex to be fixed. Specifically, the equation shown in FIG. 16 is solved to determine the value of Δpi.

Processing for moving each vertex (loop 270)
Then, the following processing is performed until i reaches the total number of x, y, and z of all vertices.

First, it is determined whether the value of | Δpi | is sufficiently small (step 330), and if it is sufficiently small, j is counted up (step 350). Next, pi is updated to pi + Δpi (step 360).

The present invention is not limited to those described in the above embodiments, and various modifications can be made.

Regarding the surface tension and the pressure applied to the deformation model of the object, the surface tension σ and the pressure p are kept constant irrespective of the change of the surface area and the volume of the object due to the deformation as in the above embodiment. Or a model in which one or both of them may change.

As the parameter to be specified, a uniform value can be specified for the entire object, or a different value can be specified for each part. Also, if the value of pressure p / surface tension σ is the same (surface tension ≠
0), since the results are equal, a ratio value may be used, or one of the values may be fixed and the other value may be designated.

Regarding the setting method of the constraint condition, a uniform condition can be designated for the entire object, or a different condition can be designated for each part. Further, the setting contents of the constraint condition are not limited to those described in the present embodiment.

Further, in the above-described modification calculation example, an object composed of polygons has been described as an example, but it is also possible to use objects other than polygon objects. For example, by using a free-form surface instead of a polygon, it is also possible to apply to an object constituted by a curved surface.

According to the method of the present invention, a program for realizing the three-dimensional shape deformation method of the present invention may be stored in an information storage medium of development hardware and used as a modeling tool, or may be used as a modeling tool. The information storage medium is stored together with data such as constraint conditions and shape data,
It may be used for real-time image synthesis.

The arithmetic processing when applying the three-dimensional shape deformation method of the present invention to image synthesis may be performed using a dedicated processing device, or may be performed using a general-purpose microcomputer,
The processing may be performed by software using a DSP or the like.

Further, by storing the program code of the program in a storage medium such as a CD or a floppy disk, the three-dimensional shape deformation method of the present invention can be easily implemented in a given computer system.

The information of the three-dimensional shape deformed by the method of the present invention or the image information generated based on the three-dimensional shape is transferred to an information storage medium of an image synthesizing apparatus, or a film such as a movie, a video, a photograph, or the like. Images stored in a storage medium such as a tape, a video disk, a CD, and a floppy disk can be easily generated by a given image generation device based on the three-dimensional shape deformation method of the present invention.

Further, the present invention described above can be implemented using any hardware regardless of whether it is for home use or business use. FIG. 18 is a diagram illustrating an example of a hardware configuration of an image synthesizing apparatus of a type widely used at present. The image synthesizing apparatus shown in FIG.
2, RAM 1004, information storage medium 1006, voice synthesis IC 1008, image synthesis IC 1010, I / O port 1
012 and 1014 are connected to each other via a system bus 1016 so that data can be transmitted and received therebetween. A display 1018 is connected to the image synthesis IC 1010,
A speaker 1020 is connected to the voice synthesis IC 1008, and a control device 10 is connected to the I / O port 1012.
22 is connected, and the communication device 1 is connected to the I / O port 1014.
024 is connected.

The information storage medium 1006 is a CD-RO
M, a game ROM, a memory means such as a memory card, which means a storage means detachably provided to the main body of the image synthesizing apparatus, and a type capable of writing and storing predetermined information according to the contents of image synthesis is also used. The ROM 1002 is a storage unit fixedly provided in the main body of the image synthesizing apparatus.

The control device 1022 is a device for an operator to input to the image synthesizing device main body.

The information storage medium 1006 and the RO
In accordance with various programs and system programs stored in M1002 or signals input by the control device 1022, the CPU 1000 controls the entire image synthesizing apparatus and performs various data processing. RAM1
Reference numeral 004 denotes storage means used as a work area of the CPU 1000, and the information storage medium 1006 and the R
The predetermined contents of the OM 1002 or the calculation results of the CPU 1000 are stored.

Further, this type of image synthesizing apparatus is provided with a voice synthesizing IC 1008 and an image synthesizing IC 1010 so that a suitable output of voice and image can be performed. The voice synthesis IC 1008 is an information storage medium 1006
And a circuit that synthesizes sound effects, music, and the like based on information stored in the ROM 1002, and the synthesized music and the like are output by the speaker 1020. The image synthesizing IC 1010 is a circuit that synthesizes pixel information to be output to the display 1018 based on image information sent from the RAM 1004, the ROM 1002, the information storage medium 1006, and the like.

The communication device 1024 exchanges various kinds of information used inside the image synthesizing device with the outside, and is also used for transmitting and receiving information such as a program via a communication line.

The three-dimensional shape deformation method of the present invention can be easily implemented using the general image synthesizing apparatus described above. For example, by storing in advance a program for realizing the three-dimensional shape deformation method of the present invention in the storage medium 1006 or the like, the CPU 1000 can store the program in the RAM 1004.
By using such a method, it can be configured to function as a means for deforming the three-dimensional shape.

The means for generating an image having a three-dimensional shape after deformation is provided by the image synthesizing IC 1010 or
This is realized by the PU 1000 and predetermined software.

Further, image information or the like generated by the three-dimensional shape deformation method of the present invention (3D shape deformed by the method of the present invention)
The information of the three-dimensional shape or the image information generated based on the three-dimensional shape) is stored in the storage medium 1 of the general image synthesizing apparatus.
By storing the data in 006 in advance as image synthesis data, it is also possible to configure so as to perform image synthesis using the image synthesis data at the time of image synthesis.

Further, the method of the present invention can be used for deforming various three-dimensional shapes other than image synthesis.
For example, there is a case where a three-dimensional shape is actually made using a resin.

[0183]

[Brief description of the drawings]

FIGS. 1A to 1C are diagrams showing deformation of an object.

FIG. 2 is an explanatory diagram of a definition based on a metaball concentration distribution.

FIG. 3 is an explanatory diagram of deformation by a metaball.

FIGS. 4 (A) to 4 (H) are explanatory diagrams of deformation by a metaball.

FIGS. 5A to 5C are diagrams showing deformation of an object.

FIGS. 6A and 6B are diagrams showing deformation of an object. FIGS.

FIGS. 7A and 7B are diagrams for explaining surface tension. FIG.

FIGS. 8A and 8B are diagrams for explaining a pressure applied, a surface tension, a pressure, and a relationship between the pressure and the surface tension.

FIGS. 9A to 9E are diagrams for explaining the relationship between deformation of an object and a constraint condition.

FIGS. 10A and 10B are diagrams for explaining a relationship between deformation of an object and a constraint condition.

FIG. 11 is a flowchart illustrating a procedure when modeling is performed using the method of the present invention.

FIG. 12 is a PAD diagram showing an algorithm of a first modification operation of the method of the present invention.

FIGS. 13A and 13B are diagrams for explaining calculation of a resultant force of surface tension acting on a vertex.

FIG. 14 is a diagram for explaining the principle of primary extrapolation.

FIG. 15 is a diagram for explaining a surface energy model.

FIG. 16 is an explanatory diagram of an equation when performing an operation by the Newton method with a vertex fixed.

FIG. 17 is a PAD diagram showing an algorithm of a second modification operation of the method of the present invention.

FIG. 18 is a diagram illustrating an example of a hardware configuration of a game device.

[Explanation of symbols]

 p pressure σ surface tension

Claims (8)

(57) [Claims] 1. A method for deforming a three-dimensional shape, comprising: a deformation condition setting step of setting surface tension and pressure acting on a surface of the three-dimensional shape as deformation conditions; A constraint condition setting step for setting a constraint condition for deforming the three-dimensional shape; a deformation condition set in the deformation condition setting step; A deformation calculation step of deforming the shape. 2. The three-dimensional shape deformation method according to claim 1, wherein in the deformation condition setting step, the same deformation condition is set for the entire three-dimensional shape. 3. The three-dimensional shape deformation method according to claim 1, wherein in the deformation condition setting step, different deformation conditions are set for each part of the three-dimensional shape. 4. The three-dimensional shape according to claim 1, wherein in the constraint condition setting step, a constraint condition is set so as not to be deformed inside or outside of the three-dimensional shape before deformation. Deformation method. 5. The deformation calculation step according to claim 1, wherein the surface tension and the pressure set in the deformation condition setting step are applied to the three-dimensional shape, and thereby the surface tension acting on the three-dimensional shape is reduced. A three-dimensional shape deformation method, comprising: calculating a balance of a force of a pressure; and performing a deformation calculation until the surface tension and the pressure are balanced within a range of a constraint condition. 6. The method according to claim 1, wherein in the deformation calculating step, the surface tension and the pressure set in the deformation condition setting step are applied to the three-dimensional shape to thereby reduce the surface tension acting on the three-dimensional shape. A three-dimensional shape deformation method, comprising calculating a potential energy of a potential energy and a potential energy of a pressure, and performing a deformation calculation until a sum of the two potential energies is minimized within a range of a constraint condition. 7. An information storage medium for storing a program code for deforming a three-dimensional shape, wherein the program code for implementing the method for deforming a three-dimensional shape according to claim 1 is stored. An information storage medium characterized by the following. 8. A method for generating image information, comprising : executing the three-dimensional shape deformation method according to claim 1.
Deforming the three-dimensional shape by using the method, and generating image information based on the deformed three-dimensional shape.
And generating the image information.