JP3377488B2 - GAME SYSTEM AND INFORMATION STORAGE MEDIUM - Google Patents

Description

Detailed Description of the Invention

[0001]

TECHNICAL FIELD The present invention relates to a game system and an information storage medium.

[0002]

2. Description of the Related Art Conventionally, a game system for generating an image viewed from a given viewpoint in an object space, which is a virtual three-dimensional space, is known, and a so-called virtual reality is experienced. It is very popular as something you can do. Taking a game system that can enjoy a racing game as an example, a player operates a racing car (object) to run in the object space and competes with another player or a racing car operated by a computer. Enjoy the dimensional game.

In such a game system, an object representing a racing car or the like is composed of a combination of many polygons.

However, the method of constructing an object with polygons has a problem that the surface of the object cannot be expressed smoothly.

In this case, for example, if the number of polygons of the object is increased, the surface of the object can be expressed to some extent smoothly. However, when the number of polygons increases, the burden of arithmetic processing increases and it becomes impossible to realize the real-time processing of completing all the image generation processing within one frame.

On the other hand, CAD / CAM (Computer Aided D
In the field of esign and computer aided manufacturing, free curved surfaces (free curved lines) such as NURBS (Non Uniform Rational B-Spline) are widely used.

According to this NURBS, a smooth surface of an object can be expressed with a small number of control points.

However, NURBS has a drawback that the load of arithmetic processing is very heavy. Therefore, NURB
Although S is widely used in fields where real-time processing is not required, such as CAD / CAM, it is the current situation that it has not been put to practical use in game systems that require real-time processing.

The present invention has been made in view of the above problems, and an object thereof is to provide a game system and an image of an object represented by a free-form surface or a free-form curve with a small processing load. It is to provide an information storage medium.

[0010]

In order to solve the above-mentioned problems, the present invention is a game system for generating images, in which the shape is specified based on knot vectors and control points whose knot intervals are not constant. A means for preparing a coefficient set of a non-uniform free-form surface or free-form curve blending function in the process before the step of sequentially obtaining each point on the free-form surface or free curve while changing the parameters, and the prepared coefficient It is characterized by including means for sequentially obtaining each point on the free-form surface or free-form curve while changing the parameter based on the set and the control point. An information storage medium according to the present invention is an information storage medium that can be used by a computer and includes a program for executing the above means. A program according to the present invention is a program that can be used by a computer (including a program embodied in a carrier wave) and includes a processing routine for executing the above means.

According to the present invention, a non-uniform free-form surface or free-form curve blending function coefficient set is prepared in the preceding step of the processing for obtaining each point on the free-form surface or free curve. Therefore, the process for obtaining the coefficient set can be omitted from the process (loop) for sequentially obtaining each point on the free-form surface or the free-form curve. As a result, real-time generation of an image of an object represented by a free-form surface or free-form curve becomes possible.

Further, the game system, the information storage medium and the program according to the present invention are polynomials obtained by expanding recurrence formulas of recursive expressions in the process before the process of sequentially obtaining each point on the free-form surface or the free-form curve. The feature is that the coefficient set is prepared by calculating the coefficient set of the mixing function represented based on the knot vector.

As described above, when the coefficient set of the mixing function represented by the polynomial obtained by expanding the recurrence formula is calculated based on the knot vector, as compared with the case where the recurrence formula is recursively solved, The coefficient set of the blending function can be obtained at higher speed.

Further, the game system, the information storage medium and the program according to the present invention read the coefficient set of the blending function from the information storage medium in the process before the process of sequentially obtaining each point on the free-form surface or the free-form curve. Alternatively, it is characterized in that the coefficient set is prepared by reading through the network.

By doing so, the processing for calculating the coefficient set becomes unnecessary and the processing load can be reduced.

Further, the game system, the information storage medium and the program according to the present invention are means for obtaining a normal vector of a free curved surface or a free curve based on a prepared coefficient set (or a program for executing the means or Processing routine).

By doing so, it becomes possible to realize shading processing, hit check processing and the like by using the obtained normal vector.

Further, the game system, the information storage medium and the program according to the present invention have a normal obtained based on the coefficient set of the blending function in the process before the process of sequentially obtaining each point on the free-form surface or the free-form curve. A coefficient set for calculation is prepared, and a normal vector of a free-form surface or free-form curve is obtained based on the prepared coefficient set for calculation of the normal line.

With this configuration, the process of obtaining the coefficient set for calculating the normal can be omitted from the process of sequentially obtaining each point on the free-form surface or free-form curve, so that the processing speed can be increased.

Further, the game system, the information storage medium and the program according to the present invention include means (or a program or a processing routine for executing the means) for performing affine transformation on the free curved surface or the control point of the free curve in frame units. A game system characterized in that a coefficient set of a blending function is prepared in a process in a pre-stage of affine transformation performed in frame units.

In this way, the processing for obtaining the coefficient set of the mixing function can be omitted from the processing (loop) performed in frame units, so that the processing in frame units can be speeded up and real-time processing can be achieved. Can meet the request of.

Further, the game system, the information storage medium and the program according to the present invention include a coefficient set of a mixing function in a process before the process of sequentially obtaining each point on a free curved surface or a free curve while changing parameters. Object data including control points are prepared, and in the process of sequentially obtaining each point on the free-form surface or free-curve while changing the parameter, a coefficient corresponding to the domain to which the value of the parameter belongs from the object data. It is characterized in that sets and control points are read out.

By doing so, it becomes possible to read out the appropriate coefficient set and control point according to the parameter value at that time from the object data.

Note that once the coefficient set and control points have been read from the object data, the coefficient sets and control points must be read again unless the domain to which the parameter value belongs changes to the next domain. Not the same coefficient set,
It is desirable to continue to use control points.

It is further desirable that the object data include a knot vector for specifying the parameter domain, in addition to the coefficient set and the control point.

[0026]

BEST MODE FOR CARRYING OUT THE INVENTION Preferred embodiments of the present invention will be described below with reference to the drawings.

1. Configuration FIG. 1 shows an example of a block diagram of a game system (image generation system) of the present embodiment. In the figure, in the present embodiment, at least the processing unit 100 may be included (or the processing unit 100 and the storage unit 170, or the processing unit 100, the storage unit 170, and the information storage medium 180 may be included), and other blocks. (For example, the operation unit 160 and the display unit 19
0, the sound output unit 192, the portable information storage device 194, and the communication unit 196) can be arbitrary constituent elements.

Here, the processing section 100 performs various processing such as control of the entire system, instruction of commands to each block in the system, game processing, image processing, or sound processing, and the function thereof is Various processors (CPU, DSP
Etc.) or hardware such as ASIC (gate array etc.) or a given program (game program).

The operation section 160 is for the player to input operation data, and its function can be realized by hardware such as a lever, a button, and a housing.

The storage unit 170 includes the processing unit 100 and the communication unit 1.
A work area such as 96, whose function is RAM
It can be realized by hardware such as.

An information storage medium (a storage medium usable by a computer) 180 stores information such as programs and data, and its function is that of an optical disc (C
D, DVD), magneto-optical disk (MO), magnetic disk, hard disk, magnetic tape, or memory (RO
It can be realized by hardware such as M). Processing unit 10
0 performs various processes of the present invention (this embodiment) based on the information stored in the information storage medium 180. That is, the information storage medium 180 stores information (program or data) for executing the means of the present invention (the present embodiment) (particularly the block included in the processing unit 100).

A part or all of the information stored in the information storage medium 180 is transferred to the storage unit 170 when the system is powered on. The information storage medium 1
Information stored in 80 is a program code for performing the process of the present invention, image data, sound data, shape data of a display object, table data, list data, information for instructing the process of the present invention, and instructions thereof. The information includes at least one of the information for performing the processing according to the above.

The display unit 190 outputs the image generated by the present embodiment, and its function is CRT,
LCD or HMD (head mounted display)
It can be realized by hardware such as.

The sound output unit 192 outputs the sound generated by this embodiment, and its function can be realized by hardware such as a speaker.

The portable information storage device 194 stores personal data, save data, etc. of the player. As the portable information storage device 194, a memory card, a portable game device or the like can be considered. .

The communication unit 196 performs various controls for communicating with the outside (for example, a host device or another game system), and its function is that of various processors or communication ASICs. It can be realized by hardware or programs.

The program or data for executing the means of the present invention (this embodiment) is distributed from the information storage medium of the host device (server) to the information storage medium 180 via the network and the communication unit 196. You may Use of such an information storage medium of the host device (server) is also included in the scope of the present invention.

The processing section 100 includes a game processing section 110, an image generating section 130, and a sound generating section 150.

Here, the game processing section 110 accepts coins (price), sets various modes, advances the game, sets selection screens, and positions and rotation angles of objects (one or more primitive surfaces). (Process for obtaining (rotation angle around X, Y or Z axis), process for moving object (motion process), process for obtaining viewpoint position (position of virtual camera) and line-of-sight angle (rotation angle of virtual camera), map object Various objects such as processing for arranging objects in the object space, processing for checking hits, processing for calculating game results (results, results), processing for allowing multiple players to play in a common game space, or game over processing. The game processing is performed by the operation data from the operation unit 160 and the portable information storage device 194.
Based on personal data, stored data, game programs, etc.

The image generating section 130 includes a game processing section 110.
Various image processes are performed in accordance with an instruction from, and an image viewed from a virtual camera (viewpoint) in the object space is generated and output to the display unit 190, for example.

The sound generation unit 150 performs various kinds of sound processing according to the instruction from the game processing unit 110, BGM,
A sound such as a sound effect or a sound is generated and output to the sound output unit 192.

The game processor 110 and the image generator 1
All of the functions of the sound generation unit 150 and the sound generation unit 150 may be realized by hardware, or all of them may be realized by a program. Alternatively, it may be realized by both hardware and a program.

The image generation unit 130 includes a coefficient calculation (reading) unit 132, an affine transformation unit 134, a curved surface (curve) calculation unit 136, a normal vector calculation unit 138, and a drawing unit 140.
including.

The coefficient calculation (reading) unit 132 mixes non-uniform free-form surfaces or free-form curves (hereinafter, "free-form surface or free-form curve" is simply referred to as "free-form surface" for convenience of description). A coefficient set (for example, a coefficient matrix) of a function (basis function) is prepared in the preceding stage of the loop processing for sequentially obtaining each point of the free-form surface while changing the parameter.

More specifically, for example, in the preceding stage of the loop processing for obtaining each point on the free-form surface, the coefficient set of the blending function is calculated based on the knot vector (vector giving the node of the parameter as a sequence of numerical values). Therefore, a coefficient set is prepared.

In this case, in this embodiment, the mixing function is represented by a polynomial (a polynomial of parameters) obtained by expanding the recurrence formula of the recursive expression (for example, the recurrence formula of DeBoorCox).

The calculated coefficient set (coefficient matrix, base matrix) is temporarily stored in the object data storage unit (storage area) 173 of the main memory 172 as the free-form surface object data.

Alternatively, in the pre-stage of the loop processing for obtaining each point of the free-form surface, the coefficient set of the blending function is read from the information storage medium 180 or is read from the outside via the network (communication unit 196) to mix. A coefficient set of the matching function may be prepared. In this case as well, it is desirable that the read coefficient set is expanded on the object data storage unit 173 of the main memory 172 as free-form surface object data.

The affine transformation unit 134 is, for example, the operation unit 1.
Affine transformation is performed for each control point of the free-form surface on a frame-by-frame basis (on a frame-by-frame basis) based on operation data input from 60, a game program, and the like.

That is, in this embodiment, in order to generate an image of an object (model) represented by a free-form surface, various geometry processes (three-dimensional) such as affine transformation (coordinate transformation), clipping processing, or light source calculation are performed. Calculation) is performed. In the present embodiment, in this geometry processing, for the control points of the free-form surface, coordinate conversion from the local coordinate system to the world coordinate system, coordinate conversion from the world coordinate system to the viewpoint coordinate system, and the viewpoint coordinate system to the screen coordinate system. Various affine transformations such as coordinate transformation (perspective transformation) to
It is done in frame units.

The curved surface (curve) calculation unit 136 uses the coefficient set (including the coefficient set for normal calculation and the coefficient set for difference calculation) prepared by the coefficient calculation (reading) unit 132 and the affine transformation unit 134. Based on the affine-transformed control points (definition points), processing is performed to sequentially obtain each point on the free-form surface while changing the parameters.

In this case, based on the prepared coefficient set (coefficient set for difference calculation), a difference set (for example, a difference matrix) of a free-form surface equation with respect to the parameter difference is obtained, and the obtained difference set and control Each point of the free-form surface may be obtained based on the point.

In this case, the coefficient set for difference calculation, which is obtained based on the coefficient set of the blending function, is prepared in the process before the loop process for obtaining each point of the free-form surface, and is prepared. It is desirable to obtain the difference set of the equation of the free-form surface based on the coefficient set for difference calculation.

The normal vector calculation unit 138 performs processing for obtaining the normal vector of each point on the free-form surface based on the prepared coefficient set.

A coefficient set for normal calculation, which is obtained based on the coefficient set of the blending function, is prepared in the process before the loop processing for obtaining each point of the free-form surface, and the prepared normal is prepared. It is desirable to find the normal vector of the free-form surface based on the coefficient set for calculation.

The drawing unit 140 performs processing for drawing the object after the geometry processing in the frame buffer 174. More specifically, the free curved surface obtained by the curved surface calculation unit 136 is converted (tessellated) into a polygon and drawn. That is, polygon data in which each point on the free-form surface is set as a vertex is generated, and drawing processing is performed based on this polygon data.

However, if the drawing unit 140 has a function of drawing not only polygons but also free-form surfaces, the free-form surfaces generated by the surface calculation unit 136 may be drawn directly in the frame buffer 174.

The game system of this embodiment is
It may be a system dedicated to the single player mode in which only human players can play, or a system having not only such a single player mode but also a multiplayer mode in which a plurality of players can play.

When a plurality of players play,
The game images and game sounds to be provided to the plurality of players may be generated using one terminal, or may be generated using a plurality of terminals connected by a network (transmission line, communication line) or the like. Good.

2. Features of this embodiment 2.1 B-splines and NURBS First, the B-spline curve will be described.

A fourth-order (third-order) B-spline curve is generated from four control points. Set each control point to Q ₀ , Q ₁ , Q ₂ , Q ₃
Then, the formula P (t) of the B-spline curve is P (t) = N _0,4 (t) Q ₀ + N _1,4 (t) Q ₁ + N _2,4 (t) Q ₂ + N _3,4 (t) Q ₃ (1)

N _{0,4 to} N _3,4 in the equation (1) are called blending functions, and in the case of a B spline curve of the fourth order, the following equation is obtained.

[0063]

[Equation 1]

The mixing functions N _{0,4 to} N _3,4 are obtained based on a knot vector which is a vector giving the node of the parameter as a sequence of numerical values. If the knot interval of the knot vector (the numerical difference between adjacent elements of the knot vector) is constant, then a uniform
It is called a free-form curve (free-form surface), and when the knot interval is not constant, it is called a non-uniform free-form curve.

For example, the knot vector T of a uniform B-spline curve on the fourth floor with four control points is given by the following equation.

T = [− 3 −2 −1 0 1 2 3 4] (3) In Expression (3), the numerical difference between adjacent elements of the knot vector is always 1, and the uniform knot vector It has become.

For the number of elements of the knot vector, the number of control points, and the rank, the relational expression of (number of elements) = (number of control points) + (rank) holds.

FIG. 2A shows an example of a uniform B-spline curve whose shape is specified based on the control points Q _{0 to} Q ₃ and the knot vector of the above equation (3). By changing the parameter t of the equation P (t) of the B-spline curve from 0 to 1, a curve as shown in FIG. 2 (A) is drawn.

Now, the mixing function of the B-spline is
It can be expressed by the recurrence formula of the recursive expression (DeBoorCox recurrence formula) as shown below.

[0070]

[Equation 2]

Here, the knot vector T is generally expressed as follows: T = [t ₀ t ₁ t ₂ ... T _{M + N-1} ] N: number of control points M: rank (order +1) (5) .

The mixing function (base function) N
_{From 0, M to} N _{n, M} and control points Q _{0 to} Q _n , the equation P (t) of the B-spline curve is generally P (t) = N _{0, M} (t) Q ₀ + N _{1, M} (t) Q ₁ + ... + N _{n, M} (t) Q _n (6)

As is clear from the above equation (6), the j-th control point Q _j has a mixing function N _{J, M.} And N
_{J and M} are functions that extend from the knot t _j to the M (floor) section.

FIG. 2B shows an example of the B-spline curve when the control points are Q _{0 to} Q ₄ and the number of elements of the knot vector T is 8.

The shape of the curve segment 10 is specified by the control points Q _{0 to} Q ₃ and the elements t _{0 to} t ₆ of the knot vector T, and the parameter t changes in the range of t ₃ ≤t <t _4. , Each point on the curve segment 10 is determined.

On the other hand, the curve segment 12 has a control point Q ₁
To Q ₄ and knot vector T by means of the elements t ₁ ~t ₇ the shape is specified, each point on curve segment 12 is determined by the parameter t varies with the variable domain of t ₄ ≦ t <t _5.

Non-uniform (Rational) rationalized B-splines are NURBS
(Non Uniform Rational B-Spline).

That is, since NURBS is non-uniform, the knot interval of the knot vector T in the above equation (5) is not constant. Therefore, since the differential coefficient of the curve (curved surface) can be corrected by the ratio of the knot intervals, the shape of the curve can be easily controlled and the shape of the curve can be locally changed. Also, various curves other than B-splines (Bezier curves, Hermitian curves, etc.) can be expressed, and all curves can be expressed in the same format.

In NURBS, since rationalization (center projection using homogeneous coordinates) is performed, the weight value for the control point can be set. Therefore, it becomes possible to draw a perfect circle or the like that cannot be drawn with an unfavorable B-spline.

2.2 Coefficient Matrix (Base Matrix) The above De used to find the value of the blending function
BoorCox's recurrence formula (4) is a recursive expression.
Therefore, it is convenient for the computer to calculate.

However, on the other hand, the recurrence formula (4)
Contains a lot of division processing with a heavy processing load, and it is necessary to judge the condition for each recursive loop. Therefore, there is a problem that the processing speed is lowered.

For example, one frame (1/60 seconds, 1/3)
In CAD / CAM, which does not require real-time processing to complete all image generation within 0 seconds), there is a margin of processing time. Therefore, recurrence equation (4) is recursively solved and the value of the mixing function is calculated. However, there is no big problem. Further, in CAD / CAM, since there is a sufficient processing time, it is general that the degree of smoothing of a free-form surface or a free-form curve is prioritized and the order of the mixing function is set to 10 or more.

