Software Technology for “Navigation point selection to navigate through virtual environments”

Metaverse – Gunnar Hovden, David V. Buchhofer, JR., Matthew Bell, Matterport Inc

Abstract for “Navigation point selection to navigate through virtual environments”

“Techniques for automatically selecting navigation points to navigate through computer-generated virtual environments such as a VR environment are disclosed. An input set of connected navigation point in a virtual environment can be automatically pruned to a subset of them, according to one or several selection factors. At least one selection factor is whether the subset will remain?connected? After pruning a navigation points from an input set. Other than whether pruning a navigation point will allow other navigation points to remain connected to it, there are additional selection factors that can be used to determine pruning techniques. One additional factor in navigation point pruning is the extent to which coverage of an input list of navigation points could be decreased by removing any navigation point from that input set.

Background for “Navigation point selection to navigate through virtual environments”

There are systems that allow users to navigate in a computer-generated virtual environment. This includes, for instance, a Virtual Reality environment (VR). Users can select predefined navigation points that correspond to a set of viewing positions within the environment. After selecting a navigation point the user’s virtual location within the environment changes to that navigation point. This allows the user to view their environment from the viewing point that corresponds with the navigation point. The transition can be gradual, showing objects moving past the user as the user moves? The transition may be gradual (showing objects move past as the user?moves? through the environment), or immediate. There are many factors that can affect the way the user selects navigation points, such as the hardware used to display the virtual environment.

For example, navigation can be done by manipulating a cursor control device such as a trackpad or mouse and/or pressing keys on a keyboard when you view a virtual environment. On the other hand, while wearing a VR headset, navigation may involve directing gaze, head movement, or a hand controller in a particular direction and then performing a navigation-triggering action. The navigation-triggering action may be operation of a control on the headset, on a handheld device that is engaged in wired or wireless communication with the headset, via a hand gesture, or merely by maintaining the gaze on a ?navigation-point-marker? “For longer than a specified time.”

“Navigation-point-markers are visual indicators, displayed within a virtual environment, of navigation points. Navigation-point-markers may take a variety of forms. Navigation point-markers can appear in a variety of ways, including as spheres, circles, or other shapes floating in the virtual environment. Preferably, the navigation-point-markers are large enough to be detectable by a user that is navigating the virtual environment, but small enough so as not to obscure too much of the virtual environment or otherwise diminish the user’s interactive virtual experience.”

“Techniques have been created to create three-dimensional (3D) models. Models based on photos (and possibly 3D) taken from real-world environments. These techniques are discussed, for instance, in ”

The navigation points described above can be used to navigate the 3D models once they have been created. In these cases, the navigation points correspond to the location of the image-capture position that was used in real-world environments to get the photos images upon which the model is built. Some techniques allow the user to “look around” the images taken at the image-capture points. “In the virtual environment in all directions.”

For example, a VR user might be able to see the sink in the kitchen when her head is at a neutral angle, the stove when her head is turned to the right and the floor when her head tilts downward. The user can capture the image-capture position of the stove, floor, and kitchen sink in this example as part of a panorama photo image capture process.

Some image-capture positions could lead to unfavorable navigation points. Some of the image-capture locations may be close to large objects or walls. These positions are not recommended for people who want to navigate in a virtual environment.

Some image-capture positions are not suitable for navigation because they are close to large objects or walls. Image-capture locations that aren’t well-suited for navigation include those with low-quality images, image capture positions with photo images that don’t capture anything of interest, image-capture position whose image images are not particularly interesting, and image-capture places whose image images are almost identical to the nearby image-capture points.

Another problem with using every image capture position as a navigator point is that the more dense the image-capture locations, the more navigation-point markers there will be in the virtual environment. There is a greater chance that the virtual environment will be hampered by too many navigation-point markers. If there are fifty floating circles displayed in a bedroom as navigation-point markers, the user is likely to be confused or annoyed. Additionally, users may need to perform a lot of navigation operations in order to move between points within the virtual environment.

It is possible to manually select which image-capture position will be used for navigation in a virtual environment. This can improve the virtual navigation experience. When a large, real-world environment is being modeled, it may be necessary to use a lot of image-capture locations to capture the photos needed to build the model. The difficulty in manually choosing the best image-capture position to use as navigation points increases with increasing size and variety of the modelled environment.

“The approaches described herein are possible approaches, but not necessarily those that have been used before. It is not possible to assume that any of these approaches are prior art, except as otherwise stated.

“The following description provides a detailed explanation of the invention. However, it will become apparent that the present invention can be used without these details. Other instances of well-known devices and structures are shown in block diagrams to avoid obscure the invention.

“General Overview”

“Techniques for automatically selecting navigation points to navigate through computer-generated virtual environments such as a VR environment are described in this article. An input set of connected navigation points in a virtual environment can be automatically pruned to a subset of them, according to one or several selection factors. At least one selection factor is whether the subset will remain?connected? After pruning a navigation-point from the input set.”

“Connected Navigation points”

“According some embodiments, in order for a set navigation points to be?connected? There must be at least one navigation path connecting each pair of navigation points so that the navigation points can be reached. A set of navigation points is considered ‘disconnected .?.”.

“Relatedly two navigation points are connected and are?adjacent?” If there is at most unidirectional?line-of sight navigation? They can be separated. If a first navigation marker is visible in the virtual environment at the viewing location corresponding to the first point, then line-of sight navigation to a second point is possible. The user can navigate directly in the virtual environment (with the appropriate user input) from the first point to the second point.

“For example, let’s say you have a simple virtual environment that contains only three navigation points.

“Assume also that the navigation points in the kitchen are adjacent to those in the hallway and that the navigation points in the hallway are adjacent to those in the dining area. The obstruction, such as a wall, between the kitchen, dining room and hallway means that the navigation points in both the kitchen, and dining room are not connected. The obstruction would mean that the navigation point in hallway could be pruned. This would make the navigation points in kitchen and dining room not connect because they are not adjacent. Also, the user cannot navigate using line-of sight from one location to the next through a series navigation points. The techniques described herein automatically reduce the input set connected navigation points to a subset.

After a subset of connected navigation point inputs has been reduced to a subset, the virtual environment can then be presented to users with navigation-point markers for that subset. This makes the virtual environment appear less cluttered than if it had navigation-point markers for all input navigation points. These techniques aren’t limited to VR environments. However, they may prove to be more useful in environments where excessive visual clutter could cause disorientation or discomfort. Because there are fewer navigation points to render, computing resources (e.g. processor and storage resources), are also conserved.

“In addition to considering whether pruning a navigation spot will allow the rest of the navigation points to remain connected to it, the techniques described herein determine a navigation-point for pruning based upon one or more additional selection criteria. One embodiment of navigation point pruning also considers the extent to which a navigation point’s coverage would be decreased by removing it from an input set.

“For instance, if two navigation point partially overlap in coverage due to their proximity in the virtual environment then the one whose pruning would reduce total cover of the input list by the least amount of time may be removed from the input list. Coverage is a broad term that includes different types of coverage. This document explains more about the term?coverage’. It can include different types of coverage. However, coverage is the portion of the virtual environment that a user can view when they navigate the environment using a set number of navigation points. The techniques herein describe how a selected subset connected navigation points covers the virtual environment to a minimum extent so that the user can navigate the environment without difficulty.

Other selection factors are also possible. A virtual environment could be built from photo images of real-world environments. The input set of navigation points corresponds to the image-capture locations in the real world environment where the photos were taken. Another selection factor is that a navigation point within the input set may be selected for pruning based upon the quality of the photograph(s) taken at the image-capture location corresponding to the navigation points. If the quality of the photo(s) captured at the image-capture position corresponding to the navigation point is poor, then the navigation point can be removed from the input set. The remaining input navigation points will remain connected after the pruning.

“Navigable, but Disconnected Navigation Points”

“As we have already mentioned, in order for a set navigation points to be connected according some embodiments, the navigation path must exist between each pair of navigation point. A navigation point set that has a path between each pair of navigation points is called a “navigable” for ease of understanding. Set of navigation points. A navigable set of points may not be considered connected in certain embodiments if there is too much distance between two navigation points. If a navigation point is pruned that is not yet connected but makes the rest of the navigation points navigable, the candidate navigation point should not be removed from the input set.

