discuss@lists.openscad.org

OpenSCAD general discussion Mailing-list

View all threads

Triangulation of quads

W
Whosawhatsis
Thu, Jan 24, 2019 8:02 PM

The answer kinda depends on whether the part of the surface in question
exhibits positive or negative curvature. On the outside of your spring,
which has positive curvature, it's clear which diagonal looks better, but
for the negative curvature inside, the answer is less clear. In some cases,
what looks "right" depends more on which direction you're viewing from than
which diagonal is shorter.

The best solution actually comes from staggering your points. I wrote code
for generating mathematical surfaces in the form of z = f(x, y), and I
recently rewrote it to sample points on an equilateral triangular grid
rather than a square grid to solve this problem. By choosing the shorter
diagonal across a quad, you're soft of approximating this solution.

There can still be spots that don't look perfectly smooth (usually because
the function has a high second derivative), but it generally handles these
things a lot better than the square grid. The next step in complexity would
be to write code to use a variable mesh density (or at least one that
remains constant relative to the face's orientation, rather than just
relative to the x/y plane), but without true variables, that would be very
difficult to implement. Even with true variables, I'm sure thesis papers in
topology have been written on the subject, some of which likely resulted in
some of the re-meshing algorithms in Meshlab.

On January 24, 2019 at 11:13:36, nop head (nop.head@gmail.com) wrote:

No its the shorter diagonal, not the longer.  I am pretty sure it isn't a
general solution for any quad patch on a 3D surface. It might be for a
sweep where the quads are always in rings, but I don't know. Seems to work
with helical springs.

The spring machines I have seen feed wire though a nozzle against an anvil
that forces it to turn into a helix . The anvil moves allowing it to vary
the pitch and diameter continuously if necessary. Then it cuts it off and
starts a new one.

On Thu, 24 Jan 2019 at 17:47, NateTG nate-openscadforum@pedantic.org
wrote:

... 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

