SYSTEM AND METHOD OF FROM-REGION VISIBILITY DETERMINATION AND DELTA-PVS BASED CONTENT STREAMING USING CONSERVATIVE LINEARIZED UMBRAL EVENT SURFACES

• US 20130207976A1
• Filed: 06/29/2011
• Published: 08/15/2013
• Est. Priority Date: 06/30/2010
• Status: Active Grant

• Current Assignee: Primal Space Systems Inc.
• Original Assignee: Primal Space Systems Inc.
• Inventors: Jenkins, Barry Lynn
• Granted Patent: US 9,472,019 B2
• Time in Patent Office: Days
• US Class Current: 345/420
• 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

A method determines a set of mesh polygons or fragments of the mesh polygons visible from a view region having a plurality of view region vertices, the mesh polygons forming polygon meshes. The method includes determining at least one supporting polygon between the view region and the polygon meshes. 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 view region beyond at least the polygon meshes. Further, the method includes determining one or more intersections of the wedges with the mesh polygons. Also, the method includes determining the set of the mesh polygons or fragments of the mesh polygons visible from the view region using the determined one or more intersections of the at least one wedge with the polygon meshes.

Claims

1-3. -3. (canceled)

4. A method of determining a set of mesh polygons or fragments of said mesh polygons visible from a view region having a plurality of view region vertices, said mesh polygons forming polygon meshes, the method comprising steps of:

a) determining at least one supporting polygon between said view region and said polygon meshes;

b) constructing at least one wedge from said at least one supporting polygon, said at least one wedge extending away from said view region beyond at least said polygon meshes;

c) determining one or more intersections of said wedges with said mesh polygons; and

d) determining said set of said mesh polygons or fragments of said mesh polygons visible from said view region using said determined one or more intersections of said at least one wedge with said polygon meshes

e) determining at least one first-order silhouette edge of said polygon meshes, wherein

said at least one supporting polygon is determined between said view region and at least one vertex of said at least one first-order silhouette edge, 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 view region vertex from the plurality of view region vertices,

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

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

5. The method of claim 4, wherein the step b) of determining at least one supporting polygon further comprises:

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

6. The method of claim 4, wherein the step b) of determining at least one supporting polygon further comprises:

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

7. The method according to claim 4, 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 view region vertices from said plurality of view region vertices, said at least two view region 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, and

said plane not front-facing with respect to each view region vertex from said plurality of view region vertices.

8. The method according to claim 4, wherein

upon determination that said at least one wedge intersects said at least one first-order silhouette edge forming a compound silhouette vertex, the at least one supporting polygon is formed by said compound silhouette vertex and at least two view region vertices from said plurality of view region vertices, said at least two view region vertices and said inside corner vertex forming a plane, said plane not front-facing with respect to each view region vertex from said plurality of view region vertices.

9. The method according to claim 5, wherein the step b) of constructing said at least one wedge further comprises the steps of:

b1) determining a plane of said at least one supporting polygon, and

b2) constructing said at least one wedge, said at least one wedge including said plane of said at least one supporting polygon;

b3) restricting said at least one wedge, formed in the step b2 of constructing, by intersecting said at least one wedge with at least a second wedge, said at least second wedge and said at least one wedge sharing a vertex of said mesh polygons.

10. The method of claim 6, wherein the step b) of constructing said at least one wedge further comprises the steps of:

b1) determining a plane of said at least one supporting polygon, and

b2) constructing a first wedge, wherein said first wedge comprises the plane of said at least one supporting polygon;

b3) restricting said at least one wedge, formed in the step b2 of constructing, by intersecting said at least one wedge with at least a second wedge, wherein said at least second wedge and said at least one wedge share said compound silhouette vertex of said mesh polygons.

11. The method according to claim 4, wherein the step c) of constructing said at least one wedge further comprises the steps of:

c1) constructing extended edges of said at least one supporting polygon by extending edges of said at least one supporting polygon away from said view region, said extended edges intersecting at least one vertex of said at least one first-order silhouette edge,

c2) constructing said at least one wedge from said extended edges and said at least one vertex of said at least one first-order silhouette edge.

12. The method of claim 4, wherein said polygon meshes comprise manifold triangle meshes.

13. The method of claim 4, wherein said at least one supporting polygon is a conservative supporting polygon that is constructed regardless of any intervening polygon meshes between said view region and said at least one first-order silhouette edge.

