Triangle polygon plotting device and triangle polygon plotting method

[0001] The present invention relates to a triangular polygon drawing apparatus for and a triangular polygon drawing method of decomposing a triangular polygon into pixels so as to draw the triangular polygon in a technology field of displaying a computer graphics image on a display.

[0002] FIG. 1A is a diagram for explaining a prior art triangular polygon drawing method. For example, the following reference discloses this prior art triangular polygon drawing method of generating pixels by repeatedly performing edge and span processings.

[0003] <Reference>

[0004] Computer Graphics Principles and Practice Second Edition, pp. 883 to 885, by James D. Foley, Andries van Dam, Steven K. Feiner, and John F. Hughes.

[0005] Next, a description will be made as to an operation of the prior art triangular polygon drawing method.

[0006] This triangular polygon drawing method is divided into three processings: a setup processing, an edge processing, and a span processing, as shown in FIG. 1B. In the setup processing, the increment parameters for a left edge, a right edge, and a span (a scanline between the right edge and the left edge, i.e., a current span) of FIG. 1A are calculated for various components of a pixel. The various components of a pixel are a depth value (z), color values (r, g, b, a), texture coordinates (s,t), and so on. The setup processing is performed on each triangular polygon only once.

[0007] In the next edge processing, a pixel Pleft on the left edge and a pixel Pright on the right edge for an active scanline are determined by an interpolation processing by using the increment parameters for the left and right edges that are determined in the setup processing. For example, the X coordinate of the left edge for the active scanline is calculated by adding the increment parameter Xleft to the preceding X coordinate Xold, as shown by the following equation (1):

[0008] In the span processing, pixels on the active scanline between the pixel Pleft on the left edge and the pixel Pright on the right edge, which are determined in the edge processing, are determined one by one by interpolation. As in the case of the edge processing, a new pixel can be determined by adding an X-direction increment parameter to each of the various components of the preceding pixel.

[0009] All pixels that constitute the triangular polygon are generated by repeatedly performing the edge and span processings for all scanlines ranging from an initial scanline including a vertex V0 to a scanline including another vertex V1.

[0010] A problem with the prior art triangular polygon drawing apparatus and the prior art triangular polygon drawing method is that when determining a pixel (Pleft) on a left edge for carrying out updating of scanlines, it is necessary to performs a calculation (subpixel correction) on a pixel value at the central point of the pixel again.

[0011] The subpixel correction process of correcting the pixel value on the edge to the value of the central point of the pixel is expressed by the following equation (3):

[0012] where X0 is the X coordinate of the central point of the pixel, and Px is a pixel increment parameter in the direction of an X axis. The equation becomes Z0Zleft(X0Xleft)Zx for the Z value, for example. It can be understood from the equation (3) that amultiplication circuit having a larger circuit scale than an adding circuit is needed for the subpixel correction processing. Because the subpixel correction processing has relatively a large amount of calculations, the amount of overhead for updating of scanlines is very large and the volume of H/W components increases.

[0013] The present invention is proposed to solve the above-mentioned problems, and it is therefore an object of the present invention to provide a triangular polygon drawing method capable of eliminating the subpixel correction processing required for updating of scanlines, and of drawing a triangular polygon with simple control and with efficiency.

[0014] In accordance with an aspect of the present invention, a triangular polygon drawing apparatus includes triangle type determining means for classifying a shape of a triangular polygon from data about coordinates of vertices of the triangular polygon according to a direction and slope of a major edge of the triangular polygon so as to determine a moving direction in which pixels are to be moved, and pixel drawing means for sequentially generating pixels by interpolation with respect to a direction of an X axis, the pixels starting from a start pixel that is the nearest to a point having a minimum Y coordinate or maximum Y coordinate of the triangular polygon based on the moving direction determined by the triangle type determining means, saving a generated pixel that is placed inside the triangular polygon across the major edge for a first time, and moving the generated pixel from the major edge to a minor edge so as to draw one scanline of the triangular polygon, and for generating a start pixel of a next scanline from the saved pixel by interpolation with respect to a direction of a Y axis.

[0015] Therefore, the triangular polygon drawing apparatus can determine the moving direction in which pixels are to be moved by classifying the shape of the triangular polygon into one of four types, can eliminate a subpixel correction processing with a large amount of calculations, and can draw triangular polygons with simple control and with efficiency.

