System and method of from-region visibility determination and delta-PVS based content streaming using conservative linearized umbral event surfaces

• US 9,472,019 B2
• Filed: 06/29/2011
• Issued: 10/18/2016
• 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
• Primary Examiner(s): Crawford, Jacinta M
• Assistant Examiner(s): WILLS, DIANE M
• Application Number:
  US13/807,824
• Publication Number:
  US 20130207976A1
• Time in Patent Office: 1,938 Days
• Field of Search: None
• US Class Current: 1/1
• 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. 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:

a) determining, using processing circuitry, at least one first-order silhouette edge of said polygon meshes, 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;

b) determining, using the processing circuitry, at least one supporting polygon between said view region and said at least one first-order silhouette edge wherein said at least one supporting polygon is a conservative supporting polygon that is constructed regardless of any mesh polygon intersecting said supporting polygon between said view region and said at least one first-order silhouette edge;

c) constructing, using the processing circuitry, at least one wedge from said at least one supporting polygon, said at least one wedge extending away from said view region beyond said at least one first-order silhouette edge;

d) determining, using the processing circuitry, one or more intersections of said wedges with said mesh polygons; and

e) determining, using the processing circuitry, 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; and

f) outputting, using processing circuitry, said set of said mesh polygons or fragments of said mesh polygons visible from said view region as a conservative approximate of exact surfaces visible from said view region.

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

determining, for said at least one first-order silhouette edge, using the processing circuitry, 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.

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

determining, for said at least one first-order silhouette edge, using the processing circuitry, 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.

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:

a) determining, using processing circuitry, at least one first-order silhouette edge of said polygon meshes, 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;

b) determining, using the processing circuitry, if 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;

c) 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, determining, using the processing circuitry, at least one supporting polygon between said view region and said at least one first-order silhouette edge, wherein 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;

d) constructing, using the processing circuitry, at least one wedge from said at least one supporting polygon, said at least one wedge extending away from said view region beyond said at least one first-order silhouette edge;

e) determining, using the processing circuitry, one or more intersections of said wedges with said mesh polygons;

f) determining, using the processing circuitry, 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; and

g) outputting, using processing circuitry, said set of said mesh polygons or fragments of said mesh polygons visible from said view region as a conservative approximate of exact surfaces visible from said view region.

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

6. 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.

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

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

9. 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:

a) determining, using processing circuitry, at least one first-order silhouette edge of said polygon meshes, 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;

b) determining, using the processing circuitry, at least one supporting polygon between said view region and at least one first-order silhouette edge;

c) constructing, using the processing circuitry, at least one wedge from said at least one supporting polygon, said at least one wedge extending away from said view region beyond said at least one first-order silhouette edge;

d) determining, using the processing circuitry, one or more intersections of said wedges with said mesh polygons;

e) determining, using the processing circuitry, if said at least one wedge intersects at least one second first-order silhouette edge, said intersection forming a compound silhouette vertex;

f) upon determination that said at least one wedge intersects said at least one first-order silhouette edge forming a compound silhouette vertex, forming at least one second wedge, wherein said at least one second wedge 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 compound silhouette vertex forming a plane, said plane not front-facing with respect to each view region vertex from said plurality of view region vertices;

g) determining, using the processing circuitry, 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; and

h) outputting, using processing circuitry, said set of said mesh polygons or fragments of said mesh polygons visible from said view region as a conservative approximate of exact surfaces visible from said view region.

10. The method of claim 9, wherein said view region is a volume.

11. The method of claim 9, wherein said polygon meshes comprise manifold triangle meshes.

12. The method of claim 9, wherein said at least one supporting polygon is a conservative supporting polygon that is constructed regardless of any mesh polygon intersecting said supporting polygon between said view region and said at least one first-order silhouette edge.

13. The method of claim 9, wherein said polygon meshes comprise non-convex polygon meshes.

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

15. 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:

a) determining, using processing circuitry, at least one first-order silhouette edge of said polygon meshes, 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;

b) determining, using the processing circuitry, at least one supporting polygon between said view region and at least one first-order silhouette edge, said determining at least one supporting polygon comprising 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;

c) constructing, using the processing circuitry, 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;

said constructing of said at least one wedge comprising;

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

c2) constructing said at least one wedge, said at least one wedge including said plane of said at least one supporting polygon, and

c3) restricting said at least one wedge, formed in the step c2) 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;

d) determining, using the processing circuitry, one or more intersections of said wedges with said mesh polygons;

e) determining, using the processing circuitry, 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; and

f) outputting, using processing circuitry, said set of said mesh polygons or fragments of said mesh polygons visible from said view region as a conservative approximate of exact surfaces visible from said view region.

