Empathy List Archives

NH

nop head

Fri, Jun 3, 2016 8:23 AM

I don't think B-rep is the problem. It is the fact that CGAL appears to do
nothing to short cut unions. I.e. it doesn't check for completely disjoint
objects and it doesn't seem to look for facets with no intersections and
pass those straight through. The only real work union needs to do is on the
facets where the objects overlap.

On 3 June 2016 at 07:52, Torsten Paul Torsten.Paul@gmx.de wrote:

On 06/03/2016 03:58 AM, Ronaldo wrote:

The lesson here is: to do CSG operations with B-rep (the internal
representation CGAL uses) works only for small number of primitives.
To deal with a great number of primitives OpenSCAD needs to look
for alternative internal representations.

Yes, this is all pretty much known, and the discussion about
alternatives is also not new. The Problem is that there's no
real alternative in sight.

The page collecting some info is:

https://github.com/openscad/openscad/wiki/Project%3A-Survey-of-CSG-algorithms

ciao,
Torsten.

OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

I don't think B-rep is the problem. It is the fact that CGAL appears to do nothing to short cut unions. I.e. it doesn't check for completely disjoint objects and it doesn't seem to look for facets with no intersections and pass those straight through. The only real work union needs to do is on the facets where the objects overlap. On 3 June 2016 at 07:52, Torsten Paul <Torsten.Paul@gmx.de> wrote: > On 06/03/2016 03:58 AM, Ronaldo wrote: > > The lesson here is: to do CSG operations with B-rep (the internal > > representation CGAL uses) works only for small number of primitives. > > To deal with a great number of primitives OpenSCAD needs to look > > for alternative internal representations. > > > Yes, this is all pretty much known, and the discussion about > alternatives is also not new. The Problem is that there's no > real alternative in sight. > > The page collecting some info is: > > https://github.com/openscad/openscad/wiki/Project%3A-Survey-of-CSG-algorithms > > ciao, > Torsten. > > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >

R

Ronaldo

Fri, Jun 3, 2016 12:59 PM

nophead wrote

I don't think B-rep is the problem. It is the fact that CGAL appears to do
nothing to short cut unions. I.e. it doesn't check for completely disjoint
objects and it doesn't seem to look for facets with no intersections and
pass those straight through. The only real work union needs to do is on
the
facets where the objects overlap.

Bounding boxes could alleviate the problem. But bounding boxes grow after
each rotation for instance. It is good for simple cases.

--
View this message in context: http://forum.openscad.org/STL-without-render-tp17503p17550.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

nophead wrote > I don't think B-rep is the problem. It is the fact that CGAL appears to do > nothing to short cut unions. I.e. it doesn't check for completely disjoint > objects and it doesn't seem to look for facets with no intersections and > pass those straight through. The only real work union needs to do is on > the > facets where the objects overlap. Bounding boxes could alleviate the problem. But bounding boxes grow after each rotation for instance. It is good for simple cases. -- View this message in context: http://forum.openscad.org/STL-without-render-tp17503p17550.html Sent from the OpenSCAD mailing list archive at Nabble.com.

R

Ronaldo

Fri, Jun 3, 2016 1:16 PM

tp3 wrote

Yes, this is all pretty much known, and the discussion about
alternatives is also not new. The Problem is that there's no
real alternative in sight.

The page collecting some info is:
https://github.com/openscad/openscad/wiki/Project%3A-Survey-of-CSG-algorithms

Thank you for the reference. I am playing with F-rep (implicit
representation) that Doug has mentioned elsewhere. I have implemented simple
modelling and rendering techniques using just OpenSCAD language. It is
certainly not efficient that way but promising. Here is an example of a
twist of a holed cube:
http://forum.openscad.org/file/n17551/Holed_cube_twist.png
The twisted hole was made in the F-rep form. The vertical hole was done by
CGAL from regular OpenSCAD cylinder. Imagine do that with B-rep directly...

Note that voxel based methods leads naturally to bounding box benefits. The
edges in the above image are rough because I have not implemented a feature
recognition method like a B-rep boolean operation inside a voxel.

--
View this message in context: http://forum.openscad.org/STL-without-render-tp17503p17551.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

tp3 wrote > Yes, this is all pretty much known, and the discussion about > alternatives is also not new. The Problem is that there's no > real alternative in sight. > > The page collecting some info is: > https://github.com/openscad/openscad/wiki/Project%3A-Survey-of-CSG-algorithms Thank you for the reference. I am playing with F-rep (implicit representation) that Doug has mentioned elsewhere. I have implemented simple modelling and rendering techniques using just OpenSCAD language. It is certainly not efficient that way but promising. Here is an example of a twist of a holed cube: <http://forum.openscad.org/file/n17551/Holed_cube_twist.png> The twisted hole was made in the F-rep form. The vertical hole was done by CGAL from regular OpenSCAD cylinder. Imagine do that with B-rep directly... Note that voxel based methods leads naturally to bounding box benefits. The edges in the above image are rough because I have not implemented a feature recognition method like a B-rep boolean operation inside a voxel. -- View this message in context: http://forum.openscad.org/STL-without-render-tp17503p17551.html Sent from the OpenSCAD mailing list archive at Nabble.com.

