Systems and methods for rendering frames of complex virtual environments

• US 20030117398A1
• Filed: 12/21/2001
• Published: 06/26/2003
• Est. Priority Date: 12/21/2001
• Status: Abandoned Application

• Current Assignee: VRcontext International SA (Siemens AG)
• Original Assignee: VRcontext International SA (Siemens AG)
• Inventors: Hubrecht, Alain Yves Nestor, Nuydens, Tom
• Application Number:
  US10/023,818
• Publication Number:
  US 20030117398A1
• Time in Patent Office: Days
• US Class Current: 345/423
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 2210/12 Bounding box

Abstract

Systems and methods are disclosed for providing interactive displays of complex virtual environments. Systems and methods consistent with embodiments of the invention may be implemented to generate virtual reality (VR) file(s) from a 3D model of the complex environment. The VR file(s) may include octree and collision detection information that is used to simulate and render frames of the complex environment. During simulation, moving objects may be evaluated to detect for collisions with other objects. Further, during rendering, objects or elements may be dynamically tessellated during run-time operations to actively control their appearance when displayed to a user. Memory management operations for facilitating the display of complex virtual environments are also disclosed, consistent with embodiments of the invention.

Claims

1. A method for rendering frames of a complex virtual environment based on an octree file, the octree file including data defining an octree for the complex environment that includes spatially partitioned cells, the cells of the octree containing dynamic tessellation elements and non-dynamic tessellation elements, the method comprising:

determining, using the octree for the complex virtual environment, cells that are visible based on a viewer position for a frame to be rendered;

identifying, in each of the visible cells, dynamic tessellation elements; and

dynamically tessellating the identified dynamic tessellation elements in the visible cells, wherein dynamically tessellating the identified dynamic tessellation elements comprises;

determining, for each identified dynamic tessellation element, a tessellation level; and

rendering each identified dynamic tessellation element according to the determined tessellation level.

2. A method according to claim 1, wherein determining visible cells comprises:

determining a view frustum for the frame to be rendered based on the viewer position;

traversing the octree to identify non-visible cells that are outside of the view frustrum; and

culling the identified non-visible cells of the octree.

3. A method according to claim 2, wherein determining visible cells further comprises:

analyzing a list of occluder candidates to identify occluder candidates that are within the view frustum;

processing the occluder candidates that are within the view frustum to identify cells of the octree that are fully occluded by one or more occluder candidates; and

culling the identified cells that are fully occluded.

4. A method according to claim 3, wherein processing the occluder candidates comprises:

determining a quality metric for each of the occluder candidates that are within the view frustum;

sorting the occluder candidates in descending order in accordance with the determined quality metric for each occluder candidate; and

analyzing, over a predetermined time period, the sorted occluder candidates to identify cells that are fully occluded by the occluder candidates.

5. A method according to claim 4, wherein analyzing the sorted occluder candidates comprises:

determining if each of the sorted occluder candidates fully occludes cells that are within the view frustum; and

if an occluder candidate is determined to fully occluded one or more cells, culling each fully occluded cell.

6. A method according to claim 4, wherein analyzing the sorted occluder candidates comprises:

determining if each of the sorted occluder candidates partially occludes cells that are within the view frustum; and

if an occluder candidate is determined to partially occluded one or more cells, analyzing neighboring occluder candidates to determine if each partially occluded cell is fully occluded by a combination of occluder candidates.

7. A method according to claim 1, wherein the method further comprises:

estimating a screen size for each identified dynamic tessellation element;

determining if the estimated screen size is equal to or greater than a predetermined threshold; and

filtering dynamic tessellation elements that are determined to have an estimated threshold equal to or greater than the predetermined threshold so that only filtered dynamic tessellation elements are dynamically tessellated and displayed to a user.

8. A method according to claim 7, wherein estimating a screen size comprises estimating a screen size based on dynamic tessellation element types, the dynamic tessellation element types including at least one of a cone element type, a torus element type, and a surface-of-revolution element type.

9. A method according to claim 7, wherein determining a tessellation level comprises setting a tessellation level to zero for identified dynamic tessellation elements that have a screen size less than the predetermined threshold.

10. A method according to claim 1, wherein determining a tessellation level comprises determining a tessellation level based on one or more dynamic tessellation element types, the dynamic tessellation element types including a cone element type, a torus element type or a surface-of-revolution element type.

11. A method according to claim 10, wherein determining a tessellation level further comprises applying one or more predefined clamp levels to restrict a value of the determined tessellation level, wherein the clamp levels are predefined with respect to one or more dynamic tessellation element types.

