Re: STL best practices & tools
I believe that 2d operations in OpenSCAD round everything to
2^-11---possibly this has something to do with clipperlib? And polyhedron
rounds to 2^-20.
On Sun, Jun 11, 2023 at 7:24 PM neri-engineering via Discuss <
discuss@lists.openscad.org> wrote:
---------- Forwarded message ----------
From: neri-engineering neri-engineering@protonmail.com
To: OpenSCAD general discussion Mailing-list discuss@lists.openscad.org
Cc:
Bcc:
Date: Sun, 11 Jun 2023 23:23:30 +0000
Subject: [OpenSCAD] Re: STL best practices & tools
Thanks for responding Torsten.
You don't need perfect math to do very adequate computing. If you're not
using perfect math then chances are very likely that you will stumble upon
anomalies in about one out of 2 billion or so cases. That's rare enough to
say that it's good enough.
I'm not going to formulate this email as well as I usually do when I write
- but I stumbled upon the area of imprecise math when doing line drawing
algorithms.
A line segment is:
(x0,y0) + t*(x1-x0,y1-y0) = (x,y) as t goes from 0 to 1.
Usually the best strategy when using approximate math is to have
x0,y0,x1,y1, and t be 64 bit floating points (high precision) and then
casting the combination of those, AFTER putting them through the formula
above, to 32 bit when choosing a pixel to turn on and off. It seems to me
that OpenSCAD and/or CGAL are doing something which would be equivalent to
casting these five values to 32 bit BEFORE passing them through this line
formula.
The problem [however] arises at those 64 bit floating point numbers that
are approximately exactly half way between two 32 bit "adjacent" floating
point numbers.
If our endpoints are of this nature, being 64 bit floats halfway between
two adjacent 32 bit floats, then by nudging the endpoint just a little bit
could make it go either way - it could "snap" to the lower value or it
could "snap" to the higher value. In certain cases this unpredictable
"snapping nature" would cause different pixels to get turned on and off
depending on the exact endpoints. In particular, if we lengthen the
segment [mathematically, using 64 bits for example] while remaining on the
same line [as close as is allowed within the scope of 64 bit math], then
the endpoints may be perturbed enough to cause this snapping effect, in
some particular situations.
There are how many 64 bit floating point number between each pair of
adjacent 32 bit floating point numbers? How about in the range [0.0,1.0] -
between each adjacent pair of 32 bit floats in that interval, how many 64
bit floats lie in between? I'm sure that there are over a billion.
Therefore the chance of seeing such a strange behavior is very rare. It's
rare enough to call it "perfect".
With careful planning and with careful programming, 64 bit and 32 bit
floats can be used to accomplish exactly what you are looking for. This is
not an easy science however. It takes a great deal of meticulous care to
write the correct code. My line drawing algorithms for example took a lot
out of me when I did them 22 years ago.
In my line drawing algorithms for example I never once happened to
encounter a situation where a segment is drawn (with 64 bit endpoint
coordinates), and then another segment is drawn from the first endpoint to
some midpoint of the original segment; not necessarily the exact midpoint
but somewhere between 1/3 of the way and 2/3 of the way, let's just say. I
never once saw that a single pixel in the original segment would not get
covered by the shorter segment. Yes, the situation will occur, but it's
maybe one in a billion, maybe even more rare if things are done very
carefully. Precise perfect math isn't needed. 64 bits is good enough.
Smart programming will do the job well.
Seeing the nature of the problems in STL I'm absolutely sure that the
problem in OpenSCAD is with careless handling of 64 bit and 32 bit floats.
I don't know where the problem is happening - whether it's in OpenSCAD
proper or if it's in CGAL. Perhaps fixing this in OpenSCAD is outside the
scope of that code. I may get around to finding the issue, depending on
how I continue further on this project. I may decide to build a CSG
engine, as a webservice maybe (small process within your larger process
which communicates over UDP or TCP with the webservice - that way I can
write it in Java to start with, which will make prototyping much easier),
and will discover more along the way. If I dive into these problems
head-first w.r.t. OpenSCAD and CGAL I may get lost or drown; it may be
better for me to study this starting from a blank sheet of paper.
Without having the specific experience in computation geometry to know for
sure where the problem lies, it's clear to me that this is a problem with
casting between 32 bits and 64 bits.
Thank you for taking the time to read through this email.
Repsectfully,
Nerius Anthony Landys
Sent with Proton Mail secure email.
------- Original Message -------
On Wednesday, June 7th, 2023 at 4:53 PM, Torsten Paul Torsten.Paul@gmx.de
wrote:
On 07.06.23 23:43, neri-engineering via Discuss wrote:
It's "only a workaround" (not good practice in general) because
if you want to begin to do truly powerful things, by combining
pieces of re-usable code in various ways, in ways that you have
not yet even considered, then you'll soon realize that the
"nudge strategy" will lead to all sorts of bottlenecks.
I'm viewing this as accepting real world computing as opposed to
perfect math. But if you find ways of reducing the need that would
be very nice. I'm doubtful it can be eliminated completely without
any other kind of compromise.
ciao,
Torsten.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
---------- Forwarded message ----------
From: neri-engineering via Discuss discuss@lists.openscad.org
To: OpenSCAD general discussion Mailing-list discuss@lists.openscad.org
Cc: neri-engineering neri-engineering@protonmail.com
Bcc:
Date: Sun, 11 Jun 2023 23:23:30 +0000
Subject: [OpenSCAD] Re: STL best practices & tools
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org