[0016] In accordance with an aspect of the present invention, a triangular polygon drawing method includes the steps of classifying a shape of a triangular polygon from data about coordinates of vertices of the triangular polygon according to a direction and slope of a major edge of the triangular polygon so as to determine a moving direction in which pixels are to be moved, and sequentially generating pixels by interpolation with respect to a direction of an X axis, the pixels starting from a start pixel that is nearest to a point having a minimum Y coordinate or maximum Y coordinate of the triangular polygon based on the moving direction determined by the triangle type determining means, saving a generated pixel that is placed inside the triangular polygon across the major edge for a first time, and moving the generated pixel from the major edge to a minor edge so as to draw one scanline of the triangular polygon, and generating a start pixel of a next scanline from the saved pixel by interpolation with respect to a direction of a Y axis.

[0017] Therefore, the triangular polygon drawing method makes it possible to determine the moving direction in which pixels are drawn or moved by classifying the shape of the triangular polygon into one of four types, can eliminate a subpixel correction processing with a large amount of calculations, and can draw triangular polygons with simple control and with efficiency.

[0018] FIG. 1 is a diagram for explaining a prior art triangular polygon drawing method;

[0019] FIG. 2 is a diagram showing the structure of a triangular polygon drawing apparatus according to embodiment 1 of the present invention;

[0020] FIG. 3 is a diagram for explaining an operation of the triangular polygon drawing apparatus according to embodiment 1 of the present invention;

[0021] FIG. 4 is a diagram for explaining the shapes of four types of triangular polygons to which a target triangular polygon is classified in a type determination step;

[0022] FIG. 5 is a diagram showing a direction in which pixels are drawn and stored pixels; and

[0023] FIG. 6 is a diagram showing the structure of a triangular polygon drawing apparatus according to embodiment 2 of the present invention.

[0024] In order to explain the present invention in greater detail, the preferred embodiments will be described below with reference to the accompanying figures. Embodiment 1.

[0025] FIG. 2 is a diagram showing the structure of a triangular polygon drawing apparatus according to embodiment 1 of the present invention.

[0026] In FIG. 2, reference numeral 1 denotes parameter calculating means for calculating increment parameters from vertex data about the vertices of a target triangular polygon, reference numeral 2 denotes triangle type determining means for classifying the shape of the triangular polygon into one of four types from the increment parameters from the parameter calculating means 1, reference numeral 3 denotes start pixel calculating means for calculating a start pixel from the increment parameters from the parameter calculating means 1, reference numeral 4 denotes pixel moving means (i.e., pixel drawing means) for moving a pixel in a direction of an X axis or direction of a Y axis according to the determination result from the triangle type determining means 2, and reference numeral 5 denotes pixel interpolating means (i.e., the pixel drawing means) for interpolating pixel values according to data from the pixel moving means 4.

[0027] Next, a description will be made as to an operation of the triangular polygon drawing apparatus according to embodiment 1 of the present invention.

[0028] FIG. 3 is a diagram for explaining the operation of the triangular polygon drawing apparatus (i.e., a triangular polygon drawing method) according to embodiment 1 of the present invention.

[0029] In FIG. 3A, the parameter calculating means 1 sorts a triangular polygon's vertices first in a vertex sorting step ST1. This sorting is so implemented that a vertex with a minimum Y coordinate (referred to as a minimum Y coordinate vertex from here on) is defined as V0(X0,Y0), a vertex with a maximum Y coordinate (referred to as a maximum Y coordinate vertex from here on) is defined as V1 (X1,Y1), and the remaining vertex is defined as V2 (X2,Y2) (refer to FIG. 3B). Assume that an upper-left side corner is an origin O of the X-Y coordinate system.

[0030] In the next parameter calculation step ST2, the parameter calculating means 1 calculates increment parameters with respect to both the direction of the X axis and the direction of the Y axis for each of the various components of a pixel from the vertex data V0, V1, and V2 of the triangular polygon. The various components of a pixel are a depth value (Z), color values (R,G,B,A), texture coordinates (U,V), and so on. For example, when the Z values of the vertices V0, V1, and V2 are z1, z2, and z3, respectively, the X-direction increment parameter dZdx and Y-direction increment parameter dZdy for the Z component are calculated by using the equations of planes and are given by the following equations (4) and (5):

[0031] where a symbol C of the equations (4) and (5) means a vector product of the triangle V0V1V2, and is given by the following equation (6):

[0032] Similarly, in order to determine whether a current pixel exists on which side of an edge in the parameter calculation step ST2, the parameter calculating means 1 also calculates increment parameters of an edge function with respect to both the direction of the X axis and the direction of the Y axis. The increment parameters of the edge function are calculated for each of a major edge, a minor edge 0, and a minor edge 1.