A navigation path connecting two points can be deemed too long depending on a number of criteria. If there are more intermediate navigation points than a threshold, such as two or more intermediate navigation points, then a navigation path connecting two navigation points A/B may be considered too long. Another example is that a candidate navigation line may not be removed from the input set if the length of the shortest navig path between two navigation points within the remaining navigation points increases by at least a threshold amount. If, for example, candidate navigation point A results in the length of navigation path between two navigation points in the set increasing by at least 70%, or another acceptable threshold amount, it may not be removed from the input list. The distance between the navigation points may be used to measure length. You can also use a combination of criteria. If a candidate navigation point A would lead to either:

“The number of intermediate navigation points along the shortest route between navigation points A and B being at least two; or

“The length of the shortest route between navigation points A and C increasing by 70% or greater.”

“A set of navigation points may be navigable, but can still be considered disconnected. This allows you to avoid selecting a lesser useful set of navigation points.

“Terminology”

“Before we continue the discussion on embodiments of this invention, it might be helpful to define some terminology used here and in the attached claims.”

“The ?coverage? “The?coverage? refers to the entire virtual environment that a user can view when they navigate the environment using the set navigation points. What is a ‘virtual environment? A 3D model that has been reconstructed using data captured. The “coverage” refers to the amount of virtual environment that has been reconstructed from captured data. The?coverage? of a navigation point is the area of the virtual environment visible from that point. The “exclusive coverage” refers to the portion of the virtual environment visible from that navigation point. The?exclusive coverage? of a navigation point is the area of the virtual environment visible only from this navigation point. It does not include any other navigation points in the input set. A navigation point’s exclusive coverage is a measure of how much coverage would be decreased by trimming it from an input set.

“Being above a threshold” is the definition herein. A value of an item under comparision is one that is greater than a specific other value. It also means that the item under compare is one of a set number of items that has the highest value or that it is within a given percentage. “Below a threshold” is the definition herein. A value of an item under a comparison is less than a specific other amount. It also means that the item under comparison is one of a number of items with the lowest value or that it has a lower percentage. “Being within a threshold” is the term used herein. A value for an item in comparison is one that is equal to or greater than two other values. Relative terms such as “high” or “unimportant?” are used to describe the item under comparison. If not defined otherwise, relative terms, such as?high? or?unimportant? can be understood to mean assigning a value, and determining how it compares with a threshold. The phrase “provided at minimum a threshold amount coverage” could be an example. Coverage that is less than or equal to a threshold can be understood.

“Constructing 3D models of real-world environments”

The input set must be first obtained before a connected navigation point set can be pruned based upon one or more selection criteria. You can get the input set from many sources. A computer-generated 3D model (real-world environment) is one possible source. This model is built using a collection photo images. Each navigation point corresponds to an image capture position in the real world environment. A collection of photos can be used to create a 3D model.

“Another technique allows for three-dimensional capture data from different locations to be received, allowing for different perspectives on 3D scenes. The algorithm uses capture device data to identify potential alignments between 3D scenes using coordinate transformations. Potential alignments are evaluated on quality and then aligned if they have sufficient relative or absolute quality. It is possible to align all or most 3D scenes in a single coordinate frame. It is possible to present areas around holes or other areas. This allows the user to capture the required 3D scene, including areas within and outside of holes or other areas, using the 3D capture tool. The new 3D scene can be aligned with existing 3D scenes or 3D composite scenes. This technique is detailed in U.S. Patent Application Ser. No. No.

A 3D capture device can capture 3D images of real-world environments at different capture positions relative the a 3D coordinate system. As the 3D images are captured or as the 3D information is extracted, the 3D capture device sends them to a mobile phone. The 3D images or derived information are aligned iteratively by the mobile device. This is done based on the spatial distance information of the real world environment that was captured by the 3D capture devices. The 3D model can be rendered on the mobile device’s display screen. The U.S. patent application Ser. No. No. 13/776688, entitled “Capturing and aligning 3D scenes,”? The entire contents are hereby included by reference.”

Many times, panoramic photo images are used to create 3D models of real-world environment. Some metadata may be tied to particular sets of coordinates. Each photo image may include or be associated with spatial information. This includes the exact location of the photo, the focal direction, and the individual portions of the photo if it is panoramic. The metadata can also include depth information that indicates the distance between the captured objects and the point from which the image was taken.

“The techniques herein described for pruning connected navigation point obtained from 3D models real-world environments aren’t limited to any one technique for building those 3D models. As long as navigation points can still be determined based upon the models, they don’t limit themselves.”

“Furthermore, although a virtual environment can be built from photo-images taken at real-world locations, the invention does not require that the navigation points within the virtual environment correspond with real-world locations. The virtual environment could be created by a computer program or gaming environment. These virtual environments may not have navigation points that correspond to real-world photo capture locations.

“The Initial Input Set Of Navigation Points”

