Home Products Download Order Contacts

comp.graphics.algorithms

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




wrote in message
news:1148060396.888561.232280@38g2000cwa.googlegroups.com...
>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
http://www.geometrictools.com



Reply


View All Messages in comp.graphics.algorithms

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

Replies:

Copyright 2006 WatermarkFactory.com. All Rights Reserved.