General approach
On 2019-07-07 18:15, nop head wrote:
I avoid floating point problems by never relying on values being exact
unless they are integers and by avoiding very close vertices that
might get merged.
Which is the same as assuming floating point coordinates everywhere. It
seems the use of 'rational numbers' in CGAL adds no real benefits in
precision, but instead adds cost in the form of lost performance and
increased memory consumption. Add the unpredictable grid stuff in
OpenSCAD and it is questionable if anything is gained compared to
computing with floating point numbers everywhere.
Carsten Arnholm
All this discussion leads far away from the origin of the thread. It may
explain, why in very rare cases extrusions fail, when vertices are to close
(even not identical) or a Boolean operation leads to a CGAL error. But I
dare to say that in 99.99% of all problems people have when sweeping,
skinning, or constructing polyhedra, there are computational or logical bugs
involved and not snap-to-grid effects.
I only mentioned this category of possible errors, because they can indeed
occur if e.g. mirrored, translated or rotated versions of skinned objects
are unioned, or symmetries are constructed by use of Boolean operations in a
more general sense, since the thread originator asked to get some opinion on
this technique.
cacb wrote
Which is the same as assuming floating point coordinates everywhere. It
seems the use of 'rational numbers' in CGAL adds no real benefits in
precision, but instead adds cost in the form of lost performance and
increased memory consumption. Add the unpredictable grid stuff in
OpenSCAD and it is questionable if anything is gained compared to
computing with floating point numbers everywhere.
Carsten, as CGAL is a piece of software on its own, and there seems no
floating point number alternative in sight, one would have to change/adopt
the number representation and arithmetics (!) in OpenSCAD in order to avoid
all this problems and gain a sort of seemless representation. Obviously this
will hold only up the point, where STL imports are involved, or floating
point numbers come into play for similar reasons. This theme has been
discussed extensively a while ago, without concrete results - no way to do
away with it.
--
Sent from: http://forum.openscad.org/
Actually, now I can see a better way to do what I wanted.
I'm trying to join two arched pathways one is in one octant and the other
is in the next octant, they intersect.
Before I was subtracting a mirror of a solid version of one from the other.
Now I simply subtract a cube (actually a rectangular box) that is wholly in
the next octant. I take the resulting shape and mirror it.
OpenSCAD gives me a warning that it might not be valid 2-manifold (which is
probably due to some error in the arched pathway before a cube was even
subtracted from it) but things LOOK close to what I want (unlike before).
So this is progress.
Thanks for the help people.
On Sun, Jul 7, 2019 at 5:24 PM Parkinbot rudolf@digitaldocument.de wrote:
All this discussion leads far away from the origin of the thread. It may
explain, why in very rare cases extrusions fail, when vertices are to close
(even not identical) or a Boolean operation leads to a CGAL error. But I
dare to say that in 99.99% of all problems people have when sweeping,
skinning, or constructing polyhedra, there are computational or logical
bugs
involved and not snap-to-grid effects.
I only mentioned this category of possible errors, because they can indeed
occur if e.g. mirrored, translated or rotated versions of skinned objects
are unioned, or symmetries are constructed by use of Boolean operations in
a
more general sense, since the thread originator asked to get some opinion
on
this technique.
cacb wrote
Which is the same as assuming floating point coordinates everywhere. It
seems the use of 'rational numbers' in CGAL adds no real benefits in
precision, but instead adds cost in the form of lost performance and
increased memory consumption. Add the unpredictable grid stuff in
OpenSCAD and it is questionable if anything is gained compared to
computing with floating point numbers everywhere.
Carsten, as CGAL is a piece of software on its own, and there seems no
floating point number alternative in sight, one would have to change/adopt
the number representation and arithmetics (!) in OpenSCAD in order to avoid
all this problems and gain a sort of seemless representation. Obviously
this
will hold only up the point, where STL imports are involved, or floating
point numbers come into play for similar reasons. This theme has been
discussed extensively a while ago, without concrete results - no way to do
away with it.
--
Sent from: http://forum.openscad.org/
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On 2019-07-07 23:24, Parkinbot wrote:
Carsten, as CGAL is a piece of software on its own, and there seems no
floating point number alternative in sight,
Actually, that is not true. There is at least one surface mesh /
floating point vertex based alternative, namely Carve. The original is
at https://github.com/folded/carve and my fork is at
https://github.com/arnholm/carve. My fork fixes some compiler warnings
and makes carve MSVC compatible, plus replaces some deprecated C++
features (auto_ptr) with modern equivalents (unique_ptr).
I use Carve in AngelCAD, so indeed it is possible. You can compare the
features of AngelCAD and OpenSCAD to verify.
one would have to change/adopt
the number representation and arithmetics (!) in OpenSCAD in order to
avoid
all this problems and gain a sort of seemless representation.
All you need to do is a bit of software re-design, i.e. define the API
(Application Programming Interface) between the application (=OpenSCAD)
and the library (=CGAL today). I.e. what is the minimum set of features
used by OpenSCAD. Such a C++ API will have floating point vertices since
that is what the application generates anyway. Defining the API is stage
1.
Stage 2 is to implement the API back-end using CGAL and check that
OpenSCAD still works as before. Stage 3 is to implement the API back-end
using Carve (eliminating 'rational numbers').
Obviously this
will hold only up the point, where STL imports are involved,
STL import is a different animal which isn't directly related to
coordinate representation, importing STL is a problem regardless of
whether one employs floating point or 'rational number' coordinates
internally.
The issue with STL import to a modeller (as opposed to a slicer) is that
it is a 'polygon soup' with zero topological information, requiring
extensive coordinate matching. Such matching is prone to failure as it
is a matter of subjective interpretation. For this and other reasons, I
have chosen to do STL import in 2 stages, first convert to OBJ/OFF/AMF
in a separate application (polyfix, ref
https://github.com/arnholm/angelcad/releases ) that does
interpretations/repairs and establishes a topology. Then import from
OBJ/OFF/AMF into AngelCAD.
OpenSCAD could choose to do it differently, e.g. one could declare STL
import as a legacy feature and promote formats such as OBJ (or whatever)
as better alternatives.
or floating
point numbers come into play for similar reasons. This theme has been
discussed extensively a while ago, without concrete results - no way to
do
away with it.
See above. As you say this was discussed before and like now I was told
it could not be done. Therefore, I did it :-)
Carsten Arnholm
cacb wrote
On 2019-07-07 23:24, Parkinbot wrote:
Carsten, as CGAL is a piece of software on its own, and there seems no
floating point number alternative in sight,
Actually, that is not true. There is at least one surface mesh /
floating point vertex based alternative, namely Carve.
Carsten, how could one miss this?
But even without having had a closer look into Carve and your adapation, I
dare to doubt that a pure floating point representation approach on both
sides, OpenSCAD and the rendering part, will be able to do away with the
snap-to-grid problem, because the problem rather arises with the use of
floating point representation. Any translation within a non aequidistant
grid will suffer from a snap-to-grid result. As floating point arithmetic is
not commuative (e.g. a+b-c = a-c+b will not hold) Boolean operations will
have to deal with snap-to-grids all the time. So two operations will not
have the same result with respect to translation. What does this mean for a
union operation? Or for a symmetric object construction scheme as proposed
by the thread starter.
CGAL may be slow, but the architects' decision to build on a rational number
representation had good reasons ...
--
Sent from: http://forum.openscad.org/
CGAL may be slow, but the architects' decision to build on a rational
number representation had good reasons .
Yes but OpenSCAD gains zero advantage from this because it converts back to
doubles and snaps to a grid and then feeds the results back to CGAL.
If Carve can do booleans in floating point then OpenSCAD will simply feed
in floats and get floats back. There would be no need to snap to a grid and
if it works in floats, rather than doubles, STL export will work.
On Mon, 8 Jul 2019 at 10:23, Parkinbot rudolf@digitaldocument.de wrote:
cacb wrote
On 2019-07-07 23:24, Parkinbot wrote:
Carsten, as CGAL is a piece of software on its own, and there seems no
floating point number alternative in sight,
Actually, that is not true. There is at least one surface mesh /
floating point vertex based alternative, namely Carve.
Carsten, how could one miss this?
But even without having had a closer look into Carve and your adapation, I
dare to doubt that a pure floating point representation approach on both
sides, OpenSCAD and the rendering part, will be able to do away with the
snap-to-grid problem, because the problem rather arises with the use of
floating point representation. Any translation within a non aequidistant
grid will suffer from a snap-to-grid result. As floating point arithmetic
is
not commuative (e.g. a+b-c = a-c+b will not hold) Boolean operations will
have to deal with snap-to-grids all the time. So two operations will not
have the same result with respect to translation. What does this mean for a
union operation? Or for a symmetric object construction scheme as proposed
by the thread starter.
CGAL may be slow, but the architects' decision to build on a rational
number
representation had good reasons ...
--
Sent from: http://forum.openscad.org/
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On 2019-07-08 11:23, Parkinbot wrote:
cacb wrote
On 2019-07-07 23:24, Parkinbot wrote:
Carsten, as CGAL is a piece of software on its own, and there seems
no
floating point number alternative in sight,
Actually, that is not true. There is at least one surface mesh /
floating point vertex based alternative, namely Carve.
Carsten, how could one miss this?
Being convinced no alternative exists, one stops looking for it?
But even without having had a closer look into Carve and your
adapation, I
dare to doubt that a pure floating point representation approach on
both
sides, OpenSCAD and the rendering part, will be able to do away with
the
snap-to-grid problem, because the problem rather arises with the use
of
floating point representation. Any translation within a non
aequidistant
grid will suffer from a snap-to-grid result. As floating point
arithmetic is
not commuative (e.g. a+b-c = a-c+b will not hold) Boolean operations
will
have to deal with snap-to-grids all the time. So two operations will
not
have the same result with respect to translation. What does this mean
for a
union operation? Or for a symmetric object construction scheme as
proposed
by the thread starter.
CGAL may be slow, but the architects' decision to build on a rational
number
representation had good reasons ...
For your theory to hold you need to use exact arithmetic at all levels
and not just in parts. OpenSCAD doesn't do that so all you really get is
floating point precision anyway. All theory aside, what matters is
practice, try it for yourself. AngelCAD uses my Carve fork via xcsg
https://github.com/arnholm/xcsg . I suggest you try AngelCAD to see if
the theory holds (the AngelCAD binary bundles xcsg). Link to
documentation and download at https://arnholm.github.io/angelcad-docs/ .
All talk of 'grid' requirement is a misunderstanding the way I see it,
unless you talk about the special case of explicit coordinate matching
from an STL polygon soup, where there are no shared vertices. Boolean
operations don't work on polygon soups, they work on polyhedra. This is
true in both CGAL and Carve. In AngelCAD/xcsg there are no grids.
Carsten Arnholm
On 2019-07-08 12:44, nop head wrote:
Yes but OpenSCAD gains zero advantage from this because it converts
back to doubles and snaps to a grid and then feeds the results back to
CGAL.
Correct (on zero advantage).
If Carve can do booleans in floating point then OpenSCAD will simply
feed in floats and get floats back. There would be no need to snap to
a grid and if it works in floats, rather than doubles, STL export will
work.
Carve works in native double precision. I have implemented STL export by
casting to float (i.e. to single precision) at the point of writing to
binary file. Single precision in binary STL is another aspect of STL
(in addition to the polygon soup issue) that makes it unsuitable for
model exchange between modellers, including the case where the exporter
and importer application is the same (OpenSCAD). You lose more precision
using STL than the difference between double precision and 'rational
numbers'. Single precision is equivalent to just 6-7 significant digits.
Carsten Arnholm
On 08.07.19 12:55, arnholm@arnholm.org wrote:
Being convinced no alternative exists, one stops looking for it?
Not sure who would be convinced of that. I can at least say,
I'm not and I would find it awesome to have the option to use
other libraries.
https://github.com/openscad/openscad/wiki/Project:-Survey-of-CSG-algorithms
That topic actually had a student applying for for this years
GSoC - but we don't have enough people to mentor more than the
two project we currently support.
ciao,
Torsten.
If you cast double to float then you will have the same STL export problems
that OpenSCAD has. Any reduction in resolution needs to fix degenerate
triangles and self intersections.
Note also OpenSCAD uses its own PolySet format and that is also a polygon
soup like STL. The only difference is it doubles and actually polygons, not
just triangles.
On Mon, 8 Jul 2019 at 13:03, Torsten Paul Torsten.Paul@gmx.de wrote:
On 08.07.19 12:55, arnholm@arnholm.org wrote:
Being convinced no alternative exists, one stops looking for it?
Not sure who would be convinced of that. I can at least say,
I'm not and I would find it awesome to have the option to use
other libraries.
https://github.com/openscad/openscad/wiki/Project:-Survey-of-CSG-algorithms
That topic actually had a student applying for for this years
GSoC - but we don't have enough people to mentor more than the
two project we currently support.
ciao,
Torsten.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org