Computerized image system

• US 7,034,825 B2
• Filed: 08/24/2001
• Issued: 04/25/2006
• Est. Priority Date: 08/24/2000
• Status: Expired due to Fees

• Current Assignee: Patent Holding Company
• Original Assignee: Patent Holding Company
• Inventors: Vandrovec, Bryan M., Clayton, Douglas B., Stowe, Jason A.
• Primary Examiner(s): Nguyen, Kimbinh T.
• Application Number:
  US10/362,389
• Publication Number:
  US 20040100465A1
• Time in Patent Office: 1,705 Days
• Field of Search: 345/419, 345/421, 345/423, 345/427, 345/426, 345/428, 345/440, 345/582
• US Class Current: 345/423
• 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 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 sub-cells 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) Of (d), wherein each sub-cell becomes the cell in step (a) for which the number of visual objects is counted.

2. A method according to claim 1, wherein the operations representing a partitioning of the cell arc 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.

3. A method according to claim 1, 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.

4. A method according to claim 1, wherein the subdivision number is 2.

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

6. A method according to claim 3, 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.

7. A method according to claim 1, 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.

8. A method according to claim 2, 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.

9. A method according to claim 3, 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.

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

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

log_q(N/F)

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

12. A method according to claim 7, 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.

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

14. A method according to claim 12, 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.

15. A method according to claim 12, 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.

16. A method according to claim 1, 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.

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

18. A method according to claim 1, 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.

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

20. 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.

21. A system according to claim 20, 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.

22. A system according to claim 20, 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.

23. A system according to claim 20, wherein the subdivision number is 2.

24. A system according to claim 21, wherein the subdivision number is 2.

25. A system according to claim 22, 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.

26. A system according to 20, 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.

27. A system according to 21, 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.

28. A system according to claim 22, 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.

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

30. A system according to claim 22, 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³.

31. A system according to claim 26, wherein the means for storing stores the data identifying the visual objects so as to he 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.

32. A system according to claim 31, 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.

33. A system according to claim 31, 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.

34. A system according to claim 31, 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.

35. A system according to claim 20, 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.

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

37. A system according to claim 20, 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.

38. A system according to claim 20, 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.

39. 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.

40. A memory according to claim 39, 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.

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

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

43. A memory according to claim 40, wherein the subdivision number s is 2.

44. A memory according to claim 41, wherein the subdivision number s is 2.

45. A memory according to claim 42, wherein the subdivision number s is 2.

46. A memory according to claim 40, 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.

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

48. A memory according to claim 46, 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.

49. A memory according to claim 39, 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.

50. A memory according to claim 49, wherein the subdivision number s is 2.

51. A memory according to claim 49, 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.

52. A memory according to claim 51, 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.

53. A memory according to claim 40, 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.

54. A computer system having a memory according to claim 40, 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.

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

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

57. A computer system according to claim 54, wherein said defined region of scene space is a generally linear ray extending therehough.

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

providing to a computer system access to a memory according o claim 40; 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.

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

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

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