Re: manifold error
I think the openscad userspace computation issue is a little more
complicated. Certainly having faster execution would help, but there's
also the problem of efficient access to advanced data structures. My
recollection is that efficient algorithms for geometric processes tend to
require things like a priority queue, and it doesn't appear like this can
be implemented to run in the required O(log n) operation time.
Regarding warning levels, the discussion at
https://github.com/openscad/openscad/issues/5135 seems to suggest some
extra complications about this.
On Sun, Oct 20, 2024 at 1:27 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
There are two issues here:
- openscad userspace computation is slow.
- warning levels
For 1, there are ways to improve this situation, but it will take quite a
bit of effort and I don't have too much time to pull it off now. Basically
just make the interpretation using bytecode and skip all the expensive
hashtable lookup for each variable/function argument, as well as AST
traversal. It is not hard, but it is quite tedious to rewrite everything
and make sure the behavior is compatible.
For warning levels, IMO fixing non-manifold geometry is probably common
enough that it can be regarded as a debug level info.
On 19/10/2024 04:38, Adrian Mariano via Discuss wrote:
There is an OpenSCAD issue about this:
https://github.com/openscad/openscad/issues/5135. I thought they WERE
going to make that an informational message rather than a warning. I
raised the point that it's basically impossible to reasonably use OpenSCAD
without setting stop on first warning because it just causes an error to
cascade into pages of garbage and hide the true problem.
If OpenSCAD is going to be picky then BOSL2 has to run vnf_merge_points()
to look for the duplicate points and combine them in the topology. You
can do this now if you want to make it work. We don't do this
automatically because we are nervous that it will be slow, though for the
above rounded_prism example it's not terrible on my machine, boosting
preview time from 0.08s to 0.3 s, so a factor of three slower, but still
fast enough. However, if you round all the edges preview time goes from
0.7s to 5s which is getting annoying. (I did this tests with a large
splinesteps value, so it doesn't need to be quite so bad.) So run time can
be a potential concern at least sometimes. Almost every interesting shape
BOSL2 creates is going to have duplicate non-exact points, so longer term
it raises questions about basically complicating things throughout BOSL2 to
track edges, for example, to reduce the points that need to be checked for
merges. Maybe if they ever introduce structures outside of textmetrics
this will seem more reasonable to do. (Note that the rounded square prism
is constructed from 26 bezier patches, one for each face, edge and corner
and I don't see a reasonable way to actually track the faces that meet from
different patches at the same edge to directly exploit the knowledge that
the patches share a boundary.)
On Fri, Oct 18, 2024 at 4:01 PM Todd Allen via Discuss <
discuss@lists.openscad.org> wrote:
If I recall correctly, openscad should try the CGAL way of repairing
meshes when manifold cannot import
the mesh, no idea why it doesn't work in this case.
I reported this incorrectly as an error which stopped rendering. But it
is only a warning. However I had the option set to stop at first warning.
Disabling that option allows this to successfully render.
If this sort of mesh issue is expected to be commonly corrected by the
automatic repair process perhaps it would be ok to downgrade this message
from WARNING to INFO and only after the repair fails issue a warning or let
it error out.
On Fri, Oct 18, 2024 at 12:45 PM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
Are you saying that vertexes shared between faces must use the same
indexes?
Both yes and no. If you mean vertices shared between triangles must use
the same indices, yes. But you can have vertices with the same
coordinate, so they can have different indices and are not shared by
triangles, despite triangles containing them can be touching
geometrically (if you consider coordinates).
The topological definition of manifoldness used in manifold is actually
very simple, see
https://github.com/elalish/manifold/wiki/Manifold-Library#manifoldness-definition
Every edge of every triangle must contain the same two vertices (by
index) as exactly one other triangle edge, and the start and end
vertices must switch places between these two edges. The triangle
vertices must appear in counter-clockwise order when viewed from the
outside of the manifold.
I think the issue is in the polyhedron triangle list not being manifold.
E.g. there may be a tiny open hole in the mesh, but merging vertices
close to each other may make the hole disappear because all vertices
around the hole are merged into one. If I recall correctly, openscad
should try the CGAL way of repairing meshes when manifold cannot import
the mesh, no idea why it doesn't work in this case.
On 19/10/2024 01:24, Jordan Brown wrote:
On 10/18/2024 9:52 AM, Chun Kit LAM via Discuss wrote:
But manifold doesn't really care about coordinates when checking for
manifoldness, it just cares about vertex indices in the list of
triangles. Previously, openscad would snap vertices to a grid and
merge identical vertices, but that can lose manifoldness in general
and it is really hard to fix, so it is no longer doing that when the
mesh PolySet can directly be imported into manifold.
Are you saying that vertexes shared between faces must use the same
indexes? Experiments indicate that there's no such requirement. I
constructed a cube out of 24 vertexes, and Manifold seemed perfectly
happy with it. Correcting the 2e-16 values in the rounded prism to
zero, without eliminating the duplication, made the problem go away.
I'm not really a fan of the grid-snap scheme; it causes problems on
its own. Getting rid of it might be a win, but will likely cause
problems like this one. (But I admit I have no experience with not
using it.) I'd like to think that we could have a scheme that snapped
together "clusters" of points that are very close to one another (say,
a difference of less than one part in 10^14), and gave up if a cluster
ever spanned the limit. (That is, if point A is considered close to
B, and B is considered close to C, but A is not close to C.) Such a
scheme seems like it could have a very high accuracy rate, fixing FP
precision problems without merging points that should be distinct.
But I suspect that it would also be quite expensive.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
I think it is possible to have O(log n) priority queue for purely
functional languages. The problem is that you can't use lists for that,
and have to ADT as nested lists or lambdas. Not sure if openscad handles
sharing well.
On 20/10/2024 20:32, Adrian Mariano via Discuss wrote:
I think the openscad userspace computation issue is a little more
complicated. Certainly having faster execution would help, but
there's also the problem of efficient access to advanced data
structures. My recollection is that efficient algorithms for
geometric processes tend to require things like a priority queue, and
it doesn't appear like this can be implemented to run in the required
O(log n) operation time.
Regarding warning levels, the discussion at
https://github.com/openscad/openscad/issues/5135 seems to suggest some
extra complications about this.
On Sun, Oct 20, 2024 at 1:27 AM Chun Kit LAM via Discuss
discuss@lists.openscad.org wrote:
There are two issues here:
1. openscad userspace computation is slow.
2. warning levels
For 1, there are ways to improve this situation, but it will take
quite a bit of effort and I don't have too much time to pull it
off now. Basically just make the interpretation using bytecode and
skip all the expensive hashtable lookup for each variable/function
argument, as well as AST traversal. It is not hard, but it is
quite tedious to rewrite everything and make sure the behavior is
compatible.
For warning levels, IMO fixing non-manifold geometry is probably
common enough that it can be regarded as a debug level info.
On 19/10/2024 04:38, Adrian Mariano via Discuss wrote:
There is an OpenSCAD issue about this:
https://github.com/openscad/openscad/issues/5135. I thought they
WERE going to make that an informational message rather than a
warning. I raised the point that it's basically impossible to
reasonably use OpenSCAD without setting stop on first warning
because it just causes an error to cascade into pages of garbage
and hide the true problem.
If OpenSCAD is going to be picky then BOSL2 has to run
vnf_merge_points() to look for the duplicate points and combine
them in the topology. You can do this now if you want to make
it work. We don't do this automatically because we are nervous
that it will be slow, though for the above rounded_prism example
it's not terrible on my machine, boosting preview time from 0.08s
to 0.3 s, so a factor of three slower, but still fast enough.
However, if you round all the edges preview time goes from 0.7s
to 5s which is getting annoying. (I did this tests with a large
splinesteps value, so it doesn't need to be quite so bad.) So
run time can be a potential concern at least sometimes. Almost
every interesting shape BOSL2 creates is going to have duplicate
non-exact points, so longer term it raises questions about
basically complicating things throughout BOSL2 to track edges,
for example, to reduce the points that need to be checked for
merges. Maybe if they ever introduce structures outside of
textmetrics this will seem more reasonable to do. (Note that
the rounded square prism is constructed from 26 bezier patches,
one for each face, edge and corner and I don't see a reasonable
way to actually track the faces that meet from different patches
at the same edge to directly exploit the knowledge that the
patches share a boundary.)
On Fri, Oct 18, 2024 at 4:01 PM Todd Allen via Discuss
<discuss@lists.openscad.org> wrote:
If I recall correctly, openscad should try the CGAL way of
repairing meshes when manifold cannot import
the mesh, no idea why it doesn't work in this case.
I reported this incorrectly as an error which stopped
rendering. But it is only a warning. However I had the
option set to stop at first warning. Disabling that option
allows this to successfully render.
If this sort of mesh issue is expected to be commonly
corrected by the automatic repair process perhaps it would be
ok to downgrade this message from WARNING to INFO and only
after the repair fails issue a warning or let it error out.
On Fri, Oct 18, 2024 at 12:45 PM Chun Kit LAM via Discuss
<discuss@lists.openscad.org> wrote:
> Are you saying that vertexes shared between faces must
use the same
indexes?
Both yes and no. If you mean vertices shared between
triangles must use
the same indices, yes. But you can have vertices with the
same
coordinate, so they can have different indices and are
not shared by
triangles, despite triangles containing them can be touching
geometrically (if you consider coordinates).
The topological definition of manifoldness used in
manifold is actually
very simple, see
https://github.com/elalish/manifold/wiki/Manifold-Library#manifoldness-definition
> Every edge of every triangle must contain the same two
vertices (by
index) as exactly one other triangle edge, and the start
and end
vertices must switch places between these two edges. The
triangle
vertices must appear in counter-clockwise order when
viewed from the
outside of the manifold.
I think the issue is in the polyhedron triangle list not
being manifold.
E.g. there may be a tiny open hole in the mesh, but
merging vertices
close to each other may make the hole disappear because
all vertices
around the hole are merged into one. If I recall
correctly, openscad
should try the CGAL way of repairing meshes when manifold
cannot import
the mesh, no idea why it doesn't work in this case.
On 19/10/2024 01:24, Jordan Brown wrote:
On 10/18/2024 9:52 AM, Chun Kit LAM via Discuss wrote:
But manifold doesn't really care about coordinates
when checking for
manifoldness, it just cares about vertex indices in
the list of
triangles. Previously, openscad would snap vertices to
a grid and
merge identical vertices, but that can lose
manifoldness in general
and it is really hard to fix, so it is no longer doing
that when the
mesh PolySet can directly be imported into manifold.
Are you saying that vertexes shared between faces must
use the same
indexes? Experiments indicate that there's no such
requirement. I
constructed a cube out of 24 vertexes, and Manifold
seemed perfectly
happy with it. Correcting the 2e-16 values in the
rounded prism to
zero, without eliminating the duplication, made the
problem go away.
I'm not really a fan of the grid-snap scheme; it causes
problems on
its own. Getting rid of it might be a win, but will
likely cause
problems like this one. (But I admit I have no
experience with *not*
using it.) I'd like to think that we could have a
scheme that snapped
together "clusters" of points that are very close to
one another (say,
a difference of less than one part in 10^14), and gave
up if a cluster
ever spanned the limit. (That is, if point A is
considered close to
B, and B is considered close to C, but A is not close
to C.) Such a
scheme seems like it could have a very high accuracy
rate, fixing FP
precision problems without merging points that should
be distinct.
But I suspect that it would also be quite expensive.
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to
discuss-leave@lists.openscad.org
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email todiscuss-leave@lists.openscad.org
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email todiscuss-leave@lists.openscad.org
What is the algorithmic order of what is implemented? Is O(log n) actually
required? The issue implied by Chun Kit's comment on ADT and nested lists
and lambdas is likely what is making the eval expensive (or in alg analysis
make the constant 'K' go through the roof).
My experience with running into issues like this is that there is rarely a
simple fix and you have to start a new version of a project with time
profiling unit-testing baked in. I'm not sure anyone has the time for that
(unless someone is taking this up as a student project, or getting paid).
On Sun, Oct 20, 2024 at 8:48 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
I think it is possible to have O(log n) priority queue for purely
functional languages. The problem is that you can't use lists for that, and
have to ADT as nested lists or lambdas. Not sure if openscad handles
sharing well.
On 20/10/2024 20:32, Adrian Mariano via Discuss wrote:
I think the openscad userspace computation issue is a little more
complicated. Certainly having faster execution would help, but there's
also the problem of efficient access to advanced data structures. My
recollection is that efficient algorithms for geometric processes tend to
require things like a priority queue, and it doesn't appear like this can
be implemented to run in the required O(log n) operation time.
Regarding warning levels, the discussion at
https://github.com/openscad/openscad/issues/5135 seems to suggest some
extra complications about this.
On Sun, Oct 20, 2024 at 1:27 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
There are two issues here:
- openscad userspace computation is slow.
- warning levels
For 1, there are ways to improve this situation, but it will take quite a
bit of effort and I don't have too much time to pull it off now. Basically
just make the interpretation using bytecode and skip all the expensive
hashtable lookup for each variable/function argument, as well as AST
traversal. It is not hard, but it is quite tedious to rewrite everything
and make sure the behavior is compatible.
For warning levels, IMO fixing non-manifold geometry is probably common
enough that it can be regarded as a debug level info.
On 19/10/2024 04:38, Adrian Mariano via Discuss wrote:
There is an OpenSCAD issue about this:
https://github.com/openscad/openscad/issues/5135. I thought they WERE
going to make that an informational message rather than a warning. I
raised the point that it's basically impossible to reasonably use OpenSCAD
without setting stop on first warning because it just causes an error to
cascade into pages of garbage and hide the true problem.
If OpenSCAD is going to be picky then BOSL2 has to run vnf_merge_points()
to look for the duplicate points and combine them in the topology. You
can do this now if you want to make it work. We don't do this
automatically because we are nervous that it will be slow, though for the
above rounded_prism example it's not terrible on my machine, boosting
preview time from 0.08s to 0.3 s, so a factor of three slower, but still
fast enough. However, if you round all the edges preview time goes from
0.7s to 5s which is getting annoying. (I did this tests with a large
splinesteps value, so it doesn't need to be quite so bad.) So run time can
be a potential concern at least sometimes. Almost every interesting shape
BOSL2 creates is going to have duplicate non-exact points, so longer term
it raises questions about basically complicating things throughout BOSL2 to
track edges, for example, to reduce the points that need to be checked for
merges. Maybe if they ever introduce structures outside of textmetrics
this will seem more reasonable to do. (Note that the rounded square prism
is constructed from 26 bezier patches, one for each face, edge and corner
and I don't see a reasonable way to actually track the faces that meet from
different patches at the same edge to directly exploit the knowledge that
the patches share a boundary.)
On Fri, Oct 18, 2024 at 4:01 PM Todd Allen via Discuss <
discuss@lists.openscad.org> wrote:
If I recall correctly, openscad should try the CGAL way of repairing
meshes when manifold cannot import
the mesh, no idea why it doesn't work in this case.
I reported this incorrectly as an error which stopped rendering. But it
is only a warning. However I had the option set to stop at first warning.
Disabling that option allows this to successfully render.
If this sort of mesh issue is expected to be commonly corrected by the
automatic repair process perhaps it would be ok to downgrade this message
from WARNING to INFO and only after the repair fails issue a warning or let
it error out.
On Fri, Oct 18, 2024 at 12:45 PM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
Are you saying that vertexes shared between faces must use the same
indexes?
Both yes and no. If you mean vertices shared between triangles must use
the same indices, yes. But you can have vertices with the same
coordinate, so they can have different indices and are not shared by
triangles, despite triangles containing them can be touching
geometrically (if you consider coordinates).
The topological definition of manifoldness used in manifold is actually
very simple, see
https://github.com/elalish/manifold/wiki/Manifold-Library#manifoldness-definition
Every edge of every triangle must contain the same two vertices (by
index) as exactly one other triangle edge, and the start and end
vertices must switch places between these two edges. The triangle
vertices must appear in counter-clockwise order when viewed from the
outside of the manifold.
I think the issue is in the polyhedron triangle list not being
manifold.
E.g. there may be a tiny open hole in the mesh, but merging vertices
close to each other may make the hole disappear because all vertices
around the hole are merged into one. If I recall correctly, openscad
should try the CGAL way of repairing meshes when manifold cannot import
the mesh, no idea why it doesn't work in this case.
On 19/10/2024 01:24, Jordan Brown wrote:
On 10/18/2024 9:52 AM, Chun Kit LAM via Discuss wrote:
But manifold doesn't really care about coordinates when checking for
manifoldness, it just cares about vertex indices in the list of
triangles. Previously, openscad would snap vertices to a grid and
merge identical vertices, but that can lose manifoldness in general
and it is really hard to fix, so it is no longer doing that when the
mesh PolySet can directly be imported into manifold.
Are you saying that vertexes shared between faces must use the same
indexes? Experiments indicate that there's no such requirement. I
constructed a cube out of 24 vertexes, and Manifold seemed perfectly
happy with it. Correcting the 2e-16 values in the rounded prism to
zero, without eliminating the duplication, made the problem go away.
I'm not really a fan of the grid-snap scheme; it causes problems on
its own. Getting rid of it might be a win, but will likely cause
problems like this one. (But I admit I have no experience with not
using it.) I'd like to think that we could have a scheme that
snapped
together "clusters" of points that are very close to one another
(say,
a difference of less than one part in 10^14), and gave up if a
cluster
ever spanned the limit. (That is, if point A is considered close to
B, and B is considered close to C, but A is not close to C.) Such a
scheme seems like it could have a very high accuracy rate, fixing FP
precision problems without merging points that should be distinct.
But I suspect that it would also be quite expensive.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
Right now, every polygon operation we have implemented in BOSL2 is O(N^2),
so if you feed it a polygon with 1000 points, which is not absurd, you can
expect a long wait due to quadratic run time. It's tough to know for sure
for the cases at hand whether we're dominated by asymptotic run time or by
a huge constant. That is, a million operations isn't that many, so maybe
if we were just 100x faster the O(N^2) would be fine for practical cases
with polygons. It's also a question of how many points the polygon needs
to have before O(N log N) would matter. As I recall, advanced algorithms
march around the polygon and enter things into a priority queue and can
find the intersections in O(N log N). I tried to re-implement offset() to
be more robust using a method that involves polygon union/intersection type
operations and run time for simple cases was >1 minute. On inputs that I
don't recall but probably had more like 100 points than 1000.
Note that to be clear, the point of a priority queue operation running in
O(log N) is that it means you can do O(N) of them and get O(N log N) so you
beat O(N^2).
For the problem of point merging for polyhedra, it's entirely possible to
have 50,000 points in a polyhedron, and having 1000 points is quite
modest. So how does O(N^2) look for that? You want to run O(N^2)
algorithms on things where N approaches 10^6? Now we have attempted to
implement an O(N log N) algorithm in BOSL2 and at least back when we tested
it, I think it appeared to help, with a crossover point of around 400
points. (Note that improvement from O(N^2) depends on the data being
non-uniform.)
On Sun, Oct 20, 2024 at 11:43 AM John David via Discuss <
discuss@lists.openscad.org> wrote:
What is the algorithmic order of what is implemented? Is O(log n)
actually required? The issue implied by Chun Kit's comment on ADT and
nested lists and lambdas is likely what is making the eval expensive (or in
alg analysis make the constant 'K' go through the roof).
My experience with running into issues like this is that there is rarely a
simple fix and you have to start a new version of a project with time
profiling unit-testing baked in. I'm not sure anyone has the time for that
(unless someone is taking this up as a student project, or getting paid).
On Sun, Oct 20, 2024 at 8:48 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
I think it is possible to have O(log n) priority queue for purely
functional languages. The problem is that you can't use lists for that, and
have to ADT as nested lists or lambdas. Not sure if openscad handles
sharing well.
On 20/10/2024 20:32, Adrian Mariano via Discuss wrote:
I think the openscad userspace computation issue is a little more
complicated. Certainly having faster execution would help, but there's
also the problem of efficient access to advanced data structures. My
recollection is that efficient algorithms for geometric processes tend to
require things like a priority queue, and it doesn't appear like this can
be implemented to run in the required O(log n) operation time.
Regarding warning levels, the discussion at
https://github.com/openscad/openscad/issues/5135 seems to suggest some
extra complications about this.
On Sun, Oct 20, 2024 at 1:27 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
There are two issues here:
- openscad userspace computation is slow.
- warning levels
For 1, there are ways to improve this situation, but it will take quite
a bit of effort and I don't have too much time to pull it off now.
Basically just make the interpretation using bytecode and skip all the
expensive hashtable lookup for each variable/function argument, as well as
AST traversal. It is not hard, but it is quite tedious to rewrite
everything and make sure the behavior is compatible.
For warning levels, IMO fixing non-manifold geometry is probably common
enough that it can be regarded as a debug level info.
On 19/10/2024 04:38, Adrian Mariano via Discuss wrote:
There is an OpenSCAD issue about this:
https://github.com/openscad/openscad/issues/5135. I thought they WERE
going to make that an informational message rather than a warning. I
raised the point that it's basically impossible to reasonably use OpenSCAD
without setting stop on first warning because it just causes an error to
cascade into pages of garbage and hide the true problem.
If OpenSCAD is going to be picky then BOSL2 has to run
vnf_merge_points() to look for the duplicate points and combine them in the
topology. You can do this now if you want to make it work. We don't do
this automatically because we are nervous that it will be slow, though for
the above rounded_prism example it's not terrible on my machine, boosting
preview time from 0.08s to 0.3 s, so a factor of three slower, but still
fast enough. However, if you round all the edges preview time goes from
0.7s to 5s which is getting annoying. (I did this tests with a large
splinesteps value, so it doesn't need to be quite so bad.) So run time can
be a potential concern at least sometimes. Almost every interesting shape
BOSL2 creates is going to have duplicate non-exact points, so longer term
it raises questions about basically complicating things throughout BOSL2 to
track edges, for example, to reduce the points that need to be checked for
merges. Maybe if they ever introduce structures outside of textmetrics
this will seem more reasonable to do. (Note that the rounded square prism
is constructed from 26 bezier patches, one for each face, edge and corner
and I don't see a reasonable way to actually track the faces that meet from
different patches at the same edge to directly exploit the knowledge that
the patches share a boundary.)
On Fri, Oct 18, 2024 at 4:01 PM Todd Allen via Discuss <
discuss@lists.openscad.org> wrote:
If I recall correctly, openscad should try the CGAL way of repairing
meshes when manifold cannot import
the mesh, no idea why it doesn't work in this case.
I reported this incorrectly as an error which stopped rendering. But
it is only a warning. However I had the option set to stop at first
warning. Disabling that option allows this to successfully render.
If this sort of mesh issue is expected to be commonly corrected by the
automatic repair process perhaps it would be ok to downgrade this message
from WARNING to INFO and only after the repair fails issue a warning or let
it error out.
On Fri, Oct 18, 2024 at 12:45 PM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
Are you saying that vertexes shared between faces must use the same
indexes?
Both yes and no. If you mean vertices shared between triangles must
use
the same indices, yes. But you can have vertices with the same
coordinate, so they can have different indices and are not shared by
triangles, despite triangles containing them can be touching
geometrically (if you consider coordinates).
The topological definition of manifoldness used in manifold is
actually
very simple, see
https://github.com/elalish/manifold/wiki/Manifold-Library#manifoldness-definition
Every edge of every triangle must contain the same two vertices (by
index) as exactly one other triangle edge, and the start and end
vertices must switch places between these two edges. The triangle
vertices must appear in counter-clockwise order when viewed from the
outside of the manifold.
I think the issue is in the polyhedron triangle list not being
manifold.
E.g. there may be a tiny open hole in the mesh, but merging vertices
close to each other may make the hole disappear because all vertices
around the hole are merged into one. If I recall correctly, openscad
should try the CGAL way of repairing meshes when manifold cannot
import
the mesh, no idea why it doesn't work in this case.
On 19/10/2024 01:24, Jordan Brown wrote:
On 10/18/2024 9:52 AM, Chun Kit LAM via Discuss wrote:
But manifold doesn't really care about coordinates when checking
for
manifoldness, it just cares about vertex indices in the list of
triangles. Previously, openscad would snap vertices to a grid and
merge identical vertices, but that can lose manifoldness in general
and it is really hard to fix, so it is no longer doing that when
the
mesh PolySet can directly be imported into manifold.
Are you saying that vertexes shared between faces must use the same
indexes? Experiments indicate that there's no such requirement. I
constructed a cube out of 24 vertexes, and Manifold seemed perfectly
happy with it. Correcting the 2e-16 values in the rounded prism to
zero, without eliminating the duplication, made the problem go away.
I'm not really a fan of the grid-snap scheme; it causes problems on
its own. Getting rid of it might be a win, but will likely cause
problems like this one. (But I admit I have no experience with
not
using it.) I'd like to think that we could have a scheme that
snapped
together "clusters" of points that are very close to one another
(say,
a difference of less than one part in 10^14), and gave up if a
cluster
ever spanned the limit. (That is, if point A is considered close to
B, and B is considered close to C, but A is not close to C.) Such a
scheme seems like it could have a very high accuracy rate, fixing FP
precision problems without merging points that should be distinct.
But I suspect that it would also be quite expensive.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
No. I agree that O(N^2) is a problem (and explains why I have had trouble
from time to time with OpenSCAD). Now that I see how you are embedding the
"required" O(log N) within another and that this would already give you an
O(N log N).
BTW, I have only ever once recommended an algorithm that I knew to be
O(N^2) - that was part of a UI initialization where users could update a
command list. It was only ever run once (at boot), was guaranteed to be
limited to 6 to 10 commands at most, this was on a memory limited system,
and some part of the code depended on that list being sorted. A
bubble-sort is only ~6 lines of additional code, and if you add 2 more you
can guarantee that it will never be handed 1,000,000 strings. Even to
implement Qsort would have put a strain on their memory budget.
On Sun, Oct 20, 2024 at 12:07 PM Adrian Mariano via Discuss <
discuss@lists.openscad.org> wrote:
Right now, every polygon operation we have implemented in BOSL2 is O(N^2),
so if you feed it a polygon with 1000 points, which is not absurd, you can
expect a long wait due to quadratic run time. It's tough to know for sure
for the cases at hand whether we're dominated by asymptotic run time or by
a huge constant. That is, a million operations isn't that many, so maybe
if we were just 100x faster the O(N^2) would be fine for practical cases
with polygons. It's also a question of how many points the polygon needs
to have before O(N log N) would matter. As I recall, advanced algorithms
march around the polygon and enter things into a priority queue and can
find the intersections in O(N log N). I tried to re-implement offset() to
be more robust using a method that involves polygon union/intersection type
operations and run time for simple cases was >1 minute. On inputs that I
don't recall but probably had more like 100 points than 1000.
Note that to be clear, the point of a priority queue operation running in
O(log N) is that it means you can do O(N) of them and get O(N log N) so you
beat O(N^2).
For the problem of point merging for polyhedra, it's entirely possible to
have 50,000 points in a polyhedron, and having 1000 points is quite
modest. So how does O(N^2) look for that? You want to run O(N^2)
algorithms on things where N approaches 10^6? Now we have attempted to
implement an O(N log N) algorithm in BOSL2 and at least back when we tested
it, I think it appeared to help, with a crossover point of around 400
points. (Note that improvement from O(N^2) depends on the data being
non-uniform.)
On Sun, Oct 20, 2024 at 11:43 AM John David via Discuss <
discuss@lists.openscad.org> wrote:
What is the algorithmic order of what is implemented? Is O(log n)
actually required? The issue implied by Chun Kit's comment on ADT and
nested lists and lambdas is likely what is making the eval expensive (or in
alg analysis make the constant 'K' go through the roof).
My experience with running into issues like this is that there is rarely
a simple fix and you have to start a new version of a project with time
profiling unit-testing baked in. I'm not sure anyone has the time for that
(unless someone is taking this up as a student project, or getting paid).
On Sun, Oct 20, 2024 at 8:48 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
I think it is possible to have O(log n) priority queue for purely
functional languages. The problem is that you can't use lists for that, and
have to ADT as nested lists or lambdas. Not sure if openscad handles
sharing well.
On 20/10/2024 20:32, Adrian Mariano via Discuss wrote:
I think the openscad userspace computation issue is a little more
complicated. Certainly having faster execution would help, but there's
also the problem of efficient access to advanced data structures. My
recollection is that efficient algorithms for geometric processes tend to
require things like a priority queue, and it doesn't appear like this can
be implemented to run in the required O(log n) operation time.
Regarding warning levels, the discussion at
https://github.com/openscad/openscad/issues/5135 seems to suggest some
extra complications about this.
On Sun, Oct 20, 2024 at 1:27 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
There are two issues here:
- openscad userspace computation is slow.
- warning levels
For 1, there are ways to improve this situation, but it will take quite
a bit of effort and I don't have too much time to pull it off now.
Basically just make the interpretation using bytecode and skip all the
expensive hashtable lookup for each variable/function argument, as well as
AST traversal. It is not hard, but it is quite tedious to rewrite
everything and make sure the behavior is compatible.
For warning levels, IMO fixing non-manifold geometry is probably common
enough that it can be regarded as a debug level info.
On 19/10/2024 04:38, Adrian Mariano via Discuss wrote:
There is an OpenSCAD issue about this:
https://github.com/openscad/openscad/issues/5135. I thought they WERE
going to make that an informational message rather than a warning. I
raised the point that it's basically impossible to reasonably use OpenSCAD
without setting stop on first warning because it just causes an error to
cascade into pages of garbage and hide the true problem.
If OpenSCAD is going to be picky then BOSL2 has to run
vnf_merge_points() to look for the duplicate points and combine them in the
topology. You can do this now if you want to make it work. We don't do
this automatically because we are nervous that it will be slow, though for
the above rounded_prism example it's not terrible on my machine, boosting
preview time from 0.08s to 0.3 s, so a factor of three slower, but still
fast enough. However, if you round all the edges preview time goes from
0.7s to 5s which is getting annoying. (I did this tests with a large
splinesteps value, so it doesn't need to be quite so bad.) So run time can
be a potential concern at least sometimes. Almost every interesting shape
BOSL2 creates is going to have duplicate non-exact points, so longer term
it raises questions about basically complicating things throughout BOSL2 to
track edges, for example, to reduce the points that need to be checked for
merges. Maybe if they ever introduce structures outside of textmetrics
this will seem more reasonable to do. (Note that the rounded square prism
is constructed from 26 bezier patches, one for each face, edge and corner
and I don't see a reasonable way to actually track the faces that meet from
different patches at the same edge to directly exploit the knowledge that
the patches share a boundary.)
On Fri, Oct 18, 2024 at 4:01 PM Todd Allen via Discuss <
discuss@lists.openscad.org> wrote:
If I recall correctly, openscad should try the CGAL way of repairing
meshes when manifold cannot import
the mesh, no idea why it doesn't work in this case.
I reported this incorrectly as an error which stopped rendering. But
it is only a warning. However I had the option set to stop at first
warning. Disabling that option allows this to successfully render.
If this sort of mesh issue is expected to be commonly corrected by the
automatic repair process perhaps it would be ok to downgrade this message
from WARNING to INFO and only after the repair fails issue a warning or let
it error out.
On Fri, Oct 18, 2024 at 12:45 PM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
Are you saying that vertexes shared between faces must use the
same
indexes?
Both yes and no. If you mean vertices shared between triangles must
use
the same indices, yes. But you can have vertices with the same
coordinate, so they can have different indices and are not shared by
triangles, despite triangles containing them can be touching
geometrically (if you consider coordinates).
The topological definition of manifoldness used in manifold is
actually
very simple, see
https://github.com/elalish/manifold/wiki/Manifold-Library#manifoldness-definition
Every edge of every triangle must contain the same two vertices
(by
index) as exactly one other triangle edge, and the start and end
vertices must switch places between these two edges. The triangle
vertices must appear in counter-clockwise order when viewed from the
outside of the manifold.
I think the issue is in the polyhedron triangle list not being
manifold.
E.g. there may be a tiny open hole in the mesh, but merging vertices
close to each other may make the hole disappear because all vertices
around the hole are merged into one. If I recall correctly, openscad
should try the CGAL way of repairing meshes when manifold cannot
import
the mesh, no idea why it doesn't work in this case.
On 19/10/2024 01:24, Jordan Brown wrote:
On 10/18/2024 9:52 AM, Chun Kit LAM via Discuss wrote:
But manifold doesn't really care about coordinates when checking
for
manifoldness, it just cares about vertex indices in the list of
triangles. Previously, openscad would snap vertices to a grid and
merge identical vertices, but that can lose manifoldness in
general
and it is really hard to fix, so it is no longer doing that when
the
mesh PolySet can directly be imported into manifold.
Are you saying that vertexes shared between faces must use the same
indexes? Experiments indicate that there's no such requirement. I
constructed a cube out of 24 vertexes, and Manifold seemed
perfectly
happy with it. Correcting the 2e-16 values in the rounded prism to
zero, without eliminating the duplication, made the problem go away.
I'm not really a fan of the grid-snap scheme; it causes problems on
its own. Getting rid of it might be a win, but will likely cause
problems like this one. (But I admit I have no experience with
not
using it.) I'd like to think that we could have a scheme that
snapped
together "clusters" of points that are very close to one another
(say,
a difference of less than one part in 10^14), and gave up if a
cluster
ever spanned the limit. (That is, if point A is considered close
to
B, and B is considered close to C, but A is not close to C.) Such
a
scheme seems like it could have a very high accuracy rate, fixing
FP
precision problems without merging points that should be distinct.
But I suspect that it would also be quite expensive.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
Note that when I am talking about O(N^2) algorithms I mean implementations
in BOSL2, not implementations in core OpenSCAD. I actually implemented an
O(N^3) algorithm in one place (the skin function) because it works and is
useful on small cases. (But there is a warning in the docs that it's cubic
and to avoid large inputs.) The problem is that in userspace, these
quadratic algorithms appear to be the best that is possible.
On Sun, Oct 20, 2024 at 5:45 PM John David ebo.2112@gmail.com wrote:
No. I agree that O(N^2) is a problem (and explains why I have had trouble
from time to time with OpenSCAD). Now that I see how you are embedding the
"required" O(log N) within another and that this would already give you an
O(N log N).
BTW, I have only ever once recommended an algorithm that I knew to be
O(N^2) - that was part of a UI initialization where users could update a
command list. It was only ever run once (at boot), was guaranteed to be
limited to 6 to 10 commands at most, this was on a memory limited system,
and some part of the code depended on that list being sorted. A
bubble-sort is only ~6 lines of additional code, and if you add 2 more you
can guarantee that it will never be handed 1,000,000 strings. Even to
implement Qsort would have put a strain on their memory budget.
On Sun, Oct 20, 2024 at 12:07 PM Adrian Mariano via Discuss <
discuss@lists.openscad.org> wrote:
Right now, every polygon operation we have implemented in BOSL2 is
O(N^2), so if you feed it a polygon with 1000 points, which is not absurd,
you can expect a long wait due to quadratic run time. It's tough to know
for sure for the cases at hand whether we're dominated by asymptotic run
time or by a huge constant. That is, a million operations isn't that
many, so maybe if we were just 100x faster the O(N^2) would be fine for
practical cases with polygons. It's also a question of how many points
the polygon needs to have before O(N log N) would matter. As I recall,
advanced algorithms march around the polygon and enter things into a
priority queue and can find the intersections in O(N log N). I tried to
re-implement offset() to be more robust using a method that involves
polygon union/intersection type operations and run time for simple cases
was >1 minute. On inputs that I don't recall but probably had more like
100 points than 1000.
Note that to be clear, the point of a priority queue operation running in
O(log N) is that it means you can do O(N) of them and get O(N log N) so you
beat O(N^2).
For the problem of point merging for polyhedra, it's entirely possible to
have 50,000 points in a polyhedron, and having 1000 points is quite
modest. So how does O(N^2) look for that? You want to run O(N^2)
algorithms on things where N approaches 10^6? Now we have attempted to
implement an O(N log N) algorithm in BOSL2 and at least back when we tested
it, I think it appeared to help, with a crossover point of around 400
points. (Note that improvement from O(N^2) depends on the data being
non-uniform.)
On Sun, Oct 20, 2024 at 11:43 AM John David via Discuss <
discuss@lists.openscad.org> wrote:
What is the algorithmic order of what is implemented? Is O(log n)
actually required? The issue implied by Chun Kit's comment on ADT and
nested lists and lambdas is likely what is making the eval expensive (or in
alg analysis make the constant 'K' go through the roof).
My experience with running into issues like this is that there is rarely
a simple fix and you have to start a new version of a project with time
profiling unit-testing baked in. I'm not sure anyone has the time for that
(unless someone is taking this up as a student project, or getting paid).
On Sun, Oct 20, 2024 at 8:48 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
I think it is possible to have O(log n) priority queue for purely
functional languages. The problem is that you can't use lists for that, and
have to ADT as nested lists or lambdas. Not sure if openscad handles
sharing well.
On 20/10/2024 20:32, Adrian Mariano via Discuss wrote:
I think the openscad userspace computation issue is a little more
complicated. Certainly having faster execution would help, but there's
also the problem of efficient access to advanced data structures. My
recollection is that efficient algorithms for geometric processes tend to
require things like a priority queue, and it doesn't appear like this can
be implemented to run in the required O(log n) operation time.
Regarding warning levels, the discussion at
https://github.com/openscad/openscad/issues/5135 seems to suggest some
extra complications about this.
On Sun, Oct 20, 2024 at 1:27 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
There are two issues here:
- openscad userspace computation is slow.
- warning levels
For 1, there are ways to improve this situation, but it will take
quite a bit of effort and I don't have too much time to pull it off now.
Basically just make the interpretation using bytecode and skip all the
expensive hashtable lookup for each variable/function argument, as well as
AST traversal. It is not hard, but it is quite tedious to rewrite
everything and make sure the behavior is compatible.
For warning levels, IMO fixing non-manifold geometry is probably
common enough that it can be regarded as a debug level info.
On 19/10/2024 04:38, Adrian Mariano via Discuss wrote:
There is an OpenSCAD issue about this:
https://github.com/openscad/openscad/issues/5135. I thought they
WERE going to make that an informational message rather than a warning. I
raised the point that it's basically impossible to reasonably use OpenSCAD
without setting stop on first warning because it just causes an error to
cascade into pages of garbage and hide the true problem.
If OpenSCAD is going to be picky then BOSL2 has to run
vnf_merge_points() to look for the duplicate points and combine them in the
topology. You can do this now if you want to make it work. We don't do
this automatically because we are nervous that it will be slow, though for
the above rounded_prism example it's not terrible on my machine, boosting
preview time from 0.08s to 0.3 s, so a factor of three slower, but still
fast enough. However, if you round all the edges preview time goes from
0.7s to 5s which is getting annoying. (I did this tests with a large
splinesteps value, so it doesn't need to be quite so bad.) So run time can
be a potential concern at least sometimes. Almost every interesting shape
BOSL2 creates is going to have duplicate non-exact points, so longer term
it raises questions about basically complicating things throughout BOSL2 to
track edges, for example, to reduce the points that need to be checked for
merges. Maybe if they ever introduce structures outside of textmetrics
this will seem more reasonable to do. (Note that the rounded square prism
is constructed from 26 bezier patches, one for each face, edge and corner
and I don't see a reasonable way to actually track the faces that meet from
different patches at the same edge to directly exploit the knowledge that
the patches share a boundary.)
On Fri, Oct 18, 2024 at 4:01 PM Todd Allen via Discuss <
discuss@lists.openscad.org> wrote:
If I recall correctly, openscad should try the CGAL way of
repairing meshes when manifold cannot import
the mesh, no idea why it doesn't work in this case.
I reported this incorrectly as an error which stopped rendering. But
it is only a warning. However I had the option set to stop at first
warning. Disabling that option allows this to successfully render.
If this sort of mesh issue is expected to be commonly corrected by
the automatic repair process perhaps it would be ok to downgrade this
message from WARNING to INFO and only after the repair fails issue a
warning or let it error out.
On Fri, Oct 18, 2024 at 12:45 PM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
Are you saying that vertexes shared between faces must use the
same
indexes?
Both yes and no. If you mean vertices shared between triangles must
use
the same indices, yes. But you can have vertices with the same
coordinate, so they can have different indices and are not shared by
triangles, despite triangles containing them can be touching
geometrically (if you consider coordinates).
The topological definition of manifoldness used in manifold is
actually
very simple, see
https://github.com/elalish/manifold/wiki/Manifold-Library#manifoldness-definition
Every edge of every triangle must contain the same two vertices
(by
index) as exactly one other triangle edge, and the start and end
vertices must switch places between these two edges. The triangle
vertices must appear in counter-clockwise order when viewed from the
outside of the manifold.
I think the issue is in the polyhedron triangle list not being
manifold.
E.g. there may be a tiny open hole in the mesh, but merging vertices
close to each other may make the hole disappear because all vertices
around the hole are merged into one. If I recall correctly, openscad
should try the CGAL way of repairing meshes when manifold cannot
import
the mesh, no idea why it doesn't work in this case.
On 19/10/2024 01:24, Jordan Brown wrote:
On 10/18/2024 9:52 AM, Chun Kit LAM via Discuss wrote:
But manifold doesn't really care about coordinates when checking
for
manifoldness, it just cares about vertex indices in the list of
triangles. Previously, openscad would snap vertices to a grid and
merge identical vertices, but that can lose manifoldness in
general
and it is really hard to fix, so it is no longer doing that when
the
mesh PolySet can directly be imported into manifold.
Are you saying that vertexes shared between faces must use the
same
indexes? Experiments indicate that there's no such requirement.
I
constructed a cube out of 24 vertexes, and Manifold seemed
perfectly
happy with it. Correcting the 2e-16 values in the rounded prism
to
zero, without eliminating the duplication, made the problem go
away.
I'm not really a fan of the grid-snap scheme; it causes problems
on
its own. Getting rid of it might be a win, but will likely cause
problems like this one. (But I admit I have no experience with
not
using it.) I'd like to think that we could have a scheme that
snapped
together "clusters" of points that are very close to one another
(say,
a difference of less than one part in 10^14), and gave up if a
cluster
ever spanned the limit. (That is, if point A is considered close
to
B, and B is considered close to C, but A is not close to C.) Such
a
scheme seems like it could have a very high accuracy rate, fixing
FP
precision problems without merging points that should be
distinct.
But I suspect that it would also be quite expensive.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
Thanks for the info, Adrian. When it is in a core library, in the OpenSCAD
core routines, it makes sense to track these down and see if there is a
more efficient solution. It is also important to realize that efficient
algorithms are notoriously difficult to implement. I know people who have
gotten their MS and PhD's doing just that. That said, it is still worth a
look to see if there are better algorithms or tricks to speed things up.
Thanks again.
On Sun, Oct 20, 2024 at 11:26 PM Adrian Mariano avm4@cornell.edu wrote:
Note that when I am talking about O(N^2) algorithms I mean implementations
in BOSL2, not implementations in core OpenSCAD. I actually implemented an
O(N^3) algorithm in one place (the skin function) because it works and is
useful on small cases. (But there is a warning in the docs that it's cubic
and to avoid large inputs.) The problem is that in userspace, these
quadratic algorithms appear to be the best that is possible.
On Sun, Oct 20, 2024 at 5:45 PM John David ebo.2112@gmail.com wrote:
No. I agree that O(N^2) is a problem (and explains why I have had
trouble from time to time with OpenSCAD). Now that I see how you are
embedding the "required" O(log N) within another and that this would
already give you an O(N log N).
BTW, I have only ever once recommended an algorithm that I knew to be
O(N^2) - that was part of a UI initialization where users could update a
command list. It was only ever run once (at boot), was guaranteed to be
limited to 6 to 10 commands at most, this was on a memory limited system,
and some part of the code depended on that list being sorted. A
bubble-sort is only ~6 lines of additional code, and if you add 2 more you
can guarantee that it will never be handed 1,000,000 strings. Even to
implement Qsort would have put a strain on their memory budget.
On Sun, Oct 20, 2024 at 12:07 PM Adrian Mariano via Discuss <
discuss@lists.openscad.org> wrote:
Right now, every polygon operation we have implemented in BOSL2 is
O(N^2), so if you feed it a polygon with 1000 points, which is not absurd,
you can expect a long wait due to quadratic run time. It's tough to know
for sure for the cases at hand whether we're dominated by asymptotic run
time or by a huge constant. That is, a million operations isn't that
many, so maybe if we were just 100x faster the O(N^2) would be fine for
practical cases with polygons. It's also a question of how many points
the polygon needs to have before O(N log N) would matter. As I recall,
advanced algorithms march around the polygon and enter things into a
priority queue and can find the intersections in O(N log N). I tried to
re-implement offset() to be more robust using a method that involves
polygon union/intersection type operations and run time for simple cases
was >1 minute. On inputs that I don't recall but probably had more like
100 points than 1000.
Note that to be clear, the point of a priority queue operation running
in O(log N) is that it means you can do O(N) of them and get O(N log N) so
you beat O(N^2).
For the problem of point merging for polyhedra, it's entirely possible
to have 50,000 points in a polyhedron, and having 1000 points is quite
modest. So how does O(N^2) look for that? You want to run O(N^2)
algorithms on things where N approaches 10^6? Now we have attempted to
implement an O(N log N) algorithm in BOSL2 and at least back when we tested
it, I think it appeared to help, with a crossover point of around 400
points. (Note that improvement from O(N^2) depends on the data being
non-uniform.)
On Sun, Oct 20, 2024 at 11:43 AM John David via Discuss <
discuss@lists.openscad.org> wrote:
What is the algorithmic order of what is implemented? Is O(log n)
actually required? The issue implied by Chun Kit's comment on ADT and
nested lists and lambdas is likely what is making the eval expensive (or in
alg analysis make the constant 'K' go through the roof).
My experience with running into issues like this is that there is
rarely a simple fix and you have to start a new version of a project with
time profiling unit-testing baked in. I'm not sure anyone has the time for
that (unless someone is taking this up as a student project, or getting
paid).
On Sun, Oct 20, 2024 at 8:48 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
I think it is possible to have O(log n) priority queue for purely
functional languages. The problem is that you can't use lists for that, and
have to ADT as nested lists or lambdas. Not sure if openscad handles
sharing well.
On 20/10/2024 20:32, Adrian Mariano via Discuss wrote:
I think the openscad userspace computation issue is a little more
complicated. Certainly having faster execution would help, but there's
also the problem of efficient access to advanced data structures. My
recollection is that efficient algorithms for geometric processes tend to
require things like a priority queue, and it doesn't appear like this can
be implemented to run in the required O(log n) operation time.
Regarding warning levels, the discussion at
https://github.com/openscad/openscad/issues/5135 seems to suggest
some extra complications about this.
On Sun, Oct 20, 2024 at 1:27 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
There are two issues here:
- openscad userspace computation is slow.
- warning levels
For 1, there are ways to improve this situation, but it will take
quite a bit of effort and I don't have too much time to pull it off now.
Basically just make the interpretation using bytecode and skip all the
expensive hashtable lookup for each variable/function argument, as well as
AST traversal. It is not hard, but it is quite tedious to rewrite
everything and make sure the behavior is compatible.
For warning levels, IMO fixing non-manifold geometry is probably
common enough that it can be regarded as a debug level info.
On 19/10/2024 04:38, Adrian Mariano via Discuss wrote:
There is an OpenSCAD issue about this:
https://github.com/openscad/openscad/issues/5135. I thought they
WERE going to make that an informational message rather than a warning. I
raised the point that it's basically impossible to reasonably use OpenSCAD
without setting stop on first warning because it just causes an error to
cascade into pages of garbage and hide the true problem.
If OpenSCAD is going to be picky then BOSL2 has to run
vnf_merge_points() to look for the duplicate points and combine them in the
topology. You can do this now if you want to make it work. We don't do
this automatically because we are nervous that it will be slow, though for
the above rounded_prism example it's not terrible on my machine, boosting
preview time from 0.08s to 0.3 s, so a factor of three slower, but still
fast enough. However, if you round all the edges preview time goes from
0.7s to 5s which is getting annoying. (I did this tests with a large
splinesteps value, so it doesn't need to be quite so bad.) So run time can
be a potential concern at least sometimes. Almost every interesting shape
BOSL2 creates is going to have duplicate non-exact points, so longer term
it raises questions about basically complicating things throughout BOSL2 to
track edges, for example, to reduce the points that need to be checked for
merges. Maybe if they ever introduce structures outside of textmetrics
this will seem more reasonable to do. (Note that the rounded square prism
is constructed from 26 bezier patches, one for each face, edge and corner
and I don't see a reasonable way to actually track the faces that meet from
different patches at the same edge to directly exploit the knowledge that
the patches share a boundary.)
On Fri, Oct 18, 2024 at 4:01 PM Todd Allen via Discuss <
discuss@lists.openscad.org> wrote:
If I recall correctly, openscad should try the CGAL way of
repairing meshes when manifold cannot import
the mesh, no idea why it doesn't work in this case.
I reported this incorrectly as an error which stopped rendering.
But it is only a warning. However I had the option set to stop at first
warning. Disabling that option allows this to successfully render.
If this sort of mesh issue is expected to be commonly corrected by
the automatic repair process perhaps it would be ok to downgrade this
message from WARNING to INFO and only after the repair fails issue a
warning or let it error out.
On Fri, Oct 18, 2024 at 12:45 PM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
Are you saying that vertexes shared between faces must use the
same
indexes?
Both yes and no. If you mean vertices shared between triangles must
use
the same indices, yes. But you can have vertices with the same
coordinate, so they can have different indices and are not shared
by
triangles, despite triangles containing them can be touching
geometrically (if you consider coordinates).
The topological definition of manifoldness used in manifold is
actually
very simple, see
https://github.com/elalish/manifold/wiki/Manifold-Library#manifoldness-definition
Every edge of every triangle must contain the same two vertices
(by
index) as exactly one other triangle edge, and the start and end
vertices must switch places between these two edges. The triangle
vertices must appear in counter-clockwise order when viewed from
the
outside of the manifold.
I think the issue is in the polyhedron triangle list not being
manifold.
E.g. there may be a tiny open hole in the mesh, but merging
vertices
close to each other may make the hole disappear because all
vertices
around the hole are merged into one. If I recall correctly,
openscad
should try the CGAL way of repairing meshes when manifold cannot
import
the mesh, no idea why it doesn't work in this case.
On 19/10/2024 01:24, Jordan Brown wrote:
On 10/18/2024 9:52 AM, Chun Kit LAM via Discuss wrote:
But manifold doesn't really care about coordinates when checking
for
manifoldness, it just cares about vertex indices in the list of
triangles. Previously, openscad would snap vertices to a grid
and
merge identical vertices, but that can lose manifoldness in
general
and it is really hard to fix, so it is no longer doing that when
the
mesh PolySet can directly be imported into manifold.
Are you saying that vertexes shared between faces must use the
same
indexes? Experiments indicate that there's no such requirement.
I
constructed a cube out of 24 vertexes, and Manifold seemed
perfectly
happy with it. Correcting the 2e-16 values in the rounded prism
to
zero, without eliminating the duplication, made the problem go
away.
I'm not really a fan of the grid-snap scheme; it causes problems
on
its own. Getting rid of it might be a win, but will likely cause
problems like this one. (But I admit I have no experience with
not
using it.) I'd like to think that we could have a scheme that
snapped
together "clusters" of points that are very close to one another
(say,
a difference of less than one part in 10^14), and gave up if a
cluster
ever spanned the limit. (That is, if point A is considered close
to
B, and B is considered close to C, but A is not close to C.)
Such a
scheme seems like it could have a very high accuracy rate, fixing
FP
precision problems without merging points that should be
distinct.
But I suspect that it would also be quite expensive.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
In general, writing code in a functional style while making sure it is
fast is a hard problem, especially when the runtime is not well
optimized. Even when the complexity matches the imperative version, the
hidden constant is likely to be much greater here. There are academic
works on optimizing functional programming languages to match the
performance of imperative languages by optimizing some code into
in-place modification, but those are non-trivial to say the least.
Rendering was too slow, so most optimization effort went into rendering.
Now that rendering is sufficiently fast for the majority of cases, more
effort can be directed towards optimizing the evaluator and minkowski/3D
offset operations, which are not yet solved.
On 21/10/2024 14:08, John David via Discuss wrote:
Thanks for the info, Adrian. When it is in a core library, in the
OpenSCAD core routines, it makes sense to track these down and see if
there is a more efficient solution. It is also important to realize
that efficient algorithms are notoriously difficult to implement. I
know people who have gotten their MS and PhD's doing just that. That
said, it is still worth a look to see if there are better algorithms
or tricks to speed things up. Thanks again.
On Sun, Oct 20, 2024 at 11:26 PM Adrian Mariano avm4@cornell.edu wrote:
Note that when I am talking about O(N^2) algorithms I mean
implementations in BOSL2, not implementations in core OpenSCAD.
I actually implemented an O(N^3) algorithm in one place (the skin
function) because it works and is useful on small cases. (But
there is a warning in the docs that it's cubic and to avoid large
inputs.) The problem is that in userspace, these quadratic
algorithms appear to be the best that is possible.
On Sun, Oct 20, 2024 at 5:45 PM John David <ebo.2112@gmail.com> wrote:
No. I agree that O(N^2) is a problem (and explains why I have
had trouble from time to time with OpenSCAD). Now that I see
how you are embedding the "required" O(log N) within another
and that this would already give you an O(N log N).
BTW, I have only ever once recommended an algorithm that I
knew to be O(N^2) - that was part of a UI initialization where
users could update a command list. It was only ever run once
(at boot), was guaranteed to be limited to 6 to 10 commands at
most, this was on a memory limited system, and some part of
the code depended on that list being sorted. A bubble-sort is
only ~6 lines of additional code, and if you add 2 more you
can guarantee that it will never be handed 1,000,000 strings.
Even to implement Qsort would have put a strain on their
memory budget.
On Sun, Oct 20, 2024 at 12:07 PM Adrian Mariano via Discuss
<discuss@lists.openscad.org> wrote:
Right now, every polygon operation we have implemented in
BOSL2 is O(N^2), so if you feed it a polygon with 1000
points, which is not absurd, you can expect a long wait
due to quadratic run time. It's tough to know for sure
for the cases at hand whether we're dominated by
asymptotic run time or by a huge constant. That is, a
million operations isn't that many, so maybe if we were
just 100x faster the O(N^2) would be fine for practical
cases with polygons. It's also a question of how many
points the polygon needs to have before O(N log N) would
matter. As I recall, advanced algorithms march around
the polygon and enter things into a priority queue and can
find the intersections in O(N log N). I tried to
re-implement offset() to be more robust using a method
that involves polygon union/intersection type operations
and run time for simple cases was >1 minute. On inputs
that I don't recall but probably had more like 100 points
than 1000.
Note that to be clear, the point of a priority queue
operation running in O(log N) is that it means you can do
O(N) of them and get O(N log N) so you beat O(N^2).
For the problem of point merging for polyhedra, it's
entirely possible to have 50,000 points in a polyhedron,
and having 1000 points is quite modest. So how does
O(N^2) look for that? You want to run O(N^2) algorithms
on things where N approaches 10^6? Now we have attempted
to implement an O(N log N) algorithm in BOSL2 and at least
back when we tested it, I think it appeared to help, with
a crossover point of around 400 points. (Note that
improvement from O(N^2) depends on the data being
non-uniform.)
On Sun, Oct 20, 2024 at 11:43 AM John David via Discuss
<discuss@lists.openscad.org> wrote:
What is the algorithmic order of what is implemented?
Is O(log n) actually required? The issue implied by
Chun Kit's comment on ADT and nested lists and lambdas
is likely what is making the eval expensive (or in alg
analysis make the constant 'K' go through the roof).
My experience with running into issues like this is
that there is rarely a simple fix and you have to
start a new version of a project with time profiling
unit-testing baked in. I'm not sure anyone has the
time for that (unless someone is taking this up as a
student project, or getting paid).
On Sun, Oct 20, 2024 at 8:48 AM Chun Kit LAM via
Discuss <discuss@lists.openscad.org> wrote:
I think it is possible to have O(log n) priority
queue for purely functional languages. The problem
is that you can't use lists for that, and have to
ADT as nested lists or lambdas. Not sure if
openscad handles sharing well.
On 20/10/2024 20:32, Adrian Mariano via Discuss wrote:
I think the openscad userspace computation issue
is a little more complicated. Certainly having
faster execution would help, but there's also the
problem of efficient access to advanced data
structures. My recollection is that efficient
algorithms for geometric processes tend to
require things like a priority queue, and it
doesn't appear like this can be implemented to
run in the required O(log n) operation time.
Regarding warning levels, the discussion at
https://github.com/openscad/openscad/issues/5135
seems to suggest some extra complications about
this.
On Sun, Oct 20, 2024 at 1:27 AM Chun Kit LAM via
Discuss <discuss@lists.openscad.org> wrote:
There are two issues here:
1. openscad userspace computation is slow.
2. warning levels
For 1, there are ways to improve this
situation, but it will take quite a bit of
effort and I don't have too much time to pull
it off now. Basically just make the
interpretation using bytecode and skip all
the expensive hashtable lookup for each
variable/function argument, as well as AST
traversal. It is not hard, but it is quite
tedious to rewrite everything and make sure
the behavior is compatible.
For warning levels, IMO fixing non-manifold
geometry is probably common enough that it
can be regarded as a debug level info.
On 19/10/2024 04:38, Adrian Mariano via
Discuss wrote:
There is an OpenSCAD issue about this:
https://github.com/openscad/openscad/issues/5135.
I thought they WERE going to make that an
informational message rather than a
warning. I raised the point that it's
basically impossible to reasonably use
OpenSCAD without setting stop on first
warning because it just causes an error to
cascade into pages of garbage and hide the
true problem.
If OpenSCAD is going to be picky then BOSL2
has to run vnf_merge_points() to look for
the duplicate points and combine them in the
topology. You can do this now if you want
to make it work. We don't do this
automatically because we are nervous that it
will be slow, though for the above
rounded_prism example it's not terrible on
my machine, boosting preview time from 0.08s
to 0.3 s, so a factor of three slower, but
still fast enough. However, if you round
all the edges preview time goes from 0.7s to
5s which is getting annoying. (I did this
tests with a large splinesteps value, so it
doesn't need to be quite so bad.) So run
time can be a potential concern at least
sometimes. Almost every interesting shape
BOSL2 creates is going to have duplicate
non-exact points, so longer term it raises
questions about basically complicating
things throughout BOSL2 to track edges, for
example, to reduce the points that need to
be checked for merges. Maybe if they ever
introduce structures outside of textmetrics
this will seem more reasonable to do.
(Note that the rounded square prism is
constructed from 26 bezier patches, one for
each face, edge and corner and I don't see a
reasonable way to actually track the faces
that meet from different patches at the same
edge to directly exploit the knowledge that
the patches share a boundary.)
On Fri, Oct 18, 2024 at 4:01 PM Todd Allen
via Discuss <discuss@lists.openscad.org> wrote:
If I recall correctly, openscad should
try the CGAL way of repairing meshes
when manifold cannot import
the mesh, no idea why it doesn't work in
this case.
I reported this incorrectly as an error
which stopped rendering. But it is only
a warning. However I had the option set
to stop at first warning. Disabling
that option allows this to successfully
render.
If this sort of mesh issue is expected
to be commonly corrected by the
automatic repair process perhaps it
would be ok to downgrade this message
from WARNING to INFO and only after the
repair fails issue a warning or let it
error out.
On Fri, Oct 18, 2024 at 12:45 PM Chun
Kit LAM via Discuss
<discuss@lists.openscad.org> wrote:
> Are you saying that vertexes
shared between faces must use the same
indexes?
Both yes and no. If you mean
vertices shared between triangles
must use
the same indices, yes. But you can
have vertices with the same
coordinate, so they can have
different indices and are not shared by
triangles, despite triangles
containing them can be touching
geometrically (if you consider
coordinates).
The topological definition of
manifoldness used in manifold is
actually
very simple, see
https://github.com/elalish/manifold/wiki/Manifold-Library#manifoldness-definition
> Every edge of every triangle must
contain the same two vertices (by
index) as exactly one other triangle
edge, and the start and end
vertices must switch places between
these two edges. The triangle
vertices must appear in
counter-clockwise order when viewed
from the
outside of the manifold.
I think the issue is in the
polyhedron triangle list not being
manifold.
E.g. there may be a tiny open hole
in the mesh, but merging vertices
close to each other may make the
hole disappear because all vertices
around the hole are merged into one.
If I recall correctly, openscad
should try the CGAL way of repairing
meshes when manifold cannot import
the mesh, no idea why it doesn't
work in this case.
On 19/10/2024 01:24, Jordan Brown wrote:
On 10/18/2024 9:52 AM, Chun Kit
LAM via Discuss wrote:
But manifold doesn't really care
about coordinates when checking for
manifoldness, it just cares about
vertex indices in the list of
triangles. Previously, openscad
would snap vertices to a grid and
merge identical vertices, but
that can lose manifoldness in general
and it is really hard to fix, so
it is no longer doing that when the
mesh PolySet can directly be
imported into manifold.
Are you saying that vertexes
shared between faces must use the same
indexes? Experiments indicate
that there's no such requirement. I
constructed a cube out of 24
vertexes, and Manifold seemed perfectly
happy with it. Correcting the
2e-16 values in the rounded prism to
zero, without eliminating the
duplication, made the problem go away.
I'm not really a fan of the
grid-snap scheme; it causes problems on
its own. Getting rid of it might
be a win, but will likely cause
problems like this one. (But I
admit I have no experience with *not*
using it.) I'd like to think that
we could have a scheme that snapped
together "clusters" of points that
are very close to one another (say,
a difference of less than one part
in 10^14), and gave up if a cluster
ever spanned the limit. (That is,
if point A is considered close to
B, and B is considered close to C,
but A is not close to C.) Such a
scheme seems like it could have a
very high accuracy rate, fixing FP
precision problems without merging
points that should be distinct.
But I suspect that it would also
be quite expensive.
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to
discuss-leave@lists.openscad.org
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to
discuss-leave@lists.openscad.org
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email todiscuss-leave@lists.openscad.org
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to
discuss-leave@lists.openscad.org
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email todiscuss-leave@lists.openscad.org
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to
discuss-leave@lists.openscad.org
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to
discuss-leave@lists.openscad.org
_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to
discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email todiscuss-leave@lists.openscad.org
Yes, I realize just how hard this can be after having to "operationalize"
other people's experimental code into working systems. I've even worked on
projects that every time I punch the button it could cost as much as
150,000 CPU hours to fully process the data set, and there I had to sweat
niggly bits of time spent. Both those sections should provide fruitful
efficiency updates. Best of luck to all.
On Mon, Oct 21, 2024 at 2:23 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
In general, writing code in a functional style while making sure it is
fast is a hard problem, especially when the runtime is not well optimized.
Even when the complexity matches the imperative version, the hidden
constant is likely to be much greater here. There are academic works on
optimizing functional programming languages to match the performance of
imperative languages by optimizing some code into in-place modification,
but those are non-trivial to say the least.
Rendering was too slow, so most optimization effort went into rendering.
Now that rendering is sufficiently fast for the majority of cases, more
effort can be directed towards optimizing the evaluator and minkowski/3D
offset operations, which are not yet solved.
On 21/10/2024 14:08, John David via Discuss wrote:
Thanks for the info, Adrian. When it is in a core library, in the OpenSCAD
core routines, it makes sense to track these down and see if there is a
more efficient solution. It is also important to realize that efficient
algorithms are notoriously difficult to implement. I know people who have
gotten their MS and PhD's doing just that. That said, it is still worth a
look to see if there are better algorithms or tricks to speed things up.
Thanks again.
On Sun, Oct 20, 2024 at 11:26 PM Adrian Mariano avm4@cornell.edu wrote:
Note that when I am talking about O(N^2) algorithms I mean
implementations in BOSL2, not implementations in core OpenSCAD. I
actually implemented an O(N^3) algorithm in one place (the skin function)
because it works and is useful on small cases. (But there is a warning in
the docs that it's cubic and to avoid large inputs.) The problem is that
in userspace, these quadratic algorithms appear to be the best that is
possible.
On Sun, Oct 20, 2024 at 5:45 PM John David ebo.2112@gmail.com wrote:
No. I agree that O(N^2) is a problem (and explains why I have had
trouble from time to time with OpenSCAD). Now that I see how you are
embedding the "required" O(log N) within another and that this would
already give you an O(N log N).
BTW, I have only ever once recommended an algorithm that I knew to be
O(N^2) - that was part of a UI initialization where users could update a
command list. It was only ever run once (at boot), was guaranteed to be
limited to 6 to 10 commands at most, this was on a memory limited system,
and some part of the code depended on that list being sorted. A
bubble-sort is only ~6 lines of additional code, and if you add 2 more you
can guarantee that it will never be handed 1,000,000 strings. Even to
implement Qsort would have put a strain on their memory budget.
On Sun, Oct 20, 2024 at 12:07 PM Adrian Mariano via Discuss <
discuss@lists.openscad.org> wrote:
Right now, every polygon operation we have implemented in BOSL2 is
O(N^2), so if you feed it a polygon with 1000 points, which is not absurd,
you can expect a long wait due to quadratic run time. It's tough to know
for sure for the cases at hand whether we're dominated by asymptotic run
time or by a huge constant. That is, a million operations isn't that
many, so maybe if we were just 100x faster the O(N^2) would be fine for
practical cases with polygons. It's also a question of how many points
the polygon needs to have before O(N log N) would matter. As I recall,
advanced algorithms march around the polygon and enter things into a
priority queue and can find the intersections in O(N log N). I tried to
re-implement offset() to be more robust using a method that involves
polygon union/intersection type operations and run time for simple cases
was >1 minute. On inputs that I don't recall but probably had more like
100 points than 1000.
Note that to be clear, the point of a priority queue operation running
in O(log N) is that it means you can do O(N) of them and get O(N log N) so
you beat O(N^2).
For the problem of point merging for polyhedra, it's entirely possible
to have 50,000 points in a polyhedron, and having 1000 points is quite
modest. So how does O(N^2) look for that? You want to run O(N^2)
algorithms on things where N approaches 10^6? Now we have attempted to
implement an O(N log N) algorithm in BOSL2 and at least back when we tested
it, I think it appeared to help, with a crossover point of around 400
points. (Note that improvement from O(N^2) depends on the data being
non-uniform.)
On Sun, Oct 20, 2024 at 11:43 AM John David via Discuss <
discuss@lists.openscad.org> wrote:
What is the algorithmic order of what is implemented? Is O(log n)
actually required? The issue implied by Chun Kit's comment on ADT and
nested lists and lambdas is likely what is making the eval expensive (or in
alg analysis make the constant 'K' go through the roof).
My experience with running into issues like this is that there is
rarely a simple fix and you have to start a new version of a project with
time profiling unit-testing baked in. I'm not sure anyone has the time for
that (unless someone is taking this up as a student project, or getting
paid).
On Sun, Oct 20, 2024 at 8:48 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
I think it is possible to have O(log n) priority queue for purely
functional languages. The problem is that you can't use lists for that, and
have to ADT as nested lists or lambdas. Not sure if openscad handles
sharing well.
On 20/10/2024 20:32, Adrian Mariano via Discuss wrote:
I think the openscad userspace computation issue is a little more
complicated. Certainly having faster execution would help, but there's
also the problem of efficient access to advanced data structures. My
recollection is that efficient algorithms for geometric processes tend to
require things like a priority queue, and it doesn't appear like this can
be implemented to run in the required O(log n) operation time.
Regarding warning levels, the discussion at
https://github.com/openscad/openscad/issues/5135 seems to suggest
some extra complications about this.
On Sun, Oct 20, 2024 at 1:27 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
There are two issues here:
- openscad userspace computation is slow.
- warning levels
For 1, there are ways to improve this situation, but it will take
quite a bit of effort and I don't have too much time to pull it off now.
Basically just make the interpretation using bytecode and skip all the
expensive hashtable lookup for each variable/function argument, as well as
AST traversal. It is not hard, but it is quite tedious to rewrite
everything and make sure the behavior is compatible.
For warning levels, IMO fixing non-manifold geometry is probably
common enough that it can be regarded as a debug level info.
On 19/10/2024 04:38, Adrian Mariano via Discuss wrote:
There is an OpenSCAD issue about this:
https://github.com/openscad/openscad/issues/5135. I thought they
WERE going to make that an informational message rather than a warning. I
raised the point that it's basically impossible to reasonably use OpenSCAD
without setting stop on first warning because it just causes an error to
cascade into pages of garbage and hide the true problem.
If OpenSCAD is going to be picky then BOSL2 has to run
vnf_merge_points() to look for the duplicate points and combine them in the
topology. You can do this now if you want to make it work. We don't do
this automatically because we are nervous that it will be slow, though for
the above rounded_prism example it's not terrible on my machine, boosting
preview time from 0.08s to 0.3 s, so a factor of three slower, but still
fast enough. However, if you round all the edges preview time goes from
0.7s to 5s which is getting annoying. (I did this tests with a large
splinesteps value, so it doesn't need to be quite so bad.) So run time can
be a potential concern at least sometimes. Almost every interesting shape
BOSL2 creates is going to have duplicate non-exact points, so longer term
it raises questions about basically complicating things throughout BOSL2 to
track edges, for example, to reduce the points that need to be checked for
merges. Maybe if they ever introduce structures outside of textmetrics
this will seem more reasonable to do. (Note that the rounded square prism
is constructed from 26 bezier patches, one for each face, edge and corner
and I don't see a reasonable way to actually track the faces that meet from
different patches at the same edge to directly exploit the knowledge that
the patches share a boundary.)
On Fri, Oct 18, 2024 at 4:01 PM Todd Allen via Discuss <
discuss@lists.openscad.org> wrote:
If I recall correctly, openscad should try the CGAL way of
repairing meshes when manifold cannot import
the mesh, no idea why it doesn't work in this case.
I reported this incorrectly as an error which stopped rendering.
But it is only a warning. However I had the option set to stop at first
warning. Disabling that option allows this to successfully render.
If this sort of mesh issue is expected to be commonly corrected by
the automatic repair process perhaps it would be ok to downgrade this
message from WARNING to INFO and only after the repair fails issue a
warning or let it error out.
On Fri, Oct 18, 2024 at 12:45 PM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
Are you saying that vertexes shared between faces must use the
same
indexes?
Both yes and no. If you mean vertices shared between triangles
must use
the same indices, yes. But you can have vertices with the same
coordinate, so they can have different indices and are not shared
by
triangles, despite triangles containing them can be touching
geometrically (if you consider coordinates).
The topological definition of manifoldness used in manifold is
actually
very simple, see
https://github.com/elalish/manifold/wiki/Manifold-Library#manifoldness-definition
Every edge of every triangle must contain the same two vertices
(by
index) as exactly one other triangle edge, and the start and end
vertices must switch places between these two edges. The triangle
vertices must appear in counter-clockwise order when viewed from
the
outside of the manifold.
I think the issue is in the polyhedron triangle list not being
manifold.
E.g. there may be a tiny open hole in the mesh, but merging
vertices
close to each other may make the hole disappear because all
vertices
around the hole are merged into one. If I recall correctly,
openscad
should try the CGAL way of repairing meshes when manifold cannot
import
the mesh, no idea why it doesn't work in this case.
On 19/10/2024 01:24, Jordan Brown wrote:
On 10/18/2024 9:52 AM, Chun Kit LAM via Discuss wrote:
But manifold doesn't really care about coordinates when
checking for
manifoldness, it just cares about vertex indices in the list of
triangles. Previously, openscad would snap vertices to a grid
and
merge identical vertices, but that can lose manifoldness in
general
and it is really hard to fix, so it is no longer doing that
when the
mesh PolySet can directly be imported into manifold.
Are you saying that vertexes shared between faces must use the
same
indexes? Experiments indicate that there's no such
requirement. I
constructed a cube out of 24 vertexes, and Manifold seemed
perfectly
happy with it. Correcting the 2e-16 values in the rounded prism
to
zero, without eliminating the duplication, made the problem go
away.
I'm not really a fan of the grid-snap scheme; it causes problems
on
its own. Getting rid of it might be a win, but will likely
cause
problems like this one. (But I admit I have no experience with
not
using it.) I'd like to think that we could have a scheme that
snapped
together "clusters" of points that are very close to one another
(say,
a difference of less than one part in 10^14), and gave up if a
cluster
ever spanned the limit. (That is, if point A is considered
close to
B, and B is considered close to C, but A is not close to C.)
Such a
scheme seems like it could have a very high accuracy rate,
fixing FP
precision problems without merging points that should be
distinct.
But I suspect that it would also be quite expensive.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
Absolutely agree. The trick is knowing when and how much time should be
spent on optimization. As a note, QSort was not available to him at that
point in the boot cycle, and he was looking at implementing some sort of
sorting routine.
As a note, I would modify one bit you said in that depending on the
language I am programming in, I actually do some optimization on
compile/build operations. When writing in C/C++/Fortran (and other
compiled languages) I tend to write lots of unit-testing code (I'm an XP
fan). So I probably run the compiler many times an hour, and waiting 10
minutes for some configuration build personally drives me nuts (unless I
have no choice).
On Mon, Oct 21, 2024 at 12:18 PM John David ebo.2112@gmail.com wrote:
Yes, I realize just how hard this can be after having to "operationalize"
other people's experimental code into working systems. I've even worked on
projects that every time I punch the button it could cost as much as
150,000 CPU hours to fully process the data set, and there I had to sweat
niggly bits of time spent. Both those sections should provide fruitful
efficiency updates. Best of luck to all.
On Mon, Oct 21, 2024 at 2:23 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
In general, writing code in a functional style while making sure it is
fast is a hard problem, especially when the runtime is not well optimized.
Even when the complexity matches the imperative version, the hidden
constant is likely to be much greater here. There are academic works on
optimizing functional programming languages to match the performance of
imperative languages by optimizing some code into in-place modification,
but those are non-trivial to say the least.
Rendering was too slow, so most optimization effort went into rendering.
Now that rendering is sufficiently fast for the majority of cases, more
effort can be directed towards optimizing the evaluator and minkowski/3D
offset operations, which are not yet solved.
On 21/10/2024 14:08, John David via Discuss wrote:
Thanks for the info, Adrian. When it is in a core library, in the
OpenSCAD core routines, it makes sense to track these down and see if there
is a more efficient solution. It is also important to realize that
efficient algorithms are notoriously difficult to implement. I know people
who have gotten their MS and PhD's doing just that. That said, it is still
worth a look to see if there are better algorithms or tricks to speed
things up. Thanks again.
On Sun, Oct 20, 2024 at 11:26 PM Adrian Mariano avm4@cornell.edu wrote:
Note that when I am talking about O(N^2) algorithms I mean
implementations in BOSL2, not implementations in core OpenSCAD. I
actually implemented an O(N^3) algorithm in one place (the skin function)
because it works and is useful on small cases. (But there is a warning in
the docs that it's cubic and to avoid large inputs.) The problem is that
in userspace, these quadratic algorithms appear to be the best that is
possible.
On Sun, Oct 20, 2024 at 5:45 PM John David ebo.2112@gmail.com wrote:
No. I agree that O(N^2) is a problem (and explains why I have had
trouble from time to time with OpenSCAD). Now that I see how you are
embedding the "required" O(log N) within another and that this would
already give you an O(N log N).
BTW, I have only ever once recommended an algorithm that I knew to be
O(N^2) - that was part of a UI initialization where users could update a
command list. It was only ever run once (at boot), was guaranteed to be
limited to 6 to 10 commands at most, this was on a memory limited system,
and some part of the code depended on that list being sorted. A
bubble-sort is only ~6 lines of additional code, and if you add 2 more you
can guarantee that it will never be handed 1,000,000 strings. Even to
implement Qsort would have put a strain on their memory budget.
On Sun, Oct 20, 2024 at 12:07 PM Adrian Mariano via Discuss <
discuss@lists.openscad.org> wrote:
Right now, every polygon operation we have implemented in BOSL2 is
O(N^2), so if you feed it a polygon with 1000 points, which is not absurd,
you can expect a long wait due to quadratic run time. It's tough to know
for sure for the cases at hand whether we're dominated by asymptotic run
time or by a huge constant. That is, a million operations isn't that
many, so maybe if we were just 100x faster the O(N^2) would be fine for
practical cases with polygons. It's also a question of how many points
the polygon needs to have before O(N log N) would matter. As I recall,
advanced algorithms march around the polygon and enter things into a
priority queue and can find the intersections in O(N log N). I tried to
re-implement offset() to be more robust using a method that involves
polygon union/intersection type operations and run time for simple cases
was >1 minute. On inputs that I don't recall but probably had more like
100 points than 1000.
Note that to be clear, the point of a priority queue operation running
in O(log N) is that it means you can do O(N) of them and get O(N log N) so
you beat O(N^2).
For the problem of point merging for polyhedra, it's entirely possible
to have 50,000 points in a polyhedron, and having 1000 points is quite
modest. So how does O(N^2) look for that? You want to run O(N^2)
algorithms on things where N approaches 10^6? Now we have attempted to
implement an O(N log N) algorithm in BOSL2 and at least back when we tested
it, I think it appeared to help, with a crossover point of around 400
points. (Note that improvement from O(N^2) depends on the data being
non-uniform.)
On Sun, Oct 20, 2024 at 11:43 AM John David via Discuss <
discuss@lists.openscad.org> wrote:
What is the algorithmic order of what is implemented? Is O(log n)
actually required? The issue implied by Chun Kit's comment on ADT and
nested lists and lambdas is likely what is making the eval expensive (or in
alg analysis make the constant 'K' go through the roof).
My experience with running into issues like this is that there is
rarely a simple fix and you have to start a new version of a project with
time profiling unit-testing baked in. I'm not sure anyone has the time for
that (unless someone is taking this up as a student project, or getting
paid).
On Sun, Oct 20, 2024 at 8:48 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
I think it is possible to have O(log n) priority queue for purely
functional languages. The problem is that you can't use lists for that, and
have to ADT as nested lists or lambdas. Not sure if openscad handles
sharing well.
On 20/10/2024 20:32, Adrian Mariano via Discuss wrote:
I think the openscad userspace computation issue is a little more
complicated. Certainly having faster execution would help, but there's
also the problem of efficient access to advanced data structures. My
recollection is that efficient algorithms for geometric processes tend to
require things like a priority queue, and it doesn't appear like this can
be implemented to run in the required O(log n) operation time.
Regarding warning levels, the discussion at
https://github.com/openscad/openscad/issues/5135 seems to suggest
some extra complications about this.
On Sun, Oct 20, 2024 at 1:27 AM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
There are two issues here:
- openscad userspace computation is slow.
- warning levels
For 1, there are ways to improve this situation, but it will take
quite a bit of effort and I don't have too much time to pull it off now.
Basically just make the interpretation using bytecode and skip all the
expensive hashtable lookup for each variable/function argument, as well as
AST traversal. It is not hard, but it is quite tedious to rewrite
everything and make sure the behavior is compatible.
For warning levels, IMO fixing non-manifold geometry is probably
common enough that it can be regarded as a debug level info.
On 19/10/2024 04:38, Adrian Mariano via Discuss wrote:
There is an OpenSCAD issue about this:
https://github.com/openscad/openscad/issues/5135. I thought they
WERE going to make that an informational message rather than a warning. I
raised the point that it's basically impossible to reasonably use OpenSCAD
without setting stop on first warning because it just causes an error to
cascade into pages of garbage and hide the true problem.
If OpenSCAD is going to be picky then BOSL2 has to run
vnf_merge_points() to look for the duplicate points and combine them in the
topology. You can do this now if you want to make it work. We don't do
this automatically because we are nervous that it will be slow, though for
the above rounded_prism example it's not terrible on my machine, boosting
preview time from 0.08s to 0.3 s, so a factor of three slower, but still
fast enough. However, if you round all the edges preview time goes from
0.7s to 5s which is getting annoying. (I did this tests with a large
splinesteps value, so it doesn't need to be quite so bad.) So run time can
be a potential concern at least sometimes. Almost every interesting shape
BOSL2 creates is going to have duplicate non-exact points, so longer term
it raises questions about basically complicating things throughout BOSL2 to
track edges, for example, to reduce the points that need to be checked for
merges. Maybe if they ever introduce structures outside of textmetrics
this will seem more reasonable to do. (Note that the rounded square prism
is constructed from 26 bezier patches, one for each face, edge and corner
and I don't see a reasonable way to actually track the faces that meet from
different patches at the same edge to directly exploit the knowledge that
the patches share a boundary.)
On Fri, Oct 18, 2024 at 4:01 PM Todd Allen via Discuss <
discuss@lists.openscad.org> wrote:
If I recall correctly, openscad should try the CGAL way of
repairing meshes when manifold cannot import
the mesh, no idea why it doesn't work in this case.
I reported this incorrectly as an error which stopped rendering.
But it is only a warning. However I had the option set to stop at first
warning. Disabling that option allows this to successfully render.
If this sort of mesh issue is expected to be commonly corrected by
the automatic repair process perhaps it would be ok to downgrade this
message from WARNING to INFO and only after the repair fails issue a
warning or let it error out.
On Fri, Oct 18, 2024 at 12:45 PM Chun Kit LAM via Discuss <
discuss@lists.openscad.org> wrote:
Are you saying that vertexes shared between faces must use the
same
indexes?
Both yes and no. If you mean vertices shared between triangles
must use
the same indices, yes. But you can have vertices with the same
coordinate, so they can have different indices and are not shared
by
triangles, despite triangles containing them can be touching
geometrically (if you consider coordinates).
The topological definition of manifoldness used in manifold is
actually
very simple, see
https://github.com/elalish/manifold/wiki/Manifold-Library#manifoldness-definition
Every edge of every triangle must contain the same two
vertices (by
index) as exactly one other triangle edge, and the start and end
vertices must switch places between these two edges. The triangle
vertices must appear in counter-clockwise order when viewed from
the
outside of the manifold.
I think the issue is in the polyhedron triangle list not being
manifold.
E.g. there may be a tiny open hole in the mesh, but merging
vertices
close to each other may make the hole disappear because all
vertices
around the hole are merged into one. If I recall correctly,
openscad
should try the CGAL way of repairing meshes when manifold cannot
import
the mesh, no idea why it doesn't work in this case.
On 19/10/2024 01:24, Jordan Brown wrote:
On 10/18/2024 9:52 AM, Chun Kit LAM via Discuss wrote:
But manifold doesn't really care about coordinates when
checking for
manifoldness, it just cares about vertex indices in the list
of
triangles. Previously, openscad would snap vertices to a grid
and
merge identical vertices, but that can lose manifoldness in
general
and it is really hard to fix, so it is no longer doing that
when the
mesh PolySet can directly be imported into manifold.
Are you saying that vertexes shared between faces must use the
same
indexes? Experiments indicate that there's no such
requirement. I
constructed a cube out of 24 vertexes, and Manifold seemed
perfectly
happy with it. Correcting the 2e-16 values in the rounded
prism to
zero, without eliminating the duplication, made the problem go
away.
I'm not really a fan of the grid-snap scheme; it causes
problems on
its own. Getting rid of it might be a win, but will likely
cause
problems like this one. (But I admit I have no experience with
not
using it.) I'd like to think that we could have a scheme that
snapped
together "clusters" of points that are very close to one
another (say,
a difference of less than one part in 10^14), and gave up if a
cluster
ever spanned the limit. (That is, if point A is considered
close to
B, and B is considered close to C, but A is not close to C.)
Such a
scheme seems like it could have a very high accuracy rate,
fixing FP
precision problems without merging points that should be
distinct.
But I suspect that it would also be quite expensive.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org