12. A method according to claim 1, wherein rendering each identified element according to the determined tessellation level comprises:

determining the number of triangles for rendering each dynamic tessellation element based on the determined tessellation level; and

generating vertex data defining the determined number of triangles for rendering the dynamic tessellation element.

13. A method according to claim 12, wherein the method further comprises storing, in a buffer memory, the vertex data for rendered dynamic tessellation elements.

14. A method according to claim 1, wherein the method further comprises:

determining whether an identified dynamic tessellation element was rendered in a previous frame at a tessellation level that is the same as the determined tessellation level for the frame to be rendered; and

using stored vertex data of the previous rendering of the dynamic tessellation element at the same tessellation level to facilitate the display of the frame to be rendered.

15. A method for performing rendering operations for providing interactive displays a complex virtual environment, the rendering operations being performed as part of a simulation loop, the method comprising:

determining, using an octree of cells for the complex virtual environment, cells that are visible based on a viewer position for a frame to be rendered, the cells of the octree containing elements of the complex environment;

identifying, in each of the visible cells, dynamic tessellation elements; and

dynamically tessellating the identified dynamic tessellation elements in the visible cells, wherein determining visible cells based on the viewer position comprises;

determining a view frustum for the frame to be rendered based on the viewer position;

traversing the octree to identify non-visible cells that are outside of the view frustum; and

culling the identified non-visible cells of the octree.

16. A method according to claim 15, wherein dynamically tessellating the identified dynamic tessellation elements comprises:

determining, for each identified dynamic tessellation element, a tessellation level; and

rendering each identified dynamic tessellation element according to the determined tessellation level.

17. A method according to claim 16, wherein the method further comprises:

estimating a screen size for each identified dynamic tessellation element;

determining if the estimated screen size is equal to or greater than a predetermined threshold; and

filtering dynamic tessellation elements that are determined to have an estimated threshold equal to or greater than the predetermined threshold so that only filtered dynamic tessellation elements are dynamically tessellated and displayed to a user.

18. A method according to claim 17, wherein estimating a screen size comprises estimating a screen size based on dynamic tessellation element types, the dynamic tessellation element types including at least one of a cone element type, a torus element type, and a surface-of-revolution element type.

19. A method according to claim 17, wherein determining a tessellation level comprises setting a tessellation level to zero for identified dynamic tessellation elements that have a screen size less than the predetermined threshold.

20. A method according to claim 16, wherein determining a tessellation level comprises determining a tessellation level based on one or more dynamic tessellation element types, the dynamic tessellation element types including a cone element type, a torus element type or a surface-of-revolution element type.

21. A method according to claim 20, wherein determining a tessellation level further comprises applying one or more predefined clamp levels to restrict a value of the determined tessellation level, wherein the predefined clamp levels are predefined with respect to the dynamic tessellation element types.

22. A method according to claim 16, wherein rendering each identified element according to the determined tessellation level comprises:

determining the number of triangles for rendering each dynamic tessellation element based on the determined tessellation level; and

generating vertex data defining the determined number of triangles for rendering the dynamic tessellation element.

23. A method according to claim 22, wherein the method further comprises storing, in a buffer memory, the vertex data for rendered dynamic tessellation elements.

24. A method according to claim 16, wherein the method further comprises:

determining whether an identified dynamic tessellation element was rendered in a previous frame at a tessellation level that is the same as the determined tessellation level for the frame to be rendered; and

using stored vertex data for the previous rendering of the dynamic tessellation element at the same tessellation level to facilitate the display of the frame to be rendered.

25. A method according to claim 15, wherein determining visible cells further comprises:

analyzing a list of occluder candidates to identify occluder candidates that are within the view frustum;

processing the occluder candidates that are within the view frustum to identify cells of the octree that are fully occluded by one or more occluder candidates; and

culling the identified cells that are fully occluded.

26. A method according to claim 25, wherein processing the occluder candidates comprises:

determining a quality metric for each of the occluder candidates that are within the view frustum;

sorting the occluder candidates in accordance with the determined quality metric for each occluded candidate;

analyzing, over a predetermined time period, the sorted occluder candidates to identify cells that are fully occluded by the occluder candidates.

27. A method according to claim 26, wherein analyzing the sorted occluder candidates comprises:

determining if each of the sorted occluder candidates fully occludes cells that are within the view frustum; and

if an occluder candidate is determined to fully occluded one or more cells, culling each fully occluded cell.

28. A method according to claim 26, wherein analyzing the sorted occluder candidates comprises:

determining if each of the sorted occluder candidates partially occludes cells that are within the view frustum; and