[0033] When advancing to a type determination step ST3, the triangle type determining means 2 classifies the shape of the triangular polygon into one of four types by using the sign of the vector product C or the like calculated in the parameter calculation step ST2, as shown in FIG. 4.

[0034] FIG. 4 is a diagram for explaining the shapes of the four types of triangular polygons to which the target triangular polygon is classified in the type determination step. The four types of triangular polygons have the following shapes:

[0035] Triangular polygon Type1 of FIG. 4A;

[0036] The major edge is on the left side of the polygon.

[0037] The X coordinate of the vertex V0 is smaller than that of the vertex V1.

[0038] Triangular polygon Type2 of FIG. 4B;

[0039] The major edge is on the left side of the polygon.

[0040] The X coordinate of the vertex V0 is larger than that of the vertex V1.

[0041] Triangular polygon Type3 of FIG. 4C;

[0042] The major edge is on the right side of the polygon.

[0043] The X coordinate of the vertex V0 is smaller from that of the vertex V1.

[0044] Triangular polygon Type4 of FIG. 4D;

[0045] The major edge is on the right side of the polygon.

[0046] The X coordinate of the vertex V0 is larger than that of the vertex V1.

[0047] In other words, the target triangular polygon is classified into one of the four types from the direction and slope of the major edge thereof in order to determine in which direction pixels are to be moved with respect to the direction of the X axis and in which direction pixels are to be moved with respect to the direction of theY axis, as will be explained below. A correspondence between each of the four types of triangular polygons and the moving direction (designated by the arrow show in FIGS. 4A to 4D) in which pixels are to be moved is provided as follows:

[0048] Triangular polygon Type1 of FIG. 4A;

[0049] Pixels are moved in a downward and rightward direction (i.e., the direction of the positive Y axis and the direction of the positive X axis) with respect to the vertex V0.

[0050] Triangular polygon Type2 of FIG. 4B;

[0051] Pixels are moved in an upward and rightward direction (i.e., the direction of the negative Y axis and the direction of the positive X axis) with respect to the vertex V1.

[0052] Triangular polygon Type3 of FIG. 4C; Pixels are moved in an upward and leftward direction (i.e., the direction of the negative Y axis and the direction of the negative X axis) with respect to the vertex V1.

[0053] Triangular polygon Type4 of FIG. 4D;

[0054] Pixels are moved in a downward and leftward direction (i.e., the direction of the positive Y axis and the direction of the negative X axis) with respect to the vertex V0.

[0055] In the start pixel calculation step ST4, the start pixel calculating means 3 calculates a start pixel by using the increment parameters calculated in the parameter calculation step ST2 (refer to FIG. 3C). The start pixel is calculated as the component values of the central point of a pixel that is the nearest to the vertex V0 or V1 (subpixel correction) For example, the Z component of the start pixel is calculated by using the following equation (7):

[0056] where px0 and py0 are the X andY coordinates of the start pixel, respectively, and are integers.

[0057] Next, in steps ST5 and ST6, interpolation is carried out with respect to the direction of the X axis until the current pixel moves across the major edge (i.e., while NO in step ST5) (refer to step ST6 and FIG. 3D). In which direction the current pixel is to be moved with respect to the X axis is determined based on the result obtained in the type determination step ST3. The interpolation process is performed by adding the X direction increment parameter calculated in step ST2 to each component of the current pixel. For example, the interpolation processing for the Z component of the current pixel is calculated by using the following equation (8):

[0058] When the current pixel moves across the major edge (i.e., when YES in step ST5), the component values of the pixel is stored (or saved) as a pixel M (in step ST7). This stored pixel M is a pixel that is used for triggering a shift o the next scanline processing.

[0059] FIG. 5 is a diagram showing a direction in which pixels are drawn and stored pixels M. In FIG. 5, each circle shows a pixel that is to be stored as a pixel M. By determining the sign of the edge function, whether or not the current pixel moves across the major edge can be easily determined.

[0060] In steps ST8, ST9, and ST10, pixels are generated and drawn by interpolation with respect to the direction of the X axis until the current pixel moves across the minor edge 0 or minor edge 1 (i.e., while NO in step ST8) (refer to steps ST9 and ST10, and FIG. 3E). In which direction pixels are drawn or moved with respect to the X axis is determined based on the determination result obtained in the type determination step ST3. The interpolation processing is performed by adding the X-direction increment parameter calculated in step ST2 to each component value of the current pixel. Generation and drawing of pixels for one scanline can be carried out according to these steps.

