SYSTEM AND METHOD OF REDUCING TRANSMISSION BANDWIDTH REQUIRED FOR VISIBILITY-EVENT STREAMING OF INTERACTIVE AND NON-INTERACTIVE CONTENT

• US 20160005214A1
• Filed: 06/29/2015
• Published: 01/07/2016
• Est. Priority Date: 06/30/2010
• Status: Active Grant

• Current Assignee: Primal Space Systems Inc.
• Original Assignee: Barry L. Jenkins
• Inventors: JENKINS, Barry L.
• Granted Patent: US 9,852,538 B2
• Time in Patent Office: Days
• 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

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; and

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.

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

g) 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 a user controlled view direction vector extending from viewpoints on said motion path, and

said predetermined view frusta restricted to view frusta originating from said view direction vectors on said motion path.

5. The computer-implemented method according to claim 1, further comprising:

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

6. The computer-implemented method according to claim 5, 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.

7. The computer-implemented method according to claim 6, wherein

the navigation cell includes a plurality of navigation cell vertices,

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.

8. The computer-implemented method according to claim 7, 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 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.

9. The computer-implemented method of claim 3, wherein said view direction vectors are directionally constrained.

10. A computer-implemented method conducted on a server, the method comprising:

a) storing graphics information including a first set of graphics information visible from a second navigation cell and not visible from a first navigation cell, said first set of graphics information visible from any direction in said second navigation cell, and said graphics information including a second set of graphics information visible from said second navigation cell and not visible from said first navigation cell, said second set of graphics information included within predetermined view frusta associated with said second navigation cell;

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

c) sending said second set of graphics information during said determined period to said client computing device.

11. The computer-implemented method of claim 10, further comprising the step of:

d) sending information which limits view directions used in rendering said graphics information on said client computing device.

12. 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, and

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.

13. 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, and

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

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.

14. 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; and

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.

15. A computer-implemented method conducted on a server said method comprising:

storing information indicating a set of renderable graphics information visible from a first navigation cell, said first navigation cell contained in a second navigation cell, said renderable graphics information including mesh polygons forming at least one polygon mesh;

sending, to a client computing device, information indicating at least one seed polygon, said at least one seed polygon being a polygon visible from said second navigation cell; and

sending, to a client computing device, information indicating at least one encounter number, said encounter number being a number of iterations of a deterministic mesh traversal required to encounter at least one transitional edge, said deterministic mesh traversal starting at said seed polygon and traversing said at least one polygon mesh, and said transitional edge being an edge of said at least one polygon mesh and said transitional edge having at least one polygon sharing said transitional edge that is occluded from said first navigation cell.

17. The computer-implemented method of claim 15, wherein said at least one encounter number is represented by a run-length encoding format.

16. A computer-implemented method conducted on a client computing device, said method comprising:

receiving information from a server, said information indicating a set of renderable graphics information visible from a first navigation cell, said first navigation cell contained in a second navigation cell, said renderable graphics information including mesh polygons, said mesh polygons forming at least one polygon mesh;

receiving information indicating at least one seed polygon, said at least one seed polygon being a polygon visible from said first navigation cell;

receiving information indicating at least one encounter number, said encounter number being a number of edge-iterations of a deterministic mesh traversal required to encounter at least one transitional edge, said deterministic mesh traversal starting at said at least one seed polygon and traversing said at least one polygon mesh, and said transitional edge being an edge of said at least one polygon mesh and said transitional edge having at least one polygon sharing said transitional edge that is occluded from said first navigation cell;

conducting said deterministic mesh traversal, beginning at said at least one seed polygon; and

interrupting said deterministic mesh traversal at said at least one encounter number corresponding to said transitional edge.

18. A server comprising:

a memory to store information indicating a set of renderable graphics information visible from a first navigation cell, said first navigation cell contained in a second navigation cell, said renderable graphics information including mesh polygons forming at least one polygon mesh; and

a processor configured to;

send, to a client computing device, information indicating at least one seed polygon, said at least one seed polygon being a polygon visible from said second navigation cell, and