if an occluder candidate is determined to partially occluded one or more cells, analyzing neighboring occluder candidates to determine if each partially occluded cell is fully occluded by a combination of occluder candidates.

29. A computer program product for providing interactive displays of a complex virtual environment, the computer program product comprising a computer readable medium embodying a computer program, the computer program comprising instructions that are executable by a system to perform a rendering method to facilitate the display of frames of the complex environment, the method comprising:

determining, using an octree of cells that spatially partition the complex virtual environment, elements of the complex environment that are visible based on a viewer position for a frame to be rendered, the elements of the complex environment including dynamic tessellation elements and non-dynamic tessellation elements; and

for each of visible element that is a dynamic tessellation element, dynamically tessellating the element by;

determining a tessellation level for the visible dynamic tessellation element based on the viewer position for the frame to be rendered; and

generating vertex data for rendering the visible dynamic tessellation element based on the determined tessellation level.

30. A computer program product according to claim 29, wherein cells of the octree contain one or more elements of the complex environment and further wherein determining visible elements comprises:

determining a view frustum for the frame to be rendered based on the viewer position;

traversing the octree to identify non-visible cells that are outside of the view frustrum; and

culling the identified non-visible cells of the octree.

31. A computer program product according to claim 30, wherein determining visible elements further comprises:

analyzing a list of occluder candidates to identify occluder candidates that are within the view frustum;

processing the occluder candidates that are within the view frustum to identify cells of the octree that are fully occluded by one or more occluded candidates; and

culling the identified cells that are fully occluded.

32. A computer program product according to claim 31, wherein processing the occluder candidates comprises:

determining a quality metric for each of the occluder candidates that are within the view frustum;

sorting the occluder candidates in accordance with the determined quality metric for each occluder candidate;

analyzing, over a predetermined time period, the sorted occluder candidates to identify cells that are fully occluded by the occluder candidates.

33. A computer program product according to claim 32, wherein analyzing the sorted occluder candidates comprises:

determining if each of the sorted occluder candidates fully occludes cells that are within the view frustum; and

if an occluder candidate is determined to fully occluded one or more cells, culling each fully occluded cell.

34. A computer program product according to claim 32, wherein analyzing the sorted occluder candidates comprises:

determining if each of the sorted occluder candidates partially occludes cells that are within the view frustum; and

if an occluder candidate is determined to partially occluded one or more cells, analyzing neighboring occluder candidates to determine if each partially occluded cell is fully occluded by a combination of occluder candidates.

35. A computer program product according to claim 29, wherein the method further comprises:

estimating a screen size for each identified dynamic tessellation element;

determining if the estimated screen size is equal to or greater than a predetermined threshold; and

filtering dynamic tessellation elements that are determined to have an estimated threshold equal to or greater than the predetermined threshold so that only filtered dynamic tessellation elements are dynamically tessellated and displayed to a user.

36. A computer program product according to claim 35, wherein determining a tessellation level comprises setting a tessellation level to zero for identified dynamic tessellation elements that have a screen size less than the predetermined threshold.

37. A computer program product according to claim 29, wherein generating vertex data for rendering visible dynamic tessellation elements comprises:

determining the number of triangles for rendering each dynamic tessellation element based on the determined tessellation level; and

generating vertex data defining the determined number of triangles for rendering the dynamic tessellation element.

38. A computer program product according to claim 29, wherein the method further comprises storing, in a buffer memory, the vertex data for rendered dynamic tessellation elements.

39. A computer program product according to claim 29, wherein the method further comprises:

determining whether a visible dynamic tessellation element was rendered in a previous frame at a tessellation level that is the same as the determined tessellation level for the frame to be rendered; and

using stored vertex data of the previous rendering of the dynamic tessellation element at the same tessellation level to facilitate the display of the frame to be rendered.

40. In a system for providing interactive displays of a complex virtual environment, a graphics system for rendering frames based on virtual reality (VR) file(s), the VR file(s) including data defining a list of occluder candidates and an octree of cells that contain one or more elements of the complex environment, the graphics system comprising:

means for determining, using the octree for the complex virtual environment, cells that are not visible based on a viewer position for a frame to be rendered;

means for culling all cells of the octree that are determined not to be visible;

means for analyzing the list of occluder candidates to determine cells of the octree that are occluded based on the viewer position;

means for culling all cells of the octree that are determined to be occluded; and

means for rendering elements contained in the visible, non-culled cells of the octree to facilitate the display the frame to a user.

41. A system according to claim 40, wherein the graphics system further comprises:

means for identifying, in each of the visible cells of the octree, dynamic tessellation elements;

