Pseudo-random point sampling techniques in computer graphics

• US 5,025,400 A
• Filed: 06/21/1989
• Issued: 06/18/1991
• Est. Priority Date: 06/19/1985
• Status: Expired due to Term

• Current Assignee: Pixar (The Walt Disney Company)
• Original Assignee: Pixar (The Walt Disney Company)
• Inventors: Cook, Robert L., Carpenter, Loren C., Porter, Thomas K.
• Primary Examiner(s): Herndon, Heather R.
• Application Number:
  US07/379,503
• Time in Patent Office: 727 Days
• Field of Search: 364/518, 364/521, 364/522, 340/725, 340/726, 340/727, 340/728, 340/729, 340/747, 358/148, 358/158, 358/183
• US Class Current: 345/611
• CPC Class Codes: G06T 15/503 Blending, e.g. for anti-aliasing
• CPC Class Codes: Y10S 345/952 Simulation

Abstract

A computer database contains visual and other information of an object scene from which a television monitor or film display is created by electronically sampling points of the object scene information in the computer memory. Undesirable effects of aliasing are significantly reduced and substantially eliminated by pseudo-randomly distributing, in a particular manner, the occurrence of the point samples in space and time. Realistic depth of field is obtained in the images, corresponding to what is observed through a camera lens, by altering the sample point locations to simulate passing them through an optical aperture in a pseudo-random distribution thereacross. Further, effects of illumination, shadows, object reflection and object refraction are made more realistic by causing each sample point to pseudo-randomly select one of a predetermined number of possible ray directions.

Claims

1. In a method of forming an electronic signal of a video image frame that individually specifies characteristic information of each pixel of an array of pixels that forms said frame, wherein the characteristic information of each pixel is determined by point sampling, at at least one point within a boundary of each of said pixels, data stored in a computer data base that specifies various parameters relating to an object scene, wherein the improvement comprises:

providing electronic point sampling of at least one of said stored parameters with a pseudo-random distribution of sample points; and

constraining said distribution such that a Fourier transform of said distribution over an infinite extent contains substantially continuous regions.

2. The improved method according to claim 1 wherein said at least one stored parameters includes location of objects in the scene relative to the image frame.

3. The improved method according to claim 1 wherein said at least one stored parameter includes an amount that the objects in the scene change during the time represented by said video image frame, whereby object blur of said object scene is represented.

4. The improved method according to claim 1 wherein said at least one stored parameter includes a range of ray paths representative of that created by an optical imaging system, whereby a depth of field of said object scene is represented.

5. The improved method according to claim 1 wherein said at least one stored parameter includes a range of angles of reflection from objects in the scene.

6. The improved method according to claim 1 wherein said at least one stored parameter includes a range of angles of refraction by objects in the scene.

7. The improved method according to claim 1 wherein said at least one stored parameter includes a range of spatial intensity variations of illumination of objects in the scene.

8. The method of claim 1 wherein said characteristic information comprises color.

9. The method of claim 1 wherein said characteristic information comprises intensity.

10. The method of claim 1 wherein said characteristic information comprises color and intensity.

11. In a method of forming an electronic signal of a video image frame that individually specifies characteristic information of each area of an array of adjacent areas that forms said frame, wherein the characteristic information of each such area is determined by point sampling, at a plurality of points in a certain pattern within a boundary of substantially every such area in said image frame, data stored in a computer data base that specifies spatial locations and visual characteristics of an object scene for said image frame, wherein the improvement comprises:

electronically arranging said plurality of sample points in a manner such that said certain pattern is a pseudo random distribution; and

constraining said distribution such that a Fourier transform of said distribution over an infinite extent contains substantially continuous regions.

12. The method according to claim 11 wherein said improvement includes making substantially all of such areas coincident with pixels of the resulting video image frame.

13. In a method of forming an electronic signal of a video image frame that individually specifies characteristic information of each area of an array of adjacent areas that forms said frame, wherein the characteristic information of each such area is determined by point sampling, at a plurality of points in a certain pattern within a boundary of substantially every such area across said image frame, data stored in a computer data base that specifies spatial locations and visual characteristics of an object scene for said image frame, wherein the improvement comprises:

electronically arranging said plurality of sample points within substantially every such area in a spatial distribution therein; and

constraining said distribution such that a Fourier transform of said distribution over an infinite plane is substantially continuous in some regions.