16. 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:

a) determining, using processing circuitry, at least one first-order silhouette edge of said polygon meshes, 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;

b) determining, using the processing circuitry, at least one supporting polygon between said view region and at least one first-order silhouette edge, said determining at least one supporting polygon comprising 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;

c) constructing, using the processing circuitry, 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;

said constructing of said at least one wedge comprising;

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

c2) constructing said at least one wedge, said at least one wedge including the plane of said at least one supporting polygon, and

c3) restricting said at least one wedge, formed in the step c2) 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;

d) determining, using the processing circuitry, one or more intersections of said wedges with said mesh polygons;

e) determining, using the processing circuitry, 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; and

f) outputting, using processing circuitry, said set of said mesh polygons or fragments of said mesh polygons visible from said view region as a conservative approximate of exact surfaces visible from said view region.

17. 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:

a) determining, using processing circuitry, at least one first-order silhouette edge of said polygon meshes, 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;

b) determining, using the processing circuitry, if said at least one first-order silhouette edge has at least one cusp vertex, said cusp vertex being defined as a vertex of said first-order silhouette edge that is not a vertex for any other first-order silhouette edge;

c) upon determination that said at least one first-order silhouette edge has at least one cusp vertex, determining, using the processing circuitry, at least one supporting polygon between said view region and said at least one first-order silhouette edge, wherein said at least one supporting polygon is formed by said cusp 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;

d) constructing, using the processing circuitry, at least one wedge from said at least one supporting polygon, said at least one wedge sharing said cusp vertex and extending away from said view region beyond said at least one first-order silhouette edge;

e) determining, using the processing circuitry, one or more intersections of said at least one wedge with said mesh polygons;

f) determining, using the processing circuitry, 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; and

g) outputting, using processing circuitry, said set of said mesh polygons or fragments of said mesh polygons visible from said view region as a conservative approximate of exact surfaces visible from said view region.

18. 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:

a) determining, using processing circuitry, at least one first-order silhouette edge of said polygon meshes, 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;

b) determining, using the processing circuitry, at least one supporting polygon between said view region and at least one first-order silhouette edge, said determining at least one supporting polygon comprising determining a higher-order supporting polygon, wherein said higher-order 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;

c) constructing, using the processing circuitry, at least one wedge from said at least one higher-order supporting polygon, said at least one wedge extending away from said view region beyond at least one first-order silhouette edge;

d) determining, using the processing circuitry, one or more intersections of said wedges with said mesh polygons;

e) determining, using the processing circuitry, 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; and

f) outputting, using processing circuitry, said set of said mesh polygons or fragments of said mesh polygons visible from said view region as an adaptive, conservative approximate of exact surfaces visible from said view region.

19. 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:

a) determining, using processing circuitry, at least one first-order silhouette edge of said polygon meshes, 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;

b) determining, using the processing circuitry, at least one supporting polygon between said view region and at least one first-order silhouette edge, said determining at least one supporting polygon comprising determining at least one higher-order supporting polygon, wherein said higher-order 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, said visible supporting view region determined by;

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

b2) 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;

b3) 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;

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

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

b6) 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;

c) constructing, using the processing circuitry, at least one wedge from said at least one higher-order supporting polygon, said at least one wedge extending away from said view region beyond at least said at least one first-order silhouette edge;

d) determining, using the processing circuitry, one or more intersections of said wedges with said mesh polygons;

e) determining, using the processing circuitry, 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; and

f) outputting, using processing circuitry, said set of said mesh polygons or fragments of said mesh polygons visible from said view region as an adaptive, conservative approximate of exact surfaces visible from said view region.

20. 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:

a) determining, using processing circuitry, at least one first-order silhouette edge of said polygon meshes, 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;

b) determining, using the processing circuitry, if 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;

c) 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, determining, using the processing circuitry, at least one supporting polygon between said view region and said at least one first-order silhouette edge, wherein said 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;

d) constructing, using the processing circuitry, at least one wedge from said at least one supporting polygon, said at least one wedge extending away from said view region beyond said at least one first-order silhouette edge;

e) determining, using the processing circuitry, one or more intersections of said wedges with said mesh polygons, said intersections defining 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;

f) determining, using the processing circuitry, 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;

g) determining, using the processing circuitry, a number of mesh polygons occluded by said at least one from view region occlusion boundary;

h) removing, using the processing circuitry, 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; and

i) outputting, using processing circuitry, said set of said mesh polygons or fragments of said mesh polygons visible from said view region, excluding said removed at least one from view region occlusion boundary, as a conservative approximate of exact surfaces visible from said view region.