Carsten Fuchs wrote
 > This situation raises the question I previously mentioned about supplying a "fast_distance" method that has O(N^2) run time.  The current method must assume a starting alignment, so if you have polygons p and q it tries aligning p[0] with q[0], then p[1] with q[0], then p[2] with q[0] and so on.   Once you pick a starting point, the algorithm that decides where to insert the edges runs in quadratic time.  So the "fast_distance" method would assume that p[0] aligns with q[0].   For your problem this seems to be obviously desired.   Do you think this "fast_distance" method is worth adding?  (And is there a better name for it?)  

 To be honest, I don't understand the algorithm enough to properly answer this question. I also looked at the code, but I don't understand the OpenSCAD language enough to follow. (It would be easier if this was C++, Python or Lua.)

 The skin() function is very, very powerful. Maybe it is worth a consideration to factor the point alignment methods out of it? This would help with adding other methods, which could be of arbitrary complexity and could also be implemented by users: writing a custom alignment method plug-in would be much closer to my current OpenSCAD language skills, making own attempts much easier.

 Also, I was wondering if a variant of method "distance" could work without segmentation, i.e. without adding points to any of the polygons. At least in my case, it seems not needed and if I understand the algorithm correctly, it would reduce the complexity to O(n²).

 Best regards,
 Carsten


 >
 >     Carsten Fuchs wrote
 >     Thanks for your reply!
 >
 >     Am 05.03.21 um 14:51 schrieb adrianv:
 >     > Yes, if the angle is zero (by which I assume you mean collinear points) then you will get evenly spaced points between the joint points.
 >
 >     Yes, sorry, colinear is the proper word.
 >
 >     >  (Note: you can test this yourself by running an example.)
 >
 >     Yes, but I was wondering if this a part of the stable API, as it seems a case where optimization might remove these extra points in the future.
 >
 >     > With regards to skin, I honestly don't know whether I covered all the cases with the provided methods.    If you are finding that you really need "distance" with an example that has a large number of points then one possible solution might be to supply an O(n^2) version of the distance method that assumes that point 0 aligns to point 0.  (The current code runs an alignment calculation one time for every possible shift of the two profiles, which adds an extra O(n) to the run time.)  
 >
 >     I'm not sure if I understood you correctly, but between two shapes, if one pair of points can be assumed to match (e.g. the first pair at indices 0, or a pair found by picking index 0 in the first shape and finding the smallest distance among all points in the second shape), maybe it would be possible to traverse from there:
 >
 >     For example, if we are at index 0 in the first shape and index 27 was the closest point in the second shape, iterate to index 1 in the first shape, then examine indices 27 and 28 in the second shape, picking the one that is closest? (I've not fully thought this through, this method is probably not good for generalization.)
 >
 >     > Another idea would be to run the part of the model that changes (the "point" of the M) separately from the rest of the model and then union them.  
 >     >
 >     > In any case, I am curious to see the example as you had it configured with the "distance" method, so if you can post some code that would be nice.
 >
 >     The attached sample is more complex than the "M", but it shows my case well: Please see module TestBody() with methods "direct" vs. "distance".
 >
 >     Best regards,
 >     Carsten
 >
 >
 >       
 >     >
 >     >     Carsten Fuchs wrote
 >     >     Hello,
 >     >
 >     >     Am 04.03.21 um 14:41 schrieb adrianv:
 >     >     > As long as you use method="smooth" and the joint parameter is nonzero, and the $fs value isn't small enough to get involved, you will get exactly $fn points added to the input.  If the joint parameter is exactly zero you will get zero points added:  round_corners will not generate duplicated points at a single vertex.  
 >     >
 >     >     Does that mean if `joint` is non-zero, $fn points are added even if the angle at the corner is zero?
 >     >     (e.g. evenly spaced between the corner +/- joint value?)
 >     >
 >     >     > I am curious to see your example where you want to use skin() with the "distance" method but with a rounded shape.  I didn't find this method to be particularly suitable to such shapes, so what did I overlook?  
 >     >
 >     >     We need the "distance" method whenever the number of points between two shapes for `skin()` changes and the other methods don't work well, don't we?
 >     >
 >     >     As `method="distance"` is O(n³) expensive, the aim of my question was to create the rounded input shapes to have the same number of points right from the start, so that `method="direct"` can be used.
 >     >
 >     >
 >     >     Verbal version:
 >     >
 >     >     (You've kindly helped me a few weeks ago with the basis of this, so this is in fact a follow-up question.)
 >     >
 >     >     I have a shape (list of points) that (very roughly, here for simplification) follows the capital letter "M" (five points). These are rounded with `round_corners()`, then offset with function `offset()`, then concatenated, so that the concatenated result follows the outline of the letter "M".
 >     >
 >     >     Now I want to morph the shape, e.g. moving the original point in the center of the "M" upwards until it is at the same height as the upper points left and right. When this is done, the number of points for the morphed "M" that result from the rounding are less than the number of points of the original "M".
 >     >
 >     >     Now I would like to use `skin()` with the original "M" and the morphed "M".
 >     >     I was not able to get good results with `method="direct"`, whereas `method="distance"` looked good. However, it is also very expensive.
 >     >
 >     >     So my intention was to create the original "M" and the morphed "M" with the same number of points right from the start so that I can use `method="direct"`?
 >     >
 >     >
 >     >     Sorry if this description is difficult to follow. I can make example code if it helps to clarify?
 >     >
 >     >     Best regards,
 >     >     Carsten
 >     >
 >

Hello, thanks again for your very detailed reply! Am 12.03.21 um 16:29 schrieb adrianv: > […] You are not required to use the fancy methods.  You can always use simply method="direct" and ensure that you supply profiles with matching point count.   Oh. Yes. I didn't consider that when I wrote it. But wouldn't that make it even easier to separate the methods from skin()? You quoted a paragraph from the documentation of skin(). Although I seem to understand it, I add some comments: > Consider this paragraph from the documentation of skin(): > >    For this operation to be well-defined, the profiles must all have the same vertex count and >    we must assume that profiles are aligned so that vertex `i` links to vertex `i` on all polygons. Very clear so far. >    Many interesting cases do not comply with this restriction.  Two basic methods can handle >    these cases: either add points to edges (resample) so that the profiles are compatible, > or repeat vertices. Instead of "add points" and "repeat vertices" I'd suggest: …: either subdivide edges (insert additional points along the edge) or duplicate vertices (insert edges of length 0) to make both polygons have the same number of points. >  Repeating vertices allows two edges to terminate at the same point, creating >    triangular faces. I prefer "duplicate" over "repeat", because "repeat" sounds as if the vertex could also be repeated elsewhere. It is also unclear which edges are meant. Suggestion: Duplicating vertices allows two edges of the newly created skin to end at the same point, creating triangular faces. Or: Duplicating vertices allows allows distinct points in one polygon to connect to a single point in the other polygon, creating triangular faces. Some minor suggestions in [brackets]: >  You can adjust non-matching [-profiles +polygons] yourself >    either by resampling them using `subdivide_path` or by duplicating vertices using >    `repeat_entries`.  It is OK to pass a [-profile +polygon] that has [duplicated vertices], such as >    a square with 5 points (two of which are identical), so that it can match up to a pentagon. >    Such a combination would create a triangular face at the location of the duplicated vertex. >    Alternatively, `skin` provides methods (described below) for [inserting additional vertices automatically to make otherwise incompatible paths match]. > It appears that the text above isn't clear, because you appear confused about the matter described in this paragraph, namely that you can choose to construct your own alignment by resampling or repeating vertices.  If you can indicate how the documentation could be improved that would be great. Hmm. I guess I understood the text, but initially didn't realize that additional vertices are inserted. Initially, I thought that the methods just find the best matching vertices in both polygons to create triangles and quads for the skin, without adding more. Maybe because I thought that the "distance" method takes the word "distance" verbatim, working like that: for p[i], find the q[j] and q[j+1] that are closest to p[i], thus giving the best triangle. This is also why I thought that "distance" always and only creates triangles for the skin, but it seems that it can use quads as well (or otherwise slices > 0 would not make sense). > To reiterate, for skin to work the profiles MUST all have the same number of points. Yes, understood. > […]  Or do like I've been suggesting and carefully insert extra points to create a "hand-crafted" alignment for your particular shape.  Then call skin and it will simply link the shapes you provide without any extra points inserted.   Yes, this is why I'm now trying to get fixed numbers of vertices with round_corners(). > The run time of the "distance" method is determined by the size of the input.  It is O(N^2) if you assume an initial alignment or O(N^3) if you have to check every possible alignment.  When you use the "refine" option with "distance" the refinement takes place *after* the distance alignment.  It is necessary to give a good rendering for curved "quadrilaterals" but does not affect how the shapes are aligned, nor the computation time to align the shapes.  Your shape, however, seems to benefit from insertion of additional points on the flat regions.   I'm not sure if I can follow … I can see how "refine" would help beforehand, but not after the "distance" alignment. Isn't the "slices" option for improving quads in the skin? > I experimented with your shape [...] Again, many thanks for your efforts, suggestions and help! This is invaluable to me! Best regards, Carsten > Carsten Fuchs wrote > > This situation raises the question I previously mentioned about supplying a "fast_distance" method that has O(N^2) run time.  The current method must assume a starting alignment, so if you have polygons p and q it tries aligning p[0] with q[0], then p[1] with q[0], then p[2] with q[0] and so on.   Once you pick a starting point, the algorithm that decides where to insert the edges runs in quadratic time.  So the "fast_distance" method would assume that p[0] aligns with q[0].   For your problem this seems to be obviously desired.   Do you think this "fast_distance" method is worth adding?  (And is there a better name for it?)   > > To be honest, I don't understand the algorithm enough to properly answer this question. I also looked at the code, but I don't understand the OpenSCAD language enough to follow. (It would be easier if this was C++, Python or Lua.) > > The skin() function is very, very powerful. Maybe it is worth a consideration to factor the point alignment methods out of it? This would help with adding other methods, which could be of arbitrary complexity and could also be implemented by users: writing a custom alignment method plug-in would be much closer to my current OpenSCAD language skills, making own attempts much easier. > > Also, I was wondering if a variant of method "distance" could work without segmentation, i.e. without adding points to any of the polygons. At least in my case, it seems not needed and if I understand the algorithm correctly, it would reduce the complexity to O(n²). > > Best regards, > Carsten > > > > > >     Carsten Fuchs wrote > >     Thanks for your reply! > > > >     Am 05.03.21 um 14:51 schrieb adrianv: > >     > Yes, if the angle is zero (by which I assume you mean collinear points) then you will get evenly spaced points between the joint points. > > > >     Yes, sorry, colinear is the proper word. > > > >     >  (Note: you can test this yourself by running an example.) > > > >     Yes, but I was wondering if this a part of the stable API, as it seems a case where optimization might remove these extra points in the future. > > > >     > With regards to skin, I honestly don't know whether I covered all the cases with the provided methods.    If you are finding that you really need "distance" with an example that has a large number of points then one possible solution might be to supply an O(n^2) version of the distance method that assumes that point 0 aligns to point 0.  (The current code runs an alignment calculation one time for every possible shift of the two profiles, which adds an extra O(n) to the run time.)   > > > >     I'm not sure if I understood you correctly, but between two shapes, if one pair of points can be assumed to match (e.g. the first pair at indices 0, or a pair found by picking index 0 in the first shape and finding the smallest distance among all points in the second shape), maybe it would be possible to traverse from there: > > > >     For example, if we are at index 0 in the first shape and index 27 was the closest point in the second shape, iterate to index 1 in the first shape, then examine indices 27 and 28 in the second shape, picking the one that is closest? (I've not fully thought this through, this method is probably not good for generalization.) > > > >     > Another idea would be to run the part of the model that changes (the "point" of the M) separately from the rest of the model and then union them.   > >     > > >     > In any case, I am curious to see the example as you had it configured with the "distance" method, so if you can post some code that would be nice. > > > >     The attached sample is more complex than the "M", but it shows my case well: Please see module TestBody() with methods "direct" vs. "distance". > > > >     Best regards, > >     Carsten > > > > > >        > >     > > >     >     Carsten Fuchs wrote > >     >     Hello, > >     > > >     >     Am 04.03.21 um 14:41 schrieb adrianv: > >     >     > As long as you use method="smooth" and the joint parameter is nonzero, and the $fs value isn't small enough to get involved, you will get exactly $fn points added to the input.  If the joint parameter is exactly zero you will get zero points added:  round_corners will not generate duplicated points at a single vertex.   > >     > > >     >     Does that mean if `joint` is non-zero, $fn points are added even if the angle at the corner is zero? > >     >     (e.g. evenly spaced between the corner +/- joint value?) > >     > > >     >     > I am curious to see your example where you want to use skin() with the "distance" method but with a rounded shape.  I didn't find this method to be particularly suitable to such shapes, so what did I overlook?   > >     > > >     >     We need the "distance" method whenever the number of points between two shapes for `skin()` changes and the other methods don't work well, don't we? > >     > > >     >     As `method="distance"` is O(n³) expensive, the aim of my question was to create the rounded input shapes to have the same number of points right from the start, so that `method="direct"` can be used. > >     > > >     > > >     >     Verbal version: > >     > > >     >     (You've kindly helped me a few weeks ago with the basis of this, so this is in fact a follow-up question.) > >     > > >     >     I have a shape (list of points) that (very roughly, here for simplification) follows the capital letter "M" (five points). These are rounded with `round_corners()`, then offset with function `offset()`, then concatenated, so that the concatenated result follows the outline of the letter "M". > >     > > >     >     Now I want to morph the shape, e.g. moving the original point in the center of the "M" upwards until it is at the same height as the upper points left and right. When this is done, the number of points for the morphed "M" that result from the rounding are less than the number of points of the original "M". > >     > > >     >     Now I would like to use `skin()` with the original "M" and the morphed "M". > >     >     I was not able to get good results with `method="direct"`, whereas `method="distance"` looked good. However, it is also very expensive. > >     > > >     >     So my intention was to create the original "M" and the morphed "M" with the same number of points right from the start so that I can use `method="direct"`? > >     > > >     > > >     >     Sorry if this description is difficult to follow. I can make example code if it helps to clarify? > >     > > >     >     Best regards, > >     >     Carsten > >     > > > >

 Carsten Fuchs wrote
 Hello,

 Am 04.03.21 um 14:41 schrieb adrianv:

 Unfortunately, it doesn't seem to work. Could you please consider the example code below? If `flapsbump_rel_height` is set to 0, no points are added to the polygon. If set to 0.001, some points are added, but fewer than $fn. I thought that I had forgotten to set $fs, but it doesn't seem to have any effect?

 Best regards,
 Carsten




 include <BOSL2/std.scad>
 include <BOSL2/rounding.scad>


 function berechneQsKombi(breite, wandstaerke, orig=[0, 0], quality=1.0) =
     let(
         hb = breite / 2,
         hb_tunnel = 70 + wandstaerke,
         h_leiste = 6,
         b_leiste = 6,
         tilt = 0.75,
         h_senke = -3,
         b_senke = 4,
         h_seiten = -64,
         h_senkrecht = -36,
         flapsbump_rel_height=10.0,  // set to 0 to see the problem

         basis_polygon = [
             [0, 0],
             [15, 0],
             [20, flapsbump_rel_height],
             [hb - b_leiste - tilt - b_senke - 1, flapsbump_rel_height],
             [hb - b_leiste - tilt - b_senke, h_senke + flapsbump_rel_height],
             [hb - b_leiste - tilt, h_senke + flapsbump_rel_height],
             [hb - b_leiste, h_leiste + flapsbump_rel_height],
             [hb, h_leiste + flapsbump_rel_height],
             [max(hb_tunnel, hb), h_seiten],
             [max(hb_tunnel, hb), h_seiten + h_senkrecht],
         ],

         joints = [
             0, 2.0, 2.5, 1.5, 1.0, 1.5, 2.75, 2.75, 8, 0
         ],

         punkte_aussen = round_corners(
             [for (p=basis_polygon) [p.x + orig.x, p.y + orig.y]],
             method="smooth",
             joint=joints,
             k=0.8,
          // $fs=0.02,   // seems to have no effect, even at 0.0
             $fn=10*quality
         ),

         punkte_innen = offset(punkte_aussen, delta=-wandstaerke)
     )
     concat(punkte_aussen, reverse(punkte_innen));


 color("#0088CC")
 translate([0, -1, 80])
 rotate([90, 0, 0])
 linear_extrude(10)
 polygon(berechneQsKombi(124, 1.5, quality=1.0));

Am 13.03.21 um 04:55 schrieb adrianv: > I get 90 points no matter the value of flapsbump_rel_height.  And $fs works as expected.  Perhaps you have an old version?  I fixed some issues with round_corners sampling a month or two ago.  Try upgrading to the latest BOSL2 version. Hmmmm. I get the same output, but this does not match what I see in the 3D view with edges higlighted. Does the 3D preview optimize colinear edges out? > Also it now supports the "fast_distance" method for skin(), if you want to experiment with that. Wow, thanks! I'll try that later today! Best regards, Carsten > > Carsten Fuchs wrote > Hello, > > Am 04.03.21 um 14:41 schrieb adrianv: > > As long as you use method="smooth" and the joint parameter is nonzero, and the $fs value isn't small enough to get involved, you will get exactly $fn points added to the input.  If the joint parameter is exactly zero you will get zero points added:  round_corners will not generate duplicated points at a single vertex.   > > Unfortunately, it doesn't seem to work. Could you please consider the example code below? If `flapsbump_rel_height` is set to 0, no points are added to the polygon. If set to 0.001, some points are added, but fewer than $fn. I thought that I had forgotten to set $fs, but it doesn't seem to have any effect? > > Best regards, > Carsten > > > > > include <BOSL2/std.scad> > include <BOSL2/rounding.scad> > > > function berechneQsKombi(breite, wandstaerke, orig=[0, 0], quality=1.0) = >     let( >         hb = breite / 2, >         hb_tunnel = 70 + wandstaerke, >         h_leiste = 6, >         b_leiste = 6, >         tilt = 0.75, >         h_senke = -3, >         b_senke = 4, >         h_seiten = -64, >         h_senkrecht = -36, >         flapsbump_rel_height=10.0,  // set to 0 to see the problem > >         basis_polygon = [ >             [0, 0], >             [15, 0], >             [20, flapsbump_rel_height], >             [hb - b_leiste - tilt - b_senke - 1, flapsbump_rel_height], >             [hb - b_leiste - tilt - b_senke, h_senke + flapsbump_rel_height], >             [hb - b_leiste - tilt, h_senke + flapsbump_rel_height], >             [hb - b_leiste, h_leiste + flapsbump_rel_height], >             [hb, h_leiste + flapsbump_rel_height], >             [max(hb_tunnel, hb), h_seiten], >             [max(hb_tunnel, hb), h_seiten + h_senkrecht], >         ], > >         joints = [ >             0, 2.0, 2.5, 1.5, 1.0, 1.5, 2.75, 2.75, 8, 0 >         ], > >         punkte_aussen = round_corners( >             [for (p=basis_polygon) [p.x + orig.x, p.y + orig.y]], >             method="smooth", >             joint=joints, >             k=0.8, >          // $fs=0.02,   // seems to have no effect, even at 0.0 >             $fn=10*quality >         ), > >         punkte_innen = offset(punkte_aussen, delta=-wandstaerke) >     ) >     concat(punkte_aussen, reverse(punkte_innen)); > > > color("#0088CC") > translate([0, -1, 80]) > rotate([90, 0, 0]) > linear_extrude(10) > polygon(berechneQsKombi(124, 1.5, quality=1.0));

Am 13.03.21 um 08:25 schrieb Carsten Fuchs: > Does the 3D preview optimize colinear edges out? It seems its linear_extrude() that does that. In sum: Using round_corners() with method="smooth", joints and $fn works well to get polygons rounded such that a number of vertices is inserted that does not vary with the shape of the polygon! The more I think about it and the more I „manually“ work with the points myself (e.g. whenever two polygons or paths need aligned vertices), the more useful this property gets! Best regards, Carsten

 Carsten Fuchs wrote
 Hello,

 Am 04.03.21 um 14:41 schrieb adrianv:

 Unfortunately, it doesn't seem to work. Could you please consider the

 Best regards,
 Carsten




 include <BOSL2/std.scad>
 include <BOSL2/rounding.scad>


 function berechneQsKombi(breite, wandstaerke, orig=[0, 0],

         basis_polygon = [
             [0, 0],
             [15, 0],
             [20, flapsbump_rel_height],
             [hb - b_leiste - tilt - b_senke - 1,

         joints = [
             0, 2.0, 2.5, 1.5, 1.0, 1.5, 2.75, 2.75, 8, 0
         ],

         punkte_aussen = round_corners(
             [for (p=basis_polygon) [p.x + orig.x, p.y + orig.y]],
             method="smooth",
             joint=joints,
             k=0.8,
          // $fs=0.02,   // seems to have no effect, even at 0.0
             $fn=10*quality
         ),

         punkte_innen = offset(punkte_aussen, delta=-wandstaerke)
     )
     concat(punkte_aussen, reverse(punkte_innen));


 color("#0088CC")
 translate([0, -1, 80])
 rotate([90, 0, 0])
 linear_extrude(10)
 polygon(berechneQsKombi(124, 1.5, quality=1.0));

Yes, this has been recently discussed in another thread. OpenSCAD removes collinear vertices when you create geometry. I suggest using debug_polygon(poly) or something like move_copies(poly) circle(r=0.5) in order to visualize a point list, poly, that may contain collinear points. Carsten Fuchs wrote > Am 13.03.21 um 04:55 schrieb adrianv: >> I get 90 points no matter the value of flapsbump_rel_height.  And $fs >> works as expected.  Perhaps you have an old version?  I fixed some issues >> with round_corners sampling a month or two ago.  Try upgrading to the >> latest BOSL2 version. > > Hmmmm. I get the same output, but this does not match what I see in the 3D > view with edges higlighted. > Does the 3D preview optimize colinear edges out? > >> Also it now supports the "fast_distance" method for skin(), if you want >> to experiment with that. > > Wow, thanks! I'll try that later today! > > Best regards, > Carsten > > >> >> Carsten Fuchs wrote >> Hello, >> >> Am 04.03.21 um 14:41 schrieb adrianv: >> > As long as you use method="smooth" and the joint parameter is >> nonzero, and the $fs value isn't small enough to get involved, you will >> get exactly $fn points added to the input.  If the joint parameter is >> exactly zero you will get zero points added:  round_corners will not >> generate duplicated points at a single vertex.   >> >> Unfortunately, it doesn't seem to work. Could you please consider the >> example code below? If `flapsbump_rel_height` is set to 0, no points are >> added to the polygon. If set to 0.001, some points are added, but fewer >> than $fn. I thought that I had forgotten to set $fs, but it doesn't seem >> to have any effect? >> >> Best regards, >> Carsten >> >> >> >> >> include &lt;BOSL2/std.scad&gt; >> include &lt;BOSL2/rounding.scad&gt; >> >> >> function berechneQsKombi(breite, wandstaerke, orig=[0, 0], >> quality=1.0) = >>     let( >>         hb = breite / 2, >>         hb_tunnel = 70 + wandstaerke, >>         h_leiste = 6, >>         b_leiste = 6, >>         tilt = 0.75, >>         h_senke = -3, >>         b_senke = 4, >>         h_seiten = -64, >>         h_senkrecht = -36, >>         flapsbump_rel_height=10.0,  // set to 0 to see the problem >> >>         basis_polygon = [ >>             [0, 0], >>             [15, 0], >>             [20, flapsbump_rel_height], >>             [hb - b_leiste - tilt - b_senke - 1, >> flapsbump_rel_height], >>             [hb - b_leiste - tilt - b_senke, h_senke + >> flapsbump_rel_height], >>             [hb - b_leiste - tilt, h_senke + flapsbump_rel_height], >>             [hb - b_leiste, h_leiste + flapsbump_rel_height], >>             [hb, h_leiste + flapsbump_rel_height], >>             [max(hb_tunnel, hb), h_seiten], >>             [max(hb_tunnel, hb), h_seiten + h_senkrecht], >>         ], >> >>         joints = [ >>             0, 2.0, 2.5, 1.5, 1.0, 1.5, 2.75, 2.75, 8, 0 >>         ], >> >>         punkte_aussen = round_corners( >>             [for (p=basis_polygon) [p.x + orig.x, p.y + orig.y]], >>             method="smooth", >>             joint=joints, >>             k=0.8, >>          // $fs=0.02,   // seems to have no effect, even at 0.0 >>             $fn=10*quality >>         ), >> >>         punkte_innen = offset(punkte_aussen, delta=-wandstaerke) >>     ) >>     concat(punkte_aussen, reverse(punkte_innen)); >> >> >> color("#0088CC") >> translate([0, -1, 80]) >> rotate([90, 0, 0]) >> linear_extrude(10) >> polygon(berechneQsKombi(124, 1.5, quality=1.0)); > _______________________________________________ > OpenSCAD mailing list > To unsubscribe send an email to > discuss-leave@.openscad -- Sent from: http://forum.openscad.org/

 Carsten Fuchs wrote

 To be honest, I don't understand the algorithm enough to properly

 The skin() function is very, very powerful. Maybe it is worth a

 Also, I was wondering if a variant of method "distance" could work

 Best regards,
 Carsten

Thanks for your comments on the paragraph from the skin documentation. I have incorporated most of your suggestions. Would it be easy to separate the methods from skin()? Yes. But what is the benefit? Skin allows you to use a different method between every pair of polygons in a stack. If the methods are provided in separate functions only you lose this ability. And if the methods are combined...then that's just a reimplementation of skin(). Basically all skin() does itself is error handling, and resampling of the profiles. Once this is complete it passes the matched profiles to _skin_core() to produce the actual polyhedron. So you're saying essentially eliminate the skin() function completely and just have _skin_core(). Again I ask, what would be gained by this? As I said before, I think this places more burden on the user who wants to just use the automatic methods. That is, it provides no advantage. You can already ignore the automated methods. So separating them and requiring that they be invoked explicitly just makes use of skin more complex. There was a question of whether the automated methods should be documented as user-callable functions or hidden as internal functions and it was argued that nobody would use them other than to call skin, hence the situation where they are hidden. The explanation in the documentation is not very clear about what the "distance" method does. I have rewritten it as follows. What do you think? The "distance", "fast_distance" and "tangent" methods work by duplicating vertices to create triangular faces. In the skined object created by two polygons, every vertex of a polygon must have an edge connecting to some vertex on the other one. If you connect two squares this can be accomplished with four edges, but if you want to connect a square to a pentagon you must add a fifth edge for the "extra" vertex on the pentagon. You must now decide which vertex on the square to connect the "extra" edge to. How do you decide where to put that fifth edge? The "distance" method answers this question by using an optimization: it minimizes the total length of all the edges connecting the two polygons. This algorithm generally produces a good result when both profiles are discrete ones with a small number of vertices. It is computationally intensive (O(N^3)) and may be slow on large inputs. The resulting surfaces generally have curved faces, so be sure to select a sufficiently large value for `slices` and `refine`. Note that for this method, `sampling` must be set to `"segment"`, and hence this is the default setting. Using sampling by length would ignore the repeated vertices and ruin the alignment. The "fast_distance" method restricts the optimization by assuming that an edge should connect vertex 0 of the two polygons. This reduces the run time to O(N^2) and makes the method usable on profiles with more points if you take care to index the inputs to match. The topic of adding points along an edge was recently discussed on another thread about linear_extrude with twist. When you have a curved "quadrilateral" you have to resample it finely enough to produce a smooth surface. You get the best result if the triangles are approximately equilateral. When the triangles are very long and skinny you get a kind of wiggly edge unless you use a huge number of triangles. The result looks ugly in openscad, with moire patterns appearing in the image, it's harder to understand what the shape looks like. The achieve equilateral triangles you need both refine and slices, and at least in my opinion you can get a better looking result with fewer total triangles. (That is, an n x n division of the quadrilateral looks better than n^2 long skinny triangles.) include<BOSL2/std.scad> //right_half() rot(60)skin([regular_ngon(n=3, r=4), regular_ngon(n=5,r=5)], z=[0,4], refine=1, slices=10, method="distance"); <http://forum.openscad.org/file/t2477/shape1.png> If you uncomment the "right_half" then you see this: <http://forum.openscad.org/file/t2477/shape2.png> Notice that the edge is not smooth? Changing to refine=5, slices=5 produces this result: <http://forum.openscad.org/file/t2477/shape3.png> which I believe is superior to the result obtained with slices=25. One problem I had with your shape was getting a result that looked good on the top/bottom but when sliced in half showed this type of behavior. Unfortunately, it wasn't so simply solved for your shape---it seemed to be a consequence of how the points were linking up, and to change it I had to add more points in the right places. Applying edge refinement *before* using skin() with the "distance" method produces a very difference result. Adding more vertices gives skin() more options for how to optimally connect the polygons. We no longer have the restriction of connecting just the corners of the polygons. This is the result: include<BOSL2/std.scad> tri = subdivide_path(regular_ngon(n=3, r=4), N=30, closed=true); pent = subdivide_path(regular_ngon(n=5,r=5), N=30, closed=true); skin([tri,pent], z=[0,4], refine=1, slices=25, method="distance"); <http://forum.openscad.org/file/t2477/shape4.png> Carsten Fuchs wrote > Hello, > > thanks again for your very detailed reply! > > Am 12.03.21 um 16:29 schrieb adrianv: >> […] You are not required to use the fancy methods.  You can always use >> simply method="direct" and ensure that you supply profiles with matching >> point count.   > > Oh. Yes. I didn't consider that when I wrote it. But wouldn't that make it > even easier to separate the methods from skin()? > > >> The run time of the "distance" method is determined by the size of the >> input.  It is O(N^2) if you assume an initial alignment or O(N^3) if you >> have to check every possible alignment.  When you use the "refine" option >> with "distance" the refinement takes place *after* the distance >> alignment.  It is necessary to give a good rendering for curved >> "quadrilaterals" but does not affect how the shapes are aligned, nor the >> computation time to align the shapes.  Your shape, however, seems to >> benefit from insertion of additional points on the flat regions.   > > I'm not sure if I can follow … I can see how "refine" would help > beforehand, but not after the "distance" alignment. Isn't the "slices" > option for improving quads in the skin? > >> I experimented with your shape [...] > > Again, many thanks for your efforts, suggestions and help! > This is invaluable to me! > > Best regards, > Carsten > > > > > >> Carsten Fuchs wrote >> > This situation raises the question I previously mentioned about >> supplying a "fast_distance" method that has O(N^2) run time.  The current >> method must assume a starting alignment, so if you have polygons p and q >> it tries aligning p[0] with q[0], then p[1] with q[0], then p[2] with >> q[0] and so on.   Once you pick a starting point, the algorithm that >> decides where to insert the edges runs in quadratic time.  So the >> "fast_distance" method would assume that p[0] aligns with q[0].   For >> your problem this seems to be obviously desired.   Do you think this >> "fast_distance" method is worth adding?  (And is there a better name for >> it?)   >> >> To be honest, I don't understand the algorithm enough to properly >> answer this question. I also looked at the code, but I don't understand >> the OpenSCAD language enough to follow. (It would be easier if this was >> C++, Python or Lua.) >> >> The skin() function is very, very powerful. Maybe it is worth a >> consideration to factor the point alignment methods out of it? This would >> help with adding other methods, which could be of arbitrary complexity >> and could also be implemented by users: writing a custom alignment method >> plug-in would be much closer to my current OpenSCAD language skills, >> making own attempts much easier. >> >> Also, I was wondering if a variant of method "distance" could work >> without segmentation, i.e. without adding points to any of the polygons. >> At least in my case, it seems not needed and if I understand the >> algorithm correctly, it would reduce the complexity to O(n²). >> >> Best regards, >> Carsten >> >> >> > >> >     Carsten Fuchs wrote >> >     Thanks for your reply! >> > >> >     Am 05.03.21 um 14:51 schrieb adrianv: >> >     > Yes, if the angle is zero (by which I assume you mean >> collinear points) then you will get evenly spaced points between the >> joint points. >> > >> >     Yes, sorry, colinear is the proper word. >> > >> >     >  (Note: you can test this yourself by running an example.) >> > >> >     Yes, but I was wondering if this a part of the stable API, as >> it seems a case where optimization might remove these extra points in the >> future. >> > >> >     > With regards to skin, I honestly don't know whether I covered >> all the cases with the provided methods.    If you are finding that you >> really need "distance" with an example that has a large number of points >> then one possible solution might be to supply an O(n^2) version of the >> distance method that assumes that point 0 aligns to point 0.  (The >> current code runs an alignment calculation one time for every possible >> shift of the two profiles, which adds an extra O(n) to the run time.)   >> > >> >     I'm not sure if I understood you correctly, but between two >> shapes, if one pair of points can be assumed to match (e.g. the first >> pair at indices 0, or a pair found by picking index 0 in the first shape >> and finding the smallest distance among all points in the second shape), >> maybe it would be possible to traverse from there: >> > >> >     For example, if we are at index 0 in the first shape and index >> 27 was the closest point in the second shape, iterate to index 1 in the >> first shape, then examine indices 27 and 28 in the second shape, picking >> the one that is closest? (I've not fully thought this through, this >> method is probably not good for generalization.) >> > >> >     > Another idea would be to run the part of the model that >> changes (the "point" of the M) separately from the rest of the model and >> then union them.   >> >     > >> >     > In any case, I am curious to see the example as you had it >> configured with the "distance" method, so if you can post some code that >> would be nice. >> > >> >     The attached sample is more complex than the "M", but it shows >> my case well: Please see module TestBody() with methods "direct" vs. >> "distance". >> > >> >     Best regards, >> >     Carsten >> > >> > >> >        >> >     > >> >     >     Carsten Fuchs wrote >> >     >     Hello, >> >     > >> >     >     Am 04.03.21 um 14:41 schrieb adrianv: >> >     >     > As long as you use method="smooth" and the joint >> parameter is nonzero, and the $fs value isn't small enough to get >> involved, you will get exactly $fn points added to the input.  If the >> joint parameter is exactly zero you will get zero points added: >>  round_corners will not generate duplicated points at a single vertex.   >> >     > >> >     >     Does that mean if `joint` is non-zero, $fn points are >> added even if the angle at the corner is zero? >> >     >     (e.g. evenly spaced between the corner +/- joint value?) >> >     > >> >     >     > I am curious to see your example where you want to use >> skin() with the "distance" method but with a rounded shape.  I didn't >> find this method to be particularly suitable to such shapes, so what did >> I overlook?   >> >     > >> >     >     We need the "distance" method whenever the number of >> points between two shapes for `skin()` changes and the other methods >> don't work well, don't we? >> >     > >> >     >     As `method="distance"` is O(n³) expensive, the aim of my >> question was to create the rounded input shapes to have the same number >> of points right from the start, so that `method="direct"` can be used. >> >     > >> >     > >> >     >     Verbal version: >> >     > >> >     >     (You've kindly helped me a few weeks ago with the basis >> of this, so this is in fact a follow-up question.) >> >     > >> >     >     I have a shape (list of points) that (very roughly, here >> for simplification) follows the capital letter "M" (five points). These >> are rounded with `round_corners()`, then offset with function `offset()`, >> then concatenated, so that the concatenated result follows the outline of >> the letter "M". >> >     > >> >     >     Now I want to morph the shape, e.g. moving the original >> point in the center of the "M" upwards until it is at the same height as >> the upper points left and right. When this is done, the number of points >> for the morphed "M" that result from the rounding are less than the >> number of points of the original "M". >> >     > >> >     >     Now I would like to use `skin()` with the original "M" >> and the morphed "M". >> >     >     I was not able to get good results with >> `method="direct"`, whereas `method="distance"` looked good. However, it >> is also very expensive. >> >     > >> >     >     So my intention was to create the original "M" and the >> morphed "M" with the same number of points right from the start so that I >> can use `method="direct"`? >> >     > >> >     > >> >     >     Sorry if this description is difficult to follow. I can >> make example code if it helps to clarify? >> >     > >> >     >     Best regards, >> >     >     Carsten >> >     > >> > >> > _______________________________________________ > OpenSCAD mailing list > To unsubscribe send an email to > discuss-leave@.openscad -- Sent from: http://forum.openscad.org/

 Carsten Fuchs wrote
 Hello,

 thanks again for your very detailed reply!

 Am 12.03.21 um 16:29 schrieb adrianv:

 Oh. Yes. I didn't consider that when I wrote it. But wouldn't that make it even easier to separate the methods from skin()?

 I'm not sure if I can follow … I can see how "refine" would help beforehand, but not after the "distance" alignment. Isn't the "slices" option for improving quads in the skin?

 Again, many thanks for your efforts, suggestions and help!
 This is invaluable to me!

 Best regards,
 Carsten

Hello, Am 13.03.21 um 13:58 schrieb adrianv: > Would it be easy to separate the methods from skin()?  Yes.  [...]  Again I ask, what would be gained by this? Hmmm. I see your point. Thinking about it further, maybe it is a matter of documentation: The very large text of the `skin()` documentation looks quite scary. It seems that the `method` parameter governs the overall functionality of `skin()`, so maybe the documentation could be arranged in subsections, i.e. one subsection for each method and other subsections, e.g. some beforehand for intro/overview and some thereafter, e.g. one for resampling/refining and one for parameters that are common to all methods. (And maybe just refer to function `subdivide_path()` instead of repeating it's documentation with `skin()`?) > The explanation in the documentation is not very clear about what the "distance" method does.  I have rewritten it as follows.  What do you think?   Please forgive me, but the sheer number of concepts along with their condensed presentation that are described in these paragraphs is really overwhelming. I would prefer if e.g. everything that is related to the square/pentagon problem (which I find is a very good choice to base the text and examples on) was in one place: The concept of inserting vertices along edges, duplicating vertices to create zero-length edges that cause triangle in the skin, the related parameters, links to `subdivide_path()`, etc. > The topic of adding points along an edge was recently discussed on another thread about linear_extrude with twist.  When you have a curved "quadrilateral" you have to resample it finely enough to produce a smooth surface.  You get the best result if the triangles are approximately equilateral.  When the triangles are very long and skinny you get a kind of wiggly edge unless you use a huge number of triangles.  The result looks ugly in openscad, with moire patterns appearing in the image, it's harder to understand what the shape looks like.  The achieve equilateral triangles you need both refine and slices, and at least in my opinion you can get a better looking result with fewer total triangles.   (That is, an n x n division of the quadrilateral looks better than n^2 long skinny triangles.) Many thanks for your very detailed reply and great example screenshots! Geometrically, I now understand how quads can result in long, sharp triangles that look bad and how they are much improved by „subdividing them along the long edges“. I think at least as difficult to understand this spatially is it to explain this in the documentation. Maybe, as suggested above, it would help if you made a separate page in the Wiki specific to this topic. I'd help, but I'm sure that you are much quicker than me to come up with the great examples that you posted in your above mail. If this page used clear, unambiguous terminology that other documentation shared, I'm sure that several other docs could link to it. Besides `skin()` e.g. the `subdivide_path()` function. Best regards, Carsten > Carsten Fuchs wrote > Hello, > > thanks again for your very detailed reply! > > Am 12.03.21 um 16:29 schrieb adrianv: > > […] You are not required to use the fancy methods.  You can always use simply method="direct" and ensure that you supply profiles with matching point count.   > > Oh. Yes. I didn't consider that when I wrote it. But wouldn't that make it even easier to separate the methods from skin()? > > > > The run time of the "distance" method is determined by the size of the input.  It is O(N^2) if you assume an initial alignment or O(N^3) if you have to check every possible alignment.  When you use the "refine" option with "distance" the refinement takes place *after* the distance alignment.  It is necessary to give a good rendering for curved "quadrilaterals" but does not affect how the shapes are aligned, nor the computation time to align the shapes.  Your shape, however, seems to benefit from insertion of additional points on the flat regions.   > > I'm not sure if I can follow … I can see how "refine" would help beforehand, but not after the "distance" alignment. Isn't the "slices" option for improving quads in the skin? > > > I experimented with your shape [...] > > Again, many thanks for your efforts, suggestions and help! > This is invaluable to me! > > Best regards, > Carsten > > > > > > >     Carsten Fuchs wrote > >     > This situation raises the question I previously mentioned about supplying a "fast_distance" method that has O(N^2) run time.  The current method must assume a starting alignment, so if you have polygons p and q it tries aligning p[0] with q[0], then p[1] with q[0], then p[2] with q[0] and so on.   Once you pick a starting point, the algorithm that decides where to insert the edges runs in quadratic time.  So the "fast_distance" method would assume that p[0] aligns with q[0].   For your problem this seems to be obviously desired.   Do you think this "fast_distance" method is worth adding?  (And is there a better name for it?)   > > > >     To be honest, I don't understand the algorithm enough to properly answer this question. I also looked at the code, but I don't understand the OpenSCAD language enough to follow. (It would be easier if this was C++, Python or Lua.) > > > >     The skin() function is very, very powerful. Maybe it is worth a consideration to factor the point alignment methods out of it? This would help with adding other methods, which could be of arbitrary complexity and could also be implemented by users: writing a custom alignment method plug-in would be much closer to my current OpenSCAD language skills, making own attempts much easier. > > > >     Also, I was wondering if a variant of method "distance" could work without segmentation, i.e. without adding points to any of the polygons. At least in my case, it seems not needed and if I understand the algorithm correctly, it would reduce the complexity to O(n²). > > > >     Best regards, > >     Carsten > > > > > >     > > >     >     Carsten Fuchs wrote > >     >     Thanks for your reply! > >     > > >     >     Am 05.03.21 um 14:51 schrieb adrianv: > >     >     > Yes, if the angle is zero (by which I assume you mean collinear points) then you will get evenly spaced points between the joint points. > >     > > >     >     Yes, sorry, colinear is the proper word. > >     > > >     >     >  (Note: you can test this yourself by running an example.) > >     > > >     >     Yes, but I was wondering if this a part of the stable API, as it seems a case where optimization might remove these extra points in the future. > >     > > >     >     > With regards to skin, I honestly don't know whether I covered all the cases with the provided methods.    If you are finding that you really need "distance" with an example that has a large number of points then one possible solution might be to supply an O(n^2) version of the distance method that assumes that point 0 aligns to point 0.  (The current code runs an alignment calculation one time for every possible shift of the two profiles, which adds an extra O(n) to the run time.)   > >     > > >     >     I'm not sure if I understood you correctly, but between two shapes, if one pair of points can be assumed to match (e.g. the first pair at indices 0, or a pair found by picking index 0 in the first shape and finding the smallest distance among all points in the second shape), maybe it would be possible to traverse from there: > >     > > >     >     For example, if we are at index 0 in the first shape and index 27 was the closest point in the second shape, iterate to index 1 in the first shape, then examine indices 27 and 28 in the second shape, picking the one that is closest? (I've not fully thought this through, this method is probably not good for generalization.) > >     > > >     >     > Another idea would be to run the part of the model that changes (the "point" of the M) separately from the rest of the model and then union them.   > >     >     > > >     >     > In any case, I am curious to see the example as you had it configured with the "distance" method, so if you can post some code that would be nice. > >     > > >     >     The attached sample is more complex than the "M", but it shows my case well: Please see module TestBody() with methods "direct" vs. "distance". > >     > > >     >     Best regards, > >     >     Carsten > >     > > >     > > >     >        > >     >     > > >     >     >     Carsten Fuchs wrote > >     >     >     Hello, > >     >     > > >     >     >     Am 04.03.21 um 14:41 schrieb adrianv: > >     >     >     > As long as you use method="smooth" and the joint parameter is nonzero, and the $fs value isn't small enough to get involved, you will get exactly $fn points added to the input.  If the joint parameter is exactly zero you will get zero points added:  round_corners will not generate duplicated points at a single vertex.   > >     >     > > >     >     >     Does that mean if `joint` is non-zero, $fn points are added even if the angle at the corner is zero? > >     >     >     (e.g. evenly spaced between the corner +/- joint value?) > >     >     > > >     >     >     > I am curious to see your example where you want to use skin() with the "distance" method but with a rounded shape.  I didn't find this method to be particularly suitable to such shapes, so what did I overlook?   > >     >     > > >     >     >     We need the "distance" method whenever the number of points between two shapes for `skin()` changes and the other methods don't work well, don't we? > >     >     > > >     >     >     As `method="distance"` is O(n³) expensive, the aim of my question was to create the rounded input shapes to have the same number of points right from the start, so that `method="direct"` can be used. > >     >     > > >     >     > > >     >     >     Verbal version: > >     >     > > >     >     >     (You've kindly helped me a few weeks ago with the basis of this, so this is in fact a follow-up question.) > >     >     > > >     >     >     I have a shape (list of points) that (very roughly, here for simplification) follows the capital letter "M" (five points). These are rounded with `round_corners()`, then offset with function `offset()`, then concatenated, so that the concatenated result follows the outline of the letter "M". > >     >     > > >     >     >     Now I want to morph the shape, e.g. moving the original point in the center of the "M" upwards until it is at the same height as the upper points left and right. When this is done, the number of points for the morphed "M" that result from the rounding are less than the number of points of the original "M". > >     >     > > >     >     >     Now I would like to use `skin()` with the original "M" and the morphed "M". > >     >     >     I was not able to get good results with `method="direct"`, whereas `method="distance"` looked good. However, it is also very expensive. > >     >     > > >     >     >     So my intention was to create the original "M" and the morphed "M" with the same number of points right from the start so that I can use `method="direct"`? > >     >     > > >     >     > > >     >     >     Sorry if this description is difficult to follow. I can make example code if it helps to clarify? > >     >     > > >     >     >     Best regards, > >     >     >     Carsten > >     >     >