System and method of reducing transmission bandwidth required for visibility-event streaming of interactive and non-interactive content

• US 9,852,538 B2
• Filed: 06/29/2015
• Issued: 12/26/2017
• Est. Priority Date: 06/30/2010
• Status: Active Grant

• Current Assignee: Primal Space Systems Inc.
• Original Assignee: Primal Space Systems Inc.
• Inventors: Jenkins, Barry L.
• Primary Examiner(s): McCulley, Ryan D
• Application Number:
  US14/754,419
• Publication Number:
  US 20160005214A1
• Time in Patent Office: 911 Days
• Field of Search: None
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06T 15/20 Perspective computation
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 15/405 using Z-buffer
• CPC Class Codes: G06T 15/60 Shadow generation
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 19/003 Navigation within 3D models or images
• CPC Class Codes: G06T 2200/16 involving adaptation to the client's capabilities
• CPC Class Codes: G06T 2200/28 involving image processing hardware
• CPC Class Codes: G06T 2200/36 Review paper; Tutorial; Survey

Abstract

In an exemplary embodiment, a computer-implemented method determines a set of mesh polygons or fragments of the mesh polygons visible from a navigation cell. The method includes determining a composite view frustum containing predetermined view frusta and determining mesh polygons contained in the composite view frustum. The method includes determining at least one supporting polygon between the navigation cell and the contained mesh polygons. The method further includes constructing at least one wedge from the at least one supporting polygon, the at least one wedge extending away from the navigation cell beyond at least the contained mesh polygons. The method includes determining one or more intersections of the at least one wedge with the contained mesh polygons. The method also includes determining the set of the contained mesh polygons or fragments of the contained mesh polygons visible from the navigation cell using the determined one or more intersections.

Claims

1. A computer-implemented method of determining a set of mesh polygons or fragments of said mesh polygons visible from a navigation cell, said mesh polygons forming polygon meshes, the method comprising steps of:

a) determining a composite view frustum containing predetermined view frusta in said navigation cell;

b) determining mesh polygons contained in said composite view frustum;

c) determining at least one supporting polygon between said navigation cell and said contained mesh polygons;

d) constructing at least one wedge from said at least one supporting polygon, said at least one wedge extending away from said navigation cell beyond at least said contained mesh polygons;

e) determining one or more intersections of said at least one wedge with said contained mesh polygons;

f) determining said set of said contained mesh polygons or fragments of said contained mesh polygons visible from said navigation cell using said determined one or more intersections of said at least one wedge with said polygon meshes; and

g) determining at least one first-order silhouette edge of said contained mesh polygons,

wherein said at least one supporting polygon is determined between said navigation cell and at least one vertex of said at least one first-order silhouette edge,

wherein the navigation cell includes a plurality of navigation cell vertices,

wherein said at least one first-order silhouette edge includes;

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

the first polygon backfacing to each navigation cell vertex from the plurality of navigation cell vertices,

the second polygon front-facing to at least e navigation cell vertex from the plurality of navigation cell vertices, and

the first and second polygons having a backfacing orientation with respect to each other, and

wherein upon determination that said at least one first-order silhouette edge and another first-order silhouette edge share a vertex forming an inside corner vertex of said polygon mesh, the at least one supporting polygon is formed by said inside corner vertex and at least two navigation cell vertices from said plurality of navigation cell vertices, said at least two navigation cell vertices and said inside corner vertex forming a plane, said plane having a same sidedness orientation as said first polygon sharing said at least one first-order silhouette edge, said plane not being front-facing with respect to each navigation cell vertex from said plurality of navigation cell vertices, and said contained mesh polygons or fragments of said contained mesh polygons included on a side of the plane that is visible from the navigation cell.

2. The computer-implemented method of claim 1, further comprising:

h) transmitting said determined set of said contained mesh polygons or fragments of said contained mesh polygons visible from said navigation cell to a client computing device for display on said client computing device.

3. The computer-implemented method of claim 1, wherein,

a computer generated modeled environment containing said determined set of contained mesh polygons or fragments of said contained mesh polygons visible from said navigation cell includes a predetermined viewpoint motion path that traverses through said navigation cell, and

said predetermined view frusta restricted to view frusta originating from said predetermined viewpoint motion path.

4. The computer-implemented method of claim 1, wherein

a computer generated modeled environment containing said determined set of contained mesh polygons or fragments of said contained mesh polygons visible from said navigation cell includes a user controlled viewpoint motion path that traverses through the navigation cell and at least one user controlled view direction vector extending from viewpoints on said motion path, and

said predetermined view frusta restricted to view frusta originating from said at least one view direction vector on said motion path.

5. The computer-implemented method of claim 4, wherein said at least one view direction vector is directionally constrained.

6. A server to determine a set of mesh polygons or fragments of said mesh polygons visible from a navigation cell, said mesh polygons forming polygon meshes, the server comprising:

a processor configured to;

determine a composite view frustum containing predetermined view frusta in said navigation cell;

determine mesh polygons contained in said composite view frustum;

determine at least one supporting polygon between said navigation cell and said contained mesh polygons;

construct at least one wedge from said at least one supporting polygon, said at least one wedge extending away from said navigation cell beyond at least said contained mesh polygons;

