Methods and apparatuses for selecting levels of detail for objects having multi-resolution models in graphics displays

• US 6,400,372 B1
• Filed: 11/29/1999
• Issued: 06/04/2002
• Est. Priority Date: 11/29/1999
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Gossweiler, Richard Carl III, Huberman, Bernardo A.
• Primary Examiner(s): Vo, Cliff N.
• Application Number:
  US09/450,365
• Time in Patent Office: 918 Days
• Field of Search: 345/418, 345/419, 345/619, 345/620, 345/61, 345/622, 345/623, 345/624, 345/428
• US Class Current: 345/619
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

The level of detail selected for each object in a scene is determined based upon a variable normalized risk parameter which may be supplied by the application. A recursive composite parent object process is invoked upon the two children of the scene object in order to allocate graphics resources to objects A and B. Primary and secondary hit value means corresponding to objects A and B are computed. The hit value means are the average sum of hit values recorded for all the leaf objects contained by the objects over a predetermined number of frames. The statistical variances of the primary hit value and secondary hit value are also computed over the previous predetermined number of frames in order facilitates the mapping of the normalized risk parameter to a non-normalized risk parameter indicating the optimal risk for objects A and object B. A quadratic parametric variance equation is solved for the optimal fraction of the remaining graphics resources to be allocated to object A. The optimal fraction is multiplied by the available graphics resources, resulting in the resources allocated to object A; the remaining graphics resources are to object B. If either object A or B is a leaf object, the level of detail is selected for object A or B as the level of detail associated with object A or B requiring the greatest amount of graphics resources not exceeding the resources allocated to object A or B. If either object A or B is a composite parent object, the recursive parent object process is invoked on the two children of object A or B with the available graphics resources for the instantiation of the recursive parent object process set to the graphics resources allocated to object A or B. After levels of detail for all objects in the scene has been achieved, the method according to the present invention renders all leaf objects.

Claims

1. A method for displaying a leaf object and an other object in a scene, the method comprising the steps of:

determining a non-normalized risk parameter;

computing a primary hit value mean for the leaf object;

computing a secondary hit value mean for the other object;

computing a primary hit value variance for the first leaf object;

computing a secondary hit value variance for the other object;

determining an optimal fraction of available graphics resources to be allocated to the leaf object based upon the non-normalized risk parameter, the primary hit value mean, the secondary hit value mean, the primary hit value variance, and the secondary hit value variance; and

selecting a level of detail for the leaf object based upon the optimal fraction and the available graphics resources.

2. A method as in claim 1, wherein the step of determining the non-normalized risk parameter includes the steps of:

determining a normalized risk parameter;

computing a minimum risk from the primary hit value variance and secondary hit value variance;

computing a maximum risk from the primary hit value mean, the secondary hit value mean, the primary hit value variance, and the secondary hit value variance; and

computing the non-normalized risk parameter from the minimum risk, the maximum risk, and the normalized risk parameter.

3. A method as in claim 2, wherein the step of determining a normalized risk parameter includes the step of:

receiving the normalized risk parameter from an application.

4. A method as in claim 2, wherein the normalized risk parameter is greater than or equal to zero and less than or equal to one.

5. A method as in claim 1, wherein the step of determining the optimal fraction of available graphics resources to be allocated to the object includes the steps of:

solving a quadratic variance equation for the optimal fraction.

6. A method as in claim 5, wherein the step of solving a quadratic variance equation includes the steps of:

if the primary hit value mean is greater than or equal to the secondary hit value mean, selecting a greater solution of the quadratic variance equation as the optimal fraction; and

if the primary hit value mean is less than the secondary hit value mean, selecting a lesser solution of the quadratic variance equation as the optimal fraction.

7. A method as in claim 1, wherein the step of selecting the level of detail for the leaf object based upon the optimal fraction and the available graphics resources includes the steps of:

allocating the optimal fraction of the available graphics resources to the leaf object.

8. A method as in claim 7, wherein the step of selecting the level of detail for the leaf object further includes the steps of:

selecting the level of detail for the leaf object requiring a greatest amount of graphics resources not exceeding the optimal fraction of the available graphics resources.

