Triangulation of quads

classic Classic list List threaded Threaded
63 messages Options
1234
Reply | Threaded
Open this post in threaded view
|

Triangulation of quads

nophead
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.

image.png

 Here I split them on the other diagonal and it looks much smoother.

image.png

Here I present them to polyhedron as quads and let F5 triangulate them.

image.png
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.

image.png



_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

NateTG
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
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

Ronaldo
In reply to this post by nophead
nophead,

There is many aspects in your observations and questions. First, there are points where you can't classify (with respect to its interior) the surface of a solid as convex or concave. For instance, the points in your spring that are nearest to the axis: they have a positive curvature in one direction and negative in other.

Besides, there is a torsion effect that makes things worst. Your cylinder is an example: if all circular level cuts were translations, the quads would be planar. In particular, the sweep of the list comprehension demos produces a twist between sections along a helicoidal path and the quads are non planar. This could be avoided by untwisting it. I have a version of sweep.scad which do that.

When a quad is non planar it induces a saddle surface that is neither convex or concave. If the diagonals have different length to choose the smallest one may a good measure for convex surfaces. Otherwise, none of the two diagonals is best.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

nophead
Yes the non-planar quads are not concave or convex in isolation but when you add the diagonal the two triangle are. When they form a concave dimple the shading alternates between light and dark and makes it visible that they are dimples in a surface that should be all convex. When split the correct way the shading changes monotonically, so it looks smoothly convex. Not only is the shading no longer alternating but it also has smaller changes between adjacent triangles, so you can get away with less of them.

Since the quads in a sweep are not in arbitrary places, they are arranged in rings, I think it is probably sufficient to work out which way the quad is twisting to pick the correct diagonal. 

How do you get rid of the twist?

On Thu, 24 Jan 2019 at 00:01, Ronaldo Persiano <[hidden email]> wrote:
nophead,

There is many aspects in your observations and questions. First, there are points where you can't classify (with respect to its interior) the surface of a solid as convex or concave. For instance, the points in your spring that are nearest to the axis: they have a positive curvature in one direction and negative in other.

Besides, there is a torsion effect that makes things worst. Your cylinder is an example: if all circular level cuts were translations, the quads would be planar. In particular, the sweep of the list comprehension demos produces a twist between sections along a helicoidal path and the quads are non planar. This could be avoided by untwisting it. I have a version of sweep.scad which do that.

When a quad is non planar it induces a saddle surface that is neither convex or concave. If the diagonals have different length to choose the smallest one may a good measure for convex surfaces. Otherwise, none of the two diagonals is best.
_______________________________________________
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
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

Parkinbot
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
<https://www.thingiverse.com/thing:3252637>   looks:
<http://forum.openscad.org/file/t887/springquad.png>



--
Sent from: http://forum.openscad.org/

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

nophead
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.

image.png

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
<https://www.thingiverse.com/thing:3252637>   looks:
<http://forum.openscad.org/file/t887/springquad.png>



--
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
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

Parkinbot
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
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

Ronaldo
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
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

NateTG
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
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

nophead
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 <[hidden email]> 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
[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
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

Whosawhatsis
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 ([hidden email]) 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 <[hidden email]> 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
[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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

Parkinbot
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
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

Kenneth Sloan
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
[hidden email]
Vision is the art of seeing what is invisible to others.





> On Jan 24, 2019, at 4:02 PM, Parkinbot <[hidden email]> 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
> [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
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

Whosawhatsis
In reply to this post by Parkinbot
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 ([hidden email]) 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
[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
rew
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

rew
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
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

Parkinbot
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
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

nophead
In reply to this post by rew
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 <[hidden email]> 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.

--
** [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

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

Parkinbot
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
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

nophead
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
Reply | Threaded
Open this post in threaded view
|

Re: Triangulation of quads

nophead
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 <[hidden email]> 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 <[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
1234