Method and apparatus for hidden surface removal

Claim 3

A method according to claim 1, comprising, before step (c), storing the value of the parameter Qp for the first grid point in memory, and step (c) comprises reading the value of the parameter Qp for the first grid point from memory.

Claim 4

A method according to claim 2, wherein the step of storing the value of the parameter Qp for the first grid point comprises loading the value of the parameter Qp for the first grid point into the memory location corresponding to the first grid point, and step (e) comprises loading the value of the parameter Qc for the first grid point into the memory location corresponding to the first grid point in place of the value of the parameter Qp for the first grid point.

Claim 5

A method according to claim 1, comprising, before step (c), storing values of the parameter Qp for the first and second grid points in memory, step (c) comprises reading the value of the parameter Qp for the first grid point from memory, and the method further comprises: (f) reading the value of the parameter Qp for the second grid point from memory, (g) comparing the value of the parameter Qc for the second grid point with the value of the parameter Qp for the second grid point, and concurrently generating a fourth address word defining a memory location corresponding to a fourth grid point and computing a value of the parameter Qc for the third grid point, and if the value of the parameter Qc for the second grid point bears a predetermined relationship to the value of the parameter Qp for the second grid point, (h) loading the value of the value of the parameter Qc for the second grid point into the memory location corresponding to the second grid point.

Claim 8

A method according to claim 5, wherein step (c) comprises computing the value of R for the first grid point as a function of X and Y.

Claim 9

A method according to claim 6, wherein step (c) is performed concurrently with step (b).

Claim 10

A method according to claim 2, wherein step (f) further comprises loading the value of the parameter Qc for the first grid point into a second memory device.

Claim 11

A method according to claim 8, comprising, before step (d), storing a value of the parameter Qp for the first grid point in the second memory device, and step (d) comprises reading the value of the parameter Qp for the first grid point from the second memory device.

Claim 12

A method according to claim 8, wherein the second memory device has a plurality of memory locations that correspond respectively to the grid points in the rectangular array, and step (f) comprises loading the value of the parameter Qc for the first grid point into the second memory device at the location corresponding to the first grid point.

Claim 13

A method according to claim 10, wherein the step of storing the value of the parameter Qp for the first grid point comprises loading the value of the parameter Qp for the first grid point into the memory location of the second memory device corresponding to the first grid point, and step (f) comprises loading the value of the parameter Qc for the first grid point into the memory location of the second memory device corresponding to the first grid point in place of the value of the parameter Qp for the first grid point.

Claim 14

A method according to claim 5, comprising, before step (d), storing values of the parameter Qp for the first and second grid points in memory, step (d) comprises reading the value of the parameter Qp for the first grid point from memory, and the method further comprises: (g) providing the value of the parameter R for the second grid point, (h) reading the value of the parameter Qp for the second grid point from memory, (i) comparing the value of the parameter Qc for the second grid point with the value of the parameter Qp for the second grid point, and concurrently generating a fourth address word defining a memory location corresponding to a fourth grid point and computing a value of the parameter Qc for the third grid point, and if the value of the parameter Qc for the second grid point bears a predetermined relationship to the value of the parameter Qp for the second grid point, (j) loading the value of the parameter R for the second grid point into the memory location corresponding to the second grid point.

Claim 15

Apparatus for generating values of a planar function Z for designated grid points in a rectangular array at a pitch dX in an X direction and a pitch dY in a Y direction, which is perpendicular to the X direction, the designated grid points lying substantially on a line from a point (X 0 , Y 0 ) to a point (X 0 +p*dX, Y 0 +q*dY), where p and q are rational numbers, the apparatus comprising: first storage means for receiving values of X 0 and s, where s is equal to the greatest integer not exceeding p/q, second storage means for receiving values of AErr 0 , PInc, NInc and Y 0 , where ##EQU2## third storage means for storing values of DZy+sDZx, DZy+(s+1)DZx, and Z 0 , where DZx is the change in Z for a change dX in X, DZy is the change in Z for a change dY in Y, and Z 0 is the value of Z at the point (X 0 +vdX, Y 0 ) where v is an integer, a subtractor coupled to the first storage means, a first adder coupled to the second storage means, a second adder coupled to the third storage means, control means coupled to the adders, the subtractor and the three storage means and operative, for each value of i in the range from 0 to r-1, where r is equal to the greatest integer not exceeding q, to set Y i+1 equal to Y i +dY and, if AErr i >=0, set X i+1 equal to X i +(s+1)dX, Z i+1 equal to Z i +DZy+(s+1)DZx and AErr i+1 equal to Aerr i +PInc, and otherwise set X i+1 equal to X i +sdX, Z i+1 equal to Z i +DZy+sDZx and AErr i+1 equal to AErr i +NInc, and output means for providing the values X i+1 , Y i+1 , and Z i+1 from the second adder.

Claim 16

Apparatus for generating values of a planar function Z for designated grid points in a rectangular array at a pitch dX in an X direction and a pitch dY in a Y direction, which is perpendicular to the X direction, the designated grid points lying substantially on a line from a point (X 0 , Y 0 ) to a point (X 0 +p*dX, Y 0 +q*dY), where p and q are rational numbers, the apparatus comprising: first storage means for receiving values of X 0 and s, where s is equal to the greatest integer not exceeding p/q, second storage means for receiving values of AErr 0 , PInc, NInc and Y 0 , where ##EQU2## third storage means for storing values of DZy+sDZx, DZy+(s+1)DZx, and Z 0 , where DZx is the change in Z for a change dX in X, DZy is the change in Z for a change dY in Y, and Z 0 is the value of Z at the point (X 0 +vdX, Y 0 ) where v is an integer, a subtractor coupled to the first storage means, a first adder coupled to the second storage means, a second adder coupled to the third storage means, control means coupled to the adders, the subtractor and the three storage means and operative, for each value of i in the range from 0 to r-1, where r is equal to the greatest integer not exceeding q, to set Y i+1 equal to Y i +dY and, if AErr i >=0, set X i+1 equal to X i +(s+1)dX, Z i+1 equal to Z i +DZy+(s+1)DZx and AErr i+1 equal to Aerr i +PInc, and otherwise set X i+1 equal to X i +sdX, Z i+1 equal to Z i +DZy+sDZx and AErr i+1 equal to AErr i +NInc, and output means for providing the values X i+1 , Y i+1 , and Z i+1 from the second adder.

Claim 17

Apparatus according to claim 13, wherein the third storage means receive the value DZx, and for each value of i the control means further execute J i steps such that for each value of j in the range from 0 to J i X.sub.i+1,j =X.sub.i+1,j-1 +k/(abs.k) where k is a constant, abs.k is the absolute value of k and X i+1 ,0 is equal to X i+1 , and in each step the control means execute Z.sub.i+1,j =Z.sub.i+1,j-1 +DZx where Z i+1 ,0 is equal to Z i+1 .