means for determining, for each identified dynamic tessellation element, a tessellation level; and

means for generating vertex data for rendering each identified dynamic tessellation element with a level of detail consistent with the determined tessellation level.

42. A system according to claim 41, wherein the means for generating vertex data comprises:

means for determining the number of triangles for rendering each dynamic tessellation element based on the determined tessellation level; and

means for generating vertex data defining the determined number of triangles for rendering the dynamic tessellation element.

43. A system according to claim 41, wherein the system further comprises means for storing, in a buffer memory, the vertex data for rendered dynamic tessellation elements.

44. A system according to claim 41, wherein the graphics system further comprises:

means for determining whether a visible dynamic tessellation element was rendered in a previous frame at a tessellation level that is the same as the determined tessellation level for the frame to be rendered; and

means for using stored vertex data of the previous rendering of the dynamic tessellation element at the same tessellation level to facilitate the display of the frame to be rendered.

45. A system according to claim 41, wherein the graphics system further comprises:

means for estimating a screen size for each identified dynamic tessellation element;

means for determining if the estimated screen size is equal to or greater than a predetermined threshold; and

means for filtering dynamic tessellation elements that are determined to have an estimated threshold equal to or greater than the predetermined threshold so that only filtered dynamic tessellation elements are dynamically tessellated and displayed to a user.

46. A system according to claim 45, wherein the means for determining a tessellation level comprises means for setting a tessellation level to zero for identified dynamic tessellation elements that have a screen size less than the predetermined threshold.

47. A system according to claim 40, wherein the means for analyzing the list of occluder candidates comprises:

means for determining a quality metric for each occluder candidate that is contained within a visible cell;

means for sorting the occluder candidates according to the determined quality metric for each occluder candidate; and

means for analyzing, over a predetermined time period, each of the sorted occluder candidates to detect cells that are fully occluded in the frame to be rendered.

48. A system according to claim 40, wherein the means for determining cells that are not visible comprises:

means for determining a view frustum for the frame to be rendered based on the viewer position; and

means for traversing the octree to identify non-visible cells that are outside of the view frustum.

49. A method for rendering frames of a complex virtual environment based on an octree of cells that spatially partition the complex virtual environment, the cells of the octree containing one or more elements of the complex environment, the method comprising:

determining, using the octree for the complex virtual environment, cells that are not visible based on a viewer position for the frame to be rendered;

culling all cells of the octree that are determined not to be visible;

analyzing a list of occluder candidates to determine cells of the octree that are occluded based on the viewer position;

culling all cells of the octree that are determined to be occluded; and

rendering elements contained in visible cells of the octree to display the frame to a user, wherein the elements contained in the visible cells include dynamic tessellation elements and non-dynamic tessellation elements.

50. A method according to claim 49, further comprising:

identifying, in each visible cell of the octree, dynamic tessellation elements;

determining, for each identified dynamic tessellation element, a tessellation level; and

rendering each identified element with a level of detail corresponding to the determined tessellation level.

51. A method according to claim 50, wherein rendering each identified dynamic tessellation element comprises:

determining the number of triangles for rendering a dynamic tessellation element based on the determined tessellation level; and

generating vertex data defining the determined number of triangles for rendering the dynamic tessellation element.

52. A method according to claim 51, wherein the method further comprises storing, in a buffer memory, the vertex data for rendered dynamic tessellation elements.

53. A method according to claim 50, wherein the method further comprises:

determining whether a visible dynamic tessellation element was rendered in a previous frame at a tessellation level that is the same as the determined tessellation level for the frame to be rendered; and

using stored vertex data of the previous rendering of the dynamic tessellation element at the same tessellation level to facilitate the display of the frame to be rendered.

54. A method according to claim 50, wherein the method further comprises:

estimating a screen size for each identified dynamic tessellation element;

determining if the estimated screen size is equal to or greater than a predetermined threshold; and

filtering dynamic tessellation elements that are determined to have an estimated threshold equal to or greater than the predetermined threshold so that only filtered dynamic tessellation elements are dynamically tessellated and displayed to a user.

55. A method according to claim 54, wherein determining a tessellation level comprises setting a tessellation level to zero for identified dynamic tessellation elements that have a screen size less than the predetermined threshold.

56. A method according to claim 49, wherein analyzing a list of occluder candidates comprises:

determining a quality metric for each occluder candidate that is contained within a visible cell

sorting the occluder candidates according to the determined quality metric for each occluder candidate;

analyzing, over a predetermined time period, each of the sorted occluder candidates to detect cells that are fully occluded in the frame to be rendered.