Re: Discuss Digest, Vol 37, Issue 9

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

Re: Discuss Digest, Vol 37, Issue 9

jim_klessig
I said 
"But with the "negative" space added, there is no longer a single solution."

Nop replied 
"I think there is if you hull all the positive objects first and then
process the negative objects. Imagine a band around the positive objects
and then introduce the negatives ones from the outside. You could get a
conflict of they overlap though. That would be an error."


A simple counter example would be two positive circles ( making a worm) then a smaller negative circle between them.
There are two ways the worm can bend around that negative circle, giving two possible solutions. And both solutions will have regions of 0 width.

Add a second negative circle and now you have an "s", a "z", and two different "c" shapes.
There are other bigger problems with "negative" shapes too.

Sent from my U.S. Cellular® Smartphone

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Discuss Digest, Vol 37, Issue 9

doug.moen
With Nop Head's "concave hull" idea, I think it can be made precise.

First, as he said, you make a convex hull around the positive objects. The boundary of the convex hull can be thought of as rubber, like a rubber band in 2D, or a balloon skin in 3D.

Then, the negative objects push on the balloon skin from outside and create concavities. There are two cases:
  • If the negative object is partly inside and partly outside the convex hull, then it must intersect exactly one surface of the hull (the balloon skin). In other words, the hull surface bisects the negative object into exactly two parts. In that case, the negative object pushes the balloon skin inwards, and creates a concavity.
  • Otherwise, the negative object is ignored. This covers several cases:
    • The negative object is entirely outside of the convex hull. It doesn't touch the balloon skin, so it has no effect.
    • The negative object is entirely inside the convex hull. Again, it doesn't interact with the ballon skin, and so it has no effect.
    • The negative object is partitioned into 3 or more pieces by the hull surface. This is an ambiguous situation, I don't know what it should mean in terms of Nop Head's model, so I'm saying that the negative object is again ignored.
I personally have no idea how to implement this, or how computationally expensive that would be. Based on other people's comments, I guess you are computing a minimum energy surface, which could be done using finite element analysis?

Also, I don't have any intuition about how useful this would be as a modelling primitive. I can easily visualize how this works in my head, which is good. But how useful is this for modelling? It seems to me that the concavities that you can create are restricted to roughly "conical" depressions, which might limit the use cases.

If you google "concave hull", you discover something different than what Nop Head describes, something also known as "alpha shapes", which are supported by CGAL. With Alpha Shapes, you create a possibly concave skin enveloping a set of points, and it looks like this is powerful enough to generate an approximation of virtually any shape.

On 9 December 2017 at 13:12, jim.klessig <[hidden email]> wrote:
I said 
"But with the "negative" space added, there is no longer a single solution."

Nop replied 
"I think there is if you hull all the positive objects first and then
process the negative objects. Imagine a band around the positive objects
and then introduce the negatives ones from the outside. You could get a
conflict of they overlap though. That would be an error."


A simple counter example would be two positive circles ( making a worm) then a smaller negative circle between them.
There are two ways the worm can bend around that negative circle, giving two possible solutions. And both solutions will have regions of 0 width.

Add a second negative circle and now you have an "s", a "z", and two different "c" shapes.
There are other bigger problems with "negative" shapes too.

Sent from my U.S. Cellular® Smartphone

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Discuss Digest, Vol 37, Issue 9

nophead
> Based on other people's comments, I guess you are computing a minimum energy surface, which could be done using finite element analysis?

I don't think it is much different from the positive convex hull case. I am not familiar with the 3D algorithm but the 2D one is pretty simple. You find an extreme point, say the bottom left, and find the next point calculating the angle to all the other points and picking the greatest. Then repeat for the next point and so on, no actual surface tension analysis. To handle the negative points I think you would work out the smallest angle to those and pick it if it is less than the angle to the next positive point.

I presume 3D hull is done with angles to planes instead of lines. It's a wrapping algorithm rather than simulating an elastic skin but gives the same result.

On 9 December 2017 at 19:31, doug moen <[hidden email]> wrote:
With Nop Head's "concave hull" idea, I think it can be made precise.

First, as he said, you make a convex hull around the positive objects. The boundary of the convex hull can be thought of as rubber, like a rubber band in 2D, or a balloon skin in 3D.

Then, the negative objects push on the balloon skin from outside and create concavities. There are two cases:
  • If the negative object is partly inside and partly outside the convex hull, then it must intersect exactly one surface of the hull (the balloon skin). In other words, the hull surface bisects the negative object into exactly two parts. In that case, the negative object pushes the balloon skin inwards, and creates a concavity.
  • Otherwise, the negative object is ignored. This covers several cases:
    • The negative object is entirely outside of the convex hull. It doesn't touch the balloon skin, so it has no effect.
    • The negative object is entirely inside the convex hull. Again, it doesn't interact with the ballon skin, and so it has no effect.
    • The negative object is partitioned into 3 or more pieces by the hull surface. This is an ambiguous situation, I don't know what it should mean in terms of Nop Head's model, so I'm saying that the negative object is again ignored.
