Interference checking method

• US 5,943,056 A
• Filed: 06/21/1996
• Issued: 08/24/1999
• Est. Priority Date: 07/11/1995
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Maruyama, Tsugito, Sato, Yuichi, Hirata, Mitsunori
• Primary Examiner(s): Powell, Mark R.
• Application Number:
  US08/668,145
• Time in Patent Office: 1,159 Days
• Field of Search: 345/418-420, 345/423, 345/433-38
• US Class Current: 345/419
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

An interference checking method for checking the interference between two objects in the shape of non-convex polyhedrons, comprising the steps of producing a convex hull for each of the non-convex polyhedrons, and checking the interference of the convex hull of one object with the convex hull of the other object; covering each of polygons which constitute each of the non-convex polyhedrons with a plurality of leaf spheres which have a predetermined radius and which are arranged on each polygon when the distance between the convex hulls becomes not more than a preset value, and sequentially enveloping the leaf spheres with hierarchical spheres so as to produce a binary tree of hierarchical envelope spheres; obtaining a pair of nearby spheres closest by checking the interference between envelope spheres of an upper grade on the basis of the structure of the binary tree, disassembling the interfering envelope spheres into envelope spheres of a lower grade, checking the interference between the envelope spheres of the lower grade, and repeating the interference check process and the disassembly process until no interference is detected; obtaining a nearby polygon pair which corresponds to the pair of nearby spheres; and checking the interference between the nearby polygon pair.

Claims

1. An interference checking method implemented using a computer system for checking the interference between a non-convex polyhedron and another object, comprising:

dividing the vertexes constituting said non-convex polyhedron into a plurality of vertex groups in each of which the difference between the coordinate values of a first axis (X-axis) of two arbitrary vertexes is zero or not more than a very small number ε

;

producing a two-dimensional convex hull using a computer program stored in a memory for each of said groups of vertexes on the plane of second and third axes (YZ plane);

producing three dimensional convex hulls using a second computer program stored in said memory by merging each pair of adjacent two-dimensional convex hulls, and thereafter sequentially merging adjacent three-dimensional convex hulls, thereby producing an intended convex hull of said non-convex polyhedron;

checking the interference between said intended convex hull and said other object;

disassembling said convex hull when said convex hull and said another object begin to interfere with each other; and

checking the interference between said non-convex polyhedron and said other object.

2. An interference checking method according to claim 1, wherein said step of merging adjacent three-dimensional convex hulls includes the steps of:

obtaining an upper bridge which is situated on the topmost of the edges which connect the vertexes of said adjacent three-dimensional convex hulls;

obtaining a triangular polygon which incorporates said upper bridge as one side and which is situated at the topmost position;

wrapping the space between adjacent three-dimensional convex hulls with said triangular polygon;

obtaining a triangular polygon which is situated at the topmost position with the exception of the already obtained triangular polygons and is adjacent to one of them;

wrapping the space between adjacent three dimensional convex hulls with said triangular polygon; and

repeating said obtaining process and said wrapping process so as to merge three-dimensional convex hulls.

3. An interference checking method according to claim 1, wherein said step of producing a two-dimensional convex hull for each of groups of vertexes in which the difference in the coordinate value of said first axis is zero or not more than a very small value ε

includes the steps of;

dividing said vertexes into a plurality of vertex groups in each of which the difference between the coordinate values of a second axis (Y-axis) of two arbitrary vertexes is zero or not more than a very small value;

producing a one-dimensional convex hull by linking the vertexes in a descending order of coordinate value of a third axis (Z-axis) in each of said groups of vertexes;

merging adjacent one-dimensional convex hulls so as to produce a two-dimensional convex hull; and

sequentially merging adjacent two-dimensional convex hulls so as to produce an intended two-dimensional convex hull.

4. An interference checking method according to claim 3, wherein said step of merging adjacent two-dimensional convex hulls includes the steps of:

obtaining an upper bridge and a lower bridge which are situated on the topmost and the lowermost, respectively, among from the edges which connect the vertexes of said adjacent two-dimensional convex hulls; and

producing a new two-dimensional convex hull by linking the adjacent two-dimensional convex hulls by each of said upper bridge and said lower bridge.

5. An interference checking method according to claim 1, further comprising the step of:

producing and outputting a nearby-point linear list having a data structure obtained by arranging the vertexes of all triangular polygons which constitute said convex hull so as to link said vertexes in a first direction ("next" direction) and arranging vertexes each of which is connected to a vertex of interest via a polygon edge, so as to link said vertexes to the vertex of interest in a second direction ("branch" direction), wherein

said step of checking interference between said convex hull and said another object is performed using said nearby-point linear list.

6. An interference checking method according to claim 5, further comprising the step of:

storing said nearby-point linear list in an external storage medium as a file;

and reading said nearby-point linear list when said nearby-point linear list is necessary so as to develop said nearby-point linear list in a memory of a system.

7. An interference checking method implemented using a computer system, for checking the interference between two objects in the shape of non-convex polyhedrons, comprising:

covering each of polygons which constitute each of said non-convex polyhedrons with a plurality of leaf spheres which have a predetermined radius and which are arranged on each polygon, and sequentially enveloping said leaf spheres with hierarchical spheres so as to produce a binary tree of hierarchical envelope spheres;

obtaining a pair of nearby spheres between said two objects by checking interference between envelope spheres if an upper grade on the basis of the structure of said binary tree, disassembling the interfering envelope spheres into envelope spheres of a lower grade, checking the interference between the envelope spheres of said lower grade, and repeating the interference check process and the disassembly process until no interference is detected;

obtaining a nearby polygon pair which corresponds to said pair of nearby spheres; and

checking the interference between said nearby polygon pair;

wherein said radius of said leaf spheres is determined on the basis of the radius of spheres which envelope the corresponding non-convex polyhedron and the number of polygons constituting said non-convex polyhedron in which the smaller the number of polygons constituting said non-convex polyhedron is, the smaller said radius of said leaf spheres is.

8. An interference checking method implemented using a computer system for checking the interference between two objects in the shape of non-convex polyhedrons, comprising:

covering each of polygons which constitute each of said non-convex polyhedrons with a plurality of leaf spheres which have a predetermined radius and which are arranged on each polygon, and sequentially enveloping said leaf spheres with hierarchical spheres so as to produce a binary tree of hierarchical spheres;

obtaining a pair of nearby spheres between said two objects by checking the interference between envelope spheres of an upper grade, disassembling the interfering envelope spheres into envelope spheres of a lower grade, checking interference between the envelope spheres of said lower grade, and repeating the interference check process and the disassembly process until no interference is detected;

obtaining a nearby polygon pair which corresponds to said pair of nearby spheres; and

checking the interference between said nearby polygon pair;

wherein the distance between leaf spheres is the distance between centers of said leaf spheres, the distance between a leaf sphere and a non-leaf sphere is the distance obtained subtracting the radius of said non-leaf sphere from the distance between the centers of the two spheres, and the distance between non-leaf spheres is the distance obtained by subtracting the radii of the two non-leaf spheres from the distance between the centers of said two non-leaf spheres.

9. An interference checking method implemented using a computer system for checking the interference between two objects in the shape of non-convex polyhedrons, comprising:

producing a convex hull for each of said non-convex polyhedrons, and checking the interference of said convex hull of one object with said convex hull of the other object;

covering each of polygons which constitute each of said non-convex polyhedrons with a plurality of leaf spheres which have a predetermined radius and which are arranged on each polygon when the distance between said convex hulls becomes not more than a preset value, and sequentially enveloping said leaf spheres with hierarchical spheres so as to produce a binary tree of hierarchical envelope spheres;

obtaining a pair of nearby spheres between said two objects by checking the interference between envelope spheres of an upper grade on the basis of the structure of said binary tree, disassembling the interfering envelope spheres into envelope spheres of a lower grade, checking the interference between the envelope spheres of said lower grade, and repeating the interference check process and the disassembly process until no interference is detected;

obtaining a nearby polygon pair which corresponds to said pair of nearby spheres; and

checking the interference between said nearby polygon pair.

10. An interference checking method according to claim 9, wherein when said distance between said convex hulls in a rectangular coordinate system becomes not more than a predetermined value, a virtual fourth axis is imagined, and a distance between said two convex hulls in the direction of said fourth axis is set at a constant value ε

.

11. An interference checking method implemented using a computer system for checking the interference between two objects each of which is composed of a set of non-convex polyhedrons, said method comprising:

producing, with regard to each object, a metatree of hierarchical envelope spheres by covering each non-convex polyhedron with spheres and then hierarchically enveloping said spheres with envelope spheres;

