Sweeping collision detection between two line segments moving in 3d I have two moving line segments in 3d; A and B with known endpoints at time t=0 and t=1. A0(t0), A1(t0), B0(t0), B1(t0), A0(t1), A1(t1), B0(t1), B1(t1)
I need to know if they collided while moving from t=0 to t=1
It is not required to know at what t or where along the line segments the collision happened, only if they did or did not collide.
My initial approach was to define two triangles as the space swept by each segment. Vertices A0(t0)-A1(t0)-A0(t1) and A1(t0)-A0(t1)-A1(t1) and similar for segment B. Then I wanted to check if the triangles intersected, which would indicate a collision. The problem is that one segment may move through the same space as the other - just at a different time. This method was obviously not good enough. Considered defining 4D surfaces instead of 3D, to take time into account, but couldn't quite wrap my head around that.
The second approach would be to define line equations for the segments as 
A(u)=A0+(A1-A0)*u for u=[0..1] and check for a common solution. This would also require a 4D line equation, though in the form of A(u,t) where I should solve for a common solution in t... but again, I am not exactly sure if this even is doable or how exactly to manage it.
The third approach is to simply transform the problem from two moving segments into one stationary and one moving. Specifically transforming A(t0) to be aligned with the x axis and having a length of 1 and doing the same transform on B(t0) and then doing the same for A(t1) and again B(t1). A is then stationary and B moves relative. Setting up the transformation matrix is trivial... for the x-axis which is along A(t1)-A(t0), but that leaves y and z, which are rather undefined for the segments, since they have no concept of rotation along their axis.
This leaves me... here... asking for insight. I am entirely unable to find anything usable for sweeping 3D moving line segments, so any hints would be very appreciated.
 A: I'm assuming that the endpoints of the line segments travel at constant velocity, since arbitrary motion will allow the line segments to pass around each other regardless of their initial and final positions. I'm also assuming that the line segments spend almost all of their time in arbitrary orientations.
The first observation is that, if the line segments collide, then the four endpoints will lie in the same plane. So, pick three points ($A_0$, $A_1$, and $B_0$, say) and define the normal vector of this moving plane by
$$\vec{n}(t) = \left(\vec{A_1}(t) - \vec{A_0}(t)\right) \times \left(\vec{B_0}(t) - \vec{A_0}(t)\right).$$
Now, the lines lie in the same plane if the fourth point ($B_1,$ in this example), lies in that plane. This is true when
$$\left(\vec{B_1}(t) - \vec{A_0}(t)\right)\cdot\vec{n}(t) = 0.$$
Since you are doing numerical simulations, you'll want to check if the above dot product changes sign at some time between $t_0$ and $t_1$ instead of looking for exactly zero. If there is no change in sign, then the line segments could not have intersected. If the steps of your simulation are small enough, then you can just check the sign at $t_0$ and $t_1$.
If there is a sign change, then you need to find the point where $B_1$ crosses the plane. Use Newton-Raphson or other means to find the collision $t_c \in [t_0, t_1]$ by solving the dot production equation. Assuming the endpoint motions are linear, the dot product equation will be some complex cubic equation. If the step from $t_0$ to $t_1$ is small, a single iteration of N-R may suffice.
Better test for intersection (old answer left below)
Once it has been established that the line segment endpoints lie in a plane, all that left is to show that the polygon formed by $A_0B_0A_1B_1$ (in that order, or any other order that alternates $A$ and $B$ endpoints) is convex. The line segments $A$ and $B$ form the diagonals of a quadrilateral, and these diagonals cross if and only if the quadrilateral is convex. See the diagram in the old answer (ignore the blue-shaded area). To show this, compute the cross product of each edge of the polygon and check if they all point in the same direction.
$$\vec{n_{A_0}} = \left(\vec{B_1} - \vec{A_0}\right) \times \left(\vec{B_0} - \vec{A_0}\right)$$
Do this for each vertex of the quardilateral and make sure that $\vec{n_x}\cdot\vec{n_y} > 0$ for all pairs of cross product vectors. Make sure to do the cross products in a consistent order.
This is better than the old method since it's simpler and you don't have to calculate unit vectors (avoiding division and square roots). The only operations are addition, multiplication, and sign checks.
Old answer
The diagram below shows the general position of the points at the potential collision. The blue shaded area is where the point $B_1$ has to be in order for the lines to have crossed.

This requirement has three conditions:
First,
$$\angle B_1B_0A_0 < \angle A_1B_0A_0$$
which implies that
$$\cos(\angle B_1B_0A_0) > \cos(\angle A_1B_0A_0)$$
thus
$$unit\left(\vec{B_1}-\vec{B_0}\right)\cdot unit\left(\vec{B_1}-\vec{A_0}\right) > unit\left(\vec{A_1}-\vec{B_0}\right)\cdot unit\left(\vec{A_1}-\vec{A_0}\right)$$
where $unit(\vec{x})$ means the unit vector of $\vec{x}.$ All of the above points are at $t=t_c$ calculated from the previous step.
Second,
$$\angle B_1B_0A_1 < \angle A_0B_0A_1$$
This works out to dot products similarly to the first condition.
The two conditions establish that the point $B_1$ lies along the dashed line that will intersect the line segment $A_0A_1$ in the diagram. The third condition is that $B_0$ and $B_1$ lie on opposite sides of the line segment $A_0A_1$. This is true when
$$\left(\vec{A_0}-\vec{B_0}\right)\times\left(\vec{A_1}-\vec{B_0}\right)$$
and
$$\left(\vec{A_1}-\vec{B_1}\right)\times\left(\vec{A_0}-\vec{B_1}\right)$$
point in the same direction (check this with the right-hand rule). So, the final check is that
$$\left(\left(\vec{A_0}-\vec{B_0}\right)\times\left(\vec{A_1}-\vec{B_0}\right)\right)\cdot\left(\left(\vec{A_1}-\vec{B_1}\right)\times\left(\vec{A_0}-\vec{B_1}\right)\right) > 0$$

On second thought, the above is a long-winded way of saying:


*

*Create a 2D barycentric coordinate system with $A_0$, $A_1$, and $B_0$ as the vertices with $B_0$ as the base vertex. All points are at the collision time $t=t_c.$

*Calculate the barycentric coordinate of $B_1$.

*The line segments intersect when the coordinate of $B_1$ is of the form $(< 0, (0, 1), (0, 1))$, that is, the first coordinate is negative while the other two are positive and less than one.

