Method and apparatus for tiling an image

Claim 2

A computer graphics system comprising: (a) a display device having a display surface, (b) display address means for generating a display address signal having an X component and a Y component such as to define a set of grid points on the display surface in a rectangular array at a pitch dX in the X direction and a pitch dY in the Y direction, (c) an electronic memory device having an equivalent set of addressable memory locations corresponding respectively to the grid points, (d) an XY address generator for automatically generating addresses of memory locations corresponding to grid points within a first selected area of the display surface and subsequently generating addresses of memory locations corresponding to grid points within a second selected area of the display surface, the second selected area and the first selected area being contiguous, and the XY address generator being such that it generates the address of each memory location in the first and second selected areas only once, and (e) loading means for calculating a value for a parameter Q for each of the memory locations whose addresses were generated in step (d) and loading the calculated values into the respective memory locations.

Claim 5

A method according to claim 2, further comprising: (e) calculating a value for the parameter Q for each memory location having an address generated in step (d), and (f) loading the values calculated in step (e) into the respective memory locations.

Claim 6

A method according to claim 2, wherein the first and second selected areas are each substantially triangular and meet at a side that extends transverse to the X direction substantially along a line from a location (P*dX, Q*dY) to a location ((P+p)*dX, (Q+q*dY)), where P, Q, p and q are integers, the addresses generated in step (a) include the addresses of memory locations corresponding to at least one grid point of which the Y coordinate is given by (Q+i)*dY, where i is an integer in the range from 1 to q, and the X coordinate is given by floor of the X coordinate of the exact intersection of a line Y=(q/p)*X+(Q*p-q*P)*dY/p with the line Y=(Q+i)*dY, and the addresses generated in step (d) include the addresses of memory locations corresponding to at least one grid point of which the Y coordinate is given by (Q+i)*dY and the X coordinate is dX plus the floor of the X coordinate of the exact intersection of the line Y=(q/p)*X+(Q*p-q*P)*dY/p with the line Y=(Q+i)*dY.

Claim 7

A computer graphics system comprising: (a) a display device having a display surface, (b) display address means for generating a display address signal having an X component and a Y component such as to define a set of grid points on the display surface in a rectangular array at a pitch dX in the X direction and a pitch dY in the Y direction, (c) an electronic memory device having an equivalent set of addressable memory locations corresponding respectively to the grid points, (d) an XY address generator for automatically generating addresses of memory locations corresponding to grid points lying substantially on a line from a location (X 0 +e*dX, Y 0 +f*dY) to a location (X 0 +p*dX, Y 0 +q*dY), where (X 0 , Y 0 ) is a grid point and e, f, p, and q are rational numbers, by performing the following operations: ______________________________________ (i) set s = floor ((p - e)/(q - f)) PInc = (p - e) - s(q - f) - (q - f) NInc = (p - e) - s(q - f) AErr.sub.0 = PInc ______________________________________ and (ii) for each value of i in the range from 0 to q-1, execute ______________________________________ If AErr.sub.i >= 0 then X.sub.i+1 : = X.sub.i + (s + 1)dX AErr.sub.i+1 : = AErr.sub.i + PInc else X.sub.i+1 : = X.sub.i + sdX AErr.sub.i+1 : = AErr.sub.i + NInc end If Y.sub.i+1 : = Y.sub.i + dY ______________________________________ and (e) loading means for calculating a value for a parameter Q at the memory location (X i+1 +u*dX, Y i+1 ), where u is an integer, for each value of i in the range from 0 to q-1, and loading the calculated value of the parameter Q into the memory location.

Claim 8