14. The method according to claim 13 wherein said improvement additionally comprises the step of causing said certain pattern of sample points within substantially every one area to be different from that of substantially all its immediately adjacent areas.

15. The method according to claim 13 wherein said improvement additionally comprises determining the certain pattern of sample points for each such area by a method comprising the steps of defining a plurality of substantially non-overlapping portions within such area and then locating each sample point within an individual area portion.

16. The method according to claim 13, wherein said electronic information contains information of spatial movement of the object scene during a time period represented by said image frame, and further wherein the characteristic information of the object is determined for each of the plurality of sample points within each frame area at one of a plurality of different instants during said image frame time period, thereby to show any motion blur of the object scene that occurs during the time period of said image frame.

17. The method according to claim 16, wherein said one of a plurality of different instants of time is pseudo-randomly determined for said sample points.

18. The method according to claim 13 wherein said improvement additionally comprises the steps of establishing the characteristics of an optical imaging system, including aperture size and focal plane relative to the objects of the scene, and determining the characteristics of the objects for each sample by taking into account the distance of the objects from the focal plane and the size of the lens aperture, whereby the image frame electronic signal contains information of the objects with a certain depth of field as determined by the characteristics of the optical imaging system.

19. The method according to claim 18 wherein the step of determining the characteristics of the objects includes pseudo-randomly distributing the path of sample points through said lens aperture.

20. The method according to claim 13 wherein said improvement additionally comprises the steps of determining, for said sample points individually, a range of angles of reflection of the object scene at each point, and pseudo-randomly selecting one such angle for each such sample point, whereby other portions of the object scene that are visible by reflection from a sampled point of the object scene are determined.

21. The method according to claim 13 wherein said improvement additionally comprises the steps of determining, for the sample points individually, a range of angles of rays extending from each such point to a source of illumination of the scene, pseudo-randomly selecting one such ray angle for each such point, and determining for each of said selected rays whether other objects are in the path of the ray, whereby penumbras are shown in the image frame.

34. The method according to claim 13, 22, 23, 24, 30 or 31 wherein said improvement additionally comprises the steps of determining, for the sample point individually, a range of angles of refraction of the object scene at such points, and pseudo-randomly selecting one such angle for each such sample point, whereby other portions of the object scene that are visible by transparency through a sample point of the object scene are determined.

22. In a method of forming an electronic signal of a video image frame that individually specifies characteristic information of each of an array of pixels that forms said frame, wherein the characteristic information of each pixel is determined by point sampling, at a plurality of points within a boundary of each of said pixels, data stored in a computer data base that specifies visual characteristics of an object scene for said image frame, the improvement comprising the steps of including in said computer data base information of changes in the object scene visual characteristics that occur during the time period of said image frame, and electronically sampling the data base at said plurality of points at different instants during said time period, whereby any motion blur of the object scene is included in the resulting image frame electronic signal.

23. The improved method according to claim 22 wherein the step of sampling the data base at said plurality of points includes doing so pseudo-randomly as a function of time for each such pixel and within said time period of said image frame, whereby the image frame signal has reduced aliasing in time.

24. The improved method according to claim 22 wherein the step of sampling the data base at said plurality of points includes the steps of defining an interval of time for taking a sample for each of said plurality of points for said pixel, and pseudo-randomly determining the instant of each such sample within its said defined interval of time, whereby the image frame signal has been reduced aliasing in time.

25. The method according to claims 22-24, inclusive, wherein said improvement additionally comprises the steps of establishing the characteristics of an optical imaging system, including aperture size and focal plane relative to the objects of the scene, and determining the characteristics of the objects for each sample by taking into account the distance of the objects from the focal plane and the size of the lens aperture, whereby the image frame electronic signal contains information of the objects with a certain depth of field as determined by the characteristics of the optical imaging system.

26. The method according to any of claims 22-24, inclusive, wherein said improvement additionally comprises the steps of determining, for the sample points individually, a range of angles of reflection of the object scene at such points, and pseudo-randomly selecting one such angle for each such sample point, whereby other portions of the object scene that are visible by reflection from a sampled point of the object scene are determined.

27. The method according to any of claims 22-24, inclusive, wherein said improvement additionally comprises the steps of determining, for the sample points individually, a range of angles of rays extending from each such point to a source of illumination of the scene, pseudo-randomly selecting one such ray angle for each such point, and determining for each of said selected rays whether other objects are in the path of the ray, whereby penumbras are shown in the image frame.

