System and method of procedural visibility for interactive and broadcast streaming of entertainment, advertising, and tactical 3D graphical information using a visibility event codec

• US 9,171,396 B2
• Filed: 04/12/2012
• Issued: 10/27/2015
• 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): Faulk, Devona
• Assistant Examiner(s): BEARD, CHARLES LLOYD
• Application Number:
  US13/445,792
• Publication Number:
  US 20120256915A1
• Time in Patent Office: 1,293 Days
• US Class Current: 1/1
• CPC Class Codes: G06T 15/40 Hidden part removal
• 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

A system includes a server and a client computer device. The server determines a graphical object visible from a view region and determines one or more parameters defining the graphical object visible from the view region. The server further transmits the determined one or more parameters to a client computing device. The client computing device includes a processor to generate the graphical object using the determined one or more parameters received from the server. The client computing device further includes a display device to display the generated graphical object within a computer generated modeled environment.

Claims

1. A computer-implemented method comprising steps of:

a) determining, using a processor, one or more portions of a procedurally generated 3D graphical object not occluded from a second viewcell and occluded from a first viewcell, the procedurally generated 3D graphical object comprising graphics primitives generated by a generation procedure using procedural parameters,

wherein the first and second viewcells have a plurality of viewcell vertices,

wherein both non-procedural 3D graphical objects and the procedurally generated 3D graphical object comprise mesh polygons forming polygon meshes, and

wherein the one or more portions of the procedurally generated graphical object not occluded from the second viewcell and occluded from the first viewcell are determined by steps of;

a1) executing a generation procedure to generate the mesh polygons comprising the procedurally generated object,

a2) determining at least one first-order silhouette edge of the polygon meshes, the at least one first-order silhouette edge being an edge of the 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 second viewcell,

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

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

a3) determining at least one supporting polygon between the second viewcell and the polygon meshes, the at least one supporting polygon being determined between the second viewcell and at least one vertex of the at least one first-order silhouette edge,

a4) constructing at least one wedge from the at least one supporting polygon, the at least one wedge extending away from the second viewcell,

a5) determining one or more intersections of the at least one wedge with the mesh polygons, and

a6) determining the set of the mesh polygons or fragments of the mesh polygons not occluded from the second viewcell using the determined one or more intersections;

b) determining, using the processor, values of the procedural parameters, which define the one or more portions of the procedurally generated 3D graphical object not occluded from the second viewcell and occluded from the first viewcell; and

c) storing the values of the procedural parameters, which define the one or more portions of the procedurally generated 3D graphical object not occluded from the second viewcell and occluded from the first viewcell.

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

d) transmitting the values of the procedural parameters to a client computing device that uses the determined one or more parameters to generate and display the procedurally generated 3D graphical object.

3. The computer-implemented method of claim 1, further comprising the step of:

d) transmitting the values of the procedural parameters if any portion of the procedurally generated 3D graphical object is unoccluded from the second viewcell and occluded from the first viewcell.

4. The computer-implemented method of claim 1, wherein the step of determining the at least one supporting polygon further comprises:

determining, for the at least one first-order silhouette edge, a supporting viewcell vertex defined as a first viewcell vertex from the plurality of viewcell vertices encountered in pivoting a plane about the first-order silhouette edge toward the second viewcell, the pivoted plane being incident on the first-order silhouette edge and not front-facing with respect to each viewcell vertex from the plurality of viewcell vertices.

5. The computer-implemented method of claim 1, wherein the step of determining the at least one supporting polygon further comprises:

determining, for the at least one first-order silhouette edge, a supporting viewcell vertex from the plurality of viewcell vertices, the supporting viewcell vertex forming a plane with the first-order silhouette edge, the plane having a same sidedness orientation as the first polygon sharing the first-order silhouette edge, and the plane not front-facing with respect to each viewcell vertex from the plurality of viewcell vertices.

6. The computer-implemented method of claim 1, wherein upon determination that the at least one first-order silhouette edge and another first-order silhouette edge share a vertex forming an inside corner vertex of the graphical object, the at least one supporting polygon is formed by the inside corner vertex and at least two viewcell vertices from the plurality of viewcell vertices, the at least two viewcell vertices and the inside corner vertex forming a plane,

the plane having a same sidedness orientation as the first polygon sharing the at least one first-order silhouette edge, and

the plane not front-facing with respect to each viewcell vertex from the plurality of viewcell vertices.

7. The computer-implemented method of claim 1, further comprising the steps of:

e) determining a likelihood that a user viewpoint undergoes movement from the first viewcell to the second viewcell; and

f) sending information representing the generation procedure and sending the values of the procedural parameters upon determination that the likelihood that the viewpoint undergoes movement from the first viewcell to the second viewcell is greater than a predetermined threshold.

8. A computer-implemented method conducted on a client computing device, the method comprising steps of:

a) displaying a first set of graphics information not occluded from a second viewcell and occluded from a first viewcell,

the first and second viewcells having a plurality of viewcell vertices,

the first set of graphics information including one or more 3D objects in a computer-represented environment,

the first set of graphics information comprising graphics primitives generated using procedural parameters, and mesh polygons forming polygon meshes,

wherein one or more portions of the procedurally generated first set of graphics information not occluded from the second viewcell and occluded from the first viewcell are determined by;

a1) determining at least one first-order silhouette edge of the polygon meshes, the at least one first-order silhouette edge being an edge of the 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 second viewcell,

the second polygon front-facing to at least one viewcell vertex from the plurality of viewcell vertices of the second 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 second viewcell and the polygon meshes, the at least one supporting polygon being determined between the second 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 second viewcell;

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

a5) determining the set of the mesh polygons or fragments of the mesh polygons not occluded from the second viewcell using the determined one or more intersections;

b) receiving, from a server, a second set of graphics information upon determination that at least one predetermined condition is satisfied, the second graphics information not occluded from the second viewcell and occluded from the first viewcell, the second set of graphics information including at least one 3D advertising object;

c) displaying the second set of graphics information within the displayed computer-represented environment;

d) displaying the second set of graphics information with a visual indication that the second set of graphics information is selectable with only a single button press; and

e) transmitting a selection result of the displayed second set of graphics information to the server.

9. The computer-implemented method of claim 8, wherein the at least one predetermined condition is satisfied upon determination that a likelihood that a user viewpoint moves from the first viewcell to the second viewcell is greater than a predetermined threshold.

10. The computer-implemented method of claim 8, wherein the at least one predetermined condition is satisfied upon determination that a likelihood that a user viewpoint moves from the first viewcell to the second viewcell is greater than a predetermined threshold and that an available transmission bandwidth between a server and the client computing device exceeds a predetermined bandwidth threshold.

11. The computer-implemented method of claim 8, wherein the step d) of displaying the second set of graphics information further comprises displaying with the visual indication that the second set of graphics information is selectable with only the single button press only if the 3D advertising object is not occluded.

12. The computer-implemented method of claim 11, wherein the displayed visual indication is a highlight around the 3D advertising object.

13. The computer-implemented method of claim 12, wherein the displayed 3D advertising object is selectable by a single-click activation of a client input device regardless of a position of a user viewpoint in the second viewcell.

14. The computer-implemented method of claim 8, wherein the displayed second set of graphics information is selectable by a single-click activation of a client input device regardless of a position of a user viewpoint in the second viewcell.

15. The computer-implemented method of claim 14, wherein the displayed second set of graphics information represents an object available for purchase, the object being usable within a computer-implemented modeled environment.

16. The computer-implemented method of claim 8, further comprising:

providing a fee-based option to prevent display of the second set of graphics information.

17. The computer-implemented method of claim 16, wherein a fee assessed to a user of the client computing device is reduced upon determination that the user did not select the fee-based option to prevent display of the second set of graphics information.

18. A system, comprising:

an encoder configured to perform a computer-implemented encoding method comprising steps of;

a1) determining, using a processor, one or more portions of a procedurally generated 3D graphical object not occluded from a second viewcell and occluded from a first viewcell, the procedurally generated 3D graphical object comprising graphics primitives generated by a generation procedure using procedural parameters,

a2) determining, using the processor, values of the procedural parameters, which define the one or more portions of the procedurally generated 3D graphical object not occluded from the second viewcell and occluded from the first viewcell, and

a3) storing the values of the procedural parameters, which define the one or more portions of the procedurally generated 3D graphical object not occluded from the second viewcell and occluded from the first viewcell;

a server configured to;

b1) transmit the values of the procedural parameters if any portion of the procedurally generated 3D graphical object is unoccluded from the second viewcell and occluded from the first viewcell; and

a client configured to;

c1) display a first set of graphics information not occluded from the second viewcell and occluded from the first viewcell, the first set of graphics information including one or more 3D objects in a computer-represented environment,

c2) receive, from the server, a second set of graphics information upon determination that at least one predetermined condition is satisfied, the second graphics information not occluded from the second viewcell and occluded from the first viewcell, the second set of graphics information including at least one 3D advertising object,

c3) display the second set of graphics information within the displayed computer-represented environment,

c4) the second set of graphics information with a visual indication that the second set of graphics information is selectable with only a single button press, and

c5) transmit a selection result of the displayed second set of graphics information to the server,

wherein the first and second viewcells have a plurality of viewcell vertices,

wherein both non-procedural 3D graphical objects and the procedurally generated 3D graphical object comprise mesh polygons forming polygon meshes, and

wherein the one or more portions of the procedurally generated 3D graphical object not occluded from the second viewcell and occluded from the first viewcell are determined by steps of;

