Computerized method and apparatus using containment relationships to represent objects in a three-dimensional space, and for moving therethrough

• US 5,414,801 A
• Filed: 06/11/1991
• Issued: 05/09/1995
• Est. Priority Date: 06/11/1991
• Status: Expired due to Fees

• Current Assignee: Nxview Technologies, Inc., Virtus Entertainment, Inc.
• Original Assignee: Virtus Corporation
• Inventors: Easter, David W., Smith, David A.
• Primary Examiner(s): JANKUS, ALMIS R
• Application Number:
  US07/714,387
• Time in Patent Office: 1,428 Days
• Field of Search: 395/119, 395/120, 395/121, 395/122, 395/125, 395/127, 395/141, 395/155, 395/161, 340/706, 340/709, 340/710, 345/157, 345/160, 345/161
• US Class Current: 345/419
• CPC Class Codes: G06T 15/10 Geometric effects

Abstract

A three-dimensional space may be rendered in a computer graphics system by representing the three-dimensional space as a plurality of convex polyhedra and representing the containment relationships among the plurality of convex polyhedra. Connection relationships among the convex polyhedra, including the location of holes in the connected surfaces, are also preferably represented. Containment and connection relationships are preferably represented using a containment logical tree and a connection logical graph. Three-dimensional graphics representations can thereby be rendered in a real time using a low cost, graphics processor. Efficient movement through three-dimensional space along all six degrees of freedom is also provided by using a two-dimensional pointing device, preferably a mouse, in combination with a function selector, preferably a pair of keys on the mouse. Use of the mouse without the function selection keys allows movement in a first plane in the three-dimensional space rendition, and use of the mouse in combination with the first function selection key allows movement in a second plane in the three-dimensional space rendition. Use of the mouse in combination with the second function key allows rotation in three-dimensional space rendition. Preferably, the six degrees of movement are implemented using predetermined combinations of mouse movement and function key selection to provide user intuitive movement through the three-dimensional space rendition along all six degrees of freedom.

Claims

1. A graphics display system comprising:

two-dimensional graphics displaying means; and

graphics processing means for a plurality of three-dimensional objects, a first one of said objects being contained within a second one of said objects, said graphics processing means comprising;

means for representing said plurality of three-dimensional objects as a corresponding plurality of convex polyhedra;

means for indicating containment relationships among said plurality of convex polyhedra corresponding to containment relationships among said plurality of three-dimensional objects, including said first object which is contained within said second object; and

means for rendering a two-dimensional representation of the plurality of three-dimensional objects by selectively rendering only some of said convex polyhedra on said graphics displaying means, based upon the containment relationships in said containment indicating means, such that said first object is not rendered on said graphics displaying means upon rendering said second object from a perspective outside said second object, and said second object is not rendered on said graphics displaying means upon rendering said first object from a perspective inside said first object.

2. The graphics display system of claim 1 wherein said containment indicating means comprises a containment logical tree for indicating said containment relationships.

3. The graphics display system of claim 1 further comprising means for indicating connection relationships among said plurality of three-dimensional objects.

4. The graphics display system of claim 1 wherein said connection indicating means comprises means for indicating connection of at least a first surface of a third one of said convex polyhedra to at least a second surface of a fourth one of said convex polyhedra.

5. The graphics display system of claim 4 wherein said connection indicating means further comprises means for indicating a location of at least one hole between said at least a first surface which is connected to said at least a second surface.

6. The graphics display system of claim 3 wherein said connection indicating means comprises a connection logical graph for indicating said connection relationships.

7. A graphics display method for displaying a plurality of three-dimensional objects, a first one of said objects being contained within a second one of said objects, said graphics display method comprising the steps of:

representing in a graphics processor, said plurality of three-dimensional objects as a corresponding plurality of convex polyhedra;

generating in the graphics processor, a representation of containment relationships among said plurality of convex polyhedra corresponding to containment relationships among said plurality of three-dimensional objects including said a first object which is contained within said second object; and