28. The improved method according to claim 24 wherein the intervals of time defined for taking each sample are substantially non-overlapping.

29. The improved method according to claim 24 wherein the intervals of time defined for taking each sample are overlapped in a manner to increase the concentration of samples in the middle of the intervals of time relative to the concentration at their beginning and end.

30. In a method of forming an electronic signal of a video image frame that individually specifies characteristic information of each of an array of pixels that forms said frame, wherein the characteristic information of each pixel is determined by point sampling, at a plurality of points within a boundary of each of said pixels, data stored in a computer data base that specifies visual characteristics of an object scene for said image frame, the improvement comprising the steps of establishing the characteristics of an optical imaging system including aperture size and focal plane relative to the objects of the scene, and electronically determining the visual characteristics of the object scene at each point sample by taking into account the distance of the objects from the focal plane and the size of the lens aperture, whereby the image frame electronic signal contains information of the objects with a certain depth of field as determined by the characteristics of the optical imaging system.

31. The improved method according to claim 30 wherein the step of determining the visual characteristics of the object scene for each point sample includes pseudo-randomly determining the point on the lens from which the object scene is sampled within a field of view of the object scene that is determined by the lens aperture and location of the focal plane.

32. The method according to either of claims 30 or 31, wherein said improvement additionally comprises the steps of determining, for the sample points individually, a range of angles of reflection of the object scene at such points, and pseudo-randomly selecting one such angle for each such sample point, whereby other portions of the object scene that are visible by reflection from a sampled point of the object scene are determined.

33. The method according to either of claims 30 or 31, wherein said improvement additionally comprises the steps of determining, for the sample points individually, a range of angles of rays extending from each such point to a source of illumination of the scene, pseudo-randomly selecting one such ray angle for each such point, and determining for each of said selected rays whether other objects are in the path of the ray, whereby penumbras are shown in the image frame.

35. In a method of forming an electronic signal of a video image frame that individually specifies characteristic information of each of an array of adjacent areas that forms said frame, wherein the characteristic information such area is determined by point sampling, at a plurality of points in a certain pattern within a boundary of substantially every such area across said image frame, data stored in a computer data base that specifies spatial locations and visual characteristics of an object scene for said image frame, the improvement comprising the steps of electronically defining a plurality of substantially non-overlapping portions within such area and then locating each sample point within an individual area portion in a nonregular distribution.

36. In a method of forming an image frame by individually controlling characteristic information of each pixel in an array of pixels that forms said frame, wherein objects to be included in said image frame are represented by data stored in computer data base that specifies spatial locations and visual characteristics of said objects for said image frame, a method of accessing the information of the computer data base for determining the characteristic information of each pixel, comprising performance of the following steps electronically:

spatially dividing the area of said pixel into a plurality of non-overlapping areas,

pseudo-randomly positioning a sample point within substantially each of said areas, thereby to determine the pseudo random position of a plurality of sample points for each pixel,

determining from the computer data base the characteristic information of the closest of said objects at each of the plurality of pseudo random sample points for each pixel of said frame, and

combining the characteristic information of the samples of each pixel, thereby to determine a single characteristic information of each pixel.

39. The method according to claims 36-38, inclusive, wherein information of any movement of said objects during the time period of said image frame is included in said computer data base, and wherein the step of determining characteristic information for each offset point comprises the steps of pseudo-randomly assigning each of said sample points to one of a plurality of different times during the image frame time period, and determining object characteristic information for each sample point at its said assigned time, whereby said image will include any motion blur that occurs during the time period of said image frame.

40. The method according to any of claim 36-38, inclusive, wherein said determining step includes a method comprising the steps of establishing the characteristics of an optical imaging system, including aperture size and focal plane relative to the objects of the scene, and determining the characteristics of the objects for each sample by taking into account the distance of the objects from the focal plane and the size of the lens aperture, whereby the image frame electronic signal contains information of the objects with a certain depth of field as determined by the characteristics of the optical imaging system.

41. The method according to claims 36-38, inclusive, wherein said determining step includes a method comprising the steps of determining, for said sample points individually, a range of angles of reflection of the object scene at each point, and pseudo-randomly selecting one such angle for each such sample point, whereby other portions of the object scene that are visible by reflection form a sampled point of the object scene are determined.

