Methods and systems for fractional level of detail assignment

• US 8,674,990 B1
• Filed: 07/21/2009
• Issued: 03/18/2014
• Est. Priority Date: 07/21/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gontmakher, Alex, Rechenberg, Andrin von
• Primary Examiner(s): Wu, Xiao M.
• Assistant Examiner(s): Sonners, Scott E
• Application Number:
  US12/507,006
• Time in Patent Office: 1,701 Days
• Field of Search: 345/428
• US Class Current: 345/428
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2207/20182 Noise reduction or smoothing in the temporal domain; Spatio-temporal filtering
• CPC Class Codes: G06T 2210/36 Level of detail
• CPC Class Codes: G06T 5/70 Denoising; Smoothing

Abstract

Methods and systems for fractional level of detail assignment are described herein. A method embodiment for fractional level of detail (LOD) assignment includes obtaining a set of features and image data at a range of LOD values, assigning one or more fractional LOD values to the obtained features and providing the features and the image data at the fractional LOD values. The embodiment also includes hashing an identifier associated with each feature and computing a hash cutoff value by mapping the range of LOD levels onto a range of integers. A system embodiment includes a LOD assigner to assign fractional LOD values to features in image data and to provide the features and the image data at the fractional LOD values. The system embodiment further includes a retrieval engine to return features with a range of LOD values that include the fractional LOD values to the LOD assigner.

Claims

1. A computer implemented method for accommodating a fractional level of detail (LOD) image data request using image data indexed at integer LOD steps, comprising:

(a) receiving, from a client, a request for image data at a fractional LOD value, wherein the fractional LOD value is not an integer, and wherein the requested image data is indexed at integer LOD steps;

(b) obtaining a set of features associated with the requested image data at a range of LOD values between a first integer endpoint LOD value and a second integer endpoint LOD value, wherein the fractional LOD value is between the first endpoint LOD value and the second endpoint LOD value;

(c) assigning the fractional LOD value to the obtained features; and

(d) providing the features and the image data at the fractional LOD value to the client, wherein at least one of steps (a)-(d) is implemented on one or more processors.

2. The method of claim 1, wherein step (c) comprises:

hashing an identifier associated with each feature;

computing a hash cutoff value; and

comparing the hash cutoff value to the hashed identifier.

3. The method of claim 2, wherein the computing step comprises evaluating a mapping function to map the range of LOD values onto a range of integers.

4. The method of claim 2, wherein the hashing step comprises hashing one or more properties associated with each feature.

5. The method of claim 1, further comprising:

shifting the range of LOD values by a fractional LOD step for a specified change in feature density.

6. The method of claim 1, wherein step (c) comprises interpolating LOD values associated with the features.

7. The method of claim 1, further comprising determining the probability of a feature to be displayed at the fractional LOD value.

8. The method of claim 1, further comprising pre-computing the fractional LOD value.

9. The method of claim 1, wherein step (c) is based on an importance of the features in the image data.

10. The method of claim 9, further comprising ranking the features based on the importance.

11. A computer based system for providing image data at a fractional level of detail (LOD) using image data indexed at integer LOD steps, comprising:

one or more processors; and

an LOD assigner to assign fractional LOD values to features in image data and to provide the features and the image data at the fractional LOD values, wherein the fractional LOD values are not integers, wherein the image data is indexed at integer LOD steps, wherein the LOD assigner is implemented on the one or more processors.

12. The system of claim 11, further comprising:

a retrieval engine to return features with a range of LOD values that include the fractional LOD values to the LOD assigner.

13. The system of claim 11, wherein the LOD assigner further comprises:

a hashing engine to hash an identifier and one or more properties associated with each feature returned by the retrieval engine; and

an LOD mapper to compute a hash cutoff value by mapping the range of LOD values onto a range of integers.

14. The system of claim 13, wherein the identifier is an alpha-numeric feature identifier.

15. The system of claim 11, further comprising a browser that displays the features and the image data at the fractional LOD values.

16. A computer implemented method of controlling density of displayed items in image data, comprising:

(a) retrieving image data at a digital zoom level that is associated with a first LOD value, wherein the retrieved image data is indexed at integer LOD steps;

(b) assigning fractional LOD values to a plurality of features in the retrieved image data, wherein the fractional LOD values are not integers; and

(c) filtering the features using the fractional LOD values, wherein at least one of steps (a)-(c) is implemented on one or more processors.

17. A computer implemented method of smoothing transitions between image data, displayed at different level of detail (LOD) values, comprising:

computing fractional LOD values of a plurality of features in retrieved image data, wherein the retrieved image data is indexed at integer LOD steps, wherein the fractional LOD values are not integers; and

shifting LOD values of the features by a fractional LOD step for a specified change in feature density, wherein the fractional LOD step is not an integer, wherein the computing and the shifting steps are implemented on one or more processors.