Interference checking method
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (10)
-
-
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. - View Dependent Claims (12, 13)
-
-
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. - View Dependent Claims (15, 16, 17, 18, 19, 20)
-
Specification