CN112116715A - Method and apparatus for efficient interpolation - Google Patents

Abstract

The method for interpolating the attribute values of the image grid may comprise: determining a root value of an attribute of a root node located at the center of the image grid; pre-computing metadata for a plurality of child nodes of one or more levels based on the one or more gradients of the attributes; and deriving an attribute value for each child node of each hierarchy based on the corresponding root value and metadata of the hierarchy for each child node, wherein each child node can serve as a root node for a next hierarchy. The image grid may have a plurality of outer cells radially arranged around a center cell, and the root node may be located in the center cell.

Description

Method and apparatus for efficient interpolation

technical field

The present disclosure relates generally to interpolation, and more particularly to methods and apparatus for efficient interpolation of nodes in grids, such as image grids.

Background technique

Interpolation is the process of determining attribute values for unknown data points that lie between known data points. In image processing, for example, interpolation can be used to find intermediate values of properties of a collection of pixels that are spatially adjacent to each other and inside primitives, which are geometric basic units used to create larger images. Interposers consume resources such as power and area on integrated circuits. The high cost and power consumption of traditional interpolators can limit throughput or the speed at which pixels can be rendered. However, displays continue to offer higher resolutions, use more primitives and/or work on larger image domains than the regular tile domain, which is a subset of the image. In addition, downstream image processing devices, such as execution units, that use and/or transform data from the interpolator continue to improve. This can create a mismatch between the bandwidth of the interpolator and the bandwidth of the downstream unit, which can lead to low utilization of the downstream unit and/or low frame rate on the rendering device. Therefore, there is a need for an interpolator that can operate with higher efficiency and/or throughput.

SUMMARY OF THE INVENTION

A method for interpolating an attribute value of an image grid, the method comprising: determining a first-level root value of an attribute at a first-level root node at the center of the image grid; a gradient and a second gradient of the attribute in the second direction to calculate first-level metadata; and based on the first-level root value and the first-level metadata, deriving an attribute of two or more first-level child nodes in the image grid A first-level child value, the two or more first-level child nodes are radially arranged around the first-level root node in the image grid. The method may further include: using one of the first-level child nodes and its corresponding first-level child value as the second-level root node and the second-level root value of the cell of the image grid, wherein the root node of the cell is located in the cell the center of , two or more secondary child nodes are arranged radially around the secondary root node in the cell.

Each first-level child node may be offset symmetrically from the first-level root node in the first direction and the second direction. Each first-level child node may be offset from the first-level root node by substantially zero or substantially the same distance in the first direction and the second direction. The image grid can include a 3x3 cell array with a center cell and eight outer cells, two or more first-level children can include eight first-level children, and a first-level root node can be located at the center of the center cell. The center, and each first-level child node can be in the center of one of the outer cells. The primary metadata may include delta values for attributes of offsets in the first and second directions. The value of the first parameter A may be based on the first gradient, and the value of the second parameter B may be based on the second gradient. Primary metadata may include the values A, B, A+B, and A-B. The value of the first parameter A may be based on the first gradient, the value of the second parameter B may be based on the second gradient, the image grid includes a 3x3 cell array, and the primary metadata may include the values 3A, 3B, 3(A+B) and 3(A-B), and secondary metadata may include the values A, B, A+B, and A-B. The primary metadata can be calculated based on a plane equation. The plane equation can be of the form P(x,y)=A*(x-Seed_X)+B*(y-Seed_Y)+C, where P can be a two-dimensional interpolation at each position (x,y) Parameters of a dimensional surface, where x can be the distance in the x direction, y can be the distance in the y direction, A can be the gradient per pixel (or other cell) in the x direction, and B can be the gradient in the y direction Gradient per pixel (or other cell), and C can be the value of P at position (Seed_X, Seed_Y). Deriving the first-level child value may include adding one or more first-level metadata to the first-level root value. The first-level root node and each first-level child node may correspond to a pixel. The first-level root node and each first-level child node may correspond to a sample. The method may also include rasterizing the image in response to the attribute value. The attribute may include a first value indicating that the node may be inside the primitive and a second value indicating that the node may be outside the primitive.

A method for interpolating attribute values of an image grid may include: determining a root value of an attribute of a root node located at the center of the image grid; precomputing in one or more levels based on one or more gradients of the attribute metadata of a plurality of child nodes; and deriving attribute values of each child node of each level based on the corresponding root value and metadata of the level of each child node; wherein each child node can be used as the root node of the next level. The image grid may have a plurality of outer cells arranged radially around the central cell, and the root node may be located in the central cell. The root node may be located in a first cell having one or more additional nodes, and the method may further include: determining attribute values of the one or more additional nodes in the first cell; and deriving the first cell associated with each hierarchy level The attribute value of the additional child node corresponding to each additional node in the cell, wherein the attribute value of each additional child node can be derived based on the attribute value of the corresponding additional node in the first cell and the metadata of the corresponding level. Attribute values for additional child nodes may be derived through a separate hierarchical tree for each node in the first cell. The first cell may be a pixel, and each node in the first cell may be a sample. The samples in the pixel can be used for multi-sample anti-aliasing (MSAA).

The system for interpolating attribute values of an image grid may include: a root unit configured to determine a root value of an attribute of a root node located at the center of the image grid; a metadata unit configured to be based on one of the attributes or A plurality of parameters, metadata for a plurality of child nodes are precomputed in one or more hierarchies, and a tree of one or more logical stages coupled to the root unit and the metadata unit and configured to be based on The corresponding root value and metadata of the hierarchy of each child node derives the attribute value of each child node of each hierarchy. One or more of the logic stages may include combinatorial logic with a two-input adder, arranged to add the root value of the attribute to the metadata of the plurality of child nodes. The system may also include a redirection unit coupled between the root unit and the tree and configured to rearrange the manner in which the samples are directed from the root unit to the tree based on the mode of operation. The logic stage may be configured to process multiple samples in a multi-sample mode of operation. The image grid may be a first sub-grid of a larger image grid, and the system may further include: a second root unit configured to determine a second root centered on the second sub-grid of the larger image grid a second root value of a second attribute of the node; a second metadata unit configured to pre-compute second elements of a plurality of second child nodes in one or more hierarchies based on one or more parameters of the second attribute data; and a second tree of one or more logical stages coupled to the second root unit and the second metadata unit and configured to The second root value and the second metadata, the second attribute value of each second child node at each level is derived. The second root unit, the second tree, and the second metadata unit may be configured to selectively use properties of the first sub-grid as second properties of the second sub-grid. The properties of the first subgrid and the second subgrid can be used for different primitives. The system may also include one or more additional logic stages coupled between the root cell and the tree in a serial hybrid configuration, wherein the one or more additional logic stages use a substantially different tree than the one or more logic stages interpolation technique. The system may be implemented in hardware, software, or a combination thereof. Hardware may include integrated circuits.