I personally have no idea how to implement this, or how computationally expensive that would be. Based on other people's comments, I guess you are computing a minimum energy surface, which could be done using finite element analysis?

Also, I don't have any intuition about how useful this would be as a modelling primitive. I can easily visualize how this works in my head, which is good. But how useful is this for modelling? It seems to me that the concavities that you can create are restricted to roughly "conical" depressions, which might limit the use cases.

If you google "concave hull", you discover something different than what Nop Head describes, something also known as "alpha shapes", which are supported by CGAL. With Alpha Shapes, you create a possibly concave skin enveloping a set of points, and it looks like this is powerful enough to generate an approximation of virtually any shape.

On 9 December 2017 at 13:12, jim.klessig <[hidden email]> wrote:
I said 
"But with the "negative" space added, there is no longer a single solution."

Nop replied 
"I think there is if you hull all the positive objects first and then
process the negative objects. Imagine a band around the positive objects
and then introduce the negatives ones from the outside. You could get a
conflict of they overlap though. That would be an error."


A simple counter example would be two positive circles ( making a worm) then a smaller negative circle between them.
There are two ways the worm can bend around that negative circle, giving two possible solutions. And both solutions will have regions of 0 width.

Add a second negative circle and now you have an "s", a "z", and two different "c" shapes.
There are other bigger problems with "negative" shapes too.

Sent from my U.S. Cellular® Smartphone

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Discuss Digest, Vol 37, Issue 9

doug.moen
In reply to this post by doug.moen
I missing something in my case analysis. If a negative object intersects a positive object, that is ambiguous. You could resolve this by ignoring the negative object in this case. Yeah, that's an arbitrary choice, but any implementation of the idea would need to pick an unambiguous set of rules for interpreting positive and negative objects.

On 9 December 2017 at 14:31, doug moen <[hidden email]> wrote:
With Nop Head's "concave hull" idea, I think it can be made precise.

First, as he said, you make a convex hull around the positive objects. The boundary of the convex hull can be thought of as rubber, like a rubber band in 2D, or a balloon skin in 3D.

Then, the negative objects push on the balloon skin from outside and create concavities. There are two cases:
  • If the negative object is partly inside and partly outside the convex hull, then it must intersect exactly one surface of the hull (the balloon skin). In other words, the hull surface bisects the negative object into exactly two parts. In that case, the negative object pushes the balloon skin inwards, and creates a concavity.
  • Otherwise, the negative object is ignored. This covers several cases:
    • The negative object is entirely outside of the convex hull. It doesn't touch the balloon skin, so it has no effect.
    • The negative object is entirely inside the convex hull. Again, it doesn't interact with the ballon skin, and so it has no effect.
    • The negative object is partitioned into 3 or more pieces by the hull surface. This is an ambiguous situation, I don't know what it should mean in terms of Nop Head's model, so I'm saying that the negative object is again ignored.
I personally have no idea how to implement this, or how computationally expensive that would be. Based on other people's comments, I guess you are computing a minimum energy surface, which could be done using finite element analysis?

Also, I don't have any intuition about how useful this would be as a modelling primitive. I can easily visualize how this works in my head, which is good. But how useful is this for modelling? It seems to me that the concavities that you can create are restricted to roughly "conical" depressions, which might limit the use cases.

If you google "concave hull", you discover something different than what Nop Head describes, something also known as "alpha shapes", which are supported by CGAL. With Alpha Shapes, you create a possibly concave skin enveloping a set of points, and it looks like this is powerful enough to generate an approximation of virtually any shape.

On 9 December 2017 at 13:12, jim.klessig <[hidden email]> wrote:
I said 
"But with the "negative" space added, there is no longer a single solution."

Nop replied 
"I think there is if you hull all the positive objects first and then
process the negative objects. Imagine a band around the positive objects
and then introduce the negatives ones from the outside. You could get a
conflict of they overlap though. That would be an error."


A simple counter example would be two positive circles ( making a worm) then a smaller negative circle between them.
There are two ways the worm can bend around that negative circle, giving two possible solutions. And both solutions will have regions of 0 width.

Add a second negative circle and now you have an "s", a "z", and two different "c" shapes.
There are other bigger problems with "negative" shapes too.

Sent from my U.S. Cellular® Smartphone

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org




_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org