Method and apparatus for triangle rasterization with clipping and wire-frame mode support

BACKGROUND

00011. Field

0002Invention relates generally to rasterizers and, more particularly, to accelerating the conversion of primitives defined by vertexes to equivalent images composed of pixel patterns that can be stored and manipulated as sets of bits.

00032. Related Art

0004Raster displays are commonly used in computer graphics systems. These displays store graphics images as a matrix of the smallest picture elements that can be displayed on a screen (“pixels”) with data representing each pixel being stored in a display buffer. This data specifies the display attributes for each pixel on the screen such as the intensity and color of the pixel. An entire image is read from the display buffer and displayed on the screen by sequentially scanning out horizontal rows of pixel data or “scan lines.”

0005Raster display systems commonly use polygons as basic building blocks or “primitives” for drawing more complex images. Triangles are a common basic primitive for polygon drawing systems, since a triangle is the simplest polygon and more complex polygons can be represented as sets of triangles. The process of drawing triangles and other geometric primitives on the screen is known as “rasterization.”

0006An important part of rasterization involves determining which pixels fall within a given triangle. Rasterization systems generally step from pixel to pixel in various ways and determine whether or not to “render,” i.e. to draw into a frame buffer or pixel map, each pixel as part of the triangle. This, in turn, determines how to set the data in the display buffer representing each pixel. Various traversal algorithms have been developed for moving from pixel to pixel in a way such that all pixels within the triangle are covered.

0007Rasterization systems sometimes represent a triangle as a set of three edge-functions. An edge function is a line equation representing a straight line, which serves to subdivide a two-dimensional plane. Edge functions classify each point within the plane as falling into one of three regions: the region “inside” of the triangle, the region “outside” of the triangle or the region representing the line itself. The type of edge function that will be discussed has the property that points “inside” of the triangle have a value greater than zero, points “outside” have a value less than zero, and points exactly on the line have a value of zero. This is shown in <figref idref="DRAWINGS">FIG. 1</figref><i>a</i>. Applied to rasterization systems, the two-dimensional plane is represented by the graphics screen, points are represented by individual pixels, and the edge function serves to subdivide the graphics screen.

0008The union of three edges, or more particularly three half-planes, each of which is specified by edge functions, create triangles. It is possible to define more complex polygons by using Boolean combinations of more than three edges. Since the rasterization of triangles involves determining which pixels to render, a tiebreaker rule is generally applied to pixels that lie exactly on any of the edges to determine whether the pixels are to be considered interior or exterior to the triangle.

0009As shown in <figref idref="DRAWINGS">FIG. 1</figref><i>b</i>, each pixel has associated with it a set of edge variables (e₀, e₁and e₂) which are proportional to the signed distance between the pixel and the three respective edges. The value of each edge variable is determined for a given triangle by evaluating the three edge functions, f₀(x,y), f₁(x,y) and f₂(x,y) for the pixel location. It is important to note that it can be determined whether or not a pixel falls within a triangle by looking at only the signs of e₀, e₁and e₂.

0010In determining which pixels to render within a triangle, typical rasterization systems compute the values of the edge variables (e₀, e₁and e₂) for a given set of three edge functions and a given pixel position, and then use a set of increment values (Δe_outside, Δe_inside, etc.) to determine the edge variable values for adjacent pixels. The rasterization system traverses the triangle, adding the increment values to the current values as a traversal algorithm steps from pixel to pixel.

0011With reference again to <figref idref="DRAWINGS">FIG. 1</figref><i>a</i>, a line is illustrated that is defined by two points: (X,Y) and (X+dX, Y+dY). As noted above, this line can be used to divide the two dimensional space into three regions: all points “outside” of, “inside” of, and exactly on the line. The edge f(x,y) can be defined as f(x,y)=(x−X)dY−(y−Y)dX. This function has the useful property that its value is related to the position of the point (x,y) relative to the edge defined by the points (X,Y) and (X+dX, Y+dY):

0012f(x,y)>0 if (x,y) is “inside”;

0013f(x,y)=0 if (x,y) is exactly on the line; and

0014f(x,y)&lt;0 if (x,y) is “outside”.

0000Existing rasterization systems commonly use this function, since it can be computed incrementally by simple addition: f(x+1,y)=f(x,y)+dY and f(x,y+1)=f(x,y)−dX.

0015A variety of different traversal algorithms are presently used by different rasterization systems in the rendering process. Any algorithm guaranteed to cover all of the pixels within the triangle can be used. For example, some solutions involve following the sides of the triangle while identifying a horizontal or vertical span of pixels therein. Following the sides of the triangle is adequate for the triangle edges, but if the triangle is clipped by a near or far plane, these boundaries are not known explicitly and cannot be followed as easily as the triangle edges. Other methods test individual pixels one at a time. In the recent past multiple pixels are tested in parallel to speed up the rasterization process.

0016Some conventional rasterizers use span-based pixel generation and contain edge and span interpolators based on the well-known Bresenham algorithm. The speed of those rasterizers depends on the interpolation speed. Furthermore, they require a complicated setup process. In most cases such rasterizers interpolate many associated parameters such as color, texture, etc. with appropriate hardware. Increasing the speed of such rasterizers requires a significant increase in the number and complexity of the interpolators, an approach not suitable for commercial products. In the case of clipping support, the structure of such rasterizers is too complex for efficient implementation.

0017Another approach is to use area rasterizers based on a definition of inner and outer pixels, grouped into blocks, with checking corner pixels' equation values to define inner, border and outer blocks. This approach may accelerate the generation of bit-masks of inner blocks, but the border blocks either need to be processed pixel by pixel or need a significant amount of dedicated hardware for processing those pixels in parallel.

0018Accordingly, there is a need for a low-cost high-speed rasterizer having a simple and uniform structure and capable of generating multiple spans per clock cycle.

SUMMARY

0019Invention describes a low-cost high-speed programmable rasterizer. The rasterizer accepts as input a set of functionals representing a triangle, clipping planes and a scissoring box, and produces multiple spans per clock cycle as output. A Loader converts the input set, as expressed in one of a number of general forms, to an expression conforming to a special case format as accepted by a set of Edge Generators. The restricted input format accepted by the Edge Generators contributes to their efficient hardware implementation.

BRIEF DESCRIPTION OF DRAWINGS

0020<figref idref="DRAWINGS">FIG. 1</figref><i>a </i>is a diagram illustrating a half-plane, according to an embodiment of the present invention.

0021<figref idref="DRAWINGS">FIG. 1</figref><i>b </i>is a diagram illustrating a triangle defined by three half-planes, according to an embodiment of the present invention.

0022<figref idref="DRAWINGS">FIG. 1</figref><i>c </i>is a diagram illustrating a polygon defined by a set of half-planes, according to an embodiment of the present invention.

0023<figref idref="DRAWINGS">FIG. 1</figref><i>d </i>is a diagram illustrating an opened half-plane and a closed half-plane, according to an embodiment of the present invention.

0024<figref idref="DRAWINGS">FIG. 2</figref> is a diagram illustrating normals in quadrants and the definition of “right” and “left” half-planes, according to an embodiment of the present invention.

0025<figref idref="DRAWINGS">FIG. 3</figref> is a diagram illustrating a wire-frame triangle, according to an embodiment of the present invention.

0026<figref idref="DRAWINGS">FIG. 4</figref> is a flow diagram illustrating a method for the moving-down process in preparation the Bresenham setup, according to an embodiment of the present invention.

0027<figref idref="DRAWINGS">FIG. 5</figref> is a flow diagram illustrating the foregoing method for the Bresenham setup process, according to an embodiment of the present invention.

0028<figref idref="DRAWINGS">FIG. 6</figref> is a flow diagram illustrating a method for the Bresenham walk process, according to an embodiment of the present invention.

0029<figref idref="DRAWINGS">FIG. 7</figref> is a block diagram illustrating a Span Generator, according to an embodiment of the present invention.

0030<figref idref="DRAWINGS">FIG. 8</figref> is a block diagram illustrating a Loader (without shifters), according to an embodiment of the present invention.

0031<figref idref="DRAWINGS">FIG. 9</figref> is a block diagram illustrating {tilde over (b)} and {tilde over (c)} values wrapping before they are loaded into an Edge Generator, according to an embodiment of the present invention.

0032<figref idref="DRAWINGS">FIG. 10</figref><i>a </i>is a block diagram illustrating an Edge Generator, according to an embodiment of the present invention.

0033<figref idref="DRAWINGS">FIG. 10</figref><i>b </i>is a block diagram illustrating an Edge Generator during the moving-down phase, according to an embodiment of the present invention.

0034<figref idref="DRAWINGS">FIG. 10</figref><i>c </i>is a block diagram illustrating an Edge Generator during the Bresenham setup phase, according to an embodiment of the present invention.

0035<figref idref="DRAWINGS">FIG. 11</figref><i>a </i>is a block diagram illustrating a Scissoring Box origin, according to an embodiment of the present invention.

0036<figref idref="DRAWINGS">FIG. 11</figref><i>b </i>is a block diagram illustrating a Scissoring Box, according to an embodiment of the present invention.

DETAILED DESCRIPTION

0000The following servers as a glossary of terms as defined herein:

0000<ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0037"> Triangle Intersection of three half-planes, wherein each half-plane is “open” or “closed”. </li><li id="ul0001-0002" num="0038"> Polygon Intersection of a triangle and the clipping half-planes (shown in <figref idref="DRAWINGS">FIG. 1</figref><i>c</i>), wherein each clipping half-plane is “open” or “closed”. </li><li id="ul0001-0003" num="0039"> “Open” half-plane A half-plane which satisfies the inequality (as shown in <figref idref="DRAWINGS">FIG. 1</figref><i>d</i>) <br /><i>a·x+b·y+c></i>0  (1)</li><li id="ul0001-0004" num="0040"> “Closed” half-plane A half-plane which satisfies the inequality (as shown in <figref idref="DRAWINGS">FIG. 1</figref><i>d</i>) <br /><i>a·x+b·y+c≧</i>0  (2)</li><li id="ul0001-0005" num="0041"> Half-plane functional An expression describing a half-plane or a line <br /><i>f</i>(<i>x, y</i>)=<i>a·x+b·y+c</i>  (3)</li><li id="ul0001-0006" num="0042"> “Right” half-plane A half-plane described by a functional <br /><i>f</i>(<i>x, y</i>)=<i>a·x+b·y+c</i>, where a<0<img file="US2005134603A1_D0001.tif" />a=0<img file="US2005134603A1_D0002.tif" />b<0  (4)</li><li id="ul0001-0007" num="0043"> “Left” half-plane A half-plane described by a functional <br /><i>f</i>(<i>x, y</i>)=<i>a·x+b·y+c</i>, where a>0<img file="US2005134603A1_D0003.tif" />a=0<img file="US2005134603A1_D0004.tif" />b>0  (5)</li><li id="ul0001-0008" num="0044"> Scissoring box A rectangle representing a part of the view-port where polygon are actually drawn. </li><li id="ul0001-0009" num="0045"> Bounding box A smallest rectangle to fit the intersection of a triangle and the scissoring box </li><li id="ul0001-0010" num="0046"> Extended bounding box A bounding box, which horizontal size is the smallest power of 2, which is greater or equal to the size of the bounding box </li><li id="ul0001-0011" num="0047"> w The horizontal size of the bounding box <br /><i>w=x</i>_max<i>−x</i>_min  (6)</li><li id="ul0001-0012" num="0048"> W The horizontal size of the extended bounding box, for which it could be expressed as: <br />W=2^{ceiling (log}^{<sub2>2 </sub2>}^w)  (7)</li><li id="ul0001-0013" num="0049"> x Representation of the integer horizontal coordinate inside the bounding box expressed in current grid units </li><li id="ul0001-0014" num="0050"> y Representation of the integer vertical coordinate inside the bounding box expressed in current grid units </li><li id="ul0001-0015" num="0051"> x_minRepresentation of the minimal horizontal coordinate of the bounding box </li><li id="ul0001-0016" num="0052"> y_minRepresentation of the minimal vertical coordinate of the bounding box </li><li id="ul0001-0017" num="0053"> a, b, c Integer coefficients of the functional of the half-plane </li><li id="ul0001-0018" num="0054"> ã, {tilde over (b)}, {tilde over (c)} Integer coefficients of the functional transformed to the bounding box relative coordinates according to the special case of the edge functional </li><li id="ul0001-0019" num="0055"> “Edge” of a “left” half-plane The set of points (x_i, y_i) satisfying the expression <maths id="MATH-US-00001" num="1"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><mrow><munder><mi>min</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mi>x</mi><mo>:</mo><mrow><mrow><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><msub><mi>y</mi><mi>i</mi></msub></mrow><mo>+</mo><mi>c</mi></mrow><mo>≥</mo><mn>0</mn></mrow></mrow><mo>}</mo></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext></mtext></mstyle><mo>⁢</mo><mrow><mrow><mrow><mrow><mi>where</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>a</mi></mrow><mo>></mo><mrow><mn>0</mn><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>and</mi><mo>⁢</mo><mrow><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mstyle><mtext> </mtext></mstyle></mrow><mo>⁢</mo><mi>i</mi></mrow></mrow><mo>=</mo><mn>0</mn></mrow><mo>,</mo><mn>1</mn><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>,</mo><mrow><msub><mi>y</mi><mi>max</mi></msub><mo>-</mo><msub><mi>y</mi><mi>min</mi></msub></mrow><mo>,</mo><mi>or</mi></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>8</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mrow><munder><mi>min</mi><mrow><mi>y</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mi>y</mi><mo>:</mo><mrow><mrow><mrow><mi>a</mi><mo>·</mo><msub><mi>x</mi><mi>i</mi></msub></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi></mrow><mo>≥</mo><mn>0</mn></mrow></mrow><mo>}</mo></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext></mtext></mstyle><mo>⁢</mo><mrow><mrow><mrow><mi>where</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>a</mi></mrow><mo>=</mo><mrow><mrow><mrow><mn>0</mn><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>and</mi><mo>⁢</mo><mrow><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mstyle><mtext> </mtext></mstyle></mrow><mo>⁢</mo><mi>b</mi></mrow><mo>></mo><mrow><mn>0</mn><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>and</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>i</mi></mrow></mrow><mo>=</mo><mn>0</mn></mrow></mrow><mo>,</mo><mn>1</mn><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>,</mo><mrow><msub><mi>x</mi><mi>max</mi></msub><mo>-</mo><msub><mi>x</mi><mi>min</mi></msub></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>9</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths></li><li id="ul0001-0020" num="0056"> “Left” edge “Edge” of a “left” half-plane </li><li id="ul0001-0021" num="0057"> “Edge” of a “right” half-plane The set of points (x_i, y_i) satisfying the expression <maths id="MATH-US-00002" num="2"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><mrow><munder><mi>max</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mi>x</mi><mo>:</mo><mrow><mrow><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><msub><mi>y</mi><mi>i</mi></msub></mrow><mo>+</mo><mi>c</mi></mrow><mo>></mo><mn>0</mn></mrow></mrow><mo>}</mo></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext></mtext></mstyle><mo>⁢</mo><mrow><mrow><mrow><mrow><mi>where</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>a</mi></mrow><mo><</mo><mrow><mn>0</mn><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>and</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>i</mi></mrow></mrow><mo>=</mo><mn>0</mn></mrow><mo>,</mo><mn>1</mn><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>,</mo><mrow><msub><mi>y</mi><mi>max</mi></msub><mo>-</mo><msub><mi>y</mi><mi>min</mi></msub></mrow><mo>,</mo><mi>or</mi></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>10</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mrow><munder><mi>max</mi><mrow><mi>y</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mi>y</mi><mo>:</mo><mrow><mrow><mrow><mi>a</mi><mo>·</mo><msub><mi>x</mi><mi>i</mi></msub></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi></mrow><mo>></mo><mn>0</mn></mrow></mrow><mo>}</mo></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext></mtext></mstyle><mo>⁢</mo><mrow><mrow><mrow><mi>where</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>a</mi></mrow><mo>=</mo><mrow><mrow><mrow><mn>0</mn><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>and</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>b</mi></mrow><mo><</mo><mrow><mn>0</mn><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>and</mi><mo>⁢</mo><mrow><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mstyle><mtext> </mtext></mstyle></mrow><mo>⁢</mo><mi>i</mi></mrow></mrow><mo>=</mo><mn>0</mn></mrow></mrow><mo>,</mo><mn>1</mn><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>,</mo><mrow><msub><mi>x</mi><mi>max</mi></msub><mo>-</mo><msub><mi>x</mi><mi>min</mi></msub></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>11</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths></li><li id="ul0001-0022" num="0058"> “Right” edge “Edge” of a “right” half-plane </li><li id="ul0001-0023" num="0059"> “Edge” of a half-plane If the half-plane is a “right” half-plane, then the “edge” of the “right” half-plane, otherwise the “edge” of the “left” half-plane </li><li id="ul0001-0024" num="0060"> “Edge” of a polygon “Edge” of one of the half-planes forming the polygon </li><li id="ul0001-0025" num="0061"> Wire-frame A disjunction of three parallelograms based on the three edges of the triangle </li><li id="ul0001-0026" num="0062"> “Width” of a wire-frame Integer number, which expresses in the current grid units projection of the width of the wire-frame line to a minor direction axis of the current grid. </li><li id="ul0001-0027" num="0063"> d The width of the wire-frame line </li><li id="ul0001-0028" num="0064"> Edge Generator EG State machine to generate an edge of a half-plane, which computes a sequence of x coordinate values in order of incrementing y coordinate associated with one of the functionals </li><li id="ul0001-0029" num="0065"> Loader Pipelined device to transform input functionals to the form, which is convenient for EG to work </li><li id="ul0001-0030" num="0066"> Sorter Pipelined device to compute the intersection of half-planes, edges of which are generated by several EG </li><li id="ul0001-0031" num="0067"> Span buffer Temporary storage for spans before tiling </li><li id="ul0001-0032" num="0068"> Tiling Process of making tiles </li><li id="ul0001-0033" num="0069"> Tile Set of 8×8 pixels, aligned by x and y coordinates </li><li id="ul0001-0034" num="0070"> Tile Generator TG State machine to produce tiles from spans in Span Buffer </li><li id="ul0001-0035" num="0071"> Moving Down Phase of the EG when EG is adding {tilde over (b)} value to the functional value each clock until the functional value is positive </li><li id="ul0001-0036" num="0072"> SHORT Data type to define signed 22-bit numbers </li><li id="ul0001-0037" num="0073"> LONG Data type to define signed 42-bit numbers </li><li id="ul0001-0038" num="0074"> BITN Data type to define unsigned N-bit numbers </li><li id="ul0001-0039" num="0075"> BITNS Data type to define signed N-bit numbers <br /> Triangle Edge Definition <br /> We assume that triangle edge functions are defined as <maths id="MATH-US-00003" num="3"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><msub><mi>F</mi><mi>i</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mrow><msub><mi>a</mi><mi>i</mi></msub><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>·</mo><mi>y</mi></mrow><mo>+</mo><msub><mi>c</mi><mi>i</mi></msub></mrow><mo>=</mo><mrow><mi>det</mi><mo>⁡</mo><mrow><mo>(</mo><mtable><mtr><mtd><msub><mi>x</mi><mi>j</mi></msub></mtd><mtd><msub><mi>x</mi><mi>k</mi></msub></mtd><mtd><mi>x</mi></mtd></mtr><mtr><mtd><msub><mi>y</mi><mi>j</mi></msub></mtd><mtd><msub><mi>y</mi><mi>k</mi></msub></mtd><mtd><mi>y</mi></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable><mo>)</mo></mrow></mrow></mrow></mrow><mo>,</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mo>,</mo><mn>1</mn><mo>,</mo><mn>2</mn></mrow></mtd><mtd><mrow><mo>(</mo><mn>12</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> wherein j=(i+1) mod 3, k=(i+2) mod 3 and [x_i, y_i], i=0, 1, 2 are triangle vertex coordinates in a standard window coordinate system expressed in the units of the main grid (see above). If the functionals are set up as “implicit” clipping functionals, they should be converted to this format as well. <br /> End Points <br /> For a right edge and a given span y_ithe interpolator should produce x_isuch that <maths id="MATH-US-00004" num="4"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><mrow><munder><mi>max</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mi>x</mi><mo>:</mo><mrow><mrow><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><msub><mi>y</mi><mi>i</mi></msub></mrow><mo>+</mo><mi>c</mi></mrow><mo>></mo><mn>0</mn></mrow></mrow><mo>}</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>13</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> such an x_ipoint for a≠0 is the last (inclusive) point of the span. <br /> For a left edge and a given span y_ithe interpolator should produce x_isuch that <maths id="MATH-US-00005" num="5"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><mrow><munder><mi>min</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mi>x</mi><mo>:</mo><mrow><mrow><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><msub><mi>y</mi><mi>i</mi></msub></mrow><mo>+</mo><mi>c</mi></mrow><mo>≥</mo><mn>0</mn></mrow></mrow><mo>}</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>14</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> such an x_ipoint for a≠0 is the first (inclusive) point of the span. <br /> If we have a=0 then the edge (left or right) is horizontal, thus the end points of the span for the functional will be x₀=0 and x₀=W. <br /> General Cases for the Edge Generator </li></ul>

