JPH02259888A - Polygon internal interpolation method - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention relates to a polygon internal interpolation method used in graphic processing to display three-dimensional graphic information on a two-dimensional plane in a form that is easy for humans to understand. It is related to.

[Conventional technology]

When displaying a three-dimensional figure on a two-dimensional plane such as the display surface of a cathode ray tube display, the three-dimensional figure 18 is divided into a large number of polygons 18a as shown in FIG.
The boundary portion of 8a is displayed with yin and yang by linear interpolation, and hidden surfaces are removed to display it in a form that is easy for humans to understand.

For example, when converting a triangle, which is the basic form of a polygon, into two dimensions, hidden surfaces are removed by calculating the Z value of the Z coordinate at the X and Y coordinate positions inside the triangle by linear interpolation from the binary values of the vertices. , that is, if two shapes overlap,
Used to hide figures on the back side, and set brightness values (colors) at the vertices! (hereinafter abbreviated as l value), it is linearly interpolated to smoothly change the ■ value to display Yin and Yang.

Each vertex Pi, P2. of the triangle shown in FIG. x, y to P3
, z coordinate, and Iii are given, the conventional method of interpolating the Z value and I value of the Z coordinate inside a general triangle is as shown in the flowchart shown in FIG.

A straight line H extending in the horizontal direction (scanning direction) from the second vertex P2 of the triangle shown in FIG. 6 intersects the first intersection P4 with the side connecting the first vertex P1 and the third vertex 23. Find the Z value of this intersection P4! The value is calculated by linear interpolation from the first vertex P1 and the third vertex P3 (step 5T7-1)
, 5T7-2).

Next, the horizontal increment value of the Z value and ■ value between the second vertex P2 and the intersection point 14 is calculated (step 5T7-3).

Then, the first vertex P1, the second vertex P2, and the first
Incremental values of the Z value and I value along the side between the vertex P1 and the intersection point 14 are calculated (step 5T7-4).

Next, the following steps are executed while sequentially changing the Y coordinate from the first vertex P1 to the intersection P4. The initial value of the Y coordinate is the Y coordinate of Pl (step 5T7-5).

By adding the increment values of the Z value and I value obtained in step 5T7-4 above, the left side X, which is the starting point from the first vertex P1 to the second vertex P2 at the current Y coordinate The coordinates, Z value, ■ value, and the X coordinate, Z value, and ■ value of the right side of the end point on the intersection P4 from the second vertex P2 are determined (step 5T76).

The Z value and 1 value between the start point and end point are determined in step 5T6-
It is obtained by sequentially adding the horizontal increment values obtained in step 3 (step 5T7-7).

Next, after decrementing the Y coordinate by "1" (step 577-8
), it is determined whether this Y coordinate is larger than the Y coordinate of the second vertex P2 (step 5T7-9); if YES, the process returns to step 5T7-6 and repeats steps 5T7-6 to 5T7-8. .

If the determination at step 5T7-9 is No, the operations at steps 5T7-1 to 5T7-7 are repeated to each point P2. P3. Points inside the triangle at the bottom of the drawing with P4 as the vertex are interpolated (step 5T7-10).

[Problem to be solved by the invention]

As described above, the conventional internal interpolation method for polygons uses the value of the vertex as a reference and calculates the increment value in the side direction and horizontal direction to the Z of the neighboring point.
&1! This is a method of sequentially calculating by adding the increments of and I@. Therefore, although there is an advantage that only addition calculations are required, there is a problem that the next point cannot be found unless the value of the adjacent point is determined, and it is not suitable for high-speed processing such as parallel processing.

The present invention has been made to solve the above-mentioned problems, and an object of the present invention is to provide a polygonal internal interpolation method that can perform parallel processing.

[Means to solve the problem]

A polygonal internal interpolation method according to the present invention is a polygonal internal interpolation method when dividing the shape of an object into predetermined polygons and performing graphic processing. and a vertical direction increment value, the polygon is divided into a predetermined number of parts, and internal interpolation of the polygon is performed in parallel using the horizontal direction increment value and the vertical direction increment value.

[Effect]

The polygon internal interpolation method in this invention calculates in advance the horizontal increment value and the vertical increment value of two orthogonal axes, so that the points inside the polygon can match the Z values of other points, ll1
It becomes possible to calculate i independently regardless of whether it has been calculated or not. As a result, internal interpolation of polygonal surfaces can be executed in parallel, facilitating high-speed processing.

