Three-dimensional virtual tour method and system

• US 7,187,377 B1
• Filed: 06/28/2002
• Issued: 03/06/2007
• Est. Priority Date: 06/28/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kuriel, Yaacov Kory, Hale, Charles A., Pella, John P., Jensen, Scott A.
• Primary Examiner(s): Zimmerman; Mark
• Assistant Examiner(s): Santiago; Enrique L.
• Application Number:
  US10/187,044
• Time in Patent Office: 1,712 Days
• Field of Search: None
• US Class Current: 345/419
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

A method and system that archive a three-dimensional site in a highly-compact manner such that real-time, three-dimensional exploration and interaction with the site with high-resolution graphics is enabled. During authoring, information is collected about a site, and processed into a walkmap comprising a number of maps. A visibility map indicates which ones of the many polygons that make up a site are potentially visible from a given region. A collision map establishes where a can navigate in the site. A ground map tracks the terrain for reproducing camera heights and viewing angles, and a trigger map causes scripts to be fired from locations in the site. During navigation, only the maps relevant to a user'"'"'s current position are active, whereby rapid rendering of an appropriate image for the user'"'"'s current perspective is possible in real-time, providing a first person, perspective tour of the site in a perceived three-dimensional environment.

Claims

1. In a computing environment, a method comprising:

dividing a site comprised of polygons into a plurality of visibility regions, wherein each visibility region may include a plurality of viewing angles;

for each visibility region, determining which polygons of the site are potentially visible from within that visibility region;

constructing a visibility map in a computer readable storage medium for each visibility region, each map indicating the polygons of the site that are potentially visible from within that visibility region wherein constructing a visibility map for each visibility region comprises providing a bitmap having a plurality of bits, including at least one bit for each polygon in the site and corresponding to one of the polygons in the site, wherein the bits in the bitmap have a value indicative of whether their corresponding polygon is visible from within the visibility region; and

causing a change in a display based upon the visibility map.

2. The method of claim 1 wherein dividing a site into visibility regions includes dividing the site into a grid, each region corresponding to at least one grid.

3. The method of claim 1 wherein determining which polygons of the site are potentially visible from within that visibility region include collecting data from a plurality of positions in that visibility region.

4. The method of claim 1 wherein determining which polygons of the site are potentially visible from within that visibility region include collecting visibility data from a plurality of positions in that visibility region, and further comprising combining visibility data from the plurality of positions using a logical OR.

5. The method of claim 1 further comprising, determining a current visibility region in which a user is navigating, accessing the visibility map corresponding to the current visibility region to identify a set of the polygons that are potentially visible from the current visibility region, and causing display of at least some of the polygons in the set.

6. The method of claim 5 wherein causing display of at least some of the polygons in the set includes culling the set based on a perspective of the user in the current visibility region, and providing data corresponding to remaining polygons in the set to a graphics subsystem.

7. The method of claim 1 further comprising, constructing at least one ground map corresponding to the site, each ground map indicating camera heights and viewing angles for at least some positions in the site.

8. The method of claim 1 further comprising, constructing at least one trigger map corresponding to the site, each trigger map indicating actions to take with respect to at least some positions in the site.

9. The method of claim 1 further comprising, constructing at least one collision fence map corresponding to the site, each collision fence map preventing a user navigating in the site from moving to a position corresponding to the fence.

10. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

11. A system for presenting a virtual tour of a site comprised of visible polygons, comprising:

an archiving process that

     1) divides the site into a plurality of visibility regions that may each correspond to a plurality of viewing angles, and

     2) for each visibility region, determines which polygons of the site are potentially visible from within that visibility region;

a walkmap constructed via the archiving process, the walkmap including a visibility map corresponding to each visibility region, each visibility map indicating the polygons of the site that are potentially visible from the corresponding region, wherein each visibility map corresponds to a bitmap, each bitmap including, for each polygon of the site, at least one bit representing whether or not that polygon is potentially visible from the visibility region that corresponds to the visibility map;

a transfer medium for recording the walkmap in association with polygon data;

executable program code that receives commands from an input mechanism, the commands positioning a user camera in a position in a current visibility region of the site; and

a visible surface determination engine in communication with the executable program code to obtain the position, the visible surface determination engine configured to

     1) access a current visibility map corresponding to the current visibility region,

     2) determine which polygons identified via the current visibility map are visible from the position, and

     3) communicate corresponding polygon data to a graphics subsystem to render an image corresponding to the polygon data.