The means for interpolating attribute values of an image grid may include a tree of one or more logical stages configured to be based on corresponding attribute values at the root node and metadata for each of the one or more levels, Attribute values for a plurality of child nodes around a centrally located root node at each of one or more hierarchies are derived. The apparatus may also include a metadata unit coupled to the tree of one or more logical stages and configured to pre-compute metadata for the plurality of child nodes of each of the one or more hierarchies based on the one or more parameters of the attribute. The apparatus may also include a root unit coupled to the tree of one or more logical stages and configured to determine a root value of an attribute of the root node in the image grid. One or more of the logic stages may include combinatorial logic with a two-input adder, arranged to add the root value of the attribute to the metadata of the plurality of child nodes. The apparatus may also include one or more additional logic stages coupled to the tree in a serial hybrid configuration, wherein the one or more additional logic stages use a substantially different interpolation technique than the tree of the one or more logic stages. The tree of one or more logical stages may be implemented in an integrated circuit. Other and/or additional configurations are contemplated.

Description of drawings

The drawings are not necessarily to scale and elements of similar structure or function are generally represented by like reference numerals for illustrative purposes throughout the drawings. The drawings are intended only to facilitate the description of the various embodiments described herein. The drawings do not depict every aspect of the teachings disclosed herein, and do not limit the scope of the claims. The drawings, together with the description, illustrate example embodiments of the present disclosure and, together with the description, serve to explain the principles of the present disclosure.

Figure 1 illustrates a conventional technique for interpolating attribute values of a grid of pixels.

2 illustrates an embodiment of a method of interpolating attribute values of a grid of pixels in accordance with the principles of the present disclosure.

3 is a flowchart of a method of interpolating attribute values of a grid of pixels in accordance with the principles of the present disclosure.

4 illustrates an example embodiment of a method for interpolating attribute values using a plane equation in accordance with the principles of the present disclosure.

5 illustrates an example embodiment of a method for interpolation of rasterization using boundary equations in accordance with the principles of the present disclosure.

Figure 6 illustrates an example embodiment of a method for interpolation of adjacent levels of metadata correlated by scaling factors.

7 is a block diagram illustrating a microarchitecture of the structure and data flow of an embodiment of a hierarchical interpolation system in accordance with the principles of the present disclosure.

8 is a block diagram illustrating a microarchitecture of the structure and data flow of an embodiment of a multi-sample hierarchical interpolation system in accordance with the principles of the present disclosure.

9-11 illustrate embodiments of grids that may be subdivided in accordance with the principles of the present disclosure.

12 is a block diagram illustrating a microarchitecture of the structure and data flow of an embodiment of a multi-attribute hierarchical interpolation system in accordance with the principles of the present disclosure.

FIG. 13 illustrates an embodiment of an imaging device 204 into which any of the methods or apparatus described in this disclosure may be integrated.

14 is a block diagram illustrating another microarchitecture of the structure and data flow of an embodiment of a hierarchical interpolation system in accordance with the principles of the present disclosure.

15 illustrates an embodiment of a computing system in accordance with the present disclosure.

Detailed ways

