Computerized image system

• US 20040100465A1
• Filed: 02/24/2003
• Published: 05/27/2004
• Est. Priority Date: 08/24/2000
• Status: Active Grant

• Current Assignee: Patent Holding Company
• Original Assignee: Patent Holding Company
• Inventors: Stowe, Jason A, Clayton, Douglas B, Vandrovec, Bryan M
• Granted Patent: US 7,034,825 B2
• Time in Patent Office: Days
• US Class Current: 345/427
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 2200/16 involving adaptation to the client's capabilities
• CPC Class Codes: G06T 2210/08 Bandwidth reduction

Abstract

This system and process for providing a rendered image of a virtual 3-D scene comprises an image generating system which stores therein data defining the 3-D scene. Responses to receiving control data such as viewing parameters, editing commands, or instructions to a software application working with the scene data, the visualization systems renders a pixel data image of the scene and transmits the pixel data over a data network, such as the Internet, to a user computer to be viewed on a display device, such as a monitor.

Claims

1. A dynamic media system comprising:

an image generating computer system having electronic storage storing scene data for a three dimensional scene;

a user computer connected with the image generating computer system over a data communications link and transmitting control data to said image generating computer system over said link;

the image generating computer system receiving the control data and automatically rendering electronic image data from the control data and the scene data, said electronic image data representing an image of the scene seen from a point of view, the image generating computer system transmitting the pixel image data to the user over the communications link; and

the user computer receiving the electronic image data and displaying the electronic image data at the user computer as a visual image viewable by a user.

2. The system of claim 1, wherein the communication link is a computer data network.

3. The system of claim 2, wherein the computer data network is the Internet.

4. The system of claim 2, wherein the computer data network is a local area network.

5. The system of claim 2, wherein the computer data network comprises a wireless cell communication system.

6. The system of claim 1, wherein the communication link is a cable TV link.

7. The system of claim 1, wherein the communication link is a telephone connection.

8. The system of claim 1, wherein the image generating computer system comprises a geometric system storing the scene data.

9. The system of claim 8, wherein the geometric system comprises a plurality of separate geometric computer systems each storing therein a respective version of the scene data.

10. The system of claim 8, wherein the image generating computer system further comprises

a visualization system connected by a communication link to the geometric system and receiving the scene data therefrom, said visualization system rendering the image from the scene data received from the geometric system and transmitting the rendered image to the user system.

11. The system of claim 10, wherein the communication link between the geometric system and the visualization system is a dedicated data link.

12. The system of claim 1, wherein the control data comprises an instruction selected from the group consisting of

instructions directing a change of the point of view,

instructions directing a change in an optical parameter of viewing the scene, instructions to modify the scene data, and

instructions to application software controlling the scene data.

13. The system of claim 10, wherein the control data comprises an instruction selected from the group consisting of instructions directing a change of the point of view,

instructions directing a change in an optical parameter of viewing the scene,

instructions to modify the scene data, and

instructions to application software controlling the scene data.

14. The system of claim 13, wherein the visualization system transmits the instruction to the geometric system.

15. The system of claim 14, wherein, where the instruction is an instruction directing a change of the point of view or of the optical parameter of viewing, the visualization system does not transmit the instruction to the geometric system.

16. The system of claim 1, wherein the image data is pixel data.

17. The system of claim 1, wherein the image data is transmitted to the user computer as compressed pixel data.

18. The system of claim 17, wherein the pixel data is compressed using a JPEG protocol.

19. The system of claim 1, wherein the image data is transmitted as a video stream.

20. The system of claim 19, wherein the communications link is a cable TV link carrying the video stream.

21. The system of claim 19, wherein the video stream is in a raw video format.

22. The system of claim 19, wherein the video stream is compressed video.

23. The system of claim 22, wherein the video is compressed using an MPEG protocol.

24. The system of claim 19, and said video stream including audio data configured to be converted to audible sound by the user computer.

25. The system of claim 24, wherein the audio data is derived from the scene data.

26. The system of claim 1, wherein the user computer has software therein providing an interactive application to the user for modifying the scene data.

27. A dynamic media system comprising:

a geometric control system having data storage, said data storage holding scene data representative of visual objects of a three dimensional scene;

a plurality of visualization systems connected with and communicating with the geometric control system; and

a plurality of user computers each communicating with a respective visualization system via a link through a computer data network;

each of said user computers having a display for displaying images and a data entry device for entering data to the user computer;

the geometric control system transmitting the scene data to the visualization system;

