J
jim.klessig
Sat, Dec 9, 2017 6:12 PM
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
null
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
null
DM
doug moen
Sat, Dec 9, 2017 7:31 PM
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 jim.klessig@gmail.com 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
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 <jim.klessig@gmail.com> 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
> Discuss@lists.openscad.org
> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>
>
NH
nop head
Sat, Dec 9, 2017 8:40 PM
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 doug@moens.org 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 jim.klessig@gmail.com 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
> 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 <doug@moens.org> 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 <jim.klessig@gmail.com> 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
>> Discuss@lists.openscad.org
>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>
>>
>
> _______________________________________________
> OpenSCAD mailing list
> Discuss@lists.openscad.org
> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>
>
DM
doug moen
Sat, Dec 9, 2017 9:17 PM
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 doug@moens.org 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 jim.klessig@gmail.com 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
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 <doug@moens.org> 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 <jim.klessig@gmail.com> 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
>> Discuss@lists.openscad.org
>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>>
>>
>
