JPH03210670A - Sampling of three-dimensional model and calculation method of normal vector - Google Patents

Abstract

PURPOSE:To simplify the arithmetic processing for calculation of a normal vector after sampling of a 3-dimensional model and to shorten the processing time by sampling equidistantly the 3-dimensional model in both X and Y axis directions, obtaining the upper limit sampling value from the coefficient value to be multiplied by the sampling interval, and applying the coefficient value to a prescribed normal vector calculation formula. CONSTITUTION:The upper limit value of a 3-dimensional model is sampled 2-dimensionally and equidistantly in both X and Y axis directions at a sampling interval (m). Then the sampled under limit value is obtained with use of the coefficient value g (i, j) which is multiplied by the sampling interval (m). Furthermore a normal vector N = (nx, ny, nz) of a surface element enclosed by four sampling points adjacent to each other on the upper limit of 3-dimensional model is calculated from an equation I. Thus the arithmetic processing is simplified for calculation of the normal vector after sampling and the processing time is shortened.

Description

[Detailed Description of the Invention] [Field of Industrial Application] The present invention relates to a method for sampling a three-dimensional model (three-dimensional model) and calculating a normal vector in CAD, CAM, etc.
Processing) This invention relates to a method for sampling a three-dimensional model and calculating a normal vector to speed up display.

[Prior art]

In recent years, due to improvements in the hardware and software aspects of computer technology, there has been remarkable progress in combiator graphics. The drawing of not only two-dimensional models (plane models) but also three-dimensional models (stereoscopic models) has greatly evolved from the wire frame method, which draws only the outline of an object, to the solid method, which draws the upper surface of the object.

Yin-yang processing display of three-dimensional models has been known for a long time.
Particularly recently, the solid method has been widely used and has become popular. Yin-yang processing display of a 3D model involves dividing (sampling) the surface of the 3D model into triangles or polygons, calculating the normal to that surface using the cross product of each side that makes up the punch, and A method that determines the color on the patch based on the normal of the surface, and then uses that color to fill in the triangular or polygonal area projected on the screen. Specifically, the color on the surface of the 3D model is Four adjacent points P...
,,P,. 194. P. l+j+l+P i
The normal vector of the quadrilateral patch surrounded by +j+1 is determined, the brightness of the patch from that normal vector is calculated, and further, the above-mentioned P,, J, P, , J, P,. l+j
*l +P, 1. . 1 are the points Qi and j in the display coordinate system.

Q1+1+JIQj. 1,1゜l + Qi+j41
The coordinates are transformed into Q194. Q. I+j+
Ql. The process is performed by filling the area surrounded by l+j+l+Q i + j + 1 with a predetermined brightness and color. For example, Pr1ciples of In
teractive Computer Graphics
cs (W, H, Newman & R, F, 5prou
McGraw-formerly LL, 1981) and Fun
damage of Interactive
Computer Graphics, (J, D, Fol
ey & 8, Van DAM, Addis
onWesley, 1982) and others.

The two-dimensional sampling method for the three-dimensional model described above is generally widely used. For example, z=f(x,
3D graphics is a method that sequentially samples the curved surface (upper interface) indicated by 1 (Megumi Kusakata, ASCII, 197
January 9th issue, pages 14-18).

In addition, regarding the yin-yang processing display of the sampled 3D model, there are methods to create a triangular patch with adjacent sampling fish schools as vertices, and to use the cross product of the two sides that make up the patch as the normal vector of that surface, and to A method is known in which an arbitrary polygon with vertices is defined as As a method to calculate the brightness from the normal vector, Pho
ng Yin-yang is law (B, T.

Phong, “Illumination for C
o+nputer Generated Picture
s, Communications of ACM
, Vol. 1B.

No. 6) is widely used.

[Problem to be solved by the invention]

However, according to the conventional two-dimensional sampling method of a three-dimensional model and the method of calculating a normal vector, it is not possible to display a three-dimensional model in three-dimensional Yin-Yang processing on a CRT display by combining these methods. However, the sampling method and normal vector calculation method were devised separately,
In addition, since they are not assembled in a particular association, many calculations are required to calculate the normal vector after sampling, resulting in a problem that it takes a long processing time.

This invention was made in order to solve the above-mentioned problems, and it is a three-dimensional model sampling and The purpose is to provide a method for calculating normal vectors.

[Means to solve the problem]

In order to achieve the above object, this invention
In a method for sampling a three-dimensional model and calculating a normal vector, the upper bound of a three-dimensional model has a single-value upper limit f(x, y) in the Y-axis direction on a space expressed by three axes of Y-Z. The values are sampled two-dimensionally at equal sampling intervals m in each direction of the Y-axis and the Y-axis, and the sampled upper bound value is multiplied by the sampling interval m using a coefficient value g (i, j). Then, the normal vector N-(nx, ny, nz) of the plane element surrounded by four adjacent sampling points on the upper bound of the three-dimensional model is calculated by the following formula.Sampling and normal of the three-dimensional model This provides a method for calculating vectors.

That is, the method for sampling a three-dimensional model and calculating a normal vector according to the present invention includes a method for sampling a three-dimensional model, and
By considering the calculation method of the normal vector of the patch constituting the surface in close association with each other, the normal vector can be calculated by simple arithmetic processing.

[Effect]

The method of sampling a three-dimensional model and calculating a normal vector according to the present invention involves sampling a three-dimensional model at equal sampling intervals m in the X-axis direction and the Y-axis direction, and calculating the sampled upper limit values at sampling intervals rn.
It is determined using the coefficient value g (i, j) multiplied by After that, the coefficient value g described above is added to the predetermined normal vector calculation formula.
By applying (i, j), we can add 2 times and 4
Calculate the normal vector using a simple operation consisting of subtraction.

〔Example〕

DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of a method for sampling a three-dimensional model and calculating a normal vector according to the present invention will be described in detail below with reference to the drawings.

FIG. 1 is a diagram illustrating sampling of a three-dimensional model and calculation of a normal vector to which the method of sampling a three-dimensional model and calculating a normal vector of the present invention is applied. The samples are taken at equal sampling intervals m in each of the direction and the Y-axis direction, and the sampled upper limit value (recorded value) is the coefficient value g(i, j
) (i and j are index values of sampling points in the X-axis and Y-axis directions, respectively).

Note that 100 indicates the upper interface of the three-dimensional model.

The principles of the sampling and normal vector calculation method will be explained below with reference to FIG. FIG. 2 shows four adjacent sampling points cut out from FIG. 1, and the four adjacent sampling points are defined as follows.

The point on the model that corresponds to the sampling point (t, j), The point on the model that corresponds to the sampling point (i+1.j), The point on the model that corresponds to the sampling point (i+1.j+1), The sampling point Let the point on the model corresponding to (i, j+1) be , the vector from Pl to P2 is ■1, the vector from P2 to P3 is ■2, the vector from P3 to P4 is ■3, from P4 to Pl If the vector leading to is 4, then these four points PI, P2 . P3. The normal vector of the patch surrounded by P4 N=(n x.

ny.

nz) teeth, Each adjacent side mentioned above According to the method of using the sum of the cross products of as the normal of the patch, (however, Operator °゛ represents the cross product) It is expressed as

Therefore, Its component nx is However, here, Than, Therefore, +(z2-zln × (-mn −2×m×(Z　l And furthermore, z　3+z　4) Than, The value of is obtained.

Similarly, ny is 2=4 Since only the ratio of line vectors is used,
Each can be reduced by 2Xm''. Therefore, nz=2, and its normal vector can be calculated with only a very simple operation of 2 additions and 4 subtractions. In other words, this simplification can only be made possible by sampling the three-dimensional model in the X-axis direction and the Y-axis direction at equal sampling intervals m, and then finding the upper bound value as a coefficient value multiplied by the sampling interval m. That is clear.

Hereinafter, one embodiment of a method for sampling a three-dimensional model and calculating a normal vector will be described using the flowchart of Yin-Yang processing display of a three-dimensional model shown in FIG. 3, a C language program, and the like.

First, a model area is secured for recording the three-dimensional model (step 301).Specifically, in a C language program, a two-dimensional array with an appropriate size is written as follows. This size is determined by factors such as the memory size of the system on which the program is executed.Also, to simplify the explanation, the array is declared as an unsigned integer type. For fishing purposes, it is treated as a fixed decimal point based on the binary system.For example, in a 16-bit computer, an integer type (int) is reserved as 16-bit data, but 8 bits of that are used to represent the part below the decimal point. If it is secured as Conversion to a type can be achieved using only a simple shift operation, and addition and subtraction processing can be performed in the same way as for integer types.This is advantageous because addition and subtraction processing for integer types can be performed very quickly on a computer.

Next, r sampling interval m is determined 1 (step 3
02). In this step, the sampling interval m is calculated from the size of the model to be displayed. For example, X of the model to be displayed.

xsize each size in the Y and Z directions.

When ysize and zsize are written in the C language program, by sampling at intervals of m, the entire model can be recorded in the model array described above.

Generate r model 1 (step 3o3).

The value in the Z-axis direction of the model to be displayed can be expressed as f (x, y), and the area of the model to be displayed is X, Y.

O to xsize-1, 0 to ysi respectively in the Z direction
If ze-1,0 to zsize-1 is written, for example, in a C language program, the sampling of the area where the model exists in the model array is completed.

The above three steps 301, 302, and 303 are executed as preprocessing, and the initialization of the model and others is completed.

After that, in step 304, "Patch selection 1 is performed. Batch selection controls the order of patches to be processed.
Hidden surface processing etc. are realized by this selection order of patches. Specifically, for example, the patches are processed sequentially starting from the previous patch,
There are methods such as providing a write-protected area and implementing hidden surface processing by sequentially processing patches starting from the rear.

This step and the following steps 305, 306゜3
Step 07 is repeated until all quadrilateral punches formed by four adjacent sampling points on the model array have been processed, in other words until all i and j have been processed (step 308).

Step 305 performs "calculation of r normal" which is the main part of this invention. For example, in a C language program, it is written as nz = 2; (i, j), (i+1.j).

(i + 1, j + 1), (i,
The normal vector of the patch surrounded by the four sampling points of J+1) is calculated.

Next, although the details are omitted, using Phong Yin and Yang, the r brightness of the patch is calculated 1 based on the normal vector determined in Step 305 (Step 306).

In step 307, coordinate transformation is performed on the four vertices of the patch onto the r screen, and the area is filled in.

After completing the above steps, you will be able to see a Yin-Yang model displayed on the screen. Further, if there is a partial change in the model (steps 309 and 31O), the process returns to step 304 and the display is performed again.

Although the static display of a three-dimensional model has been described here, it can also be applied to animation simulations, etc. by taking advantage of its high speed. It is also effective to apply this method to interference checks during model cutting, automatic determination of tool paths, etc.

The above-described flowcharts and program examples are examples of hour wheels for the purpose of explanation, and it goes without saying that various other embodiments are possible.

In this way, in this example, by associating the sampling of the model with the calculation of the normal vector, the calculation of the normal vector, which is processed in the inner loop with a large number of repetitions in the display process, can be reduced to a simple calculation. It can be processed at high speed.
I can do it.

〔Effect of the invention〕

As explained above, according to the method of sampling a three-dimensional model and calculating the normal hector of the present invention, a three-dimensional model is sampled at equal sampling intervals m in the X-axis direction and the Y-axis direction, and the sampling The coefficient value g (i,
Find it using j). After that, by applying the coefficient value g(i, j) described above to a predetermined normal vector calculation formula, the normal vector is calculated with a simple operation consisting of two additions and four subtractions, so sampling is performed. The calculation process for later normal vector calculation can be simplified,
Processing time can be shortened.

[Brief explanation of drawings]

FIG. 1 is an explanatory diagram showing the sampling method of the three-dimensional model and the method of calculating the normal vector according to the present invention, FIG. 2 is an explanatory diagram showing the method of calculating the normal vector, and FIG.
The figure is a flowchart of an embodiment in which the three-dimensional model sampling and normal vector calculation method of the present invention is utilized for Yin-Yang processing display of a three-dimensional model. In the drawings, the upper interface is 100. In the drawings, the same reference numerals indicate the same or equivalent parts.

Claims (1)

[Claims] In a space expressed by three orthogonal axes X-Y-Z,
In a method for sampling and calculating a normal vector of a three-dimensional model having a single-value upper bound value f(x, y) in the axial direction, the upper bound values of the three-dimensional model are set at equal intervals in each direction of the is sampled two-dimensionally at a sampling interval m, the sampled upper bound value is obtained using a coefficient value g (i, j) multiplied by the sampling interval m, and further, the upper bound value of the three-dimensional model is Normal vector N = (nx, n
y, nz) by the following formula nx=g(i,j)+g(i,j+1) -g(i+1,j)-g(i+1,j+1)ny=g(
i, j) + g (i + 1, j) - g (i, j + 1) - g (i + 1, j + 1) nz = 2 A method for sampling a three-dimensional model and calculating a normal vector.