MAPPING TRAVERSABLE SPACE IN A SCENE USING A THREE-DIMENSIONAL MESH
A parallel-reality game uses a virtual game board having tiles placed over an identified traversable space corresponding to flat regions of a scene. A game board generation module receives one or more images of the scene captured by a camera of a mobile device. The game board generation module obtains a topographical mesh of the scene based on the received one or more images. The game board generation module then identifies a traversable space within the scene based on the obtained topographical mesh. The game board generation module determines a location for each of a set of polygon tiles in the identified traversable space. The game board generation module also allows for queries to identify parts of the game board that meet one or more provided criterion.
1 . A computer-implemented method comprising: receiving one or more images of a scene from a camera of a mobile device; obtaining a topographical mesh of the scene based on the one or more images, the topographical mesh including a plurality of cells; identifying a traversable space within the scene from the topographical mesh; placing a plurality of polygon tiles in the identified traversable space; and identifying one or more sets of contiguous tiles from the plurality of polygon tiles, where each of the sets of contiguous tiles defines a surface that is traversable by an entity.
2 . The computer-implemented method of claim 1 , wherein the entity is a virtual character, and wherein the traversable space is identified based on a virtual character configuration comprising a metric associated with an ability of the virtual character to traverse non-contiguous surfaces.
3 . The computer-implemented method of claim 1 , further comprising: for each polygon tile of the plurality of polygon tiles: determining, using a semantic segmentation model, a semantic label for the polygon tile, the semantic segmentation model trained to identify one or more surface properties; associating the semantic label with the polygon tile, the semantic label indicating a surface property; and causing, a virtual object to be displayed in an augmented reality (AR) or virtual reality (VR) interface, the virtual object positioned according to the semantic label of the polygon tile.
4 . The computer-implemented method of claim 3 , wherein the one or more surface properties includes a reflectance, friction, or material composition.
5 . The computer-implemented method of claim 1 , wherein identifying the traversable space within the scene from the topographical mesh comprises: for each cell of the topographical mesh: determining an angle between the cell and a specified plane; andresponsive to the angle being less than a threshold angle, assigning the cell to the traversable space.
6 . The computer-implemented method of claim 5 , wherein the specified plane corresponds to a wall in the scene.
7 . The computer-implemented method of claim 1 , wherein identifying the traversable space within the scene from the topographical mesh comprises, for each cell of the topographical mesh: determining a distance between the cell and the specified plane; determining an angle between the cell and the specified plane; and responsive to the distance being less than a threshold distance and the angle being less than a threshold angle, assigning the cell to the traversable space.
8 . The computer-implemented method of claim 1 , further comprising: receiving a request to expand an amount of the one or more sets of contiguous tiles, the request identifying a region outside of the scene; receiving topology information for the region outside of the scene from a plurality of sources; determining a level of confidence of the received topology information from each source of the plurality of sources; and expanding the amount of the one or more sets of contiguous tiles based on a combination of the received topology information, wherein the topology information is combined based on the determined confidence level for each source of the plurality of sources.
9 . The computer-implemented method of claim 8 , wherein the request is a first request, and wherein the region is a first region, the computer-implemented method further comprising: receiving, from the mobile device, a second request identifying a second region for expanding the amount of one or more sets of contiguous tiles; and in response to determining that the second region has not yet been previously analyzed to determine corresponding topology information, transmitting, to the mobile device, one or more of 3 D map information or satellite image information about the second region.
10 . The computer-implemented method of claim 1 , further comprising: presenting a game interface to a user, the game interface overlaying a representation of the game board including the plurality of polygon tiles with a second set of images of the scene captured by the camera of the mobile device.
11 . One or more non-transitory computer-readable storage media storing instructions that, when executed, cause a computing system to perform operations comprising: receiving one or more images of a scene from a camera of a mobile device; obtaining a topographical mesh of the scene based on the one or more images, the topographical mesh including a plurality of cells; identifying a traversable space within the scene from the topographical mesh; placing a plurality of polygon tiles in the identified traversable space; and identifying one or more sets of contiguous tiles from the plurality of polygon tiles, where each of the sets of contiguous tiles defines a surface that is traversable by an entity.
12 . The one or more non-transitory computer-readable storage media of claim 11 , wherein the entity is a virtual character, and wherein the traversable space is identified based on a virtual character configuration comprising a metric associated with an ability of the virtual character to traverse non-contiguous surfaces.
13 . The one or more non-transitory computer-readable storage media of claim 11 , wherein the operations further comprise: for each polygon tile of the plurality of polygon tiles: determining, using a semantic segmentation model, a semantic label for the polygon tile, the semantic segmentation model trained to identify one or more surface properties; associating the semantic label with the polygon tile, the semantic label indicating a surface property; andcausing a virtual object to be displayed in an augmented reality (AR) or virtual reality (VR) interface, the virtual object positioned according to the semantic label of the polygon tile.
14 . The one or more non-transitory computer-readable storage media of claim 13 , wherein the one or more surface properties includes a reflectance, friction, or material composition.
15 . The one or more non-transitory computer-readable storage media of claim 11 , wherein identifying the traversable space within the scene from the topographical mesh comprises: for each cell of the topographical mesh: determining an angle between the cell and a specified plane; andresponsive to the angle being less than a threshold angle, assigning the cell to the traversable space.
16 . The one or more non-transitory computer-readable storage media of claim 15 , wherein the specified plane corresponds to a wall in the scene.
17 . The one or more non-transitory computer-readable storage media of claim 11 , wherein identifying the traversable space within the scene from the topographical mesh comprises, for each cell of the topographical mesh: determining a distance between the cell and the specified plane; determining an angle between the cell and the specified plane; and responsive to the distance being less than a threshold distance and the angle being less than a threshold angle, assigning the cell to the traversable space.
18 . The one or more non-transitory computer-readable storage media of claim 11 , wherein the operations further comprise: receiving a request to expand an amount of the one or more sets of contiguous tiles, the request identifying a region outside of the scene; receiving topology information for the region outside of the scene from a plurality of sources; determining a level of confidence of the received topology information from each source of the plurality of sources; and expanding the amount of the one or more sets of contiguous tiles based on a combination of the received topology information, wherein the topology information is combined based on the determined confidence level for each source of the plurality of sources.
19 . The one or more non-transitory computer-readable storage media of claim 18 , wherein the request is a first request, and wherein the region is a first region, the operations further comprising: receiving, from the mobile device, a second request identifying a second region for expanding the amount of one or more sets of contiguous tiles; and in response to determining that the second region has not yet been previously analyzed to determine corresponding topology information, transmitting, to the mobile device, one or more of 3 D map information or satellite image information about the second region.
20 . A system comprising: one or more processors; and one or more non-transitory computer-readable media storing instructions that, when executed, cause the one or more processors to perform operations comprising: receiving one or more images of a scene from a camera of a mobile device; obtaining a topographical mesh of the scene based on the one or more images, the topographical mesh including a plurality of cells; identifying a traversable space within the scene from the topographical mesh; placing a plurality of polygon tiles in the identified traversable space; and identifying one or more sets of contiguous tiles from the plurality of polygon tiles, where each of the sets of contiguous tiles defines a surface that is traversable by an entity.