Interference checking method

Details Interference checking method Interference checking method

1996-06-21

1999-08-24

Powell, Mark R.

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

G06T 1700

Patent

active

059430567

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.

REFERENCES:
patent: 4578757 (1986-03-01), Stark
patent: 4922430 (1990-05-01), Wavish
patent: 5056031 (1991-10-01), Nakano et al.
patent: 5150452 (1992-09-01), Pollack et al.
patent: 5347459 (1994-09-01), Greenspan et al.
patent: 5444838 (1995-08-01), Kommrusch et al.
patent: 5619629 (1997-04-01), Yutaka
patent: 5675720 (1997-10-01), Sato et al.
Preparata, et al, "Convex Hulls of Finite Sets of Points in Two and Three Dimensions", Communications of the ACM, pp. 87-93, Feb. 1977.
Edelsbrunner, et al, "Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms", ACM Transactions on Graphics, 9(1). pp. 66-104, 1990.
Miller, et al, "Efficient Parallel Convex Hull Algorithms", IEEE Transactions on Computers, vol. 37, No. 12, pp. 1605-1618, Dec. 1988.
D. Henrich, et al., "Fast Distance Computation for On-Line Collision Detection with Multi-Arm Robots", 1992 IEEE, pp. 2514-2519.
S. Quinlan, "Efficient Distance Computation Between Non-Convex Objects", 1994 IEEE, pp. 3324-3329.
F. Thomas, et al., "Interference Detection Between Non-Convex Polyhedra Revisited With a Practical Aim", 1994 IEEE, pp. 587-594.
Gilbert et al., A Fast Procedure for Computing the Distance Between Complex Objects in Three-Dimensional Space, IEEE, Journal of Robotics and Automation, vol. 4, No. 2, 1988, pp. 193-203.
Liu et al., A New Solid Model Named HSM for Checking an Interference between Moving Objects, The 6th Science of Lecture of Japan Society of Robotics, Oct. 1988, pp. 105-108.

Affiliated with

Also associated with

Rating

Interference checking method 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 method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interference checking method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-471412