displaying the plurality of convex polyhedra on a two-dimensional display by selectively rendering only some of said polyhedra on said two-dimensional display based on the containment relationships represented in the graphics processor, such that said first object is not rendered on said graphics display upon rendering said second object from a perspective outside said second object, and said second object is not rendered on said graphics display upon rendering said first object from a perspective inside said first object.

8. The graphics display method of claim 7 wherein said generating step comprises the step of generating a containment logical tree for indicating the containment relationships among said plurality of convex polyhedra.

9. The graphics display method of claim 7 further comprising the step of generating a representation of the connection relationships among said plurality of convex polyhedra corresponding to connection relationships among said plurality of three-dimensional objects.

10. The graphics display method of claim 9 wherein said connection relationships generating step comprises the step of representing that at least a first surface of a third one of said convex polyhedra is connected to at least a second surface of a fourth one of said convex polyhedra.

11. The graphics display method of claim 10 wherein said surface connection representing step further comprises the step of representing a location of at least one hole between said at least a first surface which is connected to said at least second surface.

12. The graphics display method of claim 9 wherein said connection relationships generating step comprises the step of generating a connection logical graph for representing said connection relationships.

13. Apparatus for moving through a computer-generated three-dimensional space rendition, said moving apparatus comprising:

two-dimensional graphical display means, for displaying a three-dimensional space rendition thereon;

two-dimensional pointing means, for moving a reference on said two-dimensional graphical display means in response to two-dimensional movement of said two-dimensional pointing means;

function selection means;

first means for moving in a first plane in the displayed three-dimensional space rendition, in response to movement of said two-dimensional pointing means; and

second means for moving in a second plane in the displayed three-dimensional space rendition, in response to the combination of selection of said function selection means and two-dimensional movement of said two-dimensional pointing means;

wherein said second moving means comprises means for rising up and sinking down in a vertical plane of the displayed three-dimensional space rendition, and for moving left and moving right in the horizontal plane of the displayed three-dimensional space rendition, in response to the combination of selection of said first function selection means and forward, backward, left and right movement, respectively, of said two-dimensional pointing means.

14. The moving apparatus of claim 13 wherein said first moving means comprises means for moving forward, moving backward, turning left and turning right in a horizontal plane of the displayed three-dimensional space rendition, in response to forward, backward, left and right movement, respectively, of said two-dimensional pointing means.

15. The moving apparatus of claim 13 wherein said two-dimensional pointing means comprises a mouse, and wherein said function selection means comprises a key.

16. The moving apparatus of claim 15 wherein said key comprises a key on said mouse.

17. The moving apparatus of claim 15 further comprising a keyboard including a plurality of keys, and wherein said key comprises a predetermined one of said keyboard keys.

18. Apparatus for moving through a computer-generated three-dimensional space rendition, said moving apparatus comprising:

two-dimensional graphical display means, for displaying a three-dimensional space rendition thereon;

two-dimensional pointing means, for moving a reference on said two-dimensional graphical display means in response to two-dimensional movement of said two-dimensional pointing means;

function selection means;

first means for moving in a first plane in the displayed three-dimensional space rendition, in response to movement of said two-dimensional pointing means; and

second means for moving in a second plane in the displayed three-dimensional space rendition, in response to the combination of selection of said function selection means and two-dimensional movement of said two-dimensional pointing means;

second function selection means; and

means for rotating in the displayed three-dimensional space rendition, in response to the combination of selection of said second function selection means and two-dimensional movement of said two-dimensional pointing means;

wherein said rotating means comprises means for rotating up and rotating down relative to a first axis in the horizontal plane of the displayed three-dimensional space rendition, and for rotating up and rotating down relative to a second axis in the horizontal plane of the displayed three-dimensional space rendition, in response to the combination of selection of said second function selection means and forward, backward, left and right movement, respectively, of said two-dimensional pointing means.

19. Apparatus for moving through a computer-generated three-dimensional space rendition, said moving apparatus comprising:

two-dimensional graphical display means, for displaying a three-dimensional space rendition thereon;

