I'm working on a 3D algorithm that at some point establishes orientation of two lines - the same way one would do using the triple product. The way those lines are described, however, makes the computation much more complicated: the first line (let's call it line $M$) is given as a pair of points (let's say $M_a$ and $M_b$) that $M$ goes through. The second line (let's say $L$) is a line that intersects four line segments given in the form of four pairs of points. In other words, there is a line segment that goes from a point $L_{1a}$ to point $L_{1b}$, another segment that goes from point $L_{2a}$ to point $L_{2b}$, another from $L_{3a}$ to $L_{3b}$ and the last one from $L_{4a}$ to $L_{4b}$. All the points are provided (a priori). The line that intersects those four segments is our line $L$. It is guaranteed that there exists exactly one line $L$ that goes through all four segments (e.g. never three of them are coplanar), so there's no need to check if a particular set of given points has a solution.

The question is: do lines $M$ and $L$ intersect, or are they clockwise-skewed, or counter-clockwise-skewed?

My solution goes as follows: the first three of $L$ line segments form a hyperboloid of one sheet or hyperbolic paraboloid (or see *). The fourth one intersects this surface in some point C. If we intersect the first line segment $\overline{L_{1a}L_{1b}}$ with a plane that goes through points $L_{2a}$, $L_{2b}$, $C$ or $L_{3a}$, $L_{3b}$, $C$, we get another point $D$. The final solution is a triple product of $([D - C][M_b - M_a][M_a - C])$ - equals zero if $L$ and $M$ intersect, greater than zero if they are cw-skewed, and negative if ccw-skewed.

This solution is impractical from the computational point of view. It's hard to be parallelized and performs extremely large amount of dot products, cross products, additions, negations, plus one inversion and a square root. The last of mentioned operations is not even available on the architecture I'm targeting with the algorithm.

Maybe I'm wrong, but I have a feeling that there exists a solution that does not need to perform all these intermediate calculations, intersection points and square root at all. For example, just like the triple product is a determinant of some matrix built on top of points defining two lines, maybe there's a matrix that can be built from those 10 points and again determinant could be used to establish the final orientation?

Every hint kindly appreciated.

$*$ - if any two of $L$ segments intersect, then this surface degrades to a plane, and if there are two intersections, then it degrades even more - directly to two points: C and D.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.