the user computers each transmitting control data to the visualization system associated therewith;

the visualization systems each rendering from the scene data a respective electronic image representing a frame view of the scene from a point of view specific to the associated user computer; and

the visualization systems transmitting the image to the associated user computer, said user computer displaying the image.

31. The system of claim 27, wherein the geometric system comprises a plurality of geometric host computer systems connected with each other, each of the geometric host computer systems communicating with at least one of the visualization systems.

32. The system of claim 31, wherein the geometric host computer systems each store therein a respective version of the scene data, said version comprising a data portion of recent scene data and a data portion of older scene data.

33. The system of claim 32, wherein the recent scene data for the geometric host computer system corresponds to an area in the scene proximate the point of view of the user computers associated with the visualization system communicating therewith.

34. The system of claim 27, wherein the computer data network is the Internet.

35. The system of claim 27, wherein the computer data network is a local area network.

28. The system of claim 28, and

said visualization systems being separated from one another or the network by at least one node, and each being connected with the respective user computer with less than three network nodes.

29. The system of claim 28, and

said visualization systems each being connected with the geometric control system by a dedicated data link.

30. The system of claim 29, wherein each of the visualization systems communicates with at least two of the user computers.

36. The system of claim 28, wherein the computer data network is a wireless cell communication network.

37. A dynamic media system comprising:

a user computer having a connection to a data communication link;

a data entry device connected with the user computer and providing for a user the capability to enter data to the user computer; and

a display device connected with the user computer and displaying images therefrom;

the user computer receiving input data from the data entry device and forming control data from the input data, said control data being configured to cause a change in data selected from the group consisting of scene data defining a 3D scene from which an image can be desired, and data defining optical parameters used in deriving said image;

the user computer transmitting the control data over the data communication link;

said user computer receiving electronic image data over the data communications network, said electronic image data being produced dependent on said scene data and said control data and representing a view of the scene according to the viewing parameters; and

the user computer causing the display device to display an output image derived from the electronic image data thereon.

38. The system of claim 37, wherein the data communication link is the Internet.

39. The system of claim 37, wherein the data communication link is a local area network.

40. The system of claim 37, wherein the data communication network is a wireless cell system.

41. The system of claim 37, wherein the data communication network is a cable TV link.

42. The system of claim 37, wherein the data communication network is a telephone connection.

43. The system of claim 37, wherein the control data comprises electronic instructions configured to be received and acted on by a software application operating in a computer image system connected with the data communication link.

44. The system of claim 37, wherein the control data is configured to cause a change in position or visual attributes of at least one visual object which is part of the scene data.

45. The system of claim 37, wherein the control data comprises data configured to cause alteration in data representing a point of view for the view of the scene.

46. The system of claim 37, wherein the control data comprises data configured to cause alteration in data representing an optical parameter for the view of the scene.

47. The system of claim 46, wherein the optical parameter is selected from the group consisting of focal length, depth of field, camera lens distortion optics and atmospheric transparency.

48. The system of claim 37, wherein the data entry device is a keyboard, a mouse, a joystick or a touch sensitive pad.

49. The system of claim 37, wherein the electronic image data is pixel data.

50. The system of claim 37, wherein the electronic image data is compressed pixel data.

51. The system of claim 50, wherein the image data is compressed according to a JPEG protocol.

52. The system of claim 37, wherein the image data is transmitted a part of a video stream.

53. The system of claim 52, wherein the communication link is a cable TV link.

54. The system of claim 52, wherein the video stream is in a raw video format.

55. The system of claim 53, wherein the video stream is compressed video.

56. The system of claim 55, wherein the video is compressed using an MPEG protocol.

57. The system of claim 52, and said video stream including audio data configured to be converted to audible sound by the user computer.

58. The system of claim 57, wherein the audio data is derived from the scene data.

59. The system of claim 37, and said user computer receiving the data input, transmitting the control data, and displaying the output image at points in time in close enough proximity for real-time interactive access to the scene data from the user.

60. The system of claim 37, wherein the user computer receives the data input, transmits the control data, receives the image pixel data, and displays the output image within less than about 15 seconds.

61. The system of claim 37, wherein the user computer receives the data input, transmits the control data, receives the image pixel data, and displays the output image within less than about 0.05 seconds.

62. A dynamic media system comprising:

an image computer system storing scene data representing a three dimensional scene and viewing data representing at least one viewing parameter for viewing the scene, the viewing data including data defining a point of view; and

