Systems and methods for simulating frames of complex virtual environments

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

What is claimed is:

1. A method for performing simulation to facilitate the rendering of frames of a complex virtual environment, the method comprising:

detecting, for a next frame to be rendered, input from a user;

determining, based on the user input, desired movements from a current position to a desired position within the complex virtual environment;

accessing a collision detection hierarchy from virtual reality files that is used during said simulation for collision detection, said virtual reality files also including an octree of elements that is used during said rendering;

performing, using said collision detection hierarchy that contain one or more elements of the complex environment, a predictive collision detection operation to determine if a collision will occur with an element represented in the complex environment if the desired movements are preformed between the current position and the desired position;

if a collision is detected, calculating an adjusted position based on the desired movements in the complex environment and setting a viewer position for rendering the next frame to the adjusted position; and

if a collision is not detected, setting a viewer position for rendering the next frame to the desired position.

2. A method according to claim 1, wherein determining desired movements comprises calculating a path between the current position and the desired position based on the user input.

3. A method according to claim 2, wherein performing a predictive collision detection operation comprises:

identifying bounding boxes of the collision detection hierarchy that intersect with the desired movements based on the calculated path between the current position and the desired position; and

analyzing elements contained in each identified bounding box to determine if a collision will occur if the desired movements are performed.

4. A method according to claim 3, wherein the user is represented by an avatar in the complex virtual environment and movements of the avatar in rendered frames of the complex environment are controlled based on movements indicated by the user input.

5. A method according to claim 4, wherein the method further comprises approximating the avatar with a bounding volume, and wherein identifying intersecting bounding boxes comprises detecting bounding boxes that intersect with the bounding volume of the avatar when the bounding volume is moved between the current position and the desired position.

6. A method according to claim 4, wherein analyzing elements to determine if a collision will occur comprises detecting elements in each identified bounding box that intersect with the bounding volume of the avatar when the bounding volume is moved between the current position and the desired position.

7. A method according to claim 6, wherein calculating an adjusted position comprises:

determining a position of the avatar at the earliest point of contact with an intersecting element represented in the complex virtual environment; and

performing a sliding motion operation from the position of to earliest point of contact to determine an adjusted position of the avatar.

8. A method according to claim 7, wherein performing a sliding motion operation comprises:

calculating a tangent plane at the position of the earliest point of contact with respect to the bounding volume of the avatar;

projecting the desired position of the avatar onto the tangent plane; and

setting an adjusted position for the avatar at approximately the projected point of the desired position on the tangent plane.

9. A method according to claim 6, wherein calculating an adjusted position comprises;

determining a position of the avatar at the earliest point of contact with an element represented in the complex virtual environment; and

setting an adjusted position for the avatar at approximately the position of the earliest point of contact.

10. A method according to claim 3, wherein a moving object is represented in the complex virtual environment and movements of the moving object in rendered frames of the complex environment are controlled based on movements indicated by the user input.

11. A method according to claim 10, wherein the method further comprises approximating the moving object with a bounding volume, and further wherein identifying intersecting bounding boxes comprises detecting bounding boxes that intersect with the bounding volume of the moving object when the bounding volume is moved between the current position and the desired position.

12. A method according to claim 10, wherein analyzing elements to determine if a collision will occur comprises detecting elements in each identified bounding box that intersect with the bounding volume of the moving object when the bounding volume is moved between the current position and the desired position.

13. A method according to claim 12, wherein calculating an adjusted position comprises:

determining a position of the moving object at the earliest point of contact with an intersecting element represented in the complex virtual environment; and

setting an adjusted position for the moving object at approximately the position of the earliest point of contact.

14. A method according to claim 1, wherein the virtual reality file(s) being generated from a three-dimensional (3D) model of the complex virtual environment.

15. A method according to claim 14, wherein the 3D model is a massive model.

16. A method for performing simulation operations to facilitate the rendering of frames of a complex virtual environment, the simulation operations being performed as part of a simulation loop to provide interactive displays of the complex environment to a user, the method comprising:

detecting, for a next frame to be rendered, input from a user;

determining, based on the user input, desired movements from a current position to a desired position within the complex virtual environment;

accessing a collision detection hierarchy from virtual reality files that is used during said simulation for collision detection, said virtual reality files also including an octree of elements that is used during said rendering;

predicting, using said collision detection hierarchy of bounding boxes that contain one or more elements of the complex environment, whether a collision will occur with an element in the complex environment based on the desired movements between the current position and the desired position; and

calculating an adjusted position for rendering the next frame in response to the detection of a collision,

wherein determining desired movements based on the user input comprises calculating a path between the current position and the desired position based on the user input, and

further wherein predicting whether a collision will occur comprises:

performing a proximity query based on the calculated path between the current position and the desired position to identify intersecting bounding boxes; and

analyzing elements contained in each identified bounding box to determine if a collision will occur based on the desired movements.

17. A method according to claim 16, wherein the method further comprises setting a viewer position for rendering the next frame to the desired position if a collision is not detected.

18. A method according to claim 16, wherein the method further comprises setting a viewer position for rendering the next frame to the adjusted position if a collision is detected.

19. A method according to claim 16, wherein the user is represented by an avatar in the complex virtual environment and movements of the avatar in rendered frames of the complex environment are controlled based on desired movements indicated by the user input.

20. A method according to claim 19, wherein the method further comprises approximating the avatar with a bounding volume, and further wherein performing a proximity query comprises detecting bounding boxes that intersect with the bounding volume of the avatar when the bounding volume is moved between the current position and the desired position.

21. A method according to claim 19, wherein analyzing elements to determine if a collision will occur comprises detecting elements in each identified bounding box that intersect with the bounding volume of the avatar when the bounding volume is moved between the current position and the desired position.

22. A method according to claim 21, wherein calculating an adjusted position comprises:

determining a position of the avatar at the earliest point of contact with an intersecting element represented in the complex virtual environment; and

performing a sliding motion operation from the position of the earliest point of contact to determine an adjusted position of the avatar.

23. A method according to claim 22, wherein performing a sliding motion operation comprises:

calculating a tangent plane at the position of the earliest point of contact with respect to the bounding volume of the avatar;

projecting the desired position of the avatar onto the tangent plane; and

setting an adjusted position for the avatar at approximately the projected point of the desired position on the tangent plane.

24. A method according to claim 21, wherein calculating an adjusted position comprises:

determining a position of the avatar at the earliest point of contact with an element represented in the complex virtual environment; and

setting an adjusted position for the avatar at approximately the position of the earliest point of contact.

25. A method according to claim 16, wherein a moving object is represented in the complex virtual environment and movements of the moving object in rendered frames of the complex environment are controlled based on movements indicated by the user input.

26. A method according to claim 25, wherein the method further comprises approximating the moving object with a bounding volume, and further wherein performing a proximity query comprises detecting bounding boxes that intersect with the bounding volume of the moving object when the bounding volume is moved between the current position and the desired position.

27. A method according to claim 25, wherein analyzing elements to determine if a collision will occur comprises detecting elements in each identified bounding box that intersect with the bounding volume of the moving object when the bounding volume is moved between the current position and the desired position.

28. A method according to claim 27, wherein calculating an adjusted position comprises:

determining a position of the moving object at the earliest point-of-contact with an intersecting element represented in the complex virtual environment; and

setting an adjusted position for the moving object at approximately the position of the earliest point of contact.

29. A method according to claim 16, wherein the virtual reality file(s) being generated from a three-dimensional (3D) model of the complex virtual environment.

30. A method according to claim 29, wherein the 3D model is a massive model.

31. 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 simulation method to facilitate the rendering of frames of the complex environment, the method comprising:

determining, based on user input for a frame to be rendered, desired movements from a current position to a desired position within the complex virtual environment;

accessing a collision detection hierarchy from virtual reality files that is used during said simulation for collision detection, said virtual reality files being generated from a three-dimensional (3D) model of said complex virtual environment and including an octree of elements that is used during said rendering;

performing, using said collision detection hierarchy that contain one or more elements of the complex environment, a predictive collision detection operation to determine if a collision will occur with an element represented in the complex environment if the desired movements are performed between the current position and the desired position; and

in response to performing the collision detection operation, setting a viewer position for the frame to be rendered.

32. A computer program product according to claim 31, wherein the method further comprises:

if a collision is detected, calculating an adjusted position based on the desired movements in the complex environment and setting the viewer position for rendering the next frame to the adjusted position; and

if a collision is not detected, setting the viewer position for rendering the next frame to the desired position.

33. A computer program product according to claim 31, wherein determining desired movements based on the user input comprises calculating a path between the current position and the desired position based on the user input.

34. A computer program product according to claim 33, wherein performing the predictive collision detection operation comprises:

performing a proximity query based on the calculated path between the current position and the desired position to identify intersecting bounding boxes, and

analyzing elements contained in each identified bounding box to determine if a collision will occur based on the desired movements.

35. A computer program product according to claim 34, wherein the user is represented by an avatar in the complex virtual environment and movements of the avatar in rendered frames of the complex environment are controlled based on movements indicated by the user input.

36. A computer program product according to claim 35, wherein the method further comprises approximating the avatar with a bounding volume, and further wherein performing a proximity query comprises detecting bounding boxes that intersect with the bounding volume of the avatar when the bounding volume is moved between the current position and the desired position.

37. A computer program product according to claim 36, wherein analyzing elements to determine if a collision will occur comprises detecting elements in each identified bounding box that intersect with the bounding volume of the avatar when the bounding volume is moved between the current position and the desired position.

38. A computer program product according to claim 37, wherein the method further comprises:

if a collision is detected, calculating an adjusted position based on the desired movements in the complex environment and setting the viewer position to the adjusted position for rendering the next frame.

39. A computer program product according to claim 38, wherein calculating an adjusted position comprises:

determining a position of the avatar at the earliest point of contact with an intersecting element represented in the complex virtual environment; and

performing a sliding motion operation from the position of the earliest point of contact to determine an adjusted position of the avatar.

40. A computer program product according to claim 39, wherein performing a sliding motion operation comprises;

calculating a tangent plane at the position of the earliest point of contact with respect to the bounding volume of the avatar;

projecting the desired position of the avatar onto the tangent plane; and

setting an adjusted position for the avatar at approximately the projected point of the desired position on the tangent plane.

41. A computer program product according to claim 38, wherein calculating an adjusted position comprises:

determining a position of the avatar at the earliest point of contact with an element represented in the complex virtual environment; and

setting an adjusted position for the avatar at approximately the position of the earliest point of contact.

42. A computer program product according to claim 34, wherein a moving object is represented in the complex virtual environment and movements of the moving object in rendered frames of the complex environment are controlled based on desired movements indicated by the user input.

43. A computer program product according to claim 42, wherein the method further comprises approximating the moving object with a bounding volume, and further wherein performing a proximity query comprises detecting bounding boxes that intersect with the bounding volume of the moving object when the bounding volume is moved between the current position and the desired position.

44. A computer program product according to claim 42, wherein analyzing elements to determine if a collision will occur comprises detecting elements in each identified bounding box that intersect with the bounding volume of the moving object when the bounding volume is moved between the current position and the desired position.

45. A computer program product according to claim 44, wherein the method further comprises:

if a collision is detected, calculating an adjusted position based on the desired movements in the complex environment and setting the viewer position to the adjusted position for rendering the next frame.

46. A computer program product according to claim 45, wherein calculating an adjusted position comprises;