9. A method as in claim 1, wherein the primary hit value mean, the secondary hit value mean, the primary hit value variance, and the secondary hit value variance are each computed from a histogram of object hit values over a predetermined number of previous frames.

10. A method as in claim 9,

wherein the histogram includes object hit values over the predetermined number of immediately previous frames;

and

wherein the object hit values for the leaf object in the histogram comprise one when the leaf object is in a central portion of the scene, and comprise zero when the leaf object is not in the central portion of the scene.

11. A method as in claim 10,

wherein the histogram includes object hit values over the predetermined number of immediately previous frames;

and

wherein the object hit values for the leaf object in the histogram comprise values which are functions of an importance weight associated with the leaf object.

12. A method as in claim 1,

wherein the other object is a composite parent object.

13. A method as in claim 1, further comprising, prior to the step of determining a non-normalized risk parameter, the step of:

wherein the other object is an other leaf object.

14. An apparatus for displaying an object in a scene, comprising:

a processor;

a display device coupled to the processor; and

a processor readable storage medium coupled to the processor containing processor readable program code for programming the apparatus to perform a method for displaying a leaf object and an other object in a scene, the method comprising the steps of;

determining a non-normalized risk parameter;

computing a primary hit value mean for the leaf object;

computing a secondary hit value mean for the other object;

computing a primary hit value variance for the first leaf object;

computing a secondary hit value variance for the other object;

determining an optimal fraction of available graphics resources to be allocated to the leaf object based upon the non-normalized risk parameter, the primary hit value mean, the secondary hit value mean, the primary hit value variance, and the secondary hit value variance; and

selecting a level of detail for the leaf object based upon the optimal fraction and the available graphics resources.

15. An apparatus as in claim 14, wherein the step of determining the non-normalized risk parameter includes the steps of:

determining a normalized risk parameter;

computing a minimum risk from the primary hit value variance and secondary hit value variance;

computing a maximum risk from the primary hit value mean, the secondary hit value mean, the primary hit value variance, and the secondary hit value variance; and

computing the non-normalized risk parameter from the minimum risk, the maximum risk, and the normalized risk parameter.

16. An apparatus as in claim 15, wherein the step of determining a normalized risk parameter includes the step of:

receiving the normalized risk parameter from an application.

17. An apparatus as in claim 15, wherein the normalized risk parameter is greater than or equal to zero and less than or equal to one.

18. An apparatus as in claim 14, wherein the step of determining the optimal fraction of available graphics resources to be allocated to the object includes the steps of:

solving a quadratic variance equation for the optimal fraction.

19. An apparatus as in claim 18, wherein the step of solving a quadratic variance equation includes the steps of:

if the primary hit value mean is greater than or equal to the secondary hit value mean, selecting a greater solution of the quadratic variance equation as the optimal fraction; and

if the primary hit value mean is less than the secondary hit value mean, selecting a lesser solution of the quadratic variance equation as the optimal fraction.

20. An apparatus as in claim 14, wherein the step of selecting the level of detail for the leaf object based upon the optimal fraction and the available graphics resources includes the steps of:

allocating the optimal fraction of the available graphics resources to the leaf object.

21. An apparatus as in claim 20, wherein the step of selecting the level of detail for the leaf object further includes the steps of:

selecting the level of detail for the leaf object requiring a greatest amount of graphics resources not exceeding the optimal fraction of the available graphics resources.

22. An apparatus as in claim 14, wherein the primary hit value mean, the secondary hit value mean, the primary hit value variance, and the secondary hit value variance are each computed from a histogram of object hit values over a predetermined number of previous frames.

23. An apparatus as in claim 22,

wherein the histogram includes object hit values over the predetermined number of immediately previous frames;

and

wherein the object hit values for the leaf object in the histogram comprise one when the leaf object is in a central portion of the scene, and comprise zero when the leaf object is not in the central portion of the scene.

24. An apparatus as in claim 23,

wherein the histogram includes object hit values over the predetermined number of immediately previous frames;

and

wherein the object hit values for the leaf object in the histogram comprise values which are functions of an importance weight associated with the leaf object.

25. An apparatus as in claim 14,

wherein the other object is a composite parent object.

26. An apparatus as in claim 14, further comprising, prior to the step of determining a non-normalized risk parameter, the step of:

wherein the other object is an other leaf object.