unreasonable amounts of memory used near CSGTermNormalizer::normalizePass

[chrysn]

the attached file makes openscad use unreasonable amounts of memory (in numbers: can't tell, longest run was aborted after 5gb used) for the negative of a relatively simple honeycomb shape.

the file consists of two top level elements, top_part and bottom_part (being a cube minus top_part); when bottom_part is active (which it is in the file), rendering in opencsg mode takes indeterminate amounts of time and memory. cgal works fine.

backtracing openscad during the run shows deep recursion (>100 levels) in CSGTermNormalizer::normalizePass.

the version used was git 67eb2eb; the original report (together with some more details i consider unimportant) can be found at http://bugs.debian.org/676967.

[chrysn]

it seems attachments don't work in github's issue tracker; the file can be downloaded here

[kintel]

A very quick analysis shows:

1. The excessive use of intersections cause very large CSG trees to be created
2. When building very large CSG trees, OpenSCAD should detect and abort this, according to the corresponding preference setting

[chrysn]

On Wed, Jun 13, 2012 at 09:25:50AM -0700, Marius Kintel wrote:

1. The excessive use of intersections cause very large CSG trees to be
   created

just for me to understand: why is it, then, that bottom_part is rendered
very quickly, and top_part (being difference() { cube(); bottom_part();
} basically) is so difficult to render?

[kintel]

The issue with intersections is that it's not possible to render them directly with OpenCSG. Instead they have to be broken down into sums of differences through a process called normalization. In practice, this means that if intersections exist as negative volumes, we must render all permutations where only one of the intersection nodes is turned off at a time. This results in extremely large trees (as well as rendering times).

To look at how this works in practice, try changing the honeycomb model to e.g. 2 rows and 2 columns and look at Design->Show CSG Products.

For the issue at hand, there are two simple ways to reduce the number of intersections:

1. Use render() to hide intersections:

module hexagon(size, height) {
  render() intersection_for(angle = [0 : 60 : 120]) {
    rotate(angle) cube(size = [size, 2 * size, height], center = true);
  }
}

2. Rewrite without intersections:

use <MCAD/regular_shapes.scad>
module hexagon(size, height) {
  translate([0,0,-height/2]) hexagon_prism(height, size/2);
}

[kintel]

I think a good enough fix for this is to fix the problem that, for this particular example, OpenSCAD doesn't should detect and abort normalization according to the corresponding preference setting.