US5729672A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Ray tracing method and apparatus for projecting rays through an object represented by a set of infinite surfaces
Assignee: Imagination Technologies Ltd
•
Filing: 1995-06-06
•
Granted: 1998-03-17
•
Expires: 2015-06-06
Abstract
Abstract A method and apparatus for shading three-dimensional images for display on a screen by displaying each object as a group of infinite surfaces, projecting rays into the image, determining the location of the intersection of each ray with each surface and determining whether any intersected surface is visible at an elementary, pixel, level. Shading that occurs as a in-image light projection is analyzed by designating the generated light as a light volume determining the intersection of the ray with the light volume, and shading the pixel point as a function of the relationship between the visible surface and the light volume. The rate of shading is enhanced by dividing the screen into a number of sub-regions and determining the location of the intersection of each object contained with the sub-region through the rays projected into the sub region. The size of the sub-regions is set by determining a bounding volume for each object on the display screen and subdividing the display based on the bounding volumes. The apparatus that performs this shading has a plurality of groups of processing elements; each group of processing elements has its own cache for storing and defining surfaces of the image. The apparatus determines depth values for the surfaces of the image based on data contained in the cache for first group of processors and then determines depth values based on the data contained in the cache for the second group of processors.
Inventors
- 👤 Martin Ashton
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 04:53
CPC Classifications
G; G06; G06T; G06T15/00; G06T15/06
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
81 words
A method for shading a three dimensional image for display on a screen comprising the steps of: representing each object in the image by a group of infinite surfaces; for each elementary area of the screen projecting a ray into the 3-dimensional image; determining the location of the intersection of the ray with each surface; determining whether any intersected surface is visible at that elementary area; and shading the elementary area for display in dependence on the result of the determination.
Claim 2
Independent Claim
81 words
A method for shading a three dimensional image for display on a screen comprising the steps of: representing each object in the image by a group of infinite surfaces; for each elementary area of the screen projecting a ray into the 3-dimensional image; determining the location of the intersection of the ray with each surface; determining whether any intersected surface is visible at that elementary area; and shading the elementary area for display in dependence on the result of the determination.
Claim 3
Dependent Claim
54 words
A method for shading a three dimensional image for display on a screen according to claim 1 in which each surface is designated as a forward facing surface or a reverse facing surface and the relative locations of intersections with forward and reverse facing surfaces are used in determining whether a surface is visible.
Claim 4
Dependent Claim
46 words
A method for shading a three dimensional image for display on a screen according to claim 2 wherein an elementary area is visible if the furthest forward facing surface intersection is closer to the projection point of the ray than the furthest reverse facing surface intersection.
Claim 5
Dependent Claim
40 words
A method for shading a three dimensional image for display on a screen according to claim 1 in which for each elementary area a ray is projected in turn through the groups of surfaces representing the objects in the image.
Claim 6
Dependent Claim
40 words
A method for shading a three dimensional image for display on a screen according to claim 4 in which for each elementary area a ray is projected through each surface in turn of each group of surfaces representing an object.
Claim 7
Dependent Claim
58 words
A method for shading a three dimensional image for display on a screen according to claim 4 in which the nearest visible surface in a group of surfaces representing an object is compared with the nearest visible surface from all preceding groups of surfaces and the elementary area is shaded in dependence on the result of the comparison.
Claim 8
Dependent Claim
68 words
A method for shading a three dimensional image for display on a screen according to claim 1 including the steps of: designating an object as a shadow object; determining a boundary of the shadow object on each ray passing through each elementary area; and shading an elementary area with a modified shade if a surface visible in that elementary area is within the boundary of the shadow object.
Claim 9
Dependent Claim
53 words
A method for shading a three dimensional image for display on a screen according to claim 1 including the steps of: designating an object as a transparent object; and modifying the shade applied to an elementary area if the visible surface at the elementary area is behind the transparent object in the image.
Claim 10
Dependent Claim
83 words
Apparatus for shading a three dimensional image for display on a screen comprising: means for supplying data defining group of infinite surfaces representing each object in the image; means for generating a depth value for each surface for each elementary area of the screen in dependence on the distance of that surface from an image plane; means for determining whether any surface is visible at that elementary area; and means for shading that elementary area in dependence on the result of the determination.
Claim 11
Dependent Claim
83 words
Apparatus for shading a three dimensional image for display on a screen comprising: means for supplying data defining group of infinite surfaces representing each object in the image; means for generating a depth value for each surface for each elementary area of the screen in dependence on the distance of that surface from an image plane; means for determining whether any surface is visible at that elementary area; and means for shading that elementary area in dependence on the result of the determination.
Claim 12
Dependent Claim
55 words
Apparatus for shading a three dimensional image for display on a screen according to claim 9 in which each surface is designated as a forward facing surface or a reverse facing surface and the relative depths of forward and reverse facing surfaces are used in determining whether a surface is visible at an elementary area.
Claim 13
Dependent Claim
46 words
Apparatus for shading a three dimensional image for display on a screen according to claim 9, including: means for comparing the relative depths of visible surfaces in the image for each elementary area and shading the elementary area in dependence on the result of the comparison.
Claim 14
Dependent Claim
42 words
Apparatus for shading a three dimensional image for display on a screen according to claim 9 in which the depth value generating means generates a depth value for each surface of each object in turn for each elementary area of the image.
Claim 15
Dependent Claim
19 words
Apparatus for shading a three dimensional image for display according to claim 9 provided on a single integrated circuit.
Claim 16
Independent Claim
77 words
A method for shading a three dimensional image for display comprising the steps of: supplying data defining a group of infinite surfaces representing each object in the image; for each elementary area of the display generating a depth value for each surface in dependence on the distance of that surface from an image plane; determining whether any surface is visible at that elementary area, and shading that elementary area in dependence on the result of the determination.
Claim 17
Independent Claim
77 words
A method for shading a three dimensional image for display comprising the steps of: supplying data defining a group of infinite surfaces representing each object in the image; for each elementary area of the display generating a depth value for each surface in dependence on the distance of that surface from an image plane; determining whether any surface is visible at that elementary area, and shading that elementary area in dependence on the result of the determination.
Claim 18
Dependent Claim
54 words
A method for shading a three dimensional image for display on a screen according to claim 14 in which each surface is designated as a forward facing surface or a reverse facing surface and the relative locations of itersections with forward and reverse facing surfaces are used in determining whether a surface is visible.
Claim 19
Dependent Claim
43 words
A method for shading a three dimensional image for display on a screen according to claim 15 wherein an elementary area is visible if the furthest forward facing surface intersection is closer to the image plane than the furthest reverse facing surface intersection.
Claim 20
Dependent Claim
66 words
A method for shading a three dimensional image for display on a screen according to claim 14 in which the depth value for the nearest visible surface in a group of surfaces representing an object is compared with the depth value for the nearest visible surface from all preceding groups of surfaces and the elementary area is shaded in dependence on the result of the comparison.
Claim 21
Dependent Claim
67 words
A method for shading a three dimensional image for display on a screen according to claim 14 including the steps of: designating an object as a shadow object; determining depth values for surfaces making up the shadow object for each elementary area; and shading an elementary area with a modified shade if a surface visible in that elementary area is within the boundary of the shadow object.
Claim 22
Independent Claim
112 words
A method for shading a three dimensional image for display on a screen comprising the steps of: representing each object in the image as a group of infinite surfaces; for each elementary area of the display projecting a ray into the 3-dimensional image; determining the location of the intersection of the ray with each surface; determining whether any intersected surface is visible at that elementary area; and including the steps of: designating an object as a light volume; determining the intersection of each ray with the light volume; and shading an elementary area in dependence on the surface visible at that elementary area and its location in relation to the light volume.
Claim 23
Independent Claim
112 words
A method for shading a three dimensional image for display on a screen comprising the steps of: representing each object in the image as a group of infinite surfaces; for each elementary area of the display projecting a ray into the 3-dimensional image; determining the location of the intersection of the ray with each surface; determining whether any intersected surface is visible at that elementary area; and including the steps of: designating an object as a light volume; determining the intersection of each ray with the light volume; and shading an elementary area in dependence on the surface visible at that elementary area and its location in relation to the light volume.
Claim 24
Independent Claim
121 words
A method for shading a three dimensional image for display on a screen comprising the steps of: representing each object in the image as a group of infinite surfaces; determining a bounding volume for each object projected onto the display screen; subdividing the display into a plurality of sub-regions, the size of the sub-regions being dependent on the complexity of the image in each area of the screen; for each pixel of each sub-region projecting a ray into the image; determining the location of the intersection of the ray with each surface of each object contained within that sub-region; determining whether any intersected surface is visible at that pixel; and shading the pixel in dependence on the result of the determination.
Claim 25
Independent Claim
121 words
A method for shading a three dimensional image for display on a screen comprising the steps of: representing each object in the image as a group of infinite surfaces; determining a bounding volume for each object projected onto the display screen; subdividing the display into a plurality of sub-regions, the size of the sub-regions being dependent on the complexity of the image in each area of the screen; for each pixel of each sub-region projecting a ray into the image; determining the location of the intersection of the ray with each surface of each object contained within that sub-region; determining whether any intersected surface is visible at that pixel; and shading the pixel in dependence on the result of the determination.
Claim 26
Dependent Claim
39 words
A method for shading according to claim 1 including the step of interleaving the determination of ray surface intersections for rows of pixels in a sub-region with the determination of ray/surface intersections for rows of pixels in other sub-regions.
Claim 27
Independent Claim
120 words
A method for shading a three dimensional image for display on a screen comprising the steps of: representing each object in the image as a group of infinite surfaces; subdividing the screen into a plurality of sub-regions,; for each pixel of each sub-region projecting a ray into the image; determining the location of the intersection of the ray with each surface of each object contained within that sub-region; determining whether any intersected surface is visible at that pixel; and shading the pixel for display in dependence on the result of the determination, wherein the determination of ray/surface intersections for groups of pixels in one sub-region is interleaved with the determination of ray/surface intersections for groups of pixels in other sub-regions.
Claim 28
Independent Claim
120 words
A method for shading a three dimensional image for display on a screen comprising the steps of: representing each object in the image as a group of infinite surfaces; subdividing the screen into a plurality of sub-regions,; for each pixel of each sub-region projecting a ray into the image; determining the location of the intersection of the ray with each surface of each object contained within that sub-region; determining whether any intersected surface is visible at that pixel; and shading the pixel for display in dependence on the result of the determination, wherein the determination of ray/surface intersections for groups of pixels in one sub-region is interleaved with the determination of ray/surface intersections for groups of pixels in other sub-regions.
Claim 29
Dependent Claim
20 words
A method for shading according to claim 22 wherein the groups of pixels comprise lines of pixels in the sub-regions.
Claim 30
Dependent Claim
36 words
A method for shading according to claim 22 wherein groups of pixels from sub-regions in less complex parts of the image are interleaved with groups of pixels from sub-regions in more complex parts of the image.
Claim 31
Independent Claim
172 words
An apparatus for shading a three dimensional image for display on a screen comprising; a plurality of groups of processing elements for determining depth values for surfaces in the image for each elementary area of the screen in dependence on the distances of the surface from an image plane and for determining whether any surface is visible at that elementary area, wherein each group of processing elements has an associated cache memory means for storing data defining the various surfaces in the image, and the groups of processing elements are coupled together by a bus means, and wherein data is read from the associated cache memory means of a first group of processing elements and transmitted via the bus means to the other group of processing elements for determination of depth values until all data from the associated cache memory means of the first group of processing elements has been read and wherein reading of data then takes place from the associated cache memory means of a second group of processing elements.
Claim 32
Independent Claim
172 words
An apparatus for shading a three dimensional image for display on a screen comprising; a plurality of groups of processing elements for determining depth values for surfaces in the image for each elementary area of the screen in dependence on the distances of the surface from an image plane and for determining whether any surface is visible at that elementary area, wherein each group of processing elements has an associated cache memory means for storing data defining the various surfaces in the image, and the groups of processing elements are coupled together by a bus means, and wherein data is read from the associated cache memory means of a first group of processing elements and transmitted via the bus means to the other group of processing elements for determination of depth values until all data from the associated cache memory means of the first group of processing elements has been read and wherein reading of data then takes place from the associated cache memory means of a second group of processing elements.
Claim 33
Independent Claim
110 words
A method for shading a three dimensional image for display on a screen comprising the steps of: supplying data defining a group of infinite surfaces representing each object; for each elementary area of the display generating a depth value for each surface in dependence on the distance of that surface from on image plane; determining whether any surface is visible at that elementary area; and including the steps of designating an object as a light volume, determining whether any visible surface falls within the light volume; and, shading the elementary area in dependence on the surface visible at the elementary area and its location in relation to the light volume.
Claim 34
Independent Claim
110 words
A method for shading a three dimensional image for display on a screen comprising the steps of: supplying data defining a group of infinite surfaces representing each object; for each elementary area of the display generating a depth value for each surface in dependence on the distance of that surface from on image plane; determining whether any surface is visible at that elementary area; and including the steps of designating an object as a light volume, determining whether any visible surface falls within the light volume; and, shading the elementary area in dependence on the surface visible at the elementary area and its location in relation to the light volume.
Claim 35
Independent Claim
120 words
A method for shading a three dimensional image for display on a screen comprising the steps of: supplying data defining a group of infinite surfaces representing each object in the image; determining a bounding volume for each object projected onto the display screen; subdividing the display into a plurality of sub-regions, the size of the sub-regions being dependent on the complexity of the image in each area of the screen; and for each pixel of each sub-region, generating a depth value for each surface within that sub-region in dependence on the distance of that surface from the image plane; determining whether any surface is visible at that pixel and shading the pixel in dependence on the result of the determination.
Claim 36
Independent Claim
120 words
A method for shading a three dimensional image for display on a screen comprising the steps of: supplying data defining a group of infinite surfaces representing each object in the image; determining a bounding volume for each object projected onto the display screen; subdividing the display into a plurality of sub-regions, the size of the sub-regions being dependent on the complexity of the image in each area of the screen; and for each pixel of each sub-region, generating a depth value for each surface within that sub-region in dependence on the distance of that surface from the image plane; determining whether any surface is visible at that pixel and shading the pixel in dependence on the result of the determination.
Claim 37
Dependent Claim
40 words
A method for shading according to claim 27 including the step of interleaving the generation of depth values surface for rows of pixels in a first sub-region with the generation of depth values for rows of pixels in other sub-regions.
Claim 38
Independent Claim
107 words
A method for shading a three dimensional image for display on a screen comprising the steps of: representing each object in the image as a group of surfaces; subdividing the screen into a plurality of sub-regions; for each pixel of each sub-region generating a depth value for each surface of each object contained within that sub-region; determining whether any surface is visible at that pixel; and shading the pixel for display in dependence on the result of the determination, wherein the determination of depth values for groups of pixels in one sub-region is interleaved with the determination of depth values for groups of pixels in other sub-regions.
Claim 39
Independent Claim
107 words
A method for shading a three dimensional image for display on a screen comprising the steps of: representing each object in the image as a group of surfaces; subdividing the screen into a plurality of sub-regions; for each pixel of each sub-region generating a depth value for each surface of each object contained within that sub-region; determining whether any surface is visible at that pixel; and shading the pixel for display in dependence on the result of the determination, wherein the determination of depth values for groups of pixels in one sub-region is interleaved with the determination of depth values for groups of pixels in other sub-regions.
Claim 40
Dependent Claim
20 words
A method for shading according to claim 29 wherein the groups of pixels comprise lines of pixels in the sub-regions.
Claim 41
Dependent Claim
36 words
A method for shading according to claim 29 wherein groups of pixels for sub-regions in less complex parts of the image are interleaved with groups of pixels from sub-regions in more complex parts of the image.
References Cited (Backward Citations)
US5317689A
Cited
US4865423A
Cited
US5088054A
Cited
EP0358493A2
Cited
US5142617A
Cited
US5101475A
Cited
EP0393309A1
Cited
US5226113A
Cited
US5313568A
Cited
US5402532A
Cited
US5377313A
Cited
US5416729A
Cited
US5355442A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-03-16 | 2001-09-15 | 2002-03-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-16 | 2005-09-15 | 2006-03-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-16 | 2009-09-15 | 2010-03-17 | $7700.00 | Window Closed / Lapsed |