Patent Document ID: 6054997
Application ID: 08921162
Patent Status: 1

Claim One:
1. A system for determining closest features between two objects wherein each of the objects are represented as a set of features defining a polyhedron, the system comprising: feature selection means for selecting a first feature from a first polyhedron and a second feature from a second polyhedron; Voronoi region determining means for determining a first Voronoi region corresponding to said first feature and a second Voronoi region corresponding to said second feature; first means for comparing said first feature to said second Voronoi region to determine whether a first closest point of said first feature is within said second Voronoi region; second means for comparing said second feature to said first Voronoi region to determine whether a second closest point of said second features is within said first Voronoi region; selection means for selecting said first and second features as said closest features when said first feature is in said second Voronoi region and said second feature is in said first Voronoi region; selecting means for selecting a new first feature and a new second feature based upon a position of said first feature relative to said second Voronoi region and a position of said second feature relative to said first Voronoi region when said first feature is outside said second Voronoi regions or said second feature is outside said first Voronoi region; and wherein the first and second means for comparing further comprise: means for clipping an edge type feature with a Voronoi region of another feature to determine an entry point where said edge enters said Voronoi region and an exit point where said edge exits said Voronoi region; means for determining a sign of a derivative of a function representing a distance between said edge type feature and said other feature at said entry point as an entry sign and at said exit point as an exit sign; means for determining an entry feature defining a plane of said Voronoi region corresponding to said entry point, and an exit feature defining a plane of said Voronoi region corresponding to said exit point; and wherein said means for selecting includes edge means for selecting said new first feature and said new second feature based upon said entry sign, exit sign, entry feature and exit feature when said first feature or said second feature is an edge type feature.