Last Updated February 11, 2009

Lin-Canny Closest Features Method

The brute-force approach discussed above is very expensive and takes no advantage of temporal or spatial coherence.

An attractive method developed by Lin & Canny can compute collisions between polyhedra. The great thing about this method is that object complexity does not impact significantly on the speed of the algorithm.

Features & Voronoi regions

Features of a polyhedron are vertices, edges and faces. Points in the space around a polyhedron can be classified according to which feature is closest. These groups of points are called voronoi regions. Voronoi regions can be calculated at build-time.

To determine which feature is closest to a given point, just figure out which voronoi region the point is in.

The Lin-Canny approach uses voronoi regions to determine which two features of two polyhedra are closest.

The goal of this algorithim is to find the closest points between two objects. A pair of points are closest if they are both in voronoi region of the other feature.

Given a pair of features there are 6 cases to consider;

1. vertex to vertex
2. vertex to edge
3. vertex to face
4. edge to edge
5. edge to face
6. face to face

Cases 5 & 6 will only occur when a edge or face is exactly parallel to a face, as this occurs extremely rarely we will not consider them.

The technique starts with an arbitrary pair of features (one on each polyhedron) and then find the closest points (point_a & point_b) between these features.

We must check if point_a is the closest point in polyhedron A to polyhedron B. (is point_a in the voronoi region of point_b's feature?)

We must check if point_b is the closest point in polyhedron B to polyhedron A.(is point_b in the voronoi region of point_a's feature?)

If either check fails, then find a new feature which is closer and recheck.

Eventually the closest points will be found.

Closest point

The algorithm requires that the closest points between each pair of features be found;

For vertex to vertex, the closest points are the vertices themselves (trivial case)

For vertex to edge, the closest point is determined by finding the perpendicular distance to the edge's supporting line from the vertex. If this point lies outside the edge, end point closest to the point is used.

For vertex to face, the perpendicular distance to the supporting plane is found, if this point lies outside the face, then the face vertex closest is used.

Point-Vertex test

If a vertex is the closest feature to a point, then the point must lie in the voronoi region of the vertex.

If the point lies inside the Voronoi region of the feature, the the feature is the nearest feature to that point, otherwise son eother feature is nearer.

The voronoi region of a vertex is the space enclosed by planes through the vertex at right angles to each of the vertex's edges. If a point lies 'outside' one of these planes then the edge associated with that plane is a closer feature to the point and the procedure selects the edge as a candidate closest feature.

Point-Edge Test

If an edge is the closest feature on a polyhedron to a point, then the point must lie in the voronoi region of the edge.

The voronoi region of edge is the space enclosed by two planes through the edge at right angles to each of the edges faces. Planes at right angles to the edge through the endpoints complete the voronoi region. If a point lies 'outside' one of these planes then the face or vertex associated with that plane is a closer feature to the point and the procedure selects the face or vertex as a candidate closest feature.

Point-Face Test

If a face is the closest feature on a polyhedron to a point, then the point must lie in the voronoi region of the face.

The voronoi region of face is the space enclosed by the planes through the edges at right angles to the faces. If a point lies 'outside' one of these planes then edge with that plane is a closer feature to the point and the procedure selects the edge as a candidate closest feature.

Procedure

1. If the features are a pair of vertices, then they both have to satisfy the applicability conditions imposed by each other, in order for them to be the closest features. If either one of the vertices fails the applicability test imposed by the other, the algorithm will return a new pair of features ­ one of the two vertices and the edge for which the test failed, then continue checking the new features until it finds the closest pair.
2. Given a vertex and an edge, the algorithm will check whether the vertex satisfies the applicability conditions imposed by the edge and whether the nearest point on the edge to the vertex satisfies the applicability conditions imposed by the vertex. If both verifications return value "true", then they are the closest features. Otherwise, a corresponding new pair of features (depending on which test failed) will be returned and the algorithm will proceed until it finds the pair of closest features.
3. For the case of a vertex and a face, both of the applicability tests imposed by the face to the vertex and from vertex to the nearest point on the face must be satisfied for this pair to qualify as the "closest­ feature pair". Otherwise, a new pair of features will be returned and the algorithm will be called again until the closest­feature pair is found.
4. Similarly, given a pair of edges as inputs, if their nearest points satisfy the applicability conditions imposed by the each other, then they are the closest features between two polyhedra. If not, one of the edges will be changed to a neighboring vertex or a face and the check will be done again on the new pair of features.
5. When a given pair of features is an edge and a face, we first need to decide whether the edge is parallel to the face. If it isn't, then the actual closest features will be either one of the vertices of the edge and the face, or the edge and some other edge bounding the face. The former case occurs when this vertex satisfies the vertex­face applicability condition, and when the edge is pointing "into" the face in the direction of this vertex. Otherwise the latter case applies. The edge (bounding the face) to be chosen is the edge which is closest to the original edge.

© Ken Power 1996-2016