Generating an image

The present invention is a device for generating an image of an object in a three-dimensional space to be displayed on a two-dimensional regular pixel array composed of a series of pixel sequences. , The device: a means for generating and storing multiple basic element descriptors, each with a geometric surface description for the basic elements of the desired image, and one point common to each pixel. A means for using the stored basic element descriptor to generate a point sample and an intermediate pixel array, and one point for each of the basic elements and the pixels for the generation of a plurality of the intermediate pixel arrays. Means for providing different predetermined offsets between the two, and means for combining the plurality of intermediate pixel arrays pixel by pixel in order to generate and store a filtered pixel array. It relates to an image generator to be equipped.

[0002] The above-mentioned type of device is described by Henry Fuch et al., Computer Graphics, Vol.19, No. It is known from'Fast Spheres, Shadows, Textures, Transparencies and Image Enhancements in Pixel Planes' on pages 111-120 of 3 (GRAPH 85), especially'Successive Refinement' on pages 119 and 120. According to Fuch, "each pixel (xy) is subdivided into a grid of sub-pixels, and the address of each sub-pixel is (x + xoffset,). It is in the form of y + y offset). Each time, the image is offset slightly (xoffset, yoffset) and the image is generated several times, eg 16 times. In this way, the sample points in the pixel region form an appropriate distribution. By adding A.xoffset + B.yoffset to the proportional coefficient C of each broadcast triple, it can be easily changed. Use two color buffers. One of them is for storing the color generated by the final image generation offset, and the other is for storing the running average when moving around the sub-pixel grid. "[0003] The main purpose of the filtering obtained by this method is to reduce the aliases generated by the sampling process. The prominent aliases are at the ends of the basic elements that are skewed in correlation with the pixel array axis. It is a step structure that appears. This effect is especially noticeable when the ends of the basic elements are approximately aligned with the axes of the pixel array.

[0004] [Problems to be Solved by the Invention] However, it is desirable to be able to provide such high-quality (real-time) image composition to the market, but the cost of'pixel plane'hardware and two full-frame color buffers are required. The large amount of memory makes Fuch's method too expensive to apply to ordinary hardware.

[0005] Classes of depiction algorithms known as scanning algorithms include, for example, E. Catmull "A Hidden-surface Algorithm with Anti-aliasing" Computer Graphics Vol.12, No.3,6-11 (GRAAPH 1978) and It is known from L. Corpenter, "the A-buffer, an Antialiased Hidden Surface Method", Computer Graphics Vol.18, No. 3,103 ~ 108 (GRAPH 1984). In the scanning algorithm, images are generated in a single pixel sequence at a time. However, the antialiasing algorithms disclosed by Catmull and Carpenter are complex to implement in hardware, especially in common hardware.

[0006] An object of the present invention is at near real-time speed in a system that does not have a large processing power applicable to image generation as compared to a known system, that is, a low cost, less complex hardware system. It is intended to realize the composition of antialiased images.

[0007] The present invention uses a database module (OBJ) and geometrically to generate an image of an object in three-dimensional space to be displayed on a two-dimensional regular pixel array consisting of a series of pixel sequences. The geometric module (GEOM), which transforms the geometrical descriptions of various object spaces related to the basic elements defined by the database module (OBJ) into the equivalent descriptions of the field of view space, and these descriptions. A basic element storage device (PST) to store, a span generator (SPGN) that holds an active polygon list, inputs a basic element descriptor, outputs a span descriptor, and performs antialiasing filtering by multiple depiction, and a span processor. A device composed of (SPPR), for the device to use the stored basic element descriptor in order to point sample a common point for each pixel and generate an intermediate pixel array. Means, means for providing different offsets between the basic element and one point per pixel for the generation of the plurality of intermediate pixel arrays, and generation of filtered pixel arrays, and In an image generator including a means for combining the plurality of the intermediate pixel arrays for each pixel in order to store the intermediate pixel arrays, the intermediate pixel array is regarded as a single pixel array, and the generation of the intermediate pixel array is performed. Pixel-by-pixel coupling is first performed on the first pixel example of a series of pixel sequences, followed by a series of pixels until an image is completed on the two-dimensional regular pixel array. In addition to being configured to be sequentially performed on a new pixel sequence, the apparatus further comprises a means for recognizing that the basic element is active for each pixel in the series of pixel sequences, and a series. For each pixel of the pixel array, a means for recognizing that the basic element is active and inactive depending on the offset, and for each pixel of the series of pixel sequences. When an active basic element is recognized by means for recognizing that the basic element is active, or each pixel in the series of pixels.When the existence of the basic element that is active is recognized by the means for recognizing that there are times when the basic element is active and when it is not active depending on the offset, the series of the above series. It is active by means for generating and coupling an intermediate pixel array for each pixel of the pixel array and for recognizing that the basic element is active for each pixel of the series of pixel sequences. A means for recognizing that when the basic element is no longer recognized, or when the basic element is active or inactive depending on the offset for each pixel in the series of pixel sequences. When the existence of the active basic element is no longer recognized by, it is determined that the image is completed, and a means for terminating the generation and coupling of the intermediate pixel array for each pixel of the series of pixel sequences is provided. It is characterized by having.

[0008] By doing so, it is possible to realize hardware having a small size and high-speed memory in the pixel processing stage by generating an intermediate pixel array in a row (that is, one scanning line) at a time. it can. Only one full-frame color buffer is needed, resulting in significant savings. At the same time, with fairly simple hardware, simple point sample depictions can be used to avoid complex analytical filtering programs.

