System and method for storing and accessing data representative of an object in various level-of-detail

• US 6,002,406 A
• Filed: 11/13/1996
• Issued: 12/14/1999
• Est. Priority Date: 11/13/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Zhao, Ze Hong
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): Nguyen, Kimbinh T.
• Application Number:
  US08/749,287
• Time in Patent Office: 1,126 Days
• Field of Search: 345/423, 345/507, 345/419, 345/139, 345/428, 345/429, 345/430
• US Class Current: 345/581
• CPC Class Codes: G06T 1/60 Memory management

Abstract

A system and method for storing a data representative of an object in various LODs. Each LOD representation is divided into a plurality of LOD cells and stored in a secondary memory. A designer designates a set of LOD cells with each of the plurality of LOD cells. When the projection of an eye point falls within a subject LOD cell, the set of LOD cells designated with the subject LOD cell are retrieved into a system memory. Thus, by properly designating the set of LOD cells, the designer may ensure that the desired LOD cells are in the system memory when required for processing. As a result, the data in the LOD cells may be accessed at a relatively high rate from the system memory when processing the LOD data. As only the required cells are retrieved into the system memory, the amount of memory required for storing the LOD data is also minimized.

Claims

1. A method of displaying an object represented in a plurality of levels of detail (LODs), the method comprising the steps of:

storing in a secondary memory each LOD divided into a plurality of LOD cells, wherein each LOD cell represents a portion of the object;

pre-designating, for each LOD cell, a corresponding set of LOD cells to be loaded into system memory with the corresponding LOD cell, whereby the probability is increased that a desired portion of the object is available in system memory when required for processing;

after the pre-designating step, determining a point of interest on the object;

determining, for each LOD, an LOD cell including the point of interest;

retrieving from the secondary memory, for each LOD, the determined LOD cell and a corresponding set of pre-designated LOD cells;

storing in a system memory the retrieved LOD cells and corresponding sets of pre-designated LOD cells; and

generating display signals from LOD cells selected from the LOD cells and corresponding sets of pre-designated LOD cells stored in system memory.

2. The method of claim 1, wherein each LOD cell comprises a polygon.

3. The method of claim 1, wherein the step of storing further comprises the step of replacing LOD cells that are no longer required in system memory according to a predetermined LOD cell replacement scheme.

4. The method of claim 3, wherein the predetermined LOD cell replacement scheme comprises the steps of:

dividing the system memory into a plurality of memory cells, wherein all memory cells have an equal number of memory locations;

maintaining a paging list indicative of LOD cells required to be in the system memory according to the retrieving step;

maintaining a free list indicative of memory cells which store LOD cells not required to be in the system memory; and

replacing the LOD cells indicated in the free list with LOD cells required to be in system memory.

5. The method of claim 1, wherein the point of interest comprises the projection of an eye-point onto the object.

6. The method of claim 1, wherein the pre-designating step comprises the step of providing an offset list having elements, wherein each element of the offset list identifies one LOD cell of the corresponding set of LOD cells.

7. The method of claim 1, wherein the pre-designating step comprises the step of designating a single LOD cell.

8. The method of claim 1, further comprising the steps of:

associating a threshold function with each LOD;

evaluating the threshold function for each LOD; and

retrieving the plurality of LOD cells in an LOD only if the corresponding threshold function returns a first value.

9. The method of claim 8, wherein the threshold function comprises the distance of an eye-point to the object as a variable.

10. The method of claim 1, further comprising the step of enabling a user to divide each LOD into a plurality of LOD cells.

11. The method of claim 1, further comprising the step of enabling a user to pre-designate the corresponding set of LOD cells with each of the plurality of LOD cells.

12. A method of displaying an object represented in a plurality of levels of detail (LODs), the method comprising the steps of:

dividing each LOD into a plurality of LOD cells, wherein each LOD cell represents a portion of the object;

storing each LOD cell in a secondary memory as a unit which can be retrieved without retrieving any other LOD cell;

pre-designating, for each LOD cell, a corresponding set of LOD cells to be loaded into system memory with the corresponding LOD cell, whereby the probability is increased that a desired portion of the object is available in system memory when required for processing;

determining a plurality of desired LOD cells required for generating an image of the object, wherein the plurality of desired LOD cells are comprised in one or more of the LOD representations;

determining, for each LOD, an LOD cell including the point of interest, wherein each of the corresponding sets of LOD cells are comprised in the plurality of desired LOD cells;

retrieving into a system memory the determined plurality of desired LOD cells; and

generating display signals from the stored plurality of desired LOD cells.

13. A system for displaying an object represented in a plurality of levels of detail (LODs), the system comprising:

means for storing in a secondary memory each LOD divided into a plurality of LOD cells, wherein each LOD cell represents a portion of the object;

means for pre-designating, for each LOD cell, a corresponding set of LOD cells to be loaded into system memory with the corresponding LOD cell, whereby the probability is increased that a desired portion of the object is available in system memory when required for processing;

means for determining, after pre-designating the corresponding set of LOD cells, a point of interest on the object;

means for determining, for each LOD, an LOD cell including the point of interest;

means for retrieving from the secondary memory, for each LOD, the determined LOD cell and a corresponding set of pre-designated LOD cells;

means for storing in a system memory the retrieved LOD cells and corresponding sets of pre-designated LOD cells; and