[Embodiment] An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram of a device that implements the internal interpolation method of the present invention. 10 is a processing position calculation circuit that inputs triangular data and calculates which point to process; 12 is a processing position calculation circuit that performs initial processing on two orthogonal axes; 1.4a to 14n are edge function calculation circuits that determine whether or not a point to be processed is inside a triangle; 16a to 16n are initial value calculation circuits that calculate a horizontal direction increment value and a vertical direction increment value; Zla and ! of the points to be processed based on the data of the value calculation circuit 12 and the edge function calculation circuits 14a to 14n. This is an internal value calculation circuit that calculates values.

FIG. 2 is an explanatory diagram of processing according to the internal interpolation direction of the present invention. For example, when one processing element (PE) is assigned to processing one point and 16 processing elements (4 x 4) are used in parallel. The edge function calculation circuit 14a (~14n) shown in FIG. 1 corresponds to each processing element.
) and internal value calculation circuits 16a (-16n) are provided.

As shown in FIG. 3, the edge function calculation circuits 14a to 14n calculate the following equation to determine which side of the straight line the point is on, and calculates E (X, Y) = (X-
xo) * (yl-yO)-(Y-yO)* (xi
-xlO) E (X, Y) >0 Internal E (X, Y) -0 vector E (X, Y) <Q This is a function that judges and examines the outside, and applies this function to the three sides of the triangle. .

Next, the internal interpolation method of the present invention will be explained based on the flowchart shown in FIG. First, steps 5T4-1 to 5T43 for calculating the horizontal direction increment value are the same as steps 5T7-1 to 5T7-S and T7-3 in FIG. 7, so a redundant explanation will be omitted.

Next, a straight line V extending vertically from the first vertex P1 intersects the side connecting the second vertex P2 and the third vertex P3.
Find the intersection P5, and calculate Zfa and Iv of this second intersection P5.
L is calculated by linear interpolation from the second vertex P2 and the third vertex P3 (steps 5T4-4 and ST4-5). Then, the vertical increment value between the first vertex P1 and the second intersection point 25 is calculated by the initial value calculation circuit 12 (step 5T4
-6).

Next, the edge function calculation circuits 14a to 14n determine whether each point including the triangle is inside or outside the triangle (step 5T4-7).

As a result of the determination, if the point is inside a triangle, the Z value and I value of each point are calculated from the horizontal increment value and vertical increment value. Internal value calculation circuit 16 for 16 processing elements while shifting their positions so that all points inside the triangle are included.
Parallel processing is performed simultaneously on a to 16n (step 5T4-8
~5T4-10).

In this case, for example, the position of e” is outside the triangle, so
If the process is devised so that no processing is performed, only 11 processing elements are required to perform the processing, and the speed can be further increased.

Although the above embodiments have been described with respect to triangles, internal interpolation can be similarly performed on polygons other than triangles.

〔Effect of the invention〕

As described above, according to the present invention, the horizontal increment value and vertical increment value of two orthogonal axes are calculated in the initial processing, and the Z value and I value are calculated independently and in parallel for each point inside the polygon. By making it possible to obtain , high-speed processing through parallel processing becomes easy, and three-dimensional figures and the like can be displayed at high speed.

[Brief explanation of drawings]

Fig. 1 is a block diagram of a device that implements the internal interpolation method of this invention, Fig. 2 is an explanatory diagram of processing by the internal interpolation method of this invention, Fig. 3 is an explanatory diagram of edge function calculation, and Fig. 4 is an illustration of the invention. Flowchart diagram explaining the internal interpolation method, Figure 5 is an explanatory diagram of dividing a three-dimensional figure into polygons, Figure 6 is an explanatory diagram of processing by the conventional internal interpolation method, and Figure 7 is the conventional internal interpolation method. It is a flowchart figure explaining. P1 to P3... First to third vertices P4. P5
... Intersection 2 no chishi to j m 2 big) Diction] g 1 Me black 7 ri f Fig. 1 This light bright direction t light 0 flow gay -) concave Fig. 4 PI (xl, yl) Ni, 'ni'! Different 2 and 1 ship ↓ Open view Figure 3 Figure 6 J An in Jirem at the end of the customer, Place A F ↓ Sakimyo Figure 6

Claims (2)

[Claims] (1) In a polygon internal interpolation method when performing graphic processing by dividing the shape of an object into predetermined polygons, within a polygonal plane that is an internal plane partitioned by the polygon of a plane containing the polygon. Find the horizontal increment value and vertical increment value of two perpendicular axes, divide the polygon into a predetermined number, and perform internal interpolation of the polygon in parallel using the horizontal increment value and vertical increment value. A polygon internal interpolation method characterized by performing the following. (2) In the polygon internal interpolation method according to claim (1), for each point including the polygonal surface, it is determined whether it is an internal point or an external point of the polygonal surface by edge function calculation, and the determination result is , if the polygon is internal, the internal interpolation of the polygon is performed in parallel using the horizontal increment value and the vertical increment value of the orthogonal two axes.