Midpoint of the shortest distance between 2 rays in 3D

Question

I would like to come with an algorithm to find the midpoint of the shortest between 2 rays a+tb and c+sd, where t and s are scalars. I have a scenario which I try to depict like this.

One of the strategies I was planning to try was finding out the equation of the plane a(sb)c, and project the point td on to abc, and then solve for intersection to get q. Then do the same for p, and then add and divide them by 2 to get r. But, without knowing t and s, I'm wondering whether this is the right way to go. Any help on this problem would be appreciated.

Answer 1

Find solution for $s$ and $t$ by

$$ \begin{aligned} s & = \frac{(b\cdot d) \left( (a \cdot d)-(b \cdot c) \right)-(a \cdot d)(c \cdot d)}{(b \cdot d)^2-1} \\ t & = \frac{(b\cdot d) \left( (c \cdot d)-(a \cdot d) \right)-(b \cdot c)(a \cdot b)}{(b \cdot d)^2-1} \\ \end{aligned} $$

where ${\cdot}$ is the dot product.

The mid point is then $r=\frac{1}{2} ( a+c+b t+d s)$

HOW ?

Point $p$ is closest point on line $c+sd$ to point $q$, and point $q$ is closest on line $a+b t$ to $p$.

The above leads to $$a+b t = c+ d s + \frac{(a \times b)\times b}{b \cdot b} $$ and $$c+ d s = a+b t + \frac{(c \times d)\times d}{d \cdot d} $$

I can dispose the cross products by projecting along $b$ and $d$

$$ b \cdot (a+b t) = b \cdot (c+d s) + 0 $$ $$ d \cdot (c+d s) = d \cdot (a+b t) + 0 $$

This is two scalar equations solvable for $t$ and $s$.

Answer 2

Hint: use the cross product $\vec b \times \vec d$. It will be perpendicular to both lines.

EDIT: other more efficient hint... You have your midpoint $R$.

Distance between $R$ and first line is $d_1=\dfrac{\mid \mid\vec{RA}\times \vec b\mid \mid}{\mid\mid\vec b \mid\mid}$

Do the same with the other line and say that they are equal...

Answer 3

One way to approach this is:

Let $r_{1o}$ and $r_{1d}$ define the origin and direction of the first ray.

Let $r_{2o}$ and $r_{2d}$ define the origin and direction of the second ray.

Minimise $d = ((r_{1o} + {r_{1d}}t) - p)^2$ where $p$ is a point on $r_2$.

$$d = ((r_{1o} + {r_{1d}}t) - p)^2$$ $$=(r_{1d}t + (r_{1o} - p))^2$$ $$=r_{1d}.r_{1d}t^2 + 2(r_{1o} - p).r_{1d}t + (r_{1o} - p)^2$$

$$dd/dt = 2r_{1d}.r_{1d}t + 2(r_{1o} - p).r_{1d}$$

Then Let $dd/dt = 0$

$$0 = 2r_{1d}.r_{1d}t + 2(r_{1o} - p).r_{1d}$$ $$0 = r_{1d}.r_{1d}t + (r_{1o} - p).r_{1d}$$

and then substitute $p$ with $r_{2o} + r_{2d}s$

Giving:

$$0 = r_{1d}.r_{1d}t + (r_{1o} - r_{2o} - r_{2d}s).r_{1d}$$ $$0 = r_{1d}.r_{1d}t - r_{2d}.r_{1d}s + (r_{1o} - r_{2o}).r_{1d}$$ $$r_{1d}.r_{1d}t - r_{2d}.r_{1d}s = -(r_{1o} - r_{2o}).r_{1d}$$

Now exchange $r_{1*}$ with $r_{2*}$, and $s$ with $t$ to simulate going through the same process with the other ray yielding:

$$r_{2d}.r_{2d}s - r_{1d}.r_{2d}t = -(r_{2o} - r_{1o}).r_{2d}$$ $$-r_{1d}.r_{2d}t + r_{2d}.r_{2d}s = -(r_{2o} - r_{1o}).r_{2d}$$

And now you have two simultaneous equations to solve:

$$r_{1d}.r_{1d}t - r_{2d}.r_{1d}s = -(r_{1o} - r_{2o}).r_{1d}$$ $$-r_{1d}.r_{2d}t + r_{2d}.r_{2d}s = -(r_{2o} - r_{1o}).r_{2d}$$

Giving:

$$t = \frac{-((r_{1o} - r_{2o}).r_{1d})(r_{2d}.r_{2d}) - (r_{2d}.r_{1d})((r_{2o} - r_{1o}).r_{2d})}{(r_{1d}.r_{1d})(r_{2d}.r_{2d}) - (r_{2d}.r_{1d})(r_{1d}.r_{2d})}$$ $$s = \frac{-(r_{1d}.r_{1d})((r_{2o} - r_{1o}).r_{2d}) - ((r_{1o} - r_{2o}).r_{1d})(r_{1d}.r_{2d})}{(r_{1d}.r_{1d})(r_{2d}.r_{2d}) - (r_{2d}.r_{1d})(r_{1d}.r_{2d})}$$

Above solved with Cramer's rule because I was getting lazy.

This can be rearranged to make the common sub-expressions more visible (for implementation with temporary variables)

$$t = \frac{((r_{2o} - r_{1o}).r_{1d})(r_{2d}.r_{2d}) + ((r_{1o} - r_{2o}).r_{2d})(r_{1d}.r_{2d})}{(r_{1d}.r_{1d})(r_{2d}.r_{2d}) - (r_{1d}.r_{2d})^2}$$ $$s = \frac{((r_{1o} - r_{2o}).r_{2d})(r_{1d}.r_{1d}) + ((r_{2o} - r_{1o}).r_{1d})(r_{1d}.r_{2d})}{(r_{1d}.r_{1d})(r_{2d}.r_{2d}) - (r_{1d}.r_{2d})^2}$$

Then taking the average for the mid point: $$m = \frac{(r_{1o} + r_{1d}t) + (r_{2o} + r_{2d}s)}{2}$$

This formula should work for non-normalized direction vectors.