Re: Distance point <=> straight line in space

Daniel Kraft <d@xxxxxxxx> writes:

Hi,

in a program, I've got a straight line in space defined by two points
(p1 and p2) on it, and a set (~ 10000) points q_i in space. Then I
need to calculate for each of those points the distance to the
straight. At the moment I'm doing it like this:

vector g = normalized (p2 - p1) // Find normalized direction
for i = 1 to n
distance_i = norm (cross_product (p2 - q_i, g))

I believe this formula is fairly straight-forward (a single
cross-product and a norm); unfortunatelly, my program spents a large
amount of time (~ 95% of total runtime) in this routine and the
current duration is unacceptable.

p2 - q_i = 3 scalar -
cross_product = 6 scalar *, 3 scalar -
norm = 3 scalar *, 2 scalar +, 1 scalar square root

total: ( 9 scalar *, 8 scalar +/-, 1 scalar square root ) per point.


Is there a better approach I could take to do this calculation that
requires less operations? The output of gcc -O3 seems already
reasonably optimized, i.e., the cross-product and norm calculation is
fully inlined. I don't think hand-optimized inline-assembly could
help here much, right?

Assume we were in 2D, then the distance to the origin would be
sqrt(x*x+y*y) for each point (x,y). That would be only 2 scalar *,
one scalar + and one scalar square root.

Now, doing the transformation of a 3D point to a coordinate system
where the line (p1,p2) is the z axis would involve multiplicating a
3x3 matrix with the vector coordinates of the point. But since we
want to compute only the distance, we don't need to compute the z
coordinate of the point in the new coordinate system. So we need to
multiply only with a 2x3 matrix: 6 scalar *, 4 scalar +.
Total: ( 8 scalar *, 5 scalar +, 1 scalar square root) per point.


If you want it even faster, you will have to parallelize the
processing (which is easily done since there's no dependencies between
iterations). You could try to make use of vectorial processors (MMX,
SSE, etc), or just spread the work across several cores with threads.




--
__Pascal Bourguignon__ http://www.informatimago.com/

NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
.

Relevant Pages