US5345541A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for approximating a value between two endpoint values in a three-dimensional image rendering device
Assignee: Apple Inc
•
Filing: 1991-12-20
•
Granted: 1994-09-06
•
Expires: 2011-12-20
Abstract
Abstract A method and apparatus for approximating a value distributed between two endpoints. The method and apparatus are embodied in a rendering device for calculating pixel shading values for the display of 3-D graphical images. The method approximates a function P(w)=(1-w)A+wB, where w is a provided interpolation weight between 0 and 1, A is a first endpoint value and B is a second endpoint value. The method causes exact evaluation for the cases where P(0)=A and P(1)=B. The method is comprised generally of the steps of: providing an interpolation weight value W comprised of N bit values; assigning a first predetermined pattern of N bits (J) to cause said first extreme parameter value A to be generated and a second predetermined pattern of N bits (K) to cause the second extreme parameter value B to be generated; assigning a third predetermined pattern of N bits (L) as a saturation multiplier, performing a linear interpolation to derive a parameter value for a pixel P, using a function ((J-W)A+WB); and adding a saturation value according to the criteria that if W is less than a saturation threshold, adding the quantity (L×A) to the result; or if W is greater than or equal to the saturation threshold, adding the quantity (L×B) to the result. The apparatus is comprised of a plurality of multiplexors, carry-save adders and a carry-propagate adder.
Inventors
- 👤 Michael Kelley
- 👤 Stephanie Winner
- 👤 Lee Mighdoll
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 15:49
CPC Classifications
G; G06; G06T; G06T15/00; G06T15/50; G06T15/80; G06T15/87; G06F; G06F17/00; G06F17/10; G06F17/17; G06F17/175; G06T15/83
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
312 words
In a pixel rendering system for generating pixel shading values for the display of 3-D graphical images, said pixel rendering system coupled to a computer system, a method for determining a value X that is distributed between a first value A and a second value B, and wherein said value X corresponds to a pixel shading value, said method comprising the steps of: a) providing an interpolation weight value W, said interpolation weight value W comprised of one or more bit values; b) providing a first of said one or more bit values as a first selection input, to a first selector means; c) providing said first value A and said second value B to said first selector means and a second selector means; d) if said first selection input is a first predetermined value, outputting said first value A from said first selector means to a first adder means; e) if said first selection input is a second predetermined value, outputting said second value B from said first selector means to said first adder means; f) providing a second of said bit values, if said interpolation weight value W comprises more than one bit values, as a second selection input, to said second selector means; g) if said second selection input is said first predetermined value, outputting said first value A from said second selector means to a shifting means, said shifting means for shifting output from said second selector means by one binary placeholder; h) if said second selection input is said second predetermined value, outputting said second value B from said second selector means to said shifting means; i) shifting said output of said second selector means, creating a shifted output; j) providing said shifted output to said first adder means; and k) adding output from said first selector means with said shifted output to generate said value X.
Claim 2
Dependent Claim
312 words
In a pixel rendering system for generating pixel shading values for the display of 3-D graphical images, said pixel rendering system coupled to a computer system, a method for determining a value X that is distributed between a first value A and a second value B, and wherein said value X corresponds to a pixel shading value, said method comprising the steps of: a) providing an interpolation weight value W, said interpolation weight value W comprised of one or more bit values; b) providing a first of said one or more bit values as a first selection input, to a first selector means; c) providing said first value A and said second value B to said first selector means and a second selector means; d) if said first selection input is a first predetermined value, outputting said first value A from said first selector means to a first adder means; e) if said first selection input is a second predetermined value, outputting said second value B from said first selector means to said first adder means; f) providing a second of said bit values, if said interpolation weight value W comprises more than one bit values, as a second selection input, to said second selector means; g) if said second selection input is said first predetermined value, outputting said first value A from said second selector means to a shifting means, said shifting means for shifting output from said second selector means by one binary placeholder; h) if said second selection input is said second predetermined value, outputting said second value B from said second selector means to said shifting means; i) shifting said output of said second selector means, creating a shifted output; j) providing said shifted output to said first adder means; and k) adding output from said first selector means with said shifted output to generate said value X.
Claim 3
Dependent Claim
23 words
The method as recited in claim 1 wherein said first predetermined value is binary 1 and said second predetermined value is binary 0.
Claim 4
Dependent Claim
29 words
The method as recited in claim 2 wherein said first value A is a left-most pixel shading value and said second value B is a right-most pixel shading value.
Claim 5
Dependent Claim
230 words
In a rendering system for generating pixel shading values for the display of 3-D graphical images, said rendering system coupled to a computer controlled display system, a method for providing exact interpolation values for pixel shading of a horizontal span of pixels, said horizontal span having a first extreme parameter value A and a second extreme parameter value B, said method comprising the steps of: a) providing an interpolation weight value W, said interpolation weight value W comprised of N bit values; b) assigning a first predetermined pattern of N bits (J) to cause said first extreme parameter value A to be generated and a second predetermined pattern of N bits (K) to cause said second extreme parameter value B to be generated, and a third predetermined pattern of N bits (L) as a saturation multiplier; c) performing a linear interpolation to derive a parameter value for a pixel P, using a function ((J-W)A+WB) d) if W is less than a saturation threshold value, adding the result of (L×A) to the result of step c) to generate a value corresponding to one of said exact interpolation values for pixel shading; and e) if W is greater than or equal to said saturation threshold value, adding the result of (L×B) to the result of step c) to generate a value corresponding to one of said exact interpolation values for pixel shading.
Claim 6
Dependent Claim
230 words
In a rendering system for generating pixel shading values for the display of 3-D graphical images, said rendering system coupled to a computer controlled display system, a method for providing exact interpolation values for pixel shading of a horizontal span of pixels, said horizontal span having a first extreme parameter value A and a second extreme parameter value B, said method comprising the steps of: a) providing an interpolation weight value W, said interpolation weight value W comprised of N bit values; b) assigning a first predetermined pattern of N bits (J) to cause said first extreme parameter value A to be generated and a second predetermined pattern of N bits (K) to cause said second extreme parameter value B to be generated, and a third predetermined pattern of N bits (L) as a saturation multiplier; c) performing a linear interpolation to derive a parameter value for a pixel P, using a function ((J-W)A+WB) d) if W is less than a saturation threshold value, adding the result of (L×A) to the result of step c) to generate a value corresponding to one of said exact interpolation values for pixel shading; and e) if W is greater than or equal to said saturation threshold value, adding the result of (L×B) to the result of step c) to generate a value corresponding to one of said exact interpolation values for pixel shading.
Claim 7
Dependent Claim
26 words
The method as recited in claim 4 wherein said first predetermined pattern of N bits is comprised of N bits all having a logical 1 value.
Claim 8
Dependent Claim
26 words
The method as recited in claim 5 wherein said second predetermined pattern of N bits is comprised of N bits all having a logical 0 value.
Claim 9
Dependent Claim
34 words
The method as recited in claim 6 wherein said third predetermined pattern of N bits is comprised of a first bit having a logical 1 value and N-1 bits having a logical 0 value.
Claim 10
Dependent Claim
17 words
The method as recited in claim 7 where N is an integer value from 4 to 10.
Claim 11
Dependent Claim
219 words
In a graphics accelerator for generating pixel shading values for the display of 3-D graphical images, a circuit for calculating an interpolated value X based on extreme values A and B and interpolation weight W, wherein said interpolated value X corresponds to a pixel shading value, said interpolation weight W having bit locations O-N, said circuit comprising: a) N+2 multiplexors, each of said N+2 multiplexors coupled to a first input having extreme parameter value A and a second input having extreme parameter value B, each of said N+2 multiplexors further coupled to receive a bit of said interpolation weight W, said bit of interpolation weight W providing a selector input; b) of said N+1 carry save adders, where N of said of said N+1 carry save adders have inputs coupled to an output of a corresponding one of said of said N+2 multiplexors and to a carry output and a sum of a preceding one of said of said N+1 carry save adders, and 1 of said of said N+1 carry save adders is coupled to said outputs of two of said of said N+2 multiplexors; and c) a carry propagate adder, said carry propagate adder coupled to the carry-out output and a sum output of one of said N+1 carry save adders to generate said interpolated value X.
Claim 12
Dependent Claim
219 words
In a graphics accelerator for generating pixel shading values for the display of 3-D graphical images, a circuit for calculating an interpolated value X based on extreme values A and B and interpolation weight W, wherein said interpolated value X corresponds to a pixel shading value, said interpolation weight W having bit locations O-N, said circuit comprising: a) N+2 multiplexors, each of said N+2 multiplexors coupled to a first input having extreme parameter value A and a second input having extreme parameter value B, each of said N+2 multiplexors further coupled to receive a bit of said interpolation weight W, said bit of interpolation weight W providing a selector input; b) of said N+1 carry save adders, where N of said of said N+1 carry save adders have inputs coupled to an output of a corresponding one of said of said N+2 multiplexors and to a carry output and a sum of a preceding one of said of said N+1 carry save adders, and 1 of said of said N+1 carry save adders is coupled to said outputs of two of said of said N+2 multiplexors; and c) a carry propagate adder, said carry propagate adder coupled to the carry-out output and a sum output of one of said N+1 carry save adders to generate said interpolated value X.
Claim 13
Dependent Claim
301 words
In a graphics accelerator for generating pixel shading values for the display of 3-D graphical images, a circuit for calculating an interpolated value X based on extreme values A and B and interpolation weight W, wherein said interpolated value X corresponds to a pixel shading value, said interpolation weight W having bit locations O-N, said circuit comprising: a) a first input having extreme value A and a second input having extreme value B; b) a first multiplexor coupled to said first input and said second input and coupled to receive the Nth bit of said interpolation weight W, said Nth bit providing a selection value for said first multiplexor; c) a second multiplexor coupled to said first input and said second input and coupled to receive the Oth bit of said interpolation weight W, said Oth bit providing a selection value for said second multiplexor; d) a first carry-save adder coupled to receive output of said first multiplexor as a first input and coupled to receive output of said second multiplexor as a second input; e) a third multiplexor coupled to said first input having extreme value A and said second input having extreme value B and coupled to receive said Nth bit of said interpolation weight W, said Nth bit providing a selection value for said third multiplexor; f) a second carry-save adder coupled to receive an output corresponding to sum output of said first carry-save adder and coupled to receive an output corresponding to carry-output of said first carry-save adder and coupled to receive output of said third multiplexor as a carry-in input; and g) a carry propagate adder coupled to a carry-out output of said second carry-save adder and a sum output of said second carry-save adder as addition operands, and providing as output said interpolated value X.
Claim 14
Dependent Claim
301 words
In a graphics accelerator for generating pixel shading values for the display of 3-D graphical images, a circuit for calculating an interpolated value X based on extreme values A and B and interpolation weight W, wherein said interpolated value X corresponds to a pixel shading value, said interpolation weight W having bit locations O-N, said circuit comprising: a) a first input having extreme value A and a second input having extreme value B; b) a first multiplexor coupled to said first input and said second input and coupled to receive the Nth bit of said interpolation weight W, said Nth bit providing a selection value for said first multiplexor; c) a second multiplexor coupled to said first input and said second input and coupled to receive the Oth bit of said interpolation weight W, said Oth bit providing a selection value for said second multiplexor; d) a first carry-save adder coupled to receive output of said first multiplexor as a first input and coupled to receive output of said second multiplexor as a second input; e) a third multiplexor coupled to said first input having extreme value A and said second input having extreme value B and coupled to receive said Nth bit of said interpolation weight W, said Nth bit providing a selection value for said third multiplexor; f) a second carry-save adder coupled to receive an output corresponding to sum output of said first carry-save adder and coupled to receive an output corresponding to carry-output of said first carry-save adder and coupled to receive output of said third multiplexor as a carry-in input; and g) a carry propagate adder coupled to a carry-out output of said second carry-save adder and a sum output of said second carry-save adder as addition operands, and providing as output said interpolated value X.
References Cited (Backward Citations)
US4819192A
Cited
US4805116A
Cited
US5025405A
Cited
US5001651A
Cited
US5163127A
Cited
US5157388A
Cited
US5222204A
Cited
US5113362A
Cited
US5148381A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-09-05 | 1998-03-07 | 1998-09-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-09-05 | 2002-03-07 | 2002-09-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-09-05 | 2006-03-07 | 2006-09-06 | $7700.00 | Window Closed / Lapsed |