0076In general case we have opened right half-planes and closed left half-planes, classified as follows, also shown in <figref idref="DRAWINGS">FIG. 2</figref>: <tables id="TABLE-US-00001" num="1"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="5"><colspec colname="1" colwidth="56PT" align="center" /><colspec colname="2" colwidth="42PT" align="left" /><colspec colname="3" colwidth="63PT" align="center" /><colspec colname="4" colwidth="14PT" align="center" /><colspec colname="5" colwidth="42PT" align="center" /><thead><row><entry /></row><row><entry namest="1" nameend="5" align="center" rowsep="1" /></row><row><entry /><entry /><entry>Normal</entry><entry /><entry /></row><row><entry>Case #</entry><entry>Half-plane</entry><entry>quadrant</entry><entry>A</entry><entry>B</entry></row><row><entry namest="1" nameend="5" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>1</entry><entry>Right open</entry><entry>II</entry><entry><0</entry><entry>≧0</entry></row><row><entry>2</entry><entry>Right open</entry><entry>III</entry><entry><0</entry><entry><0</entry></row><row><entry>3</entry><entry>Right open</entry><entry>III</entry><entry>=0</entry><entry><0</entry></row><row><entry>4</entry><entry>Left closed</entry><entry>IV</entry><entry>>0</entry><entry>≦0</entry></row><row><entry>5</entry><entry>Left closed</entry><entry>I</entry><entry>>0</entry><entry>>0</entry></row><row><entry>6</entry><entry>Left closed</entry><entry>I</entry><entry>=0</entry><entry>>0</entry></row><row><entry>7</entry><entry>Whole</entry><entry>n/a</entry><entry>=0</entry><entry>=0</entry></row><row><entry /><entry>bounding</entry></row><row><entry /><entry>box is</entry></row><row><entry /><entry>inside or</entry></row><row><entry /><entry>outside the</entry></row><row><entry /><entry>plane</entry></row><row><entry namest="1" nameend="5" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> A Loader <b>102</b> transforms a functional given according to a general case into a functional given by the special case, with the special case and the general cases described as follows:

0077Special Case for the Edge Generator <br /> The Edge Generator <b>103</b> (shown in <figref idref="DRAWINGS">FIG. 7</figref>) operates within a discrete space with integer coefficients. To simplify the work of the Edge Generator <b>103</b>, the Edge Generator <b>103</b> is designed to draw an edge of a closed right half-plane (i.e. a right edge), whose normal is located in quadrant II since we have a&lt;0 and b≧0. For an edge with a&lt;0 we have: <maths id="MATH-US-00006" num="6"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>f</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi></mrow><mo>=</mo><mrow><mrow><mn>0</mn><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⇒</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>x</mi></mrow><mo>=</mo><mrow><mrow><mrow><mo>-</mo><mfrac><mi>b</mi><mi>a</mi></mfrac></mrow><mo>·</mo><mi>y</mi></mrow><mo>-</mo><mfrac><mi>c</mi><mi>a</mi></mfrac></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>15</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> from which we calculate <maths id="MATH-US-00007" num="7"><math overflow="scroll"><mtable><mtr><mtd><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mi /><mo>⁢</mo><mrow><mi>floor</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mo>(</mo><mrow><mo>-</mo><mfrac><mi>c</mi><mi>a</mi></mfrac></mrow><mo>)</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mi>Δ</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>x</mi></mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mi>floor</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mo>(</mo><mrow><mo>-</mo><mfrac><mi>b</mi><mi>a</mi></mfrac></mrow><mo>)</mo></mrow></mrow></mrow></mtd></mtr></mtable></mtd><mtd><mrow><mo>(</mo><mn>16</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

0078The Edge Generator <b>103</b> works in a vertical stripe [x_min, x_max] using an x coordinate relative to x_minwhich satisfies 0≦x≦W, wherein W=2^mis the size of the extended bounding box. As described below, the setup division starts as soon as the functional changes sign from negative to positive and f(0, y)≧0, hence resulting in x₀≧0. Also, Δx≧0 according to the above assumption that a&lt;0 and b≧0.

0079It is possible that the value of the functional ƒ is negative when the Edge Generator <b>103</b> starts operating (i.e. when y=0). In this case, the x₀value could be negative and hence does not need to be computed, since we are only interested in the exact x₀values which satisfy 0≦x₀≦W.

0080The completion of the moving-down process is followed by calculating x₀=floor(−c/a) and Δx=floor(−b/a) using a division process performed by the divider. Since the divider starts operating when the functional value changes its sign from negative to positive, we can assume that at the start of the division process ƒ(0, y)≧0. To calculate x₀and Δx the divider operates under the assumption that <br />a&lt;0, b≧0  (17)<br /> and uses a simple adder-based divider. Since a&lt;0, we take <br /><i>c</i>_i−(−<i>a</i>_i)≡<i>c</i>_i<i>+a</i>_i<br /><i>b</i>_i−(−<i>a</i>_i)≡<i>b</i>_i<i>+a</i>_i  (18)<br /> into consideration start with <br /><i>c</i>₀<i>=f</i>(<i>x, y</i>), <i>a</i>₀<i>=ã</i>·2^m+1<i>, b</i>₀<i>={tilde over (b)}, x</i>₀₀<i>=Δx</i>₀=0  (19)<br /> and then iterate as follows: <maths id="MATH-US-00008" num="8"><math overflow="scroll"><mtable><mtr><mtd><mtable><mtr><mtd><mrow><msub><mi>c</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mi /><mo>⁢</mo><mrow><msub><mi>c</mi><mi>i</mi></msub><mo>+</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><msub><mi>a</mi><mi>i</mi></msub><mo>,</mo><mrow><mrow><msub><mi>c</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mi>i</mi></msub></mrow><mo>≥</mo><mn>0</mn></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mn>0</mn><mo>,</mo><mrow><mrow><msub><mi>c</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mi>i</mi></msub></mrow><mo>&lt;</mo><mn>0</mn></mrow></mrow></mtd></mtr></mtable></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>x</mi><mrow><mrow><mn>0</mn><mo>⁢</mo><mi>i</mi></mrow><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mi /><mo>⁢</mo><mrow><mrow><msub><mi>x</mi><mrow><mn>0</mn><mo>⁢</mo><mi>i</mi></mrow></msub><mo>·</mo><mn>2</mn></mrow><mo>+</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mn>1</mn><mo>,</mo><mrow><mrow><msub><mi>c</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mi>i</mi></msub></mrow><mo>≥</mo><mn>0</mn></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mn>0</mn><mo>,</mo><mrow><mrow><msub><mi>c</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mi>i</mi></msub></mrow><mo>&lt;</mo><mn>0</mn></mrow></mrow></mtd></mtr></mtable></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>b</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mi /><mo>⁢</mo><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>+</mo><mrow><mo>{</mo><mrow><mtable><mtr><mtd><mrow><msub><mi>a</mi><mi>i</mi></msub><mo>,</mo><mrow><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mi>i</mi></msub></mrow><mo>≥</mo><mn>0</mn></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mn>0</mn><mo>,</mo><mrow><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mi>i</mi></msub></mrow><mo>&lt;</mo><mn>0</mn></mrow></mrow></mtd></mtr></mtable><mo>,</mo><mrow><mi>i</mi><mo>=</mo><mn>0</mn></mrow><mo>,</mo><mn>1</mn><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>,</mo><mi>m</mi></mrow></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mi>Δ</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><msub><mi>x</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub></mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mrow><mi>Δ</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>·</mo><mn>2</mn></mrow></mrow><mo>+</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mn>1</mn><mo>,</mo><mrow><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mi>i</mi></msub></mrow><mo>≥</mo><mn>0</mn></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mn>0</mn><mo>,</mo><mrow><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mi>i</mi></msub></mrow><mo>&lt;</mo><mn>0</mn></mrow></mrow></mtd></mtr></mtable></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>a</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mi /><mo>⁢</mo><mfrac><msub><mi>a</mi><mi>i</mi></msub><mn>2</mn></mfrac></mrow></mtd></mtr></mtable></mtd><mtd><mrow><mo>(</mo><mn>20</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> describing the fully functional step-by-step integer divider.

0081Case 1: Right Open Half-plane and A&lt;0<img file="US2005134603A1_D0005.tif" />B≧0

0000The difference between this case and the special case is only that the half-plane is open.

0082Therefore we need to find <maths id="MATH-US-00009" num="9"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><munder><mi>max</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mi>x</mi><mo>:</mo><mrow><mrow><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi></mrow><mo>></mo><mn>0</mn></mrow></mrow><mo>}</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>21</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> Since the coefficients and variables are integer, <maths id="MATH-US-00010" num="10"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><munder><mi>max</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mi>x</mi><mo>:</mo><mrow><mrow><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi><mo>-</mo><mn>1</mn></mrow><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>≥</mo><mn>0</mn></mrow></mrow><mo>}</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>22</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> and therefore <maths id="MATH-US-00011" num="11"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><munder><mi>max</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mi>x</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mover><mi>c</mi><mo>~</mo></mover></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow><mo>,</mo><mrow><mover><mi>c</mi><mo>~</mo></mover><mo>=</mo><mrow><mi>c</mi><mo>-</mo><mn>1</mn></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>23</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> which reduces this case to the special case. Thus, in this case the Loader <b>102</b> (shown in <figref idref="DRAWINGS">FIG. 7</figref>) subtracts 1 from c before starting the Edge Generator <b>103</b>.

0083Case 2: Right Open Half-plane and A<0<img file="US2005134603A1_D0006.tif" />B<0 <br /> Again we need to find <maths id="MATH-US-00012" num="12"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><munder><mi>max</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mi>x</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi></mrow><mo>></mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>24</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> Substituting x=W−{tilde over (x)} we have <maths id="MATH-US-00013" num="13"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>W</mi><mo>-</mo><mrow><munder><mi>min</mi><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle></mrow><mo>-</mo><mrow><mi>a</mi><mo>·</mo><mover><mi>x</mi><mo>~</mo></mover></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi><mo>+</mo><mrow><mi>W</mi><mo>·</mo><mi>a</mi></mrow></mrow><mo>></mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>25</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> and computing maximum in the complimentary semi-plane <maths id="MATH-US-00014" num="14"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>W</mi><mo>-</mo><mrow><munder><mi>max</mi><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle></mrow><mo>-</mo><mrow><mi>a</mi><mo>·</mo><mover><mi>x</mi><mo>~</mo></mover></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi><mo>+</mo><mrow><mi>W</mi><mo>·</mo><mi>a</mi></mrow></mrow><mo>≤</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow><mo>-</mo><mn>1</mn></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>26</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> and rewriting the constraint and collecting appropriate terms we have <maths id="MATH-US-00015" num="15"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>W</mi><mo>-</mo><mn>1</mn><mo>-</mo><mrow><munder><mi>max</mi><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mi>a</mi><mo>·</mo><mover><mi>x</mi><mo>~</mo></mover></mrow></mrow><mo>-</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>-</mo><mi>c</mi><mo>-</mo><mrow><mi>W</mi><mo>·</mo><mi>a</mi></mrow></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>27</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> and finally <maths id="MATH-US-00016" num="16"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>W</mi><mo>-</mo><mn>1</mn><mo>-</mo><mrow><munder><mi>max</mi><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mover><mi>a</mi><mo>~</mo></mover><mo>·</mo><mover><mi>x</mi><mo>~</mo></mover></mrow></mrow><mo>+</mo><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mover><mi>c</mi><mo>~</mo></mover></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>28</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> where <br /><i>ã=a, {tilde over (b)}=−b, {tilde over (c)}=−c−W·a</i>  (29)<br /> which reduces this case to the special case.

0084Case 3: Right Open Half-plane and A=0<img file="US2005134603A1_D0007.tif" />B&lt;0 <br /> Whereas in the previous case for a&lt;0<img file="US2005134603A1_D0008.tif" />b&lt;0 we had <maths id="MATH-US-00017" num="17"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>W</mi><mo>-</mo><mn>1</mn><mo>-</mo><mrow><munder><mi>max</mi><mrow><mover><mi>x</mi><mover><mo>~</mo><mo>~</mo></mover></mover><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mover><mi>a</mi><mo>~</mo></mover><mo>·</mo><mover><mi>x</mi><mo>~</mo></mover></mrow></mrow><mo>+</mo><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mover><mi>c</mi><mo>~</mo></mover></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>30</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> wherein <br /><i>ã=a, {tilde over (b)}=−b, {tilde over (c)}=−c−W·a</i>  (31)<br /> In this case we have a=0, which means that (30) does not have a maximum. However the division algorithm described above (16) is stable in the case of a zero denominator, producing in this case <br /><i>{tilde over (x)}</i>₀=2<i>·W</i>−1<img file="US2005134603A1_D0009.tif" /><i>x</i>₀<i>=W</i>−1<i>−{tilde over (x)}</i>₀<i>=−W</i>  (32)<br /> after the completion of the division algorithm, indicating that the x value reaches the other edge of the bounding box and that the Edge Generator <b>103</b> will draw a horizontal line.

0085Case 4: Left Closed Half-plane and A>0<img file="US2005134603A1_D0010.tif" />B≦0 <br /> Again we want to find <maths id="MATH-US-00018" num="18"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><munder><mi>max</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mi>x</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>33</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> or equivalently <maths id="MATH-US-00019" num="19"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><munder><mi>min</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mi>x</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle></mrow><mo>-</mo><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow><mo>-</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>-</mo><mi>c</mi></mrow><mo>≤</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>34</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> Substituting a=−ã, b=−{tilde over (b)} and computing the maximum in the complimentary semi-plane, we have <maths id="MATH-US-00020" num="20"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mrow><munder><mi>max</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mi>x</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mover><mi>a</mi><mo>~</mo></mover><mo>·</mo><mi>x</mi></mrow></mrow><mo>+</mo><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><mi>y</mi></mrow><mo>-</mo><mi>c</mi></mrow><mo>></mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow><mo>+</mo><mn>1</mn></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>35</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> Since the coefficients and variables are integer, we have <maths id="MATH-US-00021" num="21"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mrow><munder><mi>max</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mi>x</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mover><mi>a</mi><mo>~</mo></mover><mo>·</mo><mi>x</mi></mrow></mrow><mo>+</mo><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><mi>y</mi></mrow><mo>-</mo><mi>c</mi><mo>-</mo><mn>1</mn></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow><mo>+</mo><mn>1</mn></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>36</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> and therefore <maths id="MATH-US-00022" num="22"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mrow><munder><mi>max</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mi>x</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mover><mi>a</mi><mo>~</mo></mover><mo>·</mo><mi>x</mi></mrow></mrow><mo>+</mo><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mover><mi>c</mi><mo>~</mo></mover></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow><mo>+</mo><mn>1</mn></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>37</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> wherein <br /><i>ã=−a, {tilde over (b)}=−b, {tilde over (c)}=−c−</i>1  (38)<br /> reducing to the special case.

0086Case 5: Left Closed Half-plane and A>0<img file="US2005134603A1_D0011.tif" />B>0 <br /> We want to find <maths id="MATH-US-00023" num="23"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><munder><mi>min</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mi>x</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>39</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> Substituting x=W−{tilde over (x)} we have <maths id="MATH-US-00024" num="24"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>W</mi><mo>-</mo><mrow><munder><mi>max</mi><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle></mrow><mo>-</mo><mrow><mi>a</mi><mo>·</mo><mover><mi>x</mi><mo>~</mo></mover></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi><mo>+</mo><mrow><mi>W</mi><mo>·</mo><mi>a</mi></mrow></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>40</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> and therefore <maths id="MATH-US-00025" num="25"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>W</mi><mo>-</mo><mrow><munder><mi>max</mi><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mover><mi>a</mi><mo>~</mo></mover><mo>·</mo><mover><mi>x</mi><mo>~</mo></mover></mrow></mrow><mo>+</mo><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mover><mi>c</mi><mo>~</mo></mover></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>41</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> wherein <br /><i>ã=−a, {tilde over (b)}=b, {tilde over (c)}=c+W·a</i>  (42)<br /> reducing to the special case.

0087Case 6: Left Closed Half-plane and A=0<img file="US2005134603A1_D0012.tif" />B>0 <br /> In the previous case for a>0<img file="US2005134603A1_D0013.tif" />b>0 we had <maths id="MATH-US-00026" num="26"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>W</mi><mo>-</mo><mrow><munder><mi>max</mi><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mover><mi>a</mi><mo>~</mo></mover><mo>·</mo><mover><mi>x</mi><mo>~</mo></mover></mrow></mrow><mo>+</mo><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mover><mi>c</mi><mo>~</mo></mover></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>43</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> wherein <br /><i>ã=−a, {tilde over (b)}=b, ã=c+W·a</i>  (44)<br /> In this case we have a=0 resulting in (43) having no maximum. However, the division algorithm described above (16) is again stable in this case of zero denominator, resulting in <br /><i>{tilde over (x)}</i>₀=2<i>·W</i>−1<img file="US2005134603A1_D0014.tif" /><i>x</i>₀<i>=W</i>−1<i>−{tilde over (x)}</i>₀=0  (45)<br /> after the division algorithm completes, indicating that the x value reaches the other edge of the bounding box and that the Edge Generator <b>103</b> will draw a horizontal line.

0088Case 7: The Plane of the Polygon is Parallel to the Clipping Plane and A=0<img file="US2005134603A1_D0015.tif" />B=0

0089This case indicates that the plane of the polygon is parallel to one of the clipping planes. In this case the sign of c determines whether the plane of the polygon is visible or not. If c&lt;0, then the entire bounding box is invisible. The Edge Generator <b>103</b> will function normally, but all spans will be marked as being “outside the bounding box”. Otherwise, all spans will be marked as being “inside the bounding box”.

0000Wire-frame Support

0090The next two cases involve wire-frame support. <figref idref="DRAWINGS">FIG. 3</figref> is a diagram illustrating a wire-frame of a triangle, according to one embodiment of the present invention. The wire-frame of a triangle is a disjunction of three parallelograms, each of which represents an edge of the triangle. We assume that a wire-frame to be drawn comprises a one-pixel line width. The wire-frame support reliably works in the following conditions: (a) no over-sampling (i.e. the current grid is the same as the pixel grid), and (b) the width of the wire-frame is one unit of the current grid (i.e. one pixel according to the foregoing assumption). If the wire-frame support works for any other mode (either over-sampling is on or the width is more than one) we consider the availability of those modes a bonus, which we suppose to get almost for free.

0091We restrict the wire-frame mode as not comprising any clipping functionals besides a frustum. This means that a wire-framed triangle comprises (a) three functionals representing the triangle edges and (b) the bounding box.

0000A wire-framed triangle comprises three parameters for drawing:

0000<ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0092"> Width The width of an edge, expressed as the number of pixels to be covered by a triangle edge in the minor direction. A Span Generator <b>101</b> (shown in <figref idref="DRAWINGS">FIG. 7</figref>) correctly processes a wire-frame with a one-pixel width. </li><li id="ul0002-0002" num="0093"> Edge flag Draw-edge flag (one bit per edge). Each edge of the triangle is equipped with a draw-edge flag, indicating whether the edge is to be drawn. </li><li id="ul0002-0003" num="0094"> Extension Bounding box extension. If the draw-edge flag is set for an edge, the bounding box is extended by half of the wire-frame line width. <br /> The wire-frame is an intersection of the “tight” bounding box and an exclusive intersection of two closed-edges triangles. Since the original functionals specify the center-line of each edge of the wire-framed triangle, the functionals for the wire-frame are offset by half of the wire-frame width in the “minor” direction, i.e. in the direction of that coordinate whose coefficient in the functional has a smaller absolute value: </li></ul>

0095Case 8: Right Closed Half-plane for Wire-frame and A&lt;0<img file="US2005134603A1_D0016.tif" />B≧0 <br /> There is no difference between this case and the special case, so we need to make no corrections for this case <maths id="MATH-US-00027" num="27"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><munder><mi>max</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mi>x</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>46</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths>

0096Case 9: Right Closed Half-plane for Wire-frame and A≦0<img file="US2005134603A1_D0017.tif" />B<0 <br /> Again we need to find <maths id="MATH-US-00028" num="28"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><munder><mi>max</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mi>x</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>47</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> Substituting x=W−{tilde over (x)} <maths id="MATH-US-00029" num="29"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>W</mi><mo>-</mo><mrow><munder><mi>min</mi><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle></mrow><mo>-</mo><mrow><mi>a</mi><mo>·</mo><mover><mi>x</mi><mo>~</mo></mover></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi><mo>+</mo><mrow><mi>W</mi><mo>·</mo><mi>a</mi></mrow></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>48</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> and computing maximum in the complimentary semi-plane <maths id="MATH-US-00030" num="30"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>W</mi><mo>-</mo><mrow><munder><mi>max</mi><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle></mrow><mo>-</mo><mrow><mi>a</mi><mo>·</mo><mover><mi>x</mi><mo>~</mo></mover></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi><mo>+</mo><mrow><mi>W</mi><mo>·</mo><mi>a</mi></mrow></mrow><mo><</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow><mo>-</mo><mn>1</mn></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>49</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> and rewriting the constraint and collecting appropriate terms we results in <maths id="MATH-US-00031" num="31"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>W</mi><mo>-</mo><mn>1</mn><mo>-</mo><mrow><munder><mi>max</mi><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mi>a</mi><mo>·</mo><mover><mi>x</mi><mo>~</mo></mover></mrow></mrow><mo>-</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>-</mo><mi>c</mi><mo>-</mo><mrow><mi>W</mi><mo>·</mo><mi>a</mi></mrow></mrow><mo>></mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>50</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> and finally <maths id="MATH-US-00032" num="32"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>W</mi><mo>-</mo><mn>1</mn><mo>-</mo><mrow><munder><mi>max</mi><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mover><mi>a</mi><mo>~</mo></mover><mo>·</mo><mover><mi>x</mi><mo>~</mo></mover></mrow></mrow><mo>+</mo><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mover><mi>c</mi><mo>~</mo></mover></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>51</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> wherein <br /><i>ã=a, {tilde over (b)}=−b, {tilde over (c)}=−c−W·a</i>−1  (52)<br /> reducing once again to the special case. <br /> The Loader

0097The Edge Generator <b>103</b> works under the assumption of the special case described above, allowing significant reduction of its hardware and resulting in faster operation. The Loader <b>102</b> is the element which transforms a general case to the special case, converting an input functional described by a general case into a form expected by the special case, thereby allowing the Edge Generator <b>103</b> to compute edge values correctly and efficiently.

0098The Loader <b>102</b> accepts as inputs a functional and a bounding box offset, and produces a set of coefficients a, b, and c according to the special case for the Edge Generator <b>103</b>.

0000We have: <br /><i>F</i>(<i>x, y</i>)=<i>a·x′+b·y′+c′</i><br />X∈[x_min, x_max], [y_min, y_max]  (53)<br /> Since the functional coefficients are expressed in the main grid and the x, y coordinates are expressed in the over-sampling grid, we have a grid ratio of s=2^{6+[0, 1, 2]} and will convert the c′ value to the over-sampling grid. The particular conversion depends on the type of the half-plane at hand. For a closed half-plane the conversion is as follows: <maths id="MATH-US-00033" num="33"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>f</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mrow><mrow><mi>a</mi><mo>·</mo><msup><mi>x</mi><mi>′</mi></msup></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><msup><mi>y</mi><mi>′</mi></msup></mrow><mo>+</mo><msup><mi>c</mi><mi>′</mi></msup></mrow><mo>≥</mo><mn>0</mn></mrow><mo>⇒</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>54</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mrow><mrow><mrow><mi>a</mi><mo>·</mo><mi>s</mi><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>s</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><msup><mi>c</mi><mi>′</mi></msup></mrow><mo>≥</mo><mn>0</mn></mrow><mo>,</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>=</mo><mrow><mi>s</mi><mo>·</mo><mi>x</mi></mrow></mrow><mo>,</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>=</mo><mrow><mrow><mi>s</mi><mo>·</mo><mi>y</mi></mrow><mo>⇒</mo></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext> </mtext></mstyle></mrow></mtd><mtd><mstyle><mtext> </mtext></mstyle></mtd></mtr><mtr><mtd><mrow><mrow><mrow><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mfrac><msup><mi>c</mi><mi>′</mi></msup><mi>s</mi></mfrac></mrow><mo>≥</mo><mn>0</mn></mrow><mo>⇒</mo></mrow></mtd><mtd><mstyle><mtext> </mtext></mstyle></mtd></mtr><mtr><mtd><mrow><mrow><mrow><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi></mrow><mo>≥</mo><mn>0</mn></mrow><mo>,</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mi>c</mi><mo>=</mo><mrow><mi>floor</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mo>(</mo><mfrac><msup><mi>c</mi><mi>′</mi></msup><mi>s</mi></mfrac><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mstyle><mtext> </mtext></mstyle></mtd></mtr></mtable></math></maths><br /> For an opened half-plane the conversion is as follows: <maths id="MATH-US-00034" num="34"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>f</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow><mo>=</mo><mrow><mrow><mrow><mrow><mi>a</mi><mo>·</mo><msup><mi>x</mi><mi>′</mi></msup></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><msup><mi>y</mi><mi>′</mi></msup></mrow><mo>+</mo><msup><mi>c</mi><mi>′</mi></msup></mrow><mo>></mo><mn>0</mn></mrow><mo>⇒</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>55</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mrow><mrow><mrow><mi>a</mi><mo>·</mo><mi>s</mi><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>s</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><msup><mi>c</mi><mi>′</mi></msup></mrow><mo>></mo><mn>0</mn></mrow><mo>,</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>=</mo><mrow><mi>s</mi><mo>·</mo><mi>x</mi></mrow></mrow><mo>,</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>=</mo><mrow><mrow><mi>s</mi><mo>·</mo><mi>y</mi></mrow><mo>⇒</mo></mrow></mrow></mrow><mo>⁢</mo><mstyle><mtext> </mtext></mstyle></mrow></mtd><mtd><mstyle><mtext> </mtext></mstyle></mtd></mtr><mtr><mtd><mrow><mrow><mrow><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mfrac><msup><mi>c</mi><mi>′</mi></msup><mi>s</mi></mfrac></mrow><mo>></mo><mn>0</mn></mrow><mo>⇒</mo></mrow></mtd><mtd><mstyle><mtext> </mtext></mstyle></mtd></mtr><mtr><mtd><mrow><mrow><mrow><mrow><mi>a</mi><mo>·</mo><mi>x</mi></mrow><mo>+</mo><mrow><mi>b</mi><mo>·</mo><mi>y</mi></mrow><mo>+</mo><mi>c</mi></mrow><mo>></mo><mn>0</mn></mrow><mo>,</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mi>c</mi><mo>=</mo><mrow><mi>ceiling</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mo>(</mo><mfrac><msup><mi>c</mi><mi>′</mi></msup><mi>s</mi></mfrac><mo>)</mo></mrow></mrow></mrow></mrow></mtd><mtd><mstyle><mtext> </mtext></mstyle></mtd></mtr></mtable></math></maths>

0099It is an advantageous aspect of the present invention that two or more Edge Generators <b>103</b> may participate in span generation for the same functional. In one embodiment of the present invention, wherein k=1 (respectively 2 or 4) Edge Generators <b>103</b> participate in the span generation for the same functional, we want the first span of the 2 (respectively 4 or 8) spans generated per clock cycle to be aligned by y coordinate by 2 (respectively 4 or 8) accordingly. To accomplish this, denote <maths id="MATH-US-00035" num="35"><math overflow="scroll"><mrow><mrow><msub><mover><mi>y</mi><mo>~</mo></mover><mi>min</mi></msub><mo>=</mo><mrow><mrow><mi>floor</mi><mo>⁢</mo><mrow><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mstyle><mtext> </mtext></mstyle></mrow><mo>(</mo><mfrac><msub><mi>y</mi><mi>min</mi></msub><mrow><mi>k</mi><mo>·</mo><mn>2</mn></mrow></mfrac><mo>)</mo></mrow><mo>·</mo><mi>k</mi><mo>·</mo><mn>2</mn></mrow></mrow><mo>,</mo></mrow></math></maths><br /> and substitute {tilde over ({tilde over (x)})}=x−x_min, {tilde over ({tilde over (y)})}=y−y_min, {tilde over ({tilde over (c)})}=c−a·x_min−b·{tilde over (y)}_minto obtain <br /><i>f</i>(<i>{tilde over ({tilde over (x)})}, {tilde over ({tilde over (y)})}</i>)=<i>a·{tilde over ({tilde over (x)})}+b·{tilde over ({tilde over (y)})}+{tilde over ({tilde over (c)})}</i>  (56)<br /> The size of the bounding box is (x_max−x_min)·(y_max−y_min). Here we take <br /><i>m</i>=ceiling (log₂(<i>x</i>_max<i>−x</i>_min))  (57)<br />W=2^m  (58)<br /> Observing the above cases, taking (23), (52), (38) and (42) in consideration and uniting common expressions results in <br />ã=−|a|  (59)<br />{tilde over ({tilde over (b)})}=|b|  (60) <maths id="MATH-US-00036" num="36"><math overflow="scroll"><mtable><mtr><mtd><mrow><mover><mi>c</mi><mo>~</mo></mover><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mrow><mover><mi>c</mi><mover><mo>~</mo><mo>~</mo></mover></mover><mo>-</mo><mn>1</mn></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mi>a</mi><mo><</mo><mrow><mn>0</mn><mo>⋀</mo><mi>b</mi></mrow><mo>≥</mo><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mrow><mo>-</mo><mover><mi>c</mi><mover><mo>~</mo><mo>~</mo></mover></mover></mrow><mo>-</mo><mrow><mi>a</mi><mo>·</mo><mi>W</mi></mrow></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mi>a</mi><mo>≤</mo><mrow><mn>0</mn><mo>⋀</mo><mi>b</mi></mrow><mo><</mo><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mrow><mo>-</mo><mover><mi>c</mi><mover><mo>~</mo><mo>~</mo></mover></mover></mrow><mo>-</mo><mn>1</mn></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mi>a</mi><mo>></mo><mrow><mn>0</mn><mo>⋀</mo><mi>b</mi></mrow><mo>≤</mo><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mover><mi>c</mi><mover><mo>~</mo><mo>~</mo></mover></mover><mo>+</mo><mrow><mi>a</mi><mo>·</mo><mi>W</mi></mrow></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mi>a</mi><mo>≥</mo><mrow><mn>0</mn><mo>⋀</mo><mi>b</mi></mrow><mo>></mo><mn>0</mn></mrow></mtd></mtr></mtable></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>61</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> The number of c values generated according to the foregoing description corresponds to the number of spans that are to be generated per clock cycle, wherein an Edge Generator <b>103</b> generates two spans per clock cycle. Each Edge Generator's <b>103</b> spans are to be aligned by y such that the first span is even (i.e. y_minmod 2=0) and the second is odd (i.e. y_minmod 2=1). If the y_minof the bounding box is odd, span generation starts from y_min−1. To accomplish that, denote <br /><i>c</i>₀⁰<i>={tilde over (c)}−{tilde over ({tilde over (b)})}·(</i><i>y</i>_minmod 2)<br /><i>c</i>₁⁰<i>=c</i>₀⁰<i>+{tilde over ({tilde over (b)})}</i><br /><i>{tilde over (b)}</i>=2<i>·{tilde over ({tilde over (b)})}</i>  (62)<br /> In the case of more than one Edge Generator <b>103</b> participating in span generation for the functional, we need to have more than one set of initial values for the spans. Assuming the number of Edge Generators <b>103</b> is k (wherein k=1, 2 or 4), the set of initial values is given by <br />c_jⁱ<i>=c</i>_j⁰+2<i>·{tilde over ({tilde over (b)})}·i, i=</i>1<i>, . . . , k, j=</i>0, 1<br /><i>{tilde over (b)}=k·{tilde over ({tilde over (b)})}</i>  (63)<br /> and the Edge Generators <b>103</b> participating in the span generation for the given functional are loaded with the initial values of c_jⁱ, {tilde over (b)} and ã. <br /> Moving Down <br /> Before the Bresenham traversal, an Edge Generator <b>103</b> performs two operations: moving-down and Bresenham setup. The initial values are <br /><i>f</i>(<i>{tilde over (x)}, {tilde over (y)}</i>)=<i>ã·{tilde over (x)}+{tilde over (b)}·{tilde over (y)}+{tilde over (c)}, {tilde over (x)}</i>=0<i>, {tilde over (y)}</i>=0  (64)<br /> with the goal of computing for each given {tilde over (y)} <maths id="MATH-US-00037" num="37"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mn>0</mn></msub><mo>=</mo><mrow><mi>floor</mi><mo>⁢</mo><mrow><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mstyle><mtext> </mtext></mstyle></mrow><mo>(</mo><mrow><mo>-</mo><mfrac><mrow><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><mover><mi>y</mi><mo>~</mo></mover></mrow><mo>+</mo><mover><mi>c</mi><mo>~</mo></mover></mrow><mover><mi>a</mi><mo>~</mo></mover></mfrac></mrow><mo>)</mo></mrow></mrow><mo>,</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mover><mi>c</mi><mo>~</mo></mover><mo>≥</mo><mn>0</mn></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>65</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> Additionally, an Edge Generator <b>103</b> generates an {tilde over (x)} inside the bounding box. Therefore, if x₀is outside the bounding box, x₀is substituted by 0 or W such that <maths id="MATH-US-00038" num="38"><math overflow="scroll"><mtable><mtr><mtd><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mn>0</mn><mo>,</mo></mrow></mtd><mtd><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mn>0</mn></msub><mo><</mo><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mn>0</mn></msub><mo>,</mo></mrow></mtd><mtd><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mn>0</mn></msub><mo>∈</mo><mrow><mo>[</mo><mrow><mn>0</mn><mo>,</mo><mi>W</mi></mrow><mo>]</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi>W</mi><mo>,</mo></mrow></mtd><mtd><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mn>0</mn></msub><mo>></mo><mi>W</mi></mrow></mtd></mtr></mtable></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>66</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> After converting to a special case within the bounding box, we have f({tilde over (x)}, {tilde over (y)})<0 for the points above the edge (represented by the functional) and f({tilde over (x)}, {tilde over (y)})≧0 on or below the edge, wherein “above” refers to smaller y coordinates and “below” refers to greater y coordinates. We also have b≧0 and a<0 as given by the special case conditions.

0100<figref idref="DRAWINGS">FIG. 4</figref> is a flow diagram illustrating a method for the moving-down process in preparation the Bresenham setup, according to an embodiment of the present invention. The moving-down process starts <b>200</b> with {tilde over (y)}_k=0. If <b>201</b> the functional value f(0, {tilde over (y)}_k)≧0 the moving-down process is complete <b>202</b>. Otherwise <b>203</b>, move down along the {tilde over (x)}=0 border of the bounding box by adding <b>204</b> {tilde over (b)} to the functional value at the rate of one increment per clock cycle (wherein {tilde over (b)}≧0 and a {tilde over (b)} increment of the functional value corresponds to incrementing y by 1 until ƒ(0, {tilde over (y)}_k)≧0 <b>201</b> (wherein k>i), at which point the moving-down process is <b>202</b> complete. The moving-down process is represented by the following iterative description: <br />{tilde over (y)}₀=0<br /><i>f</i>₀<i>=f</i>(0, 0)=<i>ã</i>·0<i>+{tilde over (b)}</i>·0<i>+{tilde over (c)}={tilde over (c)}</i><br /><i>f</i>_i<i>=f</i>(0<i>, i</i>)=<i>{tilde over (b)}·i+f</i>₀<i>={tilde over (b)}</i>·(<i>i</i>−1)+{tilde over (b)}+f₀<i>=f</i>_i−1<i>+{tilde over (b)}</i>  (67)<br /> Bresenham Setup

0101The moving-down process is followed by the Bresenham setup process. The purpose of the Bresenham setup is to find the two values <maths id="MATH-US-00039" num="39"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><munder><mi>max</mi><mrow><mi>x</mi><mo>∈</mo><mi>Z</mi></mrow></munder><mo>⁢</mo><mrow><mo>{</mo><mrow><mrow><mrow><mover><mi>x</mi><mo>~</mo></mover><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mrow><mover><mi>a</mi><mo>~</mo></mover><mo>·</mo><mover><mi>x</mi><mo>~</mo></mover></mrow></mrow><mo>+</mo><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mi>k</mi></msub></mrow><mo>+</mo><mover><mi>c</mi><mo>~</mo></mover></mrow><mo>≥</mo><mn>0</mn></mrow><mo>}</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>68</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> and <maths id="MATH-US-00040" num="40"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mi>Δ</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>x</mi></mrow><mo>=</mo><mrow><mi>floor</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mo>(</mo><mrow><mo>-</mo><mfrac><mover><mi>b</mi><mo>~</mo></mover><mover><mi>a</mi><mo>~</mo></mover></mfrac></mrow><mo>)</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>69</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> Furthermore, since <br /><i>{tilde over (b)}·{tilde over (y)}</i>_k<i>+{tilde over (c)}=f</i>(0<i>, {tilde over (y)}</i>_k)  (70)<br /> we obtain <maths id="MATH-US-00041" num="41"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>floor</mi><mo>(</mo><mfrac><mrow><mi>f</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mn>0</mn><mo>,</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow><mrow><mo>-</mo><mover><mi>a</mi><mo>~</mo></mover></mrow></mfrac><mo>)</mo></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>71</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> The division algorithm described above (see Special Case) is modified as follows for more efficient hardware implementation: <br /><i>c</i>₀<i>=f</i>(0<i>, {tilde over (y)}</i>_k), <i>a</i>₀<i>=ã</i>·2^m+1<i>, b</i>₀<i>={tilde over (b)}, x</i>₀₀<i>=Δx</i>₀=0  (72)<br /> with the following steps describing the iterations: <maths id="MATH-US-00042" num="42"><math overflow="scroll"><mtable><mtr><mtd><mrow><mtable><mtr><mtd><mrow><msub><mi>c</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mrow><mn>2</mn><mo>·</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mrow><msub><mi>c</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mn>0</mn></msub></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mrow><msub><mi>c</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mn>0</mn></msub></mrow><mo>≥</mo><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>c</mi><mi>i</mi></msub><mo>,</mo></mrow></mtd><mtd><mrow><mrow><msub><mi>c</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mn>0</mn></msub></mrow><mo>&lt;</mo><mn>0</mn></mrow></mtd></mtr></mtable></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>x</mi><mrow><mrow><mn>0</mn><mo>⁢</mo><mi>i</mi></mrow><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mrow><mrow><mn>2</mn><mo>·</mo><msub><mi>x</mi><mrow><mn>0</mn><mo>⁢</mo><mi>i</mi></mrow></msub></mrow><mo>+</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mn>1</mn><mo>,</mo></mrow></mtd><mtd><mrow><mrow><msub><mi>c</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mn>0</mn></msub></mrow><mo>≥</mo><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mrow><mn>0</mn><mo>,</mo></mrow></mtd><mtd><mrow><mrow><msub><mi>c</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mn>0</mn></msub></mrow><mo>&lt;</mo><mn>0</mn></mrow></mtd></mtr></mtable></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>b</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>=</mo><mrow><mn>2</mn><mo>·</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mn>0</mn></msub></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mn>0</mn></msub></mrow><mo>≥</mo><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>,</mo></mrow></mtd><mtd><mrow><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mn>0</mn></msub></mrow><mo>&lt;</mo><mn>0</mn></mrow></mtd></mtr></mtable></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mi>Δ</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><msub><mi>x</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub></mrow><mo>=</mo><mrow><mrow><mrow><mn>2</mn><mo>·</mo><mi>Δ</mi></mrow><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><msub><mi>x</mi><mi>i</mi></msub></mrow><mo>+</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mn>1</mn><mo>,</mo></mrow></mtd><mtd><mrow><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mn>0</mn></msub></mrow><mo>≥</mo><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mrow><mn>0</mn><mo>,</mo></mrow></mtd><mtd><mrow><mrow><msub><mi>b</mi><mi>i</mi></msub><mo>+</mo><msub><mi>a</mi><mn>0</mn></msub></mrow><mo>&lt;</mo><mn>0</mn></mrow></mtd></mtr></mtable></mrow></mrow></mrow></mtd></mtr></mtable><mo>,</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mo>,</mo><mn>2</mn><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>,</mo><mrow><mi>m</mi><mo>+</mo><mn>1</mn></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>73</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> The values e₀=c_m+1=f(0, {tilde over (y)}_k) mod |a| and r₀=b_m+1=|b| mod |a| are used in the Bresenham walk (described below) for calculating the Bresenham error. The value <maths id="MATH-US-00043" num="43"><math overflow="scroll"><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>floor</mi><mo>(</mo><mfrac><mrow><mi>f</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mn>0</mn><mo>,</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow><mrow><mo>-</mo><mover><mi>a</mi><mo>~</mo></mover></mrow></mfrac><mo>)</mo></mrow></mrow></math></maths><br /> is the x value for the first span after the moving-down process. <br /> The value <maths id="MATH-US-00044" num="44"><math overflow="scroll"><mrow><mrow><mi>Δ</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>x</mi></mrow><mo>=</mo><mrow><mi>floor</mi><mo>(</mo><mrow><mo>-</mo><mfrac><mover><mi>b</mi><mo>~</mo></mover><mover><mi>a</mi><mo>~</mo></mover></mfrac></mrow><mo>)</mo></mrow></mrow></math></maths><br /> is the span-to-span x-increment value. <figref idref="DRAWINGS">FIG. 5</figref> is a flow diagram illustrating the foregoing method for the Bresenham setup process, according to an embodiment of the present invention. <br /> Bresenham Walk

0102The Bresenham walk is the process following the moving-down and Bresenham setup processes. After the Bresenham setup we have <br /><i>ã·{tilde over (x)}+{tilde over (b)}·{tilde over (y)}+{tilde over (c)}</i>=0  (74)<br /> wherein <br /><i>e</i>₀<i>=f</i>(0<i>, {tilde over (y)}</i>_k) mod |a|  (75)<br /><maths id="MATH-US-00045" num="45"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><mrow><mi>floor</mi><mo>(</mo><mfrac><mrow><mi>f</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mn>0</mn><mo>,</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow><mrow><mo>-</mo><mover><mi>a</mi><mo>~</mo></mover></mrow></mfrac><mo>)</mo></mrow></mrow></mtd><mtd><mstyle><mtext> </mtext></mstyle></mtd></mtr><mtr><mtd><mrow><msub><mi>r</mi><mn>0</mn></msub><mo>=</mo><mrow><mrow><mo></mo><mi>b</mi><mo></mo></mrow><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>mod</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mo></mo><mi>a</mi><mo></mo></mrow></mrow></mrow></mtd><mtd><mstyle><mtext> </mtext></mstyle></mtd></mtr><mtr><mtd><mrow><mrow><mi>Δ</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>x</mi></mrow><mo>=</mo><mrow><mi>floor</mi><mo>(</mo><mrow><mo>-</mo><mfrac><mover><mi>b</mi><mo>~</mo></mover><mover><mi>a</mi><mo>~</mo></mover></mfrac></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mstyle><mtext> </mtext></mstyle></mtd></mtr><mtr><mtd><mi>and</mi></mtd><mtd><mstyle><mtext> </mtext></mstyle></mtd></mtr><mtr><mtd><mrow><mrow><mrow><mover><mi>a</mi><mo>~</mo></mover><mo>·</mo><msub><mover><mi>x</mi><mo>~</mo></mover><mi>n</mi></msub></mrow><mo>+</mo><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mrow><mi>n</mi><mo>+</mo><mi>k</mi></mrow></msub></mrow><mo>+</mo><mover><mi>c</mi><mo>~</mo></mover></mrow><mo>=</mo><mrow><mrow><mrow><mover><mi>a</mi><mo>~</mo></mover><mo>·</mo><msub><mover><mi>x</mi><mo>~</mo></mover><mi>n</mi></msub></mrow><mo>+</mo><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mrow><mi>n</mi><mo>+</mo><mi>k</mi></mrow></msub></mrow><mo>+</mo><mrow><mi>f</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mn>0</mn><mo>,</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow><mo>-</mo><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mi>k</mi></msub></mrow></mrow><mo>=</mo><mrow><mn>0</mn><mo>⇔</mo></mrow></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>76</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mrow><mover><mi>a</mi><mo>~</mo></mover><mo>·</mo><msub><mover><mi>x</mi><mo>~</mo></mover><mi>n</mi></msub></mrow><mo>+</mo><mrow><mover><mi>b</mi><mo>~</mo></mover><mo>·</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mi>n</mi></msub></mrow><mo>+</mo><mrow><mi>f</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mn>0</mn><mo>,</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow></mrow><mo>=</mo><mn>0</mn></mrow></mtd><mtd><mrow><mo>(</mo><mn>77</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> and we want to find <maths id="MATH-US-00046" num="46"><math overflow="scroll"><mtable><mtr><mtd><mrow><mtable><mtr><mtd><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mi>n</mi></msub><mo>=</mo><mrow><mrow><mrow><mrow><mo>-</mo><mfrac><mover><mi>b</mi><mo>~</mo></mover><mover><mi>a</mi><mo>~</mo></mover></mfrac></mrow><mo>·</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mi>n</mi></msub></mrow><mo>-</mo><mfrac><mrow><mi>f</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mn>0</mn><mo>,</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mi>k</mi></msub></mrow><mo>)</mo></mrow></mrow><mover><mi>a</mi><mo>~</mo></mover></mfrac></mrow><mo>⇔</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mi>n</mi></msub><mo>=</mo><mrow><mrow><mfrac><mrow><mi>f</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mn>0</mn><mo>,</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mn>0</mn></msub></mrow><mo>)</mo></mrow></mrow><mrow><mo></mo><mi>a</mi><mo></mo></mrow></mfrac><mo>+</mo><mrow><mfrac><mrow><mo></mo><mi>b</mi><mo></mo></mrow><mrow><mo></mo><mi>a</mi><mo></mo></mrow></mfrac><mo>·</mo><msub><mover><mi>y</mi><mo>~</mo></mover><mi>n</mi></msub></mrow></mrow><mo>⇔</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mi>n</mi></msub><mo>=</mo><mrow><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>+</mo><mfrac><msub><mi>e</mi><mn>0</mn></msub><mrow><mo></mo><mi>a</mi><mo></mo></mrow></mfrac><mo>+</mo><mrow><mi>Δ</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mrow><mi>x</mi><mo>·</mo><mi>n</mi></mrow></mrow><mo>+</mo><mrow><mfrac><msub><mi>r</mi><mn>0</mn></msub><mrow><mo></mo><mi>a</mi><mo></mo></mrow></mfrac><mo>·</mo><mi>n</mi></mrow></mrow><mo>⇔</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mi>n</mi></msub><mo>=</mo><mrow><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>+</mo><mrow><mi>Δ</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>x</mi></mrow><mo>+</mo><mfrac><mrow><msub><mi>e</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>r</mi><mn>0</mn></msub></mrow><mrow><mo></mo><mi>a</mi><mo></mo></mrow></mfrac></mrow><mo>⇒</mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mi>n</mi></msub><mo>=</mo><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>+</mo><mrow><mi>Δ</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>x</mi></mrow><mo>+</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mn>0</mn><mo>,</mo></mrow></mtd><mtd><mrow><mrow><msub><mi>e</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>r</mi><mn>0</mn></msub></mrow><mo>&lt;</mo><mrow><mo></mo><mi>a</mi><mo></mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mn>1</mn><mo>,</mo></mrow></mtd><mtd><mrow><mrow><msub><mi>e</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>r</mi><mn>0</mn></msub></mrow><mo>≥</mo><mrow><mo></mo><mi>a</mi><mo></mo></mrow></mrow></mtd></mtr></mtable></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>e</mi><mi>n</mi></msub><mo>=</mo><mrow><msub><mi>e</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>r</mi><mn>0</mn></msub><mo>-</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mn>0</mn><mo>,</mo></mrow></mtd><mtd><mrow><mrow><msub><mi>e</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>r</mi><mn>0</mn></msub></mrow><mo>&lt;</mo><mrow><mo></mo><mi>a</mi><mo></mo></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mo></mo><mi>a</mi><mo></mo></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mrow><msub><mi>e</mi><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>r</mi><mn>0</mn></msub></mrow><mo>≥</mo><mrow><mo></mo><mi>a</mi><mo></mo></mrow></mrow></mtd></mtr></mtable></mrow></mrow></mrow></mtd></mtr></mtable><mo>,</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mo>,</mo><mn>2</mn><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>,</mo><mrow><mi>h</mi><mo>-</mo><msub><mi>y</mi><mi>k</mi></msub></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>78</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> wherein h represents a height of the bounding box and y_krepresents the value of the y coordinate at the Bresenham setup point. To simplify the hardware, the error value is decremented by |a| at the beginning of the Bresenham walk, after which e_ncan be compared to 0, with the comparison being simpler to implement in hardware. We also calculate <br /><i>r</i>_i<i>=r</i>₀<i>−|a|</i><br /><i>{tilde over (e)}</i>₀<i>=e</i>₀<i>+r</i>₀<i>−|a|</i>  (79)<br /> after which the Bresenham walk is more simply described as follows: <maths id="MATH-US-00047" num="47"><math overflow="scroll"><mtable><mtr><mtd><mrow><mtable><mtr><mtd><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mi>n</mi></msub><mo>=</mo><mrow><msub><mover><mi>x</mi><mo>~</mo></mover><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>+</mo><mrow><mi>Δ</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>x</mi></mrow><mo>+</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mn>0</mn><mo>,</mo></mrow></mtd><mtd><mrow><msub><mover><mi>e</mi><mo>~</mo></mover><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>&lt;</mo><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mrow><mn>1</mn><mo>,</mo></mrow></mtd><mtd><mrow><msub><mover><mi>e</mi><mo>~</mo></mover><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>≥</mo><mn>0</mn></mrow></mtd></mtr></mtable></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mover><mi>e</mi><mo>~</mo></mover><mi>n</mi></msub><mo>=</mo><mrow><msub><mover><mi>e</mi><mo>~</mo></mover><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>+</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><msub><mi>r</mi><mn>0</mn></msub><mo>,</mo></mrow></mtd><mtd><mrow><msub><mover><mi>e</mi><mo>~</mo></mover><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>&lt;</mo><mn>0</mn></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>r</mi><mn>1</mn></msub><mo>,</mo></mrow></mtd><mtd><mrow><msub><mover><mi>e</mi><mo>~</mo></mover><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></msub><mo>≥</mo><mn>0</mn></mrow></mtd></mtr></mtable></mrow></mrow></mrow></mtd></mtr></mtable><mo>,</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mo>,</mo><mn>2</mn><mo>,</mo><mi>…</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>,</mo><mrow><mi>h</mi><mo>-</mo><msub><mi>y</mi><mi>k</mi></msub></mrow></mrow></mtd><mtd><mrow><mo>(</mo><mn>80</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /><figref idref="DRAWINGS">FIG. 6</figref> is a flow diagram illustrating a method for the Bresenham walk process, according to an embodiment of the present invention. <br /> Span Generator Structure

0103<figref idref="DRAWINGS">FIG. 7</figref> is a block diagram illustrating the Span Generator <b>101</b>, according to an embodiment of the present invention. The Span Generator <b>101</b> comprises <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0000"><ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0104"> An Input Interface <b>105</b></li><li id="ul0004-0002" num="0105"> 3 Loaders <b>102</b></li><li id="ul0004-0003" num="0106"> 12 Edge Generators <b>103</b></li><li id="ul0004-0004" num="0107"> 4 cascaded 3-input Sorters <b>104</b></li><li id="ul0004-0005" num="0108"> An Output Interface <b>106</b></li><li id="ul0004-0006" num="0109"> A scissoring box module <b>107</b></li></ul></li></ul>

0110Input Interface <b>105</b> packs input functionals for passing to the three Loaders <b>102</b>. Loaders <b>102</b> perform Edge Generator <b>103</b> initialization. Edge Generators <b>103</b> generate “left” and “right” edges, which are then sorted in tournament Sorters <b>104</b>. The Sorters' <b>104</b> output is directed via Output Interface <b>106</b> to a Tile Generator (TG), the TG for converting a set of spans into a sequence of tiles, wherein a tile refers to a rectangle set of pixels to be rendered.

0000Advantageously, the Span Generator <b>101</b> solves the following issues:

0000<ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0000"><ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0111"> 1. The Span Generator <b>101</b> produces spans for a triangle having up to 15 functionals. The X and Y clipping is performed by the scissoring box module <b>107</b>, and thus 11 functionals remain. For reasons described in items 3 and 4, there are 12 Edge Generators <b>103</b> in the Span Generator <b>101</b> architecture. </li><li id="ul0006-0002" num="0112"> 2. The Span Generator <b>101</b> generates at least two spans per clock cycle, presenting a doubling of performance when compared to generating one span per clock cycle, for 30% more cost. </li><li id="ul0006-0003" num="0113"> 3. In the case of a reduced set of functionals (i.e. fewer than 7 or 8) the Span Generator <b>101</b> can generate more than two spans per clock cycle. In this case we use two Edge Generators <b>103</b> to process the same functional. The Loaders <b>102</b> setup the Edge Generators <b>103</b> at different spans according to the initial offsets of the respective Edge Generators <b>103</b>. Analogously, in the case of fewer than 4 functionals, the span generation rate reaches eight spans per clock cycle. </li><li id="ul0006-0004" num="0114"> 4. The Loaders <b>102</b> provide the maximal Span Generator <b>101</b> performance for the most general case, which is a case involving 3 functionals. Thus the Span Generator <b>101</b> comprises 3 Loaders <b>102</b>, wherein a Loader <b>102</b> can load four Edge Generators <b>103</b> sequentially. </li><li id="ul0006-0005" num="0115"> 5. For non-adaptive over-sampling with a rotating grid, the Span Generator <b>101</b> perform clipping by several half-planes with a known tangent, a process that can be done using a separate device. </li></ul></li></ul>

0116External Assumptions of Data Formats <tables id="TABLE-US-00002" num="2"><table frame="none" colsep="0" rowsep="0" pgwide="1"><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="OFFSET" colwidth="56PT" align="left" /><colspec colname="1" colwidth="98PT" align="left" /><colspec colname="2" colwidth="49PT" align="left" /><colspec colname="3" colwidth="119PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="3" align="center" rowsep="1" /></row><row><entry /><entry /><entry>Bits for</entry><entry /></row><row><entry /><entry>Range</entry><entry>representation</entry><entry>Comment</entry></row><row><entry /><entry namest="OFFSET" nameend="3" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="1" colwidth="56PT" align="left" /><colspec colname="2" colwidth="98PT" align="left" /><colspec colname="3" colwidth="49PT" align="left" /><colspec colname="4" colwidth="119PT" align="left" /><tbody valign="top"><row><entry>Window size,</entry><entry>[0 . . . 2¹²− 1] × [0 . . . 2¹²− 1]</entry><entry>12</entry><entry>To be able to draw into 4096 × 4096</entry></row><row><entry>pixels</entry><entry /><entry /><entry>texture</entry></row><row><entry>Maximum</entry><entry>2²</entry><entry> 2</entry><entry>Not the same as vertex subpixel grid, it</entry></row><row><entry>divisions of</entry><entry /><entry /><entry>is coarser. The functional coefficients</entry></row><row><entry>oversampling</entry><entry /><entry /><entry>will be given in the vertex subpixel grid</entry></row><row><entry>grid per pixel</entry><entry /><entry /><entry>while the x, y coordinates are in the</entry></row><row><entry /><entry /><entry /><entry>oversampling one.</entry></row><row><entry>Window size,</entry><entry>[0 . . . 2¹⁴] × [0 . . . 2¹⁴]</entry><entry>15</entry><entry>Extreme window's pixels in rotated grid</entry></row><row><entry>over-samples</entry><entry /><entry /><entry>coordinates</entry></row><row><entry>Vertex X, Y after</entry><entry>[0 . . . 2¹⁴+ 1] × [0 . . . 2¹⁴+ 1]</entry><entry>15</entry><entry>We need one more grid position on the</entry></row><row><entry>clipping, over-</entry><entry /><entry /><entry>right and bottom as otherwise the last</entry></row><row><entry>samples.</entry><entry /><entry /><entry>column (raw) of pixels cannot be drawn</entry></row><row><entry /><entry /><entry /><entry>(with tight clipping) because of</entry></row><row><entry /><entry /><entry /><entry>open/close convention, hence a value of</entry></row><row><entry /><entry /><entry /><entry>2¹⁴+ 1 is possible here</entry></row><row><entry>Subpixel vertex</entry><entry>[0 . . . 2⁸− 1]</entry><entry> 8</entry><entry>Main grid for the triangle setup</entry></row><row><entry>position, per pixel</entry><entry /><entry>(subpixel</entry></row><row><entry /><entry /><entry>bits)</entry></row><row><entry>Vertex X, Y after</entry><entry>[0 . . . 2²⁰+ 1] × [0 . . . 2²⁰+ 1]</entry><entry>21</entry><entry>We need one more grid position on the</entry></row><row><entry>clipping, sub-</entry><entry /><entry /><entry>right and bottom as otherwise the last</entry></row><row><entry>pixels units.</entry><entry /><entry /><entry>column (raw) of pixels cannot be drawn</entry></row><row><entry /><entry /><entry /><entry>(with tight clipping) because of</entry></row><row><entry /><entry /><entry /><entry>open/close convention, hence a value of</entry></row><row><entry /><entry /><entry /><entry>2²⁰+ 1 is possible here</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0117Internal Data Formats <tables id="TABLE-US-00003" num="3"><table frame="none" colsep="0" rowsep="0" pgwide="1"><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="OFFSET" colwidth="56PT" align="left" /><colspec colname="1" colwidth="84PT" align="left" /><colspec colname="2" colwidth="49PT" align="left" /><colspec colname="3" colwidth="126PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="3" align="center" rowsep="1" /></row><row><entry /><entry /><entry>Bits for</entry><entry /></row><row><entry /><entry>Range</entry><entry>representation</entry><entry>Comment</entry></row><row><entry /><entry namest="OFFSET" nameend="3" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="1" colwidth="56PT" align="left" /><colspec colname="2" colwidth="84PT" align="left" /><colspec colname="3" colwidth="49PT" align="left" /><colspec colname="4" colwidth="126PT" align="left" /><tbody valign="top"><row><entry>Edge functional</entry><entry>[−2²⁰− 1 . . . 2²⁰+ 1]</entry><entry>21 + sign</entry><entry>See below</entry></row><row><entry>coefficients a_i, b_i,</entry></row><row><entry>see below</entry></row><row><entry>Edge functional</entry><entry>±(2⁴⁰+ 2²¹+ 1)</entry><entry>41 + sign</entry><entry>See below</entry></row><row><entry>coefficients (in a</entry></row><row><entry>window</entry></row><row><entry>coordinate system</entry></row><row><entry>after setup) c_i(see</entry></row><row><entry>below)</entry></row><row><entry>Bounding box</entry><entry>[0 . . . 2¹⁴]</entry><entry>15</entry><entry>Bounding box origin is inclusive; it</entry></row><row><entry>origin (x_min, y_min)</entry><entry /><entry /><entry>values the first x position to draw and</entry></row><row><entry>in oversampling</entry><entry /><entry /><entry>the first span to draw (if span is not</entry></row><row><entry>grid units</entry><entry /><entry /><entry>empty).</entry></row><row><entry /><entry /><entry /><entry>The bounding box is defined as an</entry></row><row><entry /><entry /><entry /><entry>original bounding box of a triangle</entry></row><row><entry /><entry /><entry /><entry>intersected with the scissoring box. If no</entry></row><row><entry /><entry /><entry /><entry>scissoring box exists, then the window</entry></row><row><entry /><entry /><entry /><entry>box is used as a scissoring box.</entry></row><row><entry>Edge functional</entry><entry>±(2⁴⁰+ 2³⁵+ 2²¹+ 2¹⁵+ 1)</entry><entry>41 + sign</entry></row><row><entry>coefficients after</entry></row><row><entry>shifting to the</entry></row><row><entry>bounding box</entry></row><row><entry>system c_i, see</entry></row><row><entry>below</entry></row><row><entry>Bounding box</entry><entry>[0 . . . 2¹⁴+ 1]</entry><entry>15</entry><entry>Bounding box max point is inclusive; it</entry></row><row><entry>maximum point</entry><entry /><entry /><entry>values the last x position to draw and the</entry></row><row><entry>(x_max, y_max)</entry><entry /><entry /><entry>last span to draw (if span is not empty).</entry></row><row><entry>Non adjusted</entry><entry>[0 . . . 2¹⁴+ 1]</entry><entry>15</entry><entry>The box with the width of 0 can have a</entry></row><row><entry>bounding box</entry><entry /><entry /><entry>single pixel column inside, since both</entry></row><row><entry>width x_max− x_min</entry><entry /><entry /><entry>sides of the box are inclusive.</entry></row><row><entry>Extended</entry><entry>2^{[0 . . . 15]}</entry><entry> 4</entry><entry>Adjusted (extended) bounding box is</entry></row><row><entry>bounding box</entry><entry /><entry /><entry>used in the interpolator, since the width</entry></row><row><entry>width x_max− x_min</entry><entry /><entry /><entry>is to have a value of a power of two.</entry></row><row><entry>rounded to the</entry><entry /><entry /><entry>Note: the extended box can be wider</entry></row><row><entry>next power of 2</entry><entry /><entry /><entry>then the window.</entry></row><row><entry namest="1" nameend="4" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Input Interface

0118The Span Generator <b>101</b> has the following input interface: <tables id="TABLE-US-00004" num="4"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="1" colwidth="28PT" align="left" /><colspec colname="2" colwidth="28PT" align="left" /><colspec colname="3" colwidth="161PT" align="left" /><thead><row><entry /></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row><row><entry>Field</entry><entry>Length,</entry><entry /></row><row><entry>name</entry><entry>bit</entry><entry>Description</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>L</entry><entry> 1</entry><entry>The signal to start loading the first three functionals</entry></row><row><entry>M</entry><entry> 1</entry><entry>Mode: 0 - standard, 1 - wire-frame</entry></row><row><entry>R</entry><entry> 8</entry><entry>The width of the wire-frame line in the current grid</entry></row><row><entry /><entry /><entry>units</entry></row><row><entry>F</entry><entry> 4</entry><entry>The number of the functionals. In the case of the wire-</entry></row><row><entry /><entry /><entry>frame mode, the three LSB are the mask for drawing</entry></row><row><entry /><entry /><entry>the edges (0 indicates do not draw, 1 indicates draw),</entry></row><row><entry /><entry /><entry>and MSB is a request to extent the bounding box by</entry></row><row><entry /><entry /><entry>W/2 in all directions</entry></row><row><entry>A</entry><entry>22 × 3</entry><entry>The value of the a coefficients for the 11 functionals. 0</entry></row><row><entry /><entry /><entry>if the particular functional is not present</entry></row><row><entry>B</entry><entry>22 × 3</entry><entry>The value of the b coefficients for the 11 functionals. 0</entry></row><row><entry /><entry /><entry>if the particular functional is not present</entry></row><row><entry>C</entry><entry>42 × 3</entry><entry>The value of the c coefficients for the 11 functionals. 0</entry></row><row><entry /><entry /><entry>if the particular functional is not present</entry></row><row><entry>X0</entry><entry>15</entry><entry>The start x value for the left edge of the scissoring box</entry></row><row><entry>X1</entry><entry>15</entry><entry>The start x value for the right edge of the scissoring</entry></row><row><entry /><entry /><entry>box</entry></row><row><entry>Y</entry><entry>15</entry><entry>The value of the y coordinate in the top corner of the</entry></row><row><entry /><entry /><entry>scissoring box</entry></row><row><entry>Y0</entry><entry>15</entry><entry>The value of the y coordinate in the left corner of the</entry></row><row><entry /><entry /><entry>scissoring box</entry></row><row><entry>Y1</entry><entry>15</entry><entry>The value of the y coordinate in the right corner of the</entry></row><row><entry /><entry /><entry>scissoring box</entry></row><row><entry>Y2</entry><entry>15</entry><entry>The value of the y coordinate in the bottom corner of</entry></row><row><entry /><entry /><entry>the scissoring box</entry></row><row><entry>T</entry><entry> 2</entry><entry>The tangent of the slope of the left edge of the</entry></row><row><entry /><entry /><entry>scissoring box, according to the following:</entry></row><row><entry /><entry /><entry>00 The right edge is vertical</entry></row><row><entry /><entry /><entry>01 The tangent is 1</entry></row><row><entry /><entry /><entry>10 The tangent is 2</entry></row><row><entry /><entry /><entry>11 The tangent is 3</entry></row><row><entry>XMIN</entry><entry>15</entry><entry>The value of the x coordinate for the left edge of the</entry></row><row><entry /><entry /><entry>bounding box</entry></row><row><entry>XMAX</entry><entry>15</entry><entry>The value of the x coordinate for the right edge of the</entry></row><row><entry /><entry /><entry>bounding box</entry></row><row><entry>YMIN</entry><entry>15</entry><entry>The value of the y coordinate for the top edge of the</entry></row><row><entry /><entry /><entry>bounding box</entry></row><row><entry>YMAX</entry><entry>15</entry><entry>The value of the y coordinate for the bottom edge of</entry></row><row><entry /><entry /><entry>the bounding box</entry></row><row><entry namest="1" nameend="3" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Wire-frame

0119We assume the wire-frame will be done as three functionals for edges inside the tight bounding and scissoring boxes. That means we do not support clipping planes for wire-frame. The span generation for the wire-frame mode does not take anything special besides the Loader <b>102</b> should supply corrected functional values for two nested triangles. The inner triangle is a set of points on the current grid, which should be excluded from the outer triangle. For an edge f(x, y)=a·x+b·y+c, the functional values for that two triangles will be <br />ƒ₁(<i>x, y</i>)=<i>a·x+b·y+c+w</i>/2-outer edge<br />ƒ₂(<i>x, y</i>)=<i>a·x+b·y+c−w</i>/2- inner edge<br /> where w is a width of the wireframe edges. <br /> Loader

0120<figref idref="DRAWINGS">FIG. 8</figref> is a block diagram illustrating a Loader <b>102</b> (without shifters), according to an embodiment of the present invention. Loader <b>102</b> comprises the following inputs: <tables id="TABLE-US-00005" num="5"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>SHORT xMin, yMin, xMax, yMax, a, b;</entry></row><row><entry /><entry>LONG c;</entry></row><row><entry /><entry>SHORT nF;  // the number of the functionals</entry></row><row><entry /><entry>and outputs</entry></row><row><entry /><entry>SHORT c0l, c0h, c1l, c1h, bl, bh, al, ah, m;</entry></row><row><entry /><entry>BOOL dir, cor</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0121Initially, a Loader <b>102</b> determines the global values, which are the same for all of the functionals in the polygon. To accomplish this, the Loader <b>102</b> computes the parameters of the bounding box: <tables id="TABLE-US-00006" num="6"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="28PT" align="left" /><colspec colname="1" colwidth="119PT" align="left" /><colspec colname="2" colwidth="70PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>SHORT w = xMax − xMin;</entry><entry /></row><row><entry /><entry>m = ceiling (log2 (w));</entry></row><row><entry /><entry>SHORT W = 1 << m;</entry><entry>// 2**m</entry></row><row><entry /><entry>SHORT h = yMax − yMin;</entry></row><row><entry /><entry>SHORT k = (nF > 6)? 1 : (nF > 3);</entry></row><row><entry /><entry>SHORT aT, bT;</entry><entry>// ã and {tilde over (b)}</entry></row><row><entry /><entry namest="OFFSET" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0122Then for each functional the Loader <b>102</b> computes <tables id="TABLE-US-00007" num="7"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>nCase = (a < 0 && b >= 0)? 1 :</entry></row><row><entry /><entry> (a <= 0 && b < 0)? 2 :</entry></row><row><entry /><entry> (a > 0 && b <= 0)? 4 :</entry></row><row><entry /><entry> (a >= 0 && b > 0)? 5 : 0;</entry></row><row><entry /><entry>       // but the “0” is redundant</entry></row><row><entry /><entry>BOOL cor = (nCase > 3)? 1 : 0;</entry></row><row><entry /><entry>BOOL dir = (nCase < 2 ∥ ncase > 4)? 0 : 1;</entry></row><row><entry /><entry>LONG cT2 = C − a * xMin − b * yMin;  // {tilde over ({tilde over (c)})}</entry></row><row><entry /><entry>switch (nCase) {</entry></row><row><entry /><entry> case 1:</entry></row><row><entry /><entry>  aT = a;</entry></row><row><entry /><entry>  bT = b;</entry></row><row><entry /><entry>  cT = cT2 − 1;              // {tilde over (c)}</entry></row><row><entry /><entry>  break;</entry></row><row><entry /><entry> case 2:</entry></row><row><entry /><entry>  aT = a;</entry></row><row><entry /><entry>  bT = −b;</entry></row><row><entry /><entry>  cT = −cT2 − a * W;</entry></row><row><entry /><entry> case 4:</entry></row><row><entry /><entry>  aT = −a;</entry></row><row><entry /><entry>  bT = −b;</entry></row><row><entry /><entry>  cT = −cT2 − a;</entry></row><row><entry /><entry> case 5:</entry></row><row><entry /><entry>  aT = −a;</entry></row><row><entry /><entry>  bT = −b;</entry></row><row><entry /><entry>  cT = cT2 + a * W;</entry></row><row><entry /><entry> }</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0123The Loader <b>102</b> then computes two separate functional values for two sequential spans, and in the case of having k=1, 2, 4 Edge Generators <b>103</b> per functional, the Loader <b>102</b> also computes values for all other two or six sequential spans: <tables id="TABLE-US-00008" num="8"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="49PT" align="left" /><colspec colname="1" colwidth="168PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>c [0] = cT − bT * (yMin % 2);</entry></row><row><entry /><entry>c [1] = c [0] + bT;</entry></row><row><entry /><entry>for (i = 1; i &lt; k; i ++) {</entry></row><row><entry /><entry> c [i * 2 ] = c [i * 2 − 2] + 2 * bT;</entry></row><row><entry /><entry> c [i * 2 + 1] = c [i * 2 − 1] + 2 * bT;</entry></row><row><entry /><entry> }</entry></row><row><entry /><entry>bT &lt;&lt;= k;</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0124<figref idref="DRAWINGS">FIG. 9</figref> is a block diagram illustrating {tilde over (b)} and {tilde over (c)} values wrapping before they are loaded into an Edge Generator <b>103</b>, according to an embodiment of the present invention. The division algorithm is described above (see Special Case). But if it is performed literally then the ã value needs to be scaled before division multiplying it by 2^m, which scales ã out of short range. Nevertheless each clock of division effective length of subtraction is still in the short range, thus instead of scaling the ã value, the f(0, {tilde over (y)}_k) value is scaled by 2^−mbefore the division and then instead of dividing the scaled ã value by 2 each clock, the scaled f(0, {tilde over (y)}_k) value is multiplied by 2. While a <maths id="MATH-US-00048" num="48"><math overflow="scroll"><mrow><mrow><mi>Δ</mi><mo>⁢</mo><mstyle><mtext> </mtext></mstyle><mo>⁢</mo><mi>x</mi></mrow><mo>=</mo><mrow><mi>floor</mi><mo>(</mo><mrow><mo>-</mo><mfrac><mover><mi>b</mi><mo>~</mo></mover><mover><mi>a</mi><mo>~</mo></mover></mfrac></mrow><mo>)</mo></mrow></mrow></math></maths><br /> value is also needed, the {tilde over (b)} value is also pre-scaled. The scaled f(0, {tilde over (y)}_k) value is longer than the non-scaled value. However, this does not necessitate a longer adder for performing the moving-down process: The least significant bits of the scaled f(0, {tilde over (y)}_k) value are wrapped to the most significant bits (i.e. a cyclic rotation instead of an arithmetical shift), resulting in the scaled f(0, {tilde over (y)}_k) value being expressed within the same bit-length as the non-scaled value. To avoid carry propagation from MSB to LSB, invert the sign bit before loading data into an Edge Generator <b>103</b>. In the case of f(0, {tilde over (y)}_k)&lt;0 this bit would be 0 and would not propagate a carry. To detect if f(0, {tilde over (y)}_k)≧0, compare this bit to 1. The {tilde over (b)} value is scaled in a similar way, with the difference that it is not wrapped.

0125At the first clock cycle of the division process, Edge Generator <b>103</b> determines whether one of the f(0, {tilde over (y)}_k) or {tilde over (b)} values exceed the boundaries, i.e. it determines whether the division result would be greater than or equal to W. For that purpose, the real scale factor is not m, but m+1. The division works in the above-described way, but if the result is not below W, either x₀will be beyond the bounding box limit or the result after the first Bresenham step would be beyond the bounding box limit.

0126The Loader <b>102</b> loads the Edge Generators <b>103</b> sequentially, starting from the first three functionals of each triangle, with the first functional loaded into the first Edge Generator <b>103</b>, and so on. If there are only three functionals, the Loader <b>102</b> loads other Edge Generators <b>103</b> with the functional values for other three groups of spans on the next sequential clock cycles.

0127Considering the input interface and the approach of loading several Edge Generators <b>103</b> at subsequent clock cycles, the pseudo-code for the Loader <b>102</b> is as follows: <tables id="TABLE-US-00009" num="9"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>template <int N></entry></row><row><entry /><entry>void Loader<N> ( //pipelined, performed each clock</entry></row><row><entry /><entry>     // input interface:</entry></row><row><entry /><entry> bool L, // the first clock of loading the L = 1</entry></row><row><entry /><entry> bool M, // M = 1 in the wire-frame mode</entry></row><row><entry /><entry> BIT2 Os,// oversampling grid to pixel grid relation:</entry></row><row><entry /><entry>     // 0 − 4x, 1 − 2x, 2 − 1x</entry></row><row><entry /><entry> BIT8 R, // the width of a wire-frame line</entry></row><row><entry /><entry> BIT4 F, // the number of functionals, edge mask in wire-</entry></row><row><entry /><entry>frame mode</entry></row><row><entry /><entry> SHORT A, // the first coefficient</entry></row><row><entry /><entry> SHORT B, // the second coefficient</entry></row><row><entry /><entry> LONG C,  // the free member</entry></row><row><entry /><entry> BIT21 XMIN,  // the left edge of the bounding box</entry></row><row><entry /><entry> BIT21 YMIN,  // the top edge of the bounding box</entry></row><row><entry /><entry> BIT21 XMAX,  // the right edge of the bounding box</entry></row><row><entry /><entry> BIT21 YMAX,  // the bottom edge of the bounding box</entry></row><row><entry /><entry> BIT21 XFUN,  // the X coordinate of the zero functional</entry></row><row><entry /><entry>point</entry></row><row><entry /><entry> BIT21 YFUN // the Y coordinate of the zero functional</entry></row><row><entry /><entry>point</entry></row><row><entry /><entry> ) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="119PT" align="left" /><colspec colname="2" colwidth="84PT" align="left" /><tbody valign="top"><row><entry /><entry> BIT3 toGo = (L)? 4 : toGo − 1;</entry><entry>// counts the</entry></row><row><entry /><entry>number of</entry></row><row><entry /><entry /><entry>// functionals to</entry></row><row><entry /><entry>load</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="140PT" align="left" /><colspec colname="2" colwidth="63PT" align="left" /><tbody valign="top"><row><entry /><entry> BIT3 nClk = (L)? 0 : nClk + (toGo != 0);</entry><entry>// counts</entry></row><row><entry /><entry>loading</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="133PT" align="left" /><colspec colname="1" colwidth="84PT" align="left" /><tbody valign="top"><row><entry /><entry>// clocks</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><tbody valign="top"><row><entry /><entry> if (L) {</entry></row><row><entry /><entry>  bool wf = M,</entry></row><row><entry /><entry>  BIT8 wW = R,</entry></row><row><entry /><entry>  BIT15 xMIN = ((xMIN >> 5)</entry></row><row><entry /><entry>  BIT4 nFunct = F,</entry></row><row><entry /><entry>  BIT2 k = (wf)? 2 : (nFunct < 4)? 4 : (nFunct < 7)? 2 :</entry></row><row><entry /><entry>1;</entry></row><row><entry /><entry>  BIT21 w = XMAX − XMIN;</entry></row><row><entry /><entry>  BIT21 h = YMAX − YMIN;</entry></row><row><entry /><entry>  BIT4 m = ceiling (log2 (w));</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="140PT" align="left" /><colspec colname="2" colwidth="63PT" align="left" /><tbody valign="top"><row><entry /><entry>  BIT16 W = 1 << m;</entry><entry>// 2**m</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><tbody valign="top"><row><entry /><entry>  BIT15 xMin = XMIN;</entry></row><row><entry /><entry>  BIT15 yMin = YMIN;</entry></row><row><entry /><entry>  }</entry></row><row><entry /><entry> BIT3 nCase =</entry></row><row><entry /><entry>  (A < 0 && B >= 0)? 1 :</entry></row><row><entry /><entry>  (A <= 0 && B < 0)? 2 :</entry></row><row><entry /><entry>  (A > 0 && B <= 0)? 4 :</entry></row><row><entry /><entry>  (A >= 0 && B > 0)? 5 :</entry></row><row><entry /><entry>  0; // redundant, not used</entry></row><row><entry /><entry> BOOL cor = nCase > 3;</entry></row><row><entry /><entry> BOOL dir = nCase >= 2 && nCase < 5;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="119PT" align="left" /><colspec colname="2" colwidth="84PT" align="left" /><tbody valign="top"><row><entry /><entry> SHORT aT = (A >= 0)? −A : A;</entry><entry>// ã</entry></row><row><entry /><entry> SHORT b2T = (B < 0)? −B : B;</entry><entry>// {tilde over ({tilde over (b)})}</entry></row><row><entry /><entry> LONG cT2 = C −</entry><entry>// {tilde over ({tilde over (c)})}</entry></row><row><entry /><entry>  A * (xMin − XFUN) −</entry></row><row><entry /><entry>  B * ((yMin & −(k << 1) − YFUN);</entry><entry>// align spans by Y</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="140PT" align="left" /><colspec colname="2" colwidth="63PT" align="left" /><tbody valign="top"><row><entry /><entry> cT2 >>= (6 + Os);</entry><entry>// shift to</entry></row><row><entry /><entry>get</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="119PT" align="left" /><colspec colname="2" colwidth="84PT" align="left" /><tbody valign="top"><row><entry /><entry> LONG CT = ((dir)? −cT2 : cT2)</entry><entry>// {tilde over (c)}</entry></row><row><entry /><entry>  + (nCase == 1 ∥ nCase == 4)? −1 :</entry></row><row><entry /><entry>  (dir)? −A << m : A << m;</entry></row><row><entry /><entry> LONG c [8];</entry></row><row><entry /><entry> LONG b [4];</entry></row><row><entry /><entry> c [7] = c [5] + (b2T << 1);</entry><entry>// pipelining</entry></row><row><entry /><entry> c [6] = c [4] + (b2T << 1);</entry></row><row><entry /><entry> c [5] = c [3] + (b2T << 1);</entry></row><row><entry /><entry> c [4] = c [2] + (b2T << 1);</entry></row><row><entry /><entry> c [3] = c [1] + (b2T << 1);</entry></row><row><entry /><entry> c [2] = c [0] + (b2T << 1);</entry></row><row><entry /><entry> c [0] = cT − (yMin & 1)? b2T : 0;</entry></row><row><entry /><entry> c [1] = c [0] + b2T;</entry></row><row><entry /><entry> SHORT bT = b2T << (1 << k);</entry><entry>// << 2, 4, 8</entry></row><row><entry /><entry namest="OFFSET" nameend="2" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Edge Generator

0128<figref idref="DRAWINGS">FIG. 10</figref><i>a </i>is a block diagram illustrating an Edge Generator, according to an embodiment of the present invention. The Edge Generator <b>103</b> comprises four 24-bit adders and eight 24-bit registers. An adder has the outputs of two registers as inputs, wherein the inputs of the registers are multiplexed: <tables id="TABLE-US-00010" num="10"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="35PT" align="left" /><colspec colname="1" colwidth="182PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>SHORT reg [8];</entry></row><row><entry /><entry>bool carry [4];</entry></row><row><entry /><entry>SHORT add [4];</entry></row><row><entry /><entry>add [0] = req [0] + reg [4] + carry [0];</entry></row><row><entry /><entry>add [1] = reg [1] + reg [5] + carry [1];</entry></row><row><entry /><entry>add [2] = reg [2] + reg [4] + carry [2];</entry></row><row><entry /><entry>add [3] = reg [3] + reg [7] + carry [3];</entry></row><row><entry /><entry>for (1 = 0; i &lt; 8; i ++)</entry></row><row><entry /><entry> reg [i] = some_function (add [k], reg [k], ...);</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0129The registers' outputs are supplied directly to inputs of adders to minimize a delay at the adders. The structure of multiplexers allows us to minimize a delay at them also, the maximal post-adder delay supposed to be not more than 3×1 multiplexer.

0130Besides the implementation of the general functionality, the multiplexers are also performing loading and stalling operations by writing a new set of data or a previous state of an Edge Generator <b>103</b> back to registers.

0131The basic functionality of an Edge Generator <b>103</b> comprises three main phases: moving-down, Bresenham setup and Bresenham walk. There are also seven interim states, which are: load, stall, first clock of moving down, transfer from moving down to Bresenham setup, two different clocks of transfer from Bresenham setup to Bresenham walk and finally first clock of the Bresenham.

0132An Edge Generator <b>103</b> has the following inputs: <tables id="TABLE-US-00011" num="11"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>SHORT c0l, c0h, c1l, c1h, bl, bh, al, ah, m;</entry></row><row><entry /><entry>BOOL dir, cor, load, stall;</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0133When the load signal is set, the Edge Generator <b>103</b> stores the input values in internal registers and resets its state. When the stall signal is set, the Edge Generator <b>103</b> registers retain their content for the current clock cycle.

0000Edge Generator: Moving Down

0134<figref idref="DRAWINGS">FIG. 10</figref><i>b </i>is a block diagram illustrating an Edge Generator <b>103</b> during the moving-down phase, according to an embodiment of the present invention. The functional value is accumulated in the register, which was loaded with the value of {tilde over (c)} at the start. At this phase each Edge Generator <b>103</b> performs the following: <tables id="TABLE-US-00012" num="12"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="84PT" align="left" /><colspec colname="1" colwidth="133PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>while (c &lt; 0) {</entry></row><row><entry /><entry> c = c + b;</entry></row><row><entry /><entry> }</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0135Applying this to the hardware, we obtain: <tables id="TABLE-US-00013" num="13"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>// at loading stage</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="35PT" align="left" /><colspec colname="2" colwidth="35PT" align="left" /><colspec colname="3" colwidth="126PT" align="left" /><tbody valign="top"><row><entry /><entry>SHORT</entry><entry>mm</entry><entry>= bitlength (SHORT) − logm − 1;</entry></row><row><entry /><entry>SHORT</entry><entry>mask_b</entry><entry>= 1 &lt;&lt; mm;</entry></row><row><entry /><entry>SHORT</entry><entry>mask_a</entry><entry>= mask_b − 1;</entry></row><row><entry /><entry>SHORT</entry><entry>mask_o</entry><entry>= −1 &lt;&lt; (mm − 1);</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="4"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="35PT" align="left" /><colspec colname="2" colwidth="42PT" align="left" /><colspec colname="3" colwidth="119PT" align="left" /><tbody valign="top"><row><entry /><entry>SHORT</entry><entry>clock</entry><entry>= 0, repeat = 1;;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>bool pl, ph, rl = 0, rh = 0;</entry></row><row><entry /><entry>while (repeat) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="35PT" align="left" /><colspec colname="1" colwidth="182PT" align="left" /><tbody valign="top"><row><entry /><entry>pl = rl</entry></row><row><entry /><entry>ph = rh;</entry></row><row><entry /><entry>if (clock == 0) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="49PT" align="left" /><colspec colname="1" colwidth="168PT" align="left" /><tbody valign="top"><row><entry /><entry>clock = 1;</entry></row><row><entry /><entry>if (ch &amp; mask_b) {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="63PT" align="left" /><colspec colname="1" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>repeat = 0;</entry></row><row><entry /><entry>continue;</entry></row><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="49PT" align="left" /><colspec colname="1" colwidth="168PT" align="left" /><tbody valign="top"><row><entry /><entry>rl = carry (cl + bl + ph);</entry></row><row><entry /><entry>cl += bl;</entry></row><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="35PT" align="left" /><colspec colname="1" colwidth="182PT" align="left" /><tbody valign="top"><row><entry /><entry>else {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="49PT" align="left" /><colspec colname="1" colwidth="168PT" align="left" /><tbody valign="top"><row><entry /><entry>rl = carry (cl + bl + ph);</entry></row><row><entry /><entry>cl += bl + ph;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="35PT" align="left" /><colspec colname="1" colwidth="182PT" align="left" /><tbody valign="top"><row><entry /><entry>if ((ch &amp; mask_a | masK_o) == −1 &amp;&amp; rl)   {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="49PT" align="left" /><colspec colname="1" colwidth="168PT" align="left" /><tbody valign="top"><row><entry /><entry>repeat = 0;</entry></row><row><entry /><entry>continue;</entry></row><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="35PT" align="left" /><colspec colname="1" colwidth="182PT" align="left" /><tbody valign="top"><row><entry /><entry>rh = carry (ch + bh + pl);</entry></row><row><entry /><entry>ch += bh + pl;</entry></row><row><entry /><entry>}</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="21PT" align="left" /><colspec colname="1" colwidth="196PT" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0136The masks are for preliminary zero crossing detection, and their use allows avoiding “backing-down” the functional value, since the data is not written back to ch and the LSBs of ch remain intact. The masks also allow detection of a zero crossing one clock cycle earlier.

0000Setup

0137<figref idref="DRAWINGS">FIG. 10</figref><i>c </i>is a block diagram illustrating an Edge Generator during the Bresenham setup phase, according to an embodiment of the present invention. The division algorithm was described above under “Special Case”, and is implemented as follows: <tables id="TABLE-US-00014" num="14"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="56PT" align="left" /><colspec colname="1" colwidth="161PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>// after moving down</entry></row><row><entry /><entry>setup:</entry></row><row><entry /><entry>ch &amp;= ˜ (mask_a | mask_b);</entry></row><row><entry /><entry>// setup</entry></row><row><entry /><entry>while (m != 0) {</entry></row><row><entry /><entry> BOOL c0l_c = carry (c0l + a);</entry></row><row><entry /><entry> if (!c0l_c) c0l += a;</entry></row><row><entry /><entry> c0l &lt;&lt;= 1;</entry></row><row><entry /><entry> c0l |= carry (c0h &lt;&lt; 1);</entry></row><row><entry /><entry> c0h &lt;&lt;= 1;</entry></row><row><entry /><entry> c0h |= !c0l_c;</entry></row><row><entry /><entry> BOOl c1l_c = carry (c1l + a);</entry></row><row><entry /><entry> if (!c1l_c) c1l += a;</entry></row><row><entry /><entry> c1l &lt;&lt;= 1;</entry></row><row><entry /><entry> c1l |= carry (c1h &lt;&lt; 1);</entry></row><row><entry /><entry> c1h &lt;&lt;= 1;</entry></row><row><entry /><entry> c1h |= !c1l_c;</entry></row><row><entry /><entry> BOOL bl_c = carry (bl + a);</entry></row><row><entry /><entry> if (!c0l_c) c01 += a;</entry></row><row><entry /><entry> bl &lt;&lt;= 1;</entry></row><row><entry /><entry> bl |= carry (bh &lt;&lt; 1);</entry></row><row><entry /><entry> bh &lt;&lt;= 1;</entry></row><row><entry /><entry> bh |= !bl_c;</entry></row><row><entry /><entry> m = m − 1;</entry></row><row><entry /><entry> }</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Bresenham Walk

0138After the Bresenham setup process completes, the four values ch, cl, bh and bl are produced, indicating the Bresenham error, x₀, positive correction value and Δx, respectively. To perform edge generation we also need a negative correction value r₁. The Loader <b>102</b> sets the Boolean variables dir and cor. Setting the variable dir to 1 indicates that the Edge Generator <b>103</b> subtracts the x value from W. Setting the cor variable to 1 indicates that the Edge Generator <b>103</b> adds 1 to the x value. If the x value overflows, an appropriate flag is set depending on the value of the dir variable. <tables id="TABLE-US-00015" num="15"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>// after setup</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="112PT" align="left" /><colspec colname="2" colwidth="91PT" align="left" /><tbody valign="top"><row><entry /><entry>SHORT fm = (1 << m) − 1;</entry><entry>// negation mask =</entry></row><row><entry /><entry>W − 1</entry></row><row><entry /><entry>SHORT nm = (dir)? fm : 0;</entry><entry>// negate if dir</entry></row><row><entry /><entry>== 1</entry></row><row><entry /><entry>SHORT om = ˜fm;   //</entry><entry>overflow mask to</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><tbody valign="top"><row><entry /><entry>detect x < 0 or x >= W</entry></row><row><entry /><entry>#define er ch</entry></row><row><entry /><entry>#define x0 cl</entry></row><row><entry /><entry>#define r0 bh</entry></row><row><entry /><entry>#define r1 a</entry></row><row><entry /><entry>#define dx bl</entry></row><row><entry /><entry>x0 = (nm {circumflex over ( )} x0) + cor; // x0 = W − 1 − x0 + cor</entry></row><row><entry /><entry>if (dir)</entry></row><row><entry /><entry>  dx = ˜dx;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="49PT" align="left" /><colspec colname="2" colwidth="154PT" align="left" /><tbody valign="top"><row><entry /><entry>r1 = a + b;</entry><entry> // a is negative, so r1 = |b| − |a|</entry></row><row><entry /><entry>// er = er + a;</entry><entry>// but we perform it later at first clock of</entry></row><row><entry /><entry>//</entry><entry>// Bresenham</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><tbody valign="top"><row><entry /><entry>// at this point some values are moving to different</entry></row><row><entry /><entry>registers</entry></row><row><entry /><entry>// according to general structure of the EG</entry></row><row><entry /><entry>// first clock</entry></row><row><entry /><entry>SHORT clock = 0;</entry></row><row><entry /><entry>BOOL uf = false, ov = false;</entry></row><row><entry /><entry>while (1) {</entry></row><row><entry /><entry>  if (x0 & om)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="119PT" align="left" /><colspec colname="2" colwidth="84PT" align="left" /><tbody valign="top"><row><entry /><entry>    if (dir) uf = true;</entry><entry>// x0 must be</entry></row><row><entry /><entry>negative</entry></row><row><entry /><entry>    else  ov = true; //</entry><entry>x0 must be >= W</entry></row><row><entry /><entry>  if (uf ∥ ov) continue;//</entry><entry>do not update</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><tbody valign="top"><row><entry /><entry>registers</entry></row><row><entry /><entry>  if (clock == 0) {</entry></row><row><entry /><entry>    clock = 1;</entry></row><row><entry /><entry>    x0 += dx + dir;</entry></row><row><entry /><entry>    er += r1;</entry></row><row><entry /><entry>    }</entry></row><row><entry /><entry>  else {</entry></row><row><entry /><entry>    x0 += dx + (er >= 0)? 1 − dir : dir;</entry></row><row><entry /><entry>    er += (er >= 0)? r1 : r0;</entry></row><row><entry /><entry>    }</entry></row><row><entry /><entry>  }</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Divider-by-3

0139For the Scissoring Box, a divider-by-3 is used to multiply the y offset by ⅓. A pseudo-code for a 15-bit divider-by-3 is as follows: <tables id="TABLE-US-00016" num="16"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>#define bit(a,n,m) ((a >> n) & ((1 << (m − n + 1)) − 1))</entry></row><row><entry /><entry>  // not correct in terms of the ANSI C, but works in our</entry></row><row><entry /><entry>case</entry></row><row><entry /><entry>#define bitrev(a) (((a & 2) >> 1) | ((a & 1) << 1))</entry></row><row><entry /><entry>#define simp(a,b,c,d) ((˜d & ˜c & b | c & a | d & ˜b & ˜a)</entry></row><row><entry /><entry>& 1)</entry></row><row><entry /><entry>  // single-bit operation</entry></row><row><entry /><entry>#define remh(a,b) simp (a, a >> 1, b, b >> 1)</entry></row><row><entry /><entry>#define reml(a,b) simp (a >> 1, a, b >> 1, b)</entry></row><row><entry /><entry>#define rems(a,b) ((remh (a, b) << 1) | reml (a, b))</entry></row><row><entry /><entry>#define sim1(a,b,c) ((˜c & b | c & ˜b & ˜a) & 1)</entry></row><row><entry /><entry>  // single-bit operation</entry></row><row><entry /><entry>#define sim2(a,b,c) ((˜c & a | c & b   ) & 1)</entry></row><row><entry /><entry>  // single-bit operation</entry></row><row><entry /><entry>#define remc(a,b) sim1 (a, a >> 1, b)</entry></row><row><entry /><entry>#define remd(a,b) sim2 (a, a >> 1, b)</entry></row><row><entry /><entry>#define reme(a,b) ((remc (a, b) << 1) | remd (a, b))</entry></row><row><entry /><entry>#define remf(a,b) bitrev (reme (bitrev (a), b))</entry></row><row><entry /><entry>bit16 div (bit15 a) {</entry></row><row><entry /><entry>bit15 c = a & 0x2aaa, d = a & 0x1555;</entry></row><row><entry /><entry>  c = (c & ˜(d << 1)) | (˜(c >> 1) & d);  // canonise</entry></row><row><entry /><entry>bit1</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="28PT" align="left" /><colspec colname="1" colwidth="189PT" align="left" /><tbody valign="top"><row><entry /><entry>a14 = bit (a, 14, 14),</entry></row><row><entry /><entry>a13 = bit (a, 13, 13),</entry></row><row><entry /><entry>a11 = bit (a, 11, 11),</entry></row><row><entry /><entry>a09 = bit (a, 9, 9),</entry></row><row><entry /><entry>a07 = bit (a, 7, 7),</entry></row><row><entry /><entry>a05 = bit (a, 5, 5),</entry></row><row><entry /><entry>a03 = bit (a, 3, 3),</entry></row><row><entry /><entry>a01 = bit (a, 1, 1);</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><tbody valign="top"><row><entry /><entry>bit2 part0 [ 7] = {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="28PT" align="left" /><colspec colname="1" colwidth="189PT" align="left" /><tbody valign="top"><row><entry /><entry>bit (c, 0, 1), //bits 00, 01</entry></row><row><entry /><entry>bit (c, 2, 3), //bits 02, 03</entry></row><row><entry /><entry>bit (c, 4, 5), //bits 04, 05</entry></row><row><entry /><entry>bit (c, 6, 7), //bits 06, 07</entry></row><row><entry /><entry>bit (c, 8, 9), //bits 08, 09</entry></row><row><entry /><entry>bit (c, 10, 11), //bits 10, 11</entry></row><row><entry /><entry>bit (c, 12, 13) //bits 12, 13</entry></row><row><entry /><entry>},</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><tbody valign="top"><row><entry /><entry>bit2 part1 [ 8] = {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="28PT" align="left" /><colspec colname="1" colwidth="84PT" align="left" /><colspec colname="2" colwidth="105PT" align="left" /><tbody valign="top"><row><entry /><entry>rems (part0 [ 1], part0 [ 0]</entry><entry>),</entry></row><row><entry /><entry>reme (part0 [ 1], a01</entry><entry>),</entry></row><row><entry /><entry>rems (part0 [ 3], part0 [ 2]</entry><entry>),</entry></row><row><entry /><entry>reme (part0 [ 3], a05</entry><entry>),</entry></row><row><entry /><entry>rems (part0 [ 5], part0 [ 4]</entry><entry>),</entry></row><row><entry /><entry>reme (part0 [ 5], a09</entry><entry>),</entry></row><row><entry /><entry>remf (part0 [ 6], a14</entry><entry>),</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="28PT" align="left" /><colspec colname="1" colwidth="189PT" align="left" /><tbody valign="top"><row><entry /><entry>a13 & ˜a14</entry></row><row><entry /><entry>},</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><tbody valign="top"><row><entry /><entry>bit2 part2 [ 8] = {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="28PT" align="left" /><colspec colname="1" colwidth="21PT" align="left" /><colspec colname="2" colwidth="168PT" align="left" /><tbody valign="top"><row><entry /><entry>rems</entry><entry>(part1 [ 2], part1 [ 0]),</entry></row><row><entry /><entry>rems</entry><entry>(part1 [ 2], part1 [ 1]),</entry></row><row><entry /><entry>rems</entry><entry>(part1 [ 2], part0 [ 1]),</entry></row><row><entry /><entry>reme</entry><entry>(part1 [ 2], a03    ),</entry></row><row><entry /><entry>rems</entry><entry>(part1 [ 6], part1 [ 4]),</entry></row><row><entry /><entry>remh</entry><entry>(part1 [ 6], part1 [ 5]),</entry></row><row><entry /><entry>reml</entry><entry>(part1 [ 6], part0 [ 5]),</entry></row><row><entry /><entry>remc</entry><entry>(part1 [ 6], all    ),</entry></row><row><entry /><entry>},</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><tbody valign="top"><row><entry /><entry>bit2 part3 [8] = {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="28PT" align="left" /><colspec colname="1" colwidth="21PT" align="left" /><colspec colname="2" colwidth="168PT" align="left" /><tbody valign="top"><row><entry /><entry>rems</entry><entry>(part2 [ 4], part2 [ 0]),</entry></row><row><entry /><entry>remh</entry><entry>(part2 [ 4], part2 [ 1]),</entry></row><row><entry /><entry>reml</entry><entry>(part2 [ 4], part2 [ 2]),</entry></row><row><entry /><entry>remh</entry><entry>(part2 [ 4], part2 [ 3]),</entry></row><row><entry /><entry>reml</entry><entry>(part2 [ 4], part1 [ 2]),</entry></row><row><entry /><entry>remh</entry><entry>(part2 [ 4], part1 [ 3]),</entry></row><row><entry /><entry>reml</entry><entry>(part2 [ 4], part0 [ 3]),</entry></row><row><entry /><entry>remc</entry><entry>(part2 [ 4], a07    )</entry></row><row><entry /><entry>};</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><tbody valign="top"><row><entry /><entry>bit14 m = bit (a, 0, 13) {circumflex over ( )} (</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="42PT" align="left" /><colspec colname="1" colwidth="175PT" align="left" /><tbody valign="top"><row><entry /><entry>((part3 [ 0] & 1) << 0) |</entry></row><row><entry /><entry>((part3 [ 1] & 1) << 1) |</entry></row><row><entry /><entry>((part3 [ 2] & 1) << 2) |</entry></row><row><entry /><entry>((part3 [ 3] & 1) << 3) |</entry></row><row><entry /><entry>((part3 [ 4] & 1) << 4) |</entry></row><row><entry /><entry>((part3 [ 5] & 1) << 5) |</entry></row><row><entry /><entry>((part3 [ 6] & 1) << 6) |</entry></row><row><entry /><entry>((part3 [ 7] & 1) << 7) |</entry></row><row><entry /><entry>((part2 [ 4] & 1) << 8) |</entry></row><row><entry /><entry>((part2 [ 5] & 1) << 9) |</entry></row><row><entry /><entry>((part2 [ 6] & 1) << 10) |</entry></row><row><entry /><entry>((part2 [ 7] & 1) << 11) |</entry></row><row><entry /><entry>((part1 [ 6] & 1) << 12) |</entry></row><row><entry /><entry>((part1 [ 7] & 1) << 13));</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="28PT" align="left" /><colspec colname="1" colwidth="189PT" align="left" /><tbody valign="top"><row><entry /><entry>return (m << 2) | part3 [0]; // pack the reminder</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><tbody valign="top"><row><entry /><entry>together</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="28PT" align="left" /><colspec colname="1" colwidth="189PT" align="left" /><tbody valign="top"><row><entry /><entry>}</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Scissoring Box and Synchronization

0140<figref idref="DRAWINGS">FIG. 11</figref><i>a </i>is a block diagram illustrating a Scissoring Box origin, according to an embodiment of the present invention. The Span Generator <b>101</b> comprises a Scissoring Box module <b>107</b> for providing scissoring by a view-port, rotated relative to the x and y axes by an angle with tangent 0, 1, ½ and ⅓ (hereinafter also referred to as tangent 0, 1, 2, 3, respectively). The vertical coordinate y₀of the upper-left corner of the rotated Scissoring Box is 0, and the horizontal coordinate x₁of the lower-left corner is also 0. Optionally, the Scissoring Box can be used in an optional embodiment of the present invention having an over-sampling scheme.

0141The Scissoring Box has its origin specified by four points. The coordinates of the points are calculated by the driver (i.e. the software controlling the graphics chip) and stored in registers. The y coordinate of the upper corner is y₀=0. The Scissoring Box device performs calculation of the initial Scissoring Box coordinates for the first span. After that, the Scissoring Box device calculates up to eight Scissoring Box coordinates per clock cycle for current spans.

0142<figref idref="DRAWINGS">FIG. 11</figref><i>b </i>is a block diagram illustrating a Scissoring Box, according to an embodiment of the present invention. The device to draw the Scissoring Box generates spans between two edges of the Scissoring Box. Two parts of the Scissoring Box generate both edges using the information about starting values of x and y coordinates, y coordinates of corners and rotation angle tangent: <tables id="TABLE-US-00017" num="17"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="35PT" align="left" /><colspec colname="1" colwidth="182PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>void ScissoringBox (</entry></row><row><entry /><entry> SHORT x0,  //starting left x</entry></row><row><entry /><entry> SHORT x1,  //starting right x</entry></row><row><entry /><entry> SHORT y,  //starting y (Ymin)</entry></row><row><entry /><entry> SHORT y0, //y coordinate for left corner</entry></row><row><entry /><entry> SHORT y1, //y coordinate for right corner</entry></row><row><entry /><entry> SHORT y2, //ending y (Ymax)</entry></row><row><entry /><entry> char t){ //2-bit tangent expression</entry></row><row><entry /><entry> char cnt0 = t, cnt1 = t;</entry></row><row><entry /><entry> while (y < y2) {</entry></row><row><entry /><entry>  bool m0 = y >= y0;</entry></row><row><entry /><entry>  x0 += (t)? ((m0)? t : (cnt0)? 0 : −1) : 0;</entry></row><row><entry /><entry>  cnt0 = (m0)? t : (cnt0)? cnt0 − 1 : cnt0;</entry></row><row><entry /><entry>  bool m1 = y < y1;</entry></row><row><entry /><entry>  x1 += (t)? ((m1)? t : (cnt1)? 0 : −1) : 0;</entry></row><row><entry /><entry>  cnt1 = (m1)? t : (cnt1)? cnt1 − 1 : cnt1;</entry></row><row><entry /><entry>  }</entry></row><row><entry /><entry> }</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> The pair of the coordinates x₀, x₁is then sorted among the edge coordinates by Edge Generator <b>103</b>. <br /> Sorter

0143As illustrated in <figref idref="DRAWINGS">FIG. 7</figref>, a Sorter <b>104</b> is a four-input tree compare/multiplex hardware device, three inputs of which are coupled to outputs of three Edge Generators <b>103</b> operating within the same clock cycle, and one input of which is coupled to an output of the Sorter <b>104</b> operating in the previous clock cycle. In an embodiment comprising four groups of Edge Generators <b>103</b> there are four Sorters <b>104</b>. Each Edge Generator <b>103</b> delivers the direction of a half-plane (left or right) as a tag for the x coordinate value. A Sorter <b>104</b> compares x values for edges of different types separately. <tables id="TABLE-US-00018" num="18"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="56PT" align="left" /><colspec colname="2" colwidth="147PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="2" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>typedef struct</entry><entry>{ //the output of an EG</entry></row><row><entry /><entry>  int x,</entry><entry>//the position</entry></row><row><entry /><entry>  bool uf, ov;</entry><entry>//beyond the bounding box</entry></row><row><entry /><entry>  bool dir;</entry><entry>//left (0) or right (1)</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><tbody valign="top"><row><entry /><entry>  } edge_out;</entry></row><row><entry /><entry>class temp_span {</entry></row><row><entry /><entry>public:</entry></row><row><entry /><entry>  int x0, x1; //left and right</entry></row><row><entry /><entry>  bool uf0, ov0;// left beyond the bounding box</entry></row><row><entry /><entry>  bool uf1, ov1;// right beyond the bounding box</entry></row><row><entry /><entry>  temp_span ( ) :</entry></row><row><entry /><entry>    x0 = 0, x1 = 0,</entry></row><row><entry /><entry>    uf0 = false, ov0 = false,</entry></row><row><entry /><entry>    uf1 = false, ov1 = false { };</entry></row><row><entry /><entry>  temp_span (edge_out ed) : temp_span ( ) {</entry></row><row><entry /><entry>    if (ed. dir){// if the edge is right, then it is the</entry></row><row><entry /><entry>maximal x</entry></row><row><entry /><entry>      x1 = ed. x;</entry></row><row><entry /><entry>      uf1 = ed. uf;</entry></row><row><entry /><entry>      ov1 = ed. ov;</entry></row><row><entry /><entry>      }</entry></row><row><entry /><entry>    else   {// if the edge is left , then it is the</entry></row><row><entry /><entry>minimal x</entry></row><row><entry /><entry>      x0 = ed. x;</entry></row><row><entry /><entry>      uf0 = ed. uf;</entry></row><row><entry /><entry>      ov0 = ed. ov;</entry></row><row><entry /><entry>      }</entry></row><row><entry /><entry>    };</entry></row><row><entry /><entry>  };</entry></row><row><entry /><entry>temp_span sort_two (</entry></row><row><entry /><entry>  temp_span s0,</entry></row><row><entry /><entry>  temp_span s1</entry></row><row><entry /><entry>  ) {</entry></row><row><entry /><entry>  temp_span result;</entry></row><row><entry /><entry>  bool x0m = s0. uf0 ∥ s1. ov0 ∥ // compare flags</entry></row><row><entry /><entry>    (!s1. uf0 && !s0. ov0 && s0. x0 < s1. x0); // and</entry></row><row><entry /><entry>values</entry></row><row><entry /><entry>  bool x1m = s0. ov1 ∥ s1. uf1 ∥</entry></row><row><entry /><entry>    (!s1. ov1 && !s0. uf1 && s0. x1 >= s1. x1);</entry></row><row><entry /><entry>  result. x0 = (x0m)? s1. x0 : s0. x0; // max of left</entry></row><row><entry /><entry>  result. uf0 = (x0m)? s1. uf0 : s0. uf0;</entry></row><row><entry /><entry>  result. ov0 = (x0m)? s1. ov0 : s0. ov0;</entry></row><row><entry /><entry>  result. x1 = (x1m)? s1. x1 : s0. x1; // min of</entry></row><row><entry /><entry>right</entry></row><row><entry /><entry>  result. uf1 = (x1m)? s1. uf1 : s0. uf1;</entry></row><row><entry /><entry>  result. ov1 = (x1m)? s1. ov1 : s0. ov1;</entry></row><row><entry /><entry>  return result;</entry></row><row><entry /><entry>  }</entry></row><row><entry /><entry>temp_span sorter {</entry></row><row><entry /><entry>  temp_span s0, //The output of the previous Sorter</entry></row><row><entry /><entry>  edge_out  x1, //The first EG output</entry></row><row><entry /><entry>  edge_out  x2, //The second EG output</entry></row><row><entry /><entry>  edge_out  x3 //The third EG output</entry></row><row><entry /><entry>  ) {</entry></row><row><entry /><entry>  temp_span s1 (x1), s2 (x2), s3 (x3);</entry></row><row><entry /><entry>  return sort_two (</entry></row><row><entry /><entry>    sort_two (s0, s1),</entry></row><row><entry /><entry>    sort_two (s2, s3)</entry></row><row><entry /><entry>    );</entry></row><row><entry /><entry>  }</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables><br /> Span Buffer Interface

0144The Span Buffer interface (also known as the Output Interface <b>106</b> shown in <figref idref="DRAWINGS">FIG. 7</figref>) converts the last Sorter output to absolute coordinates (note that the values are bounding box relative from the Loaders <b>102</b> through the Sorters <b>104</b>) and packs them into the Span Buffer.

0145At this point of the span generation process, the computed values comprise the output of the last Sorter s3 and the bypassed outputs of the three other Sorters s0, s1 and s2. Also available are the current y coordinate, the x_minand X_maxparameters of the bounding box, and k=1, 2, 4 representing the number of Edge Generators <b>103</b> computing spans for the same functional. Also note that the Sorters 104 are doubled, since at the lowest rate there are two spans generated per clock cycle, and therefore two spans are processed per clock cycle in parallel. <tables id="TABLE-US-00019" num="19"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><thead><row><entry /><entry /></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry /><entry>bool wf;    //wire-frame mode wf == true</entry></row><row><entry /><entry>bool update = true; //when a new triangle starts SB should</entry></row><row><entry /><entry>get new y</entry></row><row><entry /><entry>SHORT xMax, xMin;</entry></row><row><entry /><entry>SHORT y;    //from the current y counter</entry></row><row><entry /><entry>SHORT w = xMax − xMin;    // The real</entry></row><row><entry /><entry>bounding box size</entry></row><row><entry /><entry>typedef struct {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="3"><colspec colname="OFFSET" colwidth="28PT" align="left" /><colspec colname="1" colwidth="42PT" align="left" /><colspec colname="2" colwidth="147PT" align="left" /><tbody valign="top"><row><entry /><entry>x0, x1;</entry><entry>// the values −1 and −2 are reserved for</entry></row><row><entry /><entry /><entry>// uf and ov accordingly.</entry></row><row><entry /><entry>} span;</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="OFFSET" colwidth="14PT" align="left" /><colspec colname="1" colwidth="203PT" align="left" /><tbody valign="top"><row><entry /><entry>SHORT sb_cnt = 0; //the counter of position in SB row</entry></row><row><entry /><entry>span spare_buffer [16];</entry></row><row><entry /><entry>void WriteNextToSB (</entry></row><row><entry /><entry>  span sp, //span to write</entry></row><row><entry /><entry>  SHORT pos, //position in the SB row</entry></row><row><entry /><entry>  bool next //next row</entry></row><row><entry /><entry>  );</entry></row><row><entry /><entry>void move_sb_cnt ( ) {</entry></row><row><entry /><entry>  sb_cnt ++;</entry></row><row><entry /><entry>  if (sb_cnt >= 8) {</entry></row><row><entry /><entry>   Span_Buffer. Write (       // see TG doc</entry></row><row><entry /><entry>for description</entry></row><row><entry /><entry>    spare_buffer,</entry></row><row><entry /><entry>    y & (0xfffffff0 ∥ wf << 3),  // y is aligned</entry></row><row><entry /><entry>    update, // update y if necessary</entry></row><row><entry /><entry>    wf,  // wire-frame</entry></row><row><entry /><entry>    update);</entry></row><row><entry /><entry>   update = false;</entry></row><row><entry /><entry>   sb_cnt = 0;</entry></row><row><entry /><entry>  }</entry></row><row><entry /><entry>}</entry></row><row><entry /><entry>void sb_interface (</entry></row><row><entry /><entry>  temp_span s [8], //two first - from the first level</entry></row><row><entry /><entry>Sorter,</entry></row><row><entry /><entry>         // two next - from second level, etc.</entry></row><row><entry /><entry>  SHORT  y,  //from the y counter</entry></row><row><entry /><entry>  SHORT  xmin, //from the input</entry></row><row><entry /><entry>  SHORT  xmax, //from the input</entry></row><row><entry /><entry>  SHORT  k //from the input</entry></row><row><entry /><entry>  ) {</entry></row><row><entry /><entry>  int j;</entry></row><row><entry /><entry>  span sp [8]; //temporary spans</entry></row><row><entry /><entry>  //actually the following is performed at Sorters outputs</entry></row><row><entry /><entry>  for (j = 0; j < 8; j ++)     {</entry></row><row><entry /><entry>   sp [j]. x0 =</entry></row><row><entry /><entry>    (s [j]. ov0)? MAX_INT :</entry></row><row><entry /><entry>    (s [j]. uf0)? −1 :</entry></row><row><entry /><entry>    (s [j]. x0 > w)? MAX_INT : s [j]. x0 + xMin;</entry></row><row><entry /><entry>   sp [j]. x1 =</entry></row><row><entry /><entry>    (s [j]. ov1)? MAX_INT :</entry></row><row><entry /><entry>    (s [j]. uf1)? −1 :</entry></row><row><entry /><entry>    (s [j]. x1 > w)? MAX_INT : s [j]. x1 + xMin;</entry></row><row><entry /><entry>   }</entry></row><row><entry /><entry>  if (update) {</entry></row><row><entry /><entry>   sb_cnt = y & (wf)? 0x7 : 0xf;</entry></row><row><entry /><entry>   for (j = 0; j < 16)</entry></row><row><entry /><entry>    spare_buffer [j]. x0 = spare_buffer [j]. x1 = 0;</entry></row><row><entry /><entry>   }</entry></row><row><entry /><entry>  if (wf) {</entry></row><row><entry /><entry>    bool empty [4]; //empty flags for all 4 spans of the</entry></row><row><entry /><entry>          // internal triangle</entry></row><row><entry /><entry>    for (j = 0; j < 4; j ++) {</entry></row><row><entry /><entry>     empty [j] =</entry></row><row><entry /><entry>      s [j + 4]. x0 == MAX_INT ∥</entry></row><row><entry /><entry>      s [j + 4]. x1 == −1 ∥</entry></row><row><entry /><entry>      s [j + 4]. x0 > s [j + 4]. x1;</entry></row><row><entry /><entry>     spare_buffer [sb_cnt + j ]. x0 = sp [j]. x0;</entry></row><row><entry /><entry>     if (empty [j]) {</entry></row><row><entry /><entry>      spare_buffer [sb_cnt + j ]. x1 = sp [j ].</entry></row><row><entry /><entry>x1;</entry></row><row><entry /><entry>      spare_buffer [sb_cnt + j + 8]. x0 = MAX_INT;</entry></row><row><entry /><entry>      spare_buffer [sb_cnt + j + 8]. x1 = −1;</entry></row><row><entry /><entry>      }</entry></row><row><entry /><entry>     else {</entry></row><row><entry /><entry>      spare_buffer [sb_cnt + j ]. x1 = sp [j + 4].</entry></row><row><entry /><entry>x0;</entry></row><row><entry /><entry>      spare_buffer [sb_cnt + j + 8]. x0 = sp [j + 4].</entry></row><row><entry /><entry>x1;</entry></row><row><entry /><entry>      spare_buffer [sb_cnt + j + 8]. x1 = sp [j ].</entry></row><row><entry /><entry>x1;</entry></row><row><entry /><entry>      }</entry></row><row><entry /><entry>    move_sb_cnt ( );</entry></row><row><entry /><entry>    }</entry></row><row><entry /><entry>    sb_cnt = (sb_cnt + 4);</entry></row><row><entry /><entry>    return;</entry></row><row><entry /><entry>    }</entry></row><row><entry /><entry>   for (j = (k − 1) * 2; j < k * 2; j ++) {</entry></row><row><entry /><entry>    if (k == 2 && j == 4)    // when k == 2 we</entry></row><row><entry /><entry>use first and third</entry></row><row><entry /><entry>      j == 6;    // sorters outputs</entry></row><row><entry /><entry>    spare_buffer [sb_cnt] = sp [j];</entry></row><row><entry /><entry>    move_sb_cnt ( );</entry></row><row><entry /><entry>    }</entry></row><row><entry /><entry>   }</entry></row><row><entry /><entry namest="OFFSET" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0146Foregoing described embodiments of the invention are provided as illustrations and descriptions. They are not intended to limit the invention to precise form described. In particular, it is contemplated that functional implementation of invention described herein may be implemented equivalently in hardware, software, firmware, and/or other available functional components or building blocks, and that networks may be wired, wireless, or a combination of wired and wireless. The pseudo-code fragments represent high-level implementation examples and are intended to illustrate one way of implementing functionalities described herein. Other variations and embodiments are possible in light of above teachings, and it is thus intended that the scope of invention not be limited by this Detailed Description, but rather by Claims following.