System and methods for providing histogram computation in a high precision rasterization data pipeline

• US 6,917,899 B2
• Filed: 09/21/2001
• Issued: 07/12/2005
• Est. Priority Date: 09/21/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wilt, Nicholas P.
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): Raymond, Edward
• Application Number:
  US09/960,758
• Publication Number:
  US 20030059110A1
• Time in Patent Office: 1,390 Days
• Field of Search: 702/180, 382/261, 358/448
• US Class Current: 702/180
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 5/40 using histogram techniques

Abstract

A system and methods for implementing histogram computation, for example, into the rasterization pipeline of a 3-D graphics system, are provided. With the histogram computation mechanism, statistical histogram data may be generated for input data of any kind or retrieved from any source that may be specified in a 2-D array or specified in an immediate fashion to specialized data processing hardware. Depending on the nature of the input data, the data may be filtered before passing the data to data processing hardware for further processing. The data processing hardware may then apply an additional function to the input data set before calculation of the histogram data. Then, at some point, the data processing hardware may apply a function to the data to map the derived data to a real-valued function that can then be quantized to a histogram element in the range specified from zero to the number of histogram elements minus one. The corresponding element in this histogram is then incremented according to the data received as it passes through the graphics processor. Advantageously, relatively expensive host computing resources are conserved, and developers are insulated from the tedious details required of implementing histogram computation from the ground up each time it becomes desirable to compute histogram data in connection with an application.

Claims

1. A method for providing histogram computational ability in a computing system having a plurality of data sets transmitted through at least one processing chip for performing high speed data operations, comprising:

specifying, for histogram computation via a histogram computation mechanism implemented by said at least one processing chip, at least one data set of said plurality of data sets; and

computing at least one histogram from said specified at least one data set as said at least one data set transmits through said at least one processing chip, wherein said specifying includes specifying via the syntax of a procedural shader programming language.

2. A method according to claim 1, wherein said computing includes applying a masking function to said at least one data set of said plurality of data sets.

3. A method according to claim 1, further including filtering said at least one data set of said plurality of data sets before said computing of said at least one histogram and before said at least one data set is transmitted through said at least one processing chip.

4. A method according to claim 1, further including reading data back from the at least one processing chip according to a histogram reading back method call of said histogram computation mechanism.

5. A method according to claim 4, wherein the histogram reading back method call causes the histogram data to be copied to the memory pointed to by a pointer specified as an argument of the method call.

6. A method according to claim 4, wherein said histogram reading back method call is an asynchronous operation wherein the function returns immediately and signals an event when the data is read back.

7. A method according to claim 4, wherein said histogram reading back method call is a synchronous operation wherein the reading back method call blocks other operations respecting the histogram data until the requested data has been read back.

8. A method according to claim 1, wherein said computing includes:

mapping said at least one data set to at least one real-valued function data set; and

quantizing said at least one real-valued function data set.

9. A method according to claim 8, wherein a histogram element corresponding to a data value of said quantized at least one real-valued function data set is incremented according to the data value computed as it passes through the at least one processing chip.

10. A method according to claim 1, wherein said specifying includes specifying at least one state of said at least one histogram.

11. A method according to claim 10, further comprising calling a reset histogram method call of said histogram computation mechanism wherein the histogram element values for a histogram specified by the reset histogram method call are initialized to zero.

12. A method according to claim 10, further comprising calling a reset histogram method call of said histogram computation mechanism wherein the histogram element values for a histogram specified by the reset histogram method call are initialized according to a pre-defined function.

13. A method according to claim 10, wherein said specifying includes specifying at least one of (1) an element defined to be an array of elements or counts for storage of the histogram, (2) an element defined to be the number of elements in or represented by the histogram, (3) an element defined as the function to map values and (4) at least one of a minimum and maximum value used in conjunction with the element defined as the function to map values to convert at least one data value into at least one histogram element index.

14. A method according to claim 1, wherein said computing includes selecting a histogram element according to a linear quantization equation representing a desired range from ƒ

_min to ƒ

