# *Signed* distance between two moving lines

This topic is 1792 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Given two lines in R3. Each line is defined by two vertices on a moving frame (linear *and* angular motion). Assume we have world space vertices A,B and C,D defining the current lines. At t0 = 0 I compute the distance d( 0 ) = dot ( AC, cross( AB, CD) / | cross( AB, CD) | ) such that d( 0 ) > 0. I can use this function to measure the distance over time. The only problem is that the orientation of cross( AB, CD ) can flip. E.g. if edge CD would rotate around the initial cross product axis( 0 ) = cross( AB( 0 ), CD( 0 ) ). The distance would be constant, be switches signs when CD crosses over AB. I guess I would need to add some concept of handiness to get the proper sign. Is this possible or are there other possibilities to define the distance?

Thanks,

-Dirk

Edited by Dirk Gregorius

##### Share on other sites

What is the signed distance between 2 lines? Lines are in a sense infinitely skinny. They are either touching, d = 0, or not touching d > 0.

Edited by rayp

##### Share on other sites

I agree! Well, I think I need a sign relative to the initial configuration. If the lines are not touching the closest points define a plane. I want to drive this plane based on the cross product without have the cross product flip the plane. Does this make more sense?

Edited by Dirk Gregorius

##### Share on other sites

If your lines only move by translation, you might be able to define something like this (just project to a plane that is perpendicular to one of the lines and describe the other line as A*x+B*y+C*z+D=0, with A^2+B^2+C^2=1, and D is your distance). If your lines can move more freely, you can reach the same configuration with and without intersection, which makes it hard to have a meaningful sign assigned to the distance.

##### Share on other sites

I am implementing the Box2D TOI which is conceptually a root finding algorithm. You essentially find the closest features and based on this you try to find the root for d(t) = ( SupportB( -n ) - SupportA( n ) ) * n. Here n is a function of time and depends on the initial features. For the edge case I tried a fixed axis like Box2D does for vertex/vertex and I also attached a plane to one of the bodies. Both work i, but are highly inefficient. You can easily run 80 - 100 iterations which makes the algorithm unusable in practice. If you use n = e1(t) x e2(t) everything works great, but it can fail if the cross product flips. You can clearly see this if you plot the function that the root finder sees. The function has a step.

##### Share on other sites

If the edges can move freely, you could get a distance value of zero if the edges happened to become parallel, despite a possibly large |AC|.

I don't think your distance function properly captures the concept of distance. (This is probably already clear in the discontinuity that you observe.)

See: http://en.wikipedia.org/wiki/Metric_(mathematics)

I think there are too many things going on at once with your formula. First, you have the magnitude of the separation |AC|. Second, you have the relative orientation of this separation with respect to the normal (ABxCD)^. Third, you have a time evolution behavior that dynamically changes the "semantics" of the formula (at least for me, as I try to interpret this as something distance-like). It might be a little too untamed for what you are trying to use it for.

I understand now a little more clearly what you were trying to do in your other post. I think you wanted to try to piece-wise apply this function correctly. If you are seeing positive benefits from using this function and wanted to pursue making it work, I would give that a second look. On a cursory look, you have maybe three things to consider. (a) The cross-product vanishes. (b+c) The two different signs of the cross-product.

##### Share on other sites

Hi Deekr,

I give you some more context. In my initial post I used d(t) = AC * ( AB  x CD ). This would be only partially correct since this doesn't take the other features into account. Essentially I solve d(t) = ( SupportB( -n ) - SupportA( n ) ) * n. Here n is some direction based on the closest features I start with at t = 0. E.g. for vertex / vertex Box2D uses a fixed axis computed from the closest points. For face/vertex n is the face normal moving with the rigid body. If you want to extent this to 3D we have to deal with edge/edge. Of course you can use a global axis as for vertex ( e.g. n = e1( 0 ) x e2( 0 ) ). Or I can use a fixed axis attached to body A or B. There is nothing wrong with this and this works perfect;y, but the performance sucks so bad that the algorithm becomes unusable in practice with these definitions for the separation function because the iteration count goes up to 50 - 100. If you investigate this you also notice that restart the algorithm but the features haven't changed. This strongly indicates that these are poor choices for a separation function.

Using n = e1( t ) x e2( t ) works great on the other hand. The algorithm uses 1-5 iterations and is lighting fast. The problem is to define a consistent normal. This only fails if the cross products flips and I need to come up with a condition to detect this. So far I a have failed miserable on this. One idea I had was to use the initial axis n( 0 ) = e1( 0 ) x e2( 0 ) as a reference direction and then detect when dot( n( 0 ), n( t ) ) < 0 and flip the axis. This is wrong since the normals can get into valid configuration violating this condition.  Intuively I guess I need some notion of handness which I should define from the initial configuration at t = 0. If I could create e.g. a consistent RH coordinate frame at each instance in time I might be able to detect the switch the normal properly. Just the normal seems not enough.

So yes I am seeing positive benefits from this. If we can solve this we have a really nice CCD which solves a lot of problems people might notice with conservative advancement. It is a really fast algorithm.

I am not so much concerned with case (a). I this case we could always create a normal from the closest points. Given we can make sure we have the correct direction to get the proper sign. I think the two different signs of the cross product are the problem and we need more information (possibly from the initial configuration) and track this through time.

Thanks! I appreciate your help!

-Dirk

##### Share on other sites

This topic is 1792 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account