[0061] When the current pixel moves over one of the minor edges (i.e., when YES in step ST8) and then the method advances to step ST11, the pixel M stored in step ST7 is recovered and the pixel M is set to the current pixel. Then, in steps ST12 and ST13, if the Y coordinate of the current pixel does not exceed Y1, interpolation with respect the direction of the Y axis is carried out (refer to FIG. 3F). In which direction pixels are drawn or moved with respect to the Y axis is determined based on the determination result obtained in the type determination step ST3. The interpolation processing is performed by adding the Y-direction increment parameter calculated in step ST2 to each component value of the current pixel. For example, the interpolation processing required for the Z component of the current pixel is carried out by using the following equation (9):

[0062] On the other hand, because it can be assumed that the drawing of all scanlines is completed when the Y coordinate of the current pixel exceeds Y1 (i.e., when YES in step ST13), the drawing of the target triangular polygon is completed at that time.

[0063] Thus, the moving direction in which pixels are drawn or moved is determined according to the classification of the triangular polygon as shown in FIG. 4, and interpolation is implemented with respect to the direction of the X axis to generate pixels starting from the start pixel that is the nearest to the vertex V0 or V1. The pixel M that is placed inside the triangular polygon across the major edge of the triangular polygon for the first time is saved, and the interpolation and drawing processings are carried out so as to generate pixels running in the direction of the X axis until the current pixel moves across the minor edge 0 or minor edge 1.

[0064] When updating of scanlines is carried out, the saved pixel M is recovered and interpolation with respect to the direction of the Y axis is implemented on the pixel M. Then, interpolation with respect to the direction of the Y axis is implemented for the next scanline based on the interpolated pixel M. Therefore, when shifting to the next scanline, because the interpolated pixel M is positioned outside the triangular polygon with few exceptions, the interpolation with respect to the direction of the X axis is implemented so that the current pixel is moved toward the major edge. Conversely speaking, the classification as shown in FIG. 4, the start pixel, and the moving direction in which pixels are to be moved with respect to the X and Y axes so that the interpolation of the pixel M with respect to the direction of the Y axis results in the interpolated pixel M being positioned outside the triangular polygon with few exceptions, and the interpolation with respect to the direction of the X axis is implemented to move the current pixel toward the major edge.

[0065] After that, interpolation and drawing are repeatedly performed so as to generate pixels running in the direction of the X axis until the current pixel is placed outside the triangular polygon across a minor edge after being placed inside the triangular polygon across the major edge for the first time (i.e., interpolation and drawing are repeatedly performed until the current pixel exceeds the Y coordinate of the vertex V1 or V0). Therefore, because only a simple addition is needed for the updating of scanlines, the amount of calculations can be controlled and the amount of overhead for the updating of scanlines can be reduced (i.e., the volume of H/W components can be reduced).

[0066] As mentioned above, according to the embodiment 1, the triangular polygon drawing apparatus includes the parameter calculating means 1 (i.e., theparameter calculation step) for calculating the increment parameters with respect to the directions of the X and Y axes for the various components of a pixel from the vertex V0, vertex V1, and vertex V2 of a triangular polygon, the triangle type determining means 2 (i.e., the triangle type determination step) for classifying the shape of the triangular polygon into one of four types according to the direction and slope of a majors edge of triangular polygon so as to determine the moving direction in which pixels are to be moved, the start pixel calculating means 3 (i.e., the start pixel calculation step) for calculating the various components of a start pixel that is the nearest to the vertex V0 or V1, and the pixel moving means 4 and the pixel interpolating means 5 for generating pixels by interpolation with respect to the direction of the X axis from the start pixel and saving a generated pixel M that is placed inside the triangular polygon across the major edge for the first time, for generating pixels running from the major edge to a minor edge by interpolation so as to draw one scanline of said triangular polygon, and for generating a start pixel of the next scanline from the saved pixel M by interpolation with respect to the direction of the Y axis. Therefore, the triangular polygon drawing apparatus of this embodiment can determine the moving direction in which pixels are drawn or moved by classifying the shape of the triangular polygon into one of four types, can eliminate a subpixel correction processing with a large amount of calculations, and can draw triangular polygons with simple control and with efficiency.

[0067] Furthermore, in accordance with embodiment 1, when the triangle type determining means determines that the major edge is on the left side of the triangular polygon and the triangular polygon has a minimum Y coordinate vertex whose X coordinate is smaller than that of a maximum Y coordinate vertex thereof, the pixel drawing means sequentially draws pixels of one scanline by moving a start pixel that is the nearest to the minimum Y coordinate vertex in the direction of the positive X axis and the direction of the positive Y axis. Therefore, the triangular polygon drawing apparatus of this embodiment can determine the moving direction in which pixels are drawn or moved according to the shape of the triangular polygon, can eliminate a subpixel correction processing with a large amount of calculations, and can draw triangular polygons with simple control and with efficiency.