12. The system of claim 11 wherein the archiving process divides the site into a grid, and wherein each visibility region corresponding to at least one grid.

13. The system of claim 11 wherein each bitmap is compressed into the visibility map for storing onto the transfer medium.

14. The system of claim 13 wherein the current visibility map corresponding to the current visibility region is expanded into memory from its compressed state.

15. The system of claim 11 wherein the visible surface determination engine culls data corresponding to polygons of the current visibility map that are not visible from the position.

16. The system of claim 11 wherein the walkmap includes at least one ground map corresponding to the site, each ground map indicating camera heights and viewing angles for at least some positions in the site.

17. The system of claim 11 wherein the visible surface determination engine accesses a ground map corresponding to the position to determine which polygons identified via the current visibility map are visible from the position, based on a camera height and viewing angle.

18. The system of claim 11 wherein-the walkmap includes at least one trigger map corresponding to the site, each trigger map indicating actions to take with respect to at least some positions in the site.

19. The system of claim 11 wherein the visible surface determination engine accesses a trigger map corresponding to the position and takes an action in response thereto.

20. The system of claim 19 wherein the action comprises sending a message directed towards execution of a script.

21. The system of claim 11 wherein the walkmap includes at least one collision fence map corresponding to the site.

22. The system of claim 21 wherein the visible surface determination engine accesses a collision fence map corresponding to the position to determine whether executing a command to move to another position would cause a collision.

23. A computer-readable medium having stored thereon a data structure, comprising:

a plurality of polygons of a site, each polygon comprising polygon data that enables that polygon to be rendered on a display;

a plurality of visibility maps, each visibility map corresponding to a distinct region of the site, each visibility map including data indicative of whether each polygon of the site is potentially viewable from the region that corresponds to that visibility map, wherein each visibility map corresponds to a bitmap, each bitmap including, for each polygon of the site, at least one bit representing whether or not that polygon is potentially visible from the visibility region that corresponds to the visibility map; and

wherein for any position in the site, a corresponding one of the visibility maps is accessible to determine the polygons of the site that are potentially visible from that position.

24. The data structure of claim 23 further comprising at least one ground map corresponding to the site, each ground map indicating a camera height and viewing angle for a set of at least one of the polygons.

25. The data structure of claim 23 further comprising at least one trigger map corresponding to the site, each trigger map indicating at least one action to take with respect to a set of at least one of the polygons.

26. The data structure of claim 25 further comprising message data corresponding to each action.

27. The data structure of claim 23 further including a walkmap, the walkmap including a visibility map corresponding to each visibility region, each visibility map indicating the polygons of the site that are potentially visible from the corresponding visibility region wherein the walkmap includes at least one collision fence map, each collision fence map indicating invalid positions in the site.

28. A computer-implemented method, comprising:

receiving a request to navigate to a location in a site;

in response to the request, establishing a position and viewing perspective corresponding to the location;

accessing a visibility map based on the position, the visibility map indicating polygons of the site that are potentially visible from the viewing perspective, wherein each visibility map may include a plurality of viewing perspectives, wherein each visibility map corresponds to a bitmap, each bitmap including, for each polygon of the site, at least one bit representing whether or not that polygon is potentially visible from the visibility region that corresponds to the visibility map;

determining from the position and viewing perspective which of the polygons of the site that are potentially visible are within a viewing angle corresponding to the viewing perspective; and

providing data corresponding to the polygons that are within the viewing angle to the graphics subsystem.

29. The method of claim 28 wherein establishing a position and viewing perspective corresponding to the location comprises, accessing a collision map, determining whether the collision map indicates that the location requested is not allowed, and if allowed, selecting the position as the requested location, and if not allowed, selecting another position that is allowed based on the requested location and data in the collision map.

30. The method of claim 28 wherein establishing a position and viewing perspective corresponding to the location comprises, accessing a ground map to obtain height and viewing angle information corresponding to the position and viewing perspective.

31. The method of claim 28 further comprising, accessing a trigger map based on the position, determining whether the trigger map indicates an action is to be taken, and if so, taking the action.

32. The method of claim 31 wherein taking the action comprises accessing message data and sending a message including the message data to executable program code.

33. A computer-readable medium having computer-executable instructions for performing the method of claim 28.