Method of determining occluded ingress and egress routes using nav-cell to nav-cell visibility pre-computation

• US 10,109,103 B2
• Filed: 03/20/2015
• Issued: 10/23/2018
• Est. Priority Date: 06/30/2010
• Status: Active Grant

• Current Assignee: Barry L. Jenkins
• Original Assignee: Barry L. Jenkins
• Inventors: Jenkins, Barry L.
• Primary Examiner(s): Cobb, Michael J
• Application Number:
  US14/664,499
• Publication Number:
  US 20150269770A1
• Time in Patent Office: 1,313 Days
• Field of Search: None
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

In an exemplary embodiment, a computer-implemented method determines, using a processor, a relatively occluded set of viewcells connecting a current viewcell and a destination viewcell, the current viewcell containing the position of a friendly asset and the destination viewcell containing the position of an enemy asset, the relatively occluded set of viewcells including a set of viewcells connecting the current viewcell and the destination viewcell and also having a maximal number of viewcells occluded from the destination viewcell; and instructs, using the processor, the friendly asset to navigate a path comprising the relatively occluded set of viewcells.

Claims

1. A computer-implemented method comprising steps of:

a) determining, using a processor, an occluded set of viewcells connecting a current viewcell and a destination viewcell, the current viewcell containing the position of a friendly asset and the destination viewcell containing the position of an enemy asset, the occluded set of viewcells comprising a set of viewcells connecting the current viewcell and the destination viewcell and also having a maximal number of viewcells occluded from the destination viewcell; and

b) instructing, using the processor, the friendly asset to navigate a path comprising the occluded set of viewcells,

wherein the viewcells have a plurality of viewcell vertices and comprise viewcell polygon meshes, wherein 3D graphical objects comprise object polygon meshes, and

wherein the viewcells occluded from the destination viewcell are determined by steps of;

a1) determining at least one first-order silhouette edge of the object polygon meshes, the at least one first-order silhouette edge being an edge of the object polygon meshes having;

first and second polygons sharing the at least one first-order silhouette edge,

the first polygon back-facing to each viewcell vertex from the plurality of viewcell vertices of the destination viewcell,

the second polygon front-facing to at least one viewcell vertex from the plurality of viewcell vertices of the destination viewcell, and

the first and second polygons having a back-facing orientation with respect to each other;

a2) determining at least one supporting polygon between the destination viewcell and the object polygon meshes, the at least one supporting polygon being determined between the destination viewcell and at least one vertex of the at least one first-order silhouette edge;

a3) constructing at least one wedge from the at least one supporting polygon, the at least one wedge extending away from the destination viewcell;

a4) determining one or more intersections of the at least one wedge with the polygons of the viewcell polygon meshes; and

a5) determining the set of the view cell polygon meshes occluded from the destination viewcell using the determined one or more intersections.

2. The computer-implemented method of claim 1, wherein the step of determining an occluded set of viewcells is pre-computed for at least one combination of current viewcell and destination viewcell.

3. The method of claim 2, further comprising the step of:

c) transmitting, using the processor, for at least one pair of connected viewcells of the occluded set of viewcells, the at least one pair of connected viewcells comprising a first viewcell and a second viewcell, a set of object polygons not occluded from the second viewcell and occluded from the first viewcell.

4. The method of claim 2, further comprising the step of:

d) 3D map-matching, using the processor, by matching a real-time 3D representation of the surrounding environment to a 3D model of the surrounding environment, the 3D model including the set of object polygons not occluded from the second viewcell and occluded from the first viewcell.

5. A computer-implemented method comprising steps of:

a) determining, using a processor, an acoustically shadowed set of viewcells connecting a current viewcell and a destination viewcell, the current viewcell containing the position of a friendly asset and the destination viewcell containing the position of an enemy asset, the acoustically shadowed set of viewcells comprising a set of viewcells connecting the current viewcell and the destination viewcell and also having a maximal number of viewcells acoustically shadowed from the destination viewcell, the determining comprising identifying said set of viewcells having a minimal propagation of acoustic energy from the current viewcell to the destination viewcell; and

b) instructing, using the processor, the friendly asset to navigate a path comprising the acoustically shadowed set of viewcells,

wherein the viewcells have a plurality of viewcell vertices and comprise viewcell polygon meshes, wherein 3D graphical objects comprise object polygon meshes, and

wherein the viewcells acoustically shadowed from the destination viewcell are determined by steps of;

a1) determining at least one first-order silhouette edge of the object polygon meshes, the at least one first-order silhouette edge being an edge of the object polygon meshes having;

first and second polygons sharing the at least one first-order silhouette edge,

the first polygon back-facing to each viewcell vertex from the plurality of viewcell vertices of the destination viewcell,

the second polygon front-facing to at least one viewcell vertex from the plurality of viewcell vertices of the destination viewcell, and

the first and second polygons having a back-facing orientation with respect to each other;

a2) determining at least one supporting polygon between the destination viewcell and the object polygon meshes, the at least one supporting polygon being determined between the destination viewcell and at least one vertex of the at least one first-order silhouette edge;

a3) constructing at least one wedge from the at least one supporting polygon, the at least one wedge extending away from the destination viewcell;

a4) determining one or more intersections of the at least one wedge with the polygons of the viewcell polygon meshes; and

a5) determining the set of the viewcell polygon meshes occluded from the destination viewcell using the determined one or more intersections.

6. The computer-implemented method of claim 5, wherein the step of determining an acoustically shadowed set of viewcells is pre-computed for at least one combination of current viewcell and destination viewcell.

7. The method of claim 6, further comprising the step of:

c) transmitting, using the processor, for at least one pair of connected viewcells of the acoustically shadowed set of viewcells, the at least one pair of connected viewcells comprising a first viewcell and a second viewcell, a set of object polygons not occluded from the second viewcell and occluded from the first viewcell.

8. The method of claim 6, further comprising the step of:

d) 3D map-matching, using the processor, by matching a real-time 3D representation of the surrounding environment to a 3D model of the surrounding environment, the 3D model including the set of object polygons not occluded from the second viewcell and occluded from the first viewcell.