a communication connection linking the image computer system to a data communication link;

the image computer system receiving control data through said communication link from a remote source, said control data being configured to interact with the image computer system so as to cause alteration in the scene data or so as to cause formulation or modification of the viewing data;

the image computer system automatically rendering an electronic image from the scene data responsive to receiving the control data, said image data representing a view of the scene dependent upon the viewing data;

the image computer system transmitting the electronic image over the communication link in a format effective to reach the source of the control data and in a form such that a viewable image can be derived from the electronic image and displayed.

63. The system of claim 62, wherein the data communication link is the Internet.

64. The system of claim 62, wherein the data communication link is a local area network.

65. The system of claim 62, wherein the data communication link is a wireless cell communication network.

66. The system of claim 62, wherein the data communication link is a cable TV link.

67. The system of claim 62, wherein the control data comprises an instruction directing a change in the point of view data.

68. The system of claim 62, wherein the control data comprises an instruction selected from the group consisting of

instructions directing a change of the point of view,

instructions directing a change in an optical parameter of viewing the scene,

instructions to modify the scene data, and

instructions to application software controlling the scene data.

69. The system of claim 62, wherein the image computer system is connected with a second data link and receives the scene data over the second data link.

70. The system of claim 69, wherein the control data comprises an instruction selected from the group consisting of

instructions directing a change of the point of view,

instructions directing a change in an optical parameter of viewing the scene,

instructions to modify the scene data, and

instructions to application software controlling the scene data.

71. The system of claim 70, wherein the image computer system transmits the instruction over the second data link in a format configured to be used to affect the scene data received by the image computer system.

72. The system of claim 69, wherein the first and second data links comprise a connection through the Internet.

73. The system of claim 69, wherein the second data link is a dedicated data link.

74. The system of claim 62, wherein the electronic image is transmitted to the user computer as pixel data.

75. The system of claim 62, wherein the electronic image is transmitted to the user computer as compressed pixel data.

76. The system of claim 75, wherein the pixel data is compressed using a JPEG protocol.

77. The system of claim 62, wherein the electronic image is transmitted as part of a video stream.

78. The system of claim 77, wherein the data communication link is a cable TV connection.

79. The system of claim 77, wherein the video stream is in a raw video format.

80. The system of claim 77, wherein the video stream is compressed video.

81. The system of claim 80, wherein the video is compressed using an MPEG protocol.

82. The system of claim 77, wherein the video stream includes audio data configured to be converted to audible sound.

83. The system of claim 82, wherein the image computer includes a sound engine which derives the audio data from the scene data and the point of view data.

84. The system of claim 62, wherein the image computer system operates so that between the receiving of the control data and the transmitting of the electronic image rendered therefrom, a period of time of less than about 15 seconds elapses.

85. The system of claim 62, wherein the image computer system operates so that between the receiving of the control data and the transmitting of the electronic image rendered therefrom, a period of time of less than about 0.05 seconds elapses.

86. The system of claim 62, and

the image computer system storing at least some of the scene data organized in a multiresolution virtual uniform subdivision data structure, the image computer system using the multiresolution virtual uniform subdivision data structure to render the electronic image.

87. The system of claim 62, and

the scene data including data defining a light source and a visual object;

said image computer system rendering the pixel image data, said rendering including beam tracing the light source from a location on the visual object in the scene.

88. The system of claim 87, wherein

the image computer system further includes graphics pipeline circuitry;

said graphics pipeline circuitry generating rasterized illumination data corresponding to said beam tracing.

89. A method of preparing an electronic image, said method comprising:

creating scene data defining a three dimensional scene, said scene data including data defining at least one area light source and at least one visual object;

receiving control data over a data communication link;

rendering, responsive to the control data, an electronic image from scene data, said electronic image representing a view of the scene from a point of view; and

transmitting the electronic image over the data communication link in a form such that the electronic image can be received and displayed as a viewable image.

90. The method of claim 89, wherein

the rendering being based on optical parameter data representing optical parameters for the view of the scene, the optical parameters including data defining the point of view;

and

the control data comprising data configured to cause a change in the scene data or to cause a change in the optical parameter data.

91. The method of claim 90, and

the control data comprising data configured to cause a change in the scene data.

92. The method of claim 91, wherein the control data is an instruction to a software application generating or modifying the scene data.

93. The method of claim 92, wherein the software application is run on a first computer system and the rendering step is run on a second computer system.

94. The method of claim 93 wherein

the control data is received at a second computer system, and