determine one or more intersections of said at least one wedge with said contained mesh polygons;

determine said set of said contained mesh polygons or fragments of said contained mesh polygons visible from said navigation cell using said determined one or more intersections of said at least one wedge with said polygon meshes; and

determine at least one first-order silhouette edge of said contained mesh polygons,

wherein said at least one supporting polygon is determined between said navigation cell and at least one vertex of said at least one first-order silhouette edge,

wherein the navigation cell includes a plurality of navigation cell vertices,

wherein said at least one first-order silhouette edge includes;

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

the first polygon backfacing to each navigation cell vertex from the plurality of navigation cell vertices,

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

the first and second polygons having a backfacing orientation with respect to each other, and

wherein upon determination, by the processor, that said at least one first-order silhouette edge and another first-order silhouette edge share a vertex forming an inside corner vertex of said polygon mesh, the at least one supporting polygon is formed by said inside corner vertex and at least two navigation cell vertices from said plurality of navigation cell vertices, said at least two navigation cell vertices and said inside corner vertex forming a plane, said plane having a same sidedness orientation as said first polygon sharing said at least one first-order silhouette edge, said plane not being front-facing with respect to each navigation cell vertex from said plurality of navigation cell vertices, and said contained mesh polygons or fragments of said contained mesh polygons included on a side of the plane that is visible from the navigation cell.

7. A system to determine a set of mesh polygons or fragments of said mesh polygons visible from a navigation cell, said mesh polygons forming polygon meshes, the system comprising:

a server having a processor configured to;

determine a composite view frustum containing predetermined view frusta in said navigation cell;

determine mesh polygons contained in said composite view frustum;

determine at least one supporting polygon between said navigation cell and said contained mesh polygons;

construct at least one wedge from said at least one supporting polygon, said at least one wedge extending away from said navigation cell beyond at least said contained mesh polygons;

determine one or more intersections of said at least one wedge with said contained mesh polygons;

determine said set of said contained mesh polygons or fragments of said contained mesh polygons visible from said navigation cell using said determined one or more intersections of said at least one wedge with said polygon meshes; and

determine at least one first-order silhouette edge of said contained mesh polygons,

wherein said at least one supporting polygon is determined between said navigation cell and at least one vertex of said at least one first-order silhouette edge,

wherein the navigation cell includes a plurality of navigation cell vertices,

wherein said at least one first-order silhouette edge includes;

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

the first polygon backfacing to each navigation cell vertex from the plurality of navigation cell vertices,

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

the first and second polygons having a backfacing orientation with respect o each other, and

wherein upon determination, by the processor, that said at least one first-order silhouette edge and another first-order silhouette edge share a vertex forming an inside corner vertex of said polygon mesh, the at least one supporting polygon is formed by said inside corner vertex and at least two navigation cell vertices from said plurality of navigation cell vertices, said at least two navigation cell vertices and said inside corner vertex forming a plane, said plane having a same sidedness orientation as said first poly on sharing said at least one first-order silhouette edge, said plane not being front-facing with respect to each navigation cell vertex from said plurality of navigation cell vertices, and said contained mesh polygons or fragments of said contained mesh polygons included on a side of the plane that is visible from the navigation cell; and

a client computing device configured to receive and display said determined set of said contained mesh polygons or fragments of said contained mesh polygons visible from said navigation cell.

8. A non-transitory computer readable storage medium having executable instructions stored thereon, which when executed by a processor in a server causes the processor to execute a method for determining a set of mesh polygons or fragments of said mesh polygons visible from a navigation cell, said mesh polygons forming polygon meshes, the method comprising steps of:

a) determining a composite view frustum containing predetermined view frusta in said navigation cell;

b) determining mesh polygons contained in said composite view frustum;

c) determining at least one supporting polygon between said navigation cell and said contained mesh polygons;

d) constructing at least one wedge from said at least one supporting polygon, said at least one wedge extending away from said navigation cell beyond at least said contained mesh polygons;

e) determining one or more intersections of said at least one wedge with said contained mesh polygons;

f) determining said set of said contained mesh polygons or fragments of said contained mesh polygons visible from said navigation cell using said determined one or more intersections of said at least one wedge with said polygon meshes; and

g) determining, at least, one first-order silhouette edge of said contained mesh polygons,

wherein said at least one supporting polygon is determined between said navigation cell and at least one vertex of said at least one first-order silhouette edge,

wherein the navigation cell includes a plurality of navigation cell vertices,

wherein said at least one first-order silhouette edge includes;

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

the first polygon backfacing to each navigation cell vertex from the plurality of navigation cell vertices,

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

the first and second polygons having a backfacing orientation with respect to each other, and

wherein upon determination that said at least one first-order silhouette edge and another first-order silhouette edge share a vertex forming an inside corner vertex of said polygon mesh, the at least one supporting polygon is formed by said inside corner vertex and at least two navigation cell vertices from said plurality of navigation cell vertices, said at least two navigation cell vertices and said inside corner vertex forming a plane, said plane having a same sidedness orientation as said first polygon sharing said at least one first-order silhouette edge, said plane not being front-facing with respect to each navigation cell vertex from said plurality of navigation cell vertices, and said containedmesh polygons or fragments of said contained mesh polygons included on a side of the plane that is visible from the navigation cell.