These techniques can be used to automatically prune one or more navigation point from an input list of navigation points. The techniques herein for automatically pruning navigation points are not meant to replace other methods for choosing navigation points for pruning. A user may manually prune a set (such as all the image-capture positions that a 3D model based on a real-world setting is built) to create a set manually-pruned set of navigation points. The manually-pruned set of navigation points can then be automatically pruned using the automated pruning techniques discussed herein. A computer user interface may allow the user to select the navigation points from the initial set of pruning points. This interface could also have controls that enable the user to invoke automatic pruning for navigation points that are still unpruned after manual pruning. Alternately, the interface could allow the user to invoke the automatic pruning of a set of connected navig points to obtain a smaller set of connected navig points that the user can manually adjust (e.g. “Manually prune or restore navigation points that have been automatically pruned.

“In some cases, the initial input set connected navigation points corresponds with all image-capture location in a real world environment upon which construction of a 3-D model of that real-world environmental is based. In some cases, the initial input set could correspond to only a subset all image-capture places. The initial input set could correspond to all image capture locations in a specific area of a real-world setting, such as a room or floor. Another example is that the initial input set could correspond to image capture locations chosen randomly or pseudorandomly among all image-capture sites. Cluster analysis can be used to identify clusters of photo-capture sites, which are located in close proximity to one another. The initial input set could then be used to identify all image-capture locations within a cluster.

“Navigation-Point Graph”

Once an input set of connected navigation point is obtained, it can be represented as a connected graph with nodes and edges. Every navigation point in an input set is represented as a node in a graph. A graph edge that connects two nodes to the graph is adjacency between the two navigation points.

Navigation points can be considered adjacent, if they are connected by unidirectional line of sight navigation. Line-of-sight navigation can exist between two navigation points. In some cases it may only exist in one direction. Line-of-sight navigation is preferred to exist in both directions between adjacent navig points. This allows the user the ability to navigate back from an initial navigation point to another navigation point that was previously used. For a variety reasons, line-of sight navigation may not be possible in all directions between adjacent navigation points.

One reason that line-of sight navigation might not be possible in one direction between two adjacent navigational points is because a photo of the location corresponding with one navigation point may have been taken such that it is not visible in the virtual environment from the viewing location corresponding the other navigational point. A hallway location may have been captured using a photo-capture location in a nearby kitchen, but the kitchen location may have not been captured due to a door that was closed between the hallways and the kitchen when the photos were taken. The closed door may make the kitchen inaccessible from the hallway, even though it is visible from the kitchen.

“Although the techniques described herein allow for line-of sight navigation to exist in one direction between two points of navigation, these points can still be considered adjacent. The set of navigation points that the points belong to may also be considered connected.”

“The navigation point graph can be stored in computer storage media and programmatically modified there as a data structure that is suitable for representing graphs. The graph data structure should contain data structure elements that represent nodes and data structure element which represent edges. Information identifying the navigation-point markers for which the nodes are corresponding may be included in the data structure elements. Information about the nodes may include information that identifies the navigation-point markers they correspond to and/or coordinates that identify the locations of those markers. The coordinates could identify the location in a 3D coordinate system of a 3D model that represents the spatial dimensions of the real world environment being modeled. Data structure elements for edges can be linked (e.g. by pointers, reference or identifiers) to the data structure elements at the nodes connecting them.

“As stated, a navigation feature is not removed from an input set if it will cause other navigation points to be disconnected. You can programmatically determine if pruning a navigation link from an input set that has connected navigation points will result in a connected set after pruning.

“For example, we can determine whether candidate navigation can or cannot be pruned based on (a), the data structure elements of the nodes and (b), the data structure elements of the edges. A candidate navigation point should not ever be removed from the graph if it would cause any remaining nodes to be disconnected. A candidate navigation point can be removed if the candidate navigation points (and their edges) are not removed from the graph.

“When a candidate navigation points should be removed, the graph’s data structure may be modified to indicate that the candidate navigation points has been removed from the input list. To indicate that the candidate point has been removed from the input set, one example is to modify the data structure elements of the node that represents the candidate navigation. A?pruned bit? is one way to indicate that the pruning has been done. A?pruned-bit? is an attribute that each graph node has. The data structure elements of the node can include a Boolean or pruned-bit value. This can be used to indicate that the candidate navigation point has not been added to the input set. Alternately, the data structure elements of the node can be deleted or removed from the data structures representing the graph to indicate the candidate navigation point was pruned.

“Navigation-Point Coverage”

“The coverage of a navigation point is the area of the virtual environment visible from the point. The coverage area a navigation point covers may be defined as the line-of sight visibility of the virtual environment at the viewing point corresponding to the point. The volume or geometric area within a 3D model of the virtual environment may be used to calculate the space. In one embodiment, a navigation point’s coverage is assumed to be uniform in its distribution across a space. However, an alternative embodiment considers that a navigation points coverage is not uniform in its distribution over a space with a high?density. The coverage decreases with distance from the center of the space. Instead of using a volume or geometric area to calculate the coverage, where uniform coverage is assumed, coverage may be calculated using a distribution that is not uniform over the space. The coverage area may be expressed in computer storage media as an approximate value, regardless of how it was calculated.

The coverage of a navigation spot may be determined based on the 2D Cartesian coordinate spaces or the 3D model that represents the real-world environment. The virtual environment may model the spatial dimensions of the real world environment. The virtual environment could cover a navigation point, which may correspond to real-world space at the location in the real environment that corresponds to the navigation point.

“Also as stated herein, a navig point can be selected as a candidate to be pruned based on how much coverage will be reduced using the input set. In other words, between two navigation points the one with the most coverage can be chosen for pruning. This reduces the visual clutter caused by navigation-point markers within the virtual environment and minimizes the loss of coverage due to the input set.

The type of virtual environment used to model the environment may affect the coverage that a navigation spot is considered to have. If the virtual environment is used to model the interior of a building, then a location might be considered to have a coverage area that covers the floor corresponding to the point. The floor covered could be defined as the radius of a circle with a center at the point of navigation and a radius that corresponds to the distance from the point of view in the virtual environment. For example, this radius could be two to four meters. The dimensions of an area or volume that a navig point covers may change depending on the specific implementation. This includes, but is not limited, to the type and environment of the virtual environment.

“The geometry of a navigation point’s coverage area can be more complicated than a circle. Any 2D geometry is possible, including an ellipse or an oval.

The coverage of a navigation point can be modelled as a volume rather than an area. A navigation point’s coverage may be spherical, hemispherical, or based on complex 3D geometries like an ellipsoid or a spheroid. Or even more complicated 3D shapes with intricate curved surfaces.

“Reduced coverage of navigation points near objects”

Two navigation points could have the same coverage if they didn’t account for objects in the virtual environment. According to one embodiment, such objects are taken into account when determining coverage. If such objects are considered, the coverage of a navigator point can be decreased because it intersects with the boundaries of objects within the virtual environment that the user cannot navigate. A navigation point located near a wall in a room may provide less coverage than one that is in its center. This could be because the distance between the user and the virtual environment corresponding with the navigation points near the wall can be more than the viewing position corresponding the navigation points in the middle of the room.

The coverage of the navigation points that is less than the boundaries of objects in the virtual environment can be used to calculate the reduction in coverage. For example, the boundary of an object can be determined using a 3D mesh from the 3D model. This mesh defines the 3D surface. If the coverage of a navig point is represented as a circle, where the circle corresponds with a location on, above, or parallel to the floor of a home, then the area of the circle that extends beyond 3D mesh for wall surface according to the 3D model may be used to calculate the reduction in coverage.

It is worth noting that a navigation spot that is located near an object that the user is unable to navigate is more likely to be chosen for pruning than one that isn’t. A selection factor that minimizes the loss of coverage when a navigation is removed from the input list states that a navigation spot that is close to an object may be more likely to get cut than one that isn’t. If the coverage of all navigation points in the input set is less than that of an object, then the pruning of the point near the object will result in a lower coverage. The user may find it desirable to remove a navigation point located near an object. This is because the user’s line of sight in the virtual environment is less clear from the point corresponding to that navigation. The user might consider a viewing position that is less convenient than the one that corresponds to a navigation point not as close to an object to be preferable.

“Example Process”

This article will describe an example of an automated process for selecting navigation points to navigate through virtual environments. This process can be executed by a computing device that includes one or several processors and storage media. The storage media stores one or many computer programs which are executable by the processors. The computing system can perform the process in many different contexts. The process could be used to render or prepare to render a 3D model representing a real-world environment. This can be done on a standard computer video display, or with a VR headset. Alternately, the process can be done on cloud servers before the 3D model can be downloaded over the Internet to render.

“FIG. “FIG. Three high-level operations are included in the process 100, which is labeled 102 and 104 in FIG. 1. Process 100 can be used to reduce an input set to connected navigation points to a smaller set that provides at least a threshold level of coverage and contains high-utility navigation points for navigation through the virtual environment. Operations 102,104, and 106 are generally used to select a threshold coverage set of navigation points. Then, utility scores are calculated for navigation points not included in this subset (the “pruning candidates”). ), and then pruning one or more pruning candidates based upon the utility scores. These operations will now be described in more detail.

“It is obvious from the description herein of process 100 that operations 102-104 and 106 are shown in FIG. 1, in a specific order. However, these operations don’t necessarily have to be performed in that order. Operations 102,104, and106 could all be repeated in an iterative manner. In this case, a set of pruned navig points that result from operation 106 in a current iteration can be input to operation 102.

“It is important to understand that process 100 is only one example of a process to prune navigation points. There are many other processes that fall within the scope the invention. A process could score navigation points and then prune the worst-scoring navigation points, while keeping a related set of navigation point that provide at least a threshold amount coverage in the virtual environment.

“Selecting the Threshold Coverage Subset.”

“At operation 101, a subset is selected from an input list of connected navigation points. The input set may contain all navigation points within the virtual environment or just a subset. The input set of connected navigation point may, for example, correspond to all locations of image capture in the real world environment. This is based on how the 3D model of this real-world environment was constructed.

“The operation 102 subset of navigation point is referred herein as a threshold coverage subset. number of navigation points. The threshold coverage subset must provide at least a threshold level of coverage in the virtual environment. It should also reduce the number of navigation points required to provide that threshold coverage.

If the input set contains a subset or all of the navigation points in the virtual environment then the threshold coverage subset can be manually selected (e.g. user input) or automatically selected. The threshold coverage subset could correspond to a specific portion of the real world environment, such as a floor or floors or a room or rooms in a building.

One way to automatically select the threshold coverage is to: (a) calculate the coverage of all combinations of navigation point in the initial input list, and (b) choose the combination that provides the minimum coverage with the least number of navigation points. This approach can be computationally inefficient, particularly if the input set has a large number navigation points. If there are more than n navigation points in an input set, there will be 2n?1 possible combinations for computing coverage. Because of the amount of time it takes to complete exponential complexity algorithms, they are often difficult to implement using existing computer technology. It would take six months to calculate the coverage for an input list with 54 navigation points, even if all possible combinations of one, more or all of the navigation points in a set of 30 navigation points could easily be calculated using existing computer technology. It is necessary to develop a more practical algorithm. Below is a description of an example algorithm to compute the threshold coverage subset using polynomial complexity. 2.”

“Scoring the Pruning Candidats”

“The ‘pruning candidates’ are the navigation points that were not included in the threshold coverage subset of operation 102 are referred herein. Each pruning candidate is evaluated for its navigation utility at operation 104. A pruning candidate’s navigation quality score is a measure of how useful the candidate is to the user in order to navigate through the virtual environment. The navigation quality score can be calculated based on many characteristics of the point. These characteristics could include the coverage provided by the navig point, the exclusivity of the coverage provided by navigation points, proximity of navigation points to obstructions (e.g. a wall) within the virtual environment, proximity of navigation points to other navigation points, and quality of photo images taken at the location of image capture corresponding to the navigation spot. Below are examples of techniques for computing navigation quality scores.