the method further comprises transmitting the control data from the second computer to the first computer.

95. The method of claim 94, and further comprising

receiving the scene data from the first computer at the second computer.

96. The method of claim 89, and further comprising

receiving at a computer system data transmitted from a separate geometric system, the rendering step being performed at least in part by the computer system.

97. The method according to claim 96, wherein the control data comprises data configured to cause a change in the optical parameter data.

98. The method of claim 97, wherein the optical parameter data is stored on the computer system, and the data changing the optical parameter data is used by an application running on the computer system to change the optical parameter data.

99. The method of claim 89, wherein said rendering includes tracing a beam from at least one point on the visual object and deriving for said point rasterized data representing the area light source as seen from the point.

100. The method of claim 99, wherein said beam tracing includes defining a beam frustrum enclosing the area light source.

101. The method of claim 100, wherein said defining of the frame further includes applying a rotational orientation to the frustrum.

102. The method of claim 101, wherein the rotational orientation is a random angular displacement.

103. The method of claim 99, wherein the rasterized data is derived using dedicated raster-generating circuitry.

104. The method of claim 103, wherein the raster-generating circuitry performs a plurality of independent operations each on a respective portion of the circuitry.

105. The method of claim 104, wherein, while the rendering is being done by performing one of the independent operations, other calculations are performed using the other independent operations.

106. The method of claim 105, wherein the other calculations are part of a process of deriving rasterized data from a second light source, or for a different point on the same visual object or another visual object.

107. The method of claim 99, and

the beam trace including forming subscene data representing a subscene including the area light source and at least some of the visual objects.

108. The method of claim 107, and

the rasterized area light data is derived using dedicated raster-generating circuitry.

109. The method of claim 108, and

said deriving rasterized data further comprising providing the subscene data to the dedicated circuitry.

110. The method of claim 109, wherein the raster-generating circuitry performs a plurality of independent operations each on a respective portion of the circuitry.

111. The method of claim 110, wherein, while the rendering is being done by performing one of the independent operations, other calculations are performed using the other independent operations.

112. The method of claim 111, wherein the other calculations are part of a process of deriving rasterized data from a second light source, or for a different point on the same visual object or another visual object.

113. The method of claim 89, and

said creating of scene data including organizing data representing the area light source and visual object in a multiresolution virtual uniform subdivision data structure.

114. The method of claim 113, and

said rendering including deriving for at least one point on the visual object rasterized data representing the area light source as seen from the point;

and

the point on the visual object being identified by tracing a ray from the point of view using the multiresolution virtual uniform subdivision data structure.

115. The method according to claim 99, and

directional reflective coefficients of the visual object being stored as reflection texture data;

said rendering step including combining the rasterized data with an appropriate portion of the reflection texture data.

116. The method according to claim 115, wherein the reflection texture data is stored as planar texture data representing a surface of a box with planar walls around the point.

117. The method according to claim 107,

the scene data being organized at least in part in a multiresolution virtual uniform subdivision (MVUS) data structure;

said subscene data being derived using the MVUS data structure for rays proceeding from the point to the area light source.

118. A method for rendering an electronic image representing a view from a point of view of a virtual scene defined by scene data comprising a plurality of visual objects and at least one area light source, said method comprising:

identifying one of the visual objects, or a portion thereof, which is visible from the point of view, and

tracing a beam from the visual object or portion, said beams enclosing therein the light source;

deriving from said beam tracing illumination data defining the amount of light reaching the object or portion thereof; and

determining from the illumination data an amount of light from the area light source that is reflected from the visual object or portion thereof.

119. The method of claim 118, wherein

the scene data includes a second area light source, and the method further comprises tracing a beam enclosing the second light source and deriving illumination therefrom.

120. The method of claim 118, wherein the scene data is organized in an MVUS data structure and the visual object is identified by traversing the MVUS data structure.

121. The method of claim 118, wherein said beam tracing includes defining a frustrum that encloses the area light source.

122. The method of claim 121, wherein said frustrum has an angular rotational displacement incorporated therein prior to deriving the illumination data.

123. The method of claim 121, and further comprising creating mini-scene data defining visual objects in the frustrum.

124. The method of claim 123, wherein the deriving of illumination data is performed by pipeline graphics circuitry, and the mini-scene data is transmitted thereto.

125. The method of claim 118, wherein the deriving of the illumination data is performed by pipeline graphics circuitry.

126. The method of claim 125, wherein the illumination data represents a color value.

