Hi all,

I'm looking at issue #127:

https://github.com/openscad/openscad/issues/127The issue is that normalization in conjunction with intersections tend to explode the size of normalized CSG trees.

Trees are normalized and pruned according to the algorithms specified in these papers:

http://www.cc.gatech.edu/~turk/my_papers/pxpl_csg.pdfhttp://www.opencsg.org/data/csg_freenix2005_paper.pdfA minimal example is attached. This describes a CSG model which can be written A - B^C - D^E where B and C intersects each other, so does D and E, but the two groups are disjunct from each other.

The OpenSCAD normalization normalizes this to the following:

difference() { A(); B(); D(); }

difference() { A(); B(); E(); }

difference() { A(); C(); D(); }

difference() { A(); C(); E(); }

Due to the groups being disjunct, this is, however, redundant and the optimal way of rendering this would be:

difference() { A(); B(); D(); }

difference() { A(); C(); E(); }

This is a simple example, but for any slightly more complex examples, tree sizes easily grow to 10s of thousands of elements.

As far as I can see, I've implemented normalization correctly, but I haven't dealt with "difference pruning" as mentioned in the first paper. However, I expect OpenCSG to do that, but it's a bit late since the normalization needs to finalize before reaching OpenCSG.

I know that this is a bit hard to figure this out, but any help is appreciated :)

Cheers,

-Marius