# Triangulation of quads

63 messages
1234
Open this post in threaded view
|

## Triangulation of quads

 While playing with springs I found that the way I split quads into two triangles has a big effect on the appearance.Here I split them the one way and it looks wrong shading wise. Here I split them on the other diagonal and it looks much smoother.Here I present them to polyhedron as quads and let F5 triangulate them.It seems to be random, so not optimum.If I reverse the handedness of the spiral then the other diagonal is the correct one. Does anybody know the correct algorithm? The length of the two diagonals is the same so that can't be used to choose between them.I am thinking that one way makes a convex surface patch and the other way concave. I think that if the surface is convex in the area of the patch then the diagonal should be chosen to give a convex patch and vice versa. Does that make sense?Not sure how I would code that efficiently. Is there a better way than calculating the normals of the triangles to determine if the patch is concave or convex. And is there an easy way to determine if the surface is locally concave or convex? In this case it is always convex so I could cheat and always assume that. It would be right most of the time as a swept surface must always be partially convex.If this is a thing why doesn't OpenSCAD's built in triangulation do it? Things like linear_extrude with twist seem to get this wrong. Twisting a circle in the negative direction looks better than in the positive direction. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Triangulation of quads

 Looking at subdivision surface stuff makes me think you could try taking the average of all the neighbor points and then picking the diagonal that's furthest from it. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Triangulation of quads

Open this post in threaded view
|

## Re: Triangulation of quads

Open this post in threaded view
|

## Re: Triangulation of quads

 Are you sure, you have squares? You seem to twist the extrusion. Then your rects are crooked and it is natural that the shorter diagonal is better. This is how a spring from my  springs and springmaker library   looks: -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Triangulation of quads

 Yes the minimum rotation algorithm seems to create the twist, not sure why. I wonder if a real spring is twisted. Frenet-Serret  isn't twisted but it gets weird at the discontinuities in curvature  near the ends.I made a mistake earlier when I said the diagonals were equal. I was subtracting the indices instead of the coordinates. Fixing that and picking the shortest diagonal works for clockwise and anti-clockwise springs. Thanks for pointing that out.Why doesn't linear_extrude pick the shortest diagonal if that is the solution?On Thu, 24 Jan 2019 at 11:20, Parkinbot <[hidden email]> wrote:Are you sure, you have squares? You seem to twist the extrusion. Then your rects are crooked and it is natural that the shorter diagonal is better. This is how a spring from my  springs and springmaker library    looks: -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Triangulation of quads

 nophead wrote > Why doesn't linear_extrude pick the shortest diagonal if that is the > solution? Good question. You are right! linear_extrude(50, twist = 360, slices=20) translate([5,0]) square(10); I have not observed it because it was never very important to me. To be honest I don't know, whether linear_extrude() is implemented to produce triags or quads. But you are right, the result would be way better if it used always the shorter diagonal. Looks like an adversity that can easily be fixed. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Triangulation of quads

 In reply to this post by nophead nop head <[hidden email]> wrote:How do you get rid of the twist?Just calculate the total section angular rotation about its "center" and distribute this total angle along the path. It is an aproximation because the twist rate may vary along the path but it works very fine with helicoidal paths. You can accesses my version in: The untwist is done by  construct_transform_path(). _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Triangulation of quads

 In reply to this post by nophead > ... I wonder if a real spring is twisted. Coil springs mostly act in torsion - they twist and the spring expands and contracts. They're usually made by wrapping wire or rod around a mandrel, so they're not that twisted at rest. > ... Why doesn't linear_extrude pick the shortest diagonal if that is the > solution? ... Are you sure it's "the solution?"  Maybe it always works right for rotate extrude, but I'm pretty certain that "longer diagonal" does not work as a general answer. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Triangulation of quads

Open this post in threaded view
|

## Re: Triangulation of quads

Open this post in threaded view
|