FIG. 1 illustrates a conventional technique for interpolating attribute values of a 9-pixel by 9-pixel grid 100 . The attribute value may first be determined for the lower left corner pixel at sample point 102 . The attribute values at the sample points of other pixels can then be found by traversing the grid on a pixel-by-pixel basis in the x and y directions, as indicated by the arrows in Figure 1. The attribute delta value of each pixel is added to the attribute sum value of the previous pixel. (The delta value is sometimes referred to as the attribute's "delta".) The attribute delta value for each pixel can be based on each pixel's x- and y-offset relative to the previous pixel and can be used to determine any pixel's attribute function of value.

However, the x-offset and y-offset of each pixel may be variable for each row and/or each column, so the attribute calculation for each node may require a 3-input adder, which is implemented in hardware or software It can be relatively expensive. Furthermore, the logic level for a hardware implementation of an n-pixel by n-pixel grid may be 2n. Another disadvantage may be the area required by the hardware to implement the technique of Figure 1, which may increase geometrically as the value of n increases. Additionally, hardware implementations may result in large fan-outs, which may require larger and/or more expensive drivers to avoid additional delays in computation.

2 illustrates an embodiment of a method for interpolating attribute values of an image grid in accordance with the principles of the present disclosure. The image grid may be initially divided into nine cells C1, C2, . . . , C9, which may be the highest level of the levels shown in grid 110A. Each cell may have corresponding nodes N1, N2, . . . , N9. The center cell C5 and the center node N5 may be designated as the root cell and the root node, respectively. The remaining cells C1-C4 and C6-C9, which can be arranged radially around the central cell, can be designated as child cells. The remaining nodes N1-N4 and N6-N9 can be designated as child nodes.

The method can start by determining the attribute value of the root node (root attribute). This can be accomplished in any suitable way. For example, if root node N5 happens to be a known sample point, the sample value at that point can be used as the highest-level root value. Otherwise, the root value may be calculated by interpolation from other nodes outside the image grid 110A, eg, by using general multipliers, adders, or the like. The method may calculate metadata, which may, for example, include attribute delta values for offsets in the x and y directions between the root node N5 and child nodes. For example, this can be achieved by using plane equations for properties. Then, the attribute value of each child node N1-N4 and N6-N9 can be derived from the root node N5 by combining the root value with the metadata, as shown by the arrows in FIG. 2 . For example, the attribute value of each child node can be computed by adding one or more metadata to the root value through a streamlined additive process as described below. The process of deriving attribute values in child cells is referred to as phase 1 in Figure 2.

Each of the top nine cells C1, C2, ..., C9 can be subdivided into smaller sub-cells at the next level, as shown in grid 110B, which is the subdivided Another view of the grid 110A. For example, cell C1 can be subdivided into secondary cells or sub-cells C1-1, C1-2, …C1-9. Each secondary cell may have corresponding nodes N1-1, N1-2, . . . N1-9. (To avoid obscuring the drawing, not all subdivision cells and nodes of image grid 110B are labeled in Figure 2, but the designation of each cell is evident from the conventional labeling pattern.) It is possible to Designate the center cell C1-5 and the center node N1-5 as the second-level root cell and root node, respectively. Therefore, the first-level child node N1 can be used as the second-level root node N1-5. Similarly, the derived attribute values at the primary child node N1 may be used as secondary root values for secondary root nodes N1-5. The remaining cells C1-1 to C1-4 and C1-6 to C1-9, which may be arranged radially along the center cell C1-5, may be designated as sub-cells at the secondary level. The remaining nodes N1-1 to N1-4 and N1-6 to N1-9 may be designated as child nodes at the second level.

The method can calculate the metadata of the second-level child nodes, and the metadata can include the second-level root node N1-5 and the second-level child nodes N1-1 to N1-4 and N1-6 to N1-9 in the x direction and the y direction. The property increment value for the offset in the direction. This can be done, for example, using the plane equation of the property. Then, the attribute value of each second-level child node can be derived from the second-level root value of the attribute at the second-level root node N1-5 by combining the second-level root value with the second-level metadata, as shown by the arrow in Figure 2 shown. For example, the attribute value for each secondary child node may be computed by adding one or more secondary metadata to the secondary root value through a streamlined addition process, as described below.

Similarly, each of the other primary cells C2 to C9 may be subdivided into smaller cells, each cell having its own secondary node, as shown in grid 110B. In the case of the highest-level center cell C5 in the center of the grid, the root node N5 can be used as the secondary root node N5-5 of the secondary cell C5-5. The process of deriving attribute values at secondary child cells in Figure 2 is referred to as Phase 2.

The process of subdividing cells, creating child nodes, and deriving attribute values at each child node can be repeated for any arbitrary number of levels, creating hierarchical tree structures and meshes with increasingly finer resolutions. Therefore, the interpolation can start from the root node in the center cell of the highest level, and ripple down to more and more nodes at each successively lower level. Furthermore, even though the principles of the present disclosure are not limited to the 3x3 cell arrangement of Figure 2, this particular topology (which may be described as a diagonal layered 3x3 topology) can provide many benefits as described below.

3 is a flowchart of a method for interpolating attribute values of an image grid in accordance with the principles of the present disclosure. The method may begin at the beginning 112 of the highest level of the hierarchical tree. At step 114, the method may determine the attribute value at the root node whose highest level is located at the center of the image. At step 116, metadata may be pre-computed for the plurality of child nodes of one or more hierarchies based on parameters of the attributes, such as gradients. At step 118, the method may derive attribute values for each child node of the current hierarchy based on the corresponding root values and metadata of the current hierarchy. At step 120, if the current level is not the lowest level, then at step 122 the attribute value of each child node is used as the value of the root node of the next level down to the next level, and step 118 is repeated, otherwise the process ends at 124.

The method described with respect to FIG. 3 can be modified in various ways and configured and adapted for use in a myriad of applications. For example, even though some embodiments are shown as having a 3x3 array, ie, a geometric ratio N=9, any number of nodes N may be used. Then, as additional levels are added, the number of nodes in the tree can grow geometrically according to level ¹ , N, ^N2 , N3, etc. However, in some embodiments, the tree may not grow with the same proportion of nodes at each level.

As another example, in addition to interpolating continuous attribute values, the method can also be used for rasterization to determine pixel coverage of primitives by boundary estimation (i.e. point classification or point-line distance estimation with respect to the boundary), Thereby determining that a particular sample is located inside, outside, or at the boundary of primitives, among other applications. In such applications, attributes may be, for example, binary input/output determination, ternary input/output/online determination, or the like. Cells and nodes at various levels of the hierarchy can be used to implement any combination of pixels and/or samples. For example, in some embodiments, each of the highest level cells C1, C2, ..., C9 may be used to implement a pixel with each of the highest level nodes N1 through N9, used as the initial ( primary) sample. Additional nodes can then implement additional sampling for oversampling, supersampling, multi-sample antialiasing (MSAA), etc. In some other embodiments, the smallest subdivision cells at the lowest level of the hierarchy can achieve pixels of a relatively high resolution image.

The grid can have any number of cells in each direction, so a generic n-cell by m-cell grid is provided, which may incur for example in the cost of generating and storing precomputed metadata, tree depth, etc. compromise between. In the case of a general asymmetric n-by-m grid (ie, n is not equal to m), the metadata that may be required to derive attribute values for child nodes can be assumed to be formulated as n*A, m*B, n*A+m *B, n*A-m*B.

Depending on the topology of the mesh, there may not be any secondary child nodes derived from one or more of the highest level nodes. This can happen, for example, if the top-level root node is aligned with a line dividing two cells or an intersection between four cells, like a grid with an even number of cells on one or both sides This may happen in the case of . The root node N5 is shown in the center of the grids 110A, 110B of FIG. 2, and every other node is shown in the center of its corresponding cell, although it may not be necessary to place the node in these central locations. However, in some embodiments, it may be beneficial to place the root node or other nodes in the center in the sense of being sufficiently close to the center to enable efficient creation and interpolation of child nodes and other levels of the hierarchical tree.

An example application for the method shown in Figure 2 is to use plane equations to interpolate attribute values at sample locations. Equation 1 is an example plane equation for the parameter P of a two-dimensional surface, which can be interpolated at each position (x,y) using the parameters A, B, and C that define the plane:

P(x, y)=A*(x- Seed_X )+B*(y- Seed_Y )+C (equation 1)

where A is the gradient per pixel (or other cell) in the x direction, B is the gradient per pixel (or other cell) in the y direction, and C is the value of P at position (Seed_X, Seed_Y).

4 illustrates an example embodiment of a method for interpolating attribute values using a plane equation. The embodiment of Figure 4 is described in the context of implementing samples at each node, but the principles also apply to pixels or any other type of node. The embodiment of FIG. 4 uses a 3-sample by 3-sample grid 130 of spatially adjacent samples S1 to S9 as it may provide computational benefits as described below. This method uses a plane equation, such as Equation 1, where the parameter P is used as the property to be interpolated. The method precomputes the values of metadata A, B, A+B and A-B for the specific size of the cell in Figure 4 . The attribute value at the root node may be determined in any suitable manner. For example, the attribute value at the root sample may be calculated by interpolation from other samples or nodes outside the image grid 130 using general multipliers, adders, or the like.

Once the attribute values at root sample S5 are known, and the metadata values A, B, A+B, and A-B are precomputed, the child can be derived by simply adding the following metadata values to the attribute values at root sample S5 The attribute values at samples S1-S4 and S6-S9 are shown in Figure 4: sample S1:-(A-B); sample S2:B; sample S3:A+B; sample S4:-A; sample S6:A; Sample S7:-(A+B); Sample S8:-B; and Sample S9:A-B. The simplicity of these computations can be achieved by the symmetry of the topology. That is, each subsample is located at an offset of zero or one common unit from the root sample x or y. In this embodiment, the common unit is equal to the size of the grid cells. For example, sample S6 has an x offset of 1 unit and a y offset of 0, while sample S3 has an x offset of 1 unit and a y offset of 1 unit. This arrangement of all samples offset by zero or units, even samples placed diagonally from the root, enables the use of a simple addition for each subsample. This in turn may enable the addition of each subsample to be implemented with a 2-input adder, which may reduce cost and area compared to the 3-input adder required for asymmetric delta in the conventional technique of FIG. 1 .

As shown in Figure 5, the diagonal layered 3x3 topology of Figure 4 can be adapted for rasterization. When used with rasterization, interpolation can be based on edge equations rather than plane equations, in which case metadata can be precomputed as dx, dy, dx+dy and dx-dy, where , dx may be the difference in the x direction, and dy may be the difference in the y direction. The process may start with an estimate of the boundary equation for the position at the boundary of the root value of the tree, and the samples may be pixel centers. The value of the sub-pixel as shown in grid 132 of Figure 5 can then be calculated by adding the following metadata to the starting value at pixel P5: pixel P1:-(dx-dy); pixel P2: dy; pixel P3: dx+dy; pixel P4: -dx; pixel P6: dx; pixel P7: -(dx+dy); pixel P8: -dy; pixel P9: dx-dy.

Equation 1 can be adapted for use with boundary equations, eg, by substituting dx for A, dy for B, and "start" (a boundary estimate for the boundary of a location) for C in the plane equation.

The methods of Figures 4 and 5 can be extended to additional levels, as shown in Figure 6, in which case the metadata at each level can be related to the metadata at adjacent levels by a simple scaling factor. For example, in the embodiment of Figure 6, the 3x3 grid 132 of Figure 5 may be used as a secondary subdivision cell of the primary grid 134A, and the precomputed metadata dx, dy, dx+dy and dx -dy can be used to derive secondary subpixels. (Pixels P1 to P9 may be redesignated as P1-1 to P1-9.) The precomputed metadata for primary grid 134A may be computed as 3dx, 3dy, 3(dx+dy), and 3(dx -dy). These first-level metadata can be derived from the first-level subpixels P1 to P4 and P6 to P9 by adding them to the starting value of the root pixel P5, as follows: pixel P1:-3(dx-dy); pixel P2:3dy ; Pixel P3: 3(dx+dy); Pixel P4: -3dx; Pixel P6: 3dx; Pixel P7: -3(dx+dy); Pixel P8: -3dy; Pixel P9: 3(dx-dy).

The 3x factor associated with the diagonally layered 3x3 topology can be particularly easy to implement in digital logic, since x3 multiplication can be implemented using a 2-input adder. For example, 3*x can be implemented as x+2*x, while 2*x can be implemented cheaply in floating point because 2*x can be implemented by increasing the exponent of x by 1. Similarly, if the 3x3 topology of Figure 4 is extended to another level, the precomputed metadata can be computed as 3A, 3B, 3(A+B), and 3(A-B).

7 is a block diagram illustrating a microarchitecture of the structure and data flow of an embodiment of a hierarchical interpolation system in accordance with the principles of the present disclosure. The system of FIG. 7 may be used to implement any of the methods and processes disclosed herein, but is not limited to any implementation details described in this disclosure. The system 150 includes a root unit 154 configured to compute attribute values for the root node at the highest level of the hierarchical tree topology, eg, the center sample position. The root unit 154 may compute values in response to input 152 that may depend on the particular application of the system, eg, by interpolation using general multipliers, adders, or the like. For example, when used to interpolate samples based on a plane equation, input 152 may include the parameters in Equation 1, including the parameters A, B, and C that define the plane, where A is each pixel (or other cell) in the x-direction ), B is the gradient per pixel (or other cell) in the y direction, and C is the value of P at position (Seed_X, Seed_Y). Input 152 may also include the coordinates of the root location (X_root, Y_root). The metadata unit 156 may be configured to pre-compute, in response to the input 152, metadata for deriving attribute values for child nodes, such as A, B, A+B, and A-B in the case of the plane equation, and in the case of the boundary equation dx, dy, dx+dy and dx-dy below. The metadata unit 156 may be configured to use one set of metadata for each level of the hierarchical tree. For example, if the metadata precomputed for the lowest level includes the set M={A,B,A+B,A-B}, then the set precomputed for the upper and lower levels may be M'=3*M, and for the further up The next level precomputed set may be M"=9*M, and so on.

