**comp.graphics.algorithms**

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

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.