MK

Marius Kintel

Fri, Jun 3, 2016 3:13 PM

On Jun 3, 2016, at 04:23 AM, nop head nop.head@gmail.com wrote:

I don't think B-rep is the problem. It is the fact that CGAL appears to do nothing to short cut unions. I.e. it doesn't check for completely disjoint objects and it doesn't seem to look for facets with no intersections and pass those straight through.

..which I believe is an effect of CGAL defining its B-Rep as Nef polyhedrons, which is an intersection of infinite planes, which makes it expensive to calculate the bounding box. I’m not 100% certain of the internals, but it’s pretty clear that they haven’t spend much (or any) time on performance optimization.

-Marius

> On Jun 3, 2016, at 04:23 AM, nop head <nop.head@gmail.com> wrote: > > I don't think B-rep is the problem. It is the fact that CGAL appears to do nothing to short cut unions. I.e. it doesn't check for completely disjoint objects and it doesn't seem to look for facets with no intersections and pass those straight through. ..which I believe is an effect of CGAL defining its B-Rep as Nef polyhedrons, which is an intersection of infinite planes, which makes it expensive to calculate the bounding box. I’m not 100% certain of the internals, but it’s pretty clear that they haven’t spend much (or any) time on performance optimization. -Marius

P

Parkinbot

Fri, Jun 3, 2016 8:53 PM

So, do you think one could 'spend this time' and some extra effort in
OpenSCAD before entering CGAL? That was my suggestion in the thread I'd
especially opened for discussion on this theme.

--
View this message in context: http://forum.openscad.org/STL-without-render-tp17503p17553.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

So, do you think one could 'spend this time' and some extra effort in OpenSCAD before entering CGAL? That was my suggestion in the thread I'd especially opened for discussion on this theme. -- View this message in context: http://forum.openscad.org/STL-without-render-tp17503p17553.html Sent from the OpenSCAD mailing list archive at Nabble.com.

MK

Marius Kintel

Fri, Jun 3, 2016 9:06 PM

On Jun 3, 2016, at 16:53 PM, Parkinbot rudolf@parkinbot.com wrote:

So, do you think one could 'spend this time' and some extra effort in
OpenSCAD before entering CGAL?

Yes, we could definitely do some optimization on our own if we have access to the bounding boxes.
My main concern is whether developer time is better spent moving away from CGAL rather than optimizing for CGAL.
..but if we write good code, we could potentially reuse some of that for future back-ends as well.

-Marius

> On Jun 3, 2016, at 16:53 PM, Parkinbot <rudolf@parkinbot.com> wrote: > > So, do you think one could 'spend this time' and some extra effort in > OpenSCAD before entering CGAL? Yes, we could definitely do some optimization on our own if we have access to the bounding boxes. My main concern is whether developer time is better spent moving away from CGAL rather than optimizing for CGAL. ..but if we write good code, we could potentially reuse some of that for future back-ends as well. -Marius

P

Parkinbot

Fri, Jun 3, 2016 10:09 PM

With 3D Fast Intersection and Distance Computation (AABB Tree)
http://doc.cgal.org/latest/AABB_tree/index.html#aabb_tree_introduction
CGAL has some fast built-in intersection support that also offers a
predicate to do some fast intersection testing. I don't know whether
OpenSCAD employs this package at all or data formats are compatible, but in
my eyes it is a more than obvious optimization to check for intersection
before invoking any costly boolean operation. Also I'd try to restrict the
operation to at least a common bounding box if the test returns true.

--
View this message in context: http://forum.openscad.org/STL-without-render-tp17503p17557.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

With 3D Fast Intersection and Distance Computation (AABB Tree) <http://doc.cgal.org/latest/AABB_tree/index.html#aabb_tree_introduction> CGAL has some fast built-in intersection support that also offers a predicate to do some fast intersection testing. I don't know whether OpenSCAD employs this package at all or data formats are compatible, but in my eyes it is a more than obvious optimization to check for intersection *before* invoking any costly boolean operation. Also I'd try to restrict the operation to at least a common bounding box if the test returns true. -- View this message in context: http://forum.openscad.org/STL-without-render-tp17503p17557.html Sent from the OpenSCAD mailing list archive at Nabble.com.

discuss@lists.openscad.org

STL without render?