Odd ternary behaviour - 2015.05.15.nightly (git 5451fab)
On 2015-06-07 14:19, Bob Cousins wrote:
Last time I looked at OpenCascade I was unable to build it, I had
trouble getting the demo to run. Hopefully the community edition OCE is
now more polished.
OCE is what I would check first, indeed.
I agree it must be easy to build for it to become a viable alternative.
I would try the following
"OCE sanity check"
Goal: figure out if the library is maintained and usable
0. Check any license restrictions
- Check whether API documentation is understandable
- Check that it builds
- Check that any test examples work and give expected results
"OCE prototype"
Goal: Understand the basics of OCE use, with CSG in mind
4. Figure out how to construct cylinders, spheres etc.
5. Figure out how to do boolean operations with OCE
Assuming the above is successful, it is then possible to use the
knowledge to implement a CSG backend based on OCE.
In my mind, the interface of such a backend would be 100% independent of
OCE and there should even be competing implementations of the same
interface based on CGAL, OCE, ... etc.
Back in the day, I created a similar backend using ACIS. Our goal was
not CSG, but the application code never saw ACIS directly and that
turned out to be a good design decision then.
Carsten Arnholm
On 2015-06-07 18:04, Torsten Paul wrote:
The issue is not so much the actual values, but the algorithms go
unstable. E.g. if the algorithm needs to decide if a point is left
or right of a line and totally fails when getting the wrong answer,
it's essentially useless when using floating point.
A fundamental requirement is that boolean operations must be quite
stable, I agree. There may be several ways to achieve such stability.
It would be interesting to get some information about other options.
For some additional pointers/libs, see
https://github.com/openscad/openscad/wiki/Project%3A-Survey-of-CSG-algorithms
I browsed the list and did a very quick and subjective assessment of the
libraries found there, looking at C++ implementations only:
cork: mesh based, No activity the last 2 years
carve: mesh based, activity one year ago, has some documents (old)
OCE: geometry/topology based, latest update March 2015, big
csgtool: mesh based, Updated 9 months ago
csgjs-cpp: mesh based, No activity the last 2 years
In essence the list contains some "smallish" and poorly maintained (?)
libraries that are mesh based and there is OpenCascade (as represented
by OCE). Perhaps there are other candidates.
To me, the only contender in this list with a solid foundation appears
to be OCE, but again it wasn't a thorough review.
I'm not sure a huge thing like OpenCascade is the right way to go.
A big question would be how to get issues solved that involve the
CSG kernel. Right now my impression is that it's quite hard to do
with CGAL. Of cause that's not easy to find out...
I agree OpenCascade is huge. That is one reason it needs to be
encapsulated with a much simpler CSG-oriented front end call interface
to make it usable in something like OpenSCAD. It will require some
study, but I suspect it is doable over some time. The upside is that you
get a professional geometry/topology backend that is maintained.
I think CGAL does need exact predicates to work for the CSG stuff
(currently Exact_predicates_inexact_constructions_kernel is used).
Ok, I take that to mean one either use CGAL as now or replace it.
Carsten Arnholm
On 06/07/2015 09:48 PM, Carsten Arnholm wrote:
In essence the list contains some "smallish" and poorly maintained (?)
libraries that are mesh based and there is OpenCascade (as
represented by OCE). Perhaps there are other candidates.
Yep, that's one of the reasons why this is not an easy decision.
I agree OpenCascade is huge. That is one reason it needs to be encapsulated
with a much simpler CSG-oriented front end call interface to make it
usable in something like OpenSCAD. It will require some study, but I
suspect it is doable over some time. The upside is that you get
a professional geometry/topology backend that is maintained.
Well, the question is if that's actually an upside or not. It might
be, but I've seen a number of cases where an open source project
is just some 3rd level of customer, mostly ignored by the main
project people. With the smaller projects it's easier to find out
what the actual state is and there is the option to resurrect those.
Anyway, it's probably also a good idea to have a better look around,
e.g. at BRL-CAD where we have good connections or maybe see if the
Antimony kernel could be used.
I think CGAL does need exact predicates to work for the CSG stuff
(currently Exact_predicates_inexact_constructions_kernel is used).
Ok, I take that to mean one either use CGAL as now or replace it.
There might be some options to improve the CGAL usage, but it's
certainly not just easy as some things were tried in the past,
but resulted in other problems (I don't know the details, there's
something in to forum about that).
ciao,
Torsten.
Please define "rational numbers" in terms of CGAL. This sounds like some
none-native object replacing C++ double. If that is so, no wonder
OpenSCAD takes forever to complete computing slightly non-trival models,
using insane amounts of memory.
It's one big reason yes. However CGAL has some very specific requirement
about number behaviour. You don't have to use rationals. If you look
back through the threads you'll find a discussion some time back about
switching to either 64:64 or 32:32 fixed point.
CGAL lets you play with your maths system but doing so involves a mix of
C++ gunk and maths so I've never gotten to the point of implementing the
fixed point methods.
Is it possible to use CGAL with only native double variables, avoiding
"rational numbers" entirely? If yes, this would be an interesting short
Not usefully. They don't really have the right properties. The binary STL
file format is a disaster area in general (not just openscad) due to this
and requires you use dictionaries and either clean the mesh or tweak it
in order to get valid STL.
Alan
I've had also had problems with moderately complex models that have
unacceptably long rendering times.
Rationale numbers aren't the only problem. Things get much faster if you
don't union a large number of little pieces together.
I am in favour of changing OpenSCAD so that implicit unions are suppressed
in most cases. I think most slicers do not mind if your STL file contains
overlapping objects. I would suppress the top level implicit union by
default, and add an option to "Export as STL" to perform a union. I
typically want to render my object many times during development before I
am ready to create an STL, and I'd like those non-final renders to be
faster.
On 7 June 2015 at 07:52, Carsten Arnholm arnholm@arnholm.org wrote:
On 2015-06-05 23:39, doug moen wrote:
Rational numbers are very slow compared to floating point. They also
take up a lot of memory, especially if you do long chains of
multiply/divides, which causes the denominators to get increasingly
bigger.
The OpenSCAD language uses floating point to represent numbers (which is
good, for speed). But then it uses CGAL for rendering, which involves
translating those floats into rational numbers. CGAL is incredibly slow,
and one significant reason is the use of rational numbers.
Please define "rational numbers" in terms of CGAL. This sounds like some
none-native object replacing C++ double. If that is so, no wonder OpenSCAD
takes forever to complete computing slightly non-trival models, using
insane amounts of memory.
I have recently created an OpenSCAD model that was somewhat non-trivial,
although quite small compared to models I used to work with 10+ years ago,
using a commercial library (ACIS). I managed to complete my OpenSCAD model,
but it was painfully slow and I will not attempt anything larger as things
stand.
Perhaps the argument for "rational numbers" in CGAL is some illusion of
infinite precision. The fact that you may end up with non-manifold STL
files anyway, shows it really isn't worth it. In ACIS the stated precision
was 1E-6 using ordinary doubles, and we had success using it (of course
there were numerical problems at times). 1E-6 means one millionth of a
millimeter if the model units is in mm. For 3d printing purposes it is
sufficient.
I have a long term goal of revisiting OpenCascade, but it will take time
to do so. It is 20 years since I (briefly) looked at it.
Is it possible to use CGAL with only native double variables, avoiding
"rational numbers" entirely? If yes, this would be an interesting short
term thing to try and see if it would speed things up. If no, then a
replacement such as OpenCascade might become a desired goal sooner.
Carsten Arnholm
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On 2015-06-08 02:42, doug moen wrote:
I've had also had problems with moderately complex models that have
unacceptably long rendering times.
Both preview (F5) and final rendering (F6) became essentially unusable
for my case on a reasonably fast Win7 machine. Every move or rotate took
many seconds to complete in F5 mode, and with F6 I had time to make a
cup of coffee. After completing F6, rotate was fast. These things are
related to how OpenGL is used I think.
Rationale numbers aren't the only problem. Things get much faster if
you don't union a large number of little pieces together.
If boolean operations are slow, it might help using them less .... for a
while. However, the main issue is why they are slow. The "rational
number" feature is probably a major cause, but there might be other
problems too. Essentially, if the implementation is O(n²) or worse,
reducing the number of unions used will not make a big difference in the
long run. You really need an efficient back end for boolean operations,
something like O(n*log n).
I do agree it would be good to have a faster preview, however it is
done.
Carsten Arnholm
On Sun, 7 Jun 2015 20:42:19 -0400
doug moen doug@moens.org wrote:
I've had also had problems with moderately complex models that have
unacceptably long rendering times.
Rationale numbers aren't the only problem. Things get much faster if you
don't union a large number of little pieces together.
That may well be true, but if you fixe the underlying maths to be fixed
point 32:32 or similar then you'd be arguing about tiny fractions of the
time taken now and it really wouldn't matter either way.
Alan
Carsten Arnholm said:
if the implementation is O(n²) or worse, reducing the number of unions used
will not make a big difference in the long run. You really need an
efficient back end for boolean operations, something like O(n*log n).
I ran a simple benchmark on union(). It is a bit slower than O(n), but much
faster than O(n^2). So it's probably O(n*log n) for some log base. The time
complexity may be model dependent, and my test had a simple structure.
Anyway, if this time complexity result for union holds true in most cases,
then probably the rationals are the bigger performance problem.
On my underpowered Windows machine, with the latest release,
- a single sphere(10) rendered in 0s
- two overlapping sphere(10)s rendered in 5s
- 10 overlapping sphere(10)s in 58s
- 100 overlapping sphere(10)s in 951s
On 8 June 2015 at 02:43, arnholm@arnholm.org wrote:
On 2015-06-08 02:42, doug moen wrote:
I've had also had problems with moderately complex models that have
unacceptably long rendering times.
Both preview (F5) and final rendering (F6) became essentially unusable for
my case on a reasonably fast Win7 machine. Every move or rotate took many
seconds to complete in F5 mode, and with F6 I had time to make a cup of
coffee. After completing F6, rotate was fast. These things are related to
how OpenGL is used I think.
Rationale numbers aren't the only problem. Things get much faster if
you don't union a large number of little pieces together.
If boolean operations are slow, it might help using them less .... for a
while. However, the main issue is why they are slow. The "rational number"
feature is probably a major cause, but there might be other problems too.
Essentially, if the implementation is O(n²) or worse, reducing the number
of unions used will not make a big difference in the long run. You really
need an efficient back end for boolean operations, something like O(n*log
n).
I do agree it would be good to have a faster preview, however it is done.
Carsten Arnholm