“Pruning Based On Utility Scores”

“At operation106, the pruning candidates are evaluated based on their navigation quality scores. One embodiment of the pruning process begins with the lowest scoring candidate, and then proceeds to the highest scoring candidate until all candidates are considered for pruning. One embodiment states that a pruning candidate would be pruned if the input list of navigation points continues to be connected even after the candidate has been pruned. If pruning a candidate results in the input set being disconnected, the candidate is not considered for pruning.

“Selecting Threshold Coverage Subset.”

“FIGS. “FIGS. The 200th step may be used in operation 102 of the 100 described above.

“Process 200 is more efficient than an algorithm with exponential computational complexity, such as one that exhausts all combinations of navigation points. Process 200 generally performs one to several iterations. Each iteration selects a greater number of randomly selected navigation points from the input set. This allows for a maximum number random selections per iteration. Iterations are used to identify the random selection that provides the greatest coverage. If the best coverage provides less than a threshold, then the navigation points that provide the greatest coverage are chosen as the threshold coverage subset.

“Turning right to FIG. 2A: At operation 202, at most two variables in computer storage media have initial values. These variables will be referred to as?max_selections’. Both variables can be named?max_selections? and?choose_count. Each could be called differently depending on the specific implementation.

“At operation 200, the max_selections variable sets the maximum number possible of random selections per iteration. The max_selections value may be adjusted to meet the specific implementation requirements. This includes, but is not limited to: the number and size of the input sets, the CPU speed of the computer, the number and number of selections that are required to ensure that the input set contains a sufficient number of combinations of navigation points. With existing computer processing power, the max_selections variable can be set to an integer value in millions. If the input set has 40 navigation points and choose_count 6 then there is 40 choose 6, or 3,838,380 combinations of navigation points. If max_selections is set to 3,,000,000, for example, at least that many combinations will be considered.

“Initially, operation 202 sets the choose_count to 1 before the first iteration. At operation 220, it is increased by 1 after the completion of an iteration, and before starting the next one. As long as no threshold coverage subset has been determined, however, it remains at 1.”

“At operation 204, a variable indicating the number of random selections made during the current iteration has been set to 0. The variable is called?num_selections? for simplicity, but it could be named any other way depending on the specific implementation. After each selection made during operation 216, the num_selections variable increases.

“At operation 206, it is decided whether or not the current iteration should be continued. If the current value for the num_selections variables is not less than the current value for the max_selections variables, it may be decided that the current iteration should stop. If all combinations of navigation points in the input set of size choose_count are selected during an iteration, it may be decided that the current iteration should stop. Iterations can be monitored for the list of any iterations in which iterations have used previously selected combinations. If all the possible combinations of iterations have been chosen, it can be stopped at operation 206. If it is necessary to continue the iteration because the current value for the num_selections variables is lower than the current values of the max_selections variables and all possible ordered combinations of navigation points in the input set with a set size equal or greater than the current value for the choose_count variable are not selected during the current iteration then operation 200 will be performed.

“At operation 208, a subset is randomly selected from an input set. The set size of the subset is equal to the value of the choose_count variables. If the input set contains 40 navigation points, and the current value for the choose_count variable equals 5, then five navigation points are selected randomly from the total 40 points. A pseudo-random number generator can be used to make the random selection. A true random number generator can also be used. If the subset was already randomly selected during the current cycle, the process can repeat operation 208 as many times as necessary to select a random subset. If the same ordered combination of navigation point combinations has been randomly selected in the current iteration, the process can repeat operation 208 as many times as necessary to randomly choose a new combination of navigation point combinations that have not been chosen during the current iteration.

“At operation 218, the total net coverage of all navigation points randomly chosen at operation 208 are computed. The total net coverage can be calculated as the sum of all the coverages of randomly selected navigation points, minus any reductions in coverage due to other navigation points in input set that overlap the union coverage, and minus any coverage reductions resulting from the union coverage extending beyond mesh boundaries in the 3D model representing navigation obstacles (e.g. walls) in virtual environment. Below is an example of how to calculate the total net coverage.

“If the total net cover computed at operation 212 provides the best (greatest), total net coverage across all iterations, then operation 214 saves the subset of randomly selected navigation points as the best (greatest). total net coverage across all iterations. If the total net coverage at operation 210 is the best (greatest), total net coverage, then the process 200 proceeds into operation 216, where the variable num_selections is increased by 1. The process 200 returns to operation 206 to determine whether the current iteration should be continued.

“If it is decided that the current iteration should cease, the process will move to operation 218 (FIG. 2B). Operation 218, determines whether the best (greatest total net coverage) determined so far across all iterations provides at least a threshold level of coverage. The best (greatest) total net coverage determined so far, across all iterations performed so far, is referred to herein as the ?current-best-coverage?.”

“There are various ways to determine whether the current-best-coverage provides at least the threshold amount of coverage. In one possible way, the current-best-coverage provides at least the threshold amount of coverage at operation 218 if the difference between the total net coverage of all navigation points in the input set and the current-best-coverage is below a threshold. In another way, the current-best-coverage provides at least the threshold amount of coverage at operation 218 if the difference between (a) the best (greatest) total net coverage among all selections made during the just completed iteration where the choose_count equals n and (b) the best (greatest) total net coverage among all selections made during the iteration prior to that iteration where the choose_count equals n?1 is below a threshold. An example of determining the current-best-coverage, across all iterations performed so far, is provided below.”

“If it is determined at operation 218 that the current-best-coverage does not provide at least the threshold amount of coverage, then the choose_count variable is incremented by 1 at operation 220 and the process returns to operation 204 to perform another iteration, this time with a greater choose_count.”

“On the other hand, if it is determined at operation 218 that the current-best-coverage provides at least the threshold amount of coverage, then the subset of navigation points providing the current-best-coverage is selected as the threshold coverage subset.”

“As previously mentioned, process 200 can be used in operation 102 to select the threshold coverage section. Process 200 is not the only method to determine the threshold coverage subset. Other computationally feasible processes can be used in addition or alongside process 200. Coverage subsets can be determined using both process 200 or another polynomial-time process. The threshold coverage subset may be chosen from the two coverage subsets. The process 200 does not limit the selection of the threshold coverage. The remaining navigation points can be scored for navigation quality, regardless of how the threshold coverage is selected.

“Scoring Navigation points for Navigation Quality”

“As stated above, navigation points that aren’t included in the threshold coverage subset of the input set qualify as?pruning candidate. Opera 104 scores the pruning candidates for navigation quality. At operation 106, the scoring of the navigation points is done. The scored navigation points are then sorted from lowest to highest. As mentioned, a navigationpoint is not pruned if there are no connections between the input set and the navigation point.

“A navigation quality score for a point can be calculated based on a number of characteristics. These characteristics could include the coverage provided to the navigation points, the exclusive coverage of them, proximity to obstructions (e.g. a wall) within the virtual environment, proximity to other navigation points, quality of photo images taken at the location of image capture that corresponds to the navigation points.

“Generally speaking, the coverage provided to a navigation point is the most important aspect of navigation. After any coverage reductions due to mesh boundaries or overlap with other navigation points, the navigation utility will be greater and the navigation quality score will be higher. A user will consider a navigation spot that offers more line-of sight visibility of the virtual environment, from the viewing position that corresponds to the navigation point, to be more useful than one that has less. The higher score of a navigation point than another navigation point in an input set could indicate that it provides greater net coverage of the virtual environments than the other navigation points.

“Regarding the proximity of a navig point to an object (e.g. a wall), a user is more likely to consider a location closer to a boundary in the virtual environmental to have less utility than one that is further away. This is because the mesh boundary can obstruct or restrict line-of sight visibility in the environment from the viewing point corresponding to the navigation points that are closer to the boundary. One reason a navigation point with a higher navigation quality score may be that it is farther from a mesh border than another navigation point in an input set.

A user may consider a location closer to a navig point in the virtual environment as having less utility than one that is further away. This is because navigation points that are close to each other are more redundant than those that are farther apart. One reason a navigation point with a higher navigation quality score may be that it is farther from another navigation point in an input set.