send, to a client computing device, information indicating at least one encounter number, said encounter number being a number of iterations of a deterministic mesh traversal required to encounter at least one transitional edge, said deterministic mesh traversal starting at said seed polygon and traversing said at least one polygon mesh, and said transitional edge being an edge of said at least one polygon mesh and said transitional edge having at least one polygon sharing said transitional edge that is occluded from said first navigation cell.

19. A client computing device comprising:

a processor configured to;

receive information from a server, said information indicating a set of renderable graphics information visible from a first navigation cell, said first navigation cell contained in a second navigation cell, said renderable graphics information including mesh polygons, said mesh polygons forming at least one polygon mesh,

receive information indicating at least one seed polygon, said at least one seed polygon being a polygon visible from said first navigation cell,

receive information indicating at least one encounter number, said encounter number being a number of edge-iterations of a deterministic mesh traversal required to encounter at least one transitional edge, said deterministic mesh traversal starting at said at least one seed polygon and traversing said at least one polygon mesh, and said transitional edge being an edge of said at least one polygon mesh and said transitional edge having at least one polygon sharing said transitional edge that is occluded from said first navigation cell,

conduct said deterministic mesh traversal, beginning at said at least one seed polygon, and

interrupt said deterministic mesh traversal at said at least one encounter number corresponding to said transitional edge.

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

storing information indicating a set of renderable graphics information visible from a first navigation cell, said first navigation cell contained in a second navigation cell, said renderable graphics information including mesh polygons forming at least one polygon mesh;

sending, to a client computing device, information indicating at least one seed polygon, said at least one seed polygon being a polygon visible from said second navigation cell; and

sending, to a client computing device, information indicating at least one encounter number, said encounter number being a number of iterations of a deterministic mesh traversal required to encounter at least one transitional edge, said deterministic mesh traversal starting at said seed polygon and traversing said at least one polygon mesh, and said transitional edge being an edge of said at least one polygon mesh and said transitional edge having at least one polygon sharing said transitional edge that is occluded from said first navigation cell.

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

receiving information from a server, said information indicating a set of renderable graphics information visible from a first navigation cell, said first navigation cell contained in a second navigation cell, said renderable graphics information including mesh polygons, said mesh polygons forming at least one polygon mesh;

receiving information indicating at least one seed polygon, said at least one seed polygon being a polygon visible from said first navigation cell;

receiving information indicating at least one encounter number, said encounter number being a number of edge-iterations of a deterministic mesh traversal required to encounter at least one transitional edge, said deterministic mesh traversal starting at said at least one seed polygon and traversing said at least one polygon mesh, and said transitional edge being an edge of said at least one polygon mesh and said transitional edge having at least one polygon sharing said transitional edge that is occluded from said first navigation cell;

conducting said deterministic mesh traversal, beginning at said at least one seed polygon; and

interrupting said deterministic mesh traversal at said at least one encounter number corresponding to said transitional edge.

22. A system comprising:

a server having a memory to store information indicating a set of renderable graphics information visible from a first navigation cell, said first navigation cell contained in a second navigation cell, said renderable graphics information including mesh polygons forming at least one polygon mesh,

the server further including a processor configured to;

send, to a client computing device, information indicating at least one seed polygon, said at least one seed polygon being a polygon visible from said second navigation cell, and

send, to a client computing device, information indicating at least one encounter number, said encounter number being a number of iterations of a deterministic mesh traversal required to encounter at least one transitional edge, said deterministic mesh traversal starting at said seed polygon and traversing said at least one polygon mesh, and said transitional edge being an edge of said at least one polygon mesh and said transitional edge having at least one polygon sharing said transitional edge that is occluded from said first navigation cell; and

a client computing device having a processor configured to;

receive said information indicating said set of renderable graphics information visible from said first navigation cell,

receive said information indicating said at least one seed polygon, said at least one seed polygon being a polygon visible from said first navigation cell,

receive information indicating said at least one encounter number,

conduct said deterministic mesh traversal, beginning at said at least one seed polygon, and

interrupt said deterministic mesh traversal at said at least one encounter number corresponding to said transitional edge.

23. A computer-implemented method, conducted on a server, said method comprising:

sending information to a client computing device, said information indicating a set of renderable graphics information representing at least one moving object included in a computer generated modeled environment;

determining a set of navigation cells including regions of the computer generated modeled environment in which the moving objects are permitted to traverse;

