System and method for increasing performance by efficient use of limited resources via incremental fetching, loading and unloading of data assets of three-dimensional worlds based on transient asset priorities

• US 5,956,039 A
• Filed: 07/25/1997
• Issued: 09/21/1999
• Est. Priority Date: 07/25/1997
• Status: Expired due to Term

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: PLATINUM Technology IP, Inc. (Broadcom, Inc.)
• Inventors: Shute, Glenn C., Woods, Daniel J., Marrin, Christopher F., Mott, David C.
• Primary Examiner(s): Zimmerman, Mark K.
• Assistant Examiner(s): GOOD JOHNSON, MOTILEWA
• Application Number:
  US08/900,471
• Time in Patent Office: 788 Days
• Field of Search: 345/419, 345/421
• US Class Current: 345/419
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/131 Protocols for games, networked simulations or virtual reality
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A system and method for increasing the performance associated with creating simulated 3D worlds from a network. The system and method provides a means for increasing the performance by fetching objects in the order of their importance. A priority scheme is used to determine the fetching, pre-fetching, and caching of URLs. The operations of assigning priorities, making prefetch requests and cache management is driven by data in an asset database table. The database contains information pertaining to each asset within the current scene such as the priority, status, region, type bounds, and retrieval time. The asset database table is updated based on fetching activities, camera position, and the positions of moving assets. A world scene is subdivided into appropriately sized regions when a scene is first downloaded. Asset type origins are defined and moved, based on the position, orientation, and velocity of the camera. Regions are assigned priorities based on their distance from the asset origin. Assets within particular regions are assigned priorities based on the region priorities and the asset type.

Claims

1. A process for increasing the performance associated with creating an interactive three dimensional (3D) world that is modeled using assets each having an asset type, said 3D world capable of being viewed on a computer display from the viewpoint of a virtual camera having a selectable velocity and position, said process comprising the steps of:

determining a world bounding box for the world;

creating a grid enclosing said world bounding box, said grid comprising a plurality of regions;

defining region priorities to said regions; and

assigning asset priorities for said assets based on the asset types and said region priorities.

2. The process of claim 1, further comprising the step of:

ordering said assets based on said asset priority.

3. The process of claim 2, further comprising the step of:

fetching said assets based on said ordering step.

4. The process of claim 1, further comprising the step of:

updating an asset database table with information related to said assets.

5. The process of claim 1, wherein said 3D world is modeled using Virtual Reality Modeling Language.

6. The process of claim 1, wherein said defining step comprises the steps of:

finding the position of the virtual camera; and

defining a region priority for each said region using predetermined criteria based on said position the virtual camera.

7. The process of claim 6, wherein said predetermined criteria is additionally based on the velocity of the virtual camera.

8. The process of claim 1, wherein said defining step comprises the steps of:

finding the position of the virtual camera; and

constructing an asset origin within said grid for each asset type, said asset origin being displaced a fixed distance from said position of the virtual camera; and

defining a region priority for each said region using predetermined criteria based on the distance of said region from said asset origin.

9. The process of claim 8, wherein said predetermined criteria is additionally based on the velocity of said asset origin.

10. The process of claim 8, further comprising the steps of:

assigning an offset value for each asset type; and

assigning an asset priority to each asset based on said region priority and said offset value.

11. The process of claim 3, wherein said ordering and fetching steps comprise the steps of:

constructing a fetch request queue comprising N elements;

loading said fetch request queue with N fetch requests for the first N assets having the highest said asset priority;

fetching said assets based on said fetch request queue;

loading said fetch request queue with another fetch request upon completion of a fetch request.

12. The process of claim 3, wherein said ordering and fetching steps comprise the steps of:

constructing an active queue comprising N elements;

constructing a waiting queue comprising M elements;

loading said active queue with N fetch requests for the first N assets having the highest said asset priority;

loading said waiting queue with M fetch requests for the next M assets having the highest said asset priority;

loading said active queue with a fetch request from said waiting queue when said fetch request from said active queue is complete; and

loading said waiting queue with a fetch request for the next asset having the highest said asset priority.

