Re: [rp-ml] STL Round off errors

From: steve <sjbaker1_at_airmail.net>
Date: Mon Jun 12 2006 - 15:12:21 EEST

Liam MacGinley wrote:
> Hi there
> I have an STL question thats related to round off errors that occur in
> typical STL files.
>
> I have come across a number of papers which state that if two or more
> vertices are within some tolerance error value of each other then they
> can be grouped together effectively removing the round off error.

If roundoff error is causing two polygons which should join together
to somehow pull apart and not make up a continuous surface anymore
thereby causing 'leaks' that the surface skin to volumetric conversion
stage can't plug - then you need to zip them back together again.

However, this can be done selectively. Only when a polygon has
one or more edges that are not shared with another polygon do you
need to look for another one that's nearby to zip together with.

Other than that, roundoff error should be utterly negligable for
and RP machine. A single precision floating point number should
remain accurate to at least one part in a million - it's inherently
accurate to one part in four million - so it would take a lot of
consecutive math operations to introduce enough roundoffs (and all
in the same direction) to make the surface be wrong by more than
one part per million.

I very much doubt that any RP machine out there is accurate to
one part per million. So aside from 'plugging leaks' - there
should never be any need to attempt to fix roundoff problems.

One common design error that causes gaps (which can't always
be plugged by snapping things together) is when you model a
'T-edge' like this:

           /\
          / \
         / \
        / \
       / A \
      /__________\
      \ /\ /
       \ / \ /
        \/____\/
         \ /
          \ /
           \/

The vertex at 'A' is shared by the three triangles below it but
not by the top one. So the edge that's shared between bottom
and top triangles can come apart and form a teeny-tiny crack
if 'A' moves by even an infinitely small amount. Since this
kind of roundoff problem is both inevitable - and utterly
impossible to fix - the rule is quite simply "Don't Do That".

MOREOVER: If two vertices started off at the exact same
position then well-designed software should perform precisely the
same math on both of them - so the roundoff error will be the
same for both copies and there is no way for them to come
apart. So you have to ask yourself where this problem you're
having is coming from in the first place.

> My question is how do they come up with a value for this tolerance
> error?

Well, there shouldn't have to BE an error tolerance in the first
place. If you have thin gaps and cracks in the skin of the model
that cause it to fail to convert into a volumetric object then
you either designed it poorly - or you have some REALLY poor
software somewhere in your tool chain. Either way, the thing
that zips up those rogue edges should be doing it selectively.
Rather than snapping together any vertices that are within some
arbitary tolerance, it should be detecting those small gaps and
only snapping together vertices that are along the edges of those
gaps.

Since gaps shouldn't happen in the first place, the tolerance you
set should only be to determine whether the software silently
snaps vertices together to fill gaps - or whether it reports that
the gap is so big that there is a design error or something.

This is not a new problem - computer graphics people (like me!)
have been thinking about and dealing with this since the 1970's.
Received on Mon Jun 12 14:28:11 2006

This archive was generated by hypermail 2.1.8 : Tue Jul 21 2009 - 10:27:52 EEST