## Re: Triangulation of quads

 I am pretty sure that the pair of triangles that results from the shorter diagonal of a quad is a better approximation. Triags with sharp angles and long sides should be avoided if you have a better choice. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Triangulation of quads

Open this post in threaded view
|

## Re: Triangulation of quads

Open this post in threaded view
|

## Re: Triangulation of quads

 In reply to this post by nophead On Wed, Jan 23, 2019 at 10:05:58PM +0000, nop head wrote: > If I reverse the handedness of the spiral then the other diagonal is the > correct one. Does anybody know the correct algorithm? The length of the two > diagonals is the same so that can't be used to choose between them. The current rendering uses a single shade that depends on the normal of the triangle. If the length of the diagonals are not equal, chosing the shorter triangle reduces the "aspect ratio" (longest possible line segment divided by the largest perpendicular segment). As an example: imagine two equilateral triangles joined to a rhombus. Split them into the two original triangles and the aspect ratio is almost one (sqrt(3)/2 iirc). Split it the other way and you get a much larger aspect ratio. Something like sqrt(3) or even more. The aspect ratio being small means that the points of that triangle will be colored the same to "close" points. A pointy triangle has points far away that will be colored the same due to having the same normal. For presentation (i.e. not 3D printing) you can do "phong shading". This has something to do with averaging colors close to an edge between two triangles. An object shaded that way will look "perfectly round" until you start examining the image at the pixel scale. This would be great for quick rendering realistic representation of an object where you're working with a low \$fn during development but are going to increase \$fn for final rendering to be printed. > I am thinking that one way makes a convex surface patch and the other way > concave. I think that if the surface is convex in the area of the patch > then the diagonal should be chosen to give a convex patch and vice versa. > Does that make sense? That sounds like a plan. > Not sure how I would code that efficiently. Is there a better way than > calculating the normals of the triangles to determine if the patch is > concave or convex. And is there an easy way to determine if the surface is > locally concave or convex? In this case it is always convex so I could > cheat and always assume that. It would be right most of the time as a swept > surface must always be partially convex. The inside of the spring is concave (in one direction) (I'm guessing that this is exaclty the "partially convex" that you say :-) ).         Roger. -- ** [hidden email] ** https://www.BitWizard.nl/ ** +31-15-2049110 ** **    Delftechpark 11 2628 XJ  Delft, The Netherlands.  KVK: 27239233    ** The plan was simple, like my brother-in-law Phil. But unlike Phil, this plan just might work. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Triangulation of quads

 In reply to this post by Whosawhatsis I didn't get that in the sense of the general case with n slices. Can you show linear_extrusion code that has this problem? Obviously, when you do a twisted linear_extrusion say with 5 slices and the result is exactly what you want, you are better of. Whosawhatsis wrote > There are clearly cases where this is wrong, though. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Triangulation of quads

Open this post in threaded view
|

## Re: Triangulation of quads

 In reply to this post by Kenneth Sloan Kenneth Sloan wrote > Second best is to be exceedingly careful with non-planar quads.  Again - a > good approach is > often to subdivide by producing a good point on your intended surface at > the center of the > quad to produce FOUR triangles instead of trying to make do with only TWO. This is not practicable for linear_extrude in a general sense, since it uses an integral slices variable. And even then it is not trivial as it would imply to also subdivide the polygon, i.e. getting 8 vertices for a square. So multiplying slices by 2 will multiply the number of triags by four. -- Sent from: http://forum.openscad.org/_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Triangulation of quads

 In reply to this post by Parkinbot Actually linear extrude seems to chose the longest diagonal. It definitely looks bad for negative twists but less so for positive ones. I wonder what it would look like if it choose the shortest on positive twists.On Fri, 25 Jan 2019 at 13:43, Parkinbot <[hidden email]> wrote:I didn't get that in the sense of the general case with n slices. Can you show linear_extrusion code that has this problem? Obviously, when you do a twisted linear_extrusion say with 5 slices and the result is exactly what you want, you are better of. Whosawhatsis wrote > There are clearly cases where this is wrong, though. -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org