On the other hand, in the game system, real-time processing is required to be realized. Therefore, it is desired that the processing load for obtaining the value of the blending function is as low as possible. In addition, the object appearing in the game is generally moving dynamically (represented as an image) like a car in a racing car game, and the viewpoint of the player watching the object is always moving.
Therefore, the free-form surface or the free-form curve representing the object may have a certain degree of smoothness, and the order of the mixing function may be about the third order or the fourth order.

The present inventor pays attention to the above points and expands the recurrence equation (4) into a general cubic equation under the condition of the fourth order without recursively solving it. Has succeeded in seeking at high speed.

By thus expanding the recurrence formula (4) into a general cubic formula, the mixing function becomes as shown in the following formula.

N _0,4 = at ³ + bt ² + ct + d N _1,4 = et ³ + ft ² + gt + h N _2,4 = it ³ + jt ² + kt + l N _3,4 = mt ³ + nt ² + ot + p (7) For example, mixing The expansion formula of the matching function N _1,4 is as follows.

[0087]

[Equation 3]

[0088]

[Equation 4]

As is clear from the above equation (9), the values of the coefficient sets e, f, g and h of the mixing function N _1,4 are substituted by substituting the values of the elements t _{1 to} t ₅ of the knot vector. Can be obtained in advance.

Similarly, the mixing functions N _0,4 , N _2,4 , N
_3,4 coefficient set a, b, c, d, i, j, k, l,
The values of m, n, o, and p can be obtained in advance by substituting the values of the elements of the knot vector.