A tree 158 of one or more logical stages, in this example having three stages 158A, 158B, and 158C, may be configured to perform computations that derive attribute values for child nodes at each level of the hierarchical topology. In this example, a 3x3 topology is assumed. Thus, the first stage 158A may be constructed to accommodate 9 nodes, the second stage 158B to accommodate 81 nodes, and the third stage 158C to be constructed to accommodate 729 nodes.

The output 160 may be in the form of an N-pixel by M-pixel interpolated output, but in other embodiments the output may have one or more arrays of different dimensions, node types, and the like. The desired bandwidth, for example, the number of samples or pixels per clock cycle or other unit of time can be N pixels in the x-direction and M pixels in the y-direction, so that the throughput is comparable to the output data that can be used and/or transformed downstream processing or execution units.

For illustrative purposes, the embodiment of Figure 7 is illustrated as a 3x3 topology with three levels, although other topologies and numbers of levels (stages) may be used. Thus, the dashed line between stage 158C and output 160 indicates additional stages that may be added. The system 150 of FIG. 7 may be implemented in hardware, software, or any combination thereof. In a hardware implementation, the logic stage tree 158 and metadata unit 156 can be implemented as combinatorial logic with a simple two-input adder that can interpolate the entire tree hierarchy, that is, in a single clock cycle Drop all nodes to the lowest level. This may result in reduced power and/or energy consumption and/or circuit area requirements. The root unit 154 may be implemented with combinatorial and synchronization logic for integration into the clock of a larger image processing system. In some hardware implementations, system 150 may be integrated into a graphics processing unit (GPU) on an integrated circuit (IC), where it may enable improved rendering frame rates.

In the case of a software implementation, the methods and architectures disclosed herein can reduce the constant scratch pad space required for addition and/or subtraction operations. In some hybrid embodiments, a series of hierarchical tree stages may be implemented in hardware and fed with root values and/or metadata provided by software.

Some other potential benefits of the system of FIG. 7 and other embodiments disclosed herein are as follows. If N is the number of samples or other nodes to interpolate per clock cycle, i.e. the number of nodes in the lowest level of the grid tree, then the logical depth of the tree can be given by the base-9 logarithm of N+1, i.e. log ₉ (N+1). This can be advantageously compared to the conventional technique of FIG. 1, in which the logical level may increase geometrically as the value of N increases. Additionally, diagonal layering, especially in 3x3 implementations, can reduce the logic level and/or critical path of additive processing. Thus, it may be advantageous for high frequency design synthesis and reduced latency due to propagation delays through one or more stages of the hierarchical tree. Furthermore, this can reduce the cost per computed value since relatively fewer metadata values may need to be stored, eg, A, B, A+B, and AB or scaled versions thereof per level.