“A navigation point that uses higher-quality photos is more likely to be viewed by a user than a point that uses lower-quality images. This is because the quality of the images taken at the image-capture site corresponding to a navigation points is less important. There are many ways to measure photo image quality. Photo image quality can be measured by resolution, blurriness, sharpness or any other quality metrics.

Summary for “Navigation point selection to navigate through virtual environments”

There are systems that allow users to navigate in a computer-generated virtual environment. This includes, for instance, a Virtual Reality environment (VR). Users can select predefined navigation points that correspond to a set of viewing positions within the environment. After selecting a navigation point the user’s virtual location within the environment changes to that navigation point. This allows the user to view their environment from the viewing point that corresponds with the navigation point. The transition can be gradual, showing objects moving past the user as the user moves? The transition may be gradual (showing objects move past as the user?moves? through the environment), or immediate. There are many factors that can affect the way the user selects navigation points, such as the hardware used to display the virtual environment.

For example, navigation can be done by manipulating a cursor control device such as a trackpad or mouse and/or pressing keys on a keyboard when you view a virtual environment. On the other hand, while wearing a VR headset, navigation may involve directing gaze, head movement, or a hand controller in a particular direction and then performing a navigation-triggering action. The navigation-triggering action may be operation of a control on the headset, on a handheld device that is engaged in wired or wireless communication with the headset, via a hand gesture, or merely by maintaining the gaze on a ?navigation-point-marker? “For longer than a specified time.”

“Navigation-point-markers are visual indicators, displayed within a virtual environment, of navigation points. Navigation-point-markers may take a variety of forms. Navigation point-markers can appear in a variety of ways, including as spheres, circles, or other shapes floating in the virtual environment. Preferably, the navigation-point-markers are large enough to be detectable by a user that is navigating the virtual environment, but small enough so as not to obscure too much of the virtual environment or otherwise diminish the user’s interactive virtual experience.”

“Techniques have been created to create three-dimensional (3D) models. Models based on photos (and possibly 3D) taken from real-world environments. These techniques are discussed, for instance, in ”

The navigation points described above can be used to navigate the 3D models once they have been created. In these cases, the navigation points correspond to the location of the image-capture position that was used in real-world environments to get the photos images upon which the model is built. Some techniques allow the user to “look around” the images taken at the image-capture points. “In the virtual environment in all directions.”

For example, a VR user might be able to see the sink in the kitchen when her head is at a neutral angle, the stove when her head is turned to the right and the floor when her head tilts downward. The user can capture the image-capture position of the stove, floor, and kitchen sink in this example as part of a panorama photo image capture process.

Some image-capture positions could lead to unfavorable navigation points. Some of the image-capture locations may be close to large objects or walls. These positions are not recommended for people who want to navigate in a virtual environment.

Some image-capture positions are not suitable for navigation because they are close to large objects or walls. Image-capture locations that aren’t well-suited for navigation include those with low-quality images, image capture positions with photo images that don’t capture anything of interest, image-capture position whose image images are not particularly interesting, and image-capture places whose image images are almost identical to the nearby image-capture points.

Another problem with using every image capture position as a navigator point is that the more dense the image-capture locations, the more navigation-point markers there will be in the virtual environment. There is a greater chance that the virtual environment will be hampered by too many navigation-point markers. If there are fifty floating circles displayed in a bedroom as navigation-point markers, the user is likely to be confused or annoyed. Additionally, users may need to perform a lot of navigation operations in order to move between points within the virtual environment.

It is possible to manually select which image-capture position will be used for navigation in a virtual environment. This can improve the virtual navigation experience. When a large, real-world environment is being modeled, it may be necessary to use a lot of image-capture locations to capture the photos needed to build the model. The difficulty in manually choosing the best image-capture position to use as navigation points increases with increasing size and variety of the modelled environment.

“The approaches described herein are possible approaches, but not necessarily those that have been used before. It is not possible to assume that any of these approaches are prior art, except as otherwise stated.

“The following description provides a detailed explanation of the invention. However, it will become apparent that the present invention can be used without these details. Other instances of well-known devices and structures are shown in block diagrams to avoid obscure the invention.

“General Overview”

“Techniques for automatically selecting navigation points to navigate through computer-generated virtual environments such as a VR environment are described in this article. An input set of connected navigation points in a virtual environment can be automatically pruned to a subset of them, according to one or several selection factors. At least one selection factor is whether the subset will remain?connected? After pruning a navigation-point from the input set.”

“Connected Navigation points”

“According some embodiments, in order for a set navigation points to be?connected? There must be at least one navigation path connecting each pair of navigation points so that the navigation points can be reached. A set of navigation points is considered ‘disconnected .?.”.

“Relatedly two navigation points are connected and are?adjacent?” If there is at most unidirectional?line-of sight navigation? They can be separated. If a first navigation marker is visible in the virtual environment at the viewing location corresponding to the first point, then line-of sight navigation to a second point is possible. The user can navigate directly in the virtual environment (with the appropriate user input) from the first point to the second point.

“For example, let’s say you have a simple virtual environment that contains only three navigation points.

“Assume also that the navigation points in the kitchen are adjacent to those in the hallway and that the navigation points in the hallway are adjacent to those in the dining area. The obstruction, such as a wall, between the kitchen, dining room and hallway means that the navigation points in both the kitchen, and dining room are not connected. The obstruction would mean that the navigation point in hallway could be pruned. This would make the navigation points in kitchen and dining room not connect because they are not adjacent. Also, the user cannot navigate using line-of sight from one location to the next through a series navigation points. The techniques described herein automatically reduce the input set connected navigation points to a subset.

After a subset of connected navigation point inputs has been reduced to a subset, the virtual environment can then be presented to users with navigation-point markers for that subset. This makes the virtual environment appear less cluttered than if it had navigation-point markers for all input navigation points. These techniques aren’t limited to VR environments. However, they may prove to be more useful in environments where excessive visual clutter could cause disorientation or discomfort. Because there are fewer navigation points to render, computing resources (e.g. processor and storage resources), are also conserved.

“In addition to considering whether pruning a navigation spot will allow the rest of the navigation points to remain connected to it, the techniques described herein determine a navigation-point for pruning based upon one or more additional selection criteria. One embodiment of navigation point pruning also considers the extent to which a navigation point’s coverage would be decreased by removing it from an input set.

“For instance, if two navigation point partially overlap in coverage due to their proximity in the virtual environment then the one whose pruning would reduce total cover of the input list by the least amount of time may be removed from the input list. Coverage is a broad term that includes different types of coverage. This document explains more about the term?coverage’. It can include different types of coverage. However, coverage is the portion of the virtual environment that a user can view when they navigate the environment using a set number of navigation points. The techniques herein describe how a selected subset connected navigation points covers the virtual environment to a minimum extent so that the user can navigate the environment without difficulty.

Other selection factors are also possible. A virtual environment could be built from photo images of real-world environments. The input set of navigation points corresponds to the image-capture locations in the real world environment where the photos were taken. Another selection factor is that a navigation point within the input set may be selected for pruning based upon the quality of the photograph(s) taken at the image-capture location corresponding to the navigation points. If the quality of the photo(s) captured at the image-capture position corresponding to the navigation point is poor, then the navigation point can be removed from the input set. The remaining input navigation points will remain connected after the pruning.

“Navigable, but Disconnected Navigation Points”

“As we have already mentioned, in order for a set navigation points to be connected according some embodiments, the navigation path must exist between each pair of navigation point. A navigation point set that has a path between each pair of navigation points is called a “navigable” for ease of understanding. Set of navigation points. A navigable set of points may not be considered connected in certain embodiments if there is too much distance between two navigation points. If a navigation point is pruned that is not yet connected but makes the rest of the navigation points navigable, the candidate navigation point should not be removed from the input set.

A navigation path connecting two points can be deemed too long depending on a number of criteria. If there are more intermediate navigation points than a threshold, such as two or more intermediate navigation points, then a navigation path connecting two navigation points A/B may be considered too long. Another example is that a candidate navigation line may not be removed from the input set if the length of the shortest navig path between two navigation points within the remaining navigation points increases by at least a threshold amount. If, for example, candidate navigation point A results in the length of navigation path between two navigation points in the set increasing by at least 70%, or another acceptable threshold amount, it may not be removed from the input list. The distance between the navigation points may be used to measure length. You can also use a combination of criteria. If a candidate navigation point A would lead to either:

“The number of intermediate navigation points along the shortest route between navigation points A and B being at least two; or

“The length of the shortest route between navigation points A and C increasing by 70% or greater.”

“A set of navigation points may be navigable, but can still be considered disconnected. This allows you to avoid selecting a lesser useful set of navigation points.

“Terminology”

“Before we continue the discussion on embodiments of this invention, it might be helpful to define some terminology used here and in the attached claims.”

“The ?coverage? “The?coverage? refers to the entire virtual environment that a user can view when they navigate the environment using the set navigation points. What is a ‘virtual environment? A 3D model that has been reconstructed using data captured. The “coverage” refers to the amount of virtual environment that has been reconstructed from captured data. The?coverage? of a navigation point is the area of the virtual environment visible from that point. The “exclusive coverage” refers to the portion of the virtual environment visible from that navigation point. The?exclusive coverage? of a navigation point is the area of the virtual environment visible only from this navigation point. It does not include any other navigation points in the input set. A navigation point’s exclusive coverage is a measure of how much coverage would be decreased by trimming it from an input set.

“Being above a threshold” is the definition herein. A value of an item under comparision is one that is greater than a specific other value. It also means that the item under compare is one of a set number of items that has the highest value or that it is within a given percentage. “Below a threshold” is the definition herein. A value of an item under a comparison is less than a specific other amount. It also means that the item under comparison is one of a number of items with the lowest value or that it has a lower percentage. “Being within a threshold” is the term used herein. A value for an item in comparison is one that is equal to or greater than two other values. Relative terms such as “high” or “unimportant?” are used to describe the item under comparison. If not defined otherwise, relative terms, such as?high? or?unimportant? can be understood to mean assigning a value, and determining how it compares with a threshold. The phrase “provided at minimum a threshold amount coverage” could be an example. Coverage that is less than or equal to a threshold can be understood.

“Constructing 3D models of real-world environments”

The input set must be first obtained before a connected navigation point set can be pruned based upon one or more selection criteria. You can get the input set from many sources. A computer-generated 3D model (real-world environment) is one possible source. This model is built using a collection photo images. Each navigation point corresponds to an image capture position in the real world environment. A collection of photos can be used to create a 3D model.

“Another technique allows for three-dimensional capture data from different locations to be received, allowing for different perspectives on 3D scenes. The algorithm uses capture device data to identify potential alignments between 3D scenes using coordinate transformations. Potential alignments are evaluated on quality and then aligned if they have sufficient relative or absolute quality. It is possible to align all or most 3D scenes in a single coordinate frame. It is possible to present areas around holes or other areas. This allows the user to capture the required 3D scene, including areas within and outside of holes or other areas, using the 3D capture tool. The new 3D scene can be aligned with existing 3D scenes or 3D composite scenes. This technique is detailed in U.S. Patent Application Ser. No. No.

A 3D capture device can capture 3D images of real-world environments at different capture positions relative the a 3D coordinate system. As the 3D images are captured or as the 3D information is extracted, the 3D capture device sends them to a mobile phone. The 3D images or derived information are aligned iteratively by the mobile device. This is done based on the spatial distance information of the real world environment that was captured by the 3D capture devices. The 3D model can be rendered on the mobile device’s display screen. The U.S. patent application Ser. No. No. 13/776688, entitled “Capturing and aligning 3D scenes,”? The entire contents are hereby included by reference.”

Many times, panoramic photo images are used to create 3D models of real-world environment. Some metadata may be tied to particular sets of coordinates. Each photo image may include or be associated with spatial information. This includes the exact location of the photo, the focal direction, and the individual portions of the photo if it is panoramic. The metadata can also include depth information that indicates the distance between the captured objects and the point from which the image was taken.

“The techniques herein described for pruning connected navigation point obtained from 3D models real-world environments aren’t limited to any one technique for building those 3D models. As long as navigation points can still be determined based upon the models, they don’t limit themselves.”

“Furthermore, although a virtual environment can be built from photo-images taken at real-world locations, the invention does not require that the navigation points within the virtual environment correspond with real-world locations. The virtual environment could be created by a computer program or gaming environment. These virtual environments may not have navigation points that correspond to real-world photo capture locations.

“The Initial Input Set Of Navigation Points”