A computer graphics system comprising: (a) a display device having a display surface, (b) display address means for generating a display address signal having an X component and a Y component such as to define a set of grid points on the display surface in a rectangular array at a pitch dX in the X direction and a pitch dY in the Y direction, (c) an electronic memory device having an equivalent set of addressable memory locations corresponding respectively to the grid points, (d) an XY address generator for automatically generating addresses of memory locations corresponding to grid points lying substantially on a line from a location (X 0 +e*dX, Y 0 +f*dY) to a location (X 0 +p*dX, Y 0 +q*dY), where (X 0 , Y 0 ) is a grid point and e, f, p, and q are rational numbers, by performing the following operations: ______________________________________ (i) set s = floor ((p - e)/(q - f)) PInc = (p - e) - s(q - f) - (q - f) NInc = (p - e) - s(q - f) AErr.sub.0 = PInc ______________________________________ and (ii) for each value of i in the range from 0 to q-1, execute ______________________________________ If AErr.sub.i >= 0 then X.sub.i+1 : = X.sub.i + (s + 1)dX AErr.sub.i+1 : = AErr.sub.i + PInc else X.sub.i+1 : = X.sub.i + sdX AErr.sub.i+1 : = AErr.sub.i + NInc end If Y.sub.i+1 : = Y.sub.i + dY ______________________________________ and (e) loading means for calculating a value for a parameter Q at the memory location (X i+1 +u*dX, Y i+1 ), where u is an integer, for each value of i in the range from 0 to q-1, and loading the calculated value of the parameter Q into the memory location.

Claim 9

A computer graphics system according to claim 5, wherein e and f are each zero, p and q are integers, and u is an integer selected from one and zero, and the loading means calculate values of Q for the memory location (X i+1 +u*dX, Y i+1 ) and an adjacent memory location (x i+1 +u*dX+v*dX, Y i+1 ), where v is an integer selected from one and minus one, for at least one value of i in the range from 0 to q-1, and successively load the respective memory locations.

Claim 10

A computer graphics system comprising: (a) a display device having a display surface, (b) display address means for generating a display address signal having an X component and a Y component such as to define a set of grid points on the display surface in a rectangular array at a pitch dX in the X direction and a pitch dY in the Y direction, (c) an electronic memory device having an equivalent set of addressable memory locations corresponding respectively to the grid points, (d) an XY address generator for automatically generating addresses of memory locations corresponding to grid points between a straight line from a location (XM 0 +eM*dX, Y 0 +f*dY) to a location (XM 0 +pM*dX, Y 0 +q*dY) and a straight line from a location (Xm 0 +em*dX, Y 0 +f*dY) to a location (Xm 0 +pm*dx, Y 0 +q*dY) where (XM 0 , Y 0 ) and (Xm 0 , Y 0 ) are grid points and eM, em, f, pM, pm, and q are rational numbers, by performing the following operations: ______________________________________ (i) set sM = floor((pM - eM)/(q - f)) PIncM = (pM - eM) - sM(q - f) - (q - f) NIncM = (pM - eM) - sM(q - f) AEerrM.sub.0 = PIncM sm = floor ((pM - em)/(q - f)) PIncm = (pm - em) - sm(q - f) - (q - f) NIncm = (pm - em) - sm(q - f) AEerrm.sub.0 = PIncm ______________________________________ and (ii) for each line value of i in the range from 0 to q-1, execute ______________________________________ If AErrM.sub.i >= 0 then XM.sub.i+1 : = XM.sub.i + sM + 1 AErrM.sub.i+1 : = AErrM.sub.i + PIncM else XM.sub.i+1 : = XM.sub.i + sM AErrM.sub.i+1 : = AErrM.sub.i + NIncM end If If AErrm.sub.i >= 0 then Xm.sub.i+1 : = Xm.sub.i + sm + 1 AErrm.sub.i+1 : = AErrm.sub.i + PIncm else Xm.sub.i+1 : = Xm.sub.i + sm AErrm.sub.i+1 : = AErrm.sub.i + NIncm end If Y.sub.i+1 : = Y.sub.i + dy Hrz.sub.i+1 = Xm.sub.i+1 - XM.sub.i+1' ______________________________________ and (e) loading means for calculating a value for a parameter Q at the memory location (XM i+1 +u*dX, Y i+1 ), where u is an integer, and at Hrz i+1 adjacent memory locations that are on the (i+1)th row and are successively closer to the location (Xm i+1 , Y i+1 ) and for successively loading the calculated values of Q into those memory locations.

Claim 11