d1) determining at least one first-order silhouette edge of the polygon meshes, the at least one first-order silhouette edge being an edge of the 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 second viewcell,

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

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

d2) determining at least one supporting polygon between the second viewcell and the polygon meshes, the at least one supporting polygon being determined between the second viewcell and at least one vertex of the at least one first-order silhouette edge,

d3) constructing at least one wedge from the at least one supporting polygon, the at least one wedge extending away from the second viewcell,

d4) determining one or more intersections of the at least one wedge with the mesh polygons, and

d5) determining the set of the mesh polygons or fragments of the mesh polygons not occluded from the second viewcell using the determined one or more intersections.

19. A system, comprising:

a server including a memory to store;

a first set of graphics information representing a procedure for generating a procedurally generated 3D graphical object using procedural parameters, and

a second set of graphics information representing values of the procedural parameters which define the one or more portions of the procedurally generated 3D graphical object not occluded from a second viewcell and occluded from a first viewcell;

a processor configured to;

determine a likelihood that a user viewpoint moves from the first viewcell to the second viewcell, and

transmit the first and second sets of graphics information to a client only if the likelihood that a client-user viewpoint moves from the first viewcell to the second viewcell exceeds a movement threshold; and

a client computing device configured to;

upon determination that the likelihood that that the client-user viewpoint moves from the first viewcell to the second viewcell exceeds the movement threshold, and

generate a portion of the procedurally generated 3D graphical object using the transmitted first and second sets of graphics information including the values of the procedural parameters, which define the one or more portions of the procedurally generated 3D graphical object not occluded from the second viewcell and occluded from the first viewcell,

wherein the first and second viewcells have a plurality of viewcell vertices,

wherein both non-procedural 3D graphical objects and the procedurally generated 3D graphical object comprise mesh polygons forming polygon meshes, and

wherein the one or more portions of a procedurally generated 3D graphical object not occluded from a second viewcell and occluded from a first viewcell are determined by steps of;

a1) determining at least one first-order silhouette edge of the polygon meshes, the at least one first-order silhouette edge being an edge of the 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 second viewcell,

the second polygon front-facing to at least one viewcell vertex from the plurality of viewcell vertices of the second 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 second viewcell and the polygon meshes, the at least one supporting polygon being determined between the second 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 second viewcell,

a4) determining one or more intersections of the at least one wedge with the mesh polygons, and

a5) determining the set of the mesh polygons or fragments of the mesh polygons not occluded from the second viewcell using the determined one or more intersections.

20. The system of claim 19, wherein the procedurally generated 3D graphical object represents a 3D advertising object.

21. A non-transitory computer readable storage medium having computer executable instructions stored thereon, which when executed by a processor in a server, causes the server to execute a method comprising steps of:

a) determining, using a processor, one or more portions of a procedurally generated 3D graphical object not occluded from a second viewcell and occluded from a first viewcell, the procedurally generated 3D graphical object comprising graphics primitives generated by a generation procedure using procedural parameters,

wherein the first and second viewcells have a plurality of viewcell vertices,

wherein both non-procedural 3D graphical objects and the procedurally generated 3D graphical object comprise mesh polygons forming polygon meshes, and

wherein the one or more portions of a procedurally generated 3D graphical object not occluded from a second viewcell and occluded from a first viewcell are determined by steps of;

a1) executing the generation procedure to generate mesh polygons comprising the procedurally generated object,

a2) determining at least one first-order silhouette edge of the polygon meshes, the at least one first-order silhouette edge being an edge of the 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 second viewcell,

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

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

a3) determining at least one supporting polygon between the second viewcell and the polygon meshes, the at least one supporting polygon being determined between the second viewcell and at least one vertex of the at least one first-order silhouette edge,

a4) constructing at least one wedge from the at least one supporting polygon, the at least one wedge extending away from the second viewcell,

a5) determining one or more intersections of the at least one wedge with the mesh polygons, and

a6) determining the set of the mesh polygons or fragments of the mesh polygons not occluded from the second viewcell using the determined one or more intersections;

b) determining, using the processor, values of the procedural parameters, which define the one or more portions of the procedurally generated 3D graphical object not occluded from the second viewcell and occluded from the first viewcell; and

c) storing the values of the procedural parameters, which define the one or more portions of the procedurally generated 3D graphical object not occluded from the second viewcell and occluded from the first viewcell.

22. The non-transitory computer-readable storage medium according to claim 21,

wherein the procedurally generated 3D graphical object represents a 3D advertising object, and

wherein the 3D advertising object is selectable by a only single-click activation of a client input device regardless of a position of a user viewpoint in the second viewcell.

23. The non-transitory computer readable storage medium according to claim 21, further comprising:

d) transmitting the values of the procedural parameters to a client computing device if any portion of the procedurally generated graphical object is unoccluded from the second viewcell and occluded from the first viewcell.