The answer kinda depends on whether the part of the surface in question exhibits positive or negative curvature. On the outside of your spring, which has positive curvature, it's clear which diagonal looks better, but for the negative curvature inside, the answer is less clear. In some cases, what looks "right" depends more on which direction you're viewing from than which diagonal is shorter. The best solution actually comes from staggering your points. I wrote code for generating mathematical surfaces in the form of z = f(x, y), and I recently rewrote it to sample points on an equilateral triangular grid rather than a square grid to solve this problem. By choosing the shorter diagonal across a quad, you're soft of approximating this solution. There can still be spots that don't look perfectly smooth (usually because the function has a high second derivative), but it generally handles these things a lot better than the square grid. The next step in complexity would be to write code to use a variable mesh density (or at least one that remains constant relative to the face's orientation, rather than just relative to the x/y plane), but without true variables, that would be very difficult to implement. Even with true variables, I'm sure thesis papers in topology have been written on the subject, some of which likely resulted in some of the re-meshing algorithms in Meshlab. On January 24, 2019 at 11:13:36, nop head (nop.head@gmail.com) wrote: No its the shorter diagonal, not the longer. I am pretty sure it isn't a general solution for any quad patch on a 3D surface. It might be for a sweep where the quads are always in rings, but I don't know. Seems to work with helical springs. The spring machines I have seen feed wire though a nozzle against an anvil that forces it to turn into a helix . The anvil moves allowing it to vary the pitch and diameter continuously if necessary. Then it cuts it off and starts a new one. On Thu, 24 Jan 2019 at 17:47, NateTG <nate-openscadforum@pedantic.org> wrote: > > ... 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 > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org > _______________________________________________ OpenSCAD mailing list Discuss@lists.openscad.org http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
P
Parkinbot
Thu, Jan 24, 2019 10:02 PM

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/

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/
KS
Kenneth Sloan
Fri, Jan 25, 2019 1:32 AM

This is an ancient story.  The bottom line is that quads lead to all sorts of problems.

Best (if you can manage it) is to deal with purely triangular meshes.

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.

Finally, when forced to choose a diagonal,  you can evaluate the error at the center of the
quad - or you can blindly choose the smaller of the two diagonals.

--
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.

On Jan 24, 2019, at 4:02 PM, Parkinbot rudolf@digitaldocument.de wrote:

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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

This is an ancient story. The bottom line is that quads lead to all sorts of problems. Best (if you can manage it) is to deal with purely triangular meshes. 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. Finally, when forced to choose a diagonal, you can evaluate the error at the center of the quad - or you can blindly choose the smaller of the two diagonals. -- Kenneth Sloan KennethRSloan@gmail.com Vision is the art of seeing what is invisible to others. > On Jan 24, 2019, at 4:02 PM, Parkinbot <rudolf@digitaldocument.de> wrote: > > 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 > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
W
Whosawhatsis
Fri, Jan 25, 2019 5:01 AM

There are clearly cases where this is wrong, though. Imagine a sheet of
graph paper with a diagonal fold. For each of the grid squares along the
fold, the diagonal running perpendicular to the fold will be the shorter
one, but if you mesh it that way, you will end up with a jagged line down
the fold rather than a uniform one.

It doesn't even have to be a fold. A gentle bend in the sheet will have the
same problem, just to a lesser extent. This is a case where there is
clearly a "right" and "wrong" diagonal to choose, and picking the shorter
one will give you the wrong answer.

The "choose the shorter diagonal" rule will, when it fails to give the
right answer, at least give you an answer that is less wrong than if you
had chosen the longer diagonal and that choice had been wrong, but it's
not going to be the right choice every time.

On January 24, 2019 at 14:03:37, Parkinbot (rudolf@digitaldocument.de)
wrote:

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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

There are clearly cases where this is wrong, though. Imagine a sheet of graph paper with a diagonal fold. For each of the grid squares along the fold, the diagonal running perpendicular to the fold will be the shorter one, but if you mesh it that way, you will end up with a jagged line down the fold rather than a uniform one. It doesn't even have to be a fold. A gentle bend in the sheet will have the same problem, just to a lesser extent. This is a case where there is clearly a "right" and "wrong" diagonal to choose, and picking the shorter one will give you the wrong answer. The "choose the shorter diagonal" rule will, when it fails to give the right answer, at least give you an answer that is less wrong than if you had chosen the longer diagonal and *that* choice had been wrong, but it's not going to be the right choice every time. On January 24, 2019 at 14:03:37, Parkinbot (rudolf@digitaldocument.de) wrote: 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 Discuss@lists.openscad.org http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
RW
Rogier Wolff
Fri, Jan 25, 2019 12:17 PM

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. 

--
** R.E.Wolff@BitWizard.nl ** 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.

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. -- ** R.E.Wolff@BitWizard.nl ** 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.
P
Parkinbot
Fri, Jan 25, 2019 1:41 PM

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.

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/
NH
nop head
Fri, Jan 25, 2019 1:49 PM

No what I mean't was no shape can be totally concave on the outside, it
must curve back to meet itself and be convex as it does so.

Even on the inside of the spring, a quad oriented along it should still be
folded to be convex. Locally the surface is more convex around the ring and
less concave along it. So perhaps you would look the four neighbouring
quads on its sides and pick the most curved direction to decide it
should be convex or concave.

On Fri, 25 Jan 2019 at 12:18, Rogier Wolff R.E.Wolff@bitwizard.nl wrote:

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.

--
** R.E.Wolff@BitWizard.nl ** 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
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

No what I mean't was no shape can be totally concave on the outside, it must curve back to meet itself and be convex as it does so. Even on the inside of the spring, a quad oriented along it should still be folded to be convex. Locally the surface is more convex around the ring and less concave along it. So perhaps you would look the four neighbouring quads on its sides and pick the most curved direction to decide it should be convex or concave. On Fri, 25 Jan 2019 at 12:18, Rogier Wolff <R.E.Wolff@bitwizard.nl> wrote: > 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. > > -- > ** R.E.Wolff@BitWizard.nl ** 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 > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >
P
Parkinbot
Fri, Jan 25, 2019 1:55 PM

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/

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/
NH
nop head
Fri, Jan 25, 2019 2:01 PM

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 rudolf@digitaldocument.de 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.

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 <rudolf@digitaldocument.de> 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 > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >
NH
nop head
Fri, Jan 25, 2019 2:12 PM

I think the asymmetry is due to the lighting direction. Even with positive
twist it looks to have concave dimples.  My guess is it would look better
in both case if it chose the shortest diagonal to make the quads convex.

On Fri, 25 Jan 2019 at 14:01, nop head nop.head@gmail.com wrote:

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 rudolf@digitaldocument.de 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.

I think the asymmetry is due to the lighting direction. Even with positive twist it looks to have concave dimples. My guess is it would look better in both case if it chose the shortest diagonal to make the quads convex. On Fri, 25 Jan 2019 at 14:01, nop head <nop.head@gmail.com> wrote: > 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 <rudolf@digitaldocument.de> 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 >> Discuss@lists.openscad.org >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >