Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
1999-03-17
2002-09-17
Luu, Matthew (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S620000
Reexamination Certificate
active
06452604
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an apparatus for checking the state of interference between the computer graphics (CG) models of objects generated in a computer and the method thereof.
2. Description of the Related Art
Lately, in mechanical CAD (computer-aided design) systems for simulating the assembled state of products, etc., it has been required to check on the state of interference between the components in an assembly model representing the assembled state and to display the position of interference. The conventional checking methods of the state of interference between objects are classified as follows.
(1) A method using an envelope of spheres. The state of interference between objects is judged by enveloping objects with a set of spheres and repeating the check on the interference between the spheres. Technologies corresponding to this method include U.S. Pat. Official Gazette No. 4,578,757 (Stark), U.S. Pat. Official Gazette No. 4,922,430 (Wavish), U.S. Pat. Official Gazette No. 5,056,031 (Nakano et al.), Japanese Patent Laid-open 2-224004 (Kan Nakano et al.), Japanese Patent Laid-open 6-83422 (Kenji Iriguchi et al.), Japanese Patent Laid-open 6-259506 (Miwako Doi et al.) and Japanese Patent Laid-open 7-100733 (Akihiro Goto et al.).
(2) A space is divided into a set of fine grids, and a space map in which codes are allocated to both an area occupied by an object and an unoccupied area, is prepared. Then, the state of interference is judged by retrieving where on the space map other targets are located. A method using an octonal tree belongs to this group. Technologies corresponding to this method include U.S. Pat. Official Gazette No. 5,150,452 (Pollack) and U.S. Pat. Official Gazette No. 5,347,459 (Greenspan et al.) In particular, the method by Greenspan et al. also adopts the method using an envelope of spheres in (1) in combination.
(3) A map consisting of an interfering area: and a non-interfering area is drawn on a configuration space, which is well known in a field of robotics, and interference is measured in this space. Technologies corresponding to this method include U.S. Pat. Official Gazette, No. 5,047,916 (Kondo). In Kondo's method, a configuration space is divided into grids, and a map for interference judgement is prepared.
(4) A method based on the calculation of a distance between the nearest points of a convex polyhedron. Technologies corresponding to this method include a method by Gilbert et al. (E. G. Gilbert, D. W. Johnson and S. S. Keerthi, IEEE Journal of Robotics and Automation, Vol. 4, No. 2, pp. 193-203, 1988).
However, the conventional interference checking methods described above have the following problems.
Out of the conventional interference checking methods, methods (1) through (3) target an arbitrary non-convex object, and though they have a wider application range, they have the following problems compared with method (4) which is used for a convex polyhedron.
Method (1) needs a pretreatment of enveloping an object with spheres, and in the case of a convex polyhedron requires extra calculation compared with the method of Gilbert et al. Since a distance between target objects is not calculated, how much margin is left for interference, etc. cannot be measured.
In method (2), the pretreatment to prepare a map in which space is divided into grids takes a long time. If the environment changes, the map has to be prepared again, and real time processing for environmental fluctuation cannot be performed. Furthermore, since a space is divided into grids, a position cannot be calculated to an accuracy higher than a unit of one grid.
In method (3), it takes a long time to prepare a configuration space. As in method (2), when the environment changes, a map has to be prepared again, and real time processing for environmental fluctuation cannot be performed. When a configuration space is divided into grids like Kondo's method, a position cannot be calculated to an accuracy higher than a unit of one grid.
On the other hand, although method (4) requires no special pretreatment and a distance between target objects can be calculated at high speed, the shape of targets is limited to a convex polyhedron.
When, along with the recent advent of high-performance computers, etc., three-dimensional simulation is performed, many objects are moved in a three-dimensional virtual space. Therefore, a check on interference between the objects is often needed. It is also needed to verify whether or not an assembly component composed of many discrete components can be realized without any interference between the discrete components.
However, since methods (1) through (4) are all checking methods for one-to-one interference between objects, a check has to be repeated for every possible combination of many objects when a check on interference among the objects is required.
Furthermore, since in the case of objects in a recent virtual space, in order to improve reality, an astronomical number of pieces of surface information (polygons) representing an object are used, and a great number of repeated calculations are needed even in the case of a check on one-to-one object interference. When a check on interference among:many objects is made using, such a calculation method, it takes an enormous calculation time and is not realistic.
Since, as the number of objects increases, the calculation time needed for an interference check astronomically increases, it is actually impossible to automatically perform a check on interference among many objects. Under these circumstances, a user manually selects and designates objects to be checked out of many objects, and a check on one-to-one interference between objects is performed for the specific designated objects, if necessary.
SUMMARY OF THE INVENTION
An object of the present invention is to provide an interference checking apparatus for automatically performing an efficient interference check on the CG models of many non-convex objects generated on a computer and the method thereof.
According to the first aspect of the present invention, the interference checking apparatus comprises a storage unit, a projector unit, an extractor unit, a judgement unit and an output unit, and checks the interference state between a plurality of objects generated on a computer.
The storage unit stores object data representing a plurality of objects, and the projector unit generates one-dimensional projection data representing each of the plurality of objects using the object data. The extractor unit extracts a pair of objects with a possibility of interference out of the plurality of objects using the generated projection data, the judgement unit performs the interference check of the extracted pair of objects, and the output unit outputs the result of the interference check.
According to the second aspect of the present invention, the interference checking apparatus comprises a storage unit, an updating unit, a first judgement unit, a display unit, a calculator unit and a second judgement unit, and checks the interference state between a plurality of objects generated on a computer.
The storage unit stores both the position information of vertices composing each of the plurality of objects and the parental relation among the plurality of objects, and the updating unit updates the position information of the vertices of a moved object, if necessary, when the object moves. The first judgement unit performs the check of the interference among the plurality of objects at one time based on the updated position information of the vertices, and the display unit graphically displays an interference position where interference is judged to occur. The calculator unit selects one or more objects in the vicinity of the interference position and calculates the shortest distance between the one or more objects and the other objects, and the second judgement unit performs the interference check between the one or more selected objects and the other objects by judging whether or not the obtain
Fujitsu Limited
Luu Matthew
Staas & Halsey , LLP
LandOfFree
Interference checking apparatus and method for checking... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interference checking apparatus and method for checking..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interference checking apparatus and method for checking... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2855675