Hi Currently I''m puzzling over edge-to-edge collision detection (eg: whether the edges of two boxes are colliding). I''ve found some usuable theory (Moore and Wilhelms, 1988), but I''d like to hear from you guys (girls) if there is some amazing technique that I should know about. I''m not interested in broad-phase collision, I want to know if the boxes collide, which edges are responsible, and where along thoses edges the collision is taking place. (I''m not worried about whether vertices are colliding with the box-planes... that is reasonably trivial.) thanks Henri

V-clip, which is at the core of our collision detection code, does this. E.g. it takes a pair of convex polyhedra and reports the pair of features (one on each) which are nearest, or whether they overlap if they do. It''s used as part of the narrow phase of collision detection, e.g. after you have dtermined which pairs of objects are close enough to collide you call v-clip to keep track of whether the objects are seperate, and if so which features (faces, edges or vertices) are closest.

Once you detect collision you rewind/rollback the polyhedra to their previous positions and see what features were closest before the collision. If they are moving quickly you may need to interpolate their positions to get their positions just before they hit. Then use v-clip to work out which features are nearest just before collision.

These can be an vertex-face or edge-edge pair. In each case you only need the point of collision and a normal to the collision. For a vertex-face this is just the vertex position and the plane normal. For an edge-edge you use the point of intersection of the edges (if your maths up to this point is right they should intersect, or come very close at a scale about equal to the accuracy of your interpolation) and the cross product of the line directions for the point and normal. Then proceed as you would for the vertex-face.

That''s pretty perfect... - but I need an algorithm that can tell me how close two edges (line-segments) are, and at which points on the edges they are closest to each other.

I spoke with our math department, and a helpful professor mentioned that the problem is pretty well known, but he didn''t know the solution off-hand, and that he''ll get back to me. Sounds promising.

Still... any takers?
thanx
Henri

> ... - but I need an algorithm that can tell me how close two
> edges (line-segments) are, and at which points on the edges
> they are closest to each other.

Suppose each line is given in the form

a + sb

where a and b are both vectors. ''a'' can be called the position or start vector of the line, while ''b'' is the direction vector, i.e. a vector parallel to the line. Assume this is a unit vector as this makes the maths clearer. ''s'' is a scalar parameter that varies as a point moves along the line.

If the two lines are then

l1: a + sb

l2: c + td

[a, c the start vectors, b, d the unit direction vectors and s,t both scalars]

Let

e = b ^ d [using the cross product].

If this is a zero vector the lines are parallel and you cannot determine the closest point. Otherwise normalise it to get f, and the distance between the lines is just

a.f - c.f = (a-c).f [using the dot/inner product]

Finding the closest points is a bit more complex, but the final formulae are straightforward. First work out

i = b.d [again the dot product]

This should be less than 1 and greater than -1 as the lines are not parallel and b and d are unit vectors. Then the point on line 1 is given by

s = (c-a).(b-id)/(1-i^2)

While the point on line 2 is given by

t = (c-a).(ib-d)/(1-i^2)

using a dot product in each, with a, b, c, d the lines'' vectors and i the inner product just calculated.

If you want to know why this works it depends on i being the cos of the angle between the lines. (1-i^2) is then the square of the sin of the angle, and the formulae can be drived from basic algebra, trig and geometry.

Stunning! Thanks johnb.

Tomorrow I''ll still speak with a professor in the maths department - he told me that he has a solution for me. Presumably the same (or very similar).

Then compile, process and analyze results, and get the physics a rollin''

thanks again
Henri

Oh johnb

a second side note - I've been going through the details a bit and need to verify some thoughts: when calculating the s and t values, then it would be convenient to define the line as:

a + sb

Where a is the one point (p1) and b is the vector from the one point (p1) to the other point (p2) of the line-segment that goes from p1 to p2.

In that case (if b is not necessarily unit length) then the s value calculated could be used to determine whether the point of closeness is on the linesegment as values for s from 0 to 1 are "on" the line-segment.

That sound more or less sensible?

[edited by - LoreKeeper on March 25, 2002 3:16:46 PM]

You can define the line like that, using a non-unit direction vector. But you then have to include the lengths of both directions in the calculation, making the formulae far more complex. It''s probably easier to normalise the vectors before using them in the formulae, then using the pre-normalisation lengths to rescale the parameters after calculating them.