The above equation (7) is

[0092]

[Equation 5]

It can be expressed in the form of a matrix like this. As a result, the value of the blending function can be obtained by high-speed matrix calculation.

Hereinafter, M ₁ in the above equation (10) will be referred to as a coefficient matrix (base matrix; coefficient set in a broad sense).

This coefficient matrix M ₁ and control point Q
_{Based on 0} (Q ₀ ^x , Q ₀ ^y , Q ₀ ^z ) to Q ₃ (Q ₃ ^x , Q ₃ ^y , Q ₃ ^z ), each point (P ^x (t), P
^y (t), P ^z (t)) can be obtained.

P ^x (t) = N _0,4 (t) Q ₀ ^x + N _1,4 (t) Q ₁ ^x + N _2,4 (t) Q ₂ ^x + N _3,4 (t) Q ₃ ^x P ^y (t) = N _0,4 (t) Q ₀ ^y + N _1,4 (t) Q ₁ ^y + N _2,4 (t) Q ₂ ^y + N _3,4 (t) Q ₃ ^y P ^z (t) = N _0,4 (t) Q ₀ ^z + N _1,4 (t) Q ₁ ^z + N _2,4 (t) Q ₂ ^z + N _3,4 (t) Q ₃ ^z (11)

2.3 Preparation of Coefficient Matrix in Pre-Processing Elements a to p (coefficient set) of coefficient matrix M ₁
Is unique to each control point (for example, a to d for control point Q ₀ , e to h for Q ₁ , i to ₁ for Q ₂ , and m for Q ₃ ).
~ P), it is invariant unless the knot vector changes.

Therefore, in the present embodiment, the coefficient matrix is obtained in advance (or read from the information storage medium) based on the knot vector in the processing at the stage before the real-time processing, and the coefficient matrix is not calculated during the real-time processing. I am trying. By doing this, the load during real-time processing can be greatly reduced,
The processing speed can be increased.

More specifically, in this embodiment, as shown in FIG. 3, after the game is started (after reading the game program and the object data from the information storage medium or the network), the coefficient matrix is obtained based on the knot vector. (Steps S1 and S2). Then, the obtained coefficient matrix, the control point, and N including the knot vector
URBS object data is generated (step S
3).

The NURBS object data is expanded on the storage unit (RAM) and temporarily stored, for example. The knot vector and control point data are read from the information storage medium (network).

In the processing of each frame, affine transformation (coordinate transformation to the viewpoint coordinate system, perspective transformation, etc.) for the control point is performed based on the operation data from the operation section, the game program, etc. (steps S4, S5). . Then, based on the control points after the affine transformation and the coefficient matrix included in the NURBS object data, each point on the NURBS is sequentially obtained while changing the parameter t (steps S6, S7, S8). That is, based on the coefficient matrix M ₁ , the mixing function N _0,4 ,
~ N _3,4 is obtained, and this mixing function and N _0,4 , ~ N
Each point on NURBS is obtained based on ₃ , ₄ and control points Q _{0 to} Q ₃ .

Next, the drawing process of the NURBS object is performed based on the obtained points on the NURBS (step S9). For example, when a NURBS object is drawn by a polygon, polygon data in which each obtained point is set at each vertex of the polygon is generated,
A NURBS object is drawn based on the polygon data.

Alternatively, in FIG. 4, after the game is started, the NURBS including the coefficient matrix, the control points, and the knot vectors is displayed.
Object data is read from the information storage medium (downloaded from the network). Then, based on the read NURBS object data, the processing in frame units similar to steps S4 to S9 of FIG. 3 is performed (steps S14 to S19).

When obtaining a normal vector, which will be described later, in step S2 of FIG. 3, a coefficient matrix for normal calculation is generated based on the coefficient matrix,
In step S12 of FIG. 4, it is desirable to read the coefficient matrix for calculating the normal line from the information storage medium (network). By doing so, the processing load can be further reduced. However, the coefficient matrix for calculating the normal line may be calculated in the processing of step S7 of FIG. 3 and step S17 of FIG.

When a difference matrix (difference set in a broad sense) as described later is used, a coefficient matrix for difference calculation is generated in step S2 of FIG. 3, or a coefficient matrix for difference calculation is used in step S12 of FIG. It is desirable to read the coefficient matrix for difference calculation from the information storage medium (network). By doing so, the processing load can be further reduced. However, the coefficient matrix for difference calculation may be calculated in the processing of step S7 of FIG. 3 and step S17 of FIG.

According to the present embodiment, the coefficient matrix is prepared in the stage before the loop processing for obtaining each point on the NURBS (or in the stage before the frame unit processing such as affine transformation). Therefore, it becomes unnecessary to perform the processing for obtaining the coefficient matrix in this loop processing (steps S6 to S8 in FIG. 3 and steps S16 to S18 in FIG. 4). Therefore, processing of each frame (step S4 in FIG. 3)
~ S9, steps S14 to S19 in Fig. 4 can be executed at high speed, and the real-time processing required for this type of game system can be easily realized. As a result, the real-time generation of game images using NURBS, which was said to be impossible until now, has been successfully put to practical use.

In particular, the method of this embodiment has an inventive step in that it realizes speeding up in the generation of a non-uniform free-form surface or free-form curve such as NURBS.

That is, in the uniform B-spline,
As is clear from the above equation (2), the same mixing function can always be used without depending on the domain to which the value of the parameter t belongs. Therefore, there is no need to intentionally adopt the method of preparing the coefficient matrix in advance as shown in FIGS. 3 and 4.