determining if said at least one moving object enters at least one of said navigation cells; and

sending said graphics information representing said at least one moving object entering said at least one of said navigation cells.

24. The computer-implemented method of claim 23, wherein the determined set of navigation cells are visible from a current client viewpoint.

25. The computer-implemented method of claim 23, wherein the determined set of navigation cells are visible from a predicted client viewpoint.

26. A system comprising:

a server having a processor configured to;

send information to a client computing device, said information indicating a set of renderable graphics information representing at least one moving object included in a computer generated modeled environment;

determine a set of navigation cells including regions of the computer generated modeled environment in which the moving objects are permitted to traverse;

determine if said at least one moving object enters at least one of said navigation cells, and

send said graphics information representing said at least one moving object entering said at least one of said navigation cells; and

a client computing device to receive and display said graphics information.

27. The system of claim 26, wherein the determined set of navigation cells are visible from a current client viewpoint.

28. The system of claim 26, wherein the determined set of navigation cells are visible from a predicted client viewpoint.

29. 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 comprising:

sending information to a client computing device, said information indicating a set of renderable graphics information representing at least one moving object included in a computer generated modeled environment;

determining a set of navigation cells including regions of the computer generated modeled environment in which the moving objects are permitted to traverse;

determining if said at least one moving object enters at least one of said navigation cells; and

sending said graphics information representing said at least one moving object entering said at least one of said navigation cells.

30. The non-transitory computer readable storage medium of claim 29, wherein the determined set of navigation cells are visible from a current client viewpoint.

31. The non-transitory computer readable storage medium of claim 29, wherein the determined set of navigation cells are visible from a predicted client viewpoint.

32. A computer-implemented method, conducted on a client computing device said method comprising:

receiving information from a server, said information indicating a set of renderable graphics information representing at least one moving object in a computer generated modeled environment;

receiving said graphics information representing said at least one moving object entering a navigation cell including a subset of a region of the computer generated modeled environment in which the at least one moving object is permitted to traverse.

33. The computer-implemented method of claim 32, wherein the navigation cell is visible from a current client viewpoint location.

34. The computer-implemented method of claim 32, wherein the navigation cell is visible from a predicted client viewpoint location.

35. A computer-implemented method, conducted on a client computing device, said method comprising:

receiving a first set of information from said server, said first set of information including parameters determining movement of at least one autonomous moving object;

receiving a second set of information from said server, said second set of information including information representing at least one navigation cell including a subset of a region of a computer generated modeled environment in which said at least one autonomous moving object is permitted to traverse;

determining if said at least one autonomous moving object enters said at least one navigation cell;

receiving, if said at least one autonomous moving object enters said at least one navigation cell, a third set of information from a server, said third set of information indicating a set of renderable graphics information representing said at least one autonomous moving object.

36. A client computing device comprising:

a processor configured to;

receive a first set of information from said server, said first set of information including parameters determining movement of at least one autonomous moving object,

receive a second set of information from said server, said second set of information including information representing at least one navigation cell including a subset of a region of a computer generated modeled environment in which said at least one autonomous moving object is permitted to traverse,

determine if said at least one autonomous moving object enters said at least one navigation cell, and

receive, if said at least one autonomous moving object enters said at least one navigation cell, a third set of information from a server, said third set of information indicating a set of renderable graphics information representing said at least one autonomous moving object.

37. A non-transitory computer readable storage medium having executable instructions stored thereon, which when executed by a processor in a client computing device, causes the processor to execute a method comprising:

receiving a first set of information from said server, said first set of information including parameters determining movement of at least one autonomous moving object;

receiving a second set of information from said server, said second set of information including information representing at least one navigation cell including a subset of a region of a computer generated modeled environment in which said at least one autonomous moving object is permitted to traverse;

determining if said at least one autonomous moving object enters said at least one navigation cell;

receiving, if said at least one autonomous moving object enters said at least one navigation cell, a third set of information from a server, said third set of information indicating a set of renderable graphics information representing said at least one autonomous moving object.

38. A computer-implemented method, conducted on a server, said method comprising:

storing information indicating at least one navigation cell that represents part of a navigable space of a computer generated modeled environment; and

