AM
Adrian Mariano
Sun, Jan 22, 2023 4:03 AM
So anybody who didn't believe me that the problem is complicated can read
the paper, which is 31 pages long.
I just briefly skimmed over it to see what was in there, and it looks like
the majority is focused on the problem of "correspondence" and "branching"
which both have to do with the case of multiple contours mapping to single
contours. I completely ignored this case, but presumably an OpenSCAD
built-in would need to address it. So I only tried to address the "tiling"
problem, which I thought was hard enough, especially within OpenSCAD. Fig
2 looks like a diagram I drew when devising my approach. My method is a
global optimization over all the mappings of the vertices from the first
contour to the second. If f maps a vertex from C1 to C2 then I minimize
the sum over all v in C1 of d(v,f(v)), where d() is Euclidean distance.
The method you propose is exactly what I was referring to as the arc length
method, and I agree that it will generally produce a good result for
mappings between continuous curves. But for shapes with corners, I think
usually you want to map the corners to each other somehow---at least I
think that looks better, in the absence of any guidance from details of the
application.
On Sat, Jan 21, 2023 at 10:29 PM Kenneth Sloan kennethrsloan@gmail.com
wrote:
Jumping in the middle here, but...
This is an old problem. I wrote several papers on this in the previous
century. A seminal paper is by Fuchs, Kedem & Uselton (CACM, perhaps Nov.
1977). You can find a few small conference papers with my name on them -
and one major paper that handled all sorts of stuff you probably con't care
about. Start here:
https://scholar.google.com/citations?view_op=view_citation&hl=en&user=elhUt8QAAAAJ&citation_for_view=elhUt8QAAAAJ:u-x6o8ySG0sC
Most of what you need is in the references found there.
A lot depends on your assumptions, and how much attention you want to pay
to "features" in the two shapes.
When faced with a new instance of this problem, I usually start with a
simple method:
a) find one "obvious" match between a point on A and a point on B
b) normalize the two 2D curves to have length 1.0, with both 0.0 and 1.0
at the
matching points found in a)
c) connect a point on A to the point on B which is closest in normalized
arc length
This method does a better job of handling non-convex shapes than the
method you seem to be using here (also an old, well-known, method).
As a classic example of how assumptions matter, consider two shapes which
are both perfect circles, with one small bump - but the bump is rotated by
30 degrees in A compared with the orientation in B.
Do you want the resulting shape to have a single bump in A which
disappears as you move to B, while a different bump appears? Or, to you
want a cylinder with a smaller cylinder wrapped around it?
In your example, suppose you have 2 5-pointed stars, but they are rotated
slightly with respect to each other. Do you want the points of the stars
to connect? or not?
And so on...
--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.
On Jan 21, 2023, at 21:09, Sanjeev Prabhakar sprabhakar2006@gmail.com
wrote:
for nearest points mapping center of the 2 sections should almost match in
case of convex shapes
arc lengths i think is a very complicated idea.
here is an example of 2 concave shapes joined with points with approach 2
mentioned in my previous post.
<Screenshot 2023-01-22 at 8.24.24 AM.png>
this is made by intersection of 720 rays and around 100 slices
execution time is 1.5 sec in python, i dont know how long will it take in
pure openscad code.
On Sun, 22 Jan 2023 at 07:47, Adrian Mariano avm4@cornell.edu wrote:
I think you need to think carefully and define what you mean by "nearest
point mapping". It will NOT always work for convex shapes if by nearest
point you mean take one shape (one with more points) and map every point to
the nearest point. Trivial example: square in right half plane map to a
shape in the left half plane: all the points of the right hand shape map
to the single right-most point of the left hand shape. You don't get a
valid mapping.
To make this concept rigorous you need to assure that you use all the
points of both shapes. I did this in my skin() method by looking for the
mapping that maps all points from the larger shape onto the points of the
smaller shape while assuring that every point in the smaller shape is
covered. But now you no longer have a simple concept like "nearest point"
to do the mapping. Instead a complicated optimization arises. This
optimization is solved in my skin() algorithm. But as I am saying, it's
complicated. When I started trying to write skin() I had no idea how
complicated it was going to end up being. This optimization produces great
results, I think, as long as the shapes are "discrete", like polygons with
few edges. If you want to map two curved shapes to each other, the results
are not great, and the run time also becomes uncomfortably long, since the
algorithm has O(N^3) run time.
For your second concept, given two polygons located in 3-space, perhaps
not parallel to each other, how do you define the rays? I don't know how
to do that. I did devise a method maybe sort of like what you are
imagining that involves tangent planes. It produces reasonable results for
continuous shapes, though I think very often results that can also be
easily produced by other means.
You are overlooking the case which I think tends to be best when a smooth
curves is involved: connect them by arc length. This in my experience,
often produces the best result. You have to somehow align them to decide
on the starting point. Then you resample them by arc length to have the
same number of points (or generate them that way) and then simply line up
the points. This can often handle a concave shape, depending on how
different the shapes are, and it tends to produce a nicer form than the
tangent plane method. Depending on how you line things up you may get a
twist---which could be a desirable outcome.
On Sat, Jan 21, 2023 at 8:50 PM Sanjeev Prabhakar <
sprabhakar2006@gmail.com> wrote:
I think
a. if both the sections are convex the nearest point mapping
approach should work
b. if one section is convex and the other section is concave again the
first approach should work where concave shape should be the primary one
c. when both the shapes are concave the 2nd approach should be used
when the shape is so concave like an "S" shape, I have a feeling that it
would be extremely difficult or may be impossible to match without
intersecting lines. You can still do it by matching the number of points,
but it may not make any sense of the shape.
On Sun, 22 Jan 2023 at 06:58, Adrian Mariano avm4@cornell.edu wrote:
The first approach to me looks much better, but you need to add a bunch
of horizontal slices to correctly capture the curvature of the faces. As
shown you have faces that are not coplanar.
I personally do not like the look of the second approach, where an edge
is split. Personal preference. But also, I think this model is bad
because it has lots of very long skinny triangles. You can model more
efficiently and the result is better, in my opinion, when the triangles are
as close to equilateral as possible. Models like the above produce moire
effects and can be hard to view, and if you decrease the triangle count,
you get rippling across the surfaces. The rippling never goes away---just
gets smaller as you shrink the triangles. A horizontal section of such a
model will show zig-zag edges.
But I guess the question is what point are you trying to make? Rogier
suggested we should have a built-in OpenSCAD module that does things like
this (maybe?). Another poster suggested joining convex shapes using convex
hulls of cones as a claim that the desired feature already can be
implemented partially. I have argued that a full implementation is complex
because there are multiple way to align shapes and no single correct way,
so you need different algorithms for alignment. I don't see any evidence
to the contrary shown here. My point is not that the problem cannot be
solved in many interesting and useful cases---I have done it. My point is
that the problem is complicated, and it cannot be solved in all cases, so
that makes a built-in seem unlikely to occur. Furthermore, a solution is
necessarily complex in terms of its interface, since there are several ways
we can imagine aligning points. This also makes a built-in seem unlikely.
We can do lots of nice things with existing libraries and without a
built in, though of course there is the limitation due to the inability to
extract geometrical data from OpenSCAD objects. THAT may actually be
fixed in a future version, so that seems like the path forward towards a
generic solution to this kind of model that can work on geometry instead of
path lists.
On Sat, Jan 21, 2023 at 8:10 PM Sanjeev Prabhakar <
sprabhakar2006@gmail.com> wrote:
nearest point approach will be produce this result:
<Screenshot 2023-01-22 at 6.32.31 AM.png>
rays emanating from center and intersection approach will produce this
result:
<Screenshot 2023-01-22 at 6.35.04 AM.png>
in the 2nd approach 360 lines were intersected in the example.
morelines will produce much refined results and should work in most of the
cases
On Sun, 22 Jan 2023 at 05:41, Adrian Mariano avm4@cornell.edu wrote:
It is possible to write a generic extruder for the convex case using
cones, but there are a couple things that limit this. For most
interesting cases, you need many slices to produce the correct form and to
avoid producing artifacts on the curved faces that arise. (See Jordan's
example.) Where will these slices come from? Note that even with convex
endcaps, the resulting shape need not be convex. You will need the point
list of the data in order to produce the many needed slices, most likely,
since no mechanism for "averaging" geometry exists. Given that you have a
point list, simply computing the desired shape as a polyhedron is much more
efficient than computing it as the union of 100 overlapping cones. The
version I implemented (convex_offset_extrude in BOSL2) flips the cones
around to handle the ends, extrema, whether the shape is increasing or
decreasing. This all requires access to the actual point list.
Note that the direct computation of the polyhedron also already
exists in libraries (it's also here now).
Many examples can be seen here (though the animated examples look
really bad right now for some reason):
https://github.com/revarbat/BOSL2/wiki/skin.scad#functionmodule-skin
On Sat, Jan 21, 2023 at 5:27 PM nop head nop.head@gmail.com wrote:
The points of the cones can be very close to the base so they are
close to being a flat disk. As long as they are inside the hull they get
discarded.
On Sat, 21 Jan 2023 at 22:11, Jordan Brown <
openscad@jordan.maileater.net> wrote:
On 1/21/2023 1:24 PM, Steve Lelievre wrote:
I like the cones because they only involve the one perimeter at the
wide end so the shape produced is completely 'correct' in geometrical terms.
OK, thanks.
Do note that it only works if the two are aligned so that the
points of the cones fall inside the other end's polygon.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
So anybody who didn't believe me that the problem is complicated can read
the paper, which is 31 pages long.
I just briefly skimmed over it to see what was in there, and it looks like
the majority is focused on the problem of "correspondence" and "branching"
which both have to do with the case of multiple contours mapping to single
contours. I completely ignored this case, but presumably an OpenSCAD
built-in would need to address it. So I only tried to address the "tiling"
problem, which I thought was hard enough, especially within OpenSCAD. Fig
2 looks like a diagram I drew when devising my approach. My method is a
global optimization over all the mappings of the vertices from the first
contour to the second. If f maps a vertex from C1 to C2 then I minimize
the sum over all v in C1 of d(v,f(v)), where d() is Euclidean distance.
The method you propose is exactly what I was referring to as the arc length
method, and I agree that it will generally produce a good result for
mappings between continuous curves. But for shapes with corners, I think
usually you want to map the corners to each other somehow---at least I
think that looks better, in the absence of any guidance from details of the
application.
On Sat, Jan 21, 2023 at 10:29 PM Kenneth Sloan <kennethrsloan@gmail.com>
wrote:
> Jumping in the middle here, but...
>
> This is an old problem. I wrote several papers on this in the previous
> century. A seminal paper is by Fuchs, Kedem & Uselton (CACM, perhaps Nov.
> 1977). You can find a few small conference papers with my name on them -
> and one major paper that handled all sorts of stuff you probably con't care
> about. Start here:
> https://scholar.google.com/citations?view_op=view_citation&hl=en&user=elhUt8QAAAAJ&citation_for_view=elhUt8QAAAAJ:u-x6o8ySG0sC
>
> Most of what you need is in the references found there.
>
> A lot depends on your assumptions, and how much attention you want to pay
> to "features" in the two shapes.
>
> When faced with a new instance of this problem, I usually start with a
> simple method:
>
> a) find one "obvious" match between a point on A and a point on B
> b) normalize the two 2D curves to have length 1.0, with both 0.0 and 1.0
> at the
> matching points found in a)
> c) connect a point on A to the point on B which is closest in normalized
> arc length
>
> This method does a better job of handling non-convex shapes than the
> method you seem to be using here (also an old, well-known, method).
>
> As a classic example of how assumptions matter, consider two shapes which
> are both perfect circles, with one small bump - but the bump is rotated by
> 30 degrees in A compared with the orientation in B.
> Do you want the resulting shape to have a single bump in A which
> disappears as you move to B, while a different bump appears? Or, to you
> want a cylinder with a smaller cylinder wrapped around it?
>
> In your example, suppose you have 2 5-pointed stars, but they are rotated
> slightly with respect to each other. Do you want the points of the stars
> to connect? or not?
>
> And so on...
>
>
>
> --
> Kenneth Sloan
> KennethRSloan@gmail.com
> Vision is the art of seeing what is invisible to others.
>
>
>
>
>
> On Jan 21, 2023, at 21:09, Sanjeev Prabhakar <sprabhakar2006@gmail.com>
> wrote:
>
> for nearest points mapping center of the 2 sections should almost match in
> case of convex shapes
>
> arc lengths i think is a very complicated idea.
>
> here is an example of 2 concave shapes joined with points with approach 2
> mentioned in my previous post.
>
> <Screenshot 2023-01-22 at 8.24.24 AM.png>
>
> this is made by intersection of 720 rays and around 100 slices
> execution time is 1.5 sec in python, i dont know how long will it take in
> pure openscad code.
>
> On Sun, 22 Jan 2023 at 07:47, Adrian Mariano <avm4@cornell.edu> wrote:
>
>> I think you need to think carefully and define what you mean by "nearest
>> point mapping". It will NOT always work for convex shapes if by nearest
>> point you mean take one shape (one with more points) and map every point to
>> the nearest point. Trivial example: square in right half plane map to a
>> shape in the left half plane: all the points of the right hand shape map
>> to the single right-most point of the left hand shape. You don't get a
>> valid mapping.
>>
>> To make this concept rigorous you need to assure that you use all the
>> points of both shapes. I did this in my skin() method by looking for the
>> mapping that maps all points from the larger shape onto the points of the
>> smaller shape while assuring that every point in the smaller shape is
>> covered. But now you no longer have a simple concept like "nearest point"
>> to do the mapping. Instead a complicated optimization arises. This
>> optimization is solved in my skin() algorithm. But as I am saying, it's
>> complicated. When I started trying to write skin() I had no idea how
>> complicated it was going to end up being. This optimization produces great
>> results, I think, as long as the shapes are "discrete", like polygons with
>> few edges. If you want to map two curved shapes to each other, the results
>> are not great, and the run time also becomes uncomfortably long, since the
>> algorithm has O(N^3) run time.
>>
>> For your second concept, given two polygons located in 3-space, perhaps
>> not parallel to each other, how do you define the rays? I don't know how
>> to do that. I did devise a method maybe sort of like what you are
>> imagining that involves tangent planes. It produces reasonable results for
>> continuous shapes, though I think very often results that can also be
>> easily produced by other means.
>>
>> You are overlooking the case which I think tends to be best when a smooth
>> curves is involved: connect them by arc length. This in my experience,
>> often produces the best result. You have to somehow align them to decide
>> on the starting point. Then you resample them by arc length to have the
>> same number of points (or generate them that way) and then simply line up
>> the points. This can often handle a concave shape, depending on how
>> different the shapes are, and it tends to produce a nicer form than the
>> tangent plane method. Depending on how you line things up you may get a
>> twist---which could be a desirable outcome.
>>
>> On Sat, Jan 21, 2023 at 8:50 PM Sanjeev Prabhakar <
>> sprabhakar2006@gmail.com> wrote:
>>
>>> I think
>>> a. if both the sections are convex the nearest point mapping
>>> approach should work
>>>
>>> b. if one section is convex and the other section is concave again the
>>> first approach should work where concave shape should be the primary one
>>>
>>> c. when both the shapes are concave the 2nd approach should be used
>>>
>>> when the shape is so concave like an "S" shape, I have a feeling that it
>>> would be extremely difficult or may be impossible to match without
>>> intersecting lines. You can still do it by matching the number of points,
>>> but it may not make any sense of the shape.
>>>
>>>
>>>
>>> On Sun, 22 Jan 2023 at 06:58, Adrian Mariano <avm4@cornell.edu> wrote:
>>>
>>>> The first approach to me looks much better, but you need to add a bunch
>>>> of horizontal slices to correctly capture the curvature of the faces. As
>>>> shown you have faces that are not coplanar.
>>>>
>>>> I personally do not like the look of the second approach, where an edge
>>>> is split. Personal preference. But also, I think this model is bad
>>>> because it has lots of very long skinny triangles. You can model more
>>>> efficiently and the result is better, in my opinion, when the triangles are
>>>> as close to equilateral as possible. Models like the above produce moire
>>>> effects and can be hard to view, and if you decrease the triangle count,
>>>> you get rippling across the surfaces. The rippling never goes away---just
>>>> gets smaller as you shrink the triangles. A horizontal section of such a
>>>> model will show zig-zag edges.
>>>>
>>>> But I guess the question is what point are you trying to make? Rogier
>>>> suggested we should have a built-in OpenSCAD module that does things like
>>>> this (maybe?). Another poster suggested joining convex shapes using convex
>>>> hulls of cones as a claim that the desired feature already can be
>>>> implemented partially. I have argued that a full implementation is complex
>>>> because there are multiple way to align shapes and no single correct way,
>>>> so you need different algorithms for alignment. I don't see any evidence
>>>> to the contrary shown here. My point is not that the problem cannot be
>>>> solved in many interesting and useful cases---I have done it. My point is
>>>> that the problem is complicated, and it cannot be solved in all cases, so
>>>> that makes a built-in seem unlikely to occur. Furthermore, a solution is
>>>> necessarily complex in terms of its interface, since there are several ways
>>>> we can imagine aligning points. This also makes a built-in seem unlikely.
>>>>
>>>> We can do lots of nice things with existing libraries and without a
>>>> built in, though of course there is the limitation due to the inability to
>>>> extract geometrical data from OpenSCAD objects. *THAT* may actually be
>>>> fixed in a future version, so that seems like the path forward towards a
>>>> generic solution to this kind of model that can work on geometry instead of
>>>> path lists.
>>>>
>>>>
>>>> On Sat, Jan 21, 2023 at 8:10 PM Sanjeev Prabhakar <
>>>> sprabhakar2006@gmail.com> wrote:
>>>>
>>>>> nearest point approach will be produce this result:
>>>>> <Screenshot 2023-01-22 at 6.32.31 AM.png>
>>>>>
>>>>>
>>>>> rays emanating from center and intersection approach will produce this
>>>>> result:
>>>>> <Screenshot 2023-01-22 at 6.35.04 AM.png>
>>>>>
>>>>> in the 2nd approach 360 lines were intersected in the example.
>>>>> morelines will produce much refined results and should work in most of the
>>>>> cases
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> On Sun, 22 Jan 2023 at 05:41, Adrian Mariano <avm4@cornell.edu> wrote:
>>>>>
>>>>>> It is possible to write a generic extruder for the convex case using
>>>>>> cones, but there are a couple things that limit this. For most
>>>>>> interesting cases, you need many slices to produce the correct form and to
>>>>>> avoid producing artifacts on the curved faces that arise. (See Jordan's
>>>>>> example.) Where will these slices come from? Note that even with convex
>>>>>> endcaps, the resulting shape need not be convex. You will need the point
>>>>>> list of the data in order to produce the many needed slices, most likely,
>>>>>> since no mechanism for "averaging" geometry exists. Given that you have a
>>>>>> point list, simply computing the desired shape as a polyhedron is much more
>>>>>> efficient than computing it as the union of 100 overlapping cones. The
>>>>>> version I implemented (convex_offset_extrude in BOSL2) flips the cones
>>>>>> around to handle the ends, extrema, whether the shape is increasing or
>>>>>> decreasing. This all requires access to the actual point list.
>>>>>>
>>>>>> Note that the direct computation of the polyhedron also already
>>>>>> exists in libraries (it's also here now).
>>>>>>
>>>>>> Many examples can be seen here (though the animated examples look
>>>>>> really bad right now for some reason):
>>>>>>
>>>>>> https://github.com/revarbat/BOSL2/wiki/skin.scad#functionmodule-skin
>>>>>>
>>>>>> On Sat, Jan 21, 2023 at 5:27 PM nop head <nop.head@gmail.com> wrote:
>>>>>>
>>>>>>> The points of the cones can be very close to the base so they are
>>>>>>> close to being a flat disk. As long as they are inside the hull they get
>>>>>>> discarded.
>>>>>>>
>>>>>>> On Sat, 21 Jan 2023 at 22:11, Jordan Brown <
>>>>>>> openscad@jordan.maileater.net> wrote:
>>>>>>>
>>>>>>>> On 1/21/2023 1:24 PM, Steve Lelievre wrote:
>>>>>>>>
>>>>>>>> I like the cones because they only involve the one perimeter at the
>>>>>>>> wide end so the shape produced is completely 'correct' in geometrical terms.
>>>>>>>>
>>>>>>>>
>>>>>>>> OK, thanks.
>>>>>>>>
>>>>>>>> Do note that it only works if the two are aligned so that the
>>>>>>>> points of the cones fall inside the other end's polygon.
>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> OpenSCAD mailing list
>>>>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> OpenSCAD mailing list
>>>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>>>
>>>>>> _______________________________________________
>>>>>> OpenSCAD mailing list
>>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>>
>>>>> _______________________________________________
>>>>> OpenSCAD mailing list
>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>
>>>> _______________________________________________
>>>> OpenSCAD mailing list
>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>
>>> _______________________________________________
>>> OpenSCAD mailing list
>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>
>> _______________________________________________
>> OpenSCAD mailing list
>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>
>
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>
SP
Sanjeev Prabhakar
Sun, Jan 22, 2023 4:19 AM
you can give it a try with these 2 sections
sec1=[[-4.495801703898594, -4.793470460340294],
[-4.491151273898594, -4.8897992103402945],
[-4.477243243898593, -4.985232020340295],
[-4.454206973898594, -5.078881280340294],
[-4.4222567138985935, -5.1698759803402945],
[-4.381689633898594, -5.257369780340294],
[-4.332883033898594, -5.340548930340295],
[-4.276290863898594, -5.418639780340294],
[-4.212439473898594, -5.490916020340294],
[-4.1419227438985935, -5.556705420340294],
[-4.0653965438985935, -5.615396080340294],
[-3.983572613898594, -5.666442130340294],
[-3.897212003898594, -5.709368800340294],
[-3.807117933898594, -5.743776840340295],
[-3.7141283538985936, -5.769346210340294],
[-3.6191081538985936, -5.7858391003402945],
[-3.522941103898594, -5.793102120340294],
[-3.426521623898594, -5.791067710340294],
[-3.330746513898594, -5.779754790340294],
[-3.236506553898594, -5.7592685903402945],
[-3.1446782638985935, -5.729799640340294],
[2.647916176101406, -3.557576720340294],
[2.730557566101406, -3.5251837603402945],
[2.812204456101406, -3.4903600703402944],
[2.892785356101406, -3.4531361403402943],
[2.972229746101406, -3.4135445603402945],
[3.0504680561014066, -3.371619980340294],
[3.1274318061014066, -3.3273991203402944],
[3.203053616101406, -3.2809206803402944],
[3.277267286101406, -3.2322253503402942],
[3.3500078361014065, -3.181355770340294],
[3.421211606101406, -3.1283564503402945],
[3.4908162461014065, -3.0732738103402943],
[3.5587608261014063, -3.016156060340294],
[3.624985876101406, -2.9570532103402942],
[3.689433396101406, -2.8960170003402945],
[3.752046986101406, -2.833100850340294],
[3.8127718361014056, -2.7683598503402944],
[3.871554766101407, -2.7018506703402942],
[3.9283443261014055, -2.6336315503402945],
[3.983090806101406, -2.5637621903402943],
[4.035746266101406, -2.4923037703402944],
[7.374742446101407, 2.182290879659705],
[7.433412916101406, 2.2747434696597058],
[7.481623516101407, 2.373056459659706],
[7.518796226101407, 2.4760510996597063],
[7.544485336101407, 2.582492509659705],
[7.5583828661014065, 2.691104499659705],
[7.560322176101406, 2.800584839659706],
[7.5502800061014055, 2.9096208896597062],
[7.528376776101406, 3.016905349659705],
[7.494875086101406, 3.121151899659706],
[7.450176616101406, 3.221110649659705],
[7.394817286101406, 3.315583139659706],
[7.329460846101406, 3.4034366596597057],
[7.254890886101406, 3.483617869659705],
[7.172001496101406, 3.5551654396597065],
[7.0817864761014055, 3.6172215096597053],
[6.985327496101406, 3.669042069659705],
[6.883781056101406, 3.7100057896597054],
[6.778364676101407, 3.739621529659706],
[6.670342256101406, 3.7575342196597052],
[6.561008976101406, 3.7635290696597057],
[2.065753106101406, 3.7635290696597057],
[1.9332684261014066, 3.767921809659706],
[1.8013657161014063, 3.7810809996597055],
[1.6706244161014059, 3.802948819659706],
[1.5416188661014063, 3.8334292296597052],
[1.414915756101406, 3.8723883196597058],
[1.2910716761014065, 3.919654949659705],
[1.170630676101406, 3.9750214796597056],
[1.0541218161014063, 4.038244689659706],
[0.9420569161014063, 4.109046859659706],
[0.8349282661014064, 4.187116959659706],
[0.7332064561014064, 4.2721120396597065],
[0.6373383561014059, 4.363658719659705],
[0.5477450861014059, 4.461354849659706],
[0.46482021610140656, 4.5647712696597065],
[0.38892803610140625, 4.673453669659706],
[0.3204019261014066, 4.786924639659706],
[0.25954290610140607, 4.904685709659706],
[0.20661832610140607, 5.026219559659706],
[0.1618606861014058, 5.150992319659705],
[0.12546659610140587, 5.278455879659706],
[-2.525659203898594, 15.882959069659707],
[-2.5708201838985936, 16.020435529659707],
[-2.635349623898594, 16.149954809659704],
[-2.717896313898594, 16.268804859659703],
[-2.816731793898594, 16.37449704965971],
[-2.929786513898594, 16.464818259659708],
[-3.0546931938985935, 16.537877219659705],
[-3.188836373898594, 16.59214413965971],
[-3.329407193898594, 16.626482709659705],
[-3.4734621938985937, 16.640173889659707],
[-3.6179849638985937, 16.632930999659706],
[-3.759949313898594, 16.604905709659704],
[-3.896382583898594, 16.556684849659703],
[-4.024427983898594, 16.48927811965971],
[-4.141404323898594, 16.404096969659705],
[-4.2448622038985935, 16.302925039659705],
[-4.332635283898594, 16.18788079965971],
[-4.402885663898593, 16.061373189659705],
[-4.454142343898594, 15.926051189659704],
[-4.485332053898594, 15.784748349659706],
[-4.495801703898594, 15.640423439659704]];
sec2=[[7.0, 0.0],
[2.831566164617248, 2.057227810745548],
[2.163118960624632, 6.657395614066075],
[-1.081537849349347, 3.3286978070012516],
[-5.663118960624631, 4.114496766047313],
[-3.4999933156346077, 2.0572258463413817e-05],
[-5.663118960624632, -4.114496766047311],
[-1.0815769801102797, -3.3286850926462956],
[2.1631189606246304, -6.6573956140660755],
[2.831541980476986, -2.0572610973589676]]
[image: Screenshot 2023-01-22 at 9.37.59 AM.png]
On Sun, 22 Jan 2023 at 09:34, Adrian Mariano avm4@cornell.edu wrote:
So anybody who didn't believe me that the problem is complicated can read
the paper, which is 31 pages long.
I just briefly skimmed over it to see what was in there, and it looks like
the majority is focused on the problem of "correspondence" and "branching"
which both have to do with the case of multiple contours mapping to single
contours. I completely ignored this case, but presumably an OpenSCAD
built-in would need to address it. So I only tried to address the "tiling"
problem, which I thought was hard enough, especially within OpenSCAD. Fig
2 looks like a diagram I drew when devising my approach. My method is a
global optimization over all the mappings of the vertices from the first
contour to the second. If f maps a vertex from C1 to C2 then I minimize
the sum over all v in C1 of d(v,f(v)), where d() is Euclidean distance.
The method you propose is exactly what I was referring to as the arc
length method, and I agree that it will generally produce a good result for
mappings between continuous curves. But for shapes with corners, I think
usually you want to map the corners to each other somehow---at least I
think that looks better, in the absence of any guidance from details of the
application.
On Sat, Jan 21, 2023 at 10:29 PM Kenneth Sloan kennethrsloan@gmail.com
wrote:
Jumping in the middle here, but...
This is an old problem. I wrote several papers on this in the previous
century. A seminal paper is by Fuchs, Kedem & Uselton (CACM, perhaps Nov.
1977). You can find a few small conference papers with my name on them -
and one major paper that handled all sorts of stuff you probably con't care
about. Start here:
https://scholar.google.com/citations?view_op=view_citation&hl=en&user=elhUt8QAAAAJ&citation_for_view=elhUt8QAAAAJ:u-x6o8ySG0sC
Most of what you need is in the references found there.
A lot depends on your assumptions, and how much attention you want to pay
to "features" in the two shapes.
When faced with a new instance of this problem, I usually start with a
simple method:
a) find one "obvious" match between a point on A and a point on B
b) normalize the two 2D curves to have length 1.0, with both 0.0 and 1.0
at the
matching points found in a)
c) connect a point on A to the point on B which is closest in normalized
arc length
This method does a better job of handling non-convex shapes than the
method you seem to be using here (also an old, well-known, method).
As a classic example of how assumptions matter, consider two shapes which
are both perfect circles, with one small bump - but the bump is rotated by
30 degrees in A compared with the orientation in B.
Do you want the resulting shape to have a single bump in A which
disappears as you move to B, while a different bump appears? Or, to you
want a cylinder with a smaller cylinder wrapped around it?
In your example, suppose you have 2 5-pointed stars, but they are rotated
slightly with respect to each other. Do you want the points of the stars
to connect? or not?
And so on...
--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.
On Jan 21, 2023, at 21:09, Sanjeev Prabhakar sprabhakar2006@gmail.com
wrote:
for nearest points mapping center of the 2 sections should almost match
in case of convex shapes
arc lengths i think is a very complicated idea.
here is an example of 2 concave shapes joined with points with approach 2
mentioned in my previous post.
<Screenshot 2023-01-22 at 8.24.24 AM.png>
this is made by intersection of 720 rays and around 100 slices
execution time is 1.5 sec in python, i dont know how long will it take in
pure openscad code.
On Sun, 22 Jan 2023 at 07:47, Adrian Mariano avm4@cornell.edu wrote:
I think you need to think carefully and define what you mean by "nearest
point mapping". It will NOT always work for convex shapes if by nearest
point you mean take one shape (one with more points) and map every point to
the nearest point. Trivial example: square in right half plane map to a
shape in the left half plane: all the points of the right hand shape map
to the single right-most point of the left hand shape. You don't get a
valid mapping.
To make this concept rigorous you need to assure that you use all the
points of both shapes. I did this in my skin() method by looking for the
mapping that maps all points from the larger shape onto the points of the
smaller shape while assuring that every point in the smaller shape is
covered. But now you no longer have a simple concept like "nearest point"
to do the mapping. Instead a complicated optimization arises. This
optimization is solved in my skin() algorithm. But as I am saying, it's
complicated. When I started trying to write skin() I had no idea how
complicated it was going to end up being. This optimization produces great
results, I think, as long as the shapes are "discrete", like polygons with
few edges. If you want to map two curved shapes to each other, the results
are not great, and the run time also becomes uncomfortably long, since the
algorithm has O(N^3) run time.
For your second concept, given two polygons located in 3-space, perhaps
not parallel to each other, how do you define the rays? I don't know how
to do that. I did devise a method maybe sort of like what you are
imagining that involves tangent planes. It produces reasonable results for
continuous shapes, though I think very often results that can also be
easily produced by other means.
You are overlooking the case which I think tends to be best when a
smooth curves is involved: connect them by arc length. This in my
experience, often produces the best result. You have to somehow align them
to decide on the starting point. Then you resample them by arc length to
have the same number of points (or generate them that way) and then simply
line up the points. This can often handle a concave shape, depending on
how different the shapes are, and it tends to produce a nicer form than the
tangent plane method. Depending on how you line things up you may get a
twist---which could be a desirable outcome.
On Sat, Jan 21, 2023 at 8:50 PM Sanjeev Prabhakar <
sprabhakar2006@gmail.com> wrote:
I think
a. if both the sections are convex the nearest point mapping
approach should work
b. if one section is convex and the other section is concave again the
first approach should work where concave shape should be the primary one
c. when both the shapes are concave the 2nd approach should be used
when the shape is so concave like an "S" shape, I have a feeling that
it would be extremely difficult or may be impossible to match without
intersecting lines. You can still do it by matching the number of points,
but it may not make any sense of the shape.
On Sun, 22 Jan 2023 at 06:58, Adrian Mariano avm4@cornell.edu wrote:
The first approach to me looks much better, but you need to add a
bunch of horizontal slices to correctly capture the curvature of the
faces. As shown you have faces that are not coplanar.
I personally do not like the look of the second approach, where an
edge is split. Personal preference. But also, I think this model is bad
because it has lots of very long skinny triangles. You can model more
efficiently and the result is better, in my opinion, when the triangles are
as close to equilateral as possible. Models like the above produce moire
effects and can be hard to view, and if you decrease the triangle count,
you get rippling across the surfaces. The rippling never goes away---just
gets smaller as you shrink the triangles. A horizontal section of such a
model will show zig-zag edges.
But I guess the question is what point are you trying to make? Rogier
suggested we should have a built-in OpenSCAD module that does things like
this (maybe?). Another poster suggested joining convex shapes using convex
hulls of cones as a claim that the desired feature already can be
implemented partially. I have argued that a full implementation is complex
because there are multiple way to align shapes and no single correct way,
so you need different algorithms for alignment. I don't see any evidence
to the contrary shown here. My point is not that the problem cannot be
solved in many interesting and useful cases---I have done it. My point is
that the problem is complicated, and it cannot be solved in all cases, so
that makes a built-in seem unlikely to occur. Furthermore, a solution is
necessarily complex in terms of its interface, since there are several ways
we can imagine aligning points. This also makes a built-in seem unlikely.
We can do lots of nice things with existing libraries and without a
built in, though of course there is the limitation due to the inability to
extract geometrical data from OpenSCAD objects. THAT may actually be
fixed in a future version, so that seems like the path forward towards a
generic solution to this kind of model that can work on geometry instead of
path lists.
On Sat, Jan 21, 2023 at 8:10 PM Sanjeev Prabhakar <
sprabhakar2006@gmail.com> wrote:
nearest point approach will be produce this result:
<Screenshot 2023-01-22 at 6.32.31 AM.png>
rays emanating from center and intersection approach will produce
this result:
<Screenshot 2023-01-22 at 6.35.04 AM.png>
in the 2nd approach 360 lines were intersected in the example.
morelines will produce much refined results and should work in most of the
cases
On Sun, 22 Jan 2023 at 05:41, Adrian Mariano avm4@cornell.edu
wrote:
It is possible to write a generic extruder for the convex case using
cones, but there are a couple things that limit this. For most
interesting cases, you need many slices to produce the correct form and to
avoid producing artifacts on the curved faces that arise. (See Jordan's
example.) Where will these slices come from? Note that even with convex
endcaps, the resulting shape need not be convex. You will need the point
list of the data in order to produce the many needed slices, most likely,
since no mechanism for "averaging" geometry exists. Given that you have a
point list, simply computing the desired shape as a polyhedron is much more
efficient than computing it as the union of 100 overlapping cones. The
version I implemented (convex_offset_extrude in BOSL2) flips the cones
around to handle the ends, extrema, whether the shape is increasing or
decreasing. This all requires access to the actual point list.
Note that the direct computation of the polyhedron also already
exists in libraries (it's also here now).
Many examples can be seen here (though the animated examples look
really bad right now for some reason):
https://github.com/revarbat/BOSL2/wiki/skin.scad#functionmodule-skin
On Sat, Jan 21, 2023 at 5:27 PM nop head nop.head@gmail.com wrote:
The points of the cones can be very close to the base so they are
close to being a flat disk. As long as they are inside the hull they get
discarded.
On Sat, 21 Jan 2023 at 22:11, Jordan Brown <
openscad@jordan.maileater.net> wrote:
On 1/21/2023 1:24 PM, Steve Lelievre wrote:
I like the cones because they only involve the one perimeter at
the wide end so the shape produced is completely 'correct' in geometrical
terms.
OK, thanks.
Do note that it only works if the two are aligned so that the
points of the cones fall inside the other end's polygon.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
you can give it a try with these 2 sections
sec1=[[-4.495801703898594, -4.793470460340294],
[-4.491151273898594, -4.8897992103402945],
[-4.477243243898593, -4.985232020340295],
[-4.454206973898594, -5.078881280340294],
[-4.4222567138985935, -5.1698759803402945],
[-4.381689633898594, -5.257369780340294],
[-4.332883033898594, -5.340548930340295],
[-4.276290863898594, -5.418639780340294],
[-4.212439473898594, -5.490916020340294],
[-4.1419227438985935, -5.556705420340294],
[-4.0653965438985935, -5.615396080340294],
[-3.983572613898594, -5.666442130340294],
[-3.897212003898594, -5.709368800340294],
[-3.807117933898594, -5.743776840340295],
[-3.7141283538985936, -5.769346210340294],
[-3.6191081538985936, -5.7858391003402945],
[-3.522941103898594, -5.793102120340294],
[-3.426521623898594, -5.791067710340294],
[-3.330746513898594, -5.779754790340294],
[-3.236506553898594, -5.7592685903402945],
[-3.1446782638985935, -5.729799640340294],
[2.647916176101406, -3.557576720340294],
[2.730557566101406, -3.5251837603402945],
[2.812204456101406, -3.4903600703402944],
[2.892785356101406, -3.4531361403402943],
[2.972229746101406, -3.4135445603402945],
[3.0504680561014066, -3.371619980340294],
[3.1274318061014066, -3.3273991203402944],
[3.203053616101406, -3.2809206803402944],
[3.277267286101406, -3.2322253503402942],
[3.3500078361014065, -3.181355770340294],
[3.421211606101406, -3.1283564503402945],
[3.4908162461014065, -3.0732738103402943],
[3.5587608261014063, -3.016156060340294],
[3.624985876101406, -2.9570532103402942],
[3.689433396101406, -2.8960170003402945],
[3.752046986101406, -2.833100850340294],
[3.8127718361014056, -2.7683598503402944],
[3.871554766101407, -2.7018506703402942],
[3.9283443261014055, -2.6336315503402945],
[3.983090806101406, -2.5637621903402943],
[4.035746266101406, -2.4923037703402944],
[7.374742446101407, 2.182290879659705],
[7.433412916101406, 2.2747434696597058],
[7.481623516101407, 2.373056459659706],
[7.518796226101407, 2.4760510996597063],
[7.544485336101407, 2.582492509659705],
[7.5583828661014065, 2.691104499659705],
[7.560322176101406, 2.800584839659706],
[7.5502800061014055, 2.9096208896597062],
[7.528376776101406, 3.016905349659705],
[7.494875086101406, 3.121151899659706],
[7.450176616101406, 3.221110649659705],
[7.394817286101406, 3.315583139659706],
[7.329460846101406, 3.4034366596597057],
[7.254890886101406, 3.483617869659705],
[7.172001496101406, 3.5551654396597065],
[7.0817864761014055, 3.6172215096597053],
[6.985327496101406, 3.669042069659705],
[6.883781056101406, 3.7100057896597054],
[6.778364676101407, 3.739621529659706],
[6.670342256101406, 3.7575342196597052],
[6.561008976101406, 3.7635290696597057],
[2.065753106101406, 3.7635290696597057],
[1.9332684261014066, 3.767921809659706],
[1.8013657161014063, 3.7810809996597055],
[1.6706244161014059, 3.802948819659706],
[1.5416188661014063, 3.8334292296597052],
[1.414915756101406, 3.8723883196597058],
[1.2910716761014065, 3.919654949659705],
[1.170630676101406, 3.9750214796597056],
[1.0541218161014063, 4.038244689659706],
[0.9420569161014063, 4.109046859659706],
[0.8349282661014064, 4.187116959659706],
[0.7332064561014064, 4.2721120396597065],
[0.6373383561014059, 4.363658719659705],
[0.5477450861014059, 4.461354849659706],
[0.46482021610140656, 4.5647712696597065],
[0.38892803610140625, 4.673453669659706],
[0.3204019261014066, 4.786924639659706],
[0.25954290610140607, 4.904685709659706],
[0.20661832610140607, 5.026219559659706],
[0.1618606861014058, 5.150992319659705],
[0.12546659610140587, 5.278455879659706],
[-2.525659203898594, 15.882959069659707],
[-2.5708201838985936, 16.020435529659707],
[-2.635349623898594, 16.149954809659704],
[-2.717896313898594, 16.268804859659703],
[-2.816731793898594, 16.37449704965971],
[-2.929786513898594, 16.464818259659708],
[-3.0546931938985935, 16.537877219659705],
[-3.188836373898594, 16.59214413965971],
[-3.329407193898594, 16.626482709659705],
[-3.4734621938985937, 16.640173889659707],
[-3.6179849638985937, 16.632930999659706],
[-3.759949313898594, 16.604905709659704],
[-3.896382583898594, 16.556684849659703],
[-4.024427983898594, 16.48927811965971],
[-4.141404323898594, 16.404096969659705],
[-4.2448622038985935, 16.302925039659705],
[-4.332635283898594, 16.18788079965971],
[-4.402885663898593, 16.061373189659705],
[-4.454142343898594, 15.926051189659704],
[-4.485332053898594, 15.784748349659706],
[-4.495801703898594, 15.640423439659704]];
sec2=[[7.0, 0.0],
[2.831566164617248, 2.057227810745548],
[2.163118960624632, 6.657395614066075],
[-1.081537849349347, 3.3286978070012516],
[-5.663118960624631, 4.114496766047313],
[-3.4999933156346077, 2.0572258463413817e-05],
[-5.663118960624632, -4.114496766047311],
[-1.0815769801102797, -3.3286850926462956],
[2.1631189606246304, -6.6573956140660755],
[2.831541980476986, -2.0572610973589676]]
[image: Screenshot 2023-01-22 at 9.37.59 AM.png]
On Sun, 22 Jan 2023 at 09:34, Adrian Mariano <avm4@cornell.edu> wrote:
> So anybody who didn't believe me that the problem is complicated can read
> the paper, which is 31 pages long.
>
> I just briefly skimmed over it to see what was in there, and it looks like
> the majority is focused on the problem of "correspondence" and "branching"
> which both have to do with the case of multiple contours mapping to single
> contours. I completely ignored this case, but presumably an OpenSCAD
> built-in would need to address it. So I only tried to address the "tiling"
> problem, which I thought was hard enough, especially within OpenSCAD. Fig
> 2 looks like a diagram I drew when devising my approach. My method is a
> global optimization over all the mappings of the vertices from the first
> contour to the second. If f maps a vertex from C1 to C2 then I minimize
> the sum over all v in C1 of d(v,f(v)), where d() is Euclidean distance.
>
> The method you propose is exactly what I was referring to as the arc
> length method, and I agree that it will generally produce a good result for
> mappings between continuous curves. But for shapes with corners, I think
> usually you want to map the corners to each other somehow---at least I
> think that looks better, in the absence of any guidance from details of the
> application.
>
> On Sat, Jan 21, 2023 at 10:29 PM Kenneth Sloan <kennethrsloan@gmail.com>
> wrote:
>
>> Jumping in the middle here, but...
>>
>> This is an old problem. I wrote several papers on this in the previous
>> century. A seminal paper is by Fuchs, Kedem & Uselton (CACM, perhaps Nov.
>> 1977). You can find a few small conference papers with my name on them -
>> and one major paper that handled all sorts of stuff you probably con't care
>> about. Start here:
>> https://scholar.google.com/citations?view_op=view_citation&hl=en&user=elhUt8QAAAAJ&citation_for_view=elhUt8QAAAAJ:u-x6o8ySG0sC
>>
>> Most of what you need is in the references found there.
>>
>> A lot depends on your assumptions, and how much attention you want to pay
>> to "features" in the two shapes.
>>
>> When faced with a new instance of this problem, I usually start with a
>> simple method:
>>
>> a) find one "obvious" match between a point on A and a point on B
>> b) normalize the two 2D curves to have length 1.0, with both 0.0 and 1.0
>> at the
>> matching points found in a)
>> c) connect a point on A to the point on B which is closest in normalized
>> arc length
>>
>> This method does a better job of handling non-convex shapes than the
>> method you seem to be using here (also an old, well-known, method).
>>
>> As a classic example of how assumptions matter, consider two shapes which
>> are both perfect circles, with one small bump - but the bump is rotated by
>> 30 degrees in A compared with the orientation in B.
>> Do you want the resulting shape to have a single bump in A which
>> disappears as you move to B, while a different bump appears? Or, to you
>> want a cylinder with a smaller cylinder wrapped around it?
>>
>> In your example, suppose you have 2 5-pointed stars, but they are rotated
>> slightly with respect to each other. Do you want the points of the stars
>> to connect? or not?
>>
>> And so on...
>>
>>
>>
>> --
>> Kenneth Sloan
>> KennethRSloan@gmail.com
>> Vision is the art of seeing what is invisible to others.
>>
>>
>>
>>
>>
>> On Jan 21, 2023, at 21:09, Sanjeev Prabhakar <sprabhakar2006@gmail.com>
>> wrote:
>>
>> for nearest points mapping center of the 2 sections should almost match
>> in case of convex shapes
>>
>> arc lengths i think is a very complicated idea.
>>
>> here is an example of 2 concave shapes joined with points with approach 2
>> mentioned in my previous post.
>>
>> <Screenshot 2023-01-22 at 8.24.24 AM.png>
>>
>> this is made by intersection of 720 rays and around 100 slices
>> execution time is 1.5 sec in python, i dont know how long will it take in
>> pure openscad code.
>>
>> On Sun, 22 Jan 2023 at 07:47, Adrian Mariano <avm4@cornell.edu> wrote:
>>
>>> I think you need to think carefully and define what you mean by "nearest
>>> point mapping". It will NOT always work for convex shapes if by nearest
>>> point you mean take one shape (one with more points) and map every point to
>>> the nearest point. Trivial example: square in right half plane map to a
>>> shape in the left half plane: all the points of the right hand shape map
>>> to the single right-most point of the left hand shape. You don't get a
>>> valid mapping.
>>>
>>> To make this concept rigorous you need to assure that you use all the
>>> points of both shapes. I did this in my skin() method by looking for the
>>> mapping that maps all points from the larger shape onto the points of the
>>> smaller shape while assuring that every point in the smaller shape is
>>> covered. But now you no longer have a simple concept like "nearest point"
>>> to do the mapping. Instead a complicated optimization arises. This
>>> optimization is solved in my skin() algorithm. But as I am saying, it's
>>> complicated. When I started trying to write skin() I had no idea how
>>> complicated it was going to end up being. This optimization produces great
>>> results, I think, as long as the shapes are "discrete", like polygons with
>>> few edges. If you want to map two curved shapes to each other, the results
>>> are not great, and the run time also becomes uncomfortably long, since the
>>> algorithm has O(N^3) run time.
>>>
>>> For your second concept, given two polygons located in 3-space, perhaps
>>> not parallel to each other, how do you define the rays? I don't know how
>>> to do that. I did devise a method maybe sort of like what you are
>>> imagining that involves tangent planes. It produces reasonable results for
>>> continuous shapes, though I think very often results that can also be
>>> easily produced by other means.
>>>
>>> You are overlooking the case which I think tends to be best when a
>>> smooth curves is involved: connect them by arc length. This in my
>>> experience, often produces the best result. You have to somehow align them
>>> to decide on the starting point. Then you resample them by arc length to
>>> have the same number of points (or generate them that way) and then simply
>>> line up the points. This can often handle a concave shape, depending on
>>> how different the shapes are, and it tends to produce a nicer form than the
>>> tangent plane method. Depending on how you line things up you may get a
>>> twist---which could be a desirable outcome.
>>>
>>> On Sat, Jan 21, 2023 at 8:50 PM Sanjeev Prabhakar <
>>> sprabhakar2006@gmail.com> wrote:
>>>
>>>> I think
>>>> a. if both the sections are convex the nearest point mapping
>>>> approach should work
>>>>
>>>> b. if one section is convex and the other section is concave again the
>>>> first approach should work where concave shape should be the primary one
>>>>
>>>> c. when both the shapes are concave the 2nd approach should be used
>>>>
>>>> when the shape is so concave like an "S" shape, I have a feeling that
>>>> it would be extremely difficult or may be impossible to match without
>>>> intersecting lines. You can still do it by matching the number of points,
>>>> but it may not make any sense of the shape.
>>>>
>>>>
>>>>
>>>> On Sun, 22 Jan 2023 at 06:58, Adrian Mariano <avm4@cornell.edu> wrote:
>>>>
>>>>> The first approach to me looks much better, but you need to add a
>>>>> bunch of horizontal slices to correctly capture the curvature of the
>>>>> faces. As shown you have faces that are not coplanar.
>>>>>
>>>>> I personally do not like the look of the second approach, where an
>>>>> edge is split. Personal preference. But also, I think this model is bad
>>>>> because it has lots of very long skinny triangles. You can model more
>>>>> efficiently and the result is better, in my opinion, when the triangles are
>>>>> as close to equilateral as possible. Models like the above produce moire
>>>>> effects and can be hard to view, and if you decrease the triangle count,
>>>>> you get rippling across the surfaces. The rippling never goes away---just
>>>>> gets smaller as you shrink the triangles. A horizontal section of such a
>>>>> model will show zig-zag edges.
>>>>>
>>>>> But I guess the question is what point are you trying to make? Rogier
>>>>> suggested we should have a built-in OpenSCAD module that does things like
>>>>> this (maybe?). Another poster suggested joining convex shapes using convex
>>>>> hulls of cones as a claim that the desired feature already can be
>>>>> implemented partially. I have argued that a full implementation is complex
>>>>> because there are multiple way to align shapes and no single correct way,
>>>>> so you need different algorithms for alignment. I don't see any evidence
>>>>> to the contrary shown here. My point is not that the problem cannot be
>>>>> solved in many interesting and useful cases---I have done it. My point is
>>>>> that the problem is complicated, and it cannot be solved in all cases, so
>>>>> that makes a built-in seem unlikely to occur. Furthermore, a solution is
>>>>> necessarily complex in terms of its interface, since there are several ways
>>>>> we can imagine aligning points. This also makes a built-in seem unlikely.
>>>>>
>>>>> We can do lots of nice things with existing libraries and without a
>>>>> built in, though of course there is the limitation due to the inability to
>>>>> extract geometrical data from OpenSCAD objects. *THAT* may actually be
>>>>> fixed in a future version, so that seems like the path forward towards a
>>>>> generic solution to this kind of model that can work on geometry instead of
>>>>> path lists.
>>>>>
>>>>>
>>>>> On Sat, Jan 21, 2023 at 8:10 PM Sanjeev Prabhakar <
>>>>> sprabhakar2006@gmail.com> wrote:
>>>>>
>>>>>> nearest point approach will be produce this result:
>>>>>> <Screenshot 2023-01-22 at 6.32.31 AM.png>
>>>>>>
>>>>>>
>>>>>> rays emanating from center and intersection approach will produce
>>>>>> this result:
>>>>>> <Screenshot 2023-01-22 at 6.35.04 AM.png>
>>>>>>
>>>>>> in the 2nd approach 360 lines were intersected in the example.
>>>>>> morelines will produce much refined results and should work in most of the
>>>>>> cases
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Sun, 22 Jan 2023 at 05:41, Adrian Mariano <avm4@cornell.edu>
>>>>>> wrote:
>>>>>>
>>>>>>> It is possible to write a generic extruder for the convex case using
>>>>>>> cones, but there are a couple things that limit this. For most
>>>>>>> interesting cases, you need many slices to produce the correct form and to
>>>>>>> avoid producing artifacts on the curved faces that arise. (See Jordan's
>>>>>>> example.) Where will these slices come from? Note that even with convex
>>>>>>> endcaps, the resulting shape need not be convex. You will need the point
>>>>>>> list of the data in order to produce the many needed slices, most likely,
>>>>>>> since no mechanism for "averaging" geometry exists. Given that you have a
>>>>>>> point list, simply computing the desired shape as a polyhedron is much more
>>>>>>> efficient than computing it as the union of 100 overlapping cones. The
>>>>>>> version I implemented (convex_offset_extrude in BOSL2) flips the cones
>>>>>>> around to handle the ends, extrema, whether the shape is increasing or
>>>>>>> decreasing. This all requires access to the actual point list.
>>>>>>>
>>>>>>> Note that the direct computation of the polyhedron also already
>>>>>>> exists in libraries (it's also here now).
>>>>>>>
>>>>>>> Many examples can be seen here (though the animated examples look
>>>>>>> really bad right now for some reason):
>>>>>>>
>>>>>>> https://github.com/revarbat/BOSL2/wiki/skin.scad#functionmodule-skin
>>>>>>>
>>>>>>> On Sat, Jan 21, 2023 at 5:27 PM nop head <nop.head@gmail.com> wrote:
>>>>>>>
>>>>>>>> The points of the cones can be very close to the base so they are
>>>>>>>> close to being a flat disk. As long as they are inside the hull they get
>>>>>>>> discarded.
>>>>>>>>
>>>>>>>> On Sat, 21 Jan 2023 at 22:11, Jordan Brown <
>>>>>>>> openscad@jordan.maileater.net> wrote:
>>>>>>>>
>>>>>>>>> On 1/21/2023 1:24 PM, Steve Lelievre wrote:
>>>>>>>>>
>>>>>>>>> I like the cones because they only involve the one perimeter at
>>>>>>>>> the wide end so the shape produced is completely 'correct' in geometrical
>>>>>>>>> terms.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> OK, thanks.
>>>>>>>>>
>>>>>>>>> Do note that it only works if the two are aligned so that the
>>>>>>>>> points of the cones fall inside the other end's polygon.
>>>>>>>>>
>>>>>>>>> _______________________________________________
>>>>>>>>> OpenSCAD mailing list
>>>>>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> OpenSCAD mailing list
>>>>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> OpenSCAD mailing list
>>>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>>>
>>>>>> _______________________________________________
>>>>>> OpenSCAD mailing list
>>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>>
>>>>> _______________________________________________
>>>>> OpenSCAD mailing list
>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>
>>>> _______________________________________________
>>>> OpenSCAD mailing list
>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>
>>> _______________________________________________
>>> OpenSCAD mailing list
>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>
>> _______________________________________________
>> OpenSCAD mailing list
>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>
>>
>> _______________________________________________
>> OpenSCAD mailing list
>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>
AM
Adrian Mariano
Sun, Jan 22, 2023 4:55 AM
As I have said, I think getting a good result, if it is possible, probably
requires manual alignment of the shapes. My best looking automatic output
is this:
[image: image.png]
and it is also not very good. Part of the problem is that the star has 10
vertices but the lower shape is a polygon with 5 vertices that have been
rounded. What needs to happen is the ten vertices of the star mapped to
the 5 vertices of the underlying shape, and then the rounded version mapped
so that the roundings to to their corresponding vertex. I imagine that
would give the best result. I don't think an automated method is likely to
find this result, though. This distance minimizer maps the concave bottom
rounding to an edge, which looks funny, but does OK with the point of the
star in front, which maps to a rounded corner.
I think I get a somewhat better result if I line the star up better with
the other shape. These results take about 8s to compute in OpenSCAD:
[image: image.png]
Another method in practice to get a nicer result is to compute more slices
in between, so the difference is not so big between successive contours.
Then you can apply your vision about how the shapes should map to each
other.
On Sat, Jan 21, 2023 at 11:20 PM Sanjeev Prabhakar sprabhakar2006@gmail.com
wrote:
you can give it a try with these 2 sections
sec1=[[-4.495801703898594, -4.793470460340294],
[-4.491151273898594, -4.8897992103402945],
[-4.477243243898593, -4.985232020340295],
[-4.454206973898594, -5.078881280340294],
[-4.4222567138985935, -5.1698759803402945],
[-4.381689633898594, -5.257369780340294],
[-4.332883033898594, -5.340548930340295],
[-4.276290863898594, -5.418639780340294],
[-4.212439473898594, -5.490916020340294],
[-4.1419227438985935, -5.556705420340294],
[-4.0653965438985935, -5.615396080340294],
[-3.983572613898594, -5.666442130340294],
[-3.897212003898594, -5.709368800340294],
[-3.807117933898594, -5.743776840340295],
[-3.7141283538985936, -5.769346210340294],
[-3.6191081538985936, -5.7858391003402945],
[-3.522941103898594, -5.793102120340294],
[-3.426521623898594, -5.791067710340294],
[-3.330746513898594, -5.779754790340294],
[-3.236506553898594, -5.7592685903402945],
[-3.1446782638985935, -5.729799640340294],
[2.647916176101406, -3.557576720340294],
[2.730557566101406, -3.5251837603402945],
[2.812204456101406, -3.4903600703402944],
[2.892785356101406, -3.4531361403402943],
[2.972229746101406, -3.4135445603402945],
[3.0504680561014066, -3.371619980340294],
[3.1274318061014066, -3.3273991203402944],
[3.203053616101406, -3.2809206803402944],
[3.277267286101406, -3.2322253503402942],
[3.3500078361014065, -3.181355770340294],
[3.421211606101406, -3.1283564503402945],
[3.4908162461014065, -3.0732738103402943],
[3.5587608261014063, -3.016156060340294],
[3.624985876101406, -2.9570532103402942],
[3.689433396101406, -2.8960170003402945],
[3.752046986101406, -2.833100850340294],
[3.8127718361014056, -2.7683598503402944],
[3.871554766101407, -2.7018506703402942],
[3.9283443261014055, -2.6336315503402945],
[3.983090806101406, -2.5637621903402943],
[4.035746266101406, -2.4923037703402944],
[7.374742446101407, 2.182290879659705],
[7.433412916101406, 2.2747434696597058],
[7.481623516101407, 2.373056459659706],
[7.518796226101407, 2.4760510996597063],
[7.544485336101407, 2.582492509659705],
[7.5583828661014065, 2.691104499659705],
[7.560322176101406, 2.800584839659706],
[7.5502800061014055, 2.9096208896597062],
[7.528376776101406, 3.016905349659705],
[7.494875086101406, 3.121151899659706],
[7.450176616101406, 3.221110649659705],
[7.394817286101406, 3.315583139659706],
[7.329460846101406, 3.4034366596597057],
[7.254890886101406, 3.483617869659705],
[7.172001496101406, 3.5551654396597065],
[7.0817864761014055, 3.6172215096597053],
[6.985327496101406, 3.669042069659705],
[6.883781056101406, 3.7100057896597054],
[6.778364676101407, 3.739621529659706],
[6.670342256101406, 3.7575342196597052],
[6.561008976101406, 3.7635290696597057],
[2.065753106101406, 3.7635290696597057],
[1.9332684261014066, 3.767921809659706],
[1.8013657161014063, 3.7810809996597055],
[1.6706244161014059, 3.802948819659706],
[1.5416188661014063, 3.8334292296597052],
[1.414915756101406, 3.8723883196597058],
[1.2910716761014065, 3.919654949659705],
[1.170630676101406, 3.9750214796597056],
[1.0541218161014063, 4.038244689659706],
[0.9420569161014063, 4.109046859659706],
[0.8349282661014064, 4.187116959659706],
[0.7332064561014064, 4.2721120396597065],
[0.6373383561014059, 4.363658719659705],
[0.5477450861014059, 4.461354849659706],
[0.46482021610140656, 4.5647712696597065],
[0.38892803610140625, 4.673453669659706],
[0.3204019261014066, 4.786924639659706],
[0.25954290610140607, 4.904685709659706],
[0.20661832610140607, 5.026219559659706],
[0.1618606861014058, 5.150992319659705],
[0.12546659610140587, 5.278455879659706],
[-2.525659203898594, 15.882959069659707],
[-2.5708201838985936, 16.020435529659707],
[-2.635349623898594, 16.149954809659704],
[-2.717896313898594, 16.268804859659703],
[-2.816731793898594, 16.37449704965971],
[-2.929786513898594, 16.464818259659708],
[-3.0546931938985935, 16.537877219659705],
[-3.188836373898594, 16.59214413965971],
[-3.329407193898594, 16.626482709659705],
[-3.4734621938985937, 16.640173889659707],
[-3.6179849638985937, 16.632930999659706],
[-3.759949313898594, 16.604905709659704],
[-3.896382583898594, 16.556684849659703],
[-4.024427983898594, 16.48927811965971],
[-4.141404323898594, 16.404096969659705],
[-4.2448622038985935, 16.302925039659705],
[-4.332635283898594, 16.18788079965971],
[-4.402885663898593, 16.061373189659705],
[-4.454142343898594, 15.926051189659704],
[-4.485332053898594, 15.784748349659706],
[-4.495801703898594, 15.640423439659704]];
sec2=[[7.0, 0.0],
[2.831566164617248, 2.057227810745548],
[2.163118960624632, 6.657395614066075],
[-1.081537849349347, 3.3286978070012516],
[-5.663118960624631, 4.114496766047313],
[-3.4999933156346077, 2.0572258463413817e-05],
[-5.663118960624632, -4.114496766047311],
[-1.0815769801102797, -3.3286850926462956],
[2.1631189606246304, -6.6573956140660755],
[2.831541980476986, -2.0572610973589676]]
[image: Screenshot 2023-01-22 at 9.37.59 AM.png]
On Sun, 22 Jan 2023 at 09:34, Adrian Mariano avm4@cornell.edu wrote:
So anybody who didn't believe me that the problem is complicated can read
the paper, which is 31 pages long.
I just briefly skimmed over it to see what was in there, and it looks
like the majority is focused on the problem of "correspondence" and
"branching" which both have to do with the case of multiple contours
mapping to single contours. I completely ignored this case, but presumably
an OpenSCAD built-in would need to address it. So I only tried to address
the "tiling" problem, which I thought was hard enough, especially within
OpenSCAD. Fig 2 looks like a diagram I drew when devising my approach. My
method is a global optimization over all the mappings of the vertices from
the first contour to the second. If f maps a vertex from C1 to C2 then I
minimize the sum over all v in C1 of d(v,f(v)), where d() is Euclidean
distance.
The method you propose is exactly what I was referring to as the arc
length method, and I agree that it will generally produce a good result for
mappings between continuous curves. But for shapes with corners, I think
usually you want to map the corners to each other somehow---at least I
think that looks better, in the absence of any guidance from details of the
application.
On Sat, Jan 21, 2023 at 10:29 PM Kenneth Sloan kennethrsloan@gmail.com
wrote:
Jumping in the middle here, but...
This is an old problem. I wrote several papers on this in the previous
century. A seminal paper is by Fuchs, Kedem & Uselton (CACM, perhaps Nov.
1977). You can find a few small conference papers with my name on them -
and one major paper that handled all sorts of stuff you probably con't care
about. Start here:
https://scholar.google.com/citations?view_op=view_citation&hl=en&user=elhUt8QAAAAJ&citation_for_view=elhUt8QAAAAJ:u-x6o8ySG0sC
Most of what you need is in the references found there.
A lot depends on your assumptions, and how much attention you want to
pay to "features" in the two shapes.
When faced with a new instance of this problem, I usually start with a
simple method:
a) find one "obvious" match between a point on A and a point on B
b) normalize the two 2D curves to have length 1.0, with both 0.0 and 1.0
at the
matching points found in a)
c) connect a point on A to the point on B which is closest in normalized
arc length
This method does a better job of handling non-convex shapes than the
method you seem to be using here (also an old, well-known, method).
As a classic example of how assumptions matter, consider two shapes
which are both perfect circles, with one small bump - but the bump is
rotated by 30 degrees in A compared with the orientation in B.
Do you want the resulting shape to have a single bump in A which
disappears as you move to B, while a different bump appears? Or, to you
want a cylinder with a smaller cylinder wrapped around it?
In your example, suppose you have 2 5-pointed stars, but they are
rotated slightly with respect to each other. Do you want the points of the
stars to connect? or not?
And so on...
--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.
On Jan 21, 2023, at 21:09, Sanjeev Prabhakar sprabhakar2006@gmail.com
wrote:
for nearest points mapping center of the 2 sections should almost match
in case of convex shapes
arc lengths i think is a very complicated idea.
here is an example of 2 concave shapes joined with points with approach
2 mentioned in my previous post.
<Screenshot 2023-01-22 at 8.24.24 AM.png>
this is made by intersection of 720 rays and around 100 slices
execution time is 1.5 sec in python, i dont know how long will it take
in pure openscad code.
On Sun, 22 Jan 2023 at 07:47, Adrian Mariano avm4@cornell.edu wrote:
I think you need to think carefully and define what you mean by
"nearest point mapping". It will NOT always work for convex shapes if by
nearest point you mean take one shape (one with more points) and map every
point to the nearest point. Trivial example: square in right half plane
map to a shape in the left half plane: all the points of the right hand
shape map to the single right-most point of the left hand shape. You don't
get a valid mapping.
To make this concept rigorous you need to assure that you use all the
points of both shapes. I did this in my skin() method by looking for the
mapping that maps all points from the larger shape onto the points of the
smaller shape while assuring that every point in the smaller shape is
covered. But now you no longer have a simple concept like "nearest point"
to do the mapping. Instead a complicated optimization arises. This
optimization is solved in my skin() algorithm. But as I am saying, it's
complicated. When I started trying to write skin() I had no idea how
complicated it was going to end up being. This optimization produces great
results, I think, as long as the shapes are "discrete", like polygons with
few edges. If you want to map two curved shapes to each other, the results
are not great, and the run time also becomes uncomfortably long, since the
algorithm has O(N^3) run time.
For your second concept, given two polygons located in 3-space, perhaps
not parallel to each other, how do you define the rays? I don't know how
to do that. I did devise a method maybe sort of like what you are
imagining that involves tangent planes. It produces reasonable results for
continuous shapes, though I think very often results that can also be
easily produced by other means.
You are overlooking the case which I think tends to be best when a
smooth curves is involved: connect them by arc length. This in my
experience, often produces the best result. You have to somehow align them
to decide on the starting point. Then you resample them by arc length to
have the same number of points (or generate them that way) and then simply
line up the points. This can often handle a concave shape, depending on
how different the shapes are, and it tends to produce a nicer form than the
tangent plane method. Depending on how you line things up you may get a
twist---which could be a desirable outcome.
On Sat, Jan 21, 2023 at 8:50 PM Sanjeev Prabhakar <
sprabhakar2006@gmail.com> wrote:
I think
a. if both the sections are convex the nearest point mapping
approach should work
b. if one section is convex and the other section is concave again the
first approach should work where concave shape should be the primary one
c. when both the shapes are concave the 2nd approach should be used
when the shape is so concave like an "S" shape, I have a feeling that
it would be extremely difficult or may be impossible to match without
intersecting lines. You can still do it by matching the number of points,
but it may not make any sense of the shape.
On Sun, 22 Jan 2023 at 06:58, Adrian Mariano avm4@cornell.edu wrote:
The first approach to me looks much better, but you need to add a
bunch of horizontal slices to correctly capture the curvature of the
faces. As shown you have faces that are not coplanar.
I personally do not like the look of the second approach, where an
edge is split. Personal preference. But also, I think this model is bad
because it has lots of very long skinny triangles. You can model more
efficiently and the result is better, in my opinion, when the triangles are
as close to equilateral as possible. Models like the above produce moire
effects and can be hard to view, and if you decrease the triangle count,
you get rippling across the surfaces. The rippling never goes away---just
gets smaller as you shrink the triangles. A horizontal section of such a
model will show zig-zag edges.
But I guess the question is what point are you trying to make?
Rogier suggested we should have a built-in OpenSCAD module that does things
like this (maybe?). Another poster suggested joining convex shapes using
convex hulls of cones as a claim that the desired feature already can be
implemented partially. I have argued that a full implementation is complex
because there are multiple way to align shapes and no single correct way,
so you need different algorithms for alignment. I don't see any evidence
to the contrary shown here. My point is not that the problem cannot be
solved in many interesting and useful cases---I have done it. My point is
that the problem is complicated, and it cannot be solved in all cases, so
that makes a built-in seem unlikely to occur. Furthermore, a solution is
necessarily complex in terms of its interface, since there are several ways
we can imagine aligning points. This also makes a built-in seem unlikely.
We can do lots of nice things with existing libraries and without a
built in, though of course there is the limitation due to the inability to
extract geometrical data from OpenSCAD objects. THAT may actually be
fixed in a future version, so that seems like the path forward towards a
generic solution to this kind of model that can work on geometry instead of
path lists.
On Sat, Jan 21, 2023 at 8:10 PM Sanjeev Prabhakar <
sprabhakar2006@gmail.com> wrote:
nearest point approach will be produce this result:
<Screenshot 2023-01-22 at 6.32.31 AM.png>
rays emanating from center and intersection approach will produce
this result:
<Screenshot 2023-01-22 at 6.35.04 AM.png>
in the 2nd approach 360 lines were intersected in the example.
morelines will produce much refined results and should work in most of the
cases
On Sun, 22 Jan 2023 at 05:41, Adrian Mariano avm4@cornell.edu
wrote:
It is possible to write a generic extruder for the convex case
using cones, but there are a couple things that limit this. For most
interesting cases, you need many slices to produce the correct form and to
avoid producing artifacts on the curved faces that arise. (See Jordan's
example.) Where will these slices come from? Note that even with convex
endcaps, the resulting shape need not be convex. You will need the point
list of the data in order to produce the many needed slices, most likely,
since no mechanism for "averaging" geometry exists. Given that you have a
point list, simply computing the desired shape as a polyhedron is much more
efficient than computing it as the union of 100 overlapping cones. The
version I implemented (convex_offset_extrude in BOSL2) flips the cones
around to handle the ends, extrema, whether the shape is increasing or
decreasing. This all requires access to the actual point list.
Note that the direct computation of the polyhedron also already
exists in libraries (it's also here now).
Many examples can be seen here (though the animated examples look
really bad right now for some reason):
https://github.com/revarbat/BOSL2/wiki/skin.scad#functionmodule-skin
On Sat, Jan 21, 2023 at 5:27 PM nop head nop.head@gmail.com
wrote:
The points of the cones can be very close to the base so they are
close to being a flat disk. As long as they are inside the hull they get
discarded.
On Sat, 21 Jan 2023 at 22:11, Jordan Brown <
openscad@jordan.maileater.net> wrote:
On 1/21/2023 1:24 PM, Steve Lelievre wrote:
I like the cones because they only involve the one perimeter at
the wide end so the shape produced is completely 'correct' in geometrical
terms.
OK, thanks.
Do note that it only works if the two are aligned so that the
points of the cones fall inside the other end's polygon.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
As I have said, I think getting a good result, if it is possible, probably
requires manual alignment of the shapes. My best looking automatic output
is this:
[image: image.png]
and it is also not very good. Part of the problem is that the star has 10
vertices but the lower shape is a polygon with 5 vertices that have been
rounded. What needs to happen is the ten vertices of the star mapped to
the 5 vertices of the underlying shape, and then the rounded version mapped
so that the roundings to to their corresponding vertex. I imagine that
would give the best result. I don't think an automated method is likely to
find this result, though. This distance minimizer maps the concave bottom
rounding to an edge, which looks funny, but does OK with the point of the
star in front, which maps to a rounded corner.
I think I get a somewhat better result if I line the star up better with
the other shape. These results take about 8s to compute in OpenSCAD:
[image: image.png]
Another method in practice to get a nicer result is to compute more slices
in between, so the difference is not so big between successive contours.
Then you can apply your vision about how the shapes should map to each
other.
On Sat, Jan 21, 2023 at 11:20 PM Sanjeev Prabhakar <sprabhakar2006@gmail.com>
wrote:
> you can give it a try with these 2 sections
>
> sec1=[[-4.495801703898594, -4.793470460340294],
>
> [-4.491151273898594, -4.8897992103402945],
> [-4.477243243898593, -4.985232020340295],
> [-4.454206973898594, -5.078881280340294],
> [-4.4222567138985935, -5.1698759803402945],
> [-4.381689633898594, -5.257369780340294],
> [-4.332883033898594, -5.340548930340295],
> [-4.276290863898594, -5.418639780340294],
> [-4.212439473898594, -5.490916020340294],
> [-4.1419227438985935, -5.556705420340294],
> [-4.0653965438985935, -5.615396080340294],
> [-3.983572613898594, -5.666442130340294],
> [-3.897212003898594, -5.709368800340294],
> [-3.807117933898594, -5.743776840340295],
> [-3.7141283538985936, -5.769346210340294],
> [-3.6191081538985936, -5.7858391003402945],
> [-3.522941103898594, -5.793102120340294],
> [-3.426521623898594, -5.791067710340294],
> [-3.330746513898594, -5.779754790340294],
> [-3.236506553898594, -5.7592685903402945],
> [-3.1446782638985935, -5.729799640340294],
> [2.647916176101406, -3.557576720340294],
> [2.730557566101406, -3.5251837603402945],
> [2.812204456101406, -3.4903600703402944],
> [2.892785356101406, -3.4531361403402943],
> [2.972229746101406, -3.4135445603402945],
> [3.0504680561014066, -3.371619980340294],
> [3.1274318061014066, -3.3273991203402944],
> [3.203053616101406, -3.2809206803402944],
> [3.277267286101406, -3.2322253503402942],
> [3.3500078361014065, -3.181355770340294],
> [3.421211606101406, -3.1283564503402945],
> [3.4908162461014065, -3.0732738103402943],
> [3.5587608261014063, -3.016156060340294],
> [3.624985876101406, -2.9570532103402942],
> [3.689433396101406, -2.8960170003402945],
> [3.752046986101406, -2.833100850340294],
> [3.8127718361014056, -2.7683598503402944],
> [3.871554766101407, -2.7018506703402942],
> [3.9283443261014055, -2.6336315503402945],
> [3.983090806101406, -2.5637621903402943],
> [4.035746266101406, -2.4923037703402944],
> [7.374742446101407, 2.182290879659705],
> [7.433412916101406, 2.2747434696597058],
> [7.481623516101407, 2.373056459659706],
> [7.518796226101407, 2.4760510996597063],
> [7.544485336101407, 2.582492509659705],
> [7.5583828661014065, 2.691104499659705],
> [7.560322176101406, 2.800584839659706],
> [7.5502800061014055, 2.9096208896597062],
> [7.528376776101406, 3.016905349659705],
> [7.494875086101406, 3.121151899659706],
> [7.450176616101406, 3.221110649659705],
> [7.394817286101406, 3.315583139659706],
> [7.329460846101406, 3.4034366596597057],
> [7.254890886101406, 3.483617869659705],
> [7.172001496101406, 3.5551654396597065],
> [7.0817864761014055, 3.6172215096597053],
> [6.985327496101406, 3.669042069659705],
> [6.883781056101406, 3.7100057896597054],
> [6.778364676101407, 3.739621529659706],
> [6.670342256101406, 3.7575342196597052],
> [6.561008976101406, 3.7635290696597057],
> [2.065753106101406, 3.7635290696597057],
> [1.9332684261014066, 3.767921809659706],
> [1.8013657161014063, 3.7810809996597055],
> [1.6706244161014059, 3.802948819659706],
> [1.5416188661014063, 3.8334292296597052],
> [1.414915756101406, 3.8723883196597058],
> [1.2910716761014065, 3.919654949659705],
> [1.170630676101406, 3.9750214796597056],
> [1.0541218161014063, 4.038244689659706],
> [0.9420569161014063, 4.109046859659706],
> [0.8349282661014064, 4.187116959659706],
> [0.7332064561014064, 4.2721120396597065],
> [0.6373383561014059, 4.363658719659705],
> [0.5477450861014059, 4.461354849659706],
> [0.46482021610140656, 4.5647712696597065],
> [0.38892803610140625, 4.673453669659706],
> [0.3204019261014066, 4.786924639659706],
> [0.25954290610140607, 4.904685709659706],
> [0.20661832610140607, 5.026219559659706],
> [0.1618606861014058, 5.150992319659705],
> [0.12546659610140587, 5.278455879659706],
> [-2.525659203898594, 15.882959069659707],
> [-2.5708201838985936, 16.020435529659707],
> [-2.635349623898594, 16.149954809659704],
> [-2.717896313898594, 16.268804859659703],
> [-2.816731793898594, 16.37449704965971],
> [-2.929786513898594, 16.464818259659708],
> [-3.0546931938985935, 16.537877219659705],
> [-3.188836373898594, 16.59214413965971],
> [-3.329407193898594, 16.626482709659705],
> [-3.4734621938985937, 16.640173889659707],
> [-3.6179849638985937, 16.632930999659706],
> [-3.759949313898594, 16.604905709659704],
> [-3.896382583898594, 16.556684849659703],
> [-4.024427983898594, 16.48927811965971],
> [-4.141404323898594, 16.404096969659705],
> [-4.2448622038985935, 16.302925039659705],
> [-4.332635283898594, 16.18788079965971],
> [-4.402885663898593, 16.061373189659705],
> [-4.454142343898594, 15.926051189659704],
> [-4.485332053898594, 15.784748349659706],
> [-4.495801703898594, 15.640423439659704]];
>
>
> sec2=[[7.0, 0.0],
>
> [2.831566164617248, 2.057227810745548],
> [2.163118960624632, 6.657395614066075],
> [-1.081537849349347, 3.3286978070012516],
> [-5.663118960624631, 4.114496766047313],
> [-3.4999933156346077, 2.0572258463413817e-05],
> [-5.663118960624632, -4.114496766047311],
> [-1.0815769801102797, -3.3286850926462956],
> [2.1631189606246304, -6.6573956140660755],
> [2.831541980476986, -2.0572610973589676]]
>
>
> [image: Screenshot 2023-01-22 at 9.37.59 AM.png]
>
>
>
>
> On Sun, 22 Jan 2023 at 09:34, Adrian Mariano <avm4@cornell.edu> wrote:
>
>> So anybody who didn't believe me that the problem is complicated can read
>> the paper, which is 31 pages long.
>>
>> I just briefly skimmed over it to see what was in there, and it looks
>> like the majority is focused on the problem of "correspondence" and
>> "branching" which both have to do with the case of multiple contours
>> mapping to single contours. I completely ignored this case, but presumably
>> an OpenSCAD built-in would need to address it. So I only tried to address
>> the "tiling" problem, which I thought was hard enough, especially within
>> OpenSCAD. Fig 2 looks like a diagram I drew when devising my approach. My
>> method is a global optimization over all the mappings of the vertices from
>> the first contour to the second. If f maps a vertex from C1 to C2 then I
>> minimize the sum over all v in C1 of d(v,f(v)), where d() is Euclidean
>> distance.
>>
>> The method you propose is exactly what I was referring to as the arc
>> length method, and I agree that it will generally produce a good result for
>> mappings between continuous curves. But for shapes with corners, I think
>> usually you want to map the corners to each other somehow---at least I
>> think that looks better, in the absence of any guidance from details of the
>> application.
>>
>> On Sat, Jan 21, 2023 at 10:29 PM Kenneth Sloan <kennethrsloan@gmail.com>
>> wrote:
>>
>>> Jumping in the middle here, but...
>>>
>>> This is an old problem. I wrote several papers on this in the previous
>>> century. A seminal paper is by Fuchs, Kedem & Uselton (CACM, perhaps Nov.
>>> 1977). You can find a few small conference papers with my name on them -
>>> and one major paper that handled all sorts of stuff you probably con't care
>>> about. Start here:
>>> https://scholar.google.com/citations?view_op=view_citation&hl=en&user=elhUt8QAAAAJ&citation_for_view=elhUt8QAAAAJ:u-x6o8ySG0sC
>>>
>>> Most of what you need is in the references found there.
>>>
>>> A lot depends on your assumptions, and how much attention you want to
>>> pay to "features" in the two shapes.
>>>
>>> When faced with a new instance of this problem, I usually start with a
>>> simple method:
>>>
>>> a) find one "obvious" match between a point on A and a point on B
>>> b) normalize the two 2D curves to have length 1.0, with both 0.0 and 1.0
>>> at the
>>> matching points found in a)
>>> c) connect a point on A to the point on B which is closest in normalized
>>> arc length
>>>
>>> This method does a better job of handling non-convex shapes than the
>>> method you seem to be using here (also an old, well-known, method).
>>>
>>> As a classic example of how assumptions matter, consider two shapes
>>> which are both perfect circles, with one small bump - but the bump is
>>> rotated by 30 degrees in A compared with the orientation in B.
>>> Do you want the resulting shape to have a single bump in A which
>>> disappears as you move to B, while a different bump appears? Or, to you
>>> want a cylinder with a smaller cylinder wrapped around it?
>>>
>>> In your example, suppose you have 2 5-pointed stars, but they are
>>> rotated slightly with respect to each other. Do you want the points of the
>>> stars to connect? or not?
>>>
>>> And so on...
>>>
>>>
>>>
>>> --
>>> Kenneth Sloan
>>> KennethRSloan@gmail.com
>>> Vision is the art of seeing what is invisible to others.
>>>
>>>
>>>
>>>
>>>
>>> On Jan 21, 2023, at 21:09, Sanjeev Prabhakar <sprabhakar2006@gmail.com>
>>> wrote:
>>>
>>> for nearest points mapping center of the 2 sections should almost match
>>> in case of convex shapes
>>>
>>> arc lengths i think is a very complicated idea.
>>>
>>> here is an example of 2 concave shapes joined with points with approach
>>> 2 mentioned in my previous post.
>>>
>>> <Screenshot 2023-01-22 at 8.24.24 AM.png>
>>>
>>> this is made by intersection of 720 rays and around 100 slices
>>> execution time is 1.5 sec in python, i dont know how long will it take
>>> in pure openscad code.
>>>
>>> On Sun, 22 Jan 2023 at 07:47, Adrian Mariano <avm4@cornell.edu> wrote:
>>>
>>>> I think you need to think carefully and define what you mean by
>>>> "nearest point mapping". It will NOT always work for convex shapes if by
>>>> nearest point you mean take one shape (one with more points) and map every
>>>> point to the nearest point. Trivial example: square in right half plane
>>>> map to a shape in the left half plane: all the points of the right hand
>>>> shape map to the single right-most point of the left hand shape. You don't
>>>> get a valid mapping.
>>>>
>>>> To make this concept rigorous you need to assure that you use all the
>>>> points of both shapes. I did this in my skin() method by looking for the
>>>> mapping that maps all points from the larger shape onto the points of the
>>>> smaller shape while assuring that every point in the smaller shape is
>>>> covered. But now you no longer have a simple concept like "nearest point"
>>>> to do the mapping. Instead a complicated optimization arises. This
>>>> optimization is solved in my skin() algorithm. But as I am saying, it's
>>>> complicated. When I started trying to write skin() I had no idea how
>>>> complicated it was going to end up being. This optimization produces great
>>>> results, I think, as long as the shapes are "discrete", like polygons with
>>>> few edges. If you want to map two curved shapes to each other, the results
>>>> are not great, and the run time also becomes uncomfortably long, since the
>>>> algorithm has O(N^3) run time.
>>>>
>>>> For your second concept, given two polygons located in 3-space, perhaps
>>>> not parallel to each other, how do you define the rays? I don't know how
>>>> to do that. I did devise a method maybe sort of like what you are
>>>> imagining that involves tangent planes. It produces reasonable results for
>>>> continuous shapes, though I think very often results that can also be
>>>> easily produced by other means.
>>>>
>>>> You are overlooking the case which I think tends to be best when a
>>>> smooth curves is involved: connect them by arc length. This in my
>>>> experience, often produces the best result. You have to somehow align them
>>>> to decide on the starting point. Then you resample them by arc length to
>>>> have the same number of points (or generate them that way) and then simply
>>>> line up the points. This can often handle a concave shape, depending on
>>>> how different the shapes are, and it tends to produce a nicer form than the
>>>> tangent plane method. Depending on how you line things up you may get a
>>>> twist---which could be a desirable outcome.
>>>>
>>>> On Sat, Jan 21, 2023 at 8:50 PM Sanjeev Prabhakar <
>>>> sprabhakar2006@gmail.com> wrote:
>>>>
>>>>> I think
>>>>> a. if both the sections are convex the nearest point mapping
>>>>> approach should work
>>>>>
>>>>> b. if one section is convex and the other section is concave again the
>>>>> first approach should work where concave shape should be the primary one
>>>>>
>>>>> c. when both the shapes are concave the 2nd approach should be used
>>>>>
>>>>> when the shape is so concave like an "S" shape, I have a feeling that
>>>>> it would be extremely difficult or may be impossible to match without
>>>>> intersecting lines. You can still do it by matching the number of points,
>>>>> but it may not make any sense of the shape.
>>>>>
>>>>>
>>>>>
>>>>> On Sun, 22 Jan 2023 at 06:58, Adrian Mariano <avm4@cornell.edu> wrote:
>>>>>
>>>>>> The first approach to me looks much better, but you need to add a
>>>>>> bunch of horizontal slices to correctly capture the curvature of the
>>>>>> faces. As shown you have faces that are not coplanar.
>>>>>>
>>>>>> I personally do not like the look of the second approach, where an
>>>>>> edge is split. Personal preference. But also, I think this model is bad
>>>>>> because it has lots of very long skinny triangles. You can model more
>>>>>> efficiently and the result is better, in my opinion, when the triangles are
>>>>>> as close to equilateral as possible. Models like the above produce moire
>>>>>> effects and can be hard to view, and if you decrease the triangle count,
>>>>>> you get rippling across the surfaces. The rippling never goes away---just
>>>>>> gets smaller as you shrink the triangles. A horizontal section of such a
>>>>>> model will show zig-zag edges.
>>>>>>
>>>>>> But I guess the question is what point are you trying to make?
>>>>>> Rogier suggested we should have a built-in OpenSCAD module that does things
>>>>>> like this (maybe?). Another poster suggested joining convex shapes using
>>>>>> convex hulls of cones as a claim that the desired feature already can be
>>>>>> implemented partially. I have argued that a full implementation is complex
>>>>>> because there are multiple way to align shapes and no single correct way,
>>>>>> so you need different algorithms for alignment. I don't see any evidence
>>>>>> to the contrary shown here. My point is not that the problem cannot be
>>>>>> solved in many interesting and useful cases---I have done it. My point is
>>>>>> that the problem is complicated, and it cannot be solved in all cases, so
>>>>>> that makes a built-in seem unlikely to occur. Furthermore, a solution is
>>>>>> necessarily complex in terms of its interface, since there are several ways
>>>>>> we can imagine aligning points. This also makes a built-in seem unlikely.
>>>>>>
>>>>>> We can do lots of nice things with existing libraries and without a
>>>>>> built in, though of course there is the limitation due to the inability to
>>>>>> extract geometrical data from OpenSCAD objects. *THAT* may actually be
>>>>>> fixed in a future version, so that seems like the path forward towards a
>>>>>> generic solution to this kind of model that can work on geometry instead of
>>>>>> path lists.
>>>>>>
>>>>>>
>>>>>> On Sat, Jan 21, 2023 at 8:10 PM Sanjeev Prabhakar <
>>>>>> sprabhakar2006@gmail.com> wrote:
>>>>>>
>>>>>>> nearest point approach will be produce this result:
>>>>>>> <Screenshot 2023-01-22 at 6.32.31 AM.png>
>>>>>>>
>>>>>>>
>>>>>>> rays emanating from center and intersection approach will produce
>>>>>>> this result:
>>>>>>> <Screenshot 2023-01-22 at 6.35.04 AM.png>
>>>>>>>
>>>>>>> in the 2nd approach 360 lines were intersected in the example.
>>>>>>> morelines will produce much refined results and should work in most of the
>>>>>>> cases
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Sun, 22 Jan 2023 at 05:41, Adrian Mariano <avm4@cornell.edu>
>>>>>>> wrote:
>>>>>>>
>>>>>>>> It is possible to write a generic extruder for the convex case
>>>>>>>> using cones, but there are a couple things that limit this. For most
>>>>>>>> interesting cases, you need many slices to produce the correct form and to
>>>>>>>> avoid producing artifacts on the curved faces that arise. (See Jordan's
>>>>>>>> example.) Where will these slices come from? Note that even with convex
>>>>>>>> endcaps, the resulting shape need not be convex. You will need the point
>>>>>>>> list of the data in order to produce the many needed slices, most likely,
>>>>>>>> since no mechanism for "averaging" geometry exists. Given that you have a
>>>>>>>> point list, simply computing the desired shape as a polyhedron is much more
>>>>>>>> efficient than computing it as the union of 100 overlapping cones. The
>>>>>>>> version I implemented (convex_offset_extrude in BOSL2) flips the cones
>>>>>>>> around to handle the ends, extrema, whether the shape is increasing or
>>>>>>>> decreasing. This all requires access to the actual point list.
>>>>>>>>
>>>>>>>> Note that the direct computation of the polyhedron also already
>>>>>>>> exists in libraries (it's also here now).
>>>>>>>>
>>>>>>>> Many examples can be seen here (though the animated examples look
>>>>>>>> really bad right now for some reason):
>>>>>>>>
>>>>>>>> https://github.com/revarbat/BOSL2/wiki/skin.scad#functionmodule-skin
>>>>>>>>
>>>>>>>> On Sat, Jan 21, 2023 at 5:27 PM nop head <nop.head@gmail.com>
>>>>>>>> wrote:
>>>>>>>>
>>>>>>>>> The points of the cones can be very close to the base so they are
>>>>>>>>> close to being a flat disk. As long as they are inside the hull they get
>>>>>>>>> discarded.
>>>>>>>>>
>>>>>>>>> On Sat, 21 Jan 2023 at 22:11, Jordan Brown <
>>>>>>>>> openscad@jordan.maileater.net> wrote:
>>>>>>>>>
>>>>>>>>>> On 1/21/2023 1:24 PM, Steve Lelievre wrote:
>>>>>>>>>>
>>>>>>>>>> I like the cones because they only involve the one perimeter at
>>>>>>>>>> the wide end so the shape produced is completely 'correct' in geometrical
>>>>>>>>>> terms.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> OK, thanks.
>>>>>>>>>>
>>>>>>>>>> Do note that it only works if the two are aligned so that the
>>>>>>>>>> points of the cones fall inside the other end's polygon.
>>>>>>>>>>
>>>>>>>>>> _______________________________________________
>>>>>>>>>> OpenSCAD mailing list
>>>>>>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>>>>>>
>>>>>>>>> _______________________________________________
>>>>>>>>> OpenSCAD mailing list
>>>>>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> OpenSCAD mailing list
>>>>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> OpenSCAD mailing list
>>>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>>>
>>>>>> _______________________________________________
>>>>>> OpenSCAD mailing list
>>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>>
>>>>> _______________________________________________
>>>>> OpenSCAD mailing list
>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>
>>>> _______________________________________________
>>>> OpenSCAD mailing list
>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>
>>> _______________________________________________
>>> OpenSCAD mailing list
>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>
>>>
>>> _______________________________________________
>>> OpenSCAD mailing list
>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>
>> _______________________________________________
>> OpenSCAD mailing list
>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>
KS
Kenneth Sloan
Sun, Jan 22, 2023 5:06 AM
Minimizing distances doesn't work as well as minimizing the areas of the resulting triangles.
See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
Minimizing areas of triangles runs into trouble when the two 2D shapes are translated wrt each other. The fix is to register the shapes, triangulate, and then move the 2D shapes to their original position.
Minimizing distances runs into the same issue - but worse.
--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.
Minimizing distances doesn't work as well as minimizing the areas of the resulting triangles.
See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
Minimizing areas of triangles runs into trouble when the two 2D shapes are translated wrt each other. The fix is to register the shapes, triangulate, and then move the 2D shapes to their original position.
Minimizing distances runs into the same issue - but worse.
--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.
SP
Sanjeev Prabhakar
Sun, Jan 22, 2023 5:32 AM
you mean fix the orientation of 2 sections where the sum of areas of
triangles is minimum?
On Sun, 22 Jan 2023 at 10:37, Kenneth Sloan kennethrsloan@gmail.com wrote:
Minimizing distances doesn't work as well as minimizing the areas of the
resulting triangles.
See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
Minimizing areas of triangles runs into trouble when the two 2D shapes are
translated wrt each other. The fix is to register the shapes, triangulate,
and then move the 2D shapes to their original position.
Minimizing distances runs into the same issue - but worse.
--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
you mean fix the orientation of 2 sections where the sum of areas of
triangles is minimum?
On Sun, 22 Jan 2023 at 10:37, Kenneth Sloan <kennethrsloan@gmail.com> wrote:
> Minimizing distances doesn't work as well as minimizing the areas of the
> resulting triangles.
>
> See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
>
> Minimizing areas of triangles runs into trouble when the two 2D shapes are
> translated wrt each other. The fix is to register the shapes, triangulate,
> and then move the 2D shapes to their original position.
>
> Minimizing distances runs into the same issue - but worse.
>
> --
> Kenneth Sloan
> KennethRSloan@gmail.com
> Vision is the art of seeing what is invisible to others.
>
>
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>
AM
Adrian Mariano
Sun, Jan 22, 2023 5:34 AM
It doesn't seem like minimizing distance is fundamentally different in
implementation from minimizing triangle area. However, area is a bit more
complicated, and implementing this in OpenSCAD is hard enough that every
simplification must be exploited. I'm not particularly inclined to touch
at this point without a really compelling reason. The way my code works,
it actually tries to establish a correspondence between vertices of the
adjacent contours, which means it isn't producing triangles a lot of the
time, but (non-planar) quadrilaterals. These are later divided in a
separate operation into triangles. So changing the code to minimize
triangle area would be a complete rewrite. The paper talks of using a
shortest path graph algorithm. Can I implement the classic dijkstra
algorithm in OpenSCAD? And if I do...does it end up being efficient? My
instinct says it would be slow. My approach computes all the alignments
for a single starting pair in O(N^2) time, but then has to try every
starting point option, which makes it cubic.
While I can accept that minimizing area could be better than minimizing
distance, I do not understand what you mean about there being trouble when
the shapes are translated. I did not notice any such trouble. Translated
shapes do produce a different result, but that result appears good, and in
fact it seems like registering the shapes, computing an alignment, and then
using it on the original would produce an inferior result. That is,
translating the shape should change the result, because it changes the
relative configuration of the vertices. Also, translating shapes seems
tricky because then you need to figure out how to translate them. Well
behaved parallel convex shapes might sensibly be aligned on their centroids
by translating one in its plane, but concave shapes that are not parallel
to each other? Seems like it introduces a whole new problem.
On Sun, Jan 22, 2023 at 12:07 AM Kenneth Sloan kennethrsloan@gmail.com
wrote:
Minimizing distances doesn't work as well as minimizing the areas of the
resulting triangles.
See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
Minimizing areas of triangles runs into trouble when the two 2D shapes are
translated wrt each other. The fix is to register the shapes, triangulate,
and then move the 2D shapes to their original position.
Minimizing distances runs into the same issue - but worse.
--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
It doesn't seem like minimizing distance is fundamentally different in
implementation from minimizing triangle area. However, area is a bit more
complicated, and implementing this in OpenSCAD is hard enough that every
simplification must be exploited. I'm not particularly inclined to touch
at this point without a really compelling reason. The way my code works,
it actually tries to establish a correspondence between vertices of the
adjacent contours, which means it isn't producing triangles a lot of the
time, but (non-planar) quadrilaterals. These are later divided in a
separate operation into triangles. So changing the code to minimize
triangle area would be a complete rewrite. The paper talks of using a
shortest path graph algorithm. Can I implement the classic dijkstra
algorithm in OpenSCAD? And if I do...does it end up being efficient? My
instinct says it would be slow. My approach computes all the alignments
for a single starting pair in O(N^2) time, but then has to try every
starting point option, which makes it cubic.
While I can accept that minimizing area could be better than minimizing
distance, I do not understand what you mean about there being trouble when
the shapes are translated. I did not notice any such trouble. Translated
shapes do produce a different result, but that result appears good, and in
fact it seems like registering the shapes, computing an alignment, and then
using it on the original would produce an inferior result. That is,
translating the shape *should* change the result, because it changes the
relative configuration of the vertices. Also, translating shapes seems
tricky because then you need to figure out how to translate them. Well
behaved parallel convex shapes might sensibly be aligned on their centroids
by translating one in its plane, but concave shapes that are not parallel
to each other? Seems like it introduces a whole new problem.
On Sun, Jan 22, 2023 at 12:07 AM Kenneth Sloan <kennethrsloan@gmail.com>
wrote:
> Minimizing distances doesn't work as well as minimizing the areas of the
> resulting triangles.
>
> See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
>
> Minimizing areas of triangles runs into trouble when the two 2D shapes are
> translated wrt each other. The fix is to register the shapes, triangulate,
> and then move the 2D shapes to their original position.
>
> Minimizing distances runs into the same issue - but worse.
>
> --
> Kenneth Sloan
> KennethRSloan@gmail.com
> Vision is the art of seeing what is invisible to others.
>
>
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>
AM
Adrian Mariano
Sun, Jan 22, 2023 5:36 AM
I believe he means that as you establish edges that create the polygonal
surface between two contours, you choose the edge set which creates the
minimum area, with the optimization occurring over all possible edge
mappings.
On Sun, Jan 22, 2023 at 12:33 AM Sanjeev Prabhakar sprabhakar2006@gmail.com
wrote:
you mean fix the orientation of 2 sections where the sum of areas of
triangles is minimum?
On Sun, 22 Jan 2023 at 10:37, Kenneth Sloan kennethrsloan@gmail.com
wrote:
Minimizing distances doesn't work as well as minimizing the areas of the
resulting triangles.
See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
Minimizing areas of triangles runs into trouble when the two 2D shapes
are translated wrt each other. The fix is to register the shapes,
triangulate, and then move the 2D shapes to their original position.
Minimizing distances runs into the same issue - but worse.
--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
I believe he means that as you establish edges that create the polygonal
surface between two contours, you choose the edge set which creates the
minimum area, with the optimization occurring over all possible edge
mappings.
On Sun, Jan 22, 2023 at 12:33 AM Sanjeev Prabhakar <sprabhakar2006@gmail.com>
wrote:
> you mean fix the orientation of 2 sections where the sum of areas of
> triangles is minimum?
>
> On Sun, 22 Jan 2023 at 10:37, Kenneth Sloan <kennethrsloan@gmail.com>
> wrote:
>
>> Minimizing distances doesn't work as well as minimizing the areas of the
>> resulting triangles.
>>
>> See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
>>
>> Minimizing areas of triangles runs into trouble when the two 2D shapes
>> are translated wrt each other. The fix is to register the shapes,
>> triangulate, and then move the 2D shapes to their original position.
>>
>> Minimizing distances runs into the same issue - but worse.
>>
>> --
>> Kenneth Sloan
>> KennethRSloan@gmail.com
>> Vision is the art of seeing what is invisible to others.
>>
>>
>> _______________________________________________
>> OpenSCAD mailing list
>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>
SP
Sanjeev Prabhakar
Sun, Jan 22, 2023 8:02 AM
based on the minimum area triangle logic, below is the best orientation.
[image: Screenshot 2023-01-22 at 1.29.27 PM.png]
it takes 10 sec
720 points in each section
100 slices
there is a lot of opportunity to optimise the code as this is a quick try
On Sun, 22 Jan 2023 at 11:07, Adrian Mariano avm4@cornell.edu wrote:
I believe he means that as you establish edges that create the polygonal
surface between two contours, you choose the edge set which creates the
minimum area, with the optimization occurring over all possible edge
mappings.
On Sun, Jan 22, 2023 at 12:33 AM Sanjeev Prabhakar <
sprabhakar2006@gmail.com> wrote:
you mean fix the orientation of 2 sections where the sum of areas of
triangles is minimum?
On Sun, 22 Jan 2023 at 10:37, Kenneth Sloan kennethrsloan@gmail.com
wrote:
Minimizing distances doesn't work as well as minimizing the areas of the
resulting triangles.
See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
Minimizing areas of triangles runs into trouble when the two 2D shapes
are translated wrt each other. The fix is to register the shapes,
triangulate, and then move the 2D shapes to their original position.
Minimizing distances runs into the same issue - but worse.
--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
based on the minimum area triangle logic, below is the best orientation.
[image: Screenshot 2023-01-22 at 1.29.27 PM.png]
it takes 10 sec
720 points in each section
100 slices
there is a lot of opportunity to optimise the code as this is a quick try
On Sun, 22 Jan 2023 at 11:07, Adrian Mariano <avm4@cornell.edu> wrote:
> I believe he means that as you establish edges that create the polygonal
> surface between two contours, you choose the edge set which creates the
> minimum area, with the optimization occurring over all possible edge
> mappings.
>
> On Sun, Jan 22, 2023 at 12:33 AM Sanjeev Prabhakar <
> sprabhakar2006@gmail.com> wrote:
>
>> you mean fix the orientation of 2 sections where the sum of areas of
>> triangles is minimum?
>>
>> On Sun, 22 Jan 2023 at 10:37, Kenneth Sloan <kennethrsloan@gmail.com>
>> wrote:
>>
>>> Minimizing distances doesn't work as well as minimizing the areas of the
>>> resulting triangles.
>>>
>>> See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
>>>
>>> Minimizing areas of triangles runs into trouble when the two 2D shapes
>>> are translated wrt each other. The fix is to register the shapes,
>>> triangulate, and then move the 2D shapes to their original position.
>>>
>>> Minimizing distances runs into the same issue - but worse.
>>>
>>> --
>>> Kenneth Sloan
>>> KennethRSloan@gmail.com
>>> Vision is the art of seeing what is invisible to others.
>>>
>>>
>>> _______________________________________________
>>> OpenSCAD mailing list
>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>
>> _______________________________________________
>> OpenSCAD mailing list
>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>
FH
Father Horton
Sun, Jan 22, 2023 12:47 PM
Lofting between mismatched shapes is a pain in Fusion360 and OnShape. To
get usable results, I sometimes have to specify the matching points and the
paths between them. Given that, I doubt there is a way to do it internally
to OpenSCAD in any clean way.
On Sun, Jan 22, 2023 at 2:04 AM Sanjeev Prabhakar sprabhakar2006@gmail.com
wrote:
based on the minimum area triangle logic, below is the best orientation.
[image: Screenshot 2023-01-22 at 1.29.27 PM.png]
it takes 10 sec
720 points in each section
100 slices
there is a lot of opportunity to optimise the code as this is a quick try
On Sun, 22 Jan 2023 at 11:07, Adrian Mariano avm4@cornell.edu wrote:
I believe he means that as you establish edges that create the polygonal
surface between two contours, you choose the edge set which creates the
minimum area, with the optimization occurring over all possible edge
mappings.
On Sun, Jan 22, 2023 at 12:33 AM Sanjeev Prabhakar <
sprabhakar2006@gmail.com> wrote:
you mean fix the orientation of 2 sections where the sum of areas of
triangles is minimum?
On Sun, 22 Jan 2023 at 10:37, Kenneth Sloan kennethrsloan@gmail.com
wrote:
Minimizing distances doesn't work as well as minimizing the areas of
the resulting triangles.
See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
Minimizing areas of triangles runs into trouble when the two 2D shapes
are translated wrt each other. The fix is to register the shapes,
triangulate, and then move the 2D shapes to their original position.
Minimizing distances runs into the same issue - but worse.
--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
Lofting between mismatched shapes is a pain in Fusion360 and OnShape. To
get usable results, I sometimes have to specify the matching points and the
paths between them. Given that, I doubt there is a way to do it internally
to OpenSCAD in any clean way.
On Sun, Jan 22, 2023 at 2:04 AM Sanjeev Prabhakar <sprabhakar2006@gmail.com>
wrote:
> based on the minimum area triangle logic, below is the best orientation.
> [image: Screenshot 2023-01-22 at 1.29.27 PM.png]
>
> it takes 10 sec
> 720 points in each section
> 100 slices
>
> there is a lot of opportunity to optimise the code as this is a quick try
>
> On Sun, 22 Jan 2023 at 11:07, Adrian Mariano <avm4@cornell.edu> wrote:
>
>> I believe he means that as you establish edges that create the polygonal
>> surface between two contours, you choose the edge set which creates the
>> minimum area, with the optimization occurring over all possible edge
>> mappings.
>>
>> On Sun, Jan 22, 2023 at 12:33 AM Sanjeev Prabhakar <
>> sprabhakar2006@gmail.com> wrote:
>>
>>> you mean fix the orientation of 2 sections where the sum of areas of
>>> triangles is minimum?
>>>
>>> On Sun, 22 Jan 2023 at 10:37, Kenneth Sloan <kennethrsloan@gmail.com>
>>> wrote:
>>>
>>>> Minimizing distances doesn't work as well as minimizing the areas of
>>>> the resulting triangles.
>>>>
>>>> See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
>>>>
>>>> Minimizing areas of triangles runs into trouble when the two 2D shapes
>>>> are translated wrt each other. The fix is to register the shapes,
>>>> triangulate, and then move the 2D shapes to their original position.
>>>>
>>>> Minimizing distances runs into the same issue - but worse.
>>>>
>>>> --
>>>> Kenneth Sloan
>>>> KennethRSloan@gmail.com
>>>> Vision is the art of seeing what is invisible to others.
>>>>
>>>>
>>>> _______________________________________________
>>>> OpenSCAD mailing list
>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>
>>> _______________________________________________
>>> OpenSCAD mailing list
>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>
>> _______________________________________________
>> OpenSCAD mailing list
>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>
SP
Sanjeev Prabhakar
Sun, Jan 22, 2023 1:03 PM
I tried this minimum area approach and this works.
the optimised model is really quite good.
file can be downloaded here:
https://github.com/sprabhakar2006/openSCAD/blob/main/merging%202%20shapes.scad
python code is here, if anyone wants to try (openscad1.py file would be
required as all the functions are written in this):
merging 2 shapes in extrude
t0=time.time()
sec=cr(pts1([[0,0,1],[8,3,3],[5,7,1],[-8,0,2],[-5,20,1]]),20)
cp1=array(offset(sec,-4)).mean(0)
sec=c3t2(translate(-cp1,sec))
cir1=circle(0,s=720)
cir2=circle(100,s=720)
cut_lines=cpo([cir1,cir2])
i_p1=s_int1(cut_lines+seg(sec))[:718]
i=arange(0,360,360/50)
area1=[]
sol1=[]
for j in i:
pent1=circle(7,s=6)
pent2=c3t2(q_rot([f'z{360/5/2}'],circle(3.5,s=6)))
star1=c3t2(q_rot([f'z{j}'],concatenate(cpo([pent1]+[pent2])).tolist()))
i_p2=s_int1(cut_lines+seg(star1))[:718]
sol=[c2t3(i_p1)]+[translate([0,0,10],i_p2)]
pnts1,faces1=pntsnfaces(sol)
pnts1=array(pnts1)
faces1=faces1[1:-1]
a1=array([norm(cross(pnts1[m]-pnts1[l],pnts1[n]-pnts1[l])) for (l,m,n)
in faces1]).sum()
area1.append(a1)
sol1.append(sol)
sol2=sol1[array(area1).argmin()]
sol3=cpo(sol2)
sol3=cpo([ls(p,100) for p in sol3])+[sol2[1]]
with open('folder_path/trial.scad','w+') as f:
f.write(f'''
{swp(sol3)}
''')
t1=time.time()
t1-t0
On Sun, 22 Jan 2023 at 18:19, Father Horton fatherhorton@gmail.com wrote:
Lofting between mismatched shapes is a pain in Fusion360 and OnShape. To
get usable results, I sometimes have to specify the matching points and the
paths between them. Given that, I doubt there is a way to do it internally
to OpenSCAD in any clean way.
On Sun, Jan 22, 2023 at 2:04 AM Sanjeev Prabhakar <
sprabhakar2006@gmail.com> wrote:
based on the minimum area triangle logic, below is the best orientation.
[image: Screenshot 2023-01-22 at 1.29.27 PM.png]
it takes 10 sec
720 points in each section
100 slices
there is a lot of opportunity to optimise the code as this is a quick try
On Sun, 22 Jan 2023 at 11:07, Adrian Mariano avm4@cornell.edu wrote:
I believe he means that as you establish edges that create the polygonal
surface between two contours, you choose the edge set which creates the
minimum area, with the optimization occurring over all possible edge
mappings.
On Sun, Jan 22, 2023 at 12:33 AM Sanjeev Prabhakar <
sprabhakar2006@gmail.com> wrote:
you mean fix the orientation of 2 sections where the sum of areas of
triangles is minimum?
On Sun, 22 Jan 2023 at 10:37, Kenneth Sloan kennethrsloan@gmail.com
wrote:
Minimizing distances doesn't work as well as minimizing the areas of
the resulting triangles.
See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
Minimizing areas of triangles runs into trouble when the two 2D shapes
are translated wrt each other. The fix is to register the shapes,
triangulate, and then move the 2D shapes to their original position.
Minimizing distances runs into the same issue - but worse.
--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.
OpenSCAD mailing list
To unsubscribe send an email to discuss-leave@lists.openscad.org
I tried this minimum area approach and this works.
the optimised model is really quite good.
file can be downloaded here:
https://github.com/sprabhakar2006/openSCAD/blob/main/merging%202%20shapes.scad
python code is here, if anyone wants to try (openscad1.py file would be
required as all the functions are written in this):
# merging 2 shapes in extrude
t0=time.time()
sec=cr(pts1([[0,0,1],[8,3,3],[5,7,1],[-8,0,2],[-5,20,1]]),20)
cp1=array(offset(sec,-4)).mean(0)
sec=c3t2(translate(-cp1,sec))
cir1=circle(0,s=720)
cir2=circle(100,s=720)
cut_lines=cpo([cir1,cir2])
i_p1=s_int1(cut_lines+seg(sec))[:718]
i=arange(0,360,360/50)
area1=[]
sol1=[]
for j in i:
pent1=circle(7,s=6)
pent2=c3t2(q_rot([f'z{360/5/2}'],circle(3.5,s=6)))
star1=c3t2(q_rot([f'z{j}'],concatenate(cpo([pent1]+[pent2])).tolist()))
i_p2=s_int1(cut_lines+seg(star1))[:718]
sol=[c2t3(i_p1)]+[translate([0,0,10],i_p2)]
pnts1,faces1=pntsnfaces(sol)
pnts1=array(pnts1)
faces1=faces1[1:-1]
a1=array([norm(cross(pnts1[m]-pnts1[l],pnts1[n]-pnts1[l])) for (l,m,n)
in faces1]).sum()
area1.append(a1)
sol1.append(sol)
sol2=sol1[array(area1).argmin()]
sol3=cpo(sol2)
sol3=cpo([ls(p,100) for p in sol3])+[sol2[1]]
with open('folder_path/trial.scad','w+') as f:
f.write(f'''
{swp(sol3)}
''')
t1=time.time()
t1-t0
On Sun, 22 Jan 2023 at 18:19, Father Horton <fatherhorton@gmail.com> wrote:
> Lofting between mismatched shapes is a pain in Fusion360 and OnShape. To
> get usable results, I sometimes have to specify the matching points and the
> paths between them. Given that, I doubt there is a way to do it internally
> to OpenSCAD in any clean way.
>
> On Sun, Jan 22, 2023 at 2:04 AM Sanjeev Prabhakar <
> sprabhakar2006@gmail.com> wrote:
>
>> based on the minimum area triangle logic, below is the best orientation.
>> [image: Screenshot 2023-01-22 at 1.29.27 PM.png]
>>
>> it takes 10 sec
>> 720 points in each section
>> 100 slices
>>
>> there is a lot of opportunity to optimise the code as this is a quick try
>>
>> On Sun, 22 Jan 2023 at 11:07, Adrian Mariano <avm4@cornell.edu> wrote:
>>
>>> I believe he means that as you establish edges that create the polygonal
>>> surface between two contours, you choose the edge set which creates the
>>> minimum area, with the optimization occurring over all possible edge
>>> mappings.
>>>
>>> On Sun, Jan 22, 2023 at 12:33 AM Sanjeev Prabhakar <
>>> sprabhakar2006@gmail.com> wrote:
>>>
>>>> you mean fix the orientation of 2 sections where the sum of areas of
>>>> triangles is minimum?
>>>>
>>>> On Sun, 22 Jan 2023 at 10:37, Kenneth Sloan <kennethrsloan@gmail.com>
>>>> wrote:
>>>>
>>>>> Minimizing distances doesn't work as well as minimizing the areas of
>>>>> the resulting triangles.
>>>>>
>>>>> See the Fuchs, Kedem, Uselton paper for an efficient way to do that.
>>>>>
>>>>> Minimizing areas of triangles runs into trouble when the two 2D shapes
>>>>> are translated wrt each other. The fix is to register the shapes,
>>>>> triangulate, and then move the 2D shapes to their original position.
>>>>>
>>>>> Minimizing distances runs into the same issue - but worse.
>>>>>
>>>>> --
>>>>> Kenneth Sloan
>>>>> KennethRSloan@gmail.com
>>>>> Vision is the art of seeing what is invisible to others.
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> OpenSCAD mailing list
>>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>>
>>>> _______________________________________________
>>>> OpenSCAD mailing list
>>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>>
>>> _______________________________________________
>>> OpenSCAD mailing list
>>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>>
>> _______________________________________________
>> OpenSCAD mailing list
>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>>
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>