The embodiment of FIG. 7, as well as other embodiments disclosed herein, may be implemented in a serial hybrid configuration, where conventional interpolation techniques may be used to implement one or more higher levels, eg, sequentially traversed x and y paths, as shown in FIG. 1 shown. A hybrid configuration can simplify the implementation at one or more higher levels, while still using a hierarchical tree topology at lower levels, ie near or at the bottom leaf nodes, where the cost savings of a hierarchical tree topology may be greatest. Additionally, synthesis tools in electronic design automation (EDA) platforms may be able to automatically optimize unused leaf nodes when using meshes with dimensions other than 3×3.

14 is a block diagram illustrating another microarchitecture of the structure and data flow of an embodiment of a hierarchical interpolation system in accordance with the principles of the present disclosure. The system 151 of FIG. 14 may be similar in architecture to the system 150 of FIG. ⁷ , but it may include a generalized tree 159 having stages 159A, 159B, 159C, . , I ³ nodes..., "I" can be given by I=W*Z, where W and Z can represent the number of nodes in the x-direction and y-direction, respectively. Therefore, each node can branch to 1 nodes in the next stage. As the tree grows from the root node to the leaf nodes, the number of nodes at each stage may grow according to the following patterns or series: ¹ , I, ^I2 , ^I3 , I4, . . .

The numbers I, W and Z can be chosen as constants during the design process. The embodiment of FIG. 7 can be regarded as a special case of the embodiment of FIG. 8 , where W=3, Z=3, and thus I=9.

The embodiment of FIG. 14 may be characterized as having a general logical level or tree depth given by O(logN), where N may be the number of nodes in the lowest level of the hierarchical tree, and O may indicate that the asymptotic bound may be relevant Generic complexity notation for . For example, in an embodiment where each node can branch to "I" nodes in the next stage, the logic level and thus the latency caused by the propagation delay through the stages of the tree can be given by the logarithm of N to the base 1 out, which is O(log _IN ). Depending on the implementation details, this can be compared favorably with the conventional technique of Figure 1, where the logic level can be given by O(N) as N increases. Thus, in some embodiments, a system with a generic tree topology as shown in Figure 14 can reduce the logic level and/or propagation delay/interpolation delay from O(N) to O(logN).

In some embodiments, metadata can be viewed as having three general components: an X component, a Y component, and an XY component. For example, when using boundary equations, the X, Y, and XY components may be dx, dy, and dx+/-dy, respectively. The X, Y, and XY components may be specified as META_X, META_Y, and META_X+/-META_Y, respectively. Just as moving from the root node to the leaf node, the number of nodes at each stage grows, in the opposite direction, moving from the leaf node to the root node, the metadata can grow, such as: {META_X,META_Y,META_X+/-META_Y,… },{W*META_X,Z*META_Y,W*META_X+/-Z* ^META_Y …},{W2* ^META_X ,Z2* ^META_Y ,W2* ^META_X +/-Z2* ^META_Y …},{W3* META_X,Z3* ^META_Y ,W3* ^META_X +/-Z3* ^META_Y …}….

The metadata unit 157 may be configured to use one set of metadata for each level of the hierarchical tree. For example, if the metadata precomputed for the lowest level includes the set M={META_X,META_Y,META_X+META_Y,META_X-META_Y}, then the set precomputed for subsequent up levels may be M'=I*M,M"= ^I2 *M, etc.

Like the embodiment of FIG. 7, the embodiment of FIG. 14 may be implemented in hardware, software, or any combination thereof. Any number of stages can be used and any N-pixel by M-pixel interpolated output can be generated.

The embodiments of Figures 7 and 14, as well as other embodiments disclosed herein, may be configured for use with multi-sample anti-aliasing (MSAA), using multiple samples per pixel to improve image quality. The common arrangement of MSAA is to use four samples per pixel, which are arranged in a rotated 2×2 grid within the pixel. This can be referred to as 4x or 4 to 1 MSAA, but 2x, 8x and other variants of MSAA can be used.

For example, to operate with MSAA, the embodiment of FIG. 7 may be modified by duplicating or forking the tree structure to enable it to handle additional samples per pixel, as shown in FIG. 8 . The system 170 of FIG. 8 may be substantially similar to the system 150 of FIG. 7 , but with the addition of a redirection unit 162 that may operate in response to the mode selection input 164 to rearrange the directing samples from the root unit 155 to the tree 166 way. Mode selection input 164 may enable the system to switch between MSAA mode and non-MSAA mode. Root cell 155 may also be modified to rearrange the manner in which samples are directed to tree 166 in response to mode selection input 164 . Tree 166, including stages 166A, 166B, and 166C, may also be modified to handle additional nodes at each stage of the hierarchy. The number of nodes per stage can be multiplied by, for example, the number of samples per pixel in MSAA mode. For example, stage 166A may handle (9 x NUM_SAMPLES) nodes, which may be 36 nodes in the case of NUM_SAMPLES=4. Increasing the size of the stage by the same multiple as the number of samples per pixel in MSAA mode may help to switch the tree between MSAA mode and non-MSAA mode. Depending on implementation details, this may provide substantial improvements in simplicity and performance, which may outweigh any potential hardware cost increase.

In some implementations, in MSAA mode (ie, when the mode selection input 164 is active), the modified root cell 155 can be used as the root by finding/selecting one of the plurality of pixels in the center pixel of the grid start with the sample. (For example, the sample in the left corner of the center pixel may be selected as the root sample.) The root unit 155 may then extend and interpolate from the root sample to the number of samples in the center pixel, which in this example is assumed to be four (NUM_SAMPLES = 4). The root unit 155 and redirection unit 162 may then direct the four samples from the center pixel to the tree 166, which may then apply a diagonal hierarchical 3x3 topology to compute the values of other samples of other pixels adjacent to the center pixel, So on and so forth. Therefore, a hierarchical tree structure can be implemented independently for each of the plurality of samples.

In MSAA mode, the layout of sample outputs 160 may need to be rotated to accommodate the expectations of downstream processing units, eg, to compensate for the placement of samples in each pixel. The redirection unit 162 may add one level of logic to the architecture of Figure 8, but it may be relatively cost effective.

In non-MSAA mode (ie, when the mode select input 164 is active), the root cell 155 and redirection cell 162 may be on the root and its connected nodes by adding the value corresponding to the original pixel grid divided by NUM_SAMPLES Some modifications are made to reconfigure the inputs of tree 166 for reuse.

In some alternative embodiments, tree 166 may be configured to fork the center samples from the 3x3 grid of previous stages to span samples within a pixel. In this embodiment, a hybrid tree can be used, where one or more stages can be implemented in a conventional configuration to simplify the design.

Although the embodiment of FIG. 8 is shown as having a 3x3 topology, any topology may be used, including generalized forms of the embodiment of FIG. 14 . Each node can branch to "I" nodes on the next level, where I=W*Z, where W and Z can represent the number of nodes in the x and y directions.

In some embodiments, the N by M grid can be subdivided into smaller sub-grids so that different attributes can be interpolated for each sub-grid. This can be accomplished, for example, by starting at the center of each subgrid and determining the root value of the attribute to interpolate for that subgrid at the center of that subgrid. After finding the root value of each subgrid, the attribute values of each entire subgrid can be interpolated using a hierarchical tree topology on each subgrid.

In some embodiments, the system may be configured with multiple tree and/or root cells, where each tree and/or root cell may be used to interpolate the value of one of the sub-grids. For example, if the grid is subdivided into k subgrids, the system may include k hierarchical trees to interpolate the children of each root node, and k root cells to determine the origin of each subgrid center Root value.

9-11 illustrate embodiments of grids that may be subdivided in accordance with the principles of the present disclosure. In FIG. 9, the grid 180 is not subdivided (k=1), and the entire grid can be interpolated by a single hierarchical tree from the center of the entire grid identified as ROOT The root node starts and expands outward as indicated by the arrows. In Figure 10, the grid is subdivided into two sub-grids 182 and 184 (k=2). Each subgrid can be interpolated by a different hierarchical tree using different attributes, starting from one of the root nodes ROOT1 and ROOT2 in the center of the two subgrids. In Figure 11, grid 180 is subdivided into four sub-grids 186, 188, 190 and 192 (k=4). Each subgrid can be interpolated by a different hierarchical tree using different attributes, starting from one of the root nodes ROOT1, ROOT2, ROOT3, and ROOT4 in the center of the four subgrids. Properties of the same or different primitives can be interpolated using different subgrids, regardless of the level of subdivision.

12 is a block diagram illustrating a microarchitecture of the structure and data flow of an embodiment of a multi-attribute hierarchical interpolation system in accordance with the principles of the present disclosure. The example system 194 of FIG. 12 shows an embodiment with two trees (k=2), but the principles can be extended to embodiments with any number of trees for any number of sub-grids. System 194 is shown with functionality for supporting MSAA, but the functionality related to multiple attribute interpolation is independent of MSAA functionality, and MSAA functionality may be omitted.

The system 194 of FIG. 12 includes a first hierarchical tree 166A, a root unit 155A, and a metadata unit 156A that are capable of operating substantially independently of the parallel second hierarchical tree 166B, root unit 155B, and metadata unit 156B. However, it may be beneficial to operate both halves from the same clock and/or have them work together in certain modes. Each half of the system may receive separate root position and plane equation inputs 152A and 152B. The scheduler 196 may be configured to provide different inputs 152A and 152B to the two halves of the system 194 . For example, scheduler 196 may provide different root positions and plane equations to enable the system to perform the parallel interpolation shown in FIG. 10 .

The system of Figure 12 can be used to independently interpolate two different properties of two different sub-grids per clock cycle based on two different plane equations and two different root positions. Each half of the system can then implement a hierarchical tree (such as tree 166A or 166B) using its corresponding root position and the attribute value found at the center of its corresponding grid by the plane equation The rest estimates attribute values. For example, the first root cell 155A may determine the value of ROOT1 in FIG. 10 , while the root cell 155B may determine the value of ROOT2 in FIG. 10 . In this example, the tree implements a diagonal 3x3 topology, but other topologies can be used. For example, any general topology can be used, as shown in the embodiment of FIG. 14 . Each node can branch to "I" nodes at the next level, where I=W*Z, and where W and Z can represent the number of nodes in the x-direction and the y-direction.

Like the other embodiments described above, the embodiment of FIG. 12 may be implemented in hardware, software, or any suitable combination thereof. If implemented in hardware using the combinatorial logic of trees 166A and 166B, the system may be able to interpolate two sub-grids, such as those shown in FIG. 10, in a single clock cycle. The system can also be scaled to include any number of trees for interpolating any number of subgrids simultaneously. As shown in Figures 9-11, it may be beneficial to subdivide the entire grid into equally sized sub-grids because this balances the tree and reduces the logical level of the tree. The hardware configuration of the system may also be adapted to balance various factors, such as cost, power and energy consumption, performance, and the like. For example, each tree in the multi-attribute embodiment of Figure 12 can be implemented with half the amount of hardware, which, as a single-attribute embodiment, may result in each half running at about half the speed as a single-attribute version, but in The combined output still maintains the same N×M sample throughput per clock cycle. Alternatively, each half could be implemented with the same amount of hardware as the single attribute embodiment. This effectively doubles the amount of hardware and doubles the sample throughput for the combined N×M sample output.

In some embodiments, for example, where less than k attributes per clock need to be interpolated, a multi-attribute hierarchical tree may be configured to share resources. This can be accomplished, for example, by including multiplexers and/or adders near the head of the tree. In some embodiments, this may enable the system to maintain the same throughput of NxM samples per clock even while sharing resources.

The embodiment of Figure 12 includes functionality that may enable it to be reconfigured to share resources. For example, if only one property needs to be interpolated for the entire grid, the system can be reconfigured so that both trees can be configured to interpolate half of the grid using the same root position and plane equation input. In this mode of operation, the first tree 166A may operate in the normal manner using the first root cell 155A to determine the center sample at ROOT1 using the first root position and the plane equation from the input 152A. However, in this resource sharing mode of operation, the multiplexer 202 may select the first root position and plane equation from the input 152A as input to the second metadata unit 156B of the second tree. Additionally, in this resource sharing mode of operation, another multiplexer 200 may select the output of the first root cell 155A, but with an offset added by the adder 198 to place the root position of the second tree at a distance from Offset of ROOT1. That is, adder 198 and multiplexer 200 may substantially replace ROOT2 with an appropriate value to enable the second tree to interpolate its sub-grids using the first attribute. Thus, the two halves of the system can operate in parallel to interpolate an attribute over the entire grid 180 .

The principles illustrated with respect to FIG. 12 may be helpful in configuring an interpolation system to suit various system requirements. For example, as demands on the system sample throughput increase, e.g. due to an increase in the number of samples per grid, there may be an increasing need to interpolate multiple attributes simultaneously (from the same or different primitives) to ensure sufficient samples is interpolated. In cases where the size of the primitives is small and/or when interpolating at the corners of primitives with only partial sample coverage, it may be useful to be able to interpolate multiple attributes simultaneously, and thus may help improve utilization. The principles shown with respect to FIG. 12 can be adapted to help improve system performance, efficiency, etc. in any of these situations.