127. The method of claim 118, wherein the illumination data represents a color value.

128. The method of claim 118, wherein the step of determining of reflected light is performed as part of the derivation of illumination data.

129. The method of one of claims 118 to 128, wherein the determining of reflected light is performed using a reflectance function that varies dependent on an angle of incidence and an angle of viewing at the point of light being modeled.

130. The method of claim 129, wherein the reflectance function combines a reflectance texture map representing varying reflectance at the point based on said angles with the illumination data to produce the determination of the reflected light.

131. The method of claim 130, wherein the reflectance texture map is stored electronically in a form corresponding to a mapping of the varying reflectance of light on a surface of a box structure around the object or portion.

132. The method of one of claims 118 to 131, wherein the amount of reflected light from the light source is combined with a color value for other light reflected off the object.

133. The method of one of claims 118 to 132, wherein the electronic image is a pixel data image.

134. The method of one of claims 118 to 133, wherein an illumination texture is mapped onto the area light source.

153. An apparatus performing the method of one of claims 118 to 151, said apparatus including a digital computer.

154. The apparatus of claim 153, said apparatus further comprising pipeline graphics circuitry.

155. A computer-readable storage device storing thereon instructions causing a computer to perform the method of one of claims 118 to 151.

135. A method of rendering an electronic image representing a view from a point of view of a virtual scene defined by scene data comprising a plurality of visual objects, said method comprising:

identifying one of the visual objects or a portion thereof which is visible from the point of view;

deriving for the object an angle of viewing thereof;

deriving illumination data for light illuminating said object or portion, said illumination data including directional data indicating an angle of incidence of the light on the object and an intensity value;

combining the intensity value with a reflection coefficient derived from the angle of incidence and the angle of viewing of the visual object.

136. The method of claim 135, wherein the reflection coefficient is part of a texture map.

137. The method of claim 136, wherein the texture map is structured as a box surrounding a reflective portion of a visual object.

138. The method of claim 137 wherein each discrete point of the box represents the amount of light passing through said discrete point that would be reflected along a line of sight.

139. The method of one of claims 135 to 138, wherein the texture map is combined with the illumination data by graphics pipeline circuitry.

140. The method of one of claims 135 to 139, wherein the illumination data includes a raster pattern.

145. The method of claim 140, and said grid format comprising an MVUS data structure.

146. The method of claim 145, and said MVUS data structure including a subdivision of the virtual scene, said cell subdivision containing at least partially thereon a pointer to a second MVUS structure.

147. The method of claim 146, and

said second MVUS structure having a transformation function associated therewith based on a relative orientation of the second MVUS to the first MVUS.

148. The method of claim 146 or 147, wherein the second MVUS is in a library of objects for placement in virtual instances.

141. A method for rendering an electronic image representing a view of a virtual scene as viewed from a point of view, said method comprising:

providing scene data defining the virtual scene in a grid format for efficient tracing of the passage of light therethrough; and

tracing a path for light in said virtual scene using said scene data.

142. The method of claim 141, and said path of light that is traced being a beam.

143. The method of claim 141, and said beam being a generally pyramidal frustrum.

144. The method of claim 141, and said path being a ray.

149. The method of one of claims 141 to 146, said grid structure containing cells being subdivided into subcells in each of three dimensions by a subdivision number where the cell contains a number of visual objects that exceeds a first subdivision threshold value.

150. The method of one of claims 141 to 149, wherein the grid structure has cells which are subdivided into subcells in each of three dimensions in a number which is an integer power of the subdivision number where the cell contains a number of visual objects that exceeds a second multiple subdivision threshold value.

151. The method of one of claims 141 to 150, wherein cells of the grid structure are recorded in a hash table, said hash table containing said cells based on addresses calculated from grid coordinates of the cell or subcell and a level number representing the level of subdivision thereof.

152. The method of one of claims 141 to 151, wherein said tracing is performed using an algorithm as disclosed herein.

156. A method for storing in a computer-readable database scene data comprising electronic visual object data defining visual objects each having associated therewith electronic data identifying a location of the visual object in a virtual space, said method comprising:

a) determining from the electronic visual object data a number representing a count of the how many of the visual objects have locations within a cell in the virtual space;

b) comparing said number of visual objects with a predetermined threshold subdivision value and/or a predetermined threshold multiple subdivision value;

c) responsive to a determination that the number of visual objects in the cell exceeds the predetermined threshold subdivision value but not the predetermined threshold multiple subdivision value, performing a subdivision operation representing a partitioning of the cell in at least one dimension thereof into an integer subdivision number s of subcells that are equal in size to each other and together constitute the cell;

