Reducing occlusions in oblique views

• US 8,253,736 B2
• Filed: 01/29/2007
• Issued: 08/28/2012
• Est. Priority Date: 01/29/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Adabala, Neeharika, Toyama, Kentaro
• Primary Examiner(s): HAJNIK, DANIEL F
• Application Number:
  US11/668,382
• Publication Number:
  US 20080180439A1
• Time in Patent Office: 2,038 Days
• Field of Search: None
• US Class Current: 345/421
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

An occlusion reduction system is described. The occlusion reduction system can reduce occlusions when displaying multiple objects by computing an occlusion measure and applying one or more functional dynamics techniques to minimize the occlusion measure, such as by moving objects, making objects at least partially transparent, and altering the scale of objects. The occlusion reduction system can create a geometric model based on modeling information it receives, establish a viewpoint, identify a set of objects for analysis, and compute an occlusion measure for the identified set of objects.

Claims

1. A method performed by a computing system having a processor and memory for reducing occlusions when displaying multiple objects, comprising:

creating a geometric model based on modeling information, the created geometric model identifying at least two objects;

receiving a selection of a viewpoint, the viewpoint establishing a perspective from which the geometric model is to be displayed;

identifying from the created geometric model a set of objects for analysis;

analyzing by the processor the identified set of objects to compute an occlusion measure, the occlusion measure measuring an extent to which all of the objects of the set of objects are occluded, wherein the occlusion measure is computed at least in part by computing an occlusion value for each object in the identified set of objects, wherein the occlusion value for each identified object corresponds to the fraction of the object that is occluded by other objects in the set of objects;

in response to determining that the occlusion measure measuring an extent to which all of the objects of the set of objects are occluded exceeds a threshold occlusion value,

improving visibility of the occluded objects by applying a functional dynamics technique wherein the applied functional dynamics technique causes a portion of an occluded object to remain occluded; and

in response to determining that objects are occluded and that the occlusion measure measuring an extent to which all of the objects of the set of objects are occluded does not exceed the threshold occlusion value, not improving visibility of the occluded objects.

2. The method of claim 1 wherein the functional dynamics technique comprises moving an occluding object to improve the visibility of the occluded objects.

3. The method of claim 2 wherein the moving includes determining constraints specifying an extent to which the occluding object can be moved.

4. The method of claim 3 wherein the occluding object is a building and the extent is a road.

5. The method of claim 1 wherein the functional dynamics technique comprises making an occluding object at least partially transparent to improve the visibility of the occluded objects.

6. The method of claim 5 wherein when a first occluding object at least partially occludes a second occluding object and the first and second occluding objects at least partially occlude an occluded object, the occluded object is displayed as opaque and the first occluding object is displayed with greater transparency than the second occluding object.

7. The method of claim 1 wherein the functional dynamics technique comprises modifying a height of an occluding object to improve the visibility of the occluded objects.

8. The method of claim 1 wherein the functional dynamics technique comprises moving a first occluding object, making a second occluding object at least partially transparent, and modifying a height of a third occluding object.

9. The method of claim 8 wherein at least two of the first, second, or third occluding objects are the same occluding object.

19. The method of claim 1 wherein the threshold occlusion value is greater than zero percent.

20. The method of claim 1 wherein the threshold occlusion value is at least approximately fifty percent.

21. The method of claim 1 wherein the threshold occlusion value is greater than or equal to fifty percent.

22. The method of claim 1, further comprising:

repeatedly improving visibility of the occluded objects by applying a functional dynamics technique until the occlusion measure measuring an extent to which all of the objects of the set of objects are occluded is less than the threshold occlusion value.

24. The method of claim 3 wherein the constraints specify that the occluding object cannot be moved greater than a specified distance.

25. The method of claim 3 wherein the constraints specify that the occluding object cannot be moved across a street.

26. The method of claim 3 wherein the constraints specify that the occluding object cannot change its position relative to another object.

27. The method of claim 4 wherein the constraints specify that the building cannot change its position relative to the road.

28. The method of claim 3 wherein the constraints specify that if the occluding object is to one side of a first object, the occluding object cannot be moved to another side of the first object.

10. A system for reducing occlusions when displaying multiple objects, comprising:

a processor and memory;

a set of modeling information that describes a geometric model of a group of objects that can be displayed;

a transformation component that receives the set of modeling information and a selection of a viewpoint, the viewpoint establishing a perspective from which the geometric model is to be displayed, and transforms the modeling information into viewing information that identifies a subset of the group of objects that are to be displayed; and

a functional dynamics component that

computes an occlusion index that measures an extent to which all of the objects of the group of objects are occluded by occluding objects at least in part by,

for each object of the set of objects,

selecting the object, and

setting an occlusion value for the selected object, the occlusion value for the selected object corresponding to the fraction of the selected object that is occluded by objects of the set of objects other than the selected object, and

summing the occlusion values calculated for each of the objects,

determines whether the occlusion index that measures an extent to which all of the objects of the group of objects are occluded by occluding objects exceeds a threshold occlusion value, and

in response to determining that the occlusion index that measures an extent to which all of the objects of the group of objects are occluded by occluding objects exceeds the threshold occlusion value, improves visibility of the occluded objects by applying a functional dynamics technique wherein the applied functional dynamics technique causes a portion of an occluded object to remain occluded.

11. The system of claim 10 wherein the functional dynamics component can move an occluding object to improve visibility of an occluded object.

12. The system of claim 10 wherein the functional dynamics component can make an occluding object at least partially transparent to improve visibility of an occluded object wherein a level of transparency is based on a distance from the viewpoint to the occluding object.

13. The system of claim 10 wherein the functional dynamics component can scale an occluding object to improve visibility of an occluded object by performing a non-uniform scaling operation.

14. The system of claim 10 wherein the functional dynamics component computes the occlusion index by analyzing an extent to which each object that is to be displayed is occluded by other objects that are also to be displayed and applies the functional dynamics technique to minimize the computed occlusion index.

23. The system of claim 10, further comprising:

a component configured to determine a viewpoint with the lowest occlusion index at least in part by computing an occlusion index for each of a plurality of viewpoints wherein the viewpoint with the lowest occlusion index causes the fewest occlusions.

15. A computer-readable storage device storing computer-executable instructions that, when executed, cause a computing system to perform operations for reducing occlusions when displaying multiple objects, the operations comprising:

computing an occlusion measure for a set of objects the occlusion measure measuring an extent to which all of the objects of the set of objects are occluded; and

in response to determining that the occlusion measure measuring an extent to which all of the objects of the set of objects are occluded exceeds the threshold occlusion value,

improving visibility of the occluded objects by applying a functional dynamics technique wherein the applied functional dynamics technique causes a portion of an occluded object to remain occluded,

wherein the occlusion measure measuring an extent to which all of the objects of the set of objects are occluded is computed at least in part by;

for a first object in the set of objects, calculating a first occlusion value at least in part by,

determining the fraction of the potentially visible area of the first object that is blocked by a second object in the set of objects different from the first object, and

determining the fraction of the potentially visible area of the first object that is blocked by a third object in the set of objects different from the first and second objects;

for the second object, calculating a second occlusion value at least in part by,

determining the fraction of the potentially visible area of the second object that is blocked by the first object, and

determining the fraction of the potentially visible area of the second object that is blocked by the third object;

for the third object, calculating a third occlusion value at least in part by,

determining the fraction of the potentially visible area of the third object that is blocked by the first object, and

determining the fraction of the potentially visible area of the third object that is blocked by the second object;

adding together the first occlusion value, the second occlusion value, and the third occlusion value.

16. The computer-readable device of claim 15 wherein the functional dynamics technique comprises moving an object.

17. The computer-readable device of claim 15 wherein the functional dynamics technique comprises making an object at least partially transparent.

18. The computer-readable device of claim 15 wherein the functional dynamics technique comprises altering a size of an object.

29. The computer-readable storage device of claim 15 wherein the occlusion measure O measuring an extent to which all of the objects of the set of objects are occluded is computed according to the following formula:

O=Σ

_io_i,

where

O_i=Σ

<sub>j(j≠

i)</sub>BlkFrac_ij,

i and j correspond to objects in the set of objects, BlkFrac_ij is the fraction of the potentially visible area of object i that is blocked by object j, and the set of objects includes at least three objects.