Home Products Download Order Contacts


Subject: Re: Distance between two line segments in 3D

wrote in message
>A logically/algorithmically correct algorithm is here:
> http://www.fho-emden.de/~hoffmann/xsegdist03072004.pdf
> The algorithm fails numerically for extraordinarily large
> ranges for the segment end points, e.g. for line segments
> with lengths in the region of 10^8.
> This is so because the SQUARED distance is minimized.
> If the geometry is somewhat normalized - all end points
> are in a cube with edge length 10^4...10^6 - then the algorithm
> is OK for all practical purposes (double precision assumed)

One other thing to mention, when computations are done in
32-bit float, is that on a PC or equivalent desktop computer,
quite a few of the intermediate 32-bit floating-point operations
are actually done in 64-bit or 80-bit internal registers in the FPU.
This tends to make such algorithms a bit more robust.

If you do not have such hardware support, the round-off
errors can bite you very quickly. One of the bug reports I
had gotten (some years ago) was from someone running your
version of the algorithm on an SGI machine, using 32-bit float,
but the intermediate expressions were also computed in 32-bit
float. In its earlier days and by design, Java specs required all
intermediate calculations for 32-bit float be done with 32-bit
float (the illusion of portability).

When reporting the success (or failure) of an algorithm you have
implemented, it is also important to note what hardware you are
running on.

Dave Eberly


View All Messages in comp.graphics.algorithms

Distance between two line segments in 3D =>Re: Distance between two line segments in 3D =>


Copyright 2006 WatermarkFactory.com. All Rights Reserved.