determining a position of the moving object at the earliest point of contact with an intersecting element represented in the complex virtual environment; and

setting an adjusted position for the moving object at approximately the position of the earliest point of contact.

47. In a system for providing interactive displays of a complex virtual environment, a simulation component for performing simulations based on virtual reality (VR) file(s), the VR file(s) including a collision detection hierarchy used during said simulation for collision detection that contains elements represented in the complex environment, said VR file(s) also including an octree of elements that is used during said rendering, the simulation component comprising:

means for determining, based on input from a user, desired movements from a current position to a desired position within the complex virtual environment;

means for demoting, using the collision detection hierarchy, whether a collision will occur with an element represented in the complex virtual environment based on the desired movements from the current position to the desired position; and

means for calculating an adjusted position when it is determined that a collision will occur based on the desired movements indicated by the user input.

48. In a system according to claim 47, wherein the simulation component further comprises:

means for setting a viewer position for rendering a frame to the adjusted position if a collision is detected; and

means for setting a viewer position for rendering a frame to the desired position if a collision is not detected.

49. In a system according to claim 47, wherein the means for detecting whether a collision will occur comprises:

means for performing a proximity query to identify intersecting bounding boxes when simulating the desired movements between the current position and the desired position; and

means for analyzing elements contained in each identified bounding box to determine if a collision will occur based on the desired movements.

50. In a system according to claim 49, wherein the user is represented by an avatar in the complex virtual environment and movements of the avatar in rendered frames of the complex environment are controlled based on desired movements indicated by the user input.

51. In a system according to claim 50, wherein the simulation component further comprises means for approximating the avatar with a bounding volume, and further wherein the means for performing a proximity query comprises means for detecting bounding boxes that intersect with the bounding volume of the avatar when the bounding volume is moved between the current position and the desired position.

52. In a system according to claim 50, wherein the means for analyzing elements to determine if a collision will occur comprises means for detecting elements in each identified bonding box that intersect with the bounding volume of the avatar when the bounding volume is moved between the current position and the desired position.

53. In a system according to claim 52, wherein the means for calculating an adjusted position comprises:

means for determining a position of the avatar at the earliest point of contact with an intersecting element represented in the complex virtual environment; and

means for performing a sliding motion operation from the position of the earliest point of contact to determine an adjusted position of the avatar.

54. In a system according to claim 53, wherein means for performing a sliding motion operation comprises:

means for calculating a tangent plane at the position of the earliest point of contact with respect to the bounding volume of the avatar;

means for projecting the desired position of the avatar onto the tangent plane; and

means for setting an adjusted position for the avatar at approximately the projected point of the desired position on the tangent plane.

55. In a system according to claim 52, wherein the means for calculating an adjusted position comprises:

means for determining a position of the avatar at the earliest point of contact with an element represented in the complex virtual environment; and

means for setting an adjusted position for the avatar at approximately the position of the earliest point of contact.

56. In a system according to claim 47, further comprising a graphics system, the graphics system being adapted render frames of the complex virtual environment based on the results of the simulations performed by the simulation component.

57. in a system according to claim 47, further comprising means for generating the VR file(s) based on a three dimensional (3D) model of the complex virtual environment.

58. A method for simulating movement of an avatar in a complex virtual environment, the method comprising:

determining, based on input from a user, desired movements of the avatar from a current position to a desired position within the complex virtual environment; and

accessing a collision detection hierarchy from virtual reality files that is used during said simulation for collision detection, said virtual reality files being generated from a three-dimensional (3D) model of said complex virtual environment and including an octree of elements that is used during said rendering;

detecting, using said collision detection hierarchy, whether a collision will occur with an element represented in the complex virtual environment if the avatar is moved from the current position to the desired position, wherein detecting includes:

performing a proximity query based on the desired movements of the avatar to identify bounding boxes that intersect with the avatar when the avatar is moved to the desired position; and

analyzing elements contained in each identified bounding box to determine if a collision will occur with the avatar.

59. A method according to claim 58, wherein the method further comprises:

determining, in response to the detection of a collision, an adjusted position for the avatar in the complex virtual environment.

60. A method according to claim 59, wherein determining an adjusted position comprises:

determining a position of the avatar at the earliest point of contact with an intersecting element represented in the complex virtual environment;

calculating a tangent plane at the point of contact with respect to a bounding volume for the avatar;

projecting the desired position of the avatar onto the tangent plane; and

setting an adjusted position for the avatar at approximately the projected point of the desired position on the tangent plane.

61. A method according to claim 59, wherein the method further comprises:

setting a viewer position for rendering a frame to the adjusted position when a collision is detected.

62. A method according to claim 58, wherein the method further comprises:

setting a viewer position for rendering a frame to the desired position if a collision is not detected.

Description

COMPUTER PROGRAM LISTING APPENDIX

A compact disc is submitted with this application that contains an appendix of computer program listings; the contents of the compact disc are hereby incorporated by reference. The disc was created on Apr. 16, 2004 and includes a file entitled "Appendix.txt" having a size of 18 KB bytes. A duplicate disc is also submitted.

BACKGROUND OF THE INVENTION

I. Field of the Invention

The present invention generally relates to the fields of computer graphics and virtual reality. More particularly, the present invention relates to systems and methods for simulating frames of complex virtual environments, including complex virtual environments based on massive models.

II. Background Information

As a result of the advances in computer graphics and computer-aided design (CAD), a wide variety of objects and environments can be modeled and rendered with technical detail and precision. For example, 2D and 3D modeling techniques permit engineering models of mechanical parts and other physical objects to be computer generated for various purposes, such as research and development. In addition, complex environments involving offshore platforms, industrial plants, building complexes and other facilities can be modeled using conventional, computer-aided modeling methods. 3D models of such environments are often used in the architecture, engineering and construction (AEC) sectors and for plant design.

Elements or objects in a complex environment may be represented in a 3D model through polygons. Polygons (such as triangles and quadrilaterals) are closed figures made by joining line segments, wherein each line segment intersects exactly two other line segments. In a 3D model, polygons may be combined to represent the surface(s) of boxes, stairs, windows, walls, floors, pipes, beams and other objects in the modeled environment. Data defining the attributes of each object, including lighting and texture, may also be included in a 3D model.

To render 3D models, conventional graphics systems may be employed. Such graphics systems may be provided with graphics cards that are capable of processing 3D model data to generate and display the modeled environment. While triangle elements can be directly handled and rendered by most graphics cards, other polygon elements in a 3D model (such as four or five-sided polygons) require additional processing before they can be rendered. Such processing may include the triangulation of complex polygon elements into triangles so that it can be directly handled by the graphics hardware and rendered on a display terminal.

With the developments in computer-aided graphics and 3D modeling, there has been an increasing demand for interactive displays and simulation to provide virtual reality. The term virtual reality refers to the use of computer-based simulation of real or imaginary environments that permit a user to perform operations within the simulated environment. In the area of 3D game technology, virtual reality software has been created to provide real-time animation within simulated environments for users. To achieve higher levels of realism, many 3D software games permit users to navigate and/or perform operations (such as lifting, walking, running, jumping, climbing, etc.) in a manner that resembles the real world. For this purpose, the effects of gravity and/or other real-world phenomena (such as collisions) may be simulated in virtual reality applications for 3D game users.

Presently, the ability to provide interactive displays and real-time simulation for complex environments presents many challenges. For example, complex environments can be based on 3D models that are comprised of data representing hundreds of thousands of polygons. Although the throughput of graphics systems has improved over the years, rendering complex environments at interactive frame rates (such as 5 frames/second or higher) is impossible with current applications due to the volume of data that must be processed. For instance, attempts to render complex environments represented by approximately 700,000 or more polygons with current systems will typically cause the screen to freeze or lock when a user tries to navigate through the rendered model.

To overcome such obstacles, some applications eliminate real-world phenomena (such as the effect of gravity and/or collisions) to provide simple navigation features in a complex virtual environment. In such applications, however, the user is often left in a confused state since the user is permitted to navigate through walls, floors and other objects represented in the modeled environment. Further, in some cases, the viewpoint of the user may be positioned within walls or between floors, making it difficult for the user to orientate himself/herself with respect to the rendered frame.

Other applications attempt to provide real-time simulation by reducing the level of detail in the rendered frame and/or eliminating the range of interactive options available to a user. In such applications, however, curved surfaces may appear jagged as opposed to smooth. Further, the user may be limited to basic movements (such as forward, left, right, etc.) that are not practical for most applications. Therefore, while such approaches may improve the frame rate, they fail to provide an acceptable level of visualization and simulation to the user. As a result, past attempts do not provide an effective virtual reality solution for complex environments.

SUMMARY OF THE INVENTION

In accordance with embodiments of the invention, a method is provided for performing simulation to facilitate the rendering of frames of a complex virtual environment. Te method comprises: detecting, for a next frame to be rendered, input from a user; determining, based on the user input, desired movements from a current position to a desired position within the complex virtual environment; and performing, using a collision detection hierarchy of bounding boxes that contain one or more elements of the complex environment, a predictive collision detection operation to determine if a collision will occur with an element represented in the complex environment if the desired movements are performed between the current position and the desired position. If a collision is detected, an adjusted position may be calculated based on the desired movements in the complex environment and a viewer position for rendering the next frame may be set to the adjusted position. Further, if a collision is not detected, a viewer position for rendering the next frame may be set to the desired position.

According to other embodiments of the invention, a method is provided for performing simulation operations. The simulation operations being performed as part of a simulation loop to provide interactive displays of the complex environment to a user. Further, the method may comprise: detecting, for a next frame to be rendered, input from a user; determining, based on the user input, desired movements from a current position to a desired position within the complex virtual environment; predicting, using a collision detection hierarchy of bounding boxes that contain one or more elements of the complex environment, whether a collision will occur with an element in the complex environment based on the desired movements between the current position and the desired position; and calculating an adjusted position for rendering the next frame in response to the detection of a collision.

In order to determine desired movements based on the user input, methods consistent with embodiments of the invention may calculate a path between the current position and the desired position based on the user input. Moreover, to predict whether a collision will occur, methods of the invention may perform a proximity query based on the calculated path between the current position and the desired position to identify intersecting bounding boxes, and analyze elements contained in each identified bounding box to determine if a collision will occur based on the desired movements.

Consistent with still additional embodiments of the invention, a computer program product is provided for generating interactive displays of a complex virtual environment. The computer program product may comprise a computer readable medium embodying a computer program, wherein the computer program includes instructions that are executable by a system to perform a simulation method to facilitate the rendering of frames of the complex environment. Such a method may include: determining, based on user input for a frame to be rendered, desired movements from a current position to a desired position within the complex virtual environment; performing, using a collision detection hierarchy of bounding boxes that contain one or more elements of the complex environment, a predictive collision detection operation to determine if a collision will occur with an element represented in the complex environment if the desired movements are performed between the current position and the desired position; and in response to performing the collision detection operation, setting a viewer position for the frame to be rendered.

In accordance with other embodiment of the invention, systems may be provided for generating interactive displays of a complex virtual environment. In such systems, a simulation component may be provided for performing simulations based on virtual reality (VR) file(s). The VR file(s) may include data defining a collision detection hierarchy of bounding boxes that contain elements represented in the complex environment. Further, consistent with embodiments of the invention, the simulation component may comprise: means for determining, based on input from a user, desired movements from a current position to a desired position within the complex virtual environment; means for detecting, using the collision detection hierarchy of bounding boxes, whether a collision will occur with an element represented in the complex virtual environment based on the desired movements from the current position to the desired position; and means for calculating an adjusted position when it is determined that a collision will occur based on the desired movements indicated by the user input.