On the other hand, in a non-uniform NURBS in which the knot intervals of knot vectors are not constant, the mixing function to be used changes depending on the range to which the value of the parameter t belongs. For this reason, real-time processing is not required, and CAD / CAM, which has little interest in speeding up processing, performs processing for obtaining a blending function in step S in FIG.
6 to S8 and the loop processing of steps S16 to S18 of FIG. In CAD / CAM, which has a processing time enough to generate even a 10th-order NURBS, obtaining a mixing function in the above loop processing did not cause a big problem.

However, unlike CAD / CAM, in the game system, steps S6 to S8 in FIG. 3 and FIG.
If the mixing function is calculated in the loop processing of steps S16 to S18, realization of real-time processing becomes difficult.

Therefore, the present inventor has noted that in NURBS, the blending function is unique to each control point. That is, in NURBS, since the blending function is unique to each control point, even if a coefficient matrix is prepared in advance before the loop processing, the coefficient can be easily associated with each control point. Therefore, even if the coefficient matrix generation process is removed from the loop process, no problem occurs. Then, by removing the coefficient matrix generation processing from the loop processing, the processing can be significantly speeded up.

As described above, in the present embodiment, it is easy to locally control the shapes of the curved surface and the curved line, and although all kinds of curved surfaces and curved lines can be expressed, the blending function becomes non-uniform. Using NURBS, it succeeded in real-time generation of game images.

2.4 Centralized projection using rationalized homogeneous coordinates, and control points Q (x, y,
It is rationalization that the weight value w can be added to z).

For example, if the expression of the x component of the above expression (11) is rationalized, the following expression is obtained.

[0115]

[Equation 6]

Make the knot vector non-uniform,
NUR the B-spline by using the rationalized formula
Can be a BS.

For example, if the above equation (11) is expressed in the form of a matrix using the above equation (10), the following equation is obtained.

[0118]

[Equation 7]

When the above equation (13) is made advantageous, the following equation is obtained.

[0120]

[Equation 8]

When rationalization is performed, each element P ^x (t) P ^w (t), P ^y (t) P ^w (t), P is calculated based on the above equation (14).
^{After obtaining z} (t) P ^w (t), P ^w
A process of dividing by (t) is required.

However, when rationalization is not particularly necessary,
It is not necessary to force the advantage. By not performing rationalization, it becomes impossible to represent a perfect circle, but on the other hand, division processing by P ^w (t) and the like are not necessary, so that the processing can be speeded up.

As described above, it is sufficient that the free-form surface and the free-form curve to which this embodiment is applied are at least non-uniform, and it is not necessary to use NURBS for which an advantage is obtained. Further, it may be a free curved surface or a free curve other than the B spline.

2.5 Curved Surface In the above, the calculation method in the case of a curve was mainly described for the sake of simplicity. When expanding to a curved surface, the same processing as in the case of a curved surface may be performed on each component of the parameters u and v.

For example, the mixing function for each component of the parameters u and v is as follows.

[0126]

[Equation 9]

[0127]

[Equation 10]

In the above equations (15) and (16), Mu is a coefficient (base) matrix for the u component, and Mv is a coefficient matrix for the v component.

From the above equations (15) and (16), P which is a point on the curved surface
P ^x uv (u, v), which is the x component of uv (u, v), is calculated by the following equation.

[0130]

[Equation 11]

Then, in the case of making an advantage (NURB
S) has P ^x uv, similar to the rationalization in the case of curves.
^{(U, v) P w uv} (u, v) is calculated by the following equation.

[0132]

[Equation 12]

The processing for obtaining each point on the curved surface is summarized as follows. (Processing A) Coefficient matrices Mu and M for obtaining a blending function for each control point based on the knot vector
Find v. (Process B) The control points are affine transformed. (Processing C) Mixing functions Nu and Nv are obtained based on the coefficient matrices Mu and Mv and the parameters u and v set to values according to the number of divisions of the curved surface. These blending functions are unique to each control point, but when the division number actively changes, it is necessary to re-obtain the blending function each time the division number changes. (Processing D) Puv (u, v) based on the parameters u and v
Find P ^W uv (u, v). (Process E) Control point set used (combination of control points)
If does not change, the process D is repeated while sequentially changing the parameters u and v. (Processing F) When the control point set used is changed, the process returns to the process C.

FIG. 5 shows an example of the curved surface patch 20 generated by the method of this embodiment.

Here, the knot vector in the u direction is U [u
₀ , u ₁ , u ₂ ... U ₆ , u ₇ ...], and the k-vector in the v direction is V [v ₀ , v ₁ , v ₂ ... V ₆ , v ₇ ...]. Then, the coefficient matrices Mu and Mv used to generate the surface patch 20 are knot vector elements u _{0 to} u ₆ , respectively.
It is calculated based on v _{0 to} v ₆ .

Then, as is apparent from the above equation (18),
Each point on the surface patch 20 is a control point Q. ₀₀~ Q₃₃Mixed with
Function Nu_0,4~ Nu_3,4, Nv_0,4~ Nv_3,4Based on
Can be In this case, the domain of the parameter u is u₃≤u <
u_FourAnd the domain of parameter v is v₃≤v <v_FourIn
It

On the other hand, when the curved surface patch 22 is generated,
Is the set of control points used is Q₀₀~ Q₃₃To Q₀₁~
Q₃₄Change to. Then, each point on the curved surface patch 22 is
Point Q ₀₁~ Q₃₄And the mixing function Nu_1,4~ Nu_4,4, N
v_0,4~ Nv_3,4It is required based on. In this case, the parameter
The range of data u is u_Four≤u <u_FiveAnd the change of parameter v
Area is v₃≤v <v_Fourbecome.

Surface patch 2 generated according to this embodiment
The points on 0 are set to the vertices of the polygon, and the polygon constituted by these vertices is displayed on the screen.

FIGS. 6, 7, and 8 show examples of images of NURBS objects (wire frame display) generated by this embodiment. 6 shows an example when the number of divisions is small, FIG. 7 shows an example when the number of divisions is medium, and FIG. 8 shows an example when the number of divisions is large.

2.6 Calculation of Normal Vector Now, in order to perform the shading process and the hit check process of the object, the normal vector is required.
Hereinafter, a method for calculating the normal vector in the case of NURBS will be described.

In the normal normal vector calculation method, as shown in FIG. 9, the polygons PL0 to PL0 sharing the vertex VX are shared.
The normal vectors N0 to N3 of PL3 are obtained. Then, the normal vector N of the vertex VX is obtained by combining these normal vectors N0 to N3.

In the NURBS of this embodiment, each vertex is found by a cubic expression. Therefore, it is possible to obtain the normal vector based on the differential coefficients in the u direction and the v direction (tangential lines in the u direction and the v direction).

The equation P (t) of the cubic curve is as follows.

[0144]

[Equation 13]

When this P (t) is differentiated by the parameter t, the following equation is obtained.

[0146]

[Equation 14]

This makes it possible to obtain the tangent line (slope) of the curve.

On the other hand, the expression of the cubic curved surface can be generally expressed as the following expression.

[0149] Puv (u, v) = Av3 (au3 + bu2 + cu + d) + Bv2 (eu3 + fu2 + gu + h) + Cv differentiated by ^{(iu 3 + ju 2 + ku} + l) + D (mu 3 + nu 2 + ou + p) ... (21) the above equation parameters u, v (partial differential ) Then, it becomes like the following formula.

[0150]

[Equation 15]

This makes it possible to obtain the tangent line (inclination) of the curved surface in the u and v directions.

As is clear from the above equation (22), the differential coefficient of the mixing function with respect to the parameters u and v is as follows.

[0153]

[Equation 16]

[0154]

[Equation 17]

The coefficient matrix for normal calculation (the matrix obtained by multiplying the coefficient matrix and the differential coefficient matrix) in the above equations (23) and (24) is a process for obtaining each point on the free-form surface. It is desirable to prepare in the previous stage (step S2 of FIG. 3, step S12 of FIG. 4).
reference).

Based on the differential coefficient of the mixing function obtained by the above equations (23) and (24), the tangent line (tilt) vector VECU of the free curved surface in the u direction and the tangent line of the v direction as shown in FIG. The (slope) vector VECV can be obtained.

For example, the x component of the tangent vector VECU in the u direction is given by the following equation.

[0158]

[Equation 18]

In addition, x of the tangent vector VECV in the v direction
The components are as shown below.

[0160]

[Formula 19]

The above equations (25) and (26) are equations when rationalization is not performed, but can be similarly obtained when rationalization is performed.

Then, as shown in FIG. 10, by taking the outer product of these vectors VECU and VECV, the vertex V
The normal vector N at X can be determined.

By using this normal vector N, shading processing of an object composed of a free-form surface,
It becomes possible to perform hit check processing, front / back surface determination processing, and the like.

In the case of a free curve, a normal vector can be obtained by obtaining a vector that is orthogonal to the obtained tangent (slope) vector.