means for generating display signals from LOD cells selected from the LOD cells and corresponding sets of pre-designated LOD cells stored in system memory.

14. The system of claim 13, wherein the means for storing comprises of means for replacing LOD cells that are no longer required in system memory according to a predetermined LOD cell replacement scheme.

15. The system of claim 14, wherein the means for replacing comprises:

means for dividing the system memory into a plurality of memory cells, wherein all memory cells have an equal number of memory locations;

means for maintaining a paging list indicative of LOD cells required to be in the system memory according to the means for retrieving;

means for maintaining a free list indicative of memory cells which store LOD cells not required to be in the system memory; and

means for replacing the LOD cells indicated in the free list with LOD cells required to be in system memory.

16. The system of claim 13, wherein the point of interest comprises the projection of an eye-point onto the object.

17. The system of claim 13, wherein the means for pre-designating comprises means for providing an offset list having elements, wherein each element of the offset list identifies one LOD cell of the corresponding set of LOD cells.

18. The system of claim 13, wherein the means for pre-designating designates a single LOD cell.

19. The system of claim 13, further comprising:

means for associating a threshold function with each LOD;

means for evaluating the threshold function for each LOD; and

means for retrieving the plurality of LOD cells in an LOD only if the corresponding threshold function returns a first value.

20. The system of claim 19, wherein the threshold function comprises the distance of an eye-point to the object as a variable.

21. A computer program product for use with a computer system comprising a host processor, a system memory, a secondary memory, a graphics controller, and a display unit, the computer system for displaying an object represented in a plurality of levels of detail (LODs), the computer program product comprising:

computer readable program code means for causing the computer system to store in secondary memory each LOD divided into a plurality of LOD cells, wherein each LOD cell represents a portion of the object;

computer readable program code means for causing the computer system to pre-designate, for each LOD cell, a corresponding set of LOD cells to be loaded into system memory with the corresponding LOD cell, whereby the probability is increased that a desired portion of the object is available in system memory when required for processing;

computer readable program code means for causing the computer system to determine a point of interest on the object after pre-designating, for each LOD cell, a corresponding set of LOD cells;

computer readable program code means for causing the computer system to determine for each LOD, an LOD cell including the point of interest,

computer readable program code means for causing the computer system to retrieve from the secondary memory, for each LOD, the determined LOD cell and a corresponding set of pre-designated LOD cells;

computer readable program code means for causing the computer system to store in system memory the retrieved LOD cells and corresponding sets of pre-designated LOD cells; and

computer readable program code means for causing the computer system to generate display signals from LOD cells selected from the stored LOD cells and corresponding sets of predetermined LOD cells stored in system memory.

22. The computer program product of claim 21, wherein the computer readable program code means for causing the computer system to store comprises computer readable program code means for causing the computer system to replace LOD cells that are no longer required in system memory according to a predetermined LOD cell replacement scheme.

23. The computer program product of claim 22, wherein the computer readable program code means for causing the computer system to replace comprises:

computer readable program code means for causing the computer system to divide the system memory into a plurality of memory cells wherein all memory cells have an equal number of memory locations;

computer readable program code means for causing the computer system to maintain a paging list indicative of LOD cells required to be in system memory after retrieval from the secondary memory, for each LOD, the determined LOD cell and a corresponding set of pre-designated LOD cells;

computer readable program code means for causing the computer system to maintain a free list indicative of memory cells which store LOD cells not required to be in the system memory; and

computer readable program code means for causing the computer system to replace the LOD cells indicated in the free list with LOD cells required to be in system memory.

24. The computer program product of claim 21, wherein the point of interest comprises the projection of an eye-point onto the object.

25. The computer program product of claim 21, wherein the computer readable program code means for causing the computer system to pre-designate a set of LOD cells comprises computer readable program code means for causing the computer system to provide an offset list having elements, wherein each element of the offset list identifies one LOD cell of the corresponding set of LOD cells.

26. The computer program product of claim 21, wherein the computer readable program code means for causing the computer system to pre-designate a set of LOD cells causes the computer system to designate a single LOD cell.

27. The computer program product of claim 21, further comprising:

computer readable program code means for causing the computer system to associate a threshold function with each LOD;

computer readable program code means for causing the computer system to evaluate the threshold function for each LOD; and

computer readable program code means for causing the computer system to retrieve the plurality of LOD cells in an LOD only if the corresponding threshold function returns a first value.

28. The computer program product of claim 27, wherein the threshold function comprises the distance of an eye-point to the object as a variable.

29. A method of displaying an object represented in a plurality of levels of detail (LODs), the method comprising the steps of:

storing in a secondary memory each LOD divided into a plurality of LOD cells, wherein each LOD cell represents a portion of the object;

pre-designating, for each LOD cell, a corresponding set of LOD cells to be loaded into system memory with the corresponding LOD cell, whereby the probability is increased that a desired portion of the object is available in system memory when required for processing;

after the pre-designating step, determining a point of interest on the object;

determining, for an LOD, an LOD cell including the point of interest;

retrieving from the secondary memory, for each LOD, the determined LOD cell and a corresponding set of pre-designated LOD cells;

storing in a system memory the retrieved LOD cells and corresponding sets of pre-designated LOD cells; and

generating display signals from LOD cells selected from the LOD cells and corresponding sets of pre-designated LOD cells stored in system memory.