Computer graphics processing and selective visual display system – Computer graphics processing – Animation
Reexamination Certificate
2001-12-21
2004-09-14
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Animation
C345S423000, C345S428000, C345S215000, C345S215000, C345S952000, C345S958000
Reexamination Certificate
active
06791549
ABSTRACT:
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 embod
Hubrecht Alain Yves Nestor
Nuydens Tom
Beyer Weaver & Thomas LLP
Nguyen Kimbinh T.
VRcontext s.a.
Zimmerman Mark
LandOfFree
Systems and methods for simulating frames of complex virtual... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for simulating frames of complex virtual..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for simulating frames of complex virtual... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3189226