d) responsive to a determination that the number of visual objects in the cell exceeds the predetermined threshold multiple subdivision value, performing a multiple subdivision operation representing a partitioning of the cell in at least one dimension thereof into a number of sub-cells, which number is an integral power, sⁿ, of subdivision number s, said sub-cells being equal in size to each other and together constituting the cell;

e) responsive to a determination that the number of visual objects in the cell does not exceed the predetermined threshold subdivision value, storing data identifying the visual objects in the cell in the database so that the visual object data of said visual objects can be accessed by a computer based on coordinates identifying said cell; and

f) repeating steps (a) to (d) for each of the sub-cells created in steps (c) or

(d), wherein each sub-cell becomes the cell in step (a) for which the number of visual objects is counted.

157. A method according to claim 156, wherein the operations representing a partitioning of the cell are of partitioning the cell in at least two dimensions thereof into s or sⁿ sub-cells that are equal in size to each other and together constitute the cell.

158. A method according to claim 156, wherein the operations representing a partitioning of the cell are of partitioning the cell in three dimensions thereof into s³ or s³ⁿ sub-cells that are equal in size to each other and together constitute the cell.

159. A method according to claim 156, wherein the subdivision number is 2.

160. A method according to claim 157, wherein the subdivision number is 2.

161. A method according to claim 158, wherein the subdivision number is 2, and where the subdivision operation yields eight sub-cells constituting the cell, and wherein the multiple subdivision operation yields 2³ⁿ sub-cells of the cell.

162. A method according to claim 156, wherein said cell is identified by integer coordinates thereof, and each sub-cell thereof is identified by at least one coordinate derived by multiplying at least one of the coordinates of the cell by the subdivision number to obtain a product, and adding a non-negative integer number less than the subdivision number to the product as an indication of displacement from an edge of the cell.

163. A method according to claim 157, wherein said cell is identified by integer coordinates thereof, and each sub-cell thereof is identified by at least two coordinates derived by multiplying at least two of the coordinates of the cell by the subdivision number to obtain products, and adding a respective non-negative integer number less than the subdivision number to each product as an indication of displacement of the sub-cell from edges of the cell.

164. A method according to claim 158, wherein said cell is identified by three integer coordinates thereof, and each sub-cell thereof is identified by three coordinates derived by multiplying the coordinates of the cell by the subdivision number to obtain three products, and adding a respective non-negative integer number less than the subdivision number to each product as an indication of displacement of the sub-cell from edges of the cell.

165. A method according to claim 156, wherein the value of n in the multiple subdivision operation varies dependent on the number of visual objects in the cell.

166. A method according to claim 164, wherein the value of n in the multiple subdivision operation is calculated as directly proportional to the quantity:

log_q(N/T)

where N is the number of objects in the cell, T is the subdivision threshold value, and q=s³.

167. A method according to claim 162, 163 or 164, wherein the data identifying the visual objects is stored so as to be accessed by the coordinates of the cell and a level number representing the number of subdivisions by the subdivision number between the cell and the first cell to which step (a) was applied in the method.

168. A method according to claim 167, wherein the data identifying visual objects is stored in a hash table structure accessed based on the coordinates and level number of the cell.

169. A method according to claim 167, wherein the data identifying visual objects comprises a stored pointer data value that points to another location in electronic data storage at which the visual object data can be located.

170. A method according to claim 167, wherein the data identifying visual objects is accessed by a content access memory using a key based on the coordinates and level number of the cell.

171. A method according to claim 156, wherein the visual object data of said visual objects is stored in a scene graph stored in the data storage device, and the data identifying the visual objects is a stored pointer value identifying at least one location in the scene graph.

172. A method according to claim 156, wherein the visual object data of said visual objects is stored in RAM memory.

173. A method according to claim 156, wherein one of the visual objects stored is identified by a pointer to another database of visual objects prepared according to the present method couple with data identifying a transform matrix that spatially orients cells of the second database of visual objects relative to the coordinates of the cell.

174. A method according to claim 156, wherein, when the operation of multiple subdivision is performed, a record is stored that represents the integral power n of the multiple subdivision.

175. A computer system for storing in a computer-readable data storage device a database of scene data comprising electronic visual object data defining visual objects each having associated therewith electronic data identifying a location of the visual object in a virtual space, said system comprising:

means for determining from the electronic visual object data a number representing a count of the how many of the visual objects have locations within a cell in the virtual space;

means for comparing said number of visual objects with a predetermined threshold subdivision value and/or a predetermined threshold multiple subdivision value;

means for performing, responsive to a determination that the number of visual objects in the cell exceeds the predetermined threshold subdivision value but not the predetermined threshold multiple subdivision value, a subdivision operation representing a partitioning of the cell in at least one dimension thereof into an integer subdivision number s of sub-cells that are equal in size to each other and together constitute the cell;

means for performing, responsive to a determination that the number of visual objects in the cell exceeds the predetermined threshold multiple subdivision value, a multiple subdivision operation representing a partitioning of the cell in at least one dimension thereof into a number of sub-cells, which number is an integral power, sⁿ, of subdivision number s, said sub-cells being equal in size to each other and together constituting the cell;

means for storing data identifying the visual objects in the cell in the database so that the visual object data of said visual objects can be accessed by a computer based on coordinates identifying said cell, said means for storing storing said data responsive to a determination that the number of visual objects in the cell does not exceed the predetermined threshold subdivision value, and

means for providing to the means for determining, means for comparing, means for performing and means for storing each of the sub-cells created, said means for determining, means for comparing, means for performing and means for storing processing each sub-cell as the cell for which the number of visual objects is counted.

176. A system according to claim 175, wherein the operations representing a partitioning of the cell are of partitioning the cell in at least two dimensions thereof into s or sⁿ sub-cells that are equal in size to each other and together constitute the cell.

177. A system according to claim 175, wherein the operations representing a partitioning of the cell are of partitioning the cell in three dimensions thereof into s³ or s³ⁿ sub-cells that are equal in size to each other and together constitute the cell.

178. A system according to claim 175, wherein the subdivision number is 2.

179. A system according to claim 176, wherein the subdivision number is 2.

180. A system according to claim 177, wherein the subdivision number is 2, and where the subdivision operation yields eight sub-cells constituting the cell, and wherein the multiple subdivision operation yields 2 sub-cells of the cell.

181. A system according to claim 175, wherein said cell is identified by integer coordinates thereof, and each sub-cell thereof is identified by at least one coordinate derived by multiplying at least one of the coordinates of the cell by the subdivision number to obtain a product, and adding a non-negative integer number less than the subdivision number to the product as an indication of displacement from an edge of the cell.

182. A system according to claim 176, wherein said cell is identified by integer coordinates thereof, and each sub-cell thereof is identified by at least two coordinates derived by multiplying at least two of the coordinates of the cell by the subdivision number to obtain products, and adding a respective non-negative integer number less than the subdivision number to each product as an indication of displacement of the sub-cell from edges of the cell.

183. A system according to claim 177, wherein said cell is identified by three integer coordinates thereof, and each sub-cell thereof is identified by three coordinates derived by multiplying the coordinates of the cell by the subdivision number to obtain three products, and adding a respective non-negative integer number less than the subdivision number to each product as an indication of displacement of the sub-cell from edges of the cell.

184. A system according to claim 175, wherein the value of n in the multiple subdivision operation varies dependent on the number of visual objects in the cell.

185. A system according to claim 177, wherein the value of n in the multiple subdivision operation is calculated as directly proportional to the quantity:

log_q(N/T)

where N is the number of objects in the cell, T is the subdivision threshold value, and q=s³.

186. A system according to claim 181, 182 or 183, wherein the means for storing stores the data identifying the visual objects so as to be accessed based on the coordinates of the cell and a level number representing the number of subdivisions by the subdivision number between the cell and the first cell to which subdivision or multiple subdivision was applied by the system.

187. A system according to claim 186, wherein means for storing includes data storage comprising a hash table structure in which the data identifying visual objects is stored so as to be accessed based on the coordinates and level number of the cell.

188. A system according to claim 186, wherein the data identifying visual objects comprises a stored pointer data value that points to another location in electronic data storage at which the visual object data can be located.

189. A system according to claim 186, wherein the means for storing stores the data identifying visual objects so as to be accessed by a content access memory using a key based on the coordinates and level number of the cell.

190. A system according to claim 175, wherein the means for storing stores the visual object data of said visual objects in a scene graph stored in the data storage device, and the data identifying the visual objects is a stored pointer value identifying at least one location in the scene graph.

191. A system according to claim 175, wherein the means for storing includes RAM memory storing the visual object data of said visual objects.