Other embodiments of the invention may provided, such as a method for simulating movement of an avatar in a complex virtual environment. Such methods may comprise: determining, based on input from a user, desired movements of the avatar from a current position to a desired position within the complex virtual environment; and detecting, using a collision detection hierarchy of bounding boxes, whether a collision will occur with an element represented in the complex virtual environment if the avatar is moved from the current position to the desired position.

To detect collisions, method consistent with embodiments of the invention may perform a proximity query based on the desired movements of the avatar to identify bounding boxes that intersect with the avatar when the avatar is moved to the desired position. Such methods may also analyze elements contained in each identified bounding box to determine if a collision will occur with the avatar.

It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only, and should not be deemed restrictive of the full scope of the embodiments of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings, which are incorporated herein and constitute a part of this specification, illustrate various features and aspects of embodiments of the invention. In the drawings:

FIG. 1 illustrates an exemplary system environment for providing interactive displays of complex virtual environments, consistent with embodiments of the invention;

FIG. 2 is an exemplary network environment for providing interactive displays of complex virtual environments, consistent with embodiments of the invention;

FIG. 3 is an exemplary virtual reality (VR) system, consistent with embodiments of the invention,

FIG. 4 is an exemplary VR system and graphics system, consistent with embodiments of the invention;

FIG. 5 illustrates the contents of exemplary VR file(s), consistent with embodiments of the invention;

FIG. 6 is an exemplary pre-processing pipeline, consistent with embodiments of the invention;

FIG. 7 is an exemplary run-time pipeline, consistent with embodiments of the invention;

FIG. 8 is an exemplary flow diagram for providing interactive displays of complex virtual environments, consistent with embodiments of the invention;

FIG. 9 is an exemplary flow diagram for providing VR file(s) based on a 3D model, consistent with embodiments of the invention;

FIGS. 10A, 10B and 10C illustrate examples of a cone element type, a torus element type and a surface-of-revolution element type, respectively;

FIG. 11 illustrates an example of stretching an octree cell, consistent with embodiments of the invention;

FIGS. 12A and 12B illustrate examples of triangles;

FIG. 13 illustrates an example of a triangle strip, consistent with embodiments of the invention;

FIG. 14 is an exemplary flow diagram for identifying and building a list of occluder candidates, consistent with embodiments of the invention;

FIG. 15 is an exemplary flow diagram for creating a collision detection hierarchy, consistent with embodiments of the invention;

FIGS. 16A and 16B are exemplary flow diagrams for performing collision detection, consistent with embodiments of the invention;

FIG. 17 is an exemplary flow diagram for performing a sliding motion operation to determine an adjusted position, consistent with embodiments of the invention;

FIGS. 18A, 18B and 18C illustrate examples of determining an adjusted position in response to collision detection, consistent with embodiments of the invention;

FIG. 19 is an exemplary flow diagram for rendering complex virtual environments, consistent with embodiments of the invention;

FIG. 20 is an exemplary flow diagram for analyzing occluder candidates and blocked cells during rendering, consistent with embodiments of the invention;

FIGS. 21A and 21B are exemplary illustrations of determining the closest perimeter point and measuring an angle a for an occluder candidate, consistent with embodiments of the invention;

FIGS. 22A, 22B, 22C, 22D, and 22E illustrate examples of cells that are blocked, non-blocked or partially-blocked by occluder candidates;

FIG. 23 is an exemplary flow diagram for performing dynamic tessellation during rendering, consistent with embodiments of the invention;

FIGS. 24A, 24B and 24C are exemplary diagrams related to performing memory management operations, consistent with embodiments of the invention;

FIGS. 25A and 25B illustrate examples of rendered frames of a complex virtual environment that is representative of a building complex;

FIGS. 26A and 26B illustrate examples of rendered frames of a complex virtual environment that is representative of an offshore platform;

FIGS. 27A and 27B illustrate examples of rendered frames of a complex virtual environment that is representative of an energy plant; and

FIGS. 28A and 28B illustrate examples of rendered frames of a complex virtual environment that is representative of a city landscape.

BRIEF DESCRIPTION OF THE APPENDICES

In order to facilitate the detailed description of the embodiments of the present invention, reference is made to the noted appendices by way of non-limiting examples of features of the invention, wherein:

Appendix A includes exemplary programming code for performing a sweep test for intersection between two bounding spheres;

Appendix B includes exemplary programming code for performing a sweep test for intersection between a bounding sphere and a triangle element;

Appendix C includes exemplary programming code for dynamically tessellating a cone element type;

Appendix D includes exemplary programming code for dynamically tessellating a torus element type; and

Appendix E includes exemplary programming code for dynamically tessellating a surface-of-revolution element type.

DETAILED DESCRIPTION

Systems and methods consistent with embodiments of the present invention provide interactive graphical displays of complex virtual environments. Such systems and methods may be implemented, according to embodiments of the invention, to render complex virtual environments representing, for example, building complexes, industrial plants, offshore platforms, and other facilities or environments. The rendering of such complex environments may be performed at interactive frame rates to provide real-time simulation to the user. Further, real-world phenomena, including the effect of gravity and collisions with objects, may be simulated to provide a higher degree of realism for users.

The complex virtual environments may be based on 3D models. Such models may be defined by a large set of polygons, such as hundreds of thousands of polygons. Further, in the case of massive models, the complex environment may incorporate approximately one million or more polygons. Massive or large-scale models may be used to model various complex environments, including those related to the AEC sector, where many objects of different sizes and type are represented in the environment.

Embodiments of the invention may be implemented to facilitate various virtual reality applications for complex models. For examples, consistent with embodiments of the invention, interactive displays of complex virtual environments may be used for design and research, project review, public relations, familiarization training, maintenance planning and training, security review and training, and a wide array of other applications requiring real-time visualization and/or simulation of complex environments. Such applications may be employed in various areas, including areas in which walk-through and/or other full immersion capabilities are required for effective training or use.

As further disclosed herein, interactive displays of complex environments may be generated using one or more virtual reality (VR) file(s). Consistent with embodiments of the invention, VR file(s) may be created from a 3D model and used in place of the 3D model during run-time operations for performing simulation and rendering operations. Such VR file(s) may be constructed with an octree and a list of occluder candidates to permit visibility and culling operations to be performed more efficiently. Moreover, VR file(s) may include a collision detection hierarchy to facilitate collision detection operations during run-time operations.

To display frames of a complex virtual environment, systems and methods consistent with embodiments of the invention collect and analyze input from a user to determine the user's desired movements or operations. Using the VR file(s), predictive collision detection operations may be performed during a simulation phase to determine if the desired movements or operations will cause collision(s) with objects or elements represented in the complex environment. In response to the detection of a collision, an adjusted position or movement may be computed before rendering the frame to the user. Further, during a rendering phase, culling operations may be performed based on the camera or viewer position for the frame, and visible elements may be dynamically tessellated according to data from the VR file(s).

Consistent with embodiments of the invention, FIG. 1 illustrates an exemplary diagram of a system environment 10 for providing interactive displays of complex virtual environments. As shown in FIG. 1, system 10 includes a display 12, graphics hardware 18, a computing platform 20, a user interface 40 and a storage device or memory 30. As illustrated in FIG. 1, computing platform 20 may include a number of components for processing data and rendering complex virtual environments, such as a graphics system 24 and a virtual reality (VR) system 28. Exemplary embodiments of VR system 28 and graphics system 24 are provided below with reference to, for example, FIGS. 3 and 4.

In system environment 10, display 12 is adapted to graphically display rendered frames of a modeled environment according to operations performed by computing platform 20 and graphics hardware 18. By way of example, display 12 may be implemented with a color display terminal or device with predetermined quality and resolution. For instance, display 12 may be implemented with a color display screen having 16 or 32 bits color depth. Further, consistent with embodiments of the invention, display 12 may be provided as a separate display component connected to computing platform 20 (as represented in FIG. 1) or can be provided as a display device that is integrated with computing platform 20 (such as a display screen of a laptop computer).

Computing platform 20 of system environment 10 may be configured to process data and render complex virtual environments. For this purpose, computing platform 20 may be implemented with a workstation, a server, a personal desktop computer, a laptop or any other computing-based platform. By way of non-limiting examples, platform 20 may be implemented with a personal desktop computer or laptop with an Intel Pentium III, 350 MHz or higher-class central processing unit (CPU), such as 500 MHz or higher CPU. Other types of CPUs may also be used, such as the AMD Athlon XP Processor manufactured by Advanced Micro Devices, Inc. Computing platform 20 may also be configured with Microsoft Windows 98SE, ME, NT4, SP6, 2000 or XP.

In accordance with an embodiment of the invention, computing platform 20 may be implemented to provide accelerated graphics port (AGP) capabilities for facilitating higher 3D graphics throughput. In such a case, computing platform 20 may be implemented with an AGP chipset and motherboard equipped with an AGP bus slot. Further, an operating system such as the OSR 2.1 version of Windows 98 or Windows NT 4.0 may be used.

Consistent with embodiments of the invention, computing platform 20 may be adapted to perform a number of operations, including the pre-processing of a 3D model file to generate VR file(s) used for rendering a complex virtual environment. Further, during run-time operations, computing platform 20 may be adapted to receive input from user interface 40 and/or other devices, analyze data from the VR file(s) stored in memory 30, and generate instructions to display frames of the complex environment with display 12. Optionally, computing platform 20 may also provide instructions to user interface 40 to control one or more haptic devices that provide feedback to the user. For example, haptic devices such as gloves, helmet devices with automated tracking, force feedback joysticks, and/or other types of skeleton or human interface devices may be provided with user interface 40.

As stated above, computing platform 20 may include graphics system 24 and VR system 28. Collectively, components 24 and 28 may facilitate the processing of data and rendering of complex virtual environments. For instance, VR system 28 may be adapted to perform various simulation operations, including collision detection operations based on user input and data from the VR file(s). As a result of such operations, VR system 28 may provide output indicating, for example, the camera or viewer position for each frame to be rendered.

Rendering operations may be performed by graphics system 24 based on the results of the simulation operations performed by VR system 28. The rendering operations performed by graphics system 24 may include visibility and culling operations, as well as dynamic tessellation operations for specific types of elements defined in the VR file(s). The results of these rendering operations may include a list of vertex arrays for the elements determined to be visible, as well as vertex arrays for any dynamically tessellated elements. Based on these results, commands (such as Open GL commands) may be issued by system 24 to graphics hardware 18 to cause the display of the rendered frame on display 12.

