Interference checking apparatus and method for checking interference of objects in computer

• US 6,452,604 B1
• Filed: 03/17/1999
• Issued: 09/17/2002
• Est. Priority Date: 05/12/1998
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Sato, Yuichi
• Primary Examiner(s): Luu, Matthew
• Application Number:
  US09/270,504
• Time in Patent Office: 1,280 Days
• Field of Search: 345/422, 345/958, 345/619, 345/620, 345/621, 700/255, 700/301
• US Class Current: 345/619
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2210/21 Collision detection, intersection

Abstract

An interference checking apparatus approximates the shape of an object with an envelope figure, such as a rectangular parallelepiped, a sphere, etc., and checks static interference among many objects at high speed. In this static interference check, an approximate figure is projected into a space of a lower dimension, pairs of objects with a possibility of interference are focused on in stages, and the number of the pairs is reduced. Then, a precise interference check is performed for the remaining pairs.

Claims

1. An interference checking apparatus for checking an interference state of a plurality of objects generated on a computer, comprising:

a storing unit storing object data representing the plurality of objects;

a projecting unit generating one-dimensional projection data representing each of the plurality of objects using the object data, the projection data representing a segment for each object on a coordinate axis in a coordinate system;

an extracting unit extracting a pair of objects with a possibility of interference from the plurality of objects by comparing the projection data of the plurality of objects;

a judging unit checking an interference between the extracted pair of the objects; and

an outputting unit outputting a result of an interference check.

2. The interference checking apparatus according to claim 1, wherein said extracting unit includes a sorting unit sorting the projection data of the plurality of objects, and extracts the pair of objects, with a possibility of interference by checking an overlapping state of projection data based on a sorting result of the projection data.

3. The interference checking apparatus according to claim 2, wherein

said projecting unit projects the plurality of objects on at least two coordinate axes and calculates the projection data; and

said extracting unit, after checking the overlapping state of the projection;

data in a sorting direction, checks the overlapping state of the projection data in another direction.

4. The interference checking apparatus according to claim 1, wherein said projecting unit includes an approximating unit generating an envelope figure enveloping each of the plurality of objects, and generates projection data corresponding to the envelope figure.

5. The interference checking apparatus according to claim 4, wherein said approximating unit uses one of a rectangular parallelepiped and a sphere for the envelope figure.

6. The interference checking apparatus according to claim 4, further comprising:

a transforming unit performing a coordinate transformation, of the envelope figure, wherein said projecting unit generates the projection data from the envelope figure after the coordinate transformation.

7. The interference checking apparatus according to claim 1, wherein said judging unit includes

a distance calculating unit calculating a distance between two objects in the pair of objects, and judges whether or not the two objects interfere with each other by performing a threshold judgment for the obtained distance.

9. The interference checking apparatus according to claim 1, further comprising:

a selecting unit, when said outputting unit displays a pair of interfering objects, selecting one of the interfering objects; and

an interactive interference checking unit interactively checking interferences while moving the selected object.

8. An interference checking apparatus checking an interference state of a plurality of objects generated on a computer, comprising:

a storing unit storing object data representing the plurality of objects;

a projecting unit generating one-dimensional projection data representing each of the plurality of objects using the object data;

an extracting unit extracting a pair of objects with a possibility of interference from the plurality of objects using the projection data;

a judging unit checking an interference between the extracted pair of the ;

objects;

an outputting unit outputting a result of an interference check;

a selecting unit, when said outputting unit displays a plurality of pairs of interfering objects selecting one of the pairs of interfering objects; and

a displaying unit dividing a display target with a plane in a vicinity of an interference position of the selected pair, into two parts, allowing one of the two parts not to be displayed and displaying an enlarged vicinity of the interference position.

10. An interactive checking apparatus for checking an interference state of a plurality of objects generated on a computer, comprising:

a storing unit storing both position information of vertices composing each of the plurality of objects and parental relation between an object and another object;

an updating unit, when an object moves, updating the position information of the vertices of the moved object, in case of necessity;

a first judging unit performing a combinational interference check among the plurality of objects at one time based on the updated position information on the vertices;

a displaying unit graphically displaying an interference position where interference is judged to occur;

a calculating unit calculating the shortest distance between at least one object in a vicinity of the interferences position when a user selects the at least one object in the vicinity of the interference position displayed graphically and other objects; and

a second judging unit checking interference between the at least one object and the other objects by performing a threshold judgment for the obtained distance.

11. An interference checking apparatus for checking an interference state of at least three objects generated on a computer, comprising:

a first interference checking unit projecting object data representing each of the at least three objects into a lower dimensional space, generating projection data for each object, the projection data representing a scope of a space in which each object exists with coordinate values in the lower dimensional space, and extracting a pair of objects with a possibility of interference from the at least three objects by comparing the projection data of the at least three objects; and

a second interference checking unit checking an interference between the extracted pair of objects.

12. The interference checking apparatus according to claim 11, wherein

said first interference checking unit is faster in operation speed than said second interference checking unit and performs an interference check for all combinations among the at least three objects, and

said second interferences unit is higher in operation accuracy than said first interference checking unit and performs an interference check for all combinations judged to interfere with each other by said first interference unit.

13. The interference checking apparatus according to claim 11, wherein

said first interference checking unit includes:

a projecting unit projecting object data representing each of the at least three objects into a lower dimensional space; and

an extracting unit extracting the pair of objects with a possibility of interference from the at least three objects using projection data, and

said second interference checking unit includes

a judging unit checking the interference between the extracted pair of objects.

14. The interference checking apparatus according to claim 13, further comprising:

a storing unit storing the object data projected by said projecting unit; and

an outputting unit outputting a result of an interference check by said judging unit.

15. A computer-readable recording medium on which is recorded a program for causing a computer to generate a plurality of object models and′

to check an interference state of the plurality of object models, said program comprising;

generating one-dimensional projection data representing each of the plurality of objects using object data representing the plurality of objects, the projection data representing a segment for each object on a coordinate axis in a coordinate system;

extracting a pair of objects with a possibility of interference from the plurality of objects by comparing the projection data of the plurality of objects; and

checking interference between the extracted pair of objects.

16. A computer-readable recording medium on which is recorded a program for causing a computer to generate at least three object models and to check an interference state of the plurality of object models, said program comprising:

projecting object data representing each of the at least three objects into a lower dimensional space, generating projection data for each object, the projection data representing a scope of a space in which each object exists with coordinate values in the lower dimensional space;

extracting a pair of objects with a possibility of interference from the at least three objects by comparing the projection data of the at least three objects; and

checking an interferences between the extracted pair of objects.

17. An interference checking method of checking an interference state of a plurality of objects generated on a computer, comprising:

generating one-dimensional projection data representing each of the plurality of objects using object data representing the plurality of objects, the projection data representing a segment for each object on a coordinate axis in a coordinate system;

extracting a pair of objects with a possibility of interference from the plurality of objects by comparing the projection data of the plurality of objects; and

checking an interference between the extracted pair of objects.

18. An interference checking method of checking an interference state of at least three objects generated on a computer, comprising:

projecting object data representing each of the at least three objects into a lower dimensional space, generating projection data for each object, the projection data representing a scope of a space in which each object exists with coordinate values in the lower dimensional space;

extracting a pair of objects with a possibility of interference from the at least three objects by comparing the projection data of the at least three objects; and

checking an interferences between the extracted pair of objects.