These techniques can be used to automatically prune one or more navigation point from an input list of navigation points. The techniques herein for automatically pruning navigation points are not meant to replace other methods for choosing navigation points for pruning. A user may manually prune a set (such as all the image-capture positions that a 3D model based on a real-world setting is built) to create a set manually-pruned set of navigation points. The manually-pruned set of navigation points can then be automatically pruned using the automated pruning techniques discussed herein. A computer user interface may allow the user to select the navigation points from the initial set of pruning points. This interface could also have controls that enable the user to invoke automatic pruning for navigation points that are still unpruned after manual pruning. Alternately, the interface could allow the user to invoke the automatic pruning of a set of connected navig points to obtain a smaller set of connected navig points that the user can manually adjust (e.g. “Manually prune or restore navigation points that have been automatically pruned.

“In some cases, the initial input set connected navigation points corresponds with all image-capture location in a real world environment upon which construction of a 3-D model of that real-world environmental is based. In some cases, the initial input set could correspond to only a subset all image-capture places. The initial input set could correspond to all image capture locations in a specific area of a real-world setting, such as a room or floor. Another example is that the initial input set could correspond to image capture locations chosen randomly or pseudorandomly among all image-capture sites. Cluster analysis can be used to identify clusters of photo-capture sites, which are located in close proximity to one another. The initial input set could then be used to identify all image-capture locations within a cluster.

“Navigation-Point Graph”

Once an input set of connected navigation point is obtained, it can be represented as a connected graph with nodes and edges. Every navigation point in an input set is represented as a node in a graph. A graph edge that connects two nodes to the graph is adjacency between the two navigation points.

Navigation points can be considered adjacent, if they are connected by unidirectional line of sight navigation. Line-of-sight navigation can exist between two navigation points. In some cases it may only exist in one direction. Line-of-sight navigation is preferred to exist in both directions between adjacent navig points. This allows the user the ability to navigate back from an initial navigation point to another navigation point that was previously used. For a variety reasons, line-of sight navigation may not be possible in all directions between adjacent navigation points.

One reason that line-of sight navigation might not be possible in one direction between two adjacent navigational points is because a photo of the location corresponding with one navigation point may have been taken such that it is not visible in the virtual environment from the viewing location corresponding the other navigational point. A hallway location may have been captured using a photo-capture location in a nearby kitchen, but the kitchen location may have not been captured due to a door that was closed between the hallways and the kitchen when the photos were taken. The closed door may make the kitchen inaccessible from the hallway, even though it is visible from the kitchen.

“Although the techniques described herein allow for line-of sight navigation to exist in one direction between two points of navigation, these points can still be considered adjacent. The set of navigation points that the points belong to may also be considered connected.”

“The navigation point graph can be stored in computer storage media and programmatically modified there as a data structure that is suitable for representing graphs. The graph data structure should contain data structure elements that represent nodes and data structure element which represent edges. Information identifying the navigation-point markers for which the nodes are corresponding may be included in the data structure elements. Information about the nodes may include information that identifies the navigation-point markers they correspond to and/or coordinates that identify the locations of those markers. The coordinates could identify the location in a 3D coordinate system of a 3D model that represents the spatial dimensions of the real world environment being modeled. Data structure elements for edges can be linked (e.g. by pointers, reference or identifiers) to the data structure elements at the nodes connecting them.

“As stated, a navigation feature is not removed from an input set if it will cause other navigation points to be disconnected. You can programmatically determine if pruning a navigation link from an input set that has connected navigation points will result in a connected set after pruning.

“For example, we can determine whether candidate navigation can or cannot be pruned based on (a), the data structure elements of the nodes and (b), the data structure elements of the edges. A candidate navigation point should not ever be removed from the graph if it would cause any remaining nodes to be disconnected. A candidate navigation point can be removed if the candidate navigation points (and their edges) are not removed from the graph.

“When a candidate navigation points should be removed, the graph’s data structure may be modified to indicate that the candidate navigation points has been removed from the input list. To indicate that the candidate point has been removed from the input set, one example is to modify the data structure elements of the node that represents the candidate navigation. A?pruned bit? is one way to indicate that the pruning has been done. A?pruned-bit? is an attribute that each graph node has. The data structure elements of the node can include a Boolean or pruned-bit value. This can be used to indicate that the candidate navigation point has not been added to the input set. Alternately, the data structure elements of the node can be deleted or removed from the data structures representing the graph to indicate the candidate navigation point was pruned.

“Navigation-Point Coverage”

“The coverage of a navigation point is the area of the virtual environment visible from the point. The coverage area a navigation point covers may be defined as the line-of sight visibility of the virtual environment at the viewing point corresponding to the point. The volume or geometric area within a 3D model of the virtual environment may be used to calculate the space. In one embodiment, a navigation point’s coverage is assumed to be uniform in its distribution across a space. However, an alternative embodiment considers that a navigation points coverage is not uniform in its distribution over a space with a high?density. The coverage decreases with distance from the center of the space. Instead of using a volume or geometric area to calculate the coverage, where uniform coverage is assumed, coverage may be calculated using a distribution that is not uniform over the space. The coverage area may be expressed in computer storage media as an approximate value, regardless of how it was calculated.

The coverage of a navigation spot may be determined based on the 2D Cartesian coordinate spaces or the 3D model that represents the real-world environment. The virtual environment may model the spatial dimensions of the real world environment. The virtual environment could cover a navigation point, which may correspond to real-world space at the location in the real environment that corresponds to the navigation point.

“Also as stated herein, a navig point can be selected as a candidate to be pruned based on how much coverage will be reduced using the input set. In other words, between two navigation points the one with the most coverage can be chosen for pruning. This reduces the visual clutter caused by navigation-point markers within the virtual environment and minimizes the loss of coverage due to the input set.

The type of virtual environment used to model the environment may affect the coverage that a navigation spot is considered to have. If the virtual environment is used to model the interior of a building, then a location might be considered to have a coverage area that covers the floor corresponding to the point. The floor covered could be defined as the radius of a circle with a center at the point of navigation and a radius that corresponds to the distance from the point of view in the virtual environment. For example, this radius could be two to four meters. The dimensions of an area or volume that a navig point covers may change depending on the specific implementation. This includes, but is not limited, to the type and environment of the virtual environment.

“The geometry of a navigation point’s coverage area can be more complicated than a circle. Any 2D geometry is possible, including an ellipse or an oval.

The coverage of a navigation point can be modelled as a volume rather than an area. A navigation point’s coverage may be spherical, hemispherical, or based on complex 3D geometries like an ellipsoid or a spheroid. Or even more complicated 3D shapes with intricate curved surfaces.

“Reduced coverage of navigation points near objects”

Two navigation points could have the same coverage if they didn’t account for objects in the virtual environment. According to one embodiment, such objects are taken into account when determining coverage. If such objects are considered, the coverage of a navigator point can be decreased because it intersects with the boundaries of objects within the virtual environment that the user cannot navigate. A navigation point located near a wall in a room may provide less coverage than one that is in its center. This could be because the distance between the user and the virtual environment corresponding with the navigation points near the wall can be more than the viewing position corresponding the navigation points in the middle of the room.

The coverage of the navigation points that is less than the boundaries of objects in the virtual environment can be used to calculate the reduction in coverage. For example, the boundary of an object can be determined using a 3D mesh from the 3D model. This mesh defines the 3D surface. If the coverage of a navig point is represented as a circle, where the circle corresponds with a location on, above, or parallel to the floor of a home, then the area of the circle that extends beyond 3D mesh for wall surface according to the 3D model may be used to calculate the reduction in coverage.

It is worth noting that a navigation spot that is located near an object that the user is unable to navigate is more likely to be chosen for pruning than one that isn’t. A selection factor that minimizes the loss of coverage when a navigation is removed from the input list states that a navigation spot that is close to an object may be more likely to get cut than one that isn’t. If the coverage of all navigation points in the input set is less than that of an object, then the pruning of the point near the object will result in a lower coverage. The user may find it desirable to remove a navigation point located near an object. This is because the user’s line of sight in the virtual environment is less clear from the point corresponding to that navigation. The user might consider a viewing position that is less convenient than the one that corresponds to a navigation point not as close to an object to be preferable.

“Example Process”

This article will describe an example of an automated process for selecting navigation points to navigate through virtual environments. This process can be executed by a computing device that includes one or several processors and storage media. The storage media stores one or many computer programs which are executable by the processors. The computing system can perform the process in many different contexts. The process could be used to render or prepare to render a 3D model representing a real-world environment. This can be done on a standard computer video display, or with a VR headset. Alternately, the process can be done on cloud servers before the 3D model can be downloaded over the Internet to render.

“FIG. “FIG. Three high-level operations are included in the process 100, which is labeled 102 and 104 in FIG. 1. Process 100 can be used to reduce an input set to connected navigation points to a smaller set that provides at least a threshold level of coverage and contains high-utility navigation points for navigation through the virtual environment. Operations 102,104, and 106 are generally used to select a threshold coverage set of navigation points. Then, utility scores are calculated for navigation points not included in this subset (the “pruning candidates”). ), and then pruning one or more pruning candidates based upon the utility scores. These operations will now be described in more detail.

“It is obvious from the description herein of process 100 that operations 102-104 and 106 are shown in FIG. 1, in a specific order. However, these operations don’t necessarily have to be performed in that order. Operations 102,104, and106 could all be repeated in an iterative manner. In this case, a set of pruned navig points that result from operation 106 in a current iteration can be input to operation 102.

“It is important to understand that process 100 is only one example of a process to prune navigation points. There are many other processes that fall within the scope the invention. A process could score navigation points and then prune the worst-scoring navigation points, while keeping a related set of navigation point that provide at least a threshold amount coverage in the virtual environment.

“Selecting the Threshold Coverage Subset.”

“At operation 101, a subset is selected from an input list of connected navigation points. The input set may contain all navigation points within the virtual environment or just a subset. The input set of connected navigation point may, for example, correspond to all locations of image capture in the real world environment. This is based on how the 3D model of this real-world environment was constructed.

“The operation 102 subset of navigation point is referred herein as a threshold coverage subset. number of navigation points. The threshold coverage subset must provide at least a threshold level of coverage in the virtual environment. It should also reduce the number of navigation points required to provide that threshold coverage.

If the input set contains a subset or all of the navigation points in the virtual environment then the threshold coverage subset can be manually selected (e.g. user input) or automatically selected. The threshold coverage subset could correspond to a specific portion of the real world environment, such as a floor or floors or a room or rooms in a building.

One way to automatically select the threshold coverage is to: (a) calculate the coverage of all combinations of navigation point in the initial input list, and (b) choose the combination that provides the minimum coverage with the least number of navigation points. This approach can be computationally inefficient, particularly if the input set has a large number navigation points. If there are more than n navigation points in an input set, there will be 2n?1 possible combinations for computing coverage. Because of the amount of time it takes to complete exponential complexity algorithms, they are often difficult to implement using existing computer technology. It would take six months to calculate the coverage for an input list with 54 navigation points, even if all possible combinations of one, more or all of the navigation points in a set of 30 navigation points could easily be calculated using existing computer technology. It is necessary to develop a more practical algorithm. Below is a description of an example algorithm to compute the threshold coverage subset using polynomial complexity. 2.”

“Scoring the Pruning Candidats”

“The ‘pruning candidates’ are the navigation points that were not included in the threshold coverage subset of operation 102 are referred herein. Each pruning candidate is evaluated for its navigation utility at operation 104. A pruning candidate’s navigation quality score is a measure of how useful the candidate is to the user in order to navigate through the virtual environment. The navigation quality score can be calculated based on many characteristics of the point. These characteristics could include the coverage provided by the navig point, the exclusivity of the coverage provided by navigation points, proximity of navigation points to obstructions (e.g. a wall) within the virtual environment, proximity of navigation points to other navigation points, and quality of photo images taken at the location of image capture corresponding to the navigation spot. Below are examples of techniques for computing navigation quality scores.

“Pruning Based On Utility Scores”