Consistent with embodiments of the invention, graphics hardware 18, graphics system 24 and VR system 28 can be implemented through any suitable combination of hardware, firmware and/or software. By way of non-limiting example, graphics system 24 may be implemented as a software-based application using C++ and include an OpenGL software interface. Further, graphics hardware 18 may be implemented with commercially available graphics hardware, such as graphics cards that include transformation and lighting functions and suitable graphics memory (such as 32 Mb or more of graphics memory). Examples of commercially available graphics cards include GeForce II or III graphics cards available from Nvidia of Santa Clara, Calif. For GeForce graphics cards, the latest available drivers may also be installed (such as those available for downloading at Nvidia's website <http://www.nvidia.com>). By way of further example, VR system 28 may be implemented as a software-based application and programmed using C++ and/or graphics development languages or libraries, such as Microstation Development Language (MDL) available from Bentley Systems, Inc. of Exton, Pa.

Memory 30 may be implemented with a database or storage device that provides sufficient memory capacity for all of the operations performed with system 10. By way of example, memory 30 may be implemented with approximately 256 Mb or greater memory capacity depending on, for example, the complexity of the 3D model and/or data handled by system 10. As with display 12, memory 30 can be provided as a separate storage device connected to computing platform 20 (as illustrated in FIG. 1) or can be an integrated storage device that is provided as part of computing platform 20 (such as the internal memory or hard disk of a computer or laptop).

Consistent with embodiments of the invention, memory 30 may store data accessed by computing platform 20. For example, memory 30 may store data for complex virtual environments represented by 3D model files. Such files may be developed using commercially available software, such as Microstation (available from Bentley Systems, Inc.), AutoCAD (available from Autodesk, Inc.) or PDMS (available from Cadcentre Ltd.). Further, the 3D model files may be stored in conventional or proprietary file formats, such as .dgn, .dwg, etc.

Referring again to FIG. 1, memory 30 may also store VR file(s) that are used by computing platform 20 to process and render complex environments. In accordance with embodiments of the invention, VR file(s) may be generated from 3D model files. Further, as described below, VR file(s) may include optimized data representing the entire complex environment, as well as other data for facilitating the interactive display of the environment. Accordingly, consistent with embodiments of the invention, VR file(s) may be used in place of any 3D model files during run-time operations to render the complex environment. Exemplary embodiments of VR file(s) are provided below with reference to, for example, FIG. 5. In addition, pre-processing operations and exemplary flow diagrams for generating VR file(s), consistent with embodiments of the invention, are provided below with reference to, for example, FIGS. 6 and 9.

User interface 40 collects and receives input from a user and provides all user input to computing platform 20. User input may indicate instructions from the user concerning movements (forward, back, left, right, etc.) or operations (select, lift, rotate, etc.) to be virtually performed in the complex environment. Such input may permit a user to control walk-though operations in the complex virtual environment, as well as perform operations on elements (such as boxes, chairs, etc.) represented in environment. Additionally, user input may include instructions to control the operations of system 10, such as the loading of files, the execution of components and applications, etc.

By way of non-limiting examples, user interface 40 can be implemented with any number of input devices, such as a keyboard, a mouse device, a joystick and/or a track ball. The input devices may be provided as a separate device or as an integrated device with computing platform 20. User interface 40 may also include haptic devices to provide feedback to the user during simulation and rendering. As noted above, such haptic devices include gloves, helmet devices with automated tracking, force feedback joysticks, speakers and/or other types of skeleton or human interface devices.

To provide interactive displays of a complex environment, VR file(s) are first prepared (if not previously generated and stored by the user). As stated above, VR file(s) may be created from 3D model for the complex environment. By loading the 3D model from memory 30, computing platform 20 may generate the VR file(s) used for during simulation and rendering operations. For this purpose, VR system 28 may be implemented with a converter component (see, for example, FIG. 3) to perform pre-processing operations that convert or generate VR file(s) from a 3D model file. In contrast to conventional 3D model files, VR file(s) consistent with embodiments of the present invention, may be optimized to facilitate real-time, interactive display of the complex environment. For example, the VR file(s) may be constructed with an octree and/or a list of occluder candidates to permit visibility and culling operations to be performed more efficiently during run-time operations. Further, the VR file(s) may include a collision detection hierarchy to facilitate collision detection operations during run-time operations (see, for example, FIG. 5).

Once the VR file(s) are prepared, simulation and rendering operations may be performed by computing platform 20 to display successive frames of the complex virtual environment to the user. During simulation, input from the user may be collected and analyzed by VR system 28 to determine desired movements or operations for the next frame to be rendered. Based on the collision detection hierarchy of the VR file(s), VR system 28 may perform collision detection operations to determine if the desired movements or operations cause any collision(s) with objects or elements represented in the complex environment (see, for example, FIGS. 16A and 16B). In response to the detection of a collision, an adjusted position or movement may be computed by VR system 28 and provided as output for the next frame. If no collisions are detected, the desired position or operation of the user may be provided as output by VR system 28 to permit rendering operations to be performed.

Based on the output of VR system 28, rendering operations are performed by graphics system 24. For instance, during a rendering phase, visibility and culling operations may be performed by graphics system 24 to determine what cells or elements are visible for the next frame. As further described below, an octree and/or occluder candidates defined in the VR file(s) may be used by graphics system 24 to perform visibility and occlusion culling operations. In addition, curved or rounded elements that are visible in the frame may be dynamically tessellated by graphics system 24 to provide optimum rendering (see, for example, FIG. 23). In response to such operations, OpenGL commands may be issued by graphics system 24 to graphics hardware 18 to cause the next frame to be displayed to the user with display 12.

Successive frames of the complex virtual environment can be generated with system environment 10 of FIG. 1 by providing simulation and rendering operations as part of a simulation loop (see, for example, FIG. 7). Further, as indicated above, interactive displays may be provided to a user for various complex virtual environments, including those based on large-scale or massive models that contain hundreds of thousands of polygons or even one million or more polygons. Embodiments consistent with the invention, therefore, may be implemented to provide interactive displays of building complexes, off-shore platforms, industrial plants, city dwellings, and other facilities and environments that are highly detailed or contain many different types of elements.

By way of non-limiting examples, FIGS. 25-28 illustrate exemplary complex environments that may be interactively rendered by system environment 10 of FIG. 1. For instance, FIGS. 25A and 25B illustrate exemplary rendered frames of the Reichstag building complex (designed by the architectural firm of Foster and Partners of London, England) that includes many exterior as well as interior details and elements. In contrast, FIGS. 26A and 26B are exemplary rendered frames of an offshore platform (representative of a platform designed by Shell) that contains numerous structural details including curved features and rounded piping. Complex environments of industrial plants, such as the exemplary electrical energy plant of FIGS. 27A and 27B, may also be interactively displayed to a user with system 10 while providing various simulation capabilities (such as interactive walk-through operations with collision detection). Such features may also be provided for modeled environments of complex dwelling environments or landscapes. For instance, FIGS. 28A and 28B are exemplary rendered frames of a city landscape that can be interactively displayed to a user with system environment 10.

Consistent with embodiments of the invention, interactive displays of complex virtual environments may be provided to one or more users through a network environment. For instance, FIG. 2 illustrates an exemplary network environment 50 for providing interactive displays to a set of users located at client stations 70A-70N. Client stations 70A-70N may function in accordance with a peer-to-peer relationship or according to a client-server relationship with a server 54. Such arrangements may be used for various applications, including training sessions where one user acts as an instructor to train or instruct one or more other users. Network environments such as that illustrated in FIG. 2 may also be used for VR applications, where role-playing or involvement by two or more users is required.

As illustrated in FIG. 2, client stations 70A-70N and server 54 are connected to a network 62. While FIG. 2 illustrates multiple client stations 70A-70N, it will be appreciated that system 50 may be implemented for any number of users. Depending on the location and/or relationship between the users, network 62 may be implemented with a local area network, a wide area network, a virtual private network or any other type of private and/or secure communications network. Network 62 may also be implemented using public communications networks, such as the Internet. To facilitate communication over network 62, a network protocol (such as TCP/IP) may be used by and between client stations 70A-70N and/or server 54.

In the network environment 50 of FIG. 2, simulation and rendering operations may be performed entirely at each of the client stations 70A-70N. In such a case, desired movements or operations by a user at one client station may be communicated via network 62 to users at other client stations in accordance with a peer-to-peer relationship. Based on the communication of such information, each client station 70A-70N may perform simulation and rendering operations similar to that performed by computing platform 20 in FIG. 1. In order to perform these operations, identical VR file(s) may be stored in a memory 74A-74N associated with each of the client stations 70A-70N.

In a peer-to-peer relationship, such as that described above, server 54 may be omitted from network environment 50. However, to provide interactive displays in accordance with a client-server relationship, server 54 may be provided to function with client stations 70A-70N through network 62. For example, simulation operations may be performed centrally at server 54 based on user input from each of the client stations. Using data from VR file(s) stored in memory 58, server 54 may simulate the desired movements or operations by one or more users in the complex environment and provide output through network 62 to indicate the camera or viewer position for each of the client stations 70A-70N. Based on the output of server 54, each of the client stations may then perform rendering operations and graphically display each frame. In such a client-server arrangement, server 54 may also perform synchronization and user management functions for client stations 70A-70N. For instance, server 54 may coordinate and synchronize the transfer of data between the client stations. Further, server 54 may inform users when other users are connected or disconnected from the network.

As indicated above, VR file(s) may be stored in memory 58 associated with server 54, as well as in memory 74A-74N associated with each of the client stations 70A-70N. As with the embodiment of FIG. 1, the VR file(s) may include optimized data representing a complex environment, as well as other data to facilitate simulation and rendering of the complex environment on an interactive basis with each user. In the embodiment of FIG. 2, the VR file(s) may be generated from 3D model files by pre-processing operations performed by, for example, server 54. Further, memory 58 and memory devices 74A-74N may be implemented in a similar fashion to memory 30 of FIG. 1, and may also store data (such as 3D model files) in addition to the VR file(s).

For client-server arrangements, server 54 may be implemented in a similar manner as VR system 28 of FIG. 1. Thus, server 54 may be implemented with a workstation, a server, a personal desktop computer, a laptop or any other computing-based platform. Further, as with VR system 28, server 54 may include software-based components for performing simulation operations (see simulation component 25 of FIG. 3). Also, server 54 may include communication hardware for network 62 and other hardware or software-based components for performing synchronization and user management functions.

As indicated above, client stations 70A-70N may be configured to receive simulation results from server 54 over network 62. To handle such information, client stations 70A-70N may be implemented with a laptop, a workstation, a personal desktop computer or computing-based platform installed with communication hardware. Client stations 70A-70N may also be implemented with components (similar to graphics hardware 18, graphics system 24 and display 12 of FIG. 1) for performing rendering operations and displaying each rendered frame. Further, to receive user input and/or provide feedback, client stations 70A-70N may also include a user interface, such as user interface 40 of FIG. 1.

In peer-to-peer arrangements, each of the client stations 70A-70N may be additionally configured with components or systems for performing simulation operations (such as VR system 28 of FIG. 1). During simulation, client stations 70A-70N may also be adapted to track and synchronize movements with other client stations to detect and resolve collisions based on user input.

When operating in accordance with a client-server relationship, server 54 may periodically poll network 62 and detect user input from one or more of the client stations 70A-70N. User input from each client station is used by server 54 to perform simulation operations for each frame based on the VR file(s) stored in memory 58. If user input is received by more than one client station 70A-70N over a predetermined polling period, then server 54 may: analyze all of the user input; perform simulation operations (such as collision detection); and update the viewer or camera position of each user for the next frame to be rendered. Server 54 may be adapted to provide simulation such that one or more users are represented within a complex virtual environment by an avatar and/or users can observe other users represented within the environment. With such simulation capabilities, various applications can be provided for multiple users with system 50, such as training exercises where one user acts as an instructor for other users.

After simulating each frame, the output of server 54 is provided to client stations 70A-70N via network 62. Based on the output of server 54 and the data in the VR file(s), each client station may perform rendering operations for the frame to be rendered. Such rendering operations may include visibility and occlusion culling operations, as well as dynamic tessellation of curved or rounded elements that are determined to be visible in the frame. During the rendering phase, each client station may also extrapolate and determine the best fit for displaying the rendered frame to the user at the client station. To display the rendered frame, a set of commands (such as OpenGL commands) may be issued to the graphics hardware at each client station. Further, if feedback is simulated for users, then each client station may provide feedback (where applicable) to a user through the haptic devices located at the client station.

FIG. 3 illustrates exemplary VR system 28, consistent with embodiments of the present invention. VR system 28 may be implemented as part of computing platform 20 (see FIG. 1) or server 54 (see FIG. 2) to perform various operations. As illustrated in FIG. 3, VR system 28 includes a simulation component 25 and a converter component 21. These components may be implemented as software-based applications or components that are developed using a programming language and/or a graphics development language or libraries.

Converter component 21 may be configured to perform pre-processing operations including the conversion of 3D model files into VR file(s). Converter component 21 may be implemented using, for example, C++ and Microstation development language for generating VR file(s). An exemplary embodiment of VR file(s) is provided in FIG. 5 and exemplary embodiments of the pre-processing and conversion operations performed by converter component 21 to generate VR file(s) are described below with reference to, for example, FIGS. 6 and 9.

In the embodiment of FIG. 3, simulation component 25 is configured to perform run-time operations including the processing of user input and simulation to permit the rendering of frames of a complex virtual environment. Simulation component 25 may be implemented using a programming language such as C++ or other comparable programming languages. An exemplary embodiment of simulation component 25 is explained below with reference to FIG. 4 and exemplary embodiments of the run-time and simulation operations performed by simulation component 25 are further described below with reference to, for example, FIGS. 7 and 8.

FIG. 4 illustrates an exemplary embodiment of VR system 28 and graphics system 24, consistent with embodiments of the invention. As illustrated in FIG. 4, simulation component 25 of VR system 28 may be implemented with a number of software-based engines or sub-components. For example, simulation component 25 may include a physics engine 254 and an I/O engine 256. During run-time operations, user input is received and pre-processed by I/O engine 256. I/O engine 256 may perform any necessary processing operations on the user input (such as the translation of signals received from user interface or input devices) and provide the user input to physics engine 254. If feedback is provided to the user, I/O engine 256 may also output feedback instructions generated by simulation component 25 to haptic device(s) controlled or worn by the user. This may cause various sensations (such as pressure, resistance, vibration, sound, etc.) to be provided to the user in order to simulate activity or occurrences in the complex virtual environment.

Based on user input, physics engine 254 determines a user's desired movements or operations for each frame to be rendered. As part of this determination, physics engine 254 may consider the direction and velocity of a moving object or avatar based on the user input. The effect of gravity may also be analyzed to calculate the desired position for the next frame. Further, using the VR file(s), physics engine 254 may detect if any collisions exist with objects in the simulated environment due to the desired movement or operations of the user. If a collision is detected, physics engine 254 may resolve any such collisions to determine the user's final adjusted position or viewer position for the next frame. To perform such operations, physics engine 254 may be adapted to perform collision detection operations, such as those further described below with reference to, for example, FIGS. 8 and 16A-16B.

The viewer or camera position determined by physics engine 254 is provided to graphics system 24. As illustrated in FIG. 4, graphics system 24 may include a graphics engine 242. Graphics engine 242 may be a software-based engine or component that performs various rendering operations for each frame to be rendered to a user. For example, based on the viewer position and data contained in the VR file(s), graphics engine 242 may determine which objects are visible and which objects are occluded or hidden from view for each frame. In addition, for specific visible elements or objects defined in the VR file(s) (such as rounded or curved objects), graphics engine 242 may perform dynamic tessellation operations to control the level of detail by which such elements are displayed to the user. To perform such rendering operations, graphics engine 242 may be implemented with occlusion culling and dynamic tessellation functions, such as those further described below with reference to, for example, FIGS. 8, 19 and 23.

The results of the rendering operations performed by graphics engine 242 may include a list of vertex arrays for the elements determined to be visible, as well as vertex arrays for each dynamically tessellated element. Based on these results, commands (such as Open GL commands) may be generated by graphics engine 242 to the graphics hardware 18 (not illustrated in FIG. 4) to cause the display of each rendered frame to the user.

FIG. 5 illustrates exemplary VR file(s) 50, consistent with embodiments of the invention. Generally, VR file(s) contain data and information relating to a complex environment for run-time operations. In contrast to conventional 3D model files, the VR file(s) may be optimized for facilitating real-time rendering and interactive displays of a complex environment for users. Thus, as illustrated in FIG. 5, VR file(s) 50 may include an octree file 52 to facilitate, for example, visibility determinations. Further, a collision detection file 56 may be generated to optimize the VR file(s) for collision detection operations. In accordance with embodiments of the invention, files 52 and 56 may be stored as separate VR files or they may be stored as part of a single VR file. For ease of reference, whether stored separately or jointly, these files are herein referred to as "VR file(s)."

Octree file 52 and collision detection file 56 may be generated from data representing a complex environment. For example, octree file 52 and collision detection file 56 may be generated by VR system 28 based on data from conventional 3D model files, such as Microstation or AutoCAD files. Such models of complex environments typically include data for describing primitives (such as points, lines, polygons, polyhedra and/or free-form surfaces) that define the shape of components of an object. A model for a complex environment may also include data for describing object attributes, such as line style, color, or surface texture, and connectivity relationships and positioning that define how the components fit together. In a 3D model, curved surfaces can be approximated with polygons and solid objects can be represented by polyhedra, each of which represents a set of polygons connected at a common edge and enclosing a volume.

When rendering a complex environment, objects and surfaces that are hidden or occluded by other objects or surfaces closer to the viewpoint may be eliminated. For complex environments, the complexity of visibility determination can be simplified by spatially partitioning or dividing the environment into cells or cubes. For example, according to an embodiment of the invention, octrees can be used to subdivide a complex environment represented by a 3D model. Octrees provide a hierarchical approach to spatially-partitioning, whereby an environment is divided into eight equally sized, three-dimensional cells (e.g., cubes) and each cell is further divided into eight cells until a cell is empty or contains fewer than a predetermined number of elements or primitives (such as polygons or triangles). Consistent with embodiments of the invention, each level of the octree may be represented by nodes that are hierarchically related to one another in accordance with each level of division.

During pre-processing, an octree may be constructed for a complex environment represented by a 3D model. As illustrated in FIG. 5, data representing the octree can be stored as part of octree file 52. Octree file 52 includes data representing the octree of elements. The octree can be defined by any number of cells, whereby each cell includes a vertex array for every material used by the elements or primitives of the cell. Octree file 52 may also include one or more occluder candidates 54. Occluder candidates may be generated during pre-processing of a 3D model based on elements or primitives that have characteristics that classify them as global candidates for consideration when perform occlusion culling (such as a large surface area). According to embodiments of the invention, occluder candidates 54 may be stored together as a separate list in octree file 52. Alternatively, each occluder candidate may be merged with the octree and stored relative to nodes of the octree for cells occupied by the occluder candidate.

When performing simulation operations, collisions with objects may be detected and simulated to replicate real-world phenomena. The task of collision detection can be complex, especially for environments based on massive models. To improve such performance, spatial partitioning of the environment may also be performed during pre-processing to provide a collision detection hierarchy. In particular, a collision detection file 56 may be generated from a 3D model by creating grid subdivisions. As further described below, the modeled environment may be divided into a grid of equally sized cubes. After allocating elements or primitives (such as triangles) to the cubes, a bounding box tree (such as an axis-aligned bounding box (AABB) tree) may be created for each cube. Each bounding box can be created by dividing a cube into two equally sized cells or cubes and then further dividing the cubes until a cube is empty or contains fewer than a predetermined number of elements or primitives. As with octrees, each level of the bounding box may be represented by nodes that are hierarchically related to one another in accordance with each level of division. This hierarchy of bounding boxes may be stored to provide the collision detection hierarchy of collision detection file 56.

In accordance with an embodiment of the invention, FIG. 6 illustrates an exemplary pre-processing pipeline. The exemplary pre-processing pipeline of FIG. 6 may be implemented to generate VR file(s) based on a 3D model of the complex virtual environment. Such operations may be performed by VR system 28 of system environment 10 (FIG. 1) or server 54 of network environment 50 (FIG. 2). For purposes of illustration, however, reference will be made to the embodiment of FIG. 1 to describe the operations and features of FIG. 6.

As illustrated in FIG. 6, the pre-processing pipeline begins with the loading of a 3D model file (operation 102). For example, VR system 28 may load and/or access a 3D model file from memory 30. The 3D model comprises data for defining all objects in the modeled complex environment, including object attributes (such as color, surface texture, etc.). Since most conventional 3D model files are not optimized for real-time simulations or rendering, the data from the 3D model is analyzed during pre-processing to generate VR file(s), consistent with embodiments of the invention.

After loading the 3D model file, the elements or primitives (such as polygons or triangles) of the complex environment are analyzed and filtered (operation 104). In particular, VR system 28 may analyze the 3D model data to identify and filter elements that can be dynamically tessellated during run-time operations. In accordance with an embodiment of the invention, elements that have curved or rounded features may be filtered from other elements in the 3D model and identified as dynamic tessellation elements. For instance, elements including an arc, an ellipse, a curve and/or a b-spline can be filtered from other elements. Such dynamic tessellation elements can be identified based on the name, structure and/or format of the data. For example, 3D models developed with Microstation may designate element types by specific name or header. In addition, the structure or format of the data can be analyzed to confirm the identity of a particular element type. For instance, based on the type of files used (Microstation, AutoCAD, etc.), element types in a 3D model may be identified in accordance with their predetermined data structure or format.

The name, structure and/or format of elements defined in 3D model files may vary according to the software version or edition with which it was developed. To overcome such drawbacks, routines may be developed to identify element types regardless of the version or edition with which the 3D model was created. For instance, a software-based component may be created using Microstation Development Language (MDL) to analyze data sets defining elements in a 3D model regardless of the version of Microstation, 3D model file.

When filtering elements (operation 104), VR system 28 may reformat and store any identified dynamic tessellation elements according to element type. As further described below with reference to FIGS. 10A-10C, specific element types can be stored in predetermined data formats that permit the VR file(s) to be processed and handled easier during run-time operations. For all remaining elements that are not filtered (i.e., all non-dynamic tessellation elements), triangulation operations may performed for polygons having more than three line segments (operation 106). In particular, each non-dynamic tessellation element is analyzed and stored either as a single triangle or set of triangles. Thus, if an element is represented as a single triangle in the 3D model, the element will be stored as a single triangle in the VR file(s). However, if the element is represented by a polygon or a set of polygons having more than three line segments, then each polygon may be triangulated and stored as a group or set of triangles. While storing all non-dynamic tessellation elements as triangles may increase the overall volume of data related to these elements, this allows the system to take advantage of state-of-the -art graphics hardware (such as graphics cards) that can directly handle and process triangle elements.

After triangulating polygons (operation 106), the final operations of the pre-processing pipeline are performed in order to create the VR file(s). As illustrated in FIG. 6, such operations may include: building a list of occluder candidates (operation 108); constructing an octree (operation 110); and building a collision detecting hierarchy (operation 112). These operations may be performed in parallel or in any sequence by VR system 28. Further, the results of the octree may be stored as part of an octree file (such as octree file 52) and the results of the collision detection hierarchy may be stored as part of a collision detection file (such as collision detection file 56). As described with reference to FIG. 5, the list of occluders can be stored as a separate list in the VR file(s). Alternatively, the list of occluders can be merged into the related nodes of the octree. In such a case, any identified occluder candidates can be inserted and merged into the octree (operation 114) after the octree is constructed.

Consistent with embodiments of the invention, FIG. 7 illustrates an exemplary run-time pipeline for providing interactive displays of complex virtual environments. The run-time pipeline of FIG. 7 includes simulation and rendering operations that can be performed with VR file(s) that have been generated for a complex environment. The operations of FIG. 7 can be performed by computing platform 20 of system environment 10 (FIG. 1) or server 54 and/or client stations 70A-70N of network environment 50 (FIG. 2). For purposes of illustration, however, reference again will be made to the embodiment of FIG. 1 to facilitate the description of FIG. 7.

Run-time operations are initiated by loading VR file(s) (operation 132). As discussed above, VR file(s) may be stored in memory 30. To select particular VR file(s), a dialog box may be displayed to the user so that the appropriate VR file(s) can be identified or selected. When loading the VR file(s), various system configurations may be performed. For example, based on input from a user, simulation features (such as collision detection or gravity effects) may be activated or deactivated by computing platform 20. Also, other system configurations (such as memory management operations) may be initiated by computing system 20. Exemplary embodiments for performing memory management operations are described below with reference, for example, to FIGS. 24A, 24B and 24C.

Consistent with embodiments of the invention, once the VR file(s) are loaded (operation 132), a simulation loop is performed (operation 140) based on user input (138). The simulation loop for a complex virtual environment may be reiterated to render successive frames of the environment until the run-time pipeline is terminated (based on, for example, an escape or exit command entered by the user).

As further illustrated in FIG. 7, the simulation loop includes frame simulation (operation 134) and frame rendering (operation 136). During simulation of each frame, user input is analyzed to determine desired movements or operations of a moving object or avatar representing the user in the complex virtual environment. By performing operations such as collision detection, VR system 28 can determine the position of the moving object or avatar and the viewer position for the next frame to be rendered. Information determined during simulation is then used to perform rendering operations. During the rendering phase, occlusion culling and dynamic tessellation operations can be performed, in accordance with embodiments of the invention. The results of the rendering operations can be used by graphics system 24 to cause the rendered frame to be displayed to the user. During the simulation loop, various system configuration operations may be performed, such as memory management operations.

FIG. 8 is an exemplary flow diagram for providing interactive displays of complex virtual environments, consistent with embodiments of the invention. For purposes of illustration, the exemplary flow diagram of FIG. 8 will be described with reference to the system environment 10 of FIG. 1. The exemplary flow diagram of FIG. 8, however, may be implemented with other environments, including the network environment 50 of FIG. 2.

As illustrated in FIG. 8, in order to provide interactive displays of complex virtual environments, the VR file(s) are provided (step S.10). As described above, VR file(s) may be generated from a 3D model of the complex environment. The 3D model may be generated from a 2D drawing by using 3D modeling software or a 3D reconstructor program based on a laser scanning of the environment. The 3D model may also be created independently by a designer or programmer using 3D modeling software. In cases where the 3D model is based on a 2D drawing or file, 3D features may be selectively defined depending on the complex environment. For instance, if the 2D drawing represents the floor plan of building complex or residence, a 3D model may be created by projecting one or more elements in the drawing (such as walls and/or walkways) to permit better visualization of the floor plan. The elements to be projected in 3D may be uniquely identified in a 2D file (such as by color or texture) to assist in the designer or programmer in creating the 3D model. Once the 3D model is generated, the VR file(s) may be created. To generate the VR file(s), pre-processing operations may be performed by VR system 28. An exemplary pre-processing pipeline for generating VR file(s) is disclosed herein with reference to FIG. 6. Further, an exemplary flow diagram for generating VR file(s) from a 3D model is described below with reference to FIG. 9.

Referring back to FIG. 8, after the VR file(s) are generated, the VR file(s) are loaded or accessed from memory 30. During or after the loading of the VR file(s), any necessary system configurations can be performed (step S.12). As indicated above, various system configuration options may be set by the user. For instance, simulation features (such as collision detection or gravity effects) may be activated or deactivated by a user. Also, specific system configurations (such as memory management operations) may be initiated by computing system 20. An initial viewer position may also be set according to a predetermined default setting for the first frame to be displayed to the user.

Simulation and rendering is then performed to display successive frames of the complex virtual environment based on input from the user. In particular, system 10 can poll for user input over a predetermined time period for each frame (step S.14). For instance, through user interface 40, VR system 28 may detect desired movements or operations entered by the user during the polling period. Using a keyboard, a trackball or a joystick, the user may enter desired movements (forward, back, left, right, etc.) and/or operations (lift, rotate, select, etc.). Based on input detected from the user, VR system 28 then performs simulation operations in order to render the next frame.

For example, predictive collision detection may be performed based on the detected user input (step S.16). Consistent with embodiments of the invention, VR system 28 analyzes all moving objects or avatars to determine if any collisions occur with other objects when moving the object or avatar between its current position and desired position for the next frame. As disclosed herein, the collision detection file 56 of the VR file(s) may be used to detect collisions (see, for example, FIGS. 16A and 16B). If a collision is found (step S.18; Yes), then VR system 28 responds to the collision (step S.20). For example, VR system 28 may project the movement of the object or avatar and determine an adjusted position from the first point of contact. If another collision is detected between the first point of contact and the adjusted position, then another adjusted position is detected until no further collisions are detected (step S.18; No). The final adjusted position is then used in place of the desired destination for purposes of setting the viewer position for the next frame. If no collisions are detected, then the viewer position is set to the desired position. An exemplary flow diagram for performing predictive collision detection operations is described below with reference to FIGS. 16A-16B.

To render a frame, it is necessary to remove or cull all elements or primitives that are outside the view frustum or occluded by other elements or objects. For this purpose, graphics system 24 performs culling operations (including occlusion culling) based on the determined viewer or camera position for the next frame (step S.22). To perform culling operations, the octree file 52 of the VR file(s) can be used. Exemplary flow diagrams for performing culling operations are described below with reference to FIGS. 19 and 20.

In addition to performing culling operations, graphics system 24 may perform dynamic tessellation operations (step S.24). In particular, for dynamic tessellation elements that are in the view frustum and not occluded, graphics system 24 determines a tessellation level for rendering each object. As further described in connection with the exemplary embodiment of FIG. 22, the tessellation level can control the number of triangles used to approximate the object in the rendered frame. For instance, objects or elements may be rendered with increasing number of triangles for higher tessellation levels. Further, objects or elements that appear closer to the camera position or screen may be assigned higher tessellation levels to cause the object or element to be rendered with a greater number of triangles and, therefore, greater detail.

After performing culling operations and dynamic tessellation, the frame is rendered and displayed to the user (step S.26). As part of this process, the results of the rendering operations may be used by graphics system 24 to issue or generate commands (such as OpenGL commands) to graphics hardware 18. The results of the rendering operations may indicate what elements or objects are visible and need to rendered, as well as how to render dynamic tessellation elements that are within the view frustum. Each visible element or object may be represented by a vertex array of x, y, z coordinate points that define the vertices of the element. An index array may be generated that reads into the vertex array and controls the number of triangles used to render the element or object. Thus, a set of OpenGL commands may be generated based on a specific vertex array data for the elements determined to be visible, as well as vertex array data for each visible dynamically tessellated element. In response to the Open GL commands, graphics hardware 18 (such as a graphics card) may cause the display of the next frame on display 12. Thereafter, successive frames may be simulated and rendered (steps S.14-S.26) until run-time operations are terminated by the user.

FIG. 9 is an exemplary flow diagram for providing VR file(s), consistent with embodiments of the invention. As described above, VR file(s) can be generated from conventional 3D models that include data representing a complex environment. The VR file(s) can be generated during pre-processing in order to prepare and store the files before run-time operations are performed. Once created, the VR file(s) can be accessed from memory and used for simulation and rendering operations. The exemplary flow diagram of FIG. 9 may be implemented through various systems or environments, such as the system environment 10 of FIG. 1 or the network environment 50 of FIG. 2. However, for purposes of illustration, reference will be made to the embodiment of FIG. 1 to describe the flow diagram of FIG. 9.

As illustrated in FIG. 9, the exemplary process begins with the loading of a 3D model (step S.40). In accordance with embodiments of the invention, a 3D model file may be designated by the user (using, for example, a displayed dialog box) and accessed from memory (such as memory 30). The 3D model file may be a CAD or other type of 3D model file that represents a complex environment (such as a plant, a building facility, an off-shore platform, etc.). Further, the 3D model file may be generated using Microstation or other types of commercially available software.

To create the 3D model, modeling software may be used to generate the 3D model. The 3D model may also be generated from a 2D drawing or file, such as an engineering or architectural drawing. Thus, the 3D model may be based on a 2D file in which one or more elements have been projected into 3D. Alternatively, the 3D model may be created by laser scanning the environment and using a 3D reconstructor program. When creating the 3D model file, the file may be prepared with various features or functions to facilitate updates to the objects represented in the 3D model. For instance, a virtual reality (VR) library may be provided with a number of special VR functions in order to incorporate such functions into the 3D model file. The VR functions may permit the name, texture, lighting and/or rotational aspects of an object to be specified and, if needed, updated in the future. An initial, viewer or camera position for an avatar may also be defined in the modeled environment. In addition, functional links may be defined for an object to permit functions such as a database link to retrieve information for the object (such as material and/or cost information, etc.).

After accessing or loading the 3D model file, the elements or primitives of the model are filtered (step S.42). For example, VR system 28 may analyze the 3D model data to identify and filter dynamic tessellation elements from other elements that are static or non-tessellated during rendering. In accordance with embodiments of the invention, elements that have curved or rounded features may be filtered and distinguished from other elements in the 3D model. For instance, elements including an arc, an ellipse, a curve and/or a b-spline can be identified as dynamic tessellation elements and filtered from other elements identified as non-dynamic tessellation elements.

Consistent with embodiments of the invention, VR system 28 may identify one or more major types of dynamic tessellation elements, such as cone element types, torus element types, and/or surface-of-revolution element types. Generally, a cone element type is defined by two circles or ellipses and one or more lines (see, for example, FIG. 10A). If the dimensions of the two circles or ellipses are identical, the cone element type may represent a cylinder. A torus element type is generally defined by a center point, two ellipses or circles and one or more arcs. Torus element types can represent elbows or donuts (see, for example, FIG. 10B). Surface-of-revolution element types are defined by a number of parameters including a center point, an ellipse and an angle of rotation. Surface-of-revolution element types may represent different types of curved surfaces or objects (see, for example, FIG. 10C).

To identify dynamic tessellation elements, VR system 28 may analyze the name, structure and/or format of the data representing each element in the 3D model. For example, as indicated above, 3D model files developed with Microstation may designate certain element types by specific element names. In addition, the structure or format of the data can be analyzed to confirm the identity of a particular element type. For instance, a cone element type in a Microstation file is defined by a data structure comprising a header followed by two ellipses and four lines. Further, in a 3D model developed with Microstation, a torus element type developed is defined by a data structure comprising a header followed by two ellipses and a set of arcs (such as four arcs) and a surface-of-revolution element type is defined by a header and a data set indicating a surface-of-revolution. Once again, a software-based component may be created using a software-manufacturer-specific, development language (such as Microstation Development Language (MDL)) that permits data sets defining elements in the 3D model to be identified regardless of the version of 3D model file.

For each identified dynamic tessellation element, VR system 28 may store the element in an optimized data format in the VR file(s) to better facilitate run-time operations. For example, as illustrated in FIG. 10A, a cone represented by a cone element type may be stored as a data structure including: a center point of the top (T); a center point of the bottom (B); a center point (C) on the axis between T and B; a radius of the top (R.sub.t); and a radius of the bottom (R.sub.b). Further, as indicated in FIG. 10B, a torus represented by a torus element type may be defined by a data structure including: an axis of revolution (A); a center point on the axis of revolution (C); an angle of revolution (.alpha.); an internal radius (R.sub.1); and an outer radius (R.sub.2). A surface-of-revolution, such as that depicted in FIG. 10C, may be represented by a surface-of-revolution element type stored as a data structure comprising: an axis of revolution (A.sub.S); a center point of the revolution (C.sub.S); an angle of the revolution (.alpha..sub.S); a radius of the revolution (R.sub.S); a center point of the ellipse (C.sub.A); an angle of the ellipse (.alpha..sub.A); a shorter radius of the ellipse (R.sub.A1); and a longer radius of the ellipse (R.sub.A2).

For the remaining elements that are not filtered (i.e., all non-dynamic tessellation elements), triangulation operations may be performed (step S.44). In particular, VR system 28 may analyze each non-dynamic tessellation element in the 3D model and store it either as a single triangle or set of triangles. Accordingly, if an element is represented as a single triangle in the 3D model, the element will be stored as a single triangle in the VR file(s). However, if the element is represented by a polygon with more than three sides or a set of polygons, then each polygon is triangulated and stored as a group or set of triangles. While storing all non-dynamic tessellation elements as triangles may increase the overall volume of data needed to define these elements, all elements should be represented by triangles for rendering purposes to take advantage of state-of-the-art graphics cards that can directly handle triangles without any additional processing (CPU) resources required for rendering.

Consistent with embodiments of the invention, various techniques may be employed for triangulating polygons. For example, VR system 28 may be implemented to generate sets of triangles by analyzing the vertices of a polygon. Alternatively, a conventional graphics utility, such as OpenGL utility library (GLU), may be provided to perform triangulation operations. In such a case, a specific utility may be called by VR system 28 by providing the vertices of the polygon to be triangulated, and in response the utility may perform triangulation operations and output a set of triangles for the polygon.

After filtering dynamic tessellation elements (step S.42) and triangulating polygons (step S.44), an octree is constructed (step S.46). As indicated above, an octree can be constructed by spatially partitioning or dividing the complex environment into cells or cubes. Octree as well as other types of partitioning techniques can be used to simplify the task of determining which objects and surfaces are visible versus those that are hidden or occluded when rendering the complex environment.

The octree may be constructed from the filtered dynamic tessellation elements (reformatted and stored in an optimized data format) and non-dynamic tessellation elements (including polygonal elements that have been triangulated). To construct an octree, a single cell is first defined that contains the entire modeled environment, including all dynamic and non-dynamic tessellation elements. This cell is then divided into eight cells by cutting or dividing along each of three axes (x, y, z). For a 3D environment, each cell of the octree represents a three-dimensional volume defined by two x, y, z points (i.e., a minimum point and a maximum point for the cell). Each divided cell is then further divided into eight cells, with such cell division continuing until a cell is empty or contains fewer than a predetermined number of elements or primitives (such as polygons or triangles). Consistent with embodiments of the invention, each level of the octree may be represented by nodes that are hierarchically related to one another in accordance with each level of division.

When dividing a cell (including the first bounding cell), VR system 28 may cut or divide the cell at the center point of the cell to thereby create eight, equally-sized cells. Alternatively, VR system 28 may determine the median location of all triangles within the cell and divide the cell at the median location. Such a technique may be used to provide a more balanced octree, especially for environments in which triangles are not evenly distributed in space. When using the median location of triangles to divide cells, the resulting cells may be unequal in size. However, this will not effect the usage of the octree, since all cells are simply defined by a set of coordinates that define the vertices of the cell.

When performing cell division to construct the octree, an analysis may be performed to determine the number of elements that are contained within each cell. Therefore, as indicated above, VR system 28 may analyze and count non-dynamic tessellation elements (i.e., triangles) for the purposes of determining whether to further divide a cell. By way of example, cell partitioning for the octree may continue until a cell contains fewer than approximately 10,000 triangles. Further, dynamic tessellation elements may be analyzed to determine whether to further divide a cell. By way of example, cell partitioning for an octree may continue if the cell contains more than 1,000 dynamic tessellation elements. As such, the number of non-dynamic tessellation elements and/or the number of dynamic tessellation elements may be considered when performing cell division. Moreover, when assembling and storing the final VR file(s), all elements (including dynamic and non-dynamic tessellation elements) may be assigned or associated with their corresponding cells or nodes of the octree.

When creating cells of the octree, elements in the environment may not be positioned completely within a cell. This situation may arise with respect to both non-dynamic tessellation elements and dynamic tessellation elements. Various solutions may be used to address this problem. For instance, if division of a cell causes certain elements to be distributed into two or more cells, then each such element may be maintained only in the previous cell (i.e., the cell that was divided). This approach may be used for handling dynamic tessellation elements that are split during cell division. For non-dynamic tessellation elements, cells may be adaptively stretched to control the assignment of elements to cells of the octree.

FIG. 11 illustrates an example of stretching an octree cell to accommodate non-dynamic tessellation elements (i.e., triangles). For ease of illustration, the example of FIG. 11 is presented in 2D, but the concept of stretching is applicable to 3D cell partitioning. As illustrated in FIG. 11, a cell division may result in the creation of Original Cell #1 and Original Cell #2. Triangle T2 may be located within Original Cell #1, whereas triangle T1 may be located within Original Cell #1 and Original Cell #2. To address this problem, Original Cell #1 may be stretched along one direction to accommodate triangle T1 and define a new cell, Stretched Cell #1. While an overlap may exist between the stretched cell and other neighboring cells (such as between Stretched Cell #1 and Original Cell #2), elements are maintained or reassigned only to the cells that fully contain the element. For example, after performing stretching on the cells illustrated in FIG. 11, triangles T1 and T2 would be assigned to Stretched Cell #1 and triangle T3 would maintain its assignment to Original Cell #2.

When stretching the dimension(s) of a cell, the cell may be stretched only to the extent that it is necessary to fully contain the divided element (such as triangle T1). Thus, the vertices of divided or split elements may be used to determine the extent and the axis (x, y or z in 3D environments) along which the stretch should be performed. For example, as illustrated in FIG. 11, Stretched Cell #1 may be generated as a result of stretching the Original Cell #1 in the direction of and only to the extent of the outer vertex of triangle T1 that is not contained within Original Cell #1.

Further, consistent with embodiments of the invention, if more than one cell can be stretched, then the cell determined to have the majority of the volume or area of the divided element(s) may be stretched. As a result, VR system 28 would only perform stretching on the cell determined to require the least amount of stretching. Moreover, if more than one element is outside of a cell, then the cell may be stretched in one or more directions until all elements are within the stretched cell.

When stretching cells for a 3D environment, stretching can be performed along one or more axes (x, y and/or z). Further, since all triangle elements should be contained within a cell before it is divided, the vertices of the divided elements may be compared against the center point or median location where the cell division or cut occurred to determine the direction and amount of stretching required for divided cells. Such an analysis may be performed with respect to each divided element by comparing the x, y and z coordinates of the triangle to the center point or median location. This process may be repeated for divided cells requiring stretching based on more than one divided element or triangle.

Consistent with an embodiment of the invention, various techniques may be performed for allocating dynamic tessellation elements to the cells of the octree. For example, dynamic tessellation elements may be allocated only to cells within which they are fully contained. To determine if a cell fully contains a dynamic tessellation element, a bounding box may be generated about the dynamic tessellation element and the bounding box may be compared to the cells of the octree to determine the lowest level cell of the octree that fully contains the bounding box. The allocation of dynamic tessellation elements may occur during the process of creating the octree or as a separate process that is performed after all of the cells of the octree are constructed.

Referring again to FIG. 9, after identifying and constructing the cells of the octree (step S.46), each cell of the octree may be analyzed to perform a number of operations on the elements contained in the cell (step S.48). As illustrated in FIG. 9, such operations may include sorting elements by material, optimizing vertex arrays, and/or building triangle strips.

For example, the elements of each cell (including non-dynamic tessellation elements and dynamic tessellation elements) may be sorted according to their material type. The material type for each element, which may be extracted from the 3D model, may define various rendering properties for the element such as color, opacity, brightness and/or texture. For each cell, the material type for each element may be determined and then one or more linked lists may be created to list the elements according to material type. Sorting elements by material type in the final VR file(s) can provide faster rendering rates, since most conventional graphics cards can only process and render elements with one material that is active at a time. As a result, organizing elements by material type can reduce the amount of processing time required by the graphics hardware to switch between material types during run-time operations.

As illustrated in FIG. 9 (step S.48), the elements of each cell may also be processed to optimize vertex arrays. Such an operation may be performed to optimize the manner in which triangle elements are stored in the VR file(s). For example, triangle elements in a cell can be analyzed to determine shared vertices between triangles and, for triangles identified with shared vertices, the data defining such triangles may be reformatted to reduce the overall amount of data required to define the triangles. Triangle elements that do not share a common vertex with one or more other triangles can also be reformatted to define such triangles with vertex data to provide similar formatting with the triangles identified to have common vertices.

To illustrate the concept of providing optimized vertex array data, reference will now be made to FIGS. 12A and 12B to illustrate an embodiment consistent with the principles of the invention. Assume, for example, that a triangle (T1) is defined by a set of x, y, z points in the 3D model. As illustrated in FIG. 12A, three such points (P1, P2, P3) are required to define the triangle (T1). For 3D modeling, each of these points (P1, P2, P3) may be defined by different x, y, z coordinates. Thus, P1=(x1, y1, z1), P2=(x2, y2, z2), and P3=(x3, y3, z3) and T1 can be defined by a combined data set of x, y, z coordinates (x1, y1, z1; x2, y2, z2; x3, y3, z3) in the 3D model. In the example of FIG. 12A, triangle (T1) does not share a common vertex with any other triangle element in the cell. However, as illustrated in FIG. 12B, assume that two other triangles in the cell (T2 and T3) have one common vertex (P5). In the 3D model, these triangles (T2 and T3) may be represented by combined data sets (i.e., (P4, P5, P6) and (P5, P7, P8), respectively) where each point (P) in the combined data sets is uniquely defined by x, y, z coordinates. Thus, in the 3D model, T2 may be defined by a combined data set of x, y, z coordinates (x4, y4, z4; x5, y5, z5; x6, y6, z6 and T3 can be defined by another combined data set of x, y, z coordinates (x5, y5, z5; x7, y7, z2; x8, y8, z8). As can be seen by the above-noted example, repetitive data is stored in the 3D model for at least the coordinates defining the triangles (T2 and T3) that have a shared vertex.

To provide optimized vertex array data for the exemplary triangles of FIGS. 12A and 12B, VR system 28 may generate one or more vertex arrays (A.sub.v that define the x, y, z coordinates for the vertex points (P) of all triangle elements contained in the cell. Thus, for a cell containing the triangles (T1, T2, T3) illustrated in FIGS. 12A and 12B, a vertex array (A.sub.v) may be generated as follows: A.sub.v =(P1, P2, P3, P4, P5, P6, P7, P8), where each vertex point in the array is defined by a unique set of x, y, z coordinates. To define each triangle in the cell, VR system 28 may also generate an index array of triangles (A.sub.t) as follows: A.sub.t =(T1, T2, T3) where each triangle in the array is defined by a unique set of vertex points (e.g., T1=P1, P2, P3: T2=P4, P5, P6 and T3=P5, P7, P8) defined by the vertex array (A.sub.v). Alternatively, the index array may be generated with pointers that identify positions in the vertex array. For example, assume that vertices P1-P8 are defined in positions 1-8, respectively, of a vertex array (A.sub.v). Further, assume that an index array (A.sub.t) is generated for the triangles T1, T2, T3 as follows: A.sub.t =(1, 2, 3, 4, 5, 6, 7, 8). To determine the coordinates of each of the triangles, the pointers from every three positions of the index array may be used to read into the vertex array and extract the data. Thus, returning to the previous example, the pointers from the first three positions of the index array A.sub.t (i.e., 1, 2, 3) may be used to read the corresponding positions in the vertex array A.sub.v and extract the coordinates for the triangle T1(i.e., x1, y1, z1; x2, y2, z2; and x3, y3, z3). The next three position in the index array A.sub.t (i.e., 4, 5, 6)) could then be read to extract the vertex data from the vertex array A.sub.v for the triangle T2, and a similar process may be repeated to extract the vertex data for the triangle T3.

With such an approach, optimized vertex array data can be provided and stored with respect to the cells of the octree for the VR file(s). Optimizing vertex array data for triangle elements may reduce the overall amount of data needed to define the complex virtual environment, as well as improve graphics processing and cache performance since previously transformed vertices can be pulled from cache (rather than recalculated) during the rendering phase.

Another operation that may be performed on the triangle elements of each cell (FIG. 9; step S.48) is the building of triangle strips. In particular, after optimizing the vertex data, an index array for a triangle strip (A.sub.ts) may be built to replace triangle array data representing triangle elements that have common edges. FIG. 13, for example, illustrates a triangle strip comprising three triangles (T1, T2, T3). The triangles of a triangle strip may result from triangulated polygons (see FIG. 9, step S.44) or may be original triangle elements in the 3D model that have common edges. Consistent with embodiments of the invention, VR system 28 may define an index array for a triangle strip (A.sub.ts) where the array defines triangles belonging to a triangle strip according to their vertex points. These vertex points may be further defined according to a stored vertex array (A.sub.v). Therefore, for the exemplary triangle strip of FIG. 13, an index array for a triangle strip (A.sub.ts) can be defined as follows: A.sub.ts =(P1, P2, P3, P4, P5), where each vertex point (P) is further defined by a vertex array (A.sub.v). Alternatively, the index array for the triangle strip may be generated with pointers that identify positions in the vertex array. For instance, with respect to the example of FIG. 13, assume that vertices P1-P5 are defined in positions 1-5, respectively, of a vertex array (A.sub.v). Further, assume that an index array (A.sub.ts) is generated for the triangle strip as follows: A.sub.t =(1, 2, 3, 4, 5). To determine the coordinates of each of the triangles, (T1, T2, T3) in the triangle strip, a sliding window (that is three positions wide) may be used to read the pointers from the index array and extract the data from the vertex array. For example, returning to the example for FIG. 13, with the sliding window placed at the first position in the array, the pointers from the first three positions of the index array A.sub.ts (i.e., 1, 2, 3) may be used to read the corresponding positions in the vertex array A.sub.v and extract the coordinates for the triangle T1 (i.e., x1, y1, z1; x2, y2, z2; and x3, y3, z3). The sliding window may then be moved forward one position and the next three positions within the window could be read from the index array A.sub.ts (i.e., 2, 3, 4) to extract the vertex data from the vertex array A.sub.v for the triangle T2, and a similar process may be repeated to extract the vertex data for the triangle T3 of the triangle strip.

Various techniques may be employed to identify and define triangle strips. For example, VR system 28 may be implemented to analyze and identify triangles that have common edges and generate triangle strips for such triangle elements. Alternatively, a conventional graphics utility, such as NVtristrip-an Nvidia utility library, may be provided to perform triangle strip operations. In such a case, the utility may be called by VR system 28 by providing an index array for the triangles, and in response the utility may perform triangle strip operation and output an index array (such as A.sub.ts) for the corresponding triangle strip.

By storing triangle strips in the VR file(s), less memory capacity is required. Further, triangle strips can be handled more efficiently by most state-of-the-art graphics hardware systems. For instance, graphics hardware 18 can be adapted to render triangle strips through a graphics library or application program interface (API), such as OpenGL (an API maintained by a consortium of companies) or Direct 3D (an API maintained by Microsoft Corporation). Accordingly, by providing triangle strip array data in the VR file(s) cache memory requirements for the graphics hardware can be reduced and the data for rendering the complex virtual environment can be provided in a more optimized format.

Referring again to FIG. 9, a list of occluder candidates can be built from the 3D model data (step S.50). Additionally, a collision detection hierarchy can be generated based on the 3D model (step S.52). Although FIG. 9 illustrates the octree as being constructed before the occluders list and collision detection hierarchy are built, steps S.46 and S.48 (related to the octree) can be performed in any order relative to steps S.50 (related to the occluders list) and S.52 (related to the collision detection hierarchy). For example, as indicated above, these steps may be performed simultaneously or in parallel by VR system 28. Therefore, the exemplary flow diagram of FIG. 9 should not be construed as limiting the order by which certain steps are performed and, additionally, modifications to the order and nature of the steps of FIG. 9 may be implemented, consistent with the principles of the invention.

When rendering frames based on the VR file(s), there are generally two types of visibility detection and culling that must be performed. One type is view frustum culling, which is performed to remove elements or objects in the complex virtual environment that are outside the field of view. Another type is occlusion culling, which is performed to identify and remove elements or objects that are blocked from view by other elements or objects that are closer to the viewer or camera position. Consistent with embodiments of the invention, both types of visibility detection and culling may be performed on a cell-by-cell basis using the octree defined in the VR file(s). Additionally, to improve the performance of occlusion culling and real-time interaction with the user, an occluders candidate list may be provided in the VR file(s). As further described below, occluder candidates can be analyzed during rendering to more quickly identify those elements or objects that are occluded for each frame.

As illustrated in FIG. 9, occluder candidates may be generated during pre-processing of a 3D model. Generally, occluder candidates represent elements or primitives that have characteristics (such as a large surface areas) that classify them as global candidates for consideration when perform occlusion culling. Thus, to identify occluder candidates, VR system 28 may analyze elements represented in the 3D model to identify large objects (such as walls, floors, etc.) that have characteristics indicative of good occluder properties (i.e., they are likely to block the view of other elements). Various techniques, such area and/or shape analysis, may be performed to determine whether an object classifies as a good occluder candidate. Consistent with embodiments of the invention, FIG. 14 illustrates an exemplary flow diagram for generating and building a list of occluders. As indicated above, all identified occluder candidates may be stored together as a separate list in octree file 52 of the VR file(s). Alternatively, each occluder candidate may be merged with the octree and stored relative to nodes of the octree for cells occupied by the occluder candidate.

When performing simulation, collisions with objects may be detected and simulated to replicate real-world phenomena. The task of collision detection can be complex, especially for environments based on massive models. To improve such performance, spatial partitioning of the environment may also be performed during pre-processing to provide a collision detection hierarchy. In particular, as illustrated in FIG. 9, a collision detection hierarchy may be developed from the 3D model. Various techniques, such as grid subdivision processes, may be used to generate the collision detection hierarchy. With grid subdivision, the modeled environment (including all dynamic and non-dynamic tessellation elements) may be divided into a grid of equally sized cubes. After allocating elements or primitives (such as polygons or triangles) to the cubes, a bounding box tree (such as an axis-aligned bounding box (AABB) tree) may be created for each cube. Each bounding box can be created by dividing a cube into two equally sized cells or cubes and then further dividing the cubes until a cube is empty or contains fewer than a predetermined number of elements or primitives. As with octrees, each level of the bounding box may be represented by nodes that hierarchically related to one another in accordance with each level of division. This hierarchy of bounding boxes may be stored to provide the collision detection hierarchy (such as collision detection file 56) for the VR file(s) Consistent with embodiments of the invention, FIG. 15 illustrates an exemplary flow diagram for creating a collision detection hierarchy.

Referring again to FIG. 9, after analyzing and processing the 3D model data, the VR file(s) are stored (step S.54). As illustrated in the exemplary embodiment of FIG. 5, the VR file(s) may include an octree file 52 and a collision detection file 56, which may be stored separately or together as part of one general VR file. Once the VR file(s) are created, run-time operations may be performed to provide interactive displays of the complex virtual environment on a real-time basis.

FIG. 14 is an exemplary flow diagram for identifying and building a list of occluder candidates, consistent with embodiments of the invention. The exemplary flow diagram of FIG. 14 may be implemented through various systems or environments during pre-processing, such as the system environment 10 of FIG. 1 or the network environment 50 of FIG. 2. For purposes of illustration, however, reference will be made to the embodiment of FIG. 1 to describe the flow diagram of FIG. 14.

As illustrated in FIG. 14, neighboring triangle elements are identified (step S.70). To identify neighboring triangles, VR system 28 may analyze the data for all triangle elements represented in the complex environment (i.e., all non-dynamic tessellation elements, including those that were triangulated). When analyzing the data, the defined edges of each triangle element may be analyzed to determine if it has a common edge with other triangle elements. Triangle elements that are found to have common edges and that are within the same plane may be identified as neighboring triangles. With respect to dynamic tessellation elements, such elements may also be analyzed in a similar manner (in which case the dynamic tessellation elements may be triangulated) or they may be entirely ignored for the purposes of identifying occluder candidates.

After identifying neighboring triangles, the neighboring triangles are merged into polygons (step S.72). For example, VR system 28 may merge each set of neighboring triangles that are determined to be co-planar and redefine them through data representative of a polygon. Each merged set of neighboring triangles are then analyzed to determine if the resulting polygon is convex (step S.74). A merged polygon may be considered convex if it is not possible to pass a line through the polygon and intersect more than two sides of the polygon. If a line can be passed through the polygon and intersect more than two sides, then the polygon is not convex but instead concave. Consistent with embodiments of the invention, only merged triangles resulting in convex polygons may be considered for purposes of identifying candidate occluders.

If a merged polygon is convex (step S.74; Yes), then processing continues to determine the area of the polygon (step S.78). The polygon (or candidate occluder) and its determined area may then be stored for further processing and sorting. If a set of neighboring triangles when merged do not form a convex polygon (step S.74; No), then the polygon is rejected from further consideration (step S.76). Additional neighboring triangles are merged and analyzed in a similar fashion until all neighboring triangles have been processed (step S.80; No).

As illustrated in FIG. 14, candidate occluders (i.e., all merged polygons that have been determined to be convex) are then sorted (step S.82) in order to identify global occluder candidates for the complex environment. The global occluder candidates are then stored (step S.84). As indicated above, the global occluder candidates may either be stored as a separate list in the VR file(s) or they may merged into the octree according to the cell level or node of the octree within which they are fully contained.

The sorting of candidate occluders (step S.82) may be performed using various approaches or techniques. For example, candidate occluders may be sorted and selected according to predetermined thresholds relative to characteristics such as area or shape. Alternatively, a predetermined number