sending said information representing said navigation cell to said client computing device upon determination that said at least one navigation cell is reachable via the navigable space from a predicted client viewpoint location.

39. A system comprising:

a server having a memory to store information indicating at least one navigation cell that represents part of a navigable space of a computer generated modeled environment;

the server further configured to send said information representing said navigation cell to said client computing device upon determination that said at least one navigation cell is reachable via the navigable space from a predicted client viewpoint location;

and a client computing device having a processor configured to determine a location in the navigable space using said information.

40. 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 comprising:

storing information indicating at least one navigation cell that represents part of a navigable space of a computer generated modeled environment; and

sending said information representing said navigation cell to said client computing device upon determination that said at least one navigation cell is reachable via the navigable space from a predicted client viewpoint location.

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

receiving information from a server, said information indicating at least one navigation cell that is reachable from a client viewpoint location, said navigation cell representing part of the navigable space of a computer generated modeled environment; and

determining a location in said navigable space using said received information.

42. The computer-implemented method according to claim 41, wherein said determined location is a future user viewpoint location.

43. The computer-implemented method according to claim 41, wherein said determined location is a future location of a moving object that is permitted to traverse through said navigable space.

44. A non-transitory computer readable storage medium having executable instructions stored thereon, which when executed by a processor in a client computing device causes the processor to execute a method comprising:

receiving information from a server, said information indicating at least one navigation cell that is reachable from a client viewpoint location, said navigation cell representing part of the navigable space of a computer generated modeled environment; and

determining a location in said navigable space using said received information.

45. The non-transitory computer readable storage medium according to claim 44, wherein said determined location is a future user viewpoint location.

46. The non-transitory computer readable storage medium according to claim 44, wherein said determined location is a future location of a moving object that is permitted to traverse through said navigable space.

47. A computer-implemented method, conducted on a client computing device, said method comprising:

receiving, from a server, information representing a second navigation cell and a first navigation cell each of which representing part of a navigable space of a computer generated modeled environment;

predicting a likelihood that a client-user viewpoint moves from said first navigation cell to said second navigation cell; and

receiving, from the server upon determination that the likelihood that said client-user viewpoint moves from said first navigation cell to said second navigation cell is greater than a predetermined threshold, a set of renderable graphics information visible from said second navigation cell and not visible from said first navigation cell.

48. A client computing device comprising:

a processor configured to;

receive, from a server, information representing a second navigation cell and a first navigation cell each of which representing part of a navigable space of a computer generated modeled environment,

predict a likelihood that a client-user viewpoint moves from said first navigation cell to said second navigation cell, and

receive, from the server upon determination that the likelihood that said client-user viewpoint moves from said first navigation cell to said second navigation cell is greater than a predetermined threshold, a set of renderable graphics information visible from said second navigation cell and not visible from said first navigation cell.

49. A non-transitory computer readable storage medium having executable instructions stored thereon, which when executed by a processor in a client computing device causes the processor to execute a method comprising:

receiving, from a server, information representing a second navigation cell and a first navigation cell each of which representing part of a navigable space of a computer generated modeled environment;

predicting a likelihood that a client-user viewpoint moves from said first navigation cell to said second navigation cell; and

receiving, from the server upon determination that the likelihood that said client-user viewpoint moves from said first navigation cell to said second navigation cell is greater than a predetermined threshold, a set of renderable graphics information visible from said second navigation cell and not visible from said first navigation cell.

53. The computer-implemented method according to claim 49, wherein said set of renderable graphics information includes a set of mesh polygons or fragments of said mesh polygons visible from said second navigation cell and not visible from said first navigation cell, said first and second navigation cells having a plurality of navigation cell vertices, said mesh polygons forming polygon meshes, said set of renderable graphics information determined from said mesh polygons or fragments of said mesh polygons visible from said second navigation cell, and said mesh polygons or fragments of said mesh polygons visible from said second navigation cell determined by steps of:

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

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 of said second navigation cell,

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

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

a2) determining at least one supporting polygon between said second navigation cell and said polygon meshes, said at least one supporting polygon being determined between said second navigation cell and at least one vertex of said at least one first-order silhouette edge;

c3) constructing at least one wedge from said at least one supporting polygon, said at least one wedge extending away from said second navigation cell beyond at least said polygon meshes;