“At operation106, the pruning candidates are evaluated based on their navigation quality scores. One embodiment of the pruning process begins with the lowest scoring candidate, and then proceeds to the highest scoring candidate until all candidates are considered for pruning. One embodiment states that a pruning candidate would be pruned if the input list of navigation points continues to be connected even after the candidate has been pruned. If pruning a candidate results in the input set being disconnected, the candidate is not considered for pruning.

“Selecting Threshold Coverage Subset.”

“FIGS. “FIGS. The 200th step may be used in operation 102 of the 100 described above.

“Process 200 is more efficient than an algorithm with exponential computational complexity, such as one that exhausts all combinations of navigation points. Process 200 generally performs one to several iterations. Each iteration selects a greater number of randomly selected navigation points from the input set. This allows for a maximum number random selections per iteration. Iterations are used to identify the random selection that provides the greatest coverage. If the best coverage provides less than a threshold, then the navigation points that provide the greatest coverage are chosen as the threshold coverage subset.

“Turning right to FIG. 2A: At operation 202, at most two variables in computer storage media have initial values. These variables will be referred to as?max_selections’. Both variables can be named?max_selections? and?choose_count. Each could be called differently depending on the specific implementation.

“At operation 200, the max_selections variable sets the maximum number possible of random selections per iteration. The max_selections value may be adjusted to meet the specific implementation requirements. This includes, but is not limited to: the number and size of the input sets, the CPU speed of the computer, the number and number of selections that are required to ensure that the input set contains a sufficient number of combinations of navigation points. With existing computer processing power, the max_selections variable can be set to an integer value in millions. If the input set has 40 navigation points and choose_count 6 then there is 40 choose 6, or 3,838,380 combinations of navigation points. If max_selections is set to 3,,000,000, for example, at least that many combinations will be considered.

“Initially, operation 202 sets the choose_count to 1 before the first iteration. At operation 220, it is increased by 1 after the completion of an iteration, and before starting the next one. As long as no threshold coverage subset has been determined, however, it remains at 1.”

“At operation 204, a variable indicating the number of random selections made during the current iteration has been set to 0. The variable is called?num_selections? for simplicity, but it could be named any other way depending on the specific implementation. After each selection made during operation 216, the num_selections variable increases.

“At operation 206, it is decided whether or not the current iteration should be continued. If the current value for the num_selections variables is not less than the current value for the max_selections variables, it may be decided that the current iteration should stop. If all combinations of navigation points in the input set of size choose_count are selected during an iteration, it may be decided that the current iteration should stop. Iterations can be monitored for the list of any iterations in which iterations have used previously selected combinations. If all the possible combinations of iterations have been chosen, it can be stopped at operation 206. If it is necessary to continue the iteration because the current value for the num_selections variables is lower than the current values of the max_selections variables and all possible ordered combinations of navigation points in the input set with a set size equal or greater than the current value for the choose_count variable are not selected during the current iteration then operation 200 will be performed.

“At operation 208, a subset is randomly selected from an input set. The set size of the subset is equal to the value of the choose_count variables. If the input set contains 40 navigation points, and the current value for the choose_count variable equals 5, then five navigation points are selected randomly from the total 40 points. A pseudo-random number generator can be used to make the random selection. A true random number generator can also be used. If the subset was already randomly selected during the current cycle, the process can repeat operation 208 as many times as necessary to select a random subset. If the same ordered combination of navigation point combinations has been randomly selected in the current iteration, the process can repeat operation 208 as many times as necessary to randomly choose a new combination of navigation point combinations that have not been chosen during the current iteration.

“At operation 218, the total net coverage of all navigation points randomly chosen at operation 208 are computed. The total net coverage can be calculated as the sum of all the coverages of randomly selected navigation points, minus any reductions in coverage due to other navigation points in input set that overlap the union coverage, and minus any coverage reductions resulting from the union coverage extending beyond mesh boundaries in the 3D model representing navigation obstacles (e.g. walls) in virtual environment. Below is an example of how to calculate the total net coverage.

“If the total net cover computed at operation 212 provides the best (greatest), total net coverage across all iterations, then operation 214 saves the subset of randomly selected navigation points as the best (greatest). total net coverage across all iterations. If the total net coverage at operation 210 is the best (greatest), total net coverage, then the process 200 proceeds into operation 216, where the variable num_selections is increased by 1. The process 200 returns to operation 206 to determine whether the current iteration should be continued.

“If it is decided that the current iteration should cease, the process will move to operation 218 (FIG. 2B). Operation 218, determines whether the best (greatest total net coverage) determined so far across all iterations provides at least a threshold level of coverage. The best (greatest) total net coverage determined so far, across all iterations performed so far, is referred to herein as the ?current-best-coverage?.”

“There are various ways to determine whether the current-best-coverage provides at least the threshold amount of coverage. In one possible way, the current-best-coverage provides at least the threshold amount of coverage at operation 218 if the difference between the total net coverage of all navigation points in the input set and the current-best-coverage is below a threshold. In another way, the current-best-coverage provides at least the threshold amount of coverage at operation 218 if the difference between (a) the best (greatest) total net coverage among all selections made during the just completed iteration where the choose_count equals n and (b) the best (greatest) total net coverage among all selections made during the iteration prior to that iteration where the choose_count equals n?1 is below a threshold. An example of determining the current-best-coverage, across all iterations performed so far, is provided below.”

“If it is determined at operation 218 that the current-best-coverage does not provide at least the threshold amount of coverage, then the choose_count variable is incremented by 1 at operation 220 and the process returns to operation 204 to perform another iteration, this time with a greater choose_count.”

“On the other hand, if it is determined at operation 218 that the current-best-coverage provides at least the threshold amount of coverage, then the subset of navigation points providing the current-best-coverage is selected as the threshold coverage subset.”

“As previously mentioned, process 200 can be used in operation 102 to select the threshold coverage section. Process 200 is not the only method to determine the threshold coverage subset. Other computationally feasible processes can be used in addition or alongside process 200. Coverage subsets can be determined using both process 200 or another polynomial-time process. The threshold coverage subset may be chosen from the two coverage subsets. The process 200 does not limit the selection of the threshold coverage. The remaining navigation points can be scored for navigation quality, regardless of how the threshold coverage is selected.

“Scoring Navigation points for Navigation Quality”

“As stated above, navigation points that aren’t included in the threshold coverage subset of the input set qualify as?pruning candidate. Opera 104 scores the pruning candidates for navigation quality. At operation 106, the scoring of the navigation points is done. The scored navigation points are then sorted from lowest to highest. As mentioned, a navigationpoint is not pruned if there are no connections between the input set and the navigation point.

“A navigation quality score for a point can be calculated based on a number of characteristics. These characteristics could include the coverage provided to the navigation points, the exclusive coverage of them, proximity to obstructions (e.g. a wall) within the virtual environment, proximity to other navigation points, quality of photo images taken at the location of image capture that corresponds to the navigation points.

“Generally speaking, the coverage provided to a navigation point is the most important aspect of navigation. After any coverage reductions due to mesh boundaries or overlap with other navigation points, the navigation utility will be greater and the navigation quality score will be higher. A user will consider a navigation spot that offers more line-of sight visibility of the virtual environment, from the viewing position that corresponds to the navigation point, to be more useful than one that has less. The higher score of a navigation point than another navigation point in an input set could indicate that it provides greater net coverage of the virtual environments than the other navigation points.

“Regarding the proximity of a navig point to an object (e.g. a wall), a user is more likely to consider a location closer to a boundary in the virtual environmental to have less utility than one that is further away. This is because the mesh boundary can obstruct or restrict line-of sight visibility in the environment from the viewing point corresponding to the navigation points that are closer to the boundary. One reason a navigation point with a higher navigation quality score may be that it is farther from a mesh border than another navigation point in an input set.

A user may consider a location closer to a navig point in the virtual environment as having less utility than one that is further away. This is because navigation points that are close to each other are more redundant than those that are farther apart. One reason a navigation point with a higher navigation quality score may be that it is farther from another navigation point in an input set.

“A navigation point that uses higher-quality photos is more likely to be viewed by a user than a point that uses lower-quality images. This is because the quality of the images taken at the image-capture site corresponding to a navigation points is less important. There are many ways to measure photo image quality. Photo image quality can be measured by resolution, blurriness, sharpness or any other quality metrics.

Click here to view the patent on Google Patents.