2.7 Solution Method Using Difference Matrix By using the difference matrix, the free curved surface and free curve generation processing can be further speeded up.

For example, a cubic expression P (t) = At ³ + Bt ² + C
The difference Δt, 2Δt, 3 of the parameter t with respect to t + D.
Substituting Δt and 4Δt gives the following equation.

[0167] _{P 0 = P (0) =} D P 1 = P (Δt) = AΔt 3 + BΔt 2 + CΔt + D P 2 = P (2Δt) = 8AΔt 3 + 4BΔt 2 + 2CΔt + D P 3 = P (3Δt) = 27AΔt 3 + 9BΔt 2 + 3CΔt + D P ₄ = P (4Δt) = 64AΔt ³ + 16BΔt ² + 4CΔt + D (27) From the above formula (27), the formula P for the difference Δt of the parameter t
The following equation is obtained as the first-order difference of (t).

ΔP ₀ = P ₁ −P ₀ = AΔt ³ + BΔt ² + CΔt ΔP ₁ = P ₂ −P ₁ = 7A Δt ³ + 3B Δt ² + CΔt ΔP ₂ = P ₃ −P ₂ = 19A Δt ³ + 5B Δt ² + CΔt ΔP ₃ = P _{4 ^{-P 3 = 37AΔt 3 + 7BΔt 2}} + CΔt ... (28) in addition, 2 of the formula P (t) with respect to the difference △ t of the parameter t
The following equation is obtained as the floor difference.

Δ ² P ₀ = ΔP ₁ −ΔP ₀ = 6A Δt ³ + 2B Δt ² Δ ² P ₁ = ΔP ₂ −ΔP ₁ = 12A Δt ³ + 2B Δt ² Δ ² P ₂ = ΔP ₃ −ΔP ₂ = 18A Δt ³ + 2BΔt ² 29) In addition, 3 of the equation P (t) for the difference Δt of the parameter t
The following equation is obtained as the floor difference.

Δ ³ P ₀ = Δ ² P ₁ −Δ ² P ₀ = 6A Δt ³ Δ ³ P ₁ = Δ ² P ₂ −Δ ² P ₁ = 6A Δt ³ (30) The above equations (27) to (30) Therefore, P ₀ = D ΔP ₀ = AΔt ³ + BΔt ² + C Δt Δ ² P ₀ = 6A Δt ³ + 2B Δt ² Δ ³ P ₀ = 6AΔt ³ (31)

The above equation (31) can be expressed in the form of a matrix as shown below.

[0172]

[Equation 20]

Here, P ₁ = P ₀ + ΔP ₀ ΔP ₁ = ΔP ₀ −Δ ² P ₀ Δ ² P ₁ = Δ ² P ₀ + Δ ³ P ₀ Δ ³ P ₁ = Δ ³ P ₀ (33) It holds. Therefore, the recurrence formula of the difference of the formula P (t) with respect to the difference Δt is as follows.

P _{n + 1} = P _n + ΔP _n ΔP _{n + 1} = ΔP _n −Δ ² P _n Δ ² P _{n + 1} = Δ ² P _n + Δ ³ P _n Δ ³ P _{n + 1} = Δ ³ P _n ... (34) Apply the above-mentioned method of solving the difference to the case of a free-form surface.

For example, consider the following equation as a general equation for a free-form surface.

[0176]

[Equation 21]

When the vector having u ³ , u ² , u and 1 in the above equation (35) is replaced with the matrix on the right side of the above equation (32) (the matrix having the parameter difference as an element), the following equation is obtained. become that way.

[0178]

[Equation 22]

Similarly, when the vector having v ³ , v ² , v 1, in the above equation (36) as an element is replaced with the transposed matrix of the matrix on the right side of the above equation (32), the following equation is obtained. Become.

[0180]

[Equation 23]

P ^x uv (u, v) is simply expressed as P ^x .

From the general expression of the above expression (37), the parameters u and v
The difference matrix of the equation of the free-form surface for the difference of (the matrix having the difference of the equation of the free-form surface for the difference of the parameter as an element) can be actually calculated by the following equation using the control points.

[0183]

[Equation 24]

The difference calculation coefficient matrix in the above equation (38) (the matrix obtained by multiplying the coefficient matrix by the matrix having the parameter difference as an element)
Is preferably prepared before the process of obtaining each point on the free-form surface (step S2 in FIG. 3, FIG. 4).
Step S12). Further, in the above formula (38), “T” means transposition of the matrix.

Each point on the free-form surface can be obtained by adding the elements of the difference matrix.

That is, first, P ^X , which is the element in the 1st row and 1st column of the difference matrix, is the first point P _{00 in} the 1st row in the u direction on the free-form surface (curved surface patch) (see FIG. 11 (B ) See).

Next, as indicated by E1 in FIG.
A process of adding each element in the first row of the difference matrix to each element in the column adjacent to the left is performed. 1 line 1 obtained by this
The element P ^X + ΔuP ^{x in the} column becomes the second point P ₀₁ (see FIG. 11B) in the first row in the u direction.

Then, addition processing as shown in E2 is performed,
The element P ^X + 2ΔuP ^x + in the 1st row and 1st column obtained by this
Δ ² uP ^x becomes the third point P ₀₂ in the first row in the u direction.

Then, addition processing as shown in E3 is performed,
The element P ^X + 3ΔuP ^x + of the 1st row and 1st column obtained by this
3Δ ² uP ^x + Δ ³ uP ^x becomes the fourth point P ₀₃ of the first row in the u direction.

As described above, each point (vertex) P ₀₀ , P ₀₁ , P on the first line in the u direction on the free-form surface (curved surface patch).
₀₂ and P ₀₃ are requested. The result of this calculation agrees with the recurrence formula (34).

Next, as shown in FIG. 12A, shift up in the v direction is performed. That is, the process of adding the element in each column of the original difference matrix to each element in the row above it is performed.
Then, the element in the first row of the obtained difference matrix (see FIG.
The addition processing similar to that of FIG. 11A is performed on F1) of 2 (B), and points P ₁₀ and P on the second line in the u direction on the free-form surface are obtained.
_{Find 11} , P ₁₂ , and P ₁₃ .

Next, shift up in the v direction is performed, and the elements in the first row of the obtained difference matrix are shown in FIG.
The same addition process as in (A) is performed to obtain the points P ₂₀ , P ₂₁ , P ₂₂ , and P ₂₃ on the third line in the u direction on the free-form surface.

Then, the v direction is further shifted up,
For the elements in the first row of the obtained difference matrix, FIG.
The same addition processing as in (A) is performed to obtain the points P ₃₀ , P ₃₁ , P ₃₂ , and P ₃₃ on the fourth line in the u direction on the free-form surface.

As described above, by using the difference matrix, each point on the free-form surface can be obtained only by the addition process. This can significantly reduce the processing load.

3. Processing of this Embodiment Next, a detailed example of the processing of this embodiment will be described with reference to the flowcharts of FIGS. 13 to 17.

FIG. 13 is a flowchart relating to the NURBS object data generation process which is performed in the preceding stage of the process for obtaining each point on the NURBS.

First, the rank of the NURBS equation is set to 4 (third order).
Is set (step S20).

Next, a coefficient matrix is obtained based on the knot vector (step S21). That is, for example, by substituting the values of the respective elements of the knot vector into the above-mentioned equation (9), a coefficient matrix (equations (10), (15), (16)) having the coefficients of the mixing function as elements is obtained. Ask.

Note that NURBS is calculated using the difference matrix.
When obtaining the above points, the obtained coefficient matrix is multiplied by a matrix having the parameter difference as an element to obtain the coefficient matrix for calculating the difference shown in Expression (38) (step S22). ).

Next, the coefficient matrix for calculating the normal line is obtained (step S23).

Then, NURBS object data is generated based on the coefficient matrix (for difference calculation, normal calculation), knot vector, and control point data obtained as described above (step S24).

For example, in FIG. 18A, Q _{00 to} Q ₅₅ are control points of NURBS, and U [u ₀ , u ₁ ... U ₉ ] and V [v ₀ , v are knot vectors in the u and v directions. ₁ … v ₉ ]
Is prepared.

In this case, the coefficient matrices Mu0, Mu
1 and Mu2 are control points Q _{00 to} Q ₅₃ , Q _{01 to} Q ₅₄ , respectively.
It is unique to Q _{02 to} Q ₅₅ and will be used when finding each point on the NURBS using these control points.

Similarly, coefficient matrices Mv0, Mv1,
Mv2, respectively, the control points _{Q 00 ~Q 35, Q 10 ~Q} 45, Q 20
~ Q ₅₅ specific, using these control points N
It will be used in determining each point on the URBS.