obtaining a pair of nearby spheres between said objects by checking the interference between envelope spheres of an upper grade on the basis of the structure of said metatree, disassembling the interference envelope spheres into envelope spheres of a lower grade, checking the interference between the envelope spheres of said lower grade, and repeating the interference check process and the disassembly process until no interference is detected;

obtaining a pair of nearby non-convex polyhedrons which correspond to said pair of nearby spheres and producing a convex hull for each non-convex polyhedron of said pair;

checking the interference between said convex hulls;

disassembling each of said convex hulls when said convex hulls begin to interfere with each other; and

checking the interference between said non-convex polyhedrons.

12. An interference checking method according to claim 11, wherein said step of checking the interference between said non-convex polyhedrons includes the steps of:

covering each of polygons which constitute each of said non-convex polyhedrons with a plurality of leaf spheres which have a predetermined radius and which are arranged on each polygon, and sequentially enveloping said leaf spheres with hierarchical spheres so as to produce a binary tree of hierarchical envelope spheres;

obtaining a pair of nearby spheres between said non-convex polyhedrons by checking interference between envelope spheres of an upper grade on the basis of the structure of said binary tree, disassembling the interfering envelope spheres into envelope spheres of a lower grade, checking the interference between the envelope spheres of the said lower grade, and repeating the interference check process and the disassembly process until no interference is detected;

obtaining a nearby polygon pair which corresponds to said pair of nearby spheres; and

checking the interference between said nearby polygon pair.

13. An interference checking method according to claim 12, further comprising the steps of:

repeating said interference check for said nearby polygon pair;

updating said pair of nearby non-convex polyhedrons and said nearby polygon pair at intervals of predetermined cycles; and

repeating said interference check for a new nearby polygon pair.

14. An interference checking method implemented using a computer for checking the interference between two objects in the shape of a polyhedron, comprising:

covering each of polygons which constitute each of said polyhedrons with a plurality of spheres which have a predetermined radius and which are arranged on each polygon, and sequentially enveloping said spheres with hierarchical spheres so as to produce a binary tree of hierarchical envelope spheres as preprocessing;

performing a bubble collision algorithm which includes a first step of obtaining a pair of nearby spheres by checking the interference between envelope spheres of an upper grade on the basis of the structure of said binary tree, disassembling the interfering envelope spheres into envelope spheres of a lower grade, checking the interference between the envelope sphere of said lower grade, and repeating the interference check process and the disassembly process until no interference is detected, a second step of obtaining and storing the pair of polygons which correspond to said pair of nearby spheres as a nearby polygon pair, and a third step of executing an interference check for said nearby polygon pair;

repeating said interference check for said nearby polygon pair for a predetermined number of times;

updating said nearby polygon pair in accordance with said bubble collision algorithm every time the predetermined number of interference checks for said nearby polygon pair are finished; and

repeating said interference check for a new nearby polygon pair.

15. An interference checking method according to claim 14, further comprising the steps of:

producing a convex hull for each of said non-convex polyhedrons; and

checking the interference between said convex hulls;

wherein when said convex hulls begin to interfere with each other, the interference check is executed in accordance with said bubble collision algorithm.

16. An interference checking method according to claim 14, further comprising the steps of:

measuring the computation time in said bubble collision algorithm; and

changing the cycle of nearby polygon pair updating process on the basis of said computation time.

17. An interference checking method according to claim 14, further comprising the steps of:

monitoring the amount of movement of a moving object; and

updating said nearby polygon pair in accordance with said bubble collision algorithm even in the middle of the cycle of nearby polygon pair updating process when said amount of movement is larger than a preset value.

18. An interference checking method according to claim 14, further comprising the steps of:

monitoring the moving speed of a moving object; and

updating said nearby polygon pair in accordance with said bubble collision algorithm even in the middle of the cycle of nearby polygon pair updating process when said moving speed is larger than a preset speed.

19. An interference checking method according to claim 14, further comprising the steps of:

measuring the distance between said polygon pair; and

updating said nearby polygon pair in accordance with said bubble collision algorithm even in the middle of the cycle of nearby polygon pair updating process when the ratio of the current distance and the preceding distance is larger than a preset value.

20. An interference checking method according to claim 15, further comprising the step of:

holding the results of the preceding interference check for said convex hulls or said nearby polygon pair when said two objects of interference check are stationary; and

outputting said results as those of the current interference check.