192. A system according to claim 175, wherein one of the visual objects stored is identified by a pointer to another database of visual objects coupled with data identifying a transform matrix that spatially orients cells of the second database of visual objects relative to the coordinates of the cell.

193. A system according to claim 175, and further comprising means for storing for the multiply subdivided cell a record that represents the integral power n of the multiple subdivision when the operation of multiple subdivision is performed.

194. A memory for storing scene data for access by a computer program being executed on a computer system, said scene data comprising data defining a plurality of visual objects each having a respective virtual location in a scene space, said memory comprising:

a plurality of cell data entries stored in said memory, each of said cell data entries corresponding to respective cell of the scene space, said cell being defined by coordinates thereof and a subdivision level value;

the cell data entries being stored in said memory so that each cell data entry is accessed based on the coordinates and level value of the associated cell;

said cell data entries each comprising data identifying the visual object or objects having a virtual location within the cell;

said cells being configured such that no more than a threshold subdivision number of visual objects have locations in any cell.

195. A memory according to claim 194, wherein the cells are defined as volumes of the scene space defined by integer boundaries of a coordinate grid, or as subdivisions derived therefrom, said subdivisions being derived by portioning a larger cell in at least one spatial dimension thereof by a positive integer subdivision number s of equally spaced partitions.

196. A memory according to claim 195, wherein the subdivisions are derived by partitioning in at least two dimensions.

197. A memory according to claim 195, wherein the subdivisions are derived by partitioning in three dimensions.

198. A memory according to claim 195, wherein the subdivision number s is 2.

199. A memory according to claim 196, wherein the subdivision number s is 2.

200. A memory according to claim 197, wherein the subdivision number s is 2.

201. A memory according to claim 195, wherein cells that have therein a number of visual objects that exceeds a multiple subdivision threshold number of visual objects are multiply subdivided by partitioning the cell in at least one dimension thereof into a number of sub-cells equal in size to each other, said number being an integral power, sⁿ, of subdivision number s.

202. A memory according to claim 201, wherein the integer power n of multiple subdivision varies dependent upon the number of visual objects in the cell.

203. A memory according to claim 201, wherein the cell entry for a cell that is multiply subdivided includes data recording the value of the integer power n of multiple subdivision thereof.

204. A memory according to claim 194, wherein

the cells are defined as volumes of the scene space defined by integer boundaries of a coordinate grid, or as subdivisions derived therefrom such that:

cells that have therein a number of visual objects that exceeds a subdivision threshold number of visual objects, being subdivided by partitioning a larger cell in each of three spatial dimensions thereof by a positive integer subdivision number s, or an integral power (sⁿ) thereof, of equally spaced partitions so as to yield s³ or s³ⁿ subdivisions thereof, and

cells that have therein a number of visual objects that exceeds a multiple subdivision threshold number of visual objects are multiply subdivided by partitioning the cell in three spatial dimensions thereof into a number of subdivisions equal in size to each other, said number being an integral power of subdivision number s.

205. A memory according to claim 204, wherein the subdivision number s is 2.

206. A memory according to claim 204, wherein the coordinates of each cell are:

a) coordinates of the associated grid position thereof;

or

b) coordinates derived from the coordinates of a cell that was subdivided to yield the cell.

207. A memory according to claim 206, wherein the coordinates are derived by multiplying the coordinates of the subdivided cell by the number of cells that the subdivided cell was subdivided in each dimension.

208. A memory according to claim 195, wherein the level number of each cell represents the number of subdivisions into s partitions needed to reach the cell from the grid coordinate level, which is subdivision level zero.

209. A computer system having a memory according to one of claims 195 to 208, said computer system further comprising a tracing application program executable for identifying any of the visual objects of the scene data that lie in a defined region of scene space.

210. A computer system according to claim 209, wherein said defined region of scene space is a path therethough.

211. A computer system according to claim 209, wherein said defined region of scene space is a generally pyramidal beam extending therethough.

212. A computer system according to claim 209, wherein said defined region of scene space is a generally linear ray extending therethough.

213. A method of rendering an image from scene data, said method comprising:

providing to a computer system access to a memory according to one of claims 195 to 208; and

accessing said memory so as to identify any of the visual objects of the scene data that lie in a defined region of scene space.

214. A method according to claim 213, wherein said defined region of scene space is a path therethough.

215. A method according to claim 213, wherein said defined region of scene space is a generally pyramidal beam extending therethough.

216. A method according to claim 213, wherein said defined region of scene space is a generally linear ray extending therethough.