[0010] Further, as described above, the image generator according to the present invention is a basic element for each of a series of new pixel sequences.<u style="single">But</u>It has the means to recognize it as active. Therefore, by arranging the depiction means and ignoring the descriptor of the basic element other than the active, wasteful processing effort is saved.

However, with different sub-pixel offsets applied between depictions, when activating the various basic elements for each depiction, this offset employs sample points across the edges of the basic elements. , Active polygons (polygons that mean polygons form part of the base element descriptor in this case) have problems maintaining information.

[0012] Accordingly, the image generator according to the invention may further comprise a means for recognizing another subset of the basic elements as potentially active in the new pixel sequence based on the offset. it can. The depiction means can selectively treat the basic elements of the other subset as active in response to each offset.

By identifying other potentially active basic elements on a given scanline based on the magnitude of any particular offset, a scanline algorithm is provided, along with the required information in the row direction. The algorithm. This required information in the row direction, which is usually not available in the algorithm, is needed to enable antialiasing filtering with multiple depictions.

[0014] Further, the image generator according to the present invention provides, for each basic element, start row data for identifying the first pixel row in the series of pixel rows in which the basic element is active. A means for generating and storing, and for identifying and adding to the list of active basic elements the first arbitrary active basic element in each new pixel sequence, while retaining the list of active basic elements. The start column data can be used to further provide means for updating the list.

[0015] Further, the pixel generator according to the present invention includes a list for the start row data to identify the first arbitrary active basic element in the series of pixel rows for each pixel row. Can be obtained.

[0016] Further, the image generator according to the present invention generates end row data for each basic element for identifying the last pixel row in the series of pixel rows in which the basic element is active. A means for storing and a means for removing the basic element from the list of active basic elements when the plurality of intermediate pixel arrays for the last identified pixel sequence are depicted can be further provided. ..

[0017] Further, in the image generator according to the present invention, each basic element descriptor includes a pointer area for pointers of other basic element descriptors, and the active basic element list is continuous for each column. It can be formed by linking the active basic elements in a chain using such a pointer.

[0018] Here, the "basic element descriptor" refers to stored data in which a basic element is defined by surface data such as size, shape, position, color, texture, etc. in a three-dimensional environment. It was adopted as a convenient way to do this.

[0019] In addition to the geometric descriptor, each base element descriptor and each span descriptor can represent a variety of one or more parameter changes over the surface of the base element. Such parameters include depth (Z), constitutive coordinates, and other parameters related to the effects of light. To provide the best image quality, such parameters require not only vertical offset correction, but also horizontal edge correction (ie, so-called "column start correction"). This compensates for the truncation of the horizontal start position to the integer pixel position.

[0020] Therefore, in one embodiment of the present invention, the depiction means receives the basic element descriptor and generates a series of span descriptors that define the range of the basic element in the corresponding pixel sequence. The span-generating means is: means for calculating the horizontal start position of the span using the accuracy of the sub-pixels; and for calculating the initial value for at least one other parameter. With the means of; receive the vertical offset value using the precision of the subpixel, from which the vertical offset correction for the horizontal start position is calculated and according to the vertical offset correction, said horizontal. Means for modifying the start position; for the other parameter initial values, (i) the modification for the received vertical offset and (ii) for the subpixel portion of the modified horizontal start position. It is possible to perform calculations related to the correction of the above, compensate for the truncation from the horizontal start position to the integer pixel position, and provide means for correcting the initial values of the other parameters according to these corrections.

[0021] The "sub-pixel" referred to here is not the same as the "intermediate pixel". Spacing less than the width or height of a pixel is called a sub-pixel and is used to describe the degree of movement of the sample point within the pixel boundaries, or the amount of offset given to the coordinates of the base element. "Intermediate" refers to the partial value from which the value for output or display is subsequently derived instead of the x / y position or the pixel value that is finally displayed. Further, in the above, the "at least one other parameter" is, for example, the value of the depth coordinate z described later in relation to FIG. 7. The constant value calculated for the vertical offset correction of the horizontal start position can also be useful in the calculation of the correction of the values of other parameters.

Therefore, in one embodiment of the present invention, the horizontal start position of the span is modified before the modification of the other parameter initial values, and a fractional portion of the modified horizontal start position is modified. It can be temporarily stored for use in calculations and applied to the other parameter initial values.

[Example] In a description of the present invention with reference to the following drawings, FIG. 1 is a diagram schematically showing a conventional image display device for displaying a three-dimensional object on a two-dimensional display. Is. The database module (OBJ) stores and manages a model of a three-dimensional environment containing various three-dimensional objects formed as a group of basic object elements, that is, a database constituting "object space". Each basic element can be, for example, a polygonal surface or a curved patch. These are sequentially defined by geometric descriptions, such as vertex coordinates and surface descriptions such as color, composition, transparency, surface normals, and the like. A geometric surface description of the light source can also be included. The other module (VEW) defines the visual field space from, for example, the position of the viewpoint, the viewing direction, and the point of view of the visual field.