42. The method according to any of claims 36-38 wherein said improvement additionally comprises the steps of determining, for the sample points individually, a range of angles of rays extending from each such point to a source of illumination of the scene, pseudo-randomly selecting one such ray angle for each such point, and determining for each of said selected rays whether other objects are in the path of the ray, whereby penumbras are shown in the image frame.

43. The method according to any of claims 36-38, inclusive, wherein said determining step includes a method comprising the steps of determining, for said sample points individually, a range of angles of refraction of the object scene at each point, and pseudo-randomly selecting one such angle for each such sample point, whereby other portions of the object scene that are visible by transparency through a sample point of the object scene are determined.

37. In a method of forming an image frame by individually controlling characteristic information of each pixel in an array of pixels that forms said frame, wherein objects to be included in said image frame are represented by data stored in a computer data base that specifies spatial locations and visual characteristics of said objects for said image frame, a method of accessing the information of the computer data base for determining the characteristic information of each pixel, comprising performance of the following steps electronically:

spatially dividing the area of said pixel into a plurality of non-overlapping areas,

determining a nominal point location within each of said areas in a non-regular pattern,

pseudo-randomly determining an offset of each such nominal point within each of said areas for each pixel within said image frame,

determining from the computer data base the characteristic information of the closest of said objects at each pseudo random offset point for each pixel of said frame, and

combining the characteristic information of the sample points in each pixel, thereby to determining a single characteristic information of each pixel.

38. In a method of forming an image frame by individually controlling characteristic information of each pixel in an array of pixels that forms said frame, wherein objects to be included in said image frame are represented by data stored in a computer data base that specifies spatial locations and visual characteristics of said objects for said image frame, a method of accessing the information of the computer data base for determining the characteristic information of each pixel, comprising performing the following steps electronically:

spatially dividing the area of said pixel into a plurality of non-overlapping areas,

determining a nominal point location in substantially the center of each of said areas,

pseudo-randomly determining an offset of each nominal point within each of said areas for each pixel within said image frame,

determining from the computer data base the characteristic information of the closest of said objects at each pseudo random offset point for each pixel of said frame, and

combining the characteristic information of each offset point in each pixel, thereby to determine a single characteristic information of each pixel.

44. In a method of forming an electronic signal of a video image frame that individually specifies characteristic information of each pixel of an array of pixels that forms said frame, wherein the characteristic information of each pixel is determined by point sampling, at at least one point within a boundary of each of said pixels, data stored in a computer data base that specifies various parameters relating to an object scene, the improvement wherein the point sampling is electronically accomplished by a pseudo-random distribution of at least one of said stored parameters such that a Fourier transform of said distribution over an infinite extent contains substantially continuous regions, and wherein said at least one stored parameter includes location of objects in the scene relative to the image frame.

45. The method of claim 44 wherein said at least one stored parameters includes location of objects in the scene relative to the image frame.

46. The method of claim 44 wherein said at least one stored parameter includes a range of ray paths representative of that created by an optical imaging system, whereby a depth of field of said object scene is represented.

47. The method of claim 44 wherein said at least one stored parameter includes a range of angles of reflection from objects in the scene.

48. The method of claim 44 wherein said at least one stored parameter includes a range of angles of refraction by objects in the scene.

49. The method of claim 44 wherein said at least one stored parameter includes a range of spatial intensity variations of illumination of objects in the scene.

50. In a method of forming an electronic signal of a video image frame that individually specifies characteristic information of each area of an array of adjacent areas that forms said frame, wherein the characteristic information of each such area is determined by point sampling, at a plurality of points in a certain pattern within a boundary of substantially every such area in said image frame, data stored in a computer data base that specifies spatial locations and visual characteristics of an object scene for said image frame, wherein the improvement comprises electronically arranging said plurality of sample points in a manner that said certain pattern is a pseudo random distribution, and wherein said improvement includes making substantially all of such areas coincident with pixels of the resulting video image frame.

51. In a method of forming an electronic signal of a video image frame that individually specifies characteristic information of each area of an array of adjacent areas that forms said frame, wherein the characteristic information of each such area is determined by point sampling, at a plurality of points in a certain pattern within a boundary of substantially every such area in said image frame, data stored in a computer data base that specifies spatial locations and visual characteristics of an object scene for said image frame, wherein the improvement comprises electronically arranging said plurality of sample points within substantially every such area in a spatial distribution therein such that a Fourier transform of such a distribution over an infinite plane is substantially continuous in some regions, and wherein said improvement additionally comprises the step of causing said certain pattern of sample points within substantially every one are to be different from that of substantially all its immediately adjacent areas.