A computer graphics system comprising: (a) a display device having a display surface, (b) display address means for generating a display address signal having an X component and a Y component such as to define a set of grid points on the display surface in a rectangular array at a pitch dX in the X direction and a pitch dY in the Y direction, (c) an electronic memory device having an equivalent set of addressable memory locations corresponding respectively to the grid points, (d) an XY address generator for automatically generating addresses of memory locations corresponding to grid points between a straight line from a location (XM 0 +eM*dX, Y 0 +f*dY) to a location (XM 0 +pM*dX, Y 0 +q*dY) and a straight line from a location (Xm 0 +em*dX, Y 0 +f*dY) to a location (Xm 0 +pm*dx, Y 0 +q*dY) where (XM 0 , Y 0 ) and (Xm 0 , Y 0 ) are grid points and eM, em, f, pM, pm, and q are rational numbers, by performing the following operations: ______________________________________ (i) set sM = floor((pM - eM)/(q - f)) PIncM = (pM - eM) - sM(q - f) - (q - f) NIncM = (pM - eM) - sM(q - f) AEerrM.sub.0 = PIncM sm = floor ((pM - em)/(q - f)) PIncm = (pm - em) - sm(q - f) - (q - f) NIncm = (pm - em) - sm(q - f) AEerrm.sub.0 = PIncm ______________________________________ and (ii) for each line value of i in the range from 0 to q-1, execute ______________________________________ If AErrM.sub.i >= 0 then XM.sub.i+1 : = XM.sub.i + sM + 1 AErrM.sub.i+1 : = AErrM.sub.i + PIncM else XM.sub.i+1 : = XM.sub.i + sM AErrM.sub.i+1 : = AErrM.sub.i + NIncM end If If AErrm.sub.i >= 0 then Xm.sub.i+1 : = Xm.sub.i + sm + 1 AErrm.sub.i+1 : = AErrm.sub.i + PIncm else Xm.sub.i+1 : = Xm.sub.i + sm AErrm.sub.i+1 : = AErrm.sub.i + NIncm end If Y.sub.i+1 : = Y.sub.i + dy Hrz.sub.i+1 = Xm.sub.i+1 - XM.sub.i+1' ______________________________________ and (e) loading means for calculating a value for a parameter Q at the memory location (XM i+1 +u*dX, Y i+1 ), where u is an integer, and at Hrz i+1 adjacent memory locations that are on the (i+1)th row and are successively closer to the location (Xm i+1 , Y i+1 ) and for successively loading the calculated values of Q into those memory locations.

Claim 12

A computer graphics system according to claim 7, wherein eM, em and f are each zero, pM, pm and q are integers, and u is an integer selected from one and zero, and the XY address generator performs the following additional operations: (iii) for each value of i, execute ______________________________________ If Xm.sub.i+1 > XM.sub.i+1 then HES = 0 else HES = 1 end If ______________________________________ (iv) store XM i+1 , Y i+1 , Hrz i+1 and HES, and (v) if HES=1, set u=1 and otherwise set u=0, and the loading means successively load the memory locations from (XM i+1 +dX, Y i+1 ) to (Xm i+1 , Y i+1 ) if u=1, and otherwise successively load the memory locations from (XM i+1 , Y i+1 ) to (Xm i+1 +dX, Y i+1 ).

Claim 13

A computer graphics system comprising: (a) a display device having a display surface, (b) display address means for generating a display address signal having an X component and a Y component such as to define a set of grid points on the display surface in a rectangular array at a pitch dX in the X direction and a pitch dY in the Y direction, (c) an electronic memory device having an equivalent set of addressable memory locations corresponding respectively to the grid points, and (d) an XY address generator for automatically generating addresses of memory locations corresponding to grid points lying substantially on a line from a location (X 0 +e*dX, Y 0 +f*dY) to a location (X 0 +p*dX, Y 0 +dY), where (X 0 , Y 0 ) is a grid point and e, f, p, and q are rational numbers, by performing the following operations: ______________________________________ (i) set s = floor ((p - e)/(q - f)) PInc = (p - e) - s(q - f) - (q - f) Ninc = (p - e) - s(q - f) AErr.sub.0 = PInc ______________________________________ and (ii) for each value of i in the range from 0 to q-1, execute ______________________________________ If AErr.sub.i >= 0 then X.sub.i+1 : = X.sub.i + (s + 1)dX AErr.sub.i+1 : = AErr.sub.i + PInc else X.sub.i+1 : = X.sub.i + sdx AErr.sub.i+1 : = AErr.sub.i + NInc end If Y.sub.i+1 : = Y.sub.i + dY, ______________________________________ and (e) loading means for calculating a value of a parameter Q for the memory location (X i+1 +u*dX, Y i+1 ), where u is an integer, for each value of i in the range from 0 to q-1, and loading the memory locations (X i+1 +u*dX, Y i+1 ) with the respective calculated values of Q.