A user input means (INP) such as a tracker ball, mouse and / or keyboard is connected to a human-computer interface module (HCI) so that the user can process, modify or also view the object in object space. It allows us to process viewing direction and other properties related to the viewing space. The Geometry Module (GEOM) performs geometric transformations to transform the geometric descriptions of various object spaces with respect to the basic elements defined by the Database Module (OBJ) into equivalent descriptions in the visual space. In general, these transformations include translation, rotation and perspective as are well known in the art. Surface descriptions of basic elements are also defined according to the lighting conditions in the visual space. In the general case where the image is two-dimensional, the coordinates in the two-dimensional view space, usually referred to as x and y, correspond linearly to the coordinates of the screen, while the third coordinate z is the screen of the object. Corresponds to the depth to.

The geometric module (GEOM) sends the basic element description of the visual field space to the depiction module (DRW), and the depiction module sends the basic element description of the visual field space in a form suitable for display, generally scan conversion. Converts to a 2-D array of pixel values in the image buffer memory (ININT). The Depiction Module (DRW) uses the z coordinate to perform hidden surface removal calculations as well as shading calculations. Suitable means for performing such tasks are known in the art.

[0026] In the literature cited above, the pixel array in the buffer (IMINT) is set as the midpoint of the sampled image according to the multiple depiction technique described by Fuch et al. For each image generated on the display (DIS), a set of N intermediate images is drawn, and the module (OFFS) applies different predetermined offsets to each of the N pictures, and each Allow the sample points of each pixel to move between depictions. The image accumulator buffer (IMACC) adds the intermediate images at the same time as the intermediate image is generated, and after N depictions, the image accumulator buffer (IMACC) follows the sample point distribution and the weights that can be added to each sample point. , Has a filtered image.

[0027] As described by Fuch et al., When images should be improved sequentially and at the same time they should be displayed, the values held in the buffer (IMACC) should be normalized to ensure that each depiction is true. It should be possible to form an execution average. However, if the buffer (IMACC) is a double buffer, the intermediate pixel values can simply be added and divided by N after the full depiction is performed and the final mean is obtained. .. The final mean is read into the output means of the double buffered image accumulator (IMACC).

[0028] In practice, offsets can be used to move the basic elements associated with this fixed sample point array. By the way, for the sake of simplicity, in FIG. 2, which illustrates the reverse situation, the basic element P having the end E and the vertex V is invariant over the square array of pixel regions A, B, etc. Together, N is equal to 16 different subpixel offset effect point samplings at the points marked with dots in each of the two representative pixel regions A and B.

The sample point arrays shown in pixels A and B are identical and each pixel region of the pixel array follows a subpixel array defined by a set of N (= 16) sample points. Repeated every time. It can be seen that the sub-pixel array of FIG. 2 is a simple example of a sample point located in the center of a square grid of 16 sub-pixels.

[0030] For simplicity, assuming that the color value of the basic element P shown by the diagonal lines is 1 and the background color value is 0, the final average in pixel A is shown in FIG. The value is 7/16 or 8/16, and the final mean in pixel B is 5/16 or 6/16. These subparts show a small part of the pixel area covered by the basic elements quantized by 16 subpixels, and the image in the accumulator buffer (IMACC) is at least roughly antialiased. There is.

[0031] There is a problem with antialiasing processing. This is more pronounced for some features of the image than for others. In particular, at the end, such as the end E, which has a slight inclination with respect to the coordinate axes of the pixel array, a fairly obvious staircase effect tends to occur. This is especially true if the steps of the stairs appear to move at high speed along the end E as the end E moves, for example, to positions E'and E'' as a continuous image, especially in motion pictures. Interferes with the image sequence.

FIG. 2 shows how the sample grid pattern uses these 16 potential quantization levels inefficiently, especially when the aliases are most prominent in general. As the base element end E moves to position E', the filtered color values are still constant at 8 out of 16. Therefore, in the small space between E and E , the value suddenly rises by 4 levels to 12 out of 16. In effect, as the relevant edges approach horizontal or vertical, the potentially available quantization levels of N (= 16) actually drop slightly to N (= 4). However, 12 out of 16 depictions are effectively superfluous in situations where good filtering is most needed. Our Simultaneous Pending UK No. 9014528.5 Patent Application (PHB) 33649) discloses a new series of sampling arrays. This array uses the quantization level more effectively by providing an array of points that are irregular or regular but not aligned with the sequence of pixels. Therefore, the point projection intersects the pixel axis at more points than N. The present invention is equally applicable to the prior art regular sub-pixel arrays and the special sub-pixel arrays disclosed in the co-pending applications cited above.

[0033] FIG. 3 shows a display device according to the present invention for displaying an image representing an object in a three-dimensional space on a two-dimensional display in a substantially block format. The image is generated by the scan line algorithm and is arranged to allow multiple depictions of the image for antialiasing filtering.

[0034] As shown in FIG. 1, a model of a three-dimensional environment in which a database module (OBJ) includes various three-dimensional objects each formed as a group of object basic elements, that is, "objects". Stores and manages the database that forms the "space". The other module (VEW) defines the visual field space, for example, in terms of the position of the viewpoint, the viewing direction, and the viewpoint of the visual field. A user input means (INP) such as a tracker ball, mouse and / or keyboard can be connected to the Human Computer Interface (HCI) to allow the user to process or modify an object in object space, or to view, view and otherwise. It makes it possible to process characteristics related to the visual space. The Geometry Module (GEOM) performs geometric transformations to transform the geometric descriptions of various object spaces with respect to the basic elements defined by the Database Module (OBJ) into equivalent descriptions of the visual space. These descriptions are part of the Geometric Module (GEOM) Basic Element Storage (PST). Is remembered in. The span generator (SPGN) and span processor (SPPR), in combination with the offset generator (OFGN), are equivalent to the modules (DRW) and (OFFS) in Figure 1.