The data structure of the NURBS object data generated in step S24 is, for example, FIG. 18 (B).
And control points Q _{00 to} Q ₅₅ , coefficient matrix Mu
0-Mu2, Mv0-Mv2, knot vector U
It includes data such as [u ₀ , u ₁ ... U ₉ ] and V [v ₀ , v ₁ ... V ₉ ].

The matrix elements that are common to the coefficient matrices may not be redundantly and separately provided, and the NURBS object data may be compressed and stored.

Further, the processing of FIG. 13 may be performed at the time of reading the object data (at the start of the game) or before the information storage medium is created. When the processing of FIG. 13 is performed at the time of reading the object data, the knot vector and the control point data may be recorded in the information storage medium. On the other hand, when the process of FIG. 13 is performed before creating the information storage medium, NURBS object data may be recorded in the information storage medium.

When the difference matrix is used, it is premised that the initial values of the parameters u and v are 0. Therefore, it is necessary to shift the value of each element of the knot vector in each domain (section) in which the parameters u and v change. For example, the domain of u and v is u ₃ ≦ u <u ₄ ,
When v ₃ ≦ v <v ₄ , shift processing (parallel movement) as shown in the following expression is performed. U ′ = [u ₀ −u ₃ u ₁ −u ₃ u ₂ −u ₃ u ₃ −u ₃ u ₄ −u ₃ u ₅ −t ₃ u ₆ −t ₃ ...] V ′ = [v ₀ −v ₃ v ₁ −v ₃ v ₂ −v ₃ v ₃ −v ₃ v ₄ −v ₃ v ₅ −t ₃ v ₆ −t ₃ …] (39) Then, when the difference matrix is used, the above equation ( 39)
A coefficient matrix (for difference calculation) is obtained using the knot vector subjected to the shift processing of.

FIG. 14 is a flow chart relating to the process of generating the coefficient matrix for normal line calculation in step S23 of FIG.

First, k representing the number of coefficient matrices is set to 0.
Is set (step S30). Next, it is determined whether or not k = kend (step S31). If k = kend is not satisfied, the coefficient matrix is multiplied by the differential coefficient matrix as shown in the above equation (23) to calculate the normal line. The coefficient matrix of is calculated (step S32). Then, k is incremented by 1 (step S33). The above process is repeated until k = kend.

The coefficient matrix for calculating the difference shown in equation (38) can also be obtained by the same processing as in FIG.

FIG. 15 is a flow chart regarding the processing for obtaining each point on the NURBS.

First, the parameters u and v are set to u = usta.
rt and v = vstart are set (step S4)
0). In the example of FIG. 18A, start = u ₃ , v
start = v ₃ .

Next, it is judged whether v = vend, and v =
If it is not vend, it is determined whether u = uend (steps S41 and S42). In the example of FIG. 18A, uend = u ₆ and vend = v ₆ .

If u = uend is not satisfied, the current u,
The coefficient matrix, the coefficient matrix for normal calculation, and the control points according to the domain to which the value of v belongs are read from the NURBS object data generated by the processing of FIG. 13 (step S43).

Next, the tessellation process for obtaining the point (vertex) on the NURBS at the current values of u and v is performed according to the above equation (18) (step S44). Further, the tangent vector in the u and v directions is obtained based on the coefficient matrix for calculating the normal, and the normal vector is obtained by taking the outer product of the obtained tangent vectors (step S45).

Next, Δu specified by the number of divisions in the u direction is added to the parameter u to change the parameter (step S46), and the process returns to step S42.

When u = uend is determined in step S42, the parameter is changed to u = start and at the same time, the parameter v is added with Δv specified by the number of divisions in the v direction (step S42). S47). Then, it is determined whether v = vend (step S41),
The processes of steps S42 to S47 are repeated until v = vend.

For example, as shown in G1 of FIG.
Domain is u₃≤u <u_Four, V₃≤v <v_Four, Then N
From URBS object data, control point Q₀₀~ Q₃₃,
The data of the coefficient matrices Mu0 and Mv0 are read out.
It And these control points Q ₀₀~ Q₃₃, Coefficient matrix
Surface patch shown in FIG. 20 based on Smu0 and Mv0
Each point on 30 is sought.

Further, as shown in G2 of FIG. 19, when the range of u and v is u ₄ ≤u <u ₅ and v ₃ ≤v <v ₄ , NU
The data of the control points Q _{01 to} Q ₃₄ and the coefficient matrices Mu1 and Mv0 are read from the RBS object data.
Then, these control points Q _{01 to} Q ₃₄ and the coefficient matrix M
Based on u1 and Mv0, the curved surface patch 32 shown in FIG.
The above points are required.

As shown in G3 of FIG. 19, u, v
Domain is u_Five≤u <u₆, V₃≤v <v_Four, Then N
From URBS object data, control point Q₀₂~ Q₃₅,
The data of the coefficient matrix Mu2, Mv0 is read out
It And these control points Q ₀₂~ Q₃₅, Coefficient matrix
Surface patch shown in FIG. 20 based on Smu2 and Mv0
Each point on 34 is determined.

As described above, the points on all the curved surface patches 30 to 46 to be generated by the control points Q _{00 to} Q ₅₅ are obtained.

FIG. 16 and FIG. 17 are flowcharts relating to the processing for obtaining each point on NURBS using the difference matrix.

First, the surface patch numbers upn and vpn in the u and v directions are set to upn = 0 and vpn = 0 (step S50).

In the present embodiment, for example, as shown in FIG. 21, the curved surface patch numbers up of the curved surface patches 50 to 66 are up.
n and vpn are set.

Next, it is judged whether or not vpn = vpnend, and if vpn = vpnend is not satisfied, upn = u
It is determined whether it is a pnend (steps S51 and S5).
2). In the example of FIG. 21, upnend = 2, vpnen
It is set to d = 2.

If upn = upnend is not satisfied, processing is performed on the curved surface patch designated by the current upn and vpn (step S53). And after the process ends,
increment upn by 1 (step S5
4) and returns to step S52.

When it is determined in step S52 that upn = upnend, upn = 0 is returned and vpn is set.
Is incremented by 1 (step S55). Then, it is determined whether vpn = vpnend (step S
51), until step S5 until vpn = vpnend.
The processing of 2 to S55 is repeated.

FIG. 17 is a flow chart showing details of the processing for the curved surface patch in step S53 of FIG.

First, the coefficient matrix (for difference calculation, normal calculation) and control point data corresponding to the curved surface patch to be processed are read out from the NURBS object data, and according to the above equation (38). Difference matrix,
A normal difference matrix is obtained (step S60). Then, u = 0 and v = 0 are set (step S61).

Next, it is judged whether v = vend, and v =
If it is not vend, it is determined whether u = uend (steps S62 and S63).

When the difference matrix is used, the shift processing (parallel movement) as shown in the above equation (39) is performed on the parameters u and v.

If u = uend is not satisfied, the current u,
A point (vertex) on NURBS at the value of v is obtained (step S64). That is, addition processing as described with reference to FIG. 11A is performed to obtain each point in the u direction. Next, the normal vector at each point is obtained by obtaining the tangent vector in the u and v directions based on the normal difference matrix and taking the outer product of the tangent vectors (step S65). Then, Δu specified by the number of divisions in the u direction is added to the parameter u to change the parameter (step S66), and the process returns to step S63.

If u = uend is determined in step S63, the difference matrix and the normal difference matrix as described with reference to FIGS. 12A and 12B are shifted up in the v direction (step S67). ). Then, while returning to u = 0, Δv specified by the number of divisions in the v direction is added to the parameter v to change the parameter (step S68). Then, it is determined whether or not v = vend (step S62), and the processes of steps S63 to S68 are repeated until v = vend.

Note that FIG. 22 shows a comparative example of the processing speed of each method.

In FIG. 22, H1 is H3 when polygons are used, and H2 is H3 when DeBoorCox recurrence formula is used.
Is H4 in the case of the method 1 of the present embodiment described in FIG.
Represents the processing speed (processing time) in the case of the method 2 of the present embodiment described in FIGS. 16 and 17 (when the difference matrix is used). Each numerical value in FIG. 22 means that the smaller the value, the faster the processing speed.

22. H1 in FIG. 22 is the processing speed when polygon data whose total number of vertices is the number of vertices shown in H5 is generated and the vertices of those polygons are subjected to affine transformation.

On the other hand, H2, H3, and H4 in FIG.
This is the processing speed when affine transformation is performed on the control points (7 in the u direction and 4 in the v direction) to generate NURBS with the number of divisions shown in H6.

As can be seen by comparing H2 of FIG. 22 with H3 and H4, the methods 1 and 2 of this embodiment are overwhelmingly compared with the case where the coefficient matrix is not prepared in advance by using the recurrence formula of DeBoorCox. The processing speed is fast.