two-dimensional pointing means, for moving a reference on said two-dimensional graphical display means in response to two-dimensional movement of said two-dimensional pointing means;

function selection means; and

means for moving in six degrees of freedom through the displayed three-dimensional space rendition, said six degrees of freedom including translation along three orthogonal axes and rotation about said three orthogonal axes, in response to the combination of selection of said function selection means and two-dimensional movement of said two-dimensional pointing means;

wherein said function selection means comprises first and second function selection means;

wherein said six degrees of freedom comprise translation along mutually orthogonal x, y and z axes, and rotation about said x, y and z axes, and wherein said two-dimensional pointing means moves the reference horizontally and vertically along said graphical display means, and wherein said moving means comprises;

means for translating through the displayed three-dimensional space rendition along said y axis in response to vertical movement of said two-dimensional pointing means and for rotating about said z axis in response to horizontal movement of said two dimensional pointing means;

means for translating through the displayed three-dimensional space rendition along said z axis in response to vertical movement of said two dimensional pointing means and selection of said first function selection means, and for translating along said x axis in response to horizontal movement of said two-dimensional pointing means and selection of said first function selection means; and

means for rotating in the displayed three-dimensional space rendition about said x axis in response to vertical movement of said two-dimensional pointing means and selection of said second function selection means, and for rotating about said y axis in response to horizontal movement of said two-dimensional pointing means and selection of said second function selection means.

20. The moving apparatus of claim 19 wherein said two-dimensional pointing means comprises a mouse, and wherein said function selection means comprises a key.

21. The moving apparatus of claim 20 wherein said key comprises a key on said mouse.

22. The moving apparatus of claim 20 further comprising a keyboard including a plurality of keys, and wherein said key comprises a predetermined one of said keyboard keys.

23. A graphics display system for rendering a three-dimensional space including a plurality of three-dimensional objects, a first one of said objects being contained within a second one of said objects, and for moving through the three-dimensional space rendition, said graphics display system comprising:

two-dimensional graphics displaying means;

two-dimensional pointing means, for moving a reference on said two-dimensional graphics displaying means;

function selection means; and

graphics processing means, said graphics processing means comprising;

means for representing said plurality of three-dimensional objects as corresponding plurality of convex polyhedra;

means for indicating containment relationships among said plurality of convex polyhedra corresponding to containment relationships among said plurality of three-dimensional objects including said first object which is contained within said second object;

means for rendering a two-dimensional representation of the plurality of three-dimensional objects by selectively rendering only some of said convex polyhedra on said graphics displaying means, based upon the containment relationships in said containment indicating means, such that said first object is not rendered on said graphics displaying means upon rendering said second object from a perspective outside said second object, and said second object is not rendered on said graphics displaying means upon rendering said first object from a perspective inside said first object; and

means for moving in six degrees of freedom through the displayed three-dimensional space rendition on said graphics displaying means, said six degrees of freedom including translation along three orthogonal axis and rotation about said three orthogonal axis, in response to the combination of selection of said function selection means and two-dimensional movement of said two-dimensional pointing means.

24. The graphics display system of claim 23 wherein said containment indicating means comprises a containment logical tree for indicating said containment relationships.

25. The graphics display system of claim 23 wherein said graphics processing means further comprises means for indicating connection relationships among said plurality of convex polyhedra.

26. The graphics display system of claim 25 wherein said connection indicating means comprises means for indicating connection of at least a first surface of a third one of said convex polyhedra to at least a second surface of a fourth one of said convex polyhedra.

27. The graphics display system of claim 26 wherein said connection indicating means further comprises means for indicating a location of at least one hole between said at least a first surface which is connected to said at least a second surface.

28. The graphics display system of claim 25 wherein said connection indicating means comprises a connection logical graph for indicating said connection relationships.

29. The graphics display system of claim 23 wherein said function selection means comprises first and second function selection means.

30. The graphics display system of claim 29 wherein said six degrees of freedom comprise translation along mutually orthogonal x,y and z axes, and rotation about said x, y and z axes, and wherein said two-dimensional pointing means moves the reference horizontally and vertically along said graphical displaying means, and wherein said moving means comprises:

means for translating through the displayed three-dimensional space rendition along said y axis in response to vertical movement of said two-dimensional pointing means and for rotating about said z axis in response to horizontal movement of said two dimensional pointing means;

means for translating through the displayed three-dimensional space rendition along said z axis in response to vertical movement of said two dimensional pointing means and selection of said first function selection means, and for translating along said x axis in response to horizontal movement of said two-dimensional pointing means and selection of said first function selection means; and

means for rotating in the displayed three-dimensional space rendition about said x axis in response to vertical movement of said two-dimensional pointing means and selection of said second function selection means, and for rotating about said y axis in response to horizontal movement of said two-dimensional pointing means and selection of said second function selection means.

31. The graphics display system of claim 23 wherein said two-dimensional pointing means comprises a mouse, and wherein said function selection means comprises a key.

32. The graphics display system of claim 31 wherein said key comprises a key on said mouse.

33. The graphics display system of claim 31 further comprising a keyboard including a plurality of keys, and wherein said key comprises a predetermined one of said keyboard keys.

34. A system for rendering a plurality of three-dimensional objects, a first one of said objects being contained within a second one of said objects, said rendering system comprising:

two-dimensional graphics displaying means;

means for indicating containment relationships among said plurality of three-dimensional objects including that said first object is contained within said second object; and

means for displaying a two-dimensional representation of said plurality of objects on said two-dimensional graphics displaying means, from a display perspective which is outside said second object, by rendering said second object and by not rendering said first object, based upon the containment relationships in said containment indicating means, and for displaying a two-dimensional representation of said plurality of objects on said two-dimensional graphics displaying means, from a display perspective which is inside said first object, by rendering said first object and by not rendering said second object, based upon the containment relationships in said containment indicating means.

35. The rendering system of claim 34 wherein said containment indicating means comprises a containment logical tree for indicating said containment relationships.

36. The rendering system of claim 34 further comprising means for indicating connection relationships among said plurality of three-dimensional objects.

37. The rendering system of claim 36 wherein said connection indicating means comprises means for indicating connection of at least a first surface of a third one of said convex polyhedra to at least a second surface of a fourth one of said convex polyhedra.

38. The rendering system of claim 36 wherein said connection indicating means comprises a connection logical graph for indicating said connection relationships.

39. The rendering system of claim 37 wherein said connection indicating means further comprises means for indicating a location of at least one hole between said at least a first surface which is connected to said at least a second surface.

40. A method for rendering a plurality of three-dimensional objects, a first one of said objects being contained within a second one of said objects, said rendering method comprising the steps of:

indicating in a graphics processor, containment relationships among said plurality of three-dimensional objects including that said first object is contained within said second object;

displaying a two-dimensional representation of said plurality of objects on a two-dimensional graphics display, from a display perspective which is outside said second object, by rendering said second object and by not rendering said first object, based upon the containment relationships in the graphics processor; and

displaying a two-dimensional representation of said plurality of objects in said two-dimensional graphics display, from a display perspective which is inside said first object, by rendering said first object and by not rendering said second object, based upon the containment relationships in the graphics processor.

41. The rendering method of claim 40 wherein said indicating step comprises the step of generating a containment logical tree in the graphics processor, for indicating the containment relationships among said plurality of three-dimensional objects.

42. The rendering method of claim 40 further comprising the step of generating a representation of the connection relationships among said plurality of three-dimensional objects.

43. The rendering method of claim 42 wherein said connection relationships generating step comprises the step of representing that at least a first surface of a third one of said three-dimensional objects is connected to at least a second surface of a fourth one of said three-dimensional objects.

44. The rendering method of claim 42 wherein said connection relationships generating step comprises the step of generating a connection logical graph in the graphics processor for representing said connection relationships.

45. The rendering method of claim 43 wherein said surface connection representing step further comprises the step of representing a location of at least one hole between the at least a first surface which is connected to said at least a second surface.