c4) determining one or more intersections of said at least one wedge with said mesh polygons; and

c5) determining said set of said mesh polygons or fragments of said mesh polygons visible from said second navigation cell using said determined one or more intersections of said at least one wedge with said polygon meshes.

50. A computer-implemented method conducted on a server said method comprising:

sending navigation cell information to a client computing device, said navigation cell information including information representing a second navigation cell and a first navigation cell each of which representing part of a navigable space of a computer generated modeled environment;

receiving, from said client computing device, a request for a set of renderable graphics information including information visible from said second navigation cell and not visible from said first navigation cell, said request issued by said client computing device upon determination of a likelihood that a client-user viewpoint moves from said first navigation cell to said second navigation cell is greater than a predetermined threshold; and

sending, upon receiving said request from said client, said set of renderable graphics information.

54. The computer-implemented method according to claim 50, wherein said set of renderable graphics information includes a set of mesh polygons or fragments of said mesh polygons visible from said second navigation cell and not visible from said first navigation cell, said first and second navigation cells having a plurality of navigation cell vertices, said mesh polygons forming polygon meshes, said set of renderable graphics information determined from said mesh polygons or fragments of said mesh polygons visible from said second navigation cell, and said mesh polygons or fragments of said mesh polygons visible from said second navigation cell determined by steps of:

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

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 of said second navigation cell,

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

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

a2) determining at least one supporting polygon between said second navigation cell and said polygon meshes, said at least one supporting polygon being determined between said second navigation cell and at least one vertex of said at least one first-order silhouette edge;

c3) constructing at least one wedge from said at least one supporting polygon, said at least one wedge extending away from said second navigation cell beyond at least said polygon meshes;

c4) determining one or more intersections of said at least one wedge with said mesh polygons; and

c5) determining said set of said mesh polygons or fragments of said mesh polygons visible from said second navigation cell using said determined one or more intersections of said at least one wedge with said polygon meshes.

51. A system comprising:

a server having a processor configured to;

send navigation cell information to a client computing device, said navigation cell information including information representing a second navigation cell and a first navigation cell each of which representing part of a navigable space of a computer generated modeled environment; and

a client computing device having a processor configured to;

determine a likelihood that a client-user viewpoint moves from said first navigation cell to said second navigation cell is greater than a predetermined threshold, wherein

the server receives, from said client computing device, a request for a set of renderable graphics information including information visible from said second navigation cell and not visible from said first navigation cell upon determination that the likelihood is greater than a predetermined threshold, and

the server sends, upon receiving said request from said client, said set of renderable graphics information.

52. 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 comprising:

sending navigation cell information to a client computing device, said navigation cell information including information representing a second navigation cell and a first navigation cell each of which representing part of a navigable space of a computer generated modeled environment;

receiving, from said client computing device, a request for a set of renderable graphics information including information visible from said second navigation cell and not visible from said first navigation cell, said request issued by said client computing device upon determination of a likelihood that a client-user viewpoint moves from said first navigation cell to said second navigation cell is greater than a predetermined threshold; and

sending, upon receiving said request from said client, said set of renderable graphics information.

55. A computer-implemented method conducted on a server, said method comprising:

a) storing graphics information including a first set of graphics information visible from a second navigation cell and not visible from a first navigation cell, and a second set of graphics information visible from said second navigation cell and not visible from said first navigation cell, said second set of graphics information having a lower level-of-detail than said first set of graphics information, each of said first and second navigation cells representing part of a navigable space of a computer generated modeled environment;

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

c) determining a visual salience of said first set and said second set of graphics information, said visual salience representing a likelihood that the client computing device is tracking an object moving in said navigable space, said visual salience being a function of a current client viewpoint and one or more view direction vectors extending from said current client viewpoint;

d) sending said second set of graphics information during said first period upon determination that said visual salience of said first set and said second set of graphics information is below a predetermined value; and

e) sending said first set of graphics information upon determination that said visual salience is greater than or equal to said predetermined value.

56. A server comprising:

a memory to store graphics information including a first set of graphics information visible from a second navigation cell and not visible from a first navigation cell, and a second set of graphics information visible from said second navigation cell and not visible from said first navigation cell, said second set of graphics information having a lower level-of-detail than said first set of graphics information, each of said first and second navigation cells representing part of a navigable space of a computer generated modeled environment; and