Claim 14

A computer graphics system comprising: (a) a display device having a display surface, (b) display address means for generating a display address signal having an X component and a Y component such as to define a set of grid points on the display surface in a rectangular array at a pitch dX in the X direction and a pitch dY in the Y direction, (c) an electronic memory device having an equivalent set of addressable memory locations corresponding respectively to the grid points, and (d) an XY address generator for automatically generating addresses of memory locations corresponding to grid points lying substantially on a line from a location (X 0 +e*dX, Y 0 +f*dY) to a location (X 0 +p*dX, Y 0 +dY), where (X 0 , Y 0 ) is a grid point and e, f, p, and q are rational numbers, by performing the following operations: ______________________________________ (i) set s = floor ((p - e)/(q - f)) PInc = (p - e) - s(q - f) - (q - f) Ninc = (p - e) - s(q - f) AErr.sub.0 = PInc ______________________________________ and (ii) for each value of i in the range from 0 to q-1, execute ______________________________________ If AErr.sub.i >= 0 then X.sub.i+1 : = X.sub.i + (s + 1)dX AErr.sub.i+1 : = AErr.sub.i + PInc else X.sub.i+1 : = X.sub.i + sdx AErr.sub.i+1 : = AErr.sub.i + NInc end If Y.sub.i+1 : = Y.sub.i + dY, ______________________________________ and (e) loading means for calculating a value of a parameter Q for the memory location (X i+1 +u*dX, Y i+1 ), where u is an integer, for each value of i in the range from 0 to q-1, and loading the memory locations (X i+1 +u*dX, Y i+1 ) with the respective calculated values of Q.

Claim 15

A computer graphics system according to claim 9, wherein e and f are each zero, p and q are integers, and u is an integer selected from one and zero, and the loading means calculate the value of Q for the memory location (X i+1 +u*dX, Y i+1 ) and an adjacent memory location (X i+1 +u*dX+v*dX, Y i+1 ), where v is an integer selected from one and minus one, and successively load the calculated values of Q into the respective memory locations.

Claim 16

A computer graphics system comprising: (a) a display device having a display surface, (b) display address means for generating a display address signal having an X component and a Y component such as to define a set of grid points on the display surface in a rectangular array at a pitch dX in the X direction and a pitch dY in the Y direction, (c) an electronic memory device having an equivalent set of addressable memory locations corresponding respectively to the grid points, (d) an XY address generator for automatically generating addresses of memory locations corresponding to substantially all grid points between a straight line from a location (XM 0 +eM*dX, Y 0 +f*dY) to a location (XM 0 +pM*dX, Y 0 +q*dY) and a straight line from a location (Xm 0 +em*dX, Y 0 +f*dY) to a location (XM 0 +pm*dx, Y 0 +q*dY) where (XM 0 , Y 0 ) and (XM 0 , Y 0 ) are grid points and eM, em, f, pM, pm, and q are rational numbers, by performing the following operation: ______________________________________ (i) set sm = floor((pM - eM)/(q - f)) PIncM = (pM - eM) - sM(q - f) - (q - f) NIncM = (pM -eM) - sM(q -f) AEerrM.sub.0 = PIncM sm = floor ((pm - em)/q - f)) PIncm = (pm - em) - sm(q - f) - (q - f) NIncm = (pm - em) - sm(q - f) AEerrm.sub.0 = PIncm ______________________________________ and (ii) for each value of i in the range from 0 to q-1, execute ______________________________________ If AErrM.sub.i >= 0 then XM.sub.i+1 = XM.sub.i + sM + 1 AErrM.sub.i+1 : = AErrM.sub.i + PIncM else XM.sub.i+1 : = XM.sub.i + sM AErrM.sub.i+1 : = AErrM.sub.i + NIncM end If If AErrm.sub.i >= 0 then Xm.sub.i+1 : = Xm.sub.i + sm + 1 AErrm.sub.i+1 : = AErrm.sub.i + PIncm else Xm.sub.i+1 L = Xm.sub.i + sm AErrm.sub.i+1 = AErrm.sub.i + NIncm end If Y.sub.i+1 : = Y.sub.i + dy Hrz.sub.i+1 = Xm.sub.i+1 - XM.sub.i+1' ______________________________________ and (e) loading means for calculating values of a parameter Q for the memory location (XM i+1 +u*dX, Y i+1 ), where u is an integer, and Hrz i+1 adjacent memory locations on the (i+1)th row that are between the location (XM i+1 +u*dX, Y i+1 ) and the location (Xm i+1 +DIR*dX, Y i+1 ), where DIR is equal to Hrz i+1 /abs. Hrz i+1 , and loading the calculated values of Q into the respective memory locations, starting with the location (XM i+1 +u*dX, Y i+1 ) and successively loading locations closer to the location (Xm i+1 +DIR*dX, Y i+1 ).