_max, the equation being defined by HistElementIndex=Floor(((ƒ

(x)−

ƒ

_min)/(ƒ

_max−

ƒ

_min))*N), wherein HistElementIndex is the index that corresponds to the position in the array to be incremented, f(x) is a function of the data set upon which said computing is being preformed and N is the number of histogram elements in the histogram.

15. A method according to claim 14, wherein said computing includes discarding values that are outside the range of from ƒ

_min to ƒ

_max.

16. A method according to claim 14, wherein computing includes allocating two extra histogram elements bringing the total number of histogram elements to (N+2), wherein one of the two extras is for values below ƒ

_min and the other of the two extras is for values above ƒ

_max.

17. A method according to claim 1, further including storing said at least one histogram computed from said at least one data set in at least one array.

18. A method according to claim 1, wherein said specifying includes specifying via a three dimensional graphics application programming interface.

19. A method according to claim 1, wherein the shader language is augmented so that at least one shader includes a histogram increment operation that specifies at least one of (1) on which histogram to operate, (2) which fragment to use as input to the histogram increment operation, (3) how to map the fragment value to a histogram element index, and (4) the value to add to the histogram element corresponding to the histogram element index.

20. A method according to claim 1, wherein said specifying includes specifying at least one state of said at least one histogram of a DIRECT3D®

device.

21. A method according to claim 1, wherein said at least one processing chip is a specialized three dimensional graphics processing chip and said plurality of data sets are processed by a high speed rasterization pipeline of a three dimensional graphics system.

22. A method according to claim 1, wherein said specifying of at least one data set includes specifying at least one of image data, texture map data, displacement map data, bump map data, convolution output data and data storable in a two dimensional array.

23. A method according to claim 1, wherein said specifying includes specifying a histogram index number that indicates which of said at least one histogram to use.

24. A method according to claim 1, wherein said specifying includes specifying how to weight a count when received for addition to a histogram during said computing.

25. A method according to claim 1, wherein said computing includes incrementing at least one bucket of said at least one histogram by at least one count.

26. A method according to claim 25, wherein said incrementing at least one bucket of said at least one histogram by at least one count includes incrementing said at least one bucket of said at least one histogram according to a tent function, whereby larger values are added to a bucket that corresponds more closely to the function value and smaller values are added to neighboring buckets.

27. A method according to claim 25, wherein said incrementing at least one bucket of said at least one histogram by at least one count includes incrementing said at least one bucket of said at least one histogram as a function of the number of counts already received by said at least one bucket.

28. A computer readable medium having stored thereon a plurality of computer-executable instructions for performing the method of claim 1.

29. A modulated data signal carrying computer executable instructions for performing the method of claim 1.

30. A computing device comprising means for performing the method of claim 1.

31. A computer readable medium having stored thereon a plurality of computer-executable modules, the computer executable modules comprising:

a histogram computation specification mechanism for specifying at least one data set to be operated upon by at least one processing chip,

wherein said at least one chip includes a histogram computation mechanism for computing, based upon a specification according to said histogram computation specification mechanism, at least one histogram from said at least one data set as said at least one data set is transmitted through said at least one chip during processing of said at least one data set in connection with a high precision data pipeline, wherein said histogram computation specification mechanism is specified via the syntax of a procedural shader programming language.

32. A computer readable medium according to claim 31, wherein an application programming interface includes said histogram computation specification mechanism.

33. A computer readable medium according to claim 31 wherein said histogram computation specification mechanism includes a mechanism for specifying a masking function to be applied to said at least one data set by said at least one chip.

34. A computer readable medium according to claim 31, further including a reading histogram data back mechanism for reading back histogram data from the at least one chip after said at least one histogram is computed.

35. A computer readable medium according to claim 31, wherein said histogram computation specification mechanism includes a mechanism for specifying at least one state of said at least one histogram.

36. A computer readable medium according to claim 35, wherein said histogram computation specification mechanism includes a mechanism for specifying a reset of a histogram computer, wherein the histogram element values for a histogram specified are initialized to zero.

37. A computer readable medium according to claim 35, wherein said histogram computation specification mechanism includes a mechanism for specifying a reset of a histogram computer, wherein the histogram element values for a histogram specified are initialized according to a pre-defined function.

