CSG mind challenge

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

CSG mind challenge

kintel
Administrator
Hi all,

I'm looking at issue #127: https://github.com/openscad/openscad/issues/127

The 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.pdf
http://www.opencsg.org/data/csg_freenix2005_paper.pdf

A 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





normtest.scad (471 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: CSG mind challenge

donbright
The paper says this:

"Pathological objects will always exist for which the NGP algorithm's
time complexity explodes" (NGP=Normalization and Geometric Pruning)

So it seems like even if a good NGP implementation is created, it
still might be nice to have some kind of 'safety' mechanism to keep
the system from grinding to a halt (no idea how to implement that.. i
am assuming that if 'time complexity' can explode then so can RAM
usage...)

-DB


On Wed, Jun 20, 2012 at 7:40 AM, Marius Kintel <[hidden email]> wrote:

> Hi all,
>
> I'm looking at issue #127: https://github.com/openscad/openscad/issues/127
>
> The 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.pdf
> http://www.opencsg.org/data/csg_freenix2005_paper.pdf
>
> A 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
>
>
>
>
>
> _______________________________________________
> OpenSCAD mailing list
> [hidden email]
> http://rocklinux.net/mailman/listinfo/openscad
>

Reply | Threaded
Open this post in threaded view
|

Re: CSG mind challenge

kintel
Administrator
On Jun 21, 2012, at 13:48 , Don Bright wrote:
>
> So it seems like even if a good NGP implementation is created, it
> still might be nice to have some kind of 'safety' mechanism to keep
> the system from grinding to a halt

There is a preference setting for aborting normalization of the tree grows too large. Part of issue 127 is that this check isn't always triggering as it should.

My challenge was an attempt to remedy the particular case where you have lots of intersections which are negative volumes, a case which appear to pop up from time to time.

 -Marius


Reply | Threaded
Open this post in threaded view
|

Re: CSG mind challenge

Carl Witty
In reply to this post by kintel
On Wed, Jun 20, 2012 at 5:40 AM, Marius Kintel <[hidden email]> wrote:

> Hi all,
>
> I'm looking at issue #127: https://github.com/openscad/openscad/issues/127
>
> The 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.pdf
> http://www.opencsg.org/data/csg_freenix2005_paper.pdf
>
> A 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.

This looks equivalent to a circuit design problem: find a
representation of A-B^C-D^E in sum-of-products form given the "don't
care" conditions of B^D, B^E, C^D, C^E.  You might be able to find
inspiration in "circuit minimization" or "logic optimization"
literature (for instance, you could look into the "Espresso heuristic
logic minimizer"
(http://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer).

Carl