FIG. 13 illustrates an embodiment of an imaging device 204 into which any of the methods or apparatus described in this disclosure may be integrated. Imaging device 204 may be of any form, such as panel displays for PCs, laptops, mobile devices, etc., projectors, VR goggles, etc., and may be based on any imaging technology, such as cathode ray tubes (CRT), digital light Projectors (DLPs), Light Emitting Diodes (LEDs), Liquid Crystal Displays (LCDs), Organic LEDs (OLEDs), Quantum Dots, etc., are used to display the rasterized image 206 with pixels. An image processor 210 , such as a graphics processing unit (GPU) and/or driver circuitry 212 , can process and/or convert the image into a form that can be displayed on or by the imaging device 204 . A portion of image 206 is shown enlarged so that pixels 208 are visible. Any of the methods or apparatus described in this disclosure may be integrated into the imaging device 204 , the processor 210 and/or the driver circuit 212 to interpolate any of the pixels 208 shown in FIG. 13 . In some embodiments, image processor 210 may include any of a hierarchical tree topology such as those described above implemented on integrated circuit 211, for example. In some embodiments, integrated circuit 211 may also include driver circuitry 212 and/or any other components that may implement any other functionality of imaging device 204 .

In addition to those mentioned above, and depending on implementation details and circumstances, the principles of the present disclosure may provide any or all of the following advantages and/or features: methods scalable to various pixel grid dimensions and/or Device; Hierarchical topologies, including diagonal 3×3 topologies. Area, energy and/or power consumption can be reduced and can be applied to any sample/pixel interpolation unit/module; hierarchical topologies, including diagonal 3×3 topologies, can be applied on boundary equation based interpolation, which May be useful for efficient rasterization; hybrid tree topologies, including diagonal 3×3 topologies, combined with traditional designs can save cost and reduce complexity; sample interpolation with hierarchical topologies, including diagonal 3×3 topologies Can be implemented in conjunction with MSAA mode operation; hierarchical topologies, including diagonal 3×3 topologies, can be applied to any interpolation throughput of integer arrays of adjacent samples in the x and y directions; hierarchical topologies, including diagonal 3×3 topology, can be scaled to any other set of samples/pixels for use with tree interpolation; the methods and apparatus disclosed herein can be used with any attribute data format; in order to support multiple blocks (eg, k blocks) Multiple attributes are interpolated, and an interpolated tree can be constructed using bifurcation points with k leaf nodes near the head of the tree.

In some embodiments, at each stage, ie, at each level, the number of nodes may follow a geometric progression. Additionally, in the case of a 3×3 topology, the cost of each stage may be approximately equal to nine times the cost of the previous stage. Therefore, if the final stage area is A, the total area TA can be given by: TA=A+A/9+A/81+A/729...=A×(9/8). Using this approximation, an example area-based cost summary is provided in Table 1 for a rasterization implementation based on the following assumptions: (1) the approximation is based on aliasing mode (i.e., not multi-sample antialiasing); (2) fixed-point is used The algorithm performs area estimation based on rasterizers dx, dy, and starting points; (3) uses a symmetric grid with the same number of samples in the x and y directions. The values shown in Table 1 are for illustration purposes only and may not represent actual values in physical or simulated implementations.

Table 1

pixel traditional technology Diagonal layered 3×3 topology % improvement rate 4×4 9 6 33 8×8 44 19 57 12×12 100 41 59 16×16 200 74 63 24×24 500 160 68 32×32 1000 260 74

15 illustrates an embodiment of a computing system in accordance with the present disclosure. The system 300 of FIG. 15 may be used to implement any or all of the methods and/or apparatuses described in this disclosure. System 300 may include central processing unit (CPU) 302 , memory 304 , storage device 306 , graphics processing unit (GPU) 307 , user interface 308 , network interface 310 , and power supply 312 . A complete hardware implementation of the hierarchical tree structure according to the present disclosure may be implemented in GPU 307 , while a complete software implementation may be implemented fully within CPU 302 . In other embodiments, a complete hardware implementation of the hierarchical tree structure may be implemented in CPU 302 as an integrated graphics processing unit (IGPU). In other embodiments, GPU 307 may be used to implement a serial hybrid configuration, wherein higher levels of hierarchical tree structure 307 may be implemented in the GPU using conventional hardware, while lower levels may be implemented in GPU 307 and/or CPU 302 Implemented in hardware and/or software using a hierarchical tree topology. In other embodiments, hierarchical tree structures in accordance with the present disclosure may be distributed among any suitable combination of hardware and/or software using any component of system 300 . Furthermore, the principles of the present disclosure are not limited to being implemented with any of the components shown in FIG. 15, but may be implemented in any suitable hardware, software, or combination thereof.

In various embodiments, the system may omit any of these components, or may include repetition or any additional number of any of these components, as well as any other type of implementation of any of the methods and/or apparatus described in this disclosure s component.

CPU 302 may include any number of cores, caches, buses and/or interconnects and/or controllers. Memory 304 may include any arrangement of dynamic and/or static RAM, non-volatile memory (eg, flash memory), and the like. Storage device 306 may include a hard disk drive (HDD), solid state drive (SSD), and/or any other type of data storage device or any combination thereof. User interface 308 may include any type of human interface device, such as keyboards, mice, monitors, video capture or transmission devices, microphones, speakers, touch screens, etc., as well as any virtual or remote versions of these devices. Network interface 310 may include one or more adapters or other devices to communicate via Ethernet, Wi-Fi, Bluetooth, or any other computer network arrangement to enable components to communicate over physical and/or logical networks (such as intranets, the Internet , local area network, wide area network, etc.) to communicate. Power source 312 may include a battery and/or a power source capable of receiving power from an AC or DC power source and converting it into any form suitable for use with the components of system 300 .

Any or all components of system 300 may be interconnected by system bus 301, which may be collectively referred to as various interfaces, including power bus, address and data bus, high-speed interconnects such as Serial AT Attachment (SATA), peripheral components Interconnect (PCI), Peripheral Component Interconnect Express (PCI-e), System Management Bus (SMB) and any other type of interface that enables these components to work together locally at one location and/or between locations.

System 300 may also include various chipsets, interfaces, adapters, glue logic, embedded controllers such as programmable or non-programmable logic devices or arrays, application specific integrated circuits (ASICs), embedded computers, smart cards, etc., arranged Any one of all methods and/or apparatuses described in this disclosure is implemented to enable the various components of system 300 to work together. Any component of system 300 may be implemented in hardware, software, firmware, or any combination thereof. In some embodiments, any or all components may be implemented in a virtualized form and/or in a cloud-based implementation with flexible resource configuration, eg, within a data center or distributed across multiple data centers.

