Empathy List Archives

discuss@lists.openscad.org

OpenSCAD general discussion Mailing-list

No bounding box test for union() before entering CGAL?

Parkinbot

Thu, Jun 2, 2016 9:38 PM

Have a look at this simple code, which F5-displays immediately but
F6-renders several minutes on my machine. It clearly shows that there is not
even a simple boundingbox test done before CGAL invoke.

for (i = [1:30])
for (j = [1:30])
translate([i20, j20, 0])
cylinder(r = 5, h = 10);

And I'd say from its O(n²) behavior, that also CGAL doesn't seem to make any
effort to use boundingbox tests itself. Maybe this because of the way, how
it is invoked ...

Wouldn't it speed up things a lot if

boundingbox intersection checks of chached elements were introduced to be
able to call CGAL separately - and multithreaded - for obviously
non-intersecting chunks.
to invoke CGAL only once for non-intersecting chached elements occurring
multiple times (= apply last affine mapping after CGAL)

It could also make sense, to introduce a directive (or a switch) for
indicating multiple elements with non intersecting bounding boxes to
OpenSCAD. (conditional analysis)
Also have a look here:
http://www8.cs.umu.se/education/examina/Rapporter/NilsBaeckman.pdf

--
View this message in context: http://forum.openscad.org/No-bounding-box-test-for-union-before-entering-CGAL-tp17538.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

There has been a lot of discussion going on about F6 rendering time. I never had to fight with a design with many non-intersecting clones, so I didn't do any testing on it. Now I did - with astonishing results. Have a look at this simple code, which F5-displays immediately but F6-renders several minutes on my machine. It clearly shows that there is not even a simple boundingbox test done before CGAL invoke. > for (i = [1:30]) > for (j = [1:30]) > translate([i*20, j*20, 0]) > cylinder(r = 5, h = 10); And I'd say from its O(n²) behavior, that also CGAL doesn't seem to make any effort to use boundingbox tests itself. Maybe this because of the way, how it is invoked ... Wouldn't it speed up things a lot if 1. boundingbox intersection checks of chached elements were introduced to be able to call CGAL separately - and multithreaded - for obviously non-intersecting chunks. 2. to invoke CGAL only once for non-intersecting chached elements occurring multiple times (= apply last affine mapping after CGAL) It could also make sense, to introduce a directive (or a switch) for indicating multiple elements with non intersecting bounding boxes to OpenSCAD. (conditional analysis) Also have a look here: http://www8.cs.umu.se/education/examina/Rapporter/NilsBaeckman.pdf -- View this message in context: http://forum.openscad.org/No-bounding-box-test-for-union-before-entering-CGAL-tp17538.html Sent from the OpenSCAD mailing list archive at Nabble.com.

Parkinbot

Wed, Jun 8, 2016 5:44 PM

I forgot to add, there is of course a way to F6-render this specific problem
even for 40000 cylinders within 5 seconds (F5 takes about a minute)

linear_extrude(height = 10)
for (i = [1:200])
for (j = [1:200])
translate([i20, j20, 0])
circle(r = 5);

this demonstrates even more how OpenSCAD could win using some boundary box
testing.

--
View this message in context: http://forum.openscad.org/No-bounding-box-test-for-union-before-entering-CGAL-tp17538p17601.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

I forgot to add, there is of course a way to F6-render this specific problem even for 40000 cylinders within 5 seconds (F5 takes about a minute) > linear_extrude(height = 10) > for (i = [1:200]) > for (j = [1:200]) > translate([i*20, j*20, 0]) > circle(r = 5); this demonstrates even more how OpenSCAD could win using some boundary box testing. -- View this message in context: http://forum.openscad.org/No-bounding-box-test-for-union-before-entering-CGAL-tp17538p17601.html Sent from the OpenSCAD mailing list archive at Nabble.com.