[0035] Here, the span generator (SPGN) is a means for using the stored basic element descriptor, and determines which basic element of the image contributes to each pixel sampled. For each pixel sampled N times prior to drawing, each sample is taken from a different position within the pixel, especially where the pixel is only partially covered by the basic elements so that the exact value rises for the pixel. It is necessary to be. Further, regarding the addition of the offset, a different point is specified each time with respect to the sample point in the pixel.

Also, the intermediate pixel array is a single point sample value for each pixel along a line following sampling of each pixel at sample points having the same relative position within each pixel. In other words, the first intermediate pixel array comprises a list of values resulting from sampling each pixel once in its upper left hand corner. The next intermediate pixel array is another collection of values for those same pixels, this time following each sampling at its center.

The step of combining the intermediate pixel arrays involves accumulating all the different point sample values for each pixel in the array, and then these values are applied to the pixels as a whole in the output image. Used to generate an average (or weighted average) value to be. Generating the mean is as simple as adding the sample values of N points together to the pixels and dividing by N to give the output value.

As described above, the N intermediate pixel array is generated by sampling one row of pixels N times with respect to the output array during operation, and then before moving to the next line of output pixels. Combine N intermediate pixel arrays to give one line of output pixel values to, and then generate and combine N intermediate pixel arrays again.

[0039] Since the above is the subject of the present invention and is therefore also described in claim 1, this part is described in FIGS. 8 (a) to 8 (c), 9 and 10, and FIG. This will be explained in an easy-to-understand manner with reference to FIGS. 11 (a) and 11 (b). It should be noted that this description includes the definition of the terminology used in the present specification and the explanation of the relationship between the terminology. Further, in FIGS. 8 to 11 used for explanation, the number of sample points per pixel is 16, which is the same as in FIG. 2.

[0040] In all of FIGS. 8-11, each square represents a pixel, and when the image is displayed, the surface of each pixel is squeezed to find the average or overall color applied to the entire pixel plane. Point sample 16 times. Hereinafter, the process until the image is displayed will be described by dividing it into steps representing the process.

Step 1: As shown in FIG. 8 (a), consider the pixels that make up the pixel array (DIS), one row at a time. For a given pixel sequence (N) (see FIG. 8 (a)), the first step is to take a sample value A at the first point in each pixel of the sequence. Thus, for each of the pixels in the column, each sample value A_l, A₂ , A₃ ···have. All sample points A have the same offset (x)₁ , y_l)have. Note that although in the figure this offset is measured and shown with respect to pixel boundaries (rather than with respect to any x, y axis), however, this produces the same result as the offset measured with respect to the underlying elements. I want to. In the actual result, there is a common sample point position marked within each pixel, and the application of the offset is a pixel (hence the sample point) relative to the basic element while the image is being depicted. ) Shift the position.

[0042] In relation to the terminology used, the distances of offsets x, y are less than the pixel width and are therefore referred to as sub-pixel offsets. The sample value A is called the intermediate pixel value because the value A represents only part of the pixel (ie, should be combined with the others). Values collected for sample point A along pixel sequence (N), i.e., values (A)_l, A₂ , A₃ ...) Array is therefore an intermediate pixel array. Therefore, the above value (A_l, A₂ , A₃ ...) Gives a first intermediate pixel array. Now, considering one at a time, these intermediate pixel arrays are therefore also a single pixel array.

Step 2: As shown in Figure 8 (b), in this step the pixel offset is (x).₂, y₂ ), Which changes the position of the sample point with respect to the base element from A to B. This gives a second intermediate pixel array containing the values (Bl, B2, B3 ...) For the pixel sequence (N) (see Figure 8 (b)).

[0044] Step 16: The process of changing the offset and collecting another intermediate pixel array is continued from step 2 to 14 times until step 16. In step 16, the last sample point P is used, as shown in Figure 8 (c), which is the value (P) for the pixel sequence (N) (see Figure 8 (c))._l, P₂, P₃ ...) Gives a 16th intermediate pixel array containing. As mentioned above, 16 sample points per pixel were selected as typical values here, but it should be noted that other numbers are also selected.

[0045] Step 17: The process of combining the first to 16th intermediate pixel arrays obtained as described above for each pixel begins. The values of each sample point from each of the 16 intermediate pixel arrays for that pixel are collected into one, as shown in Figure 9, where the pixel sequence (N) (see Figure 9). Value of sample points in the pixel inside A_lFrom P_lValues up to are collected in one. The sample point value is a single value Q, which is the display value applied to all pixels when the image is displayed.₁Is then processed to give. This particular form of processing is not a substantive feature of the present invention and, in fact, the sample point value A_lFrom P_lValue Q based on₁There are several ways in which is selected. In the attached example, the value Q₁Is taken as the direct average of the values of the 16 sample points, but not only that value, but also more complex calculations with weights given to the position of the sample points within the pixel can be used.

[0046] Step 18: As described above, the process (combination) of collecting the values of a plurality of sample points into one is sequentially performed for each pixel in the column. This is an array per pixel value (Q_l, Q₂, Q₃...) Generates a filtered pixel array for columns of the form.

Step 19: As shown in FIG. 10, the processes of steps 1 to 18 described above are repeated for the next column (N + 1) (see FIG. 10) of the pixel sequence (N), and sequentially. All pixel sequences are sampled from one column to the next, and the filtered pixel array is pulled out for all pixel arrays to give a filtered pixel array for the entire image. It repeats until it is done.

[0048] Further, in the present invention, for each pixel in a series of pixel sequences, a means for recognizing that the basic element is (always) active, and a recognition that the basic element may be active depending on the offset. It has the means to do it.

This will be described with reference to FIGS. 11 (a) and 11 (b). First, the term "active" means that the basic element contributes to the output value for the pixel. In the example shown in FIG. 11 (a), the basic elements are clearly active. This is because the pixel offset contributes to the output value no matter where the sample points (A to P) for that pixel are placed relative to the basic element.

Next, in the example shown in FIG. 11 (b), the basic element may be active depending on the offset. This is because the offset may or may not contribute depending on where the sample point is placed with respect to the pixel. For this example (Figure 11 (b)), if the pixels are sampled at an offset that places the sample points at points A, L, E, G, D, H, P, N, K or O, for example. The base element does not contribute to the output value, so the base element will not be active. However, if the pixel is sampled at any of the points F, C, I, B, M and J, the base element will contribute to the output value and therefore the base element will be active.

[0051] The scan line algorithm produces one image line at a time, usually from top to bottom. While processing the screenline, in the examples described, polygons (polygons are examples of parts of the base element descriptor, which is a geographical description of the base elements of the image (ie, triangles and polygons (ie, triangles and polygons). A description of the surface corresponding to the basic element (ie, what color the basic element is, what its light reflection characteristics are, etc.), but all that contribute to the line. Information about the basic elements must be available. This is achieved by using a linked list of polygons that contribute to all output values, called the Active Polygon List (APL). When moving from one screen line to the next, if some polygons do not contribute to the image, they should be removed from the list. Others, on the other hand, should begin to contribute and be added together. The order in which the polygons appear in the list does not matter at all. It is only necessary that the list accurately records all the polygons that partially cover the current line.

[0052] To construct the active polygon list, a data table of all the two-dimensional polygons that form the image is assembled before any pixel of the image occurs. This is contrasted with a non-scanning line system as shown in FIG. In a non-scanning system, one polygon at a time is processed from a 3D representation to a 2D pixel. On the other hand, in the present invention, when one 3D polygon is classified into buckets for each screen line, a new polygon is created by simply adding an appropriate bucket list to the active polygon list (APL). Added to the Active Polygon List (APL). Figure 5 shows this configuration in memory PST.

As shown in FIG. 5, a memory bank 0,1, ----- L indicating a bucket list of polygons starting at scan line 0,1, ----- L Provide. These Y buckets contain a linked list of polygons starting at a given line Y. Figure 5 shows that two polygons start at line Y = 0 (1st and 2nd). For each polygon, the start line (STY) and end line (EDY) are stored along with the edge tilt and the X value at the start line (this is the basic element of the triangle shown in Figure 4). It will be a single value). In addition, the depth value (z) and surface properties are also stored.

The basic algorithm of the span generator (SPGN) for processing one frame is as follows: For each Y, if there is a new entry in the Y bucket, the new entry is the active polygon. Generate a span descriptor for each polygon in the active polygon list to add to the list. If the line is an end line (EDY), remove the polygon from the active polygon list. If the line is not an end line (EDY), increment the end.

In this way, after all polygons have been classified into Y buckets based on the value of the smallest Y bucket, the span generator (SPGN) will move from the smallest screen Y to the largest screen Y, ie. Cross the screen from top to bottom. For each line, the span generator (SPGN) transmits a span descriptor (SD) to the span processor (SPPR) for each polygon of the line. The span processor sends pixels to a single pixel sequence line image buffer (LIMINT), which stores intermediate pixel values. The span generator (SPGN) maintains a list of active polygons that are updated before processing each scan line. Usually new Y bucket polygons are added to the list and some old ones are removed. The remaining old polygons have all the edge values that are incremented by the vertical tilt at this stage.

At any screen line Y = L, there is a bucket of linked polygons. It ends with a null pointer, a pointer pointing to address zero. The processor in the span generator (SPGN) holds a list of active polygons. In the current line, the processor first adds bucket L to the active polygon list and incorporates polygons. This starts at this line by first writing the start address of bucket L to the null pointer of the active polygon list. At this time, the null pointer of the bucket L forms a new null pointer of the active polygon list. At this time, the span generator traverses the active polygon list, and for each polygon, the span descriptor (SD) To generate. Span descriptor (SD), start and end x-values, depth or z-values, colors, light-dark values, etc. This span descriptor is sent to an independent span processor (SPPR), which writes the pixel values to the line buffer (LIMINT). If necessary, hidden surface removal is also performed at this stage, for example by the z-buffer algorithm. The span generator (SPGN) also increments the x-left and x-right values of each polygon descriptor with the appropriate slope value in preparation for the next screen line.

The amount of memory that should be allocated to the Y bucket polygon list depends on the total number of polygons in the scene and the complexity of the data structure. Elaborate depiction programs with multi-configuration maps require significantly more storage capacity than simple Gouraud shaded polygons. The polygon list holds two different linked structures, namely the Y bucket linked list and the active polygon linked list at the same time. However, since these lists are not needed at the same time, the same pointer area can be applied to both at the same time.

[0058] In memory, an array of size equal to the number of lines on the screen (0,1-----L) with an entry pointing to the Y bucket, i.e., a linked polygon starting at each line. Make a list. Also in the active polygon list (APL), a pointer indicating the first polygon structure, that is, an APL start is provided. This structure is used to hold the active polygon list (APL). The only area of interest in this structure is the link pointer. FIG. 5 shows the contents of the frame polygon memory before processing the first screen line.

[0059] First, the link pointer area of the APL start indicates a null. The Y bucket entry for screenline zero points to a list of two polygons linked by the link pointer area. The second polygon points to null. The new Y bucket will be added to the active polygon list at the start of each screen line. If the bucket is empty, the polygon null pointer at the end is a null pointer and is simply overwritten from the bucket array entry.

[0060] According to the antialiasing filtering mechanism disclosed by Fuch et al., All polygons in the frame are sent to the cumulative buffer many times. Each depiction has a different pair of subpixels x-offset and y-offset. All x and y polygon configuration positions are processed to maintain fractional accuracy. Finally, the antialiasing effect is used to spatially filter the image. The scan lines processed by definition occur on the basis of the line-by-line principle. Further, the x-offset of the sub-pixel can be easily processed, but the y-offset causes one scan line to affect the next scan line. This is not possible even with known scanline algorithms.

[0061] In the present invention, antialiasing is the result of filtering given by N oversamplings performed on each pixel. This softens the edges of the basic element and spoils the appearance of the graphic image based on the basic element to which antialiasing is not applied, eliminating the visible ladder-stepped anthropogenic effect.

FIG. 4 shows the triangles at normal positions 1 and 2 possible offset positions 2 and 3. On scan lines A through D, the new span limits xleft and xright for positions 2 and 3 can be calculated from the offset values Nx and Ny. The values Nx are simply added to xleft and xright, and Ny is edge-sloped and converted to a horizontal offset before subtraction. That is; xleft (new) = xleft + Nx-Nyδxleftxright (new) = xright + Nx-Nyδxright Each span is sent to the span processor (SPPR) multiple times with xleft and xright values modified according to each offset.

[0063] In order to perform antialiasing filtering by multiple depiction, each span descriptor needs to be sent to the span processor (SPPR) many times. This is not a problem for horizontal (ie x) offsets, but there are many problems with vertical (ie y) offsets. At scan line A, these offsets reduce the scan to zero or negative length. Strictly speaking, the polygon ends at line D, but if it is offset to position 3, it must also be drawn at line E. The first problem can be solved by detecting a zero or negative span and rejecting the span during or before feeding it to the span generator (SPPR). .. The second problem is solved by this embodiment by keeping the delined polygon list (DPL) as well as the active polygon list (APL). The Delined Polygon List (DPL) consists of adopting all polygons that are deleted during the processing of the previous scan line. Therefore, the polygon list (DPL) is deleted after the next scan line and the polygon to be deleted related thereto are stored. In this way, the deferred polygon list includes all these polygons that are removed from the active polygon list of the preceding line.

[0064] FIG. 6 is a diagram showing the contents of the frame polygon memory for processing the screen line L. It shows the first and second polygons with a polygon list DPL starting at line O and ending at line L-1 and being deleted at line L. It should be noted that the polygons do not have to start and end on the same line. For example, as long as the first polygon ends at line L-1, the polygon list to be deleted contains only the first polygon and outputs a null pointer instead of being linked to the second polygon. Two more polygons, namely the 3rd and 4th polygons, start at line L and these are the active polygon list APL You can also see that it is added to. In this example, there are only two polygons in the active polygon list, but this is not always necessary and is normal. The reason is that there are still other polygons that started on the preceding line. In this case, the 3rd and 4th polygons are simply added to the list by linking them to the null pointer of the preceding Y bucket.

The high-level algorithm performed by the span generator (SPGN) when performing antialiasing filtering with multiple depictions is as follows; for each Y, a new Y bucket is added to the active polygon list. .. Select the first offset. Generates a span for all polygons in the list of polygons to be deleted for all depictions except the last depiction. Generate spans for all polygons in the active polygon list. Select the next offset to store in the line buffer. Generate a span for all polygons in the list to be deleted. Clear the delimited polygon list. For all polygons in the active list, for the first span of polygons, the polygon is slightly incremented to the next screen line. If it is not the first span of the polygon, a span is generated. Increment the polygon by one screen line. For the final span of polygons, add the polygon to the delined polygon list. Accumulate in the line buffer (LIMINT). Move the line accumulator to the framebuffer (FRMB). The high-level algorithm described above should be suitable for considering the problems that arise in relation to the offset in the y direction in some respects. The statement to "generate a span" associated with the delined polygon list is only executed if the vertical offset Ny + (fractional part of the end line (EDY)) = 1. This is a prerequisite for sending a portion of the polygon to the current scan line.

Also, the high-level algorithms described above are large, mainly in the form of pseudocode, and "selecting a first offset" or "generating a span" is the generation and granting of offsets (depending on the offset given). , A system-based software conceptual command programmed to handle (including determining whether the underlying element causes a "spillover" to occur in the next horizontal row of pixels).

[0067] When two polygons are vertically close together, that is, when they match in an antialiased system, they do not appear on the screen line, which is noticeable for other smooth images. You need to eliminate the error. In the embodiment of the present invention, in order to achieve this, the first line of the polygon is not displayed. This is advantageous because it solves the problem of giving a vertical offset to the first span of a polygon that starts at a small number of vertical positions. The conversion of vertical offsets to xleft and xright, which are horizontal shifts, does not work well in these cases. That is, when the apex of the triangle is the first line, xleft and xright are exchanged to generate a negative span length. However, due to the vertical offset, when the first span of the polygon occurs on the next display line (ie, the screen line), it still needs to be processed. These spans are detected and rejected using the following tests applied to the screen line immediately after the start line (STY).

If (integer part of start line (STY)) = Y-1 and (fractional part of start line (STY)) + Ny = 1, the span is rejected. Combining this test with the condition that the first line of the polygon is not displayed, the following test is given. If the integer part of (start line (STY) + Ny) is Y, the span is rejected. Unlike the Active Polygon List (APL), which gradually evolves as the screen lines are processed, the Deleted Polygon List (DPL) is erased and reconstructed for each screen line. However, since there are no polygons in both the active list and the deferred list at the same time, the same link pointer can be used in the polygon descriptor for both purposes.

[0069] In addition to generating spans from polygons, it is also necessary to vertically increment all parameters of the polygon for each screen. This is done at the same time that the final depiction of each line is generated. Therefore, the first (n-1) depictions are merely accompanied by the occurrence of spans for the current Active Polygon List (APL) and Deleted Polygon List (DPL). Each depiction is performed, stored in the line buffer (LIMINT) and added to the line accumulator (LIMACC). In the final depiction, first a span is generated from the delined polygon list (DPL), and then the delined polygon list (DPL) is erased in preparation for reconstruction. At this time, the active polygon list (APL) is processed. That is, a span is generated and the completed polygon is moved from the active polygon list (APL) to the new delayed polygon list (DPL). Finally, the line accumulator buffer (LIMACC) is accumulated, and the finally obtained antialiasing filtered image line is transmitted from the line accumulator (LIMACC) to the frame buffer.

Another thing to consider regarding polygon processing is that if parameters such as xleft, xright, zleft increase in the vertical direction, the correct value at the integer pixel position is required. Since the polygon start line (STY) value has a fractional part, the first vertical increment is used to match the polygon to the integer y grit. That is, not all screen lines are incremented, but only 1- [the fractional part of the start line (STY)] is incremented.

FIG. 7 is a diagram showing the span generator SPGN shown in FIG. 3 in more detail. As described above, this span generator receives the basic element descriptor PD from the basic element storage PST (shown in Figure 3) and supplies the span descriptor (SD) to the span processor SPPR. The span generator SPGN is also connected to the offset generator OFFGN shown by the dotted line in Fig. 7.

The span generator SPGN includes a vertical incremental circuit VINC and an offset correction circuit 600. This circuit 600 consists of three 2-1 multiplexers 60, 62 and 64, five temporary storage registers 66, 68, 70, 72 and 74, a multiplication circuit 76 and two subtraction circuits 78 and 80. And the adder circuit 82. Sequential control circuits for supplying a selection signal to a multiplexer, supplying a clock signal to a register, and the like are not shown, but are natural to those skilled in the art.

Each basic element descriptor PD supplied to the vertical incremental VINC is: the values of the start line STY and the end line EDY; and the starting values of xleft and xright (left and right edge positions of the base element). It has the slopes δxleft and δxright of these ends with respect to position) and; y (vertical position coordinates). The basic element descriptor also has an initial value of zleft. This value is the value of the depth coordinate z at the left end of the basic element. Partial derivatives δzleft and δz / δx with respect to y are also included. In addition, in a practical example, the descriptor PD contains more parameters to create the coordinate axes u and v (with partial differentiation of x and y), but also the value or surface of the light source used for the shading effect. It can also have parameters such as normal values.