14. The method of claim 4, wherein said polygon meshes comprise non-convex polygon meshes.

15. The method of claim 4, wherein the step b) of determining at least one supporting polygon further comprises the steps of:

d) constructing at least one swept supporting polygon between said view region and said polygon meshes for each cusp vertex of said polygon meshes, the cusp vertex being defined as a vertex of a first-order silhouette edge, wherein said vertex of a first-order silhouette is not a vertex for any other first-order silhouette edge.

16. The method of claim 9, wherein said at least one first-order silhouette edge is not an edge of a portal.

19. The method according to claim 4, wherein the step a) of determining said at least one supporting polygon further comprises:

determining a higher-order vertex supporting polygon, wherein said higher-order vertex supporting polygon is defined by said at least one first-order silhouette edge and a visible supporting view region vertex defined as a first visible view region vertex encountered in pivoting a plane about said first-order silhouette edge toward said view region, said pivoted plane incident on said first-order silhouette edge and not front-facing with respect to each visible view region vertex, said visible view region vertex visible from said first-order silhouette edge.

20. The method according to claim 19, wherein determining said at least one visible view region vertex further comprises:

using said at least one first-order silhouette edge as a lineal view region;

determining at least one backprojection first-order silhouette edge of said polygon meshes in a shaft formed between said lineal view region and said view region, said at least one backprojection first-order silhouette edge further including;

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

the first polygon backfacing to each lineal view region vertex of said lineal view region,

the second polygon front-facing to at least one lineal view region vertex of said lineal view region, and

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

determining at least one backprojection supporting polygon between said lineal view region and at least one vertex of said at least one backprojection first-order silhouette edge;

constructing at least one backprojection wedge from said at least one backprojection supporting polygon;

determining one or more intersections of said at least one backprojection wedge with polygons of said view region; and

determining said at least one visible view region vertex using said one or more intersections of said at least one backprojection wedge with said polygons of said view region.

17-18. -18. (canceled)

21-56. -56. (canceled)

57. A method of determining a set of mesh polygons or fragments of said mesh polygons visible from a view region, said mesh polygons forming polygon meshes, the method comprising steps of:

a) determining at least one from view region occlusion boundary incident on said mesh polygons, said at least one from view region occlusion boundary having an unoccluded side and an occluded side;

b) determining a number of mesh polygons added to said set of mesh polygons or fragments of said mesh polygons visible from said view region, said mesh polygons added by repartitioning, at an intersection between a polygon mesh and said at least one from view region occlusion boundary on said unoccluded side, a surface of said intersected polygon mesh;

c) determining a number of mesh polygons occluded by said at least one from view region occlusion boundary;

d) removing said at least one from view region occlusion boundary upon determination that said number of mesh polygons added exceeds said number of mesh polygons occluded by a predetermined threshold.

58-119. -119. (canceled)

120. A method, conducted on a server, for controlling navigation-based pre-fetch sending of graphics information to a client device, said graphics information including a first set of graphics information visible from a second view region and not visible from a first view region, and said graphics information including a second set of graphics information visible from said second view region and not visible from said first view region, said second set of graphics information having a lower level-of-detail than said first set of graphics information, the method comprising steps of:

a) determining a first period during which said first set of graphics information will arrive after said client device is scheduled to access said first set of graphics information on said client device; and

b) sending said second set of graphics information during said first period.

121. The method according to claim 120, wherein said navigation-based prefetch comprises steps of:

receiving, from said client device, information indicating a first viewpoint location at a first instant;

predicting, using said information indicating said first viewpoint location, a second viewpoint location at a second instant, said second instant later than said first instant;

determining if said first viewpoint location and said second viewpoint location are in different view regions,

sending, upon determination that said first viewpoint location and said second viewpoint location are in different view regions, said second set of graphics information.

123. The method of claim 120 further comprising steps of:

c) sending additional graphics information during a second period occurring after said first period, said additional graphics information including information used to add detail to said second set of graphics information sent during said first period.

124. The method of claim 123, wherein

the amount of said additional graphics information sent in the step c) is selected in accordance with a function of an elapsed time period between said first period and said second period, and

the amount of said additional graphics information sent in the step c) is further selected in proportion to the human visual system'"'"'s ability to perceive said additional graphics information after said elapsed time period.

122. (canceled)

125-155. -155. (canceled)