52. The method of claim 51 wherein said improvement additionally comprises the step of causing said certain pattern of sample points within substantially every one area to be different from that of substantially all its immediately adjacent areas.

53. The method of claim 51 wherein said electronic information contains information of spatial movement of the object scene during a time period represented by said image frame, and further wherein the characteristic information of the object is determined for each of the plurality of sample points within each frame area at one of a plurality of different instants during said image frame time period, thereby to show any motion blur of the object scene that occurs during the time period of said image frame.

54. The method according to claim 53 wherein said one of a plurality of different instants of time is pseudo-randomly determined for said sample points.

55. The method of claim 51 wherein said improvement additionally comprises the steps of establishing the characteristics of an optical imaging system, including aperture size and focal plane relative to the objects of the scene, and determining the characteristics of the objects for each sample by taking into account the distance of the objects from the focal plane and the size of the lens aperture, whereby the image frame electronic signal contains information of the objects with a certain depth of field as determined by the characteristics of the optical imaging system.

56. The method according to claim 55, wherein the step of determining the characteristics of the objects includes pseudo-randomly distributing the path of sample points through said lens aperture.

57. The method of claim 51 wherein said improvement additionally comprises the steps of determining, for said sample points individually, a range of angles of reflection of the object scene at each point, and pseudo-randomly selecting one such angle for each such sample point, whereby other portions of the object scene that are visible by reflection from a sampled point of the object scene are determined.

58. The method of claim 51 wherein said improvement additionally comprises the steps of determining, for the sample points individually, a range of angles of rays extending from each such point to a source of illumination of the scene, pseudo-randomly selecting one such ray angle for each such point, and determining for each of said selected rays whether other objects are in the path of the ray, whereby penumbras are shown in the image frame.

59. In a method of forming an electronic signal of a video image frame that individually specifies the color of each pixel of an array of pixels that forms said frame, wherein the color of each pixel is determined by point sampling, at at least one point within a boundary of each of said pixels, data stored in a computer data base that specifies various parameters relating to an object scene, wherein the improvement comprises;

controlling the electronic point sampling of at least one of said stored parameters with a pseudo-random distribution; and

constraining said distribution such that a Fourier transform of said distribution over an infinite extent contains substantially continuous regions.

60. In a method of forming an electronic signal of a video image frame that individually specifies the intensity of each pixel of an array of pixels that forms said frame, wherein the intensity of each pixel is determined by point sampling, at at least one point within a boundary of each of said pixels, data stored in a computer data base that specifies various parameters relating to an object scene, wherein the improvement comprises:

controlling the electronic point sampling of at least one of said stored parameters with a pseudo-random distribution; and

constraining said distribution such that a Fourier transform of said distribution over an infinite extent contains substantially continuous regions.

61. In a method of forming an electronic signal of a video image frame that individually specifies the color and intensity of each pixel of an array of pixels that forms said frame, wherein the color and intensity of each pixel is determined by point sampling, at at least one point within a boundary of each of said pixels, data stored in a computer data base that specifies various parameters relating to an object scene, wherein the improvement comprises:

controlling the electronic point sampling of at least one of said stored parameters with a pseudo-random distribution; and

constraining said distribution such that a Fourier transform of said distribution over an infinite extent contains substantially continuous regions.

62. In a method of forming an electronic signal of a video image frame that individually specifies characteristic information of each area of an array of adjacent areas that forms said frame, wherein the characteristic information of each such area is determined by point sampling, at a plurality of points in a certain pattern within a boundary of substantially every such area across said image frame, data stored in a computer data base that specifies spatial locations and visual characteristics of an object scene for said image frame, wherein the improvement comprises:

electronically arranging said plurality of sample points within substantially every such area in a spatial distribution therein; and

constraining said distribution such that a Fourier transform of such a said distribution over an infinite plane is substantially continuous in some regions; and

determining, for the sample points individually, a range of angles of refraction of the object scene at such points; and

pseudo-randomly selecting one such angle for each such sample point, whereby other portions of the object scene that are visible by transparency through a sample point of the object scene are determined.