With respect to a given basic element, the vertical incremental VINC uses the slope of the end with respect to y and partial differentiation, updating the start position xleft and end position xright with respect to the current span, while the start line ( The values xleft, xright, zleft, required to form the span descriptor SD sent to the span processor SPPR (Figure 3) in circuit 600, as well as stepping through the line from STY) to the end line (EDY). Supply δz / δx. The values δxleft, δxright and δzleft are also provided to facilitate the addition of offsets Nx, Ny and to ensure that the vertical offset and horizontal edge corrections for zleft are included in the span descriptor SD. To reduce the number of connections in the circuit, these values are supplied sequentially in the order listed in 61 in FIG.

[0075] To include sub-pixel offsets Nx, Ny and correction, switch the multiplexer 60, connect the output terminal of adder 82 to the span processor SPPR, as the SPPR is listed in 63 of FIG. A series of modified values xleft (new), xright (new), etc. can be received. The processing method and occurrence of these values corrected by the offset correction circuit 600 are described.

As already mentioned, the equations defining xleft (new) and xright (new) are as shown below; xleft (new) = xleft + Nx-Nyδxleft, xright (new) = xright + Nx -Nyδxright registers 66 and 68 store the horizontal and vertical offset values Nx and Ny received from the offset generator OFGN, respectively. The terms Ny · δxleft and Nyδ · xright are offset correction (VOC) terms in the water drop direction, and the register 70 temporarily stores the correction (VOC) term at a predetermined time at a predetermined time.