13. The process of claim 1, further comprising the step of:

performing cache management for said assets based on said asset priority.

14. The process of claim 13, wherein said performing step comprises the steps of:

defining N levels of cache storage;

determining whether to store or remove assets from a particular said level by comparing said asset priorities.

15. A computer program-product readable by a computer system, tangibly embodying a computer program-product comprising instructions executable by the computer system to perform method steps for increasing the performance associated with creating an interactive three dimensional (3D) world that is modeled using assets each having an asset type, said 3D world capable of being viewed on a computer display from the viewpoint of a virtual camera having a selectable velocity and position, said method steps comprising the steps of:

determining a world bounding box for the world;

creating a grid enclosing said world bounding box, said grid comprising a plurality of regions;

defining region priorities to said regions; and

assigning asset priorities for said assets based on the asset types and said region priorities.

16. The computer program-product of claim 15, further comprising the step of:

ordering said assets based on said asset priority.

17. The computer program-product of claim 16, further comprising the step of:

fetching said assets based on said ordering step.

18. The computer program-product of claim 15, further comprising the step of:

updating an asset database table with information related to each said asset.

19. The computer program-product of claim 15, wherein said 3D world is modeled using Virtual Reality Modeling Language.

20. The computer program-product of claim 15, wherein said defining step comprises the steps of:

finding the position of the virtual camera; and

defining a region priority for each said region using predetermined criteria based on the position the virtual camera.

21. The computer program-product of claim 20, wherein said predetermined criteria is additionally based on the velocity of the virtual camera.

22. The computer program-product of claim 15, wherein said defining step comprises the steps of:

finding the position of the virtual camera; and

constructing an asset origin within said grid for each asset type, said asset origin being displaced a fixed distance from the virtual camera; and

defining a region priority for each said region using predetermined criteria based on the distance of said region from said asset origin.

23. The computer program-product of claim 22, wherein said predetermined criteria is additionally based on the velocity of said asset origin.

24. The computer program-product of claim 22, further comprising the steps of:

assigning an offset value for each asset type; and

assigning an asset priority to each asset based on said region priority and said offset value.

25. The computer program-product of claim 17, wherein said ordering and fetching steps comprise the steps of:

constructing a fetch request queue comprising N elements;

loading said fetch request queue with N fetch requests for the first N assets having the highest said asset priority;

fetching said assets based on said fetch request queue;

loading said fetch request queue with another fetch request upon completion of a fetch request.

26. The computer program-product of claim 17, wherein said ordering and fetching steps comprise the steps of:

constructing an active queue comprising N elements;

constructing a waiting queue comprising M elements;

loading said active queue with N fetch requests for the first N assets having the highest said asset priority;

loading said waiting queue with M fetch requests for the next M assets having the highest said asset priority;

loading said active queue with a fetch request from said waiting queue when said fetch request from said active queue is complete; and

loading said waiting queue with a fetch request for the next asset having the highest said asset priority.

27. The computer program-product of claim 15, further comprising the step of:

performing cache management for said assets based on said asset priority.

28. The computer program-product of claim 27, wherein said performing step comprises the steps of:

defining N levels of cache storage;

determining whether to store or remove assets from a particular said level by comparing said asset priorities.

29. A system for increasing the performance associated with creating an interactive three dimensional (3D) world that is modeled using assets each having an asset types, said 3D world is viewed on a computer display from the viewpoint of a virtual camera, said system comprising:

means for determining the world bounding box of the world;

grid creating means for creating a grid that encloses said world bounding box, said grid comprising a plurality of regions;

region prioritizing means for assigning region priorities to said regions; and

asset prioritizing means for assigning asset priorities to each of said assets, based on the asset types and said region priorities.

30. The system according to claim 29, further comprising:

ordering means for ordering said assets based on said asset prioritizing means.

31. The system according to claim 29, further comprising:

asset table means for updating an asset database table with information related to said assets.

32. The system of claim 30, further comprising fetching means for fetching said assets based on said ordering means.

33. The system of claim 30, further comprising cache management means for performing cache management for assets based on said ordering means.