38. A computer readable medium according to claim 35, wherein said mechanism for specifying at least one state of said at least one histogram includes a mechanism for specifying at least one of (1) an element defined to be an array of elements or counts for storage of the histogram, (2) an element defined to be the number of elements in or represented by the histogram, (3) an element defined as the function to map values and (4) at least one of a minimum and maximum value used in conjunction with the element defined as the function to map values to convert at least one data value into at least one histogram element index.

39. A computer readable medium according to claim 31, wherein said histogram computation specification mechanism includes a mechanism for specifying at least one state of said at least one histogram of a DIRECT3D®

device.

40. A computer readable medium according to claim 31, wherein said at least one processing chip is at least one specialized three dimensional graphics processing chip and said plurality of data sets are processed by a high speed rasterization pipeline of a three dimensional graphics system.

41. A computer readable medium according to claim 31, wherein said histogram computation specification mechanism includes a mechanism for specifying at least one data set to be at least one of image data, texture map data, displacement map data, bump map data, convolution output data and data storable in a two dimensional array.

42. A computer readable medium according to claim 31, wherein said histogram computation specification mechanism includes a mechanism for specifying a histogram index number that indicates which of said at least one histogram to use.

43. A computer readable medium according to claim 31, wherein said histogram computation specification mechanism includes a mechanism for specifying how to weight a count when received for addition to a histogram during said computing.

44. An application programming interface, stored as computer-executable instructions on a computer readable medium, for specifying at least one histogram to be computed from at least one data set as said at least one data set is transmitted through a high precision data pipeline, comprising:

a histogram computation specification mechanism for specifying at least one data set to be operated upon by at least one processing chip of said high precision data pipeline,

wherein said at least one chip include a histogram computation mechanism for computing, based upon a specification according to said histogram computation specification mechanism, at least one histogram from said at least one data set as said at least one data set is transmitted through said at least one chip during processing of said at least one data set, wherein said histogram computation specification mechanism is specified via the syntax of a procedural shader programming language.

45. An application programming interface according to claim 44, wherein said histogram computation specification mechanism includes a mechanism for specifying a masking function to be applied to said at least one data set by said at least one chip.

46. An application programming interface according to claim 44, further including a reading histogram data back mechanism for reading back histogram data from the at least one chip after said at least one histogram is computed.

47. An application programming interface according to claim 44, wherein said histogram computation specification mechanism includes a mechanism for specifying at least one state of said at least one histogram.

48. An application programming interface according to claim 47, wherein said histogram computation specification mechanism includes a mechanism for specifying a reset of a histogram computer, wherein the histogram element values for a histogram specified are initialized to zero.

49. An application programming interface according to claim 47, wherein said histogram computation specification mechanism includes a mechanism for specifying a reset of a histogram computer, wherein the histogram element values for a histogram specified are initialized according to a pre-defined function.

50. An application programming interface according to claim 47, wherein said mechanism for specifying at least one state of said at least one histogram includes a mechanism for specifying at least one of (1) an element defined to be an array of elements or counts for storage of the histogram, (2) an element defined to be the number of elements in or represented by the histogram, (3) an element defined as the function to map values and (4) at least one of a minimum and maximum value used in conjunction with the element defined as the function to map values to convert at least one data value into at least one histogram element index.

51. An application programming interface according to claim 44, wherein said histogram computation specification mechanism includes a mechanism for specifying at least one state of said at least one histogram of a DIRECT3D®

device.

52. An application programming interface according to claim 44, wherein said at least one chip is at least one specialized three dimensional graphics processing chip and said plurality of data sets are processed by a high speed rasterization pipeline of a three dimensional graphics system.

53. An application programming interface according to claim 44, wherein said histogram computation specification mechanism includes a mechanism for specifying at least one data set to be at least one of image data, texture map data, displacement map data, bump map data, convolution output data and data storable in a two dimensional array.

54. An application programming interface according to claim 44, wherein said histogram computation specification mechanism includes a mechanism for specifying a histogram index number that indicates which of said at least one histogram to use.

55. An application programming interface according to claim 44, wherein said histogram computation specification mechanism includes a mechanism for specifying how to weight a count when received for addition to a histogram during said computing.