The blocks or steps of the methods or algorithms and functions described in connection with the embodiments disclosed herein may be embodied directly in hardware, in one or more software modules executed by a processor, or in a combination of both, including system 300 . If implemented in software, the functions may be stored on or transmitted over as one or more instructions or code on a tangible, non-transitory computer-readable medium. Software modules may reside in random access memory (RAM), flash memory, read only memory (ROM), electrically programmable ROM (EPROM), electrically erasable programmable ROM (EEPROM), registers, hard disk, removable disk, CD ROM or any other form of storage medium. Any of the systems disclosed herein, or components or portions thereof, may be implemented as part of a software stack of a larger system (eg, a graphics processing unit (GPU) or other larger system). Any system disclosed herein, or a component or portion thereof, may be implemented as its own software stack.

The above disclosed embodiments have been described in the context of various implementation details, but the principles of the present disclosure are not limited to these or any other specific details. For example, some functionality has been described as being implemented by certain components, but in other embodiments the functionality may be distributed among different systems and components with various user interfaces in different locations. Certain embodiments have been described as having particular processes, steps, etc., but these terms also encompass embodiments in which multiple processes, steps, etc. may be used to implement particular processes, steps, etc. or multiple processes, steps, etc. may be integrated into a single process , steps, etc. References to a component or element may refer to only a portion of that component or element. For example, a reference to an integrated circuit may refer to all or only a portion of the integrated circuit, and a reference to a block may refer to the entire block or one or more sub-blocks. Although the principles of the present disclosure have been described in the context of certain applications, the principles may be applied to any attribute interpolation and/or rasterizer processing, and they may be within the use of boundary equations, plane equations, or any other equations Useful in any mathematical calculation that interpolates or extrapolates one or more values. In some embodiments, computations may be performed for positions in the lowest level of the hierarchy, and depending on the resolution of the grid or other array, the positions may correspond to various things, such as pixels, samples, centroids, and the like. In some embodiments, the interpolation can work at any spatial sampling frequency of the planar primitives. In some embodiments, a zero offset may refer to a substantially zero offset that enables the value to be ignored for computational purposes without significantly degrading the result.

Terms such as "first" and "second" are used in this disclosure and in the claims only to distinguish what they modify, and may not indicate any spatial or temporal order unless apparent from the context. The mention of the first thing may not imply the existence of the second thing.

The various details and embodiments described above may be combined to yield further embodiments in accordance with the inventive principles of this patent disclosure. Since the inventive principles of the present patent disclosure may be modified in arrangement and detail without departing from the inventive concept, such changes and modifications are considered to be within the scope of the appended claims.

Claims (20)

1. A method for interpolating an attribute value of an image grid, the method comprising: Determine the first-level root value of the attribute at the first-level root node located at the center of the image grid; computing the first level metadata based on the first gradient of the attribute in the first direction and the second gradient of the attribute in the second direction; and Based on the primary root value and primary metadata, primary child values for attributes of two or more primary child nodes radially arranged around the primary root node in the image grid are derived. 2. The method of claim 1, further comprising: Using one of the first-level child nodes and its corresponding first-level child value as the second-level root node and second-level root value of the cell of the image grid, wherein the root node of the cell is located in the center of the cell; computing secondary metadata based on the first gradient and the second gradient; and Based on the secondary root value and the secondary metadata, secondary child values are derived for attributes of two or more secondary child nodes radially arranged around the secondary root node in the cell. 3. The method of claim 1, wherein each first-level child node is symmetrically offset from the first-level root node in the first direction and the second direction. 4. The method of claim 3, wherein each first-level child node is offset from the first-level root node by substantially zero or substantially the same distance in the first direction and the second direction. 5. The method of claim 1, wherein: The image grid includes a 3x3 cell array with a center cell and eight outer cells; Two or more first-level child nodes include eight first-level child nodes; the first-level root node is at the center of the center cell; and Each first-level child node is centered on one of the outer cells. 6. The method of claim 1, wherein the primary metadata includes attribute delta values offset in the first direction and the second direction. 7. The method of claim 1, wherein: the value of the first parameter A is based on the first gradient; and The value of the second parameter B is based on the second gradient. 8. The method of claim 7, wherein the primary metadata includes values A, B, A+B, and A-B. 9. The method of claim 2, wherein: the value of the first parameter A is based on the first gradient; The value of the second parameter B is based on the second gradient; The image grid includes a 3×3 cell array; Primary metadata includes the values 3A, 3B, 3(A+B), and 3(A-B); and Secondary metadata includes the values A, B, A+B, and A-B. 10. The method of claim 1, wherein the first-level metadata is calculated based on a planar equation. 11. The method of claim 10, wherein: The form of the plane equation is P(x,y)=A*(x-Seed_X)+B*(y-Seed_Y)+C; P is the parameter of the two-dimensional surface interpolated at each position (x,y), where x is the distance in the x direction and y is the distance in the y direction; A is the gradient per pixel or other cell in the x direction; B is the gradient per pixel or other cell in the y direction; and C is the value of P at position (Seed_X, Seed_Y). 12. The method of claim 1, wherein deriving a first-level sub-value comprises adding one or more first-level metadata to a first-level root value. 13. The method of claim 1, wherein a first-level root node and each first-level child node corresponds to a pixel. 14. The method of claim 1, wherein the first-level root node and each first-level child node corresponds to a sample. 15. The method of claim 1, further comprising rasterizing the image in response to the attribute value. 16. The method of claim 15, wherein the attribute includes a first value indicating that the node is inside the primitive and a second value indicating that the node is outside the primitive. 17. A method for interpolating attribute values of an image grid, the method comprising: Determine the root value of the attribute of the root node at the center of the image grid; precomputing metadata for a plurality of child nodes in one or more hierarchies based on one or more gradients of attributes; and Based on the corresponding root value and metadata of the hierarchy of each sub-node, the attribute value of each sub-node of each hierarchy is derived; where each child node serves as the root node in the next hierarchy. 18. The method of claim 17, wherein: The image grid has a plurality of outer cells arranged radially around the central cell; and The root node is in the center cell. 19. The method of claim 17, wherein the root node is located in the first cell having one or more additional nodes, the method further comprising: determining attribute values for one or more additional nodes in the first cell; and Deriving the attribute value of the additional child node corresponding to each additional node in the first cell of each level, wherein each additional node is derived based on the attribute value of the corresponding additional node in the first cell and the metadata of the corresponding level The attribute value of the child node. 20. An apparatus for interpolating attribute values of an image grid, the apparatus comprising: A tree of one or more logical stages configured to derive, based on corresponding attribute values at the root node and metadata for each of the one or more levels, a plurality of child nodes around the centrally located root node in the level property value.

Images