Generate xleft (new) for high (sub-pixel) accuracy, but the decimal (sub-pixel) portion of xleft (new) is ignored by the horizontal increment of the span processor SPPR. .. If some other parameters such as z, u or v are inserted in the base element, this truncation to the integer value x causes problems. For example, the value of z calculated at the start of a row matches the value of xleft very accurately, but not the truncated value. This z error can cause incomplete intersections between basic elements and hidden surface spurious "poke-throughs". Similarly, the truncation error of the constitutive axes u, v can cause a small but visually noticeable discontinuity in the creation of the constitutive pattern.

The horizontal edge correction value HEC (z) is calculated according to the equation: HEC (z) = (1-frac (xleft (new)) · δz / δx and added to zleft. frac (xleft (new)) is the fractional (subpixel) part of the modified horizontal start position xleft (new). The fractional part of the value is generally 4 out of 16-32 bits. It can have a minimum effective bit, which depends on the size of the pixel array and the accuracy of the required sub-pixels, including the vertical offset correction values Ny · δzleft, of zleft (new). The correct equation is: zleft (new) = zleft + (1-frac (xleft (new)) · δz / δx -Ny · δzleft. Using HEC (z), it can be seen that the equation of xleft (new) shown above is similar in its form. Furthermore, the required fractional part of xleft (new) can or can occur at the same time as the integer part of xleft (new). The integer part of xleft (new) has already been requested by the span processor.

The span generator of FIG. 7 has this similarity and the availability of frac (xleft (new)), the same as used to generate xleft (new) and xright (new). It is advantageous to use the circuit practically to modify the zleft. This is achieved by synchronizing the operations of multiplexers 60-64 and storage registers 70-74 to use seven values sequentially at the output terminals of the vertical incremental VINC. These seven operation stages are numbered (1) to (7) and will be described in order below. The sequence of values given by the incremental VINC of these operating stages is shown in 61 of FIG. 7, and the sequence of values supplied to the span processor is shown in 63 of FIG. The values given in cycles 2, 4, 5 and 7 make up the span descriptor SD, but the values in parentheses (cycles 1, 3 and 6) are unnecessary and are ignored by the span processor. The operations in each stage of (1) to (7) are as follows: (1) The offset Ny received from the register 68 via the multiplexer 62 and the δxright received from the incremental VINC are supplied to the input terminal of the multiplexer 76. In this way, the output terminal of the multiplexer 76 transmits VOCs (xright) stored in register 70; in (2) 78, the register from the horizontal offset Nx received from register 66 via multiplexer 64. Subtract the VOC (xright) stored in 70. The difference is added at 82 to the original xright value received from the horizontal incremental VINC; thus the output terminal of the adder 82 transmits the modified xright (new). At least its integer portion of this modified xright (new) is transferred via the multiplexer 60 to the span processor as the first part of the span descriptor SD; (3) δxleft is received from the incremental VINC. VOC (xleft) = Ny · δxleft is stored in register 70; (4) xleft is received from the incremental VINC and xleft (new) is generated by the adder 82 and transferred to the span processor SPPR; at the same time, the fractional part of xleft (new) or frac (xleft (new)) is Stored in register 74; (5) At 80, subtract frac (xleft (new)) from 1 and feed to multiplier 76 via multiplexer 62: multiplier 76 from incrementer VINC δz / δx Is received and the horizontal z end correction value HEC (z) = (1-frac (xleft (new)) · δz / δx is generated. This value is stored in register 72; δz / δx is transferred to the span processor by the multiplexer 60; at (6) 76, Ny and δzleft are multiplied to form the vertical z offset correction value VOC (z), which is in register 70. Remembered; (7) zleft (new) Is generated by subtracting VOC (z) from HEC (z) and adding the value zleft with that received from the incremental VINC. This value is supplied to the span processor (FIG. 3) via the multiplexer 60.

As long as frac (xleft (new)) remains in register 74, horizontal edge corrections and vertical offset corrections are cycled (5) using the appropriate values provided by the incremental VINC. ), (6), (7) can be repeated to apply any number of other parameters (u, v, surface normals, etc.). Components 72,74,62 and 64 and some additional knitting are required for horizontal end correction, and other components (especially multiplexer 76) are of vertical xleft and xright. It is for offset correction. Moreover, one of the factors used in the multiplexer 76 is probably always a 4-5 bit decimal. There is no need to provide a general purpose multiplier for two high precision numbers, each 16-32 bits.

[0081] The present invention is not limited to the examples disclosed herein, and various modifications or changes can be made without changing the gist.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram showing a conventional image display device for displaying a three-dimensional object suitable for performing antialiasing filtering by multiple depiction on a two-dimensional display.

FIG. 2 is a diagram showing the principle of antialiasing filtering by multiple depiction.

FIG. 3 is a diagram showing an example of an apparatus according to the present invention for generating an image of an object in a three-dimensional space of a display on a two-dimensional pixel array.

FIG. 4 is a diagram showing the principle of antialiasing filtering by multiple depiction in the device of FIG.

FIG. 5 is a diagram showing a memory organization in the device shown in FIG.

FIG. 6 is a diagram showing a memory organization in the device shown in FIG.

FIG. 7 is a block diagram showing a part of a span generator in an apparatus according to the present invention.

FIG. 8 is a diagram illustrating a subject of the present invention, and in particular, shows step 1, step 2, and step 16 until an image is displayed according to the present invention.

FIG. 9 also shows steps 17 and 18 until an image is displayed according to the present invention.

FIG. 10 also shows step 19 until an image is displayed according to the present invention.

FIG. 11 shows the operation of a means of recognizing that a basic element is active and a means of recognizing that a basic element may be active for each pixel in a series of pixels. ..

[Code description] 60, 62, 64 Multiplexer 66, 68, 70, 72, 74 Register 76 Multiplication circuit 78, 80 Subtraction circuit 82 Addition circuit 600 Offset correction circuit