[0068] Furthermore, in accordance with embodiment 1, when the triangle type determining means determines that the major edge is on the left side of the triangular polygon and the triangular polygon has a minimum Y coordinate vertex whose X coordinate is larger than that of a maximum Y coordinate vertex thereof, the pixel drawing means sequentially draws pixels of one scanline by moving a start pixel that is the nearest to the maximum Y coordinate vertex in the direction of the positive X axis and the direction of the negative Y axis. Therefore, the triangular polygon drawing apparatus of this embodiment can determine the moving direction in which pixels are drawn or moved according to the shape of the triangular polygon, can eliminate a subpixel correction processing with a large amount of calculations, and can draw triangular polygons with simple control and with efficiency.

[0069] Furthermore, in accordance with embodiment 1, when the triangle type determining means determines that the major edge is on the right side of the triangular polygon and the triangular polygon has a minimum Y coordinate vertex whose X coordinate is smaller than that of amaximumY coordinate vertex thereof, the pixel drawing means sequentially draws pixels of one scanline by moving a start pixel that is the nearest to the minimum Y coordinate vertex in the direction of the negative X axis and the direction of the negative Y axis. Therefore, the triangular polygon drawing apparatus of this embodiment can determine the moving direction in which pixels are drawn or moved according to the shape of the triangular polygon, can eliminate a subpixel correction processing with a large amount of calculations, and can draw triangular polygons with simple control and with efficiency.

[0070] Furthermore, in accordance with embodiment 1, when the triangle type determining means determines that the major edge is on the right side of the triangular polygon and the triangular polygon has a minimum Y coordinate vertex whose X coordinate is larger than that of a maximum Y coordinate vertex thereof, the pixel drawing means sequentially draws pixels of one scanline by moving a start pixel that is the nearest to the maximum Y coordinate vertex in the direction of the negative X axis and the direction of the positive Y axis. Therefore, the triangular polygon drawing apparatus of this embodiment can determine the moving direction in which pixels are drawn or moved according to the shape of the triangular polygon, can eliminate a subpixel correction processing with a large amount of calculations, and can draw triangular polygons with simple control and with efficiency.

[0071] Embodiment 2.

[0072] FIG. 6 is a diagram showing the structure of a triangular polygon drawing apparatus according to embodiment 2 of the present invention. The same reference numerals as shown in FIG. 2 denote the same components as those of the triangular polygon drawing apparatus according to embodiment 1 or like components.

[0073] In FIG. 6, reference numeral 6 denotes pixel moving direction predetermining means (i.e., pixel drawing means) for determining a moving direction in which pixels are to be moved in advance by determining whether pixels are placed inside or outside a target triangular polygon.

[0074] The triangular polygon drawing apparatus of this embodiment 2 basically operates in the same way that that of embodiment 1 does. However, the triangular polygon drawing apparatus of this embodiment 2 differs from that of embodiment 1 in that it predetermines the moving direction in which pixels are to be moved by calculating the values of edge functions in advance. In other words, without performing additions for the edge functions and additions for pixels (e.g., for their Z values) at the same time, the triangular polygon drawing apparatus can perform additions for the edge functions in advance (e.g., prior to additions forpixels byone clock cycle) and can predetermine whether or not pixels are made to move across a minor edge.

[0075] Because the triangular polygon drawing apparatus moves pixels and performs interpolation on a pixel-by-pixel basis without performing an interpolation processing along any edge of the triangular polygon, a subpixel correction processing for updating of scanlines becomes unnecessary. As a result, while the complex arithmetic processing becomes unnecessary and the drawing speed can be improved, the volume of H/W components can be reduced.

[0076] As mentioned above, according to embodiment 2, because the triangular polygon drawing apparatus includes the pixel moving direction predetermining means 6 for predetermining the moving direction in which pixels are to be moved by calculating the values of the edge functions in advance and then determining whether pixels are placed inside or outside a target triangular polygon, a useless addition processing required for pixels (e.g., for pixels that are made to move across a minor edge) with respect to a direction of an X axis and a direction of a Y axis becomes unnecessary and the drawing efficiency can be further improved.

[0077] As mentioned above, the triangular polygon drawing apparatus and triangular polygon drawing method in accordance with the present invention are suitable for an image display of triangular polygons with simple control and with efficiency.