a processor configured to;

determine a first period during which said first set of graphics information is determined to arrive after said client computing device is scheduled to access said first set of graphics information on said client computing device,

determine a visual salience of said first set and said second set of graphics information, said visual salience representing a likelihood that the client computing device is tracking an object moving in said navigable space, said visual salience being a function of a current client viewpoint and one or more view direction vectors extending from said current client viewpoint,

send said second set of graphics information during said first period upon determination that said visual salience of said first set and said second set of graphics information is below a predetermined value, and

send said first set of graphics information upon determination that said visual salience is greater than or equal to said predetermined value.

57. 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 comprising, said method comprising:

a) storing graphics information including a first set of graphics information visible from a second navigation cell and not visible from a first navigation cell, and a second set of graphics information visible from said second navigation cell and not visible from said first navigation cell, said second set of graphics information having a lower level-of-detail than said first set of graphics information, each of said first and second navigation cells representing part of a navigable space of a computer generated modeled environment;

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

c) determining a visual salience of said first set and said second set of graphics information, said visual salience representing a likelihood that the client computing device is tracking an object moving in said navigable space, said visual salience being a function of a current client viewpoint and one or more view direction vectors extending from said current client viewpoint;

d) sending said second set of graphics information during said first period upon determination that said visual salience of said first set and said second set of graphics information is below a predetermined value; and

e) sending said first set of graphics information upon determination that said visual salience is greater than or equal to said predetermined value.

58. A computer-implemented method, conducted on a client computing device, said method comprising:

a) determining a first period during which a first set of graphics information is determined to arrive after said client computing device is scheduled to access said first set of graphics information on said client computing device, said first set of graphics information visible from a second navigation cell and not visible from a first navigation cell, each of the first and second navigation cells representing part of a navigable space of a computer generated modeled environment;

b) receiving a second set of graphics information during said first period if a visual salience of said first set and said second set of graphics information is below a predetermined value, said visual salience being a function of current client viewpoint and view direction vectors, said visual salience representing a likelihood that said client computing device is tracking an object moving in said navigable space, said second set of graphics information visible from said second navigation cell and not visible from said first navigation cell, said second set of graphics information having a lower level-of-detail than said first set of graphics information; and

c) receiving said first set of graphics information upon determination that said visual salience is greater than or equal to said predetermined value.

59. A client computing device comprising:

a processor configured to;

determine a first period during which a first set of graphics information is determined to arrive after said client computing device is scheduled to access said first set of graphics information on said client computing device, said first set of graphics information visible from a second navigation cell and not visible from a first navigation cell, each of the first and second navigation cells representing part of a navigable space of a computer generated modeled environment,

receive a second set of graphics information during said first period if a visual salience of said first set and said second set of graphics information is below a predetermined value, said visual salience being a function of current client viewpoint and view direction vectors, said visual salience representing a likelihood that said client computing device is tracking an object moving in said navigable space, said second set of graphics information visible from said second navigation cell and not visible from said first navigation cell, said second set of graphics information having a lower level-of-detail than said first set of graphics information, and

receive said first set of graphics information upon determination that said visual salience is greater than or equal to said predetermined value.

60. A non-transitory computer readable storage medium having executable instructions stored thereon, which when executed by a processor in a client computing device causes the processor to execute a method comprising, said method comprising:

a) determining a first period during which a first set of graphics information is determined to arrive after said client computing device is scheduled to access said first set of graphics information on said client computing device, said first set of graphics information visible from a second navigation cell and not visible from a first navigation cell, each of the first and second navigation cells representing part of a navigable space of a computer generated modeled environment;

b) receiving a second set of graphics information during said first period if a visual salience of said first set and said second set of graphics information is below a predetermined value, said visual salience being a function of current client viewpoint and view direction vectors, said visual salience representing a likelihood that said client computing device is tracking an object moving in said navigable space, said second set of graphics information visible from said second navigation cell and not visible from said first navigation cell, said second set of graphics information having a lower level-of-detail than said first set of graphics information; and

c) receiving said first set of graphics information upon determination that said visual salience is greater than or equal to said predetermined value.