Compared with the case of using the H1 polygon, the processing speeds of the methods 1 and 2 of this embodiment are faster since the number of vertices exceeds 28 (the number of control points).

Further, the method 1 of this embodiment for H3 and H4,
Comparing two, the method 1 has a higher processing speed when the number of vertices is small, but the method 2 is faster when the number of vertices is large (from around 28).

4. Hardware Configuration Next, an example of a hardware configuration capable of realizing the present embodiment will be described with reference to FIG.

The main processor 900 is a CD982.
It operates based on a program stored in the (information storage medium), a program transferred via the communication interface 990, a program stored in the ROM 950 (one of the information storage media), game processing, image processing,
Various processing such as sound processing is executed.

The coprocessor 902 assists the processing of the main processor 900, has a product-sum calculator and a divider capable of high-speed parallel calculation, and executes matrix calculation (vector calculation) at high speed. For example, when a physical simulation for moving or moving an object requires a process such as a matrix calculation, a program operating on the main processor 900 instructs (requests) the coprocessor 902 to perform the process. ) Do.

The geometry processor 904 performs geometry processing such as coordinate transformation, perspective transformation, light source calculation, and curved surface generation, has a product-sum calculator and a divider capable of high-speed parallel calculation, and performs matrix calculation (vector calculation). Calculation) is executed at high speed. For example, when processing such as coordinate transformation, perspective transformation, and light source calculation is performed, the program running on the main processor 900 instructs the geometry processor 904 to perform the processing.

The data expansion processor 906 performs a decoding process for expanding the compressed image data and sound data, and a process for accelerating the decoding process of the main processor 900. As a result, a moving image compressed by the MPEG system or the like can be displayed on the opening screen, the intermission screen, the ending screen, the game screen, or the like. The image data and sound data to be decoded are stored in the ROM 950,
It is stored in the CD 982 or transferred from the outside via the communication interface 990.

The drawing processor 910 is for executing the drawing (rendering) processing of an object composed of primitive surfaces such as polygons and curved surfaces at high speed. When drawing an object, the main processor 900
Uses the function of the DMA controller 970 to pass the object data to the drawing processor 910 and
If necessary, the texture is transferred to the texture storage unit 924. Then, the drawing processor 910 draws the object in the frame buffer 922 at high speed while performing hidden surface removal using a Z buffer or the like based on these object data and texture. The drawing processor 910 can also perform α blending (semi-transparency processing), depth cuing, mip mapping, fog processing, trilinear filtering, anti-aliasing, shading processing, and the like. Then, when the image for one frame is written in the frame buffer 922, the image is displayed on the display 912.

The sound processor 930 incorporates a multi-channel ADPCM sound source, etc., and generates high-quality game sounds such as BGM, sound effects, and sounds. The generated game sound is output from the speaker 932.

Operation data from the game controller 942, save data from the memory card 944, and personal data are transferred via the serial interface 940.

The ROM 950 stores system programs and the like. In the case of the arcade game system, the ROM 950 functions as an information storage medium,
Various programs are stored in 950. A hard disk may be used instead of the ROM 950.

The RAM 960 is used as a work area for various processors.

The DMA controller 970 is a DM between processors and memories (RAM, VRAM, ROM, etc.).
It controls the A transfer.

The CD drive 980 is a CD 982 for storing programs, image data, sound data and the like.
(Information storage medium) is driven to enable access to these programs and data.

The communication interface 990 is an interface for transferring data with the outside via a network. In this case, a communication line (analog telephone line, ISDN), high-speed serial bus, or the like can be considered as the network connected to the communication interface 990. Then, by using the communication line, data transfer via the Internet becomes possible. Further, by using the high-speed serial bus, data transfer with another game system becomes possible.

The means of the present invention may be executed by hardware only, or by only a program stored in an information storage medium or a program distributed via a communication interface. Good. Alternatively, it may be executed by both hardware and a program.

When each means of the present invention is executed by both hardware and a program, the information storage medium stores a program for executing each means of the present invention using hardware. Will be. More specifically, the program instructs each processor 902, 904, 906, 910, 930, which is hardware, to perform processing, and passes data if necessary. Then, each processor 902, 904, 906, 910,
930 etc., based on the instruction and the passed data,
Each means of the present invention will be implemented.

FIG. 24A shows an example in which the present embodiment is applied to an arcade game system. The player enjoys the game by operating the lever 1102, the buttons 1104, etc. while watching the game image displayed on the display 1100. Various processors, various memories, etc. are mounted on the built-in system board (circuit board) 1106. Information (program or data) for executing each unit of the present invention is stored in the memory 1108 which is an information storage medium on the system board 1106. Hereinafter, this information will be referred to as stored information.

FIG. 24B shows an example in which this embodiment is applied to a home game system. While watching the game image displayed on the display 1200, the player operates the game controllers 1202 and 1204 to enjoy the game. In this case, the above-mentioned stored information is stored in the CD 1206 or the memory cards 1208, 1209, which is an information storage medium that can be detachably attached to the main body system.

FIG. 24C shows a host device 1300,
This host device 1300 and network 1302 (LA
A terminal 130 connected via a small network such as N or a wide area network such as the Internet)
An example in which the present embodiment is applied to a system including 4-1 to 1304-n will be described. In this case, the stored information is, for example, a magnetic disk device that can be controlled by the host device 1300,
It is stored in an information storage medium 1306 such as a magnetic tape device or a memory. When the terminals 1304-1 to 1304-n are capable of standalone generation of game images and game sounds, the host device 1300 sends game images,
A game program or the like for generating a game sound is provided on the terminal 1
It is delivered to 304-1 to 1304-n. On the other hand, when it cannot be generated standalone, the host device 1300 generates a game image and a game sound, and the terminal device 1304-1 ...
It will be transmitted to 1304-n and output at the terminal.

In the case of the configuration shown in FIG. 24C, each means of the present invention may be distributed and executed by the host device (server) and the terminal. Further, the above stored information for executing each means of the present invention may be distributed and stored in the information storage medium of the host device (server) and the information storage medium of the terminal.

The terminal connected to the network may be a home-use game system or an arcade game system. When the arcade game system is connected to a network, a portable information storage device is capable of exchanging information with the arcade game system and also with the home game system. (Memory card, portable game device) is preferably used.

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

For example, in an invention according to a dependent claim of the present invention, it is possible to omit some of the constituent elements of the claim on which the invention is dependent. Further, a main part of the invention according to one independent claim of the present invention can be made dependent on another independent claim.

Further, although the case where the present invention is applied to a free-form surface has been mainly described in the present embodiment, the present invention can be applied to a free-form curve as well.

In the present embodiment, the case of NURBS has been mainly described, but the present invention is not limited to NURBS and can be applied to various free-form surfaces and free-form curves as long as it is at least non-uniform. For example, rationalization may be omitted when the processing speed is prioritized.

Further, in the present embodiment, the case where the expressions of the free-form surface and the free-form curve are the fourth floor (third order) has been described. However, if the processing time allows, the present invention can be applied to the fifth floor, the sixth floor, etc. Is also applicable.

The expression form of the mixing function and the coefficient set is preferably the expression form described in this embodiment, but is not limited to this.

Further, in the present embodiment, an image is drawn by setting each point on the obtained free-form surface and free-form curve as the vertex of the polygon, but the obtained free-form surface and each point on the free-form curve are directly drawn. It may be drawn.

The method described in the present embodiment is particularly preferable as the method for obtaining each point on the free-form surface and the free-form curve while changing the parameters, but the method is not limited to this.

In addition, the present invention is applicable to various games (fighting games,
It can be applied to shooting games, robot battle games, sports games, competition games, role playing games, music playing games, dance games, etc.).

Further, the present invention is applicable to various game systems such as an arcade game system, a home game system, a large attraction system in which a large number of players participate, a simulator, a multimedia terminal, a system board for generating a game image (image generation). System).

[Brief description of drawings]

FIG. 1 is an example of a block diagram of a game system according to an embodiment.

FIGS. 2A and 2B are diagrams showing examples of B-spline curves.

FIG. 3 is a step before the process of obtaining each point on NURBS,
It is a figure for demonstrating the method of calculating a coefficient matrix based on a knot vector.

FIG. 4 is a step before the process of obtaining each point on NURBS,
It is a figure for demonstrating the method of reading a coefficient matrix from an information storage medium (network).

FIG. 5 is a diagram showing an example of a curved surface patch generated according to this embodiment.

FIG. 6 is an example of an image of a NURBS object generated according to this embodiment.

FIG. 7 is an example of an image of a NURBS object generated according to this embodiment.

