Dear group,
with the `round_cordners()` function from BOSL2 (https://github.com/revarbat/BOSL2/wiki/rounding.scad#function-round_corners), when I use the `joint` parameter along with `$fn`, is this guaranteed to always result in the same number of points, even if the angles at the corners are very small or even zero? For example: round_corners( points, method="smooth", joint=list_of_joint_values, $fn=12 // is this guaranteed? ) My intention is to use the resulting shape with the `skin()` function from BOSL2, whose O(n³) characteristic of `method=distance` is too expensive for the number of points in my smoothed polygon. Best regards, Carsten _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
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.
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?
Sent from the OpenSCAD mailing list archive at Nabble.com. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
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 [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
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. (Note: you can test this yourself by running an example.)
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.) 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.
Sent from the OpenSCAD mailing list archive at Nabble.com. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
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 [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org test.scad (4K) Download Attachment |
I have no plans to change the behavior: you will always get $fn points. I will document the behavior.
I took a look at your example. I think that it is a kind of example that in principle one wants to solve with the "tangent" method, but unfortunately this method fails when the shape has concave regions. I agree that the result with "reindex" is terrible. So "distance" is your only option if you seek an automated approach. First a couple observations. When you use "distance" the resulting shape is not linear. I find I want slices=10 perhaps to avoid zig-zags in the surface. You have slices=0 which I feel produces a poor result. Secondly, you have some very easy ways to divide the problem into smaller pieces. You can separate the inside curve and outside curve and skin() them separately and then take the difference(). I tried this and run time fell from 90s to 20s. With O(N^3) run time it helps a lot to do two half-sized problems instead of one full problem. Another big time saver is that your model has mirror symmetry, so you can cut it in half once more and use mirror() to create the second after after skinning. This should give another big savings. So that's where you can go if you want to get a quick solution without working too hard using the existing tools. I have to say I feel that the solution is a bit funny looking around one of the curves. I suspect that if you manually match profiles, as you have been trying to do, you should be able to get a superior solution. 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?)
Sent from the OpenSCAD mailing list archive at Nabble.com. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
Hello,
Am 08.03.21 um 22:18 schrieb adrianv: > I have no plans to change the behavior: you will always get $fn points. I will document the behavior. Thanks! > […] So that's where you can go if you want to get a quick solution without working too hard using the existing tools. Thank you! > 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 [hidden email] |
In reply to this post by adrianv
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)); _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] |
In reply to this post by Carsten Fuchs
There is a large comment block entitled "Minimum Distance Mapping using Dynamic Programming" that explains the algorithm. I think reading this will be much more informative than trying to read the code, even for someone expert in OpenSCAD. But knowing how the algorithm works isn't very important. You just need to know what it does: it inserts edges so as to minimize the total sum of edge length.
You suggest to "factor the point alignment methods out". This API change would make the function harder to use without providing any benefit. 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. 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. 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. Repeating vertices allows two edges to terminate at the same point, creating triangular faces. You can adjust non-matching profiles yourself either by resampling them using `subdivide_path` or by duplicating vertices using `repeat_entries`. It is OK to pass a profile that has the same vertex repeated, 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 matching up incompatible paths. 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. To reiterate, for skin to work the profiles MUST all have the same number of points. If you have two shapes that fail this requirement then you (or skin) MUST insert extra points somehow, either by repeating points (which will result in triangular faces in the skinned shape) or by interpolating (which results in quadrilateral faces). If the inputs are incompatible, skin() by default resamples the smaller one to match the larger. The "distance" method, on the other hand, repeats points in the shorter input to produce a matching length. If you don't want this to happen, don't invoke skin with incompatible inputs. If you want to devise your own fancy (or simple) algorithm for making the alignment you can do so yourself outside of skin. There is nothing standing in the way of this. All the existing methods do is take polygons as input and produce new polygons as output that have matching point count. You can do whatever complicated calculation you need to insert extra points so that the shapes have the same length. 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. 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 experimented with your shape and it seems quite difficult to get a truly beautiful result with the automated methods. I added "fast_distance" but I think it is necessary to resample the points along some of the flat sections to create more options for edges that must align with the curve, and even so there is still a behavior occurring that I don't like, though it's a bit subtle. I tried using resample_path() and it produces a result nice in some ways and bad in others. Using $fs for all the arcs gave a result that appears good on half but not so good on the other half. To get the best result I think you need to subdivide the curves manually, as I think you are now trying to do. In this way you can choose how the different parts of the curve will align to produce the most pleasing result. Some of the flat parts need to be subsampled and aligned with curved parts.
Sent from the OpenSCAD mailing list archive at Nabble.com. _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] |
In reply to this post by Carsten Fuchs
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. Also it now supports the "fast_distance" method for skin(), if you want to experiment with that.
Sent from the OpenSCAD mailing list archive at Nabble.com. _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] |
In reply to this post by adrianv
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 > > > > > > OpenSCAD mailing list To unsubscribe send an email to [hidden email] |
In reply to this post by adrianv
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)); OpenSCAD mailing list To unsubscribe send an email to [hidden email] |
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 _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] |
In reply to this post by Carsten Fuchs
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.
Sent from the OpenSCAD mailing list archive at Nabble.com. _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] |
In reply to this post by Carsten Fuchs
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"); If you uncomment the "right_half" then you see this: Notice that the edge is not smooth? Changing to refine=5, slices=5 produces this result: 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");
Sent from the OpenSCAD mailing list archive at Nabble.com. _______________________________________________ OpenSCAD mailing list To unsubscribe send an email to [hidden email] |
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 > > > > OpenSCAD mailing list To unsubscribe send an email to [hidden email] |
Free forum by Nabble | Edit this page |