Claim 17

A computer graphics system comprising: (a) a display device having a display surface, (b) display address means for generating a display address signal having an X component and a Y component such as to define a set of grid points on the display surface in a rectangular array at a pitch dX in the X direction and a pitch dY in the Y direction, (c) an electronic memory device having an equivalent set of addressable memory locations corresponding respectively to the grid points, (d) an XY address generator for automatically generating addresses of memory locations corresponding to substantially all grid points between a straight line from a location (XM 0 +eM*dX, Y 0 +f*dY) to a location (XM 0 +pM*dX, Y 0 +q*dY) and a straight line from a location (Xm 0 +em*dX, Y 0 +f*dY) to a location (XM 0 +pm*dx, Y 0 +q*dY) where (XM 0 , Y 0 ) and (XM 0 , Y 0 ) are grid points and eM, em, f, pM, pm, and q are rational numbers, by performing the following operation: ______________________________________ (i) set sm = floor((pM - eM)/(q - f)) PIncM = (pM - eM) - sM(q - f) - (q - f) NIncM = (pM -eM) - sM(q -f) AEerrM.sub.0 = PIncM sm = floor ((pm - em)/q - f)) PIncm = (pm - em) - sm(q - f) - (q - f) NIncm = (pm - em) - sm(q - f) AEerrm.sub.0 = PIncm ______________________________________ and (ii) for each value of i in the range from 0 to q-1, execute ______________________________________ If AErrM.sub.i >= 0 then XM.sub.i+1 = XM.sub.i + sM + 1 AErrM.sub.i+1 : = AErrM.sub.i + PIncM else XM.sub.i+1 : = XM.sub.i + sM AErrM.sub.i+1 : = AErrM.sub.i + NIncM end If If AErrm.sub.i >= 0 then Xm.sub.i+1 : = Xm.sub.i + sm + 1 AErrm.sub.i+1 : = AErrm.sub.i + PIncm else Xm.sub.i+1 L = Xm.sub.i + sm AErrm.sub.i+1 = AErrm.sub.i + NIncm end If Y.sub.i+1 : = Y.sub.i + dy Hrz.sub.i+1 = Xm.sub.i+1 - XM.sub.i+1' ______________________________________ and (e) loading means for calculating values of a parameter Q for the memory location (XM i+1 +u*dX, Y i+1 ), where u is an integer, and Hrz i+1 adjacent memory locations on the (i+1)th row that are between the location (XM i+1 +u*dX, Y i+1 ) and the location (Xm i+1 +DIR*dX, Y i+1 ), where DIR is equal to Hrz i+1 /abs. Hrz i+1 , and loading the calculated values of Q into the respective memory locations, starting with the location (XM i+1 +u*dX, Y i+1 ) and successively loading locations closer to the location (Xm i+1 +DIR*dX, Y i+1 ).

Claim 18

A computer graphics system according to claim 11 wherein eM, em, and f are each zero, pM, pm and q are integers, and u is an integer selected from one and zero, and the XY address generator performs the following additional operations: (iii) for each value of i, execute ______________________________________ If Xm.sub.i+1 > XM.sub.i+1 then HES = 0 else HES = 1 end If ______________________________________ (iv) store XM i+1 , Y i+1 , Hrz i+1 and HES, and (v) if HES=1, set u=1 and otherwise set u=0 and the loading means successively loads the memory locations from (XM i+1 +dX, Y i+1 ) to (Xm i+1 , Y i+1 ) if u=1, and otherwise successively loads the memory locations from (XM i+1 , Y i+1 ) to (Xm i+1 +dX, Y i+1 ).