FIG. 8 is an example of an image of a NURBS object generated according to this embodiment.

FIG. 9 is a diagram for explaining a method of deriving a normal vector of a vertex by synthesizing normal vectors of polygons sharing a vertex.

FIG. 10 is a diagram for explaining a method of obtaining a normal vector of a vertex by obtaining a tangent vector in the u and v directions.

11A and 11B are diagrams for explaining a method of obtaining each point on NURBS by adding elements of a difference matrix.

12A and 12B are v direction (column direction).
FIG. 6 is a diagram for explaining shift up of FIG.

FIG. 13 is a flowchart showing a detailed processing example of the present embodiment.

FIG. 14 is a flowchart showing a detailed processing example of the present embodiment.

FIG. 15 is a flowchart showing a detailed processing example of the present embodiment.

FIG. 16 is a flowchart showing a detailed processing example of the present embodiment.

FIG. 17 is a flowchart showing a detailed processing example of the present embodiment.

18A and 18B are diagrams for explaining NURBS object data.

FIG. 19 is a diagram for explaining a method of reading control points and a coefficient matrix based on a domain to which a parameter value belongs.

FIG. 20 is a diagram showing an example of a curved surface patch generated according to the present embodiment.

FIG. 21 is a diagram showing an example of a curved surface patch generated according to this embodiment.

FIG. 22 is a comparative example of the processing speed of each method.

FIG. 23 is a diagram showing an example of a hardware configuration capable of realizing the present embodiment.

24 (A), (B), and (C) are diagrams showing examples of various types of systems to which the present embodiment is applied.

[Explanation of symbols]

10, 12 curve segments 20,22 curved patch 30-46 curved surface patch 50-66 curved surface patch 100 processing unit 110 Game processing unit 130 Image generator 132 Coefficient calculation (reading) section 134 Affine transformation unit 136 Curved surface calculation unit 138 Normal Vector Operation Unit 140 Drawing unit 150 sound generator 160 Operation part 170 storage 172 main memory 173 Object data storage 174 frame buffer 180 Information storage medium 190 Display 192 sound output section 194 Portable information storage device 196 Communications Department

Claims (16)

(57) [Claims] 1. A game system for generating an image, wherein a coefficient set of a blending function of a non-uniform free-form surface or free-form curve whose shape is specified based on a knot vector with a non-constant knot interval and a control point is provided. , Means for preparing in the process of the previous step of sequentially obtaining each point on the free-form surface or free-curve while changing the parameter, and freely changing the parameter based on the prepared coefficient set and control points Free curved surface or free curve based on the means for sequentially obtaining each point on the curved surface or free curve and the prepared coefficient set
And a means for obtaining the normal vector of the line, and the preceding stage of the processing for sequentially obtaining each point on the free-form surface or free-form curve
In processing the floor, based on the coefficient set of the blending function
The obtained coefficient set for normal calculation is prepared, and based on the prepared coefficient set for normal calculation,
A game system characterized in that a normal vector of a free-form surface or a free-form curve is obtained . 2. A game system for generating images, which is a non-uniform free-form surface or free-form curve blending function whose shape is specified based on knot vectors and control points whose knot intervals are not constant, and recurses. Recurrence of shape representation
A means for preparing a coefficient set of a mixing function represented by a polynomial in which an expression is expanded in the process before the step of sequentially obtaining each point on the free-form surface or free-curve while changing the parameters, and the prepared coefficient and set, based on a control point, viewed contains a sequentially obtaining means each point on the free-form surface or a free curved while changing the parameters, on the free-form surface or a free curved while changing the parameters
In the process before the process of sequentially obtaining each point,
Object data including coefficient set of control function and control points
On the free-form surface or free-form curve while changing the parameters.
In the process of sequentially obtaining each point, the object data
From among the parameters, the coefficient
The game system is characterized by reading out the control points and control points . 3. A mixing function represented by a polynomial obtained by expanding a recurrence formula of a recursive expression in a process of a step before a process of sequentially obtaining each point on a free-form surface or a free-form curve according to claim 1 or 2. A game system in which a coefficient set is prepared by calculating the coefficient set based on the knot vector. 4. The method according to claim 1, wherein the coefficient set of the blending function is read from an information storage medium or read via a network in the process before the process of sequentially obtaining each point on the free-form surface or free-form curve. Therefore, the game system is characterized in that the coefficient set is prepared. 5. The game system according to claim 2, further comprising means for determining a normal vector of a free-form surface or free-form curve based on a prepared coefficient set. 6. The coefficient set for normal calculation, which is obtained on the basis of the coefficient set of the blending function in the process of the step before the process of sequentially obtaining each point on the free-form surface or the free-form curve according to claim 5. A game system characterized in that a normal vector of a free-form surface or free-form curve is obtained based on the prepared coefficient set for calculating the normal. 7. The method according to claim 1, further comprising means for performing affine transformation on control points of a free-form surface or a free-form curve in frame units, and mixing in a process in a preceding stage of affine transformation performed in frame units. A game system in which a coefficient set of a matching function is prepared. 8. The object data including a coefficient set of a blending function and a control point is prepared in a process of a step before a process of sequentially obtaining each point on a free curved surface or a free curve while changing parameters. During the process of sequentially obtaining each point on the free-form surface or the free-form curve while changing the parameter, the coefficient set and the control point according to the domain to which the value of the parameter belongs are read out from the object data. A game system characterized by. 9. A non-uniform free-form surface or free-form curve blending function coefficient, which is a computer-usable information storage medium and whose shape is specified based on a knot vector and a control point whose knot intervals are not constant. A parameter is changed based on the means for preparing the set in the process of the previous stage of the process of sequentially obtaining each point on the free-form surface or free-curve while changing the parameter, the prepared coefficient set, and the control point. However, based on the prepared coefficient set and the means for sequentially obtaining each point on the free-form surface or free-form curve , the free-form surface or free-form
A means for determining the normal vector of a line and a professional
Pre- stage of the process that sequentially calculates each point on the free-form surface or free-form curve including gram
In processing the floor, based on the coefficient set of the blending function
The obtained coefficient set for normal calculation is prepared, and based on the prepared coefficient set for normal calculation,
An information storage medium characterized in that a normal vector of a free-form surface or free-form curve is obtained . 10. A computer-usable information storage medium, which is a non-uniform free-form surface or free-form curve blending function whose shape is specified based on knot vectors and control points whose knot intervals are not constant. Recursive recursion
A means for preparing a coefficient set of a mixing function represented by a polynomial in which an expression is expanded in the process before the step of sequentially obtaining each point on the free-form surface or free-curve while changing the parameters, and the prepared coefficient and set, based on a control point, seen including a program for executing a sequential seek means each point on the free-form surface or a free curved while changing the parameters, free-form surface or a free curved on while changing the parameters of
In the process before the process of sequentially obtaining each point,
Object data including coefficient set of control function and control points
On the free-form surface or free-form curve while changing the parameters.
In the process of sequentially obtaining each point, the object data
From among the parameters, the coefficient
An information storage medium characterized by reading out the control points and control points . 11. A mixing function represented by a polynomial obtained by expanding a recurrence formula of a recursive expression in a process of a step before a process of sequentially obtaining each point on a free-form surface or a free-form curve according to claim 9 or 10. An information storage medium characterized in that a coefficient set is prepared by calculating the coefficient set based on the knot vector. 12. The method according to claim 9 or 10, wherein a coefficient set of a blending function is read from an information storage medium or is read via a network in the process before the process of sequentially obtaining each point on the free-form surface or the free-form curve. As a result, an information storage medium characterized in that a coefficient set is prepared. 13. The information storage medium according to claim 10, further comprising a program for executing a means for obtaining a normal vector of a free-form surface or free-form curve based on a prepared coefficient set. 14. The coefficient set for normal calculation, which is obtained on the basis of the coefficient set of the blending function, is prepared in the process of the preceding step of the process for sequentially obtaining each point on the free-form surface or the free-form curve. An information storage medium characterized in that a normal vector of a free-form surface or free-form curve is obtained based on the prepared coefficient set for calculating the normal. 15. The program according to claim 9, further comprising a program for executing a unit for performing affine transformation for a control point of a free-form surface or a free-form curve on a frame-by-frame basis, before the affine transformation performed on a frame-by-frame basis. An information storage medium, characterized in that a coefficient set of a blending function is prepared in the step processing. 16. The object data including a coefficient set of a blending function and a control point is prepared in a process of a step before a process of sequentially obtaining each point on a free-form surface or a free-form curve while changing parameters. During the process of sequentially obtaining each point on the free-form surface or the free-form curve while changing the parameter, the coefficient set and the control point according to the domain to which the value of the parameter belongs are read out from the object data. An information storage medium characterized by.